# Local SGD in Overparameterized Linear Regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 38 references that are in the map.
- First posted on arXiv 20 Oct 2022.

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

- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [Distributed learning with regularized least squares](https://mlsanity.com/paper/1608.03339/) (2016)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression](https://mlsanity.com/paper/2110.06198/) (2021)
- [Communication-Efficient Accurate Statistical Estimation](https://mlsanity.com/paper/1906.04870/) (2019)
- [The Benefits of Implicit Regularization from SGD in Least Squares Problems](https://mlsanity.com/paper/2108.04552/) (2021)
- [A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)](https://mlsanity.com/paper/1710.09430/) (2017)
- [Beating SGD Saturation with Tail-Averaging and Minibatching](https://mlsanity.com/paper/1902.08668/) (2019)
- [Communication-efficient SGD: From Local SGD to One-Shot Averaging](https://mlsanity.com/paper/2106.04759/) (2021)
- [Generalization Properties and Implicit Regularization for Multiple Passes SGM](https://mlsanity.com/paper/1605.08375/) (2016)
- [WONDER: Weighted one-shot distributed ridge regression in high dimensions](https://mlsanity.com/paper/1903.09321/) (2019)
- [Distributed Generalized Cross-Validation for Divide-and-Conquer Kernel Ridge Regression and its Asymptotic Optimality](https://mlsanity.com/paper/1612.05907/) (2016)
- [Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime](https://mlsanity.com/paper/2203.03159/) (2022)
- [Data splitting improves statistical performance in overparametrized regimes](https://mlsanity.com/paper/2110.10956/) (2021)
- [Stochastic Gradient Descent in Hilbert Scales: Smoothness, Preconditioning and Earlier Stopping](https://mlsanity.com/paper/2006.10840/) (2020)

## Abstract (arXiv)

We consider distributed learning using constant stepsize SGD (DSGD) over several devices, each sending a final model update to a central server. In a final step, the local estimates are aggregated. We prove in the setting of overparameterized linear regression general upper bounds with matching lower bounds and derive learning rates for specific data generating distributions. We show that the excess risk is of order of the variance provided the number of local nodes grows not too large with the global sample size. We further compare the sample complexity of DSGD with the sample complexity of distributed ridge regression (DRR) and show that the excess SGD-risk is smaller than the excess RR-risk, where both sample complexities are of the same order.