High-order Evaluation Complexity of a Stochastic Adaptive Regularization Algorithm for Nonconvex Optimization Using Inexact Function Evaluations and Randomly Perturbed Derivatives

Stefania Bellavia, Gianmarco Gurioli, Benedetta Morini, Philippe TOINT

Résultats de recherche: Papier de travailArticle de travail

1 Téléchargements (Pure)

Résumé

A stochastic adaptive regularization algorithm allowing random noise in derivatives and inexact function values is proposed for computing strong approximate minimizers of any order for inexpensively constrained smooth optimization problems. For an objective function with Lipschitz continuous p-th derivative in a convex neighbourhood of the feasible set and given an arbitrary optimality order q, it is shown that this algorithm will, in expectation, compute such a point in at most O( ( \min_{1<=j<=q} \epsilon_j )^{-(p+1)/(p-q+1)} ) inexact evaluations of f and its derivatives whenever q=1 and the feasible set is convex, or q=2 and the problem is unconstrained, where \epsilon_j is the tolerance for j-th order accuracy. This bound becomes at most O( ( \min_{1<=j<=q} \epsilon_j )^{-q(p+1)/p} ) inexact evaluations in the other cases if all derivatives are Lipschitz continuous. Moreover these bounds are sharp in the order of the accuracy tolerances.
langue originaleAnglais
ÉditeurArxiv
Nombre de pages22
Volume2005.04639
Etat de la publicationPublié - 13 mai 2020

Empreinte digitale Examiner les sujets de recherche de « High-order Evaluation Complexity of a Stochastic Adaptive Regularization Algorithm for Nonconvex Optimization Using Inexact Function Evaluations and Randomly Perturbed Derivatives ». Ensemble, ils forment une empreinte digitale unique.

Contient cette citation