Source-linked AI summary
Linearized ADMM for Non-convex Non-smooth Optimization with Convergence Analysis
Qinghua Liu, Xinyue Shen, Yuantao Gu
TL;DR
Convergence guarantees for ADMM on nonconvex problems remain open in general, and its subproblems can be difficult to solve. The paper proposes two-block and parallel multi-block linearized ADMM, reporting convergence under comparatively broad assumptions. The multi-block method also updates coupled variables in parallel and makes subproblems easier to solve.
Problem
For many nonconvex, nonsmooth objectives, theoretical convergence guarantees for ADMM remain an open problem, while ADMM subproblems can be difficult to solve.
Source: §1 · p. 2Method
The paper linearizes differentiable objective and augmented-Lagrangian terms in a two-block ADMM and extends the approach to parallel multi-block updates.
Source: §1.3 · p. 4, §6 · p. 14Results
The authors report convergence analyses for both algorithms under their assumptions, which they describe as broad relative to recent nonconvex ADMM work.
Source: §3.3 · p. 9, §6 · p. 14Takeaways & Limitations
The multi-block algorithm can update coupled variables in parallel, and linearization yields subproblems usually easier to solve than the originals.
Source: §1.3 · p. 4, §6 · p. 14The multi-block problem is subject to the same Assumption 1 as the two-block formulation.
Source: §1.1 · p. 3
Abstract
from arXiv · showhide
Linearized alternating direction method of multipliers (ADMM) as an extension of ADMM has been widely used to solve linearly constrained problems in signal processing, machine leaning, communications, and many other fields. Despite its broad applications in nonconvex optimization, for a great number of nonconvex and nonsmooth objective functions, its theoretical convergence guarantee is still an open problem. In this paper, we propose a two-block linearized ADMM and a multi-block parallel linearized ADMM for problems with nonconvex and nonsmooth objectives. Mathematically, we present that the algorithms can converge for a broader class of objective functions under less strict assumptions compared with previous works. Furthermore, our proposed algorithm can update coupled variables in parallel and work for less restrictive nonconvex problems, where the traditional ADMM may have difficulties in solving subproblems.
1 Introduction
The introduction motivates linearized ADMM by the open convergence question for nonconvex problems and the difficulty of solving some ADMM subproblems. It presents two-block and parallel multi-block algorithms, their assumptions, and their relation to earlier work.
1 Introduction
- Nonconvex ADMM convergence remains open, while difficult subproblems can require approximate updates or costly numerical solvers; large problems also motivate parallel methods.Linearization is presented as a way to make intractable subproblems solvable and reduce computational complexity.Source: §1 · p. 2
1.1 Main problems
- The paper proposes two-block linearized ADMM for coupled variables and a parallel multi-block method as a special case, under the same assumptions.The two-block formulation allows nonconvex differentiable terms and a nonconvex, nondifferentiable term; the authors describe their restrictions on f and A as relatively weak.Source: §1.1 · p. 3
1.2 Related Works
- Unlike [29], which requires B to have full row rank, these algorithms require full column rank and the multi-block method allows parallel computation.The authors also distinguish their approach from prior works with more restrictive assumptions on objective functions and constraint matrices.Source: §1.2 · p. 4, §1.3 · p. 5
1.3 Contribution
- Linearizing differentiable objective and augmented-Lagrangian parts transforms subproblems into proximal or quadratic problems, usually easier than the originals.The multi-block method decouples coupled variables for parallel updates; the paper reports numerical evidence of efficiency relative to other recent nonconvex ADMM algorithms.Source: §1.3 · pp. 4–5
1.4 Outline
- The paper proceeds from preliminaries to algorithm design and convergence analysis, then discusses update rules and applications before numerical experiments and conclusions.The two-block method and its analysis appear before the parallel multi-block method.Source: §1.4 · p. 5
2 Preliminary
The preliminary section establishes notation and introduces regular subgradients, Lipschitz differentiability, and coercivity. It also gives the two-block algorithm’s stopping rule.
2.1 Notation
- Bold capitals denote matrices, bold lowercase letters vectors, and xk and xi denote the kth iterate and ith block, respectively.The section also defines notation for gradients, regular subgradients, eigenvalues, norms, and matrix images.Source: §2.1 · p. 5
2.2 Definition
- Algorithm 1 initializes x, y, and γ, iterates until successive changes are within ε, then returns the variables and dual iterate.Its stopping test uses the maximum of the successive differences in x, y, and γ.Source: §2.2 · p. 6
- A regular subgradient is set-valued; for a differentiable function, its set contains only the gradient.The preliminaries also define Lipschitz differentiability through the Lipschitz continuity of the gradient and define coercivity relative to a feasible set.Source: §2.2 · p. 6
3 Linearized ADMM: two-block and multi-block
The section develops a two-block linearized ADMM for possibly nonsmooth nonconvex problems, analyzes its convergence under Assumption 1, and extends it to parallel multi-block updates with the same guarantees.
3.1 Two-block linearized ADMM updating rules
- The two-block updates linearize the x- and y-subproblems with regularization terms, then use auxiliary functions to define the update rules.The x-update becomes a proximal problem, and the matrix inversion in the y-update can be computed beforehand.Source: §3.1 · pp. 6–7
3.2 Convergence analysis
- Under Assumption 1 and specified Lx, Ly, and β, the augmented Lagrangian converges and the primal and dual residues vanish.Theorem 1 gives these results when the parameters satisfy its stated conditions.Source: §3.2 · p. 7
- Under Assumption 1, the iterates approach the feasible set and the Lagrangian's primal-variable derivative tends to zero; any limit points are KKT points.The paper also describes these limit points as saddle points of the augmented Lagrangian.Source: §3.2 · p. 8
3.3 Multi-block parallel linearized ADMM
- When f is separable across xi, linearization decouples otherwise coupled blocks so they can be optimized in parallel.The multi-block algorithm is a special case of Algorithm 1, so its convergence assumptions and results remain the same.Source: §3.3 · p. 9
- Because the multi-block algorithm is a special case of Algorithm 1, its convergence assumptions and results remain the same.This follows by replacing f(x) with the sum of the block functions fi(xi).Source: §3.3 · p. 9
4 Discussion
The discussion explains how proximal terms support convergence, frames linearization and parallel computation as a time-cost trade-off, and describes problem classes that satisfy Assumption 1.
4.1 Proximal term
- The proximal term guarantees descent of the Lagrangian after primal updates and controls the inexactness introduced by linearization.This lets the method place almost no restriction on f (fi).Source: §4.1 · p. 10
4.2 Linearization versus parallel computation
- Linearization may slow convergence, but decoupling coupled variables enables parallel computation that reduces single-iteration time cost.The total time cost depends on the balance between these effects; the paper says Section 5 demonstrates that parallel acceleration can outweigh the slowdown.Source: §4.2 · p. 10
4.3.1 Sparsity relate topics
- Sparsity-related problems satisfy Assumption 1 when the loss is Lipschitz differentiable, with F allowed to be an ℓp-norm (0 ≤ q ≤ 1) or another nonconvex sparsity measure.The passage also requires the loss gradient to be Lipschitz continuous.Source: §4.3.1 · pp. 10–11
4.3.2 Indicator function of compact manifold
- For integer programming over a finite set M, the converted problem satisfies Assumption 1 if h is Lipschitz differentiable.The problem statement also assumes f is lower bounded over M.Source: §4.3.2 · p. 11
5 Numerical Experiment
The experiments compare the proposed method with two reference ADMM algorithms on a nonconvex regularized LASSO problem. The proposed method is reported to converge faster and to have lower average CPU time, while the objective-value comparison shows different saddle-point outcomes across methods.
5 Numerical Experiment
- The experiment applies Algorithm 2 to a nonconvex regularized LASSO problem, replacing the traditional l1 norm with a nonconvex sparsity measure.The experiment uses N = 1024, M = 256, λ = 0.1, and η = 0.1, with Gaussian A and b.Source: §5 · pp. 11–12
- Our algorithm averaged 12.56s, 15.23s, and 20.76s, versus Ref1’s 230.23s, 257.84s, and 439.3s and Ref2’s 75.92s, 83.31s, and 109.57s.The reported averages use best parameters and are based on 1000 independent trials.Source: §5 · p. 13
- The proposed algorithm’s maximum-variable-gap curve converges fastest among the three methods in one random trial.The authors report observing the same phenomenon across 1000 trials with both theoretically chosen and best parameters.Source: §5 · p. 13, Figure 1 · p. 13
- Ref2 and the proposed algorithm converge to the same objective-value saddle point, while Ref1 converges to another saddle point with a higher objective value.The authors report the same pattern across 1000 trials.Source: §5 · p. 13, Figure 2 · p. 14
6 Conclusion
The paper proposes two-block linearized ADMM for nonconvex, nonsmooth problems and extends it to a multi-block parallel algorithm. Its convergence analysis applies under a relatively broad assumption, and the algorithms are presented as applicable to problems including sparse recovery and integer programming.
6 Conclusion
- The two-block algorithm linearizes differentiable terms in both the objective and augmented term, making subproblems easier to solve.The paper provides theoretical convergence analysis under Assumption 1.Source: §6 · p. 14
- The multi-block extension updates coupled variables in parallel, with convergence analysis that remains applicable.Source: §6 · p. 14
- The authors characterize Assumption 1 as relatively broad and identify sparse recovery and integer programming as example applications.Source: §6 · p. 14
7 Appendix
The appendix establishes convergence by bounding changes in the augmented Lagrangian across updates and showing an auxiliary sequence converges. These results yield vanishing primal and dual residues.
7 Appendix
- Bounds on the augmented Lagrangian’s descent or ascent are established for the x, y, and γ updates using quadratic forms of the primal residual.Source: §7 · pp. 16–18
- The proof constructs an auxiliary sequence that is monotone and convergent under Assumption 1 and the stated parameter conditions.The sequence is shown to decrease monotonically and to be lower bounded.Source: §7 · pp. 19–20
2. Lower bound of {mk}
The appendix proves convergence by lower-bounding an auxiliary sequence, then deriving vanishing iterate changes and stationarity. Under the cited conditions, it also establishes boundedness and objective-value convergence.
2. Lower bound of {mk}
- The sequence {m_k} is lower bounded using a feasible comparison point, and its monotone decrease therefore implies convergence.Source: §2 · pp. 20–21
7.1 Proof of Theorem 1
- Theorem 1’s proof uses convergence of {m_k} to show that the augmented Lagrangian converges and primal and dual residues vanish.Source: §7.1 · p. 22
7.2 Proof of Corollary 1
- For Corollary 1, coercivity over the feasible set with respect to y is used to establish boundedness of the iterates.Source: §7.2 · p. 22
7.3 Proof of Theorem 2
- Theorem 2’s proof establishes feasibility in the limit and convergence of the Lagrangian derivatives with respect to the primal variables to zero.Source: §7.3 · p. 23, §7.4 · p. 23
7.4 Proof of Corollary 2
- Corollary 2 concludes that the objective-function value converges because the augmented Lagrangian converges.Source: §7.4 · p. 23