Accelerating Nesterov's Method for Strongly Convex Functions with Lipschitz Gradient

2011/09/27 by Xiangrui Meng, Hao Chen, Meng, Xiangrui +1
Engineering · Mathematics · #90C25 #FOS: Mathematics #Numerical methods in inverse problems #Optimization and Control (math.OC) #Photoacoustic and Ultrasonic Imaging #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1109.6058

openalex publication_date 2011/09/27 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

We modify Nesterov's constant step gradient method for strongly convex functions with Lipschitz continuous gradient described in Nesterov's book. Nesterov shows that f(x_k) - f^* ≤ L ∏_i=1^k (1 - α_k) ‖ x₀ - x^* ‖₂² with α_k = √ρ for all k, where L is the Lipschitz gradient constant and ρ is the reciprocal condition number of f(x). Hence the convergence rate is 1-√ρ. In this work, we try to accelerate Nesterov's method by adaptively searching for an α_k > √ρ at each iteration. The proposed method evaluates the gradient function at most twice per iteration and has some extra Level 1 BLAS operations. Theoretically, in the worst case, it takes the same number of iterations as Nesterov's method does but doubles the gradient calls. However, in practice, the proposed method effectively accelerates the speed of convergence for many problems including a smoothed basis pursuit denoising problem.

Citations

• Atomic Decomposition by Basis Pursuit
• LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares

Related

• An Adaptive and Parameter-Free Nesterov's Accelerated Gradient Method for Convex Optimization
• Nesterov Finds GRAAL: Optimal and Adaptive Gradient Method for Convex Optimization
• A unified convergence bound for conjugate gradient and accelerated gradient
• The Global R-linear Convergence of Nesterov's Accelerated Gradient Method with Unknown Strongly Convex Parameter
• Optimal convergence rates for Nesterov acceleration