Source-linked AI summary
Fixing and extending some recent results on the ADMM algorithm
Sebastian Banert, Radu Ioan Bot, Ernö Robert Csetnek
TL;DR
The paper revisits proof steps in proximal ADMM convergence analysis, including a statement used for convergence claims in. It proposes a gradient-evaluated, variable-metric ADMM variant and establishes convergence results for it.
Problem
Method
The paper formulates an ADMM variant for infinite-dimensional Hilbert spaces with an additional smooth objective function evaluated through its gradient and variable metrics at each iteration.
Source: §1 · p. 3Results
The paper gives a different proof technique for the statement and establishes an ergodic primal-dual-gap rate and convergence of iterates to a Lagrangian saddle point.
Source: §1 · pp. 3–4Takeaways & Limitations
The proposed variant is analyzed for both an ergodic primal-dual gap and convergence of its iterates to a saddle point.
Source: §1 · p. 4The x-update includes Ax, so f and A are not evaluated independently, making this ADMM form less attractive to implement than primal-dual splitting algorithms.
Source: §1 · pp. 2–3
Abstract
from arXiv · showhide
We investigate the techniques and ideas used in the convergence analysis of two proximal ADMM algorithms for solving convex optimization problems involving compositions with linear operators. Besides this, we formulate a variant of the ADMM algorithm that is able to handle convex optimization problems involving an additional smooth function in its objective, and which is evaluated through its gradient. Moreover, in each iteration we allow the use of variable metrics, while the investigations are carried out in the setting of infinite dimensional Hilbert spaces. This algorithmic scheme is investigated from the point of view of its convergence properties.
1 Introduction
The introduction presents ADMM for convex objectives involving a linear operator, reviews proximal variants and their convergence analysis, and identifies a proof flaw in prior work. It then outlines a variable-metric extension for infinite-dimensional Hilbert spaces with an additional smooth, gradient-evaluated term and convergence results.
1 Introduction
- For classical ADMM, the stated convergence result requires A to have full column rank, while the minimizers in the x-update are then unique.The z-update minimizer is unique without an additional assumption.Source: §1 · p. 2
- Classical ADMM couples f and A in its x-update, making it less attractive for implementation than primal-dual splitting algorithms.The introduction motivates a proximal variant as a way to overcome this drawback.Source: §1 · pp. 2–3
- With positive semidefinite metrics, Algorithm 2 recovers classical ADMM at M1=M2=0 and, under specified metric choices, the algorithm and a [13] primal-dual algorithm.Source: §1 · p. 3
- The paper identifies a flaw in a proof underlying prior convergence claims and develops different techniques to establish the needed result.It also formulates a smooth-function, variable-metric ADMM variant in infinite-dimensional Hilbert spaces and proves an ergodic primal-dual gap rate and convergence of iterates to a saddle point.Source: §1 · pp. 3–4
- The proposed variant handles an additional smooth objective term through its gradient, allows variable metrics at each iteration, and is studied in infinite-dimensional Hilbert spaces.The paper reports an ergodic convergence rate for a Lagrangian primal-dual gap and convergence of iterates to a saddle point.Source: §1 · pp. 3–4
2 Fixing some results from [25] related to the convergence analysis for Algorithm 2
This section revisits a proof step in that supports residual-rate and iterate-convergence claims for Algorithm 2. It shows how monotonicity-based techniques establish the needed inequality and recover those convergence conclusions.
2 Fixing some results from [25] related to the convergence analysis for Algorithm 2
- The proof in assumes an inequality that its stated techniques establish only in a weaker form, leaving the claimed residual rate and iterate convergence unsupported by that argument.The stronger inequality is used for the O(1/k) rate of ∥Ax^k−z^k∥ and convergence of iterates to a Lagrangian saddle point.Source: §2 · p. 5
- The section derives the needed inequality using different techniques based on monotonicity of convex subdifferentials, rather than the function-value and saddle-point arguments in.The authors state that their analysis uses properties of the convex subdifferential as a monotone set-valued operator.Source: §2 · p. 5
- The corrected inequality, together with a decreasing sequence and telescoping arguments, yields an O(1/k) convergence rate for ∥Ax^k−z^k∥.The authors identify this inequality as an essential part of their subsequent iterate-convergence analysis.Source: §2 · p. 6
- The section presents its correction as providing a rigorous formulation and proof of the convergence result stated in [25, Theorem 5.6].The broader purpose is to fix arguments used for both residual decay and convergence of the generated sequence to a saddle point.Source: §2 · pp. 4, 6
3 A variant of the ADMM algorithm in the presence of a smooth function and by involving variable metrics
The section extends ADMM to problems with a smooth convex term evaluated through its gradient and iteration-dependent metrics in infinite-dimensional Hilbert spaces, and analyzes ergodic and weak convergence. Under the considered assumptions, the iterates converge weakly to a Lagrangian saddle point; the analysis also corrects a previously flawed ADMM proof and includes classical ADMM as a special case.
3 A variant of the ADMM algorithm in the presence of a smooth function and by involving variable metrics
- The proposed extension of ADMM adds a convex differentiable function evaluated through its gradient, uses different metrics at each iteration, and works in Hilbert spaces.The smooth function is Fréchet differentiable with an L-Lipschitz continuous gradient.Source: §3 · p. 6
3.1 Ergodic convergence rates for the primal-dual gap
- Theorem 12 establishes an ergodic primal-dual-gap estimate for averaged iterates when the second metric is nonincreasing; a bound also follows when dual optimal solutions are bounded.The theorem’s estimate applies to the ergodic sequences defined in the result.Source: §3.1 · pp. 9, 11, 12
3.2 Convergence of the sequence of generated iterates
- With a nonempty saddle-point set, nonincreasing second metrics, and one of Theorem 15’s stated conditions, the iterates converge weakly to a saddle point.The proof uses monotone-operator techniques without objective-function or Lagrangian values, unlike the proofs in and other conventional ADMM analyses.Source: §3.2 · pp. 12–13
- Under Assumptions (I), (II), and (III), the generated iterates converge weakly to a saddle point of the Lagrangian.For Assumption (II), the proof establishes that every weak sequential cluster point is a saddle point and that the cluster-point set is a singleton; the proof under Assumption (III) follows the same argument.Source: §3.2 · pp. 16–18
- Theorem 15 provides a correct proof of the result in [25, Theorem 5.6] for h = 0, L = 0, M_k^1 = 0, and constant M_k^2 = M_2 ≽ 0 under Assumption (III).The paper notes that the earlier proof for M_1 = 0 and full-column-rank A contains flaws and relies on incorrect statements.Source: §3.2 · p. 19
- Theorem 15 under Assumption (III) also covers convergence of classical ADMM iterates when h = 0, L = 0, M_1 = M_2 = 0, and A has full column rank, as in.Source: §3.2 · p. 19