Adaptive Regularization for Nonconvex Optimization sing Inexact Function Values and Randomly Perturbed Derivatives

Stefania Bellavia, Gianmarco Gurioli, Benedetta Morini, Philippe TOINT

Research output: Working paper

1 Downloads (Pure)

Abstract

  A regularization algorithm allowing random noise in derivatives and inexact
  function values is proposed for computing approximate local critical points
  of any order for smooth unconstrained optimization problems. For an
  objective function with Lipschitz continuous p-th derivative and given an
  arbitrary optimality order q <= p, it is shown that this algorithm will, in
  expectation, compute such a point in at most  
         O((min_{j=1,...,q}epsilon_j)^{-(p+1)/(p-q+1)})
  inexact evaluations of f and its derivatives whenever q in {1,2}, where
  \epsilon_j is the tolerance for j-th order accuracy.  This bound becomes at most
         O((min_{j=1,...,q}epsilon_j)^{-(q(p+1))/(p)})
  inexact evaluations if q>2 and all derivatives are Lipschitz
  continuous. Moreover these bounds are sharp in the order of the accuracy
  tolerances. An extension to convexly constrained problems is also outlined.
Original languageEnglish
PublisherArxiv
Number of pages22
Volume2005.04639
Publication statusPublished - 13 May 2020

Keywords

  • evaluation complexity
  • regularization methods
  • lnexact functions and derivatives
  • stochastic analysis

Fingerprint Dive into the research topics of 'Adaptive Regularization for Nonconvex Optimization sing Inexact Function Values and Randomly Perturbed Derivatives'. Together they form a unique fingerprint.

Cite this