Improving Self-Supervised Learning by Characterizing Idealized Representations
Authors: Yann Dubois
Stefano Ermon
Tatsunori Hashimoto
Percy Liang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Self-Supervised Learning
Invariances
Contrastive Learning
Machine Learning
Representation Learning

Abstract: Despite the empirical successes of self-supervised learning (SSL) methods, it is unclear what characteristics of their representations lead to high downstream accuracies. In this work, we characterize properties that SSL representations should ideally satisfy. Specifically, we prove necessary and sufficient conditions such that for any task invariant to given data augmentations, probes (e.g., linear or MLP) trained on that representation attain perfect accuracy. These requirements lead to a unifying conceptual framework for improving existing SSL methods and deriving new ones. For contrastive learning, our framework prescribes simple but significant improvements to previous methods such as using asymmetric projection heads. For non-contrastive learning, we use our framework to derive a simple and novel objective. Our resulting SSL algorithms outperform baselines on standard benchmarks, including SwAV+multicrops on linear probing of ImageNet.

Improving Self-Supervised Learning by Characterizing Idealized Representations
Yann Dubois, Tatsunori Hashimoto, Stefano Ermon, Percy Liang
Stanford University
(yanndubs, thashim, ermon, ermmn,, p @stanford. edu
Abstract
Despite the empirical successes of self-supervised learning (SSL) methods, it is unclear what characteristics of their representations lead to high downstream accuracies. In this work, characterize properties that SSL representations should ideally satisfy. Specifically, we prove necessary and sufficient conditions such that for any task invariant given data augmentations, desired probes (e.g., linear or MLP) trained on that representation attain perfect accuracy. These requirements lead unifying conceptual framework for improving existing SSL methods and deriving new ones. For contrastive learning, our framework prescribes simple but significant improvements to previous methods such as using asymmetric projection heads. For non-contrastive learning, we use our framework to derive a simple and novel objective. Our resulting SSL algorithms outperform baselines on standard benchmarks, including SwuA-muutis on linear probing of ImageNet.
Introduction
We study self-supervised learning (SSL), where the goal is to learn representations from minimal supervision, such that simple probes trained these representations achieve high downstream accuracy. Recently, there has been many different SSL methods achieving impressive empirical results (e.g. SimCLR [Л SwAV (2)) using preseevin augmentations (e.g. cropping or color jittering) as supervision. We dub this setting imariant SSL (ISSL). Despite these empirical successes, it remains unclear how these various SSL methods relate to another, how improve them, and how to derive new ones. Our goal is to provide a simple conceptual framework to think about those questions.
To derive such framework, we ask ourselves: what are the ideal requirements that ISSL representa- tions should aim to satisfy? We prove necessary and sufficient requirements to ensure that probes from specified family, e.g. linear multi-layer perceptron (MLP), perfectly classify any task that is invari- ant to desired data augmentations. This complements theoretical work in ISSL [B,) which analyze specific ISSL algorithms. Our work instead focuses on properties of representations that should serve as a goal for any ISSL algorithm. These ideal properties are: (i) desired predictors should able to distinguish positive and negative examples from the representation; (ii) the dimensionality of the rep- resentation should be sufficiently large; (iii) augmented inputs should map to the same representations.
Previous ISSL methods can be seen as approximations of our ideal requirements. Using our require- ments, we derive simple improvements to those approximations as well as new ISSL objectives. Our theory thus results in a unifying conceptual ISSL framework, with practical prescriptions including:
improvements existing methods, such as increasing the dimensionality of representations and using asymmetric projections heads, which lead to 5% point gains on Tiny-mageNet;;
a novel non-contrastive ISSL objective that outperforms all baselines, including SwAV+multicrops, by at least 1% point on linear classification of ImageNet;
extensions of ISSL. algorithms to learn representations that are better suited for non-linear probes.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

encoder
X O
2 Problem statement
x(X)
Z
2.1 Invariant Self-Supervised Learning
SSL learns an encoder & that maps an input I from a finite space X' (e.g,, 256 x 256 images) into a representation o(x) E R Given the encoder and dataset Di drawn from some task of interest Pt (X, Y). we fit a classifier f from desired family of probes F. Families of probes are sets of k-ary classifiers for any k 2 2 such as linear or MLP probes. For clar- ity, we consider linear probes F until SSec. 5]
linear probes JF Figure I: ISSL setting. (Top) 1D inputs, partitioned into 3 equivalence classes (shapes), are encoded by & into a 2D representation. (Bot. left) 3 ~ invariant tasks, where labels are the colors. (Bot. right) examples of probes for 2 of the invariant tasks.
invariant tasks T
Supervision for ISSL comes from unlabeled data px and label-pres augmentations. Augmenta- tions are ways of sampling "positive" æ, x examples that are equivalent for downstream classification tasks. We formalize this using an equivalence relation x x+ that partitions the inputs X' into equivalent classes [x] E X//,, and we consider the following downstream tasks T whose labelings deterministic and constant within these classes (we allow stochastic labeling in appendices).
Definition 1. The --iinariiant tasks T, is the set of all input-label distributions px Y) such that the labeling Pe (YIX) is deterministic and invariant to ~ i.e.,
for all Pt E T, I, xt xx: I x~xx
arg max arg max (y VEy
vEy
As an illustration, consider the 3 classes (triangle, square, and circle) shown in Fig. Then T consists of all tasks that are predictable from those shapes, e.g.. recognizing shapes with vertices (blue/orange in Fig. 1) or recognizing the shape (yellow/red/purplee Fig. Importantly, equivalence classes (here shapes) are different from and essentially refinements of downstream classes y (here colors). Note that equivalence relations can model arbitrary transformations including cropping and adding Gaus- sian noise, which contrasts with typical restrictions to augmentations defined by group actions DI
2.2 Idealized representations for ISSL
In this section, we define the optimal encoders, those that induce idealized representations that ISSL should be striving for. Although such encoders exist, they will likely not be learned in practice. Those idealized representations will nevertheless allow us to derive practical algorithms in Secc. 4] Note that our approach to defining ideal representations is to take into account how they will be used downstream, and thus depends on the desired family of probe F and potential invariant tasks 'T
The goal of ISSL is to learn representations from which (typically simple) probes f E F classify well downstream tasks Pt E T, i.e., they achieve low 0-1 risk (2 f) == (E,,( * f()(X)))]]. Ideally, for any task of interest Pt E T there will be a probe that can classify it perfectly.
An encoder o is population optimal for T,F. F, denoted as E $ pay. iff predictors realize the Bayes eтror on any invariant task, i..., for all Pe E T we have in Re( f) = 0.
Definition 2.
Population optimality ensures the existence of perfect downstream probes, which would be learned with infinite downstream data. In practice, however, predictors will be trained from finite datasets D, of possibly small size n with empirical risk minimization. When n is small a fitted probe (ERM) ff E F(D.. == arg minjer fer - 1 & f()(2))) could be terrible population predictor even when the underlying encoder is population optimal. Ideally, representations would thus also guarantee that any ERM performs as well possible for any desired task and dataset size n. This suggests minimizing the following worst-case expected risk over tasks and ERMs.
W (o, == sup E. E,
sup FEF(D..))
Re(
EET
Definition 3. An encoder d' is sample optimal for T, if is population optimal and minimizes the worst-case expected risk of ERMs for arbitrary sample sizes, i.e.,
for all n 2 1:
Φ E arg min W,
de pop

---

2
not prodictable
prodictable
(e) linearly prodactuble
(d)
pred.
(e) Popuiation optimal
Figure 2: Representations are population optimal for linear F iff their dimensionality is sufficiently
large and equivalence classes M (X) are linearly classifiable. The first 2 figures show representations from which (XX) is (a) never or (b) only non-linearly classifiable. Although (c) ensures linear classification of M (X), there exist invariant tasks, e.g. (d), that are not classifiable linearly, (e) Linear classifiability of (X) ensures population optimality iff the dimensionality is at least | X//~ //| -1
Theoretical framework for linear probes F
3.1 Characterizing optimal encoders for linear ISSL
In this section, we characterize all samplc-optimal encoders Def. 3). with simple properties that give insights into the form of the idealized representation. The key for theory is that any ~~iinvarian function g can be written as composition between some function Cy and maximal invariant i.e., 9 Cg M where M X {l,..., X//1} indexes the equivalence class:
for any x, x+ X: x x~* - M(x) = (())=
(4)
To build intuition for the final characterization, let us first discuss population optimal encoders (De. 2) for unconstrained probes, then linear probes, and finally sample optimality (Def. 3).
Unconstrained probes. By Det. 1 labels of downstream tasks pt are ---invariant. Labels can thus be written some function of M, i.e., arg max, Pt (y) X) = ct (M(X)). This shows that M(X) contains all and only information about desired tasks T. If probes are unconstrained, an encoder population optimal iff (X) predictable/classifabbl
i.e., there exist an has such that M(X) hM (ø(X)). Indeed, this ensures that the probe defined by hM can classify the task pe-
Linear probes F. The problem with constrained probes is that they might not be able to the information about desired tasks. In particular, the previous probe might not be linear hM E FF. As an illustration, consider 4 equivalence classes: cats, dogs, oranges, and lemons. Fig. 2b shows representation from which .M (X) is predictable but invariant tasks are not linearly classifiable. In fact, even when M (X) is linearly predictable, i.e., hus E in Fig. 2c, downstream labels might not be, i.e., C has & F as shown in Fig. 2d By standard VC dimension arguments
[ 14! such binary task is linearly predictable the representation' 's dimensionality is one less than the number of equivalence classes | 1, as in Fig. 2c Building on this intuition we prove that population optimal encoders are essentiall those that induce d 2 /X/~|- dimensional representations from which M MXX is linearly predictable.
there exists bad ERMs
all ERMs good
Sample optimality. Although population optimal- ity ensures the existence of perfect linear probe, ERM probes trained on finite samples might still be bad due to generalization issues (Fig. left). Intuitively, one can remove such bad ERMs by mapping equivalent examples to the same repre- sentation, i.e.. by using invariant encoders. Indeed, this ensures that ERMs that correctly predict one example in an equivalence class also correctly predict all the other [ig.. 3 right). We prove that such invariance of population optimal encoders is necessary and sufficient for sample optimality.
train
non-invariant enc.
invariant enc.
Figure 3: Invariance of population-optimal en- coders is (a) necessary and (b) sufficient sure that there exists no had ERM.
'The difference with learning theory is that instead of (binary) shatterability of all examples, we want k-ary shatterability of all equivalence classes from representations. The key is that both notions coincide for specific probes (e.g. linear) and invariant encoders, which are necessary for sample optimality.

---

Putting all together gives the following necessary and sufficient properties of cumple-optineg encoders.
Theorem 1. An encoder @ is sample optimal for --invariant tasks T and linear F if and only if F-predictability of M: there exists max. invariant M and an f E F M(X) f( (X)): Invariance: o² is --iinvriint,, i.e., for any æ; r, E X we have x ~ x+ = (x) o- (x+);
Dimensionality: the effective dimensionality of the representations is at least one less than the number of equivalence classes, i.e., dim (span (z)[æ E 22)) 2 |2/~1-1
3.2 The impact of augmentations on downstream performance
Let us compute the worst-case excess risk W (0, F, T) of sample optimal encoders and show its dependence on the invariance structure. The key is that since sample optimal encoders are invariant [Theorem I). ERMs only need be trained on a single example per equivalence class to perfectly clas- sify all other examples from that class. The risk then depends on the proportion of equivalence classes seen when training the probe, which can be computed closed form as a function of the number of equivalence classes / and downstream samples n. For other similar results refer to Appx. B.3
Proposition 2. The worst expected risk of a sample optimal ø² for invinrrraant tasks T and any F is
Wn F, - (1 X//~
1
(5)
Prop. 2 shows that fewer equivalence classes, i.e., coarser re, leads better downstream sample efficiency. Of course, the convergence rate will be slower for practical encoders than for sample optimal ones. The result nevertheless suggests that good augmentations should be as strong as possible (induce coarser ~)) while being label-preserving. Examples of coarse augmentations are those from CLIP [5]. which map many images to similar sentences.
4 Practical ISSL objectives for linear probes F
The main remaining question is how to practically enforce requirements from Theorem In this section, we derive simple objectives that learn optimal encoders in ideal settings (infinite data, perfect optimizers, universal approximators). In the process, we shed light on why previously proposed ISSL methods work, and how to improve them in practice.
no
Our key insight is that we can learn sample-optimal encoders by jointly training encoder and a logistic regression to predict M(X) from the representations. Indeed, the resulting representations will be characterized by three properties, each of which implies a requirement from Theorem I #--predictability. invariance, effective dimensionality). First, the repre- sentations will allow linear predictability of M MX) due to the linearity of logistic regression. Second, the variance of same-class representations will be minimized due to Jensen's 's inequality. Finally, the effective dimensionality will be maximal. Indeed, logistic regression favors maximal angles between representations of different classes to increase the confidence of the predicted class. Specifically, the representations learned by this joint procedure form a simplex equiangular tight frame (sETF) illustrated in Fig. 4ndd discussed and we prove that those are optimal.
var.
Figure 4: sETF are idealized representa- tions that collapse same-class examples and maximize the an- gle across classes.
in the neural collapse literature 16
More formally, we prove in Prop. 3 that high dimension encoders trained to minimize the following multinomial logistic regression of (X), dubbed ~ISSL log loss, will be sample optimal,
log cxp(W(M(XX) ((()))(()))
C,(o:px) == inf Epx wew;
(6)
Ex/ (
where maps classes to weights, e.g., by indexing a weight matrix. Following previous work on neural collapse, we assume for this section that classes are equiprobable p. ([x) = 1/1x/=1, and that classifier's weights and representations are unit-normalized, i.e., w E W, := (I,..., 1.--11//111 + S - S where S denotes the (d- --shhrre (these assumptions can be relaxed e.g. We then have the desired relation between ISSL log loss and sample-optimal encoders.
and d E Φ
2 2

---

Proposition 3. Let Px be distribution with support X' and equiprobable equivalence classes Px (x]) 1/1x/11 Vr X. If Ifd | then any mottnnommllizdd encoder that minimizes the --ISSL. log loss x= arg mingminse 66:; C, Px ) is sample-optimal for i-iinvriiat tasks and linear F.
Prop. Slop..Jshe shows that the ISSL log loss is perfect pretext task in ideal settings. This suggests optimizing the ISSL log loss in practice and provides a formal relation between self-supervised and classical supervised learning. The challenge is that we typically neither have access to the maximal invariant (X) nor the number of equivalence classes />| required to compute the denominator of Bq. (6)
Instead, knowledge about the equivalence structure comes from data augmentations A A(X|X X) from which we can sample examples that are equivalent to the input X ~ X.
Having established our framework, we can re-interpret previous ISSL methods as practical approxima- tions of the ISSL log loss using data augmentations (e.g.. SimCLR, SwAV, DINO (2]. SimSiam (25)).
These approximations optimal encoders in idealized settings. By directly deriving ISSL methods from Eq. (6) we will
nevertheless suboptimal: none of them learn sample- (nor population-)
preseribe improvements to previous ISSL objectives that ensure that sample-optimal encoders
learned in idealized settings. We broadly categorize prior methods into two families depending on
whether they explicitly select the number of equivalence classes |X/~| if it is implicitly inferred
from augmentations. We call these approaches distillation and contrastive ISSL respectively. For derivations and Pytorch implementation see Appx.
4.1 Contrastive ISSL (CISSL)
softmax W
T
suftmax
Inspired by previous contrastive objectives III 26.28) we show how to optimize the ISSL log loss using data augmentations and negative sam- ples to remove the need of knowing M (X) and the number of classes ///- The resulting ob- jective, dubbed CISSL, corresponds to SimCLR using only a projection head 9 on one branch. See Fig. 5] This asymmetry is necessary to learn population optimal encoders for linear F.
project
W
project
g
g
represent
represent
4
augment
augment
A
A
A
A
CISSL bypasses the need for M (XX by noticing that it only appears in the ISSL log loss through the class weights wi( (XM())). CISSL thus learns a function 9 mapping equivalent (augmented) inputs X to (X)). Such mapping exists since M is invariant, e.g., 9 w o M.
SimCLR
(b) CISSL
Figure 5: CISSL corresponds to SimCLR with a single (asymmetric) projection head g This ensures linear predictability of downstream tasks, which will be computed by W, Tz.
When augmentations satisfy the Markov Chain X ((X) - X, we show that we can replace the class weights w( [M (X)) in the ISSL loss by g( g(X), where is optimized over. Intuitively, this is because predicting X contains only information about M (X) due to the data processing inequality.
The only remaining challenge is computing the denominator of Eq. (6) without summing over the unknown classes X ///> To do so we use ranking conditional noise contrastive estimation (NCE; 29 B1). NCE replaces classification of equivalence classes by classification of positives in batch X X [X+,X ...... xx} where the positive X is sampled from the conditional A(X X)), while the negatives X; come from the marginal A A(X) = Epx [A(X]x)) Using Monte Carlo (MC) estimates with an unlabeled dataset DD
Ui Px we get our final empirical CISSL objective
exp exppg(X To(z))
L)( = inf Σ E () - log Exee exp 9X") ((x) gES* ZED
(7)
By Prop. and NCE's consistency [1], encoders trained with CISSL o" E arg migminsse se (o D)
are sample optimal for linear F in our ideal setting assumption (DD + co and unconstrained g) and when X - (X) - X forms Markov Chain. While consistency (and thus optimality) holds for k Z 1, more negatives improves statistical efficiency (1
Typically X, take value in the same space (e.g. images). If so, we can tie parameters by encoding X, i.c., we replace g by g' o where g' _d + S is called a projection head. The logits
5

---

inside of Eq. (7) are then computed by ('()(X)) SimCLR's objective o' (((X)) (((()))) shown in Fig. 5a The difference is that, by projecting the current representation, SimCLR learns encoders that are not even population optimal for linear F. In contrast, CISSL learns sample optimal encoders in ideal settings. Intuitively, this is because CISSL trains the representations in the same way as they will be used in downstream tasks Pt. Indeed, representations ((X) will be dotted with the downstream tasks' weights W, 6(x) compute logits. In ISSL, representations ((z)-rather than their projections g o'((x)) should thus be used in the inner product with ISSL weights wi wo(((X) g' (x(X)) ) to compute logits. CISSL thus derives, from first principles, an asymmetric of projection heads.
T o(x) as shown in Fig. 5b
This is very similar to
H[M Ellog q (M)
4.2 Distillation ISSL (DISSL)
In practice, CISSL requires contrasting many negatives. To avoid contrastive estimation, we can directly approximate M(X)-instead of the weight w( (XM()))sso that the
q {MM
denominator of Eg. (6) can be computed exactly, The resulting method, dubbed DISSL (Fig. 6p. is simpler and pnoretically-groundee version of non- controatraet losses (e.g. SWAV, DINO, SimSiam). The challenge and main difference between each of those methods is how they estimate M().
softmax (w(
A
1
Figure 6: DISSL. The teacher (top branch) trained with the top loss to ensure M is maximal invariant r.v. The student (bottom branch) distills the teacher by predicting M
conditional categorical distribution q(Ml X) to estimate (X) with random variable M. Replacing terms in the ISSL log loss then gives the following objective. Differences with Eq. (6) are in red.
As (() is discrete,
exp(w(m) ((x))
inf E pxpq(( xx [ 8,.- (M xx)
83. (m
x))
(8)
wEW;
m== (xp(w((m) ((x))
To highlight similarities with previous methods
3 we refer Eq. (8) as distilling the
teacher (M XX) into the student (M X). Importantly, Eq. (8) is exactly the ISSL log loss if
the teacher outputs a maximal invariant random variable, i.c., M = (X). By Prop. 3 distillation
thus learns sample-optimal encoders when the teacher takes at least C > | values and satisfies
the following requirements, which correspond to the definition of maximal invariance (Eq. (4)
Deterministic the teacher a deterministic distribution max (I.... C) {(m X)= 11; Invariant the teacher maps positives together x ~ x+ = a( M ()) = q(M x)); Maximal the teacher maps negatives separately x of x = q(M x) + q(M xx)).
Intuitively, these requirements ensure that the teacher clusters examples by equivalence classes, which will then be classified by the student. There are many ways of enforcing such requirements. In the following, we use information-thentt the teacher (online clustering) and student. Such quantities have the advantage being interpretable and computable in closed form for the categorical distributions given by our teacher and student.
quantities (entropies and KL. divergences) to jointly train
Determinism and Invariance. Both properties hold if and only if for any equivalent example the cross-entropy of the teacher's outputs is minimized Egth 1 log ( x = 0. Indeed,
x
zero cross-entropy simultancously minimizes the conditional entropy HII / x = 0 (equivalent to [+)]] (equivalent to invariance).
determinism) and the KL divergence [AM (x) ((g
Maximality. A natural way of enforcing maximality is train the teacher predict differently negatives x ل x- This requires accessing batches of negatives, which we wanted to avoid with DISSL. Instead, assume that we know (or have prior on) the true distribution of equivalence classes (XM). Then deterministic and invariant teacher is maximal if and only if the KL divergence between its marginal (λat)= = Ep [ and the true one is minimized DxL, (g(AT) (M O. We can thus avoid contrasting negatives using (a prior on) the distribution of equivalence classes.
Using a Lagrangian relaxation (with multipliers X, B) of the teacher's constraints with an MC estimate of the distillation loss (Eq. (8)) we get the following empirical DISSL loss (o(o; ==
inf A DRL ((A))) (XM((X)) 4,
E (1(())) |=)))(((()))))))) log (M X) + log s., (M x))
(9)
ZED
Maximality
Det. and Inv.
Distillation

---

In ideal settings (12) + oc, unconstrained known p()) and for X, - oo we show that encoders trained with DISSL are sample optimal for linear F and tasks that are invariant to the equivalences defined by the connected components of the augmentation graph [8] If the marginal is unknown, we follow the MaxEnt [3] and use uniform prior p( M (X) (1, C)) The KL in Eq. (9) then corresponds to maximizing entropy H..
Algorithm 1 Batched DISSI.
Require:
head g. weights W, enc. $. batched imputs X, aug. A, hyp. 8, X.
X + sample(A(X ()).2)
(MMIX) (
3: ((M]))+)))) softmax ( (g(
s(M x+*) softmax (W" x(X+)
5: ((M) = Maatchavg((g(M[])
As with CISSL, when X, X are in the same space, we
6: mxml Σn. ((m) log g(m)
tie parameters by encoding X before the teacher, i.e.,
7: det jtt_imy--a = Em ((m) X) log q(m|
g(M
((MIX)= softmax(4 [ó6 (x) for head g' Rd
dstl = E.. 4(m) ) log s(m
RC Algorithm 1 and Fig. Gillustrate DISSL with a uni-
return * mxmml 3 del inv dstl
form prior, and marginal q (M) estimated from batches.
DISSL is one of the many distillation methods that can be derived from our teacher's requirements.
These requirements generally lead to framework for deriving, comparing, and analyzing distillation objectives. In Appx. D we provide a taxonomy of 12 previous SSL methods from this perspective- none of which recover sample optimal encoders. Typically, previous methods favor: (i) determinism
by "sharpening" the teacher with a temperature parameter; (ii) invariance by making matching the teacher and student on equivalent inputs q( x=+) 8 (M x): (iii) maximality through optimization tricks (e.g. stop gradients or momentum encoder) to avoid a constant teacher -referred
to as "collapsing" 25 34 36 Note that avoiding constant collapse q( M xx) = q(M]
M ( for any
x E X' is insufficient, c.g., mapping half the inputs to a constant is also undesirable. Maximality formalizes the desired requirement: non-equivalent examples should not be mapped together.
5 ISSL for non-linear predictors F+
Linear probes F are standard for evaluating representations 27
38 However, if the goal is to 17
maximize performance it is natural to consider non-linear predictors F+. The question then becomes how should we learn optimal representations for any F+? In (Apxx B.5 we extend our framework to certain non-linear probes, such as neural networks, that separate into hidden component h and linear layer, i.e., f()) = WT h()). We informally summarize the theory and implications below.
Theory. There are two main differences between our characterization of optimal encoders for linear and non-linear probes. First, encoders should ensure predictability of (X) for the desired F+, Second, the dimensionality requirement decreases with the complexity of F+ e.g., for universal F+ it d 2 1. More generally, the necessary dimension and the sufficient dimension for optimality do not coincide and respectively depend the predictors' VC dimension
[ and memory capacity [39
Implications. Both theoretical differences lead direct implications for non-linear ISSL. First, we can decrease the dimensionality when performing ISSL for more complex non-linear probes. Second, we should use projection head that ensures the predictability of the maximal invariant with using the desired probes F+. Similarly to the linear case, we should match how the representation is used in the ISSL log loss and downstream tasks. We should thus apply the non-linear predictor asymmetric way. For CISSL we should thus compute the right hand side of Fig. 5 as y ( (()))))( ()))))) For DISSL, we should change the line 4 of Algorithm to s( (M x+ = softmax
a similar
)))
6 Summary of insights and relation to previous work
Let summarize our framework's 's main insights and their relation to previous work. Details in Appx. D
Dimensionality. Theorem I shows large representation's 's dimensionality is needed ensure probes can classify all invariant tasks (note: this is different from the projection's 's dimensionality analyzed in ). This suggests: (i) increasing the dimensionality of the representation; and (ii) ensuring that representations do not live in lower dimensional subspace. Although the first has surprisingly not been investigated in SSL, there have been recent empirical analyses about the second (4 42
Projection heads. Secs. 4 and 5 theoretically show how to choose projection heads, namely, one should be large possible while the other should have the architecture of downstream probes.
7

---

To our knowledge, we are the first to relate the architecture of the probing family and the projection head. Furthermore, our theory suggests why projection heads empirically improve performances in general SSL,, i.e., beyond avoiding collapsing in non-contrastive learning 25 36
1 2 4
Augmentations. Prop. 2 shows the benefit of using coarse label-pres augmentations, by proving the exact relation between optimal sample efficiency and the number of equivalence classes. This gives a new theoretical perspective on the use of augmentations that remove lot of information of the input, which have been suggested to be useful for many different reasons 12 11:4
DISSL. In Sec. 4 we derive DISSL to learn optimal encoders in ideal settings, contrary to prior work. DISSL follows recent methods 49 51, in particular SwAV and DINO, that learn representations by jointly predicting and learning clusters of examples. DISSL/DINO/SWAN each distill categorical teacher but differ in how they enforce its maximality. DINO does it implicitly through optimization tricks, e.g., exponentially moving averages and stop-gradients. SwAV explicitly enforces maximality by equiprobably clustering a queue of examples using Sinkhorn's 's algorithm [52]. DISSL is also ex- plicit but uses more efficient max entropy regularization (no ceceuessto-gradienniiie
algorithm). Furthermore, DISSL's student uses a linear projection head to ensure good linear probing (Scc. 4.1p
Theoretical SSL. Theorem characterizes optimal encoders for ISSL. This contrasts with standard theoretical work in SSL that typically analyze specific SSL algorithms [ 5
6
R [3
55 and or
focus upper-bounding downstream performance [4. The advantage of our theory is that it provides a simple unifying framework from which we can derive a variety of SSL methods and actionable insights. The downside is that by distancing itself from specific algorithms, the framework does not provide guarantees outside of ideal settings. We thus see our theory as complementary to prior work.
7 Experiments
The experiments in the main paper focus on evaluating our frameworks' prescriptive implications. For experimental details see Appx. Fland our aurGGitHub repository
For more results see Appx. G
In summary, our experimental results show that: (i) CISSI/DISSL. outperform their respective baselines on standard benchmarks as suggested by Sec. 4 (ii) increasing dimensionality improves
downstream probing as suggested by Theorem (iii) coarser augmentations improve sample effi-
ciency as in Prop. 2 (iv) smaller ISSL log loss improves downstream performance suggested by
Prop 3 (v) projection heads should be related to probing family as discussed in Secs. 4|d 5
TinyImageNet [56), 300 pretraining epochs, and ResNet18s. Note that for ResNet 8s the dimensionality of the representation (res5avg) is d = 512. For contrastive baselines
For the first experiments,
SimCLR. For distilling baselines we use the best over DINO, SwAV, SimSiam.
We use standard TinylmageNet augmentations (34 (color jittering, grayscaling, cropping) with a parameter controlling the probability and strength of augmentations study the effect of coarsening.
CISSL/DISSL improve linear probing
Table 1:
Our prescriptive implications im- proves ISSL. for linear probes on Tinylma- geNet with ResNet18 encoders. 3 seeds.
Table I shows that each of our prescriptions sig-
nificantly improve distillation and contrastive ISSL. "Ours" vs "Base" shows that removing one non-linear projection head (as in Fig. 5) gives a 1% gain in con- trastive learning, while our new distillation objective achieves 2% gains compared to the best distillation baseline. "dim. 13d shows that increasing the dimen- sionality of representation 512 - 2048 further im- proves linear probing by 2%. "Epochs 1" and "coarse aug." show that training for longer (300 + 1000 epochs) ) and using coarser augmentations both fur- ther improve performance by 1-2%. Altogether our framework's 's insights significantly improve linear probing accuracy: 6% gains for contrastive learning and 7% for distillation.
CONTR.
DISTIL.
BASE (SIMCLR (DINO)
44.9 #0.2
43.5 #0.2
OURS (CISSL (DISSL)
45.8 10.0
45.5 10.1
+ DIM. 1
47.6 10.1
47.9 10.1
EPOCHS t
48.7 10.1
49.2 #0.1
COARSE AUG.
51.0 10.1
50.6 40.2
Coarse augmentations improve sample efficiency. Prop. 2 suggests that coarser prebervieg augmentations improve downstream sample efficiency. We test that by training four DISSL encoders with augmentations of varying strengths (25%,, 50%, 100%, 200%) relative to standard augmenta- tions) and evaluating them at different downstream samples sizes. As suggested by the theory. Fig. 7a shows that stronger label- aabel-preeeriin augmentations improve sample efficiency.
8

---

0.40
46-
500 U
1000
Standard d=512
veryling hyperameters
0.48
0.35
Accuracy
0.30
Augmentations
0.5
Accuracy
44
Accuracy
0.46
0.25
42
0.20
100
0.44
40
0.15
0.25
0.10
38
50 spoons
0.42
Linear
0.05
36
0.40
MLP
10a
10
10
0.95
0.90
0.85
2
2
21z
# Downstream Samples
Test ISSL Loss
Dimension
(a) Augmentations
(b) ISSL log loss
(c) Dimensionality
As suggested by theory: (a) coarsening augmentations improves sample efficiency; (b) decreasing ISSL log loss improves representations, which can be achieved by longer training; and (c) increasing the representation's dimensionality improves performance for linear , but less so for MLPs F+. Y-axis is TinylmageNet probing performance. Each point is obtained by sweeping: (a) augmentation strengths for DISSL and downstream sample sizes; (b) CISSL's optimization hyperparameters including epochs; and (c) the dimensionality of CISSL's representations.
Figure 7:
ISSL. log loss correlates with performance. Previous work 57 suggested contrastive losses may not predict probing performance. On the contrary, crotra shows that minimal ISSL log loss implies the optimality of encoders if is large. This suggests that, for fixed augmentations, ISSL log loss is highly related to performance. To test this relation, we trained 80 CISSL models with various hyper- parameters, while fixing augmentations and negatives k. Fig. shows that the test ISSL loss indeed correlates with probing accuracy (gray points). Appx. G.oshows similar results for the train ISSL loss.
Longer training decreases ISSL log loss. An efficient way of decreasing ISSL log loss is longer training (blue points in Fig. 7b only vary the number ISSL epochs). Prop. 3 thus provides an explanation of the well-known performance gains of longer ISSL training 58 Namely, longer training decreases ISSL log loss, which results in representations that are closer to optimality.
Increasing dimensionality improves performance. Theorem shows that linear ISSL requires dimensionality of d = | -1 to ensure predictability of all invariant tasks. In practice, the number of equivalence classes is most likely very large. Although such dimensionality is impractical, it does suggest increasing the dimensionality beyond the d = 512 of ResNet188. To test this, we train CISSL with a larger dimensionality by increasing the output channels before the average pooling layer. To keep the number of parameters comparable, we use bottlenecks or low-rank linear layers before and after the representations layer as detailed in Appx. F Fig. 7c shows that increasing the dimensionality has significant effect on downstream performance for linear F. (blue).
Previous results concern linear F which are standard for ISSL evaluation. In practice, one would likely use more complex probes F+ to improve results. In See. 5 we discussed how to perform ISSL for F+,. In the following, we evaluate ISSL for MLPs F+ with two hidden layers of 2048 units.
Performing ISSL for MIPs Ft. Table shows that MLP probes ("F EVAL: MLP") outperforms lin- ear ones ("Fevu:: lin.") even in few-shot regimes (10 shot). Furthermore, when predicting with MLP probes it is desirable to train the ISSL encoders for MLPs (*F MLP"" instead of linear probes (row 4 vs 3). As discussed in Secc 3] the only difference between DISSL for different probes is that the stu- dent's representation is projected using a head with the same architecture as downstream probes.
Table 2: MLP probes outperform linear ones on TinyImageNe when using MLP ISSL.
Fism
F
ALL
SHOT
DINO
MLP
44.7
22.0 40.2
DISSL
LIN.
LIN.
45.9 10.0
25.3 40.0
LIN.
MLP
46.4 #0.1
25.6 40.0
MLP
47.5 +0.2
26.1 #0.1
Dimensionality affects less MLPs F+, In Sec. we saw that the optimal dimensionality d decreases for more complex predictors F-. Fig. 7c indeed shows that larger dimensions result in smaller gains when the training and evaluation probe are MLPs Fi (orange) compared to linear ones F (blue).
Given encouraging TinyImageNet results, we investigated whether our objectives can be used as replacement for standard objectives on ImageNet [59]. We specifically replaced SimCLR with CISSI and SWAV with DISSL in VISSL's 's codebase 60 without modifying hyperparameters.

---

Table Our models outperform baselines on ImageNet. All models use ResNet50, 100 epochs. 2560 batch size. For our models, we incraase the dimensionality of the representations (2048 + 8192).
SIMCLR
SWAV
BARLOW T. CISSL
DISSL
65.1
64.6
66.1
67.7
68.9
Our models outperform baselines on ImageNet. Table 3 shows that both CISSL and our novel DISSL objective significantly outperform all considered baselines, including SwAV by a 4%, when using standard augmentations. For CISSL we found (contrary to Table T) that gains compared to SimCLR were mostly due to increasing the dimensionality of the representation.
Given encouraging results on standard augmentations, we compared the performance of DISSL with near SOTA model: SwAV trained with their special multi-crop augmentations.
DISSL competitive with SOTA models at scale. Table shows that DISSI outperforms SwAV. Combined with Table 3 this suggests that DISSL works well in different settings. This is encouraging given the lack of tuning and the simplicity of DISSL's out-of-the-box objective. In contrast, SwAV requires stopping gradients, storing a queue, rumning Sinkhorn's 's algorithm, and freezing certain parameters during initial training steps.
Table 4: Our DISSL outperforms SwAV using 2 x 160 4 x 96 multi-crops on ImageNet. 2560 batch size, ResNet50.
100 EPOCHS
EPOCHS
SWAV DISSL
69.5
73.5
70.7
74.0
Table 5: DISSL is competitive transfer tasks. Same models as in Table 4 evallaaed by linear probes.
FOOD
CIFARI0
CIFARI00
CARS
AIRCRAFTS
DTD
PETS
CALTECH
FLOWERS
SWAV DISSL
75.5
92.0
76.2
58.2
49.1
72.6
86.9
92.0
94.7
77.9
93.6
77.6
62.2
48.1
73.9
88.0
91.5
95.3
DISSL is competitive on transfer. Table 5 shows that DISSL generally outperforms SwAV on the standard transfer benchmarks from 61 even though our theory does not discuss transfer.
8 Summary and Outlook
We presented a simple conceptual framework to understand, compare and improve ISSL methods. Inspired by recent work optimal representations for supervised [22 and robust 63 learning, derived such a framework by studying aggorithmic-agnostie goals for ISSL. In particular, Theorem ] provides the minimal and sufficient requirements for optimal encoders. On the algorithmic Lide|Sec. 4 uses our framework to derive simpler and theoretically-mottie motivvtte variants of prior SSL objectives. Al- together framework provides actionable insights for ISSL such how choose: SSL algorithms, the dimensionality of the representations, projection heads, and augmentations. On the empirical side, |Sec. shows that prescriptions leads significant gains on linear probing benchmarks.
There are many limitations that should be addressed for a more realistic prescriptive framework for ISSL. See Appx. El for more details. First, our theory is binary, e.g., augmentations are either label preserving or not, and encoders are optimal or not. Although our framework likely captures consider unconstrained encoders
the right intuition, nuance would be more realistic. Second, o, dimensionality, and infinite unlabeled data. As a result, our framework cannot currently improve the computational data efficiency of the pretraining phase. Finally, consider all invariant tasks T even though only a subset of those are meaningful. Despite those limitations, we showed that framework's insights lead to substantial improvements in ISSL. performance.
Acknowledgments and Disclosure of Funding
We thank Ananya Kumar, Shengjia Zhao, Mo Tiwari, Michael Xie, Niladri Chatterji, Shibani Santurkar, Jiaming Song, Ali Malik, Colin Wei, Yangjun Ruan and Chris Maddison for helpful feedback. YD supported by a Knights-Hennessy Scholarship. The work is partially supported by an Open Philanthropy Project Award, Sloan Fellowship. and ARO (W91INF-2111-0025
10

---

References
[1] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton, "A simple framework for contrastive learning of visual representations." " in International Conference on Machine Learning (ICMI., 2020. (Cited on
g
9
45 49
[2] M. Caron, I. Misra, J. Mairal, P. Goyal, P. Bojanowski, and A. Joulin, "Unsupervised learning
of visual features by contrasting cluster assignments. in Advances in Neural Information Processing Systems (NeurIPS), 2020. (Cited on
45)
[3] N. Saunshi, O. Plevrakis, S. Arora, M. Khodak, and H. Khandeparkar, "A theoretical analysis of contrastive unsupervised representation learning." " in International Conference on Machine Learning (ICML), 2019. (Cited on
[4] Y. Bansal, G. Kaplun, and B. Barak, "For self supervisd learning, rationality implies general- ization, provably," in International Conference on Learning Representations (ICLR), 2021. (Cited on
[5] D. Lee, Q. Lei, N. Saunshi, and J. Zhuo, "Predicting what you already know helps: Provable self-supervised learning," " in Advances in Neural Information Processing Systems (NeurIPS), 2021. (Cited on
[6] C. Tosh, A. Krishnamurthy, and D. Hsu, "Contrastive learning, multi-view redundancy, and linear models," in Conference on Algorithmic Learning Theory (ALT),, 2021. (Cited on g 42
[7] Z. Wen and Y. Li, "Toward understanding the feature learning process of self-supervised contrastive learning," in International Conference on Machine Learning (ICML), 2021. (Cited on
45)
[8] J. Z. HaoChen, C. Wei, A. Gaidon, and T. Ma, "Provable guarantees for self-supervised deep learning with spectral contrastive loss," in Advances in Neural Information Processing Systems (NeurIPS), 2021. (Cited on I 7
g 39 43
[9] T. Leen, "From data distributions to regularization in invariant learning," in Advances in Neural Information Processing Systems (NeurIPS), 1994. (Cited on 2
[10] S. Chen, E. Dobriban, and J. H. Lee, "A group-theoretic framework for data augmentation." in Advances in Neural Information Processing Systems (NeurIPS), 2020. (Cited on 43
[1]] C. Lyle, M. van der Wilk, M. Kwiatkowska, Y. Gal, and B. Bloem-Reddy, "On the benefits of invariance in neural networks," aariiv preprini arXiv:2005.001 70,78 2020. (Cited on
[12] Y. Dubois, B. Bloem-Reddy, K. Ullrich, and C. J. Maddison, "Lossy compression for lossless prediction," Advances in Neural Information Processing Systems (NeurIPS), 2021. (Cited on
21 22
25
37
45
[13] V. N. Vapnik and A. Y. Chervonenkis, "On uniform convergence of the frequencies of events to their probabilities." " Teoriya Veroyatnostei i ee Primeneniya, vol. 16, no. 2, pp. 264-279,
1971. (Cited on 7 32
[14] C. C. Burges, "A tutorial on support vector machines for pattern recognition." Data mining and knowledge discovery, vol. 2, no. 2, pp. 121-167, 1998. (Cited on 25 32
[15] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Saastr, A. Askell,
P. Mishkin, J. Clark, G. Krueger, and I. Sutskever, "Learning transferable visual models from natural language supervision," in International Conference on Machine Learning (ICML), 2021. (Cited on
43
[16] V. Papyan, X. Y. Han, and D. L. Donoho, "Prevalence of neural collapse during the terminal phase of deep learning training," Proceedings of the National Academy of Sciences, vol. 117, pp. 652 - 24 663, 2020. (Cited on
[17] T. Ergen and M. Pilanci, "Revealing the structure of deep neural networks via convex duality," in International Conference on Muchine Learning (ICML), 2021.
[18] J. Lu and S. Steinerberger, "Neural collapse under cross-entropy loss," Applied and Compula- tional Harmonic Analysis, vol. 59, pp. 221- 2022. (Cited on
[19] F. Graf, C. Hofer, M. Niethammer, and R. Kwitt, "Dissecting supervised contrastive learning." " in International Conference Machine Learning (ICML), 2021.
11

---

[20] J. Zarka, F. Guth, and S. Mallat, "'Searrttoon and concentration in deep networks," in Interna- tional Conference on Learning Representations (ICLR). 2021.
[21] W. E and S. Wojtowytsch, "On the emergence of simplex symmetry in the final and penulti- mate layers of neural network classifiers, in Mathematical and Scientific Machine Learning Conference (MSML), 2021. (Cited on
[22] Z. Zhu, T. Ding. J. Zhou, X. Li, C. You, J. Sulam, and Q. Qu, "A geometric analysis of neural collapse with unconstrained features," Advances in Neural Information Processing Systems (NeurIPS), 2021. (Cited on
43
[23] W. Ji, Y. Lu, Y. Zhang, Z. Deng, and J. Su, "An unconstrained layer-peeled perspective on neural collapse." " in International Conference on Learning Representations (ICLR), 2022. (Cited
[24] M. Caron, H. Touvron, Misra, H. J'egou, J. Mairal, P. Bojanowski, and A. Joulin, "Emerging properties in self-supe vision transformers," in International Conference on Computer Vision (ICCV), 2021. (Cited on 5
[25] X. Chen and K. He, "Exploring simple siamese representation learning," " in Conference on Computer Vision and Pattern Recognition (CVPR), 2021. (Cited on S
45
[26] A. Mnih and K. Kavukcuoglu, "Learning word embeddings efficiently with noise-contrastive estimation," in Advances in Neural Information Processing Systems (NeurIPS), 2013. (Cited
on 5
[27] A. van den Oord, Li, and O. Vinyals, "Representation learning with contrastive predictive coding," arXiv preprini arXiv:21 2019. (Cited on
45
[28] I. Misra and I.. van der Maaten, "Self-supervised learning of pretext-invariant representations," in Conference on Computer Vision and Pattern Recognition (CVPR), 2020. (Cited on 5
[29] M. Gutmann and A. Hyvärinen, Moosse-cottasstvve estimation: A new estimation principle for unnormalized statistical models," in Artificial Intelligence and Statistics (AISTATS), 2010. (Cited on
37
[30] R. Jozefowicz, O. Vinyals. M. Schuster, N. Shazeer, and Y. Wu, "Exploring the limits of language modeling," arXiv preprint arXiv:1602.022100, 2016. (Cited on 37
[31] Z. Ma and M. Collins, "Noise contrastive estimation and negative sampling for conditional models: Consistency and statistical efficiency," in Empirical Methods in Natural Language Processing, 2018. (Cited on 5 37
[32] Z. Fang, J. Wang, L. Wang. L. Zhang, Y. Yang, and Z. Liu, "SEED: Self-supervised distillation for visual representation, in International Conference on Learning Representations (ICLR), 2021. (Cited on 6
[33] E. T. Jaynes, "Information theory and statistical mechanics," Physical Review, vol. 106, no. pp. 220-630, 1957. (Cited on
[34] A. Ermolov, A. Siarohin, E. Sangineto, and N. Sebe, "Whitening for self-supervised represen-
tation learning," " in International Conference on Machine Learning (ICML), 2021. (Cited on 7
8 44 45 48
[35] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick, "Momentum contrast for unsupervised visual representation learning," in Conference on Computer Vision and Pattern Recognition (CVPR), 2020. (Cited on 44p
[36] B. Grill, F. Strub, F. Altché, C. Tallec, P. H. Richemond, E. Buchatskaya, C. Doersch, B. A. Pires, Z. Guo, M. G. Azar, B. Piot, K. Kavukcuoglu. R. Munos, and M. Valko, "Bootstrap Your Own Latent- a new approach to self-supervised learning." in Advances in Neural Information Processing Systems (NeurIPS), 2020. (Cited on g
45
[37] Y. Bengio, A. C. Courville, and P. Vincent, "Representation learning: A review and new perspectives," " IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 8, pp. 1798-18822 1828, 2013. (Cited on 0
[38] Zhang, Isola, and A. A. Efros, "Colorful image colorization," " in European Conference on Computer Vision (ECCV), 2016. (Cited on B
12

---

[39] T. M. Cover, "Geometrical and statistical properties of systems of linear inequalities with applications pattern recognition." IEEE Transactions on Electronic Computers, vol. EC-14, no. 3, pp. 326-334, Jun. 1965. (Cited on 7
350
[40] J. Zbontar, L. Jing. I. Misra, Y. LeCun, and S. Deny, "Barlow Twins: Self-supervised learning via redundancy reduction," in International Conference on Machine Learning (ICMI., 2021. (Cited on
44
[41] T. Hua, W. Wang, Z. Xue, S. Ren, Y. Wang, and H. Zhao, "On feature decorrelation in self- supervised learning," in International Conference Computer Vision (ICCV), 2021. (Cited on
[42] I.. Jing, Vincent, Y. LeCun, and Y. Tian, "Understanding dimensional collapse in contrastive self superviid learning," in International Conference on Learning Representations (ICLR), 2022. (Cited on
[43] T. Chen, C. Luo, and I.. Li, "Intriguing properties of contrastive losses," " in Advances in Neural Information Processing Systems (NeurIPS), 2021. (Cited on 43
[44] Y. H. Tsai, Y. Wu, R. R. Salakhutdinov, and Morency, "Self-supervised learning from a multi-vien perspective." in International Conference Learning Representations (ICLR), 2021. (Cited on
45
[45] Y. Tian, C. Sun, Poole, D. Krishnan, C. Schmid, and Isola, "What makes for good views for contrastive learning?" in Advances in Neural Information Processing Systems (NeurIPS), 2020.
[46] M. Federici, Dutta, P. Forré, N. Kushman, and Z. Akata, "Learning robust representations via multi-view information bottleneck," in International Conference on Learning Representations (ICLR), 2020. (Cited on 45
[47] J. Mitrovic, B. McWilliams, J. Walker, L. Buesing, and C. Blundell, "Representation learning via invariant causal mechanisms," in International Conference on Learning Representations (ICLR), 2021. (Cited on 43
[48] M. Wu, C. Zhuang, M. Mosse, D. L. K. Yamins, and N. D. Goodman, "On mutual information in contrastive learning for visual representations," arXiv preprint arXiv:2005. 2021. (Cited on
[49] M. Caron, P. Bojannowki,, A. Joulin, and M. Douze, "Deep clustering for unsupervised learning of visual features," in European Conference on Computer Vision (ECCV), 2018. (Cited on S
[50] Y. M. Asano, C. Rupprecct, and A. Vedaldi, "Self-labelling via simultaneous clustering and representation learning." in International Conference Learning Representations (ICLR), 2020. (Cited on 43
[51] J. Yang, D. Parikh, and D. Batra, "Joint unsupervised learning of deep representations and image clusters," in Conference Computer Vision and Pattern Recognition (CVPR), 2016.
(Cited on [
[52] R. Sinkhorn and Knopp, "Concerning nonnegative matrices and doubly stochastic matrices." Pacific Journal of Mathematics, vol. 21, no. 2, pp. 343-348, 1967. (Cited on R
[53] C. Tosh, A. Krishnamurthy, and D. Hsu, "Contrastive estimation reveals topic posterior information to linear models," Journal of Machine Learning Research (JMLR), vol. 22, pp. 281:1-281:31, 2021. (Cited on
[54] K. Nozawa and I. Sato, "Understanding negative samples in instance discriminative self- supervised representation learning." in Advances in Neural Information Processing Systems (NeurIPS), 2021. (Cited on 42
[55] Y. Tian, X. Chen, and S. Ganguli, "Understanding supervuee learning dynamics without contrastive pairs," in International Conference on Machine Learning (ICML), 2021. (Cited on
g
43 45)
[56]
cn231n, "Tinyimagenet," 2015. (Cited
47
[57]
N. Saunshi, J. T. Ash, S. Goel, D. Misra, C. Zhangg S. Arora, S. M. Kakade, and A. Krish- namurthy, "Understanding contrastive learning requires incorporating inductive biases," in International Conference on Machine Learning (ICML), 2022. (Cited on 42
13

---

[58] Z. Wu, Y. Xiong, S. X. Yu, and D. Lin, "Unsupervised feature learning via non- parametric instance discrimination," in Conference on Computer Vision and Pattern Recognition (CVPR), 2018. (Cited on
[59] J. Deng, W. Dong, R. Socher, I.. Li, K. Li, and Fei-Fei, "Imagenet: A large-scale hierarchical image database," " in Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
(Cited on 2 47
[60] P. Goyal, Q. Duval, J. Reizenstein, M. Leavitt, M. Xu, B. Lefaudeux, M. Singh, V. Reis,
M. Caron, P. Bojanowski, A. Joulin, and Misra, "VISSL," " 2021. (Cited on 48
[61] S. Kornblith, T. Chen, H. Lee, and M. Norouzi, "Why do better loss functions lead to less transferable features?" in Advances in Neural Information Processing Systems (NeurIPS), 2021. (Cited on
[62] Y. Dubois, D. Kiela, J. Schwab, and R. Vedantam, "Learning optimal representations with the decodable information bottleneck," in Advances in Neural Information Processing Systems (NeurIPS), 2020. (Cited on 10
45
[63] Y. Ruan, Y. Dubois, and C. J. Maddison, "Optimal representations for covariate shift," in International Conference on Learning Representations (ICLR). 2022. (Cited on I0 42
[64] M. L. Eaton, "Group invariance applications in statistics," " Regional Conference Series in Probability and Statistics, vol. 1, pp. i-133, 1989. (Cited on 22
[65] E. L.. Lehmann and J. P. Romano, Testing Statistical Hypotheses, Third Edition, 3rd ed., ser. Springer texts in statistics. Springer, 2008. (Cited on 22)
[66] C. Zalinescu, Convex Analysis in General Vector Spaces.
World Scientific, 2002. (Cited on
25
[67] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004.
[68] L. Narici and E. Beckenstein, Topological Vector Spaces, 2nd ed. Chapman and Hall/CRC,
2010. (Cited on (5)
[69] A. Brøndsted, An introduction to convex polytopes.
Springer Science & Business Media,
1983, no. 90. (Cited on 29
[70] G. M. Ziegler, Lectures on polytopes. Springer Science & Business Media, 2012, vol. 152.
[71] Grünbaum, V. Klee, M. A. Perles, and G. C. Shephard, Convex polytopes. Springer, 1967, vol. 16. (Cited on 29
[72] S. Straszewicz, "Over exposed points of closed point sets." Fundamenta Mathematicae, vol. 24, pp. 139-143, 1935. (Cited on 30
[73] T. Rockafellar, Convex analywis. Princeton university press, 1970. (Cited on
[74] S. Shalev-Shwartz and T. Zhang, "Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization," Mathematical Programming, pp. 1-41, 2014. (Cited on
[75] S. Dutta and A. Goswami, "Mode estimation for discrete distributions," Mathematical Methods of Statistics, vol. 19, no. 4, pp. 374-384, 2010. (Cited on 33
[76] P. Flajolet, D. Gardy, and L.. Thimonier, "Birthday paradox, coupon collectors, caching algorithms and self-organizing search," Discrete Applied Mathematics, vol. 39, no. 3, pp. 207-229, 1992. (Cited on 33
[77] P. Berenbrink and T. Sauerwald, "The weighted coupon collector's problem and applications." "
in International Computing and Combinatorics Conference (COCOON), 2009. (Cited on 33
[78] W. Feller, An introduction to probability theory and its applications. 2008. (Cited on 33
John Wiley & Sons,
[79] B. O'Neill, "The classical occupancy distribution: Computation and approximation," The American Statistician, vol. 75, no. 4, pp. 364-375, 2021. (Cited on 33
[80] C. Fang, H. He, Q. Long, and W. J. Su, "Exploring deep neural networks via layer-peeled model: Minority collapse in imbalanced training," Proceedings of the National Academy of Sciences, vol. 118, 2021. (Cited on 34 42
14

---

[81] D. J. C. MacKay, Information theory, inference, and learning algorithms. University Press, 2003. (Cited on 35
Cambridge
[82] Kowalezyk, "Dense shattering and teaching dimensions for differentiable families (extended
abstract))" in Conference on Learning Theory (COLT), 1997. (Cited on 35 36
[83] E. D. Sontag, "Remarks on interpolation and recognition using neural nets," in Advances in Neural Information Processing Systems (NeurIPS), 1990. (Cited on 35)
[84]
"Shattering all sets of k points in general position' requires (k - 1)/2 parameters," " Neural
Computation, vol. 9, no. 2. pp. 337-348, 1997. (Cited on 35 36
[85] E. B. Baum, "On the capabilities of multilayer perceptrons," Journal of Complexity, vol. 4, no. 3. pp. 193-215, 1988.
[86] A. Sakurai, "n-h-1 networks store no less n*h+1 examples, but sometimes no more," in International Joint Conference on Neural Networks (IJCNN, vol. 3, 1992.
[87] G. J. Mitchison and R. M. Durbin, "Bounds on the learning capacity of some multi-layer networks," Biological Cyberneties, vol. 60, no. 5, pp. 345-365, 1989. (Cited on 35
[88] T. M. Cover, "Capacity problems for linear machines," " Pattern recognition, pp. 283 289, 1968. (Cited on 35| 36)
[89] P. L.. Bartlett, N. Harvey, C. Liaw, and A. Mehrabian, "Nearly-tight ve-dimension and pseu- dodimension bounds for piecewise linear neural networks," JMLR, vol. 20, pp. 1::17, 2019. (Cited on 36
[90] S. Shalev-Shwartz and S. Ben-David, Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. (Cited on 36
[91] A. Kowalczyk, "Estimates of storage capacity of multilayer perceptron with threshold logic hidden units," " Neural Networks, vol. 10, no. 8, pp. 1417-1433, 1997. (Cited on 36))
[92] C. Yun, S. Sra, and A. Jadbabaie, "Small relu networks are powerful memorizers: a tight analysis of memorization capacity," in Advances in Neural Information Processing Systems (NeurIPS), 2019.
[93] P. Baldi and R. Vershynin, "The capacity of feedforward neural networks," " Neural Networks, vol. 116, pp. 288-311, 2019. (Cited 36
[94] Xu and M. Raginsky, "Minimum excess risk in bayesian learning," " IEEE Transactions on Information Theory, 2022. (Cited on 57
[95] O. Kallenberg, Foundations of modern probability. Springer, 1997. (Cited on 37
[96] H. Bao, Y. Nagano, and K. Nozawa, "Sharp learning bounds for contrastive unsupervised representation learning," arXiv preprint arXiv:2 10.022010.0 2021. (Cited on
[97] K. Nozawa, P. Germain, and Guedj, "Pac-bayesian contrastive unsupervised representation learning." in Conference on Uncertainty in Artificial Intelligence (UAI), 2020.
[98] J. T. Ash, S. Goel, A. Krishnamurthy, and D. Misra, "Investigating the role of negatives in contrastive representation learning," " in Artificial Intelligence and Statistics (AISTATS), 2022.
[99] P. Awasthi, N. Dikkala, and P. Kamath, "Do more negative samples necessarily hurt in contrastive learning"" in International Conference on Machine Learning (ICML), 2022. (Cited
on
[100] Y. Wang, Y. Zhang, Y. Wang, J. Yang, and Z. Lin, "Chaos is a ladder: A new theoretical understanding of contrastive learning via augmentation overlap," in International Conference on Learning Representations (ICLR), 2022. (Cited on 42)
[101] Y. Tian, L. Yu, X. Chen, and S. Ganguli. "Understanding sulf-supervised learning with dual deep networks," " arXiv preprint mrXiv:2010.00576 2021. (Cited on 42 45
[102] D. G. Mixon, H. Parshall, and J. Pi, "Neural collapse with unconstrained features," Sampling Theory, Signal Processing, and Data Analysis, vol. 20, no. 2, pp. 1-13, 2022. (Cited on 22
[103] T. Wang and P. Isola, "Understanding contrastive representation learning through alignment and uniformity on the hypersphere," in International Conference on Machine Learning (ICMI.),
2020. (Cited on 2
15

---

[104] F. Wang and H. Liu, "Understanding the behaviour of contrastive loss," in Conference on Computer Vision and Pattern Recognition (CVPR). 2021. (Cited on 42
[105] P. H. Richemond, J.-B. Grill, F. Altché, C. Tallec, F. Strub, A. Brock, S. L. Smith, S. De,
R. Pascanu, B. Piot, and M. Valko, "BYOL works even without batch statistics," arXiv preprint arXiv:2010. 10241, 2020. (Cited on
45
[106] C. Zhang, K. Zhang, C. Zhang, T. X. Pham, C. Yoo, and I. S. Kweon, "How does sim- siam avoid collapse without negative samples? unified understanding with self-supervised contrastive learning," in ICLR, 2022. (Cited on 43 450
[107] L. Ericsson, H. Gouk, and T. M. Hospedales, "Why do self-supervised models transfer? inves- tigating the impact of invariance downstream tasks," arXiv preprint arXivaabs2111.113388 2021. (Cited on 43p
[108] A. Foster, R. Pukdee, and Rainforth, "Improving transformation invariance in contrastive representation learning," in International Conference on Learning Representations (ICIR),
2021. (Cited on 4
[109] J. Kügelgen, Y. Sharma, L.. Gresele, W. Brendel, B. Schölkopf, M. Besserve, and F. Lo- catello, "Self-supervised learning with data augmentations provably isolates content from style," in NeurIPS, 2021. (Cited on 43
[110] T. Galanti, A. György, and M. Hutter, "On the role of neural collapse in transfer learning," in International Conference on Learning Representattonss (ICLR), 2022. (Cited on 43)
[111] L. Hui, M. Belkin, and P. Nakkiran, "Limitations of neural collapse for understanding general- ization in deep learning," arXiv preprint arXiv:2202.083384 2022. (Cited on +3 56
[112] A. Bardes, Ponce, and Y. LeCun, "VICReg: Variance-invariane-covvaa regularizatonoo for self- supervied learning," in International Conference Learning Representations (ICLR),
2022. (Cited on
[113] X. Yan, Misra, A. Gupta, D. Ghadiyaram, and D. Mahajan, "ClusterFit: Improving general- ization of visual representations"" in Conference on Computer Vision and Pattern Recognition (CVPR), 2020. (Cited on
[114] R. D. Hjelm, A. Fedorov, S. Lavoie-Marchille Marchildon, K. Grewal, P. Bachman, A. Trischler, and Y. Bengiio, "Learning deep representations by mutual information estimation and maximization." " in International Conference on Learning Representations (ICLR), 2019. (Cited on 4
[115] P. Bachman, R. D. Hjelm, and W. Buchwalter, "Learning representations by maximizing mutual information across views," in Advances in Neural Information Processing Systems (NeurIPS), 2019.
[116] Y. Tian, D. Krishnan, and P. Isola, "Contrastive multiview coding," in European Conference Computer Vision (ECCV), 2020. (Cited on 45
[117] M. Tschannen, J. Djolonga. P. K. Rubenstein, S. Gelly, and M. Lucic, "On mutual infor- mation maximization for representation learning," in International Conference on Learning
Representations (ICLR), 2020. (Cited on 45)
[118] Y. Xu, S. Zhao, J. Song, R. Stewart, and S. Ermon, "A theory of usable information under computational constraints," in International Conference on Learning Representations (ICIR), 2020. (Cited on 45)
[119] Pokle, J. Tian, Y. Li, and A. Risteski, "Contrasting the landscape of contrastive and non- contrastive learning," in Artificial Intelligence and Statistics (AISTATS), 2022. (Cited on
[120] L. Bossard, M. Guillaumin, and L. V. Gool, "Food-101 - with random forests," in European Conference on Computer Vision (ECCV), 2014. (Cited on
mining discriminative components
[121] A. Krizhevsky, "Learning multiple layers of features from tiny images," " University of Toronto, Tech. Rep., 2009. (Cited on 47 50
[122] J. Krause, M. Stark, J. Deng, and I.. Fei-Fei, "3d object representations for fine-grained categorization," " in ICCV Wokshop on 3D Representation and Recognition, 2013. (Cited on 1
[123] S. Maji, J. Kannala, F. Rahtu, M. Blaschko, and A. Vedaldi, "Fine-grained visual classification of aircraft," arXiv preprint arXiv: X.::vv::33000 5151, 2013. (Cited on 47
16

---

[124] M. Cimpoi, S. Maji, I. Kokkinos, S. Mohamed, and A. Vedaldi. "Describing textures in the wild," in Conference on Computer Vision and Pattern Recognition (CVPR), 2014. (Cited on
47
[125] O.M. M. Parkhi, A. Vedaldi, A. Zisserman, and C. V. Jawahar, "Cats and dogs," in Conference on Computer Vision and Pattern Recognition (CVPR), 2012. (Cited on
[126]
F.-F. Li, M. Andreeto, M. A. Ranzato, and P. Perona, "Caltech 101," 2022. (Cited on +
[127] M.-E. Nilsback and A. Zisserman, "Automated flower classification over a large number of classes," in Indian Conference on Computer Vision, Graphics Image Processing (ICVGIP), 2008. (Cited on 47
[128] K. He, X. Zhang, S. Ren, and Sun, "Deep residual learning for image recognition," in Computer Vision and Patlern Recognition (CVPR), 2016, pp. 770-778. (Cited on 47
[129] S. Ioffe and C. Szegedy, "Batch normalization: Accelerating deep network training by reducing internal covariate shift," " in International Conference on Machine Learning (ICML), 2015, pp. 448-48 -566.. (Cited
[130] D. P. Kingma and J. Ba, "Adam: A method for stochastic optimization," in International Conference on Learning Representations (ICLR), 2015. (Cited on 47
[131] F. Pedregosa, G. Varoquaux, A. Gramfort, Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg. J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay, "Scikit-learn: Machine learning Python," Journal of Machine Learning Research (JMLR), vol. 12, 2011. (Cited on 49
[132] C. Cortes and V. Vapnik, "Suppoortvectoor networks," Machine Learning, vol. 20, pp. 273-297, 1995. (Cited on 49
[133] L. McInnes, J. Healy, N. Saul, and L. Großherger, "UMAP: uniform manifold approximation and projection," Journal of Open Source Software, vol. no. 29, p. 861, 2018. (Cited on 56
17

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] in Sec. 8 eexpanded in Appx. E.
(c) Did you discuss any potential negative societal impacts of your work? [No].
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] in the paper the main paper we mention the important ones succintly, in Appx. A.2 we discuss each in detail.
(b) Did you include complete proofs of all theoretical results? [Yes] in inppp
you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or a URL)? [Yes] all the code to reproduce our results can be found at github.. com/ Soom/Yannubb// -oat--eef-SSuprrvssed---ee
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] in [Appx.
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes] for the TinylmageNet table. We did not for ImageNet due to computational constraints.
Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No].
4. you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes].
(b) Did you mention the license of the assets? [No].
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No].
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/Á].
(b) Did you describe any potential participant risks, with links to Institutional Review Board
(IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A].
18


Reviews:
[{"review_id": "uCkkWQ8xAiZ", "reviewer": "Reviewer_L1ta", "summary": "In this work, the authors characterize the properties of an ideal set of representations for self-supervised learning. Namely, they use the notion of equivalence classes with respect to some transformation, and show that under certain assumptions, it is possible to characterize a sample optimal encoder for the desired equivalence classes. Using intuition from this characterization, they formulate a variant of self-supervised loss which can learn these optimal encoders under ideal conditions. The authors also evaluate practical objectives based on this loss, and show their competitiveness against other similar techniques from the literature.", "questions": "I would like to know whether the authors have performed any experiments regarding transferability of the learned representations for their methods. This is an experiment commonly seen in the literature of this topic, and it would be good if the authors could include it in the paper.\n\nAs mentioned above, I would also suggest the authors to include parts of the related work and proof sketches in the main paper, to help with reader understanding.", "limitations": "The authors have adequately adressed the limitations of their work (namely, the idealized setting of their theory and the lack of constraints on the encoders and tasks considered), both briefly in the main paper and extensively in the appendix. Moreover, I don't believe there is any negative societal impact arising from this work. As such, I believe the authors have addressed these topics sufficiently.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a solid work overall, with several strong points:\n\n- First of all, the topic of this work (self-supervised learning) is of great interest to the NeurIPS community. The authors analyze in great detail this paper’s related work, and properly demonstrate how it is positioned with relation to previous works in the literature. The paper is also very cleanly written overall. As a minor comment, although I understand that the authors moved the related work to the appendix due to space limitations, I believe that at least a short version of its should appear in the main paper.\n\n- Secondly, the theoretical foundation of this work is solid. While the idealized encoders are defined using ideas which exist as a notion in the literature (for example, the fact that we want our encoders to be invariant to augmentations and predictive of the latent classes, which are conditions set in Theorem 1), this work provides a careful formalization of these ideas. Moreover, with Propositions 2 and 3 the authors provide an expression for the expected risk of those encoders and a loss that when minimized recovers these optimal encoders. Even though these theorems are only applicable under idealized assumptions, they still provide a good theoretical characterization of the idealized representations.\n\n- Moreover, the link between the theoretical formulation of the ISSL loss and the practical versions defined in the paper is clear and well-motivated. The authors accurately assess that the main problem in the formulation of the ISSL loss is the lack of knowledge regarding the underlying classes and take measures to rectify this in the practical versions of the loss. I also appreciate the discussion on how each of the two formulations proposed by the authors (CISSL and DISSL) relate to contrastive and non-contrastive technique in the literature, respectively. In my opinion, this provides a good foundation of the proposed techniques, in relation to existing literature. The experimental evaluation of the two proposed methods also demonstrates that they are competitive and in most cases outperform the previous techniques, despite their simplicity.\n\n- Finally, the authors extensively prove their theoretical statements and expand upon connections to the related work in the appendix. The added experiments in the appendix also go beyond standard performance evaluation based on accuracy, and examine various effects such as the augmentations used and the dimensionality of the representations. This is very useful in order to fully understand the proposed method.\n\nA few weaknesses I can identify are the following:\n\n- At the beginning of Section 4, the introduction of the loss function is somewhat abrupt, and while Proposition 3 demonstrates the link of the loss to the optimal encoders discussed above, I believe that including a proof sketch for the proposition or intuition on why it holds would help the connection with the previous parts of the paper. In a similar vein, I believe expanding upon Figure 4 would be useful, because currently it seems to be somewhat disconnected from the rest of the paper.\n\n- A key limitation in the idealized setting is that it holds only in if the dimension of the representation is at least the number of equivalence classes minus 1. Combined with the assumption that the encoder is invariant to the equivalence class, this geometrically implies that there exists one point for each class in the representation space, and they can be shattered by halfspaces (which can be easily done if the points are general enough and they are at most 1 plus the representation dimension). Lemma 13 in the appendix expands upon this, but I believe it should also be pointed out in the main paper, because it may seem as an oversimplification otherwise.\n\n- I believe that Section 5 should be shortened and included in the Section 4. This would allow parts of the appendix (namely, related work and some proof sketches) to be included in the main paper without harming the experimental section (since non-linear probes are only a small part of the main paper).\n\nOverall, this is a strong and clearly written work. The above flaws I pointed out are minor, and I believe that the main issues I have can be addressed in the author response.\n\nMinor comments:\n- In Section 3, consider explicitly highlight the fact that equivalence classes are different from downstream classes, to avoid confusion.\n- Line 43, $\\mathcal{T}$ is not defined.\n- Line 224: missing \"and\"\n- Appendix H.2 seems to be missing.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RLGb3Ll27ty", "reviewer": "Reviewer_uR7p", "summary": "This paper tends to figure out crucial properties of self-supervised learning (SSL) methods, which promote good performance on downstream tasks. To reach this target, the authors propose a unifying conceptual ISSL framework. In particular, their primary contributions contain: i) increasing the dimensionality of presentation and using asymmetric projection heads; ii) presenting a new non-contrastive ISSL objective; iii) applying non-linear probes.", "questions": "- Are there any different insights in your experiments? If yes, please elaborate the difference between this paper and [1,2].\n- Can the authors discuss the difference between DINO and the proposed DISSL?", "limitations": "Yes, the authors have addressed the societal impact of their work.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The motivation is clear, and I appreciate the heavy theoretical and empirical efforts.\n\nHowever, my main doubts/concerns regarding the paper are the following:\n\n- This paper is hard to follow because of the lack of organization. I strongly recommend that the paper needs significant improvement in writing.\n- The novelty of the mentioned contributions is limited:\n1. Increasing the dimensionality of presentation. The effect of dimensionality has been thoroughly discussed in previous literature [1,2]. Are there any different insights in your experiments? If yes, please elaborate the difference between this paper and [1,2].\n2. Using asymmetric projection heads. In [3,4,5], they have theoretically and empirically discussed the impact of asymmetric projection heads.\n3. Novel non-contrastive ISSL objective. To my knowledge, DINO[6] may first introduce \"self-distillation\" into self-supervised learning. The authors mention DINO in line 210, yet I did not find any analysis on comparison between DINO and DISSL. Can the authors discuss the difference between DINO and the proposed DISSL?\n4. Non-linear probes. Although non-linear probes improve downstream tasks, they cannot serve as a property of SSL representation. Thus, this result can hardly support your original motivation.\n5. Coarser augmentation. InfoMin [7] has thoroughly analyzed the effect of augmentations or view selections. Besides, they claimed that \"we should reduce the mutual information (MI) between views while keeping task-relevant information intact.\", which is nearly the same as your proposed \"stronger label-preserving augmentations\".\n- In Table 3, a lack of comparisons with state-of-the-art methods mentioned in the \"related work\" section, including BYOL[3], DINO[7], MoCo[8], Simsiam[9].\n- Inconsistent hyper-parameters between main paper and supplementary material. For instance, \"3072 batch size\" in Table 3 and \"a total batch-size of 2560\" in line 1034.\n\nMinor:\n\n- The experimental setting on TinyImageNet is not standard. I kindly suggest that you could follow some previous work [10,11,12] if the computation resources are constrained.\n- Some informal theorems and algorithms. Take Algorithm 1 (line 237) for example, the inputs are required to be clearly described.\n\n[1] T. Chen, et al., \"A Simple Framework for Contrastive Learning of Visual Representations\", ICML 2020.\n\n[2] J. Zbontar, et al., \"Barlow Twins: Self-Supervised Learning via Redundancy Reduction\", CVPR 2022.\n\n[3] J. Grill, et al., \"Bootstrap your own latent: A new approach to self-supervised Learning\", NeurIPS 2020.\n\n[4] Y. Tian, et al., \"Understanding Self-supervised Learning Dynamics without Contrastive Pairs\", ICML 2021.\n\n[5] X. Wang, et al., \"On the Importance of Asymmetry for Siamese Representation Learning\", CVPR 2022.\n\n[6] M. Caron, et al., \"Emerging Properties in Self-Supervised Vision Transformers\", ICCV 2021.\n\n[7] Y. Tian, et al., \"What Makes for Good Views for Contrastive Learning?\", NeurIPS 2020.\n\n[8] K. He, et al., \"Momentum Contrast for Unsupervised Visual Representation Learning\", CVPR 2020.\n\n[9] X. Chen, et al., \"Exploring Simple Siamese Representation Learning\", CVPR 2021.\n\n[10] Y. Tian, et al., \"Contrastive Multiview Coding\", NeurIPS 2021.\n\n[11] Y. Kalantidis, et al., \"Hard Negative Mixing for Contrastive Learning\", NeurIPS 2020.\n\n[12] C. Chuang, et al., \"Debiased Contrastive Learning\", NeurIPS 2020.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Mt4e7XsMkd", "reviewer": "Reviewer_bMPi", "summary": "Characterizing the desirable properties for representations learned via self-supervised learning objectives,  presents open theoretical and empirical questions, particularly in the context of downstream classification tasks. The authors propose a framework to study popular contrastive and non-contrastive learning algorithms as invariant-SSL (iSSL). Under some technical assumptions, they present certain properties of population-optimal and sample-optimal feature encoders (c.f. Eq 2, Sec 3) for evaluation with linear probes. Building on these characteristics, the paper presents practical design primitives to learn encoders with such properties. In particular, with approximations to a log-loss training objective, and different estimators to approximate the true loss, the framework recovers popular SSL objectives (SimCLR, Dino). Finally, these estimators are evaluated via experiments on the Tiny Imagenet dataset, where ISSL motivated modifications translate to ~3% improvement in both regimes of pretraining. Notably, Distillation ISSL is a simplified training algorithm which recovers representations which are competitive to, and often better than strong baselines (SwAV).", "questions": "A couple of questions for the authors:\n1. How well do the estimators approximate the desired quantities (e.g. DISSL approximates $M(x)$) ? For instance, are there controlled experiments with toy datasets to demonstrate the effectiveness of the auxillary losses?", "limitations": "The authors are encouraged to consider relaxing some of the strict assumptions, namely:\n1. Coarse-grained effects of data-augmentation operators (the operators are often smooth, low-variance). \n2. While the authors demonstrate that stronger data-augmentations improve in-distribution generalization, I think it also important to consider out-of-distribution generalization (i.e. performance on different tasks).", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ The paper presents a novel framework (ISSL) to study the paradigm of contrastive learning, SSL pretraining objectives. Notably, the authors study invariance to data-augmentation with downstream classification tasks and use ISSL to find simplifications to popular SSL algorithms (e.g. SimCLR with asymmetric projection head, Distillation SSL as an alternative to SwAV).\n+ The authors perform extensive ablations on TinyImagenet dataset and compare to strong baselines to establish the efficacy of insights from there proposed framework. The simplifed learning objectives could further encourage research into more fine-grained questions about these training algorithms (such as learning dynamics, sample efficiency etc).\n\n\nWeaknesses:\n- Beyond evaluation on linear probing, the authors are encouraged to present visualizations, discussion on emergent structure in representations learned with their proposed algorithm as compared to prior work. \n- Certain assumptions in the framework are too restrictive or unrealistic (such as label being either invariant to class of augmentations, or not i.e. binary effects of the data-augmentations). ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4il0TR1vPYV", "reviewer": "Reviewer_j7cH", "summary": "In this work, the authors characterize properties that representations learned in self-supervised way should ideally satisfy. They prove necessary and sufficient conditions such that for any task invariant to given data augmentations, the probes (e.g., linear or MLP) trained on such representation attain perfect accuracy. Based on these requirements the authors propose a unifying framework for improving existing SSL methods and deriving new ones. In contrastive learning regime, they propose asymmetric projection heads and in non-contrastive learning regime, they derive novel objective. \n\nIn the evaluation, the authors focus on the implications of the proposed framework using the TinyImageNet and ImageNet data sets. It consists of experiments and results \n(i)   about the use of the proposed objectives to ensure sample optimal encoders in ideal settings, \n(ii)  regarding the finding by the theoretical result (Theorem 1), \n(iii) related to the use of coarser label-preserving augmentations (Proposition 2) and \n(iv) for training with the smallest ISSL log loss to ensure optimality (Proposition 3). \n\nThe results show that the proposed self-supervised algorithms lead to improvements in performance with respect to the baselines on the used datasets for different ResNet neural network architectures.", "questions": "Could the authors comment more about how close the proposed theoretical foundation is to the practical cases?\nHave the authors evaluated the proposed approach on other datasets (common in computer vision or other public ones)?\n", "limitations": "The authors address the limitations of the paper exposition in Section 7 Discussion and Outlook. Regarding the potential negative societal impact might be nice that the authors comment/discuss about the theoretical connections/aspect of their framework related to learning of possible biases/\"short cuts\" that might be undesirable as well as misused.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The authors present a framework in an attempt to characters self-supervised learning and describe the problem grounded on invariant self-supervised learning and idealized representations. The authors formalized the notion of invariant self-supervised learning using an equivalence relation between original data and it's augmented version that should partitions the inputs X into  equivalent classes. Further they define optimal encoders at least theoretically, stating/defining population optimal and sample optimal cases that can produce ideal representations in terms of classification with minimum error (minimum empirical risk).\n\nThey give result about the required dimensionality of the population optimal encoders (at the output) by which the representations are linearly predictable. They argue that ERMs encoders that correctly predict one example in an equivalence class, also correctly predict all the others. They prove that such invariance of population optimal encoders is necessary and sufficient for sample optimality.\n\nThey also derive simple objectives that learn optimal encoders in ideal settings (infinite data, perfect optimizers, universal function approximators). In addition, they try to explain why previously proposed invariant self-supervised learning methods work, and comment how they might be improved in practice for contrastive invariant self-supervised learning and distillation invariant self-supervised learning.\n\nQuality: The quality seems good. It is interesting how the authors state the problem formulation and relate it to empirical risk minimization in order to characterize the ideal representations (under ideal scenario) as well as how the authors relate to existing work and to practical considerations. \n\nIn the evaluation, the authors focus on experiments that are towards verifying the postulated theory. On the TinyImageNet data set they show large gaps of improvement of recondition accuracy compared to the used baselines. On the ImageNet data set they are somewhat on pair (with small improvement) compared to some of the state-of-the-art methods.\n\nClarity: The paper attempts to outlay an unified theory. Overall, the paper is well organized and the writing is good. The readers have to keep track of the many characteristics, propositions, derivations, etc, sometimes pushes the paper a bit on the heavy side, which might suggest that the content in this work needs more space. Maybe a table of content about the most important concepts could help.\n\nThe authors take on practical considerations for contrastive invariant self-supervised learning and distillation invariant self-supervised learning. Maybe focusing only on one of these two (or putting one in the appendix) might have made the paper lighter and the authors could have had more space to do more experiments as well as overall make the paper a more easy of a read. On the other hand, there are also a lot of additional details that the authors leave for the appendix\n\nSignificance: Unsupervised and self-surprised learning might be very important aspect towards the long-lasting goal of human-capable machine learning and artificial intelligence in practice. Theoretical foundation in this direction are of particular interest for understanding and improving existing works, and designing novel algorithms that could brings us closer to this goal.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept