<p>This was proven in</p>

<blockquote>
  <p>M. Talagrand. <em>Sharper bounds for Gaussian and empirical processes.</em> The Annals of Probability, pages 28–76, 1994.</p>
</blockquote>

<p>This is mentioned in e.g. <a href="https://arxiv.org/abs/1607.00932" rel="noreferrer">this paper (Section 1.1.2)</a>, which does a pretty good job (in my opinion) of summarizing the landscape.</p>

CC BY-SA 3.0
2018-02-18T05:43:54.320Z
Fantastic, thanks! I have some reading to do, including chasing some references.
Thomas Steinke
CC BY-SA 3.0
2018-02-18T07:57:20.013Z
So it seems that the key to the improvement is a generalization of Sauer's lemma by [Haussler](https://pdfs.semanticscholar.org/da08/19e556c860aa43496944f6592bfca0024759.pdf). 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 Steinke
CC BY-SA 3.0
2018-02-18T11:00:11.173Z
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: https://www.cs.bgu.ac.il/~asml162/Class_Material
Aryeh
CC BY-SA 3.0
2018-02-18T18:07:40.323Z
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 Steinke
CC BY-SA 3.0
2018-02-18T03:46:21.193Z
2018-02-18T05:37:50.020Z
2018-02-18T05:37:50.020Z
Clement C.
<p>The following result is <a href="http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf#page=72" rel="noreferrer">supposedly known</a>. 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?</p>

<blockquote>
  <p><strong>Theorem.</strong> Let $\mathcal{H}$ be a class of functions $h : \mathcal{X} \to \{-1,+1\}$ with <a href="https://en.wikipedia.org/wiki/VC_dimension" rel="noreferrer">VC dimension</a> $d&lt;\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&gt;0$.</p>
  
  <p>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.$$</p>
</blockquote>

<hr>

<p>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$.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma" rel="noreferrer">Perles-Sauer-Shelah lemma</a> 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.</p>

<p>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!</p>

CC BY-SA 3.0
2018-02-18T05:48:30.263Z
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
CC BY-SA 3.0
2018-02-18T05:49:20.170Z
@gradstudent Chapter 28 proves the weaker version.
Thomas Steinke
CC BY-SA 3.0
2018-02-18T05:56:12.990Z
Can you specify which theorem of Chapter 28 you are referring to?
gradstudent
CC BY-SA 3.0
2018-02-18T06:02:25.847Z
@gradstudent This is in section 28.1 -- there is no theorem statement, but what they show is eq. (28.1).
Thomas Steinke
CC BY-SA 3.0
2018-02-18T06:09:10.487Z
Whats confusing me is that Theorem 6.8 as stated on page 73 seems to give the tight bounds already as you want.
gradstudent
CC BY-SA 3.0
2018-02-18T06:48:25.893Z
@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 Steinke
<reference-request><lg.learning><vc-dimension>
Tight VC bound for agnostic learning
Thomas Steinke
# Tight VC bound for agnostic learning

(Asked by: username_0 on 2018-02-17)

The following result is [supposedly known](http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf#page=72). 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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Sauer%E2%80%93Shelah_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!

**Tags:** reference-request, lg.learning, vc-dimension
> **Comments:**
> **username_1**: 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?  
> **username_0**: @gradstudent Chapter 28 proves the weaker version.  
> **username_1**: Can you specify which theorem of Chapter 28 you are referring to?  
> **username_0**: @gradstudent This is in section 28.1 -- there is no theorem statement, but what they show is eq. (28.1).  
> **username_1**: Whats confusing me is that Theorem 6.8 as stated on page 73 seems to give the tight bounds already as you want.  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_2 on 2018-02-18. Score: 6 | Accepted 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)](https://arxiv.org/abs/1607.00932), which does a pretty good job (in my opinion) of summarizing the landscape.

> **Comments:**
> **username_0**: Fantastic, thanks! I have some reading to do, including chasing some references.  
> **username_0**: So it seems that the key to the improvement is a generalization of Sauer's lemma by [Haussler](https://pdfs.semanticscholar.org/da08/19e556c860aa43496944f6592bfca0024759.pdf). 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.  
> **username_3**: 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: https://www.cs.bgu.ac.il/~asml162/Class_Material  
> **username_0**: 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$.  

---

