PaperlayerView exact revision on arXiv

Source-linked AI summary

Adding vs. Averaging in Distributed Primal-Dual Optimization

Chenxin Ma, Virginia Smith, Martin Jaggi, Michael I. Jordan, Peter Richtárik, Martin Takáč

arXiv:1502.03508v2cs.LG

TL;DR

Distributed machine learning must reduce communication without weakening the aggregation of work across machines. This paper introduces COCOA+, which modifies COCOA to support additive local-update aggregation and derives stronger guarantees; experiments report significant speedups, especially as machines scale.

  • Problem

    Distributed optimization suffers from communication bottlenecks, while averaging local updates becomes weaker as the number of machines grows.

  • Method

    COCOA+ modifies COCOA’s local subproblems and uses an aggregation parameter to enable more aggressive additive combination of local updates.

  • Results

    COCOA+ provides stronger primal-dual convergence guarantees and significant experimental speedups over previous methods, with convergence rates independent of K in the worst case.

  • Takeaways & Limitations

    Additive aggregation offers a practical and theoretical alternative to conservative averaging for communication-efficient distributed primal-dual optimization.

  • Takeaways & Limitations

    The framework assumes local solvers produce Θ-approximate solutions and, in the setup, assumes non-negative loss functions.

Abstract

from arXiv · show

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.

1. Introduction

Distributed optimization is constrained by communication costs and by update averaging that weakens as machines multiply. COCOA+ modifies local subproblems to support additive aggregation, with theory and experiments indicating stronger scaling and faster convergence.

  • Distributed machine learning faces a communication bottleneck because worker communication can match local computation while being several orders slower than memory access.
  • COCOA’s averaging dilutes updates by 1/K as the number of machines grows, whereas direct addition can diverge.
  • COCOA+ modifies local subproblems so workers can combine updates additively without extra computational cost.
  • Strong Scaling: COCOA+ has worst-case convergence rates independent of K, while COCOA’s rate degrades as K increases.
  • Theoretical Analysis of Non-Smooth Losses: The analysis covers general convex L-Lipschitz losses, including support vector machines and non-smooth regression variants.
  • Experimental Results: Experiments on real-world distributed datasets confirm COCOA+ strong scaling as K grows, while competing methods slow down.

2. Setup

The paper studies regularized empirical loss minimization with convex losses and formulates both primal and dual problems. The duality gap supplies a computable certificate of approximation quality during training.

  • The setup covers regularized empirical loss minimization with arbitrary convex losses, including hinge loss, and encompasses standard machine-learning models.
  • The dual formulation uses the data matrix A and conjugate loss functions ℓ*_j.
  • A dual vector α determines a corresponding primal feasible point, enabling comparison between primal and dual objectives.
  • Primal-Dual Certificates: The duality gap bounds primal suboptimality and therefore certifies approximation quality.
  • Primal-Dual Certificates: The computable certificate is useful during training because primal-only methods such as SGD cannot accurately detect whether the model is well trained.
  • Classes of Loss-Functions: The analysis assumes non-negative loss functions and separately defines Lipschitz-continuous and smooth loss classes.

3. The COCOA+ Algorithm Framework

COCOA+ distributes data-local dual subproblems and aggregates their approximate solutions using a tunable parameter. Its modified subproblems permit more aggressive additive updates while retaining flexible local solvers.

  • Local Subproblems in COCOA+: COCOA+ assigns each worker a local subproblem depending only on locally available data, the shared primal vector, and local dual-variable changes.
  • The parameter σ′ measures the difficulty of the data partition and must satisfy a lower-bound condition for the framework’s analysis.
  • The aggregation parameter γ controls how aggressively local updates are combined, including direct addition to the global vector w.
  • COCOA+ performs parallel local approximate solves, then updates the global variables by aggregating the workers’ results.

4. Convergence Guarantees

The convergence analysis covers smooth and non-smooth losses and provides primal-dual guarantees for averaging and adding regimes. The adding regime has iteration complexity independent of the number of machines, unlike averaging, and experiments support this advantage.

  • The analysis establishes convergence for non-smooth L-Lipschitz losses in both objective value and primal-dual gap.
  • More aggressive addition requires significantly fewer total iterations than averaging, with adding independent of K while averaging degrades as K grows.
  • For averaging with γ := 1/K, the worst-case iteration requirement increases as the number of machines K increases.
  • For COCOA+ adding with γ := 1, the stated iteration bound is significantly better than the averaging case.
  • The analogous smooth-loss analysis again gives a K-independent COCOA+ rate while the COCOA variant degrades with K.
  • The averaging choice with σ′ := 1 recovers the original COCOA algorithm, whose earlier analysis covered only smooth losses and dual suboptimality rather than the duality gap.

5. SDCA as an Example Local Solver

The paper uses randomized coordinate ascent (SDCA) as an illustrative local solver for COCOA+, with convergence guarantees for both smooth and non-smooth losses. The required local approximation quality depends on the number of inner iterations and the aggregation parameter.

  • The local solver receives worker-local α variables and a shared compatible vector w as inputs.The convergence rates depend on the approximation quality Θ supplied by the local solver.
  • LOCALSDCA applies randomized coordinate ascent to the COCOA+ local subproblem.The algorithm initializes local updates and performs H randomized coordinate selections over the worker’s data partition.
  • For smooth losses, LOCALSDCA satisfies the local approximation assumption when H is chosen according to Theorem 13.The theorem assumes each loss function is (1/µ)-smooth.
  • For non-smooth losses, LOCALSDCA satisfies the local approximation assumption under the L-Lipschitz condition in Theorem 14.This extends the solver analysis beyond smooth objectives.
  • Increasing σ′ can raise the worst-case local computational cost because aggregation becomes more aggressive, but experiments report negligible additional cost relative to the speed gain.The remark compares the computational trade-off across COCOA+ regimes ranging from averaging to adding updates.

6. Discussion and Related Work

The discussion situates COCOA+ among distributed optimization methods that trade communication against local computation. It emphasizes that COCOA+ combines flexible local optimization with additive aggregation, while related approaches face communication, accuracy, or convergence limitations.

  • SGD-based Algorithms: Distributed SGD variants can require communication comparable to the amount of data read locally, limiting their practical competitiveness.Parameter-server approaches communicate frequently even when using small per-worker mini-batches.
  • One-Shot Communication Schemes: One-shot communication methods reduce communication but require additional data-partition assumptions and may lack convergence guarantees for all regularizers.These methods occupy the low-communication extreme of the computation–communication trade-off.
  • Mini-Batch Methods: Increasing mini-batch size causes mini-batch SGD and coordinate-descent convergence rates to approach batch gradient descent.The degradation follows because mini-batch updates depend on the available local data.
  • Methods Allowing Local Optimization: Methods using local optimization often require highly accurate subproblem solutions, which can be prohibitive for large per-machine datasets.COCOA instead permits local data subproblems with weaker solver accuracy.
  • COCOA+: COCOA+ retains convergence-efficient local aggregation while allowing additive updates, unlike conservative averaging schemes.Figure 1 compares COCOA and COCOA+ using duality gap against communication and elapsed time across datasets and settings.
  • Related Additive Methods: DisDCA-p is recovered as a special COCOA+ case with SDCA, balanced partitions, and σ′ := K, while COCOA+ supplies convergence theory for that setting.The practical method had previously been proposed without convergence guarantees.
  • ADMM and Batch Proximal Methods: ADMM uses a penalty parameter to balance constraints and objective optimization, but its known rates are weaker and parameter selection is often unclear.Batch proximal methods likewise require high-accuracy subproblem solutions, unlike COCOA+ with weak-accuracy solvers.

7. Numerical Experiments

Experiments on distributed real-world datasets compare COCOA+ with COCOA and other methods across regularization, local iteration, and machine-count settings. COCOA+ consistently improves convergence and exhibits strong scaling, while its aggregation parameter presents a speed–stability trade-off.

  • Experimental Setup: COCOA+ converges faster than COCOA in total rounds and elapsed time across varied datasets, regularization, batch sizes, and cluster sizes.The experiments use several large distributed datasets and implement the methods in Apache Spark on Amazon EC2 instances.
  • Experimental Setup: The experiments use binary hinge-loss support vector machines, extending practical and theoretical evaluation to a non-smooth loss.SDCA serves as the local solver for both COCOA and COCOA+; under balanced partitions and σ′ := K, COCOA+ reduces to DisDCA-p.
  • COCOA versus COCOA+: Across Covertype and RCV1, COCOA+ reaches the optimum faster than COCOA in both communication count and elapsed time across regularization and local-iteration settings.The discrepancy is larger for greater regularization values, according to the reported comparison.
  • Scaling with K: COCOA+ improves with additional machines, whereas COCOA becomes linearly slower as K increases and begins degrading only slightly after K=16 on RCV1.This behavior confirms the strong-scaling prediction of the theory.
  • Effect of σ′: For RCV1 with K=8 and H=1e4, convergence is best around σ′=4 but diverges for σ′ ≤2.The experiment uses the aggressive γ=1 variant, where updates are added.
  • Scaling with K: COCOA+ converges twice as fast as COCOA on 100 Epsilon machines and nearly 7 times as fast on RCV1; mini-batch SGD is an order of magnitude slower than both.Figure 2 measures time to reach an ϵD-accurate solution as K increases.
  • Effect of σ′: The safe upper bound σ′ := γK performs only slightly worse than the practically best parameter.This makes the easy-to-calculate bound a useful practical choice despite the existence of an unsafe optimum.

8. Conclusion

The paper concludes that COCOA+ enables communication-efficient additive aggregation with strong convergence and scaling properties. Its theory covers stronger primal-dual guarantees and non-smooth convex losses, while experiments show substantial speedups over prior methods.

  • COCOA+ enables fast, communication-efficient additive aggregation for distributed primal-dual optimization.The framework combines additive updates with theoretical analysis of its convergence behavior.
  • Theoretical convergence rates for COCOA+ have outer iterations scaling independently of the number of machines.The paper also extends the analysis to non-smooth losses.
  • Experiments report significant speedups over COCOA and other state-of-the-art distributed optimization methods.The conclusion summarizes the empirical comparison rather than identifying a single benchmark value.

B. Proofs

The proofs bound expected changes in dual objectives and feasibility by decomposing terms, applying convexity inequalities, and selecting iteration parameters to obtain convergence guarantees.

  • Bounding the proof terms: The analysis separates terms A and B, bounds B using the safe separability measure σ′, and combines the bounds to derive an improvement guarantee.The proof invokes Jensen’s inequality and substitutes the separate bounds into the main inequality.
  • Dual-objective change: The proof analyzes the expected change of the dual objective using the dual update and the local solver’s approximation-quality assumption.The update is written as α(t+1) := α(t) + γP, with local quality controlled by Assumption 1.
  • General convex case: For general convex losses, the strong convexity parameter is µ = 0, changing the definition of the residual term R(t).The proof then recursively bounds the resulting quantities and selects a burn-in time t0.
  • Iteration requirements: The proof chooses t0 and T so the resulting bounds fall below the target duality-gap tolerance ϵG.The argument uses geometric and arithmetic mean inequalities to establish the required recursive bounds.

B.6. Proof of Theorem 10

This proof derives a duality-gap convergence result by relating expected dual-objective change to the duality gap and applying coordinate-descent-style bounds.

  • Assumptions and proof strategy: The proof assumes the relevant loss functions are µ-strongly convex with respect to the chosen norm and uses this structure in the convergence argument.The proof also cites coordinate-descent techniques as the basis for its analysis.
  • Convergence conclusion: After sufficiently many iterations, the proof obtains a duality gap less than ϵG under the stated relationship between ϵD and ϵG.The bound connects the duality gap to the dual-objective error through the convergence parameters.
  • Composite-function formulation: The analysis defines a composite function F(ζ) = Φ(ζ) + f(ζ), where ζ collects local dual-variable updates.The function is used to analyze the local optimization subproblem.
  • Local-update analysis: The smooth component has a coordinate-wise Lipschitz-continuous gradient, enabling coordinate-descent bounds for the local updates.The argument applies these bounds over successive local steps and selects H to satisfy the theorem’s assumption.

C. Relationship of DisDCA to COCOA+

The section establishes relationships between COCOA+ and DisDCA-p while emphasizing COCOA+’s broader framework, arbitrary local solvers, data-adaptive parameters, and convergence theory.

  • Relationship to DisDCA-p: With SDCA, equal data partitions, σ′ = K, and γ = 1, COCOA+ reduces exactly to DisDCA-p.This correspondence is stated as a special case of the COCOA+ framework.
  • Update correspondence: During one outer round, COCOA+ and DisDCA-p produce the same evolution of local dual variables and the same trajectory of ulocal under the stated coordinate-update conditions.The equivalence requires care when the same coordinate is sampled more than once in a round.
  • Framework abstraction: COCOA+ is a framework rather than a single algorithm because it permits arbitrary local solvers for approximate local subproblem updates.This separates the distributed scheme from problem-specific single-machine solver choices.
  • Data adaptation: The data-dependent parameter σ′ adapts the local subproblems to partition difficulty while remaining decoupled from the chosen local solver.The safe bound σ′ = K can be pessimistic, whereas data structure may justify smaller values.
  • Scope of the correspondence: The exact DisDCA-p correspondence breaks when σ′ differs from K, and practical data partitions may be unbalanced.SDCA is also described as a demonstration choice rather than necessarily the best available local solver.
  • Theoretical guarantees: The framework supplies convergence rates for arbitrary local solvers and provides theoretical justification for COCOA and DisDCA-p in broader convex settings.The stated rates cover general convex objectives and, for DisDCA-p, both general convex and smooth convex objectives.
Loading 1502.03508v2…