A stochastic cubic regularisation method with inexact function evaluations and random derivatives for finite sum minimisation

Stefania Bellavia; Gianmarco Gurioli; Benedetta Morini; Philippe L. Toint

A stochastic cubic regularisation method with inexact function evaluations and random derivatives for finite sum minimisation

Stefania Bellavia
, Gianmarco Gurioli
, Benedetta Morini
, Philippe L. Toint

Namur Institute for Complex Systems

Research output: Contribution to conference › Paper › peer-review

118 Downloads (Pure)

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 language	English
Publication status	Accepted/In press - 2020
Event	Thirty-seventh International Conference on Machine Learning: ICML2020 - Duration: 13 Jul 2020 → 18 Jul 2020

Conference

Conference	Thirty-seventh International Conference on Machine Learning
Period	13/07/20 → 18/07/20

Keywords

Stochastic optimization
Complexity theory

Access to Document

ICML2020Accepted author manuscript, 227 KB

2 Article
1 Book
1 Working paper

Evaluation complexity of algorithms for nonconvex optimization
Cartis, C., Gould, N. I. M. & TOINT, P., Jul 2022, SIAM. 600 p. (SIAM-MOS Series on Optimization)
Research output: Book/Report/Journal › Book
Adaptive regularization algorithms with inexact evaluations for nonconvex optimization
Bellavia, S., Gurioli, G., Morini, B. & Toint, P., 2 Jan 2020, In: SIAM Journal on Optimization. 29, 4, p. 2881-2915 35 p.
Research output: Contribution to journal › Article › peer-review

Open Access
File
80 Downloads (Pure)
Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints
Toint, P., Cartis, C. & Gould, N. I. M., Jan 2020, In: SIAM Journal on Optimization. 30, 1, p. 513-541 29 p.
Research output: Contribution to journal › Article › peer-review

Open Access
File
95 Downloads (Pure)

Complexity in nonlinear optimization
Toint, P. (CoI), Gould, N. I. M. (CoI) & Cartis, C. (CoI)
1/11/08 → …
Project: Research
ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization
Sartenaer, A. (CoI) & Toint, P. (CoI)
1/01/87 → …
Project: Research Axis

Cite this

@conference{b6f2398b3ae44ad58e2e853114419908,

title = "A stochastic cubic regularisation method with inexact function evaluations and random derivatives for finite sum minimisation",

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\textasciicircum{}\{-3/2\} ) or O( \textbackslash{}max[ epsilon\_1\textasciicircum{}\{-3/2\},epsilon\_2\textasciicircum{}\{-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.",

keywords = "Stochastic optimization, Complexity theory",

author = "Stefania Bellavia and Gianmarco Gurioli and Benedetta Morini and Toint, \{Philippe L.\}",

year = "2020",

language = "English",

note = "Thirty-seventh International Conference on Machine Learning : ICML2020 ; Conference date: 13-07-2020 Through 18-07-2020",

}

TY - CONF

T1 - A stochastic cubic regularisation method with inexact function evaluations and random derivatives for finite sum minimisation

AU - Bellavia, Stefania

AU - Gurioli, Gianmarco

AU - Morini, Benedetta

AU - Toint, Philippe L.

PY - 2020

Y1 - 2020

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

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

KW - Stochastic optimization

KW - Complexity theory

M3 - Paper

T2 - Thirty-seventh International Conference on Machine Learning

Y2 - 13 July 2020 through 18 July 2020

ER -

A stochastic cubic regularisation method with inexact function evaluations and random derivatives for finite sum minimisation

Abstract

Conference

Keywords

Access to Document

Fingerprint

Research output

Evaluation complexity of algorithms for nonconvex optimization

Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints

Projects

Complexity in nonlinear optimization

ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization

Cite this