Contrastive learning is an efficient approach to self-supervised representation learning.
Although recent studies have made progress in the theoretical understanding of contrastive learning, the investigation of how to characterize the clusters of the learned representations is still limited.
In this paper, we aim to elucidate the characterization from theoretical perspectives.
To this end, we consider a kernel-based contrastive learning framework termed Kernel Contrastive Learning (KCL), where kernel functions play an important role when applying our theoretical results to other frameworks.
We introduce a formulation of the similarity structure of learned representations by utilizing a statistical dependency viewpoint.
We investigate the theoretical properties of the kernel-based contrastive loss via this formulation.
We first prove that the formulation characterizes the structure of representations learned with the kernel-based contrastive learning framework.
We show a new upper bound of the classification error of a downstream task, which explains that our theory is consistent with the empirical success of contrastive learning.
We also establish a generalization error bound of KCL.
Finally, we show a guarantee for the generalization ability of KCL to the downstream classification task via a surrogate bound.

§ INTRODUCTION

Recently, many studies on self-supervised representation learning have been paying much attention to contrastive learning [9, 11, 8, 26, 19, 40].
Through contrastive learning, encoder functions acquire how to encode unlabeled data to good representations by utilizing some information of similarity behind the data, where recent works [9, 11, 19] use several data augmentation techniques to produce pairs of similar data.
It is empirically shown by many works [9, 11, 8, 26, 19] that contrastive learning produces effective representations that are fully adaptable to downstream tasks, such as classification and transfer learning.

Besides the practical development of contrastive learning, the theoretical understanding of contrastive learning is essential to construct more efficient self-supervised learning algorithms.
In this paper, we tackle the following fundamental question of contrastive learning from the theoretical side:
How are the clusters of feature vectors output from an encoder model pretrained by contrastive learning characterized?

Recently, several works have shed light on several theoretical perspectives on this problem to study the generalization guarantees of contrastive learning to downstream classification tasks [3, 18, 26, 31, 80, 25, 88].
One of the primary approaches of these works is to introduce some similarity measures in the data. 3 has introduced the conditional independence assumption, which assumes that data $x$ and its positive data $x^{+}$ are sampled independently according to the conditional probability distribution $\mathcal{D}_{c}$, given the latent class $c$ drawn from the latent class distribution.
Although the concepts of latent classes and conditional independence assumption are often utilized to formulate semantic similarity of $x$ and $x^{+}$ [3, 4, 5, 6, 89], it is pointed out by several works [26, 80] that this assumption can be violated in practice.
Several works [26, 80] have introduced different ideas about the similarity between data to alleviate this assumption.
26 have introduced the notion called population augmentation graph to provide a theoretical analysis for Spectral Contrastive Learning (SCL) without the conditional independence assumption on $x$ and $x^{+}$.
Some works also focus on various graph structures [18, 25, 80].
Although these studies give interesting insights into contrastive learning, the applicable scope of their analyses is limited to specific objective functions.
Recently, several works [31, 88] consider the setup where raw data in the same latent class are aligned well in the sense that the augmented distance is small enough.
Although their theoretical guarantees can apply to multiple contrastive learning frameworks, their assumptions on the function class of encoders are strong, and it needs to be elucidated whether their guarantees can hold in practice.
Therefore, the investigation of the above question from unified viewpoints is ongoing, and more perspectives are required to understand the structure learned by contrastive learning.

§.§ Contributions

In this paper, we aim to theoretically investigate the above question from a unified perspective by introducing a formulation based on a statistical similarity between data.
The main contributions of this paper are summarized below:

* Since we aim to elucidate the mechanism of contrastive learning, we need to consider a unified framework that can apply to others, not specific frameworks such as SimCLR [9] and SCL [26].
40 pointed out that kernel-based self-supervised learning objectives are related to other contrastive losses, such as the InfoNCE loss [73, 9].
Therefore, via a kernel-based contrastive learning framework, other frameworks can be investigated through the lens of kernels.
Motivated by this, we utilize the framework termed Kernel Contrastive Learning (KCL) as a tool for achieving the goal.
The loss of KCL, which is called kernel contrastive loss, is a contrastive loss that has a simple and general form, where the similarity between two feature vectors is measured by a reproducing kernel [7, 59, 2] (Section <ref>).
One of our contributions is employing KCL to study the mechanism of contrastive learning from a new unified theoretical perspective.

* We introduce a new formulation of similarity between data (Section <ref>). Our formulation of similarity begins with the following intuition: if raw or augmented data $x$ and $x'$ belong to the same class, then the similarity measured by some function should be higher than a threshold.
Following this, we introduce a formulation (Assumption <ref>) based on the  similarity function (<ref>).

* We present the theoretical analyses towards elucidating the above question (Section <ref>).
We first show that KCL can distinguish the clusters of representations according to this formulation (Section <ref>).
This result shows that our formulation is closely connected to the mechanism of contrastive learning.
Next, we establish a new upper bound for the classification error of the downstream task (Section <ref>), which indicates that our formulation does not contradict the practical efficiency of contrastive learning shown by a line of work [9, 11, 26, 19].
Notably, our upper bound is valid under more realistic assumptions on the encoder functions, compared to the previous works [31, 88].
We also establish the generalization error bound for KCL (Section <ref>).
Finally, applying our theoretical results, we show a guarantee for the generalization of KCL to the downstream classification task via a surrogate bound (Section <ref>).

§.§ Related Work

Contrastive learning methods have been investigated from the empirical side  [8, 9, 11, 10].
9 propose a method called SimCLR, which utilizes a variant of InfoNCE [73, 9].
Several works have recently improved contrastive methods from various viewpoints [52, 19, 51, 8].
Contrastive learning is often utilized in several fundamental tasks, such as clustering [74] and domain adaptation [57], and applied to some domains such as vision [9], natural language processing [20], and speech [34].
Besides the contrastive methods, several works [23, 12] also study non-contrastive methods.
Investigation toward the theoretical understanding of contrastive learning is also a growing focus.
For instance, the generalization ability of contrastive learning to the downstream classification task has been investigated from many kinds of settings [3, 66, 26, 80, 6, 53, 31, 25, 88].
Several works investigate contrastive learning from various theoretical and empirical viewpoints to elucidate its mechanism, such as the geometric properties of contrastive losses [79, 31],
formulation of similarity between data [3, 26, 75, 80, 31, 18, 88],
inductive bias [53, 25],
transferablity [27, 55, 88],
feature suppression [10, 51], negative sampling methods [13, 52], and optimization viewpoints [83, 62].

Several works [40, 85, 68, 36, 18, 37] study the connection between contrastive learning and the theory of kernels.
40 investigate some contrastive losses, such as InfoNCE, from a kernel perspective.
85 show a relation between the kernel method and $f$-mutual information and apply their theory to contrastive learning.
68 tackle the conditional sampling problem using kernels as similarity measurements.
18 consider incorporating prior information in contrastive learning by using the theory of kernel functions.
37 connect several self-supervised learning algorithms to kernel methods through optimization problem viewpoints.
Note that different from these works, our work employs kernel functions to investigate a new unified perspective of contrastive learning via the statistical similarity.

Many previous works investigate various interpretations of self-supervised representation learning objectives. For instance, the InfoMax principle [50, 71], spectral clustering [26] (see 45 for spectral clustering), and Hilbert-Schmidt Independence Criterion (HSIC) [40] (see 22 for HSIC).
However, the investigation of contrastive learning from unified perspectives is worth addressing to elucidate its mechanism, as recent works on self-supervised representation learning tackle it from the various standpoints [31, 62, 36, 37, 17].

§ PRELIMINARIES

§.§ Problem Setup

We give the standard setup of contrastive learning.
Our setup closely follows that of 26, though we also introduce additional technically necessary settings to maintain the mathematical rigorousness.
Let $\overline{\mathbb{X}}\subset\mathbb{R}^{p}$ be a topological space consisting of raw data, and let $P_{\overline{\mathbb{X}}}$ be a Borel probability measure on $\overline{\mathbb{X}}$.
A line of work on contrastive learning [9, 11, 19, 26] uses data augmentation techniques to obtain similar augmented data points.
Hence, we define a set $\mathcal{T}$ of maps transforming a point $\overline{x}\in\overline{\mathbb{X}}$ into $\mathbb{R}^{p}$, where we assume that $\mathcal{T}$ includes the identity map on $\mathbb{R}^{p}$.
Then, let us define $\mathbb{X}=\bigcup_{t\in\mathcal{T}}\{t(\overline{x})\,:\,\overline{x}\in\overline{\mathbb{X}}\}$.
Every element $t$ in $\mathcal{T}$ can be regarded as a map returning an augmented data $x=t(\overline{x})$ for a raw data point $\overline{x}\in\overline{\mathbb{X}}$.
Note that since the identity map belongs to $\mathcal{T}$, $\overline{\mathbb{X}}$ is a subset of $\mathbb{X}$.
We endow $\mathbb{X}$ with some topology.
Let $\nu_{\mathbb{X}}$ be a $\sigma$-finite and non-negative Borel measure in $\mathbb{X}$.
Following the idea of 26, we denote $a(x|\overline{x})$ as the conditional probability density function of $x$ given $\overline{x}\sim P_{\overline{\mathbb{X}}}$ and define the weight function $w:\mathbb{X}\times \mathbb{X}\to\mathbb{R}$ as $w(x,x')=\mathbb{E}_{\overline{x}\sim P_{\overline{\mathbb{X}}}}\left[a(x|\overline{x})a(x'|\overline{x})\right].$
From the definition, $w$ is a joint probability density function on $\mathbb{X}\times\mathbb{X}$.
Let us define the marginal $w(\cdot)$ of the weight function to be $w(x)=\int w(x,x')d\nu_{\mathbb{X}}(x')$.
The marginal $w(\cdot)$ is also a probability density function on $\mathbb{X}$, and the corresponding probability measure is denoted by $dP_{\mathbb{X}}(x)=w(x)d\nu_{\mathbb{X}}(x)$.
Denote by $\mathbb{E}_{x,x^{+}}[\cdot], \mathbb{E}_{x,x^{-}}[\cdot]$ respectively, the expectation w.r.t. the probability measure $w(x,x')d\nu_{\mathbb{X}}^{\otimes 2}(x,x'), w(x)w(x')d\nu_{\mathbb{X}}^{\otimes 2}(x,x')$ on $\mathbb{X}\times\mathbb{X}$, where $\nu_{\mathbb{X}}^{\otimes 2}:=\nu_{\mathbb{X}}\otimes \nu_{\mathbb{X}}$ is the product measure on $\mathbb{X}\times\mathbb{X}$.
To rigorously formulate our framework of contrastive learning, we assume that the marginal $w$ is positive on $\mathbb{X}$.
Indeed, a point $x\in\mathbb{X}$ satisfying $w(x)=0$ is not included in the support of $a(\cdot|\overline{x})$ for $P_{\overline{\mathbb{X}}}$-almost surely $\overline{x}\in\overline{\mathbb{X}}$, which means that such a point $x$ merely appears as augmented data.

Let $f_{0}:\mathbb{X}\to\mathbb{R}^{d}$ be an encoder model mapping augmented data to the feature space, and let $\mathcal{F}_{0}$ be a class of functions consisting of such encoders.
In practice, $f_{0}$ is defined by a backbone architecture (e.g., ResNet [29]; see 9), followed by the additional multi-layer perceptrons called projection head [9].
We assume that $\mathcal{F}_{0}$ is uniformly bounded, i.e., there exists a universal constant $c\in\mathbb{R}$ such that $\sup_{f_{0}\in\mathcal{F}_{0}}\sup_{x\in\mathbb{X}}\|f_{0}(x)\|_{2}\leq c$.
For instance, a function space of bias-free fully connected neural networks on a bounded domain, where every neural network has the continuous activate function at each layer, satisfies this condition.
Since a feature vector output from the encoder model is normalized using the Euclidean norm in many empirical studies [9, 19] and several theoretical studies [79, 80], we consider the function space of normalized functions $\mathcal{F}=\{f\;|\;\exists f_{0}\in\mathcal{F}_{0},\;f(x)=f_{0}(x)/\|f_{0}(x)\|_{2}\textup{ for }\forall x\in\mathbb{X}\}$.
Here, to guarantee that every $f\in\mathcal{F}$ is well-defined, suppose that $\mathfrak{m}(\mathcal{F}_{0}):=\inf_{f\in\mathcal{F}}\inf_{x\in\mathbb{X}}\|f_{0}(x)\|_{2}>0$ holds.

Finally, we introduce several notations used throughout this paper.
Let $\mathbb{M}\subset\mathbb{X}$ be a measurable set, then we write

\begin{align*}
\mathbb{E}[f(x)|\mathbb{M}]:=\int_{\mathbb{X}}f(x)P_{\mathbb{X}}(dx|\mathbb{M})=P_{\mathbb{X}}(\mathbb{M})^{-1}\int_{\mathbb{M}}f(x)w(x)d\nu_{\mathbb{X}}(x).
\end{align*}

We also use the notation $\mathbb{E}[f(x);\mathbb{M}]:=\int_{\mathbb{M}}f(x)w(x)d\nu_{\mathbb{X}}(x)$.
Denote by $\mathbbm{1}_{\mathbb{M}}(\cdot)$, the indicator function of a set $\mathbb{M}$.
We also use $[n]:=\{1,\cdots,n\}$ for $n\in\mathbb{N}$.

§.§ Reproducing Kernels

We provide several notations of reproducing kenrels [7, 59, 2].
Let $k:\mathbb{S}^{d-1}\times\mathbb{S}^{d-1}\to\mathbb{R}$ be a real-valued, continuous, symmetric, and positive-definite kernel, where $\mathbb{S}^{d-1}$ denotes the unit hypersphere centered at the origin $\bm{0}\in\mathbb{R}^{d}$, and the positive-definiteness means that for every $\{z_{i}\}_{i=1}^{n}\subset\mathbb{S}^{d-1}$ and $\{c_{i}\}_{i=1}^{n}\subset\mathbb{R}$, $\sum_{i,j=1}^{n}c_{i}c_{j}k(z_{i},z_{j})\geq 0$ holds [7].
Let $\mathcal{H}_{k}$ be the Reproducing Kernel Hilbert Space (RKHS) with kernel $k$ [2], which satisfies $\phi(z)=\langle \phi,k(\cdot,z)\rangle_{\mathcal{H}_{k}}$ for all $\phi\in\mathcal{H}_{k}$ and $z\in\mathbb{S}^{d-1}$.
Denote $h(z)=k(\cdot, z)$ for $z\in\mathbb{S}^{d-1}$, where such a map is often called feature map [59].
Here, we impose the following condition.

For the kernel function $k$, there exists some $\rho$-Lipschitz function $\psi:[-1,1]\to\mathbb{R}$ such that for every $z,z'\in\mathbb{S}^{d-1}$, $k(z,z')=\psi(z^{\top}z')$ holds.

Several popular kernels in machine learning such as the linear kernel, quadratic kernel, and Gaussian kernel, satisfy Assumption <ref>.
Note that the Lipschitz condition in Assumption <ref> is useful to derive the generalization error bound for the kernel contrastive loss (see Section <ref>), and sometimes it can be removed when analyzing for a specific kernel. We use this assumption to present general results.
Here, we also use the following notion in this paper:

Let $\mathbb{M}\subset \mathbb{X}$ be a measurable set and $f\in\mathcal{F}$.
Define $\mu_{\mathbb{M}}(f):=\mathbb{E}_{P_{\mathbb{X}}}[h(f(x))|\mathbb{M}]$.
Then, $\mu_{\mathbb{M}}(f)\in\mathcal{H}_{k}$.

The quantity $\mu_{\mathbb{M}}(f)$ with a measurable subset $\mathbb{M}$ can be regarded as a variant of the kernel mean embedding [44].
The proof of Proposition <ref> is a slight modification of  44; see Appendix <ref>.

§ KERNEL CONTRASTIVE LEARNING

In this section, we introduce a contrastive learning framework to analyze the mechanism of contrastive learning.
In representation learning, the InfoNCE loss [73, 9] are widely used in application domains such as vision [9, 10, 19].
Following previous works [73, 9, 6], we define the InfoNCE loss as,

\begin{align*}
\end{align*}

where $\{x_{i}^{-}\}$ are i.i.d. random variables, $\tau>0$, and $M$ is the number of negative samples.
79 introduce the asymptotic of the InfoNCE loss:

\begin{align*}
\end{align*}

According to the theoretical analysis of 79, they show that the first term represents the alignment, i.e., the averaged closeness of feature vectors of the pair $(x,x^{+})$, while the second one indicates the uniformity, i.e., how far apart the feature vectors of negative samples $x,x'$ are.
Besides, 10 report the efficiency of the generalized contrastive losses, which have the additional weight hyperparameter.
Meanwhile, since we aim to study the mechanism of contrastive learning, a simple and general form of contrastive losses related to other frameworks is required.
Here, 40 find the connection between self-supervised learning and kernels by showing that some HSIC criterion is proportional to the objective function $\mathbb{E}_{x,x^{+}}[k(f(x),f(x^{+}))]-\mathbb{E}_{x,x^{-}}[k(f(x),f(x^{-}))]$ (for more detail, see Appendix <ref>).
Motivated by this connection, we consider a contrastive learning objective where a kernel function measures the similarity of the feature vectors of augmented data points.
More precisely, for the kernel function $k$ introduced in Section <ref>, we define the kernel contrastive loss as,

\begin{align*}
L_{\textup{KCL}}(f;\lambda)=-\mathbb{E}_{x,x^{+}}\left[k(f(x),f(x^{+}))\right]+\lambda \mathbb{E}_{x,x^{-}}\left[k(f(x),f(x^{-}))\right],
\end{align*}

where the weight hyperparameter $\lambda$ is inspired by 10.
Here, the kernel contrastive loss $L_{\textup{KCL}}$ is minimized during the pretraining stage of contrastive learning.
Throughout this paper, the contrastive learning framework with the kernel contrastive loss is called Kernel Contrastive Learning (KCL).

Next, we show the connections to other contrastive learning objectives.
First, for the InfoNCE loss, we consider the linear kernel contrastive loss $L_{\textup{LinKCL}}(f;\lambda)$ defined by selecting $k(z,z')=z^{\top}z'$.
Note that $L_{\textup{LinKCL}}$ and its empirical loss are also discussed in several works [78, 31].
For $L_{\textup{LinKCL}}(f;1)$, we have,

\begin{align}
\label{eq:lin vs nce}
\tau^{-1}L_{\textup{LinKCL}}(f;1)\leq L_{\textup{NCE}}(f;\tau)+\log M^{-1}.
\end{align}

In Appendix <ref>, we show a generalized inequality of (<ref>) for the generalized loss [10].
Note that similar relations hold when $L_{\textup{NCE}}$ is replaced with the asymptotic loss [79] or decoupled contrastive learning loss [84]; see Appendix <ref>.
Therefore, it is possible to analyze the InfoNCE loss and its variants via $L_{\textup{LinKCL}}(f;\lambda)$.

The kernel contrastive loss is also related to other contrastive learning objectives.
For instance, the quadratic kernel contrastive loss with the quadratic kernel $k(z,z')=(z^{\top}z')^{2}$ becomes a lower bound of the spectral contrastive loss [26] up to an additive constant (see Appendix <ref>).
Thus, theoretical analyses of the kernel contrastive loss can apply to other contrastive learning objectives.

Note that we empirically demonstrate that the KCL frameworks with the Gaussian kernel and quadratic kernel work, although simple; see Appendix <ref> for the experimental setup and Appendix <ref> and <ref> for the results in the supplementary material. The experimental results also motivate us to use KCL as a theoretical tool for studying contrastive learning.

§ A FORMULATION BASED ON STATISTICAL SIMILARITY

§.§ Key Ingredient: Similarity Function

To study the mechanism of contrastive learning, we introduce a notion of similarity between two augmented data points, which is a key component in our analysis.
Let us define,

\begin{align}
\label{def:similarity function}
\text{sim}(x,x';\lambda):=\frac{w(x,x')}{w(x)w(x')}-\lambda,
\end{align}

where $\lambda\geq 0$ is the weight parameter of $L_{\textup{KCL}}$, and $w(x,x')$ and $w(x)$ have been introduced in Section <ref>.
Note that (<ref>) is well-defined since $w(x)>0$ holds for every $x\in\mathbb{X}$.
The quantity $\text{sim}(x,x';\lambda)$ represents how much statistical dependency $x$ and $x'$ have.
The density ratio $w(x,x')/(w(x)w(x'))$ can be regarded as an instance of point-wise dependency introduced by 70.
The hyperparameter $\lambda$ controls the degree of relevance between two augmented data $x,x'$ via their (in-)dependency.
For instance, with the fixed $\lambda=1$, $\text{sim}(x,x';1)$ is positive if $w(x,x')>w(x)w(x')$, i.e., $x$ and $x'$ are correlated.

Here, we note that several theoretical works on representation learning [66, 36, 81] use the density ratio to study the optimal representations of several contrastive learning objectives.
66 focus on the fact that the minimizer of a logistic loss can be written in terms of the density ratio and utilize it to study landmark embedding [65].
36 connect the density ratio to the minimizers of several contrastive learning objectives and investigate the quality of representations related to the minimizers.
In addition, 81 study the minimizer of the spectral contrastive loss [26].
Meanwhile, we emphasize that the purpose of using the density ratio in (<ref>) is not to study the optimal representation of KCL but to give a formulation based on the statistical similarity between augmented data.

We can show that the kernel contrastive loss can be regarded as a relaxation of the population-level Normalized Cut problem [61], where the integral kernel is defined with (<ref>).
Thus, (<ref>) defines the similarity structure utilized by KCL.
Detailed arguments and comparison to related works [26, 62] can be found in Appendix <ref>.

§.§ Formulation and Example

We introduce the following formulation based on our problem setting.

There exist some $\delta\in\mathbb{R}$, number of clusters $K\in\mathbb{N}$, measurable subsets $\mathbb{M}_{1},\cdots,\mathbb{M}_{K}\subset\mathbb{X}$, and a deterministic labeling function $y:\mathbb{X}\to[K]$ such that the following conditions hold:

$\bigcup_{i=1}^{K}\mathbb{M}_{i}=\mathbb{X}$ holds.

For every $i\in[K]$, any points $x,x'\in\mathbb{M}_{i}$ satisfy $\textup{sim}(x,x';\lambda)\geq \delta$.

For every $x\in\mathbb{X}$ and the set of indices $J_{x}=\{j\in[K]\;|\;x\in\mathbb{M}_{j}\}$, $y(x)\in J_{x}$ holds. Moreover, each set $\{x\in\mathbb{X}\;|\;y(x)=i\}$ is measurable.

Assumption <ref> does not require that $\mathbb{M}_{1},\cdots,\mathbb{M}_{K}$ are disjoint, which is a realistic setting, as 80 show that clusters of augmented data can have inter-cluster connections depending on the strength of data augmentation.
The conditions (A) and  in Assumption <ref> guarantee that each subset $\mathbb{M}_{i}$ consists of augmented data that have high similarity.
The condition  enables to incorporate label information in our analysis.
Note that several works on contrastive learning [26, 53, 25] also employ deterministic labeling functions.

These conditions are useful to analyze the theory of contrastive learning.
To gain more intuition, we provide a simple example that satisfies Assumption <ref>.

[The proof can be found in Appendix <ref>]

Suppose that $\mathbb{X}$ consists of disjoint open balls $\mathbb{B}_{1},\cdots,\mathbb{B}_{K}$ of the same radius in $\mathbb{R}^{p}$, and $\overline{\mathbb{X}}=\mathbb{X}$.
Let $a(x|\overline{x})=\textup{vol}(\mathbb{B}_{1})^{-1}\sum_{i=1}^{K}\mathbbm{1}_{\mathbb{B}_{i}\times\mathbb{B}_{i}}(x,\overline{x})$, and let $p_{\overline{\mathbb{X}}}(\overline{x})=(K\textup{vol}(\mathbb{B}_{1}))^{-1}$ be the probability density function of $P_{\overline{\mathbb{X}}}$. Then, $w(x)>0$ and $\textup{sim}(x,x';\lambda)=K\mathbbm{1}_{\bigcup_{i\in[K]}\mathbb{B}_{i}\times\mathbb{B}_{i}}(x,x')-\lambda$ hold.
Hence, for instance let $\lambda=1$ and $\delta=K-1$, and take  $\mathbb{M}_{i}:=\mathbb{B}_{i}$.
Also, define $y:\mathbb{X}\to[K]$ as $y(x)=i$ if $x\in\mathbb{B}_{i}$ for some $i\in[K]$.
Then, Assumption <ref> is satisfied in this setting.

Here, theoretical formulations of similarity have been investigated by several works on contrastive learning [3, 26, 75, 80, 31, 25, 18, 88, 48].
The basic notions introduced by these works are:
latent classes of unlabeled data and conditional independence assumption [3],
graph structures of augmented data [26, 80, 25, 18],
the decomposition of unlabled data into the
content (i.e., invariant against data augmentation) and style (i.e., changeable by data augmentation) variables [75, 48],
and the geometric structure based on augmented distance and the concentration within class subsets [31, 88].
Meanwhile, our formulation in Assumption <ref> uses the similarity function (<ref>), which differs from the previous works.
Note that Assumption <ref> has some relation to Assumption 3 in 25; see Appendix <ref>.
Our formulation gives deeper insights into contrastive learning, as shown in Section <ref>.

§ THEORETICAL RESULTS

§.§ KCL as Representation Learning with Statistical Similarity

First, we connect the kernel contrastive loss to the formulation based on the similarity $\textup{sim}(x,x';\lambda)$.
The following theorem indicates that KCL has two effects on the way of representation learning, where the clusters $\mathbb{M}_{1},\cdots,\mathbb{M}_{K}$ involve to explain the mathematical relation.

Suppose that Assumption <ref> and <ref> hold.
Take $\delta\in\mathbb{R}$, $K\in\mathbb{N}$, and $\mathbb{M}_{1},\cdots,\mathbb{M}_{K}$ such that the conditions  and  in Assumption <ref> are satisfied.
Then, the following inequality holds for every $f\in\mathcal{F}$:

\begin{align}
\label{eq:decomposition}
\frac{\delta}{2}\cdot\mathfrak{a}(f)+\lambda\cdot\mathfrak{c}(f)\leq L_{\textup{KCL}}(f;\lambda)+R(\lambda).
\end{align}

where $R(\lambda)$ is a function of $\lambda$, $\mu_{i}(f)=\mu_{\mathbb{M}_{i}}(f)$, and

\begin{align*}
\mathfrak{a}(f)&:=\sum_{i=1}^{K}\mathbb{E}_{x,x^{-}}\left[\|h(f(x))-h(f(x^{-}))\|_{\mathcal{H}_{k}}^{2};\mathbb{M}_{i}\times\mathbb{M}_{i}\right],\\
\mathfrak{c}(f)&:=\sum_{i\neq j}P_{\mathbb{X}}(\mathbb{M}_{i})P_{\mathbb{X}}(\mathbb{M}_{j})\langle \mu_{i}(f),\mu_{j}(f)\rangle_{\mathcal{H}_{k}}.
\end{align*}

An illustration of Theorem <ref>. The clusters $\mathbb{M}_{1},\cdots,\mathbb{M}_{K}$ in the data space are mapped into the RKHS, where each cluster in the RKHS shrinks or expands (via $\mathfrak{a}(f)$) while maintaining the distance to other clusters (via $\mathfrak{c}(f)$).

For the proof of Theorem <ref>, see Appendix <ref>.
Note that the key point of the proof is the following usage of Assumption <ref>: for any $x,x'\in\mathbb{M}_{i}$, the inequality $\textup{sim}(x,x';\lambda)\geq\delta$ implies the relation $w(x,x')\geq (\lambda+\delta)w(x)w(x')$.
Here we briefly explain each symbol in Theorem <ref>.
The value $\mathfrak{a}(f)$ quantifies the concentration within each cluster consisting of the representations of augmented data in $\mathbb{M}_{i}$.
The quantity $\mathfrak{c}(f)$ measures how far the subsets $h(f(\mathbb{M}_{1})),\cdots,h(f(\mathbb{M}_{K}))$ are, since $\langle \mu_{i}(f),\mu_{j}(f)\rangle_{\mathcal{H}_{k}}=\int_{\mathbb{M}_{i}}\int_{\mathbb{M}_{j}}k(f(x),f(x'))P_{\mathbb{X}}(dx|\mathbb{M}_{i})P_{\mathbb{X}}(dx'|\mathbb{M}_{j})$ holds (see Lemma <ref> in Appendix <ref>).
These quantities indicate that representation learning by KCL can distinguish the subsets $\mathbb{M}_{1},\cdots,\mathbb{M}_{K}$ in the RKHS (see Figure <ref> for illustration).
The function $R(\lambda)$ includes the term that represents the hardness of the pretraining task in the space of augmented data $\mathbb{X}$: if the overlaps between two different subsets $\mathbb{M}_{i}$ and $\mathbb{M}_{j}$ expand, then $R(\lambda)$ increases (the precise definition is given in Appendix <ref>).

A key point of Theorem <ref> is that $\delta$ and $\lambda$ can determine how learned representations distribute in the RKHS.
If $\delta>0$, then representations of augmented data in each $\mathbb{M}_{i}$ tend to align as controlling the trade-off between $\mathfrak{a}(f)$ and $\mathfrak{c}(f)$.
For $\delta\leq 0$, not just the means $\mu_{1}(f),\cdots,\mu_{K}(f)$ but also the representations tend to scatter.
We remark that $\delta$ depends on the fixed weight $\lambda$ due to the condition (B) in Assumption <ref>.
Intuitively, larger $\lambda$ makes $\delta$ smaller and vice versa.

Here we should remark that under several assumptions, the equality holds in (<ref>), as shown below:

Suppose that Assumption <ref> and <ref> hold.
Take $\delta\in\mathbb{R}$, $K\in\mathbb{N}$, and $\mathbb{M}_{1},\cdots,\mathbb{M}_{K}$ such that the conditions  and  in Assumption <ref> are satisfied.
Suppose that $\mathbb{M}_{1},\cdots,\mathbb{M}_{K}$ are disjoint, and for every pair $(i,j)\in[K]\times[K]$ such that $i\neq j$, every $(x,x')\in\mathbb{M}_{i}\times\mathbb{M}_{j}$ satisfies $w(x,x')=0$.
Suppose that for every $i\in[K]$, it holds that $\textup{sim}(x,x';\lambda)=\delta$ for any $x,x'\in\mathbb{M}_{i}$.
Then, for every $f\in\mathcal{F}$, the equality holds in (<ref>), i.e.,

\begin{align*}
\end{align*}

The proof of Corollary <ref> can be found in Appendix <ref>.
The above corollary means that, under these assumptions, the minimization of the kernel contrastive loss is equivalent to that of the objective function $(\delta/2)\cdot\mathfrak{a}(f)+\lambda\cdot\mathfrak{c}(f)$.
Note that Example <ref> satisfies all the assumptions enumerated in the statement.
In summary, Theorem <ref> and Corollary <ref> imply that contrastive learning by the KCL framework is characterized as representation learning with the similarity structure of augmented data space $\mathbb{X}$.

§.§.§ Comparison to Related Work

The quantity $\mathfrak{a}(f)$ is closely related to the property called alignment [79] since the representations of similar data are learned to be close in the RKHS.
Also, the quantity $\mathfrak{c}(f)$ has some connection to divergence property [31] since it measures how far apart the means $\mu_{i}(f)$ and $\mu_{j}(f)$ are.
Although the relations between these properties and contrastive learning have been pointed out by 79, 31, we emphasize that our result gives a new characterization of the learned clusters.
Furthermore, this theorem also implies that the trade-off between $\mathfrak{a}(f)$ and $\mathfrak{c}(f)$ is determined with the threshold $\delta$ and the hyperparameter $\lambda$.
Therefore, Theorem <ref> provides deeper insights into understanding the mechanism of contrastive learning.

§.§ A New Upper Bound of the Classification Error

Next, we show how minimization of the kernel contrastive loss guarantees good performance in the downstream classification task, according to our formulation of similarity. To this end, we prove that the properties of contrastive learning shown in Theorem <ref> yield the linearly well-separable representations in the RKHS.
First, we quantify the linear separability as follows:
following 26, 53, under Assumption <ref>, for a model $f\in\mathcal{F}$, a linear weight $W:\mathcal{H}_{k}\to\mathbb{R}^{K}$, and a bias $\beta\in\mathbb{R}^{K}$, we define the downstream classification error as,

\begin{align*}
L_{\textup{Err}}(f, W, \beta;y):=P_{\mathbb{X}}\left(g_{f,W,\beta}(x)\neq y(x)\right),
\end{align*}

where $\textstyle g_{f,W,\beta}(x):=\textup{arg~max}_{i\in[K]}\{\langle W_{i},h(f(x))\rangle_{\mathcal{H}_{k}}+\beta_{i}\}$ for $W_{i}\in\mathcal{H}_{k}$ and $\beta_{i}\in\mathbb{R}$.
Note that we let $\textup{arg~max}$ and $\textup{arg~min}$ break tie arbitrary as well as 26.
Note that in our definition, after augmented data $x\in\mathbb{X}$ is encoded to $f(x)\in\mathbb{S}^{d-1}$, $f(x)$ is further mapped to $h(f(x))$ in the RKHS, and then linear classification is performed using $W$ and $\beta$.

To derive a generalization guarantee for KCL, we focus on the 1-Nearest Neighbor (NN) classifier in the RKHS $\mathcal{H}_{k}$ as a technical tool, which is a generalization of the 1-NN classifiers utilized in 52, 31.

Suppose $\mathbb{C}_{1},\cdots,\mathbb{C}_{K}$ are subsets of $\mathbb{X}$.
For a model $f:\mathbb{X}\to\mathbb{R}^{d}$, the 1-NN classifier $g_{\textup{1-NN}}:\mathbb{X}\to[K]$ associated with the RKHS $\mathcal{H}_{k}$ is defined as

\begin{align*}
\end{align*}

31 show that the 1-NN classifier they consider can be regarded as a mean classifier [3, 80] (see Appendix E in 31).
This fact can also apply to our setup: indeed, under Assumption <ref>, $g_{\textup{1-NN}}$ is equal to

\begin{align*}
g_{f,W_{\mu},\beta_{\mu}}(x)=\textup{arg~max}_{i\in[K]}\left\{\langle W_{\mu,i},h(f(x))\rangle_{\mathcal{H}_{k}}-\beta_{\mu,i}\right\},
\end{align*}

where $W_{\mu}:\mathcal{H}_{k}\to\mathbb{R}^{K}$ is defined as $W_{\mu}(\phi)_{i}:=\langle W_{\mu,i},\phi\rangle_{\mathcal{H}_{k}}=\langle \mu_{\mathbb{C}_{i}}(f),\phi\rangle_{\mathcal{H}_{k}}$ for each coordinate $i\in[K]$, and $\beta_{\mu,i}:=(\|\mu_{\mathbb{C}_{i}}(f)\|_{\mathcal{H}_{k}}^{2}+\psi(1))/2$ for $i\in[K]$.

Before presenting the result, we need the following notion:

An encoder $f\in\mathcal{F}$ is said to be meaningful if $\min_{i\neq j}\|\mu_{i}(f)-\mu_{j}(f)\|_{\mathcal{H}_{k}}^{2}>0$ holds.

Note that a meaningful encoder $f\in\mathcal{F}$ avoids the complete collapse of feature vectors [30, 35], where many works on self-supervised representation learning [9, 23, 12, 26, 40] introduce various architectures and algorithms to prevent it.
Now, the theoretical guarantee is presented:

Suppose that Assumption <ref> and <ref> hold.
Take $\delta\in\mathbb{R}$, $K\in\mathbb{N}$, $\mathbb{M}_{1},\cdots,\mathbb{M}_{K}$, and $y$ such that the conditions , , and  in Assumption <ref> are satisfied.
Then, for each meaningful encoder $f\in\mathcal{F}$, we have

\begin{align*}
L_{\textup{Err}}(f, W_{\mu},\beta_{\mu};y)\leq
\frac{8(K-1)}{\Delta_{\textup{min}}(f)\cdot\min_{i\in[K]}P_{\mathbb{X}}(\mathbb{M}_{i})}\mathfrak{a}(f)
\end{align*}

where $\Delta_{\textup{min}}(f)=\min_{i\neq j}\|\mu_{i}(f)-\mu_{j}(f)\|_{\mathcal{H}_{k}}^{2}$.

The proof of Theorem <ref> can be found in Appendix <ref>.
The upper bound in Theorem <ref> becomes smaller if the representations of any two points $x,x'$ belonging to $\mathbb{M}_{i}$ are closer for each $i\in[K]$ and the closest centers $\mu_{i}(f)$ and $\mu_{j}(f)$ of different subsets $\mathbb{M}_{i}$ and $\mathbb{M}_{j}$ become distant from each other.
Since $\|\mu_{i}(f)-\mu_{j}(f)\|_{\mathcal{H}_{k}}^{2}=-2\langle \mu_{i}(f),\mu_{j}(f)\rangle_{\mathcal{H}_{k}}+\|\mu_{i}(f)\|_{\mathcal{H}_{k}}^{2}+\|\mu_{j}(f)\|_{\mathcal{H}_{k}}^{2}$, Theorem <ref> and <ref> indicate that during the optimization for the kernel contrastive loss, the quantities $\mathfrak{a}(f)$ and $\mathfrak{c}(f)$ can contribute to making the learned representations linearly well-separable.
Thus, our theory is consistent with the empirical success of contrastive learning shown by a line of research [9, 11, 26, 19].

§.§.§ Comparison to Related Work

We discuss Theorem <ref>.
1) Several works [52, 31] also show that the classification loss or error is upper bounded by the quantity related to the alignment of feature vectors within each cluster.
However, their results do not address the following conjecture:
Does the distance between the centers of each cluster consisting of feature vectors affect the linear separability?
Theorem <ref> indicates that the answer is yes via the quantity $\Delta_{\textup{min}}(f)$.
Note that Theorem 3.2 of 88 implies a similar answer, but their result is for the squared loss and requires several strong assumptions on the encoder functions. Meanwhile, our Theorem <ref> for the classification error requires the meaningfulness of encoder functions (Definition <ref>), which is more practical than those of 88.
2) Furthermore, our result is different from previous works [52, 31, 88] in the problem setup. Indeed, 52 follow the setup of 3, and 31, 88 formulate their setup by imposing the $(\sigma,\delta)$-augmentation property to given latent class subsets.
Meanwhile, our formulation is mainly based on the statistical similarity (<ref>).
Furthermore, we note that our Theorem <ref> can be extended to the case that $K\in\mathbb{N}$, $\mathbb{M}_{1},\cdots,\mathbb{M}_{K}\subset\mathbb{X}$, and $y$ are taken to satisfy the conditions (A) and (C) in Assumption <ref> (see Theorem <ref> in Appendix <ref>), implying that our result can apply to other problem setups of contrastive learning.
Due to space limitations, we present more detailed explanations in Appendix <ref> and <ref>.

§.§ A Generalization Error Bound for KCL

Since in practice we minimize the empirical kernel contrastive loss, we derive a generalization error bound for KCL.
The empirical loss is defined as follows:
denote $dP_{+}(x,x')=w(x,x')d\nu_{\mathbb{X}}^{\otimes 2}(x,x')$.
Let $(X_{1},X_{1}'),\cdots,(X_{n},X_{n}')$ be pairs of random variables drawn independently from $P_{+}$, where $X_{i}$ and $X_{j}'$ are assumed to be independent for each pair of distinct indices $i,j\in[n]$.
Following the standard setup that a pair of two augmented samples is obtained by randomly transforming the same raw sample, which is considered in many empirical works [9, 11, 19], for each $i\in[n]$, we consider the case that $X_{i},X_{i}'$ are not necessarily independent.
The empirical kernel contrastive loss is defined as,

\begin{align}
\label{def:empirical kernel contrastive loss}
\widehat{L}_{\textup{KCL}}(f;\lambda)=-\frac{1}{n}\sum_{i=1}^{n}k(f(X_{i}),f(X_{i}'))+\frac{\lambda}{n(n-1)}\sum_{i\neq j}k(f(X_{i}),f(X_{j}')).
\end{align}

In the statement below, denote $\mathcal{Q}=\{f(\cdot)^{\top}f(\cdot):\mathbb{X}\times\mathbb{X}\to\mathbb{R}\;|\;f\in\mathcal{F}\}$.
Define the Rademacher complexity [43] as, $\mathfrak{R}_{n}^{+}(\mathcal{Q}):=\mathbb{E}_{P_{+},\sigma_{1:n}}[\sup_{q\in\mathcal{Q}}n^{-1}\sum_{i=1}^{n}\sigma_{i}q(X_{i},X_{i}')]$, where $\sigma_{1},\cdots,\sigma_{n}$ are independent random variables taking $\pm 1$ with probability one half for each.
We also define the Rademacher compexltiy $\mathfrak{R}_{n/2}^{-}(\mathcal{Q};s^{*})$ with the optimal choice $s^{*}$ from the symmetric group $S_{n}$ of degree $n$:

\begin{align*}
\mathfrak{R}_{n/2}^{-}(\mathcal{Q};s^{*}):=\max_{s\in S_{n}}\mathbb{E}_{\substack{X,X'\\\sigma_{1:(n/2)}}}\left[\sup_{q\in\mathcal{Q}}\frac{2}{n}\sum_{i=1}^{n/2}\sigma_{i}q(X_{s(2i-1)},X_{s(2i)}')\right].
\end{align*}

Note that $\mathfrak{R}_{n/2}^{-}(\mathcal{Q};s^{*})$ is related to the average of "sums-of-i.i.d." blocks technique for $U$-statistics explained in 14; for more detail, see also Remark <ref> in Appendix <ref>.
The generalization error bound for KCL is presented below:

Suppose that Assumption <ref> holds, and $n$ is even.
Furthermore, suppose that the minimizer $\widehat{f}\in\mathcal{F}$ of $\widehat{L}_{\textup{KCL}}(f;\lambda)$ exists. Then, with probability at least $1-2\varepsilon$ where $\varepsilon>0$, we have

\begin{align*}
L_{\textup{KCL}}(\widehat{f};\lambda)\leq L_{\textup{KCL}}(f;\lambda)+2\cdot\textup{Gen}(n,\lambda,\varepsilon),
\end{align*}

where $\mathfrak{R}_{n}(\mathcal{Q}):=\mathfrak{R}_{n}^{+}(\mathcal{Q})+\lambda\mathfrak{R}_{n/2}^{-}(\mathcal{Q};s^{*})$, and

\begin{align*}
\textup{Gen}(n,\lambda,\varepsilon)=O\left(\mathfrak{R}_{n}(\mathcal{Q})+(1+\lambda)\sqrt{\frac{\log(2/\varepsilon)}{n}}\right).
\end{align*}

In Appendix <ref>, we show that under some conditions, $\textup{Gen}(n,\lambda,\varepsilon)\downarrow 0$ holds as $n\to\infty$.

The proof of Theorem <ref> can be found in Appendix <ref>.
Since $X_{i},X_{i}'$ are not necessarily independent for each $i\in[n]$, the standard techniques (e.g., Theorem 3.3 in 43) are not applicable in the proof.
We instead utilize the results by 86 to overcome this difficulty, which is different from  the previous bounds for contrastive learning [3, 46, 26, 4, 85, 89, 39, 81] (see Appendix <ref> for more detail).
Here, if $\mathfrak{R}_{n}(\mathcal{Q})\downarrow 0$ as $n\to\infty$, then by using our result, we can prove the consistency of the empirical contrastive loss to the population one for each $f\in\mathcal{F}$.

§.§ Application of the Theoretical Results: A New Surrogate Bound

Recent works [3, 46, 66, 47, 26, 80, 4, 6, 5, 53, 89, 18] show that some contrastive learning objectives can be regarded as surrogate losses of the supervised loss or error in downstream tasks.
Here, 3 show that, a contrastive loss $L_{\textup{CL}}$ surrogates a supervised loss or error $L_{\textup{Sup}}$: for every $f\in\mathcal{F}$, $L_{\textup{sup}}(W\circ f)\lesssim L_{\textup{CL}}(f)+\alpha$ holds for some $\alpha\in\mathbb{R}$ and matrix $W$.
This type of inequality is also called surrogate bound [6].
3 show that the inequality guarantees that $L_{\textup{sup}}(W^{*}\circ\widehat{f})\lesssim L_{\textup{CL}}(f)+\alpha$ holds with high probability, where $\widehat{f}$ is a minimizer of the empirical loss for $L_{\textup{CL}}$, $W^{*}$ is the optimal weight, and $\alpha$ is some term.
Motivated by these works, we show a surrogate bound for KCL.

Suppose that Assumption <ref> and <ref> hold, $n$ is even, and there exists a minimizer $\widehat{f}$ of $\widehat{L}_{\textup{KCL}}(f;\lambda)$ such that $\widehat{f}$ is meaningful.
Take $\delta\in\mathbb{R}$, $K\in\mathbb{N}$, $\mathbb{M}_{1},\cdots,\mathbb{M}_{K}$, and $y$ such that the conditions , , and  in Assumption <ref> are satisfied.
Then, for any $f\in\mathcal{F}$ and $\varepsilon>0$, with probability at least $1-2\varepsilon$,

\begin{align*}
L_{\textup{Err}}(\widehat{f}, W^{*},\beta^{*};y)\lesssim L_{\textup{KCL}}(f;\lambda)+(1-\frac{\delta}{2})\mathfrak{a}(\widehat{f})-\lambda\mathfrak{c}(\widehat{f})+R(\lambda)+2\textup{Gen}(n,\lambda,\varepsilon),
\end{align*}

where $L_{\textup{Err}}(\widehat{f},W^{*},\beta^{*};y)=\inf_{W,\beta}L_{\textup{Err}}(\widehat{f},W,\beta;y)$, and $\lesssim$ omits the coefficient

The proof of Theorem <ref> can be found in Appendix <ref>.
This theorem indicates that minimization of the kernel contrastive loss in $\mathcal{F}$ can reduce the infimum of the classification error with high probability.
Note that since larger $\lambda$ can make $\delta$ smaller due to the relation in condition (B) of Assumption <ref>, larger $\lambda$ may result in enlarging $(1-\delta/2)\mathfrak{a}(\widehat{f})-\lambda\mathfrak{c}(\widehat{f})$ and loosening the upper bound if $\mathfrak{a}(\widehat{f})>0$ and $\mathfrak{c}(\widehat{f})<0$.
We empirically find that the KCL framework with larger $\lambda$ degrades its performance in the downstream classification task; see Appendix <ref>.

§.§.§ Comparison to Related Work

Several works also establish the surrogate bounds for some contrastive learning objectives [3, 46, 66, 47, 26, 80, 4, 6, 5, 53, 89, 18].
The main differences between the previous works and Theorem <ref> are summarized in three points:
1) Theorem <ref> indicates that the kernel contrastive loss is a surrogate loss of the classification error, while the previous works deal with other contrastive learning objectives.
2) Recent works [80, 6] prove that the InfoNCE loss is a surrogate loss of the cross-entropy loss.
However, since the theory of classification calibration losses (see e.g., 87) indicates that the relation between the classification loss and the cross-entropy loss is complicated under the multi-class setting, the relation between the InfoNCE loss and the classification error is non-trivial from the previous results.
On the other hand, combining Theorem <ref> and (<ref>), we can show that the InfoNCE loss is also a surrogate loss of the classification error.
Note that Theorem <ref> can apply to other contrastive learning objectives.
3) The bound in Theorem <ref> is established by introducing the formulation presented in Section <ref>.
Especially our bound includes the geometric quantity $\delta$ and hyperparameter $\lambda$.

§ CONCLUSION AND DISCUSSION

In this paper, we studied the characterization of the structure of the representations learned by contrastive learning.
By employing Kernel Contrastive Learning (KCL) as a unified framework, we showed that the formulation based on statistical similarity characterizes the clusters of learned representations and guarantees that the kernel contrastive loss minimization can yield good performance in the downstream classification task.
As a limitation of this paper,
we point out that in practice, it is challenging to compute the true $\textup{sim}(x,x';\lambda)$ and $\delta$ for datasets.
However, we believe that our theory promotes future theoretical and empirical research to investigate the practical success of contrastive learning via the sets of augmented data defined by $\textup{sim}(x,x';\lambda)$ and $\delta$.
Note that as recent works [70, 69] tackle the estimation of the point-wise dependency by using neural networks, the estimation problem is an important future work.
As a future work, it is worth studying how the selection of kernels affects the quality of representations via our theory.
The investigation of transfer learning perspectives of KCL is also an interesting future work, as recent works [55, 27, 88] also address the problem for some contrastive learning frameworks.

§.§.§ Ethical Statement

Since this paper mainly studies theoretical analysis of contrastive learning, it will not be thought that there is a direct negative social impact.
However, revealing detailed properties of contrastive learning could promote an opportunity to misuse the knowledge.
We point out that such wrong usage is not straightforward with the proposed method, as the application is not discussed much in the paper.

[1]
Arendt, W., Batty, C. J., Hieber, M., and Neubrander, F. (2011).
Vector-valued Laplace transforms and Cauchy problems.
Birkhäuser Basel.

[2]
Aronszajn, N. (1950).
Theory of reproducing kernels.
Transactions of the American Mathematical Society,

[3]
Arora, S., Khandeparkar, H., Khodak, M., Plevrakis, O., and Saunshi, N. (2019).
A theoretical analysis of contrastive unsupervised representation
In Proceedings of the 36th International Conference on Machine
Learning, volume 97 of Proceedings of Machine Learning Research, pages
5628–5637. PMLR.

[4]
Ash, J., Goel, S., Krishnamurthy, A., and Misra, D. (2022).
Investigating the role of negatives in contrastive representation
In Proceedings of The 25th International Conference on
Artificial Intelligence and Statistics, volume 151 of Proceedings of
Machine Learning Research, pages 7187–7209. PMLR.

[5]
Awasthi, P., Dikkala, N., and Kamath, P. (2022).
Do more negative samples necessarily hurt in contrastive learning?
In Proceedings of the 39th International Conference on Machine
Learning, volume 162 of Proceedings of Machine Learning Research,
pages 1101–1116. PMLR.

[6]
Bao, H., Nagano, Y., and Nozawa, K. (2022).
On the surrogate gap between contrastive and supervised losses.
In Proceedings of the 39th International Conference on Machine
Learning, volume 162 of Proceedings of Machine Learning Research,
pages 1585–1606. PMLR.

[7]
Berlinet, A. and Thomas-Agnan, C. (2004).
Reproducing kernel Hilbert spaces in probability and
Springer Science & Business Media.

[8]
Caron, M., Misra, I., Mairal, J., Goyal, P., Bojanowski, P., and Joulin, A.
Unsupervised learning of visual features by contrasting cluster
In Advances in Neural Information Processing Systems,
volume 33, pages 9912–9924. Curran Associates, Inc.

[9]
Chen, T., Kornblith, S., Norouzi, M., and Hinton, G. (2020a).
A simple framework for contrastive learning of visual
In International Conference on Machine Learning, pages
1597–1607. PMLR.

[10]
Chen, T., Luo, C., and Li, L. (2021).
Intriguing properties of contrastive losses.
In Advances in Neural Information Processing Systems,
volume 34, pages 11834–11845. Curran Associates, Inc.

[11]
Chen, X., Fan, H., Girshick, R., and He, K. (2020b).
Improved baselines with momentum contrastive learning.
arXiv preprint arXiv:2003.04297v1.

[12]
Chen, X. and He, K. (2021).
Exploring simple siamese representation learning.
In 2021 IEEE/CVF Conference on Computer Vision and Pattern
Recognition (CVPR), pages 15745–15753.

[13]
Chuang, C.-Y., Robinson, J., Lin, Y.-C., Torralba, A., and Jegelka, S. (2020).
Debiased contrastive learning.
In Advances in Neural Information Processing Systems,
volume 33, pages 8765–8775. Curran Associates, Inc.

[14]
Clémençon, S., Lugosi, G., and Vayatis, N. (2008).
Ranking and Empirical Minimization of U-statistics.
The Annals of Statistics, 36(2):844 – 874.

[15]
Coates, A., Ng, A., and Lee, H. (2011).
An analysis of single-layer networks in unsupervised feature
In Proceedings of the Fourteenth International Conference on
Artificial Intelligence and Statistics, volume 15 of Proceedings of
Machine Learning Research, pages 215–223. PMLR.

[16]
Deng, J., Dong, W., Socher, R., Li, L.-J., Li, K., and Fei-Fei, L. (2009).
Imagenet: A large-scale hierarchical image database.
In 2009 IEEE Conference on Computer Vision and Pattern
Recognition, pages 248–255. Ieee.

[17]
Dubois, Y., Ermon, S., Hashimoto, T., and Liang, P. (2022).
Improving self-supervised learning by characterizing idealized
In Advances in Neural Information Processing Systems.

[18]
Dufumier, B., Barbano, C. A., Louiset, R., Duchesnay, E., and Gori, P. (2022).
Rethinking positive sampling for contrastive learning with kernel.
arXiv preprint arXiv:2206.01646v1.

[19]
Dwibedi, D., Aytar, Y., Tompson, J., Sermanet, P., and Zisserman, A. (2021).
With a little help from my friends: Nearest-neighbor contrastive
learning of visual representations.
In 2021 IEEE/CVF International Conference on Computer Vision
(ICCV), pages 9568–9577.

[20]
Gao, T., Yao, X., and Chen, D. (2021).
SimCSE: Simple contrastive learning of sentence embeddings.
In Proceedings of the 2021 Conference on Empirical Methods in
Natural Language Processing, pages 6894–6910. Association for Computational

[21]
Goyal, P., Dollár, P., Girshick, R., Noordhuis, P., Wesolowski, L., Kyrola,
A., Tulloch, A., Jia, Y., and He, K. (2017).
Accurate, large minibatch sgd: Training imagenet in 1 hour.
arXiv preprint arXiv:1706.02677v2.

[22]
Gretton, A., Bousquet, O., Smola, A., and Schölkopf, B. (2005).
Measuring statistical dependence with hilbert-schmidt norms.
In Algorithmic Learning Theory, pages 63–77. Springer Berlin

[23]
Grill, J.-B., Strub, F., Altché, F., Tallec, C., Richemond, P.,
Buchatskaya, E., Doersch, C., Avila Pires, B., Guo, Z., Gheshlaghi Azar, M.,
Piot, B., Kavukcuoglu, K., Munos, R., and Valko, M. (2020).
Bootstrap your own latent - a new approach to self-supervised
In Advances in Neural Information Processing Systems,
volume 33, pages 21271–21284. Curran Associates, Inc.

[24]
Guedj, B. (2019).
A primer on pac-bayesian learning.
arXiv preprint arXiv:1901.05353v3.

[25]
HaoChen, J. Z. and Ma, T. (2023).
A theoretical study of inductive biases in contrastive learning.
The Eleventh International Conference on Learning Representations.

[26]
HaoChen, J. Z., Wei, C., Gaidon, A., and Ma, T. (2021).
Provable guarantees for self-supervised deep learning with spectral
contrastive loss.
In Advances in Neural Information Processing Systems,
volume 34, pages 5000–5011. Curran Associates, Inc.

[27]
HaoChen, J. Z., Wei, C., Kumar, A., and Ma, T. (2022).
Beyond separability: Analyzing the linear transferability of
contrastive representations to related subpopulations.
In Advances in Neural Information Processing Systems.

[28]
Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtanen, P.,
Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N. J., Kern, R.,
Picus, M., Hoyer, S., van Kerkwijk, M. H., Brett, M., Haldane, A., del
Río, J. F., Wiebe, M., Peterson, P., Gérard-Marchant, P.,
Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., and Oliphant,
T. E. (2020).
Array programming with NumPy.
Nature, 585(7825):357–362.

[29]
He, K., Zhang, X., Ren, S., and Sun, J. (2016).
Deep residual learning for image recognition.
In 2016 IEEE Conference on Computer Vision and Pattern
Recognition (CVPR), pages 770–778.

[30]
Hua, T., Wang, W., Xue, Z., Ren, S., Wang, Y., and Zhao, H. (2021).
On feature decorrelation in self-supervised learning.
In 2021 IEEE/CVF International Conference on Computer Vision
(ICCV), pages 9578–9588.

[31]
Huang, W., Yi, M., Zhao, X., and Jiang, Z. (2023).
Towards the generalization of contrastive self-supervised learning.
The Eleventh International Conference on Learning Representations.

[32]
Hunter, J. D. (2007).
Matplotlib: A 2d graphics environment.
Computing in Science & Engineering, 9(3):90–95.

[33]
Ioffe, S. and Szegedy, C. (2015).
Batch normalization: Accelerating deep network training by reducing
internal covariate shift.
In International Conference on Machine Learning, pages
448–456. PMLR.

[34]
Jiang, D., Li, W., Cao, M., Zou, W., and Li, X. (2021).
Speech SimCLR: Combining contrastive and reconstruction objective
for self-supervised speech representation learning.
In Proc. Interspeech 2021, pages 1544–1548.

[35]
Jing, L., Vincent, P., LeCun, Y., and Tian, Y. (2022).
Understanding dimensional collapse in contrastive self-supervised
International Conference on Learning Representations.

[36]
Johnson, D. D., Hanchi, A. E., and Maddison, C. J. (2023).
Contrastive learning can find an optimal basis for approximately
view-invariant functions.
The Eleventh International Conference on Learning Representations.

[37]
Kiani, B. T., Balestriero, R., Chen, Y., Lloyd, S., and LeCun, Y. (2022).
Joint embedding self-supervised learning in the kernel regime.
arXiv preprint arXiv:2209.14884v1.

[38]
Krizhevsky, A. (2009).
Learning multiple layers of features from tiny images.
Technical report.

[39]
Lei, Y., Yang, T., Ying, Y., and Zhou, D.-X. (2023).
Generalization analysis for contrastive representation learning.
arXiv preprint arXiv:2302.12383v2.

[40]
Li, Y., Pogodin, R., Sutherland, D. J., and Gretton, A. (2021).
Self-supervised learning with kernel dependence maximization.
In Advances in Neural Information Processing Systems,
volume 34, pages 15543–15556. Curran Associates, Inc.

[41]
Loshchilov, I. and Hutter, F. (2017).
SGDR: Stochastic gradient descent with warm restarts.
International Conference on Learning Representations.

[42]
McDiarmid, C. (1989).
On the method of bounded differences, page 148–188.
London Mathematical Society Lecture Note Series. Cambridge University

[43]
Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2018).
Foundations of machine learning.
MIT press.

[44]
Muandet, K., Fukumizu, K., Sriperumbudur, B., and Schölkopf, B. (2017).
Kernel mean embedding of distributions: A review and beyond.
Foundations and Trends® in Machine Learning,

[45]
Ng, A. Y., Jordan, M. I., and Weiss, Y. (2002).
On spectral clustering: Analysis and an algorithm.
In Advances in Neural Information Processing Systems, pages

[46]
Nozawa, K., Germain, P., and Guedj, B. (2020).
Pac-bayesian contrastive unsupervised representation learning.
In Conference on Uncertainty in Artificial Intelligence, pages
21–30. PMLR.

[47]
Nozawa, K. and Sato, I. (2021).
Understanding negative samples in instance discriminative
self-supervised representation learning.
In Advances in Neural Information Processing Systems,
volume 34, pages 5784–5797. Curran Associates, Inc.

[48]
Parulekar, A., Collins, L., Shanmugam, K., Mokhtari, A., and Shakkottai, S.
Infonce loss provably learns cluster-preserving representations.
arXiv preprint arXiv:2302.07920v1.

[49]
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen,
T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E.,
DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L.,
Bai, J., and Chintala, S. (2019).
Pytorch: An imperative style, high-performance deep learning library.
In Advances in Neural Information Processing Systems,
volume 32. Curran Associates, Inc.

[50]
Poole, B., Ozair, S., van den Oord, A., Alemi, A., and Tucker, G. (2019).
On variational bounds of mutual information.
In International Conference on Machine Learning, pages
5171–5180. PMLR.

[51]
Robinson, J., Sun, L., Yu, K., Batmanghelich, K., Jegelka, S., and Sra, S.
Can contrastive learning avoid shortcut solutions?
In Advances in Neural Information Processing Systems,
volume 34, pages 4974–4986. Curran Associates, Inc.

[52]
Robinson, J. D., Chuang, C.-Y., Sra, S., and Jegelka, S. (2021b).
Contrastive learning with hard negative samples.
International Conference on Learning Representations.

[53]
Saunshi, N., Ash, J., Goel, S., Misra, D., Zhang, C., Arora, S., Kakade, S.,
and Krishnamurthy, A. (2022).
Understanding contrastive learning requires incorporating inductive
In Proceedings of the 39th International Conference on Machine
Learning, volume 162 of Proceedings of Machine Learning Research,
pages 19250–19286. PMLR.

[54]
Shalev-Shwartz, S. and Ben-David, S. (2014).
Understanding machine learning: From theory to algorithms.
Cambridge University Press.

[55]
Shen, K., Jones, R. M., Kumar, A., Xie, S. M., Haochen, J. Z., Ma, T., and
Liang, P. (2022).
Connect, not collapse: Explaining contrastive learning for
unsupervised domain adaptation.
In Proceedings of the 39th International Conference on Machine
Learning, volume 162 of Proceedings of Machine Learning Research,
pages 19847–19878. PMLR.

[56]
Shi, J. and Malik, J. (2000).
Normalized cuts and image segmentation.
IEEE Transactions on Pattern Analysis and Machine Intelligence,

[57]
Singh, A. (2021).
Clda: Contrastive learning for semi-supervised domain adaptation.
In Advances in Neural Information Processing Systems,
volume 34, pages 5089–5101. Curran Associates, Inc.

[58]
Smola, A., Gretton, A., Song, L., and Schölkopf, B. (2007).
A hilbert space embedding for distributions.
In Algorithmic Learning Theory, pages 13–31. Springer Berlin

[59]
Steinwart, I. and Christmann, A. (2008).
Support vector machines.
Springer Science & Business Media.

[60]
Susmelj, I., Helle, M., Wirth, P., Prescott, J., and Ebner et al., M. (2020).

[61]
Terada, Y. and Yamamoto, M. (2019).
Kernel normalized cut: A theoretical revisit.
In International Conference on Machine Learning, pages
6206–6214. PMLR.

[62]
Tian, Y. (2022).
Understanding deep contrastive learning via coordinate-wise
In Advances in Neural Information Processing Systems.

[63]
Tian, Y., Krishnan, D., and Isola, P. (2020).
Contrastive multiview coding.
In Computer Vision – ECCV 2020, pages 776–794. Springer
International Publishing.

[64]
TorchVision maintainers and contributors (2016).
Torchvision: Pytorch's computer vision library.

[65]
Tosh, C., Krishnamurthy, A., and Hsu, D. (2021a).
Contrastive estimation reveals topic posterior information to linear
Journal of Machine Learning Research, 22(281):1–31.

[66]
Tosh, C., Krishnamurthy, A., and Hsu, D. (2021b).
Contrastive learning, multi-view redundancy, and linear models.
In Proceedings of the 32nd International Conference on
Algorithmic Learning Theory, volume 132 of Proceedings of Machine
Learning Research, pages 1179–1206. PMLR.

[67]
Trillos, N. G., Slepčev, D., Von Brecht, J., Laurent, T., and Bresson, X.
Consistency of cheeger and ratio graph cuts.
The Journal of Machine Learning Research, 17(1):6268–6313.

[68]
Tsai, Y.-H. H., Li, T., Ma, M. Q., Zhao, H., Zhang, K., Morency, L.-P., and
Salakhutdinov, R. (2022).
Conditional contrastive learning with kernel.
International Conference on Learning Representations.

[69]
Tsai, Y.-H. H., Ma, M. Q., Yang, M., Zhao, H., Morency, L.-P., and
Salakhutdinov, R. (2021).
Self-supervised representation learning with relative predictive
International Conference on Learning Representations.

[70]
Tsai, Y.-H. H., Zhao, H., Yamada, M., Morency, L.-P., and Salakhutdinov, R. R.
Neural methods for point-wise dependency estimation.
In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin,
H., editors, Advances in Neural Information Processing Systems,
volume 33, pages 62–72. Curran Associates, Inc.

[71]
Tschannen, M., Djolonga, J., Rubenstein, P. K., Gelly, S., and Lucic, M.
On mutual information maximization for representation learning.
International Conference on Learning Representations.

[72]
Tu, Z., Zhang, J., and Tao, D. (2019).
Theoretical analysis of adversarial learning: A minimax approach.
In Advances in Neural Information Processing Systems,
volume 32. Curran Associates, Inc.

[73]
van den Oord, A., Li, Y., and Vinyals, O. (2018).
Representation learning with contrastive predictive coding.
arXiv preprint arXiv:1807.03748v2.

[74]
Van Gansbeke, W., Vandenhende, S., Georgoulis, S., Proesmans, M., and Van Gool,
L. (2020).
Scan: Learning to classify images without labels.
In Proceedings of the European Conference on Computer Vision.

[75]
von Kügelgen, J., Sharma, Y., Gresele, L., Brendel, W., Schölkopf, B.,
Besserve, M., and Locatello, F. (2021).
Self-supervised learning with data augmentations provably isolates
content from style.
In Advances in Neural Information Processing Systems,
volume 34, pages 16451–16467. Curran Associates, Inc.

[76]
Von Luxburg, U. (2007).
A tutorial on spectral clustering.
Statistics and computing, 17(4):395–416.

[77]
Wainwright, M. J. (2019).
High-Dimensional Statistics: A Non-Asymptotic Viewpoint.
Cambridge Series in Statistical and Probabilistic Mathematics.
Cambridge University Press.

[78]
Wang, F. and Liu, H. (2021).
Understanding the behaviour of contrastive loss.
In 2021 IEEE/CVF Conference on Computer Vision and Pattern
Recognition (CVPR), pages 2495–2504.

[79]
Wang, T. and Isola, P. (2020).
Understanding contrastive representation learning through alignment
and uniformity on the hypersphere.
In International Conference on Machine Learning, pages
9929–9939. PMLR.

[80]
Wang, Y., Zhang, Q., Wang, Y., Yang, J., and Lin, Z. (2022a).
Chaos is a ladder: A new theoretical understanding of contrastive
learning via augmentation overlap.
International Conference on Learning Representations.

[81]
Wang, Z., Luo, Y., Li, Y., Zhu, J., and Schölkopf, B. (2022b).
Spectral representation learning for conditional moment models.
arXiv preprint arXiv:2210.16525v2.

[82]
Waskom, M. L. (2021).
seaborn: statistical data visualization.
Journal of Open Source Software, 6(60):3021.

[83]
Wen, Z. and Li, Y. (2021).
Toward understanding the feature learning process of self-supervised
contrastive learning.
In Proceedings of the 38th International Conference on Machine
Learning, volume 139 of Proceedings of Machine Learning Research,
pages 11112–11122. PMLR.

[84]
Yeh, C.-H., Hong, C.-Y., Hsu, Y.-C., Liu, T.-L., Chen, Y., and LeCun, Y.
Decoupled contrastive learning.
In Computer Vision – ECCV 2022, pages 668–684. Springer
Nature Switzerland.

[85]
Zhang, G., Lu, Y., Sun, S., Guo, H., and Yu, Y. (2022).
$f$-mutual information contrastive learning.

[86]
Zhang, R. R., Liu, X., Wang, Y., and Wang, L. (2019).
Mcdiarmid-type inequalities for graph-dependent variables and
stability bounds.
In Advances in Neural Information Processing Systems,
volume 32. Curran Associates, Inc.

[87]
Zhang, T. (2004).
Statistical analysis of some multi-category large margin
classification methods.
Journal of Machine Learning Research, 5:1225–1251.

[88]
Zhao, X., Du, T., Wang, Y., Yao, J., and Huang, W. (2023).
ArCL: Enhancing contrastive learning with augmentation-robust
The Eleventh International Conference on Learning Representations.

[89]
Zou, X. and Liu, W. (2023).
Generalization bounds for adversarial contrastive learning.
arXiv preprint arXiv:2302.10633v1.

§ PROOF IN SECTION <REF>

First we prove Proposition <ref>.

The proof of the claim closely follows the proof of Lemma 3.1 in 44 (see also 58), which shows that if $\mathbb{E}_{P}[\sqrt{k(x,x)}]<+\infty$ where $x\sim P$, then $\mathbb{E}_{P}[k(\cdot,x)]\in\mathcal{H}_{k}$.
For the sake of completeness, we provide the proof of Proposition <ref> by modifying the proof of 44 slightly.

Let $\mathbb{M}$ be a measurable set in $\mathbb{X}$.
Define $\mu_{\mathbb{M}}(f):=\mathbb{E}[h(f(x))|\mathbb{M}]$.
Our goal is to show that $\mu_{\mathbb{M}}(f)\in\mathcal{H}_{k}$ holds.
To this end, for $\phi\in\mathcal{H}_{k}$, we compute

\begin{align}
\left|\mathbb{E}\left[\phi(f(x))|\mathbb{M}\right]\right|
&=\left|\mathbb{E}\left[\langle \phi,k(\cdot,f(x))\rangle_{\mathcal{H}_{k}} |\mathbb{M}\right]\right|\nonumber\\
&\leq \mathbb{E}\left[\left|\langle \phi,k(\cdot,f(x))\rangle_{\mathcal{H}_{k}}\right| |\mathbb{M}\right]\nonumber\\
&\leq \mathbb{E}\left[\|\phi\|_{\mathcal{H}_{k}}\|k(\cdot,f(x))\|_{\mathcal{H}_{k}}|\mathbb{M}\right]\tag{Cauchy-Schwarz ineq.}\\
\end{align}

Since $\sup_{z,z'\in\mathbb{S}^{d-1}}k(z,z')<\infty$ holds, we have $\mathbb{E}[\sqrt{k(f(x),f(x))}|\mathbb{M}]<+\infty$.
Hence, the map $\phi\mapsto \mathbb{E}[\phi(f(x))|\mathbb{M}]$ is a bounded linear functional on $\mathcal{H}_{k}$, and thus from Riesz's representation theorem, there exists some $\xi\in\mathcal{H}_{k}$ such that $\mathbb{E}[\phi(f(x))|\mathbb{M}]=\langle \xi,\phi\rangle_{\mathcal{H}_{k}}$.
However, let $\phi=k(\cdot,z)$, then $\xi(z)=\langle \xi,k(\cdot,z)\rangle_{\mathcal{H}_{k}}=\mathbb{E}[k(f(x),z)|\mathbb{M}]$.
This implies $\xi=\mathbb{E}[k(f(x),\cdot)|\mathbb{M}]\in\mathcal{H}_{k}$.
Since $k$ is symmetric, we have $\mu_{\mathbb{M}}(f)=\mathbb{E}[k(\cdot,f(x))|\mathbb{M}]\in\mathcal{H}_{k}$.

§ PROOFS IN SECTION <REF>

§.§ Useful Lemmas for the Proof of Theorem <ref>

Before showing Theorem <ref>, we give several basic and useful lemmas that are used in the proof of the theorem.
Since the definition of $\mu_{\mathbb{M}}(f)$, where $\mathbb{M}$ is a measurable subset of $\mathbb{X}$ and $f\in\mathcal{F}$, is slightly different from the kernel mean embedding of the usual form [7, 44] due to the existence of the encoder function $f$, we provide the proof for each lemma for the sake of completeness.

Let $\{e_{j}\}$ be an orthonormal basis of $\mathcal{H}_{k}$, and let $\mathbb{M}$ be a measurable set.
Let $f\in\mathcal{F}$.
Then, the following identity holds for each $j$:

\begin{align*}
\int_{\mathbb{M}}\langle h(f(x)),e_{j}\rangle_{\mathcal{H}_{k}}P_{\mathbb{X}}(dx|\mathbb{M})=\langle \mu_{\mathbb{M}}(f),e_{j}\rangle_{\mathcal{H}_{k}}.
\end{align*}

We calculate,

\begin{align*}
\langle \mu_{\mathbb{M}}(f),e_{j}\rangle_{\mathcal{H}_{k}}
&=\left\langle \int_{\mathbb{M}}h(f(x))P_{\mathbb{X}}(dx|\mathbb{M}),e_{j}\right\rangle_{\mathcal{H}_{k}}\\
&=\left\langle \int_{\mathbb{M}}\sum_{j'}\langle h(f(x)),e_{j'}\rangle_{\mathcal{H}_{k}}e_{j'} P_{\mathbb{X}}(dx|\mathbb{M}),e_{j}\right\rangle_{\mathcal{H}_{k}}\\
&=\left\langle \sum_{j'}e_{j'}\int_{\mathbb{M}}\langle h(f(x)),e_{j'}\rangle_{\mathcal{H}_{k}}P_{\mathbb{X}}(dx|\mathbb{M}),e_{j}\right\rangle_{\mathcal{H}_{k}}\\
&=\int_{\mathbb{M}}\langle h(f(x)),e_{j}\rangle_{\mathcal{H}_{k}}P_{\mathbb{X}}(dx|\mathbb{M}),
\end{align*}

where in the third line, we use the Dominated Convergence Theorem for the Bochner integral (e.g., see Theorem 1.1.8 in 1).
Hence, we obtain the claim.

Let $\mathbb{M},\mathbb{M}'$ be measurable subsets of $\mathbb{X}$.
Let $f\in\mathcal{F}$.
Then, we have

\begin{align*}
\int_{\mathbb{M}}\int_{\mathbb{M}'}\langle h(f(x)),h(f(x'))\rangle_{\mathcal{H}_{k}}P_{\mathbb{X}}(dx|\mathbb{M})P_{\mathbb{X}}(dx'|\mathbb{M}')=\langle \mu_{\mathbb{M}}(f),\mu_{\mathbb{M}'}(f)\rangle_{\mathcal{H}_{k}}.
\end{align*}

Let $\{e_{j}\}$ be an orthonormal basis of $\mathcal{H}_{k}$.
Then we have,

\begin{align}
&\;\;\;\;\int_{\mathbb{M}}\int_{\mathbb{M}'}\langle h(f(x)),h(f(x'))\rangle_{\mathcal{H}_{k}}P_{\mathbb{X}}(dx|\mathbb{M})P_{\mathbb{X}}(dx'|\mathbb{M}')\nonumber\\
&=\int_{\mathbb{M}}\int_{\mathbb{M}'}\left\langle \sum_{j}\langle h(f(x)),e_{j}\rangle_{\mathcal{H}_{k}}e_{j},\sum_{j}\langle h(f(x')),e_{j}\rangle_{\mathcal{H}_{k}}e_{j}\right\rangle_{\mathcal{H}_{k}}P_{\mathbb{X}}(dx|\mathbb{M})P_{\mathbb{X}}(dx'|\mathbb{M}')\nonumber\\
&=\int_{\mathbb{M}}\int_{\mathbb{M}'} \sum_{j}\langle h(f(x)),e_{j}\rangle_{\mathcal{H}_{k}}\langle h(f(x')),e_{j}\rangle_{\mathcal{H}_{k}}P_{\mathbb{X}}(dx|\mathbb{M})P_{\mathbb{X}}(dx'|\mathbb{M}')\nonumber\\
\label{lem inner eq1}
&=\sum_{j}\int_{\mathbb{M}}\int_{\mathbb{M}'} \langle h(f(x)),e_{j}\rangle_{\mathcal{H}_{k}}\langle h(f(x')),e_{j}\rangle_{\mathcal{H}_{k}}P_{\mathbb{X}}(dx|\mathbb{M})P_{\mathbb{X}}(dx'|\mathbb{M}')\\
&=\sum_{j}\left(\int_{\mathbb{M}} \langle h(f(x)),e_{j}\rangle_{\mathcal{H}_{k}}P_{\mathbb{X}}(dx|\mathbb{M})\right)\left(\int_{\mathbb{M}'}\langle h(f(x')),e_{j}\rangle_{\mathcal{H}_{k}}P_{\mathbb{X}}(dx'|\mathbb{M}')\right)\nonumber\\
&=\sum_{j}\langle\mu_{\mathbb{M}}(f),e_{j}\rangle_{\mathcal{H}_{k}}\langle \mu_{\mathbb{M}'}(f),e_{j}\rangle_{\mathcal{H}_{k}}\tag{Lemma~\ref{lemma:reproducing property of kme}}\\
&=\left\langle\sum_{j}\langle \mu_{\mathbb{M}}(f),e_{j}\rangle_{\mathcal{H}_{k}}e_{j},\sum_{j}\langle \mu_{\mathbb{M}'}(f),e_{j}\rangle_{\mathcal{H}_{k}}e_{j}\right\rangle_{\mathcal{H}_{k}}\nonumber\\
&=\langle \mu_{\mathbb{M}}(f),\mu_{\mathbb{M}'}(f)\rangle_{\mathcal{H}_{k}},\nonumber
\end{align}

where in (<ref>) we use the Dominated Convergence Theorem.
Hence we obtain the claim.

§.§ Proof of Theorem <ref>

The following notation is used in the proof of Theorem <ref>.

Denote $M_{k}=\sup_{z,z'\in\mathbb{S}^{d-1}}\|k(\cdot,z)-k(\cdot,z')\|_{\mathcal{H}_{k}}^{2}$.
We define,

\begin{align*}
R(\lambda):=\frac{M_{k}}{2}\sum_{i\neq j}P_{+}((\mathbb{M}_{i}\cap\mathbb{M}_{j})\times(\mathbb{M}_{i}\cap\mathbb{M}_{j}))+\lambda\psi(1)\sum_{i=1}^{K}P_{\mathbb{X}}(\mathbb{M}_{i})\left(1-P_{\mathbb{X}}(\mathbb{M}_{i})\right)+(1-\lambda)\psi(1),
\end{align*}

where $dP_{+}(x,x')=w(x,x')d\nu_{\mathbb{X}}^{\otimes 2}(x,x')$.

Note that under Assumption <ref>, $k(z):=k(z,z)=\psi(z^{\top}z)=\psi(1)$ is a constant function on $\mathbb{S}^{d-1}$.
We are now ready to present the proof of Theorem <ref>.

It is convenient to analyze the following form instead of the kernel contrastive loss:

\begin{align}
\label{eq:thm 2 eq1}
\widetilde{L}_{\textup{KCL}}(f;\lambda):=\underbrace{\mathbb{E}_{x,x^{+}}\left[\|h(f(x))-h(f(x^{+}))\|_{\mathcal{H}_{k}}^{2}\right]}_{\textup{the positive term}}-\lambda\underbrace{\mathbb{E}_{x,x^{-}}\left[\|h(f(x))-h(f(x^{-}))\|_{\mathcal{H}_{k}}^{2}\right]}_{\textup{the negative term}}.
\end{align}

Note that, $\widetilde{L}_{\textup{KCL}}(f;\lambda)=2(1-\lambda)\psi(1)+2L_{\textup{KCL}}(f;\lambda)$ holds since $f(x)\in\mathbb{S}^{d-1}$ for all $x\in\mathbb{X}$.
For the positive term of $\widetilde{L}_{\textup{KCL}}(f)$, we can evaluate that,

\begin{align}
\label{eq:theorem 5.1 exeq1}
&\geq \int_{\bigcup_{i=1}^{K}\mathbb{M}_{i}\times\mathbb{M}_{i}}\|h(f(x))-h(f(x'))\|_{\mathcal{H}_{k}}^{2}w(x,x')d\nu_{\mathbb{X}}(x)d\nu_{\mathbb{X}}(x')\\
&\geq \sum_{i=1}^{K}\int_{\mathbb{M}_{i}\times\mathbb{M}_{i}}\|h(f(x))-h(f(x'))\|_{\mathcal{H}_{k}}^{2}w(x,x')d\nu_{\mathbb{X}}(x)d\nu_{\mathbb{X}}(x')\nonumber\\
\label{eq:theorem 5.1 exeq2}
-\sum_{j\neq i}\int_{(\mathbb{M}_{i}\cap\mathbb{M}_{j})\times(\mathbb{M}_{i}\cap\mathbb{M}_{j})}\|h(f(x))-h(f(x'))\|_{\mathcal{H}_{k}}^{2}w(x,x')d\nu_{\mathbb{X}}(x)d\nu_{\mathbb{X}}(x')\\
\label{eq:thm 2 eq2}
&\geq \sum_{i=1}^{K}\left(\int_{\mathbb{M}_{i}\times\mathbb{M}_{i}}\|h(f(x))-h(f(x'))\|_{\mathcal{H}_{k}}^{2}w(x,x')d\nu_{\mathbb{X}}(x)d\nu_{\mathbb{X}}(x')
-M_{k}\sum_{j\neq i}P_{+}((\mathbb{M}_{i}\cap\mathbb{M}_{j})\times(\mathbb{M}_{i}\cap\mathbb{M}_{j}))\right)
\end{align}

where in the second inequality we use the fact that

\begin{align*}
Q(\bigcup_{i=1}^{K}\mathbb{M}_{i}\times\mathbb{M}_{i})\geq \sum_{i=1}^{K}Q(\mathbb{M}_{i}\times\mathbb{M}_{i})-\sum_{i\neq j}Q((\mathbb{M}_{i}\times\mathbb{M}_{i})\cap(\mathbb{M}_{j}\times\mathbb{M}_{j})),
\end{align*}

for any probability measure $Q$ in $\mathbb{X}\times\mathbb{X}$, and in the last inequality we use the definition $M_{k}=\sup_{z,z'\in\mathbb{S}^{d-1}}\|k(\cdot,z)-k(\cdot,z')\|_{\mathcal{H}_{k}}^{2}$.
The first term of the above lower bound can be bounded as

\begin{align}
\label{eq:thm 2 eq3}
&\geq \sum_{i=1}^{K}\int_{\mathbb{M}_{i}\times\mathbb{M}_{i}}\|h(f(x))-h(f(x'))\|_{\mathcal{H}_{k}}^{2}\cdot(\lambda+\delta)w(x)w(x')d\nu_{\mathbb{X}}(x)d\nu_{\mathbb{X}}(x'),
\end{align}

where we utilize the definition of $\mathbb{M}_{i}$ for each $i\in\{1,\cdots,K\}$;
recall that due to the condition (B) in Assumption <ref>, for every $x,x'\in\mathbb{M}_{i}$ we have $\textup{sim}(x,x';\lambda)\geq \delta$.

On the other hand, for the negative term we can compute as follows:

\begin{align}
&\;\;\;\;\;\;\;\;-\int_{\mathbb{X}\times\mathbb{X}\setminus\left(\bigcup_{i=1}^{K}\mathbb{M}_{i}\times\mathbb{M}_{i}\right)}\|h(f(x))-h(f(x'))\|_{\mathcal{H}_{k}}^{2}w(x)w(x')d\nu_{\mathbb{X}}(x)d\nu_{\mathbb{X}}(x')\nonumber \\
&\geq -\sum_{i=1}^{K}\int_{\mathbb{M}_{i}\times\mathbb{M}_{i}}\|h(f(x))-h(f(x'))\|_{\mathcal{H}_{k}}^{2}w(x)w(x')d\nu_{\mathbb{X}}(x)d\nu_{\mathbb{X}}(x')\nonumber\\
\label{eq:theorem 5.1 exeq3}
\end{align}

where the last inequality is due to the union bound.
For the second term in the right hand side of the inequality above, we have

\begin{align}
&\geq -\sum_{i\neq j}\int_{\mathbb{M}_{i}\times\mathbb{M}_{j}}\|h(f(x))-h(f(x'))\|_{\mathcal{H}_{k}}^{2}w(x)w(x')d\nu_{\mathbb{X}}(x)d\nu_{\mathbb{X}}(x')\nonumber\\
\label{eq:theorem 5.1 exeq4}
&\;\;\;\;\;\;\;\;-\int_{\mathbb{X}\times\mathbb{X}\setminus\left(\bigcup_{i,j=1}^{K}\mathbb{M}_{i}\times\mathbb{M}_{j}\right)}\|h(f(x))-h(f(x'))\|_{\mathcal{H}_{k}}^{2}w(x)w(x')d\nu_{\mathbb{X}}(x)d\nu_{\mathbb{X}}(x') \\
\label{eq:negative term 1}
&\geq -\sum_{i\neq j}\int_{\mathbb{M}_{i}\times\mathbb{M}_{j}}\|h(f(x))-h(f(x'))\|_{\mathcal{H}_{k}}^{2}w(x)w(x')d\nu_{\mathbb{X}}(x)d\nu_{\mathbb{X}}(x')-M_{k}P_{\mathbb{X}}^{\otimes 2}\left(\mathbb{X}\times\mathbb{X}\setminus\left(\bigcup_{i,j=1}^{K}\mathbb{M}_{i}\times\mathbb{M}_{j}\right)\right).
\end{align}

Here, the second term of (<ref>) vanishes since Assumption <ref> implies $\mathbb{X}\times\mathbb{X}=\bigcup_{i,j=1}^{K}\mathbb{M}_{i}\times\mathbb{M}_{j}$.
The first term of (<ref>) is further lower bounded as,

\begin{align}
&\;\;\;\;-\sum_{i\neq j}\int_{\mathbb{M}_{i}\times\mathbb{M}_{j}}\|h(f(x))-h(f(x'))\|_{\mathcal{H}_{k}}^{2}w(x)w(x')d\nu_{\mathbb{X}}(x)d\nu_{\mathbb{X}}(x')\nonumber\\
&\geq 2\sum_{i\neq j}\left\{-\sup_{z\in\mathbb{S}^{d-1}}k(z,z)P_{\mathbb{X}}(\mathbb{M}_{i})P_{\mathbb{X}}(\mathbb{M}_{j})\right.\nonumber\\
\label{eq:theorem 5.1 exeq5}
&\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left.+\int_{\mathbb{M}_{i}\times\mathbb{M}_{j}}\langle h(f(x)),h(f(x'))\rangle_{\mathcal{H}_{k}}w(x)w(x')d\nu_{\mathbb{X}}(x)d\nu_{\mathbb{X}}(x')\right\}\\
&=2\sum_{i\neq j}\left\{-\sup_{z\in\mathbb{S}^{d-1}}k(z,z)P_{\mathbb{X}}(\mathbb{M}_{i})P_{\mathbb{X}}(\mathbb{M}_{j})+P_{\mathbb{X}}(\mathbb{M}_{i})P_{\mathbb{X}}(\mathbb{M}_{j})\langle \mu_{i}(f),\mu_{j}(f)\rangle_{\mathcal{H}_{k}}\right\}\tag{Lemma~\ref{lem:inner product}}\\
\end{align}

Thus for the negative term we obtain the inequality,

\begin{align}
\label{eq:thm 2 eq4}
&\geq -\sum_{i=1}^{K}\int_{\mathbb{M}_{i}\times\mathbb{M}_{i}}\|h(f(x))-h(f(x'))\|_{\mathcal{H}_{k}}^{2}w(x)w(x')d\nu_{\mathbb{X}}(x)d\nu_{\mathbb{X}}(x')\nonumber\\
\end{align}

Combining (<ref>),(<ref>),(<ref>), and (<ref>), we have

\begin{align}
\label{eq:thm 2 eq5}
&\;\;\;\; L_{\textup{KCL}}(f;\lambda)+(1-\lambda)\psi(1)\nonumber\\
&\geq \frac{\delta}{2}\sum_{i=1}^{K}\mathbb{E}_{x,x^{-}}\left[\|h(f(x))-h(f(x^{-}))\|_{\mathcal{H}_{k}}^{2};\mathbb{M}_{i}\times\mathbb{M}_{i}\right]+\lambda\mathfrak{c}(f)\nonumber\\
&\;\;\;\;\;\;-\frac{M_{k}}{2}\sum_{i\neq j}P_{+}((\mathbb{M}_{i}\cap\mathbb{M}_{j})\times(\mathbb{M}_{i}\cap\mathbb{M}_{j}))-\lambda\psi(1)\sum_{i=1}^{K}P_{\mathbb{X}}(\mathbb{M}_{i})\left(1-P_{\mathbb{X}}(\mathbb{M}_{i})\right).
\end{align}

Therefore, we complete the proof.

§.§ Proof of Corollary <ref>

The proof of Corollary <ref> is completed by checking whether the equality holds in each inequality that appears in the proof of Theorem <ref>.
We list the detail of the checks below:

(<ref>): Since $w(x,x')=0$ for any $(x,x')\in\mathbb{M}_{i}\times\mathbb{M}_{j}$ ($i\neq j$), we have $\int_{\mathbb{M}_{i}\times\mathbb{M}_{j}}\|h(f(x))-h(f(x'))\|_{\mathcal{H}_{k}}^{2}w(x,x')d\nu_{\mathbb{X}}(x)d\nu_{\mathbb{X}}(x')=0$. Here, we have the decomposition $\mathbb{X}\times\mathbb{X}=(\bigcup_{i=1}^{K}\mathbb{M}_{i})\times(\bigcup_{j=1}^{K}\mathbb{M}_{j})=\bigcup_{i,j=1}^{K}\mathbb{M}_{i}\times\mathbb{M}_{j}$, where $(\mathbb{M}_{i}\times\mathbb{M}_{j})\cap(\mathbb{M}_{i'}\times\mathbb{M}_{j'})=\emptyset$ for any $(i,j,i',j')$ such that $i\neq i'$ or $j\neq j'$, from the assumption that $\mathbb{M}_{1},\cdots,\mathbb{M}_{K}$ are disjoint. Hence, using the additivity of a probability measure yields the equality.

(<ref>): Since $\mathbb{M}_{i}\cap\mathbb{M}_{j}=\emptyset$ for $i,j\in[K]$ such that $i\neq j$, the first term in the right-hand-side of (<ref>) is equal to the first term in the left-hand-side of (<ref>). On the other hand, the second term in the right-hand-side of (<ref>) is equal to 0. Hence, the equality holds.

(<ref>): Since the second term of the right-hand-side of (<ref>) is 0 under the assumption that $\mathbb{M}_{i}\cap\mathbb{M}_{j}=\emptyset$ for $i,j$ $(i\neq j)$, the equality holds.

(<ref>): The equality holds from the assumption that for any $x,x'\in\mathbb{M}_{i}$ ($i\in[K]$), $\textup{sim}(x,x';\lambda)=\delta$ holds. Indeed, this assumption implies that $w(x,x')=(\lambda+\delta)w(x)w(x')$ for any $x,x'\in\mathbb{M}_{i}$.

(<ref>): Since $\mathbb{M}_{1}\times\mathbb{M}_{1},\cdots,\mathbb{M}_{K}\times\mathbb{M}_{K}$ are disjoint, the equality holds.

(<ref>): Since $\bigcup_{i,j=1}^{K}\mathbb{M}_{i}\times\mathbb{M}_{j}=\mathbb{X}\times\mathbb{X}$, the second term of the right-hand-side of (<ref>) is equal to 0. Thus, the equality holds.

(<ref>): The equality holds due to the same reason as (<ref>) above.

(<ref>): Since $\|h(f(x))\|_{\mathcal{H}_{k}}^{2}=k(f(x),f(x))=\psi(f(x)^{\top}f(x))=\psi(1)$ for any $x\in\mathbb{X}$ and $f\in\mathcal{F}$, the equality holds.

(<ref>): Since (<ref>) is the combination of (<ref>), (<ref>), (<ref>), and (<ref>), the equality in (<ref>) holds in this case.

(<ref>): Since (<ref>) is obtained by combining (<ref>), (<ref>), and (<ref>), the equality holds.

Therefore, we obtain the result.

§ PROOF IN SECTION <REF>

We present the proof of a generalized version of Theorem <ref>.
The generalized theorem is presented below.

Suppose that Assumption <ref> and <ref> hold.
Take $K\in\mathbb{N}$ and $\mathbb{M}_{1},\cdots,\mathbb{M}_{K}$ such that the condition  in Assumption <ref> is satisfied.
Let $\widetilde{\mathbb{M}}_{1},\cdots\widetilde{\mathbb{M}}_{K}$ be a disjoint partition of $\mathbb{X}$ satisfying $\widetilde{\mathbb{M}}_{i}\subset\mathbb{M}_{i}$ for each $i\in[K]$.
Define $\widetilde{y}:\mathbb{X}\to[K]$ as $\widetilde{y}(x)=i$ for every $x\in\widetilde{\mathbb{M}}_{i}$.
Then, for each meaningful encoder $f\in\mathcal{F}$, we have

\begin{align*}
L_{\textup{Err}}(f, W_{\mu},\beta_{\mu};\widetilde{y})\leq
\frac{8(K-1)}{\Delta_{\textup{min}}(f)\cdot\min_{i\in[K]}P_{\mathbb{X}}(\mathbb{M}_{i})}\mathfrak{a}(f)
\end{align*}

where $\Delta_{\textup{min}}(f)=\min_{i\neq j}\|\mu_{i}(f)-\mu_{j}(f)\|_{\mathcal{H}_{k}}^{2}$.

From the definition, we have $\widetilde{\mathbb{M}}_{i}\subset\mathbb{M}_{i}$ and $\widetilde{\mathbb{M}}_{i}\cap\widetilde{\mathbb{M}}_{j}=\emptyset$ for all the pairs of distinct indices $i,j\in[K]$.
Let us recall the definition of $L_{\textup{Err}}(f,W_{\mu},\beta_{\mu};\widetilde{y})$:

\begin{align*}
L_{\textup{err}}(f,W_{\mu},\beta_{\mu};\widetilde{y})=P_{\mathbb{X}}\left(g_{f,W_{\mu},\beta_{\mu}}(x)\neq \widetilde{y}(x)\right).
\end{align*}

Here recall that we let $\textup{arg~max}, \textup{arg~min}$ also breaks tie arbitrary.
For instance, if there are distinct integers $i_{1},\cdots,i_{j}\in[K]$ such that $g_{f,W_{\mu},\beta_{\mu}}(x)=\{i_{1},\cdots,i_{j}\}$, then we define $g_{f,W_{\mu},\beta_{\mu}}(x)=\widetilde{y}(x)$ if $\widetilde{y}(x)\in\{i_{1},\cdots,i_{j}\}$, and $g_{f,W_{\mu},\beta_{\mu}}(x)=i_{1}$ if $\widetilde{y}(x)\notin\{i_{1},\cdots,i_{j}\}$.
The event $\mathbb{A}:=\{x\;|\;g_{f,W_{\mu},\beta_{\mu}}(x)\neq \widetilde{y}(x)\}=\{x\;|\;g_{f,W_{\mu},\beta_{\mu}}(x)\neq \widetilde{y}(x)\}\cap\bigcup_{i=1}^{K}\widetilde{\mathbb{M}}_{i}\subset\mathbb{X}$ is a subset of the event $\mathbb{D}:=\bigcup_{i=1}^{K}\bigcup_{j\neq i}\{x\;|\;\|h(f(x))-\mu_{i}(f)\|_{\mathcal{H}_{k}}\geq \|h(f(x))-\mu_{j}(f)\|_{\mathcal{H}_{k}}\}\cap\widetilde{\mathbb{M}}_{i}$, since

\begin{align}
&\qquad\quad x\in\mathbb{A}\nonumber\\
&\iff \textup{arg~min}_{i\in[K]}\|h(f(x))-\mu_{i}(f)\|_{\mathcal{H}_{k}}\neq \widetilde{y}(x)\quad\textup{and}\quad x\in\bigcup_{i=1}^{K}\widetilde{\mathbb{M}}_{i}\tag{def. of $g_{f,W_{\mu},\beta_{\mu}}$ and $g_{\textup{1-NN}}$}\\
&\iff x\in \bigcup_{j\neq \widetilde{y}(x)} \{x'\;|\;\|h(f(x'))-\mu_{\widetilde{y}(x)}(h_{f})\|_{\mathcal{H}_{k}}\geq\|h(f(x'))-\mu_{j}(f)\|_{\mathcal{H}_{k}}\}\nonumber\\
&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\textup{and}\quad x\in\bigcup_{i=1}^{K}\widetilde{\mathbb{M}}_{i}\nonumber\\
&\iff x\in\bigcup_{j\neq \widetilde{y}(x)}\{x'\;|\;\|h(f(x'))-\mu_{\widetilde{y}(x)}(h_{f})\|_{\mathcal{H}_{k}}\geq \|h(f(x'))-\mu_{j}(f)\|_{\mathcal{H}_{k}}\}\cap\widetilde{\mathbb{M}}_{\widetilde{y}(x)}\nonumber\\
&\;\;\Longrightarrow x\in\bigcup_{i=1}^{K}\bigcup_{j\neq i}\{x'\;|\;\|h(f(x'))-\mu_{i}(f)\|_{\mathcal{H}_{k}}\geq \|h(f(x'))-\mu_{j}(f)\|_{\mathcal{H}_{k}}\}\cap\widetilde{\mathbb{M}}_{i}=\mathbb{D}.\nonumber
\end{align}

Define $\mathbb{L}_{ij}:=\{c(\mu_{j}(f)-\mu_{i}(f))\;|\;c\in\mathbb{R}\}\subset\mathcal{H}_{k}$ for every $i,j\in[K], i\neq j$.
Since each $\mathbb{L}_{ij}$ is a closed subspace of $\mathcal{H}_{k}$, for every $z\in\mathcal{H}_{k}$ there exists some $z_{1}\in\mathbb{L}_{ij}$ and $z_{2}\in\mathbb{L}_{ij}^{\perp}$ (where $\mathbb{L}_{ij}^{\perp}$ is the orthogonal complement space of $\mathbb{L}_{ij}$) such that $z$ admits the unique decomposition $z=z_{1}+z_{2}$.
Here define the projection $\widetilde{\pi}_{ij}:\mathcal{H}_{k}\to\mathbb{L}_{ij}$ as $\widetilde{\pi}_{ij}(z)=z_{1}$, and define the shifted projection $\pi_{ij}$ as
\pi_{ij}:\mathcal{H}_{k}\to\mathcal{H}_{k}, \pi_{ij}(z):=\widetilde{\pi}_{ij}(z-\mu_{i}(f))+\mu_{i}(f).
From the definition, we have that $\|\pi_{ij}(z)-\mu_{i}(f)\|_{\mathcal{H}_{k}}\leq\|z-\mu_{i}(f)\|_{\mathcal{H}_{k}}$ and $\|\pi_{ij}(z)-\mu_{j}(f)\|_{\mathcal{H}_{k}}\leq\|z-\mu_{j}(f)\|_{\mathcal{H}_{k}}$.

Hereafter, we use the abbreviation $\Delta_{ij}:=\Delta_{ij}(f)=\|\mu_{i}(f)-\mu_{j}(f)\|_{\mathcal{H}_{k}}^{2}$ for the sake of convenience.
Using $\pi_{ij}$, $i,j\in[K], i\neq j$, the event $\mathbb{D}$ can be decomposed into,

\begin{align*}
\mathbb{D}&=\underbrace{\left(\mathbb{D}\cap\left(\bigcup_{i=1}^{K}\bigcup_{j\neq i}\left\{x\;|\;\|\pi_{ij}(h(f(x)))-\mu_{j}(f)\|_{\mathcal{H}_{k}}\leq \frac{1}{2}\Delta_{ij}^{\frac{1}{2}}\right\}\cap\widetilde{\mathbb{M}}_{i}\right)\right)}_{=\;\mathbb{D}_{1}}\\
\underbrace{\left(
\mathbb{D}\cap\left(\bigcup_{i=1}^{K}\bigcup_{j\neq i}\left\{x\;|\;\|\pi_{ij}(h(f(x)))-\mu_{j}(f)\|_{\mathcal{H}_{k}}\leq \frac{1}{2}\Delta_{ij}^{\frac{1}{2}}\right\}\cap\widetilde{\mathbb{M}}_{i}\right)^{c}
\right)}_{=\;\mathbb{D}_{2}}.
\end{align*}

For $\mathbb{D}_{1}$, we have

\begin{align}
P_{\mathbb{X}}\left(\bigcup_{i=1}^{K}\bigcup_{j\neq i}\left\{x\;|\;\|\pi_{ij}(h(f(x)))-\mu_{j}(f)\|_{\mathcal{H}_{k}}\leq \frac{1}{2}\Delta_{ij}^{\frac{1}{2}}\right\}\cap\widetilde{\mathbb{M}}_{i}\right)\nonumber\\
&\leq \sum_{i=1}^{K}\sum_{j\neq i}P_{\mathbb{X}}\left(\left\{x\;|\;\|\pi_{ij}(h(f(x)))-\mu_{j}(f)\|_{\mathcal{H}_{k}}\leq \frac{1}{2}\Delta_{ij}^{\frac{1}{2}}\right\}\cap\widetilde{\mathbb{M}}_{i}\right)\tag{the union bound}\\
&\leq \sum_{i=1}^{K}\sum_{j\neq i}P_{\mathbb{X}}\left(\left\{x\;|\;-\|\pi_{ij}(h(f(x)))-\mu_{i}(f)\|_{\mathcal{H}_{k}}+\|\mu_{i}(f)-\mu_{j}(f)\|_{\mathcal{H}_{k}}\leq \frac{1}{2}\Delta_{ij}^{\frac{1}{2}}\right\}\cap\widetilde{\mathbb{M}}_{i}\right)\tag{triangle ineq.}\\
&=\sum_{i=1}^{K}\sum_{j\neq i}P_{\mathbb{X}}\left(\left\{x\;|\;\|\pi_{ij}(h(f(x)))-\mu_{i}(f)\|_{\mathcal{H}_{k}}\geq \frac{1}{2}\Delta_{ij}^{\frac{1}{2}}\right\}\cap\widetilde{\mathbb{M}}_{i}\right)\nonumber\\
&\leq \sum_{i=1}^{K}\sum_{j\neq i}\frac{4}{\Delta_{ij}}\mathbb{E}\left[\|\pi_{ij}(h(f(x)))-\mu_{i}(f)\|_{\mathcal{H}_{k}}^{2};\widetilde{\mathbb{M}}_{i}\right]\tag{Markov's ineq.}\\
&\leq \sum_{i=1}^{K}\sum_{j\neq i}\frac{4}{\Delta_{ij}}\mathbb{E}\left[\|h(f(x))-\mu_{i}(f)\|_{\mathcal{H}_{k}}^{2};\widetilde{\mathbb{M}}_{i}\right]\tag{def. of $\pi_{ij}$}\\
&\leq \sum_{i=1}^{K}\sum_{j\neq i}\frac{4}{\Delta_{ij}}\mathbb{E}\left[\|h(f(x))-\mu_{i}(f)\|_{\mathcal{H}_{k}}^{2};\mathbb{M}_{i}\right].\tag{def. of $\widetilde{\mathbb{M}_{i}}$}
\end{align}

For $\mathbb{D}_{2}$, we note that we can rewrite as,

\begin{align}
&= P_{\mathbb{X}}\left(\mathbb{D}\cap\left(\bigcup_{i=1}^{K}\bigcup_{j\neq i}\left\{x\;|\;\|\pi_{ij}(h(f(x)))-\mu_{j}(f)\|_{\mathcal{H}_{k}}\leq \frac{1}{2}\Delta_{ij}^{\frac{1}{2}}\right\}\cap\widetilde{\mathbb{M}}_{i}\right)^{c}\right)\nonumber\\
&= P_{\mathbb{X}}\left(\left(\bigcup_{i=1}^{K}\bigcup_{j\neq i}\{x\;|\;\|h(f(x))-\mu_{i}(f)\|_{2}\geq \|h(f(x))-\mu_{j}(f)\|_{2}\}\cap\widetilde{\mathbb{M}}_{i}\right)\right.
\cap\nonumber\\
\left.\left(\bigcap_{i=1}^{K}\bigcap_{j\neq i}\left\{x\;|\;\|\pi_{ij}(h(f(x)))-\mu_{j}(f)\|_{\mathcal{H}_{k}}> \frac{1}{2}\Delta_{ij}^{\frac{1}{2}}\right\}\cup\widetilde{\mathbb{M}}_{i}^{c}
\right)\right)\nonumber\\
&= P_{\mathbb{X}}\left(\bigcup_{i=1}^{K}\bigcup_{j\neq i}\bigcap_{i'=1}^{K}\bigcap_{j'\neq i'}\left(
\{x\;|\;\|h(f(x))-\mu_{i}(f)\|_{2}\geq \|h(f(x))-\mu_{j}(f)\|_{2}\}\cap\widetilde{\mathbb{M}}_{i}\cap\right.\right.\nonumber\\
\left.
\left(
\left\{x\;|\;\|\pi_{i'j'}(h(f(x)))-\mu_{j'}(h_{f})\|_{\mathcal{H}_{k}}> \frac{1}{2}\Delta_{i'j'}^{\frac{1}{2}}\right\}\cup\widetilde{\mathbb{M}}_{i'}^{c}
\right)\right)\Bigg)\nonumber
\end{align}

By using above, we have

\begin{align}
\label{eq:theorem 2 eq1}
&\leq P_{\mathbb{X}}\left(\bigcup_{i=1}^{K}\bigcup_{j\neq i}
\left(
\{x\;|\;\|h(f(x))-\mu_{i}(f)\|_{\mathcal{H}_{k}}\geq \|h(f(x))-\mu_{j}(f)\|_{\mathcal{H}_{k}}\right.\right.\nonumber\\
&\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\textup{ and }\|\pi_{ij}(h(f(x)))-\mu_{j}(f)\|_{\mathcal{H}_{k}}>\frac{1}{2}\Delta_{ij}^{\frac{1}{2}}\}\cap\widetilde{\mathbb{M}}_{i}
\Bigg)\\
&\leq P_{\mathbb{X}}\left(\bigcup_{i=1}^{K}\bigcup_{j\neq i}
\left(
\{x\;|\;\|h(f(x))-\mu_{i}(f)\|_{\mathcal{H}_{k}}\geq \frac{1}{2}\Delta_{ij}^{\frac{1}{2}}\}\cap\widetilde{\mathbb{M}}_{i}
\right)
\right)\tag{def. of $\pi_{ij}$}\\
&\leq \sum_{i=1}^{K}\sum_{j\neq i}P_{\mathbb{X}}\left(
\{x\;|\;\|h(f(x))-\mu_{i}(f)\|_{\mathcal{H}_{k}}\geq \frac{1}{2}\Delta_{ij}^{\frac{1}{2}}\}\cap\widetilde{\mathbb{M}}_{i}
\right)\tag{the union bound}\\
&\leq \sum_{i=1}^{K}\sum_{j\neq i}\frac{4}{\Delta_{ij}}\mathbb{E}\left[\|\pi_{ij}(h(f(x)))-\mu_{i}(f)\|_{\mathcal{H}_{k}}^{2};\widetilde{\mathbb{M}}_{i}\right]\tag{Markov's ineq.}\\
&\leq \sum_{i=1}^{K}\sum_{j\neq i}\frac{4}{\Delta_{ij}}\mathbb{E}\left[\|h(f(x))-\mu_{i}(f)\|_{\mathcal{H}_{k}}^{2};\widetilde{\mathbb{M}}_{i}\right]\tag{def. of $\pi_{ij}$}\\
&\leq \sum_{i=1}^{K}\sum_{j\neq i}\frac{4}{\Delta_{ij}}\mathbb{E}\left[\|h(f(x))-\mu_{i}(f)\|_{\mathcal{H}_{k}}^{2};\mathbb{M}_{i}\right]. \tag{def. of $\widetilde{\mathbb{M}_{i}}$}
\end{align}

Here, let us show (<ref>).
First let us fix $i,j\in[K]$, where $i\neq j$.
For $i',j'\in[K]$ satisfying $i'\neq j'$, we consider the following two cases.

* If $i'=i$ and $j'=j$, then $\widetilde{\mathbb{M}}_{i}\cap \widetilde{\mathbb{M}}_{i}^{c}=\emptyset$, which implies

\begin{align*}
&\hskip -1em
\left\{x\;|\;\|h(f(x))-\mu_{i}(f)\|_{2}\geq \|h(f(x))-\mu_{j}(f)\|_{2}\right\}\cap\widetilde{\mathbb{M}}_{i}\cap
\left(
\left\{x\;|\;\|\pi_{i'j'}(h(f(x)))-\mu_{j'}(h_{f})\|_{\mathcal{H}_{k}}> \frac{1}{2}\Delta_{i'j'}^{\frac{1}{2}}\right\}\cup\widetilde{\mathbb{M}}_{i'}^{c}
\right)\\
&=\left\{x\;|\;\|h(f(x))-\mu_{i}(f)\|_{\mathcal{H}_{k}}\geq \|h(f(x))-\mu_{j}(f)\|_{\mathcal{H}_{k}}\textup{ and }\|\pi_{ij}(h(f(x)))-\mu_{j}(f)\|_{\mathcal{H}_{k}}>\frac{1}{2}\Delta_{ij}^{\frac{1}{2}}\right\}\cap\widetilde{\mathbb{M}}_{i}.
\end{align*}

* if $i'\neq i$ or $j'\neq j$, then

\begin{align*}
&\hskip -1em
\{x\;|\;\|h(f(x))-\mu_{i}(f)\|_{2}\geq \|h(f(x))-\mu_{j}(f)\|_{2}\}\cap\widetilde{\mathbb{M}}_{i}\cap
\left(
\left\{x\;|\;\|\pi_{i'j'}(h(f(x)))-\mu_{j'}(h_{f})\|_{\mathcal{H}_{k}}> \frac{1}{2}\Delta_{i'j'}^{\frac{1}{2}}\right\}\cup\widetilde{\mathbb{M}}_{i'}^{c}
\right)\\
\end{align*}

\begin{align*}
&\;\;\;\;\bigcap_{i'=1}^{K}\bigcap_{j'\neq i'}\bigg(
\{x\;|\;\|h(f(x))-\mu_{i}(f)\|_{2}\geq \|h(f(x))-\mu_{j}(f)\|_{2}\}\\
\left(
\left\{x\;|\;\|\pi_{i'j'}(h(f(x)))-\mu_{j'}(h_{f})\|_{\mathcal{H}_{k}}> \frac{1}{2}\Delta_{i'j'}^{\frac{1}{2}}\right\}\cup\widetilde{\mathbb{M}}_{i'}^{c}
\right)\right)\\
&\subset \{x\;|\;\|h(f(x))-\mu_{i}(f)\|_{\mathcal{H}_{k}}\geq \|h(f(x))-\mu_{j}(f)\|_{\mathcal{H}_{k}}\textup{ and }\|\pi_{ij}(h(f(x)))-\mu_{j}(f)\|_{\mathcal{H}_{k}}>\frac{1}{2}\Delta_{ij}^{\frac{1}{2}}\}\cap\widetilde{\mathbb{M}}_{i}.
\end{align*}

By combining all the results, we obtain

\begin{align}
P_{\mathbb{X}}(\mathbb{A})&\leq P_{\mathbb{X}}(\mathbb{D})\nonumber\\
&\leq P_{\mathbb{X}}(\mathbb{D}_{1})+P_{\mathbb{X}}(\mathbb{D}_{2})\nonumber\\
&\leq \sum_{i=1}^{K}\sum_{j\neq i}\frac{8}{\Delta_{ij}}\mathbb{E}\left[\|h(f(x))-\mu_{i}(f)\|_{\mathcal{H}_{k}}^{2};\mathbb{M}_{i}\right]\nonumber\\
&\leq \frac{8(K-1)}{\Delta_{\textup{min}}(f)}\sum_{i=1}^{K}\mathbb{E}[\|h(f(x))-\mu_{i}(f)\|_{\mathcal{H}_{k}}^{2};\mathbb{M}_{i}]\nonumber\\
&\leq \frac{8(K-1)}{\Delta_{\textup{min}}(f)}\sum_{i=1}^{K}\frac{1}{P_{\mathbb{X}}(\mathbb{M}_{i})}\mathbb{E}_{x,x^{-}}[\|h(f(x))-h(f(x^{-}))\|_{\mathcal{H}_{k}}^{2};\mathbb{M}_{i}\times\mathbb{M}_{i}]\tag{Jensen's inequality}\\
&\leq \frac{8(K-1)}{\Delta_{\textup{min}}(f)\cdot\min_{i\in[K]}P_{\mathbb{X}}(\mathbb{M}_{i})}\mathfrak{a}(f),\nonumber
\end{align}

and we complete the proof.

From the definition of $y$, it is guaranteed that the sets $\{x\in\mathbb{X}\;|\;y(x)=i\}$ for $i=1,\cdots,K$ are disjoint and satisfy the relation $\{x\in\mathbb{X}\;|\;y(x)=i\}\subseteq \mathbb{M}_{i}$ for every $i\in[K]$.
Thus, Theorem <ref> can apply to this case, and we obtain the result.

§ PROOFS IN SECTION <REF>

§.§ Proof of Theorem <ref>

First, we prove Theorem <ref>.
Before that, we present the following theorem, which is a part of the proof of Theorem <ref>.

Let $(X_{1},X_{1}'),\cdots,(X_{n},X_{n}')$ be random variables introduced in Section <ref>.
Suppose that Assumption <ref> holds, and suppose that $n$ is even.
Then, with probability at least $1-\varepsilon$, the following inequality holds:

\begin{align*}
\sup_{f\in\mathcal{F}}\left(-\frac{1}{n(n-1)}\sum_{i\neq j}k(f(X_{i}),f(X_{j}'))+\mathbb{E}_{X,X^{-}}\left[k(f(X),f(X^{-}))\right]\right)\leq 2\rho\mathfrak{R}_{n/2}^{-}(\mathcal{Q};s^{*})+\sqrt{\frac{10b^{2}\log\left(1/\varepsilon\right)}{n}},
\end{align*}

where we define $\mathfrak{R}_{n/2}^{-}(\mathcal{Q};s^{*})$ with the symmetric group $S_{n}$ of degree $n$:

\begin{align*}
\mathfrak{R}_{n/2}^{-}(\mathcal{Q};s^{*}):=\max_{s\in S_{n}}\mathbb{E}_{\substack{X,X'\\\sigma_{1:(n/2)}}}\left[\sup_{f\in\mathcal{F}}\frac{2}{n}\sum_{i=1}^{n/2}\sigma_{i}f(X_{s(2i-1)})^{\top}f(X_{s(2i)}')\right].
\end{align*}

We remark that in Theorem <ref>, we need to deal with more delicate technical matters compared to the typical generalization error bounds (e.g., Theorem 3.3 of 43), since in our setup $X_{1},X_{1}',\cdots,X_{n},X_{n}'$ are not necessarily independent to each other.
We give the proof of Theorem <ref> in Appendix <ref>.

Now, we can show Theorem <ref>.

First observe that,

\begin{align*}
\sup_{f\in\mathcal{F}}\left(\frac{1}{n}\sum_{i=1}^{n}k(f(X_{i}),f(X_{i}^{'}))-\frac{\lambda}{n(n-1)}\sum_{i\neq j}k(f(X_{i}),f(X_{j}'))\right.\\
&\qquad\qquad\qquad\qquad -\mathbb{E}_{X,X^{+}}\left[k(f(X),f(X^{+}))\right]+\lambda\mathbb{E}_{X,X^{-}}\left[k(f(X),f(X^{-}))\right]\Bigg)\\
&\leq \underbrace{\sup_{f\in\mathcal{F}}\left(\frac{1}{n}\sum_{i=1}^{n}k(f(X_{i}),f(X_{i}^{'}))-\mathbb{E}_{X,X^{+}}\left[k(f(X),f(X^{+}))\right]\right)}_{\textup{(i)}}\\
&\qquad\quad +\lambda\underbrace{ \sup_{f\in\mathcal{F}}\left(-\frac{1}{n(n-1)}\sum_{i\neq j}k(f(X_{i}),f(X_{j}'))+\mathbb{E}_{X,X^{-}}\left[k(f(X),f(X^{-}))\right]\right)}_{\textup{(ii)}}.\\
\end{align*}

Let us define the function space $\mathcal{K}:=\{k(f(\cdot),f(\cdot)):\mathbb{X}\times\mathbb{X}\to\mathbb{R}\;|\;f\in\mathcal{F}\}$.
Then $\mathcal{K}$ is uniformly bounded with constant $b=\sup_{z,z\in\mathbb{S}^{d-1}}|k(z,z')|$.
Here we note that $b<+\infty$ holds since $k$ is continuous and $\mathbb{S}^{d-1}$ is compact; see Section <ref>.
From the ULLNs (Theorem 3.3 in 43), with probability at least $1-\varepsilon/2$, we have

\begin{align*}
\textup{(i)}\leq 2\mathfrak{R}_{n}^{+}(\mathcal{K})+\sqrt{\frac{2b^{2}\log\left(2/\varepsilon\right)}{n}}.
\end{align*}

Since $k$ is represented by $k(x,x')=\psi(x^{\top}x')$ for some $\rho$-Lipshitz function $\psi$ from Assumption <ref>, by applying Talagrand's lemma (Lemma 26.9 in 54) we have $\mathfrak{R}_{n}^{+}(\mathcal{K})\leq \rho\mathfrak{R}_{n}^{+}(\mathcal{Q})$. Hence, with probability at least $1-\varepsilon/2$, we have

\begin{align*}
\textup{(i)}\leq 2\rho\mathfrak{R}_{n}^{+}(\mathcal{Q})+\sqrt{\frac{2b^{2}\log\left(2/\varepsilon\right)}{n}}.
\end{align*}

For (ii), from Theorem <ref>, with probability at least $1-\varepsilon/2$ we have

\begin{align*}
\textup{(ii)}\leq 2\rho\mathfrak{R}_{n/2}^{-}(\mathcal{Q};s^{*})+\sqrt{\frac{10b^{2}\log\left(2/\varepsilon\right)}{n}}.
\end{align*}

Therefore, with probability at least $1-\varepsilon$ we have,

\begin{align}
\label{eq:gen err bound 1}
\sup_{f\in\mathcal{F}}\left(-\widehat{L}_{\textup{KCL}}(f;\lambda)+L_{\textup{KCL}}(f;\lambda)\right)\leq 2\rho\mathfrak{R}_{n}(\mathcal{Q})+\sqrt{\frac{2b^{2}\log\left(2/\varepsilon\right)}{n}}+\lambda\sqrt{\frac{10b^{2}\log\left(2/\varepsilon\right)}{n}},
\end{align}

where $\mathfrak{R}_{n}(\mathcal{Q}):=\mathfrak{R}_{n}^{+}(\mathcal{Q})+\lambda\mathfrak{R}_{n/2}^{-}(\mathcal{Q};s^{*})$.

Note that in the same way as the proof of the above probability bound, we have the following inequality: with probability at least $1-\varepsilon$,

\begin{align}
\label{eq:gen err bound 2}
\sup_{f\in\mathcal{F}}\left(\widehat{L}_{\textup{KCL}}(f;\lambda)-L_{\textup{KCL}}(f;\lambda)\right)\leq 2\rho\mathfrak{R}_{n}(\mathcal{Q})+\sqrt{\frac{2b^{2}\log\left(2/\varepsilon\right)}{n}}+\lambda\sqrt{\frac{10b^{2}\log\left(2/\varepsilon\right)}{n}}.
\end{align}

Hence, let $\widehat{f}$ be the minimizer of $\widehat{L}_{\textup{KCL}}(f;\lambda)$, then from (<ref>) and (<ref>), with probability at least $1-2\varepsilon$ we have

\begin{align*}
L_{\textup{KCL}}(\widehat{f};\lambda)\leq L_{\textup{KCL}}(f;\lambda)+ 4\rho\mathfrak{R}_{n}(\mathcal{Q})+2\sqrt{\frac{2b^{2}\log\left(2/\varepsilon\right)}{n}}+2\lambda\sqrt{\frac{10b^{2}\log\left(2/\varepsilon\right)}{n}},
\end{align*}

where we note that $\widehat{L}_{\textup{KCL}}(\widehat{f};\lambda)\leq \widehat{L}_{\textup{KCL}}(f;\lambda)$ from the definition of $\widehat{f}$.
Therefore, we complete the proof.

§.§ An Upper Bound of the Rademacher Complexity

In this section for the sake of simplicity, we consider the case in which for every $f\in\mathcal{F}$, there exists the unique function $f_{0}\in\mathcal{F}_{0}$ such that $f(x)=f_{0}(x)/\|f_{0}(x)\|_{2}$ for every $x\in\mathbb{X}$.
First let us recall the definition of a sub-Gaussian process:

A collection of zero-mean random variables $\{X_{\theta},\theta\in\mathbb{T}\}$ is a sub-Gaussian process with respect to a metric $\rho_{X}$ on $\mathbb{T}$ if

\begin{align*}
\mathbb{E}\left[e^{\lambda(X_{\theta}-X_{\widetilde{\theta}})}\right]\leq e^{\frac{\lambda^{2}\rho_{X}^{2}(\theta,\widetilde{\theta})}{2}}\quad\textup{for all}\;\theta,\widetilde{\theta}\in\mathbb{T}\textup{, and }\lambda\in\mathbb{R}.
\end{align*}

We next upper bound the Rademacher complexity via the chaining technique (Theorem 5.22 in 77).

Suppose $n$ is even.
For $\mathfrak{R}_{n}(\mathcal{Q})$, we have the upper bound,

\begin{align*}
\mathfrak{R}_{n}(\mathcal{Q})\leq \frac{64(1+\sqrt{2}\lambda)}{\mathfrak{m}(\mathcal{F}_{0})\sqrt{n}}\int_{0}^{Cd}\sqrt{\log \mathfrak{C}(u;\mathcal{F}_{0},\|\cdot\|_{\infty})}du,
\end{align*}

where $\|f_{0}\|_{\infty}:=\sup_{x\in\mathbb{X}}\|f_{0}(x)\|_{2}$ for $f_{0}\in\mathcal{F}_{0}$, $\mathfrak{m}(\mathcal{F}_{0})$ is defined in Section <ref>, $C$ is a constant independent of $d,n,\lambda$, and $\mathfrak{C}(u;\mathcal{F}_{0},\|\cdot\|_{\infty})$ is the $u$-covering number of $(\mathcal{F}_{0},\|\cdot\|_{\infty})$ (for the definition of covering number, see e.g., Definition 5.1 in 77).

In this proof, we follow the proof idea of 72 (see Lemma 5 in 72).
Since our setup is different from 72, we need to modify the proof and add several new techniques.

\begin{align*}
\end{align*}

where $\sigma_{1},\cdots,\sigma_{n}$ are Rademacher random variables that are independent to each other and to each $(X_{i},X_{i}')$, $i\in[n]$, $f_{0}\in\mathcal{F}_{0}$, $(X_{1},X_{1}),\cdots,(X_{n},X_{n}')$ are the random vectors defined in Section <ref>, and

\begin{align*}
\end{align*}

Also, let us recall the assumption for $\mathcal{F}_{0}$ introduced in Section <ref>: for every $f\in\mathcal{F}$, there exists the unique function $f_{0}\in\mathcal{F}_{0}$ such that $f(x)=f_{0}(x)/\|f_{0}(x)\|_{2}$ for every $x\in\mathbb{X}$.
We show that $\{Z_{f_{0}}\}_{f_{0}\in\mathcal{F}_{0}}$ is a sub-Gaussian process as follows: note that, for every $f_{1,0},f_{2,0}\in\mathcal{F}_{0}$,

\begin{align}
&\leq \frac{\mathfrak{m}(\mathcal{F}_{0})}{2\sqrt{n}}\left|f_{1}(X_{i})^{\top}f_{1}(X_{i}')-f_{2}(X_{i})^{\top}f_{2}(X_{i}')\right|\tag{def. of $\sigma_{i}$}\\
&\leq \frac{\mathfrak{m}(\mathcal{F}_{0})}{2\sqrt{n}}\left(\left|f_{1}(X_{i})^{\top}f_{1}(X_{i}')-f_{1}(X_{i})^{\top}f_{2}(X_{i}')\right|+\left|f_{1}(X_{i})^{\top}f_{2}(X_{i}')-f_{2}(X_{i})^{\top}f_{2}(X_{i}')\right|\right)\tag{triangle ineq.}\\
&\leq \frac{\mathfrak{m}(\mathcal{F}_{0})}{2\sqrt{n}}\left(\|f_{1}(X_{i})\|_{2}\|f_{1}(X_{i}')-f_{2}(X_{i}')\|_{2}+\|f_{1}(X_{i})-f_{2}(X_{i})\|_{2}\|f_{2}(X_{i}')\|_{2}\right)\tag{Cauchy-Schwarz ineq.}\\
&\leq \frac{\mathfrak{m}(\mathcal{F}_{0})}{2\sqrt{n}}\left(\|f_{1}(X_{i}')-f_{2}(X_{i}')\|_{2}+\|f_{1}(X_{i})-f_{2}(X_{i})\|_{2}\right)\tag{def. of $f_{1},f_{2}$}\\
&\leq \frac{\mathfrak{m}(\mathcal{F}_{0})}{\sqrt{n}}\sup_{x\in\mathbb{X}}\|f_{1}(x)-f_{2}(x)\|_{2}\nonumber\\
&= \frac{\mathfrak{m}(\mathcal{F}_{0})}{\sqrt{n}}\sup_{x\in\mathbb{X}}\left\|\frac{f_{1,0}(x)}{\|f_{1,0}(x)\|_{2}}-\frac{f_{2,0}(x)}{\|f_{2,0}(x)\|_{2}}\right\|_{2}\tag{the uniqueness of $f_{1,0},f_{2,0}$}\nonumber\\
&\leq \frac{1}{\sqrt{n}}\|f_{1,0}-f_{2,0}\|_{\infty}.\tag{def. of $\mathfrak{m}(\mathcal{F}_{0})$}
\end{align}

Hence, we have

\begin{align*}
\mathbb{E}_{X_{1:n},X_{1:n}',\sigma_{1:n}}\left[\exp\left(t(Z_{f_{1,0}}-Z_{f_{2,0}})\right)\right]
\leq \exp\left(\frac{t^{2}}{2n}\|f_{1,0}-f_{2,0}\|_{\infty}^{2}\right)^{n}=\exp\left(\frac{t^{2}}{2}\|f_{1,0}-f_{2,0}\|_{\infty}^{2}\right).
\end{align*}

This indicates that $\{Z_{f_{0}}\}_{f\in\mathcal{F}_{0}}$ is a sub-Gaussian process with the norm $\|\cdot\|_{\infty}$.
Here note that $\sup_{f_{1,0},f_{2,0}\in\mathcal{F}_{0}}\|f_{1,0}-f_{2,0}\|_{\infty}\leq C\sqrt{d}$ for some constant $C\in\mathbb{R}$ that is independent of $d$, since $\mathcal{F}_{0}$ is uniformly bounded.
By using the chaining theorem (Theorem 5.22 in 77), we have

\begin{align*}
\mathfrak{R}_{n}^{+}(\mathcal{Q})\leq \frac{64}{\mathfrak{m}(\mathcal{F}_{0})\sqrt{n}}\int_{0}^{C\sqrt{d}}\sqrt{\log\mathfrak{C}(u;\mathcal{F}_{0},\|\cdot\|_{\infty})}du.
\end{align*}

For $\mathfrak{R}_{n/2}^{-}(\mathcal{Q})$, in a similar way we obtain,

\begin{align*}
\mathfrak{R}_{n/2}^{-}(\mathcal{Q})\leq \frac{64\sqrt{2}}{\mathfrak{m}(\mathcal{F}_{0})\sqrt{n}}\int_{0}^{C\sqrt{d}}\sqrt{\log\mathfrak{C}(u;\mathcal{F}_{0},\|\cdot\|_{\infty})}du.
\end{align*}

Thus, we have

\begin{align*}
\mathfrak{R}_{n}(\mathcal{Q})\leq  \frac{64(1+\sqrt{2}\lambda)}{\mathfrak{m}(\mathcal{F}_{0})\sqrt{n}}\int_{0}^{C\sqrt{d}}\sqrt{\log\mathfrak{C}(u;\mathcal{F}_{0},\|\cdot\|_{\infty})}du,
\end{align*}

and complete the proof.

The integral in the above upper bound is often called Dudley entropy integral [77].
Proposition <ref> makes it easier to derive a generalization bound via chaining, since it is enough to evaluate the Dudley entropy integral for the function space $\mathcal{F}_{0}$ instead of the space of critic functions $\mathcal{Q}$.

Here, denote by $\mathfrak{D}(\mathcal{F}_{0},\|\cdot\|_{\infty})$, the Dudley entropy integral w.r.t. $(\mathcal{F}_{0},\|\cdot\|_{\infty})$, i.e.,

\begin{align*}
\mathfrak{D}(\mathcal{F}_{0},\|\cdot\|_{\infty})=\int_{0}^{C\sqrt{d}}\sqrt{\log\mathfrak{C}(u;\mathcal{F}_{0},\|\cdot\|_{\infty})}du.
\end{align*}

It is shown by 72 that if $\mathcal{F}_{0}$ is a function space of feedforward (deep) neural networks, where each neural networks have weight matrices whose norms are bounded by some universal constant, and Lipschitz activation functions that vanish at the origin, then $\mathfrak{D}(\mathcal{F}_{0},\|\cdot\|_{\infty})<+\infty$ holds.
Based on this fact, we introduce:

The Dudley entropy integral $\mathfrak{D}(\mathcal{F}_{0},\|\cdot\|_{\infty})$ is finite, and $\mathfrak{R}_{n}(\mathcal{Q})\leq O((1+\lambda)/\sqrt{n})$ holds.

Consequently, we obtain the generalization error bound.

Suppose that Assumption <ref>, <ref> hold, and $n$ is even.
Then, with probability at least $1-\varepsilon$ where $\varepsilon>0$, we have

\begin{align*}
L_{\textup{KCL}}(f;\lambda)\leq \widehat{L}_{\textup{KCL}}(f;\lambda)+O\left(\frac{(1+\lambda)\left(1+\sqrt{\log\left(2/\varepsilon\right)}\right)}{\sqrt{n}}\right).
\end{align*}

Due to Theorem <ref> and Assumption <ref>.

§.§ Useful Results on McDiarmid's Inequality for Dependent Random Variables

Before showing Theorem <ref>, we need to prepare several definitions and an existing result.
The following three definitions are quoted from 86.

An undirected graph $G$ is called a dependency graph of a random vector ${\mathbf{X}}=(X_{1},\cdots,X_{n})$ if

* $V(G)=[n]$

* if $I,J\subset [n]$ are non-adjacent in $G$, then $\{X_{i}\}_{i\in I}$ and $\{X_{j}\}_{j\in J}$ are independent.

Given a graph $G$, a forest $F$, and a mapping $\phi: V(G)\to V(F)$, if $\phi(u)=\phi(v)$ or $\langle \phi(u),\phi(v)\rangle \in E(F)$ for any $\langle u,v\rangle \in E(G)$, we say that $(\phi, F)$ is a forest approximation of $G$.
Let $\Phi(G)$ denote the set of forest approximations of $G$.

Given a graph $G$ and any forest approximation $(\phi, F)\in\Phi(G)$ with $F$ consisting of trees $\{T_{i}\}_{i\in[k]}$, let

\begin{align*}
\lambda_{(\phi,F)}=\sum_{\langle u,v\rangle \in E(F)}\left(|\phi^{-1}(u)|+|\phi^{-1}(v)|\right)^{2}+\sum_{i=1}^{k}\min_{u\in V(T_{i})}|\phi^{-1}(u)|^{2}.
\end{align*}

We call

\begin{align*}
\Lambda(G)=\min_{(\phi,F)\in\Phi(G)}\lambda_{(\phi, F)}
\end{align*}

the forest complexity of the graph $G$.

86 have shown the following result, which is an extension of McDiarmid's inequality [42] for dependent random variables.

Suppose that $f:\mathbf{\Omega}\to\mathbb{R}$ is a $\mathbf{c}$-Lipschitz function and $G$ is a dependency graph of a random vector ${\mathbf{X}}$ that takes values in $\mathbf{\Omega}$.
For any $t>0$, the following inequality holds:

\begin{align*}
\mathbf{\textup{Pr}}(f(\mathbf{X})-\mathbf{E}[f(\mathbf{X})]\geq t)\leq \exp\left(-\frac{2t^{2}}{\Lambda(G)\|\mathbf{c}\|_{\infty}^{2}}\right).
\end{align*}

Note that, in the above theorem $f:\mathbf{\Omega}\to\mathbb{R}$ is said to be $\mathbf{c}$-Lipschitz if $|f(\mathbf{x})-f(\mathbf{x}')|\leq \sum_{i=1}^{p}\mathbf{c}_{i}\mathbbm{1}_{\{\mathbf{x}_{i}\neq \mathbf{x}_{i}'\}}$ for every $\mathbf{x},\mathbf{x}'\in\mathbf{\Omega}$, where $\mathbf{\Omega}\subset\mathbb{R}^{p}$ for some $p\in\mathbb{N}$.

§.§ Proof of Theorem <ref>

We show Theorem <ref> by utilizing the contents in Appendix <ref>.
Recall the definition of the random variables introduced in Section <ref>:
$(X_{1},X_{1}'),\cdots,(X_{n},X_{n}')$ are pairs of random variables sampled independently according to the joint probability distribution with density $w(x,x')$, where $X_{i}$ and $X_{j}'$ are independent for each pair of distinct indices $i,j\in[K]$.
From the definition, the following claim holds.

Let $G_{n}$ be a dependency graph that is defined with a random vector $(X_{1},X_{1}',\cdots,X_{n},X_{n}')$, where the edges in $G_{n}$ are defined as follows: for any $i,j\in[n]$, $X_{i}$ and $X_{j}$ are not connected, and $X_{i}$ and $X_{j}'$ are connected by an edge if and only if $i=j$.
Then, we have $\Lambda(G_{n})\leq 5n$.

Let $\phi:G_{n}\to G_{n}$ be the identity map.
From the definition, $G_{n}$ can be decomposed into trees $\{T_{i}\}_{i\in[n]}$ where $V(T_{i})=\{X_{i},X_{i}'\}$ for each $i\in[n]$.
Let $F$ be the forest consisting of the trees $\{T_{i}\}_{i\in[n]}$.
Then, we have $\lambda_{(\phi,F)}= 5n$, which implies $\Lambda (G_{n})\leq \lambda_{(\phi,F)}\leq 5n$.

The goal of this proof is to upper bound the following quantity with high probability:

\begin{align*}
\sup_{f\in\mathcal{F}}\left(-\frac{1}{n(n-1)}\sum_{i\neq j}k(f(X_{i}),f(X_{j}'))+\mathbb{E}_{X,X^{-}}\left[k(f(X_{i}),f(X^{-}))\right]\right).
\end{align*}

However, as explained before, the standard argument (see e.g., Theorem 3.3 in 43) cannot apply to this case since $k(f(X_{i}),f(X_{j}'))$, $i,j\in[n], i\neq j$ are not necessarily independent to each other from our problem setup.
We instead utilize the McDiarmid's inequality for dependent random variables, which is shown by 86, to avoid this problem.
Our proof below is mainly based on Theorem 3.3 in [43], but it includes some modification due to the application of the results by 86.
Let $\widetilde{X}_{1},\widetilde{X}_{1}',\cdots,\widetilde{X}_{n},\widetilde{X}_{n}'$ be i.i.d. random variables to the original random variables $X_{1},X_{1}'.\cdots,X_{n},X_{n}'$.
Define the measurable function $F(f):=F(f)(x_{1},x_{1}',\cdots,x_{n},x_{n}')$ on $\mathbb{X}^{2n}$ as

\begin{align*}
F(f):=\frac{1}{n(n-1)}\sum_{i\neq j}k(f(x_{i}),f(x_{j}'))-\mathbb{E}_{X,X^{-}}\left[k(f(X),f(X^{-}))\right].
\end{align*}

For simplicity, denote

\begin{align*}
F(f)_{x_{\ell}}&:=\frac{1}{n(n-1)}\left(\sum_{j:j\neq \ell}k(f(\widetilde{x}_{\ell}),f(x_{j}'))+\sum_{\substack{i,j:i\neq j\\i\neq \ell}}k(f(x_{i}),f(x_{j}'))\right)-\mathbb{E}_{X,X^{-}}\left[k(f(X),f(X^{-}))\right].
\end{align*}

In a similar way, we also use the notation $F(f)_{x_{\ell}'}$.
Let $j\in[n]$.
Then, for every $f\in\mathcal{F}$, we have

\begin{align*}
\leq F(f)-F(f)_{X_{j}}
&\leq \left|F(f)-F(f)_{X_{j}}\right|\\
&\leq \left|\frac{1}{n(n-1)}\sum_{i\in[n],i\neq j}\left(k(f(X_{j}),f(X_{i}'))-k(f(\widetilde{X}_{j}),f(X_{i}'))\right)\right|\\
&\leq \frac{1}{n(n-1)}\cdot 2(n-1)b= \frac{2b}{n},
\end{align*}

where $b:=\sup_{z,z'\in\mathbb{S}^{d-1}}|k(z,z')|$.
Hence, $\sup_{f\in\mathcal{F}}F(f)-\sup_{f\in\mathcal{F}}F(f)_{X_{j}}\leq \frac{2b}{n}$.
By applying the same argument several times, $\sup_{f\in\mathcal{F}}F(f)$ satisfies the assumption of Theorem <ref>.
Therefore, from Theorem <ref> (i.e., Theorem 3.6 in 86) and Lemma <ref>, with probability at least $1-\varepsilon$ we have

\begin{align}
\label{lemma3ineq0.9}
\sup_{f\in\mathcal{F}}F(f)\leq \mathbb{E}\left[\sup_{f\in\mathcal{F}}F(f)\right]+\sqrt{\frac{10b^{2}\log\left(1/\varepsilon\right)}{n}}.
\end{align}

Let $\sigma_{1:n/2}:=(\sigma_{1},\cdots,\sigma_{n/2})$ be a random vector that consists of a Rademacher random variable (i.e., a random variable taking $\pm$ 1 with probability $1/2$ each) for each entry, and let $\widetilde{X}_{1:n},\widetilde{X}_{1:n}'$ be i.i.d. copies of the random vectors $X_{1:n},X_{1:n}'$, respectively.
Denote $m=n/2\in\mathbb{N}$.

\begin{align}
\label{lemma3ineq0.901}
\mathbb{E}\left[\sup_{f\in\mathcal{F}}\left(\frac{1}{n(n-1)}\sum_{i\neq j}k(f(X_{i}),f(X_{j}'))-\mathbb{E}_{X,X^{-}}\left[k(f(X),f(X^{-}))\right]\right)\right]\nonumber\\
\mathbb{E}\left[\sup_{f\in\mathcal{F}}\left(\frac{1}{n(n-1)}\sum_{i\neq j}k(f(X_{i}),f(X_{j}'))-\mathbb{E}_{\widetilde{X}_{1:n},\widetilde{X}_{1:n}'}\left[\frac{1}{n(n-1)}\sum_{i\neq j}k(f(\widetilde{X}_{i}),f(\widetilde{X}_{j}'))\right]\right)\right]\nonumber\\
&=\mathbb{E}\left[\sup_{f\in\mathcal{F}}\left(\frac{1}{n!m}\sum_{s\in S_{n}}\left(\sum_{i=1}^{m}k(f(X_{s(2i-1)}),f(X_{s(2i)}'))-\mathbb{E}_{\widetilde{X}_{1:n}',\widetilde{X}_{1:n}'}\left[\sum_{i=1}^{m}k(f(\widetilde{X}_{s(2i-1)}),f(\widetilde{X}_{s(2i)}'))\right]\right)\right)\right]\\
&\leq \frac{1}{n!}\sum_{s\in S_{n}}\mathbb{E}\left[\sup_{f\in\mathcal{F}}\left(\frac{1}{m}\sum_{i=1}^{m}k(f(X_{s(2i-1)}),f(X_{s(2i)}'))-\mathbb{E}_{\widetilde{X}_{1:n},\widetilde{X}_{1:n}'}\left[\frac{1}{m}\sum_{i=1}^{m}k(f(\widetilde{X}_{s(2i-1)}),f(\widetilde{X}_{s(2i)}'))\right]\right)\right]\nonumber\\
&\leq \frac{1}{n!}\sum_{s\in S_{n}}\mathbb{E}_{\substack{X_{1:n},X_{1:n}'\\\widetilde{X}_{1:n},\widetilde{X}_{1:n}'}}\left[\sup_{f\in\mathcal{F}}\left(\frac{1}{m}\sum_{i=1}^{m}\left(k(f(X_{s(2i-1)}),f(X_{s(2i)}'))-k(f(\widetilde{X}_{s(2i-1)}),f(\widetilde{X}_{s(2i)}'))\right)\right)\right]\nonumber\\
\label{lemma3ineq0.902}
&= \frac{1}{n!}\sum_{s\in S_{n}}\mathbb{E}_{\substack{X_{1:n},X_{1:n}'\\\widetilde{X}_{1:n},\widetilde{X}_{1:n}'\\\sigma_{1:m}}}\left[\sup_{f\in\mathcal{F}}\left(\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}\left(k(f(X_{s(2i-1)}),f(X_{s(2i)}'))-k(f(\widetilde{X}_{s(2i-1)}),f(\widetilde{X}_{s(2i)}'))\right)\right)\right]\\
&\leq \frac{2}{n!}\sum_{s\in S_{n}}\mathbb{E}_{\substack{X_{1:n},X_{1:n}'\\\sigma_{1:m}}}\left[\sup_{f\in\mathcal{F}}\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}k(f(X_{s(2i-1)}),f(X_{s(2i)}'))\right]\nonumber\\
\label{lemma3ineq0.903}
&\leq \frac{2\rho}{n!}\sum_{s\in S_{n}}\mathbb{E}_{\substack{X_{1:n},X_{1:n}'\\\sigma_{1:m}}}\left[\sup_{f\in\mathcal{F}}\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}f(X_{s(2i-1)})^{\top}f(X_{s(2i)}')\right]\\
&\leq 2\rho\max_{s\in S_{n}}\mathbb{E}_{\substack{X_{1:n},X_{1:n}'\\\sigma_{1:m}}}\left[\sup_{f\in\mathcal{F}}\frac{1}{m}\sum_{i=1}^{m}\sigma_{i}f(X_{s(2i-1)})^{\top}f(X_{s(2i)}')\right]\nonumber\\
\end{align}

where in (<ref>) we define $S_{n}$ as the symmetric group of degree $n$ (see Remark <ref> for the relation to the average of "sums-of-i.i.d." blocks technique for $U$-statistics which is explained in 14).
Besides in (<ref>), for every $s\in S_{n}$ the random vectors $(X_{s(2i-1)},X_{s(2i)})$, $(\widetilde{X}_{s(2i-1)},\widetilde{X}_{s(2i)})$ for $i=1,\cdots,m$ are independent and identically distributed, which implies that the standard symmetrization argument (Theorem 4.10 of 77) is applicable.
Finally, in (<ref>), under Assumption <ref>, we apply Talagrand's lemma (Lemma 26.9 in 54).
Therefore, we obtain with probability at least $1-\varepsilon$,

\begin{align*}
\sup_{f\in\mathcal{F}}F(f)\leq 2\rho\mathfrak{R}_{n/2}^{-}(\mathcal{Q};s^{*})+\sqrt{\frac{10b^{2}\log\left(1/\varepsilon\right)}{n}}.
\end{align*}

Thus, we obtain the claim.

In (<ref>) of the proof of Theorem <ref>, we use the identity,

\begin{align*}
\frac{1}{n(n-1)}\sum_{i\neq j}k(f(X_{i}),f(X_{j}'))=\frac{1}{n!m}\sum_{s\in S_{n}}\sum_{i=1}^{m}k(f(X_{s(2i-1)},f(X_{s(2i)}')).
\end{align*}

We notice that the above identity is closely related to the average of "sum-of-i.i.d." blocks technique explained in Appendix A of 14.
As well as the technique presented in 14, in (<ref>) of our paper we also decompose the sum $\sum_{i\neq j}k(f(X_{i}),f(X_{j}'))$ into the sums of the i.i.d. random variables.
However, we remark that the definition of the sum $\sum_{i\neq j}k(f(X_{i}),f(X_{j}'))$ is different from that presented in 14: indeed, in our case, the random variables $f(X_{1}),f(X_{1}'),\cdots,f(X_{n}),f(X_{n}')$ are not necessarily independent of each other.
To address this problem, we decompose our sum in (<ref>) as follows: for $2n$ random variables $X_{1},X_{1}',\cdots,X_{n},X_{n}'$, we create the tuples $(X_{s(1)},X_{s(2)}',\cdots,X_{s(n-1)},X_{s(n)}')$ where $s\in S_{n}$, then sum up all the components $\{\sum_{i=1}^{n}k(f(X_{s(2i-1)}),f(X_{s(2i)}'))\}_{s\in S_{n}}$.

§ PROOF IN SECTION <REF>

First applying Theorem <ref> to the empirical loss minimizer $\widehat{f}$, we have

\begin{align}
\label{eq:cor eq1}
\end{align}

Using Theorem <ref>, we have the inequality,

\begin{align}
\label{eq:cor eq2}
\mathfrak{a}(\widehat{f})\leq L_{\textup{KCL}}(\widehat{f};\lambda)+(1-\frac{\delta}{2})\mathfrak{a}(\widehat{f})-\lambda\mathfrak{c}(\widehat{f})+R(\lambda).
\end{align}

Combining (<ref>) and (<ref>), we obtain

\begin{align}
\label{eq:cor eq3}
\end{align}

Here, using the standard technique for upper bounding the optimal classification loss or error [3, 4], the classification error $L_{\textup{Err}}(\widehat{f},W_{\mu},\beta_{\mu};y)$ is lower bounded as

\begin{align}
\label{eq:cor eq4}
L_{\textup{Err}}(\widehat{f},W^{*}\beta^{*};y)=\inf_{W,\beta}L_{\textup{Err}}(\widehat{f},W,\beta;y)\leq L_{\textup{Err}}(\widehat{f},W_{\mu},\beta_{\mu};y).
\end{align}

From (<ref>) and (<ref>),

\begin{align}
\label{eq:cor eq5}
\end{align}

Applying Theorem <ref> to (<ref>), we obtain: with probability at least $1-2\varepsilon$,

\begin{align*}
L_{\textup{Err}}(\widehat{f},W_{\mu},\beta_{\mu};y)\lesssim L_{\textup{KCL}}(f;\lambda)+(1-\frac{\delta}{2})\mathfrak{a}(\widehat{f})-\lambda\mathfrak{c}(\widehat{f})+R(\lambda)+2\textup{Gen}(n,\lambda,\varepsilon),
\end{align*}

where $\lesssim$ omits the coefficient $\frac{8(K-1)}{\Delta_{\textup{min}}(\widehat{f})\cdot\min_{i\in[K]}P_{\mathbb{X}}(\mathbb{M}_{i})}$.
Therefore, we obtain the result.

§ ADDITIONAL INFORMATION, RESULTS, AND DISCUSSION

§.§ Examples Satisfying Assumption <ref>

§.§.§ Proofs in Example <ref>

We show the several claims that appear in Example <ref> as a proposition.

Let $r>0$, $K\in\mathbb{N}$, and $v_{1},\cdots,v_{K}\in\mathbb{R}^{p}$.
For each $i\in[K]$, let $\mathbb{B}_{i}\subset\mathbb{R}^{p}$ be the open ball of radius $r$ centered at a point $v_{i}$.
Suppose $\mathbb{B}_{1},\cdots,\mathbb{B}_{K}$ are disjoint to each other. Define $\overline{\mathbb{X}}=\bigcup_{i=1}^{K}\mathbb{B}_{i}$, $\mathbb{X}=\overline{\mathbb{X}}$, and the conditional probability $a(x|\overline{x})=\textup{vol}(\mathbb{B}_{1})^{-1}\sum_{i=1}^{K}\mathbbm{1}_{\mathbb{B}_{i}\times\mathbb{B}_{i}}(x,\overline{x})$, where $\textup{vol}(\mathbb{B}_{1})$ be the volume of $\mathbb{B}_{i}$ in $\mathbb{R}^{p}$.
Let $p_{\overline{\mathbb{X}}}(\overline{x}):=(K\textup{vol}(\mathbb{B}_{1}))^{-1}$ be a probability density function of $P_{\overline{\mathbb{X}}}$.
Define $y:\mathbb{X}\to [K]$ as $y(x)=i$ if $x\in\mathbb{B}_{i}$.
Then, we have the following properties:

* $w(x)>0$ for every $x\in\mathbb{X}$.

* $\textup{sim}(x,x';\lambda)=K\mathbbm{1}_{\bigcup_{i\in [K]}\mathbb{B}_{i}\times\mathbb{B}_{i}}(x,x')-\lambda$ for every $x,x'\in\mathbb{X}$.

* Let $\delta\in(-\lambda,K-\lambda]$. Then, $\delta$, $K$, $\mathbb{B}_{1},\cdots,\mathbb{B}_{K}$, and y satisfy Assumption <ref>.

We first show the claim 1.
From the definition of $w(x)$, for every $x\in\mathbb{B}_{1}$ we have

\begin{align*}
w(x)=\int_{\overline{\mathbb{X}}}a(x|\overline{x})p_{\overline{\mathbb{X}}}(\overline{x})d\overline{x}=\int_{\mathbb{B}_{1}} \frac{1}{K\left(\textup{vol}(\mathbb{B}_{1})\right)^{2}}d\overline{x}=\frac{1}{K\textup{vol}(\mathbb{B}_{1})}.
\end{align*}

Similarly, for each $i\in[K]$ we obtain $w(x)=(K\textup{vol}(\mathbb{B}_{1}))^{-1}$ for every $x\in\mathbb{B}_{i}$.
Since $\mathbb{X}=\overline{\mathbb{X}}=\bigcup_{i=1}^{K}\mathbb{B}_{i}$, we have that $w(x)>0$ for every $x\in\mathbb{X}$.

Next, let us show the claim 2.
From the claim 1, the function $\textup{sim}(x,x';\lambda)$ is well-defined.
To compute $\textup{sim}(x,x';\lambda)$, we need to know the function $w(x,x')$.
The computation of $w(x,x')$ is done as follows:

\begin{align*}
\int_{\mathbb{B}_{i}} \frac{1}{K\left(\textup{vol}(\mathbb{B}_{1})\right)^{3}}d\overline{x}\quad\textup{if }x,x'\in\mathbb{B}_{i}\textup{ for some }i\in[K]\\
0 \quad\quad\quad\quad\quad\quad\quad\;\,\textup{if }x\in\mathbb{B}_{i}\textup{ and }x'\in\mathbb{B}_{j}\textup{ for some }i\neq j
\end{cases}
\\
\frac{1}{K\left(\textup{vol}(\mathbb{B}_{1})\right)^{2}}\quad\quad\;\;\quad\textup{if }x,x'\in\mathbb{B}_{i}\textup{ for some }i\in[K]\\
0 \quad\quad\quad\quad\quad\quad\quad\;\,\textup{if }x\in\mathbb{B}_{i}\textup{ and }x'\in\mathbb{B}_{j}\textup{ for some }i\neq j.
\end{cases}
\end{align*}

Hence, it is obvious that the claim 2 holds.

Finally, let us prove the claim 3.
However, from the claim 2 we see that $\textup{sim}(x,x';\lambda)\geq \delta$ if and only if $x,x'\in\mathbb{B}_{i}$ for some $i\in[K]$.
Furthermore, $y$ is well-defined and the set $\{x\in\mathbb{X}\;|\;y(x)=i\}=\mathbb{B}_{i}$ is measurable for every $i\in[K]$.
Thus, the claim 3 is also true, and we end the proof.

§.§.§ An Example When Clusters Overlap

Here, we also deal with an example where the clusters in $\mathbb{X}$ have some overlap.
In the following proposition, for the sake of simplicity, we consider the case that there are two clusters in $\mathbb{X}$.

Let $r>0$, and $v_{1},v_{2}\in\mathbb{R}^{p}$.
For each $i\in\{1,2\}$, let $\mathbb{B}(v_{i};r)\subset\mathbb{R}^{p}$ be the open ball of radius $r$ centered at point $v_{i}$.
Suppose that $\|v_{1}-v_{2}\|_{2}=3r$.
Define $\overline{\mathbb{X}}=\mathbb{B}(v_{1};r)\cup\mathbb{B}(v_{2};r)$, $\mathbb{X}=\mathbb{B}(v_{1};2r)\cup\mathbb{B}(v_{2};2r)$, and $a(x|\overline{x})=\textup{vol}(\mathbb{B}(v_{1};2r))^{-1}\sum_{i=1}^{2}\mathbbm{1}_{\mathbb{B}(v_{i};2r)\times\mathbb{B}(v_{i};r)}(x,\overline{x})$.
Let $p_{\overline{\mathbb{X}}}(\overline{x}):=(2\cdot\textup{vol}(\mathbb{B}(v_{1};r)))^{-1}$ be a probability density function of $P_{\overline{\mathbb{X}}}$.
Define $y:\mathbb{X}\to \{1,2\}$ as $y(x)=1$ if $x\in\mathbb{B}(v_{1};2r)$ and $y(x)=2$ if $x\in\mathbb{B}(v_{2};2r)\setminus\mathbb{B}(v_{1};2r)$.
Then, we have the following results:

* $w(x)>0$ for every $x\in\mathbb{X}$.

* $\textup{sim}(x,x';\lambda)=2-\lambda$ if $x,x'\in\mathbb{B}(v_{1};2r)\setminus\mathbb{B}(v_{2};2r)$ or $x,x'\in\mathbb{B}(v_{2};2r)\setminus\mathbb{B}(v_{1};2r)$, $\textup{sim}(x,x';\lambda)=-\lambda$ if $(x,x')\in(\mathbb{B}(v_{1};2r)\setminus\mathbb{B}(v_{2};2r))\times(\mathbb{B}(v_{2};2r)\setminus\mathbb{B}(v_{1};2r))$ or $(x,x')\in(\mathbb{B}(v_{2};2r)\setminus\mathbb{B}(v_{1};2r))\times(\mathbb{B}(v_{1};2r)\setminus\mathbb{B}(v_{2};2r))$, and $\textup{sim}(x,x';\lambda)=1-\lambda$ otherwise.

* Let $\delta\in(-\lambda,1-\lambda]$. Then, $\delta$, $K$, $\mathbb{B}_{1},\cdots,\mathbb{B}_{K}$, and y satisfy Assumption <ref>.

Let $\overline{\mathbb{X}}_1$ (resp. $\overline{\mathbb{X}}_{2}$) denote $\mathbb{B}(v_{1};r)$, (resp. $\mathbb{B}(v_{2};r)$). Then,

\begin{align*}
&=\int_{\overline{\mathbb{X}}}a(x|\overline{x})p_{\overline{\mathbb{X}}} (\overline{x}) d\overline{x}\\
&=\int_{\overline{\mathbb{X}}_{1}}a(x|\overline{x})p_{\overline{\mathbb{X}}} (\overline{x}) d\overline{x}+\int_{\overline{\mathbb{X}}_{2}}a(x|\overline{x})p_{\overline{\mathbb{X}}} (\overline{x}) d\overline{x}\\
&=p_{\overline{\mathbb{X}}} (\overline{x})\left\{  \int_{\overline{\mathbb{X}}_{1}}a(x|\overline{x})d\overline{x}+\int_{\overline{\mathbb{X}}_{2}}a(x|\overline{x}) d\overline{x}   \right\}\tag{$p_{\overline{\mathbb{X}}}$ is a constant function}
\end{align*}

Here, we consider Case 1 and Case 2. Firstly, Case 1 is when either $x \in \mathbb{B}(v_1;2r) \setminus \mathbb{B}(v_2;2r)$ or $x \in \mathbb{B}(v_2;2r) \setminus \mathbb{B}(v_1;2r)$ holds. Since in this case, it is sufficient to prove for the case that $x \in \mathbb{B}(v_1;2r) \setminus \mathbb{B}(v_2;2r)$ holds, we may assume this condition. Then, $\int_{\overline{\mathbb{X}}_{1}}a(x|\overline{x})d\overline{x} = \text{vol}(\mathbb{B}(v_1;r))\text{vol}(\mathbb{B}(v_1;2r))^{-1}$  and $\int_{\overline{\mathbb{X}}_2}a(x|\overline{x})d\overline{x} = 0$. Thus, $w(x) = 1/(2\text{vol}(\mathbb{B}(v_1;2r)))$. Secondly, Case 2 is when $x \in \mathbb{B}(v_1;2r) \cap \mathbb{B}(v_2;2r)$. Then, $\int_{\overline{\mathbb{X}}_1}a(x|\overline{x})d\overline{x} = \int_{\overline{\mathbb{X}}_2}a(x|\overline{x})d\overline{x} = \text{vol}(\mathbb{B}(v_1;r))\text{vol}(\mathbb{B}(v_1;2r))^{-1}$. Thus, $w(x) = 1/\text{vol}(\mathbb{B}(v_1;2r))$. Since $r>0$, it implies $\text{vol}(\mathbb{B}(v_1;2r))>0$. Thus $w(x)>0$ for both cases.

Next, we compute

\begin{align*}
w(x, x')&=\mathbb{E}_{\overline{x}}\left[a(x|\overline{x})a(x'|\overline{x})\right]\\
&=\int_{\overline{\mathbb{X}}}a(x|\overline{x})a(x'|\overline{x})p_{\overline{\mathbb{X}}} (\overline{x}) d\overline{x}\\
&=\int_{\overline{\mathbb{X}}_1}a(x|\overline{x})a(x'|\overline{x})p_{\overline{\mathbb{X}}} (\overline{x}) d\overline{x}\ + \int_{\overline{\mathbb{X}}_2}a(x|\overline{x})a(x'|\overline{x})p_{\overline{\mathbb{X}}} (\overline{x}) d\overline{x}\\
&=p_{\overline{\mathbb{X}}} (\overline{x})\left\{  \int_{\overline{\mathbb{X}}_1}a(x|\overline{x}) a(x'|\overline{x})d\overline{x}+\int_{\overline{\mathbb{X}}_2}a(x|\overline{x})a(x'|\overline{x}) d\overline{x}   \right\}\tag{$p_{\overline{\mathbb{X}}}$ is a constant function}.
\end{align*}

Here, we consider Case A, Case B, Case C, and Case D. Firstly Case A is that both $x$ and $x^\prime$ belong to $\mathbb{B}(v_1;2r)\setminus \mathbb{B}(v_2;2r)$ (note that the computation for the case that both $x$ and $x^\prime$ belong to $\mathbb{B}(v_2;2r)\setminus \mathbb{B}(v_1;2r)$ is the same). Then, $\int_{\overline{\mathbb{X}}_1}a(x|\overline{x}) a(x'|\overline{x})d\overline{x} = \text{vol}(\mathbb{B}(v_1;r))/\text{vol}(\mathbb{B}(v_1;2r))^2$ and $\int_{\overline{\mathbb{X}}_2}a(x|\overline{x}) a(x'|\overline{x})d\overline{x} = 0$. Hence,
$w(x, x') = \{2(\text{vol}(\mathbb{B}(v_1;2r)))^2\}^{-1}$. Here recall that $w(x)=w(x')=1/(2\text{vol}(\mathbb{B}(v_1;2r)))$, then we have $\text{sim}(x, x';\lambda) = 2 - \lambda$. Secondly Case B is that $x \in \mathbb{B}(v_1;2r)\setminus\mathbb{B}(v_{2};2r)$ and $x' \in \mathbb{B}(v_2;2r) \setminus \mathbb{B}(v_1;2r)$ (the calculation for the case that $x \in \mathbb{B}(v_2;2r)\setminus\mathbb{B}(v_{1};2r)$ and $x' \in \mathbb{B}(v_1;2r) \setminus \mathbb{B}(v_2;2r)$ is the same). Then, $\int_{\overline{\mathbb{X}}_1}a(x|\overline{x}) a(x'|\overline{x})d\overline{x}=\int_{\overline{\mathbb{X}}_2}a(x|\overline{x}) a(x'|\overline{x})d\overline{x}=0$. Therefore, $\text{sim}(x, x';\lambda) = 0 - \lambda = -\lambda$. Thirdly Case C is that both $x$ and $x^\prime$ belong to $\mathbb{B}(v_1;2r) \cap \mathbb{B}(v_2;2r)$. Then, $\int_{\overline{\mathbb{X}}_1}a(x|\overline{x}) a(x'|\overline{x})d\overline{x} =\int_{\overline{\mathbb{X}}_2}a(x|\overline{x}) a(x'|\overline{x})d\overline{x} = \text{vol}(\mathbb{B}(v_1;r))/\text{vol}(\mathbb{B}(v_1;2r))^2$. Since $w(x) = w(x') = 1/\text{vol}(\mathbb{B}(v_1;2r))$, $\text{sim}(x, x';\lambda) = 1 - \lambda$.
Finally in Case D, consider the complementary of the union of the other cases.
From the setting, we may assume that $x$ belongs to $\mathbb{B}(v_{1};2r)\cap\mathbb{B}(v_{2};2r)$ and $x'$ to $\mathbb{B}(v_{1};2r)\setminus\mathbb{B}(v_{2};2r)$.
Then, $\int_{\overline{\mathbb{X}}_{1}}a(x|\overline{x})a(x'|\overline{x})d\overline{x}=\textup{vol}(\mathbb{B}(v_{1};r))/\textup{vol}(\mathbb{B}(v_{1};2r))^{2}$ and $\int_{\overline{\mathbb{X}}_{2}}a(x|\overline{x})a(x'|\overline{x})d\overline{x}=0$.
Since $w(x)=1/\textup{vol}(\mathbb{B}(v_{1};2r))$ and $w(x')=1/(2\textup{vol}(\mathbb{B}(v_{1};2r)))$, we have $\textup{sim}(x,x';\lambda)=1-\lambda$.
As a result,

\begin{equation*}
\text{sim}(x,x';\lambda)=\left\{
\begin{array}{ c l }
2 - \lambda,& \text{if Case~A holds}, \\
-\lambda,   & \text{if Case~B holds}, \\
1 - \lambda, & \text{if Case~C holds}, \\
1 - \lambda, & \text{if Case~D holds}.
\end{array}
\right.
\end{equation*}

Finally, take $\delta\in(-\lambda,1-\lambda]$. Then, from the computation for $\textup{sim}(x,x';\lambda)$ above, the conditions in Assumption <ref> are satisfied.

§.§ SSL-HSIC Revisit

40 propose the framework termed SSL-HSIC, which is defined using the notion Hilbert-Schmidt Independence Criterion (HSIC, [58]).
They show that under some conditions, for a random variable $Z$ (resp. $Y$) that represents the feature vector (resp. the label), one obtains

\begin{align*}
\textup{HSIC}(Z,Y)=c\left( \mathbb{E}_{x,x^{+}}\left[k(f(x),f(x^{+}))\right]-\mathbb{E}_{x,x^{-}}\left[k(f(x),f(x^{-}))\right]\right),
\end{align*}

where $c>0$.
40 define the loss of SSL-HSIC as,

\begin{align*}
L_{\textup{SSL-HSIC}}(f;\kappa)=-\textup{HSIC}(Z,Y)+\kappa \sqrt{\textup{HSIC}(Z,Z)},
\end{align*}

where $\kappa\in\mathbb{R}$.

In the case that $\kappa>0$, we have

\begin{align*}
L_{\textup{KCL}}(f;1)\lesssim L_{\textup{SSL-HSIC}}(f;\kappa).
\end{align*}

§.§ Supplementary Information of Section <ref>

§.§.§ Relations to Variants of InfoNCE

We first define variants of InfoNCE [73, 9]:

* Decoupled InfoNCE loss, which is a variant of the decoupled NT-Xent loss of 10:

\begin{align*}
\widetilde{L}_{\textup{NCE}}(f;\tau,\lambda)=
\mathbb{E}_{\substack{x,x^{+}\\\{x_{i}^{-}\}}}\left[\log\left(e^{\frac{f(x)^{\top}f(x^{+})}{\tau}}+\sum_{i=1}^{M}e^{\frac{f(x)^{\top}f(x_{i}^{-})}{\tau}}\right)\right].
\end{align*}

* Asymptotic of contrastive loss [79] decoupled by following the way of 10:

\begin{align*}
\widetilde{L}_{\infty\textup{-NCE}}(f;\tau,\lambda)=-\mathbb{E}_{x,x^{+}}\left[\frac{f(x)^{\top}f(x^{+})}{\tau}\right]+\lambda\mathbb{E}_{x}\left[\log\mathbb{E}_{x'}\left[e^{\frac{f(x)^{\top}f(x')}{\tau}}\right]\right],
\end{align*}

* InfoNCE loss as a variant of decoupled contrastive learning loss [84]:

\begin{align*}
\widetilde{L}_{\textup{NCE}}(f;\tau,1)=
\mathbb{E}_{x,\{x_{i}^{-}\}}\left[\log\left(\sum_{i=1}^{M}e^{\frac{f(x)^{\top}f(x_{i}^{-})}{\tau}}\right)\right].
\end{align*}

* InfoNCE loss as a variant of decoupled contrastive learning loss with additional weight parameter, following 10:

\begin{align*}
\widetilde{L}_{\textup{NCE}}(f;\tau,\lambda)=
\mathbb{E}_{x,\{x_{i}^{-}\}}\left[\log\left(\sum_{i=1}^{M}e^{\frac{f(x)^{\top}f(x_{i}^{-})}{\tau}}\right)\right].
\end{align*}

Note that $L_{\textup{NCE}}(f;\tau)$ and $L_{\infty\textup{-NCE}}(f;\tau)$ in Section <ref> coincide with $\widetilde{L}_{\textup{NCE}}(f;\tau,1)$ and $\widetilde{L}_{\infty\textup{-NCE}}(f;\tau,1)$ in this subsection, respectively.
We show the following facts:

The following relations hold:

\begin{align}
\label{eq:lkcl vs dnce}
\tau^{-1}L_{\textup{LinKCL}}(f;\lambda)&\leq \widetilde{L}_{\textup{NCE}}(f;\tau,\lambda)+\lambda\log M^{-1},\\
\label{eq:lkcl vs dance}
\tau^{-1}L_{\textup{LinKCL}}(f;\lambda)&\leq \widetilde{L}_{\infty\textup{-NCE}}(f;\tau,\lambda),\\
\label{eq:lkcl vs ddcllnce}
\tau^{-1}L_{\textup{LinKCL}}(f;\lambda)&\leq \widetilde{L}_{\textup{NCE}}(f;\tau,\lambda)+\lambda\log M^{-1}.
\end{align}

From the definition of $L_{\textup{NCE}}(f;\tau,\lambda)$, we have

\begin{align*}
&\;\;\;\;\widetilde{L}_{\textup{NCE}}(f;\tau,\lambda)+\lambda\log \frac{1}{M}\\
&= -\tau^{-1}\mathbb{E}_{x,x^{+}}\left[f(x)^{\top}f(x^{+})\right]+\lambda\mathbb{E}_{x,x^{+},\{x_{i}^{-}\}}\left[\log \left(\frac{1}{M}e^{f(x)^{\top}f(x^{+})/\tau}+\frac{1}{M}\sum_{i=1}^{M}e^{f(x)^{\top}f(x_{i}^{-})/\tau}\right)\right]\\