PaperlayerView exact revision on arXiv

Source-linked AI summary

On Nonconvex Decentralized Gradient Descent

Jinshan Zeng, Wotao Yin

arXiv:1608.05766v4math.OCcs.DCcs.MA

TL;DR

The paper addresses limited understanding of decentralized consensus optimization under nonconvexity by analyzing DGD and Prox-DGD with fixed and decreasing step sizes. It shows convergence to Lyapunov or original-problem stationary points, with asymptotic consensus for decreasing steps, and extends Prox-DGD to nonconvex nonsmooth terms under regularity conditions.

  • Problem

    Convergence of simple decentralized gradient descent under nonconvex local objectives was previously unknown, despite DGD’s simplicity and broad extensibility.

  • Method

    The paper analyzes DGD and Prox-DGD using Lyapunov functions, new lemmas, and an auxiliary sequence for consensus-rate estimates.

  • Results

    DGD with decreasing step sizes reaches asymptotic consensus and converges to a stationary point of the original problem, while Prox-DGD extends to nonconvex proximal functions.

  • Takeaways & Limitations

    DGD and Prox-DGD retain most convex-setting convergence properties in nonconvex settings, apart from guaranteed global optimality.

Abstract

from arXiv · show

Consensus optimization has received considerable attention in recent years. A number of decentralized algorithms have been proposed for {convex} consensus optimization. However, to the behaviors or consensus \emph{nonconvex} optimization, our understanding is more limited. When we lose convexity, we cannot hope our algorithms always return global solutions though they sometimes still do sometimes. Somewhat surprisingly, the decentralized consensus algorithms, DGD and Prox-DGD, retain most other properties that are known in the convex setting. In particular, when diminishing (or constant) step sizes are used, we can prove convergence to a (or a neighborhood of) consensus stationary solution under some regular assumptions. It is worth noting that Prox-DGD can handle nonconvex nonsmooth functions if their proximal operators can be computed. Such functions include SCAD and $\ell_q$ quasi-norms, $q\in[0,1)$. Similarly, Prox-DGD can take the constraint to a nonconvex set with an easy projection. To establish these properties, we have to introduce a completely different line of analysis, as well as modify existing proofs that were used the convex setting.

I. INTRODUCTION

The paper studies DGD and Prox-DGD for decentralized consensus optimization when local objectives or proximal terms may be nonconvex. It develops new analysis showing that many convex-setting convergence properties remain valid, aside from global optimality.

  • Nonconvex DGD convergence was previously unknown, despite DGD’s simplicity and suitability for extensions such as online processing.
  • DGD combines neighbor averaging with local gradient steps, while Prox-DGD additionally applies proximal maps to local regularizers.Both algorithms support fixed or decreasing step sizes.
  • With a properly bounded fixed step size, DGD converges to a stationary point of a Lyapunov function, while disagreement from the global average is proportional to the step size.
  • With α_k = O(1/(k + 1)^ε), 0 < ε ≤ 1, DGD’s objective sequence converges and its iterates become asymptotically consensual at O(1/(k + 1)^ε).The analysis also derives convex-setting objective convergence rates for different ε.
  • Prox-DGD extends the convergence analysis to differentiable functions plus potentially nonconvex or nonsmooth proximable terms, including nonconvex-set indicators and ℓ_q quasi-norms.For nonconvex proximal terms, positive-definite mixing and a smaller step size are required.
  • The paper introduces Lyapunov arguments, new lemmas, and an auxiliary sequence to analyze decreasing-step convergence and consensus rates.These techniques are presented as distinct from prior analyses.

III. ASSUMPTIONS AND MAIN RESULTS

The paper establishes convergence properties for nonconvex DGD under fixed stepsizes, while identifying the limits of consensus and original-problem stationarity. Its analysis uses Lyapunov and KŁ tools under regularity assumptions.

  • Assumptions: Assumptions require each local objective to be Lipschitz differentiable, proper, and coercive.The network mixing matrix is also assumed to satisfy graph, symmetry, null-space, and spectral properties.
  • Analysis and rates: The analysis introduces a Lyapunov function, new convergence lemmas, and an auxiliary sequence to establish iterate, objective, and consensus behavior.KŁ exponents yield finite, linear, or sublinear eventual convergence rates, depending on θ.
  • Limitations: Without convexity, the objective sequence converges under the decreasing-step analysis, but no general rate to an optimal value is available.Obtaining such an optimal-value rate is generally difficult without convexity.
  • Fixed-step convergence: For a fixed stepsize satisfying 0 < α < (1 + λ_n(W))/L_f, DGD accumulation points are stationary points of the Lyapunov function L_α.Under the KŁ property, the entire iterate sequence globally converges to an accumulation point.
  • Fixed-step convergence: The Lyapunov stationary point is stationary for the separable objective, but not necessarily for the original consensus problem because its rows may differ.The row differences remain bounded rather than necessarily vanishing.
  • Fixed-step convergence: Fixed-step consensus is approximate: the asymptotic disagreement is proportional to α and inversely proportional to the spectral gap of W.The bound depends on a universal gradient bound and the second-largest magnitude eigenvalue of W.

2) Convergence of DGD with decreasing step sizes:

With decreasing step sizes, DGD reaches asymptotic consensus and converges to stationary points in nonconvex settings, while convexity yields explicit objective-rate tradeoffs.

  • DGD with decreasing step sizes reaches consensus asymptotically, with ∥xk −¯xk∥ converging at O(1/(k + 1)^ǫ).This improves on the nonzero consensus-error bound associated with fixed step sizes.
  • The consensus error in the (I − W) semi-norm decays at O(1/(k + 1)^(2ǫ)).The corresponding distance to a global consensual solution decays at O(1/k^(2ǫ)) if the iterates converge to that solution.
  • The objective sequence converges, and every limit point of DGD is a stationary point of the original nonconvex problem.If an isolated accumulation point exists, the entire iterate sequence converges.
  • The analysis introduces a Lyapunov function, auxiliary sequences, and new lemmas to establish objective convergence, stationarity, and consensus rates.These techniques are specifically used for decreasing-step-size DGD analysis.
  • Under convexity, the ergodic objective converges to the optimum at rates depending on ǫ: O(1/K^ǫ), O(ln K/K), O(1/K^(1−ǫ)), or O(1/K).These cases correspond respectively to 0 < ǫ < 1/2, ǫ = 1/2, 1/2 < ǫ < 1, and ǫ = 1.
  • The choice of ǫ trades off objective convergence and consensus speed: ǫ = 1/2 may optimize the former, while larger ǫ generally accelerates consensus.The analysis assumes uniformly bounded gradients, a condition common in decentralized gradient-method analyses.

C. Convergence results of Prox-DGD

Prox-DGD can be analyzed as a forward-backward splitting method and converges to stationary points under composite-objective assumptions, with rates refined by the KŁ property.

  • Prox-DGD performs gradient descent on Lαk(x) followed by the proximal operation for r(x), yielding a forward-backward splitting interpretation.The method combines local gradients, proximal maps, and neighbor information.
  • The composite-objective assumptions require Lipschitz differentiable fi and proper, lower semicontinuous, coercive fi + ri.The common Lipschitz constant is defined using the maximum individual smoothness constant.
  • Under the stated step-size and composite-objective assumptions, Prox-DGD has an accumulation point, and every accumulation point is stationary for ˆLα(x).The nonconvex-ri case requires λn(W) > 0 and a smaller step-size bound than the convex-ri case.
  • Prox-DGD achieves running-best rates o(1/k) for iterate differences, proximal residuals, and averaged perturbation terms.These rates apply to the sequences specified in Theorem 3.
  • If ˆLα satisfies the KŁ property, Prox-DGD converges to an accumulation point with finite, linear, or sublinear rates depending on θ.For θ = 0 convergence is finite; θ ∈ (0, 1/2] gives a geometric rate; θ ∈ (1/2, 1) gives a polynomial rate.

2) Convergence of Prox-DGD with decreasing step sizes:

Prox-DGD extends decentralized convergence guarantees to composite objectives with potentially nonconvex nonsmooth proximal terms under decreasing step sizes. Under stated regularity conditions, it achieves asymptotic consensus and stationary-point convergence, with rates and scope depending on additional assumptions.

  • Consensus rates: Prox-DGD achieves asymptotic consensus, with ∥xk − x̄k∥ converging to 0 at O(1/(k + 1)^ε) and the related consensus quantity at O(1/(k + 1)^(2ε)).These rates are stated under the assumptions of Proposition 6 and the decreasing step-size schedule.
  • Convergence guarantees: Theorem 4 establishes convergence of the Lyapunov/objective sequences and asymptotic stationarity for Prox-DGD with decreasing step sizes.Any limit point is stationary; an isolated accumulation point yields convergence of the iterate sequence.
  • Model and assumptions: Prox-DGD analyzes composite objectives whose differentiable and proximal components may both be nonconvex, while allowing proximal terms such as ℓq quasi-norms, SCAD, and MCP.The method also covers nonconvex constraints when projection is easy, and uses decreasing step sizes under revised bounded-composite-subgradient conditions.
  • Applications to nonconvex penalties: For ℓq quasi-norm regularization, the generated sequence has finite support and sign convergence; SCAD and MCP also satisfy the theorem’s regularity condition.The argument combines a positive lower bound on nonzero components with asymptotic regularity.
  • Relation to prior work: Compared with related methods, this work allows nonconvex nonsmooth proximal terms, estimates asymptotic consensus rates, and establishes global convergence with a fixed step size.The paper contrasts these properties with methods restricted to convex proximal terms or with fixed-step guarantees available only in selected related work.

B. Prox-DGD for decentralized L0 regularization

The L0 experiment applies Prox-DGD to a ten-agent decentralized sparse-recovery model and tests fixed versus decreasing step sizes. The observed trade-offs match the theoretical convergence and consensus claims.

  • Experimental setup: The experiment uses n = 10 agents, p = 256 variables, mi = 150 measurements per agent, and hard thresholding for the ℓ0 proximal operator.Each agent contributes a quadratic data-fidelity term and an ℓ0 penalty with λi = 0.5.
  • Fixed step sizes: Fixed step sizes produce faster convergence for larger steps but also larger consensus error, while convergence is to a Lyapunov-function stationary point rather than necessarily the original problem.The fixed step size must be sufficiently small to satisfy the theoretical restriction.
  • Decreasing step sizes: Decreasing step sizes eliminate the persistent consensus error observed with fixed steps, confirming the motivation for diminishing schedules.Under fixed steps, the consensus error settles to a deterministic nonzero value; decreasing steps overcome this behavior.
  • Rate trade-off: With decreasing steps αk = O(k^-ε), smaller ε generally gives faster convergence but slower consensus, whereas larger ε gives faster consensus.The experiment is presented as verification of the corresponding theoretical rate proposition.

B. Proof for Proposition 2

The proof of Proposition 2 uses the KŁ framework and auxiliary sequence estimates to derive convergence-rate bounds for the relevant iterates and objective quantities.

  • KŁ-based rate analysis: The proof invokes sufficient decrease, lower boundedness, continuity, and the KŁ property to estimate convergence rates in different cases of the KŁ exponent θ.The argument uses a Lyapunov sequence and an induction-based estimate.
  • Auxiliary-sequence argument: Consensus-rate analysis introduces an auxiliary sequence and compares its asymptotic behavior with the original disagreement sequence.The power-convergence estimate depends on the second-largest magnitude eigenvalue ζ of the mixing matrix.

D. Proof for Theorem 2

Theorem 2’s proof combines a reformulation of decreasing-step DGD, weakly summable-sequence arguments, and boundedness to show consensus and stationarity of limit points.

  • Lyapunov convergence: The decreasing-step DGD iterates are rewritten using a varying Lyapunov function, whose descent properties yield convergence of the Lyapunov and objective sequences.The proof also establishes asymptotic regularity through vanishing successive differences.
  • Weak summability: A weakly summable-sequence lemma converts weighted summability and controlled successive changes into convergence to zero.This lemma is the key technical device used for the decreasing-step analysis.
  • Stationarity and whole-sequence convergence: Boundedness provides convergent subsequences, while the consensus result ensures every limit point is consensual and stationary for the original problem.If the limit point is isolated, asymptotic regularity yields convergence of the whole iterate sequence.

E. Proof for Proposition 4

The proposition is established through a sequence of inequalities, consensus lemmas, and bounded-gradient assumptions. Summing these bounds and applying the accumulated-consensus result yields the proposition’s claims.

  • Auxiliary bounds: The analysis uses lemmas for accumulated consensus of iterates and bounded gradients under the proposition’s conditions.These lemmas provide the consensus and gradient controls needed later in the proof.
  • Proof structure: The proof begins by developing an inequality and estimating two terms on its right-hand side.Substitution produces the basic inequality (69).
  • Optimal solution: Because the optimal solution is consensual, the Lyapunov expression at that point equals the optimal objective value.The identity I−W = 0 at xopt gives Lαk(xopt) = fopt.
  • Final bound: Summing the main inequality over iterations and using convexity and bounded gradients produces the required aggregate bound.The resulting constants depend on the initial distance and quantities specified by the consensus lemma.
  • Conclusion: The proposition follows after applying Lemma 14 to the established estimates.The proof explicitly concludes that Lemma 14 supplies the remaining claims.

F. Proofs for Theorem 3 and Proposition 5

Theorem 3 and Proposition 5 rely on sufficient descent, boundedness, and bounded-subgradient properties of the Lyapunov sequence. The proof distinguishes convex and nonconvex proximal functions through different step-size conditions.

  • Sufficient descent: Lemma 16 establishes sufficient descent of the Lyapunov sequence under separate cases for convex and not necessarily convex proximal functions.The two cases impose different assumptions on the proximal terms and step size.
  • Convex case: For convex proximal functions, sufficient descent requires 0 < α < (1+λn(W))/Lf.This condition makes the final term in the descent inequality negative.
  • Boundedness: The Lyapunov sequence is lower bounded, while the iterate sequence is bounded under the conditions of Lemma 16.Boundedness follows from the Lyapunov upper bound and coercivity of each fi+ri.
  • Subgradient control: Lemma 18 supplies a bounded subgradient element from the limiting subdifferential at each new iterate.The construction uses the proximal optimality condition.
  • Theorem and proposition: Lemmas 16–18 are combined to prove Theorem 3 and Proposition 5, with proofs otherwise paralleling earlier results.Theorem 3 is stated to follow a proof pattern similar to Theorem 1, while Proposition 5 parallels Proposition 2.

G. Proofs for Theorem 4 and Proposition 6

Theorem 4 and Proposition 6 are proved using Prox-DGD recursions, proximal optimality conditions, and lemmas controlling descent and iterate behavior. The resulting arguments extend the earlier DGD proof pattern to proximal terms.

  • Iterate recursion: The Prox-DGD iterate recursion is derived in a form analogous to the earlier DGD recursion.This recursion is obtained from the proximal update and supports the subsequent convergence analysis.
  • Proximal terms: The proximal subgradient selected by the operator is explicitly tracked across iterations in the proof.For every prior iterate, ξj+1 is chosen from the subdifferential at xj+1.
  • Descent analysis: Lemma 20 provides the descent estimates needed for Prox-DGD under the stated assumptions and step sizes.Its proof follows the sufficient-descent argument used for Lemma 16.
  • Convex analysis: In the convex case, Lemma 21 establishes a recursion relating distances to an arbitrary reference point and proximal subgradient terms.The recursion is derived using the Lipschitz-gradient inequality and the proximal optimality condition.
  • Final results: Theorem 4 follows from Lemmas 20 and 21, while Proposition 6 uses a uniformly bounded subgradient term.Theorem 4’s cases largely mirror Theorem 2, with an additional Lipschitz condition in one case.

VII. CONCLUSION

The paper analyzes DGD and Prox-DGD for smooth, possibly nonconvex consensus optimization under fixed and decreasing step sizes. It establishes stationary-point and consensus behavior, together with objective-rate and step-size results under specified settings.

  • DGD with fixed step sizes: With a fixed step size, DGD iterates converge to a stationary point of a Lyapunov function approximating the original problem.The paper also bounds each local point’s distance from the global average using the step size and mixing-matrix eigenvalue gap.
  • Consensus error: The local-to-average disagreement bound is proportional to the step size and inversely proportional to the mixing-matrix spectral gap.The relevant gap is between the largest and second-largest magnitude eigenvalues.
  • DGD with decreasing step sizes: With decreasing step sizes, DGD reaches consensus asymptotically at a sublinear rate and converges to a stationary point of the original problem.The paper also estimates convex-setting objective convergence rates for different diminishing-step strategies.
  • Prox-DGD: The convergence results extend to Prox-DGD for sums of differentiable and proximal functions, including cases where both functions are nonconvex.When the proximal function is convex, a larger fixed step size is allowed.
  • Analysis: The results are obtained through existing and new proof techniques.
Loading 1608.05766v4…