Timezone: »

 
Oral
Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization
Kaiyi Ji · Zhe Wang · Yi Zhou · Yingbin LIANG

Tue Jun 11 11:20 AM -- 11:25 AM (PDT) @ Room 104
in Non-convex Optimization »
Two types of zeroth-order stochastic algorithms have recently been designed for nonconvex optimization respectively based on the first-order techniques SVRG and SARAH/SPIDER. This paper addresses several important issues that are still open in these methods. First, all existing SVRG-type zeroth-order algorithms suffer from worse function query complexities than either zeroth-order gradient descent (ZO-GD) or stochastic gradient descent (ZO-SGD). In this paper, we propose a new algorithm ZO-SVRG-Coord-Rand and develop a new analysis for an existing ZO-SVRG-Coord algorithm proposed in Liu et al. 2018b, and show that both ZO-SVRG-Coord-Rand and ZO-SVRG-Coord (under our new analysis) outperform other exiting SVRG-type zeroth-order methods as well as ZO-GD and ZO-SGD. Second, the existing SPIDER-type algorithm SPIDER-SZO (Fang et al., 2018) has superior theoretical performance, but suffers from the generation of a large number of Gaussian random variables as well as a $\sqrt{\epsilon}$-level stepsize in practice. In this paper, we develop a new algorithm ZO-SPIDER-Coord, which is free from Gaussian variable generation and allows a large constant stepsize while maintaining the same convergence rate and query complexity, and we further show that ZO-SPIDER-Coord automatically achieves a linear convergence rate as the iterate enters into a local PL region without restart and algorithmic modification.
[ Slides]  [ Video] 

Author Information

Kaiyi Ji (The Ohio State University)
Zhe Wang (Ohio State University)
Yi Zhou (Duke University)
Yingbin LIANG (The Ohio State University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors