New Analysis of Linear Convergence of Gradient-type Methods via Unifying Error Bound Conditions

Abstract

This paper reveals that a common and central role, played in many error bound (EB) conditions and a variety of gradient-type methods, is a residual measure operator. On one hand, by linking this operator with other optimality measures, we define a group of abstract EB conditions, and then analyze the interplay between them; on the other hand, by using this operator as an ascent direction, we propose an abstract gradient-type method, and then derive EB conditions that are necessary and sufficient for its linear convergence. The former provides a unified framework that not only allows us to find new connections between many existing EB conditions, but also paves a way to construct new EB conditions. The latter allows us to claim the weakest conditions guaranteeing linear convergence for a number of fundamental algorithms, including the gradient method, the proximal point algorithm, and the forward-backward splitting algorithm. In addition, we show linear convergence for the proximal alternating linearized minimization algorithm under a group of equivalent EB conditions, which are strictly weaker than the traditional strongly convex condition. Moreover, by defining a new EB condition, we show Q-linear convergence of Nesterov's accelerated forward-backward algorithm without strong convexity. Finally, we verify EB conditions for a class of dual objective functions.

40 papes; incorporating the referee's comments, the presentation has been further improved

References in corpus (8)

• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^2$
• Global optimality conditions for deep neural networks
• Second-order growth, tilt stability, and metric regularity of the subdifferential
• Characterization of Gradient Dominance and Regularity Conditions for Neural Networks
• Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry
• The Physical Systems Behind Optimization Algorithms
• On Faster Convergence of Cyclic Block Coordinate Descent-type Methods for Strongly Convex Minimization
• Exact worst-case convergence rates of the proximal gradient method for composite convex minimization

Cited by in corpus (7)

• The Physical Systems Behind Optimization Algorithms
• Adaptive Accelerated Gradient Converging Methods under Holderian Error Bound Condition
• Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions
• Linear Convergence of the Proximal Incremental Aggregated Gradient Method under Quadratic Growth Condition
• Inertial Proximal Incremental Aggregated Gradient Method
• On the Linear Convergence of the Cauchy Algorithm for a Class of Restricted Strongly Convex Functions
• Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than $O(1/\epsilon )$