mlsanityData to 7 Oct 2026

Local SGD in Overparameterized Linear Regression

arXiv 2210.11562 ↗First posted 20 Oct 2022stat.ML cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

19 of 38 references.

References · 19

  1. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  2. 2019Benign Overfitting in Linear Regressioncited by 544
  3. 2020Benign overfitting in ridge regressioncited by 152
  4. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  5. 2013Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Ratescited by 64
  6. 2016Distributed learning with regularized least squarescited by 42
  7. 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 41
  8. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 37
  9. 2019Communication-Efficient Accurate Statistical Estimationcited by 32
  10. 2021The Benefits of Implicit Regularization from SGD in Least Squares Problemscited by 32
  11. 2017A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)cited by 25
  12. 2019Beating SGD Saturation with Tail-Averaging and Minibatchingcited by 21
7 more
  1. 2021Communication-efficient SGD: From Local SGD to One-Shot Averagingcited by 19
  2. 2016Generalization Properties and Implicit Regularization for Multiple Passes SGMcited by 16
  3. 2019WONDER: Weighted one-shot distributed ridge regression in high dimensionscited by 14
  4. 2016Distributed Generalized Cross-Validation for Divide-and-Conquer Kernel Ridge Regression and its Asymptotic Optimalitycited by 9
  5. 2022Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regimecited by 8
  6. 2021Data splitting improves statistical performance in overparametrized regimescited by 6
  7. 2020Stochastic Gradient Descent in Hilbert Scales: Smoothness, Preconditioning and Earlier Stoppingcited by 5

Built on by

Not cited yet.