Strong Convergence of FISTA Iterates under Hölderian and Quadratic Growth Conditions

2024/07/24 by Aujol, Jean-François, Dossal, Charles, Labarrière, Hippolyte +1 · 2 citations
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2407.17063

Abstract

Introduced by Beck and Teboulle, FISTA (for Fast Iterative Shrinkage-Thresholding Algorithm) is a first-order method widely used in convex optimization. Adapted from Nesterov's accelerated gradient method for convex functions, the generated sequence guarantees a decay of the function values of O(n^-2) in the convex setting. We show that for coercive functions satisfying some local growth condition (namely a H''olderian or quadratic growth condition), this sequence strongly converges to a minimizer. This property, which has never been proved without assuming the uniqueness of the minimizer, is associated with improved convergence rates for the function values. The proposed analysis is based on a preliminary study of the Asymptotic Vanishing Damping system introduced by Su et al. in to modelNesterov's accelerated gradient method in a continuous setting. Novel improved convergence results are also shown for the solutions of this dynamical system, including the finite length of the trajectory under the aforementioned geometry conditions.

Cited by

• Continuized Nesterov Acceleration for Non-Convex Optimization
• On the Effectiveness of the z-Transform Method in Quadratic Optimization

Related

• Linear convergence of forward-backward accelerated algorithms without knowledge of the modulus of strong convexity
• The iterates of FISTA convergence even under inexact computations and stochastic gradients
• Fast inertial dynamics and FISTA algorithms in convex optimization. Perturbation aspects
• Restart FISTA with Global Linear Convergence
• Lyapunov analysis for FISTA under strong convexity