PaperlayerView exact revision on arXiv

Source-linked AI summary

Geometrically Convergent Distributed Optimization with Uncoordinated Step-Sizes

Angelia Nedić, Alex Olshevsky, Wei Shi, César A. Uribe

arXiv:1609.05877v1math.OCeess.SYstat.ML

TL;DR

Distributed optimization methods can require identical step-sizes even when they converge geometrically. This paper analyzes ATC-DIGing with agent-specific step-sizes and shows geometric convergence, with evidence that ATC can outperform the original DGD structure.

  • Problem

    DIGing’s geometric convergence has required identical step-sizes across agents, motivating analysis of the ATC variation under uncoordinated step-sizes.

  • Method

    The paper studies the convergence rate of ATC-DIGing for distributed optimization with uncoordinated step-sizes.

  • Results

    ATC-DIGing converges geometrically even with constant uncoordinated step-sizes, and the analysis indicates faster convergence and lower sensitivity than DGD.

  • Takeaways & Limitations

    ATC-DIGing supports geometric convergence without requiring agents to coordinate their step-sizes.

Abstract

from arXiv · show

A recent algorithmic family for distributed optimization, DIGing's, have been shown to have geometric convergence over time-varying undirected/directed graphs. Nevertheless, an identical step-size for all agents is needed. In this paper, we study the convergence rates of the Adapt-Then-Combine (ATC) variation of the DIGing algorithm under uncoordinated step-sizes. We show that the ATC variation of DIGing algorithm converges geometrically fast even if the step-sizes are different among the agents. In addition, our analysis implies that the ATC structure can accelerate convergence compared to the distributed gradient descent (DGD) structure which has been used in the original DIGing algorithm.

I. INTRODUCTION

Distributed optimization aggregates agents’ private objectives over communication networks, but early methods were slow and linear rates required careful step-size selection. This paper studies ATC-DIGing and shows geometric convergence with uncoordinated step-sizes, including potentially larger step-sizes than the DGD structure.

  • Motivation: Earlier distributed sub-gradient methods were flexible across functions and graphs but considerably slow.Even for strongly convex functions, they require diminishing step-sizes, which prevents linear rates.
  • Motivation: Recent methods obtain linear convergence for strongly convex functions but require careful step-size selection.This motivates studying convergence under agent-specific step-sizes.
  • Related work: ATC-based distributed optimization methods had already shown convergence for smooth convex objectives with sufficiently small constant, uncoordinated step-sizes.This paper focuses on their convergence rate and provides an explicit geometric-rate result.
  • Contribution: ATC-DIGing achieves geometric convergence even when agents use uncoordinated step-sizes.The paper studies the Adapt-Then-Combine variation of Distributed Inexact Gradient Tracking.
  • Contribution: Under specific conditions, ATC-DIGing can use step-sizes as large as in the centralized case.The authors state that this improves the stability region of the ATC structure over the DGD structure used in original DIGing.

II. DEFINITIONS, ALGORITHM AND MAIN RESULT

The paper formulates ATC-DIGing over connected networks with smooth, strongly convex local objectives and agent-specific step-sizes. Its main theorem gives an explicit global geometric rate under bounded step-size heterogeneity and suitable mixing conditions.

  • Assumptions: The network assumptions require a connected graph and a doubly stochastic mixing matrix.These assumptions yield consensus contraction, with ∥x∥_Ł ≤ δ∥y∥_Ł for δ < 1.
  • Assumptions: The convergence analysis assumes differentiable local functions with Lipschitz-continuous gradients and aggregate strong convexity.At least one local strong-convexity parameter is nonzero, ensuring a unique optimum for the aggregate objective.
  • Algorithm: The algorithm uses a doubly stochastic weight matrix W and a diagonal step-size matrix D whose entries are agents’ step-sizes α_i.Each agent initializes y_0 = ∇f(x_0), and the algorithm maintains x_k and y_k variables.
  • Main result: The analysis permits uncoordinated agent step-sizes when their heterogeneity is sufficiently small.The step-size matrix condition is expressed through its condition number κ_D = α_max/α_min.
  • Main result: ATC-DIGing converges to the optimal solution at a global R-linear rate O(λ^k), with λ ∈ (0, 1).The theorem provides an explicit estimate for λ under the stated assumptions.

III. THE SMALL GAIN THEOREM FOR LINEAR RATES

The analysis uses a small gain theorem to organize cyclic bound relations among algorithmic variables and establish R-linear decay. A weighted ergodic norm and suitable step-size conditions ensure the gains contract and all quantities in the cycle decay geometrically.

  • III. THE SMALL GAIN THEOREM FOR LINEAR RATES: The small gain theorem is presented as a sufficient boundedness result for cyclic sequences with nonnegative gains whose product is below one.
  • III. THE SMALL GAIN THEOREM FOR LINEAR RATES: The small gain condition requires the product of the cycle gains to be less than one, achieved by choosing an appropriate step-size matrix D.
  • III. THE SMALL GAIN THEOREM FOR LINEAR RATES: The proof defines optimality and gradient-difference residuals, then establishes the required arrow relations through lemmas before invoking the small gain theorem.The residuals include q_k = x_k − x∗ and z_k = ∇f(x_k) − ∇f(x_{k−1}).
  • III. THE SMALL GAIN THEOREM FOR LINEAR RATES: The proof establishes R-linear decay by applying a small gain theorem to a cyclic set of bound relations among algorithmic variables.The relations are organized around the cycle depicted in Figure 1, and the resulting quantities decay at an R-linear rate.

A. The Inexact Gradient Descent on a Sum of Strongly Convex Functions

This section analyzes inexact gradient descent for a sum of strongly convex functions by modeling gradient errors as additive noise. Its main lemma provides an error bound for the resulting iterates and supports the final distributed convergence proof.

  • A. The Inexact Gradient Descent on a Sum of Strongly Convex Functions: The section introduces separate notation for the inexact-gradient analysis before restating the optimization problem and specifying assumptions on the component functions.
  • A. The Inexact Gradient Descent on a Sum of Strongly Convex Functions: The inexact gradient method models optimization updates with a step-size θ and additive noise e_k, while tracking distance from the global minimizer.The associated residual is r_k = ∥p_k − p∗∥_F.
  • A. The Inexact Gradient Descent on a Sum of Strongly Convex Functions: Lemma 6 gives an error bound for the inexact gradient method under the stated assumptions and tunable parameters β ≥ 2 and η > 0.
  • A. The Inexact Gradient Descent on a Sum of Strongly Convex Functions: The resulting error-bound lemma is used as the key ingredient for establishing the final arrow from the x- and y-related quantities to the optimality residual q.

B. Proof of Main Result

The main-result proof combines the small gain theorem with the previously established lemmas and imposes parameter restrictions so the required gain product is below one. Specific parameter choices then yield a concise convergence-rate bound.

  • B. Proof of Main Result: The proof of Theorem 2 combines the small gain theorem with Lemmas 5 and 7 to establish boundedness of the analysis quantities.
  • B. Proof of Main Result: Choosing β = 2L/μ̂ and η = 1, together with 0.5 ≤ λ < 1, produces a concise though potentially loose convergence-rate bound.
  • B. Proof of Main Result: Aggregating the conditions on α_max and λ completes the derivation of the stated result.

IV. DISCUSSION

The discussion presents explicit but potentially loose convergence-rate bounds for ATC-DIGing with uncoordinated step-sizes. It highlights trade-offs involving step-size heterogeneity, network connectivity, and the ATC structure, while noting simplifying assumptions and possible extensions.

  • The explicit rate estimate may be loose because alternative choices of β, η, αmax, and λ could yield tighter bounds.
  • ATC-DIGing has a faster convergence rate and is less sensitive to relevant conditions than the compared DIGing structure under specific conditions.
  • Uncoordinated step-sizes require geometric decay of the Frobenius norm ∥y_k∥F, adding steps to the small-gain argument and producing a worse bound than the identical-step-size case.
  • Theorem 2 trades tolerance to step-size heterogeneity against the achievable largest step-size.
  • When the graph is sufficiently well-connected and step-size heterogeneity is sufficiently small, the analysis permits a step-size as large as 1/(2L̄) and correspondingly fast convergence.
  • The analysis is conducted for time-invariant undirected graphs, although its ideas are expected to extend to Push-DIGing and other DIGing variants on time-varying directed graphs.

V. NUMERICAL TEST

Numerical experiments evaluate DIGing-family performance for decentralized Huber minimization over time-varying undirected graphs with heterogeneous step-sizes. The reported residual plots show geometric convergence under these conditions.

  • The test problem is decentralized Huber minimization over time-varying undirected graphs.
  • At each iteration and agent, the base step-size is perturbed by a uniform random variable over (0.5, 1.5).The resulting step-size varies across agents and iterations.
  • Monte Carlo simulations evaluate the heterogeneous step-size sequences for n = 12 agents.
  • The experiments demonstrate geometric convergence of DIGing families under uncoordinated step-sizes.The numerical results are illustrated through residual plots.
  • Figure 2 plots the residuals ∥xk−x∗∥F for the time-varying undirected-graph experiment.

VI. CONCLUSIONS AND FUTURE WORK

The paper concludes that ATC-DIGing converges geometrically to the optimum with constant, uncoordinated agent step-sizes and provides explicit rate estimates. It also reports reduced sensitivity to problem parameters relative to DGD under specific conditions, while leaving rate tightness and directed-graph extensions for future work.

  • ATC-DIGing converges geometrically to the optimal solution even when agents use constant uncoordinated step-sizes.
  • The analysis provides explicit convergence-rate estimates derived using the small gain theorem.
  • The paper makes no claim that its rate estimates are tight.
  • Under specific conditions, the obtained rate shows that ATC-DIGing is less sensitive to problem parameters than DGD.
  • Future work includes extending the analysis to time-varying directed graphs and studying rate tightness.

APPENDIX I

Appendix I develops proof steps for the convergence analysis, using Lipschitz continuity, the algorithmic relation, and invariant identities to establish the desired result.

  • The proof invokes Lipschitz continuity of f to establish an inequality used in the convergence analysis.
  • Combining the intermediate relations completes the proof.
  • An invariant identity links 1′yk−1′∇f(xk) to its initial value and uses 1′∇f(x∗) = 0.
  • The analysis repeatedly takes maxima over iteration ranges to derive uniform bounds.

APPENDIX II

Appendix II derives bounds through averaged inequalities, a two-case analysis, recursive relations, and choices of the tunable parameter ρk. The argument ultimately uses a time-invariant choice because the resulting bounds have the same order.

  • The proof averages inequalities over agents and relates the resulting quantities to the evolution of rk+1 and rk.
  • The derivation uses substitutions into a basic norm equality to obtain the key relation.
  • The sequence ρk is a tunable parameter that may vary over time when the noise term decays.
  • The analysis considers two possibilities for the relevant terms and combines both cases into a common inequality.
  • Recursively applying the inequality yields a bound that is then square-rooted to obtain the stated form.
  • A time-invariant choice ρk = ρ is used for conciseness because alternative choices produce bounds on λ with the same order.

APPENDIX III

The appendix compares DIGing and ATC-DIGing complexity restrictions, showing that ATC-DIGing permits a larger step-size range and performs better on well-connected graphs, although a worse rate is also derived in the current paper.

  • APPENDIX III: ATC-DIGing permits a larger step-size range than DIGing under the analyzed restrictions.The appendix states that condition (40) allows a larger range than condition (39), and gives an additional small-δ order comparison.
  • APPENDIX III: ATC-DIGing performs better when the graph is well-connected.
  • APPENDIX III: For small δ, the left-hand side of (40) is O(δ2α), whereas that of (41) is O(δα).
  • APPENDIX III: The current paper derives a worse rate in the comparison discussed in the appendix.
Loading 1609.05877v1…