# 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

• 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