Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework
arXiv:2012.11518
Abstract
In this work, we focus on the study of stochastic zeroth-order (ZO) optimization which does not require first-order gradient information and uses only function evaluations. The problem of ZO optimization has emerged in many recent machine learning applications, where the gradient of the objective function is either unavailable or difficult to compute. In such cases, we can approximate the full gradients or stochastic gradients through function value based gradient estimates. Here, we propose a novel hybrid gradient estimator (HGE), which takes advantage of the query-efficiency of random gradient estimates as well as the variance-reduction of coordinate-wise gradient estimates. We show that with a graceful design in coordinate importance sampling, the proposed HGE-based ZO optimization method is efficient both in terms of iteration complexity as well as function query cost. We provide a thorough theoretical analysis of the convergence of our proposed method for non-convex, convex, and strongly-convex optimization. We show that the convergence rate that we derive generalizes the results for some prominent existing methods in the nonconvex case, and matches the optimal result in the convex case. We also corroborate the theory with a real-world black-box attack generation application to demonstrate the empirical advantage of our method over state-of-the-art ZO optimization approaches.
arXiv comment27 pages, 3 figures
References in corpus (11)
- ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
- Black-box Adversarial Attacks with Limited Queries and Information
- Sparsified SGD with Memory
- An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
- Structured Adversarial Attack: Towards General Implementation and Better Interpretability
- Query-Efficient Hard-label Black-box Attack:An Optimization-based Approach
- Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
- A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order
- ZO-AdaMM: Zeroth-Order Adaptive Momentum Method for Black-Box Optimization
- A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning
- Asynchronous Stochastic Block Coordinate Descent with Variance Reduction