Optimization Online


Trust-region algorithms: probabilistic complexity and intrinsic noise with applications to subsampling techniques

Stefania Bellavia(stefania.bellavia***at***unifi.it)
Gianmarco Gurioli(gianmarco.gurioli***at***unifi.it)
Benedetta Morini(benedetta.morini***at***unifi.it)
Philippe L. Toint(philippe.toint***at***unamur.be)

Abstract: A trust-region algorithm is presented for finding approximate minimizers of smooth unconstrained functions whose values and derivatives are subject to random noise. It is shown that, under suitable probabilistic assumptions, the new method finds (in expectation) an epsilon-approximate minimizer of arbitrary order q > 0 in at most O(epsilon^{-(q+1)}) inexact evaluations of the function and its derivatives, providing the first such result for general optimality orders. The impact of intrinsic noise limiting the validity of the assumptions is also discussed and it is shown that difficulties are unlikely to occur in the first-order version of the algorithm for sufficiently large gradients. Conversely, should these assumptions fail for specific realizations, then ``degraded'' optimality guarantees are shown to hold when failure occurs. These conclusions are then discussed and illustrated in the context of subsampling methods for finite-sum optimization.

Keywords: evaluation complexity, trust-region methods, inexact functions and derivatives, probabilistic analysis, finite-sum optimization, subsampling methods

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Category 2: Nonlinear Optimization (Nonlinear Systems and Least-Squares )


Download: [PDF]

Entry Submitted: 12/12/2021
Entry Accepted: 12/12/2021
Entry Last Modified: 12/12/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society