2024/12/18 by M.W. Fu, Bin Shi, Fu, Mingwei +1 · 1 citation
Engineering · #Advanced Control Systems Optimization #Control Systems and Identification #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Stability and Control of Uncertain Systems
paper · pdf · doi:10.48550/arxiv.2412.13527
openalex publication_date 2024/12/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Nesterov's accelerated gradient method (NAG) achieves faster convergence than gradient descent for convex optimization but lacks monotonicity in function values. To address this, Beck and Teboulle [2009b] proposed a monotonic variant, M-NAG, and extended it to the proximal setting as M-FISTA for composite problems such as Lasso. However, establishing the linear convergence of M-NAG and M-FISTA under strong convexity remains an open problem. In this paper, we analyze M-NAG via the implicit-velocity phase representation and show that an additional assumption, either the position update or the phase-coupling relation, is necessary to fully recover the NAG iterates. The essence of M-NAG lies in controlling an auxiliary sequence to enforce non-increase. We further demonstrate that the M-NAG update alone is sufficient to construct a Lyapunov function guaranteeing linear convergence, without relying on full NAG iterates. By modifying the mixed sequence to incorporate forward-indexed gradients, we develop a new Lyapunov function that removes the kinetic energy term, enabling a direct extension to M-NAG. The required starting index depends only on the momentum parameter and not on problem constants. Finally, leveraging newly developed proximal inequalities, we extend our results to M-FISTA, establishing its linear convergence and deepening the theoretical understanding of monotonic accelerated methods.