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.

本文介绍了两种零阶随机算法的优化和改进，其中一种通过新的 ZO-SVRG-Coord-Rand 算法和分析结果发现，比现有的同类算法以及 ZO-GD 和 ZO-SGD 更为优秀，另一种通过新的 ZO-SPIDER-Coord 算法有效降低了 Gaussian 随机变量的数量和步长的级别以实现相同的收敛速度和查询复杂度，并且自动实现了线性收敛率。