Answers.Body: <p>The formula <span class="math-container">$G=\mathbb{E}\left[ f(Z_{T+1}) \mid \mathbf{Z}_1^T\right] - \sum_{t=1}^Tq_t \mathbb{E}\left[ f(Z_t) \mid \mathbf{Z}_1^{t-1} \right]$</span> actually represents a set, for all possible values of <span class="math-container">$f$</span>. Therefore, <span class="math-container">$\text{disc}(\mathbf{q}) = \operatorname{sup}_{f \in \mathcal{F}} \left( \mathbb{E}\left[ f(Z_{T+1}) \mid \mathbf{Z}_1^T\right] - \sum_{t=1}^Tq_t \mathbb{E}\left[ f(Z_t) \mid \mathbf{Z}_1^{t-1} \right] \right)$</span> is the element <strong>not</strong> necessarily in that set <span class="math-container">$G$</span> that is greater than all elements in that set <span class="math-container">$G$</span>, but is the smaller than any other element that is greater than any element in that set <span class="math-container">$G$</span>. In other words, <span class="math-container">$\text{disc}(\mathbf{q})$</span> represents an upper bound on the discrepancy <span class="math-container">$G$</span>, but it is the smallest possible upper bound. See also <a href="https://math.stackexchange.com/a/166661/168764">this answer</a> for more details about the supremum and the relationship between the supremum and upper bounds.</p>
  
  <p>So, unless I am wrong, this is not necessarily a worst-case analysis (but I am not even sure how one would define the worst-case analysis in this context), but we are looking for the smallest upper bound. In the context of algorithms, the worst-case analysis is with respect to the input (i.e. the worst-case input), but you can have upper or lower bounds for worst and best-case scenarios. See, for example, <a href="https://stackoverflow.com/a/7485213/3924118">this answer</a> that illustrates this. Why do we want an upper bound? Because we can be certain that we won't have a generalization error worse than it. You can't do this with e.g. a lower bound.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-11T08:27:13.050Z
Answers.Text: I am referring more to the choice of sup as opposed to any other norm. I think in this case, there is something not immediately obvious where the sup norm is driving the  $q$ weights and for these $q$ weights you then optimize over the standard objective. The sup norm is a particularly choice of norm here and maybe is just chosen as it is worst case, or maybe it is the only possible choice for the bounds that follow to be amenable.
Answers.UserDisplayName: safetyduck
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-11T12:11:21.030Z
Answers.Text: @mathtick The supremum is not a norm. I still don't get why you're talking about worst-case. Here we are talking about an upper bound (not worst-case).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-11T14:02:43.433Z
Answers.Text: Yes it is. What I am asking is a deeper question about the topics specific to the paper.
  
  http://mathworld.wolfram.com/SupremumNorm.html
Answers.UserDisplayName: safetyduck
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-11T14:26:14.203Z
Answers.Text: @mathtick Ok, I was not aware of this supremum norm, but, in your case, where is this norm? The supremum norm involves an absolute value or a norm (inside the set), but you have only the supremum there and the difference between two expectations. What's your deeper question? And what "norm" or other operators would use other than the supremum?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-12T14:07:32.623Z
Answers.Text: There are usually various inequalities related different kinds of norms. For example often one is working in $L_p$ space where the $p$ norm is indicates some choice of norm. $L_1$, $L_2$, and $L_{\infty}$ are ones you probably know. See https://en.wikipedia.org/wiki/Lp_space#The_p-norm_in_countably_infinite_dimensions_and_%E2%84%93_p_spaces
Answers.UserDisplayName: safetyduck
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-12T14:08:40.667Z
Answers.Text: And reading further after I posted, I think mostly the sup is used as it is the only way to extend the inequalities encountered further on without additional assumptions on the distributions. Not 100% on that but that is the hunch.
Answers.UserDisplayName: safetyduck
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-12T17:20:58.403Z
Answers.Text: @mathtick You still haven't answered why the sup in your equation is used as a norm. In all examples of the supremum norm that I've seen include an absolute value or norm inside the expression, but your equation doesn't include that. That's why I am not sure that your expression represents a supremum norm. Yes, I know that there are different norms (but I mainly used or saw them in the context of linear algebra, etc.).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-13T09:43:05.620Z
Answers.Text: What does "used as a norm" mean? These *can* be interpreted as norms, the triangle inequality is used later in the paper etc. I just typically call these things norms without worrying about whether all properties of a norm are used.
Answers.UserDisplayName: safetyduck
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-11T01:19:16.960Z
Answers.LastActivityDate: 2020-02-11T12:18:07.253Z
Answers.LastEditDate: 2020-02-11T12:18:07.253Z
Answers.UserDisplayName: nbro
Body: <p>I am referring specifically to the disc defined by Kuznetsov and Mohri in <a href="https://arxiv.org/pdf/1803.05814.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1803.05814.pdf</a></p>
  
  <p><a href="https://i.sstatic.net/TVtez.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/TVtez.png" alt="enter image description here"></a></p>
  
  <p>This is a kind of worst case path dependent generalization error. But what is the intuitive way of seeing why a <em>worst</em> case is needed? I am probably missing something or reading something incorrectly. </p>
  
Tags: <computational-learning-theory><generalization>
Title: Why does the discrepancy measure involve a supremum over the hypothesis space?
UserDisplayName: safetyduck
ThreadText: # Why does the discrepancy measure involve a supremum over the hypothesis space?
  
  (Asked by: username_0 on 2020-02-10)
  
  I am referring specifically to the disc defined by Kuznetsov and Mohri in <https://arxiv.org/pdf/1803.05814.pdf>
  
  [![enter image description here](https://i.sstatic.net/TVtez.png)](https://i.sstatic.net/TVtez.png)
  
  This is a kind of worst case path dependent generalization error. But what is the intuitive way of seeing why a *worst* case is needed? I am probably missing something or reading something incorrectly.
  
  **Tags:** computational-learning-theory, generalization
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-02-11. Score: 1
  
  The formula $G=\mathbb{E}\left[ f(Z\_{T+1}) \mid \mathbf{Z}\_1^T\right] - \sum\_{t=1}^Tq\_t \mathbb{E}\left[ f(Z\_t) \mid \mathbf{Z}\_1^{t-1} \right]$ actually represents a set, for all possible values of $f$. Therefore, $\text{disc}(\mathbf{q}) = \operatorname{sup}\_{f \in \mathcal{F}} \left( \mathbb{E}\left[ f(Z\_{T+1}) \mid \mathbf{Z}\_1^T\right] - \sum\_{t=1}^Tq\_t \mathbb{E}\left[ f(Z\_t) \mid \mathbf{Z}\_1^{t-1} \right] \right)$ is the element **not** necessarily in that set $G$ that is greater than all elements in that set $G$, but is the smaller than any other element that is greater than any element in that set $G$. In other words, $\text{disc}(\mathbf{q})$ represents an upper bound on the discrepancy $G$, but it is the smallest possible upper bound. See also [this answer](https://math.stackexchange.com/a/166661/168764) for more details about the supremum and the relationship between the supremum and upper bounds.
  
  So, unless I am wrong, this is not necessarily a worst-case analysis (but I am not even sure how one would define the worst-case analysis in this context), but we are looking for the smallest upper bound. In the context of algorithms, the worst-case analysis is with respect to the input (i.e. the worst-case input), but you can have upper or lower bounds for worst and best-case scenarios. See, for example, [this answer](https://stackoverflow.com/a/7485213/3924118) that illustrates this. Why do we want an upper bound? Because we can be certain that we won't have a generalization error worse than it. You can't do this with e.g. a lower bound.
  
  > **Comments:**
  > **username_0**: I am referring more to the choice of sup as opposed to any other norm. I think in this case, there is something not immediately obvious where the sup norm is driving the  $q$ weights and for these $q$ weights you then optimize over the standard objective. The sup norm is a particularly choice of norm here and maybe is just chosen as it is worst case, or maybe it is the only possible choice for the bounds that follow to be amenable.  
  > **username_1**: @mathtick The supremum is not a norm. I still don't get why you're talking about worst-case. Here we are talking about an upper bound (not worst-case).  
  > **username_0**: Yes it is. What I am asking is a deeper question about the topics specific to the paper.  http://mathworld.wolfram.com/SupremumNorm.html  
  > **username_1**: @mathtick Ok, I was not aware of this supremum norm, but, in your case, where is this norm? The supremum norm involves an absolute value or a norm (inside the set), but you have only the supremum there and the difference between two expectations. What's your deeper question? And what "norm" or other operators would use other than the supremum?  
  > **username_0**: There are usually various inequalities related different kinds of norms. For example often one is working in $L_p$ space where the $p$ norm is indicates some choice of norm. $L_1$, $L_2$, and $L_{\infty}$ are ones you probably know. See https://en.wikipedia.org/wiki/Lp_space#The_p-norm_in_countably_infinite_dimensions_and_%E2%84%93_p_spaces  
  > **username_0**: And reading further after I posted, I think mostly the sup is used as it is the only way to extend the inequalities encountered further on without additional assumptions on the distributions. Not 100% on that but that is the hunch.  
  > **username_1**: @mathtick You still haven't answered why the sup in your equation is used as a norm. In all examples of the supremum norm that I've seen include an absolute value or norm inside the expression, but your equation doesn't include that. That's why I am not sure that your expression represents a supremum norm. Yes, I know that there are different norms (but I mainly used or saw them in the context of linear algebra, etc.).  
  > **username_0**: What does "used as a norm" mean? These *can* be interpreted as norms, the triangle inequality is used later in the paper etc. I just typically call these things norms without worrying about whether all properties of a norm are used.  
  
  ---
  
  