Optimization of Smooth Functions with Noisy Observations: Local Minimax
  Rates
  We consider the problem of global optimization of an unknown non-convex
smooth function with zeroth-order feedback. In this setup, an algorithm is
allowed to adaptively query the underlying function at different locations and
receives noisy evaluations of function values at the queried points (i.e. the
algorithm has access to zeroth-order information). Optimization performance is
evaluated by the expected difference of function values at the estimated
optimum and the true optimum. In contrast to the classical optimization setup,
first-order information like gradients are not directly accessible to the
optimization algorithm. We show that the classical minimax framework of
analysis, which roughly characterizes the worst-case query complexity of an
optimization algorithm in this setting, leads to excessively pessimistic
results. We propose a local minimax framework to study the fundamental
difficulty of optimizing smooth functions with adaptive function evaluations,
which provides a refined picture of the intrinsic difficulty of zeroth-order
optimization. We show that for functions with fast level set growth around the
global minimum, carefully designed optimization algorithms can identify a near
global minimizer with many fewer queries. For the special case of strongly
convex and smooth functions, our implied convergence rates match the ones
developed for zeroth-order convex optimization problems. At the other end of
the spectrum, for worst-case smooth functions no algorithm can converge faster
than the minimax rate of estimating the entire unknown function in the
$\ell_\infty$-norm. We provide an intuitive and efficient algorithm that
attains the derived upper error bounds.
