Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper focuses on unbiased approximations to matrix multiplication and
convolution computations in deep neural networks (DNNs). The aim is to
reduce the complexity of these computations without the resulting function
the network as a whole computes. As practically all of the computation in
a deep network is expended in matrix multiplications and convolutions this
would provide a global acceleration. In practice this work demonstrates
4-37% improvement in training speed on ImageNet, depending on how the
computation is distributed.
main_review: ## Originality

> Are the tasks or methods new? Is the work a novel
> combination of well-known techniques? (This can be valuable!) Is it clear
> how this work differs from previous contributions? Is related work
> adequately cited?

Approximating matrix multiplications with stochastic algorithms is a large
area of inquiry in numerical computing. The authors apply this to the
matrix multiplications that are performed during training of a deep neural
network to make training more efficient. 

The authors provide a good review in Section 2.1 of related work in the are
of approximate matrix multiplication, not limited to stochastic algorithms.
It is clear that it would be useful to find out if the CRS algorithm can be
applied in training deep neural networks.

One of the main findings of this work is:

> ...we propose a new _Bernoulli-CRS_ variant which achieves statistical
> independence of samples, study its properties, and show that in linear
> regression it is equivalent to dynamic $L_2$ weight regularisation of the
> original, non-approximate loss.

However, the relationship between a Bernoulli noise mask (dropout) has been
known since [Fast Dropout][fast] in 2013. In addition, the method designed
in that work also was used to speed up training and appears to speed up
training more than 50% on MNIST, as presented here. However, they do not
present results on larger datasets as that was not expected at the time.

The extension to top-$k$ selection is novel to my knowledge. It is a
natural extension to the CRS approximation and is well explored in theory
and experiment by this work.

[fast]: http://proceedings.mlr.press/v28/wang13a.html

## Quality

> Is the submission technically sound? Are claims well supported
> (e.g., by theoretical analysis or experimental results)? Are the methods
> used appropriate? Is this a complete piece of work or work in progress? Are
> the authors careful and honest about evaluating both the strengths and
> weaknesses of their work?

The argument of the paper is delivered clearly. The use of CRS is well
motivated and argued in theory. The experiments then demonstrate that this
method can improve the efficiency of a neural network in training. It is
clear that the method should work and it does work.

The motivation behind the Top-$k$ selection algorithm to further improve
on CRS is sound. It is investigated in experiment and theory correctly. It
is clear that it works and is an improvement over CRS.

Section 7 describes how the algorithm may be extended to apply to
convolution. It seems unnecessary to include this as a common method to
implement convolution is the im2col-gemm algorithm and this involves a
matrix multiplication that CRS trivially applies to.

While the experiments show that the methods work, the authors do not
investigate the effect of hyperparameters. The training speed improvements
observed are relatively small and could be affected by learning rate,
regularisation, architecture. The stochastic algorithm itself could affect
convergence to the target accuracy by operating as a regulariser in a
similar way to dropout.

For example, in the [fast dropout][fast] paper the
authors specifically aimed to remove the random noise added by dropout
using better regularisation to speed up the experiment.

It is not clear to me that this training speedup would remain stable across
architectures or hyperparameter choices.

[fast]: http://proceedings.mlr.press/v28/wang13a.html

## Clarity

> Is the submission clearly written? Is it well organized? (If not, please
> make constructive suggestions for improving its clarity.) Does it
> adequately inform the reader? (Note that a superbly written paper provides
> enough information for an expert reader to reproduce its results.)

The ideas in this paper are presented in a natural sequence that is easy to
follow. The reader is able to follow easily the chain of reasoning that
leads from CRS to top-$k$ sampling for approximating matrices and why these
could be useful in deep learning.

Section 4 is titled "Bernoulli Sampling" and this could be misleading for
some readers because the algorithm being described is known as [Poisson
Sampling][poisson]. However, the name Poisson sampling may also be
misleading to readers that assume that samples will be drawn from a Poisson
distribution. Another name entirely may be more appropriate.

I feel confident I could reproduce the results presented in this paper
using the description in main body of the text.

[poisson]: https://en.wikipedia.org/wiki/Poisson_sampling

## Significance

> Are the results important? Are others (researchers or practitioners) likely
> to use the ideas or build on them? Does the submission address a difficult
> task in a better way than previous work?  Does it advance the state of the
> art in a demonstrable way? Does it provide unique data, unique conclusions
> about existing data, or a unique theoretical or experimental approach?

Universally improving the efficiency of matrix multiplications in deep
learning would be a valuable addition to the field. Unfortunately, it is
not clear to me that the methods presented in this paper are able to do
that.

However, an investigation of whether these methods can be used in deep
learning is valuable as a reference to future work. I think that this work
could provide unique results in that area that will be useful for future
researchers.
limitations_and_societal_impact: The experiments in this paper do not compare against other methods that
aim to reduce the complexity of matrix multiplications in deep learning.
The authors could compare against methods that replace the matrix
multiplications with other algorithms, such as [FFTs][] or [Tensor
networks][tt] or other methods listed in Section 2.1.

[ffts]: https://arxiv.org/abs/1511.05946
[tt]: https://epubs.siam.org/doi/abs/10.1137/090752286
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

Quality - 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.

Clarity - 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.
As 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.
The 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.

Significance - 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.

Minor Note - In equations 5, 11, 15, should the sum go up to n rather than k?
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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

Reducing 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.

How 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).

Line 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.

Line 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].

Line 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.

I am missing some kind of summary / takeaway message of the findings in the conclusion section?

Minor: 
- line 150: single dot "." looks strange

[1] Wager et al.; Dropout Training as Adaptive Regularization; NIPS 2013
limitations_and_societal_impact: Sufficiently addressed (limitations: see above)
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.

The 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]. 

To revise/improve/expand:

- 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. 
- 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.
- (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?
- 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?
- (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)

[1] [ReSprop](https://openaccess.thecvf.com/content_CVPR_2020/html/Goli_ReSprop_Reuse_Sparsified_Backpropagation_CVPR_2020_paper.html)

[2] [Backprop with Approximate Activations](https://arxiv.org/abs/1901.07988)

### Update
Post rebuttal update, I raise my score from 4 to 6. (see comment below for reasons).
limitations_and_societal_impact: - Limited evaluation of the proposed method.
- No clear advantage over existing techniques (e.g. gradient sparsification) that are evaluated on standard image classification tasks.
review_title: null

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)