# 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.
• 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. – mathtick Feb 11 '20 at 8:27
• 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/… – mathtick Feb 12 '20 at 14:07