Convergence Rate Analysis of Accelerated Forward-Backward Algorithm with Generalized Nesterov Momentum Scheme

Yizun Lin, Si Li, Yunzhong Zhang

Abstract

Nesterov's accelerated forward-backward algorithm (AFBA) is an efficient algorithm for solving a class of two-term convex optimization models consisting of a differentiable function with a Lipschitz continuous gradient plus a nondifferentiable function with a closed form of its proximity operator. It has been shown that the iterative sequence generated by AFBA with a modified Nesterov's momentum scheme converges to a minimizer of the objective function with an $o(1/k^2)$ convergence rate in terms of the function value (FV-convergence rate) and an $o(1/k)$ convergence rate in terms of the distance between consecutive iterates (DCI-convergence rate). In this paper, we propose a more general momentum scheme with an introduced power parameter $\omega \in (0,1]$ and show that AFBA with the proposed momentum scheme converges to a minimizer of the objective function with an $o(1/k^{2\omega})$ FV-convergence rate and an $o(1/k^\omega)$ DCI-convergence rate. The generality of the proposed momentum scheme provides us a variety of parameter selections for different scenarios, which makes the resulting algorithm more flexible to achieve better performance. We then employ AFBA with the proposed momentum scheme to solve the smoothed hinge loss $\ell_1$-support vector machine model. Numerical results demonstrate that the proposed generalized momentum scheme outperforms two existing momentum schemes.

Introduction

In convex optimization, many problems are formulated as the minimization of a two-term objective function: $F(x) = f(x) + g(x)$, where $f$ is a smooth function with a Lipschitz continuous gradient and $g$ is a non-smooth, convex function (often a penalty term like the $\ell_1$-norm). The Forward-Backward Algorithm (FBA) is a standard approach for these problems, but its convergence can be slow for high-dimensional data.

To accelerate convergence, Nesterov’s momentum techniques are frequently employed, most notably in algorithms like FISTA. While standard schemes offer a theoretical convergence rate of $O(1/k^2)$, they lack flexibility for specific practical applications. This research introduces a Generalized Nesterov (GN) momentum scheme that incorporates a tunable power parameter, $\omega$, allowing for a more adaptable acceleration profile.

Methodology: The Generalized Nesterov Scheme

The core innovation lies in the definition of the momentum sequence $t_k$. In the proposed AFBA-GN, the sequence is defined as:

$$t_{k-1} = a(k-1)^\omega + b$$

where $\omega \in (0, 1]$ is the power parameter, and $a$ and $b$ are constants. This generalization allows the algorithm to recover existing methods (such as the Chambolle-Dossal scheme when $\omega = 1$) while also exploring new acceleration trajectories when $\omega < 1$.

Theoretical Convergence

The authors establish two primary convergence guarantees for this generalized scheme:

  1. Function Value (FV) Convergence: The objective function value converges at a rate of $o(1/k^{2\omega})$.
  2. Distance Between Consecutive Iterates (DCI) Convergence: The distance between successive guesses converges at a rate of $o(1/k^\omega)$.

This DCI-convergence is particularly important for numerical stability, ensuring that the sequence of iterates $x_k$ eventually stabilizes at a minimizer.

Experimental Evaluation

The AFBA-GN algorithm was tested on a smoothed hinge loss $\ell_1$-support vector machine (SVM) model. This model combines a differentiable version of the hinge loss with an $\ell_1$ penalty to promote feature sparsity. Testing was conducted on two datasets from the LIBSVM library:

  • MNIST01: A subset of handwritten digits (0 and 1) with 12,665 samples and 400 features.
  • Splice: A genetic sequence classification dataset with 1,000 samples and 60 features.

Results and Discussion

Numerical experiments indicate that the GN scheme provides significant practical advantages over standard FISTA and the Chambolle-Dossal (CD) scheme.

  • Efficiency Gains: On the MNIST01 dataset, AFBA-GN achieved 99.9% test accuracy in 620 iterations. In contrast, FISTA required 1,259 iterations and AFBA-CD required 1,265 iterations. This represents an approximate 2x speedup in reaching high-precision solutions.
  • Initial Acceleration: The GN scheme demonstrated a steeper initial learning curve, which is beneficial for large-scale applications where computational budgets may limit the total number of iterations.
  • Parameter Flexibility: While a larger $\omega$ provides a faster asymptotic theoretical rate, the study found that specific combinations of $a, b,$ and $\omega$ can be tuned to optimize practical performance for specific datasets.

Conclusion

The introduction of the power parameter $\omega$ transforms the Nesterov momentum scheme from a rigid formula into a flexible tool for optimization. By allowing for a variety of parameter selections, the AFBA-GN algorithm can be tailored to achieve superior performance in machine learning tasks like SVM training. Future work may explore automated methods for selecting these parameters to reduce the need for manual tuning.

Summary updated

Abstract

Nesterov's accelerated forward-backward algorithm (AFBA) is an efficient algorithm for solving a class of two-term convex optimization models consisting of a differentiable function with a Lipschitz continuous gradient plus a nondifferentiable function with a closed form of its proximity operator. It has been shown that the iterative sequence generated by AFBA with a modified Nesterov's momentum scheme converges to a minimizer of the objective function with an $o\left(\frac{1}{k^2}\right)$ convergence rate in terms of the function value (FV-convergence rate) and an $o\left(\frac{1}{k}\right)$ convergence rate in terms of the distance between consecutive iterates (DCI-convergence rate). In this paper, we propose a more general momentum scheme with an introduced power parameter $ω\in(0,1]$ and show that AFBA with the proposed momentum scheme converges to a minimizer of the objective function with an $o\left(\frac{1}{k^{2ω}}\right)$ FV-convergence rate and an $o\left(\frac{1}{k^ω}\right)$ DCI-convergence rate. The generality of the proposed momentum scheme provides us a variety of parameter selections for different scenarios, which makes the resulting algorithm more flexible to achieve better performance. We then employ AFBA with the proposed momentum scheme to solve the smoothed hinge loss $\ell_1$-support vector machine model. Numerical results demonstrate that the proposed generalized momentum scheme outperforms two existing momentum schemes.
BibTeX
@article{lin2023convergence,
  author = {Yizun Lin and Si Li and Yunzhong Zhang},
  title = {{Convergence Rate Analysis of Accelerated Forward-Backward Algorithm with Generalized Nesterov Momentum Scheme}},
  journal = {International Journal of Numerical Analysis and Modeling},
  year = {2023},
  doi = {10.4208/ijnam2023-1022},
}
Figure