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

03/30/2021
by   Stefania Bellavia, et al.
0

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 [3]: 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 𝒪(ϵ_1^-2) or 𝒪(ϵ_1^-3/2) when searching for a first-order critical point using a second or third order model, respectively, and of 𝒪(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 jth-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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset