# Batches Stabilize the Minimum Norm Risk in High Dimensional Overparameterized Linear Regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 42 references that are in the map.
- First posted on arXiv 14 Jun 2023.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [Train longer, generalize better: closing the generalization gap in large batch training of neural networks](https://mlsanity.com/paper/1705.08741/) (2017)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [A Survey on Distributed Machine Learning](https://mlsanity.com/paper/1912.09789/) (2019)
- [Optimal Regularization Can Mitigate Double Descent](https://mlsanity.com/paper/2003.01897/) (2020)
- [Revisiting Small Batch Training for Deep Neural Networks](https://mlsanity.com/paper/1804.07612/) (2018)
- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality](https://mlsanity.com/paper/2102.04396/) (2021)
- [Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints](https://mlsanity.com/paper/1802.08417/) (2018)
- [Distributed Coordinate Descent Method for Learning with Big Data](https://mlsanity.com/paper/1310.2059/) (2013)
- [Distributed linear regression by averaging](https://mlsanity.com/paper/1810.00412/) (2018)
- [WONDER: Weighted one-shot distributed ridge regression in high dimensions](https://mlsanity.com/paper/1903.09321/) (2019)
- [Data splitting improves statistical performance in overparametrized regimes](https://mlsanity.com/paper/2110.10956/) (2021)
- [Distributed Estimation of Gaussian Correlations](https://mlsanity.com/paper/1805.12472/) (2018)
- [Communication Complexity of Estimating Correlations](https://mlsanity.com/paper/1901.09100/) (2019)
- [Communication-efficient sparse regression: a one-shot approach](https://mlsanity.com/paper/1503.04337/) (2015)

## Abstract (arXiv)

Learning algorithms that divide the data into batches are prevalent in many machine-learning applications, typically offering useful trade-offs between computational efficiency and performance. In this paper, we examine the benefits of batch-partitioning through the lens of a minimum-norm overparametrized linear regression model with isotropic Gaussian features. We suggest a natural small-batch version of the minimum-norm estimator and derive bounds on its quadratic risk. We then characterize the optimal batch size and show it is inversely proportional to the noise level, as well as to the overparametrization ratio. In contrast to minimum-norm, our estimator admits a stable risk behavior that is monotonically increasing in the overparametrization ratio, eliminating both the blowup at the interpolation point and the double-descent phenomenon. We further show that shrinking the batch minimum-norm estimator by a factor equal to the Weiner coefficient further stabilizes it and results in lower quadratic risk in all settings. Interestingly, we observe that the implicit regularization offered by the batch partition is partially explained by feature overlap between the batches. Our bound is derived via a novel combination of techniques, in particular normal approximation in the Wasserstein metric of noisy projections over random subspaces.