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

Résultats de recherche: Contribution à un événement scientifique (non publié) › Papier › Revue par des pairs

71 Téléchargements (Pure)

Résumé

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.

langue originale	Anglais
Etat de la publication	Accepté/sous presse - 2020
Evénement	Thirty-seventh International Conference on Machine Learning: ICML2020 - Durée: 13 juil. 2020 → 18 juil. 2020

Une conférence

Une conférence	Thirty-seventh International Conference on Machine Learning
période	13/07/20 → 18/07/20

Accès au document

ICML2020Accepted author manuscript, 227 KB

2 Article
1 Livre
1 Papier de travail

Evaluation complexity of algorithms for nonconvex optimization
Cartis, C., Gould, N. I. M. & TOINT, P., juil. 2022, SIAM. 600 p. (SIAM-MOS Series on Optimization)
Résultats de recherche: Livre/Rapport/Revue › Livre
Adaptive regularization algorithms with inexact evaluations for nonconvex optimization
Bellavia, S., Gurioli, G., Morini, B. & Toint, P., 2 janv. 2020, Dans: SIAM Journal on Optimization. 29, 4, p. 2881-2915 35 p.
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

Accès ouvert
File
42 Téléchargements (Pure)
Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints
Toint, P., Cartis, C. & Gould, N. I. M., janv. 2020, Dans: SIAM Journal on Optimization. 30, 1, p. 513-541 29 p.
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

Accès ouvert
File
53 Téléchargements (Pure)

2 Actif

Complexity in nonlinear optimization
Toint, P. (Co-investigateur), Gould, N. I. M. (Co-investigateur) & Cartis, C. (Co-investigateur)
1/11/08 → …
Projet: Recherche
ADALGOPT: ADALGOPT - Algorithmes avancés en optimisation non-linéaire
Sartenaer, A. (Co-investigateur) & Toint, P. (Co-investigateur)
1/01/87 → …
Projet: Axe de recherche

Contient cette citation

@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 forapproximating a second-order critical point of a finite sum minimisation problem.The variant presented belongs to the framework of Bellavia, Gurioli, Morininand Toint (2020): it employs random models with accuracy guaranteed with asufficiently large prefixed probability and deterministic inexact functionevaluations within a prescribed level of accuracy. Without assuming unbiasedestimators, 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.",

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",

}

A stochastic cubic regularisation method with inexact function evaluations and random derivatives for finite sum minimisation. / Bellavia, Stefania; Gurioli, Gianmarco; Morini, Benedetta et al.
2020. Papier présenté � Thirty-seventh International Conference on Machine Learning.

Résultats de recherche: Contribution à un événement scientifique (non publié) › Papier › Revue par des pairs

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 forapproximating a second-order critical point of a finite sum minimisation problem.The variant presented belongs to the framework of Bellavia, Gurioli, Morininand Toint (2020): it employs random models with accuracy guaranteed with asufficiently large prefixed probability and deterministic inexact functionevaluations within a prescribed level of accuracy. Without assuming unbiasedestimators, 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 forapproximating a second-order critical point of a finite sum minimisation problem.The variant presented belongs to the framework of Bellavia, Gurioli, Morininand Toint (2020): it employs random models with accuracy guaranteed with asufficiently large prefixed probability and deterministic inexact functionevaluations within a prescribed level of accuracy. Without assuming unbiasedestimators, 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

Résumé

Une conférence

Accès au document

Empreinte digitale

Résultat de recherche

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

Projets

Complexity in nonlinear optimization

ADALGOPT: ADALGOPT - Algorithmes avancés en optimisation non-linéaire

Contient cette citation