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

Stefania Bellavia, Gianmarco Gurioli, Benedetta Morini, Philippe L. Toint

    Research output: Contribution in Book/Catalog/Report/Conference proceedingConference contribution

    Abstract

    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.

    Original languageEnglish
    Title of host publicationProceedings - 2021 21st International Conference on Computational Science and Its Applications, ICCSA 2021
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages258-267
    Number of pages10
    ISBN (Electronic)9781665458436
    DOIs
    Publication statusPublished - 2021
    Event21st International Conference on Computational Science and Its Applications, ICCSA 2021 - Cagliari, Italy
    Duration: 13 Sept 202116 Sept 2021

    Publication series

    NameProceedings - 2021 21st International Conference on Computational Science and Its Applications, ICCSA 2021

    Conference

    Conference21st International Conference on Computational Science and Its Applications, ICCSA 2021
    Country/TerritoryItaly
    CityCagliari
    Period13/09/2116/09/21

    Keywords

    • evaluation complexity
    • inexact functions and derivatives
    • regularization methods
    • stochastic analysis

    Fingerprint

    Dive into the research topics of 'Quadratic and Cubic Regularisation Methods with Inexact function and Random Derivatives for Finite-Sum Minimisation'. Together they form a unique fingerprint.

    Cite this