Adaptive Restart of the Optimized Gradient Method for Convex Optimization

2017/03/31 by Donghwan Kim, Jeffrey A. Fessler · 35 citations
Computer Science · Engineering · Mathematics · #Convergence (economics) #Convex function #Convex optimization #Frank–Wolfe algorithm #Function (biology) #Gradient method #Heuristic #Iterated function #Optimization and Variational Analysis #Proximal Gradient Methods #Rate of convergence #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #math.OC

paper · pdf · doi:10.1007/s10957-018-1287-4

published in Journal of Optimization Theory and Applications 178(1), 240-263 (Springer Science+Business Media)

openalex created_date 2017/04/07 · arxiv created 2017/11/28 · openalex publication_date 2018/05/07 · arxiv updated 2019/06/14 · openalex updated_date 2026/08/06

Abstract

First-order methods with momentum such as Nesterov's fast gradient method are very useful for convex optimization problems, but can exhibit undesirable oscillations yielding slow convergence rates for some applications. An adaptive restarting scheme can improve the convergence rate of the fast gradient method, when the parameter of a strongly convex cost function is unknown or when the iterates of the algorithm enter a locally strongly convex region. Recently, we introduced the optimized gradient method, a first-order algorithm that has an inexpensive per-iteration computational cost similar to that of the fast gradient method, yet has a worst-case cost function rate that is twice faster than that of the fast gradient method and that is optimal for large-dimensional smooth convex problems. Building upon the success of accelerating the fast gradient method using adaptive restart, this paper investigates similar heuristic acceleration of the optimized gradient method. We first derive a new first-order method that resembles the optimized gradient method for strongly convex quadratic problems with known function parameters, yielding a linear convergence rate that is faster than that of the analogous version of the fast gradient method. We then provide a heuristic analysis and numerical experiments that illustrate that adaptive restart can accelerate the convergence of the optimized gradient method. Numerical results also illustrate that adaptive restart is helpful for a proximal version of the optimized gradient method for nonsmooth composite convex functions.

Cited by

• HNAG++: A Super-Fast Accelerated Gradient Method for Strongly Convex Optimization
• Smooth optimization using global and local low-rank regularizers
• Optimization Methods for Magnetic Resonance Image Reconstruction: Key Models and Optimization Algorithms. [europepmc]
• Poisson Phase Retrieval in Very Low-count Regimes. [europepmc]
• Efficient Approximation of Jacobian Matrices Involving a Non-Uniform Fast Fourier Transform (NUFFT). [europepmc]
• Manifold Regularizer for High-Resolution fMRI Joint Reconstruction and Dynamic Quantification. [europepmc]
• Convergence for nonconvex ADMM, with applications to CT imaging. [europepmc]
• SNAKE: A modular realistic fMRI data simulator from the space-time domain to k-space and back. [europepmc]
• Smooth optimization using global and local low-rank regularizers. [europepmc]

Related

• Accelerated Gradient Methods with Gradient Restart: Global Linear Convergence
• Efficient parameter-free restarted accelerated gradient methods for convex and strongly convex optimization
• Polyak Steps for Adaptive Fast Gradient Method
• An accelerated gradient method with adaptive restart for convex multiobjective optimization problems
• A Simple Nearly-Optimal Restart Scheme For Speeding-Up First Order Methods