What Do We Maximize in Self-Supervised Learning And Why Does Generalization Emerge?
Authors: Ravid Shwartz-Ziv
Randall Balestriero
Kenji Kawaguchi
Yann LeCun
Venue: Submitted to ICLR 2023 (2023)
Keywords: Self Supervised Learning
Neural Networks
Information Theory
Generalization Bounds

Abstract: In this paper, we provide an information-theoretic (IT) understanding of self-supervised learning methods, their construction, and optimality. As a first step, we demonstrate how IT quantities can be obtained for deterministic networks, as an alternative to the commonly used unrealistic stochastic networks assumption. Secondly, we demonstrate how different SSL models can be (re)discovered based on first principles and highlight what the underlying assumptions of different SSL variants are. Third, we derive a novel generalization bound based on our IT understanding of SSL methods, providing generalization guarantees for the downstream supervised learning task. As a result of this bound, along with our unified view of SSL, we can compare the different approaches and provide general guidelines to practitioners. Consequently, our derivation and insights can contribute to a better understanding of SSL and transfer learning from a theoretical and practical perspective.



Under review as a conference paper at ICLR 2023
WHAT Do WE MAXIMIZE IN SELF-SUPERVISED LEARNING AND WHY DOES GENERALIZATION EMERGE?
Anonymous authors Paper under double-bling brindd review
ABSTRACT
this paper, we provide an information-theoreticc (IT) understanding of self- supervised learning methods, their construction, and optimality. As first step, we demonstrate how quantities can be obtained for deterministic networks as alternative to the commonly used unrealistic stochastic networks assumption. Secondly, we demonstrate how different SSL models can be dre)discoe based on first principles and highlight the underlying assumptions of different SSL variants. Based on this understanding, we present new SSL methods that are superior to existing methods in terms of performance. Third, we derive novel generalization bound based on our IT understanding of SSL methods, providing generalization guarantees for the downstream supervised learning task. As a result of this bound, along with our unified view of SSL, we can compare the different approaches and provide general guidelines to practitioners. Consequently, our derivation and insights contribute to a better understanding of SSL and transfer learning from a theoretical and practical perspective.
INTRODUCTION
Self-Supervised Learning methods (SSL) learn representations using a surrogate objective between inputs and self-defined signals. In SimCLR (Chen et al., 2020). for example, contrastive loss is defined that makes representations for different versions of the same image similar, while making the representations for different images different. After optimizing the surrogate objective, the pre-trained model is used feature extractor for downstream supervised task, such as image classification,
object detection, instance segmentation and transfer learning (Caron et al. 2021 Chen et al. 2020 Misra & Maaten 2020, Shwartz-Ziv et al. 2022). However, despite success in practice, only few number of authors (Arora et al. 2019 Lee et al. 2021a) have sought to provide theoretical insights about the effectiveness of SSL.
In recent years, information theory methods have played a key role in several deep learning achieve- ments, from practical applications in representation learning (Alemi et al., 2016). to theoretical investigations (Xu & Raginsky] [017]] Steinke & Zakynthinou, 2020) Shwartz- (002).. Moreover, different deep learning problems have been successfully approached by developing and applying novel estimators and learning principles derived from information-theore
quantities. Specifically, many works have attempted analyze SSL from an information theory perspective. An example is the use of the renowned information maximization (InfoMax) principle (Linsker 1988) in SSL (Bach) man et al.) 2019). However, looking at these works may be confusing. Numerous objective functions are presented without a rigorous justification, some contradicting each other, as well as many implicit assumptions (Kahana & Hoshen 2022 Wang et al., 2022] Lee al. (02Tb) Moreover, these works rely a crucial assumption: stochastic DN mapping, which rarely the case nowadays.
This paper presents a unified framework for SSL methods from an information theory perspective, which can be applied to deterministic DN training. We summarize our contributions into four points: (i) First, in order to study deterministic DNs from an information theory perspective, we shift stochasticity to the DN input, which is much more faithful assumption for current training techniques. (ii) Second, based on this formulation, we analyze how current SSL methods that use deterministic networks optimize ceommatiio-thhorette quantities. (iii) Third, present SSL

---

Under review as a conference paper at ICLR 2023
methods based on analysis and empirically validate their superior performance. (iv) Fourth, study how the optimization of cermattio-thhoretee quantities is related to the final performance in the downstream task using new generalization bound.
2 BACKGROUND
Continuous Piecewise Affine (CPA) Mappings. A rich class of functions emerges from piecewise polynomials: spline operators. In short, given a partition Q a domain IR,, a spline of order is a mapping defined by a polynomial of order k on each region E 52 with continuity constraints on the entire domain for the derivatives of order O.....k .k- 1. As we will focus on affine splines (I: = 1), we define this case only for concreteness. An K dimiennsional affine spline f produces its output via
f(z) = Σ (A + bw bl
WE
with input E RR. and A E RKXD bw E RRK Ve E S the per-region slope and offset param- eters respectively, with the key constraint that the entire mapping is continuous over the domain E (. Spline operators and especially affine spline operators have been widely used in function approximation theory (Cheney & Light 2009), optimal control (Egerstedt & Martin 2009).
statistics (Fantuzzi al. 2002), and related fields.
Deep Networks. A deep network (DN) is a (non-linear) operator fe with parameters θ that map imput I to a prediction y IR The precise definitions of DNs operators can be found in Goodfellow et al. (2016). We will omit the θ notation for clarity unless needed. The only assumption we require for our study that the lineariitss present in the DN are CPA, as is the case with (leaky-) ReLU, absolute value, and max- max-pooling. In that case, the entire input-output mapping becomes a CPA spline with an implicit partition 52, the function of the weights and architecture of the network (Montufar et al., 2014 Balestriero & Baraniuk (018). For smooth nonlinearities, our results hold from a first-order Taylor approximation argument.
Self-Supere Supervised Learning. Joint embedding methods learn the DN parameters O without supervision and input reconstruction. The difficulty SSL is to produce a good representation for downstream tasks whose labels are not available during training -while avoiding a trivially simple solution where the model maps all inputs to constant output. Many methods have been proposed to solve this problem, see Balestriero & LeCun (2022) for a summary and connections between methods. Contrastive methods learn representations by contrasting positive and negative examples, e.g. Sim-
CLR (Chen et al.) (2200) and its InfoNCE criterion (Oord et al.. 2018). Other recent work introduced non-contrastive methods that employ different regularization methods to prevent collapsing of the representation. Several papers used stop-gradients and extra predictors avoid collapse (Chen & He 2021 Grill et al. (020) while Caron et al. (2020) uses an additional clustering step. As opposed to contrastive methods, noncontrastive methods not explicitly rely on negative samples. Of particular interest to us is the VICReg method (Bardes et al. [2021) that considers two embedding batches
Z [f(r)).... ... ((xx)) and Z' = [fa1), ...i)...... J.. [axxx) each of size (N K). Denoting by C the
(K x K) covariance matrix obtained from Iz, Z'I we obtain the VICReg triplet loss
K
a max (0.7- 107-VCam A + [(OKN) + + Z
-=
K
Deep Networks and Information-Theory. Recently, information-theorede methods have played a key role in several remarkable deep learning achievements (Alemi et al.) 2016) Xu & Raginsky 2017 Steinke Zakynthinou, 2020 Shwartz-Ziv & Tishby 2017]. Moreover, different deep learning problems have been successfully approached by developing and applying information- theoretic estimators and learning principles (Hjelm al. 2018 Belghazi al. 2018 Piran et al.. 2020; (Shwart--Ziv et al.) 2018). There is, however, a major problem when it comes to analyzing information-theoreiic objectives in deterministic deep neural networks: the source of randomness. The mutual information between the input and the representation in such networks is infinite, resulting in ill-posed optimization problems or piecewise constant, making gradient- gradient-based optimization methods ineffective (Amjad & Geiger 2019). To solve these problems, researchers have proposed several solutions. For SSL, stochastic deep networks with variational bounds could be used, where the output of the deterministic network is used as parameters of the conditional distribution (Lee et al.
2

---

Under review as a conference paper at ICLR 2023
2021b Shwartz-Ziv & Alemi 2020). Dubois et al. (202)) suggested another option, which assumed that the randomness data augmentation among the two views is the source of stochasticity in the network. Another line of works assume random imput, but not using any properties of the distribution of the newtork's 's output in order to analysis the netwokr's objective, which rely on general lower bounds (Wang & Isola 2020 Zimmermann et al.) (02T). For supervised learning, Goldfeld et al. (2018) introduced an auxiliary (noisy) DN framework by injecting additive noise into the model and demonstrated that it is a good proxy for the original (deterministic) DN in terms of both performance and representation. Finally, /Achille & Soatto (2018) found that minimizing stochastic network with regularizer is equivalent minimizing cross- pross-entrppy over deterministic DNs with multiplicative noise. However, all of these methods assume that the noise comes from the model itself, which contradicts current training methods. this work, we explicitly assume that the stochasticity comes from the data, which is less restrictive assumption and does not require changing current algorithms.
3 INFORMATION THEORY FOR DETERMINISTIC DEEP NETWORKS
This section first sets up notation and assumption the information-thhorrcte challenges in SSL (section and on our assumptions regarding the data distribution (section (.2) so that any training sample can be we obtain that the output of any deep network f(x) corresponds to a mixture of truncated Gaussian (section p. In particular, it can fall back single Gaussian under small noise (det(E) e) assumptions. These results will enable information measures to be applied to deterministic DNs. We then recover known SSL methods (Bardes et al.) 2021]] Chen et al. 2020 by making different assumptions about the data distribution and estimating their information.
coming from single Gaussian distribution in N (Mt Eg) From this
3.1 SSL AS AN INFORMATION THEORETTI PROBLEM
To better grasp the difference between key SSL methods, we first formulate the general SSL goal from information-theoretiia perspective. We start with the MultiView InfoMMa principle, i.e., maximizing the mutual information between the representations. Let X and X' be two different views and Z and Z' their corresponding representations. As shown in Federici al. (2020). to maximize their information, we maximize (2; and ;(Z'; X) using the lower bound
1(z,'') = - H( 2 HZ)) + Ez' (logq(2(<")
(2)
where (Z) is the entropy of Z. In supervised learning, where need maximize I(ZYY) Y), the
labels (Y) are fixed, the entropy term H(Y) is constant, and you only need to optimize the log- loss well known that for Siamese networks there exists a degenerate solution, in which all outputs "collapse" into an undesired value (Chen al. 2020). Looking eq. ? we can see that the entropies are not constant and can be optimized throughout the learning process. Therefore, only minimizing the log loss will cause it to collapse to the trivial solution of making the representations constant (where the entropy goes to zero). To regularize these entropies, that is, prevent collapse, different methods utilize different approaches to implicit regularizing information. To recover them in section 4 we must first introduce the results around the data distribution (section 3.2 and how a DN transforms that distribution (section 3.3)
Eg log (2 [r] (cross-entropy or square loss). However,
3.2 DATA DISTRIBUTION HYPOTHESIS
Our first step is to assess how the output random variables of the network are represented, assuming distribution on the data itself. Under the manifold hypothesis, any point can be seen as a Gaussian random variable with low-rank covariance matrix in the direction of the manifold tangent space of the data (Fefferman et al. 2016). Therefore, we will consider throughout this study the conditioning of a latent representation with respect to the mean of the observation, i.e., X|2" N/(x", Ex-) where the eigenvectors of Σg are in the same linear subspace than the tangent space of the data manifold at x." which varies with the position of xx in space.
3

---

Under review as a conference paper at ICLR 2023
Hence a dataset is considered to be collection of {2;, 1, .,...,.N] .N and the full data distribution to be a sum of low-rank covariance Gaussian densities, as in
X Σ N( Mx;))
) (Tr=)), T Cat(NN,
with the uniform Categorical random variable. For simplicity, we consider that the effective support of (x Ex;) and ; Ex;) do not overlap, where the effective support is defined as {z E RD.. p(x) of This keeps things general, as it is enough to cover the domain of the data manifold overall, without overlap between different Gaussians, Therefore, we have that.
p(a) ~ N [x; (f(())) Dmicce) /N,
where N (z) is the Gaussian density at z and with n²x) arg min,, (x -x,)) x;)) " (x xy,). This assumption, that a dataset is mixture of Gaussians with non-overlapping support, will simplify our derivations below, and could be extended the general case if needed.
3.3 DATA DISTRIBUTION AFTER DEEP NETWORK TRANSFORMATION
Consider affine spline operator f (Eq. 1 that goes from space of dimension D to space of dimension K with 2 D. The span, that we denote as image, of this mapping is given by
Im(f) & {f(x) a RD
U Aff(ww Aw.
(5)
with Aff(w: A_,, parameters Au:, bu, and with Ω the partition of the input space in which lives in. The practical computation of the per-region affine mapping can be obtained by setting A_ to the Jacobian matrix of the network at the corresponding input x, and 6 to defined as f(z) a.
b = w the affine transformation of region w by the per-region
Therefore, the DN mapping consists of affine transformations on each input space partition region Ω based on the coordinate change induced by A., and the shift induced by bw.
When the input space is equipped with a density distribution, this density is transformed by the mapping f. In general, finding the density of f(X) is an intractable task. However, given our disjoint support assumption provided in section 3.2] we can arbitrarily increase the representation power of the density by increasing the number of prototypes N. In doing so, the support of each Gaussian included with the region in which its means lie in, leading to the following result.
Theorem 1. Given the setting of eq. 4 the unconditional DN output density denoted as Z is approximately mixture of the affinely transformed distributions æ x (r(()))) e.g. for the Gaussian case
1(T=n)
Z~
A(A Aw(rg) + bw(mz)) AT A Daz Au(a;))
(6)
where w(x;), E Ω - x the partition region in which the prototype xf, lives in.
Proof.
The proof of of Theorem
I
presented in Appendix A
INFORMATION OPTIMIZATION AND OPTIMALITY
Next, we will show how SSL algorithms for deterministic networks can be derived. According to Section 3.1 we want to maximize 1 ((;;'') and XX) Although this mutual information is intractable in general, we can obtain tractable variational estimation using the expected loss. First, when our input noise is small, namely that the effective support of the Gaussian centered at x is contained within the region w of the DN's input space partition, we can reduce the conditional output density to single Gaussian: X In) ' (u(Ix)) E(x,)), where μ(Ix)) Au(an) Tn. bw(r.) and E(rn) T ((x.)) Exe,, A Aw(ee)- Second, In order compute the expected loss, need
4

---

Under review as a conference paper at ICLR 2023
H22-44
HP2
0.15
0.0001
SimCLR VICReg
Learning Rate Centrooss
more Gauzzian)
H22
H22
valuu
0.05
H521-45
H12) 264
0.0
6.1
0.3
0.5
0,02505 Learmnng Rate Data
Normalized input (a)
Figure 1: Left: The network output SSL training more Gaussian for small input noise. The P-value of the normality test for different SSL models trained CIFAR-10 for different input noise levels. The dashed line represents the point at which the null hypothesis (Gaussian distribution) can be rejected with 99% confidence. Right: Smaller learning rates prevent collapsing. GMM points where in black is the entropy, in blue and red are the data points and GMM centroids respectively, with the corresponding learning rate
to marginalize out the stochasticity in the output of the network. In general, training with squared loss is equivalent to assuming Gaussian observation model p(z[z') ~ M(22. Σ,), where Σ, I. To compute the expected loss over samples of x', we need to marginalize out the stochasticity in Z': which means that the conditional decoder is a Gaussian (Z r..) >N(u(,,) E, E(rr)). However, the expected log loss over samples of Z is hard to compute, and therefore we focused on its lower bound, the expected log loss over samples of Z'. For simplicity, we set Σ, which gives us:
m(x')) 1 Trl E(x') (7)
Ex' [log (<(1=/)] 2 Eay [log [logg(=(2') = log 2nT
2
and now we can take the expectation over Z:
E2je E2 [log [2|=²)]] log (u(x) - =xx'))²²
log ([E(x) -
(8)
Full derivations of eq. and eq. (8) are presented in Appendix B Combine all the above give
I(; H(2) Er, , [loga (2]22))
(9)
(2) + 2 2
log 2n
Ezr (M(xx) =(x²))² + log ([E(x) [E(')))
1
(10)
To optimize it in practice, approximate p(z,2') using the empirical data distribution:
1
L H(Z) - (m(xa) u(=())² log ([E(x))) [E()))
(11)
Next, we will discuses how the estimation of the intractable entropy H(Z) effect objective.
4.1 DERIVING VICREG FROM FIRST PRINCIPLEES
As result of eq. [1]. we can reconstruct VICReg from first principles. Unfortunately. H ( cannot be determined explicitly. However, there are several approximations the literature (Kolchinsky & Tracey| 2017; Huber et al., 2008). For detailed discussion about the different entropy estimator, see appendix C A simpler solution to approximate the entire mixture by capturing the first two moments of the distribution, which provides an upper bound on the entropy. Note that we are optimizing an upper bound, which means we do not have a formal guarantee, and could lead to an arbitrary increase in our estimator. In practice, there cases where maximizing a lower bound (Martinez et al.) [022] Nowozin et al. 2016), even though this may cause instability in the training process. Using Ez the covariance matrix of Z, will maximize:
achieve good results by
5

---

Under review as a conference paper at ICLR 2023
Σz L log [x)))
2
(u(())=((z)) -
(12)
Optimizing the log determinate of means maximizing its log eigenvalues. Although is theoreti- cally possible to differentiate eigendecomposition, this leads to numerical instability (Dang et al. 2018). While many works have attempted to address this issue (Giles) 2008 Ionescu et al. (015)) VICReg is using straightforward approach. Because the eigenvalues of diagonal matrix are the diagonal, increasing the sum of the log- diagonal terms is equivalent to increasing the sum of the log eigenvalues. One approach is to set the off- off-diagonal terms of Σz to zero. However, VICReg maximizes the sum of the diagonal term instead of the log of diagonal terms, which is an upper. An exciting research direction is to maximize the eigenvalues of Z using more sophisticated methods, such as using a differential expression for eigendecomposition.
4.2
EMPIRICAL EVALUATION
4.2.1
VALIDATION OF OUR ASSUMPTIONS
Based on the theory presented in Section 3.3 the conditional output density Pz|z=i reduces to a single Gaussian with decreasing input noise. We validated it using ResNet-18 model trained with SimCLR or VICReg on the CIFAR-I0 dataset (Krizhevsky) 2009). From the test dataset, we sample 512 Gaussian samples for each image and analyzed whether each sample remains Gaussian in the penultimate layer of the DN. Then, we employ the D' A'Aossiino and Pearson's 's test (D' Agostino function of the normalized standard deviation. For small noise, we can reject the hypothesis that the conditional output density of the network is not Gaussian (85% for VICReg). Increasing the input noise causes the network's 's output to become less Gaussian. Although the results indicate that the output of the network is Gaussian, even for the small noise regime, there is a 15% of Type error.
(left) 1971). Figure (left) shows the p-value
The next step is to try to confirm our assumption that the model of the data distribution has non- overlapping effective support. We calculate the distribution of pairwise lo distances between images for seven datasets: MNIST, CIFAR1O, CIFARI00 100, Flowers102, Food101, FGVAircaft. In Figure appendix DD we can see that even for raw pixels, the pairwise distances are far from zero, which means you can use a small Gaussian around each point without overlapping. Therefore, the effective support of these datasets are not-overlapping. and our assumption is realistic.
4.2.2 OPTIMIZING THE MUTUAL INFORMATION OBJECTIVE
Implementing Eq in practice requires many "design choices". In section 4.1 discuss how VICReg uses an approximation the entropy that is both loose and an upper bound on the true entropy. Next, we suggest combining the VICReg invariance term with different methods for optimizing the entropy.
Estimators. The VICReg objective aims approximate the log determinate of the empirical covariance matrix by using diagonal terms. However, this estimator can be problematic Huber et al. (2008). Instead, we use the LogDet Entropy Estimator Zhouyin & Liu (202I), which provides tighter upper bound. This estimator is still an upper bound on entropy, which does not provide any guarantee. To address this problem, we also use lower bound, based on the pairwise distances of the individual Gaussians (Kolchinsky & Tracey 2017). These proposed methods are compared with recent SSL methods SimCLR (Chen et al.) 2020) and Barlow Twin (Zbontar et al. 2021).
Setup Our experiments are conducted on CIFAR- 10 Krizhevsky et al. (2009). We use ResNet- 18 (He al. 2016) as our backbone. We use linear evaluation for the quality of the representation. For full
details see Appendix
Results. It can be seen from Table D that the proposed estimators outperform both the original VICReg and SimCLR as well as Barlow Twin. By estimating the entropy with a more accurate estimator, we can improve the results of VICReg, and the pairwise distance estimator, which is a lower bound, achieves the best results. This aligns with the theory that want to maximize lower bound on true entropy. The results of our study suggest that a smart selection of entropy estimators, inspired by our framework, leads to better results.

---

Under review as a conference paper at ICLR 2023
5 SELF SUPERVISED LEARNING, EM AND INFORMATION
Several SSL methods employ the stop gradient operator and only train with positive pairs of data (Grill et al. 2020; Chen & He 202T). According to (Chen & He 202T), presetting the stop gradient operation implicitly involves presenting two sets of variables where the algorithm alternates between optimizing each set. Next, we formalize these SSL methods as generalized EM optimization problems, link them to information theory, and analyze how specific design choices affect their collapse.
5.1 THE EM ALGORITHM AND SELF SUPERVISED LEARNING
The classical approach learning with hidden variables is based on the Expectation Maxi- mization (EM) algorithm (Dempster et al., 1977). Neal & Hinton (1998) showed that we can view it as dual optimization where both steps are seen as maximizing the same function, F(P.0) = pp [P(Z, Z' 0)) (P) where (P) = EEp [log P(z") is the entropy of the empir-
ical distribution P and E [P(Z, 210) is the regular likelihood. Using this formulation, Neal & Hinton (1998) showed that the (G)EM algorithm maximizes variational lower bound on the log likelihood. However, as discussed in section optimize the likelihood can be problematic when both variables are changing. Unlike the classic EM algorithm, for SSL, our imput variable Z changes in each iteration, and the optimization is with respect to both and Z'.
5.2 PREVENTING POINT COLLAPSE UNDER THE EM ALGORITHM
For Gaussian mixture models (GMMs), clustering consists of estimating the parameters that maximize its likelihood function, followed by assigning to each data point the cluster corresponding to its most likely multivariate Gaussian distribution. Chen & He (2021) suggested that the SimSiam method can be viewed as the K-means algorithm, which can be derived by reducing the GMMs
Let us examine a toy dataset on the pattern of two intertwining moons illustrate the collapse phenomenon under GMM (Figure I right). We begin by training a classical GMM with maximum likelihood, where the means are initialized based on random samples, and the covariance is used as the identity matrix. A red dot represents the Gaussian's 's mean after training, while blue dot represents the data points. In the presence of fixed input samples, we observe that there is no collapsing and that the entropy of the centers is high (Figure 4 left, in the Appendix). However, when we make the input samples trainable and optimize their location, all the points collapse into a single point, resulting in sharp decrease in entropy (Figure 4 right, in the Appendix).
To prevent collapse, we follow the K-means algorithm in enforcing sparse posteriors, i.e. using small initial standard deviations and learning only the mean. This forces a one-to-one mapping which leads all points to be closest to the mean without collapsing, resulting in high entropy (Figure J middle, in the Appendix). Another option to prevent collapse is to use different learning rates for input and parameters. Using this setting, the collapsing of the parameters does not maximize the likelihood. Figure shows the results of GMM with different learning rates for learned inputs and parameters. When the parameter learning rate is sufficiently high in comparison to the input learning rate, the entropy decreases much more slowly and collapse occurs.
BENEFITS OF INFORMATION MAXIMIZATION FOR GENERALIZATION
The purpose of this section is to further connect the invariance loss, the covariance matrix, and the information with the input to the generalization ability of the model by deriving a novel generalization bound. Together with the results from the previous sections, this provides mathematical understand- ing of the benefits of SSL through maximization of information with implicit regularization.
6.1 NOTATION
Let be our input and y E R' the output. We are given labeled training data $ = ((x2,, y:)); of size and unlabeled training data $ ((x + )) of size m, where 2 and x share the same (unknown) label. With the unlabeled training data, we define the invariance loss
Is(fo) _ Em [= Jo(f+t]] where fo is the trained representation on the unlabeled
7

---

Under review as a conference paper at ICLR 2023
data S. We define labeled loss (w) | (o) yl where vec[W] E R is the vectorization of the matrix W E Brxd. Let ws vecl be the minimum norm solution as Ws = minimizew, ||W'||F s.t. W E arg minw 1 - (W - yoll. We also define the E n
-R and Zg = [[(x]] (...),........... ( Rdxm and the projection matrices P Pzg = 1 Zs (Zs 1t and Pzg T Zg (Z Zg We define the label matrix Ys , .n]
representation matrices Zs = [2)) f (Ix) ]]
R and the unknown label matrix Ys [Vi ...... Von] E RRaxr, where y,_ is the unknown label of x.. Let F be hypothesis space of fo. For given hypothesis space F, we define the normalized Rademacher complexity (F)
Vm Rm.ss.(suppeE E (=1 [(,+t)l], where .i.... . are independent uniform random variables taking values in (-1.1}. It is normalized such that R.m. (F)
(1) m oC for typical
choices of hypothesis spaces F, including DNs (Bartlett et al. 2017 Kawaguchi et al. 2018
6.2 GENERALIZATION BOUND FOR VICREG
We now show that SSL via VICReg can be understood improve the generalization ability for the supervised downstream task. Namely, Theorem 2 shows that the expected labeled loss Ez.g/ (Z (ws)) minimized when we minimize the unlabeled invariance loss (f()) while controlling the covariance Zg and the complexity of representations (F):F)::
Theorem 2. (Informal version). For any 8 >> O, with probability at least 1 - ō, the following holds:
2
PP2y + (Rm((F VT
Ex.yley((s) 1aalsssss50 Is(fo) + Pzg YsllF +
+ -m.
(13)
vm
co. In Qm the value of G for the term decaying at the rate 1/ /mm depends on the hypothesis space of fa and w whereas the term decaying at the rate 1/ v is independent of any hypothesis space.
where 2m, =
In(1/8)
In(1/8)
0 as m.
Proof. The complete version of Theorem 2 and its proof are presented in Appendix G
Note that our framework holds for classification with a linear layer and the 12 norm as the loss. Also, in order that this bounds will not become vacuous we should imposed that the class F has finite norm range and that the class of matrices for the linear layer W is of finite norm.
The term ||P zg Ysli F Theorem 2 contains the unobservable label matrix Yg. However, we can minimize this term by using ( Ysllf S [|Pz, || ||s|| and by minimizing [|Pzzllr: The factor [| |e is minimized when the rank of the covariance ZgZsT T is maximized. Since strictly diagonally dominant matrix is non-singular, this can be enforced by maximizing the diagonal entries while minimizing the off-diagonal entries, is done in VICReg. For example, if d n, then || lr when the covariance 7g is of full rank. The term |Pz. Ysllr contains only observable variables and we can directly measure the value of this term using training data. In addition, the term |P Ysllp is also minimized when the rank of the covariance ZsZs is maximized. Since the covariances ZgZs
T and ZgZs" concentrate to each other via concentration can also
inequalities with the error in the order of (Im((1/))) R., (F) (F) (Im(11)))m minimize the upper bound on || Ys|lr r by maximizing the diagonal entries of 7 while minimizing its off- off-diagonal entries, as is done in VICReg.
Thus, VICReg can be understood as a method minimize the generalization bound in Theorem 2 by minimizing the invariance loss while controlling the covariance ZzZg T to minimize the label- agnostic upper bounds on || n Y sslr r and || Ys If we know partial information about the label Ys of the unlabeled data, we can use it to minimize |Pz,, YslIF F and PP Ys |r directly. This direction can be used to improve VICReg in future work for the partial observable setting.
6.3 UNDERSTANDING VIA MUTCAL INFORMATION
Theorem 2 together with the result of the previous section shows that, for generalization in the downstream task, it is helpful maximize the mutual information T(Z; X') in SSL via minimizing
8

---

Under review as a conference paper at ICLR 2023
the invariance loss (So) while controlling the covariance 7g7Z5' T. The term 2R.
m/m captures the importance of controlling the complexity of the representations fe. To understand this term further in terms of mutual information, let us consider a discretization of the parameter space of F to have finite [F] < oo (indeed, a computer always implements some discretization of continuous variables). Then, by Massart's Finite Class Lemma, we have that (F) CV [ii for some constant C' > 0. Moreover, Shwartz- Ziv (2022) shows that we can approximate In Fi by 2!(2,x), Thus, in Theorem the term (s) + vm P| 2g YslIF + v PPz Ys||r corresponds to [(;; X') while the term of
(R) mm
corresponds to [(: X). Recall that the information can be decomposed as
IZ; - (Z; + (ZZ ((2
(14)
where we want to maximize the predictive information X(;) while minimizing (Z; (??).
Thus, in order improve generalization, we also need control (R.,( to restrict the superfluous information I (Z; x|X'), in addition to minimize [f()) V
vm
P2gYslla + Ja [P2, Ys|le that
corresponded to maximize the predictive information I(Z; X'). Although we can explicitly add regularization on [Z; x|X') to control
2R__(F) it is possible that T(Z; x and 2Rm(() are
ym
ym
implicitly regularized via implicit bias through e design choises (Gunasekar et al. 2017 Soudry et al.
2018, Gunasekar et al. 2018). Thus, Theorem connects the information-theoretiic understanding of SSL with the probabilistic guarantee on the generalization ability.
[
6.4 COMPARING GENERALIZATION BOUNDS
The generalization bound of SimCLR (Saunshi et al. 2019) requires the number of label classes to go infinity to make the generalization gap decrease towards zero. In contrast, the bound on VICReg in Theorem 2 does not require the number of label classes to approach infinity to let the generalization gap go to zero. This reflects the fact that, unlike SimCLR, VICReg does not use negative pairs and thus does not use a loss function that is based on the implicit expectation that the labels of a negative pair "y*"y")) are different. Another difference is that our VICReg bound improves as n increases, while the previous bound of SimCLR (Saunshi et al., 2019) does not depend on n. This given y per class
because the previous work assumes partial access to the true distribution for setting W, which removes the importance of labeled data size n and is not assumed in study. Consequently, our bound provides a new insight for VICReg regarding the ratio of the effects of m v.s. n through G //mm(1/)mm + (1/1///// Finally, Theorem 2 also illuminates the advantages of VICReg over standard supervised training. That is, with standard training, the generalization bound via the Rademacher complexity requires the complexities of hypothesis spaces, R, (W)/ v and Rr, (F)/ /n. with respect the size of labeled data n. instead of the size of unlabeled data m. Here, RR, (W) is the the normalized Rademacher complexity for the hypothesis space of w. Thus, Theorem 2]shows that using SSL, we can replace all the complexities of hypothesis spaces in terms of n with those in terms of m. Since m is typically much larger than n, this illuminates the benefit of SSL.
7 CONCLUSIONS
In this study, we examine SSL's objective function from an information-thhorreic perspective, Based on transfering of the required stochasticity the input distribution, we show how SSL objectives can be derived. Thus, even when using deterministic DNs, it is possible to perform an information- theoretic analysis. The second part of the paper rediscovered SSL loss functions from first principles and demonstrated their implicit assumptions. We empirically validated our analysis and confirmed the validity of our novel understanding. As a result of our analysis, we have proposed new SSL algorithms that perform better than existing ones. Furthermore, we derived generalization bound on the downstream task, tight to known information objeective terms and demonstrate that VICReg minimizes it. In addition, our work opens many new avenues for future research, including better estimation of information -tteorttiit quantities that are consistent with our assumptions and identifying which SSL method is the most appropriate according to data characteristics. In addition, our probabilistic guarantee suggests that VICReg can be further improved for the setting of partial label information by aligning the covariance matrix with the partially observable label matrix.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alessandro Achille and Stefano Soatto. Information dropout: Learning optimal representations through noisy computation. IEEE transactions on pattern analysis and machine intelligence, 40 (12):2897-2905, 2018.
N.A. Ahmed and D.V. Gokhale. Entropy expressions and their estimators for multivariate distributions. IEEE Transactions on Information l'heory, 35(3):688-66)) 1989. doi: 10. 109/18.3099..
Alexander A Alemi, lan Fischer, Joshua V Dillon, and Kevin Murphy. Deep variational information bottleneck. arXiv preprint arXiv: 1612.00410, 2016.
Rana Ali Amjad and Bernhard Claus Geiger. Learning representations for neural sewwork-based classification using the information bottleneck principle. IEEE transactions on pattern analysis and machine intelligence, 2019.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. A theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv: D:Xi:09902.09299 2019.
Philip Bachman, Devon Hjelm, and William Buchwalter. Learning representations by maximizing mutual information across views. Advances in neural information processing systems, 32, 2019.
Randall Balestriero and Richard Baraniuk. A spline theory of deep networks. In Proc. ICML, volume 80, pp. 374-383, Jul. 2018.
Randall Balestriero and Yann LeCun. Contrastive and honn-cooottatiiveeeeeffsssesseis learnigg recover global and local spectral embedding methods, 2022. URL /tt.ttttt///arii.o////////221111
Adrien Bardes, Jean Ponce, and Yann LeCun. Vicreg: Variane-iivarrane-ccvaaanne regularization for self-super learning. arXiv preprint arXiv:2105.04906 2021.
Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3NN0v)4433-482, 2002.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Specctally--normalizedd margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and R Devon Hjelm. Mine: mutual information neural estimation. arXiv preprint arXiv:1801.04062 2018.
Brendon J Brewer. Computing entropies with nested sampling. Entropy, 19(8):422, 2017.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. Advances in Neural Information Processing Systems, 33:9912 99-49, 2020.
Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self-supervised vision transformers. In Proceedings the IEFF/CVF International Conference on Computer Vision, pp.
2021.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp- 1597-1607. PMLR, 2020.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 15750-15758, 2021.
Elliott Ward Cheney and William Allan Light. A course in approximation theory, volume 101. American Mathematical Soc., 2009.
Ralph B. D' Agostino. An omnibus test of normality for moderate and large size samples. Biometrika, 58(2):31-3443 1971. ISSN 00063444. URL http://wwwwwibooooogggbeb222222
10

---

Under review as a conference paper at ICLR 2023
Zheng Dang. Kwang Moo Yi, Yinlin Hu, Fei Wang, Pascal Fua, and Mathieu Salzmann. Eigendecomposition-reee training of deep networks with zero eigenvalue- based losses. In Proceed- ings of the European Conference Computer Vision (ECCV), pp. 768-783, 2018.
Arthur P Dempster, Nan M Laird, and Donald Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39(1): 1-22, 1977.
Yann Dubois, Benjamin Bloem-Reddy, Karen Ultrich, and Chris Maddison. Lossy compression for lossless prediction. Advances in Neural Information Processing Systems, 34, 2021.
Magnus Egerstedt and Clyde Martin. Control theoretic splines: optimal control, statistics, and path planning. Princeton University Press, 2009.
Cesare Fantuzzi, Silvio Simani, Sergio Beghelli, and Riccardo Rovatti. Identification of piecewise affine models in noisy environment. International Journal of Control, 75(18):1472-11 2002.
Marco Federici, Anjan Dutta, Patrick Forré, Nate Kushman, and Zeynep Akata. Learning robust representations via multi-view information bottleneck. arXiv preprint arXiv:2002.07017, 2020.
Charles Fefferman, Sanjoy Mitter, and Hariharan Narayanan. Testing the manifold hypothesis. Journal of the American Mathematical Society, 29(4):983-104) 2016.
Mike B. Giles, Collected matrix derivative results for forward and reverse mode algorithmic differ- entiation. In Christian H. Bischof, H. Martin Bücker, Paul Hovland, Uwe Naumann, and Jean Utke (eds.), ), Advances in Automatic Differentiation, pp. 35 44, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
Z. Goldfeld, E. van den Berg, K. Greenewald, I. Melnyk, N. Nguyen, B. Kingsbury, and Y. Polyanskiy. Estimating Information Flow in Neural Networks. ArXiv e-prints, 2018.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. Conference On Learning Theory, pp. 297-299. PMLR, 2018.
Goodfellow, Y. Bengio, and A. Courville. Deep Leurning, volume MIT Press, 2016.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach to self-supervised learning. Advances in neural information processing systems, 33:21271-21 2020.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pp. 6151-6159 2017.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pp. 9461-9471, 2018
Kaiming Hc. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 9729-9738, 2020.
R Devon Hjelm, Alex Fedorov, Samuel Aavoie-Marchildon Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint arxiv:1800 066000 2018.
Marco Huber, Tim Bailey, Hugh Durrant- Whyte, and Uwe Hanebeck. On entropy approximation for gaussian mixture random vectors. In IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems, pp. 181 188, (9 2008. doi: 10.
11

---

Under review as a conference paper at ICLR 2023
Catalin Ionescu, Orestis Vantzos, and Cristian Sminchisescu. Matrix backpropagation for deep networks with structured layers. In 2015 JEEE International Conference on Computer Vision (ICCV), pp. 2965-2973, 2015. doi: 10. 10.1109//CCV22215.33999
Jonathan Kahana and Yedid Hoshen. A contrastive objective for learning disentangled representations. arXiv preprini arXiv:2203. / /284, 2022.
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. MIT-CSAIL-TR-2018-011 Massachusetts Institute of Technology, 2018.
Kenji Kawaguchi, Zhun Deng, Kyle Luh, and Jiaoyang Huang. Robustness Implies Generalization via Data- DetaaDeeenddett Generalization Bounds, In International Conference on Machine Learning (ICML), 2022.
Artemy Kolchinsky and Brendan Tracey. Estimating mixture entropy with pairwise distances. Entropy, 19(7):361,
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable self-supervised learning. Advances in Neural Information Processing Systems, 34, 202
Kuang-Huei Lee, Anurag Amab, Sergio Guadarrama, John Canny, and Ian Fischer. Compressive visual representations. Advances in Neural Information Processing Systems, 34, 2021b.
Ralph Linsker. Self-organization in perceptual network. Computer, 21(3):105-117, 1988.
Julieta Martinez, Jashan Shewakramani, Ting Wei Liu, Ioan Andrei Bårsan, Wenyuan Zeng, and
Raquel Urtasun. Permute, quantize, and fine-tune: Efficient compression neural networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp.
2021.
Ishan Misra and Laurens van der Maaten. Self-supervised learning of pretext-invariant representations. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp.
6707-6717, 2020.
Neeraj Misra, Harshinder Singh, and Eugene Demchuk. Estimation of the entropy of multivariate normal distribution. Journal of Multivariate Analysis, 92(2):324-342, 2005. ISSN 0047-259X. doi:
URL
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2012.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Proc. NeurlPS, pp. 2924 2932, 2014.
Radford M Neal and Geoffrey E Hinton. view of the em algorithm that justifies incremental, sparse, and other variants. In Learning in graphical models, pp. 355-368. Springer, 1998.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. In Advances in Neural Information Processing systems, pp. 271-279, 2016.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint 1rXiv:1807.03748 2018.
Zoe Piran, Ravid Shwartz-Ziv, and Naftali Tishby. The dual information bottleneck. arXiv preprint arXiv:2006. 1,4441,,00.04641, 2020.
Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khandeparkar. A theoretical analysis of contrastive unsupervised representation learning. In International Confer- on Machine Learning, pp. 5628-5637 PMLR, 2019.
12

---

Under review as a conference paper at ICLR 2023
Shai Shalev-Shwarte and Shai Ben-Davis Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Ravid Shwartz-Ziv. Information flow in deep neural networks. arXiv preprint arXiv:2202.06745 2022.
Ravid Shwartz-Ziv and Alexander A Alemi. Information in infinite ensembles of infinitely-wide neural networks. In Symposium on Advances in Approximate Bayesian Inference, pp. 1-17. PMLR, 2020.
Ravid Shwartz-ZD Ziv and Naftali Tishby. Opening the black box of deep neural networks via information. arXiv preprint wwX.v:1703.008/11 2017.
Ravid Shwartz-Ziv, Amichai Painsky, and Naftali Tishby. Representation compression and general- ization deep neural networks, 2018.
Ravid Shwartz-Ziv Ziv, Micah Goldblum, Hossein Souri, Sanyam Kapoor, Chen Zhu, Yann LeCun, and Andrew Gordon Wilson. Pre-train your loss: Easy bayesian transfer learning with informative priors. arXiv preprint ar0iv: 10279, 2022.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1): 2822-28788 2018
Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Conference on Learning Theory, pp. 3437-3452. PMLR, 2020.
Haoqing Wang, Xun Guo, Zhi-Hong Deng, and Yan Lu. Rethinking minimal sufficient representation in contrastive learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16041-16050, 2022.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere. In International Conference on Machine Learning, pp. 9929 9939. PMLR, 2020.
Aolin Xu and Maxim Raginsky. Information-theorret analysis of generalization capability of learning algorithms. Advances in Neural Information Processing Systems, 30, 2017.
Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self-supervised learning via redundancy reduction. International Conference on Machine Learning, pp. 12310- 12320. PMLR, 2021.
Zhanghao Zhouyin and Ding Liu. Understanding neural networks with logarithm determinant entropy estimator. arXiv preprint arXiv:2105.03705, 2021.
Roland S Zimmermann, Yash Sharma, Steffen Schneider, Matthias Bethge, and Wieland Brendel. Contrastive learning inverts the data generating process. In International Conference on Machine Learning, pp. 12979-12990. PMLR, 2021.
A DATA DISTRIBUTION AFTER DEEP NETWORK TRANSFORMATION
Theorem 3. Given the setting of eq. (4) the unconditional DN output density denoted as Z approxi- mates (given the truncation of the Gaussian on its effective support that included within a single region w of the DN's input space partition) mixture of the affinely transformed distributions x xl(""(()) e.g. for the Gaussian case
T=n
Z~
N (Au((n))z bw(n))) AT A Exy Auto:))
where wwx" Ω < 2y is the partition region in which the prototype ot lives in.
13

---

Under review as a conference paper at ICLR 2023
Proof. We know that If S (( )x s 1 then f is linear within the effective support of p. Therefore, any sample from p will almost surely lie within single region w 52 and therefore the entire mapping can be considered linear with respect to p. Thus, the output distribution is a linear transformation of the input distribution based on the per-region affine mapping.
B LOWER BOUNDS ON Ey [log (((xx²)
In this appendix we present the full derivation of the lower bound on Ey [log (2|22))]
Because X' is Gaussian, we can write it as Z' ul²²) + L(x')e where NO 1) and L(x)) E(r'). Now, setting Σ, = I, will give us:
En Dog {(2|x))]
(15)
[log (=(22))
=
(16)
d
1
(2 21' (1)) (a - -z)
2
log 2n
2
(17)
d
log 2T
1
Bayls' (===1)²
(18)
2
d
log 2T
1
Eg
(z - -m(x)) - I(01)c)
(19)
2
2
d
1
(: mmz2))² 2( -m(x) L(d))c) ((L(Z))))* (L(x")c))
log 2T
Ee
2
2
(20)
d
log 2TT
Ee
(:
+ + (==2))))
E. [ ((=')²) L L(x')c) =
2
2
(21)
d
1 Tr log 2ix')
log 2T
(2 - -((x)))²²
(22)
2
2
where Fy, (log q<2(=²)] = Ey [log Ezy [<<2|=]]]] 2 E., [=]=() by Jensen's inequality,
E. = 0 and E. le ((x)) = Tr log E(x') by the Hutchinson's estimator.
Ez/s [E2]] /ar [log q(2|2')|]
(23)
d
1
E
log 2T
(z u(x'))²
Tr Tr I(1') (r())((())
(24)
2
2
d
log 2n
-
1
Ezju
(2= M(
1 Tr log 2(x')= =
(25)
2
d
log 2nT
-
1
Ee
((u(e)) + M(x)e m(a'))²
Tr Trlog E(x')
2
2
(26)
d
1
Es ((u(e) - m(a'))²] + Ee [(((x) - u(x')) M(x)e]
log 2n
2
2
(27)
1 E. [<" L(x)e 1 ((o'' =
- Trloo
(28)
d
1
1
log 2n
2/ (m(x) =m(x1)²²
Tr log E(x) T log E(x')
2
2
(29)
d 2
1 (m(x) - u(x'))²
1 log (E(x)) (E(x'))
log 2T
(30)
2
14

---

Under review as a conference paper at ICLR 2023
C ENTROPY ESTIMATORS
The estimation of entropy is one of the classic problems in information theory, where Gaussian mixture density is one of the most popular representations. With sufficient number of components, they can approximate any smooth function with arbitrary accuracy. For Gaussian mixtures, there is, however, closed-form solution to differential entropy. There exist several approximations in the literature, including loose upper and lower bounds (Huber et al.) 2008). Monte Carlo (MC) sampling is one way to approximate Gaussian mixture entropy. With sufficient MC samples, unbiased estimate of entropy with an arbitrarily accurate can be obtained. Unfortunately, MC sampling is a very computationally expensive and typically requires a large number of samples, especially in high dimensions (Brewer 2017). Using the first two moments of the empirical distribution, VIGCreg used one of the most straightforward approaches for approximating the entropy. Despite this, previous studies have found that this method is poor approximation of the entropy in many cases Huber al. (2008). Another options use the LogDet function. Several estimators have been proposed to implement it, including uniformly minimum variance unbiased (UMVU) (Ahmed & Gokhale 1989), and bayesian methods Mísra et al. (2005). These methods, however, often require complex optimizations. The LogDet estimator presented in Zhouyin & Liu (202T) used the differential entropy a order entropy using scaled noise. They demonstrated that can be applied to high-dimensional features and is robust random noise. Based on Taylor-series expansions, Huber et al. (2008) presented a lower bound for the entropy of Gaussian mixture random vectors. They use Taylor-series expansions of the logarithm of each Gaussian mixture component to get analytical evaluation of the entropy measure. In addition, they present a technique for splitting Gaussian densities to avoid components with high variance, which would require computationally expensive calculations. Kolchinsky & Tracey (2017) introduce novel family of estimators for the mixture entropy. For this family, a pairwise-distane function between component densities defined for each member. These estimators are computationally efficient, as long as the pairwise-distance function and the entropy of each component distribution are easy to compute. Moreover, the estimator is continuous and smooth and is therefore useful for optimization problems. In addition, they presented both lower bound (using Chernoff distance) and an upper bound (using the KL divergence) on the entropy, which are are exact when the component distributions are grouped into well-separated clusters,
D EMPIRICAL VALIDATION OF OUR ASSUMPTION
We will try to verify empirically our assumptions on different datasets We compute the pairwise (2 distances between images for seven datasets: MNIST, CIFAR10, CIFAR100, Flowers 102, Food101, and FGVAircaft. We found that even for raw pixels, the pairwise distances are far from zero, which means you can use small Gaussian around each point without overlapping. Consequently, the effective supports of these high-dimensional datasets are not overlapping, and our assumption is realistic even for current popular SSL datasets..
E EXPERIMENTAL VERIFICATION OF INFORMATIOON-ASEBI BOUND OPTIMIZATION
Setup Our experiments are conducted on CIFAR- 10 Krizhevsky et al. 2209)). We use ResNet- 18 (He et al., 2016) as our backbone. Each model trained with 512 batch size for 800 epochs. We use linear evaluation to assess the quality of the representation. Once the model has been pre-trained, we follow the same fine-tuning procedures as for the baseline methods (Caron et al. 2020).
F EXPECTATION MAXIMIZATION AND COLLAPSING
G ON BENEFITS OF INFORMATION MAXIMIZATION FOR GENERALIZATION
In this Appendix, we present the complete version of Theorem along with its proof and additional discussions.
15

---

SimCLR Barlow Twins Under review as a conference paper at ICLR 2023
175
150
12 Distances
100
75
50
25
MNIST
CIFAR10
CIFAR100
Flowers102
Food101
FGVCAircraft
Figure 2: The Gaussians around each point are not overlapping The 12 distances between raw images for different datasets
Method
Accuracy
89.72 + 0.05
88.81 + 0.1
VICReg
89.32 = 0.09
VICReg + Pairwise Distances Estimator (ours)
90.09 = 0.09
VICReg + Log Derminate Estimator (ours)
89.77 = 0.08
Table 1: Entropy estimator achieved better results on SSL CIFARIO accuracy on linear
evaluation of SSL for different entropy estimators, The best results achieved by pairwise distances lower bound
16

---

Under review as a conference paper at ICLR 2023
0.0001
0.02505
0.05
0
0.0001
-100
-200
0
0.02505
-100
-200
0
0.05
-100
-200
500
10000
500
10000
500
1000
Figure 3: Evolution of the entropy for each the learning rate configurations showing that the impact of picking the incorrect learning rate for the data and/or centroids lead to collapse of the samples.
G.1 ADDITIONAL NOTATION AND DETAILS
We start to introduce additional notation and details. We use the notation of x E X' for an input and y y C RC for output. Define p(y) TP(Y = y) be the probability of getting label y and p(y) = Σー 1 f3 = y} to be the empirical estimate of p(y). Let Ç be an upper bound on the for all y E V. Define the minimum norm solution W3 of the unlabeled
norm of the label as ||l|2 data as W3 minimizew ||W'||| |F W' E arg minw m E [[ - (a. )l(a. Let us be a data-dependent upper bound on the per-sample Euclidian norm loss with the trained model as ||Ss fe(x) yl| < Kg for all (x, y) E X' x y. Similarly, let Kg be data-dependent upper bound on the per-sample Euclidian norm loss as | (e) - yl < ng for all (I, y) E X x y. Define the difference between Ws and W3 by c [Ws Walla Let W be hypothesis space of W such that W3 W. We denote by R., FW = - Es,g wsupwew.feF Dmt & (x Wf(x;) [I] the normalized Rademacher complexity of the set fx+ (x+) Wf(x+) W W. F). we denote by i a upper bound on the per-sample Euclidian norm loss as W f(x) - all < 6 for all (z. y. W. f) X x y W x F.
Vun
We adopt the following data data-generatin generating process model that used in the previous paper on analyzing contrastive learning (Saunshi et al. 2019). For the labeled data, first, y is drawn from the distritbuion
17

---

Under review as a conference paper at ICLR 2023
4
H(Z)=40
H(Z)=34
S data centroids
data
data centroids
centroids
Figure 4: Evolution of GMM training when enforcing a one-to-one mapping between the data and centroids akin to K-means ie. using small and fixed covariance matrix. We see that collapse does not occur. Left In the presence of fixed input samples, we observe that there is no collapsing and that the entropy of the centers is high. Right when make the input samples trainable and optimize their location, all the points collapse into a single point, resulting in a sharp decrease in entropy.
on V, and then is drawn from the conditional distribution Dy conditioned on the label y. That is, we have the join distribution D(x, y) (2)())(()) with ((2,, )x)) DD. For the unlabeled data, first, each of the unknown labels y* and y is drawn from the distritbuion p. and then each of the positive examples x and x + is drawn from the conditional distribution Dy+ while the negative example is drawn from the D Unlike the analysis of contrastive learning, we do not require the negative samples. Let T3 be a data-dependent upper bound on the invariance loss with the trained representation as ( [o() S Tg for all (z ~ DJ and y E V. Let T be a data- iata-independent upper bound on the invariance loss with the trained representation as (ze, x) ~ D
fx))l s for all y, and / E F. For the simplicity, we assume that there exists a function g" such that y = g (x) E Rd for all (x, y) E X x y. Discarding this assumption adds the average of label noises the final result, which goes to zero the sample sizes n and m increase, assuming that the mean of the label noise is zero.
G.2 RESULT
The following theorem is the complete version of Theorem 2
Theorem 4. For any 8 > O, with probability at least 1 5, the following holds:
(eple,, < cIg(fo)
P 23
Ys
Pz Yslle + Qm.n
(31)
mm
Vn
where
2mm (J)
In(3/8)
(3/3
Qm,, =
+
+ T3V
mm
2m
2n
+ Ks
VV(y) /pw))
2n
DEY
4Rm (Wo
In(4/5)
In(4/8)
2x
+ 2xg V
Vm
2m
2n
Proof. The complete proof is presented in Appendix
G.3
18

---

Under review as a conference paper at ICLR 2023
The bound in the complete version of Theorem is better than the one in the informal version of Theorem 2 because the factor c. The factor c measures the difference between the minimum norm solution Ws of the labeled training data and the minimum norm solution Ws of the unlabeled training data. Thus, the factor e also decreases towards zero as ni and m increase. Moreover, if the labeled and unlabeled training data are similar, the value of e is small, decreasing the generalization bound further, which makes sense. Thus, we can view the factor as a measure on the distance between the labeled training data and the unlabeled training data.
We obtain the informal version from the complete version of Theorem by the following reasoning to simplify the notation in the main text. We have that cIg cfg(fe) + 2R...
Vm Is(fo)
(F) + Q. vm
where Q (c (Jo) = S + as m, + oc, since
Vm
m, 71 - co.
However, this reasoning used only to simplify the notation in the main text. The bound in the complete version of Theorem 2 is more accurate and indeed tighter than the one in the informal version.
In Theorem Qm, as m,n n 00 if R.n. (F)
as m XC. Indeed, this typically
holds because Rm (F) (1) as m + 00 for typical choices of F, including deep neural networks (Bartlett et al. 2017 Kawaguchi et al. 2018 Golowich al. 2018) as well as other common machine learning models (Bartlett & Mendelson 2002 Mohri et al. 2012: Shalev-Shwartz & Ben-David
2014).
G.3 PROOF OF THEOREM 2
Proof of Theorem 2 Let W = Ws where Ws is the the minimum norm solution as Ws minimizew ||W |F s.t. W E arg minw n " fo(;)) - wil?. Let W Ws where Ws is the minimum norm solution as W = Ws = minimizew [|W|ee s.t. W arg minw J. E [W 9" g=xx= (22))1 Since y = g (x),
y= g #
W' fa(x) + (x) - W" fa(x)) "' = W fo(x) + p(x)
- g" (z) W (z)z. Define Ls(w) = A Ei= fo(x)) 3/l1- Using these, where =
Ls(w)= fo(z)) - -vill
[o - W fo(x)) - :((x))l
71
[o(,)) W fo(z))) -1 1 n
|<<((;))|
11
71
[o
|1+((=))
where W- W - W', We now consider new fresh samples F, ~ Dy: for = I,..., to rewrite the above further as:
Ls(w)= >
[folz) Σ [<<(x))]
[o.,)) - (o.) - fo(x)))) 1
Σ
[xx)))))
12
im
[o - 1 71 Σ fo..) W
1
Σ
[(((W)))
72
1
[o
([o()) fo(x)))
[>(((;))|
19

---

Under review as a conference paper at ICLR 2023
This implies that
1 E W fo()))) (s(w) 1
Σ ( - fo(x))) - Σ [=)()))
Furthermore, since y = W fa(x) + (xx)) by writing Tt = fo(E)) + +x(5,) (where y; = y: since T Dy, for 1, ,,..,, n),
WS Sa (3x))) = n
Σ
[W W so(x))
7
1
(o D1 (
n
(o(s)) --1- Σ ||.((.))
Combining these, we have that
n
1
[o(F)) Dell S Ls(w) +
((f(()) fo(a)))l
(32)
n
n
|x(x))| 1
72
To bound the left-hand side of equation 32 we now analyze the following random variable:
- YII
[Wsfo(;;) - T7ll.
(33)
where T1 = since E. ~ Dy. for i I...., Importantly, this means that as Ws depends on ys. Ws depends on Vi- Thus, the collection random variables (ā)) - yn ... I| fo(n,) Ja is not independent. Accordingly, we cannot apply standard concentration inequality to bound equation 33 A standard approach in learning theory is to first bound equation 33 by se
all
(T;))(;;) - %/l S supwew EE,,, || fa fa()) - yl x Σ W fo( - Me for some hypothesis space W (that is independent of S) and realize that the right-hand side now contains collection of independent random variables || ( - 71 fill..., (/,, Ball for which utilize standard concentration inequalities. This reasoning leads to the Rademacher complexity of the hypothesis space W. However, the complexity of the hypothesis space W can be very large, resulting into loose bound. In this proof, we show that space W by using a very different approach with conditional expectations to
avoid the dependency take care the dependent random variables Wss fe (z1)= V vi.l..., WWs (n,)) I. Intuitively, we utilize the fact that for these dependent random variables, there are a structure of conditional independence, conditioned on each y E y
hypothesis
We first write the expected loss as the sum of the conditional expected loss:
[x.x(]WsJooXX- YI]] = Σ
Ex,y [IlWs YI1 Y = u)P(Y =
yEy
Σ
Ex, [Il (l,s(()))) - vI|IPYY y),
nEY
where X2 is the random variable for the conditional with Y y. Using this, decompose
equation 33 into two terms:
n Wsf((E;) Jill
Ex,y BayIllssf((R YIl n
(34)
T=1
Σ NEY
Ex, [l - 111
Σ
[[sff(Et) Fill
n
n
2m1
[nnl
Σ
Ex, (| - wlll
[((y = y)
n
yEy
20

---

Under review as a conference paper at ICLR 2023
where
I, = = fiE [n] =y.
The first term in the right-hand side of equation 34 is further simplified by using
[Wff((.)) - Tell 1 ΣΣ
[Wsff(E.) - =ll
yEY TE
as
[Tl Wsfo(F;) - Uzll
Σ
Ex, (l - -Vll
n
NEY
1
Σ
[ul
Ex, [x, -lll
([ssfo vll
yE
IET
where 5 = (y V: [Tyl # 0}. Substituting these into equation equation 34 yields
YIll (Wsf((E)) - Tsll
(35)
Σ Fzyl [x, - wlll
(isf((;)) y/1
Inp TT
yEY
Ex, Bxx,lWssf(XX, - wlll (P(Y =v) n
[Tv
Σ DEy
Importantly, while dependent random variables, (( - yll...., s fT - yll are independent random variables since Ws and o are independent and is fixed here. Thus, by using Hoeffding' 's inequality (Lemma| 1. and taking union bounds over E D, we have that with probability at least - 8, the following holds for all y E y:
Fnll (l...) -. Gn on the right-hand side of equation 35
In((51/8))
Ex, (1l]ssosXX)p - -
Σ ET
[Wsso(Te) wll S SKSV
Inl
2|Inr
This implies that with probability least 8,
Σ
Ex, (l,][lsooXX,))> wlll
[Wss((F)) v/1
[Ty VeI,
DE
In( in(51/0)
KS Σ
2|In|
vEÿ
In In(())/6)
Σ
2n
vEY
Substituting this bound into equation
35 have that with probability at least 5,
Ex,Y (c.lloo Y1
[Wff((E.) Tell
(36)
< Ks
Σ VP(v)
in(15(/6))
Σ
Ex, (Wss(((x)) -vlll (P(Y- y)
Izl
2n
VEJ
vEY
21

---

Under review as a conference paper at ICLR 2023
where
p(v) = |yn n
Moreover, for the second term on the right-hand side of equation 36 by using Lemma of Kawaguchhi et al. 2022), we have that with probability at least - 6.
Σ Ex vEY
Ex, (Ilsso(X,,)) =lll (PeYY- v)
[Tn]
2 (In(/))
Σ NEY
E (llsx, - w/l Ull)
2n
2
S Ks
Σ PEY
p(u)
2n
where p(y) = P(Y y). Substituting this bound into equation 36 with the union bound, we have that with probability at least - 8,
1
Fx.r|IWssooNN YIIl
Weso - Dell
(37)
n i=1
In 1n(2(51/8)
21n(21)1/6)
I Ks
ΣV Voy)
+ Kg
Σ
pl()
2n
2n
NE
DEY
2 (22(11)
2ln(2 (2))
Σ
Viy)
KS
Σ
p(y)
KS
2n.
2n
vEY
DEY
2 2l
S KS
V p(U) + VP())
2n
VEY
Combining equation 32 and equation
37
implies that with probability least 1 5,
E Ex,y II.Yll|sssoCX - YII
(38)
2 2 (2(2188/8)
(a.)((;)) Del + Ks\
VV(y)= + vp(y)
2n
NEV
< Ls(ws) + [[o(z.) - fo(x)))
n ||(x;))|
n Σ
22n
+
||+(,)) + 1
VVly) vP())
n2
2n
DEY
We will now analyze the term
Σ ||
+ + Σm [(((T))) on the right-hand side of equa-
tion 38 Since W
Ws. s,
Σ [[(()))
- n
Σ lgg - Wsfo(z;))l
By using Hoeffding's 's inequality (Lemma] D. we have that for any 0, with probability at least
1 5,
1
In(1/8)
(xx) Wsfo( < E, (x+) - Wsfo(*
+ Kg
2n
22

---

Under review as a conference paper at ICLR 2023
Moreover, by using (Mohri et al. 2012 Theorem 3.1) with the loss function x² + W f(x*))l (i.e., Lemma 2). we have that for any d > O, with probability at least 1 1-8,
11g"(x*))
Es I1lg((**) - Wsfo(x 1
2R CW F) Wsfo(x7)1l
1n(1/))
1g (x))
viV
m
2m
(39)
where R. (W F) = Vm Lsp.suupeeeeees (ot WI(x])]] is the normalized
&ills
Rademacher complexity of the fa+ H 11g (=*)- I| W W. F} (it is normalized such that (F) = O(1) as m + ac for typical choices of F), and Ei...., Sm are independent uniform random variables taking values in {-1,1}. Takinng union bounds, have that for any > 0, with probability at least -
1 Σ I[(()))
Σ
(g Wsfo(x)))l 2Rm (WoF) + ki
In(2/0) 2m
In(2/0)
+
mm
2n.
Similarly, for any d 0, with probability least 1- 8,
Wsfo(a))ll 2Rm (W F)
In(2/6)
In
(2/0))
|ل Σ 11g
+ +
+ Kg
vm
2m
2n
Thus, by taking union bounds, we have that for any 5 > 0, with probability at least
6,
a
a
Ix(())) Σ (+x))))
(40)
2 m
4Rm (W
In(4/0)
Im(4/5)
l (xt)
(zf +
+ 2n/
2xg V
m
mm
2m
2n
To analyze the first term on the right-hand side of equation 40 recall that
1
Wg = minimize W
[W s.t. W' e arg min
(41)
m
Here, since (o(x)) E RR, we have that W veo[W ( @ vec[W] RR"
where I, Rrxr is the identity matrix, and [f(())) & 1. R is the Kronecker product of the two matrices, and vec[W]] E dRdr is the vectorization of the matrix W E igrdd, Thus, by defining A, = [ & I,] E RRr and using the notation of w = vec[W] and its inverse W = vec - [w] (i.e.. the inverse of the vectorization from grxd xd to d with a fixed ordering), we rewrite equation by
Wg vec- where
Wz minimize || 1| s.t. w' arg min Σ 11g. Awll2
with g. (xxt E RR. Since the function > i=1 119. A 2 is convex, necessary and sufficient condition the minimizer of this function is obtained by
m
1g
Aw
AJ (ti Arw) E dr
This implies that
Σ A. A.
A gi-
7=1
23

---

Under review as a conference paper at ICLR 2023
In other words,
A1
91
A2
92
A Aw = A
where =
E dmr and =
E R
:
Am
9m
Thus,
w' E arg min Σ
19: - A,wl {(A A) +o:ue g Nu)l(A))
where (ATA) is the Moore-Penrose inverse of the matrix ATA A and Null(A) is the null space of the matrix A. Thus, the minimum norm solution obtained by
vee [Ws] we (AT A)T AT
Thus, by using this Ws. we have that
m2
T2
11g" 1x²) - Wsso(at)ll
(g: Arw3)a)²
m
m
m
((: A,
m
m
(g: Awgg)a
m
llg - Awslla
Vm
1 |gg A(A = Vm
||( A(A A) A D)gll2
where the inequality follows from the Jensen's 's inequality and the concavity of the square root function. Thus, we have that
|x(x;)|
(42)
7
|I( - A(A A) A )al1 + 4Rm (WoF) + 2
In(4/0)
In(4/8)
2x5
mm
Vm
2m
2n
By combining equation 38 and equation 42 with union bound, we have that
Wss Yll
(43)
< [s(ws)) +
([(())))) - fo(os))
Pagl22
mm
4R. 4Rm(W (WoF)
In(8/8)
[I(88/)
+ 2
+ +2NsV
Vm
2m
2n
2n
(V(()) vp(s)).
+ KS\
2n
DEY
where W Ws W and PA = 1 A(A A AT
We will now analyze the second term on the right- side equation 43
( - fo(x:)) < |
l - fo(x))ll)
(44)
24

---

Under review as a conference paper at ICLR 2023
where [| is the spectral norm of W. Since Σ, shares the same label with 2; as Dy. (and Dy,), and because fo is trained with the unlabeled data 8, using Hoeffding's inequality (Lemma implies that with probability at least
In(1/0)
Σ (1fo(a.) fa(2:))l By-pB (z) fo(x))l] + TB
(45)
2n
Moreover, by using (Mohri et al. 2012, Theorem 3.1) with the loss function (2, + - (i.e., Lemma 2) we have that with probability at least 1 - 6.
Ey Dg [Ilff(()) fa(=))l = llfo(z;) - fo(x:t) + 2R, (F)
In(1/6)
+ +TV
m
2m
(46)
where (F) 1 Eg, (sppeE E {xll((x)) [a,
+ IIl is the normalized Rademacher complexity of the set {(x ((*,,x**)) + 11f(x*)) f(x++)ll
v
F} (it is normalized such that (F) = (1) as + oo for typical choices of F), and fi...., fm are independent uniform random variables taking values in 11,, Thus, taking union bound, we have that for any d > with probability at least -. 8,
((f(E,)) (xx))l
(47)
n
m
2Rm (F)
ln(2/6)
In(2/6)
W
m (o(())) fo(a;
+ +TS/
/m
2m
2n
By combining equation 43
and equation 47 using the union bound, have that with probability
least 1 - 6,
Ex [Il - []
(48)
m [so(x))) - So(x;- I|I +
2Rm (F)
In(4/8)
In(4/5)
S [s((w))+ + -|Wi|1
+ +TV
TS
Vm
2m
2n
1=1
2
4mm (W
In(16/8)
+ 2 (n(16/5)
+ Vm
Pagll2 +
+ 2x1
mm
2m
2n
21n(8)21/8)
(Vly) Vplv)
+KsV
2n
NEY'
= -s(ws)) + 1|/||2
[o(x - fo(at I1|
+ Vm
Pagllz + Qm...
1=1
where
(F)
In(3/8)
ln(3/6)
Qm, =lli12
+TV
+ T3V
Vm
2m
2nz
21n(6121/8)
Σ
(VD()) + VP(U))
+ Kg
2n
yEY
4Rm (Wo
In(4/8)
In(4/8)
+
+2x
+ 2xz V 2n
Vm
2m
Define 7g- = [f(xt)
E Rdxm Then, we have A 17g 59 Tr). Thus,
PA = 1- 1
T @ 411
& 1 & 4. =
[2s T (ZsZs T) & 1,] = 1 @ 4.]
where P25 Im Z (ZgZg T)tZg E m By defining Ys = [g" (x+ ) ....... (x.)))
Rmxr, since 9 = veol (Y.)
P || @ I,] vo || 2 vec Pz P2gll 1ll |Pz Yslif
(49)
25

---

Under review as a conference paper at ICLR 2023
On the other hand, recall that Ws is the minimum norm solution
We minimize [W s.t. W arg min
Σ W n
1 [o(x)) -vill
By solving this, we have
Ws YT 3s (2 T),
where Zs [f(xz)) ..... f(xx)) E Rdxn and Ys [1/1..... ,, T R Then,
Ls(ws) Σ (Wsf((x;) will 72 Σ
Σ ((Wsfo(z)) - v2)a)2
(Wsfo(zs) w))a)²
k=1
W -Y
Vn
||YT (Zs TZsT(Zs2, T) -T]lE
Vn.
I1(T 28 (2s 2s))
Thus,
1
Ls(ws) Vn PP Y
(50)
where Pzs 1 'ss' (z )
Zs.
By combining equation 48 equation 50 and using 1 S V2, have that with probability at least
1- 6,
2
Ex.r|IWsfe(X)) Y11 <cl(sf) + mm
P YslIF +
P
Pzll +
Qm.
(51)
Vn
where
2R (F)
In(3/8)
l3(3/))
2m,n
73
Vm
2m
2n
2 21n(61)118)
+ KS
VP(y) + pP())
2n
DEY
4R (R o o)
In(4/8)
In(4/8)
2x
+ 2xg
mm
2m
2n
H KNOWN LEMMAS
We use the following well-known theorems as lemmas in our proof. We put these below for the completeness. These are classical results and not results.
Lemma 1. (Hoeffding's inequality) Let X1...., Xn be independent random variables such that X; < b almost surely. Consider the average of these random variables,
1 (X1 + . X,). Then, for all t > 0,
S. =
In(1/6)
Ps
E [[Sa] - S. 2 (b (b-a))
a)p 2n < 6,
26

---

Under review as a conference paper at ICLR 2023
and
In(1/0)
Ps Sn [S.]] (b VV
S 6.
2n
Proof.
By using Hoeffding's inequality, we have that for all 0,
(- (- (b - a)²
2nt²
Ps (E [Sm] Sn 2 1) S exp
and
2nt2
Ps (Sn - E [Snn] 2 1) S exp
a)2
Setting 8 = exp
(-12 2nr [b-a]²
(-
and solving for l 0,
2nt
1/8 = exp
(b a)²
2n12
1n(110) (b- a)²
(b a)² 1nnn1 (1/1)) $2
2n
1= (b v)\ In(1/8)
2n
has been shown that generalization bounds can be obtained via Rademacher complexity (Bartlett & Mendelson 2002 Mohri et al. 2012; Shalev-Shwariz & Ben-David 2014). The following is trivial modification of (Mohri et al. 2012, Theorem 3.1) for one-sided bound on the nonnegative general loss functions:
Lemma 2. Let G be a set functions with the codomain [0, MM. Then, for any 5 > 0, with probability least 8 over an i.i.d. draw of m samples (g:) Th the following holds for all tp E G:
1
m
In(1/8)
Eg(0()))
S
(q.) + 2R (9) + MV
(52)
m
2m
where (G) = Essc/suppsee 1 Σm 1= (g)( and ......, , are independent uniform random variables taking values in {-1.1}.
m
Proof. Let S = ( and S
(g)) Define
( = sup Ey. (v()) weg
(ga))
(53)
m
To apply McDiarmid's inequality to (SS). we compute upper bound on (y(()) :p(S") where S and 5' be two test datasets differing by exactly one point an arbitrary index io; i.e. S; = S for all i + in and Si, # S% Then,
(ggh))
M
((S') ((S) S sup
(54)
VEg
m
m
Similarly, ((5) ((S)) < M least 1 - 5,
Thus, by McDiarmid's inequality, for any > 0, with probability at
m
In(1/5)
((S) < Es(p(S)) + MY
(55)
2m
27

---

Under review as a conference paper at ICLR 2023
Moreover,
Es [s)]
(56)
1
Σ Maw
Es
sup Es
(16))
(57)
VEG
i=1
S Es,s
sup VEg
(v(() - +((i))
(58)
im
$ R
sup NEG
(a(b((b)) - +((ai)))
(59)
1 (as((s)) (9)
< 2
sup NEG
(60)
where the fist line follows the definitions of each term, the second line uses the Jensen's 's inequality and the convexity of the supremum, and the third line follows that for each & [-1,+1], the distribution of each term (((((())) vt) - (x(())) 3)) is the distribution of (L(f(=)), v.) (x(((;;) vy)) since S and S' are drawn iid with the same distribution. The forth line uses the subadditivity of supremum. O
I SIMCLR
contrastive learning, different augmented views of same image are attracted (positive pairs), while different augmented views are repelled (negative pairs). MoCo (He al. 2020) and SimCLR (Chen et al.) 2020) are recent examples of self-supervised visual representation learning that reduce the gap between self-supervised and fully -upervsueee learning. SimCLR applies randomized aug- mentations to an image to create two different views, I and y, and encodes both of them with shared encoder, producing representations ru and ry. Both and ry are 12-normalized. The SimCLR version of the InfoNCE objective is:
Ex.y
log
kml e
where 7) a temperature term and is the number views in a minibatch
28


Reviews:
[{"review_id": "oFVa1N9BTaz", "reviewer": "Reviewer_48RM", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.\n2. The paper also presents a generalization bound on downstream tasks based on the above information-theoretical quantities.\n3. 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). ", "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.\n\n", "strength_and_weaknesses": "Strengths\n====\n1. It is always valuable to cast heuristic objectives under a new and more formal perspective/framework, which this paper achieves.\n2. Most of the discussion in the paper are fairly intuitive and easy to follow (at least until the derivation of VicReg).\n3. 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).\n\nWeaknesses\n====\n\nMy 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.)\n\n1. 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.\n\n2. 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. \n \n3. 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? \n\n4. 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. \n- 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?\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "gv1IyDr2e02", "reviewer": "Reviewer_DWKP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.  ", "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.", "strength_and_weaknesses": "**Strength**\n\nThe main strength of the paper is its justification of VICReg and the generalization bound provided. \n\n**Weakness**\n\n* 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.\n\n* The presentation of paper seems sloppy, awkward and sometimes lacks clarity. I am listing a few here.\n1. In Equation (3), the notation of raising the Gaussian density to the power of \"$T=n$\" is strange. \n2. 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?\n3. In section 6.1, the notation ${\\cal T}$ appears multiple times, which is supposed to mean transpose?\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MMHwnL1P3d", "reviewer": "Reviewer_KD44", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper intends to provide an understanding of self-supervised learning using information theory. \n\nFirst, they lay down certain assumptions for deterministic networks, under which they conclude that deterministic networks' projections are distributed as a mixture of Gaussians.\n\nThen, 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]*.\n\nAfter 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.\n\nFinally, 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.\n\n**References** \n\n*[Federici et al. 2020]* Learning robust\nrepresentations via multi-view information bottleneck. \\\n*[Chen and He 2021]* Exploring simple siamese representation learning.", "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. \n \n Under that assumption, they attempt to justify the objective of VICReg. \n\n   * 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.\n\nIt 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). \n\n  * 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. \n\nFinally, they present a new bound on the generalization of SSL methods for classification tasks and a linear layer on top of the learned representations. \n\n  * 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. \n\nOverall, 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**.\n\nFor 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.\n\n**Minor comments and nitpicks that did not impact the score of the review**\n\n* 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.\n\n* 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$.\n\n* In Section 4, before (6) I believe you wanted to write $q(z|z') \\sim \\mathcal{N}(z',\\Sigma_r)$.\n\n* 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.\n\n* In the last paragraph of Section 2 the citation of *[Achille and Soatto 2018]* should be citet.\n\n* Right before Section 4.1. it the citation of *[Moshksar and Khandani 2016]* should be with citep.\n\n* 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.\n\n* 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?\n\n* 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}$.\n\n**References**\n\n*[Achille and Soatto 2018]* Information dropout: Learning optimal representations\nthrough noisy computation. \\\n*[Moshksar and Khandani 2016]* Arbitrarily tight bounds on differential entropy of Gaussian mixtures. ", "strength_and_weaknesses": "**Strengths**\n\nThe paper includes a couple of nice ideas, for instance:\n\n* Considering the input as a mixture of Gaussians allows them to analyze properties of the output under certain assumptions. \n* Under the assumption that SSL with a stop-gradient operation is an Expectation-Maximization problem, one can try to avoid collapse explicitly. \n\nThe proof of the generalization bound for SSL algorithms is beautifully constructed and the resulting inequality is interesting.\n\n* They go around having to deal with the large Rademacher complexity $\\tilde{\\mathcal{R}}(\\mathcal{W})$ in a clever manner. \n* 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.\n\n**Weaknesses**\n\n* Sometimes the paper makes some claims without a citation to prior work:\n\n    *  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. \n    \n    * 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.\n\n* There are some mis-representations of the literature. \n\n    * 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]*.\n\n* Sometimes the paper is either not rigorous or forgets to add important information to the reader.\n\n    * 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?\n\n    * 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$.\n\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?\n\n    * 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.\n\n    * 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)}$.\n\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.\n\n    * 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.\n\n    * 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?\n\n        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.\n\n        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.\n    \n  * 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\\%. \\\n  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. \\\n  I believe that these findings and caveats should be more clear in the text of that section.\n\n  * 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. \\\n  Moreover, to employ *[Kawaguchi et al. 2022]* one needs that the random variable is multinomial and therefore finite. \\\n  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}$.\n\n  * 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.\n\n  * There are some restrictions on the norms that need to be imposed for the Theorem to work.\n\n    * 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.\n\n    * 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.\n\n* 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?\n\n**References**\n\n*[Wang and Isola 2020]* Understanding contrastive representation learning through alignment and uniformity on the hypersphere. \\\n*[Zimmermann et al. 2021]* Contrastive learning inverts the data generating process. \\\n*[Chen and He 2021]* Exploring simple siamese representation learning. \\\n*[Kawaguchi et al. 2022]* On the theory of implicit deep learning: Global convergence with implicit layers.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "HHOYTDxu3jy", "reviewer": "Reviewer_3Mx6", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The submission explores information-theoretically motivated objectives for self-supervised learning (SSL). \nThe 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). \nA 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.\nA generalization bound and relationships to prior criteria for SSL optimization (spec. VICReg) are also derived.", "summary_of_the_review": "The idea appears novel, but the practical significance of the results for SSL in general remains unclear.", "strength_and_weaknesses": "### Strengths\n\n1. **Clarity.** The paper is extremely well-written. I had no trouble understanding the ideas presented in the work and their relationship to prior work.\n\n1. **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.\n\n1. **Novelty.** Using a neural-networks-as-splines argument to derive an information-theoretic SSL optimization criterion appears novel.\n\n### Weaknesses\n\n1. **Assumptions are insufficiently related to practice.**\nBroadly, the manuscript aims to explain SSL in practice (judging from the introduction).\n\n    1. In Section 3.2, two assumptions are made regarding a model of the data distribution\n    (non-overlapping effective support) and sufficient Gaussian modes.\n    In practical settings (i.e., not in the limit of modes), how well does this represent data\n    distributions of interest to SSL?\n\n    1. The mapping $f$ is assumed *not* to be a dimensionality reduction operator (i.e., $f : D \\to K$ with $K \\ge D$).\n    Is this not false of the neural networks used as standard in SSL?\n\n1. **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$). \nThis is in contrast to the more complicated expressions in Balestriero & Baraniuk (2018), who define splines per layer (e.g., their Eq. (6)).\nCould you explain this discrepancy?\nHow could your setting \"be extended to the general case,\" as is claimed in Section 3.2?\n\n1. **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.\n\n### Minor\n\n1. Please number all equations, etc. in the manuscript.\n\n1. 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)\n\n1. The plot in Figure 1 looks stretched rather than scaled.\n\n1. Typo (both \"first\" & \"second\"): \"VICReg ... estimates the entropy of Z solely from the first second moment\"\n\n1. The \"Theorem\" counters in the appendix are off.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject