PaperlayerView exact revision on arXiv

Source-linked AI summary

A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates

Zhi Li, Wei Shi, Ming Yan

arXiv:1704.07807v2math.OCcs.DCcs.LGmath.NAstat.ML

TL;DR

The paper studies decentralized composite optimization with privately held smooth and nonsmooth objectives over a communication network. It proposes NIDS, a proximal-gradient method with independently selected, network-independent step-sizes, and reports sublinear convergence generally plus separated linear convergence in a smooth strongly convex special case.

Abstract

from arXiv · show

This paper proposes a novel proximal-gradient algorithm for a decentralized optimization problem with a composite objective containing smooth and non-smooth terms. Specifically, the smooth and nonsmooth terms are dealt with by gradient and proximal updates, respectively. The proposed algorithm is closely related to a previous algorithm, PG-EXTRA \cite{shi2015proximal}, but has a few advantages. First of all, agents use uncoordinated step-sizes, and the stable upper bounds on step-sizes are independent of network topologies. The step-sizes depend on local objective functions, and they can be as large as those of the gradient descent. Secondly, for the special case without non-smooth terms, linear convergence can be achieved under the strong convexity assumption. The dependence of the convergence rate on the objective functions and the network are separated, and the convergence rate of the new algorithm is as good as one of the two convergence rates that match the typical rates for the general gradient descent and the consensus averaging. We provide numerical experiments to demonstrate the efficacy of the introduced algorithm and validate our theoretical discoveries.

I. INTRODUCTION

The paper addresses decentralized composite optimization over connected networks, where agents privately hold smooth and proximable nonsmooth objectives. It introduces NIDS, targeting network-independent local step-sizes and convergence rates that separate objective and network effects.

Problem setting

  • Agents solve a composite decentralized optimization problem using local smooth and nonsmooth objective terms while communicating only with immediate neighbors.The smooth term has a Lipschitz gradient, and the nonsmooth term is proximable.Source: §I · p. 1

Proposed method

Step-size advantage

  • NIDS permits independently chosen local step-sizes based on objective functions, with an upper bound as large as 2/L and no network-topology dependence.A common public parameter can be selected without knowledge of the mixing matrix.Source: B. Proposed Algorithm and its Advantages · p. 3

Convergence results

  • For general convex objectives, NIDS achieves an o(1/k) convergence rate, reported as slightly better than PG-EXTRA’s O(1/k) rate.The paper attributes potentially faster numerical performance to larger, topology-independent step-sizes.Source: B. Proposed Algorithm and its Advantages · p. 3
  • With no nonsmooth terms and strongly convex local functions, NIDS has linear convergence whose objective-function and network dependencies are separated.The resulting factors align with typical gradient-descent and consensus-averaging rates, helping identify the bottleneck and motivate preconditioning.Source: B. Proposed Algorithm and its Advantages · pp. 3–4

C. Future Works

The paper identifies locally determined parameters as a basis for extending the algorithm to dynamic networks and decentralized empirical risk minimization.

  • Purely local parameters may support extensions to dynamic networks with a time-varying number of nodes.Source: C. Future Works · p. 5
  • The authors identify decentralized empirical risk minimization as a potential application of similar schemes.Source: C. Future Works · p. 5
  • The paper leaves convergence rates and scalability for a Nesterov-accelerated version of the algorithm as future work.Source: C. Future Works · p. 5

D. Paper Organization

The paper develops NIDS for composite decentralized optimization, relates it to existing primal-dual and proximal-gradient methods, and explains its network-independent step-size design.

II. INTUITION FOR NETWORK-INDEPENDENT STEP-SIZE

  • With a block diagonal metric, the forward-step nonexpansiveness depends on the objective function only, yielding α ≤ 2/L.Source: §II · p. 6

Assumptions

  • The paper assumes a connected undirected network whose symmetric mixing matrix has the stated null-space and spectral properties.Source: §III · p. 7

III. PROPOSED ALGORITHM NIDS

  • For heterogeneous agents, NIDS uses local Lipschitz constants and permits step-sizes as large as 2/L_i on any connected network.Source: §III · p. 7
  • NIDS allows each agent to choose its own step-size α_i while using a common parameter c and locally constructed mixing values.Source: §III · pp. 6–7
  • Choosing c = 1/(2 max_i α_i) avoids requiring network information, although a preprocessing step is used to obtain the maximum step-size.Source: §III · p. 7
  • NIDS differs from PG-EXTRA by applying the mixing operation to successive gradient differences in addition to the estimations.Source: §III · p. 7

IV. CONVERGENCE ANALYSIS OF NIDS

The convergence analysis reformulates NIDS as an iteration over auxiliary variables, connects its fixed points to optimal solutions, and establishes the analytical tools used for convergence.

IV. CONVERGENCE ANALYSIS OF NIDS

  • The analysis introduces a sequence {d_k} and shows that the original iteration generates the same {x_k, z_k} sequence under an equivalent update order.Source: §IV · pp. 7–8
  • Because x_k is determined by z_k, the reformulated iteration operates essentially on (d, z), with d_k remaining in range(I − W).Source: §IV · p. 8
  • A fixed point of iteration (12) is characterized using a subgradient q* and the relation z* = x* + Λq*.Source: §IV · p. 8
  • An optimal solution is consensual and corresponds to a fixed point with d* ∈ range(I − W).Source: §IV · p. 8
  • The analysis defines a norm on range(I − W) through a matrix M satisfying the stated semidefinite condition.Source: §IV · p. 8
  • A fundamental inequality compares the distance between consecutive iterates and a fixed point, supporting the subsequent convergence arguments.Source: §IV · p. 8

A. Sublinear convergence of NIDS

The sublinear analysis applies a primal-dual convergence theorem to NIDS under step-size and matrix conditions, showing convergence of its iterates and derived quantities.

B. Linear convergence for special cases

For r(x)=0, NIDS achieves linear convergence under strong convexity, with convergence-rate dependence separated between objective functions and network structure. This separation can guide step-size and consensus choices.

V. NUMERICAL EXPERIMENTS

The numerical experiments compare NIDS with several decentralized optimization methods under specified network and implementation settings. The comparisons include proximal, gradient-tracking, accelerated, and optimal distributed algorithms.

  • The experiments compare NIDS with EXTRA/PG-EXTRA, DIGing-ATC, accelerated distributed Nesterov gradient descent, and a dual-friendly optimal algorithm.Source: §V · p. 11
  • DIGing-ATC and Acc-DNGD-SC use two communication rounds per iteration, whereas EXTRA, NIDS, and OA use one.Source: §V · p. 11
  • The exact solution x∗ is computed centrally using centralized proximal gradient descent before the experiments.Source: §V · p. 11
  • Networks are randomly generated by connectivity ratio τ, and mixing matrices use the Metropolis rule.Source: §V · p. 11
  • Experiments are run in Matlab R2016b on a laptop, with source code provided for reproducing the numerical results.Source: §V · p. 11

A. The strongly convex case with r(x) = 0

For strongly convex problems with r(x)=0, experiments evaluate relative error across network settings and heterogeneous local smoothness constants. NIDS is tested with common and adaptive local step-sizes.

B. The case with nonsmooth function r(x)

NIDS is evaluated on decentralized nonsmooth problems, where larger network-independent step-sizes improve convergence relative to PG-EXTRA while preserving convergence. Experiments also assess sparse classification accuracy, consensus, and sparsity.

Decentralized compressed sensing

  • NIDS is compared with PG-EXTRA on a decentralized compressed sensing problem with sparse signals and nonsmooth regularization.Each agent holds noisy linear measurements, and the optimization promotes a sparse solution.Source: B. The case with nonsmooth function r(x) · p. 12
  • Step-size 1 gives NIDS and PG-EXTRA the same convergence speed, while NIDS remains convergent at step-size 1.9 after PG-EXTRA diverges at 1.4.The comparison uses a network connectivity ratio τ = 0.1 and normalizes each local Lipschitz constant to 1.Source: B. The case with nonsmooth function r(x) · p. 12

Sparse logistic regression

  • The sparse logistic regression experiment uses 50 connected nodes, one training sample per node, and a 2,000-feature colon-cancer dataset.The data contain 62 samples: 22 normal and 40 tumor tissue samples.Source: C. An application in classification… · pp. 12–13
  • The optimization combines an ℓ2 term imposing strong convexity with an ℓ1 term promoting sparsity in the learned classifier.Prediction performance is evaluated on 12 held-out samples, while additional plots track consensus error and sparsity.Source: C. An application in classification… · p. 13

Theoretical summary

  • The conclusion states that NIDS supports independently chosen local step-sizes, rates o(1/k) for general convex objectives, and linear convergence for strongly convex objectives.The stated step-size can be as large as 2/L, where L is the smooth-gradient Lipschitz constant.Source: §VI · p. 13

A. Proof of Lemma 1

The proof characterizes fixed points of NIDS and shows that they correspond to consensual optimal solutions through subgradient and network-range conditions.

Fixed-point characterization

Optimality condition

  • A consensual x* is optimal if and only if there exist p* and q* ∈ ∂r(x*) satisfying the stated network-coupled optimality conditions.Consensus follows from the nullspace of I − W, while the subgradient condition yields optimality.Source: B. Proof of Lemma 2 · p. 16

Range-space norm

  • For a positive-semidefinite matrix A, the proof defines a range-space norm using the pseudoinverse A†.The construction uses the eigendecomposition of A and its positive eigenvalues.Source: C. Proof of Lemma 3 · p. 16

D. Proof of Proposition 1

The proposition proves that a matrix constructed from the network Laplacian-like term and local step-size matrix defines a valid norm on range(I − W).

Norm construction

  • M = c^-1(I − W)† − Λ defines a norm on range(I − W) when I ≽ cΛ^1/2(I − W)Λ^1/2 ≽ 0.Λ is symmetric positive definite, and the proof rewrites M before applying the range-space norm lemma.Source: D. Proof of Proposition 1 · pp. 16–17

E. Proof of Theorem 1

The theorem proof establishes descent and monotonicity properties for NIDS, then uses them to prove sublinear convergence and convergence to a fixed point under network-dependent matrix conditions.

Descent and monotonicity

  • The proof begins with descent and successive-difference lemmas showing that distances and a special-norm difference measure decrease.These lemmas provide the inequalities used in the convergence argument.Source: E. Proof of Theorem 1 · p. 17
  • Young’s inequality and the algorithmic condition produce the key descent inequality used to control the NIDS iterates.The proof derives this inequality from the update relation and the step-size condition.Source: E. Proof of Theorem 1 · p. 17
  • The successive-difference sequence is monotonically nonincreasing under α_i < 2/L_i and I ≽ cΛ^1/2(I − W)Λ^1/2.The proof obtains this by comparing consecutive inequalities and applying Cauchy–Schwarz-related bounds.Source: E. Proof of Theorem 1 · pp. 17–18

Sublinear convergence

  • Theorem 1 establishes an o(1/k) sublinear rate when every local step-size satisfies α_i < 2/L_i and the matrix condition holds.The result is stated for the sequence generated by NIDS in iteration (12).Source: E. Proof of Theorem 1 · p. 18

Fixed-point convergence

  • Under the strict condition I ≻ cΛ^1/2(I − W)Λ^1/2, the iterates converge to a fixed point with d̄ ∈ range(I − W).Boundedness, a convergent subsequence, and the key inequality are used to extend subsequence convergence to the full sequence.Source: E. Proof of Theorem 1 · p. 18

Related papers

Loading 1704.07807v2…