PaperlayerView exact revision on arXiv

Source-linked AI summary

Accelerated Distributed Nesterov Gradient Descent

Guannan Qu, Na Li

arXiv:1705.07176v4math.OC

TL;DR

The paper asks how to minimize the average of agents’ local functions in distributed optimization. Acc-DNGD combines a gradient-estimation scheme with a consensus matrix for distributed optimization. Rates are O(1/t^(1.4−ε)) for convex L-smooth functions, O(1/t^2) for a linear-map/strongly-convex-smooth composition, and linear convergence for μ-strongly convex L-smooth functions; C is independent of L or μ.

  • Problem

    The paper asks how to minimize the average of agents’ local functions in distributed optimization.

    Source: §I · pp. 1–2

  • Method

    Acc-DNGD combines a gradient-estimation scheme with a consensus matrix for distributed optimization.

    Source: §I · pp. 2–3, C. Our Algorithm: Accelerated… · p. 5

  • Results

    Rates are O(1/t^(1.4−ε)) for convex L-smooth functions, O(1/t^2) for a linear-map/strongly-convex-smooth composition, and linear convergence for μ-strongly convex L-smooth functions; C is independent of L or μ.

    Source: §VII · p. 32

  • Takeaways & Limitations

    The reported rates are better than those of CGD and CGD-based distributed methods.

    Source: §VII · p. 32

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 introduction presents Acc-DNGD for distributed optimization and outlines its convergence guarantees, alongside the assumptions and centralized Nesterov Gradient Descent variants that provide context for the method.

I. INTRODUCTION

  • O((1 - C(μ/L)^(5/7))^t) convergence is achieved by Acc-DNGD-SC for μ-strongly convex, L-smooth objectives, with C independent of L and μ.The paper states this condition-number dependence is best among primal gradient-based distributed algorithms for this function class, to the authors’ knowledge.Source: §I · pp. 2–3
  • O(1/t^(1.4−ε)) convergence for every ε in (0, 1.4) is achieved by Acc-DNGD-NSC, while a linear-map composition with a strongly convex smooth function permits O(1/t^2).The first rate uses a vanishing step size; the second uses a fixed step size.Source: §I · p. 3
  • A gradient-estimation scheme tracks the average gradient and combines with centralized Nesterov Gradient Descent to avoid an inner loop, enabling one communication step per gradient evaluation.The paper says its rates are strictly better than centralized gradient descent but still slower than centralized Nesterov Gradient Descent, so the gap is only partially bridged.Source: §I · pp. 2–3
  • The proof shows that a specially structured error can still yield exact convergence in an inexact Nesterov method.The authors suggest this proof technique may also be of independent interest for general inexact Nesterov methods.Source: §I · p. 3

A. Problem Formulation

  • Distributed optimization seeks to minimize the average of agents’ local convex functions using local computation and communication over a connected undirected graph.Each agent bases its decisions on its local function and information from its neighbors.Source: A. Problem Formulation · p. 4
  • The set of minimizers of f is assumed to be compact.Source: A. Problem Formulation · p. 4

B. Centralized Nesterov Gradient Descent (CNGD)

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

This section presents Acc-DNGD, which uses a gradient estimator and neighbor-only communication in versions for strongly convex and general convex objectives, and summarizes its convergence results. It also identifies tighter bounds as future work.

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

  • Acc-DNGD-SC and Acc-DNGD-NSC maintain xi(t), vi(t), yi(t), and a gradient estimator si(t); the versions target strongly convex and convex, L-smooth objectives, respectively.The strongly convex version initializes si(0)=∇fi(yi(0)); the general convex version initializes the other variables at zero and si(0)=∇f(0).Source: C. Our Algorithm: Accelerated… · pp. 5–6
  • Each agent sends its four variables only to neighbors, enabling fully distributed local communication; si(t) estimates the average gradient and improves convergence.Source: C. Our Algorithm: Accelerated… · p. 6

D. Convergence of the Algorithm

  • Under strong convexity, Acc-DNGD-SC achieves f(¯x(t))−f* = O((1−√(μη)^t) and the same rate for each f(yi(t))−f*.The theorem applies when its step-size upper bound is met.Source: D. Convergence of the Algorithm · p. 7
  • For convex, L-smooth objectives, Acc-DNGD-NSC achieves O(1/t^(1.4−ϵ)) convergence with a vanishing step size and β=0.6+ϵ, where ϵ∈(0,1.4).The rate applies to both the average sequence and each agent's yi(t).Source: D. Convergence of the Algorithm · p. 7
  • Acc-DNGD-NSC achieves O(1/t^2) with a fixed step size when each local objective is a linear-map composition with a strongly convex, smooth function.The condition is stated as fi(x)=hi(xAi), where hi is strongly convex and smooth.Source: D. Convergence of the Algorithm · p. 8
  • The special composition condition yields local strong convexity along the iterates, explaining the faster convergence result.The paper attributes this property to iterates and gradients lying in the relevant row space, together with strong convexity of hi.Source: D. Convergence of the Algorithm · p. 8
  • Finding tighter bounds remains future work.The passage does not specify the bounds’ scope or size.Source: D. Convergence of the Algorithm · p. 9

III. ALGORITHM DEVELOPMENT

Acc-DNGD adapts Nesterov updates to distributed agents using a gradient estimator, while controlling disagreement among agents. The paper contrasts this approach with inner-loop consensus methods and explains its convergence trade-offs.

A. Inexact Nesterov gradient methods

  • The proof bounds consensus errors, then treats the distributed method as an inexact centralized Nesterov update and applies an inexact-gradient convergence framework.Bounding disagreement in y_i(t) is sufficient for the proof described here.Source: A. Inexact Nesterov gradient methods · p. 9
  • Nesterov methods can accumulate noise and diverge; the paper adapts the method to a distributed setting and presents its proof technique as potentially useful for inexact Nesterov methods more generally.The authors identify nontrivial convergence analysis as a challenge in inexact settings.Source: A. Inexact Nesterov gradient methods · p. 9

B. Comparison with Inner-Loop Methods and Intuition on Gradient Estimator si(t)

  • Local gradients can point in the wrong direction at a global optimizer, so the iterates may not have that optimizer as a fixed point.The desired direction is the average gradient, which is zero at the optimizer.Source: B. Comparison with Inner-Loop Methods… · p. 10
  • Inner-loop methods add coordination overhead, require uniformly bounded gradients in the cited work, and may need Ω(t) inner iterations for strongly convex objectives, yielding sublinear convergence.The paper says even simple quadratic functions need not satisfy the bounded-gradient assumption.Source: B. Comparison with Inner-Loop Methods… · p. 10
  • The gradient estimator averages neighbors’ estimates and adds the change in local gradients, allowing it to track the average gradient without inner-loop consensus iterations.The authors state that the estimator asymptotically approaches the average gradient.Source: B. Comparison with Inner-Loop Methods… · pp. 10–11
  • For convex smooth functions, Acc-DNGD’s O(1/t^(1.4−ϵ)) rate is slower than D-NC’s O(1/t^(2−ϵ)); under an additional functional-form assumption, Acc-DNGD reaches O(1/t^2).The paper notes that the comparison also depends on assumptions and implementation complexity.Source: B. Comparison with Inner-Loop Methods… · p. 11

IV. CONVERGENCE ANALYSIS OF ACC-DNGD-SC

The proof analyzes the averaged agent sequences as an inexact centralized Nesterov method, with consensus error measuring gradient inexactness. It bounds that error and uses an inexact-method argument to establish convergence.

A. Proof Overview

  • The average sequences follow a centralized Nesterov update with an inexact gradient, whose error is characterized by disagreement between local and average iterates.The proof overview identifies the y-sequence consensus error as the relevant quantity to bound.Source: A. Proof Overview · p. 12
  • The proof bounds consensus error and then applies centralized inexact Nesterov proof steps to the average sequence.The overview says the resulting argument establishes Theorem 3.Source: A. Proof Overview · pp. 12–13
  • For the average iterates, the proof derives f(x̄(t)) − f* = O((1−α)^t); it also gives f(y_i(t)) − f* = O((1−√(μη))^t) for local iterates.The local-iterate rate is presented as a corollary of the main inequality.Source: A. Proof Overview · pp. 14–15
  • The proof states that sufficiently small step size can yield exact convergence when inexact-gradient error depends on past iterates through the specified decaying-error form.This contrasts with the cited constant-error setting, where only approximate convergence is obtained.Source: A. Proof Overview · p. 15

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

The proof bounds consensus error by representing the algorithm as a linear system and analyzing its state-transition matrix. It then uses that bound to establish convergence of individual agents under strong convexity.

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

  • The proof represents disagreement quantities as a state z(t) and derives a linear system inequality with b(t) as its input.The state includes disagreement in v(t) and y(t); b(t) is given as [0, 0, √n a(t)]^T.Source: B. Proof of the Bounded Consensus… · p. 15
  • The transition matrix G(η) has spectral bounds whose dependence on η is used to conclude the bounded-consensus-error lemma.The proof notes that a matrix-power quantity converges to zero as η → 0 and is crucial to its argument for (19).Source: B. Proof of the Bounded Consensus… · p. 17
  • The consensus-error bound is derived from the linear-system inequality and the state’s relation to the input.The proof identifies ∥y(t) − 1¯y(t)∥ as the second entry of z(t), then applies Lemma 3 to bound it by ν^Tπ_k.Source: B. Proof of the Bounded Consensus… · p. 17, C. Proof of (19) · p. 18

C. Proof of (19)

  • Under strong convexity, the proof bounds each agent’s objective error by O((1 − α)^t).It first bounds the distance from each y_i(t) to x* by O((1 − α)^(t/2)), then applies L-smoothness.Source: C. Proof of (19) · p. 20

V. CONVERGENCE ANALYSIS OF ACC-DNGD-NSC

The convergence analysis treats the average sequences as an inexact Nesterov method, with consensus error controlling the gradient inexactness. It combines a consensus-error bound with an inexact-method argument to establish convergence results for vanishing and fixed step sizes.

A. Proof Overview

  • The average sequences follow a CNGD-NSC update with an inexact gradient, whose inexactness is characterized by consensus error.The gradient g(t) is inexact at ¯y(t), with error O(∥y(t) − 1¯y(t)∥²).Source: A. Proof Overview · p. 21
  • The proof bounds the consensus error and then applies the CNGD proof strategy to the average sequences despite that error.The overview assigns the average-sequence update, inexact-gradient characterization, consensus-error bound, and intermediate result to Lemmas 8–11.Source: A. Proof Overview · pp. 21–22
  • The proof develops intermediate results for both vanishing and fixed step sizes, then uses them to prove Theorems 4 and 5.The overview says the final steps carefully control error caused by inexactness.Source: A. Proof Overview · pp. 21–22
  • For the stated history-dependent error form, sufficiently small η and β ∈ (0.6, 2) permit exact convergence with a vanishing step size.The passage contrasts this with the cited result that inexact Nesterov methods diverge when the error is fixed throughout.Source: A. Proof Overview · p. 22

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

The proof of Lemma 10 bounds consensus error by modeling the algorithm as a linear system, analyzing its transition matrix, and bounding the state by the input.

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

  • The proof models the algorithm as a linear system with a state containing scaled disagreement in v(t), disagreement in y(t), and disagreement in s(t).It derives a linear system inequality for this state before analyzing the transition matrix.Source: B. Proof of the Bounded Consensus… · p. 23
  • The proof establishes spectral properties of G(η), including bounds on its largest eigenvalue and eigenvector components.For 0 < ηL < 1, Lemma 13 gives σ < θ(η) < σ + 4(ηL)^(1/3) and χ2(η) ≤ 2L^(2/3)η^(1/3).Source: B. Proof of the Bounded Consensus… · p. 23
  • An induction bounds the state by the input, using step 3.1 to control input decrease and step 3.2 to show sufficient state decrease.The proof overview states that this state-by-input bound yields the lemma’s conclusion.Source: B. Proof of the Bounded Consensus… · pp. 24–26

C. Proof of Theorem 4

Theorem 4’s proof analyzes a vanishing-step-size schedule and derives objective-error rates for the average iterate and individual agents. Its argument uses intermediate bounds under the theorem’s step-size conditions.

C. Proof of Theorem 4

  • The proof uses asymptotic bounds on α_t and λ_t for the vanishing-step-size schedule.Lemma 16 states λ_t = O(1/t^(2−β)) and α_t ≤ 2/(t+1).Source: C. Proof of Theorem 4 · p. 26
  • With vanishing step sizes, the proof gives average objective error O(1/t^(2−β)) and individual-agent objective error O(1/t^(1.4−ε)).The vanishing step size is specified as η_t = η/(t+t0)^β with t0 ≥ 1 and β ∈ (0, 2).Source: C. Proof of Theorem 4 · pp. 26, 29
  • The proof bounds the iterates using a compact level set under Assumption 2.The passage bounds ∥¯x(k) − x*∥ by the diameter of that level set.Source: C. Proof of Theorem 4 · p. 27

VI. NUMERICAL EXPERIMENTS

The experiments report that Acc-DNGD outperforms comparison methods in strongly convex cases and show convergence across several graph settings. The conclusion gives convergence guarantees for convex smooth, structured, and strongly convex smooth objectives.

VI. NUMERICAL EXPERIMENTS

  • In Case III, Acc-DNGD-NSC with β=0.61 is faster than 1/t^1.39, while its β=0 variant and CNGD-NSC are faster than 1/t^2.The compared D-NG, CGD, and distributed baselines are slower than 1/t^1.39.Source: §VI · pp. 30–31, Figure 3 · p. 32
  • For strongly convex Cases I and II, Acc-DNGD-SC significantly outperforms centralized and distributed baselines, including when the condition number is 300–800.The figures compare objective error over iterations across three graph types.Source: §VI · p. 30
  • For individual agents, objective-error trajectories become indistinguishable after about 100 iterations.This is reported for Case I and Case III with a random graph.Source: §VI · p. 31, Figure 4 · p. 32
  • With a time-varying graph, objective errors converge to zero, but their trajectories are more volatile than with a fixed graph.The experiment removes a randomly selected 0.75 portion of the ground graph's edges at each iteration.Source: §VI · p. 31, Figure 5 · p. 33
  • Acc-DNGD-NSC is stable under the step-size rule in Remark 1, and its objective error decays faster than the baseline O(1/t^1.39).Source: §VI · p. 32

VII. CONCLUSION

  • For convex L-smooth objectives, the method achieves O(1/t^(1.4−ε)) for ε∈(0,1.4), improving to O(1/t^2) for a linear-map composition with a strongly convex smooth function.These are the first-version guarantees described in the conclusion.Source: §VII · p. 32
  • For μ-strongly convex, L-smooth objectives, the second version achieves linear convergence, with rates stated to be better than CGD and CGD-based distributed methods.The conclusion says the constant C is independent of L and μ.Source: §VII · p. 32
  • The authors identify tightening the analysis to obtain better convergence rates as future work.Source: §VII · p. 32

APPENDIX

The appendix proves spectral bounds for the iteration matrix and establishes a quadratic potential characterization.

A. Proof of Lemma 5 and Lemma 6

B. Proof of Lemma 7

  • The spectral gap is at least ρ(G(η))−σ, and γ1−|γ3| is at least (σηL)^(1/3).The proof also bounds the largest entries of G(η)^t by 39(σηL)^(2/3)γ1^t.Source: B. Proof of Lemma 7 · p. 38

C. Proof of the Intermediate Result (Lemma 11)

D. Proof of Lemma 12

This section provides derivations for Lemma 12 and the linear system in Lemma 10, then bounds spectral quantities used in Lemmas 13–15.

D. Proof of Lemma 12

  • The section provides derivations for Lemma 12.The passage introduces the derivations without stating their contents.Source: D. Proof of Lemma 12 · p. 39

E. Derivation of (43) in the Proof of Lemma 10

F. Proof of Lemma 13, Lemma 14 and Lemma 15

G. Proof of Lemma 16

The proof uses a comparison lemma to establish bounds on the sequences, including a polynomial rate for λ_t.

G. Proof of Lemma 16

  • The proof applies the comparison lemma with a fixed step size η′ to establish part (i).It then derives a tighter upper bound for α_t.Source: G. Proof of Lemma 16 · p. 44
  • λ_t=O(1/t^(2−β)).This is the stated conclusion of part (ii) of the lemma.Source: G. Proof of Lemma 16 · p. 46
  • The proof also derives a logarithmic lower bound on λ_t.The displayed bound is log λ_t ≥ −(2−β)log(t−1+t0)−2log(t0+3)−6/(2−β)−16.Source: G. Proof of Lemma 16 · p. 47

H. Proof of Theorem 4 (b)

The proofs establish an O(1/t²) objective-error rate under Theorem 5 and an O(1/t^(2−β)) rate for individual agents under Theorem 4(b).

H. Proof of Theorem 4 (b)

  • The proof bounds both ∥∇f(ȳ(t))∥ and ∥∇f(x̄(t))∥ by O(1/t^(1−β)).These bounds are intermediate steps in the individual-error proof.Source: H. Proof of Theorem 4 (b) · p. 48
  • For each agent i, f(y_i(t))−f*=O(1/t^(2−β)).This is the stated individual-error conclusion of Theorem 4(b).Source: H. Proof of Theorem 4 (b) · p. 48

I. Proof of Theorem 5

  • Under Theorem 5, f(x̄(t))−f* = O(1/t²).The proof obtains this by bounding λ_t by O(1/t²).Source: §I · p. 51

J. Supplementary Materials for the Simulation in Section VI

The supplementary material reports step-size settings for the Section VI figures and plots individual objective errors across selected nodes. It also includes the closing estimates in the proof of Lemma 17.

J. Supplementary Materials for the Simulation in Section VI

K. Proof of Lemma 17

1. Hence,

  • The closing estimate is bounded by (|B0| + 2|B1| + |B2|)γ1^t β^2.Source: §1 · p. 55

Related papers

Loading 1705.07176v4…