# Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictors

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Sep 2020.

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

- [Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)](https://mlsanity.com/paper/2103.12024/) (2021)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [An elementary analysis of ridge regression with random design](https://mlsanity.com/paper/2203.08564/) (2022)
- [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)
- [Exploring Local Norms in Exp-concave Statistical Learning](https://mlsanity.com/paper/2302.10726/) (2023)
- [Optimal Excess Risk Bounds for Empirical Risk Minimization on p-Norm Linear Regression](https://mlsanity.com/paper/2310.12437/) (2023)
- [PAC Learning is just Bipartite Matching (Sort of)](https://mlsanity.com/paper/2502.00607/) (2025)
- [Improved Learning Rates for Stochastic Optimization](https://mlsanity.com/paper/2107.08686/) (2021)

## Abstract (arXiv)

We study the problem of predicting as well as the best linear predictor in a bounded Euclidean ball with respect to the squared loss. When only boundedness of the data generating distribution is assumed, we establish that the least squares estimator constrained to a bounded Euclidean ball does not attain the classical O(d/n) excess risk rate, where d is the dimension of the covariates and n is the number of samples. In particular, we construct a bounded distribution such that the constrained least squares estimator incurs an excess risk of order Omega(d3/2/n) hence refuting a recent conjecture of Ohad Shamir [JMLR 2015]. In contrast, we observe that non-linear predictors can achieve the optimal rate O(d/n) with no assumptions on the distribution of the covariates. We discuss additional distributional assumptions sufficient to guarantee an O(d/n) excess risk rate for the least squares estimator. Among them are certain moment equivalence assumptions often used in the robust statistics literature. While such assumptions are central in the analysis of unbounded and heavy-tailed settings, our work indicates that in some cases, they also rule out unfavorable bounded distributions.