Gradientless Descent: High-Dimensional Zeroth-Order Optimization

  • 2019-11-14 18:58:13
  • Daniel Golovin, John Karro, Greg Kochanski, Chansoo Lee, Xingyou Song, Qiuyi, Zhang
  • 10

Abstract

Zeroth-order optimization is the process of minimizing an objective $f(x)$,given oracle access to evaluations at adaptively chosen inputs $x$. In thispaper, we present two simple yet powerful GradientLess Descent (GLD) algorithmsthat do not rely on an underlying gradient estimate and are numerically stable.We analyze our algorithm from a novel geometric perspective and present a novelanalysis that shows convergence within an $\epsilon$-ball of the optimum in$O(kQ\log(n)\log(R/\epsilon))$ evaluations, for {\it any monotone transform} ofa smooth and strongly convex objective with latent dimension $k < n$, where theinput dimension is $n$, $R$ is the diameter of the input space and $Q$ is thecondition number. Our rates are the first of its kind to be both 1)poly-logarithmically dependent on dimensionality and 2) invariant undermonotone transformations. We further leverage our geometric perspective to showthat our analysis is optimal. Both monotone invariance and its ability toutilize a low latent dimensionality are key to the empirical success of ouralgorithms, as demonstrated on BBOB and MuJoCo benchmarks.

 

Quick Read (beta)

loading the full paper ...