First- and Second-Order Stochastic Adaptive Regularization with Cubics: High-Probability Iteration and Sample Complexity

We present high-probability (and expectation) complexity bounds for two versions of stochastic adaptive regularization methods with cubics (SARC), also known as regularized Newton methods. The first algorithm aims to find first-order stationary points, whereas the second targets second-order optimality conditions. Both methods employ stochastic zeroth-, first-, and second-order oracles with specific accuracy and reliability requirements. These oracles, which have been previously used with other stochastic adaptive methods such as trust region and line-search algorithms, are applicable to various optimization settings, including expected risk minimization and simulation optimization. In this paper, we establish the first high-probability iteration and sample complexity bounds for both first- and second-order SARC algorithms. Our analysis demonstrates that, as in the deterministic case, they outperform other stochastic adaptive methods.

Funding: Financial support from the National Science Foundation [Grant CCF-21-40057 ] and the Office of Naval Research [Award N00014-22-1-215] is acknowledged.