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.
Scheinberg et al. (Wed,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: