mlsanityData to 14 Oct 2026

The Sample Complexity of Learning Linear Predictors with the Squared Loss

arXiv 1406.5143 ↗First posted 19 Jun 2014cs.LG stat.MLcited by 16

Not on the map. Why?

Abstract (arXiv)

In this short note, we provide a sample complexity lower bound for learning linear predictors with respect to the squared loss. Our focus is on an agnostic setting, where no assumptions are made on the data distribution. This contrasts with standard results in the literature, which either make distributional assumptions, refer to specific parameter settings, or use other performance measures.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). First posted on arXiv 19 Jun 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 2; 2022: 2; 2023: 5; 2024: 2; 2025: 1; 2026: 4.

16 papers.

Sort:

  1. 2021Distribution-Free Robust Linear Regressioncited by 19
  2. 2022Differentially Private Generalized Linear Models Revisitedcited by 17
  3. 2023An Adaptive Algorithm for Learning with Unknown Distribution Driftcited by 16
  4. 2023High-Probability Risk Bounds via Sequential Predictorscited by 10
  5. 2022Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Conditioncited by 9
  6. 2024Omnipredicting Single-Index Models with Multi-Index Modelscited by 7
  7. 2023Local Risk Bounds for Statistical Aggregationcited by 3
  8. 2026Simultaneous Blackwell Approachability and Applications to Multiclass Omnipredictioncited by 3
  9. 2021Distribution Free Uncertainty for the Minimum Norm Solution of Over-parameterized Linear Regressioncited by 2
  10. 2023Exploring Local Norms in Exp-concave Statistical Learningcited by 2
  11. 2023A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using L-λ Smoothnesscited by 2
  12. 2024Sample Complexity of the Sign-Perturbed Sums Methodcited by 1
4 more
  1. 2026Near-Optimal Private Linear Regression via Iterative Hessian Mixingcited by 1
  2. 2025Hardness, Structural Knowledge, and Opportunity: An Analytical Framework for Modular Performance Modelingcited by 0
  3. 2026Modulated learning for private and distributed regression with just a single sample per client devicecited by 0
  4. 2026The Fast Mixing Mechanism for Differential Privacycited by 0