Communication-Efficient Distributed Dual Coordinate Ascent

Abstract

Communication remains the most significant bottleneck in the performance of distributed optimization algorithms for large-scale machine learning. In this paper, we propose a communication-efficient framework, CoCoA, that uses local computation in a primal-dual setting to dramatically reduce the amount of necessary communication. We provide a strong convergence rate analysis for this class of algorithms, as well as experiments on real-world distributed datasets with implementations in Spark. In our experiments, we find that as compared to state-of-the-art mini-batch versions of SGD and SDCA algorithms, CoCoA converges to the same .001-accurate solution quality on average 25x as quickly.

NIPS 2014 version, including proofs. Published in Advances in Neural Information Processing Systems 27 (NIPS 2014)

References in corpus (4)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Parallel Coordinate Descent for L1-Regularized Loss Minimization
• Parallel Coordinate Descent Methods for Big Data Optimization
• Analysis of Distributed Stochastic Dual Coordinate Ascent

Cited by in corpus (43)

• Federated Optimization:Distributed Optimization Beyond the Datacenter
• Federated Optimization in Heterogeneous Networks
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• A Survey of Stochastic Simulation and Optimization Methods in Signal Processing
• Federated Learning in Mobile Edge Networks: A Comprehensive Survey
• Communication Complexity of Distributed Convex Learning and Optimization
• Variational Federated Multi-Task Learning
• Distributed Learning with Compressed Gradient Differences
• Central Server Free Federated Learning over Single-sided Trust Social Networks
• Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
• Towards Geo-Distributed Machine Learning
• GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning
• Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Robust Distributed Accelerated Stochastic Gradient Methods for Multi-Agent Networks
• Less than a Single Pass: Stochastically Controlled Stochastic Gradient Method
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks
• Large Scale Kernel Learning using Block Coordinate Descent
• Distributed Multi-Task Learning with Shared Representation
• Splash: User-friendly Programming Interface for Parallelizing Stochastic Algorithms
• Theory of Dual-sparse Regularized Randomized Reduction
• On Convergence of Distributed Approximate Newton Methods: Globalization, Sharper Bounds and Beyond
• A Distributed One-Step Estimator
• Wireless for Machine Learning
• Tracking Performance of Online Stochastic Learners
• Distributed Multitask Learning
• A Primal-Dual Algorithm for Hybrid Federated Learning
• COKE: Communication-Censored Decentralized Kernel Learning
• Linear convergence of SDCA in statistical estimation
• Distributed Training of Structured SVM
• SCOPE: Scalable Composite Optimization for Learning on Spark
• An efficient distributed learning algorithm based on effective local functional approximations
• Distributed Learning of Finite Gaussian Mixtures
• A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems
• LAGC: Lazily Aggregated Gradient Coding for Straggler-Tolerant and Communication-Efficient Distributed Learning
• FlexPD: A Flexible Framework Of First-Order Primal-Dual Algorithms for Distributed Optimization
• Communication-Efficient Distributed Optimization with Quantized Preconditioners
• Parallel and Communication Avoiding Least Angle Regression
• A Stochastic Large-scale Machine Learning Algorithm for Distributed Features and Observations
• GPU-Accelerated Primal Learning for Extremely Fast Large-Scale Classification
• Addressing Algorithmic Bottlenecks in Elastic Machine Learning with Chicle
• Projected Semi-Stochastic Gradient Descent Method with Mini-Batch Scheme under Weak Strong Convexity Assumption
• Distributed Dual Coordinate Ascent in General Tree Networks and Communication Network Effect on Synchronous Machine Learning