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.