Mathilde Caron
email: mathilde@fb.com

Ishan Misra

Julien Mairal

Priya Goyal

Piotr Bojanowski

Armand Joulin

Unsupervised Learning of Visual Features by Contrasting Cluster Assignments

Unsupervised image representations have significantly reduced the gap with supervised pretraining, notably with the recent achievements of contrastive learning methods. These contrastive methods typically work online and rely on a large number of explicit pairwise feature comparisons, which is computationally challenging. In this paper, we propose an online algorithm, SwAV, that takes advantage of contrastive methods without requiring to compute pairwise comparisons. Specifically, our method simultaneously clusters the data while enforcing consistency between cluster assignments produced for different augmentations (or "views") of the same image, instead of comparing features directly as in contrastive learning. Simply put, we use a "swapped" prediction mechanism where we predict the code of a view from the representation of another view. Our method can be trained with large and small batches and can scale to unlimited amounts of data. Compared to previous contrastive methods, our method is more memory efficient since it does not require a large memory bank or a special momentum network. In addition, we also propose a new data augmentation strategy, multi-crop, that uses a mix of views with different resolutions in place of two full-resolution views, without increasing the memory or compute requirements. We validate our findings by achieving 75.3% top-1 accuracy on ImageNet with ResNet-50, as well as surpassing supervised pretraining on all the considered transfer tasks.

Introduction

Unsupervised visual representation learning, or self-supervised learning, aims at obtaining features without using manual annotations and is rapidly closing the performance gap with supervised pretraining in computer vision [START_REF] Chen | A simple framework for contrastive learning of visual representations[END_REF][START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF][START_REF] Misra | Self-supervised learning of pretext-invariant representations[END_REF]. Many recent state-of-the-art methods build upon the instance discrimination task that considers each image of the dataset (or "instance") and its transformations as a separate class [START_REF] Dosovitskiy | Discriminative unsupervised feature learning with exemplar convolutional neural networks[END_REF]. This task yields representations that are able to discriminate between different images, while achieving some invariance to image transformations. Recent self-supervised methods that use instance discrimination rely on a combination of two elements: (i) a contrastive loss [START_REF] Hadsell | Dimensionality reduction by learning an invariant mapping[END_REF] and (ii) a set of image transformations. The contrastive loss removes the notion of instance classes by directly comparing image features while the image transformations define the invariances encoded in the features. Both elements are essential to the quality of the resulting networks [START_REF] Chen | A simple framework for contrastive learning of visual representations[END_REF][START_REF] Misra | Self-supervised learning of pretext-invariant representations[END_REF] and our work improves upon both the objective function and the transformations.

The contrastive loss explicitly compares pairs of image representations to push away representations from different images while pulling together those from transformations, or views, of the same image. Since computing all the pairwise comparisons on a large dataset is not practical, most implementations approximate the loss by reducing the number of comparisons to random subsets of images during training [START_REF] Chen | A simple framework for contrastive learning of visual representations[END_REF][START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF][START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF]. An alternative to approximate the loss is to approximate the task-that is to relax the instance discrimination problem. For example, clustering-based methods discriminate between groups of images with similar features instead of individual images [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF]. The objective in clustering is tractable, but it does not scale well with the dataset as it requires a pass over the entire dataset to form image "codes" (i.e., cluster assignments) that are used as targets during training. In this work, we use a different paradigm and propose to compute the codes online while enforcing consistency between codes obtained from views of the same image. Comparing cluster assignments allows to contrast different image views while not relying on explicit pairwise feature comparisons. Specifically, we propose a simple "swapped" prediction problem where we predict the code of a view from the representation of another view. We learn features by Swapping Assignments between multiple Views of the same image (SwAV). The features and the codes are learned online, allowing our method to scale to potentially unlimited amounts of data. In addition, SwAV works with small and large batch sizes and does not need a large memory bank [START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF] or a momentum encoder [START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF].

Besides our online clustering-based method, we also propose an improvement to the image transformations. Most contrastive methods compare one pair of transformations per image, even though there is evidence that comparing more views during training improves the resulting model [START_REF] Misra | Self-supervised learning of pretext-invariant representations[END_REF]. In this work, we propose multi-crop that uses smaller-sized images to increase the number of views while not increasing the memory or computational requirements during training. We also observe that mapping small parts of a scene to more global views significantly boosts the performance. Directly working with downsized images introduces a bias in the features [START_REF] Touvron | Fixing the train-test resolution discrepancy[END_REF], which can be avoided by using a mix of different sizes. Our strategy is simple, yet effective, and can be applied to many self-supervised methods with consistent gain in performance.

We validate our contributions by evaluating our method on several standard self-supervised benchmarks. In particular, on the ImageNet linear evaluation protocol, we reach 75.3% top-1 accuracy with a standard ResNet-50, and 78.5% with a wider model. We also show that our multi-crop strategy is general, and improves the performance of different self-supervised methods, namely SimCLR [START_REF] Chen | A simple framework for contrastive learning of visual representations[END_REF], DeepCluster [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF], and SeLa [START_REF] Asano | Self-labelling via simultaneous clustering and representation learning[END_REF], between 2% and 4% top-1 accuracy on ImageNet. Overall, we make the following contributions:

• We propose a scalable online clustering loss that improves performance by +2% on ImageNet and works in both large and small batch settings without a large memory bank or a momentum encoder.

• We introduce the multi-crop strategy to increase the number of views of an image with no computational or memory overhead. We observe a consistent improvement of between 2% and 4% on ImageNet with this strategy on several self-supervised methods.

• Combining both technical contributions into a single model, we improve the performance of selfsupervised by +4.2% on ImageNet with a standard ResNet and outperforms supervised ImageNet pretraining on multiple downstream tasks. This is the first method to do so without finetuning the features, i.e., only with a linear classifier on top of frozen features.

Related Work

Instance and contrastive learning. Instance-level classification considers each image in a dataset as its own class [START_REF] Bojanowski | Unsupervised learning by predicting noise[END_REF][START_REF] Dosovitskiy | Discriminative unsupervised feature learning with exemplar convolutional neural networks[END_REF][START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF]. Dosovitskiy et al. [START_REF] Dosovitskiy | Discriminative unsupervised feature learning with exemplar convolutional neural networks[END_REF] assign a class explicitly to each image and learn a linear classifier with as many classes as images in the dataset. As this approach becomes quickly intractable, Wu et al. [START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF] mitigate this issue by replacing the classifier with a memory bank that stores previously-computed representations. They rely on noise contrastive estimation [START_REF] Gutmann | Noise-contrastive estimation: A new estimation principle for unnormalized statistical models[END_REF] to compare instances, which is a special form of contrastive learning [START_REF] Hjelm | Learning deep representations by mutual information estimation and maximization[END_REF][START_REF] Oord | Representation learning with contrastive predictive coding[END_REF]. He et al. [START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF] improve the training of contrastive methods by storing representations from a momentum encoder instead of the trained network. More recently, Chen et al. [START_REF] Chen | A simple framework for contrastive learning of visual representations[END_REF] show that the memory bank can be entirely replaced with the elements from the same batch if the batch is large enough. In contrast to this line of works, we avoid comparing every pair of images by mapping the image features to a set of trainable prototype vectors.

Clustering for deep representation learning. Our work is also related to clustering-based methods [START_REF] Asano | Self-labelling via simultaneous clustering and representation learning[END_REF][START_REF] Bautista | Cliquecnn: Deep unsupervised exemplar learning[END_REF][START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF][START_REF] Caron | Unsupervised pre-training of image features on non-curated data[END_REF][START_REF] Gidaris | Learning representations by predicting bags of visual words[END_REF][START_REF] Huang | Unsupervised deep learning by neighbourhood discovery[END_REF][START_REF] Xie | Unsupervised deep embedding for clustering analysis[END_REF][START_REF] Yan | ClusterFit: Improving generalization of visual representations[END_REF][START_REF] Yang | Joint unsupervised learning of deep representations and image clusters[END_REF][START_REF] Zhuang | Local aggregation for unsupervised learning of visual embeddings[END_REF]. Caron et al. [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF] show that k-means assignments can be used as pseudo-labels to learn visual representations. This method scales to large uncurated dataset and can be used for pre-training of supervised networks [START_REF] Caron | Unsupervised pre-training of image features on non-curated data[END_REF]. However, their formulation is not principled and recently, Asano et al. [START_REF] Asano | Self-labelling via simultaneous clustering and representation learning[END_REF] show how to cast the pseudo-label assignment problem as an instance of the optimal transport problem. We consider a similar formulation to map representations to prototype vectors, but unlike [START_REF] Asano | Self-labelling via simultaneous clustering and representation learning[END_REF] we keep the soft assignment produced by the Sinkhorn-Knopp algorithm [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF] instead of approximating it into a hard assignment. Besides, unlike Caron et al. [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF][START_REF] Caron | Unsupervised pre-training of image features on non-curated data[END_REF] and Asano et al. [START_REF] Asano | Self-labelling via simultaneous clustering and representation learning[END_REF], we obtain online assignments which allows our method to scale gracefully to any dataset size.

Handcrafted pretext tasks. Many self-supervised methods manipulate the input data to extract a supervised signal in the form of a pretext task [START_REF] Agrawal | Learning to see by moving[END_REF][START_REF] Doersch | Unsupervised visual representation learning by context prediction[END_REF][START_REF] Jenni | Self-supervised feature learning by learning to spot artifacts[END_REF][START_REF] Kim | Learning image representations by completing damaged jigsaw puzzles[END_REF][START_REF] Larsson | Learning representations for automatic colorization[END_REF][START_REF] Mahendran | Cross pixel optical flow similarity for self-supervised learning[END_REF][START_REF] Misra | Shuffle and learn: unsupervised learning using temporal order verification[END_REF][START_REF] Pathak | Learning features by watching objects move[END_REF][START_REF] Pathak | Context encoders: Feature learning by inpainting[END_REF][START_REF] Wang | Unsupervised learning of visual representations using videos[END_REF][START_REF] Wang | Transitive invariance for self-supervised visual representation learning[END_REF][START_REF] Zhang | Split-brain autoencoders: Unsupervised learning by crosschannel prediction[END_REF]. We refer the reader to Jing et al. [START_REF] Jing | Self-supervised visual feature learning with deep neural networks: A survey[END_REF] for an exhaustive and detailed review of this literature. Of particular interest, Misra and van der Maaten [START_REF] Misra | Self-supervised learning of pretext-invariant representations[END_REF] propose to encode the jigsaw puzzle task [START_REF] Noroozi | Unsupervised learning of visual representations by solving jigsaw puzzles[END_REF] as an invariant for contrastive learning. Jigsaw tiles are non-overlapping crops with small resolution that cover only part (∼20%) of the entire image area. In contrast, our multi-crop strategy consists in simply sampling multiple random crops with two different sizes: a standard size and a smaller one.

Method

Our goal is to learn visual features in an online fashion without supervision. To that effect, we propose an online clustering-based self-supervised method. Typical clustering-based methods [START_REF] Asano | Self-labelling via simultaneous clustering and representation learning[END_REF][START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF] are offline in the sense that they alternate between a cluster assignment step where image features of the entire dataset are clustered, and a training step where the cluster assignments, i.e., "codes" are predicted for different image views. Unfortunately, these methods are not suitable for online learning as they require multiple passes over the dataset to compute the image features necessary for clustering.

In this section, we describe an alternative where we enforce consistency between codes from different augmentations of the same image. This solution is inspired by contrastive instance learning [START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF] as we do not consider the codes as a target, but only enforce consistent mapping between views of the same image. Our method can be interpreted as a way of contrasting between multiple image views by comparing their cluster assignments instead of their features.

More precisely, we compute a code from an augmented version of the image and predict this code from other augmented versions of the same image. Given two image features z t and z s from two different augmentations of the same image, we compute their codes q t and q s by matching these features to a set of K prototypes {c 1 , . . . , c K }. We then setup a "swapped" prediction problem with the following loss function:

L(z t , z s ) = (z t , q s ) + (z s , q t ), (1)
where the function (z, q) measures the fit between features z and a code q, as detailed later. Intuitively, our method compares the features z t and z s using the intermediate codes q t and q s . If these two features capture the same information, it should be possible to predict the code from the other feature. A similar comparison appears in contrastive learning where features are compared directly [START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF]. In Fig. 1, we illustrate the relation between contrastive learning and our method.

Online clustering

Each image x n is transformed into an augmented view x nt by applying a transformation t sampled from the set T of image transformations. The augmented view is mapped to a vector representation by applying a non-linear mapping f θ to x nt . The feature is then projected to the unit sphere, i.e., z nt = f θ (x nt )/ f θ (x nt ) 2 . We then compute a code q nt from this feature by mapping z nt to a set of K trainable prototypes vectors, {c 1 , . . . , c K }. We denote by C the matrix whose columns are the c 1 , . . . , c k . We now describe how to compute these codes and update the prototypes online.

Swapped prediction problem. The loss function in Eq. ( 1) has two terms that setup the "swapped" prediction problem of predicting the code q t from the feature z s , and q s from z t . Each term represents the cross entropy loss between the code and the probability obtained by taking a softmax of the dot In contrastive learning methods applied to instance classification, the features from different transformations of the same images are compared directly to each other. In SwAV, we first obtain "codes" by assigning features to prototype vectors. We then solve a "swapped" prediction problem wherein the codes obtained from one data augmented view are predicted using the other view. Thus, SwAV does not directly compare image features. Prototype vectors are learned along with the ConvNet parameters by backpropragation.

products of z i and all prototypes in C, i.e.,

(z t , q s ) = - k q (k) s log p (k)
t , where p

(k) t = exp 1 τ z t c k k exp 1 τ z t c k . ( 2
)
where τ is a temperature parameter [START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF]. Taking this loss over all the images and pairs of data augmentations leads to the following loss function for the swapped prediction problem:

- 1 N N n=1 s,t∼T 1 τ z nt Cq ns + 1 τ z ns Cq nt -log K k=1 exp z nt c k τ -log K k=1 exp z ns c k τ .
This loss function is jointly minimized with respect to the prototypes C and the parameters θ of the image encoder f θ used to produce the features (z nt ) n,t .

Computing codes online. In order to make our method online, we compute the codes using only the image features within a batch. Intuitively, as the prototypes C are used across different batches, SwAV clusters multiple instances to the prototypes. We compute codes using the prototypes C such that all the examples in a batch are equally partitioned by the prototypes. This equipartition constraint ensures that the codes for different images in a batch are distinct, thus preventing the trivial solution where every image has the same code. Given B feature vectors Z = [z 1 , . . . , z B ], we are interested in mapping them to the prototypes C = [c 1 , . . . , c K ]. We denote this mapping or codes by Q = [q 1 , . . . , q B ], and optimize Q to maximize the similarity between the features and the prototypes , i.e., max

Q∈Q Tr Q C Z + εH(Q), (3)
where H is the entropy function,

H(Q) = -ij Q ij log Q ij
and ε is a parameter that controls the smoothness of the mapping. We observe that a strong entropy regularization (i.e. using a high ε) generally leads to a trivial solution where all samples collapse into an unique representation and are all assigned uniformely to all prototypes. Hence, in practice we keep ε low. Asano et al. [START_REF] Asano | Self-labelling via simultaneous clustering and representation learning[END_REF] enforce an equal partition by constraining the matrix Q to belong to the transportation polytope. They work on the full dataset, and we propose to adapt their solution to work on minibatches by restricting the transportation polytope to the minibatch:

Q = Q ∈ R K×B + | Q1 B = 1 K 1 K , Q 1 K = 1 B 1 B , (4)
where 1 K denotes the vector of ones in dimension K. These constraints enforce that on average each prototype is selected at least B K times in the batch. Once a continuous solution Q * to Prob. (3) is found, a discrete code can be obtained by using a rounding procedure [START_REF] Asano | Self-labelling via simultaneous clustering and representation learning[END_REF]. Empirically, we found that discrete codes work well when computing codes in an offline manner on the full dataset as in Asano et al. [START_REF] Asano | Self-labelling via simultaneous clustering and representation learning[END_REF] we use only minibatches, using the discrete codes performs worse than using the continuous codes. An explanation is that the rounding needed to obtain discrete codes is a more aggressive optimization step than gradient updates. While it makes the model converge rapidly, it leads to a worse solution.

We thus preserve the soft code Q * instead of rounding it. These soft codes Q * are the solution of Prob.

(3) over the set Q and takes the form of a normalized exponential matrix [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF]:

Q * = Diag(u) exp C Z ε Diag(v), (5)
where u and v are renormalization vectors in R K and R B respectively. The renormalization vectors are computed using a small number of matrix multiplications using the iterative Sinkhorn-Knopp algorithm [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF]. In practice, we observe that using only 3 iterations is fast and sufficient to obtain good performance. Indeed, this algorithm can be efficiently implemented on GPU, and the alignment of 4K features to 3K codes takes 35ms in our experiments, see § 4.

Working with small batches. When the number B of batch features is too small compared to the number of prototypes K, it is impossible to equally partition the batch into the K prototypes. Therefore, when working with small batches, we use features from the previous batches to augment the size of Z in Prob. [START_REF] Bachman | Learning representations by maximizing mutual information across views[END_REF]. Then, we only use the codes of the batch features in our training loss. In practice, we store around 3K features, i.e., in the same range as the number of code vectors. This means that we only keep features from the last 15 batches with a batch size of 256, while contrastive methods typically need to store the last 65K instances obtained from the last 250 batches [START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF].

Multi-crop: Augmenting views with smaller images

As noted in prior works [START_REF] Chen | A simple framework for contrastive learning of visual representations[END_REF][START_REF] Misra | Self-supervised learning of pretext-invariant representations[END_REF], comparing random crops of an image plays a central role by capturing information in terms of relations between parts of a scene or an object. Unfortunately, increasing the number of crops or "views" quadratically increases the memory and compute requirements. We propose a multi-crop strategy where we use two standard resolution crops and sample V additional low resolution crops that cover only small parts of the image. Using low resolution images ensures only a small increase in the compute cost. Specifically, we generalize the loss of Eq (1):

L(z t1 , z t2 , . . . , z t V +2 ) = i∈{1,2} V +2 v=1 1 v =i (z tv , q ti ). (6)
Note that we compute codes using only the full resolution crops. Indeed, computing codes for all crops increases the computational time and we observe in practice that it also alters the transfer performance of the resulting network. An explanation is that using only partial information (small crops cover only small area of images) degrades the assignment quality. Figure 3 shows that multi-crop improves the performance of several self-supervised methods and is a promising augmentation strategy.

Main Results

We analyze the features learned by SwAV by transfer learning on multiple datasets. We implement in SwAV the improvements used in SimCLR, i.e., LARS [START_REF] You | Large batch training of convolutional networks[END_REF], cosine learning rate [START_REF] Loshchilov | Sgdr: Stochastic gradient descent with warm restarts[END_REF][START_REF] Misra | Self-supervised learning of pretext-invariant representations[END_REF] and the MLP projection head [START_REF] Chen | A simple framework for contrastive learning of visual representations[END_REF]. We provide the full details and hyperparameters for pretraining and transfer learning in the supplementary material.

Evaluating the unsupervised features on ImageNet

We evaluate the features of a ResNet-50 [START_REF] He | Deep residual learning for image recognition[END_REF] trained with SwAV on ImageNet by two experiments: linear classification on frozen features and semi-supervised learning by finetuning with few labels. When using frozen features (Fig. 2 left), SwAV outperforms the state of the art by +4.2% top-1 accuracy and is only 1.2% below the performance of a fully supervised model. Note that we train SwAV during 800 epochs with large batches (4096). We refer to Fig. 3 for results with shorter trainings and to Table 3 for experiments with small batches. On semi-supervised learning (Table 1), SwAV outperforms other self-supervised methods and is on par with state-of-the-art semi-supervised models [START_REF] Sohn | Fixmatch: Simplifying semi-supervised learning with consistency and confidence[END_REF], despite the fact that SwAV is not specifically designed for semi-supervised learning.

Variants of ResNet-50. Figure 2 (right) shows the performance of multiple variants of ResNet-50 with different widths [START_REF] Kolesnikov | Revisiting self-supervised visual representation learning[END_REF]. The performance of our model increases with the width of the model, and follows a similar trend to the one obtained with supervised learning. When compared with concurrent work like SimCLR, we see that SwAV reduces the difference with supervised models even further. Indeed, for large architectures, our method shrinks the gap with supervised training to 0.6%.

Transferring unsupervised features to downstream tasks

We test the generalization of ResNet-50 features trained with SwAV on ImageNet (without labels) by transferring to several downstream vision tasks. In Table 2, we compare the performance of SwAV features with ImageNet supervised pretraining. First, we report the linear classification performance on the Places205 [START_REF] Zhou | Learning deep features for scene recognition using places database[END_REF], VOC07 [START_REF] Everingham | The pascal visual object classes (voc) challenge[END_REF], and iNaturalist2018 [START_REF] Van Horn | The inaturalist species classification and detection dataset[END_REF] datasets. Our method outperforms supervised features on all three datasets. Note that SwAV is the first self-supervised method to surpass ImageNet supervised features on these datasets. Second, we report network finetuning on object detection on VOC07+12 using Faster R-CNN [START_REF] Ren | Faster r-cnn: Towards real-time object detection with region proposal networks[END_REF] and on COCO [START_REF] Lin | Microsoft coco: Common objects in context[END_REF] with DETR [START_REF] Carion | End-to-end object detection with transformers[END_REF]. DETR is a recent object detection framework that reaches competitive performance with Faster R-CNN while being conceptually simpler and trainable end-to-end. We use DETR because, unlike Faster R-CNN [START_REF] He | Rethinking imagenet pre-training[END_REF], using a pretrained backbone in this framework is crucial to obtain good results compared to training from scratch [START_REF] Carion | End-to-end object detection with transformers[END_REF]. In Table 2, we show that SwAV outperforms the supervised pretrained model on both VOC07+12 and COCO datasets. Note that this is line with previous works that also show that self-supervision can outperform supervised pretraining on object detection [START_REF] Gidaris | Learning representations by predicting bags of visual words[END_REF][START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF][START_REF] Misra | Self-supervised learning of pretext-invariant representations[END_REF]. We report more detection evaluation metrics and results from other self-supervised methods in the supplementary material. Overall, our SwAV ResNet-50 model surpasses supervised ImageNet pretraining on all the considered transfer tasks and datasets. We have released this model so other researchers might also benefit by replacing the ImageNet supervised network with our model.

Training with small batches

We train SwAV with small batches of 256 images on 4 GPUs and compare with MoCov2 and SimCLR trained in the same setup. In Table 3, we see that SwAV maintains state-of-the-art performance even when trained in the small batch setting. Note that SwAV only stores a queue of 3, 840 features. In comparison, to obtain good performance, MoCov2 needs to store 65, 536 features while keeping an additional momentum encoder network. When SwAV is trained using 2×160 + 4×96 crops, SwAV has a running time 1.2× higher than SimCLR with 2×224 crops and is around 1.4× slower than MoCov2 due to the additional back-propagation [START_REF] Chen | Improved baselines with momentum contrastive learning[END_REF]. Hence, one epoch of MoCov2 or SimCLR is faster in wall clock time than one of SwAV, but these methods need more epochs for good downstream performance. Indeed, as shown in Table 3, SwAV learns much faster and reaches higher performance in 4× fewer epochs: 72% after 200 epochs (102 hours) while MoCov2 needs 800 epochs to achieve 71.1%. Increasing the resolution and the number of epochs, SwAV reaches 74.3% with a small batch size, a small number of stored features and no momentum encoder. Finally, note that SwAV could be combined with a momentum mechanism and a large queue [START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF]; we leave these explorations to future work. DeepCluster-v2 and SeLa-v2, which are obtained by applying various training improvements introduced in other self-supervised learning papers to DeepCluster [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF] and SeLa [START_REF] Asano | Self-labelling via simultaneous clustering and representation learning[END_REF]. Among these improvements are the use of stronger data augmentation [START_REF] Chen | A simple framework for contrastive learning of visual representations[END_REF], MLP projection head [START_REF] Chen | A simple framework for contrastive learning of visual representations[END_REF], cosine learning rate schedule [START_REF] Misra | Self-supervised learning of pretext-invariant representations[END_REF], temperature parameter [START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF], memory bank [START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF], multi-clustering [START_REF] Asano | Self-labelling via simultaneous clustering and representation learning[END_REF], etc. Full implementation details can be found in the supplementary material. Besides, we also improve DeepCluster model by introducing explicit comparisons to k-means centroids, which increase stability and performance. Indeed, a main issue in DeepCluster is that there is no correspondance between two consecutive cluster assignments. Hence, the final classification layer learned for an assignment becomes irrelevant for the following one and thus needs to be re-initialized from scratch at each epoch. This considerably disrupts the convnet training. In DeepCluster-v2, instead of learning a classification layer predicting the cluster assignments, we perform explicit comparison between features and centroids.

Comparing clustering with contrastive instance learning. In Fig. 3 (left), we make a best effort fair comparison between clustering-based and contrastive instance (SimCLR) methods by implementating these methods with the same data augmentation, number of epochs, batch-sizes, etc. In this setting, we observe that SwAV and DeepCluster-v2 outperform SimCLR by 2% without multi-crop and by 3.5% with multi-crop. This suggests the learning potential of clustering-based methods over instance classification.

Advantage of SwAV compared to DeepCluster-v2. In Fig. 3 (left), we observe that SwAV performs on par with DeepCluster-v2. In addition, we train DeepCluster-v2 in SwAV best setting (800 epochs -8 crops) and obtain 75.2% top-1 accuracy on ImageNet (versus 75.3% for SwAV). However, unlike SwAV, DeepCluster-v2 is not online which makes it impractical for extremely large datasets ( § 5.4). For billion scale trainings for example, a single pass on the dataset is usually performed [START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF]. DeepCluster-v2 cannot be trained for only one epoch since it works by performing several passes on the dataset to regularly update centroids and cluster assignments for each image.

As a matter of fact, DeepCluster-v2 can be interpreted as a special case of our proposed swapping mechanism: swapping is done across epochs rather than within a batch. Given a crop of an image DeepCluster-v2 predicts the assignment of another crop, which was obtained at the previous epoch. SwAV swaps assignments directly at the batch level and can thus work online.

Applying the multi-crop strategy to different methods

In Fig. 3 (left), we report the impact of applying our multi-crop strategy on the performance of a selection of other methods. Details of how we apply multi-crop to SimCLR loss can be found in the supplementary material. We see that the multi-crop strategy consistently improves the performance for all the considered methods by a significant margin of 2-4% top-1 accuracy. Interestingly, multi-crop seems to benefit more clustering-based methods than contrastive methods. We note that multi-crop does not improve the supervised model.

Method

Impact of longer training

In Fig. 3 (right), we show the impact of the number of training epochs on performance for SwAV with multi-crop. We train separate models for 100, 200, 400 and 800 epochs and report the top-1 accuracy on ImageNet using the linear classification evaluation. We train each ResNet-50 on 64 V100 16GB GPUs and a batch size of 4096. While SwAV benefits from longer training, it already achieves strong performance after 100 epochs, i.e., 72.1% in 6h15.

Unsupervised pretraining on a large uncurated dataset

We evaluate SwAV on random, uncurated images that have different properties from ImageNet which allows us to test if our online clustering scheme and multi-crop augmentation work out of the box. In particular, we pretrain SwAV on an uncurated dataset of 1 billion random public non-EU images from Instagram. We test if SwAV can serve as a pretraining method for supervised learning. In Fig. 4 (left), we measure the performance of ResNet-50 models when transferring to ImageNet with frozen or finetuned features. We report the results from He et al. [START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF] but note that their setting is different. They use a curated set of Instagram images, filtered by hashtags similar to ImageNet labels [START_REF] Mahajan | Exploring the limits of weakly supervised pretraining[END_REF]. We compare SwAV with a randomly initialized network and with a network pretrained on the same data using SimCLR. We observe that SwAV maintains a similar gain of 6% over SimCLR as when pretrained on ImageNet (Fig. 2), showing that our improvements do not depend on the data distribution. We also see that pretraining with SwAV on random images significantly improves over training from scratch on ImageNet (+1.3%) [START_REF] Caron | Unsupervised pre-training of image features on non-curated data[END_REF][START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF]. This result is in line with Caron et al. [START_REF] Caron | Unsupervised pre-training of image features on non-curated data[END_REF] and He et al. [START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF]. In Fig. 4 (right), we explore the limits of pretraining as we increase the model capacity. We consider the variants of the ResNeXt architecture [START_REF] Xie | Aggregated residual transformations for deep neural networks[END_REF] as in Mahajan et al. [START_REF] Mahajan | Exploring the limits of weakly supervised pretraining[END_REF]. We compare SwAV with supervised models trained from scratch on ImageNet. For all models, SwAV outperforms training from scratch by a significant margin showing that it can take advantage of the increased model capacity. For reference, we also include the results from Mahajan et al. [START_REF] Mahajan | Exploring the limits of weakly supervised pretraining[END_REF] obtained with a weakly-supervised model pretrained by predicting hashtags filtered to be similar to ImageNet classes. Interestingly, SwAV performance is strong when compared to this topline despite not using any form of supervision or filtering of the data.

Discussion

Self-supervised learning is rapidly progressing compared to supervised learning, even surpassing it on transfer learning, even though the current experimental settings are designed for supervised learning. In particular, architectures have been designed for supervised tasks, and it is not clear if the same models would emerge from exploring architectures with no supervision. Several recent works have shown that exploring architectures with search [START_REF] Liu | Are labels necessary for neural architecture search?[END_REF] or pruning [START_REF] Caron | Pruning convolutional neural networks with self-supervision[END_REF] is possible without supervision, and we plan to evaluate the ability of our method to guide model explorations.

A Implementation Details

In this section, we provide the details and hyperparameters for SwAV pretraining and transfer learning. Our code is publicly available at https://github.com/facebookresearch/swav.

A.1 Implementation details of SwAV training

First, we provide a pseudo-code for SwAV training loop using two crops in Pytorch style:

= sum(Q, dim=1) Q *= (r / u).unsqueeze(1) Q *= (c / sum(Q, dim=0)).unsqueeze(0) return (Q / sum(Q, dim=0, keepdim=True)).T
Most of our training hyperparameters are directly taken from SimCLR work [START_REF] Chen | A simple framework for contrastive learning of visual representations[END_REF]. We train SwAV with stochastic gradient descent using large batches of 4096 different instances. We distribute the batches over 64 V100 16Gb GPUs, resulting in each GPU treating 64 instances. The temperature parameter τ is set to 0.1 and the Sinkhorn regularization parameter ε is set to 0.05 for all runs. We use a weight decay of 10 -6 , LARS optimizer [START_REF] You | Large batch training of convolutional networks[END_REF] and a learning rate of 4.8 which is linearly ramped up during the first 10 epochs. After warmup, we use the cosine learning rate decay [START_REF] Loshchilov | Sgdr: Stochastic gradient descent with warm restarts[END_REF][START_REF] Misra | Self-supervised learning of pretext-invariant representations[END_REF] with a final value of 0.0048. To help the very beginning of the optimization, we freeze the prototypes during the first epoch of training. We synchronize batch-normalization layers across GPUs using the optimized implementation with kernels through CUDA/C-v2 extension from apex -2 . We also use apex library for training with mixed precision [START_REF] Micikevicius | Mixed precision training[END_REF]. Overall, thanks to these training optimizations (mixed precision, kernel batch-normalization and use of large batches [START_REF] Goyal | Accurate, large minibatch sgd: Training imagenet in 1 hour[END_REF]), 100 epochs of training for our best SwAV model take approximately 6 hours (see Table 4). Similarly to previous works [START_REF] Chen | A simple framework for contrastive learning of visual representations[END_REF][START_REF] Chen | Improved baselines with momentum contrastive learning[END_REF][START_REF] Li | Prototypical contrastive learning of unsupervised representations[END_REF], we use a projection head on top of the convnet features that consists in a 2-layer multi-layer perceptron (MLP) that projects the convnet output to a 128-D space.

Note that SwAV is more suitable for a multi-node distributed implementation compared to contrastive approaches SimCLR or MoCo. The latter methods require sharing the feature matrix across all GPUs at every batch which might become a bottleneck when distributing across many GPUs. On the contrary, SwAV requires sharing only matrix normalization statistics (sum of rows and columns) during the Sinkhorn algorithm.

A.2 Data augmentation used in SwAV

We obtain two different views from an image by performing crops of random sizes and aspect ratios. Specifically we use the RandomResizedCrop method from torchvision.transforms module of PyTorch with the following scaling parameters: s=(0.14, 1). Note that we sample crops in a narrower range of scale compared to the default RandomResizedCrop parameters. Then, we resize both full resolution views to 224 × 224 pixels, unless specified otherwise (we use 160 × 160 resolutions in some of our experiments). Besides, we obtain V additional views by cropping small parts in the image. To do so, we use the following RandomResizedCrop parameters: s=(0.05, 0.14). We resize the resulting crops to 96 × 96 resolution. Note that we always deal with resolutions that are divisible by 32 to avoid roundings in the ResNet-50 pooling layers. Finally, we apply random horizontal flips, color distortion and Gaussian blur to each resulting crop, exactly following the SimCLR implementation [START_REF] Chen | A simple framework for contrastive learning of visual representations[END_REF]. An illustration of our multi-crop augmentation strategy can be viewed in Fig. 5.

x n1 x n(V+2) x n Loss t 3 ~Tsmall 2 Global Views fθ zn2 fθ zn1 t 1 ~T … Additional Small Views zn(V+2) fθ zn3 t 2 ~T t V + 2 ~Tsmall x n2
x n3 fθ Figure 5: Multi-crop: the image x n is transformed into V + 2 views: two global views and V small resolution zoomed views.

A.3 Implementation details of linear classification on ImageNet with ResNet-50

We obtain 75.3 top-1 accuracy on ImageNet by training a linear classifier on top of frozen final representations (2048-D) of a ResNet-50 trained with SwAV. This linear layer is trained during 100 epochs, with a learning rate of 0.3 and a weight decay of 10 -6 . We use cosine learning rate decay and a batch size of 256. We use standard data augmentations, i.e., cropping of random sizes and aspect ratios (default parameters of RandomResizedCrop) and random horizontal flips.

-2 github.com/NVIDIA/apex

A.8 SimCLR loss with multi-crop augmentation

When implementing SimCLR with multi-crop augmentation, we have to deal with several positive pairs formed by an anchor features and the different crops coming from the same instance. We denote by B the total number of unique dataset instances in the batch and by M the number of crops per instance. For example, in the case of 2x160+4x96 crops, we have M = 6 crops per instance. We call N = B × M the effective total number of crops in the batch. Overall, we minimize the following loss

L = - 1 N 1 M -1 N i=1 v + ∈{v + i } log exp z T i v + /τ exp z T i v + /τ + v -∈{v - i } exp z T i v -/τ . (7)
For a feature representation z i , the corresponding set of positive examples {v + i } is formed by the representations of the other crops from the same instance. The set of negatives {v - i } is formed by the representations of all crops in the same batch except ones coming from the same instance as x i . Note that this extension of SimCLR loss with several pairs of positive is similar to the one used in Khosla et al. [START_REF] Khosla | Supervised contrastive learning[END_REF].

B Additional Results

B.1 Running times

In Table 4, we report compute and GPU memory requirements based on our implementation for different settings. As described in § A.1, we train each method on 64 V100 16GB GPUs, with a batch size of 4096, using mixed precision and apex optimized version of synchronized batch-normalization layers. We report results with ResNet-50 for all methods. In Fig. 6, we report SwAV performance for different training lengths measured in hours based on our implementation. We observe that after only 6 hours of training, SwAV outperforms SimCLR trained for 1000 epochs (40 hours based on our implementation) by a large margin. If we train SwAV for longer, we see that the performance gap between the two methods increases even more.

B.2 Larger architectures

In Table 5, we show results when training SwAV on large architectures. We observe that SwAV benefits from training on large architectures and plan to explore in this direction to furthermore boost self-supervised methods.

Implementation details for SwAV R50-w2. The model is trained for 400 epochs on 128 GPUS (batch size 4096). We train the model with 2x224+4x96 (total of 6 crops). All other hyperparameters are the same as the ones described in appendix A.1. Implementation details for SwAV R50-w5. The model is trained for 400 epochs on 128 GPUS (batch size 1536) with a queue of 1536 samples starting from the beginning of training. We train the model with 2x224+4x96 (total of 6 crops). All other hyperparameters are the same as the ones described in appendix A.1.

B.3 Transferring unsupervised features to downstream tasks

In Table 6, we expand results from the main paper by providing numbers from previously and concurrently published self-supervised methods. In the left panel of Table 6, we show performance after training a linear classifier on top of frozen representations on different datasets while on the right panel we evaluate the features by finetuning a ResNet-50 on object detection with Faster R-CNN [START_REF] Ren | Faster r-cnn: Towards real-time object detection with region proposal networks[END_REF] and DETR [START_REF] Carion | End-to-end object detection with transformers[END_REF]. Overall, we observe on Table 6 that SwAV is the first self-supervised method to outperform ImageNet supervised backbone on all the considered transfer tasks and datasets. Other self-supervised learners are capable of surpassing the supervised counterpart but only for one type of transfer (object detection with finetuning for MoCo/PIRL for example). We will release this model so other researchers might also benefit by replacing the ImageNet supervised network with our model.

B.4 More detection metrics for object detection

In Table 7 and Table 8, we evaluate the features by finetuning a ResNet-50 on object detection with Faster R-CNN [START_REF] Ren | Faster r-cnn: Towards real-time object detection with region proposal networks[END_REF] and DETR [START_REF] Carion | End-to-end object detection with transformers[END_REF] and report more detection metrics compared to Table 6. We observe in Table 7 and in Table 8 that SwAV outperforms the ImageNet supervised pretrained model on all the detection evaluation metrics. Note that MoCov2 backbone performs particularly well on the object detection benchmark, and even outperform SwAV features for some detection metrics. However, as shown in Table 6, this backbone is not competitive with the supervised features when evaluating on classification tasks without finetuning.

B.5 Low-Shot learning on ImageNet for SwAV pretrained on Instagram data

We now test whether SwAV pretrained on Instagram data can serve as a pretraining method for low-shot learning on ImageNet. We report in Table 8 results when finetuning Instagram SwAV features with only few labels per ImageNet category. We observe that using pretrained features from Instagram improves considerably the performance compared to training from scratch.

Table 6: Transfer learning on downstream tasks. Comparison between features from ResNet-50 trained on ImageNet with SwAV or supervised learning. We also report numbers from other selfsupervised methods ( † for numbers from other methods run by us). We consider two settings. (1) Linear classification on top of frozen features. We report top-1 accuracy on Places205 and iNat18 datasets and mAP on VOC07. (2) Object detection with finetuned features on VOC07+12 trainval using Faster R-CNN [START_REF] Ren | Faster r-cnn: Towards real-time object detection with region proposal networks[END_REF] and on COCO [START_REF] Lin | Microsoft coco: Common objects in context[END_REF] using DETR [START_REF] Carion | End-to-end object detection with transformers[END_REF]. In this Following previous work protocols [START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF][START_REF] Zhuang | Local aggregation for unsupervised learning of visual embeddings[END_REF], we evaluate the quality of our unsupervised features with K-nearest neighbor (KNN) classifiers on ImageNet. We get features from the computed network outputs for center crops of training and test images. We report results with 20 and 200 NN in Table 10.

We outperform the current state-of-the-art of this evaluation. Interestingly we also observe that using fewer NN actually boosts the performance of our model.

C Ablation Studies on Clustering

C.1 Number of prototypes

In Table 11, we evaluate the influence of the number of prototypes used in SwAV. We train ResNet-50 with SwAV for 400 epochs with 2 × 160 + 4 × 96 crops (ablation study setting) and evaluate the performance by training a linear classifier on top of frozen final representations. We observe in Table 11 that varying the number of prototypes by an order of magnitude (3k-100k) does not affect much the performance (at most 0.3 on ImageNet). This suggests that the number of prototypes has little influence as long as there are "enough". Throughout the paper, we train SwAV with 3000 prototypes. We find that using more prototypes increases the computational time both in the Sinkhorn algorithm and during back-propagation for an overall negligible gain in performance. We investigate the impact of learning the prototypes compared to using fixed random prototypes. Assigning features to fixed random targets has been explored in NAT [START_REF] Bojanowski | Unsupervised learning by predicting noise[END_REF]. However, unlike SwAV, NAT uses a target per instance in the dataset, the assignment is hard and performed with Hungarian algorithm. In Table 12 (left), we observe that learning prototypes improves SwAV from 73.1 to 73.9 which shows the effect of adapting the prototypes to the dataset distribution.

Overall, these results suggest that our framework learns from a different signal from "offline" approaches that attribute a pseudo-label to each instance while considering the full dataset and then predict these labels (like DeepCluster [START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF] for example). Indeed, the prototypes in SwAV are not strongly encouraged to be categorical and random fixed prototypes work almost as well. Rather, they help contrasting different image views without relying on pairwise comparison with many negatives samples. This might explain why the number of prototypes does not impact the performance significantly.

C.3 Hard versus soft assignments

In Table 12 (right), we evaluate the impact of using hard assignment instead of the default soft assignment in SwAV. We train the models during 400 epochs with representations. We also report the training losses in Fig. 7. We observe that using the hard assignments performs worse than using the soft assignments. An explanation is that the rounding needed to obtain discrete codes is a more aggressive optimization step than gradient updates. While it makes the model converge rapidly (see Fig. 7), it leads to a worse solution.

C.4 Impact of the number of iterations in Sinkhorn algorithm

In Table 13, we investigate the impact of the number of normalization steps performed during Sinkhorn-Knopp algorithm [START_REF] Cuturi | Sinkhorn distances: Lightspeed computation of optimal transport[END_REF] on the performance of SwAV. We observe that using only 3 iterations is enough for the model to converge. When performing less iterations, the loss fails to converge. We observe that using more iterations slightly alters the transfer performance of the model. We conjecture that it is for the same reason that rounding codes to discrete values deteriorate the quality of our model by converging too rapidly.

D Details on Clustering-Based methods: DeepCluster-v2 and SeLa-v2

In this section, we provide details on our improved implementation of clustering-based approaches DeepCluster-v2 and SeLa-v2 compared to their corresponding original publications [START_REF] Asano | Self-labelling via simultaneous clustering and representation learning[END_REF][START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF]. These two methods follow the same pipeline: they alternate between pseudo-labels generation ("assignment phase") and training the network with a classification loss supervised by these pseudo-labels ("training phase").

D.1 Training phase

During the training phase, both methods minimize the multinomial logistic loss of the pseudo-labels q classification problem:

(z, c, q) =k q (k) log p (k) , where

p (k) = exp 1 τ z c k k exp 1 τ z c k . ( 8
)
The pseudo-labels are kept fixed during training and updated for the entire dataset once per epoch during the assignment phase.

Training phase in DeepCluster-v2. In the original DeepCluster work, both the classification head c and the convnet weights are trained to classify the images into their corresponding pseudo-label between two assignments. Intuitively, this classification head is optimized to represent prototypes for the different pseudo-classes. However, since there is no mapping between two consecutive assignments: the classification head learned during an assignment becomes irrelevant for the following one. Thus, this classification head needs to be re-set at each new assignment which considerably disrupts the convnet training. For this reason, we propose to simply use for classification head c the centroids given by k-means clustering (Eq. 11). Overall, during training, DeepCluster-v2 optimizes

D.2 Assignment phase

The purpose of the assignment phase is to provide assignments q for each instance of the dataset. For both methods, this implies having access to feature representations z for the entire dataset. Both original works [START_REF] Asano | Self-labelling via simultaneous clustering and representation learning[END_REF][START_REF] Caron | Deep clustering for unsupervised learning of visual features[END_REF] perform regularly a pass forward on the whole dataset to get these features.

Using the original implementation, if assignments are updated at each epoch, then the assignment phase represents one third of the total training time. Therefore, in order to speed up training, we choose to use the features computed during the previous epoch instead of dedicating pass forwards to the assignments. This is similar to the memory bank introduced by Wu et al. [START_REF] Wu | Unsupervised feature learning via non-parametric instance discrimination[END_REF], without momentum.

Assignment phase in DeepCluster-v2. DeepCluster-v2 uses spherical k-means to get pseudolabels. In particular, pseudo-labels q are obtained by minimizing the following problem:

min C∈R d×K 1 N N n=1 min q -z n Cq, (11)
where z n and the columns of C are normalized. The original work DeepCluster uses tricks such as cluster re-assignments and balanced batch sampling to avoid trivial solutions but we found these unnecessary, and did not observe collapsing during our trainings. As noted by Asano et al., this is due to the fact that assignment and training are well separated phases.

Assignment phase in SeLa-v2. Unlike DeepCluster, SeLa uses the same loss during training and assignment phases. In particular, we use Sinkhorn-Knopp algorithm to optimize the following assignment problem (see details and derivations in the original SeLa paper [START_REF] Asano | Self-labelling via simultaneous clustering and representation learning[END_REF]):

min q (z, c, q). (12)
Implementation details We use the same hyperparameters as SwAV to train SeLa-v2 and DeepCluster-v2: these are described in § A. Asano et al. [START_REF] Asano | Self-labelling via simultaneous clustering and representation learning[END_REF] have shown that multi-clustering boosts performance of clustering-based approaches, and so we use 3 sets of 3000 prototypes c when training SeLa-v2 and DeepCluster-v2. Note that unlike online methods (like SwAV, SimCLR and MoCo), the clustering approaches SeLa-v2 and DeepCluster-v2 can be implemented with only a single crop per image per batch. The major limitation of SeLa-v2 and DeepCluster-v2 is that these methods are not online and therefore scaling them to very large scale dataset is not posible without major adjustments.

Figure 1 :

 1 Figure 1: Contrastive instance learning (left) vs. SwAV (right).In contrastive learning methods applied to instance classification, the features from different transformations of the same images are compared directly to each other. In SwAV, we first obtain "codes" by assigning features to prototype vectors. We then solve a "swapped" prediction problem wherein the codes obtained from one data augmented view are predicted using the other view. Thus, SwAV does not directly compare image features. Prototype vectors are learned along with the ConvNet parameters by backpropragation.

Figure 2 :

 2 Figure 2: Linear classification on ImageNet. Top-1 accuracy for linear models trained on frozen features from different self-supervised methods. (left) Performance with a standard ResNet-50. (right) Performance as we multiply the width of a ResNet-50 by a factor ×2, ×4, and ×5.

Figure 3 :

 3 Figure 3: Top-1 accuracy on ImageNet with a linear classifier trained on top of frozen features from a ResNet-50. (left) Comparison between clustering-based and contrastive instance methods and impact of multi-crop. Self-supervised methods are trained for 400 epochs and supervised models for 200 epochs. (right) Performance as a function of epochs. We compare SwAV models trained with different number of epochs and report their running time based on our implementation.

Figure 4 :

 4 Figure 4: Pretraining on uncurated data. Top-1 accuracy on ImageNet for pretrained models on an uncurated set of 1B random Instagram images. (left) We compare ResNet-50 pretrained with either SimCLR or SwAV on two downstream tasks: linear classification on frozen features or finetuned features. (right) Performance of finetuned models as we increase the capacity of a ResNext following [40]. The capacity is provided in billions of Mult-Add operations. *: pretrained on a curated set of 1B Instagram images filtered with 1.5k hashtags similar to ImageNet classes.

#

  C: prototypes (DxK) # model: convnet + projection head # temp: temperature for x in loader: # load a batch x with B samples x_t = t(x) # t is a random augmentation x_s = s(x) # s is a another random augmentation z = model(cat(x_t, x_s)) # embeddings: 2BxD scores = mm(z, C) # prototype scores: 2BxK scores_t = scores[:B] scores_s = scores[B:] # compute assignments with torch.no_grad(): q_t = sinkhorn(scores_t) q_s = sinkhorn(scores_s) # convert scores to probabilities p_t = Softmax(scores_t / temp) p_s = Softmax(scores_s / temp) # swap prediction problem loss = -0.5 * mean(q_t * log(p_s) + q_s * log(p_t)) # SGD update: network and prototypes loss.backward() update(model.params) update(C) # normalize prototypes with torch.no_grad(): C = normalize(C, dim=0, p=2) # Sinkhorn-Knopp def sinkhorn(scores, eps=0.05, niters=3): Q = exp(scores / eps).T Q /= sum(Q) K, B = Q.shape u, r, c = zeros(K), ones(K) / K, ones(B) / B for _ in range(niters): u

Figure 6 :

 6 Figure 6: Influence of longer training. Top-1 ImageNet accuracy for linear models trained on frozen features. We report SwAV performance for different training lengths measured in hours based on our implementation. We train each ResNet-50 models on 64 V100 16GB GPUs with a batch size of 4096 (see § A.1 for implementation details).

  Training phase in SeLa-v2. In SeLa work, the prototypes c are learned with stochastic gradient descend during the training phase. Overall, during training, SeLa-v2 optimizes the following problem: min z,c (z, c, q).

  . However, in the online setting where

	Method	Arch. Param. Top1		Supervised	SwAV
	Supervised Colorization [64] R50 R50 Jigsaw [45] R50 NPID [57] R50 BigBiGAN [15] R50 LA [67] R50 NPID++ [43] R50 MoCo [24] R50 SeLa [2] R50 PIRL [43] R50 CPC v2 [27] R50 PCL [36] R50 SimCLR [10] R50 MoCov2 [11] R50 SwAV R50	24 24 24 24 24 24 24 24 24 24 24 24 24 24 24	76.5 39.6 45.7 54.0 56.6 58.8 59.0 60.6 61.5 63.6 63.8 65.9 70.0 71.1 75.3	80 68 70 72 74 76 78 ImageNet top-1 accuracy	24M94M MoCov2 number of parameters 375M CPCv2 CMC AMDIM 586M SimCLR-x1 SimCLR-x2 75.3 SimCLR-x4 77.3 77.9 78.5

Table 1 :

 1 Semi-supervised learning on ImageNet with a ResNet-50. We finetune the model with 1% and 10% labels and report top-1 and top-5 accuracies. *: uses RandAugment[START_REF] Cubuk | Randaugment: Practical data augmentation with no separate search[END_REF].

			1% labels	10% labels
		Method	Top-1 Top-5	Top-1	Top-5
		Supervised	25.4	48.4	56.4	80.4
	Methods using	UDA [59]	-	-	68.8*	88.5*
	label-propagation	FixMatch [50]	-	-	71.5*	89.1*
		PIRL [43]	30.7	57.2	60.4	83.8
	Methods using	PCL [36]	-	75.6	-	86.2
	self-supervision only	SimCLR [10]	48.3	75.5	65.6	87.8
		SwAV	53.9	78.5	70.2	89.9

Table 2 :

 2 Transfer learning on downstream tasks. Comparison between features from ResNet-50 trained on ImageNet with SwAV or supervised learning. We consider two settings. (1) Linear classification on top of frozen features. We report top-1 accuracy on all datasets except VOC07 where we report mAP. (2) Object detection with finetuned features on VOC07+12 trainval using Faster R-CNN[START_REF] Ren | Faster r-cnn: Towards real-time object detection with region proposal networks[END_REF] and on COCO[START_REF] Lin | Microsoft coco: Common objects in context[END_REF] using DETR[START_REF] Carion | End-to-end object detection with transformers[END_REF]. We report the most standard detection metrics for these datasets: AP 50 on VOC07+12 and AP on COCO.

		Linear Classification	Object Detection
		Places205 VOC07 iNat18	VOC07+12 (Faster R-CNN) COCO (DETR)
	Supervised	53.2	87.5	46.7	81.3	40.8
	SwAV	56.7	88.9	48.6	82.6	42.1

Table 3 :

 3 Training in small batch setting. Top-1 accuracy on ImageNet with a linear classifier trained on top of frozen features from a ResNet-50. All methods are trained with a batch size of 256. We also report the number of stored features, the type of cropping used and the number of epochs.

	Method	Mom. Encoder Stored Features	multi-crop	epoch batch Top-1
	SimCLR	0	2×224	200	256	61.9
	MoCov2	65, 536	2×224	200	256	67.5
	MoCov2	65, 536	2×224	800	256	71.1
	SwAV	3, 840	2×160 + 4×96	200	256	72.0
	SwAV	3, 840	2×224 + 6×96	200	256	72.7
	SwAV	3, 840	2×224 + 6×96	400	256	74.3

Table 4 :

 4 Computational cost. We report time and GPU memory requirements based on our implementation for different models trained during 100 epochs.

	Method	multi-crop	time / 100 epochs peak memory / GPU
	SimCLR	2 × 224	4h00	8.6G
	SwAV	2 × 224	4h09	8.6G
	SwAV	2 × 160 + 4 × 96	4h50	8.5G
	SwAV	2 × 224 + 6 × 96	6h15	12.8G
	running time (hours) 0 15 30 45 64 68 72 76 top-1 accuracy	SimCLR SwAV

Table 5 :

 5 Large architectures. Top-1 accuracy for linear models trained on frozen features from different self-supervised methods on large architectures. The model is trained for 400 epochs on 64 GPUS (batch size 2560) with a queue of 2560 samples starting from the beginning of training. We train the model with 2x224+4x96 (total of 6 crops). All other hyperparameters are the same as the ones described in appendix A.1.

	Method	Arch.	Param. Top1
	Supervised	EffNet-B7	66	84.4
	Rotation [20]	RevNet50-4w	86	55.4
	BigBiGAN [15] RevNet50-4w	86	61.3
	AMDIM [3]	Custom-RN	626	68.1
	CMC [51]	R50-w2	188	68.4
	MoCo [24]	R50-w4	375	68.6
	CPC v2 [27]	R161	305	71.5
	SimCLR [10]	R50-w4	375	76.8
	SwAV	R50-w2	188	77.3
	SwAV	R50-w4	375	77.9
	SwAV	R50-w5	586	78.5
	Implementation details for SwAV R50-w4.

Table 7 :

 7 table, we report the most standard detection metrics for these datasets: AP 50 on VOC07+12 and AP on COCO. More detection metrics for object detection on VOC07+12 with finetuned features using Faster R-CNN[START_REF] Ren | Faster r-cnn: Towards real-time object detection with region proposal networks[END_REF].

		Linear Classification		Object Detection
		Places205 VOC07 iNat18	VOC07+12 (Faster R-CNN) COCO (DETR)
	Supervised	53.2	87.5	46.7		81.3	40.8
	RotNet [19]	45.0	64.6	-		-	-
	NPID++ [43]	46.4	76.6	32.4		79.1	-
	MoCo [24]	46.9 †	79.8 † 31.5 †		81.5	-
	PIRL [43]	49.8	81.1	34.1		80.7	-
	PCL [36]	49.8	84.0	-		-	-
	BoWNet [19]	51.1	79.3	-		81.3	-
	SimCLR [10]	53.3 †	86.4 † 36.2 †		-	-
	MoCov2 [24]	52.9 †	87.1 † 38.9 †		82.5	42.0 †
	SwAV	56.7	88.9	48.6		82.6	42.1
			Method	AP all AP 50 AP 75
			Supervised	53.5	81.3	58.8
			Random	28.1	52.5	26.2
			NPID++ [43] 52.3	79.1	56.9
			PIRL [43]	54.0	80.7	59.7
			BoWNet [19] 55.8	81.3	61.1
			MoCov1 [24] 55.9	81.5	62.6
			MoCov2 [11] 57.4	82.5	64.0
			SwAV	56.1	82.6	62.7
	B.6 Image classification with KNN classifiers on ImageNet

Table 8 :

 8 More detection metrics for object detection on COCO with finetuned features using DETR[START_REF] Carion | End-to-end object detection with transformers[END_REF].MethodAP AP 50 AP 75 AP S AP M AP L

	ImageNet labels	40.8 61.2	42.9 20.1 44.5 60.3
	MoCo-v2	42.0 62.7	44.4 20.8 45.6 60.9
	SwAV	42.1 63.1	44.5 19.7 46.3 60.9

Table 9 :

 9 Low-shot learning on ImageNet. Top-1 and top-5 accuracies when training with 13 or 128 examples per category.

	# examples per class	13	128
		top1 top5 top1 top5
	No pretraining	25.4 48.4 56.4 80.4
	SwAV IG-1B	38.2 67.1 64.7 87.2
	C.2 Learning the prototypes

Table 10 :

 10 2 × 160 + 4 × 96 crops (ablation study setting) and evaluate the performance by training a linear classifier on top of frozen final KNN classifiers on ImageNet. We report top-1 accuracy with 20 and 200 nearest neighbors.

		8		Soft		Hard
		7
	SwAV loss	5 6 4				Figure 7: Hard versus soft assignments. We report the training loss for SwAV models trained with either soft or hard assignments. The models are trained during 400 epochs with 2 × 160 + 4 × 96 crops.
		3
		0	100	200 epochs	300	400
						20

Table 11 :

 11 Impact of number of prototypes. Top-1 ImageNet accuracy for linear models trained on frozen features.

	Number of prototypes 300 1000 3000 10000 30000 100000
	Top-1	72.8 73.6 73.9	74.1	73.8	73.8

Table 12 :

 12 Ablation studies on clustering. Top-1 ImageNet accuracy for linear models trained on frozen features. (left) Impact of learning the prototypes. (right) Hard versus soft assignments.

	Prototypes Learned Fixed	Assignment Soft Hard
	Top-1	73.9	73.1	Top-1	73.9 73.3
	the following problem with mini-batch SGD:

Table 13 :

 13 Impact of the number of iterations in Sinkhorn algorithm. Top-1 ImageNet accuracy for linear models trained on frozen features.

	Sinkhorn iterations	1	3	10	30
	Top-1	fail 73.9 73.8 73.7

Acknowledgement. We thank Nicolas Carion, Kaiming He, Herve Jegou, Benjamin Lefaudeux, Thomas Lucas, Francisco Massa, Sergey Zagoruyko, and the rest of Thoth and FAIR teams for their

A. [START_REF] Bautista | Cliquecnn: Deep unsupervised exemplar learning[END_REF] Implementation details of semi-supervised learning (finetuning with 1% or 10% labels)

We finetune with either 1% or 10% of ImageNet labeled images a ResNet-50 pretrained with SwAV. We use the 1% and 10% splits specified in the official code release of SimCLR. We mostly follow hyperparameters from PCL [START_REF] Li | Prototypical contrastive learning of unsupervised representations[END_REF]: we train during 20 epochs with a batch size of 256, we use distinct learning rates for the convnet weights and the final linear layer, and we decay the learning rates by a factor 0.2 at epochs 12 and 16. We do not apply any weight decay during finetuning. For 1% finetuning, we use a learning rate of 0.02 for the trunk and 5 for the final layer. For 10% finetuning, we use a learning rate of 0.01 for the trunk and 0.2 for the final layer.

A.5 Implementation details of transfer learning on downstream tasks Linear classifiers. We mostly follow PIRL [START_REF] Misra | Self-supervised learning of pretext-invariant representations[END_REF] for training linear models on top of representations given by a ResNet-50 pretrained with SwAV. On VOC07, all images are resized to 256 pixels along the shorter side, before taking a 224 × 224 center crop. Then, we train a linear SVM with LIBLINEAR [START_REF] Fan | Liblinear: A library for large linear classification[END_REF] on top of corresponding global average pooled final representations (2048-D). For linear evaluation on other datasets (Places205 and iNat18), we train linear models with stochastic gradient descent using a batch size of 256, a learning rate of 0.01 reduced by a factor of 10 three times (equally spaced intervals), weight decay of 0.0001 and momentum of 0.9. On Places205, we train the linear models for 28 epochs and on iNat18 for 84 epochs. We report the top-1 accuracy computed using the 224 × 224 center crop on the validation set.

Object Detection on VOC07+12. We use a Faster R-CNN [START_REF] Ren | Faster r-cnn: Towards real-time object detection with region proposal networks[END_REF] model as implemented in Detec-tron2 [START_REF] Wu | Detectron2[END_REF] and follow the finetuning protocol from He et al. [START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF] making the following changes to the hyperparameters -our initial learning rate is 0.1 which is warmed with a slope (WARMUP_FACTOR flag in Detectron2) of 0.333 for 1000 iterations. Other training hyperparamters are kept exactly the same as in He et al. [START_REF] He | Momentum contrast for unsupervised visual representation learning[END_REF], i.e., batchsize of 16 across 8 GPUs, training for 24K iterations on VOC07+12 trainval with the learning rate reduced by a factor of 10 after 18K and 22K iterations, using SyncBatchNorm to finetune BatchNorm parameters, and adding an extra BatchNorm layer after the res5 layer (Res5ROIHeadsExtraNorm head in Detectron2). We report results on VOC07 test set averaged over 5 independant runs.

Object Detection on COCO. We test the generalization of our ResNet-50 features trained on ImageNet with SwAV by transferring them to object detection on COCO dataset [START_REF] Lin | Microsoft coco: Common objects in context[END_REF] with DETR framework [START_REF] Carion | End-to-end object detection with transformers[END_REF]. DETR is a recent object detection framework that relies on a transformer encoderdecoder architecture. It reaches competitive performance with Faster R-CNN while being conceptually simpler and trainable end-to-end. Interestingly, unlike other frameworks [START_REF] He | Rethinking imagenet pre-training[END_REF], current results with DETR have shown that using a pretrained backbone is crucial to obtain good results compared to training from scratch. Therefore, we investigate if we can boost DETR performance by using features pretrained on ImageNet with SwAV instead of standard supervised features. We also evaluate features from MoCov2 [START_REF] Chen | Improved baselines with momentum contrastive learning[END_REF] pretraining. We train DETR during 300 epochs with AdamW, we use a learning rate of 10 -4 for the transformer and apply a weight decay of 10 -4 . We select for each method the best learning rate for the backbone among the following three values: 10 -5 , 5 × 10 -5 and 10 -4 . We decay the learning rates by a factor 0.1 after 200 epochs.

A.6 Implementation details of training with small batches of 256 images

We start using a queue composed of the feature representations from previous batches after 15 epochs of training. Indeed, we find that using the queue before 15 epochs disturbs the convergence of the model since the network is changing a lot from an iteration to another during the first epochs. We simulate large batches of size 4096 by storing the last 15 batches, that is 3, 840 vectors of dimension 128. We use a weight decay of 10 -6 , LARS optimizer [START_REF] You | Large batch training of convolutional networks[END_REF] and a learning rate of 0.6. We use the cosine learning rate decay [START_REF] Loshchilov | Sgdr: Stochastic gradient descent with warm restarts[END_REF] with a final value of 0.0006.

A.7 Implementation details of ablation studies

In our ablation studies (results in Table 5 of the main paper for example), we choose to follow closely the data augmentation used in concurrent work SimCLR. This allows a fair comparison and importantly, isolates the effect of our contributions. In practice, it means that we use the default parameters of the random crop method (RandomResizedCrop), s=(0.08, 1) instead of s=(0.14, 1), when sampling the two large resolution views.