Convergence Analysis of Proximal Gradient with Momentum for Nonconvex Optimization

Abstract

In many modern machine learning applications, structures of underlying mathematical models often yield nonconvex optimization problems. Due to the intractability of nonconvexity, there is a rising need to develop efficient methods for solving general nonconvex problems with certain performance guarantee. In this work, we investigate the accelerated proximal gradient method for nonconvex programming (APGnc). The method compares between a usual proximal gradient step and a linear extrapolation step, and accepts the one that has a lower function value to achieve a monotonic decrease. In specific, under a general nonsmooth and nonconvex setting, we provide a rigorous argument to show that the limit points of the sequence generated by APGnc are critical points of the objective function. Then, by exploiting the Kurdyka-Łojasiewicz (\KL) property for a broad class of functions, we establish the linear and sub-linear convergence rates of the function value sequence generated by APGnc. We further propose a stochastic variance reduced APGnc (SVRG-APGnc), and establish its linear convergence under a special case of the \KL property. We also extend the analysis to the inexact version of these methods and develop an adaptive momentum strategy that improves the numerical performance.

arXiv commentAccepted in ICML 2017, 9 papes, 4 figures

Cited by in corpus (23)

• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• Nonconvex Sparse Logistic Regression with Weakly Convex Regularization
• SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms
• Investigating Task-driven Latent Feasibility for Nonconvex Image Modeling
• Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization
• Bayesian Learning of Parameterised Quantum Circuits
• Cubic Regularization with Momentum for Nonconvex Optimization
• Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimization
• A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems
• An Average Curvature Accelerated Composite Gradient Method for Nonconvex Smooth Composite Optimization Problems
• Covariance Steering for Nonlinear Control-affine Systems
• On the Convergence of Learning-based Iterative Methods for Nonconvex Inverse Problems
• FasTer: Fast Tensor Completion with Nonconvex Regularization
• DEAM: Adaptive Momentum with Discriminative Weight for Stochastic Optimization
• Structured Sparse Non-negative Matrix Factorization with L20-Norm for scRNA-seq Data Analysis
• Faster Stochastic Quasi-Newton Methods
• Accelerated Block Coordinate Proximal Gradients with Applications in High Dimensional Statistics
• A FISTA-Type First Order Algorithm on Composite Optimization Problems that is Adaptable to the Convex Situation
• TAG: Task-based Accumulated Gradients for Lifelong learning
• Comparison-Based Algorithms for One-Dimensional Stochastic Convex Optimization
• Learning Collaborative Generation Correction Modules for Blind Image Deblurring and Beyond
• Average Curvature FISTA for Nonconvex Smooth Composite Optimization Problems
• Proximal Gradient Algorithm with Momentum and Flexible Parameter Restart for Nonconvex Optimization