Another look at the fast iterative shrinkage/thresholding algorithm (FISTA)

Abstract

This paper provides a new way of developing the fast iterative shrinkage/thresholding algorithm (FISTA) that is widely used for minimizing composite convex functions with a nonsmooth term such as the ${\ell }_1$ regularizer. In particular, this paper shows that FISTA corresponds to an optimized approach to accelerating the proximal gradient method with respect to a worst-case bound of the cost function. This paper then proposes a new algorithm that is derived by instead optimizing the step coefficients of the proximal gradient method with respect to a worst-case bound of the composite gradient mapping. The proof is based on the worst-case analysis called Performance Estimation Problem.

minor modification in the title

References in corpus (3)

• Exact Worst-case Performance of First-order Methods for Composite Convex Optimization
• Generalizing the optimized gradient method for smooth convex minimization
• On the convergence analysis of the optimized gradient method

Cited by in corpus (15)

• Acceleration Methods
• Generalizing the optimized gradient method for smooth convex minimization
• Inertial, corrected, primal-dual proximal splitting
• Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions
• Accelerated Proximal Point Method for Maximally Monotone Operators
• Optimal Nonergodic Sublinear Convergence Rate of Proximal Point Algorithm for Maximal Monotone Inclusion Problems
• Fast dual proximal gradient algorithms with rate $O(1/k^{1.5})$ for convex minimization
• On the Optimal Ergodic Sublinear Convergence Rate of the Relaxed Proximal Point Algorithm for Variational Inequalities
• Computer-Assisted Design of Accelerated Composite Optimization Methods: OptISTA
• Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums
• Optimal First-Order Algorithms as a Function of Inequalities
• A Geometric Structure of Acceleration and Its Role in Making Gradients Small Fast
• Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates
• On the dual step length of the alternating direction method of multipliers
• Convergence Rate of Inertial Forward-Backward Algorithms Based on the Local Error Bound Condition