Variance reduction methods such as SVRG and SpiderBoost use a mixture of
large and small batch gradients to reduce the variance of stochastic gradients.
Compared to SGD, these methods require at least double the number of operations
per update to model parameters. To reduce the computational cost of these
methods, we introduce a new sparsity operator: The random-top-k operator. Our
operator reduces computational complexity by estimating gradient sparsity
exhibited in a variety of applications by combining the top-k operator and the
randomized coordinate descent operator. With this operator, large batch
gradients offer an extra benefit beyond variance reduction: A reliable estimate
of gradient sparsity. Theoretically, our algorithm is at least as good as the
best algorithm (SpiderBoost), and further excels in performance whenever the
random-top-k operator captures gradient sparsity. Empirically, our algorithm
consistently outperforms SpiderBoost using various models on various tasks
including image classification, natural language processing, and sparse matrix
factorization. We also provide empirical evidence to support the intuition
behind our algorithm via a simple gradient entropy computation, which serves to
quantify gradient sparsity at every iteration.

本文提出了一种新的稀疏操作符：随机 Top-k 操作符，用于估计梯度稀疏性，将其与随机化坐标下降操作符结合，可降低 SVRG 和 SpiderBoost 方法的计算复杂度。实验证明该方法在各种模型和任务中的表现优于 SpiderBoost。

稀疏梯度的方差减少

Variance Reduction with Sparse Gradients

SARAH and SPIDER are two recently developed stochastic variance-reduced
algorithms, and SPIDER has been shown to achieve a near-optimal first-order
oracle complexity in smooth nonconvex optimization. However, SPIDER uses an
accuracy-dependent stepsize that slows down the convergence in practice, and
cannot handle objective functions that involve nonsmooth regularizers. In this
paper, we propose SpiderBoost as an improved scheme, which allows to use a much
larger constant-level stepsize while maintaining the same near-optimal oracle
complexity, and can be extended with proximal mapping to handle composite
optimization (which is nonsmooth and nonconvex) with provable convergence
guarantee. In particular, we show that proximal SpiderBoost achieves an oracle
complexity of $\mathcal{O}(\min\{n^{1/2}\epsilon^{-2},\epsilon^{-3}\})$ in
composite nonconvex optimization, improving the state-of-the-art result by a
factor of $\mathcal{O}(\min\{n^{1/6},\epsilon^{-1/3}\})$. We further develop a
novel momentum scheme to accelerate SpiderBoost for composite optimization,
which achieves the near-optimal oracle complexity in theory and substantial
improvement in experiments.

本文提出了 SpiderBoost 算法，扩展了 SPIDER 并克服了其在实践中收敛速度慢以及处理涉及非光滑正则化器的目标函数的缺点，可以通过使用 Proximal Mapping 处理复合优化，并利用动量方案实现了理论上的近乎最优巨大 Oracle 复杂度和实验结果的实质性改善。