A stochastic ARC method with inexact function and random derivatives evaluations

Research output: Contribution to conferencePaperpeer-review

11 Downloads (Pure)


This paper focuses on an Adaptive Cubic Regularisation (ARC) method for
approximating a second-order critical point of a finite sum minimisation problem.
The variant presented belongs to the framework of Bellavia, Gurioli, Morinin
and Toint (2020): it employs random models with accuracy guaranteed with a
sufficiently large prefixed probability and deterministic inexact function
evaluations within a prescribed level of accuracy. Without assuming unbiased
estimators, the expected number of iterations is O( epsilon_1^{-3/2} ) or O( \max[ epsilon_1^{-3/2},epsilon_2^{-3} ] ) when searching for a first- or second-order critical point, respectively, where epsilon_j is the jth-order tolerance. These results match the worst-case optimal complexity for the deterministic counterpart of the method.
Original languageEnglish
Publication statusAccepted/In press - 2020
EventThirty-seventh International Conference on Machine Learning: ICML2020 -
Duration: 13 Jul 202018 Jul 2020


ConferenceThirty-seventh International Conference on Machine Learning


  • Stochastic optimization
  • Complexity theory

Fingerprint Dive into the research topics of 'A stochastic ARC method with inexact function and random derivatives evaluations'. Together they form a unique fingerprint.

Cite this