A stochastic ARC method with inexact function and random derivatives evaluations

Research output: Contribution to conferencePaper

Abstract

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

Conference

ConferenceThirty-seventh International Conference on Machine Learning
Period13/07/2018/07/20

Keywords

  • 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.

  • Projects

    Complexity in nonlinear optimization

    TOINT, P., Gould, N. I. M. & Cartis, C.

    1/11/08 → …

    Project: Research

    Cite this

    Toint, P. L. (Accepted/In press). A stochastic ARC method with inexact function and random derivatives evaluations. Paper presented at Thirty-seventh International Conference on Machine Learning, .