We consider the problem of global optimization of an unknown non-convex\nsmooth function with zeroth-order feedback. In this setup, an algorithm is\nallowed to adaptively query the underlying function at different locations and\nreceives noisy evaluations of function values at the queried points (i.e. the\nalgorithm has access to zeroth-order information). Optimization performance is\nevaluated by the expected difference of function values at the estimated\noptimum and the true optimum. In contrast to the classical optimization setup,\nfirst-order information like gradients are not directly accessible to the\noptimization algorithm. We show that the classical minimax framework of\nanalysis, which roughly characterizes the worst-case query complexity of an\noptimization algorithm in this setting, leads to excessively pessimistic\nresults. We propose a local minimax framework to study the fundamental\ndifficulty of optimizing smooth functions with adaptive function evaluations,\nwhich provides a refined picture of the intrinsic difficulty of zeroth-order\noptimization. We show that for functions with fast level set growth around the\nglobal minimum, carefully designed optimization algorithms can identify a near\nglobal minimizer with many fewer queries. For the special case of strongly\nconvex and smooth functions, our implied convergence rates match the ones\ndeveloped for zeroth-order convex optimization problems. At the other end of\nthe spectrum, for worst-case smooth functions no algorithm can converge faster\nthan the minimax rate of estimating the entire unknown function in the\n$\\ell_\\infty$-norm. We provide an intuitive and efficient algorithm that\nattains the derived upper error bounds.\n