Source-linked AI summary
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
Wei Shi, Qing Ling, Gang Wu, Wotao Yin
TL;DR
The paper addresses the accuracy–speed dilemma in decentralized gradient descent, where fixed steps leave neighborhood error while diminishing steps slow exact convergence. It proposes EXTRA, an exact decentralized first-order method, with theoretical convergence results and numerical evidence that it continues progressing after fixed-step DGD stalls.
Problem
Fixed-step decentralized gradient methods converge only to an O(α)-neighborhood, while reducing the step size enables exact convergence but causes slower convergence.
Method
EXTRA is a decentralized first-order algorithm that uses cumulative correction terms to neutralize the gradient component orthogonal to consensus.
Results
EXTRA has theoretical convergence under convexity and linear convergence when the objective is restricted strongly convex, with numerical simulations verifying the theoretical results.
Takeaways & Limitations
EXTRA uses a fixed large step size and quickly returns an accurate solution, while fixed-step DGD eventually stalls and EXTRA continues progressing.
Takeaways & Limitations
The paper restricts its treatment to the synchronous case, leaving adaptation to asynchronous and dynamic settings for future work.
Abstract
from arXiv · showhide
Recently, there have been growing interests in solving consensus optimization problems in a multi-agent network. In this paper, we develop a decentralized algorithm for the consensus optimization problem $$\min\limits_{x\in\mathbb{R}^p}~\bar{f}(x)=\frac{1}{n}\sum\limits_{i=1}^n f_i(x),$$ which is defined over a connected network of $n$ agents, where each function $f_i$ is held privately by agent $i$ and encodes the agent's data and objective. All the agents shall collaboratively find the minimizer while each agent can only communicate with its neighbors. Such a computation scheme avoids a data fusion center or long-distance communication and offers better load balance to the network. This paper proposes a novel decentralized EXact firsT-ordeR Algorithm (abbreviated as EXTRA) to solve the consensus optimization problem. "exact" means that it can converge to the exact solution. EXTRA can use a fixed large step size, {which is independent of the network size}, and has synchronized iterations. The local variable of every agent $i$ converges uniformly and consensually to an exact minimizer of $\bar{f}$. In contrast, the well-known decentralized gradient descent (DGD) method must use diminishing step sizes in order to converge to an exact minimizer. EXTRA and DGD have the same choice of mixing matrices and similar per-iteration complexity. EXTRA, however, uses the gradients of last two iterates, unlike DGD which uses just that of last iterate. EXTRA has the best known convergence rates among the existing first-order decentralized algorithms. Specifically, if $f_i$'s are convex and have Lipschitz continuous gradients, EXTRA has an ergodic convergence rate $O(\frac{1}{k})$ in terms of the first-order optimality residual. If $\bar{f}$ is also restricted strongly convex, EXTRA converges to an optimal solution at a linear rate $O(C^{-k})$ for some constant $C>1$.
1. Introduction.
The paper introduces EXTRA, a synchronous decentralized gradient algorithm for consensus optimization, addressing DGD’s trade-off between exactness and speed. It establishes convergence guarantees and reports numerical comparisons with decentralized gradient descent.
- Problem and setting: EXTRA addresses decentralized consensus optimization over connected networks, where agents privately hold convex local functions and update synchronously.Each agent maintains a local copy of the common variable and uses decentralized computation based on local and neighbor information.
- Limitations of existing methods: Fixed-step-size DGD converges only near a solution, whereas diminishing stepsizes enable exact convergence but slow the method.With a fixed stepsize, agents may converge to different points in an O(α)-neighborhood; reducing the stepsize supports exact consensus but worsens convergence speed.
- Convergence guarantees: O(1/k) convergence is established for general convex objectives with Lipschitz differentials, measured by the best running first-order optimality violation.When the aggregate objective is also restricted strongly convex, the convergence rate is linear.
- Empirical evaluation: Numerical simulations verify the theoretical results and compare EXTRA with decentralized gradient descent.In one least-squares experiment, fixed-step DGD eventually stalls while EXTRA continues progressing after both initially show similar linear convergence.
- EXTRA: EXTRA is a synchronous gradient-based method derived by differencing two DGD updates and correcting cumulative disagreement terms.Its correction term neutralizes gradient components orthogonal to the consensus subspace, supporting consensual optimality.
2. Algorithm Development.
The section explains why fixed-step DGD is inexact and develops EXTRA by differencing consecutive DGD updates. Under decentralized mixing assumptions, any convergent EXTRA sequence reaches consensus and an optimizer of the aggregate problem.
- DGD limitation: DGD uses local and neighbor information through a symmetric mixing matrix W whose nonzero weights correspond to network edges.The condition wij = 0 for non-neighboring, distinct agents makes each iteration decentralized.
- DGD limitation: Fixed-step DGD converges only to an O(α)-neighborhood, while diminishing stepsizes enable exact convergence but slow the method.The limiting points for different agents can also differ under a fixed stepsize.
- Development of EXTRA: EXTRA is obtained by subtracting two consecutive DGD formulas, producing an update that uses the current and previous iterates.Given xk and xk+1, the next iterate is generated by the resulting recurrence.
- Development of EXTRA: If the EXTRA sequence converges, its limit is consensual and any identical row vector solves the consensus optimization problem.Consensus follows from the mixing relation, while optimality follows after telescoping the correction terms and left-multiplying by 1T.
- Mixing-matrix assumptions: EXTRA uses two symmetric mixing matrices satisfying decentralized, null-space, and spectral properties, and can reuse DGD's W with a suitable ˜W.The recommended choice is ˜W = (W + I)/2; the matrices diffuse information through the network.
- Development of EXTRA: The correction term accumulates past mixing differences to neutralize the gradient component orthogonal to the consensus subspace.The passage states that individual terms vanish asymptotically, so their cumulative effect is necessary.
3. Convergence Analysis.
Under convexity and Lipschitz-gradient assumptions, EXTRA admits ergodic convergence guarantees, while restricted strong convexity yields linear convergence. Its fixed-step-size bound is independent of network properties, and linear convergence does not require each local function to be strongly convex.
- Step size: A fixed step size can be chosen independently of network size and diameter, with a bound comparable in order to centralized gradient descent when local smoothness constants are similar.The paper describes this as permitting a fixed and rather large step size.
- General convex convergence: Under Assumptions 1–3 and 0 < α < 2λmin(˜W)/Lf, EXTRA’s auxiliary sequence converges to an optimal point.The analysis uses Lipschitz continuity of the aggregate gradient and the stated mixing-matrix step-size condition.
- General convex convergence: The running-average and running-best progress and first-order optimality residuals have the rates stated in Theorem 3.5.The theorem separately reports running-average progress, running-best progress, and corresponding optimality-residual guarantees.
- Restricted strong convexity: Under restricted strong convexity of the aggregate objective, EXTRA achieves Q-linear convergence for G and R-linear convergence for the associated primal sequence.The paper states that the aggregate objective, rather than every individual f_i, may satisfy restricted strong convexity.
- Restricted strong convexity: The linear-convergence argument can be based on restricted strong convexity of the penalized function g, whose strong-convexity constant is no smaller than that of the aggregate objective.The penalized function adds a mixing-matrix-dependent quadratic term.
4. Numerical Experiments.
The experiments compare EXTRA with DGD across decentralized least-squares, robust least-squares, and logistic-regression settings. EXTRA continues progressing after fixed-step DGD stalls, exhibits sublinear-to-linear behavior on robust least squares, and achieves linear exact convergence on logistic regression.
- 4.1. Decentralized Least Squares: In decentralized least squares, fixed-step DGD and EXTRA show similar linear convergence during the first 200 iterations.The comparison uses the same mixing matrix and fixed step size for both methods.
- 4.1. Decentralized Least Squares: After 200 iterations, fixed-step DGD slows and eventually stalls, whereas EXTRA continues progressing.
- Across the experiments, the numerical results support EXTRA’s theoretical convergence claims and demonstrate competitive performance against DGD.
- 4.2. Decentralized Robust Least Squares: EXTRA shows sublinear convergence for the first 1000 iterations and then begins linear convergence in decentralized robust least squares.This experiment uses the Huber loss, which is described as robust to outliers.
- 4.3. Decentralized Logistic Regression: In a 200-agent decentralized logistic-regression network, EXTRA outperforms DGD with linear and exact convergence to the reference classifier.Each agent holds 10 samples, and the agents collaboratively estimate 20 coefficients.
Appendix A. Proof of Proposition 3.6.
The appendix proves the relationship between restricted strong convexity of the aggregate objective and the auxiliary function used in the convergence analysis. It uses consensus/disagreement decomposition and concludes that the auxiliary function is restricted strongly convex under the stated conditions.
- The proof decomposes each variable into a consensual component u and a disagreement component v orthogonal to the consensus subspace.The solution x* is consensual, so the decomposition separates optimization error from disagreement.
- Convexity of f and the spectral properties of ˜W−W provide nonnegative lower bounds for the auxiliary function’s gradient inner product.
- If the aggregate objective is restricted strongly convex, the auxiliary function g is restricted strongly convex for any α > 0.
- The proof notes that the auxiliary strong-convexity constant µg can be smaller than the aggregate constant µ̄f, but can approach it as α tends to zero.
- The step-size order derived for matching the strong-convexity scales coincides with the order of the critical step size ensuring linear convergence.