# A THEORETICALLY GROUNDED CHARACTERIZATION
## OF FEATURE REPRESENTATIONS

**Anonymous authors**
Paper under double-blind review

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.

1 INTRODUCTION

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.


-----

Figure 1: An illustration of the properties of local alignment and congregation. Feature representations on the left are more congregated than those on the right. The first and third feature representations 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.

2 RELATED WORK

**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.

3 PROBLEM SETUP

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 → R[f] 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 : R[f] _→_ 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 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 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→** **w[T]** **v; ∥w∥≤** _W_ .

Because the zero-one loss, l[∗](h(φ(x)), y) = I[sign(h(φ(x))) ̸= 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.

4 TWO PROPERTIES OF FEATURE REPRESENTATIONS

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:


-----

Figure 2: Intuition behind our analysis for the lower bound on error (Theorem 1, Left) and upper
bound on generalization (Theorem 2, Right). In each case we look at pairs of data points that fall
within a distance α of each other (shown as red balls). The lower bound notes that examples with
different labels in these balls yield high error. 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 α > 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.

5 WHAT IS THE BEST ACCURACY WE CAN ACHIEVE?

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 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 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[′])∥_ _<_ _W1_ _[and][ y][ ̸][=][ 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 ̸= 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_

1 1

inf 1 _p[φ]a_ _p[φ]c_ (16)
_h∈H_ [E][x,y][∼D][[][l][(][h][(][φ][(][x][))][, y][)]][ >][ 1]2  _−_  _W_   _W_ 


_Proof. We observe that if (x, y), (x[′], y[′]) ∼D, then the probability that ∥φ(x) −_ _φ(x[′])∥_ _<_ _W1_ [and]

_y ̸= y[′]_ is given by ˜p = (1 − _p[φ]a[(1][/W]_ [))][p][φ]c [(1][/W] [)][. Then, for all][ h][ ∈H][.]


Ex,y [l(h(φ(x)), y)] = [1] (17)
_∼D_ 2 [E][(][x,y][)][,][(][x][′][,y][′][)][∼D][[][l][(][h][(][φ][(][x][))][, y][) +][ l][(][h][(][φ][(][x][′][))][, y][′][)]]

_p_
_φ(x)_ _φ(x[′])_ _<_ [1] (18)
_≥_ 2[˜][E][[][l][(][h][(][φ][(][x][))][, y][) +][ l][(][h][(][φ][(][x][′][))][, y][′][)] _∥_ _−_ _∥_ _W_ [and][ y][ ̸][=][ y][′][]]

_p_
(19)
_≥_ 2[˜]

(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.

6 HOW WELL WILL CLASSIFIERS GENERALIZE?

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).

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 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_ _φ, let lmax(z, S) = max(x,y)_ _S l(z(x), y) be the maximum loss z incurs on_
_∈H_ _∈_
_S. Then, for all ϵ > 0 and (x, y) ∼D:_

_m_

_ϵ_ _ϵ_
_P (l(z(x), y) > lmax(z, S) + ϵ) ≤_ 1 − _p[φ]a_ _W_ _p[φ]c_ _W_ _._ (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_ _φ_ (23)
_⇒_ _≤_ _∀_ _∈H_


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)

_m_

_ϵ_ _ϵ_
= 1 − 1 − _p[φ]c_ _W_ _p[φ]a_ _W_ (25)
    

6.2 BOUNDING THE EXCESS RISK

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)_ _m(_ ) + log [1]δ (26)
_−_ [ˆ] _≤R_ _H_ s 2m

where R(h) is the test loss (or expected risk), _R[ˆ](h, S) is the training loss (or empirical risk), and_
_m(_ ) is the Rademacher complexity of .
_R_ _H_ _H_

Thus, to bound the generalization error, it suffices to bound the Rademacher complexity of, which
is defined as Rm(H) = ES∼Dm,σ suph∈H _m1_ _mi=1_ _[σ][i][h][(][x][i][)][. Here][ σ][i][ are Rademacher random] H_

the hypothesis class, and can be used to bound the difference between a hypothesis’ performance onvariables (i.e., σi ∈{−1, 1}, Eσi = 0). The Rademacher complexity is a measure of the size ofP
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 of Wφ is bounded above by:_

_W_ _α_ _p[φ]c_ [(][α][)][/][2 + 2][B] (1 − _p[φ]c_ [(][α][)) + 2(1][ −] _[p]c[φ][(][α][))][2]_
_m(_ _φ)_  q q  (27)
_R_ _W_ _≤_ 2[√]m


that the next pointProof sketch: (Full proof presented in Appendix). For any xi+1 is (a) within a distance α in feature space, and (b) is multiplied with a xi ∈ _S, there is a probability p[φ]c_ [(][α][)][/][2]
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).


1.6 1.6

1.4 Random 1.4

1.2 SimCLR 1.2

ImageNet

1.0 1.0

( )0.8 0.8( )
a c
p p

0.6 0.6

0.4 0.4

0.2 0.2

0.0 0.0

0.0 0.2 0.4 0.6 0.8 1.0


Figure 3: pa (left axis, solid line) and pc (right
axis, dotted line) as a function of α for three feature representations on CIFAR-10


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.

8 EMPIRICAL ANALYSIS


Above we have shown that p[φ]a [and]
_p[φ]c_ [yield bounds on classifier perfor-]
mance. But are they useful enough in Representation _pa_ _pc_ Test loss Excess risk

(large dataset) (5-shot)

practice to make decisions? We first
look to see whether they are corre- Random 0.51 0.88 0.29 0.26
lated with actual loss values, and then SimCLR 0.7 0.1 0.18 0.24
present potential applications. ImageNet 1.0 0.0 0.04 0.65

8.1 CORRELATIONS Table 1: Three representations with different alignment and
WITH CLASSIFIER ACCURACY congregation, and the corresponding test loss (with large

training sets) as well as excess risk with tiny training sets.

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 cor-**
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


-----

Lower bound vs training loss Theorem 2 vs excess risk

12

8

10

8 6

6

4

Number of tasks 4 Number of tasks

2

2

0 0

0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0

Correlation Correlation

Theorem 3 vs excess risk Classical bound vs excess risk

12

10

10

8

8

6

6

Number of tasks 4 Number of tasks 4

2 2

0 0

0.0 0.2 0.4 0.6 0.8 1.0 0.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 3 (right) vs actual excess risk.

CUB 200 CIFAR-10

40

40 35

30

30

25

20

20

15

10 10

% Error relative to oracle % Error relative to oracle

5

0 0

Random Hscore TransRate Ours Random Hscore TransRate Ours


Figure 5: Our characterization of the feature space allows us to choose the best pre-trained representation for a 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 ρ 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.


-----

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 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 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 better choices than both baselines on both benchmark datasets thus suggesting the usefulness of our
characterization for practical problems.

9 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 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.

REFERENCES

Alessandro Achille, Michael Lam, Rahul Tewari, Avinash Ravichandran, Subhransu Maji, Charless 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–6439,
2019.

Pulkit Agrawal, Ross Girshick, and Jitendra Malik. Analyzing the performance of multilayer neural 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 optimization and generalization for overparameterized two-layer neural networks. In International
_Conference on 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 computer-generated imagery. 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-theoretic 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 2021 IEEE Winter Conference on 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. In International conference on machine learning,
pp. 1597–1607. PMLR, 2020.

Uri Cohen, SueYeon Chung, Daniel D 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 fine-grained
categorization and domain-specific transfer learning. In Proceedings of the IEEE conference on
_computer vision and pattern recognition, pp. 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. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern
_Recognition, pp. 12387–12396, 2019._


-----

Kshitij Dwivedi, Jiahui Huang, Radoslaw Martin Cichy, and Gemma Roig. Duality diagram similarity: a generic framework for initialization selection in task transfer learning. In European
_Conference on Computer Vision, pp. 497–513. Springer, 2020._

Tomer Galanti, Lior Wolf, and Tamir Hazan. A theoretical framework for deep transfer learning.
_Information and Inference: A Journal of the IMA, 5(2):159–209, 2016._

Yansong Gao and Pratik Chaudhari. An information-geometric 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 selfsupervised visual representation learning. In 2019 IEEE/CVF International Conference on Com_puter Vision (ICCV), pp. 6390–6399. IEEE._

Yunhui Guo, Noel C Codella, Leonid Karlinsky, James V Codella, John R Smith, Kate Saenko, Tajana 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 Huang, Ying Wei, Yu Rong, Qiang Yang, and Junzhou Huang. Frustratingly easy transferability estimation. arXiv preprint arXiv:2106.09362, 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 Kornblith, 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), 115(3):211–252, 2015. doi: 10.1007/s11263-015-0816-y._

Ravid Shwartz-Ziv and Naftali Tishby. Opening the black box of deep neural networks via information. arXiv preprint arXiv:1703.00810, 2017.

Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In
_Proceedings of the 31st International Conference on 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 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3922–3930, 2020._


-----

Ryan Steed and Aylin Caliskan. Image representations learned with unsupervised pre-training contain human-like biases. In Proceedings of the 2021 ACM Conference on Fairness, 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.6199, 2013.

Anh T Tran, Cuong V Nguyen, and Tal Hassner. Transferability and hardness of supervised classification 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-supervised learning across
domains. In ECCV, 2020.

Bram Wallace, Ziyang Wu, and Bharath Hariharan. Can we characterize tasks without labels or features? 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 alignment and uniformity on the hypersphere. In International Conference on Machine Learning, pp.
9929–9939. PMLR, 2020.

P. Welinder, S. Branson, T. Mita, C. Wah, F. Schroff, S. Belongie, and P. Perona. Caltech-UCSD
Birds 200. Technical Report CNS-TR-2010-001, California Institute of Technology, 2010.

Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep
neural networks? arXiv preprint arXiv:1411.1792, 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[′]) ≤|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 of Wφ is bounded above by:_


_p[φ]c_ [(][α][)][/][2 + 2][B]


(1 − _p[φ]c_ [(][α][)) + 2(1][ −] _[p]c[φ][(][α][))][2]_
 (28)

2[√]m


_m(_ _φ)_
_R_ _W_ _≤_

_Proof. First note that:_

_Rm(Wφ) = ES,σ supz∈Wφ_

= [1]

_m_ [E][S,σ][ sup]h∈W


_σiz(xi)_ (29)
_i=1_

_mX_

_σiwh[T]_ _[φ][(][x][i][)]_ (30)
_i=1_

X


= [1] **wh[T]** [(]

_m_ [E][S,σ][ sup]h∈W


_σiphi(xi))_ (31)
_i=1_

X


_≤_ _[W]m_ [E][S,σ][∥]


_σiφ(xi)∥_ (∵ _∥wh∥≤_ _W_ ) (32)
_i=1_

X

(33)


Thus we need to bound ES,σ∥ [P]i[m]=1 _[σ][i][φ][(][x][i][)][∥]_

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][ P]i[m]=1 _[σ][i][φ][(][x][i][) =]_
_m_ _m_
_i=1_ _[σ]i[′][φ][(][x][′]i[) =][ 1]2_ _i=1[(][σ][i][φ][(][x][i][) +][ σ]i[′][φ][(][x][′]i[))][.]_
PENote thatS,σai = x EiS,σ ⊥⊥a[2]ix[=][′]i P[and][ p]c[φ]2[(][ σ][α][)][i][ ⊥], which we will denote as⊥ _σi[′][. Define][ a][i][ =][ I][[(][σ] p[i][ =]α._ _[ −][σ]i[′][)][ and][ (][∥][φ][(][x][i][)][ −]_ _[φ][(][x][′]i[)][∥]_ _[< α][)]][. Then]_

Therefore:


_σiφ(xi)_ (34)
_∥_
_i=1_

X


ES,σ∥


= [1]

2 [E][S,σ][∥]


(σiφ(xi) + σi[′][φ][(][x][′]i[))][∥] (35)
_i=1_

X


= [1]

2 [E][S,σ][∥]

_≤_ [1]2 [E][S,σ][∥]


(aiσi(φ(xi) − _φ(x[′]i[)) +]_
_i=1_

Xm

_aiσi(φ(xi) −_ _φ(x[′]i[))][∥]_
_i=1_

X


_a¯i(σiφ(xi) + σi[′][φ][(][x][′]i[)))][∥]_ (36)
_i=1_

X


+ [1]

2 [E][S,σ][∥]

+ [1]

2 [E][S,σ][∥]


_a¯iσiφ(xi)_
_∥_
_i=1_

Xm

_a¯iσi[′][φ][(][x][′]i[)][∥]_ (37)
_i=1_

X


-----

Observe thatterm yields: _ai ⊥⊥_ _σi, and ai ⊥⊥_ _σi[′][. Using this, the second and third terms are similar. The second]_


1
2 [E][S,σ][∥]

= [1]

2 [E][S,σ]


_a¯iσiφ(xi)_ (38)
_∥_
_i=1_

X

_m_

_a¯ia¯jσiσjφ(xi)[T]_ _φ(xj)_ (39)
_i,j=1_

X


_≤_ [1]2


ES,σa¯ia¯jσiσjφ(xi)[T] _φ(xj)_ (40)
_i,j=1_

X


We note that if i = j and i = π(j) and j = π(i) then ¯aiσi _a¯jσj. Thus, looking at the expression_
under the square root: ̸ _̸_ _̸_ _⊥⊥_

_m_

ES,σa¯ia¯jσiσjφ(xi)[T] _φ(xj)_ (41)
_i,j=1_

X

_≤_ _i_ ES,σa¯[2]i _[σ]i[2][∥][φ][(][x][i][)][∥][2]_ (42)
X

+ ES,σa¯ia¯jσiσjφ(xi)[T] _φ(xj)_ (43)

_i,j:i=π(j)orj=π(i)_

X

_≤B[2][ X]_ ES,σa¯[2]i _[σ]i[2]_ (∵ Ea¯[2]i [=][ E]a[¯]i = 1 − _pα)_ (44)

_i_

+ B[2] ES,σa¯ia¯jσiσj (45)

_i,j:i=π(j)orj=π(i)_

X


ES,σa¯ia¯j (∵ Eσi ≤ 1) (46)
_i,j:i=π(j)orj=π(i)_

X


_B[2]m(1_ _pα) + B[2]_
_≤_ _−_


_B[2]m(1_ _pα) + B[2]2m(1_ _pα)[2]_ (47)
_≤_ _−_ _−_

. Thus:


1
2 [E][S,σ][∥]


_a¯iσiφ(xi)_ (48)
_∥_
_i=1_

X


_≤_ _[B]2_


_m(1_ _pα) + 2m(1_ _pα)[2]_ (49)
_−_ _−_


Through similar reasoning, the first term yields:

_m_

1

_aiσi(φ(xi)_ _φ(x[′]i[)][∥]_ (50)

2 [E][S,σ][∥] _−_

_i=1_

X

_m_

ES,σa[2]i _[σ][2][∥][φ][(][x][i][)][ −]_ _[φ][(][x]i[′]_ [)][∥][2] (51)

_≤_ [1]2 v

u _i=1_
uX
t _m_

ES,σa[2]i _[α][2]_ (52)

_≤_ [1]2 v

u _i=1_
uX
t


= [1]


_mpαα[2]_ (∵ Ea[2]i [=][ E][a][i] [=][ p][α][)] (53)


-----

0.7

0.5

0.6

0.5 0.4

0.4

0.3

0.3

Train loss Actual excess risk

0.2 0.2

0.1

0.0 0.1

0.00 0.05 0.10 0.15 0.20 0.25 0.2 0.4 0.6 0.8 1.0

Lower bound on loss New bound on bad performance

0.5 0.5

0.4 0.4

0.3 0.3

0.2 0.2

Test loss - train loss Test loss - train loss

0.1 0.1

1.50 1.75 2.00 2.25 2.50 2.75 3.00 3.25 1.6 1.8 2.0 2.2 2.4 2.6

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-based bound vs excess risk, and
Theorem 3 vs excess risk.

Putting these expressions back in equation 37, we get:

_m(_ _φ)_ _mpαα[2]_ + B _m(1_ _pα) + 2m(1_ _pα)[2]_ + B _m(1_ _pα) + 2m(1_ _pα)[2])_
_R_ _H_ _≤_ 2[W]m [(] _−_ _−_ _−_ _−_

p p p (54)

_W_ _α[√]pα + 2B_ _m(1 −_ _pα) + 2m(1 −_ _pα)[2]_
= (55)
 p 2[√]m 

A.2 SCATTER PLOTS

See Figure 6.

A.3 REPRESENTATIONS USED IN EXPERIMENTS

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 dataset C 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 on C _∪F with fine-grained soft pseudo-labels for C obtained using_
a classifier trained on F

5. A representation trained on C _∪F with fine-grained soft pseudo-labels for C 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.**

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 Y. There
is an underlying distribution D over X × Y. We have a feature representation φ : X → R[f] 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 : R[f] _×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 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(φ(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→** **wy[T]** **[v][;][ ∥][w][y][∥≤]** _[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 = arg maxy′ h(φ(x), y[′])]. We will use the following continuous margin-based upper bound:
_̸_

_l(h, φ(x), y) = min(1, max(0, max_ (57)
_y[′]=y[(1 +][ h][(][φ][(][x][)][, y][′][))][ −]_ _[h][(][φ][(][x][)][, y][)))][ ≥]_ _[l][∗][(][h, φ][(][x][)][, y][)]_
_̸_

We can now prove equivalent lower and upper bounds as below.

A.4.2 LOWER BOUND


**Claim 3. Consider two data points (x, y) and (x[′], y[′]). If ∥φ(x) −** _φ(x[′])∥_ _<_ 2W1 _[and][ y][ ̸][=][ 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[′])_ _y_ (59)
_|_ _−_ _| ≤_ _∥_ _−_ _∥≤_ 2[1] _∀_

_h(φ(x[′]), y)_ [h(φ(x), y) (60)
_⇒_ _∈_ _−_ [1]2 _[, h][(][φ][(][x][)][, y][) + 1]2_ []]]

This in turn implies that for any pair of classes y1 and y2,


_h(φ(x[′]), y1)_ _h(φ(x[′]), y2)_ _h(φ(x), y1)_
_−_ _≥_ _−_ [1]2 2 [)][ ≥] _[h][(][φ][(][x][)][, y][1][)][ −]_ _[h][(][φ][(][x][)][, y][2][)][ −]_ [1]

_[−]_ [(][h][(][φ][(][x][)][, y][2][) + 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_ (62)
_y[′′]=y[(1 +][ h][(][φ][(][x][)][, y][′′][))][ −]_ _[h][(][φ][(][x][)][, y][))]_
_̸_

max (63)
_≥_ _y[′′]=y[(1 +][ h][(][φ][(][x][)][, y][′′][))][ −]_ _[h][(][φ][(][x][)][, y][)]_
_̸_

_≥_ 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_ (66)
_y[′′]=y[′][(1 +][ h][(][φ][(][x][′][)][, y][′′][))][ −]_ _[h][(][φ][(][x][′][)][, y][′][))]_
_̸_

max (67)
_≥_ _y[′′]=y[′][(1 +][ h][(][φ][(][x][′][)][, y][′′][))][ −]_ _[h][(][φ][(][x][′][)][, y][′][)]_
_̸_

_≥_ (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:

Note that the only difference between the bounds for the binary and the multiclass case is the factor

**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_

1 1

inf 1 _p[φ]a_ _p[φ]c_ (72)
_h∈H_ [E][x,y][∼D][[][l][(][h][(][φ][(][x][))][, y][)]][ >][ 1]2  _−_  2W   2W 

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** _-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′≠ _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)

max max (75)

_≤_ _y[′]=y[(1 +][ h][(][φ][(][x][)][, y][′][))][ −]_ _[h][(][φ][(][x][)][, y][)]_ _−_ _y[′]=y[(1 +][ h][(][φ][(][x][′][)][, y][′][))][ −]_ _[h][(][φ][(][x][′][)][, y][)]_

 _̸_   _̸_ 

= max + (h(φ(x[′]), y) _h(φ(x), y))_ (76)

_y[′]=y[(1 +][ h][(][φ][(][x][)][, y][′][))][ −]_ [max]y[′]=y[(1 +][ h][(][φ][(][x][′][)][, y][′][))] _−_
 _̸_ _̸_ 


_≤_ _y[′]=y[(1 +][ h][(][φ][(][x][)][, y][′][))][ −]_ [max]y[′]=y[(1 +][ h][(][φ][(][x][′][)][, y][′][))] [+][ |][h][(][φ][(][x][′][)][, y][)][ −] _[h][(][φ][(][x][)][, y][)][|]_ (77)
_̸_ _̸_

max (78)
_≤_ [max]y[′][ |][h][(][φ][(][x][)][, y][′][)][ −] _[h][(][φ][(][x][′][)][, y][′][)][|][ +][ |][h][(][φ][(][x][′][)][, y][)][ −]_ _[h][(][φ][(][x][)][, y][)][|]_

_≤_ _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_

_m_

_ϵ_ _ϵ_
_P (l(h, φ(x), y) > lmax(k, S) + ϵ) ≤_ 1 − _p[φ]a_ 2W _p[φ]c_ 2W _._ (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[′])_ _<_ 2∆W
_∥_ _−_ _∥_

_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[(∆][/][2][W] [)][p][φ]c [(∆][/][2][W] [)][. 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)

_m_

_ϵ_ _ϵ_
= 1 − 1 − _p[φ]c_ 2W _p[φ]a_ 2W (85)
    


Once again, the only difference in proofs is the use of factor 2W instead of W .


-----

