Linear Convergence of Forward-Backward Accelerated Algorithms without Knowledge of the Modulus of Strong Convexity
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.
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}
}
EUVIMED