# Simplicial Embeddings in Self-Supervised Learning and Downstream
Classification

Samuel Lavoie⋄†, Christos Tsirigotis⋄†, Max Schwarzer⋄†, Kenji Kawaguchi‡,
Ankit Vani⋄†,
Aaron Courville⋄†♣
⋄ Mila, † Université de Montréal, ‡ National University of Singapore, ♣ CIFAR
Fellow
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

We introduce Simplicial Embeddings (SEMs) as a way to constrain the encoded
representations of a self-supervised model to $L$ simplices of $V$ dimensions
each using a Softmax operation. This procedure imposes a structure on the
representations that reduce their expressivity for training downstream
classifiers, which helps them generalize better. Specifically, we show that
the temperature $\tau$ of the Softmax operation controls for the SEM
representation’s expressivity, allowing us to derive a tighter downstream
classifier generalization bound than that for classifiers using unnormalized
representations. We empirically demonstrate that SEMs considerably improve
generalization on natural image datasets such as CIFAR-100 and ImageNet.
Finally, we also present evidence of the emergence of semantically relevant
features in SEMs, a pattern that is absent from baseline self-supervised
models.

##  1 Introduction

Self-supervised learning (SSL) is an emerging family of methods that aims to
learn an embedding of the data without manual supervision, such as class
labels. Those methods embed the data in some representations that render
themselves amenable to fitting a linear classifier, as demonstrated in Hjelm
et al. [2019]; Grill et al. [2020]; Saeed et al. [2020]; You et al. [2020].
This observation demonstrates that the representation learned by those SSL
methods encodes the semantic content necessary to learn a classifier as a
linear combination of the features.

In this work, we propose to embed the latent representation of the data into
$L$ simplices of $V$ dimensions each by using a Softmax operation. We refer to
the normalized embeddings as Simplicial Embeddings (SEMs) due to the
geometrical structure of the representation induced by the Softmax. The SEMs
have an effect both while training the representation and on the training of
the downstream classifier. For the former, the SEM is an inductive bias to fit
the data in a more constrained space that may lead to a simpler
representation. For the latter, the Softmax allows us to control for the
expressivity of the representation. This control gives us a better
generalization bound for training downstream classifiers.

We demonstrate that the proposed SEMs improve the generalization of downstream
classifiers trained with BYOL [Grill et al., 2020] and MoCo [He et al., 2020]
on CIFAR-100 and ImageNet. We also show an improvement in transfer learning
and robustness to out-of-distribution datasets. Finally, we present evidence
that individual features of the SEMs encode semantical content related to our
intuitive notion of the semantics in CIFAR-100. In contrast, we argue that the
baseline SSL methods may learn the semantics related to the classes as a
linear combination of the features in the representation but not at the
individual features’ level.

Concretely, this work makes the following contributions:

  1. 1.

Propose the Simplicial Embeddings.

  2. 2.

Derive a generalization bound for downstream classifiers trained on the
Simplicial Embeddings.

  3. 3.

Empirically studies the Simplicial Embeddings and its effect on the
generalization of downstream classifiers.

###  1.1 Related works

The use of Softmax as an inductive bias has been studied in other contexts,
notably as an architectural component for models to attend to context-
dependent queries via, for example, attention mechanisms [Bahdanau et al.,
2016; Vaswani et al., 2017] or memory augmented networks [Graves et al.,
2014]. Different from these, our method places the Softmax at the output of an
encoder to constrain the representation and to allow control of the
expressivity of the representation for downstream classifiers.

Our work builds on top of the literature on self-supervised learning. Notably,
we demonstrate the effect of the SEM on contrastive approaches using the noise
contrastive estimation (NCE) objective [Hjelm et al., 2019; Chen et al.,
2020b] with memory banks [He et al., 2020] and on the bootstrapping approaches
[Grill et al., 2020; Chen and He, 2020]. Related, some works explicitly induce
clustering of the representation [Caron et al., 2019; Ym et al., 2019; Caron
et al., 2020]. Contrary to these works, we do not explicitly induce clustering
on the representation.

In the realm of improving the generalization of SSL methods, Wang et al.
[2021] propose a method to iteratively select a partition of the data and use
this partition to minimize an IRM regularizer [Arjovsky et al., 2020] with an
SSL objective. Lee et al. [2021] present an objective to minimize the
conditional entropy bottleneck. Contrary to these works, our methods do not
require additional objectives as it is merely an inductive bias in the SSL
models.

##  2 Background on self-supervised learning

Models trained with a contrastive objective learn to embed samples
$x\in\mathcal{X}$ into representations $z\in\mathcal{Z}$, where $\mathcal{Z}$
is a bounded metric space. The aim is to both minimize the distance between
the representation of a sample
$z_{i}=f_{\theta}(x_{i})\mathrel{\mathop{\mathchar 58\relax}}x\in\mathcal{X}$
and the representation of a positive sample $z_{j}=f_{\theta}(x_{j})$, and to
maximize the distance between $z_{i}$ and the representation of negative
samples $f_{\theta}(x^{\prime})\mathrel{\mathop{\mathchar
58\relax}}x^{\prime}\in\mathcal{X}\setminus x_{i}$. While the positive samples
are typically augmented samples of $x_{i}$, other strategies can be decided,
such as choosing samples from the same labelled category [Khosla et al.,
2020]. A common contrastive objective is Noise Contrastive Estimation (NCE)
[Hjelm et al., 2019; Chen et al., 2020b], which is defined as

$\mathcal{L}_{\text{nce}}\mathrel{\mathop{\mathchar
58\relax}}=-\log\dfrac{\exp(d(z_{i},z_{j})/t)}{\sum_{\bar{x}\in\mathcal{X}\setminus
x}\exp({d(z_{i},\bar{z})/t)}},$ (1)

where $d$ is often taken to be the cosine similarity:
$d(x,y)\mathrel{\mathop{\mathchar 58\relax}}=x^{\top}y/\|x\|_{2}\|y\|_{2}$ and
$t>0$ is a hyper-parameter that denotes a temperature.

Unlike most contrastive methods, BYOL [Grill et al., 2020] does not require
negative samples. Instead, it introduces a target network in which the
parameters $\xi$ are taken as an exponential moving average of the embedding
function parameters, $\theta$. More precisely,
$\xi\leftarrow\alpha\xi+(1-\alpha)\theta$, with $\alpha\in[0,1]$. The authors
define the anchor and positive samples as $z_{\theta}=f_{\theta}(t(x))$ and
$z_{\xi}=f_{\xi}(t^{\prime}((x))$ respectively, where
$t,t^{\prime}\sim\mathcal{T}$ are augmentations sampled from a set of possible
augmentations defined by the practitioner. To prevent degenerate solutions,
they re-normalize the representation using batch normalization [Ioffe and
Szegedy, 2015], and utilize a stop-gradient operation on $z_{\xi}$ that
prevents the gradient from back-propagating through the target network. They
also introduce a _prediction head_ that maps the representation to a
prediction: $z_{\theta}\mapsto q_{\theta}$. The BYOL objective is defined as

$\mathcal{L}_{\text{byol}}\mathrel{\mathop{\mathchar 58\relax}}=2-2\cdot
d(q_{\theta},\ z_{\xi}),$ (2)

where $d$ is chosen to be the cosine similarity.

(a)

(b)

(c)

Figure 1: (a) Illustration of the proposed Simplicial Embeddings (SEM).
$\sigma_{\tau}$ represents the Softmax operation with $\tau$. We assume that
$z$ decomposes into $L$ vectors in $\mathbb{R}^{V}$. (b) Histogram of the
entropies $H(\bar{z}_{i}^{(x)})$ at the end of the pre-training phase, for a
given temperature $\tau$, of each simplex for each training sample in
CIFAR-100. (c) Integration of the SEM with BYOL [Grill et al., 2020].

##  3 Simplcial Embeddings

We illustrate the proposed Simplicial Embeddings (SEMs) in Figure 1(a). An
encoder embeds a sample $x$ into a $L\times V$ representation $z$. A
temperature parameter $\tau$ then scales the logits $z\in\mathbb{R}^{L\times
V}$ before re-normalizing each row via $L$ independent Softmax operations.
Then, the normalized vectors are concatenated to produce
$\bar{z}\in\mathbb{R}^{LV}$. Concretely, the logits are re-normalized as
follows:

$\begin{split}\bar{z}_{i}\mathrel{\mathop{\mathchar
58\relax}}=[\sigma_{\tau}(z_{i1}),~{}\ldots,\sigma_{\tau}(z_{iV})],\sigma_{\tau}(z_{ij})=\dfrac{e^{z_{ij}/\tau}}{\sum_{k=1}^{V}e^{z_{ik}/\tau}},~{}\bar{z}\mathrel{\mathop{\mathchar
58\relax}}=\text{Concat}(\bar{z}_{1},\ldots,\bar{z}_{L}),\end{split}$ (3)

for all $i\in[L]$ and $j\in[V]$.

The SEMs can be integrated easily into a NCE model [Hjelm et al., 2019; Chen
et al., 2020b] or BYOL [Grill et al., 2020]. We insert it after the encoder
and before the projector in our experiments. Figure 1(c) depicts how we use
the SEMs in BYOL. The embedding $\bar{z}$ is passed into the projector module,
which we define as a linear layer or a small MLP. Beyond this small
modification, the SSL method considered remains unchanged.

###  3.1 Inductive bias of the SEMs

We now describe at a high level the inductive bias of the SEMs during the
self-supervised learning phase. We note that each simplex can be interpreted
as representing a probability mass function $p(\bar{z}_{i}^{(x)})$ where
$\sum_{j=1}^{V}p(\bar{z}_{ij}^{(x)})=1$ and $p(\bar{z}^{(x)}_{ij})\geq
0~{}\forall j$. Here, $\bar{z}^{(x)}_{i}$ represents the simplex $i$ for a
sample $x$. The simplex puts a constrain on how the its elements may organize:
they may interpolate between being a sparse vector and being a constant
vector. The state of a simplex can be quantified using the entropy of
$p(\bar{z}_{i}^{(x)})$ that we denote as follows:
$H(\bar{z}_{i})\mathrel{\mathop{\mathchar
58\relax}}=-\sum_{j=1}^{V}p(\bar{z}_{ij}^{(x)})\log p(\bar{z}_{ij}^{(x)})$.
That is, if $H(\bar{z}_{i}^{(x)})=0$ then the vector is sparse and if
$H(\bar{z}_{i}^{(x)})=\log(V)$ then the vector is constant.

While we may argue that the temperature parameter $\tau$, which merely induces
a scaling of the logit, may be subsumed during training, we demonstrate in
Figure 1(b) that this temperature is an important initial condition for
determining the state to which the simplex will converge. Here, we plot the
histogram of the entropies $H(\bar{z}_{i}^{(x)})$, for a given $\tau$, of each
simplex for each sample $x$ in the training set of CIFAR-100. The temperature
parameter dictates in which state the representation will converge: a small
$\tau$ will induce a sparse representation, and a large $\tau$ will induce a
constant representation. Interestingly, for an intermediate temperature, the
distribution of entropies is more spread out, rather than having the same
variance smoothly translated toward the center of the histogram.

The above observation gives an intuition about how the induce a bias of the
SEMs on the learned representation during SSL. Besides the qualitative
properties of the vectors that the SEM may induce, this embedding has a
particular structure that we may leverage for learning a classifier with a
better generalization bound. Next, we theoretically present how the SEMs allow
for a better generalization of a downstream classifier and derive a
generalization bound for the classifiers trained on such representation.

###  3.2 Theoretical bound on the downstream classifier

In this subsection, we mathematically analyze the SEM to understand its
benefit and the effect of the hyper-parameter $\tau$. We show that: (1) there
is a trade-off between the training loss and the generalization gap, which is
controlled by the value of $\tau$, and (2) the SEM can improve the base model
performance when we attain good balance in this trade-off.

Let $g$ represent the layer(s) after the normalization. With this notation, we
can define a baseline model without normalization as
$f_{\mathrm{base}}(z)=g(z)$ and the corresponding model with normalization as
$f_{\mathrm{SEM}(\tau)}(z)=(g\circ\sigma_{\tau})(z)$. We consider a training
dataset $S=(z_{i},y_{i})_{i=1}^{n}$ of $n$ samples that is used for supervised
training of a classifier using the representations $z$, which are extracted
from the self-supervised encoder. To understand the quality of the final model
after supervised training of the classifier, we analyze the generalization gap
$\mathbb{E}_{z,y}[l(f(z),y)]-\frac{1}{n}\sum_{i=1}^{n}l(f(z^{(i)}),y^{(i)})$
for each $f\in\\{f_{\mathrm{SEM}(\tau)}^{S},f_{\mathrm{base}}^{S}\\}$, where
$l\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}\times\mathcal{Y}\rightarrow\mathbb{R}_{\geq 0}$ is the
per-sample loss.

To simplify the notation, we consider the normalization to $[-1,+1]$; i.e.,
$z\in\mathcal{Z}=[-1,+1]^{L\times V}$. We assume that there exists $\Delta>0$
such that for any $i\in[L]$, if $k=\operatorname*{arg\,max}_{j\in[V]}z_{ij}$,
then $z_{ik}\geq z_{ij}+\Delta$ for any $j\neq k$. Since $\Delta$ can be
arbitrarily small (e.g., much smaller than machine precision), this assumption
typically holds in practice. Next, we define $B$ to be the upper bound on the
per-sample loss such that $l(f(z),y)\leq B$ for all $f\in\mathcal{H}$ and for
all $(z,y)\in\mathcal{Z}\times\mathcal{Y}$, where $\mathcal{H}$ is the union
of the hypothesis spaces of $f_{\mathrm{SEM}(\tau)}$ and $f_{\mathrm{base}}$.
For example, $B=1$ for the 0-1 loss. We also use
$\mathcal{Q}_{i}=\\{q\in[-1,+1]^{V}\mathrel{\mathop{\mathchar
58\relax}}i=\operatorname*{arg\,max}_{j\in[V]}q_{j}\\}$, with the following
two definitions:
$\varphi(f_{\mathrm{base}}^{S})=\sup_{i\in[V]}\sup_{q,q^{\prime}\in
Q_{i}}\sum_{t=1}^{n}\|q-q^{\prime}\|_{2}^{2},$ and
$\varphi(f_{\mathrm{SEM}(\tau)}^{S})=\sup_{i\in[V]}\sup_{q,q^{\prime}\in
Q_{i}}\sum_{t=1}^{n}\|\sigma_{\tau}(q)-\sigma_{\tau}(q^{\prime})\|_{2}^{2}$,
where
$\sigma_{\tau}(q)_{j}=\frac{e^{q_{j}/\tau}}{\sum_{t=1}^{V}e^{q_{t}/\tau}}$ for
$j=1,\dots,V$. Next, we define $\mathcal{G}_{S}$ to be the set of $g$ returned
by the training algorithm using dataset $S$, and $R$ to be the Lipschitz
constant of $l_{y}\circ g$ for all $y\in\mathcal{Y}$ and
$g\in\mathcal{G}_{S}$; i.e., $|(l_{y}\circ g)(z)-(l_{y}\circ
g)(z^{\prime})|\leq R\|z-z^{\prime}\|_{F}$, where $l_{y}(q)=l(q,y)$. Finally,
let $c>0$ be a universal constant in
$(n,f,\mathcal{H},\delta,\mathcal{H},\tau,S)$.

Using the established notation, Theorem 1 illuminates the advantage of the SEM
and the effect of the hyper-parameter $\tau$ on the performance of the
downstream classifier:

######  Theorem 1.

Let $V\geq 2$. For any $\delta>0$, with probability at least $1-\delta$, the
following holds for any
$f_{S}\in\\{f_{\mathrm{SEM}(\tau)}^{S},f_{\mathrm{base}}^{S}\\}$:

$\displaystyle\mathbb{E}_{z,y}[l(f_{S}(z),y)]\leq\frac{1}{n}\sum_{i=1}^{n}l(f_{S}(z^{(i)}),y^{(i)})+R\sqrt{\frac{L\varphi(f_{S})}{n}}+c\sqrt{\frac{\ln(2/\delta)}{n}}.\vspace{-10pt}$

Moreover,

$\displaystyle\varphi(f_{\mathrm{SEM}(\tau)}^{S})\rightarrow 0\ \ \text{ as
}\tau\rightarrow
0\quad\text{and}\quad\varphi(f_{\mathrm{SEM}(\tau)}^{S})-\varphi(f_{\mathrm{base}}^{S})\leq\frac{3n}{4}(1-V)<0\
\ \ \forall\tau>0.$

The first statement of Theorem 1 shows that the expected loss is bounded by
the three terms: training loss
$\frac{1}{n}\sum_{i=1}^{n}l(f_{S}(z^{(i)}),y^{(i)})$, the second term
$R\sqrt{\frac{L\varphi(f_{S})}{n}}$, and the third term
$c\sqrt{\frac{\ln(2/\delta)}{n}}$. Since $c$ is a universal constant in
$(n,f,\mathcal{H},\delta,\mathcal{H},\tau,S)$, the third term
$c\sqrt{\frac{\ln(2/\delta)}{n}}$ goes to zero as $n\rightarrow\infty$ and is
the same for both models with and without soft-discretization. Thus, for the
purpose of comparing the models with and without soft-discretization, we can
focus on the second term, where the difference arises.

Theorem 1 shows that the second term $R\sqrt{\frac{L\varphi(f_{S})}{n}}$ goes
to zero with the SEM; i.e., $\varphi(f_{\mathrm{SEM}(\tau)}^{S})\rightarrow
0\text{ as }\tau\rightarrow 0$. Also, for any $\tau>0$, the second term with
soft-discretization is strictly smaller than that without soft-discretization
as
$\varphi(f_{\mathrm{SEM}(\tau)}^{S})-\varphi(f_{\mathrm{base}}^{S})\leq\frac{3n}{4}(1-V)<0$.
This shows that the improvement due to soft-discretization is expected to be
higher as $V$ increases.

Overall, Theorem 1 shows the benefit of the SEM as well as the trade-off with
$\tau$. When $\tau\rightarrow 0$, the second term goes to zero, but the
training loss (the first term) can increase due to the reduction in
expressivity and increased difficulty in optimization. Thus, we assert that
the best $\tau$ is the one that balances this trade-off.

##  4 Experiments

We study the effect of the Simplicial Embeddings on the generalization of
self-supervised learning methods111We provide the code to reproduce the
experiments: https://github.com/lavoiems/simplicial-embeddings. We demonstrate
that the Simplicial Embeddings improve the test set accuracy on CIFAR-100 and
ImageNet. On CIFAR-100, we also study the different properties of the SEM, and
we demonstrate the emergence of semantic features relevant to the classes in
the representation feature. On ImageNet, we show that the Simplicial
Embeddings improve the test accuracy on several robustness test sets and the
accuracy on transfer learning datasets.

###  4.1 The effect of the SEM on downstream classification

Method | Accuracy
---|---
SimCLR$\dagger$ | $65.78$
MOCO$\dagger$ | $69.89$
SwaV$\dagger$ | $64.88$
DINO$\dagger$ | $66.76$
BYOL | $70.46$
BYOL \+ SEM | 74.36
(a) CIFAR-100 on ResNet18

Method | Accuracy
---|---
SimCLR$\ddagger$ | $68.73$
BYOL | $74.28$
BYOL* | $73.33$
BYOL \+ SEM | 77.05
(b) CIFAR-100 on ResNet50

Method | Accuracy
---|---
SimCLR$\ddagger$ | 63.1
MoCo$\ddagger$ | 67.3
MoCo \+ SEM | 69.0
SimSiam$\diamond$ | 70.0
BYOL$\diamond$ | 70.6
BYOL \+ SEM | 72.8
(c) ImageNet on ResNet50

Figure 2: Accuracy on (a) CIFAR-100 with ResNet18 for 1000 epochs. (b)
CIFAR-100 with ResNet50 for 1000 epochs. (c) ImageNet with ResNet50 for 200
epochs. *Denotes the accuracy obtained when training BYOL with a
representation the same size as SEM. $\dagger$ Results taken from da Costa et
al. [2021]. $\ddagger$ Results taken from Wang et al. [2021]. $\diamond$
Results taken from [Chen et al., 2020b]. Boldface indicates highest accuracy.
Green rows indicate a SSL method + SEM.

Comparison study.  We first compare the effect of using the SEM in a BYOL
model with related SSL approaches in the literature. We take a standard BYOL
model, as implemented in the Solo-Learn library [da Costa et al., 2021], and
implement the Simplicial Embeddings after the encoder. We test our approach
with a ResNet18 and ResNet50 on CIFAR-100 and with a ResNet50 for ImageNet [He
et al., 2015]. Our models are trained with Stochastic Gradient Descent [Bottou
et al., 2018] with a cosine decay scheduler on the learning rate, as done in
previous works [Grill et al., 2020; Chen et al., 2020b]. We use a batch size
of 256 for all of our models and train on a single A100 GPU. We selected the
parameters of the SEM by performing a grid search over several values using a
validation set and re-trained our model using all the training data to
evaluate the test set. We did not modify the default hyper-parameters of the
method, demonstrating that the gain in accuracy is a product of the SEM. We
present the hyper-parameters used in the Appendix. We evaluate all of our
models by training a linear classifier, using the training data on top of the
learned representations as it is typically done.

We compare our approach on CIFAR-100 and ImageNet in Table 1(b) and Table 1(c)
respectively. Compared with prior models, our approach improves the baseline
methods by a considerable margin. On CIFAR-100, we compare with several
baselines, such as DINO and SwaV. We also trained BYOL with the same
representation size as what we used in the SEM, without the embedding, and
observed a marginal performance decrease. As demonstrated in Zbontar et al.
[2021], BYOL does not seemingly benefit from large representations.

The SEM also presents a noticeable improvement compared to the baselines on
ImageNet when trained for 200 epochs. Here, we trained our model on both BYOL
and MOCO [He et al., 2020] to demonstrate that the effect of the SEM is not
limited to BYOL.

Figure 3: Study of the effect of the parameters of the SEM. We plot the
accuracy obtained for several downstream classification SEM’s temperature
($f_{\text{SEM}(\tau)}$) and without SEM ($f_{\text{base}}$) described in the
legend. We performed the training with a ResNet18 on CIFAR-100. Interpolation
of Left: $\tau$ during the training of the SSL model. Middle: $V$. Right: $L$

Study of the SEM parameters.  We study the effect of each of the parameters of
the SEM and evaluate their effect on the validation accuracy in Figure 3. We
trained each model with a ResNet18 on CIFAR-100 using the BYOL training
procedure. We keep the other parameters constant to their default value for
each parameter that we study. The default value of $\tau$ is $1$, $V$ is $13$
and $L$ is $5000$. For each pre-trained SSL model, we trained 5 downstream
classifiers, one on the unnormalized features denoted $f_{\text{base}}$ and
one on the normalized features for $\tau\in\\{0.01,0.1,1,10\\}$.

We observe that the temperature used to normalized the embedding before
training the downstream classifier, $f_{\text{SEM}}(\tau)$, is important for
the downstream classification and is generally better than training a
classifier on the unnormalized features ($f_{\text{base}}$) as predicted in
Theorem 1. We observe the trade-off, as presented in Section 3.2, between
having a small and a large $\tau$.

We also observe a trade-off between having a large and a small temperature
when training the SSL model. As demonstrated in Figure 1(b), the temperature
parameter has an impact on whether the simplicies will represent a sparse or a
constant vector. We demonstrated that a small temperature yields a set of
sparse vectors while a large temperature yields a constant vector. Here, we
observe that the temperature yielding the better validation accuracy offers a
trade-off between a sparse and a constant vector. We hypothesize that a sparse
vector leads to harder training but a smaller expressivity. Thus, the better
temperature during the training of the SSL model is the one that offers a
trade-off between a sparse but trainable representation.

In Theorem 1, we demonstrated theoretically that the second term was more
sensitive to the temperature as $V$ increased. This prediction is empirically
verified in Figure 3 where we evaluate the validation accuracy for several
$V$. As $V$ increases, the validation accuracy drops for larger $\tau$s. For
example, the validation accuracy drops when interpolating between $V=13$ and
$V=34$ for $\tau=10$, stays constant for $\tau=1$ and increases for the
smaller temperatures.

Finally, we interpolate the $L$ parameter and demonstrate that larger $L$
yields increased normalized features’ validation accuracy. As expected, the
effect of $\varphi(f_{S})$ grows with larger $L$, and thus we would expect a
bigger difference between $f_{\text{base}}$ and $f_{\mathrm{SEM}}(\tau)$. This
demonstrates empirically and theoretically that the SEM may scale the
representation of SSL methods to a larger representation and thus potentially
increasing the scaling capability of these methods.

(a)

(b)

Figure 4: Semantic relevance of the features. (a) Subset of $\mathcal{W}_{K}$,
the bipartite graph of the most important features shared between at least two
classes of a classifier trained on BYOL + SEMs features. The connected
components emerge without additional interventions. (b) Relevance of the top
$K$ features to the semantics of the super-class of the categories of
CIFAR-100. It is taken as the number of pairwise categories in the same super-
class for which a feature is among its top $K$ most predictive features over
the total number of pairwise categories.

###  4.2 Emergence of semantically relevant features

In this subsection, we investigate the semantic content held by the most
predictive features of an embedding. To make this study, we consider an
encoder pretrained on CIFAR-100, using BYOL with and without SEM, and a
downstream linear classifier trained on the embedding of the CIFAR-100
samples. Consider the trained linear classifier with a weight matrix
$W\in\mathbb{R}^{N\times C}$, where $N$ denotes the number of features, and
$C$ denotes the number of classes. This classifier is trained by minimizing
the cross-entropy loss between the predicted class and the given label.

Here, we study the semantic relevance of the top $K$ features for each class.
Consider the weight matrix $W$. By preserving the top $K$ parameters of this
weight matrix for each class and pruning the features predictive for only one
class, we create a bipartite graph between two set of nodes: the categories
and the features. We denote this graph $\mathcal{W}_{K}$. We plot a subset
$\mathcal{W}_{5}$, obtained when taking the top $5$ features for each class,
on the SEM representations in Figure 4(a) and the full bipartite graph on the
SEM and the one obtained when applying the procedure on the representation
obtained with an unnormalized BYOL in the Appendix. In the graph obtained with
the SEM, we observe that a set of connected components emerge, and the
connected components of the graph are semantically related. For example, the
first set of connected components are fruits and vegetables, and the second
set of connected components are aquatic mammals. The same observation does not
occur when this experiment is performed on the baseline BYOL and BYOL, with a
large representation model. In particular, we do not see a small number of
semantically related connected components. Instead, we see a large fully
connected graphs. This observation suggests that the features learned by the
baseline model do not hold the same amount of semantic information. Instead,
the semantic information could be encoded as a linear combination of several
features, for example.

|  |  | 100% |  |  |  |  | 1% |  |
---|---|---|---|---|---|---|---|---|---|---
| IN | IN-V2 | IN-R | IN-A | IN-C | IN | IN-V2 | IN-R | IN-A | IN-C
BYOL | 68.3 | 55.3 | 16.5 | 0.68 | 35.4 | 46.8 | 37.5 | 12.2 | 0.71 | 25.0
BYOL \+ SEM | 70.6 | 57.9 | 18.1 | 0.77 | 38.9 | 47.9 | 38.5 | 12.2 | 0.65 | 25.3
MoCo | 66.7 | 53.4 | 14.0 | 0.69 | 31.1 | 43.5 | 34.2 | 8.7 | 0.51 | 20.1
MoCo \+ SEM | 68.0 | 55.0 | 15.21 | 0.61 | 33.8 | 44.1 | 35.9 | 9.1 | 0.51 | 21.4
Table 1: Test accuracies of a linear probe trained with 100% and 1% of the ImageNet samples on a pre-trained representation trained for 100 epochs. Boldface indicates the maximal value for each evaluation set and each base model type (BYOL or MoCo). | Food | Cifar10 | CIFAR-100 | SUN | DTD | Pets | Flowers | Caltech | Cars
---|---|---|---|---|---|---|---|---|---
BYOL | 71.3 | 89.5 | 71.4 | 57.6 | 71.5 | 85.4 | 84.6 | 77.8 | 45.7
BYOL \+ SEM | 74.1 | 92.0 | 76.3 | 60.5 | 72.5 | 87.1 | 88.6 | 82.4 | 57.3
MoCo | 70.6 | 88.6 | 69.5 | 57.6 | 70.9 | 82.3 | 81.5 | 74.3 | 39.8
MoCo \+ SEM | 71.0 | 89.6 | 72.8 | 58.6 | 70.9 | 83.8 | 84.5 | 77.5 | 45.2
Table 2: Transfer learning accuracy by training a linear probe on a pre-
trained representation with ImageNet for 100 epochss. Boldface indicates the
maximal value for each transfer dataset and each base model type (BYOL or
MoCo).

We also study more quantitatively the semantic relevance of the features in
CIFAR-100. Two categories share a predictive feature on $\mathcal{W}_{K}$ if
they are 2-neighbour, that is they share a common predictive feature. Let
$\mathcal{N}(c_{i})$ returns all pairs $(c_{i},c_{j})$ for all $j$ 2-neighbour
of $c_{i}$. Moreover, define the operation $\text{is\\_super}(c_{i},c_{j})$
which returns 1 if $c_{i}$ and $c_{j}$ are from the same CIFAR-100 superclass
and $0$ otherwise. We reproduce the superclass of CIFAR-100 in Table 5. We
define the semantic relevance as follows:

$\text{Relevance}(\mathcal{W}_{K})\mathrel{\mathop{\mathchar
58\relax}}=\sum_{i=1}^{C}\dfrac{\sum_{(c_{i},c_{j})\in\mathcal{N}(c_{i})}\text{is\\_super}(c_{i},c_{j})}{|\mathcal{N}(c_{i})|},$
(4)

where $C=100$ for CIFAR-100 and $|\cdot|$ is the cardinality of a set.

We compare the semantic relevance of BYOL+SEM with the control experiments
BYOL and BYOL with a representation of the same size as BYOL+SEM but without
the normalization. We observe that using the SEM yields more semantically
relevant features than the baseline. This observation is consistent with the
qualitative experiments presented earlier and indicates that the semantics
encoded in the baseline representation may follow a more complicated syntactic
structure than those encoded with the SEM features.

###  4.3 Out-of-distribution evaluation on ImageNet

Robustness to out-of-distribution test sets on ImageNet.  We perform a
comparative study using several robustness evaluation sets. Specifically, we
use the validation set provided in ImageNet; ImageNet-C, which exhibits a set
of common image corruptions [Hendrycks and Dietterich, 2018]; Imagenet-A [Chen
et al., 2020a], which contains a set of natural adversarial examples that are
misclassified by a Resnet-50 classifier; ImageNet-R [Hendrycks et al., 2021],
which consists of different renderings for several ImageNet classes; and
ImageNet-V2 [Recht et al., 2019], a distinct test set for ImageNet collected
using the same process. We use the methodology proposed in Djolonga et al.
[2020, 2021] along with their software to perform our experiments.

Table 1 shows the performance on these test sets using a linear probe trained
with 100% of ImageNet’s data and 1% of ImageNet’s data. Using the SEM
generally leads to an improvement in the in-distribution and out-of-
distribution generalization. Notably, we observe a 2% improvement on BYOL due
to the SEM on in-distribution ImageNet. On average, there is an improvement of
2% and 0.5% in the 100% and 1% data regimes respectively for BYOL. For MoCo,
the average improvement due to the SEM is 1.5% and 0.8% for the 100% and 1%
data regimes respectively.

Transfer learning on ImageNet.  We probe the effect of inducing the SEM in
BYOL and MoCo on the transfer accuracy to other classification tasks from
representations trained on ImageNet. We follow the linear evaluation
methodology described in previous works [Grill et al., 2020; Lee et al.,
2021], which entails training a linear classifier on the embeddings of the
samples for each dataset. We perform our transfer learning experiments on the
following datasets: Food [Bossard et al., 2014], CIFAR-10 [Krizhevsky, 2009],
CIFAR-100 [Krizhevsky, 2009], SUN [Xiao et al., 2010], DTD [Cimpoi et al.,
2014], Pets [Parkhi et al., 2012], Flowers [Nilsback and Zisserman, 2008],
CalTech [Fei-Fei et al., 2004] and Cars [Krause et al., 2013].

This task evaluates the generality of the encoder as it has to encode samples
from various out-of-distribution domains with categories that it may not have
seen during training. We present our results in Table 2 and observe that the
SEM improves the transfer accuracy over the baseline for every dataset.

##  5 Conclusion

This work introduces the Simplicial Embeddings (SEM) as a simple and effective
drop-in module for self-supervised learning that leads to representation with
better generalization. Our theoretical insights demonstrate that the
temperature parameter of the SEM allows for control over the trade-off between
the training loss and expressivity on downstream classifiers; we also observe
that controlling the expressivity via the temperature parameter. We validate
our theoretical prediction with a set of controlled experiments. Moreover, we
empirically demonstrate that the SEM improves the in-distribution test
accuracy and out-of-distribution accuracy on several robustness test sets and
transfer learning datasets.

We have also demonstrated that the SEM leads to more semantically relevant
features for predicting the categories of a dataset compared to the baseline
method. Thus, the SEM embedding may be simpler than the un-normalized
embedding, leading to more interpretable representations. We want to study
this in more depth in future works. Related, we would also like to investigate
further why the SEM leads to such representations.

## Acknowledgments and Disclosure of Funding

The authors are grateful for the insightful discussions with Xavier
Bouthillier, Michael Noukhovitch, Hattie Zhou, Sébastien Lachapelle, Yuchen
Lu, Eeshan Dhekane, and Devon Hjelm. We acknowledge funding support from
Samsung and Hitachi, as well as support from Aaron Courville’s CIFAR CCAI
chair. We also wish to acknowledge Mila and Compute Canada for providing the
computing infrastructure that enabled this project. Finally, this project
would not have been possible without the contribution of the following open
source projects: Pytorch [Paszke et al., 2019], Orion [Bouthillier et al.,
2022], Solo-Learn [da Costa et al., 2021], Scikit-Learn [Pedregosa et al.,
2011], and Numpy [Harris et al., 2020].

## References

  * Arjovsky et al. [2020] Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz.  Invariant Risk Minimization.  _arXiv:1907.02893 [cs, stat]_ , March 2020.  URL http://arxiv.org/abs/1907.02893.  arXiv: 1907.02893.
  * Bahdanau et al. [2016] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural Machine Translation by Jointly Learning to Align and Translate.  _arXiv:1409.0473 [cs, stat]_ , May 2016.  URL http://arxiv.org/abs/1409.0473.  arXiv: 1409.0473.
  * Bossard et al. [2014] Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool.  Food-101 – mining discriminative components with random forests.  In David Fleet, Tomas Pajdla, Bernt Schiele, and Tinne Tuytelaars, editors, _Computer Vision – ECCV 2014_ , pages 446–461, Cham, 2014. Springer International Publishing.  ISBN 978-3-319-10599-4.
  * Bottou et al. [2018] Léon Bottou, Frank E. Curtis, and Jorge Nocedal.  Optimization Methods for Large-Scale Machine Learning.  _arXiv:1606.04838 [cs, math, stat]_ , February 2018.  URL http://arxiv.org/abs/1606.04838.  arXiv: 1606.04838.
  * Bouthillier et al. [2022] Xavier Bouthillier, Christos Tsirigotis, François Corneau-Tremblay, Thomas Schweizer, Lin Dong, Pierre Delaunay, Fabrice Normandin, Mirko Bronzi, Dendi Suhubdy, Reyhane Askari, Michael Noukhovitch, Chao Xue, Satya Ortiz-Gagné, Olivier Breuleux, Arnaud Bergeron, Olexa Bilaniuk, Steven Bocco, Hadrien Bertrand, Guillaume Alain, Dmitriy Serdyuk, Peter Henderson, Pascal Lamblin, and Christopher Beckham.  Epistimio/orion: Asynchronous Distributed Hyperparameter Optimization, March 2022.  URL https://doi.org/10.5281/zenodo.3478592.
  * Caron et al. [2019] Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze.  Deep Clustering for Unsupervised Learning of Visual Features.  _arXiv:1807.05520 [cs]_ , March 2019.  URL http://arxiv.org/abs/1807.05520.  arXiv: 1807.05520.
  * Caron et al. [2020] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.  Unsupervised learning of visual features by contrasting cluster assignments.  2020\.
  * Chen et al. [2020a] Tianlong Chen, Sijia Liu, Shiyu Chang, Yu Cheng, Lisa Amini, and Zhangyang Wang.  Adversarial Robustness: From Self-Supervised Pre-Training to Fine-Tuning.  pages 699–708, 2020a.  URL https://openaccess.thecvf.com/content_CVPR_2020/html/Chen_Adversarial_Robustness_From_Self-Supervised_Pre-Training_to_Fine-Tuning_CVPR_2020_paper.html.
  * Chen et al. [2020b] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 1597–1607. PMLR, 13–18 Jul 2020b.
  * Chen and He [2020] Xinlei Chen and Kaiming He.  Exploring simple siamese representation learning.  _arXiv preprint arXiv:2011.10566_ , 2020.
  * Cimpoi et al. [2014] Mircea Cimpoi, Subhransu Maji, Iasonas Kokkinos, Sammy Mohamed, and Andrea Vedaldi.  Describing textures in the wild.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 3606–3613, 2014.
  * da Costa et al. [2021] Victor G. Turrisi da Costa, Enrico Fini, Moin Nabi, Nicu Sebe, and Elisa Ricci.  Solo-learn: A library of self-supervised methods for visual representation learning, 2021.  URL https://github.com/vturrisi/solo-learn.
  * Djolonga et al. [2020] Josip Djolonga, Frances Hubis, Matthias Minderer, Zachary Nado, Jeremy Nixon, Rob Romijnders, Dustin Tran, and Mario Lucic.  Robustness Metrics, 2020.  URL https://github.com/google-research/robustness_metrics.
  * Djolonga et al. [2021] Josip Djolonga, Jessica Yung, Michael Tschannen, Rob Romijnders, Lucas Beyer, Alexander Kolesnikov, Joan Puigcerver, Matthias Minderer, Alexander D’Amour, Dan Moldovan, Sylvain Gelly, Neil Houlsby, Xiaohua Zhai, and Mario Lucic.  On Robustness and Transferability of Convolutional Neural Networks.  _arXiv:2007.08558 [cs]_ , March 2021.  URL http://arxiv.org/abs/2007.08558.  arXiv: 2007.08558.
  * Fei-Fei et al. [2004] Li Fei-Fei, Rob Fergus, and Pietro Perona.  Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories.  In _2004 conference on computer vision and pattern recognition workshop_ , pages 178–178. IEEE, 2004.
  * Graves et al. [2014] Alex Graves, Greg Wayne, and Ivo Danihelka.  Neural Turing Machines.  _arXiv:1410.5401 [cs]_ , December 2014.  URL http://arxiv.org/abs/1410.5401.  arXiv: 1410.5401.
  * Grill et al. [2020] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, Bilal Piot, koray kavukcuoglu, Remi Munos, and Michal Valko.  Bootstrap your own latent - a new approach to self-supervised learning.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 21271–21284. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/f3ada80d5c4ee70142b17b8192b2958e-Paper.pdf.
  * Harris et al. [2020] Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant.  Array programming with NumPy.  _Nature_ , 585(7825):357–362, September 2020\.  doi: 10.1038/s41586-020-2649-2.  URL https://doi.org/10.1038/s41586-020-2649-2.
  * He et al. [2015] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep Residual Learning for Image Recognition.  _arXiv:1512.03385 [cs]_ , December 2015.  URL http://arxiv.org/abs/1512.03385.  arXiv: 1512.03385.
  * He et al. [2020] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum Contrast for Unsupervised Visual Representation Learning.  _arXiv:1911.05722 [cs]_ , March 2020.  URL http://arxiv.org/abs/1911.05722.  arXiv: 1911.05722.
  * Hendrycks and Dietterich [2018] Dan Hendrycks and Thomas Dietterich.  Benchmarking Neural Network Robustness to Common Corruptions and Perturbations.  September 2018.  URL https://openreview.net/forum?id=HJz6tiCqYm.
  * Hendrycks et al. [2021] Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, Dawn Song, Jacob Steinhardt, and Justin Gilmer.  The Many Faces of Robustness: A Critical Analysis of Out-of-Distribution Generalization.  _arXiv:2006.16241 [cs, stat]_ , July 2021.  URL http://arxiv.org/abs/2006.16241.  arXiv: 2006.16241.
  * Hjelm et al. [2019] R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio.  Learning deep representations by mutual information estimation and maximization.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=Bklr3j0cKX.
  * Ioffe and Szegedy [2015] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In Francis Bach and David Blei, editors, _Proceedings of the 32nd International Conference on Machine Learning_ , volume 37 of _Proceedings of Machine Learning Research_ , pages 448–456, Lille, France, 07–09 Jul 2015. PMLR.  URL https://proceedings.mlr.press/v37/ioffe15.html.
  * Khosla et al. [2020] Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan.  Supervised contrastive learning.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 18661–18673. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/d89a66c7c80a29b1bdbab0f2a1a94af8-Paper.pdf.
  * Kolesnikov et al. [2019] Alexander Kolesnikov, Xiaohua Zhai, and Lucas Beyer.  Revisiting self-supervised visual representation learning.  _CoRR_ , abs/1901.09005, 2019.  URL http://arxiv.org/abs/1901.09005.
  * Krause et al. [2013] Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei.  3d object representations for fine-grained categorization.  In _Proceedings of the IEEE international conference on computer vision workshops_ , pages 554–561, 2013.
  * Krizhevsky [2009] Alex Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, 2009.
  * Lee et al. [2021] Kuang-Huei Lee, Anurag Arnab, Sergio Guadarrama, John Canny, and Ian Fischer.  Compressive Visual Representations.  _arXiv:2109.12909 [cs, math]_ , September 2021.  URL http://arxiv.org/abs/2109.12909.  arXiv: 2109.12909.
  * Nilsback and Zisserman [2008] Maria-Elena Nilsback and Andrew Zisserman.  Automated flower classification over a large number of classes.  In _2008 Sixth Indian Conference on Computer Vision, Graphics Image Processing_ , pages 722–729, 2008.  doi: 10.1109/ICVGIP.2008.47.
  * Parkhi et al. [2012] Omkar M Parkhi, Andrea Vedaldi, Andrew Zisserman, and C. V. Jawahar.  Cats and dogs.  In _2012 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 3498–3505, 2012.  doi: 10.1109/CVPR.2012.6248092.
  * Paszke et al. [2019] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems 32_ , pages 8024–8035. Curran Associates, Inc., 2019.  URL http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf.
  * Pedregosa et al. [2011] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  _Journal of Machine Learning Research_ , 12:2825–2830, 2011\.
  * Recht et al. [2019] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar.  Do ImageNet Classifiers Generalize to ImageNet?  In _Proceedings of the 36th International Conference on Machine Learning_ , pages 5389–5400. PMLR, May 2019.  URL https://proceedings.mlr.press/v97/recht19a.html.  ISSN: 2640-3498.
  * Saeed et al. [2020] Aaqib Saeed, David Grangier, and Neil Zeghidour.  Contrastive Learning of General-Purpose Audio Representations.  _arXiv:2010.10915 [cs, eess]_ , October 2020.  URL http://arxiv.org/abs/2010.10915.  arXiv: 2010.10915.
  * van der Vaart and Wellner [1996] Aad W. van der Vaart and Jon A. Wellner.  _Weak Convergence and Empirical Processes_.  Springer New York, 1996.  doi: 10.1007/978-1-4757-2545-2.  URL https://doi.org/10.1007%2F978-1-4757-2545-2.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention Is All You Need.  _arXiv:1706.03762 [cs]_ , December 2017.  URL http://arxiv.org/abs/1706.03762.  arXiv: 1706.03762 version: 5.
  * Wang et al. [2021] Tan Wang, Zhongqi Yue, Jianqiang Huang, Qianru Sun, and Hanwang Zhang.  Self-Supervised Learning Disentangled Group Representation as Feature.  May 2021.  URL https://openreview.net/forum?id=RQfcckT1M_4.
  * Xiao et al. [2010] Jianxiong Xiao, James Hays, Krista A Ehinger, Aude Oliva, and Antonio Torralba.  Sun database: Large-scale scene recognition from abbey to zoo.  In _2010 IEEE computer society conference on computer vision and pattern recognition_ , pages 3485–3492. IEEE, 2010.
  * Ym et al. [2019] Asano Ym, Rupprecht C, and Vedaldi A.  Self-labelling via simultaneous clustering and representation learning.  September 2019.  URL https://openreview.net/forum?id=Hyx-jyBFPr.
  * You et al. [2020] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen.  Graph contrastive learning with augmentations.  _CoRR_ , abs/2010.13902, 2020.  URL https://arxiv.org/abs/2010.13902.
  * Zbontar et al. [2021] Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny.  Barlow twins: Self-supervised learning via redundancy reduction.  _arXiv preprint arXiv:2103.03230_ , 2021.

##  Appendix A Proof of Theorem 1

Let us introduce additional notations used in the proofs. Define
$r=(z,y)\in\mathcal{R}$, $\ell(f,r)=l(f(z),y),$

$\tilde{\mathcal{C}}_{y,k_{1},\dots,k_{L}}=\\{(z,\hat{y})\in\mathcal{Z}\times\mathcal{Y}\mathrel{\mathop{\mathchar
58\relax}}\hat{y}=y,k_{j}=\operatorname*{arg\,max}_{t\in[V]}z_{j,t}\ \ \
\forall j\in[L]\\},$

and

$\tilde{\mathcal{Z}}_{k_{1},\dots,k_{L}}=\\{z\in\mathcal{Z}\mathrel{\mathop{\mathchar
58\relax}}k_{j}=\operatorname*{arg\,max}_{t\in[V]}z_{j,t}\ \ \ \forall
j\in[L]\\}.$

We then define $\mathcal{C}_{k}$ to be the flatten version of
$\tilde{\mathcal{C}}_{y,k_{1},\dots,k_{L}}$; i.e.,
$\\{\mathcal{C}_{k}\\}_{k=1}^{K}=\\{\tilde{\mathcal{C}}_{y,k_{1},\dots,k_{L},y}\\}_{y\in\mathcal{Y},k_{1},\dots,k_{L}\in[V]}$
with $C_{1}=\tilde{\mathcal{C}}_{1,1,\dots,1}$,
$C_{2}=\tilde{\mathcal{C}}_{2,1,\dots,1}$,
$C_{|\mathcal{Y}|}=\tilde{\mathcal{C}}_{|\mathcal{Y}|,1,\dots,1}$,
$C_{|\mathcal{Y}|+1}=\tilde{\mathcal{C}}_{1,2,1,\dots,1}$,
$C_{2|\mathcal{Y}|}=\tilde{\mathcal{C}}_{|\mathcal{Y}|,2,1,\dots,1}$, and so
on. Similarly, define $\mathcal{Z}_{k}$ to be the flatten version of
$\tilde{\mathcal{Z}}_{k_{1},\dots,k_{L}}$. We also use
$\mathcal{Q}_{i}=\\{q\in[-1,+1]^{V}\mathrel{\mathop{\mathchar
58\relax}}i=\operatorname*{arg\,max}_{j\in[V]}q_{j}\\},$
$\mathcal{I}_{k}\mathrel{\mathop{\mathchar
58\relax}}=\mathcal{I}_{k}^{S}\mathrel{\mathop{\mathchar
58\relax}}=\\{i\in[n]\mathrel{\mathop{\mathchar
58\relax}}r_{i}\in\mathcal{C}_{k}\\},$ and
$\alpha_{k}(h)\mathrel{\mathop{\mathchar
58\relax}}=\mathbb{E}_{r}[\ell(h,r)|r\in\mathcal{C}_{k}].$ Moreover, we define
$\varphi(f_{\mathrm{base}}^{S})=\sup_{i\in[V]}\sup_{q,q^{\prime}\in
Q_{i}}\sum_{t=1}^{n}\|q-q^{\prime}\|_{2}^{2},$ and
$\varphi(f_{\mathrm{SEM}(\tau)}^{S})=\sup_{i\in[V]}\sup_{q,q^{\prime}\in
Q_{i}}\sum_{t=1}^{n}\|\sigma_{\tau}(q)-\sigma_{\tau}(q^{\prime})\|_{2}^{2}$
where
$\sigma_{\tau}(q)_{j}=\frac{e^{q_{j}/\tau}}{\sum_{t=1}^{V}e^{q_{t}/\tau}}$ for
$j=1,\dots,V$.

We first decompose the generalization gap into two terms using the following
lemma:

######  Lemma 1.

For any $\delta>0$, with probability at least $1-\delta$,the following holds
for all $h\in\mathcal{H}$:

$\displaystyle\mathbb{E}_{r}[\ell(h,r)]-\frac{1}{n}\sum_{i=1}^{n}\ell(h,r_{i})\leq\frac{1}{n}\sum_{k=1}^{K}|\mathcal{I}_{k}|\left(\alpha_{k}(h)-\frac{1}{|\mathcal{I}_{k}|}\sum_{i\in\mathcal{I}_{k}}\ell(h,r_{i})\right)+c\sqrt{\frac{\ln(2/\delta)}{n}}.$

###### Proof.

We first write the expected error as the sum of the conditional expected
error:

$\displaystyle\mathbb{E}_{r}[\ell(h,r)]$
$\displaystyle=\sum_{k=1}^{K}\mathbb{E}_{r}[\ell(h,r)|r\in\mathcal{C}_{k}]\Pr(r\in\mathcal{C}_{k})=\sum_{k=1}^{K}\mathbb{E}_{r_{k}}[\ell(h,r_{k})]\Pr(r\in\mathcal{C}_{k}),$

where $r_{k}$ is the random variable for the conditional with
$r\in\mathcal{C}_{k}$. Using this, we decompose the generalization error into
two terms:

$\displaystyle\mathbb{E}_{r}[\ell(h,r)]-\frac{1}{n}\sum_{i=1}^{n}\ell(h,r_{i})$
(5)
$\displaystyle=\sum_{k=1}^{K}\mathbb{E}_{r_{k}}[\ell(h,r_{k})]\left(\Pr(r\in\mathcal{C}_{k})-\frac{|\mathcal{I}_{k}|}{n}\right)+\left(\sum_{k=1}^{K}\mathbb{E}_{r_{k}}[\ell(h,r_{k})]\frac{|\mathcal{I}_{k}|}{n}-\frac{1}{n}\sum_{i=1}^{n}\ell(h,r_{i})\right).$

The second term in the right-hand side of (5) is further simplified by using

$\frac{1}{n}\sum_{i=1}^{n}\ell(h,r_{i})=\frac{1}{n}\sum_{k=1}^{K}\sum_{i\in\mathcal{I}_{k}}\ell(h,r_{i}),$

as

$\displaystyle\sum_{k=1}^{K}\mathbb{E}_{r_{k}}[\ell(h,r_{k})]\frac{|\mathcal{I}_{k}|}{n}-\frac{1}{n}\sum_{i=1}^{n}\ell(h,r_{i})$
$\displaystyle=\frac{1}{n}\sum_{k=1}^{K}|\mathcal{I}_{k}|\left(\mathbb{E}_{r_{k}}[\ell(h,r_{k})]-\frac{1}{|\mathcal{I}_{k}|}\sum_{i\in\mathcal{I}_{k}}\ell(h,r_{i})\right)\
$

Substituting these into equation (5) yields

$\displaystyle\mathbb{E}_{r}[\ell(h,r)]-\frac{1}{n}\sum_{i=1}^{n}\ell(h,r_{i})$
(6)
$\displaystyle=\sum_{k=1}^{K}\mathbb{E}_{r_{k}}[\ell(h,r_{k})]\left(\Pr(r\in\mathcal{C}_{k})-\frac{|\mathcal{I}_{k}|}{n}\right)+\frac{1}{n}\sum_{k=1}^{K}|\mathcal{I}_{k}|\left(\mathbb{E}_{r_{k}}[\ell(h,r_{k})]-\frac{1}{|\mathcal{I}_{k}|}\sum_{i\in\mathcal{I}_{k}}\ell(h,r_{i})\right)$
$\displaystyle\leq
B\sum_{k=1}^{K}\left|\Pr(r\in\mathcal{C}_{k})-\frac{|\mathcal{I}_{k}|}{n}\right|+\frac{1}{n}\sum_{k=1}^{K}|\mathcal{I}_{k}|\left(\mathbb{E}_{r_{k}}[\ell(h,r_{k})]-\frac{1}{|\mathcal{I}_{k}|}\sum_{i\in\mathcal{I}_{k}}\ell(h,r_{i})\right)$

By using the Bretagnolle-Huber-Carol inequality [van der Vaart and Wellner,
1996, A6.6 Proposition], we have that for any $\delta>0$, with probability at
least $1-\delta$,

$\displaystyle\sum_{k=1}^{K}\left|\Pr(r\in\mathcal{C}_{k})-\frac{|\mathcal{I}_{k}|}{n}\right|\leq\sqrt{\frac{2K\ln(2/\delta)}{n}}.$
(7)

Here, notice that the term of
$\sum_{k=1}^{K}\left|\Pr(r\in\mathcal{C}_{k})-\frac{|\mathcal{I}_{k}|}{n}\right|$
does not depend on $h\in\mathcal{H}$. Moreover, note that for any $(f,h,M)$
such that $M>0$ and $B\geq 0$ for all $X$, we have that $\mathbb{P}(f(X)\geq
M)\geq\mathbb{P}(f(X)>M)\geq\mathbb{P}(Bf(X)+h(X)>BM+h(X)),$ where the
probability is with respect to the randomness of $X$. Thus, by combining (6)
and (7), we have that for any $h\in\mathcal{H}$, for any $\delta>0$, with
probability at least $1-\delta$, the following holds for all
$h\in\mathcal{H}$,

$\displaystyle\mathbb{E}_{r}[\ell(h,r)]-\frac{1}{n}\sum_{i=1}^{n}\ell(h,r_{i})$
$\displaystyle\leq\frac{1}{n}\sum_{k=1}^{K}|\mathcal{I}_{k}|\left(\alpha_{k}(h)-\frac{1}{|\mathcal{I}_{k}|}\sum_{i\in\mathcal{I}_{k}}\ell(h,r_{i})\right)+c\sqrt{\frac{\ln(2/\delta)}{n}}.$

∎

In particular, the first term from the previous lemma will be bounded with the
following lemma:

######  Lemma 2.

For any $f\in\\{f_{\mathrm{SEM}(\tau)}^{S},f_{\mathrm{base}}^{S}\\}$,

$\frac{1}{n}\sum_{k=1}^{K}|\mathcal{I}_{k}|\left(\alpha_{k}(f)-\frac{1}{|\mathcal{I}_{k}|}\sum_{i\in\mathcal{I}_{k}}\ell(f,r_{i})\right)\leq
R\sqrt{\frac{L\varphi(f)}{n}}.$

###### Proof.

By using the triangle inequality,

$\displaystyle\frac{1}{n}\sum_{k=1}^{K}|\mathcal{I}_{k}|\left(\mathbb{E}_{r}[\ell(f,r)|r\in\mathcal{C}_{k}]-\frac{1}{|\mathcal{I}_{k}|}\sum_{i\in\mathcal{I}_{k}}\ell(f,r_{i})\right)$
$\displaystyle\leq\frac{1}{n}\sum_{k=1}^{K}|\mathcal{I}_{k}|\left|\mathbb{E}_{r}[\ell(f,r)|r\in\mathcal{C}_{k}]-\frac{1}{|\mathcal{I}_{k}|}\sum_{i\in\mathcal{I}_{k}}\ell(f,r_{i})\right|.$

Furthermore, by using the triangle inequality,

$\displaystyle\left|\mathbb{E}_{r}[\ell(f,r)|r\in\mathcal{C}_{k}]-\frac{1}{|\mathcal{I}_{k}|}\sum_{i\in\mathcal{I}_{k}}\ell(f,r_{i})\right|$
$\displaystyle=\left|\frac{1}{|\mathcal{I}_{k}|}\sum_{i\in\mathcal{I}_{k}}\mathbb{E}_{r}[\ell(f,r)|r\in\mathcal{C}_{k}]-\frac{1}{|\mathcal{I}_{k}|}\sum_{i\in\mathcal{I}_{k}}\ell(f,r_{i})\right|$
$\displaystyle\leq\frac{1}{|\mathcal{I}_{k}|}\sum_{i\in\mathcal{I}_{k}}\left|\mathbb{E}_{r}[\ell(f,r)|r\in\mathcal{C}_{k}]-\ell(f,r_{i})\right|$
$\displaystyle\leq\sup_{r,r^{\prime}\in\mathcal{C}_{k}}\left|\ell(f,r)-\ell(f,r^{\prime})\right|.$

If
$f=f_{\mathrm{SEM}(\tau)}^{S}=g^{S}_{\mathrm{SEM}(\tau)}\circ\sigma_{\tau}$,
since $g^{S}_{\mathrm{SEM}(\tau)}\in\mathcal{G}_{S}$, by using the Lipschitz
continuity, boundedness, and non-negativity,

$\displaystyle\sup_{r,r^{\prime}\in\mathcal{C}_{k}}\left|\ell(f,r)-\ell(f,r^{\prime})\right|$
$\displaystyle=\sup_{y\in\mathcal{Y}}\sup_{z,z^{\prime}\in\mathcal{Z}_{k}}|(l_{y}\circ
g^{S}_{\mathrm{SEM}(\tau)})(\sigma_{\tau}(z))-(l_{y}\circ
g^{S}_{\mathrm{SEM}(\tau)})(\sigma_{\tau}(z^{\prime}))|$ $\displaystyle\leq
R\sup_{z,z^{\prime}\in\mathcal{Z}_{k}}\|\sigma_{\tau}(z)-\sigma_{\tau}(z^{\prime})\|_{F}$
$\displaystyle=R\sup_{z,z^{\prime}\in\mathcal{Z}_{k}}\sqrt{\sum_{t=1}^{L}\sum_{j=1}^{V}(\sigma_{\tau}(z_{t,j})-\sigma_{\tau}(z^{\prime}_{t,j}))_{2}^{2}}$
$\displaystyle\leq R\sqrt{\sum_{t=1}^{L}\sup_{i\in[V]}\sup_{q,q^{\prime}\in
Q_{i}}\|\sigma_{\tau}(q)-\sigma_{\tau}(q^{\prime})\|_{2}^{2}}$
$\displaystyle=R\sqrt{\frac{L\varphi(f_{\mathrm{SEM}(\tau)}^{S})}{n}}$

Similarly, if $f=f_{\mathrm{base}}^{S}=g^{S}_{\mathrm{base}}$, since
$g^{S}_{\mathrm{base}}\in\mathcal{G}_{S}$, by using the Lipschitz continuity,
boundedness, and non-negativity,

$\displaystyle\sup_{r,r^{\prime}\in\mathcal{C}_{k}}\left|\ell(f,r)-\ell(f,r^{\prime})\right|$
$\displaystyle=\sup_{y\in\mathcal{Y}}\sup_{z,z^{\prime}\in\mathcal{Z}_{k}}|(l_{y}\circ
g^{S}_{\mathrm{base}})(z)-(l_{y}\circ g^{S}_{\mathrm{base}})(z^{\prime})|$
$\displaystyle\leq R\sup_{z,z^{\prime}\in\mathcal{Z}_{k}}\|z-z^{\prime}\|_{F}$
$\displaystyle\leq R\sqrt{\frac{L\varphi(f_{\mathrm{base}}^{S})}{n}}.$

Therefore, for any
$f\in\\{f_{\mathrm{SEM}(\tau)}^{S},f_{\mathrm{base}}^{S}\\}$,

$\frac{1}{n}\sum_{k=1}^{K}|\mathcal{I}_{k}|\left(\alpha_{k}(f)-\frac{1}{|\mathcal{I}_{k}|}\sum_{i\in\mathcal{I}_{k}}\ell(f,r_{i})\right)\leq\frac{1}{n}\sum_{k=1}^{K}|\mathcal{I}_{k}|R\sqrt{L\varphi(f)}=R\sqrt{\frac{L\varphi(f)}{n}}.$

∎

Combining Lemma 1 and Lemma 2, we obtain the following upper bound on the gap:

######  Lemma 3.

For any $\delta>0$, with probability at least $1-\delta$,the following holds
for any $f\in\\{f_{\mathrm{SEM}(\tau)}^{S},f_{\mathrm{base}}^{S}\\}$:

$\displaystyle\mathbb{E}_{r}[\ell(f,r)]-\frac{1}{n}\sum_{i=1}^{n}\ell(f,r_{i})\leq
R\sqrt{\frac{L\varphi(f)}{n}}+c\sqrt{\frac{\ln(2/\delta)}{n}}.$

###### Proof.

This follows directly from combining Lemma 1 and Lemma 2. ∎

We now provide an upper bound on $\varphi(f_{\mathrm{SEM}(\tau)}^{S})$ in the
following lemma:

######  Lemma 4.

For any $\tau>0$,

$\displaystyle\frac{\varphi(f_{\mathrm{SEM}(\tau)}^{S})}{n}$
$\displaystyle\leq\left|\frac{1}{1+(V-1)e^{-2/\tau}}-\frac{1}{1+(V-1)e^{-\Delta/\tau}}\right|^{2}$
$\displaystyle\qquad+(V-1)\left|\frac{1}{1+e^{\Delta/\tau}(1+(V-2)e^{-2/\tau})}-\frac{1}{1+e^{2/\tau}(1+(V-2)e^{-\Delta/\tau})}\right|^{2}.$

###### Proof.

Recall the definition:

$\frac{\varphi(f_{\mathrm{SEM}(\tau)}^{S})}{n}=\sup_{i\in[V]}\sup_{q,q^{\prime}\in
Q_{i}}\|\sigma_{\tau}(q)-\sigma_{\tau}(q^{\prime})\|_{2}^{2}.$

where

$\sigma_{\tau}(q)_{j}=\frac{e^{q_{j}/\tau}}{\sum_{t=1}^{V}e^{q_{t}/\tau}},$

for $j=1,\dots,V$. By the symmetry and independence over $i\in[V]$ inside of
the first supremum, we have

$\frac{\varphi(f_{\mathrm{SEM}(\tau)}^{S})}{n}=\sup_{q,q^{\prime}\in
Q_{1}}\|\sigma_{\tau}(q)-\sigma_{\tau}(q^{\prime})\|_{2}^{2}.$

For any $q,q^{\prime}\in Q_{1}$ and $i\in\\{2,\dots,V\\}$ (with
$q=(q_{1},\dots,q_{V})$ and
$q^{\prime}=(q_{1}^{\prime},\dots,q_{V}^{\prime})$), there exists
$\delta_{i},\delta_{i}^{\prime}>0$ such that

$q_{i}=q_{1}-\delta_{i}$

and

$q_{i}^{\prime}=q_{1}^{\prime}-\delta_{i}^{\prime}.$

Here, since $z_{ik}-\Delta\geq z_{ij}$ from the assumption, we have that for
all $i\in\\{2,\dots,V\\}$,

$\delta_{i},\delta^{\prime}_{i}\geq\Delta>0.$

Thus, we can rewrite

$\displaystyle\sum_{t=1}^{V}e^{q_{t}/\tau}$
$\displaystyle=e^{q_{1}/\tau}+\sum_{i=2}^{V}e^{(q_{1}-\delta_{i})/\tau}$
$\displaystyle=e^{q_{1}/\tau}+e^{q_{1}/\tau}\sum_{i=2}^{V}e^{-\delta_{i}/\tau}$
$\displaystyle=e^{q_{1}/\tau}\left(1+\sum_{i=2}^{V}e^{-\delta_{i}/\tau}\right)$

Similarly,

$\displaystyle\sum_{t=1}^{V}e^{q_{t}^{\prime}/\tau}=e^{q_{1}^{\prime}/\tau}\left(1+\sum_{i=2}^{V}e^{-\delta_{i}^{\prime}/\tau}\right).$

Using these,

$\sigma_{\tau}(q)_{1}=\frac{e^{q_{1}/\tau}}{\sum_{t=1}^{V}e^{q_{t}/\tau}}=\frac{e^{q_{1}/\tau}}{e^{q_{1}/\tau}\left(1+\sum_{i=2}^{V}e^{-\delta_{i}/\tau}\right)}=\frac{1}{1+\sum_{i=2}^{V}e^{-\delta_{i}/\tau}}$

and for all $j\in\\{2,\dots,V\\}$,

$\displaystyle\sigma_{\tau}(q)_{j}$
$\displaystyle=\frac{e^{q_{j}/\tau}}{\sum_{t=1}^{V}e^{q_{t}/\tau}}$
$\displaystyle=\frac{e^{(q_{1}-\delta_{j})/\tau}}{e^{q_{1}/\tau}\left(1+\sum_{i=2}^{V}e^{-\delta_{i}/\tau}\right)}$
$\displaystyle=\frac{e^{-\delta_{j}/\tau}}{1+\sum_{i=2}^{V}e^{-\delta_{i}/\tau}}$
$\displaystyle=\frac{1}{1+e^{\delta_{j}/\tau}+\sum_{i\in
I_{j}}^{V}e^{(\delta_{j}-\delta_{i})/\tau}}$

where $I_{j}\mathrel{\mathop{\mathchar
58\relax}}=\\{2,\dots,V\\}\setminus\\{j\\}$. Similarly,

$\sigma_{\tau}(q^{\prime})_{1}=\frac{1}{1+\sum_{i=2}^{V}e^{-\delta_{i}^{\prime}/\tau}},$

and for all $j\in\\{2,\dots,V\\}$,

$\sigma_{\tau}(q^{\prime})_{j}=\frac{1}{1+e^{\delta_{j}^{\prime}/\tau}+\sum_{i\in
I_{j}}^{V}e^{(\delta_{j}^{\prime}-\delta_{i}^{\prime})/\tau}}.$

Using these, for any $q,q^{\prime}\in Q_{1}$,

$\displaystyle|\sigma_{\tau}(q)_{1}-\sigma_{\tau}(q^{\prime})_{1}|$
$\displaystyle=\left|\frac{1}{1+\sum_{i=2}^{V}e^{-\delta_{i}/\tau}}-\frac{1}{1+\sum_{i=2}^{V}e^{-\delta_{i}^{\prime}/\tau}}\right|$
$\displaystyle\leq\left|\frac{1}{1+\sum_{i=2}^{V}e^{-2/\tau}}-\frac{1}{1+\sum_{i=2}^{V}e^{-\Delta/\tau}}\right|$
$\displaystyle=\left|\frac{1}{1+(V-1)e^{-2/\tau}}-\frac{1}{1+(V-1)e^{-\Delta/\tau}}\right|,$

and for all $j\in\\{2,\dots,V\\}$,

$\displaystyle|\sigma_{\tau}(q)_{j}-\sigma_{\tau}(q^{\prime})_{j}|$
$\displaystyle=\left|\frac{1}{1+e^{\delta_{j}/\tau}+\sum_{i\in
I_{j}}^{V}e^{(\delta_{j}-\delta_{i})/\tau}}-\frac{1}{1+e^{\delta_{j}^{\prime}/\tau}+\sum_{i\in
I_{j}}^{V}e^{(\delta_{j}^{\prime}-\delta_{i}^{\prime})/\tau}}\right|$
$\displaystyle\leq\left|\frac{1}{1+e^{\Delta/\tau}+\sum_{i\in
I_{j}}^{V}e^{(\Delta-2)/\tau}}-\frac{1}{1+e^{2/\tau}+\sum_{i\in
I_{j}}^{V}e^{(2-\Delta)/\tau}}\right|$
$\displaystyle=\left|\frac{1}{1+e^{\Delta/\tau}+(V-2)e^{(\Delta-2)/\tau}}-\frac{1}{1+e^{2/\tau}+(V-2)e^{(2-\Delta)/\tau}}\right|$
$\displaystyle=\left|\frac{1}{1+e^{\Delta/\tau}(1+(V-2)e^{-2/\tau})}-\frac{1}{1+e^{2/\tau}(1+(V-2)e^{-\Delta/\tau})}\right|.$

By combining these,

$\displaystyle\sup_{q,q^{\prime}\in
Q_{1}}\|\sigma_{\tau}(q)-\sigma_{\tau}(q^{\prime})\|_{2}^{2}$
$\displaystyle=\sup_{q,q^{\prime}\in
Q_{1}}\sum_{j=1}^{V}|\sigma_{\tau}(q)_{j}-\sigma_{\tau}(q^{\prime})_{j}|^{2}$
$\displaystyle\leq\left|\frac{1}{1+(V-1)e^{-2/\tau}}-\frac{1}{1+(V-1)e^{-\Delta/\tau}}\right|^{2}$
$\displaystyle\qquad+(V-1)\left|\frac{1}{1+e^{\Delta/\tau}(1+(V-2)e^{-2/\tau})}-\frac{1}{1+e^{2/\tau}(1+(V-2)e^{-\Delta/\tau})}\right|^{2}.$

∎

Using the previous lemma, we will conclude the asymptotic behavior of
$\varphi(f_{\mathrm{SEM}(\tau)}^{S})$ in the following lemma:

######  Lemma 5.

It holds that

$\displaystyle\varphi(f_{\mathrm{SEM}(\tau)}^{S})\rightarrow 0\text{ as
}\tau\rightarrow 0.$

###### Proof.

Using Lemma 4,

$\displaystyle\lim_{\tau\rightarrow 0}\varphi(f_{\mathrm{SEM}(\tau)}^{S})$
$\displaystyle\leq\lim_{\tau\rightarrow
0}n\left|\frac{1}{1+(V-1)e^{-2/\tau}}-\frac{1}{1+(V-1)e^{-\Delta/\tau}}\right|^{2}$
$\displaystyle\qquad+n(V-1)\lim_{\tau\rightarrow
0}\left|\frac{1}{1+e^{\Delta/\tau}(1+(V-2)e^{-2/\tau})}-\frac{1}{1+e^{2/\tau}(1+(V-2)e^{-\Delta/\tau})}\right|^{2}.$

Moreover,

$\lim_{\tau\rightarrow
0}\left|\frac{1}{1+(V-1)e^{-2/\tau}}-\frac{1}{1+(V-1)e^{-\Delta/\tau}}\right|^{2}=\left|\frac{1}{1}-\frac{1}{1}\right|^{2}=0,$

and

$\lim_{\tau\rightarrow
0}\left|\frac{1}{1+e^{\Delta/\tau}(1+(V-2)e^{-2/\tau})}-\frac{1}{1+e^{2/\tau}(1+(V-2)e^{-\Delta/\tau})}\right|^{2}=\left|0-0\right|^{2}=0.$

Therefore,

$\lim_{\tau\rightarrow 0}\varphi(f_{\mathrm{SEM}(\tau)}^{S})\leq 0.$

Since $\varphi(f_{\mathrm{SEM}(\tau)}^{S})\geq 0$, this implies the statement
of this lemma. ∎

As we have analyzed $\varphi(f_{\mathrm{SEM}(\tau)}^{S})$ in the previous two
lemmas, we are now ready to compare $\varphi(f_{\mathrm{SEM}(\tau)}^{S})$ and
$\varphi(f_{\mathrm{base}}^{S})$, which is done in the following lemma:

######  Lemma 6.

For any $\tau>0$,

$\varphi(f_{\mathrm{SEM}(\tau)}^{S})-\varphi(f_{\mathrm{base}}^{S})\leq\frac{3n}{4}(1-V)<0.$

###### Proof.

From Lemma 4, for any $\tau>0$,

$\displaystyle\varphi(f_{\mathrm{SEM}(\tau)}^{S})$ $\displaystyle\leq
n\left|\frac{1}{1+(V-1)e^{-2/\tau}}-\frac{1}{1+(V-1)e^{-\Delta/\tau}}\right|^{2}$
$\displaystyle\qquad+n(V-1)\left|\frac{1}{1+e^{\Delta/\tau}(1+(V-2)e^{-2/\tau})}-\frac{1}{1+e^{2/\tau}(1+(V-2)e^{-\Delta/\tau})}\right|^{2}$
$\displaystyle\leq
n\left|\frac{1}{1+(V-1)e^{-2/\tau}}-\frac{1}{1+(V-1)}\right|^{2}$
$\displaystyle\qquad+n(V-1)\left|\frac{1}{1+(1+(V-2)e^{-2/\tau})}-\frac{1}{1+e^{2/\tau}(1+(V-2))}\right|^{2}$
$\displaystyle=n\left|\frac{1}{1+(V-1)e^{-2/\tau}}-\frac{1}{V}\right|^{2}+n(V-1)\left|\frac{1}{2+(V-2)e^{-2/\tau}}-\frac{1}{1+e^{2/\tau}(V-1)}\right|^{2}$
$\displaystyle\leq
n\left|\frac{1}{1}-\frac{1}{V}\right|^{2}+n(V-1)\left|\frac{1}{2}-0\right|^{2}$
$\displaystyle=n\left(\frac{1}{1}-\frac{1}{V}\right)^{2}+n(V-1)\frac{1}{4}.$

Recall the definition of

$\varphi(f_{\mathrm{base}}^{S})=\sup_{i\in[V]}\sup_{q,q^{\prime}\in
Q_{i}}n\|q-q^{\prime}\|_{2}^{2}.$

By choosing an element in the set over which the supremum is taken, for any
$\delta\geq\Delta>0$,

$\varphi(f_{\mathrm{base}}^{S})\geq\sup_{q,q^{\prime}\in
Q_{1}}n\|q-q^{\prime}\|_{2}^{2}\geq
n\|\hat{q}-\hat{q}^{\prime}\|_{2}^{2}=n\sum_{j=1}^{V}(\hat{q}_{j}-\hat{q}^{\prime}_{j})_{2}^{2}=n(2-\delta)^{2}V,$

where $\hat{q}_{1}=1$, $\hat{q}_{j}=1-\delta$ for $j\in\\{2,\dots,V\\}$,
$\hat{q}_{1}^{\prime}=\delta-1$, and $\hat{q}_{j}^{\prime}=-1$ for
$j\in\\{2,\dots,V\\}$.

By combining those, for for any $\tau>0$ and $\delta\geq\Delta>0$,

$\displaystyle\frac{\varphi(f_{\mathrm{SEM}(\tau)}^{S})-\varphi(f_{\mathrm{base}}^{S})}{n}$
$\displaystyle\leq\left(\frac{1}{1}-\frac{1}{V}\right)^{2}+(V-1)\frac{1}{4}-(2-\delta)^{2}V$
$\displaystyle\leq 1+\frac{1}{4}V-\frac{1}{4}-(2-\delta)^{2}V$
$\displaystyle=\frac{3}{4}+\frac{1}{4}V-(2-\delta)^{2}V$
$\displaystyle=\frac{3}{4}-V\left((2-\delta)^{2}-\frac{1}{4}\right)$
$\displaystyle\leq\frac{3}{4}-V\left(1-\frac{1}{4}\right)$
$\displaystyle=\frac{3}{4}(1-V)$

∎

We combine the lemmas above to prove Theorem 1, which is restated below with
its proof:

See 1

###### Proof.

The first statement directly follows from Lemma 3. The second statement is
proven by Lemma 5 and Lemma 6. ∎

##  Appendix B Hyperparameters

We present the hype-parameters used to train for BYOL+SEM on CIFAR100. The
same parameters were used for ResNet18 and ResNet50.

Learning rate | 0.5
---|---
Weight-decay | 1e-4
Optimizer | AdamW
BYOL EMA | 0.99
Vocabulary size (V) | 13
Message length (L) | 5000
$\tau$ online network | 0.5
$\tau$ target network | 0.5
(a) BYOL+SEM hyper-parameters.

##  Appendix C Experiment details for ImageNet

###  C.1 Image augmentation

We follow the same procedure as [Grill et al., 2020] for the image
augmentation procedure. The augmentation applied in order during training are:

  * •

Random Resize crop to a $224\times 224$ image. A random patch of the image is
selected and resized to a $224\times 224$ image.

  * •

Random color jitter. Modifying the brightness, the contrast, the saturation
and the hue.

  * •

Random gray scale. Randomly applying a gray scale filter to the image

  * •

Random gaussian blur. Randomly applying a gaussian blue filter.

  * •

Random solarization. Randomly applying a solarization filter.

At validation and test time, we resize the images to $256\times 256$ and then
center crop a patch of $224\times 224$.

For both training and evaluation, we re-normalize the image using the
statistic of the training set.

###  C.2 Hyper-parameters

We summarize the hyper-parameters for BYOL with SEM and MoCo with SEM in table
4.

Learning rate | 0.9
---|---
Batch size | 256
Weight-decay | 1e-6
Optimizer | SGD with lars
Epochs | 100
Base momentum | 0.99
Vocabulary size (V) | 29
Message length (L) | 465
$\tau$ online network | 2.397
$\tau$ target network | 2.386
(a) BYOL+SEM hyper-parameters.

Learning rate | 0.6
---|---
Batch size | 256
Weight-decay | 3e-5
Optimizer | SGD with lars
Epochs | 100
MoCo’s EMA | 0.1
Vocabulary size (V) | 12
Message Length (L) | 512
$\tau$ online network | 1.35
$\tau$ target network | 1.2
(b) MoCo+SEM hyper-parameters.

Table 4: ImageNet’s experiment hyper-parameters.

###  C.3 Linear evaluation

We follow the evaluation protocol from [Chen et al., 2020b]. The linear
evaluation is done by training a linear classifier on the frozen
representation of the ImageNet training samples. We train a linear classifier
with a cross-entropy objective for 100 epochs using SGD with nesterov and a
batch size of 512. During training, we apply random resized crop and random
horizontal flip.

###  C.4 Semi-supervised learning

We perform semi-supervised experiments by training a linear classifier on top
of a frozen representation. The procedure is the same as the linear evaluation
procedure with the exception that we train with $1\%$ of the training sample.
That training samples are taken according to the split defined in [Chen et
al., 2020b].

###  C.5 Robustness experiments

We follow the evaluation procedure from [Lee et al., 2021]. We treated the
robustness datasets as additional "test sets" in that we simply evaluated them
using the evaluation procedure described above. The images were resized to a
$256\times 256$ before being center cropped to a $224\times 224$ image. The
evaluation procedure was performed using the public robustness benchmark
evaluation code of [Djolonga et al., 2020]222https://github.com/google-
research/robustness_metrics.

###  C.6 Transfer learning experiments

We follow the linear evaluation protocol of [Kolesnikov et al., 2019; Chen et
al., 2020b] We train a linear classifier using a regularized multinomial
logistic regression from the scikit-learn package [Pedregosa et al., 2011].
The representation is frozen, so that we do not train the encoder backbone nor
the batch-normalization statistics. We do not perform any augmentations and
the images are resized to 224 pixels using bicubic resampling and the
normalized using the statistics on ImageNet’s training set. We tune the
regularizer term from a range of 11 logarithmically-spaced values between
$10^{-6}$ and $10^{5}$ using a small validation set and re-train using the
full training set.

##  Appendix D CIFAR100 superclass

The 100 classes of CIFAR-100 [Krizhevsky, 2009] are grouped into 20
superclasses. The list of superclass for each class in Table 5

Superclass | Classes
---|---
aquatic mammals | beaver, dolphin, otter, seal, whale
fish | aquarium fish, flatfish, ray, shark, trout
flowers | orchids, poppies, roses, sunflowers, tulips
food containers | bottles, bowls, cans, cups, plates
fruit and vegetables | apples, mushrooms, oranges, pears, sweet peppers
household electrical devices | clock, computer keyboard, lamp, telephone, television
household furniture | bed, chair, couch, table, wardrobe
insects | bee, beetle, butterfly, caterpillar, cockroach
large carnivores | bear, leopard, lion, tiger, wolf
large man-made outdoor things | bridge, castle, house, road, skyscraper
large natural outdoor scenes | cloud, forest, mountain, plain, sea
large omnivores and herbivores | camel, cattle, chimpanzee, elephant, kangaroo
medium-sized mammals | fox, porcupine, possum, raccoon, skunk
non-insect invertebrates | crab, lobster, snail, spider, worm
people | baby, boy, girl, man, woman
reptiles | crocodile, dinosaur, lizard, snake, turtle
small mammals | hamster, mouse, rabbit, shrew, squirrel
trees | maple, oak, palm, pine, willow
vehicles 1 | bicycle, bus, motorcycle, pickup truck, train
vehicles 2 | lawn-mower, rocket, streetcar, tank, tractor
Table 5: Set of classes for each superclass on CIFAR-100.

##  Appendix E Additional CIFAR-100 relevance graphs

(a) BYOL baseline

(b) BYOL baseline with a large representation

(c) BYOL + SEM

Figure 5: Comparison of the full relevance graph $\mathcal{W}_{5}$ between
BYOL and BYOL + SEM.