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

Aug 25, 2026

The Sharp Tail of Uniform Stability

Uniform stability controls how much one training example can change the loss at any test point. A new logarithmic-free upper bound shows that a γγ-uniformly stable algorithm with loss in [0,L][0,L] has generalization gap at most O(γlog⁡(1/δ)+Llog⁡(1/δ)n)O \left(γ\log(1/δ) +L\sqrt{\frac{\log(1/δ)}{n}}\right) with probability 1−δ1-δ. Whether an actual bounded-loss learning algorithm can realize the linear dependence on log⁡(1/δ)\log(1/δ) has remained open. The known construction realizes it only for auxiliary weakly dependent random variables whose pointwise range grows with nn. The known learning lower bound holds only at constant probability. We close this gap. For every nn, stability level γγ, and loss bound LL, we construct one deterministic γγ-uniformly stable learning problem whose tail satisfies, simultaneously for 1≤p≤cn1\le p\le c n, P(R(AS)−RS(AS)≥c′min⁡{L,γp+Lp/n})≥e−p.\mathbb P \left( R(A_S)-R_S(A_S) \ge c'\min \left\{L,γp+L\sqrt{p/n}\right\} \right)\ge e^{-p}. The construction is ordinary bounded absolute-loss regression with constant labels. Its key is a multiscale collection of rare Rademacher features. A coordinatewise ramp is stable in sup norm, while an odd symmetrized maximum converts a unique extreme feature into a gap of order γpγp without violating the loss bound. Geometrically spaced ramps put all confidence levels into the same problem. Together with the logarithmic-free upper bound, this determines the optimal high-probability and moment dependence of uniform stability up to universal constants.
Sep 23, 2026

Even Sharper Bounds for Transductive Learning and Its Applications

We introduce Sharper Transductive Local Complexity (STLC), a localized complexity method for transductive learning under uniform sampling without replacement. The construction starts from a Bernstein-type concentration inequality for the supremum of the test--train empirical process. Its proof uses the modified log-Sobolev inequality for the swap walk and a two-parameter entropy closure. A peeling argument with a surrogate localization functional then gives excess-risk bounds with the same fixed-point and confidence terms as the classical inductive local Rademacher-complexity bounds, without the additional logarithmic confidence factor in earlier transductive results. For realizable learning over a binary class of VC dimension \dVC\dVC, with training size mm, test size uu, and u≥m≥\dVCu\ge m\ge\dVC, STLC yields \cO{\dVClog⁡(me/\dVC)/m}\cO\{\dVC\log(me/\dVC)/m\}. This matches the standard inductive rate and, when m≥9m\ge9, is within a logarithmic factor of the transductive minimax lower bound of order \dVC/m\dVC/m. For transductive kernel learning, STLC gives a spectrum-adaptive excess-risk bound without the multiplicative imbalance factors appearing in the earlier local-complexity bound.
Oct 17, 2026

Uniform convergence at optimal rate and scale

Uniform convergence asks how many random samples suffice for empirical averages to approximate expectations simultaneously over an entire class of functions. It is a central concept in probability and a foundation of statistical learning. For binary-valued classes, the Vapnik--Chervonenkis theorem characterizes uniform convergence by finiteness of the VC dimension. For dimension dd, the sharp worst-case sample complexity for additive error ε\varepsilon is of order d/ε2d/\varepsilon^2. For real-valued functions, the analogous combinatorial parameter is the fat-shattering dimension, which depends on an approximation scale γγ. The challenge is to achieve error γ+εγ+\varepsilon with order d/ε2d/\varepsilon^2 samples, matching the sample bound for binary classes, where dd is now the fat-shattering dimension at scale γγ. Previous results achieved either the optimal scale or the optimal sample complexity, but not both. Our main result closes this gap, establishing the sharp sample complexity at the optimal scale. Along the way, we use several tools that may be of independent interest. The first concerns ε\varepsilon-nets with margin. A classical ε\varepsilon-net intersects every set of mass at least ε\varepsilon in a prescribed family; we allow the net to intersect a slightly enlarged version of each such set. Remarkably, this relaxation permits bounds independent of the ambient dimension in natural geometric settings. Second, we derive improved covering bounds in both discrete and real-valued settings: we extend Haussler's covering lemma to partial concept classes and use this extension to obtain ℓ2\ell_2 covers at the optimal scale for real-valued function classes. Third, we obtain a chaining bound at the optimal scale by aligning the covers so that successive approximations become increasingly close to one another.