mlsanityData to 14 Oct 2026

A Stochastic Newton Algorithm for Distributed Convex Optimization

arXiv 2110.02954 ↗First posted 7 Oct 2021math.OC cs.LG stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

We propose and analyze a stochastic Newton algorithm for homogeneous distributed stochastic convex optimization, where each machine can calculate stochastic gradients of the same population objective, as well as stochastic Hessian-vector products (products of an independent unbiased estimator of the Hessian of the population objective with arbitrary vectors), with many such stochastic computations performed between rounds of communication. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance, by proving convergence guarantees for quasi-self-concordant objectives (e.g., logistic regression), alongside empirical evidence.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 23 of its 47 references that are in the map. First posted on arXiv 7 Oct 2021.

Builds on

23 of 47 references.

References · 23

  1. 2021Convex optimizationcited by 2,515
  2. 2018Local SGD Converges Fast and Communicates Littlecited by 605
  3. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 367
  4. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  5. 2019SCAFFOLD: Stochastic Controlled Averaging for Federated Learningcited by 175
  6. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  7. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  8. 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 132
  9. 2017On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimizationcited by 92
  10. 2020Federated Accelerated Stochastic Gradient Descentcited by 85
  11. 2019First Analysis of Local GD on Heterogeneous Datacited by 81
  12. 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
11 more
  1. 2017GIANT: Globally Improved Approximate Newton Method for Distributed Optimizationcited by 44
  2. 2016AIDE: Fast and Communication Efficient Distributed Optimizationcited by 43
  3. 2020Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitationscited by 40
  4. 2018Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimizationcited by 34
  5. 2020Acceleration with a Ball Optimization Oraclecited by 31
  6. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 31
  7. 2021Distributed Second Order Methods with Fast Rates and Compressed Communicationcited by 25
  8. 2018Global linear convergence of Newton's method without strong-convexity or Lipschitz gradientscited by 24
  9. 2016Accelerated Methods for Non-Convex Optimizationcited by 20
  10. 2019DINGO: Distributed Newton-Type Method for Gradient-Norm Optimizationcited by 20
  11. 2021LocalNewton: Reducing Communication Bottleneck for Distributed Learningcited by 15

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 3; 2024: 2.

6 papers.

  1. 2024The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communicationcited by 12
  2. 2023Federated Online and Bandit Convex Optimizationcited by 7
  3. 2022FLECS-CGD: A Federated Learning Second-Order Framework via Compression and Sketching with Compressed Gradient Differencescited by 2
  4. 2023Federated Composite Saddle Point Optimizationcited by 0
  5. 2023Adaptive pruning-based Newton's method for distributed learningcited by 0
  6. 2024Natural Policy Gradient and Actor Critic Methods for Constrained Multi-Task Reinforcement Learningcited by 0