Exploiting negative curvature in conjunction with adaptive sampling: theoretical results and a practical algorithm

Authors:
Open Access
Publisher website
Google Scholar
Abstract
In this paper, we propose algorithms that exploit negative curvature for solving noisy nonlinear nonconvex unconstrained optimization problems. We consider both deterministic inexact and stochastic settings, and develop two-step algorithms that combine directions of negative curvature and descent directions to update the iterates. Under reasonable assumptions, we prove second-order convergence results and derive complexity guarantees for both settings. To tackle large-scale problems, we develop a practical variant that utilizes the conjugate gradient method with negative curvature detection and early stopping to compute a step, a simple adaptive step size scheme, and a strategy for selecting the sample sizes of the gradient and Hessian approximations as the optimization progresses. Numerical results on two machine learning problems showcase the efficacy and efficiency of the practical method.
Funding Information
  • National Science Foundation (DMS-2324643)
  • Office of Naval Research (N00014-24-1-2670)

This publication has 43 references indexed in Scilit: