Faster Neural Network Training with Approximate Tensor Operations
Authors: Menachem Adelman
Kfir Yehuda Levy
Ido Hakimi
Mark Silberstein
Venue: NeurIPS 2021 Poster (2021)
Keywords: optimization for deep networks

Abstract: We propose a novel technique for faster deep neural network training which systematically applies sample-based approximation to the constituent tensor operations, i.e., matrix multiplications and convolutions. We introduce new sampling techniques, study their theoretical properties, and prove that they provide the same convergence guarantees when applied to SGD training. 
We apply approximate tensor operations to single and multi-node training of MLP and CNN networks on MNIST, CIFAR-10 and ImageNet datasets. We demonstrate up to 66% reduction in the amount of computations and communication, and up to 1.37x faster training time while maintaining negligible or no impact on the final test accuracy.

Faster Neural Network Training with Approximate Tensor Operations
Menachem Adelman Intel & Technion
Kfir Y. Levy
Technion
adelman mww.mmee@gmail.ccommm com
kfarylery@techhiior ac.
Ido Hakimi
Mark Silberstein
Technion idohakimi idohakimi@gmail... com
Technion markθee www.hien..ccc..cc ac. il
Abstract
We propose novel technique for faster deep neural network training which system- atically applies sample-based approximation to the constituent tensor operations, i.e., matrix multiplications and convolutions. We introduce niques, study their theoretical properties, and prove that they provide the same convergence guarantees when applied SGD training. We apply approximate tensor operations to single and multi-node training of MLP and CNN networks on MNIST, CIFAR-10 and ImageNet datasets. We demonstrate up to 66% reduction in the amount of computations and communication, and to 1.37x faster training time while maintaining negligible or impact on the final test accuracy.
sampling tech-
Introduction
Approximation techniques for faster inference and training of deep neural networks (DNNs) have received considerable attention. Examples include quantization (15), low-rank and structured-spars. models 9 weight extrapolations [10), and partial/asynchronou gradient updates in the context of distributed training 11 12]. Sampling-bar based approximations were used to accelerate inference but using them in training 17 has not been systematically studied nor demonstrated
13 14, end-to-end GPU performance benefits in practice.
We propose a novel approach to accelerating DNN training by systematically approximating tensor operations via sampling.
high level, the original matrix products and convolutions are replaced with their faster approximate versions. The approximation is applied separately to each tensor operation, keeping the network architecture and tensor dimensions intact, thereby facilitating the adoption of this technique in existing DNN training frameworks, potentially in combination with other approximation techniques. Furthermore, when combined with distributed training, our technique allows for seamless reduction in the communication bandwidth and increased performance gains.
We begin by reviewing the plethora existing methods for approximating matrix multiplication. We compare several known algorithms 25), and find column-row sampling (CRS) [20] to be the most suitable for approximating matrix multiplications in training. In order to compute the product two matrices A B, the CRS algorithm samples the columns of A and the corresponding rows of B thus constructing smaller matrices which are then multiplied as usual. This method incurs low sampling overheads and lends itself to efficient implementation using existing dense matrix product routines. CRS minimizes the approximation error for the Frobenius norm of the resulting matrix while keeping the approximation unbiased.
A Viterbi fellow
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Sampling-basee based approximations can be interpreted as a form of Dropout [6], and we discuss the similarities and differences between the two. While Dropout aims to prevent overfitting, we focus on approximations means to accelerate training by reducing the amount of computation.
In this work aim to approximate tensor operations? Second, what are the relations between using exact or approximate operations during training?
two main questions. First, can neural networks be trained while using
We start by analyzing the simpler case of linear regression, where we can derive the effects of approximations in closed form. We define loss function that takes the sampling into account, and observe that the resulting gradients differ from the exact training due to the dependency between sampled features. To this end, propose independence of samples, study its properties, and show that in linear regression it is equivalent to dynamic L2 weight regularization of the original, non-approximate loss.
Bernoulli CinoollliCRRst CRS variant which achieves statistical
We then turn to the more general case of non-linear deep neural networks. We show that using sampling-base -baedd--badddd approximations in the backward pass provides the same convergence guarantees as the exact SGD for bounded weights. The convergence result holds for unbounded weights as well approximation is applied only to the weight gradients and if the activation functions are bounded.
We also study new TopK-CRs algorithm which deterministically selects the top-k column-row pairs with the highest norms. We show that this algorithm is equivalent to the minimal mean square error estimator (MMSE) in case column-row pairs are pairwise independent with zero mean.
Last, we generalize matrix product approximation to convolutions and analyze the approximation error to derive the optimal sampling policy. This allows us apply approximations training of convolutional neural networks (CNNs).
We implement our techniques in PyTorch 27 and evaluate them on several DNN topologies, including MLP and CNN networks on MNIST
28). Wide ResNet 28-10 [29] on CIFAR- (30),
and Re and ResNet- 152 B1 on ImageNet 332. We demonstrate up to 66% reduction in the number of FLOPs and up to 1.33x faster training time with little or no degradation model accuracy.
We develop another flavor of TopK-CRS which samples according to the weight norms only. When sampling the same subset of weights for different workers in a data-parallel setting, our sampling technique enables reducing the amount of gradient communication between workers. Notably, our algorithm is compatible with the standard AllReduce approach used in distributed deep learning. We implement AllReduce scheme that takes advantage of the smaller gradient footprint and demonstrate 1.09x-1.37 1.37x speedup in multi-node training.
Our contributions are as follows:
We derive general convergence guarantees for training with approximate tensor operations.
We develop novel sampling algorithms and analyze their theoretical properties.
We extend sampling-base algorithms to fast approximation of multi-channel convolutions.
We show that our approach can reduce the computation, communication and total training time on several popular neural network architectures with little or no accuracy degradation.
2
Related work
To the best of our knowledge, we are the first to study the application of sample-based approximations of tensor operations to speed up DNN training. However, there have been several prior efforts to accelerate DNN computations via approximation which we survey below.
Several works accelerate inference through model compression 33/399 A large body of work is
devoted quantization and low-precision datatypes (see for example 2 5)). Approximation was
used to extrapolate weight values [10]. Another approach enforces low-rank or structured-sparse structure on the layers, resulting lower computational cost both for training and inference 9..
Other works accelerate inference by approximating large matrices as products of lower-ranked ones 40
or through lecslity-sensitive hashing 42

---

In the context of distributed training, several works targeted communication bottlenecks by gradient
quantization B delayed weight updates [TT [2] and low-rank approximation of the gradient
matrix 43 These methods are complementary and compatible with ours.
semplling-bsedd approximations
used accelerate inference
[
but using them for
training [1H17] has not been systematically studied nor shown to speed training on GPUs without accuracy degradation. Sub-sampling whole layers was shown enable training of very deep CNNs
44
2.1
Approximate matrix multiplication
There several known algorithms for approximating matrix product. However, only those that meet the following requirements will be effective for DNN training. First, the algorithm should apply to dense matrices of arbitrary dimensions. Second, to reduce training time, the overall multiplication including input transformation should be faster than the original product. Last, the algorithm should be amenable to efficient implementation commodity hardware.
Using these criteria, we consider the following algorithms:
Random walk [8 This algorithm performs random walks on a graph representation of the input matrices, but is applicable to non-negative matrices only.
Random projections 231 The two matrices to be multiplied are first projected into a lower- dimensional subspace by scaled random sign matrix. These algorithms require both input matrices to be roughly square, otherwise the cost of projection will be similar to the cost of original product. In DNNs, however, it is common for one dimension to be smaller than the other.
These algorithms represent each column-row outer product as polynomial multiplica- tion and then calculate it using Fast Fourier Transform. The complexity depends the sparsity of the input matrices, decreasing as the sparsity increases. Therefore, these algorithms might not be effective for dense matrices.
FFT [4 25]
Several algorithms replace one input matrix with its low-rank approximation using truncated SVD. These algorithms are suitable for inference where the weight matrix factorization can be pre-computed offline, but are not applicable to training since the high cost of factorization is incurred in every matrix product.
SVD 19 33 36
Column-row sampling (CRS) 119 20 The sampling algorithm approximates matrix product A B by sampling & columns of A and respective rows of B to form smaller matrices, which are then multiplied as usual.
We choose CRS as the basis for our current work because meets all the criteria above: It is applicable to fully-connected layers of any size, its effectiveness does not depend on the matrix contents, its sampling is computationally lightweight, and may use regular matrix multiplication algorithms since the sampled sub-man sub-matrices remain dense.
2.2 CRS
Let A E RR B RTxp, Their product A B is approximated as a weighted sum of outer products between sampled columns of A and corresponding rows of B:
B
1
AGO B(a))
kp
where A (1), B(a denote the matrix i' i'th column and row respectively, k is the number of samples (satisfying < le < n). {pr]._ is probability distribution over the column-row pairs of AT, B and & E (1,..., n.. This algorithm allows linear reduction in complexity from O(mnp) to O(mkp).
can also be expressed as A DST SDB, where D E |Rax is diagonal scaling matrix with:
1
(D)s
Vkp,
3

---

and S E R is sampling matrix that selects & features, possibly with replacement. S is random matrix, where each row has in one entry and zeros in others. In each row, the probability of having the non-zero entry in column j is Pj-
Drineas al. 20 show that CRS is unbiased:
E [AA DS SDB) A
and also derive upper bounds for the expected Frobenius and spectral norms of the error matrix [A B - A DS SDB]: They show that the error is minimized when the sampling probabilities are proportional to the product of the column-row Euclidean norms:
A B P: Σj=1 (6))
(4)
In which case the expected Frobenius error is:
1 k
Σ A
- (lATTB)
(5)
2.3 Approximate Tensor Operations and Dropout
Sampling-based approximations can be interpreted as a flavor of Dropout 26 a popular technique prevent overfitting by randomly zeroing individual activations during training. However, the sparsity pattern resulting from Dropout is unstructured and therefore cannot be exploited efficiently by GPUs despite recent advances structured sparsity support [8). Prior works on fast Dropout training [45] 46] are different than ours and do not demonstrate acceleration of large networks while maintaining accuracy.
Some works proposed non-uniform Dropout probabilities for individual activations [47 or full channels 48). Their sampling heuristics are different from ours which derived from optimal approximation. Furthermore, they use Dropout only for preventing overfitting and do not leverage speed up training. In experiments demonstrate the utility of sampling-basee approximations for DNNs with and without Dropout. Conversely, we did not observe improved accuracy from approximations which could have been attributed to reduced overfitting.
3 Approximate Linear Regression
We now analyze CRS in the simpler context of linear regression, where we can derive the effects of approximations closed form. We show that this leads to biased gradient estimates.
Let X C R a dataset containing M examples, each a vector in R". Every x¹ E X is associated with "ground truth" value y' E R.
Let w E R be parameters linear model that predicts value 17 for every of E
(6)
To simplify the notation do not include an explicit bias term. We do without loss of generality since we can always add another entry of 1 to the features.
Let us define the MSE (Mean Square Error) loss function:
When using SGD (Stochastic Gradient Descent), are given single example z² E g" in each dt For notation simplicity we omit the superscript from step, and update w using the gradients 9w x² ". g.yy"

---

The gradients are given by the chain rule as:
de TT x y)
2x(w
(8)
dw
Now, let us assume that the multiplication w is approximated using CRS. The linear regression model now becomes:
i w DS SDx
(9)
and for the MSE loss the gradients will be:
2DS SDr(w DST SDx y)
(10)
dw
Where Øt Ow
denotes the CRS weight gradients.
Note that DS SD appears twice in (10). In T DS SDx represents sampling in the forward pass, while in DS SDx it results in passing gradients only the elements of w that sampled the forward pass.
It should be emphasized that (9) and 10 in fact describe gradients with respect to different loss function compared to (8): one loss function uses while the other uses y. If the approximate gradients unbiased estimates of the con-approximate gradients, could relate the approximate training process to the original one. However, the weight gradients do not satisfy this unbiasedness property:
a Σ W (5)s
E
2xy
3e y/
(11)
Ow
where we denote $ A DS SD, and use the fact that $ is diagonal.
For the expression in 11 to be equal to that in (8) we need that (5),,) = 1. However,
this is not the case because ($)j.) and (S)r., are not independent random variables: an entry in the diagonal of Š is the (scaled) number of times column-row pair selected out of the total samples in CRS. The event selecting particular pair therefore affects selecting others.
We note that if instead of changing the loss function treated the approximate multiplication "black box" that replaces the original product, we could use (8) and only replace the forward pass product w with the "black box" substitute of w DS SDr. This would yield:
08 Ow
2r(w DS SDx - y)
(12)
which satisfies:
OE
Of
E
(13)
Ow
Dw
12 is equivalent to applying the approximate computation in the forward pass, but propagating the gradients all weight entries in the same way if the computation find that this approach leads to significantly lower accuracy in deep neural networks compared to sampling the same entries in the forward and backward pass, or applying approximations in the backward pass only.
exact. In practice we
Bernoulli-CRS
We now turn to develop Bernoulli-CRS, a new variant of sampling approximation that enables to sample column-row pairs independently and without replacement. Applied to línear regression, we show that using Bernoulli-CRS is equivalent to employing unbiased gradient estimates addition to bias term which can be interpreted scale dependent weight regularization.
5

---

These aforementioned properties can be achieved by assigning separate Bernoulli sampling probability p; for each column-row pair i, and sampling pairs independently of each other. To control the amount of sampling, we add another constraint that all the probabilities will sum up to an integer k:
Bernoulli-CRS:
Pi
(14)
Let us define K E TRex a random diagonal sampling matrix where Kjj ~ Bernoulli(p,) for 1 j 1 n. Furthermore, let us define another diagonal scaling matrix E Raxn where Pj. = v/5 for 1 i
Using the K and P matrices we may now define our new Bernoulli-CRe CRR algorithm. Let A E R and B RTxp, The product A B can be approximated with AT B defined as follows:
Zi A AT B PKKPB
A B
(15)
Pt
where (Z: Bernoullí(p:))= are independent random variables. We denote Ā A KPA and B A KPB.
In the appendix we develop the properties of Bernouli-CRR. We show it is unbiased and derive bounds on the eтror variance both in expectation and in high probability. We derive the optimal sampling probabilities minimizing the expected variance, and show that under certain conditions they are given by the simpler expression:
(() B Σソ= A B
1
pt min
(16)
In the appendix we show that applying Bernoulli-CRB in linear regression leads to unbiased estimate of the original gradients with an additional regularization term R(w), which we define as:
Pi x3 mm
R(w)= E
(17)
Pj
and the expectation is with respect to the distribution of the data samples.
The term R(w) can be interpreted as input-dependent L2 regularization. The regularization higher as 2 grows in magnitude and as Pj decreases. Both serve to reduce the impact on the weights if they were chosen with small probabilities or mostly because of the input size. We note that Wager et al. [49] conduct similar analysis for Dropout in the particular case where the same sampling probability used for all features.
To summarize, sampling in the simpler case linear regression minimizes the original loss function with added regularization term.
Approximate Backpropagation in Non-Linear Deep Networks
The analysis of approximate linear regression cannot simply generalize deep non-linear networks: non-linearity leads to biased network output even if the approximate multiplication is itself unbiased. Still, are able to obtain strong theoretical results on the relations between exact and approximate training if the approximations are limited to the backward pass: the forward pass is calculated as usual, and the matrix products in the backward pass performed using approximate matrix multiplication.
We prove the following theorem:
Theorem 1. Let (xx W,b) be a multi-layer neural network with B-Lipschitz activation functions Let E be B B-Lipschitz loss function, and let the network be trained with SGD using properly

---

decreasing learning rate. Assume that the weights are bounded; and further assume that the matrix products the backward pass are approximated using an unbiased approximation scheme, i.e..
IE [AA
B approx(A B)] =0
and that there exists constant C and a norm |1-I1 such that:
E || approx B)]|"] (TTB) Sc [I
Then the upproximated NN gradient estimates are unbiased, and their second moments are bounded. Corollary. Based recent works non-convex optimization (see e.g. (50]), the unbiasedness and bounded second moments ensured by Theorem 7 imply that approximate backpropagation enjoys the same convergence guarantees as regular SGD training.
In the appendix we show that CRS and other sampling algorithms satisfy the property
A B approx(A B) B)] s C |||||| ||B||
E
Note that for Theorem 1 we required that weights will be bounded during the training process. This strong assumption which could be justified if weight regularization or clipping is used. In the appendix we prove the same results without relying on these assumptions, if only the weight gradients approximated and if the activation function is bounded (such sigmoid).
6 Sampling Without Scaling and Top-k Selection
We now consider a different sampling scheme where & column-rov -ro pairs are selected deterministically without scaling. This can be viewed as a special case of Bernouli-CRSS, where the sampling probabilities are either 0 or 1. We now show that under certain assumptions on the distribution of the input matrices, this scheme can lead to the optimal estimation:
Theorem 2. Let A be
random matrix and B be n x p random matrix, such that
A T ((0) =
for 1 SiS n. Assume column-row pairs with indices {i} are sampled from A and Then, the MMSE estimator of the product A AT where A, B are constructed from the sampled column- row pairs without scaling.
Furthermore, if A T Búy and A TÚ BG) are independent for different i, then the MSE minimized when sampling pairs with the maximum norm multiplication
The assumptions in Theorem 2 can hold in practice if weights are initialized with a zero-centered distribution(51] if the distribution weights remains centered around zero during training (51)54), [55).
and if different weights can be considered
We study the approximation quality of CRS. Bernoulli-CRS and top-k selection synthetic matrix multiplication. We generate 100 x 100 random matrices and compute the error metric:
|A B approx(A") B)
(18)
|| ||B||
Figures [(a) show the approximation error for different algorithms and sampling ratios, averaged over 1000 runs. We observe that Bernouli-CRRS outperforms CRS in higher sampling ratios. Also, when one matrix has i.i.d entries with zero mean, Bernoulli-CRS outperforms CRS and top-k selection performs the best as expected from Theorem 21
We also consider different flavor of top-k selection, which we refer to as "top-k-weights". sampling k column-row pairs corresponding to rows of B with the highest norms. While not providing the theoretical guarantees of Theorem [ the new variant has desirable property for data parallel distributed training, where weights are identical between different workers. A deterministic selection algorithm that only depends on the weights will sample the same weights for all workers, allowing to reduce the gradient communication between nodes to the selected weights only.
7

---

Approximation Error
1
top-k
Approximation Error
top-k
0.8
CRS
0.8
CRS
0.6
Bernoulli
0.6
Bernoulli
0.4
0.4
0.2
0.2
0
20
40
60
80
100
0
20
40
60
80
100
of computations
of computations
(a) Matrix product: both matrix entries drawn from
(b) Matrix product: one matrix entries drawn from
(1,
(0, 1), the other from (111 1)
Figure I: Approximation error depending on the amount of performed computations. Lower is better.
7 Approximating Convolutions
We extend the basic CRS algorithm to the approximation of multi-channel convolutions. In matrix multiplication sampling is performed over the common dimension. The analogue for multi-channel convolution is sample over the input channels dimension, illustrated in Figure As in the matrix case, the output dimensions remain the same.
OH
IH
KH
IW
KW
OW
OC
IC
Figure 2: Sampling input channel out of three
the appendix we derive the optimal sampling probabilities and scaling factors. Bernoull-CRRS and top-k algorithms can be developed for convolutions as well in analogous way.
Experimental Results
We implement CRS, Bernoulli-CRe --R and top-k selection approximation algorithms in PyTorch both for matrix multiplication and convolution. Our implementation allows to control the sampling degree and the application of approximation in the forward or backward passes.
We replace exact tensor operations with their sampling-based approximations, without changing training hoper-parametery. Only column-row pairs sampled in the forward pass are used during backpropagation as the rest do not affect the loss. Hence, sampling the forward pass also reduces the amount of backward pass computations by the same ratio. We apply approximations only during training, and use exact computations for validation/test evaluation.
We evaluate our approximate training technique on several network architectures and datasets: MLP and CNN on MNIST, Wide ResNet 28-10 on CIFAR- 10 and ResNet-50 and ResNet-152 ImageNet. We train the networks on single node using NVidia V100 GPUs (two GPUs for ResNet-152, one for the rest), and measure the reduction in multiply-acummulae operations due to sampling as well as the overall speedup in total training time versus oon-approx baseline. The appendix includes additional details on the models and the training process.

---

Table I: Compute reduction, communication reduction and wall-clock speedup of training with approximate tensor operations.
NETWORK
COMPUTE REDUCTION
COMMUNICATION REDUCTION
ACCURACY (BASELINE)
TRAINING SPEEDUP
MLP (MNIST)
50%
98.22% (98.22%)
CNN (MNIST)
66%
99.25% (99.35%
WRN-28-10 10 (CIFAR-10)
50%
95.89% (96.17%)
1.33x
RESNET-50 (IMAGENET)
6.5%
75.65 75.63% (75, (5.6%)
1.04X
40%
76.44% % (77 (7.65%)
1.16X
SINGLE NODE
9%
77.66% (77 665%)
1.04X
RESNET-152
(IMAGENET)
40%
48%
76.44% (77.65%
1.37X
NODES
12%
23%
77.48% (77.65%)
1.13X
9%
13%
77.8% (77.65%)
1.09X
100
100
Test Accuracyy
80
top-k Bernoulli
Accuracy
top-k CRS Bernaulli Baseline
Images/see
600
- 23%
Base 13%
-+-48%
60
90
400
20
200
80
20
40
60
80
100
0
20
40
60
80
100
2
3
4
5
6
8
% of computations
%6 of backward computations
Nodes
Figure 3: CIFAR-10 (approximate for- MNIST (exact forward, approxi- weights sampling (% fewer gra- ward and backward)
WRN-28-10 on Figure 4: 3-layer MLP on Figure 5: AllReduce with top-k-
mate backward)
dients sent).
Our results using top-k sampling are summarized in Table We see reduction of up 66% in the computational cost with little or no degradation in model accuracy, and up to 1.33x faster training time. We believe the gap between compute reduction and end-to-end speedup fusing the sampling with the matrix multiplication routines, or running different HW architecture that allows fast sampling and norm computation. We note that the small MNIST models do not exhibit training time speedup since they are not compute-intensive enough to saturate the GPU. The ratio between compute reduction and actual speedup is smaller in ResNet- 152 compared to ResNet-50 and WRN-28- 22--288-0 10 because the batch size per GPU is lower due to the limited GPU memory capacity.
be reduced by
Sampling Algorithms We compare CRS, Bernoulli-CRs and top-k selection on MNIST and CIFAR-10 and find empirically that top-k results in higher accuracy and faster training time (FigureB) This result is consistent with that of approximate (0, 1) matrix product (Figure I(b). This is not surprising given Theorem 2 and our empirical observation that the weight distribution is close to symmetrical around zero throughout training.
Approximations in Forward Pass and Backpropagation For the small MNIST models we are able to perform low 10% of the computations in the backward pass without harming accuracy 4. However, in the larger models (WRN-28-100 10) we find empirically that accuracy drops when approximating only the backward pass. Therefore, TableTTw report results for consistent sampling in the forward and backward passes.
Sampling Ratio Sensitivity We find that the achievable compute reduction not consistent across networks and datasets. For MNIST and CIFAR-10 we maintain good accuracy while reducing 50%-66% of the computations. However, ImageNet proved to be more sensitive and we kept accuracy intact when applying 50% sampling to the ResNet layers with 1024 or more channels only. Figure 6 shows the learning curves under different sampling ratios compared to the non-approximate baseline.

---

100
80
80
Accuracy
80
Accuracy
60
Accuracy
60
60
% computations
% computations
%f computations
Baseline
10%
Baseline
522
Baseline - 50%
30%
59%
68%
20
70%
-0%%
91%
0
40
80
120
160
200
0
10
20
30
40
50
60 70
80
90
0
10 20 30
40
50
60
70
80 90
Epoch
Epoch
Epoch
(a) WRN-28-10 CIFAR-10 10
(b) ResNet-50 Imagenet (top-1)
(c) ResNet-152 Imagenet (top-1)
Figure 6: Learning curves for validation accuracy under different top-k sampling ratios
Distributed Training We implement an AllReduce "top-k-weights" scheme in PyTorch. This scheme performs reduction only for the gradients of the sampled weights, reducing inter-node communications. Table [ shows the accuracy-speedus trade-off for ResNet- 152 distributed training. [igure[]showe the respective scaling behavior of these schemes relative to the exact baseline. We note that compute savings did not lead to significant single-node speedup since in this experiment the V100 GPUs (from Amazon AWS) had lower memory capacity, which led to smaller batch size per GPU. The multi-node training speedup therefore mostly due to the communication savings.
Conclusion
In this work we have demonstrated the utility of sample-based approximation of tensor operations for neural network training. both theoretically and empirically. We believe that further acceleration could be achieved through dedicated GPU primitives fusing sampling and matrix multipicaaton/ccovvlltin as well as varying and adaptive sampling rates for different layers and iterations. Studying other approximation algorithms, applications in resource-constraing between our theoretical results and what worked best in practice are all promising directions for future research. Overall, we believe that sample-basee approximations and fast approximations in general are valuable additions to the toolbox of techniques for deep learning acceleration.
environments and bridging the gaps
Acknowledgments and Disclosure of Funding
K.Y. Levy acknowledges support from the Israel Science Foundation (grant No. 447/20). I. Hakimi acknowledges support from the Hasso Plattner Institute at the Technion. M. Silberstein acknowledges support from the Israel Science Foundation (grant No. 1027/18).
References
[1] Itay Hubara, Matthieu Courhariaux, Daniel Soudry, Ran El-ivniv, Yoshua Bengio. Quantized neural networks: Training neural networks with low precision weights and activations. arXiv preprint MiXiv:1609.0706 2016.
[2] Paulius Micikevieius, Sharan Narang, Jonah Alben, Gregory Diamos, Erich Elsen, David Garcia, Boris Ginsburg. Michael Houston, Oleksii Kuchaev, Ganesh Venkatesh, al. Mixed precision training. arXiv preprint arXiv:1710.037440 2017.
[3] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data Satallarallel distributed training of speech duns. In Fifieenth Annual Conference of the International Speech Communication Association. 2014.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Temary gradients to reduce communication distributed deep learning. Advances in Neural Information Processing Systems, pages 1508-1518, 2017.
[5] Ayan Chakrabarti and Benjamin Moseley. Backprop with approximate activations for memory-efficiinnt network training. Advances in Neural Information Processing Systems. 32:2429-2443 2019.
10

---

[6] Franck Mamalet and Christophe Garcia. Simplifying convnets for fäst learning. In International Conference Artificial Neural Networks, pages 58-65. Springer. 2012.
Oleksii Kuchaiev and Boris Ginsburg. Factorization tricks for Istm networks. arXiv preprint 1703 10722, 2017.
[8] Asit Mishra, Jorge Albericio Latorre, Jeff' Pool, Darko Stosic, Dusan Stosic, Ganesh Venkatesh, Chong Yu, and Paulius Micikevicius. Accelcrating sparse deep neural networks. arXiv preprint arXiv:2 2021.
[9] Ita Hubara, Brian Chmiel, Moshe Island, Ron Banner, Seffi Naor, and Daniel Soudry. Accelerated sparse neural training: A provable and efficient method find n: m transposable masks, arXiv preprint arXiv:2102.088 08124, 2021.
[10] Sagar V Kamarthi and Stefan Pittner. Accelerating neural network training using weight extrapolations. Neural networks, 12(9):1285-1299 1999.
[11] Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In Advances in neural information processing systems, pages 693-701, 2011.
[12] Nikko Strom. Scalable distributed dnn training using commodity gpu cloud computing. Sixteenth Annual Conference of the International Speech Communication Association, 2015.
[13] Weizhe Hua, Yuan Zhou, Christopher M De Sa, Zhiru Zhang, and G Edward Suh. Channel gating neural networks. In Advances in Neural Information Processing Systems, pages 1886-18966 2019.
[14] Xitong Gao, Yiren Zhao, Lukasz Dudziak, Rohert Mullins, and Cheng-zhong Xu. Dynamic channel pruning: Feature boosting and suppression. arXiv preprint vrXiv:1810.05311. 2018.
[15] Xu Sun, Xuancheng Ren, Shuming Ma, and Houfeng Wang. meprop: Sparsified back propagation for accelerated deep learning with reduced overfitting. In International Conference on Machine Learning, pages 3299-3308, 2017.
[16] Beidi Chen, Tharun Medini, James Farwell, Sameh Gobriel, Charlie Tai, and Anshumali Shrivastava. Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems. arXiv preprint ar X 000.00319, 2019.
[17] Negar Goli and Tor M Aamodt. Resprop: Reuse sparsified backpropagation. In Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1548-1558, 2020.
[18] Edith Cohen and David D Lewis. Approximating matrix multiplication for pattern recognition tasks. Journal of Algorithmss 30(2)2211 1-222, 1999.
[19] Petros Drineas and Ravi Kannan. Fast monte-carlo algorithms for approximate matrix multiplication. In FoCS, volume 1, pages 452-459) 2001.
[20] Petros Drincas, Ravi Kannan, and Michael W Mahoney, Fast monte carlo algorithms for matrices i: Approximating matrix multiplication. SIAM Journal on Computing, 36(1):132 157, 2006.
[21] Avner Magen and Anastasios Zouzias. Low rank matrix-valus valued chernoff bounds and approximate matrix multiplication. In Proceedings the twenty-second annual ACM-SIAM. symposium on Discrete Algorithums, pages 1422-1436. SIAM, 2011.
[22] Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In Foun- dations of Computer Science, 2006, FOCS'06. 47th Annual IEEE Symposium on, pages 143-152, IEEE, 2006.
[23] Kenneth I. Clarkson and David P Woodruff. Numerical linear algehra in the streaming model. In Proceedings the forty-first annual ACM symposium Theory of computing, pages 205-214. ACM, 2009.
[24] Rasmus Pagh. Compressed matrix multiplication. ACM Transactions on Computation Theory (TOCT), 5 (3):9, 2013.
[25] Konstantin Kutzkov, Deterministic algorithms for skewed matrix products. In 30th International Symposium Theoretical Aspects of Computer Science, page 466, 2013.

---

[26] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way prevent neural networks from overfitting. The Journal of Machine Learning Rexearch, 15 (1):1929-1958, 2014.
[27] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in neural information processing systems, pages 8026-8037, 2019.
[28] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86( 1):2788-2322, 1998.
[29] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint arXiv:100.007146. 2016.
[30] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009,
[31] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pottern recognition, pages 770-778, 2016.
[32] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma. Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 1 115(3)211 2015.
[33] Emily L Denton, Wojciech Zaremba, Joan Bruna, Yann LeCun, and Rob Fergus. Exploiting linear structure within convolutional networks for efficient evaluation. In Advances in neural information processing systems, pages 1269-1277, 2014.
[34] Max Jaderberg, Andrea Vedaldi, and Andrew Zisserman. Speeding up convolutional neural networks with low rank expansions. In Proceedings of the British Machine Vision Conference. BMVA Press, 2014.
[35] Vadim Lehedev, Yaroslav Ganin, Maksim Rakhuba, Ivan Oscledets, and Victor Lempitsky. Speeding-up convolutional neural networks using fine-tuned cp-decomposition. arXiv preprint arXiv:1412.6553, 2014.
[36] Kazuki Osawa, Akira Sekiya, Hiroki Naganuma, and Rio Yokota. Accelerating matrix multiplication in deep learning by using low-rank approximation. In High Performance Computing & &Simulation (HPCS), 2017 International Conference on, pages 186-192. IEEE, 2017.
[37] Yunchao Gong, Liu Liu, Ming Yang, and Lubomir Bourdey. Compressing deep convolutional networks using vector quantization. arXiv preprint 14 15, 2014.
[38] Song Han, Huizi Mao, and William J Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv: 100.0009,, 2015
[39] Xu Sun, Xuancheng Ren, Shuming Ma. Bingzhen Wei, Wei Li. and Houfeng Wang. Training simplification and model simplification for deep learning: A minimal effort back propagation method, arXiv preprint 171iv:1111, 006528,, 2017.
[40] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint 2009 14794, 2020.
[41] Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXivv2006.04700 04768, 2020.
[42] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint 22Xiv:200100455/ 2020.
[43] Thijs Vogels, Sai Pranccth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compression for distributed optimization. arXiv preprint arXiv:190S 13727, 2019.
[44] Gao Huang, Yu Sun, Zhuang Liu, Daniel Sedra, and Kilian Q Weinherger. Deep networks with stochastic depth. In European conference on computer vision, pages 646-661. Springer, 2016.
[45] Sida Wang and Christopher Manning. Fast dropout training. In international conference on machine learning, pages 118-126. PMLR, 2013.
[46] Ben Graham, Jeremy Reizenstein, and Leigh Robinson. Efficient batchwise dropout training using submatrices. arXiv preprint arXiv:1502.024722 2015.
12

---

[47] Zhe Li, Boqing Gong, and Tianbao Yang. Improved dropout for shallow and deep learning. In Advances in Neural Information Processing Systems, pages 2523-2531, 2016.
[48] Saihui Hou and Zilei Wang. Weighted channel dropout for regularization of deep convolutional neural network. In Proceedings the AAAI Conference Artificial Intelligence, volume 33, pages 8425 8432, 2019.
[49] Stefan Wager, Sida Wang, and Percy Liang. Dropout training adaptive regularization. Advances in neural information processing systems, pages 351-359, 2013.
[50] Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient tensor decomposition. Conference on Learning Theory, pages 797-842. 2015.
[51] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. Proceedings of the thirteenth international conference on artificial intelligence and statistics. pages 249-256. JMLR Workshop and Conference Proceedings, 2010.
[52] Charles Blundell, Julien Cornebise, Koray Kavukeuoglu, and Daan Wierstra. Weight uncertainty neural network. In International Conference on Machine Learning, pages 1613-1622. PMLR, 2015.
[53] Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections efficient neural networks. arXiv preprint D.XXvx:506.002222. 2015.
[54] Martin Thoma. Analysis and optimization of convolutional neural network architectures. arXiv preprint IXXv::707.00972. 2017.
[55] Zhongzhan Huang, Wenqi Shao, Xinjiang Wang. and Ping Luo. Convolution Convolution-weight-liis weight-distribution assump- tion: Rethinking the criteria of channel pruning, arXiv preprint arXiv:2004.1162) 2020.
[56] Dimitri P Bertsekas John Tsitsiklis. Neuro-dynamic progranming. Athena Scientific, 1996.
[57] Joel Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathematics, 12(4):389-434, 2012.
[58] Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv: 141666900 2014.
13


Reviews:
[{"review_id": "ob5VWc80V7Z", "reviewer": "Reviewer_nbsG", "summary": "This paper adapts the CRS method for approximate matrix multiplication into a new method, Bernoulli-CRS, that yields unbiased gradient estimates. The paper then analyzes this method on linear regression and shows the new method and giving unbiased estimates of a gradient for the original objective with a regularization term. They then devise a new routine for approximate backpropagation that has unbiased estimates with bounded second moments. The paper then introduces a deterministic variant called top-k sampling and show the performance of the 3 methods (CRS, Bernoulli-CRS, top-k) in experiments in terms of performance, compute, and speed.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "Originality - A somewhat novel adaptation to a pre-existing method that addresses some of the problem to applying it in a deep learning context.\n\nQuality - The theory for approximate backpropagation seem applicable to practice and justify the use of this method. However, its not immediately clear whether it applies to ResNets, which is the only network architecture used on larger datasets. Furthermore, there is no justification for the use of this method in the forward pass, so it would be good to have some explanation for why it approximating the forward and backward pass performs so well, and in particular, why it outperforms only approximating the backward pass.\n\nClarity - Overall the presentation is clear and organized. However, the section describing the practical applicability of Theorem 2 is unclear. While the theorem is easily applicable at initialization with independent zero-mean entries, its not clear what it means after any number of iterations. In particular, the backpropagation of a gradient signal should introduce dependencies between the weights, so the pairwise-independence is almost immediately violated.\nAs well, in line 230 the phrase \"if the distribution remains centered around zero during training\" isn't entirely clear to me. Given that standard NN training only takes a point initialization and not a distribution around each weight, I'm not sure what it means to be \"centered around zero during training\". The discussion in the experiments section seems to imply something like the distribution generated by the trajectory of the weight, but it's not clear.\nThe conclusions reached in the linear regression sections aren't totally clear. The CRS method was deemed suboptimal since it would not yield unbiased gradient estimates; however, the Bernoulli-CRS was concluded to have the property of an expected gradient equal to one for linear regression with an additional regularization term -- so this too is not an unbiased gradient estimate. It seems you may also be able to recast the expected gradient from CRS as a linear regression + regularization gradient (but I didn't do the math so may it doesn't exactly work out). Because of that, it's not clear why one method is preferable to the other in this linear regression toy problem.\n\nSignificance - The experimental results show promising speedups with little loss in performance. This can be particularly useful in cases where there are many networks being trained to find the best, such NAS or an ablation study. Some more analysis about the effects of Bernoulli-CRS would be required before standard use of the method, as there may be implicit regularization effects by this method (as seen in the linear regression case) and maybe other effects that aren't obvious. The main reason for worry is that the only approximate the backward pass caused big performance degradation in the larger networks even though that seems quite well understood by the theory; on the other hand, approximate the forward as well improved performance but is not really understood theoretically.\n\nMinor Note - In equations 5, 11, 15, should the sum go up to n rather than k?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations - There's a discrepancy between practice and theory where it seems practically you need to approximate both directions but the theory only supports the backward pass.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "ZwyGt5nEOzA", "reviewer": "Reviewer_pWRo", "summary": "This paper proposes a method for speeding up training by approximating the computation of linear and convolutional layers. The approximation of such operation is done by taking K samples of the operands (e.g. K row-column pairs in a matrix multiplication) instead of multiplying them directly. The authors motivate the use of the CRS algorithm because is lightweight, can be applied to matrices/tensors of all shapes and, it is unbiased. The authors then study its use in Linear Regression settings and Convolutional layers and, propose their own Bernoulli-based sampling strategy. The authors evaluate their approximate training scheme on common image classification tasks, including a distributed learning scenario.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "This paper touches upon an important problem that arises in two radically different settings: first when training massive models, even when hyperparamters (e.g. batch-size, number of nodes, etc) are correct, being able to approximate the compute could give that extra 1.5x  to make the experiment finish in a more reasonable time frame; second, when training small or medium size models on very constrained devices like in wearables, which are both compute and memory restricted and (!) battery powered. In essence both scenarios are similar in the sense that both push the hardware to the limit. As authors point out, there are other ways of introducing “approximations”, being quantization the most widely used in practice.\n\nThe paper is very well written, the notation is easy to follow. As the authors refer in their work, there have been a number of works proposing ways of speeding up training by using approximations. Two works that weren’t cited but are relevant are [1], [2]. \n\nTo revise/improve/expand:\n\n- My main concerns are regarding the length of the evaluation section and number of experiments in general.  Given the number of other works attempting to also speedup training, I would say that the proposed method, which emphasises on *sampling*, would benefit from evaluating scenarios/models/datasets where *sampling* would have an advantage over the other techniques. \n- Someone could argue that the model architectures chosen (WRN-28-10 for CIFAR-10 or ResNet-152) are overparameterized for each tasks, making it easier for the algorithm proposed to show higher compute reduction rations. It would be interesting to show how the technique proposed in this work could speedup networks that have already been pruned or quantized.\n- (minor) I would advice improving the captions of the figures and tables to make them more self-contained. For example, what are the differences between each of the rows for ResNet-152 @ 8 nodes?\n- Could the method proposed in this paper be interpreted as a (unstructured) pruning technique? Specially when using Top-K selection. Could the authors comment upon this?\n- (for the future), the space of efficient training is getting busy. Looking into specific (instead of generic image classification workload) areas where ML is currently limited could be a good way to making the sampling technique here propose really shine. Going back to the previous paragraph, I think this technique could be valuable for on-device training in scenarios with limited compute/memory capabilities (e.g. federated learning on wearables/phones)\n\n[1] [ReSprop](https://openaccess.thecvf.com/content_CVPR_2020/html/Goli_ReSprop_Reuse_Sparsified_Backpropagation_CVPR_2020_paper.html)\n\n[2] [Backprop with Approximate Activations](https://arxiv.org/abs/1901.07988)\n\n### Update\nPost rebuttal update, I raise my score from 4 to 6. (see comment below for reasons).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- Limited evaluation of the proposed method.\n- No clear advantage over existing techniques (e.g. gradient sparsification) that are evaluated on standard image classification tasks.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "ShINj0a5EXW", "reviewer": "Reviewer_G6cy", "summary": "This paper focuses on unbiased approximations to matrix multiplication and\nconvolution computations in deep neural networks (DNNs). The aim is to\nreduce the complexity of these computations without the resulting function\nthe network as a whole computes. As practically all of the computation in\na deep network is expended in matrix multiplications and convolutions this\nwould provide a global acceleration. In practice this work demonstrates\n4-37% improvement in training speed on ImageNet, depending on how the\ncomputation is distributed.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "## Originality\n\n> Are the tasks or methods new? Is the work a novel\n> combination of well-known techniques? (This can be valuable!) Is it clear\n> how this work differs from previous contributions? Is related work\n> adequately cited?\n\nApproximating matrix multiplications with stochastic algorithms is a large\narea of inquiry in numerical computing. The authors apply this to the\nmatrix multiplications that are performed during training of a deep neural\nnetwork to make training more efficient. \n\nThe authors provide a good review in Section 2.1 of related work in the are\nof approximate matrix multiplication, not limited to stochastic algorithms.\nIt is clear that it would be useful to find out if the CRS algorithm can be\napplied in training deep neural networks.\n\nOne of the main findings of this work is:\n\n> ...we propose a new _Bernoulli-CRS_ variant which achieves statistical\n> independence of samples, study its properties, and show that in linear\n> regression it is equivalent to dynamic $L_2$ weight regularisation of the\n> original, non-approximate loss.\n\nHowever, the relationship between a Bernoulli noise mask (dropout) has been\nknown since [Fast Dropout][fast] in 2013. In addition, the method designed\nin that work also was used to speed up training and appears to speed up\ntraining more than 50% on MNIST, as presented here. However, they do not\npresent results on larger datasets as that was not expected at the time.\n\nThe extension to top-$k$ selection is novel to my knowledge. It is a\nnatural extension to the CRS approximation and is well explored in theory\nand experiment by this work.\n\n[fast]: http://proceedings.mlr.press/v28/wang13a.html\n\n## Quality\n\n> Is the submission technically sound? Are claims well supported\n> (e.g., by theoretical analysis or experimental results)? Are the methods\n> used appropriate? Is this a complete piece of work or work in progress? Are\n> the authors careful and honest about evaluating both the strengths and\n> weaknesses of their work?\n\nThe argument of the paper is delivered clearly. The use of CRS is well\nmotivated and argued in theory. The experiments then demonstrate that this\nmethod can improve the efficiency of a neural network in training. It is\nclear that the method should work and it does work.\n\nThe motivation behind the Top-$k$ selection algorithm to further improve\non CRS is sound. It is investigated in experiment and theory correctly. It\nis clear that it works and is an improvement over CRS.\n\nSection 7 describes how the algorithm may be extended to apply to\nconvolution. It seems unnecessary to include this as a common method to\nimplement convolution is the im2col-gemm algorithm and this involves a\nmatrix multiplication that CRS trivially applies to.\n\nWhile the experiments show that the methods work, the authors do not\ninvestigate the effect of hyperparameters. The training speed improvements\nobserved are relatively small and could be affected by learning rate,\nregularisation, architecture. The stochastic algorithm itself could affect\nconvergence to the target accuracy by operating as a regulariser in a\nsimilar way to dropout.\n\nFor example, in the [fast dropout][fast] paper the\nauthors specifically aimed to remove the random noise added by dropout\nusing better regularisation to speed up the experiment.\n\nIt is not clear to me that this training speedup would remain stable across\narchitectures or hyperparameter choices.\n\n[fast]: http://proceedings.mlr.press/v28/wang13a.html\n\n## Clarity\n\n> Is the submission clearly written? Is it well organized? (If not, please\n> make constructive suggestions for improving its clarity.) Does it\n> adequately inform the reader? (Note that a superbly written paper provides\n> enough information for an expert reader to reproduce its results.)\n\nThe ideas in this paper are presented in a natural sequence that is easy to\nfollow. The reader is able to follow easily the chain of reasoning that\nleads from CRS to top-$k$ sampling for approximating matrices and why these\ncould be useful in deep learning.\n\nSection 4 is titled \"Bernoulli Sampling\" and this could be misleading for\nsome readers because the algorithm being described is known as [Poisson\nSampling][poisson]. However, the name Poisson sampling may also be\nmisleading to readers that assume that samples will be drawn from a Poisson\ndistribution. Another name entirely may be more appropriate.\n\nI feel confident I could reproduce the results presented in this paper\nusing the description in main body of the text.\n\n[poisson]: https://en.wikipedia.org/wiki/Poisson_sampling\n\n## Significance\n\n> Are the results important? Are others (researchers or practitioners) likely\n> to use the ideas or build on them? Does the submission address a difficult\n> task in a better way than previous work?  Does it advance the state of the\n> art in a demonstrable way? Does it provide unique data, unique conclusions\n> about existing data, or a unique theoretical or experimental approach?\n\nUniversally improving the efficiency of matrix multiplications in deep\nlearning would be a valuable addition to the field. Unfortunately, it is\nnot clear to me that the methods presented in this paper are able to do\nthat.\n\nHowever, an investigation of whether these methods can be used in deep\nlearning is valuable as a reference to future work. I think that this work\ncould provide unique results in that area that will be useful for future\nresearchers.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The experiments in this paper do not compare against other methods that\naim to reduce the complexity of matrix multiplications in deep learning.\nThe authors could compare against methods that replace the matrix\nmultiplications with other algorithms, such as [FFTs][] or [Tensor\nnetworks][tt] or other methods listed in Section 2.1.\n\n[ffts]: https://arxiv.org/abs/1511.05946\n[tt]: https://epubs.siam.org/doi/abs/10.1137/090752286", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "LGP1HkcJuEq", "reviewer": "Reviewer_yvhy", "summary": "The paper proposes to approximate matrix multiplications (and convolutions) by randomly sampling column-row pairs and only multiplying submatrices. This is used to compute stochastic gradients which subsequently speed up training. Different sampling modes are presented and compared in experiments. Theoretical and practical training speed-ups are reported on standard architectures and datasets.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The paper is very well written and easy to follow. It considers an important problem and the idea of speeding up training in the proposed way is (to my knowledge) a novel and worthy contribution.\n\nReducing training time is especially important on datasets on which training takes very long. Therefore, more results on ImageNet are required. Results from the appendix using top-k show that accuracy degrades substantially for slight theoretical reductions in training time (e.g., Fig. 10a). There seem to be no results for CRS/Bernoulli on ImageNet. Figure 1a suggests that it might be possible that CRS/Bernoulli provides a better approximation for lower computational budgets. This needs to be verified. Furthermore, it would be interesting to see if more epochs would result in the original accuracy, e.g., twice as many epochs at 50% computations per iteration.\n\nHow can you explain that Eq. (12) produces worse results although it appears to be unbiased? The only way I see is that it substantially increases variance. It would be interesting to verify this and put a short comment on that in text. The same is true for the method presented in Section 5 where only the backward pass is approximated, which does not seem to produce better results (see lines 281/282).\n\nLine 192 says that the estimates are unbiased. However, line 197 says that there is an additional regularization term induced. In my opinion you cannot really consider this to be an unbiased estimate of the original loss function then.\n\nLine 137 says that improved accuracies due to regularization were not observed. However, it is later shown that the induced loss function obtained for Bernoulli sampling has an additional regularization term (Eq. (17)). This is somehow contradictory and requires clarification. In fact, the induced regularizer (17) reminds me of results from [1]. What is the difference to [1].\n\nLine 165 says that the Expectation E[S_jj S_tt] is not equal to 1 because S_jj and S_tt are not independent. I do not immediately see why independence would imply that the expectation equals 1. Could you please clarify that for me.\n\nI am missing some kind of summary / takeaway message of the findings in the conclusion section?\n\nMinor: \n- line 150: single dot \".\" looks strange\n\n[1] Wager et al.; Dropout Training as Adaptive Regularization; NIPS 2013", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Sufficiently addressed (limitations: see above)", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a method for approximating the matrix multiplication and convolution operations in neural networks. Theoretical results show that the gradient estimates are robust to the approximation applied in the backwards pass (but not necessarily the forwards pass). Experiments show that the number of computations can be reduced significantly without degrading test accuracy.

Reviewers generally feel like the paper is sound overall, without significant gaps in correctness or discussion of prior work. They had various specific comments which they feel were mostly addressed in the author response. However, the reviewers kept their scores at middling values, due to concerns about whether the method translates into significant wall clock gains, whether it outperforms other approximations, and whether the noise robustness will extend to other architectures. These are all valid concerns, but this approach seems like worthwhile addition to the toolbox, and the authors have validated it in a reasonable variety of situations. I'd favor acceptance.

Decision: Accept (Poster)