# AIDE: Fast and Communication Efficient Distributed Optimization

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Aug 2016.

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

- [FedNL: Making Newton-Type Methods Applicable to Federated Learning](https://mlsanity.com/paper/2106.02969/) (2021)
- [A Bayesian Federated Learning Framework with Online Laplace Approximation](https://mlsanity.com/paper/2102.01936/) (2021)
- [Communication Efficiency in Federated Learning: Achievements and Challenges](https://mlsanity.com/paper/2107.10996/) (2021)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning](https://mlsanity.com/paper/2102.03198/) (2021)
- [Distributed Second Order Methods with Fast Rates and Compressed Communication](https://mlsanity.com/paper/2102.07158/) (2021)
- [AdaBest: Minimizing Client Drift in Federated Learning via Adaptive Bias Estimation](https://mlsanity.com/paper/2204.13170/) (2022)
- [Acceleration in Distributed Optimization under Similarity](https://mlsanity.com/paper/2110.12347/) (2021)
- [Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning](https://mlsanity.com/paper/2111.01847/) (2021)
- [Asynchronous Federated Learning for Sensor Data with Concept Drift](https://mlsanity.com/paper/2109.00151/) (2021)
- [SHED: A Newton-type algorithm for federated learning based on incremental Hessian eigenvector sharing](https://mlsanity.com/paper/2202.05800/) (2022)
- [SAFARI: Sparsity enabled Federated Learning with Limited and Unreliable Communications](https://mlsanity.com/paper/2204.02321/) (2022)
- [Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation](https://mlsanity.com/paper/2206.03588/) (2022)
- [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)
- [On Second-order Optimization Methods for Federated Learning](https://mlsanity.com/paper/2109.02388/) (2021)
- [Linear Speedup in Personalized Collaborative Learning](https://mlsanity.com/paper/2111.05968/) (2021)
- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [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)
- [Stabilized Proximal-Point Methods for Federated Optimization](https://mlsanity.com/paper/2407.07084/) (2024)
- [A Stochastic Newton Algorithm for Distributed Convex Optimization](https://mlsanity.com/paper/2110.02954/) (2021)
- [FedSSO: A Federated Server-Side Second-Order Optimization Algorithm](https://mlsanity.com/paper/2206.09576/) (2022)
- [Memory-Constrained Algorithms for Convex Optimization via Recursive Cutting-Planes](https://mlsanity.com/paper/2306.10096/) (2023)
- [Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications](https://mlsanity.com/paper/2101.01505/) (2021)
- [CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems](https://mlsanity.com/paper/2105.14216/) (2021)
- [Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning](https://mlsanity.com/paper/2202.06083/) (2022)
- [Convergence of Agnostic Federated Averaging](https://mlsanity.com/paper/2507.10325/) (2025)
- [Communication-Efficient {Federated} Learning Using Censored Heavy Ball Descent](https://mlsanity.com/paper/2209.11944/) (2022)

## Abstract (arXiv)

In this paper, we present two new communication-efficient methods for distributed minimization of an average of functions. The first algorithm is an inexact variant of the DANE algorithm that allows any local algorithm to return an approximate solution to a local subproblem. We show that such a strategy does not affect the theoretical guarantees of DANE significantly. In fact, our approach can be viewed as a robustification strategy since the method is substantially better behaved than DANE on data partition arising in practice. It is well known that DANE algorithm does not match the communication complexity lower bounds. To bridge this gap, we propose an accelerated variant of the first method, called AIDE, that not only matches the communication lower bounds but can also be implemented using a purely first-order oracle. Our empirical results show that AIDE is superior to other communication efficient algorithms in settings that naturally arise in machine learning applications.