AIDE: Fast and Communication Efficient Distributed Optimization

Abstract

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.

References in corpus (1)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives

Cited by in corpus (29)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• A Field Guide to Federated Optimization
• Expanding the Reach of Federated Learning by Reducing Client Resource Requirements
• Overcoming Forgetting in Federated Learning on Non-IID Data
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Communication Efficiency in Federated Learning: Achievements and Challenges
• Privacy for Free: Communication-Efficient Learning with Differential Privacy Using Sketches
• Stochastic, Distributed and Federated Optimization for Machine Learning
• Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis
• Communication trade-offs for synchronized distributed SGD with large step size
• Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
• DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• Local SGD: Unified Theory and New Efficient Methods
• Stochastic Channel-Based Federated Learning for Medical Data Privacy Preserving
• FedDANE: A Federated Newton-Type Method
• DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimization
• Privacy Preserving Stochastic Channel-Based Federated Learning with Neural Network Pruning
• A Stochastic Newton Algorithm for Distributed Convex Optimization
• DINO: Distributed Newton-Type Optimization Method
• Straggler-Agnostic and Communication-Efficient Distributed Primal-Dual Algorithm for High-Dimensional Data Mining
• Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning
• Asynchronous Federated Learning for Sensor Data with Concept Drift
• On Second-order Optimization Methods for Federated Learning
• Do Subsampled Newton Methods Work for High-Dimensional Data?
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Practical Newton-Type Distributed Learning using Gradient Based Approximations