[2502.15118] Do we really need the Rademacher complexities?

View a PDF of the paper titled Do we really need the Rademacher complexities?, by Daniel Bartl and Shahar Mendelson

View PDF
HTML (experimental)

Abstract:We study the fundamental problem of learning with respect to the squared loss in a convex class. In the subgaussian setting, the sharpest known sample complexity bounds are characterised via fixed points associated with the limiting gaussian process. In more general settings (for example, heavier-tailed scenarios) the state-of-the-art bounds rely on localised Rademacher complexities, which are often difficult to control and can be considerably larger than their limiting gaussian counterparts.

We show that if one has access to coarse information on the covariance structure of the underlying class, it is possible to derive an upper bound on the sample complexity that matches the state-of-the-art rates in the gaussian setting—even in heavy-tailed regimes. As a consequence, under rather minimal assumptions, learning problems that share the same $L_2$-structure—even those involving heavy-tailed distributions—admit the same upper bound on the sample complexity as if the problem were fully gaussian. This constitutes the first universality result for general convex learning problems.

The proof is based on a novel learning procedure, and its performance is studied by combining optimal mean estimation techniques for real-valued random variables with Talagrand’s generic chaining method.