# Tight VC bound for agnostic learning

The following result is supposedly known. However, the proofs I am able to find all prove a weaker result with an extra log factor. Where can I find the proof of the tight bound?

Theorem. Let $\mathcal{H}$ be a class of functions $h : \mathcal{X} \to \{-1,+1\}$ with VC dimension $d<\infty$. Let $\mathcal{D}$ be a distribution on $\mathcal{X} \times \{-1,1\}$ and let $(X_1,Y_1), \cdots, (X_n,Y_n)$ be independent samples from $\mathcal{D}$. Let $\varepsilon,\delta>0$.

If $n \geq O\left(\frac{d+\log(1/\delta)}{\varepsilon^2}\right)$, then $$\mathbb{P}\left[\forall h \in \mathcal{H} ~~\left|\frac{1}{n} \sum_{i=1}^n h(X_i) \cdot Y_i - \underset{(X_*,Y_*) \leftarrow \mathcal{D}}{\mathbb{E}}[h(X_*) \cdot Y_*]\right|\le\varepsilon\right] \ge 1-\delta.$$

The (well-known) connection to agnostic learning is as follows. $\mathcal{H}$ is a class of "hypotheses" and $\mathcal{D}$ is some unknown ground truth distribution on attributes $X \in \mathcal{X}$ and labels $Y \in \{-1,+1\}$. You see $n$ samples from $\mathcal{D}$ and want to be sure that any hypothesis that labels the sample well (i.e. $\frac{1}{n} \sum_{i=1}^n h(X_i) \cdot Y_i$ is large) also labels the ground truth well (i.e. $\underset{(X_*,Y_*) \leftarrow \mathcal{D}}{\mathbb{E}}[h(X_*) \cdot Y_*]$ is also large). The above theorem says that if $n \geq O\left(\frac{\mathsf{VCdim}(\mathcal{H})+\log(1/\delta)}{\varepsilon^2}\right)$ then with probability $\ge 1-\delta$, for all hypotheses the error on the sample and the error on the distribution are within $\varepsilon$.

The proofs that I can find relating VC dimension to uniform convergence all include an extra log factor. That is, they prove a bound of $n \geq O\left(\frac{\mathsf{VCdim}(\mathcal{H}) \cdot \log(\mathsf{VCdim}(\mathcal{H})/\varepsilon)+\log(1/\delta)}{\varepsilon^2}\right)$. This is achieved by applying the Perles-Sauer-Shelah lemma and a clever union bound. For the simple case where $\mathsf{VCdim}(\mathcal{H})=\log|\mathcal{H}|$, this just follows from Hoeffding's inequality and a union bound.

Unfortunately, I haven't been able to find a proof of the tight and general result, despite looking for several hours. Surely someone can point me to the right source!

• Isn't Chapter 28 of the book you have linked to proving this theorem as you state? Where is this weaker theorem proved as you say? – gradstudent Feb 18 '18 at 5:48
• @gradstudent Chapter 28 proves the weaker version. – Thomas Feb 18 '18 at 5:49
• Can you specify which theorem of Chapter 28 you are referring to? – gradstudent Feb 18 '18 at 5:56
• @gradstudent This is in section 28.1 -- there is no theorem statement, but what they show is eq. (28.1). – Thomas Feb 18 '18 at 6:02
• @gradstudent yes, the statement is what I want, but the proof is not. If you read the fist few lines of section 28.1, it is clear that they prove something weaker than they state. – Thomas Feb 18 '18 at 6:48

## 1 Answer

This was proven in

M. Talagrand. Sharper bounds for Gaussian and empirical processes. The Annals of Probability, pages 28–76, 1994.

This is mentioned in e.g. this paper (Section 1.1.2), which does a pretty good job (in my opinion) of summarizing the landscape.

• Fantastic, thanks! I have some reading to do, including chasing some references. – Thomas Feb 18 '18 at 5:43
• So it seems that the key to the improvement is a generalization of Sauer's lemma by Haussler. Namely, rather than just bounding the cardinality of the hypothesis class, he bounds the covering number. This extra geometric information is enough to improve the bound via chaining. – Thomas Feb 18 '18 at 7:57
• You can get asymptotically optimal (up to constants) agnostic PAC bounds without the full power of Haussler's result. Older results of Dudley and Pollard suffice. See my lecture notes here: cs.bgu.ac.il/~asml162/Class_Material – Aryeh Feb 18 '18 at 11:00
• Thanks, @Aryeh ! That is considerably simpler. Indeed, we just need the covering number to be $(1/\varepsilon)^{O(d)}$, rather than Haussler's $O(1/\varepsilon)^d$. – Thomas Feb 18 '18 at 18:07