Answers.Body: <p>Yes, you're interpreting the <span class="math-container">$\max$</span> there wrongly. In your second formula</p>
  <p><span class="math-container">$$
  \operatorname{Regret}_{T}(\mathcal{H})=\max _{h^{\star} \in \mathcal{H}} \operatorname{Regret}_{T}\left(h^{\star}\right) \label{1}\tag{1}
  $$</span></p>
  <p>The sign <span class="math-container">$=$</span> means &quot;is defined as&quot;, so maybe the following notation is less confusing</p>
  <p><span class="math-container">$$
  \operatorname{Regret}_{T}(\mathcal{H}) \triangleq \max _{h^{\star} \in \mathcal{H}} \operatorname{Regret}_{T}\left(h^{\star}\right)
  $$</span></p>
  <p>In fact, in <a href="https://www.cs.huji.ac.il/%7Eshais/papers/OLsurvey.pdf#page=8" rel="nofollow noreferrer">section 2.1 of the same paper</a>, there's a similar but more detailed formula that should clarify the meaning of <span class="math-container">$\max$</span>
  <span class="math-container">$$
  \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)
  $$</span></p>
  <p>Note that <span class="math-container">$\operatorname{Regret}_{T}(\mathcal{H})$</span> is defined for <span class="math-container">$\mathcal{H}$</span>, while your first formula is defined for <span class="math-container">$x$</span>. So, \ref{1} is the regret for the whole hypotheses class <span class="math-container">$\mathcal{H}$</span>, which is thus the maximum regret that you can have across all possible hypotheses <span class="math-container">$h \in \mathcal{H}$</span>. This should make sense.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-29T07:36:06.853Z
Answers.Text: 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
Answers.UserDisplayName: FraMan
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-29T12:34:53.653Z
Answers.Text: @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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-29T13:18:19.237Z
Answers.Text: I wrote the Latex formula wrong and then I uploaded a screenshot of that formula because I'm stupid :)
Answers.UserDisplayName: FraMan
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-29T13:41:31.373Z
Answers.Text: @FraMan Haah, don't worry, man :)
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-28T19:49:07.880Z
Answers.LastActivityDate: 2020-07-28T19:49:07.880Z
Answers.UserDisplayName: nbro
Body: <p>I found that the regret in <a href="https://www.cs.huji.ac.il/%7Eshais/papers/OLsurvey.pdf" rel="nofollow noreferrer">Online Machine Learning</a> is stated as:</p>
  <p><span class="math-container">$$\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),$$</span></p>
  <p>where <span class="math-container">$p_t$</span> is the answer of my algorithm to the question <span class="math-container">$x$</span> and <span class="math-container">$y_t$</span> is the right answer, while <span class="math-container">$h()$</span> 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</p>
  <p><span class="math-container">$$
  \operatorname{Regret}_{T}(\mathcal{H})=\max _{h^{\star} \in \mathcal{H}} \operatorname{Regret}_{T}\left(h^{\star}\right)
  $$</span></p>
  <p>they maximize this value. Am I interpreting the <span class="math-container">$max$</span> wrongly?</p>
  
Tags: <machine-learning><optimization><computational-learning-theory><online-learning>
Title: Does this $\max$ mean that we need to maximize the regret in this regret formula?
UserDisplayName: FraMan
ThreadText: # Does this $\max$ mean that we need to maximize the regret in this regret formula?
  
  (Asked by: username_0 on 2020-07-28)
  
  I found that the regret in [Online Machine Learning](https://www.cs.huji.ac.il/%7Eshais/papers/OLsurvey.pdf) 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?
  
  **Tags:** machine-learning, optimization, computational-learning-theory, online-learning
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-07-28. Score: 1 | Accepted answer
  
  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](https://www.cs.huji.ac.il/%7Eshais/papers/OLsurvey.pdf#page=8), 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.
  
  > **Comments:**
  > **username_0**: 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  
  > **username_1**: @username_0 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.  
  > **username_0**: I wrote the Latex formula wrong and then I uploaded a screenshot of that formula because I'm stupid :)  
  > **username_1**: @username_0 Haah, don't worry, man :)  
  
  ---
  
  