Gradientless Descent: High-Dimensional Zeroth-Order Optimization
Zeroth-order optimization is the process of minimizing an objective, given oracle access to evaluations at adaptively chosen inputs.In this paper, we present two simple yet powerful GradientLess Descent algorithms that do not rely on an underlying gradient estimate and are numerically stable.We analyze our algorithm from a novel geometric perspective and we show that for of a smooth and strongly convex objective with latent dimension, we present a novel analysis that shows convergence within an-ball of the optimum in evaluations, where the input dimension is, is the diameter of the input space and is the condition number.Our rates are the first of its kind to be both1) poly-logarithmically dependent on dimensionality and2) invariant under monotone transformations.We further leverage our geometric perspective to show that our analysis is optimal.Both monotone invariance and its ability to utilize a low latent dimensionality are key to the empirical success of our algorithms, as demonstrated on synthetic and MuJoCo benchmarks.
Gradientless Descent is a provably efficient gradient-free algorithm that is monotone-invariant and fast for high-dimensional zero-th order optimization.This paper proposes stable GradientLess Descent (GLD) algorithms that do not rely on gradient estimate.