TY - GEN
T1 - Quadratic and Cubic Regularisation Methods with Inexact function and Random Derivatives for Finite-Sum Minimisation
AU - Bellavia, Stefania
AU - Gurioli, Gianmarco
AU - Morini, Benedetta
AU - Toint, Philippe L.
N1 - Publisher Copyright:
© 2021 IEEE.
PY - 2021
Y1 - 2021
N2 - This paper focuses on regularisation methods using models up to the third order to search for up to second-order critical points of a finite-sum minimisation problem. The variant presented belongs to the framework of [1]: it employs random models with accuracy guaranteed with a sufficiently large prefixed probability and deterministic inexact function evaluations within a prescribed level of accuracy. Without assuming unbiased estimators, the expected number of iterations is O( _1^ - 2 ) or O( _1^ - 3/2 ) when searching for a first-order critical point using a second or third order model, respectively, and of O( max [ _1^ - 3/2, _2^ - 3 ] ) when seeking for second-order critical points with a third order model, in which _j,j 1,2, is the j th-order tolerance. These results match the worst-case optimal complexity for the deterministic counterpart of the method. Preliminary numerical tests for first-order optimality in the context of nonconvex binary classification in imaging, with and without Artifical Neural Networks (ANNs), are presented and discussed.
AB - This paper focuses on regularisation methods using models up to the third order to search for up to second-order critical points of a finite-sum minimisation problem. The variant presented belongs to the framework of [1]: it employs random models with accuracy guaranteed with a sufficiently large prefixed probability and deterministic inexact function evaluations within a prescribed level of accuracy. Without assuming unbiased estimators, the expected number of iterations is O( _1^ - 2 ) or O( _1^ - 3/2 ) when searching for a first-order critical point using a second or third order model, respectively, and of O( max [ _1^ - 3/2, _2^ - 3 ] ) when seeking for second-order critical points with a third order model, in which _j,j 1,2, is the j th-order tolerance. These results match the worst-case optimal complexity for the deterministic counterpart of the method. Preliminary numerical tests for first-order optimality in the context of nonconvex binary classification in imaging, with and without Artifical Neural Networks (ANNs), are presented and discussed.
KW - evaluation complexity
KW - inexact functions and derivatives
KW - regularization methods
KW - stochastic analysis
UR - http://www.scopus.com/inward/record.url?scp=85127405353&partnerID=8YFLogxK
U2 - 10.1109/ICCSA54496.2021.00043
DO - 10.1109/ICCSA54496.2021.00043
M3 - Conference contribution
AN - SCOPUS:85127405353
T3 - Proceedings - 2021 21st International Conference on Computational Science and Its Applications, ICCSA 2021
SP - 258
EP - 267
BT - Proceedings - 2021 21st International Conference on Computational Science and Its Applications, ICCSA 2021
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 21st International Conference on Computational Science and Its Applications, ICCSA 2021
Y2 - 13 September 2021 through 16 September 2021
ER -