Stochastic Zeroth-order Optimization in High Dimensions

Abstract

We consider the problem of optimizing a high-dimensional convex function using stochastic zeroth-order queries. Under sparsity assumptions on the gradients or function values, we present two algorithms: a successive component/feature selection algorithm and a noisy mirror descent algorithm using Lasso gradient estimates, and show that both algorithms have convergence rates that de- pend only logarithmically on the ambient dimension of the problem. Empirical results confirm our theoretical findings and show that the algorithms we design outperform classical zeroth-order optimization methods in the high-dimensional setting.

Camera-ready version at AISTATS 2018

References in corpus (2)

• Practical Bayesian Optimization of Machine Learning Algorithms
• Stochastic Zeroth-order Optimization in High Dimensions

Cited by in corpus (21)

• Stochastic Zeroth-order Optimization in High Dimensions
• Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling
• AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits
• Stochastic Zeroth-order Optimization via Variance Reduction method
• Zero-Shot Knowledge Distillation from a Decision-Based Black-Box Model
• A One-bit, Comparison-Based Gradient Estimator
• Boosting One-Point Derivative-Free Online Optimization via Residual Feedback
• Multi-Point Bandit Algorithms for Nonstationary Online Nonconvex Optimization
• A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization
• A New One-Point Residual-Feedback Oracle For Black-Box Learning and Control
• Black Box Submodular Maximization: Discrete and Continuous Settings
• Spanning Attack: Reinforce Black-box Attacks with Unlabeled Data
• Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods
• Continuum-Armed Bandits: A Function Space Perspective
• Zeroth-Order Supervised Policy Improvement
• Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm
• Sparse Perturbations for Improved Convergence in Stochastic Zeroth-Order Optimization
• The Influence of Shape Constraints on the Thresholding Bandit Problem
• A Dimension-Insensitive Algorithm for Stochastic Zeroth-Order Optimization
• Scalable Projection-Free Optimization