`local' vs. `global' parameters -- breaking the gaussian complexity barrier
This provides a theoretical breakthrough for statistical learning theory by breaking the Gaussian complexity barrier in convex function classes.
The paper tackles the problem of error rates in learning problems with independent noise by showing they are equivalent to fixed points determined by local covering estimates rather than Gaussian averages. The result establishes new sharp upper and lower estimates on these error rates.
We show that if $F$ is a convex class of functions that is $L$-subgaussian, the error rate of learning problems generated by independent noise is equivalent to a fixed point determined by `local' covering estimates of the class, rather than by the gaussian averages. To that end, we establish new sharp upper and lower estimates on the error rate for such problems.