On the Trade-off of Intra-/Inter-class Diversity for Supervised Pre-training
Authors: Jieyu Zhang
Bohan Wang
Zhengyu Hu
Pang Wei Koh
Alexander Ratner
Venue: NeurIPS 2023 poster (2023)
Keywords: data-centric study
supervised pretraining
transfer learning
TL;DR: A comprehensive study on the impact of the intra-/inter-class diversity of the supervised pre-training dataset on downstream performance.

Abstract: Pre-training datasets are critical for building state-of-the-art machine learning models, motivating rigorous study on their impact on downstream tasks. In this work, we study the impact of the trade-off between the intra-class diversity (the number of samples per class) and the inter-class diversity (the number of classes) of a supervised pre-training dataset. Empirically, we found that with the size of the pre-training dataset fixed, the best downstream performance comes with a balance on the intra-/inter-class diversity. To understand the underlying mechanism, we show theoretically that the downstream performance depends monotonically on both types of diversity. Notably, our theory reveals that the optimal class-to-sample ratio (#classes / #samples per class) is invariant to the size of the pre-training dataset, which motivates an application of predicting the optimal number of pre-training classes. We demonstrate the effectiveness of this application by an improvement of around 2 points on the downstream tasks when using ImageNet as the pre-training dataset.

On the Trade-off of Intra-/Inter-class Diversity for Supervised Pre-training
Jieyu Zhang'; Bohan Wang"; Zhengyu Hu Pang Wei Koh Alexander Ratner 1.4
1 University of Washington USTC 3 HKKUST(GZ)
Snorkel AI, Inc.
{jieyuz2, panguei, pan.guiiiaanneiiiapaa ajsggeerr...aatrr)......o bhwangfy0gail..com zhu0218connect. www.settt.huutgeeee hkust-gz.edu.
Abstract
Pre-training datasets are critical for building state-of-the-art machine learning models, motivating rigorous study their impact downstream tasks. In this work, we study the impact of the trade-off between the intra-class diversity (the number of samples per class) and the inter-class diversity (the number of classes) of a supervised pre-training dataset. Empirically, given fixed pre-training dataset size, we find that the best downstream performance comes with balance on the intr-/interrcllas diversity. To understand the underlying mechanism, we show theoretically that downstream performance depends monotonically on both types of diversity. Notably, our theory reveals that the optimal class-to to-spplle ratio Aclasses
#samples per class ) i.e., the ratio of the number of pre-training classes to the number samples per class, is invariant to the size of the pre- pre-trainin trainininng dataset, enabling the prediction of the optimal number of pre- pre-training classes. We demonstrate the effectiveness of this application by an improvement of approximately 2 points on average downstream tasks when pre-training ImageNet.
1 Introduction
Many state-of-the-art deep neural network models are pre-trained on large datasets before being finetuned for downstream tasks [13 23 II. While the composition of their pre-training dataset has been shown to be a key factor in the performance of these models [7] 9 14 g 12] 26), how best to design these pre-training datasets still remains underexplored. supervised pre-training,
this work, we focus on of the most popular pre pre-training paradigms, and study two key quantities of supervised pre-training dataset: intra-class diversity (the number of different samples within each pre-training class) and inter-class diversity (the number of different pre-training classes). Intuitively, both diversities are beneficial for supervised pre-training [3]. Yet when the size of the pre-training will decrease the other. Our work studies the impact of this dataset diversity trade-off on downstream performance, as well as how to balance them design supervised pre-training dataset with the best downstream performance.
dataset is fixed, these diversities trade off, since increasing
Empirically, with ImageNet 24 as the pre-training dataset and the pre-training dataset size fixed, we show that the optimal performance on the downstream tasks occurs when a balance the intra-/inter- class diversity is achieved. We then offer thcoretical explanation for this effect by first modeling the dataset generation process through two-step sampling framework. and then demonstrating that the test error of the downstream task displays a rational relationship with respect to the class-to-sample ratio, i.e., the ratio of the number of pre-training classes to the number of samples per class, or, in other words, the ratio between inter-/intra- diversity. The established analytical relationship
"These authors contributed equally to this work.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

between downstream performance and the flass-to-samp ratio can serve as guiding principle in designing a supervised pre-training dataset by estimating the optimal paass-to-smpll ratio rather than the grid search.
Notably, our theory shows that given source of pre-training dataset and downstream task, the optimal class-to -lasse ratio is invariant to the size of the pre-training dataset. Based on such an invariance, one could estimate the optimal class-to-sample ratio with small pre-training datasets and then leverage it to build a large-scale pre-training dataset. In particular, the optimal number of pre- training classes K and the number of examples per class n are proportional to the square root of the size of the pre-training dataset N, i.e. K VN, which leads to an invariant optimal Blass-to-sampe ratio. We empirically verify our theoretical findings on ImageNet (24] and present the effectiveness of its application in predicting the optimal number of classes for pre-training datasets with different sizes. In addition, we conducted experiments with different pre- pre-trained datasets, different model backbones, and downstream tasks of different domains demonstrate that our findings are consistent across many scenarios.
Our major findings and contributions are as follows:
In supervised pre-training, we observe that with fixed pre-training dataset size, there exists trade-off between intra-class and inter-class diversities. This balance between diversities plays a crucial role in shaping the downstream performance, underscoring the significance of considering both aspects when designing the pre-training dataset;
We then theoretically explain this effect by first modeling the dataset generation process through a two-step sampling framework and then showing that the test error of the downstream task displays a convex relationship with respect to the class-to- toa-tto-sammy sample ratio, serving as a guiding principle in designing a supervised pre- pre-training dataset.:
Our theory also uncovers the invariance of the optimal class-to class-to-sample ratio with respect to the size of the pre-training dataset, allowing us to predict the optimal number of classes with a small number of pre-training data before building a larger pre-training dataset for a downstream task.
2 Empirical Observations
The goal of this work is to study the trade-off of intra-/inter-class diversity in a supervised pre-training dataset and its impact on the pre-trained model's performance on downstream tasks. Specifically, the inter-class diversity refers to the diversity of classes in pre-training dataset, i.e., how many different classes we have (K); while the intra-class diversity refers to the diversity of samples within each class, i..., how many different samples in each class (n.. When the size of the pre-training dataset is fixed, increasing either type of diversity will by definition decrease the other, leading to a dataset diversity trade-off. To study the impact of such dataset diversity trade-off, we experiment with pre-training datasets with varying numbers of classes and number of samples per class. The experimental details can be found in Appendix [A.2]
we use the ImageNet (24 as the dataset for supervised pre-training. In this work, mainly ResNet-18 18 [10] as the backbone model. For evaluating the performance of the pre- pre-trained model on downstream tasks, we perform linear probing (tuning the head but freezing the lower layers). We repeat each individual experiment five times and report the averaged top-1 accuracy.
Evaluation protocol. Following common practice 13
Downstream tasks. We adopt the following six datasets as the downstream classification tasks: Stanford40 dataset (25) for action recognition, StanfordDogs [15] for fine-grained object recognition, MIT67 (22 for scene classification, CIFAR1O [66] for image recognition datasets, Flowers 102 (20 for image classification dataset, FGVCAircraft [8] for aircraft classification datasct.
While having all the other configurations fixed, during pre-training, we vary the number of classes and the number of samples per class. Specifically, given N as the size of the pre-training dataset and K as the number of classes, we randomly sample K classes from ImageNet and then uniformly sample n K samples from each class to compose the dataset. We experiment with the following N and K values: (IK, 2K, 5K. 10K, 20K, 50K, 100K) and (2, 10, 20, 50, 100, 200, 500, 1000) respectively. Note that with larger N (e.g. N = 10K), we cannot evaluate smaller values of K (e.g.. K = 2), since in ImageNet each class has at most 1300 samples.

---

8.30
S
lagin) 0
0.42
login)
lagtn)
50
0.04
0.50
log(K)
log(K)
log(K)
CIFARIO
(b) FGVCAicraft
(c) Flowers
6
6
0.72
0..00
logtn)
4
0.72
logio)
64
logtn)
4
00
2
2
86
1
2
4 log(K)
5
6
3
log(K)
log(K)
(d) MITG7
(e) Stanford40
(l) StanfordDogs
Test error rate (the darker, the better) function of intra-class diversity the y-axis (log n) and inter-class diversity on the x-axis (log K). Each plot represents a different dataset. The red dashed anti-diagonal lines indicate fixed pre-training dataset sizes (log K log n log N is constant), from which we can see that obtaining the best downstream performance given a fixed pre-training dataset size requires balancing both diversities.
Figure 1:
Results and observations. We visualize the results in Figure In the contour plot, the z-value is the error rate on the test set, thus lower is better. The x-axis and y-axis are inter-class diversity (log K) and intra-class diversity (log in the log space, respectively. The values anti-diagonal lines (y = - + c) share the same pre-training dataset size as log N log K + log n. From the results, beneficial for downstream tasks: We can see that increasing either inter-class diversity (Aog K) or intra-class diversity (log n), given the other is fixed, would lead to better test error rate. This is intuitive and expected, since the size of the pre-training dataset N would increase accordingly, which is known to be beneficial for downstream tasks 717 13) 2) A trade-off of intra-/inter-class diversity on downstream task performance: More importantly, by looking at the anti-diagonal lines where log is fixed and equals log K log n,, we can see trade-off between intra-/inter-class diversity the test rate of downstream tasks: either cases of 1) high inter-class diversity, low intra-class diversity and 2) low inter-class diversity and high intra-class diversity would not render the best performance. Instead, some point in the middle of the anti-diagonal line leads to the lowest test error rate.
have observations: 1) Both intra-iinter-class diversity
3 Theoretical Understanding
In this section, we first present the theoretical setup and notations and then provide a theory on the impact of the pre-training dataset diversity on downstream performance. We also show that the optimal class-to-sample ratio ( is invariant to the size of the pre-training dataset; such a property can be leveraged predict the optimal number of classes for building a large pre-training dataset with small number of data samples first.
3.1 Setup and notations
Dataset. To be consistent with our experimental setup. we consider the supervised pre-training task. Specifically, we can access two datasets, one for the pre-training task (denoted as S") and another for the downstream task (denoted as 5td). Each example in the pre-training dataset consists of input features K the number classes). Specifically, we denote S ((x1, y1), .,. (IN, yN)), where N the size of SP, and assume that S" is sampled according some underlying distribution P (we do
X Rd: (where dj is the dimension of data) and a label y E [K] (where
3

---

not specify P here because we will analyze cases with different P latter). Every example in the downstream dataset consists of input features I E A' and label [K] (note that K does not necessarily equal-to K), and is sampled i.idd according to underlying distribution P. We denote Sd (($1, 01), (Zx, R and thus 5 ~ P...
Model. The models for both pre-training and downstream tasks consist of two components: the feature extractor and the classifier. Specifically, the model for the pre-training task is given as fS o hgr, where fsr :R + R is the pre-training classifier (dy is the dimension of feature) and hge R + d2 is the feature extractor. We denote the set of all possible fss F, and the set of all possible as H. The model for the downstream task is given as fSa hgs, where fS* 12 - R is the downstream classifier and h is the feature extractor shared with the pre-training task. We set all possible fso as F.
Loss. To measure the correctness of model's predictions, given an example (r, y) and pre-trainin/ddownstrenn model f h, the corresponding cross-entropy loss is defined
the cross-entropy loss. Specifically,
@foh((x)
{(f o h(x),)) = -log Σ, E,ihoh(x))
where f; h(x) is the i-th coordinate of f h(r). We make the following assumption about the complexity of the model.
Assumption 1. There exist a positive constant Mc. such that Vi. Vf E FUF,he H
{(f a h(x), M
Furthermore, for any distribution Q over the feature space RR, any m E N, and any F' E {F,F) define the Gaussian complexity of function class F' H over the marginal distribution Q with sample number m as
TR
GO H) A -aw.
sup
ΣΣ
ouass o h(x.).
JEF i=ij=l
Here K' dim(()) We assume that G2 H) S Gym, where G is independent of Q and m.
Assumption constrains the dependence of model complexity over the number of sample N, which a standard assumption in generalization analysis [99]
Risks and corresponding minimizers. We first define the empirical risk R2 (foh, ST) and population risk Rf o h, P) over the pre-training task as
N
o A
(f e u())) of o (s o,, SP).
The corresponding feature extractor and classifier of the empirical risk minimizer over the pre-training task as
hr arg min keR
min R2 (f o 5P) fse A feF
arg min JEF
min Rp o h, hT,
Given a feature extractor h E H. we measure its performance over the pre-training task through classifier agnostic approach by considering
(h, P) A min R,, P).
JEF
Note here slightly abuse the notation of R2 without causing confusion f h and h have different image spaces. The representation error of h over P then defined as the gap between the risk of and the smallest possible risk
(hh P) A R,, P) min R, P). (b,
hCR
This inequality holds for wide range of models, including deep neural networks 2

---

Similarly, the empirical risk Ru(f o h, 5 and population risk Ra(f o h P) over the downstream task are defined as
Ralf o S4)
h(t.).)))) Ra(s a P) Ege Ra(s h,
The learned classifier from the downstream task can then be defined as
fs -
arg min FEF
min Ra( a lis,, soh) )t)).
hEW
The corresponding performance and excess risk of h over the downstream task can then be defined as
Ra(h, P) & min Ra(f o h. P), Ea(h, P) Ra(h, P) miin Ra(h, (ahh.)) P). hEH
jEF
Finally, we are interested in the excess risk of the obtained model fSa lio over the downstream task, i.e.,
Eal hs, P) a Ralfsa hs, P) min Ra(h, P).
bEи
3.2 A theory on the impact of intra-/inter-class diversity trade-off
In this work, we focus on a common practice of collecting the pre-training dataset: one first sample K' classes and then collect samples for each class. We start with detailed characterization of such data generation process, followed by assumptions and the main result.
Data generation process 1. We assume the pre pre-trainmnn training data is generated through a two-step sampling process. Specifically, suppose that there is a distribution D over A (X') (the set consisting of all distributions on X). Then, S" is generated by the following procedure (and P is naturally induced)
Sample K classes by i.i.d. sampling K distributions {Pr) according to D. These are respec- tively the underlying distributions of K classes;
For each E [K]. i.idd. sample data (in according to P, and denote S {(z,,1, i), .-. (Zi.n, e)}. Note here Tij does not contain the information of label, as its label information is already contained in i. The whole dataset obtained by putting all S; together, i.e.
S" = (S ,t.....,k'''"
We make the following assumption on the correlation between the representation powers of the pre-training and the downstream task.
Assumption 2. Given P, there exists non-negative coefficients vi (P) and vf (P), such that Vh H.
Ed P) < (P)E,, + (P).
We further assume that v8 (P) and uf (P) are stable, that is, there exist two P-dependent positive
constants My and Mf, such that for any P = IT (P,, i) and P' IT (P,,i)" x (Pic K)" which differ by only one component, we have that 1ug (P) - vg (P')) < K
M
and |np (P)
of (PP))
M
Moreover, we assume that vi (P) and (P) concentrate around their means, K.
i.e., there exist ug (D). vf (D), op and CP, such that [B(P) -DKV (P) v/ (D) < c VK
and
E S (() (f) c
VR"
Assumption assumes that the pre-training representation error can bound the downstream represen- tation error, which is common assumption in existing works [6 [6] 3 Also, as P is derived by sampling K distributions according D. make mild assumptions that the coefficients vg (P) and uP (P) is robust when changing the underlying distribution of only one class, and when K grows, the expectation of v/ (P) and of (P) converge to some limits.
5

---

Theorem 3.1. Let Assumptions andd 2 hold. For data generation process with probability over the sampling of the datasets at least 1
have
Ealfsa o hs,, P)s (D) Mi
log 1
C1
5M
log
S +
2G
+ + (D)
2K
VK
2n
vTi
log 2K
Co
log
Mot
+
5M
2V2G
VK
2N
VN
The detailed proof deferred to Appendix 1
Below we simplify the right-hand-side of Equation
D and show that the empirically observed downstream performance trade-off can be explained by such a result.
Simplifying the Theorem
3.1
Denote the RHS of Equation
as U, we have
log 2 2
log a
log 8
U (D)
5M1
2GV2
vn" +
Moo
+
Co
M1
+ +1
2
VK
log
log
5M4
+ 2G
10 (D)
2V22
2N
V
We can see that the above equation can be simplified as
A +
C VN
U
+D,
(2)
where A, B, D do not depend on N, K, n, but instead only depend on the properties of the underlying pre-training and the downstream task data distribution.
that Explaining downstream performance trade-off given fixed N. From Equation we
the performance on the target task would increase when we increase 1) intra-class diversity n, 2) inter- class diversity K, and 3) the size of pre-training dataset N. When N is fixed, however, increasing either intra-class diversity or inter-class diversity would decrease the other (since N = n x K) and therefore eventually lead to performance drop. Another way function of K without n:
this is parameterize U
AVK VN
B
C
U(K)
+ D,
VK
VN
From this we can clearly see that both extremes of K (too large or too small) would not lead to optimal performance. A similar conclusion can be drawn regarding n when parametrizing U as function of without K.
3.3 Balancing intra-/inter-class diversity: the optimal class-to-sample ratio
When N is fixed, by leveraging the fact that N X K, can express U as
Ar + B 1-1
U= NJ
+
3/4
where C. + D is constant and K is the llas-to-sample ratio. To minimize U, we have
VN
a² the optimal class-to-sample ratio 7 - Notably, because both and B have no dependency on N, the optimal class-to-sample ratio for specific downstream task is invariant to the size of the pre-training dataset. Motivated by this, one could estimate the optimal lass-to-sample ratio using small N and then use it to predict the optimal number of classes for building a large pre-training dataset. In particular, given the optimal class-to-sample ratio F. the optimal number of classes is 4 one only needs three (class-to-sample ratio, performance) tuples to estimate the constants (A, B, with fixed N for computing the optimal class-to-sampe ratio.
K = A V... Based on Equation

---

3.4 When no need to balance intra-/inter-class diversity: a contrasting case
So far, we have studied a common practice of collecting the pre-training dataset, iee, first sample K classes and then collect samples for each class, and showed that when the size of the pre-training dataset N is fixed, neither too large nor too small K is optimal. However, there exist other ways of collecting the pre-training dataset. For example, one could collect fixed set of data samples and then manipulate the value of K by clustering the samples into any number of clusters. This raises natural question: is conclusion still valid for this case? To answer this question and further understand the condition for our theory, in this section, we study a contrasting case of the data generation process corresponding the aforementioned example, with which the trade-off no longer exists and, instead, K dominates the downstream performance. Concretely, the data generation process is given as follows:
Data generation process 2. The pre-training dataset is generated by first i.id. sampling data {01, I2, .NN } according to some distribution Px ( We then obtain the label Y: E [K] of each I, by performing clustering. The final pre-training dataset is given as S (1),,))), (Z), (and P is naturally induced).
The new data generation process is different from the one in Section 3.2 In particular, with different K, the new data generation process would not introduce new data samples as we manipulate the label by clustering the current sampled data, while for the data generation process Section 3.2 the sampled data change according to the classes we picked.
As analogy to Assumption we make the following assumption the correlation between the representation powers of the pre-training and the downstream task and then present the theorem.
Assumption 3. We assume the pre-training representation error can bound the downstream rep- resentation error. Specifically, there exists non-negative constants vg (P) and vi (P), such that wh E H.
Ea(h, P) S
+
We further assume that vi (P) and (P) concentrate to their means, i.e., there exist vi (Px), cf
of (Px), of and Cf, such that 1n (P) vi (Px) S cº and (P) (Px)) 7K'
VK
Theorem 3.2. Let Assumptions 1 and 3 hold. For data generation process with probability least
c/ 5M
log
2GV2
CP VK
EalSsa o hhs, P)5 (Px)
8
(
VK)
2N
VN
log 2N
+2V2G 1 V
+ 5Mey
According to Theorem diversity K and the intra-class diversity n. Instead, the bound gets smaller when K is larger. To verify this, conduct experiments under this setting (Figure in in the Appendix A.3) and observe tendency of lower error rate with increasing K.
see that there is no longer a trade-off between the inter-class
A.3
The classes and data samples correspond to two dimensions of diversity. When the size of the pre-training dataset fixed, in the case Theorem 3.1 both diversities would vary in a lee-saw-like way with different K, but for Theorem 3.2 since we fix the data samples used, only one dimension of diversity varies when K is different and therefore the downstream performance only depends on the varying diversity (K). This difference reveals the underlying cause of the downstream performance trade-off rather than relying solely on K and n values.
Discussion.
4 Justification and Application
In this section, we first verify our theoretical findings via empirical results. Then, we show the effectiveness of using the optimal class-to-sample ratio, which is estimated based on our theory with relatively small number of data samples, to build larger pre-training datasets.
7

---

4.1 Are the trade-off curves for different N aligned?
According to our findings in Section 3.3 the test error on downstream task is a convex function
with respect to the class-to-sample ratio (Equation 4) and the optimal class-to-sample ratio こ = 22 is invariant the size of pre-training dataset N. To empirically verify this, visualize the performance on downstream tasks as a function of the class-to-sample to-pll ratio with different N in Figure
50
Wobk
Roat
Text entor rale 189
45
90
Test error rake (19)
88
40
as
50
80
30
78
40-
75
30
72
sample ratio
Class-to sample ratio
Class-to-sampit ratio
(a) CIFARIO
(b) FGVCAirraft
(c) flowers102
90
tel eroor rale (89
75
R-20K
Test rate 199
75
g 85
70
70
80
75
65
60
R-CK
65
55
55
55
50
50
c²
Class sample
Class:
Class-to sample ratio
(d) MIT67
(e) Stanford40
(f) StanfordDogs
Figure 2: Test error rate across class-to-sample ratio. The vertical bar is the standard deviation.
From the figures, we can see that the curves of different N for a specific downstream task are aligned, as well as the optimal class-to-ratios, which follows our theoretical findings. This indicates that empirically, one could extrapolate the optimal class-to-ratio estimated with a small N for building a large-scale pre-training dataset. Note that the rightmost point of each curve corresponds to using all the classes in ImageNet, i.e., K = 1000, and we can see that such a standard design choice does not lead to optimal downstream performance, especially with small pre-training datasets. In addition, conducted experiments with different pre-trained datasets (Appendix (444, different model backbones (Appendix [A.)) and downstream tasks of different domains (Appendix A.5) to demonstrate that our findings are consistent across many scenarios.
4.2 Predicting the optimal number of pre-training classes
As a direct application of our theoretical and empirical findings, one could estimate the optimal class-to-sample ratio with small N and use to decide the optimal number of classes when building a larger pre- pre-training dataset. In particular, denoted by H the optimal class-to-sample ratio, the optimal number of classes for given N is K VEN. We refer to this approach as Extrapolation. We empirically compare it against the following methods of deciding the number of classes when building pre-training dataset: 1) Standard: the number of classes equals 1000 as the standard design choice of ImageNet; 2) Grid Search: the number of classes corresponding to the data point with the lowest error rate for each curve in Figure 2 3) Fitting: given the target size, we use the corresponding data points in Figure to fit the theoretically-derivee performance function (Equation 4 and then analytically calculate the optimal number of classes. We use the calculated number of classes to build a pre- pre-training dataset and measure the performance of a model trained with it. In reality, the latter two baselines require repeatedly training models on pre-training datasets with the target size yet different numbers of classes and are therefore time- consuminn and data-intensiie.
We set the target size of pre-training dataset as | |50K, 100K) and round the number of classes to an integer if needed. For our Extrapolation method, we only use three data points with N being much smaller than the target size to estimate the optimal class-to-sample ratio: N 5000 and K = (10, 50, 200). We use the estimated optimal class-to- ratio for both target sizes. The results as well the number of classes selected by the above methods can be found in Table] I From
8

---

Table 1: Test enror rate on downstream tasks (the first row of each task, lower is better), and the number of classes in the pre- wreitrainin dataset (the second row).
N
Method
Target Dataset
CIFARIO
FGVCAirraft
Flowers102
MTT67
Stanford40
StanfordDDegs
Standard (X(=1000)
29.19
77.80
34.08-a35
57.51sam
62.45
64.96
Grid Scarch
26.242044
75.96anes
32.70_431
54.10g54
57.05 u
59.12,07
(200)
(200)
(500)
(200)
(100)
(200)
50K
Filting
26.25
76.00
32.13-
53.60
57.10
(169)
(293)
(415)
(161)
(138)
(260)
Extrapolation
26.27an2
76, 183014
32 60
53.013031
57.25
60.15
(190)
(168)
(296)
(163)
(134)
(158)
Standard (K 1000)
25.04
52,79g0m
54,6950
$4.70a04
Grid Search
23.13
73,70
27.15-044
50.30a0
51,45503)
$1.98
(500)
(500)
(500)
(200)
(200)
(500)
100K
Fitting
22.67
73.45
26 26.67-633
50.82403
52.245033
52.24
(276)
(372)
(655)
(249)
(207)
(392)
Extrapolation
23.12
73030
26.98_841
10.42
52.32
g3.17
(269)
(238)
(418)
(231)
(190)
(233)
Table 2: Total number of samples used for building the pre-training dataset.
Target Datuset
N
Method
CIFAR1O
PGVCAireraft
Flowers102
MIT67
Stamford40
StanfordDoog
Standard (K-1000)
50K
Grid Search
150K (5 trials)
50K
Fitting
158.164K
161,570K
159.403K
158.694K
159.268K
160.538K
Extrapolation
55,418K
55.183K
55.830K
55.1
54.598K
55.045K
Standard (K=1000)
Grid Search
260K (4 triale)
100K
Fitting
272,336K
2718836
268 164K
269 278K
261.981K
270.579K
Extrapolation
103,937K
103.608K
104.517K
103.515K
103.019K
103,401K
the results, we can that although the ImageNet dataset is widely used, its number of classes (K = 1000) is not optimal for building a pre-training dataset of 50K/100K samples, since the Standard underperforms other methods. Besides, methods except for the Standard all render similar test error rate even though their number of classes are different, which reveals that the performance is pick reasonable number. Thus, Extrapolation
not sensitive to the number of classes as long method is superior to Grid Search and Fitting, since it needs much fewer samples to estimate the number of classes, while both Grid Search and Fitting require building the pre-training dataset of target size multiple times.
4.3 Extra data needed for estimating the optimal class-to-sample ratio
One advantage of the Standard method that it does not require extra data for estimating the optimal number of classes. In contrast, other methods would introduce extra data unused in the final pre- training dataset. For example, when estimating the optimal stass-to-sampl ratio, one may sample data from 1000 classes but eventually find the optimal number of classes is 600, then the data of the additional 400 classes would not be used the final pre-training dataset. We then investigate how much data is needed by different methods to build the final pre-training dataset. We list the total number of samples used by different methods in Table From the table, we can see that Grid Search and Fitting require much more samples than the target size of the pre-training dataset, since they involve building the pre-training dataset of the target size multiple times, while the number of extra data needed by Extrapolation is relatively small, because it estimates the optimal number of classes using a small N of 5000. In addition, using Extrapolation, one only needs to estimate the optimal dlass-to-sample ratio once and then use it for building pre-training datasets with different sizes without re- estimation.
As the Extrapolation requires more data than the Standard, fairer comparison between them needs to ensure the total number of data used is similar, and the Standard would have a slightly larger pre-training dataset since it does not spend any data budget for estimation. In Figure we compare

---

the Extrapolation to the Standard whose pre-training dataset size is slightly larger than the total number of data used by the Extrapolation. Each bar plot represents specific downstream task, and the number in parentheses indicates the size (N) of the corresponding pre-training dataset. We can observe that in most cases, the Extrapolation demonstrates improved performance over the Standard even when the latter uses a larger pre-training dataset, which further justifies the effectiveness of the Extrapolation method.
CIFARIO
FGVCAircraft
Flowers102
Testt effor rate (%)
80
Test error rate (%6
-30
70
60
Standara (104k)
Extrpptaation (1o0m)
Standara
[5eK)
Extrapelare Exrapelation
(50K)
Standard
(104))
Extrepstation
(1b0k)
Standard (Sek)
Extepstant torapstation (30K)
Standard (104k)
Extrapatanie
Standard (Sck]
Extrapeton Inrapetation (30X)
MIT67
Stanford40
StanfordDogs
Test error rate (%0
Text error rate (%)
53
60
50
50
Test
Standare (104K)
Extrapatation
Stanaad (58K)
Exrapalation
Stardarrs (104K)
Intrpotation (100K)
Standari (5ek)
Extrapdiation (oC
Standard (104k)
Extrapatation (baRk)
Standard (56K)
Enrapalation
(ook)
(50K)
(90K)
Figure 3: Each bar plot visualizes the error rates different methods on a specific downstream task. The number in parentheses is N, i.c. the size of the corresponding pre-training dataset.
Related Work
We briefly review recent studies on supervised pre-training from data-centric perspectives. First, on the composition of the pre-training dataset, [ presents a scaling law that predicts the test loss on downstream tasks under varying source dataset compositions, while [14] studies the performance on downstream tasks when subsets the pre-training dataset are removed. Second, on the label space of supervised pre-training, (26) offers a statistical analysis explaining pre-training techniques' success NLP, showing that class diversity in pre-trainnn pre-training tasks substantially enhances sample efficiency in downstream tasks, while the study by [12 explores the impact of pre-training label granularity downstream tasks, emphasizing the importance of selecting an appropriate level of label granularity. transfer performance, finding the choice the pre-training dataset to be crucial. In contrast, we dive into the trade-off of the intra-/inter-class diversity in the supervised pre-training dataset. The study related the most to is 13, where the authors empirically examined the importance pre-training data characteristics on downstream performance. While covering wide range of pre-training data characteristics, this study only briefly explores the trade-off of intra-/inter-class diversity in the pre-training dataset (Section 5.5 in (13). Specifically, the authors only considered different cases of intra-/inter-class diversity, i.e., K = {500, 1000} for ImageNet. In contrast, we, both empirically and theoretically. show how such a trade-off would impact the downstream performance and our theory uncovers surprising property of the optimal class-to-samee -aample ratio: it is invariant to the size of the pre- pre-training dataset.
Lastly, 77] explores the impact of pre-training data distribution
Conclusion
In this study, we explore the trade-off of the intra-/inter-llas diversity in supervised pre-training datasets of fixed size. We discovered that the optimal downstream performance is achieved through balance of intra-finter-class diversity. Our theory demonstrates that downstream performance depends on both diversities, and the optimal class-to-sample ratio remains constant regardless of the dataset size. We apply this finding to predict the optimal number of classes pre-training datasets and provide evidence of its effectiveness across many scenarios.
10

---

References
[1] Jean-Baptiste Alayrac, Jeff Donahue, Pauline Lue, Antoine Miech, lain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katie Millican, Malcolm Reynolds, et al. Flamingo: visual language model for few-shot learning. Advances in neural information processing systems, 2022.
[2] Peter I. Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normaliza margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
[3] Shuxiao Chen, Koby Crammer, Hangfeng He, Dan Roth, and Weijie J Su. Weighted training for cross-task learning. In International Conference Learning Representations.
[4] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPR09, 2009.
[5] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 1929, 2020.
[6] 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. 2021.
[7] Rahim Entezari, Mitchell Wortsman, Olga Saukh, M. Moein Shariatnia, Hanie Sedghi, and Ludwig Schmidt. The role of pre-training data in transfer learning, 2023.
[8] Samir Yitzhak Gadre, Gabriel Ilharco, Alex Fang. Jonathan Hayase, Georgios Smyrnis, Thao Nguyen, Ryan Marten, Mitchell Wortsman, Dhruba Ghosh, Jieyu Zhang, et al. Datacomp: In search of the next generation of multimodal datasets. arXiv preprint arXiv:2304. 1414,,110,, 2023.
[9] Tatsunori Hashimoto. Model performance scaling with multiple data sources. In International Conference on Machine Learning, 2021.
[10] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and paltern recognition, pages 770-778, 2016.
[11] Danny Hermandez, Jared Kaplan, T.J. Henighan, and Sam McCandlish. Scaling laws for transfer. ArXiv, abs/2102.01299 2021.
[12] Guan Zhe Hong, Yin Cui, Ariel Fuxman. Stanley H Chan, and Enming Luo. Towards under- standing the effect of pretraining label granularity. arXiv preprint arXiv:2303. 16887, 2023.
[13] Minyoung Huh, Pulkit Agrawal, and Alexei A. Efros, What makes imagenet good for transfer learning? ArXiv, hhss/1608.08/// 2016.
[14] Saachi Jain, Hadi Salman, Alaa Khaddaj, Eric Wong, Sung Min Park, and Aleksander Madry, data-based perspective on transfer learning. 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2023.
(15) Aditya Khosla, Nityananda Jayadevaprakash, Bangpeng Yao, and Fei-Fei Li. Novel dataset for fine-grained image categorization: Stanford dogs. In Proc. CVPR workshop on fine- grained visual categorization (FGVC), volume 2. Citeseer, 2011.
[16] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[17] Dhruv Mahajan, Ross B. Girshick, Vignesh Ramanathan, Kaiming He, Manohar Paluri, Yixuan Li. Ashwin Bharambe, and Laurens van der Maaten. Exploring the limits of weakly supervised pretraining. In Vittorio Ferrari, Martial Hebert, Cristian Sminchisescu, and Yair Weiss, editors, Computer Vision ECCV 2018 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part II, volume 1 12006 of Lecture Notes Computer Science, pages 101. Springer, 2018
11

---

[18] S. Maji, J. Kannala, E. Rahtu, M. Blaschko, and A. Vedaldi. Fine- Fine-grained visual classification of aireraft. Technical report, 2013.
[19] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[20] Maria-Elena Nilsback and Andrew Zisserman. Automated flower classification over large number of classes. In 2008 Sixth Indian Conference on Computer Vision, Graphics & Image Processing, pages 722-729. IEEE, 2008.
[21] Xingchao Peng, Qinxun Bai, Xide Xia, Zijun Huang, Kate Saenko, and Bo Wang. Moment matching for multi-source domain adaptation. In Proceedings of the IEEE/CVF international conference on computer vision, pages 1406-1415, 2019.
[22] Ariadna Quattoni and Antonio Torralba. Recognizing indoor scenes. 2009 IEEE conference on computer vision and pattern recognition, pages 413-420. IEEE, 2009.
[23] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pages 8748-8763. PMLR, 2021.
[24] 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
(153))111 2015.
[25] Bangpeng Yao, Xiaoye Jiang, Aditya Khosla, Andy Lai Lin, Leonidas Guibas, and Li Fei-Fei. Human action recognition by learning bases of action attributes and parts. In 201 International conference on computer vision, pages 1331-1338. IEEE, 2011.
[26] Yulai Zhao, Jianshu Chen, and Simon S Du. Blessing class diversity pre-training. Interna- tional Conference on Artificial Intelligence and Statistics, 2022.
[27] Bolei Zhou, Agata Lapedriza, Aditya Khosla, Aude Oliva, and Antonio Torralba. Places: A 10 million image database for scene recognition. IEEE transactions on pattern analysis and machine intelligence, 40(6): 2017.
12

---

A Appendix
A.1 Limitation and Potential Negative Social Impact
Some potential negative societal impacts might arise from this research, such as:
Bias Amplification: When the research discusses the optimal class-to-sample ratio in pre-training datasets, it does not discuss how these classes are determined. There's s a risk that the choice classes and the samples within these classes could reflect and perpetuate existing biases in society. For instance, if the classes are determined by stereotypical or biased criteria, models trained on these datasets could amplify these biases their predictions recommendations.
Overemphasis on Quantity over Quality: This research might also create an overemphasis on the quantity (size and diversity) of the data at the expense of its quality. Poor data quality could lead to the development of inaccurate or unreliable machine learning models.
A.2
Experimental Details
A.2.1 Training Details
We build our code Python and Pytorch. We fix the model to be the ResNet-18 [0]]. For pre-training. we set the number of epochs to be 100 and the batch size to be 64. We use the Adam optimizer for training with learning rate of 0.1, momentum of 0.9, and weight decay of le-4. We repeat each experiment 3 times with different seeds and report the mean and variance of the results. All experiments
machine with Intel(R) Xeon(R) CPU E5-2678 v3 with 512G memory and two 48G NVIDIA RTX A6000 GPUs.
A.2.2 Details of Dataset
The Pre-training Dataset:
ImageNet [4) is an image dataset organized according the WordNet hierarchy. Each meaningful concept in WordNet, possibly described by multiple words or word phrases, is called "synonym set" or "synset". There are more than 100,000 synsets in WordNet; the majority of them are nouns (80,000+).
Place365 225 It has 1,803,460 training images with the image number per class varying from 3,068 to 5,000. The validation has 50 images per class and the test has 900 images per class.
The Downstream Tasks Dataset
Stanford Actions 40 25 It contains images of humans performing 40 actions. There about 180-300 images per class. We do not bounding boxes and other annotation information for training. There are total of 9,532 images, making it the smallest dataset in our benchmark experiments.
Stanford Dogs 120 [1). It contains images of 120 breeds of dogs worldwide. There precisely 100 examples per category in the training set. is used for the task of fine-grained image categorization. We do not the bounding box annotations. There total of 20,580 images.
MIT Indoors 67 [22] It is a scene classification dataset containing 67 indoor scene categories, each consisting of 80 images for training and 20 for testing. Indoor scene recognition is challenging because spatial properties, background information, and object characters expected to be extracted. There are 15,620 images in total.
CIFAR10 [6]. It is collection of images commonly used train machine learning and computer vision algorithms. contains 60,000 32x32 color images in 10 different classes. The ten classes represent airplanes, cars, birds, cats, deer, dogs, frogs, horses, ships, and trucks. There are 6,000 images of each class.
Flowers102 20 It is an image classification dataset consisting of 102 flower categories. The flowers chosen be flowers commonly occurring in UK. Each class consists of
13

---

between 40 and 258 images. The images have large scale, pose and light variations. In addition, some categories have significant variations within the category and several very similar categories.
FGVCAircraft 18] It contains 10,200 images of aircraft, with 100 images for each of 102 different aircraft model variants, most of which are airplanes. Each image's (main) aircraft is annotated with tight bounding box and hierarchical airplane model label. Aircraft models are organized in four-level hierarchy.
DomainNet-real and Domainnet-paintinng 21]. DemainNet-real and DomainNet-paintinn belong to real and painting domains, respectively, and both comprise 345 categories. DomainNet-real contains over 170k images, while DomainNet-painie has more than 70k images.
A.3
Empirical Verification of Theorem 3.2
95
Test error rate (96)
60
N=20K
Test error rate (%)
80
N--00
90
N=200K
Test rate
70
N=200K
85
60
40-
50
80
40
75
30
e-
6- 8a
e
e-
6
e- e²
Class-to-sample ratio
Class-to-sample ratio
Class-to-sapple ratio
CIFAR10
FGVCAireraft
(c) Flowers
N-2K
Test error rate (96)
85
N-10K
Test error rate (%))
80
N=100K
N100K
80
75
70
N-SK
60
65
N-10C
60
60
N-20C
NebpC
55
N=1055
e-6 e-4 e-2 eº
e*
e e-f e-
8
6
e
e-f e-
e² e* e
Class-to-sample ratio
Class-to-sample ratio
Class-to-sample ratio
(d) MIT67
(e) Stanford40
(f) StanfordDogs
Figure 4: Test error rate across class-to-sane to-sample ratio. The vertical bar each point the standard deviation.
As shown in Figure 4 can find that, across all datasets, the results generally showed decreasing trend in test error rate as the class-to-sample ratio increased. This empirically supports the theoretical assertion that there is no downstream performance trade-off caused by the inter-class diversity K and the intra-class diversity n. Instead, the downstream performance improves with increasing K, as suggested in Theorem 3.2
A.4 Experiments on Places365 as Pre-training Dataset
We use the Places36.5 27 for our pre-training and the result is represented in Figure 5 We then performed evaluations on same batch of downstream tasks as the main body of the paper to demonstrate the trade-off between intra- and inter-class diversity is consistent with our main findings.
14

---

96
fwb
90-
He5K
85 error rate (%)
rate (%)
85
N--0K
92
80
50
90
75
70
45
65
40
60
64
82
50
e e²
e
e²
e
e
e²
et
Class-to-sample ratio
Class-to-sample ratio
Classto-sample ratio
(a) CIFAR10
(b) FGVCAireraft
(c) Flowers102
90
ho5k
96
K-5K
Test error (%)
85
(96)
94
gr rate
92
75
80
90
88
86
60
70
84
e 1-
e"
e
e 6 e
e"
6
e e
e
et
e*
Class-to-sample ratio
Class-to-sample ratio
Class-to-sample
(d) MIT67
(c) Stanford40
(f) StanfordDogs
Figure 5: Test error rate across class-to-sample ratio. ResNet-18 18 pre-trained on the Places365 dataset.
75
N=5K
N=5K
N-10K
N- 10K
84-
Test error rate (%)
70-
@ 82
Test error P
80
65
78
60
74-
72:
e
e-
e0
e²
e-
e
e
e
e4
e
Class-to-sample ratio
Class-to-sample ratio
(a) DomainNet painting
(b) DomainNet
Figure 6: Test eтrоr rate across class-to ta-pl ratio. ResNet- 18 pre-trained on ImageNet and tested on two datasets of different domains from the DomainNet benchmark.
A.5 Experiments Downstream Tasks of Different Domains
As illustrated in Figure 6 we test models trained on ImageNet on two distinct domains (painting and real images) sourced from the DomainNet benchmark [2] and the result indicates that our conclusions do not change with different downstream task datasets.
A.6 Experiments VIT Model Backbone
To ensure conclusions are not restricted to specific model architecture, we use ViT-B-16 model S as the backbone model. The results Figure show that different model backbone does not change the conclusions we derived.
15

---

52
95
75
Test error rate (86
72
70
93-
er
65
Test
62
60
92
58
6-3
end
e
e²
e
e-
e
e²
Clas-toossample ratio
Class to sample ratio
Class-to-sampie ratio
(a) CIFARIO
(b) FGVCAireraft
(c) Flowers102
N=SC H=10C 20
88
N=SK
N=106
93
R3: error rate (80)
92
86
91
84
90
enror
89
82
88
78
80-
87
N-10c
86
e
6
ea
ratio
Class-to sample ratio
Class to sample ratio
(d) MIT67
(c) Stanford40
(f) StanfordDogs
Figure 7: Test error rate across saaslee ratio. ViT-B-16 pre-trained on the ImageNet dataset.
Table 3:
Actual v.s. predicted test rate downstream tasks according Equation
Target Dataset
N
Method
CIFARIO
FGVCAireraft
Flowers102
MIT67
Stanford40
StanfordDogs
Predicted
33.13
75.95=04
32.96.0.
53.99
56,72a0.1
28.8720.5
50K
Actual
26.25aa47
76.00a044
32.13
03.60=039
$7.10=03
59.76 20.26
Predicted
22.842040
73.52a041
27.3320.0
50.15=04:
51.74
$1.69
100K
Actual
22.67
73.45
26.672001
50.82:031
52.24
52.2420.1
A.7
Actual v.s. Predicted Performance of Fitting Equation 4
In Section we study the performance of the Fitting method, i.e., using the optimal number of classes derived from the function fitting Equation Given the fitted function, the test error given a specific value the number of classes. Here, we compare the actual test error of the derived number of classes (the Fitting entry of Table I with the one predicted by the fitted function, in order to see whether our theory offers an accurate prediction performance. From results presented in Table 3
also predict
that the actual test error (Actual) is similar to the test error predicted by the fitted function (Predicted), this further proves the utility of our theory.
A.8 Proofs of Thcoretical Results
A.8.1 Proof of Theorem 3.1
Before we formally state the proof of Theorem 3.1 we define several notations as follows:
hp A arg min (h, P), NEw
fp A arg min Uni [ hp(x),
Proof of Theorem 3.1 Step I. Bound (pss,, P).
hhtt:///laaces2.csall www.:/ssaaaaiii.cc..
"htt::/ai..uueee http:/aii.b..dd/MMSSS.A
16

---

Ep(hso, P) can be decomposed into
Ep(hsr, RRy(se (hphss P)
min Ry P)
hCHt
Ry(hsr, P)
{fss (ar())))
nk
K
K
e(Ssr hip (2is),))))
Σ nk
(elfo ((())))(()))))))
nk
i=
K
1
(e(fr o hp((is)) ()) - Rp(hp, P))
nk
We tackle the three terms of the RHS of the above inequality respectively. As for the first term, since
Rps P) = min (nff [e(f hg (z). i)]
feF
{B [C(ssp hip (1)) i)]
we have that the first term can be bounded by
K
Ry(ss, P)
(Ssr lisp (1).).
< BBathitt
((ffr [((fs> hsp (s) (x),
1
Σ
{fsr har (xLs),
nk
1=1
sup fET,NEN
(L M(x),
((f o h(os),))))))))))
nk
Applying Gaussian complexity to EE=( Σ {(f ([foh([sj)))))) 1)), we obtain that with probability at least 1 - 8, the RHS of the above inequality is smaller than
9 log
M
+ 2E (( pny ~N0.
sup
Σ o
elf h(xus))
2n
JEF n
j=1
<Mi
9 log
2
K
E -pp ~N0.
sup Σ JEFN
ajlls o h()
2n
K
1=1
s=1
9 Log
2
SMey
+
Σ
E E و -eg.er/eee.e..e..e..............
sup JEFNEN 1ml
oyafi o h(aa.)
2n
9 log
<Ma
2G
2n
Vn
Here the second inequality is due to Slepian's Lemma, and the last inequality is due to Assumption) 1 All all, with probability at least ô,
8, the first term can bounded as
K ΣΣ
9log 1
Ry(hiv, P)
ASss o hse (x)5),)) < Mr
2GV2
n.K
2n
Vni
Mcanwhile, the second term is non-positive due to the optimality of fs- and hsr.
17

---

Finally, the third term can be bounded as
K
(e(fr o hp(2))))
Rpllip p))
nk
K
hp())))( E..ttat//K)2- [(fp hp(x), i)]
nk
1-p.1-6 2
log
Mc
n
where the last inequality due to Hoeffding's inequality. As a conclusion of Stage we obtain that with probability at least - 26,
log 8 + 2n
2GV2
(pss,, S 5M
vn
Step II. Bound (. Applying Assumption
2
we obtain that with probability at least
25,
log J
2GV2 +
Ea(hs,, s (P) ( (p)
(n)
+ 1/ (P).
2n
vn
By McDiarmid's inequality, we obtain that with probability at least 1-8.
log 1 2K
log 3
Co. VK
(P) < EP-DKY (P) Mo
S v (D) vD((D)) + Mo
+
2K
Similarly, with probability at least 1 - 5,
log á 2K
log C1
(P() < Ep + Mi MiV
< v (D) + MiV
2K
VK
As conclusion, we obtain that with probability at least 46,
(hsp P)
log 5
Ci VK
log
2G + Vn
log } Co
(D)+ + Miy < vi (D)
5Me
+ + (D) + +Mo
2K VK"
Step III. Bound Rs hsp Sp)
Rhs P) Finally, denote f3 arg min min jer Ralf h, P) based on Hoeffding's inequality, we obtain that with probability at least 1 - 5, Ra(Jsa hs,, Sp) Ra(hs, P) <Ro hs, P)) Ra(hs, P)
min
2 2 1
<May
Meanwhile, applying Gaussian's ' inequality, have that with probability at least 8,
Ra(Ssa hs, P) RalJsa Sp)
9 2N
<2R 1 200
sup JEF
all h(x)).))) Mey
N
N
9 glog 1o2
<2V2E waw.s//w.......aaaeeeeeeae.....
sup JEF
osaff h((x)) + Mel
2Ñ
i=1
S2GV2 1 + Mey
9 log 1
VN
2N
18

---

where the second inequality is due to Slepian's 's Lemma, and the last inequality is due to Assumption
All in all, we have with probability at least - 66,
Ea(Sso hs,;?) P)
=Eahh P) + Rolfsa hsp, P) Ra(fss o hs,, Sp) + Ralfsa o hsp, - Ra(hs,, P)
( 5.Mey
< (P(D) + MiV
log
C1
log 2n
2GV2 +
log
Co.
+ + (D) + Mo
+
2K
VK
vn
2K
VK
log
+ 5Mp
2V2G
2N
VÑ N
The proof is completed.
A.8.2 Proof of Theorem 3.2
Proof. Denote
hp a arg min (h),,, NEH
fo 2 arg min B( [f[ (x).
1
Step I. Bound (psrr)
Denote (hso)) can be decomposed into
Ep(1gr) -Rp(hsr) hEH
min (h)
N Ry(ho))= Σ
E(fsv o hsv (ss((z)).
1 N
((fsv hSp (2.).
Σ
(l(fo (ppl))))
N
(Elfp h v()) - Rp(hp))
+
N
We tackle the three terms of the RHS of the above inequality respectively. As for the first term, since
(hsh))) = min [(e o hs- (x), S (eteg)>o(((sss hss (c),
PEF
we have that the first term can be bounded by
Rysh)
N Σ UlSr (1s( v:)
N Σ
<B(a (x),
(SSor hig (2:).
N
1=1
< sup JEF,
1
Σ {(f o l((x))
N
19

---

Applying Gaussian complexity to E l(f h(z4), we obtain that with probability at least 1 6, the RHS of the above inequality is smaller than
9 log 8
n ofe(f o ((2)).8)))
Mc
+ 2E (a:)
sup SETH
2NV
9 9lgg 2N
VMV
+ +2
(..)) (m Blo www...eeeeeeeeedaoooooooooo aime)))
sup JEFAEH
وز h(r;))
1=1
9og 3
+ 2GV2 1
SMp
2N
VN
Here the first inequality is due to Slepian's lemma, and the last inequality is due to Assumption 1 in all, with probability at least 1-8. the first term can be bounded as
All
9log 2N
Rp(hs²) E ((fs (gs S Mey
+ 2GV2
VN
Mcanwhile, the second term is non non-positive due to the optimality of fs* and hss.
Finally, the third term can be bounded
N
E(fr o hp(x:)) - (ppp))))
L(fr o hp(x:) - E(z.)) (x)))
N
w.p.1-
2 log !/
Mey
N
where the last inequality is due to Hoeffding's inequality. As a conclusion of Stage I, we obtain that with probability at least 1- 28,
log 2GV2 2N VN
Epsh, 5
Step II. Bound Ed(hsr). Applying Assumption 3
obtain that with probability at least 25,
Ea(hsr, =f (/( < (P(
(5Me|
log
2G
+ $ (P).
2N
Furthermore, as 1n8 - (Px) - c / and
-
(Pxx) S
C³ KK'
we obtain that with
probability at least 1 - 28
cP p (Px) +
log
2G +
CP VK
Ea(hso, P) <
5.M
+ + +
VK
2NV
VN
The rest of the proof flows exactly the same as that of Theorem
3.1
20


Reviews:
[{"review_id": "ptzfuC1wR9", "reviewer": "Reviewer_xyoX", "summary": "This work studied the impact of the trade-off between the intra-class diversity (the number of samples per class) and the inter-class diversity (the number of classes) of a supervised pre-training dataset. The authors found that with the size of the pre-training dataset fixed, the best downstream performance comes with a balance on the intra-/inter-class diversity and show that the downstream performance depends monotonically on both types of diversity theoretically.", "questions": "* Can authors elaborate line 195: \"obtain the label $y_i$ for each $x_i$ by performing clustering.\", for example, which clustering method was used? what is the input/feature for clustering algorithm?", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The claims over how intra-class diversity and the inter-class diversity affect downstream tasks' performance were well supported by the empirical results, i.e., Fig. 1.\n\n* The authors provided a theory on the impact and verified the theoretical findings via empirical results.", "weaknesses": "* The study was limited to fine-tuning on classification tasks only, other types of tasks, such as detection and segmentation, were not covered.\n\n*  Though ResNet-18 is a classic architecture, it became less popular recently. It remains unclear if the same conclusion holds for other models (e.g., ViT) empirically.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">W1:  *The study was limited to fine-tuning on classification tasks only, other types of tasks, such as detection and segmentation, were not covered.*\n\nThis is a good point, our current study(theory) focuses on(supports) classification tasks and we would like to leave the exploration of other types of downstream tasks to the future work. We would update the paper to point out these directions of future work.\n\n>W2:   *Though ResNet-18 is a classic architecture, it became less popular recently. It remains unclear if the same conclusion holds for other models (e.g., ViT) empirically.*\n\nWe added new experiment results regarding the ViT model (please find the **Figure R2 in the general rebuttal**) and our main findings still hold for the ViT model. \n\n>Q1: *Can authors elaborate line 195: \"obtain the label y_i for each x_i by performing clustering.\", for example, which clustering method was used? what is the input/feature for clustering algorithm?*\n\nThanks for asking and we clarify the clustering method below both experimentally and theoretically below.\n\n**Experimentally**: We performed the K-means clustering algorithm on the embeddings of the 1,000 labels of ImageNet, where the label embeddings are obtained from the ConceptNet database (it includes label embeddings corresponding to the labels of ImageNet). Then the samples in ImageNet can be split into K clusters based on the obtained clusters of labels.  We will add more details about clustering to the revised version. \n\n**Theoretically**: Our theoretical result does not depend on the type of clustering method employed, and can apply to standard clustering methods such as K-means clustering and spectral clustering.   \n\n"}, {"review_id": "ObJNxqZ2RX", "reviewer": "Reviewer_Ypk9", "summary": "The paper presents a detailed analysis on the intra-class diversity and inter-class diversity when you have a fixed dataset size. The authors develop some theoretical rule based on empirical results.", "questions": "- Why not add another pre-training dataset to the mix?\n- What happens when pre-training distribution doesn't match well with downstream dataset?", "limitations": "- Analysis restricted to ImageNet pretraining.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Provides a rigorous study on pretraining using ImageNet, that makes the empirical motivation clear for theoretical result.\n- Theory is relatively well-explained in a step-by-step manner.\nProposes a method to balance intra-class and inter-class diversity, which leads to better performance on downstream tasks.\n- The paper is well-structured and easy to follow.\n- As we move towards a more data-centric view of deep learning, analysis of the composition of a dataset and how to best create a new dataset is a welcome area of research. This paper is one in this new area and sets a relatively decent standard for what should be done.", "weaknesses": "- All of the experiments are based on using ImageNet as the pretraining dataset. This makes me uncertain of whether the result relates to ImageNet only, as there are particularities in relation to dataset acquisition, labelling, diversity between samples in a class etc. that makes ImageNet unique. Another pre-training dataset would be very welcome and I think perhaps a needed addition to this paper.\n- The paper seems like it is inspired by What Makes ImageNet Good for Transfer Learning by Huh et al, 2016; and this paper beyond just studying the trade-off between intra/inter-class diversity, actually ended generating a theoretically and empirically grounded rule for dataset construction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">W1/Q1: *All of the experiments are based on using ImageNet as the pretraining dataset. This makes me uncertain of whether the result relates to ImageNet only, as there are particularities in relation to dataset acquisition, labelling, diversity between samples in a class etc. that makes ImageNet unique. Another pre-training dataset would be very welcome and I think perhaps a needed addition to this paper. Why not add another pre-training dataset to the mix?*\n\n\nWe added new experiment results regarding using another dataset (Places365) as the pre-training dataset, and we can still observe the diversity trade-off and the aligned optimal class-to-sample ratio. Please find the details (**Figure R1**) in the general rebuttal.\n\n>W2: *The paper seems like it is inspired by What Makes ImageNet Good for Transfer Learning by Huh et al, 2016; and this paper beyond just studying the trade-off between intra/inter-class diversity, actually ended generating a theoretically and empirically grounded rule for dataset construction.*\n\nThe \"What Makes ImageNet Good for Transfer Learning\" paper (referred as [1])  empirically examined the importance of a wide range of pre-training data characteristics on downstream performance. In contrast, we provide in-depth study and theory regarding a specific aspect, the trade-off between intra/inter-class diversity. Besides, we come up with a theoretically and empirically grounded rule for dataset construction in addition to studying the diversity trade-off. That is, one could estimate the optimal class-to-sample\nratio using a small N and then use it to predict the optimal number of classes for building a large pre-training dataset. We do have a paragraph in the related work section to discuss the connection of [1] and our study.\n\n[1] What Makes ImageNet Good for Transfer Learning. Huh et al, 2016.\n\n>Q2: *What happens when pre-training distribution doesn't match well with downstream dataset?*\n\nIn the general rebuttal (**Figure R3**), we added results of using dataset from painting domain (DomainNet-painting) as the downstream task (while the pre-training dataset used can be seen as from real image domain). We can see that although the two domains have different distributions of the data samples, we still observe the diversity trade-off and the aligned optimal class-to-sample ratio.\n\n"}, {"review_id": "MKZXsRUVlf", "reviewer": "Reviewer_AXB6", "summary": "This paper provides empirical study and theoretical analysis of the class-to-sample ratio in supervised pre-training datasets.", "questions": "1. Would other datasets affect the conclusion drawn.\n2. Would other larger models and vision transformers lead to the similar observation and conclusion?\n3. Would similar observation holds on larger downstream datasets or downstream datasets of other domains?", "limitations": "See weakness and questions.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This papers reveals an important conclusion - the optimal class-to-sample ratio is invariant to the size of the pre-training dataset. This can be utilized as a guidance of the data size for the scaling law in pre-training.\n2. Detailed theoretical analysis are provided, from which a guidance of choosing the class-to-sample ratio is also provided. ", "weaknesses": "1. The pre-training dataset is restricted to ImageNet. \n2. The model ResNet18 used is relatively small and may not reveal the true conclusion. \n3. The evaluation is restricted to only 7 small downstream datasets. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "In the general rebuttal, we added new experiments regarding the three weakness points/questions: using different pre-training dataset (**Figure R1**), using different model architecture (vision transformer, **Figure R2**), and using larger downstream datasets or datasets from other domain (painting domain, **Figure R3**). From the results, we observed that our main findings (the diversity trade-off and aligned optimal class-to-sample ratio) still hold for these different setups. Please find the details in the general rebuttal and we hope that your concern can be addressed by the new experiments."}]

Author rebuttal:
We thank all of the reviewers for their thoughtful feedback. Based on reviewers’ feedback and questions, we add several experiments and the results can be found in the attached PDF. In particular, we plot the curves of test error rate on downstream tasks across different class-to-sample ratio (similar to the Figure 2 of the main paper) for the following settings:

- **Figure R1: using the Places365 [1] dataset as the pre-training dataset.**  Based on reviewer Ypk9 and AXB6’s suggestion for experiments on an additional pr-etraining dataset, we pre-trained ResNet-18 on a new pre-training dataset, Places365, and tested the pre-trained models on downstream tasks;

- **Figure R2: using the ViT model.** Based on reviewer xyoX and AXB6’s comment on experimenting with other model like ViT, we pre-trained ViT-b-16 on the ImageNet dataset to show the diversity trade-off for models other than ResNet;

- **Figure R3: using larger/other domain datasets as downstream tasks.** Reviewer xyoX and AXB6 requested for experiments on other downstream tasks, so we tested ResNet-18 pretrained on ImageNet on two new downstream tasks from the DomainNet benchmark [2]: DomainNet-real and DomainNet-painting. They are from real and painting domains respectively and both have 345 categories. The DomainNet-real has >170K images and the DomainNet-painting has >70K images.

We focus on the test error rate across the class-to-sample ratio figure because it can demonstrate the trade-off of the intra-/inter-class diversity and show that the optimal class-to-sample ratio of different Ns are aligned, which is the main findings of this paper. From the figures, we can see that 1) overall, the largest and smallest class-to-sample ratio would not lead to the best test error rate, which indicates the diversity trade-off exists for these different settings; and 2) the best class-to-sample ratio for different Ns in the same setting are generally aligned, which reinforces our main findings in the paper. 

[1] Places365 dataset: http://places2.csail.mit.edu/

[2] DomainNet benchmark: http://ai.bu.edu/M3SDA/

Meta-review: The paper performs an analysis of the class-to-sample ratio in pretraining datasets. They propose a theoretical analysis based on generalization error bounds, as well as experiments, that conclude that the optimal class-to-sample ratio might remain constant across pre-training dataset sizes.

There is no clear consensus among reviewers on the exact novelty of the paper, but the main weaknesses -- single dataset, small model, and small downstream datasets -- have been partly cleared by the rebuttal and the reviewers agree that the in-depth theoretical analysis is new.

The paper is borderline but I feel the topic is important and timely. I accept the paper assuming there is a chance this type of analysis, joining theory and experiments, can be broadened and deepened and yield actionable insights at larger scale.
Decision: Accept (poster)