Variance Reduction With Sparse Gradients
Authors: Melih Elibol
Lihua Lei
Michael I. Jordan
Venue:  (2020)
Keywords: optimization
variance reduction
machine learning
deep neural networks

Abstract: 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.

Published as a conference paper at ICLR 2020
VARIANCE REDUCTION WITH SPARSE GRADIENTS
Melih Elibol, Michael I. Jordan
Lihua Lei
University of California, Berkeley
Stanford University Lihualei@stanforddcc
{elibol, jordan]@cs berkeley.edu
ABSTRACT
Variance reduction methods such as SVRG (Johnson & Zhang 2013) and Spi- derBoost (Wang et al. 2018) use a mixture of large and small batch gradients to reduce the variance of stochastic gradients. Compared to SGD (Robbins & Monro I95I). these methods require 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 opera- tor reduces computational complexity by estimating gradient sparsity exhibited in variety applications by combining the top-k operator (Stich et al.) 20118] Aji & Heafield 2017) 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, as good as the best algorithm (SpiderBoost), and further excels in performance whenever the random-top-k operator captures gradient sparsity. Empirically, algorithm consistently outperforms SpiderBoost using various models on various tasks including image classification, natural language processing, and sparse ma- trix factorization. We also provide empirical evidence to support the intuition behind our algorithm via simple gradient entropy computation, which serves quantify gradient sparsity at every iteration.
algorithm is least
INTRODUCTION
Optimization tools for machine learning applications seek to minimize the finite sum objective
min f(x) a M f(x), RERd
(1)
where æ is a vector of parameters, and ft Rd + R is the loss associated with sample SGD serves as the prototype for modern stochastic gradient methods. It updates the iterate æ with I f2()), where is the learning rate and fz() is the batch stochastic gradient, i.e.
i. Batch
Vz((x) Σ V)(().
The batch size [Z] in batch SGD directly impacts the stochastic variance and gradient query com- plexity of each iteration of the update rule.
In recent years, variance reduction techniques have been proposed by carefully blending large and small batch gradients (e.g. |Rox et al. 2012: Johnson & Zhang 2013) Defazio et al. 2014: 4 Xiao & Zhang 2014 Allen
Yuan 2016 Allen-Zin & Hazan 201 6 Reddi et al. 201 b Allen -hu
2017
Lei & Jordan 2017 Lii et al. 2017]AAllen- ZZu [2018;; Fang et al. 20188 Zhou et al. 2018
Wang et al. 2018: Pham al., 2019 Nguyen et al. 2019; Lei & Jordan 2019). They are alterna-
tives 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
per-iteration query complexity which is more than double than that of batch SGD. Defazio (2019) questions the utility of variance reduction techniques in modern machine learning problems, empir- ically identifying query complexity one issue. In this paper, show that gradient sparsity (Aji & Heafield, 2017) can be used to significantly reduce the query complexity of variance reduction methods. Our work is motivated by the observation that gradients tend be "sparse," having only

---

Published as a conference paper at ICLR 2020
small fraction of large coordinates. Specifically, if the indices of large gradient coordinates (mea- sured in absolute value) are known before updating model parameters, we compute the derivative of only those coordinates while setting the remaining gradient coordinates to zero. In principle, if spar- sity is exhibited, using large gradient coordinates will not effect performance and will significantly reduce the number of operations required update model parameters. Nevertheless, this heuristic alone has three issues: (I) bias is introduced by setting other entries to zero; (2) the locations of large coordinates are typically unknown; (3) accessing subset of coordinates may not be easily implemented for some problems like deep neural networks.
We provide solutions for all three issues. First, we introduce a new sparse gradient operator: The random-top-K operator. The nooo operator is a composition of the randomized coordinate descent operator and the top-k operator. In prior work, the top-k operator has been used to reduce the communication complexity of distributed optimization (Stich et al. 2018 Aji & Heafield 2017) applications. The candom-top-k operator has two phases: Given a stochastic gradient and pair of integers (k1, k2) that sum to k, the operator retains 41 coordinates which are most "promising" in terms of their "likelihood" to be large on average, then randomly selects h2 of the remaining coordinates with appropriate rescaling. The first phase captures sparsity patterns while the second phase eliminates bias. Second, we make use of large batch gradients in variance reduction methods to estimate sparsity patterns. Inspired by the use of memory vector in Aji & Heafield (2017), the algorithm maintains a memory vector initialized with the absolute value of the large batch gra- dient at the beginning of each outer loop and updated by taking an exponential moving average over subsequent stochastic gradients. Coordinates with large values in the memory vector are more "promising," " and the random-top-- operator will pick the top L coordinate indices based on the memory vector. Since larger batch gradients have lower variance, the initial estimate is quite accu- rate. Finally, for software that supports dynamic computation graphs, we provide cost-effective way (sparse back-propagation) to implement the random-top-k operator.
In this work we apply the random-top-k operator to SpiderBoost (Wang et al., 2018), a recent vari- ance reduction method that achieves optimal query complexity, with slight modification based on the "geometrization" technique introduced by Lei & Jordan (2019). Theoretically, we show that our algorithm is never worse than SpiderBoost and can strictly outperform it when the random- top-- operator captures gradient sparsity. Empirically, we demonstrate the improvements in computa- tion for various tasks including image classification, natural language processing, and sparse matrix factorization.
The rest of the paper is organized as follows. In Section 2, define the random-top-k operator, our optimization algorithm, and a description of sparse backpropagation. The theoretical analyses presented in Section 3, followed by experimental results in Section 4. All technical proofs relegated to Appendix A, and additional experimental details can be found in Appendix B
2 STOCHASTIC VARIANCE REDUCTION WITH SPARSE GRADIENTS
Generally, variance reduction methods reduce the variance of stochastic gradients by taking a snap- shot fy()) of the gradient V f (x)) every steps of optimization, and use the gradient information in this snapshot to reduce the variance of subsequent smaller batch gradients fzz(x) (Johnson & Zhang 2013] Wang et al. 2018). Methods such as SCSG (Lei & Jordan| 2017) utilize large batch gradient, which is typically some multiple in size of the small batch gradient b. which is much more practical and is what we do in this paper. To reduce the cost of computing additional gradients, use sparsity by only computing a subset & of the total gradients d, where E Rd.
For d, k, ki, k2 E4. let k k1 + k2, where < k < d for parametric model of dimension d. In what follows, we define an operator which takes vectors I, and outputs y', where y retains only i of the entries in y. h of which are selected according to the coordinates in which have the k1 largest absolute values, and the remaining k2 entries are randomly selected from The k coordinate indices and ky coordinate indices are disjoint. Formally, the operator rtop,,,k2 Rd
Rd is defined for x; y E IRd as
yt (d) kz
if > 0 and lalle 2 (xl()) if E otherwise.
(rtops,, k2 (z. vl),)))
2

---

Published as a conference paper at ICLR 2020
where |z|| denotes vector of absolute values, (2|(1)
|x|(2) 2 ... |م| denotes the order
statistics of coordinates of x in absolute values, and denotes a random subset with size ky that is uniformly drawn from the set {e: | < [2](k;) J. For instance, if x (11, 12, 13, - 14, - -15),y
(-25, 224, 13, 12, 11) and b h2 1, then S is singleton uniformly drawn from {1, 2, 4). Suppose = {2). then rtop1,1 (z, y) = (0, 4y2, 0, O, y/) = (0, -96, 0, 11). If hy + k2 = d, rlop,, Av (x, y) = y- On the other hand, if A = O, rlopo,k, (2r, y) does not depend on x and returns rescaled random subset of y. This is the operator used in coordinate descent methods. Finally, rtopk,,ky kg (z, y) is linear in y. The following Lemma shows that rtopk, &g (r, y) is an unbiased estimator of y, which is erucial property in later analysis.
Lemma 1. Given any F, y E Rd
d - k1 12 Var (rtopk, (x,
E (rtopk (z, v)) = y.
k, (z, v)1
li2
where E is taken over the random subset S involved in the rtopk, operator and
ye if > 0 and (zlee < (2)(()))
(Lop Mop-k,l00 (,,
otherwise.
Our algorithm is detailed as below.
Algorithm 1: SpiderBoost with Sparse Gradients.
Input:
Learning rate inner loop size m, outer loop size T, large batch size B, small batch size b, initial iterate Zgg memory decay factor a, sparsity parameters 11, kg.
To ~ Uni.(11......1
with [To =
Mo | (xoo
for j = 1....,? T do
Fo == -- M = M, 1
(1)
I ~ Unif([1..... n1) with Iz = B
vo = fz, (z)))
7
N = m (for implementation) or N2 ~ geometric distribution with mean m (for theory)
for t 0, ......,, do
()) - m
x 41 = F2
I(6 Unif((n)) with | =b
10
14 = v( rtop,,, (M("), VV
(=()
(of))
11
M alv!2) + a)M(1)
12
By = N,, M, MY²
13
Output: Tou FT (for implementation) Tout Ty where T Un]f((T]) (for theory)
The algorithm includes outer-loop and an inner-loop. In the theoretical analysis, we generate N; as Geometric random variables. This trick is called "gcometrization"" proposed by Lei & Jordan (217)) and dubbed by Lei & Jordan 2019).
greatly simplifies analysis (e.g. Lei al., 2017 Allen-Zhu 2018al In practice, as observed by Lei et al. (2017), setting N, to m does not impact performance in any significant way. We only use "geometrization" in our theoretical analysis for clarity. Similarly, for our theoretical analysis, the output of our algorithm is selected uniformly at random from the set outer loop iterations. Like the use of average iterates convex optimization, this is a common technique for nonconvex optimization proposed by Nemirovski et al. (2009). In practice, we simply use the last iterate.
Similar to Aji & Heafield (017)). we maintain memory vector M..) at each iteration of our al- gorithm. The memory vector is initialized to the large batch gradient computed before every pass through the inner loop, which provides relatively accurate gradient sparsity estimate of x The exponential moving average gradually incorporates information from subsequent small batch gra- dients to account for changes to gradient sparsity. We then use M as an approximation to the variance of each gradient coordinate in rlop operator. With M,5) input, the rtop ks
3

---

Published as a conference paper at ICLR 2020
operator targets 11 high variance gradient coordinates in addition to l2 randomly selected coordi- nates.
The cost of invoking rto is dominated by the algorithm for selecting the top & coordinates, which has linear worst case complexity when using the rntelse algorithm Musser 1997).
2.1 SPARSE BACK- PROPAPROOGG
weakness of our method is the technical difficulty implementing a sparse backpropagation algorithm in modern machine learning libraries, such as Tensorflow (Abadi et al. 2015) and Pytorch (Paszke al. 2017). Models implemented in these libraries generally assume dense structured parameters. The optimal implementation of our algorithm makes use of sparse forward pass and assumes sparse computation graph upon which backpropagation is executed. Libraries that support dynamic computation graphs, such Pytorch, will construct the sparse computation graph in the forward pass, which makes the required sparse backpropagation trivial. We therefore expect our algorithm to perform quite well libraries which support dynamic computation graphs.
Consider the forward pass of a deep neural network, where & is deep composition of parametric functions,
b(1; 0) = ( ( 0
The unconstrained problem of minimizing over the 0g can be rewritten constrained optimization problem as follows:
min
loss
2
(I+1)
,3))
1=1
(L+1) = Φ2(25 (2)
s.t.
(3)
(e+1) (0(2(0)00)
2 Φ0(x;; to)
In this form, L++1 is the model estimate for data point i. Consider (z(2;0)) (xx for 1 < É < L, dr be the output layer, and a be some subdifferentiable activation function. If we apply the rtopk, operator per-layer in the forward -ass, with appropriate scaling of k1 and l to account for depth, we see that the number of multiplications artopp, Ag (v,z)² rtopk, (v, 0z)). A sparse forward-pass yields computation graph for (ki + parammeee model, and pack-propagation will compute the gradient of the objective with respect to model parameters linear time (Chauvin Rumelhart 1995).
the forward pass reduced k + by:
THEORETICAL COMPLEXITY ANALYSIS
3.1 NOTATION AND ASSUMPTIONS
Denote by || - the Euclidean norm and by A b the minimum of a and b. For random vector E _dd
Var(Y) Σ Var(Y).
We say random variable N has geometric distribution, N ~ Geom(m), if N is supported on the non-negative integers with
P(N = k) - Ak 0.1.....
for some such that EN Here allow N to be zero facilitate the analysis.
4

---

Published as a conference paper at ICLR 2020
Assumption Al on the smoothness of individual functions will be made throughout the paper.
A1 Sa is differentiable with
[V(xz) V((ii)I L||= vll,
for some oo and for all E (I,...,7..
As direct consequence of assumption 1, it holds for any x, 1/ E Rd that
L
こ || y12 S f((x) f.()) (Vf(ty), x- y) - 2 || y/1
(4)
To formulate our complexity bounds, we define
inf f(x), A ((xo) l"
Further we define x² as an upper bound on the expected norm of the stochastic gradients:
a² sup a
[Vf(2))]
(5)
By Cauchy-Schwarz inequality, it easy to see that o² is also a uniform bound of || [>x]]]
Finally, we assume that sampling an index i and accessing the pair Vf((x)) incur unit of cost and accessing the truncated version rtop,,, (m, fz()) incur (k1 + k2)/d units of cost. Note that calculating rt (m, V f=))) incurs (k) + k2) units of computational cost. Given our framework, the theoretical complexity of the algorithm is
T
Coomp (e)
2
Σ 1=1
B + 26N,
+ K2
(6)
3.2 WORST-CASE GUARANTEE
Theorem 1, Under the following setting of parameters
K2
20² 2
nT
A n
6dm
For any T T(c) & 4 40//mme?
( S e.
If we furthr set
Bd
b(ki + k:2)
the complexity to achieve the above condition is
ECComm (e) =
12
LAiV
b(ki + K2)
K2
Recall that the complexity of SpiderBoost (Wang et al. 2018 is
((
LA
Thus as long as b 0(1), K1 = Okk2), our algorithm has the same complexity as SpiderBoost under appropriate settings. The penalty term Ol O(vb(k sparsification.
b(k, + k2)/k2) is due to the information loss by
5

---

Published as a conference paper at ICLR 2020
3.3
DATA ADAPTIVE ANALYSIS
Let
(6 lopp (M V -
and
G 1 top -o (M v \1
By Cauchy-Schwarr inequality and the linearity of top ky it easy to see that 9. G. If algorithm succeeds in capturing sparsity, both ( and G will be small. In this subsection we will analyze the complexity under this case. Further define R2 as
E6 G N
R3 = B,,,, +
(7)
where E, is taken over all randomness in j-th outer loop (line 4-13 of Algorithm I
Theorem 2. Under the following setting of parameters
AAm m 3m
30
B =
An
6
For any T 2 T'e) & 6 /mme.
20
(d
k2)m
ERT.
3
hi2
where
RT Σ Rg.
Ef S 3(d-ki-ko km then
E V (Iout)l e.
If we further set
Bd
b(ki + K:2)
the complexity to achieve the above condition is
ECcomp (c) = =0 ((
ki + K2
LAIN
LA
2
d
bAm
In practice, m is usually much larger than As a result, the complexity of our algorithm is O(v(ks (k2 + k2)/d) smaller than that of SpiderBoost if our algorithm captures gradient sparsity. Al- though this type of data adaptive analyses not clean the worst-case guarantee (Theorem [ reveals the potentially superior performance of our algorithm. Similar analyses have been done for various other algorithms, including AdaGrad (Duchi al. 2011 and Adam (Kingma & Ba 2014).
4 EXPERIMENTS
In this section, we present variety of experiments to illustrate gradient sparsity and demonstrate the performance of Sparse SpiderBoost. By computing the entropy of the empirical distribution of the absolute value of stochastic gradient coordinates, we show that certain models exhibit gradient sparsity during optimization. To evaluate the performance of variance reduction with sparse gradi- ents, compute the loss over gradient queries per epoch of Sparse Spiderboost and SpiderBoost for a number of image classification problems. We also compare Sparse SpiderBoost, SpiderBoost, and SGD natural language processing task and sparse matrix factorization.
For all experiments, unless otherwise specified, we run SpiderBoost and Sparse SpiderBoost with a learning rate 1 0.1. large- batch size B 1000, small-batch size b 100, inner loop length of m = 10, memory decay factor of a = 0.5, and k and 22 both set to 5% of the total number of model parameters. We call the sum kj Az k 10% the sparsity of the optimization algorithm.

---

Published as a conference paper at ICLR 2020
4.1 GRADIENT SPARSITY AND IMAGE CLASSIFICATION
Our experiments in this section test number of image classification tasks for gradient sparsity, and plot the learning curves of some of these tasks. We test 2-layer fully connected neural network with hidden layers of width 100, a simple convolutional neural net which we describe in detail in Appendix [ and Resnet-18 18 (He al. 2015). All models use ReLu activations. For datasets, we use CIFAR- 10 (Krizhevsky et al.), SVHN (Netzer al. 2011), and MNIST (LeCun & Cortes 2010).
None our experiments include Resnet-18 on MNIST as MNIST is an easier dataset; included primarily provide variety.
Our method relies partially on the assumption that the magnitude of the derivative of some model parameters greater than others. To measure this, compute the entropy of the empirical distri- bution of the absolute value of stochastic gradient coordinates. In Algorithm T the following term updates estimate of the variance of each coordinate's derivative:
++1 alv (1- a))
Consider the entropy of the following probability vector ( = M, /I| The entropy of provides with measure of how much structure there is in our gradients. To see this, consider the hypothetical scenario where = =/dd. In this scenario we have no structure; the top ln component of our sparsity operator providing no value and entropy is maximized. On the other hand. if single entry = 1 and all other entries Pj O, then the top k1 component of our sparsity operator effectively identifying the only relevant model parameter.
To measure the potential of our sparsity operator, we compute the entropy of while running Spi- derBoost on a variety of datasets and model architectures. The results of running this experiment are summarized in the following table.
Table 1: Entropy of Memory Vectors
FC NN
Conv NN
Resnet-18
Max
Before
After
Max
Before
After
Max
Before
After
CIFAR-10
18.234
16.41
8.09
15.920
13.38
2.66
23.414
22.59
21.70
SVHN
18.234
15.36
8.05
15.920
13.00
2.97
23.414
22.62
21.31
MNIST
18.234
14.29
9.77
15.920
14.21
2.77
Table provides the maximum entropy as well as the entropy of the memory vector before and after training for 150 epochs, for each dataset and each model. For each model, the entropy at the beginning training is almost maximal. This is due to random initialization of model parameters. After 150 epochs, the entropy of M, for the convolutional model drops approximately 3, which suggests a substantial amount of gradient structure. Note that for the datasets that we tested, the gradient structure depends primarily on the model and not the dataset. In particular, for Resnet-18, the entropy appears to vary minimally after 150 epochs.
Resnet-18 trained on CIFAR-10
Convolutional NN trained on MNIST
Sparse SpiderBoost
109
SpiderBoost
10
Loss
Loss
109
Sparse SpiderBoost
SpiderBoost
10-1
6 10-1
10-1
0
10 20
Gradient Queries N
30
40
50
60
0.0
0.5
Gradient Queries NN.
1.0
1,5 2.0
Figure 1: SpiderBoost with 10% sparsity (k 0.1d) compared SpiderBoost without sparsity. Left figure compares the two algorithms using Resnet-18 on Cifar-10 10. Right figure compares the two algorithms using a convolutional neural network trained on MNIST. The x-axis measures gradient queries over N, where N is the size of the respective datasets. Plots in log-scale.
7

---

Published as a conference paper at ICLR 2020
Figure compares SpiderBoost alone to SpiderBoost with 10% sparsity (10% of parameter deriva- tives). All experiments in this section are run for 50 epochs. In our comparison to SpiderBoost, measure the number of gradient queries over the size of the dataset N. A single gradient query is taken to be the cost of computing a gradient for a single data point. i the index of a single sample, then V f(((1) (xx is single gradient query. Using the batch gradient update model parameters for a dataset of size B has a gradient query cost of B. For a model with d parameters, using a single sample update k model parameters has gradient query cost of k/d. etc.
Our results of fitting the convolutional neural network to MNIST show that sparsity provides a sig- nificant advantage compared to using SpiderBoost alone. We only show 2 epochs of this experiment since the MNIST dataset is fairly simple and convergence is rapidly achieved. The results of training Resnet- 18 on CIFAR-10 suggests that our sparsity algorithm works well on large neural networks, and non-trivial datasets. We believe Resnet-18 density we observe for Resnet- 18 in general. Sparsity here not only has the additional benefit of reducing gradient query complexity, but also provides dampening effect variance due to the additional covariates in SpiderBoost's update to model parameters. Results for the rest of these experiments can be found in Appendix
CIFAR-10 10 does not do as well due to the gradient
4.2 NATURAL LANGUAGE PROCESSING
We evaluate Sparse SpiderBoost's performance an LSTM-based (Hochreiter & Schmidhuber 1997] generative language model. We compare Sparse SpiderBoost, SpiderBoost, and SGD. We train our LSTM model on the Penn Treebank (Marcus et al. 1994) corpus. The natural language processing model consists
word embedding of dimension 128 of 1000 tokens, which is jointly learned with the task. The LSTM has hidden and cell state dimension of 1024. All three opti- mization algorithms operate on this model. The variance reduction training algorithm for this type of model can be found in Appendix B We run SpiderBoost and Sparse SpiderBoost with learning rate 7j = 0.2, large-batch size B 40, small-batch size = 20, inner loop length m = 2. We run SGD with learning rate 0.2 and batch size 20. Figure 2 shows SpiderBoost is slightly worse than SGD, and sparsity provides a noticeable improvement over SGD.
LSTM trained on
BPR trained on MovieLens
x 10
Sparse SpiderBoost
4 10-4
Sparse SpiderBoost
x 10
NLP SpiderBoost
Spider Boost
SGD
3
SGD
Loss
7 x 10"
Loss
x 10"
x 10-1
5 100
0.0
0.5
1.0
1.5
0
10 15 Gradient Queries
20
Gradient Queries N
Figure 2: (a): SGD learning rate is 0.2 and batch size is 20. (b): SGD batch size is 103 and learning
rate schedule is 0.1 for epochs 0) 10, 0.01 for epochs 10 20, and 0.001 for epochs 20 40. The x-axis measures gradient queries over N, where is the size of the respective datasets. Plots are in log-scale.
4.3 SPARSE MATRIX FACTORIZATION
For our experiments with sparse matrix factorization, we perform Bayesian Personalized Ranking (Rendle et al. 2009) on the MovieLens database (Harper & Konstan 2015) with latent dimension of 20. To satisfy m = B/b, we run SpiderBoost and Sparse SpiderBoost with a large-batch size B 1030, small-batch size b 103, inner loop length of m = 10. For this experiment, we run SpiderBoost with the following learning rate schedule:
(a, b, = b (a
m
where 1.0 and b 0.1. The schedule interpolates from the algorithm progresses through the inner loop. For instance, within the inner loop, at iteration 0 the learning rate is 1.0, and at iteration m the learning rate is 0.1. We believe this natural way utilize the low variance
8

---

Published as a conference paper at ICLR 2020
at the beginning of the inner loop, and is fair comparison to exponential decay learning rate schedule for SGD. Details of the SGD baselines are provided in Figure 2 We see SpiderBoost is slightly worse than SGD, and sparsity provides slight improvement over SGD, especially in the first few epochs.
CONCLUSION
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 provide 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, problem which has thus far not been addressed. Assuming our algo- rithm captures the sparsity structure of the optimization problem, we also prove that the complexity of algorithm is an improvement over SpiderBoost. The results of our comparison Spider- Boost validates this assumption, and entropy measures provided in Table T Tempirically support our hypothesis that gradient sparsity exists.
Table D also supports the results in Aji & Heafield (2017), which shows that the top-k operator generally outperforms the random-k operator. Our random-top-k operator takes advantage of the superior performance of the top-k operator while eliminating bias via secondary random-k opera- 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 + k2 coordinates, which is essentially randomized coordinate descent analogue of SpiderBoost. Empirically, we see that Sparse Spider- Boost outperforms SpiderBoost when no sparsity structure present. We believe this due to the variance introduced by additional covariates in the SpiderBoost update, which is mitigated in Sparse SpiderBoost by our random-top-4 operator.
The results of our experiments on natural language processing and matrix factorization demonstrate that, with additional effort, variance reduction methods are competitive with SGD. 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.
REFERENCES
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving. Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dan Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vin- cent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Watten- berg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. tensorflow.org.
oorgg Software available from
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. CoRR, abs/l 704.05021, 2017. httpa/ppp////xx.oo///aaass//////
05021
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. In Pro- ceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1200-1205.
ACM, 2017.
Zeyuan Allen-Zhu. Katyusha Practical momentum method for stochastic sum-of-nonconveex optimization. arXiv preprint arXiv:1802.03388 2018a.
Zeyuan Allen-Zhu. Natasha 2: Faster non-convex optimization than sgd. In S. Ben- gio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett

---

Published as a conference paper at ICLR 2020
(eds.),
Advances in Neural Information Processing Systems 31, pp.
Curran
Associates.
mips cctccc//pppp// cc/paper/ Inc., 2018b. URL bttt::/pppers.
Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. ArXiv e-prints abx/1603.05643, 2016.
Zeyuan Allen-Zhu and Yang Yuan. Improved SVRG for non-stronglyy-conve or sum-of-non-comwe objectives. In International conference on machine learning, pp- 1080-1089, 2016.
Yves Chauvin and David E. Rumelhart (eds.). Backpropagation: Theory, Architectures, and Appli- cations. L. Erlbaum Associates Inc., Hillsdale, NJ, USA, 1995. ISBN 1-8058-12594
Aaron Defazio. On the ineffecttvenness of variance reduced optimization for deep learning, 2019.
URL http:p/s/wpgeeeeeeeeeeeeerrrr/aa
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Infor- mation Processing Systems, pp. 1646-1654, 2014.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(ul):2121-2159) 2011.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex op- timization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pp. 689-699, 2018.
F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst. 1(4):19: December 2015. ISSN 2160-6455, doi: 10.1145/ 2827872.
acm. www.ooggg//..o 0et.lo..115/22288000
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. CoRR, abs/1512.00335 2015. httttp://axxiw.org//bbs..
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Proceedings of the 26th International Conference on Neural Information Processing Systems Volume 1, NIPS 13, pp. 315-323, USA, 2013. Curran Associates Inc. URL http:
//dl. acm. htt.://www..caat...oo...oaaaaaaa
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14Xiv:1412.69880 2014.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. C0 (canadian institute for advanced re- search). URL http:
toronto.oooooooooo edu/-kriz/cifar. wtt.oootto..d./keii//..aaaa.
html
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. htthhttp://aat
lecun. http://tpt/pppcc////////////////
Lihua Lei and Michael Jordan. Less than Single Pass: Stochastically Controlled Stochastic Gradi- ent. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54, pp. 148-156. PMLR, 2017.
Lihua Lei and Michael Jordan. On the adaptivity of stochastic gradient-based optimization. arXiv preprint 194.44190..04480, 2019.
Lihua Lei, Cheng Ju. Jianbo Chen, and Michael Jordan. Non-convex finite- optimization via scsg methods. In Advances in Neural Information Process-
ing Systems 30, pp. 2348-2358. 2017. URL htttp:/ppapers httpppppprrr.ipss.pppppapppppe 68-9-non-convex-fii finite---e-iiieeeeeeeeeee-eeeeee sureee-uu-pppppp 1m scwa--ssss---tte- www.-iisss....mmm.ssss.s.....
10

---

Published as a conference paper at ICLR 2020
Mitchell Marcus, Grace Kim, Mary Ann Marcinkiewicz, Robert Maclntyre, Ann Bies, Mark Fer- guson, Karen Katz, and Britta Schasberger. The penn treebank: Annotating predicate argument structure. In Proceedings of the Workshop Human Language Technology, HLT '94, pp. 114- 119, Stroudsburg, PA, USA, 1994. Association for Computational Linguistics. ISBN 1-55860- 357-3. doi: 0..115/10755812.0755828 URL /ttts:://bii.org/// .tt 3115/1075511777 1075835
David R Musser. Introspective sorting and selection algorithms. Software: Practice and Experience, 27(8):983-993, 1997.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 194):1574- 1609, 2009.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, 2011. URL http::/uflll. wtt.iill.saaffoooooo hoosennnbeers/apps2000 www.hhhuuuuuurssseeee påf
Lam M Nguyen, Marten Dijk, Dzung T Phan, Phuong Ha Nguyen, Tsui- Tsui-Wei Weng, and Jayant R Kalagnanam. Optimal finite-sum smooth non-convex optimization with sarah. arXiv preprint (eXiv:/901.0700 2019.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Nhan H Pham, Lam Nguyen, Dzung T Phan, and Quoe Tran-Dinh. Proxsarah: An effi cient algorithmic framework for stochastic composite nonconvex optimization. arXiv preprint arXiv:1902.05679. 2019.
Sashank J Reddi, Ahmed Hefny,, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. arXiv preprint arXiv:1603.06166 2016a.
Sashank J Reddi, Suvrit Sra, Barnabás Póczos, and Alex Smola. Fast incremental method for non- convex optimization. arXiv preprint 16Xiv:/603.06112 2016b.
Steffen Rendle, Christoph Freudenthaler, Zeno Gantner, and Lars Schmidt-Thieme. Bpr: Bayesian personalized ranking from implicit feedback. In Proceedings of the twenty-fifth conference on uncertainty in artificial intelligence, pp. 452-461. AUAI Press, 2009.
H. Robbins and S. Monro. A stochastic approximation method. Annals of Mathematical Statistics, 22:400-400 407, 1951.
Nicolas Le Roux, Mark Schmidt, and Francis Bach. A stochastic gradient method with expo- nential convergence rate for finite training sets. Advances in Neural Information Processing Systems, pp. 2663-2671, 2012.
Sebastian U. Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. CoRR, abs/1809.07559/ 2018. http::: wwwp:/iivrrg//booo wwtp://ag.a....oo.///// 07599
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost: A class of faster variance-reduced algorithms for nonconvex optimization. CoRR, abs/1810.10690. 2018. URL
http://arxiv.on http:/bb//11000 10660
Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduc- tion. SIAM Journal on Optimization, 24(4):2057-2075, 2014.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex opti- mization. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 9926-3936. Curran Associates Inc., 2018

---

Published as a conference paper at ICLR 2020
A TECHNICAL PROOFS
A.1 PREPARATORY RESULTS
Lemma 2 (Lemma 3.1 of Lei & Jordan 2019)) Let N Goom(m). Then for any sequence Do, D with D 00,
B(Dx - DN+1) (Do ETDN)
Remark 1. The requirement Dx < is essential. A useful sufficient condition if [Da] ((Poly()) because a geometric random variable has finite moments of any order.
Lemma (Lemma B.2 of Lei Jordan (2019)). Let Bi,.... RM E I& be an arbitrary population
and J be uniform random subset of [M] with size Then
7(m < M)
1
Var
Σ 2j jEJ
M Σ
1,y112.
m
Proof of Lemma 7 WLOGG, assume that [iil 2 |.22 2 ... 2 |aral- Let be a random subset of
{ki + 1, .,. d} with size k2. Then
41 (I(E k1) + d d-ki I(e E(e ES)
kn
As result,
d d- ki I(e> ((E>&))((ESS) ye.
E (z kz)+
bo
and
d d ki
2
Var (1tops,,ts (2, =
I > ki) S)(1 - 1[[1-((E S))
li2
l:2
ye > kn).
hiz
Therefore,
Var (rtops, My (I,, 8))
k1
K2
Σ
21
k1
k2
top k1 (z, 1)
l:2
k2
E>
A.2 ANALYSIS OF A SINGLE INNER LOOP Lemma 4. For any 1,
E - ((0) =V((2 VS(a(()
and
Var
(1)
(0) ) b
22
|| 2
k1 b2
ge
+
G
K2
where Eja and Varj, are taken over the randomness of I( and the random subset S. involved in the rtopk,,k ky operator.
Proof. By definition,
=rlopki.e Ao (ML))
((zg((e())
t+1 Di
12

---

Published as a conference paper at ICLR 2020
Let S be the random subset involved in rko Then S is independent of (I MD) ()
By Lemma I
Es (utt1 - -6(0) - Vizgs ( Vizpo(o(
and
Vars - - d- ki k K2
|Lop* (Mr)) V Viypa (2)( (o2os((()) |
K2
axt11 xx ).))). the tower property of conditional expectation and Since I is independent of (M() variance implies that
Egpt (ul2) -v() = =Byo0 (Vizg Viggpn
(o) -v/))))V/(((f)))) -V(o)))
and
Varz, (u-11 - 10-(( ) Byy (Vars (uifi (())) Varzoo (Bs (uif) - -f)))) (8)
To bound the first term, we note that top-k, is linear in and thus
cop- (M,") V.220 (x(f1) (x
E 2000
BBg top-ki (M,), V0 (1 V VI2101 (z) ( 1
+ Varz(1) (rop (M Vigio (2(21 Vfz(0 (x) (2) }
= (3) + Varz()
Σ
top hi (M vl(aa2)) - vA(aT))
D
$EI
G(U)
< ( + b
(9)
where the last inequality uses Lemma 3 To bound the second term of (8) by Lemma 3
Var 2(1)
Es
() u+1 - 2)²))
= Varzto 2(00
V ( - V (
11 n
(1) L
- xt 210 (1)) 22
(2)
b 1| 1
bn
where (i) uses assumption Al and (ii) uses the definition that x111 = 222 (1)
Lemma 5. For any j,t,
E
() - vf(al2i11 > & -
+
1222 b 10
d- ki
li2
(5)
+
K2
b
where Eje and Varj. are taken over the randomness of I( and the random subset S involved in the 1t k2 operator.
Proof. By Lemma
4 we have
(
v((222)) = -100) - -V((z))) + (1241 v1 - -B,,(u -v())
241
Since I independent of (v 1x -((2),,
Cov,,e (16) 223_vo vf(x()
() 1,1 -1()) = 0.
As result,
( E.
(1 (1 - Var3. Var35111 - (.9))
The proof is then completed by Lemma
13

---

Published as a conference paper at ICLR 2020
Lemma 6. For any j.
E - V((RR)1
12 b
T²T <
<n)
+ (d - ki - k22) km)m
(d-
Rj+
B
1/2
where E, is taken over all randomness in j-th outer loop (line 4-13 of Algorithm Proof. By definition,
4
| || S || (1 || + rtop A2 (M,)), Vigci(a - Vizgo (zf
- 11 (1) || + V (222) - Vizpo (of2)
s 1 +
1 5
Σ VA(a - v(((a())
S $1100++
-
b (EI!")
S <1105001
Σ
v
||²
+
Σ
FE
1 11 +
2n
1 n
/|
2
+
1 n
Σ
|
b
n1
S |100501 + V2na
As result,
||- ||bb0||
|| + IV2na,
(10)
Thus,
||² < 2 + +2/lV/(< = Poly(().
This implies that we can apply Lemma 2 on the sequence D. = ||x - Vf(= )1.
Letting j Ny in Lemma 5 and taking expectation over all randomness in E,, we have
()) N V V. +1)
22
d K1
122 Es
v 12
E,
12 13
9N,
b
122
V =B,1 S
2 + 22 E, |
(
12 1+
d - K1
102 R.y.
(11)
K2
By Lemma
2
Ey ((( - v(<o8t++)11
1 (116)) v v 11 - T)(2
[Bllkdd (0) - -[( ()) - v((x))1)
(12)
(1)
(1)
where the last line uses the definition that æÿ 000 1 = ',,;' By Lemma
- ([ 0² [ < n)
(13)
B
The proof is completed by putting 11
12 and 13
together.
14

---

Published as a conference paper at ICLR 2020
Lemma 7. For any j,t.
(( S [(0) + 7 - // (2 2 -
Proof. By (4)
f(x11) S f(z(,) + (vf(z 2 - =4") + 4 -14 - z 12
2
-((o!") n (VS(x,)) (1) 1/) 1/4 L
1 1
V = = + - ~ )1 1
-
10,
_ 11
n²L
2
The proof is then completed.
Lemma 8. For any j.
E) 2 -(s) VV(xx)] (1- nL)EE || 10.. 12
rpm
where E, is taken over all randomness in j-th outer loop (line 4-13 of Algorithm 7
Proof. Since [V S a for any
- S 1|
This implies that
(f 60)
Σ
|10 + =f(
S o
k=0
As shown in 100. |0 = Poly(t) and thus [(((00)] Poly(t). This implies that we can apply
Lemma 2 on the sequence D. (x
Letting j = NN in Lemma 7 and taking expectation over all randomness in E,. we have
E, (= ( E, + 1 - "IS - - (1nn))ll0011
By Lemma
1 -, E, - -
(f( 1 -
m
m
The proof is then completed.
Combining Lemma and Lemma g we arrive at the following key result on one inner loop. Theorem 3. For any j.
2 (f( - fxx)))
d2I(B <n) (d - kr -2)m R.
f(2,))1 < mmm
K2
(1-nL- 1L- m
E, E, 1/
A.3 COMPLEXITY ANALYSIS
Proof of Theorem i By definition
of Rg and the smoothness assumption A1,
ER, < b+1 L L'BlI N,+1
2n) 2
b
15

---

Published as a conference paper at ICLR 2020
By Theorem
E [ & - (f(((o)-1) - f(x,)) -(x,))) o²I(B n))
1pm
1- mn² L2
2(d - kı - 12 m L2
10, 1
k2
Since nL v //2//6d /6dm
mn I, I?2
+ 2(d ki - k22 M2) 1.2
1
1
nL +
+
1.
b
K2
v6
6
3
As a result,
2 - f(x))) + o²I(B n)
2
E ||
17m
B
Since Tout ZT where T ~ (n])( we have
2 (ff(z)) -f f(TT+1)) +
0²I(B <n)
2
I2 < <n)
E| (fFout
<
1yTT
B
nmT
B
The setting of I and B guarantees that
2 Tmm
2
I²I(B
< <n)
2
2
B
2
Therefore,
1| S
By Cauchy-Schwarz inequality,
E (
)l S v B Vf 12 Sc
In this case, the average computation cost is
2(k1 + k22 hm 3BT(()
E.Coomp (t)
T(c) B
d
BA mmc2
VBbLA,
k2
0
0
2
The proof is then proved by the setting of B.
Proof of Theorem
2
Under the setting of 17,
mn m L
1
1
nL +
b S
1
v3
By Theorem
Q²T(B < n)
d
ki l22 R.
B[ <
+
+
mm
B
12
By definition of Fouts
24,
q²I(B <n)
(d - ki k2)m ERT.
(
<
+
nmT
B
k22
Under the settings of T and B,
24 mmf
2
Q2I(B < n)
2
<
3
B
3
This proves the first result. The second result follows directly. For the computation cost, similar to the proof of Theorem I we have
ECcomp (BBT) (022)
)
LA,,
B vm(bAm)
The proof is then completed by trivial algebra.
16

---

Published as a conference paper at ICLR 2020
Convolational Nit trained or KNST
Fully Connected NK trained on MNIST
1x00
Loss
AUM
10"
ty-.2)
opparsity.
ty
oppersty-d
ty
6 30
oparsiity 8)
tyoarsty-1)
(aparsity-11
3
0.00
025
0.50
0.75
1.0
1.25
1:50
1.75
2.00
0.00
0.25
0.50
1.25 Gradient Quartes /N
0.75
1.00
1:50
1.75
2.00
Gradient Queries /N
Figure 3: SpiderBoost with various values of sparsity, where (sparsity=k/4d d) corresponds to Spider- Boost with sparsity k/d. Both figures MNIST. The x-axis measures gradient queries over N, where is the size of the respective datasets. Plots are in log-scale.
B EXPERIMENTS
B. DESCRIPTION OF SIMPLE CONVOLUTIONAL NEURAL NETWORK
The simple convolutional neural network used in the experiments consists of a convolutional layer with kernel size of 5, followed by max pool layer with kernel size 2, followed by another convo- lutional layer with kernel size 5. followed by fully connected layer of input size 16 x side? 120 (side is the size of the second dimension of the input), followed by fully connected layer of size 120 84, followed by a final fully connected layer of size 84x the output dimension.
B.2 NATURAL LANGUAGE PROCESSING
The natural language processing model consists of word embedding of dimension 128 of 1000 tokens, which is jointly learned with the task. The LSTM has a hidden and cell state dimension of 1024.
Algorithm 2: SpiderBoost for Natural Language Processing.
Input: Learning rate inner loop size number of iterations T. large batch matrix Zo with & batches of size B, small batch matrix Z₁ with & batches of size b, initial iterate Zo, initial states Sy and Sp- do
for t 0..... T
i mod 4
j mod (1, f2)
then L = 0)
j = then
L S.
if mod(t, m) ( then
Vt, S1+1 == F2a, (rt, St)
10
St11 = St
else
12
9p = Vfzı (z, Sc-1)
13
De: 8141 = V [2 (Iz,
14
V1 = V-- + (ge 9b)
15
S
Ft+1 24 ni
Output: FT
let us derive the full batch gradient of generative language model. We encode the vocabulary of our dataset of length N that D Nº is sequence of integers corresponding to one-hot encodings of each token. We model the transition p( (D441 1 D,, 8;) using RNN model M M (D,, 8;) D2+1, 81+1, where 8; the sequential model state step The
Before describing Algorithm 2
17

---

Published as a conference paper at ICLR 2020
model M can be thought of as classifier with cross entropy loss L and additional dependence
St. The batch gradient objective can therefore be formulated by considering the full sequence of
predictions from = 0 to = N 1, generating for each step the output D 81+1- Each token one-hot encoded as integer (from 0 to the size of the vocabulary), so the empirical risk is given
by
N-1
J(: = N k=
Σ D,D,,
Thus, the full batch gradient is simply the gradient of with respect to æ.
In Algorithm 2 D is split into b contiguous sequences of length & N/b and stored in matrix Z1 E Nbx Taking a pass over Z1 requires maintaining a state 8; E No for each entry in a batch, which is reset before every pass over Z1. To deal with maintaining state for batches at different time scales, we define a different matrix Z2 E Nbxes which maintains a different set of states S; E NB for each entry of batch size B. We denote by 9. 8t+1 Vzz, (Ir 8e) the gradient of our model with respect to where fzz,, denotes the gradient function corresponding to the jth batch of matrix Z1. The function fz,, simply computes the loss of the jth batch of matrix Zz.
18


Reviews:
[{"review_id": "rJx0y3HZYS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThe author(s) provide a method which combines some property of SCGS method and SpiderBoost. Theoretical results are provided and achieve the state-of-the-art complexity, which match the one of SpiderBoost. Numerical experiments show some advantage compared to SpiderBoost on some deep neural network architecture for some standard datasets MNIST, SVHN, and CIFAR-10. \n\nComments: \n\n1) It is true that variance reduction methods achieve the state-of-the-art complexity theory for finding first order stationary point of general nonconvex optimization problems. However, it is well-known that variance reduction methods are not very efficient for training deep neural networks. All of the experiments in this paper are focusing on deep learning problems. If the author(s) would like to show good performance, I would suggest to compare the algorithms with the state-of-the-art algorithms in Deep Learning such as Adam, SGD-Momentum. Showing some improvement over SpiderBoost for deep learning problems would have low impact. \n\n2) I would suggest the author(s) to switch directions to focus on general nonconvex problems, that is, to find some different examples on general non-convex optimization problems rather than for deep learning problems. In other words, to find examples which show that your algorithm has more advantage than SGD-type algorithms, SVRG-type. \n\n3) I would also suggest the author(s) to plot all figures in log-scale in order to see in more detail performance. \n\n4) According to my knowledge, SpiderBoost is an alternative way of re-writing the SARAH algorithm [1, 2] with some small modification, that is a variant of SARAH. Therefore, the SARAH algorithm should be highly related to this paper and need to be discussed and mentioned more clearly. \n\n[1] Nguyen et al 2017a, “SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient”.\n[2] Nguyen et al 2017b, “Stochastic Recursive Gradient Algorithm for Nonconvex Optimization”. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "S1gBwSJRtB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper introduces a sparse variant to SpiderBoost which reduces the complexity cost of updating gradient estimates by way of sparse updates. The authors prove that this variant incurs a negligible increase in worst case complexities as soon as certain assumptions are satisfied, and that when their algorithm captures sparsity correctly, they improve upon SpiderBoost's complexity.\n\nThis paper is clearly, and the experiments support the theoretical contributions. \n\nIn Figure 1, you report results as a function of gradient queries/N. Given Theorem 2, I assume that the graphs would look similar as a function of wall-clock time; can you confirm this?\n\nRecommendation: Accept. \n\nMinor comments and questions for the author:\n- I am slightly confused by the introduction of the rtop operator. Specifically, \n  1) What is the relation between k1, k2, and k?\n  2) You write that S is a random subset of size k. Should this be k2?\n  3) In your first example, should we have rtop(x,y) = (0, 16, 0, 0, 1), since for \\ell = 2, y_\\ell = 4, d-k1 = 4, k2=1? Am I missing something?\n  More generally, my understanding is that the rtop(x,y) operator randomly sparsifies y based on x, which essentially provides indication of where sparsity would be least harmful; when not sparsifying, rtop applies a rescaling that guarantees unbiased estimates. If this is correct, I would recommend making that intuition more clear early on in the paper, in order to improve upon the clarity of the paper.\n\n- You state that rtop is linear in y; since rtop depends on the random variable S, is the claim that E[rtop(x, y+y')] = E[rtop(x, y)]+E[rtop(x,y')] (which follows from unbiasedness)?\n\n- For your experiments, could you discuss how your choice of hyperparameters relates to the constraints in Theorem 1 and 2? \n\n- I believe Table 1 would be more impactful if it also included the initial entropy ratios at the beginning of training, rather than reporting those values below.\n\n- Other variance reduction techniques for minibatching focus on choosing the minibatches themselves with non-uniform sampling. Under such a sampling mechanism, do you foresee any complications to using SpiderBoost with Sparse Gradients, eg., decrease in overall sparsity?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1g8clOTFH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper aims at improving the computational cost of variance reduction methods while preserving their benefits regarding the fast provable convergence. The existing variance reduction based methods suffer from higher per-iteration gradient query complexity as compared to the vanilla mini-batch SGD, which limits their utility in many practical settings. This paper notices that, for many models, as the training progresses the gradient vectors start exhibiting structure in the sense that only a small number of coordinates have large magnitude. Based on this observation, the paper proposes a modified variance reduction method (by modifying the SpiderBoost method), where a 'memory vector' keeps track of the coordinates of the gradient vectors with large variance. Let $d$ be the size of the model parameter. During each iteration, one computes the gradient for $k_1$ coordinates with the highest variance (according to the memory vector) and an additional $k_2$ random coordinates. \n\nThe paper shows that in the worst case, the proposed method has the same gradient query complexity as the SpiderBoost variance reduction method. Assuming that the proposed method can track the sparsity of the gradient vector, the proposed method achieves a gradient query complexity which is $O(\\sqrt{(k_1 + k_2)/d})$ times that of the SpiderBoost method. The paper demonstrates the gradient query complexity improvement over the SpiderBoost method on MNIST and CIFAR-10 data set.\n\nThe paper presents novel results by utilizing the ideas from the field of communication-efficient distributed optimization. As far as the reviewer can tell, the results in the paper are correct. That said, there is quite a bit of room for improvement in terms of the writing of the paper. \n\nThe paper appears to have way too many typos. For example, \n\nIn Section 2.1:\n- Why is $k$ introduced?\n- $S$ denotes a random subset with size $k$ ---> $k_2$?\n- drawn from the set ${\\ell : |y_{\\ell}| < |y_{(k)}|}$ ----> ${\\ell : |x_{\\ell}| < |x_{(k_2)}|}$?\n- $rtop(x, y) = (0, 12, 0, 0, 1)$ --> $rtop(x, y) = (0, 16, 0, 0, 1)$\nIn Lemma 1: \n - while defining $top_{-k_1}(x, y)$, \".... if |x_{\\ell}| >= |x_{(k_1)}|\" ----> \".... if |x_{\\ell}| <= |x_{(k_1)}|\"?\nIn Section 2.2:\n - What are $g_0, g_1,..., g_{L-1}$? Shouldn't these be $\\phi_0, \\phi_1,..., \\phi_{L-1}$?\nIn A1: \n - right after (5), what is $\\tilde{x}_0$ in the definition of $\\Delta_f$?\n\nThe authors may also consider making the empirical evaluation more comprehensive by considering tasks from the NLP domain, e.g., language modeling. This would further help asses the utility of the proposed method.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Congratulations on getting your paper accepted to ICLR. Please make sure to incorporate the reviewers' suggestions for the final version.
Decision: Accept (Poster)