Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work proposes a novel information-theoretic framework for understanding deep learning. Under the proposed framework, the sample complexity of learning a deep neural network scales linearly with the number of layers rather than exponentially, a problem conventional PAC bounds suffer from.

The framework assumes target deep function can be treated as a sequence of “environments” — each environment transforms the output of the previous environment. Learning can be reduced to minimizing the mutual information between a sequence of proxy environments (i.e., the deep neural networks used to do the learning) and the true environment via samples from the true environment. The key insight is that, under some assumptions, the average-case error can be decomposed as a layer-wise sum of mutual information between the proxy environments and the true environments.
strengths_and_weaknesses: Using the average-case analysis is crucial for the reduction from exponential sample complexity to linear in depth. Introducing information-theoretical analysis into understanding function approximation feels like a promising direction and may lead to future works that further utilize tools from information theory to understanding deep learning.

**Problems**
- More discussion of the connection to information bottleneck would be nice to have because the characterization that it is just an “optimization” method is in my opinion inadequate. It is fundamentally a study of “representation” and it also provides sample complexity.
- Does not account for implicit regularization and inductive bias, both of which are key ingredients of deep learning, and it’s not clear how one could do it.
- Following the previous point and as pointed out by the authors themselves, the resulting bound is essentially a parameter counting bound which is better than VC by a factor of depth. This reduction on a high level comes directly from the fact of the average case nature of the analysis; however, I am not convinced that this reduction is what is needed to fully understand why deep learning works. Notably, this bound is likely still loose for all intents and purposes and probably would not correlate well with generalization error [1,2].
- Following the previous point, there is currently no empirical verification for the assumptions made. It would be good to see some experimental results that demonstrate the validity of the assumptions.
- Can you also take advantage of the fact that the input $X$ usually has low entropy? As it stands, the framework only makes assumptions about the ground truth labeling function.



**Typo**
-  244. “Leading to potentially .. information” missing an adjective?

**Reference**
1. Fantastic Generalization Measures and Where to Find Them. Jiang & Neyshabur et al.
2. In Search of Robust Measures of Generalization. Dziugaite & Drouin et al.
questions: See Strengths And Weaknesses
limitations: Most limitations are addressed.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes an information-theoretic framework that builds on rate-distortion theory for analyzing sample complexity of learning with an average-case notion of regret based on KL divergence. Under this framework, analysis and complexity bounds for two specific network setups are also provided.
strengths_and_weaknesses: Strengths:
1. The main results motivated by the average-case analysis are interesting.
2. The analysis for two network environments is interesting.

Weaknesses:
1. Lack of empirical justification.
2. Organization of the paper could be improved. 

Details:
1. The main weakness in my opinion is the omission of any experimental justification for the proposed framework. Particularly, I am really curious about how the average-case analysis that this framework builds on holds in reality. For example, to what extent does the quadratic depth dependence hold? Since the paper already provides relevant analysis for some prototypical networks, I think it would strengthen the paper a lot more if some preliminary results can be provided to demonstrate the relevance of this framework in the real world. 
2. This paper builds on rate-distortion theory but related work provided in the paper is quite limited. A dedicated section of preliminaries would help improve the readability of the paper.

questions: My questions are outlined above.
limitations: No.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors proposed a novel information-theoretic framework with newly introduced notions of regret and sample complexity. The work is motivated by the gap between empirical success of generalizability of the deep neural networks and previous results on their complexity. By assuming an optimal agent and replace the out-of-sample error with average cumulative error, they provide general bounds on regret and sample complexity via rate-distortion theory. They further study the deep ReLU networks and deep non-parametric networks with the theory established earlier.
strengths_and_weaknesses: The authors focus on the average case rather than the worst case scenarios, and thus are able to show sample complexity grows linear or quadratic in network depth. This brings the theoretical understanding closer to what is observed in practice. The introduction of new notions are very intuitive and easy to understand. 

The reference style needs to be fixed. Many of the references are not covered by parentheses properly (use \citep{} for example), so do equations (can use \eqref{}). Minor typos are observed, like line 77, "consider an our framework". And the presentation of the paper could be greatly improved if the authors add more cross references in the paper when mention some equations/notations they defined earlier in the paper. 
questions: The results in the paper are based on the "optimality" assumption, which may not be the case in the training process. This will change the monotonicity of the prediction errors. Can the authors elaborate on this?And does the current framework also provide a worth-case sample complexity?
limitations: The authors have included discussions on limitations and future directions in their paper.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper addresses a problem in Machine Learning very much deserving attention: to develop an information theoretic basis for Deep Learning (DL) Networks. Still largely heuristic, DL  would greatly benefit from an information theoretic perspective to help understand the complexity variation (or potentially required) of  a network with   breadth and depth. It promises in particular, an ability to consider several layers (i.e. varying depth) without necessarily invoking  an exponential dependence on the depth, with potentially infinite breadth with a constrained boundedness on the sum of the parameter weights.
Overall the paper is clearly written with a good description of its objectives and an acceptable review of the current lay of the land.
 
strengths_and_weaknesses: The goal of the paper is very legitimate and hence worthy, and understanding the complexity of a network (sample and parameterization) would be in the same vein as model order estimation/complexity in the linear world. This is a problem, as duly noted in the paper, investigated by a number of researchers and each with their set of assumptions.
The objectives are nicely motivated and clearly stated.

Weaknesses:
While a good effort is expended at maintaining some rigor, which is very welcome in this area, given the plethora of data-driven and data-dictated efforts, I would sadly add that some sloppy notation and some mathematically erroneous/misleading  statements were strewn here and there. While I could not verify the proofs to the theorems, since I had no access to the Appendices, I found some of the key assumptions that i inferred to be key to the claimed strength of the results were also impractical and hence of limited interest (e.g. IID property of data, which is certainly not the case in practice).


questions: 1. Given that I was not privvy to the details of the proofs (no appendices), how does the independence assumption in IID property weaken the result?
2. For a given distribution, and if one could associate an energy functional to the data (as in the Gibbs distribution expression), could one guide the analysis in estimating the (even a bound) depth complexity?

limitations: I have not really seen any development/statement of any significance in the societal impact direction.
They did mention that their paper had not addressed any practical issue related to their development. 

 In addition, this reviewer did not think that the title of the paper was a adequately matched reflection of the results in the paper.
review_title: null

Meta-review: metareview: While some reviewers have expressed some criticism for the possibility that some assumptions might be unrealistic, all the reviewers commented on the refreshingly novel approach that could lead to new directions of research. Hence, while not perfect, this is an exciting paper that should be accepted at the conference. Please take into account the reviewers' comments in preparing the camera-ready version, in particular the comments on the limitations of the proposed approach.
confidence: Less certain
Decision: Accept