Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
Sijia Liu, Bhavya Kailkhura, Pin‐Yu Chen, Paishun Ting, Shiyu Chang, Lisa D. Amini · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 2018
As application demands for zeroth-order (gradient-free) optimization accelerates, 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 two point random gradient estimator suffers an additional error of order O(1/b) where b the mini-batch size.To mitigate this error, we propose two accelerated versions of ZO-SVRG utilizing reduced variance 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 zeroth-order algorithms, and strike a balance between the convergence rate and the function query complexity.