Recent Theoretical Advances in Non-Convex Optimization
From MaRDI portal
Abstract: Motivated by recent increased interest in optimization algorithms for non-convex optimization in application to training deep neural networks and other optimization problems in data analysis, we give an overview of recent theoretical results on global performance guarantees of optimization algorithms for non-convex optimization. We start with classical arguments showing that general non-convex problems could not be solved efficiently in a reasonable time. Then we give a list of problems that can be solved efficiently to find the global minimizer by exploiting the structure of the problem as much as it is possible. Another way to deal with non-convexity is to relax the goal from finding the global minimum to finding a stationary point or a local minimum. For this setting, we first present known results for the convergence rates of deterministic first-order methods, which are then followed by a general theoretical analysis of optimal stochastic and randomized gradient schemes, and an overview of the stochastic first-order methods. After that, we discuss quite general classes of non-convex problems, such as minimization of -weakly-quasi-convex functions and functions that satisfy Polyak--Lojasiewicz condition, which still allow obtaining theoretical convergence guarantees of first-order methods. Then we consider higher-order and zeroth-order/derivative-free methods and their convergence rates for non-convex optimization problems.
Recommendations
Cites work
- A concise second-order complexity analysis for unconstrained optimization using high-order regularized models
- A simple proof of the restricted isometry property for random matrices
- A Simplex Method for Function Minimization
- A theoretical and empirical comparison of gradient approximations in derivative-free optimization
- About the power law of the PageRank vector component distribution. II: The Buckley-Osthus model, verification of the power law for this model, and setup of real search engines
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- Accelerated methods for nonconvex optimization
- Accelerated primal-dual gradient descent with linesearch for convex, nonconvex, and nonsmooth optimization problems
- Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization
- Adaptive cubic regularisation methods for unconstrained optimization. I: Motivation, convergence and numerical results
- Adaptive cubic regularisation methods for unconstrained optimization. II: Worst-case function- and derivative-evaluation complexity
- Adaptive subgradient methods for online learning and stochastic optimization
- Alternating minimization methods for strongly convex optimization
- An accelerated directional derivative method for smooth stochastic convex optimization
- An accelerated method for derivative-free smooth stochastic convex optimization
- An adaptive high order method for finding third-order critical points of nonconvex optimization
- An Incremental Gradient(-Projection) Method with Momentum Term and Adaptive Stepsize Rule
- Black-Box Complexity of Local Minimization
- Combining stochastic adaptive cubic regularization with negative curvature for nonconvex optimization
- Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
- Convex optimization: algorithms and complexity
- Cubic regularization of Newton method and its global performance
- Decoding by Linear Programming
- Deep learning
- Derivative-free methods for policy optimization: guarantees for linear quadratic systems
- Derivative-free optimization methods
- Encyclopedia of Optimization
- Enhancing sparsity by reweighted \(\ell _{1}\) minimization
- Exact matrix completion via convex optimization
- Finding approximate local minima faster than gradient descent
- First-order and stochastic optimization methods for machine learning
- First-order methods for convex optimization
- Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation
- Foundations of Data Science
- Generalized descent for global optimization
- Generalized momentum-based methods: a Hamiltonian perspective
- Generalized uniformly optimal methods for nonlinear programming
- Global Convergence Rate Analysis of a Generic Line Search Algorithm with Noise
- Gradient descent finds the cubic-regularized nonconvex Newton step
- Gradient descent with random initialization: fast global convergence for nonconvex phase retrieval
- Gradient methods for problems with inexact model of the objective
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 7246283 (Why is no real title available?)
- scientific article; zbMATH DE number 7306906 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- scientific article; zbMATH DE number 3245053 (Why is no real title available?)
- scientific article; zbMATH DE number 3313108 (Why is no real title available?)
- scientific article; zbMATH DE number 3371284 (Why is no real title available?)
- Identifiability in Blind Deconvolution With Subspace or Sparsity Constraints
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Incremental gradient algorithms with stepsizes bounded away from zero
- Incremental majorization-minimization optimization with application to large-scale machine learning
- Inexact model: a framework for optimization and variational inequalities
- Introduction to Derivative-Free Optimization
- Introductory lectures on convex optimization. A basic course.
- Iterative hard thresholding for compressed sensing
- Iterative Potts minimization for the recovery of signals with discontinuities from indirect measurements: the multivariate case
- Large-scale machine learning with stochastic gradient descent
- Lectures on convex optimization
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Low-rank matrix completion using alternating minimization
- Lower bounds for finding stationary points I
- Lower bounds for finding stationary points II: first-order methods
- Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
- Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization
- Minimizing finite sums with the stochastic average gradient
- Misspecified nonconvex statistical optimization for sparse phase retrieval
- Newton-type methods for non-convex optimization under inexact Hessian information
- Non-convex optimization for machine learning
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Numerical methods for finding global extrema (Case of a non-uniform mesh)
- On Nonconvex Optimization for Machine Learning
- Online convex optimization in the bandit setting: gradient descent without a gradient
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary
- Optimization methods for large-scale machine learning
- Optimization with sparsity-inducing penalties
- Optimizing static linear feedback: gradient method
- Parametric estimation. Finite sample theory
- Phase retrieval via Wirtinger flow: theory and algorithms
- Primal-dual accelerated gradient methods with small-dimensional relaxation oracle
- Proximal splitting methods in signal processing
- Random gradient-free minimization of convex functions
- Some methods of speeding up the convergence of iteration methods
- Some NP-complete problems in quadratic and nonlinear programming
- Stochastic block mirror descent methods for nonsmooth and stochastic optimization
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
- Stochastic global optimization.
- Stochastic model-based minimization of weakly convex functions
- Stochastic three points method for unconstrained smooth minimization
- Stochastic variance-reduced cubic regularization methods
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks
- Trust Region Methods
- Universal Regularization Methods: Varying the Power, the Smoothness and the Accuracy
- Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
- Zeroth-order methods for noisy Hölder-gradient functions
Cited in
(11)- Recent progress in unconstrained nonlinear optimization without derivatives
- Why Do Local Methods Solve Nonconvex Problems?
- Recent advances in nonconvex semi-infinite programming: applications and algorithms
- (Global) optimization: historical notes and recent developments
- Global solutions to nonconvex problems by evolution of Hamilton-Jacobi PDEs
- A unified Bregman alternating minimization algorithm for generalized DC programs with application to imaging
- Hessian barrier algorithms for non-convex conic optimization
- Optimal experimental design for parameter estimation in the presence of observation noise
- Kernel sum of squares for data adapted kernel learning of dynamical systems from data: a global optimization approach
- Scientific machine learning: a symbiosis
- Hypodifferentials of nonsmooth convex functions and their applications to nonsmooth convex optimization
This page was built for publication: Recent Theoretical Advances in Non-Convex Optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6355806)
