Search direction correction with normalized gradient makes first-order methods faster

DOI10.1137/20M1335480MaRDI QIDQ3382800zbMATH OpenOpenAlexFDO

Authors Yifei Wang, Zeyu Jia, Zaiwen Wen

Publication date 22 September 2021

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.06507

zbMATH Keywords

composite optimizationfirst-order methodsLyapunov functionsearch direction correctionstochastic optimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Stochastic programming (90C15) Nonlinear programming (90C30)

Abstract: The so-called fast inertial relaxation engine is a first-order method for unconstrained smooth optimization problems. It updates the search direction by a linear combination of the past search direction, the current gradient and the normalized gradient direction. We explore more general combination rules and call this generalized technique as the search direction correction (SDC). SDC is extended to composite and stochastic optimization problems as well. Deriving from a second-order ODE, we propose a fast inertial search direction correction (FISC) algorithm as an example of methods with SDC. We prove the $mathcalO(k^{-2})$ convergence rate of FISC for convex optimization problems. Numerical results on sparse optimization, logistic regression as well as deep learning demonstrate that our proposed methods are quite competitive to other state-of-the-art first-order algorithms.

Recommendations

• Optimized first-order methods for smooth convex minimization
• Adaptive restart of the optimized gradient method for convex optimization
• First-order methods for convex optimization
• Nearly optimal first-order methods for convex optimization under gradient norm measure: an adaptive regularization approach
• The common-directions method for regularized empirical risk minimization

Cites work

• A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
• A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A Nonmonotone Line Search Technique and Its Application to Unconstrained Optimization
• A proximal stochastic gradient method with progressive variance reduction
• A regularized semi-smooth Newton method with projection steps for composite convex programs
• A semismooth Newton method with multidimensional filter globalization for l₁-optimization
• A stochastic semismooth Newton method for nonsmooth nonconvex optimization
• A variational perspective on accelerated methods in optimization
• Adaptive restart for accelerated gradient schemes
• Adaptive subgradient methods for online learning and stochastic optimization
• Analysis and design of optimization algorithms via integral quadratic constraints
• First-order optimization algorithms via inertial systems with Hessian driven damping
• scientific article; zbMATH DE number 4015993 (Why is no real title available?)
• scientific article; zbMATH DE number 3850830 (Why is no real title available?)
• Introductory lectures on convex optimization. A basic course.
• On the limited memory BFGS method for large scale optimization
• Sparse Reconstruction by Separable Approximation
• Two-Point Step Size Gradient Methods

Cited in

(1)

• A unified differential equation solver approach for separable convex optimization: splitting, acceleration and nonergodic rate

Describes a project that uses

Uses Software

• AdaGrad
• Saga
• L-BFGS
• LIBSVM
• FPC_AS
• CIFAR
• Adam

This page was built for publication: Search direction correction with normalized gradient makes first-order methods faster

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3382800)