First-Order Methods for Nonconvex Quadratic Minimization
From MaRDI portal
Publication:5113167
Abstract: We consider minimization of indefinite quadratics with either trust-region (norm) constraints or cubic regularization. Despite the nonconvexity of these problems we prove that, under mild assumptions, gradient descent converges to their global solutions, and give a non-asymptotic rate of convergence for the cubic variant. We also consider Krylov subspace solutions and establish sharp convergence guarantees to the solutions of both trust-region and cubic-regularized problems. Our rates mirror the behavior of these methods on convex quadratics and eigenvector problems, highlighting their scalability. When we use Krylov subspace solutions to approximate the cubic-regularized Newton step, our results recover the strongest known convergence guarantees to approximate second-order stationary points of general smooth nonconvex functions.
Recommendations
- First-order methods for convex optimization
- scientific article; zbMATH DE number 223552
- Linear convergence of first order methods for non-strongly convex optimization
- Optimized first-order methods for smooth convex minimization
- First-Order Methods for Fast Feasibility Pursuit of Non-convex QCQPs
- Efficient first-order methods for convex minimization: a constructive approach
- An inexact first-order method for constrained nonlinear optimization
- Optimizing first-order methods for smooth convex minimization of gradient Q-linearly convergence
- A first order method for finding minimal norm-like solutions of convex optimization problems
- Quasiconvex first-order approximations and Kuhn-Tucker type optimality conditions
Cites work
- A D.C. Optimization Algorithm for Solving the Trust-Region Subproblem
- A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices
- A geometric analysis of phase retrieval
- A linear-time algorithm for trust region problems
- A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization
- A second-order cone based approach for solving the trust-region subproblem and its variants
- Accelerated methods for nonconvex 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
- Affine conjugate adaptive Newton methods for nonlinear elastomechanics
- Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
- Cubic regularization of Newton method and its global performance
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Fast Curvature Matrix-Vector Products for Second-Order Gradient Descent
- Finding approximate local minima faster than gradient descent
- Globally solving the trust region subproblem using simple first-order methods
- Gradient descent finds the cubic-regularized nonconvex Newton step
- Gradient descent learns linear dynamical systems
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 4213315 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 3633705 (Why is no real title available?)
- scientific article; zbMATH DE number 1012640 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution
- Introductory lectures on convex optimization. A basic course.
- Local Minimizers of Quadratic Functions on Euclidean Balls and Spheres
- Methods of conjugate gradients for solving linear systems
- Newton-type methods for non-convex optimization under inexact Hessian information
- On parallel complexity of nonsmooth convex optimization
- On the generalized Lanczos trust-region method
- On the use of iterative methods in cubic regularization for unconstrained optimization
- Optimization methods for large-scale machine learning
- Solving the Trust-Region Subproblem using the Lanczos Method
- Some NP-complete problems in quadratic and nonlinear programming
- The Conjugate Gradient Method and Trust Regions in Large Scale Optimization
- Tight query complexity lower bounds for PCA via finite sample deformed Wigner law
- Trust Region Methods
Cited in
(18)- Refined bounds on the convergence of block Lanczos method for extended trust-region subproblem
- Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
- Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
- Gradient descent finds the cubic-regularized nonconvex Newton step
- Solving the cubic regularization model by a nested restarting Lanczos method
- A new Lagrangian-based first-order method for nonconvex constrained optimization
- Steering exact penalty DCA for nonsmooth DC optimisation problems with equality and inequality constraints
- A Block Lanczos Method for Large-Scale Quadratic Minimization Problems with Orthogonality Constraints
- Recent Theoretical Advances in Non-Convex Optimization
- Exploiting constant trace property in large-scale polynomial optimization
- A unified Bregman alternating minimization algorithm for generalized DC programs with application to imaging
- On convergence of the generalized Lanczos trust-region method for trust-region subproblems
- Fast convergence of trust-regions for non-isolated minima via analysis of CG on indefinite matrices
- Riemannian adaptive regularized Newton methods with Hölder continuous Hessians
- Complexity analysis of inexact cubic-regularized primal-dual methods for finding second-order stationary points
- Provable accelerated convergence of Nesterov's momentum for deep ReLU neural networks
- On the convergence of SignSGD under weak first- and second-order gradient Lipschitz
- Complexity of minimizing regularized convex quadratic functions
This page was built for publication: First-Order Methods for Nonconvex Quadratic Minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113167)
