Source-linked AI summary
A Coordinate Descent Primal-Dual Algorithm and Application to Distributed Asynchronous Optimization
Pascal Bianchi, Walid Hachem, Franck Iutzeler
TL;DR
The paper addresses distributed minimization in which agents use local information to seek consensus on a minimizer of their aggregate objective. It introduces randomized coordinate descent for a primal-dual method and obtains an asynchronous distributed algorithm; the method converges under its stated setting and is reported faster than other stochastic-gradient methods in simulations.
Problem
Distributed agents must use local information to converge to a common consensus value minimizing the aggregate objective.
Source: §IV · p. 5Method
The paper applies randomized coordinate descent to ADMM+, producing DAPD, in which randomly selected agents update local estimates and communicate with neighbors.
Source: §I · pp. 1–2Results
DAPD's local estimates converge almost surely to a random variable supported on the minimizers, and simulations report it significantly faster than other stochastic-gradient methods.
Source: C. A Distributed Asynchronous Primal… · p. 7, §V · p. 7Takeaways & Limitations
The framework extends stochastic coordinate descent to asynchronous distributed optimization and supports processing distinct blocks on different machines.
Source: §VI · pp. 7–8Step (4d) can be delicate when M lacks a convenient structure for computing its argmin.
Source: E. Comparison to the original… · p. 4
Abstract
from arXiv · showhide
Based on the idea of randomized coordinate descent of $\alpha$-averaged operators, a randomized primal-dual optimization algorithm is introduced, where a random subset of coordinates is updated at each iteration. The algorithm builds upon a variant of a recent (deterministic) algorithm proposed by V\~u and Condat that includes the well known ADMM as a particular case. The obtained algorithm is used to solve asynchronously a distributed optimization problem. A network of agents, each having a separate cost function containing a differentiable term, seek to find a consensus on the minimum of the aggregate objective. The method yields an algorithm where at each iteration, a random subset of agents wake up, update their local estimates, exchange some data with their neighbors, and go idle. Numerical results demonstrate the attractive performance of the method. The general approach can be naturally adapted to other situations where coordinate descent convex optimization algorithms are used with a random choice of the coordinates.
I. INTRODUCTION
The paper develops randomized coordinate-descent extensions of primal-dual optimization and applies them to asynchronous distributed consensus. Its setup connects a differentiable-plus-convex aggregate objective to a consensus constraint, while the proposed method combines node-level asynchrony, proximal updates, gradients, and constant step sizes.
A. Problem statement
- Each agent has a private cost fn + gn, with fn differentiable, and the goal is to minimize their aggregate cost at consensus.The paper reformulates consensus as an indicator-function constraint within the general minimization problem.Source: §I · p. 1
I. INTRODUCTION
- ADMM+ extends the Vũ–Condat primal-dual algorithm, and randomized coordinate descent of averaged operators yields convergent asynchronous versions for distributed optimization.The framework also gives a convergence result for stochastic coordinate-descent versions of proximal gradient, viewed as applying a 1/2-averaged operator.Source: §I · pp. 1–2
- DAPD lets an i.i.d. random subset of agents wake, apply local proximity operators, send estimates to neighbors, and go idle.The distributed formulation encodes graph connections through M.Source: §I · p. 2
- Earlier stochastic coordinate descent on averaged operators was limited to unrelaxed firmly nonexpansive operators, suited to ADMM.The paper situates asynchronous distributed optimization as a framework for scaling machine-learning problems involving massive datasets.Source: §I · p. 2
- The proposed method combines node-level asynchrony, proximal updates for possibly nondifferentiable terms, local gradients, and a constant gradient step size.The paper contrasts node-level activation with asynchronous ADMM's edge-level activation and constant steps with adaptation-diffusion methods' vanishing steps.Source: §I · p. 2
A. Problem statement
- The general problem assumes convex differentiable f with Lipschitz gradient, convex g and h, an injective M, and an attained infimum with a qualification condition.The paper's assumptions also require ∇(f ◦ M^-1) to be L-Lipschitz continuous on the image of M.Source: A. Problem statement · p. 2
B. A Primal-Dual Algorithm
ADMM+ is a primal-dual algorithm with convergence guarantees under stated assumptions and step-size conditions. When f is zero, it recovers standard ADMM, with a weaker step-size condition that permits equal parameters.
B. A Primal-Dual Algorithm
- Under Assumptions 1–3 and τ^-1 − ρ^-1 > L/2, ADMM+ converges to a primal-dual point from any initial value.The algorithm is especially useful when ∇f and the left-hand member of its x-step are easy to compute, such as with quadratic f and ℓ1-regularized g.Source: B. A Primal-Dual Algorithm · p. 3
- When f = 0, the step-size condition weakens to τ^-1 − ρ^-1 ≥ 0, so τ = ρ is allowed without requiring M to be injective.This special case permits a single instrumental parameter to tune.Source: B. A Primal-Dual Algorithm · p. 3
C. The case f ≡0 and the link with ADMM
- When f = 0 and τ = ρ, ADMM+ reduces to standard ADMM.Source: C. The case f ≡0 and the link with ADMM · p. 3
D. The case h ≡0 and the link with the Forward-Backward algorithm
ADMM+ reduces to the Forward-Backward algorithm when h ≡ 0 and M = I. The paper also relates ADMM+ to averaged operators and develops a randomized coordinate version with almost-sure fixed-point convergence.
D. The case h ≡0 and the link with the Forward-Backward algorithm
- With h ≡ 0 and M = I, ADMM+ becomes the Forward-Backward algorithm, with τ < 2/L and ρ unrestricted by the stepsize condition.The applications of this algorithm include ISTA.Source: D. The case h ≡0 and the link with the… · p. 3
E. Comparison to the original V˜u-Condat algorithm
- ADMM+ can be delicate to implement when M lacks structure that makes step (4d) affordable, but it converges under weaker stepsize assumptions than the original Vũ–Condat algorithm.The injectivity assumption on M is not needed when f = 0 and is satisfied in the motivating application scenarios.Source: E. Comparison to the original… · p. 4
A. Averaged operators and the primal-dual algorithm
- Under τ^-1 − ρ^-1 > L/2, the ADMM+ transformation is α-averaged, enabling a Krasnosel’skii–Mann iteration to converge to a fixed point.The general iteration converges when its relaxation parameters satisfy the stated bound and divergent-sum condition.Source: A 1-averaged operator is said… · p. 4
B. Randomized Krasnosel’skii Mann Iterations
- Randomized coordinate descent of an α-averaged operator converges almost surely to a fixed point when every coordinate has a positive-probability selection.The result is applied to ADMM+ to obtain an asynchronous distributed version.Source: B. Randomized Krasnosel’skii Mann… · pp. 4–5
IV. DISTRIBUTED OPTIMIZATION
The distributed optimization problem assigns each agent a private cost and seeks a common minimizer of their aggregate. The network formulation encodes consensus through local constraints on graph edges.
IV. DISTRIBUTED OPTIMIZATION
- Agents use private cost functions, with differentiable convex terms and convex regularizers, to seek a consensus minimizer of the aggregate objective.Motivating applications include distributed learning, communication-network resource allocation, and sensor-network estimation.Source: §IV · p. 5
A. Network Model and Problem Formulation
- The graph-based formulation encodes global consensus through local consensus constraints on each edge; simply imposing a single global constraint would not yield a distributed algorithm.Each edge connects agents that can communicate, and the graph is assumed connected and without self-loops.Source: A. Network Model and Problem Formulation · p. 5
- For a connected graph, minimizers of the reformulated problem are tuples with identical components, each equal to a minimizer of the original aggregate problem.The formulation builds f and g from the agents’ private functions and uses the consensus-enforcing function h with an edge-based operator M.Source: A. Network Model and Problem Formulation · p. 5
B. Instantiating ADMM+
The paper instantiates ADMM+ on the graph-based consensus problem as Distributed ADMM+. Under the stated assumptions, its local estimates converge to a minimizer of the aggregate objective.
B. Instantiating ADMM+
- Because the consensus function is separable across edges, the ADMM+ updates can be expressed through edge-level quantities and local agent updates.The derivation uses edge averages and each node’s degree in its local update.Source: B. Instantiating ADMM+ · p. 6
- The resulting Distributed ADMM+ procedure stores local variables at each agent and sends updated local parameters to other agents.The supplied procedure begins with per-agent memory and communication steps.Source: B. Instantiating ADMM+ · p. 6
- Distributed ADMM+ produces local estimates that converge to a minimizer of Problem (10) under the theorem’s assumptions.The convergence theorem requires the stated condition involving the graph’s minimum node degree.Source: B. Instantiating ADMM+ · p. 6
C. A Distributed Asynchronous Primal Dual Algorithm
The asynchronous algorithm activates a random single agent or subset at each iteration, without a central scheduler. Under the stated conditions, the local estimates converge almost surely to a random minimizer of the aggregate objective.
C. A Distributed Asynchronous Primal Dual Algorithm
- Unlike synchronous operation, asynchronous operation has no central scheduler and allows nodes to wake independently at random times.The paper identifies complexity and flexibility as advantages of this mode of operation.Source: C. A Distributed Asynchronous Primal… · p. 6
- At each iteration, DAPD activates a randomly chosen single agent or subset of agents to perform a proximal update on its local variable.The selected agents are encoded by an i.i.d. sequence of subsets of the agent set.Source: C. A Distributed Asynchronous Primal… · p. 6
- The DAPD local estimates converge almost surely to a random variable supported on the minimizers of Problem (10).The theorem assumes the stated conditions and that the selection sets cover every agent with positive probability.Source: C. A Distributed Asynchronous Primal… · pp. 6–7
V. NUMERICAL ILLUSTRATIONS
The numerical illustrations evaluate DAPD on distributed ℓ2-regularized logistic regression and report faster convergence than the compared stochastic-gradient methods. DAPD also uses relatively little communication, while the reported tests use only one active agent per iteration.
V. NUMERICAL ILLUSTRATIONS
- The experiments address ℓ2-regularized logistic regression with data partitioned among networked agents.The agents hold disjoint observation blocks, and the regularization parameter is set to 10^-4.Source: §V · p. 7
- The reported tests use a single active agent, although DAPD permits multiple agents to wake up and the authors note this single-agent case underperforms multiple-agent activation.The logistic-regression data are distributed across a 10 × 10 toroidal grid; the rcv1 comparison also considers a 5 × 5 toroidal grid and a 50-node complete network.Source: §V · p. 7
- DAPD is significantly faster than the other stochastic-gradient methods on the reported logistic-regression problems.The cost is plotted against the number of local gradients used.Source: §V · p. 7
- DAPD exchanges roughly a vector shorter than 2Np per iteration—8p for the tested graph—compared with a dataset of roughly Tp.The authors describe the number of transmissions as generally small relative to the dataset size.Source: §V · p. 7
VI. CONCLUSIONS AND PERSPECTIVES
The paper presents a stochastic coordinate-descent framework and applies it to ADMM+, a variant of the Vũ–Condat algorithm. The resulting asynchronous distributed algorithm can process distinct blocks on different machines; convergence-rate analysis and efficient step-size strategies remain future work.
VI. CONCLUSIONS AND PERSPECTIVES
- The paper introduces a general framework for stochastic coordinate descent and applies it to ADMM+, a variant rooted in recent work by Vũ and Condat.ADMM+ includes ADMM as a special case when f = 0, as stated in the contribution passage.Source: §VI · p. 7
- The framework yields an asynchronous distributed algorithm for processing distinct blocks on different machines.The conclusion identifies convergence-rate analysis and efficient step-size strategies as future work.Source: §VI · p. 8
APPENDIX
The appendix derives ADMM+ from the earlier iterations and proves convergence properties for randomized coordinate updates of averaged operators. Its proof uses a supermartingale argument and shows accumulation points lie in the fixed-point set.
A. Proof of Theorem 1
- Rewriting the earlier iterations with Moreau’s identity recovers the ADMM+ iterates.The proof relates the transformed functions and primal-dual points before rewriting the two update equations.Source: A. Proof of Theorem 1 · p. 8
B. Proof of Theorem 3
- The squared distance to a fixed point is a nonnegative supermartingale and converges almost surely to a finite value.The proof uses averagedness to obtain the supermartingale property.Source: B. Proof of Theorem 3 · p. 8
- The proof shows accumulation points of the iterates belong to fix(T) and reduces them to a single point.It combines convergence of distances to fixed points with the residual tending to zero almost surely.Source: B. Proof of Theorem 3 · p. 9
C. Proof of Theorem 4
The proof bounds the Lipschitz constant of the transformed gradient using the minimum graph degree. The graph operator’s normal product is diagonal, with node degrees on its diagonal.
C. Proof of Theorem 4
- The graph operator satisfies M*M diagonal with node degrees on its diagonal, linking its norm bound to the minimum degree dmin.For each node n, the diagonal entry is its degree dn.Source: C. Proof of Theorem 4 · p. 9
- The transformed gradient has Lipschitz constant L = Lbar/dmin under the stated hypotheses.The proof derives the bound by combining the graph-degree norm inequality with the local gradient bound.Source: C. Proof of Theorem 4 · p. 9
D. Proof of Theorem 5
The proof models DAPD as a randomized coordinate update of an α-averaged operator and uses this representation to establish almost-sure convergence. It then matches the resulting primal update to DAPD’s x-update.
D. Proof of Theorem 5
- The proof represents DAPD as randomized updates of an α-averaged operator on H, applying the full operator to selected coordinates and leaving the others unchanged.The coordinate selection is identified with the set of agents V.Source: D. Proof of Theorem 5 · p. 9
- The generated sequence converges almost surely to a primal-dual point, implying that the agent estimates converge to consensus at a minimizer of Problem (10).The proof invokes Theorem 3 for primal-dual convergence and Lemma 3 for convergence of the estimates.Source: D. Proof of Theorem 5 · p. 9
- After rewriting the equations, the proof identifies the resulting update with DAPD’s x-update.The derivation uses the stated identities for the transformed functions and the operator M* M.Source: D. Proof of Theorem 5 · pp. 9–10