Timezone: »

 
Poster
Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
Sijia Liu · Bhavya Kailkhura · Pin-Yu Chen · Paishun Ting · Shiyu Chang · Lisa Amini

Wed Dec 05 02:00 PM -- 04:00 PM (PST) @ Room 210 #51
in Wed Poster Session B »
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.
Keywords: Optimization · Non-Convex Optimization

Author Information

Sijia Liu (MIT-IBM Watson AI Lab, IBM Research AI)

Sijia Liu received the Ph.D. degree in electrical engineering from Syracuse University in 2016. From 2016 to 2017, he was a postdoctoral research fellow in Department of Electrical and Computer Engineering, University of Michigan, Ann Arbor, MI. He is currently a research staff member in IBM Research, MIT-IBM Watson AI Lab. His research interests include machine learning algorithms and statistical signal processing.

Bhavya Kailkhura (Lawrence Livermore National Lab)
Pin-Yu Chen (IBM Research AI)
Paishun Ting (University of Michigan)
Shiyu Chang (IBM T.J. Watson Research Center)
Lisa Amini (IBM Research)

More from the Same Authors