Learning without Concentration

Abstract

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.

Cited by in corpus (13)

• Early-Learning Regularization Prevents Memorization of Noisy Labels
• The Modern Mathematics of Deep Learning
• On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels
• Probably approximate Bayesian computation: nonasymptotic convergence of ABC under misspecification
• Learning Some Popular Gaussian Graphical Models without Condition Number Bounds
• Robust 1-Bit Compressed Sensing via Hinge Loss Minimization
• Tight bounds for minimum l1-norm interpolation of noisy data
• Robust learning and complexity dependent bounds for regularized problems
• Improved rates for prediction and identification of partially observed linear dynamical systems
• Sum-of-squares meets square loss: Fast rates for agnostic tensor completion
• II. High Dimensional Estimation under Weak Moment Assumptions: Structured Recovery and Matrix Estimation
• Beyond Independent Measurements: General Compressed Sensing with GNN Application
• A convex program for bilinear inversion of sparse vectors