EUVIMEDEUVIMED entdecken
Crossref

Linear Convergence of Forward-Backward Accelerated Algorithms without Knowledge of the Modulus of Strong Convexity

Bowen Li, Bin Shi, Ya-xiang Yuan

SIAM Journal on Optimization · 30.06.2024 · 34 (2) · 2150-2168

DOI: 10.1137/23m158111x ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Optimization, online erschienen am 19.06.2024. Verfasst von Bowen Li und 2 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 24 Literaturangaben. Gefördert von: Chinese Academy of Sciences, National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A significant milestone in modern gradient-based optimization was achieved with the development of Nesterov’s accelerated gradient descent (NAG) method. This forward-backward technique has been further advanced with the introduction of its proximal generalization, commonly known as the fast iterative shrinkage-thresholding algorithm (FISTA), which enjoys widespread application in image science and engineering. Nonetheless, it remains unclear whether both NAG and FISTA exhibit linear convergence for strongly convex functions. Remarkably, these algorithms demonstrate convergence without requiring any prior knowledge of strongly convex modulus, and this intriguing characteristic has been acknowledged as an open problem in the comprehensive review [A. Chambolle and T. Pock, Acta Numer., 25 (2016), pp. 161–319]. In this paper, we address this question by utilizing the high-resolution ordinary differential equation (ODE) framework. Expanding upon the established phase-space representation, we emphasize the distinctive approach employed in crafting the Lyapunov function, which involves a dynamically adapting coefficient of kinetic energy that evolves throughout the iterations. Furthermore, we highlight that the linear convergence of both NAG and FISTA is independent of the parameter [Formula: see text]. Additionally, we demonstrate that the square of the proximal subgradient norm likewise advances toward linear convergence.

Förderung

  • Chinese Academy of Sciences
  • National Natural Science Foundation of China

Zitieren

APA

Li, B., Shi, B., & Yuan, Y. (2024). Linear Convergence of Forward-Backward Accelerated Algorithms without Knowledge of the Modulus of Strong Convexity. SIAM Journal on Optimization, 34(2), 2150-2168. https://doi.org/10.1137/23m158111x

Vancouver

Li B, Shi B, Yuan Y. Linear Convergence of Forward-Backward Accelerated Algorithms without Knowledge of the Modulus of Strong Convexity. SIAM Journal on Optimization. 2024;34(2):2150-2168. doi:10.1137/23m158111x

BibTeX
@article{Li2024,
  author = {Li, Bowen and Shi, Bin and Yuan, Ya-xiang},
  title = {Linear Convergence of Forward-Backward Accelerated Algorithms without Knowledge of the Modulus of Strong Convexity},
  journal = {SIAM Journal on Optimization},
  year = {2024},
  volume = {34},
  number = {2},
  pages = {2150--2168},
  doi = {10.1137/23m158111x}
}
Kostenlos starten →