# Why does the discrepancy measure involve a supremum over the hypothesis space?

I am referring specifically to the disc defined by Kuznetsov and Mohri in https://arxiv.org/pdf/1803.05814.pdf

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.

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 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 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.

• 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. Feb 11 '20 at 8:27
• @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).
– nbro
Feb 11 '20 at 12:11
• Yes it is. What I am asking is a deeper question about the topics specific to the paper. mathworld.wolfram.com/SupremumNorm.html Feb 11 '20 at 14:02
• @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?
– nbro
Feb 11 '20 at 14:26
• 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 en.wikipedia.org/wiki/… Feb 12 '20 at 14:07