Abstract
In this paper, we consider a class of Forward--Backward (FB) splitting methods that includes several variants (e.g. inertial schemes, FISTA) for minimizing the sum of two proper convex and lower semi-continuous functions, one of which has a Lipschitz continuous gradient, and the other is partly smooth relatively to a smooth active manifold $\mathcal{M}$. We propose a unified framework, under which we show that, this class of FB-type algorithms (i) correctly identifies the active manifolds in a finite number of iterations (finite activity identification), and (ii) then enters a local linear convergence regime, which we characterize precisely in terms of the structure of the underlying active manifolds. For simpler problems involving polyhedral functions, we show finite termination. We also establish and explain why FISTA (with convergent sequences) locally oscillates and can be slower than FB. These results may have numerous applications including in signal/image processing, sparse recovery and machine learning.
Introduction
In modern machine learning and signal processing, optimization problems frequently involve a composite objective: a smooth "data-fitting" term paired with a non-smooth "regularizer" (such as the $L_1$ norm for promoting sparsity). Forward-Backward (FB) splitting methods are the standard tools for solving these problems. While the global convergence rates of these methods—such as FISTA’s $O(1/k^2)$ rate—are well-established, their local behavior has remained less understood.
Practitioners often observe that these algorithms quickly identify the correct support of a signal (the "active manifold") but then exhibit complex oscillations or a slowdown in convergence as they approach the optimum. This research provides a unified theoretical framework to bridge the gap between these empirical observations and mathematical theory, characterizing exactly how these algorithms behave once they enter the neighborhood of a solution.
Methodology: A Unified Framework
The authors introduce a General Inertial Forward–Backward (iFB) splitting framework, detailed in Algorithm 1. This framework is sufficiently general to encompass several popular optimization schemes as special cases, including standard FB (no momentum), Heavy-ball style inertial FB (iFB), and the Fast Iterative Soft-Thresholding Algorithm (FISTA).
The analysis hinges on the concept of Partial Smoothness. A function is considered partly smooth if it is non-smooth globally but behaves smoothly when restricted to a specific "active manifold" $\mathcal{M}$ (for example, the subspace where the non-zero coefficients of a sparse vector reside). By linearizing the algorithm's iteration around the optimal solution on this manifold, the authors employ spectral analysis of an iteration matrix $M$ to predict convergence rates and oscillatory patterns.
Key Insights and the FISTA Paradox
Finite Activity Identification
Under a standard "non-degeneracy" condition—where the solution does not lie exactly on a "corner" of the non-smooth term—the algorithm is guaranteed to identify the correct active manifold (e.g., the exact sparsity pattern) in a finite number of iterations. This explains why practitioners see the "support" of a signal stabilize long before the numerical values fully converge.
The FISTA Paradox and Local Oscillations
A major contribution of this work is the explanation of the "FISTA Paradox." While FISTA is globally faster than standard FB, the authors prove it is often locally slower. Once the active manifold is identified, the momentum parameters that provide global acceleration cause the algorithm to overshoot and oscillate.
As shown in the parameter region plots, the choice of inertial parameters $a$ and $b$ directly influences the eigenvalues of the local iteration matrix. In certain regions, these eigenvalues become complex, which mathematically translates to the "ripples" or oscillations observed in convergence plots. This theory provides a rigorous justification for the "restarting" heuristic, where momentum is periodically reset to dampen these local oscillations and restore faster convergence.
Key Results and Empirical Validation
- Theoretical Convergence Rates: The paper provides an exact formula for the local linear convergence rate $\rho(M)$ based on step size and momentum parameters.
- Tightness of Theory: Numerical experiments on standard problems like the Lasso, Total Variation (TV) deconvolution, and Nuclear Norm minimization show that the theoretical slopes predicted by the authors' spectral analysis align perfectly with observed practical performance.
- Finite Termination: For specific polyhedral problems (e.g., quadratic objectives with $L_1$ penalties), the authors demonstrate that the algorithm can reach the exact solution in finite time when paired with a specific projection step.
Limitations and Future Directions
While the framework is powerful, it relies on a non-degeneracy condition (ND) and a restricted injectivity condition (RI). These are standard in optimization theory but can be challenging to verify for high-dimensional, complex real-world datasets. Additionally, the current analysis is focused on convex problems. Extending these results to non-convex "partly smooth" optimization—potentially using tools like the Kurdyka-Łojasiewicz inequality—remains a promising avenue for future research. Finally, the authors note that while the algorithm is robust to gradient errors, inaccuracies in the proximal step can impede the finite identification of the active manifold.
Summary updated