<p>I follow the proof of the Dudley chaining/metric entropy bound of the (empirical) Rademacher complexity, but I don't have any intuition for why this bound should be true. In particular, I don't know why anyone would think to make this argument. Can someone please explain why? (An example of the chaining argument: <a href="http://www.cs.cornell.edu/~sridharan/dudley.pdf" rel="nofollow noreferrer">http://www.cs.cornell.edu/~sridharan/dudley.pdf</a>.)</p>

<p>For context:</p>

<p>The following covering number bound makes some sense to me:
<span class="math-container">$$
  \texttt{Rad}(\mathcal{A} \circ x) \leq \inf_{\epsilon &gt; 0} \{ \epsilon + \text{const} \times \sqrt{\log \texttt{CoveringNumber}(\mathcal{A}, ||\cdot{}||_{1, x}, \epsilon)} \}
$$</span>
where <span class="math-container">$x = x_1, \dots, x_n$</span> and <span class="math-container">$||a||_{1, x} = \left(\frac 1n \sum_{i=1}^n |a(x_i)|^p \right)^{1/p}$</span> for <span class="math-container">$a \in \mathcal{A}$</span> and <span class="math-container">$\mathcal{A}$</span> is a set of algorithms/hypotheses. I think of the right hand side as counting equivalence classes of <span class="math-container">$\mathcal{A}$</span> under "predictions on <span class="math-container">$\mathcal{X}$</span> are <span class="math-container">$\epsilon$</span>-close in <span class="math-container">$||\cdot{}||_{1, x}$</span>". Intuitively, the more of these there are, the more "different" predictions <span class="math-container">$\mathcal{A}$</span> can express on the training set <span class="math-container">$x$</span> and hence <span class="math-container">$\mathcal{A}$</span> is more "complex".</p>

CC BY-SA 4.0
2020-02-17T14:15:23.960Z
The crudest possible way to quantify the complexity of a function class is to count how many members it has. A more refined idea (really, a brilliant flash of insight) is to realize that actually what matters is the number of behaviors that the function class attains on a given sample. The next stage is to chunk the behaviors into closely related clusters -- hence the idea of covering numbers.
Aryeh
CC BY-SA 4.0
2020-02-18T09:37:16.097Z
I see the question being upvoted, and yet I struggle to imagine what a satisfactory answer might look like. My comment above contains some standard intuitions on the matter, and it really doesn't seem like you're likely to get much more than that. I'd love to be proven wrong, though...
Aryeh
CC BY-SA 4.0
2020-02-18T13:41:46.947Z
Is the question mostly about **chaining**? For that I like to picture bounding a $1$-d Brownian motion. You could first bound it at all points in an $\epsilon$-net and union-bound over them. But what about the other infinitely many points? Well, you could next show that points within $\epsilon/2$ cannot be too much higher than their neighbors. This is one level of chaining and implies a bound for an $\epsilon/2$-net. You can picture why this would give better bounds than union-bounding over the $\epsilon/2$-net directly. Then you could "chain" this argument down to arbitrarily small scales.
usul
CC BY-SA 4.0
2020-02-18T14:05:08.193Z
Thanks for your comment. Yes the question is exactly about chaining. It is intuitive that covering prediction space should give a bound on complexity, but not so clear to me that a better bound can be obtained by integrating over different granularities of covers.
user27182
CC BY-SA 4.0
2020-02-18T14:06:18.210Z
(Didn’t mean time press send) my intuition currently is that we decompose the predictor into members of increasing finer covers. So we decompose the predictor into increasingly more complex or accurate representatives, then bound each of these representations.
user27182
CC BY-SA 4.0
2020-02-21T16:22:13.300Z
@user27182, I'm wondering if my Brownian motion example is helpful.
usul
CC BY-SA 4.0
2020-02-21T16:45:57.920Z
@usul Yes it does help, thank you. Is there any reason why we might use the analogy of brownian motion for $\mathcal{A}\circ x$?
user27182
<machine-learning><lg.learning><sample-complexity>
Understanding Dudley Chaining Argument for Rademacher Bound
user27182
# Understanding Dudley Chaining Argument for Rademacher Bound

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

I follow the proof of the Dudley chaining/metric entropy bound of the (empirical) Rademacher complexity, but I don't have any intuition for why this bound should be true. In particular, I don't know why anyone would think to make this argument. Can someone please explain why? (An example of the chaining argument: <http://www.cs.cornell.edu/~sridharan/dudley.pdf>.)

For context:

The following covering number bound makes some sense to me:
$$
\texttt{Rad}(\mathcal{A} \circ x) \leq \inf\_{\epsilon > 0} \{ \epsilon + \text{const} \times \sqrt{\log \texttt{CoveringNumber}(\mathcal{A}, ||\cdot{}||\_{1, x}, \epsilon)} \}
$$
where $x = x\_1, \dots, x\_n$ and $||a||\_{1, x} = \left(\frac 1n \sum\_{i=1}^n |a(x\_i)|^p \right)^{1/p}$ for $a \in \mathcal{A}$ and $\mathcal{A}$ is a set of algorithms/hypotheses. I think of the right hand side as counting equivalence classes of $\mathcal{A}$ under "predictions on $\mathcal{X}$ are $\epsilon$-close in $||\cdot{}||\_{1, x}$". Intuitively, the more of these there are, the more "different" predictions $\mathcal{A}$ can express on the training set $x$ and hence $\mathcal{A}$ is more "complex".

**Tags:** machine-learning, lg.learning, sample-complexity
> **Comments:**
> **username_1**: The crudest possible way to quantify the complexity of a function class is to count how many members it has. A more refined idea (really, a brilliant flash of insight) is to realize that actually what matters is the number of behaviors that the function class attains on a given sample. The next stage is to chunk the behaviors into closely related clusters -- hence the idea of covering numbers.  
> **username_1**: I see the question being upvoted, and yet I struggle to imagine what a satisfactory answer might look like. My comment above contains some standard intuitions on the matter, and it really doesn't seem like you're likely to get much more than that. I'd love to be proven wrong, though...  
> **username_2**: Is the question mostly about **chaining**? For that I like to picture bounding a $1$-d Brownian motion. You could first bound it at all points in an $\epsilon$-net and union-bound over them. But what about the other infinitely many points? Well, you could next show that points within $\epsilon/2$ cannot be too much higher than their neighbors. This is one level of chaining and implies a bound for an $\epsilon/2$-net. You can picture why this would give better bounds than union-bounding over the $\epsilon/2$-net directly. Then you could "chain" this argument down to arbitrarily small scales.  
> **username_0**: Thanks for your comment. Yes the question is exactly about chaining. It is intuitive that covering prediction space should give a bound on complexity, but not so clear to me that a better bound can be obtained by integrating over different granularities of covers.  
> **username_0**: (Didn’t mean time press send) my intuition currently is that we decompose the predictor into members of increasing finer covers. So we decompose the predictor into increasingly more complex or accurate representatives, then bound each of these representations.  
> **username_2**: @user27182, I'm wondering if my Brownian motion example is helpful.  
> **username_0**: @usul Yes it does help, thank you. Is there any reason why we might use the analogy of brownian motion for $\mathcal{A}\circ x$?  

---

## 0 answers

