Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

Stefania Bellavia, Gianmarco Gurioli, Benedetta Morini, Philippe Toint

Research output: Contribution to journalArticle

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 beta-Hölder 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 (2018) 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 epsilon is computed by the proposed algorithm in at most O(epsilon^{-(p+beta)/(p-q+beta)}) iterations and at most O(|\log(\epsilon)|\epsilon^{-(p+beta)/(p-q+beta)}) approximate evaluations. An algorithmic variant, although more rigid in practice, can be proved to find such an approximate minimizer in O(|\log(\epsilon)|+\epsilon^{-(p+beta)/(p-q+beta)}) 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.
Original languageEnglish
Pages (from-to)2881-2915
JournalSIAM Journal on Optimization
Volume29
Issue number4
Publication statusPublished - 2 Jan 2020

Fingerprint

Nonconvex Optimization
Adaptive algorithms
Regularization
Derivatives
Derivative
Minimizer
Evaluation
Inexact Methods
Iteration
Subsampling
Complexity Analysis
Arbitrary
Value Function
Learning systems
Optimality
Machine Learning
Sample Size
Objective function
Cover
First-order

Keywords

  • evaluation complexity
  • regularization methods
  • inexact functions and derivatives
  • subsampling methods
  • machine learning

Cite this

Bellavia, Stefania ; Gurioli, Gianmarco ; Morini, Benedetta ; Toint, Philippe. / Adaptive regularization algorithms with inexact evaluations for nonconvex optimization. In: SIAM Journal on Optimization. 2020 ; Vol. 29, No. 4. pp. 2881-2915.
@article{9b35c02c72fc426d85d352c68e65d452,
title = "Adaptive regularization algorithms with inexact evaluations for nonconvex optimization",
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 beta-H{\"o}lder 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 (2018) 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 epsilon is computed by the proposed algorithm in at most O(epsilon^{-(p+beta)/(p-q+beta)}) iterations and at most O(|\log(\epsilon)|\epsilon^{-(p+beta)/(p-q+beta)}) approximate evaluations. An algorithmic variant, although more rigid in practice, can be proved to find such an approximate minimizer in O(|\log(\epsilon)|+\epsilon^{-(p+beta)/(p-q+beta)}) 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.",
keywords = "evaluation complexity, regularization methods, inexact functions and derivatives, subsampling methods, machine learning",
author = "Stefania Bellavia and Gianmarco Gurioli and Benedetta Morini and Philippe Toint",
year = "2020",
month = "1",
day = "2",
language = "English",
volume = "29",
pages = "2881--2915",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics",
number = "4",

}

Adaptive regularization algorithms with inexact evaluations for nonconvex optimization. / Bellavia, Stefania; Gurioli, Gianmarco; Morini, Benedetta; Toint, Philippe.

In: SIAM Journal on Optimization, Vol. 29, No. 4, 02.01.2020, p. 2881-2915.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

AU - Bellavia, Stefania

AU - Gurioli, Gianmarco

AU - Morini, Benedetta

AU - Toint, Philippe

PY - 2020/1/2

Y1 - 2020/1/2

N2 - 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 beta-Hölder 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 (2018) 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 epsilon is computed by the proposed algorithm in at most O(epsilon^{-(p+beta)/(p-q+beta)}) iterations and at most O(|\log(\epsilon)|\epsilon^{-(p+beta)/(p-q+beta)}) approximate evaluations. An algorithmic variant, although more rigid in practice, can be proved to find such an approximate minimizer in O(|\log(\epsilon)|+\epsilon^{-(p+beta)/(p-q+beta)}) 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.

AB - 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 beta-Hölder 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 (2018) 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 epsilon is computed by the proposed algorithm in at most O(epsilon^{-(p+beta)/(p-q+beta)}) iterations and at most O(|\log(\epsilon)|\epsilon^{-(p+beta)/(p-q+beta)}) approximate evaluations. An algorithmic variant, although more rigid in practice, can be proved to find such an approximate minimizer in O(|\log(\epsilon)|+\epsilon^{-(p+beta)/(p-q+beta)}) 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.

KW - evaluation complexity

KW - regularization methods

KW - inexact functions and derivatives

KW - subsampling methods

KW - machine learning

M3 - Article

VL - 29

SP - 2881

EP - 2915

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 4

ER -