# The Sample Complexity of Learning Linear Predictors with the Squared Loss

arXiv: https://arxiv.org/abs/1406.5143 · HTML: https://mlsanity.com/paper/1406.5143/

## Key facts

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

## Built on by (most cited first, 16 of 16)

- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [Differentially Private Generalized Linear Models Revisited](https://mlsanity.com/paper/2205.03014/) (2022)
- [An Adaptive Algorithm for Learning with Unknown Distribution Drift](https://mlsanity.com/paper/2305.02252/) (2023)
- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition](https://mlsanity.com/paper/2202.11461/) (2022)
- [Omnipredicting Single-Index Models with Multi-Index Models](https://mlsanity.com/paper/2411.13083/) (2024)
- [Local Risk Bounds for Statistical Aggregation](https://mlsanity.com/paper/2306.17151/) (2023)
- [Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction](https://mlsanity.com/paper/2602.17577/) (2026)
- [Distribution Free Uncertainty for the Minimum Norm Solution of Over-parameterized Linear Regression](https://mlsanity.com/paper/2102.07181/) (2021)
- [Exploring Local Norms in Exp-concave Statistical Learning](https://mlsanity.com/paper/2302.10726/) (2023)
- [A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using L-λ Smoothness](https://mlsanity.com/paper/2307.15892/) (2023)
- [Sample Complexity of the Sign-Perturbed Sums Method](https://mlsanity.com/paper/2409.01243/) (2024)
- [Near-Optimal Private Linear Regression via Iterative Hessian Mixing](https://mlsanity.com/paper/2601.07545/) (2026)
- [Hardness, Structural Knowledge, and Opportunity: An Analytical Framework for Modular Performance Modeling](https://mlsanity.com/paper/2509.11000/) (2025)
- [Modulated learning for private and distributed regression with just a single sample per client device](https://mlsanity.com/paper/2605.07233/) (2026)
- [The Fast Mixing Mechanism for Differential Privacy](https://mlsanity.com/paper/2605.30600/) (2026)

## 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.