# Sketched Ridgeless Linear Regression: The Role of Downsampling

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 45 references that are in the map.
- First posted on arXiv 2 Feb 2023.

## Builds on (most cited first, 19 of 19)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [Sensitivity and Generalization in Neural Networks: an Empirical Study](https://mlsanity.com/paper/1802.08760/) (2018)
- [High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification](https://mlsanity.com/paper/1507.03003/) (2015)
- [An Analysis of Deep Neural Network Models for Practical Applications](https://mlsanity.com/paper/1605.07678/) (2016)
- [Classification vs regression in overparameterized regimes: Does the loss function matter?](https://mlsanity.com/paper/2005.08054/) (2020)
- [Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime](https://mlsanity.com/paper/2004.12019/) (2020)
- [Asymptotics of Ridge (less) Regression under General Source Condition](https://mlsanity.com/paper/2006.06386/) (2020)
- [Interpolating Classifiers Make Few Mistakes](https://mlsanity.com/paper/2101.11815/) (2021)
- [A Statistical Perspective on Randomized Sketching for Ordinary Least-Squares](https://mlsanity.com/paper/1406.5986/) (2014)
- [Lectures on Randomized Numerical Linear Algebra](https://mlsanity.com/paper/1712.08880/) (2017)
- [Substitution principle for CLT of linear spectral statistics of high-dimensional sample covariance matrices with applications to hypothesis testing](https://mlsanity.com/paper/1404.6633/) (2014)

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

- [High-dimensional analysis of double descent for linear regression with random projections](https://mlsanity.com/paper/2303.01372/) (2023)
- [Asymptotically free sketched ridge ensembles: Risks, cross-validation, and tuning](https://mlsanity.com/paper/2310.04357/) (2023)
- [Analysis of Bootstrap and Subsampling in High-dimensional Regularized Regression](https://mlsanity.com/paper/2402.13622/) (2024)
- [Ensemble linear interpolators: The role of ensembling](https://mlsanity.com/paper/2309.03354/) (2023)
- [Implicit Regularization Paths of Weighted Neural Representations](https://mlsanity.com/paper/2408.15784/) (2024)
- [Why Self-Training Helps and Hurts: Denoising vs. Signal Forgetting](https://mlsanity.com/paper/2602.14029/) (2026)
- [Prediction Risk and Estimation Risk of the Ridgeless Least Squares Estimator under General Assumptions on Regression Errors](https://mlsanity.com/paper/2305.12883/) (2023)

## Abstract (arXiv)

Overparametrization often helps improve the generalization performance. This paper presents a dual view of overparametrization suggesting that downsampling may also help generalize. Focusing on the proportional regime masymp n asymp p, where m represents the sketching size, n is the sample size, and p is the feature dimensionality, we investigate two out-of-sample prediction risks of the sketched ridgeless least square estimator. Our findings challenge conventional beliefs by showing that downsampling does not always harm generalization but can actually improve it in certain cases. We identify the optimal sketching size that minimizes out-of-sample prediction risks and demonstrate that the optimally sketched estimator exhibits stabler risk curves, eliminating the peaks of those for the full-sample estimator. To facilitate practical implementation, we propose an empirical procedure to determine the optimal sketching size. Finally, we extend our analysis to cover central limit theorems and misspecified models. Numerical studies strongly support our theory.