mlsanityData to 7 Oct 2026

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

arXiv 2207.05697 ↗First posted 12 Jul 2022math.OC cs.LG cs.NAcited by 2

Not on the map. Why?

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.

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

Builds on

18 of 42 references.

References · 18

  1. 2017Lower Bounds for Finding Stationary Points Icited by 125
  2. 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
  3. 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
  4. 2017Neon2: Finding Local Minima via First-Order Oraclescited by 36
  5. 2019An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraintscited by 29
  6. 2018A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimizationcited by 23
  7. 2019Complexity of Proximal augmented Lagrangian for nonconvex optimization with nonlinear equality constraintscited by 17
  8. 2017Complexity analysis of second-order line-search algorithms for smooth nonconvex optimizationcited by 16
  9. 2019Polynomial time guarantees for the Burer-Monteiro methodcited by 12
  10. 2019Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimizationcited by 10
  11. 2017NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimizationcited by 9
  12. 2017Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundarycited by 8
6 more
  1. 2019A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guaranteescited by 7
  2. 2017Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimizationcited by 6
  3. 2022Computing second-order points under equality constraints: revisiting Fletcher's augmented Lagrangiancited by 6
  4. 2017Optimality of orders one to three and beyond: characterization and evaluation complexity in constrained nonconvex optimizationcited by 5
  5. 2021Hessian barrier algorithms for non-convex conic optimizationcited by 5
  6. 2017An Inexact Regularized Newton Framework with a Worst-Case Iteration Complexity of O(ε-3/2) for Nonconvex Optimizationcited by 2

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 1.

2 papers.

  1. 2023A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimizationcited by 2
  2. 2024Stochastic interior-point methods for smooth conic optimization with applicationscited by 1