The restricted strong convexity revisited: analysis of equivalence to error bound and quadratic growth

By Hui Zhang. 2015

56 citations recorded by the source corpus.

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 between 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 for 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.

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): “Indeed, all of the relationships that have been explored have only been in the context of convex functions [Liu and Wright, 2015, Necoara et al., 2015, Zhang, 2015].”
Choosing the Sample with Lowest Loss makes SGD Robust (2020, methodology): “n any point w and the point w , the surrogate loss function F~ is convex from any point { even though it is not convex overall. This is akin to the restricted secant inequality condition described in [17, 37]. The following theorem uses this lemma to establish our rst result: that in the noiseless s”