PaperlayerView exact revision on arXiv

Source-linked AI summary

A general framework for decentralized optimization with first-order methods

Ran Xin, Shi Pu, Angelia Nedić, Usman A. Khan

arXiv:2009.05837v1cs.LGcs.MAcs.SYeess.SYmath.OCstat.ML

TL;DR

Decentralized optimization seeks to minimize a finite sum across networked nodes using locally available data. The article organizes first-order methods in a framework for directed and undirected networks and discusses stochastic methods combining gradient tracking with variance reduction. It reports that this combination recovers exact linear convergence in the stated smooth, strongly convex setting.

  • Problem

    Decentralized optimization must combine information from nodes holding local data to minimize a global cost without a central coordinator.

    Source: §I · p. 1

  • Method

    The article presents AB/Push-Pull as a unifying framework for gradient-tracking methods and discusses adding variance reduction to tracking for stochastic optimization.

    Source: §IX · p. 15

  • Results

    Adding variance reduction to gradient tracking recovers exact linear convergence for decentralized stochastic methods in the stated smooth, strongly convex setting.

    Source: §IX · p. 15

  • Takeaways & Limitations

    The AB/Push-Pull framework relates much of the existing gradient-tracking work, while numerical results illustrate the convergence behavior and performance of the methods.

    Source: §IX · p. 15

    Formal analysis of SAB and the described row- and column-stochastic extensions remains open.

    Source: C. Decentralized Stochastic… · p. 12

Abstract

from arXiv · show

Decentralized optimization to minimize a finite sum of functions over a network of nodes has been a significant focus within control and signal processing research due to its natural relevance to optimal control and signal estimation problems. More recently, the emergence of sophisticated computing and large-scale data science needs have led to a resurgence of activity in this area. In this article, we discuss decentralized first-order gradient methods, which have found tremendous success in control, signal processing, and machine learning problems, where such methods, due to their simplicity, serve as the first method of choice for many complex inference and training tasks. In particular, we provide a general framework of decentralized first-order methods that is applicable to undirected and directed communication networks alike, and show that much of the existing work on optimization and consensus can be related explicitly to this framework. We further extend the discussion to decentralized stochastic first-order methods that rely on stochastic gradients at each node and describe how local variance reduction schemes, previously shown to have promise in the centralized settings, are able to improve the performance of decentralized methods when combined with what is known as gradient tracking. We motivate and demonstrate the effectiveness of the corresponding methods in the context of machine learning and signal processing problems that arise in decentralized environments.

I. INTRODUCTION

The article surveys decentralized first-order optimization, where networked nodes use local data and peer-to-peer communication to minimize a shared finite-sum cost. It presents AB/Push-Pull as a framework spanning directed and undirected networks, then discusses stochastic methods and variance reduction.

I. INTRODUCTION

  • Gradient descent repeatedly steps against the gradient; the article focuses on decentralized methods for smooth, strongly convex problems while noting extensions to smooth non-convex problems.The article presents smooth, strongly convex problems to illustrate its technical ideas.Source: §I · pp. 1–2
  • Decentralized first-order methods combine local gradient computation with information exchange so nodes can estimate a global minimizer without sharing raw data.The article focuses on networks without a central coordinator, motivated in part by privacy and communication constraints.Source: §I · p. 1
  • AB/Push-Pull combines row- and column-stochastic weights to achieve linear convergence on smooth, strongly convex problems over directed or undirected networks.The framework unifies gradient-tracking methods and subsumes several non-trivial average-consensus algorithms as special cases.Source: §I · p. 2
  • For decentralized stochastic methods, gradient tracking alone does not ensure the same performance improvement; combining it with variance reduction can yield exact linear convergence for smooth, strongly convex problems.The article notes that existing directed-network results are rather restrictive.Source: §I · p. 2

A. Literature Survey

  • Prior work spans doubly stochastic weights for undirected networks, row- or column-stochastic approaches for directed networks, and online or finite-sum stochastic methods.Some directed methods use push-sum and eigenvector estimates; the article also situates its coverage among second-order, primal-dual, and imperfect-communication approaches.Source: A. Literature Survey · p. 2

B. Outline of the Article

  • The article proceeds from problem formulation and preliminaries through decentralized gradient methods and AB/Push-Pull, then stochastic methods, numerical studies, and conclusions.Its outline distinguishes stochastic tracking alone from tracking combined with variance reduction.Source: B. Outline of the Article · p. 2

C. Notation

  • Notation conventions specify scalar, vector, and matrix styles; vector elements, norms, limits, Kronecker products, and spectral quantities.The identity and all-ones vectors are denoted by I_p and 1_p.Source: C. Notation · p. 3

II. PROBLEM FORMULATION AND MOTIVATION

  • The problem formulation minimizes a finite sum whose local functions remain at their respective nodes, with peer-to-peer communication and no central coordinator.The article identifies privacy preservation and data parallelism as properties of this paradigm.Source: §II · p. 3

2) Linear models for binary classification

The section illustrates decentralized learning with binary classification and empirical risk minimization, then reviews convexity and smoothness assumptions used in the article’s analysis.

2) Linear models for binary classification

  • Users can train a shared linear classifier from locally held face images without moving personal data to a central server.The example contrasts a classifier trained across users’ images with local classifiers whose performance depends on local image quantity and quality.Source: 2) Linear models for binary… · p. 3

3) Empirical risk minimization

1) Convex functions

  • Strong convexity ensures a global minimum exists and is unique, while smoothness supplies a quadratic upper bound on the function.The article assumes local functions are smooth and strongly convex unless stated otherwise, while also citing extensions to smooth, possibly non-convex functions.Source: 1) Convex functions · p. 4

2) Communication Graph

The section defines communication graphs and weight matrices, then explains decentralized gradient descent as a combination of local descent and network information fusion. For undirected connected graphs, doubly stochastic weights support agreement and global optimality, with a rate–accuracy tradeoff under constant steps.

2) Communication Graph

  • A directed graph may have ordered communication links, and is strongly connected when a directed path exists between every pair of nodes.The section also defines incoming and outgoing neighbors and associates positive matrix weights with graph edges.Source: 2) Communication Graph · p. 4

3) Nonnegative matrices

  • Row-stochastic matrices have rows summing to one, column-stochastic matrices have columns summing to one, and doubly stochastic matrices satisfy both conditions.The section also defines irreducibility and primitivity in terms of the graph induced by a nonnegative matrix.Source: 3) Nonnegative matrices · p. 4

III. DECENTRALIZED GRADIENT DESCENT

  • A decentralized optimization method must achieve both agreement among nodes and optimality at the global minimum.The section describes consensus protocols used for undirected and directed graphs.Source: §III · p. 5

A. Decentralized gradient descent: Undirected graphs

  • DGD combines weighted estimates from neighboring nodes with local gradients, using a doubly stochastic weight matrix on undirected connected graphs.With zero step-size, the iteration reduces to average consensus.Source: A. Decentralized gradient descent:… · p. 5
  • DGD with decaying step-sizes converges sublinearly to the exact global minimum, while a constant step-size gives linear convergence to an O(alpha)-accurate solution.A larger constant step-size brings faster convergence but worse accuracy.Source: A. Decentralized gradient descent:… · p. 5

B. Decentralized gradient descent: Directed graphs

On directed graphs, using only row- or column-stochastic weights can prevent agreement on the global minimizer. Gradient-Push adds an iteration to estimate the eigenvector needed to correct the column-stochastic imbalance.

B. Decentralized gradient descent: Directed graphs

1) DGD with column stochastic weights

  • Gradient-Push estimates the relevant eigenvector through an additional iteration; with decaying step-sizes, the corrected iterates intuitively achieve agreement while preserving optimality.The scaled iterates under column-stochastic weights converge to the average of initial states, but nodes do not agree without the correction.Source: 1) DGD with column stochastic weights · pp. 5–6

2) DGD with row stochastic weights

With row-stochastic weights on directed graphs, DGD can agree on a weighted-cost minimizer rather than the global one; eigenvector correction addresses this imbalance but requires additional estimation. Gradient tracking and AB/Push-Pull extend decentralized optimization to constant-step linear convergence, including on directed networks.

2) DGD with row stochastic weights

  • Dividing each local gradient by its row-stochastic matrix’s eigenvector entries corrects convergence toward a weighted-cost minimizer, but requires separately estimating the eigenvector.The method is termed DGD-RS [106]; nodes may need unique identifiers for the estimation iterations, and eigenvector estimation may slow convergence, especially on poorly connected graphs.Source: 2) DGD with row stochastic weights · p. 6

IV. THE AB/PU S H-PU L L FRAMEWORK

  • With decaying step-sizes, the discussed decentralized algorithms converge sub-linearly to the global minimizer; with constant step-sizes, they converge linearly to a sub-optimal solution.The global minimizer is generally not a fixed point for constant-step DGD because it need not minimize each local cost.Source: §IV · p. 6
  • Gradient tracking replaces each node’s local gradient with an iterative tracker of the global gradient, overcoming steady-state error while retaining a constant step-size.GT-DGD linearly converges to the global minimum for smooth, strongly convex problems, using doubly stochastic weights and therefore requiring an undirected or balanced graph.Source: §IV · pp. 6–7
  • AB/Push-Pull uses row-stochastic weights for agreement and column-stochastic weights for optimality, avoiding the need for doubly stochastic weights.For smooth, strongly convex local costs, it converges linearly to the global minimum on directed or undirected graphs [14],.Source: §IV · p. 7
  • AB/Push-Pull permits distinct constant step-sizes across nodes when their maximum is positive and sufficiently small; other nodes’ step-sizes may be zero.In this case, the method can operate in a leader-follower mode, with one node descending and the others following its state.Source: §IV · p. 7

A. Analysis

The analysis establishes AB/Push-Pull convergence by tracking agreement, optimality, and gradient-tracking errors in norms suited to its row- and column-stochastic weights. It then uses a linear error system and shows that a sufficiently small positive step-size makes its spectral radius less than one.

A. Analysis

  • Ordinary Euclidean contraction arguments do not generally apply to row- or column-stochastic weights, and the state and gradient-tracking dynamics are coupled.The analysis instead uses weighted norms in which the respective primitive matrices contract, then writes the errors as a linear time-invariant system.Source: A. Analysis · p. 7
  • The proof tracks three errors: node disagreement, distance from the network average to the global minimizer, and gradient-tracking disagreement.These errors are expressed using norms associated with the row-stochastic matrix A and column-stochastic matrix B.Source: A. Analysis · pp. 7–8
  • A sufficiently small positive step-size makes the error system’s spectral radius less than one, establishing linear convergence of AB/Push-Pull.At zero step-size, two eigenvalues are strictly below one; the eigenvalue at one decreases as the step-size increases slightly.Source: A. Analysis · p. 8

B. Architectures

AB/Push-Pull supports distinct communication graphs and unifies fully decentralized and semi-centralized architectures under shared connectivity conditions. Momentum extensions are described, but their acceleration over AB is supported numerically rather than by a complete theoretical analysis.

B. Architectures

  • AB/Push-Pull permits separate graphs GA and GB, subject to rooted-tree conditions that include a common root in GA and GB⊤.The stated condition is weaker than requiring both graphs to be strongly connected, while retaining topology restrictions.Source: B. Architectures · p. 8
  • A directed strongly connected network can use GA = GB = G for peer-to-peer operation, while a star arrangement yields a master–slave architecture.In the star example, node 1 receives information through GB and disseminates its state through GA; replacing nodes with subnets gives a semi-centralized structure.Source: B. Architectures · pp. 8–9, Figure 2 · p. 8

C. Acceleration

  • ABm converges linearly for sufficiently small step-size and momentum parameters, but acceleration over AB is shown only numerically.A detailed theoretical analysis remains open.Source: C. Acceleration · p. 9
  • For ABN, acceleration is shown numerically, while its analysis remains open; a closely related form with doubly stochastic weights has analytically shown acceleration.The related form is studied in, whereas ABN's numerical acceleration is reported in.Source: C. Acceleration · p. 9

V. AB/PU S H-PULL: A GENERAL FRAMEWORK

AB/Push-Pull provides a framework that relates decentralized gradient-tracking and consensus methods through choices of network weights and state transformations. The framework also yields average consensus, including a form related to surplus consensus.

V. AB/PU S H-PULL: A GENERAL FRAMEWORK

  • GT-DGD is a special case of AB/Push-Pull with doubly stochastic weights, and DGD follows with a doubly stochastic matrix and identity tracker weights.These relationships are stated as examples of AB/Push-Pull's unifying framework.Source: §V · p. 9

A. GT-DGD with column stochastic weights

  • A state transformation embeds methods using only column-stochastic weights in AB/Push-Pull, but their implementation requires estimating an unknown eigenvector.The described transformed methods include ADDOPT and Push-DIGing, which add push-sum consensus to GT-DGD over directed graphs,.Source: A. GT-DGD with column stochastic weights · p. 9

B. GT-DGD with row stochastic weights

C. Average consensus

  • With the specified local costs, AB/Push-Pull's consensus form converges linearly to the average and is related to surplus consensus by a state transformation.Related GT-DGD, ADDOPT/Push-DIGing, and FROST variants also yield average consensus with doubly stochastic, column-stochastic, or row-stochastic weights, respectively.Source: C. Average consensus · p. 10

VI. DECENTRALIZED STOCHASTIC OPTIMIZATION

Decentralized stochastic optimization addresses settings where nodes use imperfect gradients or sample from local data batches. The section reviews SGD and DSGD, including their convergence behavior and the effects of network connectivity and data heterogeneity.

VI. DECENTRALIZED STOCHASTIC OPTIMIZATION

  • Sampling a small subset of local data reduces the per-iteration gradient computation compared with computing each node's full local gradient.The passage identifies high-dimensional data and nontrivial cost functions as settings where computing all local component gradients can be taxing.Source: §VI · p. 10
  • SGD with decaying step-sizes requires O(κϵ^-1) component-gradient evaluations for an ϵ-accurate solution, independent of sample size.Here κ = ℓ/µ; the comparison states that full-batch GD requires O(mκ lnϵ^-1) evaluations.Source: §VI · pp. 10–11

A. Decentralized Stochastic Gradient Descent (DSGD):

  • DSGD with a constant step-size has linear convergence up to a steady-state error under smooth, strongly convex local costs.The stated result assumes the network weight matrix is doubly stochastic; the graph is therefore undirected or weight-balanced directed.Source: A. Decentralized Stochastic Gradient… · p. 11
  • With decaying step-sizes, DSGD asymptotically matches centralized minibatch SGD at a network-independent rate, while network topology affects transient iterations.With an appropriate constant step-size, DSGD also achieves linear convergence, as stated in the cited comparison.Source: A. Decentralized Stochastic Gradient… · p. 11
  • DSGD's steady-state error has additional bias terms tied to network connectivity, and one term also depends on local–global solution deviation.That deviation can be large when node data distributions are heterogeneous; this motivates adding gradient tracking.Source: A. Decentralized Stochastic Gradient… · p. 11

B. DSGD with Gradient Tracking (GT-DSGD):

GT-DSGD adds gradient tracking to decentralized stochastic gradient descent, with node descent directions tracking average local stochastic gradients. Its reported trade-offs differ by step-size regime and data heterogeneity.

B. DSGD with Gradient Tracking (GT-DSGD):

  • Under a constant step-size, GT-DSGD's mean-squared error decays linearly at rate (1 − O(µα))^k up to a steady-state error.The stated conditions include ℓ-smooth component functions and a µ-strongly convex global cost.Source: B. DSGD with Gradient Tracking (GT-DSGD) · p. 11
  • With decaying step-sizes, GT-DSGD matches centralized minibatch SGD's convergence rate after a finite number of transient iterations.The cited comparison discusses the transient time relative to DSGD.Source: B. DSGD with Gradient Tracking (GT-DSGD) · p. 11
  • With a constant step-size, GT-DSGD's steady-state error lacks DSGD's dependence on b, but has worse network dependence: O((1−λ)^-3) versus O((1−λ)^-2).The passage says GT-DSGD may be preferable when data distributions across nodes are substantially heterogeneous.Source: B. DSGD with Gradient Tracking (GT-DSGD) · p. 11

C. Decentralized Stochastic Optimization: Directed Graphs

The section describes stochastic first-order methods for directed networks and variance-reduction methods combined with gradient tracking. It highlights open analysis questions, convergence properties, and implementation trade-offs.

C. Decentralized Stochastic Optimization: Directed Graphs

  • SAB combines stochastic gradients with AB/Push-Pull’s row- and column-stochastic weights for directed graphs.It converges linearly with a constant step-size up to a steady-state error.Source: C. Decentralized Stochastic… · p. 12
  • Formal analysis of SAB and related row- and column-stochastic extensions remains open.The extensions are described as having promise of improved performance over SGP, but this comparison is not formally analyzed.Source: C. Decentralized Stochastic… · p. 12
  • The stochastic methods discussed also apply to online problems without finite-sum local costs.In that setting, each local stochastic gradient is a noisy sample of the true gradient.Source: C. Decentralized Stochastic… · p. 12

VII. DECENTRALIZED STOCHASTIC FIRST-ORDER METHODS WITH VARIANCE REDUCTION

  • GT-VR combines local variance reduction with global gradient tracking to address GT-DSGD’s persistent stochastic-gradient variance.The framework uses local gradient estimation, tracking across neighboring nodes, and descent along the tracked direction.Source: §VII · p. 13
  • In the big-data regime M ≈ m ≥ κ^2/(1−λ2), GT-SAGA has O(M ln ϵ^-1) complexity, independent of the network, and is n times faster than centralized SAGA.The paper identifies this as non-asymptotic linear speedup.Source: §VII · p. 13
  • GT-SAGA converges linearly to the optimum with a constant step-size and without a steady-state error.Its local variance-reduction scheme removes the persistent-error issue described for stochastic gradients.Source: §VII · p. 13
  • GT-SAGA’s gradient tables cost O(pmi) storage per node, while GT-SVRG avoids that storage at the expense of additional network synchronization.The framework offers different performance and implementation trade-offs.Source: §VII · p. 13
  • GT-SARAH is reported to achieve optimal, network-independent performance for non-convex finite-sum problems in a certain practical regime.The paper also notes Push-SAGA as an extension of GT-SAGA to arbitrary directed graphs using push-sum consensus.Source: §VII · p. 13

VIII. NUMERICAL EXPERIMENTS

The section compares the performance of decentralized first-order methods using linear and logistic regression problems.

VIII. NUMERICAL EXPERIMENTS

  • The section compares the performance of the decentralized first-order methods discussed in the article.The passage does not report comparison outcomes.Source: §VIII · p. 14
  • Linear regression is one of the problems used for the comparison.Source: §VIII · p. 14
  • Logistic regression is also used as a comparison problem.Source: §VIII · p. 14

1) Decentralized state estimation in sensor networks

The sensor-estimation and logistic-regression examples compare decentralized methods on undirected and directed networks. The article concludes that AB/Push-Pull unifies much gradient-tracking work, while variance reduction restores exact linear convergence for stochastic methods.

1) Decentralized state estimation in sensor networks

2) Decentralized training over multiple machines

  • The training example distributes 11,968 MNIST images evenly across nodes on balanced directed exponential graphs; with 8 nodes, each has 1,496 images.These graphs admit doubly stochastic weights.Source: 2) Decentralized training over… · p. 15, Figure 6 · p. 15
  • On the directed exponential graph with 8 nodes, GT-SAGA exhibits consistent fast linear convergence to the global minimum and outperforms the other methods.The comparison includes deterministic and stochastic methods with constant step-sizes.Source: 2) Decentralized training over… · p. 15, Figure 7 · p. 15
  • Fig. 8 reports linear-speedup comparisons: DSGD and GT-DSGD versus SGD at 10−3, and GT-SAGA versus SAGA at 10−15.The decentralized methods evaluate n component gradients in parallel per iteration, compared with one for centralized SGD and SAGA.Source: Figure 8 · p. 15, 2) Decentralized training over… · p. 15

IX. CONCLUSIONS

  • The article presents AB/Push-Pull as a unifying framework for much gradient-tracking work and variance reduction as restoring exact linear convergence for stochastic methods.The article also provides numerical results illustrating the methods’ convergence behavior and performance.Source: §IX · p. 15
Loading 2009.05837v1…