I found that the regret in Online Machine Learning is stated as:

$$\operatorname{Regret}_{T}(h)=\sum_{t=1}^{T} l\left(p_{t}, y_{t}\right)-\sum_{t=1}^{T} l\left(h(x), y_{t}\right),$$

where $p_t$ is the answer of my algorithm to the question $x$ and $y_t$ is the right answer, while $h()$ is one of the hypotheses in the hypothesis space. Intuitively, as denoted in the paper, our objective is to minimize this Regret in order to optimize our algorithm, but in the following formula

$$ \operatorname{Regret}_{T}(\mathcal{H})=\max _{h^{\star} \in \mathcal{H}} \operatorname{Regret}_{T}\left(h^{\star}\right) $$

they maximize this value. Am I interpreting the $max$ wrongly?


Yes, you're interpreting the $\max$ there wrongly. In your second formula

$$ \operatorname{Regret}_{T}(\mathcal{H})=\max _{h^{\star} \in \mathcal{H}} \operatorname{Regret}_{T}\left(h^{\star}\right) \label{1}\tag{1} $$

The sign $=$ means "is defined as", so maybe the following notation is less confusing

$$ \operatorname{Regret}_{T}(\mathcal{H}) \triangleq \max _{h^{\star} \in \mathcal{H}} \operatorname{Regret}_{T}\left(h^{\star}\right) $$

In fact, in section 2.1 of the same paper, there's a similar but more detailed formula that should clarify the meaning of $\max$ $$ \operatorname{Regret}_{T}(\mathcal{H})=\max _{h \in \mathcal{H}}\left(\sum_{t=1}^{T}\left|p_{t}-y_{t}\right|-\sum_{t=1}^{T}\left|h\left(\mathbf{x}_{t}\right)-y_{t}\right|\right) $$

Note that $\operatorname{Regret}_{T}(\mathcal{H})$ is defined for $\mathcal{H}$, while your first formula is defined for $x$. So, \ref{1} is the regret for the whole hypotheses class $\mathcal{H}$, which is thus the maximum regret that you can have across all possible hypotheses $h \in \mathcal{H}$. This should make sense.

  • $\begingroup$ I corrected the argument of my first formula, it was h not x. Anyway thank you, I thought was "is defined as" but I was not sure $\endgroup$ – FraMan Jul 29 '20 at 7:36
  • $\begingroup$ @FraMan But note that you had taken a screenshot of the formula and it was $x$ because I used a program to convert the screenshot to the latex formula. $\endgroup$ – nbro Jul 29 '20 at 12:34
  • $\begingroup$ I wrote the Latex formula wrong and then I uploaded a screenshot of that formula because I'm stupid :) $\endgroup$ – FraMan Jul 29 '20 at 13:18
  • $\begingroup$ @FraMan Haah, don't worry, man :) $\endgroup$ – nbro Jul 29 '20 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.