Source-linked AI summary
The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates
Radu Ioan Bot, Dang-Khoa Nguyen
TL;DR
The paper studies minimizing a smooth function plus a nonsmooth function composed with a linear operator. It proposes two proximal ADMM schemes and proves KKT convergence under a Kurdyka-Lojasiewicz condition, with convergence rates under a Lojasiewicz condition.
Problem
The paper studies minimizing the sum of a smooth function and a nonsmooth function composed with a linear operator.
Source: §1.1 · p. 1Method
It proposes proximal ADMM and proximal linearized ADMM schemes with variable metrics for the nonconvex problem.
Source: §1.1 · p. 2Results
The iterates converge to a KKT point when a regularization of the augmented Lagrangian has the Kurdyka-Lojasiewicz property, and convergence rates hold when the augmented Lagrangian has the Lojasiewicz property.
Source: §1.1 · p. 2, §2.3 · p. 21, §3 · p. 22Takeaways & Limitations
To the authors’ knowledge, these are the first convergence-rate results for nonconvex ADMM.
Source: §1.1 · p. 2The analysis relies on surjectivity of the linear operator, an assumption the authors say cannot presently be omitted for convergence of nonconvex Lagrangian-based algorithms.
Source: §2.1 · p. 8
Abstract
from arXiv · showhide
We propose two numerical algorithms in the fully nonconvex setting for the minimization of the sum of a smooth function and the composition of a nonsmooth function with a linear operator. The iterative schemes are formulated in the spirit of the proximal alternating direction method of multipliers and its linearized variant, respectively. The proximal terms are introduced via variable metrics, a fact which allows us to derive new proximal splitting algorithms for nonconvex structured optimization problems, as particular instances of the general schemes. Under mild conditions on the sequence of variable metrics and by assuming that a regularization of the associated augmented Lagrangian has the Kurdyka-Lojasiewicz property, we prove that the iterates converge to a KKT point of the objective function. By assuming that the augmented Lagrangian has the Lojasiewicz property, we also derive convergence rates for both the augmented Lagrangian and the iterates.
1 Introduction
The paper studies nonconvex minimization using proximal ADMM and proximal linearized ADMM schemes, with convergence and rate guarantees. It also presents notation, sequence results, and a technical lemma for the analysis.
1.1 Problem formulation and motivation
- The problem formulation combines a proper lower-semicontinuous g composed with a linear operator A and a Fréchet-differentiable h with Lipschitz-continuous gradient.The objective is to minimize g(Ax) + h(x).Source: §1.1 · p. 1
- The proposed P-ADMM and PL-ADMM iterates are bounded, have KKT cluster points, and converge globally under a Kurdyka–Łojasiewicz condition on a regularized augmented Lagrangian.If the regularization has the Łojasiewicz property, the paper derives convergence rates for the iterates; the authors identify these as the first nonconvex ADMM convergence-rate results.Source: §1.1 · p. 2
- Under general assumptions, boundedness is central to the convergence analysis; the paper assumes g is smooth because this enables its bounded-iterate result.The paper also emphasizes that prior nonconvex ADMM analyses did not propose full-splitting schemes for problems involving compositions with linear operators, and that it addresses boundedness and convergence rates.Source: §1.1 · p. 3
- Appropriate variable metrics yield full-splitting algorithms: P-ADMM uses proximal steps for g and h, while PL-ADMM handles h with a gradient step.The P-ADMM and PL-ADMM schemes also admit relaxed dual updates with ρ in (0, 2).Source: §1.1 · p. 3
1.2 Notations and preliminaries
- The preliminaries establish limiting-subdifferential rules for smooth sums and injective linear compositions, alongside notation for variable-metric norms and operator properties.The rules support the later convergence analysis.Source: §1.2 · pp. 4–5
- A sequence lemma states that a bounded-below sequence with successive decreases controlled by nonnegative terms is monotonically decreasing and convergent.This result is presented for use in the subsequent convergence analysis.Source: §1.2 · p. 5
- A preliminary lemma extends [13, Lemma 2.3] and [16, Lemma 3].The passage notes that the lemma is also of interest in its own right.Source: §1.2 · p. 5
2 A proximal ADMM algorithm and a proximal linearized ADMM algorithm in the nonconvex setting
This section introduces two nonconvex proximal ADMM schemes—a full proximal splitting method and a linearized variant—and analyzes the sequences they generate using the associated augmented Lagrangian. It establishes boundedness and convergence controls, including finite-length convergence to a KKT point when the regularized augmented Lagrangian has the Kurdyka–Łojasiewicz property.
2 A proximal ADMM algorithm and a proximal linearized ADMM algorithm in the nonconvex setting
- The section proposes two proximal ADMM algorithms for the optimization problem and makes the associated augmented Lagrangian central to their convergence analysis.The Lagrangian is defined for every positive penalty parameter.Source: §2 · p. 7
2.1 General formulations and full proximal splitting algorithms as particular instances
- The full proximal splitting instance evaluates g and h through proximal operators and applies the linear operator and its adjoint in forward steps.The passage notes that proximal formulas are available for many nonconvex functions arising in applications.Source: §2.1 · p. 7
- The second algorithm linearizes h at the current iterate, evaluating the smooth term by a gradient step, and its variable-metric scheme unifies several linearized ADMM algorithms [35, 36, 40, 41, 48, 50].This avoids placing the smooth function in a subproblem, which may be difficult to solve.Source: §2.1 · pp. 7–8
- The stated convergence setting assumes A is surjective; the authors note that this assumption cannot currently be omitted for nonconvex Lagrangian-based convergence proofs.Source: §2.1 · p. 8
- With particular metric choices, the schemes recover classical ADMM and linearized ADMM, and their convergence analysis does not require monotonicity of the metric-inducing matrix sequences.The passage contrasts this with monotonicity assumptions commonly used for variable-metric algorithms in convex optimization [5].Source: §2.1 · pp. 9–10
2.2 Preliminaries of the convergence analysis
- Under Assumption 1, preliminary lemmas establish a monotonicity result and three estimates used in the convergence analysis.Source: §2.2 · pp. 10, 12, 13
- Theorem 6 states that, assuming Assumption 1, the sequence is bounded under either (B-I), A is invertible and g is coercive, or (B-II), h is coercive.Source: §2.2 · pp. 14–15
- Under Assumption 1, Theorem 7 states that F_k is bounded below and convergent, successive x, z, and y differences vanish, and the specified sequences share a common limit.Source: §2.2 · pp. 15–16
- Limiting-subgradient estimates for the augmented and regularized augmented Lagrangians are bounded above in terms of the iterates.The estimates apply to sequences generated by either algorithm under Assumption 1.Source: §2.2 · pp. 16–17
- For bounded generated sequences, the cluster set is nonempty, connected, and compact, and its projected points satisfy the KKT conditions.The objective has the same limiting value on that projection.Source: §2.2 · p. 18
- The cluster points of the augmented sequence are critical points of the regularized augmented Lagrangian, where that function takes its limiting value.The limiting value agrees with the objective value on the projection onto the x component.Source: §2.2 · p. 20
2.3 Convergence analysis under Kurdyka- Lojasiewicz assumptions
- If the regularized augmented Lagrangian is a KL function, a bounded sequence generated by either algorithm has finite length and converges to a KKT point.The associated energy sequence decreases monotonically to zero.Source: §2.3 · p. 21
- The iterate sequence is Cauchy and converges to a KKT point of problem (1).The convergence analysis also establishes that the sum of successive x-iterate differences is finite.Source: §2.3 · p. 22
- Fr is a Kurdyka–Łojasiewicz function, for instance, when the objective functions g and h are semialgebraic.Source: §2.3 · p. 22
3 Convergence rates under Lojasiewicz assumptions
This section establishes exponent-dependent convergence rates for bounded sequences generated by Algorithms 1 and 2 under Łojasiewicz assumptions. It gives rates for the augmented Lagrangian values and iterates, including the case ρ = 1 under the original Assumption 1.
3.2 Convergence rates
- The section also derives convergence rates for the iterates of both algorithms from the regularized augmented Lagrangian rates.This transfer is considered for bounded sequences under Assumption 2 and the Łojasiewicz property.Source: §3 · p. 22, §3.2 · p. 27
3.1 Lojasiewicz property and a technical lemma
- For bounded algorithm sequences, the cluster set is nonempty, compact, and connected; the Łojasiewicz property then implies it is a singleton and the sequence converges.The regularized augmented Lagrangian is constant on the cluster set, and its cluster points are critical points of the associated Lagrangian.Source: §3.1 · p. 23
- Under Lemma 15’s assumptions, for a monotonically decreasing sequence converging to 0, if θ∈(0,1/2], there exist C_e,0>0 and Q∈[0,1) such that 0≤e_k≤C_e,0Q^k for every k≥k_0.Source: §3.1 · p. 23
3.2 Convergence rates
- For θ in (0, 1/2], the augmented Lagrangian gap decays geometrically; for θ in (1/2, 1), it is bounded by a constant times (k − 1)^−1.These bounds apply to F_k − F* for bounded sequences generated by Algorithm 1 or Algorithm 2 under Assumption 2 and the Łojasiewicz property of F_r.Source: §3.2 · p. 27
- Theorem 20 assumes Assumption 2 and a Łojasiewicz property with constant CL > 0 and exponent θ ∈ [0, 1), for a KKT point of problem (1) approached as k→∞.Source: §3.2 · p. 28
- For θ = 0 the algorithms converge in finite time; for θ in (0, 1/2] and (1/2, 1), Theorem 20 gives separate rate regimes.The first positive-exponent regime includes a geometric factor Q in [0, 1); the supplied passages do not preserve the remaining rate formulas.Source: §3.2 · p. 28
- When ρ = 1, the same convergence rates hold under the original Assumption 1.The remark notes that ρ = 1 makes T1 = 0.Source: §3.2 · p. 29