Learning without Concentration

By Shahar Mendelson. 2014

348 citations recorded by the source corpus.

We obtain sharp bounds on the estimation error of the Empirical Risk Minimization procedure, 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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Variance-based Regularization with Convex Objectives (2016, background): “In many cases, such tradeoffs require either conditions such as the Mammen-Tsybakov noise condition [15, 6] or localization results [3, 2, 17] made possible by curvature conditions that relate the risk and variance.”
Slope meets Lasso: Improved oracle bounds and optimality (2016, background): “A useful sufficient condition for the s-sparse eigenvalue condition is the small ball condition [14, 19, 21].”
Relative deviation learning bounds and generalization with unbounded loss functions (2013, methodology): “Another approach is taken in [37], which avoids concentration based methods for the squared loss function, though the bounds produced are not straightforward to interpret.”
Regularization, sparse recovery, and median-of-means tournaments (2017, methodology): “In a similar fashion for the norm Ψ used as a regularization function, let In what follows we make two important modiﬁcations to the deﬁnitions of the complexity parameters used in [12, 13, 10].”
Learning with Square Loss: Localization through Offset Rademacher Complexity (2015, background): “In a recent pathbreaking paper, [14] showed that a large part of this heavy machinery is not necessary for obtaining tight upper bounds on excess loss, even—and especially—if functions are unbounded.”
Learning from MOM’s principles: Le Cam’s approach (2017, background): “We refer to Koltchinskii and Mendelson (2015); Lecu´e and Mendelson (2014); Mendelson (2015b, 2014b, 2015a); Rudelson and Vershynin (2014) for examples of distributions satisfying this assumption.”
Loss Minimization and Parameter Estimation with Heavy Tails (2013, background): “In recent work, Mendelson (2014) proposes a more subtle ‘small-ball’ criterion for analyzing the performance of the risk minimizer.”
Risk minimization by median-of-means tournaments (2016, background): “To this end, let us introduce some notation, following the path of [29, 30].”
Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity (2018, methodology): “That is, f(x;S) ≥ f(x?;S) + λ dist(x,X ?) with nonzero probability, which is reasonably easy to check (for example, using the Paley-Zygmund inequality and Mendelson’s small-ball conditions [39]).”
Convergence rates of least squares regression estimators with heavy-tailed errors (2017, background): “This complements Mendelson’s work [35, 44, 46, 47, 49] that allows arbitrary dependence between ξi and Xi’s with independent observations in a learning framework.”
On the Risk of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels (2019, background): “The approach proceeds along the lines of (Koltchinskii and Mendelson, 2015; Mendelson, 2014).”
Early-Learning Regularization Prevents Memorization of Noisy Labels (2020, methodology): “In the other direction, we employ a method based on [30].”
Conformal prediction with conditional guarantees (2023, positive): “For the second condition note that by the Paley-Zygmund inequality Thus, by Theorem 5.4 in Mendelson (2014) we have that there exists constants a, b > 0 such that with probability at least 1 − c (cid:48) d 2 / ( n + 1) 2”