Source-linked AI summary
Distributed Optimization with Arbitrary Local Solvers
Chenxin Ma, Jakub Konečný, Martin Jaggi, Virginia Smith, Michael I. Jordan, Peter Richtárik, Martin Takáč
TL;DR
Distributed optimization needs to retain the performance and adaptability of highly tuned single-machine solvers despite costly communication. The paper introduces CoCoA+, a framework that uses arbitrary local solvers with strong primal-dual guarantees, and reports significant runtime speedups over prior and state-of-the-art methods. Its guarantees allow local-solver accuracy to be chosen as a practical trade-off against communication cost.
Problem
Distributed solvers often cannot fully leverage competitive, tuned single-machine methods or automatically incorporate their subsequent improvements.
Method
CoCoA+ uses arbitrary local solvers within communication rounds, combining local updates through an additive, communication-efficient primal-dual framework.
Results
Significant runtime speedups are reported over the original CoCoA framework and other state-of-the-art methods.
Takeaways & Limitations
The framework supports reusing problem-specific single-machine solvers while providing convergence rates whose outer iterations scale independently of the number of machines.
Takeaways & Limitations
Local subproblem accuracy must be selected in practice because driving the relative error Θ toward zero can require excessive computation, while Θ approaching one reduces local improvement.
Abstract
from arXiv · showhide
With the growth of data and necessity for distributed optimization methods, solvers that work well on a single machine must be re-designed to leverage distributed computation. Recent work in this area has been limited by focusing heavily on developing highly specific methods for the distributed environment. These special-purpose methods are often unable to fully leverage the competitive performance of their well-tuned and customized single machine counterparts. Further, they are unable to easily integrate improvements that continue to be made to single machine methods. To this end, we present a framework for distributed optimization that both allows the flexibility of arbitrary solvers to be used on each (single) machine locally, and yet maintains competitive performance against other state-of-the-art special-purpose distributed methods. We give strong primal-dual convergence rate guarantees for our framework that hold for arbitrary local solvers. We demonstrate the impact of local solver selection both theoretically and in an extensive experimental comparison. Finally, we provide thorough implementation details for our framework, highlighting areas for practical performance gains.
1. Motivation
The paper targets distributed optimization methods that struggle to match tuned single-machine solvers and incorporate their ongoing improvements. It proposes a flexible framework using arbitrary local solvers while addressing communication costs, convergence guarantees, and empirical performance.
- Distributed solvers often cannot match highly tuned single-machine counterparts or automatically benefit from improvements to them.
- The framework uses arbitrary single-machine local solvers and separates local computation from distributed communication.Each round solves local subproblems, then combines partial updates using the global problem's primal-dual structure.
- Users can control local computational effort to balance communication and computation across systems with widely varying communication costs.The framework accommodates different amounts of local work per round while retaining convergence guarantees.
- The framework provides strong primal-dual convergence guarantees, including worst-case rates independent of the number of machines.The paper extends guarantees to smooth and non-smooth losses and reports favorable strong-scaling properties.
- Experiments compare CoCoA and CoCoA+ across datasets, solver choices, and a massive 280 GB dataset.The study examines how arbitrary local solver selection affects distributed performance.
2. Background and Problem Formulation
This section motivates distributed optimization, introduces a framework using arbitrary local solvers and aggregated updates, and formulates the convex primal-dual problem setting.
- Background and Problem Formulation: Single-machine algorithms are typically evaluated by iteration time and iteration count, whereas distributed performance must also account for communication time per round.The distributed model includes a communication cost c, which can dominate local computation when communication is much slower.
- Background and Problem Formulation: Distributed optimization is needed because growing datasets no longer fit in one computer, making computation and data distribution necessary.
- Background and Problem Formulation: The framework forms data-local subproblems, solves them independently with arbitrary local algorithms, and aggregates their partial updates into a global update.Workers operate in parallel without communication while solving their local subproblems.
- Background and Problem Formulation: The framework generalizes CoCoA by analyzing broader update aggregation choices, including summing partial updates rather than only averaging them.The paper states that summing can yield the best result in theory and practice and can produce significant performance gains.
- Background and Problem Formulation: Local solver quality is represented by Θ, where Θ = 0 is an exact subproblem solution and Θ = 1 means no objective improvement during the call.The convergence analysis applies to arbitrarily weak local solvers that achieve a specified local quality.
- Background and Problem Formulation: For strongly convex problems, the number of outer rounds has the form I(ϵ, Θ) = O(log(1/ϵ))/(1−Θ), so high local accuracy has diminishing benefit while Θ approaching 1 causes round complexity to explode.There remain order-of-logarithmic outer iterations even when local subproblems are solved very accurately.
- Background and Problem Formulation: A footnote clarifies that one-step local gradient descent becomes naively distributed gradient descent under the framework’s specified local subproblems.The equivalence depends on the choice of local subproblems described later in the paper.
- 2.1 Problem Formulation: The problem formulation covers convex losses ℓ_i with a regularizer g, and its dual uses the convex conjugates ℓ_i* and g*.The paper states assumptions including convex losses and strong duality under the stated conditions.
3. The Framework
The framework decomposes the dual problem into data-local subproblems solved independently by arbitrary local solvers, then aggregates their updates through a shared d-dimensional vector. Its design preserves locality while requiring only one vector of communication per round.
- Parallel local optimization: Arbitrary local solvers run in parallel on the machines, producing approximate updates to their respective coordinate blocks.The framework does not require communication while local subproblems are being solved.
- Aggregation: The aggregation parameter ν controls whether machine updates are averaged or added, with ν=1/K corresponding to averaging and ν=1 to adding.The parameters ν and σ′ jointly determine a valid approximation to the global objective.
- Locality: Each machine solves a data-local subproblem using its own data, local dual variables, and shared primal information.The subproblem changes only coordinates assigned to that machine.
- Subproblem construction: The local subproblem forms a separable quadratic approximation of the smooth dual objective while retaining the non-smooth regularizer.The approximation coincides with the global objective at the reference point.
- Practical implementation: Per round, machines communicate only their d-dimensional updates to form a new shared vector, which is then broadcast back.This communication pattern maintains consistency of the shared state across rounds.
4. Main Results
The framework provides convergence guarantees for approximate local solutions under smooth and Lipschitz losses, without restricting the local solver beyond sufficient objective decrease. More aggressive adding can improve the theoretical rate over averaging, while local accuracy must be balanced against communication cost.
- Local-solver assumptions: Θ=0 denotes an exact local solution, whereas Θ=1 denotes no improvement; practical choices balance local computation against communication time.The framework can adapt from fast communication systems to slow MapReduce-style rounds.
- Local-solver assumptions: The convergence analysis permits arbitrary local solvers, requiring only the sufficient-decrease condition in Assumption 4.1.This is the central generality of the theoretical results.
- Computation–communication trade-off: The leading complexity term depends inversely on 1−Θ, but highly accurate local solutions may cost more than they save in overall runtime.The preferred accuracy depends on the estimated communication-round duration.
- Adding versus averaging: ν=1 with σ′=K yields a convergence rate that is better than averaging with ν=1/K and σ′=1 in the analyzed smooth-loss comparison.The improvement is especially pronounced when λγn is much larger than σmax.
- Adding versus averaging: Adding provides an analogous order-K improvement for the sub-linear convergence rate with general Lipschitz losses.The difference is negligible when the regularizer is O(1/n).
5. Discussion and Related Work
The framework addresses limitations of existing distributed and batch methods by supporting weak arbitrary local solvers, flexible aggregation, and reusable single-machine algorithms. Its related-work position connects it to proximal, coordinate, stochastic, and communication-limited approaches while retaining broader solver and convergence flexibility.
- Communication regimes: Compared with one-shot and mini-batch methods, the framework avoids relying on specially arranged partitions and simplifies aggregation through an adding choice ν=1.Mini-batch aggregation can otherwise be difficult to tune.
- Distributed batch solvers: Standard ADMM and quasi-Newton methods lack the gradual communication–computation trade-off available in this framework.An inexact ADMM-based exception is restricted to L2-regularized problems and selected losses and provides no complexity results.
- Comparison with proximal methods: Unlike batch proximal and analyzed distributed Newton methods, the framework does not require high-accuracy subproblem solutions or strong data-partition assumptions.Those requirements make competing local solvers expensive and their guarantees less general.
- Distributed methods with local optimization: CoCoA and CoCoA+ are presented as the first frameworks to allow arbitrary weak local solvers while also controlling update aggregation.The convergence theory extends the special case of DisDCA-p beyond coordinate descent.
6. Numerical Experiments
The experiments show that arbitrary local-solver choice, local accuracy, aggregation, and subproblem parameters substantially affect distributed optimization performance. Additive aggregation and suitable solver settings often improve convergence or runtime, while overly aggressive parameter choices can cause divergence.
- Comparison of Different Local Solvers: Coordinate descent (CD) consistently outperforms the other tested local solvers on the RCV dataset.CD avoids evaluating full batch gradients and function values, although some competing solvers can be faster initially.
- Effect of the Quality of Local Solver Solutions on Overall Performance: Increasing local iterations H reduces outer communication rounds but increases local computation time, so the best H balances both costs.For rcvtest, CD with H = 40,000 was faster overall, while L-BFGS performed best with H = 10.
- Averaging vs. Adding the Local Updates: Adding local updates converges faster than averaging across tested solvers and regularization settings on RCV.The advantage is smaller when local solvers perform many iterations; smaller λ requires more iterations to reach the same accuracy.
- The Effect of the Subproblem Parameter σ′: Decreasing σ′ improves communication efficiency only until a dataset-dependent threshold, after which the algorithm diverges.The best values were around σ′ = 5 for rcvtest and σ′ around 6 for epsilon, while the safe σ′ = 8 was only slightly worse.
- Scaling with the Number of Machines: With ν = 1, runtime improves as the number of machines increases, whereas averaging slows as K increases.These observations support the framework’s scaling analysis.
- Comparison with Competing Methods: CoCoA+ usually converges more rapidly early in communication rounds and can still achieve lower running time than competing methods.Its subproblems can be solved more efficiently than those in DiSCO and DANE.
7. Conclusion
The paper presents CoCoA+ as a flexible, communication-efficient framework for distributed primal-dual optimization. Its theory supports arbitrary local solvers and strong scaling, while experiments report runtime speedups over prior methods.
- CoCoA+ enables fast, communication-efficient additive aggregation in distributed primal-dual optimization.
- Its outer-iteration complexity scales independently of the number of machines and supports non-smooth losses, arbitrary strongly convex regularizers, and primal-dual convergence.
- Experiments show significant runtime speedups over the original CoCoA framework and other state-of-the-art methods.
A.1 Proof of Lemma 2.3
The proof uses strong convexity of g to establish smoothness of its conjugate and derive the displayed quadratic bound.
- Because g is 1-strongly convex, g∗ is 1-smooth, enabling inequality (7).The resulting expression includes the quadratic term 1/(2λn^2) h^T X^T Xh.
A.2 Proof of Lemma 3.1
The proof invokes Jensen’s inequality and the block-diagonal structure of G to obtain the stated equality.
- Jensen’s inequality supplies the first bound, while G’s block-diagonal definition yields the final equality.
A.3 Proof of Lemma 3.2
The proof restricts h to a single block, relates X^T X to G, and uses positive semidefiniteness to establish the claimed bound.
- For h supported only on block P_k, h^T X^T Xh equals h^T Gh, implying σ′ ≥ ν.
- Positive semidefiniteness of X^T X supplies the inequality used for distinct blocks k and l.
- For h satisfying h^T Gh ≤ 1, the proof applies definition (10) to control νh^T X^T Xh.
A.4 Proofs of Theorems 4.2 and 4.3
This section introduces the lemmas needed for the main theorems and analyzes the primal-dual quantities under the algorithm’s convexity assumptions. The proof allows weak convexity and concludes with the claimed improvement bound.
- The main-theorem proofs are preceded by several crucial lemmas.
- The lemma assumes each ℓ_i is strongly convex with parameter γ ≥ 0 under the specified norm and algorithmic assumptions.
- The proof estimates expected changes in the dual objective and dual feasibility, then relates them to the duality gap.
- Weakly convex conjugates are explicitly allowed because the lemma remains valid when γ = 0.
- The claimed improvement bound (A3) follows by substituting (A9) into (A6).
A.4.1 Proof of Theorem 4.3
The proof recursively bounds the dual objective and duality gap using parameter choices and convexity inequalities. It then gives an iteration condition guaranteeing a duality gap below the target tolerance.
- The proof recursively applies (A12) and selects s = 1 with t0 determined by ν, Θ, λ, n, L, σ, σ′, and the initial objective gap.
- An induction argument establishes the required bound from the base case t = t0 to every later iteration.
- The proof upper-bounds D and uses the geometric-mean–arithmetic-mean inequality in its estimates.
- For T ≥ ⌈1/[ν(1−Θ)]⌉ + T0 with T0 ≥ t0, the derived bounds satisfy the stated conditions for reducing the duality gap.
- Under γ-strong convexity, substituting the selected s into the bounds yields Rt ≤ 0.
- Once ε_D is sufficiently small relative to ν(1−Θ) and the problem parameters, the duality gap is below ε_Gap after the stated number of iterations.