Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The submission explores information-theoretically motivated objectives for self-supervised learning (SSL). 
The submission derives a bound on an objective to maximize the mutual information between neural network inputs and outputs using assumptions about Gaussianity of the input distribution and a spline framing of neural network functions as in Montufar et al. (2014) and Balestriero & Baraniuk (2018). 
A small experiment tests deviations from the normality of the distribution of outputs of a neural network, given inputs from a KDE-like expansion of the CIFAR-10 test dataset to validate the theory's assumptions.
A generalization bound and relationships to prior criteria for SSL optimization (spec. VICReg) are also derived.
strength_and_weaknesses: ### Strengths

1. **Clarity.** The paper is extremely well-written. I had no trouble understanding the ideas presented in the work and their relationship to prior work.

1. **Reasonable motivation.** The paper aims to derive SSL algorithms from an information-theoretic perspective, given that naive formulations thereof are ill-defined. This is reasonable and of interest to the community.

1. **Novelty.** Using a neural-networks-as-splines argument to derive an information-theoretic SSL optimization criterion appears novel.

### Weaknesses

1. **Assumptions are insufficiently related to practice.**
Broadly, the manuscript aims to explain SSL in practice (judging from the introduction).

    1. In Section 3.2, two assumptions are made regarding a model of the data distribution
    (non-overlapping effective support) and sufficient Gaussian modes.
    In practical settings (i.e., not in the limit of modes), how well does this represent data
    distributions of interest to SSL?

    1. The mapping $f$ is assumed *not* to be a dimensionality reduction operator (i.e., $f : D \to K$ with $K \ge D$).
    Is this not false of the neural networks used as standard in SSL?

1. **Unconvincing result.** The assumption of non-overlapping effective support in Theorem 1 appears to allow the output distribution of the neural network to depend quite simply as the result of a single affine spline (with parameters $A_\omega$, $b_\omega$). 
This is in contrast to the more complicated expressions in Balestriero & Baraniuk (2018), who define splines per layer (e.g., their Eq. (6)).
Could you explain this discrepancy?
How could your setting "be extended to the general case," as is claimed in Section 3.2?

1. **No practical experiments.** Despite aiming to address SSL in practice, the paper does not attempt to optimize the bound on the MI objective derived in (7) nor empirically verify the generalization bound derived in Theorem 2.

### Minor

1. Please number all equations, etc. in the manuscript.

1. Around Eq. (2), $X$, $X'$, $Z$, $Z'$ are not explicitly defined, and it is not given which distribution to take the expectation with respect to (for completeness, though this is a standard expression)

1. The plot in Figure 1 looks stretched rather than scaled.

1. Typo (both "first" & "second"): "VICReg ... estimates the entropy of Z solely from the first second moment"

1. The "Theorem" counters in the appendix are off.
clarity,_quality,_novelty_and_reproducibility: **Clarity:** The motivation of the paper is clear, but the details of the contribution need to be more clearly communicated.

**Novelty:** The contribution appears novel.

**Reproducibility:** I did not see any overt effort towards reproducibility, and the experimental setup seems to lack details.
summary_of_the_review: The idea appears novel, but the practical significance of the results for SSL in general remains unclear.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: 1. This paper presents an information-theoretic view of SSL methods showing that current methods happen to maximize meaningful information-theoretic quantities.
2. The paper also presents a generalization bound on downstream tasks based on the above information-theoretical quantities.
3. Crucial to these results is the fact that the paper assumes a certain kind of stochasticity in the input, which allows information-theoretic results for a deterministic network (rather than a stochastic network as is typical). 
strength_and_weaknesses: Strengths
====
1. It is always valuable to cast heuristic objectives under a new and more formal perspective/framework, which this paper achieves.
2. Most of the discussion in the paper are fairly intuitive and easy to follow (at least until the derivation of VicReg).
3. The paper also presents a neat generalization bound for SSL that offers better guarantees than prior work (in terms of dependence on number of classes, and on the labeled dataset size). The bound depends on the three main terms of VicReg, thus providing a neat theoretical justification of VicReg. The proof of this result appears non-trivial (I've not checked it).

Weaknesses
====

My main concern is that I am not convinced of the significance of the results, however "neat" they seem to be. (Admittedly, this may also be due to the fact that I do not directly work in information theory.)

1. Although the information-theoretic view seems novel in that no one has pinned it down this way before, it is unclear to me what the significance is. When one examines the VICReg objective, it is fairly natural to believe that some kind of mutual information is being maximized: decreasing the off-diagonal terms of the covariance of Z while increasing the diagonal terms must naturally correspond to increasing the entropy H(Z); bringing Z and Z' closer together should correspond to reducing H(Z|Z'). The core connection in itself, I'm afraid, is not surprising.

2. Although the generalization bound makes a neat connection to the pieces of VicReg and is highly non-trivial (for which I greatly appreciate the authors' effort), it's unclear how significant of an insight this bound is. 
 
3. The paper seems to claim that its information-theoretic formulate ``fully recovers the VICReg objective''. But is it right to say that the information-theoretic VICReg objective doesn't actually match the exact VICReg objective? e.g., maximizing $\log |\Sigma_Z|$ would correspond to maximizing the $\log$ of the diagonal variance terms, but in VICReg, this $\log$ wouldn't be there? 

4. The paper makes a lot of *strong* (and novel) distributional assumptions to derive the existing objective. I understand that this is necessary to (a) resolve well-known information-theoretic quantities into well-known loss functions and (b) deal with a deterministic network. Given that (b) is novel, it'd be nice if (b) was also a technically significant contribution, which again is not clear to me. 
- One question to the authors is, without these Gaussian assumptions, if we were forced to deal with a stochastic network, could one establish similar connections between VicReg and the mutual information maximization problem?



clarity,_quality,_novelty_and_reproducibility: 1. Not sure where the p(z' | z) Gaussian assumption comes from. Is this explicitly required or does it follow from the previous disjoint-support-Gaussian assumption + affine mapping assumption?
2. The argument in 4.1: can it be more formally written? It was hard to follow after the equation.
 

### Minor

1. Could you state the VicReg and SimCLR objective somewhere in the paper for completeness; ideally in the main paper?
2. Does the generalization bound rely on the assumptions made earlier in the text? I assume yes; in which case these assumptions may need to be stated formally
summary_of_the_review: The paper has neat results establishing the existing SSL objectives (VICReg & SimCLR) in theoretical foundations. However, I am not convinced of the significance of these results, at least to the ICLR community, as the takeaway in the paper is essentially "VicReg does make sense from a formal point of view". In an ideal world, I'd have hoped to see this paper (a) derive an insight that tells us something _new_ about how SSL works OR (b) suggested new algorithms. Or perhaps the paper simply hasn't laid out its own significance well enough or I'm missing something due to my lack of expertise in information theory.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper intends to provide an understanding of self-supervised learning using information theory. 

First, they lay down certain assumptions for deterministic networks, under which they conclude that deterministic networks' projections are distributed as a mixture of Gaussians.

Then, under the assumption from *[Federici et al. 2020]* that we want to maximize the mutual information $I(Z;X')$ and $I(Z';X)$ between the inputs $X$ and $X'$ and the projections $Z = f(X)$ and $Z' = f(X)$, they justify the objective of VICReg *[Bardes et al. 2021]*.

After that, they use the hypothesis from *[Chen and He 2021]* that says that a siamese network with a stop-gradient operation implements an Expectation-Maximization problem analogous to $k$-means. An iteration consists of a selection of $k$ clusters and an assignment of those. Under this assumption, they use the reduction of Gaussian mixture models (GMMs) clustering to $k$-means to show that one may avoid collapse enforcing sparse posteriors.

Finally, they conclude with a generalization bound for self-supervised methods using a linear layer for classification. This particularly exhibits that VICReg *[Bardes et al. 2021]* minimizes their lower bound on the generalization error.

**References** 

*[Federici et al. 2020]* Learning robust
representations via multi-view information bottleneck. \
*[Chen and He 2021]* Exploring simple siamese representation learning.
strength_and_weaknesses: **Strengths**

The paper includes a couple of nice ideas, for instance:

* Considering the input as a mixture of Gaussians allows them to analyze properties of the output under certain assumptions. 
* Under the assumption that SSL with a stop-gradient operation is an Expectation-Maximization problem, one can try to avoid collapse explicitly. 

The proof of the generalization bound for SSL algorithms is beautifully constructed and the resulting inequality is interesting.

* They go around having to deal with the large Rademacher complexity $\tilde{\mathcal{R}}(\mathcal{W})$ in a clever manner. 
* They manage to include the decreasing term $c = \lVert W_S - W_{\bar{S}} \rVert$ in some of the terms of their inequality, where $W_S$ and $W_{\bar{S}}$ are the minimum norm solutions of the empirical risk on the labeled $S$ and unlabeled $\bar{S}$ datasets.

**Weaknesses**

* Sometimes the paper makes some claims without a citation to prior work:

    *  In the second paragraph of the introduction, it is claimed that some objective functions in the literature contradict each other, as well as many implicit assumptions. It would be good for the community to provide some examples of these cases. 
    
    * In the first paragraph of Section 3.2., they claim that under the manifold hypothesis, any point can be seen as a Gaussian random variable with a low-rank covariance matrix in the direction of the manifold tangent space of the data. It would be nice to have some citation of such a hypothesis or some justification as of why this is true.

* There are some mis-representations of the literature. 

    * The background section seems to suggest that no previous work has considered the input the source of randomness of deep neural networks. This is actually not the case. For instance, some works on contrastive learning have considered the network as deterministic and only the inputs as random variables, e.g. *[Zimmermann et al. 2021; Wang and Isola 2020]*.

* Sometimes the paper is either not rigorous or forgets to add important information to the reader.

    * In Section 3.2., what is the effective support of a random variable?. Also, in a standard dataset, are the supports of Gaussians centered at the images densities with non-overlapping supports?

    * Equation (4) is wrong since $p(x)$ is a density and $\mathcal{N}({x}; {x}^*[n({x})], \Sigma_{{x}*[n({x})]}) / N$ does not integrate to 1. I believe that you wanted to write that without dividing by $N$.

    * Section 3.3. it is mentioned that an analytical form of the per-region affine mappings is given in section 2. I could not find that. What did you mean?

    * Theorem 3 is stated as an absolute statement instead of an approximate statement. The assumption for the theorem is that $p({x}|{x}_{n({x})}^*)$ is approximately a Gaussian. Furthermore, in the proof it is also assumed that $\int_\omega p({x}|{x}^*[n({x})]) dx \approx 1$. Then, the linearity of the mapping with respect to $p$ is also an approximation.

    * In the first equation in Section 4, what are $\mu_n$ and $\Sigma_n$? I assume they are $\mu_n = A_{\omega(x_n)} x_n$ and $\Sigma_n = A_{\omega(x_n)}^T \Sigma_{x_n} A_{\omega(x_n)}$.

    * How is (7) obtained? Since the conditional decoder is the Gaussian $\mathcal{N}(\mu_n, \Sigma_r + \Sigma_n)$, the corresponding conditional entropy would be $$\frac{d}{2} \log(2 \pi e) + \frac{1}{2} \mathbb{E}[ \log |\Sigma_r + \Sigma_n|].$$  It is not clear to me how (7) is obtained from here.

    * In Section 4, it is said that $H(Z)$ and $H(Z|X')$ cannot increase if the other does not. It would be nice to explain why this happens, since it does not seem obvious to me. In fact it seems it could be false. While $Z|X'=x'$ is a Gaussian with covariance $\Sigma_r + \Sigma_n$, the marginal $Z$ is a mixture of Gaussians. One could keep the matrices $A$ fixed so that the covariance $\Sigma_n$ is the same and thus also the entropy $H(Z|X')$, and then modify the biases ${b}$ arbitrarily so the components of $Z$ are as far apart as possible, hence increasing the variance and thus the entropy $H(Z)$ arbitrarily.

    * Also in Section 4, it is mentioned that a simpler solution is to approximate the entire mixture as a single Gaussian by only capturing the first two moments and as this provides an upper bound of the entropy $H(Z)$. Why is this a good approximation? And why would this be a sensitive choice for the objective?

        1. As per your distribution model, the distribution of $Z$ is a mixture of Gaussians where the inputs were also Gaussians and well separated. Thus, this seems to indicate that $Z$ will be far from Gaussian or any unimodal-distributed random variable.

        2. Also, note that you want to maximize the mutual information $I(Z;X')$. For this reason you use the lower bound $I(Z;X') \geq H(Z) + \mathbb{E}[\log q(Z|X')]$. Then, if you use an upper bound on $H(Z)$ for your objective, you end up with an objective that is neither an upper nor a lower bound of $I(Z;X')$ and therefore maximizing it offers no guarantee that it maximizes the mutual information of interest.
    
  * In Section 4.3. and Figure 1 (left), the results suggest that the hypothesis that, for VICReg, the conditional output density is not Gaussian can be rejected with 85\% confidence for small noise and increases to 99\% confidence as the noise increases. This is fine but again, it means that the probability of a Type I error when rejecting the hypothesis that the data is not Gaussian is 15\%. \
  Also note that if the significance level were set to the standard $0.05$ the Gaussianity assumption would be rejected after the normalized noise is between 0.3 and 0.4. \
  I believe that these findings and caveats should be more clear in the text of that section.

  * Theorem 2 only holds for finite labels. In the notation of the main text and later in the proof it is mentioned that $y \in \mathbb{R}^r$. However, a crucial part of the proofs uses $p(y) = \mathbb{P}(Y=y)$ which only makes sense for discrete random variables. Then, it also includes the term $|\mathcal{Y}|$ which will result on a non-vacuous bound only if the amount of possible labels is finite. \
  Moreover, to employ *[Kawaguchi et al. 2022]* one needs that the random variable is multinomial and therefore finite. \
  Since one can always re-label the labels as they want this does not take away the nice proof, but I believe this fact should be made clear in the main text. The only constraint to do the re-labelling is that $\lVert y \rVert \leq \zeta$ for all $y \in \mathcal{Y}$.

  * Theorem 2 only holds for a classification (or regression of finite elements) with a linear layer and the $\ell_2$ norm as the loss. That is, for classification tasks where the loss is measured as $\lVert W f_\theta(X) - Y \rVert$. This is a very particular (and not common) scenario. I believe that this should be made clear as well in the main text.

  * There are some restrictions on the norms that need to be imposed for the Theorem to work.

    * Unless it is imposed that the class $\mathcal{F}$ has a finite norm range, i.e., $\mathcal{F} = \lbrace f_\theta: \mathcal{X} \to \mathcal{Z} \ | \ \lVert f_\theta(x) \rVert \leq a \textnormal{ for all } x \in \mathcal{X} \rbrace$ for some finite $a$, then $\tilde{\mathcal{R}}(\mathcal{F})$, $\tilde{\mathcal{R}}(\mathcal{W} \circ \mathcal{F})$, and $\kappa$ will tend to $\infty$ and the bounds will become vacuous.

    * Similarly, unless it is imposed that the class of matrices for the linear layer $\mathcal{W}$ is of finite norm, i.e., $\mathcal{W} = \lbrace w \in \mathbb{R}^{r \times K} \ | \ \lVert w \rVert \leq b \rbrace$ for some finite $b$, then both $\tilde{\mathcal{R}}(\mathcal{W} \circ \mathcal{F})$ and $\kappa$ will tend to $\infty$ and the bounds will become vacuous.

* It is not clear to me what is the insight to be gained in Section 5. I understand that *[Chen and He 2021]* made a connection between learning with a siamese network and a stop-gradient operation and expectation maximization ($k$-means in particular), but I do not see why noting how to avoid collapse for clustering with GMMs adds to the topic. The reason is that if you fix all covariances a priory to be the identity matrix, you need $\Sigma_{n} = A_{\omega(x_n)}^T \Sigma_{x} A_{\omega(x_n)} = I$, and therefore you cannot learn $A_{_{\omega(x_n)}}$. Am I missing something here? What is the purpose of this section?

**References**

*[Wang and Isola 2020]* Understanding contrastive representation learning through alignment and uniformity on the hypersphere. \
*[Zimmermann et al. 2021]* Contrastive learning inverts the data generating process. \
*[Chen and He 2021]* Exploring simple siamese representation learning. \
*[Kawaguchi et al. 2022]* On the theory of implicit deep learning: Global convergence with implicit layers.
clarity,_quality,_novelty_and_reproducibility: * **Clarity**: The paper is clear in some parts but it misses some citations justifying some claims, important information such as when does a theorem hold, or how some equations are obtained. Also, the intent take-away of some parts of the text (e.g. Section 5) are not clear to me.

* **Quality**: The quality of the paper varies. While the proof of Theorem 2 is beautiful albeit with some assumptions that need to be included to make it work, the first part of the text is a little subpar, with the example of using an upper bound of the entropy in a lower bound to justify an objective.

* **Novelty**: The paper is definitely novel. Considering the input as a mixture of Gaussians, continuous piecewise affine (CPA) mappings, and both Theorem 2 and its proof is new and very interesting.

* **Reproducibility**: \
*Theory*: I reproduced all the proofs except of the questions that I placed the authors in the weaknesses. 

  *Experiments*: There is no code to reproduce the experiments. Hence, I did not have time to replicate them. They should be "easy" to replicate due to the small size of the datasets and simplicity of the experiment. Nonetheless, it would be helpful to include this resource, both for the goodness of fit tests and the GMMs experiments.
summary_of_the_review: This paper considers the hypothesis that the input data can be viewed as a mixture of Gaussians with low-rank covariances. 
 
 Under that assumption, they attempt to justify the objective of VICReg. 

   * If I am not mistaken, there is a flaw in their argument here and it is that their argument starts saying that they want to maximize $I(Z;X')$. They find a lower bound on it, and then they use an upper bound on one of the terms of said lower bound to optimize $I(Z;X')$. Hence, they are optimizing a quantity that is neither an upper nor a lower bound of their objective. As mentioned in the weaknesses, this may not even be a good estimate.

It has been hypothesized that learning using siamese networks with a stop-gradient operation is equivalent to an expectation-maximization algorithm (in particular $k$-means). Thus they make a suggestion on how to avoid collapse on clustering with a Gaussian mixture model (GMM). 

  * Even though the idea is nice, it is unclear to me, though, how this can be directly linked back to self-supervised learning or learning with siamese networks with a stop-gradient operation. 

Finally, they present a new bound on the generalization of SSL methods for classification tasks and a linear layer on top of the learned representations. 

  * The proof of the bound is pretty and the result is interesting. However, it is not clearly stated the restrictions under which such theorem applies. 

Overall, I believe that this paper has very interesting ideas and a beautiful proof of a nice theorem. However, it has some lack of rigor and some mistakes in certain places. Also, it requires some work to downplay some of the claims such as "different SSL models can be (re)discovered based on...", when only VICReg is re-discovered. All in all, I believe that the paper is not quite ready **yet**.

For this reason, at the current state, I must recommend rejection of the paper. Nonetheless, I encourage the authors to continue down this path since interesting results seem to await. Of course, if the issues discussed in the weaknesses section can be addressed satisfactorily during the rebuttal phase, I am open to increase the score, since a proper application of the ideas in this paper would be a good contribution.

**Minor comments and nitpicks that did not impact the score of the review**

* In Section 3.1, note that since $Z$ is a continuous random variable and assuming that it has a density the (differential) entropy goes to $- \infty$ not to $0$ as the Shannon entropy would.

* In Section 3.3. it is mentioned that the transformation goes from a space of dimension $D$ to a space of dimension $K$ where $K \geq D$. Usually the input space (images) is much larger than the space of the projections or representations, i.e. $D \gg K$.

* In Section 4, before (6) I believe you wanted to write $q(z|z') \sim \mathcal{N}(z',\Sigma_r)$.

* Throughout the text sometimes you write the vectors $x_n$ and $x_n^*$ in bold and sometimes without bold. It would be better to have a consistent notation.

* In the last paragraph of Section 2 the citation of *[Achille and Soatto 2018]* should be citet.

* Right before Section 4.1. it the citation of *[Moshksar and Khandani 2016]* should be with citep.

* If I am not mistaken you are sometimes writing $A \mathcal{T}$ to refer to a transpose and sometimes $A^T$. Please, could you use the same notation throughout? If you use the notation $A \mathcal{T}$, could you write it in some notation section as I do not recall this being standard.

* In the proof of Theorem 2 in the appendix, the notation $g^*$ is used without introduction (at least I did not find it). Could you include it?

* In certain point in the proof of Theorem 2 in the appendix (end of page 19), you started forgetting to include the tilde in the Rademacher complexity of $\mathcal{W} \circ \mathcal{F}$.

**References**

*[Achille and Soatto 2018]* Information dropout: Learning optimal representations
through noisy computation. \
*[Moshksar and Khandani 2016]* Arbitrarily tight bounds on differential entropy of Gaussian mixtures.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Under certain mixture of Gaussian assumption of the data distribution, the paper provides an information-theoretic justification of the VICReg method for self-supervised learning. Additionally, a generalization bound for the down-stream tasks is established.  
strength_and_weaknesses: **Strength**

The main strength of the paper is its justification of VICReg and the generalization bound provided. 

**Weakness**

* The mixture of Gaussian assumption particularly considering the Gaussian components "do not overlap" is quite rough and lacks rigour. Any two Gaussians necessarily overlap.  When the overlapped region of two Gaussians has a small probability (under either one of the two Gaussians), which is presumably what the paper tries to assume by "do not overlap", the modes of the two Gaussians will need to be sufficiently apart.  But in many cases, for example when the data distribution is nearly uniform on its support, to model the data distribution using a mixture of Gaussians, a large number of significantly overlapping Gaussian would be needed, which violates the assumption of the paper.

* The presentation of paper seems sloppy, awkward and sometimes lacks clarity. I am listing a few here.
1. In Equation (3), the notation of raising the Gaussian density to the power of "$T=n$" is strange. 
2. In beginning of section 4, when you say "when our input noise is small", what do you mean by "input noise"? Please also justify this statement, ie, why when the "input noise is small" you can reduce the density $p_{z|x^*}$ to a single Gaussian?
3. In section 6.1, the notation ${\cal T}$ appears multiple times, which is supposed to mean transpose?



clarity,_quality,_novelty_and_reproducibility: 
The presented results are novel and interesting, but the assumptions are quite restrictive. The writing can be improved for better clarity. The results are likely reproducible.
summary_of_the_review: The paper presents interesting and novel results, with some limitation,  that justify VICReg. A generalization bound for the downstream tasks is also given.  Clarity can be improved.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper provides an information-theoretic framework for self-supervised learning (SSL), which unifies several existing SSL methods. It also derives a generalization bound for SSL methods, and provides generalization guarantees for the downstream supervised learning task.

Strengths:

+ The paper is well written
+ A generalization error bound for SSL is derived.

Weaknesses:
- Assumptions made in this paper are loosely connected with practice
- Certain parts of the paper lack rigorous argument. 
- It is not clear how the information theoretic understanding can be used to design new SSL methods. So the significance of this work may be limited.
- No real convincing experimental support. 

After the author's response and discussion, the reviewers are still not fully convinced regarding the significance of this work. The information-theoretic perspective of SSL is promising, but this idea needs a more thorough execution.

justification_for_why_not_higher_score: The reviewers are mostly concerned with the significance of this work.
Decision: Reject