Sparse Perturbations for Improved Convergence in Stochastic Zeroth-Order Optimization
arXiv:2006.01759
Abstract
Interest in stochastic zeroth-order (SZO) methods has recently been revived in black-box optimization scenarios such as adversarial black-box attacks to deep neural networks. SZO methods only require the ability to evaluate the objective function at random input points, however, their weakness is the dependency of their convergence speed on the dimensionality of the function to be evaluated. We present a sparse SZO optimization method that reduces this factor to the expected dimensionality of the random perturbation during learning. We give a proof that justifies this reduction for sparse SZO optimization for non-convex functions without making any assumptions on sparsity of objective function or gradient. Furthermore, we present experimental results for neural networks on MNIST and CIFAR that show faster convergence in training loss and test accuracy, and a smaller distance of the gradient approximation to the true gradient in sparse SZO compared to dense SZO.
arXiv commentInternational Conference on Machine Learning, Optimization, and Data Science (LOD), Siena, Italy
References in corpus (11)
- Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
- 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
- Improving Black-box Adversarial Attacks with a Transfer-based Prior
- Simple random search provides a competitive approach to reinforcement learning
- An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
- Stabilizing the Lottery Ticket Hypothesis
- Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
- Stochastic Zeroth-order Optimization in High Dimensions
- Gradient-free Policy Architecture Search and Adaptation
- Sparse Stochastic Zeroth-Order Optimization with an Application to Bandit Structured Prediction