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

Dmitriy Drusvyatskiy () and Adrian S. Lewis ()
Additional contact information
Dmitriy Drusvyatskiy: Department of Mathematics, University of Washington, Seattle, Washington 98195
Adrian S. Lewis: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853

Mathematics of Operations Research, 2018, vol. 43, issue 3, 919-948

Abstract: The proximal gradient algorithm for minimizing the sum of a smooth and 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 and quadratic 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.

Keywords: proximal algorithm; error bound; quadratic growth; linear convergence; subregularity; subdifferential; tilt-stability (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0889 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:43:y:2018:i:3:p:919-948

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().