Stochastic analysis of an adaptive cubic regularization method under inexact gradient evaluations and dynamic Hessian accuracy

Abstract

We here adapt an extended version of the adaptive cubic regularization method with dynamic inexact Hessian information for nonconvex optimization in Bellavia et al. [Adaptive cubic regularization methods with dynamic inexact hessian information and applications to finite-sum minimization. IMA Journal of Numerical Analysis. 2021;41(1):764–799] to the stochastic optimization setting. While exact function evaluations are still considered, this novel variant inherits the innovative use of adaptive accuracy requirements for Hessian approximations introduced in the just quoted paper and additionally employs inexact computations of the gradient. Without restrictions on the variance of the errors, we assume that these approximations are available within a sufficiently large, but fixed, probability and we extend, in the spirit of Cartis and Scheinberg [Global convergence rate analysis of unconstrained optimization methods based on probabilistic models. Math Program Ser A. 2018;159(2):337–375], the deterministic analysis of the framework to its stochastic counterpart, showing that the expected number of iterations to reach a first-order stationary point matches the well-known worst-case optimal complexity. This is, in fact, still given by $O\left({ϵ}^{-3/2}\right)$, with respect to the first-order ϵ tolerance. Finally, numerical tests on nonconvex finite-sum minimization confirm that using inexact first- and second-order derivatives can be beneficial in terms of the computational savings.

Keywords:

• Adaptive cubic regularization methods
• inexact derivatives evaluations
• stochastic nonconvex optimization
• worst-case complexity analysis
• finite-sum minimization

2010 Mathematics Subject Classifications:

• 65K05
• 49M37
• 90C30

Acknowledgments

The authors dedicate this paper, in honour of his 70th birthday, to Alfredo Iusem. Thanks are due to Coralia Cartis, Benedetta Morini and Philippe L. Toint for fruitful discussion on stochastic complexity analysis and to two anonymous referees whose comments significantly improved the presentation of this paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

The authors are member of the INdAM Research Group GNCS and partially supported by INdAM-GNCS through Progetti di Ricerca 2019.