Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods

By Dmitriy Drusvyatskiy, A. S. Lewis. 2016

394 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition (2016, background): “…holds for other problems where a linear convergence rate has been show like group L1-regularization [Tseng, 2010], sparse group L1-regularization [Zhang et al., 2013], nuclear-norm regularization [Hou et al., 2013], and other classes of functions [Zhou and So, 2015, Drusvyatskiy and Lewis, 2016].”
The importance of better models in stochastic optimization (2019, background): “Finding global minima of nonconvex functions is computationally infeasible (28), so we follow established practice and consider convergence to stationary points via the Moreau envelope (5, 29).”
A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem (2022, background): “, X ∗ g is a set of weak sharp minima of g (Burke and Ferris, 1993; Burke and Deng, 2005); 2) g satisfies (11) with r = 2 known as quadratic growth condition (Drusvyatskiy and Lewis, 2018).”
On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems (2019, neutral): “Then, we have Since f (ˆ x , · ) is µ -strongly-concave over Y , the global error bound condition [Drusvyatskiy and Lewis, 2018] holds true here and we have Therefore, we conclude that ∥∇ Φ(ˆ x ) ∥ ≤ ϵ + ϵ/κ = O ( ϵ ) .”
Better Theory for SGD in the Nonconvex World (2020, background): “…if for all x ∈ R d where f (cid:63) is the minimum value of f and where π ( x ) def = argmin y ∈ X x − y 2 is the projection on the set of minima There are only a handful of results under QFG (Drusvyatskiy & Lewis, 2018; Necoara et al., 2019; Sun, 2019), none of which is for SGD with smooth losses.”
Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity (2018, background): “A substantial body of work investigates this modeling perspective [11, 18], and recent work by Duchi and Ruan [19] and Davis and Drusvyatskiy [14] demonstrates convergence for appropriate models in weakly convex stochastic optimization, motivating our approach.”
The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth (2015, methodology): “Similarly, the modiﬁed and extended versions can be used to derive globally linear convergence results for a large class of descent methods in convex minimization [13, 5, 6, 3].”
Linear convergence of first order methods for non-strongly convex optimization (2015, background): “Similar results have appeared independently around the time this paper was ﬁnalized, e.g in [8,12,14,15].”
Subgradient Methods for Sharp Weakly Convex Functions (2018, background): “Our current work sits within the broader scope of analyzing subgradient and proximal methods for weakly convex problems [9, 11, 13–16, 25, 26]; see also the recent survey [12].”
Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity (2017, background): “2 Improved Convergence Without Strong Convexity Strong convexity is stronger than necessary to achieve many of the standard improvements in convergence rate for smooth optimization problems [1, 4, 10, 11].”