Year: 2021

Abstract:
A large body of work has explored how learned feature representations can be useful for a variety of downstream tasks. This is true even when the downstream tasks differ greatly from the actual objective used to (pre)train the feature representation. This observation underlies the success of, e.g., few-shot learning, transfer learning and self-supervised learning, among others. However, very little is understood about why such transfer is successful, and more importantly, how one should choose the pre-training task. As a first step towards this understanding, we ask: what makes a feature representation good for a target task? We present simple, intuitive measurements of the feature space that are good predictors of downstream task performance. We present theoretical results showing how these measurements can be used to bound the error of the downstream classifiers, and show empirically that these bounds correlate well with actual downstream performance. Finally, we show that our bounds are practically useful for choosing the right pre-trained representation for a target task.

text: A large body of work has explored how learned feature representations can be useful for a variety of downstream tasks. This is true even when the downstream tasks differ greatly from the actual objective used to (pre)train the feature representation. This observation underlies the success of, e.g., few-shot learning, transfer learning and self-supervised learning, among others. However, very little is understood about why such transfer is successful, and more importantly, how one should choose the pre-training task. As a first step towards this understanding, we ask: what makes a feature representation good for a target task? We present simple, intuitive measurements of the feature space that are good predictors of downstream task performance. We present theoretical results showing how these measurements can be used to bound the error of the downstream classifiers, and show empirically that these bounds correlate well with actual downstream performance. Finally, we show that our bounds are practically useful for choosing the right pre-trained representation for a target task.

heading: 1 INTRODUCTION
text: Since the (re)-discovery of neural networks for visual recognition, a plethora of work has observed that the feature representations trained on ImageNet generalize to many downstream tasks, even to new domains (Donahue et al., 2014; Kornblith et al., 2019; Kolesnikov et al., 2020; Wallace & Hariharan, 2020). This observation, and the resulting gain in accuracy even with very limited labels, has heralded new research directions into other ways of learning representations, such as self-supervised learning (Chen et al., 2020) or meta-learning (Snell et al., 2017).
This growing field of representation learning has yielded ostensibly better and better feature representations. However, a closer look reveals many mysterious results. For example, meta-learning methods do not transfer across domains (Guo et al., 2020) and self-supervised representations struggle with fine-grained recognition (Wallace & Hariharan, 2020). These empirical results are extremely valuable, but do not provide a deeper understanding of the corresponding phenomena. On the other side of the spectrum, theoretical work on neural representations is illuminating, but often makes assumptions about models or tasks (Du et al., 2020; Arora et al., 2019b). We lack a general understanding of which neural representations work well for a given task and why.
In this paper, we take a first step towards such an understanding by developing lower and upper bounds on classifier accuracy based on data-driven properties of the feature space. Classical theoretical bounds focus entirely on the complexity of the classifier and ignore the feature space. In contrast, our bounds are based on two intuitive properties of the feature representation (Figure 1): (a) Local alignment, which is the degree to which nearby data points share labels, and (b) local congregation which is the degree to which data points embed close to each other. Intuitively, if the feature representation is locally aligned to the task, then any smooth classifier will be able to model the task well. If it is additionally congregated, then most test points will have nearby training instances, so the classifier will generalize well from limited data. We show that our bounds are not only intuitive and theoretically justified, but also predictive of actual performance in practical settings: on a large dataset of realistic few-shot tasks, we can use our bounds to pick the best pre-trained representation without any training. Taken together, our work is a first step towards a general, intuitive characterization of the feature space that is predictive of downstream classifier performance.

heading: 2 RELATED WORK
text: Analyzing transferability: The motivations of our work lie in understanding the empirical effectiveness of transferring feature representations from supervised (Donahue et al., 2014; Zhai et al., 2019; Kolesnikov et al., 2020) or self-supervised (Goyal et al.; Wallace & Hariharan, 2020; Chen et al., 2020) tasks. With these successes on transfer, and with the availability of a large number of pretrained features trained on a wide variety of domains, there has been an increasing interest in predicting transferability, or in selecting the right features for a particular target task. The simplest approach is to train a classifier with every available pre-trained representation and pick the best performer (Zamir et al., 2018; You et al., 2021). This is both computationally expensive and requires lots of labeled data for the target task. If the pre-training task is a classification task with a known label space then the conditional distribution of targets given pre-training task labels is informative of transfer performance (Tran et al., 2019; Nguyen et al., 2020). However, this approach is difficult to apply if the pre-training task is not classification, or is inaccessible (as with models trained on proprietary data). This inaccessibility of pre-training data is also a problem for approaches that match pre-training and target distributions (Gao & Chaudhari, 2021), or explicitly adapt the pre-training images or label space (Cui et al., 2018). In contrast to these approaches, we focus on directly analyzing the pre-trained feature representation, which allows us to be agnostic to the actual task it was trained on. Our work is most similar in setup and motivation to work on measuring the alignment between feature representations and the target labels (Huang et al., 2021; Bao et al., 2019), but in addition to allowing model selection, yields intuitive and general bounds on accuracy. Our work is orthogonal to work on characterizing tasks and measuring task similarity; this frequently requires pre-trained features in the first place (Achille et al., 2019; Wallace et al., 2021; Song et al., 2020; Dwivedi et al., 2020; Dwivedi & Roig, 2019).
Analyzing feature representations: Our work is also related to research on understanding feature representations in general. Some of this work has focused on understanding invariance properties of convnet features (Aubry & Russell, 2015). Others have looked at what individual feature dimensions mean (Agrawal et al., 2014; Zeiler & Fergus, 2014; Szegedy et al., 2013). Still others have explored if and when features from pre-trained networks transfer well between tasks as a function of the layer chosen (Yosinski et al., 2014) or the architecture (Kornblith et al., 2019). Recently these explorations have been extended to other representation learning techniques, notably self supervised techniques (Wang & Isola, 2020; Wallace & Hariharan, 2020). The insights from these explorations inspire our results. However, these explorations have been primarily empirical, and are therefore limited by the diversity of real world benchmarks that they experiment with. On the other end of the spectrum, there is prior work on theoretical analysis of transfer learning. This prior work often follows the framework proposed by Baxter (2000), and in so doing makes assumptions about the distributions of the different tasks (Maurer, 2009; Du et al., 2020; Galanti et al., 2016; Pentina & Lampert, 2014). In contrast, our approach eschews these assumptions in lieu of data-driven measurements. Data-driven complexity measures have been explored before for analyzing neural network training dynamics and generalization. These measures include eigenvectors of the gram matrix between data points (Arora et al., 2019a), the variance and separation of class-specific manifolds (Cohen et al., 2020), the underlying intrinsic dimensionality of the task (Lampinen & Ganguli, 2018) or the mutual information between representations and the inputs or labels (Shwartz-Ziv &
Tishby, 2017). The corresponding results can be used for analyzing feature representations as well. Our proposed measurements are similar, but are simpler to measure and potentially more intuitive.

heading: 3 PROBLEM SETUP
text: Suppose we are interested in mapping a space of inputs X to a space of targets Y . There is an underlying distribution D over X × Y . We have a feature representation φ : X → Rf which might be pre-trained on another dataset or task, which is inaccessible to us. We will assume that ‖φ(x)‖ ≤ B. For ease of exposition in the paper, we focus on the task of binary classification; the case of multiclass classification is similar. For binary classification, we write the label space as Y = {−1, 1}. Our classifier will use a scoring function that operates on feature space, h : Rf → R. The predicted label will then be sign(h(φ(x))), where if h(φ(x)) is 0, we will arbitrarily assign a label of -1. The set of possible functions h defines the hypothesis class for the classifier; denote this byH. For most of our analysis, we primarily care about the smoothness of the functions in H. We will assume that all functions inH are Lipschitz continuous with Lipschitz constant less than W . Thus: h(φ(x))− h(φ(x′)) ≤W‖φ(x)− φ(x′)‖ ∀h ∈ H (1) We note that one such hypothesis class which is commonly used in practice is the class of linear classifiers of bounded norm: W = { v 7→ wTv; ‖w‖ ≤W } .
Because the zero-one loss, l∗(h(φ(x)), y) = I[sign(h(φ(x))) 6= y] is difficult to analyze, we will use the following continuous upper bound which is standard in theoretical treatments (Mohri et al., 2018)
l(h(φ(x)), y) = min(1,max(0, 1− yh(φ(x)))) ≥ l∗(h(φ(x)), y) (2)
Our focus in this paper is to understand how the properties of the feature extractor φ affect the loss of the classifiers l(h(φ(x))). In particular, we wish to understand how φ impacts (a) the lowest average error that one can achieve, and (b) the true error when one generalizes from a small training set.
We begin by first identifying the key properties of feature representations.

heading: 4 TWO PROPERTIES OF FEATURE REPRESENTATIONS
text: What properties should we use to characterize feature representations? First, we should use properties that are easy to measure, potentially with limited labeled data. Second, these properties should be easy for human developers and practitioners to reason about. Third, they should correlate well with the final accuracy of downstream classifiers. In sum, we want simple, intuitive measurements of the feature space that are predictive of downstream accuracy.
One kind of intuitive measurement is to look at what the feature representation considers as similar. In particular, we could look at pairs of examples that embed close to each other in feature space and ask if they are indeed similar in terms of their ground truth labels. We call this property local alignment. In particular, we make the following definition Definition 1. Suppose α > 0. The local alignment of the feature space φ, denoted by pφa(α) is the probability that two data points (x, y), (x′, y′) ∼ D share a label given that they embed within a distance of α:
pφa(α) , P (y = y ′ ∣∣ ‖φ(x)− φ(x′)‖ ≤ α, (x, y), (x′, y′) ∼ D) (3)
α here is a hyperparameter which governs the resolution at which we do the analysis. Note that this notion of local alignment is different from the alignment proposed by Wang & Isola (2020): the latter looks at how often two data points that are semantically similar embed close to each other, while the former looks at how often two data points that embed close to each other are semantically similar. A feature space that is locally aligned per our definition may not actually be aligned per the definition of Wang & Isola (2020) because two very similar images may be embedded far away from each other.
Local alignment alone may be meaningless if data points do not generally embed close to each other. We also need the feature space to be such that data points generally congregate:
Definition 2. Suppose α > 0. The degree of congregation of the feature space φ, denoted by pφc , is the probability that two points x, x′ sampled from D embed within a distance of α:
pφc (α) , P (‖φ(x)− φ(x′)‖ ≤ α|x, x′ ∼ D) (4)
We have α as a hyperparameter here too.
We now use these notions of local alignment and congregation to analyze the downstream error of classifiers.

heading: 5 WHAT IS THE BEST ACCURACY WE CAN ACHIEVE?
text: Given a feature space φ, what is the best accuracy we can hope to get using scoring functions from H? Recall that these scoring functions are all W -Lipschitz. Our key intuition is that this Lipschitz continuity will force any scoring function inH to produce very similar scores for nearby data points. If these have different labels, then the classifier will be forced to err on at least one of them. To formalize this intuition, we begin with the following claim Claim 1. Consider two data points (x, y) and (x′, y′). If ‖φ(x)− φ(x′)‖ < 1W and y 6= y ′, then:
l(h(φ(x)), y) + l(h(φ(x′)), y′) ≥ 1 (5)
Proof. Observe first that due to Lipschitz continuity of h:
|h(φ(x))− h(φ(x′))| ≤W‖φ(x)− φ(x′)‖ ≤ 1 (6) ⇒ h(φ(x′)) > h(φ(x))− 1 (7)
Now, since y 6= y′, it follows that y′ = −y. Without loss of generality, let us assume that y = 1. Denote l(h(φ(x)), y) by a and l(h(φ(x′)), y′) by b. We will prove this claim by contradiction. Suppose, if possible, that the clam is not true, and a+ b < 1. Since the loss is always non-negative, it follows that a < 1 and b < 1. Thus:
a = max(0, 1− yh(φ(x))) (8) ≥ 1− yh(φ(x)) = 1− h(φ(x) (9)
⇒ h(φ(x)) ≥ 1− a (10)
Taking the other data point:
b = max(0, 1− y′h(φ(x′))) (11) ≥ 1− y′h(φ(x′)) = 1 + h(φ(x′)) (12) ≥ 1 + h(φ(x))− 1 = h(φ(x)) (∵ equation 7) (13) ≥ 1− a (14)
⇒ a+ b ≥ 1 (15) thus yielding a contradiction.
Thus, if two data points are close, at least one of them must be incorrectly classified. We can thus bound the error of the best possible classifier from below by estimating how often this happens:
Theorem 1. Let l be the loss function defined above, and H be a hypothesis class of Lipschitz functions with Lipschitz constant at most W . Let D be a distribution over X × Y , and pφa and pφc defined as above. Then
inf h∈H
Ex,y∼D[l(h(φ(x)), y)] > 1
2
( 1− pφa ( 1
W
)) pφc ( 1
W
) (16)
Proof. We observe that if (x, y), (x′, y′) ∼ D, then the probability that ‖φ(x) − φ(x′)‖ < 1W and y 6= y′ is given by p̃ = (1− pφa(1/W ))pφc (1/W ). Then, for all h ∈ H.
Ex,y∼D[l(h(φ(x)), y)] = 1
2 E(x,y),(x′,y′)∼D[l(h(φ(x)), y) + l(h(φ(x′)), y′)] (17)
≥ p̃ 2 E[l(h(φ(x)), y) + l(h(φ(x′)), y′) ∣∣ ‖φ(x)− φ(x′)‖ < 1 W and y 6= y′] (18)
≥ p̃ 2
(19)
(20)
where the second step follows because the loss is non-negative, so only focusing on the case when x and x′ are close but have different labels yields a lower bound. This is true for all h ∈ H, so it is true for the infimum as well.

heading: 6 HOW WELL WILL CLASSIFIERS GENERALIZE?
text: There may be classifiers that yield low error, but it can be challenging to find these from small training sets. Therefore we now ask if we can use the feature space to analyze how well classifiers trained on small training sets might generalize.
While generalization bounds abound, they typically do not include any reasoning about the underlying feature space beyond the maximum norm of feature vectors. As such, these bounds are insufficient for understanding the impact of the feature space on generalization.
Here, we present two kinds of bounds. The first bound uses a similar proof strategy of relying on the Lipschitz continuity of the classifier. The second bound leverages a more traditional Rademacher complexity-based analysis to bound the excess risk (i.e., the difference between the test loss and training loss).

heading: 6.1 BOUNDING THE PROBABILITY OF HIGH-LOSS DATA POINTS
text: Classical generalization bounds are based primarily on concentration inequalities and the law of large numbers. This produces substantially coarse estimates for applications like few-shot learning, where the training dataset has very few labels.
We propose a simpler alternative bound here. We observe that owing to the Lipschitz continuity of the classifier, test data points that are close to training data points will have very similar loss as the corresponding training points, which can be no worse than the loss on the worst performing training example.
Theorem 2. Let Hφ = {z = x 7→ h(φ(x));h ∈ H}. Suppose S is a sampled training set of m points. For any z ∈ Hφ, let lmax(z, S) = max(x,y)∈S l(z(x), y) be the maximum loss z incurs on S. Then, for all > 0 and (x, y) ∼ D:
P (l(z(x), y) > lmax(z, S) + ) ≤ ( 1− pφa ( W ) pφc ( W ))m . (21)
Proof. It can be shown that for any y, l(z(x), y) − l(z(x′), y) ≤ |z(x) − z(x′)| (see Appendix). Further, ∀h ∈ H, h is W -Lipschitz. So we have, for all x, x′, y:
l(z(x), y)− l(z(x′), y) ≤ |z(x)− z(x′)| ≤W‖φ(x)− φ(x′)‖ (22)
It follows that for any (x, y), (x′, y′):
‖φ(x)− φ(x′)‖ < ∆W y = y′
} ⇒ l(z(x), y) ≤ l(z(x′), y′) + ∆ ∀z ∈ Hφ (23)
Note that the probability of sampling such an (x′, y′) is pφa(∆/W )p φ c (∆/W ). If (x ′, y′) is in S, then l(z(x′), y′) ≤ lmax(z, S). Thus, for any (x, y) ∼ D
P (l(z(x), y) ≤ lmax(z, S) + ) ≥ P ( ∃(x′, y′) ∈ S s.t ‖φ(x)− φ(x′)‖ < ∆
W and y = y′ ) (24)
= 1− ( 1− pφc ( W ) pφa ( W ))m (25)

heading: 6.2 BOUNDING THE EXCESS RISK
text: We can also perform a more traditional analysis of the excess risk, which uses the law of large numbers and various concentration inequalities. It is well known that the difference between train loss and the test loss is upper bounded by the Rademacher complexity of the hypothesis class plus a small constant (Mohri et al., 2018). Concretely, with probability greater than 1− δ, the following holds for all h ∈ H:
R(h)− R̂(h, S) ≤ Rm(H) + √ log 1δ 2m
(26)
where R(h) is the test loss (or expected risk), R̂(h, S) is the training loss (or empirical risk), and Rm(H) is the Rademacher complexity ofH. Thus, to bound the generalization error, it suffices to bound the Rademacher complexity ofH, which is defined as Rm(H) = ES∼Dm,σ suph∈H 1m ∑m i=1 σih(xi). Here σi are Rademacher random variables (i.e., σi ∈ {−1, 1},Eσi = 0). The Rademacher complexity is a measure of the size of the hypothesis class, and can be used to bound the difference between a hypothesis’ performance on two sampled datasets. To allow us to define a concrete bound, we will analyze the class of linear classifiers with bounded norm,W . The key insight here is that if, for a particular α, pφc (α) is large, then any two datasets (e.g., a train and a test dataset) that we sample from the underlying distribution will be “similar”, in terms of having nearby data points. As such, linear classifiers will be forced to produce similar scores for both datasets, yielding similar loss. This insight is expressed as the following bound on the Rademacher complexity of the set of linear classifiers composed with φ:
Theorem 3. Let Wφ = {z = x 7→ h(φ(x));h ∈ W}. Let pφc be defined as above. Then the Rademacher complexity ofWφ is bounded above by:
Rm(Wφ) ≤ W
( α √ pφc (α)/2 + 2B √ (1− pφc (α)) + 2(1− pφc (α))2 ) 2 √ m
(27)
Proof sketch: (Full proof presented in Appendix). For any xi ∈ S, there is a probability pφc (α)/2 that the next point xi+1 is (a) within a distance α in feature space, and (b) is multiplied with a Rademacher variable of the opposite sign. Such pairs will effectively cancel out each other except for a small quantity of α, resulting in the first term. The second term is obtained from all the rest of the data points in S, which have to be analyzed in the usual way.
7 IMPLICATIONS
Both the lower and upper bounds (in particular theorem 2) suggest the need for a high pa, namely, a feature space where nearby examples have similar labels. However, the two bounds differ in the need for congregation.
The lower bound suggests that we need a less congregated feature space, i.e., a space where examples are in general far apart. This matches the training objective of self-supervised and contrastive learning techniques, which primarily attempt to push examples apart. This is demonstrated in Figure 3, which shows that ImageNet training and self-supervised training produce not just locally aligned (i.e., high pa), but also non-congregated feature representations (i.e, low pc).
However, the upper bound suggests that good generalization from small datasets actually requires a highly congregated feature space. As such, these highly spread out feature representations can actually yield large generalization errors in few-shot settings, as demonstrated in Table 1, even if they yield much lower errors with large training sets. Thus, finding a good representation for a task is a nuanced decision, requiring one to balance between these conflicting requirements.
Theorem 2 vs 3: The two generalization bounds both demand high congregation, but differ in whether they involve alignment. Interestingly, the Rademacher complexity-based bound does not use pa. Below, we will see that for this reason, this bound is less correlated with the downstream performance.

heading: 8 EMPIRICAL ANALYSIS
text: Above we have shown that pφa and pφc yield bounds on classifier performance. But are they useful enough in practice to make decisions? We first look to see whether they are correlated with actual loss values, and then present potential applications.

heading: 8.1 CORRELATIONS WITH CLASSIFIER ACCURACY
text: We used CIFAR-10(Krizhevsky, 2009) as our test bed. We sampled pairs of classes from CIFAR-10 as “recognition tasks”, resulting in 45 different tasks. For each task we ran 10 different trials. In each trial, we sampled a small 20-example training set to train a linear classifier, and then evaluated the classifier on a large validation set. The training and validation margin losses were averaged over the 10 trials. We used 18 different representations, all normalized to have maximum norm 1, and all with the architecture of a ResNet-18. These representations were trained with labels of varying granularity on ImageNet(Russakovsky et al., 2015), iNaturalist(Van Horn et al., 2018), or CIFAR-100 (see Appendix). For each task and for every representation, we computed our bounds using the labeled validation set to get pφa and p φ c , and using the empirically obtained classifier norm as W (a more practical approach is described in the next section).
Results: For each task, we computed the correlations between our proposed bounds and the corresponding true losses. Histograms of these correlations across the 45 tasks are shown in Figure 4 (scatter plots with individual data points are in Figure 6). We find that the lower bound is extremely
well correlated with the training loss (average Spearman’s ρ 0.93), but less so with the test loss (average Spearman”s ρ 0.55). This is of course expected because the lower bound does not take into account the perils of classifiers trained on small training sets. The difference between the training and test loss correlates very well with our proposed upper bound in Theorem 2 (average Spearman’s ρ 0.80), which is much better than the correlation obtained with the classical bound (average ρ 0.50). Theorem 3 yields a worse correlation that Theorem 2, perhaps because it doesn’t take into account the alignment. Since Theorem 2 yields a stronger correlation, we use this upper bound in conjunction with the lower bound for a more practical experiment on model selection below.

heading: 8.2 APPLICATIONS TO FEW-SHOT TRANSFER
text: We now see if our bounds can help choose the right feature representation for problems with very limited labeled data. In particular, we assume that we have a very small labeled set S (e.g., 10 labeled examples per class) and a larger unlabeled set U . Because labeled data is very limited, one cannot afford to use labeled data for held-out validation sets. Therefore, a way of characterizing feature representations without training and evaluating classifiers is valuable.
Baselines: Much of prior work on estimating transferability assumes that the representations come from classification tasks Nguyen et al. (2020) on accessible datasets Cui et al. (2018), or that an initial appropriate feature representation is available Achille et al. (2019); Dwivedi et al. (2020). With the advent of self-supervised learning Chen et al. (2020) and large proprietary datasets Kolesnikov et al. (2020), and the wide variety of visual domains Wallace & Hariharan (2020), these assumptions are no longer appropriate. We therefore consider only baselines that make minimal assumptions about the pre-trained feature representation and the target task: H-score Bao et al. (2019) and TransRate Huang et al. (2021). Both approaches are based on information-theoretic arguments justifying the use of intra- and inter-class covariance matrices, which are global statistics of the feature representation, in contrast to our more local measurements. In addition, we also include a baseline that chooses a representation at random.
Experimental setup: We run few-shot experiments on two datasets: CIFAR-10 and CUB200(Welinder et al., 2010). The pre-trained representations were obtained by training on iNaturalist, ImageNet and CIFAR-10 (only for CUB-200) with various loss functions. In each case, we sample 50 binary classification problems with 10 labeled examples each; all other examples from the classes involved are unlabeled. To estimate pφa(α) using just 10 labeled examples, we choose α to be large enough that for at least one class, every pair of labeled examples is at most α away in feature space. Our estimate of transferability involves linearly combining our lower bound on error (with a weight of 100 because of its smaller scale) and the upper bound on generalization from Theorem 2; lower values indicate better representations. For the baselines, the unconditional covariance matrix was estimated using the unlabeled data and other label-dependent measurements used the labeled data. We evaluate all approaches in terms of the average accuracy drop relative to the oracle representation (the one which post-hoc yields the highest test accuracy). Thus lower drops are better.
Results: We show results in figure 5. Interestingly, TransRate and H-score seem to have opposite trends on these two datasets, with H-score performing worse than random selection for CUB and TransRate performing worse than random on CIFAR-10 Our approach consistently yields better choices than both baselines on both benchmark datasets thus suggesting the usefulness of our characterization for practical problems.

heading: 9 LIMITATIONS, CONCLUSION AND FUTURE WORK
text: We have presented here a characterization of feature representations that is predictive of how well downstream classifiers will do. Our analysis is limited to classification, though the results may be adapted potentially to other classification-like tasks (e.g., object detection). We also assume that the downstream classifier is linear, which is in line with how feature representations are typically evaluated (Goyal et al.); however practical systems may use more powerful classifiers where our bounds may not apply. Finally, while our bounds are interpretable and predictive, it is not clear if they can be used to drive training objectives. This is an important direction for future work.
Reproducibility: All theoretical proofs and experimental details are included in either the main paper or the appendix. Code and pre-trained representations will be made public upon acceptance.
Ethics statement: This work aims to improve our understanding of feature representations, thus paving the way for more widespread use of pre-trained feature representations. We hope that this makes the power of sophisticated visual recognition techniques available to a much broader community who may not have the data or resources to train big networks from scratch. However, we note that our work focuses only on the average accuracy one can obtain from these representations in a downstream task; we do not delve into the biases that these representations might perpetuate Steed & Caliskan (2021), or privacy or consent issues in the original datasets used to train these
representations Birhane & Prabhu (2021). We suggest that when choosing a pre-trained representation, practitioners should consider not just our characterization of downstream accuracy, but also a broader characterization in terms of the many ethical implications of choosing a representation pre-trained on questionably collected or opaque datasets.

heading: A APPENDIX

heading: A.1 PROOFS
text: Theorem 4. Let f(x) = min(1,max(0, x)). Then f(x)− f(x′) ≤ |x− x′|.
Proof. We do a case-by-case analysis.
1. x ≥ 0, x′ ≤ 1. In this case, f(x′) ≥ x′ and f(x) ≤ x. So f(x)−f(x′) ≤ x−x′ ≤ |x−x′|.
2. x < 0. In this case f(x) = 0. Since f(x′) ≥ 0, it follows that f(x)−f(x′) < 0 < |x−x′|.
3. x′ > 1. In this case f(x′) = 1. Since f(x) ≤ 1 it follows that f(x)−f(x′) < 0 < |x−x′|.
Claim 2. (Used in proof of Theorem 2) Let l(z, y) = min(1,max(0, 1 − zy)). Then l(z, y) − l(z′, y) ≤ |z − z′|.
Proof. l(z, y) = f(1−yz), where f is defined as above. The claim follows directly from Theorem 4.
Theorem 5. Let Wφ = {z = x 7→ h(φ(x));h ∈ W}. Let pφc be defined as above. Then the Rademacher complexity ofWφ is bounded above by:
Rm(Wφ) ≤ W
( α √ pφc (α)/2 + 2B √ (1− pφc (α)) + 2(1− pφc (α))2 ) 2 √ m
(28)
Proof. First note that:
Rm(Wφ) = ES,σ sup z∈Wφ
1
m m∑ i=1 σiz(xi) (29)
= 1
m ES,σ sup
h∈W m∑ i=1 σiw T hφ(xi) (30)
= 1
m ES,σ sup h∈W wTh ( m∑ i=1 σiphi(xi)) (31)
≤ W m ES,σ‖ m∑ i=1 σiφ(xi)‖ (∵ ‖wh‖ ≤W ) (32)
(33) Thus we need to bound ES,σ‖ ∑m i=1 σiφ(xi)‖
Consider any set S of m points sampled from D. Let π be the mapping i 7→ (i + 1) mod m, and define σ′i = σπ(i) and x ′ i = xπ(i). Then, for any z ∈ Hφ we have that ∑m i=1 σiφ(xi) =∑m
i=1 σ ′ iφ(x ′ i) = 1 2 ∑m i=1(σiφ(xi) + σ ′ iφ(x ′ i)).
Note that xi ⊥⊥ x′i and σi ⊥⊥ σ′i. Define ai = I[(σi = −σ′i) and (‖φ(xi) − φ(x′i)‖ < α)]. Then ES,σai = ES,σa2i = pφc (α) 2 , which we will denote as pα.
Therefore:
ES,σ‖ m∑ i=1 σiφ(xi)‖ (34)
= 1
2 ES,σ‖ m∑ i=1 (σiφ(xi) + σ ′ iφ(x ′ i))‖ (35)
= 1
2 ES,σ‖ m∑ i=1 (aiσi(φ(xi)− φ(x′i)) + m∑ i=1 āi(σiφ(xi) + σ ′ iφ(x ′ i)))‖ (36)
≤1 2 ES,σ‖ m∑ i=1 aiσi(φ(xi)− φ(x′i))‖
+ 1
2 ES,σ‖ m∑ i=1 āiσiφ(xi)‖
+ 1
2 ES,σ‖ m∑ i=1 āiσ ′ iφ(x ′ i)‖ (37)
Observe that ai ⊥⊥ σi, and ai ⊥⊥ σ′i. Using this, the second and third terms are similar. The second term yields:
1 2 ES,σ‖ m∑ i=1 āiσiφ(xi)‖ (38)
= 1
2 ES,σ √√√√ m∑ i,j=1 āiājσiσjφ(xi)Tφ(xj) (39)
≤1 2 √√√√ m∑ i,j=1 ES,σāiājσiσjφ(xi)Tφ(xj) (40)
We note that if i 6= j and i 6= π(j) and j 6= π(i) then āiσi ⊥⊥ ājσj . Thus, looking at the expression under the square root:
m∑ i,j=1 ES,σāiājσiσjφ(xi)Tφ(xj) (41)
≤ ∑ i ES,σā2iσ2i ‖φ(xi)‖2 (42)
+ ∑
i,j:i=π(j)orj=π(i)
ES,σāiājσiσjφ(xi)Tφ(xj) (43)
≤B2 ∑ i ES,σā2iσ2i (∵ Eā2i = Eāi = 1− pα) (44)
+B2 ∑
i,j:i=π(j)orj=π(i)
ES,σāiājσiσj (45)
≤B2m(1− pα) +B2 ∑
i,j:i=π(j)orj=π(i)
ES,σāiāj (∵ Eσi ≤ 1) (46)
≤B2m(1− pα) +B22m(1− pα)2 (47)
. Thus:
1 2 ES,σ‖ m∑ i=1 āiσiφ(xi)‖ (48)
≤B 2
√ m(1− pα) + 2m(1− pα)2 (49)
Through similar reasoning, the first term yields:
1 2 ES,σ‖ m∑ i=1 aiσi(φ(xi)− φ(x′i)‖ (50)
≤ 1 2 √√√√ m∑ i=1 ES,σa2iσ2‖φ(xi)− φ(x′i)‖2 (51)
≤ 1 2 √√√√ m∑ i=1 ES,σa2iα2 (52)
= 1
2
√ mpαα2 (∵ Ea2i = Eai = pα) (53)
Putting these expressions back in equation 37, we get:
Rm(Hφ) ≤ W 2m ( √ mpαα2 +B √ m(1− pα) + 2m(1− pα)2 +B √ m(1− pα) + 2m(1− pα)2)
(54) = W ( α √ pα + 2B √ m(1− pα) + 2m(1− pα)2 ) 2 √ m (55)

heading: A.2 SCATTER PLOTS
text: See Figure 6.

heading: A.3 REPRESENTATIONS USED IN EXPERIMENTS
text: In general it is difficult to do statistically rigorous experiments for choosing representations since publicly available pre-trained representations vary wildly in architecture and dimensionality. However, we want to ensure that the characterization we produce is nuanced enough to distinguish between fairly similar representations that are based on the same backbone architecture and the same feature dimensionality. Therefore we used multiple feature representations that are all trained on ResNet 18 on the same 3 datasets (ImageNet, CIFAR-100 and iNaturalist) but with very different loss functions. These representations were trained in the context of an unrelated exploration on the use of coarsely labeled data (see supplementary). For completeness, we present a brief overview of these representations here.
All representations were trained on a combination of a coarsely labeled datasetC and a finely labeled dataset F . C may have some classes that are not present in F . The representations we used are:
1. A representation trained with simple supervised learning on F alone. 2. A representation trained with simple supervised learning on C alone. 3. A representation trained on C ∪ F with two classifier heads, one for coarse categorization
and another for fine-grained categorization 4. A representation trained onC∪F with fine-grained soft pseudo-labels forC obtained using
a classifier trained on F 5. A representation trained onC∪F with fine-grained soft pseudo-labels forC obtained using
a classifier trained on F , and with the pseudo-labels filtered to be consistent with the coarse label,
6. A representation trained on C ∪ F with ground-truth fine-grained. labels for images in C.
6 representations trained on 3 datasets gives us 18 representations. Details on the training are in the paper linked in the supplementary. These pre-trained representations will be released upon acceptance.

heading: A.4 BOUNDS FOR MULTICLASS CLASSIFICATION

heading: A.4.1 PROBLEM SETUP
text: Suppose, as before, we are interested in mapping a space of inputs X to a space of targets Y . There is an underlying distribution D over X × Y . We have a feature representation φ : X → Rf which might be pre-trained on another dataset or task, which is inaccessible to us. We will assume that ‖φ(x)‖ ≤ B. For multiclass classification, our classifier will use a scoring function that scores how well a feature vector matches a class label, h : Rf×Y → R. The predicted label will then be arg maxy h(φ(x), y), where ties are broken arbitrarily. The set of possible functions h defines the hypothesis class for the classifier; denote this byH. For most of our analysis, we primarily care about the smoothness of the functions inH. We will assume that all functions inH are Lipschitz continuous in the first argument with Lipschitz constant less than W . Thus:
h(φ(x), y)− h(φ(x′), y) ≤W‖φ(x)− φ(x′)‖ ∀h ∈ H,∀y ∈ Y (56) We note that one such hypothesis class which is commonly used in practice is the class of linear classifiers of bounded norm: W = { v, y 7→ wTy v; ‖wy‖ ≤W∀y ∈ Y } .
For a data point x with label y, the zero-one loss incurred by scoring function h is l∗(h, φ(x), y) = I[y 6= arg maxy′ h(φ(x), y′)]. We will use the following continuous margin-based upper bound:
l(h, φ(x), y) = min(1,max(0,max y′ 6=y
(1 + h(φ(x), y′))− h(φ(x), y))) ≥ l∗(h, φ(x), y) (57)
We can now prove equivalent lower and upper bounds as below.

heading: A.4.2 LOWER BOUND
text: Claim 3. Consider two data points (x, y) and (x′, y′). If ‖φ(x)− φ(x′)‖ < 12W and y 6= y ′, then:
l(h(φ(x)), y) + l(h(φ(x′)), y′) ≥ 1 (58)
Proof. Observe first that due to Lipschitz continuity of h:
|h(φ(x), y)− h(φ(x′), y)| ≤W‖φ(x)− φ(x′)‖ ≤ 1 2 ∀y (59)
⇒ h(φ(x′), y) ∈ [h(φ(x), y)− 1 2 , h(φ(x), y) + 1 2 ]] (60)
This in turn implies that for any pair of classes y1 and y2,
h(φ(x′), y1)− h(φ(x′), y2) ≥ h(φ(x), y1)− 1
2 − (h(φ(x), y2) +
1 2 ) ≥ h(φ(x), y1)− h(φ(x), y2)− 1
(61)
Now, denote l(h, φ(x), y) by a and l(h, φ(x′), y′) by b. We will prove this claim by contradiction. Suppose, if possible, that the clam is not true, and a+ b < 1. Since the loss is always non-negative, it follows that a < 1 and b < 1. Thus:
a = max(0,max y′′ 6=y
(1 + h(φ(x), y′′))− h(φ(x), y)) (62)
≥ max y′′ 6=y
(1 + h(φ(x), y′′))− h(φ(x), y) (63)
≥ 1 + h(φ(x), y′)− h(φ(x), y) (64) ⇒ h(φ(x), y)− h(φ(x), y′) ≥ 1− a (65)
Taking the other data point: b = max(0, max
y′′ 6=y′ (1 + h(φ(x′), y′′))− h(φ(x′), y′)) (66)
≥ max y′′ 6=y′
(1 + h(φ(x′), y′′))− h(φ(x′), y′) (67)
≥ (1 + h(φ(x′), y))− h(φ(x′), y′) (68) ≥ 1 + h(φ(x), y)− h(φ(x), y′)− 1 (∵ equation 61) (69) = h(φ(x), y)− h(φ(x), y′) ≥ 1− a(∵ equation 65)
(70) ⇒ a+ b ≥ 1 (71)
thus yielding a contradiction.
This claim directly leads to the following lower bound for the multiclass case, with the exact same proof:
Theorem 6. Let l be the loss function defined above, and H be a hypothesis class of Lipschitz functions with Lipschitz constant at most W . Let D be a distribution over X × Y , and pφa and pφc defined as above. Then
inf h∈H
Ex,y∼D[l(h(φ(x)), y)] > 1
2
( 1− pφa ( 1
2W
)) pφc ( 1
2W
) (72)
Note that the only difference between the bounds for the binary and the multiclass case is the factor 2W in lieu of W .

heading: A.4.3 UPPER BOUND
text: We can similarly give the following upper bound. We first begin with the following claim: Claim 4. For the multiclass loss function defined above, and if h isW -Lipschitz as described above,
l(h, φ(x), y)− l(h, φ(x′), y) ≤ 2W‖φ(x)− φ(x′)‖ (73)
Proof. We note that l(h, φ(x), y) = f(maxy′ 6=y(1 +h(φ(x), y′))−h(φ(x), y)), where f is defined in Theorem 4. Theorem 4 directly yields: l(h, φ(x), y)− l(h, φ(x′), y) (74)
≤ ∣∣∣∣(maxy′ 6=y(1 + h(φ(x), y′))− h(φ(x), y) ) − ( max y′ 6=y (1 + h(φ(x′), y′))− h(φ(x′), y) )∣∣∣∣ (75)
= ∣∣∣∣(maxy′ 6=y(1 + h(φ(x), y′))−maxy′ 6=y(1 + h(φ(x′), y′)) ) + (h(φ(x′), y)− h(φ(x), y)) ∣∣∣∣ (76)
≤ ∣∣∣∣maxy′ 6=y(1 + h(φ(x), y′))−maxy′ 6=y(1 + h(φ(x′), y′)) ∣∣∣∣+ |h(φ(x′), y)− h(φ(x), y)| (77) ≤ max
y′ |h(φ(x), y′)− h(φ(x′), y′)|+ |h(φ(x′), y)− h(φ(x), y)| (78) ≤W‖φ(x)− φ(x′)‖+W‖φ(x)− φ(x′)‖ (79) ≤ 2W‖φ(x)− φ(x′)‖ (80)
The above claim then yields the following theorem
Theorem 7. Suppose S is a sampled training set of m points. For any h ∈ H, let lmax(h, S) = max(x,y)∈S l(h, φ(x), y) be the maximum loss h incurs on S. Then, for all > 0 and (x, y) ∼ D:
P (l(h, φ(x), y) > lmax(k, S) + ) ≤ ( 1− pφa (
2W
) pφc ( 2W ))m . (81)
Proof. As we have shown above, for all x, x′, y:
l(h, φ(x), y)− l(h, φ(x′), y) ≤ 2W‖φ(x)− φ(x′)‖ (82)
It follows that for any (x, y), (x′, y′):
‖φ(x)− φ(x′)‖ < ∆2W y = y′
} ⇒ l(h, φ(x), y) ≤ l(h, φ(x′), y′) + ∆ ∀h ∈ H (83)
Note that the probability of sampling such an (x′, y′) is pφa(∆/2W )p φ c (∆/2W ). If (x ′, y′) is in S, then l(h, φ(x′), y′) ≤ lmax(h, S). Thus, for any (x, y) ∼ D
P (l(h, φ(x), y) ≤ lmax(h, S) + ) ≥ P ( ∃(x′, y′) ∈ S s.t ‖φ(x)− φ(x′)‖ < ∆
2W and y = y′ ) (84)
= 1− ( 1− pφc (
2W
) pφa ( 2W ))m (85)
Once again, the only difference in proofs is the use of factor 2W instead of W .

Review summaries:
This work studies the relation between properties of the feature extractor, and the downstream performance on binary classification tasks. The authors identify two key properties, namely "local alignment" and "congregation", which can be used to derive lower bound on the test accuracy and generalization bounds. The theoretical results are verified empirically on CIFAR10 and CUB200.

The paper addresses the question of what makes a representation suitable or "good" for a particular task. The submission includes three data-dependent bounds: a lower bound on the average accuracy and two upper bounds on generalization. The analysis is based on the simple and intuitive concepts of local alignment and degree of congregation of the data points within a representational space and according to a binary labeling of the points. Two experiments support the theoretical claims.

This paper proposes to study how feature representations are transferable to downstream tasks. It presents a theoretical characterization of such transfer, in terms of relatively intuitive concepts of congregation and alignment. Specifically, it presents various bounds on classifier's expected error, probability of high-error inputs, and Rademacher complexity. The paper validates these theoretical observations by experiments with transfer in visual settings, between supervised tasks, or to few-shot (+unlabeled data) transfer.