  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.
