Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the learning onset of Information Bottleneck (IB). The authors derive perturbation theory for the IB method and characterize the learning onset, and verifies with experiments. The authors also compare the difference and subtleties in their derivation and previous attempts at deriving a perturbation theory for the learning onset. 
main_review: In terms of originality, the perturbative approach to address the IB learning onset is not new, but the details of the perturbation, and characterization of the information quantities at the onset is new. 

In terms of comparison with the previous work "Learnability for the Information Bottleneck" (Wu et al 2019), there is a difference between the meaning of \epsilon. In (Wu et al 2019), the epsilon is defined as an infinitesimal number which is used for series expansion, which is independent of \beta-\beta_c, and the perturbation on the probability q(z|x) is the global difference between the perturbed probability and the trivial q_0(z|x)=q_0(z), and is allowed on the full support of Z. In the current work, \epsilon is defined as \epsilon=\beta-\beta_c, and therefore there are multiple terms q(z|x) = q0(z|x) + ε q1(z|x) + ε^2 q2(z|x) + ... , w.r.t. \beta-\beta_c. In (Wu et al 2019), the perturbative theory is used for deriving an upper bound of beta_c using sufficient conditions of non-trivial representation, while in the current work, since \epsilon is defined as \epsilon=\beta-\beta_c, it can obtain a tight bound of the onset. In the paper, it will be appropriate if the authors clarify the difference in the above perspective.

Apart from the above, the paper is mostly clear. In terms of significance, the result is incremental, but will be interesting to the IB and representation learning community.
limitations_and_societal_impact: The paper is clear about its limitations.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper investigates the perturbation theory for the information bottleneck method to characterize the learning onset, i.e., the threshold parameter that governs the transition between the informative and uninformative regimes. First order theory and second order perturbation analyses to estimate the learning onset are presented. The utility of the theoretical results is demonstrated with the help of experiments. The authors also show the recovery of known results for Gaussian case using their analysis techniques. 
main_review: 1. Since learning onset is central to the theoretical claims in the paper, I expected Section 2 to be more detailed and self contained. It's unclear why the learning onset corresponds to a transition characteristic and why the threshold parameter $\beta_c$ is related to the maximum relevant information encoded per bit. 

2. The paper is well organized and mathematical details are reasonably clear, however, some parts of the analysis are not motivated well enough. What's the basis for expansions in (6) and (7)? Are these expansions valid for all stochastic encoders $q(z\mid x)$? What do the quantities $I_{Z;X}^{(1)}[q_1]$ and $I_{Z;X}^{(1)}[q_1,q_2]$ signify? 

The paper provides a worthy contribution to the information bottleneck theory by theoretically characterizing the learning onset. However, some parts of the paper could be improved with better motivation and discussions. 
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors investigate the learning onset for the information bottleneck method, i.e., the behavior of the problem at \beta being close to the critical parameter \beta_c. More specifically, the IB curve is studied via a perturbation around the optimal compression map. In contrast to previous work, the authors allow this perturbation also outside of the alphabet of the optimal compression.
main_review: The manuscript is well-written and seems mathematically correct (although I have to admit that I did not check every single detail). Understanding the properties of such an important and popular optimization problem is relevant in its own right. The insights are thus interesting and relevant, albeit only for a very small community (e.g., while the IB framework is often used for training neural networks, it is rarely the IB functional that is directly optimized, but some variational (or other) approximations). I am therefore generally in favor of this paper.

There are a few consideration that I would like to add:
- In equations (8)-(9) it is not clear whether these are definitions or calculations. If they are calculations, I would appreciate to see these carried out in an appendix. These two equations are central to the paper, as the remaining derivations start from these assumptions.
- In line 100 you claim that the ratio q1(z|x)/q1(z) does not depend on z. This is not obvious to me. It may very well be that I misunderstood some central part of the paper, but then it may be that this also escapes the attention of the occasional reader. May I ask you to expand on this statement a bit?
- In equations (21)-(23) it is not exactly clear where and why the optimum q1* should be used. (And I assume that q1* is the optimizer of Section 3.1.) For example, why is q1* used in (21), but not in (22) and (23)? I would expect that q1* should at least be used in (23), as in its left-hand side of the equation.
- In (22) is the r(x') defined via (14) or via (16), or is this the same by selecting q1(z|x)=q1*(z|x) as in (13)? This also leaves unclear to me whether in (15) the sums should run over q1* instead of q1, as (15) is obtained via inserting (13) into (14), and (13) uses the minimizer q1*. Again, I may have missed an important point here, in which case I apologize.
- In Fig. 2 you add the proportionality to I(X;Y) in the figures. Are these proportionalities derived from or consistent with theory? I did not see this clearly mentioned in the paper. Even then, it is peculiar that the Gaussian case exhibits a bigger difference between the proportionality and the numerical results than previous approaches yielded. I would appreciate if you could expand on this fact somewhere in the text.
- In lines 161-163 you connect the leading corrections for I(Z;Y) and I(Z;X), and you justify this via equations (26)-(27). If these equations hold true in general, then I would appreciate to see lines 161-163 in the general part of the paper (e.g., Section 3), rather than just at the end of the numerical experiments.
- In line 165 you mention that the theory is agnostic about the discrete or continuous nature of the representation, while in line 184 you claim that the representations are discrete in this work. Which of the two statements is correct? They appear to be in conflict, at least to me. More generally, you claim in lines 183-184 that the analyses are distinct. I wonder if, using a Gaussian assumption, the functions r(x) and r(y) would have the same shape as they do in the discrete case. More generally, where is the discreteness of your assumption essential, and where can it be generalized to continuous distributions? I acknowledge that this last question is a very complicated one and I would fully accept as answer that this investigation is out of scope. However, I would be willing to share an educated guess here in the replies, I would read it with interest.


Finally, there are some minor comments that I have, but that did not influence the score of the review:
- in lines 82-83, I think you mean that the corrections get larger if \epsilon deviates from zero, right?
- in line 91, the notation \delta_n,0 is not fully clear. I prefer the notation in eq. (20) or in line 126.
limitations_and_societal_impact: The authors mention that the results concern only the learning onset, which is sufficient in my opinion. I also agree with the authors that no societal impacts are to be anticipated from this theoretical work.
review_title: null

Meta-review: Reviewers agree that this work is a clear, well-written theory paper that will be of interest to the growing community of researchers working with models trained using the Information Bottleneck and related objective functions. Consequently, we are recommending the paper for acceptance.
Decision: Accept (Poster)