Bellavia S., Gurioli G., Morini B., Toint Ph. L.
Modeling and Simulation 65K05 Management Science and Operations Research Computational Mathematics Control and Optimization FOS: Mathematics 90C26 G.1.6 65C50 Trust-region methods Evaluation complexity Probabilistic analysis Subsampling methods Inexact functions and derivatives Finite-sum optimization Optimization and Control (math.OC) Mathematics - Optimization and Control F.2.1
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 >= 1 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. (C) 2022 The Author(s). Published by Elsevier Ltd on behalf of Association of European Operational Research Societies (EURO).
Source: EURO journal on computational optimization (Print) 10 (2022). doi:10.1016/j.ejco.2022.100043
Publisher: Springer, Heidelberg, Germania
@article{oai:it.cnr:prodotti:476983, title = {Trust-region algorithms: probabilistic complexity and intrinsic noise with applications to subsampling techniques}, author = {Bellavia S. and Gurioli G. and Morini B. and Toint Ph. L.}, publisher = {Springer, Heidelberg, Germania}, doi = {10.1016/j.ejco.2022.100043 and 10.48550/arxiv.2112.06176}, journal = {EURO journal on computational optimization (Print)}, volume = {10}, year = {2022} }