# Generalization Bounds for Few-Shot Transfer Learning with Pretrained
Classifiers

Tomer Galanti<EMAIL_ADDRESS>
McGovern Institute
Massachusetts Institute of Technology
Cambridge, MA, USA András György<EMAIL_ADDRESS>
Google DeepMind
London, UK Marcus Hutter<EMAIL_ADDRESS>
Google DeepMind
London, UK

###### Abstract

We study the ability of foundation models to learn representations for
classification that are transferable to new, unseen classes. Recent results in
the literature show that representations learned by a single classifier over
many classes are competitive on few-shot learning problems with
representations learned by special-purpose algorithms designed for such
problems. We offer a theoretical explanation for this behavior based on the
recently discovered phenomenon of class-feature-variability collapse, that is,
that during the training of deep classification networks the feature
embeddings of samples belonging to the same class tend to concentrate around
their class means. More specifically, we show that the few-shot error of the
learned feature map on new classes (defined as the classification error of the
nearest class-center classifier using centers learned from a small number of
random samples from each new class) is small in case of class-feature-
variability collapse, under the assumption that the classes are selected
independently from a fixed distribution. This suggests that foundation models
can provide feature maps that are transferable to new downstream tasks, even
with very few samples; to our knowledge, this is the first performance bound
for transfer-learning that is non-vacuous in the few-shot setting.

Keywords: Generalization bounds, foundation models, few-shot learning,
transfer learning, neural collapse, class-features variability collapse.

##  1 Introduction

In a variety of machine learning applications, we have access to a limited
amount of data from the task that we would like to solve, as labeled data is
oftentimes scarce and/or expensive. In such scenarios, training directly on
the available data is unlikely to produce a hypothesis that performs well on
new, unseen test samples. A prominent solution to this problem is to apply
transfer learning (see, e.g., Caruana, 1995; Bengio, 2012; Yosinski et al.,
2014). In transfer learning, we are typically given a large-scale source task
(e.g., ImageNet ILSVRC, Russakovsky et al., 2015) and a target task from which
we encounter only a limited amount of data. While there are multiple
approaches to transfer knowledge between tasks, a popular approach suggests to
train a large neural network on a source classification task with a wide range
of classes (such as ResNet50, He et al., 2016, MobileNet, Howard et al., 2017
or the VGG network, Simonyan and Zisserman, 2014), and then to train a
relatively smaller network (e.g., a linear classifier or a shallow MLP) on top
of the penultimate (also known as feature) layer of the pretrained model,
using the data available in the target task.

Due to the effectiveness of this approach, transfer learning has become a
central element in the machine learning toolbox. For instance, using
pretrained feature maps is common practice in a variety of applications,
including fine-grained classification (Chen et al., 2019a; Huang and Li, 2020;
Yang et al., 2018), object detection, (Redmon et al., 2016; Ren et al., 2015;
He et al., 2017), semantic segmentation (Long et al., 2015; Chen et al.,
2018), or medical imaging (Chen et al., 2019b). In fact, due to the cumulative
success of transfer learning, large pretrained models that can be effectively
adapted to a wide variety of tasks (Brown et al., 2020; Ramesh et al., 2021)
have recently been characterized as foundation models (Bommasani et al.,
2021), emphasizing their central role in solving various learning tasks.

Foundation models are typically pretrained on a source task at a time when the
concrete details of the target task(s) are not – or only partially – available
to the practitioner. Therefore, the ability to precondition or design the
training regime of the foundation model to match the target task is limited.
As a result, there may be a mismatch between the source and target tasks, such
as a different number of classes or a different number of available samples.
This suggests that a foundation model should be generic and applicable to a
wide range of tasks.

On the other hand, when some specifics of the target tasks are known, often
special-purpose algorithms are designed to utilize this information. Such an
example is the problem of few-shot learning, when it is known in advance that
the target problems come with a very small training set (Vinyals et al., 2016;
Ravi and Larochelle, 2017; Finn et al., 2017; Lee et al., 2019). While these
specialized algorithms have significantly improved the state of the art, the
recent work of Tian et al. (2020); Dhillon et al. (2020) demonstrated that
predictors trained on top of foundation models can also achieve state-of-the-
art performance on few-shot learning benchmarks.

#### Contributions.

In previous work (Galanti et al., 2022b), we provided an explanation for the
success of transfer learning between classification problems based on the
phenomenon of neural collapse (Papyan et al., 2020). Informally, neural
collapse (see Section 3) describes the training dynamics of deep networks for
standard classification tasks, where multiple structural properties arise. A
central property, known as class-features variability collapse, asserts that
the features (the output of the penultimate layer of the deep network)
associated with training samples belonging to the same class tend to
concentrate around their class feature mean. We argued that this property
generalizes to new data points and new classes (e.g., the target classes) when
the model is trained on several classes with many samples each. Additionally,
we showed that in the presence of neural collapse, training a linear
classifier on top of the learned feature map can generalize well even with few
samples. However, our analysis relied on assumptions about the feature maps
that may be difficult to justify in practical situations.

In this paper we provide a stronger theoretical analysis for this problem
without relying on this kind of assumptions. Instead of claiming that feature-
variability collapse generalizes to new samples and classes, we argue that
weaker notions of clustering generalize to new samples and classes.
Specifically, we study the few-shot error of the learned feature map, which is
the classification error of nearest class-center classifiers on top of the
feature map with centers learned using a small number of random samples. We
show that the few-shot error generalizes from training to test data (Lemma 4),
and upper bound the expected few-shot error between new classes using the
average few-shot error between the source classes (Lemma 5). Additionally, we
show that the few-shot error on the training data can be upper bounded using
the degree of feature-variability collapse (Lemmas 6–8). Based on this
analysis, we prove that large neural networks that exhibit feature-variability
collapse when trained on many classes and samples can be easily adapted to new
downstream tasks with very few samples (Theorems 4 and 5). While our results
provide a proof of concept for the ability of pre-trained classifiers to
easily adapt to new tasks with very few samples, our bounds are typically
loose, akin to traditional generalization bounds.

###  1.1 Related Work

#### Generalization bounds for transfer and meta-learning.

Several theoretical frameworks have been proposed to study various multi-task
learning settings (Baxter, 2000; Maurer et al., 2016; Pentina and Lampert,
2014; Galanti et al., 2016; Khodak et al., 2019; Du et al., 2021). However,
these frameworks all consider settings in which the learning algorithm is
provided with a sequence of similar learning problems (e.g., problems selected
independently from the same distribution over tasks), and therefore cannot be
used to study the case where only a single source task is available, which is
quite different from the target task.

In contrast, we propose a theoretical framework in which the learning
algorithm is provided with one classification task and is required to learn a
representation of the data that can be adapted to solve new unseen tasks using
a limited amount of data. This framework is more closely aligned with the
common practice of transfer learning using deep neural networks.

Furthermore, while the aforementioned papers indeed show that having a
collection of similar source tasks are useful in learning feature vectors
(essentially, as if the number of data points was the number of points in all
the source tasks), they require that the final target task have enough samples
to learn a classifier in the feature space. This is in stark contrast to our
results as our bounds remain meaningful (and are especially derived for this
case) when the number of samples in the target class is a small constant.

#### Feature clustering and transfer learning.

The connection between clustering in the feature space and few-shot transfer
learning has been explored empirically by Goldblum et al. (2020): They
demonstrated on multiple benchmark tasks that the more the feature embeddings
of the classes are clustered the better the few-shot performance is. Motivated
by this observation, they designed modified training algorithms that directly
encourage clusterability, which led to better few-shot transfer performance
for both in meta-learning and in classical training of foundation models. As
their notion of feature-clusterability is essentially the same as the class-
features variability collapse we consider in this paper (although the
mathematical details are somewhat different, with our measure being more local
than theirs, see the discussion in Section 3), our results also give a
theoretical explanation to their empirical observations.

###  1.2 Notation

Throughout the paper we use the following notation. $\|\cdot\|$ denotes the
Euclidean norm for vectors and the spectral norm for matrices. For matrices we
also use $\|\cdot\|_{F}$ to denote the Frobenius norm. For a distribution $Q$
over $\mathcal{X}\subset\mathbb{R}^{d}$ and $u:\mathcal{X}\to\mathbb{R}^{p}$,
the mean and variance of $u(x)$ for $x\sim Q$ are denoted by
$\mu_{u}(Q):=\mathbb{E}_{x\sim Q}[u(x)]$ and by
$\mathrm{Var}_{u}(Q):=\mathbb{E}_{x\sim Q}[\|u(x)-\mu_{u}(Q)\|^{2}]$, where
$\mathbb{E}_{x\sim Q}[\cdot]$ denotes the expectation operator according to
$x$ with distribution $Q$ (we may omit $Q$ when it is clear from the context).
For a finite set $A=\\{a_{i}\\}^{n}_{i=1}$, we denote
$\operatorname{Avg}^{n}_{i=1}[a_{i}]:=\frac{1}{n}\sum^{n}_{i=1}a_{i}$ and by
$U[A]$ the uniform distribution over $A$. We write $x\sim A$ to denote $x\sim
U[A]$ for a finite set $A$, and to simplify notation, in some similar cases we
use $A$ in place of $U[A]$ where it does not cause confusion. For a positive
integer $k$, we use $[k]:=\\{1,\ldots,k\\}$; to simplify the notation, we
write $U[k]$ in place of $U[[k]]$. For an event $E$, $\mathbb{I}[E]$ denotes
its indicator function (equals 1 if the event holds and 0 otherwise).
$\mathbf{0}$ denotes the zero-vector of appropriate dimension. For a class of
functions $\mathcal{H}\subset\\{h:\mathcal{W}\to\mathcal{Z}\\}$ for some sets
$\mathcal{W}$ and $\mathcal{Z}$ and a (multi-)set $W\subset\mathcal{W}$, we
denote $h(W):=\\{h(w):w\in\mathcal{W}\\}$ for any $h\in\mathcal{H}$ (i.e., $h$
is applied elementwise), and we also define $\mathcal{H}(W):=\\{h(w):w\in
W,h\in\mathcal{H}\\}$. We use similar notation when $W$ is a vector. We use
$\log$ to denote the natural logarithm.

##  2 Problem Setup

We study a transfer learning setting in which a model is pretrained on a
source task and later adapted to solve downstream tasks. To model this setup,
we assume that the final downstream task is a balanced $k$-class
classification problem, called the _target_ problem, and the auxiliary task,
which is used to train the feature representation, is a balanced $l$-class
classification problem, called the _source_ problem. Formally, a target task
is defined by a distribution $P$ over samples
$(x,y)\in\mathcal{X}\times\mathcal{Y}_{k}$, where
$\mathcal{X}\subset\mathbb{R}^{d}$ is the instance space and
$\mathcal{Y}_{k}:=[k]$ is the label space. For a pair $(x,y)$ with
distribution $P$, we denote by $P_{c}$ the class-conditional distribution of
$x$ given $y=c$ (i.e.,
$P_{c}(\boldsymbol{\cdot})=\Pr[x\in\boldsymbol{\cdot}\mid y=c]$).

Our goal is to learn a classifier $h:\mathcal{X}\to\mathcal{Y}_{k}$ that
minimizes the target test error

$L_{P}(h)~{}:=~{}\mathbb{E}_{(x,y)\sim P}\big{[}\mathbb{I}[h(x)\neq
y]\big{]}.$ (1)

The algorithm is provided with a labeled training dataset
$S:=\cup^{k}_{c=1}S_{c}$, where the sets $S_{c}:=\\{x_{ci}\\}^{n}_{i=1}$ are
drawn from the class-conditional distributions $P_{c}$, but the true
distributions $P_{c}$ (and $P$) are unknown. We assume that $P$ is a balanced
distribution (i.e., $P[y=c]=1/k$) with class-conditional distributions
$\\{P_{c}\\}^{k}_{c=1}$ and that the training data $S$ is also balanced over
the $k$ classes (as described above).

When the number of training samples $n$ (for each class) is small, it may be
difficult to train a classifier on $S$ that achieves good performance on the
target task. To address this issue, we aim to learn a classifier of the form
$h=g\circ f$, where
$f\in\mathcal{F}\subset\\{f^{\prime}:\mathbb{R}^{d}\to\mathbb{R}^{p}\\}$ is a
feature map and
$g\in\mathcal{G}\subset\\{g^{\prime}:\mathbb{R}^{p}\to\mathbb{R}^{k}\\}$ is a
classifier used on the feature space $\mathbb{R}^{p}$. The idea is to learn
the feature map $f$ based on a different problem where more data is available,
and then train the classifier $g$ to solve the hopefully simpler
classification problem of predicting $y$ based on $f(x)$ instead of $x$. That
is, $g$ is actually a function of the modified labeled training data
$\cup^{k}_{c=1}\\{f(x_{ci})\\}_{i=1}^{n}$. To emphasize this dependence, we
use the notation $g_{f,S}$ for the trained classifier based on the features,
and $h_{f,S}=g_{f,S}\circ f$ for the full classifier.

We assume that the source task used to learn the feature map $f$ is a single
$l$-class classification problem over the same sample space $\mathcal{X}$,
given by a distribution $\tilde{P}$. We are interested in finding a classifier
$\tilde{h}:\mathcal{X}\to\mathbb{R}^{l}$ of the form $\tilde{h}=\tilde{g}\circ
f$, where
$\tilde{g}\in\tilde{\mathcal{G}}\subset\\{g^{\prime}:\mathbb{R}^{p}\to\mathbb{R}^{l}\\}$
is a classifier over the feature space
$f(\mathcal{X}):=\\{f(x):x\in\mathcal{X}\\}$. Given a training dataset
$\tilde{S}:=\cup^{l}_{c=1}\\{(\tilde{x}_{ci})\\}_{i=1}^{m}$, we train the
classifier $\tilde{h}$ on $\tilde{S}$ with the goal of minimizing the source
test error, $L_{\tilde{P}}(\tilde{h}_{\tilde{S}})$.

Similarly to the target task, we assume that $\tilde{P}$ is balanced (i.e.,
$\tilde{P}[y=c]=1/l$) with class-conditionals $\\{\tilde{P}_{c}\\}^{l}_{c=1}$,
and that the dataset $\tilde{S}=\cup^{l}_{c=1}\\{\tilde{x}_{ci}\\}^{m}_{i=1}$
is also balanced with
$\tilde{S}_{c}:=\\{\tilde{x}_{ci}\\}^{m}_{i=1}\sim\tilde{P}^{m}_{c}$. Finally,
we assume that the _classes in the source and target tasks are selected
randomly_ : that is, the elements of the sets of class-conditionals,
$\tilde{\mathcal{P}}:=\\{\tilde{P}_{c}\\}^{l}_{c=1}$ and
$\mathcal{P}:=\\{P_{c}\\}^{k}_{c=1}$ for the source and target tasks,
respectively, are independent and identically distributed (i.i.d.), drawn from
a distribution $\mathcal{D}$ over a set of class-conditional distributions
$\mathcal{E}$. For simplicity, we could assume that the classification
problems are all noiseless, that is, the supports of the class-conditional
distributions in $\mathcal{E}$ are disjoint. While this is not needed for our
theorems to hold, it is needed for neural collapse to occur, which is
essential so that our theoretical results provide an explanation for the
success of few-shot learning. However, as our results are still meaningful
under approximate neural collapse, which may still occur under some limited
label noise, we keep our definition general.

In a typical transfer learning setting, the classifier $\tilde{h}$ is a deep
neural network, and $f$ is the representation in the last internal layer of
the network, a.k.a. the _penultimate_ or _feature embedding_ layer. The last
layer of the network, $\tilde{g}$, is often a linear map, and the same is true
for $g$ in the target problem. The learned feature map $f$ is called a
_foundation model_ when it can be effectively used in a wide range of target
tasks.

The effectiveness of a foundation model $f$ in dealing with downstream tasks
can be measured by the transfer error of the trained classifier $h_{f,S}$,
defined as the expected error
$\mathbb{E}_{P\sim\mathcal{D}}\mathbb{E}_{S:S_{c}\sim
P_{c}^{n}}[L_{P}(h_{f,S})]$ taken over both the training and the evaluation on
the random target task. For concreteness, we focus on the simple _nearest
class-center (NCC)_ classification rule

$h_{f,S}^{\text{\tiny
NCC}}(x)~{}:=~{}\operatorname*{arg\,min}_{c\in[C]}\|f(x)-\mu_{f}(S_{c})\|,$
(2)

that attributes $x$ to a class $c$ if its embedding $f(x)$ is closest to the
empirical class center $\mu_{f}(S_{c})$ amongst all centers
$\\{\mu_{f}(S_{c})\\}^{C}_{c=1}$. Then the _transfer error_ of $f$ is defined
as

$\mathcal{L}_{\mathcal{D}}(f)~{}:=~{}\mathbb{E}_{P\sim\mathcal{D}}\mathbb{E}_{S:S_{c}\sim
P_{c}^{n}}[L_{P}(h_{f,S}^{\text{\tiny NCC}})],$ (3)

(the expectation is taken over the random choice of target tasks $P$ and the
training data $S$ for the target class). Note that while the feature map $f$
is evaluated on the distribution of the target task $P$ determined by
$\mathcal{D}$, the training of $f$ in a foundation model is completely
independent of this target. As the main contribution of the paper, we analyze
the above setting and provide an explanation why transfer learning (or more
precisely NCC classification) is effective through the concept of neural
collapse.

#### Network architectures.

For concreteness, we focus on the case where $\mathcal{F}$, the class of
feature maps, is a set of depth-$q$ ReLU neural networks of the form
$f(\boldsymbol{\cdot})=W^{q}\sigma(W^{q-1}\dots\sigma(W^{1}\boldsymbol{\cdot})):\mathbb{R}^{d}\to\mathbb{R}^{p}$,
where $\sigma(x):=\max\\{0,x\\}$ is the element-wise ReLU function, and
$W^{i}\in\mathbb{R}^{d_{i+1}\times d_{i}}$ for $i\in[q]$, where $d_{1}=d$ and
$d_{q+1}=p$. Our bounds depend on the norm of a network $f$, which is defined
as

$\mathcal{C}(f)~{}:=~{}\prod^{q}_{i=1}\|W^{i}\|_{F},$ (4)

where $\|\cdot\|_{F}$ is the Frobenius norm. This quantity upper bounds the
Lipschitz constant of $f$ and is similar in fashion to other (slightly
different) norms of neural networks (Golowich et al., 2017; Bartlett et al.,
2017).

####

Finally, we assume that the sample space $\mathcal{X}$ is compact and define
$B:=\sup_{x\in\mathcal{X}}\|x\|<\infty$. Combining this with the facts that
$\mathcal{C}(f)$ bounds the Lipschitz constant of a ReLU network
$f\in\mathcal{F}$ and that $f(\mathbf{0})=\mathbf{0}$, it follows that for any
$f\in\mathcal{F}$ and $x\in\mathcal{X}$,

$\|f(x)\|\leq\mathcal{C}(f)\cdot\|x\|\leq\mathcal{C}(f)B.$

##  3 Neural Collapse

Neural collapse (NC) is a recently discovered phenomenon in deep learning
(Papyan et al., 2020). It occurs in learning settings where, during the
training of deep networks for standard classification tasks with deterministic
labels, the feature embeddings (the output of the penultimate, or embedding,
layer) associated with training samples belonging to the same class tend to
concentrate around their means, or – in other words – the classes are
clustered. Specifically, Papyan et al. (2020) observed that the ratio of the
within-class variances and the distances between the class means converge to
zero (NC1).111Note that condition NC1 of Papyan et al. (2020), called
_variability collapse_ , only requires that the average within-class variance
tends to zero, and the condition on the normalized (or relative) variance we
consider here only follows from having properly normalized and maximally
distant class means as dictated by NC2. In the paper we refer to our more
general and more meaningful notion as _class-features variability collapse_.
They also noticed that, asymptotically, the class means are not only linearly
separable, but are also maximally distant (and hence orthogonal) with the same
norm when normalized properly (NC2). Furthermore, the weights of the last
(linear) layer converge to the class means (NC3), and hence the behavior of
the last-layer classifier (operating on the features) converges to that of the
NCC decision rule (NC4). In other words, neural collapse is a phenomenon in
which deep learning models exhibit a particular behavior during training,
resulting in a concentration of feature embeddings around their mean for each
class in the training set.

In this paper, we focus on two properties related to neural collapse: class-
features variability collapse and the nearest class-center separability, both
defined below. We will explore how these properties affect the performance of
transfer learning and foundation models.

#### Class-features variability collapse.

In this work we use a simplified version of normalized class-features
variability collapse, introduced in our initial paper (Galanti et al., 2022b):
For a feature map $f:\mathbb{R}^{d}\to\mathbb{R}^{p}$ and two distributions
$Q_{i},Q_{j}$ over $\mathcal{X}\subset\mathbb{R}^{d}$, we define their _class-
distance normalized variance_ (CDNV) as

$V_{f}(Q_{i},Q_{j})~{}:=~{}\frac{\mathrm{Var}_{f}(Q_{i})}{\|\mu_{f}(Q_{i})-\mu_{f}(Q_{j})\|^{2}}.$

Furthermore, the definition can be extended to finite sets
$S_{1},S_{2}\subset\mathcal{X}$ by defining

$V_{f}(S_{1},S_{2})~{}:=~{}V_{f}(U[S_{1}],U[S_{2}]).$

This quantity essentially measures to what extent the feature vectors of
samples from $Q_{i}$ and $Q_{j}$ are clustered in space. Suppose we have a
learning algorithm that, given a training dataset $\tilde{S}$, returns a
classifier $h^{(t)}=g^{(t)}\circ f^{(t)}$ after $t$ iterations, we say that it
satisfies _class-features variability collapse_ if

$\lim_{t\to\infty}\operatorname{Avg}_{i\neq
j\in[l]}[V_{f^{(t)}}(\tilde{S}_{i},\tilde{S}_{j})]=0,$ (5)

where $f^{(t)}$ is the penultimate layer of the neural network
$h^{(t)}=g^{(t)}\circ f^{(t)}$ produced by the learning algorithm after $t$
iterations. Similarly to the measure proposed by Papyan et al. (2020), in
practice exact convergence to zero rarely occurs, but we show experimentally
in Section 6 that the left-hand side of the equation above does indeed
decrease to some small value during training. Galanti et al. (2022a)
demonstrated empirically that the limit decreases significantly when the depth
of the network $f$ is increased.

It is interesting to note that while our average CDNV measures pairwise
separability of the classes (as we shall see), related measures of class-
features clustering considered in the literature are much more global: In the
context of measuring class-features clustering for few-shot learning, Goldblum
et al. (2020) considered
$\frac{l\cdot\operatorname{Avg}_{i\in[l]}[\mathrm{Var}_{f}(Q_{i})]}{\operatorname{Avg}_{i\in[l]}[\|\mu_{f}(Q_{i})-\mu_{G}\|^{2}]}$
where $\mu_{G}=\operatorname{Avg}_{i\in[l]}[\mu_{f}(Q_{i})]$ is the global
mean of the data, while Papyan et al. (2020) used the trace of
$\Sigma_{W}\Sigma_{B}^{\dagger}/l$ to measure neural collapse where
$\Sigma_{W}=\operatorname{Avg}_{i\in[l]}\mathbb{E}_{x\sim
Q_{i}}[(x-\mu_{f}(Q_{i}))(x-\mu_{f}(Q_{i}))^{\top}]$ is the average within-
class covariance matrix and $\Sigma_{B}^{\dagger}$ is the Moore-Pensrose
inverse of the average between-class covariance matrix
$\Sigma_{B}=\operatorname{Avg}_{i\in[l]}[(\mu_{f}(Q_{i})-\mu_{G})(\mu_{f}(Q_{i})-\mu_{G})^{\top}]$.
Introducing a pairwise measure of separability instead of a global one greatly
facilitates our analysis.

#### Nearest class-center separability.

A weaker notion of neural collapse, known as NCC separability, asserts that
the features of samples from the same class can be accurately classified using
the nearest class-center classification rule. To this end, the _expected
$\Delta$-margin NCC classification error_ of a feature map
$f:\mathbb{R}^{d}\to\mathbb{R}^{p}$ for two classes with class-conditional
distributions $Q_{i}$ and $Q_{j}$ is defined as

$E_{\Delta}(f;Q_{i},Q_{j})~{}:=~{}\mathbb{E}_{x_{i}\sim
Q_{i}}\Big{[}\mathbb{I}\big{[}\|f(x_{i})-\mu_{f}(Q_{j})\|\leq\|f(x_{i})-\mu_{f}(Q_{i})\|+\Delta\big{]}\Big{]},$
(6)

where $\Delta>0$ is a margin of our choice. By setting $\Delta=0$, we simply
obtain the expected classification error of the NCC classifier for the two-
class classification problem of separating samples from $Q_{i}$ and $Q_{j}$
(not considering ties for the NCC classifier for simplicity). In particular,
given a dataset $\tilde{S}=\cup^{C}_{c=1}\tilde{S}_{c}$ and a mapping $f$, we
can measure the degree of NCC separability by $\operatorname{Avg}_{i\neq
j\in[l]}E_{\Delta}(f;\tilde{S}_{i},\tilde{S}_{j})$ (where the average is taken
over all ordered pairs of classes), which in turn is an upper bound on the
average training loss.

Suppose we have a learning algorithm that, given a training dataset
$\tilde{S}$, returns a neural network $h^{(t)}=g^{(t)}\circ f^{(t)}$ after $t$
iterations, we say that it satisfies _NCC separability_ with margin $\Delta$
if the aforementioned upper bound on the classification error of the NCC
classifier approaches zero as $t$ goes to infinity:

$\lim_{t\to\infty}\operatorname{Avg}_{i\neq
j\in[l]}[E_{\Delta}(f^{(t)};\tilde{S}_{i},\tilde{S}_{j})]=0.$ (7)

Here, again, $f^{(t)}$ is the penultimate layer of the neural network
$h^{(t)}=g^{(t)}\circ f^{(t)}$.

As we show in Lemma 7, NCC separability is a weaker notion of collapse than
variability collapse, as the NCC error rate can be upper bounded in terms of
the CDNV. However, the NCC error can be zero in cases where the CDNV is larger
than zero (see the example after Lemma 7).

##  4 Generalization Bounds for Transfer Learning

In our previous paper (Galanti et al., 2022b), we introduced generalization
bounds for transfer learning in the setting of Section 2. Our analysis was
divided into three main steps. First, we showed that if the CDNV on the
training data, $\operatorname{Avg}_{i\neq
j\in[l]}[V_{f}(\tilde{S}_{i},\tilde{S}_{j})]$, is small at the end of
training, then we can expect that the CDNV over unseen samples,
$\operatorname{Avg}_{i\neq j\in[l]}[V_{f}(\tilde{P}_{i},\tilde{P}_{j})]$,
would also be small for the same classes when $m$ is sufficiently large (see
Lemma 1 of Galanti et al., 2022b). As a second step, we bounded the expected
CDNV between two new target classes, $\mathbb{E}_{P_{c}\neq
P_{c^{\prime}}}[V_{f}(P_{c},P_{c^{\prime}})]$ (here the expectation is taken
with respect to the random choice of the target class conditionals $P_{c}$ and
$P_{c^{\prime}}$ under the condition that they are different), using the CDNV
between the source classes, $\operatorname{Avg}_{i\neq
j\in[l]}[V_{f}(\tilde{P}_{i},\tilde{P}_{j})]$. Finally, we proved that
$\mathcal{L}_{\mathcal{D}}(f)=\mathbb{E}_{P}\mathbb{E}_{S}[L_{P}(h_{f,S}^{\text{\tiny
NCC}})]\leq C(k+{\textstyle\frac{k}{n}})\cdot\mathbb{E}_{P_{c}\neq
P_{c^{\prime}}}[V_{f}(P_{c},P_{c^{\prime}})]$, where $C>0$ is some constant
and $h_{f,S}^{\text{\tiny NCC}}$ is the NCC classifier defined in (2).

However, there are several limitations to this argument. The first issue
arises from the fact that $\mathbb{E}_{P_{c}\neq
P_{c^{\prime}}}[V_{f}(P_{c},P_{c^{\prime}})]$ may be very large even when
$\mathcal{L}_{\mathcal{D}}(f)$ is very small. For example, if the support
$\mathcal{E}$ of $\mathcal{D}$ is infinite and $f$ is bounded, then the set
${\mu_{f}(P_{c})}_{P_{c}\in\mathcal{E}}\subset\mathbb{R}^{p}$ has at least one
limit point, and therefore, $\inf_{P_{1}\neq
P_{2}\in\mathcal{E}}\|\mu_{f}(P_{1})-\mu_{f}(P_{2})\|=0$ and
$\mathbb{E}_{P_{c}\neq P_{c^{\prime}}}[V_{f}(P_{c},P_{c^{\prime}})]=\infty$.
In addition, the upper bound on $\mathbb{E}_{P_{c}\neq
P_{c^{\prime}}}[V_{f}(P_{c},P_{c^{\prime}})]$ scales with the inverse of
$\inf_{f\in\mathcal{F}}\inf_{P_{1}\neq
P_{2}\in\mathcal{E}}\|\mu_{f}(P_{1})-\mu_{f}(P_{2})\|$, which may be very
large even if $\mathcal{E}$ is finite (for example, if $\mathcal{F}$ contains
a constant function).

In this paper we aim to circumvent these issues and provide an upper bound on
the transfer error $\mathcal{L}_{\mathcal{D}}(f)$ of $f$ which does not suffer
from these limitations. Instead of bounding the term $\mathbb{E}_{P_{c}\neq
P_{c^{\prime}}}[V_{f}(P_{c},P_{c^{\prime}})]$, we bound
$\mathcal{L}_{\mathcal{D}}(f)$ with the average margin error of the few-shot
NCC classifier between pairs of source classes $i\neq j$ (Lemma 4). As a next
step, we show that each of these error terms can be bounded using the average
margin error of few-shot NCC classifiers over the training data of classes $i$
and $j$ (Lemma 5). Finally, we provide various upper bounds to these terms
based on the CDNV between the two samples,
$V_{f}(\tilde{S}_{i},\tilde{S}_{j})$ (Lemmas 6-8). Combining these bounds we
obtain the main results of this paper: upper bounds on the transfer error of
$f$ in terms of the average CDNV between pairs of source classes,
$\operatorname{Avg}_{i\neq j}[V_{f}(\tilde{S}_{i},\tilde{S}_{j})]$, which
typically yields small values, as demonstrated empirically in Section 6.

Our first results, Theorem 1 covers the general case, while Theorem 3 provides
somewhat better results when the feature embeddings satisfy certain symmetry
properties. The main proof components (i.e., the aforementioned lemmas) are
presented in the next section, while the full proofs of the theorems are given
in Section 5.4.

###### Theorem 1

Let $\delta\in(0,1)$, $l\geq 2$, $1\leq n\leq\sqrt{m}$ and let $\mathcal{F}$
be a class of ReLU neural networks of depth $q$. Let $\Lambda:=\min_{i\neq
j\in[l]}\|\mu_{f}(\tilde{S}_{i})-\mu_{f}(\tilde{S}_{j})\|$ and define
$\kappa:=\frac{m}{m-n}$. Then, with probability at least $1-\delta$ over the
selection of the source class-conditionals
$\tilde{\mathcal{P}}=\\{\tilde{P}_{c}\\}^{l}_{c=1}$ and the corresponding
source training data $\tilde{S}_{1}\dots,\tilde{S}_{l}$, for any
$f\in\mathcal{F}$, we have

$\displaystyle\mathcal{L}_{\mathcal{D}}(f)$ $\displaystyle\leq
C_{1}(k-1)\kappa\operatorname{Avg}_{i\neq
j\in[l]}[V_{f}(\tilde{S}_{i},\tilde{S}_{j})]+(k-1)\kappa\delta^{2}$
$\displaystyle\quad+C_{2}\frac{(k-1)\lceil\mathcal{C}(f)\rceil B\kappa
n^{2}}{\Lambda\sqrt{m-n}}\sqrt{(q+\log(p))\log(m)}$
$\displaystyle\quad+C_{3}\frac{(k-1)\lceil\mathcal{C}(f)\rceil
B\kappa}{\Lambda\sqrt{m-n}}\sqrt{\log\left({\textstyle\frac{l^{2}(\lceil\mathcal{C}(f)\rceil+1)^{2}\left(\left|\log\left({\textstyle\frac{\Lambda}{40B}}\right)\right|+2\right)^{2}}{\delta}}\right)}$
$\displaystyle\quad+C_{4}\frac{(k-1)\lceil\mathcal{C}(f)\rceil
B}{\Lambda\sqrt{l}}\left(\\!\sqrt{\log(l)(q+\log(p))}+\sqrt{\log\left({\textstyle\frac{(\lceil\mathcal{C}(f)\rceil+1)\left(\left|\log\left({\textstyle\frac{\Lambda}{40B}}\right)\right|+2\right)}{\delta}}\right)}\
\right)\\!,$

where $C_{1},C_{2},C_{3},C_{4}>0$ are appropriate constants.

In the above theorem, we bound the transfer error
$\mathcal{L}_{\mathcal{D}}(f)$, which is the quantity that measures the
performance of $f$ in adapting to new tasks with very few samples. For
simplicity, we stated the bound without explicitly specifying the constants,
which are given in (12) in Section 5.4.

To interpret the bound, note that we are interested in the regime where $n$ is
a constant (or when $n=o(m^{1/4})$), hence
$\kappa={\textstyle\frac{m}{m-n}}\approx
1+\mathcal{O}({\textstyle\frac{1}{m}})$ (or $1+o(m^{-3/4})$). The bound is
composed of multiple terms. The first term is proportional to $k$ (the number
of target classes) times the average CDNV over the source training data,
$\operatorname{Avg}_{i\neq j\in[l]}[V_{f}(\tilde{S}_{i},\tilde{S}_{j})]$,
which is expected to be small in the presence of neural collapse. The second
term scales as $\mathcal{O}\left(\kappa k\delta^{2}\right)$ that depends on a
free parameter $\delta$ that can be selected to be very small, as the other
terms scale (poly-)logarithmically with respect to $1/\delta$. The third term
scales as
$\tilde{\mathcal{O}}\left({\textstyle\frac{n^{2}k\sqrt{q}\lceil\mathcal{C}(f)\rceil
B}{\Lambda\sqrt{m}}}\right)$ dominating the fourth term which is a factor
$1/n^{2}$ smaller, while the last term scales as
$\tilde{\mathcal{O}}\left({\textstyle\frac{k\sqrt{q}\lceil\mathcal{C}(f)\rceil
B}{\Lambda\sqrt{l}}}\right)$.

Thus, selecting, e.g., $\delta=1/m$, the terms other than the CDNV in the
bound are of order ${\textstyle\frac{k\sqrt{q}\lceil\mathcal{C}(f)\rceil
B}{\Lambda}}\cdot\left({\textstyle\frac{n^{2}}{\sqrt{m}}}+{\textstyle\frac{1}{\sqrt{l}}}\right)$
up to logarithmic factors, which goes to zero with $m$ and $l$ increasing as
desired (with the square-root rate expected from standard concentration
arguments), while in the numerator we have typical complexity terms. The two
unusual terms are $n^{2}$ in the numerator and $\Lambda$ in the denominator.
The presence of $n$ is somewhat undesired and is probably the artifact of our
proof technique as one would expect better performance as the number of
samples in the target problems increases; however, since we are interested in
the regime where $n$ is very small (a small constant, typically below $10$),
this is only a slight problem. $\Lambda$ is a data-dependent term, measuring
the minimum pairwise distance of the class-means. According to previous work
on neural collapse (Papyan et al., 2020; Mixon et al., 2020; Zhu et al., 2021;
Xu et al., 2021; Tirer and Bruna, 2022), under the usual conditions required
for neural collapse (such as, training with weight decay, the features are
properly normalized and $p\geq l$), the function $f$ converges to a solution
such that $\\{\mu_{f}(\tilde{S}_{i})\\}^{l}_{i=1}$ forms a simplex equiangular
tight frame, meaning that the class centers $\mu_{f}(\tilde{S}_{i})$ are of
equal length and the distances
$\|\mu_{f}(\tilde{S}_{i})-\mu_{f}(\tilde{S}_{j})\|$ are also equal and
maximized for all $i\neq j$. This property, which is typically referred to as
NC2 in the literature, implies that
$\Lambda=\sqrt{2}\|\mu_{f}(\tilde{S}_{i})\|$. To empirically validate that
$\Lambda$ is indeed maximized, we evaluated $\Lambda$ during our experiments
(reported in Section 6.3), and we can observe that it significantly increases
during training. Therefore, if $n=\mathcal{O}(1)$ and $l$ and $m$ are large,
and if neural collapse is present in the source data (i.e.,
$\operatorname{Avg}_{i\neq j\in[l]}[V{f}(\tilde{S}_{i},\tilde{S}_{j})]$ is
small) and $\mathcal{C}(f)$ is bounded (as a function of $m$ and $l$, i.e., if
the size of the neural network $f$ only mildly increases with the amount of
the input data, as per the practitioner’s choice), then the few-shot transfer
error $\mathcal{L}_{\mathcal{D}}(f)$ is also small.

Next we present two improvements for Theorem 1, both aiming to improve the
dependence on the CDNV, $\operatorname{Avg}_{i\neq
j\in[l]}[V{f}(\tilde{S}_{i},\tilde{S}_{j})]$. The first idea is to measure
neural collapse with the weaker notion of the average $\Delta$-margin error
$\operatorname{Avg}_{i\neq j\in[l]}[E_{8\Delta}(\tilde{S}_{i},\tilde{S}_{j})]$
for some specific choice of $\Delta$. In fact, if the feature vectors are
sufficiently clustered during training, then the $\Delta$-margin error can
easily vanish while the CDNV remains positive.

###### Theorem 2

Let $\delta\in(0,1)$, $l\geq 2$, $1\leq n\leq\sqrt{m}$ and let $\mathcal{F}$
be a class of ReLU neural networks of depth $q$. Furthermore, let
$\Lambda_{ij}:=\|\mu_{f}(\tilde{S}_{i})-\mu_{f}(\tilde{S}_{j})\|$ for
$i,j\in[l]$, $\Lambda:=\min_{i\neq j\in[l]}\Lambda_{ij}$ as before, and define
$\kappa:=\frac{m}{m-n}$. Then, with probability at least $1-\delta$ over the
selection of the source class-conditionals
$\tilde{\mathcal{P}}=\\{\tilde{P}_{c}\\}^{l}_{c=1}$ and the corresponding
source training data $\tilde{S}_{1}\dots,\tilde{S}_{l}$, for any
$f\in\mathcal{F}$ and $\phi>0$, we have

$\displaystyle\mathcal{L}_{\mathcal{D}}(f)$ $\displaystyle\leq
C_{1}(k-1)\kappa\left(\operatorname{Avg}_{i\neq
j\in[l]}[E_{\phi\Lambda}(f;\tilde{S}_{i},\tilde{S}_{j})]+\frac{C_{2}}{\phi^{2}n^{2}}\operatorname{Avg}_{i\neq
j\in[l]}\left[\frac{\Lambda_{ij}^{2}}{\Lambda^{2}}V_{f}(\tilde{S}_{i},\tilde{S}_{j})\right]\right)$
$\displaystyle\quad+(k-1)\kappa\delta^{2}+C_{3}\frac{(k-1)\lceil\mathcal{C}(f)\rceil
B\kappa n^{2}}{\phi\Lambda\sqrt{m-n}}\sqrt{(q+\log(p))\log(m)}$
$\displaystyle\quad+C_{4}\frac{(k-1)\lceil\mathcal{C}(f)\rceil
B\kappa}{\phi\Lambda\sqrt{m-n}}\sqrt{\log\left({\textstyle\frac{l^{2}(\lceil\mathcal{C}(f)\rceil+1)^{2}\left(\left|\log\left({\textstyle\frac{\phi\Lambda}{40B}}\right)\right|+2\right)^{2}}{\delta}}\right)}$
$\displaystyle\quad+C_{5}\frac{(k-1)\lceil\mathcal{C}(f)\rceil
B}{\phi\Lambda\sqrt{l}}\left(\\!\sqrt{\log(l)(q+\log(p))}+\sqrt{\log\left({\textstyle\frac{(\lceil\mathcal{C}(f)\rceil+1)\left(\left|\log\left({\textstyle\frac{\phi\Lambda}{40B}}\right)\right|+2\right)}{\delta}}\right)}\
\right)\\!,$

where $C_{1},C_{2},C_{3},C_{4},C_{5}>0$ are appropriate constants.

If the features are sufficiently clustered during training, the
$E_{\phi\Lambda}$ terms vanish (or become very small) for $\phi$ sufficiently
small. Furthermore, when neural collapse happens, the class-mean distances are
typically of the same order (i.e., $\Lambda_{ij}\approx\Lambda$ for all $i\neq
j\in[l]$), and so the second term involving the $V_{f}$ terms becomes
$1/n^{2}$-times the CDNV, significantly improving the dependence on the bound
on the CDNV compared to Theorem 1. This comes at the price of multiplying the
rest of the terms with a $1/\phi>1$ factor.

A further improvement is possible if the distribution of the embeddings of the
training samples are spherically symmetric. In case they are, the CDNV term in
the bound can be multiplied with an additional factor $(1/p+1/n)$ (compared to
Theorem 1), again assuming that the class-mean distances are of the same order
(i.e., $\Lambda_{ij}\approx\Lambda$ for all $i\neq j\in[l]$). This can be a
substantial improvement when the number of samples $n$ from the target classes
is moderate, as the embedding dimension $p$ is typically much larger (at least
a few hundred in practical situations).

###### Theorem 3

Let $\delta\in(0,1)$, $l\geq 2$, $1\leq n\leq\sqrt{m}$ and let $\mathcal{F}$
be a class of ReLU neural networks of depth $q$. Furthermore, let
$\Lambda_{ij}:=\|\mu_{f}(\tilde{S}_{i})-\mu_{f}(\tilde{S}_{j})\|$ for
$i,j\in[l]$, $\Lambda:=\min_{i\neq j\in[l]}\Lambda_{ij}$ as before, and $s:=p$
if the set $\\{f\circ\tilde{S}_{c}\\}$ is spherically symmetric for all
$c\in[l]$ and $s:=1$ otherwise. Then, with probability at least $1-\delta$
over the selection of the source class-conditionals
$\tilde{\mathcal{P}}=\\{\tilde{P}_{c}\\}^{l}_{c=1}$ and the corresponding
source training data $\tilde{S}_{1}\dots,\tilde{S}_{l}$, for any
$f\in\mathcal{F}$, we have

$\displaystyle\mathcal{L}_{\mathcal{D}}(f)$ $\displaystyle\leq
C_{1}(k-1)\kappa\operatorname{Avg}_{i\neq
j\in[l]}\left[\left({\textstyle\frac{1}{s}}+{\textstyle\frac{\Lambda^{2}_{ij}}{n\Lambda^{2}}}+{\textstyle\frac{\Lambda^{2}}{n\Lambda^{2}_{ij}}}\right)\cdot
V_{f}(\tilde{S}_{i},\tilde{S}_{j})\right]+(k-1)\kappa\delta^{2}$
$\displaystyle\quad+C_{2}\frac{(k-1)\lceil\mathcal{C}(f)\rceil B\kappa
n^{2}}{\Lambda\sqrt{m-n}}\sqrt{(q+\log(p))\log(m)}$
$\displaystyle\quad+C_{3}\frac{(k-1)\lceil\mathcal{C}(f)\rceil
B\kappa}{\Lambda\sqrt{m-n}}\sqrt{\log\left({\textstyle\frac{l^{2}(\lceil\mathcal{C}(f)\rceil+1)^{2}\left(\left|\log\left({\textstyle\frac{\Lambda}{40B}}\right)\right|+2\right)^{2}}{\delta}}\right)}$
$\displaystyle\quad+C_{4}\frac{(k-1)\lceil\mathcal{C}(f)\rceil
B}{\Lambda\sqrt{l}}\left(\\!\sqrt{\log(l)(q+\log(p))}+\sqrt{\log\left({\textstyle\frac{(\lceil\mathcal{C}(f)\rceil+1)\left(\left|\log\left({\textstyle\frac{\Lambda}{40B}}\right)\right|+2\right)}{\delta}}\right)}\
\right)\\!,$

where $C_{1},C_{2},C_{3},C_{4}>0$ are appropriate constants.

Finally, although the bounds in the above theorems tend to zero as $m$ and $l$
tend to infinity and when class-features variability collapse happens during
training, similarly to standard generalization bounds in the deep learning
literature (e.g., Golowich et al., 2017; Bartlett et al., 2017; Neyshabur et
al., 2015; Li et al., 2018), these bounds may be quite loose in practical
situations. The aim of these results is to serve as a “proof of concept” that
few-shot learnability is possible by training a large model that exhibits
class-features variability collapse with respect to the training data when
trained on many source classes and many samples for each class.

##  5 Main Components of the Analysis

In this section we present the main ingredients of the proofs of our main
results, proving our main theorems in Section 5.4.

###  5.1 Generalization to New Classes

In this section we derive a generalization bound on the transfer error
$\mathcal{L}_{\mathcal{D}}(f)$ as a function of an average two-class soft-
margin error of the NCC classifier (based on $f$) over the training classes.
We start by reducing the problem to two-class classification: using the union
bound, we can easily show (see the proof of Lemma 4) that

$\mathcal{L}_{\mathcal{D}}(f)\leq(k-1)\cdot\mathbb{E}_{P_{1},P_{2}}\mathbb{E}_{S_{1},S_{2}}\mathbb{E}_{x_{1}\sim
P_{1}}\big{[}\mathbb{I}\left[\|f(x_{1})-\mu_{f}(S_{2})\|<\|f(x_{1})-\mu_{f}(S_{1})\|\right]\big{]}.$
(8)

$-\Delta$$r$$\mathbb{I}[r>-\Delta]$$\mathbb{I}[r>0]$$\ell_{\Delta}(r)$$1$
Figure 1: The soft-margin loss $\ell_{\Delta}$.

The interesting part of the analysis is to relate the expected two-class
classification error above, where the expectation is taken over the random
selection of the class-conditionals $P_{1}$ and $P_{2}$ of the target problem,
to a similar quantity which depends on the training classes only; in
particular, we aim to replace the expectation
$\mathbb{E}_{P_{1},,P_{2}}[\cdot]$ by
$\operatorname{Avg}_{\tilde{P}_{i}\neq\tilde{P}_{j}\in[l]}[\cdot]$, the
average over the pairs of the source classes. Notice that analyzing such an
average has two unusual components: First, we treat class-conditional
distributions as data points on which the feature map $f$ is trained. Second,
the average is not a standard linear statistics over the data points (i.e.,
class conditionals $\\{tP_{c}\\}_{c=1}^{l}$), since although we assume that
both the source and target class-conditionals, $\\{\tilde{P}_{c}\\}^{l}_{c=1}$
and $\\{P_{c}\\}^{k}_{c=1}$ are i.i.d. samples from $\mathcal{D}$, the
individual terms in the average depend on two distributions, and hence they
are interdependent. To be able to analyze their concentration properties, we
build on the work of Maurer and Pontil (2019), who considered the deviation of
nonlinear functions of independent random variables from their means. More
specifically, we apply their Corollary 3 to bound the deviation of the average
pairwise loss from its expectation. While the corollary generally applies to
any bounded loss functions, certain terms that arise from this bound can be
more easily quantified when the loss function is Lipschitz continuous.
Therefore, we replace the zero-one loss function $\mathbb{I}[r>0]$ with the
“soft-margin” loss function $\ell_{\Delta}:\mathbb{R}\to[0,\infty)$, defined
as follows:

$\ell_{\Delta}(r)~{}:=~{}\left\\{\begin{array}[]{lll}0&\mbox{if }r<-\Delta;\\\
1+\frac{r}{\Delta}&\mbox{if }r\in[-\Delta,0];\\\ 1&\mbox{if
}r>0.\end{array}\right.$ (9)

It is clear that for all $\Delta>0$ and $r\in\mathbb{R}$, we have
$\mathbb{I}[r>0]\leq\ell_{\Delta}(r)\leq\mathbb{I}[r>-\Delta]$ and
$\ell_{\Delta}$ is a ${\textstyle\frac{1}{\Delta}}$-Lipschitz continuous
function (see Figure 1). Thus, the expected pairwise error of few-shot trained
NCC classifiers $h_{f,S}^{\text{\tiny NCC}}$ for any two classes $P_{1},P_{2}$
can be bounded by the soft-margin error $\ell_{\Delta}(f;P_{1},P_{2})$ given
below: for a feature map $f:\mathbb{R}^{d}\to\mathbb{R}^{p}$ and two class-
conditional distributions $Q_{i},Q_{j}$, the _$n$ -shot_ (or, informally,
_few-shot_) _soft-margin NCC classification error_ of $f$ is defined as

$\ell_{\Delta}(f;Q_{i},Q_{j})~{}:=~{}\mathbb{E}_{\hat{S}_{i}\sim
Q^{n}_{i}}\mathbb{E}_{\hat{S}_{j}\sim Q^{n}_{j}}\mathbb{E}_{x_{i}\sim
Q_{i}}\left[\ell_{\Delta}(\|f(x_{i})-\mu_{f}(\hat{S}_{i})\|-\|f(x_{i})-\mu_{f}(\hat{S}_{j})\|)\right].$

This quantity measures the expected soft-margin test error of the NCC
classifier when using $n$ samples per-class to estimate the centers of $f$
over $Q_{i}$ and $Q_{j}$. The next result, proved in Appendix A, is obtained
by bounding $\mathbb{E}_{P_{1},P_{2}}[\ell_{\Delta}(f;P_{1},P_{2})]$ from the
right-hand side of (8) by $\operatorname{Avg}_{i\neq
j\in[l]}[\ell_{2\Delta}(f;\tilde{P}_{i},\tilde{P}_{j})$, the expected few-shot
soft-margin error of $f$ over the source classes, plus additional terms, which
depend on the complexity of $f$ and the number of classes (also note the
technical change of the margin from $\Delta$ to $2\Delta$):

###### Lemma 4

Let $\delta\in(0,1)$, $l\geq 2$, and let $\mathcal{F}$ be a class of ReLU
neural networks of depth $q$. With probability at least $1-\delta$ over the
selection of i.i.d. class-conditional distributions
$\tilde{\mathcal{P}}=\\{\tilde{P}_{c}\\}^{l}_{c=1}\sim\mathcal{D}^{l}$, for
any $f\in\mathcal{F}$ and $\Delta>0$, it holds that

$\displaystyle\mathcal{L}_{\mathcal{D}}(f)~{}$
$\displaystyle\leq~{}(k-1)\left(\operatorname{Avg}_{i\neq
j\in[l]}[\ell_{2\Delta}(f;\tilde{P}_{i},\tilde{P}_{j})]+\delta^{2}\right)$
$\displaystyle\quad\quad+(k-1)\frac{\lceil\mathcal{C}(f)\rceil
B}{\Delta\sqrt{l}}\Bigg{(}355\sqrt{\log(l)(q\log(2)+\log(p))}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad+16.5\sqrt{\log\left({\textstyle\frac{\sqrt{3}(\lceil\mathcal{C}(f)\rceil+1)(|\log(\Delta/B)|+2)}{\delta}}\right)}\Bigg{)}.$

The bound above can be broken down into several parts. The first term is the
average few-shot soft-margin error of $f$ between the source classes
$\tilde{P}_{1},\dots,\tilde{P}_{l}$. Specifically, for each pair of source
classes $(i,j)$, we measure the soft-margin _test_ error (over samples
$x_{i}\sim\tilde{P}_{i}$) of NCC classifiers $h_{f,\hat{S}}^{\text{\tiny
NCC}}$ produced using two random datasets $\hat{S}_{i}\sim\tilde{P}^{n}_{i}$
and $\hat{S}_{j}\sim\tilde{P}^{n}_{j}$ of size $n$. The second term,
$\delta^{2}$, depends on a free parameter (the probability of error) that can
be selected to be very small, as the only other term (the last one) which
depends on $\delta$ scales as $\sqrt{\log(1/\delta)}$ with respect to this
parameter. The third term is proportional to the ratio between the complexity
of the selected function $f$ and the task, which is captured by
$\sqrt{\log(l)(q+\log(p))}kB\mathcal{C}(f)$, and $\Delta\sqrt{l}$. This means
that as the number of source classes $l$ increases, we can expect the
generalization to new classes to improve as long as $\Delta$ remains
unchanged.

###  5.2 Generalization to New Samples

In the previous lemma, we bounded the loss function
$\mathcal{L}_{\mathcal{D}}(f)$ using the average few-shot soft-margin error
between pairs of source classes, $\operatorname{Avg}_{i\neq
j\in[l]}[\ell_{2\Delta}(f;\tilde{P}_{i},\tilde{P}_{j})]$. Since during the
training of a neural network we do not have access to the true source class-
conditional distributions $\tilde{P}_{1},\dots,\tilde{P}_{l}$, we would like
to bound each term $\ell_{2\Delta}(f;\tilde{P}_{i},\tilde{P}_{j})$ using its
empirical counterpart $\ell_{4\Delta}(f;\tilde{S}_{i},\tilde{S}_{j})$. The
following lemma, proved in Appendix B using similar techniques as in the proof
of Lemma 4, provides such a bound.

###### Lemma 5

Let $\delta\in(0,1)$, $1\leq n\leq\sqrt{m}$, and let $\mathcal{F}$ be a class
of ReLU neural networks of depth $q$. Let $\tilde{P}_{i}$ and $\tilde{P}_{j}$
be two class-conditional distributions. With probability at least $1-\delta$,
for any $f\in\mathcal{F}$ and $\Delta>0$, the following holds when sampling
$\tilde{S}_{i}\sim\tilde{P}^{m}_{i}$ and $\tilde{S}_{j}\sim\tilde{P}^{m}_{j}$
independently:

$\displaystyle\ell_{\Delta}(f;\tilde{P}_{i},\tilde{P}_{j}){}$
$\displaystyle\leq~{}4\left(1+\frac{n}{m-n}\right)\cdot\ell_{2\Delta}(f;\tilde{S}_{i},\tilde{S}_{j})$
$\displaystyle\qquad+16\lceil\mathcal{C}(f)\rceil
B\frac{\sqrt{m}(2n+4)^{2}}{(m-n)\Delta}\sqrt{\pi(q\log(2)+\log(p))\log(2m)}$
$\displaystyle\qquad+32\lceil\mathcal{C}(f)\rceil
B\frac{\sqrt{m}}{(m-n)\Delta}\sqrt{2\log\left({\textstyle\frac{3(\lceil\mathcal{C}(f)\rceil+1)^{2}(|\log(\Delta/B)|+2)^{2}}{\delta}}\right)}.$

The first term in the above bound,
$\ell_{2\Delta}(f;\tilde{S}_{i},\tilde{S}_{j})$, is the few-shot soft-margin
error of $f$ between the empirical distributions of the samples
$\tilde{S}_{i}$ and $\tilde{S}_{j}$, respectively. This quantity measures the
empirical error (over $x_{i}\in\tilde{S}_{i}$) of the NCC classifier
$h_{f,\hat{S}}^{\text{\tiny NCC}}$ for random datasets $\hat{S}_{i}$ and
$\hat{S}_{j}$, each containing $n$ samples selected uniformly at random from
$\tilde{S}_{i}$ and $\tilde{S}_{j}$ (i.e., $\hat{S}_{i}\sim
U[\tilde{S}_{i}]^{n}$ and $\hat{S}_{j}\sim U[\tilde{S}_{j}]^{n}$). Note that
we are interested in the situation where $n\ll m$, that is, the coefficient of
the first term is very close to $1$ (alternatively, we can think of having a
leading coefficient $1$ and an extra error term
$\frac{n}{m-n}\ell_{2\Delta}(f;\tilde{S}_{i},\tilde{S}_{j})\leq\frac{n}{m-n}$).
The other terms in the bound are of order
$\tilde{\mathcal{O}}\left({\textstyle\frac{\mathcal{C}(f)B\sqrt{q}n^{2}}{\Delta\sqrt{m}}}\right)$,
which tends to zero as the number of samples per class $m$ increases, as long
as $n=o(m^{1/4})$.

###  5.3 Bounding the Few-Shot Soft-Margin Error

In the previous sections, we showed that the transfer error
$\mathcal{L}_{\mathcal{D}}(f)$ can be upper bounded using the average few-shot
soft-margin error between the source classes, denoted as
$\ell_{2\Delta}(f;\tilde{P}_{i},\tilde{P}_{j})$. We also demonstrated that
each of these terms can be bounded using their empirical counterparts,
$\ell_{4\Delta}(f;\tilde{S}_{i},\tilde{S}_{j})$. Informally,
$(\ell_{4\Delta}(f;\tilde{S}_{i},\tilde{S}_{j})+\ell_{4\Delta}(f;\tilde{S}_{j},\tilde{S}_{i}))$
measures the accuracy with which we can classify samples $\tilde{S}$ using a
random NCC classifier $h_{f,\hat{S}}^{\text{\tiny NCC}}$ based on $n$ samples
from each of the training sets $\tilde{S}_{i}$ and $\tilde{S}_{j}$. This
quantity can be thought of as measuring the degree to which the samples
$f(\tilde{S}_{i})=\\{f(x_{i}):x_{i}\in\tilde{S}_{i}\\}$ and
$f(\tilde{S}_{j})=\\{f(x_{j}):x_{j}\in\tilde{S}_{j}\\}$ are clustered in
space. Based on this intuition, we aim to upper bound each term
$\ell_{4\Delta}(f;\tilde{S}_{i},\tilde{S}_{j})$ using measures of neural
collapse. Specifically, next we derive generic upper bounds for
$\ell_{\Delta}(f;Q_{i},Q_{j})$ in terms of $V_{f}(Q_{i},Q_{j})$ and
$E_{\Delta}(f;Q_{i},Q_{j})$, where $Q_{i}$ and $Q_{j}$ represent arbitrary
class-conditional distributions (recall that $E_{\Delta}$ is defined in (6)).
All the proofs for this section are presented in Appendix C.

We start with a lemma that connects the few-shot soft-margin error to the CDNV
(this result is an extension of Proposition 5 in our preliminary work (Galanti
et al., 2022b)).

###### Lemma 6

Consider a pair of class-conditional distributions, $Q_{i}$ and $Q_{j}$, and a
feature map $f:\mathbb{R}^{d}\to\mathbb{R}^{p}$. Let $\mu_{c}=\mu_{f}(Q_{c})$,
where $c\in\\{i,j\\}$, and let $\Delta\leq 0.1\|\mu_{i}-\mu_{j}\|$. Then

$\displaystyle\ell_{\Delta}(f;Q_{i},Q_{j})\leq
12\left({\textstyle\frac{1}{n}}+1\right)\cdot
V_{f}(Q_{i},Q_{j})+{\textstyle\frac{100}{n}}\cdot\big{(}V_{f}(Q_{i},Q_{j})+V_{f}(Q_{j},Q_{i})\big{)}.$

Furthermore, if $\\{f\circ Q_{i},f\circ Q_{j}\\}$ are spherically symmetric,
for $\Delta\leq 0.1\cdot\|\mu_{i}-\mu_{j}\|/p$, we have

$\displaystyle\ell_{\Delta}(f;Q_{i},Q_{j})\leq
128\left({\textstyle\frac{1}{n}}+{\textstyle\frac{1}{p}}\right)\cdot
V_{f}(Q_{i},Q_{j})+{\textstyle\frac{100}{n}}\cdot\big{(}V_{f}(Q_{i},Q_{j})+V_{f}(Q_{j},Q_{i})\big{)}.$

Informally, the expected soft-margin error $\ell_{\Delta}(f;Q_{i},Q_{j})$ of
$f$ is upper bounded by $\mathcal{O}((1+{\textstyle\frac{1}{n}})\cdot
V_{f}(Q_{i},Q_{j}))$, and when $f\circ Q_{i}$ and $f\circ Q_{j}$ are
spherically symmetric and $\Delta$ is also of order $1/p$, it can be bounded
by the smaller quantity
$\mathcal{O}(({\textstyle\frac{1}{p}}+{\textstyle\frac{1}{n}})\cdot
V_{f}(Q_{i},Q_{j}))$. Therefore, in case of neural collapse (i.e., when
$\operatorname{Avg}_{i\neq j}[V_{f}(\tilde{S}_{i},\tilde{S}_{j})]$ is small),
we expect the term $\operatorname{Avg}_{i\neq
j}[\ell_{\Delta}(f;\tilde{S}_{i},\tilde{S}_{j})]$ to be small.

There are two potential problems with the above lemma. In the first part, the
soft-margin loss scales with $V_{f}(Q_{i},Q_{j}))$, and so the number of
samples $n$ has limited effect. While the second part tries to address this,
improving the scaling to $(1/n+1/p)V_{f}(Q_{i},Q_{j}))$ (note that typically
$p$ is larger than $n$), this comes with the cost that
$\Delta=\mathcal{O}(\|\mu_{i}-\mu_{j}\|/p$. Substituting such a $\Delta$ into
Lemma 4, the second term would become
$\mathcal{O}({\textstyle\frac{1}{\Delta\sqrt{l}}})=\mathcal{O}(\sqrt{{\textstyle\frac{p}{l}}})=\Omega(1)$,
since neural collapse typically requires $p\geq l$ to allow representation of
$l$ (approximately) orthogonal class mean feature vectors. We address these
issues in the next lemma.

###### Lemma 7

Consider a pair of class-conditional distributions, $Q_{i}$ and $Q_{j}$, and a
feature map $f:\mathbb{R}^{d}\to\mathbb{R}^{p}$. Let $\Delta>0$ and
$\mu_{c}=\mu_{f}(Q_{c})$. Then

$\displaystyle\ell_{\Delta}(f;Q_{i},Q_{j})~{}$
$\displaystyle\leq~{}E_{2\Delta}(f;Q_{i},Q_{j})+{\textstyle\frac{4\|\mu_{i}-\mu_{j}\|^{2}}{n^{2}\Delta^{2}}}\cdot\big{(}V_{f}(Q_{i},Q_{j})+V_{f}(Q_{j},Q_{i})\big{)}.$

Furthermore, let $s=p$ if $\\{f\circ Q_{i},f\circ Q_{j}\\}$ are spherically
symmetric and $s=1$ otherwise. Then, if
$\Delta\leq{\textstyle\frac{1}{4}}\|\mu_{i}-\mu_{j}\|$, we have

$\displaystyle\ell_{\Delta}(f;Q_{i},Q_{j})~{}$
$\displaystyle\leq~{}64\left({\textstyle\frac{1}{s}}+{\textstyle\frac{\Delta^{2}}{\|\mu_{i}-\mu_{j}\|^{2}}}\right)\cdot
V_{f}(Q_{i},Q_{j})+{\textstyle\frac{4\|\mu_{i}-\mu_{j}\|^{2}}{n^{2}\Delta^{2}}}\cdot\big{(}V_{f}(Q_{i},Q_{j})+V_{f}(Q_{j},Q_{i})\big{)}.$

The first part of the lemma shows that the few-shot soft-margin error
$\ell_{\Delta}(f;Q_{i},Q_{j})$ can be bounded using the margin error of the
NCC classifier, $E_{2\Delta}(f;Q_{i},Q_{j})$, together with the term
$\frac{4\|\mu_{i}-\mu_{j}\|^{2}}{n^{2}\Delta^{2}}(V_{f}(Q_{i},Q_{j})+V_{f}(Q_{j},Q_{i}))$.
The main advantage of this bound is its weaker dependence on
$V_{f}(Q_{i},Q_{j})$ in the general case (not spherically symmetric embedding
distributions, i.e., $s=1$). The quantity $E_{2\Delta}(f;Q_{i},Q_{j})$
measures the $2\Delta$-margin error of the NCC classifier with means
$\mu_{f}(Q_{i})$ and $\mu_{f}(Q_{j})$ in the feature space given by $f$, which
is a much weaker notion of separation than the normalized variance
$V_{f}(Q_{i},Q_{j})$. Specifically, $E_{2\Delta}(f;Q_{i},Q_{j})$ can be zero
with $\Delta=\mathcal{O}(\|\mu_{i}-\mu_{j}\|)$ even when
$V_{f}(Q_{i},Q_{j})>0$. For example, if the embeddings $f(x)$ of samples from
the two classes $Q_{i}$ and $Q_{j}$, respectively, are uniformly distributed
over $0.5R$-radius circles around the points $\mu_{i}=(-R,0)$ and
$\mu_{j}=(R,0)$ in $\mathbb{R}^{2}$, then they are perfectly NCC separable
with margin $\Delta=R$ while the CDNV between the two distributions is a
positive constant (independent of $R$). In particular, even though
$E_{2\Delta}(f;Q_{i},Q_{j})=0$ for any $\Delta\leq 0.5R$, we have
$V_{f}(Q_{i},Q_{j})>0$. In this case, choosing
$\Delta=\Theta(\|\mu_{i}-\mu_{j}\|)$, the upper bound becomes
$\mathcal{O}(\frac{1}{n^{2}}(V_{f}(Q_{i},Q_{j})+V_{f}(Q_{j},Q_{i})))$, in
contrast to the previous bound that does not vanish as $n\to\infty$.

The second part of the lemma follows by bounding $E_{2\Delta}(f;Q_{i},Q_{j})$
using $V_{f}(Q_{i},Q_{j})$ in the following manner:
$E_{2\Delta}(f;Q_{i},Q_{j})\leq
64\left(\frac{1}{s}+\frac{\Delta^{2}}{\|\mu_{i}-\mu_{j}\|^{2}}\right)\cdot
V_{f}(Q_{i},Q_{j})$. Choosing $\Delta=\mathcal{O}(\|\mu_{i}-\mu_{j}\|/n)$, we
obtain a similar $\mathcal{O}\left((\frac{1}{s}+\frac{1}{n})\cdot
V_{f}(Q_{i},Q_{j})\right)$ bound as in the second part of Lemma 6, but here
$\Delta$ needs to scale with only $1/n$, not $1/p$ as in the previous lemma,
allowing a meaningful combination with Lemma 4.

Next, we derive a much better bound, which is exponentially small in
$\frac{p}{V_{f}(Q_{i},Q_{j})}$ if $f\circ Q_{c}$ are assumed to be centered
Gaussian distributions, as also assumed by Papyan et al. (2020).

###### Lemma 8

Consider a pair of class-conditional distributions, $Q_{i}$ and $Q_{j}$, and a
feature map $f:\mathbb{R}^{d}\to\mathbb{R}^{p}$. Let
$\Delta\in(0,\|\mu_{i}-\mu_{j}\|)$ with $\mu_{c}=\mu_{f}(Q_{c})$ for $c=1,2$.
Assume that $f\circ Q_{c}$ are spherical Gaussian distributions with means
$\mu_{c}$ such that
$V^{ij}_{f}:=\frac{\mathrm{Var}_{f}(Q_{i})}{(\|\mu_{i}-\mu_{j}\|-\Delta)^{2}}\leq
1/16$. Then we have
$\ell_{\Delta}(f;Q_{i},Q_{j})\leq\frac{3\exp\left(-p/(32V^{ij}_{f})\right)}{(\textnormal{e}\cdot
V^{ij}_{f})^{p/2}}$.

The above lemma provides an upper bound for $\ell_{\Delta}(f;Q_{i},Q_{j})$
using a term that exponentially decays with $1/V^{ij}_{f}$. While this bound
rapidly decays with the degree of neural collapse, it cannot be immediately
applied to upper bound $\ell_{\Delta}(f;\tilde{S}_{i},\tilde{S}_{j})$ since
$f(x_{i})$ and $f(x_{j})$ cannot be normally distributed for $x_{i}\sim
U[\tilde{S}_{i}]$ and $x_{j}\sim U[\tilde{S}_{j}]$. However, we can instead
apply this bound for $\ell_{\Delta}(f;\tilde{P}_{i},\tilde{P}_{j})$ when
$f\circ\tilde{P}_{i}$ and $f\circ\tilde{P}_{j}$ are spherical Gaussian
distributions and obtain a bound
$\ell_{\Delta}(f;\tilde{P}_{i},\tilde{P}_{j})\leq\frac{3\exp\left(-p/(32V^{ij}_{f})\right)}{(\textnormal{e}\cdot
V^{ij}_{f})^{p/2}}$. In addition, we can use standard concentration
inequalities (a variation of Lemma 1 in our earlier work, Galanti et al.,
2022b) to upper bound
$V^{ij}_{f}=\frac{\mathrm{Var}_{f}(\tilde{P}_{i})}{(\|\mu_{i}-\mu_{j}\|-\Delta)^{2}}$
using its empirical counterpart
$\hat{V}^{ij}_{f}:=\frac{\mathrm{Var}_{f}(\tilde{S}_{i})}{(\|\mu_{f}(\tilde{S}_{i})-\mu_{f}(\tilde{S}_{j})\|-\Delta)^{2}}$.
This would give a bound on $\ell_{\Delta}(f;\tilde{P}_{i},\tilde{P}_{j})$ in
terms of $\hat{V}^{ij}_{f}$.

###  5.4 Proofs of Theorems 1–3

Given the above lemmas, we are ready to prove our main theorems. We start with
proving Theorem 1. Applying Lemma 4 with $\delta/2$ in place of $\delta$ and
Lemma 5 for all pairs $i\neq j\in[l]$, with
${\textstyle\frac{\delta}{2l(l-1)}}$ in place of $\delta$, the union bound
implies that with probability at least $1-\delta$ over the selection of
$\tilde{S}_{1},\dots,\tilde{S}_{l}$, for all $f\in\mathcal{F}$ and $\Delta>0$,
we have

$\displaystyle\mathcal{L}_{\mathcal{D}}(f){}$
$\displaystyle\leq~{}4(k-1)\left(1+\frac{n}{m-n}\right)\left(\operatorname{Avg}_{i\neq
j\in[l]}[\ell_{4\Delta}(f;\tilde{S}_{i},\tilde{S}_{j})]+{\textstyle\frac{\delta^{2}}{4}}\right)$
(10) $\displaystyle\qquad+8(k-1)\lceil\mathcal{C}(f)\rceil
B\frac{\sqrt{m}(2n+4)^{2}}{(m-n)\Delta}\sqrt{\pi(q\log(2)+\log(p))\log(2m)}$
$\displaystyle\qquad+16(k-1)\lceil\mathcal{C}(f)\rceil
B\frac{\sqrt{m}}{(m-n)\Delta}\sqrt{2\log\left({\textstyle\frac{6l^{2}(\lceil\mathcal{C}(f)\rceil+1)^{2}(|\log(\Delta/B)|+2)^{2}}{\delta}}\right)}$
$\displaystyle\qquad+\frac{(k-1)\lceil\mathcal{C}(f)\rceil
B}{\Delta\sqrt{l}}\Bigg{(}355\sqrt{\log(l)(q\log(2)+\log(p))}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad+16.5\sqrt{\log\left({\textstyle\frac{2\sqrt{3}(\lceil\mathcal{C}(f)\rceil+1)(|\log(\Delta/B)|+2)}{\delta}}\right)}\Bigg{)}.$

Choosing $\Delta:=0.025\min_{i\neq
j\in[l]}\|\mu_{f}(\tilde{S}_{i})-\mu_{f}(\tilde{S}_{j})\|=0.025\Lambda$, the
first part of Lemma 6 implies

$\operatorname{Avg}_{i\neq
j\in[l]}[\ell_{4\Delta}(f;\tilde{S}_{i},\tilde{S}_{j})]\leq(12+{\textstyle\frac{212}{n}})\cdot\operatorname{Avg}_{i\neq
j\in[l]}[V_{f}(\tilde{S}_{i},\tilde{S}_{j})].$ (11)

Combining with (10) gives the desired bound

$\displaystyle\mathcal{L}_{\mathcal{D}}(f){}$
$\displaystyle\leq~{}(k-1)\left(1+\frac{n}{m-n}\right)\left(48+\frac{848}{n}\right)\operatorname{Avg}_{i\neq
j\in[l]}[V_{f}(\tilde{S}_{i},\tilde{S}_{j})]+\frac{(k-1)m\delta^{2}}{m-n}$
(12) $\displaystyle\qquad+320(k-1)\lceil\mathcal{C}(f)\rceil
B\frac{\sqrt{m}(2n+4)^{2}}{(m-n)\Lambda}\sqrt{\pi(q\log(2)+\log(p))\log(2m)}$
$\displaystyle\qquad+640(k-1)\lceil\mathcal{C}(f)\rceil
B\frac{\sqrt{m}}{(m-n)\Lambda}\sqrt{2\log\left({\textstyle\frac{6l^{2}(\lceil\mathcal{C}(f)\rceil+1)^{2}(|\log({\textstyle\frac{\Lambda}{40B}})|+2)^{2}}{\delta}}\right)}$
$\displaystyle\qquad+\frac{(k-1)\lceil\mathcal{C}(f)\rceil
B}{\Lambda\sqrt{l}}\Bigg{(}14200\sqrt{\log(l)(q\log(2)+\log(p))}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad+660\sqrt{\log\left({\textstyle\frac{2\sqrt{3}(\lceil\mathcal{C}(f)\rceil+1)(|\log({\textstyle\frac{\Lambda}{40B}})|+2)}{\delta}}\right)}\Bigg{)},$

which proves Theorem 1. The proofs of Theorem 2 and Theorem 3 follow the same
lines, but instead of (11), we use the first part of Lemma 7 with
$\Delta=\phi\Lambda/8$ for Theorem 2 and the second part of the same lemma
with $\Delta=\Lambda/\sqrt{n}$ for Theorem 3.

##  6 Experiments

In this section, we conduct experiments to study the neural collapse
phenomenon and how it generalizes to new data points and new classes. We
observe neural collapse not only during training, as previously reported by
Papyan et al. (2020), but also on test data from the same classes and on data
from new classes (this generalization of the neural collapse phenomenon to new
data was formally proved in Lemma 1 of our previous work, Galanti et al.,
2022b). Our results show that neural collapse is strongly correlated with
accuracy in few-shot learning scenarios. Our experiments are conducted on
multiple datasets and using multiple standard architectures, providing strong
empirical evidence that neural collapse provides a compelling explanation for
the performance of foundation models in few-shot learning tasks. The
experimental results are reported as the average over 20 random
initializations, with 95% confidence intervals.

###  6.1 Setup

#### Method.

In this study, we train a neural network classifier $\tilde{h}=\tilde{g}\circ
f$ on a source task using stochastic gradient descent (SGD) with momentum
(see, e.g., Sutskever et al., 2013; Yan et al., 2018), with a learning rate of
$\eta$ (specified in each experiment), a momentum of 0.9, and a batch size of
64. The mapping implemented by all layers of the neural network except for the
top linear layer $\tilde{g}$ is referred to as $f$.

To evaluate the few-shot performance of $f$ on target classification tasks, we
train a new classifier $g$ on top of $f$ by minimizing the cross-entropy loss
between its logits and the one-hot encodings of the labels. Formally, given a
target few-shot classification task with training data
$S=\cup^{k}_{c=1}\\{x_{ci}\\}_{i=1}^{n}$, we train a new top linear layer $g$
by solving a ridge regression problem on the dataset
$\cup^{k}_{c=1}\\{(f(x_{ci})\\}^{n}_{i=1}$ with regularization
$\lambda_{n}=\alpha\sqrt{kn}$. This results in the weight matrix
$w_{f,S}=(f(X)^{\top}f(X)+\lambda_{n}I)^{-1}f(X)^{\top}Y$, where
$f(X)=(f(x_{ci}))_{c,i}\in\mathbb{R}^{nc\times d}$ is the data matrix
containing the feature vectors, $Y\in\mathbb{R}^{nc\times k}$ is the label
matrix, and $X\in\mathbb{R}^{nc\times d}$ is the data matrix. We did not apply
any fine-tuning to $f$ during this process.

To measure the performance of the model $f$, we randomly sample 5-class
classification tasks (i.e., $k=5$) from the target dataset, with $n=1$ or
$n=5$ training samples for each class, and evaluate the accuracy on 100 random
test samples from each class. We report the resulting accuracy rates averaged
over 100 randomly chosen tasks.

#### Architectures and hyperparameters.

We experimented with two types of architectures for $\tilde{h}$: wide ResNets
(Zagoruyko and Komodakis, 2016) and vanilla convolutional networks. The wide
ResNets consist of a convolutional layer with $3\times 3$ kernels and 16
output channels, followed by three groups of layers. Each group includes a
convolutional layer followed by a series of $N$ residual layers. Each residual
layer in the $i$th group contains two convolutional layers with $3\times 3$
kernels and $2^{i+3}M$ output channels. Each convolutional layer is followed
by a ReLU activation and batch normalization. The penultimate layer of the
network is a mean pooling activation with $4\times 4$ kernels, producing an
output of size 256, followed by a linear layer. The vanilla convolutional
networks have the same structure as the wide ResNets, but do not include the
residual connections. These networks are denoted as WRN-$N$-$M$ and
Conv-$N$-$M$, respectively.

#### Datasets.

We evaluate our approach using four datasets: (i) Mini-ImageNet (Vinyals et
al., 2016), (ii) CIFAR-FS (Bertinetto et al., 2019), (iii) FC-100 (Oreshkin et
al., 2018), (iv) and EMNIST (balanced) (Cohen et al., 2017). Each dataset is
divided into three sets: meta-train, meta-validation, and meta-test. The meta-
training and meta-test sets are used for training and evaluating our models,
respectively. The meta-validation set is not used. The Mini-ImageNet dataset
consists of 100 randomly selected classes from ImageNet ILSVRC-2012
(Russakovsky et al., 2015), with 600 images of size 84 x 84 pixels per class.
It is divided into 64 meta-train classes, 16 meta-validation classes, and 20
meta-test classes. CIFAR-FS and FC-100 are both derived from the CIFAR-100
dataset (Krizhevsky, 2012). CIFAR-FS consists of a random split of the
CIFAR-100 classes into 64 meta-train classes, 14 meta-validation classes, and
20 meta-test classes. FC-100 contains 100 classes grouped into 20
superclasses. These classes are divided into 60 meta-train classes from 12
superclasses, 20 meta-validation classes from 4 superclasses, and 20 meta-test
classes from 4 superclasses. The EMNIST dataset is an extension of the
original MNIST dataset. We randomly split its classes into 35 meta-train
classes and 12 meta-test classes (which are: 2, 10, 11, 12, 13, 16, 18, 22,
25, 33, 34, 44). We apply random cropping augmentations during training for
all experiments.

###  6.2 Results

Method | Architecture | Mini-ImageNet | CIFAR-FS | FC-100
---|---|---|---|---
|  | 1-shot | 5-shot | 1-shot | 5-shot | 1-shot | 5-shot
Matching Networks (Vinyals et al., 2016) | 64-64-64-64 | $43.56\pm 0.84$ | $55.31\pm 0.73$ | - | - | - | -
LSTM Meta-Learner (Ravi and Larochelle, 2017) | 64-64-64-64 | $43.44\pm 0.77$ | $60.60\pm 0.71$ | - | - | - | -
MAML (Finn et al., 2017) | 32-32-32-32 | $48.70\pm 1.84$ | $63.11\pm 0.92$ | $58.9\pm 1.9$ | $71.5\pm 1.0$ | - | -
Prototypical Networks (Snell et al., 2017) | 64-64-64-64 | $49.42\pm 0.78^{\dagger}$ | $68.20\pm 0.66^{\dagger}$ | $55.5\pm 0.7$ | $72.0\pm 0.6$ | $35.3\pm 0.6$ | $48.6\pm 0.6$
Relation Networks (Sung et al., 2018) | 64-96-128-256 | $50.44\pm 0.82$ | $65.32\pm 0.7$ | $55.0\pm 1.0$ | $69.3\pm 0.8$ | - | -
SNAIL (Mishra et al., 2018) | ResNet-12 | $55.71\pm 0.99$ | $68.88\pm 0.92$ | - | - | - | -
TADAM (Oreshkin et al., 2018) | ResNet-12 | $58.50\pm 0.30$ | $76.7\pm 0.3$ | - | - | $40.1\pm 0.4$ | $56.1\pm 0.4$
AdaResNet (Munkhdalai et al., 2018) | ResNet-12 | $56.88\pm 0.62$ | $71.94\pm 0.57$ | - | - | - | -
Dynamics Few-Shot (Gidaris and Komodakis, 2018) | 64-64-128-128 | $56.20\pm 0.86$ | $73.0\pm 0.64$ | - | - | - | -
Activation to Parameter (Qiao et al., 2018) | WRN-28-10 | $59.60\pm 0.41^{\dagger}$ | $73.74\pm 0.19^{\dagger}$ | - | - | - | -
R2D2 (Bertinetto et al., 2019) | 96-192-384-512 | $51.2\pm 0.6$ | $68.8\pm 0.1$ | $65.3\pm 0.2$ | $79.4\pm 0.1$ | - | -
Shot-Free (Ravichandran et al., 2019) | ResNet-12 | $59.04\pm n/a$ | $77.64\pm n/a$ | $69.2\pm n/a$ | $84.7\pm n/a$ | - | -
TEWAM Qiao et al. (2019) | ResNet-12 | $60.07\pm n/a$ | $75.90\pm n/a$ | $70.4\pm n/a$ | $81.3\pm n/a$ | - | -
TPN (Liu et al., 2019) | ResNet-12 | $55.51\pm 0.86$ | $75.64\pm n/a$ | - | - | - | -
LEO (Rusu et al., 2019) | WRN-28-10 | $61.76\pm 0.08^{\dagger}$ | $77.59\pm 0.12^{\dagger}$ | - | - | - | -
MTL (Sun et al., 2019) | ResNet-12 | $61.20\pm 1.80$ | $75.50\pm 0.80$ | - | - | - | -
OptNet-RR (Lee et al., 2019) | ResNet-12 | $61.41\pm 0.61$ | $77.88\pm 0.46$ | $72.6\pm 0.7$ | $84.3\pm 0.5$ | $40.5\pm 0.6$ | $57.6\pm 0.9$
MetaOptNet (Lee et al., 2019) | ResNet-12 | $62.64\pm 0.61$ | $78.63\pm 0.46$ | $72.0\pm 0.7$ | $84.2\pm 0.5$ | $41.1\pm 0.6$ | $55.3\pm 0.6$
Transductive Fine-Tuning (Dhillon et al., 2020) | WRN-28-10 | $65.73\pm 0.68$ | $78.40\pm 0.52$ | $76.58\pm 0.68$ | $85.79\pm 0.5$ | $43.16\pm 0.59$ | $57.57\pm 0.55$
Distill-simple (Tian et al., 2020) | ResNet-12 | $62.02\pm 0.63$ | $79.64\pm 0.44$ | $71.5\pm 0.8$ | $86.0\pm 0.5$ | $42.6\pm 0.7$ | $59.1\pm 0.6$
Distill (Tian et al., 2020) | ResNet-12 | $64.82\pm 0.60$ | $82.14\pm 0.43$ | $73.9\pm 0.8$ | $86.9\pm 0.5$ | $44.6\pm 0.7$ | $60.9\pm 0.6$
Ours (simple) | WRN-28-4 | $58.12\pm 1.19$ | $72.0\pm 0.99$ | $68.81\pm 1.20$ | $81.49\pm 0.98$ | $44.96\pm 1.14$ | $57.21\pm 10.89$
Ours (lr scheduling) | WRN-28-4 | $60.37\pm 1.25$ | $72.35\pm 0.99$ | $70.0\pm 1.29$ | $81.39\pm 0.96$ | $43.42\pm 1.0$ | $54.14\pm 1.1$
Ours (lr scheduling + model selection) | WRN-28-4 | $61.27\pm 1.14$ | $74.74\pm 0.76$ | $72.37\pm 1.12$ | $82.94\pm 0.89$ | $45.81\pm 1.27$ | $56.85\pm 1.30$

Table 1: Comparison to prior work on Mini-ImageNet, CIFAR-FS, and FC-100 on 1-shot and 5-shot 5-class classification. Reported numbers are test target classification accuracy of various methods for various data sets. The notation a-b-c-d denotes a 4-layer convolutional network with a, b, c, and d filters in each layer. †The algorithm was trained on both training and validation classes. We took the data from Dhillon et al. (2020) and Tian et al. (2020). |  |  |
---|---|---|---
WRN-28-4 on CIFAR-FS
|  |  |
Conv-28-4 on CIFAR-FS
|  |  |
WRN-28-4 on Mini-ImageNet
|  |  |
Conv-16-2 on EMNIST
(a) training CDNV | (b) test CDNV | (c) target CDNV | (d) target accuracy
Figure 2: Class-features variability collapse. (a) CDNV on the source training
data; (b) CDNV over the source test data; (c) CDNV over the target classes,
all plotted in log-log scale. (d) Target accuracy rate (lin-log scale). In
each experiment we trained the model on a different number of source classes
$l\in\\{5,10,20,30,40,50,60\\}$ (as indicated in the legend).

#### Few-shot performance of transfer learning.

While the use of ridge regression to train the few-shot classifier $g$ may
seem simple, it has been shown to provide reasonable performance and is
therefore suitable for evaluating the effectiveness of recent
transfer/transductive learning methods for few-shot learning (Dhillon et al.,
2020; Tian et al., 2020). To demonstrate this, we compared the 1- and 5-shot
performance of our approach to several other few-shot learning algorithms on
the Mini-ImageNet, CIFAR-FS, and FC-100 datasets, as summarized in Table 1.
For each dataset, we report the average performance of our method on epochs 90
to 100. As shown in the table, our method performs competitively with other
approaches on the three benchmarks, particularly in the 1-shot case (achieving
state-of-the-art performance on FC-100). Note that the inferior performance of
our method compared to Distill-simple (Tian et al., 2020) is likely due to the
choice of the final few-shot classifier: our ridge regression classifier is
not as effective as their logistic regression solution (as shown in Table 1),
but is superior to their nearest neighbor classifier (see Table5 in their
paper).

To improve the performance of our method slightly, we employed a standard
learning rate scheduling with an initial learning rate of $\eta=0.05$, which
is decayed twice by a factor of 0.1 after 30 epochs each (accuracy rates are
reported as the average over epochs 90 to 100, as before). Since the
performance of these networks plateaued slightly after the first learning rate
decay on the source test data, we also applied model selection based on this
information and used the network from the first 60 epochs (to avoid
overfitting to the source data and classes at the smallest learning rate) with
the best source test performance. This combination of variations typically
resulted in a small improvement of a few percentage points on the problems
considered, as shown in the last line of Table 1.

#### Neural collapse and few-shot learnability.

In our main experiment, we test the theoretical conclusions we made in Section
4. We argued that in the presence of neural collapse on the training classes,
the trained feature map can be used to train a classifier with a small number
of samples on new, unseen classes. In this section, we demonstrate that neural
collapse generalizes to a certain degree to new samples from the same classes
and also to new classes, and we show that it is correlated with good few-shot
performance.

To validate these conclusions, we trained classifiers $\tilde{h}$ with a
varying number of $l$ randomly selected source classes. For each run, we plot
the CDNV as a function of epoch for the training and test datasets of the
source classes and the test samples of the target classes in Figure 2. In
addition, we plot the 5-shot accuracy of ridge regression using the learned
feature map $f$. Similar experiments with different numbers of target samples
are shown in Figures 4 and 5.

As shown in Figure 2, the CDNV decreases over the course of training on both
training and test datasets of the source classes, showing that neural collapse
generalizes to new samples from the training classes. Since the classification
tasks with fewer source classes are easier to learn, the CDNV tends to be
larger when training with a wider set of source classes. In contrast, we
observe that when increasing the number of source classes, the presence of
neural collapse in the target classes strengthens. This is in alignment with
our theoretical observations (the more “training” classes, the better
generalization to new classes), and the few-shot performance also consistently
improves when the overall number of source classes is increased. Note that in
practice the CDNV does not decrease to zero (due to the limited sample sizes),
and plateaus at a value above 1 on the target classes since we use a
relatively small number of source classes (at most 60). To validate the
generality of our results, this phenomenon is demonstrated in several
settings, e.g., using different network architectures and datasets in Figure
2. As can be seen, the values of the CDNV on the target classes are relatively
large compared to those on the source classes, except for the results on
EMNIST. However, these values still indicate a reasonable few-shot learning
performance, as demonstrated in the experiments. These results consistently
validate our theoretical findings, that is, that neural collapse generalizes
to new source samples, it emerges for new classes, and its presence
immediately facilitates good performance in few-shot learning.

###  6.3 Dynamics of the Class-Embedding Distances

|  |  |
---|---|---|---
(a) Source classes, train data
|  |  |
(b) Source classes, test data
|  |  |
(c) Target classes, test data
Figure 3: Dynamics of minimal class-means distance. In (a) we plot
$\min_{i\neq j}\|\mu_{f}(\tilde{S}_{i})-\mu_{f}(\tilde{S}_{j})\|$, in (b) we
plot $\min_{i\neq j}\|\mu_{f}(\tilde{P}_{i})-\mu_{f}(\tilde{P}_{j})\|$ and in
(c) we plot $\min_{i\neq j}\|\mu_{f}(P_{i})-\mu_{f}(P_{j})\|$ as a function of
the number of training iterations. In each experiment we trained a WRN-28-4
using SGD on a set of $l\in\\{5,10,20,30,40,50,60\\}$ source classes on CIFAR-
FS (as indicated in the legend). The $i$’th column corresponds to the results
of training with SGD with $\eta=2^{-2i-2}$.

Recall that Theorem 1 scales with
$\Lambda^{-1}=\mathcal{O}({\textstyle\frac{1}{\min_{i\neq
j\in[l]}\|\mu_{f}(\tilde{S}_{i})-\mu_{f}(\tilde{S}_{j})\|}})$. Therefore, we
empirically investigated the dynamics of $\min_{i\neq
j\in[l]}\|\mu_{f}(\tilde{S}_{i})-\mu_{f}(\tilde{S}_{j})\|$ during training in
our standard setting (WRN-28-4 with the default hyperparameters, see Section
2) on CIFAR-FS, considering a varying number source classes
($l\in\\{5,10,20,30,40,50,60\\}$) and learning rates
($\eta\in\\{2^{-2i-2}\\}^{4}_{i=1}$). As can be seen in Figure 3, the values
of $\min_{i\neq j\in[l]}\|\mu_{f}(\tilde{S}_{i})-\mu_{f}(\tilde{S}_{j})\|$
tend to increase during training and is tends to be larger when using a
smaller learning rate. For completeness, we also plotted the values of
$\min_{i\neq j\in[l]}\|\mu_{f}(\tilde{P}_{i})-\mu_{f}(\tilde{P}_{j})\|$ and
$\min_{i\neq j\in[k]}\|\mu_{f}(P_{i})-\mu_{f}(P_{j})\|$. Interestingly,
$\min_{i\neq j\in[k]}\|\mu_{f}(P_{i})-\mu_{f}(P_{j})\|$ tends to increase with
the number of source classes, indicating improved generalization to new
classes.

###  6.4 Varying the Number of Target Samples

|  |  |
---|---|---|---
(a) CDNV, train |  (b) CDNV, test |  (c) CDNV, target |
|  |  |
(d) 1-shot accuracy |  (e) 5-shot accuracy |  (f) 10-shot acc |  (g) 20-shot acc
CIFAR-FS
|  |  |
(a) CDNV, train |  (b) CDNV, test |  (c) CDNV, target |
|  |  |
(d) 1-shot acc |  (e) 5-shot acc |  (f) 10-shot acc |  (g) 20-shot acc
Mini-ImageNet
Figure 4:  Class-features variability collapse and few-shot performance with learning rate $\eta=2^{-4}$. We trained WRN-28-4 using SGD with learning rate scheduling on $l\in\\{5,10,20,30,40,50,64\\}$ source classes (as indicated in the legend). For each dataset, in (a-c) we plot the CDNV on the training and test data and the target classes (resp.). In (d-g) we plot the 1,5,10 and 20-shot accuracy rates (resp.).  |  |  |
---|---|---|---
(a) CDNV, train |  (b) CDNV, test |  (c) CDNV, target |
|  |  |
(d) 1-shot accuracy |  (e) 5-shot accuracy |  (f) 10-shot acc |  (g) 20-shot acc
CIFAR-FS
|  |  |
(a) CDNV, train |  (b) CDNV, test |  (c) CDNV, target |
|  |  |
(d) 1-shot acc |  (e) 5-shot acc |  (f) 10-shot acc |  (g) 20-shot acc
Mini-ImageNet
Figure 5:  Class-features variability collapse and few-shot performance with
learning rate scheduling. We trained WRN-28-4 using SGD with learning rate
scheduling on $l\in\\{5,10,20,30,40,50,64\\}$ source classes (as indicated in
the legend). For each dataset, in (a-c) we plot the CDNV on the training and
test data and the target classes (resp.). In (d-g) we plot the 1,5,10 and
20-shot accuracy rates (resp.).

To further demonstrate the relationship between neural collapse and
generalization to new classes, we conducted an experiment to examine the
effect of varying the number of target samples. In this experiment, we trained
WRN-28-4 using SGD and reported the CDNV on the source training data, the
source test data (i.e., unseen test samples from the source classes), and the
target classes (resp.). In Figure 4(d-g), we plotted the 1, 5, 10 and 20-shot
accuracy rates of the network during training time. We also experimented with
a learning rate scheduling, starting with learning rate $\eta=0.05$ and
decreasing it by a factor of 0.1 every 30 epochs twice. The results of this
experiment are provided in Figure 5.

Similarly to Figure 2, as expected, we observed that the few-shot performance
improved when the number of source classes increased, while the CDNV on the
target classes tended to decrease. Additionally, in line with our theory, the
CDNV on the target classes was negatively correlated with the few-shot
performance, meaning that better neural collapse resulted in better
performance. For example, in Figure 5(d-g), it is clear that the peak
performance on all few-shot experiments for the case of 64 source classes was
achieved around the minimal value of the CDNV on the target classes in Figure
5(c). This occurred around iteration 16,000 for CIFAR-FS and around iteration
20,000 for Mini-ImageNet, slightly after the first learning rate decay (at
15,000 and 18,000 steps, respectively). As shown, the performance slightly
decreased after the peak iteration, while the CDNV on the target classes
slightly increased, as the training started to overfit to the source data and
classes. This effect can be mitigated by selecting the final network based on
the performance on the source test data, as demonstrated in Table 1.

##  7 Conclusions

The use of pre-trained models for transfer learning is a successful approach
for addressing overfitting in the low-data regime, but the reasons for this
success are not clear. Recently, Galanti et al. (2022b) proposed a new
perspective on this problem using the concept of neural collapse. However,
their theoretical analysis was based on several unrealistic assumptions. In
this work, we provide a more comprehensive theoretical analysis by
significantly relaxing these assumptions. We study the transfer error of pre-
trained feature maps, which measures the expected error of random classifiers
trained on few samples using the feature maps for randomly generated
classification tasks. We derive a generalization bound on the transfer error
of a pre-trained feature map. This bound is decomposed into a measure of the
variability collapse between the training samples and additional terms that
scale as $\mathcal{O}(m^{-1/2}\textnormal{poly}(n))$ and
$\mathcal{O}(l^{-1/2})$, where $m$ is the number of training samples per
source class, $n$ is the number of samples per target class, and $l$ is the
number of source classes. We show that if neural collapse occurs when training
with many source classes and training samples per class, then it requires very
few samples to train a linear classifier on top of the learned feature
representation that accurately predicts the new classes. These results provide
a justification for the recent successes of transfer learning in few-shot
tasks, as observed by Tian et al. (2020) and Dhillon et al. (2020).

##  A Proof of Lemma 4

To prove Lemma 4, we apply Corollary 3 of Maurer and Pontil (2019), which
provides generalization bounds for settings where the total loss over a
dataset is a nonlinear function of the dataset (and not the usual average of
losses computed independently for every data point). We will apply this result
to the average pairwise error for distinguishing two classes (note that
although we will consider average loss functions, here the terms in the sum
are not independent as there is overlap among the classes used in each pair).
In order to do so, we use the following definitions (their Definition 1): Let
$\|\cdot\|$ be the Euclidean norm, $\mathcal{Z}\subset\mathbb{R}^{d}$ be any
set and $A:\mathcal{Z}^{l}\to\mathbb{R}$. For ${\bf z}=(z_{1},\dots,z_{l})$,
$j\in\\{1,\dots,l\\}$ and $z^{\prime}_{j}\in\mathcal{Z}$, we define the $j$-th
partial difference operator on $A$ as

$D^{j}_{z^{\prime}_{j}}A({\bf
z})~{}:=~{}A(z_{1},\dots,z_{j-1},z_{j},z_{j+1}\dots,z_{l})-A(z_{1},\dots,z_{j-1},z^{\prime}_{j},z_{j+1},\dots,z_{l}).$

In addition, we denote

$M(A)~{}:=~{}\max_{j\in[l]}\sup_{\begin{subarray}{c}{\bf
z}\in\mathcal{Z}^{l}\\\ z^{\prime}_{j}\in\mathcal{Z}:~{}z^{\prime}_{j}\neq
z_{j}\end{subarray}}\frac{D^{j}_{z^{\prime}_{j}}A({\bf
z})}{\|z_{j}-z^{\prime}_{j}\|},$

and

$J(A)~{}:=~{}l\cdot\max_{\begin{subarray}{c}r,j\in[l]\\\ r\neq
j\end{subarray}}\sup_{\begin{subarray}{c}{\bf z}\in\mathcal{Z}^{l}\\\
z^{\prime}_{j}\in\mathcal{Z}:~{}z^{\prime}_{j}\neq z_{j}\\\
z^{\prime}_{r}\in\mathcal{Z}:~{}z^{\prime}_{r}\neq
z_{r}\end{subarray}}\frac{D^{r}_{z^{\prime}_{r}}D^{j}_{z^{\prime}_{j}}A({\bf
z})}{\|z_{j}-z^{\prime}_{j}\|},$

and the maximal difference

$K(A)~{}:=~{}\max_{j\in[l]}\sup_{\begin{subarray}{c}{\bf
z}\in\mathcal{Z}^{l}\\\ z^{\prime}_{j}\in\mathcal{Z}:~{}z^{\prime}_{j}\neq
z_{j}\end{subarray}}D^{j}_{z^{\prime}_{j}}A({\bf z}).$

In addition, we need the notion of Rademacher complexity: the Rademacher
complexity of a set of vectors $Y\subset\mathbb{R}^{s}$ is defined as
$R(Y):=\mathbb{E}_{\epsilon}\sup_{y\in
Y}\left[\langle\epsilon,y\rangle\right]$, where
$\epsilon=(\epsilon_{1},\dots,\epsilon_{s})\sim U[\\{\pm 1\\}]^{s}$ (see,
e.g., Mohri et al., 2018).

Now assume that $W=(W_{1},\ldots,W_{l})$ is an i.i.d. random vector with each
$W_{i},i\in[l]$ taking values in a set $\mathcal{W}$, and let $\mathcal{H}$ be
a finite class of functions $H:\mathcal{W}\to\mathcal{Z}$. When $H$ is applied
to the vector $W$, it is applied coordinatewise, that is,
$H(W):=(H(W_{1}),\ldots,H(W_{l}))$, and we denote
$\mathcal{H}(W):=\\{H(W):H\in\mathcal{H}\\}$. For this setting, the following
generalization bound is proved in Corollary 3 of Maurer and Pontil
(2019):222The original statement makes use of Gaussian complexity instead of
Rademacher complexity. The Gaussian complexity of a set
$Z\subset\mathbb{R}^{l}$ is upper bounded by $2\sqrt{\log(l)}R(Z)$
(Wainwright, 2019, Exercise 5.5). for any $\delta^{\prime}\in(0,1)$, with
probability at least $1-\delta^{\prime}$ over the selection of $W$, for all
$H\in\mathcal{H}$ we have

$\displaystyle\mathbb{E}_{W}\left[A(H(W))\right]{}$
$\displaystyle\leq~{}A(H(W))+2\sqrt{2\pi\log(l)}\big{(}2M(A)+J(A)\big{)}\cdot\mathbb{E}_{W}[R(\mathcal{H}(W))]$
(13)
$\displaystyle\qquad+K(A)\cdot\sqrt{l\log\left({\textstyle\frac{1}{\delta^{\prime}}}\right)}.$

Importantly, the above inequality does not depend on the size of
$\mathcal{H}$, which is only required to be finite. Therefore, the inequality
can be easily extended to any infinite function class $\mathcal{H}$ that
admits a sequence of finite covers
$\mathcal{H}_{t}\subset\mathcal{H},t=1,2,\ldots$ such that for every
$H\in\mathcal{H}$ there exists a $H_{t}\in\mathcal{H}_{t}$ such that
$|H(w)-H_{t}(w)|\leq 1/t$ for any $w\in\mathcal{W}$. Applying (13) to
$\mathcal{H}_{t}$ and letting $t$ to infinity then implies that (13) also
holds for $\mathcal{H}$, since $R(\mathcal{H}_{t}(W))\leq R(\mathcal{H}(W))$
for any $W\in\mathcal{W}^{l}$ by definition. In the sequel, we use this
slightly extended version of Corollary 3 of Maurer and Pontil (2019).

Now we are ready to proceed with the proof of Lemma 4; we start with repeating
the statement for convenience.

See 4

Proof  We start the proof by reducing the error bound to a classification
problem between two classes: For any $f\in\mathcal{F}$,

$\displaystyle\mathcal{L}_{\mathcal{D}}(f)~{}$
$\displaystyle=~{}\mathbb{E}_{P_{1},\dots,P_{k}}\mathbb{E}_{S_{1},\dots,S_{k}}\mathbb{E}_{(x,y)\sim
P}\big{[}\mathbb{I}[h_{f,S}^{\text{\tiny NCC}}(x)\neq y]\big{]}$
$\displaystyle=~{}\mathbb{E}_{P_{1},\dots,P_{k}}\mathbb{E}_{S_{1},\dots,S_{k}}\mathbb{E}_{(x,y)\sim
P}\big{[}\mathbb{I}\left[\exists i\neq
y:~{}\|f(x)-\mu_{f}(S_{i})\|\leq\|f(x)-\mu_{f}(S_{y})\|\right]\big{]}$
$\displaystyle\leq~{}\mathbb{E}_{P_{1},\dots,P_{k}}\mathbb{E}_{S_{1},\dots,S_{k}}\mathbb{E}_{(x,y)\sim
P}\left[\sum_{i\neq
y}\mathbb{I}\left[\|f(x)-\mu_{f}(S_{i})\|\leq\|f(x)-\mu_{f}(S_{y})\|\right]\right]$
$\displaystyle=~{}\mathbb{E}_{P_{1},\dots,P_{k}}\mathbb{E}_{S_{1},\dots,S_{k}}\mathbb{E}_{y\sim
U[\\{1,\ldots,k\\}]}\mathbb{E}_{x\sim P_{y}}\left[\sum_{i\neq
y}\mathbb{I}\left[\|f(x)-\mu_{f}(S_{i})\|<\|f(x)-\mu_{f}(S_{y})\|\right]\right]$
$\displaystyle=~{}\mathbb{E}_{y\sim U[\\{1,\ldots,k\\}]}\sum_{i\neq
y}\mathbb{E}_{P_{i},P_{y}}\mathbb{E}_{S_{i},S_{y}}\mathbb{E}_{x\sim
P_{y}}\big{[}\mathbb{I}\left[\|f(x)-\mu_{f}(S_{y})\|<\|f(x)-\mu_{f}(S_{i})\|\right]\big{]}$
$\displaystyle=~{}(k-1)\cdot\mathbb{E}_{P_{1},P_{2}}\mathbb{E}_{S_{1},S_{2}}\mathbb{E}_{x_{1}\sim
P_{1}}\big{[}\mathbb{I}\left[\|f(x_{1})-\mu_{f}(S_{2})\|<\|f(x_{1})-\mu_{f}(S_{1})\|\right]\big{]}$

where $P_{i}\sim\mathcal{D}$ and $S_{i}\sim P^{n}_{i}$. To further bound the
right-hand side above, we use the _soft-margin_ relaxation $\ell_{\Delta}$
(defined in (9)):

$\displaystyle\mathbb{I}\left[\|f(x_{1})-\mu_{f}(S_{2})\|<\|f(x_{1})-\mu_{f}(S_{1})\|\right]$
$\displaystyle\leq\ell_{\Delta}\left(\|f(x_{1})-\mu_{f}(S_{1})\|-\|f(x_{1})-\mu_{f}(S_{2})\|\right),$

implying

$\mathcal{L}_{\mathcal{D}}(f)\leq(k-1)\cdot\mathbb{E}_{P_{1},P_{2}}\mathbb{E}_{S_{1},S_{2}}\mathbb{E}_{x_{1}\sim
P_{1}}\big{[}\ell_{\Delta}\left(\|f(x_{1})-\mu_{f}(S_{1})\|-\|f(x_{1})-\mu_{f}(S_{2})\|\right)\big{]}.$
(14)

By the random selection of $P_{1},P_{2}$, $\tilde{P}_{c},c\in[l]$, the main
term on the right-hand side above (i.e., omitting the $(k-1)$ factor) is equal
to

$\operatorname{Avg}_{i\neq
j\in[l]}\mathbb{E}_{\tilde{P}_{i},\tilde{P}_{j}}\mathbb{E}_{\hat{S}_{i},\hat{S}_{j}}\mathbb{E}_{x_{i}\sim\tilde{P}_{i}}[\ell_{\Delta}(\|f(x_{i})-\mu_{f}(\hat{S}_{i})\|-\|f(x_{i})-\mu_{f}(\hat{S}_{j})\|)].$
(15)

To write this averaging succinctly, we introduce some notation. Let
$\hat{U}_{c}:=(x_{c},\hat{S}_{c})$ for $c\in[l]$ where
$x_{c}\sim\tilde{P}_{c}$ and $\hat{S}_{c}\sim\tilde{P}_{c}^{n}$, independently
for all $c$, and $\hat{\mathcal{U}}:=\\{\hat{U}_{c}\\}^{l}_{c=1}$ (recall that
this also depends on the random choice of the $\tilde{P}_{c}$). Furthermore,
let $\mathcal{Q}:=\\{(x,S)\mid x\in\mathcal{X},~{}S\in\mathcal{X}^{n}\\}$
denote the set of all point-sample pairs (note that
$\hat{U}_{c}\in\mathcal{Q}$). For any $f\in\mathcal{F}$, define
$H_{f}:\mathcal{Q}\to\mathbb{R}$ as $H_{f}(x,S)=(f(x),\mu_{f}(S))$ and for any
$\mathcal{F}^{\prime}\subset\mathcal{F}$ and
$\mathcal{Q}^{\prime}\subset\mathcal{Q}$, let
$H_{\mathcal{F}^{\prime}}:=\\{H_{f}:f\in\mathcal{F}^{\prime}\\}$ and
$H_{\mathcal{F}^{\prime}}(\mathcal{Q}^{\prime}):=\\{H_{f}(x,S):(x,S)\in\mathcal{Q}^{\prime},f\in\mathcal{F}^{\prime}\\}$.
Finally define the aggregation function
$A_{\Delta}:H_{\mathcal{F}}(\mathcal{Q})^{l}\to\mathbb{R}$ as

$A_{\Delta}({\bf z})~{}:=~{}\operatorname{Avg}_{i\neq
j\in[l]}[\ell_{\Delta}(\|u_{i}-v_{i}\|-\|u_{i}-v_{j}\|)],$

where ${\bf z}=(z_{1},\dots,z_{l})$ such that $z_{i}=(u_{i},v_{i})\in
H_{\mathcal{F}}(\mathcal{Q})$ for all $i\in[l]$. Then

$A_{\Delta}(H_{f}(\hat{\mathcal{U}}))=\operatorname{Avg}_{i\neq
j\in[l]}[\ell_{\Delta}(\|f(x_{i})-\mu_{f}(\hat{S}_{i})\|-\|f(x_{i})-\mu_{f}(\hat{S}_{j})\|)]$

by definition, and (15) can be rewritten as
$\mathbb{E}_{\hat{\mathcal{U}}}[A_{\Delta}(H_{f}(\hat{\mathcal{U}}))]$ and
from (14) we get

$\mathcal{L}_{\mathcal{D}}(f)\leq(k-1)\cdot\mathbb{E}_{\hat{\mathcal{U}}}[A_{\Delta}(H_{f}(\hat{\mathcal{U}}))].$
(16)

Our next step is to bound the expectation on the right-hand side above with
the randomly selected samples of class-conditional distributions
$\tilde{P}_{c},c\ \in[l]$ for a fixed $\Delta$. Let $\delta^{\prime}\in(0,1)$
and $\mathcal{F}^{\prime}\subset\mathcal{F}$ with
$\alpha=\sup_{f\in\mathcal{F}^{\prime}}\mathcal{C}(f)<\infty$. It is easy to
see that $\mathcal{F}^{\prime}$ can be approximated arbitrarily closely with a
finite subset $\mathcal{F}^{\prime\prime}$ of $\mathcal{F}$ in $L_{\infty}$
distance, and hence $H_{\mathcal{F}}$ can also be arbitrarily closely
approximated by the corresponding finite set $H_{\mathcal{F}^{\prime\prime}}$.
Then, by the extension of Corollary 3 of Maurer and Pontil (2019) discussed
after (13), with probability at least $1-\delta^{\prime}$ over the selection
of $\hat{\mathcal{U}}$, for all $f\in\mathcal{F}^{\prime}$ we have

$\displaystyle\mathbb{E}_{\hat{\mathcal{U}}}\left[A_{\Delta}(H_{f}(\hat{\mathcal{U}}))\right]$
$\displaystyle\leq
A_{\Delta}(H_{f}(\hat{\mathcal{U}}))+2\sqrt{2\pi\log(l)}\big{(}2M(A_{\Delta})+J(A_{\Delta})\big{)}\cdot\mathbb{E}_{\hat{\mathcal{U}}}[R(H_{\mathcal{F}^{\prime}}(\hat{\mathcal{U}}))]$
(17)
$\displaystyle\qquad+K(A_{\Delta})\cdot\sqrt{l\log\left({\textstyle\frac{1}{\delta^{\prime}}}\right)}.$

Next we bound the terms $K(A_{\Delta})$, $M(A_{\Delta})$, and $J(A_{\Delta})$.

#### Bounding $K(A_{\Delta})$, $M(A_{\Delta})$ and $J(A_{\Delta})$.

Let $\Delta>0$, $j\in[l]$ and
$z_{i}=(u_{i},v_{i})\in\mathbb{R}^{p}\times\mathbb{R}^{p}$ for $i\in[l]$. Let
${\bf z}=(z_{1},\dots,z_{l})$ and ${\bf
z}=(z^{\prime}_{1},\dots,z^{\prime}_{l})$, where $z_{i}=z^{\prime}_{i}$ for
all $i\neq j$. We have

$\displaystyle D^{j}_{z^{\prime}_{j}}A_{\Delta}({\bf z})=A_{\Delta}({\bf
z})-A_{\Delta}({\bf z}^{\prime})$
$\displaystyle=\frac{1}{l(l-1)}\sum_{i_{1}\neq
i_{2}\in[l]}\left(\ell_{\Delta}(\|u_{i_{1}}-v_{i_{1}}\|-\|u_{i_{1}}-v_{i_{2}}\|)-\ell_{\Delta}(\|u^{\prime}_{i_{1}}-v^{\prime}_{i_{1}}\|-\|u^{\prime}_{i_{1}}-v^{\prime}_{i_{2}}\|)\right)$
$\displaystyle=\frac{1}{l(l-1)}\sum_{i\in[l]:~{}i\neq
j}\left(\ell_{\Delta}(\|u_{i}-v_{i}\|-\|u_{i}-v_{j}\|)-\ell_{\Delta}(\|u_{i}-v_{i}\|-\|u_{i}-v^{\prime}_{j}\|)\right)$
$\displaystyle\quad+\frac{1}{l(l-1)}\sum_{i\in[l]:~{}i\neq
j}\left(\ell_{\Delta}(\|u_{j}-v_{j}\|-\|u_{j}-v_{i}\|)-\ell_{\Delta}(\|u^{\prime}_{j}-v^{\prime}_{j}\|-\|u^{\prime}_{j}-v_{i}\|)\right).$
(18)

Since $\ell_{\Delta}$ is $\Delta^{-1}$-Lipschitz and by the triangle
inequality

$\displaystyle\ell_{\Delta}(\|u_{i}-v_{i}\|-\|u_{i}-v_{j}\|)-\ell_{\Delta}(\|u_{i}-v_{i}\|-\|u_{i}-v^{\prime}_{j}\|)$
$\displaystyle\leq\Delta^{-1}\Big{|}\|u_{i}-v_{i}\|-\|u_{i}-v_{j}\|-\|u_{i}-v_{i}\|+\|u_{i}-v^{\prime}_{j}\|\Big{|}$
$\displaystyle=\Delta^{-1}\Big{|}\|u_{i}-v^{\prime}_{j}\|-\|u_{i}-v_{j}\|\Big{|}$
$\displaystyle\leq\Delta^{-1}\|v_{j}-v^{\prime}_{j}\|$ (19)
$\displaystyle\leq\Delta^{-1}\|(u_{j},v_{j})-(u^{\prime}_{j},v^{\prime}_{j})\|$
$\displaystyle=\Delta^{-1}\|z_{j}-z^{\prime}_{j}\|.$ (20)

Similarly,

$\displaystyle\ell_{\Delta}(\|u_{j}-v_{j}\|-\|u_{j}-v_{i}\|)-\ell_{\Delta}(\|u^{\prime}_{j}-v^{\prime}_{j}\|-\|u^{\prime}_{j}-v_{i}\|)$
$\displaystyle\leq\Delta^{-1}\Big{|}\|u_{j}-v_{j}\|-\|u_{j}-v_{i}\|-\|u^{\prime}_{j}-v^{\prime}_{j}\|+\|u^{\prime}_{j}-v_{i}\|\Big{|}$
$\displaystyle\leq\Delta^{-1}\left(\Big{|}\|u_{j}-v_{j}\|-\|u^{\prime}_{j}-v^{\prime}_{j}\|\Big{|}+\Big{|}\|u_{j}-v_{i}\|-\|u^{\prime}_{j}-v_{i}\|\Big{|}\right)$
$\displaystyle\leq\Delta^{-1}\left(\|u_{j}-u^{\prime}_{j}\|+\|v_{j}-v^{\prime}_{j}\|+\|u_{j}-u^{\prime}_{j}\|\right)$
$\displaystyle\leq\Delta^{-1}\left(\|u_{j}-u^{\prime}_{j}\|+\|v_{j}-v^{\prime}_{j}\|+\|(u_{j},v_{j})-(u^{\prime}_{j},v^{\prime}_{j})\|\right)$
$\displaystyle\leq(1+\sqrt{2})\Delta^{-1}\|(u_{j},v_{j})-(u^{\prime}_{j},v^{\prime}_{j})\|$
(21) $\displaystyle=(1+\sqrt{2})\Delta^{-1}\|z_{j}-z^{\prime}_{j}\|,$ (22)

where the last inequality follows from the arithmetic mean–quadratic mean
inequality. Combining (18), (20) and (22), we obtain that

$M(A_{\Delta})=\max_{j\in[l]}\sup_{\begin{subarray}{c}{\bf z}\in
H_{\mathcal{F}}(\mathcal{Q})^{l}\\\ z^{\prime}_{j}\in
H_{\mathcal{F}}(\mathcal{Q}):~{}z^{\prime}_{j}\neq
z_{j}\end{subarray}}\frac{D^{j}_{z^{\prime}_{j}}A({\bf
z})}{\|z_{j}-z^{\prime}_{j}\|}\leq\frac{2+\sqrt{2}}{\Delta l}.$ (23)

Using that $\|u_{j}-u^{\prime}_{j}\|$ and $\|v_{j}-v^{\prime}_{j}\|$ are both
bounded by $2\sup_{x\in\mathcal{X},f\in\mathcal{F}^{\prime}}\|f(x)\|\leq
2\alpha B$ for any ${\bf z},{\bf z}^{\prime}$, we obtain from (18), (19) and
(21) that

$D^{j}_{z^{\prime}_{j}}A_{\Delta}({\bf z})\leq\frac{6+4\sqrt{2}}{\Delta
l}\sup_{x\in\mathcal{X},f\in\mathcal{F}^{\prime}}\|f(x)\|\leq\frac{(6+4\sqrt{2})\alpha
B}{\Delta l}.$

Hence,

$K(A_{\Delta})\leq\frac{(6+4\sqrt{2})\alpha B}{\Delta l}.$ (24)

Finally, we bound $J(A_{\Delta})$. Let $j,r\in[l]$ with $j\neq r$ and ${\bf
z}=(z_{1},\dots,z_{l})\in H_{\mathcal{F}}(\mathcal{Q})^{l}$. We have

$\displaystyle D^{r}_{z^{\prime}_{r}}D^{j}_{z^{\prime}_{j}}A_{\Delta}({\bf
z})$ $\displaystyle=\frac{1}{l(l-1)}\sum_{i\in[l]:~{}i\neq
j}D^{r}_{z^{\prime}_{r}}\left(\ell_{\Delta}(\|u_{i}-v_{i}\|-\|u_{i}-v_{j}\|)-\ell_{\Delta}(\|u_{i}-v_{i}\|-\|u_{i}-v^{\prime}_{j}\|)\right)$
$\displaystyle\quad+\frac{1}{l(l-1)}\sum_{i\in[l]:~{}i\neq
j}D^{r}_{z^{\prime}_{r}}\left(\ell_{\Delta}(\|u_{j}-v_{j}\|-\|u_{j}-v_{i}\|)-\ell_{\Delta}(\|u^{\prime}_{j}-v^{\prime}_{j}\|-\|u^{\prime}_{j}-v_{i}\|)\right)$
$\displaystyle=\frac{1}{l(l-1)}\cdot
D^{r}_{z^{\prime}_{r}}\left(\ell_{\Delta}(\|u_{r}-v_{r}\|-\|u_{r}-v_{j}\|)-\ell_{\Delta}(\|u_{r}-v_{r}\|-\|u_{r}-v^{\prime}_{j}\|)\right)$
$\displaystyle\quad+\frac{1}{l(l-1)}\cdot
D^{r}_{z^{\prime}_{r}}\left(\ell_{\Delta}(\|u_{j}-v_{j}\|-\|u_{j}-v_{r}\|)-\ell_{\Delta}(\|u^{\prime}_{j}-v^{\prime}_{j}\|-\|u^{\prime}_{j}-v_{r}\|)\right),$
(25)

where the second equality follows as all terms are $0$ for which $i\neq r$,
since the function in that case is constant with respect to $u_{r}$ (since
$j\neq r$ by our definition). Using again that $\ell_{\Delta}$ is
$\Delta^{-1}$-Lipschitz, we have

$\displaystyle
D^{r}_{z^{\prime}_{r}}\left(\ell_{\Delta}(\|u_{r}-v_{r}\|-\|u_{r}-v_{j}\|)-\ell_{\Delta}(\|u_{r}-v_{r}\|-\|u_{r}-v^{\prime}_{j}\|)\right)$
$\displaystyle=\ell_{\Delta}(\|u_{r}-v_{r}\|-\|u_{r}-v_{j}\|)-\ell_{\Delta}(\|u_{r}-v_{r}\|-\|u_{r}-v^{\prime}_{j}\|)$
$\displaystyle\quad-\ell_{\Delta}(\|u^{\prime}_{r}-v^{\prime}_{r}\|-\|u^{\prime}_{r}-v_{j}\|)+\ell_{\Delta}(\|u^{\prime}_{r}-v^{\prime}_{r}\|-\|u^{\prime}_{r}-v^{\prime}_{j}\|)$
$\displaystyle\leq 2\Delta^{-1}\|v_{j}-v^{\prime}_{j}\|.$ (26)

Similarly,

$\displaystyle
D^{r}_{z^{\prime}_{r}}\left(\ell_{\Delta}(\|u_{j}-v_{j}\|-\|u_{j}-v_{r}\|)-\ell_{\Delta}(\|u^{\prime}_{j}-v^{\prime}_{j}\|-\|u^{\prime}_{j}-v_{r}\|)\right)$
$\displaystyle=\ell_{\Delta}(\|u_{j}-v_{j}\|-\|u_{j}-v_{r}\|)-\ell_{\Delta}(\|u^{\prime}_{j}-v^{\prime}_{j}\|-\|u^{\prime}_{j}-v_{r}\|)$
$\displaystyle\quad-\ell_{\Delta}(\|u_{j}-v_{j}\|-\|u_{j}-v^{\prime}_{r}\|)+\ell_{\Delta}(\|u^{\prime}_{j}-v^{\prime}_{j}\|-\|u^{\prime}_{j}-v^{\prime}_{r}\|)$
$\displaystyle\leq|\ell_{\Delta}(\|u_{j}-v_{j}\|-\|u_{j}-v_{r}\|)-\ell_{\Delta}(\|u^{\prime}_{j}-v^{\prime}_{j}\|-\|u^{\prime}_{j}-v_{r}\|)|$
$\displaystyle\quad+|\ell_{\Delta}(\|u_{j}-v_{j}\|-\|u_{j}-v^{\prime}_{r}\|)-\ell_{\Delta}(\|u^{\prime}_{j}-v^{\prime}_{j}\|-\|u^{\prime}_{j}-v^{\prime}_{r}\|)$
$\displaystyle\leq
2\Delta^{-1}\left(\|u_{j}-u^{\prime}_{j}\|+\|u_{j}-u^{\prime}_{j}+v^{\prime}_{j}-v_{j}\|\right)$
$\displaystyle\leq
2\Delta^{-1}\left(2\|u_{j}-u^{\prime}_{j}\|+\|v_{j}-v^{\prime}_{j}\|\right)$
(27)

Combining (25)–(27) with the arithmetic mean–quadratic mean inequality, we
obtain

$\frac{D^{r}_{z^{\prime}_{r}}D^{j}_{z^{\prime}_{j}}A_{\Delta}({\bf
z})}{\|z_{j}-z^{\prime}_{j}\|}\leq\frac{4\left(\|u_{j}-u^{\prime}_{j}\|+\|v_{j}-v^{\prime}_{j}\|\right)}{l(l-1)\Delta\|z_{j}-z^{\prime}_{j}\|}\leq\frac{4\sqrt{2}}{l(l-1)\Delta},$

which gives

$J(A_{\Delta})\leq\frac{4\sqrt{2}}{\Delta(l-1)}.$ (28)

Substituting (23), (24), and (28) into (17), we get that with probability at
least $1-\delta^{\prime}$ over the selection of $\hat{\mathcal{U}}$ for any
$f\in\mathcal{F}^{\prime}$ with
$\sup_{f\in\mathcal{F}^{\prime}}\mathcal{C}(f)\leq\alpha$,

$\displaystyle\mathbb{E}_{\hat{\mathcal{U}}}\left[A_{\Delta}(H_{f}(\hat{\mathcal{U}}))\right]{}$
$\displaystyle\leq~{}A_{\Delta}(H_{f}(\hat{\mathcal{U}}))+\frac{8(3+\sqrt{2})\sqrt{\pi\log(l)}\cdot\mathbb{E}_{\hat{\mathcal{U}}}[R(H_{\mathcal{F}^{\prime}}(\hat{\mathcal{U}}))]}{\Delta(l-1)}$
(29) $\displaystyle\quad+\frac{(6+4\sqrt{2})\alpha
B}{\Delta\sqrt{l}}\sqrt{\log\left({\textstyle\frac{1}{\delta^{\prime}}}\right)}.$

To be able to adapt to the complexity $\mathcal{C}(f)$ of $f$ and prove a
bound for all $\Delta$, we apply the above to
$\mathcal{F}^{\prime}=\mathcal{F}^{\alpha}:=\\{f\in\mathcal{F}:\mathcal{C}(f)\leq\alpha\\}$
with positive integers $\alpha$ and for an exponential grid for $\Delta$
defined as $\Delta_{t}=2^{-t}B$ for any integer $t$ and
$\delta^{\prime}=\delta_{t,\alpha}$ where
$\delta_{t,\alpha}:={\textstyle\frac{\delta}{3\alpha(\alpha+1)|t|(|t|+1)}}$
for all $t\neq 0$ and
$\delta_{0,\alpha}:={\textstyle\frac{\delta}{3\alpha(\alpha+1)}}$. Note that
by definition,
$\sum_{t=-\infty}^{\infty}\sum_{\alpha=1}^{\infty}\delta_{t,\alpha}=\delta$.

#### Bounding
$\mathbb{E}_{\hat{\mathcal{U}}}[R(H_{\mathcal{F}^{\alpha}}(\hat{\mathcal{U}}))]$.

As a next step, we upper bound
$\mathbb{E}_{\hat{\mathcal{U}}}[R(H_{\mathcal{F}^{\alpha}}(\hat{\mathcal{U}}))]$.
Let $\epsilon$ be the collection of i.i.d. Rademacher random variables
$\epsilon^{1}_{cj}$ and $\epsilon^{2}_{cj}$ for $c\in[l]$ and $j\in[p]$. Then

$\displaystyle\mathbb{E}_{\hat{\mathcal{U}}}[R(H_{\mathcal{F}^{\alpha}}(\hat{\mathcal{U}}))]$
$\displaystyle=\mathbb{E}_{\hat{\mathcal{U}}}\mathbb{E}_{\epsilon}\left[\sup_{f\in\mathcal{F}^{\alpha}}\sum^{l}_{c=1}\sum^{p}_{j=1}\left(f(x_{c})_{j}\epsilon^{1}_{cj}+\mu_{f}(\hat{S}_{c})_{j}\epsilon^{2}_{cj}\right)\right]$
$\displaystyle\leq\mathbb{E}_{\hat{\mathcal{U}}}\mathbb{E}_{\epsilon}\left[\sup_{f\in\mathcal{F}^{\alpha}}\sum^{p}_{j=1}\sum^{l}_{c=1}f(x_{c})_{j}\epsilon^{1}_{cj}\right]+\mathbb{E}_{\hat{\mathcal{U}}}\mathbb{E}_{\epsilon}\left[\sup_{f\in\mathcal{F}^{\alpha}}\sum^{p}_{j=1}\sum^{l}_{c=1}\mu_{f}(\hat{S}_{c})_{j}\epsilon^{2}_{cj}\right]$
$\displaystyle=\mathbb{E}_{\hat{\mathcal{U}}}\mathbb{E}_{\epsilon}\left[\sup_{f\in\mathcal{F}^{\alpha}}\sum^{p}_{j=1}\sum^{l}_{c=1}f(x_{c})_{j}\epsilon^{1}_{cj}\right]+\mathbb{E}_{\hat{\mathcal{U}}}\mathbb{E}_{\epsilon}\left[\sup_{f\in\mathcal{F}^{\alpha}}\sum^{p}_{j=1}\sum^{l}_{c=1}\mathbb{E}_{x_{c}\sim
U[\hat{S}_{c}]}f(x_{c})_{j}\epsilon^{2}_{cj}\right]$
$\displaystyle\leq\mathbb{E}_{\hat{\mathcal{U}}}\mathbb{E}_{\epsilon}\left[\sup_{f\in\mathcal{F}^{\alpha}}\sum^{p}_{j=1}\sum^{l}_{c=1}f(x_{c})_{j}\epsilon^{1}_{cj}\right]+\mathbb{E}_{\hat{\mathcal{U}}}\mathbb{E}_{x_{c}\sim
U[\hat{S}_{c}]}\mathbb{E}_{\epsilon}\left[\sup_{f\in\mathcal{F}^{\alpha}}\sum^{p}_{j=1}\sum^{l}_{c=1}f(x_{c})_{j}\epsilon^{2}_{cj}\right]$
$\displaystyle=2\mathbb{E}_{x_{1},\dots,x_{l}}\left[R(\mathcal{F}^{\alpha}(\\{x_{c}\\}^{l}_{c=1}))\right].$
(30)

Due to the homogenity of the ReLU nonlinearities, we can rescale the layers of
a ReLU network so that all layer matrix have norm at most $1$ except for the
last layer, that is, any $f\in\mathcal{F}^{\alpha}$ can be written in a
canonical form as $f=W^{q}\tilde{f}$ with $\|W^{q}\|_{F}\leq\alpha$ and some
$\tilde{f}\in\tilde{\mathcal{F}}:=\\{\sigma(W^{q-1}(\dots
W^{2}\sigma(W^{1}x)\dots)\mid\forall i\leq q-1:~{}\|W^{i}\|_{F}\leq 1\\}$.
Denoting the $j$th row of $W^{q}$ by $W^{q}_{(j)}$, for any
$\\{x_{1},\dots,x_{l}\\}\subset\mathcal{X}$ we can bound the Rademacher
complexity as

$\displaystyle R(\mathcal{F}^{\alpha}(\\{x_{c}\\}^{l}_{c=1})$
$\displaystyle=\mathbb{E}_{\epsilon}\left[\sup_{f\in\mathcal{F}^{\alpha}}\sum^{p}_{j=1}\sum^{l}_{c=1}f(x_{c})_{j}\epsilon_{cj}\right]$
$\displaystyle=\mathbb{E}_{\epsilon}\left[\sup_{\begin{subarray}{c}W^{q}:~{}\|W^{q}\|_{F}\leq\alpha\\\
\tilde{f}\in\tilde{\mathcal{F}}\end{subarray}}\sum^{p}_{j=1}\sum^{l}_{c=1}W^{q}_{(j)}\tilde{f}(x_{c})\epsilon_{cj}\right]$
$\displaystyle\leq\alpha\mathbb{E}_{\epsilon}\left[\sup_{g\in\mathcal{G}}\max_{j\in[p]}\left\|\sum^{l}_{c=1}\tilde{f}(x_{c})\epsilon_{cj}\right\|\right]$
$\displaystyle\leq\frac{\alpha}{\lambda}\log\left(\mathbb{E}_{\epsilon}\left[\max_{j\in[p]}\sup_{\tilde{f}\in\tilde{\mathcal{F}}}\exp\left(\lambda\left\|\sum^{l}_{c=1}\tilde{f}(x_{c})\epsilon_{cj}\right\|\right)\right]\right)$
$\displaystyle\leq\frac{\alpha}{\lambda}\log\left(\mathbb{E}_{\epsilon}\left[\sum_{j\in[p]}\sup_{\tilde{f}\in\tilde{\mathcal{F}}}\exp\left(\lambda\left\|\sum^{l}_{c=1}\tilde{f}(x_{c})\epsilon_{cj}\right\|\right)\right]\right)$
$\displaystyle=\frac{\alpha}{\lambda}\log\left(p\cdot\mathbb{E}_{\epsilon}\left[\sup_{\tilde{f}\in\tilde{\mathcal{F}}}\exp\left(\lambda\left\|\sum^{l}_{c=1}\tilde{f}(x_{c})\epsilon_{c1}\right\|\right)\right]\right),$

where (i) the first inequality follows by moving all the norms of $W^{q}$ to
the row maximizing
$W^{q}_{(j)}\sum_{c=1}^{l}W^{q}_{(j)}\tilde{f}(x_{c})\epsilon_{cj}$ and
applying the Cauchy-Schwartz inequality; (ii) the second inequality follows
for arbitrary $\lambda>0$ (to be chosen later) by Jensen’s inequality and
flipping the order of the $\sup$ and the $\max$; (iii) the thrid inequality
follows by upper bounding the maximum over $j$ by the sum; while (iv) the last
equality holds by exchanging the expectation and the summation over $j$, and
noticing that the resulting expectation is the same for all $j$. Finally, by
the proof of Theorem 1 of Golowich et al. (2017), when choosing
$\lambda={\textstyle\frac{\sqrt{2(q\log(2)+\log(p))}}{\sqrt{\sum^{l}_{c=1}\|x_{c}\|^{2}}}}$,
we have

$\displaystyle R\left(\mathcal{F}^{\alpha}(\\{x_{c}\\}^{l}_{c=1})\right)$
$\displaystyle\leq\alpha\sqrt{2l(q\log(2)+\log(p))}\cdot\max_{c\in[l]}\|x_{c}\|~{}.$
(31)

Plugging into (30) (and using that $B=\sup_{x\in\mathcal{X}}\|x\|$ by
definition) gives

$\mathbb{E}_{\hat{\mathcal{U}}}[R(H_{\mathcal{F}^{\alpha}}(\hat{\mathcal{U}}))]\leq
2\alpha B\sqrt{2l(q\log(2)+\log(p))}.$ (32)

Substituting this into (29) and using that $l-1\geq l/2$ for $l\geq 2$ and the
union bound, we obtain that with probability at least $1-\delta$, for all
integers $t$, positive integers $\alpha$, and $f\in\mathcal{F}^{\alpha}$,

$\displaystyle\mathbb{E}_{\hat{\mathcal{U}}}\left[A_{\Delta_{t}}(H_{f}(\hat{\mathcal{U}}))\right]$
$\displaystyle\leq A_{\Delta_{t}}(H_{f}(\hat{\mathcal{U}}))+\frac{\alpha
B}{\Delta_{t}\sqrt{l}}\left(355\sqrt{\log(l)(q\log(2)+\log(p))}+(6\\!+\\!4\sqrt{2})\sqrt{\log\\!\left(\\!\frac{3(\alpha+1)^{2}(|t|+1)^{2}}{\delta}\right)}\right).$

Now, for any $\Delta>0$ there exists a $t$ such that $\Delta\leq\Delta_{t}\leq
2\Delta$; then clearly $|t|\leq|\log({\textstyle\frac{\Delta}{B}})|+1$. Since
$\ell_{\Delta}$ and $A_{\Delta}$ monotonically increase in $\Delta$, the above
inequality with $\alpha=\lceil\mathcal{C}(f)\rceil$ implies that with
probability at least $1-\delta$ over the choice of $\hat{\mathcal{U}}$, for
all $f\in\mathcal{F}$ we have

$\displaystyle\mathbb{E}_{\hat{\mathcal{U}}}\left[A_{\Delta}(H_{f}(\hat{\mathcal{U}}))\right]$
(33) $\displaystyle\leq
A_{2\Delta}(H_{f}(\hat{\mathcal{U}}))+\frac{\lceil\mathcal{C}(f)\rceil
B}{\Delta\sqrt{l}}\left(355\sqrt{\log(l)(q\log(2)+\log(p))}+16.5\sqrt{\log\left(\frac{\sqrt{3}(\lceil\mathcal{C}(f)\rceil+1)(|\log({\textstyle\frac{\Delta}{B}})|+2)}{\sqrt{\delta}}\right)}\right).$

Let $\mathcal{Z}_{\delta}$ denote the event that the above inequality (Eq. 33)
does not hold; then we have that $\Pr[\mathcal{Z}_{\delta}]\leq\delta$. Let
$p_{\delta^{2},\tilde{\mathcal{P}}}:=\Pr[\mathcal{Z}_{\delta^{2}}|\tilde{\mathcal{P}}]$
denote the conditional probability that (33) holds with $\delta^{2}$ in place
of $\delta$ given the random choice of $\tilde{\mathcal{P}}$. Then,

$\mathbb{E}_{\tilde{\mathcal{P}}}[p_{\delta^{2},\tilde{\mathcal{P}}}]=\Pr[\mathcal{Z}_{\delta^{2}}]\leq\delta^{2}$

and hence by Markov’s inequality,

$\Pr[p_{\delta^{2},\tilde{\mathcal{P}}}\geq\delta]\leq\frac{\mathbb{E}_{\tilde{\mathcal{P}}}[p_{\delta^{2},\tilde{\mathcal{P}}}]}{\delta}\leq\delta.$

That is, with probability at least $1-\delta$ over the choice of
$\tilde{\mathcal{P}}$, with probability at least $1-\delta^{2}$ over the
choice of $\hat{\mathcal{U}}$ (given $\tilde{\mathcal{P}}$), for all
$f\in\mathcal{F}$ we have

$\displaystyle\mathbb{E}_{\hat{\mathcal{U}}}\left[A_{\Delta}(H_{f}(\hat{\mathcal{U}}))\right]$
(34)
$\displaystyle\leq~{}A_{2\Delta}(H_{f}(\hat{\mathcal{U}}))+\frac{\lceil\mathcal{C}(f)\rceil
B}{\Delta\sqrt{l}}\left(355\sqrt{\log(l)(q\log(2)+\log(p))}+16.5\sqrt{\log\left(\frac{\sqrt{3}(\lceil\mathcal{C}(f)\rceil+1)(|\log({\textstyle\frac{\Delta}{B}})|+2)}{\delta}\right)}\right).$

Taking expectation with respect to $\hat{\mathcal{U}}$ given
$\tilde{\mathcal{P}}$, we have

$\displaystyle\mathbb{E}_{\hat{\mathcal{U}}}[A_{2\Delta}(H_{f}(\hat{\mathcal{U}}))\mid\tilde{\mathcal{P}}]~{}$
$\displaystyle=~{}\operatorname{Avg}_{i\neq
j\in[l]}\mathbb{E}_{\hat{\mathcal{U}}}\left[\ell_{2\Delta}(\|f(x_{i})-\mu_{f}(\hat{S}_{j})\|-\|f(x_{i})-\mu_{f}(\hat{S}_{i})\|)\mid\tilde{\mathcal{P}}\right]$
$\displaystyle=~{}\operatorname{Avg}_{i\neq
j\in[l]}\mathbb{E}_{\hat{S}_{i},\hat{S}_{j}}[\ell_{2\Delta}(\|f(x_{i})-\mu_{f}(\hat{S}_{j})\|-\|f(x_{i})-\mu_{f}(\hat{S}_{i})\|)\mid\tilde{\mathcal{P}}]$
$\displaystyle=~{}\operatorname{Avg}_{i\neq
j\in[l]}\mathbb{E}_{\hat{S}_{i},\hat{S}_{j}}[\ell_{2\Delta}(f;\tilde{P}_{i},\tilde{P}_{j})]$

Combining with (34) and also that $A_{\Delta}(H_{f}(\hat{\mathcal{U}}))\leq 1$
for all $\hat{\mathcal{U}}$ yields that with probability at least $1-\delta$
over the choice of $\tilde{\mathcal{P}}$, for all $f\in\mathcal{F}$

$\displaystyle\mathbb{E}_{\hat{\mathcal{U}}}\left[A_{\Delta}(H_{f}(\hat{\mathcal{U}}))\right]~{}$
$\displaystyle\leq~{}\operatorname{Avg}_{i\neq
j\in[l]}\mathbb{E}_{\hat{S}_{i},\hat{S}_{j}}[\ell_{2\Delta}(f;\tilde{P}_{i},\tilde{P}_{j})]+\delta^{2}$
$\displaystyle\quad+\frac{\lceil\mathcal{C}(f)\rceil
B}{\Delta\sqrt{l}}\left(355\sqrt{\log(l)(q\log(2)+\log(p))}+16.5\sqrt{\log\left({\textstyle\frac{\sqrt{3}(\lceil\mathcal{C}(f)\rceil+1)(|\log({\textstyle\frac{\Delta}{B}})|+2)}{\delta}}\right)}\right).$

The statement of the lemma now follows by combining this inequality with (16).

##  B Proof of Lemma 5

See 5

Proof  As in the proof of Lemma 4, we proceed by considering feature maps $f$
belonging to the function class
$\mathcal{F}^{\alpha}:=\\{f\in\mathcal{F}:\mathcal{C}(f)\leq\alpha\\}$ for a
sequence of $\alpha$ growing to infinity. For now, fix $\alpha>0$,
$f\in\mathcal{F}^{\alpha}$, and $\Delta>0$. Our plan is to rewrite
$\ell_{\Delta}(f;\tilde{S}_{i},\tilde{S}_{j})$ as an average so that we can
apply our extension (13) of Corollary 3 of Maurer and Pontil (2019) to get a
generalization bound.

To this end, consider a vector ${\bf z}=({\bf z}_{i},{\bf
z}_{j})\in\mathcal{F}(\mathcal{X})^{m}\times\mathcal{F}(\mathcal{X})^{m}$ with
${\bf z}_{r}=(z_{r1},\ldots,z_{rm})$ for $r\in\\{i,j\\}$ (representing $m$
samples from classes $i$ and $j$, respectively), and multi-sets
$I_{i},I_{j}\subset[m]$ of size $n$ representing the indices of $n$ samples
selected from ${\bf z}_{i}$ and ${\bf z}_{j}$ without replacement. For
$r\in\\{i,j\\}$, let $\mu_{r,I_{r}}({\bf z})=\operatorname{Avg}_{b\in
I_{r}}[z_{rb}]$ denote the mean of the selected subsamples, and for any
$I=(I_{i},I_{j})$ and $b\in[m]$, denote the soft-margin loss of $z_{ib}$ of
the nearest neighbor classifier defined by $\mu_{i,I_{i}}({\bf z})$ and
$\mu_{j,I_{j}}({\bf z})$ as

$Q_{\Delta}({\bf z};I,b):=\ell_{\Delta}(\|z_{ib}-\mu_{i,I_{i}}({\bf
z})\|-\|z_{ib}-\mu_{j,I_{j}}({\bf z})\|).$

Finally, define the aggregation function
$B_{\Delta}:\mathcal{F}(\mathcal{X})^{2m}\to\mathbb{R}$ as

$B_{\Delta}({\bf z}):=B_{\Delta}({\bf z}_{i},{\bf
z}_{j}):=\operatorname{Avg}_{b,I}[Q_{\Delta}({\bf z};I,b)],$

where in the average $b$ ranges over $[m]$ and $I=(I_{i},I_{j})$ over any
pairs of multi-sets $I_{i},I_{j}\subset[m]$ of cardinality $n$. Then clearly

$B_{\Delta}(f(\tilde{S}_{i}),f(\tilde{S}_{j}))=\ell_{\Delta}(f;\tilde{S}_{i},\tilde{S}_{j}).$
(35)

Denoting $\tilde{S}_{i}=\\{\tilde{x}_{i1},\ldots,\tilde{x}_{im}\\}$ and
$\tilde{S}_{j}=\\{\tilde{x}_{j1},\ldots,\tilde{x}_{jm}\\}$, we can think of
$(f(\tilde{S}_{i}),f(\tilde{S}_{j}))$ as a collection of $m$ i.i.d. vectors
$(f(\tilde{x}_{ib}),f(\tilde{x}_{jb}))_{b\in[m]}$, hence by extension (13) of
Corollary 3 of Maurer and Pontil (2019), for any
$\mathcal{F}^{\prime}\subset\mathcal{F}^{\alpha}$ with
$\alpha=\sup_{f\in\mathcal{F}^{\prime}}\mathcal{C}(f)$ and any
$\delta^{\prime}\in(0,1)$, with probability at least $1-\delta^{\prime}$ over
the selection of $\tilde{S}_{i}$ and $\tilde{S}_{j}$ we have

$\displaystyle\mathbb{E}_{\tilde{S}_{i},\tilde{S}_{j}}[B_{\Delta}(f(\tilde{S}_{i}),f(\tilde{S}_{j}))]$
(36) $\displaystyle\leq
B_{\Delta}(f(\tilde{S}_{i}),f(\tilde{S}_{j}))+2\sqrt{2\pi\log(m)}\big{(}2M(B_{\Delta})+J(B_{\Delta})\big{)}\cdot\mathbb{E}_{\tilde{S}_{i},\tilde{S}_{j}}[R(\mathcal{F}^{\prime}(\tilde{S}_{i}\cup\tilde{S}_{j}))]$
$\displaystyle\qquad+K(B_{\Delta})\cdot\sqrt{m\log\left({\textstyle\frac{1}{\delta^{\prime}}}\right)}.$

Next we explore how
$\mathbb{E}_{\tilde{S}_{i},\tilde{S}_{j}}[B_{\Delta}(f(\tilde{S}_{i}),f(\tilde{S}_{j}))]$
and $\ell_{\Delta}(f;\tilde{P}_{i},\tilde{P}_{j})$ are related.

$\displaystyle\mathbb{E}_{\tilde{S}_{i},\tilde{S}_{j}}[B_{\Delta}(f(\tilde{S}_{i}),f(\tilde{S}_{j}))]$
$\displaystyle=~{}\mathbb{E}_{\tilde{S}_{i},\tilde{S}_{j}}[\ell_{\Delta}(f;\tilde{S}_{i},\tilde{S}_{j})]$
$\displaystyle=~{}\mathbb{E}_{\tilde{S}_{i},\tilde{S}_{j}}\mathbb{E}_{\bar{S}_{i}\sim
U[\tilde{S}_{i}]^{n}}\mathbb{E}_{\bar{S}_{j}\sim
U[\tilde{S}_{j}]^{n}}\mathbb{E}_{\tilde{x}_{i}\sim
U[\tilde{S}_{i}]}[\ell_{\Delta}(\|f(\tilde{x}_{i})-\mu_{f}(\bar{S}_{i})\|-\|f(\tilde{x}_{i})-\mu_{f}(\bar{S}_{j})\|)]$
$\displaystyle=~{}\mathbb{E}_{\tilde{S}_{i},\tilde{S}_{j}}\mathbb{E}_{\bar{S}_{i}\sim
U[\tilde{S}_{i}]^{n}}\mathbb{E}_{\bar{S}_{j}\sim
U[\tilde{S}_{j}]^{n}}\mathbb{E}_{b\sim
U[m]}[\ell_{\Delta}(\|f(\tilde{x}_{ib})-\mu_{f}(\bar{S}_{i})\|-\|f(\tilde{x}_{ib})-\mu_{f}(\bar{S}_{j})\|)].$

Note that by replacing $\tilde{x}_{i}\sim U[\tilde{S}_{i}]$ with
$\tilde{x}_{i}\sim\tilde{P}_{i}$, the above expression would be equal to

$\ell_{\Delta}(f;\tilde{P}_{i},\tilde{P}_{j})=\mathbb{E}_{\hat{S}_{i}\sim\tilde{P}^{n}_{i}}\mathbb{E}_{\hat{S}_{j}\sim\tilde{P}^{n}_{j}}\mathbb{E}_{\tilde{x}_{i}\sim\tilde{P}_{i}}[\ell_{\Delta}(\|f(\tilde{x}_{i})-\mu_{f}(\hat{S}_{i})\|-\|f(\tilde{x}_{i})-\mu_{f}(\hat{S}_{j})\|)],$

which is the term that we would like to bound. The problem is that because
both $\tilde{x}_{i}$ and $\bar{S}_{i}$ are selected from $\tilde{S}_{i}$, they
are not independent. However, since $n\ll m$, it is likely that
$\tilde{x}_{i}$ is not an element of $\bar{S}_{i}$; to put it differently, the
index $b$ of $\tilde{x}_{i}$ (i.e., $\tilde{x}_{i}=\tilde{x}_{ib}$) does not
belong to the multi-set of indices $I_{i}$ defining $\bar{S}_{i}$ (i.e.,
$\bar{S}_{i}=\\{\tilde{x}_{ib^{\prime}}:b^{\prime}\in I_{i}\\}$. Under this
assumption, $\tilde{x}_{i}$ and $\bar{S}_{i}$ become independent with
$\tilde{x}_{i}$ following distribution $\tilde{P}_{i}$. Since $I_{i}$ contains
at most $n$ different indices, we indeed have $\Pr[b\notin I_{i}]\geq
1-{\textstyle\frac{n}{m}}$. These, together with the nonnegativity of
$\ell_{\Delta}$ imply that

$\displaystyle\mathbb{E}_{\tilde{S}_{i},\tilde{S}_{j}}[B_{\Delta}(f(\tilde{S}_{i}),f(\tilde{S}_{j}))]$
$\displaystyle\geq~{}\mathbb{E}_{\tilde{S}_{i},\tilde{S}_{j}}\mathbb{E}_{\bar{S}_{i},\bar{S}_{j}}\mathbb{E}_{b\sim
U[m]}[\ell_{\Delta}(\|f(\tilde{x}_{ib})-\mu_{f}(\bar{S}_{i})\|-\|f(\tilde{x}_{ib})-\mu_{f}(\bar{S}_{j})\|)\mid
b\notin I_{i}]\cdot\Pr[b\notin I_{i}]$
$\displaystyle\geq~{}\mathbb{E}_{\tilde{S}_{i},\tilde{S}_{j}}\mathbb{E}_{\bar{S}_{i},\bar{S}_{j}}\mathbb{E}_{b\sim
U[m]}[\ell_{\Delta}(\|f(\tilde{x}_{ib})-\mu_{f}(\bar{S}_{i})\|-\|f(\tilde{x}_{ib})-\mu_{f}(\bar{S}_{j})\|)\mid
b\notin I_{i}]\cdot\left(1-{\textstyle\frac{n}{m}}\right)$
$\displaystyle=~{}\mathbb{E}_{\tilde{S}_{i},\tilde{S}_{j}}\mathbb{E}_{\bar{S}_{i},\bar{S}_{j}}\mathbb{E}_{b\sim
U[[m]\setminus
I_{i}]}[\ell_{\Delta}(\|f(\tilde{x}_{ib})-\mu_{f}(\bar{S}_{i})\|-\|f(\tilde{x}_{ib})-\mu_{f}(\bar{S}_{j})\|)]\cdot\left(1-{\textstyle\frac{n}{m}}\right)$
$\displaystyle=~{}\mathbb{E}_{\tilde{S}_{i},\tilde{S}_{j}}\mathbb{E}_{\bar{S}_{i},\bar{S}_{j}}\mathbb{E}_{\tilde{x}_{i}\sim\tilde{P}_{i}}[\ell_{\Delta}(\|f(\tilde{x}_{i})-\mu_{f}(\bar{S}_{i})\|-\|f(\tilde{x}_{i})-\mu_{f}(\bar{S}_{j})\|)]\left(1-{\textstyle\frac{n}{m}}\right).$
(37)

Finally, we would like to replace the distributions of $\bar{S}_{i}$, and
$\bar{S}_{j}$ above from $U[\tilde{S}_{i}]^{n}$ and $U[\tilde{S}_{j}]^{n}$ to
$\tilde{P}_{i}^{n}$ and $\tilde{P}_{j}^{n}$, respectively. Note that sampling
$\bar{S}_{i}\sim\tilde{P}^{n}_{j}$ is equivalent to sampling
$\tilde{S}_{i}\sim\tilde{P}^{m}_{i}$ and then $\bar{S}_{i}\sim
U[\tilde{S}_{i}]^{n}$ conditioned on the event that the indices of the samples
we choose to put in $\bar{S}_{i}$ are unique. This event happens with
probability ${\textstyle\frac{m(m-1)\cdots(m-n+1)}{m^{n}}}$, and hence

$\displaystyle\mathbb{E}_{\tilde{S}_{i},\tilde{S}_{j}}\mathbb{E}_{\bar{S}_{i}\sim
U[\tilde{S}_{i}]^{n},\bar{S}_{j}\sim
U[\tilde{S}_{j}]^{n}}\mathbb{E}_{\tilde{x}_{i}\sim\tilde{P}_{i}}[\ell_{\Delta}(\|f(\tilde{x}_{i})-\mu_{f}(\bar{S}_{i})\|-\|f(\tilde{x}_{i})-\mu_{f}(\bar{S}_{j})\|)]$
$\displaystyle\geq~{}\mathbb{E}_{\tilde{S}_{i},\tilde{S}_{j}}\mathbb{E}_{\bar{S}_{i}\sim\tilde{P}_{i}^{n},\bar{S}_{j}\sim\tilde{P}_{j}^{n}}\mathbb{E}_{\tilde{x}_{i}\sim\tilde{P}_{i}}[\ell_{\Delta}(\|f(\tilde{x}_{i})-\mu_{f}(\bar{S}_{i})\|-\|f(\tilde{x}_{i})-\mu_{f}(\bar{S}_{j})\|)]\cdot{\textstyle\frac{m(m-1)\cdots(m-n+1)}{m^{n}}}$
$\displaystyle=~{}\mathbb{E}_{\bar{S}_{i}\sim\tilde{P}_{i}^{n}}\mathbb{E}_{\bar{S}_{j}\sim\tilde{P}_{j}^{n}}\mathbb{E}_{\tilde{x}_{i}\sim\tilde{P}_{i}}[\ell_{\Delta}(\|f(\tilde{x}_{i})-\mu_{f}(\bar{S}_{i})\|-\|f(\tilde{x}_{i})-\mu_{f}(\bar{S}_{j})\|)]\cdot{\textstyle\frac{m(m-1)\cdots(m-n+1)}{m^{n}}}$
$\displaystyle\geq~{}{\textstyle\frac{1}{4}}\ell_{\Delta}(f;\tilde{P}_{i},\tilde{P}_{j}),$

where in the last step we used that
${\textstyle\frac{m(m-1)\cdots(m-n+1)}{m^{n}}}\geq 2/9$ which is easy to see:
for $m\geq 4$, we have

${\textstyle\frac{m(m-1)\cdots(m-n+1)}{m^{n}}}=\left(1-{\textstyle\frac{1}{m}}\right)\cdots\left(1-{\textstyle\frac{n-1}{m}}\right)\geq\left(1-{\textstyle\frac{1}{\sqrt{m}}}\right)^{\sqrt{m}}\geq{\textstyle\frac{1}{4}}$

because $n\leq\sqrt{m}$, and the bound follows by inspection for
$m\in\\{1,2,3\\}$.

Combining with (35), (36), and (37), we obtain

$\displaystyle\ell_{\Delta}(f;\tilde{P}_{i},\tilde{P}_{j}){}$
$\displaystyle\leq~{}{\textstyle\frac{4m}{m-n}}\cdot\ell_{\Delta}(f;\tilde{S}_{i},\tilde{S}_{j})$
(38)
$\displaystyle\quad+\frac{8m\sqrt{2\pi\log(2m)}}{m-n}\big{(}2M(B_{\Delta})+J(B_{\Delta})\big{)}\cdot\mathbb{E}_{\tilde{S}_{i},\tilde{S}_{j}}[R(\mathcal{F}^{\prime}(\tilde{S}_{i}\cup\tilde{S}_{j})))]$
$\displaystyle\quad+\frac{4m}{m-n}K(B_{\Delta})\cdot\sqrt{2m\log({\textstyle\frac{1}{\delta^{\prime}}})}.$

It remains to bound $M(B_{\Delta})$, $J(B_{\Delta})$ and $K(B_{\Delta})$.

#### Bounding $K(B_{\Delta})$ and $M(B_{\Delta})$.

Let $z_{rt}\in\mathbb{R}^{p}$ for $r\in\\{i,j\\}$, $t\in[m]$ with ${\bf
z}_{r}=(z_{r1},\dots,z_{rm})$ and ${\bf
z}^{\prime}_{r}=(z^{\prime}_{r1},\dots,z^{\prime}_{rm})$, where
$z_{rb}=z^{\prime}_{rb}$ for all $b\neq t$. By definition, for ${\bf z}=({\bf
z}_{i},{\bf z}_{j})$ and ${\bf z}^{\prime}=({\bf z}^{\prime}_{i},{\bf
z}^{\prime}_{j})$,

$\displaystyle D^{t}_{(z^{\prime}_{it},z^{\prime}_{jt})}B_{\Delta}({\bf z})$
$\displaystyle=B_{\Delta}({\bf z})-B_{\Delta}({\bf
z}^{\prime})=\operatorname{Avg}_{b,I}\left[Q_{\Delta}({\bf
z};I,b)-Q_{\Delta}({\bf z}^{\prime};I,b)\right].$ (39)

Note that the actual organization of the variables in $B_{\Delta}({\bf z})$ is
according to pairs $(z_{ib},z_{jb})_{b\in[m]}$, so in the partial difference
operator above we consider changing a pair. To bound (39), we consider the
difference of the $Q_{\Delta}$ functions above. Using that $\ell_{\Delta}$ is
$\Delta^{-1}$-Lipschitz, the triangle inequality and that ${\bf z}$ and ${\bf
z}^{\prime}$ only differ in a single coordinate $(r,t)$, we obtain the
following:

$\displaystyle Q_{\Delta}({\bf z};I,b)-Q_{\Delta}({\bf z}^{\prime};I,b)$
$\displaystyle=~{}\ell_{\Delta}(\|z_{ib}-\mu_{i,I_{i}}({\bf
z})\|-\|z_{ib}-\mu_{j,I_{j}}({\bf
z})\|)-\ell_{\Delta}(\|z^{\prime}_{ib}-\mu_{i,I_{i}}({\bf
z}^{\prime})\|-\|z^{\prime}_{ib}-\mu_{j,I_{j}}({\bf z}^{\prime})\|)$
$\displaystyle\leq~{}\Delta^{-1}\left|\|z_{ib}-\mu_{i,I_{i}}({\bf
z})\|-\|z_{ib}-\mu_{j,I_{j}}({\bf z})\|-\|z^{\prime}_{ib}-\mu_{i,I_{i}}({\bf
z}^{\prime})\|+\|z^{\prime}_{ib}-\mu_{j,I_{j}}({\bf z}^{\prime})\|\right|$
$\displaystyle\leq~{}\Delta^{-1}\left(\left|\|z_{ib}-\mu_{i,I_{i}}({\bf
z})\|-\|z^{\prime}_{ib}-\mu_{i,I_{i}}({\bf
z}^{\prime})\|\right|+\left|\|z_{ib}-\mu_{j,I_{j}}({\bf
z})\|-\|z^{\prime}_{ib}-\mu_{j,I_{j}}({\bf z}^{\prime})\|\right|\right)$
$\displaystyle\leq~{}\Delta^{-1}\left(\|z_{ib}-z^{\prime}_{ib}\|+\|\mu_{i,I_{i}}({\bf
z})-\mu_{i,I_{i}}({\bf
z}^{\prime})\|+\|z_{ib}-z^{\prime}_{ib}\|+\|\mu_{j,I_{j}}({\bf
z})-\mu_{j,I_{j}}({\bf z}^{\prime})\|\right)$
$\displaystyle=~{}\Delta^{-1}\left(2\|z_{ib}-z^{\prime}_{ib}\|+\|\mu_{i,I_{i}}({\bf
z})-\mu_{i,I_{i}}({\bf z}^{\prime})\|+\|\mu_{j,I_{j}}({\bf
z})-\mu_{j,I_{j}}({\bf z}^{\prime})\|\right)$
$\displaystyle=~{}\frac{\|z_{it}-z^{\prime}_{it}\|}{\Delta}\left(2\mathbb{I}[b=t]+\frac{\mathbb{I}[t\in
I_{i}]}{n}\right)+\frac{\|z_{jt}-z^{\prime}_{jt}\|\cdot\mathbb{I}[t\in
I_{j}]}{\Delta n}$ (40)
$\displaystyle\leq~{}\frac{\|(z_{it},z_{jt})-(z^{\prime}_{it},z^{\prime}_{jt})\|}{\Delta}\left(2\mathbb{I}[b=t]+\frac{\mathbb{I}[t\in
I_{i}]}{n}+\frac{\mathbb{I}[t\in I_{j}]}{n}\right),$ (41)

Now trivially

$\displaystyle\operatorname{Avg}_{b,I}\Big{[}\mathbb{I}[b=t]\Big{]}$
$\displaystyle=\operatorname{Avg}_{b}\Big{[}\mathbb{I}[b=t]\Big{]}=\frac{1}{m},$
(42)

and for $r\in\\{i,j\\}$,

$\displaystyle\operatorname{Avg}_{b,I}\Big{[}\mathbb{I}[t\in I_{r}]\Big{]}$
$\displaystyle=\operatorname{Avg}_{I_{r}}\Big{[}\mathbb{I}[t\in
I_{r}]\Big{]}=1-\frac{(m-1)^{n}}{m^{n}}\leq\frac{n}{m},$ (43)

where in the last step we used that $(1-{\textstyle\frac{1}{m}})^{n}\geq
1-{\textstyle\frac{n}{m}}$ for $n\leq m$.

Combining with (39) and (41) implies
$\frac{D^{t}_{(z^{\prime}_{it},z^{\prime}_{jt})}B_{\Delta}({\bf
z})}{\|(z_{it},z_{jt})-(z^{\prime}_{it},z^{\prime}_{jt})\|}\leq{\textstyle\frac{4}{\Delta
m}}$ and hence

$M(B_{\Delta})=\max_{t\in[m]}\sup_{\begin{subarray}{c}{\bf z}_{i},{\bf
z}_{j}\in\mathcal{F}(\mathcal{X})^{m}\\\
(z^{\prime}_{it},z^{\prime}_{jt})\neq(z_{it},z_{jt})\end{subarray}}\frac{D^{t}_{(z^{\prime}_{it},z^{\prime}_{jt})}B_{\Delta}({\bf
z})}{\|(z_{it},z_{jt})-(z^{\prime}_{it},z^{\prime}_{jt})\|}\leq\frac{4}{\Delta
m}.$ (44)

In addition, since $f\in\mathcal{F}^{\alpha}$, $\|z_{rt}-z^{\prime}_{rt}\|\leq
2\sup_{x\in\mathcal{X}}\|f(x)\|\leq 2\alpha B$ for any $r\in\\{i,j\\}$, (39),
(40), (42), and (43) imply which gives

$K(B_{\Delta})=\max_{t\in[m]}\sup_{\begin{subarray}{c}{\bf z}_{i},{\bf
z}_{j}\in\mathcal{F}(\mathcal{X})^{m}\\\
(z^{\prime}_{it},z^{\prime}_{jt})\neq(z_{it},z_{jt})\end{subarray}}D^{t}_{(z^{\prime}_{it},z^{\prime}_{jt})}B_{\Delta}({\bf
z})\leq\frac{8\alpha B}{\Delta m}.$ (45)

#### Bounding $J(B_{\Delta})$.

Consider $t_{1}\neq t_{2}\in[m]$ and for $r\in\\{i,j\\}$, let ${\bf
z}_{r}=(z_{r1},\dots,z_{rm})$, ${\bf
z}^{\prime}_{r}=(z^{\prime}_{r1},\dots,z^{\prime}_{rm})$ where
$z^{\prime}_{rb}=z_{rb}$ for all $b\neq t_{1}$, and ${\bf
z}^{\prime\prime}_{r}=(z^{\prime\prime}_{r1},\dots,z^{\prime\prime}_{rm})$
where $z^{\prime\prime}_{rb}=z^{\prime}_{rb}$ for all $b\neq t_{2}$. Finally,
let $\bar{{\bf z}}_{r}=(\bar{z}_{r1},\dots,\bar{z}_{rm})$ where
$\bar{z}_{rb}=z_{rb}$ for all $b\neq t_{2}$ and
$\bar{z}_{rt_{2}}=z^{\prime\prime}_{rt_{2}}$. Then it is easy to see that

$\displaystyle
D^{t_{2}}_{(z^{\prime\prime}_{it_{2}},z^{\prime\prime}_{jt_{2}})}D^{t_{1}}_{(z^{\prime}_{it_{2}},z^{\prime}_{jt_{2}})}B_{\Delta}({\bf
z}_{i},{\bf z}_{j})$ $\displaystyle=~{}B_{\Delta}({\bf z}_{i},{\bf
z}_{j})-B_{\Delta}({\bf z}^{\prime}_{i},{\bf z}^{\prime}_{j})+B_{\Delta}({\bf
z}^{\prime\prime}_{i},{\bf z}^{\prime\prime}_{j})-B_{\Delta}(\bar{{\bf
z}}_{i},\bar{{\bf z}}_{j})$
$\displaystyle=~{}\operatorname{Avg}_{b,I}\left[Q_{\Delta}({\bf
z};I,b)-Q_{\Delta}({\bf z}^{\prime};I,b)+Q_{\Delta}({\bf
z}^{\prime\prime};I,b)-Q_{\Delta}(\bar{{\bf z}};I,b)\right]$ (46)

Now consider the terms inside the average. First notice that the first and
second, and respectively the third and fourth terms only differ in the
$t_{1}$th coordinate of the variables, that is, the differences are nonzero
only if $b=t_{1}$ or $t_{1}\in I_{i}\cup I_{j}$. Similarly, the first and
fourth, respectively the second and third terms differ in the $t_{2}$th
coordinate, so again their difference is nonzero only if $b=t_{2}$ or
$t_{2}\in I_{i}\cup I_{j}$. Therefore,

$\displaystyle Q_{\Delta}({\bf z};I,b)-Q_{\Delta}({\bf
z}^{\prime};I,b)+Q_{\Delta}({\bf z}^{\prime\prime};I,b)-Q_{\Delta}(\bar{{\bf
z}};I,b)$ $\displaystyle=~{}\left(Q_{\Delta}({\bf z};I,b)-Q_{\Delta}({\bf
z}^{\prime};I,b)+Q_{\Delta}({\bf z}^{\prime\prime};I,b)-Q_{\Delta}(\bar{{\bf
z}};I,b)\right)$
$\displaystyle\qquad\times\left(\mathbb{I}[b=t_{1}]+\mathbb{I}[t_{1}\in
I_{i}\cup I_{j}]\right)\cdot\left(\mathbb{I}[b=t_{2}]+\mathbb{I}[t_{2}\in
I_{i}\cup I_{j}]\right)$

Similarly to (41), we obtain that

$\displaystyle Q_{\Delta}({\bf z};I,b)-Q_{\Delta}({\bf z}^{\prime};I,b)$
$\displaystyle\leq~{}\frac{\|(z_{it_{1}},z_{jt_{1}})-(z^{\prime}_{it_{1}},z^{\prime}_{jt_{1}})\|}{\Delta}\bigg{(}2\mathbb{I}[b=t_{1}]+\frac{\mathbb{I}[t_{1}\in
I_{i}]}{n}+\frac{\mathbb{I}[t_{1}\in
I_{j}]}{n}\bigg{)}\Big{(}\mathbb{I}[b=t_{2}]+\mathbb{I}[t_{2}\in I_{i}\cup
I_{j}]\Big{)}$
$\displaystyle\leq~{}\frac{\|(z_{it_{1}},z_{jt_{1}})-(z^{\prime}_{it_{1}},z^{\prime}_{jt_{1}})\|}{\Delta}\bigg{(}2\mathbb{I}[b=t_{1}]\big{(}\mathbb{I}[t_{2}\in
I_{i}]+\mathbb{I}[t_{2}\in
I_{j}]\big{)}+\mathbb{I}[b=t_{2}]\frac{\mathbb{I}[t_{1}\in
I_{i}]+\mathbb{I}[t_{1}\in I_{j}]}{n}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\big{(}\mathbb{I}[t_{2}\in
I_{i}]+\mathbb{I}[t_{2}\in I_{j}]\big{)}\frac{\mathbb{I}[t_{1}\in
I_{i}]+\mathbb{I}[t_{1}\in I_{j}]}{n}\bigg{)},$

where in the last step we used that $t_{1}\neq t_{2}$ and hence
$\mathbb{I}[b=t_{1}]\mathbb{I}[b=t_{2}]=0$. As in (42) and (43), for
$v\in\\{1,2\\}$ and $r\in\\{i,j\\}$

$\displaystyle\operatorname{Avg}_{b,I}\Big{[}\mathbb{I}[b=t_{v}]\Big{]}=\frac{1}{m}\quad\text{and}\quad\operatorname{Avg}_{b,I}\Big{[}\mathbb{I}[t_{v}\in
I_{r}]\Big{]}\leq\frac{n}{m}.$

Finally,

$\displaystyle\operatorname{Avg}_{b,I}\Big{[}\mathbb{I}[t_{1}\in
I_{r}]\mathbb{I}[t_{2}\in
I_{r}]\Big{]}=\operatorname{Avg}_{I_{r}}\Big{[}\mathbb{I}[t_{1},t_{2}\in
I_{r}]\Big{]}$
$\displaystyle=~{}1-\operatorname{Avg}_{I_{r}}\Big{[}\mathbb{I}[t_{1},t_{2}\notin
I_{r}]+\mathbb{I}[t_{1}\in I_{r},t_{2}\notin I_{r}]+\mathbb{I}[t_{1}\notin
I_{r},t_{2}\in I_{r}]\Big{]}$
$\displaystyle=~{}1-\frac{(m-2)^{n}+2((m-1)^{n}-(m-2)^{n})}{m^{n}}\frac{m^{n}-2(m-1)^{n}+(m-2)^{n}}{m^{n}}\leq\frac{2n(n-1)}{m^{2}}$

where the last step holds since

$\displaystyle m^{n}-2(m-1)^{n}+(m-2)^{n}$
$\displaystyle=\int_{m-1}^{m}nu^{n-1}\text{d}u-\int_{m-2}^{m-1}nu^{n-1}\text{d}u\leq
n\left(m^{n-1}-(m-2)^{n-1}\right)$
$\displaystyle=n(n-1)\int_{m-2}^{m}u^{n-2}\text{d}u\leq 2n(n-1)m^{n-2}.$

Therefore, since we can independently average over the different variables
($b,I_{1},I_{2}$), we obtain

$\displaystyle\operatorname{Avg}_{b,I}\Big{[}Q_{\Delta}({\bf
z};I,b)-Q_{\Delta}({\bf z}^{\prime};I,b)\Big{]}$
$\displaystyle\leq\frac{\|(z_{it_{1}},z_{jt_{1}})-(z^{\prime}_{it_{1}},z^{\prime}_{jt_{1}})\|}{\Delta}\left(\frac{2}{m^{2}}+\frac{6n}{m^{2}}+\frac{4n(n-1)}{m^{2}}\right)$

and the same bound holds for $\operatorname{Avg}_{b,I}\Big{[}Q_{\Delta}({\bf
z}^{\prime\prime};I,b)-Q_{\Delta}(\bar{{\bf z}};I,b)\Big{]}$. Substituting
into (46), we obtain

$\displaystyle
D^{t_{2}}_{(z^{\prime\prime}_{it_{2}},z^{\prime\prime}_{jt_{2}})}D^{t_{1}}_{(z^{\prime}_{it_{2}},z^{\prime}_{jt_{2}})}B_{\Delta}({\bf
z}_{i},{\bf z}_{j})$
$\displaystyle\leq\frac{\|(z_{it_{1}},z_{jt_{1}})-(z^{\prime}_{it_{1}},z^{\prime}_{jt_{1}})\|}{\Delta}\left(\frac{2}{m^{2}}+\frac{6n}{m^{2}}+\frac{4n(n-1)}{m^{2}}\right).$