TY - JOUR
T1 - Trust-region algorithms
T2 - Probabilistic complexity and intrinsic noise with applications to subsampling techniques
AU - Bellavia, S.
AU - Gurioli, G.
AU - Morini, B.
AU - Toint, Ph L.
N1 - Publisher Copyright:
© 2022 The Author(s)
PY - 2022/1
Y1 - 2022/1
N2 - 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 ϵ-approximate minimizer of arbitrary order q≥1 in at most O(ϵ−(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.
AB - 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 ϵ-approximate minimizer of arbitrary order q≥1 in at most O(ϵ−(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.
KW - Evaluation complexity
KW - Finite-sum optimization
KW - Inexact functions and derivatives
KW - Probabilistic analysis
KW - Subsampling methods
KW - Trust-region methods
UR - http://www.scopus.com/inward/record.url?scp=85140252127&partnerID=8YFLogxK
U2 - 10.1016/j.ejco.2022.100043
DO - 10.1016/j.ejco.2022.100043
M3 - Article
AN - SCOPUS:85140252127
SN - 2192-4406
VL - 10
JO - EURO Journal on Computational Optimization
JF - EURO Journal on Computational Optimization
M1 - 100043
ER -