arrow
Volume 20, Issue 4
Convergence Rate Analysis of Accelerated Forward-Backward Algorithm with Generalized Nesterov Momentum Scheme

Yizun Lin, Si Li & Yunzhong Zhang

Int. J. Numer. Anal. Mod., 20 (2023), pp. 518-537.

Published online: 2023-05

Export citation
  • 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 (\frac{1}{k^2})$ convergence rate in terms of the function value (FV-convergence rate) and an $o(\frac{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 $ω ∈ (0, 1]$ and show that AFBA with the proposed momentum scheme converges to a minimizer of the objective function with an $o ( \frac{1}{ k^{2ω}} )$ FV-convergence rate and an $o (\frac{1}{k^ω})$ 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 $ℓ_1$-support vector machine model. Numerical results demonstrate that the proposed generalized momentum scheme outperforms two existing momentum schemes.

  • AMS Subject Headings

49M37, 65K05, 90C25

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{IJNAM-20-518, author = {Lin , YizunLi , Si and Zhang , Yunzhong}, title = {Convergence Rate Analysis of Accelerated Forward-Backward Algorithm with Generalized Nesterov Momentum Scheme}, journal = {International Journal of Numerical Analysis and Modeling}, year = {2023}, volume = {20}, number = {4}, pages = {518--537}, 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 (\frac{1}{k^2})$ convergence rate in terms of the function value (FV-convergence rate) and an $o(\frac{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 $ω ∈ (0, 1]$ and show that AFBA with the proposed momentum scheme converges to a minimizer of the objective function with an $o ( \frac{1}{ k^{2ω}} )$ FV-convergence rate and an $o (\frac{1}{k^ω})$ 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 $ℓ_1$-support vector machine model. Numerical results demonstrate that the proposed generalized momentum scheme outperforms two existing momentum schemes.

}, issn = {2617-8710}, doi = {https://doi.org/10.4208/ijnam2023-1022}, url = {http://global-sci.org/intro/article_detail/ijnam/21714.html} }
TY - JOUR T1 - Convergence Rate Analysis of Accelerated Forward-Backward Algorithm with Generalized Nesterov Momentum Scheme AU - Lin , Yizun AU - Li , Si AU - Zhang , Yunzhong JO - International Journal of Numerical Analysis and Modeling VL - 4 SP - 518 EP - 537 PY - 2023 DA - 2023/05 SN - 20 DO - http://doi.org/10.4208/ijnam2023-1022 UR - https://global-sci.org/intro/article_detail/ijnam/21714.html KW - Nesterov’s momentum, forward-backward algorithm, convergence rate, support vector machine. AB -

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 (\frac{1}{k^2})$ convergence rate in terms of the function value (FV-convergence rate) and an $o(\frac{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 $ω ∈ (0, 1]$ and show that AFBA with the proposed momentum scheme converges to a minimizer of the objective function with an $o ( \frac{1}{ k^{2ω}} )$ FV-convergence rate and an $o (\frac{1}{k^ω})$ 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 $ℓ_1$-support vector machine model. Numerical results demonstrate that the proposed generalized momentum scheme outperforms two existing momentum schemes.

Yizun Lin, Si Li & Yunzhong Zhang. (2023). Convergence Rate Analysis of Accelerated Forward-Backward Algorithm with Generalized Nesterov Momentum Scheme. International Journal of Numerical Analysis and Modeling. 20 (4). 518-537. doi:10.4208/ijnam2023-1022
Copy to clipboard
The citation has been copied to your clipboard