math.OC
Linearly Convergent Gradient Free Methods for Minimization of Parabolic Approximation. 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 log left( frac 1 varepsilon right) 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.