Source-linked AI summary
An Accelerated Linearized Alternating Direction Method of Multipliers
Yuyuan Ouyang, Yunmei Chen, Guanghui Lan, Eduardo Pasiliao
TL;DR
The paper develops an accelerated linearized ADMM framework for convex composite optimization with linear constraints. AADMM improves convergence-rate dependence on the smooth component’s Lipschitz constant, handles unbounded feasible sets when a saddle point exists, and includes backtracking for practical performance.
Problem
The paper targets AECCO and UCO problems where the smooth component may have a large Lipschitz constant and the feasible region may be unbounded.
Method
AADMM incorporates a multi-step acceleration scheme and variable weighting sequence into linearized ADMM, with a backtracking scheme for practical performance.
Results
AADMM has better convergence rates than linearized ADMM in their dependence on the Lipschitz constant, while AL-ADMM and ALP-ADMM improve rates over L-ADMM and LP-ADMM, respectively.
Takeaways & Limitations
AADMM can solve the targeted convex composite optimization problems on bounded or unbounded feasible sets when a saddle point exists.
Takeaways & Limitations
The feasibility-residual convergence rate in the cited prior result is not clear because the objective residual expression can be negative.
Abstract
from arXiv · showhide
We present a novel framework, namely AADMM, for acceleration of linearized alternating direction method of multipliers (ADMM). The basic idea of AADMM is to incorporate a multi-step acceleration scheme into linearized ADMM. We demonstrate that for solving a class of convex composite optimization with linear constraints, the rate of convergence of AADMM is better than that of linearized ADMM, in terms of their dependence on the Lipschitz constant of the smooth component. Moreover, AADMM is capable to deal with the situation when the feasible region is unbounded, as long as the corresponding saddle point problem has a solution. A backtracking algorithm is also proposed for practical performance.
1. Introduction.
The paper develops AADMM, an accelerated framework for convex composite optimization with linear constraints, extending linearized ADMM to improve convergence dependence on the smooth term’s Lipschitz constant. It also addresses unbounded feasible sets under saddle-point existence and proposes backtracking for practical use.
- 1. Introduction.: The framework targets AECCO problems with convex, lower-semicontinuous objective components and bounded linear constraint operators.The model minimizes G(x)+F(w) subject to Bw−Kx=b, with G and F convex and finitely valued.
- 1. Introduction.: The paper motivates AECCO and UCO through applications in machine learning and image processing, including total-variation-based image reconstruction.In this setting, G is the fidelity term and F is the regularization term.
- 1.2. Augmented Lagrangian and alternating direction method of multipliers.: Existing ADMM analyses include residual-rate results, but prior bounds may require bounded feasible sets or leave feasibility-residual behavior unclear.For one cited result, the objective gap can be negative when iterates are infeasible, complicating interpretation of the feasibility rate.
- 1.4. Contribution of the paper.: AADMM incorporates a multi-step acceleration scheme into linearized ADMM through accelerated L-ADMM and accelerated LP-ADMM.These methods extend L-ADMM and LP-ADMM, respectively.
- 1.4. Contribution of the paper.: AADMM improves convergence-rate dependence on LG relative to linearized ADMM, including when LG is as large as Ω(N) without affecting the rate up to a constant factor.The comparison applies to AL-ADMM versus L-ADMM and ALP-ADMM versus LP-ADMM.
- 1.4. Contribution of the paper.: AADMM handles bounded and unbounded feasible sets when the corresponding saddle point exists, with unbounded-case rate estimates depending on the initial point’s distance to optimal solutions.The convergence analysis uses primal and feasibility residuals directly.
2. An accelerated ADMM framework.
AADMM combines accelerated weighting with linearized ADMM to improve convergence dependence on the smooth component’s Lipschitz constant while covering constrained and unconstrained composite problems.
- Framework: AADMM is an accelerated framework for AECCO and UCO problems, presented through an algorithmic framework that unifies several ADMM variants.With χ = 0 it specializes to L-ADMM, and with χ = 1 it specializes to LP-ADMM; simple G further yields ADMM or P-ADMM.
- Gap functions: The framework addresses saddle-point formulations with potentially unbounded feasible sets, provided a saddle point exists.Its convergence analysis works directly with primal and feasibility residuals, with estimates depending on the initial distance to the optimal-solution set.
- Gap functions: AADMM’s gap functions connect saddle-point accuracy to approximate-solution guarantees through primal and feasibility residuals.Proposition 2.1 states that a bounded gap and constraint violation imply an (ε, δ)-solution; when Y = Y, the gap argument also identifies the feasibility residual.
- Framework: Variable weighting sequence {αt} accelerates convergence with respect to LG at approximately the same iteration cost.The acceleration uses weighted middle and aggregate points rather than the unweighted choice αt = 1.
- Convergence results: AL-ADMM and ALP-ADMM improve the dependence on LG over L-ADMM and LP-ADMM, allowing LG as large as Ω(N) without affecting the rate up to a constant factor.ALP-ADMM matches Nesterov’s smoothing rate, while AL-ADMM has better rate constants but higher iteration cost than ALP-ADMM.
- Convergence results: For the unaccelerated parameter choice αt ≡ 1, ADMM algorithms have primal and feasibility residual rates of order O(1/t).The choice ρ = 1 is adopted for simplicity, although larger ρ trades off the two residual bounds.
3. Numerical examples.
The numerical experiments evaluate AADMM variants on group LASSO, compressive sensing, and partially parallel image reconstruction. Across these applications, accelerated methods generally outperform their linearized ADMM or backtracking baselines, especially for difficult sampling settings.
- Experimental setup: The experiments cover overlapped LASSO, compressive sensing, and partially parallel image reconstruction, using MATLAB implementations.The reported metrics include primal objective values, relative errors, and CPU-time comparisons.
- 3.1. Group LASSO with overlap: The group LASSO experiment uses n = 4096 features, m = 2048 observations, 2 × 2 groups, and λ = 1.The data are generated from Gaussian sensing vectors and noisy observations of a structured 64 × 64 signal.
- 3.1. Group LASSO with overlap: AL-ADMM and ALP-ADMM perform almost identically and outperform L-ADMM and LP-ADMM on the group LASSO problem.This agrees with the reported theoretical advantage of their convergence rate over the corresponding ADMM methods.
- 3.2. Compressive sensing: In compressive sensing, ALP-ADMM with box constraints outperforms AL-ADMM with X = Rn, while both accelerated variants outperform their linearized baselines.The authors interpret this as suggesting that ground-truth intensity bounds help image reconstruction.
- 3.3. Partially parallel imaging: For partially parallel imaging, AL-ADMM and ALP-ADMM outperform BOSVS in reducing both primal objective values and relative errors, especially with Cartesian sampling.Cartesian sampling is harder in these experiments because it collects fewer low-frequency samples and lacks sampling randomness.
4. Conclusion.
The paper introduces AADMM, which adds multi-step acceleration to linearized ADMM for convex composite problems with linear constraints. It reports improved dependence on the smooth term’s Lipschitz constant, applicability to bounded and unbounded feasible sets under a saddle-point condition, and promising preliminary numerical results.
- Conclusion: AADMM incorporates a multi-step acceleration scheme into linearized ADMM.The framework includes accelerated L-ADMM and accelerated LP-ADMM methods.
- Conclusion: AADMM has better convergence rates than linearized ADMM in their dependence on the Lipschitz constant of the smooth component.The comparison concerns a class of convex composite optimization problems with linear constraints.
- Conclusion: AADMM handles bounded and unbounded feasible sets when the corresponding saddle-point problem has a solution.For unbounded feasible sets, the convergence-rate estimate depends on the distance from the initial point to the saddle-point set.
- Conclusion: A backtracking scheme is proposed to improve AADMM’s practical performance.The paper concludes that preliminary numerical results indicate promise for large-scale convex composite optimization with linear constraints.