Adding vs. Averaging in Distributed Primal-Dual Optimization

Abstract

Distributed optimization methods for large-scale machine learning suffer from a communication bottleneck. It is difficult to reduce this bottleneck while still efficiently and accurately aggregating partial work from different machines. In this paper, we present a novel generalization of the recent communication-efficient primal-dual framework (CoCoA) for distributed optimization. Our framework, CoCoA+, allows for additive combination of local updates to the global parameters at each iteration, whereas previous schemes with convergence guarantees only allow conservative averaging. We give stronger (primal-dual) convergence rate guarantees for both CoCoA as well as our new variants, and generalize the theory for both methods to cover non-smooth convex loss functions. We provide an extensive experimental comparison that shows the markedly improved performance of CoCoA+ on several real-world distributed datasets, especially when scaling up the number of machines.

ICML 2015: JMLR W&CP volume37, Proceedings of The 32nd International Conference on Machine Learning, pp. 1973-1982

References in corpus (11)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Distributed Coordinate Descent Method for Learning with Big Data
• An Asynchronous Parallel Stochastic Coordinate Descent Algorithm
• Accelerated Mini-Batch Stochastic Dual Coordinate Ascent
• Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• On Optimal Probabilities in Stochastic Coordinate Descent Methods
• LOCO: Distributing Ridge Regression with Random Projections
• Accelerated Proximal Stochastic Dual Coordinate Ascent for Regularized Loss Minimization

Cited by in corpus (10)

• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Statistically Preconditioned Accelerated Gradient Method for Distributed Optimization
• DAve-QN: A Distributed Averaged Quasi-Newton Method with Local Superlinear Convergence Rate
• Clustering with Distributed Data
• 99% of Distributed Optimization is a Waste of Time: The Issue and How to Fix it
• Local and Global Uniform Convexity Conditions
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• A Privacy-Preserving and Trustable Multi-agent Learning Framework
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Gradient-Leakage Resilient Federated Learning