PaperlayerView exact revision on arXiv

Source-linked AI summary

CoCoA: A General Framework for Communication-Efficient Distributed Optimization

Virginia Smith, Simone Forte, Chenxin Ma, Martin Takac, Michael I. Jordan, Martin Jaggi

arXiv:1611.02189v2cs.LG

TL;DR

Large-scale machine learning needs distributed optimization that limits costly communication while supporting varied objectives and system trade-offs. CoCoA provides a flexible primal-dual framework with arbitrary local solvers, convergence guarantees, and support for non-strongly-convex regularizers. On real distributed datasets, it achieves up to a 50× speedup over widely used methods.

  • Problem

    Distributed optimization must reduce costly inter-machine communication while accommodating differing datasets, systems, objectives, and solver settings.

  • Method

    CoCoA uses duality to construct distributed subproblems, permits arbitrary local solvers and flexible communication, and analyzes primal-dual convergence including non-strongly-convex regularizers.

  • Results

    Up to a 50× speedup over other widely used distributed methods was achieved on real-world distributed datasets.

  • Takeaways & Limitations

    CoCoA offers a general communication-efficient framework whose communication profile, local solver accuracy, data distribution, and primal-dual form can be adapted to the setting.

  • Takeaways & Limitations

    One-shot communication schemes can reduce communication but, unlike CoCoA, are generally not guaranteed to converge to the optimal solution.

Abstract

from arXiv · show

The scale of modern datasets necessitates the development of efficient distributed optimization methods for machine learning. We present a general-purpose framework for distributed computing environments, CoCoA, that has an efficient communication scheme and is applicable to a wide variety of problems in machine learning and signal processing. We extend the framework to cover general non-strongly-convex regularizers, including L1-regularized problems like lasso, sparse logistic regression, and elastic net regularization, and show how earlier work can be derived as a special case. We provide convergence guarantees for the class of convex regularized loss minimization objectives, leveraging a novel approach in handling non-strongly-convex regularizers and non-smooth loss functions. The resulting framework has markedly improved performance over state-of-the-art methods, as we illustrate with an extensive set of experiments on real distributed datasets.

1. Introduction

CoCoA addresses distributed optimization’s communication bottleneck and limited solver flexibility with a general primal-dual framework that supports tailored communication and arbitrary local solvers. It provides convergence guarantees and reports substantial empirical speedups on real distributed datasets.

  • Motivation: Distributed learning requires methods that coordinate information efficiently because communication is more expensive than local computation and trade-offs vary across systems and objectives.The framework must therefore accommodate flexible communication-computation profiles while preserving convergence guarantees.
  • Framework: CoCoA uses arbitrary local solvers in parallel and a flexible communication scheme whose amount can be tailored to the problem and system.This design directly incorporates application-specific single-machine solvers and can substantially reduce distributed communication.
  • Framework: Primal-dual information helps decompose objectives into meaningful distributed subproblems while enabling convergence guarantees and duality-gap certificates.The framework supports different decompositions depending on data distribution and whether optimization is performed in the primal or dual.
  • Contributions: The framework covers non-strongly-convex regularizers, supports feature- or training-point partitioning, and runs in either primal or dual form.These capabilities extend the framework beyond more restricted earlier settings.
  • Contributions: CoCoA provides O(1/t) communication-round convergence for convex objectives with Lipschitz continuous losses and a faster linear rate for strongly convex losses.The guarantees do not degrade with the number of machines and permit arbitrary local subproblem accuracies.
  • Experiments: Up to 50× speedups over state-of-the-art methods are reported in extensive experiments on real-world distributed datasets.The experiments also compare primal and dual variants and examine how local subproblem accuracy affects convergence.

2. Background and Setup

The paper formulates distributed convex regularized loss minimization through primal-dual objectives and maps problem classes to suitable variants based on loss smoothness and regularizer convexity. This setup covers common machine-learning models and specifies duality, assumptions, mappings, and data partitioning across machines.

  • Objective: The general objective combines a convex loss ℓ with a convex regularizer r, covering support vector machines, linear and logistic regression, lasso, and sparse logistic regression.The regularizer may be expressed as r(u) = λ∥u∥p, while the loss is commonly a sum of individual losses.
  • Primal-Dual Setting: The framework supports primal and dual optimization by mapping the input objective to alternative distributed formulations and seeking a minimizer in a distributed fashion.Fenchel-Rockafellar duality connects the formulations, and both are written as minimization problems for the framework.
  • Primal-Dual Setting: The duality gap is non-negative, reaches zero only for an optimal pair under strong duality, and provides a computable upper bound on primal and dual suboptimality.It also serves as a certificate of approximation quality and a practical stopping criterion.
  • Problem Cases: The framework distinguishes three cases according to loss smoothness and regularizer strong convexity: smooth/strongly convex, smooth/non-strongly convex separable, and non-smooth/separable settings.Different framework variants apply depending on which case describes the input problem.
  • Examples: Elastic-net regression can map to either primal or dual objectives, whereas lasso maps to the primal because its L1 norm is non-strongly convex.The choice of mapping affects data distribution and overall framework performance.
  • Data Partitioning: The dataset is partitioned across K machines by columns of A, where columns may represent training examples or features depending on the application.The framework discusses these distribution schemes as part of choosing suitable primal or dual variants.

3. The CoCoA Method

CoCoA distributes optimization by assigning data-local subproblems to machines, combining their updates through a flexible aggregation scheme. Its primal and dual variants accommodate different loss and regularizer properties while supporting adjustable local computation and communication.

  • Primal vs. Dual: CoCoA offers primal and dual views of the same distributed minimization problem, choosing the view according to smoothness and strong-convexity properties.The primal variant typically distributes by feature, while the dual variant typically distributes by training point.
  • Generalized Framework: The local objective uses a quadratic approximation of the globally coupled term f(Aα), allowing minimization to separate across machines.The resulting subproblem is quadratic apart from the local regularizer term and depends on f only through its linearization at v.
  • Generalized Framework: Each machine solves a data-local subproblem using only its local columns and the previous shared vector v.The framework initializes shared and local variables, invokes parallel local solvers, and returns their updates to shared state.
  • Framework Parameters: The aggregation parameter γ controls how machine updates are combined, while σ′ controls the local subproblem and can be set as σ′ := γK or improved using data-dependent information.The standard choice γ := 1 and σ′ := K guarantees convergence and provides the fastest convergence rates described here.
  • Communication and Local Solvers: CoCoA permits arbitrary local solvers and adjustable local accuracy, enabling communication to be traded against computation across different system settings.This flexibility spans low-communication settings with more local iterations and high-communication settings with fewer local iterations.
  • Scope and Interpretation: The framework covers non-strongly-convex regularizers and non-smooth losses, while feature-wise primal execution can reduce communication when the number of features is high.Its parallel block-Jacobi updates combine with potentially faster local Gauss-Seidel-style work, and approximate subproblem solutions are supported by the theory.

4. Convergence Analysis

CoCoA provides convergence guarantees for convex objectives across non-strongly-convex and strongly convex settings, using primal-dual analysis and a bounded-support modification. Its rates support flexible local accuracy and communication profiles, with convergence guarantees that do not degrade as the number of machines increases.

  • General convex objectives: CoCoA introduces a primal-dual technique for analyzing objectives with non-strongly-convex regularizers and non-smooth losses.The framework provides convergence rates for general convex gi and includes lasso, sparse logistic regression, and hinge-loss SVM models.
  • Rates and scalability: The framework allows arbitrary local solver accuracies and provides convergence guarantees that do not degrade with the number of machines K.For convex objectives with Lipschitz continuous losses, the stated communication-round rate is O(1/t), while strongly convex losses receive a faster linear rate.
  • Global convergence: The sum of local subproblem objectives forms a block-separable upper bound on the global objective when aggregation and subproblem parameters satisfy the prescribed conditions.This relationship connects local progress to global convergence through the main lemma and the subproblem-approximation assumption.
  • Bounded-support modification: For non-strongly-convex regularizers such as L1, bounded-support modification preserves the original solutions and iterates while enabling primal-dual convergence guarantees.Unlike smoothing, the modification does not require tuning a smoothing parameter and leaves algorithms for the original objectives unchanged.
  • Strongly convex objectives: For strongly convex regularizers, CoCoA obtains a faster linear convergence rate, including for elastic net regression and logistic regression.The strongly convex case is covered by Theorem 3 and contrasts with the sublinear rates obtained for cases II and III.

5. Applications

CoCoA casts diverse loss and regularization problems into primal or dual forms that support distributed optimization. The applications include smooth losses, non-strongly-convex regularizers, and non-smooth losses, while local subproblems can reuse established single-machine solvers.

  • Framework mappings: The application section maps common objectives into three cases based on smoothness, strong convexity, separability, and the choice of primal or dual formulation.Examples are organized around minimizing objectives of the form ℓ(u) + r(u).
  • Smooth losses: Least-squares and logistic regression instantiate the smooth-loss setting, with least squares using a 1-smooth loss and logistic regression using a separable classifier loss.For least squares, the primal-dual mapping is the residual vector w(α) := Aα−b.
  • Strongly convex regularizers: Elastic net regularization provides a strongly convex example that interpolates between L1 and L2 penalties through the parameter η.The special cases η = 1 and η = 0 yield the L1-norm and L2-norm, respectively.
  • Non-strongly-convex regularizers: L1 regularization and group lasso illustrate non-strongly-convex regularizers, with L1 requiring the bounded-support modification for primal-dual convergence and certificates.For sufficiently large B, the modified L1 problem has the same solution as the original objective.
  • Non-smooth losses: Hinge loss and absolute deviation loss represent non-smooth losses handled through the dual formulation with strongly convex regularization.The framework applies a sublinear convergence rate to this case because the loss is non-smooth.
  • Local solvers: CoCoA local subproblems resemble the global problem on smaller datasets, allowing existing single-machine or multicore solvers to be reused.For L1-regularized examples, established solvers such as glmnet variants or blitz can be applied directly to local subproblems.

6. Experiments

The experiments evaluate CoCoA on lasso, elastic net, and SVM problems against distributed optimization baselines. Results show strong performance, robustness across settings, and practical trade-offs between primal and dual formulations and local subproblem accuracy.

  • Experimental setup: CoCoA is compared with Mb-SGD, Prox-GD, OWL-QN, ADMM, and mini-batch coordinate methods on large-scale regression and classification tasks.Experiments use Apache Spark and real distributed datasets.
  • CoCoA in the primal: CoCoA’s primal formulation converges faster than the compared methods for lasso, especially on datasets with many features.The evaluation measures improvement to the primal objective OA(α) against wall-clock time.
  • Robustness: CoCoA’s speedups remain robust across different lasso regularization values and elastic-net settings.Figure 2 varies λ for lasso and η for elastic net.
  • Primal versus dual: For pure L1 regularization, smoothing the dual either changes the solution or slows convergence, motivating primal CoCoA.Reducing the smoothing parameter improves sparsity matching but degrades performance.
  • Primal versus dual: CoCoA in the dual converges faster for SVM experiments, while elastic-net results favor the dual when training points greatly outnumber features.Dual performance deteriorates as strong convexity disappears.
  • Communication and computation: CoCoA exposes one main tuning parameter, local subproblem approximation quality Θ, controlled experimentally through H.Increasing H improves communication-round performance, while total wall time reflects the computation spent locally.

7. Related Work

The related work spans batch, mini-batch, distributed, parallel, and one-shot optimization methods. CoCoA distinguishes itself through flexible local solvers, communication-computation trade-offs, and convergence guarantees accommodating inexact local solutions.

  • Parallel methods: Shotgun is a special case of the framework but lacks CoCoA’s convergence coverage because its upper-bound condition is not guaranteed to be safe.Its frequent communication is particularly problematic in distributed environments.
  • One-shot communication schemes: One-shot methods use a single communication round but require data-partitioning assumptions that are often unavailable in practice.This places them at the low-communication extreme of distributed optimization.
  • Mini-batch methods: Mini-batch methods reduce communication bottlenecks by processing multiple points or features per communication round.Their convergence can degrade toward batch-gradient rates as mini-batch size increases.
  • Batch solvers: Batch methods have low communication requirements but require full distributed batch-gradient computations and lack CoCoA’s gradual communication-computation trade-off.The comparison includes ADMM, gradient descent, and L-BFGS.
  • Distributed solvers: CoCoA’s convergence rates allow arbitrary local approximation quality and local solvers that can be cheaper than batch methods.The theory incorporates local inexactness directly rather than requiring exact or fixed-quality subproblem solutions.
  • Distributed solvers: CoCoA supports any local solver, whereas related distributed methods such as specialized L1 approaches impose narrower approximation or problem-structure choices.The framework also relates to block-diagonal Hessian methods for distributed L1 optimization.

8. Discussion

The discussion presents CoCoA as a general communication-efficient primal-dual framework whose local subproblems support solver reuse and adaptable communication. It reports convergence guarantees and up to 50× speedups on real-world distributed datasets.

  • Framework: CoCoA derives machine-specific subproblems using duality, enabling parallel local optimization and reuse of state-of-the-art single-machine solvers.Local updates reduce and adapt communication to the system.
  • Convergence: The framework’s global primal-dual convergence rates are agnostic to the particular local solvers.The analysis also studies the effect of local solver approximation quality.
  • Non-strong convexity: CoCoA extends its convergence treatment to non-strongly-convex regularizers through a bounded-support modification technique.This addresses difficult cases including non-smooth regularization.
  • Empirical results: Up to 50× speedup over other widely used methods is reported on real-world distributed datasets.The result comes from an extensive experimental comparison with state-of-the-art distributed solvers.
  • Supporting theory: Convex conjugacy underlies the appendix’s supporting theory, including equivalences between Lipschitzness and bounded support and between smoothness and strong convexity.These properties support the primal-dual derivations used by the framework.

Appendix B. Proofs of Primal-Dual Relationships

The appendix derives primal-dual relationships for the paper’s general objectives and illustrates the bounded-support modification through the conjugate of a modified L1 norm.

  • Primal-dual relationships: The appendix derives the primal-dual relationship for the general objectives (A) and (B).It then applies the derivation to the conjugate of a modified L1 norm.

B.1 Primal-Dual Relationship

The appendix derives the dual of the original formulation using standard Fenchel-Rockafellar duality. It introduces an auxiliary variable and Lagrange multipliers, then converts the resulting maximization into the stated minimization form.

  • The original formulation is related to its dual through Fenchel-Rockafellar duality.The passage presents this relationship as standard in convex analysis.
  • An auxiliary vector v is introduced to derive the dual formulation.
  • Lagrange multipliers w are used to form the Lagrangian.
  • Taking the infimum over α and v yields the dual problem.
  • Changing signs converts the dual maximization into the claimed minimization formulation (B).

B.2 Continuous Conjugate Modification for Indicator Functions

This section derives the modified L1-norm conjugate and compares consensus ADMM formulations with CoCoA. The comparison shows that ADMM updates can take a form similar to CoCoA subproblems under suitable parameter and variable transformations.

  • Continuous Conjugate Modification for Indicator Functions: The convex conjugate of the bounded-support modification of the L1-norm is characterized directly from the conjugate definition.The proof separates cases according to α relative to ±B and the interval [−B, B].
  • Continuous Conjugate Modification for Indicator Functions: For α ∈ [0, B], the maximizer is constrained to x⋆ ∈ [0, 1], with maximum α attained at x = 1.
  • Continuous Conjugate Modification for Indicator Functions: The conjugate’s Lipschitz continuity follows directly or from the equivalence between Lipschitz conjugates and bounded support of the original functions.
  • Consensus ADMM comparison: Consensus ADMM is decomposed through re-parameterization, augmented-Lagrangian construction, and decomposable updates.
  • Consensus ADMM comparison: The dual form of an ADMM update for w_k has a similar form to the CoCoA subproblem under ρ := τ.
  • Consensus ADMM comparison: Applying consensus ADMM to the primal formulation introduces local copies and consensus constraints, and its first minimization is solved locally across partitions.
  • Consensus ADMM comparison: With ρ := σ′/τ and Δα[k] = αk − α(t−1), the local ADMM subproblems become the CoCoA local subproblems.
  • Consensus ADMM comparison: The global α update is not separable, making the dual formulation a more natural comparison setting for distributed ADMM.The passage also relates the primal formulation to sharing ADMM.

Appendix D. Convergence Proofs

The convergence proofs extend earlier arguments directly to the original formulation (A). They relate local-subproblem progress to the global objective using smoothness, Jensen’s inequality, and the local solver quality assumption.

  • The proofs generalize prior convergence reasoning so it applies directly to formulation (A).Full details are given for Lemma 1, while later proofs emphasize strategy and deviations from earlier work.
  • The first lemma relates progress on local subproblems to the global objective OA(·).
  • The local solver quality parameter Θ is incorporated into the convergence analysis through the local subproblem objective.
  • An outer CoCoA iteration is analyzed using a general (1/τ)-smoothness assumption on f(·).
  • The proof bounds separate terms using smoothness of f and Jensen’s inequality before substituting them into the iteration bound.

D.2 Proof of Main Convergence Result (Theorem 2)

The main convergence result bounds the expected duality gap of Algorithm 1 under local-solver and regularity assumptions. The proof combines local progress, duality-gap identities, recursive bounds, and parameter choices to obtain an iteration requirement.

  • The convergence analysis characterizes how Algorithm 1 iterations affect the duality gap for a local solver of quality Θ.
  • Assumptions and proof ingredients: The proof permits weakly convex g_i by allowing the strong-convexity parameter μ = 0.
  • Assumptions and proof ingredients: The analysis extends earlier convergence arguments to generalized subproblems Gσ′.
  • Proof of progress: Expected objective progress is bounded by relating the local subproblems to the global objective through the solver quality Θ.
  • Proof of progress: The duality gap is expressed using formulations (A) and (B), convex conjugates, and the maximal property of convex conjugates.
  • Proof of progress: The claimed improvement bound follows by substituting the convex-conjugate bound into the preceding inequality.
  • Uniform bounds: L-Lipschitz continuity of g_i* implies bounded effective support for g_i, which supplies a uniform bound on R(t).
  • Uniform bounds: If data points satisfy ∥x_i∥ ≤ 1 and the partition is balanced, then σ ≤ n^2/K, yielding a bound on R(t).

D.3 Proof of Convergence Result for Strongly Convex gi

The convergence result analyzes Algorithm 1 when the local regularizers are strongly convex, deriving iteration requirements for suboptimality and expected duality-gap guarantees. The proof specializes general theorem parameters and uses assumptions on the data, regularizers, and loss smoothness.

  • Initialization: The proof initializes α(0) as the zero vector and reduces the initial duality gap using the conjugate-objective identities.It uses f∗(w(0)) = −f(0) together with the initial assumption on g(0).
  • Theorem 11: Theorem 11 assumes µ-strong convexity of every gi and defines σmax as the maximum local σk.These assumptions support the subsequent iteration and duality-gap bounds for Algorithm 1.
  • Duality-gap guarantee: After T iterations, the analysis provides an expected duality-gap bound for Algorithm 1.The bound is established by applying the strong-convexity-based theorem and the definition of σk.
  • Theorem’ 3: Under the stated assumptions, T iterations of Algorithm 1 suffice to reach suboptimality ϵOA.The specialized theorem also includes assumptions on bounded columns of A and the form of g∗i.
  • Proof specialization: The proof converts the general theorem into a specialized rate by setting γ := 1, σ′ := K, and ˜µ = nµ.For balanced datasets, the resulting expression is further simplified using the stated parameter relationships.
  • Proof specialization: For the 1-smooth least-squares and logistic losses, τ = 1 simplifies the convergence rate.This simplification applies to the loss examples identified in the paper.
Loading 1611.02189v2…