PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking

Ran Xin, Usman A. Khan

arXiv:1808.02942v2math.OC

TL;DR

Distributed optimization requires agents with local smooth, strongly-convex objectives to reach the global minimizer over communication graphs, while prior gradient-tracking approaches lacked a clear unifying connection. The paper identifies AB as the common framework and introduces ABm, which adds heavy-ball momentum and nonidentical local step-sizes while using row- and column-stochastic weights. ABm achieves global R-linear convergence for sufficiently small positive largest step-size, with numerical acceleration especially on ill-conditioned objectives.

  • Problem

    The paper addresses distributed minimization of a sum of smooth, strongly-convex local objectives and the unclear relationship among existing gradient-tracking methods.

  • Method

    The paper uses AB as a state-transformation framework and extends it to ABm by adding heavy-ball momentum, nonidentical local step-sizes, and row- and column-stochastic weights.

  • Results

    ABm has a global R-linear convergence rate when the largest step-size is positive and sufficiently small, with numerical acceleration especially for ill-conditioned objectives.

  • Takeaways & Limitations

    ABm provides a unified distributed optimization and average-consensus framework applicable to undirected and directed graphs without doubly-stochastic weights or eigenvector estimation.

Abstract

from arXiv · show

We study distributed optimization to minimize a global objective that is a sum of smooth and strongly-convex local cost functions. Recently, several algorithms over undirected and directed graphs have been proposed that use a gradient tracking method to achieve linear convergence to the global minimizer. However, a connection between these different approaches has been unclear. In this paper, we first show that many of the existing first-order algorithms are in fact related with a simple state transformation, at the heart of which lies the $\mathcal{AB}$ algorithm. We then describe \textit{distributed heavy-ball}, denoted as $\mathcal{AB}m$, i.e., $\mathcal{AB}$ with momentum, that combines gradient tracking with a momentum term and uses nonidentical local step-sizes. By simultaneously implementing both row- and column-stochastic weights, $\mathcal{AB}m$ removes the conservatism in the related work due to doubly-stochastic weights or eigenvector estimation. $\mathcal{AB}m$ thus naturally leads to optimization and average-consensus over both undirected and directed graphs, casting a unifying framework over several well-known consensus algorithms over arbitrary strongly-connected graphs. We show that $\mathcal{AB}m$ has a global $R$-linear rate when the largest step-size is positive and sufficiently small. Following the standard practice in the heavy-ball literature, we numerically show that $\mathcal{AB}m$ achieves accelerated convergence especially when the objective function is ill-conditioned.

I. INTRODUCTION

The paper studies distributed optimization of sums of smooth, strongly-convex local objectives using only neighbor communication. It connects gradient-tracking methods through AB and proposes ABm to support optimization and consensus on undirected and directed graphs.

  • Problem formulation: Agents collaboratively minimize an aggregate objective whose local smooth, strongly-convex functions are known only individually.The global minimizer is unique under the stated smoothness and strong-convexity assumptions.
  • Existing methods: DGD-type methods generally converge sublinearly with diminishing step-sizes, while constant step-sizes improve speed at the cost of inexact solutions.Augmented Lagrangian methods can achieve exact linear convergence but require more computation per iteration.
  • Existing methods: Gradient-tracking methods extend linear-convergence results across undirected, directed, and time-varying graphs using different stochastic-weight designs.The cited approaches include Aug-DGM, ADD-OPT, and related methods based on dynamic consensus or push-sum.
  • AB framework: AB generalizes several first-order gradient-tracking methods by simultaneously using row- and column-stochastic weights, making it applicable to arbitrary directed graphs.This design removes the need for eigenvector estimation required by earlier column-stochastic approaches.
  • Paper contributions: ABm extends AB with heavy-ball momentum, nonidentical local step-sizes, and a framework covering optimization and average-consensus over arbitrary strongly-connected graphs.The paper establishes global R-linear convergence when the largest step-size is positive and sufficiently small.

A. Heavy-ball method

The heavy-ball method adds momentum to gradient descent to accelerate convergence, particularly for ill-conditioned objectives. The paper adapts this idea to distributed optimization through ABm, where agents maintain local estimates and auxiliary gradient-tracking variables.

  • Motivation: Gradient descent slows as the condition number Q of the objective increases, with a rate expressed in terms of Q.The paper identifies large Q with ill-conditioned objectives.
  • Heavy-ball method: Heavy-ball adds the momentum term β(x_k − x_{k−1}) to the gradient update.The parameters α and β are selected as step-size and momentum parameters.
  • Heavy-ball method: With specific α and β, heavy-ball has a locally accelerated rate O((√Q−1/√Q+1)^k), while arbitrary initial conditions guarantee only linear convergence analytically.Global acceleration is typically assessed through numerical analysis and simulations.
  • Distributed heavy-ball: ABm assigns each agent a local estimate x_i^k and an auxiliary variable y_i^k, with local step-size α_i and momentum parameter β_i.The algorithm is initialized with arbitrary local estimates and uses graph-associated weights.
  • Distributed heavy-ball: ABm uses row-stochastic A for state mixing and column-stochastic B for gradient tracking, and reduces to AB when all β_i equal zero.The gradient-tracking variable asymptotically supplies the global descent direction.

III. CONNECTION WITH EXISTING FIRST-ORDER METHODS

The AB algorithm provides a unifying representation of gradient-tracking methods through state transformations, relating formulations with doubly-stochastic, column-stochastic, or row-stochastic weights. These transformations also connect AB to momentum-based and consensus protocols.

  • Optimization with DS weights: AB generalizes several gradient-tracking methods by using separate row-stochastic and column-stochastic weight matrices.Methods using doubly-stochastic weights arise as special cases because such weights satisfy both stochasticity requirements.
  • Optimization with DS weights: Unlike EXTRA, AB supports non-doubly-stochastic and non-symmetric weight matrices while retaining a gradient-tracking formulation.Eliminating the y^k update yields an EXTRA-format representation, but EXTRA's symmetry-based analysis does not directly establish AB's linear convergence.
  • Optimization with CS weights: A state transformation converts AB's row-stochastic update into a column-stochastic formulation related to ADD-OPT and Push-DIGing.The transformed implementation requires two primitive column-stochastic matrices respecting the graph topology.
  • Optimization with CS weights: ADD-OPT and Push-DIGing estimate a right eigenvector locally, whereas AB avoids this estimation by retaining row-stochastic weights.The eigenvector-estimation nonlinearity creates stability issues, and the resulting convergence is slower than AB's according to the passage.
  • Optimization with RS weights: A complementary transformation produces a row-stochastic-only representation, connecting AB with FROST-type methods and their eigenvector-based scaling.The transformed formulation uses the right eigenvector of the column-stochastic matrix in AB's original representation.
  • Extensions and consensus: ABm extends these equivalences by adding momentum, yielding momentum versions of Aug-DGM, ADD-OPT/Push-DIGing, and FROST, while also supporting average-consensus protocols.The paper presents ABm as a distributed heavy-ball method built on AB's representation.

IV. CONVERGENCE ANALYSIS

The convergence analysis combines contractions for row- and column-stochastic matrices with gradient-tracking conservation and standard strongly-convex optimization results. These ingredients support the analysis of ABm under smoothness and strong convexity assumptions.

  • Auxiliary Results: The analysis begins by establishing contractions for the augmented row-stochastic and column-stochastic weight matrices under suitable vector norms.The contraction constants satisfy 0 < σ_A < 1 and 0 < σ_B < 1.
  • Auxiliary Results: The sum of the tracking variables preserves the sum of local gradients through dynamic consensus with column-stochastic weights.This conservation property is used as a bridge between distributed tracking and the global gradient information.
  • Auxiliary Results: The optimization component relies on the standard contraction of distance to the optimizer for gradient descent on smooth, strongly-convex objectives.The cited lemma applies when the objective is µ-strongly-convex and l-smooth, with a step-size restricted by the stated bound.
  • Auxiliary Results: A nonnegative-matrix spectral-radius lemma converts a componentwise inequality Xx < ωx into the bound ρ(X) < ω.This result supplies a spectral condition used in the convergence analysis.

B. Main results

ABm analyzes consensus, optimality, state-difference, and biased gradient-estimation errors through an LTI contraction framework. Under sufficiently small step-size and momentum bounds, it converges globally R-linearly to the global minimizer.

  • Convergence analysis: ABm's convergence analysis tracks four quantities: network consensus error, optimality gap, state difference, and biased gradient-estimation error.These quantities form the state of an LTI-system inequality used to establish convergence.
  • Convergence analysis: The biased gradient-estimation error is distinguished from the unbiased error defined using a doubly-stochastic weight matrix.ABm uses B∞ in the biased error, whereas the comparison uses W∞ for doubly-stochastic weights.
  • Main theorem: ABm converges to the global minimizer at a global R-linear rate.The result follows from the contraction relationships among the four tracked quantities.
  • Main theorem: The theorem requires upper bounds on the largest step-size α and momentum parameter β, with tunable parameters depending on network topology and objective functions.The bounds ensure the contraction conditions needed for ρ(Jα,β) < 1.
  • Limitations: For arbitrary directed graphs, the bounds on α and β may be noncomputable because contraction and norm-equivalence constants can be unknown.For undirected graphs, computable bounds can be obtained; larger step-sizes require smaller momentum parameters for stability.
  • Heterogeneous step-sizes: ABm's largest-step-size bound is independent of step-size heterogeneity, allowing agents to choose sufficiently small local step-sizes without coordination.The bound also permits zero step-sizes among agents when the largest step-size is positive and sufficiently small.

V. AVERAGE-CONSENSUS FROM ABm

ABm naturally yields an average-consensus algorithm, ABm-C, on strongly-connected directed graphs. Its analysis gives global R-linear convergence to the average, while momentum incorporates information from past iterations.

  • ABm-C construction: Choosing suitable local objective functions in ABm produces ABm-C, an average-consensus algorithm for strongly-connected directed graphs.The construction uses the identity ∇f(xk+1) −∇f(xk) = xk+1 −xk and, for simplicity, identical α and β.
  • Convergence: ABm-C converges R-linearly to the average of the agents' υi values by the ABm convergence theorem.Concrete rate statements could be obtained by studying the spectral radius of the associated system matrix.
  • Relation to surplus consensus: When β = 0, ABm-C still converges to the average and reduces to surplus consensus after a state transformation.The transformation can use a diagonal, invertible matrix that respects the graph topology.
  • Relation to surplus consensus: Compared with surplus consensus, ABm-C uses information from past iterations through its momentum term.The paper identifies this history information as momentum from the distributed-optimization perspective.
  • Unifying framework: State transformations connect ABm-derived consensus protocols with methods using doubly-, column-, or row-stochastic weights.The resulting protocols include consensus forms associated with methods such as ADD-OPT and FROST.

VI. NUMERICAL EXPERIMENTS

The numerical experiments use randomly generated sparse undirected and directed graphs with 500 agents. Figure 1 shows representative samples of the two graph types used in the experiments.

  • Experimental graphs: The experiments use an undirected graph G1 and a directed graph G2, each with n = 500 agents.The graphs are generated using nearest-neighbor rules with fewer than 0.05% random links.
  • Experimental graphs: The graphs contain fewer than 4% of all possible edges.Figure 1 omits self-edges and random links for visual clarity.
  • Weight construction: The experiments generate doubly-stochastic weights with a Laplacian method and row- and column-stochastic weights using uniform weighting.The text states that only the uniform strategy can be used over directed graphs.
  • Figure 1: Figure 1 places the undirected graph G1 on the left and the directed graph G2 on the right.The displayed graphs are representative samples because the graphs are randomly generated across experiments.

A. Logistic Regression

The logistic-regression experiments compare ABm with momentum against distributed and centralized baselines on undirected and directed graphs. Momentum improves convergence over applicable methods without momentum, while ADD-OPT/Push-DIGing is slower in the directed setting.

  • Experimental setup: The study minimizes a global logistic-regression objective using privately held training data at each agent.Each agent has training pairs with p features and binary labels, and the agents cooperatively minimize the sum of local losses.
  • Undirected graphs: On undirected graphs, the comparison includes ABm with row- and column-stochastic weights, ABm with doubly-stochastic weights, gradient-tracking methods, EXTRA, and centralized gradient descent.Performance is evaluated using the average residual across agents.
  • Directed graphs: On directed graphs, the comparison includes ABm, AB, ADD-OPT/Push-DIGing, and centralized gradient descent because doubly-stochastic-weight algorithms are not applicable.The algorithm parameters are selected as discussed in the paper, while the gradient-descent step-size uses its specified optimum.
  • Results: Momentum improves convergence over applicable algorithms without momentum, whereas ADD-OPT/Push-DIGing is much slower because of eigenvector estimation.This result is reported for the directed-graph comparison.

B. Distributed Quadratic Programming

The quadratic-programming experiments examine distributed and centralized convergence as the global objective’s condition number changes. ABm with momentum outperforms centralized gradient descent when the condition number is large.

  • Problem setup: The experiments use a quadratic global objective whose condition number is the ratio of the largest to smallest eigenvalue of its aggregate positive-definite matrix.The local quadratic matrices are diagonal and positive-definite.
  • Experimental design: Performance is compared over undirected and directed graphs across different condition numbers, with algorithm parameters hand-tuned for best performance.The same experimental procedure is used for both graph settings.
  • Small condition numbers: For small condition numbers, centralized gradient descent is fast while distributed algorithms experience relatively slower fusion over the graphs.The paper attributes the comparison to the relative effect of graph fusion at small condition numbers.
  • Large condition numbers: When the condition number is large, ABm with momentum outperforms centralized gradient descent.The paper notes that this agrees with existing heavy-ball literature.

C. ABm and Average-Consensus

The paper evaluates ABm-C with momentum against surplus consensus without momentum for average-consensus on a directed graph. Grid search selects parameters by minimizing the spectral convergence factors, and the numerical comparison may show acceleration.

  • Convergence analysis: The analysis compares powers of the system matrices after subtracting their limiting matrices to characterize convergence speed.This construction is stated for both surplus consensus and the augmented ABm-C system.
  • Parameter selection: Grid search chooses parameters that minimize the spectral radii of the corresponding transient system matrices.The selected parameters are α* for surplus consensus and α̃*, β̃* for the augmented system.
  • Numerical result: The minimum spectral radius for the augmented system may be smaller than that of surplus consensus, indicating possible acceleration by momentum.The convergence-speed comparison is performed over directed graph G2.
  • Average-consensus comparison: The average-consensus comparison evaluates ABm-C with momentum against surplus consensus without momentum on a directed graph.The two methods are shown in Fig. 5.

VII. CONCLUSIONS

The conclusion presents AB as a unifying framework for distributed optimization and proposes ABm, which adds heavy-ball momentum and applies to undirected and directed graphs. ABm also yields an average-consensus algorithm with potential momentum-based acceleration.

  • Conclusions: AB uses both row-stochastic and column-stochastic weights, removing the need for doubly-stochastic weights and eigenvector estimation.A state transformation based on the non-1_n eigenvector connects AB to several earlier algorithms.
  • Conclusions: ABm combines AB with a heavy-ball-type momentum term for distributed optimization.The paper identifies this as its distributed heavy-ball method.
  • Conclusions: The framework is naturally applicable to both undirected and directed graphs.This follows from its simultaneous use of row- and column-stochastic weights.
  • Conclusions: ABm subsumes a novel average-consensus algorithm that unifies earlier attempts over directed graphs, with potential acceleration from momentum.The conclusion states this as a special case of ABm.
Loading 1808.02942v2…