Low-Rank Approximations for Conditional Feedforward Computation in Deep Neural Networks
Authors: Andrew Davis, Itamar Arel
ICLR 2014

Abstract: Scalability properties of deep neural networks raise key research questions, particularly as the problems considered become larger and more challenging. This paper expands on the idea of conditional computation introduced by Bengio, et. al., where the nodes of a deep network are augmented by a set of gating units that determine when a node should be calculated. By factorizing the weight matrix into a low-rank approximation, an estimation of the sign of the pre-nonlinearity activation can be efficiently obtained. For networks using rectified-linear hidden units, this implies that the computation of a hidden unit with an estimated negative pre-nonlinearity can be ommitted altogether, as its value will become zero when nonlinearity is applied. For sparse neural networks, this can result in considerable speed gains. Experimental results using the MNIST and SVHN data sets with a fully-connected deep neural network demonstrate the performance robustness of the proposed scheme with respect to the error introduced by the conditional computation process.


Peer review:
[Review]:
The authors investigate a proposed method of speeding up computation in a feed-forward ReLU network by predicting the sign of the presynaptic activations with a low-rank predictor obtained by SVD on the weights.

Novelty: medium
Quality: low

Pros:
- Investigates a problem of substantial interest to the community, that of scaling up neural nets through what Yoshua Bengio has dubbed “conditional computation”
- Experimental procedures are well documented, software cited

Cons:
- misinterprets the goals articulated by Bengio on conditional computation: namely, to explicitly learn which computations to do/which parts of an architecture to activate, rather than simply identify ways of speeding up existing architectures through predictive computation. In that respect it could still be an interesting line of inquiry but not really “conditional computation” related.
- Provides no empirical benchmarking: I strongly suspect an empirical investigation of the proposed speedup would reveal that the cache unfriendliness of the non-uniform memory access would result in a significant slowdown even for large, relatively sparse network.
- The commentary contains several instances of speculation that is not qualified as such (see below)
- The experimental baselines are questionable, uninteresting, and applying the same sort of fully connected architecture to only two tasks, one of which has not been widely studied with fully-connected networks and thus hard to judge. Especially in the first layer it seems like the efficacy of the low rank predictor may depend heavily on the input distribution.

Detailed comments:

Sec 2.1:
- The speculation that parameter redundancy leads to activation redundancy is very questionable. Consider two filters consisting of oriented, localized edge filters, one appearing exclusively in the upper left quadrant of the receptive field and the other appearing in the lower right, with 3 of 4 quadrants having zero weights in each filter. The two have extremely redundant parameters (only a few bits are needed to describe one given knowledge of the other), but their activations are not redundant in the least.

Sec 2.2:
- Both of the datasets on which you run experiments have had extremely competitive (state of the art, in the case of SVHN) performance documented with maxout activations, where activities are completely non-sparse. The importance of representational sparsity is thus far less clear than you seem to suggest.

Sec 3.1:
- Notational comment: sigma() is typically reserved for the logistic function, or at least a sigmoidal function such as tanh. Its use to represent the ReLU activation is somewhat jarring. 
- You can probably assume that a reader of this paper understands how to perform matrix multiplication. The exposition in terms of dot products is unnecessary.
- Regarding considerable speed gains, I find this dubious given the degree to which optimized matrix-matrix multiplication libraries (the BLAS, etc.) leverage the properties of today’s CPU and GPU hardware. In sparse linear algebra applications where sheer memory requirements are not the limiting factor (i.e. making explicitly representing the sparse matrix infeasible), sparsity well in excess of 99% is typically necessary for specialized sparse matrix multiplication routines to beat BLAS on a sparse problem represented densely. While you may be able to claim an asymptotic speedup, it’s unclear whether this means anything in practice for a wide class of problems of interest. Even if things are sparse enough for there to be a savings, it’s unclear whether this would be negated by the necessity of performing the low-rank computation as well.
- It would be interesting and comforting to see some analysis (theoretical or empirical) of the probability of the low rank approximation making a mistake (and each kind of mistake, as mistakenly flagging a filter response as having a positive value results in no actual error being made in the final analysis, as it will be computed and then presumably thresholded to zero, whereas not computing one that should’ve been positive will affect the representation passed up to the next layer). If you assume bounded norms of the weight vectors I’m fairly sure you could say something theoretically as a function of the rank of the approximation.
- I’d also be interested in how the activation estimator’s efficacy differs for the first layer and subsequent layers, given that the latter have a more sparse input distribution, and whether preprocessing helps or not. Similarly, how does error accumulate through this process when you use it at multiple layers?

Sec 3.4:
- multiplying an asymptotic O(...) expression by a constant makes no sense. O() notation is explicitly defined to absorb all multiplicative constants. What you should do instead is either a) make use of a numerical methods textbook pseudocode implementation of SVD to bound the number of theoretical flops, or b) drop the O(...), add a multiplicative constant (which you could bound) and add O(...)’s for the lower-order terms.

Sec 4.1 & 4.2
- Generally, the lack of comparison to the literature for your baselines is troubling. I don’t know what the state of the art is for a permutation-invariant method (such as a fully connected network) on SVHN, but your nets seem critically underresourced. I know that layer sizes for an MNIST network achieving close to 1% typically features layer sizes at least double those of what you report, and it seems like you are underfitting significantly on SVHN. The whole point of conditional computation is to save computation time in very large models, but you restrict your investigation to extremely impoverished architectures.
- Your MNIST results are significantly worse with what is the permutation-invariant state of the art standard nowadays and there’s really no excuse for it, an error of 1.05-1.06% is easily reproducible. At the very least it would frame the error rates in terms of results with which people are familiar.
- The architectures of the activation estimators seem arbitrary and it is not clear how they were chosen, or why a wider variety were not explored.
- In addition to the error rates for various activation estimator architectures, you should make clear the theoretical speedup provided by this architecture, and the measured empirical speedup.

Section 5:
- The extension to the convolutional setting is not obvious to me at all. Sure, you can write out the convolution as a matrix multiply with a structured sparse matrix but the SVD of that is going to be dense and gigantic.
- There’s no mention of the possibility of learning the low-rank approximation, which seems like the natural thing to do, especially as concerns test-time speed-up rather than train-time speedup. I also consider it critical to compare against the case where there is no full rank weight matrix, just this low rank version being used as the actual weight matrix, to show that maintaining and carefully multiplying by the full rank weight matrix actually is in some respect a necessary ingredient. If you can get away with simply learning factored weight matrices (i.e. introducing bottleneck linear layers) then this scheme is needlessly complicated.