Robustifying stability of the Fast iterative shrinkage thresholding algorithm for ℓ₁ regularized problems

The fast iterative shrinkage-thresholding algorithm (FISTA) is a well-known first order method used to minimize '1 regularized problems. However, it is also a non-monotone algorithm that can exhibit a sudden and gradual oscillatory behavior during the convergence. One of the parameters that directly affects the convergence of the FISTA method, whose optimal value is typically unknown, is the step-size (SS) that is linked to the Lipschitz constant. Depending on a suitable selection of the SS either manual or automatic, and the SS evolution throughout iterations, e.g. constant, decreasing, or increasing sequence, the practical performance can differ in orders of magnitude with or without stability issues (oscillations or, in the worst case, divergence). In this paper, we propose an algorithm, which has two variants, to address the stability issues in case of ill-chosen parameters for a given SS policy (either manual or adaptive). The proposed method structurally consists of an instability prediction rule based on the ∞ norm of the gradient, and a correction for it, which can interpreted as an under-relaxation technique.