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".

  • 1
    $\begingroup$ 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. $\endgroup$
    – Aryeh
    Feb 17 '20 at 14:15
  • $\begingroup$ 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... $\endgroup$
    – Aryeh
    Feb 18 '20 at 9:37
  • 1
    $\begingroup$ 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. $\endgroup$
    – usul
    Feb 18 '20 at 13:41
  • $\begingroup$ 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. $\endgroup$
    – user27182
    Feb 18 '20 at 14:05
  • $\begingroup$ (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. $\endgroup$
    – user27182
    Feb 18 '20 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.