PaperlayerView exact revision on arXiv

Source-linked AI summary

DSA: Decentralized Double Stochastic Averaging Gradient Algorithm

Aryan Mokhtari, Alejandro Ribeiro

arXiv:1506.04216v1math.OC

TL;DR

The paper addresses decentralized optimization of distributed machine-learning objectives, where stochastic updates reduce computation but existing decentralized stochastic methods converge sublinearly. It proposes DSA, which combines local stochastic averaging gradients with two-iterate descent information, and shows linear convergence in expectation under strong convexity and Lipschitz-gradient assumptions. Experiments report favorable convergence and training-vector-processing comparisons against stochastic and deterministic alternatives.

  • Problem

    Distributed machine-learning objectives require decentralized optimization with lower-cost stochastic updates, but existing decentralized stochastic methods converge sublinearly.

  • Method

    DSA uses local stochastic averaging gradients and information from two consecutive iterates within a neighbor-communication decentralized algorithm.

  • Results

    DSA converges linearly to the optimum in expectation under strong convexity and Lipschitz continuity, while local iterates converge almost surely; experiments report favorable comparisons with stochastic and deterministic alternatives.

  • Takeaways & Limitations

    DSA is reported as the only decentralized stochastic algorithm in the experiments to reach linear convergence and to outperform decentralized stochastic alternatives in required iterations.

  • Takeaways & Limitations

    The stochastic design has a relatively large initialization cost, and convergence speed decreases as the graph condition number, local-function condition number, or functions per node increase.

Abstract

from arXiv · show

This paper considers convex optimization problems where nodes of a network have access to summands of a global objective. Each of these local objectives is further assumed to be an average of a finite set of functions. The motivation for this setup is to solve large scale machine learning problems where elements of the training set are distributed to multiple computational elements. The decentralized double stochastic averaging gradient (DSA) algorithm is proposed as a solution alternative that relies on: (i) The use of local stochastic averaging gradients. (ii) Determination of descent steps as differences of consecutive stochastic averaging gradients. Strong convexity of local functions and Lipschitz continuity of local gradients is shown to guarantee linear convergence of the sequence generated by DSA in expectation. Local iterates are further shown to approach the optimal argument for almost all realizations. The expected linear convergence of DSA is in contrast to the sublinear rate characteristic of existing methods for decentralized stochastic optimization. Numerical experiments on a logistic regression problem illustrate reductions in convergence time and number of feature vectors processed until convergence relative to these other alternatives.

1. Introduction

The paper targets decentralized machine-learning optimization when large training sets are distributed across network nodes, while seeking lower per-iteration cost without sacrificing linear convergence. It proposes DSA, analyzes its convergence, and evaluates it against stochastic and deterministic alternatives.

  • Motivation: Large training sets are distributed across network nodes, with each node storing a moderate number of samples and accessing local objective summands.The resulting problem requires nodes to optimize a global cost using local functions and neighbor communication.
  • Motivation: Existing decentralized methods either require costly full local-gradient evaluations or reduce iteration cost through stochastic approximations that typically converge sublinearly.The cited stochastic rate is O(1/t), even when the corresponding deterministic method converges linearly.
  • Method: DSA combines stochastic averaging gradients with information from two consecutive iterates in a decentralized algorithm using neighbor communication.Its design replaces the gradients in EXTRA with stochastic averaging gradients and interprets the method through a stochastic saddle-point framework.
  • Convergence: Strong convexity and Lipschitz continuity of local instantaneous-function gradients yield linear convergence in expectation for DSA's Lyapunov function and local iterates.The paper also establishes convergence of all local variables to the optimum with probability 1.
  • Experiments: Numerical experiments on logistic regression with a synthetic dataset compare DSA with stochastic and deterministic alternatives.The experiments evaluate convergence behavior, processed training vectors, and different network topologies.

2. Decentralized Double stochastic averaging gradient

DSA extends EXTRA with stochastic averaging gradients for decentralized optimization, using neighbor communication and differences of consecutive stochastic gradients to reduce computation while retaining exact convergence properties under stated conditions.

  • Each node maintains a local variable and communicates with neighboring nodes so connected-network consensus makes all local variables coincide.The decentralized formulation minimizes local objectives while enforcing agreement among neighboring variables.
  • Stochastic gradients lower per-iteration computation by evaluating one instantaneous function, but ordinary stochastic descent has sublinear O(1/t) convergence even when its deterministic counterpart is linear.DSA addresses the difference between stochastic and deterministic descent directions by averaging stored gradients.
  • Stochastic averaging gradients reduce noise by replacing one entry in a stored table of instantaneous gradients at each iteration and averaging the table entries.The table stores the latest evaluation point for each instantaneous function; initialization requires evaluating all stored gradients, creating a relatively large initial cost.
  • DSA’s update requires neighbor iterates, consecutive stochastic averaging gradients, uniform random index selection, and maintenance of the local gradient table.The first iteration uses a special initialization update, while later iterations apply the DSA recursion summarized in Algorithm 1.
  • DSA is a decentralized stochastic algorithm that replaces EXTRA’s local gradients with stochastic averaging gradients and uses two consecutive iterates.It is decentralized through neighbor-only communication, stochastic because one randomly selected local function is evaluated per iteration, and double because it uses consecutive iterates.
  • The weight matrices must satisfy symmetry, null-space, spectral-ordering, and positive-definiteness conditions, while stochastic averaging gradients are unbiased estimates of local gradients.These conditions support the consensus and convergence interpretation inherited from EXTRA.

3. Convergence analysis

Under strong convexity and Lipschitz-gradient assumptions, DSA's Lyapunov function converges linearly in expectation, while local iterates converge almost surely to the optimum.

  • Assumptions: Strong convexity and Lipschitz continuity of instantaneous local functions imply corresponding properties for local and aggregate objectives.
  • Lyapunov analysis: DSA's primal-dual iterates are analyzed through a Lyapunov function combining weighted primal-dual error with the auxiliary sequence p_t.
  • Lyapunov analysis: The stochastic averaging gradient error is bounded using the auxiliary sequence and the optimality gap, enabling a recursive convergence bound.
  • Expected convergence: A constant 0 < δ < 1 makes the Lyapunov function contract in expectation, establishing linear convergence under the stated assumptions.
  • Expected convergence: The convergence constant depends on curvature, gradient smoothness, network spectra, local sample counts, and the stepsize, and worsens with graph and function condition numbers.
  • Almost-sure convergence: All local iterates converge almost surely to the optimal argument at least at order O(1/t), slower than the linear expected rate.

4. Numerical analysis

Numerical experiments apply DSA to distributed regularized logistic regression and compare it with deterministic and stochastic decentralized methods across network topologies.

  • Experimental setup: The experiment distributes logistic-regression samples across nodes, represents each local objective as an average of instantaneous functions, and applies DSA.
  • Experimental setup: The synthetic experiment uses Q = 500 samples, p = 2 features, λ = 10^-4 regularization, and edge probability p_c = 0.3.
  • Algorithm comparison: DSA outperforms deterministic alternatives when convergence is measured by the number of processed feature vectors.
  • Algorithm comparison: Figure 2 compares DSA with DGD, EXTRA, stochastic EXTRA, and decentralized SAGA using relative distance to optimality versus iterations.
  • Algorithm comparison: DSA is the only stochastic algorithm reported to achieve linear convergence, while DGD, stochastic EXTRA, and decentralized SAGA converge only to neighborhoods with constant stepsizes.
  • Network topologies: More connected topologies yield faster DSA convergence; the complete graph reaches e_t = 10^-6 in 160 iterations, versus 210 and 280 for random graphs.

5. Conclusions

DSA combines stochastic averaging gradients with information from consecutive iterates for decentralized optimization. Under stated convexity and smoothness assumptions, its iterates converge almost surely, while experiments show favorable convergence behavior against stochastic and deterministic alternatives.

  • 5. Conclusions: DSA uses stochastic averaging gradients and mixes two consecutive iterates to determine descent directions.The method targets decentralized problems whose local functions are averages of instantaneous functions.
  • 5. Conclusions: Under strong convexity of local instantaneous functions and Lipschitz continuity of their gradients, DSA has linear convergence in expectation.
  • 5. Conclusions: Each local iterate almost surely converges to the optimal argument.
  • 5. Conclusions: In logistic regression experiments, DSA is the only stochastic decentralized algorithm reported to reach linear convergence.
  • 5. Conclusions: DSA outperforms decentralized stochastic alternatives in required iterations and converges faster than deterministic alternatives by feature vectors processed.

Appendix A. Proof of Lemma 3

The proof of Lemma 3 bounds gradient-related terms using Lipschitz continuity, uniform sampling, variance decomposition, and strong convexity. These substitutions establish the lemma's claimed inequality.

  • Appendix A. Proof of Lemma 3: Lipschitz continuity of instantaneous gradients supplies upper bounds for the relevant gradient-difference terms.
  • Appendix A. Proof of Lemma 3: Summing the per-function inequalities and dividing by qn converts instantaneous-function bounds into local-objective bounds.
  • Appendix A. Proof of Lemma 3: Uniform sampling of fn,itn permits replacing sampled-function expressions with conditional expectations.
  • Appendix A. Proof of Lemma 3: The proof concludes by substituting the derived upper and lower bounds into the preceding inequality and simplifying.
  • Appendix A. Proof of Lemma 3: Strong convexity provides a lower bound on gradient differences that yields the claim in (34).

Appendix B. Proof of Lemma 4

The proof of Lemma 4 controls the recursion through smoothness, conditional unbiasedness, variance bounds, and strong convexity. Algebraic substitutions then establish the stated claim.

  • Appendix B. Proof of Lemma 4: Lipschitz continuity relates aggregate-gradient differences to the iterate difference and initiates the recursion bound.
  • Appendix B. Proof of Lemma 4: Conditional unbiasedness, E[ĝt | Ft] = ∇f(xt), eliminates the corresponding conditional-expectation cross term.
  • Appendix B. Proof of Lemma 4: Young's inequality bounds the cross term involving xt+1 − xt and the gradient-estimation error.
  • Appendix B. Proof of Lemma 4: Strong convexity supplies the gradient-difference lower bound needed to prove the claim in (36).

Appendix C. Proof of Lemma 5

The proof of Lemma 5 analyzes the two possible updates of each stored instantaneous gradient under uniform index selection. Strong convexity and aggregation then produce the claimed bound.

  • Appendix C. Proof of Lemma 5: Each auxiliary vector yt+1_n,i takes its previous value or yt+1_n with probabilities 1 − 1/qn and 1/qn.
  • Appendix C. Proof of Lemma 5: The same two-case distribution applies to the corresponding random instantaneous function evaluated at the updated auxiliary vector.
  • Appendix C. Proof of Lemma 5: Averaging the conditional expectations over all instantaneous functions yields the required local relation.
  • Appendix C. Proof of Lemma 5: Strong convexity makes the two terms in the intermediate bound non-negative, while qmin ≤ qn ≤ qmax controls their aggregation.
  • Appendix C. Proof of Lemma 5: Summing across nodes and rewriting the aggregate sequences establishes the claim in (37).

Appendix D. Proof of Theorem 6

The proof establishes bounds on the auxiliary sequence and uses them to show linear convergence under a stepsize condition. It derives the result through eigenvalue bounds, norm inequalities, and conditional expectations.

  • Appendix D. Proof of Theorem 6: Lemma 10 bounds the squared norm ∥v_t−v∗∥2 using the smallest non-zero and largest eigenvalues of ˜Z−Z.The bound assumes Assumptions 1, 2, and 3.
  • Appendix D. Proof of Theorem 6: The proof combines norm inequalities and eigenvalue bounds to upper-bound the auxiliary error terms and their conditional expectations.The argument repeatedly applies ∥a+b∥2 ≤ 2∥a∥2 + 2∥b∥2 and uses Γ′ as the largest eigenvalue of ˜Z−Z.
  • Appendix D. Proof of Theorem 6: Theorem 6’s linear convergence claim follows once the sufficient inequalities and the δ condition are established.The proof explicitly states that inequality (94) implies the validity of inequalities (93) and (40).
  • Appendix D. Proof of Theorem 6: The proof links the auxiliary sequence to the primal error through the maximum eigenvalue of ˜Z and bounds involving the objective function.These substitutions transform the sufficient condition into a bound involving ∥x_t−x∗∥2 and f(x_t)−f(x∗).
  • Appendix D. Proof of Theorem 6: The resulting sufficient conditions ensure that the convergence factor δ satisfies 0 < δ < 1, validating the linear convergence claim.Positivity follows from the conditions on η, α, and c, while δ ≤ 1/2.

Appendix E. Proof of Theorem 8

The proof constructs nonnegative stochastic processes satisfying a supermartingale convergence theorem. This yields almost-sure summability of the primal error and convergence to zero.

  • Appendix E. Proof of Theorem 8: The proof defines stochastic processes ζ_t and β_t to build a supermartingale sequence from the relationship in Theorem 6.Both processes are nonnegative and are considered with respect to a sigma-algebra measuring ζ_t, β_t, and u_t.
  • Appendix E. Proof of Theorem 8: The supermartingale convergence theorem implies that ζ_t converges almost surely and that the sum of β_t is almost surely finite.The nonnegativity of the relevant sequences supplies the theorem’s conditions.
  • Appendix E. Proof of Theorem 8: The finite sum of β_t, together with the eigenvalue lower bound γ, implies that the weighted sum of squared primal errors is almost surely finite.The proof relates ∥u_t−u∗∥2 to γ∥x_t−x∗∥2.
  • Appendix E. Proof of Theorem 8: With positive δ and γ, ∥x_t−x∗∥2 is almost surely summable and converges to zero with probability one at least at order O(1/t).This establishes the almost-sure convergence claim in Theorem 8.
Loading 1506.04216v1…