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 (6)

• TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Federated Optimization:Distributed Optimization Beyond the Datacenter
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants

Cited by in corpus (64)

• Federated Learning: Strategies for Improving Communication Efficiency
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• On the Convergence of FedAvg on Non-IID Data
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates
• Communication-Efficient Federated Deep Learning with Asynchronous Model Update and Temporally Weighted Aggregation
• Federated Optimization in Heterogeneous Networks
• Federated Learning of a Mixture of Global and Local Models
• Gradient Sparsification for Communication-Efficient Distributed Optimization
• Byzantine Stochastic Gradient Descent
• 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
• Distributed Learning with Compressed Gradient Differences
• Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Natural Compression for Distributed Deep Learning
• A Bayesian Federated Learning Framework with Online Laplace Approximation
• 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
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Communication-Efficient Local Decentralized SGD Methods
• Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data
• 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
• Stochastic Nonconvex Optimization with Large Minibatches
• Parallel Restarted SPIDER -- Communication Efficient Distributed Nonconvex Optimization with Optimal Computation Complexity
• Bias-Variance Reduced Local SGD for Less Heterogeneous Federated Learning
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Communication-Efficient Distributed Optimization in Networks with Gradient Tracking and Variance Reduction
• Distributed Saddle-Point Problems Under Similarity
• Distributed Second Order Methods with Fast Rates and Compressed Communication
• Local SGD: Unified Theory and New Efficient Methods
• On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond
• Stochastic Channel-Based Federated Learning for Medical Data Privacy Preserving
• Randomized Distributed Mean Estimation: Accuracy vs Communication
• FedDANE: A Federated Newton-Type Method
• DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimization
• COKE: Communication-Censored Decentralized Kernel Learning
• Privacy Preserving Stochastic Channel-Based Federated Learning with Neural Network Pruning
• Distributed Newton Can Communicate Less and Resist Byzantine Workers
• Newton-ADMM: A Distributed GPU-Accelerated Optimizer for Multiclass Classification Problems
• Adaptive Sampling Distributed Stochastic Variance Reduced Gradient for Heterogeneous Distributed Datasets
• A Stochastic Newton Algorithm for Distributed Convex Optimization
• Alternating Direction Method of Multipliers for Quantization
• Optimal Data Splitting in Distributed Optimization for Machine Learning
• DINO: Distributed Newton-Type Optimization Method
• Straggler-Agnostic and Communication-Efficient Distributed Primal-Dual Algorithm for High-Dimensional Data Mining
• Communication-Efficient Distributed Optimization with Quantized Preconditioners
• Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning
• Asynchronous Federated Learning for Sensor Data with Concept Drift
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization
• CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
• Sparse sketches with small inversion bias
• Practical Newton-Type Distributed Learning using Gradient Based Approximations
• Linear Speedup in Personalized Collaborative Learning
• On Second-order Optimization Methods for Federated Learning
• Do Subsampled Newton Methods Work for High-Dimensional Data?
• Newton Method over Networks is Fast up to the Statistical Precision
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters