Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

Stefania Bellavia, Gianmarco Gurioli, Benedetta Morini, Philippe Toint

Research output: Contribution to journalArticle

2 Downloads (Pure)

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 β-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 [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 propposed algorithm in at most O[Formula presented] iterations and at most O[Formula presented] approximate evaluations. An algorithmic variant, although more rigid in practice, can be proved to find such an approximate minimizer in O[Formula presented] 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
Number of pages35
JournalSIAM Journal on Optimization
Volume29
Issue number4
DOIs
Publication statusPublished - 2 Jan 2020

Keywords

  • evaluation complexity
  • regularization methods
  • inexact functions and derivatives
  • subsampling methods
  • machine learning
  • Evaluation complexity
  • Subsampling methods
  • Inexact functions and derivatives
  • Regularization methods

Fingerprint Dive into the research topics of 'Adaptive regularization algorithms with inexact evaluations for nonconvex optimization'. Together they form a unique fingerprint.

  • Projects

    Complexity in nonlinear optimization

    TOINT, P., Gould, N. I. M. & Cartis, C.

    1/11/08 → …

    Project: Research

    Activities

    • 3 Invited talk
    • 3 Visiting an external academic institution
    • 1 Participation in workshop, seminar, course

    5th Conference on Numerical Analysis and Optimization

    Philippe Toint (Contributor)

    6 Jan 20209 Jan 2020

    Activity: Participating in or organising an event typesParticipation in workshop, seminar, course

    ENSEEIHT-IRIT

    Philippe Toint (Visiting researcher)

    4 Nov 20198 Nov 2019

    Activity: Visiting an external institution typesVisiting an external academic institution

    Cite this