# Generalization Analysis for Contrastive Representation Learning

Yunwen Lei1 Tianbao Yang2 Yiming Ying3111Corresponding author Ding-Xuan Zhou4
1Department of Mathematics, Hong Kong Baptist University
2Department of Computer Science and Engineering, Texas A&M University
3Department of Mathematics and Statistics, State University
of New York at Albany
4School of Mathematics and Statistics, University of Sydney
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Recently, contrastive learning has found impressive success in advancing the
state of the art in solving various machine learning tasks. However, the
existing generalization analysis is very limited or even not meaningful. In
particular, the existing generalization error bounds depend linearly on the
number $k$ of negative examples while it was widely shown in practice that
choosing a large $k$ is necessary to guarantee good generalization of
contrastive learning in downstream tasks. In this paper, we establish novel
generalization bounds for contrastive learning which do not depend on $k$, up
to logarithmic terms. Our analysis uses structural results on empirical
covering numbers and Rademacher complexities to exploit the Lipschitz
continuity of loss functions. For self-bounding Lipschitz loss functions, we
further improve our results by developing optimistic bounds which imply fast
rates in a low noise condition. We apply our results to learning with both
linear representation and nonlinear representation by deep neural networks,
for both of which we derive Rademacher complexity bounds to get improved
generalization bounds.

##  1 Introduction

The performance of machine learning (ML) models often depends largely on the
representation of data, which motivates a resurgence of contrastive
representation learning (CRL) to learn a representation function
$f:\mathcal{X}\mapsto\mathbb{R}^{d}$ from unsupervised data [11, 23, 20]. The
basic idea is to pull together similar pairs $(\mathbf{x},\mathbf{x}^{+})$ and
push apart disimilar pairs $(\mathbf{x},\mathbf{x}^{-})$ in an embedding
space, which can be formulated as minimizing the following objective [11, 32]

$\\!\mathbb{E}_{\mathbf{x},\mathbf{x}^{+},\\{\mathbf{x}_{i}^{-}\\}_{i=1}^{k}}\\!\log\\!\Big{(}1+\sum_{i=1}^{k}\exp\Big{(}-f(\mathbf{x})^{\top}\big{(}f(\mathbf{x}^{+})-f(\mathbf{x}_{i}^{-})\big{)}\\!\Big{)}\\!\Big{)},$

where $k$ is the number of negative examples. The hope is that the learned
representation $f(\mathbf{x})$ would capture the latent structure and be
beneficial to other downstream learning tasks [3, 40]. CRL has achieved
impressive empirical performance in advancing the state-of-the-art performance
in various domains such as computer vision [20, 10, 11, 10] and natural
language processing [8, 15, 33].

The empirical success of CRL motivates a natural question on theoretically
understanding how the learned representation adapts to the downstream tasks,
i.e.,

_How would the generalization behavior of downstream ML models benefit from
the representation function built from positive and negative pairs?
Especially, how would the number of negative examples affect the learning
performance?_

Arora et al. [3] provided an attempt to answer the above questions by
developing a theoretical framework to study CRL. They first gave
generalization bounds for a learned representation function in terms of
Rademacher complexities. Then, they showed that this generalization behavior
measured by an unsupervised loss guarantees the generalization behavior of a
linear classifier in the downstream classification task. However, the
generalization bounds there enjoy a linear dependency on $k$, which would not
be effective if $k$ is large. Moreover, this is not consistent with many
studies which show a large number of negative examples [11, 38, 21, 23] is
necessary for good generalization performance. For example, the work [20] used
$65536$ negative examples in unsupervised visual representation learning, for
which the existing analysis requires $n\geq(65536)^{2}d$ training examples to
get non-vacuous bounds [3]. Therefore, the existing analysis does not fully
answer the question on the super performance of CRL to downstream tasks as
already shown in many applications. Yuan et al. [45] has demonstrated the
benefits using all negative data for each anchor data for CRL and proposed an
efficient algorithms for optimizing global contrastive loss. Therefore, the
existing analysis does not fully answer the question on the super performance
of CRL to downstream tasks as already shown in many applications.

Assumption | Arora et al.’19 | Ours
---|---|---
| $O\Big{(}{k\sqrt{d}\over\sqrt{n}}\Big{)}$ | $\widetilde{O}\Big{(}{\sqrt{d}\over\sqrt{n}}\Big{)}$
low noise | $O\Big{(}{k\sqrt{d}\over\sqrt{n}}\Big{)}$ | $\widetilde{O}\Big{(}{d\over{n}}\Big{)}$
Table 1: Comparison between our generalization bounds and those in Arora et
al. [3] for the logistic loss. Here $d$ is the number of learned features. The
notation $\widetilde{O}$ ignores log factors.

In this paper, we aim to further deepen our understanding of CRL by fully
exploiting the Lipschitz continuity of loss functions. Our contributions are
listed as follows.

1\. We develop generalization error bounds for CRL. We consider three types of
loss functions: $\ell_{2}$-Lipschitz loss, $\ell_{\infty}$-Lipschitz loss and
self-bounding Lipschitz loss. For $\ell_{2}$-Lipschitz loss, we develop a
generalization bound with a square-root dependency on $k$ by two applications
of vector-contraction lemmas on Rademacher complexities, which improves the
existing bound by a factor of $\sqrt{k}$ [3]. For $\ell_{\infty}$-Lipschitz
loss, we develop generalization bounds which does not depend on $k$, up to
some logarithmic terms, by approximating the arguments of loss functions via
expanding the original dataset by a factor of $k$ to fully exploit the
Lipschitz continuity. For self-bounding Lipschitz loss, we develop optimistic
bounds involving the training errors, which can imply fast rates under a low
noise setting. All of our generalization bounds involve Rademacher
complexities of feature classes, which preserve the coupling among different
features.

2\. We then apply our general result to two unsupervised representation
learning problems: learning with linear features and learning with nonlinear
features via deep neural networks (DNNs). For learning with linear features,
we consider two regularization schemes, i.e., $p$-norm regularizer and
Schatten-norm regularizer. For learning with nonlinear features, we develop
Rademacher complexity and generalization bounds with a square-root dependency
on the depth of DNNs. To this aim, we adapt the technique in Golowich et al.
[16] by using a different moment generalization function to capture the
coupling among different features.

3\. Finally, we apply our results on representation learning to the
generalization analysis of downstream classification problems, which
outperforms the existing results by a factor of $k$ (ignoring a log factor).

The remaining parts of the paper are organized as follows. Section 2 reviews
the related work, and Section 3 provides the problem formulation. We give
generalization bounds for CRL in Section 4 for three types of loss functions,
which are then applied to learning with both linear and nonlinear features in
Section 5. Conclusions are given in Section 6.

##  2 Related Work

The most related work is the generalization analysis of CRL in Arora et al.
[3], where the authors developed generalization bounds for unsupervised errors
in terms of Rademacher complexity of representation function classes. Based on
this, they further studied the performance of linear classifiers on the
learned features. In particular, they considered the mean classifier where the
weight for a class label is the mean of the representation of corresponding
inputs. A major result in Arora et al. [3] is to show that the classification
errors of the mean classifier can be bounded by the unsupervised errors of
learned representation functions. This shows that the downstream
classification task can benefit from a learned representation function with a
low unsupervised error.

The above work motivates several interesting theoretical study of CRL. Nozawa
et al. [31] studied CRL in a PAC-Bayesian setting, which aims to learn a
posterior distribution of representation functions. Nozawa et al. [31] derived
PAC-Bayesian bounds for the posterior distribution and applied it to get PAC-
Bayesian bounds for the mean-classifier, which relaxes the i.i.d. assumption.
Negative examples in the framework [3] are typically taken to be randomly
sampled datapoints, which may actually have the same label of the point of
interest. This introduces a bias in the objective function of CRL, which leads
to performance drops in practice. Motivated by this, Chuang et al. [12]
introduced a debiased CRL algorithm by building an approximation of unbiased
error in CRL, and developed generalization guarantees for the downstream
classification.

Several researchers studied CRL from other perspectives. Lee et al. [24]
proposed to learn a representation function $f$ to minimize
$\mathbb{E}_{(X_{1},X_{2})}[\|X_{2}-f(X_{1})\|_{2}^{2}]$, where $X_{1},X_{2}$
are unlabeled input and pretext target. Under an approximate conditional
independency assumption, the authors showed that a linear function based on
the learned representation approximates the ground true predictor on
downstream problems. In a generative modeling setup, Tosh et al. [41] proposed
to learn representation functions by a landmark embedding procedure, which can
reveal the underlying topic posterior information. Tosh et al. [40] studied
CRL in a multi-view setting with two views available for each datum. Under an
assumption on the redundancy between the two views, the authors showed that
low-dimensional representation can achieve near optimal downstream performance
with linear models. HaoChen et al. [19] studied self-supervised learning from
the perspective of spectral clustering based on a population augmentation
graph, and proposed a spectral contrastive loss. They further developed
generalization bounds for both representation learning and the downstream
classification. This result is improved in a recent work by developing a
guarantee to incorporate the representation function class [35]. There are
also recent work on theoretical analysis of representation learning via
gradient-descent dynamics [24, 39], mutual information [42], alignment of
representations [43], and causality [29]. CRL is related to metric learning,
for which generalization bounds have been studied in the literature [9].

##  3 Problem Formulation

Let $\mathcal{X}$ denote the space of all possible datapoints. In CRL, we are
given several _similar_ data in the form of pairs
$(\mathbf{x},\mathbf{x}^{+})$ drawn from a distribution $\mathcal{D}_{sim}$
and _negative_ data
$\mathbf{x}_{1}^{-},\mathbf{x}_{2}^{-},\ldots,\mathbf{x}_{k}^{-}$ drawn from a
distribution $\mathcal{D}_{neg}$ unrelated to $\mathbf{x}$. Our aim is to
learn a feature map $f:\mathcal{X}\mapsto\mathbb{R}^{d}$ from a class of
representation functions $\mathcal{F}=\big{\\{}f:\|f(\cdot)\|_{2}\leq
R\big{\\}}$ for some $R>0$, where $\|\cdot\|_{2}$ denotes the Euclidean norm.
Here $d\in\mathbb{N}$ denotes the number of features.

We follow the framework in Arora et al. [3] to define the distribution
$\mathcal{D}_{sim}$ and the distribution $\mathcal{D}_{neg}$. Let
$\mathcal{C}$ denote the set of all latent classes and for each class
$c\in\mathcal{C}$ we assume there is a probability distribution
$\mathcal{D}_{c}$ over $\mathcal{X}$, which quantifies the relevance of
$\mathbf{x}$ to the class $c$. We assume there is a probability distribution
$\rho$ defined over $\mathcal{C}$. Then we define
$\mathcal{D}_{sim}(\mathbf{x},\mathbf{x}^{+})$ and
$\mathcal{D}_{neg}(\mathbf{x}^{-})$ as follows

$\displaystyle\mathcal{D}_{sim}(\mathbf{x},\mathbf{x}^{+})=\mathbb{E}_{c\sim\rho}\big{[}\mathcal{D}_{c}(\mathbf{x})\mathcal{D}_{c}(\mathbf{x}^{+})\big{]},$
$\displaystyle\mathcal{D}_{neg}(\mathbf{x}^{-})=\mathbb{E}_{c\sim\rho}\big{[}\mathcal{D}_{c}(\mathbf{x}^{-})\big{]}.$

Intuitively, $\mathcal{D}_{sim}(\mathbf{x},\mathbf{x}^{+})$ measures the
probability of $\mathbf{x}$ and $\mathbf{x}^{+}$ being drawn from the same
class $c\sim\rho$, while $\mathcal{D}_{neg}(\mathbf{x}^{-})$ measures the
probability of drawing an un-relevant $\mathbf{x}^{-}$. Let
$(\mathbf{x}_{j},\mathbf{x}_{j}^{+})\sim\mathcal{D}_{sim}$ and
$(\mathbf{x}_{j1}^{-},\ldots,\mathbf{x}_{jk}^{-})\sim\mathcal{D}_{neg},j\in[n]:=\\{1,\ldots,n\\}$,
where $k$ denotes the number of negative examples. We collect these training
examples into a dataset

$S=\Big{\\{}(\mathbf{x}_{1},\mathbf{x}_{1}^{+},\mathbf{x}_{11}^{-},\ldots,\mathbf{x}_{1k}^{-}),(\mathbf{x}_{2},\mathbf{x}_{2}^{+},\mathbf{x}_{21}^{-},\ldots,\mathbf{x}_{2k}^{-}),\ldots,(\mathbf{x}_{n},\mathbf{x}_{n}^{+},\mathbf{x}_{n1}^{-},\ldots,\mathbf{x}_{nk}^{-})\Big{\\}}.$
(3.1)

Given a representation function $f$, we can measure its performance by
building a classifier based on this representation and computing the accuracy
of the classifier. To this aim, we define a $(K+1)$-way supervised task
$\mathcal{T}$ consisting of distinct classes
$\\{c_{1},\ldots,c_{K+1}\\}\subseteq\mathcal{C}$. The examples for this
supervised task are drawn by the following process:

We first draw a label $c\in\mathcal{T}=\\{c_{1},\ldots,c_{K+1}\\}$ from a
distribution $\mathcal{D}_{\mathcal{T}}$ over $\mathcal{T}$, after which we
draw an example $\mathbf{x}$ from $\mathcal{D}_{c}$. This defines the
following distribution over labeled pairs $(\mathbf{x},c)$:
$\mathcal{D}_{\mathcal{T}}(\mathbf{x},c)=\mathcal{D}_{c}(\mathbf{x})\mathcal{D}_{\mathcal{T}}(c).$
Since there is a label for each example, we can build a multi-class classifier
$g:\mathcal{X}\mapsto\mathbb{R}^{K+1}$ for $\mathcal{T}$, where
$g_{c}(\mathbf{x})$ measures the “likelihood” of assigning the class label $c$
to the example $\mathbf{x}$. The loss of $g$ on a point
$(\mathbf{x},y)\in\mathcal{X}\times\mathcal{T}$ can be measured by
$\ell_{s}\big{(}\big{\\{}g(\mathbf{x})_{y}-g(\mathbf{x})_{y^{\prime}}\\}_{y^{\prime}\neq
y}\big{)}$, where $\ell_{s}:\mathbb{R}^{K}\mapsto\mathbb{R}^{+}$. We quantify
the performance of a classifier $g$ on the task $\mathcal{T}$ by the
supervised loss. By minimizing the supervised loss, we want to build a
classifier whose component associated to the correct label is largest.

######  Definition 3.1 (Supervised loss).

Let $g:\mathcal{X}\mapsto\mathbb{R}^{K+1}$ be a multi-class classifier. The
supervised loss of $g$ is defined as

$L_{sup}(\mathcal{T},g):=\mathbb{E}_{(\mathbf{x},c)\sim\mathcal{D}_{\mathcal{T}}}\Big{[}\ell_{s}\big{(}\big{\\{}g(\mathbf{x})_{c}-g(\mathbf{x})_{c^{\prime}}\big{\\}}_{c^{\prime}\neq
c}\big{)}\Big{]}.$

For CRL, we often consider $g$ as a linear classifier based on the learned
representation $f$, i.e., $g(\mathbf{x})=Wf(\mathbf{x})$, where
$W\in\mathbb{R}^{(K+1)\times d}$. Then the performance of the representation
function $f(\mathbf{x})$ can be quantified by the accuracy of the best linear
classifier on the representation $f(\mathbf{x})$:

$L_{sup}(\mathcal{T},f)=\min_{W\in\mathbb{R}^{(K+1)\times
d}}L_{sup}(\mathcal{T},Wf).$

To find a good representation $f$ based on unsupervised dataset $S$, we need
to introduce the concept of unsupervised loss functions. Let
$\ell:\mathbb{R}^{k}\mapsto\mathbb{R}_{+}$ be a loss function for which
popular choices include the hinge loss

$\ell(\mathbf{v})=\max\big{\\{}0,1+\max_{i\in[k]}\\{-v_{i}\\}\big{\\}}$ (3.2)

and the logistic loss

$\ell(\mathbf{v})=\log\big{(}1+\sum_{i\in[k]}\exp(-v_{i})\big{)}.$ (3.3)

Let $f(\mathbf{x})^{\top}$ denote the transpose of $f(\mathbf{x})$.

######  Definition 3.2 (Unsupervised error).

The population unsupervised error is defined as

$L_{un}(f):=\mathbb{E}\big{[}\ell\big{(}\big{\\{}f(\mathbf{x})^{\top}(f(\mathbf{x}^{+})-f(\mathbf{x}_{i}^{-}))\big{\\}}_{i=1}^{k}\big{)}\big{]}.$

The empirical unsupervised error with $S$ is defined as

$\hat{L}_{un}(f):=\frac{1}{n}\sum_{j=1}^{n}\ell\big{(}\big{\\{}f(\mathbf{x}_{j})^{\top}(f(\mathbf{x}_{j}^{+})-f(\mathbf{x}_{ji}^{-}))\big{\\}}_{i=1}^{k}\big{)}.$

A natural algorithm is to find among $\mathcal{F}$ the function with the
minimal empirical unsupervised loss, i.e.,
$\hat{f}:=\arg\min_{f\in\mathcal{F}}\hat{L}_{un}(f)$. This function can then
be used for the downstream supervised learning task, e.g., to find a linear
classifier $g(\mathbf{x})=Wf(\mathbf{x})$ indexed by
$W\in\mathbb{R}^{(K+1)\times d}$.

##  4 Generalization Error Bounds

In this paper, we are interested in the performance of $\hat{f}$ on testing,
i.e., how the empirical behavior of $\hat{f}$ on $S$ would generalize well to
testing examples. Specifically, we will control
$L_{un}(\hat{f})-\hat{L}_{un}(\hat{f})$. Since $\hat{f}$ depends on the
dataset $S$, we need to control the uniform deviation between population
unsupervised error and empirical unsupervised error over the function class
$\mathcal{F}$, which depends on the complexity of $\mathcal{F}$. In this
paper, we will use Rademacher complexity to quantify the complexity of
$\mathcal{F}$ [6].

######  Definition 4.1 (Rademacher Complexity).

Let $\widetilde{\mathcal{F}}$ be a class of real-valued functions over a space
$\mathcal{Z}$ and
$\widetilde{S}=\\{\mathbf{z}_{i}\\}_{i=1}^{n}\subseteq\mathcal{Z}$. The
_empirical_ Rademacher complexity of $\widetilde{\mathcal{F}}$ with respect to
(w.r.t.) $\widetilde{S}$ is defined as
$\mathfrak{R}_{\widetilde{S}}(\widetilde{\mathcal{F}})=\mathbb{E}_{\bm{\epsilon}}\big{[}\sup_{f\in\widetilde{\mathcal{F}}}\frac{1}{n}\sum_{i\in[n]}\epsilon_{i}f(\mathbf{z}_{i})\big{]},$
where $\bm{\epsilon}=(\epsilon_{i})_{i\in[n]}\sim\\{\pm 1\\}^{n}$ are
independent Rademacher variables. We define the _worst-case_ Rademacher
complexity as
$\mathfrak{R}_{\mathcal{Z},n}(\widetilde{\mathcal{F}})=\sup_{\widetilde{S}\subseteq\mathcal{Z}:|\widetilde{S}|=n}\mathfrak{R}_{\widetilde{S}}(\widetilde{\mathcal{F}}),$
where $|\widetilde{S}|$ is the cardinality of $\widetilde{S}$.

For any $f\in\mathcal{F}$, we introduce
$g_{f}:\mathcal{X}^{k+2}\mapsto\mathbb{R}$ as follows

$g_{f}(\mathbf{x},\mathbf{x}^{+},\mathbf{x}_{1}^{-},\ldots,\mathbf{x}_{k}^{-})=\ell\big{(}\big{\\{}f(\mathbf{x})^{\top}\big{(}f(\mathbf{x}^{+})-f(\mathbf{x}_{i}^{-})\big{)}\big{\\}}_{i=1}^{k}\big{)}.$

It is then clear that

$L_{un}(f)\\!-\\!\hat{L}_{un}(f)=\mathbb{E}_{\mathbf{x},\mathbf{x}^{+},\mathbf{x}_{1}^{-},\ldots,\mathbf{x}_{k}^{-}}\big{[}g_{f}(\mathbf{x},\mathbf{x}^{+},\mathbf{x}_{1}^{-},\ldots,\mathbf{x}_{k}^{-})\big{]}-\frac{1}{n}\sum_{j\in[n]}g_{f}(\mathbf{x}_{j},\mathbf{x}_{j}^{+},\mathbf{x}_{j1}^{-},\ldots,\mathbf{x}_{jk}^{-}).$

Results in learning theory show that we can bound
$L_{un}(\hat{f})-\hat{L}_{un}(\hat{f})$ by $\mathfrak{R}_{S}(\mathcal{G})$
[6], where

$\mathcal{G}=\big{\\{}(\mathbf{x},\mathbf{x}^{+},\mathbf{x}_{1}^{-},\ldots,\mathbf{x}_{k}^{-})\mapsto
g_{f}(\mathbf{x},\mathbf{x}^{+},\mathbf{x}_{1}^{-},\ldots,\mathbf{x}_{k}^{-}):f\in\mathcal{F}\big{\\}}.$

Note functions in $\mathcal{G}$ involve the nonlinear function
$\ell:\mathbb{R}^{k}\mapsto\mathbb{R}_{+}$, which introduces difficulties in
the complexity analysis. Our key idea is to use the Lipschitz continuity of
$\ell$ to reduce the complexity of $\mathcal{G}$ to the complexity of another
function class without $\ell$. Since the arguments in $\ell$ are vectors, we
can have different definition of Lipschitz continuity w.r.t. different norms
[25, 37, 26, 14]. For any $\mathbf{a}=(a_{1},\ldots,a_{k})\in\mathbb{R}^{k}$
and $p\geq 1$, we define the $\ell_{p}$-norm as
$\|\mathbf{a}\|_{p}=\big{(}\sum_{i=1}^{n}|a_{i}|^{p}\big{)}^{\frac{1}{p}}$.

######  Definition 4.2 (Lipschitz continuity).

We say $\ell:\mathbb{R}^{k}\mapsto\mathbb{R}_{+}$ is $G$-Lipschitz w.r.t. the
$\ell_{p}$-norm iff

$|\ell(\mathbf{a})-\ell(\mathbf{a}^{\prime})|\leq
G\|\mathbf{a}-\mathbf{a}^{\prime}\|_{p},\quad\forall\mathbf{a},\mathbf{a}^{\prime}\in\mathbb{R}^{k}.$

In this paper, we are particularly interested in the Lipschitz continuity
w.r.t. either the $\ell_{2}$-norm or the $\ell_{\infty}$-norm. According to
Proposition F.1, the loss functions defined in Eq. (3.2) and Eq. (3.3) are
$1$-Lipschitz continuous w.r.t. $\|\cdot\|_{\infty}$, and $1$-Lipschitz
continuous w.r.t. $\|\cdot\|_{2}$ [26].

Note each component of the arguments in $\ell$ are of the form
$f(\mathbf{x})^{\top}(f(\mathbf{x}^{+})-f(\mathbf{x}^{-}))$. This motivates
the definition of the following function class

$\mathcal{H}=\Big{\\{}h_{f}(\mathbf{x},\mathbf{x}^{+},\mathbf{x}^{-})=f(\mathbf{x})^{\top}\big{(}f(\mathbf{x}^{+})-f(\mathbf{x}^{-})\big{)}:f\in\mathcal{F}\Big{\\}}.$

As we will see in the analysis, the complexity of $\mathcal{G}$ is closely
related to that of $\mathcal{H}$. Therefore, we first show how to control the
complexity of $\mathcal{H}$. In the following lemma, we provide Rademacher
complexity bounds of $\mathcal{H}$ w.r.t. a general dataset $S^{\prime}$ of
cardinality $n$. We will use a vector-contraction lemma to prove it [28]. The
basic idea is to notice the Lipschitz continuity of the map
$(\mathbf{x},\mathbf{x}^{+},\mathbf{x}^{-})\mapsto\mathbf{x}^{\top}(\mathbf{x}^{+}-\mathbf{x}^{-})$
w.r.t. $\|\cdot\|_{2}$ on $\mathcal{X}^{3}$. The proof is given in Section A.

######  Lemma 4.3.

Let $n\in\mathbb{N}$ and
$S^{\prime}=\\{(\mathbf{x}_{j},\mathbf{x}_{j}^{+},\mathbf{x}_{j}^{-}):j\in[n]\\}$.
Assume $\|f(\mathbf{x})\|_{2}\leq R$ for any $f\in\mathcal{F}$ and
$\mathbf{x}\in S^{\prime}$. Then

$\mathfrak{R}_{S^{\prime}}(\mathcal{H})\leq\frac{\sqrt{12}R}{n}\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}\times\\{\pm 1\\}^{d}\times\\{\pm 1\\}^{3}}\\\
\Big{[}\sup_{f\in\mathcal{F}}\sum_{j\in[n]}\sum_{t\in[d]}\Big{(}\epsilon_{j,t,1}f_{t}(\mathbf{x}_{j})+\epsilon_{j,t,2}f_{t}(\mathbf{x}_{j}^{+})+\epsilon_{j,t,3}f_{t}(\mathbf{x}_{j}^{-})\Big{)}\Big{]},$

where $f_{t}(\mathbf{x})$ is the $t$-th component of
$f(\mathbf{x})\in\mathbb{R}^{d}$.

######  Remark 4.4.

We compare Lemma 4.3 with the following Rademacher complexity bound in HaoChen
et al. [19]

$\mathbb{E}_{\bf{\epsilon}\sim\\{\pm\\}^{n}}\Big{[}\sup_{f\in\mathcal{F}}\sum_{j\in[n]}\epsilon_{j}f(\mathbf{x}_{j})^{\top}f(\mathbf{x}_{j}^{+})\Big{]}\leq\\\
d\max_{t\in[d]}\mathbb{E}_{\bf{\epsilon}\sim\\{\pm\\}^{n}}\Big{[}\sup_{f_{t}\in\mathcal{F}_{t}}\sum_{j\in[n]}\epsilon_{j}f_{t}(\mathbf{x}_{j})f_{t}(\mathbf{x}_{j}^{+})\Big{]},$
(4.1)

where $\mathcal{F}_{t}=\big{\\{}\mathbf{x}\mapsto
f_{t}(\mathbf{x}):f\in\mathcal{F}\big{\\}}.$ As a comparison, our analysis in
Lemma 4.3 can imply the following bound

$\mathbb{E}_{\bf{\epsilon}\sim\\{\pm\\}^{n}}\Big{[}\sup_{f\in\mathcal{F}}\sum_{j\in[n]}\epsilon_{j}f(\mathbf{x}_{j})^{\top}f(\mathbf{x}_{j}^{+})\Big{]}\leq
2R\mathbb{E}_{\bf{\epsilon}\sim\\{\pm\\}^{2nd}}\Big{[}\sup_{f\in\mathcal{F}}\sum_{j\in[n]}\sum_{t\in[d]}\big{(}\epsilon_{j,t,1}f_{t}(\mathbf{x}_{j})+\epsilon_{j,t,2}f_{t}(\mathbf{x}_{j}^{+})\big{)}\Big{]}.$

Eq. (4.1) decouples the relationship among different features since the
maximization over $t\in[d]$ is outside of the expectation operator. As a
comparison, our result preserves this coupling since the summation over
$t\in[d]$ is inside the supermum over $f\in\mathcal{F}$. This preservation of
coupling has an effect on the bound. Indeed, it is expected that

$\mathbb{E}_{\bf{\epsilon}\sim\\{\pm\\}^{2nd}}\Big{[}\sup_{f\in\mathcal{F}}\sum_{j\in[n]}\sum_{t\in[d]}\big{(}\epsilon_{j,t,1}f_{t}(\mathbf{x}_{j})+\epsilon_{j,t,2}f_{t}(\mathbf{x}_{j}^{+})\big{)}\Big{]}=\\\
O\Big{(}\sqrt{d}\mathbb{E}_{\bf{\epsilon}\sim\\{\pm\\}^{2n}}\Big{[}\sup_{f_{t}\in\mathcal{F}_{t}}\sum_{j\in[n]}\big{(}\epsilon_{j,1}f_{t}(\mathbf{x}_{j})+\epsilon_{j,2}f_{t}(\mathbf{x}_{j}^{+})\big{)}\Big{]}\Big{)}.$

In this case, our result implies a bound with a better dependency on $d$ as
compared to Eq. (4.1) (the factor of $d$ in Eq. (4.1) is replaced by
$\sqrt{d}$ here). We can plug our bound into the analysis in HaoChen et al.
[19] to improve their results.

######  Remark 4.5.

Lemma 4.3 requires an assumption $\|f(\mathbf{x})\|_{2}\leq R$. This
assumption can be achieved by adding a projection operator as
$f(\mathbf{x})=\mathcal{P}_{R}(\tilde{f}(\mathbf{x}))$ for
$\tilde{f}\in\mathcal{F}$, where $\mathcal{P}_{R}$ denotes the projection
operator onto the Euclidean ball with radius $R$ around the zero point.
According to the inequality
$\|\mathcal{P}_{R}(\tilde{f}(\mathbf{x}))-\mathcal{P}_{R}(\tilde{f}^{\prime}(\mathbf{x}))\|_{2}\leq\|\tilde{f}(\mathbf{x})-\tilde{f}^{\prime}(\mathbf{x})\|_{2}$,
the arguments in the proof indeed show the following inequality with
$\mathcal{H}=\big{\\{}h_{\tilde{f}}(\mathbf{x},\mathbf{x}^{+},\mathbf{x}^{-})=\mathcal{P}_{R}(\tilde{f}(\mathbf{x}))^{\top}\big{(}\mathcal{P}_{R}(\tilde{f}(\mathbf{x}^{+}))-\mathcal{P}_{R}(\tilde{f}(\mathbf{x}^{-}))\big{)}:\tilde{f}\in\mathcal{F}\big{\\}}$:

$\mathfrak{R}_{S^{\prime}}(\mathcal{H})\leq\frac{\sqrt{12}R}{n}\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{3nd}}\Big{[}\sup_{\tilde{f}\in\mathcal{F}}\sum_{j\in[n]}\sum_{t\in[d]}\Big{(}\epsilon_{j,t,1}\tilde{f}_{t}(\mathbf{x}_{j})+\epsilon_{j,t,2}\tilde{f}_{t}(\mathbf{x}_{j}^{+})+\epsilon_{j,t,3}\tilde{f}_{t}(\mathbf{x}_{j}^{-})\Big{)}\Big{]}.$

That is, we can add a projection operator over $\mathcal{F}$ to remove the
assumption $\|f(\mathbf{x})\|_{2}\leq R$.

Loss | Arora et al.’19 | Ours
---|---|---
$1$-$\ell_{2}$-Lipschitz | $\frac{\sqrt{k}\mathfrak{B}}{n}$ | $\frac{\mathfrak{A}}{n}$
$1$-$\ell_{\infty}$-Lipschitz | $\frac{\sqrt{k}\mathfrak{B}}{n}$ | $\frac{\mathfrak{C}}{n\sqrt{k}}^{*}$
S.B. $1$-Lipschitz |  | $n^{-1}\\!+\\!n^{-2}k^{-1}\mathfrak{C}^{2}\\!+\\!(n^{-\frac{1}{2}}+n^{-1}k^{-\frac{1}{2}}\mathfrak{C})\hat{L}^{\frac{1}{2}}_{un}(f)^{*}$
Table 2: Comparison between our generalization bounds and those in Arora et
al. [3]. The notation ∗ means we ignore log factors. S.B. means self-bounding.
The notations $\mathfrak{A},\mathfrak{B}$ and $\mathfrak{C}$ are defined in
Eq. (4.2), (4.4) and (4.5), which are typically of the same order. Then, our
results improve the bounds in Arora et al. [3] by a factor of $\sqrt{k}$ for
$\ell_{2}$-Lipschitz loss, and by a factor of $k$ for
$\ell_{\infty}$-Lipscthiz loss. For self-bounding loss, we get optimistic
bounds.

###  4.1 $\ell_{2}$ Lipschitz Loss

We first consider $\ell_{2}$ Lipschitz loss. The following theorem to be
proved in Section A gives Rademacher complexity and generalization error
bounds for unsupervised loss function classes. We always assume
$\ell\big{(}\big{\\{}f(\mathbf{x})^{\top}(f(\mathbf{x}^{+})-f(\mathbf{x}_{i}^{-}))\big{\\}}_{i=1}^{k}\big{)}\leq
B$ for any $f\in\mathcal{F}$ in this paper.

######  Theorem 4.6 (Generalization bound: $\ell_{2}$-Lipschitz loss).

Assume $\|f(\mathbf{x})\|_{2}\leq R$ for any $f\in\mathcal{F}$ and
$\mathbf{x}\in\mathcal{X}$. Let $S$ be defined as in Eq. (3.1). If
$\ell:\mathbb{R}^{k}\mapsto\mathbb{R}_{+}$ is $G_{2}$-Lipschitz w.r.t. the
$\ell_{2}$-norm, then
$\mathfrak{R}_{S}(\mathcal{G})\leq\frac{\sqrt{24}RG_{2}\mathfrak{A}}{n},$
where

$\mathfrak{A}=\mathbb{E}_{\bm{\\{}\epsilon\\}\sim\\{\pm
1\\}^{3nkd}}\mathbb{E}\Big{[}\sup_{f\in\mathcal{F}}\sum_{j\in[n]}\sum_{i\in[k]}\sum_{t\in[d]}\Big{(}\epsilon_{j,i,t,1}f_{t}(\mathbf{x}_{j})+\epsilon_{j,i,t,2}f_{t}(\mathbf{x}_{j}^{+})+\epsilon_{j,i,t,3}f_{t}(\mathbf{x}^{-}_{ji})\Big{)}\Big{]}.$
(4.2)

Furthermore, for any $\delta\in(0,1)$, with probability at least $1-\delta$
the following inequality holds for any $f\in\mathcal{F}$

$L_{un}(f)-\hat{L}_{un}(f)\leq\frac{4\sqrt{6}RG_{2}\mathfrak{A}}{n}+3B\sqrt{\frac{\log(2/\delta)}{2n}}.$

######  Remark 4.7.

Under the same Lipschitz continuity w.r.t. $\|\cdot\|_{2}$, the following
bound was established in Arora et al. [3]

$L_{un}(f)=\hat{L}_{un}(f)+O\Big{(}\frac{G_{2}R\sqrt{k}\mathfrak{B}}{n}+B\sqrt{\frac{\log(1/\delta)}{n}}\Big{)},$
(4.3)

where

$\mathfrak{B}=\mathbb{E}_{\bm{\epsilon}\sim\\{\pm 1\\}^{n}\times\\{\pm
1\\}^{d}\times\\{\pm
1\\}^{k+2}}\Big{[}\sup_{f\in\mathcal{F}}\sum_{j\in[n]}\sum_{t\in[d]}\\\
\Big{(}\epsilon_{j,t,k+1}f_{t}(\mathbf{x}_{j})+\epsilon_{j,t,k+2}f_{t}(\mathbf{x}_{j}^{+})+\sum_{i\in[k]}\epsilon_{j,t,k}f_{t}(\mathbf{x}_{ji}^{-})\Big{)}\Big{]}.$
(4.4)

Note $\mathfrak{A}$ and $\mathfrak{B}$ are of the same order. Therefore, it is
clear that our bound in Theorem 4.6 improves the bound in Arora et al. [3] by
a factor of $\sqrt{k}$.

###  4.2 $\ell_{\infty}$ Lipschitz Loss

We now turn to the analysis for the setting with $\ell_{\infty}$ Lipschitz
continuity assumption, which is more challenging. The following theorem
controls the Rademacher complexity of $\mathcal{G}$ w.r.t. the dataset $S$ in
terms of the worst-case Rademacher complexity of $\mathcal{H}$ defined on the
set $S_{\mathcal{H}}$, where

$S_{\mathcal{H}}=\Big{\\{}\underbrace{(\mathbf{x}_{1},\mathbf{x}_{1}^{+},\mathbf{x}^{-}_{11}),(\mathbf{x}_{1},\mathbf{x}_{1}^{+},\mathbf{x}^{-}_{12}),\ldots,(\mathbf{x}_{1},\mathbf{x}_{1}^{+},\mathbf{x}^{-}_{1k})}_{\text{induced
by the first
example}},\underbrace{(\mathbf{x}_{2},\mathbf{x}_{2}^{+},\mathbf{x}^{-}_{21}),(\mathbf{x}_{2},\mathbf{x}_{2}^{+},\mathbf{x}^{-}_{22}),\ldots,(\mathbf{x}_{2},\mathbf{x}_{2}^{+},\mathbf{x}^{-}_{2k})}_{\text{induced
by the second example}},\ldots,\\\
\underbrace{(\mathbf{x}_{n},\mathbf{x}_{n}^{+},\mathbf{x}^{-}_{n1}),(\mathbf{x}_{n},\mathbf{x}_{n}^{+},\mathbf{x}^{-}_{n2}),\ldots,(\mathbf{x}_{n},\mathbf{x}_{n}^{+},\mathbf{x}^{-}_{nk})}_{\text{induced
by the last example}}\Big{\\}}.$

As compared to $\mathcal{G}$, the function class $\mathcal{H}$ removes the
loss function $\ell$ and is easier to handle. Our basic idea is to exploit the
Lipschitz continuity of $\ell$ w.r.t. $\|\cdot\|_{\infty}$: to approximate the
function class $\\{\ell(v_{1}(\mathbf{y}),\ldots,v_{k}(\mathbf{y}))\\}$, it
suffices to approximate each component $v_{j}(\mathbf{y}),j\in[k]$. This
explains why we expand the set $S$ of cardinality $n$ to the set
$S_{\mathcal{H}}$ of cardinality $nk$. The proof is given in Section B.

######  Theorem 4.8 (Complexity bound: $\ell_{\infty}$-Lipschitz loss).

Assume $\|f(\mathbf{x})\|_{2}\leq R$ for any $f\in\mathcal{F}$ and
$\mathbf{x}\in\mathcal{X}$. Let $S$ be defined as in Eq. (3.1). If
$\ell:\mathbb{R}^{k}\mapsto\mathbb{R}_{+}$ is $G$-Lipschitz w.r.t. the
$\ell_{\infty}$-norm, then

$\mathfrak{R}_{S}(\mathcal{G})\leq
24G(R^{2}+1)n^{-\frac{1}{2}}+48G\sqrt{k}\mathfrak{R}_{S_{\mathcal{H}},nk}(\mathcal{H})\times\bigg{(}1+\log(4R^{2}n^{\frac{3}{2}}k)\Big{\lceil}\log_{2}\frac{R^{2}\sqrt{n}}{12}\Big{\rceil}\bigg{)},$

where

$\mathfrak{R}_{S_{\mathcal{H}},nk}(\mathcal{H})=\max\limits_{\big{\\{}(\tilde{\mathbf{x}}_{j},\tilde{\mathbf{x}}_{j}^{+},\tilde{\mathbf{x}}_{j}^{-})\big{\\}}_{j\in[nk]}\subseteq
S_{\mathcal{H}}}\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{nk}}\Big{[}\sup_{h\in\mathcal{H}}\frac{1}{nk}\sum_{j\in[nk]}\epsilon_{j}f(\tilde{\mathbf{x}}_{j})^{\top}(f(\tilde{\mathbf{x}}_{j}^{+})-f(\tilde{\mathbf{x}}_{j}^{-}))\Big{]}.$

Note in $\mathfrak{R}_{S_{\mathcal{H}},nk}(\mathcal{H})$ we restrict the
domain of functions in $\mathcal{H}$ to $S_{\mathcal{H}}$, and allow an
element in $S_{\mathcal{H}}$ to be chosen several times in the above
maximization.

We can use Lemma 4.3 to control
$\mathfrak{R}_{S_{\mathcal{H}},nk}(\mathcal{H})$ in Theorem 4.8, and derive
the following generalization error bound. The proof is given in Section B.

######  Theorem 4.9 (Generalization bound: $\ell_{\infty}$-Lipschitz loss).

Let $\ell:\mathbb{R}^{k}\mapsto\mathbb{R}_{+}$ be $G$-Lipschitz continuous
w.r.t. $\|\cdot\|_{\infty}$. Assume $\|f(\mathbf{x})\|_{2}\leq
R,\delta\in(0,1)$. Then with probability at least $1-\delta$ over $S$ for all
$f\in\mathcal{F}$ we have

$L_{un}(f)\leq\hat{L}_{un}(f)+3B\sqrt{\frac{\log(2/\delta)}{2n}}+48G(R^{2}+1)n^{-\frac{1}{2}}+\frac{96\sqrt{12}GR}{n\sqrt{k}}\bigg{(}1+\log(4R^{2}n^{\frac{3}{2}}k)\Big{\lceil}\log_{2}\frac{R^{2}\sqrt{n}}{12}\Big{\rceil}\bigg{)}\mathfrak{C},$

where

$\mathfrak{C}=\max_{\\{(\tilde{\mathbf{x}}_{j},\tilde{\mathbf{x}}_{j}^{+},\tilde{\mathbf{x}}_{j}^{-})\\}_{j=1}^{nk}\subseteq
S_{\mathcal{H}}}\mathbb{E}_{\bm{\epsilon}\sim\\{\pm 1\\}^{nk}\times\\{\pm
1\\}^{d}\times\\{\pm
1\\}^{3}}\Big{[}\sup_{f\in\mathcal{F}}\sum_{j\in[nk]}\sum_{t\in[d]}\big{(}\epsilon_{j,t,1}f_{t}(\tilde{\mathbf{x}}_{j})+\epsilon_{j,t,2}f_{t}(\tilde{\mathbf{x}}_{j}^{+})+\epsilon_{j,t,3}f_{t}(\tilde{\mathbf{x}}_{j}^{-})\big{)}\Big{]}.$
(4.5)

######  Remark 4.10.

We now compare our bound with Eq. (4.3) developed in Arora et al. [3]. It is
reasonable to assume $\mathfrak{C}$ and $\mathfrak{B}$ are of the same order.
222Indeed, under a typical behavior of Rademacher complexity as
$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm\\}^{n}}\sup_{\bm{a}\in\mathcal{A}\subset\mathbb{R}^{n}}\big{[}\epsilon_{i}a_{i}\big{]}=O(\sqrt{n})$
[6], we have $\mathfrak{C}=O(\sqrt{nkd})$ and $\mathfrak{B}=O(\sqrt{nkd})$.
Then, our bound becomes

$L_{un}(f)=\hat{L}_{un}(f)+O\Big{(}\frac{GR\mathfrak{B}\log^{2}(nRk)}{n\sqrt{k}}+B\sqrt{\frac{\log(1/\delta)}{n}}\Big{)}.$
(4.6)

We know if $\ell$ is $G_{2}$-Lipschitz continuous w.r.t. $\|\cdot\|_{2}$, it
is also $\sqrt{k}G_{2}$-Lipschitz continuous w.r.t. $\|\cdot\|_{\infty}$.
Therefore, in the extreme case we have $G=\sqrt{k}G_{2}$. Even in this extreme
case, our bound is of the order
$L_{un}(f)=\hat{L}_{un}(f)+O\Big{(}\frac{G_{2}R\mathfrak{B}\log^{2}(nRk)}{n}+B\sqrt{\frac{\log(1/\delta)}{n}}\Big{)}$,
which improves Eq. (4.3) by a factor of $\sqrt{k}$ up to a logarithmic factor.
For popular loss functions defined in Eq. (3.2) and Eq. (3.3), we have
$G=G_{2}=1$ and in this case, our bound in Eq. (4.6) improves Eq. (4.3) by a
factor of $k$ if we ignore a logarithmic factor.

###  4.3 Self-bounding Lipschitz Loss

Finally, we consider a self-bounding Lipschitz condition where the Lipschitz
constant depends on the loss function values. This definition was given in
Reeve & Kaban [34].

######  Definition 4.11 (Self-bounding Lipschitz Continuity).

A loss function $\ell:\mathbb{R}^{k}\mapsto\mathbb{R}_{+}$ is said to be
$G_{s}$-self-bounding Lipschitz continuous w.r.t. $\ell_{\infty}$ norm if for
any $\bm{a},\bm{a}^{\prime}\in\mathbb{R}^{k}$

$\big{|}\ell(\bm{a})-\ell(\bm{a}^{\prime})\big{|}\leq
G_{s}\max\big{\\{}\ell(\bm{a}),\ell(\bm{a}^{\prime})\big{\\}}^{\frac{1}{2}}\|\bm{a}-\bm{a}^{\prime}\|_{\infty}.$

It was shown that the logistic loss given in Eq. (3.3) satisfies the self-
bounding Lipschtiz continuity with $G_{s}=2$ [34]. In the following theorem,
we give generalization bounds for learning with self-bounding Lipschitz loss
functions. The basic idea is to replace the Lipschitz constant $G$ in Theorem
4.9 with empirical errors by using the self-bounding property. We use
$\widetilde{O}$ to hide logarithmic factors. The proof is given in Section C.

######  Theorem 4.12 (Generalization bound: self-bounding Lipschitz loss).

Let $\ell:\mathbb{R}^{k}\mapsto\mathbb{R}_{+}$ be $G_{s}$-self-bounding
Lipschitz continuous w.r.t. $\|\cdot\|_{\infty}$. Assume
$\|f(\mathbf{x})\|_{2}\leq R,\delta\in(0,1)$. Then with probability at least
$1-\delta$ over $S$ we have the following inequality uniformly for all
$f\in\mathcal{F}$

$L_{un}(f)=\hat{L}_{un}(f)+\widetilde{O}\Big{(}(B+G_{s}^{2}R^{4})n^{-1}+G_{s}^{2}R^{2}n^{-2}k^{-1}\mathfrak{C}^{2}\Big{)}\\\
+\widetilde{O}\Big{(}(\sqrt{B}+G_{s}R^{2})n^{-\frac{1}{2}}+G_{s}Rn^{-1}k^{-\frac{1}{2}}\mathfrak{C}\Big{)}\hat{L}^{\frac{1}{2}}_{un}(f).$

######  Remark 4.13.

Theorem 4.12 gives optimistic generalization bounds in the sense that the
upper bounds depend on empirical errors [36]. Therefore, the generalization
bounds for $L_{un}(f)-\hat{L}_{un}(f)$ would benefit from low training errors.
In particular, if $\hat{L}^{\frac{1}{2}}_{un}(f)=0$, Theorem 4.12 implies
generalization bounds

$L_{un}(f)=\hat{L}_{un}(f)\\!+\\!\widetilde{O}\Big{(}Bn^{-1}\\!+\\!G_{s}^{2}R^{4}n^{-1}\\!+\\!G_{s}^{2}R^{2}n^{-2}k^{-1}\mathfrak{C}^{2}\Big{)}.$

Typically, we have $\mathfrak{C}=O(\sqrt{nk})$ and in this case
$L_{un}(f)=\hat{L}_{un}(f)+\widetilde{O}\big{(}Bn^{-1}+G_{s}^{2}R^{4}n^{-1}\big{)}$.
In other words, we get fast-decaying error bounds in an interpolating setting.

##  5 Applications

To apply Theorem 4.6 and Theorem 4.9, we need to control the term
$\mathfrak{A}$ or $\mathfrak{C}$, which is related to the Rademacher
complexity of a function class. In this section, we will show how to control
$\mathfrak{C}$ for features of the form $\mathbf{x}\mapsto
U\mathbf{v}(\mathbf{x})$, where $U\in\mathbb{R}^{d\times d^{\prime}}$ is a
matrix and $\mathbf{v}:\mathcal{X}\mapsto\mathbb{R}^{d^{\prime}}$. Here
$\mathbf{v}$ maps the original data $\mathbf{x}\in\mathcal{X}$ to an
intermediate feature in $\mathbb{R}^{d^{\prime}}$, which is used for all the
final features. If $\mathbf{v}$ is the identity map, then we get linear
features. If $\mathbf{v}$ is a neural network, then we get nonlinear features.
For a norm $\|\cdot\|$ on a matrix, we denote by $\|\cdot\|_{*}$ its dual
norm. The following lemmas to be proved in Section D give general results on
Rademacher complexities. Lemma 5.1 gives upper bounds, while Lemma 5.2 gives
lower bounds. It is immediate to extend our analysis to control
$\mathfrak{A}$. For brevity we ignore such a discussion.

######  Lemma 5.1 (Upper bound).

Let $d,d^{\prime}\in\mathbb{N}$. Let $\mathcal{V}$ be a class of functions
from $\mathcal{X}$ to $\mathbb{R}^{d^{\prime}}$. Let
$\mathcal{F}=\\{f(\mathbf{x})=U\mathbf{v}(\mathbf{x}):U\in\mathcal{U},\mathbf{v}\in\mathcal{V}\\}$,
where
$\mathcal{U}=\big{\\{}U=(\mathbf{u}_{1},\ldots,\mathbf{u}_{d})^{\top}\in\mathbb{R}^{d\times
d^{\prime}}:\|U^{\top}\|\leq\Lambda\big{\\}}$ and
$f(\mathbf{x})=U\mathbf{v}(\mathbf{x})=(\mathbf{u}_{1},\ldots,\mathbf{u}_{d})^{\top}\mathbf{v}(\mathbf{x}).$
Then

$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{nd}}\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{j,t}f_{t}(\mathbf{x}_{j})\leq\Lambda\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{nd}}\sup_{\mathbf{v}\in\mathcal{V}}\big{\|}\big{(}\sum_{j\in[n]}\epsilon_{1,j}\mathbf{v}(\mathbf{x}_{j}),\ldots,\sum_{j\in[n]}\epsilon_{d,j}\mathbf{v}(\mathbf{x}_{j})\big{)}\big{\|}_{*}.$

######  Lemma 5.2 (Lower bound).

If $\mathcal{F}$ is symmetric in the sense that $f\in\mathcal{F}$ implies
$-f\in\mathcal{F}$, then we have

$\mathfrak{C}\geq\sqrt{\frac{nk}{2}}\\!\sup\limits_{f\in\mathcal{F}}\max\limits_{(\tilde{\mathbf{x}},\tilde{\mathbf{x}}^{+},\tilde{\mathbf{x}}^{-})\in
S_{\mathcal{H}}}\\!\\!\\!\Big{(}\|f(\tilde{\mathbf{x}})\|_{2}^{2}+\|f(\tilde{\mathbf{x}}^{+})\|_{2}^{2}+\|f(\tilde{\mathbf{x}}^{-})\|_{2}^{2}\Big{)}^{\frac{1}{2}}.$

###  5.1 Linear Features

We first apply Lemma 5.1 to derive Rademacher complexity bounds for learning
with linear features. For any $p\geq 1$ and a matrix
$W=(\mathbf{w}_{1},\ldots,\mathbf{w}_{d^{\prime}})\in\mathbb{R}^{d\times
d^{\prime}}$, the $\ell_{2,p}$ norm of $W$ is defined as
$\|W\|_{2,p}=\big{(}\sum_{i\in[d^{\prime}]}\|\mathbf{w}_{i}\|_{2}^{p}\big{)}^{\frac{1}{p}}$.
If $p=2$, this becomes the Frobenius norm $\|W\|_{F}$. For any $p\geq 1$, the
Schatten-$p$ norm of a matrix $W\in\mathbb{R}^{d\times d^{\prime}}$ is defined
as the $\ell_{p}$-norm of the vector of singular values
$(\sigma_{1}(W),\ldots,\sigma_{\min\\{d,d^{\prime}\\}}(W))^{\top}$ (the
singular values are assumed to be sorted in non-increasing order), i.e.,
$\|W\|_{S_{p}}:=\|\sigma(W)\|_{p}$. Let $p^{*}$ be the number satisfying
$1/p+1/p^{*}=1$. The following proposition to be proved in Section D.1 gives
complexity bounds for learning with linear features.

######  Proposition 5.3 (Linear representation).

Consider the feature map defined in Lemma 5.1 with
$\mathbf{v}(\mathbf{x})=\mathbf{x}$.

  1. (a)

If $\|\cdot\|=\|\cdot\|_{2,p}$, then

$\mathbb{E}_{\bm{\epsilon}}\sup\limits_{f\in\mathcal{F}}\sum\limits_{t\in[d]}\sum\limits_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})\leq\min_{q\geq
p}\Big{\\{}\Lambda
d^{1/q^{*}}\max(\sqrt{q^{*}-1},1)\Big{\\}}\Big{(}\sum_{j\in[n]}\|\mathbf{x}_{j}\|_{2}^{2}\Big{)}^{\frac{1}{2}}.$

  2. (b)

If $\|\cdot\|=\|\cdot\|_{S_{p}}$ with $p\leq 2$, then

$\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})\leq\Lambda
2^{-\frac{1}{4}}\min_{q\in[p,2]}\sqrt{\frac{q^{*}\pi}{e}}\max\Big{\\{}\Big{\|}\Big{(}d\sum_{j\in[n]}\mathbf{x}_{j}\mathbf{x}_{j}^{\top}\Big{)}^{\frac{1}{2}}\Big{\|}_{S_{q^{*}}},d^{1/q^{*}}\Big{(}\sum_{j\in[n]}\|\mathbf{x}_{j}\|_{2}^{2}\Big{)}^{1/2}\Big{\\}}.$

We now plug the above Rademacher complexity bounds into Theorem 4.9 to give
generalization error bounds for learning with unsupervised loss. Let
$B_{x}=\max\\{\|\mathbf{x}_{j}\|_{2},\|\mathbf{x}_{j}^{+}\|_{2},\|\mathbf{x}^{-}_{jt}\|_{2}:j\in[n],t\in[k]\\}$.
Note
$\big{(}\sum_{j\in[nk]}\|\tilde{\mathbf{x}}_{j}\|_{2}^{2}\big{)}^{\frac{1}{2}}\leq\sqrt{nk}B_{x}$
for $\tilde{\mathbf{x}}_{j}$ in the definition of $\mathfrak{C}$, from which
and Proposition 5.3 we get the following bound for the case
$\mathbf{v}(\mathbf{x})=\mathbf{x}$ (the definition of $\mathfrak{C}$ involves
$nk$ examples, while in Proposition 5.3 we consider $n$ examples):

$\mathfrak{C}=O\Big{(}\sqrt{nk}B_{x}\min_{q\geq p}\big{\\{}\Lambda
d^{1/q^{*}}\max(\sqrt{q^{*}-1},1)\big{\\}}\Big{)}.$

The following corollary then follows from Theorem 4.9.

######  Corollary 5.4.

Consider the feature map in Proposition 5.3 with $\|\cdot\|=\|\cdot\|_{2,p}$.
Let $\ell$ be the logistic loss and $\delta\in(0,1)$. Then with probability at
least $1-\delta$ the following inequality holds for all $f\in\mathcal{F}$

$L_{un}(f)-\hat{L}_{un}(f)=\frac{B\log^{\frac{1}{2}}(1/\delta)}{\sqrt{n}}+\widetilde{O}\Big{(}\frac{GRB_{x}\min_{q\geq
p}\big{\\{}\Lambda
d^{1/q^{*}}\max(\sqrt{q^{*}-1},1)\big{\\}}}{\sqrt{n}}\Big{)}.$

It is also possible to give generalization bounds for learning with
$\ell_{2}$-Lipschitz loss functions, and optimistic generalization bounds for
learning with self-bounding Lipschitz loss functions. We omit the discussion
for brevity.

###  5.2 Nonlinear Features

We now consider Rademacher complexity for learning with nonlinear features by
DNNs. The following lemma to be proved in Section D.2 gives Rademacher
complexity bounds for learning with features by DNNs. We say an activation
$\sigma:\mathbb{R}\mapsto\mathbb{R}$ is positive-homogeneous if
$\sigma(ax)=a\sigma(x)$ for $a\geq 0$, contractive if
$|\sigma(x)-\sigma(x^{\prime})|\leq|x-x^{\prime}|$. The ReLU activation
function $\sigma(x)=\max\\{x,0\\}$ is both positive-homogeneous and
contractive.

######  Proposition 5.5 (Nonlinear representation).

Consider the feature map defined in Lemma 5.1 with $\|\cdot\|=\|\cdot\|_{F}$
and

$\mathcal{V}=\Big{\\{}\mathbf{x}\mapsto\mathbf{v}(x)=\sigma\big{(}V_{L}\sigma\big{(}V_{L-1}\cdots\sigma(V_{1}\mathbf{x})\big{)}\big{)}:\|V_{l}\|_{F}\leq
B_{l},\forall l\in[L]\Big{\\}},$

where $\sigma$ is positive-homogeneous, contractive and $\sigma(0)=0$, and $L$
is the number of layers. Then

$\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})\leq\sqrt{d}\Lambda
B_{L}B_{L-1}\cdots B_{1}\bigg{(}16L\big{(}\sum_{1\leq i<j\leq
n}(\mathbf{x}_{i}^{\top}\mathbf{x}_{j})^{2}\big{)}^{\frac{1}{2}}+\sum_{j\in[n]}\|\mathbf{x}_{j}\|_{2}^{2}\bigg{)}^{\frac{1}{2}}.$

######  Remark 5.6.

If $d=1$, the following bound was established in Golowich et al. [16]

$\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{j\in[n]}\epsilon_{j}f_{t}(\mathbf{x}_{j})=O\Big{(}\sqrt{L}\Big{(}\sum_{j\in[n]}\|\mathbf{x}_{j}\|_{2}^{2}\Big{)}^{\frac{1}{2}}\prod_{l\in[L]}B_{l}\Big{)}.$

Proposition 5.5 extends this bound to the general case $d\in\mathbb{N}$. In
particular, if $d=1$, our result matches the result in Golowich et al. [16]
within a constant factor. We need to introduce different techniques to handle
the difficulty in considering the coupling among different features
$\bm{u}_{t}^{\top}\mathbf{v}(x),t\in[d]$, which is reflected by the
regularizer on $U$ as $\|U\|_{F}\leq\Lambda$. Ignoring this coupling would
imply a bound with a crude dependency on $d$. For example, we consider the
moment generation function of
$\sup_{f\in\mathcal{F}}\big{(}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})\big{)}^{2}$,
and then reduce it to the moment generation function of a Rademacher chaos
variable $\sum_{1\leq i<j\leq
n}\epsilon_{i}\epsilon_{j}\mathbf{x}_{i}^{\top}\mathbf{x}_{j}$ by repeated
applications of contraction inequalities of Rademacher complexities. A direct
application of the analysis in Golowich et al. [16] would imply bounds
$\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{j\in[n]}\epsilon_{j}f_{t}(\mathbf{x}_{j})=O\big{(}d\sqrt{L}\big{(}\sum_{j\in[n]}\|\mathbf{x}_{j}\|_{2}^{2}\big{)}^{\frac{1}{2}}\prod_{l\in[L]}B_{l}\big{)}$.
As a comparison, our analysis implies a bound with a square-root dependency on
$d$. We will give more details on the comparison of technical analysis in
Remark D.6.

Note $\big{(}\sum_{1\leq i<j\leq
n}(\mathbf{x}_{i}^{\top}\mathbf{x}_{j})^{2}\big{)}^{\frac{1}{2}}=O\big{(}\sum_{j\in[n]}\|\mathbf{x}_{j}\|_{2}^{2}\big{)}$,
from which and Proposition 5.5 we get for nonlinear features that
$\mathfrak{C}=O\big{(}\sqrt{dL}\Lambda(nk)^{\frac{1}{2}}B_{x}\prod_{l\in[L]}B_{l}\big{)}.$
The following proposition then follows directly from Theorem 4.9.

######  Corollary 5.7.

Consider the feature map in Proposition 5.5. Let $\ell$ be the logistic loss
and $\delta\in(0,1)$. With probability at least $1-\delta$ the following
inequality holds for all $f\in\mathcal{F}$

$L_{un}(f)-\hat{L}_{un}(f)=\widetilde{O}\Big{(}\frac{GR\sqrt{dL}\Lambda
B_{x}\prod_{l\in[L]}B_{l}+B\log^{\frac{1}{2}}\frac{1}{\delta}}{\sqrt{n}}\Big{)}.$

###  5.3 Generalization for Downstream Classification

In this subsection, we apply the above generalization bounds on unsupervised
learning to derive generalization guarantees for a downstream supervised
learning task. Similar ideas can be dated back to metric/similarity learning,
where one shows that similarity-based learning guarantees a good
generalization of the resultant classification [18, 5, 4]. Following Arora et
al. [3], we consider a particular _mean classifier_ with rows being the means
of the representation of each class, i.e., $\mathbf{x}\mapsto
W^{\mu}f(\mathbf{x})$ with the $c$-th row of $W$ being the mean $\mu_{c}$ of
representations of inputs with label $c$:
$\mu_{c}:=\mathbb{E}_{\mathbf{x}\sim\mathcal{D}_{c}}[f(\mathbf{x})]$. Consider
the _average supervised loss_

$L^{\mu}_{sup}(f):=\mathbb{E}_{\\{c_{i}\\}_{i=1}^{K+1}\sim\rho^{K+1}}\big{[}L_{sup}(\\{c_{i}\\}_{i=1}^{K+1},W^{\mu}f)|c_{i}\neq
c_{j}\big{]},$

where we take the expectation over $\mathcal{T}=\\{c_{i}\\}_{i=1}^{K+1}$. The
following lemma shows that the generalization performance of the mean
classifier based on a representation $f$ can be guaranteed in terms of the
generalization performance of the representation in unsupervised learning.

######  Lemma 5.8 (Arora et al. 3).

There exists a function $\rho:\mathcal{C}^{K+1}\mapsto\mathbb{R}_{+}$ such
that the following inequality holds for any $f\in\mathcal{F}$:
$\mathbb{E}_{\mathcal{T}\sim\mathcal{D}}\big{[}\rho(\mathcal{T})L^{\mu}_{sup}(f)\big{]}\leq
L_{un}(f).$

We refer the interested readers to Arora et al. [3] for the expression of
$\rho(\mathcal{T})$, which is independent of $n$. The following corollaries
are immediate applications of Lemma 5.8 and our generalization bounds for
unsupervised learning. We omit the proof for brevity.

######  Corollary 5.9 (Linear representation).

Consider the feature map in Proposition 5.3 with $\|\cdot\|=\|\cdot\|_{2,p}$.
Let $\ell_{s},\ell$ be the logistic loss and $\delta\in(0,1)$. Then with
probability at least $1-\delta$ the following inequality holds

$\mathbb{E}_{\mathcal{T}\sim\mathcal{D}}\Big{[}\rho(\mathcal{T})L^{\mu}_{sup}(\hat{f})\Big{]}=\hat{L}_{un}(\hat{f})+\widetilde{O}\Big{(}\frac{B\log^{\frac{1}{2}}(1/\delta)}{\sqrt{n}}+\frac{GRB_{x}\min_{q\geq
p}\big{\\{}\Lambda
d^{1/q^{*}}\max(\sqrt{q^{*}-1},1)\big{\\}}}{\sqrt{n}}\Big{)}.$

######  Remark 5.10.

If $p\leq(\log d)/(\log d-1)$, we set $q=(\log d)/(\log d-1)$, and get
$d^{1/q^{*}}\max(\sqrt{q^{*}-1},1)=O(\log^{\frac{1}{2}}d)$ ($q^{*}=\log d$).
In this case, we get a bound with a logarithmic dependency on the number of
features. It is possible to extend our discussion to more general norms
$\|\cdot\|=\|\cdot\|_{p,q},p,q\geq 1$ [22].

######  Corollary 5.11 (Nonlinear representation).

Consider the feature map in Proposition 5.5. Let $\ell_{s},\ell$ be the
logistic loss and $\delta\in(0,1)$. With probability at least $1-\delta$ we
have

$\mathbb{E}_{\mathcal{T}\sim\mathcal{D}}\Big{[}\rho(\mathcal{T})L^{\mu}_{sup}(\hat{f})\Big{]}=\hat{L}_{un}(\hat{f})+\widetilde{O}\Big{(}\frac{GR\sqrt{dL}\Lambda
B_{x}\prod_{l\in[L]}B_{l}}{\sqrt{n}}+\frac{B\log^{1/2}(1/\delta)}{\sqrt{n}}\Big{)}.$

######  Remark 5.12.

If we combine our Rademacher complexity bounds in Section 5 and Eq. (4.3)
developed in Arora et al. [3], we would get generalization bounds for
supervised classification with a linear dependency on $k$. If we combine our
complexity bounds and Theorem 4.6, we would get generalization bounds for
supervised classification with a square-root dependency on $k$. These
discussions use the Lipschitz continuity of $\ell$ w.r.t $\|\cdot\|_{2}$. As a
comparison, the use of Lipschitz continuity w.r.t. $\|\cdot\|_{\infty}$ allows
us to derive generalization bounds with a logarithmic dependency on $k$ in
Corollary 5.9 and Corollary 5.11. Furthermore, we can improve the bounds
$\widetilde{O}(1/\sqrt{n})$ in these corollaries to $\widetilde{O}(1/n)$ in an
interpolation setting by applying Theorem 4.12.

##  6 Conclusion

Motivated by the existing generalization bounds with a crude dependency on the
number of negative examples, we present a systematic analysis on the
generalization behavior of CRL. We consider three types of loss functions. Our
results improve the existing bounds by a factor of $\sqrt{k}$ for $\ell_{2}$
Lipschitz loss, and by a factor of $k$ for $\ell_{\infty}$ Lipschitz loss (up
to a log factor). We get optimistic bounds for self-bounding Lipschitz loss,
which imply fast rates under low noise conditions. We justify the
effectiveness of our results with applications to both linear and nonlinear
features.

Our analysis based on Rademacher complexities implies algorithm-independent
bounds. It would be interesting to develop algorithm-dependent bounds to
understand the interaction between optimization and generalization. For
$\ell_{\infty}$ loss, our bound still enjoys a logarithmic dependency on $k$.
It would be interesting to study whether this logarithmic dependency can be
removed in further study.

## References

  * Alon et al. [1997] Alon, N., Ben-David, S., Cesa-Bianchi, N., and Haussler, D.  Scale-sensitive dimensions, uniform convergence, and learnability.  _Journal of the ACM_ , 44(4):615–631, 1997.
  * Anthony & Bartlett [1999] Anthony, M. and Bartlett, P. L.  _Neural network learning: Theoretical foundations_ , volume 9.  1999\.
  * Arora et al. [2019] Arora, S., Khandeparkar, H., Khodak, M., Plevrakis, O., and Saunshi, N.  A theoretical analysis of contrastive unsupervised representation learning.  In _International Conference on Machine Learning_ , pp. 9904–9923, 2019.
  * Balcan & Blum [2006] Balcan, M.-F. and Blum, A.  On a theory of learning with similarity functions.  In _international Conference on Machine Learning_ , pp. 73–80, 2006\.
  * Balcan et al. [2008] Balcan, M.-F., Blum, A., and Srebro, N.  Improved guarantees for learning via similarity functions.  In _Conference on Learning Theory_ , pp. 287–298, 2008.
  * Bartlett & Mendelson [2002] Bartlett, P. and Mendelson, S.  Rademacher and gaussian complexities: Risk bounds and structural results.  _Journal of Machine Learning Research_ , 3:463–482, 2002\.
  * Boucheron et al. [2013] Boucheron, S., Lugosi, G., and Massart, P.  _Concentration Inequalities: A Nonasymptotic Theory of Independence_.  Oxford university press, 2013.
  * Brown et al. [2020] Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Cao et al. [2016] Cao, Q., Guo, Z.-C., and Ying, Y.  Generalization bounds for metric and similarity learning.  _Machine Learning_ , 102(1):115–132, 2016.
  * Caron et al. [2020] Caron, M., Misra, I., Mairal, J., Goyal, P., Bojanowski, P., and Joulin, A.  Unsupervised learning of visual features by contrasting cluster assignments.  _Advances in Neural Information Processing Systems_ , 33:9912–9924, 2020.
  * Chen et al. [2020] Chen, T., Kornblith, S., Norouzi, M., and Hinton, G.  A simple framework for contrastive learning of visual representations.  In _International Conference on Machine Learning_ , pp. 1597–1607. PMLR, 2020.
  * Chuang et al. [2020] Chuang, C.-Y., Robinson, J., Lin, Y.-C., Torralba, A., and Jegelka, S.  Debiased contrastive learning.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 8765–8775, 2020.
  * De la Pena & Giné [2012] De la Pena, V. and Giné, E.  _Decoupling: from dependence to independence_.  Springer Science & Business Media, 2012.
  * Foster & Rakhlin [2019] Foster, D. J. and Rakhlin, A.  $\ell_{\infty}$ vector contraction for rademacher complexity.  _arXiv preprint arXiv:1911.06468_ , 2019.
  * Gao et al. [2021] Gao, T., Yao, X., and Chen, D.  Simcse: Simple contrastive learning of sentence embeddings.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pp. 6894–6910, 2021.
  * Golowich et al. [2018] Golowich, N., Rakhlin, A., and Shamir, O.  Size-independent sample complexity of neural networks.  In _Conference On Learning Theory_ , pp. 297–299. PMLR, 2018.
  * Guermeur [2017] Guermeur, Y.  Lp-norm sauer–shelah lemma for margin multi-category classifiers.  _Journal of Computer and System Sciences_ , 89:450–473, 2017.
  * Guo & Ying [2014] Guo, Z.-C. and Ying, Y.  Guaranteed classification via regularized similarity learning.  _Neural Computation_ , 26(3):497–522, 2014.
  * HaoChen et al. [2021] HaoChen, J. Z., Wei, C., Gaidon, A., and Ma, T.  Provable guarantees for self-supervised deep learning with spectral contrastive loss.  _Advances in Neural Information Processing Systems_ , 34:5000–5011, 2021.
  * He et al. [2020] He, K., Fan, H., Wu, Y., Xie, S., and Girshick, R.  Momentum contrast for unsupervised visual representation learning.  In _Computer Vision and Pattern Recognition_ , pp. 9729–9738, 2020\.
  * Hénaff et al. [2020] Hénaff, O. J., Srinivas, A., De Fauw, J., Razavi, A., Doersch, C., Eslami, S. A., and Van Den Oord, A.  Data-efficient image recognition with contrastive predictive coding.  In _International Conference on Machine Learning_ , pp. 4182–4192, 2020.
  * Kakade et al. [2012] Kakade, S. M., Shalev-Shwartz, S., and Tewari, A.  Regularization techniques for learning with matrices.  _Journal of Machine Learning Research_ , 13:1865–1890, 2012\.
  * Khosla et al. [2020] Khosla, P., Teterwak, P., Wang, C., Sarna, A., Tian, Y., Isola, P., Maschinot, A., Liu, C., and Krishnan, D.  Supervised contrastive learning.  _Advances in Neural Information Processing Systems_ , 33:18661–18673, 2020.
  * Lee et al. [2021] Lee, J. D., Lei, Q., Saunshi, N., and Zhuo, J.  Predicting what you already know helps: Provable self-supervised learning.  _Advances in Neural Information Processing Systems_ , 34:309–323, 2021.
  * Lei et al. [2015] Lei, Y., Dogan, U., Binder, A., and Kloft, M.  Multi-class svms: From tighter data-dependent generalization bounds to novel algorithms.  In _Advances in Neural Information Processing Systems_ , pp. 2026–2034, 2015.
  * Lei et al. [2019] Lei, Y., Dogan, Ü., Zhou, D.-X., and Kloft, M.  Data-dependent generalization bounds for multi-class classification.  _IEEE Transactions on Information Theory_ , 65(5):2995–3021, 2019.
  * Lust-Piquard & Pisier [1991] Lust-Piquard, F. and Pisier, G.  Non commutative khintchine and paley inequalities.  _Arkiv för Matematik_ , 29(1):241–260, 1991\.
  * Maurer [2016] Maurer, A.  A vector-contraction inequality for rademacher complexities.  In _International Conference on Algorithmic Learning Theory_ , pp. 3–17, 2016.
  * Mitrovic et al. [2020] Mitrovic, J., McWilliams, B., Walker, J., Buesing, L., and Blundell, C.  Representation learning via invariant causal mechanisms.  _arXiv preprint arXiv:2010.07922_ , 2020.
  * Mohri et al. [2012] Mohri, M., Rostamizadeh, A., and Talwalkar, A.  _Foundations of Machine Learning_.  MIT press, 2012.
  * Nozawa et al. [2020] Nozawa, K., Germain, P., and Guedj, B.  PAC-bayesian contrastive unsupervised representation learning.  In _Uncertainty in Artificial Intelligence_ , pp. 21–30. PMLR, 2020\.
  * Oord et al. [2018] Oord, A. v. d., Li, Y., and Vinyals, O.  Representation learning with contrastive predictive coding.  _arXiv preprint arXiv:1807.03748_ , 2018.
  * Radford et al. [2021] Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., et al.  Learning transferable visual models from natural language supervision.  In _International Conference on Machine Learning_ , pp. 8748–8763. PMLR, 2021.
  * Reeve & Kaban [2020] Reeve, H. and Kaban, A.  Optimistic bounds for multi-output learning.  In _International Conference on Machine Learning_ , pp. 8030–8040. PMLR, 2020.
  * Saunshi et al. [2022] Saunshi, N., Ash, J., Goel, S., Misra, D., Zhang, C., Arora, S., Kakade, S., and Krishnamurthy, A.  Understanding contrastive learning requires incorporating inductive biases.  In _International Conference on Machine Learning_ , volume 162, pp. 19250–19286, 2022.
  * Srebro et al. [2010] Srebro, N., Sridharan, K., and Tewari, A.  Smoothness, low noise and fast rates.  In _Advances in Neural Information Processing Systems_ , pp. 2199–2207, 2010.
  * Tewari & Chaudhuri [2015] Tewari, A. and Chaudhuri, S.  Generalization error bounds for learning to rank: Does the length of document lists matter?  In _International Conference on Machine Learning_ , pp. 315–323. PMLR, 2015.
  * Tian et al. [2020a] Tian, Y., Krishnan, D., and Isola, P.  Contrastive multiview coding.  In _European Conference on Computer Vision_ , pp. 776–794. Springer, 2020a.
  * Tian et al. [2020b] Tian, Y., Yu, L., Chen, X., and Ganguli, S.  Understanding self-supervised learning with dual deep networks.  _arXiv preprint arXiv:2010.00578_ , 2020b.
  * Tosh et al. [2021a] Tosh, C., Krishnamurthy, A., and Hsu, D.  Contrastive learning, multi-view redundancy, and linear models.  In _Algorithmic Learning Theory_ , pp. 1179–1206. PMLR, 2021a.
  * Tosh et al. [2021b] Tosh, C., Krishnamurthy, A., and Hsu, D.  Contrastive estimation reveals topic posterior information to linear models.  _Journal of Machine Learning Research_ , 22:281–1, 2021b.
  * Tsai et al. [2020] Tsai, Y.-H. H., Wu, Y., Salakhutdinov, R., and Morency, L.-P.  Demystifying self-supervised learning: An information-theoretical framework.  _arXiv preprint arXiv:2006.05576_ , 2, 2020.
  * Wang & Isola [2020] Wang, T. and Isola, P.  Understanding contrastive representation learning through alignment and uniformity on the hypersphere.  In _International Conference on Machine Learning_ , pp. 9929–9939. PMLR, 2020.
  * Ying & Campbell [2010] Ying, Y. and Campbell, C.  Rademacher chaos complexities for learning the kernel problem.  _Neural computation_ , 22(11):2858–2886, 2010\.
  * Yuan et al. [2022] Yuan, Z., Wu, Y., Qiu, Z., Du, X., Zhang, L., Zhou, D., and Yang, T.  Provable stochastic optimization for global contrastive learning: Small batch does not harm performance.  In _Proceedings of International Conference of Machine Learning_ , 2022.
  * Zhou [2002] Zhou, D.-X.  The covering number in learning theory.  _Journal of Complexity_ , 18(3):739–767, 2002\.

##  Appendix A Proof of Theorem 4.6

To prove Theorem 4.6, we first prove Lemma 4.3 by the following vector-
contraction lemma on Rademacher complexities.

######  Lemma A.1 (Maurer 28).

Let $S=\\{\mathbf{z}_{j}\\}_{j=1}^{n}\in\mathcal{Z}^{n}$. Let
$\mathcal{F}^{\prime}$ be a class of functions
$f^{\prime}:\mathcal{Z}\mapsto\mathbb{R}^{d}$ and
$h:\mathbb{R}^{d}\mapsto\mathbb{R}$ be $G$-Lipschitz w.r.t. $\ell_{2}$-norm.
Then

$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\Big{[}\sup_{f^{\prime}\in\mathcal{F}^{\prime}}\sum_{j\in[n]}\epsilon_{j}(h\circ
f^{\prime})(\mathbf{z}_{j})\Big{]}\leq\sqrt{2}G\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{nd}}\Big{[}\sup_{f^{\prime}\in\mathcal{F}^{\prime}}\sum_{j\in[n]}\sum_{t\in[d]}\epsilon_{j,t}f^{\prime}_{t}(\mathbf{z}_{j})\Big{]}.$

In Section E, we will provide an extension of the above lemma.

###### Proof of Lemma 4.3.

Let $f^{\prime}:\mathcal{X}^{3}\mapsto\mathbb{R}^{3d}$ be defined as

$f^{\prime}(\mathbf{x},\mathbf{x}^{+},\mathbf{x}^{-})=\big{(}f(\mathbf{x}),f(\mathbf{x}^{+}),f(\mathbf{x}^{-})\big{)}\in\mathbb{R}^{3d}$

and $h:\mathbb{R}^{3d}\mapsto\mathbb{R}$ be defined as

$h(\mathbf{y},\mathbf{y}^{+},\mathbf{y}^{-})=\mathbf{y}^{\top}(\mathbf{y}^{+}-\mathbf{y}^{-}),\quad\mathbf{y},\mathbf{y}^{+},\mathbf{y}^{-}\in\mathbb{R}^{d}.$

Then it is clear that

$f(\mathbf{x})^{\top}(f(\mathbf{x}^{+})-f(\mathbf{x}^{-}))=h\circ
f^{\prime}(\mathbf{x},\mathbf{x}^{+},\mathbf{x}^{-}).$

Furthermore, for any
$\mathbf{y}_{1},\mathbf{y}^{+}_{1},\mathbf{y}^{-}_{1},\mathbf{y}_{2},\mathbf{y}^{+}_{2},\mathbf{y}^{-}_{2}$
with Euclidean norm less than or equal to $R$, we have

$\displaystyle
h(\mathbf{y}_{1},\mathbf{y}_{1}^{+},\mathbf{y}_{1}^{-})-h(\mathbf{y}_{2},\mathbf{y}_{2}^{+},\mathbf{y}_{2}^{-})=\mathbf{y}_{1}^{\top}(\mathbf{y}_{1}^{+}-\mathbf{y}_{1}^{-})-\mathbf{y}_{2}^{\top}(\mathbf{y}_{2}^{+}-\mathbf{y}_{2}^{-})$
$\displaystyle=\mathbf{y}_{1}^{\top}(\mathbf{y}_{1}^{+}-\mathbf{y}_{1}^{-})-\mathbf{y}_{1}^{\top}(\mathbf{y}_{2}^{+}-\mathbf{y}_{2}^{-})+\mathbf{y}_{1}^{\top}(\mathbf{y}_{2}^{+}-\mathbf{y}_{2}^{-})-\mathbf{y}_{2}^{\top}(\mathbf{y}_{2}^{+}-\mathbf{y}_{2}^{-})$
$\displaystyle=\mathbf{y}_{1}^{\top}(\mathbf{y}_{1}^{+}-\mathbf{y}_{1}^{-}-\mathbf{y}_{2}^{+}+\mathbf{y}_{2}^{-})+(\mathbf{y}_{1}-\mathbf{y}_{2})^{\top}(\mathbf{y}_{2}^{+}-\mathbf{y}_{2}^{-}).$

It then follows from the elementary inequality
$(a+b)^{2}\leq(1+p)a^{2}+(1+1/p)b^{2}$ that

$\big{|}h(\mathbf{y}_{1},\mathbf{y}_{1}^{+},\mathbf{y}_{1}^{-})-h(\mathbf{y}_{2},\mathbf{y}_{2}^{+},\mathbf{y}_{2}^{-})\big{|}^{2}\leq\\\
2(1+p)\|\mathbf{y}_{1}\|^{2}\|\mathbf{y}_{1}^{+}-\mathbf{y}_{2}^{+}\|^{2}+2(1+p)\|\mathbf{y}_{1}\|^{2}\|\mathbf{y}_{1}^{-}-\mathbf{y}_{2}^{-}\|_{2}^{2}+(1+1/p)\|\mathbf{y}_{2}^{+}-\mathbf{y}_{2}^{-}\|_{2}^{2}\|\mathbf{y}_{1}-\mathbf{y}_{2}\|_{2}^{2}.$

We can choose $p=2$ and get

$\displaystyle\big{|}h(\mathbf{y}_{1},\mathbf{y}_{1}^{+},\mathbf{y}_{1}^{-})-h(\mathbf{y}_{2},\mathbf{y}_{2}^{+},\mathbf{y}_{2}^{-})\big{|}^{2}$
$\displaystyle\leq
6R^{2}\big{(}\|\mathbf{y}_{1}^{+}-\mathbf{y}_{2}^{+}\|^{2}+\|\mathbf{y}_{1}^{-}-\mathbf{y}_{2}^{-}\|_{2}^{2}+\|\mathbf{y}_{1}-\mathbf{y}_{2}\|_{2}^{2}\big{)}$
$\displaystyle=6R^{2}\|(\mathbf{y}_{1},\mathbf{y}_{1}^{+},\mathbf{y}_{1}^{-})-(\mathbf{y}_{2},\mathbf{y}_{2}^{+},\mathbf{y}_{2}^{-})\|_{2}^{2}.$

This shows that $h$ is $\sqrt{6}R$-Lipschitz continuous w.r.t.
$\|\cdot\|_{2}$. We can apply Lemma A.1 to derive

$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\Big{[}\sup_{f^{\prime}\in\mathcal{F}^{\prime}}\sum_{j\in[n]}\epsilon_{j}(h\circ
f^{\prime})(\mathbf{z}_{j})\Big{]}\\\
\leq\sqrt{12}R\mathbb{E}_{\bm{\epsilon}\sim\\{\pm 1\\}^{n}\times\\{\pm
1\\}^{d}\times\\{\pm
1\\}^{3}}\Big{[}\sup_{f\in\mathcal{F}}\sum_{j\in[n]}\sum_{t\in[d]}\Big{(}\epsilon_{j,t,1}f_{t}(\mathbf{x}_{j})+\epsilon_{j,t,2}f_{t}(\mathbf{x}_{j}^{+})+\epsilon_{j,t,3}f_{t}(\mathbf{x}_{j}^{-})\Big{)}\Big{]}.$

The proof is completed. ∎

The following standard lemma gives generalization error bounds in terms of
Rademacher complexities.

######  Lemma A.2 (Mohri et al. 30).

Let $\widetilde{\mathcal{G}}$ be a function class and
$\widetilde{S}=\\{\mathbf{z}_{1},\ldots,\mathbf{z}_{n}\\}$. If for any
$g\in\widetilde{\mathcal{G}}$ we have $g(\mathbf{z})\in[0,B]$, then for any
$\delta\in(0,1)$ the following inequality holds with probability (w.r.t.
$\widetilde{S}$) at least $1-\delta$

$\mathbb{E}[g(\mathbf{z})]\leq\frac{1}{n}\sum_{i=1}^{n}g(\mathbf{z}_{i})+2\mathfrak{R}_{\widetilde{S}}(\widetilde{\mathcal{G}})+3B\sqrt{\frac{\log(2/\delta)}{2n}},\quad\forall
g\in\widetilde{\mathcal{G}}.$

###### Proof of Theorem 4.6.

According to the $G_{2}$-Lipschitz continuity of $\ell$ w.r.t. $\ell_{2}$-norm
and Lemma A.1, we have

$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\Big{[}\sup_{f\in\mathcal{F}}\sum_{j\in[n]}\epsilon_{j}\ell\big{(}\big{\\{}f(\mathbf{x}_{j})^{\top}(f(\mathbf{x}_{j}^{+})-f(\mathbf{x}^{-}_{ji}))\big{\\}}_{i\in[k]}\big{)}\Big{]}\\\
\leq\sqrt{2}G_{2}\mathbb{E}_{\bm{\\{}\epsilon\\}\sim\\{\pm
1\\}^{nk}}\mathbb{E}\Big{[}\sup_{f\in\mathcal{F}}\sum_{j\in[n]}\sum_{i\in[k]}\epsilon_{j,i}f(\mathbf{x}_{j})^{\top}(f(\mathbf{x}_{j}^{\top})-f(\mathbf{x}^{-}_{ji}))\Big{]}.$

According to Lemma 4.3, we further get

$\mathbb{E}_{\bm{\\{}\epsilon\\}\sim\\{\pm
1\\}^{nk}}\mathbb{E}\Big{[}\sup_{f\in\mathcal{F}}\sum_{j\in[n]}\sum_{i\in[k]}\epsilon_{j,i}f(\mathbf{x}_{j})^{\top}(f(\mathbf{x}_{j}^{\top})-f(\mathbf{x}^{-}_{ji}))\Big{]}\leq\\\
\sqrt{12}R\mathbb{E}_{\bm{\\{}\epsilon\\}\sim\\{\pm
1\\}^{3nkd}}\mathbb{E}\Big{[}\sup_{f\in\mathcal{F}}\sum_{j\in[n]}\sum_{i\in[k]}\sum_{t\in[d]}\Big{(}\epsilon_{j,i,t,1}f_{t}(\mathbf{x}_{j})+\epsilon_{j,i,t,2}f_{t}(\mathbf{x}_{j}^{+})+\epsilon_{j,i,t,3}f_{t}(\mathbf{x}^{-}_{ji})\Big{)}\Big{]}.$

We can combine the above two inequalities to get the Rademacher complexity
bounds.

We now turn to the generalization bounds. Applying Lemma A.2, with probability
at least $1-\delta$ the following inequality holds with probability at least
$1-\delta$

$L_{un}(f)\leq\hat{L}_{un}(f)+2\mathfrak{R}_{S}(\mathcal{G})+3B\sqrt{\frac{\log(2/\delta)}{2n}},\quad\forall
f\in\mathcal{F}.$

The stated bound on generalization errors then follows by plugging the
Rademacher complexity bounds into the above bound. The proof is completed. ∎

##  Appendix B Proof of Theorem 4.9

We first introduce several complexity measures such as covering numbers and
fat-shattering dimension [1, 2, 46].

######  Definition B.1 (Covering number).

Let
$\widetilde{S}:=\\{\mathbf{z}_{1},\ldots,\mathbf{z}_{n}\\}\in\mathcal{Z}^{n}$.
Let $\widetilde{\mathcal{F}}$ be a class of real-valued functions defined over
a space ${\mathcal{Z}}$. For any $\epsilon>0$ and $p\geq 1$, the empirical
$\ell_{p}$-norm covering number
$\mathcal{N}_{p}(\epsilon,\widetilde{\mathcal{F}},\widetilde{S})$ with respect
to $\widetilde{S}$ is defined as the smallest number $m$ of a collection of
vectors
$\mathbf{v}^{1},\ldots,\mathbf{v}^{m}\in\\{(f(\mathbf{z}_{1}),\ldots,f(\mathbf{z}_{n})):f\in\widetilde{\mathcal{F}}\\}$
such that

$\sup_{f\in\widetilde{\mathcal{F}}}\min_{j\in[m]}\Big{(}\frac{1}{n}\sum_{i\in[n]}|f(\mathbf{z}_{i})-\mathbf{v}_{i}^{j}|^{p}\Big{)}^{\frac{1}{p}}\leq\epsilon,$

where $\mathbf{v}_{i}^{j}$ is the $i$-th component of the vector
$\mathbf{v}^{j}$. In this case, we call
$\\{\mathbf{v}^{1},\ldots,\mathbf{v}^{m}\\}$ an $(\epsilon,\ell_{p})$-cover of
$\widetilde{\mathcal{F}}$ with respect to $\widetilde{S}$.

######  Definition B.2 (Fat-Shattering Dimension).

Let $\widetilde{\mathcal{F}}$ be a class of real-valued functions defined over
a space $\widetilde{\mathcal{Z}}$. We define the fat-shattering dimension
$\mathrm{fat}_{\epsilon}(\widetilde{\mathcal{F}})$ at scale $\epsilon>0$ as
the largest $D\in\mathbb{N}$ such that there exist $D$ points
$\mathbf{z}_{1},\ldots,\mathbf{z}_{D}\in\tilde{\mathcal{Z}}$ and witnesses
$s_{1},\ldots,s_{D}\in\mathbb{R}$ satisfying: for any
$\delta_{1},\ldots,\delta_{D}\sim\\{\pm 1\\}$ there exists
$f\in\widetilde{\mathcal{F}}$ with

$\delta_{i}(f(\mathbf{z}_{i})-s_{i})\geq\epsilon/2,\qquad\forall i\in[D].$

To prove Theorem 4.8, we need to introduce the following lemma on Rademacher
complexity, fat-shattering dimension and covering numbers. Part (a) shows that
the covering number can be bounded by fat-shattering dimension (see, e.g.,
Theorem 12.8 in Anthony & Bartlett [2]). Part (b) shows that the fat-
shattering dimension can be controlled by the worst-case Rademacher
complexity, which was developed in Srebro et al. [36]. Part (c) is a
discretization of the chain integral to control Rademacher complexity by
covering numbers [36], which can be found in Guermeur [17]. Let $e$ be the
base of the natural logarithms.

######  Lemma B.3.

Let
$\widetilde{S}:=\\{\mathbf{z}_{1},\ldots,\mathbf{z}_{n}\\}\subseteq\tilde{\mathcal{Z}}$.
Let $\widetilde{\mathcal{F}}$ be a class of real-valued functions defined over
a space $\widetilde{\mathcal{Z}}$.

  1. (a)

If functions in $\widetilde{\mathcal{F}}$ take values in $[-B,B]$, then for
any $\epsilon>0$ with $\mathrm{fat}_{\epsilon}(\widetilde{\mathcal{F}})<n$ we
have

$\log\mathcal{N}_{\infty}(\epsilon,\widetilde{\mathcal{F}},\widetilde{S})\leq
1+\mathrm{fat}_{\epsilon/4}(\widetilde{\mathcal{F}})\Big{(}\log_{2}\frac{4eBn}{\epsilon\mathrm{fat}_{\epsilon/4}(\widetilde{\mathcal{F}})}\Big{)}\Big{(}\log\frac{16B^{2}n}{\epsilon^{2}}\Big{)}.$

  2. (b)

For any
$\epsilon>\mathfrak{R}_{\widetilde{\mathcal{Z}},n}(\widetilde{\mathcal{F}})$,
we have
$\mathrm{fat}_{\epsilon}(\widetilde{\mathcal{F}})<\frac{4n}{\epsilon^{2}}\mathfrak{R}_{\widetilde{\mathcal{Z}},n}^{2}(\widetilde{\mathcal{F}})$.

  3. (c)

Let $(\epsilon_{j})_{j=0}^{\infty}$ be a monotone sequence decreasing to $0$
and any $(a_{1},\ldots,a_{n})\in\mathbb{R}^{n}$. If

$\epsilon_{0}\geq\sqrt{n^{-1}\sup_{f\in\widetilde{\mathcal{F}}}\sum_{i=1}^{n}\big{(}f(\mathbf{z}_{i})-a_{i}\big{)}^{2}},$

then for any non-negative integer $N$ we have

$\mathfrak{R}_{\widetilde{S}}(\widetilde{\mathcal{F}})\leq
2\sum_{j=1}^{N}\big{(}\epsilon_{j}+\epsilon_{j-1})\sqrt{\frac{\log\mathcal{N}_{\infty}(\epsilon_{j},\widetilde{\mathcal{F}},\widetilde{S})}{n}}+\epsilon_{N}.$
(B.1)

According to Part (a) of Lemma B.3, the following inequality holds for any
$\epsilon\in(0,2B]$ (the case
$\mathrm{fat}_{\epsilon/4}(\widetilde{\mathcal{F}})=0$ is trivial since in
this case we have
$\mathcal{N}_{\infty}(\epsilon,\widetilde{\mathcal{F}},\widetilde{S})=1$, and
otherwise we have $\mathrm{fat}_{\epsilon/4}(\widetilde{\mathcal{F}})\geq 1$)

$\log\mathcal{N}_{\infty}(\epsilon,\widetilde{\mathcal{F}},\widetilde{S})\leq
1+\mathrm{fat}_{\epsilon/4}(\widetilde{\mathcal{F}})\log_{2}^{2}\frac{8eB^{2}|\widetilde{S}|}{\epsilon^{2}}.$
(B.2)

We follow the arguments in Lei et al. [26] to prove Theorem 4.8.

###### Proof of Theorem 4.8.

We first relate the empirical $\ell_{\infty}$-covering number of $\mathcal{F}$
w.r.t.
$S=\\{(\mathbf{x}_{j},\mathbf{x}_{j}^{+},\mathbf{x}^{-}_{j1},\mathbf{x}^{-}_{j2},\ldots,\mathbf{x}^{-}_{jk}):j\in[n]\\}$
to the empirical $\ell_{\infty}$-covering number of $\mathcal{H}$ w.r.t.
$S_{\mathcal{H}}$. Let

$\Big{\\{}\mathbf{r}^{m}=\big{(}r^{m}_{1,1},r^{m}_{1,2},\ldots,r^{m}_{1,k},\ldots,r^{m}_{n,1},r^{m}_{n,2},\ldots,r^{m}_{n,k}\big{)}\\\
:m\in[N]\Big{\\}}$

be an $(\epsilon/G,\ell_{\infty})$-cover of $\mathcal{H}$ w.r.t.
$S_{\mathcal{H}}$. Recall that

$h_{f}(\mathbf{x},\mathbf{x}^{+},\mathbf{x}^{-})=f(\mathbf{x})^{\top}\big{(}f(\mathbf{x}^{+})-f(\mathbf{x}^{-})\big{)}.$
(B.3)

Then, by the definition of $\ell_{\infty}$-cover we know for any
$f\in\mathcal{F}$ we can find $m\in[N]$ such that

$\max_{j\in[n]}\max_{i\in[k]}\big{|}h_{f}(\mathbf{x}_{j},\mathbf{x}_{j}^{+},\mathbf{x}_{ji}^{-})-r^{m}_{j,i}\big{|}\leq\epsilon/G.$

By the Lipschitz continuity of $\ell$, we then get

$\displaystyle\max_{j\in[n]}\big{|}\ell\big{(}\big{\\{}f(\mathbf{x}_{j})^{\top}\big{(}f(\mathbf{x}_{j}^{+})-f(\mathbf{x}_{ji}^{-})\big{)}\big{\\}}_{i=1}^{k}\big{)}-\ell\big{(}\\{r^{m}_{j,i}\\}_{i=1}^{k}\big{)}\big{|}$
$\displaystyle\leq
G\big{\|}\big{(}f(\mathbf{x}_{j})^{\top}\big{(}f(\mathbf{x}_{j}^{+})-f(\mathbf{x}_{ji}^{-})\big{)}\big{)}_{i=1}^{k}-\big{(}r^{m}_{j,i}\big{)}_{i=1}^{k}\big{\|}_{\infty}=G\big{\|}\big{(}h_{f}(\mathbf{x}_{j},\mathbf{x}_{j}^{+},\mathbf{x}^{-}_{ji})\big{)}_{i=1}^{k}-\big{(}r^{m}_{j,i}\big{)}_{i=1}^{k}\big{\|}_{\infty}$
$\displaystyle\leq G\epsilon/G=\epsilon.$

This shows that
$\big{\\{}\big{(}\ell\big{(}\\{r^{m}_{1,i}\\}_{i=1}^{k}\big{)},\ell\big{(}\\{r^{m}_{2,i}\\}_{i=1}^{k}\big{)},\ldots,\ell\big{(}\\{r^{m}_{n,i}\\}_{i=1}^{k}\big{)}\big{)}:m\in[N]\big{\\}}$
is an $(\epsilon,\ell_{\infty})$-cover of $\mathcal{G}$ w.r.t. $S$ and
therefore

$\mathcal{N}_{\infty}(\epsilon,\mathcal{G},S)\leq\mathcal{N}_{\infty}(\epsilon/G,\mathcal{H},S_{\mathcal{H}}).$
(B.4)

Since we consider empirical covering number of $\mathcal{F}$ w.r.t. $S$, we
can assume functions in $\mathcal{H}$ are defined over $S_{\mathcal{H}}$. For
simplicity, we denote
$\mathfrak{R}_{nk}(\mathcal{H}):=\mathfrak{R}_{S_{\mathcal{H}},nk}(\mathcal{H})$.
We now control $\mathcal{N}_{\infty}(\epsilon/G,\mathcal{H},S_{\mathcal{H}})$
by Rademacher complexities of $\mathcal{H}$. For any
$\epsilon>2\mathfrak{R}_{nk}(\mathcal{H})$, it follows from Part (b) of Lemma
B.3 that

$\mathrm{fat}_{\epsilon}(\mathcal{H})\leq\frac{4nk}{\epsilon^{2}}\mathfrak{R}^{2}_{S_{\mathcal{H}},nk}(\mathcal{H})\leq
nk.$ (B.5)

Note for any $f\in\mathcal{F}$, we have
$f(\mathbf{x})^{\top}(f(\mathbf{x}^{+})-f(\mathbf{x}^{-}))\in[-2R^{2},2R^{2}]$.
It then follows from Eq. (B.2) and Eq. (B.5) that (replace $B$ by $2R^{2}$)

$\displaystyle\log\mathcal{N}_{\infty}(\epsilon,\mathcal{H},S_{\mathcal{H}})$
$\displaystyle\leq
1+\mathrm{fat}_{\epsilon/4}(\mathcal{H})\log^{2}(32eR^{4}nk/\epsilon^{2})$
$\displaystyle\leq
1+\frac{64nk\mathfrak{R}^{2}_{nk}(\mathcal{H})}{\epsilon^{2}}\log^{2}(32eR^{4}nk/\epsilon^{2}),\quad\epsilon\in(0,4R^{2}].$

We can combine the above inequality and Eq. (B.4) to derive the following
inequality for any $2G\mathfrak{R}_{nk}(\mathcal{H})\leq\epsilon\leq 4GR^{2}$

$\log\mathcal{N}_{\infty}(\epsilon,\mathcal{G},S)\leq
1+\frac{64nkG^{2}\mathfrak{R}^{2}_{nk}(\mathcal{H})}{\epsilon^{2}}\log^{2}(32eR^{4}G^{2}nk/\epsilon^{2}).$
(B.6)

Let
$\epsilon_{N}=24G\max\big{\\{}\sqrt{k}\mathfrak{R}_{nk}(\mathcal{H}),n^{-\frac{1}{2}}\big{\\}}$,

$\epsilon_{j}=2^{N-j}\epsilon_{N},\quad j=0,\ldots,N-1,$

where

$N=\bigg{\lceil}\log_{2}\frac{2GR^{2}}{24G\max\Big{\\{}\sqrt{k}\mathfrak{R}_{nk}(\mathcal{H}),n^{-\frac{1}{2}}\Big{\\}}}\bigg{\rceil}.$

It is clear from the definition that

$\epsilon_{0}\geq 2GR^{2}\geq\epsilon_{0}/2.$

The Lipschitz continuity of $\ell$ implies

$\ell((\\{h_{f}(\mathbf{x},\mathbf{x}^{+},\mathbf{x}^{-}_{i})\\}_{i\in[k]}))-\ell((0,0,\ldots,0))\leq
G\|h_{f}(\mathbf{x},\mathbf{x}^{+},\mathbf{x}^{-})\|_{\infty}\leq 2R^{2}G.$

According to the above inequality and Part (c) of Lemma B.3, we know (note
$\epsilon_{N}\geq 2G\mathfrak{R}_{nk}(\mathcal{H})$ and therefore Eq. (B.6)
holds for $\epsilon=\epsilon_{j},j=1,\ldots,N$)

$\displaystyle\mathfrak{R}_{S}(\mathcal{G})\leq
2\sum_{j=1}^{N}(\epsilon_{j}+\epsilon_{j-1})\sqrt{\frac{\log\mathcal{N}_{\infty}(\epsilon_{j},\mathcal{G},S)}{n}}+\epsilon_{N}$
$\displaystyle\leq
2n^{-\frac{1}{2}}\sum_{j=1}^{N}(\epsilon_{j}+\epsilon_{j-1})+\frac{16G\sqrt{nk}\mathfrak{R}_{nk}(\mathcal{H})}{\sqrt{n}}\sum_{j=1}^{N}\frac{(\epsilon_{j}+\epsilon_{j-1})\log(32eR^{4}G^{2}nk/\epsilon_{j}^{2})}{\epsilon_{j}}+\epsilon_{N}$
$\displaystyle\leq
6\epsilon_{0}n^{-\frac{1}{2}}+\epsilon_{N}+\frac{48G\sqrt{nk}\mathfrak{R}_{nk}(\mathcal{H})}{\sqrt{n}}\sum_{j=1}^{N}\log(32eR^{4}G^{2}nk/\epsilon_{j}^{2})$
$\displaystyle\leq
24GR^{2}n^{-\frac{1}{2}}+\epsilon_{N}+48GN\sqrt{k}\mathfrak{R}_{nk}(\mathcal{H})\log(32eR^{4}G^{2}nk)+48G\sqrt{k}\mathfrak{R}_{nk}(\mathcal{H})\sum_{j=1}^{N}\log(1/\epsilon_{j}^{2}).$

According to the definition of $\epsilon_{k}$, we know

$\displaystyle\sum_{j=1}^{N}\log(1/\epsilon_{j}^{2})$
$\displaystyle=\sum_{j=1}^{N}\log(2^{2j}/\epsilon_{0}^{2})=\sum_{j=1}^{N}\log(1/\epsilon_{0}^{2})+\log
4\cdot\sum_{j=1}^{N}j=N\log(1/\epsilon_{0}^{2})+\frac{N(N+1)\log 4}{2}$
$\displaystyle=N\Big{(}\log 1/\epsilon_{0}^{2}+(N+1)\log 2\Big{)}=N\log
2^{N+1}/\epsilon_{0}^{2}=N\log\Big{(}\frac{1}{\epsilon_{N}}\frac{2}{\epsilon_{0}}\Big{)}\leq
N\log\Big{(}\frac{1}{\epsilon_{N}}\frac{2}{2GR^{2}}\Big{)}$ $\displaystyle\leq
N\log\Big{(}\frac{\sqrt{n}}{24G}\frac{1}{GR^{2}}\Big{)}=N\log\frac{\sqrt{n}}{24G^{2}R^{2}}.$

We can combine the above two inequalities together to get

$\displaystyle\mathfrak{R}_{S}(\mathcal{G})$ $\displaystyle\leq
24GR^{2}n^{-\frac{1}{2}}+\epsilon_{N}+48NG\sqrt{k}\mathfrak{R}_{nk}(\mathcal{H})\Big{(}\log(32eR^{4}G^{2}nk)+\log\frac{\sqrt{n}}{24G^{2}R^{2}}\Big{)}$
$\displaystyle\leq
24GR^{2}n^{-\frac{1}{2}}+\epsilon_{N}+48G\sqrt{k}\mathfrak{R}_{nk}(\mathcal{H})\Big{(}\log(32eR^{4}G^{2}nk)+\log\frac{\sqrt{n}}{24G^{2}R^{2}}\Big{)}\Big{\lceil}\log_{2}\frac{2GR^{2}\sqrt{n}}{24G}\Big{\rceil}$
$\displaystyle\leq
24GR^{2}n^{-\frac{1}{2}}+\epsilon_{N}+48G\sqrt{k}\mathfrak{R}_{nk}(\mathcal{H})\Big{(}\log(4R^{2}n^{\frac{3}{2}}k)\Big{)}\Big{\lceil}\log_{2}\frac{R^{2}\sqrt{n}}{12}\Big{\rceil},$

where we have used the definition of $N$ and $32e/24\leq 4$. The proof is
completed. ∎

###### Proof of Theorem 4.9.

Applying Lemma A.2, with probability at least $1-\delta$ the following
inequality holds with probability at least $1-\delta$

$L_{un}(f)\leq\hat{L}_{un}(f)+2\mathfrak{R}_{S}(\mathcal{G})+3B\sqrt{\frac{\log(2/\delta)}{2n}},\quad\forall
f\in\mathcal{F}.$

According to Theorem 4.8 and Lemma 4.3, we know

$\displaystyle\mathfrak{R}_{S}(\mathcal{G})$ $\displaystyle\leq
48G(R^{2}+1)n^{-\frac{1}{2}}+48G\sqrt{k}\mathfrak{R}_{nk}(\mathcal{H})\bigg{(}1+\log(R^{2}n^{\frac{3}{2}}k)\Big{\lceil}\log_{2}\frac{R^{2}\sqrt{n}}{12}\Big{\rceil}\bigg{)}$
$\displaystyle\leq
48G(R^{2}+1)n^{-\frac{1}{2}}+\frac{48\sqrt{12}GR\sqrt{k}}{nk}\bigg{(}1+\log(R^{2}n^{\frac{3}{2}}k)\Big{\lceil}\log_{2}\frac{R^{2}\sqrt{n}}{12}\Big{\rceil}\bigg{)}\mathfrak{C}.$

We can combine the above two inequalities together and derive the stated
bound. The proof is completed. ∎

##  Appendix C Proof of Theorem 4.12

To prove Theorem 4.12, we introduce the following lemma on generalization
error bounds in terms of local Rademacher complexities [34].

######  Lemma C.1 (Reeve & Kaban 34).

Consider a function class $\mathcal{G}$ of functions mapping $\mathcal{Z}$ to
$[0,b]$. For any $\widetilde{S}=\\{\mathbf{z}_{i}:i\in[n]\\}$ and
$g\in\mathcal{G}$, let
$\hat{\mathbb{E}}_{\widetilde{S}}[g]=\frac{1}{n}\sum_{i\in[n]}g(\mathbf{z}_{i})$.
Assume for any $\widetilde{S}\in\mathcal{Z}^{n}$ and $r>0$, we have

$\mathfrak{R}_{\widetilde{S}}\big{(}\\{g\in\mathcal{G}:\hat{\mathbb{E}}_{\widetilde{S}}[g]\leq
r\\}\big{)}\leq\phi_{n}(r),$

where $\phi_{n}:\mathbb{R}_{+}\mapsto\mathbb{R}_{+}$ is non-decreasing and
$\phi_{n}(r)/\sqrt{r}$ is non-increasing. Let $\hat{r}_{n}$ be the largest
solution of the equation $\phi_{n}(r)=r$. For any $\delta\in(0,1)$, with
probability at least $1-\delta$ the following inequality holds uniformly for
all $g\in\mathcal{G}$

$\mathbb{E}_{\mathbf{z}}[g(\mathbf{z})]\leq\hat{\mathbb{E}}_{\widetilde{S}}[g]+90(\hat{r}_{n}+r_{0})+4\sqrt{\hat{\mathbb{E}}_{\widetilde{S}}[g](\hat{r}_{n}+r_{0})},$

where $r_{0}=b\big{(}\log(1/\delta)+6\log\log n\big{)}/n$.

###### Proof of Theorem 4.12.

For any $r>0$, we define $\mathcal{F}_{r}$ as a subset of $\mathcal{F}$ with
the empirical error less than or equal to $r$

$\mathcal{F}_{r}=\Big{\\{}f\in\mathcal{F}:\frac{1}{n}\sum_{j\in[n]}g_{f}(\mathbf{x}_{j},\mathbf{x}_{j}^{+},\mathbf{x}_{j1}^{-},\ldots,\mathbf{x}_{jk}^{-})\leq
r\Big{\\}}.$

Let

$\Big{\\{}\mathbf{r}^{m}=\big{(}r^{m}_{1,1},r^{m}_{1,2},\ldots,r^{m}_{1,k},\ldots,r^{m}_{n,1},r^{m}_{n,2},\ldots,r^{m}_{n,k}\big{)}\\\
:m\in[N]\Big{\\}}$

be an $(\epsilon/(\sqrt{2r}G_{s}),\ell_{\infty})$-cover of
$\mathcal{H}_{r}:=\big{\\{}h_{f}\in\mathcal{H}:f\in\mathcal{F}_{r}\big{\\}}$
w.r.t. $S_{\mathcal{H}}$. Then, by the definition of $\ell_{\infty}$-cover we
know for any $f\in\mathcal{F}_{r}$ we can find $m\in[N]$ such that

$\max_{j\in[n]}\max_{i\in[k]}\big{|}h_{f}(\mathbf{x}_{j},\mathbf{x}_{j}^{+},\mathbf{x}_{ji}^{-})-r^{m}_{j,i}\big{|}\leq\epsilon/(\sqrt{2r}G_{s}).$

According to the self-bounding Lipschitz continuity of $\ell$, we know

$\displaystyle\frac{1}{n}\sum_{j\in[n]}\big{|}\ell\big{(}\big{\\{}f(\mathbf{x}_{j})^{\top}\big{(}f(\mathbf{x}_{j}^{+})-f(\mathbf{x}_{ji}^{-})\big{)}\big{\\}}_{i=1}^{k}\big{)}-\ell\big{(}\\{r^{m}_{j,i}\\}_{i=1}^{k}\big{)}\big{|}^{2}$
$\displaystyle\leq\frac{G_{s}^{2}}{n}\sum_{j\in[n]}\max\Big{\\{}\ell\big{(}\big{\\{}f(\mathbf{x}_{j})^{\top}\big{(}f(\mathbf{x}_{j}^{+})-f(\mathbf{x}_{ji}^{-})\big{)}\big{\\}}_{i=1}^{k}\big{)},\ell\big{(}\\{r^{m}_{j,i}\\}_{i=1}^{k}\big{)}\Big{\\}}\big{\|}\big{(}f(\mathbf{x}_{j})^{\top}\big{(}f(\mathbf{x}_{j}^{+})-f(\mathbf{x}_{ji}^{-})\big{)}\big{)}_{i=1}^{k}-\big{(}r^{m}_{j,i}\big{)}_{i=1}^{k}\big{\|}_{\infty}^{2}$
$\displaystyle\leq\frac{G_{s}^{2}}{n}\sum_{j\in[n]}\big{(}\ell\big{(}\big{\\{}f(\mathbf{x}_{j})^{\top}\big{(}f(\mathbf{x}_{j}^{+})-f(\mathbf{x}_{ji}^{-})\big{)}\big{\\}}_{i=1}^{k}\big{)}+\ell\big{(}\\{r^{m}_{j,i}\\}_{i=1}^{k}\big{)}\big{)}\big{\|}\big{(}h_{f}(\mathbf{x}_{j},\mathbf{x}_{j}^{+},\mathbf{x}^{-}_{ji})\big{)}_{i=1}^{k}-\big{(}r^{m}_{j,i}\big{)}_{i=1}^{k}\big{\|}_{\infty}^{2}$
$\displaystyle\leq 2G_{s}^{2}r\epsilon^{2}/(2rG_{s}^{2})=\epsilon^{2},$

where we have used the following inequalities due to the definition of
$\mathcal{F}_{r}$

$\frac{1}{n}\sum_{j\in[n]}\ell\big{(}\big{\\{}f(\mathbf{x}_{j})^{\top}\big{(}f(\mathbf{x}_{j}^{+})-f(\mathbf{x}_{ji}^{-})\big{)}\big{\\}}_{i=1}^{k}\big{)}\leq
r,\qquad\frac{1}{n}\sum_{j\in[n]}\ell\big{(}\\{r^{m}_{j,i}\\}_{i=1}^{k}\big{)}\leq
r.$

Therefore, we have

$\mathcal{N}_{2}(\epsilon,\mathcal{G}_{r},S)\leq\mathcal{N}_{\infty}(\epsilon/(\sqrt{2r}G_{s}),\mathcal{H}_{r},S_{\mathcal{H}}),$

where $\mathcal{G}_{r}=\\{g_{f}\in\mathcal{G}:f\in\mathcal{F}_{r}\\}$.
Analyzing analogously to the proof of Theorem 4.8, we get (replacing $G$ there
by $\sqrt{2r}G_{s}$)

$\mathfrak{R}_{S}(\mathcal{G}_{r})\leq
24\sqrt{2r}G_{s}(R^{2}+1)n^{-\frac{1}{2}}+48\sqrt{2r}G_{s}\sqrt{k}\mathfrak{R}_{S_{\mathcal{H}},nk}(\mathcal{H})\bigg{(}1+\log(4R^{2}n^{\frac{3}{2}}k)\Big{\lceil}\log_{2}\frac{R^{2}\sqrt{n}}{12}\Big{\rceil}\bigg{)}:=\psi_{n}(r).$

Let $\hat{r}_{n}$ be the point satisfying $\hat{r}_{n}=\psi_{n}(\hat{r}_{n})$:

$\hat{r}_{n}=24\sqrt{2\hat{r}_{n}}G_{s}(R^{2}+1)n^{-\frac{1}{2}}+48\sqrt{2\hat{r}_{n}}G_{s}\sqrt{k}\mathfrak{R}_{S_{\mathcal{H}},nk}(\mathcal{H})\bigg{(}1+\log(4R^{2}n^{\frac{3}{2}}k)\Big{\lceil}\log_{2}\frac{R^{2}\sqrt{n}}{12}\Big{\rceil}\bigg{)},$

from which we get

$\displaystyle\hat{r}_{n}$
$\displaystyle=\widetilde{O}\Big{(}G_{s}^{2}R^{4}n^{-1}+G_{s}^{2}k\mathfrak{R}^{2}_{S_{\mathcal{H}},nk}(\mathcal{H})\Big{)}.$

We can apply Lemma C.1 to get the following inequality with probability at
least $1-\delta$ uniformly for all $f\in\mathcal{F}$

$L_{un}(f)=\hat{L}_{un}(f)+\widetilde{O}\Big{(}Bn^{-1}+G_{s}^{2}R^{4}n^{-1}+G_{s}^{2}k\mathfrak{R}^{2}_{S_{\mathcal{H}},nk}(\mathcal{H})\Big{)}+\widetilde{O}\Big{(}\sqrt{B}n^{-\frac{1}{2}}+G_{s}R^{2}n^{-\frac{1}{2}}+G_{s}\sqrt{k}\mathfrak{R}_{S_{\mathcal{H}},nk}(\mathcal{H})\Big{)}\hat{L}^{\frac{1}{2}}_{un}(f).$

We can apply Lemma 4.3 to control
$\mathfrak{R}_{S_{\mathcal{H}},nk}(\mathcal{H})$ and derive the following
bound

$L_{un}(f)=\hat{L}_{un}(f)+\widetilde{O}\Big{(}Bn^{-1}+G_{s}^{2}R^{4}n^{-1}+G_{s}^{2}R^{2}n^{-2}k^{-1}\mathfrak{C}^{2}\Big{)}+\widetilde{O}\Big{(}\sqrt{B}n^{-\frac{1}{2}}+G_{s}R^{2}n^{-\frac{1}{2}}+G_{s}Rn^{-1}k^{-\frac{1}{2}}\mathfrak{C}\Big{)}\hat{L}^{\frac{1}{2}}_{un}(f).$

The proof is completed. ∎

##  Appendix D Proof on Rademacher Complexities

We first prove Rademacher complexity bounds for feature spaces in Lemma 5.1,
and then give lower bounds. Finally, we will apply it to prove Proposition 5.3
and Proposition 5.5.

###### Proof of Lemma 5.1.

Let $U=(\mathbf{u}_{1},\ldots,\mathbf{u}_{d})^{\top}$ and
$V_{S}=(\mathbf{v}(\mathbf{x}_{1}),\ldots,\mathbf{v}(\mathbf{x}_{n}))$. Then
it is clear

$UV_{S}=\begin{pmatrix}\mathbf{u}_{1}^{\top}\mathbf{v}(\mathbf{x}_{1})&\cdots&\mathbf{u}_{1}^{\top}\mathbf{v}(\mathbf{x}_{n})\\\
\vdots&\vdots&\vdots\\\
\mathbf{u}_{d}^{\top}\mathbf{v}(\mathbf{x}_{1})&\cdots&\mathbf{u}_{d}^{\top}\mathbf{v}(\mathbf{x}_{n})\end{pmatrix}.$

Let

$M_{\epsilon}=\begin{pmatrix}\epsilon_{1,1}&\cdots&\epsilon_{1,n}\\\
\vdots&\vdots&\vdots\\\ \epsilon_{d,1}&\cdots&\epsilon_{d,n}\\\
\end{pmatrix}\in\mathbb{R}^{d\times n}.$

Then we have

$\displaystyle\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}\mathbf{u}_{t}^{\top}\mathbf{v}(\mathbf{x}_{j})$
$\displaystyle=\big{\langle}M_{\epsilon},UV_{S}\rangle=\text{trace}(M_{\epsilon}^{\top}UV_{S})=\text{trace}(UV_{S}M_{\epsilon}^{\top})$
$\displaystyle=\big{\langle}U^{\top},V_{S}M_{\epsilon}^{\top}\big{\rangle}\leq\|U^{\top}\|\|V_{S}M_{\epsilon}^{\top}\|_{*},$

where trace denotes the trace of a matrix. Therefore, we have

$\displaystyle\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})$
$\displaystyle=\sup_{U\in\mathcal{U},\mathbf{v}\in\mathcal{V}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}\mathbf{u}_{t}^{\top}\mathbf{v}(\mathbf{x}_{j})$
$\displaystyle\leq\Lambda\sup_{\mathbf{v}\in\mathcal{V}}\|V_{S}M_{\epsilon}^{\top}\|_{*}=\Lambda\sup_{\mathbf{v}\in\mathcal{V}}\big{\|}\big{(}\sum_{j\in[n]}\epsilon_{1,j}\mathbf{v}(\mathbf{x}_{j}),\ldots,\sum_{j\in[n]}\epsilon_{d,j}\mathbf{v}(\mathbf{x}_{j})\big{)}\big{\|}_{*}.$

The proof is completed. ∎

###### Proof of Lemma 5.2.

Note

$\Big{|}\sum_{j\in[nk]}\sum_{t\in[d]}\big{(}\epsilon_{j,t,1}f_{t}(\tilde{\mathbf{x}}_{j})+\epsilon_{j,t,2}f_{t}(\tilde{\mathbf{x}}_{j}^{+})+\epsilon_{j,t,3}f_{t}(\tilde{\mathbf{x}}_{j}^{-})\big{)}\Big{|}=\\\
\max\Big{\\{}\sum_{j\in[nk]}\sum_{t\in[d]}\big{(}\epsilon_{j,t,1}f_{t}(\tilde{\mathbf{x}}_{j})+\epsilon_{j,t,2}f_{t}(\tilde{\mathbf{x}}_{j}^{+})+\epsilon_{j,t,3}f_{t}(\tilde{\mathbf{x}}_{j}^{-})\big{)},-\sum_{j\in[nk]}\sum_{t\in[d]}\big{(}\epsilon_{j,t,1}f_{t}(\tilde{\mathbf{x}}_{j})+\epsilon_{j,t,2}f_{t}(\tilde{\mathbf{x}}_{j}^{+})+\epsilon_{j,t,3}f_{t}(\tilde{\mathbf{x}}_{j}^{-})\big{)}\Big{\\}}.$

According to the symmetry of $\mathcal{F}$ we know

$\displaystyle\mathfrak{C}$
$\displaystyle=\max_{\\{(\tilde{\mathbf{x}}_{j},\tilde{\mathbf{x}}_{j}^{+},\tilde{\mathbf{x}}_{j}^{-})\\}_{j=1}^{nk}\subseteq
S_{\mathcal{H}}}\mathbb{E}_{\bm{\epsilon}\sim\\{\pm 1\\}^{nk}\times\\{\pm
1\\}^{d}\times\\{\pm
1\\}^{3}}\Big{[}\sup_{f\in\mathcal{F}}\Big{|}\sum_{j\in[nk]}\sum_{t\in[d]}\big{(}\epsilon_{j,t,1}f_{t}(\tilde{\mathbf{x}}_{j})+\epsilon_{j,t,2}f_{t}(\tilde{\mathbf{x}}_{j}^{+})+\epsilon_{j,t,3}f_{t}(\tilde{\mathbf{x}}_{j}^{-})\big{)}\Big{|}\Big{]}$
$\displaystyle\geq\sup_{f\in\mathcal{F}}\max_{\\{(\tilde{\mathbf{x}}_{j},\tilde{\mathbf{x}}_{j}^{+},\tilde{\mathbf{x}}_{j}^{-})\\}_{j=1}^{nk}\subseteq
S_{\mathcal{H}}}\mathbb{E}_{\bm{\epsilon}\sim\\{\pm 1\\}^{nk}\times\\{\pm
1\\}^{d}\times\\{\pm
1\\}^{3}}\Big{[}\Big{|}\sum_{j\in[nk]}\sum_{t\in[d]}\big{(}\epsilon_{j,t,1}f_{t}(\tilde{\mathbf{x}}_{j})+\epsilon_{j,t,2}f_{t}(\tilde{\mathbf{x}}_{j}^{+})+\epsilon_{j,t,3}f_{t}(\tilde{\mathbf{x}}_{j}^{-})\big{)}\Big{|}\Big{]},$

where we have used the Jensen’s inequality in the last step.

Since we take maximization over
$\\{(\tilde{\mathbf{x}}_{j},\tilde{\mathbf{x}}_{j}^{+},\tilde{\mathbf{x}}_{j}^{-})\\}_{j=1}^{nk}\subseteq
S_{\mathcal{H}}$, we can choose
$(\tilde{\mathbf{x}}_{j},\tilde{\mathbf{x}}_{j}^{+},\tilde{\mathbf{x}}_{j}^{-})=(\tilde{\mathbf{x}},\tilde{\mathbf{x}}^{+},\tilde{\mathbf{x}}^{-})$
for any $(\tilde{\mathbf{x}},\tilde{\mathbf{x}}^{+},\tilde{\mathbf{x}}^{-})\in
S_{\mathcal{H}}$. Then we get

$\displaystyle\mathfrak{C}$
$\displaystyle\geq\sup_{f\in\mathcal{F}}\max_{(\tilde{\mathbf{x}},\tilde{\mathbf{x}}^{+},\tilde{\mathbf{x}}^{-})\in
S_{\mathcal{H}}}\mathbb{E}_{\bm{\epsilon}\sim\\{\pm 1\\}^{nk}\times\\{\pm
1\\}^{d}\times\\{\pm
1\\}^{3}}\Big{[}\Big{|}\sum_{j\in[nk]}\sum_{t\in[d]}\big{(}\epsilon_{j,t,1}f_{t}(\tilde{\mathbf{x}})+\epsilon_{j,t,2}f_{t}(\tilde{\mathbf{x}}^{+})+\epsilon_{j,t,3}f_{t}(\tilde{\mathbf{x}}^{-})\big{)}\Big{|}\Big{]}$
$\displaystyle\geq
2^{-\frac{1}{2}}\sup_{f\in\mathcal{F}}\max_{(\tilde{\mathbf{x}},\tilde{\mathbf{x}}^{+},\tilde{\mathbf{x}}^{-})\in
S_{\mathcal{H}}}\Big{(}\sum_{j\in[nk]}\sum_{t\in[d]}\big{(}f_{t}^{2}(\tilde{\mathbf{x}})+f_{t}^{2}(\tilde{\mathbf{x}}^{+})+f_{t}^{2}(\tilde{\mathbf{x}}^{-})\big{)}\Big{)}^{\frac{1}{2}}$
$\displaystyle=2^{-\frac{1}{2}}\sup_{f\in\mathcal{F}}\max_{(\tilde{\mathbf{x}},\tilde{\mathbf{x}}^{+},\tilde{\mathbf{x}}^{-})\in
S_{\mathcal{H}}}\Big{(}\sum_{j\in[nk]}\big{(}\|f(\tilde{\mathbf{x}})\|_{2}^{2}+\|f(\tilde{\mathbf{x}}^{+})\|_{2}^{2}+\|f(\tilde{\mathbf{x}}^{-})\|_{2}^{2}\big{)}\Big{)}^{\frac{1}{2}}$
$\displaystyle=\sqrt{2^{-1}nk}\sup_{f\in\mathcal{F}}\max_{(\tilde{\mathbf{x}},\tilde{\mathbf{x}}^{+},\tilde{\mathbf{x}}^{-})\in
S_{\mathcal{H}}}\Big{(}\|f(\tilde{\mathbf{x}})\|_{2}^{2}+\|f(\tilde{\mathbf{x}}^{+})\|_{2}^{2}+\|f(\tilde{\mathbf{x}}^{-})\|_{2}^{2}\Big{)}^{\frac{1}{2}},$

where we have used the following Khitchine-Kahane inequality [13]

$\mathbb{E}_{\epsilon}\big{|}\sum_{i=1}^{n}\epsilon_{i}t_{i}\big{|}\geq
2^{-\frac{1}{2}}\big{[}\sum_{i=1}^{n}|t_{i}|^{2}\big{]}^{\frac{1}{2}},\quad\forall
t_{1},\ldots,t_{n}\in\mathbb{R},$ (D.1)

The proof is completed. ∎

######  Remark D.1.

The analysis in the proof implies a lower bound for
$\mathfrak{R}_{\widetilde{S}}(\widetilde{\mathcal{F}})$ for a symmetric
$\widetilde{\mathcal{F}}$ and
$\widetilde{S}=\\{\mathbf{z}_{1},\ldots,\mathbf{z}_{n}\\}$

$\mathfrak{R}_{\widetilde{S}}(\widetilde{\mathcal{F}})\geq\frac{1}{\sqrt{2}n}\sup_{f\in\widetilde{\mathcal{F}}}\big{\|}\big{(}f(\mathbf{z}_{1}),\ldots,f(\mathbf{z}_{n})\big{)}\big{\|}_{2}.$

Indeed, by the symmetry of $\mathcal{F}$, the Jensen inequality and Eq. (D.1),
we have

$\displaystyle\mathfrak{R}_{\widetilde{S}}(\widetilde{\mathcal{F}})$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}}\big{[}\sup_{f\in\widetilde{\mathcal{F}}}\frac{1}{n}\sum_{i\in[n]}\epsilon_{i}f(\mathbf{z}_{i})\big{]}=\mathbb{E}_{\bm{\epsilon}}\big{[}\sup_{f\in\widetilde{\mathcal{F}}}\frac{1}{n}\big{|}\sum_{i\in[n]}\epsilon_{i}f(\mathbf{z}_{i})\big{|}\big{]}$
$\displaystyle\geq\frac{1}{n}\sup_{f\in\widetilde{\mathcal{F}}}\mathbb{E}_{\bm{\epsilon}}\big{[}\big{|}\sum_{i\in[n]}\epsilon_{i}f(\mathbf{z}_{i})\big{|}\big{]}\geq\frac{1}{\sqrt{2}n}\sup_{f\in\widetilde{\mathcal{F}}}\Big{(}\sum_{i\in[n]}f^{2}(\mathbf{z}_{i})\Big{)}^{\frac{1}{2}}.$

###  D.1 Proof of Proposition 5.3

The following Khintchine-Kahane inequality [13, 27] is very useful for us to
estimate Rademacher complexities.

######  Lemma D.2.

Let $\epsilon_{1},\ldots,\epsilon_{n}$ be a sequence of independent Rademacher
variables.

  1. (a)

Let $\mathbf{v}_{1},\ldots,\mathbf{v}_{n}\in\mathcal{H}$, where $\mathcal{H}$
is a Hilbert space with $\|\cdot\|$ being the associated norm. Then, for any
$p\geq 1$ there holds

$\big{[}\mathbb{E}_{\epsilon}\|\sum_{i=1}^{n}\epsilon_{i}\mathbf{v}_{i}\|^{p}\big{]}^{\frac{1}{p}}\leq\max(\sqrt{p-1},1)\big{[}\sum_{i=1}^{n}\|\mathbf{v}_{i}\|^{2}\big{]}^{\frac{1}{2}}.$
(D.2)

  2. (b)

Let $X_{1},\ldots,X_{n}$ be a set of matrices of the same dimension. For all
$q\geq 2$,

$\Big{(}\mathbb{E}_{\bm{\epsilon}}\big{\|}\sum_{i=1}^{n}\epsilon_{i}X_{i}\big{\|}_{S_{q}}^{q}\Big{)}^{\frac{1}{q}}\leq
2^{-\frac{1}{4}}\sqrt{\frac{q\pi}{e}}\max\Big{\\{}\big{\|}\big{(}\sum_{i=1}^{n}X_{i}^{\top}X_{i}\big{)}^{\frac{1}{2}}\big{\|}_{S_{q}},\big{\|}\big{(}\sum_{i=1}^{n}X_{i}X_{i}^{\top}\big{)}^{\frac{1}{2}}\big{\|}_{S_{q}}\Big{\\}}.$
(D.3)

###### Proof of Proposition F.1.

Let $q\geq p$. It is clear $q^{*}\leq p^{*}$. The dual norm of
$\|\cdot\|_{2,p}$ is $\|\cdot\|_{2,p^{*}}$. Therefore, according to Lemma 5.1
and $\|\cdot\|_{p^{*}}\leq\|\cdot\|_{q^{*}}$ we know

$\displaystyle\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})$
$\displaystyle\leq\Lambda\mathbb{E}_{\bm{\epsilon}}\Big{(}\sum_{t\in[d]}\big{\|}\sum_{j\in[n]}\epsilon_{t,j}\mathbf{x}_{j}\big{\|}_{2}^{p^{*}}\Big{)}^{1/p^{*}}\leq\Lambda\mathbb{E}_{\bm{\epsilon}}\Big{(}\sum_{t\in[d]}\big{\|}\sum_{j\in[n]}\epsilon_{t,j}\mathbf{x}_{j}\big{\|}_{2}^{q^{*}}\Big{)}^{1/q^{*}}$
$\displaystyle\leq\Lambda\Big{(}\mathbb{E}_{\bm{\epsilon}}\Big{[}\sum_{t\in[d]}\big{\|}\sum_{j\in[n]}\epsilon_{t,j}\mathbf{x}_{j}\big{\|}_{2}^{q^{*}}\Big{]}\Big{)}^{1/q^{*}}=\Lambda\Big{(}d\mathbb{E}_{\bm{\epsilon}}\big{\|}\sum_{j\in[n]}\epsilon_{j}\mathbf{x}_{j}\big{\|}_{2}^{q^{*}}\Big{)}^{1/q^{*}},$

where we have used Jense’s inequality and the concavity of $x\mapsto
x^{1/q^{*}}$. By Lemma D.2, we know

$\mathbb{E}_{\bm{\epsilon}}\big{\|}\sum_{j\in[n]}\epsilon_{j}\mathbf{x}_{j}\big{\|}_{2}^{q^{*}}\leq\max(\sqrt{q^{*}-1},1)^{q^{*}}\Big{(}\sum_{j\in[n]}\|\mathbf{x}_{j}\|_{2}^{2}\Big{)}^{\frac{q^{*}}{2}}.$

It then follows that

$\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})\leq\Lambda
d^{1/q^{*}}\max(\sqrt{q^{*}-1},1)\Big{(}\sum_{j\in[n]}\|\mathbf{x}_{j}\|_{2}^{2}\Big{)}^{\frac{1}{2}}.$

Note the above inequality holds for any $q\geq p$. This proves Part (a).

We now prove Part (b). Since the dual norm of $\|\cdot\|_{S_{p}}$ is
$\|\cdot\|_{S_{p^{*}}}$, by Lemma 5.1 we know

$\displaystyle\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})$
$\displaystyle\leq\Lambda\mathbb{E}_{\bm{\epsilon}}\big{\|}\big{(}\sum_{j\in[n]}\epsilon_{1,j}\mathbf{x}_{j},\ldots,\sum_{j\in[n]}\epsilon_{d,j}\mathbf{x}_{j}\big{)}\big{\|}_{S_{p^{*}}}.$

For any $t\in[d]$ and $j\in[n]$, define

$\widetilde{X}_{t,j}=\begin{pmatrix}0&\cdots&0&\mathbf{x}_{j}&0&\cdots&0\end{pmatrix},$

i.e., the $t$-th column of $\widetilde{X}_{t,j}=\mathbf{x}_{j}$, and other
columns are zero vectors. This implies that

$\big{(}\sum_{j\in[n]}\epsilon_{1,j}\mathbf{x}_{j},\ldots,\sum_{j\in[n]}\epsilon_{d,j}\mathbf{x}_{j}\big{)}=\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}\widetilde{X}_{t,j}.$

It is clear that
$\widetilde{X}_{t,j}\widetilde{X}_{t,j}^{\top}=\mathbf{x}_{j}\mathbf{x}_{j}^{\top}$
and

$\widetilde{X}_{t,j}^{\top}\widetilde{X}_{t,j}=\begin{pmatrix}0&\cdots&\cdots&0\\\
\vdots&\dots&\cdots&0\\\ \vdots&0&\mathbf{x}_{j}^{\top}\mathbf{x}_{j}&0\\\
0&\cdots&\cdots&\dots.\end{pmatrix}=\mathbf{x}_{j}^{\top}\mathbf{x}_{j}\text{diag}(\underbrace{0,\ldots,0}_{t-1},1,0\ldots,0),$

where $\text{diag}(a_{1},\ldots,a_{n})$ denotes the diagonal matrix with
elements $a_{1},\ldots,a_{n}$. Therefore, we have

$\sum_{t\in[d]}\sum_{j\in[n]}\widetilde{X}_{t,j}\widetilde{X}_{t,j}^{\top}=d\sum_{j\in[n]}\mathbf{x}_{j}\mathbf{x}_{j}^{\top}$

and

$\sum_{t\in[d]}\sum_{j\in[n]}\widetilde{X}_{t,j}^{\top}\widetilde{X}_{t,j}=\big{(}\sum_{j\in[n]}\mathbf{x}_{j}^{\top}\mathbf{x}_{j}\big{)}\mathbb{I}_{d\times
d},$

where $\mathbb{I}_{d\times d}$ denotes the identity matrix in
$\mathbb{R}^{d\times d}$. Therefore, we can apply Lemma D.2 to show that

$\displaystyle\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})$
$\displaystyle\leq\Lambda\Big{(}\mathbb{E}_{\bm{\epsilon}}\big{\|}\big{(}\sum_{j\in[n]}\epsilon_{1,j}\mathbf{x}_{j},\ldots,\sum_{j\in[n]}\epsilon_{d,j}\mathbf{x}_{j}\big{)}\big{\|}_{S_{q}^{*}}^{q^{*}}\Big{)}^{1/q^{*}}$
$\displaystyle\leq\Lambda
2^{-\frac{1}{4}}\sqrt{\frac{q^{*}\pi}{e}}\max\Big{\\{}\Big{\|}\Big{(}d\sum_{j\in[n]}\mathbf{x}_{j}\mathbf{x}_{j}^{\top}\Big{)}^{\frac{1}{2}}\Big{\|}_{S_{q^{*}}},d^{1/q^{*}}\big{(}\sum_{j\in[d]}\|\mathbf{x}_{j}\|_{2}^{2}\big{)}^{\frac{1}{2}}\Big{\\}}.$

The proof is completed. ∎

###  D.2 Proof of Proposition 5.5

For convenience we introduce the following sequence of function spaces

$\mathcal{V}_{k}=\Big{\\{}\mathbf{x}\mapsto\sigma_{k}\big{(}V_{k}\sigma\big{(}V_{k-1}\cdots\sigma(V_{1}\mathbf{x})\big{)}\big{)}:\|V_{j}\|_{F}\leq
B_{j}\Big{\\}},\quad k\in[L].$

To prove Proposition 5.5, we need to introduce several lemmas. The following
lemma shows how the supremum over a matrix can be transferred to a supremum
over a vector. It is an extension of Lemma 1 in Golowich et al. [16] from
$d=1$ to $d\in\mathbb{N}$, and can be proved exactly by the arguments in
Golowich et al. [16].

######  Lemma D.3.

Let $\sigma:\mathbb{R}\mapsto\mathbb{R}$ be a $1$-Lipschitz continuous,
positive-homogeneous activation function which is applied elementwise. Then
for any vector-valued function class $\widetilde{\mathcal{F}}$

$\sup_{\tilde{f}\in\widetilde{\mathcal{F}},V\in\mathbb{R}^{h\times
h^{\prime}}:\|V\|_{F}\leq
B}\sum_{t\in[d]}\Big{\|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(V\tilde{f}(\mathbf{x}_{j}))\Big{\|}_{2}^{2}\leq
B^{2}\sup_{\tilde{f}\in\widetilde{\mathcal{F}},\tilde{\mathbf{v}}\in\mathbb{R}^{h^{\prime}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\sup_{\|\tilde{\mathbf{v}}\|_{2}\leq
1}\sum_{t\in[d]}\Big{|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|}^{2}.$

###### Proof.

Let $\mathbf{v}_{1}^{\top},\ldots,\mathbf{v}_{h}^{\top}$ be rows of matrix
$V$, i.e., $V^{\top}=\big{(}\mathbf{v}_{1},\ldots,\mathbf{v}_{h}\big{)}$. Then
by the positive-homogeneous property of activation function we have

$\displaystyle\sum_{t\in[d]}\Big{\|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(V\tilde{f}(x_{i}))\Big{\|}_{2}^{2}$
$\displaystyle=\sum_{t\in[d]}\left\|\begin{pmatrix}\sum_{j\in[n]}\epsilon_{t,j}\sigma(\mathbf{v}_{1}^{\top}\tilde{f}(\mathbf{x}_{j}))\\\
\vdots\\\
\sum_{j\in[n]}\epsilon_{t,j}\sigma(\mathbf{v}_{h}^{\top}\tilde{f}(\mathbf{x}_{j}))\\\
\end{pmatrix}\right\|_{2}^{2}=\sum_{t\in[d]}\sum_{r\in[h]}\left(\sum_{j\in[n]}\epsilon_{t,j}\sigma(\mathbf{v}_{r}^{\top}\tilde{f}(\mathbf{x}_{j}))\right)^{2}$
$\displaystyle=\sum_{r\in[h]}\|\mathbf{v}_{r}\|_{2}^{2}\sum_{t\in[d]}\bigg{(}\sum_{j\in[n]}\epsilon_{t,j}\sigma\Big{(}\frac{\mathbf{v}_{r}^{\top}}{\|\mathbf{v}_{r}\|_{2}}\tilde{f}(\mathbf{x}_{j})\Big{)}\bigg{)}^{2}$
$\displaystyle\leq\Big{(}\sum_{r\in[h]}\|\mathbf{v}_{r}\|_{2}^{2}\Big{)}\max_{r\in[h]}\sum_{t\in[d]}\Big{|}\sum_{j\in[n]}\epsilon_{t,j}\sigma\Big{(}\frac{\mathbf{v}_{r}^{\top}}{\|\mathbf{v}_{r}\|_{2}}\tilde{f}(\mathbf{x}_{j})\Big{)}\Big{|}^{2}$
$\displaystyle\leq B^{2}\sup_{\|\tilde{\mathbf{v}}\|_{2}\leq
1}\sum_{t\in[d]}\Big{|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|}^{2}.$

The proof is completed. ∎

The following lemma gives a general contraction lemma for Rademacher
complexities. It allows us to remove a nonlinear function $\psi$, which is
very useful for us to handle the activation function in DNNs.

######  Lemma D.4 (Contraction Lemma, Thm 11.6 in Boucheron et al. [7]).

Let $\tilde{\tau}:\mathbb{R}_{+}\mapsto\mathbb{R}_{+}$ be convex and
nondecreasing. Suppose $\psi:\mathbb{R}\mapsto\mathbb{R}$ is contractive in
the sense $|\psi(t)-\psi(\tilde{t})|\leq|t-\tilde{t}|$ and $\psi(0)=0$. Then
the following inequality holds for any $\widetilde{\mathcal{F}}$

$\mathbb{E}_{\bm{\epsilon}}\tilde{\tau}\bigg{(}\sup_{f\in\widetilde{\mathcal{F}}}\sum_{i=1}^{n}\epsilon_{i}\psi\big{(}f(x_{i})\big{)}\bigg{)}\leq\mathbb{E}_{\bm{\epsilon}}\tilde{\tau}\bigg{(}\sup_{f\in\widetilde{\mathcal{F}}}\sum_{i=1}^{n}\epsilon_{i}f(x_{i})\bigg{)}.$

The following lemma gives bounds of moment generation functions for a random
variable $Z=\sum_{1\leq i<j\leq n}\epsilon_{i}\epsilon_{j}a_{ij}$, which is
called a Rademacher chaos variable [13, 44].

######  Lemma D.5 (page 167 in De la Pena & Giné [13]).

Let $\epsilon_{i},i\in[n]$ be independent Rademacher variables. Let
$a_{i,j}\in\mathbb{R},i,j\in[n]$. Then for $Z=\sum_{1\leq i<j\leq
n}\epsilon_{i}\epsilon_{j}a_{ij}$ we have

$\mathbb{E}_{\bm{\epsilon}}\exp\Big{(}|Z|/(4es)\Big{)}\leq 2,\quad\text{where
}s^{2}:=\sum_{1\leq i<j\leq n}a_{i,j}^{2}.$

###### Proof of Proposition 5.5.

The dual norm of $\|\cdot\|_{F}$ is $\|\cdot\|_{F}$. Therefore, according to
Lemma 5.1 we know

$\displaystyle\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})$
$\displaystyle\leq\Lambda\mathbb{E}_{\bm{\epsilon}}\sup_{\mathbf{v}\in\mathcal{V}}\Big{(}\sum_{t\in[d]}\big{\|}\sum_{j\in[n]}\epsilon_{t,j}\mathbf{v}(\mathbf{x}_{j})\big{\|}_{2}^{2}\Big{)}^{1/2}$
$\displaystyle=\Lambda\mathbb{E}_{\bm{\epsilon}}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1},V:\|V\|_{F}\leq
B_{L}}\sum_{t\in[d]}\Big{\|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(V\tilde{f}(\mathbf{x}_{j}))\Big{\|}_{2}^{2}\bigg{)}^{\frac{1}{2}}$
$\displaystyle\leq\Lambda
B_{L}\mathbb{E}_{\bm{\epsilon}}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\sum_{t\in[d]}\Big{|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|}^{2}\bigg{)}^{\frac{1}{2}},$

where we have used Lemma D.3 in the second inequality. Let $\lambda\geq 0$ and
$\tau(x)=\exp(\lambda x^{2})$. It is clear that $\tau$ is convex and
increasing in the interval $[0,\infty)$. It then follows from the Jensen’s
inequality that

$\displaystyle\exp\bigg{(}\lambda\Big{(}\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})\Big{)}^{2}\bigg{)}$
$\displaystyle\leq\exp\bigg{(}\lambda\bigg{(}\Lambda
B_{L}\mathbb{E}_{\bm{\epsilon}}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\sum_{t\in[d]}\Big{|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|}^{2}\bigg{)}^{\frac{1}{2}}\bigg{)}^{2}\bigg{)}$
$\displaystyle\leq\mathbb{E}_{\bm{\epsilon}}\exp\bigg{(}\lambda\bigg{(}\Lambda
B_{L}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\sum_{t\in[d]}\Big{|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|}^{2}\bigg{)}^{\frac{1}{2}}\bigg{)}^{2}\bigg{)}$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}}\exp\bigg{(}\lambda\Lambda^{2}B_{L}^{2}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\sum_{t\in[d]}\Big{|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|}^{2}\bigg{)}$
$\displaystyle\leq\mathbb{E}_{\bm{\epsilon}}\exp\bigg{(}\lambda\Lambda^{2}B_{L}^{2}\sum_{t\in[d]}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\Big{|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|}^{2}\bigg{)}$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}}\prod_{t\in[d]}\exp\bigg{(}\lambda\Lambda^{2}B_{L}^{2}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\Big{|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|}^{2}\bigg{)}$
$\displaystyle=\prod_{t\in[d]}\mathbb{E}_{\bm{\epsilon}_{t}}\exp\bigg{(}\lambda\Lambda^{2}B_{L}^{2}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\Big{|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|}^{2}\bigg{)}$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\exp\bigg{(}d\lambda\Lambda^{2}B_{L}^{2}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\Big{|}\sum_{j\in[n]}\epsilon_{j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|}^{2}\bigg{)},$

where we have used the independency between
$\epsilon_{t}=(\epsilon_{t,j})_{j\in[n]},t\in[d]$. Let
$\tilde{\tau}:\mathbb{R}_{+}\mapsto\mathbb{R}_{+}$ be defined as
$\tilde{\tau}(x)=\exp(d\lambda\Lambda^{2}B_{L}^{2}x^{2})$. Then we have

$\displaystyle\exp\bigg{(}\lambda\Big{(}\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})\Big{)}^{2}\bigg{)}\leq\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\Big{|}\sum_{j\in[n]}\epsilon_{j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|}\bigg{)}$
$\displaystyle\leq\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\sum_{j\in[n]}\epsilon_{j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\bigg{)}+\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}-\sum_{j\in[n]}\epsilon_{j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\bigg{)}$
$\displaystyle=2\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\sum_{j\in[n]}\epsilon_{j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\bigg{)}\leq
2\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\sum_{j\in[n]}\epsilon_{j}\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j})\bigg{)}$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\tilde{\mathbf{v}}^{\top}\sum_{j\in[n]}\epsilon_{j}\tilde{f}(\mathbf{x}_{j})\bigg{)}=\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1}}\Big{\|}\sum_{j\in[n]}\epsilon_{j}\tilde{f}(\mathbf{x}_{j})\Big{\|}_{2}\bigg{)}.$
(D.4)

where we have used Lemma D.4 and the contraction property of $\sigma$ in the
last inequality.

According to Lemma D.3, we know

$\displaystyle\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1}}\Big{\|}\sum_{j\in[n]}\epsilon_{j}\tilde{f}(\mathbf{x}_{j})\Big{\|}_{2}\bigg{)}$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}\sup_{\|V_{L-1}\|_{F}\leq
B_{L-1},\tilde{f}\in\mathcal{V}_{L-2}}\Big{\|}\sum_{j\in[n]}\epsilon_{j}\sigma\big{(}V_{L-1}\tilde{f}(\mathbf{x}_{j})\big{)}\Big{\|}_{2}\bigg{)}$
$\displaystyle\leq\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}B_{L-1}\sup_{\|\tilde{\mathbf{v}}\|_{2}\leq
1,\tilde{f}\in\mathcal{V}_{L-2}}\Big{|}\sum_{j\in[n]}\epsilon_{j}\sigma\big{(}\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j})\big{)}\Big{|}\bigg{)}.$

It then follows that

$\displaystyle\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1}}\Big{\|}\sum_{j\in[n]}\epsilon_{j}\tilde{f}(\mathbf{x}_{j})\Big{\|}_{2}\bigg{)}$
$\displaystyle\leq\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}B_{L-1}\sup_{\|\tilde{\mathbf{v}}\|_{2}\leq
1,\tilde{f}\in\mathcal{V}_{L-2}}\sum_{j\in[n]}\epsilon_{j}\sigma\big{(}\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j})\big{)}\bigg{)}+\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}B_{L-1}\sup_{\|\tilde{\mathbf{v}}\|_{2}\leq
1,\tilde{f}\in\mathcal{V}_{L-2}}-\sum_{j\in[n]}\epsilon_{j}\sigma\big{(}\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j})\big{)}\bigg{)}$
$\displaystyle=2\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}B_{L-1}\sup_{\|\tilde{\mathbf{v}}\|_{2}\leq
1,\tilde{f}\in\mathcal{V}_{L-2}}\sum_{j\in[n]}\epsilon_{j}\sigma\big{(}\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j})\big{)}\bigg{)}\leq
2\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}B_{L-1}\sup_{\|\tilde{\mathbf{v}}\|_{2}\leq
1,\tilde{f}\in\mathcal{V}_{L-2}}\sum_{j\in[n]}\epsilon_{j}\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j})\bigg{)}$
$\displaystyle=2\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}B_{L-1}\sup_{\|\tilde{\mathbf{v}}\|_{2}\leq
1,\tilde{f}\in\mathcal{V}_{L-2}}\tilde{\mathbf{v}}^{\top}\sum_{j\in[n]}\epsilon_{j}\tilde{f}(\mathbf{x}_{j})\bigg{)}\leq
2\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}B_{L-1}\sup_{\tilde{f}\in\mathcal{V}_{L-2}}\Big{\|}\sum_{j\in[n]}\epsilon_{j}\tilde{f}(\mathbf{x}_{j})\Big{\|}_{2}\bigg{)}.$

We can apply the above inequality recursively and derive

$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1}}\Big{\|}\sum_{j\in[n]}\epsilon_{j}\tilde{f}(\mathbf{x}_{j})\Big{\|}_{2}\bigg{)}\leq
2^{L-1}\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}B_{L-1}\cdots
B_{1}\Big{\|}\sum_{j\in[n]}\epsilon_{j}\mathbf{x}_{j}\Big{\|}_{2}\bigg{)}.$

Furthermore, by Eq. (D.4) we know

$\displaystyle\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})$
$\displaystyle=\tau^{-1}\tau\bigg{(}\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})\bigg{)}$
$\displaystyle\leq\tau^{-1}\bigg{(}\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1}}\Big{\|}\sum_{j\in[n]}\epsilon_{j}\tilde{f}(\mathbf{x}_{j})\Big{\|}_{2}\bigg{)}\bigg{)}$
$\displaystyle\leq\tau^{-1}\bigg{(}2^{L-1}\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\bigg{(}B_{L-1}\cdots
B_{1}\Big{\|}\sum_{j\in[n]}\epsilon_{j}\mathbf{x}_{j}\Big{\|}_{2}\bigg{)}\bigg{)}$
$\displaystyle=\tau^{-1}\bigg{(}2^{L-1}\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\exp\bigg{(}d\lambda\Lambda^{2}B_{L}^{2}B^{2}_{L-1}\cdots
B_{1}^{2}\Big{\|}\sum_{j\in[n]}\epsilon_{j}\mathbf{x}_{j}\Big{\|}_{2}^{2}\bigg{)}\bigg{)},$

where the last identity follows from the definition of $\tilde{\tau}$. Let
$\lambda_{0}=d\lambda\Lambda^{2}B_{L}^{2}B^{2}_{L-1}\cdots B_{1}^{2}$. Then

$\displaystyle\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\exp\Big{(}\lambda_{0}\Big{\|}\sum_{j\in[n]}\epsilon_{j}\mathbf{x}_{j}\Big{\|}_{2}^{2}\Big{)}$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\exp\Big{(}\lambda_{0}\sum_{j\in[n]}\|\mathbf{x}_{j}\|_{2}^{2}+2\lambda_{0}\sum_{1\leq
i<j\leq n}\epsilon_{i}\epsilon_{j}\mathbf{x}_{i}^{\top}\mathbf{x}_{j}\Big{)}$
$\displaystyle\leq\exp\Big{(}\lambda_{0}\sum_{j\in[n]}\|\mathbf{x}_{j}\|_{2}^{2}\Big{)}\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\exp\Big{(}2\lambda_{0}\sum_{1\leq i<j\leq
n}\epsilon_{i}\epsilon_{j}\mathbf{x}_{i}^{\top}\mathbf{x}_{j}\Big{)}.$

We choose $\lambda=\frac{1}{8esd\Lambda^{2}B_{L}^{2}B^{2}_{L-1}\cdots
B_{1}^{2}}$, where $s=\big{(}\sum_{1\leq i<j\leq
n}(\mathbf{x}_{i}^{\top}\mathbf{x}_{j})^{2}\big{)}^{\frac{1}{2}}.$ Then it is
clear $\lambda_{0}=\frac{1}{8es}$. We can apply Lemma D.5 to derive that

$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\exp\Big{(}2\lambda_{0}\sum_{1\leq i<j\leq
n}\epsilon_{i}\epsilon_{j}\mathbf{x}_{i}^{\top}\mathbf{x}_{j}\Big{)}\leq 2$

and therefore

$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\exp\Big{(}\lambda_{0}\Big{\|}\sum_{j\in[n]}\epsilon_{j}\mathbf{x}_{j}\Big{\|}_{2}^{2}\Big{)}\leq
2\exp\Big{(}\lambda_{0}\sum_{j\in[n]}\|\mathbf{x}_{j}\|_{2}^{2}\Big{)}.$

We know $\tau^{-1}(x)=\sqrt{\lambda^{-1}\log x}$. It then follows that

$\displaystyle\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})$
$\displaystyle\leq\bigg{(}\lambda^{-1}(L-1)\log
2+\lambda^{-1}\log\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\exp\Big{(}\lambda_{0}\Big{\|}\sum_{j\in[n]}\epsilon_{j}\mathbf{x}_{j}\Big{\|}_{2}^{2}\Big{)}\bigg{)}^{\frac{1}{2}}$
$\displaystyle\leq\bigg{(}\lambda^{-1}(L-1)\log
2+\lambda^{-1}\log\Big{(}2\exp\Big{(}\lambda_{0}\sum_{j\in[n]}\|\mathbf{x}_{j}\|_{2}^{2}\Big{)}\Big{)}\bigg{)}^{\frac{1}{2}}$
$\displaystyle=\bigg{(}\lambda^{-1}L\log
2+\lambda^{-1}\lambda_{0}\sum_{j\in[n]}\|\mathbf{x}_{j}\|_{2}^{2}\bigg{)}^{\frac{1}{2}}$
$\displaystyle=\bigg{(}8esd\Lambda^{2}B_{L}^{2}B^{2}_{L-1}\cdots
B_{1}^{2}L\log 2+d\Lambda^{2}B_{L}^{2}B^{2}_{L-1}\cdots
B_{1}^{2}\sum_{j\in[n]}\|\mathbf{x}_{j}\|_{2}^{2}\bigg{)}^{\frac{1}{2}}$
$\displaystyle=\sqrt{d}\Lambda B_{L}B_{L-1}\cdots B_{1}\bigg{(}8esL\log
2+\sum_{j\in[n]}\|\mathbf{x}_{j}\|_{2}^{2}\bigg{)}^{\frac{1}{2}}.$

The proof is completed by noting $8e(\log 2)\leq 16$. ∎

######  Remark D.6.

Our proof of Proposition 5.5 is motivated by the arguments in Golowich et al.
[16], which studies Rademacher complexity bounds for DNNs with $d=1$. Our
analysis requires to introduce techniques to handle the difficulty of
considering $d$ features simultaneously. Indeed, we control the Rademacher
complexity for learning with $d$ features by

$\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})\leq\mathbb{E}_{\bm{\epsilon}}\bigg{(}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\sum_{t\in[d]}\Big{|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|}^{2}\bigg{)}^{\frac{1}{2}}.$

If $d=1$, this becomes

$\mathbb{E}_{\bm{\epsilon}}\sup_{f\in\mathcal{F}}\sum_{t\in[d]}\sum_{j\in[n]}\epsilon_{t,j}f_{t}(\mathbf{x}_{j})\leq\mathbb{E}_{\bm{\epsilon}}\sup_{\tilde{f}\in\mathcal{V}_{L-1},\tilde{\mathbf{v}}:\|\tilde{\mathbf{v}}\|_{2}\leq
1}\Big{|}\sum_{j\in[n]}\epsilon_{j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|},$

and the arguments in Golowich et al. [16] apply. There are two difficulties in
applying the arguments in Golowich et al. [16] to handle general
$d\in\mathbb{N}$. First, the term
$\sum_{t\in[d]}\Big{|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|}$
cannot be written as a Rademacher complexity due to the summation over
$t\in[d]$. Second, there is a square function of the term
$\Big{|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|}$.
To handle this difficulty, we introduce the function $\tau(x)=\exp(\lambda
x^{2})$ instead of the function $\tau(x)=\exp(\lambda x)$ in Golowich et al.
[16]. To this aim, we need to handle the moment generation function of a
Rademacher chaos variable $\sum_{1\leq i<j\leq
j}\epsilon_{i}\epsilon_{j}(\mathbf{x}_{i}^{\top}\mathbf{x}_{j})^{2}$, which is
not a sub-Gaussian variable. As a comparison, the analysis in Golowich et al.
[16] considers the moment generation function for a sub-Gaussian variable. One
can also use the following inequality

$\bigg{(}\sum_{t\in[d]}\Big{|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|}^{2}\bigg{)}^{\frac{1}{2}}\leq\sum_{t\in[d]}\Big{|}\sum_{j\in[n]}\epsilon_{t,j}\sigma(\tilde{\mathbf{v}}^{\top}\tilde{f}(\mathbf{x}_{j}))\Big{|},$

the latter of which can then be further controlled by the arguments in
Golowich et al. [16]. This, however, incurs a bound with a linear dependency
on $d$. As a comparison, our analysis gives a bound with a square-root
dependency on $d$.

##  Appendix E A General Vector-contraction Inequality for Rademacher
Complexities

In this section, we provide a general vector-contraction inequality for
Rademacher complexities, which recovers Lemma A.1 with $\tau(a)=a$. The lemma
is motivated from Lemma D.4 by considering a general convex and nondecreasing
$\tau$.

######  Theorem E.1.

Let $\mathcal{F}$ be a class of bounded functions
$f:\mathcal{Z}\mapsto\mathbb{R}^{d}$ which contains the zero function. Let
$\tau:\mathbb{R}_{+}\to\mathbb{R}_{+}$ be a continuous, non-decreasing and
convex function. Assume
$\tilde{g}_{1},\ldots,\tilde{g}_{n}:\mathbb{R}^{d}\to\mathbb{R}$ are
$G$-Lipschitz continuous w.r.t. $\|\cdot\|_{2}$ and satisfy
$\tilde{g}_{i}(\bm{0})=0$. Then

$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tau\Big{(}\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))\Big{)}\leq\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{nd}}\tau\Big{(}G\sqrt{2}\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\sum_{j=1}^{d}\epsilon_{i,j}f_{j}(\mathbf{x}_{i})\Big{)}.$
(E.1)

The following lemma is due to [28]. We provide here the proof for
completeness.

######  Lemma E.2.

Let $\mathcal{F}$ be a class of functions $f:\mathcal{Z}\mapsto\mathbb{R}^{d}$
and $g$ be any functional defined on $\mathcal{F}$. Assume that
$\tilde{g}_{1},\ldots,\tilde{g}_{n}:\mathbb{R}^{d}\to\mathbb{R}$ are
$G$-Lipschitz continuous w.r.t. $\|\cdot\|_{2}$. Then,

$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\sup_{f\in\mathcal{F}}\big{[}g(f)+\sum_{i=1}^{n}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))\big{]}\leq\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{nd}}\sup_{f\in\mathcal{F}}\Big{[}g(f)+G\sqrt{2}\sum_{i=1}^{n}\sum_{j=1}^{d}\epsilon_{i,j}f_{j}(\mathbf{x}_{i})\Big{]}.$
(E.2)

###### Proof.

We prove this result by induction. According to the symmetry between $f$ and
$\tilde{f}$, we derive

$\displaystyle\mathbb{E}_{\epsilon_{n}}\sup_{f\in\mathcal{F}}\big{[}g(f)+\sum_{i=1}^{n}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))\big{]}$
$\displaystyle=\frac{1}{2}\sup_{f,\tilde{f}\in\mathcal{F}}\Big{[}g(f)+g(\tilde{f})+\sum_{i=1}^{n-1}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))+\sum_{i=1}^{n-1}\epsilon_{i}\tilde{g}_{i}(\tilde{f}(\mathbf{x}_{i}))+\tilde{g}_{n}(f(\mathbf{x}_{n}))-\tilde{g}_{n}(\tilde{f}(\mathbf{x}_{n}))\Big{]}$
$\displaystyle=\frac{1}{2}\sup_{f,\tilde{f}\in\mathcal{F}}\Big{[}g(f)+g(\tilde{f})+\sum_{i=1}^{n-1}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))+\sum_{i=1}^{n-1}\epsilon_{i}\tilde{g}_{i}(\tilde{f}(\mathbf{x}_{i}))+\big{|}\tilde{g}_{n}(f(\mathbf{x}_{n}))-\tilde{g}_{n}(\tilde{f}(\mathbf{x}_{n}))\big{|}\Big{]},$
(E.3)

According to the Lipschitz property and Eq. (D.1), we derive

$\displaystyle\big{|}\tilde{g}_{n}(f(\mathbf{x}_{n}))-\tilde{g}_{n}(\tilde{f}(\mathbf{x}_{n}))\big{|}$
$\displaystyle\leq
G\big{\|}f(\mathbf{x}_{n})-\tilde{f}(\mathbf{x}_{n})\big{\|}_{2}\leq
G\sqrt{2}\mathbb{E}_{\epsilon_{n,1},\ldots,\epsilon_{n,j}}\big{|}\sum_{j=1}^{d}\epsilon_{n,j}\big{[}f_{j}(\mathbf{x}_{n})-\tilde{f}_{j}(\mathbf{x}_{n})\big{]}\big{|}.$

Plugging the above inequality back into (E.3) and using the Jensen’s
inequality, we get

$\displaystyle\mathbb{E}_{\epsilon_{n}}\sup_{f\in\mathcal{F}}\big{[}g(f)+\sum_{i=1}^{n}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))\big{]}$
$\displaystyle\leq\frac{1}{2}\mathbb{E}_{\epsilon_{n,1},\ldots,\epsilon_{n,j}}\sup_{f,\tilde{f}\in\mathcal{F}}\Big{[}g(f)+g(\tilde{f})+\sum_{i=1}^{n-1}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))+\sum_{i=1}^{n-1}\epsilon_{i}\tilde{g}_{i}(\tilde{f}(\mathbf{x}_{i}))+G\sqrt{2}\big{|}\sum_{j=1}^{d}\epsilon_{n,j}\big{[}f_{j}(\mathbf{x}_{n})-\tilde{f}_{j}(\mathbf{x}_{n})\big{]}\big{|}\Big{]}$
$\displaystyle=\frac{1}{2}\mathbb{E}_{\epsilon_{n,1},\ldots,\epsilon_{n,j}}\sup_{f,\tilde{f}\in\mathcal{F}}\Big{[}g(f)+g(\tilde{f})+\sum_{i=1}^{n-1}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))+\sum_{i=1}^{n-1}\epsilon_{i}\tilde{g}_{i}(\tilde{f}(\mathbf{x}_{i}))+G\sqrt{2}\sum_{j=1}^{d}\epsilon_{n,j}\big{[}f_{j}(\mathbf{x}_{n})-\tilde{f}_{j}(\mathbf{x}_{n})\big{]}\Big{]}$
$\displaystyle=\mathbb{E}_{\epsilon_{n,1},\ldots,\epsilon_{n,j}}\sup_{f\in\mathcal{F}}\Big{[}g(f)+\sum_{i=1}^{n-1}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))+G\sqrt{2}\sum_{j=1}^{d}\epsilon_{n,j}f_{j}(\mathbf{x}_{n})\Big{]},$

where we have used the symmetry in the second step.

The stated result can be derived by continuing the above deduction with
expectation over $\epsilon_{n-1}$, $\epsilon_{n-2}$ and so on. ∎

To prove Theorem E.1, we introduce the following lemmas on the approximation
of a continuous, non-decreasing and convex function. Let
$a_{+}=\max\\{a,0\\}$.

######  Lemma E.3.

Let $f:[a,b]\to\mathbb{R}_{+}$ be a continuous, non-decreasing and convex
function and $m\geq 2$. Let $a=x_{1}<\cdots<x_{m}=b$. Then the function
$\tilde{g}:[a,b]\to\mathbb{R}$ defined by

$\tilde{g}(x)=f(x_{k})+\frac{f(x_{k+1})-f(x_{k})}{x_{k+1}-x_{k}}(x-x_{k}),\quad\text{if
}x\in[x_{k},x_{k+1}]$

belongs to the set

$H_{[a,b]}:=\Big{\\{}c_{0}+\sum_{i=1}^{m}c_{i}(x-t_{i})_{+}:c_{i}\geq
0,i\in[n],t_{i}\in\mathbb{R},m\in\mathbb{N},x\in[a,b]\Big{\\}}.$ (E.4)

###### Proof.

Define

$\bar{f}(x)=f(x_{1})+\sum_{i=1}^{m-1}\frac{f(x_{i+1})-f(x_{i})}{x_{i+1}-x_{i}}\big{[}(x-x_{i})_{+}-(x-x_{i+1})_{+}\big{]}.$

We first show that $\bar{f}(x)=\tilde{g}(x)$ for all $x\in[a,b]$. Suppose that
$x\in[x_{k},x_{k+1})$. Then, it is clear that

$\displaystyle\bar{f}(x)$
$\displaystyle=f(x_{1})+\sum_{i=1}^{k-1}\frac{f(x_{i+1})-f(x_{i})}{x_{i+1}-x_{i}}\big{[}(x-x_{i})_{+}-(x-x_{i+1})_{+}\big{]}+\frac{f(x_{k+1})-f(x_{k})}{x_{k+1}-x_{k}}\big{[}(x-x_{k})_{+}-(x-x_{k+1})_{+}\big{]}$
$\displaystyle\qquad+\sum_{i=k+1}^{m-1}\frac{f(x_{i+1})-f(x_{i})}{x_{i+1}-x_{i}}\big{[}(x-x_{i})_{+}-(x-x_{i+1})_{+}\big{]}$
$\displaystyle=f(x_{1})+\sum_{i=1}^{k-1}\frac{f(x_{i+1})-f(x_{i})}{x_{i+1}-x_{i}}\big{[}(x-x_{i})-(x-x_{i+1})\big{]}+\frac{f(x_{k+1})-f(x_{k})}{x_{k+1}-x_{k}}\big{[}(x-x_{k})-0\big{]}$
$\displaystyle=f(x_{k})+\frac{f(x_{k+1})-f(x_{k})}{x_{k+1}-x_{k}}(x-x_{k})=\tilde{g}(x).$

We now show that $\bar{f}(x)$ belongs to the set $H_{[a,b]}$. Indeed, it
follows from $(x-x_{m})_{+}=0$ for all $x\leq x_{m}=b$ that

$\displaystyle\bar{f}(x)$
$\displaystyle=f(x_{1})+\sum_{i=1}^{m-1}\frac{f(x_{i+1})-f(x_{i})}{x_{i+1}-x_{i}}(x-x_{i})_{+}-\sum_{i=2}^{m}\frac{f(x_{i})-f(x_{i-1})}{x_{i}-x_{i-1}}(x-x_{i})_{+}$
$\displaystyle=f(x_{1})+\frac{f(x_{2})-f(x_{1})}{x_{2}-x_{1}}(x-x_{1})_{+}+\sum_{i=2}^{m-1}\Big{[}\frac{f(x_{i+1})-f(x_{i})}{x_{i+1}-x_{i}}-\frac{f(x_{i})-f(x_{i-1})}{x_{i}-x_{i-1}}\Big{]}(x-x_{i})_{+}.$

Therefore, $\bar{f}(x)$ can be written as
$\bar{f}(x)=c_{0}+\sum_{i=1}^{m-1}c_{i}(x-t_{i})_{+}$ with
$t_{i}=x_{i},c_{0}=f(x_{1}),c_{1}=\frac{f(x_{2})-f(x_{1})}{x_{2}-x_{1}}$ and
$c_{i}=\frac{f(x_{i+1})-f(x_{i})}{x_{i+1}-x_{i}}-\frac{f(x_{i})-f(x_{i-1})}{x_{i}-x_{i-1}},i=2,\ldots,m-1$.
The terms $c_{1},\ldots,c_{m-1}$ are all non-negative since $f$ is non-
decreasing and convex. The proof is completed. ∎

######  Lemma E.4.

If $f:[a,b]\to\mathbb{R}_{+}$ is continuous, non-decreasing and convex, then
$f$ belongs to the closure of $H_{[a,b]}$ defined in Eq. (E.4).

###### Proof.

Let $m\in\mathbb{N}$. We can find
$a=x_{1}^{(m)}<x_{2}^{(m)}<\cdots<x_{n+1}^{(m)}=b$ such that

$f(x_{k}^{(m)})-f(x_{k-1}^{(m)})\leq\frac{f(b)-f(a)}{n}.$

Introduce

$f^{(m)}(x):=f(x_{k}^{(m)})+\frac{f(x_{k+1}^{(m)})-f(x_{k}^{(m)})}{x_{k+1}^{(m)}-x_{k}^{(m)}}(x-x_{k}^{(m)})\quad\text{if
}x\in[x_{k}^{(m)},x_{k+1}^{(m)}].$

For any $x\in[x_{k}^{(m)},x_{k+1}^{(m)}]$, it follows from the convexity of
$f$ that

$\displaystyle|f^{(m)}(x)-f(x)|$
$\displaystyle=\Big{|}f(x_{k}^{(m)})-f(x)+\frac{\big{(}f(x_{k+1}^{(m)})-f(x_{k}^{(m)})\big{)}(x-x_{k}^{(m)})}{x_{k+1}^{(m)}-x_{k}^{(m)}}\Big{|}$
$\displaystyle=f(x_{k}^{(m)})-f(x)+\frac{\big{(}f(x_{k+1}^{(m)})-f(x_{k}^{(m)})\big{)}(x-x_{k}^{(m)})}{x_{k+1}^{(m)}-x_{k}^{(m)}}$
$\displaystyle\leq\frac{\big{(}f(x_{k+1}^{(m)})-f(x_{k}^{(m)})\big{)}(x-x_{k}^{(m)})}{x_{k+1}^{(m)}-x_{k}^{(m)}}\leq\frac{f(b)-f(a)}{n},$

from which we know $\lim_{n\to\infty}|f^{(m)}(x)-f(x)|=0$ for all $x\in[a,b]$.
Lemma E.3 shows that $f^{(m)}\in H_{[a,b]}$ for all $m\in\mathbb{N}$.
Therefore, $f$ belongs to the closure of $H_{[a,b]}$. The proof is completed.
∎

###### Proof of Theorem E.1.

According to the boundedness assumption of $f\in\mathcal{F}$ and the fact
$\bm{0}\in\mathcal{F}$, there exist $B>0$ such that

$0\leq\min\Big{\\{}\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i})),G\sqrt{2}\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\sum_{j=1}^{d}\epsilon_{i,j}f_{j}(\mathbf{x}_{i})\Big{\\}}\\\
\leq\max\Big{\\{}\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i})),G\sqrt{2}\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\sum_{j=1}^{d}\epsilon_{i,j}f_{j}(\mathbf{x}_{i})\Big{\\}}\leq
B$

for all $\bm{\epsilon}\in\\{\pm 1\\}^{n}$. Let $t\in\mathbb{R}$ be an
arbitrary number. Define $g_{t}:\mathcal{F}\mapsto\mathbb{R}$ by $g_{t}(f)=0$
for any $f\neq\bm{0}$ and $g_{t}(\bm{0})=t$. It is clear that

$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\sup_{f\in\mathcal{F}}\big{[}g_{t}(f)+\sum_{i=1}^{n}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))\big{]}=\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\max\Big{\\{}\sup_{f\in\mathcal{F}:f\neq\bm{0}}\big{[}\sum_{i=1}^{n}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))\big{]},t\Big{\\}}$

and

$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{nd}}\sup_{f\in\mathcal{F}}\big{[}g_{t}(f)+G\sqrt{2}\sum_{i=1}^{n}\sum_{j=1}^{d}\epsilon_{i,j}f_{j}(\mathbf{x}_{i})\big{]}=\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{nd}}\max\Big{\\{}G\sqrt{2}\sup_{f\in\mathcal{F}:f\neq\bm{0}}\big{[}\sum_{i=1}^{n}\sum_{j=1}^{d}\epsilon_{i,j}f_{j}(\mathbf{x}_{i})\big{]},t\Big{\\}}.$

Plugging the above identities into (E.2) with $g=g_{t}$ gives

$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\max\Big{\\{}\sup_{f\in\mathcal{F}:f\neq\bm{0}}\big{[}\sum_{i=1}^{n}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))\big{]},t\Big{\\}}\leq\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{nd}}\max\Big{\\{}G\sqrt{2}\sup_{f\in\mathcal{F}:f\neq\bm{0}}\big{[}\sum_{i=1}^{n}\sum_{j=1}^{d}\epsilon_{i,j}f_{j}(\mathbf{x}_{i})\big{]},t\Big{\\}}.$

If $t\geq 0$, the above inequality is equivalent to

$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\max\Big{\\{}\sup_{f\in\mathcal{F}}\big{[}\sum_{i=1}^{n}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))\big{]},t\Big{\\}}\leq\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{nd}}\max\Big{\\{}G\sqrt{2}\sup_{f\in\mathcal{F}}\big{[}\sum_{i=1}^{n}\sum_{j=1}^{d}\epsilon_{i,j}f_{j}(\mathbf{x}_{i})\big{]},t\Big{\\}}$
(E.5)

by noting $\tilde{g}_{i}(\bm{0})=0$ for all $i\in\mathbb{N}_{n}$. If $t<0$, it
follows from (E.2) with $g(f)=0$ that

$\displaystyle\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\max\Big{\\{}\sup_{f\in\mathcal{F}}\big{[}\sum_{i=1}^{n}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))\big{]},t\Big{\\}}$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\sup_{f\in\mathcal{F}}\big{[}\sum_{i=1}^{n}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))\big{]}\leq\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{nd}}\sup_{f\in\mathcal{F}}\Big{[}G\sqrt{2}\sum_{i=1}^{n}\sum_{j=1}^{d}\epsilon_{i,j}f_{j}(\mathbf{x}_{i})\Big{]}$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{nd}}\max\Big{\\{}G\sqrt{2}\sup_{f\in\mathcal{F}}\big{[}\sum_{i=1}^{n}\sum_{j=1}^{d}\epsilon_{i,j}f_{j}(\mathbf{x}_{i})\big{]},t\Big{\\}},$

where we have used $\tilde{g}_{i}(\bm{0})=0$ for all $i\in\mathbb{N}_{n}$ in
the first identity. That is, (E.5) holds for all $t\in\mathbb{R}$. Subtracting
$t$ from both sides of Eq. (E.5) gives

$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\Big{(}\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))-t\Big{)}_{+}\leq\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{nd}}\Big{(}G\sqrt{2}\sup_{f\in\mathcal{F}}\big{[}\sum_{i=1}^{n}\sum_{j=1}^{d}\epsilon_{i,j}f_{j}(\mathbf{x}_{i})\big{]}-t\Big{)}_{+},\quad\forall
t\in\mathbb{R},$ (E.6)

from which we know

$\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{n}}\tilde{\tau}\Big{(}\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\epsilon_{i}\tilde{g}_{i}(f(\mathbf{x}_{i}))\Big{)}\leq\mathbb{E}_{\bm{\epsilon}\sim\\{\pm
1\\}^{nd}}\tilde{\tau}\Big{(}G\sqrt{2}\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\sum_{j=1}^{d}\epsilon_{i,j}f_{j}(\mathbf{x}_{i})\Big{)},\quad\forall\tilde{\tau}\in
H_{[0,B]}.$

According to Lemma E.4, we know $\tau:[0,B]\to\mathbb{R}_{+}$ belongs to the
closure of $H_{[0,B]}$. Therefore, Eq. (E.1) holds. The proof is completed. ∎

##  Appendix F Lipschitz Continuity of Loss Functions

The following proposition is known in the literature [26]. We prove it for
completeness.

######  Proposition F.1.

  1. (a)

Let $\ell$ be defined as Eq. (3.2). Then $\ell$ is $1$-Lipschitz continuous
w.r.t. $\|\cdot\|_{\infty}$ and $1$-Lipschitz continuous w.r.t.
$\|\cdot\|_{2}$.

  2. (b)

Let $\ell$ be defined as Eq. (3.3). Then $\ell$ is $1$-Lipschitz continuous
w.r.t. $\|\cdot\|_{\infty}$ and $1$-Lipschitz continuous w.r.t.
$\|\cdot\|_{2}$.

###### Proof.

We first prove Part (a). For any $\mathbf{v}$ and $\mathbf{v}^{\prime}$, we
have

$\displaystyle|\ell(\mathbf{v})-\ell(\mathbf{v}^{\prime})|$