The restricted strong convexity revisited: Analysis of equivalence to error bound and quadratic growth
Author:
Preprint
Abstract
The restricted strong convexity is an effective tool for deriving globally linear convergence rates of descent methods in convex minimization. Recently, the global error bound and quadratic growth properties appeared as new competitors. In this paper, with the help of Ekeland's variational principle, we show the equivalence among these three notions. To deal with convex minimization over a closed convex set and structured convex optimization, we propose a group of modified versions and a group of extended versions of these three notions by using gradient mapping and proximal gradient mapping separately, and prove that the equivalence among the modified and extended versions still holds. Based on these equivalence notions, we establish new asymptotically linear convergence results for the proximal gradient method. Finally, we revisit the problem of minimizing the composition of an affine mapping with a strongly convex differentiable function over a polyhedral set, and obtain a strengthened property of the restricted strong convex type under mild assumptions.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- A unified approach to error bounds for structured convex optimization problemsMathematical Programming, 2017
- From error bounds to the complexity of first-order descent methods for convex functionsMathematical Programming, 2016
- Linearly convergent away-step conditional gradient for non-strongly convex functionsMathematical Programming, 2016
- Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence PropertiesSIAM Journal on Optimization, 2015
- Restricted strong convexity and its applications to convergence analysis of gradient-type methods in convex optimizationOptimization Letters, 2014
- Augmented $\ell_1$ and Nuclear-Norm Models with a Globally Linearly Convergent AlgorithmSIAM Journal on Imaging Sciences, 2013
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse ProblemsSIAM Journal on Imaging Sciences, 2009
- On the Linear Convergence of Descent Methods for Convex Essentially Smooth MinimizationSIAM Journal on Control and Optimization, 1992
- Lipschitz Continuity of Solutions of Linear Inequalities, Programs and Complementarity ProblemsSIAM Journal on Control and Optimization, 1987
- Bounds for error in the solution set of a perturbed linear programLinear Algebra and its Applications, 1973