PaperlayerView exact revision on arXiv

Source-linked AI summary

Decentralized Proximal Gradient Algorithms with Linear Convergence Rates

Sulaiman A. Alghunaim, Ernest K. Ryu, Kun Yuan, Ali H. Sayed

arXiv:1909.06479v3math.OC

TL;DR

Decentralized optimization with local costs and a common nonsmooth term raises the question of exact convergence under local communication. This paper develops a primal-dual framework and establishes linear convergence for the shared-term setting, alongside a numerical counterexample involving local nonsmooth terms.

  • Problem

    The paper studies decentralized minimization of local costs plus a common nonsmooth term through communication among neighboring agents.

    Source: §I · p. 2

  • Method

    The authors extend a unified primal-dual decentralized algorithm framework to handle a common nonsmooth regularization term.

    Source: B. Contribution · p. 3

  • Results

    Under proper conditions, the framework provides linear convergence for a common nonsmooth term, while a counterexample shows PG-EXTRA and proximal linearized ADMM, fail to converge linearly for strongly convex objectives.

    Source: B. Contribution · pp. 3–4

  • Takeaways & Limitations

    The step-size and convergence-rate upper bounds shed light on the stability and performance of the methods.

    Source: B. Contribution · p. 4

    The analysis comes at the expense of stronger assumptions on the combination matrices.

    Source: §VII · p. 16

Abstract

from arXiv · show

This work studies a class of non-smooth decentralized multi-agent optimization problems where the agents aim at minimizing a sum of local strongly-convex smooth components plus a common non-smooth term. We propose a general primal-dual algorithmic framework that unifies many existing state-of-the-art algorithms. We establish linear convergence of the proposed method to the exact solution in the presence of the non-smooth term. Moreover, for the more general class of problems with agent specific non-smooth terms, we show that linear convergence cannot be achieved (in the worst case) for the class of algorithms that uses the gradients and the proximal mappings of the smooth and non-smooth parts, respectively. We further provide a numerical counterexample that shows how some state-of-the-art algorithms fail to converge linearly for strongly-convex objectives and different local non-smooth terms.

I. INTRODUCTION

The paper studies decentralized minimization of local strongly convex costs plus a shared convex, possibly nonsmooth term, using communication between neighboring agents. Under its assumptions, the global solution is unique.

I. INTRODUCTION

  • Agents seek to minimize an objective involving their private local costs and a common convex term that need not be differentiable.The network is static and undirected, and agents communicate only with immediate neighbors.Source: §I · pp. 1–2
  • Strong convexity of the objective guarantees a unique global solution.The paper assumes each local cost is differentiable and strongly convex, and that a solution exists; the smooth gradients are Lipschitz continuous.Source: §I · p. 2

A. Related Works

Prior work covers many decentralized algorithms, but existing frameworks and convergence analyses do not encompass all algorithm classes or general agent-specific nonsmooth terms. This paper unifies several methods and studies the common-term setting and the limits of linear convergence with local terms.

A. Related Works

  • Earlier canonical forms cover some decentralized algorithms but exclude ATC gradient tracking or focus on characterization rather than analysis, [17].The method in includes EXTRA and DIGing for static undirected networks, but not ATC gradient-tracking algorithms [1],,.Source: A. Related Works · p. 2
  • The proposed primal-dual framework unifies EXTRA, DLM, Exact diffusion, NIDS, and gradient-tracking methods including Aug-DGM.It represents ATC gradient-tracking methods as primal-dual recursions, an interpretation the authors identify as new for those methods,,,.Source: A. Related Works · p. 3
  • A proximal-gradient method in [20] established exact linear convergence for the smooth problem, and this work extends the framework to a common nonsmooth term.The proposed method is shown to converge linearly to the exact solution in that setting.Source: A. Related Works · p. 3
  • For agent-specific nonsmooth terms, prior methods had not been shown to achieve global linear convergence, and the question remained unresolved.The paper adapts a result from to show that proximal-gradient algorithms cannot guarantee linear convergence in the worst case for this setup.Source: A. Related Works · p. 3
  • In the worst case, no proximal-gradient-based algorithm achieves linear convergence for non-smooth strongly-convex functions when limited to one communication round but allowed unlimited computation and function access per iteration.In contrast, the considered algorithms allow unlimited communication rounds but are limited to one gradient and proximal computation per iteration.Source: A. Related Works · p. 3

B. Contribution

The contributions are a primal-dual unification of decentralized algorithms, a linear-convergence framework for a shared nonsmooth term, and worst-case and numerical evidence about local nonsmooth terms.

B. Contribution

  • When R(w) = 0, the authors propose a primal-dual unified decentralized algorithm that covers ATC and non-ATC methods.The unified set includes gradient-tracking algorithms and state-of-the-art methods; the paper calls this the first primal-dual interpretation of ATC gradient tracking,,,.Source: B. Contribution · p. 3
  • The framework extends to a common nonsmooth regularization term and provides a linear-convergence analysis under proper conditions.Its step-size and convergence-rate upper bounds shed light on the stability and performance of the methods.Source: B. Contribution · pp. 3–4
  • With agent-specific nonsmooth terms, exact linear convergence is impossible in the worst case for the considered class of decentralized algorithms.The result tailors a lower-bound result from.Source: B. Contribution · p. 4
  • A numerical counterexample shows PG-EXTRA and proximal linearized ADMM, fail to converge linearly for strongly convex objectives.Each agent can compute one gradient and one proximal mapping per iteration for the smooth and nonsmooth parts, respectively.Source: B. Contribution · p. 4

C. Notation

The notation section specifies matrix and vector conventions and defines the subdifferential used in the paper.

C. Notation

  • The paper defines matrix singular-value notation and matrix ordering, along with identity matrices, all-ones vectors, Kronecker products, and stacked vectors or matrices.It uses σmax(A) for the maximum singular value and σ(A) for the minimum nonzero singular value.Source: C. Notation · p. 4
  • The subdifferential ∂f(x) is defined as the set of vectors satisfying the paper's inequality for every y.The notation section also introduces a proximal operator with parameter μ > 0.Source: C. Notation · p. 4

II. UNIFIED DECENTRALIZED ALGORITHM (UDA)

The unified decentralized algorithm (UDA) covers various state-of-the-art algorithms as special cases. This section first treats the smooth case, then extends the method to include the non-smooth component.

II. UNIFIED DECENTRALIZED ALGORITHM (UDA)

  • UDA covers various state-of-the-art algorithms as special cases.Source: §II · p. 4
  • The section first focuses on the smooth case, with R(w) = 0.Source: §II · p. 4
  • The smooth-case treatment is extended to handle the non-smooth component R(w) in the following section.Source: §II · p. 4

A. General Primal-Dual Framework

The framework rewrites the smooth problem using local copies and a saddle-point formulation, then applies gradient and combination steps. Proper matrix choices recover state-of-the-art algorithms.

A. General Primal-Dual Framework

B. Network Combination Matrix

The network combination matrix is constrained by graph connectivity and stochasticity conditions. Under these conditions, its consensus constraint holds exactly when all agents’ local values agree.

B. Network Combination Matrix

C. Specific Instances

The section rewrites the UDA recursion and uses specific matrix choices to recover existing decentralized algorithms. One instance follows from the stated parameter choices for [10].

C. Specific Instances

1) Exact diffusion

The section derives exact diffusion from an equivalent rewriting of the unified decentralized recursion and relates a parameterized smooth NIDS case to it.

1) Exact diffusion

  • The recursion is rewritten by eliminating the dual variable and multiplying by the combination matrix before identifying exact diffusion.Source: 1) Exact diffusion · p. 6
  • The resulting recursion is the exact diffusion method first proposed in.Source: 1) Exact diffusion · p. 6
  • With C = 0, B2 = c(I − A), and Ā = I − B2, the smooth NIDS case is recovered and matches exact diffusion when c = 0.5.Source: 1) Exact diffusion · p. 6

2) Aug-DGM

The section connects several decentralized algorithms through a shared recursion, extends the framework to a common nonsmooth term, and establishes linear convergence under stated conditions.

2) Aug-DGM

  • The recursion is equivalent to Aug-DGM, also known as ATC-DIGing.Source: 2) Aug-DGM · p. 6

Appendix B.

  • Table I lists state-of-the-art first-order algorithms recoverable through specific choices of the framework matrices.Source: Table I · p. 7

3) ATC tracking method

  • ATC tracking methods require two communication rounds per iteration, and Aug-DGM additionally sends its two variables sequentially.Source: 3) ATC tracking method · p. 8

III. PROXIMAL UNIFIED DECENTRALIZED ALGORITHM (PUDA)

  • PUDA extends UDA to include the nondifferentiable component R(w), with a unique fixed point whose W⋆ equals the replicated optimizer.Source: §III · p. 8

IV. LINEAR CONVERGENCE

  • PUDA converges linearly to the solution when Assumptions 1–2 hold, Y0 = 0, and the step size satisfies Theorem 1.Its unique W⋆ equals 1K ⊗ w⋆, where w⋆ solves problem (1).Source: §III · p. 8, §IV · p. 10
  • For C = 0, the step-size bound is network-independent and as large as centralized proximal gradient descent, while the rate separates network and cost effects.Source: §IV · p. 11

V. SIMULATIONS ON REAL DATA

This section examines the framework’s scope and convergence behavior through theoretical analyses and simulations on real data. It includes fixed-point and algorithm-equivalence arguments, convergence analyses under stated conditions, and comparisons of algorithms in the tested setups.

V. SIMULATIONS ON REAL DATA

  • Prox-ED performs best in the real-data simulations, while performance varies by dataset and Prox-ATC I/II use two communication rounds per iteration versus one for the other algorithms.The comparison uses Covtype.binary, MNIST, and CIFAR-10; Figure 2 plots relative squared error against communication rounds per iteration.Source: §V · p. 12, Figure 2 · p. 13

A. Sublinear Lower Bound

  • O(G/sqrt(nu epsilon)) or more iterations are required in the worst case for agent-specific non-smooth terms under local function, gradient, and proximal queries.For 0 < epsilon < G^2/(288 nu) and sufficiently large dimension M = O(KG/sqrt(nu epsilon)), this lower bound rules out global linear convergence in the worst case for the stated algorithm class.Source: A. Sublinear Lower Bound · pp. 14–15
  • The lower bound excludes dimension-independent linear rates, but dimension-dependent linear convergence may still be possible in special cases.The paper contrasts this limitation with its own dimension-independent linear convergence result for any dimension M.Source: A. Sublinear Lower Bound · p. 15

B. Numerical Counterexample

  • PG-EXTRA [21] and DL-ADMM, converge sublinearly to the counterexample solution; their error curves show this after around 10^3 iterations, with no global linear convergence observed for sufficiently large M and algorithms independent of M.In Fig. 3’s right plot, both axes are logarithmic.Source: B. Numerical Counterexample · p. 16, Figure 3 · p. 16

VII. CONCLUDING REMARKS

  • The proximal primal-dual framework subsumes many smooth-case algorithms and converges linearly for strongly convex objectives; its wider step-size bounds require stronger assumptions on combination matrices.The authors identify studying the step-size and combination-matrix interrelation as future work.Source: §VII · p. 16
  • The authors identify optimally choosing Ā, B, and C as a function of A to improve convergence rate while balancing communication cost as future work.The conclusion also calls for studying how step sizes and combination matrices interact for linear convergence.Source: §VII · p. 16

APPENDIX A

  • Appendix A constructs and characterizes a unique fixed point whose primal component is the solution to problem (1).The construction uses strong convexity to ensure a unique solution; the fixed-point characterization shows W⋆=1_K⊗w⋆ and that W⋆ and Z⋆ are unique.Source: Appendix A · pp. 19–20

A. Prox-ED: ¯

APPENDIX D

APPENDIX E

Loading 1909.06479v3…