Long-Tailed Learning Requires Feature Learning
Authors: Thomas Laurent
James von Brecht
Xavier Bresson
Venue: ICLR 2023 poster (2023)
Keywords: deep learning theory
generalization
long-tailed data distribution

Abstract: We propose a simple data model inspired from natural data such as text or images, and use it to study the importance of learning features in order to achieve good generalization. Our data model follows a long-tailed distribution in the sense that some rare and uncommon subcategories have few representatives in the training set. In this context we provide evidence that a learner succeeds if and only if it identifies the correct features, and moreover derive non-asymptotic generalization error bounds that precisely quantify the penalty that one must pay for not learning features.

Published as a conference paper at ICLR 2023
LONG-TAILD LEARNING REQUIRES FEATURE LEARNING
Thomas Laurent', James H. von Brecht, Xavier Bresson
1 Loyola Marymount University, tlaurent 1mu edu
2 National University of Singapore, xaviercaênus, edu. sg
ABSTRACT
We propose simple data model inspired from natural data such as text or images, and use it to study the importance of learning features in order to achieve good generalization. Our data model follows a long-tailed distribution in the sense that some rare subcategories have few representatives in the training set. In this context we provide evidence that a learner succeeds if and only if it identifies the correct features, and moreover derive non-asymptotic generalization error bounds that precisely quantify the penalty that one must pay for not learning features.
INTRODUCTION
Part of the motivation for deploying neural network arises from the belief that algorithms that learn feattrresreprresentttions generalize better than algorithms that do not. We try to give some mathematical ballast this notion by studying data model where, an intuitive level, learner succeeds if and only if it manages to learn the correct features. The data model itself attempts to capture two key structures observed in natural data such as text or images. First, is endowed with a latent structure at the patch or word level that is directly tied to classification task. Second, the data distribution has long-tail, in the sense that rare and uncommon instances collectively form significant fraction of the data. We derive non-asymptotic generalization error bounds that quantify, within our framework, the penalty that one must pay for not learning features.
We first prove a two part result that quantifies precisely the necessity of learning features within the context of our data model. The first part shows that a trivial nearest neighbor classifier performs perfectly when given knowledge of the correct features. The second part shows it is impossible to priori craft a feature map that generalizes well when using nearest neighbor classification rule. In other words, success or failure depends only the ability to identify the correct features and not the underlying classification rule. Since this cannot be done a priori, the features must be learned.
Our theoretical results therefore support the idea that algorithms cannot generalize on long toigetailed data if they do not learn features. Nevertheless, an algorithm that does learn features can general- ize well. Specifically, the most direct neural network architecture for our data model generalizes almost perfectly when using either a linear classifier or a nearest neighbor classifier on the top of the learned features. Crucially, designing the architecture requires knowing only the meta structure of the problem, but no priori knowledge of the correct features. This illustrates the built-in advantage of neural networks; their ability to learn features significantly eases the design burden placed on the practitioner.
Subcategories in commonly used visual recognition datasets tend follow long- tailed distribution Salakhutdinov et al. 2011 Zhu et al. 2014 Feldman & Zhang 2020). Some common subcate- gories have a wealth of representatives in the training set, whereas many rare subcategories only have a few representatives. At intuitive level. learning features seems especially important long-tailed dataset since features learned from the common subcategories help to properly classify test points from rare subcategory. Our theoretical results help support this intuition.
We note that when considering complex visual recognition tasks, datasets are almost unavoidably long-tailes (Liu et al., 2019) even if the dataset contains millions of images, it is to be expected that many subcategories will have few samples. In this setting, the classical approach of deriving asymptotic performance guarantees based on a large-sample limit is not fruitful avenue. General-

---

Published as a conference paper at ICLR 2023
ization must be approached from different point of view (c.f. Feldman (2020) for very interesting work in this direction). In particular, the analysis must be non-asympiotic. One of our main con- tribution is to derive, within the context of our data model, generalization error bounds that are non-asymptotic and relatively tight- - by this we mean that our results hold for small numbers of data samples and track reasonably well with empirically evaluated generalization error.
In Section 2 we introduce our data model and in Section 3 we discuss our theoretical results. For the simplicity of exposition, both sections focus on the case where each rare subcategory has single representative in the training set. Section 4 is concerned with the general case in which each rare subcategory has few representatives. Section 5 provides an overview of our proof techniques. Finally, in Section[o] we investigate empirically a few questions that we couldn 't resolve analytically. In particular, our error bounds are restricted to the case in which a nearest neighbor classification rule is applied on the top of the features we provide empirical evidence in this last section that replacing the nearest neighbor classifier by linear classifier leads to very minimal improvement. This further support the notion that, our data model, it is the ability to learn features that drives success, not the specific classification rule used on the top of the features.
Related work. By now, rich literature has developed that studies the generalization abilities of neural networks. A major theme in this line of work is the use of the PAC learning framework to derive generalization bounds for neural networks (e.g. |Barlettt et al. (2017);NNyssabbur et al. (2017); Golowich et al.] (2018): Arora et al. 2018); Neyshabur et al. (2018)) 8)). usually by proving a bound on the difference between the tinite-sappe empirical loss and true loss. While powerful in their generality, such approaches are usually task independent and asymptotic; that is, they are mostly agnostic any idiosyncrasies in the data generating process and need a statistically meaningful number of samples in the training set. As such, the PAC learning framework is not well-tailored to our specific aim of studying generalization on long-tailos data distributions; indeed, in such setting, a rare subcategory might have only a handful of representatives in the training set.
After breakthrough results (e.g. Jacot et al. 20188:: Du et al. (2018); Allen-Zhu et al. (2019) Ji & Telgarsky (2019)) showed that vastly wee-pparametrized neural networks become kernel methods (the so-called Neural Tangent Kernel or NTK) in an appropriate limit, much effort has gone toward analyzing the extent to which neural networks outperform kernel methods (Ychudai & Shamir 2019
Wei et al. 2019; Refinetti et al. 2021 Ghorbani et al. 2019: 2020 Karp et al. [02 1| Allen- -hu &
2019; 2020 Li et al. 2020 Malach et al.) 2021). Our interest lies not in proving such gap for its own sake, but rather in using the comparison to gain some understanding on the importance of learning features in computer vision and NIP contexts.
Li
Analyses that shed theoretical light onto learning with long-tailed distributions (Feldman 2020
Brown et al., (021) onto specific learning mechanisms (Karp al.) 2021) are perhaps closest to our own. The former analyses (Feldman 2020: Brown et al. 2021) investigate the necessity of memorizing rare training examples in order obtain near-optimal generalization error when the data distribution is long-tailed. Our analysis differs to the extent that we focus on the necessity of learning features and sharing representations in order to properly classify rare instances. Like us, the latter analysis (Karp et al., (201)) also considers a computer vision inspired task and uses it to compare a neural network to kernel method, with the ultimate aim of studying the learning mechanism involved. Their object of study (finding sparse signal in the presence of noise), however, markedly differs from our own (learning with long-tailed distributions).
2 THE DATA MODEL
We begin with simple example to explain our data model and to illustrate, at an intuitive level, the importance of learning features when faced with long-tailed data distribution. For the sake of exposition we adopt NLP terminology such as "words" and 'sentences,' but the image-based terminology of "patches' and 'images' would do as well.
The starting point is very standard mechanism for generating observed data from some underlying collection of latent variables. Consider the data model depicted in Figure] I of n = 12 words and a set of n. = 3 concepts:
We have a vocabulary
V (potato, cheese, carrots, chicken, and
C (vegetable, dairy, meat).
2

---

Published as a conference paper at ICLR 2023
Vecabulary words parthioned into
sequeeccs concapts variables)
15 sertiancas (the training set)
datry.
delry
veggie
datr..
datry
lettock
yigrrt
carros
potato
lands
tarteer
potata
pogort
potato
Ietture
Jook
Bestter
pork
chicken
butter
checese
10 dain mest
Valry
Chooss
Chooss
lettocs
pock
meat
boef
park
creum
yugurt
dairy
1eot datyy dily
vaggle
butter
potats,
cakieen
Chones
Chooos
pagent
curi
Jelk
pock
Crean
beise
Lends
perk
Inirent
Insiter.
Figure 1: Data model with parameters set to L = 5, nw = 12, n2 = 3, R = 3, and Mspl = 5.
The 12 words are partitioned into the 3 concepts as shown on the left of Figure We also have 6 sequences of concepts of length I. 5. They denoted by C2:C2: C3 and cj C22 C/-- Sequences of concepts are latent variables that generate sequences of words. For example
[dairy, dairy, veggie, meat, veggie] generates
[cheese, butter, lettuce, chicken, leek]
The sequence of words on the right was obtained by sampling each word uniformly at random from the corresponding concept. For example, the first word was randomly chosen out of the dairy concept (butter, cheese, cream, yogurt), and the last word was randomly chosen out of the vegetable concept (potato, carrot, leek, lettuce.) Sequences of words will be referred to as sentences.
The non-standard aspect of model comes from how datum' process to form a training distribution. The training set in Figure i made of 15 sentences split into R 3 categories. The latent variables c/, c22, c/ each generate single sentence, whereas the latent variables C1, C2, C3 each generate 4 sentences. We will refer to Cj C22 C3 as the familiar sequences of concepts since they generate most of the sentences encountered in the training set. On the other hand c'2 c2 c'3 will be called unfamiliar. Similarly, a sentence generated by familiar (resp. unfamiliar) sequence of concepts will be called a familiar (resp. unfamiliar) sentence. The former represents datum sampled from the head of a distribution while the latter represents a datum sampled from its tail. We denote by X,,s the 5hh sentence of the y*th category, indexed so that the first sentence of each category is unfamiliar sentence and the remaining ones are familiar.
the Hatent-variable - observed-
Suppose now that we have trained a learning algorithm on the training set described above and that at inference time we are presented with previously unseen sentence generated by the unfamiliar sequence of concept ci = [dairy, dairy, veggie, meat, veggie]. To fix ideas, let's 's say that sentence is:
x
Jest [butter, yogurt, carrot, beef, lettuce]
(I)
This sentence hard to classify since there single sentence in the training set that has been generated by the same sequence of concepts, namely
X1,1 [cheese, butter, lettuce, chicken,
Moreover these two sentences do not overlap at all (i.e. the th word of test is different from the 7th word of X1,1 for all i.) To properly classify eestt the algorithm must have learned the equivalences butter < cheese, yogur! < bulter, carrot ++ lettuce and so forth. In other words, the algorithm must have learned the underlying concepts.
Nevertheless, a neural network with a well-chosen architecture can easily succeed at such a clas- sification task. Consider, for example, the network depicted on Figure 2 Each word of the input sentence, after being encoded into a one-hot-vector, goes through a multi-layer perceptron (MLP on the figure) shared across words. The output is then normalized using LayerNorm (Ba et al. 2016) to produce a representation of the word. The word representations are then concatenated into single vector that goes through a second multi-layer perceptron (MLP 2 on the figure).
3

---

Published as a conference paper at ICLR 2023
This network, if properly trained, will learn to give similar repre- sentations to words that belong to the same concept. Therefore, if it correctly classifies the train point X1,1 given by 2 it will nec- essarily correctly classify the test point x given by (1) So the neural network is able classify the previously unseen sentence x despite the fact that the training set contains single example with the same underlying sequence of concepts. This comes from the fact that the neural network learns features and representations from the familiar part of the training set (generated by the head of the distribution), and uses these, at test time, to correctly classify the unfamiliar sentences (generated by the tail of the distribution). In other words, because it learns features, the neural network has no difficulty handling the long-tailed nature of the distribution.
dbsc
MUP
rcr
narm
Fcm
p2m
MLP
MuP
chreees
butter,
lettoon
chidoer,
lock
Figure 2: A simple neural net.
To summarize, the variables L, Tl Re. R and nlll parametrize instances of our data model. They denote, respectively, the length of the sentences, the number of words the vocabulary, the number of concepts, the number of categories, and the number of samples per category. So in the example presented in Figure[[we have L 5. f = 12, n2 = 3, R = 3 and Rspl = (four familiar sentences and one unfamiliar sentence per cafegory). The vocabulary V and set of concepts C are discrete sets with VI = Thu and [C] = Yhe rendered as V = (1...., Mhe and C = (1....,77 ,?ee for concreteness.
A partition of the vocabulary into concepts, like the one depicted the top of Figure [ is encoded by a function
V + C that assigns words to concepts. We require that each concept contains the same number of words, so that yp satisfies
for all c C, 10 ((c)(( = H[ e V (p(w)= = c}} nw/nne /
(3)
and we refer such a function 0 V C satisfying (3 as equipartition of the vocabulary. The set
AIll functions yp from V to C that satisfy 3
denotes the collection of all such equipartitions, while the data space and latent space are denoted
X VL and
Z =
respectively. Elements of X' are sentences of I, words and they take the form x = [ar, 22; ......... vr.s while elements of Z take the form [ci, c2..... cr.) and correspond to sequences of concepts.
In the context of this work, a feature map refers to any function x/ X' + F from data space to feature space. The feature space F can be any Hilbert space (possibly infinite dimensional) and we denote by (, the associated inner product. Our analysis applies to the case in which nearest neighbor classification rule is applied on the top of the extracted features. Such rule works as follow: given a test point x, the inner products (1x)).. (()); are evaluated for all y in the training set; the test point x is then given the label of the training point y that led to the highest inner product.
STATEMENT AND DISCUSSION OF MAIN RESULTS
Our main result states that, in the context of our data model, features must be tailored (i.e. learned)
to each specific task. Specifically, it is not possible to find a universal feature map ié : X' - F that performs well on a collection of tasks like the one depicted on Figure [ In the context this work, task refers to a tuple
T= p CI...., CR ci...., cR
& Z
that prescribes a partition of the vocabulary into concepts, R familiar sequences concepts, and R unfamiliar sequences of concepts. Given such a task T we generate a training set S as described in the previous section. This training set contains nxpt sentences split over R categories, and each category contains single unfamiliar sentence. Randomly generating the training set S from the task T corresponds to sampling
S Dipin
from a distribution Dipin defined on the space X a and parametrized by the variables in (4) (the appendix provides explicit formula for this distribution). We measure performance of an
4

---

Published as a conference paper at ICLR 2023
algorithm by its ability generalize previously unseen unfamiliar sentences. Generating unfamiliar sentence amounts to drawing a sample
D
from a distribution D on the space X' parametrized by the variables p, .i....., CnR in (4) that de- termine unfamiliar sequences concepts. Finally, associated with every task we have labelling function fr X + .1...... R} that assigns the label to sentences generated by either C, or c (this function ill-defined if two sequences concepts from different categories are identical, but this issue is easily resolved by formal statements in the appendix). Summarizing our notations, for every task E & x z we have a distribution Di on the space X distribution Dipai on the space X, and labelling function fT.
Given a feature space F, a feature map &i X F, and a task T Φ x z the expected generalization error of the nearest neighbor classification rule on unfamiliar sentences is given by:
fr ((ag arg max max())xx, ((x))) * fr(x)) yES
err( F, 2b T)
E SwDii
(5)
For simplicity, if the test point has multiple nearest neighbors with inconsistent labels the training set (and so the arg max returns multiple training points y), we will count the classification as failure for the nearest neighbor classification rule. We therefore replace (5) by the more formal (but more cumbersome) formula
By E arg (ax()(()), v(y))> such that fr(y) + Fr(x)) ] yES
err( F,
(6)
S
D
make this explicit. Our main theoretical results concern performance of a learner on a single task T but on collection of tasks I = [Ti, T2,..., T J. and so we define
err( 1/
1
Σ TET
em( 1)
the expected generalization of the discrete set & x g2R, any subset I C $ x Z2R defines a collection of tasks. Our main result concerns the case where the collection of tasks = + Z2R consists in all possible lasks that one might encounter. For concreteness, we choose specific values for the model parameters and state the following special case of our main theorem (Theorem 33 at the end of this section)
such collection T of tasks. As task refers to element
Theorem 1. Let L = 9. nw 150. ne 5. R 1000 and Napt 2. Let I = ① Z Then
err Fr w. T > 98.4%
for all feature spaces F, and all feature maps 3b X + F.
In other words, for the model parameters specified above, it is not possible to design a 'task-agnostic' feature map & that works well if we are uniformly uncertain about which specific task we will face. Indeed, the best possible feature map will fail at least 98.4% of the time at classifying unfamiliar sentences (with a ncarest-neighbor classification rule), where the probability is with respect to the random choices of the task, of the training set, and of the unfamiliar test sentence.
Interpretation: Our desire to understand learning demands that we consider a collection of tasks rather than single one, for if consider only single task then the problem, in setting, becomes trivial. Indeed, assume T = {Ti} with Ti = (ạ;; Ci, CRi ci, CR) consists only of single task. With knowledge this task we can easily construct a feature map e X' - ILne that performs perfectly. Indeed, the map
(8) that simply 'replaces' each word It of the input sentence by the mne-hot-nncodig Op(xz) of its corresponding concept will d bit of thinking reveals that the nearest neighbor classification rule associated with feature map ( perfectly solves the task Tr. This is due the fact that sentences
= (eee(a.)............
We use ej denote the 4hh basis vector of TR So ( one-hot vector coding for the concept (p(re).

---

Published as a conference paper at ICLR 2023
generated by the same sequence of concepts mapped by & to the exact same location in feature space. As a consequence, the nearest neighbor classification rule will match the unfamiliar test sentence to the unique training sentence y that occupies the same location in feature space, and this training sentence has the correct label by construction (assuming that sequences of concepts from different categories are distinct). To put it formally:
Theorem 2. Given a task T x Z satisfying c, + and c, + c. for all r + 8, there exists feature space F and feature map v X + F such that err(F, v, (,,T)=0
Consider now the case where I {Ti, T2) consists of two tasks. According Theorem 2 there exists a v that perfectly solves Ti, but this vp might perform poorly on T2, and vice versa. So, it might not be possible to design good features if we do not know a priori which of these tasks we will face. Theorem [ states that, in the extreme case where I contains all possible tasks, this indeed the case the best possible 'task-agnostic" features v will perform catastrophically on average. In other words, features must be task-depender in order to succeed.
To draw very approximate analogy, imagine once again that 5 } and that Ti represents, say, a hand-written digit classification task. A practitioner, after years of experience, could hand-craft a very good feature map v that performs almost perfectly for this task. If we then imagine the case I = (Ti, ]2} where Ti represents hand-written digit classification task and T2 represents, say, an animal classification task, then becomes more difficult for a practitioner to handcraft a feature map & that works well for both tasks. In this analogy, the size of the set I encodes the amount of knowledge the practitioner has about the specific tasks she will face. The extreme choice I == + x z corresponds to the practitioner knowing nothing beyond the fact that natural images are made of patches. Theorem [ quantifiess in this extreme case, the impossibility of hand-crafting a feature map & knowing only the range of possible tasks and not the specific task itself. In realistic setting the collection of tasks I is smaller, of course, and the data generative process itself is more coherent than in our simplified setup. Nonetheless, we hope our analysis sheds some light on some of the essential limitations of algorithms that do not learn features.
Finally, our empirical results (see Section o show that a simple algorithm that learns features does not face this obstacle. We do not need knowledge of the specific task T in order to design a good neural network architecture, but only of the family of tasks $ = t x g2R that we will face. In- at classifying unfamiliar test sentences more than 99% of
deed, the architecture in the time. This probability, which we empirically evaluate, is with respect to the choice of the task, the choice of the training set, and the choice of the unfamiliar test sentence (we use the values of L, Tlw ne and from Theorem]] [ and 7ppl = 6, for this experiment). Continuing with our approxi- mate analogy, this means our hypothetical practitioner needs no domain specific knowledge beyond the patch structure of natural images when designing a successful architecture. In sum, successful feature design requires task-specific knowledge while successful architecture design requires only knowledge of the task family.
Main Theorem:
Our main theoretical result extends Theorem I to arbitrary values of L,, Paw Rey
Napp and R. The resulting formula involves various combinatorial quantities. We denote by (+) the
binomial coefficients and by {x] the Stirling numbers of the second kind. Let N = (0, 1, 1... ... and
let 7; 6: N4+1 + N be the functions defined by >(k) == Eltl(e (i - 1)k, and +(k) = Ei1 iks, respectively. We then define, for 0 < E S L, the sets
S = (k E N {kk) = nwe
and e 7 - L]-
We let S = Sy, and we note that the inclusion St c S always holds. Given k E N we denote by
L+1
Ax A N((+))x)
Σ -Ay--nwl = nw/no for all j and
Σ Auj =
for all i)
3=1
the set of k-admissible matrices. Finally, we let g: S - R be the functions defined by
f(k) :- ((nw/ne))
n
Σ
L+1
kd!
and
A A,2! ... Asmoo
AEAr
i=1
g(k) = 7(k)
L+1
()
Σ
2'
n 2L
ky
k
R141!
i=2
(=)(k)
6

---

Published as a conference paper at ICLR 2023
respectively. With these definitions at hand, may now state main theorem.
Theorem 3 (Main Theorem). Let I = ① x Z2R, Then
( 2
Σ kES
f(k)g(k)
1 R
1
max j(k)
(9)
2 KESt
for all feature spaces F, all feature maps vb X' + F, and all 0 SESL.
The combinatorial quantities involved appear a bit daunting at a first glance, but, within the context of the proof, they all take quite intuitive meaning. The heart of the proof involves the analysis of a measure of concentration that we call the permuted moment, and of an associated graph-cut problem. The combinatorial quantities arise quite naturally in the course of analyzing the graph cut problem. We provide a quick overview of the proof in Section 5 and refer to the appendix for full details. For now, it suffices to note that have formula (i.e. the right hand side of (9) that can be exactly evaluated with few lines code. This formula provides relatively tight lower bound for the generalization error. Theorem [ is then a direct consequence plugging
nuw 150, ne = 5, R = 1000 and & = 7 in the right hand side of (9) gives the claimed 98.4% lower bound.
4 MULTIPLE UNFAMILIAR SENTENCES PER CATEGORY
The two previous sections were concerned with the case in which each unfamiliar se- quence of concepts has a single representative the training set. In this section we consider the more general case in which each unfamil- iar sequence of concepts has n² representa- tives in the training set. Figure depicts an example with 7spl = 6 and n = 2. This means that each category contains total of Aspl = 6 sentences, and that n = 2 of these sentences are generated by the unfamiliar se- quence of concepts (the remaining four are generated by the familiar sequence of con- cepts). The other parameters in this example are 5, New = 12, n. and R = 3.
Figure 3: More general version of our data model.
Using simple union bound, inequality ( easily extends to this situation the resulting formula bit cumbersome so we present in the appendix (see Theorem 7.. In the concrete case where
L = 9, n. 150, 5. R = 1000 this formula simplifies to
er w. 5) 2 0.015 n - 1/R for all F and all v.
(10)
therefore exhibiting an affine relationship between the error rate and the number n of unfamiliar sentences per category. Note that choosing n 1 in (10) leads to 98.4% lower bound on the error rate, therefore recovering the result from Theorem | This lower bound then decreases by 1.5% with each additional unfamiliar sentence per category in the training set.
We would like to emphasize one more time the importance of non-asymptotic analysis the long- tailed learning setting. For example, in inequality (IO). the difficulty lies in obtaining value as small as possible for the coefficient in front of n²" We accomplish this via a careful analysis of the graph cut problem associated with our data model.
PROOF OUTLINE PERMUTED MOMENT AND OPTIMAL FEATURE MAP
The proof involves two main ingredients. First, the key insight of our analysis is the realization that generalization in our data model closely tied to the permuted moment of probability distribution. To state this central concept, it will prove convenient to think of probability distributions vectors E N with N = {X), together with indices < < N 1 given by some arbitrary (but fixed) indexing of the elements of data space. Then p; denotes the probability of the 7th element of
X' as

---

Published as a conference paper at ICLR 2023
X' in this indexing. We use Sy to denote the set of permutations of {0, (0.,....,A .N- 1} and a E Si to refer to a particular permutation. The tah permuted moment of the probability vector E RV is
N-1
HP(P) =
max dESy
Σ (i/N)' Po(1) T=0
(11)
Since [1 involves maximum over all possible permutations, the definition clearly does not depend on the way the set X was indexed. In order to maximize the sum, the permutation a must match the largest values of p, with the largest values of (i/N),, so the maximizing permutation simply orders the entries p, from smallest to largest. A very peaked distribution that gives large probability to only handful of elements of X' will have large permuted moment. Because of this, the permuted moment is akin to the negative entropy: it has large values for delta-like distributions and small values for is clear that 0 S (p) I for all probability vectors p. and
uniform ones. From definition it is easily verified that the permuted moment is convex. These properties, as well as various useful bounds for the permuted moment, are presented and proven in the appendix.
Second, we identify specific feature map, 3²" : X' - F*, which is optimal for collection of tasks closely related the ones considered in our data model. Leveraging the optimality of y* on these related tasks allows us to derive an eπrоr bound that holds for the tasks of interest. The feature map gi* is better understood through its associated kernel, which is given by the formula
(0))))((()))) = no Hi E & (((z)) = ((y)) for all 1 SSELs n
K (x = (1b e0 (y))s=
(12)
+
Up to normalization, K (x(x,)) y) simply counts the number of equipartitions of the vocabulary for which sentences x and y have the same underlying sequence of concepts. Intuitively this makes sense, for the best possible kernel must leverage the only information general structure of the problem (words are partitioned into concepts) but not the partition itself. So try and determine if sentences (x,y) were generated by the same sequence of concepts, the best we can do is to simply try all possible equipartitions of the vocabulary and count how many of them wind up generating (x, y) from the same underlying sequence of concepts. A high count makes more likely that (x,y) were generated by the same sequence of concepts. The optimal kemnel K** does exactly this, and provides a good (actually optimal, see the appendix) measure of similarity between pairs of sentences.
have at hand. We know the
For fixed x E X. the function y + K"((x y) defines probability distribution on data space. The connection between generalization error, permuted moment, and optimal feature map, come from the fact that
sup [1 - कπ +, J.
<
Σ XEX
H2R-1 (K*(x, +)++ R'
(13)
X
and so, up to small error 1/R, it is the permuted moments of K* that determine the success rate. We then obtain the lower bound ( by studying these moments in great detail. A simple union bound is then used to obtain inequalities such as I0h.
EMPIRICAL RESULTS
We conclude by presenting empirical results that complement our theoretical findings. The full details of these experiments (training procedure, hyperparameter choices, number of experiments ran to estimate the success rates, and standard deviations of these success rates), as well addi- tional experiments, can be found in Appendix F Codes are available at /tttps://g/t thub. com/
kbresson/LLong_ee Tail Lerd__Laaniii no
Parameter Settings. We consider five parameter settings for the data model depicted in Figure 3 Each setting corresponds to a column in Table [ all five settings, we set the parameters L = 9. nw 150, n. = 5 and At 1000 to the values for which the error bound (10) holds. We choose values for the parameters Napl and n² so that the hth column of the table corresponds to a setting in which the training set contains 5 familiar and unfamiliar sentences per category. Recall that Napt is the total number of samples per category in the training set. So the first column of the table corresponds to setting in which each category contains familiar sentences and unfamiliar
8

---

Published as a conference paper at ICLR 2023
Table 1: Success rate on unfamiliar test sentences.
n² n==1
n" =2
n' =3
n²=4
n²=5
nspl 6
napl -pp1=7
Repl =8
Mspl= 9
Repl 10 10
Neural network in Figure
99.8%
99.9%
99.9%
99.9%
100%
Nearest neighb. on features learned by neural net
99.9%
99.9%
99.9%
99.9%
99.9%
Nearest neighb. features extracted by ei*
0.7%
1.1%
1.5%
1.8%
2.2%
Nearest neighb. on features extracted by hot hot
0.6%
1.1%
1.4%
1.7%
2.1%
Theoretical upper bound (0.015m" + 1/1000)
1.6%
3.1%
4.6%
6.1%
7.6%
SVM on features extracted by ti
0.6%
1.5%
2.2%
3.2%
1.2%
SVM on features extracted by P'ne-boot hot
0.5%
1.1%
1.9%
2.8%
3.8%
SVM with Gaussian kernel
0.6%
1.1%
2.0%
2.8%
3.6%
sentence, whereas the last column corresponds to a setting in which each category contains 5 familiar sentences and 5 unfamiliar sentences.
Algorithms. We evaluate empirically seven different algorithms. The first two rows of the table correspond experiments in which the neural network in Figure trained with SGD and constant learning rate. At test time, we consider two different strategies to classify test sentences. The first row of the table considers the usual situation in which the trained neural network used classify test points. The second row considers the situation in which the trained neural network is only used to extract features (i.e. the concatenated words representation right before MLP2). The classification of test points is then accomplished by running nearest neighbor classifier on these learned features. The third (resp. sixth) row of the table shows the results obtained when running a nearest neighbor algorithm (resp. SVM) on the features v/ of the optimal feature map. By the kernel trick, these algorithms only require the values of the optimal kernel (v (x), 16 (y)))r computed via (2). and not the features zi themselves. The fourth (resp. seventh) row shows results obtained when running a nearest neighbor algorithm (resp. SVM) on features extracted by the simplest possible feature map, that is
Wone-hot hot ([z1,...,
(c2,. Cr,
where eze denotes the one-hot hot-encoding of the gth word of the input sentence. Finally, the last row considers a SVM with Gaussian Kernel (also called RBF kernel).
The first two rows of the table correspond to algorithms that learn features from the data; the remaining rows correspond to algorithms that use a pre-determined (not learned) feature map. Table reports the success rate of each algorithm on unfamiliar test sentences. A crystal-clear pattern emerges. Algorithms that learn features generalize almost perfectly, while algorithms that do not learn features catastrophically fail. Moreover, the specific classification rule matters little. For example, replacing MLP2 by a nearest neighbor classifier on the top of features learned by the neural network leads to equally accurate results. Similarly. replacing the nearest neighbor classifier by a SVM on the top of features extracted by zi* or Voue-hot leads to almost equally poor results. The only thing that matters whether or not the features are learned. Finally, inequality (T)) gives an upper bound of 0.015n" + 1 1/1000 on the success rate of the nearest neighbor classification rule applied on the top of any possible feature map (including g/* and Wone-hoot). The fifth row of Table I compares this bound against the empirical accuracy obtained with 16* and Wone-hot. -ott and the comparison shows that our theoretical upper bound is relatively tight.
Results.
When n. = our main theorem states that no feature map can succeed more than 1.6% of the time on unfamiliar test sentences (fifth row of the table). At first glance this appears to contradict the empirical performance of the feature map extracted by the neural network, which succeeds 99% of the time (second row of the table). The resolution of this apparent contradiction lies in the order of operations. The point here is to separate hand crafted or fixed features from learned features via the order of operations. the algorithm performs poorly since it uses unlearned, task-independent features. By contrast, the neural network learns a feature map from the training set, and since the training set is generated by the task, this process takes place after the random selection of the task. It therefore uses task- dependent features, and the network performs almost perfectly for the specific task that generated its training set. But by our main theorem, it too must fail if the task changes but the features do not.
we choose the feature map before the random selection the task then

---

Published as a conference paper at ICLR 2023
Acknowledgements. Xavier Bresson is supported by NUS-R-252 222-0000-B97-133 and A*STAR Grant ID A20H4g2141.
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? Ad- vances in Neural Information Processing Systems, 32, 2019.
Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning. arXiv preprint urXiv:2001.044111 2020.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. International Conference on Machine Learning, pp. 242-252. PMLR, 2019.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pp- 254-263. PMLR, 2018.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey Hinton. Layer normalization. arXiv preprint arXiv: 1607.06607 2016.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalizeed margin bounds for neural networks. Advances neural information processing systems, 30, 2017.
Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar. When memorization of imrlevant training data necessary for high-accuracy learning? In Proceedings of the 53rd Anmual ACM SIGACT Symposium on Theory of Computing, pp. 123-132, 2021.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a library for support vector machines. ACM trans- actions on intelligent systems and technology (TIST), 2(3):1-27, 2011.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.0205. 2018.
Vitaly Feldman. Does learning require memorization? a short tale about a long tail. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 954 959, 2020.
Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. Advances in Neural Information Processing Systems, 33:2881- 2891, 2020.
Behrooz Ghorbani, Song Mci, Theodor Misiakiewicz, and Andrea Montanari. Limitations of lazy training of two-layers neural network. Advances in Neural Information Processing Systems, 32, 2019.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? Advances in Neural Information Processing Systems, 33: 14820-14830, 2020.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size- Size-independent sample complexity of neural networks. Conference On Learning Theory, pp. 297-299. PMLR, 2018.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, 31, 2018.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbi- trarily small test eroor with shallow relu networks. arXiv preprint (xXiv:1909.12200 12292, 2019.
Stefani Karp, Ezra Winston, Yuanzhi Li, and Aarti Singh. Local signal adaptivity: Provable feature learning in neural networks beyond kernels. Advances in Neural Information Processing Systems, 34, 2021.
Yuanzhi Li, Tengyu Ma. and Hongyang R Zhang. Learning over perammrmmtreized two-layer neural networks beyond ntk. In Conference on learning theory, pp. 2613-2682. PMLR, 2020.
10

---

Published as a conference paper at ICLR 2023
Ziwei Liu, Zhongqi Miao, Xiaohang Zhan, Jiayun Wang, Boqing Gong, and Stella X Yu. Large- scale long-tailed recognition in an open world. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2537-25444 2019.
Eran Malach, Pritish Kamath, Emmanuel Abbe, and Nathan Srebro. Quantifying the benefit of using differentiable learning over tangent kernels, In International Conference on Machine Learning, pp. 7379-7389. PMLR, 2021.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A Pac-Bayesian approach to spectrally-normalizeed margin bounds for neural networks. arXiv preprint arXiv:1707.09564 2017.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. To- wards understanding the role of over-paramettization in generalization of neural networks. arXiv preprint arXiv: 1805, 2018.
F. Pedregosa. G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Maria Refinetti, Sebastian Goldt, Florent Krzakala, and Lenka Zdeborová. Classifying high- dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed. In International Conference on Machine Learning, pp. 8936-8947. PMLR, 2021.
Ruslan Salakhutdinov, Antonio Torralba, and Josh Tenenbaum. Learning to share visual appearance for multiclass object detection. In CVPR 2011, pp. 1481-1488. IEEE, 2011.
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets vs their induced kernel. Advances in Neural Information Processing Systems, 32, 2019.
Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Xiangxin Zhu, Dragomir Anguelov, and Deva Ramanan. Capturing long-tail distributions of object subcategories. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recogni- tion, pp. 915-922, 2014.

---

Published as a conference paper at ICLR 2023
Appendix
In Section A we prove few clementary properties of the permuted moment devoted the proof of inequality (13). which we restate here for convenience:
Section B is
sup
[1 - e v 5) :/
Σ XEX
H2R-1 (K :))
(14)
X
where the collection of tasks T = + x 22R consists in all possible tasks that one might encounter. Inequality (14) plays central role our work as it establishes the connection between the gen- eralization error, the permuted moment, and the optimal kernel K* defined by (12). The proof is
non-technical and easily accessible. In Section we provide following upper bound on the permuted moment of the optimal kernel:
Σ XEX
H2R-1 (K* (x, -)) - 1 Σ ((k)((k) KESt
+
max f(k)
(15)
2R
KES,
for all 0 S.S. S L. The proof is combinatorial in nature, and involves the analysis of graph-cut problem. Combining (14) and (15) establishes Theorem 3 In Section D we consider the case in which each unfamiliar sequence of concepts has n" representatives in the training set. A simple union bound shows that, in this situation, inequality (14) becomes
sup [1 eT 1 {)] F. F.
n* X
Σ XEX
H2n-1 (K :)
1
(16)
Combining (16) and 15 then provides most general eπror bound, Theorem 7 (10) in the main body of the paper is just a special case Theorem 7 Finally, in Section E we provide the full details of the experiments.
Inequality
A PROPERTIES OF THE PERMUTED MOMENT
The permuted moment, in Section 5 defined for probability vectors only. It will prove conve- nient to consider the permuted moment of nonnegative vectors as well. We denote by R. = [0, +oo) the nonnegative real numbers, and by R. the vectors with N nonnegative real entries indexed from i 0 to N - 1. The permuted moment of E RR- then given by
N-1 (1/N)* Ua())
(u)
=
max dESN
(17)
1=0
where Sy denote the set of permutations (0,1.... - 1}. The concept of an ordering permu- tation will prove useful in the next lemma.
Definition 1. E Sy is said to be an ordering permutation of E RN if
Ua(0) S (a(l) .... S NN(NN-))
(18)
The lemma below shows that the permutation maximizing 17 is the that sorts the entries u. from smallest to largest. Lemma 1. Let E R and let be an ordering permutation of u. Then
N-1
a" E
arg max DESN
(i/N)* ua(1)-
(19)
100
Proof. The optimization problem 19) can be formulated as finding a pairing between the u, 's and the (i/N)'s that maximizes the of the product of the pairs. An ordering permutation of corresponds to pairing the smallest entry of u to (O/N)', the second smallest entry to (1/N)5, the third smallest entry (2/N)*, and forth. This pairing is clearly optimal.
12

---

Published as a conference paper at ICLR 2023
In light of the previous lemma, that computing the permuted moment of vector can be accomplished as follow: 1) sort the entries of u from smallest to largest; 2) compute the dot product between this sorted vector and the vector
[(*)
(
(20)
Let us now focus the case where is probability distribution. If is very peaked, it must have a large permuted moment since, after sorting, most of the mass concentrates on the high values of 20 located the right. On the contrary. if is very spread, it must have small permuted moment since it 'wastes' its mass on small values of (20). Because of this, the permuted moment is akin the negative entropy; it has large values for delta-like distributions and small values for uniform ones.
We now show that the permuted moment subaddiditive and me-hooogeeeouu on E (as a con- sequence it is convex on the set of probability vectors) and we derive some elementary & and loo bounds. We denote by ||u||p the nn-norm of a vector u. particular, RN have
N
| =
and
|uulo == max U.
OSigN-1
==0
With this notation in hand, we can now state our lemma:
Lemma 2. (i) Hu(u + Hu(u) + He(v) for all u, R
(i) Hi(cu) (u) for all E E and all 2 0.
(iii) (u) ||u|| for all u R
(iv) (u) N
Iullo for all u E RN
Proof. Properties (i) and (ii) are obvious. To prove (iii) and (iv), define wy = (i/N)² and note that
1 N-1 (1/N))
NN f r' N
and
|| = N
N
t t+1
Then (iii) comes from Hy(u) S ||w||o/||l]] whereas (iv) comes from H.(u) S [ w|11 |u/loo
We conclude this section with slightly more sophisticated bound that holds for probability vectors this bound will play central role in Section C
Lemma 3. Suppose N. and suppose
Σ Pi 1. Then
Di=1
N-1 min (pi, 21
AN
Ha(p) S
for all X 2 0.
Proof. Fix À and define the vectors and follow:
for all 0 S i i N - Note that this two vectors are non-negative and sum to p. We can therefore use Lemma to obtain
Mi min(p:.>) A}
and 0 min A}
N |u/|=0 + ||v||
Ha(p) (u + Hu( + 74(v) ++1
To conclude, note that ||u||/o A, and |
Σn' min (p.
13

---

Published as a conference paper at ICLR 2023
B PERMUTED MOMENT OF K* AND GENERALIZATION ERROR
This section is devoted to the proof of inequality (4). We start by recalling few definitions. The vocabulary, set of concepts, data space, and latent space are
V = [l.....,w) ). C = -l....,,mch
Y VZ
and
2 = C
respectively. Elements of X' sentences of L words and they take the form [a1, 22 ................................ 2 ILIs while elements 2 take the form с = [e,, C2...., Cr] and correspond to sequences of concepts. We also recall that the collection of all equipartitions of the vocabulary is denoted by
All functions y from V that satisfy | ({c])] se for all
where 8c = /n/ denote the size of the concepts. Given yp E 4, we denote by & X + the function
([x 22 .... zL]) [1(z)), ((22), ..... (((L)]
that operates on sentences element-wise. The informal statement "the sentence x is randomly gen- erated by the sequence of concepts c" means that is sampled uniformly random from the set
((c)) = (x X (((x) = c}.
(21)
We will often do the abuse of notation of writing (c) instead of ((c)() We now formally define the sampling process associated with main data model. Sampling Process DM:
ii Sample T = ( ( Cl...., CR CR uniformly at random in I = x Z
(ii) For r = 1,..., R:
Sample (Xr,1,..., , ara uniformly random 3-) x... (c,) Sample (Xrimmeth>>. Xp uniformly at random in & (c,) x x x (ct).
(ii)
Sample xlest uniformly random in g (c)))
Step (i) of the above sampling process consists in selecting random task T among all possible tasks. Step (ii) consists in generating a training se S Rt exactly depicted on Figure each unfamiliar sequence of concept c, generates Tuunf sentences, whereas each familiar sequence of concept generates Maam sentences (recall that the number of samples per category is Rspl Nauf + ). Finally step (iii) consists in randomly generating an unfamiliar test sentence xesst E X. Without loss of generality assume that this test sentence is generated by the unfamiliar sequence of concept c/.
We denote by @DM the p.d.f. of the sampling process DM. This function is defined on the sample space
Ppm = ( x C2ll) x Nxx x X
sample from ΩDM takes the form
w p C1. CR ...... CR X1.1 X1,na .... ......g... XR,1 ... X XR
test The test sentence
The task
The training sentences
and we have the following formula for @DM
1 13-1(c)) (X,,
Thpt
* (er) (Xr,a) 1/ ((,,))
1--1 (x(0s)
(DM(W)= + | 2R
II
(22)
(
140 (c()
where 1g-1(e,) and 1 (eg) denote the indicator functions of the set à (c,,) and vo- (c,) respec- tively. Let compute few marginals of @DM order to verify that it is indeed the p.d.f. of the
We refer the "training set'. In our formalism however is set, but element of X Rx
14

---

Published as a conference paper at ICLR 2023
sampling process DM. Writing w (T, S, ".x" summing over the variables S and x and using the fact that ExEx 1 (e) (x) = 18 (c), we obtain
Σ Σ @DM (T,,,,,,,,, x
+ |
SEC2R XMEX
This shows that each task T is equiprobable. Summing over the variable S gives
(e) (x lest)
Σ
(T, S,
SECOR
This shows that, given task T, the test sentence xles is obtained by sampling uniformly random from (c)) A similar calculation shows that, given a task T. the train sentence Xy,s is obtained by sampling uniformly at random from 3 (c,, 8 2 1, and from (c,( if 1.
Given feature space F and feature map X F, define the events E Ωpm as follow:
EF,y = {wr SDM: : There exists 1 1 s I napl such that
(W(xx (x(x1,))) (1b(x (x+, for all 2 r S R and all S 8 1 Mspl
(23)
Note that this event consists in all the outcomes w = (T.S, for which the feature map &i associates the test sentence xlest to train point x,,, from the first category. Since by construction, xest belongs to the first category, E consists all the outcomes for which the nearest neighbor classification rule is 'successful'. As a consequence, when + 22R the generalization error can be expressed as
Jt 1/. 3) = 1 IPM Fs.
(24)
where PM denote the probability measure on 9pm induced by 2DM- Equation (24) should be viewed our 'fully formal' definition of the quantity CTT(F, v,, F), opposed the more informal definition given earlier by equations (6) and 7p.
The goal of this section to prove inequality (4). which, in light of 24 equivalent to
1
sup PDM Fr,
I
Hzn-1 (K*(x, ))
(25)
X
R
XEX
which in turn equivalent to
sup K:X'x x
PDM
EK
S
1
Σ
(K*
1
(26)
pos.
where the event Eg is defined by
Ex {w E 9DM
There exists S s* < nspl such that
K(x ((x.s))) > K(xtes x,.s) for all 2 r S R and all 1 S S m (27)
and where the supremum is taken over all kernels X' x X + IR which are symmetric positive semidefinite. We will actually prove slightly stronger result, namely
sup X Kis symmetric
PDM
Ex
1
Σ XEX
Han-1 (K :)
1
(28)
|
R
where the supremum taken over all functions X' R that satisfy K(x,y) K(y.x) x)
for all y) E X' x X. The rest of the section is devoted to proving (28).
In Subsection B.I we start by considering a simpler data model for this simpler data model we are able to show that the function gi* implicitly defined by (12) is the best possible feature map (we actually only work with the associated kernel K*, and never need 3 itself). We also show that the success rate is exactly equal to the permuted moment of K see Theorem 4 which is is the
central result of this section. In the remaining subsections, namely Subsection B.2 and Subsection
B33] we leverage the bound obtained for the simpler data model in order to obtain bound (28) for the mai data model. These two subsections are mostly notational. The core of the analysis takes place in Subsection B.1
15

---

Published as a conference paper at ICLR 2023
B. A SIMPLER DATA MODEL
We start by presenting the sampling process associated with our simpler datamodel.
Sampling Process SDM:
(i) Sample yp uniformly at random in Φ. Sample C1 C2,..., C uniformly at random in 2.
(ii) For 1 r 5t 1: Sample x, uniformly at random in -
(iii) Sample xlest uniformly at random in (c1).
The function
1 (c. (x+) Il
1, (x
@SDM (1) CI.....
C1 Xx41ix
+ cil+t
(c,)
(8-1(c))
(29)
on ΩSDM 4 x C++1 x x is the p.d.f. of the above sampling process. We use PSDM to denote the probability measure on QşD induced by this function. The identity in the next theorem is the central result of this section.
Theorem 4. Let K denote the set of all
from X x N to R. Then
sup PSDM K [x*tta x1) K( (xxt0 for all S Sr KEK:
1
Σ H.(K))
(30)
X
30), K stands for the function K(x,) :). Theorem establishes an intimate connection between the permuted moment and the ability of any fixed feature map (or equivalently, any fixed kemel) to generalize well our framework. The sampling process considered in this theorem involves two points, x and X1, generated by the same sequence of concepts C1, and 'distractor" points X2,...,Xett generated by different sequences of concepts. Success for the kernel means cor- rectly recognizing that x is more 'similar' X1 than any of the distractors, and the success rate in (30) precisely quantifies its ability to do so as a function of the number t of distractors. The theorem shows that the probability of success for the best possible kernel this task is exactly equal the averaged tt --ermutedd moment of K so it elegantly quantifies the generalization ability of the best possible fixed feature map in term of the permuted moment. We also provide an explicit construc- tion for kernel K K(x, y) that achieves the supremum in 30 satisfies
First, choose a kemel s(x, y) that
E X' with + z. (i) c(x,y) E(xx z) for all x, y,
(ii) < y(x S for all x, E
and then define the following perturbation
x + 5 +xx, (2
(31)
of K*, Any such kernel is maximizer of the optimization problem in perturbations of K** as bona-fide optimal.
30 so we may think of
The rest of this subsection is devoted to the proof of Theorem 4 and we also show, in the course of the proof, that (31) is maximizer of the optimization problem in (30). We use IC denote the set of all symmetric functions from X' x X to R. We will refers to such functions as 'keree'' despite the fact that these functions are not necessarily positive remi-definite.
Proving Theorem 4 requires that we study the following optimization problem:
Maximize ((K) : PSDM K( x1) > K(x x,) for all 2 s1rist1
(32)
over all kernels K E KC We recall the definition of the optimal kernel,
(33)
Hp 2 p(zs) ((v)) for all 1585
Kt (*
(34)
st.
where 8, news.. Sa denotes the size of concept. We start with the following simple lemma:
16

---

Published as a conference paper at ICLR 2023
Lemma 4. The function K-(-) K* (x,,)) -) is probability distribution X.
Proof. First note that K** can be written
Hp & ((() = {(y))
K* y)
Σ
1100000001
(35)
cc
(
PED
Since maps exactly se words to each concept e E , we have that
Xxx X: (x() =c} = =t
for all E C.
(36)
Therefore
Σ (x,))
Σ Σ (((x)))()))
Σ Eyy E x: ;()) = =1
st
yEA
yE
PEd
We now show that the marginal of the p.d.f. @SDM is related to K Lemma 5. For all X and xtest in X we have
ΣΣ-..
CI,,.. Co11i Xt+1ix (est)
| K* (x11)
CIEC
cr+1EC
Proof. Identity (36) can be expressed as (c) = for all c C. As consequence, definition 29 of @SDM (w) simplifies
+++1
(WDM(W)= =
II
1 (a-1(c))(x))) (x,) 1 13-1(e,)
(37)
where the constant given by
b c ((+22)
L(t+1), L(t+2)
| ++
50
In the above we have used the fact that |C| no and | ny. 1a (x) = (((x)==)) implies
We then note that the identity
[x)-(0(x)= Σ 11(x0==0=1 =1
(38)
CEC
CEC
Σ (1s (x) 1s (()(8)) eEC
Σ
(114())=e) 1((())=o))
1 ((0))=(01)
(39)
aEc
for x, E X. Summing 37
over the variables Cı,... c++1 we obtain
2+1
Σ Σ
(SDM(W)
Σ
Σ
1s (x)))(1)) 1s (x
II 1 (c.))
CrEC
citiec
CrEC
EHTEE
r=2
H+1
=a Σ
1s (x1) 1s (x!e))
Σ
Σ C1+1EC
II Ar=
1
(x,)
CLEC
E2EC
(0(x)==((xx)
where we have used
38 and
39 to obtain the last equality. Summing the above over the variable
gives K (x1,,,x
The next lemma provides a purely algebraic (as opposed to probabilistic) formulation for the func- tional ((K) defined in (32).
17

---

Published as a conference paper at ICLR 2023
Lemma 6. The functional é KC - R can be expressed as
K(x, 2) < K xx,
ε(K) = Σ Σ
yx
(40)
[
|
XE XE yEA
Proof. g: g: X²+2 x X + {0, } be the indicator function defined by
X teM K) {
if K( x1) K (x!est x,) for all 5
otherwise
Let denote the sample (ip; C1 Cc+13 X1, XI.... x(+1;x Since g only depends the last ++2 variables of w, we have
((K) = PSDM
K(x tex x1)
K(x lest x,) for all 2 25
(41)
Σ
Σ
Σ
Σ
Σ
g(x x(x1 10st K) @SDM(W)
(42)
PEO ciEC
Cc+1EC XIEX
X++iEX x
Σ
Σ
Σ
g(x1 X(+1, x Jest K)
Σ ΣΣ ... Σ eSDM((W)
(43)
XIEX
Xi+IEX xooEX
Deb CIEC
Ci+iEC
Σ
Σ
E
g(X1.....
X less R)
|8 (x1,))
(44)
X1EX
XiJIEX X"EE
EE
1
K Xx)
Σ
K)
(45)
X
X X
X
X41EEX
where we have used Lemma 5 to go from to of indicator functions,
Writing the indicator function y as a product
++
g(x X, lest K)
1
we obtain the following expression for the term appearing between parentheses 45
t-1
Σ
Σ
g(x1,
X141, xest
test K)
=
II
Σ
(K
x)) xx))
X
X1FIEX
r=2
XXEX
1
1 K(emm,
REX
liz X K K(xeest x1) K (xeeett
2)
|
x Changing the name of variables xlest, X1 to y gives 40
33 into an equiv- alent optimization problem over symmetric matrices. Putting arbitrary ordering on the set X (starting with i = 0) and denoting by Kł, the value of the kernel K on the pair that consists of the can be written as
We now use expression 440 for E(K) and reformulate optimization problem 32
tth and jth element of X, see that optimization problem
32
33
1 N-1N-1
Ki
[N]
Kiy < Ko)l)
Maximize
C(K) = ΣΣ
K
(46)
N
1=
over all symmetric matrices K R
NxN
(47)
18

---

Published as a conference paper at ICLR 2023
In the above have used the letter N to denote the cardinality of X, that is N = = and have used the notation [N] = {0, ,,..., - -1.. Before solving the matrix optimization problem
466-447 start with simpler vector optimization problem. Let p" be probability vector, that p E R. with Σ ps and consider the optimization problem:
N-1
(115'
[M] : by < <
Maximize
c(v)
Σ pz 5=0
(48)
N
over all vector E RN..
(49)
Recall from Definition ! that an ordering permutation vector v is permutation that sorts its entries from smallest largest. We will say that two vectors v, E IR have the same ordering if there exist a E SN which ordering both v and w. The following lemma is key - shows that the optimization problem (48 49 has simple solution.
Lemma 7. The following identity
sup e(v) = He(p")
VERN
holds. Moreover, the supremum is achieved by any vector v E RR that has mutually distinct entrie and that has the same ordering than p"
Proof. Let Distinct(R**) denote the vectors of R that have mutually distinct entries. We will first show that
sup c(v)
sup VEDisinet(EMM)
c(v).
(50)
VERN
To do this we show that for any E R.,, there exists w E Distinct(Re)) such that
Ht'' [N] ey < ey S Hi [N] wy wj}H for all 0 S -
(51)
There are many ways to construct such w. One way is to simply set wi oj' for some permutation that orders v. Indeed, note that o (j) provides the position of vy in the sequence of inequality (18). Therefore if uy < 0y we must have that o (0"(j") < This implies
(j' [M]: uy < <;) c (j' E [N] :0 -0" <0)
for all j E [N]
which in turn implies 5T
restrict attention to E Distinct(RA\). Note that if v Distinct(R then it has unique ordering permutation a,
Because of (50)
va(()) (n(1) (o(2) Un(3) <... Vo(N-))
and, recalling that "i) provide the position of vy in the above ordering, we clearly have that
HD's [M] o/ < = o
Therefore, if v Distinct(R.M) and if a denotes its unique ordering permutation, c(v) can be expressed as
10' [N] by < =
N-1 Σ Paus (i/N)* (52)
e(v)= = Σ
Σ p
P3
Looking definition 11 of the permuted moment, it is then clear that e(v) Hy(p') for all E Distinct(1R*".. We then note that if v E Distinct(I has the same ordering than p", then its unique ordering permutation must also be an ordering permutation of p*. Then (2)) combined with Lemma implies that e(v) = Mp(p*). This concludes the proof.
Thht is, ii my for all
19

---

Published as a conference paper at ICLR 2023
Relaxing the symmetric constraint in the optimization problem 46 strained problem over all ---y-- matrices:
47
gives the following uncon-
1 N-1N-1
[N]: K, < <Koll)"
Maximize
E(K) == N
ΣΣ K
(53)
N
2 1=0
over all matrices K N
(54)
Let denote by KT: the ith row of the matrix K* and remark that K?, is probability vector (because (x, -) is probability distribution on A' see Lemma 4. We then note that the above unconstrained problem decouples into N separate optimization problems of the type (48)- 49 in
which the probability vector p must be replaced by the probability vector K Using Lemmal therefore have that any K R. NxN that satisfies, for each 0 S
(a) The entries of K2 mutually distinct, (b) Ki, and K have the same ordering.
must be a solution of 53 54 Lemma
7 also gives:
sup C(K) N
Σ
H.(K).)
KERNNN
==0
Now let E E NxN be a symmetric matrix that satisfies:
(i) Eij + Eg for all j.j.j' e [N] with J
(ii) 0 < εy < for all i,j E [N].
and define the following perturbation of the matrix K":
K = K
E
(55)
Recalling definition
35 of the kernel K", it is clear that for each i, J E (N), we have
KЛ
for some integer f.
(56)
As consequence perturbing K* by adding to its entries quantities smaller than 1/ 1/(52 (+]) can not
change the ordering of its rows. Therefore the kernel defined by (55) satisfies (b). also satisfies (a). Indeed, if Ki = K and j * j'. then we clearly have that K, 7 Kig due to (i). On the other hand if Kij * kig. then K, + Kij' due to (ii) and (56).
We have therefore constructed symmetric matrix that is solution of the optimization problem As a consequence we have
53 (4).
sup E(K)
sup KERN
C(K) 1
Σ H((K))) 1=0
KER
N
where K. should now be interpreted the set of N- N-by-N symmetric matrices. The above equality
proves Theorem 4 and we have also shown that the perturbed kernel (53) achieves the supremum.
B.2 CONNECTION BETWEEN THE TWO SAMPLING PROCESSES
In this subsection we show that the p.d.f. of Sampling Process SDM can be obtained by marginal- izing the p.d.f. of Sampling Process DM over subset of the variables. We also compute another marginal of (Dm that will prove useful in the next subsection. Recall that
IR II
(e-1(e))
That
1 (e,)(c,)) (Xr,
1 ((f (xtest)
(DM(W) =
(57)
+
2R
3 (c((),,)
[c())
2
20

---

Published as a conference paper at ICLR 2023
on AD + C X Rx is the p.d.f. of the sampling process for main data model.
Samples from fDM take the form
(0 C1 C2 C3. CR
cj c3..... C'R
X1,1, X X1, 31,3 Min ... Kn,1,XR,23 X12,3,---
.. ; xlest)
We separate these variables into two groups, w (w,ww)) where
Wa = (p C2 C3....,
c₁, C2. ,y....,, nn X1,1,X122
X,,1,X
x!xx)
(58)
Wb = (X1,3, X1,4.
Xm ;
n,3, X1,4, X.)
(59)
The variable wa belongs to Ωr + x x x 2 and the variable w/ belongs to S2 X Re
Note that the variables in w/ contains, among other, 2R sequences of concepts and 2R training points (the first and second training points of each category). Each of these 2/t training points is generated by one of the 2/t sequences of concepts. So the variables involved in wa are generated by a process similar the one involved in the simpler data model. The following lemma shows that p.d.f. of wa. after marginalizing wb, is indeed @SDM-
Lemma 8. For all Wa E Su we have
R II
1 (e (e,)
(e, (x,,))) 16 (c,))
(
L (e; (ct) (x(ee)) 13--((c) (cDi
LDM (Waswb)
(c,,)
Recalling the definition 29 of @SDM, and letting t + 2R, that the above lemma states that
Σ E
(WM wa) (SDM(Wa)
(60)
and Qa = QSDM
Proof of Lemma g We start by reorganizing the terms involved in the product defining @DM so that the variables in and wh are clearly separated:
@DM(W)
R 1s (o)) (x,, (ct)
1g (c..) (c.)) (x,,2)
1 Vee (el (et) (xtees)
R Flip (in ==3
a ((.)) (XCr,s)
II
| |||
bs (c,)]
To demonstrate the process, let us start by summing the above formula over the first variable of wb. namely X1,3. Since this variable only occurs in the last term of the above product, we have:
1. ((e (x)..) 1 (o-((c.) (x.:)) II
1 [s=1(ef)) (x
Σ (w) X1
(
|0|
8 (c))
1/ (c,)
(c())
1 1x-1)))
1 1 (o)1(o)))111) 16 1--(()1]]
(6 (c,,)]
ISrER 35eEnal (1,3)
X1.EX
Since Exex 13-1(a)) (x) = (c> the last term of the above product equal to 1 and can therefore omitted. Repeating this process for all the x,,s that constitute w/ leads to the desired result.
In the next subsection we will need the marginal of @DM with respect to another set of variables. To this aim we write w = (wie, wix) where
We = (pp X1,2, X1.3 X1,
XR,,, W1 = (CI...., Cn c..... cnn X1,1 ; xR,1)
XR,
x
reat
(61)
(62)
Note that all the unfamiliar training points are contained wa. The test point and the familiar training points are in w. We also let Ω. = + R(n -1++1 and Ω4 C2R x RR.
21

---

Published as a conference paper at ICLR 2023
Lemma 9. For all We Dee we have
R II
Σ aa
(DM(We; wa)
(a(x..)) ((x..)) (00...)))
|
LR( R+1 bc
Proof. We reorganizing the terms involved the product defining 2DM so that the variables in we and wid are separated:
(x-1(c)) (x- 18 (ci)
) (ii 1. (ee (x,,,)
QDM (w)
||
(cx)())))
Summing the above formula over the last variable involved in wa, namely XR,1, gives
R Fegt
(c,, (Xx.)))))))
(
1 (1-1(07)
Σ (DM(W)= = |
183-(cc9)
XR.IEA
R-1 1 - -
1. (cc)) (xR.1)
II
Σ
(3-1()))
(3-2(
XR,EEX
The term the above product is equal to and can therefore be omitted. Iterating this process gives
R Auai
* 1e, 16,,) (Xr,e)
)
) (
1 (e-)(e)) (x
Σ
Σ
(DM(W)= =
( |
18 (c,)]
(-8-1(c1))
X1I
XR.EE
<= 8=2
We then use the fact that Edec (c)) obtain
1, see
38
together with
1 = 5/6 see
36
R Rlpt
a (c..) (x),
ΣΣ
E (DM(W)= = [ CR
1/3 (c,))
cfECx,,ER xX
EX
XRIEE
We then sum over c2 .... CR. Since these variables are not involved in the above formula we
R Nap
1 (x,.)()r,))
Σ E... cfec
Σ Σ
Σ XR,
(DM(WW) = + sh
IIII
16 (c,)l
Tg,
1=1
R Post
p (e (X),ss))
- (c,]l
1=
where we have used [C]s = n T. = | to obtain the last equality. Summing over e1 gives
1. ((c,) (x,,s)
ΣΣ Σ CIEC EfC
Σ
(DM(W))
1 (cr)
CREC X1.1
Xn.
CIEC
R Thpl
(c,, (Xr:o)
ΣI
1 (e (x1))
||
1 (c,)]
18 (c,])
( (x),))
(c,)
|
To obtain the last equality we have used 139 but for product of Napl of just two. Iterating this process we obtain
indicator functions instead
Σ
ΣΣ...
Σ
Σ
Σ XR.EEX
(DM(W)
(+(x).)) ((
C
C
1 moa
CLEC
CRECEEEC
Using more time that [
o and Cl |2' gives to the desired result.
22

---

Published as a conference paper at ICLR 2023
sequences of concepes (latet variables)
15 sentences (the training set)
Test point
bxtter
ketter
cedee
pack
chone
lotter
batte
batter
Jasy sipll cost
mome
betler
petats
Ax
chiders
ChrO
RAS
caly)
daly. Gay
Viga
CTREE
leas
Categgoy
bratee
Lexs
Figure 4: The test point x and the train point X1,1 are generated by the same sequence of concepts.
B.3 CONCLUSION OF PROOF
We now establish the desired upper bound (28).
which we restate below for convenience:
1
sup IDMM
EK
H2R-1 (K ))
(63)
KeK
X
xEX
where
Ex {wr 4pm
There exists S 5* S Repl such that
K (x!eM x1,--) K (xtea x,,)) for all 2 2 S R and all 1 S S ngd (64)
We recall that the test point x jest is generated by the unfamiliar sequence of concepts of and that belongs to category 1, see Figure The event Ex describes all the outcomes in which the training point most similar to xles (where similarity is measured with respect to the kernel K) belongs to the first category. There are two very distinct cases within the event Ex: the training point most similar to test can be X1,1 this corresponds to a 'meaningful success' which the learner recognizes that x1,1 is generated by the same sequence of concepts than xtest Figure 4 Or the training point most similar to xtest can be one of the points X X1, X1,ng - this corresponds to a 'lucky success' because X1,2...., Xi,ng are not related to test (they are generated by a different sequence of concept, Figure To make this discussion formal, we fix kernel K K, and we partition
the event E'K as follow
EK Emeaningtul U Ejuck
(65)
where
Emeaningtul = EK n {w E Spm: K (x!est x1,1) K (xeest, x1,e) for all 2 S s S napl
Frnck FK n tw 0pm: K (x x1,1) S K (xtes, x1,)) for some 2 S & S nyp!
The next two lemmas provide upper bounds for the probability the events Emsaninguul and Ejuck Lemma 10. PDM Emmcningfar] S
Σ
H2R-1(K²)
X
XEX
23

---

Published as a conference paper at ICLR 2023
Proof. Define the event
A = w esMM: K (111) > K (x,1), for 2 S R
n now E K (x xx.1) K (x xx.2) for all 1 Sr S R...
This events involves only the first two training points of each category. On the example depicted on Figure 4 that would be the points X1.1 and X1,2, 2 the points X2,1 and X2.2, and finally the points X3,1 and X3,2- The event A consists in all the outcomes in which, among these 2R training points, X1,1 is most similar xtest We then make two key remarks. First, these 2R points are generated by 2R distinct sequences on concepts situation very similar to the simpler data model @SDM (i.e. we first generate 2R sequences of concepts, then from each sequence of concepts we generate a single training point, and finally generate a test point from the first sequence of concepts.) We will make this intuition precise by appealing to the fact that @SDM is the marginal of @DM, and this will allow us to obtain bound for PP A] in term of the permuted moment of K The second remark that menningful is clearly contained in A, and therefore we have
so if we restrict our attention to these 2R points, we are
PDM [Emeninggfa
S [AM
(66)
so an upper bound for PD [A] is also an upper bound for PDM |mmaanigfful:
Let us rename some of the variables. We define d dj...., d2R. and Y1: .......... .2R follow: for 1,...,
d2r-1 = cf and d2r
Y2r-1 = x,,1 and
Y2r = x,,2
for l.....
On the example depicted on Figure that would be:
y1 X1,1: di = Ci,
y2 X1,2 22 c
y3
X2,1 C2
= dp = c2
=== X3,1 d; = C3
Y6 X3,2
dg
dg = C'
In other words, the y, 's are the first two training points of each category and the d, 's are their corresponding sequence of concepts. With these notations it is clear that the training points y, are generated by distinct sequences of concepts, and that the test point eest is generated by the same sequence of concepts than y1. Moreover the event A can now be conveniently written as
A = {w E 0pm:
K .y)) > K kxtm,yy)) for all 2 < r 2R).
Let h 2 - R be the indicator function defined by
{ 0
K (xest .y) > K (x(ex,xx) for all S r S 2R
h(y V2R, x less)
otherwise
We now recall the splitting w = (Wa, wy) described in 58 59 and note that Wa can be written as
Wa = (pp di,..., d2n yı,.. Y2n test
Since h only depends on the variables involved in was and since, according Lemma Ean (DM(Way wa) @SDM (wa), we obtain
PDM[A|= Σ Σ h(y .... y2n, x ))) eDM (way wb)
We WaER, ws E.E
Σ hyy......
V2n. X2n. lest) (WDM)
we En
PSDMIWa E E K (xxemt .y)) > K (uml,,,)) for all 2 - $ 2R
H2R-1(K2)
X
XEX
where we have used Theorem in order to get the last inequality (with the understanding that I 2R.) Combining the above bound with (66) concludes the proof.
24

---

Published as a conference paper at ICLR 2023
We now estimate the probability of the event Buck.
1
Lemma 11. FDM [ S πt
Proof. For 1 S S R. we define the events
{ w SDM max 25a5n
B.
N
K(xta test
xr,s)
max 25 Tapl
K(x lest
ISPSR p'
Note that the events B, involve only the training points with an index 2 2: these are the familiar training points, On the example depicted on Figure 4 these are the training points generated by C1 C2 and C3. Let us pursue with this example. The event B1 consists in all the outcomes in which one of the points generated by C₁ is more similar to x than any of the points generated by C2 and C3- The event B2 consists in all the outcomes in which one of the points generated by C2 is more similar to xiest than any of the points generated by C1 and C3- And finally the event B3 consists in all the outcomes in which one of the points generated by C3 more similar to x than any of the points generated by and C2. Importantly, the test point xlest is generated by the unfamiliar sequence of concepts cj, and this sequence of concept is unrelated the sequence C1y C2 and C3- So one would expect that, from simple symmetry, that
PDM[B]] [i] PDM [B2] (DMM(BB)
(67)
We will prove (67) rigorously, for general R. using Lemma 9 from the previous subsection. But before to do so, let us show that (67) implies the desired upperbound on the probability of E First, note that Ejuck B1 and therefore
FDM S [1).
(68)
Then, note that B1, B2 and By are mutually disjoints, and therefore, continuing with the same example,
PDM B1] + DM [2]] + DM [B] = PDM BB U B2 U Bs] S
which, combined with 67 and (68) gives PDM [Euck] S 1/3 as desired.
We now provide formal proof of (67p. As in the proof of the previous lemma, it is convenient to rename some of the variables. Let denote by fam, the variable that consists in the familiar training points from category r: fam, = (Xr:2 , Xe.n E R
With this notation we have fam,, = X4,+11 We now recall the splitting w = (wes wa) described in 61 62)
and note that we be written
We (pp: fam,
fam x x
(69)
Using Lemma we have
R
eDM Nox(lWesa) wa) = a 1
II
(70)
Wa Eaa
r=1
R
a
II
1 (f(am (()mm..))(((mmm)))) 2)= (tt...)....amm.................. -1)
(71)
r=l R
a II hlyp, fam,)
(72)
where a is the constant appearing in front of the product in Lemma 9 an h & X - {0, 1) the indicator function implicitly defined equality - With the slight abuse of notation of viewing fam, as a set instead of a tuple, let us rewrite the event B,
B, =
N
WE E Ωpm: :
max K x) > max K k(xlou xx) XEfam,
XEfam,
1S'S #T
25

---

Published as a conference paper at ICLR 2023
We also define the corresponding indicator function
if max ((x*s, ,x) > xefam,
K K(x tost ;))
max xefam,
g famm, fam,, x x(ma)
otherwise
We now compute (Bi) (the formula for the other PDM (Br) are obtained in similar manner.) Recall from (69) that the variables involved fam, only appear in we- Therefore
PDM [Bi]
Σ
Σ
II ofam fam,, x(o1)) A==2
@DM( Wa)
(73)
waEDa
R
Σ
II g(fam) fam,, x 2==
Σ waEla
LDM (we; wa)
(74)
Elt
R II (fam], fam,, x rest)
= a Σ
II
h(pp, fam.))
(75)
W.ER
where we have used
72 to obtain the last equality. Let us now compare PDM and PDM (DM
Letting Z nz
and recalling that we (pp: famı
fama x²")), we obtain:
R
PDM B1}
Σ
Σ
Σ
Σ
II IStER r#1
g (fam, fam,, x
II
Mo fam)))
Φ fam
fam & x
R
PDM [By]
Σ FE fam fam
Σ
Σ
Σ
II SSER r2
(famm, fam,, xlstt
II
h(o fam())
x
From the above it is clear that PD FDM (as can be seen by exchanging the name of the variables fam; and fam2). Similar reasoning shows that the events B, are all equiprobable, which concludes the proof.
Combining Lemma 10 and together with the fact that Ex = Ecoreet U E concludes the proof of 63 Inequality (63) implies inequality (26). which itself is equivalent to inequality (14)
C UPPER BOUND FOR THE PERMUTED MOMENT OF K"
This section is devoted to the proof of inequality 15 venience.
which we state below as a theorem for con-
Theorem 5. For all 0 S seS L, have the upper bound
Σ H((K)) < (1- -
Σ f(k)
+ 1+1
max f(K)
(76)
X
KESt
XEX
KES,
The rather intricate formula for the function and g can be found in the main body of the paper, but we will recall them as we go through the proof.
We also recall that the optimal kernel is given by the formula:
Hp & p(xx) v(ve) for all 8 L}
K (x,
(77)
sI.
The key insight to derive the upper bound 76)) is to note that each pair of sentences (x,y) induces a graph on the vocabulary {1, 2..., ). and that the quantity
Hp + (((2)) (pve)) for all < T.)
26

---

Published as a conference paper at ICLR 2023
Table 2: First five rows of the Strirling triangle for the Stirling numbers {x)
k
2
3
4
2
1
3
3
1
7
6
1
5
15
25
10
can be interpreted as the number of equipartitions of the vocabulary that do not sever any of the edges of the graph. This graph-cut interpretation of the optimal kernel presented in detail in Subsection C.T In Subsection C.2 we derive formula for K* which is
tractable than 77 To do this we partition X' x X' into subsets on which K" is constant, then provide formula for the value of K" each of these subsets (c.f. Lemma T6p. With this formula at hand, then appeal Lemma to derive a first bound for the permuted moment of K (c.f. Lemma 17). This first bound is not fully explicit because involves the size of the subsets
which K* is constant. In section C.3 appeal to Cayley's formula, classical result from graph theory, to estimate the size of these subsets (c.f. Lemma 18) and therefore conclude the proof of Theorem 5
We now introduce the combinatorial notations that will be used in this section, and we recall a few basics combinatorial facts. We denote by N {0, 1,2....) the nonnegative integers. We use the standard notations
(x) k:
n!! = k!(nn - k:)!
n!
and
11 1o2.
km
ky 1k2 kin
for the binomial and multinomial coefficients, with the understanding that o! We recall that multinomial coefficients can be interpreted as the number of ways of placing distinet objects into m distinct bins, with the constraint that jj objects must go in the first bin, k2 objects must go second bin, and so forth.
The Stirling numbers of the second kind { are close relatives of the binomial coefficients. [e] stands for the number of ways to partition a set of n objects into l nonempty subsets. To give
simple example, {1) 7 because there are 7 ways to partition the set (1,2,3,4) into two non- empty subsets, namely:
[1) U 3,4) (1,3,4 (1,,44 (1,233.
(3,4), (2,4), (3.4).
Stirling numbers are easily computed via the following variant of Pascal's recurrence formula
for 2
n
for 2 S k: S n-
The above formula easily derived from the definition of the Stirling numbers as providing the number of ways to partition set of n objects into & nonempty subsets (see for example chapter 6 of ?). shows the first few Stirling numbers.
We recall that undirected graph is an ordered pair G = (V, F),, where V/ is the vertex set and
E C ffe, 2'} v E V and + u²}
is the edge set. Edges are unordered pairs of distinct vertices (so loops are not allowed.) A tree is connected graph with no cycles. A states that there are n- ways to put edges on n labeled vertices in order to make a tree. We formally state this classical result below:
n vertices has exactly n I edges. Cayley's formula
Lemma 12 (Cayley's formula). There are n-2 trees on labeled vertices.
A lternatively, Stirling numbers be defined through the formula [*] 1 Σt E- (... i)"
27

---

Published as a conference paper at ICLR 2023
C.1 GRAPH-CUR FORMULATION OF THE OPTIMAL KERNEL
In this section we consider undirected graphs on the vertex set
R. :
Since the data space X' consists of sentences of length L, graphs that have at most L edges will be of partieular importance. We therefore define:
{All graphs V that have most L edges).
In other words, 6 consists in all the graphs (V, whose edge F. has cardinality less equal to Since these graphs all have the same vertex set, we will often identify them with their edge set. We now introduce a mapping between pairs of sentences containing L words, and graphs containing at most L edges.
Definition 2. The function ; x X + B is defined by
((x,y) = U (.r.80)).
(78)
ISESL zefVe
The right hand side of (78) set of most L edges. Since graphs in are identified with their edge set, indeed define a mapping from X' x X' to 6. Let us give a few examples illustrating how words and sentences length 6.
the map Ç works. Suppose we have vocabulary nhe
Consider the pair of sentences (x, E X' x X' where
2.
2,
8,
5,
9,
(79)
=
2,
5,
8,
2,
2,
Then y( is the set of edges
<(x,y)= (2,5), (9,2), {7,1} }
which indeed define a graph on V. Note that position / = 2 and l = of (x, y) 'code' for the same edge 5), position 5 codes for the edge (9, 2}, and position 6 codes for the edge {7, 1}. On the other hand, position and do not code for any edge: indeed, since x1 = y1 and T3 y3. these two positions do not contribute any edges to the edge set defined by (78). We will say that positions and 3 are silent. We make this terminology formal the definition below:
Definition 3. Let (x,y) X X. xt Yt for some 1 < S L, we say that position of the pair (x, y) is silent. If 24. + yr for some 1 < f < L. we say that position of the pair (x,y) codes for the edge J.).
Note that if (x, y) has some silent positions, if multiple positions codes for the same edge, then the graph Ç(x, y) will have strictly less than L edges. On the other hand, if none of these take place, then {(x, y) will have exactly I edges. For example the pair of sentences
x
1, 2,
5.
6.
(80)
y
3,
4,
6,
7,
does not have silent positions, and all positions code for different edges. The corresponding graph
<(x. y) = (1,2). {1,3), {1,4), (5.6), {6, 7), {7.1) }
has the maximal possible number of edges, namely 7. = 6 edges. From the above discussion, it is clear that any graph with L or less edges can he expressed as y(x,)) for some pair of sentences (x, A' x X. Therefore Ç X' x d' -> 6 is surjective. On the other hand, different pair of sentences can be mapped to the same graph. Therefore is not injective. We now introduce the following function.
Definition (Number of cut-free equipartitions of graph). The function I - N is defined by:
I(g) Ky + ((v) sp(v') ) for all edge {v, v'} of the graph 9)
(81)
28

---

Published as a conference paper at ICLR 2023
(a) Cut-free
(b) Not cut-free
Figure 5: Two equipartitions of the same graph (each subsets of the equipartitions contain 7 vertices). The equipartition on the left is cut-free (no edges are severed). The equipartition on the right is not cut-free (4 edges are severed). The optimal kernel K k*(x, y) can interpreted as the number of distinct cut-free equipartitions of the graph y(x,y) (modulo some scaling factor.)
Recall that + is the set of maps of : -> (1...., ne) that satisfy (c)] & for all S c S nee- Given graph G, the quantity I(g) can therefore be interpreted as the number of ways to partition the vertices into n. labelled subsets of equal size so that no edges are severed (i.e. two connected vertices must be in the same subset.) In other words, I(G) is the number of "cut-free" equipartition of the graph G. see Figure for an illustration. Note that the graph G is connected, then I(g) since any equipartition of the graph will severe some edges. On the other hand, if the graph G has no edges, then I(g) = [ since there are no edges to be cut (and therefore any equipartition is acceptable.)
The optimal kernel K** can be expressed as a composition of the function Ç and I. Indeed:
k* = [
Hipe E t (p(x)) = (pve) for all 1 < s <>
(82)
K :: x(() plv') for all {u, y(x,)) }
(83)
I(C(x,y))
(84)
where we have simply used that y(x,y) = Uisper 313} to go from (82) to (83). We will zイ
refer 184 as the graph-cut formulation of the optimal kernel.
We have discussed earlier that the function Ç X' x X' + 6 is surjective but not injective. We conclude this subsection with a lemma that provides an exact count of how many distinct (x.y) are mapped by Ç to a same graph g.
Lemma 13. Suppose G E G has m edges. Then
k-) H((x,)) E x 9] m!
Σ
1.
C m
2
n
Proof. Fix once and for all graph G (V,E) E) with edge set E {el,..., )m) where m S L.
Given 0 < a < L, define the set
O₂ = (x. E X x X' ((x,y)= G and y) has exactly a non-silent positions}.
We start by noting that the set On is empty for all m positions a pair (x,y) y) must be coding for edges (i.e., must be non-silent) in order to have ((x, G. We therefore have the following partition:
indeed, since & has edges, least
Ü O. O.
and O~ =0 if a
m
To conclude the proof, we need to show that
10 = (2) {a m
m!
2a ny
L-a
for m S a S L.
(85)
29

---

Published as a conference paper at ICLR 2023
Consider the following process generate ordered pair yx. that belong to Oa: start by deciding which positions of (x.y) are going to be silent, and which positions are going to code for which edge of the graph G. This is equivalent to choosing map p {l....,LI L} + (cI,.... Cm s}
where (1, (1.....,,, I.} denotes the I. positions, e1,..., 6m denote the m edges of the graph g, and is the silent symbol. Choosing a map P correspond to assigning "rrol" to each position: p(() 6
means that position e is given the role to code for edge E,, and p(t) = means that position is given the role of being silent. The map P must satisfy:
(s) = - a and (e)) for S S m
(86)
because L - a position must be silent and each edge must be represented by at least one position. .m::8] 8) that satisfies (86) is equal to
The number of maps p: {I,..., L} - {ei...., Cmm
(1-aa
1
a
L-a
m!
m
Indeed, we need choose the T. a positions that will be mapped to the silent symbol s: there (Laa) ways of accomplishing this. We then partition the remaining positions into m non-empty subsets: there are {m] ways of accomplishing this. We finally map each of these non-empty subset different edge: there are m!! ways of accomplishing this.
We have shown that there are (+) {m mm ways to assign roles to the positions. Let say that position l is assigned the role of coding for edge {v, v'). Then we have two choices to generate entries Zz and ye: either Zt = and Y/+ = =', or 2g u and yı = e. Since a positions are coding for edges, this lead to the factor 2 in equation (85). Finally, if the position E is silent, then we have now choices to generate entries Iy and y/ (because we need to choose u V such that ze = Y/e = v) hence the factor n appearing in (85).
C.2 LEVEL SETS OF THE OPTIMAL KERNEL
We recall that a connected component (or simply a component) of graph a connected subgraph that is not part of any larger connected subgraph. Since graphs in & have most L edges, their components contain at most L + vertices. This comes from the fact that the largest component that can be made with L edges contains I. vertices. It is therefore natural, given vector = [k1,...,kL+t) E NL+1, to define
6₂ = (g E G G has exactly kn components of size 1, exactly hy components of size 2, exactly kL-1 components of size L + 1 (87)
where the size of a component refers to the number of vertices it contains. We recall that N = (0, .... therefore some of the entries of the vector k can be equal to zero. Note that components of size 1 are simply isolated vertices. The following lemma identify which k E N4+11 lead to non- empty 6k.
Lemma 14. The set Gk not empty if and only if satisfies
L+1 Σ
L+1
ih;
and
Σ i - (i-1 S T.
(88)
d=1
Proof. Suppose 6k is not empty. Then there exists graph @ that has exactly components of size i, for 1 < < L + 1. A component of size i contains i vertices (by definition) and at least i 1 edges (otherwise would not be connected.) Since G 6 must have nu vertices and at most I. edges. Therefore (88) must hold.
Suppose that E N satisfies (88). Then we can easily construct graph 9 on that has a number of edges less or equal to I., and that has exactly k; components of size i, for 1 < i < L++1 To do this
we first partition the vertices into subsets so that there are k; subsets of size i, for 1 < < L 1. We then put 1 edges each subset of size so that they form connected components. The resulting
graph has h; components of size i, for 1 < <
L 1, and ELtl (i 1) 1)k; edges.
30

---

Published as a conference paper at ICLR 2023
The previous lemma allows to partition & into non-empty subsets follow:
- UUS Ok
8k + for all k E S;
and
8k n 8K 00
(89)
KES
where S
k KENNII
Σ
tk nw
and
(i-
(90)
Recall that I(G) count the number of equipartitions that do not severe edges of G. The next lemma shows that two graphs that belongs to the same subset 6k have the same number of cut-free equipar- titions, and it provides formula for this number in term of the index k of the subset.
Lemma 15. Suppose k E S and define the set of admissible assignment matrices
{A { Ak == A A
Σ
Re
Ais
k for all and
Σ
L+1
iAi = for all }
(91)
j=1
Then for all Bk. we have that
(I(A
ki A A
I(G) = Σ II
(92)
AEAx i=1
Let us remark that, since 0! = 1, the multinomial coefficient equal when k; is equal
2am appearing in 92 is
Poof of Lemma
15
Let k S and fix once and for all graph G e Gk. Define the set
V {p E =p() = <(e') for all edge {v, v/} of the graph g}
so that ((g) component to the same concept (otherwise some edges of G would be severed.) So a map E y can be viewed as assigning connected components to concepts. Given a matrix E N(L+1)xne we define the set:
Note that map oo that belongs to must map all vertices that are in a connected
A = {pp E V P assigns Ay components of size to concept j, for all 1 i L+1 and S S nct.
We then note that the set A is empty unless the matrix A satisfies:
A₁1 A,2 + A1,3 ... + Ain, k for all 1 s +iSL+1
Ai + 2A2, + 3.3.jj +... (I. 1)A+115 8c for all S nc-
The first constraint states that the total number of connected components of size i is equal k; (because G E (k)) The second constraint states that concept must receive total of s, vertices (because & E Q.) The matrices that satisfy these two constraints constitute the set As defined in We therefore have the following partition of the set V::
91
V
U
A
A Aif Ak
B if
AEλx
To conclude the proof, we need to show that
L+1
|
II i=1
k
for all E Ak-
(93)
ALL, A Ain.)
To see this, consider the k; components of size The number of ways assign them to the ne concepts so that concept j receives Ai of them is equal to the multinomial coefficient (A Aidd Repeating this reasonning for the components of each size gives 93
by
now leverage the previous lemma to obtain a formula for K*. For E we define
(G
31

---

Published as a conference paper at ICLR 2023
Since Ç: A' X - B is surjective, partition 88 of & induces the following partition of X 2:
X' x X
U
Sk
Uk 00 Of
and
if k'.
(94)
keS
Using the graph-cut formulation of the optimal kernel together with Lemma 15
we therefore have
L+1
Ki
K (x)
I(C(x,)))
Σ1 AEAx
II
for all (x.y) 4k-
A12,
As..
(95)
The above formula is key to our analysis. We restate it in the lemma below, but in slightly different format that will better suit the rest the analysis. Let f: S + R be the function defined by
f(k)
m (so!)"
EI
E
II
L+1
ki (ALI,
(96)
naw
Aim
AEAx 2=1
We then have:
Lemma 16 (Level set decomposition of K*), The kernel K is constant each subsets 94 of the
partition (4). Moreover we have
K (*(x,y)= f(k))) f(k)/ for all (x, She for all k E S.
Proof. The quantity / appearing (95) can be interpreted as the number of ways to assign the nw words to the n. concepts so that each concept receives sc words. Therefore
Pew
8cr 801
Sc
(so!)
Combined with the fact that |X|
n this leads the desired formula for K*
The above lemma provides us with the level sets of the optimal kernel. Together with Lemma this allows us derive the following upper bound for the permuted moment of K*
Lemma 17. Let = X x X. The inequality
H((K)) <
Σ KES'
14 S2
f(k)
+
1
max f(k) KES'
X XEX
t+1
holds for all S' C.
Proof. Let S' S and define:
1
max max K* K*(x,y) KES' (x.))
max f(k)
[X|
kes'
where we have used the fact that K* is equal to f(k)/|X) Su. We then appeal to Lemma to obtain:
X|X
Σ H4
HK*
+1
Σ yex
min min K (x),)),
(97)
X
X
t
A/
+1
Σ
minfK (x,
(98)
t+1
X
XEX
X|XXI
+1
Σ
min K m (x, y)
(99)
E+1
X
KES (x,))Ef
X
Σ
Σ
(100)
[+1
X
KES'
(x.y)EL+
X
+1
Σ
K*
(101)
t+1
X
KES!
(x.
X|X
f(k)
+1
14
(102)
1+1
X
|
KES'
32

---

Published as a conference paper at ICLR 2023
where have use the fact that X' x X' Ukes 94 to go from 98 to 99 and the fact that
K K'(x,,7 S À on Ukes Ok to go from (100 to 1OT). To conclude the proot, we simply note that \|xk = maxkes f(k) according to our definition of A.
The bound provided by the above lemma not fully explicit because it involves the size of level sets Okk In the next section, we appeal to Cayley's formula to obtain lower bound for [Sx]-
C.3 FOREST LOWER BOUND FOR THE SIZE OF THE LEVEL SETS
We recall that a forest is a graph whose connected components are trees (equivalently, a forest is graph with cycles.) Let define:
= (9 6: is a forest).
In other words, & is the set of forests on V [1. 2, ... ..w that have at most L edges. We obviously have the following lower bound on the size of the level sets:
s2 ((xx) 2 | (5k n
(103)
In this subsection, we use Cayley's 's formula to derive an explicit formula for |s- (0x n 8)| We start with the following lemma:
Lemma 18. Let k E S, then
L+1
/--2
6k n 3/
New
II 1=
(104)
ky
KL+1!
i!
Proof. First we note that (104) can be written as
L+1
shili-2)
ihs (i,,...,;)
16 n 3l
II
k1, 2k2, ..... (L 1)KL+1
1=2
We now explain the above formula. The set 6k consists in all the forests that have exactly k trees of size 1, ky trees of size ..... kL+1 trees of size L + 1. In order to construct forest with this specific structure, we start by assigning the new vertices to 1 bins, with bin receiving k vertices, bin 2 receiving 2k2 vertices, bin I.+1 receiving (T 1)kr+1 vertices. The number of ways of accomplishing this
Thw
k1 2k......
[L + 1)
Let us now consider the vertices in bin for some 2 2. We claim that there are
ik;
(4:(6-2)
ways of putting edges on these ik; vertices in order to make k; trees of size i. Indeed, there are I ik; F.T (........) ways of partitioning the vertices into k; disjoint subsets of size i, and then, according to Cayley's formula, there are zi-2 ways of putting edges on each of these subsets so that they form tree. To conclude, remark that there is obviously only one way to to make kj trees of size out of the j vertices the first bin.
Recall that
vertices always has edges. So graph that belongs to 6₁ O S has
L+1
m Σ (1 1)k:
edges since it is made of k; trees of size 1, k2 trees of size 2, ... kL+1 trees of size (L+1). The fact that all graphs in 6k 3 have the same number of edges allows us to to obtain an explicit formula for 15- (G O 33) by combining combine Lemma 13 and 18 namely
L+1
f.
To (B n = ki ... KLT1!
m!
Σ a=m
2 n
L-a
i!
m
i=2
33

---

Published as a conference paper at ICLR 2023
This lead to define the function g 8 - by
g(k)
1
L+1
8-2)
7(k)
Σ
30 L-a
2
(x(k) ((ck)))2n)
] 20
kn !/22
... KL+11
i!
a=)
1-1
where 7(k)
Σ
(i - 1)
1=1
Recalling (103) therefore have that
[2
2 o(k)
for all E S.
[S]
Combining the above inequality with Lemma 17
obtain:
Theorem 6. The inequality
1
1-
Σ Hi(K)) S X
a(k) f(k)
max f(k) KES"
1+1
kES
holds for all S' C.
The above theorem is more general than Theorem subset S' is restricted the L + candidates:
5
indeed, in Theorem 5 the choice of the
L+1
L+1
S = k 1
Σ 1=1
ik. = fw
and Σ 2=1
<
i
1)k- <
where & 1, L.
When = 9, nww 150, n. 5 and 1999 (these the parameters used in Theorem T choosing S = Sy leads to relatively tight upper bound. When L = 15, Twe = 30, ne = 5 and t 5999 (these are the parameters corresponding the the second experiment of the experimental section), choosing S = S11 gives good upper bound.
D MULTIPLE UNFAMILIAR SENTENCES PER CATEGORY
In the data model depicted in Figure D each unfamiliar sequence of concept has a single represen- tative in the training set. In this section consider the more general case which each unfamiliar sequence of concepts has n² representatives in the training set, where
n
Napl-
An example with n 2 is depicted Figure 6 The variables L,, Dar, The, R, Degt and n² parametrize instances of this more general data model, and the associated sampling process is:
Sampling Process DM2:
Sample T = (ip: CI...., CR ci..... CR uniformly at random in I + Z2R
(ii) For r = I,..., R:
Sample (Xr,,,..., X uniformly at random in (3-((c)) x... x (c)) Sample (x x. uniformly at random in & (c,) ... x 3 ( (c+).
(iii) Sample lest uniformly at random in (c().
Our analysis easily adapts to this more general case and gives:
Theorem 7. Ler I + Z Then
[1-> Σ f(k))(())
1 1- n²
max
f(k) +
(105)
KES,
KES,
for all feature space F, all feature map 1p X F. and all 0 < E T.
34

---

Published as a conference paper at ICLR 2023
prigert
T
Vogges
Taads
Tacc
Clewn
Loak
yeegan,
6
dain
dais
High
Vagae 2ant dan, 2A00 dasy
Baads
daans pack
roguat
diilbra
regort
dibie
lands
stase
Figure 6: Data Model with n²" = 2 unfamiliar sentences per category. The other parameters in this example are set L Tww 12, ne R and Napl 6. The points highlighted yellow are the ones involved the definition of the event A (1), see equation 109
Theorem in the main body of the paper be viewed as special case of the above theorem indeed, setting n² = in inequality (105) we exactly recover
In order to prove Theorem 7 simply need to revisit subsection B.3 We denote by ΩDM2 and PDM2 the sample space and probability measure associated with the sampling process DM2, As in subsection B.3 given kernel K E K., define the event
Eg
w E ΩDM2: There exists S 8" < Nsppl such that
K (x x1,5-) > K (xtst .x,,) for all 2 Sr R and all S S nappl
Such event describes all outcomes corresponding to successful classification the test point x tost For simplicity let assume that n" 2 (therefore matching the scenario depicted in Figure 6 We further partition the event Ex according to which training point from the first category is most similar the test point:
EK E
U Eruck
(106)
meaningful
meaningful
The event [11) meaningful consists in all the outcomes where, among the points from first category, X1,1 is the most similar test (2()) menningtul consists in all the outcomes where, among the points from first category, X1,2 is the most similar to test and Ejuck consists in all the remaining cases. Formally we have:
E meaningtul
EK n w E PDMP: K (xeea x1,1) > K (x!est x1.2)
n w E Apma: K (x!et x1,1) > K (xt x1,,) for all 3 napl
E 2
Ex n
w Ωome: K (xt x1,2) 2 K fest x1,1)
n w E PDMz: K (x x1,2) > K (ess x1,)) for all 3 napl
Ernc Ex n {we IDMZ: there exists 3 < 8" S Napl such that
K (x1st xx,,,) 2 K (x x1,0)) for all 1 5 S nlpl
35

---

Published as a conference paper at ICLR 2023
Exactly in subsection B.3
then prove that
( PDM2 masaingtul
-
(2R-1(K²)) for = 1,2 xEx
Σ
(107)
1
PDM2 Fruck S
(108)
R
The proof of inequality (107) is essentially identical the proof of Lemma 10
We define the event
A = [w E PDMM:
K (x!"a, x1.1) > K (xe x,,1) for all 2 2 R}
n nfw E spmz: K (xlest, x1.1) > K (xtee x,,3) for all s R] (109)
and the event
(2) = {w E PDM2:
K
> K (xtex xx,2) for all S r R
n {ws PDM2: K (xteat x1,2) > K (x xx,3) for all Sr R
The x's involved in the definition of the event A are highlighted in yellow in Figure Crucially they are all generated by different sequences of concepts, except for X1,1 and seest, We can therefore appeal to Theorem to obtain
DM2 |DM2|A S
Σ H2R-1(K²)
X
XEX
since there is total of t = 2R - 'distractors' (the 'distractors' in Figure 6 are x1,3+ X2,1, X2,3 menningful
X3,1 and X3.3). We then use the fact (2) exactly similar.
C A() to obtain (177 with i 1. The case i = is
We now prove 108 events
The proof is similar to the proof of Lemma
For 1 <r S R, we define the
B, = n
E ΩDM2: : max
{(xttst Xr..)
max 35 Stipl
K K(x xp)
SSa
IS''RR
pr
By symmetry, these events equiprobable. They also mutually disjoints, and therefore FDM2 [B,] < 1/R. Inequality (108) then comes from the fact that Eluck C B1-
Combining (T06).
(07
108) then gives
2 X
sup PDM2 KeK
EK
S
Σ xEX
HeR-1 (Kt) +
(110)
R
and, going back to the general case where n denotes the number of representatives that each se- quence of unfamiliar concepts has the training set,
n
1
sup PDM2 Kek
<
Han-1 (K*)
(111)
X
R
XEX
which in turn implies 16.. Combining inequalities rem 7
15 and 16) then concludes the proof of Theo-
E DETAILS OF THE EXPERIMENTS
In this section we provide the details of the experiments described in Section as well as additional experiments. Table provides the results of experiments in which the parameters L, Raws Be and R are set to
L 9, The 150, n. R 1000.
36

---

Published as a conference paper at ICLR 2023
Table 3: Accuracy in % on unfamiliar test points (L 9, nww 150, ne 5, R 1000).
n'
n' =2
n²=3
n'=4
n²=5
nsp1 =
Pepl=
nspl =8
7sp1=9
Pspl =
Neural network
99.8 - 0.3
99.9 0.1
99.9 0.1
99.9 1 0.1
100 T 0.1 99.9 0.1
NN on feat, extracted by neural net
99.9 0.1
99.9 1 0.1
99.9 0.1
99.9 + 0.1
NN feat. extracted 1
0.7 = 0.2
1.1
1.5
1.8 0.3
2.2 0.3
on extracted by Mone- hot
= 0.2 1.6
1.1 0.3
1.4 0.2
0.3
2.1 0.3
Upper bound (0.015n" + 1/1000)
3.1
4.6
6.1
7.6
SVM on feat. extracted by 10"
- 0.3
1.4
2.2
3.2
4.2
SVM on feat. extracted by Mone- hot
0.1
1.10011
1.1
2.8
3.8
SVM with Gaussian kernel
0.1
1.100.1
2.0
2.8
3.6
Table 4: Accuracy in % on unfamiliar test points (J. 9, flw = 50, n.
5, R 1000).
n'=1
n² =2
n ===3
n'=4
n =5 Napl 10
nspl= = 6
Napl =
Rap1 =8
Rapl Rsp==9
Neural network
99.9 + 0.1
99.9 + 0.1
99.9 + 0.1
99.9 0.1
100 + 0.1
NN on feat. extracted by neural net
99.9 = 0.1
99.9 + 0.1
99.9 + 0.1
99.9 0.1
99.9 0.1
NN on feat. extracted by 10"
2.4 0.3
4.1 4.1 0.6
5.5 + 0.6
6.9 6.9
8.0 8.0 0.8 6.7
NN on feat, extracted by Voue-hot
2.0
3.4 0.5
4.8 + 0.6
6.7
Upper bound (0.073n" + 1/1000)
7.4
14.7
22.0
29.3
36.6
SVM on feat. extracted by 1/*
2.2
5.2
8.6
11.7
15.1 + 1.2
SVM feat. extracted by Mone-hhtt hot
0.1
3.5
6.2
9.3
13.6 0.4
SVM with Gaussian kernel
2.0 0.1
3.7 6.710.1 0.2
5.4 0.2
8.6 0.3
12.1 0.3
The parameters Napl and n² chosen that the training set contains familiar sentences per category, and between 1 and 5 unfamiliar sentences per category. Table is identical to Table [i] Section 6 with the exception that it contains additional information (i.e. the standard deviations of the obtained accuracies). The abbreviation NN appearing in Table stands for "Nearest Neighbor'.
Table provides the results of additional experiments in which the parameters L, Dww, ne and R are set to
- 9, The 50, The
R 1000.
The parameters Nspp and n² are chosen, in the previous set experiments, that the training set contains 5 familiar sentences per category, and between and unfamiliar sentences per category. The tasks considered in this set of experiments are easier due to the fact that the vocabulary is smaller (nw = 50 instead of no 150).
E NEURAL NETWORK EXPERIMENTS
We consider the neural network in Figure The number of neurons in the input, hidden and output layers of the MLPs constituting the neural network are set to:
MLP 1: dm = 150, dhidden = 500, dout = 10,
MLP 2: d,, 90, dhidden 2000, dout = 1000.
For each of the 10 possible parameter settings in Table 3 and Table do 104 experiments. For each experiment we generate:
A training set containing R Napl sentences.
A containing 10, 000 unfamiliar sentences (10 sentences per category).
We then train the neural network with stochastic gradient descent until the training loss reaches 10 (we use a cross entropy loss). The learning rate is set to 0.01 (constant learning rate), and the batch size to 100. At test time, either use the neural network to classify the test points (first row of the tables) or we use a nearest neighbor classification rule on the top of the features extracted by the neural network (second row of the tables). The mean and standard deviation of the 104 test
37

---

Published as a conference paper at ICLR 2023
accuracies, for each of the 10 settings, and for each of the two evaluation strategies, is reported in the first two rows of Table 3 and Table
E.2 NEAREST-NEIGHBON EXPERIMENTS
In these experiments we use nearest neighbor classification rule on the top of features extracted by 2 (third row of Table 3 and 4 or Wone-bot (fourth row), For each of the 10 possible parameter settings Table and Table we experiments. For each experiment we generate:
A training set containing R napl sentences.
A test set containing 1, 000 unfamiliar sentences (one sentences per category).
In order to perform the nearest neighbor classification rule on the features extracted by th*, one needs to evaluate the kernel K" (x, = (45 (x), 18" (y))) for each pair sentences. Computing K (*(x, requires expensive combinatorial calculation which is the reason why perform fewer experiments and use a smaller test set than in E. In order to break ties, the values of K (*(x,)) y) perturbed according to (3I).
are
With the parameter setting = 9, fw = 50, n. and R = 1000, our theoretical lower bound for the generalization error is
e v. 5)
0.073 n' - -/RR for all and all vs
(112)
which is obtained by choosing & = 6 in inequality (105). This lead to an upper bound of 0.073 n + 1/R R on the success rate. This upper bound evaluated for ranging from to in the fifth row of Table 4
E.3 SVM ON FEATURES EXTRACTED BY Vone-hot AND SVM WITH GAUSSIAN KERNEL.
For each of the 10 possible parameter settings in Table and Table we do 100 experiments. For each experiment generate:
A training set containing R Napl sentences.
A test set containing 10, 000 unfamiliar sentences (10 sentences per category).
We use the feature map Vone-hot (which simply concatenates the one-hot-encodings of the words composing a sentence) extract features from each sentence. These features are further normalized according to the formula
Vone- hot (x) p
where p = 1/nuw
(113)
Vp(1 p)
so that they are centered around 0 and are O11). We then use the SVC function of Scikit-learn Pedregosa et al. (201I), which itself relies the LIBSVM library Chang & Lin (001)). in order to run soft multiclass SVM algorithm on these features. We tried various values for the parameter controlling the & regularization in the Soft-SVM formulation, and found that the algorithm, this task, not sensitive to this choice - so we chose C = The results are reported the seventh row of both tables.
We also tried a soft SVM with Gaussian Kernel
applied on the top of features extracted by voone-hot and normalized according to (113). We use the SVC function of Scikit-learn with & regularization parameter set to C 1. For the experiments in
Table 3 (n = 150), the parameter y involved in the definition of the kernel was set to y = 0.25 50),
when {1, 2} and to 7 0.1 when n² E {3, 4, 5). For the experiments in Table
was set to 7 = 0.75 when n² = 1, to = 0.1 when n²* = 2, and finally to y 0.005 when
n" E [3, 4,
38

---

Published as a conference paper at ICLR 2023
Table 5: Search for the hyperparameter a
Amin Amin(Guru (Gurain)
Amax ( (Gtrain)
Test Accuracy
0.001
-90.9
50, 583.3
6.1 %
0.01
88.55
32, 334.9
6.1 %
0.1
-56.8
15, 15.358.7
6.6%
1.0
-22.9
4, 191.5
7.6%
10
-2.5
673.4
7.2%
15
-0.138
471.7
7.0%
16
0.2
445.5
7.0%
100
4.7
86.9
5.4%
1000
4.983
15.573
5.0%
E.4 SVM ON FEATURES EXTRACTED o
Applying a SVM on the feature extracted by s/ is equivalent to running kernelized SVM with ker- nel K naive implementation of such algorithm leads to very poor results on our data model. For such algorithm to not completely fail, it is important to carefully "rescale" K* so that the eigenvalues of the corresponding Gram matrix are well behaved. Recall that
ne Hp & (p(x)) = (we) for 1 S sses LH
K' (x.
(114)
m
and let & R + R be a strictly increasing function. Since the nearest neighbor classification rule works by comparing the values of K various pairs of points, it is clear that using the kernel K** (**(x,)) y) = E(K* (x,y)) y)) is equivalent to using the kernel (x,,, In particular, choosing {(x)) == log(1 (a)))))) gives the following family of optimal kernels:
(x,(*(x,))
n. a
Ky (x, y) log [1+ (x.)))
(115)
To be clear, all these kernels are exactly equivalent to the the kernel K* when using nearest neigh- bor classification rule, However, they lead to different algorithms when used for kernelized SVM. We have experimented with various choice of the function & and found out that this logarithmic scaling works well for kernelized SVM.
For each of the 10 possible parameter settings in Table 3 and Table we do 10 experiments, For each experiment we generate:
A training set containing R Tapl sentences.
A test containing 1, 000 unfamiliar sentences (one sentences per category).
Let us denote by x!rin, 1 < i < R x Rsp). the data points in one of these training set, and by x!es 1 S i 1000, the data points in the corresponding test set. In order run the kernelized SVM algorithm we need to form the Gram matrices
drain K** (x!
train
and
G
train K (x x
(116)
Constructing each of these Gram matrices takes few days on CPU. We then use the SVC function of Scikit-learn parameter controlling the & and found that the algorithm is not sensitive to this choice - so we chose C The algorithm, the other hand, is quite sensitive the choice of the hyperparamater defining the kernel K** We experimented with various choices of a and found that choosing the smallest a that makes the Gram matrix Gurain positive definite works well (note that the Gram matrix should be positive semidefinite for the kernelized SVM method to make sense). In Table 5 we show an example, on specific pair of train and test se of how the eigenvalues of Grrain and the test accuracy depends on
soft multiclass kernelized-SVe algorithm. We tried various values for the
'the training set and test set used in this experiment were generated by data model with parameters nu. 50, n. R 1000, Nep! 8, and n"
39


Reviews:
[{"review_id": "uxIbjZyXbN", "reviewer": "Reviewer_gVke", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a simple data model of a classification task (a model that generates a training and testing set), and use it to demonstrate the theoretical importance of learning task-specific features (transformation of input features) to achieve good generalization performance on a specific task. The model relates to the commonly encountered long-tail distribution of data, by assuming a low number of examples in the train set for each category/class and test set containing unobserved before examples (not present in train set), what is common for a long-tail (the unbalanced that is also a characteristic for long-trail distributions is not touched here). In such a setting, intuitively learning features is required to achieve a good result. First, the authors use their model to confirm that by showing that on a given task, the nearest neighbor classifier achieves a perfect score when given optimal features representation results using experimental comparison. Later the authors show that it's not possible to find feature representation that will generalize well for all tasks from a set of all possible (with the assumed data model with the same parameters) when using the nearest neighbor classification. The authors derive the bond on the expected error on a task from a set of all possible ones. Finally, these findings are confirmed by empirical experiments, where the authors compare the performance of two settings. In the first, a neural network was used to learn features for a specific task, and mean performance on these tasks is reported, as expected, this gives low mean error. In the second setting, one general feature map is used for all tasks, as expected, resulting in a very high mean error.", "summary_of_the_review": "I find this paper very difficult to rate, I think it is interesting, from the point of view of the technique and the proof, maybe because I'm not very familiar with similar works. On the other hand, I'm not sure how this work may impact further research. Convinced by the high quality of the writing, at the moment, I'm leaning toward accepting this paper.", "strength_and_weaknesses": "Strengths:\n+ The paper is well-written, mostly easy to understand, and technically sound.\n+ The theoretical findings are nicely confirmed by empirical experiments.\n+ The very comprehensive appendix nicely explains the proofs and some other details (unfortunately, I haven't yet had time to go through everything).\n+ The paper matches the main themes of the conference very well.\n\nWeaknesses:\n- The main conclusions of the work are not surprising, I believe this is the well-known fact that tail-distributions require better feature learning and was kind of confirmed empirically in many domains. While I find this as a nice theoretical confirmation, at the moment, I don't see any other application/implications of this work. The derived error bound is just for the proposed model, which is too simple to be used as a model for any real dataset.\n- Based on the abstract I was hoping that the authors will use the model to try to answer some more interesting questions like: what error can we expect if we will use the same feature for a set of similar tasks?\n- Among all the nice proofs and details in the appendix, I lack the proof for Theorem 2.\n- Some important details are in the appendix. e.g., the experimental section is much clearer after reading the corresponding appendix section. I would suggest moving the description of parameters to the appendix and describing the better experimental protocol in the main paper.\n\nNITs:\n- In section 2, the example with 3 concepts could use different colors to mark words from the same concept, I believe this would make it even easier to read/understand quickly.\n- Some small language mistakes I noticed:\n  - from a different point view -> from a different point of view\n  - intances -> instances\n  - The former represent/the latter represent -> represents?\n  - data generative process itself more coherent -> data generative process itself is more coherent \n  - We would like to emphasis one more time -> We would like to emphasize one more time\n  - one just need -> one just needs\n  - Our experiments shows -> Our experiments show\n  - There are missing comas in phrases like \"In ...,\" in some places.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "qzgB3PwO20", "reviewer": "Reviewer_3imt", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a novel model of data, and shows that under the proposed model, a model can only succeed if it performs feature learning. Specifically, the primary data model proposed in the paper involves a set of concepts, each with an equal number of vocabularies. There is an $R$ number of categories (or classes). Each category contains two sequences of concepts. The first concept sequence, $c_r'$, is “unfamiliar” which accounts for a small portion of the generated data (i.e., long tail of the distribution) and the second concept sequence, $c_r$, is “familiar” which accounts for the majority of generated data (i.e., the head of the distribution). At training time, for each sample, the model first samples a concept sequence, and then generates a sequence of vocabularies corresponding to the concept sequence uniformly. At test time, the model only samples from the tail of the distribution. The paper then proceeds to show that on this data model, generalization error on the test distribution be lower bounded by a combinatorial quantity and using this lower bound, the paper shows in certain configurations of the data distribution, the test error can be arbitrarily high. Finally, the paper demonstrates, through simple experiments on an instantiation of the proposed data model, that the test error of models which do not learn features is much higher than neural networks which learn features.", "summary_of_the_review": "The paper proposes a very interesting data model that advocates for the importance of learning features and shows models that do not learn features cannot do well on the tail of the distribution. However, currently, there seems to be a gap between the theoretical results and empirical results which I could not resolve after reading the paper multiple times. As such, my current assessment of the paper is slightly below the threshold and look forward to hearing the authors’ response.\n\n\n## Update\nThe paper is much clearer after the revision and I think the paper is definitely interesting enough for the theoretical community. I decide to increased my score to 8.\n\n", "strength_and_weaknesses": "### Strength\n1. The paper proposes a fairly novel model for deep learning in certain long-tailed distributions that argues for the importance of feature learning\n2. The theoretical result is sound as far as I can tell and the proof techniques are novel for this area (although I did not have the time to go through all the details of the appendix given the short period of review).\n3. The story is convincing, and I can tell that the authors have taken great care to make the paper as clear as possible in spite of its highly complicated nature and novelty (although there are still parts of the paper that are unclear)\n\n### Weakness\n1. It is unclear how well the proposed model reflects real world problems. Some empirical evidence would strengthen the paper.\n2. There seems to be a disconnect between the theoretical part and empirical verification (please correct me if I am wrong).\n     - Based on my understanding, the theoretical result precludes **any** feature map $\\psi$ that maps the sentence to features, which presumably includes those learned by neural networks so it is weird that the experiments suggest something otherwise. In a similar vein, I find the claim to be too strong to be useful. \n    - I spent a lot of time trying to understand the previous point and I came to the conclusion that (I believe) the tasks used in the experiments only have a single $\\varphi$. Is this correct? If that is the case, how does the experimental section fits into the theoretical framework which uses $\\Phi$ that include **all** partition functions.\n    - How does the theory change if I have only **one** partition function $\\varphi$?\n    - I am concerned that this disconnect makes the theoretical results less useful than it appears to be.\n3. The test error is not iid but in practice the model would presumably still get most of the data correct if the test distribution is the same as training distribution.\n4. The paper doesn’t have a conclusion.\n\n### Questions\n1. Can you provide more explanation on how one should interpret the optimal feature map $\\psi^\\star$?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EDp3hPwMwtG", "reviewer": "Reviewer_VYVD", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies machine learning in settings where where classes have rare subcategories (potentially as small as one example in the training set).\n\nThe paper creates a data model, and shows that while a model that properly learns features can achieve very high performance, models that do not learn these features have very low accuracy. Error bounds are derived for this data model, and experiments showing similar behavior with other models are performed.", "summary_of_the_review": "The paper introduces a data model where the performance of machine learning heavily depends on learning the categories of each word. While the results do highlight the importance of feature learning in this data model, my impression is that the data model is still relatively far from real problems.", "strength_and_weaknesses": "Strengths\n\n - The model is relatively straightforward to understand, and it is relatively intuitive to understand why it is critical to learn the features.\n - The performance differences between learning and not learning the features are  very dramatic.\n\nWeaknesses\n\n - The theoretical section of the paper is somewhat difficult to follow. There are many variables that I had to look back to recall, and the derivations sometimes lack descriptive text around it to help guide the reader.\n - The model is somewhat synthetic. While it does highlight the importance of learning categories in this particular data model, it is relatively unclear to me how directly this generalizes to other NLP problems and image problems.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "E9b6O-OO43h", "reviewer": "Reviewer_LVLa", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper derives generalization error bounds that are non-asymptotic and relatively tight against long-tailed problems, within the context of our data model, through mathematical analysis and partial empirical evidence.", "summary_of_the_review": "Being a novel research in the field of CV and NLP, especially some parts do not have strict mathematical analysis, but rely on experience, and more experimental results should be provided to support the conclusion. In addition, the legends in the article are not rich, which is not conducive to reading and understanding. More graphical explanations should be added appropriately. Finally, as a very mathematical article, important reasoning procedures should be included in the main text rather than all listed in the appendix.", "strength_and_weaknesses": "Strength: \n1. The effectiveness of the method has been proved by mathematical analysis and empirical experience.\n2. The method can be used for long-tailed problems in the field of both CV and NLP.\n3. The paper puts novel theoretical results that can inspire future theoretical research on long-tail problems.\n\nWeaknesses:\n1. The experimental results are too few to illustrate the effectiveness of the method.\n2. Although the detailed proof process is given in the appendix, the idea of the text is a bit jumpy.\n3. The method in this paper is based on the nearest neighbor or SVM, which requires neural networks to extract features for learning. However, the extraction process is a black-box model, and it is difficult to combine the features extracted by the deep network with the method in this paper without mathematics analysis and experimental verification in this regard.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster