The Description Length of Deep Learning Models
Solomonoff's general theory of inference (Solomonoff, 1964) and the Minimum Description Length principle (Grünwald, 2007;Rissanen, 2007) formalize Occam's razor, and hold that a good model of data is a model that is good at losslessly compressing the data, including the cost of describing the model itself. Deep neural networks might seem to go against this principle given the large number of parameters to be encoded. We demonstrate experimentally the ability of deep neural networks to compress the training data even when accounting for parameter encoding. The compression viewpoint originally motivated the use of variational methods in neural networks (Hinton and Van Camp, 1993;Schmidhuber, 1997). Unexpectedly, we found that these variational methods provide surprisingly poor compression bounds, despite being explicitly built to minimize such bounds. This might explain the relatively poor practical performance of variational methods in deep learning. On the other hand, simple incremental encoding methods yield excellent compression values on deep networks, vindicating Solomonoff's approach.
Summary :   The paper considers the problem of minimum description length of any model - resting on the conjecture (as supported by Solomonoff’s general theory of inference and the Minimum Description Length) that a good model must compress the date along with its parameters well. Thus generalization is heuristically linked to compressive power of the model. With their experimental results, the authors surprise showing good overall compressive power of Deep Learning models using the prequential coding approach.  Relating to the "Chaitin’s hypothesis [Cha07] that “comprehension is compression” any regularity in the data can be exploited both to compress it and to make predictions", the authors focus only on the compression problem .  Detailed Comments:  Clarity: The paper in well written and presents a good survey of the related work.  Originality: There is no theory in the paper. The paper presents an empirical study of the possible confirmation of the Chaitin’s hypothesis [Cha07]  that DL generalizes as it compresses well too, i.e., it has small MDL. For whatever it is worth, it is an interesting approach to understand an important problem in DL community, viz. the generalization issue despite the huge number of parameters in a DL model.  Quality and Significance: I have the following concerns towards the acceptance of this paper:  (a) No Sound Theory : This is the biggest drawback. Beyond the two experiments presented it's not rigorously clear, that describing a model with less description complexity has direct connection to generalization. You can always use a over-parametrized model, and still get very good generalization (see https://arxiv.org/abs/1710.05468), and that over-parametrized model may not have good MDL. Perhaps, what we need to quantify is some inter layer quantity layer (like Tishby's paper: https://arxiv.org/abs/1503.02406), so that the representation is learned to be well-suited for classification. So the connection with MDL is not clear.   (b) Experiments not reproduced carefully : There is further concern about Section 3.4. Prequential coding applying to non-sequential data (e.g MNIST) is equivalent to training ConvNet without shuffling the data batches. The result with MNIST at 99.5% is not state of the art. State of the art is around 99.8% (https://github.com/hwalsuklee/how-far-can-we-go-with-MNIST).  (c) Lack of enough experiments : For the claim supporting prequential coding causing good generalization, a better experiment will be using other dataset, which is not well studied as MNIST and CIFAR. Comparing Vanilla ConvNet model and Prequential Coding ConvNet model without any explicit regularization will be fair. Prequential code may not work very well, since it doesn't have shuffling dataset ability, which might make neural network overfit in some order-based rules.  Overall, I like the idea of applying Information Theory to Deep Learning, but description length may not be the right way, or atleast has not been explained and exposited rigorously with this submission. A good revision may be required.   ****** In the light of the author-feedback after the review process, I agree that quite a few of my concerns have been addressed and hence the overall score and the score of reproducibility has been updated.