math.STFeb 21, 2025

Do we really need the Rademacher complexities?

Authors: Daniel Bartl, Shahar Mendelson

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

Explore similar work

CardsList
  1. The Sharp Tail of Uniform Stability

    Aug 25, 2026Pahan DewasurendraAlgorithmic StabilityGeneralization Bounds

  2. Even Sharper Bounds for Transductive Learning and Its Applications

    Sep 23, 2026Yingzhen YangTransductive LearningStatistical Learning Theory

  3. Uniform convergence at optimal rate and scale

    Oct 17, 2026Noga Alon, Steve Hanneke, Shay Moran +1Generalization Bounds