Gradientless Descent: High-Dimensional Zeroth-Order Optimization

Abstract

Zeroth-order optimization is the process of minimizing an objective $f(x)$, given oracle access to evaluations at adaptively chosen inputs $x$. In this paper, we present two simple yet powerful GradientLess Descent (GLD) algorithms that do not rely on an underlying gradient estimate and are numerically stable. We analyze our algorithm from a novel geometric perspective and present a novel analysis that shows convergence within an $\epsilon$-ball of the optimum in $O(kQ\log (n)\log (R/\epsilon ))$ evaluations, for any monotone transform of a smooth and strongly convex objective with latent dimension $k<n$, where the input dimension is $n$, $R$ is the diameter of the input space and $Q$ is the condition number. Our rates are the first of its kind to be both 1) poly-logarithmically dependent on dimensionality and 2) 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 BBOB and MuJoCo benchmarks.

arXiv comment11 main pages, 26 total pages

References in corpus (11)

• Practical Bayesian Optimization of Machine Learning Algorithms
• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Evolution Strategies as a Scalable Alternative to Reinforcement Learning
• Simple random search provides a competitive approach to reinforcement learning
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• Adaptive Bound Optimization for Online Convex Optimization
• Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
• Structured Evolution with Compact Architectures for Scalable Policy Optimization
• Hyperparameter Optimization: A Spectral Approach
• Zeroth-Order Online Alternating Direction Method of Multipliers: Convergence Analysis and Applications
• A Stochastic Derivative Free Optimization Method with Momentum

Cited by in corpus (13)

• Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
• Rapidly Adaptable Legged Robots via Evolutionary Meta-Learning
• A One-bit, Comparison-Based Gradient Estimator
• A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization
• ZARTS: On Zero-order Optimization for Neural Architecture Search
• Continuum-Armed Bandits: A Function Space Perspective
• Zeroth-Order Supervised Policy Improvement
• On the Convergence of Prior-Guided Zeroth-Order Optimization Algorithms
• Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm
• Small errors in random zeroth-order optimization are imaginary
• ES-ENAS: Efficient Evolutionary Optimization for Large Hybrid Search Spaces
• On the Second-order Convergence Properties of Random Search Methods
• Approximately Exact Line Search