Venue: ICLR 2018 conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposes replacing fully connected layers with block-diagonal fully connected layers and proposes two methods for doing so.  It also make some connections to random matrix theory.

The parameter pruning angle in this paper is fairly weak.  The networks it is demonstrated on are not particularly large (largeness usually being the motivation for pruning) and the need for making them smaller is not well motivated.  Additionally MNIST is a uniquely bad dataset for evaluating pruning methods, since they tend to work uncharacteristically well on MNIST (This can be seen in some of the references the paper cites).

The random matrix theory part of this paper is intriguing, but left me wondering "and then what?"  It is presented as a collection of observations with no synthesis or context for why they are important.  I'm usually quite happy to see connections being made to other fields, but it is not clear at all how this particular connection is more than a curiosity.  This paper would be much stronger if it offered some way to exploit this connection.

There are two half-papers here, one on parameter pruning and one on applying insights from random matrix theory to neural networks, but I don't see a strong connection between them. Moreover, they are both missing their other half where the technique or insight they propose is exploited to achieve something. 

review_title: A lack of synthesis.

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper proposes to make the inner layers in a neural network be block diagonal, mainly as an alternative to pruning. The implementation of this seems straightforward, and can be done either via initialization or via pruning on the off-diagonals. There are a few ideas the paper discusses:

(1) compared to pruning weight matrices and making them sparse, block diagonal matrices are more efficient since they utilize level 3 BLAS rather than sparse operations which have significant overhead and are not "worth it" until the matrix is extremely sparse. I think this case is well supported via their experiments, and I largely agree.

(2) that therefore, block diagonal layers lead to more efficient networks. This point is murkier, because the paper doesn't discuss possible increases in *training time* (due to increased number of iterations) in much detail. At if we only care about running the net, then reducing the time from 0.4s to 0.2s doesn't seem to be that useful (maybe it is for real-time predictions? Please cite some work in that case)

(3) to summarize points (1) and (2), block diagonal architectures are a nice alternative to pruned architectures, with similar accuracy, and more benefit to speed (mainly speed at run-time, or speed of a single iteration, not necessarily speed to train)

[as I am not primarly a neural net researcher, I had always thought pruning was done to decrease over-fitting, not to increase computation speed, so this was a surprise to me; also note that the sparse matrix format can increase runtime if implemented as a sparse object, as demonstrated in this paper, but one could always pretend it is sparse, so you never ought to be slower with a sparse matrix]

(4) there is some vague connection to random matrices, with some limited experiments that are consistent with this observation but far from establish it, and without any theoretical analysis (Martingale or Markov chain theory)

This is an experimental/methods paper that proposes a new algorithm, explained only in general details, and backs up it up with two reasonable experiments (that do a good job of convincing me of point (1) above). The authors seem to restrict themselves to convolutional networks in the first paragraph (and experiments) but don't discuss the implications or reasons of this assumption. The authors seem to understand the literature well, and not being an expert myself, I have the impression they are doing a fair job.


The paper could have gone farther experimentally (or theoretically) in my opinion. For example, with sparse and block diagonal matrices, reducing the size of the matrix to fit into the cache on the GPU must obviously make a difference, but this did not seem to be investigated. I was also wondering about when 2 or more layers are block sparse, do these blocks overlap? i.e., are they randomly permuted between layers so that the blocks mix? And even with a single block, does it matter what permutation you use? (or perhaps does it not matter due to the convolutional structure?)

The section on the variance of the weights is rather unclear mathematically, starting with the abstract and even continuing into the paper. We are talking about sample variance? What does DeltaVar mean in eq (2)? The Marchenko-Pastur theorem seemed to even be imprecise, since if y>1, then a < 0, implying that there is a nonzero chance that the positive semi-definite matrix XX' has a negative eigenvalue.

I agree this relationship with random matrices could be interesting, but it seems too vague right now. Is there some central limit theorem explanation? Are you sure that you've run enough iterations to fully converge? (Fig 4 was still trending up for b1=64). Was it due to the convolutional net structure (you could test this)? Or, perhaps train a network on two datasets, one which is not learnable (iid random labels), and one which is very easily learnable (e.g., linearly separable). Would this affect the distributions?

Furthermore, I think I misunderstood parts, because the scaling in MNIST and CIFAR was different and I didn't see why (for MNIST, it was proportional to block size, and for CIFAR it was independent of block size almost).

Minor comment: last paragraph of 4.1, comparing with Sindhwani et al., was confusing to me. Why was this mentioned? And it doesn't seem to be comparable. I have no idea what "Toeplitz (3)" is.
review_title: Block diagonal is more efficient that sparse formats and can be used effectively; other parts of paper are vague

final_score: rating: 5: Marginally below acceptance threshold
review_content: This is a mostly experimental paper which evaluates the capabilities of neural networks with weight matrices that are block diagonal. The authors describe two methods to obtain this structure: (1) enforced during training, (2) enforced through regularization and pruning. As a second contribution, the authors show experimentally that the random matrix theory can provide a good model of the spectral behavior of the weight matrix when it is large. However, the authors only conjecture as to the potential of this method without describing clear ways of approaching this subject, which somewhat lessens the strength of their argument.

Quality: this paper is of good quality
Clarity: this paper is clear, but would benefit from better figures and from tables to report the numerical results instead of inserting them into plain text.
Originality: this paper introduces block diagonal matrices to structure the weights of a neural network. The idea of structured matrices in this context is not new, but the diagonal block structure appears to be.  
Significance: This paper is somewhat significant.

PROS 
- A new approach to analyzing the behavior of weight matrices during learning
- A new structure for weight matrices that provides good performance while reducing matrix storage requirements and speeding up forward and backward passes.

CONS
- Some of the figures are hard to read (in particular Fig 1 & 2 left) and would benefit from a better layout.
- It would be valuable to see experiments on bigger datasets than only MNIST and CIFAR-10. 
- I understand that the main advantage of this method is the speedup; however, providing the final accuracy as a function of the nonzero entries for slower methods (e.g. the sparse pruning showed in Fig 1. a) would provide a more complete picture.

Main questions:
- Could you briefly comment on the training time in section 4.1? 
- Could you elaborate on the last sentence of section 4.1?
- You state: "singular values of an IP layer behave according to the MP distribution even after 1000s of training iterations." Is this a known fact, or something that you observed empirically? In practice, how large must the weight matrix be to observe this behavior?

Nitpicks:
- I believe the term "fully connected" is more standard than "inner product" and would add clarity to the paper, but I may be mistaken. 
review_title: A mostly experimental paper using block diagonal weight matrices for NN pruning, with valuable insights into random matrix theory to model weight behavior.

Meta-review: The authors propose a technique for weight pruning that leaves block diagonal weights, instead of unstructured sparse weights, leading to faster inference.  However, the experiments demonstrating the quality of the pruned models are insufficient.   The authors also discuss connections to random matrix theory; but these connections are not worked out in detail.
Decision: Reject