# Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2020.

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

- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [Decentralized Local Stochastic Extra-Gradient for Variational Inequalities](https://mlsanity.com/paper/2106.08315/) (2021)
- [Faster federated optimization under second-order similarity](https://mlsanity.com/paper/2209.02257/) (2022)
- [Acceleration in Distributed Optimization under Similarity](https://mlsanity.com/paper/2110.12347/) (2021)
- [Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis](https://mlsanity.com/paper/2304.07504/) (2023)
- [Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity](https://mlsanity.com/paper/2205.15136/) (2022)
- [Federated Optimization with Doubly Regularized Drift Correction](https://mlsanity.com/paper/2404.08447/) (2024)
- [Non-convex Stochastic Composite Optimization with Polyak Momentum](https://mlsanity.com/paper/2403.02967/) (2024)
- [Communication-Efficient Distributed Optimization with Quantized Preconditioners](https://mlsanity.com/paper/2102.07214/) (2021)
- [Distributed Saddle-Point Problems Under Similarity](https://mlsanity.com/paper/2107.10706/) (2021)
- [Compression and Data Similarity: Combination of Two Techniques for Communication-Efficient Solving of Distributed Variational Inequalities](https://mlsanity.com/paper/2206.09446/) (2022)
- [Random-reshuffled SARAH does not need a full gradient computations](https://mlsanity.com/paper/2111.13322/) (2021)
- [Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy](https://mlsanity.com/paper/2302.03542/) (2023)
- [Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities](https://mlsanity.com/paper/2302.07615/) (2023)
- [Stabilized Proximal-Point Methods for Federated Optimization](https://mlsanity.com/paper/2407.07084/) (2024)
- [Robust Distributed Optimization With Randomly Corrupted Gradients](https://mlsanity.com/paper/2106.14956/) (2021)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization](https://mlsanity.com/paper/2102.04259/) (2021)
- [Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis](https://mlsanity.com/paper/2501.04443/) (2025)
- [Distributed Event-Based Learning via ADMM](https://mlsanity.com/paper/2405.10618/) (2024)
- [SPAM: Stochastic Proximal Point Method with Momentum Variance Reduction for Non-convex Cross-Device Federated Learning](https://mlsanity.com/paper/2405.20127/) (2024)
- [Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning](https://mlsanity.com/paper/2409.14280/) (2024)
- [Accelerated Methods with Compressed Communications for Distributed Optimization Problems under Data Similarity](https://mlsanity.com/paper/2412.16414/) (2024)
- [Optimal Data Splitting in Distributed Optimization for Machine Learning](https://mlsanity.com/paper/2401.07809/) (2024)
- [Local Methods with Adaptivity via Scaling](https://mlsanity.com/paper/2406.00846/) (2024)
- [Non-Convex Federated Optimization under Cost-Aware Client Selection](https://mlsanity.com/paper/2512.05327/) (2025)
- [Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity](https://mlsanity.com/paper/2405.16126/) (2024)
- [Accelerated Methods with Complexity Separation Under Data Similarity for Federated Learning Problems](https://mlsanity.com/paper/2601.08614/) (2026)
- [From Inexact Gradients to Byzantine Robustness: Acceleration and Optimization under Similarity](https://mlsanity.com/paper/2602.03329/) (2026)
- [Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuning](https://mlsanity.com/paper/2606.14970/) (2026)

## Abstract (arXiv)

We consider the setting of distributed empirical risk minimization where multiple machines compute the gradients in parallel and a centralized server updates the model parameters. In order to reduce the number of communications required to reach a given accuracy, we propose a preconditioned accelerated gradient method where the preconditioning is done by solving a local optimization problem over a subsampled dataset at the server. The convergence rate of the method depends on the square root of the relative condition number between the global and local loss functions. We estimate the relative condition number for linear prediction models by studying uniform concentration of the Hessians over a bounded domain, which allows us to derive improved convergence rates for existing preconditioned gradient methods and our accelerated method. Experiments on real-world datasets illustrate the benefits of acceleration in the ill-conditioned regime.