Variance reduction methods which use a mixture of large and small batch gradients, such as SVRG (Johnson & Zhang, 2013) and SpiderBoost (Wang et al., 2018), require significantly more computational resources per update than SGD (Robbins & Monro, 1951). We reduce the computational cost per update of variance reduction methods by introducing a sparse gradient operator blending the top-K operator (Stich et al., 2018; Aji & Heafield, 2017) and the randomized coordinate descent operator. While the computational cost of computing the derivative of a model parameter is constant, we make the observation that the gains in variance reduction are proportional to the magnitude of the derivative. In this paper, we show that a sparse gradient based on the magnitude of past gradients reduces the computational cost of model updates without a significant loss in variance reduction. Theoretically, our algorithm is at least as good as the best available algorithm (e.g. SpiderBoost) under appropriate settings of parameters and can be much more efficient if our algorithm succeeds in capturing the sparsity of the gradients. Empirically, our algorithm consistently outperforms SpiderBoost using various models to solve various image classification tasks. 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. Optimization tools for machine learning applications seek to minimize the finite sum objective where x is a vector of parameters, and f i : R d → R is the loss associated with sample i. Batch SGD serves as the prototype for modern stochastic gradient methods. It updates the iterate x with x − η∇f I (x), where η is the learning rate and f I (x) is the batch stochastic gradient, i.e. ∇f I (x) = 1 |I| i∈I ∇f i (x). The batch size |I| in batch SGD directly impacts the stochastic variance and gradient query complexity of each iteration of the update rule. Lower variance improves convergence rate without any changes to learning rate, but the step-size in the convergence analysis of SGD decreases with variance (Robbins & Monro, 1951) , which suggests that learning rates can be increased when stochastic variance is decreased to further improve the convergence rate of gradient-based machine learning optimization algorithms. This is generally observed behavior in practice (Smith et al., 2018; Hoffer et al., 2017) . In recent years, new variance reduction techniques have been proposed by carefully blending large and small batch gradients (e.g. Roux et al., 2012; Johnson & Zhang, 2013; Defazio et al., 2014; Xiao & Zhang, 2014; Allen-Zhu & Yuan, 2016; Allen-Zhu & Hazan, 2016; Reddi et al., 2016a; b; Allen-Zhu, 2017; Lei & Jordan, 2017; Lei et al., 2017; Allen-Zhu, 2018b; Fang et al., 2018; Zhou et al., 2018; Wang et al., 2018; Pham et al., 2019; Nguyen et al., 2019; Lei & Jordan, 2019) . They are alternatives to batch SGD and are provably better than SGD in various settings. While these methods allow for greater learning rates than batch SGD and have appealing theoretical guarantees, they require a per-iteration query complexity which is more than double than that of batch SGD. This 1. We introduce a novel way to reduce the computational complexity of SVRG-style variance reduction methods using gradient sparsity estimates. Concretely, we define an algorithm which applies these ideas to SpiderBoost (Wang et al., 2018) . 2. We provide a complete theoretical complexity analysis of our algorithm, which shows algorithmic improvements in the presence of gradient sparsity structure. 3. We experimentally show the presence of sparsity structure for some deep neural networks, which is an important assumption of our algorithm. Our experiments show that, for those deep neural networks, sparse gradients improve the empirical convergence rate by reducing both variance and computational complexity. 4. We include additional experiments on natural language processing and sparse matrix factorization, and compare our algorithms to two different SGD baselines. These experiments demonstrate different ways in which variance reduction methods can be adapted to obtain competitive performance on challenging optimization tasks. The rest of the paper is organized as follows. We begin by providing a sparse variance reduction algorithm based on a combination of SCSG (Lei et al., 2017) and SpiderBoost (Wang et al., 2018) . We then explain how to perform sparse back-propagation in order to realize the benefits of sparsity. We prove both that our algorithm is as good as SpiderBoost, and under reasonable assumptions, has better complexity than SpiderBoost. Finally, we present our experimental results which include an empirical analysis of the sparsity of various image classification problems, and a comparison between our algorithm and SpiderBoost. In this paper, we show how sparse gradients with memory can be used to improve the gradient query complexity of SVRG-type variance reduction algorithms. While we provide a concrete sparse variance reduction algorithm for SpiderBoost, the techniques developed in this paper can be adapted to other variance reduction algorithms. We show that our algorithm provides a way to explicitly control the gradient query complexity of variance reduction methods, a problem which has thus far not been explicitly addressed. Assuming our algorithm captures the sparsity structure of the optimization problem, we also prove that the complexity of our algorithm is an improvement over SpiderBoost. The results of our comparison to SpiderBoost validates this assumption, and our entropy experiment empirically supports the hypothesis that gradient sparsity does exist. The results of our entropy experiment also support the results in Aji & Heafield (2017) , which show that the top k operator generally outperforms the random k operator. Not every problem we tested exhibited sparsity structure. While this is true, our analysis proves that our algorithm performs no worse than SpiderBoost in these settings. Even when there is no structure, our algorithm reduces to a random sampling of k 1 + k 2 coordinates. The results of our experiments on natural language processing and matrix factorization demonstrate that, with extra engineering effort, variance reduction methods can be competitive with SGD baselines. While we view this as progress toward improving the practical viability of variance reduction algorithms, we believe further improvements can be made, such as better utilization of reduced variance during training, and better control over increased variance in very high dimensional models such as dense net (Defazio, 2019) . We recognize these issues and hope to make progress on them in future work. A TECHNICAL PROOFS
We use sparsity to improve the computational complexity of variance reduction methods.
{"src": "scitldr-AIC_train", "paper_id": "Syx1DkSYwB"}