Understanding Few-Shot Learning: Measuring Task Relatedness and Adaptation Difficulty via Attributes
Authors: Minyang Hu
Hong Chang
Zong Guo
Bingpeng Ma
Shiguang Shan
Xilin CHEN
Venue: NeurIPS 2023 poster (2023)
Keywords: Few-shot Learning
Meta-Learning
Task Relatedness
Task Adaptation Difficulty
TL;DR: We propose a novel distance metric, called Task Attribute Distance (TAD) to measure the task relatedness and we derive a generalization error bound of a novel task with the proposed TAD metric

Abstract: Few-shot learning (FSL) aims to learn novel tasks with very few labeled samples by leveraging experience from \emph{related} training tasks.
    In this paper, we try to understand FSL by exploring two key questions:
    (1) How to quantify the relationship between \emph{ training} and \emph{novel} tasks?
    (2) How does the relationship affect the \emph{adaptation difficulty} on novel tasks for different models?
    To answer the first question, we propose Task Attribute Distance (TAD) as a metric to quantify the task relatedness via attributes.
    Unlike other metrics, TAD is independent of models, making it applicable to different FSL models.
    To address the second question, we utilize TAD metric to establish a theoretical connection between task relatedness and task adaptation difficulty.
    By deriving the generalization error bound on a novel task, we discover how TAD measures the adaptation difficulty on novel tasks for different models.
    To validate our theoretical results, we conduct experiments on three benchmarks.
    Our experimental results confirm that TAD metric effectively quantifies the task relatedness and reflects the adaptation difficulty on novel tasks for various FSL methods, even if some of them do not learn attributes explicitly or human-annotated attributes are not provided.
    Our code is available at 
    \href{https://github.com/hu-my/TaskAttributeDistance}{https://github.com/hu-my/TaskAttributeDistance}.

Understanding Few-Shot Learning: Measuring Task Relatedness and Adaptation Difficulty via Attributes
Minyang Hu 1.2 Hong Chang Zong Guo 1.2, Bingpeng Ma², Shiguang Shan 12, Xilin Chen 1,2
Institute of Computing Technology, Chinese Academy of Sciences University of Chinese Academy of Sciences (minyang.hu, zong-guo] @aanggguoo@@ulllllllll @vipl.ctt.cccnn (changhong, sgshan, xlchen) @ict.ac.cn, bpma caaaauucaacccooo
Abstract
Few-shot learning (FSL) aims to learn novel tasks with very few labeled samples by leveraging experience from related training tasks. In this paper, we try to understand FSL by exploring two key questions: (1) How to quantify the rela- tionship between truining and novel tasks? (2) How does the relationship affect the adaptation difficulty novel tasks for different models? To answer the first question, we propose Task Attribute Distance (TAD) as a metric to quantify the task relatedness via attributes. Unlike other metries, TAD is independent of models, making applicable to different FSL models. To address the second question, we utilize TAD metric establish theoretical connection between task relatedness and task adaptation difficulty. By deriving the generalization error bound on a novel task, discover how TAD measures the adaptation difficulty novel tasks for different models. To validate our theoretical results, we conduct exper- iments on three benchmarks. Our experimental results confirm that TAD metric effectively quantifies the task relatedness and reflects the adaptation difficulty on novel tasks for various FSL methods, even if some of them do not learn attributes attributes are not provided. Our code is available at explicitly or myTTTasktAtttrruutttsst Itttp:://gthhu..cmmm cow/hu
Introduction
Learning in human biological system is highly efficient compared artificial systems. For example, only one example is enough for a child to learn a novel word (9, while thousands of training samples are needed for deep learning models. This learning efficiency comes from the past experiences accumulated by human brain. Inspired by human learning capability, Few-Shot Learning (FSL) aims learn novel tasks with very few samples by leveraging experience from related training tasks.
Despite the great progress made in FSL during the past decade 48
45
10
16
50
there is less exploration what it means for training tasks to be related. Some prior studies focus on constructing related training tasks by sampling categories within a dataset. Recent works 446] 33 consider training tasks sampled from different datasets, known cross-domain few-shot learning. The latter is considered as a more challenging problem, partly because the category gaps across datasets usually larger, resulting in training tasks less related to novel tasks. Although this follows the intuition, two natural questions arise: (1) How to quantify the relationship between training and novel tasks? (2) How does the relationship affect the adaptation difficulty on novel tasks for different FSL models?
48
To quantify the relationship between tasks, approach is to measure the category relationship in common representation space. With properly learned representation function, various distribution divergence metrics, like EMD [39 and FID (20), be used calculate the distance between feature distributions of different categories, as well as tasks over them. The main obstacle to this
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

solution is how to learn a good representation function for novel categories with only a few labeled samples. Previous works F2 assume that the representation function learned from training categories can be directly applied to novel categories, but this assumption may not hold due to the large category gaps. Some recent studies [ 26 utilize the Fisher Information Matrix to quantify the task relatedness without assuming common representation function. However, this approach has a heavy burden of computing Hessian matrix. Besides, the calculated task distances are highly dependent on the learned model, making them difficult to apply to other FSL models.
To investigate the influence of task relatedness on the difficulty of adapting models to novel tasks, existing studies [37 40 32 33) often make an empirical assumption that a novel task with large distances to the training tasks will be hard adapt to. With this assumption, some works [40] (2 B3) employ specific distance metries to quantify the task relatedness, and then construct more challenging benchmarks to explore the generalization ability of different models. Different with the these works, [26) select the most related training data to improve the episodic fine-tune process for FSL models based on an asymmetric task relatedness measure. Despite their empirical success, all the aforementioned works lack theoretical analysis, leaving the connection between task relatedness and task adaptation difficulty not formally clarified.
In this work, we try to overcome the existing obstacles and answer the two questions via attributes. Firstly, we introduce Task Attribute Distance (TAD) as met- ric to quantify the task relatedness. Our intuition lies in the attribute compositionality hypothesis (shown in Fig. []: each category can be represented as a compo- sition of attributes, which are reusable in huge assort- ment of meaningful compositions. TAD formulates this intuition by first measuring the total variation distance between attribute distributions categories, and then finding the maximum matching with minimum weight of a bipartite graph. Unlike other metrics, TAD only relies on the attribute conditional distributions, making it independent of models and the number of samples in novel tasks. Secondly, utilize the TAD metric to establish a theoretical connection between task relatedness and task adaptation difficulty in FSL. We provide theoretical proof to verify that TAD contributes to the generalization error bound on novel task, at different training settings. Importantly, our theoretical results indicate that the adaptation difficulty on novel task can be efficiently measured by relying solely on the TAD metric, without the need for training any models.
Souty Albatross
Med
Allowoss
Luysan
leng
Yellowtboat
training and novel
Figure 1: The categories and attribute sets of three bird images. Each category can be represented as composition of some attributes, which act as relationship bridge between different categories.
We conduct experiments three benehmark datasets validate our theoretical results and explore the generality of TAD metric. To this end, we consider two scenarios that the human-anma -nnootated attributes provided not available. For the latter case, we propose an efficient way to auto- annotate attributes. Experimental results show that as the distance between novel and training tasks increases, the performance of various FSL models novel tasks decreases. With the TAD metric, also present two potential applications: intervening a small set of difficult novel tasks before training, and investigating the benefits of heterogeneous training tasks for different models.
Our main contributions can be summarized as follows:
We propose Task Attribute Distance (TAD) metric in FSL to quantify the relationship between training and novel tasks, which is model-agnostic and easy to compute.
We provide a theoretical proof of the generalization error bound on a novel task based on TAD, which connects task relatedness and adaptation difficulty theoretically.
We conduct experiments to show TAD can effectively reflect the adaptation difficulty novel tasks for various FSL methods with human-annotatee and auto-amma auto-annotated attributes.
2 Related works
Few-shot learning. Most recent few-shot learning (FSI.) approaches are based on meta-learning framework. These meta-learning based methods can be roughly categorized into two categories. The

---

metric- based approach 48 42 45, 22 3 16, 50 aims to learn cross-task embedding function and predict the query labels based on the learned distances. The optimization- based approach focuses on learning some optimization state, like model initialization [17 or step sizes [28 5 to rapidly update models with very few labeled samples. Except for these meta-learning methods, transfer- based approaches [T,, 11 have recently shown that standard transfer learning procedure of early
pre-training and subsequent fine-tuning is a strong baseline for FSL with deep backbone networks.
Meta-Icarning theory. In parallel to the empirical success of meta-learning methods, a series of theoretical works study how meta-learning utilizes the knowledge obtained from the training task data and generalizes to the novel test tasks. Many works 35 error bound on novel tasks from the PAC-Bayesian perspective 30
4
12 19] give a generalization 38
31 These works often assume that each task is sampled from meta task distribution. Under such assumption, the generalization error bound on novel tasks can be reduced with increasing number of training tasks and training samples 44. Some recent works replace the meta task distribution assumption with other conditions. For example, g 14 47 assume a common representation function between different tasks, then they give the sample complexity bounds for the expected excess risk on a novel task. However, the above works do not quantify the relationship between training and novel tasks, and seldom explore the adaptation difficulty on novel tasks. In this paper, we propose the TAD as metric to quantify the task relatedness, and provide a new generalization error bound on a novel task.
Task Difficulty. Exploring the difficulty of few-shot tasks is an important research question in FSL, and has been explored from two aspects: measure the difficulty of (1) training tasks and (2) novel tasks. For training tasks, many previous works 44 29,
43 6 have attempted to measure their difficulties based on model's output, such negative log- liceliooo or accuracy, and use this information to sample different tasks to train the model. The sampling strategy based on training task difficulty is similar the area of hard example mining 41 or curriculum learning 77 that trains model according to specific order of samples to improve its generalization ability. For
novel tasks, recent works [ 37 32 26 try to measure the adaptation difficulty of novel tasks based on the relationship between novel and training tasks. Task2vec [ encodes each novel task into an embedding based on the Fisher Information Matrix, and uses the norm of embedding to reflect task difficulty. Other works utilize specific distribution divergence metrics, such as EMD and FID, to quantify the task relatedness, then select the most related training data to fine-tune models 26 or construct more challenging benchmarks to explore the generalization of models [37 40 33
Closer to our work, (37 introduces a transferability score to quantify the transferability of novel tasks via attributes and explore the generalization of FSL models at different transferability scores. However, different with our work, (37) aims to investigate the benefits of self-supervised pretraining with supervised finetuning in the few-shot attribute classification context.
3 Problem Setting
In few-shot learning problem, model observes different training tasks {ri with each task represented as a pair T; = =D, S.). S < n. D; is an unknown data distribution over the input space X' and label space V: S, = {Z 91) T= (Ix, Uk) D, represents drawn from D, With a model trained on the n. training tasks, our target is to adapt and evaluate it on l novel test tasks T/- S)),, ) S S (. Dj is an unknown data distribution over X' and )" and SJ is labeled dataset drawn from Dj. Note that, in few-shot learning, the labeled data for each category is very limited, and the categories in training tasks (7.) will not appear in novel tasks (7/))= which means V/ ny = 0, vi E uI,,., E (1,...,)) 4).
observed training set
Generalization Analysis of Attribute-based Few-shot Learning
The key to answering the two questions we raised above lies in a proper metric that quantifies task relatedness and contributes to the generalization error on a novel task. In this section, we begin by introducing the Task Attribute Distance (TAD), which first measures the category relationship through attribute conditional distributions, based on which the relationship between tasks measured as well. Then, to facilitate our theoretical analysis, we introduce a meta-learning framework with attribute learning. Finally, we provide theoretical proof that establishes a connection between the proposed TAD metric and the generalization error bound on a novel task.
3

---

4.1 Model-Agnostic Distance Metric via Attributes
To measure the relationship between two categories yk and yt. a natural idea to measure the divergence between class-conditional distributions p(rluu)) and p(all)) by a divergence measure, like the In or total variation distance (TV) [8] Unfortunately, this idea is frequently unfeasible, because the set of measurable subsets under distributions p(r) yk) and p(z|y) is often infinite, making it hard to compute the distance from finite samples.
In this paper, we introduce attributes to overcome the above limitation because the values of attributes are usually discrete and finite. The basic idea is based on the attribute compositionality hypothesis presented in the introduction section. Specifically, the distance between two categories can be measured by the difference between the corresponding attribute conditional distributions. Follow the above idea, let A be the attribute space spanned by L attribute variables {a' (a')er we define the distance between two categories yi: and yt. on L attribute variables as:
1 Σ drv (pla' (b)) p(a p(d)lv)) d(yk. 31) -
1 L
Σ
sup BEB'
Pal [B] Pa'pa.BB]
(I)
1=1
where Be is the set measurable subsets under attribute conditional distributions p(a' lyn) and p(a'luu ([e)),)) and B' is a finite set if the values of variable a' are finite.
Based on the distance between categories, we then define the distance metric between training and novel test tasks. To this end, we represent the set of categories in training task T, and the set of categories in novel task Tj as two disjoint vertex sets respectively, and construct a weighted bipartite graph G between the two vertex sets, where each node denotes a category and each edge weight represents the distance between two categories in Ti, Tj respectively. Let M = {Ekr} denote a maximum matching of G, which contains the largest possible number of edges and any two edges do not connect the same vertex. We choose M with minimum weights and define the task distance
d(T,, r))
1
Σ CMIMM
d(yk. Mc)
()))()))))..))o Σ drv (pl'p(lolvv yx). p(al CHEM
Σ
(2)
M
L [M]
where |M| is the number of edges in matching M. From this definition, if the two tasks Te, 7 are identical, the task distance d(T,,T;) is equal to O. We call the task distance d(T., 7/) as the Task Attribute Distance (TAD). Additionally, the TAD is invariant to the permutation of categories in tasks. In other words, modifying the numeric order of categories in т; or T does not affect their distance d(T,, 7/). To emphasize the attribute conditional distributions with respect to different tasks, we hereinafter add task indexes on the distribution and probability notations, like p (a'a (8k) and Ps aalve [B], although the true distributions are task agnostic.
4.2 A Specific Few-Shot Learning Framework
To facilitate the subsequent theoretical analysis, we consider meta-learning framework with attribute learning. In this framework, meta-learner so X ++ A parameterized by 0 learns the mapping from a sample x E X' to attributes a E A, and a task-specific base-learner Jø. A - Yds parameterized by d; learns the mapping from attributes E A to class label y E D, for training task T, During training. fe is meta-learned from n different training tasks. To adapt to a novel task TJ. we fix fo and train a new base-learner do; parameterized by df using few labeled samples Sy.
In the following theoretical deduction, we will denote pa(a, y) A p(ff(2),))) y) joint distribution over Axy induced by the meta-learned mapping fo. Further, with the induced conditional distribution pa(aly). we can compute the distance between task 7; and 7/ as
do(Te,
1
Σ CREEM 1=1
Σ
drv (v' (yx) (a'
LIM
Note that d(T:, T3) (as defined in Eq. (2)) computed based on p(aly) is the model-agnostic distance metric, while do (Te, TJ) is a model-related one since it relies on the meta-learned mapping fa.

---

4.3 Theoretical Analysis on Generalization
As for the above meta-learning framework, we provide theoretical analysis of the generalization error on novel task, in terms of the proposed TAD metric. We define the generalization error and empirical error of the meta-learner fe on novel task rj as
m ml Mag (fe(zz)) # yk):
e(fo 1
e(fe, = B( [[ge (fe(z)) # y)1.
where of is the parameters of Io learned from labeled samples Sj given fo. and m' - is the number of labeled samples in Sj. I denotes the indicator function. Similarly, we can define the generalization error e(fo. Tτ) and empirical error ē(fe; Tū) for training task TΙ. With these definitions, we will proceed by introducing an auxiliary lemma, and then stating our main theoretical results. All detailed proof's of the following lemma and theorems are in the Appendix.
Lemma 1. Let A be the attribute space, L be the number of attributes. Assume all attributes are independent of each other given the class label, i.e. p(aly) = II p(a"ly). For all E A and any two categories yk yt, the following inequality holds:
Σ
(p(aslun) p(aslve)) < d(yn, M1. + A.
GLEA
where d(yk: ye) is the distance as defined in Eq. and Enses 27 (p(afu()) + +(dd
Lemma says that under the attribute conditional independence assumption, the distance between two attribute conditional distributions p(a yyk, ), p(aly) over attribute space A is bounded by the defined distance d(yk: Vr) and a non-negative term A. This result enables us to make use of the defined TAD metric in deriving the generalization error bound, leading the following theoretical results.
Theorem 1. With the same notation and assumptions as in Lemma 1. let H. be the hypothesis space with VC- dimennin d. fe and 96 be the meta-learner and the base-learner as introduced in Sec. 4.2 respectively. Denote 96- as the best base-learner on some specific tasks given a fixed meta-learne fo- For any single training task T; (D;, S:) and a novel task 7Ú = (D', St), suppose the number of categories in the two tasks is the same, then with probability at least 1 6, V. So E H. we have
20m: cSo; 13) S ((fo, +V (dlog d
4
4. do 7 A +
+ log 8
(5)
where = As + X3 is the generalization error of 90- and fo on the two tasks, i.e., d; ((e.y)>,,(T (Jo(z)) * u)l. X3 = (a [Tgay (Jo(x)) # v)]. A' is term depending on learned base-learners 9et and the best base-learners :
Theoretically, the generalization eтror on a novel task is bounded by the the training task empirical error ē(fe. T²) plus four terms: the second term (T 7/) is the model-related distance between тІ and r/. which derived based on Lemma the third term A' reflects the classification ability of Is. which converges to zero if the learned base-learners are equal to the best ones for both tasks; the last term is the generalization error of fo and Jø-, which depends on the attribute discrimination ability of fo and the hypothesis space of base-learner I3- For a reasonable hypothesis space, if fo has a good attribute discrimination ability on both tasks, the last term usually converges to zero. Next we generalize this bound to the setting of training tasks.
Corollary 1. With the same notation and assumptions as Theorem 1, for n training tasks { and a novel task The define č(fe, 1 = Ei E(fo, T.), then with probability at least dgg fo H. we have
cffo. T3) & Efee, 7
1
Σ
n
ld
2em, 4 + log g)
+ n
Σ
A X, (6) do T/)
π 1=1
d
where X = - - d + Mj. and A is a term depending on the learned base-learners {go, l 1 9o/, and the best base-learners {g0; 1 9
5

---

Corollary iis straightforward extension of Theorem 1 in which we consider multiple training tasks instead single training task. In Corollary| I the generalization error on a novel task Tj is bounded partially by the average distance between task 73 and n training tasks. Note that the distance do (T;, Tj) used in the bound is model-related. Next, we further derive the relationship between model-related distance and model-agnostic distance as follows.
Theorem 2. With the same notation and assumptions as in Corollary 7 assume that the conditional distribution p(æraa²) is task agnostic. If the number of labeled samples my in n. training tasks and the number of labeled samples m'j in novel task TJ tend to be infinite, the following equality holds:
Σ df)
I T2
d(T...)).
Theorem 2 shows that when the number of labeled samples in n training task and a novel task tends be infinite, the model-related average distance can be bounded by the average TAD. Based on the universal approximation theorem [5] and the same assumption as in Theorem 2 if g6 fe is complex enough network, the second and fourth terms on the r.h.s. of Eq. (6) in Corollary [] will converge to 0, the first term é(fo: T(=) and 1 Li=1 X will converge to Bayes risk [13] We assume the Bayes risk is small enough, so that can be ignored. In this case, the generalization error on novel task TY is only bounded by X; and the average TAD, i.e., (f), S S E>= d(r;, T/)-- Note that the average TAD is independent of models, thus we can rely solely on the TAD metric to measure the adaptation difficulty of each novel task, without the need for training any models.
5
Computing the Model-Agnostic Task Distance
5.1 Distance Approximation
In this section, we discuss practical considerations in computing the TAD on real data, where the attributes often take on discrete and finite values. For continuous and infinite attributes, it is possible to divide their values into many segments or discrete parts. Therefore, we denote V as a finite set of possible values of attribute a', and re-express the TAD in Eq. 2
d( r1) = 2L M
ΣΣΣ
Pa [b]
P. by.
[v]
(8)
Cke PMEM 1=1 VEVI
Computing the above distance is challenging as it requires finding the maximum matching M with minimum weights, which is combinatorial optimization problem. The Hungarian algorithm [25 is commonly used to solve the matching problem, but it is computationally expensive. Due to the high computational cost, we do not calculate this distance directly but estimate the approximation instead:
L
d(T,, T,) 2LC
ΣΣ 1=1 VEV!
Σ
Pd ue [o]
Σ
Pd a'lve
where we assume all tasks have C' categories, which holds in most FSL settings. In Eq. (9) simplify the comparison of attribute conditional distributions between two tasks by replacing the individual differences with the average difference. Through the above approximation, seeking the minimum weight perfect matching M and estimate the TAD efficiently.
avoid
5.2 Attributes Auto-Annotation
As stated before, our proposed theory and TAD metric rely on category-level attribute annotations that are possibly unavailable for some few-shot benchmarks, like minilmageNet [48). To address this issue, we propose a solution to auto-annotate attributes using a pretrained CLIP [36] model, which has demonstrated impressive zero-shot classification ability. We first pre-define 14 attribute labels based on pattern, shape, and texture. Then we create two descriptions for each attribute, such as "a photo has shape of round" and "a photo has no shape of round", which are used as text inputs for CLIP. We formulate the annotation problem as 14 attribute binary classification problems for each image using CLIP model. After that, we gather the attribute predictions of all images within the same category, which provides rough category- attribute information while greatly reduces the cost of attribute annotations. With the above auto-annotation process, we can obtain the letegory-level attributes for minilmageNet in just minutes.

---

6 Experiments
In this section, we conduct experiments validate theoretical results and explore the generality of the proposed TAD metric in measuring task adaptation difficulty. Firstly, we evaluate our TAD metric in scenario where human-annotated attributes are available and the training/novel tasks are sampled from the same dataset but with different categories. Next, we test the TAD in a more general and challenging scenario where human-anman annotated attributes are not available and the training tasks are constructed by sampling categories from different datasets.
6.1 Setups
Datasets. We choose three widely used benchmarks: (1) CUB-CUUBUUU 200-22011 (CUB) 49 CUB is fine-griined dataset of birds, which has 200 bird classes and 11,788 images in total. We follow 23 to split the dataset into 100 training classes, 50 validation classes and 50 test classes. As fine-grained dataset, CUB provides part-based annotations, such as beak, wing and tail of a bird. Each part is annotated by a bounding box and some attribute labels. Because the provided attribute labels are noisy, we denoise them by majority voting, as in [24). After the proceesscsssng we acquire 109 binary category-level attribute labels. (2) SUN with Attribute (SUN) + SUN is scene classification dataset, which contains 14.340 images for 717 scene classes with 102 scene attributes. In following experiments, We split the dataset into 430/215/72 classes for training/validationn
respectively. (3) minelmageNet [48]: minilmageNet is a subset of ImageNet consisting of 60,000 images uniformly distributed over 100 object classes. Note that, different with CUB and SUN, minilmageNee does not provide the attribute annotations, which means category-
attribute annotations are not available. Following [TO), we consider the cross- cross-dataser scenario from min'llmaeNeet to CUB, where we use 100 classes of minilmageNett as training classes, and the 50 validation and 50 test classes from CUB.
Attribute Prototypical Network. Our theoretical analysis is based on specific meta-learning framework with attribute learming (proposed in Sec. (42)). Thus, we first instantiate a simple model under that framework as an example to verify our theory. Specifically, we adopt four-layer convolution network (Conv-4) with an additional MLP as the meta-learner fo. The convolutional network extracts feature representations from images, then the MLP takes features as input and predicts attribute labels. For base-learner Ie, parameterized by di. we simply choose an non- parametric base-leamer like ProtoNet [4). which takes the attributes outputted by fa as input to calculate cosine distance between test samples and attribute prototypes, then predicts the target label. We call this method as Attribute Prototypical Network (APNet). We train APNet by simultaneously minimizing the attribute classification loss and the few-shot classification loss.
Other FSL Methods. Besides of APNet, we choose five classical FSL methods in the following experiments, since they cover a diverse set of approaches to few-shot learning: (1) Matching Network
(MatchingNet) [48. (2) Prototypical Network (ProtoNet) 42. (3) Relation Network (RelationNet) 45). (4) Model Agnostic Meta-Learning (MAML) [17] and (5) Baseline++ [IO]. Note that these FSL methods, unlike the above APNet, do not use attribute annotations during training. See more implementation and experimental details in the Appendix.
6.2 Task Attribute Distance with Human-annotated Attributes
Approximate results with limited samples. According to Theorem 2 if the number of labeled samples in tasks tends to be infinite, the TAD serves as a metric to measure the adaptation difficulty on novel task. However, it is impossible that each task contains infinite labeled samples in real-world applications. Thus, we try to empirically verify the approximate theoretical result with limited labeled samples for each task. We train our APNet on CUB and SUN dataset, then use the provided attribute annotations to calculate the average distance Ei d(Ti, TT) between each novel task TJ and n training tasks {r: hr respectively. For simplicity, we sample n = 100, 000 training tasks to estimate the distances to 2, 400 novel tasks. Following N-way K-shot setting, each task only contains N= x K labeled samples for training or fine-tuning models. Fig, shows the task distance and the corresponding accuracy on novel tasks for APNet. We can observe in Fig. 4 that as the distance increases, the accuracy of APNet decreases in both 5-way 1-shot and 5-way 5-shot settings on CUB and SUN. These results verify that TAD can characterize model's generalization error on each novel task and measure the task adaptation difficulty effectively, even with limited labeled samples for
7

---

CUB 1-shet
CUB 5-shot
SUN 1-shet
SUN 5-shet
Accuracy
X14 035
314 K35 <Ie
416
038 Distance
324
Distance
Distance
Distance
(a)
(b)
(c)
(d)
Figure 2: Accuracy of APNet in terms of the average task distance. (a)-(b) 5-way 1-shot and 5-shot on CUB. (c)-(d) 5-way 1-shot and 5-shot on SUN. In (a)-(d), each gray point denotes the average accuracy for all points in distance interval, and the error bar denotes the confidence interval at 95% % confidence level. The red dashed line is fitted line, which shows the tendency of gray points.
RelationNet
Baseline++
MatchingNet
CUB 1-shot
5-shot
SUN 1-shot
SUN 5-shot
Accuracy
Distance
Distance
Distance
Distance
Figure 3: Accuracy different methods in terms of the average task distance. From left to right, 5-way 1-shot and 5-shot on CUB/SUN, Each point denotes the average accuracy in distance interval.
training and fine-tuning models. Note that the confidence interval in Fig. Dis much larger for the last few points. We argue this because these distance intervals contain fewer novel tasks, thus the average accuracy of novel tasks in the interval is more easily affected by random factors.
The number of labeled samples. Additionally, in Fig. when comparing 1-shot and 5-shot results with the same distance interval, we find that the increase of accuracy varies at different distance intervals. For instance, on the CUB dataset (comparing Fig. 2(a) with Fig. ((b)). when the task distance is 041 APNet shows an improvement of approximately 10% in accuracy for the 5-shot setting over the 1-shot setting, whereas shows an improvement of around 15% for the distance of 0.20. This suggests that increasing the number of labeled samples is more effective for harder tasks. One possible explanation is that as the task distance increases, less knowledge can be transferred from training tasks, making harder for models to adapt to the novel task. Hence, more information from the novel task is required for adaptation, and the model's performance can get more benefit from additional labeled samples.
Other FSL models. We have shown that the average TAD can effectively reflect the task adaption difficulty for APNet. natural question is whether the calculated task distance can be directly applied to other FSL methods, even if they do not follow the specific meta-learning framework and do not use the attributes during training. We try to empirically explore this question. With the same distance estimation and experimental setting, we conduct experiments with five different FSL methods on CUB and SUN. Fig. 3 shows the task distance and the corresponding accuracy of 2,400 novel test tasks for them. We observe similar results that with the increase of task distance, the accuracy of all FSL models tends decrease. This indicates that even though these FSL methods do not use the attribute annotations during training, they implicitly learn mixture of attributes in their representations. Therefore, autribute-based distance can still reflect the task adaptation difficulty for them. These results demonstrate the generality of the proposed TAD metric, and provide some insight into the transferable knowledge that different FSL models have learned.
6.3 Task Attribute Distance with Auto-annotated Attributes
Cross-datase generalization. Another interesting question is how to utilize the proposed TAD metric in situations where human-annotated attributes are either unavailable or expensive to obtain. One classic example is the cross-domain few-shot learning problem, since it requires the annotation

---

All attributes
w/o pattern
w/o shape
w/o texture
Accuracy (%)
Accur acy (6)
Accuracy
Accuracy
06
326 d5s Distance
532 334
18 Distance
635
03: 03 by
Distance
Distance
(a)
(b)
(c)
(d)
Figure 4: Accuracy of different methods in terms of the average task distance with (a) all attributes, (b) removal of pattern attributes, (c) removal of shape attributes, (d) removal of texture attributes. The experiment is conduct in 5-way 5-shot setting.
of distinct datasets with common attribute set. To address this challenge, use the auto-annotation method described in previous section to annotate the attributes for both minilmageNet and CUB, We then train the above FSL models on the cross cross-dataset scenario from miniImageNet CUB, and estimate the average task distance with the auto-annonn anootated attributes. Fig. 4(a) illustrates the distance and corresponding accuracy of 2,400 novel test tasks with the auto-annotated attributes. We can find that, with the increase of task distance, the accuracy of different models tends to decrease. This phenomenon is consistent with our previous findings and shows the proposed TAD metric still works with auto-annotated attributes. Besides, we selectively remove some attributes to explore the influence of them the distance-accuracy curve. Figs. [(b) to A(d)sshow that the exclusion of pattern, shape, and texture attributes exhibits varying degrees of influence on the decreasing tendency. Notably, discover that texture attributes are more importance than others, as indicated by the more pronounced fluctuations in the curve.
100 classes
64 classes
MatchingNet
50.0
51.7
-1.7
Accuracy 1%6)
ProtoNet
53.7
52.6
1.1
RelationNet
52.6
50.3
2.3
MAML
51.6
49.7
1.9
Baseline++
52.4
55.5
-3.1
Table 1: Comparison of 5-shot accuracy for differ- ent methods, when training on selected 64 classes instead of all 100 classes. A represents the differ- ence in accuracy between the cases. The best accuracy of each method is marked in bold.
Figure 5: 1-shot results of test-time interven- tion (minilmageNet-<CCU We only show the accuracy of the intervened tasks.
Test-time Intervention. With the proposed TAD metric, we can quantify the adaptation difficulty scenarios,
of novel test tasks without training and adapting model. This makes sense in as we can identify more challenging tasks before training and take interventions to improve a model's performance those tasks. In this part, we explore a simple test-time intervention operation that supplies more labeled samples for harder novel tasks. To construct the intervention experiment, first calculate the distances between each novel task and training tasks, as done in previous experiments. We manually set constant threshold value, denoted as r. to identify the harder tasks that exhibit large distances and generally yield low accuracy. Once identify these challenging tasks, we intervene by providing additional labeled samples, which contain more task-specific information. Specifically, the 5-way 1-shot setting, we offer 4 extra labeled samples for each intervened task, which can be seen as the additional annotated samples. We set the distance threshold r = 0.29 for the cross-date dataset scenario. With the above threshold values, we only need intervene with a small subset of novel tasks (approximately 5%-7%), which greatly reduces the cost of sample annotation. The results of the test-time intervention can seen Fig. 5 As illustrated in Fig. 5 the test-time intervention can significantly improve the performance of different FSL. models on the challenging novel tasks. Note that we are not proposing a novel intervention method, but demonstrating a practical application of the proposed TAD metric.

---

Training with partial versus all tasks. Using the proposed TAD, we can also investigate whether training on all available training tasks leads to better generalization compared to training on only the most related ones. While it is generally expected that training with more tasks helps to improve generalization, remains question whether this holds for heterogeneous data (e.g. cross-dataset scenario). To explore this, we follow the cross-dataset experiment setup from minilmageNet to CUB, and select these less related training tasks based on their calculated task distances. We collect the classes in the selected tasks, compute the frequency of each class, and remove the most frequent 36 classes (out of total of 100 classes in minilmageNet), We then reconstruct training tasks based on the remaining 64 classes in minilmageNet and retrain five FSL models. The results are presented in Tab. | It can be observed that incorporating more heterogeneous data that less related to the novel tasks may not lead to much improvement for ProtoNet, RelationNet and MAML), but could even result in performance degradation ( for Matching and Baseline++). This result may inspire future research on how to better utilize heterogeneous data to improve the performance of models in the cross-domain few-shot learning problem.
7 Conclusion
We propose a novel distance metric, called Task Attribute Distance (TAD), FSL to quantify the relationship between training and novel tasks, which only relies on the category-level attribute annotations. We present a theoretical analysis of the generalization error bound on a novel task with TAD, which connects task relatedness and adaptation difficulty theoretically. Our experiments demonstrate TAD can effectively reflect the task adaptation difficulty for various FSL methods, even if some of them do not learn attributes explicitly or human-annotated attributes are not available. We also present two potential applications of our TAD metric: intervening a small set of difficult novel tasks before training, and investigating the benefits of heterogeneous training tasks. We believe our theoretical and empirical analysis can provide more insight into few-shot learning and related arcas.
Limitations and broader impact. Our theory and proposed TAD metric assume that attributes are conditionally independent without considering the correlations that may exists between them. Furthermore, identifying which attributes However, we believe that our work lays a solid foundation for measuring task relatedness and adaptation difficulty of novel tasks, which offers starting point for further research in few-shot learning and related areas.
critical in the distance metric is still an open question.
Acknowledgments
This work is partially supported by National Key R&D Program of China no. 2021ZD0111901, and National Natural Science Foundation of China (NSFC): 61976203 and 62276246.
References
[1] 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 ICCV, 2019.
[2] Arman Afrasiyabi, Hugo Larochelle, Jean- Françoranç Lalonde, and Christian Gagné. Matching feature sets for few-shot image classification. In CVPR, 2022.
[3] Kelsey Allen, Evan Shelhamer, Hanul Shin, and Joshua Tenenbaum. Infinite mixture prototypes for few-shot learning. In ICML, 2019.
[4] Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended PAC-Bayes theory. In ICML, 2018.
[5] Antreas Antoniou, Harri Edwards, and Amos Storkey. How to train your MAML. In ICLR, 2019.
[6] Sébastien Amool, Guneet Dhillon, Avinash Ravichandran, and Stefano Soatto. Uniform sampling over episode difficulty. 2021.
10

---

[7] Yoshua Bengio, Jéröme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In ICML, 2009.
[8] Tianshi Cao, Marc T Law, and Sanja Fidler. theoretical analysis of the number of shots in few-shot learning. In ICLR, 2020.
[9] Susan Carey and Elsa Bartlett. Acquiring a single new word. Papers and Reports on Child Language Development, 15:17-29, 1978.
[10] Weiyu Chen, Yencheng Liu, Zsolt Kira, Yuchiang Frank Wang, and Jiabin Huang. closer look at few-shot classification. In ICLR, 2019.
[11] Yinbo Chen, Zhuang Liu, Huijuan Xu, Trevor Darrell, and Xiaolong Wang. Meta-baseline: Exploring simple meta-learning for few-shot learning. ICCV, 2021.
[12] Nan Ding, Xi Chen, Tomer Levinboim, Sebastian Goodman, and Radu Soricut. Bridging the gap between practice and PAC-Bayes theory in few-shot meta-learning. In NeurlPS, 2021.
[13] Geoff Dougherty, Puttern recognition and classification: an introduction. Springer Science & Business Media, 2012.
[14] Simon Shaolei Du, Wei Hu, Sham M Kakade, Jason D Lee, and Qi Lei. Few-shot learning via learning the representation, provably. In ICLR, 2021.
[15] András Faragó and Gábor Lugosi. Strong universal consistency of neural network classifiers. IEEE Transactions on Information Theory, 39:1 146-1151, 1993.
[16] Nanyi Fei, Yizhao Gao, Zhiwu Lu, and Tao Xiang. Z-score normalization, hubness, and few-shot learning. In ICCV, 2021.
[17] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. In ICML, 2017.
[18] Alison Gibbs and Francis Edward Su. On choosing and bounding probability metrics. International statistical review, 10:419-435, 2002.
[19] Jiechao Guan and Zhiwu Lu. Fast-rate PAC-Bayesian generalization bounds for meta-learning. In ICMI., 2022.
[20] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-seale update rule converge to local nash equilibrium. In NeurIPS, 2017.
[21] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks universal approximators. Neural networks, 2:359-366, 1989.
[22] Ruibing Hou, Hong Chang, Bingpeng Ma, Shiguang Shan, and Xilin Chen. Cross attention network for few-shot classification. In NeurIPS, 2019.
[23] Dahyun Kang, Heeseung Kwon, Juhong Min, and Minsu Cho. Relational embedding for few-shot classification. ICCV, 2021.
[24] Pang Wei Koh, Thao Nguyen, Yew Siang Tang, Stephen Mussmann, Emma Pierson, Been Kim, and Percy Liang. Concept bottleneck models. In ICML, 2020.
[25] Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2:83-97, 1955.
[26] Cat Phuoc Le, Juncheng Dong, Mohammadreza Soltani, and Vahid Tarokh. Task affinity with maximum bipartite matching in few-shot learning. In ICLR, 2022.
[27] SuBeen Lee, WonJun Moon, and Jae-Pil Heo. Task discrepancy maximization for fine-grained few-shot classification. CVPR, 2022.
[28] Zhenguo Li, Fengwei Zhou, Fei Chen, and Hang Li. Meta-sgd: Learning to learn quickly for few-shot learning, arXiv, 2017.

---

[29] Chenghao Liu, Zhihao Wang, Doyen Sahoo, Yuan Fang, Kun Zhang, and Steven CH Hoi. Adaptive task sampling for meta-learning In ECCV, 2020.
[30] David A McAllester. Some -ayysian theorems. Machine Learning, 37:355 16355-33,,11- 1998.
[31] David A McAllester. PAC-Bayesian model averaging. In COLT, 1999.
[32] Timo Milbich, Karsten Roth. Samarth Sinha, Ludwig Schmidt, Marzych Ghassemi, and Bjorn Ommer. Characterizing generalization under out-o--distribution shifts in deep metric learning. In NewrIPS, 2021.
[33] Jachoon Oh, Sungnyun Kim. Namgyu Ho, Jin-Hwa Kim, Hwanjun Song, and Se- Se-Young Yun. Understanding cross-domain few-shot learning based on domain similarity and few-shot difficulty. In NeurIPS, 2022.
[34] Genevieve Patterson, Chen Xu, Hang Su, and James Hays. The sun attribute database: Beyond categories for deeper scene understanding. International Journal of Computer Vision, 108:59-81, 2014.
[35] Anastasia Pentina and Christoph Lampert. A PAC-Bayesian bound for lifelong learning. In ICML, 2014.
[36] 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 JCML, 2021.
[37] Mengye Ren, Eleni Triantafillou, Kuan-Chieh Wang, James Lucas, Jake Snell, Xaq Pitkow, Andreas S Tolias, and Richard Zemel. Probing few-shot generalization with attributes. arXiv, 2020.
[38] Jonas Rothfuss, Vincent Fortuin, Martin Josifoski, and Andreas Krause. PACOH: Bayes-optimal meta-learning with -uaratarss. In ICML, 2021.
[39] Yossi Rubner, Carlo Tomasi, and Leonidas J Guibas. A metric for distributions with applications image databases. In ICCV, 1998.
[40] Mert Bulent Sariyildiz, Yannis Kalantidis, Diane Larlus, and Karteck Alahari. Concept general- ization in visual representation learning. In ICCV, 2021.
[41] Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick. Training region- based object detectors with online hard example mining. In CVPR, 2016.
[42] Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In NeurlPS, 2017.
[43] Qianru Sun, Yaoyao Liu, Zhaozheng Chen, Tat-Seng Chua, and Bernt Schiele. Meta-transfer learning through hard tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44: 14:1443-1456, 2020.
[44] Qianru Sun, Yaoyao Liu, Tat-Seng Chua, and Bernt Schiele. Meta-transfer learning for few-shot learning. In CVPR, 2019.
[45] Flood Sung, Yongxin Yang, Li Zhang, Tao Xiang, Philip HS Torr, and Timothy M Hospedales. Learning to compare: Relation network for few-shot learning. CVPR, 2018.
[46] Eleni Triantafillou, Tyler Zhu, Vincent Dumoulin, Pascal Lamblin, Utku Evei, Kelvin Xu, Ross Goroshin, Carles Gelada, Kevin Swersky, Pietre-Antoine Manzagol, et al. Meta-dataset: A dataset datasets for learning to learn from few examples. In ICLR, 2020.
[47] Nilesh Tripuraneni, Chi Jin, and Michael Jordan. Provable meta-learning of linear representa- tions. In ICML, 2021.
[48] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. In NeurIPS, 2016.
12

---

[49] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie. The caltech-uesd birds-200-2011 dataset. 2011.
[50]
Jiangtao Xie, Fei Long, Jiaming Lv, Qilong Wang, and Peihua Li. Joint distribution matters: Deep brownian distance covariance for few-shot classification. In CVPR, 2022.
13


Reviews:
[{"review_id": "zn3QKBsKQh", "reviewer": "Reviewer_PSzT", "summary": "This paper proposes a new metric--Task Attribute Distance (TAD)--to measure the distance between training and novel tasks in few-shot learning. TAD, based on pre-defined attributes of images, calculates a minimum matching between classes in training and novel tasks, where each edge in the bipartite graph is represented by the average TV distance between each two categories on all attribute variables. Using a meta-learning framework, the authors give a theoretical guarantee of the positive connection between TAD and adaptation difficulty. Experiments verify that an increased TAD can indeed lead to decreased few-shot learning performance, hence increased adaptation difficulty. ", "questions": "- Why consider the TV distance?\n- What if decreasing distance further in Figure 2-3, for example, below 0.1?", "limitations": "The authors have adequately stated the limitations.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "-  How to measure task similarity is central to few-shot learning problems. Using attributes to calculate task similarity is intuitive and makes sense to me, and has the advantage of not relying on specific models.\n- It is clever to utilize CLIP to automatically annotate attributes.\n- The theoretical analysis gives a guarantee of the effectiveness of the proposed metric.\n- Experiments on in-domain and cross-domain few-shot learning problems verify that the proposed metric can indeed serve as a surrogate of task adaptation difficulty, independent of the model used.\n- The writing is clear and easy to follow.", "weaknesses": "- The proposed metric only considers the distance between categories of two tasks, but not considers the relationship among categories inside each task. Thus some important characteristics of a task, like finegrainedness, are not taken into account.\n- In Theorem 1, VC dimension can go to a large value for neural networks, so the second term is not negligible, and the whole bound is thus not tight.\n- Theorem 2 and the following analysis depend on the assumption that the number of samples in the support set goes to infinity, thus not applied to few-shot learning, deviating from the main topic of the paper.\n- The theorem can be applied only to the hand-crafted meta-learning algorithm.\n- It seems to differ a lot switching from minimum matching to average difference.\n- Automatic annotation may lead to wrong definitions and assignments of attributes. This problem manifests in Figure 4.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed and constructive comments. \nWe are glad that you consider our studied problem is central in FSL problems and find the auto-annotation part clever.\nIn the following, we address your questions and concerns in the order of being proposed.\n\n**W1: The proposed metric only considers the distance between categories of two tasks, but ignores the relationship among categories inside each task.**  \nYes, we focus on measuring the relationship between categories of two tasks while ignoring the internal relationship within each task. \nThe rationale behind this idea is our belief that the former takes a more dominant role in the FSL problems.\nIn the common 5-way setting, each novel task has only 5 categories, thereby the internal relationship is less influential. \nTo account for the internal relationship, a possible solution is to measures the distance between attribute distributions of categories within a novel task, and then incorporate the distance into generalization error bound.\n\n**W2: The bound in Theorem 1 is not tight due to a large value of VC dimension for neural networks.**  \nThanks to point out this problem.\nWe will modify the Eq.13 in the proof of theorem 1 (see Appendix) by replacing the VC dimension with Rademacher complexity, which is commonly used in generalization theory for a tighter bound. \nWe would like to highlight that this modification will only impact the second term in Theorem 1, as well as Corollary 1.\nNote that our theoretical conclusions and experimental findings will remain unchanged after the modification.\n\n**W3: The assumption of infinite samples in support set for Theorem 2 and the following analysis deviates from the few-shot learning topic.**  \nThis is a nice question -- thank you for asking!\nTheorem 2 assumes infinite labeled samples to guarantee the proximity between the learned function $f_\\theta$ and the true labeling function $f: \\mathcal{X} \\rightarrow \\mathcal{A}$.\nTo relax the assumption, we introduce the notation of $\\epsilon$-approximation Network, as proposed in [ref1].\nThe $\\epsilon$-approximation Network is a model trained on support set such that the performance on query set is not less than 1-$\\epsilon$, where $0<\\epsilon<1$.\nBuilding upon this notation, we restate the Theorem 2 as:  With the same notation and assumptions as in Corollary 1, assume the conditional distribution $p(x|a^l)$ is task agnostic and $f_\\theta$ is a $\\epsilon$-approximation Network. The model-related average distance can be bounded by the average TAD, if $\\epsilon$ tends to zero.\nIn the final version, we will provide a more precise formulation of Theorem 2, and, if necessary, effectuate the modifications within the corresponding proof.  \n[ref1] Task Affinity with Maximum Bipartite Matching in Few-Shot Learning. In ICLR 2022.\n\n**W4: The theorem can be applied only to the hand-crafted meta-learning algorithm.**  \nOur theorem can be applied to other few-shot learning framework, such as transfer-based approach [9, ref2], with slight modification.\nMore specifically, we can consolidate all few-shot training tasks as a single training task, containing all training categories and samples.\nThen replace the meta-learning framework discussed in Sec 4.2 with a transfer-based framework, which performs early pre-training on all training samples and subsequent fine-tuning on each novel task.\nFor this new framework, Theorem 1 can be directly applied, which permits the applicability of our theorem into transfer-based few-shot approaches. \nFurthermore, how to incorporate other few-shot methods (like optimization-based approach) into our theoretical framework is an interesting problem, and we leave them into future work.  \n[ref2] Meta-baseline: Exploring simple meta-learning for few-shot learning. In CVPR 2021.\n\n**W5: It seems to differ a lot switching from minimum matching to average difference.**  \nWe switch from minimum matching to average difference mainly due to the computational burden.\nTo find a maximum matching, the commonly used Hungarian algorithm exhibits a time complexity of $O(V^2logV + VE)$ or $O(V^2E)$, where $V$ is the number of vertices and $E$ is the number of edges.\nDue to the high computational cost, we approximate it with average difference.\nThis approximation preserves some properties in original TAD, such as symmetricity and identity, while significantly mitigating computational overhead.\nEmpirical results demonstrate the reasonability of this approximation, as it can effectively reflect the task adaptation difficulty for various FSL methods.\n\n**W6: Automatic annotation may lead to wrong definitions and assignments of attributes.**  \nTo evaluate the quality of auto-annotated attributes, we manually annotate a few images ourselves.\nDetailed experiment results and analysis can be found in the response to Weakness 1 for Reviewer b4dX.\nTo acquire more accurate annotations, a better way is to fine-tune CLIP model with a few human-annotated samples, which can be achieved by learning prompts or adapters.\n\n**Q1: Why consider the TV distance?**  \nWe consider the TV distance due to the following two advantages: (1) Bounded distance. TV distance has a bounded value that ranges from 0 to 1, thus is well-suited for establishing a tighter upper bound on generalization error. (2) Efficient computation. When the set of measurable subsets is finite, TV distance is equal to half of the $L_1$ distance. In real-world scenarios, attributes often take on discrete and finite values, enabling the efficient computation of the TV distance.\n\n**Q2: What if decreasing distance further in Figure 2-3, for example, below 0.1?**  \nAccording to our theorem, we speculate that further decreasing the distance in Fig. 2-3 could lead to an increase in accuracy. \nHowever, empirically confirming this speculation poses challenges. \nIn our experiments, we observe a minimal task distance of 0.134, and no tasks exhibit a distance smaller than 0.1 within the current datasets and settings. "}, {"review_id": "qGJsgr8wMs", "reviewer": "Reviewer_aTLp", "summary": "The paper proposes a new metric called TAD (Task Attribute Distance) to measure the distance between two tasks which is expected to serve as a proxy for how difficult the target task is in comparison to the source pre-training data and also provide an approximation of the few-shot classification performance of a given task. The proposed method works by calculating a set of attributes for each class per dataset and then by computing an approximation of the maximum bipartite matching score between the classes from the source and target tasks. Authors provide theoretical justification related to the generalization bounds and also provide some empirical results. ", "questions": "* How will this method work if there is partial overlap in terms of classes between train and test? Is it a strict condition that the classes have to be disjoint between train and test?\n\n* How will the attribute prediction work for domains where CLIP may not work well?\n\n* Why does the attributes have to be dataset specific and defined apriori? Can it be something that is learnable too?\n\nFor other questions, please see my comments under weaknesses section.", "limitations": "Authors mentioned some limitations of their work in the paper and those seem reasonable.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The proposed method has a unique viewpoint -- instead of measuring task distance by using gradients or the fisher information matrix like some other methods, using a set of attributes as the anchors and computing distance based on the learned values of those attributes is a novel idea.\n\n* Given that not all datasets come with a set of pre-defined attributes, authors provide a practical backup solution to define a set of prompts per dataset where such attributes are not available and use CLIP to determine to get a score for each attribute -- after that, the original algorithm can be used.\n\n* The paper provides theoretical guarantees regarding the generalization error on a new task in terms of the proposed metric.\n\n* I appreciate the effort from authors to reduce the computational complexity of the bipartite matching by replacing the `hungarian` algorithm with a reasonable approximation. ", "weaknesses": "* The practicality of this metric is questionable -- it needs a somewhat large set of attributes per dataset and for most of the datasets, such attributes are not available and it would require users to generate a set of prompts and then feed the data through a CLIP model and perform trial and error before finding the right set of attributes.\n\n* Although in the related works section, the paper mentions a few works from the literature, I do not see any direct comparison between this metric and those in the experimental setup. It is hard to understand how good this metric is compared to other metrics.\n\n* The paper here misses comparing against (both method wise and experiment wise) against a relevant paper called Task2Vec - https://arxiv.org/abs/1902.03545. \n\n* The proposed metric is heavily tied to meta-learning algorithms and also where the number of ways (in K-way N-shot) have to be fixed between meta-train and test - which means to use this metric, one needs to train multiple meta learners with different number of ways. Please let me know if my understanding is incorrect.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our work.\nWe are glad that you deemed our method has a unique viewpoint, found TAD metric novel and recognized the effort we make to reduce the computational complexity.\nIn the following, we address your questions and concerns in the order of being proposed.\n\n**W1: The practicality of this metric is questionable when human annotated attributes are unavailable.**  \nWe provide some strategies to improve the efficiency of auto-annotation thus mitigate the problem you raised:\n+ **Domain-Specific Prompts.** Existing works [ref] offer several domain-specific prompts to improve the zero-shot image classification ability of CLIP for different datasets. Incorporating these established domain-specific prompts considerably alleviates the burden of generating a set of new prompts.\n+ **Coarse-Grained Attribute.** Pre-defining and auto-annotating a large set of fine-grained attributes incur substantial costs. A possible solution is to pre-define a small set of coarse-grained attributes, as adopted in our experiments, and it works to reflect the task adaptation difficulty. \n\n[ref] Learning to Prompt for Vision-Language Models. In IJCV 2022.\n\n**W2: Lack of comparisons between proposed TAD metric and other metrics by experiments.**  \nThanks for this valuable suggestion.\nFor comparing different metrics, we design a task selection experiment.\nMore specifically, we select top 5% novel tasks with the highest distances computed by different metrics, and \nthen evaluate the accuracy of FSL models on these chosen tasks.\nThe central hypothesis behind this experiment is that if a distance metric can better reflect task difficulty, then novel tasks with the highest distances should be more challenging.\n\nDue to the page limit, we present the experiment details and table in the global response.\nThe table shows that TAD significantly outperforms other comparison methods in identifying more challenging novel tasks, demonstrating the effectiveness of TAD metric.\nFurthermore, we are glad to highlight that the computational efficiency of TAD surpasses other methods, as illustrated in the last column of table.\n\n**W3: The paper here misses comparing (both method wise and experiment wise) against a relevant paper called Task2Vec.**  \nThank you for pointing out this related work, we will include it in final version.\nIn the following, we compare Task2Vec and our work from method wise and experiment wise.\n+ **Method Wise.** Task2Vec encodes each task into an embedding, and uses the norm of embedding to reflect task complexity. \nLike ours, Task2Vec provides a way to measure the difficulty of a novel task. However, there are two main differences: (1) \nTask2Vec utilizes the second derivative of the loss on novel tasks, whereas TAD employs attribute distributions in both training and novel tasks. These two approaches can be combined together to obtain a more accurate measure.\n(2) Task2Vec requires retraining the classifier and computing fisher information matrix for each novel task, thus it is time-consuming.\nHowever, TAD measures the task difficulty efficiently without the need of training any model.\n+ **Experiment Wise.** \nWe conduct a task selection experiment for comparisons.\nAs depicted in the table (see global response), Task2Vec works well with RelationNet and APNet, while fails with other FSL models.\nWe attribute this to the reliance on a pretrained model.\nMoreover, Task2Vec suffers from the computational burden.\nIt demands 100 minutes for 2400 novel tasks. In contrast, TAD completes the task difficulty measure in just 3 seconds.\n\n**W4: The proposed metric is not applicable with varying number of ways: one needs to train multiple meta learners.**  \nWe need to clarify that using TAD does ***not*** require training multiple meta learners.\nThe TAD metric can be applied directly in the scenario by averaging the attribute conditional distributions of each task in Eq.9.\nTo verify this point, we conduct experiments with varying numbers of ways.\nFig.1 (in the pdf file of global response) confirms that TAD metric can handle this scenario. \n\n**Q1: How will this method work if there is partial class overlap between train and test?**  \nThe proposed TAD metric can be directly applied when a class overlap exists. \nFrom Eq.9, if a category in the training task $\\tau_i$ also appears in the novel task $\\tau_j'$, the corresponding attribute conditional distributions can be eliminated within the subtraction formula.\n\n**Q2: How will the attribute prediction work for domains where CLIP may not work well?**  \nThe attribute auto-annotation process may not work well on a dataset where the performance of CLIP is subpar.\nIn light of this, we present solutions to tackle this problem:\n+ **Parameter-Efficient Fine-Tuning.** \nAn effective way is fine-tuning CLIP model to adapt general knowledge to specific datasets.\nTo this end, we can augment CLIP with additional parameters (like prompts or adapters) and train only the newly introduced parameters with few labeled samples.\n+ **In-Context Learning.** A better way is utilizing in-context learning capacity of pretrained vison-language models, such as GPT-4. In this approach, the labeled samples are treated as demonstrations. Take the demonstrations and query as input, GPT-4 can make predictions without fine-tuning models.\n\n**Q3: Why does the attributes have to be dataset specific and defined apriori?**  \nWe consider the dataset specific and predefined attributes due to two reasons:\n+ **Interpretability.** Predefined attributes offer interpretability, enabling a better way to understand the transferable knowledge acquired by distinct FSL models.\n+ **Model Independence.** Predefined attributes correspond to physical entities that are independent of models. Consequently, the distance metric derived from these attributes can be calculated without training a model. \n\nIt is noted that learning these attributes in an unsupervised manner might compromise these advantages.\n"}, {"review_id": "egCQ8dP0Rt", "reviewer": "Reviewer_mMtZ", "summary": "This work raises two questions regarding the setting of few-shot classifications: (1) How to evaluate the difference between training and novel tasks? (2) How does the difference impact FSL methods? For the first question, the authors proposed Task Attribute Distance (TAD), which uses attributes from CLIP to evaluate task differences. For the second question, the author derives upper bounds for the task and show some empirical evaluation.", "questions": "1. It is interesting that Figure 2 shows an almost linear response between distance and accuracy. Is this expected from the theory?\n2. Comparing Figures 2 and 3, it seems that the accuracy of APNet is generally better than other few-shot methods. Does that mean the APNet, which uses additional information from CLIP models, can be considered as an upper-bound method so we know which tasks have reached their best performance and we should not further push it? Can the authors evaluate it?\n\n", "limitations": "The author addressed the limitation in the selection of attributes, as I mentioned in the first point in the weakness section. Also, while the author raises several interesting observations and tries to derive the theory behind it, there is still some gap between the theory and the experiments, as I mentioned in the questions sections.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The author provides some theoretical insight into the difficulty of few-shot classifications with clear writing.", "weaknesses": "1. It is unclear how the manually selected 25 attribute impact the performance. The author also admits that the 25 pre-defined attributes are not comprehensive enough for the experiment in Sec 6.3. \n2. It is not very intuitive how this work can provide insight into few-shot learning areas. For example, for the experiments conducted in current few-shot papers, what is their average TAD? Can we tell the difficulty of these tasks based on their TAD? If some settings have TAD larger than a threshold, can we tell that these settings are not practical to do few-shot classification at all? It will be much more impactful if the author can point out problems or expectations of the few-shot learning area based on their theorem.\n3. Minor errors: Line 291, ProtoNet calculated Euclidean distance. It is MatchingNet that calculates cosine distance.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our work. \nWe are glad that you were interested in our observations, and we appreciate the suggestions you raised to enhance the impact of our paper.\nIn the following we address your concerns and questions in the order they are asked.\n\n**W1: It is unclear how the manually selected 25 attribute impact the performance.**  \nWe first explain how we select the 25 attributes in the auto-annotation process, then we perform a sensitivity analysis to explore the impact of these attributes.\n+ **Attribute selection and universality.** In the process of attribute selection, we follow previous work [ref1] and pre-define 25 semantic appearance attributes. A comprehensive list of these attributes can be found in the response to Question 2 for Reviewer b4dX. These 25 attributes encompass a wide spectrum including color, pattern, shape and texture, thus can be applicable across various datasets.  Fig. 4 showcases the effectiveness and universality of these attributes on miniImagenet and CUB datasets, although the decreasing tendency is not a strict monotonic pattern.\n+ **Sensitivity analysis.** To explore the influence of the selected 25 attributes, we exclude some attributes and observe the changes in distance-accuracy curve. \nFig.2 (in the pdf file of global response) shows that the exclusion of 11 color attributes makes the curve more linear, consistent with the linear tendency of Fig.2 and Fig.3 in main paper. A possible explanation could be that the auto-annotated color attributes are more susceptible to the background.\nFurthermore, the exclusion of pattern, shape, and texture attributes exhibits varying degrees of influence on the decreasing tendency.\n\n[ref1] Attribute learning in large-scale datasets. In ECCV 2010.\n\n**W2: How this work can provide insight into few-shot learning areas? It will be much more impactful if the author can point out problems or expectations of the few-shot learning area based on their theorem.**  \nThanks for this valuable suggestion, and we will point out some expectations of few-shot learning area based on the insights gleaned from our theorem:\n+ **Explore the boundaries of few-shot learning.** Based on our theorem and proposed metric, we can explore which tasks are not practical to do few-shot learning at all. Taking CUB dataset as an example. In Fig.3 (left, 5-way 1-shot setting), assuming a consistent tendency for the accuracy-distance curve, the accuracy of various FSL models reduces to 0.2 when the distance increases from 0.3 to 0.4. In other words, different FSL models performs like random guess when the distance of a novel task exceeds the threshold 0.4. In such case, these tasks are not practical to do few-shot classification at all, which is beyond the boundary of few-shot learning problem. \nWe conducted empirical verification of this idea by first selecting tasks with the highest distances and then evaluating the performance of FSL models on these tasks. Notably, as the distance of novel tasks approaches 0.3, the accuracy of different FSL models reduces to the range of 0.25-0.35, aligning with the observed curve in Fig.3.\n+ **Explore the utilization of heterogeneous data in cross-domain few-shot learning**. Based on our theorem and metric, a viable direction in cross-domain few-shot learning is to select appropriate training tasks to optimize models, like [25]. As shown in Sec 6.3, our study reveals that incorporating more training tasks that are less related to novel tasks, may not lead to much improvement. It could even result in performance degradation. This observation suggests that, with the context of cross-domain few-shot learning, selecting training tasks that are closely related to the novel tasks could be more beneficial for improving performance. \n\n**W3: Minor errors: Line 291, ProtoNet calculated Euclidean distance. It is MatchingNet that calculates cosine distance.**  \nThanks for pointing out this. It is not an error but a less clear description. At line 291, our intention is to describe a non-parametric base learner similar to ProtoNet, utilizing the average of sample embeddings to calculate the prototypes. We will revise this sentence to avoid misunderstandings in the final version.\n\n**Q1: It is interesting that Figure 2 shows an almost linear response between distance and accuracy. Is this expected from the theory?**  \nYes. At line 233, if $\\lambda_j'$ is a small constant, we anticipate observing a linear correlation between the average TAD and the generalization error bound.\nIt is noted that Theorem 2 and the following analysis rely on the assumption of infinite labeled sample, whereas we empirically verify the linear relationship using limited samples for each task.\nThis emphasizes that the infinite sample assumption can be further relaxed to closely align with the experiment finding.\n\n**Q2: Can the APNet be considered as an upper-bound method? So we know which tasks have reached their best performance and we should not further push it.**  \nAPNet utilizes additional attributes, whether human-annotated or auto-annotated, thus its accuracy is generally better than other few-shot methods.\nHowever, designating APNet as an upper-bound method requires more evaluation and analysis. This is because the best performance on each task depends on many factors, such as network architecture, training strategy and attribute annotation noise.\nFor a comprehensive understanding of which tasks have reached their best performance and hence not necessitate to further push, an extensive evaluation and analysis considering all these factors (including APNet and many SOTA methods) are required, which lies beyond the scope of this paper."}, {"review_id": "ioOTxWs7VS", "reviewer": "Reviewer_b4dX", "summary": "The paper proposes a new metric, the Task Attribute Distance (TAD), to quantify the link between two tasks for FSL. The distance is based on the relationship between some pre-defined attributes and classes in the two tasks. This distance can be computed from a model point of view, considering the distribution of attributes in the features space of a given model, or in a model-agnostic way. The paper presents two main theoretical results about TAD:\n- first, showing the link between TAD from a model computed on training tasks and a given novel task, and the generalization error on this novel task.\n- second, the link between the model-related TAD and the model-agnostic one.\nThen the paper discusses how to empirically estimate the model-agnostic TAD, and how to create attributes automatically for datasets without ones, using a pretrained CLIP model.\nFinally, the paper provides experiments on two datasets with attributes labels (SUN and CUB), and one with attributes from auto-annotation (mini-imagenet). The results show that the task distance is correlated with the performance of the models. A final experiment shows that some models benefits from removing frequent classes in training.", "questions": "- I would like to see preliminary results for potential applications of this metric to assess the significance of the work. \n- What are the attributes obtained for mini-Imagenet ? Are they sounded ? ", "limitations": "The authors have included a discussion about the limitations of their works. I don't think that a discussion on societal impact is needed for this work. ", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- *Originality:* the metric presented is novel and represents an interesting way to measure task difficulty. It uses information about attributes related between the tasks, as opposed to previous works which mainly used model's outputs. \n- *Quality:* The claims are all supported, and the paper presents theoretical results with proofs to link the TAD metric with generalization bounds. The experimental results show the correlation between the distance and the performance. I took a look at the proofs and the results are sounded.\n- *Clarity:* The paper is clearly written and easy to follow.", "weaknesses": "The main weakness of the paper is the significance and the quality of the analysis regarding the attributes automatically obtained. \n- I found the metric interesting because it can be computed in a model-agnostic way, but its main problem is that it relies on attributes that are not always available on datasets. Even though the paper explains a way to automatically annotate with attributes, an evaluation of the quality of the obtained attributes is missing. We can even see on Figure 4 that the correlation between the obtained attributes and the performance is less clear than on other datasets. It would also be interesting to show more examples of the obtained attributes, for a qualitative analysis. Because it relies too much on attributes, and on their quality, I am afraid this metric will be of limited impact.\n- I think the paper is missing an application of the proposed metric in a setting where it could be useful. Besides the experiments showing the link between the distance and the performance, I'm not really convinced by the last experiment on training with less training tasks. I don't think it is a good representative of potential applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for taking the time out to review our work. We are glad that you found the proposed metric to be both novel and interesting, and the represented proofs to be sounded.\nIn the following we address your concerns and questions in the order they are asked.\n\n**W1: An evaluation of the quality of the obtained attributes is missing. It would also be interesting to show more examples of the obtained attributes for a qualitative analysis.**  \nThanks for pointing out this question. We try to evaluate the quality of the auto-annotated attributes and then give some examples for qualitative analysis.\n+ **Auto-annotation evaluation.** Due to the absence of attribute annotations in the miniImagenet dataset, we collect the annotations ourselves. We first pre-define 25 attribute labels, then random select 50 images and proceed to annotate them. By comparing the ground-truth annotations and the results produced by CLIP model, we discern that the average accuracy across the 25 attributes approaches 0.65. Notably, we observe that CLIP achieves good performance across the majority of attributes, with accuracy from 0.7 to 0.9. However, it fails on some attributes, such as \"white,\" \"pink\",\"smooth,\" and \"shiny\", where the accuracy decreases to approximately 0.2. This discrepancy could potentially stem from the less frequency of these attributes in the CLIP training dataset. To understand the underlying factors more comprehensively, further experiment is required.\n+ **Qualitative examples.** Fig.3 (in the pdf file of global response) shows the qualitative examples of the obtained attributes. We find that CLIP model can annotate the main attributes correctly in an image. The common wrong cases are color attributes. CLIP model always predicts more colors than manual annotations.\n\n**W2&Q1: I think the paper is missing an application of the proposed metric. I would like to see preliminary results for potential applications of this metric to assess the significance of the work.**  \nWe present two potential applications in the last experiment and Appendix 4.2.\nSpecifically, in Appendix 4.2, we design a toy intervention experiment. \nThis intervention experiment is motivated by the property of TAD metric that we can quantify the adaptation difficulty of novel test tasks without the need to train a model.\nThis property enables us to identify more challenging tasks before training and take interventions to improve a model's performance on those tasks.\nIn the intervention experiment, we intervene these challenging tasks by simply providing additional labeled samples.\nWith a proper distance threshold, we only need to intervene with a small subset of novel tasks (approximately 5%-7%), which greatly reduces the cost of sample annotation and improves the performance of various models.\nFurthermore, inspired by the question raised by Reviewer mMtZ, we conceive another possible application for our proposed metric: it can be used to explore which tasks are not practical to do few-shot classification at all.\nMore details about this application can be found in our response to Weakness 2 for Reviewer mMtZ.\n\n**Q2: What are the attributes obtained for mini-Imagenet? Are they sounded?**  \nIn the attribute auto-annotation process, we follow previous work [ref1] and pre-define 25 attribute labels. These 25 attributes are semantic appearance attributes, including color, pattern, shape and texture. The details about these attributes are described in the following table.  \n\n| | attributes |\n|----------|------------|\n| Color    | black, blue, brown, gray, green, orange, pink, red, violet, white, yellow           |\n| Pattern  | spotted, striped           |\n| Shape    | long, round, rectangular, square           |\n| Texture  | furry, smooth, rough, shiny, metallic, vegetation, wooden, wet           |\n\n[ref1] Attribute learning in large-scale datasets. In ECCV 2010."}]

Author rebuttal:
We are grateful to all reviewers for the generous effort they have invested in reviewing our work, and are enthused to learn that they consider our studied problem is "central" in few-shot learning (Reviewer PSzT), find our ideas "unique", "novel" (Reviewer aTLp), "interesting" and "well supported" (Reviewer b4dX).

We appreciate the valuable feedback, and take this opportunity to highlight a few important enhancements we have made during the rebuttal period. Details and additional experiments can be found under individual comments to the reviewers.

**Attribute Auto-Annotation**
+ Efficiency: Reviewer aTLp request the efficiency when we apply TAD metric in datasets without attribute annotations. We response with some strategies to auto-annotate images efficiently thus mitigate the problem.
+ Sensitivity analysis: Reviewer mMtZ asks how the manually selected 25 attribute impact the performance. We response with sensitivity analysis to show the effectiveness of these attributes in task difficulty measure (Fig.2 in the pdf file). We find a more linear relationship when excludes 11 color attributes. We attribute this to the quality of obtained color attributes, because the these attributes are more susceptible to the background.
+ Evaluation of quality: Reviewer b4dX requests an evaluation of the quality of the obtained attributes. We response with experiments by annotating a small number of images ourselves. By comparing the ground-truth annotations and the results produced by CLIP model, we observe a good classification ability for CLIP model on majority attributes, while fails on some specific attributes, like "white," "pink","smooth," and "shiny". 
+ Qualitive examples: Reviewer b4dX asks showing some examples of the obtained attributes, for a qualitative analysis. We response with a figure showing 6 examples (Fig.3 in the pdf file). We find the common wrong cases are color attributes. CLIP model always predicts more colors than manual annotations.

**Practicality of TAD metric**
+ Comparison with other metrics: Reviewer aTLp raised a valuable point to understand how good the TAD metric is by comparing with other metrics.
To compare different metric, we design a task selection experiment that compares the difficulty of tasks selected with highest distance. 
Due to the page limit, we present some details and the corresponding table below: 

  We choose three methods for comparison, which have been proposed in the few-shot learning or related area: (1) **Frechet Inception Distance (FID)** [31], (2) **Earth Mover’s Distance (EMD)** [32], (3) **Task2Vec** [ref].
  Note that those three methods rely on a pretrained model. Following [32], we use ResNet-101 pre-trained on ImageNet for them. 

  ||MatchingNet|ProtoNet|RelationNet|Baseline++|APNet| Cost|
  |-|-|-|-|-|-|-|
  |FID|-3.71|-1.78|-0.57|-0.33|-3.63|8min|
  |EMD|-0.24|-1.33|1.6|-0.75|1.17| 22s|
  |Task2Vec|-0.54| -0.3|-3.64|-0.54|-2.45|100min|
  |TAD|**-8.23**|**-6.64**|**-7.39**|**-3.52**|**-7.24**| 3s|

  In the above table, we calculate the difference in accuracy between the chosen tasks and all novel tasks.
  We find that TAD significantly outperforms other three methods in identifying more challenging novel tasks across all FSL models, demonstrating the effectiveness of TAD metric.
  Furthermore, the computational efficiency of TAD greatly surpasses other methods, as illustrated in the last column of table. 
  Notably, TAD requires only 3 seconds to compute across 2400 novel tasks, underscoring its advantage of ease of computation.  

  [ref] Task2Vec-Task Embedding for Meta-Learning. In ICCV 2019.
+ Insight: Reviewer mMtZ encourages us to think about how our theorem and proposed metric can provide insight into few-shot learning areas. 
We response with two expectations that can drive exploration within the few-shot learning domain: exploring the boundaries of FSL methods and the utilization of heterogeneous data in CD-FSL.
+ Potential applications: Reviewer b4dX request some preliminary results for potential applications of TAD metric. We response with experiments in Appendix and insights inspired by Reviewer mMtZ.

**Theory**
+ Tighter Bound: Reviewer PSzT asks a tighter bound in Theorem 1 due to the large value of VC dimension for neural networks. We response with some modifications by replace VC dimension with Rademacher complexity. Our theoretical conclusions and experimental findings will remain unchanged after the modification.
+ Infinite Sample Assumption: Theorem 2 and following analysis assume infinite labeled samples in support set, thus deviating from the few-shot learning problem. Reviewer PSzT asks whether such infinite sample assumption can be relaxed further, we response with a new condition without assuming infinite labeled samples,thereby is more suitable for few-shot learning area.

Meta-review: The submission presents a metric called Task Attribute Distance (TAD) as a proxy to the difficulty of performing few-shot learning on novel tasks depending on the training tasks used to obtain the (pre)trained model. TAD is computed using predetermined image attributes, which are assumed to take on discrete and finite values. Given two learning problems, per-class attribute distributions are compared on the cross-product of the two learning problems' label spaces. TAD is then expressed as the maximum bipartite matching score between the classes in the two label spaces. For datasets with no pre-defined attributes (like mini-ImageNet), the submission proposes to use a pre-trained CLIP model in conjunction with 25 pre-defined attributes based on color, pattern, shape, and texture to annotate the datasets automatically.

Theoretical results are presented in the meta-learning setting on the relationship between TAD and the generalization error on a novel task. Empirical results are also presented on CUB, SUN, and mini-ImageNet, showing that TAD is correlated with model performance.

Reviewers note that the submission is clear (PSzT, b4dX) and tackles a central problem in few-shot learning (PSzT), and the proposed approach is an interesting and new take on defining task difficulty (aTLp, b4dX) backed by theoretical results (PSzT, aTLp, mMtZ, b4dX).

The main reviewer concerns are:

* The bound in Theorem 1 is loose, and Theorem 2 assumes that the number of samples goes to infinity, which is incompatible with few-shot learning (PSzT). The authors present an update to their theorems which replaces VC dimensions with Rademacher complexity for a tighter bound in Theorem 1 and relaxes Theorem 2's assumptions with an $\epsilon$-approximation network. This addresses Reiewer PSzT's concern.
* There is no direct comparison between TAD and related work on defining task difficulty, and the paper misses out on Task2Vec (aTLp). The authors acknowledge the Task2Vec oversight and commit to discussing it and its relationship with TAD in the final manuscript. They also present a task selection experiment comparing TAD against FID, EMD, and Task2Vec and showing TAD outperforms competing approaches. This addresses Reviewer aTLp's concern from my vantage point.
* The attribute auto-annotation approach could be prone to trial-and-error in defining the attributes, and it's unclear whether TAD is robust to different choices of 25 attributes (mMtZ, b4dX). The authors present qualitative and quantitative analyses for the auto-annotation procedure which addresses Reviewer b4dX's concern.

Following the author-reviewer discussion, the reviewer consensus is in favor of acceptance.
Decision: Accept (poster)