Error bounds, quadratic growth, and linear convergence of proximal methods

Understand

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.