Source-linked AI summary
Global convergence of splitting methods for nonconvex composite optimization
Guoyin Li, Ting Kei Pong
TL;DR
The paper addresses nonconvex composite optimization with a smooth bounded-Hessian term and a nonsmooth composition whose proximal mappings are simple. It analyzes ADMM and proximal gradient, proving stationary-point guarantees and stronger convergence results under additional conditions.
Problem
Nonconvex composite problems with a general linear composition can be difficult to solve efficiently, despite covering applications in engineering and machine learning.
Method
The paper studies proximal ADMM for surjective M and proximal gradient for M = I, using penalty, step-size, quadratic-approximation, and semi-algebraic assumptions.
Results
ADMM cluster points are stationary under a sufficiently large penalty and cluster-point existence, while semi-algebraicity yields whole-sequence convergence and M = I permits a more flexible proximal-gradient step-size rule.
Takeaways & Limitations
The guarantees apply to broad application classes and include sufficient conditions for boundedness of the proximal ADMM sequence.
Takeaways & Limitations
The paper gives a concrete two-dimensional example showing ADMM can diverge when M is injective instead of surjective.
Abstract
from arXiv · showhide
We consider the problem of minimizing the sum of a smooth function $h$ with a bounded Hessian, and a nonsmooth function. We assume that the latter function is a composition of a proper closed function $P$ and a surjective linear map $\cal M$, with the proximal mappings of $τP$, $τ> 0$, simple to compute. This problem is nonconvex in general and encompasses many important applications in engineering and machine learning. In this paper, we examined two types of splitting methods for solving this nonconvex optimization problem: alternating direction method of multipliers and proximal gradient algorithm. For the direct adaptation of the alternating direction method of multipliers, we show that, if the penalty parameter is chosen sufficiently large and the sequence generated has a cluster point, then it gives a stationary point of the nonconvex problem. We also establish convergence of the whole sequence under an additional assumption that the functions $h$ and $P$ are semi-algebraic. Furthermore, we give simple sufficient conditions to guarantee boundedness of the sequence generated. These conditions can be satisfied for a wide range of applications including the least squares problem with the $\ell_{1/2}$ regularization. Finally, when $\cal M$ is the identity so that the proximal gradient algorithm can be efficiently applied, we show that any cluster point is stationary under a slightly more flexible constant step-size rule than what is known in the literature for a nonconvex $h$.
1 Introduction
The paper studies nonconvex composite optimization with a smooth bounded-Hessian term and a nonsmooth composition, developing ADMM and proximal-gradient guarantees under surjectivity or identity-map structure.
- Problem setting: The model minimizes h(x) + P(Mx), where h has a bounded Hessian and P is proper closed with efficiently computable proximal mappings.The linear map M is assumed surjective for the general formulation.
- Applications: The framework covers applications in engineering and machine learning, including sparse learning, rank regularization, and cardinality-constrained models.Examples include ℓ1/2 and ℓ0 regularization and low-rank matrix constraints.
- ADMM guarantees: ADMM cluster points are stationary when its fixed penalty parameter exceeds a computable lower bound and a cluster point exists.The result applies to a general surjective linear map M.
- ADMM guarantees: The ADMM analysis permits local quadratic approximations of h, reducing each iteration to proximal evaluation for τP and unconstrained convex quadratic minimization.The paper also provides sufficient conditions for boundedness that apply across a wide range of applications.
- ADMM guarantees: If h and P are semi-algebraic, existence of an ADMM cluster point implies convergence of the whole sequence.The assumption covers quadratic functions, polyhedral norms, and the cardinality function.
- Proximal gradient: When M is the identity, proximal gradient admits a slightly more flexible constant step-size rule for nonconvex h.The paper states that this extends the known step-size treatment for the proximal-gradient setting.
2 Notation and preliminaries
This section establishes notation and introduces the variational-analysis concepts used to state stationarity, curvature bounds, and convergence conditions.
- Notation: The paper defines Euclidean inner products and norms, adjoint linear maps, operator norms, symmetry, and eigenvalue notation for linear self-maps.Positive semidefinite and positive definite orderings are defined through symmetric linear maps.
- Variational analysis: Proper functions are finite somewhere and never −∞, while closed functions are lower semicontinuous.The domain consists of points where the function is finite.
- Variational analysis: The limiting subdifferential reduces to the classical convex subdifferential for convex functions and to the gradient for continuously differentiable functions.For composite functions with surjective M, the paper invokes calculus rules for this subdifferential.
- Stationarity: A stationary point is defined by satisfying the paper’s necessary optimality condition in place of an optimal solution.The condition is used to characterize algorithmic cluster points.
- Bregman distance: The Bregman distance is introduced for continuously differentiable functions, with bounds derived from upper or lower Hessian inequalities.These inequalities support the later convergence analysis.
- Semi-algebraic and KL properties: Semi-algebraic functions are defined through graphs formed from finite unions of polynomial equalities and strict inequalities, and proper closed semi-algebraic functions are KL functions.The KL property is stated using a concave desingularizing function satisfying a subgradient inequality.
3 Alternating direction method of multipliers
The paper analyzes proximal ADMM for nonconvex composite optimization, establishing stationarity of cluster points, whole-sequence convergence under semi-algebraicity, and boundedness conditions. It also identifies implementation simplifications, objective improvement under suitable initialization, and a concrete non-convergence boundary for injective maps.
- Algorithm and implementation: The proximal ADMM subproblems can use local quadratic approximations of h, reducing each iteration to a proximal mapping of τP and an unconstrained convex quadratic minimization.Choosing φ based on a Lipschitz modulus of ∇h can simplify the x-update to a convex quadratic programming problem.
- Objective behavior: With suitable initialization, every existing cluster point has strictly lower objective value than the starting point, although the objective need not decrease along the iterates.The strict improvement is h(x∗) + P(Mx∗) < h(x0) + P(Mx0).
- Boundedness: Additional sufficient conditions guarantee that the sequence generated by proximal ADMM is bounded, thereby ensuring existence of a cluster point.The paper gives conditions involving the model assumptions and a sufficiently large penalty parameter.
- Convergence guarantees: The whole ADMM sequence converges when h and P are semi-algebraic and a cluster point exists.Semi-algebraicity is presented as an easily verifiable sufficient condition and covers quadratic functions, polyhedral norms, and the cardinality function.
- Scope and limitations: For injective rather than surjective M, a two-dimensional example produces an eight-step limit cycle, so the ADMM iterates need not converge.In that example, the successive change in the z-update also fails to converge to zero.
4 Proximal gradient algorithm when M = I
When M = I, proximal gradient efficiently uses the simple proximal mapping of P. Under a flexible step-size condition, it is a descent method whose cluster points are stationary, with whole-sequence convergence under the KL property.
- Algorithm and setting: For M = I, proximal gradient applies because the objective combines a smooth term with a possibly nonsmooth term having a simple proximal mapping.Each update can be performed efficiently through a proximal mapping of βP.
- Convergence guarantees: The algorithm is a descent method, and any cluster point of the generated sequence is stationary.The descent conclusion follows from the update and the subdifferential inequality applied to the nonsmooth term.
- Step-size condition: The concave part of h imposes no step-size restriction under the theorem’s condition, potentially allowing a larger β than the Lipschitz bound for ∇h.Examples include β in (0, 2/(λ1 + λ2)) when λ1 < λ2, and any positive β for a concave quadratic.
- Convergence guarantees: If h + P is a KL-function and a cluster point exists, the whole sequence converges to that point.The analysis verifies the conditions used for the KL-based convergence theorem.
- Implementation: A line-search strategy can be incorporated, with the viable step-size interval providing an initial value for backtracking.The paper notes direct adaptation of existing convergence analysis for continuous difference-of-convex regularizers.
5 Numerical simulations
Numerical experiments evaluate ADMM on constraint-violation and piecewise-constant fitting problems, and proximal gradient under varying step sizes. The reported results show favorable recovery and feasibility behavior for ADMM, while larger proximal-gradient step sizes often reduce iterations but can affect solution quality.
- ADMM: ADMM is tested on finding points that violate at most r of m equalities, comparing the ℓ0 model with an ℓ1 relaxation.Experiments use random instances with full-row-rank M and compare ADMM against SDPT3 through CVX.
- ADMM: The ℓ0 model solved by ADMM always gives a solution closer to bx than the ℓ1 model in the reported constraint-violation experiments.An ADMM initialization from an approximate ℓ1 solution can be slightly closer to bx than zero initialization, depending on the instance.
- ADMM: In piecewise-constant fitting, DD* ⪰ σI with σ close to zero for large n makes the prescribed β large and can lead to slow convergence.A heuristic initializes β as 1/t while retaining clustering at a stationary point.
- ADMM: For piecewise-constant fitting, the model solution always has the correct number of pieces and is always closer to the original noiseless signal.The experiments use n = 8000, 10000, r = 50, 100, and noise levels τ = 0, 2.5%, and 5%.
- Proximal gradient algorithm: For concave minimization over compact convex sets, proximal gradient has bounded iterates and stationary cluster points for any β > 0.The experiments compare β values from 1/λmax(A*A) through 50/λmax(A*A).
- Proximal gradient algorithm: Larger β typically reduces proximal-gradient iterations, while solution quality depends on β for the unit ℓ∞ norm ball but not the easier unit ℓ1 norm-ball problems.Table 3 reports terminating function values and iteration counts for both constraint sets.
6 Conclusion and future directions
The paper concludes that proximal ADMM and proximal gradient produce stationary cluster points under the stated parameter and cluster-point assumptions. With semi-algebraic h and P, clustered ADMM sequences converge, while future work includes other splitting methods for injective M.
- Conclusion: For general surjective M and M = I, the studied proximal ADMM and proximal gradient methods have stationary cluster points under specific parameter choices and cluster-point existence.The result applies to the nonconvex model problem under the paper's assumptions.
- Conclusion: If h and P are semi-algebraic and the ADMM sequence clusters, the whole sequence converges.The paper also gives simple sufficient conditions ensuring boundedness of the proximal ADMM sequence.
- Future directions: A future direction is adapting other convex-problem splitting methods to problem (1), especially when M is injective.Their convergence properties in that setting remain to be studied.