Stochastic Zeroth-order Optimization via Variance Reduction method
This work addresses the high variance and poor convergence rates in derivative-free optimization, which is crucial for machine learning applications like black-box attacks, though it appears incremental as it builds on existing variance reduction techniques.
The paper tackles the problem of derivative-free optimization for black-box models by introducing a novel stochastic zeroth-order method with variance reduction (SZVR-G), which achieves sublinear complexity relative to dimension d and outperforms existing methods in both smooth and non-smooth cases, as demonstrated in experiments including a black-box attack on deep neural networks.
Derivative-free optimization has become an important technique used in machine learning for optimizing black-box models. To conduct updates without explicitly computing gradient, most current approaches iteratively sample a random search direction from Gaussian distribution and compute the estimated gradient along that direction. However, due to the variance in the search direction, the convergence rates and query complexities of existing methods suffer from a factor of $d$, where $d$ is the problem dimension. In this paper, we introduce a novel Stochastic Zeroth-order method with Variance Reduction under Gaussian smoothing (SZVR-G) and establish the complexity for optimizing non-convex problems. With variance reduction on both sample space and search space, the complexity of our algorithm is sublinear to $d$ and is strictly better than current approaches, in both smooth and non-smooth cases. Moreover, we extend the proposed method to the mini-batch version. Our experimental results demonstrate the superior performance of the proposed method over existing derivative-free optimization techniques. Furthermore, we successfully apply our method to conduct a universal black-box attack to deep neural networks and present some interesting results.