Source-linked AI summary
Fast Stochastic Alternating Direction Method of Multipliers
Leon Wenliang Zhong, James T. Kwok
TL;DR
Existing stochastic ADMM methods have low per-iteration complexity but converge more slowly than batch ADMM on convex problems. The proposed method incrementally approximates the full gradient in linearized ADMM. It achieves the batch convergence rate with lower per-iteration complexity, and experiments demonstrate efficiency over batch and stochastic ADMM algorithms.
Problem
Existing stochastic ADMM algorithms achieve O(1/sqrt(T)) convergence for general convex problems, compared with batch ADMM’s O(1/T) rate.
Source: §I · p. 1Method
The algorithm incrementally approximates the full gradient in the linearized ADMM formulation.
Source: §V · p. 5Results
O(1/T), matching batch ADMM with much lower per-iteration complexity; empirical results demonstrate efficiency over batch and stochastic ADMM algorithms.
Source: C. Convergence Analysis · p. 4, §V · p. 6Takeaways & Limitations
The method bridges the stochastic-versus-batch convergence-rate gap while retaining the computational simplicity of stochastic ADMM.
Source: §I · p. 1The theoretical convergence rate on strongly convex problems remains for future investigation.
Source: §V · p. 6
Abstract
from arXiv · showhide
In this paper, we propose a new stochastic alternating direction method of multipliers (ADMM) algorithm, which incrementally approximates the full gradient in the linearized ADMM formulation. Besides having a low per-iteration complexity as existing stochastic ADMM algorithms, the proposed algorithm improves the convergence rate on convex problems from $O(\frac 1 {\sqrt{T}})$ to $O(\frac 1 T)$, where $T$ is the number of iterations. This matches the convergence rate of the batch ADMM algorithm, but without the need to visit all the samples in each iteration. Experiments on the graph-guided fused lasso demonstrate that the new algorithm is significantly faster than state-of-the-art stochastic and batch ADMM algorithms.
I. INTRODUCTION
ADMM’s flexible objective splitting and equality constraint make it useful for structured optimization, but batch iterations can require visiting every sample. Existing stochastic variants reduce per-iteration cost yet lag batch ADMM in convergence rate, motivating a stochastic method that closes this gap.
I. INTRODUCTION
- ADMM’s objective splitting lets regularized risk minimization assign empirical loss and regularization to separate terms, with the constraint encoding the model’s sparsity pattern.The same equality-constraint structure can support consensus across local optimization subproblems in distributed convex optimization.Source: §I · p. 1
- Batch ADMM becomes costly for data-intensive regularized risk minimization because each iteration visits all samples.The introduction gives overlapping group lasso with large feature and dataset sizes as an example of costly matrix computations.Source: §I · p. 1
- Stochastic ADMM algorithms have low per-iteration complexities yet converge suboptimally relative to batch ADMM, which achieves O(1/T) for general convex problems and O(µT) for strongly convex problems, where 0 < µ < 1,.Source: §I · p. 1
- The proposed stochastic algorithm targets the stochastic–batch rate gap while retaining the computational simplicity of existing stochastic ADMM methods.The paper reports that it matches batch ADMM’s convergence rate.Source: §I · p. 1
II. BATCH AND STOCHASTIC ADMM
Batch ADMM minimizes an augmented Lagrangian by alternating updates, while stochastic variants seek to avoid full-data work in each iteration. Linearization makes these variants cheaper, but their reported convergence rates remain below batch ADMM’s.
II. BATCH AND STOCHASTIC ADMM
- ADMM alternates minimization over x and y in the augmented Lagrangian, using a scaled dual variable for its updates.The constraint residual is weighted by the Lagrange multiplier vector and a positive penalty parameter.Source: §II · p. 2
- For regularized risk minimization, the objective combines an empirical loss with a simple regularizer whose proximal step can be computed efficiently.The empirical loss averages sample-level losses across n samples.Source: §II · p. 2
- Online ADMM uses one sample per iteration, but its update generally requires nonlinear optimization, making it computationally unattractive.The online update uses a Bregman divergence and a stepsize proportional to 1/√t.Source: §II · p. 2
- For strongly convex φ, stochastic methods achieve O(log T/T) except RDA-ADMM, whose rate is unclear; these rates are inferior to batch ADMM’s O(µT), with 0 < µ < 1.Source: §II · p. 2
III. STOCHASTIC AVERAGE ADMM (SA-ADMM)
Existing stochastic ADMM updates replace the full empirical loss with a single-sample approximation, a trade-off also seen in stochastic gradient methods. The proposed approach draws on incremental surrogate methods to target batch-level convergence while retaining ADMM’s ability to handle equality constraints.
III. STOCHASTIC AVERAGE ADMM (SA-ADMM)
- Existing stochastic ADMM replaces the full training-set loss with a single-sample linear approximation plus a proximal term, paralleling SGD’s approach.The paper connects this stochastic substitution with the slower convergence of existing stochastic ADMM relative to batch methods.Source: §III · p. 3
- SAG incrementally updates an estimate of the full gradient, keeping per-iteration time as low as SGD while achieving linear convergence in its stated setting.The cited setting is a strongly convex sum of smooth functions.Source: §III · p. 3
- MISO incrementally replaces each sample loss with a surrogate, and its Lipschitz-gradient-surrogate update resembles SAG’s.This similarity is specified when each sample loss is smooth.Source: §III · p. 3
- The proposed stochastic ADMM targets batch-level convergence and, unlike SAG or MISO, applies to problems with equality constraints.The paper motivates this design using stochastic optimization methods that incrementally approximate full-gradient information.Source: §III · p. 3
A. Algorithm
The algorithm samples one loss per iteration while retaining gradient information from previously visited samples, then uses that information in a linearized ADMM update. It also provides an inexact Uzawa option and accommodates a nonzero regularizer through a proximal step.
A. Algorithm
- At each iteration, a uniformly sampled loss updates its stored gradient while the other loss gradients remain at previously stored values.The x-update uses information from all losses, unlike stochastic variants that retain only the sampled loss; y and α use the existing ADMM updates.Source: A. Algorithm · p. 3
- When ρA^T A + LI is manageable, the update can precompute its inverse; for a large matrix, the inexact Uzawa method uses an upper bound to approximate the feasibility term.The direct update follows by setting the derivative of the update objective to zero.Source: A. Algorithm · p. 3
- The inexact Uzawa update is similar to OPG-ADMM but uses information from all loss terms, whereas RDA-ADMM's gradient average still converges more slowly.The Uzawa simplification is described as easier to solve in general.Source: A. Algorithm · p. 3
- For nonzero Ω, the regularizer can be added to the update, yielding a proximal step that is efficient when Ω is simple, including common norms.Examples include ℓ1, ℓ2, ℓ∞, and mixed norms.Source: A. Algorithm · p. 3
B. Discussion
The discussion presents the stochastic ADMM procedure and relates its updates to existing surrogate-based methods. It also describes trade-offs in handling regularization and reformulating the problem.
B. Discussion
- When ψ=0, the problem reduces to minimizing φ(x), and the feasibility-violation term can be dropped.Source: B. Discussion · p. 3
- Ouyang et al. suggest fixing the changing stepsize at its smallest value, η_T, but the proof is missing and the choice may converge very slowly in practice.Source: B. Discussion · p. 3
- Algorithm 1 samples an index each iteration, updates x using the selected update rule, then updates y and the dual variable α, and outputs averaged iterates.The x-update uses (16) or (19) when Ω=0 and (22) when Ω≠0.Source: B. Discussion · p. 4
- The update is related to MISO's Lipschitz-gradient surrogate and to a proximal-gradient surrogate; unlike MISO, ADMM can handle equality constraints.SAG lacks the proximal term and cannot handle nonsmooth Ω.Source: B. Discussion · p. 4
- For nonzero Ω, using its subgradient does not exploit its structure, while folding it into ψ through a reformulation introduces an additional variable z of the same size as x.The reformulation is described as more computationally expensive empirically and as increasing the parameter-space radius, hence the big-Oh constants.Source: B. Discussion · p. 4
C. Convergence Analysis
The convergence analysis establishes an O(1/T) rate for the proposed updates, matching batch ADMM while retaining lower per-iteration complexity. The analysis extends beyond unconstrained surrogate methods to ADMM's equality constraints and Lagrangian multipliers.
C. Convergence Analysis
- The analysis is a non-trivial extension of MISO because ADMM adds equality constraints and Lagrangian multipliers.Source: C. Convergence Analysis · p. 4
- The bounds for updates (22) and (16) control expected objective error together with weighted feasibility violation for averaged iterates.The theorem statements provide these bounds, though the supplied passages truncate their right-hand sides.Source: C. Convergence Analysis · p. 4
- When B is invertible, recovering y from the averaged x makes feasibility violation zero; the stated objective-convergence corollary also assumes ψ is Lipschitz continuous.Source: C. Convergence Analysis · p. 4
- O(1/T) convergence matches batch ADMM across the analyzed cases while requiring much lower per-iteration complexity.Source: C. Convergence Analysis · p. 4
IV. EXPERIMENTS
The experiments evaluate stochastic and batch ADMM variants on graph-guided fused lasso, where the proposed SA-IU-ADMM is reported as the fastest overall. They also compare performance on a strongly convex problem.
IV. EXPERIMENTS
- The graph-guided fused lasso uses a graph-defined sparsity pattern and logistic loss for classification.The graph is obtained by sparse inverse covariance selection.Source: §IV · p. 4
- The comparison includes two proposed variants, three stochastic ADMM algorithms, and two deterministic batch variants, differing in their x updates.Online ADMM and direct batch ADMM are excluded because their x updates require nonlinear optimization.Source: §IV · p. 5
- SA-IU-ADMM is fastest overall, followed by SA-ADMM and the other stochastic algorithms; batch ADMM algorithms are slowest.Figures 1 and 2 plot objective value and testing loss against effective passes over data.Source: §IV · p. 5, Figure 1 · p. 5
- On the strongly convex problem, SA-IU-ADMM’s improvement over the other methods is reported as even more dramatic.The authors note that whether their algorithm has O(log T/T) convergence for strongly convex loss remains an open question.Source: §IV · p. 5
V. CONCLUSION
The paper presents a stochastic algorithm that incrementally approximates the full gradient in linearized ADMM while retaining the simplicity of stochastic ADMM. Its convergence rate matches batch ADMM, and experiments report efficiency over both batch and stochastic ADMM algorithms.
V. CONCLUSION
- The algorithm incrementally approximates the full gradient in the linearized ADMM formulation while retaining the computational simplicity of stochastic ADMM.Its convergence rate matches batch ADMM.Source: §V · p. 5
- Empirical results on general convex and strongly convex problems demonstrate efficiency over batch and stochastic ADMM algorithms.The authors identify theoretical convergence on strongly convex problems as future work.Source: §V · p. 6