For self-supervised learning, Rationality implies generalization, provably
Authors: Yamini Bansal
Gal Kaplun
Boaz Barak
Venue: ICLR 2021 Poster (2021)
Keywords: Deep Learning Theory
Generalization Bounds
Self-supervised learning
Representation learning

Abstract: We prove a new upper bound on the generalization gap of classifiers that are obtained by first using self-supervision to learn a representation $r$ of the training~data, and then fitting a simple (e.g., linear) classifier $g$ to the labels. Specifically, we show that (under the assumptions described below) the generalization gap of such classifiers tends to zero if $\mathsf{C}(g) \ll n$, where $\mathsf{C}(g)$ is an appropriately-defined measure of the simple classifier $g$'s complexity, and $n$ is the number of training samples. We stress that our bound is independent of the complexity of the representation $r$. 
We do not make any structural or conditional-independence  assumptions on the representation-learning task, which can use the same training dataset that is later used for classification. Rather, we assume that the training procedure satisfies certain natural noise-robustness (adding small amount of label noise causes small degradation in performance) and rationality  (getting the wrong label is not better than getting no label at all) conditions that widely hold across many standard architectures.
We also conduct an extensive empirical study of the generalization gap and the quantities used in our assumptions for a variety of self-supervision based algorithms, including SimCLR, AMDIM and BigBiGAN,  on the CIFAR-10 and ImageNet datasets. We show that, unlike standard supervised classifiers, these algorithms display small generalization gap, and the bounds we prove on this gap are often non vacuous. 

Published as a conference paper at ICLR 2021
FOR SELF-SUPERVISED LEARNING, RATIONALITY IMPLIES GENERALIZATION, PROVABLY
Yamini Bansal
Gal Kaplun'
Boaz Barak'
Harvard University
Harvard University
Harvard University
ABSTRACT
We prove a new upper bound on the generalization gap of classifiers that are ob- tained by first using self-supervision to learn a representation of the training data, and then fitting a simple (e.g.. linear) classifier to the labels. Specifically, we show that (under the assumptions described below) the generalization gap of such classifiers tends to zero if C(g) < n, where C(g) is an appropriately-dffie measure of the simple classifier g's complexity, and n is the number of training samples. We stress that our bound is independent of the complexity of the repre- sentation r.
We do not make any structural or conditional-indeeendenee assumptions on the representation--earinng task, which use the same training datasel that is later used for classification. Rather, we assume that the training procedure satisfies certain natural noise-robustmess (adding small amount of label noise causes small degradation in performance) and rationality (getting the wrong label is not better than getting no label at all) conditions that widely hold across many standard architectures.
We also conduct extensive empirical study of the generalization gap and the quantities used in our assumptions for variety of self-supervision based algo- rithms, including SimCLR, AMDIM and BigBiGAN, on the CIFAR- 10 and Ima- geNet datasets. We show that, unlike standard supervised classifiers, these algo- rithms display small generalization gap, and the bounds we prove on this gap are often non vacuous.
INTRODUCTION
The current standard approach for classification is "end-to-end supervised learning" where one fits complex (c.g.. deep neural network) classifier to the given training set (Tan & Le 2019 He et al.) 2016). However, modern classifiers are heavily over parameterized, and as demonstrated by Zhang et al. (017)) can fit 100% of their training set even when given random labels as inputs (in which case test performance is no better than chance). Hence, the training performance of such methods is by itself no indication of their performance on new unseen test points.
In this work, we study a different class of supervised learning procedures that have recently at- tracted significant interest. These classifiers are obtained by: (i) performing pre-training with a self- supervised task (i.e., without labels) to obtain a complex representation of the data points, and then (ii) fitting simple (c.g., lincar) classifier the representation and the labels. Such "Self- Super-Suue -Simple" " (SSS for short) algorithms are commonly used in natural language processing tasks (De- vlin al. 2018 Brown et al. 2020). and have recently found uses in other domains well (Ra- vanelli et al. 2020 Liu et al. 2019). Compared to standard "end-to-end supervised learning", SSS algorithms have several practical advantages. In particular, SSS algorithms can incorporate addi- tional unlabeled data, the representation obtained can be useful for multiple downstream tasks, and they can have improved -itt---distribution performance (Hendrycks al. 2019). Moreover, recent works show that even without additional unlabeled data, SSS algorithms can get close to statc-of-art accuracy in several classification tasks (Chen et al. 2020b He et al. 2020 Misra & Maaten 2020
"Equal contribution. Email: (ybansal, galkaplun) 0g harvard.edu
I Email: beboazbares .ok.

---

Published as a conference paper at ICLR 2021
Tian et al. 2019). For instance, SimCLRv2 (Chen et al. 2020b) achieves 79.8% top-1 performance on ImageNet et with a variant of ResNet- 152, on par with the end-to-end supervised accuracy of this architecture at 80.5%.
We show that SSS algorithms have another advantage over standard supervised learning-thh often have small generalization gap between their train and test accuracy, and we prove non-vacuous bounds on this gap. We stress that SSS algorithms use vver-parameterized models to extract the representation, and reuse the same training data learn a simple classifier on this representation. Thus, the final classifier they produce has high complexity by most standard measures, and it is by no means apriori evident that their generalization gap will be small.
Our bound is obtained by first noting that the generalization gap of every training algorithm is bounded by the sum of three quantities, which we name the Robustness gap, Rationality gap, and Memorization gap (we call this the RRM bound, see F. We now describe these gaps at a high level, deferring the formal definitions Section 2 All three gaps involve comparison with setting where we inject label noise by replacing a small fraction 1/ of the labels with random values.
The robustness gap corresponds to the amount by which training performance degrades by noise injection. That is, it equals the difference between the standard expected training accuracy (with no label noise) and the expected training accuracy in the noisy setting; in both cases, we measure accuracy with respect to the original (uncorrupted) labels. The robustness gap is nearly always small, and sometimes provably so (see Section 33
The rationality gap corresponds to the difference between performance on the noisy training samples (on which the training algorithm gets the wrong label) and test samples (on which it doesn't 't get any label at all), again with respect to uncorrupted labels. An optimal Bayesian procedure would have zero rationality gap, and indeed this gap is typically zero or small in practice. Since it is a non- standard quantity, We discuss the rationality gap in Section 3.11 and explain assuming it is small is both well-founded and does not trivialize the question of generalization.
The memorization gap, which often accounts for the lion's share of the generalization gap, corre- sponds to the difference in the noisy experiment between the training accuracy on the entire train set and the training accuracy on the samples that received the wrong label (both measured with respect to uncorrupted labels). The memorization gap can be thought of as quantifying the extent to which the classifier can "memorize" noisy labels, or act differently on the noisy points compared to the overall train set. The memorization gap is large in standard "end-to-end supervised training". In contrast, our main theoretical result is that for SSS algorithms, the memorization gap is small if the simple classifier has small complexity, independently of the complexity of the representation. As long as the simple classifier is under-pann pareeeetrrmeteeeeeed (i.e., its complexity is asymptotically smaller than the sample size), our bound on the memorization gap tends to zero. When combined with small rationality and robustness, we get concrete non-vace non-vacuous generalization bounds for various SSS algorithms on the CIFAR-10 and ImageNet datasets (see Figures [nd 4).
In a nutshell, our results are the following:
Theoretical contributions.
1. Our main theoretical result (Theorem Ii is that the memorization gap of an SSS algorithm is bounded by O(vC/n) where C is the complexity of the simple classifier produced in the "simple fit" stage. This bound is oblivious to the complexity of the representation produced in the pre-training and does not make any assumptions on the relationship between the representation learning method and the supervised learning task.
One way to interpret this result that we give a rigorous bound on the generalization gap of SSS algorithms, under the assumptions that the robustness and rationality gaps are bounded by some small constant (e.g.. 5%). As mentioned below, these assumptions hold widely in practice across many different classifiers. Moreover, these assumptions are non- trivial and do not "assume away the difficulty". Indeed, there are many natural examples of training algorithms for which these assumptions hold but the generalization gap is large. Last, making some assumptions is necessary for a generalization bound to hold for SSS algorithms; see Remark 3.1 and Appendix E
2

---

Published as a conference paper at ICLR 2021
40%
Theorem Bound
70.5%
vacuous
RRM Bound
35
Generalization Gap
Robustness Gap
30
Rationality Gap
Memorization Gap
Bound
Empirical RRM Bound
10
Theorem II bound
5
5 Generalization Gap
10
15%
Figure 1- Empirical RRM bound. The components of the RRM bound, as well as the upper bound of Theorem for variety models on the CIFAR-IO dataset with noise n 0.05.
Each vertical line corresponds to single model (architecture + self-supervised task fitting algorithm) and plots the RRM bound for this model. The green component corresponds to robustness, yellow rationality, and red memorization. The axis is the generalization gap, and the RRM bound always above the dashed = line. negative generalization gap can occur in algorithms that use augmentation.
blue dots correspond to the bound on the generalization gap obtained by re- placing the memorization gap with the bound of Theorem || See Sections Andd for more information.
2. We also give a theoretical justification for the assumption of a small rationality gap. by proving that positive rationality gap corresponds to "leaving performance the table", in the sense that we can transform a learning procedure with a large rationality gap into procedure with better test performance (Theorem 3.2)
Empirical contributions. We complement the theoretical results above with an extensive empiri- cal study of several SSS and end-to-end algorithms on both the CIFAR-I0 and ImageNet datasets.
We study several top-perforiing SSS architectures, and show that they exhibit relatively small generalization gaps on both CIFAR-10 10 and ImageNet. We stress that we consider the case where the same data is used for both representation Icarning and classification, and hence it is by no means a-priori obvious that these algorithms should have small general- ization gaps. See Figures and for sample results and Section 4 for more details.
2. We also show that the results of Zhang et al. (2017) do not replicate to SSS algorithms, in the sense that such algorithms, despite using over-parameterized representation, not able fit random label noise.
3. We understake an empirical study of the robustness, rationality, and memorization gaps for both SSS and end-to-ent supervised learning algorithms. We show that the robustness and rationality gaps are small for all these algorithms, while the memorization gap small for SSS algorithms but can be large for end-to-end supervised learning. We show that the RRM bound is typically non-vacuous, and fact, often close to tight, for variety of SSS algorithms the CIFAR-10 and ImageNet datasets, including SimCLR (which achieves test errors close to its supervised counterparts).
4. We demonstrate that replacing the memorization gap with the upper bound of Theorem yields non-vacuous generalization bound for variety of SSS algorithms on CIFAR-ID 10 and ImageNet. Moreover, this bound gets tighter with more data augmentation.
Related Work. There many works generalization bounds for supervised learning (e.g.,
Golowich et al. (2018); Neyshabur et al. (2017): [Bartlett et al.] (2017); Dziugaite & Roy (2017); Neyshabur al. (0018) Cao & Gul (2019), and references therein). The related work section of
3

---

Published as a conference paper at ICLR 2021
Arora et al. (2019) contains an extensive discussion of such bounds, and why more often than not the assumptions used do not hold in practice. Indeed, many such bounds give vacuous guarantees for modern architectures (such the ones considered in this paper) that have the capacity to memorize their entire training set (Zhang et al. 2017). Some non-vacuous bounds are known; e.g.. Zhou et al. (2019) gave 96.5% bound on the error of MobileNet on ImageNet. BBekinn et al. (2019); Nagarajan & Kolter (2019) showed some barriers for generalization gaps for standard end-to-en supervised
learning. Similarly, standard approaches such as Rademacher complexity cannot directly bound SSS
algorithms' generalization gap(see Remark 3.1.
Recently, /Sannshi al. (2019) and Lee et (2200) gave generalization bounds for self-supervised based classifiers. The two works considered special cases of SSS algorithms, such as contrastive learning and pre-text tasks. Both works make strong statistical assumptions of (exact or approxi- mate) conditional independence relating the pre-training and classification tasks. For example, if the pre-training task is obtained by splitting a given image x into two pieces (22) and predict- ing 22 from Ti, then Lee et al. (2020)'s 's results require xj and 22 to be approximately independent conditioned on their class y. However, in many realistic cases, the two parts of the same image will share a significant amount of information not explained by the label. Our work applies to general SSS algorithms without such statistical assumptions, at the expense of assuming bounds on the ro- bustness and rationality gaps. There have been works providing rigorous bounds the robustness gap or related quantities (See Section 3) However, as far as we know, the rationality gap has not been explicitly defined or studied before.
We provide a brief exposition of the various types of SSS methods in Section 4 and a more detailed discussion in Appendix [..
Paper Organization. Section contains formal definitions and statements of our results. Section 3 provides an overview of prior work and our new results on the three gaps of the RRM bound. In
Section 4 we describe our experimental setup and detail our empirical results. Section concludes the paper and discusses important open questions. We defer proofs and additional experimental results to the appendix. Appendix B contains the proof of Theorem M while Appendix contains the proof of Theorem 3.2 Appendix D fully details our experimental setup
Notation. We use capital letters (e.g., X) for random variables, lower case letters (e.g., z) for a single value, and bold font (e.g., æ)) for tuples (which will typically have dimension corresponding to the number of samples, denoted by nt). We use x; for the i-th element of the tuple æ. We use calligraphic letters (c.g., D) for both sets and distributions.
2 FORMAL STATEMENT OF RESULTS
A training procedure a (possibly randomized) algorithm T that takes as input train set (a: y) (I; (s) E (X' x x)))" and outputs a classifier : X' + Y. For our current discussion, we make no assumptions on the type of classifier output or the way that it is computed. We denote the distribution over training sets in (X' x 31"" by Drrin and the distribution over test samples in X' x 3 by Die The generalization gap of a training algorithm T with respect to a distribution pair D = (Dumin: Pan) the expected difference between its train accuracy (which we denote by Trainp, and its test performance (which we denote by Testp,r). We will often drop subscripts such as D, T' when they can be inferred from the context. We will also consider the n-noisy experiment, which involves computing the classifier f T(x: ÿ) where i y with probability 1 - 17 and is uniform over y otherwise.
Our starting point is the following observation which we call the RRM bound (for Robustness, Rationality, and Memorization). The quantities appearing in it are defined in Table T and discussed more in depth in Section
Fact (RRM bound). For every noise parameter n > O, training procedure T and distribution D = (Duato: D over training sets and test samples, the RRM bound with respect to T and D is,
'We provide our code and data in anonymous repository on: http://githab.com//IL..ea wttp://////.....11eeeeeeee---e/e
'The train and test data often stem from the same distribution (i.e.. Durin = Dies), but not always (e.g., it does not hold if we use data augmentation). Diss enters the RRM hound only via the rationality gap, so the assumption of small rationality may be affected if Drain # Di but the RRM bound still holds.
4

---

Published as a conference paper at ICLR 2021
Train Test <
Train Train(n)
+
NTrain(n) Test
+
Train(n) NTrain(n)
Generalization gap
Robustness gap
Rationality gup
Memorization gap
where we denote I+ max(x, 0).
Table 1 - The measurements of accuracy in the RRM bound, all with respect to a training algorithm T,
distributions (Dum,, Dea)) and parameter 17 >> O. The robustness gap is max((Tainn (r), 0), the tionality gap is max(NNrain(()) Test, 0), and the memorization gap is (axx(Trin(1)) NTrain(n)) 0).
Quantity
Training
Measurement
Testp,r
f = T(x, y) for (z. y) ~ Duain
Pr(f(z) = yl for (a, y) ~ Diss
Trainp,7
f T y) for (x. y) Durin
Pr(f(z;) y.] for train sample (24,, U1).
f = T'x, 3) for (x, y) ~ D Denin D1 Ys w.p. 17, uniform o/w
Pr[f(z;) = yi for train sample (24, 9.)
Trainp,r(1))
where y/ original label for 24.
f = T'x, 7) for (ax y) D mnin
Pr(f(z;) = yolū: + yil for a corrupted train sample 2; where y/ original label for I₁.
NTrainp.r(1)
D/ 1/s w.p. 1). uniform o/w
The RRM bound is but an observation, as directly follows from the fact that x+ 2 x for every However, it is very useful one. As mentioned above, for natural algorithms, expect both the robustness and rationality components of this gap to be small, and hence the most significant component is the memorization gap. Our main theoretical result is bound this gap:
Theorem II (Memorization gap bound). Let T (Tp.:: TΦ) be an SSS training procedure obtained by first training Type on æ x" to get a representation r X' + and then training Tg on (r(x), (), y) for y E 3m obtain classifier g R Y, with the final classifier f X as fxx)= = g(((x))- Then, for every noise parameter > and distribution D over X" x y):
defined
Memorization gap(TT) Tra)n NTrainT, S <O(V 30(VCo(
where (T&) is a complexity measure of the second phase training procedure, which in particular is upper bounded by the number of bits required describe the classifier g (See Definition 2.3
2.1 COMPLEXITY MEASURES
We now define three complexity measures, all of which can be plugged in the measure in Theo- rem II The first one, _ is the minimum description length of a classifier in bits. At a first reading, the reader can feel free skip the description of the other two measures CP and C These superficially similar to Rademacher Complexity (cf. Bartlett & Mendelson (2002)) in the sense that they capture the ability of the hypothesis to correlate with random noise but erucially depend on the algorithm used rather than the class of concepts (see Remark 3.1
Definition 2.3 (Complexity of training procedures). Let T be a training procedure taking as input a set (r, 3) = {Tr, H (R x V)" and outputting classifier g y and let n 0. For every training set (r, y). we define the following three complexity measures with respect to r, U.W)
The minimum description length of T' is defined as Cyidl (T) H where consider the model as random variable arising in the nj-noisy experiment
The prediction complexity of T is defined as C. CF.,,, (T) = J 's are the labels obtained the n-noisy experiment.
where the
The (unconditional) deviation complexity of T' is defined as Ct.y. (T') = [g((r))
Yi Øi yi) where the random variables above are taken over ~ [n] and subtraction is done modulo [)], identifying y with the set (0..... | 1}.
The name "minimum description length" is justified by the operational definition of entropy relating it to the minimum amortized length of prefix-free encoding of random variable.
5

---

Published as a conference paper at ICLR 2021
Conditioned on y and the choice of the index i, the deviations g(rz) y and 0 ys determine the predictions g(r)) and noisy labels Øt. and vice versa. Hence we can think of Cde as an "averaged" variant of C where we make the choice of the index i part of the sample space for the random variables. While we expect the two measures to be approximately close, the fact that C* takes i into the sample space makes it easier to estimate this quantity in practice without using large number of executions (See Figure D.2 convergence rates.). The measure C is harder to evaluate in practice, it requires finding the optimal compression scheme for the classifier. Appendix B contains the full proof of Theorem MI It is obtained by showing that: (i) for every r. r. and T it holds that Cr,y,((() (T) I Cr.y. (T) I Cr.g,,, (T)), and (ii) for every SSS algorithm T (T pre Tm.
and distribution D (D iniin Due), the memorization gap of T is at most
(mm(()))))) (Ta)
(vV22)
It is the quantity !
that we compute in our experiments.
3 THE THREE GAPS
We now briefly describe what known and what we prove about the three components of the RRM bound. We provide some additional discussions in Appendix B including "counter-example" of algorithms that exhibit large values for each one of these gaps.
555
supervised
555
supervised
555
supervoee
Rebustrees Gep-5%
Highest
Highest
Highest Mernor bation Gap-
Gop-0.577 0.51%
-80
-60
-40
-20
20 60
Robustness (%)
Rationality
Memorization (%)
Figure Robustness, Rationality, and Memorization for CIFAR-10 Each blue point is different combination (architecture + self-supervised task + fitting algorithm). Each red point is different architecture trained end-to-end with supervision. We use the "+' marker to denote the two best models of cach type (SSS and supervised). No augmentations were added. Noise is 5%. Details in Appendix D.3
The robustness gap. The robustness gap measures the decrease in training accuracy from adding noisy labels, measured with respect to the clean labels. The robustness gap and related notions such as noise stability tolerance have been studied in various works (cf. Frénay & Verleysen (2013); Manwani & Sastry| (2013)). Interpolating classifiers (with zero train error) satisfy Train(n)
77 and hence their robustness gap is most 17 (See left panel of Figure 2}. In SSS algorithms, since the representation is learned without using labels, the injection of label noise only affects the simple classifier, which is often linear. Robustness guarantees for linear classifiers have been given previously by [Rudin| (2005). While proving robustness bounds is not the focus of this paper, note in the appendix some simple bounds for least-squares minimization of linear classifiers and the (potentially inefficient) Empirical Risk Minimization algorithm (see Appendices and G). Empirically, we observe that the robustness gap of SSS algorithms is often significantly smaller than (See left panels of Figure and Figure 3
The memorization gap. The memorization gap corresponds to the algorithm's 's ability fit the noise (i.c., the gap increases with the number of fit noisy labels). If, for example, the classifier output interpolating, i.e., satisfies (x;) = Gh for every i, then accuracy over the noisy samples will be O (since for them y: o (... In contrast, the overall accuracy will be in expectation at least 1-1j which means that the memorization gap will be Rs 1 for small 7j. However, we show empirically (see right panels of Figures and 3) that the memorization gap is small for many SSS algorithms and prove a bound on it in Theorem When combined with small rationality and robustness, this bound results in non- non-vacuous generalization bounds for various real settings (e.g., 48% for ResNet101 with SimCLRv2 on ImageNet, and as low as 4% for MoCo V2 with ResNet- 18 on CIFAR- 10). Moreover, unlike other generalization bounds, our bound decreases with data augmentation (See Figure 5

---

Published as a conference paper at ICLR 2021
Remark 3.1 (Memorization vs. Rademacher complexity). The memorization gap, well the com- plexity measures defined in Section 2.1 have a superficial similarity to Rademacher complexity (Bartlett & Mendelson 2002), in the sense that they quantify the ability of the output classifier to fit noise. One difference is that Rademacher complexity is defined with respect to 100% noise, while consider the 17-noisy experiment for small rj. A more fundamental difference is that Rademacher complexity is defined via supremum over all classifiers in some class. The final classifiers of SSS algorithms are obtained by a composition of the complex representation and simple classifier. This composed classifier will in general have high Radamacher complexity, and in particular we would not be able to prove non-vacuous bounds on it using Radamacher complexity. We cannot ignore the complexity of the representation in medamacher-cooplexiin based analysis of SSS algorithms since the representation
learned using the same data that is later used for classification. In fact, there are examples of SSS algorithms with simple classifiers that have large generalization gaps (see Sec- tion B.T). This shows that Radamacher complexity bounds for the class of simple classifiers cannot, on their own, be used to derive generalization bounds.
Zhang et al. 2 demonstrated a lower bound on the Radamacher complexity of modern deep networks, by showing that modern end-to-end supervised learning algorithm can fit 100% of their label noise. Our experiments show that this is not the case for SSS algorithms, which can only fit 15%-25% of the CIFAR-IO training set when the labels are completely random (See Table[D.Jjp in the appendix.). However, absence of evidence is not evidence of absence, and the fact that empirically SSS algorithms do not fit the noise, does not imply that the Radamacher complexity of the resulting class is small, nor does it, by its own, automatically imply small generalization gap.
3.1 THE RATIONALITY GAP
Unlike the other quantities defined above, the rationality gap is novel and less intuitive, and so we discuss it more in depth. The rationality gap, like all other quantities in the RRM bound, applies to any learning procedure and not only to SSS algorithms. Indeed, our empirical results show that rationality is typically small for both SSS and end-to-end algorithms, and so it is not this gap but rather the memorization gap that accounts for the difference in their generalization behavior.
To build intuition for the rationality gap, consider example of training procedure T that input a train set S, has 70% test accuracy and a 10% rationality gap with noise parameter = 5%. In the nynoisy experiment, the classifier ʃ output by T recovers the original uncorrupted label for 80% of the 17- n datapoints for which it received the wrong labels. In contrast, 10% rationality gap means the same classifier will only succeed in recovering the label of 70% of unseen test samples.
Intuitively, such classifier is being "irrational" or "inconsistent" in the sense that it succeeds better on datapoints on which it was given the wrong label, then on datapoints on which it was given no label at all. (In error-correcting code parlance, it handles corruption errors better than erasure errors.) We can turn this intuition into formal argument, by giving transformation from such a training algorithm T to an algorithm T" that achieves roughly 80% test accuracy. On input a fresh unseen datapoint ær the algorithm T chooses random label ~ Y, runs T on the train set S O (Z,, })} to obtain some classifier f. and outputs f(x). Up to low-order terms, T" will achieve test accuracy at least as good as the performance T on noisy datapoints, which is 80%. The above reasoning leads to the proof of the following theorem (see also Appendix
Theorem 3.2 (Performance on the table theorem, informal). For every training procedure T and distribution Disso Diamm D there exists a training procedure T satisfying Testi" 2 Testr + rationality gap robustness gap o1).
Why do natural algorithms have small rationality gap? Empirically, the rationality gap is of- ten small or zero for both SSS and end-to-end supervised learning algorithms, particularly for better- performing ones. (See middle panels of Figure and 3) Theorem 332 provides an "economic explanation" for this phenomenon: a rational agent would not use a classifier with a positive ratio- nality gap since this amounts to "leaving performance on the table". However, this transformation comes at a high computational cost; inference for the classifier produced by T" is as expensive as retraining from scratch. Hence Theorem 3.2 does not fully explain why natural algorithms tend to have small rationality gap. In this paper we take low rationality gap as an ampirically-justifiaee as- sumption. We believe that both proving that natural algorithms have small rationality gaps, as well
7

---

Published as a conference paper at ICLR 2021
coming up with computationally efficient transformations to extract performance from rationality gaps, are important open questions.
Does assuming small rationality gap trivialize generalization? Since the definition of the ratio- nality gap involves the test accuracy, the reader might wonder if assuming small rationality is not tantamount to assuming a small generalization gap. However, there is nothing "irrational" about a large generalization gap, and indeed many excellent classifiers have 100% train accuracy. In con- trast, it is irrational to "leave performance on the table" and use a classifier with test accuracy p when can be transformed into one with significantly better accuracy. Concretely, our empirical studies show that the rationality gap is uniformly small, even for end-to-end classifiers that have large gen- cralization gaps. Hence, by itself, rationality is not enough to guarantee small generalization gap.
Is assuming small rationality gap even needed? Since SSS algorithms use simple classifiers, the reader may wonder why need the generalization bounds using standard tools such as Rademacher complexity. The issue that the representation used by SSS algorithms is still sufficiently werrparamettrizzd to allow memorizing the training set. As a pedagogical example, consider a representation-lcaaming procedure that maps label-free training set æ representation r X' + R under which the differently labeled æ's are linearly separable. Moreover, suppose that the representation space has dimension much smaller than n, and hence a linear classifier would have small complexity under any reasonable measure. Without access to the labels, we can transform to a representation r' that on input x outputs r(x)) if x is the training set, and outputs the all-zero vector (or another trivial value) otherwise. Given sufficiently many parameters, the representation r' (or a close-enough approximation) can be implemented by a neural network. Since r and r' are identical on the training set, a learning procedure using r' will have the same train accuracy and (small) memorization gap. However, the generalization gap of such a procedure will be large, since it will not achieve better than trivial accuracy unseen test examples. The issue here is not that the representation "memorizes" the train set. Representations of practical SSS algorithms are highly over-parameterized and are quite likely to memorize specific aspects of the training set. Rather, the issue is that the representation artificially behaves differently on test points in a way that decreases its performance. It is the latter property that makes the classifier "irrational", and violates the small rationality gap assumption.
gap assumption and cannot directly prove
EMPIRICAL STUDY OF THE RRM BOUND
In support of our theoretical results, conduct an extensive empirical study of the three gaps and empirically evaluate the bound from Equation T for a variety of SSS algorithms for the CIFAR- 10 and ImageNet datasets. We provide summary of setup and findings below. For a full deseription of the algorithms and hyperparameters, see Appendix D
smmdrr22
IntoMin
InDDas
amdim CMC
simcir
5.46%
Mest
Most
Rational
Ineeiionl
Robustress
Retionality (%)
Memorization (56
Figure 3 Robustness, Rationality and Memorization for ImageNet. Each point represents a different combination of sulf-super learning algorithm (e.g.. SimCLR), backbone architecture (e.g.. ResNet- 50) and simple classifier (e.g., linear classification). Star indicates experiments with 10 augmentations per training sample. Noise level is 1 5%. Full experimental details in Section D
SSS Algorithms (Tpe, We consider various self-supervised training algorithms that learn a representation without explicit training labels. In our study, we include methods based on contrastive learning such as Instance Discrimination (Wu et al.] 2018). MoCoV2 (He et al. 2020), SimCLR (Chen al. 2020alb b), AMDIM (Bachman et al.) 2019), CMC (Tian et al. [219)). InfoMin (Tian ctt al. 2020) as well as adversarial methods such as BigBiGAN (Donahue & Simonyan, 2019). For
the second phase of training (also known the evaluation phase (Goyal et al. 2019)), we consider
8

---

Published as a conference paper at ICLR 2021
simple models such as regularized linear regression, small Multi-Layer Perceptrons (MLPs). For each evaluation method, we run two experiments: 1) the clean experiment where we train The on the data and labels (x, y): 2) the 1y-oisy experiment where we train Tm, on (z, ÿ) where y are the noised labels. Unless specified otherwise we set the noise to 5%
Adding augmentations. We investigate the effect of data augmentation on the three gaps and the theoretical bound. For each training point, we sample random augmentations (t = 10 unless stated otherwise) and add it to the train set. Note that in the noisy experiment two augmented samples of the same original point might be assigned with different labels. We use the same augmentation used in the corresponding supe-vupe training phase.
Results. Figures and 2 provide summary of our experimental results for CIFAR-10 10. The ro- bustness and rationality gaps are close zero for most SSS algorithms, while the memorization gap is usually the dominant term, especially so for models with larger generalization gap. More- over, we see that C* often produces a reasonably tight bound for the memorization gap, leading to generalization bound that can be as low as 5-10%. In Figures 3 and and 4 we give a summary of our experimental results for SSS algorithms on ImageNet. Again, the rationality and robustness gaps are bounded by small constants. Notice, that adding augmentations reduces memorization, but may lead to an increase in the rationality gap. This is also demonstrated in Figure 5 where we vary the number of data augmentations systematically for one SSS algorithm (AMDIM) CIFAR-10. Since computing the Theorem II bound for ImageNet is computationally expensive (See Appendix [D.5. compute it only for two algorithms, which achieve non-vacuous generalization bound of 48%.
Theorem I bound
easn Round Dotraatten
Bertonaalty Gopp tualtnn Gupp
Rabuctions D:D
Hartonall by
10
Genandizztion
0
Augrintationn persarple
Figure 4 The RRM bound of SSS methods on ImageNet, with models sorted by the generaliza- tion gap. We plot the robustness, rationality and memorization gaps. Similar to Fogiurre I] for most models, the bound is tight and dominated by the memorization gap. Theorem I bound is marked for the two leftmost models (we did not evaluate it for the others, for computational reasons).
Figure 5 355EEna Empirical RRM for the AMDIM SSS model on CIFAR-10 with increasing number of augmentations. While robust- ness and memorization gaps decrease, and so does our generalization bound, the ra- tionality gap increases since Drain and Dies grow apart.
5 CONCLUSIONS AND OPEN QUESTIONS
This work demonstrates that SSS algorithms have small generalization gaps. While our focus is on the memorization gap, our work motivates more investigation of both the robustness and rationality gaps. In particular, we are not aware of any rigorous bounds for the rationality gap of SSS algo- rithms, but view our "performance on the table" theorem (Theorem 3.2) as a strong indication that it is close to zero for natural algorithms. Given our empirical studies, we believe the assumptions of small robustness and rationality conform well to practice.
Our numerical bounds are still far from tight, especially for ImageNet, where evaluating the bound (more so with augmentations) computationally expensive. Nevertheless, we find it striking that already in this initial work, we get non-vacuous (and sometimes quite good) bounds. Furthermore, the fact that the empirical RRM bound is often close to the generalization gap, shows that there significant room for improvement.
Overall, this work can be viewed as additional evidence for the advantages of SSS algorithms over end-to-end supervised learning. Moreover, some (very preliminary) evidence shows that end-to- end supervised learning implicitly separates into a representation learning and classification phases (Morcos et al.) 2018). Understanding the extent that supervised learning algorithms implicitly per- form SSS learning is an important research direction in its own right. To the extent this holds, our work might shed light on such algorithms' generalization performance well.

---

Published as a conference paper at ICLR 2021
6 ACKNOWLEDGEMENTS
We thank Dimitris Kalimeris, Preetum Nakkiran, and Eran Malach for comments on early drafts of this work. This work supported in part by NSF award CCF 1565264, IIS 1409097, DARPA grant W91 INF2010021, and a Simons Investigator Fellowship. We also thank Oracle and Microsoft for grants used for computational resources. Y.B is partially supported by MIT-IBM Watson AI Lab. Work partially performed while G.K. was an intern at Google Research.
REFERENCES
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In 36th ternational Conference Machine Learning, ICML 2019, pp. 477-502. International Machine Learning Society (IMLS), 2019.
Philip Bachman, R Devon Hjelm, and William Buchwalter. Learning representations by maximizing mutual information across views. In Advances in Neural Information Processing Systems, pp- 15535-15545, 2019.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexitie: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov::463-48) 2002.
Peter L Bartlett, Dylan Foster, and Matus Telgarsky. neural networks. In Advances in Neural Information Processing Systems, pp. 6240-6249, 2017.
margin bounds for
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116(32):15849 15854, 2019.
Avrim Blum, Merrick L. Furst, Michael J. Kearns, and Richard Lipton. Cryptographic prim- itives based on hard learning problems. In Douglas R. Stinson (ed.), Advances in Cryptology CRYPTO '93, 13th Annual International Cryptology Conference, Santa Barbara, California, USA, August 22-26, 1993, Proceedings, volume 773 of Lecture Notes in Computer Science, pp- 778-291. Springer, 1993. doi: 10.1007/3-540-4833 540--444--449-22- 24.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Vose Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 10836-10846. Curran Associates, Inc., 2019.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. arXiv preprint urXiv:2002.05709, 2020a.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton. Big self- supervised models are strong semi sumi-vupee learners. arXiv preprint arXiv:2006. 10029, 2020b.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003.0420 2020c.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-255. Icee, 2009.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 1 04.0050 2018.
10

---

Published as a conference paper at ICLR 2021
Jeff Donahue and Karen Simonyan. Large scale adversarial representation learning. In Advances in Neural Information Processing Systems, pp. 10542-10552, 2019.
Gintare Karolina
Dziugaite and Daniel Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008, 2017.
William Falcon and Kyunghyun Cho. A framework for contrastive self-supervised learning and designing new approach, 2020.
Benoît Frénay and Michel Verleysen. Classification in the presence of label noise: survey, IEEE Iransactions on neural networks and learning systems, 25(5)8845-869, 2013.
Spyros Gidaris. Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. arXiv preprint arXiv:/803.077 1803.07788, 2018.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Advances in Neural Information Processing Systems, volume 75 of Proceedings of Machine Learning Re- search, pp. 297-299, PMLR, 06-09 Jul 2018.
Priya Goyal, Dhruv Mahajan, Abhinav Gupta, and Ishan Misra. Scaling and benchmarking self- supervised visual representation learning. In Proceedings of the IEEE International Conference on Computer Vision, pp. 6391-6400, 2019.
Michael Gutmann and Aapo Hyvärinen. Noise contrastie estimation: new estimation principle for unnormalized statistical models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statisties, pp. 297-304, 2010.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. 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 of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9729-9738, 2020.
Dan Hendrycks, Mantas Mazeika, Saurav Kadavath, and Dawn Song. Using self-supervised learn- ing can improve model robustness and uncertainty. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Bun Fox, and Garnett (eds.), Advances Neural Information Processing Sys- Curran Associates, Inc., 2019.
tems 32, pp.
Alex Krizhevsky et al. Learning multiple layers of features from tiny images, 2009.
Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable self-supervised learning. arXiv preprint arXiv:2008. 000044 2020.
Pengpeng Liu, Michael Lyu, Irwin King, and Jia Xu. Selflow: Self-supervised learning of optical flow. In Proceedings of the IEEF/VV Conference on Computer Vision and Puttern Recognition (CVPR), June 2019.
Naresh Manwani and PS Sastry. Noise tolerance under risk minimization. IEEE transactions cybernetics, 43(3): 146-1151,1 1551, 2013.
Ishan Misra and Laurens van der Maaten. Self-supervised learning of pretext-invariant representa- tions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
Ari S. Morcos, Maithra Raghu, and Samy Bengio. Insights on representational similarity in neural networks with canonical correlation, 2018.

---

Published as a conference paper at ICLR 2021
Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable to explain general- ization in deep learning. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Process- ing Systems 32: Anmual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp- 11611-11622, 2019.
Behnam Neyshabur, Srinadh Bhojanapalli, David Mcallester, and Nati Srebro. Exploring general- ization in deep learning. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vish- wanathan, and R. Gamett (eds.), Advances in Neural Information Processing Systems 30, pp- 5947-5956. Curran Associates, Inc., 2017.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. To- wards understanding the role of over-parametrization in generalization of neural networks. CoRR, abs/1805. 2018.
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.
David Page.
How to
train your resnet.
https: ptttps://myttee.al.
how-to- -o----o---ooo---------------- ressetttrrreee---ee----- waweeet--aarchttttureee 2018.
Deepak Pathak, Philipp Krahenbuhl, Jeff Donahue, Trevor Darrell, and Alexei A Efros. Context encoders: Feature learning by inpainting. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2536-2544, 2016.
Mirco Ravanelli, Jianyuan Zhong, Santiago Pascual, Pawel Swietojanski, Joao Monteiro, Jan Tr- mal, and Yoshua Bengio. Multi-task self-supervised learning for robust speech recognition. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6989-6993. IEEE, 2020.
Cynthia Rudin. Stability analysis for regularized least squares regression. arXiv preprint cs/0502016, 2005.
Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khandeparkar. A theoretical analysis of contrastive unsupervised representation learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 5628-5637, PMLR, 2019.
Mingxing Tan and Quoe V Le. Efficientnet: Rethinking model scaling for convolutional neural networks. arXiv preprint arXiv: 1905. 1946, 2019.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. abs/1906.05849, 2019.
Contrastive multiview coding. CoRR,
Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. What makes for good views for contrastive learning. arXiv preprint arXiv:2005. T00.:2005./0233,, 2020.
Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-Antoine Manzagol. Extracting and composing robust features with denoising autoencoders. In Proceedings of the 25th international conference on Machine learning, pp. 1096-1103, 2008
Zhirong Wu, Yuanjun Xiong, Stella Yu, and Dahua Lin. Unsupervised feature learning via non- parametric instance-level discrimination. arXiv preprini 1 2018
Sergey Zagoruyko and Nikos Komodakis.
Wide residual networks.
arXiv preprint
arXiv:1605.07146, 2016.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
12

---

Published as a conference paper at ICLR 2021
Richard Zhang, Phillip Isola, and Alexei A Efros. Colorful image colorization. In European confer- ence on computer vision, pp. 649-666. Springer, 2016.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Non-vacuou generalization bounds at the imagenet scale: pac-bayesian compression approach. In 7th Inter- national Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
13

---

Published as a conference paper at ICLR 2021
A MUTUAL INFORMATION FACTS
Lemma A.1. Af B are two Bernoulli random variables with nonzero expectation then
E[ -] V
B) BBB]
Proof. A standard relation between mutual information and Kl.-divergence gives
(AA; B) -DrI(VA,ellAAP))
On the other hand, by the Pinsker inequality,
sup PA.B(S) -PAx((5) & V DKLLAsolPPAPE V I(A, B). sc x0(0.))((0.1
Thus (letting S - ((1,1)()
Pr[A = 1, Pr(A= Pr S B),
Consequently,
E E B]A S V LTAA BJ) B(B)
Lemma A.2. For three random variables W,X,X Y, s.t. X and Y are independent, T(W: X, Y) 2 T(W; X) I(W;Y)
Proof. Using the chain rule for mutual information we have:
(W;X,,1 Y) I(W: X) I(W;YIX)
Since X,Y are independent, (X) = (Y) and since conditioning only reduces entropy, we have HY, X) H()))), Combining the we get,
I(W;YIX) -X(IX) H(Y[W,X) X) -YY) W
=I(WYY)
Thus have that (W;X,MM Y) I(W; X) I(W;Y).
Note that by induction we can extend this argument to show that L(W; X1, 11, where X; are mutually independent.
((W;
B SIMPLE CLASSIFIERS IMPLY SMALL MEMORIZATION GAP
In this appendix we we prove our main theoretical result (Theorem B.4). We will start by giving formal definition of SSS algorithms and restating the definition of our complexity measures.
Definition B.1 (SSS Algorithms,, restated). An SSS algorithm over (X x )))" is procedure
(T pe Tm. that takes as input a set (ar, y) and operates as follows:
1. T pe takes the (label free) data points input and outputs representation :. - R for some set R;
2. On input the points {(r(x)), 1 Ta outputs a simple classifier R V;
3. The output is classifier f X' + y defined f(x) g(((x)) for every E X.
We restate the definitions of complexity measure.
14

---

Published as a conference paper at ICLR 2021
Definition B.2 (Complexity of training procedures, restated), Let T be training procedure taking
as imput (r, 3) = {(ri. 91) E (R x y)" and outputting a classifier g r + y and let 7) > 0. For every training set (r,y):
The minimum description length of T with respect to r, y, is defined as (g) where is the random variable T(r, ÿ) in the 7 noisy experiment.
Cmdll rr.g.n (T)
The prediction complexity of T with respect to r, y, 7 is defined as,
C y.., (T)
Σ (g((r)))
where g(rs) and jt are viewed as random variables over the sample space induced by choos- ing ý according to the no-oisy experiment w.r.t. y and letting T(x,, Ø).
The deviation complexity T
T with respect to r, y, 1 is defined as
u (T) == n n I():N)
where A g(:)) y (mod (D') and N taken over both the above sample space and the choice i ~ [n] and identifying y with (o.....,100 | 1}.
y: (mod Dl are random variables
The following theorem shows that Cde is upper bounded by CP, which in turn is bounded by the operational entropy of g.
Theorem B.3 (Relation of complexity measures). For every r, y. > O, and C+ S Cr (T)
where is the classifier output by T (considered as a random variable).
Proof. Fix T,r, y. We get ÿ by choosing i.d random variables .I.....NN each equalling with probability 1 -n and uniform otherwise, and letting ūi = Yt + N₂ (mod (2)).
We start by proving the second inequality CF S H(g). Let g T(r, 9) and define p (g(ri).....g(r., be the vector of predictions. Then,
C (T) = IPER V1) I
(p)
with the last equality holding since for fixed yı. N, determines Dt and vice versa. However, since the full vector p contains only more information than ps. the right-hand side of ( is most En I(p; N2) < I(p; NN....,,NN) using the fact that N; random variables are independent (see Lemma A.2p. For a fixed r. the value of is completely determined by y and hence the entropy of is at most (g), establishing the second inequality of the theorem.
We now turn to the first inequality C+: C*,,,n
C. (T). Let A, pt 10-- Di (mod [)]). Then,
C n M-.
(T)
E T(ps; N₂) 3~([n]
E I(A,;N,) j~(n]
since p; determines A, and vice versa. But, since N, = Nli = j and A, Ali = j (where N A the random variables defined in Definition B.2). the right- hand side of equals
E I(A:Nli = 1) = E H(Nii j) H(N = j) [~[[N]
(4)
Since Ni.... N₂ are identically distributed, H(N = =) = H(N) which means that the right- hand side of equals
H(N) - E H(NA, = 1) > H(N) H(N I(A;N) j~[n]
with the inequality holding since on average conditioning reduces entropy. By definition [(A; N) C (T), establishing what wanted prove.
15

---

Published as a conference paper at ICLR 2021
The complexity measures C and C* are defined with respect fixed train set (r, y), rendering them applicable for single training sets such as CIFAR-10 10 and ImageNet that arise in practice. If D is a distribution over (r. y). then define the complexity measures C and C with respect D as the average of the corresponding measure with respect to (r, y) ~ DD We now restate Theorem I1:
M restated). Let T = (Tpm: TR) be a training procedure obtained by first training T a: E X to obtain a representation r X - 'R. and then training Ta (r)
Theorem B.4 (Theorem
where y E y" to obtain classifier g R + V. Then, for every noise parameter > and distribution Drnin over (
Memorization gap(T) Train TrainD munin ((1) :
NTrain ( T(1)
cd
(Tar) Zn
1
?
where D, is the distribution over (R 3)nh induced by Tpm on Dunie-
Note that the bound on the right-hand side is expressed only terms of the complexity of the second stage The and is independent of the complexity of Tpe- The crux of the proof is showing (close to) independence between the corrupted indices and prediction deviation of resulting from the noise.
Proof. Let (r, y) be sampled by first drawing (ar, y) Duzia over ()) then applying r = r(æ) where r = (x)) Consider the sample space of sampling ÿ according to the n--oiss distribution with respect to Y, computing g = (r, ÿj), and sampling [n]. We define the following two Bernoulli random variables over this sample space:
{o
(R.) - otherwise
{1 1s + y:
Z = 11A
B B= L
=
otherwise
For given r, y. since Z determined by A and B is determined by N, I(Z; B) S I(A;N) C* (r. (Tm)/n, n. By Lemmal A. for every Bernoulli random variables B, Z
B|Z]
E B = 1] = B) B
And hence in our case (since E[B] = 17).
E 2 - B <
cllc C.a.n
(Tic)
But [[ corresponds to the probability that g(r) for (r, y) in the train set, while E| B = 1] corresponds to this probability over the noisy samples. Hence the memorization gap bounded by
Co m (Tm)
dd u. (Tt)
cdle (Tin)
1
I
(r.g))~,,
(r.y)>.,
2n
2T
17
using the Jensen inequality and the concavity of square root for the first inequality.
C POSITIVE RATIONALITY GAP LEAVES ROOM FOR IMPROVEMENT
In this appendix, we prove the "performance on the table theorem" that states that we can always transform robust training procedure with positive rationality gap into training procedure with better performance:
Theorem C.1 (Performance on the table theorem. restated), For every training procedure T and Dn there exists a training procedure S such that
Dians Th T7, if Drnm
Tests. NTrainn, p., (y) -(1)
(S)
where o(1) is term that vanishes with n, and under the assumption that Trainy, 2 NTraing,
16

---

Published as a conference paper at ICLR 2021
For any reasonable training procedure T. performance noisy train samples will not be better than the overall train accuracy, and hence the assumption will be satisfied. In particular (since we can always add noise to our data), the above means that test performance is at least Testy + A where = NTraing - Testr is the rationality gap of T. Hence if the rationality gap is larger than the robustness gap, performance of "irrational" networks. (Note that the robustness gap of almost all standard training procedure is at most 7) and in fact often much smaller.) We stress that the procedure of Theorem 3.2 while running in "polynomial time", is not particularly practical, since it makes inference be as computationally expensive as training. However, is a proof of concept that irrational networks are, to some extent, "leaving performance on the table".
obtain a procedure S' whose clean
use the above to improve the test
Proof. Let T be a procedure as above. Our algorithm S would be the following:
The algorithm will not do any training but input labels D {z ū:)} simply stores these labels.
Training:
On input a data point x, Algorithm S will choose i E [pi] at random, and run T the data D replacing the i-th sample with (xr, 77) where ÿ is chosen uniformly at random. The output is ((x) where / is the classifier output by T
Inference:
First note that while the number of noisy samples could change by one by replacing (2t, ys) with (I, ū). since this number is distributed according to the Binomial distribution with mean 7/n and standard deviation (11- 17 > this change factor. If y has classes, then with probability 1- - 1/k we will make (z, ÿ) noisy (y * ÿ) in which case the expected performance
affect probabilities by at most o(1) additive
it will be NTrain--(7)- With probability 1/k, choose the correct label y in which case performance on this sample will be equal to the expected performance on clean samples which by our assumptions is at least NTrainT as well.
D EXPERIMENTAL DETAILS
We perform an empirical study of the RRM bound for a wide variety of self-supervised training methods on the ImageNet (Deng al. 2009) and CIFAR-I0 (Krizhevsky et al., 2009) training datasets. We provide a brief description of all the self-supervised training methods that appear in our results below. For each method, we use the official pre-trained models on ImageNet wherever available. Since very few methods provide pre-trained models for CIFAR-10, we train models from scratch. The architectures and other training Table H.3 Since primary aim is to study the RRM bound, we do not optimize for reaching the state-of-the-art performance in our re-implementations. For the second phase of training, we use L2-regularized linear regression, small non-interpolating Multi-layer perceptrons (MLPs).
are summarized in [Table H.4 and
D.1 SELF-SUPERVISER TRAINING METHODS (Tra:)
There are a variety of self-supervised training methods for learning representations without explicit labels. The two chief classes of self-supervised learning methods are:
1. Contrastive learning: These methods seek to find an emhedding of the dataset that pushes a positive pair of images close together and pair of negative images far from each other. For example, two different augmented versions of the same image may be considered a positive pair, while two diffferent images may be considered a negative pair. Different methods such as Instance Discrimination, MoCo, SimCLR, AMDIM, differ in the the way they select the positive/negative pairs, as well other details like the use of memory bank or the encoder architecture. (See Falcon & Cho (2020) for detailed comparison of these methods).
2. Handcrafted pretext tasks: These methods learn a representation by designing a fairly gen- eral supervised task, and utilizing the penultimate or other intermediate layers of this net- work as the representation. Pretext tasks include a variety of methods such as predicting the rotation angle of input image (Gidaris et al.) 2018), solving jigsaw puzzles (Noroozi) & Favaro, (0166). colorization (Zhang et al. 2016), denoising images (Vincent et al. 2008) image inpainting (Pathak et al. 2016).
17

---

Published as a conference paper at ICLR 2021
Additionally, adversarial image generation be used for by augmenting the image generator with an encoder (Donahue & Simonyam 2019). We focus primarily on contrastive learning methods since they achieve ofate-of- performance. We now describe these methods briefly.
Instance Discrimination: (Wu et al.) 2018) In essence, Instance Discrimination performs super- vised learning with each training sample separate class. They minimize the non-parametric softmax loss given below for the training dataset.
explef/o/T) J(O) = Σ log Σ exp(uf
(6)
where (2;) is the feature vector for the i-th example. They use memory banks and a con- trastive loss (also known as Noise Contrastive Estimation or NCE (Gutmann & Hyvärinen, 2010)) for computing this loss efficiently for large datasets. So in this case, positive pair is image and itself, while a negative pair is two different training images.
Momentum Contrastive (MoCo): (He al. 2020) MoCo replaces the memory bank in Instance Discrimination with a momentum- query encoder. MoCoV2 (Chen et al.) (020c) uses various modifications from SimCLR, like projection head, and combines it with the MoCo framework for improved performance.
AMDIM: (Bachman et al. 2019) AMDIM uses two augmented versions of the same image. For these augmentations, they use random resized crops, random jitters in color space, random horizontal flip and random conversion grayscale. They apply the NCE loss across multiple scales, by using features from multiple layers. They use modified ResNet by changing the receptive fields to decrease overlap between positive pairs.
TTin et al. 2019) CMC creates two views for contrastive learning by converting each image into the Lab color space. L and ab channels from the same image considered be positive pair, while those from two different images are considered to be negative pair.
CMC:
(Misra & Maaten 2020) PiRL first creates jigsaw transformation of an image (it divides an image into 9 patches and shuffles these patches). It treats an image and its jigsaw as positive pair, and that of a different image as a negative pair. They additionally modify encoder on the jigsaw branch.
PiRL:
SimCLRvl and SimCLRv2: (Chen et al., 2020a b) SimCLR also use strong augmentations cre- ate positive and negative pairs They use random resized crops, random Gaussian blur and random jitters in color space. Crucially, they use a projection head that maps the representations to a 128- dimensional space where they apply the contrastive loss. They do not memory bank, but use large batch size.
InfoMin: InfoMin uses random resized crop, color jitter and gaussian blur, well jigsaw shuf- fling from PiRL.
D.2 SIMPLE CLASSIFIER (Ter
After training the representation learning method, we extract representations for the training and test images. We do not add random augmentations to the training images (unless stated otherwise). Then, we train simple classifier on the dataset (r(zz), , y We use linear classifier in most cases, but we also try small multi-layer perceptron (as long as it has few parameters and does not interpolate the training data). We add weight decay in some methods achieve good test accuracy (See Table HH4] for values for each method.) For the noisy experiment, we set the noise level to 7) = 5%. To compute the complexity bound Cds we run 20 trials of the noisy experiment for CIFAR- 10 and 50 trials for ImageNet.
D.3 EXPERIMENTAL DETAILS FOR EACH PLOT
Figure I This figure shows the robustness, rationality and memorization gap for various SSS algo- rithms trained on CIFAR-10. The type of self-supervised method, the encoder architecture, well
18

---

Published as a conference paper at ICLR 2021
the training hyperparameters described in Table H.3 For the second phase Tm L2- regularized linear regression for all the methods. For each algorithm listed in Table H.3 the figure contains 2 points, one without augmentations, and one with augmentations. Further, compute the complexity measure Cde for all the methods. All the values (along with the test accuracy) are listed in Table
Figure 2 This figure shows the robustness, rationality and memorization for CIFAR-10 for all the same methods in Figure We only include the points without augmentation to show how rationality behaves when (D Dise) are identical. All the values (along with the test accuracy) are listed in Table H.I For the supervised architectures, we train a Myrtle-5 (Page) 2018) convolutional network, ResNet-18 18 (He et al.) (0166) and a WideResNet-28. (Zagoruyko & Komodakis 2016) with standard training hyperparameters.
Figure and Figure 4, These figures show the robustness, rationality and memorization for the Im- ageNet dataset. The type of self-supervised method, the encoder architecture, as well the training hyperparameters are described in Table H.4 For the second phase Ti. we use L2-regularized linear regression for all the methods. The figures also contain some points with 10 augmentations per training image. Further, we compute the complexity measure Cae for all three methods SimCLRv2 with architectures ResNet-50-Lx and ResNet-101-2x. All the values (along with the test accuracy) listed in Table H
Figure This figure shows the effect increasing augmentations. We add t = (..... 10) aug- mentations and re-train the simple classifier. We do this for the CIFAR-10 dataset, AMDIM self- supervised training with the AMDIM encoder and linear regression (See Table H.3) the hyperpa- rameters).
D.4 ADDITIONAL RESULTS
D.4.1 GENERALIZATION ERROR OF SSS ALGORITHMS
To show that SSS algorithms have qualitatively different generalization behavior compared to stan- dard end-to-end supervised methods, we repeat the experiment from Zhang et (2017). We ran- domize all the training labels in the CIFAR- 10 dataset and train 3 high-performing SSS methods on these noisy labels. For results see Table D.I Unlike fully supervised methods, SSS algorithms do not achieve 100% training accuracy on the dataset with noisy labels. In fact, their training accuracies are fairly low (x= 15-25%). This suggests that the empirical Rademacher complexity is bounded. The algorithms were trained without any augmentations during the simple fitting phase for both SSS and supervised algorithms. The SSS methods were trained using parameters described in Table
Table D.1 Empirical Rademacher for fully supervised vs. SSS algorithms CIFAR-IO, Averaged runs. No augmentations were added.
Training method
Architecture/Method
Train Acc
Test Ace
Inception (no aug)
100%
86%
Supervised Zhang et al.
2017
(fitting random labels)
100%
10%
SimCLR (ResNet-50) Linear
94%
92%
(fitting random labels)
22%
10%
SSS
AMDIM (AMDIM Encoder) Linear
94%
87.4%
(fitting random labels)
18%
10%
MoCoV2 (ResNet-18) + Linear (fitting random labels)
69%
67.6%
15%
10%
D.5 RRM BOUND WITH VARYING NOISE PARAMETER
We now investigate the effect of varying noise levels the three gaps well on the complexity. We see that the robustmess gap increases as we add more noise thise-hhis is expected as noise should affect the clean training accuracy. We also observe that the memorization gap decreases, suggesting that C+ as a function of 7) goes down faster than 172 (see Appendix B). The Theorem [I bound on memorization gap also decays strongly with the 7, becoming more fight as the noise increases.
19

---

Published as a conference paper at ICLR 2021
OIFA310 Robustness with noise
100%
Theorem Bound
Rubusiness Gap
Rationality
Memorizztion Gap
Bound
202
30
12
25
20%
Figure D.1 RRM bound with changing vj
D.5.1 CONVERGENCE OF COMPLEXITY MEASURES
We now plot the complexity measures Cds and CP with increasing number of trials for one of the SSS algorithms. As expected, C < C and C converges in about trials for CIFAR-10. the other hand, the complexity computations for ImageNet need many more trials for convergence, since it contains about 10 augmentations x1.2 million training samples making cost prohibitive to compute for all the methods. For the CIFAR-10, we use AMDIM with the AMDIM encoder archi- tecture without augmentations. For ImageNet, we use SimCLRv2 with the ResNet-100 101 architecture with 10 augmentations per training sample.
Thearem bound with increasing trials (CIFAR-10, AMDIM) Complexity with increasing trials (ImageNet, SimCLRy2)
Qo:
Complexity Measure
Theorem bound
C
1.2
CX
1.0
0.8
0.8
0.6
0
10
20
30
40
50
60
Number of trials
Number of trials
(a) Thcorom II bound with increasing trials. The bound based on C* is lower than CP expected, and converges within 20 trials.
(b) Theorem II bound with increasing trials. C is slow converge duc to the large dataset size (10 augmentations x 1.2 million training samples).
Figure D.2 Convergence of Theorem II bounds for CIFAR-10 and ImageNet
E EXAMPLES OF ALGORITHMS WITH LARGE GAPS
While argued that SSS algorithms will tend to have small robustness, rationality, and memoriza- tion gaps, this does not hold in the worst case and there are examples of such algorithms that exhibit large gaps each of those cases.
E.1 LARGE ROBUSTNESS GAP
Large robustness gap can only arise via computational (as opposed to statistical) considerations. That is, if training procedure outputs classifier / E F that achieves average accuracy a
20

---

Published as a conference paper at ICLR 2021
clean train set (X,Y), Y), then with high probability, if (x, Y) is an n7-oisy train set then there exists E FF that achieves a(1 - 77) accuracy on this train set (by fitting only the "clean" " points).
However, the training algorithm might not always be able to find such a classifier. For example, if the distribution has the form (z, y) = (æ, Σ ajæy mod 2) where x' ~ GF Σμ and a E G2) some hidden vector, then there is an efficient algorithm (namely Gaussian elimination) given the samples (z, y) and hence get accuracy 1. However, for every & > and > 0, there is no known efficient algorithm that, given finds a' (2( such that Σ Eaja, known as the learning parity with noise (LPN) problem (Blum et al. 1993).
find
"i perturbed equations of the form {(a, xi) Do [e()) a, mod on a 1/2 + e fraction of the r's. This
The assumption of robustness is necessary for a small generalization gap, the sense that we can come up with (contrived) examples of algorithms that have small rationality and memorization gaps while still having large generalization gap. For example, consider an algorithm T that has large generalization gap (high train accuracy and small test accuracy), and suppose augment to the following algorithm
(Ta
if y "clean" if y is "noisy"
Tx y)
where 0 denotes the constant zero function (e.g., some trivial classifier) and we use some algorithm to estimate whether or not the labels are noisy. (Such estimates can often be achieved in many natural cases.) The algorithm T" will inherit the generalization gap of T, since that depends only on the experiment without noise. Since performance noisy and clean training samples will be the same (close to random), will have zero memorization gap. Since we have assumed small test accuracy, it will have rationality gap also.
E.2 LARGE RATIONALITY GAP
As discussed Section in the case that Deno D robust algorithm with large rationality gap leaves "performance on the table". We can obtain such algorithms by artificially dropping performance on the test data. For example, in the SSS framework, since the representation r is over-parameteriized and can memorize the entire train set, we can consider the trivial representation
in train otherwise
r(x)
0
If we train some simple classifier r(x:) then it can have non-trivial performance the noisy train samples, while getting trivial accuracy on all samples outside the train set.
In cases where Desin and Dise different (for example when Dinin is augmented version of D then we can no longer claim that a large rationality gap corresponds to "leaving performance on the table". For example, do observe (mild) growth in the rationality gap we add more augmented points to the training set.
E.3 LARGE MEMORIZATION GAP
It is not hard to find examples of networks with large memorization gap. Indeed, as mentioned before, any standard interpolating supervised learning algorithm will get a memorization gap close to 1.
F ROBUSTNESS OF LEAST SQUARES CLASSIFIERS
One can prove robustness for classes of algorithms under varying assumptions. As a simple example, record here self-contained observation of how margin leads to robustness in least squares minimization. (We believe that this bound folklore, but weren't able to find the right reference.) This is very simple but also pessimistic bound, and much better ones often hold.
21

---

Published as a conference paper at ICLR 2021
Lemma F.1 Let 21..... R and y1..... ...... Un [k], and consider linear function RR - R that minimizes the quantity Lie())
- -1 and suppose that for p fraction of the i's, the maximum over E [k] of f (xx; is 7 larger than the second-largent value.
Then in expectation, if we let ÿ be the sy-oisy version of y and f minimizes Eselo)eetk [f(z))s = P. we gel that arg maxy f(x.)) = for at least An//²² fruction of the i's.
Proof. We identify y with its "one hot" encoding as vector in Rnn. Let V C Runk be the subspace of all vectors the form the theorem statement, and p (f(21),-... f(x,)) then p Tyy where ITy is the orthogonal projection the subspace If f is the minimizer for the noisy labels and p then p = Hy = Iy (y + e) where e is the noise vector ÿ y
for linear g Rd - R If ʃ is the minimizer in
f(rn).
Hence |p pl probability < 7)) For every point for which the margin was at least in p. if pis prediction is different in then the contribution of the i-th block their square norm difference is at least y² (by shifting the maximum coordinate by -2/2 and the second largest one by 7/2)) Hence at most 4mn/7² of these points could have different predictions in p and p
[[vel I |ell.- But in expectation ||e|| 2mm (since flip label with
G ROBUSTNESS OF EMPIRICAL RISK MINIMIZER
The (potentially inefficient) algorithm that minimizes the classification errors is always robust, Lemma G.1 Let (xx, y) arg minser E faaydre Then for every 1 >> O,
Robustness gTp(T) S 2n.
Proof. Let æ, y be any train set, and let minger Σ (o( and be the minimizer of this quantity. Let ÿ be the nois version of y and let vj be the fraction of on which y/4 + ir. Then,
((a)) S sa+
Hence if is the minimizer of (7) then we know that f(x) o ūs for at most a + 7j fraction of the i's, and so f(x:) * for at most a + 2îj fraction of the i's. Since the train accuracy of T is and in expectation of ij is 7), we get that in expectation
TrainT(1) 2 Traing 27j
22

---

Published as a conference paper at ICLR 2021
H LARGE TABLES
methods, architectures the corresponding results (gaps accura- cies) on CIFAR-I0, sorted by generalization gap. While Figure already plots this data, here we also provide the test performance of the corresponding models.
Table Summary
Data
Generalization Gap
Mem- orization
Theorem bound
RRM
Test
Method
Backbone
Robustness
Rationality
Aug
bound
Acc
mocov2
resnet18
Truc
-7.35
0.07
0.21
0.00
3.47
0.28
67.19
mocov2
wide resnet50 2
True
-6.37
0.18
1.03
0.00
7.63
1.21
70.99
mocov2
resnet101
True
-6.01
0.15
0.71
0.00
6.38
0.86
68.58
mocov2
resnet50
True
-5.88
0.19
0.84
0.00
6.99
1.03
69.68
simelr
resnet50
True
-2.99
0.30
0.55
0.00
0.85
91.96
amdim
resnet101
True
-0.91
0.64
3.70
0.00
25.99
4.34
63.56
amdim
resnet18
True
0.33
0.23
1.15
0.00
8.66
1.38
62.84
mocov2
resnet18
False
1.43
0.15
1.24
0.03
14.14
1.43
67.60
simelr
resnet18
False
1.43
0.28
0.79
0,36
13.35
1.43
82.50
amdim
wide_resnet500,
True
1.60
0.69
2.46
0.00
19.20
3.15
64.38
simelr
resnet50
False
1.97
0.22
0.78
0.97
15.75
1.97
92.00
simelr
resnet50
False
2.24
0.52
1.71
0.01
19.53
2.24
84.94
mocov2
resnet50
False
2.72
0.30
2.96
0.00
24.18
3.26
70.09
mocov2
resnet101
False
2,82
0.33
3.03
0.00
22.78
3.36
69.08
mocov2
wide ride_resnet50.1
False
3.11
0.38
2.79
0.00
22.39
3.18
70.84
amdim
resnet50_bn _bn resnet18
True
3.69
0.84
4.22
0.00
31.12
5.06
66.44
amdim
Falsc
4.34
0.42
4.58
0.00
33.47
5.00
62.28
amdim
amdim_cncoderr
amdim encoder
Truc
4.43
0.68
0.36
3.39
10.32
4,43
87.33
amdim
amdim, amdim_encodee encoder
6.68
2.08
5.69
0.00
70.52
7.77
87.38
amdim
resnet101
False
12.46
1.22
14.26
0.00
100.00
15.49
62.43
amdim
wide resmet50.2
False
13.07
1.70
15.33
0.00
100.00
17.03
63.80
amdim
resnet50. bn
False
14.73
1.81
16.63
0.00
100.00
18.43
66.28
23

---

Published as a conference paper at ICLR 2021
Summary of all the methods, architectures their corresponding results (gaps and accuracies) on ImageNet, sorted by generalization gap. While Figure already plots this data, here we also provide the test performance of the corresponding models.
Table H.2
Data
Generalization Gap
Mem- orization
Theorem bound
RRM bound
Test
Method
Backbone
Robustness
Rationality
Aug
Ace
simelrv2
r50_Ix xks
Truc
-2.34
0.26
0.68
0.00
46.93
0.94
70.96
simelrv2
r101 _2x_sk0
True
0.63
0.10
0.80
0.00
47.90
0,91
77.24
simclrv2
r152.2x_sk0
True
1.00
0.13
0.77
0.10
NA
1.00
77.65
moco
ResNet-50
True
1.32
0.57
0.93
0.00
NA
1.49
70.15
InfoMin
ResNet-50
True
4.88
0.81
1.01
3.06
NA
4.88
72.29
PiRL
ResNet-50
True
6.23
0.29
0.99
4.95
6.23
60.56
InsDis
ResNet-50
True
6.85
0.25
1.13
5,46
NA
6.85
58.30
simcirv2
r101_1x_sk1
False
8.23
0.71
4.66
2.86
NA
8.23
76.07
InfoMin
ResNet-50
False
10.21
2.34
8.96
0.00 NA
11.31
70.31
simelrv2
r152_1x_sk0
False
10.32
1.12
6.93
2.26 NA
10.32
74.17
simelrv2
r101_1x_sk0
False
10.53
1.11
6.99
2.42
10.53
73.04
simclrv2
1k0
False
10.62
0.99
7.31
2.31
NA
10.62
70.69
moco
ResNet-50
False
10.72
1.82
7.86
1.04 NA
10.72
68.39
simelrv2
r152.2x_sk0
False
10.92
0.75
7.45
2.72 NA
10.92
77.25
simelrv2
r101
False
0.74
7.51
2.78
76.72
simolr
ResNet50.1s 1x
False
11.07
1.22
7.73
2.13 NA
11.07
68.73
simclrv2
ResNet-50
False
11.16
0.64
7.67
2.85 NA
11.16
74.99
PiRL
ResNet-50
False
11.43
1.49
8.26
1.68
NA
11.43
59.11
InsDis
ResNet-50
False
12.02
1.40
8.52
2.10
NA
12.02
56.67
amdim
ResNet-50
False
13.62
0.90
9.72
3.01
13.62
CMC
ResNet-50
False
14.73
2.30
12.30
0.13
NA
14.73
54.60
bigbigan
ResNet-50
False
29.60
3.13
25.19
1.27
NA
29.60
50.24
Table H.3 Summary of training methods with their hyper-parameters for CIFAR-10
Self- supervised method
Simple Phase
Backbone Architectures
Self-supervised Training
Evaluation
Optimization
AMDIM Encoder
Adam
ResNet-18 18 ResNet-50
PLB Default parameters
B1 0.8 8g 0.999
AMDIM
Linear
Constant LR -2e-
WideResNet-50
Batchsize 500
ResNet 101
Weight decay = le-6
ResNet-18 ResNet-50 WideResNet-50 ResNet 101
Adam
PLB Default parameters
B1 0.8 3g 0.999
MoCoV2
Linear
Constant LR 2e-4
Batchsize 500
Weight decay = le-6
ResNet-18 ResNet-50
Batchsize 128
SGD
Epochs 200
Momentum 0.9
SimCLR
Linear
Constant LR 0.1
Batchsize = 512
Weight decay le-6
ResNer-50
Epochs 600
24

---

Published as a conference paper at ICLR 2021
Table H.4
Summary of training methods with their syper-parametery for ImageNet
Self-supervised method
Backbone Architecture
Pre-trained Model
Weight Decay
Evaluation
Optimization
Epochs
SGD Momentum 0.9
Instance Discrimination
ResNet-50
PyContrast
Linear
Initial LR = 30
40
LR drop (30)
by factor 0.2
SGD
Momentum 0.9
MoCo
ResNet-50
Official
Linear
Initial LR 30
40
LR drop at (30)
by factor 0.2
SGD
Momentum 0..
PiRL
ResNet-50
PyContrast
Linear
Initial LR 30
40
LR drop at {30}
by factor 0.2
SGD
Momentum 0.9
CMC
ResNet-50
PyContrast
Linear
Initial L.R 30
40
LR drop at (30)
by factor 0.2
SGD
Momentum 0,9
AMDIM
AMDIM Encoder
Official
Linear
Initial LR 30
1e-3
40
LR drop at {15, 25)
by factor 0.2
SGD
Momentum 0.9
BigBiGAN
ResNet-50
Official
Linear
Initial LR 30
le-5
40
LR drop at {15, 25}
by factor 0.2
ResNet-50 1x ResNet-50
SGD Momentum 0.9
SimCLRy1
Official
Linear
1e-6
40
Constant LR 0.1
ResNet-50 SK0
SGD Momentum 0.9
ResNet- 101 2x SKO
SimCLRy2
Official
Linear
1e-6
40
ResNet-157 2x SKO
Constant LR 0.1
ResNet-152 3x SKO
25


Reviews:
[{"review_id": "chMnpXRQjss", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper analyzes the generalization gap for self-supervised learning. This paper's contribution includes the proposal of decomposing the generalization bound into three terms: robustness, rationality, and memorization (RRM). The three terms explain the generalization gap with some different perspectives. With the RRM decomposition's help, it proves that since SSS doesn't memorize data, small robustness and small rationality gap will naturally guarantee a small generalization gap.  \n\nAlthough I believe the RRM is novel and might bring some good insights for future studies, in isolation to self-supervised learning, this paper's main results (on the SSS part) seem to be stating something obvious in a fancy way. It is well understood that self-supervised learning has a small generalization gap, considering downstream tasks only learn from a function class with small capacity. For each T_pre, the generalization gap is guaranteed to be small with uniform convergence. The remark 3.2 doesn't really make sense to me. As for SSS, the T_pre is obtained with x sampled from the marginal distribution (with much more dataset), and T_fit is trained from (x,y) pairs generated from the joint distribution. T_pre is not supposed to see the same training examples, especially y. Therefore T_pre should not be memorizing the data samples. \n\nThe prior work mentioned in this paper in understanding SSL targets to explain why the representation learned from pretext tasks can be useful for the downstream task, hence proving a small generalization error (instead of generalization gap), which is more important in understanding the success of self-supervised learning. And assumptions like (approximate) conditional independence were only to show a small approximation error and were not needed for proving a small generalization gap. Therefore removing these assumptions does not seem to be a real contribution here. \n\nIt will be more interesting to me if the paper focuses more on the RRM decomposition and gives some further insights into how to use these terms in the future to improve the generalization performance of certain algorithms or tasks. \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "RELWFkTuRLr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The present paper aims to understand the generalization capability of self-supervised learning algorithms that fine-tune a simple linear classifier to the labels. Analyzing generalization in this case is challenging due to a data re-use problem: the same training data that is used for self-supervised learning is also used to fit the labels. The paper addresses this issue by implicitly conditioning on the training covariates x and then deriving generalization bounds that depend only on (hypothetical) noise to the labels y. The paper show that, empirically, the dominant factor in generalization error is a certain quantity called the \"memorization gap\", which can also be upper-bounded via theoretical analysis (the theoretical bound seems to be loose by about a factor of 4 compared to the empirical measurement, but is still non-vacuous in many cases). Interestingly, this is *not* the case for standard supervised learning, likely to the higher-complexity models used to fit the labels; in that case the memorization gap is high, but a different gap (called the \"rationality gap\") is large in magnitude but negative.\n\nOverall, the paper is clearly presented, innovative, and has interesting empirical and theoretical results. It seems like a clear accept to me, with my only uncertainty that I am not completely familiar with the related literature. I am also not sure why the authors could not use the Rademacher complexity---are there theoretical obstacles to using it to upper-bound generalization error in this setting, or is the problem that it is too large? If the latter, then have you considered using your approach in settings other than just the self-supervised setting in order to improve on Rademacher complexity bounds?\n\n====\n\nFraming comments / questions:\n\n-I don't like the word rationality, since it has a technical meaning in Bayesian statistics that is not the same as the usage here (i agree they are somewhat similar in flavor, but I think it's confusing to conflate them).\n\n-I'm not sure it's correct to say that SS+S is a dominant methodology. In practice we would almost always do full fine-tuning on the self-supervised representation, rather than just the final layer. Still, starting with final layer fine-tuning is a reasonable start for analysis.\n\n-It seems an important point of your analysis is that we can condition on x and then just look at label noise for measuring generalization. It seems like empirical Rademacher complexity bounds also condition on x, so is there a fundamental difference here? (I think you try to address this in Remark 3.3 but I didn't understand your point there.)\n\n======\n\nA few presentation comments:\n\n-I didn't understand this claim: \" An optimal Bayesian procedure would have zero rationality gap, and indeed this gap is typically zero or small in practice.\"\n\n-Drawing lines between the dots (and shading the area under the curve) in Figure 1 is inappropriate, since the different points don't follow a logical linear progression (it's really just a scatter plot).\n\n-In Fact I, why do we need to take the max with zero? The result is still true even without the max, I believe.\n\n-In Fact I, it would be helpful to comment on the effect of changing eta. Do we expect certain of these quantities to get bigger or smaller in that case? Any heuristic intuition for how to choose the best eta?\n\n-Section 2.1 is a bit dense.\n\n-I liked Figure 2 a lot.", "extra_scores": {}, "extra_text": {}}, {"review_id": "OaKprR-2VC", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe authors propose to upper bound the generalization gap via three quantities, namely robustness gap, rationality gap and memorization gap, shows that the memorization gap can be bounded via standard learning theory arguments, and empirically show that all of the three terms are small. The authors also argue that if the rationality gap is large, then the performance can be improved.\n\n1. First of all, I think this paper is highly over-claimed. I don’t see how the proposed methods provably indicates the generalization. In fact, there is no theoretical conclusion on bounding the rationality gap and little theoretical discussion on robustness gap. Instead, the authors only show the empirical estimation on the robustness gap and  rationality gap. I would like to say, such inaccurate claim makes me feel uncomfortable.\n\n2. I would like to argue that, we cannot know the exact rationality gap, as we don’t have the data distribution at any time, thus we need a generalization bound to describe the performance of algorithm on unseen data. How do the authors deal with the rationality gap? I don’t feel empirical estimation on ‘test set’ is an acceptable choice, as ‘test set’ is only a batch of sample of real data distribution. The bound proposed by authors is not a generalization bound, thus it is meaningless to talk about the bound is vacuous or not.\n\n3. Moreover, as we don’t know the exact rationality gap, the claim by Theorem 3.1 is also not meaningful. In other words, even if we find the rationality gap is large when evaluating on test data, what we really do is tuning the model using the test data, not improving the performance of the model on data distribution.\n\n4. The authors argue in the abstract that the bound is independent of the complexity of the representation. However, several properties of the representation, e.g. the dimension, will definitely influence the generalization bound. I don’t feel this argument well-supported.\n\nOverall, the decomposition itself may motivate new idea on improving the current algorithms. However, theoretically, I don’t think this paper is a rigorous paper considering the generalization bound. If the authors want to argue the decomposition have some insight on improving algorithm, the authors should focus more on the intuition, algorithm design and empirical justification. If the authors want to argue the decomposition indicate tight generalization bound, then the authors should give rigorous proof on the bound of all three terms and calculate the bound based on the theoretical prediction instead of empirical simulation. There can be some misunderstanding on some of the points in the paper, but overall, with the current presentation, I think this paper is not ready for acceptance.", "extra_scores": {}, "extra_text": {}}, {"review_id": "LNl_1HjhMUD", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper gives a new perspective on generalization, motivated by the success of self-supervised learning, especially on noisy data. They view the generalization error as consisting of 3 independent components: robustness, rationality and memorization. Informally, robustness measures the degradation in training accuracy due to the addition of noise. rationality measures the gap between noisy training and test accuracy and memorization is the gap between the training error on the uncorrupted and corrupted examples. The main point of the paper is that the memorization gap is smaller for self-supervised, simple algorithms compared to full supervised algorithms. They prove that when the noise is defined by a small fraction of labels being randomly flipped, then the memorization error of such simple algorithms can be bounded in terms of their information-theoretic complexity, independent of the representation they produce. (The proof is simple once the definitions are set up properly).\nThe most interesting part of the paper is an experimental study of several training procedures on benchmark data sets, measuring the three notions of error, matching what their theoretical result and overall motivation suggests. While perhaps not directly relevant to the practice of ML, this paper gives some explanation of the success of self-supervision in a toy setting, and is likely to inspire further research.\n--- You study random label noise. What about attribute noise? And what is the noise is not random but adversarial? Do at least the notions still make sense?\n--- the rationality gap is still confusing, and your dog/cat example does not help. More intuition/better examples would be great.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper offers a new take on generalization, motivated by the empirical success of self-supervised learning.  Two reviewers found the contribution novel and interesting, and recommend acceptance (with one reviewer championing for it).  Two reviewers remain skeptical about the value of the paper, and the authors are encouraged to add a discussion about the points made in these reviews.

I agree with the positive reviewers and would like to recommend acceptance.
Decision: Accept (Poster)