Self-supervised Learning is More Robust to Dataset Imbalance
Authors: Hong Liu
Jeff Z. HaoChen
Adrien Gaidon
Tengyu Ma
Venue: ICLR 2022 Spotlight (2022)
Keywords: self-supervised learning
dataset imbalance
representation learning
long-tailed recognition

Abstract: Self-supervised learning (SSL) is a scalable way to learn general visual representations since it learns without labels. However, large-scale unlabeled datasets in the wild often have long-tailed label distributions, where we know little about the behavior of SSL. In this work, we systematically investigate self-supervised learning under dataset imbalance. First, we find via extensive experiments that off-the-shelf self-supervised representations are already more robust to class imbalance than supervised representations. The performance gap between balanced and imbalanced pre-training with SSL is significantly smaller than the gap with supervised learning, across sample sizes, for both in-domain and, especially, out-of-domain evaluation. Second, towards understanding the robustness of SSL, we hypothesize that SSL learns richer features from frequent data: it may learn label-irrelevant-but-transferable features that help classify the rare classes and downstream tasks. In contrast, supervised learning has no incentive to learn features irrelevant to the labels from frequent examples. We validate this hypothesis with semi-synthetic experiments as well as rigorous mathematical analyses on a simplified setting. Third, inspired by the theoretical insights, we devise a re-weighted regularization technique that  consistently improves the SSL representation quality on imbalanced datasets with several evaluation criteria, closing the small gap between balanced and imbalanced datasets with the same number of examples.

Published as a conference paper at ICLR 2022
SELF-SUPERVISED LEARNING IS MORE ROBUST TO
DATASET IMBALANCE
Hong Liu Stanford University h1 h1lus9@stanford.ceem edu
Jeff Z. HaoChen Stanford University Shaochen@stannoord..o
Adrien Gaidon
Tengyu Ma
Toyota Research Institute adrien. gaidon@tri... globall
Stanford University
tengy:ma@stanfford.ccm
ABSTRACT
Self-supervised learning (SSL) is scalable way to learn general visual represen- tations since it learns without labels. However, large-scale unlabeled datasets the wild often have long-tailed label distributions, where we know little about the behavior SSL. this work, we systematically investigate self-supervised learning under dataset imbalance. First, we find out via extensive experiments that off-the-shelf self-supervised representations are already more robust to class imbalance than supervised representations. The performance gap between bal- anced and imbalanced pre-training with SSL is significantly smaller than the gap with supervised learning, out-of-domann evaluation. Second, towards understanding the robustness of SSL, we hypothesize that SSL learns richer features from frequent data: it may learn wew--rreeeeaan----ttrssf-eeeeeee
sample sizes, for both in-domain and, especially,
features that help classify the rare classes and downstream tasks. contrast, supervised learning has no incentive learn fea- tures irrelevant to the labels from frequent examples. We validate this hypothesis with semi-synthetic experiments and theoretical analyses on simplified setting. Third, inspired by the theoretical insights, we devise re-weighted regularization technique that consistently improves the SSL representation quality on imbalanced datasets with several evaluation criteria, closing the small gap between balanced and imbalanced datasets with the same number of examples.
INTRODUCTION
Self Self-supervised learning (SSL) is an important paradigm of machine learning, because it can lever- age the availability of large-scale unlabeled datasets to learn representations for a wide range of downstream tasks and datasets (He et al., 2020; Chen al., 2020; Grill et al., 2020; Caron al., 2020; Chen & He, 2021). Current SSL algorithms are mostly trained on curated, balanced datasets, but large-scale unlabeled datasets the wild are inevitably imbalanced with a long-tailed label distribution (Reed, 2001; Liu et al., 2019). Curating a blass-bllanced unlabeled dataset requires the knowledge of labels, which defeats the purpose of leveraging unlabeled data by SSL.
The behavior of SSL algorithms under dataset imbalance remains largely underexplored in the literature, but extensive studies do not bode well for supervised learning (SL) with imbalanced datasets. The performance of vanilla supervised methods degrades significantly on class-inbalanced datasets (Cui al., 2019; Cao al., 2019; Buda al., 2018), posing challenges to practical applications such instance segmentation (Tang et al., 2020) and depth estimation (Yang et al., 2021). Many recent works address this issue with various regularization and w--weeghing/rr-samplliinn techniques (Ando & Huang, 2017: Wang al., 201 7b; Jamal et al., 2020; Cui et al., 2019; Cao et al., 2019; 2021; Tian et al., 2020; Hong et al., 2021; Wang et al., 2021).
In this work, systematically investigate the representation quality of SSL algorithms under class imbalance. Perhaps surprisingly, we find out that off-the-shelf SSL representations are already more robust dataset imbalance than the representations learned by supervised pre-training. We evaluate

---

Published as a conference paper at ICLR 2022
cap to Ba batsont
Imbalanced 0.004
Imbalanced Ratio
Cap ateative Bo anced Datarett
4
" 6
A6Co
20
4
A0oo
15
2
87K
116K
16K
40K 60K 80K
14C
29K
5BC
87K
116K
10K
20K
40K
60k
BOK
Tota Number of Pre-training Examp es
Total Number of Pre-training Examples
(a) In Domain (ID).
(b) Out of Domain (OOD).
Figure 1: Relative performance gap (lower is better) between imbalanced and balanced represen- tation learning. The gap is much smaller for self- seff-supervised (MoCo v2) representations (A SSL. in blue) vs, supervised ones (A in red) on long-tailed ImageNet with various number of examples n, across both ID (a) and OOD (b) evaluations. See Equation (1) for the precise definition of the relative performance gap and and Figure 2 for the absolute performance.
the representation quality by linear probe on in-domain (ID) data and finetuning on out-of-domain (OOD) data. We compare the robustness of SL and SSL representations by computing the gap between the performance of the representations tre-trained on balanced and imbalanced datasets of the same sizes. We observe that the balance-imbalanee gap for SSL is much smaller than SL, under variety of configurations with varying dataset sizes and imbalance ratios and with both ID and OOD evaluations (see Figure 1 and Section 2 for more details). This robustness holds even with the same number of samples for SL and SSL, although SSL does not require labels and hence can be more easily applied larger datasets than SL.
Why is SSL more robust to dataset imbalance? We identify the following underlying cause to answer this fundamental question: SSL learns richer features from the frequent classes than SL does. These features may help classify the rare classes under ID evaluation and are transferable to the downstream tasks under OOD evaluation. For simplicity, consider the situation where rare classes have so limited data that both SL. and SSL models overfit to the rare data. In this case, it is important for the models to learn diverse features from the frequent classes which can help classify the rare classes. Supervised learning is only incentivized to learn those features relevant to predicting frequent classes and may ignore other features. In contrast, SSL may learn the structures within the frequent classes better-because it is not supervised incentivized by any labels, it can learn not only the label-relevant features but also other interesting features capturing the intrinsic properties of the input distribution, which may generalize/transfrr better to rare classes and downstream tasks.
We empirically validate this intuition by visualizing the features on a semi-synthetic dataset where the label-relevant features and label-irelevaat-bute trranssra--ra features are prominently seen by design (cf. Section 3.2). In addition, we construct a toy example where we can rigorously prove the difference between self-supervised and supervised features in Section 3.1.
Finally, given our theoretical insights, we take a step towards further improving SSL algorithms, clos- ing the small gap between SSL balanced and imbalanced datasets. We identify the generalization gap between the empirical and population pre- pre-training losses on rare data as the key to improvements.
To this end, we design a simple algorithm that first roughly estimates the density examples with kernel density estimation and then applies larger sharpness haupness-bbsed regularization (Foret et al., 2020) the estimated rare examples. Our algorithm consistently improves the representation quality under several evaluation protocols.
We sum up our contributions as follows. (1) We are the first systematically investigate the robustness of self-supervised representation learning to dataset imbalance. (2) We propose and validate an explanation of this robustness of SSL, empirically and theoretically. (3) We propose a principled method to improve SSL under unknown dataset imbalance.
EXPLORING THE EFFECT OF CLASS IMBALANCE ON SSL
Dataset class imbalance can pose challenge to self-supervised learning in the wild. Without access to labels, cannot know in advance whether large-scale unlabeled dataset is imbalanced. We need to
2

---

Published as a conference paper at ICLR 2022
study how SSL will behave under dataset imbalance to deploy SSL in the wild safely. In this section, we systematically investigate the effect of class imbalance on self-supervised representations.
2.1 PROBLEM FORMULATION
Class-imbalanced pre-training datasets. We assume the datapoints inputs are in I& and come from C' underlying classes. Let æ denote the input and y denote the corresponding label. Supervised pre-training algorithms have access to the inputs and corresponding labels, whereas self-supervised pre-training only observes the inputs. Given a pre-training distribution P over over Rd x [C], let denote the ratio of class imbalance. That is, is the ratio between the probability of the rarest class and the most frequent class:
winjercr P(y=))
< 1. We will construct distributions with varying imbalance ratios and use P to denote the distribution with ratio r. also use phal for the case where r = 1, i.e. the dataset is balanced. Large-scale data in the wild often follow heavily long-tailed label distributions where r is small. We assume that for any class j E [C]. the class-conditional distribution pr (xly j) is the same across balanced and imbalanced datasets for all The pre-training dataset Pr. consists of i...d. samples from pr.
ma P(y=)}
Pre-trained models. A feature extractor is a function fo : IRd -> Im parameterized by neural network parameters o, which maps inputs to representations. A linear head is a linear function ge = + EC, which can be composed with fo to produce the predictions. SSL algorithms learn ø from unlabeled data. Supervised pre-training learns the feature extractor and the linear head from labeled data. We drop the head and only evaluate the quality of feature extractor é.
Following the standard evaluation protocol in prior works (He et al., 2020; Chen et al., 2020), we measure the quality of learned representations on both in-domain and out-of-domain datasets with either linear probe or fine-tuning, as detailed below.
In-domain (ID) evaluation tests the performance of representations on the balanced in-domain distribution phul with linear probe. Given a feature extractor f pre-trained on a pre-training dataset Pr, with n data points and imbalance ratio we train C-way linear classifier 0 on top of fo on balanced dataset² sampled i.i.d. from phaa_ We evaluate the representation quality with the top-1 I accuracy of the learned linear head on phoal We denote the ID accuracy of supervised pre-trained representations by ADD (n, r). Note that (n, 1) stands for the result with balanced pre-training dataset. For SSL representations, we denote the accuracy by A (n1, (n,r).
Out-of-domain (OOD) evaluation tests the performance of representations by fine-tuning the feature extractor and the head on a (or multiple) downstream target distribution P,. Starting from a feature extractor f (pre-trained on a dataset of size n and imbalance ratio r') and a randomly initialized classifier 0, we fine-tune @ and 0 on the target dataset Pr, and evaluate the representation quality by the expected top-1 accuracy on Pt. We use ASL. (n, r) and ASSL. A to denote the resulting accuracies of supervised and self-supervised representations, respectively.
Summary of varying factors. We aim to study the effect of class imbalance feature qualities on a diverse set of configurations with the following varying factors: (1) the number of examples in pre- trainrain n, (2) the imbalance ratio of the pre-training dataset r, (3) ID or OOD evaluation, and (4) self-supervised learning algorithms: MoCo v2 (He et al., 2020), or SimSiam (Chen & He, 2021).
2.2 EXPERIMENTAL SETUP
Datasets. We pre-train the representations on variants of ImageNet (Russakovsky et al., 2015) or CIFAR-10 (Krizhevsky & Hinton, 2009) with a wide range of numbers of examples and ratios of im- balance. Following Liu et al. (2019), we consider exponential and Pareto distributions, which closely simulate the natural long-tailed distributions. We consider imbalance ratio in (1, 0.004, 0.0025) for ImageNet and (1,0.1, 0.1, 0.01) for C1 For each imbalance ratio, further downsample the dataset with a sampling ratio in {0.75, 0.5, 0.25, 0.125) to form datasets with varying sizes. We
IIt is well-known that the composition of the head and features learned from supervised learning is more sensitive imbalanced dataset than feature extractor e itself (Cao al., 2019; Kang et al., 2020). Please also see Table 3 in Appendix C for a comparison hetween CRT (Kang et al., 2020) and Supervised. We essentially use the largest halanced labeled ID) dataset for this evaluation, which oftentimes means the entire curated training dataset, such CIFAR-10 10 with 50,000 examples and ImageNet with 1,681,167 examples.
3

---

Published as a conference paper at ICLR 2022
Accuracy CIFAR %
45
Accurasy 6n ImageMe
70
Ap (1,
tn,
35
(8 0,004)
A
30
AD 0.01)
Ag% 0.0025)
60
AB 1)
Ağ Intn 1)
AB 0.1)
20
Agtn, 0.004)
A8 0.01)
Agtn, 0.0025)
Total Number Pre Pre-training Examples
Total Number of Pre Pre-training Examples
CIFAR-IO, ID
(b) ImageNet, ID
Accuracy on Target Agso
80
70
Accurscy STL ts
Aoco1n,
70
Aopln.
50
633
ASco(n, 1)
80
Acoonn, 1]
Aduln, 004)
Abboln, 0.01)
Abalin 025)
30
12500 15000 17500
100000
Total Number trainnin
Number Pra-training Examples
(c) CIFAR-10, 10, OOD
(d) ImageNet, OOD
Figure 2: Representation quality on balanced and imbalanced datasets. Left: CIFAR-IO, SL vs. SSL (SimSiam); Right: ImageNet, SL vs. SSL (MoCo v2). For both ID and OOD, the gap between balanced and imbalanced datasets with the same is larger for supervised learning. The accuracy of supervised representations is better with reasonably large n in ID evaluation, while self-supervised representations perform better in OOD evaluation."
fix the variant of the dataset when comparing different algorithms. For ID evaluation, we use the original CIFAR-10 10 ImageNet training set for the training phase of linear probe and use the original validation set for the final evaluation. For OOD evaluation of representations learned on CIFAR- 10, we use STL-10 (Coates et al., 2011) as the target /downstream dataset. For OOD evaluation of repre- sentations learned on ImageNet, we fine-tune the pre-trained feature extractors CUB-200 (Wah et al., 201 1), Stanford Cars (Krause et al., 2013), Oxford Pets (Parkhi et al., 2012), and Aircrafts (Maji al., 2013), and measure the representation quality with average accuracy the downstream tasks.
Models. We use ResNet-18 on CIFAR-IO and ResNet-50 on ImageNet as backbones. For supervised pre-training, we follow the standard protocol of He et al. (2016) and Kang et al. (2020). For self- supervised pre-training, we consider MoCo v2 (He et al., 2020) and SimSiam (Chen & He, 2021 I). We run each evaluation experiment with 3 seeds and report the average and standard deviation in the figures. Further implementation details and additional results are deferred to Section A.
2.3 RESULTS: SEL.--SUERVISED LEARNING IS MORE ROBUST THAN SUPERVISED LEARNING TO DATASET IMBALANCE
In Figure 2, we plot the results of ID and OOD evaluations, respectively. For both ID and OOD evaluations, the gap between SSL representations learned balanced and imbalanced datasets with the same number of pre-training examples, i.e., A (n, 1) ASSL (n, r). is smaller than the gap of supervised representations, i.e., (n, Furthermore, we compute the relative accuracy gap balanced dataset A ASSL r) A (ASSL (n, 1) A (n, r))/ASSI, ASSI 1) in Figure 1. We observe that with the same number of pre- tra-training examples, the relative gap of SSL representations between balanced and imbalanced datasets is smaller than that of SI. representations across the board,
(n, consistently in all configurations.
ASSL (nz, 1) (ISS((n,)) ASSL(n,
ASL 1) (S, & (ALL(,,))
A SSL (n,r)
'The maximum is smaller for extreme imbulance. The standard deviation comes only from the randomness of evaluation. We do not include the stddev for ImageNet ID due limitation of computation resources.
4

---

Published as a conference paper at ICLR 2022
class 1 class 2
learned features
Pa:d
11
class 3
SL:
e1
(overfitting to the rare class)
e
02
SSL:
e2
Figure 3: Explaining SSL's robustness in toy setting. 61 and e2 are two orthogonal directions in the d-dimensional Euclidean space that decides the labels, and E3id represents the other d - 2 dimensions. Classes and are frequent classes and the third class is rare. To classify the three classes, the representations need to contain both é₁ and 62 directions. Supervised learning learns direction 61 from the frequent classes (which necessary and sufficient identify classes and 2) and some overfitting direction from the rare class which has insufficient data. Note that might be contrast, SSL learns both e and e2 directions from
mostly in the eg.d directions due to overfitting. the frequent classes because they capture the intrinsic structures of the inputs (c.g., e1 and e2 the directions with the largest variances), even though e2 does not help distinguish the frequent classes. The direction 62 learned from frequent data by SSL can help classify the rare class.
Also note that comparing the robustness with the same number of data is actually in favor of SL, because SSL is more easily applied to larger datasets without the need of collecting labels.
ID VS. OOD. As shown in Figure 2. we observe that representations from supervised pre-training perform better than superviid pre-training in ID evaluation with reasonably large n, while self-supervised pre-training is better in OOD evaluation. This phenomenon is orthogonal to our observation that SSL. more robust to dataset imbalance, and consistent with recent works (e.g.. Chen et al. (2020); He et al. (2020)) which also observed that SSL performs slightly worse than supervised learning on balanced ID evaluation but better on OOD tasks.
ANALYSIS
We have found out with extensive experiments that self-supervised representations robust to class imbalance than supervised representations. A natural and fundamental question arises: where does the robustness stem from? In this section, propose possible reason and justify it with theoretical and empirical analyses.
SSL learns richer features from frequent data that are transferable to rare data. The rare classes of the imbalanced dataset can contain only a few examples, making it hard to learn proper features to classify the rare classes. In this case, one may want resort the features learned from the frequent classes for help. However, due to the supervised nature of classification tasks, the supervised model mainly learns the features that help classify the frequent classes and may neglect other features which can transfer to the rare classes and potentially the downstream tasks. Partly because of this, Jamal al. (2020) explicitly encourage the model learn features transferable from the frequent to the rare classes with meta- meta-learning. In contrast, in self-supervised learning, without the bias or incentive from the labels, the models can learn richer features that capture the intrinsic structures of the inputs-both features useful for classifying the frequent classes and features transferable to the rare classes.
3.1 RIGOROUS ANALYSIS ON A TOY SETTING
To justify the above conjecture, we instantiate supervised and self-supervised learning in a setting where the features helpful classify the frequent classes and features transferable to the rare classes can be clearly separated. In this case, we prove that self-supervised learning learns better features than supervised learning.
Let el, e2 be two orthogonal unit-norm vectors in the d-dimensional Euclidean space. Consider the following pre- pre-training distribution P of a 3-way classification problem, where the class label y [3]. The input is generated as follows. Let 7 > 0 and p > 0 be hyperparameters of the distribution. First sample q uniformly from {0, 1} and & ~ (0, I) from Gaussian distribution. e1 qrez + PC. For the second class (y 2),
Data distribution.
For the first class (y 1),
5

---

Published as a conference paper at ICLR 2022
- + PÇ. For the third class (y 3), set C2 + pL. Classes and 2 are frequent classes, while class is the rare class, i... P(y=3) P(y=3) of (1. See Figure for an illustration of this data distribution. In this case, both e and e2 are features from the frequent classes and 2. However, only 61 helps classify the frequent classes and only e2 can be transferred to the rare classes.
P(y=1)* 2(y=2)
Algorithm formulations. For supervised learning, we train two-layer linear network fw, ww, (z) & W2 W/ with weight matrices W1 E RRnxd and W2 E R for some m 2 3, and then use the first layer Wst. = W as the feature for downstream tasks. Given a linearly separable labeled dataset, we learn such network with minimal norm || Wills + [[W, W subject to the margin constraint fw, (zr)y 2 fw.,w, (x) + 1 for all data (x, y) in the dataset and y' * y. For self- supervised learned, similar to SimSiam (Chen et al., 2020), we construct positive pairs (x + &, 2 + +") where x is from the empirical dataset, & and g are independent random perturbations. We learn matrix WSSL E Rmxd which minimizes [B( + ( + E')] + |[W Wl]2, where the expectation É is over the empirical dataset and the randomness of & and e'. The regularization term 1 1 is introduced only to make the learned features more mathematically tractable. We use WSSL.C as the feature of data x in the downstream task.
Main intuitions. We compare the features learned by SSL and supervised learning on imbalanced dataset that contains an abundant (poly in d) number of data from the frequent classes but only a small (sublinear in d) number of data from the rare class. The key intuition behind our analysis is that supervised learning learns only the é₁ direction (which helps classify class I vs. class 2) and some random direction that overfits to the rare class. In contrast, supe-super learning learns both e1 and directions from the frequent classes. Since how well the feature helps classify the rare class (in ID evaluation) depends on how much correlates with the e, direction, SSL provably learns features that help classify the rare class, while supervised learning fails. This intuition is formalized by the following theorem.
Theorem 3.1. Let n1, n22, na be the number of data from the three classes respectively. Let d and r- = dt in the data generative model. For T22 = (ppoly(d)) and na S dd, with probubility
at least 1--0 -Oee O -d ), the following statements hold for any feature dimension mn 2 3:
Let WSL [wi, u.. .... Wmn] IT be the feature learned by SL, then Eis (e2, w,)² 2 v Od tb). Let WSSL = [w),, 02.- ... "m) T be the feature learned by SSL, then ||Teell2 2 0(d-b) b),
where 11 projects e2 onto the row span of WSSL.
Supervised learning results in features WsL whose rows have small correlation with the transferable feature e2, indicating that supervised learning only learns features for classifying the frequent classes and ignore the transferable features. In contrast, superviee learning recovers 62 well, even though e2 is not relevant to classifying the frequent classes. The proofs are deferred to Section E.
3.2 I.LUSTRATIVE SEMI-SYNTHETE EXPERIMENTS
In the previous subsection, we have shown that self-supervised learning provably learns label- srrelevant-uu--rrnsfeeraa features from the frequent classes which can help classify the rare class in the toy case, while supervised learning mainly focuses on the label-relevant features. However, in real-world datasets, it intractable to distinguish the two groups of features. To amplify this effect in a real-world dataset and highlight the insight of the theoretical analysis, we design a semi semi-synthetic experiment on SimCLR (Chen et al., 2020) to validate our conclusion.
Dataset. In the theoretical analysis above, the frequent classes contain both features related to the classification of frequent classes and features transferable to the the rare classes. Similarly, we consider imbalanced pre-training dataset with two groups of features modified from CIFAR- as shown in Figure (Left). We construct classes 1-5 as the frequent classes, where each class contains 5000 examples. Classes 6- are the rare classes, where each class has 10 examples. In this case, the ratio of imbalance r = 0.002. Each image from classes 1-5 consists of a left half and a right half. The left half of an example is from classes 1-5 of the original CIFAR- 10 and corresponds to the label of that example. The right half is from a random image of CIFAR- 10, which is iirelevatt...... In
Prevvios work shows that deep linear networks trained with gradient descent using logistic loss converge this min norm solution in direction (Ji & Telgarsky, 2018)
6

---

Published as a conference paper at ICLR 2022
Input
Supervised
SimCLR
Input
Supervised
SimCCR
Accuracy % on Rare Casses
80
Supersinent-rree
Supervised SimCLR
Label-
Frequent Classes
Random
40
30
rolevant
Figure 4: Visualization of SSL features in semi-synthetic settings. Left: The right halves of the rare examples decide the labels, while the left are blank. The left halves of the frequent examples decide the labels, while the right halves are random half images, which contain label-irrelevant-bur transferable features. Middle: Visualization of features with Grad-CAte (Selvaraju al., 2017). SimCLR learns features from both left and right sides, whereas SL mainly learns label-relevant features from the left and ignore label-irrelevant features
the right. Right: Accuracies evaluated on rare classes. The head classifiers are trained on 25000 examples from the 5 rare classes. SimCLR learns much better features for rare classes than SL. We include random feature (feature extractor with random weights) and supervised-rare (model trained with only the rare examples) for references.
contrast, the left half of an example from classes 6-16 6-10% is blank, whereas the right half is label-relevant and from classes 6-10 of the original CIFAR-IO. In this setting, features from the left halves of the images are correlated to the classification of the frequent classes, while features from the right halves are label-irrelevant for the frequent classes, but can help classify the rare classes. Note that features from the right halves cannot be directly learned from the rare classes since they have only 10 examples per class. This is consistent with the setting of Theorem 3.1.
Pre-training. We pre-train the representations on the semi-synthetic imbalanced dataset. For supervised learning, we use ResNet-50 on this 10-way classification task. For self-supervised learning, we use SimCLR with ResNet-50. To avoid confusing the left and right parts, we disable the random horizontal flip the data augmentation. After pre-training, we fix the representations and train linear classifier top of the representations with balanced data from the 5 rare classes (25000 examples in total) to test if the model learns proper features for the rare classes during pre-training. In Figure (Right), test the classifier 7) of the representations on the held-out set
the rare classes. In Figure 4 (Middle), further visualize
the Grad-CAN CMM (Selvaraju et al., 2017)
Results. As sanity check, first pre-train supervised model with only the 50 rare examples and train the linear head classifier with 25000 examples from the rare classes (5-way classification) to see if the model can learn proper features for the rare classes with only examples (Supervised-rare in Figure 4 (Right)). As expected, the accuracy is 36.5%. which is almost the same randomly initialized representations with trained head classifier, indicating that the model cannot learn the features for the rare classes with only rare examples due to the limited number of examples. We then compare supervised learning with self-supervised learning on the whole semi-synthetic dataset. In Figure 4 (Right), self-supervised representations perform much better than supervised representations on the rare classes (70.1% vs 44.3%). We further visualize the activation maps of representations with Grad-CAM. Supervised learning mostly activate the left halves of the examples for both frequent and rare classes, indicating that it mainly learn features on the left. sharp contrast, supervueee learning activates the whole image the frequent examples and the right part on the rare examples, indicating that it learns features from both parts.
IMPROVING SSL ON IMBALANCED DATASETS WITH REGULARIZATION
In this section, we aim to further improve the performance of SSL to close the gap between imbalanced and balanced datasets. Many prior works on imbalanced supervised learning regularize rare classes more strongly, motivated by the observation that the classes suffer from more overfitting (Cao et al., 2019; 2021). Inspired by these works, we compute the generalization gaps (i.c., the differences between empirical and validation pre-training losses) frequent and rare classes for the step-
.CIFAR images are of low resolution. For visualization, use high resolution version of the CIFAR-10 images Figure (Middle). We also provide the visualization original CIFAR-10 images Figure
7

---

Published as a conference paper at ICLR 2022
imbalance CIFAR-10 datasets (where 5 classes are frequent class with 5000 examples per class and the rest are rare with 50 examples per class). As shown in Table 1 (a), we still observe a similar phenomenon- the frequent classes have much smaller pre-training generalization gap than the rare classes (0.035 vs. 0,081), which indicates the necessity of more regularization on the rare classes.
We need a data-dependent regularizer that can have different effects Thus, weight decay or dropout (Srivastava et al., 2014) are not suitable. The prior work of Cao et al. (2019) regularizes the rare classes more strongly with larger margin, but does not apply to SSL where no labels are available. Inspired by Cao et al. (2021), we adapt sharpness-aware minimization (SAM) (Foret et al., 2021) to imbalanced SSL.
and frequent examples.
Reweighted SAM (rwSAM). SAM improves model generalization by penalizing loss sharpness. Suppose the training loss of the representation fo is L(Ø), i.e. L(Ø) = + ブ E(zz, Ø). SAM seeks
parameters where the loss is uniformly low in the neighboring area,
min L( + c(Ø)),
where
c(Ø) = arg max c
V VO). |
To take the weight of different examples into account, we add reweighting to the inner maximization step of SAM. Intuitively, we wish the optimization landscape to be flatter for rare examples, which is in effect regularizing the model more on rare examples. Concretely, consider the reweighted training loss associated with weight vector E RD, (o) - myl(an .). The reweighted SAM objective re-weights the regularization-related terms (c.g., Ew) but not the training loss L:
min L + Em)()), where (Ø) arg max E VV VoLl
[|c|
Assigning Weight with Kernel Density Estimation. The weight wy of an example 2, should be inversely correlated with the frequency of the corresponding class yj- However, we have no access top of
to the labels. In order to approximate the frequency, the representations fa- Concretely, denote by (-, h) the Gaussian density with bandwidth h. We assign wi to be inversely correlated with the estimated density, i.e., w; = ( Σÿ= (ff((x))
use kernel density estimation
fo(r,); h)) where h and a > 0 are hyperparameters selected by cross validation.
4.1 EXPERIMENTS
We test the proposed rwSAM on CIFAR-10 with step or exponential imbalance and ImageNet- LI (Liu et al., 2019). After self-supervised pre-training on the long-tailed dataset, we evaluate the representations by (1) linear probing on the balanced in-domain dataset and (2) fine-tuning on downstream target datasets. For (1) and (2), we compare with SSL, SSL+SAM (w/o reweighting). and SSL balanced, which learns the representations on the balanced dataset with the same number of examples. Implementation details and additional results are deferred to Section C. Code is available at httpt::////. / http:/gtthuh..ooo Li uhong99 Imbal 1 anced- SSL.
Results. Table (a) summarizes results on long tailed CIFAR- With both step and exponential imbalance, rwSAM improves the performance of SimSiam over 1%. and even surpasses the perfor- mance of SimSiam on balanced CIFAR- 10 with the same number of examples. Note that compared to SimSiam, rwSAM closes the generalization gap of pre-training loss on rare examples from 0.081 to 0.066, which verifies the effect of re- weighted regularization. In Table 1 (b), we provide the result of fine-tuning downstream tasks with representations pre-traines pre-trained on ImageNet-LT. The proposed method improves the transferability of representations to downstream tasks consistently.
RELATED WORK
Supervised Learning with Dataset Imbalance. There exists line of works studying supervised imbalanced classification. Ando & Huang (2017); Buda et al. (2018) proposed to re-sample the data to make the frequent and rare classes appear with equal frequency in training. Re-weighting assigns different weights for head and tail classes and eases the optimization difficulty under class imbalance (Cui et al., 2019; Tang al., 2020; Wang et al., 2017b). Byrd & Lipton (2019); Xu et al. (2021) studied the effect of importance weighting and found out that importance weighting does not change the solution without regularization. Cao et al. (2019) studied reweighted regularization based
8

---

Published as a conference paper at ICLR 2022
(a) CIFAR, ID
0.01, step
0.01, exp
Method
Acc. (%)
Gap Freq.
Gap Rare
Acc. (%)
SimSiam
84.3 + 0.2
0.035
0.081
81.4 1 0.3
Sim
84.7 + 0.3
0.044
0.075
82.1 +: 0.4
SimSiam, balanced
85.8 +: 0.2
0.038
0.037
82.0 0.4
SimSiam-rWSAAM
85.6 + 0.4
0.037
0.066
82.7 + 0.5
(b) ImageNet, 0OD
Target datasct
Method
CUB
Cars
Aircrafts
Pets
Avg.
MoCo v2
69.9 0.7
88.4 + 0.4
82,9 0.6
80.1
80.3
MoCo v2+SAM
69.9 0.5
88.8 + 0.5
83.4 0.4
81.5 = 0.8
80.9
MoCo v2, balanced
69.8 0.5
88.6 + 0,4
82.7 + 0.5
80.0 = 0.4
80.2
MoCo v2+rwSAM
70.3 0.7
88.7 + 0.3
84,9 + 0.6
81.7 + 0.4
81.4
SimSiam
70.0 0.3
87.0 + 0.6
81.5 + 0.7
83.8 + 0.5
80.6
SimSiam, balanced
70.5 + 0.8
87.9 + 0.7
81.8 + 0.7
82.7 + 0.4
80.7
SimSSam+rwSSAM
70.7 = 0.8 88.4 1 0.6 82.6 1 0.6 84.0 + 0.4
81.4
Table I: Results the proposed rwSAM. (a) Results on CIFAR-1O-LT with linear probe and ID evaluation. SimSian+rWSAM imbalanced datasets performs even better than SimSiam balanced datasets with the same number examples. Note that rwSAM closes the generalization gap on the rare examples (0.081 0.066). (b) Results on ImageNet-LT with fine-tuning and OOD evaluation. rwSAM improves the performance of MoCo v2 and SimSiam on the target datasets.
on classifier margin, but these techniques are limited to supervised imbalanced recognition. Cao et al. (2021) proposed to regularize the local curvature of loss imbalanced and noisy datasets. Recent works also designed specific losses or training pipelines for imbalanced recognition (Jamal et al., 2020; Hong al., 2021; Wang et al., 2021; Zhang et al., 2021).
Several works also studied the supervised representations under dataset imbalance. Kang et al. (2020); Wang et al. (2020) found out that the representations of supervised learning perform better than the classifier itself with class imbalance. Yang & Xu (2020) studied the effect of self telf-training and self-supervised pre-training on supervised imbalanced recognition classifiers. contrast, the focus of our paper is the effect of class imbalance on self-supervised representations.
Self-supervised Learning. Recent works on self-supervised learning successfully learn representa- tions that approach the supervised baseline ImageNet and various downstream tasks. Contrastive learning methods attract positive pairs and drive apart negative pairs (He et al., 2020; Chen et al., 2020). Siamese networks predict the output of the other branch, and use stop-gradient to avoid collapsing (Grill et al., 2020; Chen & He, 2021). Clustering methods learn representations by per- forming clustering the representations and improve the representations with cluster index (Caron et al., 2020). Cole et al. (2021) investigated the effect of data quantity and task granularity on self-supervised representations. Goyal al. (2021) studied sule-supe methods large scale datasets in the wild. Kotar et al. (2021) studied whether dataset imbalance can have a significant impact on contrastive learning representations. Several works have also theoretically studied the success of self-supervised learning (Arora et al., 2019; Lee et al., 2020b; HaoChen et al., 2021; Wei al., 2021).
CONCLUSION
Our paper is the first to study the problem of robustness to imbalanced training of self-supervised representations. We discover that self-supervised representations are more robust to class imbalance than supervised representations and explore the underlying cause of this phenomenon. Our experi- ments mainly focus on vision datasets. Future works can study the effect of dataset imbalance on NLP datasets, where self self-supervised pre-training is dominant approach. We hope our study inspire analysis of self-supervised learning in broader environments in the wild such as domain shift, and provide insights for the design of future unsupervised learning methods.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
We thank Colin Wei, Margalit Glasgow, and Shibani Santurkar for helpful discussions. TM ac- knowledges support of Google Faculty Award, NSF IIS 2045685, the Sloan Fellowship, and JD.com. Toyota Research Institute provided funds to support this work.
REPRODUCIBILITY STATEMENT
To ensure reproducibility,
describe the implementation details of the algorithms and the con- struction of the datasets in Section A.1 and Section C. The code of the experiments in Section 2, Section 3.2 and Section 4 provided the supplementary material. We describe the setting and data assumptions of the toy case in Section 3.1 and provide the proof in Section E.
ETHICS STATEMENT
Our paper studies the problem of robustness to imbalanced training of self-supervised representations. This setting is important to AI Ethics, as large real-world datasets tend to be imbalanced in practice, for instance including less examples from under-represented minorities. Furthermore, pre-training is standard practice in deep learning, especially for quickly adapting models to domains, which corresponds to our OOD evaluation scenario.
Our experiments and theoretical analysis show that SSL is more robust than supervised pre-training, especially in the OOD scenario. As supervised learning is still the de facto standard for pre-training, our work should have wide impact, encouraging practitioners to use SSL for pre-trate pre-training instead, or at least consider evaluating the impact of imbalanced pre-traine vre-training on their downstream task.
We also remark that the paper does not imply at all that the algorithms proposed or studied can guarantee any form of fairness, and they in fact should still suffer from biases. The paper should be considered as a step towards studying the important technical issue of dataset imbalance, which related to the fairness or biases questions.
REFERENCES
Shin Ando and Chun Yuan Huang. Deep over-sampling framework for classifying imbalanced data. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 770-785, 2017.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. A theoretical analysis of contrastive unsupervised representation learning. In International Conference on Machine Learning, 2019.
Mateusz Buda, Atsuto Maki, and Maciej Mazurowski. systematic study of the class imbalance problem in convolutional neural networks. Neural Networks, 106:249-259, 2018.
Jonathon Byrd and Zachary Lipton. What is the effect of importance weighting in deep learning? In International Conference Machine Learning, pp. 872-881. PMLR, 2019.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with label-distribution-awa aware margin loss. In Advances in Neural Information Processing Systems, volume 32, pp. 1565-1576. Curran Associates, Inc., June 2019.
Kaidi Cao, Yining Chen, Junwei Lu, Nikos Arechiga, Adrien Gaidon, and Tengyu Ma. Heteroskedas- tic and imbalanced deep learning with adaptive regularization. International Conference on Learning Representations, 2021.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. arXiv preprint arXiv:2006. 098882, 33:9912-999 99244, 2020.
Nitesh V Chawla, Kevin W Bowyer, Lawrence Hall, and W Philip Kegelmeyer. Smote: synthetic minority over-sampling technique. Journal of artificial intelligence research, 16:321-357, 2002.
10

---

Published as a conference paper at ICLR 2022
Ting Chen, Simon Komblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning. volume 119 of Proceedings of Machine Learning Research, pp. 1597-1607. PMLR, PMLR, 13- Jul 2020.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pp. 15750-15758, June 2021.
Adam Coates, Andrew Y Ng, and Honglak Lee. An analysis of single-layer networks in unsupervised feature learning. In International Conference Artificial Intelligence and Statistics, pp. 215-223, 2011.
Elijah Cole, Xuan Yang, Kimberly Wilber, Oisin Mac Aodha, and Serge Belongie. When does contrastive visual representation learning work? arXiv preprint arXiv:2105.05837, 2021.
Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoe V Le. Randaugment: Practical automated data augmentation with reduced search space. Proceedings of the IEEF/CVE Conference on Computer Vision and Puttern Recognition Workshops, pp. 702-703, 2020.
Yin Cui, Menglin Jia, Tsung- Yi Lin, Yang Song, and Serge Belongie. Class-balances loss based on effective number of samples. In Proceedings the IEEE/CVF conference on computer vision and paltern recognition, pp. 9268-9277, 2019.
Carl Doersch, Abhinav Gupta, and Alexei A Efros. Unsupervised visual representation learning by context prediction. Proceedings of the IEEE international conference on computer vision, pp- 1430, 2015.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. arXiv preprint arXiv:2010.01412, 2020.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. In International Conference on Learning Representations, 2021.
Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. arXiv preprint arXiv: 2018.
Priya Goyal, Mathilde Caron, Benjamin Lefaudeux, Min Xu, Pengchao Wang. Vivek Pai, Mannat Singh, Vitaliy Liptchinsky, Ishan Misra, Armand Joulin, al. Self-supervised pretraining of visual features in the wild. arXiv preprint arXiv: 100.0/90330 2021.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent: new approach to self-supervised learning. arXiv preprint 2020.
arXiv:2006.07733: 33:21271-21
Hongyu Guo and Herna L Viktor. Learning from imbalanced data sets with boosting and data generation: the databoost-im approach. ACM Sigkdd Explorations Newsletter, 6(1):30-39, 2004.
Jeff Z. HaoChen, Colin Wei, Jason Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. arXiv preprint arXiv:2006. 08680, 2020.
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self self-super deep learning with spectral contrastive loss. arXiv preprint arXiv:2 /06.04 2021.
Peter Hart. The condensed nearest neighbor rule (corresp.). IEEE transactions on information theory, (433)551-5166, 1968.
Haibo He and Edwardo A Garcia. Learning from imbalanced data. IEEE Transactions on knowledge 2009.
and data engineering,
Haibo He, Yang Bai, Edwardo A Garcia, and Shutao Li. Adasyn: Adaptive synthetic sampling approach for imbalanced learning. In 2008 IEEE international joint conference on neural networks (IEEE world congress computational intelligence), pp. 1322-1328. IEFF, 2008

---

Published as a conference paper at ICLR 2022
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 9729-9738, June 2020.
Youngkyu Hong. Seungju Han, Kwanghee Choi, Seokjun Seo, Beomsu Kim, and Buru Chang- Disentangling label distribution for long-tailed visual recognition. In Proceedings of the JEEF/CVF Conference Computer Vision and Patfern Recognifion, pp. 6626-6636, 2021.
Xinting Hu, Yi Jiang, Kaihua Tang, Jingyuan Chen, Chunyan Miao, and Hanwang Zhang. Learning to segment the tail. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 14045-14054, 2020.
Chen Huang. Yining Li, Chen Change Loy, and Xiaoou Tang. Deep imbalanced learning for face recognition and attribute prediction. IEEE transactions on pattern analysis and machine intelligence, 42(1 1):2781-2794, 2019.
Muhammad Abdullah Jamal, Matthew Brown, Ming-Hsuan Yang, Ligiang Wang, and Boqing Gong. Rethinking class-balanced methods for long-tailed visual recognition from domain adaptation perspective. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. arXiv preprint arXiv:1810.02033 0.00000 2018.
Bingyi Kang, Saining Xie, Marcus Rohrbach, Zhicheng Yan, Albert Gordo, Jiashi Feng, and Yannis Kalantidis. Decoupling representation and classifier for long-tailed recognition. In International Conference Leurning Representations, 2020.
Klemen Kotar, Gabriel Ilhareo, Ludwig Schmidt, Kiana Ehsani, and Roozbeh Mottaghi. Contrasting contrastive self-supervised representation learning pipelines. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 9949-9959, 2021.
Jonathan Krause, Michael Stark, Jia Deng, and Li Fei-Fei. 3d object representations for fine-grained categorization. Proceedings of the IEEE international conference on computer vision workshops, pp. 554-561, 2013.
Bartosz Krawezyk. Learning from imbalanced data: open challenges and future directions. Progress in Artificial Intelligence, ((4):221-233) 2016.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
Miroslav Kubat, Stan Matwin, et al. Addressing the curse of imbalanced training sets: one-sided selection. Ieml, volume 97, pp. 179-186. Citeseer, 1997.
Hae Beom Lee, Hayeon Lee, Donghyun Na. Saehoon Kim, Minseop Park, Eunho Yang, and Sung Ju Hwang. Learning to balance: Bayesian meta-learning for imbalanced and out-of-distribution tasks. In International Conference on Learning Representations, 2020a.
Jason Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable self-supervised learning. arXiv preprint arXiv:2008.01006 2020b.
Tsung- Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár, Focal loss for dense object detection. In Proceedings of the IEEE international conference computer vision, pp. 3980-2983 2017.
Jialun Liu, Yifan Sun, Chuchu Han, Zhaopeng Dou, and Wenhui Li. Deep representation learning on long-tailed data: A learnable embedding augmentation perspective. In Proceedings of the IEFF/CVF Conference Computer Vision and Pattern Recognition, pp. 2970-2979, 2020.
12

---

Published as a conference paper at ICLR 2022
Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella X. Yu. Large- scale long-tailed recognition in an open world. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
Divyam Madaan, Jaehong Yoon, Yuanchun Li, Yunxin Liu, and Sung Ju Hwang. Representa- tional continuity for unsupervised continual learning. In International Conference on Learning Representations, 2022.
Subhransu Maji, Esa Rahtu, Juho Kannala, Matthew Blaschko, and Andrea Vedaldi. Fine-grained visual classification of aircraft. arXiv preprint arXiv:/306.555 2013.
Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. Long-tail learning via logit adjustment. In International Conference on Learning Representations, 2021.
Mehdi Noroozi and Paolo Favaro. Unsupervised learning of visual representations by solving jigsaw puzzles. In European conference on computer vision, pp. 69-84. Springer, 2016.
Omkar M Parkhi, Andrea Vedaldi, Andrew Zisserman, and CV Jawahar. Cats and dogs. In 2012 IEEE conference on computer vision and pattern recognition, pp. -498-3505, 2012.
William J Reed. The pareto, zipf and other power laws. Economics letters, 74(1):15-19, 2001.
Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In International Conference Machine Learning, pp. 4334 4343, 2018.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Sathcesh, Sean Ma. Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision, 115(3): 211-252, 2015.
Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based local- ization. In Proceedings of the IEEE international conference on computer vision, pp. 618-626, 2017.
Jun Shu, Qi Xie, Lixuan Yi, Qian Zhao, Sanping Zhou, Zonghen Xu, and Deyu Meng. Meta-weight net: Learning an explicit mapping for sample weighting. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Iya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15():1199-11988 2014.
Kaihua Tang, Jianqiang Huang, and Hanwang Zhang. Long-tailed classification by keeping the good and removing the bad momentum causal effect. In Advances in Neural Information Processing Systems, volume 33, pp. 1513-15511 1524. Curran Associates, Inc., 2020.
Junjiao Tian, Yen-Cheng Liu, Nathan Glaser, Yen-Chang Hsu, and Zsolt Kira. Posterior re-calibration for imbalanced datasets. arXiv preprint arXiv:2010. 1820, 2020.
Yuandong Tian, Xinlei Chen, and Surya Ganguli. Understanding self-supervised learning dynamics without contrastive pairs. arXiv preprint arXiv:2102.06870, 2021.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive estimation reveals topic
posterior information to linear models. arXiv:2003.022 002334, 2020.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redun- dancy, and linear models. In Algorishmic Learning Theory, pp. 1179-1206. PMLR, 2021.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie. The caltech-ucsd birds-200-2011 dataset. 2011.
13

---

Published as a conference paper at ICLR 2022
Shuo Wang and Xin Yao. Diversity analysis imbalanced data sets by using ensemble models. In 2009 IEEE symposium on computational intelligence and data mining, pp. 324-331. IEEE, 2009.
Tao Wang, Yu Li, Bingyi Kang, Junnan Li, Junhao Liew, Sheng Tang, Steven Hoi, and Jiashi Feng. The devil is in classification; A simple framework for long-tail instance segmentation. In European Conference on computer vision, pp. 728-744. Springer, 2020.
Xiaolong Wang, Kaiming He, and Abhinav Gupta. Transitive invariance for self supf-suue visual representation learning. Proceedings of the IEEE international conference on computer vision, pp. 1329-1338, 2017a.
Xudong Wang, Long Lian, Zhongqi Miao, Ziwei Liu, and Stella Yu. Long-tailed recognition by rout- ing diverse distribution-awar experts. In International Conference on Learning Representations, 2021.
Yu- Yu-Xiong Wang, Deva Ramanan, and Martial Hebert. Learning model the tail. In Proceedings of the 31st International Conference on Neural Information Processing Systems, 7032-7042, 2017b.
Colin Wei, Sang Michael Xie, and Tengyu Ma. Why pretrained language models help in downstream tasks? an analysis of head and prompt tuning. arXiv preprint arXiv:2106.09223 2021.
Da Xu, Yuting Ye, and Chuanwei Ruan. Understanding the role of importance weighting for deep learning. International Conference on Learning Representations, 2021.
Yuzhe Yang and Zhi Xu. Rethinking the value of labels for improving class-imbalanced learning. In Advances in Neural Information Processing Systems, volume 33, pp. 19290-19301. Curran Associates, Inc., 2020.
Yuzhe Yang, Kaiwen Zha, Yingcong Chen, Hao Wang, and Dina Katabi. Delving into deep imbal- anced regression. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 11842-11851, 18 24 Jul 2021.
Songyang Zhang, Zeming Li, Shipeng Yan, Xuming He, and Jian Sun. Distribution alignment: A unified framework for long-tail visual recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2361-2370, 2021.
14

---

Published as a conference paper at ICLR 2022
r= 0.01
Imbalanced ImageNet
0.0025
0.35
0.1
0.004
0.32
Brbbbbiig
0.5
0. 0.019
0.5
0.003
015
9:005
0.004
10
600
800
1000
Figure 5: Visualization of the label distributions. We visualize the label distributions of the imbal- anced CIFAR- 10 and ImageNet. We consider two imbalance ratios r for each dataset.Imbale Imbalanced CIFAR- 10 follows the exponential distribution, while imbalanced ImageNet follows Pareto distribu- tion.
A DETAILS OF SECTION 2
A.1 IMPLEMENTATION DETAILS
Generating Pre-training Datasets. CIFAR-10 10 (Krizhevsky & Hinton, 2009) contains 10 classes with 5000 examples per class. We use exponential imbalance, i.e. for class c, the number of examples is 5000 x estc-1), we consider imbalance ratio r E {00.1, 0. i.c. the number of examples belonging to the rarest class is 500 or 50. The total n, is therefore 20431 12406. ImageNet-LT is constructed by Liu et al. (2019), which follows the Pareto distribution with the power value 6. The number of examples from the rarest class is 5. We construct a long tailed ImageNet following the Pareto distribution with more imbalance, where the number of examples from the rarest class is 3. The total number of examples n, is 115846 and 80218 respectively. For each ratio of imbalance, we further downsample the dataset with the sampling ratio in {0.75, 0.5, 0.25, 0.125] to formulate different number of examples. To compare with the balanced setting fairly, we also sample balanced versions of datasets with the same number of examples. Note that each variant of the dataset is fixed after construction for all algorithms. See the visualization of label distributions of dataset variants in Figure 5.
Training Procedure, For supervised pre-training we follow the standard protocol of He al. (2016) and Kang et al. (2020). On the standard ImageNet-LT, we train the models for 90 epochs with step learning rate decay. For down-sampled variants, the training epochs are selected with cross validation. Fo self-supervised learning. the initial learning rate on the standard ImageNet-LD LT is set to 0.025 with batch-size 256. We train the model for 300 epochs on the standard ImageNet-LT and adopt cosine learning rate decay following (He et al., 2020; Chen & He, 2021). We train the models for more epochs on the down sampled variants to ensure the same number of total iterations. The code on CIFAR-10 LT adapted from https: /tt:://gitt /ggthtb...../// www//eoaeeaeoeeeeo Reeza-eeaaaaa Safdari /Simsiia am 91. 9 t-topl- acc- on CIFAR10.
For in-domain evaluation (ID), first train the the representations on the aforemen- tioned dataset variants, and then train the linear head classifier on the full balanced CIFARI0 10 or ImageNet. We set the initial learning rate 30 when training the linear head with batch-size 4096 and train for 100 epochs in total. For in-domain first train the the representations on the aforementioned dataset variants, and then fine-tune the model to CUB-200 (Wah et al., 2011), ),, Stanford Cars (Krause et al., 2013), Oxford Pets (Parkhi et al., 2012) 2). and Aircrafts (Maji et al., 2013). The number of examples of these target datasets ranges from 2k to 10k, which is reasonable scale as the number of examples of the pre-training dataset variants ranges from 10k to 110k. The representation quality is evaluated with the average performance on the four tasks. We set the initial learning rate to 0.1 1 in fine-tuning train for 150 epochs in total. For in-domain out-of-domain evaluation (OOD) on CIFAR-10 10, we use STL-10 as the downstream target tasks and perform linear probe.
Evavluation.
evaluation (OOD) on ImageNet, we
15

---

Published as a conference paper at ICLR 2022
Imabalanced Ratio 0.004
mabalanced Ratio 0.0025
4880
75
4800
70
Aooonn 0.004)
Al 0.025)
Gag Relative
Abo 1)
Accurscy
Asu 0.004)
Absoin, 0.025)
20000 40000 60200 80000
100000
Total Number of Pre training Examples
Total Number Pre traininiinnngg Examples
(a) OOD Accuracy.
(b) Relative Gap.
Figure 6: OOD Results of SimSiam on ImageNet. SimSiam also demonstrates more robustness to class imbalance compared supervised learning. The relative gap to balanced dataset is much smaller than supervised learning across different imbalance ratios.
Table Numbers in Figure and Figure 6.
Imbalanced Ratio rl
1, balanced
0.004
0.0025
Data Quantity
116K
87K
58K
29K
14K
116K
87K
58K
29K
14K
80K
60K
40K
20K
10K
MoCo V2, ID
50.4
43.5
40.9
37.0
30.8
49.5
43.2
39.5
36.6
30.5
40.6
38.8
35.5
31.9
27.2
MoCo V2, OOD
80.3
79.8
79.7
77.4
77.0
80.2
80.1
79.5
77.8
77.3
79.2
78.8
77.7
75.6
74.4
Supervised, ID
54.3
51.6
46.1
40.5
26.3
52.9
49.6
44.0
37.3
24.9
46.1
42.0
36.3
27.5
20.3
Supervised, OOD
76.6
74.7
71.9
67.4
59.1
75.5
73.3
70.4
65.8
57.8
71.8
69.1
65.9
60.3
54.3
SimSiam, OOD
80.7
80.4
79.9
78.7
77.2
80.6
79.9
79.6
78.8
76.9
79.8
79.3
77.5
76.0
A.2 ADDITIONAL RESULTS
To validate the phenomenon observed Section consistent for different self-supervised learning algorithms, we provide the OOD evaluation results of SimSiam trained on ImageNet variants and relative performance gap with balanced datasets in Figure 6. SimSiam representations are also less sensitive class imbalance than supervised representations.
We also provide the numbers of Figure 2 and Figure 6 in Table 2.
B DETAILS OF SECTION 3.2
We first generate the balanced semi-synthetic dataset with 5000 examples per class. The left halves of images from classes 1-5 correspond to the labels, while the right halves random. The left halves of images from class 6-10 are blank, whereas the right halves correspond to the labels. We then generate the imbalanced dataset, which consists of the 5000 examples per class from classes 1-5 (frequent classes), and 10 examples per class from classes 6-10 (rare classes). We use Grad-CAM imple- mentation based on https:://// /tttts::/githeee hug. wtt.m/eeeeteeomeeeeeeeeecoeeeete gradeaaaaa.aaaaaa.aaaaam pytorch and SimCLR implementation from https: github. wwwtthhaams//mmmm..... We provide examples and Grad-CAM of the semi-synthetic datasets Figure 7.
C DETAILS OF SECTION
C.1 IMPLEMENTATION DETAILS
We use the same implementation as Section for supervised and self-supervised learning baselines. We implement sharpness-aware minimization following (Foret et al., 2021). In each step of update, first compute the reweighted loss (Ø) - - wyl(I,, Φ) and compute its gradient w.r.t. d, i.e. Votnn( Then we can compute (Φ)) as (Φ) = psgn(V V Vo)) VoLn (0) 1-11 (1Voln
1/p where ! = Finally, we update the
16

---

Published as a conference paper at ICLR 2022
Supersised
Selfssgervised Representations
Supertiedd
Self-upervised Representations
Frequent
Representations
Represencations
Fruquant Closses
relevant
Rare Claoess
Baak
Figure 7: Examples of the semi-synthetic Datasets and Grad-CAM visualizations. SimCLR learns features from both left and right sides, whereas SL mainly learns label-relevant features from the left side of frequent data and ignore label-irrelen irreleaaelv features on the right side. Figure provide results the high-resolution images of the 10 CIFAR classes to make the results easier to interpret. Here we further visualize the results on original CIFAR-10 images.
model on the loss without reweighting L(0) by e VoInnoo c())). A detailed algorithm be viewed Algorithm 1.
Algorithm Reweighted Sharpness-Aware Minimization (rwSAM)
1: Input: the pre-training dataset D...
2: Output: learned representations Φ.
3: Stage I: compute the weight
4: for = 0 to MaxIter do
5: Randomly sample batch of examples {2:) from D...
6: Update the representations é on {x:)1_. minimize the loss.
x v/ LT()).
7: end for
8: Generate the weight with kernel density estimation:
Wt - ((fo(z))- -((().)))f((z)).))
9: Stage 1: reweighted SAM.
for = 0 to MaxTter do
11: Randomly sample a batch of examples {x; (x:),- from D..
Calculate c()) based on the reweighted loss (Ø). (o) 9-1
((VoLtco))1)) 1/2
= psgn (osgg((VoL.. (()
13: Update the representations fa; 1 minimize the loss and penalize the sharpness, v/ VVL((++(o))
14: end for
We select the hyperparameters and with cross validation. On ImageNet-LT and iNaturalist, p and a = 0.5. On CIFAR-1O-LT, = 5 and a = 1.2.
C.2 ADDITIONAL RESULTS
Table 3: ImageNet-I.T with Supervision.
We further introduce another evaluation protocol of the representations learned on imbalanced Ima- geNet: following the protocol of Kang et al. (2020); Yang Xu (2020), we fine-tune the representa- tions on imbalanced ImageNet dataset with super- vision, and then re-train the linear classifier with resampling, to compare with super- vised imbalanced recognition methods. In MoCo V2 pre-training, the standard data augmen-
Method
Backbone
Ace.
Supervised
ResNet-50
49.3
CRT (Kang al., 2020)
ResNet-50
52.0
LADE (Hong et al., 2021)
ResNeXt-50
53.0
RIDE (Wang et al., 2021)
ResNet-50
54.9
RIDE (Wang et al., 2021)
ResNeXt-50
56.4
MoCo V2
ResNet-50
55.0
MoCo V2+IWSAM
ResNet-50
55.5
17

---

Published as a conference paper at ICLR 2022
tation following He et al. (2020). In fine-tuning, we use RandAugment (Cubuk et al., 2020). For this evaluation, we further compare with CRT (Kang et al., 2020), LADE (Hong et al., 2021), and RIDE (Wang et al., 2021), which are strong methods tailored to supervised imbalanced recognition. Results are provided in Table 3. Supervised here refers to training the feature extractor and linear classifier with supervision on the imbalanced dataset directly. CRT first trains the feature extractor with supervision, and then re-trains the classifier with class-aware resampled loss. Note that CRT is performing better than Supervised, indicating that the composition of the head and features learned from supervised learning is more sensitive to imbalanced dataset than the quality of feature extractor itself.
Even with simple pre-training and fine-tuning pipeline, MoCo V2 representations can be comparable with much more complicated kate-of-the-ard tailored to supervised imbalanced recognition, further corroborating the power of SSL under class imbalance. With rwSAM, we can further improve the result of MoCo V2.
D ADDITIONAL RELATED WORK
D.1 SUPERVISED LEARNING WITH DATASET IMBALANCE
There exists long line of works studying supervised imbalanced classification (He & Garcia, 2009; Krawezyk, 2016). Early works on ensemble learning adjusted the boosting and bagging algorithms with resampling in the imbalanced setting (Guo & Viktor, 2004; Wang & Yao, 2009). Classical methods include resampling and reweighting. Hart (1968); Kubat et al. (1997); Chawla et al. (2002); He et al. (2008); Ando & Huang (2017); Buda et al. (2018); Hu et al. (2020) proposed to re-sample the data to make the frequent and rare classes appear with equal frequency in training. Re-weighting assigns different weights for head and tail classes and eases the optimization difficulty under class imbalance (Cui et al., 2019; Tang et al., 2020; Wang et al., 2017b; Huang et al., 2019). Byrd & Lipton (2019) empirically studied the effect of importance weighting and found out that importance weighting does not change the solution without regularization. Xu et al. (202 1) justified this finding with theoretical analysis based on the implicit bias of gradient descend on separable data.
Cao et al. (2019) initiated the idea of using re-weighted regularization and proposed the principle of regularizing rare classes more heavily. Re- weighted regularizaton is shown be typically more effective than re- re-weighting or sampliiing the losses. Cao et al. (2021) proposed to regularize the local curvature of loss on imbalanced and noisy datasets.
Works in the modern deep learning era also designed specific losses or training pipelines for imbal- anced recognition (Tang et al., 2020; Hong et al., 2021; Wang et al., 2021; Zhang et al., 2021). Lin et al. (2017) proposed to focus on hard examples to prevents easy examples from overwhelming the models during training. Meta-learning approaches meta-learned the weight or the ensemble (Wang et al., 2017b; Ren et al., 2018; Shu et al., 2019; Lee et al., 2020a). Liu et al. (2019); Jamal et al. (2020); Liu et al. (2020) improved the performance on the rare examples by explicitly encourages transfer learning. Re-calibration methods adjust the logits of the outputs with re-weighting (Tian et al., 2020; Menon et al., 2021).
Several works also studied the supervised representations under dataset imbalance. Kang et al. (2020); Wang et al. (2020) found out that the representations of supervised learning perform better than the classifier itself with class imbalance. Yang & Xu (2020) studied the effect of self-training and self-supervised pre-training on supervised imbalanced recognition classifiers. In contrast, the focus of our paper is the effect of class imbalance on self-supe representations.
D.2 SELF-SUPERVISED LEARNING
Earlier works on self-supervised learning learned visual representations by context prediction (Do- ersch et al., 2015; Wang et al., 2017a), solving puzzles (Noroozi & Favaro, 2016), and rotation prediction (Gidaris et al., 2018). Recent works on self-supervised learning successfully learn repre- sentations that approach the supervised baseline on ImageNet and various downstream tasks, and closed the gap with supervised pre-training. Contrastive learning methods attract positive pairs and drive apart negative pairs (He et al., 2020; Chen et al., 2020). Siamese networks predict the output of the other branch, and use stop- gradient to avoid collapsing (Grill et al., 2020; Chen & He, 2021). Clustering methods learn representations by performing clustering the representations and
18

---

Published as a conference paper at ICLR 2022
improve the representations with cluster index (Caron et al., 2020). Cole et al. (2021) investigated the effect of data quantity and task granularity on self-supervised representations. Goyal et al. (2021) large scale datasets in the wild, but they do not consider dataset
studied self-supervised methods imbalance explicitly. Kotar et al. (2021) studied whether dataset imbalance can have a significant impact contrastive learning representations. Madaan al. (2022) found out that self-supervised representations are better at continual learning than supervised representations. Several works have also theoretically studied the success of self-supervised learning (Arora et al., 2019; HaoChen et al., 2021: Wei et al., 2021; Lee et al., 2020b; Tian et al., 2021; Tosh et al., 2020; 2021). Our analysis in Section 3.1 is partially inspired by the work HaoChen al. (2020).
19

---

Published as a conference paper at ICLR 2022
E PROOF OF THEOREM 3.1
We notate data from the first class as x = 61 - qi 11
Te2 + ph; where E [ni] and q." E {0, 1]. Similarly, notate data from the second class as x (2)
61 9i Tez Ae, (2) where E [m2] and
(2)
di" {0, 1). We notate data from the third class as x e2 + psi where E [na]] Notice that all c(()) are independently sampled from (N I).
We first introduce the following lemma, which gives some high probability properties of independent Gaussian random variables.
Lemma E.1. Let & ~ (N, for E [n]. Then, for any n S poly(d), with probability at least
1 e---doo -di and large enough d, we have:
((,, S dtt,, KEi,, S d and ||E: S 4d for all E [n].
((,, S 3d3 for all
Proof of Lemma E.I. E ~ (0, 1) be two independent random variables. By the tail bound of normal distribution, we have
$
Pr (IKE e1) 2 dtt)
S d
(4)
By the tail bound of xa distribution, we have
Pr (IIIl - d 2 4d
S 2e Va
(5)
Since the directions of & and g are independent, we can bound their correlation with the norm of g times the projection of g onto E:
db
Pr ((S. 2 3d3) - Pr (I1Ella 2 Vi 2d8) + Pr (165', & >> dio ||
+ 2e
va
d
(6)
Since every & and Ej are independent when i + j. by the union bound, we know that with probability
at least 1 - (n² 2n)( d
+ 2e --2e-vo v). we have (5 e1)l S dd (E., e2)1 S t and ||| - d <
4d for all E [n]. and also KEr, E s 3dt for all + j. Since the error probability exponential in d, for large enough d, the error probability is smaller than ed which finishes the proof.
Using the above lemma, we can prove the following lemma which constructs linear classifier the empirical dataset with relatively large margin and small norm.
Lemma E.2. In the setting of Theorem 3.1, let w e1, w c,, w pd EE Apply Lemma E.1 to the set of all e! where is E [3] and E [ng]. When the high probability outcome of Lemma E. happens, the margin of classifter (w", wzz wz} is at least 1 O(d tb). Furthermore, we have ||ug]1 < O(d t).
Proof of Lemma E.2. When the high probability outcome of Lemma E. happens, we give lower bound on the margin for all data in the dataset. For data x in class 1, we have
w T r 1 + (5! calp 1 pd
w -1 + (s! eelp < -1 + tt
(8)
w/g
T 1
(e) 03 re2 + 15(21)
(1)
Σ
ng
(3)
<
Na(T + 1)
di
+
3ng d
pd
pd
d
20

---

Published as a conference paper at ICLR 2022
So the margin on data (1: 1) is
(1)
i x 33 x 2 1 - pd n2((T + +1)
d
3n3
d 2 - O(d
(10)
pd
d
(2) in class 2, the margin is at least to) Similarly, for data x;
(3) For data = Iz in class 3, we have
T
T x
(3)
E2 + p5: 2 7|1 d
3ns
ngd To
1 - 0(d (II)
W/
pd
pd
On the other hand,
w = (p ,e) S pd
(12)
w (pt -en) S pdtto
(13)
So the margin is Finally, noticing that ||wBl22 S
wg maxfwi 2, w² x} 2 wz T pa 2 Old idd
T
(14)
2uayd pd s 2d- to finishes the proof.
U
We also introduce the following helper lemma:
Lemma E.3. Let W E B33dd be arbitrary matrix, m 2 3. Then, we have
||W P3 2 W
min
Wall. + (IIWTWall2 (WWWTTl)))
(15)
where W1 E Rmnd and W2 E 33mm Furthermore, the minimum is achieved when W W.T W. W2.
=
Proof. On one hand, we have
[ = TT(WWT
(16)
WaWi=W min Tr(WWW1W,) W
(17)
min Tr( WTTww W2)
(18)
w.W.=w
< min W.Wi=w"
WT | + W Wall.),
(19)
where the inequality becomes equality if and only if W WT WT W2.
On the other hand, let W UEV be the SVD decomposition of W, where E E 3xdd is a diagonal matrix with σ1, 02 02; d3 its diagonal. For integers p, 3,
D denote the p x matrix
with Vol / 22, Vog at its first diagonal positions and 0 otherwise. we set W1 = r D V and
W2 = US 3xm then it can be verified that W = W,W,, and ||]] 1 (1WW,, 1 | Wa 12l. Therefore, the equality holds Equation 19, which finishes the proof."
Now are ready to prove the supervised learning part of Theorem 3.1:
Proof of Theorem 3.1 (supervised learning part). Let [101, 22 dh be three vectors in Rd that mini- mize | 11 + || |wm] 1| + | subject to the margin constraint w. 2 w, + for all empirical data (z. y) and y * y. To prove the supervised learning part of Theorem 3. 1, we will first prove that (w,,e,) + (12,e,) + e1 < O(d t) with high probability, and then use this result to prove the correlation between 62 and WSL.
21

---

Published as a conference paper at ICLR 2022
We frist apply Lemma 1 to the set of all c,4)) where & [3] and i E [Ma).. We consider the situation when the high probability outcome of Lemma E.1 holds (which happens with probability at least
I - --- ). By Lemma E,2, the constructed classifier {wī, wg. wz) } has margin a 2 1 - O +
in this case. As result, (2 (_ 2w2, a 2yg) } is classifier with margin 1 and norm bounded by
1 = + wi 11 + -Il-- a
1 =wlll= 2+ + 1 a
22+
(20)
a
a²
Let {w1, 22, di)) ) be min-norm linear classifier of the empirical dataset. Since its norm cannot be larger than the constructed one, we have || + || + || S Old 1)) By standard concentration inequality, when ni 2 poly(d), with probability at least 1 ed to we have
E " 1 ei S d
(2))
where the expectation is over all the data from class that satisfies of = O. By the definition of {w,, vi2, viz)) } we know (wi vhg) T xx!"
for all i [ma], hence averaging over all the class 1 data with q; = 0 and using the above inequality gives us
(w² wng) e 2 1 - l|:02 u/l12 dt to 21 2 1).
(22)
A similar analysis for class 2 data gives us
(#2- - 03) (- 2- Oc.
(23)
Now we prove that w1, 1h2, ths all have small correlation with ez. Without loss of generality, we
assume wi e t tz O. If 2 3, we have
(w), e2 + (202, e1 + (1), 2 (1+1-0(d 2 > 2.25 - O(d
(24)
which contradicts with | 12 + |لاماا + 1100 < 2 2 Old 1b). Therefore, there must be t < 2' hence
(1) + (102, 2 + e1)
(25)
2 (1+1- Old ) 2 + -1-t-O(d +1) + 22
(26)
2 2 - Old
(27)
22 - 0 +).
(28)
As result,
02) + (112 e2) 2 + e2)
(29)
< || 1 + |1 112 + || - (Wi, e1) (102, e1) (W3,, e1)
(30)
< (2 + to) - (2 O tb))
(31)
< (d
(32)
Now we turn to the analysis of Wst. Recall that we learn two matrices W, Rmxd and W2 Raxm that minimize [[W Wi W. + +I[,, W2 subject to the margin constraint (W2 > (Wr + 1, and the supervised representation is Ws.. = W.. According to Lemma E.3, we know that the solution W1 and W2 satisfy W2W1 = [ύ^, W2, wa]] and W₂ W2 = W.WT. Let U ΣU be the SVD decomposition, where Σ E Rmxm is non-negative
W. W22 = Wi WT diagonal matrix and U is unitary matrix. Since W2 has rank at most 3, there are at most 3 entries in Σ that are non-zero. Without loss of generality, we assume that all the non-zero entries of Σ are in the first 3 rows
Let Emxd and Σaxm be the matrices by reshaping Σ (deleting or padding all-O rows/columns) to the corresponding dimensions. We can write W, as W1 U Exx Vi for some unitary matrix
22

---

Published as a conference paper at ICLR 2022
Vi E Rdxd, where Σ mnx is the element-wise square root of mmxd Similarly, W2 = V22 some unitary matrix 1/2 E R3x3, Taking the product gives W,W1 = V22axd 3xm
for
Let WsL W [w1, Way" [m]] Now finishe the proof with
Σ ww, 02)² |W1e2112 = I0 Med S 11Vie211 [Faxx -12 VV2axaVieell
(33)
[W2Wie2lß = (101, 02) (122, 02)² + (103, 22)²=2²00000 Odd-b))
(34)
To prove the self-supervised learning part of Theorem 3.1, we first introduce the following lemma which gives some helpful properties of the empirical data matrix.
Lemma E.4. In the setting of Theorem 3.1, let M & [g[xx]] where the expectation is over empirical data. Then, when nı, 122 2 poly(d), with probability at least 1 - e we have: (1) oj Me2 2 22(d)), and (2) u Mu S O(1) for all u E IRd such that u. uee2 0 and ||u||2 =1.
Proof of Lemma E.4. Let n = n1 + n2 + ng.. We abuse notation and let & (i E [ri] be the set of all _!²) that appears in the empirical data. Let matrix M' EE, By standard concentration inequalities and union bound, for n 2 poly(d), with probability at least - - we have that J for all i + j and [M,, 1 / a for all i E [d]. In this case, for any vector u E IRd such that ||ul|2 and u uTe2 e2 = 0, we have
|M[ S 1
Mu S 2| 2u
2 2p + 222 - -|F S O1).
(35)
On the other hand, by the definition of data distirbution and standard concentration incqualities, for n 2 poly(d), with probability at least 1 -e- we have that: at least 1 of all data either is class 1 with q:" 1) = 1 or class 2 with 9. 1. and | Ei=1 Eill2 S ( In this case,
= (e]] (e) 2 T -2 Σ &1 1) 2 o E
2 2(77) = Qdd3). (36)
e
Using the above lemma, we can prove the self-supervised learning part of Theorem 3.1.
Proof of Theorem3. [pself-uupervised learning part). Let M = Ex, [xx J be the empirical data ma- trix, where the expectation over the dataset. Notice that self-supervised learning objective has the same minimizer as the matrix factorization objective ||M W W 1|.. by Sckart-Young-Mor rem we know that the span of Φ1 ...,.... Wm is exactly the span of the top m eigenvectors of matrix M. Let A > Aoauo where A is the i-th largest eigenvalue of M with the corresponding eigenvector 14 We decompose eg in the eigenvector basis e2 Σi= S.0
theo-
We first note that A 2 22d33) and max A, S O(1). Indeed, we know that E|M] diag(1 d d
d 2 d ..... d ). By standard matrix concentration bounds (e.g. Theorem 4.6.1 of Vershynin (2018)), we know that with probability at least - edd | - E[M]] < O t). By Weyl's inequality we know that max; [A:(T) As) < || - TlI so A 2 2(d5) and max, X < O(1).
By Lemma E.4, we know that with probability at least - we have 67 Mez 2 2(d and Mu < O1) for all u orthogonal to ez. To prove the result regarding self-supervised learning, we Tail
only need to prove that s 2 1 Odd-t) +) in this case.
23

---

Published as a conference paper at ICLR 2022
We first show that Çi 2.2 For contradiction, first assume S I 2-2 Define vector
51
Si 2i= 4.u
(37)
v1 52
which satisfies u uTez 0 and
||ul|2 = 1. Notice that
u T Mu - G9)A
AP
1
(38)
|ul13
1- St
max A
(39)
2
M(dd)) )
(40)
which contradicts to Mu < 01). Therefore, we have C 2 2. 1
To prove that ?? is close to 1, we let scalar = &t and define vector
-1110 Σ Se
(41)
which satisfies u T E2 = 0. Since C? 2 2. we have S 1 and ||]|2 S 1. As result, we have
u Mu
x 2 Mez 2 2(Pdt).
(42)
On the other hand, we know that x which means s? 2 1 - Odd
< (1). Comparing these two bounds gives 8 s O(d +).
24


Reviews:
[{"review_id": "u2fIj1hvf-m", "reviewer": "Reviewer_qJjn", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I enjoyed the paper. It reads well and has a robust set of experiments to investigate the effects of class imbalance on representation learning. Some suggestions and questions on how to improve the paper:\n\n- The effect of class difficulty: while random sampling for rare classes is a good strategy to take, I wonder how the class difficulty may play a role. This may become important as usually rare classes are also harder classes (even for annotators). So, an experimental setup to test this would be to use the class performance of a model on a balanced dataset to deliberately more frequently choose challenging classes as rare.\n- reSAM computational complexity: because of pairwise kernel within the regularisation term, I think this methods can't scale to very large datasets. So, what are your ideas on how to improve this? I thought of in-batch sampling, but that might be ineffective as it's possible samples in a batch are already far away from each other.\n\nMinor comments:\n- Abstract - first sentence: While the paper focuses on vision, SSL is not a vision specific. For example, NLP domain has been enjoying SSL since ELMo, BERT, ...\n- NLP applications: following from above, would be interesting to study the effect of dataset balance on NLP applications where SSL is a dominant pre-training approach.", "summary_of_the_paper": "This paper studies and compares the performance of self-supervised representation learning methods against supervised representation learning when there are class imbalance. It shows empirically that self-supervised methods are more robust to class imbalance, i.e. the performance gap between models trained on balanced and imbalanced datasets is smaller. The paper also investigates the quality of the features learnt by SSL vs SL, and shows both theoretically in a limited setting and empirically on synthetic datasets that features learnt by SSL are diverse and capture characteristics that might be useful for rare classes. Finally, they provide a regularisation method for SSL to encourage model to learn better features for rare classes without having access to labels.", "summary_of_the_review": "I think this is an important paper with experiments and limited theory to show and explain why SSL methods are more robust to class imbalance problem which also occur frequently in practice.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "fIbo1RGHOE", "reviewer": "Reviewer_Kf27", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nEmpirical analysis, with theoretical justification, shows that SSL is more roboust than SL in feature learning from imbalance datasets.\n\nUsing a semi-synthetic dataset, they show that SSL learns label-irrelevant features that are useful for classifying rare classes. \n\nAdapting SAM by reweighting more on low density instances improves performance.\n\nWeaknesses:\n\nTheorem 1 could have more explanation.\n\nTable 1:  Gap Freq and Gap Rare were not described\n\nTable 2;  Which of the four classes are frequent (or rare)?", "summary_of_the_paper": "The authors explore the robustness of feature learning via self-supervised learning (SSL) and supervised learning (SL) with imbalance datasets.  Generally, SL can learn better features than SSL, and features are better from balanced than from imbalance datasets.  However, with imbalance data, SSL is more robust than SL in terms of the performance difference of features learned from balance and imbalance datasets.  That is, the performance does not drop as much for SSL with imbalance data from balanced data.   The robustness is observed from both in-domain (ID)  and out-of-domain (OOD) tasks (different downstream tasks).  They hypothesized that \"SSL learns richer features from frequent data that are transferable to rare data.\"\n\nUsing a synthetic dataset with 2 frequent classes and 1 rare class, they observe that SL learns one feature to distinguish the two frequent classes and one feature to overfit the rare class.  However, SSL learns two features that can classify the 3 classes well. That is, SSL can learn label-irrelevant-but-transferable features from the frequent classes which can help classify the rare class.\n \nTo illustrate the observation from a synthetic dataset also exists in the real world, they construct a semi-synthetic dataset.  From CIFAR 10, they generate 5 fequent classes and 5 rare classes.  For the frequent classes, the right half of the image is replaced by a random half image, ie not relevant to the label.  For the rare classes, the left half is replaced by blank.  Using activation maps, they observe that SL learn features from only the left half (relevant to the label) but not from the right half (irrelevant to the label).   However, SSL learns features from both halves.\n\nTo further improve robustness, they adapt SAM to the imbalance scenario: rwSAM. SAM improves model generalization by penalizing loss sharpness. For SAM, the loss is uniformly low in the neighboring area.   To have a flatter region for rare examples, rwSAM reweights rare examples in the inner maximization step of SAM.  Since labels are not available, they estimate kernel density on feature vectors and the weight is inversely proportional to the density.  On two datasets, empirical results indicate rwSAM improves performance over SAM.\n\n", "summary_of_the_review": "The authors propose well-designed experiments to show SSL is more robust than SL in feature learning from imbalance data and SSL learns label-irrelevant features that could be useful for the rare classes.   The presentation can be improved as indicated above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DQ5q96cJ5jg", "reviewer": "Reviewer_8MoR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper focuses on class-imbalanced learning and shows that self-supervised pre-training yields representations that are more robust to dataset imbalance.\n\nStrength:\n1) This paper is well-written and the conclusion is clear.\n\nWeakness:\n1) The conclusions are mainly observed from empirical results. There lack of theoretical insights. \n2) The generalization of the conclusions is not clear. Given an imbalanced dataset, how to decide which algorithm should I adopt? For example, on what conditions self-supervised learning is better than supervised learning, and on what conditions are not?\n3) Some class-imbalanced learning methods are not compared. In section 4.1, the authors report the performance of the proposed rwSAM on imbalanced datasets. More related algorithms should be compared to show the effectiveness of the proposal.\n", "summary_of_the_paper": "This paper focuses on class-imbalanced learning and shows that self-supervised pre-training yields representations that are more robust to dataset imbalance.\n", "summary_of_the_review": "This paper focuses on class-imbalanced learning and shows that self-supervised pre-training yields representations that are more robust to dataset imbalance. The problem is interesting. But the results are mainly observed from empirical results, the generalization of the conclusions is not clear. The novelty and contribution of the paper are limited.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7NKD4SjYKV_", "reviewer": "Reviewer_Jyb6", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written in general and its motivation is clear. \n\nWeaknesses: \n\n- The only task considered in the paper is image classification using the standard accuracy as the evaluation metric. Is the observed robustness also valid for other tasks? Although the paper presents a large range of experiments, the conclusions are less general than what is sold. The imbalanced datasets used in the paper are CIFAR-10-LT and ImageNet-LT, which are versions of CIFAR-10 and ImageNet that are originally balanced. Datasets that follow an intrinsic long-tail distribution (e.g., iNaturalist 2018) are not considered. Although the superior results of SSL in imbalanced settings are promising (e.g. the apparent robustness in Figure 2), it would be interesting to know if the conclusions in the paper generalize to datasets that are originally imbalanced (e.g., iNaturalist 2018).\n\n- The improvement of the proposed regularization in Tables 1 and 2 does not seem statistically significant.\n\n- The toy dataset setup in Section 3.1 is difficult to read.\n\n\nDespite the weaknesses mentioned above, I think that the paper is worth publishing. It considers a problem that is relevant to the machine learning and computer vision communities. It shows that, in the OOD case or very imbalanced case, it is better to use SSL techniques (e.g. SimCLR or MoCo v2) since they do not overfit to the training samples and labels, and the imbalanced factor does not matter. \nThe paper gives a sensible explanation of why this is the case, with detailed ablation studies. \nAlthough Table 2 uses diverse datasets such as CUB, Cars, Aircrafts and Pets, the improvement does not seem significant. It is then difficult to know whether or not the conclusions of the paper generalize to datasets other than CIFAR-10 and ImageNet.\n\n\n\n\n\n\nminor typo in titles of Figure 1: \"Imabalanced\" => \"Imbalanced\"", "summary_of_the_paper": "The paper studies the differences between representations pretrained with Self-Supervised Learning (SSL) and the standard Supervised Learning (SL) frameworks in the In-Domain (ID) and Out-Of-Domain (OOD) settings of the image classification task with an imbalanced dataset. \n\nThe paper presents different results that are relevant to the computer vision and machine learning community: \n1) In the ID setting, representations pretrained with SL outperform those pretrained with SSL. However, in the OOD setting, representations pretrained with SSL outperform those pretrained with SL and are even robust to the imbalance factor.\n2) An analysis in Section 3.1 on a toy dataset and semi-synthetic data (by cropping and fusing half images during pretraining) in Section 3.2 validate that SSL methods learn representations that do not overfit to labels and show improved accuracy at test time.\n3) The paper also proposes a regularization framework (called rwSAM) that promotes flatter landscape for rare examples to improve performance at test time (see Table 1 and 2).", "summary_of_the_review": "The paper considers the imbalanced dataset problem that is relevant to the machine learning and computer vision communities. The proposed analysis also makes sense and is interesting to the ML and CV communities.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is proposed to investigate the robustness of self-supervised learning (SSL) and supervised learning (SL) in both balanced (in domain) and imbalanced (out of domain) settings. It can be concluded that SL can regularly learn better representations than SSL, and representations are better from balanced than from imbalanced datasets. The SSL is more robust than SL in the imbalanced settings, which is the crucial of this paper. Expect the experimental results, the authors also provided theoretical analysis to support their claims. The authors also extend a well-established method SAM into the Reweighted SAM as the technical contribution to better address the imbalanced setting. The paper is well written with clear logic to follow.
Decision: Accept (Spotlight)