This question is somewhat related to this one. There are many results in statistics where convergence rates (including minimax ones) are given in terms of the smoothness properties of the underlying function class: Lipschitz, Hölder, etc. The problem with these is that they're quite pessimistic: a function with a high oscillation on a tiny region of the space is penalized the same as a function with high oscillation everywhere. Are there generalization bounds that take into account average-case smoothness? The one classic example is functions of bounded variation at most $V$ on $[0,1]$, whose $\gamma$-shattering dimension is $1+\lfloor\frac{V}{2\gamma}\rfloor$ (see the Anthony-Bartlett book). For differentiable $f:[0,1]\to\mathbb{R}$, the bounded variation is given by $\int_0^1|f'(x)|dx$, and thus corresponds to an average measure of smoothness.

Can anyone point me to other results along these lines for more general spaces?


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.