A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees
원문 초록
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 $(\epsilon,\sqrt{\epsilon})$-SOSP of this problem. Our method is not only implementable, but also achieves an iteration complexity of ${\cal O}(\epsilon^{-3/2})$, which matches the best known iteration complexity of second-order methods for finding an $(\epsilon,\sqrt{\epsilon})$-SOSP of unconstrained nonconvex optimization. The operation complexity, consisting of ${\cal O}(\epsilon^{-3/2})$ Cholesky factorizations and $\widetilde{\cal O}(\epsilon^{-3/2}\min\{n,\epsilon^{-1/4}\})$ other fundamental operations, is also established for our method.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
NysAct: A Scalable Preconditioned Gradient Descent using Nystrom Approximation
Towards Practical Second-Order Optimizers in Deep Learning: Insights from Fisher Information Analysis
SASSHA: Sharpness-aware Adaptive Second-order Optimization with Stable Hessian Approximation
Online Covariance Matrix Estimation in Sketched Newton Methods
Exact, Tractable Gauss-Newton Optimization in Deep Reversible Architectures Reveal Poor Generalization
Alternating Iteratively Reweighted $\ell_1$ and Subspace Newton Algorithms for Nonconvex Sparse Optimization
토론
이 논문과 연결된 포럼 글이 아직 없습니다.