Source-linked AI summary
Learning without Concentration
Shahar Mendelson
TL;DR
The paper studies Empirical Risk Minimization in convex classes under squared loss, where boundedness and concentration-based proof techniques may be unavailable. It develops a lower-bound-based analysis that yields sharp L2 estimation guarantees, including when two-sided concentration is impossible.
Problem
The paper studies the error of Empirical Risk Minimization in a convex class relative to squared loss, including settings where functions and targets need not be bounded.
Method
The analysis replaces reliance on two-sided concentration with a lower bound on empirical loss over functions sufficiently far from the target.
Results
ERM produces a function close in L2(µ) to the best approximation of the target in F, with a sharp estimation guarantee even when two-sided concentration is impossible.
Takeaways & Limitations
The resulting approach extends sharp ERM analysis beyond uniformly bounded classes and bounded targets to settings where concentration-based proofs cannot realistically be extended.
Takeaways & Limitations
The earlier concentration-and-contraction proof applies only to uniformly bounded classes and bounded targets, limiting its extension without a new argument.
Abstract
from arXiv · showhide
We obtain sharp bounds on the performance of Empirical Risk Minimization performed in a convex class and with respect to the squared loss, without assuming that class members and the target are bounded functions or have rapidly decaying tails. Rather than resorting to a concentration-based argument, the method used here relies on a `small-ball' assumption and thus holds for classes consisting of heavy-tailed functions and for heavy-tailed targets. The resulting estimates scale correctly with the `noise level' of the problem, and when applied to the classical, bounded scenario, always improve the known bounds.
1 Introduction
The paper studies how accurately ERM estimates the best function in a convex class under squared loss when data are random, including settings where boundedness and light tails fail. It develops sharper estimates that address heavy-tailed functions and targets, reflect the noise level, and improve classical bounded-case bounds.
- Problem: The estimation problem is to approximate the L2-best function f ∗ in a class F using an independent random sample (Xi, Yi)N_i=1.The target is measured through squared loss, whose average cost is E(f(X) −Y )2 = ∥f(X) −Y ∥2_L2.
- Method: ERM selects an empirical minimizer ˆf by minimizing empirical squared loss over the class.The empirical mean is taken with respect to the given sample.
- Existing bounds: The classical high-probability ERM result assumes a closed, convex class and target whose functions are bounded by 1.Its proof relies on contraction and concentration arguments for uniformly bounded functions and a bounded target.
- Limitations: These boundedness assumptions exclude heavy-tailed targets, heavy-tailed function classes, Gaussian-noise problems, and many general regression settings.Gaussian noise is unbounded, and linear functionals under Gaussian measures are unbounded as well.
- Motivation: The paper seeks estimation bounds that remain sharp without boundedness, unlike the classical theorem whose error can scale incorrectly with R and σ.In the bounded linear-functional example, the classical estimate is described as far from optimal and incorrectly scaled in both parameters.
2 Towards a heavy-tailed framework
The paper develops a framework for learning when heavy-tailed functions or targets make two-sided concentration unavailable. It replaces concentration with lower-bound arguments and complexity parameters that capture version-space size and target–class interaction.
- Bypassing concentration: Heavy-tailed settings can invalidate two-sided concentration, because rare large observations may destroy upper estimates even when lower empirical bounds remain possible.A single large value can increase the empirical quadratic mean, while lower bounds are not harmed; consequently, standard two-sided concentration analysis cannot handle heavy-tailed learning problems.
- Bypassing concentration: A lower bound on the empirical quadratic process, rather than a two-sided estimate, can yield sharp L2 error bounds when two-sided concentration is impossible.The paper emphasizes that the relevant lower bound supports estimation of the ERM error even without two-sided concentration.
- Low-noise regime: The low-noise regime is governed by a parameter measuring localized complexity and controlling the size and stability of the version space.This parameter depends on the class rather than the exact noise and implies that distant functions cannot remain in the version space, while empirical distances preserve a fixed proportion of L2 distances.
- High-noise regime: The high-noise regime is governed by a parameter measuring interaction between target noise and localized class members through a multiplier process.The process measures maximal correlation with the symmetrized noise vector; unlike the noise-insensitive bounded-case complexity, it is favorably smaller when the target is close to the class.
- Comparison with bounded analysis: In bounded problems, the noise-interaction parameter is dominated by the classical complexity, while the latter loses dependence on noise through contraction.The paper contrasts a bounded-case parameter that is insensitive to noise with one that can improve as the noise level decreases.
3 The main result
The main result bounds ERM through two complementary conditions: version-space complexity and noise interaction, using a one-sided quadratic lower bound enabled by a small-ball assumption. The resulting framework applies broadly, including heavy-tailed classes and targets, and identifies distinct low- and high-noise regimes.
- The main result: ERM achieves an L2(µ) error bound once empirical excess loss is positive outside a radius around the best approximation f ∗.An empirical minimizer cannot lie in the region where the empirical excess loss is positive.
- The main result: The error radius is controlled by the larger of α∗N(γ2, δ) and β∗N(γ1), corresponding respectively to noise interaction and version-space complexity.The two conditions are imposed beyond their respective thresholds, and the combined event yields positivity of empirical excess loss.
- The assumption on the class: The quadratic lower bound requires only a weak small-ball condition on F−F, which can hold with absolute constants in many examples.The assumption requires QF−F(u) > 0; the paper states that this condition is minimal in several generic settings.
- The assumption on the class: Small-ball reasoning replaces concentration by ensuring that many independent evaluations of each function have magnitude proportional to its L2 norm.Under moment equivalence, a binomial estimate gives a high-probability lower bound on the empirical quadratic term.
- Theorem 3.1: Theorem 3.1 imposes essentially no restrictions on the class or target beyond the small-ball condition and applies to settings excluded by the earlier theorem.The paper explicitly includes heavy-tailed functions and targets among the settings enabled by the result.
- Applications: In persistence with bounded coordinates and bounded symmetric noise, Theorem 3.1 yields an estimate that is optimal in the minimax sense.The example allows dimension, radius, and noise level to grow with sample size while targeting consistency conditions.
- Optimality: A general optimality proof is deferred because the non-subgaussian setting lacks the machinery used in the available sketchy argument.The article only sketches optimality facts for a wide variety of classes.
- Optimality: The low-noise parameter controls version-space diameter, while the high-noise parameter captures interaction between the target residual and the class.The paper gives optimality indications for both regimes under additional subgaussian regularity assumptions, but defers the general proof.
4 Some Examples
The examples show that small-ball conditions can support ERM guarantees for heavy-tailed classes and targets, including linear prediction, while improving bounded-case estimates through correct dependence on radius and noise.
- Small-ball conditions: Moment comparisons imply a uniform small-ball condition for differences in F, with constants depending only on the comparison parameters.Both L2–L1 and Lp–L2 conditions yield a lower bound on Q_F−F at a fixed scale.
- Linear classes: For independent-coordinate linear classes, either stated moment condition yields ERM guarantees with constants depending only on the corresponding moment parameters.The result applies when the coordinates are distributed as ζ and the parameter set is closed and convex.
- Heavy-tailed settings: The small-ball method applies beyond bounded or rapidly decaying settings, where the classical bounded theorem is inapplicable.The excluded problems include classes or targets that are unbounded or heavy-tailed.
- Noise-sensitive bounds: Theorem 4.6 measures noise through σ = ∥W∥L2,1 and gives an error bound controlled by max{v1, v2}.The cited discussion states that v1 captures the version-space diameter, v2 captures interaction with noise, and the rate is minimax optimal up to probability estimates.
- Extensions: Theorem 4.6 extends to general targets, relaxed coordinate assumptions, and heavy-tailed measures, although the more general proof has high technical cost.The extension is stated as available through related results rather than developed fully here.
5 Proof of Theorem 3.1
The proof of Theorem 3.1 converts a uniform small-ball estimate into a lower bound on empirical excess loss outside a critical radius, using convexity to obtain star-shaped structure.
- Critical radius: For radii exceeding β_N(H, τQ_H(2τ)/16), the proof establishes a high-probability empirical lower bound for every f with ∥f − f*∥L2 at least that radius.The probability is at least 1 − 2 exp(−NQ_H(2τ)^2/2).
- Small-ball estimate: The proof centers on a uniform empirical small-ball estimate for a class on the L2 sphere.The estimate is the first major step toward controlling empirical behavior without two-sided concentration.
- Proof ingredients: The empirical small-ball process is controlled by truncation, bounded differences, symmetrization, and contraction for the Lipschitz truncation function.These tools provide uniform control of empirical threshold counts or truncated magnitudes.
- Star-shaped reduction: A convex class produces a star-shaped difference class H = F − f*, allowing radial rescaling of functions toward the origin.This follows because convex combinations of f and f* remain in F.
- Excess loss: The argument uses the excess-loss identity and the projection property of f* to show nonnegative expected linear error against f − f*.The resulting comparison links population optimality to empirical control of excess loss.
6 Additional proofs
The additional proofs establish small-ball behavior for heavy-tailed linear forms and derive the persistence examples, including noise- and radius-dependent bounds for bounded-coordinate designs.
- Heavy-tailed linear forms: Unconditional isotropic vectors with coordinates in Lp for fixed p > 2 satisfy a small-ball condition for every linear functional, with constants depending on κ and p.Such vectors may still be heavy-tailed when p is close to 2.
- Heavy-tailed linear forms: The proof obtains the lower-tail estimate through unconditionality, Khintchine’s inequality, and Paley-Zygmund applied to coordinate contributions.The argument uses coordinate threshold indicators whose expectations are bounded below.
- Bounded-coordinate analysis: For bounded coordinates, the proof uses subgaussian moment control for normalized empirical sums to analyze the persistence class.The coordinate sums have bounded ψ2 norms and corresponding Lp bounds.
- Proof of Theorem 4.6: Theorem 4.6’s proof separates the error into a class-size term and a noise-interaction term, with the latter controlled using multiplier and empirical-process estimates.The resulting probability control combines bounds for the relevant processes.
7 Concluding Remarks
The concluding remarks explain that the framework extends beyond squared loss, while emphasizing that heavy-tailed settings require high-probability rather than average-based control.
- Class indexing: The proof indexes functions through F − f* or, under central symmetry, through a scaled version of F, avoiding dependence on the unknown target in common applications.The centrally symmetric case gives F − F ⊂ 2F.
- Heavy-tailed analysis: Averaged versions of the critical parameter are unsuitable for heavy-tailed problems because the mean need not represent typical behavior.Replacing high-probability control with an average-based parameter would return the analysis to a concentration question.
- Beyond squared loss: For squared loss, the general convex-loss proof simplifies because the first derivative is linear and the second derivative is constant.This removes the substantive role of intermediate Taylor-expansion points in the squared-loss case.
- Beyond squared loss: The results extend to strongly convex losses and, according to related work, to arbitrary convex losses.For merely convex losses, controlling the relevant midpoint-dependent terms requires more careful analysis.