Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper explores the problem of designing a distance measure in the space of the functions parameterized by neural networks. Ideally, such a measure should be independent of the parameterization of the networks. Also, the measure should support quantifying the distance between the networks with different structures and/or different underlying training tasks. The information distance meets this natural requirement. However, information distance is computational infeasible as it is defined by Kolmogorov complexity.

This paper utilizes the length of prequential coding to approximate the information distance which leads to a practical distance measure for neural networks. The paper empirically verifies that this distance measure is indeed invariant to the parameterization of the network. Furthermore, the paper shows that the distance measure explains/captures various behaviors of neural networks, e.g., the effect of regularization, connection between model diversity and performance for network ensembles, and generalization.

The paper studies an interesting and timely problem. The empirical results demonstrate the value of prequential coding based distance measure for understanding the behavior of neural networks. That said, there are some concerns about the novelty and presentation of the paper:
1. Prequential coding has been previously used in the context of neural networks, e.g., [1], which limits the novelty of this paper.
2. There is significant room for improvement in term of the presentation of the paper:
   i) Consider organizing the text in Section 2 (before Section 2.1) in various subsections. This would help streamline the presentation. E.g., prequential coding can be introduced in a subsection. Similarly, it is not clear why the discussion on information transfer measures is necessary after (6). Perhaps, the authors can introduce (11) after (6) and then talk about information transfer measures in a subsection.
    ii) The last two paragraphs of Section 2.2 are not very clear. Please consider expanding those paragraphs to make the message more clear.
    iii) Please use the expansion of EMD and CKA the first time these terms are used.

######## Post rebuttal ###########

Thank you for your response and the efforts to improve the presentation of Section 2. After going through other reviewers' comments and the authors' responses to those, I am comfortable with my original score. 
review_title: Prequential coding based distance measure for neural networks

final_score: rating: 4: Ok but not good enough - rejection
review_content: 1, Summary of contribution:
The paper proposes a new distance measure between a pair of neural networks, which is invariant to the reparameterization. Specifically, it introduces prequential coding to approximate the Kolmogorov complexity between two neural networks, and 
The paper also conducts empirical studies on the properties of the proposed distance. (especially the relationships to model diversity and generalization in the section 4.3) 


2, Strengths and Weaknesses:
The idea of introducing Kolmogorov complexity is interesting, and many interesting ablation studies are done.  At the same time,  there seems to be a mistake in the important step of their theoretical justification.  Also, although the paper presents many empirical studies,  it does not extensively compare the proposed distance to other distances on a theoretical basis, and this makes it difficult for the readers to understand the position of this study in the field. 

3, Recommendation:
Because the validity of  “distance” in an application is rather subjective and depends on the tasks,  the significance of a study in this field most likely hinges on theoretical soundness and the depth of theoretical analysis. Because there seems to be a flaw in the theoretical soundness, I suggest rejection. 

4, Reasons for Recommendation: 
There appears to be a mistake in the equation (4)-(6), which is the core of the justification of the proposed distance.  
In equation (4)-(6),  the authors endeavor to take an expectation with respect to {(x_i,  y_i)}.  However, in the transition from LHS of (4) to  RHS of (4), the authors seem to be forgetting the fact that theta_i is also a variable of {(x_m, y_m) ; k =1,...i-1}.  
In other words,   E_{x_{0:i}, y_{0:i}} [ log p_{theta_i} (y_i | x_{1:i},  y_{1:i-1}) ]  is not   E_{x_{i}, y_{i} } [ log p_{theta_i} (y_i | x_{1:i},  y_{1:i-1}) ] 
On this basis, I do not believe that (4) can be simplified into (6).  

If the problem raised in 4 can be resolved, I would very much like to change my rate. Please let me know if there is some misunderstanding on my part.
 
Also, because the theoretical analysis is an important part of this research, more theoretical studies on the properties of the proposed distance.

\
---Post rebuttal---

Thank you very much for the response, and I understood that some of the concerns I raised can be resolved empirically under appropriate conditions.   After the response, however, I think I am still comfortable with the original score, because this is (as I understood it) a theoretical paper and I felt that it is necessary to make a judge based on theoretical solidness. 


review_title: Review

final_score: rating: 4: Ok but not good enough - rejection
review_content: 
The authors proposed a distance measure to characterize the information space among neural networks. They derive this measure by empirically compute the expected code length. They applied the distance measure to neural network models in didfferent settings and compared with some baselines.


Strength:

+ the information theoretic perspective of the deep learning is a useful approach to compare neural networks.
+ the spectrum of the empirical study is pretty wide, covering some interesting aspects of neural network behaviors.
+ the connection with generalization of neural networks is an interesting observation.

Weakness:

- lack of important details on the experiments and related work. Despite briefly introduced the baselines in the Appendix, the main text should be self-contained. Why are these baselines chosen is also not clear. Without a clear description of the baselines, experiments, or codes greatly hinders the reading and evaluation of the results.
- limiting novelty: the concept of computing code length is not news in deep learning (Blier et al., 2018; Kim et al., 2018), and the authors are only incrementally extending the complete formulation of information transfer in Zhang et al., 2020 into the expected codelength. It is not clear the contribution, both theoretically and empirically.
- why is eq 10 a valid assumption? if not, the entire basis for this measure is not solid.
- missing definition of math notations: e.g. what is f_square in eq 14? the technical sections are below standard to top-tier conferences.
- didn't show a clear benefit over existing methods: section 3.2 explored the invariances of the measure in different parameterization settings of neural networks. however, we see that many baselines are equally invariant if not better than the proposed measure.  even in section 3.3, we see EMD performing just as well in capturing the change in training process.
- lack of comparison with other methods in Fig 4. It is likely that other similarlity measures offers interesting visualizations like this in three-dimensional space as well. Why is this method better in any way?
- several acronyms used without introducing their definition first.



Suggestion:

This submission appears to only preliminary work to a potentially interesting approach to understand the behaviors of deep learning. 

The writing is a little bit hard to follow, mostly due to a lack of details in the empirical evaluations from section 3 onward. I think it would require some significant rewriting before ready for publication.

The contribution of the work is also a bit confusing. It feels like the heavy lifting of the idea actually comes from the formulation of information transfer in Zhang et al., 2020. The empirical study also didn't show any clear benefit of the proposed approach over existing ones. 




review_title: Interesting in topics, Weak in techicals, Confusing in contribution

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary: 

The authors provide a practical distance measure among different neural networks. They extend the classical information distance by replacing the uncomputable Kolmogorov complexity in terms of code length of prequential coding. Empirically, they show several practical advantages of the proposed distances.  

Pros: The proposed distance may be easy to estimate. 

Cons:

1. For the proposed information distance definition and invariance property, are there any concrete examples or analytical formulas to demonstrate its effectiveness? E.g., if a simple linear function gives the neural network, what is the concrete value of this distance. 

2. The distance is data-dependent. Suppose the data is given by a particularly known distribution, even Gaussian, 
is there a mathematical way to demonstrate the defined quantities? 

Some sentences need to be revised:

`"` Information distance dp is based on information distance defined with Komolgorov complexity K."

Some questions:

1. In literature, there are already many works in studying the distance and geometry associated with the neural networks, such as Fisher information geometry (S. Amari) and Wasserstein information geometry (W. Li). What is the relation between this new distance based on prequential coding's codelength and two distances mentioned above? Especially the role that KL-divergence plays in this framework?

Li, Zhao, Wasserstein information matrix. 

Amari, Matsuda, Wasserstein statistics in one-dimensional location-scale model. 


2. Fisher information metric is known to be invariant under parameterization and is even characterized as the unique metric on probability space to have this property. In your paper, you mention that this new practical distance is also invariant under parameterization. Does this have something to do with the classical Fisher metric?

3. To obtain the data-dependency definition of information distance, do you have to calculate an empirical version of it? If this is the case, what is the convergence properties, such as the convergence rate of this empirical information distance?
review_title: Defining information distance by relaxing Kolmogorov complexity 

Meta-review: All the reviewers agree that the paper studies an important and interesting problem. However the reviewers felt the paper is still in preliminary stages, with incorrect derivations, missing comparisons/references,  and writing. While the authors updated the paper during the discussion stage addressing some of the concerns, the paper still needs more work in adding appropriate comparisons and in presenting the concepts more clearly. Hence I believe the paper is not yet ready for publication and encourage authors to continue their work.
Decision: Reject