# A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 42 references that are in the map.
- First posted on arXiv 12 Jul 2022.

## Builds on (most cited first, 18 of 18)

- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent](https://mlsanity.com/paper/1711.10456/) (2017)
- ["Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions](https://mlsanity.com/paper/1705.02766/) (2017)
- [Neon2: Finding Local Minima via First-Order Oracles](https://mlsanity.com/paper/1711.06673/) (2017)
- [An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints](https://mlsanity.com/paper/1906.11357/) (2019)
- [A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimization](https://mlsanity.com/paper/1803.02924/) (2018)
- [Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraints](https://mlsanity.com/paper/1908.00131/) (2019)
- [Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization](https://mlsanity.com/paper/1706.03131/) (2017)
- [Polynomial time guarantees for the Burer-Monteiro method](https://mlsanity.com/paper/1912.01745/) (2019)
- [Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization](https://mlsanity.com/paper/1912.04365/) (2019)
- [NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimization](https://mlsanity.com/paper/1712.01033/) (2017)
- [Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary](https://mlsanity.com/paper/1702.04300/) (2017)
- [A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees](https://mlsanity.com/paper/1904.03563/) (2019)
- [Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization](https://mlsanity.com/paper/1709.07180/) (2017)
- [Computing second-order points under equality constraints: revisiting Fletcher's augmented Lagrangian](https://mlsanity.com/paper/2204.01448/) (2022)
- [Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimization](https://mlsanity.com/paper/1705.07285/) (2017)
- [Hessian barrier algorithms for non-convex conic optimization](https://mlsanity.com/paper/2111.00100/) (2021)
- [An Inexact Regularized Newton Framework with a Worst-Case Iteration Complexity of O(ε-3/2) for Nonconvex Optimization](https://mlsanity.com/paper/1708.00475/) (2017)

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

- [A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization](https://mlsanity.com/paper/2301.04204/) (2023)
- [Stochastic interior-point methods for smooth conic optimization with applications](https://mlsanity.com/paper/2412.12987/) (2024)

## Abstract (arXiv)

In this paper we consider finding an approximate second-order stationary point (SOSP) of nonconvex conic optimization that minimizes a twice differentiable function over the intersection of an affine subspace and a convex cone. In particular, we propose a Newton-conjugate gradient (Newton-CG) based barrier method for finding an (ε,√ε)-SOSP of this problem. Our method is not only implementable, but also achieves an iteration complexity of cal O(ε-3/2), which matches the best known iteration complexity of second-order methods for finding an (ε,√ε)-SOSP of unconstrained nonconvex optimization. The operation complexity, consisting of cal O(ε-3/2) Cholesky factorizations and widetildecal O(ε-3/2minn,ε-1/4) other fundamental operations, is also established for our method.