PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact Diffusion for Distributed Optimization and Learning --- Part I: Algorithm Development

Kun Yuan, Bicheng Ying, Xiaochuan Zhao, Ali H. Sayed

arXiv:1702.05122v2math.OC

TL;DR

The paper addresses bias and restrictive matrix requirements in distributed diffusion optimization. It derives exact diffusion through a correction-based construction and establishes its applicability to balanced left-stochastic policies. The resulting method converges exactly, with Part II reporting wider stability than EXTRA and simulations supporting the conclusions.

  • Problem

    Existing exact consensus methods are often limited to doubly-stochastic matrices, while standard diffusion converges only to a biased neighborhood.

  • Method

    The paper derives exact diffusion by adding a correction step to diffusion and using a construction based on a penalized problem and incremental descent.

  • Results

    Exact diffusion converges exponentially fast to the exact solution and is applicable to balanced left-stochastic matrices; Part II establishes a wider stability range than EXTRA.

  • Takeaways & Limitations

    Exact diffusion extends exact-convergence guarantees beyond symmetric doubly-stochastic policies while retaining essentially the computational efficiency of standard diffusion.

Abstract

from arXiv · show

This work develops a distributed optimization strategy with guaranteed exact convergence for a broad class of left-stochastic combination policies. The resulting exact diffusion strategy is shown in Part II to have a wider stability range and superior convergence performance than the EXTRA strategy. The exact diffusion solution is applicable to non-symmetric left-stochastic combination matrices, while many earlier developments on exact consensus implementations are limited to doubly-stochastic matrices; these latter matrices impose stringent constraints on the network topology. The derivation of the exact diffusion strategy in this work relies on reformulating the aggregate optimization problem as a penalized problem and resorting to a diagonally-weighted incremental construction. Detailed stability and convergence analyses are pursued in Part II and are facilitated by examining the evolution of the error dynamics in a transformed domain. Numerical simulations illustrate the theoretical conclusions.

I. INTRODUCTION AND MOTIVATION

Distributed optimization methods differ in computational structure, exactness, and matrix requirements. This work develops exact diffusion to remove standard diffusion bias while extending applicability beyond symmetric doubly-stochastic policies.

  • Distributed agents cooperatively minimize a strongly-convex aggregate cost using only neighbor communication.Each local risk function is convex and differentiable, and the global minimizer is unique.
  • Consensus and diffusion differ in update ordering: diffusion uses a symmetric update with coincident iteration and gradient points, yielding a wider stability range.Consensus introduces asymmetry because its recursion starts and evaluates the gradient at different points.
  • EXTRA removes consensus bias and reaches the exact minimizer with computational burden similar to traditional consensus.Its correction combines two prior iterates, while related methods use gradient tracking.
  • Exact diffusion adds a computationally trivial correction step between adaptation and combination, producing an adapt-correct-combine structure.The method retains essentially the computational efficiency of standard diffusion while targeting exact convergence.
  • The approach targets locally balanced left-stochastic matrices, including policies beyond symmetric doubly-stochastic matrices.Earlier algorithms commonly require both rows and columns of the combination matrix to sum to one, whereas this work does not require symmetry.

B. Combination Policy

The paper focuses on balanced left-stochastic policies, a class broader than symmetric doubly-stochastic policies, and develops exact diffusion for them. The local balance condition supports exact convergence while accommodating practical combination rules and preserving undirected-network scope.

  • Local balance: The local balance condition requires each pair of rescaled incoming weights to match: a_ℓk p_k = a_kℓ p_ℓ.Here p is the Perron eigenvector of the primitive left-stochastic matrix A.
  • Local balance: Local balance has an information-cost interpretation: rescaled information flows are equitable across neighboring agents.The weights represent confidence or information flow, while Perron entries represent the associated price paid by agents.
  • Examples: Hastings, averaging, relative-degree, and symmetric doubly-stochastic policies satisfy the conditions needed for the proposed construction.For other locally balanced policies, agents can learn the Perron eigenvector iteratively to adjust step-sizes.
  • Policy classes: Balanced left-stochastic policies extend symmetric doubly-stochastic policies and form the class for which exact convergence is guaranteed.Every symmetric doubly-stochastic matrix is also left-stochastic and balanced; guarantees are not universal across all left-stochastic matrices.
  • Scope and performance: For locally balanced policies, exact diffusion is reported as more communication efficient and more stable than EXTRA and DIGing methods, but it applies to undirected rather than directed graphs.The paper also reports directed-network examples where both exact diffusion and push-sum EXTRA diverge for every step-size.

C. Useful Properties

The local balance condition gives the combination matrix a symmetric, positive-semidefinite structure that exposes consensus as the nullspace and provides favorable spectral properties.

  • Matrix structure: Under local balance, AP − P + I_N is primitive, symmetric, and doubly stochastic.These properties are collected with related results for balanced primitive left-stochastic matrices.
  • Matrix structure: Under local balance, P − AP is symmetric and positive semidefinite.This matrix becomes the central penalty and consensus operator in subsequent formulations.
  • Nullspace: The nullspace of P − AP consists exactly of block vectors whose agent components are all equal.Thus, its nullspace represents network-wide consensus vectors.
  • Spectral properties: A is diagonalizable with real eigenvalues ordered as 1 = λ_1(A) > λ_2(A) ≥ ⋯ ≥ λ_N(A) > −1.The local balance condition makes P^−1/2 A P^1/2 symmetric, supporting the real spectral decomposition.

III. PENALIZED FORMULATION OF DIFFUSION

The paper reformulates diffusion through a penalized formulation to clarify the source of standard diffusion’s O(µ_max^2) bias.

  • Penalized formulation: The unconstrained optimization problem is reformulated as an equivalent constrained problem and then treated using a penalized formulation.This derivation is intended to explain the bias behavior of standard diffusion.

A. Constrained Problem Formulation

The aggregate optimization problem is converted into a consensus-constrained block problem whose constraint is generated by the balanced combination matrix.

  • Constrained formulation: The original unconstrained problem is transformed into an equivalent constrained problem over the stacked agent vector W.The transformation preserves the original optimization solution while making consensus explicit.
  • Consensus constraint: The constraint enforces consensus because the nullspace of V equals that of P − AP, and both contain exactly equal-component block vectors.The factorized operator V is introduced from the eigendecomposition of P − AP.

B. Penalized Formulation

The paper explains standard diffusion as an incremental method for an approximate penalized problem rather than the original constrained problem. This approximation introduces a bias relative to the exact solution, motivating the subsequent exact-diffusion development.

  • Penalized formulation: Penalty methods replace the constrained problem with an approximate unconstrained problem using a positive penalty parameter α.Smaller α makes the penalized and original problem solutions closer, but the problems are not equivalent.
  • Bias: Because the construction solves an approximation, diffusion estimates cannot converge exactly to the true solution w⋆; their bias is related to µmax.The paper identifies this fixed-point bias as the reason exact diffusion is needed.
  • Incremental construction: A diagonally-weighted incremental algorithm can solve the unconstrained penalized formulation.The paper derives the diffusion recursion by applying this incremental construction to the penalized problem.
  • Connection to diffusion: Standard diffusion corresponds to a diagonally-weighted incremental construction for the approximate penalized problem, not the real problem.The derivation uses relations involving the combination matrix and its weighting structure to obtain the diffusion recursions.

IV. DEVELOPMENT OF EXACT DIFFUSION

The paper develops exact diffusion by applying a primal-dual saddle-point approach and a diagonally incremental construction to the original optimization problem. Eliminating the dual variable yields a primal recursion and a distributed implementation with an added correction step.

  • Development of exact diffusion: Exact diffusion is developed by adjusting the standard diffusion strategy to ensure exact convergence to w⋆.The derivation targets the original problem directly rather than the approximate penalized problem.
  • Primal-dual formulation: The method introduces an augmented Lagrangian and applies primal descent together with dual ascent.The first recursion performs primal descent, while the second performs dual ascent.
  • Incremental construction: The primal descent is performed incrementally through a diagonally incremental recursion.This replaces direct descent in the standard primal-dual saddle-point method.
  • Primal recursion: Eliminating the dual variable produces the primal exact-diffusion recursion.The paper identifies this recursion as the primal version of exact diffusion.
  • Distributed implementation: The distributed algorithm adds a correction step between adaptation and combination by removing the previous iterate difference from the intermediate estimate.Exact and standard diffusion otherwise have essentially the same structure and computational burden.
  • Unknown Perron entries: When Perron entries are unavailable, the algorithm can blend a power iteration into the exact-diffusion procedure.The standard implementation assumes the Perron entries are known beforehand; the modified version addresses the unknown case.

V. SIGNIFICANCE OF BALANCED POLICIES

Exact diffusion’s convergence depends critically on the combination policy: balanced policies can support convergence, whereas general unbalanced left-stochastic policies may cause divergence.

  • V. SIGNIFICANCE OF BALANCED POLICIES: Exact diffusion is guaranteed to converge for balanced left-stochastic matrices with sufficiently small step-sizes.The local balancing property is identified as critical for convergence.
  • V. SIGNIFICANCE OF BALANCED POLICIES: The examples show that general left-stochastic policies cannot always guarantee convergence to w_o.The two cases demonstrate both divergence for all tested step-sizes and convergence below a threshold.
  • V. SIGNIFICANCE OF BALANCED POLICIES: Under the stated assumptions, an eigenvalue λ_1 = 1 does not affect convergence because the initialization lies in range(V).The passage notes that the remaining eigenvalues determine the relevant convergence behavior.
  • V. SIGNIFICANCE OF BALANCED POLICIES: The error recursion converges when ρ(F − G_i−1) < 1 and diverges when ρ(F − G_i−1) > 1.The spectral radius determines the stability of recursion (111).
  • V. SIGNIFICANCE OF BALANCED POLICIES: For one unbalanced left-stochastic matrix, ρ(F − G_i−1) > 1 for every tested step-size µ ∈ [10^-6, 3].This example therefore exhibits divergence for any µ > 0.
  • V. SIGNIFICANCE OF BALANCED POLICIES: A second unbalanced left-stochastic example converges when µ < 0.2 because ρ(F − G_i−1) < 1 in that range.The simulations confirm exact convergence to w_o for sufficiently small step-sizes in this setting.

VI. NUMERICAL EXPERIMENTS

The numerical experiments evaluate convergence using relative error relative to the initial error and the exact optimizer.

  • VI. NUMERICAL EXPERIMENTS: All figures plot relative error, defined as ∥W_i − W_o∥2/∥W_0 − W_o∥2.Here W_i stacks the agents’ iterates and W_o stacks copies of the optimizer.
  • VI. NUMERICAL EXPERIMENTS: The relative-error metric compares the current network iterate W_i with the optimizer W_o.The denominator normalizes by the initial distance from the optimizer.
  • VI. NUMERICAL EXPERIMENTS: The experiments use the same relative-error convention across the displayed convergence figures.The passage states that the y-axis indicates this quantity in all figures.

A. Distributed Least-squares

On a 20-agent distributed least-squares problem, exact diffusion reaches the exact solution exponentially fast, while standard diffusion retains an O(µ_o^2) bias neighborhood.

  • A. Distributed Least-squares: N = 20 agents solve a distributed least-squares problem with parameter dimension M = 30.Each agent’s U_k and d_k entries are generated from N(0, 1).
  • A. Distributed Least-squares: The comparison uses a left-stochastic matrix generated by the averaging rule and step-sizes µ_k = µ_o/n_k.The experiment sets µ_o = 0.01.
  • A. Distributed Least-squares: Standard diffusion converges to a neighborhood of w_o on the order O(µ_o^2), whereas exact diffusion converges exponentially fast to w_o.The figure is presented as confirming that exact diffusion corrects standard diffusion’s bias.

B. Distributed Logistic Regression

The experiments compare exact diffusion with standard diffusion across logistic regression and highly unbalanced networks, showing bias correction, faster averaging-rule convergence, and policy-dependent stability.

  • B. Distributed Logistic Regression: The logistic-regression experiment uses N = 20 agents, parameter dimension M = 30, and L = 50 local samples per agent.Labels are generated from a logistic model with ρ = 0.1.
  • B. Distributed Logistic Regression: In distributed logistic regression, exact diffusion corrects the bias observed with standard diffusion.The comparison uses µ_o = 0.05 with µ_k = µ_o/n_k.
  • C. Averaging Rule v.s. Doubly Stochastic Rules: In the highly unbalanced topology, the averaging rule is almost three times faster than the doubly-stochastic rule.The comparison concerns distributed least-squares with each matrix tuned for fastest convergence.
  • D. Exact Diffusion for General Left-Stochastic A: For the Example 1 general left-stochastic policy, exact diffusion diverges because ρ > 1 for every µ ∈ [10^-6, 3].At µ = 0.01, standard diffusion converges to an O(µ^2) neighborhood while exact diffusion diverges.
  • D. Exact Diffusion for General Left-Stochastic A: For the Example 2 policy, exact diffusion converges when µ < 0.2 and reaches w_o exactly at µ = 0.001.These cases show that general left-stochastic policies do not universally guarantee convergence.
  • B. Distributed Logistic Regression: The proposed strategy targets exact convergence for a broad class of combination policies, including non-symmetric left-stochastic matrices.Earlier exact-consensus developments were limited to doubly-stochastic or right-stochastic matrices.

APPENDIX A PROOF OF (121)

The appendix applies the Jury stability criterion to the seventh-order polynomial D(λ) and shows that no step-size makes all stability conditions hold. Thus, D(λ) is unstable for every step-size μ.

  • Role of the unit eigenvalue: The eigenvalue λ = 1 does not determine convergence here because the initialization places W0 in range(V).The roots of D(λ), rather than this eigenvalue, decide convergence of recursion (111).
  • Jury table construction: Because D(λ) is seventh order, the proof constructs a Jury table instead of calculating its roots directly.The table is formed using the coefficient combinations defined in (132)–(134).
  • Jury stability criterion: The Jury criterion requires eight conditions, including endpoint inequalities and coefficient-magnitude comparisons.These conditions are necessary and sufficient for all roots of D(λ) to lie within the unit-circle.
  • Condition checking: The condition (−1)^7D(−1) > 0 holds when μ < 0.1265 or μ > 3.0410.This is one of the step-size restrictions checked in the Jury analysis.
  • Jury stability conclusion: D(λ) is not stable for any step-size μ because the required stability-range intersection is empty.The ranges in (141), (142), and (143) cannot be satisfied simultaneously, so conditions (1)–(8) cannot all hold.
Loading 1702.05122v2…