# Bounding the uniform deviation of the empirical risk from the risk over a finite function class

I am having difficulty interpreting the following theorem from here as a probability statement:

Theorem.

For all $$\delta$$ such that $$0 < \delta < 1/2$$, with proability at least $$1 - \delta$$ the following is true $$\lvert \hat{R}_n(f) - {R}(f) \rvert \leq \sqrt{\frac{\ln \lvert \mathcal{F} \rvert + \ln (2 / \delta)}{2n}} \quad \forall f \in \mathcal{F} \tag{4.3}$$

Where $$\hat{R}_n(f) = n^{-1} \sum^n_{i=1} \mathbb{I}(Y_i \neq f(X_i))$$ is the empirical risk under a 0/1 loss function from $$n$$ training data points $$(X_i, Y_i)$$ drawn from an unknown distribution $$p^*$$, and $$R(f) = \mathbb{E}_{(X, Y) \sim p^*}[\mathbb{I}(Y \neq f(X))]$$ is the risk. $$f$$ is a linear classifier in a function class $$\mathcal{F}$$ that is finite i.e. $$\lvert \mathcal{F} \rvert < \infty$$.

Query.

If I were to rewrite this as a probability statement, would the qualifier $$\forall f \in \mathcal{F}$$ go inside or outside the probability statement?

That is, should the above theorem read:

$$\mathbb{P} \left( \forall f \in \mathcal{F} \lvert \hat{R}_n(f) - R(f) \rvert \leq \sqrt{\frac{\ln \lvert \mathcal{F} \rvert + \ln (2 / \delta)}{2n}}\right) \geq 1 - \delta \tag{A}$$

Or should it read:

$$\forall f \in \mathcal{F} , \mathbb{P} \left( \lvert \hat{R}_n(f) - R(f) \rvert \leq \sqrt{\frac{\ln \lvert \mathcal{F} \rvert + \ln (2 / \delta)}{2n}}\right) \geq 1 - \delta \tag{B}$$

Further context - proof of the theorem.

I will now detail each step of the proof, which is fairly standard in the statistics and statistical learning theory literature, together with my understanding.

Step 1 - Bound the deviation of the empirical risk from the risk for a single function $$f \in \mathcal{F}$$ using a concentration inequality.

For a single function $$f \in \mathcal{F}$$, as the empirical risk $$\hat{R}(f)$$ is the sample average of i.i.d. Bernoulli rvs, and the risk $$R(f)$$ is the theoretical expectation, we have that

$$\mathbb{P} \left( \lvert \hat{R}(f) - R(f) \rvert \geq \epsilon \right) \leq 2\exp(-2n\epsilon^2)$$

Step 2 - Bound the uniform deviation using the union bound.

My understanding is that we require the empirical risk to be a good estimate of the risk in the sense of being 'uniformly close' to the risk over the entire function class $$\mathcal{F}$$ . And that Hoeffding's inequality by itself is insufficient, because for a particular $$f \in \mathcal{F}$$, there will be a set of training samples $$S_f$$ such that $$\hat{R}(f) - R(f) \leq \epsilon$$ with probability $$\mathbb{P}(S_f) \geq 1 - 2\exp(-2n\epsilon^2)$$, and the crux is that in general, this set $$S_f$$ will be different for different functions in $$\mathcal{F}$$.

We define the event $$E_f = \{\lvert \hat{R}(f) - R(f) \rvert \geq \epsilon\}$$ and as the function class $$\mathcal{F}$$ is finite, apply the union bound over $$E_f$$:

\begin{align} \mathbb{P} \left( \sup_{f \in \mathcal{F}} \lvert \hat{R}_n(f) - R(f) \rvert \geq \epsilon \right) &= \mathbb{P}\left( \bigcup_{f \in \mathcal{F}} \{ \lvert \hat{R}_n(f) - R(f) \rvert \geq \epsilon\} \right) \\ &\leq \sum_{f \in \mathcal{F}} \mathbb{P} \left(\lvert \hat{R}_n(f) - R(f) \rvert \geq \epsilon\right) \\ &\leq \sum_{f \in \mathcal{F}} 2 \exp(-2n \epsilon^2) \\ &= 2 \lvert \mathcal{F} \rvert \exp(-2n \epsilon^2) \end{align}

Rewriting in terms of $$\delta$$, that is taking $$\delta := 2 \lvert \mathcal{F} \rvert \exp(-2n \epsilon^2)$$ and rearranging for $$\epsilon$$ to get

$$\epsilon = \sqrt{\frac{\ln \lvert \mathcal{F} \rvert + \ln (2 / \delta)}{2n}}$$

Yields

$$\mathbb{P} \left( \sup_{f \in \mathcal{F}} \lvert \hat{R}_n(f) - R(f) \rvert \leq \sqrt{\frac{\ln \lvert \mathcal{F} \rvert + \ln (2 / \delta)}{2n}} \right) \geq 1 - \delta$$

Up to here, I am comfortable with the proof steps - and I read the above line as, "the probability that the maximum deviation between the empirical risk and risk over the entire function class $$\mathcal{F}$$ lies in $$[-C_{\delta}, C_{\delta}]$$ is at least $$1 - \delta$$.

My confusion.

However, where it gets unfamiliar is that the authors state that this proves $$(4.3)$$, but I am having difficulty trying to figure out whether this means that

\begin{align} &\mathbb{P} \left( \sup_{f \in \mathcal{F}} \lvert \hat{R}_n(f) - R(f) \rvert \leq \sqrt{\frac{\ln \lvert \mathcal{F} \rvert + \ln (2 / \delta)}{2n}} \right) \geq 1 - \delta \\ & \implies \mathbb{P} \left( \forall f \in \mathcal{F} \lvert \hat{R}_n(f) - R(f) \rvert \leq \sqrt{\frac{\ln \lvert \mathcal{F} \rvert + \ln (2 / \delta)}{2n}}\right) \geq 1 - \delta \end{align}

or whether it means that

\begin{align} &\mathbb{P} \left( \sup_{f \in \mathcal{F}} \lvert \hat{R}_n(f) - R(f) \rvert \leq \sqrt{\frac{\ln \lvert \mathcal{F} \rvert + \ln (2 / \delta)}{2n}} \right) \geq 1 - \delta \\ & \implies \forall f \in \mathcal{F} , \mathbb{P} \left( \lvert \hat{R}_n(f) - R(f) \rvert \leq \sqrt{\frac{\ln \lvert \mathcal{F} \rvert + \ln (2 / \delta)}{2n}}\right) \geq 1 - \delta \\ \end{align}

The statement the authors intended is (A) for the following reasons.

Much of your reluctance to consider $$(A)$$ as the correct statement amounted to insufficient attentiveness concerning the following basic distinction between:

$$\mathbb{P} \left( \sup_{f \in \mathcal{F}} \lvert \hat{R}_n(f) - R(f) \rvert \geq \epsilon \right) = \mathbb{P} \left( \bigcup_{f \in \mathcal{F}} \{\lvert \hat{R}_n(f) - R(f) \rvert \geq \epsilon \} \right)$$

and

\begin{align} \mathbb{P} \left( \sup_{f \in \mathcal{F}} \lvert \hat{R}_n(f) - R(f) \rvert \leq \epsilon \right) &= \mathbb{P} \left( \bigcap_{f \in \mathcal{F}} \{ \lvert \hat{R}_n(f) - R(f) \rvert \leq \epsilon \} \right) \\ &= \mathbb{P} \left( \forall f \in \mathcal{F}, \space \lvert \hat{R}_n(f) - R(f) \rvert \leq \epsilon \right) \end{align}

Consider the events within each statement.

• In the first statement, the event that the "maximum absolute deviation between the empirical risk and the risk over the function class $$\mathcal{F}$$ exceeds $$\epsilon$$" is the same as the compound event that "there is at least one function $$f$$ whose absolute deviation between the empirical risk and risk exceeds $$\epsilon$$".
• In the second statement, the event that the "maximum absolute deviation between the empirical risk and the risk over the function class $$\mathcal{F}$$ does not exceed $$\epsilon$$" is the same as the compound event that the "absolute deviation between the empirical risk and the risk does not exceed $$\epsilon$$ for all functions $$f \in \mathcal{F}$$.

Difference between statements $$(A)$$ and $$(B)$$.

The reason why the statement the authors intended is not statement $$(B)$$ goes back to the argument about the insufficiency of concentration inequalities for understanding generalisation error, and why we are instead interested in bounding uniform deviations. Statement $$(B)$$ is of the same flavour as a concentration inequality applied to every $$f \in \mathcal{F}$$, except it is much looser than the one derived using Hoeffding in step 1, due to the inclusion of the $$\ln \lvert \mathcal{F} \rvert$$ term:

$$\space \mathbb{P} \left( \lvert \hat{R}_n(f) - R(f) \rvert \leq \sqrt{\frac{\ln \lvert \mathcal{F} \rvert + \ln (2 / \delta)}{2n}} \right) \geq 1 - \delta, \quad \forall f \in \mathcal{F}$$

• Setting the looseness of the bound aside, this is qualitatively distinct from statement $$(A)$$.
• Statement $$(B)$$ is saying that for every single function $$f \in \mathcal{F}$$, there exists a set of training samples associated with that function $$f$$, which we define as $$S_f$$, such that $$\hat{R}_n(f) - R(f) \leq \sqrt{\frac{\ln \lvert \mathcal{F} \rvert + \ln (2 / \delta)}{2n}}$$, and that the probability of encountering this sample exceeds $$1 - \delta$$, that is, $$P(S_f) \geq 1 - \delta$$.
• Even though for all $$f \in \mathcal{F}$$, the probability $$P(S_f) \geq 1 -\delta$$, this does not change the fact that in general, each training sample $$S_f$$ for which $$\hat{R}_n(f) - R(f) \leq \sqrt{\frac{\ln \lvert \mathcal{F} \rvert + \ln (2 / \delta)}{2n}}$$ holds is different for different functions $$f \in \mathcal{F}$$. Hence what is required is something stronger than this.
• What instead is required is the probability of a set of training samples $$S$$ for which every absolute deviation $$\lvert \hat{R}_n(f) - R(f) \rvert \leq \sqrt{\frac{\ln \lvert \mathcal{F} \rvert + \ln (2 / \delta)}{2n}}$$. Only statement $$(A)$$ captures this sense.

Key take away: The position of the qualifier $$\forall f \in \mathcal{F}$$ is of the utmost importance.

Illustrations.

To see this graphically, statement $$(B)$$ is a statement concerning a pointwise deviation for every function $$f \in \mathcal{F}$$. That is, it only bounds the vertical distances in the graph below as individual events.

Statement $$(A)$$ is a uniform bound across the entire function class. That is, it bounds the probability of the compound event that the entire blue curve lies within the "white river", and does not cross over onto the "grey river bank".

Other sources.

Statements equivalent to $$(A)$$, though not written explicitly as probability statements, and with some mild idiosyncratic differences in notation, can be found in:

• Anthony, M., & Bartlett, P. (1999). Neural Network Learning: Theoretical Foundations. Cambridge: Cambridge University Press. p22 doi:10.1017/CBO9780511624216
• Bousquet O., Boucheron S., Lugosi G. (2004) Introduction to Statistical Learning Theory. In: Bousquet O., von Luxburg U., Rätsch G. (eds) Advanced Lectures on Machine Learning. ML 2003. Lecture Notes in Computer Science, vol 3176. Springer, Berlin, Heidelberg. p179 https://doi.org/10.1007/978-3-540-28650-9_8