A theoretically grounded characterization of feature representations 
Authors: Bharath Hariharan
Cheng Perng Phoo
Venue: ICLR 2022 Submitted (2022)
Keywords: features
analysis
generalization
transfer
few-shot

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.

Under review as a conference paper at ICLR 2022
A THEORETICALLY GROUNDED CHARACTERIZATION OF FEATURE REPRESENTATIONS
An Anonymous authors
Paper under double-blind review
ABSTRACT
A large body of work has explored how learned feature representations can be use- ful for variety of downstream tasks. This is true even when the downstream tasks differ greatly from the actual objective used to (pre)train the feature representa- tion. This observation underlies the success of, e.g., few-shot learning, transfer learning and self-supervised learning, among others. However, very little is un- derstood about why such transfer is successful, and more importantly, how one should choose the pre-training task. As first step towards this understanding. we ask: what makes 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 perfor- mance. Finally, show that our bounds are practically useful for choosing the right pre-trained representation for a target task.
INTRODUCTION
Since the (re)-discovery of neural networks for visual recognition, plethora of work has observed that the feature representations trained on ImageNet generalize to many downstream tasks, even to new domains (Donahue et al.] [014 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. (017).
This growing field of representation learning has yielded ostensibly better and better feature rep- resentations. However, a closer look reveals many mysterious results. For example, meta-learning methods do not transfer across domains (Guo et al., (020)) and self-supervised representations strug- gle with fine-grained recognition (Wallace & Hariharan 2020). These empirical results are tremely valuable, but do not provide a deeper understanding of the corresponding phenomena. On the other side of the spectrum, theoretical work neural representations is illuminating, but often makes assumptions about models or tasks (Du et al., 20200 Arora et al., 20195). We lack a general understanding of which neural representations work well for 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 the- oretical 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 D:: (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 in- stances, 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 large dataset of realistic few-shot tasks, we use our bounds to pick the best pre- pre-trained rep- resentation 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.

---

Under review as a conference paper at ICLR 2022
Figure I: An illustration of the properties of local alignment and congregation. Feature representa- tions on the left are more congregated than those the right. The first and third feature representa- tions on the top are more aligned locally than the other two. Classical error bounds depend only on the norm of the feature vectors and so cannot distinguish between these. We show theoretically and empirically that the distinctions shown here impact the error of a downstream classifier.
RELATED WORK
Analyzing transterability: The motivations of our work lie in understanding the empirical effec-
tiveness of transferring feature representations from supervised (Donahue et al., 2014 Zhai et al.
2019 Kolesnikov et al. (020) or self-supervised (Goyal et al.) WWllace & Harhaarn 2020 Chen 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 classifier with every available pre-trained representation and pick the best per- former (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 classification task with known label space then the conditional distribution of targets given pre-training task labels is informative of transfer performance (Tran et al. 2019: Nguyen 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 pro- prietary data). This inaccessibility of pre-training data is also 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 ana- lyzing the pre-trained feature representation, which allows us to be agnostic to the actual task it was trained on. Our work most similar in setup and motivation to work on measuring the alignment between feature representations and the target labels (Huang et al. |021 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 dimen- sions mean (Agrawal et al. [014 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 al. 2014) or the architecture (Kornblith et al. (019)). 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 lcarning. This prior work of- ten 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 & Lamperi, 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 al. 2019a), the variance and separation of class-specifi mani- folds (Cohen et al., 22220), the underlying intrinsic dimensionality of the task (Lampinen & Ganguli 2018) the mutual information between representations and the inputs or labels (Shwartz-7iv &
2

---

Under review as a conference paper at ICLR 2022
Tishby 2017). The corresponding results can be used for analyzing feature representations well.
Our proposed measurements are similar, but are simpler to measure and potentially more intuitive.
PROBLEM SETUP
Suppose interested in mapping a space of inputs X' to space of targets V. There is an underlying distribution D over X' x V. We have a feature representation & : - R which might be pre-trained on another dataset task, which is inaccessible to us. We will assume that [[(())] S B.
For of exposition in the paper. we focus on the task of binary classification; the case of multi- class 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 RR + R. The predicted label will then be sign(h(((x))) where if h()(z)) ) is O, we will arbitrarily assign label of -1. The set of possible functions defines the hypothesis class for the classifier; denote this by H. For most of our analysis, we primarily care about the smoothness of the functions in H. We will assume that all functions H are Lipschitz, continuous with Lipschitz constant less than W. Thus:
h(((z)) h()(x') S Wilo(x>) <(x')l vh H We note that one such hypothesis class which is commonly used in practice the class of linear classifiers of bounded norm: W {[- w v; v; ||]] < W
(1)
Because the zero-one loss, 1" ("((((())) 3) (ssig(h(((())) * yl is difficult to analyze, we will use the following continuous upper bound which standard theoretical treatments (Mohri al. 2018)
(b(((x))).)) v) min(1, max(0, 1 - y)((())))) 2 1" (h(cbx)))
Our focus in this paper is to understand how the properties of the feature extractor & affect the loss of the classifiers ()()))) 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 small training set.
We begin by first identifying the key properties of feature representations.
4 TWO PROPERTIES OF FEATURE REPRESENTATIONS
What properties should we use to characterize feature representations? First, we should use proper- ties 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 mcasurement is to look at what the feature representation considers as similar. In particular, could look pairs of examples that embed close 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,
make the following definition
Definition 1. Suppose a > O. The local alignment of the feature space &. denoted by (ax) the probability that two data points (I, (2,)), (xl, v/) D share label given that they embed within distance of ac
(a) P(y =
[|d(x) <(x')l S a. (x. (a', ~ D)
here is 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:
3

---

Under review as a conference paper at ICLR 2022
Figure 2: Intuition behind our analysis for the lower bound on error (Theorem Left) and upper bound on generalization (Theorem 2 Right). In each case look at pairs of data points that fall within a distance a of each other (shown as red balls). The lower bound notes that examples with different labels in these balls yield high enror. The upper bound notes that outside the red balls centered on training points (large dots) generalization is not guaranteed. Also shown are the optimal (red) and obtained (black) classifiers.
Definition 2. Suppose >> O. The degree of congregation of the feature space o, denoted by p is the probability that two points v, x! sampled from embed within distance of a:
(a) P(l(((a) Φ(x¹)) S ou/ D)
(4)
We have hyperparameter here too.
We now use these notions of local alignment and congregation to analyze the downstream error of classifiers.
5 WHAT IS THE BEST ACCURACY WE CAN ACHIEVE?
Given a feature space o, what is the best accuracy we can hope to get using scoring functions from H? Recall that these scoring functions are all W -Lpiscchitz. Our key intuition is that this Lipschitz continuity will force any scoring function in H to produce very similar scores for nearby data points. If these have different labels, then the classifier will be forced to err on least one of them. To formalize this intuition, we begin with the following claim
Claim 1. Consider two data points (x, and 3/). 1f]l((x) o(x')l to and y + s/. then:
[(h(olz)), v) ((h(o(z))), 8/) 2
(5)
Proof. Observe first that due to Lipschitz continuity of h: (a((())) - h(((x²))) S Wll((z) - a(z')l S
(6)
+ -h(((z))) > (()())) -1
(7)
Now, since * y/, it follows that y/ -y. Without loss of generality, let us assume that = 1. Denote ((h(ó(x)). y) by and ((h(o(=')).'/ y²) by We will prove this claim by contradiction. Suppase, if possible, that the clam is not true, and a + b < 1. Since the loss is always non-negative, follows that a < and Thus:
a = max(0,1111111 1 yh()(x)))
(8)
> 1 - yh(((x)) = h((()))
(9)
h(o())) 2 -aa
(10)
Taking the other data point:
b = max (0,11)/(((((())))
(11)
> =1 h(+(((=)))
(12)
> h(6(=)) -1 M((=))
(:: equation 7
(13)
> 1 a a
(14)
#a+b21 thus yielding contradiction.
(15)
4

---

Under review as a conference paper at ICLR 2022
Thus, if two data points close, at least one of them must be incorrectly classified. We can thus bound the error the best possible classifier from below by estimating how often this happens:
Theorem 1. Let I be the loss function defined above, and H be hypothesis class of Lipsehitz finctiins with Lipschitz constant at most W. Let be distribution over X x Y, and pa and p defined as above. Then
inf NEw
1
Pe
Pe
(16)
W
W
Proof. We observe that if (a:, y), (1', ~ D, then the probability that [| - <(x')) < and
y # y' is given by p = (1 (1 Wp Then, for all h E H.
Exy (M(((())) v)1 = - (ew.leeews--lll((((cc))) v) + ((((((())) (),0))) p 2
(17)
E(((((())))))) ((L(6(2)))))) [lá(x) <(x')l W
1
and y # y/
(18)
(19)
(20)
where the second step follows because the loss is non-negative, so only focusing on the case when and x' are close but have different labels yields lower bound. This is true for all h H. so it is true for the infimum as well.
How WELL WILL CLASSIFIERS GENERALIZE?
There may 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 un- derlying feature space beyond the maximum norm 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 more traditional Rademacher complexity based analysis to bound the excess risk (i.c., the difference between the test loss and training loss).
6.1 BOUNDING THE PROBABILITY OF HIGH-LOSS DATA POINTS
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 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 worse than the loss the worst performing training example.
Theorem 2. Let Hop = f== M((())); H). Suppose is sampled training of m points. For any z E Ho, let (maa(2,)) max(n.y)e ((((x) y) be the maximum loss incurs on S. Then, for all e > and (I, v) D:
P (((((xx)))) > (2a 11-p2 (1-
PE
(21)
W
W
5

---

Under review as a conference paper at ICLR 2022
Proof. It can be shown that for any y, [2((2),) y) - 1(2(x'), 3) S 12(x) 2(x')1 (see Appendix).
Further, vh E H. is Lipsschitz. So we have, for all x. yy:
1(=(x),y) (==(r'),)) S (x(x) - =(x') S Wllo(z) 6(x'))1 follows that for any (z, 9) 3/)
(22)
( ((x²) || < w } = ((<((())))) E Hs
(23)
y y y
Note that the probability of sampling such an (x'.y)) is A//))) If (2', is in S
then ((=(x'))) s²) S mma (2, 5). Thus, for any (z. v)
A W
P (1(2(2),,) y) & Ima ( +c) P 3(x' v/) E 1l(2) - (('')l
and y = y
(24)
(1
é W
Pe
Pa
(25)
W
6.2 BOUNDING THE EXCESS RISK
We can also perform 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 - 6, the following holds for all h H:
log
R(h) - R)h, S Rm (H) +
V
(26)
2m
where R(h) is the test loss (or expected risk), R(,, S) is the training loss (or empirical risk), and Rm (H) is the Rademacher complexity of H.
Thus, to bound the generalization error, suffices to bound the Rademacher complexity of H, which
is defined as Rmm (H) = Es-D= SUPPRR m Σ ozh();;- Here ag are Rademacher random variables (i.e., a; E 1,, Eo, = 0). The Rademacher complexity is 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 particular a, (a) is large. then any two datasets (c.g., 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 fol- lowing bound on the Rademacher complexity of the set of linear classifiers composed with d:
Theorem 3. Let W. = {z = + h(o(z)); E W). Let d be defined as above. Then the Rademacher complexity of We is bounded above by:
w (ay pE + 2B (1 - p (a)) + 2( pa (a=)²
Rm <
(27)
2/m
Proof sketch: (Full proof presented in Appendix). For any 2; E S, there is probability (a)/2 that the next point 2441 (a) within distance a in feature space, and (b) multiplied with Rademacher variable of the opposite sign. Such pairs will effectively cancel out each other except for small quantity of a, resulting in the first term. The second term obtained from all the rest of the data points in S, which have to be analyzed in the usual way.
7 IMPLICATIONS

---

Under review as a conference paper at ICLR 2022
Both the lower and upper bounds (in particu- lar theorem 2) suggest the need for a high Par namely, a feature space where nearby examples have similar labels. However, the two bounds differ in the need for congregation.
Random
14
14
SimCLR
ImageNet
1.0
14
Pala)
The lower bound suggests that we need less congregated feature space, i.e., space where examples are in general far apart. This matches the training objective of self-supervised and contrastive learning techniques, which primar- ily 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 representa- tions (i.e, low P.).
0.6
0.5
0.4
0.2
02
α
Figure 3: Pa (left axis, solid line) and (right axis, dotted line) function of for three fea- ture representations on CIFAR-10
However, the upper bound suggests that good generalization from small datasets actually re- quires a highly congregated feature space. As such, these highly spread out feature representations actually yield large generalization errors in few-shot settings, demonstrated in Table [ even if they yield much lower errors with large training sets. Thus, finding a good representation for task nuanced decision, requiring one balance between these conflicting requirements.
Theorem 2 vs 3 The two generalization bounds both demand high congregation, but differ in whether they involve aligmment. Interestingly, the Rademacher complexity-base bound does not use Pa- Below, we will see that for this reason, this bound is less correlated with the downstream performance.
EMPIRICAL ANALYSIS
Above we have shown that p and p yield bounds classifier perfor- mance. But are they useful enough in practice to make decisions? We first look to see whether they are corre- lated with actual loss values, and then present potential applications.
Representation
Pa
Pe
Test loss (large dataset)
Excess risk (5-shot)
Random SimCLR ImageNet
0.51
0.88
0.29
0.26
0.7
0.1
0.18
0.24
1.0
0.0
0.04
0.65
8.1 CORRELATIONS
Table 1: Three representations with different alignment and congregation, and the corresponding test loss (with large training sets) as well as excess risk with tiny training sets.
WITH CLASSIFIER ACCURACY
We used CIFAR- Krriihesy 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, sampled small 20-example training set to train linear classifier, and then evaluated the classifier on a large validation 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 varying granularity on ImageNerRussakovsky et al.) 2015), iNaturalist Van Horn al.) 2018), CIFAR- 100 (see Appendix). For each task and for every representation, we computed our bounds using the labeled validation set to get p and pe. and using the empirically obtained classifier norm W (a more practical approach is described in the next section).
Results: For each task, computed the correlations between proposed bounds and the responding 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

---

Under review as a conference paper at ICLR 2022
Lower bound training loss
Theorem vs excess risk
12
10
Number of tasks
of
Correlation
Correlation
Theorem vs excess risk
Classical bound vs excess risk
Number 100
Number of tacks
0.0
0.2
0.4
0.6
0.8
1.0
6.0
0.2
0,4
0.6
0.8
1.0
Correlation
Correlation
Figure 4: Correlations of our proposed bounds with actual margin loss. Clockwise from top left: Lower bound vs train loss, Theorem 2 vs excess risk, the classical textbook bound vs excess risk, and Theorem (right) vs actual excess risk.
CIFAR-10
% Error relative to oracie
relaove
20
Random
Hscore
TransRate
Ours
Random
Hscore
Transitate
Ours
Figure 5: Our characterization of the feature space allows choose the best pre-trained repre- sentation for given few-shot task. Lower numbers are better. Left: results on CUB-200. Right: results on CIFAR-10.
well correlated with the training loss (average Spearman's p 0.93), but less so with the test loss (av- erage Spearman"s, p 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 proposed upper bound in Theorem 2 (average Spear- man's ' p 0.80), which much better than the correlation obtained with the classical bound (average 0.50). Theorem yields a worse correlation that Theorem 2 perhaps because it doesn't take into account the alignment. Since Theorem yields a stronger correlation, we use this upper bound in conjunction with the lower bound for more practical experiment model selection below.
8

---

Under review as a conference paper at ICLR 2022
8.2 APPLICATIONS TO FEW-SHOT TRANSFER
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 al. (2020) accessible datasets Cui et al. (2018). that ini- tial 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 iet al.] (2020), and the wide variety of visual domains Wallace & Hariharan (2020), these assumptions 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 Tran- sRate Huang et al. (202T). Both approaches are based information- theerrtte arguments justifying the use of intra- and inter-class covariance matrices, which are global statistics of the feature repre- sentation, in contrast to our more local measurements. In addition, we also include baseline that chooses a representation at random.
Experimental setup: We run few-shot experiments on two datasets: CIFAR-10 and CUB- 200(Welinder et al. 2010). The pre-trained representations were obtained by training on iNaturalist, ImageNet and CIFAR-I0 (only for CUB-200) with various loss functions. 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 a to be large enough that for at least one class, every pair of labeled examples is at most a 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 habel-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.
We show results in figure 5 Interestingly, TransRate and H-score seem to have oppo- site 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 bet- ter choices than both baselines on both benchmark datasets thus suggesting the usefulness of our characterization for practical problems.
Results:
LIMITATIONS, CONCLUSION AND FUTURE WORK
We have presented here a characterization of feature representations that is predictive of how well downstream classifiers will do. Our analysis limited to classification, though the results may be adapted potentially to other classification-lis tasks (c.g., object detection). We also assume that the downstream classifier 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 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 com- munity who may not have the data or resources to train big networks from scratch. However, we note that our work focuses only the average accuracy one obtain from these representations in a downstream task; we do not delve into the biases that these representations might perpetu- ate Steed& & Caliskan (2021), or privacy consent issues in the original datasets used to train these

---

Under review as a conference paper at ICLR 2022
representations Birhane & Prabhu (2021). We suggest that when choosing pre-trained represen- tation, practitioners should consider not just our characterization downstream accuracy, but also broader characterization in terms of the many ethical implications of choosing representation pre-trained on questionably collected or opaque datasets.
REFERENCES
Alessandro Achille, Michael Lam, Rahul Tewari, Avinash Ravichandran, Subhransu Maji, Char- less C Fowlkes, Stefano Soatto, and Pietro Perona. Task2vec: Task embedding for meta-learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 6430, 2019.
Pulkit Agrawal, Ross Girshick, and Jitendra Malik. Analyzing the performance of multilayer neu- ral networks for object recognition. In European conference on computer vision, pp. 329-344. Springer, 2014.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference Machine Learning, pp- 322-332. PMLR, 2019a.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A theoretical analysis of contrastive unsupervised representation learning. In 36th International Conference on Machine Learning, ICML 2019, pp. 9904-9923. International Machine Learning Society (IMLS), 2019b.
Mathieu Aubry and Bryan C Russell. Understanding deep features with compuler-generated im- agery. In Proceedings of the IEEE International Conference on Computer Vision, pp. 2875-2883, 2015.
Yajie Bao, Yang Li, Shao-Lun Huang, Lin Zhang, Lizhong Zheng, Amir Zamir, and Leonidas Guibas. An information-theoree approach to transferability in task transfer learning. In 2019 IEEE International Conference on Image Processing (ICIP), pp. 2309-2313, IEEE, 2019.
Jonathan Baxter. A model of inductive bias learning. Journal of artificial intelligence research, 12: 149-198, 2000.
Abeba Birhane and Vinay Uday Prabhu. Large image datasets: A pyrrhic win for computer vision? In 202/ IEEE Winter Conference Applications of Computer Vision (WACV), pp. 1536-1546. IEEE, 2021.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. International conference on machine learning, pp. 1597-1607. PMLR, 2020.
Uri Cohen, Yeon Chung, Daniel Lee, and Haim Sompolinsky. Separability and geometry of object manifolds in deep neural networks. Nature communications, 11(1):1-13, 2020.
Yin Cui, Yang Song, Chen Sun, Andrew Howard, and Serge Belongie. Large scale fne-grained categorization and domain-specific transfer learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 41 4109-4118. 2018.
Jeff Donahue, Yangqing Jia, Oriol Vinyals, Judy Hoffman, Ning Zhang, Eric Tzeng, and Trevor Darrell. Decaf: A deep convolutional activation feature for generic visual recognition. In Inter- national conference on machine learning, pp. 647-655. PMLR, 2014.
Simon Shaolei Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. In International Conference on Learning Representations, 2020.
Kshitij Dwivedi and Gemma Roig. Representation similarity analysis for efficient task taxonomy & transfer learning. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12387-12396, 2019.
10

---

Under review as a conference paper at ICLR 2022
Kshitij Dwivedi, Jiahui Huang, Radoslaw Martin Cichy, and Gemma Roig. Duality diagram sim- ilarity: a generic framework for initialization selection in task transfer learning. In European Conference Computer Vision, pp. 497-513. Springer, 2020.
Tomer Galanti, Lior Wolf, and Tamir Hazan. theoretical framework for deep transfer learning- Information and Inference: A Journal of the IMA, 5(2): 2016.
Yansong Gao and Pratik Chaudhari. An information-geomerii distance on the space of tasks. In International Conference on Machine Learning, pp. 3553-3563, PMLR, 2021.
Priya Goyal, Dhruv Mahajan, Abhinav Gupta, and Ishan Misra. Scaling and benchmarking self- supervised visual representation learning. In 2019 IEEE/CVF International Conference on Com- puler Vision (ICCV), pp. 6390-6399, IEEE
Yunhui Guo, Noel C Codella, Leonid Karlinsky, James Codella, John R Smith, Kate Saenko, Ta- jana Rosing, and Rogerio Feris. A broader study of cross-domain few-shot learning. In European Conference on Computer Vision, pp. 124-141. Springer, 2020.
Long-Kai Kai Huang, Ying Wei, Yu Rong, Qiang Yang. and Junzhou Huang. Frustratingly easy trans- ferability estimation. arXiv preprint arXiv:2106.099322 2021.
Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby. Big transfer (bit): General visual representation learning. In Computer Vision- ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part V 16, pp. 491-507. Springer, 2020.
Simon Komblith, Jonathon Shlens, and Quoc V Le. Do better imagenet models transfer better? In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp- 2661-2671, 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Andrew K Lampinen and Surya Ganguli. An analytic theory of generalization dynamics and transfer learning in deep linear networks. In International Conference on Learning Representations, 2018.
Andreas Maurer. Transfer bounds for linear feature learning. Machine learning, 75(3):327-350, 2009.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT' press, 2018.
Cuong Nguyen, Tal Hassner, Matthias Seeger, and Cedric Archambeau. Leep: A new measure to evaluate transferability of learned representations. In International Conference on Machine Learning, pp. 7294-7305. PMLR, 2020.
Anastasia Pentina and Christoph Lampert. A pac-bayesian bound for lifelong learning. In Interna- tional Conference on Machine Learning, pp. 991-999. PMLR, 2014.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), (15(3):211 1--2222 2015. doi: 10.10077/11123-01-0000
Ravid Shwartz-Ziv Ziv and Naftali Tishby. Opening the black box of deep neural networks via informa- tion. arXiv preprint arXiv: 7703.00810 000800, 2017.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In Proceedings of the 31st International Conference Neural Information Processing Systems, pp- 4080-4090, 2017.
Jie Song, Yixin Chen, Jingwen Ye, Xinchao Wang, Chengchao Shen, Feng Mao, and Mingli Song. Depara: Deep attribution graph for deep knowledge transferability. In Proceedings of the IEFE/CVF Conference Computer Vision and Pattern Recognition, pp. p 3922-3930, 2020.
11

---

Under review as a conference paper at ICLR 2022
Ryan Steed and Aylin Caliskan. Image representations learned with unsupervised pre-training con- tain human- like biases. In Proceedings of the 2021 ACM Conference on Fairess, Accountability, and Transparency, pp. 701-713, 2021.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 1312.6799 2013.
Anh T Tran, Cuong V Nguyen, and Tal Hassner. Transferability and hardness of supervised classifi- cation tasks. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1395-1405, 2019.
Grant Van Horn, Oisin Mac Aodha, Yang Song, Yin Cui, Chen Sun, Alex Shepard, Hartwig Adam, Pietro Perona, and Serge Belongie. The inaturalist species classification and detection dataset. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8769-8778 2018.
Bram Wallace and Bharath Hariharan. Extending and analyzing self-supervise learning across domains. In ECCV, 2020.
Bram Wallace, Ziyang Wu, and Bharath Hariharan. Can we characterize tasks without labels fea- tures? In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1245-1254, 2021.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere. In International Conference Machine Learning, pp. PMLR, 2020.
P. Welinder, S. Branson, T. Mita, C. Wah, F. Schroff, S. Belongie, and P. Perona. Caltech-UCSD Birds 200. Technical Report ENS--R-2010-000 California Institute of Technology, 2010.
Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks? arXiv preprint 1rXiv:/411.1733 2014.
Kaichao You, Yong Liu, Jianmin Wang, and Mingsheng Long. Logme: Practical assessment of
pre-trained models for transfer learning. In International Conference on Machine Learning, pp- 12133-12143, PMLR, 2021.
Amir R Zamir, Alexander Sax, William Shen, Leonidas J Guibas, Jitendra Malik, and Silvio Savarese. Taskonomy: Disentangling task transfer learning. In Proceedings of the IEEE con- ference on computer vision and pattern recognition, pp. 3712-3722, 2018.
Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In European conference on computer vision, pp. 818-833 Springer, 2014.
Xiaohua Zhai, Joan Puigcerver, Alexander Kolesnikov, Pierre Ruyssen, Carlos Riquelme, Mario Lucic, Josip Djolonga, Andre Susano Pinto, Maxim Neumann, Alexey Dosovitskiy, et al. The visual task adaptation benchmark. 2019.
A APPENDIX
A.1 PROOFS
Theorem 4, Let f(x) = min(1, max(0, x)). Then f(x) f(x)) S lx x'|.
Proof. We do a case-by-case analysis.
1. x 2 0, < 1. In this case, f(x') 2 x' and f(x) < x. So f()) x-1' s x
2. x < 0. In this case f(x) 0. Since f(x') 0, it follows that f(z) f(x)-f(z') < <0<<--11
3. x > 1. In this case f(x') 1. Since ((x it follows that f(x) [(x)) < <<x-11
12

---

Under review as a conference paper at ICLR 2022
Claim 2. (Used in proof of Theorem 2 Let ((2,)) min(1, max(0, - zy)). Then ((,,)) y)
1() S 1z z/1.
Proof. (z, y) ((1-y2), where f is defined as above. The claim follows directly from Theorem
Theorem 5. Let We fa h((())); W}. Let p be defined as above. Then the Rademacher complexity of We is bounded above by:
w ( 2B / (1-p2 (a)) + +2(1111111111111 på (a))²
Rm (Wa)
(28)
2/m
Proof. First note that:
(Wo) = Es,o sup zeWs m
(29)
i=1
1
m
EsSa
sup
a. (bx;;)
(30)
m
1
Es. sup
apph((>a)
(31)
m NEW
W
<
Es,
(: Ww S W)
(32)
(33)
Thus need bound 1 Σ 0x((1))
Consider any set S of m points sampled from D. Let ı be the mapping i + (i + 1) mod m, and define of m(() and x (i). Then, for any z Hs have that Σ (((((;))
Σm d(((x() = 5 (o:ú(()) + d(((x)))
Note that 11 1/ and a; IL of Define I[(a; of) and (ll((z)) <(x!)) < a)). Then Bs = as = (a)) which we will denote as Po 2
Therefore:
m
Es. ||
(1)(1))
(34)
Es.a
(αp((())) + +
(35)
Es.al
(aro;(((2;)) - x(x()) Σ +(o()()))
(36)
2
E=1
< Es,ol
(o((() ((x)))
2
iml
m
+
Es.o
a,))())))
2
1
+
Es.al a,)()(2))
(37)
2
i=1
13

---

Under review as a conference paper at ICLR 2022
Observe that a; TT og, and a, TT o.-- Using this, the second and third terms are similar. The second term yields:
E 5
2,
(38)
2
1
S,
((0,0,0,((x)))(())
(39)
2
1
Es ((,00(
(40)
2
We note that if + j and i & T(i) and + mii) then a,o, 1L ayoz. Thus, looking at the expression under the square root:
Bs,ddd,,010od(aa)) ((a,)
(41)
S, oj 0 (1::)11))
(42)
Σ
[so0dd;or,,((a oa(;)
(43)
f (j)om
<
Es of
(, Ea = Eā,- = 1 pa)
(44)
B²
Σ
Eg
(45)
()i==((Jan==((i)
<B2m(1 Pa)) + B²
Σ
Bs
(: Ro; 11
(46)
b.j: (()oo==(()))))
<B²m(1 Pa)) + Bm2m1 Pa)²
(47)
Thus:
m
Es Es.ol a,,,((x;))
(48)
2
B
/m Pa) 2m(1 Pa)
(49)
2
Through similar reasoning, the first term yields:
m
Es.o
(o(:)) <(x))1l
(50)
2
1 m
(001((0)))) - -(x))\
(51)
2
m
<
Es az
(52)
21
i=1
1
V a2
(:: C:EEa = -Ea; Pa)
(53)
2
14

---

Under review as a conference paper at ICLR 2022
6.7
Train l055
0.4
Actaal
23-
6.-
12.
0.0
2.1
5.02
0.55
Lower bound loss
6.30
0.55
6.20
0.25
5.2
New bound on bad performnnc
6.
16
0.5
0.-
Test loss train loss
Test loss train loss
5.4
0.4
6.1
01
New bound on excess risk (Thm 3)
Classical bound on excess risk
Figure 6: Scatter plots showing the correlations described in the main paper. For these scatter plots, data across all 45 tasks was pooled together. Clockwise from top left: Lower bound vs training loss. bound from theorem 2 vs excess risk, classical Rademacher-bau bound vs excess risk, and Theorem 3 vs excess risk.
Putting these expressions back in equation 37 we get: W
Rmn (Ha) v (Vmpan" BV B/m(1 m(1 Pa) 2m(1 pa,2 B Bmm11 Pa)) 2m(11 pa)3)
2m
(54)
W (avPo + 2B m(1 2mLLl Pa) + 2m Pa.)
(55)
m/m
A.2 SCATTER PLOTS
See Figure
A.3 REPRESENTATIONS USED EXPERIMENTS
In general it is difficult to do statistically rigorous experiments for choosing representations since publicly available pre- pre-tedined representations vary wildly architecture and dimensionality. How- ever, we want to ensure that the characterization we produce is nuanced enough to distinguish be- tween fairly similar representations that are based on the same backbone architecture and the same feature dimensionality. Therefore 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 use of coarsely labeled data (see supplementary). For completeness, we present a brief overview of these representations here.
trained in the context of unrelated exploration on the
All representations were trained on a combination of coarsely labeled dataset C and a finely labeled dataset F. C' may have classes that are not present in F. The representations used are:
15

---

Under review as a conference paper at ICLR 2022
1. A representation trained with simple supervised learning F alone.
2. A representation trained with simple supervised learning on C' alone.
3. A representation trained on U with two classifier heads, one for coarse categorization and another for fine-grained categorization
4. A representation trained on CUF with fine-grainede soft pseudo-labels for C' obtained using a classifier trained on F
5. A representation trained on CUF with fine- tine-grained soft pseudo-labels for C obtttined using a classifier trained on F, and with the pseudo-labels filtered to be consistent with the coarse label,
6. A representation trained C'U 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.
A.4 BOUNDS FOR MULTICLASS CLASSIFICATION
A.4.1 PROBLEM SETUP
Suppose, as before, we are interested in mapping a space of inputs X' to a space of targets V. There an underlying distribution D over X y. We have a feature representation X - R which might be pre-trained on another dataset or task, which is inaccessible to us. We will assume that [[o())] s B.
For multiclass classification, our classifier will use a scoring function that scores how well a feature vector matches a class label, h R x R. The predicted label will then be arg max, h(((())) y). where ties are broken arbitrarily. The set of possible functions h defines the hypothesis class for the classifier: denote this by H. For most of our analysis, we primarily care about the smoothness of the functions in H. We will assume that all functions in H are Lipschitz continuous in the first argument with Lipschitz constant less than W. Thus:
h(o(z), h()(2'))))))))))))))))())))))))) v) S W(lo(z) - <(x')ll Yh E H. E E
(56)
We note that one such hypothesis class which is commonly used in practice the class of linear classifiers of bounded norm: W = [v.y y + [/]v://w..
WVy E }
For a data point æ with label y, the zero-one loss incurred by scoring function is 1" (h, dxx),)
[ly A arg maxy h()()), s/)]. We will use the following continuous margin-based upper bound:
1(h, ((x), y) min(1, m0x(0, max(1 + (((()))))))))))))))))))))))))()) - (((((()) 2 1" (h, ,(x),9)
(57)
v'
We can now prove equivalent lower and upper bounds as below.
A.4.2 LOWER BOUND
Claim 3. Consider two data points (a, u) and (x', 1f1((()) 6(x')l < zw and + v/. then:
I(h(o(z)), v) ((h(0(2))).''
(58)
Proof. Observe first that due Lipschitz continutty of h:
1 Vy
[k(((z).)) - h((((1)))))))))))))))(())))))h) v) & - = h((((z') y) [)()(z),)) 1 ((((z),)) }
- 6(2))1 5
(59)
(60)
This in turn implies that for any pair of classes y1 and y/.
1 h()()") (1(()))))) vi) h(((x') v2) h()()) vn) (h(((x),u2) + } M((()), h(0()), yz)
(61)
16

---

Under review as a conference paper at ICLR 2022
Now, denote 1(h, ((2), y) by and ((h, ((2"),)) by b. We will prove this claim by contradiction. Suppose, if possible, that the clam is not true, and a + < 1. Since the loss is always non-negative, it follows that a < 1 and b 1. Thus:
= (0, max + (((()),)))))))))) - -0(--((())) k()(z).)))
(62)
8"*v
2 max + ((((+((()))))))))) M((x))
(63)
2 1+ h((()),))) ((6()),))))
(64)
= =((6(r),9) -()()))) 21-a
(65)
Taking the other data point:
max(0, max (1 + h(o()))))))) (((('),,))
(66)
4"*""
max (1 h(o(x)),)))) -
(67)
2 (1 +
(68)
2 1+ -M(o)
(: equation 61
(69)
= h(6()).)) (((
2 al: equation
65
(70)
>a+b21 1
(71)
thus yielding a contradiction.
This claim directly leads the following lower bound for the multiclass case, with the exact same proof:
Theorem 6. Let I be the loss function defined above, and H be hypothesis class of Lipschitz functions with Lipschitz constant at most W. Let DD be distribution over X' x Y, and p and pe: defined as above. Then
1 {(1
1 2W
))
1
inf E Ee.g- v\ 2
1 pa
P
(72)
bEH
2W
Note that the only difference between the bounds for the binary and the multiclass case is the factor 2W in lieu of W.
A.4.3 UPPER BOUND
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 is W -ipschiitz described above,
1(h, ()x).()))))))))))))))))) u) - 1(h, o(x²). 2W (l)))))) ((x')l)
(73)
Proof. We note that 1(h, ((x), y) f (max, (maxx'=((11) ( h()()),))), where f is defined in Theorem 4 Theorem directly yields:
1(h, ((x), 3) - ((h, 6(x)),)
(74)
+ -
max(1 + h((())) v/)) - M((()).)) -
(75)
V'zy
max(1+ + h((())))))))))))))(()))))))))) v/)) max(1 + +((l+')))))))) + (h(o(='), -
(76)
v'
max(1 + (( max(1 ((0l))(((()))))))) + (M((('))))) (((()))
(77)
1'Fy
v'Fy
< max (b(((2),)/) -
(1(((=))))))))) x))())))))
(78)
(ll((z) -(x')]] + -7())())6(2'1)
(79)
2W]ld(=) - -(x'))
(80)
17

---

Under review as a conference paper at ICLR 2022
The above claim then yields the following theorem
Theorem 7. Suppose S is a sampled training set of m points. For any h E H. let tma (ma S) (x,))) (h, ((x), v) be the maximum loss h incurs on S. Then, for all e >> and (I, y) ~ D:
P (( ((x).)) v) Ima S) ((111111) (1-pi) p.
m
Pc
(81)
2W
2W
Proof. As have shown above, for all x,, yy: 1(,, ((x),( v) 1(h, 6(x)).)) s 2w]lo(x) <(x')l
(82)
follows that for any (sr, v). (x',y/)
[Ø((z) 6(z') y y=
} } 1(h, ((x) S ((1))(()))))))
2W
4h E H
(83)
Note that the probability of sampling such an (a', 3/ is 2/ /2). If (z',3') is in S, then 1(h, ((x)),))) < Iaxx (h, (h,S). S). Thus, for any (z. y) D
P (1(h, ((x),8) S Iman (), +c) 2 P
3( v/ E S s.t [1(()) - ه(>')1 < 2W
and = y
(84)
= - (1
Pe ④
E
(85)
2W
2W
Once again, the only difference in proof' is the use of factor 2W instead of W.
18


Reviews:
[{"review_id": "pPhhxfrfP-9", "reviewer": "Reviewer_PXiU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Defn 1: This should be defined more carefully, with (x,y)(x',y') ~ D. Also, not\ne that this quantity could be defined conditional on x.\n\nDefn 2: This should be defined more carefully, with x, x' ~ D.  Figure 1 contrasts lower (left 2 plots) and higher (right 2 plots) degree of concentration. However, as defined, p_c^{\\phi}(\\alpha) would depend on the scaling of the feature space. Although at the start of sec 3 we are told ||phi(x)|| \\le B, this is never used below, so in fact this definition just serves to set the scale of the\n feature space. For example, it is easy to see that for a Gaussian p(x) in 1-d,\n this quantity will depend on the standard deviation of the distribution (and it is easy to extend the analysis to a multivariate Gaussian.) I suspect that the notion that is wanted here the entropy of p(x) relative to a Gaussian with the same mean and covariance, i.e. the negentropy https://en.wikipedia.org/wiki/N\negentropy , as the Gaussian has maximum entropy for a given mean and covariance\n.\n\nNotice also that a Lipshitz constraint only makes sense relative to the scale of the feature space. If we double its scale, then we need to half the Lipshitz \nconstant to retain the same semantics.\n\nComment: I believe that the intuition behind Defn 1 is relevant to the issue of\n \"what makes a feature representation good for a target task?\", but am rather unconvinced by the subsequent analyses, for reasons explained below.\n\n\nClaim 1: The derivation of eq 7 from eq 6 is incorrect -- the inequality in eq \n6 could also imply h(phi(x)) \\le 1 + h(phi(x')) .  However I believe the claim in eq 5 is correct. Consider the functions \\ell(h,+1) and \\ell(h,-1) as a function of h. Eq 6 says that |h(phi(x) - h(phi(x')| \\le 1, so we can \"slide\" one of these functions in h by (-1,1) relative to the other. The result is then intuitive.\n\nHowever, I doubt that Claim 1 is of great practical use. The loss function (eq 2) is introduced because \"the zero-one loss ... is difficult to analyze\". However, Claim 1 depends critically on the \"margin\" for l(h,\\pm 1) extending to h=\\pm 1, and indeed the Lipshitz condition is specifically designed to exploit this margin to obtain eq 5. Thus I don't believe that this property is relevant to the zero-one loss we actually care about.\n\nTheorem 1:\n\nWritten out more carefully, the required statement is Pr( ||phi(x) - phi(x')|| < 1/W AND y \\neq y') = \nPr( ||phi(x) - phi(x')|| < 1/W) \\times Pr( y \\neq y') | ||phi(x) - phi(x')|| < 1/W) .\n\nWe start my making the above statements *conditional on x* as mentioned for Defns 1 and 2 above, giving Pr( ||phi(x) - phi(x')|| < 1/W AND y \\neq y' | x) = p^{phi}_c(alpha;x) \\times (1 - p^{phi}_a(alpha;x)) , where the notation ;x indicates dependence on a particular x.\n\nWe can now try to average the expression p^{phi}_c(alpha;x) \\times (1 - p^{phi}_a(alpha;x)) wrt D ~ x but an issue arises with the product term E_x [p^{phi}_c(alpha;x) p^{phi}_a(alpha;x)] which cannot be reduced to the product of the individual expectations.\n\nHence I believe there is a \"bug\" in this derivation for Theorem 1 as stated.\n\nAnother issue is that Theorem 1 depends only on the losses obtained when ||phi(x) - phi(x')|| < 1/W AND y \\neq y', so other losses will be sustained for situations where this condition does not apply, so the bound may be very loose. Also as noted above it depends critically on the loss function used in eq 2, and so may have little relevance to the zero-one loss of interest.\n\nExperiment 7.1: I am unclear if the loss you are reporting on the y-axis is the loss as per eq 2, or 0/1 loss -- please clarify. Also you don't state the alpha used (or how it was chosen), or the size of the training and test sets -- please expand (remember -- reproducible science!).\n\nI realize that this is mainly a theory paper, but I believe the analysis of the experiments can be much improved. For a start you are only carrying out experiments on one dataset -- while for a more experimental paper we would probably look for say 10 datasets.\n\nFor the CIFAR-10 data, for each of the 45 tasks we have 18 different representations. For EACH of the 45x10 trials, one can compare the training and test losses for each of the 18 representations against the bounds. Strong evidence for the efficacy of the bound would be that the ordering of the observed losses would correlate well with the ordering of the bounds, over most of the 45x10 replications. So for example you could compute your Spearman's rho on the 18 datapoints, and make a histogram of the values obtained over the 450 expts.  As it is, such a fine-grained comparison is \"washed out\" in the plots in Fig 3.\n\nThe claim that a rho of 0.61 is much better than 0.56 is, I'm sorry to say, pretty silly -- just look how similar the plots in Fig 5 are.\n\nSec 7.2 considers a few-shot task -- here for model selection the new bounds are shown to give better performance than the H-score and TransRate. It is notable that these last two methods can perform worse than the Random baseline.\n\nFurther comments: It is worth noting that the \"purity\" of the classes in a given ball of radius alpha around phi(x) (as in Defn 1) is something that also arises in the \"RadiusNeighborsClassifier\" version of k-nearest neighbors, see e.g.  https://scikit-learn.org/stable/modules/neighbors.html#nearest-neighbors-classification -- for this paper the radius is given by alpha.\n\n\nSummary: While the intuition behind Definition 1 makes quite a lot of sense, there seem to be some errors in the derivation of Theorem 1. Also, importantly, it is not so clear that bounds on the loss from eq 2 will be well correlated with the 0/1 loss. (This could be investigated experimentally in sec 7.) The experiments could be carried out more thoroughly (as described above) to gain a better understanding of what is going on. Overall, my judgment is that this paper is not of ICLR standard.\n\n** Other points\n\nEq 18: Is the 1/2W in eq (18) a typo for 1/W?\n\nEq 24: enhance readability by using larger brackets the P() statement on the LHS, as per the RHS.\n\np 7 para 2, defn of Rademacher complexity should contain \\sum_i \\sigma_i h(x_i) not \\sum_i h(x_i)\n\n== post rebuttal ===\n\nI have already made comments on revised manuscript  (on 27 Nov) and the authors have responded to these.\n\nPros:\n\n* the idea of relating performance/generalization to p_a and p_c seems useful.\n\n* I like the new Fig 3 (as suggested by some of the reviewers and now implemented.)\n\nCons:\n\n* As I've made clear before, I believe Thm 1 is unlikely to be of much import, as it makes use of the specifics of the \"margin\" of the\n  loss in eq 2. I'd like to see more focus on 0/1 loss in the expts,  rather than the margin loss. (I note 0/1 loss results are promised\n  for the camera ready version.)\n\n* As I understand it, Thms 2 and 3 are not particularly novel (my understanding here is from other reviewers, I am not a learning theory\nexpert.)\n\n* As pointed out by many reviewers, there does not seem to be a good  justification for the use of 100*lower bound + upper bound as a\n  basis for model selection.\n\nI am sticking with my updated score of 6.\n\n\n  \n", "summary_of_the_paper": "The paper presents two properties, \"local alignment\" (eq 3) and \"degree of congregation\" (eq 4) which are claimed to be good predictors of downstream (classification) task performance. These properties are used to derive bounds on the error of downstream classifiers (under a number of assumptions, including a linea\nr classifier with Lipshitz constraints), and are investigated empirically for pairwise classification tasks derived from the CIFAR-10 dataset, and for model selection on a few-shot task.", "summary_of_the_review": "While the intuition behind Definition 1 makes quite a lot of sense, there seem to be some errors in the derivation of Theorem 1. Also, importantly, it is not so clear that bounds on the loss from eq 2 will be well correlated with the 0/1 loss. (This could be investigated experimentally in sec 7.) The experiments could be carried out more thoroughly (as described above) to gain a better understanding of what is going on. Overall, my judgment is that this paper is not of ICLR standard.\n\n==updated===\nsee post-rebuttal summary.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "foBu6yq2XX", "reviewer": "Reviewer_tEiy", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is clearly written, and the bounds are fairly intuitive and well presented. However, I think that the paper would be improved with better experimental evaluation, and more discussion of the existing literature. \n\nExperimental evaluation\n-------------------------\n\n* The authors restrict their analyses to convenient representations they have from other work. While I share the author's desire for statistically rigorous experiments, the paper would be made much stronger if the authors demonstrated the validity of their approach with some existing representations, especially trained in different paradigms e.g. unsupervised. Even if the authors can't find multiple trained versions of the same architecture, just showing that their metrics e.g. predict how well SimCLR representations perform on different downstream tasks would improve the paper substantially. This would still allow a controlled comparison, since the source representations would be the same; it would just add another dimension of experiments to complement the present ones.\n\n* Relatedly, this paper does not compare to the work of Nguyen et al. (2020) because it \"assumes that representations come from classification tasks.\" This seems like a rather weak justification, since the present paper only evaluates representations pre-trained on classification (even if they sometimes do joint coarse + fine classification, one could apply the method of Nguyen et al. to the joint labels I believe). There may be other justifications for why the present method is superior (e.g. making use of unlabelled data); but demonstrating such benefits experimentally would improve the paper.\n\n* While it can be useful to have transfer bounds that don't depend on training, computing the probabilities used in the bounds exactly involves pairwise comparisons, i.e. $O(N^2)$ computations over the data. For large supervised datasets it seems like the transfer estimates might be better from spending an equivalent amount of compute actually training a classifier on the data and seeing how well it did. I believe similar strategies are used in neural architecture search, because performance after e.g. one epoch of training is fairly strongly correlated with asymptotic performance. It would be useful for the paper to compare to such methods.\n\n* I would also like to see some more analysis of how important the unlabelled data is in the few-shot setting, as this is fairly non-standard in the meta-learning literature. For example, the authors could vary the amount of unlabelled data, and plot the % accuracy drop correspondingly.\n\n\nLiterature\n-----------\n\nThis paper would benefit from situating further within the existing theoretical literature on transfer. This work seems in several places to overlook prior theory work that considers generalization in ways that could be (or are) applied to understanding representations and transfer. Some of these papers may not conflict with this work or impact its novelty, but nevertheless might still be worth discussing. I've ordered the works that seem related to me in roughly what I see as the order of importance for addressing them.\n\n* Petina & Lampert (2014) consider lifelong learning from a PAC-Bayesian perspective, including a representation transfer setting similar to that considered here. It would be useful to discuss any relationship between the bounds they express (taking the one-prior-task case from their work) and the present work.\n\n* Arora et al. (2019, distinct from Arora's work cited in the paper) explore a \"data-dependent complexity measure\" that discriminates at least between random and true label distributions on real tasks, and is based on a characterization of failure probability in terms of Lipschitz functions. I haven't read this paper in detail, but superficially it seems very relevant to the present work, and it should probably be discussed.\n\n* Cohen et al. (2020) consider object representation manifolds, and explore classification capacity in terms of the structure, extent, and relationships between these manifolds. These seems quite related to the notions used in this paper.\n\n* Galanti et al. (2016) extend PAC bounds to the case of transfer and consider a few different cases. Their notion of transfer is a little different than explored in this work, since they consider simultaneous training with shared weights rather than classification of trained representations. However, it seems worth discussing.\n\n* By making simplifying assumptions of linear hidden layers Advani et al. (2020) and Lampinen & Ganguli (2019) analyze learned representations and generalization in deep networks. The latter also consider some kind of transfer between tasks, though again shared weights rather than classification on trained representations. These results seem somewhat relevant, although they are within a simplified regression setting rather than classification.\n\n* Schwartz-Ziv & Tishby (2017) explore representations in terms of their mutual information with the inputs and outputs, and the dynamics of how this MI evolves over training. While MI is less directly relevant to transfer, it could at least provide a lower bound th1at might be worth considering (i.e. transfer is impossible if no mutual information), and this work suggests it might be interesting to consider transferability partway through learning (e.g. perhaps representations are more transferable before the \"compression\" phase the authors describe).\n\nIt's also quite possible that there are even more relevant papers I've missed; I hope the other reviewers will share some. \n\nReferences\n-----------\n\nAdvani, M. S., Saxe, A. M., & Sompolinsky, H. (2020). High-dimensional dynamics of generalization error in neural networks. Neural Networks, 132, 428-446.\n\nArora, S., Du, S., Hu, W., Li, Z., & Wang, R. (2019, May). Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning (pp. 322-332). PMLR.\n\nCohen, U., Chung, S., Lee, D. D., & Sompolinsky, H. (2020). Separability and geometry of object manifolds in deep neural networks. Nature communications, 11(1), 1-13.\n\nGalanti, T., Wolf, L., & Hazan, T. (2016). A theoretical framework for deep transfer learning. Information and Inference: A Journal of the IMA, 5(2), 159-209.\n\nLampinen, A. K., & Ganguli, S. (2019). An analytic theory of generalization\ndynamics and transfer learning in deep linear networks. International Conference\non Learning Representations\n\nPentina, A., & Lampert, C. (2014, June). A PAC-Bayesian bound for lifelong learning. In International Conference on Machine Learning (pp. 991-999). PMLR.\n\n\nShwartz-Ziv, R., & Tishby, N. (2017). Opening the black box of deep neural networks via information. arXiv preprint arXiv:1703.00810.\n\n", "summary_of_the_paper": "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. ", "summary_of_the_review": "The paper is clear and seems moderately useful; broader experimental evaluation and more engagement with the literature would improve it substantially.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Lxfc3-i-n_", "reviewer": "Reviewer_J9Rs", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "strengths:\n\n- The paper is very well written. The exposition is clear. The introduction makes very clear the specific challenges to be addressed in the paper and the approach taken.\n- The description of the relationship to previous work is thorough and precise.\n- Addresses an important question\n\nweaknesses:\n\n- limitations not well acknowledged/discussed. (As in any work of this sort) the presented results address a question that is narrower in scope than the one posed in the introduction. For example, the analysis assumes the relevant task is a classification task and so the results may not be relevant for reconstruction tasks or other regression tasks. The assumption that the scoring function is W -Lipschitz narrows what is meant by \"good representation\". It seems to imply that a good rep is one that is already appropriately disentangled, rather than one that can be disentangled by, say, a neural network (which would violate the assumption), to do something useful (or several useful things). A small point.\n- Pearson seems more appropriate than Spearman correlation here since the the losses and errors are on an interval rather than ordinal scale.\n- No statistical tests or confidence intervals on the correlations presented in the results.\n\nminor comments:\n\n- missing primes on x and y in second loss in the text between equations 7 and 8\n- would be good to know to what extent your correlations are driven by the concentrations at the extremes in Figure 3.\n- I don't think you need the line \"Theoretical bounds are useless if they do not impact practical decisions.\"\n- Not clear what representations were tested in the experiments without consulting the appendix. Consider moving a basic description to the main text.\n- Consider adding subpanel titles (CUB-200, CIFAR-10) to Figure 4 to make it easier to grok. You could also include a more informative plot that a bar plot, e.g. show the distribution with box & whisker or violin plot, etc.", "summary_of_the_paper": "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.", "summary_of_the_review": "The submission seems like a clear accept. It makes a clear contribution to an important topic and is very well written and clearly described. The statistical analysis of the empirical results could be improved. I made a number of minor comments that I think can be easily addressed to improve the quality of the paper. I have no major complaints. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "LJs3pypvMLx", "reviewer": "Reviewer_DEHm", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Minor Comments\n\nThe paper is well written. The concepts presented are intuitive and seem useful. And their transferability to the empirical tasks chosen seems well demonstrated. As an empiricist, I defer to other reviewers when it comes to reviewing the theoretical proofs, but I can speak to the paper’s claims of practical application.\n\nMy main concern is that the empirical tasks chosen are very constrained classification problems (made into binary tasks by choosing pairs of classes; no multi-class fine-grained classification tasks as is more realistic). I understand the desire to start with a simple settings, especially in a theoretical paper, but it makes it hard to justify the paper’s claims of testing “what makes a [good] feature representation” and “impact[ing] practical decisions”.\n\nAnother question: how does one know if an embedding is not “congregated” unless there is a less-congregated frame of reference? The paper alludes that “congregation” might help explain the success of contrastive learning, so it’s disappointing to see no experiments trying to demonstrate this.\n\nI also believe the paper would have been improved if the authors explicitly encouraged/discouraged local alignment/congregation when optimizing models, and showing that this changes the metrics introduced accordingly.\n", "summary_of_the_paper": "The paper asks the question “what makes a feature representation good for a target task?” In order to tackle this question, it introduces the concepts of local alignment (examples similar in feature space -> same labels), and congregation (how much examples generally embed close to each other). It uses them to produce bounds on achievable accuracy on binary classification problems which seem to be correlated with actual accuracy on real binary tasks.\n", "summary_of_the_review": "This is a well-written paper that investigates a narrow task setting which unfortunately does not justify its claims of practical applicability. This could change with more extensive experiments in realistic datasets/settings.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3-X8hs-yuN_", "reviewer": "Reviewer_sCcc", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: the paper is clearly written and easy to follow. The observations make intuitive sense.\n\nQuestions:\n  - How does the correlation between your lower bound and test loss compare with the correlation between kNN accuracy and the test loss?\n  - How are the values of $p_{a}^{\\phi}, p_{c}^{\\phi}$ distributed empirically?\n  - Empirically, how well can the lower bound predict the performance, when the learned representations are far from being clustered (for example, on representations from some lower layer of a network)?\n  - For few-shot transfer, how would the performance change if we vary the number of training samples per class?\n  - Do you have any recommendations on how to increase $p_{a}^{\\phi}$ and decrease $p_c^{\\phi}$ in practice?\n\nMinor point: in equation (24), $\\Delta$ should be $\\epsilon$.\n \n", "summary_of_the_paper": "This work studies the relation between properties of the feature extractor, and the downstream performance on binary classification tasks.\nThe 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.\nThe theoretical results are verified empirically on CIFAR10 and CUB200.", "summary_of_the_review": "The paper is clear and well justified.\nHowever, I find the results unsurprising, since local alignment and congregation together mean that the features should be well clustered, which is intuitive and well known.\nPersonally I think the paper would need more technical contributions to be accepted.\n\n=== Post rebuttal update ===\n\nBased on the authors clarifications and additional experimental results, I have raised my score to 5. While I agree that the paper has improved after the revision and I acknowledge the contributions, it's still below the bar to me though only marginally.\n\nSpecifically, I am now convinced that the intuitive connection with knn is a plus, though I still think the theoretical novelty is limited.\nGiven the theoretical contribution, I'd expect stronger empirical results for the proposed method to be convincing. Potential improvements, as also mentioned by other reviewers, include 1) comparing with more baseline methods with a larger variety of features (e.g. expand Table 1 with results from other self-supervised methods, including non-contrastive ones), and 2) better justifying the criteria for model selection (i.e. the sum of the lower bound in Thm 1 and the upper bound in Thm 2) as it currently seems arbitrary.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, authors introduce two properties of feature representations, namely local alignment and local congregation, and show how these properties can be predictive of downstream performance. The paper has a heavier focus on providing theoretical statements using these properties but authors also empirically evaluate their suggested method.

**Strong Points**:
- The paper is well-written and easy to follow.


- The proposed concepts (local alignment and local congregation) are intuitive.


- The theoretical statements and their proofs are correct.


- The proposed metric shows some advantage against a few baselines.


- Prior work on feature representations and transferability are discussed.


**Weak Points**:


- **The connections to prior work on K-nearest neighbors and linear classifiers are not properly discussed.** This is very important because authors assume that the network that outputs the feature representations is trained on a different data and they reduced the analysis to that of a binary linear classifier. Hence, all classical learning theory results on binary classifiers apply in this setting. Furthermore, KNN methods and analysis can be simply applied on the features as well. In light of this and the lack of discussion on this matter, the significance of the theoretical and empirical results are not clear.


- **The main proposed properties could be improved further**. It looks like the defined properties (local alignment and local congregation) could be improved by merging them into one property about separability of data? The current properties are sensitive to scaling which is undesirable given that classification performance is invariant to scaling of the features. It seems like local congregation is mostly capturing the scale so some normalized version of local alignment might be able to capture the main property of interest.


- **The theoretical results in their current form are not very significant.** One limiting factor on the theoretical results is that since the analysis is done only on the classification layer, it does not say anything about the relationship of the upstream and downstream tasks. But perhaps the most important limitation is that the properties are defined based on the downstream task distribution as opposed to downstream training data. That makes it difficult to measure them in practical settings where we have a limited number of data points. Classical results on learning theory avoid this and only use measures that depend on the given training set.


- **The empirical evaluation could benefit from stronger baselines** Authors mentioned "We therefore consider only baselines that make minimal assumptions about the pre-trained feature representation and the target task" and hence avoided comparing to many prior methods. However, I think the appropriate approach would be to compare the performance of the proposed method to strong baselines but then explain how they differ in terms of their assumptions, etc. Moreover, there are other simple heuristic baselines to consider, eg. K-NN (which is not computationally expensive in the few-shot settings) or a classifier that is trained by initializing it to be the sum of feature vectors in the first class (assuming binary classification) minus sum of feature vectors in the second class and doing a few SGD updates on it. Therefore, I believe authors could improve the empirical section significantly by taking these suggestions into account.


**Final Decision Rationale**:

This is a borderline paper. While the paper has a nice combination of theoretical and empirical contributions, both theoretical and empirical contributions have a lot of room for improvement (and a clear path to get there) as pointed above. In particular, I believe having either strong theoretical contributions or strong empirical contributions would have been enough for acceptance and I hope authors would take the above suggestions into account and submit the improved version of this work again!
Decision: Reject