Source-linked AI summary
Error bounds, quadratic growth, and linear convergence of proximal methods
Dmitriy Drusvyatskiy, Adrian S. Lewis
TL;DR
The paper addresses the opaque assumptions behind error-bound analyses of linear convergence. It establishes their equivalence with quadratic growth and extends the analysis to proximal methods for nonsmooth compositions with smooth mappings, while identifying a slower nonconvex rate that quadratic growth restores to the natural rate.
Problem
Error-bound parameters are difficult to interpret because they depend on the prox-gradient mapping rather than directly stated problem data.
Method
The paper systematically relates error bounds to quadratic growth and analyzes proximal gradient and prox-linear methods through their connection to the proximal point algorithm.
Results
The analysis yields linear convergence guarantees and extends to proximal methods for nonsmooth functions composed with smooth mappings.
Takeaways & Limitations
Quadratic growth provides a transparent objective-level characterization of error bounds and supports natural-rate convergence under the stronger condition.
Takeaways & Limitations
For nonconvex prox-linear methods, error bounds alone can produce a linear rate an order of magnitude slower than the natural rate.
Abstract
from arXiv · showhide
The proximal gradient algorithm for minimizing the sum of a smooth and a nonsmooth convex function often converges linearly even without strong convexity. One common reason is that a multiple of the step length at each iteration may linearly bound the "error" -- the distance to the solution set. We explain the observed linear convergence intuitively by proving the equivalence of such an error bound to a natural quadratic growth condition. Our approach generalizes to linear convergence analysis for proximal methods (of Gauss-Newton type) for minimizing compositions of nonsmooth functions with smooth mappings. We observe incidentally that short step-lengths in the algorithm indicate near-stationarity, suggesting a reliable termination criterion.
1 Introduction
The paper explains linear convergence through an equivalence between error bounds and quadratic growth, extending the analysis from proximal gradient to prox-linear methods. It also connects step lengths with near-stationarity and studies broader composite settings.
- Motivation: Error bounds linearly relate algorithmic step lengths to distance from the solution set, providing convergence analysis without strong convexity.The assumption is analytically useful but initially opaque as a property of the optimization problem.
- Contributions: The paper systematically proves equivalence between quadratic growth away from minimizers and error bounds in proximal-gradient and related frameworks.The approach targets problems with convex smooth-plus-nonsmooth structure and more general convex-composite structure.
- Contributions: The analysis views proximal-gradient and prox-linear methods as approximations of the proximal point algorithm, yielding linear convergence guarantees under mild assumptions.The assumptions rely primarily on a natural strict complementarity condition.
- Limitations: For prox-linear methods, error bounds alone can give a rate an order of magnitude worse than the natural convex prox-gradient rate because linearizations need not lower-bound the objective.Quadratic growth restores the natural rate in the stated setting.
- Contributions: Short prox-linear step lengths indicate near-stationarity and can support termination with explicit guarantees on final-solution quality.The step is zero at stationary points and otherwise serves as a surrogate measure of optimality.
- Extensions: The paper extends key analytical ingredients to composite optimization where the outer function may be nonconvex or discontinuous.The authors describe this extension as considerably more technical.
2 Preliminaries
The preliminaries establish notation for Euclidean spaces, extended-real-valued functions, subdifferentials, proximal mappings, and set-valued mappings used throughout the analysis.
- Notation: The paper uses Euclidean-space notation, including the norm, inner product, closed unit ball, open balls, and distance functions.These conventions support the later error and convergence statements.
- Functions and sets: Functions may take values in the extended real line, with closedness and sublevel sets defined in the standard way.Indicator functions evaluate to zero on a set and +∞ elsewhere.
- Subdifferentials: For convex functions, the subdifferential consists of vectors satisfying the global supporting-affine inequality.This definition underlies the paper’s error-bound conditions.
- Proximal objects: The Moreau envelope and proximal map provide the smoothing and implicit-update objects used by proximal algorithms.The proximal map is always 1-Lipschitz continuous.
- Mappings: Set-valued mappings, their graphs, inverse maps, and resolvent identities supply the variational-analysis language for the algorithms.For convex g, proxtg = (I + t∂g)^−1.
3 Linear convergence of the prox-gradient method
This section establishes that proximal-gradient linear convergence can be characterized equivalently by error bounds and quadratic growth. The proof compares proximal-gradient steps with proximal-point steps and derives the resulting convergence guarantee.
- Error bounds: The error bound condition requires distance to the minimizer set to be bounded by γ times the prox-gradient mapping norm on a sublevel set.This condition is introduced with parameters (γ, ν).
- Linear convergence: Under the error bound condition, proximal gradient with t ≤ β^-1 achieves linear convergence in function values.The theorem gives an explicit iteration bound for reaching ϕ(xk) − ϕ* ≤ ϵ.
- Quadratic growth: The error bound is equivalent to quadratic growth of the objective away from its minimizing set, making the convergence assumption more transparent.Quadratic growth is described as familiar and weaker than strong convexity in relevant smooth examples.
- Subdifferential characterization: Quadratic growth and subdifferential error bounds are equivalent for closed convex functions, with explicit relationships between their parameters.The converse holds for any α in the stated admissible interval.
- Proximal error bounds: Subdifferential error bounds are equivalent to proximal-map error bounds, with constants differing by the step length t.The proximal identity links t^-1∥x − proxt h(x)∥ to subgradients.
- Step-length comparison: The proximal-gradient and proximal-point step lengths are proportional, allowing the proximal-point error-bound theory to transfer to proximal gradient.The prox-gradient mapping vanishes exactly at optimal points.
- Final convergence result: Quadratic growth therefore yields a proximal-gradient complexity bound matching, up to a constant, the linear rate for strongly convex functions.The result applies with t ≤ β^-1.
4 Quadratic growth in structured optimization
This section establishes quadratic-growth and error-bound results for structured convex composite optimization, including settings that do not require strong convexity. It also identifies broad function classes where the assumptions hold and shows preservation properties for separable sums and Moreau envelopes.
- Firm convexity: Firm convexity is defined through quadratic growth of a tilted function relative to a vector.The tilted function is h_v(x) := h(x) −⟨v, x⟩, and the growth condition is required on compact sets.
- Main theorem: Strong convexity is unnecessary for the theorem, allowing robust formulations based on translated Huber penalties and asymmetric extensions.The paper contrasts this with prior work that required strong convexity of f.
- Problem setting: The analysis studies composite problems involving a smooth convex function composed with a linear map and a closed convex function.The objective is represented as ϕ(x) := f(Ax) + g(x), within a Fenchel-dual framework.
- Main theorem: Theorem 4.2 derives quadratic growth for the composite objective under compactness, dual nondegeneracy, strict complementarity, and firm convexity of both components.The component functions must be firmly convex relative to the dual vectors ȳ and −A^T ȳ.
- Examples and closure properties: Firm convexity includes strongly convex, polyhedral, convex PLQ, and several affinely composed PLQ functions, including elastic net and soft-insensitive loss.The class also includes Moreau envelopes of polyhedral functions and the nuclear norm.
- Corollary 4.3: For convex PLQ g, the error-bound condition holds when f is either strictly convex or PLQ, without requiring strict complementarity.Polyhedral subdifferentials or a singleton subdifferential ensure the needed inequality.
- Examples and closure properties: Firm convexity is preserved under separable sums and Moreau envelopes.These closure properties extend the usable function class for structured optimization models.
5 Prox-linear algorithm
The prox-linear method applies proximal optimization to convex-composite problems, using linearized subproblems and a prox-gradient mapping to obtain descent, convergence, and near-stationarity guarantees. Under an error bound, function values converge Q-linearly and iterates R-linearly, while quadratic growth recovers the natural rate in relevant settings.
- Problem class: The prox-linear method targets nonsmooth, generally nonconvex convex-composite problems with a convex function composed with a smooth mapping.The framework uses a proper closed convex outer function and a smooth mapping, seeking first-order stationary points.
- Algorithm: Each iteration minimizes a convex linearized proximal model, and the prox-gradient mapping G_t(x) vanishes exactly at stationary points.The linearized model is convex even when the original objective is not; for suitable steps, it also provides a quadratic upper estimator.
- Global convergence: The method provides global descent and convergence guarantees: prox-gradient norms are square-summable, and an iterate with norm squared at most ε is found after 2Lβ(ϕ(x1) − ϕ*)/ε iterations.The function values converge to ϕ*, while the stated iteration bound certifies a nearly stationary point.
- Termination: A small prox-gradient step implies proximity to a nearly stationary point, supporting the reliability of the algorithm’s termination criterion.The near-stationarity result assumes h is L-Lipschitz continuous and ∇c is β-Lipschitz.
- Linear convergence: Around a limit point satisfying the error bound condition, function values converge Q-linearly and iterates converge R-linearly.The result applies with t ≤ (Lβ)^−1 and requires an error-bound parameter γ > 0 locally.
- Error bounds and quadratic growth: The error bound is equivalent to subdifferential subregularity with explicit constant relationships, which is tied to quadratic growth in convex or tame settings.For the prox-linear method, the error bound and subdifferential subregularity imply one another under the stated Lipschitz assumptions.
6 Natural rate of convergence under tilt-stability
Under tilt-stability and equivalent uniform-growth conditions, the prox-linear method achieves its natural linear convergence rate, improving on the slower error-bound rate.
- Equivalent stability conditions: Theorem 6.2 establishes equivalence among uniform quadratic growth, local subdifferential convexity, tilt-stability, and strong regularity of the subdifferential.These properties characterize stable strong local minimizers in the convex-composite setting.
- Baseline rate: The weaker error-bound condition yields a linear rate on the order of 1 − (α/Lβ)^2.This rate follows from subdifferential subregularity with constant 1/α.
- Natural rate: Under the stronger equivalent conditions, the prox-linear method accelerates to a natural rate on the order of 1 − α/Lβ.The theorem assumes h is L-Lipschitz, ∇c is β-Lipschitz, t ≤ (Lβ)^−1, and the iterates have a limit point satisfying one equivalent property.
- Convergence guarantees: The resulting function values converge Q-linearly, while the iterates converge R-linearly.The proof derives the Q-linear guarantee from the main rate inequality and obtains the R-linear rate by a standard argument.
7 Proximal gradient method without convexity
The proximal gradient method without convexity is treated as a special case of the prox-linear algorithm, allowing the general convergence theory to apply with simpler arguments.
- Nonconvex setting: The general results apply immediately to the proximal gradient method without requiring convexity in f.The section explicitly revisits proximal gradient in the absence of convexity in f.
- Reduction to prox-linear: The proximal gradient method is an instance of the prox-linear algorithm applied to ϕ = g + Id ◦ f.In this additive case, the framework uses L = 1.
- Simplified analysis: The additive case simplifies the analysis because Ekeland’s variational principle is unnecessary for relating subdifferential subregularity to the error-bound property.The proximal subproblem’s optimality conditions also yield an improved estimate.
- Error bounds and rates: The error-bound and prox-gradient subregularity conditions are compared through the same equivalence framework used for the broader prox-linear analysis.The section considers subregularity of the prox-gradient mapping and derives corresponding rate estimates.
8 The proximal subproblem in full generality
The paper extends the proximal-subproblem analysis to nonsmooth, nonconvex, and potentially infinite-valued compositions, using variational analysis to recover error-bound equivalences under transversality and prox-regularity.
- Problem framework: The broader framework drops convexity and finite-valuedness assumptions while studying stationary points of the original and linearized proximal functions.For convenience, one section sets g = 0, while stating that results extend to the general setting.
- General-setting difficulty: Directly solving the linearized proximal subproblems can fail because they may be nonconvex and can become infeasible.The latter issue can stall the algorithm, motivating a different analysis and future algorithmic work.
- Variational machinery: Transversality supplies the variational regularity needed to compare the original composite problem with its linearized proximal subproblems.The analysis relies on metric regularity and its stability under small linear perturbations.
- Comparison theorem: Theorem 8.6 establishes local comparison inequalities for composite problems satisfying transversality and having locally Lipschitz Jacobians.These inequalities support the subsequent relationship between algorithmic mappings and the original subdifferential.
- Error-bound equivalence: Theorem 8.11 gives equivalence between subdifferential subregularity and the error-bound property under the stated prox-regularity assumptions.When h is convex, the converse holds for arbitrary t > 0 without localization.