Parameter-Free FISTA by Adaptive Restart and Backtracking

Jean–François Aujol, Luca Calatroni, Charles Dossal, Hippolyte Labarrière, Aude Rondepierre

Abstract

We consider a combined restarting and adaptive backtracking strategy for the popular Fast Iterative Shrinking-Thresholding Algorithm (FISTA) frequently employed for accelerating the convergence speed of large-scale structured convex optimization problems. Several variants of FISTA enjoy a provable linear convergence rate for the function values $F(x_n)$ of the form $\mathcal{O}( e^{-K\sqrt{μ/L}~n})$ under the prior knowledge of problem conditioning, i.e., of the ratio between the (Łojasiewicz) parameter $μ$ determining the growth of the objective function and the Lipschitz constant $L$ of its smooth component. These parameters are nonetheless hard to estimate in many practical cases. Recent works address the problem by estimating either parameter via suitable adaptive strategies. In our work, both parameters can be estimated at the same time by means of an algorithmic restarting scheme where, at each restart, a non-monotone estimation of $L$ is performed. For this scheme, theoretical convergence results are proved, showing that a $\mathcal{O}( e^{-K\sqrt{μ/L}n})$ convergence speed can still be achieved along with quantitative estimates of the conditioning. The resulting Free-FISTA algorithm is therefore parameter-free. Several numerical results are reported to confirm the practical interest of its use in many exemplar problems.

Introduction

Optimization serves as the foundational engine for modern machine learning and signal processing. Among the most widely adopted frameworks is the Fast Iterative Shrinking-Thresholding Algorithm (FISTA). While FISTA is renowned for its acceleration capabilities, its peak performance—specifically linear convergence—is typically contingent on knowing the "conditioning" of the problem. This requires precise knowledge of the smoothness of the function ($L$) and its growth rate ($\\mu$).

In practical applications, these parameters are notoriously difficult to estimate accurately. Practitioners often resort to computationally expensive grid searches or heuristic guessing. This paper introduces Free-FISTA, a variant that eliminates this guesswork by automatically tuning itself during execution, achieving optimal convergence speeds without requiring prior knowledge of the problem's geometric parameters.

The Challenge of Parameter Estimation

To solve composite convex optimization problems (such as Lasso or Logistic Regression), FISTA utilizes an "inertial" term to accelerate convergence. However, if the inertial coefficient is poorly matched to the problem's actual geometry, the algorithm can suffer from significant oscillations.

Existing strategies to mitigate this include restarting (resetting the inertia) and backtracking (adjusting the step size). However, a significant gap remained: most existing methods could adaptively estimate either the smoothness $L$ or the growth $\\mu$, but rarely both simultaneously while maintaining a provable, accelerated convergence rate. Free-FISTA bridges this gap by integrating these two adaptive mechanisms into a unified framework.

The Free-FISTA Framework

The proposed algorithm employs a two-pronged adaptive strategy:

  1. Adaptive Non-Monotone Backtracking (FISTA_adaBT): Traditional backtracking typically only increases the estimated $L$, leading to progressively smaller step sizes. Free-FISTA utilizes a "non-monotone" approach, allowing the estimate of $L$ to decrease if the algorithm detects that the function is locally "flatter." This enables the algorithm to take larger, more aggressive steps when the local geometry permits.
  2. Adaptive Restarting: Rather than restarting at fixed intervals, Free-FISTA computes an online estimate of the conditioning ($\kappa = \mu/L$) by comparing objective function values at different iterations. It employs a "doubling condition" to determine the optimal moment to restart, ensuring that the interval between restarts is tuned to the estimated local geometry.

This combination allows the algorithm to "sense" the curvature of the objective function and adjust its parameters dynamically. The final Free-FISTA algorithm requires only a starting point and a target accuracy ($\epsilon$), making it truly parameter-free.

Experimental Evaluation

The authors evaluated Free-FISTA across several benchmark optimization problems:

  • Logistic Regression: Tests included high-dimensional synthetic data (30,000 features) and the dorothea dataset, a drug discovery benchmark featuring 100,000 features.
  • Image Inpainting: The task involved recovering damaged images using Daubechies wavelets.
  • Poisson Image Super-resolution: The algorithm was applied to enhance low-resolution microscopy images (SMLM ISBI13 dataset) corrupted by Poisson noise.

Key Results and Insights

  • Significant Speedups: On the dorothea dataset, Free-FISTA reached the target accuracy in 989 seconds, whereas vanilla FISTA required 28,594 seconds—representing a nearly 29x speedup.
  • Superior Efficiency: Free-FISTA consistently outperformed specialized variants, such as FISTA with restart (which only adapts $\mu$) and FISTA with backtracking (which only adapts $L$).
  • Theoretical Robustness: Despite the adaptive nature of the algorithm, the authors proved it maintains the "gold standard" accelerated convergence rate of $\mathcal{O}(e^{-K\sqrt{\mu/L}n})$.
  • Parameter Insensitivity: The algorithm demonstrated high robustness to its internal hyperparameters (such as the backtracking factor $\delta$), confirming its utility as a "set and forget" tool for researchers.

Limitations and Conclusion

While Free-FISTA offers substantial improvements, the authors noted specific cases where the benefits are more modest. In the Poisson super-resolution experiments, where the objective function was exceptionally "flat" ($\mu$ near zero), the overhead of the restarting logic meant that simple backtracking was occasionally more efficient.

Free-FISTA represents a significant step forward in making accelerated optimization algorithms more accessible and robust. Future research may extend these adaptive strategies to non-convex optimization or stochastic settings, such as deep neural network training, where manual parameter tuning remains a primary bottleneck.

Summary updated

Abstract

We consider a combined restarting and adaptive backtracking strategy for the popular Fast Iterative Shrinking-Thresholding Algorithm frequently employed for accelerating the convergence speed of large-scale structured convex optimization problems. Several variants of FISTA enjoy a provable linear convergence rate for the function values $F(x_n)$ of the form $\mathcal{O}( e^{-K\sqrt{μ/L}~n})$ under the prior knowledge of problem conditioning, i.e. of the ratio between the (Łojasiewicz) parameter $μ$ determining the growth of the objective function and the Lipschitz constant $L$ of its smooth component. These parameters are nonetheless hard to estimate in many practical cases. Recent works address the problem by estimating either parameter via suitable adaptive strategies. In our work both parameters can be estimated at the same time by means of an algorithmic restarting scheme where, at each restart, a non-monotone estimation of $L$ is performed. For this scheme, theoretical convergence results are proved, showing that a $\mathcal{O}( e^{-K\sqrt{μ/L}n})$ convergence speed can still be achieved along with quantitative estimates of the conditioning. The resulting Free-FISTA algorithm is therefore parameter-free. Several numerical results are reported to confirm the practical interest of its use in many exemplar problems.
BibTeX
@article{aujol2024parameter,
  author = {Jean–François Aujol and Luca Calatroni and Charles Dossal and Hippolyte Labarrière and Aude Rondepierre},
  title = {{Parameter-Free FISTA by Adaptive Restart and Backtracking}},
  journal = {SIAM J. Optim.},
  year = {2024},
  doi = {10.1137/23m158961x},
}
Figure