A stochastic ARC method with inexact function and random derivatives evaluations

Philippe L. Toint

A stochastic ARC method with inexact function and random derivatives evaluations

Philippe L. Toint

Namur Institute for Complex Systems

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

15 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

Empreinte digitale Examiner les sujets de recherche de « A stochastic ARC method with inexact function and random derivatives evaluations ». Ensemble, ils forment une empreinte digitale unique.

2 Actif

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

Contient cette citation

@conference{b6f2398b3ae44ad58e2e853114419908,

title = "A stochastic ARC method with inexact function and random derivatives evaluations",

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 = "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 ARC method with inexact function and random derivatives evaluations

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 ARC method with inexact function and random derivatives evaluations

Résumé

Une conférence

Accès au document

Complexity in nonlinear optimization

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

Contient cette citation