mlsanityData to 14 Oct 2026

Learning without Concentration

arXiv 1401.0304 ↗First posted 1 Jan 2014cs.LG stat.MLcited by 50

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 50 papers in the map (data through 14 Oct 2026). First posted on arXiv 1 Jan 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 15; 2022: 10; 2023: 10; 2024: 6; 2025: 3; 2026: 6.

50 papers.

Sort:

By area:

  1. 2021Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfittingcited by 54
  2. 2022Statistical Learning Theory for Control: A Finite Sample Perspectivecited by 53
  3. 2022Learning with little mixingcited by 33
  4. 2023A Tutorial on the Non-Asymptotic Theory of System Identificationcited by 26
  5. 2022Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Biascited by 22
  6. 2023Aiming towards the minimizers: fast convergence of SGD for overparametrized problemscited by 22
  7. 2021Distribution-Free Robust Linear Regressioncited by 19
  8. 2021Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regressioncited by 17
  9. 2021On Empirical Risk Minimization with Dependent and Heavy-Tailed Datacited by 16
  10. 2021Tight bounds for minimum l1-norm interpolation of noisy datacited by 16
  11. 2021Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Gamescited by 16
  12. 2021On the Power of Preconditioning in Sparse Linear Regressioncited by 15
38 more
  1. 2024On the Performance of Empirical Risk Minimization with Smoothed Datacited by 13
  2. 2024Shallow diffusion networks provably learn hidden low-dimensional structurecited by 12
  3. 2022A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Modelscited by 11
  4. 2022Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiencycited by 10
  5. 2024Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Losscited by 10
  6. 2022Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Conditioncited by 9
  7. 2022On the Importance of Gradient Norm in PAC-Bayesian Boundscited by 6
  8. 2023The noise level in linear regression with dependent datacited by 6
  9. 2021Beyond Independent Measurements: General Compressed Sensing with GNN Applicationcited by 5
  10. 2021Universal and data-adaptive algorithms for model selection in linear contextual banditscited by 5
  11. 2023Learning linear dynamical systems under convex constraintscited by 5
  12. 2024Evaluating Model Performance Under Worst-case Subpopulationscited by 5
  13. 2022Outlier Robust and Sparse Estimation of Linear Regression Coefficientscited by 4
  14. 2021On the Minimal Error of Empirical Risk Minimizationcited by 3
  15. 2023On the Variance, Admissibility, and Stability of Empirical Risk Minimizationcited by 3
  16. 2023Perceptual adjustment queries and an inverted measurement paradigm for low-rank metric learningcited by 3
  17. 2021AdaBoost and robust one-bit compressed sensingcited by 2
  18. 2021DeepMoM: Robust Deep Learning With Median-of-Meanscited by 2
  19. 2021Posterior concentration and fast convergence rates for generalized Bayesian learningcited by 2
  20. 2022Error Bound of Empirical ℓ2 Risk Minimization for Noisy Standard and Generalized Phase Retrieval Problemscited by 2
  21. 2023Exact Recovery for System Identification with More Corrupt Data than Clean Datacited by 2
  22. 2023Optimal Excess Risk Bounds for Empirical Risk Minimization on p-Norm Linear Regressioncited by 2
  23. 2025Do we really need the Rademacher complexities?cited by 2
  24. 2021Some Hoeffding- and Bernstein-type Concentration Inequalitiescited by 1
  25. 2022A note on the smallest eigenvalue of the empirical covariance of causal Gaussian processescited by 1
  26. 2023Uniform Risk Bounds for Learning with Dependent Data Sequencescited by 1
  27. 2024On the Efficiency of ERM in Feature Learningcited by 1
  28. 2025Complexity Dependent Error Rates for Physics-informed Statistical Learning via the Small-ball Methodcited by 1
  29. 2026Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite Lp Momentscited by 1
  30. 2026On the Gradient Heterogeneity Dynamics of Adversarially Robust Federated Regressioncited by 1
  31. 2021Empirical Risk Minimization for Time Series: Nonparametric Performance Bounds for Predictioncited by 0
  32. 2023Sample Complexity of Linear Regression Models for Opinion Formation in Networkscited by 0
  33. 2024Subsampled Ensemble Can Improve Generalization Tail Exponentiallycited by 0
  34. 2025RANSAC Revisited: An Improved Algorithm for Robust Subspace Recovery under Adversarial and Noisy Corruptionscited by 0
  35. 2026Learning When to Trust LLM Priors: A Validated Framework for Semantic Prior Integrationcited by 0
  36. 2026Cost-Driven Representation Learning for Linear Quadratic Gaussian Control: Part IIcited by 0
  37. 2026Optimal Centered Active Excitation in Linear System Identificationcited by 0
  38. 2026Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tailscited by 0