A regularization algorithm using inexact function values and inexact derivatives is proposed and its evaluation complexity analyzed. This algorithm is applicable to unconstrained problems and to problems with inexpensive constraints (that is, constraints whose evaluation and enforcement has negligible cost) under the assumption that the derivative of highest degree is β-Holder continuous. It features a very flexible adaptive mechanism for determining the inexactness which is allowed, at each iteration, when computing objective function values and derivatives. The complexity analysis covers arbitrary optimality order and arbitrary degree of available approximate derivatives. It extends results of Cartis, Gould, and Toint [SIAM J. Optim., to appear] on the evaluation complexity to the inexact case: if a qth-order minimizer is sought using approximations to the first p derivatives, it is proved that a suitable approximate minimizer within ε is computed by the proposed algorithm in at most O(ε^[-(p+β)/(p-q+β)]) iterations and at most O(abs(log(ε)) ε^[-(p+β)/(p-q+β)]) approximate evaluations. An algorithmic variant, although more rigid in practice, can be proved to find such an approximate minimizer in O(abs(log(ε))+ ε^[-(p+β)/(p-q+β)]) evaluations. While the proposed framework remains so far conceptual for high degrees and orders, it is shown to yield simple and computationally realistic inexact methods when specialized to the unconstrained and bound-constrained first- and second-order cases. The deterministic complexity results are finally extended to the stochastic context, yielding adaptive sample-size rules for subsampling methods typical of machine learning.

Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization / Stefania Bellavia, Gianmarco Gurioli, Benedetta Morini, Philippe L. Toint. - In: SIAM JOURNAL ON OPTIMIZATION. - ISSN 1052-6234. - STAMPA. - 29:(2019), pp. 2881-2915. [10.1137/18M1226282]

Adaptive Regularization Algorithms with Inexact Evaluations for Nonconvex Optimization

Stefania Bellavia;Gianmarco Gurioli;Benedetta Morini;
2019

Abstract

A regularization algorithm using inexact function values and inexact derivatives is proposed and its evaluation complexity analyzed. This algorithm is applicable to unconstrained problems and to problems with inexpensive constraints (that is, constraints whose evaluation and enforcement has negligible cost) under the assumption that the derivative of highest degree is β-Holder continuous. It features a very flexible adaptive mechanism for determining the inexactness which is allowed, at each iteration, when computing objective function values and derivatives. The complexity analysis covers arbitrary optimality order and arbitrary degree of available approximate derivatives. It extends results of Cartis, Gould, and Toint [SIAM J. Optim., to appear] on the evaluation complexity to the inexact case: if a qth-order minimizer is sought using approximations to the first p derivatives, it is proved that a suitable approximate minimizer within ε is computed by the proposed algorithm in at most O(ε^[-(p+β)/(p-q+β)]) iterations and at most O(abs(log(ε)) ε^[-(p+β)/(p-q+β)]) approximate evaluations. An algorithmic variant, although more rigid in practice, can be proved to find such an approximate minimizer in O(abs(log(ε))+ ε^[-(p+β)/(p-q+β)]) evaluations. While the proposed framework remains so far conceptual for high degrees and orders, it is shown to yield simple and computationally realistic inexact methods when specialized to the unconstrained and bound-constrained first- and second-order cases. The deterministic complexity results are finally extended to the stochastic context, yielding adaptive sample-size rules for subsampling methods typical of machine learning.
2019
29
2881
2915
Stefania Bellavia, Gianmarco Gurioli, Benedetta Morini, Philippe L. Toint
File in questo prodotto:
File Dimensione Formato  
SIOPT_ARCINESATTO.pdf

Accesso chiuso

Descrizione: Articolo principale
Tipologia: Pdf editoriale (Version of record)
Licenza: Tutti i diritti riservati
Dimensione 593.91 kB
Formato Adobe PDF
593.91 kB Adobe PDF   Richiedi una copia
SIOPT_ARCIINESATTO_preprint.pdf

accesso aperto

Tipologia: Versione finale referata (Postprint, Accepted manuscript)
Licenza: Open Access
Dimensione 432.7 kB
Formato Adobe PDF
432.7 kB Adobe PDF

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1178998
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 27
  • ???jsp.display-item.citation.isi??? 26
social impact