Linearly Convergent Gradient-Free Methods for Minimization of Parabolic Approximation

DOI10.20537/2076-7633-2022-14-2-239-255MaRDI QIDQ6348835zbMATH OpenFDO

Authors Aleksandra Bazarova, Aleksandr Beznosikov, A. V. Gasnikov

Publication date 10 September 2020

Full work available at URL https://doi.org/10.20537/2076-7633-2022-14-2-239-255

Abstract: Finding the global minimum of non-convex functions is one of the main and most difficult problems in modern optimization. In the first part of the paper, we consider a certain class of "good" non-convex functions that can be bounded above and below by a parabolic function. We show that using only the zeroth-order oracle, one can obtain the linear speed $logleft(frac1varepsilonight)$ of finding the global minimum on a cube. The second part of the paper looks at the nonconvex problem in a slightly different way. We assume that minimizing the quadratic function, but at the same time we have access to a zeroth-order oracle with noise and this noise is proportional to the distance to the solution. Dealing with such noise assumptions for gradient-free methods is new in the literature. We show that here it is also possible to achieve the linear rate of convergence.

This page was built for publication: Linearly Convergent Gradient-Free Methods for Minimization of Parabolic Approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6348835)