# First-Order Methods for Nonconvex Quadratic Minimization

arXiv: https://arxiv.org/abs/2003.04546 · HTML: https://mlsanity.com/paper/2003.04546/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2020.

## Built on by (most cited first, 10 of 10)

- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods](https://mlsanity.com/paper/2302.11962/) (2023)
- [Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain](https://mlsanity.com/paper/2110.03950/) (2021)
- [Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods](https://mlsanity.com/paper/2412.02175/) (2024)
- [Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitz](https://mlsanity.com/paper/2310.14616/) (2023)
- [Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Rate](https://mlsanity.com/paper/2401.03058/) (2024)
- [On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/2402.02569/) (2024)
- [On Underdamped Nesterov's Acceleration](https://mlsanity.com/paper/2304.14642/) (2023)
- [Noise is All You Need: Private Second-Order Convergence of Noisy SGD](https://mlsanity.com/paper/2410.06878/) (2024)
- [HOUDINI: Escaping from Moderately Constrained Saddles](https://mlsanity.com/paper/2205.13753/) (2022)

## Abstract (arXiv)

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.