1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2020 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, 2020 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, 2020 at 13:18
  • $\begingroup$ @FraMan Haah, don't worry, man :) $\endgroup$
    – nbro
    Jul 29, 2020 at 13:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .