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

     S. Bellavia,  G. Gurioli, B. Morini and  Ph. L. Toint

                    November 2021

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.