PaperlayerView exact revision on arXiv

Source-linked AI summary

Accelerated Distributed Nesterov Gradient Descent

Guannan Qu, Na Li

arXiv:1705.07176v4math.OC

TL;DR

Distributed optimization seeks an x minimizing the average of local functions over a network. The paper proposes Acc-DNGD, using gradient estimation, and establishes sublinear, O(1/t^2), and linear convergence rates under progressively stronger objective assumptions.

  • Problem

    Distributed optimization seeks an x that minimizes the average of all local functions, motivating comparable rates for gradient-based methods.

  • Method

    The paper proposes Accelerated Distributed Nesterov Gradient Descent (Acc-DNGD), combining a gradient estimation scheme with distributed optimization.

  • Results

    Acc-DNGD achieves O(1/t^(1.4−ε)) for convex L-smooth functions, O(1/t^2) for a stated composition class, and O([1−C(μ/L)^(5/7)]^t) for μ-strongly convex L-smooth functions.

  • Takeaways & Limitations

    The reported rates are better than CGD and CGD-based distributed methods under the paper’s stated assumptions.

  • Takeaways & Limitations

    The method relies on a strong uniform-boundedness assumption that simple quadratic functions do not satisfy.

Abstract

from arXiv · show

This paper considers the distributed optimization problem over a network, where the objective is to optimize a global function formed by a sum of local functions, using only local computation and communication. We develop an Accelerated Distributed Nesterov Gradient Descent (Acc-DNGD) method. When the objective function is convex and $L$-smooth, we show that it achieves a $O(\frac{1}{t^{1.4-ε}})$ convergence rate for all $ε\in(0,1.4)$. We also show the convergence rate can be improved to $O(\frac{1}{t^2})$ if the objective function is a composition of a linear map and a strongly-convex and smooth function. When the objective function is $μ$-strongly convex and $L$-smooth, we show that it achieves a linear convergence rate of $O([ 1 - C (\fracμ{L})^{5/7} ]^t)$, where $\frac{L}μ$ is the condition number of the objective, and $C>0$ is some constant that does not depend on $\frac{L}μ$.

I. INTRODUCTION

The paper develops primal-only distributed Nesterov gradient methods using local computation and communication, targeting faster convergence with one communication step per gradient evaluation. Acc-DNGD improves over centralized gradient descent while partially narrowing the gap to centralized Nesterov methods.

  • Distributed optimization seeks to minimize the average of agents’ local convex functions using local communication and computation.
  • Primal-only gradient methods use local gradient evaluations, avoiding sub-optimization or dual-gradient computations that can limit applicability.
  • Existing consensus-based methods achieve sublinear rates for convex functions, while later methods obtain linear rates for strongly convex and smooth functions or centralized-gradient-like rates for convex and smooth functions.
  • The paper targets distributed Nesterov rates with only one communication step per gradient evaluation, avoiding the coordination and communication burden of inner consensus loops.
  • Acc-DNGD-SC achieves O([1 − C(μ/L)^5/7]^t) for μ-strongly convex and L-smooth functions, with C independent of L and μ.
  • Acc-DNGD-NSC achieves O(1/t^1.4−ε) for convex and L-smooth functions, improving to O(1/t^2) for linear-map compositions with strongly convex and smooth functions.

C. Our Algorithm: Accelerated Distributed Nesterov Gradient Descent (Acc-DNGD)

Acc-DNGD combines consensus-based distributed updates with a gradient estimator, yielding accelerated convergence under convex, structured, and strongly convex objectives.

  • Algorithm design: Acc-DNGD uses a consensus matrix W and local communication, with each agent maintaining primal variables plus a gradient-estimator sequence si(t).Agents exchange xi(t), vi(t), yi(t), and si(t) only with neighbors; si(t) estimates the average gradient.
  • Algorithm variants: The strongly convex variant Acc-DNGD-SC targets μ-strongly convex, L-smooth functions, while Acc-DNGD-NSC targets convex, L-smooth functions.The two variants use different initialization and step-size rules.
  • Convergence guarantees: O([1−C(μ/L)^5/7]^t) convergence is established for strongly convex and smooth objectives, with condition-number dependence strictly better than earlier analysis.The paper identifies L/μ as the condition number and reports an improved dependence relative to its conference version.
  • Convergence guarantees: O(1/t^1.4−ε) convergence holds for Acc-DNGD-NSC when β=0.6+ε and ε∈(0,1.4), for both the average and each agent’s objective value.The theorem states f(¯x(t))−f* and f(yi(t))−f* both achieve this rate.
  • Conditions and limitations: The NSC theorem’s step-size condition may be difficult to implement because the constant R can be unknown to individual agents.The authors use η=1/(2L) and t0=1 in simulations and conjecture convergence for β∈[0,0.6], supported numerically.
  • Convergence guarantees: O(1/t^2) convergence is obtained with fixed step size when each local function is a strongly convex and smooth function composed with a linear map.This follows from the local strong convexity property induced by the composition structure.

III. ALGORITHM DEVELOPMENT

The algorithm is designed to imitate centralized Nesterov descent despite consensus errors. Its gradient estimator avoids inner consensus loops, while the proof controls estimation and consensus errors to establish convergence.

  • Distributed imitation of centralized descent: The distributed updates do not exactly follow centralized Nesterov descent because agents experience consensus errors in their local variables and estimators.The proof first bounds consensus errors, then treats the distributed method as an inexact Nesterov method.
  • Distributed imitation of centralized descent: Nesterov methods can accumulate noise and diverge, so inexact adaptations require nontrivial error bounds and proof techniques.The paper frames its contribution as establishing convergence for Nesterov descent in a distributed setting.
  • Comparison with inner-loop methods: Inner-loop methods use growing consensus iterations to correct local descent directions, but their iteration count can impose substantial coordination and convergence costs.For strongly convex problems, sufficiently accurate average-gradient estimates may require Ω(t) inner iterations, yielding sublinear convergence.
  • Comparison with inner-loop methods: O(1/T^(2−ε)) convergence is reported for the inner-loop D-NC method, where T counts total consensus steps.This rate uses a constant step size after inner consensus makes the descent direction approximately correct.
  • Gradient estimator intuition: The gradient estimator averages neighboring estimates and adds incremental gradient information, allowing it to track the average gradient asymptotically.The incremental term is controlled through smoothness and step-size selection, enabling larger steps than the compared method.

IV. CONVERGENCE ANALYSIS OF ACC-DNGD-SC

The proof reduces the network average sequences to an inexact CNGD-SC process, with the gradient error controlled by consensus error. Bounding that error enables the theorem’s convergence conclusions.

  • Proof overview: The consensus error is bounded separately, after which CNGD-SC proof steps are applied to the average sequence.The proof uses a recursively defined series of functions Φt(ω) to establish the convergence inequality.
  • Proof overview: The average sequences follow an update rule similar to CNGD-SC, but g(t) replaces the exact gradient at ¯y(t).The averages are derived using double stochasticity of W.
  • Proof overview: g(t) is an inexact gradient at ¯y(t) with error O(∥y(t) −1¯y(t)∥2).This connects local disagreement to the optimization error in the averaged dynamics.
  • Theorem consequences: f(¯x(t)) −f* = O((1 −α)t) follows from the major inequality, yielding part (a) of Theorem 3.The same analysis also gives f(yi(t)) −f* = O((1 −√µη)t) for the agents.
  • Theorem consequences: Exact convergence can occur for sufficiently small η when the inexact-gradient error depends on past iterates and decays geometrically.This contrasts with constant error, for which the cited inexact Nesterov results yield only approximate convergence.

B. Proof of the Bounded Consensus Error (Lemma 3)

The consensus-error proof models the disagreement dynamics as a linear system and analyzes its transition matrix spectrally. These properties provide the bounds needed to control disagreement and establish optimization convergence.

  • Step 1: A Linear System Inequality: The proof first derives a linear system inequality for a state containing velocity and y-sequence disagreement.The state is z(t) = [∥v(t)−1¯v(t)∥, ∥y(t)−1¯y(t)∥, 1]T, with b(t) as the system input.
  • Step 2: Spectral Properties: The transition matrix G(η) is then analyzed through its spectral radius and powers to bound the state evolution.The proof uses spectral properties after deriving the linear inequality.
  • Step 2: Spectral Properties: ρ(G(η)) is bounded above by σ + 4(ηL)1/3, while selected entries of G(η)t receive explicit bounds.The second-row bounds directly concern the consensus-related state components.
  • Step 2: Spectral Properties: The spectral factor (σ)2/3 converges to 0 as η → 0, a property used in proving the main inequality.This behavior is identified as crucial for the proof of equation (19).
  • Consequence: The resulting bounds give ∥y(t) −1¯y(t)∥ = O((1 −α)t/2), which leads to agent-level convergence f(yi(t)) −f* = O((1 −α)t).The argument combines bounds on averaged iterates, disagreement, and L-smoothness.

V. CONVERGENCE ANALYSIS OF ACC-DNGD-NSC

The analysis of Acc-DNGD-NSC again represents the averaged dynamics as inexact CNGD-NSC, with consensus error supplying the inexactness. It treats vanishing and fixed step-size cases through shared intermediate lemmas.

  • Proof scope: The shared proof framework covers both the vanishing-step-size and fixed-step-size analyses.The paper says the lemma sequence works for both cases.
  • Proof overview: The average sequences follow an update rule similar to CNGD-NSC, with g(t) replacing the exact gradient at ¯y(t).The average identities follow from W being doubly stochastic.
  • Proof overview: g(t) is an inexact gradient at ¯y(t) with error O(∥y(t)−1¯y(t)∥2).The paper explains this terminology by contrasting g(t) with the exact gradient’s smoothness inequality.
  • Proof overview: The proof bounds consensus error in Lemma 10 and then applies CNGD proof strategies to the average sequences despite that error.Lemma 11 provides the intermediate result used before proving Theorems 4 and 5.
  • Theorem consequences: Exact convergence can hold with ηt = η(t+1)^β for sufficiently small η and β ∈ (0.6, 2), under the stated error dependence.The cited comparison says fixed error causes divergence for the referenced inexact Nesterov methods.

B. Proof of the Bounded Consensus Error (Lemma 10)

The proof of bounded consensus error uses a three-step linear-system argument: derive the inequality, establish spectral properties, and bound the state by the input.

  • Step 1: A Linear System Inequality: The state z(t) records scaled velocity disagreement, y disagreement, and s disagreement in a three-dimensional vector.It is used to formulate the linear system inequality governing consensus error.
  • Step 2: Spectral Properties: The transition matrix G(η) is nonnegative, and Perron-Frobenius theory identifies its unique largest positive eigenvalue θ(η) = ρ(G(η)).The corresponding positive eigenvector is normalized by χ3(η) = 1.
  • Step 2: Spectral Properties: When 0 < ηL < 1, σ < θ(η) < σ + 4(ηL)1/3 and χ2(η) ≤ 2L2/3η1/3.Additional bounds on θ(η) and χ1(η) are used under the stated step-size conditions.
  • Step 3: Bound the state by the input: The third step proves by induction that the state is bounded by the input sequence a(t).The argument shows the input does not decrease too much while the state decreases sufficiently to preserve the bound.
  • Step 3: Bound the state by the input: The resulting estimate controls disagreement through a(t), which combines averaged-sequence separation and gradient magnitude.The paper concludes the lemma after relating a(t) to ∥¯y(t) −¯x(t)∥ and ηt∥g(t)∥.

C. Proof of Theorem 4

The proof establishes asymptotic bounds for the acceleration parameters and uses induction to derive the objective-error rate for Acc-DNGD under a vanishing step size.

  • Step-size conditions: η_t = η(t+t_0)^β with β∈(0,2) and η_0 < 1/(4L) is the vanishing-step-size regime used by Lemma 16.These conditions ensure the auxiliary lemmas required in Theorem 4 apply.
  • Parameter bounds: α_t ≤ 2/(t+1) bounds the acceleration parameter.
  • Parameter bounds: λ_t = O(1/t^(2−β)) gives the asymptotic decay rate of the product of the factors (1−α_t).
  • Parameter bounds: λ_t ≥ D(β,t_0)/(t+t_0)^(2−β), where D(β,t_0) depends only on β and t_0, supplies a matching lower bound.
  • Inductive objective bound: The induction controls the iterates through a compact level set, bounded distance to x*, smoothness, and recursively accumulated consensus terms.

VI. NUMERICAL EXPERIMENTS

The numerical experiments evaluate Acc-DNGD across graph topologies, objective classes, and time-varying networks, comparing it with distributed and centralized baselines. The reported results show faster convergence, including rates beyond the principal theoretical baselines, while preserving convergence under changing graphs.

  • Experimental settings: The experiments use random graphs, k-cycles, and 2D grids, including a 100-agent k-cycle and a 25-node 5×5 grid.The random graph uses an Erdős–Rényi model with connectivity probability 0.3.
  • Strongly convex cases: Case I and II test the strongly-convex variant Acc-DNGD-SC against CGD, CNGD-SC, D-NG, DGD, EXTRA, and Acc-DGD.
  • Strongly convex cases: Acc-DNGD-SC performs significantly better than CGD, CGD-based distributed methods, and D-NG in the reported strongly convex simulations.
  • Strongly convex cases: For condition numbers between 300 and 800, the proposed method already outperforms CGD and existing distributed methods.The paper attributes the advantage to better asymptotic dependence on L/μ in the large-condition-number regime.
  • Non-strongly-convex case: Acc-DNGD-NSC with β=0.61 is faster than 1/t^1.39, while β=0 and CNGD-NSC are faster than 1/t^2 in Case III.
  • Agent-level and time-varying behavior: Individual objective errors become indistinguishable after about 100 iterations, whereas time-varying graphs produce more volatile trajectories despite convergence to zero.The time-varying experiment removes 75% of ground-graph edges at each iteration and recomputes weights.
  • Step-size stability: Across 20 random instances, Acc-DNGD-NSC is stable under Remark 1’s step-size rule and decays faster than the O(1/t^1.39) baseline.
  • Reported theoretical results: The paper concludes that Acc-DNGD achieves O(1/t^(1.4−ε)) for convex smooth objectives, O(1/t^2) under the stated composition condition, and a linear strongly-convex rate.It also states that these rates are better than CGD and CGD-based distributed methods.

APPENDIX

The appendix establishes spectral properties of the matrix G(η) and derives quadratic-potential identities used in the convergence analysis.

  • Spectral analysis: The spectral gap is at least ρ(G(η)) − σ.This conclusion covers both the three-real-eigenvalue and complex-conjugate-eigenvalue cases considered in the proof.
  • Spectral analysis: (σηL)1/3 lower-bounds the separation between the leading eigenvalue and the smaller eigenvalues.The proof states γ1 − |γ3| ≥ γ1 − |γ2| ≥ (σηL)1/3.
  • Matrix-power bounds: The entries [G(η)t]21, [G(η)t]22, and [G(η)t]23 are bounded by 39(σηL)2/3γ1^t.This follows from the eigenvalue representation and bounds on the initial matrix entries.
  • Potential construction: The potential Φt is quadratic, minimized at v̄(t), and has Hessian γtI.These properties are proved inductively and support the recursive potential analysis.

D. Proof of Lemma 12

This proof bounds the dominant eigenvalue and its sensitivity to the step size, yielding estimates used in the spectral convergence analysis.

  • Root localization: The characteristic polynomial places the largest real root within (σ, σ + 4(ηL)1/3).This root localization is used in the derivative analysis.
  • Eigenvector bounds: The leading eigenvalue obeys χ1(η) < η(σηL)1/3.The proof first establishes θ(η) > σ + (σηL)1/3 and then derives the bound on χ1(η).
  • Eigenvalue sensitivity: 0 < θ′(η) ≤ 9Lσ2/3 under the step-size condition η < σ2/L^9/3.The derivative is obtained by differentiating the characteristic-polynomial equation.
  • Lipschitz estimates: ξ1 is 6/σ-Lipschitz continuous after the logarithmic reparameterization ξ1(y) = log χ1(e^y).The proof introduces ξ1 and bounds its derivative using the step-size restrictions.

G. Proof of Lemma 16

The proof uses a comparison lemma and logarithmic estimates to derive polynomial decay for the sequence λt.

  • Parameterization: The parameter transformation ξ(y) = y2/(1 − y) is strictly increasing and bijective on (0,1).Its inverse is used to relate αt+1 to the step-size sequence.
  • Comparison argument: The analysis compares a varying step-size sequence with a fixed step size η′.The comparison lemma is applied to transfer bounds between the two sequences.
  • Polynomial decay: λt = O(1/t2−β) for the sequence analyzed in Lemma 16.The result follows after bounding a series and using the comparison lemma.
  • Lower bound: The lower bound on λt has the form λt ≥ 1/[(t + t0)2−β(t0 + 3)2e16+6/(2−β)].This estimate is obtained by combining logarithmic inequalities with earlier bounds.

H. Proof of Theorem 4 (b)

The theorem proof converts the potential and consensus estimates into objective-error bounds, obtaining an O(1/t2) rate for the averaged and individual errors.

  • Assumptions: The local functions fi are convex and L-smooth under the theorem’s assumptions.This property is invoked at the start of the proof.
  • Proof strategy: The proof establishes an inductive potential inequality before deriving the objective-error rate.The induction uses Lemma 21, Lemma 10, and the prescribed step-size condition.
  • Theorem result: f(x̄(t)) − f* = O(1/t2).The proof first establishes f(x̄(t)) − f* = O(λt), then uses λt = O(1/t2).
  • Theorem result: f(yi(t)) − f* = O(1/t2) for every agent i.The individual-agent result follows after bounding the averaged error and disagreement terms.

J. Supplementary Materials for the Simulation in Section VI

The supplementary material documents simulation settings and individual objective-error plots for Acc-DNGD variants across several network cases. It also includes proof fragments related to the non-strongly-convex analysis.

  • Simulation settings: The simulations use random graphs, k-cycles, and 2D grids with algorithm-specific step-size parameters.The supplementary passages list step sizes for Acc-DNGD and comparison methods across the network settings.
  • Simulation settings: The supplementary experiments compare Acc-DNGD variants with D-NG, DGD, EXTRA, CGD, and CNGD.The listed parameter settings identify the methods used in the simulation comparisons.
  • Simulation results: Individual objective errors are plotted for Acc-DNGD-SC in Cases I and II and Acc-DNGD-NSC with β = 0 in Case III.Each figure reports f(y_i(t)) − f* for 10 evenly spaced agent indices.
  • Proof material: The supplementary proof material bounds expressions involving γ parameters using β ≥ (σηL)^1/3.These passages belong to the proof of Lemma 17 and provide an intermediate parameter condition.
Loading 1705.07176v4…