Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization

Abstract

As application demands for zeroth-order (gradient-free) optimization accelerate, the need for variance reduced and faster converging approaches is also intensifying. This paper addresses these challenges by presenting: a) a comprehensive theoretical analysis of variance reduced zeroth-order (ZO) optimization, b) a novel variance reduced ZO algorithm, called ZO-SVRG, and c) an experimental evaluation of our approach in the context of two compelling applications, black-box chemical material classification and generation of adversarial examples from black-box deep neural network models. Our theoretical analysis uncovers an essential difficulty in the analysis of ZO-SVRG: the unbiased assumption on gradient estimates no longer holds. We prove that compared to its first-order counterpart, ZO-SVRG with a two-point random gradient estimator could suffer an additional error of order $O(1/b)$, where $b$ is the mini-batch size. To mitigate this error, we propose two accelerated versions of ZO-SVRG utilizing variance reduced gradient estimators, which achieve the best rate known for ZO stochastic optimization (in terms of iterations). Our extensive experimental results show that our approaches outperform other state-of-the-art ZO algorithms, and strike a balance between the convergence rate and the function query complexity.

Cited by in corpus (35)

• HopSkipJumpAttack: A Query-Efficient Decision-Based Attack
• Gradientless Descent: High-Dimensional Zeroth-Order Optimization
• Daedalus: Breaking Non-Maximum Suppression in Object Detection via Adversarial Examples
• Sign-OPT: A Query-Efficient Hard-label Adversarial Attack
• Hessian-Aware Zeroth-Order Optimization for Black-Box Adversarial Attack
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning
• Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
• On the Convergence of SGD with Biased Gradients
• Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization
• An ADMM Based Framework for AutoML Pipeline Configuration
• Adaptive First-and Zeroth-order Methods for Weakly Convex Stochastic Optimization Problems
• Stochastic Subspace Descent
• Efficiently avoiding saddle points with zero order methods: No gradients required
• Learning to Learn by Zeroth-Order Oracle
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity
• Don't Forget to Sign the Gradients!
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework
• Bilevel Optimization for Machine Learning: Algorithm Design and Convergence Analysis
• Man-in-the-Middle Attacks against Machine Learning Classifiers via Malicious Generative Models
• Distributed Zeroth-Order Stochastic Optimization in Time-varying Networks
• A Hybrid-Order Distributed SGD Method for Non-Convex Optimization to Balance Communication Overhead, Computational Complexity, and Convergence Rate
• A Hard Label Black-box Adversarial Attack Against Graph Neural Networks
• Is Ordered Weighted ${\ell }_1$ Regularized Regression Robust to Adversarial Perturbation? A Case Study on OSCAR
• Towards an Efficient and General Framework of Robust Training for Graph Neural Networks
• Distributed Derivative-free Learning Method for Stochastic Optimization over a Network with Sparse Activity
• Learning Sampling Policy for Faster Derivative Free Optimization
• Zeroth-order optimisation on subsets of symmetric matrices with application to MPC tuning
• Statistical Inference for Polyak-Ruppert Averaged Zeroth-order Stochastic Gradient Algorithm
• Sparse Perturbations for Improved Convergence in Stochastic Zeroth-Order Optimization
• Universal Decision-Based Black-Box Perturbations: Breaking Security-Through-Obscurity Defenses
• Adaptive Weight Decay for Deep Neural Networks
• Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order Coordinate Method
• An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization
• Zeroth-Order Stochastic Alternating Direction Method of Multipliers for Nonconvex Nonsmooth Optimization