Convergence Rate of Inertial Forward-Backward Algorithms Based on the Local Error Bound Condition

Hongwei Liu, Ting Wang, Zexian LiuarXiv 2020 · DOI · arXiv

Abstract

The Inertial Forward-Backward algorithm (IFB) is a powerful tool for convex nonsmooth minimization problems. It encompasses the well-known Fast Iterative Shrinkage-Thresholding Algorithm (FISTA), which enjoys an $O(1/k^2)$ global convergence rate of function values; however, convergence of iterates for FISTA has remained unproven. By introducing a small modification, the accelerated IFB variant "FISTA_CD" improves the convergence rate to $o(1/k^2)$ and demonstrates weak convergence of iterates. The local error bound (LEB) condition is extremely useful in analyzing convergence rates for iterative methods, as many practical problems with special structures satisfy it. In this paper, based on the LEB condition, we exploit a new assumption for the parameter $t_k$ in IFB and establish improved convergence rates for function values and strong convergence of iterates in Hilbert space. Notably, under the LEB condition, we establish the strong convergence of iterates for the original FISTA and prove that IFB algorithms with certain $t_k$ can achieve sublinear convergence rates of $o(1/k^p)$ for any positive integer $p > 1$. Numerical experiments illustrate these results.

Introduction

In the field of nonsmooth convex optimization—essential for tasks like LASSO or sparse logistic regression—the Inertial Forward-Backward (IFB) algorithm family is the standard. Its most famous member, FISTA, is widely adopted due to its $O(1/k^2)$ convergence rate for objective function values.

However, FISTA has long faced a theoretical limitation: while function values decrease predictably, proving that the sequence of iterates ($x_k$) actually converges to a specific minimizer is difficult. Furthermore, many real-world problems possess a hidden structure known as a Local Error Bound (LEB). This condition implies that the distance to the solution set is bounded by the algorithm's residual. This research addresses how to leverage the LEB condition to prove stronger convergence results and achieve rates significantly faster than the standard $O(1/k^2)$ benchmark.

Methodology

The authors analyze the IFB algorithm framework through a new theoretical lens. The general structure of the algorithm is defined in Algorithm 1.

Algorithm 1: The Inertial Forward-Backward (IFB) algorithm framework.

Key methodological contributions include:

  1. Generalized Parameter Assumption ($A_2$): A new condition for the inertial parameter $t_k$ (which governs momentum) is proposed, allowing for the study of various momentum update rules beyond the standard Nesterov rule.
  2. The Comparison Method: A mathematical technique is introduced to bound objective function values and iterate variations using a sequence $s_k$, translating the growth of the momentum parameter directly into a convergence rate.
  3. Adaptive Modification (IFB_AdapM): The paper proposes a version of the algorithm that "resets" momentum if the objective function increases, providing a theoretically grounded alternative to heuristic restarting strategies used in practice.

Key Results and Insights

The study reveals several critical insights that advance the state of inertial splitting methods:

  • Strong Convergence is Guaranteed: Under the LEB condition, the authors provide the first proof that the iterates of the original FISTA converge strongly to a minimizer, filling a significant gap in optimization theory.
  • Breaking the $1/k^2$ Barrier: By selecting specific momentum parameters (Case 1 and Case 3 in the paper), the algorithm can achieve a sublinear rate of $o(1/k^p)$ for any positive integer $p$.
  • Numerical Efficiency: Experiments on the "sonar" dataset from LIBSVM showed that while standard FISTA required 8,405 iterations to reach a target precision, the new "FISTA_pow(0.5)" variant required only 922—a nearly 9x speedup.
  • Robustness of Adaptation: The adaptive version (IFB_AdapM) proved highly effective across different problem types, often exhibiting R-linear (exponentially fast) convergence in practice, making it competitive with state-of-the-art methods.

Conclusion

This work demonstrates that the Local Error Bound condition is a powerful catalyst for accelerating Inertial Forward-Backward algorithms. By moving beyond the standard $O(1/k^2)$ analysis, the authors provide both stronger theoretical guarantees—specifically strong convergence of iterates—and practical variants that significantly outperform traditional FISTA in real-world applications. Future work may involve extending these results to non-convex settings or more general Banach spaces.

Summary updated

Abstract

The "Inertial Forward-Backward algorithm" (IFB) is a powerful tool for convex nonsmooth minimization problems, it gives the well known "fast iterative shrinkage-thresholding algorithm " (FISTA), which enjoys $O\left( {\frac{1}{k^2}} \right)$ global convergence rate of function values, however, no convergence of iterates has been proved; by do a small modification, an accelerated IFB called "FISTA\_CD" improves the convergence rate of function values to $o\left( {\frac{1}{k^2}} \right)$ and shows the weak convergence of iterates. The local error bound condition is extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems, and in practical application, a large number of problems with special structure often satisfy the error bound condition. Naturally, using local error bound condition to derive or improve the convergence rate of IFB is a common means. In this paper, based on the local error bound condition, we exploit an new assumption condition for the important parameter $t_k$ in IFB, and establish the improved convergence rate of function values and strong convergence of the iterates generated by the IFB algorithms with six $t_k$ satisfying the above assumption condition in Hilbert space. It is remarkable that, under the local error bound condition, we establish the strong convergence of the iterates generated by the original FISTA, and prove that the convergence rates of function values for FISTA\_CD is actually related to the value of parameter $a,$ and show that the IFB algorithms with some $t_k$ mentioned above can achieve sublinear convergence rate $o\left( {\frac{1}{k^p}} \right)$ for any positive integer $p>1$. Some numerical experiments are conducted to illustrate our results.
BibTeX
@misc{liu2020convergence,
  author = {Hongwei Liu and Ting Wang and Zexian Liu},
  title = {{Convergence Rate of Inertial Forward-Backward Algorithms Based on the Local Error Bound Condition}},
  year = {2020},
  eprint = {2007.07432},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2007.07432},
}

Loading related content...

Figure