# Local SGD Accelerates Convergence by Exploiting Second Order Information of the Loss Function

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 16 references that are in the map.
- First posted on arXiv 24 May 2023.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Federated Learning for Mobile Keyboard Prediction](https://mlsanity.com/paper/1811.03604/) (2018)
- [Identifying and attacking the saddle point problem in high-dimensional non-convex optimization](https://mlsanity.com/paper/1406.2572/) (2014)
- [The Loss Surfaces of Multilayer Networks](https://mlsanity.com/paper/1412.0233/) (2014)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Don't Use Large Mini-Batches, Use Local SGD](https://mlsanity.com/paper/1808.07217/) (2018)
- [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021)
- [FedVision: An Online Visual Object Detection Platform Powered by Federated Learning](https://mlsanity.com/paper/2001.06202/) (2020)
- [First Analysis of Local GD on Heterogeneous Data](https://mlsanity.com/paper/1909.04715/) (2019)
- [Local SGD With a Communication Overhead Depending Only on the Number of Workers](https://mlsanity.com/paper/2006.02582/) (2020)

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

- [EDiT: A Local-SGD-Based Efficient Distributed Training Method for Large Language Models](https://mlsanity.com/paper/2412.07210/) (2024)

## Abstract (arXiv)

With multiple iterations of updates, local statistical gradient descent (L-SGD) has been proven to be very effective in distributed machine learning schemes such as federated learning. In fact, many innovative works have shown that L-SGD with independent and identically distributed (IID) data can even outperform SGD. As a result, extensive efforts have been made to unveil the power of L-SGD. However, existing analysis failed to explain why the multiple local updates with small mini-batches of data (L-SGD) can not be replaced by the update with one big batch of data and a larger learning rate (SGD). In this paper, we offer a new perspective to understand the strength of L-SGD. We theoretically prove that, with IID data, L-SGD can effectively explore the second order information of the loss function. In particular, compared with SGD, the updates of L-SGD have much larger projection on the eigenvectors of the Hessian matrix with small eigenvalues, which leads to faster convergence. Under certain conditions, L-SGD can even approach the Newton method. Experiment results over two popular datasets validate the theoretical results.