Accelerated gradient methods for nonconvex nonlinear and stochastic programming

DOI10.1007/s10107-015-0871-8zbMath1335.62121arXiv1310.3787OpenAlexW1987083649MaRDI QIDQ263185

Saeed Ghadimi, Guanghui Lan

Publication date: 4 April 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

complexitystochastic programmingnonconvex optimizationaccelerated gradient

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Stochastic programming (90C15) Stochastic approximation (62L20)

Related Items (only showing first 100 items - show all)

A penalty method for rank minimization problems in symmetric matrices ⋮ Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization ⋮ Asynchronous variance-reduced block schemes for composite non-convex stochastic optimization: block-specific steplengths and adapted batch-sizes ⋮ An overview on recent machine learning techniques for port Hamiltonian systems ⋮ Weakly-convex–concave min–max optimization: provable algorithms and applications in machine learning ⋮ Accelerated projected gradient method with adaptive step size for compliance minimization problem ⋮ A smoothing SQP framework for a class of composite \(L_q\) minimization over polyhedron ⋮ Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Nonconvex Stochastic Optimization: Nonasymptotic Performance Bounds and Momentum-Based Acceleration ⋮ On the global convergence rate of the gradient descent method for functions with Hölder continuous gradients ⋮ A stochastic extra-step quasi-Newton method for nonsmooth nonconvex optimization ⋮ Riemannian proximal gradient methods ⋮ Accelerated inexact composite gradient methods for nonconvex spectral optimization problems ⋮ Stochastic optimization using a trust-region method and random models ⋮ Accelerated Optimization in the PDE Framework: Formulations for the Manifold of Diffeomorphisms ⋮ Stochastic Multilevel Composition Optimization Algorithms with Level-Independent Convergence Rates ⋮ Distributed Variable Sample-Size Gradient-Response and Best-Response Schemes for Stochastic Nash Equilibrium Problems ⋮ A Projected Gradient and Constraint Linearization Method for Nonlinear Model Predictive Control ⋮ A Variable Sample-Size Stochastic Quasi-Newton Method for Smooth and Nonsmooth Stochastic Convex Optimization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Accelerated Methods for NonConvex Optimization ⋮ Generalizing the Optimized Gradient Method for Smooth Convex Minimization ⋮ On the information-adaptive variants of the ADMM: an iteration complexity perspective ⋮ A Diffusion Approximation Theory of Momentum Stochastic Gradient Descent in Nonconvex Optimization ⋮ Primal–dual accelerated gradient methods with small-dimensional relaxation oracle ⋮ A multi-step doubly stabilized bundle method for nonsmooth convex optimization ⋮ A globally convergent algorithm for nonconvex optimization based on block coordinate update ⋮ Block Stochastic Gradient Iteration for Convex and Nonconvex Optimization ⋮ An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems ⋮ Algorithms for stochastic optimization with function or expectation constraints ⋮ On computing the distance to stability for matrices using linear dissipative Hamiltonian systems ⋮ Scheduled Restart Momentum for Accelerated Stochastic Gradient Descent ⋮ Accelerated schemes for a class of variational inequalities ⋮ Approximating the nearest stable discrete-time system ⋮ Iteratively reweighted \(\ell _1\) algorithms with extrapolation ⋮ Momentum-based variance-reduced proximal stochastic gradient method for composite nonconvex stochastic optimization ⋮ Unnamed Item ⋮ Run-and-inspect method for nonconvex optimization and global optimality bounds for R-local minimizers ⋮ Behavior of accelerated gradient methods near critical points of nonconvex functions ⋮ Misspecified nonconvex statistical optimization for sparse phase retrieval ⋮ Stochastic heavy ball ⋮ Open Problem—Iterative Schemes for Stochastic Optimization: Convergence Statements and Limit Theorems ⋮ Stochastic first-order methods for convex and nonconvex functional constrained optimization ⋮ Another Look at the Fast Iterative Shrinkage/Thresholding Algorithm (FISTA) ⋮ Mean curvature flow for generating discrete surfaces with piecewise constant mean curvatures ⋮ Penalty methods with stochastic approximation for stochastic nonlinear programming ⋮ Distributed stochastic gradient tracking methods with momentum acceleration for non-convex optimization ⋮ A smoothing proximal gradient algorithm with extrapolation for the relaxation of \({\ell_0}\) regularization problem ⋮ Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis ⋮ Accelerated stochastic variance reduction for a class of convex optimization problems ⋮ A nonmonotone approximate sequence algorithm for unconstrained nonlinear optimization ⋮ An inexact Riemannian proximal gradient method ⋮ Optimization-Based Calibration of Simulation Input Models ⋮ Conditional gradient type methods for composite nonlinear and stochastic optimization ⋮ A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization ⋮ Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria ⋮ Portfolio selection with the effect of systematic risk diversification: formulation and accelerated gradient algorithm ⋮ Accelerated Optimization in the PDE Framework Formulations for the Active Contour Case ⋮ Asynchronous Schemes for Stochastic and Misspecified Potential Games and Nonconvex Optimization ⋮ An Average Curvature Accelerated Composite Gradient Method for Nonconvex Smooth Composite Optimization Problems ⋮ Stochastic Conditional Gradient++: (Non)Convex Minimization and Continuous Submodular Maximization ⋮ Finding the Nearest Positive-Real System ⋮ On variance reduction for stochastic smooth convex optimization with multiplicative noise ⋮ Variational Representations and Neural Network Estimation of Rényi Divergences ⋮ An Accelerated Inexact Proximal Point Method for Solving Nonconvex-Concave Min-Max Problems ⋮ Complexity of proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints ⋮ Efficient Learning with a Family of Nonconvex Regularizers by Redistributing Nonconvexity ⋮ Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization ⋮ Dynamic stochastic approximation for multi-stage stochastic optimization ⋮ Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems ⋮ Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods ⋮ Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions ⋮ Second-order optimality and beyond: characterization and evaluation complexity in convexly constrained nonlinear optimization ⋮ An optimal randomized incremental gradient method ⋮ Random Gradient Extrapolation for Distributed and Stochastic Optimization ⋮ Unnamed Item ⋮ Variable smoothing for weakly convex composite functions ⋮ A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems ⋮ Robust and sparse regression in generalized linear model by stochastic optimization ⋮ Provable accelerated gradient method for nonconvex low rank optimization ⋮ A Single Timescale Stochastic Approximation Method for Nested Stochastic Optimization ⋮ Accelerated First-Order Primal-Dual Proximal Methods for Linearly Constrained Composite Convex Programming ⋮ Generalized uniformly optimal methods for nonlinear programming ⋮ Hessian Barrier Algorithms for Linearly Constrained Optimization Problems ⋮ Adaptive FISTA for Nonconvex Optimization ⋮ Analysis of generalized Bregman surrogate algorithms for nonsmooth nonconvex statistical learning ⋮ Complexity of a Quadratic Penalty Accelerated Inexact Proximal Point Method for Solving Linearly Constrained Nonconvex Composite Programs ⋮ Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization ⋮ On the local convergence of a stochastic semismooth Newton method for nonsmooth nonconvex optimization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Efficiency of minimizing compositions of convex functions and smooth maps ⋮ Understanding the acceleration phenomenon via high-resolution differential equations ⋮ Unnamed Item ⋮ An adaptive Polyak heavy-ball method ⋮ Stochastic Gauss-Newton algorithm with STORM estimators for nonconvex composite optimization ⋮ Extrapolated smoothing descent algorithm for constrained nonconvex and nonsmooth composite problems ⋮ On stochastic accelerated gradient with convergence rate ⋮ Accelerating variance-reduced stochastic gradient methods ⋮ A hybrid stochastic optimization framework for composite nonconvex optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Smooth minimization of non-smooth functions
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A proximal method for composite minimization
• Gradient methods for minimizing composite functions
• An optimal method for stochastic composite optimization
• Introductory lectures on convex optimization. A basic course.
• Iteration-complexity of first-order penalty methods for convex programming
• Complexity of unconstrained \(L_2 - L_p\) minimization
• Stochastic simulation: Algorithms and analysis
• Feature Article: Optimization for simulation: Theory vs. Practice
• Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization
• On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems
• Recursive Trust-Region Methods for Multiscale Nonlinear Optimization
• Robust Stochastic Approximation Approach to Stochastic Programming
• Acceleration of Stochastic Approximation by Averaging
• Introduction to Stochastic Search and Optimization
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
• Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization, II: Shrinking Procedures and Optimal Algorithms
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
• A Stochastic Approximation Method
• Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization

This page was built for publication: Accelerated gradient methods for nonconvex nonlinear and stochastic programming