Quadratic and Cubic Regularisation Methods with Inexact function and Random Derivatives for Finite-Sum Minimisation

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 ${\mathcal{O}}\left( { \in _1^{ - 2}} \right){\text{ or }}{\mathcal{O}}\left( { \in _1^{ - 3/2}} \right)$ when searching for a first-order critical point using a second or third order model, respectively, and of ${\mathcal{O}}\left( {\max \left[ { \in _1^{ - 3/2}, \in _2^{ - 3}} \right]} \right)$ when seeking for second-order critical points with a third order model, in which ${ \in _j},j \in \{ 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.