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.

  • Problem

    Decentralized composite optimization requires agents to collaboratively solve privately held objectives over networks without a master agent, while existing methods can use conservative or network-dependent step-sizes.

  • Method

    NIDS modifies PG-EXTRA by exchanging gradient-adapted estimations and applying gradient and proximal updates to the smooth and nonsmooth terms.

  • Results

    NIDS achieves o(1/k) convergence for general convex objectives and linear convergence for smooth strongly convex objectives, with objective and network dependencies separated in the latter case.

  • Takeaways & Limitations

    Agents can choose local step-sizes independently from their objective functions, with bounds as large as 2/L, while numerical experiments report better performance than state-of-the-art algorithms.

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.
  • Proposed method: NIDS modifies PG-EXTRA by exchanging gradient-adapted estimations rather than only estimation differences.This modification yields the algorithm’s network-independent step-size property.
  • 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.
  • 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.
  • Convergence results: 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.

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.
  • The authors identify decentralized empirical risk minimization as a potential application of similar schemes.
  • The paper leaves convergence rates and scalability for a Nesterov-accelerated version of the algorithm as future work.

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.
  • Assumptions: The paper assumes a connected undirected network whose symmetric mixing matrix has the stated null-space and spectral properties.
  • 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.
  • III. PROPOSED ALGORITHM NIDS: NIDS allows each agent to choose its own step-size α_i while using a common parameter c and locally constructed mixing values.
  • III. PROPOSED ALGORITHM NIDS: Choosing c = 1/(2 max_i α_i) avoids requiring network information, although a preprocessing step is used to obtain the maximum step-size.
  • III. PROPOSED ALGORITHM NIDS: NIDS differs from PG-EXTRA by applying the mixing operation to successive gradient differences in addition to the estimations.

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.
  • IV. CONVERGENCE ANALYSIS OF NIDS: Because x_k is determined by z_k, the reformulated iteration operates essentially on (d, z), with d_k remaining in range(I − W).
  • IV. CONVERGENCE ANALYSIS OF NIDS: A fixed point of iteration (12) is characterized using a subgradient q* and the relation z* = x* + Λq*.
  • IV. CONVERGENCE ANALYSIS OF NIDS: An optimal solution is consensual and corresponds to a fixed point with d* ∈ range(I − W).
  • IV. CONVERGENCE ANALYSIS OF NIDS: The analysis defines a norm on range(I − W) through a matrix M satisfying the stated semidefinite condition.
  • IV. CONVERGENCE ANALYSIS OF NIDS: A fundamental inequality compares the distance between consecutive iterates and a fixed point, supporting the subsequent convergence arguments.

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.

  • Theorem 1 establishes a sublinear convergence result for NIDS when α_i < 2/L_i and I ≽ cΛ^1/2(I − W)Λ^1/2.
  • Under the strict matrix inequality, (d_k, z_k) converges to a fixed point whose d-coordinate lies in range(I − W).
  • The analysis separately relates convergence in z and d to convergence in the quantities indexed by (14).

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.

  • NIDS has a linear convergence rate when the nonsmooth term vanishes and the objective functions are strongly convex.
  • Choosing α = 1/max_i L_i and c = 1/((1−λ_n(W))α) yields a rate with decoupled network and functional impacts.
  • Without λ_n(W), choosing c = 1/(2 max_i α_i) avoids requiring network information but couples network impact with smoothness heterogeneity.
  • The convergence rate can separate functional condition-number effects from network effects.This separation helps identify the bottleneck for a particular problem and network.
  • If proximal-gradient steps are expensive, the explicit rate formula can inform whether multi-step consensus reduces computational time.
  • When L/µ = 1, decentralized optimization is network-limited because centralized gradient descent reaches the optimum in one step.
  • Preconditioning through x = By is suggested for function-limited cases, but reducing function condition numbers is left as future work.

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.
  • DIGing-ATC and Acc-DNGD-SC use two communication rounds per iteration, whereas EXTRA, NIDS, and OA use one.
  • The exact solution x∗ is computed centrally using centralized proximal gradient descent before the experiments.
  • Networks are randomly generated by connectivity ratio τ, and mixing matrices use the Metropolis rule.
  • Experiments are run in Matlab R2016b on a laptop, with source code provided for reproducing the numerical results.

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.

  • The signal-estimation experiment uses yi = M_i x + e_i, with agents collaboratively estimating x through decentralized optimization.
  • With L_i = 1 and µ_i = 0.5 for all agents, NIDS uses α = 1 and compares network-aware and fixed c choices.
  • NIDS with c = 1/((1−λ_n(W))α) uses fewer than half as many iterations as EXTRA to reach the same accuracy.
  • The comparison includes NIDS, EXTRA, DIGing-ATC, Acc-DNGD-SC, and OA across networks with connectivity ratios τ = 0.35 and τ = 0.45.
  • When local smoothness constants are heterogeneous, adaptive step-size NIDS uses 1/L_i while the common-step variant uses 1/max_i L_i.
  • In the heterogeneous experiment, adaptive-step NIDS converges faster than the same-step-size variant without requiring network information.

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.
  • Decentralized compressed sensing: 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.
  • 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.
  • Sparse logistic regression: 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.
  • 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.

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: A fixed point is represented as d* = (I − W)p* and z* = x* + Λq*, with q* ∈ ∂r(x*).The fixed-point characterization is established in both directions.
  • 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.
  • 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.

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.

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.
  • Descent and monotonicity: 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.
  • Descent and monotonicity: 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.
  • 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).
  • 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.
Loading 1704.07807v2…