Adv-SSL: Adversarial Self-Supervised Representation Learning with Theoretical Guarantees
Authors: Chenguang Duan
Yuling Jiao
Huazhen Lin
Wensen Ma
Jerry Zhijian Yang
Venue: NeurIPS 2025 poster ()
Keywords: self-supervised representation learning
transfer learning
adversarial training
error analysis
Primary area: theory

Abstract: Learning transferable data representations from abundant unlabeled data remains a central challenge in machine learning. Although numerous self-supervised learning methods have been proposed to address this challenge, a significant class of these approaches aligns the covariance or correlation matrix with the identity matrix. Despite impressive performance across various downstream tasks, these methods often suffer from biased sample risk, leading to substantial optimization shifts in mini-batch settings and complicating theoretical analysis. In this paper, we introduce a novel \underline{\bf Adv}ersarial \underline{\bf S}elf-\underline{\bf S}upervised Representation \underline{\bf L}earning (Adv-SSL) for unbiased transfer learning with no additional cost compared to its biased counterparts. Our approach not only outperforms the existing methods across multiple benchmark datasets but is also supported by comprehensive end-to-end theoretical guarantees. Our analysis reveals that the minimax optimization in Adv-SSL encourages representations to form well-separated clusters in the embedding space, provided there is sufficient upstream unlabeled data. As a result, our method achieves strong classification performance even with limited downstream labels, shedding new light on few-shot learning.

Adv-SSL: Adversarial Self-Supervised Representation Learning with Theoretical Guarantees
Chenguang Duan'
Yuling 3. Jerry Zhijian Yang 3,4
Huazhen Lin 6,8,8
Wensen Ma²
1 School of Mathematics and Statistics, Wuhan University
School of Artificial Intelligence, Wuhan University
National Center for Applied Mathematics in Hubei, Wuhan University
HHubei Key Laboratory of Computational Science, Wuhan University
Centee Statistical Research, Southwestern University Finance and Economics
School of Statisties and Data Science, Southwestern University of Finance and Economics New Cornersoone Science Laboratory, Southwestern University of Finance and Economics 'Institute for Math & AI, Wuhan University
{ogduan math, yulingj aomaahh, vincen, zjyang wath) edu. cn linhz0swufe. edu. cn
Abstract
Learning transferable data representations from abundant unlabeled data remains a central challenge machine learning. Although numerous self-supervised learning methods have been proposed to address this challenge, a significant class of these approaches aligns the covariance or correlation matrix with the identity matrix. Despite impressive performance across various downstream tasks, these methods often suffer from biased sample risk, leading to substantial optimization shifts in mini-batch settings and complicating theoretical analysis. In this paper, we introduce a novel Adversarial Self-Supervised Representation Learning (Adv- SSL) for unbiased transfer learning with no additional cost compared to its biased counterparts. Our approach not only outperforms the existing methods across multiple benchmark datasets but is also supported by comprehensive end-to-end theoretical guarantees. Our analysis reveals that the minimax optimization in Ady- SSL encourages representations to form well-separated clusters in the embedding space, provided there is sufficient upstream unlabeled data. As a result, our method achieves strong classification performance even with limited downstream labels, shedding new light on few-shot learning.
Introduction
Collecting unlabeled data is considerably more convenient and cost-effective than gathering labeled data in real-world applications. Representations learned from such abundant data can be effectively transferred to various downstream tasks, thereby enhancing model performance or reducing the amount of labeled data required. Consequently, learning representations from abundant unlabeled data both highly valuable and challenging.
Recently, self-supervised contrastive learning has emerged as leading approach for learning rep- resentations from unlabeled data. This method aims produce representations that are invariant to data augmentation. However, solely minimizing the distance between similar pairs can result in
Cooresponning author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

trivial solutions, known as model collapse. To address this issue, researchers have proposed various strategies, which can be broadly categorized into three types.
The first strategy treats augmented views from different images as negative pairs, ensuring that their representations remain dissimilar [36, 23, 8, 9, 21, 38). However, these methods require large hatch sizes to provide sufficient negative samples, resulting in substantial computational and memory demands that may be prohibitive in many applications. Additionally, by treating augmented views from different images as negative pairs, these approaches overlook semantic similarities between distinct images, potentially forcing apart representations of conceptually related content. As noted by [12, II, this design can degrade representation performance.
The second strategy prevents model collapse through asymmetric network architectures [19, 10, 6, 7]. Although these methods eliminate the need for negative pairs, they exhibit significant sensitivity to architectural design choices, where minor modifications can lead to collapsed solutions [19, 10). Furthermore, these approaches introduce considerable challenges for interpretability.
The third line of work prevents model collapse by introducing regularization term that aligns the covariance or correlation matrix with the identity matrix [37, 14, 4, 22, 3, 20, 24, 39], thereby encouraging the separation of class centers. These methods do not require negative samples and also offer clearer theoretical interpretability. typical regularization term employed in these ap- proaches [37, 22, 20, 24] is formulated as:
R()) = |B Ez,, 2. 2. (<x,))))(( - La
(I)
where f Rdd + Rd denotes representation mapping from the original image space to the representation space, ||-|| is the Frobenius norm, I, represents an original image following a distribution P., and A(x,)) denotes the collection of all possible augmented views yielded from œ,. The terms x,, x,, E A(xx,) refer to two augmented views independently sampled from the uniform distribution on A(æ.). while Ia- is a d" d' identity matrix.
The population risk defined in equation (1) is typically intractable. In [22, 20, 37, 24), the researchers estimate (1) using the following sample-level regularization:
1 Σ (xx)))()))) - 1a- 10
R( = Th
where Jeein. denotes the original dataset, and D. - ( (1) (xx,,,x (1) A(x!"))ee Jeen.. represents
the augmented dataset for learning representations. Unfortunately, it is evident that R(f) is biased estimator of RRf). ie., ED, {R(f)} # R(f), due to the con-commutativity between the expectation and the Frobenius norm. This inherent bias gives rise to two significant challenges.
Firstly, the biased estimator (2) used in [22, 20, 37] introduces significant optimization deviations during training. Although theoretically 55 (R(J)} converges to R(() as n approaches infinity, practical memory constraints necessitate the use of mini-batch samples. As a result, the bias introduces an offset in the optimization direction at each iteration. Moreover, this offset can accumulate over successive training steps, since each gradient direction depends on the previous one. Ultimately, this compounding effect may cause the learned representation to diverge significantly from the true minimizer of the population risk, thereby impairing practical performance, as demonstrated in Table 1.
Secondly, this inherent bias presents significant obstacles to establishing end-to-end theoretical guarantees, which is crucial for addressing several fundamental questions: How quickly does the downstream task error converge with respect to both the number of unlabeled samples in the source domain and the number of labeled samples in the target domain? What is the mechanism by which unlabeled data in self-supervise learning contributes to downstream task performance? Why do self- supervised learning methods remain effective even when downstream labeled data is limited?
Although recent theoretical studies have significantly advanced the understanding of self seff-supervised learning, several issues remain unresolved. These studies can be broadly categorized into two main lines of research. The first line [15, 22, 2, 24] focuses analyzing the population risk of self- supervised learning methods. However, fundamental questions remain incompletely addressed due to the lack of discussion at the sample level. A comprehensive theoretical analysis requires bridging

---

the gap between population-leve (1) and sample-level (2) risks, which is challenging due to the bias inherent in methods such as [37, 22, 20].
second line of theoretical research analyzes generalization error using Rademacher complexity [31, 21, 1, 26, 20], but frequently overlooks the approximation error. This omission is critical, overall learning performance is determined by the total error, which is the sum of both generalization and approximation errors. Consequently, by focusing on only one component, these analyses may provide an incomplete picture of model performance.
In this study, we propose novel self- learning framework, Adversarial Self- Sele--Sueeeieedd Representation Learning (Adv-SSL). Adv-SSL introduces an innovative iterative scheme that elimi- nates the bias between the population risk (1) and its sample-leve estimator (2), thereby addressing two critical challenges: training deviation and theoretical limitations caused by bias. Through compre- hensive end-to-end analysis, we demonstrate how the amount of unlaheled data in the self-supervised pre-training phase enhances downstream task performance. Specifically, we show that representation learning with Adv-SSL enables downstream data to be effectively clustered by category the repre- sentation space, provided that the upstream unlabeled sample size is sufficiently large. As a result, Adv-SSL achieves outstanding classification performance even with only few downstream labeled samples, offering valuable insights for few-shot learning.
1.1 Contributions
Our main contributions can be summarized as follows:
We introduce Adv-SSL, a novel unbiased self-supervised transfer learning method. This approach learns representations from unlabeled data by solving min-max optimization problem that corrects the bias inherent in existing methods [22. 37]. Through extensive experiments, we demonstrate that Adv-SSL significantly outperforms previous biased sample risk (Table 1), as well as several existing self-supervised learning approaches (Table 3).
We establish comprehensive end-to-end theoretical guarantees for Adv-SSL in transfer learning scenarios under misspecified setting (Theorem 1). Our theoretical analysis shows that representations learned by Adv-SSL, through minimax optimization, enable downstream data to be clustered by category in the representation space. provided that the upstream unlabeled sample size is sufficiently large. Consequently, Adv-SSL achieves outstanding classification performance even with only a few downstream labeled samples, offering valuable insights for few-shot learning.
1.2 Preliminaries
Given an integer n E N. we use [n] to represent the integer set 21, .n.. For any vector æ, we denote ||æ]|| and oo the 2-norm and co-norm of respectively. Let A, B E Rd xd2 be two matrices, we define their Frobenius inner product by B) tr(AT B). Moreover,
denote |Al|p as the Frobenius norm of A, which is the norm induced by Frobenius inner product, and [A sup]|=l] _ ||AAz//oo as the oc-norm of A, which is the maximum 1-norm of the rows of A. For vector-valued map f. we adopt dom(f) represent its domain. Further, given 0 01 S a2, [I ll2 S ag. Besides Additionally, we use
use a1 < 11fll2 I a2 to denote a S infzedom(s) (I S suPxedom((F)
that, the Lipschitz norm of f is given by ||f = suPay/ |パe-v||a if E Lip(L) to represent L| < L. Finally, if X and Y are two quantities, for ease of presentation, we employ X $ Y or Y X to indicate the statement that s CY for some C' and denote X x Y when X SY & X throughout this paper.
[1f(=)-f()llz
We subsequently adopt the following neural networks as the hypothesis space.
Definition 1 (ReLU neural networks). Let di, E and L, Ii....., ., Nr E N. A ReLU neural network with depth L and width W := max(NN, . Nr) has the following form:
fo(æ)
o (Apo: bo)) bz-1);
(NN)
where A, E R.N.4IXN, by E N=+,, and a()) is the element-wise ReL.U activation function. Denote by 0 == ((Ao, ..., bL-1), the collection of parameters of the neural network (NN).
3

---

Furthermore, define x(0) = || Ih max [A, b1) [0)))o.111 1}. For KC > 0, it follows from Appendix G.1 that Il tip K. provided that x(0) S K.
Let K > 0 and 0 < B1 < B2, ReLU network class NN d1 (W, I,, K. B1, B2) is defined as
{ Lo has the form (NN): No = d1, N1+1 d2, k0 K, B s So B2).
Finally, for two given measures 4 and v, we define the 1-Wasserstein distance as W(J, v) maxgELip(1) [x=+(((X)) - (o())
1.3 Organization
The rest of this paper is structured as follows: Section 2 introduces the core concept of Adv-SSL and presents our alternating optimization algorithm. In Section 3, we develop a comprehensive end-to-end theoretical guarantee for Adv-SSL with proof details in Section F. Section 4 demonstrates Adv-SSL's effectiveness through extensive experimental evaluations across diverse datasets and metrics. Section 5 summarizes the conclusions of this work.
The appendices provide review of existing studies (Appendix A), notation summary (Appendix B), experimental details (Appendix C), additional numerical experiments (Appendix D), discussions on assumptions (Appendix E), and complete theoretical proofs (Appendices F to G).
2 Adversarial Self-Supervised Representation Learning
2.1 Notations
Throughout this paper, use d and d' to represent the dimensions of the original image space and the representation space, respectively. We use the letter æ, and its variants to denote image instances from the source domain X, S [0, 1] with the source distribution F... Correspondingly, letter æ; and its variants for image instances from the target domain Xi S [o, 1] while P, represents the measure regarding the entry (Ix, y) with label y E [K]. In this context, we can independently and identically sample total of n, source image instances from P, and n, labeled downstream samples from Pr, and refer to them as D, = {> (e) )oe[n.] and D. {xx :1:) respectively.
use the
Since the primary objective of contrastive learning is to learn a representation that is invariant to differ- ent augmentations, data augmentation plays a crucial role in this field. A augmentation A R Rd is essentially a predefined transformation applied to original images. Common augmentations include the composition of random transformations, such as RandomCrop. HorizontalFlip, and Color Distor- tion [8]. We refer to A = (A:(-))e((m total number of data augmentations, which is finite since only a finite number of augmentations will be used in practice. Based on it, we can construct an augmented dataset D. = {x. (f) )ie[m.]. where x = -xx!!) (x) (x (0)
the collection of used data augmentations, where m is the
2.2 = (Ar, (x) ( A, (z))))))) and A,,1 and A, are independently drawn from the uniform distribution A. The Appendix summarizes the notations used throughout this work for
easy reference and cross-checking.
2.2
Adversarial self-supervised learning
The regularization term R(f) defined in (1) has been adopted in various studies [22, 20, 24] to prevent model collapse. Specifically, we aim to identify an encoder that is as close as possible f":
s" arg min S.B.
C(J) Latign (.) + AR())
Calign (ff) = Ex,.P, Ex E (l f(xx,1) - f(xx,2)
Intuitively, imposing the constraint B, < 11/l12 < B2 does not impair encoder performance, as the key aspect of data representation is the ability distinguish between features rather than the scale of their values. As we will demonstrate, this constraint actually can actually facilitate the theoretical analysis of Adv-SSL.

---

Since the expectation in this regularization term is challenging to compute practically, it is necessary to approximate it using an empirical average based on the collected samples. One of the most commonly- used empirical versions is R(() defined in (2) [22, 20J. However, as stated in Section 1, R(() is biased estimation of R()). i... E, (R()) * R(f), which introduces optimization deviation from f and hinders establishing a theoretical understanding of the empirical risk minimizer.
To address these issues, propose novel unbiased sample-level estimator for the population risk (I). A key observation that motivates Adv-SSL is that we can rewrite Rff) as
R(f) = sup R(f.G), GEG(f)
where G [dd" xd is a matrix variable, and
R(F.)) = (Ex~F, Ex, I2. (f (fxxx1) - Ga G) g()) = (G :||G| F I Vv((f)
The equation (3) holds because of the fact that (A, B)F S ||A|| | for any matrices A, of same dimension, with equality holding if and only if A B. Correspondingly, its sample-level counterpart defined (2) can be rewritten as
Ř(
sup R(f.G). GEõ(J)
where
R( = f (x)) Is
õ(f) = G xd" |||G|| S VR(1))
It can be shown that R(. -) is an unbiased estimator of the population risk R(,,)), that is, for each fixed f and auxiliary variable G,
R) (
Hence, the equivalent transformation (3) help us avoid the issue introduced by bias. Specifically, with the equation (3) and its empirical version, we learn a representation through Adv-SSL. the sample level, which can be formulated mini-max problem as follows:
min max B(J, Lalign (f) + XR(F, G), JEF GEÔIF)
1 nh ns
Latiga()) (J)
1(x(())
where F is defined as WW(W, K, B1, B2). We will specify the appropriate parameters (W, KC, Bi, B2) to satisfy the theoretical requirements in Section 3. The term Latign (f) em- bodies the core idea of contrastive learning: learning representation that invariant to different augmentations. Additionally, À 0 serves the regularization hyperparameter.
This mini-max problem naturally suggests solving it via an alternating optimization algorithm,in which G' is held fixed during the optimization of the encoder f. and f is held fixed during the optimization of G. This procedure detailed in Algorithm
Remark 1 (Detach technique). It is important to note that G5 in Algorithm has been detached from the computational graph when updating the encoder parameters O, which implies that the gradient
regarding 0 is given by the Step of Algorithm 1, rather than Voll Ei" Jo(x,, ')
(n(")),
(n (2) >
Ta-1|²= which the mini-batch gradient of R()). In this regard, such a mini-max iteration format will yield distinctly different encoder in the mini-batch scenario compared previous studies [37, 22].
5

---

Algorithm Alternative Optimization Algorithm
Require: Unlabeled dataset D. {ar²²) [en")) initial encoder parameter Og iteration horizon T, mini-batch size N, learning rate 72-
NE(n.]
1: Construct augmented dataset D { hee[o.]
2: for {0) U 1] do
JeeN S D2 of size N, where n represents the index 3: Sample a mini-batch B, = (x.
of the i-th sample in the mini-batch B, within D,.
4:
if then
Go - for (x, (n."))
(n 1 1.
5:
(x,,1 fe, (x
6:
Detach: Gu f- G..detach()
7:
end Update encoder 0, 0, moo, where Do is given by
8:
Ag V Σ
[x(x),]
-fo(x
(n
11:
Vo N
Σ
(xxx,,)
(n.
Lo Lo. Gr
9:
G++1 Ei= so (x So-m (x
(mn
1T la
Detach: Gr+1 G++1 detacch)
11: end for
12: return The learned encoder for.
The natural question that arises is whether this adversarial iteration format will lead to better performance?
To answer this question, we compare Adv-SSL against two biased self-supervised learning methods: Barlow Twins [37] and the approach proposed by [22], across multiple benchmark datasets. The experimental results, summarized Table 1, demonstrate that Adv-SSL significantly improves downstream classification accuracy compared to both baseline methods, which are implemented using our repository, with a total training of 1000 epochs and representation dimension of 512. It worth mentioning that our results are close those reported in the well-known Python package LightlySSL, suggesting our results align with expectations.
Method
CIFAR-10
CIFAR-100 100
Tiny ImageNet
Linear
k-nn
Linear
k-nn
Linear
k-nn
Barlow Twins[37]
87.32
84.74
55.88
46.41
41.52
27.00
Beyond Separability(2]
86.95
82.04
56.48
48.62
41.04
31.58
Adv-SSI.
93.01
90.97
68.94
58.50
50.21
37.40
Table 1: Top-1 Accuracy Comparison with Biased SSL Methods.
The experimental details can be found in Appendix C. In addition, more ablation studies are deferred to Appendices D.I, D.2, D.3 and D.4, which respectively involve the choice of the regularization parameter X, the impact of data augmentations, the influence of the alignment term and effectiveness terms of transfer learning.
Furthermore, it naturally raises a question of whether the minimax iteration in Adv-SSL incurs any additional training cost? Intuitively, the extra cost from adversarial updates is negligible, as the inner maximization problem admits an analytical solution, as shown in Step 9 of Algorithm 1. To further support this view, we provide detailed comparison of the timing and memory costs in Table 2.
All experiments were conducted on single Tesla V100 GPU. The time mentioned refers to the training time spent per epoch. As we seen, this observation aligns well with our intuition.

---

Method
CIFAR- 10
CIFAR- 100
Tiny ImageNet
Memory
Time
Memory
Time
Memory
Time
Barlow Twins
5598 MiB
68s
5598 MiB
74s
8307 Miß
386s
Adv-SSL
5585 MiB
51s
5585 MiB
52s
8282 MiB
352s
Table 2: Comparison of Training Memory and Time Costs Between Barlow Twins and Adv-SSI..
3 End-to-End Theoretical Guarantee
3.1
Problem formulation
We first define fn, the empirical risk minimizer for Adv-SSL. (4) and hope establish rigorous theoretical guarantee for that.
fn, arg min max G) Latign (J) GR(J,G) EEP GeOLf)
Moreover, following the similar process to that used for obtaining D. we can construct the
downstream augmented dataset D. [(x{") He(m)) where x!() = (x (1) x R2dd with
*1,1 = A (m, xt,2
(1) Aa,)(ar Therein, A;, Ai.2 are independently and identically dis-
(8))
tributed samples drawn from the uniform distribution defined on A. In this context, for a testing
sample æ, we construct the following linear probe as classifier:
Q fn, (x) = arg max (W (x))
(5)
RE(K)
where the k-th row of W is given by (b) 2m:(k) Σ
fr. (.. k).
therein, (k) El= Ls: k). Here the Adv-SSL estimator f., is defined (4). The classifier defined in (5) indicates that by calculating the average representations for each class, we build template for each downstream class individually. Whenever new sample needs to classified, is assigned to the category of the template that it most closely resembles. Furthermore, we use the following misclassification rate to evaluate the quality of fn..
Err(Q f., (2x,) + y),
(6)
Appendix B summarizes the notations used throughout this paper for easy cross-checking.
3.2 Theoretical limitation induced by bias
In this section, we aim to elucidate the limitations imposed by bias from theoretical perspective. We first assert that E,, (Frr(Q,,,)) )} s BB,, (f(f..) under specific conditions, the details of which can be found F.4.7. Consequently, analyzing the sample complexity of E,,, (f(fm.)) is essential for establishing an end-to-end theoretical guarantee for fn,. However, the bias between C(f) and its empirical counterpart Σ(ʃ) presents a significant challenge for this analysis.
In fact, in the field learning theory, the condition E,, {ε()) = [(f) is quite important to explore the sample complexity of F,,, {<(f.,)) }} Specifically, let satisfy L(f) L((*) inf inf C( where we recall R(()) is given by (2), then
C(fn.) = (C(fm,) - [(fm,)) + (ā(fm.) - + (())))))))(++0000 S (C(fn.) - -((f.)) (2(F) - -()) (((f)) -())+
< 2 sup FEF
[(J) ((())(()))))))) + inf JEF -(1))+()))+())
where the first inequality follows from the fact that fn, minimizes the empirical risk [() over F. Taking the expectation with respect to D3 on both sides yields Ep, (C(fn.)) C(f*)
7

---

+ ( Standard techniques from empirical process [17] can be used to estimate the second term in unbiased settings. However, the presence of bias complicates their direct application. In contrast, leveraging the unbiased nature of Adv-SSL, we develop a novel error decomposition as follows:
B. supper fEF
EB [(m.) S ((F) + P. {
QU,G)-
inf {an) a()} fer
sup
SEF,GELU)
(
+ ED.
sup SEF
la- E Rd and its sample counterpart La. We defer the corresponding proof to Section F.4.1. This decomposition allows us to directly apply empirical process methods to handle the second term on the hight-hand side, as presented in Section F.4.3. Regarding the other terms, the first term vanishes under Assumption 2, as demonstrated in Section F.4.2. The third term, known as the approximation error, quantifies the error introduced by using F to upproximate f*; this can be controlled using existing results from [25]. as shown in Section F.4.4. The last term can be reformulated as a standard problem concerning the rate of convergence of the empirical mean to the population mean, as discussed in Section F.4.5. By combining these results, we leverage the adversarial formulation of Adv-SSL to successfully establish end-to-end theoretical guarantee for fn..
where G*) = - Brn,,R,,,,, 2E (
G(f) = n, Eis ( (f ((a)))
3.3 Assumptions
We begin with defining the Hölder class, which plays key role in bounding the approximation error. Definition 2. Let d E N and r + 3 0, where No and B (0, 1]. We assert Rd IR belongs to the Hölder class H (I2) if and only if
0 f(x(x) - O* f(y)
10 f(x)] < 1 and max sup |
< 1,
where for a multi-index ($1, : differential operator 0= grr 8'2 0td
88) Nd and f Rd + R, the symbol 0* denotes the partial Furthermore, define H : {f [0, 1jd + R. e
Bu 8n
ax
Ha (R+)} } as the restriction of H (R.) to [0. 1]d.
In this context, we make following assumption on f":
Assumption 1. There exists a = + 3 with r E N and / E (0, s.t f E H for each i E [d*).
Assumption is a standard assumption in the nonparametric statistics [33, 32].
As for the term C(f*) in eq (7), we need following Assumption 2 to justify C(f*) =
Assumption 2. Assume there exists measurable partition (PI...., Pa- } of X, satisfying (P.). e
1 B
for each E [d*].
Assumption 2 requires that the source data distribution is not overly singular. In particular, all common continuous distributions defined on the Borel algebra satisfy this condition, as the measure of any single point zero. Further details regarding the vanishing of L(f") are provided in Section F.4.2.
Additionally, we introduce two assumptions regarding the data augmentations.
Assumption 3. Assume any data augmentation A; E A is M-Lipschitz continuous, that is, [I)(())) (v) < M||a Ull for any x. y [0, 1]d.
The most commonly used augmentations, including cropping, horizontal mirroring, color jittering, grayscale conversion, and Gaussian blurring, actually all satisfy this assumption. See Section E.
In addition to the Lipschitz property of data augmentation, we adopt Definition to mathematically quantify the quality of data augmentations. To present it, we define (k) as set such that E (k) and only if æ, belongs to the k-th class. Correspondingly, similar to [24], we assume that any upstream instance x, can be categorized into one or more latent classes {C, (k))k(()))
8

---

Definition 3. A data augmentations is referred to as (0,, (2)) augmentaatiss if for each k e
[K], there exists two subsets C. _ (kk and (k)) (k) such that (i) Ps (x,, C. 2
(zp C.()),, (ii) sup s.
| - x2,2112 S dzi (iii)
Pa E (())) 2 apPi(an E C,()), (iv) sup mi min )l xt.2 1,a S 6, and (v) PA ((())) 2 ot, where 0x ot E (0, 1] and 6,, 6, 20. 0.
xx,1
Broadly speaking, this definition emphasizes that robust data augmentation should consistently produce distance-closed augmented views for semantically similar original images. We refer to Section F.2 for further explanations. In this context, introduce the following assumption to delineate the data augmentation necessary for the end-to-end theoretical guarantee of Adv-SSL.
Assumption 4 (Existence of augmentation sequence). Assume there exists a sequence of [E[[m]
(o." (n) ,.!") ,6(")) )- augmentations A, )E{()) such that (i) max
((()))
g!m) (5t)) S
-1+1 FRF3 holds for some e 0, (ii) min
(n) oi (n)) 1 as n2 oc.
It is noteworthy that this assumption closely aligns with [21, Assumption 3.5] and [20, Assumption 3.6), both of which require the augmentations must be sufficiently robust to ensure the internal connections within latent classes remain strong enough to prevent the separation of instance clusters.
We next introduce the assumption related distribution shift. Prior to characterizing the transferability from the source domain to the target domain, we must first quantify the similarity between these domains. For ease of presentation, let (k) probability distribution of the source data that categorized into the k-th latent class C, (A), i.e., P. (k)))))== = P. (-1 E (k)). Similarly, let (r(k) = Pr (2 C.(k)) and (-(k)(-) = Pr( la, E C (k))). In this context, we make following assumption:
(s Cs(k)) and denote P., (R) as the
Assumption 5 (Domain shift). There exists a eds > such that both maxke]k] (P), P.(K)) z
1d11 and ma (p.(k) (c)) S n Z0=d+13
2(44441)
78.
Generally speaking, smaller cas indicates less discrepancy between the source and target domains.
Similar assumptions using alternative divergence measures have been proposed in [5, 16, 13). To help readers quickly understand this assumption, we discuss it more specifically in Section E.3.
3.4 End-to-end theoretical guarantee
We present the end-to-end theoretical guarantee as follow and defer its proof to Appendix F.
Theorem 1. Under certain Assumptions, set W 2 n2g I L 2 (llog2(d r)] + 2. x
7
and A = An, (excellent data augmentation), then we have ED..D, {Err(Q fm. )} 2 (1 (m=))) +n,
minio cuith) 22ta ar1)
mink V (n)(k)
for sufficiently large Yh.-
Interpretation of sample complexity regarding n, The upper bound of misclassification error in Theorem offers several key insights into the convergence behavior regarding n., First, as the data dimensionality d increases, the convergence rate with respect to the sample size n, slows down, reflecting the curse of dimensionality, In contrast, the augmentation quality с increases, indicating better augmentation, the convergence rate of the upper bound on the misclassification rate with respect n1, improves. Similarly, éds measures the extent of the shift between the source and target domains. A larger éds indicates the difference between the domains is smaller, a smaller domain difference, which makes the transfer learning task easier and further improves the convergence rate regarding n, increases. Finally, when both εд and eds exceed a, the convergence rate adopts a typical form found in nonparametric statistics [32], specifically 32(o+++11)
Few-shot learning Theorem demonstrates how the abundance of unlabeled data in the source domain leveraged by Adv-SSL benefits downstream tasks in the target domain. Specifically, the

---

classification error of downstream tasks consists of three components: the first depends on the data distribution, the second diminishes as the number of unlabeled data the source domain increases, and the third approaches zero the quantity of labeled data in downstream tasks grows. Furthermore, when a sufficiently large number of unlabeled samples the source domain available, such that
16jo+d=1) na 2 ming (A) A then ED, D. [Er(Q )} 2 (1 - ds (m))) + mine (n.(k) This find-
ing indicates that classifiers powered by the representation learned by Adv-SSL can achieve excellent performance with minimal labeled samples, thereby providing rigorous theoretical understanding for few-shot learning [28, 30, 35, 27].
How does the rate change as m increases If we consider the case where m increases with n2. according to our theoretical guarantee, we have following conclusions:
minta A.
DD (Er(QQ )} x (1 -
(1-o!-))) o! + +mnn
32t (UT1)
ming (n,(()
minfa.s Astael 64(a+441)
First of all, long as m X ns However, as the growth rate of m increases, the convergence rate with respect to n, becomes slower. This result is intuitive: larger implies that more potential knowledge must be learned from the data, which in turn requires a larger sample size to maintain the same level of misclassification rate. min(o.r aitde the resulting convergence rate 7yg 64(or1111))
the desired asymptotic property can be guaranteed.
minla.t ddgel 128tadd11)
For instance, if we set m x n2y
Comparison with Existing Methods
As the experiments conducted in existing self-supervised learning methods, pretrain the repre- sentation on CIFAR-IO, CIFAR-100 100 and Tiny ImageNet, and subsequently conduct fine-tuning on each dataset with annotations. Table 3 shows the classification accuracy of representations learned by Adv-SSL, compared with baseline methods including SimCLR [8], BYOL [19], WMSE [14]. where the results has been reported in [14]. In addition, we also compare Adv-SSL with VICReg [4] and LogDet [39]. The presented result shows that Adv-SSL consistently outperforms previous mainstream self-supervised methods. The experimental details are deferred to Section and the implementation can be found in https://ittubb.com/iii wwtmm//incen-iihuiee witeeeenggitttt//ige Sittt-gitthhhhhh/////// SSI.
Method
CIFAR-10
CIFAR-108
Tiny ImageNet
Linear
k-nn
Linear
k-nn
Linear
k-nn
SimCLR
91.80
88.42
66.83
56.56
48.84
32.86
BYOL
91.73
89.45
66.60
56.82
51.00
36.24
WMSE2
91.55
89.69
66.10
56.69
48.20
34.16
WMSE4
91.99
89.87
67.64
56.45
49.20
35.44
VICReg
91.23
89.15
67.61
57.04
48.55
35.62
LogDet
92.47
90.19
67.32
57.56
49.13
35.78
Adv-SSL
93.01
90.97
68.94
58.50
50.21
37.40
Table 3: Top-1 Accuracy Comparison for Different SSL Methods.
5
Conclusion
In this paper, we propose novel adversarial contrastive learning method for unsupervised transfer learning. Our approach achieves -ftte-af-the-art classification accuracy on various real datasets, outperforming existing self supervueee learning methods under both fine-tuned linear probe and k-NN protocols. Additionally. we provide an end-to-end theoretical guarantee for downstream classification tasks misspecified and wvrr-parameterized settings. Our analysis shows that misclassification rate depends primarily on the strength of data augmentation applied to large amounts of unlabeled data, and offers new theoretical insights into the effectiveness of few-shot learning for downstream tasks with limited samples.
10

---

Acknowledgments
This work has been funded by the National Key Research and Development Program of China (No. 2024YFA1014200 No. 2023YFA 1000103, No. 0022YFA1033002 the National Natural Science Foundation China (Nos. 123B2019, 12125103, U24A2002, 12371441, 12426309), and the Fundamental Research Funds for the Central Universities.
References
[1] Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Dipendra Misra. Investigating the role of negatives in contrastive representation learning. In Gustau Camps-Valls, Francisco R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 7187-7209. PMLR, 2022.
[2] Pranjal Awasthi, Nishanth Dikkala, and Pritish Kamath. Do more negative samples necessarily hurt in contrastive learning? In International conference on machine learning, pages 1101-1116. PMLR, 2022.
[3] Wele Gedara Chaminda Bandara, Celso M. De Melo, and Vishal M. Patel. Guarding barlow twins against overfitting with mixed samples, 2023.
[4] Adrien Bardes, Jean Ponce, and Yann LeCun. Vicreg: Variunc-iinvarancc--ovraaa regu- larization for sele-super learning. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
[5] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. theory of learning from different domains. Machine learning. 79:151-175, 2010.
[6] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. Advances in neural information processing systems, 33:9912 1999412-9924, 2020.
[7] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self- caf-ssueerviee vision transformers. In Proceedings of the JEEE/CVF international conference on computer vision, pages
2021.
[8] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. simple framework for contrastive learning of visual representations. In International conference machine learning, pages 1597-1607. PMLR, 2020.
[9] Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003.0422 2020.
[10] Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 15750-15758, 2021.
[11] Ching- Yao Chuang, R Devon Hjelm, Xin Wang, Vibhav Vineet, Neel Joshi, Antonio Torralba, Stefanie Jegelka, and Yale Song. Robust contrastive learning against noisy views. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16670-16681, 2022.
[12] Ching- Bao Chuang, Joshua Robinson, Yen-Chen Lin, Antonio Torralba, and Stefanie Jegelka. Debiased contrastive learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 8765- 8775. Curran Associates, Inc.. 2020.
[13] Corinna Cortes, Mehryar Mohri, and Andrés Muñoz Medina. Adaptation based on generalized discrepancy. Journal of Machine Learning Research, 20(1):1-30, 2019.
11

---

[14] Aleksandr Ermolov, Aliaksandr Siarohin, Enver Sangineto, and Nicu Sebe. Whitening for self-supervised representation learning. International conference on machine learning, pages 3015-3024. PMLR, 2021.
[15] Quentin Garrido, Yubei Chen, Adrien Bardes, Laurent Najman. and Yann Lecun. On the duality between contrastive and non-contrastive self-supervised learning. arXiv preprint arXiv:2206.02577 02574, 2022.
[16] Pascal Germain, Amaury Habrard, François Laviolette, and Emilie Morvant. pac-bayesian approach for domain adaptation with specialization to linear classifiers. In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, number 3 in Proceedings of Machine Learning Research, pages 738-746, Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR.
[17] E. Giné and R. Nickl. Mathematical Foundations of Infiiite-Dimenssionn Statistical Models. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2016.
[18] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the s1 Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 297-299. PMLR, 06-09 Jul 2018.
[19] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach to self-supervised learning. Advances in neural information processing systems, 13:21171-221881 2020.
[20] Jeff Z. HaoChen and Tengyu Ma. A theoretical study of inductive biases in contrastive learning. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OvenReview.net, 2023.
[21] Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- supervised deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34:5000-555 5011,, 2021.
[22] Jeff Z. HaoChen, Colin Wei, Ananya Kumar, and Tengyu Ma. Beyond separability: Analyzing the linear transferability of contrastive representations to related subpopulations. In Sanmi Koyejo, S. Mohamed, Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 December 9, 2022, 2022.
Neural Information
[23] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9729-9738, 2020.
[24] Weiran Huang, Mingyang Yi, Xuyang Zhao, and Zihao Jiang. Towards the generalization of contrastive self-supervised learning. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
[25] Yuling Jiao, Yang Wang, and Yunfei Yang. Approximation bounds for norm constrained neural networks with applications to regression and gans. Applied and Computational Harmonic Analysis, 65:249-277 278, 2023.
[26] Yunwen Lei, Tianbao Yang, Yiming Ying, and Ding-Xuan Zhou Generalization analysis for contrastive representation learning. In International Conference on Machine Learning, pages 19200-19227. PMLR, 2023.
[27] Jit Yan Lim, Kian Ming Lim, Chin Poo Lee, and Yong Xuan Tan. Sel: Self-supervised contrastive learning for few-shot image classification. Neural Networks, 163,1,,0,, 2023.
12

---

[28] Chen Liu, Yanwei Fu, C. Xu, Siqian Yang. Jilin Li, Chengjie Wang, and Li Zhang. Learning few-shot embedding model with contrastive learning. In AAAI Conference on Artificial Intelligence, 2021.
[29] Andreas Maurer. A vector-contraction inequality for rademacher complexities. In Algorithmic Learning Theory: 27th International Conference, ALT 2016, Bari, Italy. October 19-21, 2016, Proceedings 27, pages 3-17. Springer, 2016.
[30] Mamshad Nayeem Rizve, Salman Khan, Fahad Shahbaz Khan, and Mubarak Shah. Exploring complementary strengths of invariant and equivariant representations for few-shot learning. In Proceedings of the IEEE/CVF conference on computer vision and pallern recognition, pages 10836-10846, 2021.
[31] Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khande- parkar. theoretical analysis of contrastive unsupervised representation learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97
of Proceedings of Machine Learning Research, pages 5628- 5637. PMLR, 2019.
[32] Johannes Schmidt-Hieber. Nonparametric regression using deep neural networks with ReLU activation function. The Annals of Statistics, 48(4):1875 1897, 2020.
[33] A.B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer New York, 2008
[34] Roman Vershynin. Highh-Dimessooal Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
[35] Zhanyuan Yang, Jinghua Wang, and Yingying Zhu. Few-shot classification with contrastive learning. In European conference on computer vision, pages 293-309. Springer, 2022.
[36] Mang Ye, Xu Zhang, Pong C Yuen, and Shih-Fu Chang. Unsupervised embedding learning via invariant and spreading instance feature. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 6210-6219, 2019.
[37] Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self- supervised learning via redundancy reduction. In International conference on machine learning, pages 22310-12320. PMLR, 2021.
[38] Qi Zhang, Yifei Wang, and Yisen Wang. Identifiable contrastive learning with automatic feature importance discovery. In NeurlPS, 2023.
[39] Yifei Zhang, Hao Zhu, Zixing Song, Yankai Chen, Xinyu Fu, Ziqiao Meng, Piotr Koniusz, and Irwin King. Geometric view of soft decorrelation in self-supervised learning. In Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, KDD '24, page 4338-4349, New York, NY, USA, 2024. Association for Computing Machinery.
13

---

Contents
Introduction
1.1
Contributions
1.2
Preliminaries
1.3
Organization
2
Adversarial Self-Supervised Representation Learning
2.1
Notations
2.2
Adversarial supe-vud learning
3
End-to-End Theoretical Guarantee
3.1
Problem formulation
3.2
Theoretical limitation induced by bias
3.3
Assumptions.
3.4
End-to-end theoretical guarantee
4
Comparison with Existing Methods
10
Conclusion
10
6
Acknowledgments
11
A Related Works
15
Notation List
15
Experimental Details
16
Additional Numerical Experiments
17
D.I Ablation study on the regularization parameter
17
D.2 Ablation study on the data augmentations
17
D.3 Ablation study the alignment term
17
D.4 Transfer learning
18
Additional Discussions Assumptions
18
E.1 Discussions on assumption 3
18
E.2 Discussions assumption 4
19
E,3 Discussions assumption 5
20
F Proof of Theorem
21
F.1
Proof sketch
F2 Sufficient condition of small misclassification rate
F3 The effect of minimaxing Adv-SSI.
24
14

---

F.4
The sample complexity of E D, {f(fr.)}
32
F4.1
Risk decomposition.
33
F.4.2
Vanishing L()*)
35
F.4.3
Upper bound of Esta
36
F444
Upper bound of &
37
F44.5
Upper bound of Eg
E.4.6
Trade-off several errors
39
E44.7
The proof of primary theorem
39
G Auxiliary Lemmas
41
G.1 KC-Lipschitz property of NW do (W, L, K., B1, B2)
41
G.2 Lipschitz property of
42
A Related Works
Self-super contrastive loss The loss function proposed by [22] can be regarded as special version of Adv-SSL with the constraint Xs,1 = xx.2- The main difference between Adv-SSL and the approach by [22] lies in the iteration format. As stated in Section 1, optimization deviation accumulate with each iteration, particularly in the mini- bani-batch scenario, while Adv-SSL employs adversarial training mitigate this issue. The same problem is encountered by [37], which can be loosely regarded as a biased sample version of (1).
Self-supervised theory Recent theoretical studies be categorized into two main lines of research. The first line [15, 22, 2, 24] focuses on analyzing the population risk of self-supervised learning methods, which can not characterize how the error in downstream tasks diminishes with increasing sample size. The second line of research [31, 21, 1, 26, 20] studies the generalization error through Rademacher complexity without the consideration of approximation error. However, the absence of approximation етгог renders the resulting generalization eπror analysis ineffective. Specifically, ignoring the approximation error by simply supposing f belonging to deep neural network class, the Rademacher complexity can be significantly reduced by controlling the scale of the network class, leading to impressive upper bounds. However, this controlled neural network class intuitively limits its approximation capacity. The increasing approximation error results in a larger overall error. Therefore, these studies cannot provide theoretical guidance for hypothesis class selection nor fully characterize the total еrror of self-supervisee learning methods. In contrast, our work provides comprehensive convergence analysis that characterizes how the downstream task error converges with respect to both the number of unlabeled samples in the source domain and labeled samples in the target domain.
B Notation List
To reduce confusion and enhance comprehension regarding the symbols used in this study, have created a list to provide readers with a convenient reference. This list directs readers to the first occurrence of each symbol in the relevant sections equations. Within this table, the symbol indicates an option for s or t, representing the source domain and the target domain, respectively.
Symbol
Description
Reference
Du
dataset
Section 2.1
d'
representation dimension
Section 2.1
mx(k) A
sample size of k-th target class data augmentation
Equation (5)
Section 2.1
Continued next page
15

---

Symbol
Description
Reference
m
number augmentations
Section 2.
M
Lipschitz constant of augmentations
Assumption
(
augmented view concatenated augmented view
Section 2.1
(0
Section 2.1
D,
source augmented dataset target augmented dataset the number classes k-th source/target class main part of C=(k)
Section 2.1
D
Section D.4
K
Section 2.1
(a(
Definition 3
(-(k) P.
Definition 3
data distribution
Section 2.1
(n(k)
distribution conditioned on En E C.(k)
Assumption
(n(k)
probability of z E (n(k)
Assumption
Polk)
k-th representation center
Lemma and
(k)
k-th empirical center population optimal encoder sample optimal encoder classifier based on fn, misclassification error Wasserstien Distance neural network hypothesis space feasible set of G alignment term regularization term regularization term parameter of Hölder class augmentation parameter distribution shift parameter parameters of augmentation distribution shift
Equation (5)
f
Equation (2.2)
fr.
Equation (4)
Qj
Equation (5)
Err
Equation (6)
W F G())
Section 2.1
Equation (4)
Section (2.2)
Latign
Section 3.1
R(J.))
Definition 3
R(f)
Definition
a
Definition 2
EA
Assumption
Eds
Assumption
ou: be
Definition' 3
Equation (17)
W. W,L,K, B,, B2
parameters of neural network
Definition
Table 4: Summary of Symbols
C Experimental Details
Implementation details. Except for tuning for different datasets, all other hyperparameters used in our experiments align with [14]. We train for 1,000 epochs with a learning rate x 10 for CIFAR-10 and CIFAR-100, and x 10 for Tiny ImageNet. A learning rate warm-up is applied for the first 500 iterations the optimizer, in addition to 0.2 learning rate drop at 50 and 25 epochs before the training end. We use mini- batch size of 256, and the dimension of the hidden layer in the projection head is set to 1024. The weight decay is set to 10-3. We adopt an embedding size (d") ) of 512. The backbone network used in implementation is ResNet- 18.
Image transformation details. We randomly apply crops with sizes ranging from 0.08 to 1.0 of the original area and aspect ratios ranging from 3/4 to 4/3 of the original aspect ratio. Furthermore, we apply horizontal mirroring with a probability of 0.5. Additionally, color jittering is applied with configuration of (0.4: 0.4: 0.4; 0.1) and probability of 0.8, while grayscaling applied with probability of 0.2. For CIFAR- 10 and CIFAR-100 100, random Gaussian blurring adopted with probability of 0.5 and a kernel size of 0.1. During testing, only crop is used for evaluation.
Evaluation protocol. During evaluation, we freeze the network encoder and remove the projection head after pretraining, then train a supervised linear classifier on top of it, which is a fully-connected layer followed by softmax. we train the linear classifier for 500 epochs using the Adam optimizer with corresponding labeled training set without data augmentation. The learning rate is exponentially decayed from 10-2 10-6, The weight decay is set as 10-4 we also include the accuracy of k-nearest neighbors classifier with & 5, which does not require fine tuning.
16

---

All experiments were conducted using single Tesla V100 GPU unit. The PyTorch implementations can be found in supplementary material.
D Additional Numerical Experiments
D.1 Ablation study on the regularization parameter
The regularization parameter À in Adv-SSL balances the alignment term Lalign and the regulariza- tion term R(.). Our theoretical analysis suggests that À = O(1). Specifically,
In Lemma 4, we demonstrate that the alignment factor Re(E, f) can be bounded by the alignment term faliggn (-), while the divergence factor max (1((1) p&(i)l bounded by the regularization term R(-).
Based on the definition of the population risk C(f) = Calggn (f) + XR(f), we find
aalign 2 L(F) and R() - X ( X C()),
where used À = O1). This allows us to bound both the alignment factor RE, f) and the divergence factor maxişj (t) (e)) in terms of the population risk L(J), which leads the conclusion 5.
Regularization parameter
CIFAR-10
CIFAR-100
Linear
k-nn
Linear
k-nn
À = 5.0 10
90.11
87.72
67.59
57.34
À = 1.0
x 10-4
90.53
88.12
68.01
57.59
À 5.0 10
92.24
89.99
68.24
58.35
À 1.0 10-3
92.01
90.18
67.88
57.89
À = 5.0
10-3
92.11
90.01
68.12
57.66
À 1.0
10
92.47
90.33
68.94
58.50
À 5.0
10
93.01
90.97
67.68
57.13
À = 1.0 10-1
92.77
90.38
67.82
57.49
À 1.0
91.75
89.76
66.78
56.76
Table 5: Comparisons of Adv-SSL with different regularization parameters.
D.2 Ablation study on the data augmentations
random cropping
grayscale
color distortion
random horizontal flipping
CIFAR-10
Linear
k-nn
93.01
90.97
91.03
88.34
89.18
85.65
79.32
69.81
Table 6: Downstream performance of Adv-SSL under different richness of augmentations.
D.3 Ablation study on the alignment term
The loss function (4) proposed in this work consists of an alignment term and a regularization term. In contrast, Barlow Twins [37] does not require the alignment term. In this subsection, we show whether this additional alignment term necessary for this method.
[24, Lemma 4.1] has demonstrated that the the diagonal part of the cross-correlation matrix serves as a alignment term under certain conditions. Indeed,
Ex,oP, Ex, a(ee)))) ( - f1(xx.2))²)

---

Ex zEA(r,)
2E ~P, Ae. { (z.(x..1) + f((x22)) 2z Pr, Ex Ea(2) { (x.)) ~P,
-P, 2x. (
where the second equality holds from that xs,1 and xx.2 follow the same distribution. The alignment risk is then related to the diagonal part of the cross-correlation matrix as:
d
Falign (J) =
Ba, -F, R2, (.. (Ui(z.)) - f((xx,2) ))
(5 RR Bx ( (xx)) - Be Be, Maaee
< 4d
Ex, ~p, Bx, E(()) (x,))
where the last inequality follows from Baeway-Sehwarz inequality. It crucial that the right-hand side of the inequality is consistent with the alignment term in the loss function of Barlow Twins, provided that Eg, ~e, E((m) (x 1 for each E {l...., d]. However, this condition does not hold generally.
Therefore, from theoretical perspective, the cross-correlation loss alone, used in Barlow Twins [37], is insufficient for learning representations invariant to augmentations, as previously discussed. To address this, introduce an additional explicit alignment term in the loss, as also suggested by [22, 20].
From a practical perspective, we conduct ablation study comparing Adv-SSL with and without the explicit alignment term. Our results shown in Table 7 indicate that the inclusion of the explicit alignment term improves Adv-SSL's performance.
Method
CIFAR-10
CIFAR-100
Linear
k-nn
Linear
k-nn
Adv-SSL without alignment
92.42
90.01
67.27
58.10
Adv-SSL with alignment
93.01
90.97
68.94
58.50
Table 7: Comparisons of Adv-SSI. without and with the alignment term.
D.4 Transfer learning
To align the experiments with the theoretical settings, we conduct simple additional experiment in terms of transfer learning. Specifically, we transfer the representation trained on CIFAR-I00 to CIFAR-10. 10. Compared to the performance of Barlow Twins [37], we can see that Adv-SSL indeed has strong transferability in practice, as demonstrated in our theory.
Methods
Linear
k-nn
Barlow Twins[37]
73.56
66.34
Beyond Separability[22]
74.11
66.79
Adv-SSI.
80.57
73.41
Table 8: Transfer learning from CIFAR-100 to CIFAR-10
E
Additional Discussions on Assumptions
E.1 Discussions assumption 3
Assumption is mild and numerous commonly-used augmentation methods satisfy this assumption. Specifically, all of the augmentation methods used in experiments meet this requirement.
18

---

As outlined in Section C, the data augmentations used in our experiments, including crops, horizontal mirroring, color jittering, gray scaling, and Gaussian blurring, are indeed Lipschitz continuous. the following, we provide detailed justification for each of these transformations.
Crops: For each image Rd crop of this image is defined as Crop(æ; æ,, for some index set 1 _ (l,...,,.. .d......d..... d}. The Lipschitz continuity follows from the fact that:
|| Crop(æ; I) Crop(y; 1)1l
|
yr yr
(a; y:)
NE1
( y.)² 1|0 y122.
Thus crop is I-Lipschitz.
Horizontal mirroring: For each image a E R a horizontal mirror of this image can be formulated as Mir æy, where the index a rearrangement {I....,de , d}. We find
Mirror(x) Mirror (y) ||,1 yr Σ 21 y1)
a y1)² = 1| - y11..
Thus horizontal mirroring is I-Lipschitz.
Color jittering: As an example, consider the brightness adjustment for color jittering. The color jittering operator is defined as Jitter(x) clip( 0, 1) for some adjustment factor > 0. If 1, the image becomes brighter; a 1, the image becomes darker. Then
|| Jitter(ar) Jitter(y)15 (clip(axr, 0, 1) clip(ayr,0,1) 0,1))
(ax) ayr)² s a²ll v1
Thus color jittering is a-LLipschitz.
The grayscale transformation is a weighted sum of the RGB channels. For a RGB image Rdd the red channel is defined æR (xr) d/3 the green channel is defined as
Grayscaling:
DG == (a.) and the blue channel is defined as œB == (x, ( 24/3: The grayscaling of this image is defined as Gray(æ) aæ 3xg + w z for some 7, (0, 1). The Lipschitz continuity follows from:
Gray(ar) Gray(y) S a a| ynll2 + 3 - yall2 + + - ynll
s max(fa 3, < yl12.
where the first inequality holds from Jensen's inequality. Thus grayscaling is max(o, 3, 3,7)-3,--shpihii
Gaussian blurring: Gaussian blurring applies a Gaussian kernel to smooth the image, reducing high-frequency noise and detail. The blurred image GaussianBlur((z; σ) x K₂ is defined by convolving the original image z with a Gaussian kernel Kg- Convolution a linear operation, and well-known that convolution with Gaussian kernel is Lipschitz continuous, where the Lipschitz constant depends on the kernel size and a. Therefore, Gaussian blurring is Lipschitz continuous with constant that depends the kernel size and
E.2 Discussions on assumption
The concept of (ax, 8., ot, -ugameemetntio is introduced quantify the concentration of augmented data, which is extensive version of (a,, 5.) augmentations proposed by [24, Definition 1] in terms of transfer learning. We now provide step-by-step explanation:
19

---

Augmentation distance: for given augmentation set A, the augmentation distance between two samples a and y are defined as the minimum distance between their augmented views: ||x ||x-y|la Since augmentations can capture partial semantic
| ur-yyle y == A()) meanings the original sample through various views, this augmentation distance reflects the maximal semantic similarity between the two samples.
oy-main-part part of the latent class: for a latent class in the source domain (.()), the o,-main- part is defined as (k) C (k)) satisfying Ps, (æ E C.))) 2 o,P,, (x E (k)).. The parameter o, quantifies the concentration of the distribution P.(()(-) == P. E (A)) of this latent class. Specifically, for fixed sets (k) and C, (k), larger value of os indicates a higher concentration of the distribution P., (k)..
Augmentation diameter of the o, o--main-part part: the parameter 6, is defined as the diameter the o.-main-part in augmentation distance, that is, sup (EE,(())) || - yll.A. For fixed distribution IP, and a fixed parameter 0s, the smaller value of the diameter 6, means a higher concentration of the augmented distribution, well as greater similarity between augmented data samples.
Summary for (a,, 6.) au-mmmetmtttt::::: The concentration of the augmented distribution, as measured by the pair of parameters (a,, 82), depends on both the distribution (k) and the augmentation set A. Specifically, for fixed augmentation set A, a smaller value of as and higher concentration of PP (A) result in smaller d.-main-part (k),,, leading smaller value of 6,. Additionally, for a fixed distribution (A:), a smaller value of a, and a larger augmentation set lead to smaller augmentation distances || ylla for each pair of samples (x, y), resulting in smaller value of 5g.
The conditions (i)- in Definition 3 can be considered an extensive version that takes into account the difference between the source domain and the target domain.
The extra condition (v) in Definition 3 replaces the assumption ((C nA((C,)) = required by [24]. This implies that the augmentation methods used should be intelligent enough to recognize objects that align with the image labels in multi-objective images. A straightforward alternative to this requirement to assume that different classes (k) are pairwise disjoint, meaning that for all i j,C(() (j) = 0, which implies that Σ (((C(())) = dt. k=1
PP( ( (,(K)) = P.
To ensure readers can get quickly understanding for the Definition 3, we provide following example:
Example 1. Suppose the samples in the k-tth latent class follows the uniform distribution on [0, R), i.c. (k))) [0, R) and P. (k) (0, R). For each 0, E (0, 1], we can find a o a-mai--parr of C. as (A) = [0. o. R) Further, we define the augmentation set as A(x) = {x E R |a x S r) for each z E X. Then the augmentation diameter 6, of the σr, -ain part is given
sup x.yEč, (R)
||x vIla max (a, 2r, 0} 8,.
The parameters J., 8., and It are interrelated by this equality. Note that the parameter R reflects the concentration of the distribution (k) within the latent class. A smaller value of It indicates higher concentration of P. (k)). which in turn leads to smaller value of the augmentation diameter dg Additionally, larger augmentation set, i.e., larger value of r, results in smaller value of the augmentation diameter 8,.
E.3 Diseussions assumption 5
Assumption 5 is common in the theory of transfer learning, such as [5, 16, 13]. We now provide concrete example for more intuition. Consider the following example using nie-dmensiioal Gaussian mixtures. Specifically, we define the source and target distributions as follows:
K
P
w. (k)),,(),,
Σ
w,(k) 1,
20

---

K Pr
K
wi (K)P.))))
Σ wi(k) =
where the distributions of each latent class are Gaussian:
P. (k) (m,,(k)),)) Pr(k) == (f)( 1sksK.
Then the parameter e the maximum distance between the means of the source and target distribu- tions for each latent class:
max (().
kE[K] max (lus(k) (e())))}
KE[K]
Additionally, the parameter 62 is the maximum distance between the mixture weights of the source and target distributions:
= max w. (k) w,)k)). kE[K]
Thus, Assumption 5 not only requires that the source and target distributions for each latent class close in terms of their means, but also that their mixture weights are similar.
F
Proof of Theorem 1
F1
Proof sketch
In this section, we focus providing the proof sketch for Theorem 1. Based on [24], we begin by exploring the sufficient condition regarding the downstream error bound, as shown in Lemma 1. Specifically, it reveals that the error bound Err(Q,) S (1 (1-o,) o,) + R.(e, f) holds under the condition maxişj 14, (i) f. (2 E, f). The naturally raised question is whether minimaxing the risk of Adv-SSI. can help us meet the required condition. To answer this question, we establish Lemma in Section F.3, which reveals that minimizing the risk of Adv-SSL can achieve the requirement maxi4j (i) M4 < (a, & e, f). Meanwhile, its directly induced corollary 1 indicates that we should explore the sample complexity of EB, (C(N}- To this end, we begin by developing novel error decomposition approach in Section F.4.1, which decouples E,, {<(f) into four terms: L(f*). the statistical error Esta regarding the neural network class J. the approximation eиror &x. and the error induced by the dual variable Eg. We then deal with them individually in Sections F.4.2. F.4.3, F.4.4, and F.4.5 respectively. Subsequently, we conduct the tradeoff to obtain the sample complexity of E,, [{()} and the corresponding parameters of the network, including width, depth, and norm constraint. Based on these results, we can derive the desired error upper bound for Adv-SSL, as shown Theorem 1, which completes the proof.
can
F.2 Sufficient condition of small misclassificatton rate
To begin with, let pr == Ec. ExE (s(x))) = p=(k) BR ExIE [f(x)) far (k)))]] inspired by [24], we have following lemma.
Lemma 1. Given a (a o 61) (al--aagmentation if the encoder f such that B1 S [1fl| 1 Bg is K-Lipschitz and
pe(1) mx(i) < B3yb(o,, 8,, E,),
holds for any pair of (i,3) with i j. then the downstream error rate of Q,
Err(Q,) < (1-o,) Re(,,f))
where Re(E, f) Pr( E X; SuP (xf() (xx2))l2
E). vlor, E,
mmin(ar, E,,,, f)) 2 - 2l mi (oe, de,
min ix (k))
2 2 (8c (k)
B3
B1
herein, T miiu( E,,5, f) (o.
Re(e.f)
)
1
2
2r.
min; po(3)
Br
B2
B3
21

---

Proof. For any encoder f. let S,(5,f) f E Ne i ( (xf(x))) - f S {t) any 2, E Err(Q,) can bounded by (1-0,) + RR,, In fact,
can be correctly classified by Qy, it turns out that
Err(Q,) P((or(m)) * s (C((((()).--.C.)))))))))))))))
= (K())) f)M s (1 -1 o1) + (s f)}
= =1 (1- + f)
The first row is derived from the definition of Err(Q,). Since any æ, E (Č,(1) U U (K)) n (, f) can be correctly classified by Q,. we obtain the second row. De Morgan's 's laws imply the third row. The fourth row follows from Definition 3. Finally, noting that R, f) P., (R [) yields the last line.
Hence it suffices to show for given E [K]. x E C S((,f) can be correctly classified by 1 if for any j * i,
(() m4(1) B3 (T,(,,;,,,ef)) -----220200- (o,,
1 (
minke[K] 11 (A:)l
2
B3
[1ūe(t))
m4(1)l2
lide(t) po(illl))
B2
B2
where [i 8, = (a+ Re(es) pe(a)
(1
2
Kb.
25
B2
B2
B2
To this end, without losing generality, consider the case i = 1. To turn out æ, E can be correctly classified by Q, by the definition of (1() and Se(e, f), It just need to show vk + 1, (zx)))) - (c(1))l2 < (z)) pe((k)llz which is equivalent to
( (1)0 [1(a(())12) O.
fa::) T in (1) (xx)) (a)(k))))))))))))))))
We first deal with the term f(x:)) (c))).
(1))) = ((x)) T (e(( + (xx,) -
(a(1)
2 f(x))) (1) Ex)(m))))))) (xx) (I(aaall m((1)l2
T E2, E2 [xxx11 cc()]]
(c(
(RRT), E. F [(xx)
f(xz) T "EENP, Eer Bre)) [(x))1{
pr(1)
(8)
- (e]1(t(1)-Hx11))))
(((c, f(x.) ( Bacds.orssccpleesstelllllll
Pt(1)
Pc(1) ERiNZi
B2 21)()]
P. (FCCC(1) f(xx)
E
E (f(x:)
(1(1)
e (m(())
B3
P. [CCC))CC. B2 B2ll)((1) -mo(1)lz p.(1)
(9)
22

---

The second row follows from the ==((aanv60))@@anntsss....
inequality. The third and last rows are derived
from the condition Il. I Bz. Note that
P.GOYEOOSS( = = =
(10)
<(100))i(1) + f(,,
(11)
and
(12)
2 2 (1 Rc(e,f)
= - -
(13)
Plugging (10) and (12) into (8) yields
f(xx)) T [Le(1)= 2 (t (e, f)
E x f(xx)) (1(
E [f(x)) - B3 (8(11 -1-0
Pt(1)
B2 (1)+(1) - -1((1)
(14)
Notice that It E C1(1) n f), Thus, for any x Ca(1) f), by the defini- tion of Cc)1,, we have
||x - x1112 I d,. Further, denote (xf, x+") =
arg Alen) ||x - x/112- Then, we have || - x I 6c. Combining this with the XC-Lipschitz property of f. we obtain [x](x;; - (xx))]l2 s Kl|x -x -xt'laa s Ko,, Moreover,
since 2, E Sc(E, f). it follows that for all x E A(xi). [f(x))
f(x)")le S E. Similarly, as
ae E f) and both af and x belong to A(xx), we know [.(x)) - [xx)) S..
Therefore,
f(x:) TF " Elaa ( = E E,, (() [(()))
E Ba En A(m))) [(xx)] T {f(x;) - f(x,) + f f(xi)
2 B E n ( Bx EA(O [(())) (f(x)) f(x)))
-
B² - E E (,,E En E((M.)
[(xr) [( (xx: - s(x()) + [xx [(x)) + [xx] (2x)) }
1| SK0,
11
B (B2e B2K8, B22)
Bt (Kō, + 2z).
(15)
where the fourth line is derived from ||f1|2 2 B1. Plugging (15) into the inequality (14) yields
Re(e,f) f(x.))
Re(e, f)
f(x)) (1) Z 0
E x
E [s(x)) - B3 0o +
(1)
(1)
B2 [i((1) (x()))12
B Of-BBy -28 + +2)) -B3 BB ox + Re(s,
(1)
p((1)
B2 (T))) (x(1))l2
BB(
(1+ (1
(o.- )
B1
2)
-ule, -aa- Re(e,
Kōx + 28 - }}
B3
(((1)
(1(
B2 B₂
BB2line (pal(rr(1) (1)))
B3 ( a. (a.- Ri(e, f)
(1) ) (1 +
B 2
Kd.
25 - 1 -1)1
B3
B2
B
= B (at, E), - B2 (ir()) - -14 (1)l2
Similar process can also turn out
f(xx) (((1 >
(16)
23

---

Combining with (1))22 || Bn }112 S E B. e0) B Flaite)) -
B2 yields
f(x))) (k))))
- f(x)) (( (1(1) + f(x)) (p+())) - (1((t)))(((t)
1 f(x))) (k() + [| - (2)21
I f(x)) p4(k)) + (())l]
= (f(x,) - mx(1)} (a(k) + [x(1) (e))))))(()))))))))))))))))))))) + B2ll - (1)12112
= (1f((z)- m,((1)l2 (k) 1l2 + (c (4(k) + (k) (r(1))12
< B2y [1s( 11 (20))) (=(1) + (1) (1)1 + (c( (x(k)) + -
I BBy 2B3 - -2f(x,) (1( - (1) 14 (A)) + B2 [c)) - pe(k)l12
S BBy B2y 2B3 2BB3
(1) 44 (k) + (x)) (1)12
v2B3 [i E, + (o() (1) + Be - -c
where the inequality in eighth row stems from (16). Moreover, we can conclude
((x))Ti((1))) (c(1) f(x:)] (e)
2
1
(1) [11((+)1++)
= =s(x)) [(x.))Ta(1))
(a(11) - f(xx)) (k((k) 2
(1)+(1)1 (k))(
2 f(x)) [e(()) - f(xx)) (be(k)
1
B3 + +2
min 11 [| (1:)11 KE(K)
2
BoT, - B2 (1) (c(1))l2 v2B3 /1 (o -)((() (o(k)
- (k) - [e(k)]12 B3 (1 minke(K]
>00
B2
where the last inequality is derived from the given condition in Lemma 1, which finishes the proof.
E3 The effect of minimaxing Adv-SSL
In this section, we explore the effect of minimaxing the risk of Adv-SSL, as demonstrated in Lemma 5. We begin by showing that the required condition in Lemma I can indeed be satisfied by method. To achieve this, we first introduce Lemma 2. Lemma as preparatory steps. We will begin with reviewing and introducing some necessary notations at first.
Review that (k)) P. (x. E (k)) and (.))) = P [x, C.())). Correspondingly, (k(k) = (xr E (k)) and (.)))())) = Pe(( |x0 E C+))).. We use the quantities
(A), <2 KE(K)
max
max (p) (k)),,
(17)
kE(K]
measure the divergence between the source and the target domains. In addition, Following the notations in the target domain, we denote the center of the k-th latent class in the representation (f 1 (x, E C.(+))]
space ps (k) ;= EC, (K) Ex, (xxx)) p.(k) 1 Ex wP, Ex,EA(m.) [Zx
In this context, the Lemma can be presented as follow:
Lemma 2. If the encoder K-Lipschitz continuous, then for any k E [K]
[l - [(()))) s MKe.
Proof. For all k E [K].
d'
(p.(k) - (m(())1
Σ [ -mm(s))))
24

---

- (f ]
E
Σ
Ez [=,,co.01((((A((a))) - (=
S d' M
The final inequality is obtained from é1 = max (Kk,,k), ((())) and the definition of Wasser- stein distance, along with the fact that f(A,()) is MK-LLipscitz continuous. In fact, since I E Lip(K), it follows that for every i E [dM] Js E Lip(K). Combining this with the prop- erty that (,(+) E Lip(M) stated in Assumption 3, we conclude that f(A((.) is MKC-Lipschiz continuous. So that
[|x,(k)) - ( ( MKG.
Next present Lemma 3. Lemma 3. Given a (a,, ot, 8z, 5,) aaggmentatio, if the encoder I with |1/l|2 S B2 is K-Lipschitz continuous, then
[(xx)) - -m AB3 (1 -o+
K8. 2
R)(e,f))²
(k( )² + (1 (1- o. Ro f) ))}
2. (M)
2Ba
(k(k)
where f) = frr, , E Ex :spp sup..... (. [lf( -
10000-((3 f(x,,(
> e].
Proof. Let S,(,f) == {x+ E N, sup x. (xx,,,)) f f fxx, 2)11 S for each k E [K],
Eg, Bx, ((x,) - (1) 1: (k( E. Bx,, 1120, E (c(()))]]((z). - Ns
(x))1]]
1
Ee Er Ex.EAO ((t (k)
(k(k)
Ba E., [G (.
+ (k(k)
110. (x.(((()nn..))))(((((()))))))))) (a) [ (k(
(kk Be,NP,Ex,EEn
[1,0 n (((,))))s(s,, me [1] + +4B3 - 1 R.(e,f)
(k( Ha..P. F. ELLE)
(
(k)
P. (C..
[l((z)) (b(()) +4B3 (BB3) 0, + R)(E,f)
E # (.
E
(k(
ps
1 R,(e,f)
E EG (k)ns, Be.
4B3 -1-
(18)
po(k)
where the second inequality is due to
P. -CC $ (1-oz))ue (k) + R.
Furthermore,
E Bu. 26
(19)
= (e Br. f(xx) - Exee
P.(CC())nssseee)) Eū, (Kynss Ee (eens (f(x)) (f({)
= =E ",, Ex A( f(x,)
(k))
25

---

P. PKC
(k)
Be Br. ( -f(x)))Baee -Ba, -eseecaennsicceeeessaee
(k(
P. (sse) (F(x)) - -B Pew.acaeeeeeensssss.o/oaaaaa//aa
(k)
E
E
2 (.C [[])))))
E
2B2 +2B (
+
o, + Re f) )}
2. I.
ps (k)
(20)
For any as x'y (.(k)) S,(s, by the definition of (k)), we can yield
min x,
||x - - S 8z:
Thus, let (x), x arg min ste ||x; - we have || - S 8,. Further- more, by the KC-Lipschizz continuity of J. we yield [1](x;) [(x"")]l S K x S Kå,- In addition, since Fs E S,(e, we know for any x,
f(x))ll e. Sim-
ilarly, x', E S,(s, f) implies [xx)x - f(x())ll I = for any x E A(x²). Therefore, for any vts, x', (,, and E A(=,), x E A(x'),
[] - fxx))l2 $ fxx))) - fxx:)]l + [[f(x)) - f(xx))l2 + +115(2() -x(x)112
- 2: + Kd.,
(21)
Combining inequalities (18), (19) and (21) concludes
Em,ec, EC, (x) (xx,) - (k))
s 25 + K8. + -BB [ 1 + Rx(E,))
(k) )} + 4B3 1-00 Ra(E, f)
12
Ps (k)
4B² (1-0x
Kd
+ + Ro(e,
+ (1 (1-0a+
Ro(E,
}]
2B₂
B2
Pa(k)
ps (k)
Subsequently, we state Lemma to establish the connection between Adv-SSL and the requirements shown in Lemma 1. Following lemma reveals the upstream task indeed render the representation space well-structured.
Lemma 4. Given a G,, dt) augmenttatin, if K and the encoder f with Bi S llf S B2 is K-LLppshittz continuous, then for any ε > 0,
m
(2, <
22 (fligalf),
RE f) E m² E²
8m4
4m
Calign (f) +
B2d MKe, +
BBd Ke2,
e²
and
max (Me(i) (M(()))((()) S $V minn P. (i) (X]
2
+ (R(f)
R(())
+(o + +2Vd=B.MKa.
where ((0,, := 433 (1-o, +
(1 (1-a,) - 20,
Ko.+2e
2B
B2
(E K
p.ttTt p )}
+ B2( + 4B3 R. (e, f))
Proof. Since the measure on A is uniform, we have
Ex, 1 x DE ( ((m))) - f(xx,))12 m
[[((A())) - ((A)(x:)))
26

---

hence,
[| - f(xx,2) = sup
[f(A;(zr)) - ((A,(a)))]l
sup (((())))
1.je/m]
[f((())))) ((,aaa))))((A(())))) ((A)(z))) ||
1,j=1
= m "x 2e (tx.))
Denote := {
(xx,))
f(xx2))12 > mz J. by the definition of Re(E, f) along
with Markov inequality, we have
RR Mx [(x,,1) -
r(suz)ll2)
Re ()e,s)sPtt (S) v
(22)
m²
E E np. DE (x,,1) (xx,2)
m
m
8² E Ex,
Aeees (xx,2))1
(23)
Apart from that, similar process yields the first inequity to be justified in Lemma 4:
RE < m Ex,
uR Ex Re - fxxx2)) E² Calign (f).
m
Furthermore, we can turn out
Eg ( (l [(x - f (x
[[xx,1) (zx,2) 112 ae E((e))
E
(z),)) (xx,2))1
2. ((((..)
E m
[f((x,,) ff (x,,2))
2E
Ex -=._vell/((A(aa))))((444 1en (I(((())))) - - (AA)
m
+ E
.p se /I - 1xxx2)) (xx,1)
m
E BapP pp, ((((((())) f(( (AA((()))) ER, ( - )
m
+ Ee, .P, Ex, flf(z)))) fxx
we subsequently focus on dealing with the first term. Since for all E [mm], B E [m] and 7 e [d"],
Em, ~P, { (A((aa)))) - -((A(())))) ER,,, -r, ((((((())) 2
K
(a(k)Beaeccci - -A(A(()))) EK -(a))))-((AAA (i(A)(x))))
Σ
(e(K)(BBEcc.oot((((()))) ((C)))))((((((())))((()(())))))) E. (0) (.((A((z))) (x))
s(x.)
(pekk) Po Ec, Ec.
- (M(,(())))
$ 8B2MKG + Kc2
To obtain the last inequality, suffices to show g(x.)) E Tip(8B2MKK.. In fact, we know [d"), ft Lip(K) as Lip(K), along with the fact that A((-) and A,(:) are both M M-Lipschitz
27

---

continuous according to Assumption 3, we can conclude fi(A.()) - f((A(()) E Lip(2MM..
Additionally, note that (ft().()) - (i) 2B2 |[fll2 S 12, we can turn out outermost quadratic function remains locally 4B2-Lipschit continuity in [-2B2. 2B2). which implies that g E Mi), Furthermore, by the definition Wasserstein distance, we yield
(e(
-f ((A)())))) -E
-
K 8B,MKK,
MK2
Σ
k=1
As for the second term in the last inequality, note that fi(A((x.)) - f((A)(z.)) 2BB₂ to yield
k
Σ -P)k)
((AA(()))) s 4B2
Therefore,
ExcP Er, Ee,
f(xx,)) - f(x12) S Eu,ne, Ee Ex.
f(zo2)
+ 8B2d" MKa + 4B3d Kc2.
(24)
Combining (22) and(24) turns out the second inequality of Lemma 4.
Re, S m²
Sm
4m B2d Kc2.
(flign(f)+
B2d MKG +
E²
E²
To justify the third part of this Lemma, first recall Lemma 2 that vk E [K], [(a(k)) mx(hll12 S v MKet Hence, for any + j. we have
|mr(1) poli) - (i) vo( |m:0) (e( - (i() ()) + mi(1) p.( - (1) (i)xi + 12.00)2lllpe0)) - S 2vd B2MKe1,
mo(i)
$ (1) - so that we can further yield the relationship of class center divergence between the source domain and the target domain as follows:
#fj max Me (1) p+(i) < max [ma(i) [x( + B2MKr. (デ)
(25)
We next derive the upper bound of max (1) (z(l (V), ..... (K) (.))))))))))...)))))))))))((())) E =dd" x then
To this end, let U
K
Σ (A))))) 1a 1
DUUT - -a- 1 2
TrUUUTUUT - +a)) (|A1/= = TA(A A))
TT(UTUUT - U +T(TT(k))) + KK (Tr(AB) Tr(BA))
1 -ikl
(d' > K)
K
Σ (VP.().(() mall) 5k))
2 p. (M, mG)))²
Therefore,
EK Po (k))sss (k)) - 18-
Ps (i)
28

---

((xxx))
La- Σ (H)))))
E
(xxx)))
By 25
k=1
Bs 2
(1(())(()
E
E
((xx2))(xxx2)
La-
2 E (())))
-
B
(xxx2))
2.
pa(1)pa(1)
(26)
For the term
-x=1 (a)K)
K
- ((x.)))))
note that
K
K Σ (+))))))
R=1
Ps ( (b)) En, (at.
(x,,1)) ]
K
Σ Po EC, (1)
| ( (((o::))--((((((s/s)>--)-->--
(27)
ER, I [(x -
(28)
where the last equation is derived from
EC, BM) Ex, (.(m)) (x..)) -V(()) (K))
Ec, Ex,,, EAee, ((x..)))) (k))))
- -.
EC,,, R, E(x.)) - (J)) - (<sx,.)))(<(k)))))
So its norm is
K
Σ
p (k)))s((()))
K
Σ Pe (k) E Ec.t - Ho()))
k=1
+ En,, up, BR.I
((x, -
K
(k))
E
E
{11((xn.) (1((xx.1)-m((()11)))
{11s(s..))lllll(<x.. s(3s1))l2)
E(())))
ws 2 E(A()))
K
(Il(x,.)))) -
Pe
k=1
Ee Ex EAtt (e - f(xx,1)
K
Ps Br Bn (1
[xx,))) -aah)))-(((kk (1))
B2 (2 Ex (ll - ((xx,)) (xx (.E..)))l)
Review Ss(e,f) = fa., E
sup
[| (xxx,2)122 s
K
Ps Em [1f(xx,1) - (1))
k=1
29

---

B2 (2 B4BBEm,,s [1 & s)(e
k
Σ
(k(k) (4,)) Bx..
[11(())1)) - -aa(
+ BB +4B3 (44BBBR,e,T1)
k=1
4
Σ
Pa (1t -1
+ E
+ Ro(e,)))
+ +(1 (1-10, 02 Ra(E,f) } + B2fE² (E,
2B2
B3
(kk))
(k(
k=1
(Lemma 3)
Kdd + 28
+ (1 - o.) + f) (3- 20, + Kō0 + 28
2B2
B3
K
Pa(ki )
B2 8² + Ro }
+ Re f)
k=1
If we define (l E,, == AB3 (1 +
Kd,+20
+ (1-o,) (c, f) 20, -
2B² -B2
Kd +2 + (E f) EiE pu( ) } B2 (s² ++++4135 (4B3R((Eff) above derivation implies
K Σ
-B Ben (/s. |/ 3/p S splo, f), (29)
1=
Besides that, Note that
R = Be, ~r, Rx,, xs 2, (EA())) (f(xx))((xx2)) - Ia F²
(30)
Combining (26), (27), (29) and (30) yields for any j
(1,(1) (,()))) p.(1).(i))
((() + &ne,1)
which implies that
(e( Ho) $ min44; Ps (i)p
2
R(ff) + + +lam....e..))
max (f
So we can get what we desired according to (25)
max
( s igj
2 min (.)
R() + plo., + 2Vd B2MKe1
Next we present the population theorem as follows, which is direct corollary of Lemma because of the facts that R(f) S L(f) and Latigu (f) S L(f).
Lemma 5. Given a (a.,, as, 8z, auggentttinn,, if > K, Assumption 3 holds and the encoder f with B < |lf < B2 K-Lipschitz continuous, then for any >
max iAj
(i) mn(i) & VC(F) p(o,, + Kgg
Se, f), then the misclassification rate of Q2 Furthermore, if maxi4i (i) (e( < (or (e,
Err(Qr) $ (1 - (z) + + [Calign (f) + Kei /22
where the specific formulations of (p(a,, 8z, E, f) and (a 8e, E, f) can be found Lemma 4 and Lemma 1. respectively.
We apply Lemma 5 to the optimizer at sample level fn, to yield following corollary 1.
30

---

Corollary 1. Given a (02, or - augmentation, for any ε > 0, we have
EB { max (i) T pc( X v EB., (((fn.)) + EE { So,E, fn,,, + Kee. (31)
195
where EB, ( Ss, e, (e, {n,))} 2 (1 ox Kā, + 28)² 2 V BB. {f(sm.)] 20,
K6, + 22) + D. {((fm.)) + (1 σ.) (e² _/4 SVDD {((f).))) } maxi7j (mi(i) T pe(i)] < (B (t, E, then
Furthermore, if
B. [ f.. ) 2 (1 - oz) + = 1R ( + Kei +
(32)
In addition, the following inequalities always hold
1 : EB, (c((.)) ER 1 (E, 2
(33)
D. (Role, 1n S 1 BB, [[(Snn)) + Ke1 + 62.
(34)
Proof. Applying Lemma 4 to fn. yields
m²
Re S
x2 f(fnn)
(35)
Re Sn.) s m² f(fn.)
8m1
4m
+ B2d MKG +
BBd Kc2
(36)
e²
E²
E²
and
2
(f ((on) + 2V d2MMKt
max pe(() me(i)) (e)i)) S (f)
min (i)
(37)
Take the expectation with respect to D. on both sides of (35), (36), and (37), using Jensen's inequality
to obtain (31), (33) and (34). where BB {p(o,, dn, e, f..)) = 4B3 [ 02 +
+ +11-
2B
a.) o.)+ K (e, fn,) (3- 20, + K + +EB, (n. 2k=1 putR)) ) + B2 D.
16-0
B2
4B3 R., fn.)) In this regard, further by Jensen inequality, we know that
ED, (o d,r e, Ro(e, fn.))) s 4B3 (1 oo +
K8, + +2E 2
+ (1 + +KED, (R,(s,
2B₂
33 20, +
Ko₂ 28
+ EE, (R((,, )}
(}(2)
( (a(k)
K
)1
+ +B2 (2(22 + +4BBE B. { {
(e, fmo 4
B2
< 4B3 (1 0s +
Kd, + k5,+ 28)2
2
Km²
v EB, (((rn))))
33-20, 20, + K5.+ + 22
+
2B
E
B2
m² + केt ED. (C(fm.))
Σ
K
+ )
1
(=² + 4B3m² σ.) + B2
VED (((m)))))))
(k))
e
(38)
which is same as what we desired.
Bi Se, e, fo.), then Err(Q,, f., ) S (1- + (e, fn.). Combining with what we have had yield 32, which completes the proof.
Moreover, since Lemma reveals that if maxiys ( (n(i)) <
Above corollary reveals the necessity of exploring the sample complexity of EB, {((fm.) } for proving Theorem 1. To this end, we need to introduce some basic concepts of learning theory in advance.
31

---

F.4 The sample complexity of BB, {(((m))
Recall that for given W, Ne x, x 2 is uniformly and independently sampled from A(xx).
we denote &2 = (I,,1, xx,2) E R²* Moreover, we denote {(2.. G) == (x,,, - fxxx,2)
((f(x,))f(xx)) La,, G) In this context, our risk at the sample level can be rewritten
1 Ra (11((2(1) (xx2)11++ XF(())(())) La G) The
1
1 ns
R2 (xX G).
G(f.G)=
G)
Furthermore, let 9i {G E Rd ||Gl| & Vd It is obvious that 9( is subset of 9i for given f such that |1/1|2 S Bz. Likewise, G(J is subset as well for given N d.d- (W, L,K,, B1, B2). On the other hand, following Proposition reveals that f(æz, G) is Lipschitz function defined on x E 1220" :||z||, - /2BB) x 91 S R22d" +(d)) Consider these two facts together, we can regard l as Lipschitz function in subsequent context. More specifically, summary the Lipschitz constants of E(ar, G) with respect
{æ I222" ||æ/||2 S /2B2) and G E 91 in Table 9, the corresponding calculating process is deferred to Proposition 2 for clarity of structure.
Function
Lipschitz constant
((x,-) G()
V2B₂ (B2 + V max 2B2 + vdc)
((-)
Table 9: Lipschitz constant of E with respect to each component
Following Definition and Lemma 6, 7 are all typical elements of learning theory, which will be involved by our further derivation.
Definition 4 (Rademacher complexity). Given a set S C R", the Rademacher complexity of S is defined as
(S) = E
sup ( JES T
Σ 3
where [E:)ie(n) a sequence of i.i.d Radmacher random variables which take the values and with equal probability 1/2.
Moreover, if we use l to denote the Hilbert space of square summable sequences of real numbers, we have following vectorcomttaction principle.
Lemma (Vector-contraction principle). Let be any set, (æ1,..., xn) E Xn, F be a class of functions f X + l2 and let ha l2 + lR. have Lipschitz norm L. Then
E sup
Eehh((((.))) 222LE SEF
sup FEF
Σ Eent((r))
where eij is an independent doubly indexed Rademacher sequence and f5 is the j-th component of [xx)..
Proof. Combining [29] and Theorem 3.2.1 of [17] obtains the desired result.
Definition 5 (Covering number). Given n E N g-net of S with respect to norm ||-|| on R", if N C S and for any S, there exists N such defined as
R and e > 0, the W referred to as an
that || - e| < g. Furthermore, the covering number
N(S, ||, e) == min { Q is an g-cover of S}
where Q represents the cardinality of the set Q.
32

---

In this context, denote B2 as the unit ball in R". According to the Corollary 4.2.13 of [34], [B2,,, Il-ll2 0)1, which represents the the covering number Bg regarding 2-norm, can be bounded by (3/e) Based on this fact, if we denote Ne. (0) is a cover 91 with radius 2. whose cardinality
(d')²
[N (0) is identical with the covering number of 91, then NN (e) S (B]+va))))
Lemma 7 (Finite maximum inequality). For any N 2 1, X,, i N, dau-Gausiian random variables admitting constants og, then
E max [E|N]
Xxl} S 2 log 2N max iSN
The proof of this lemma can be found in [17]. Lemma 2.3.4.
Recall NN (W, (W, L, (fx) A (Ar,1oo (0.... (Apxz)) k(0) S K). defined in eq 48. The second lemma we will employ is related to the upper bound for the Rademacher complexity of the hypothesis space consisting of norm-constrained neural networks, which was provided by [18].
Lemma (Thcorem 3.2 of [18]. Given n E N and Ig.1...., In E [-B, with B 2 1, define = ((.(())..... f(x,) E aW, L, C R", then
BK v 2(L + + log(d 1))
RR) S 1 2 2ogodd + 1))
Σ i=1
max 155S4+1
Vn
where Fij is the j-th coordinate of the vector (a: 1)T E Rd+1 the definition of norm-constraint networks NN ds,ds dt (W, L,, K.) is given by
NNd, dg W, L,K. == (So(m.) = ALo (AL-AA110( (Aox. kk()) S SK).
herein, review k()) = || A IT
F.41 Risk decomposition
Let G(f) = - 15 Σ
-e (x)
La we can decompose {fF,) into three terms shown as follow and then deal each term successively, To achieve conciseness in subsequent conclusions, recall if X and Y are two quantities, we employ X S Y or Y Z X to indicate the statement that X < CY form some C > 0. In addition, We denote X Y when X x Y S X.
Lemma 9. The Bd, ([(fn,)) has following decomposition
EB. (((m.)) EC(F) + Esta + EE + Eg.
where Est Ep, sus (uPPeEF. [C "(,,))} is referred the statistical error, E == inf {C(f) - [(f)) is called as the approximation error regarding F, while Eg == Ep, supjer (f* ( (()) is named as the error regarding G.
Proof. Notice that L(J) supGeau) L(f, G) holds for both fn, and f*, then for any f E F we have
[(Pn.)= = D(F*) + C(f...)
+ sup GEgthm))
C(fn..G) - sup C(f,G)
GEg(
= =C(M)++ sup ClSn,, G) G)- sup GEÂ(Lm))
[(in,, ) +
ClSn, G)- sup [(nn, GEÔ(fa.)
sup GEG((n))
GES(hT.)
+ sup Gerlfn.)
Z(in, G) sup [(,,)) + sup
[(fr)) sup [(S.G)
GEEl
GEG(1)
Geălf)
33

---

+ sup L(f.G)
sup GEG(S)
+
sup C(f.G) GEGlF)
sup [( GEG(S")
GEÔ(F)
Firstly, both the second and fourth terms can bounded by Esta. Specifically, as for the fourth term, we have
sup L( GEÔ(S)
sup G(S,G) v sup GEÔ(S)
(ZV.G) - s sup GES()
(ZU.G) C(S.G)
GES(S)
sup fEF,GEÚ()
similar bound holds for the second term.
Next, we note that the sum of the first and fifth terms can be bounded by Eg. In particular, for the first term
sup C(fn, G)
Clfm, G) S sup { sup L(f.G) sup [(f,G)}
sup
GEG(fm.)
GEc(fu.)
FEF GEG(S)
CEă()
$ sup { sup ((f.G) (f. ((f,((f)))))))))))()) fer GEG(S)
- -(..()()
sup fer
< <22B2 sup || ( G SEF
< V2B2 sup fer
Ba a.A /aal
(<)))) (39)
(1
Th
where the second inequality follows from G(J) G()), while the third inequality follows from the fact that ((x, :) E Lip())22), which can be found in Table 9. Meanwhile, regarding the fifth term, we can derive
sup C(JG)) sup [(J,G) sup GEE()
BB { (OL1)))
}
sup GEGU)
(J)
GEO(S)
aEε())
S BB { sup GEŌ(J)
(G()).)pp
(f) EB, -
sup GEG(S)
s <B v
BB. -
2B v(+)
sup
Es,
fEF
$ sup SeF
E
(xx))) - -La-
L 10-11,31
$ sup SEF
Ep,
-EO, Ff
n4
{1
(x) Ex Ex f | (40)
S BB.
sup
fEF
where the first equality is derived from (G* (f) =E, ((())))) }. while the second
p
inequality derived from ||Ō()|| - B3 + vd and ||@ s B3 + VVd Combining (39) and (40) yields Eg.
Furthermore, it is easy to conclude the third term suPGeōth.,) L( G) supce Z(f, G) < according the definition of fn,- Taking infimum over all f E NN a,-- (W, L,, K., B1, B2) both sides yields
EB (C(fr.)) SC()) Esta + EF Eg,
which completes the proof.
Next, the remaining task is to handle each term the right-hand side individually.
34

---

F.4.2 Vanishing [(f*)
In this section will show the optimal encoder can indeed vanish L(*)) The justification comprises a total of two steps. At first, we assert that if there exists a measurable map, / such be positive definite, then can conduct a series of minor that Σ E (x=)
modifications on f to obtain f such that L(f) = 0. In the second step, we will demonstrate that the required f indeed exists under Assumption 2, and that the modification of also satisfies the constraint 13 - [f S B2, which implies that [(f*) 0, since the definition of f indicates that ((1) s())) L(f).
To this end, it suffices to find f : B1 1 | S Bg satisfying both Calign (f) and <R,,, Ex mee.(e (fxx.))))) T = First note that
E Pp, R m2 = (fx,,))) Ta-
Er E Pes
+ NR Ezg m.AA) [(xx))
[ f(xx,1)) "] Ia- 1p
Eg, P, ,.
I7-
+ Ee -P, Ix,, (x((xx))ll2 (x,,,) f f(xx22)l1)
~r, Rx Ex
Ta- + B2 Ex..a (xx,1) - (xxx,2) (1lll S B2)
It reveals that, to achieve our destination, we just need to construct f: Bi S || < BN such
that Calign (f) = O, and well as F.te.,
Ia. 0. To this end, we
provide following lemma:
Lemma 10. If there exists a measurable encoder f making E = EEE,,
positive
definite, then there exists a measurable encoder such that
Calign ( 0,
- la 0.
Proof. We conduct following modifications on the given f as follows: for any vs E X. define
(V-1)(x)) (((z.)
if X2 E A(x.) x, & A(x,)
fz. (x.)
where Σ = VVT, which is the Cholesky decomposition of Σ. Here the positivity of Σ ensure V is well-defined. Iteratively repeat this modification for all x, X to yield f. As the result, we have
Ea,~r, Ex..)
V Be,,r, (f(xx)f(x.) ( Is-
and
Vo, E X, x,, x E A(xxs) [(xx,1 - (xx,,2 =
- -(xx)))((x))) =
That is precisely what desire.
Remark 2. Based on the construction approach in Lemma 10, we just need show there exists a encoder f such that E are positive definite. In fact, if we have a measur- able partition X' = P as shown in Assumption 2 such that P; n P, = 0 and P., where e;
I B. just set the f(x.) = e: if x. the standard basis of Rd then Σ = diag(P, (P.)....,PP(PP)) P.P.....PP.....PPPPPP. diag (v P.(A.).....
Vi [d'), By S (P.).
V-1 = P(P. P..)..) ) f(x.) = E.pee x, E Pe. is obvious that
B |[1 < B2.
35

---

F.4.3 Upper bound of Esta
Lemma 11. Regarding the statistical ervor Estas we have
KvL.
Esta S
Proof. To obtain the desired conclusion, is necessary to clarify several definitions in advance. For any f R2 + RR"" define f : 122d - IR2d such that f(x,)) = (f(xs,1, f(x,2))) where 2, (x,,1, E TR.d. Furthermore, let F == (f f NNN., (W, T,, K.). In addition, denote
D' - (x |2 ) which is collection consisting of n, independent samples. The distribution of
these samples is identical to that of Dg; D', is therefore referred to the ghost samples of D,. Moreover, recall 91 {G E Rd"xd", xd' =| B3 + vd*), by the definition of Estas we have:
Esta ED {
[(f.G) E(F. -()
sup A (W..K,
S ED {
((.,)) BUs Gi
sup (.C.ENN
(Vf E NN
9t)
- -Lf.Gi Gi|
$ E. (I.G)ENN. (W.KK))GG
sup
a. (W, Br, CNN L,K)
B2
E by (1 G)} 1 n,
sup F. {
Rs
Thg
i=1
< <ED {
(J(Z G.) Th
sup
(f,0)EFX9
1 i=1
=Ep { sup
(<(((()) G) e((x!)) {
(41)
(f,))eFxG
n i=1
sup < <2BD, (f,G)EFxg,
Σ {(( |
n2y
1=1
1 n d'
I <4v2 1
(ED
3>
م (x.)) + (x.
sup
SENN (W,L,X)
n2
== j=1
R2
+ Eg {
Geg })
sup GEG:
(42)
My
f=
n2 d'
< 2 10llai F
Ees (x + 4v2dd 11e
sup
SENN (W,LKK)
n,
+ +4v2 1121|ellzpp
Eg
max (e)o
(43)
< <8V2 1e E D..s
Guf ( (1)
4V2d" [ell e
sup (W.L,K)
n1
2log (2|Ne
+ +4V2(B2 + vd+) ||e|Lap V
(44)
< SVddd [[ellrip ED.el
(x(() + 4v20" 11l
sup
(W.L2.
17
36

---

2 log (2( (13+va)) )(d))2)
+ +4V2(B2 + v [|ellipp V
(NNG, $ ((B )2
3
((d)))
LVL.
log ns
(Lemma 8 and set 2 = 0(1/ /n,))
B4
n
KVL
(ff こ Vlog n,))
Where (41) stems from the fact that ((((F(x))) G, - e(f(x.)), Gi) has identical distribution with ((f())))) ) G) - {(f(xx)), G). In addition, notice that we have shown | < cc, applying Lemma 6 obtains (42). Regarding 43, since Ng. (e) a g-covering, thus for any fixed G E 91, we
can find a G E Ng. (e) satisfying G E|| S o. therefore we have
n,
d"
d
San G5h - }
Eg
max
GE91
j=1
R2
d Eugee (Gjs - Gjt)
Gnj } EE
< Eg
max
max GE91
GE9:
Ys
< Bg
max
n2 GnghCge
1
V(dt)Pnon
ns
GGyk GG,+
GENe (e) n2
ns
k=1
inequality)
n4 Caa } + d
< Be
max GENG (e)
n
d'
To handle the last term (44), notice that ||G]| S B3 + v implies that
Σ
Σ
Gig ~
1=1
1 n4 Σ Σ Σ Gij subG V. just apply Lemma to =====
d" d'
(B2 + v vd+). Therefore,
complete the proof.
F.4. Upper bound of Ey
we define
E(H NNW. (W,,
inf geRu feNNa.(W.L.K)
sup
|lf - -9llooo1199
where C(JO, 11d) is the space of continuous functions on [0, 1]ad equipped with the sup-norm. Accord- ing to Theorem 3.2 of [25], we have following lemma:
Lemma 12 (Theorem 3.2 [25]). Let N and a = r 3 O, where r No and B E (0, 1]. There exists e such that for any K. 1, any W 2 (2(24a))(22t)) and L, 2 2[og (d + r)] +
E(Ha .N
sx-a/(dt11)
Based on Lemma 12, we yield
de Σ (1(x)));(0))
inf TENNaa(W;LL) (W.LK) [[((x) - S a
inf
d'
inf (ENNa.-(W.L..))
Ilfi ft lo
inf geH FENN (WL.K)
sup
Σ ll 9 g12c(0.11))
37

---

I sup SEN" JENN
inf K,,
Ilf - silexpo.1je S .NNai((W/d)..1) (F
S (K-a/(d+1),
where the third inequality is because following fact: if we have total of d' function fi E ( k,), E [d"] of independent parameters, according to following Proposition 1, ) can be regarded as an elements of N. (W, D, with
the concatenation / (fi, f2. specifie parameters, that is, J' E N d,a- (W, K.).
Proposition 1 ((ii) of Proposition 2.5 in [25]). Let f1 E NN (W1, L,, K1) and fz E NN a,4; (W2, K2), define ((xs)) = (2(xx),f((x.) then f E a. (W W2, max L2), 1a (2)))
Above conelusion implies optimal approximation element of f in NN (W, K.) can be ar- bitrarily close to f under the setting that K. is large enough. Hence we can conclude optimal approximation element of f* is also contained in F NN d. (W, K, B1, B2) under the setting that B1 - |I l12 I B2. Therefore, if we denote
{1ls(x..1) f(x3,2) 1(x),2))1 11:
T() = E H, x..3 & 2EA(E.))
E
E
E 2.,
(fxx)1)(ZZ02)
11- p²
then we have
= inf
sup
C(f.G)
sup GEG(F")
[(f", C(f%,G)]
inf SET
-
feF
((xx)) f(53)11
inf a
(T()) T(f*) S |lellrip JENN (W.L.K)
inf
Ex, -e, Bi,
d'
<
<11lllii JENN a. (W,LKK)
inf
Ex Br, Ex.EA(()
2
Σ
- f(()))
1=1
sup I V2d" [
inf JENN..
|l gllc(1a.11)
gEH²
I 22d p EHH (NNaa(WW//"),,,.
$ (d=1)
where the first inequality is because of Proposition
F.4.5 Upper bound of &g
Let M(x) σ 21, 22 Rd, which is Lipchitz map on fx Rd2d" S v2B²} as presented in Proposition 2. Then
The Σ
{
(
Eg 5 E. sup fEF
M FT, [as Ex, 1x
(f(x)) T1
-
FE!!
Furthermore, according to the multidimensional Chebyshev's inequality, we can turn out +xx) B(
P. Σm= f(x(")) - EP,, s. (f(.)) 2 n
8B
[ V2B2. Therefore,
Eg /
1
P. (1),
f(x!")
En, ~B, Ex SEA (f(x,)
1 + 2V222B
8B3
n1
1/4
n2
n1
1/4
Vng
1
1
+
16
2B3
1/4
Th
n2
1/4
where the first inequity is due to | S V2B2.
38

---

E.4.6 Trade-off' on several errors
Let W 2 cc(24+0)/(244)) and L 2 2[]ogg +r + 2, combining all bounds yields
K
FB [[(((() S Esta + E + Eg S
+ a(da/1)+1)
n
Setting K x n ममाीरा yields EB, [[(nn)) X n,
za Tar
under conditions W
Cn2
2d 4[alddi)
L 2 2|1ogg (d + r) 2
F.4.7
The proof of primary theorem
Based on the previous preparation, we next prove the primary theorem Before that, we summary here all crucial conclusions which have obtained so far.
2d
. If WWW Z
10+4-1)
L 2 2 [oog2 (d +r] + 2 x n
20+d+1)
then Bβ, {f(mm)) 2
f1 3[o+d+1)
d+11
According to Assumption 4, max ,.fm))) S n when n2 - xc.
2(a-d41) 2+1)
2
minfo! ,0 o.fo))) + 1
(n.)
According Assumption 5, 61 2 n4
Natdi1)
62 S ns Nai2i1)
According to Lemma we have
EB, { max (1) (e(D)) & (((m)) + +R (p((! mm) (ime))ennr Ino)) + Kee. i7j
where EB, { (a slmm)) E(())) Ro 2 a (mm)) + ko(lm)) + 2Enn 2 + cn
(ma) ) Ena v E. -0.
-Ko(m)) + +2en.
BB, (f(sm.) )) (1-o!- ) c
D. ([((n.))) 1
Furthermore, if maxiss (1T mr(i) < B3yblo, 8,, 8, f), then
Enr(Q,,.)(0 o1) + V + Kr, +
(45)
In addition, the following inequalities always hold
ED. Re fn.)) S VED. (Cbmn))
(46)
Ep (Re Fn.) 2 - BB, (((fn))) + Ka 62.
min(o B(o+d-1)
2dt
Theorem 1. When Assumptions 1-5 all hold, set Sn, me 211 ā.lāт. and = An, in Assumption 4, then we have
W 2 ns
an++d+1
L 2
[o (d + r)] + 2, nss
E. {Err(Q fn, )) E (1 o(mo)) + ns
minlar Autdel 32
mink (k)
for sufficiently large n2g-
(m.) g( en,, fn.)). which is a event de- fined on the product measure space (X's x Xe, IP) with IP is the joint distribution on X, x Nz.
Proof. Define C = maxizi ( < Bzb((,
D. [Er((Q ((..)n.))))))) (.. = E,,,, (Eir(Q (2, ir )1c} + E...D. (Er((Q f.. )cc=} [(1 of (m))) + Rulen, Sn. + E E.D.D, (1c:)
5 Ep, D,
39

---

< (1 oi (m)))
+ BB {
+ P(C))
< (1 oi (
+ E EEj, [[((f.)) + +2) +P(C*)
< (1 ot (mx)) + + [Ep. [((n) +el + 62
+P(C)
(47)
Since we have known the sample complexity of each terms except for IC()), the remaining question is to estimate P(C To this end, first recall (b(ar")) 8fm0), Em. fn.) = I minn on 66mma, En,, fn.))
(n,) /2 12-2T 2 inin (a." _66m))) ,Cn,, fn.)) (1 mingeing Il. (1ill
2 mas (x
Notice
B3
B2
that (34) and dominated convergence theorem imply RelEma, Sn.)
- 0 a.s., thus
[m (m)) (0," ,0( En. = (n.)
(o(
Ro(Em, fnn)
fmn)
(1+
B
2 -1
min, (i)
B2
B2
B2
B1
2
B2
Combining with the fact that 3-mings e R) Ia (K)1
2 can yield
Imin( (nn)
1 {(1 (1 (mn) olmm), een, So.) 1 (mx) g(a)) En,, In,) V2 2r min (o, (o
min (1))())) kE(K]
1
2
Bj is sufficiently close to B2. On the other hand, by Multidimensional Chebyshev's inequality, we yield
64 E E(.kk) Ex (( flx(z)) - (M)))l)
Pr (lir(k)) (((n(())
mi(k))] 2
B2
128
8 S
B 2mg())
B3 ne (k)
which implies that (h (mn)) slmw)) En,, fn,) 2 1 with probability at least
Ba / min: (k) when
128K
n, is sufficiently large. Therefore, with probability at least 1 0( mine v (n)(
we have C S
{ max (mo(1) (onT+.() Bi
P(C)) = Ps (c c S max (a(1))TTl) m+(i)² 2
1) Pe Cc S max (p+(1) (10mmm00] 2 = -
B
(F)
8
ifj
)) P. c g { mmax (me(t) me(i)] 2 B3 )) '5
B3
+ P. (00l 6 & { max (pa(1) T mx(5)) N g
< P. max (t)) po(5)] 2
B3
c C c=
max (e))) T Hc(i)²
2 8 1)
B?
8
+ Pt C & { max (1)) pe(5)] 2
B²
8 ))
< P. max |en (i) pt(5i) > 8
B3
) /Pa (c C
max if)
(uo(i) [o0])/((] 2 )
+ Pt C & { max (i) p=(ii]] > (
8 ))
P. maxisu (i) T mz( 2 E
+ P. Cco z { max (i)( me(3)) 2 $ 1)
B3
1- 0(/ mink v km((k)))
ii
B3 8
B? ))
S P. max (u))) p+(5) >
+ p c & { max (c( pc(i)l 2
40

---

min(o.2cA) S (1-o (ma)) + 10i++a11)
miny (n((k)
wherein, for the term P. maxizj pe(()) 2 inequality obtains
B
in the last inequality, applying Markov
B
max (e(()) pe(iil 173
Ps max (e(1) moli (F)
BD.
$ BB. { (f(fm.) (m.mm)))-mm + ED ( odmm), En,, fn.)} + Kei,
where the sample complexities of both EB, {f(fr.)} and e on the right-hand side has been thoroughly explored. Therefore, the final step investigate the sample complexity of E. ( (m)) sl E.n, Fn,)). In fact,
BD (o(o!")) 8lm)), ((,)) ((()) R. (e, fn.))) (1- (1-o of 188gm.) +2En.) 2² 1
V BB, (c(fn.))
on
(3-20 (m))) + k8 + 2Em.)) +
EB, {((fm.)) + (1- (1-o!"n)) ofmi)) + (2n + En.
1
V ([,,(
En
1 (1 (ma)) K5)(ma) ) 22n,) + BB, [[((m))]
2
ED, (C(fm.))
En.
Rr
+ (1 - (nx) + Ko(tn)) + 2En.) + (en, + Ena
EB, [[((n.)))))
m 121+
$ - (1-o + T
Substituting this conclusion back to (47) yields our conclusion, that is
( (1 (1-0, (1-o!!u)) + ns
minfa.cc..ca 32(a-451))
1
ming v (k((k)
G
Auxiliary Lemmas
G.1 K-Lipschitz property of NN (W, T., IC, B1, B2)
Proof. To demonstrate that any function & E NW (W, L, K., B1, B2) is K--Lipschitz function, first define two special classes. The first class is given by
NN d,, de (W, L, = {d(xz) (Lo (Aoz)) k()) s x]]
(48)
which is equivalent to AN (W, L, B1, B₂) when ignoring the condition ||0| E [B1. Bz). The second class is defined
SNN (W, == (p(z)) A - II |i <K).
a
a 1
where À N with No = 1
clear that NN da (W, L, B1, B2) S NNa (W, K.K.) and every element in SNN, d, as (W,L,K L, K.) is a K-Lipschitz function due to the 1-Lipschitz property of the ReLU ac- tivation function. Thus, suffices to show that
SNN de (W.L, S AWW, de IW S SNN (W + L,)
to establish our claim.
41

---

To begin, any function o(x) - (Lo(AAL- (Anz +b)) + +bL-1) E WN d, (W, L, (.) can be restructured as ((x)) - AA a (An where
á = 1 A= = (Az, 0), A =
A
0
bi
1
)
1= 1=
Notably, we have =o | = ||Ar|1s I max max [1( bo) 13 = =x(0)= S K, which im- plies that Φ E SNN 41 (W + 1, I.)
Conversely, since any o SNW L. KC) can also be parameterized as ALO (AL-10(.... o (Agx bo)) + b)- with 0 = (Ao. (A1, O),... (AL-1, 0). AL), we can use the absolute homogeneity of the ReLU function to rescale Ar such that | I and | 1 for I * L. Consequently, have x0) = o || S K, which yields ENWWW, L.). This completes the proof. C
G.2 Lipschitz property of Proposition 2. f is a sipschitz,uunction on the domain {o E IR2d" :||ا|| S v2B2} x G1.
Proof. We begin by proving [[((, < do for any fixed G E 91. Let x (2), 222) RR2d"
where 21, 22 E I.d" We first demonstrate that g(x:) = || 22 is Lipschitz function. To this
end, let p(x) == x1 22, then we have:
[l([))- - p(y))1 = || 222 - y + y2112 S || y 2| + | 922l2)²
= |x1 yı 112 + || - y21l + 2|| - 3 1121|02 3/2 3211
S 2 (1|=21 - yn + +|1022 v21l2) = =21 v11.. 912..
which implies that p(æ)) E (ip(v22) Moreover, it is easy to notice that p satisfies [|p())]22 = ||a1 22l12 S ||r1ll2 + || 1l2 S 2||00|1 12 S 2/2 on the other hand, let g(y) = y We have:
04 (p(=)) = 211p(>))12 - 4V2B2. Oy
2
Combining these facts together, we know g(x) {(((z)) |||| x2113 E Lip(8B2). Now, we show that h(x)) = [xaa) Ia-, G) F is also Lipschitz function. Define r(æ) == 01
We have:
[|[(z) r(y)ll= |ج T y U2 T || ||ل| x 1 +. vive ||F
|| (x²2 y2)
+ (a) - yn )92 ||r ||||||||0> y2l1F + |a y1llelluallr
< (1 112 + || 22)l= - - -yll s 2v 22 | vlle.
Additionally, define t(4) == (A- 11-1a-, G. It is obvious that [t(A)]l== = |Gl|e S B2 Va. Based on these, we can conclude h(xx)) = ((((x)) E Lip(2v2B, B3 + VTF).. By combining above results, we yield for any G E G1, [d(-, G < co on the domain {x : |||||| S v2B2).
Furthermore, for fixed x E 2dd such that ||0||2 S V2Bg, we have
16(x, ((),,G) - (12, G2) = (x,, G. - G2) s || |2||Gr - G2ll = V2B2l|Gr -Gales which implies that ((z, )) E Lip(V/B.). Finally, we can conclude
(((1,,G) l(02, 2² - {|((01, G1) (( G1) ((22)
[[(22 G1) ) l(02, ((22) G2)
vdt)} } [ - - + v2B2 G1 -2 1
<
x 12 2V2 +
+ / }
2 || =2 + 4B3 G1 - G2ll
s velleec G1) - vec(222 G2)
where C is constant such that C 2 max {2(v2 2 2B2BBB + " ,AB3} and vea(.)
represents vectorized operator.
42

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
43

---

Justification:
The limitations of this work are discussed in Appendix 5.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specifiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The assumptions of our theorems completely and clearly stated. Complete and correct proofs for theoretical results are provided the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The numerical results are reproducible following the description and the pseudo-code in the manuscript.
Guidelines:
44

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: Our code is released at the supplementary material for reproducing the nu- merical experiments in the paper. The datasets used in the numerical experiments are commonly-used and openly accessible..
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.cd
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/
/etggiddeeeeeedmmiiii httpublccguuuieeeeeeeee gew.idee///eeeeeee/oooeeoesss /CodeSubmi asi aassonPolll onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
45

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The setup of the numerical experiments are clearly specified
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: We do not provide error bars, but instead run the same experiment with three different seeds and report the one with best performance.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Computing resource specified in the Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
46

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
ines?
Answer:
[Yes]
Justification:
The research conducted conforms with the code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: As the paper only focuses on the foundational methods and theoretical under- standing of method, there is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
47

---

Justification: The paper focuses on the foundational methods and theoretical understanding of the self-supervised learning, and poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All creators and original owners of assets used in this paper are properly credited. The licenses and terms of use explicitly mentioned and respected according to their respective guidelines
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's 's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
Our code along with documentation are released at the supplementary material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/modell as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
48

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our L.LM policy (https : http//eeerippepe/ www.oooeeeennce//2222222222 for what should or should not be described.
49


Reviews:
[{"review_id": "vFlbGhr9WA", "reviewer": "Reviewer_N15g", "summary": "This paper presents an unbiased adversarial self-supervised representation learning framework (ASSRL) that removes the estimation bias of covariance regularization through a min–max formulation. It provides end-to-end risk bounds for transfer and few-shot settings and achieves consistent improvements on several benchmarks.", "questions": "See weakness.", "limitations": "See weakness.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper offers the first end-to-end risk bound for non-contrastive self-supervised learning under limited data and distribution shift, filling a gap in the literature. \n\n2. By leveraging adversarial training, the method corrects the bias inherent in mini-batch estimation, avoiding the cumulative drift observed in Barlow Twins and WMSE.\n\nWeaknesses:\n1. The maximization step is realized by directly setting G equal to the empirical estimate, rather than through a dynamic min–max game. The main paper does not clarify this equivalence, which may lead readers to overinterpret the “adversarial” aspect. In practice, the procedure is not truly adversarial.\n\n2. The empirical improvements, while consistent, are modest. Table 2 should include additional recent decorrelation-based non-contrastive methods, notably VICReg [a] and LogDet [b]. The reported accuracies slightly exceed VICReg but are below LogDet. Moreover, more recent contrastive and non-contrastive baselines should be included.\n [a] VICReg: Variance-Invariance-Covariance Regularization for Self-Supervised Learning, ICLR 2022.\n [b] Geometric View of Soft Decorrelation in Self-Supervised Learning, KDD 2024.\n\n3. Empirical analyses are insufficient.\n1）The claim that “ASSRL-learned representations cluster downstream data by class” should be supported by visualizations or quantitative metrics.\n2）Assumptions 4 and 5 depend on parameters such as  $\\sigma_{s}^{(n)},\\sigma_{t}^{(n)},\\delta_{s}^{(n)},\\delta_{t}^{(n)}$ for augmentations and $\\epsilon_{\\mathrm{ds}}$ for domain shift. These should be measured in experiments and toy examples to validate the assumptions.\n\n4. The theoretical setting does not fully align with the experiments. The required network width and depth, sample sizes, augmentation constraints, and downstream domain settings are stricter than those used in practice. Assumptions 4 and 5 are particularly stringent and difficult to verify. Additionally, a lower bound on the error is absent. These limitations hinder the theory’s direct applicability to implementation and engineering.", "was_revised": true, "final_justification": "Taking everything into consideration, I tend to increase the score. I appreciate the author's efforts and exploration in addressing this valuable research question. However, it should be acknowledged that the current conclusions and phenomena have very limited impact on real applications. I am excited to see more progresses regarding this issue in the future.", "rebuttal": "We thank you for your thorough review of our manuscript and for your constructive suggestions. We have revised our manuscript by incorporating all of your suggestions. The revised version is much strengthened. Our point-by-point responses to your comments are given below.\n\n> **Comment** The maximization step is realized by directly setting G equal to the empirical estimate, rather than through a dynamic min–max game. The main paper does not clarify this equivalence, which may lead readers to overinterpret the “adversarial” aspect. In practice, the procedure is not truly adversarial.\n\n**Response** Thank you for your feedback. Our algorithm is still within a min-max framework (thus called \"adversarial\"), while the maximization step can be solved explicitly. Hence we directly set $G$ equal to the empirical estimate, which is the analytical solution to the inner maximization step.\n\n> **Comment** The empirical improvements, while consistent, are modest. Table 2 should include additional recent decorrelation-based non-contrastive methods, notably VICReg [a] and LogDet [b]. The reported accuracies slightly exceed VICReg but are below LogDet. Moreover, more recent contrastive and non-contrastive baselines should be included.  [a] VICReg: Variance-Invariance-Covariance Regularization for Self-Supervised Learning, ICLR 2022.  [b] Geometric View of Soft Decorrelation in Self-Supervised Learning, KDD 2024.\n\n**Response** Thank you for your valuable feedback. We highly value your professional suggestions. We notice that the paper you mentioned didn't provide their implementations. Therefore, we try to implement the methods your mentioned ([a], [b]) with the same setting as ours and successfully get The preliminary results shown as follows:\n\n| Method | CIFAR-10 | CIFAR-10 | CIFAR-100 | CIFAR-100 |  Tiny ImageNet | Tiny ImageNet |\n| ---- | ----- | ----- | ----- | ----- | ---- | ----- |\n|  | Linear | $k$-nn | Linear | $k$-nn | Linear | $k$-nn |\n| VICReg | 91.23 | 89.15 | 67.61 | 57.04 | 48.55 | 35.62 |\n| LogDet | 92.47 | 90.19 | 67.32 | 57.56 | 49.13 | 35.78 |\n| ASSRL | **93.01** | **90.97** | **68.94** |  **58.50** | **50.21** | **37.40** |\n\nAdditionally, we have achieved improvements of 6\\% to 12\\% compared to the biased methods. \n\n> **Comment** The claim that “ASSRL-learned representations cluster downstream data by class” should be supported by visualizations or quantitative metrics\n\n**Response** To provide empirical evidence for our claim, we follow the definition of divergence term from [c], which is expressed as the average of $\\Big(\\frac{1}{\\vert C_t(i)\\vert}\\sum_{x_t \\in C_t(i)}f(x_t)\\Big)^{\\top}\\Big(\\frac{1}{\\vert C_t(j)\\vert}\\sum_{x_t \\in C_t(j)}f(x_t)\\Big)$ among all $i \\neq j$. This quantity measures the divergence between representations of data in different latent classes. Further, lower divergence term implies more divergence. We compute the divergence term of the representations learned by our method in CIFAR-10, resulting in a value of 0.231, which reveals that our representations cluster downstream data by class. Moreover, this quantity is smaller than the corresponding values of the other methods reported in [c].\n\n[c] Towards the Generalization of Contrastive Self-Supervised Learning, ICLR 2023.\n\n> **Comment** Assumptions 4 and 5 depend on parameters such as $\\sigma_s^{(n)}, \\sigma_t^{(n)}, \\sigma_s^{(n)}, \\sigma_t^{(n)}$ for augmentations and $\\epsilon_{\\mathrm{ds}}$ for domain shift. These should be measured in experiments and toy examples to validate the assumptions. Assumptions 4 and 5 are particularly stringent and difficult to verify.\n\n**Response** Thank you for your comments. We have illustrated Assumption 4 in Appendix F.2 of our initial manuscript with a toy example. Additionally, the corresponding explanation for Assumption 5 can be found in Appendix F.3. However, in practical applications, these assumptions are challenging to verify since we cannot access the image distribution. Thank you for your understanding.\n\n> **Comment** The required network width and depth, sample sizes, augmentation constraints, and downstream domain settings are stricter than those used in practice. Assumptions 4 and 5 are particularly stringent and difficult to verify.\n\n**Response** Thank you for your comments. As you mentioned, our assumptions may indeed be stricter than those typically used in practice. However, we want to emphasize that the width and depth represent only a sufficient but not necessary condition. Meanwhile, the sample sizes serve merely as a theoretical guarantee to illustrate the effectiveness of our proposed method. Additionally, the augmentation constraints provide insight into the types of augmentations we require. Overall, from a theoretical perspective, it is common to explore theoretical understanding in an ideal scenario. Thank you for your understanding.\n\n> **Comment** Additionally, a lower bound on the error is absent.\n\n**Response** Thank you for your feedback. The mini-max lower bound of self-supervised contrastive learning remains an open problem. It is undoubtedly a valuable and promising area for future research. \n\nThank you once again for your careful reading, professional suggestions, and inspiring recognitions. If you have any questions, please feel free to contact us."}, {"review_id": "XuN4KfEmFj", "reviewer": "Reviewer_2wB8", "summary": "The paper studies the regimen where unlabeled data is used to learn a representation that aligns an image with its augmentations with the hope of learning semantic information useful for a downstream supervised task. Of several methods towards this end surveyed in the introduction, they use a regularization approach where the covariance over augmentations is aligned towards the identity matrix (1) and thus encouraging separability. The authors introduce a modification of this regularizer that leads to a minimax learning algorithm they term Adversarial Self-Supervised Representation Learning (ASSRL). This leads way to a natural numerical alternating procedure, Algorithm 1, which they use in experiments to demonstrate their method; These experiments demonstrate the success of their method in comparison to prior work. Finally, Theorem 1 provides a theoretical guarantee for an RERM version of their algorithm for ReLU neural networks for classification.", "questions": "**About Augmentations**\n* Line 150, the authors say that $m$ could be infinite, yet later we consider a uniform density over all augmentations. Could the authors clarify this? \n* In order to approximate some augmentation classes we require a cover that is exponential in dimension. e.g., rotational transformations. Thus, there can be additional dimensional dependence for augmentations commonly used. How does this affect the rate?\n*  It seems to me that a covering based argument over continuous augmentation classes would be more direct. Can the authors comment on the difficulty or feasibility of adapting their argument to this setting? \n\n**Theorem 1**\n* Is there a reason why a finite-sample bound is used for the source task? \n*  Is the  $1/\\mathrm{min}_k \\sqrt{n_t(k)}$ natural here should we expect something that is more balanced as as we get more data for all classes except for one. \n\n\n**On approach** (my biggest concern)\n* For fixed $f$ and $G$ it is clear that  $\\mathcal{R}(f, G)=\\mathbb{E}_{\\widetilde{D}_s}\\{\\widehat{\\mathcal{R}}(f, G)\\}$.   \n\nYet, as I understand, this isn't true for $\\mathbb{E}_{\\widetilde{D}_s}$$ \\sup _{G \\in \\widehat{\\mathcal{G}}(f)} \\widehat{\\mathcal{R}}(f, G)$. \n\nFor example in (4) on line 174, on the left hand side we see taking the maximum over $G$ in $\\hat{\\mathcal{G}}(f)$ which is equal to a term for which there is no max over $G$. As I understand the latter is ASSRL because it's the adversarial minimax and thus it appears to me to be similarly biased in comparison to prior work. And therefore I'm not sure how Section 3.2 provides a justification for the method.\n\nAm I misunderstanding the method? \n\n**Miscellaneous**\n* Are ReLU networks a Holder class? As their partials may not exist everywhere.", "limitations": "Repeating a two points mentioned above,  the function in Theorem 1 doesn't apply to the numerical procedure and the \"mixed bounds\" for Theorem 1 (asymptotic versus finite) .", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n* The problem is well motivated and the algorithmic setting is valuable in practice. \n* The work is extensive in the sense that it has experiments, practical numerical algorithms, a theoretical guarantee, etc. \n* To my knowledge the work is original. Their modification of the regularizer is reminiscent of other methods that could be viewed as searching over all one dimensional projections.\n* It's a generally well thought out paper. The Appendix has several sections that the reader will find useful, as I did. For example see the sections justifying the assumptions made.\n\n**Weaknesses**\n* Theorem 1's guarantee doesn't hold for the result of Algorithm 1. Of course, this is common in the literature as the problem is non-convex.  A note just specifying that Algorithm 1 likely doesn't return the RERM in Theorem 1 may be useful to the reader. \n* I was confused by their augmentations discussion (see below)\n* To my eye, which doesn't include much familiarity with prior work, I do not find the rate in Theorem 1 very interpretable. I'd appreciate more remarks on interpreting the rate of decay for each term in Theorem 1 perhaps, if possible, an example. Concretely there are with the several $\\mathrm{min}$s that make it to tell which setting achieves which argument therein.\n* Theorem 1's rate is a mixture of asymptotic and finite bounds. Asymptotic for the source task and finite for the target task. \n \nGeneral Writing notes: \n* Although perhaps implicit in context I think the reader would be aided in learning that ReLU neural networks for classification is the model used.", "was_revised": true, "final_justification": "My biggest concern was addressed by the authors. The authors making additional remarks along the lines those made to me would be valuable to the reader. The work of unbiased estimator of a representation with end-to-end bounds adds to and clarifies to the literature. To my knowledge the contribution is novel and I raise my score to 4.", "rebuttal": "We thank you for your thorough review of our manuscript and for your constructive suggestions. We have revised our manuscript by incorporating all of your suggestions. The revised version is much strengthened. Our point-by-point responses to your comments are given below.\n\n> **Comment** Theorem 1's guarantee doesn't hold for the result of Algorithm 1. Of course, this is common in the literature as the problem is non-convex. A note just specifying that Algorithm 1 likely doesn't return the RERM in Theorem 1 may be useful to the reader.\n\n**Response** Thank you for your professional comment and understanding. As you mentioned, the algorithm does not return the RERM involved in Theorem 1. We have emphasized this difference in the revised manuscript.\n\n> **Comment** To my eye, which doesn't include much familiarity with prior work, I do not find the rate in Theorem 1 very interpretable. I'd appreciate more remarks on interpreting the rate of decay for each term in Theorem 1 perhaps, if possible, an example.\n\n**Response** Thank you for your invaluable suggestion. We found a typo regarding the term $\\epsilon_{n_s} \\asymp n_s^{-\\frac{\\min\\\\{\\alpha, \\nu, \\varsigma, \\epsilon_\\mathcal{A}\\\\}}{8(\\alpha + d + 1)}}$ in our theorem, it should be $\\epsilon_{n_s} \\asymp n_s^{-\\frac{\\min\\\\{\\alpha, \\epsilon_\\mathrm{ds}, \\epsilon_\\mathcal{A}\\\\}}{8(\\alpha + d + 1)}}$. we have revised our manuscript according to your advice. The rate respected to $n_s$ is $-\\frac{\\min\\\\{\\alpha, \\epsilon_\\mathcal{A}, \\epsilon_\\mathrm{ds}\\\\}}{32(\\alpha + d + 1)}$. We will interpret it term by term. \n\n* First, as the dimensionality of the data \\( d \\) increases, the convergence rate of ASSRL with respect to the sample size $n_s$ slows down.\n* The term $\\epsilon_{\\mathcal{A}}$ represents the quality of the data augmentation used. As $\\epsilon_{\\mathcal{A}}$ increases, it indicates a higher quality of data augmentation, which in turn leads to a faster convergence rate of the upper bound on the misclassification rate with respect to $n_s$.\n* The term $\\epsilon_{\\mathrm{ds}}$ indicates the extent of the shift between the source domain and the target domain. As it increases, the degree of shifting decreases, meaning that the difference between the source and target domains becomes smaller. This makes the transfer learning task significantly easier. Consequently, the convergence rate with respect to $n_s$ will increase as $\\epsilon_{\\mathrm{ds}}$ rises.\n* As for the term $\\alpha$, Consider the case that both $\\epsilon_{\\mathcal{A}}$ and $\\epsilon_{\\mathrm{ds}}$ are larger than $\\alpha$, In this scenario, the convergence rate takes on a typical form found in nonparametric statistics: $-\\frac{\\alpha}{32(\\alpha + d + 1)}$.\n\n> **Comment** Concretely there are with the several $\\min$s that make it to tell which setting achieves which argument therein.\n\n**Response** Thanks for your constructive suggestions. Let's consider a special case that $\\epsilon_{\\mathrm{ds}} > \\alpha$ and $\\epsilon_{\\mathcal{A}} > \\alpha$. This indicates that the distribution shift is minimal but significant enough to consider, while the augmentations used are sufficiently strong. In this context, the rate involved in our theorem degenerates to $n_s^{-\\frac{\\alpha}{\\alpha + d + 1}}$, which is a typical rate in nonparametric statistics [a].\n\n[a] Nonparametric regression using deep neural networks with ReLU activation function\n\n> **Comment** Theorem 1's rate is a mixture of asymptotic and finite bounds. Asymptotic for the source task and finite for the target task.\n\n**Response** Thank you for your valuable comment. As you mentioned, our result does not provide a complete non-asymptotic upper bound for $n_s$. The primary challenge lies in the difficulty of determining a specific sample size $n_s$ based on the discussion from Lines 1000-1003 in our manuscript as the formulation of it is quite complex. Therefore, we adopt asymptotic analysis to circumvent this issue. This approach does not hinder our ability to further explore the finite-sample bound, provided that $n_s$ is sufficiently large. Thank you for your understanding.\n\n> **Comment** Although perhaps implicit in context I think the reader would be aided in learning that ReLU neural networks for classification is the model used.\n\n**Response** Thanks for your valuable advice. We have revised our manuscript according to it.\n\n> **Comment** Line 150, the authors say that $m$ could be infinite, yet later we consider a uniform density over all augmentations. Could the authors clarify this? It seems to me that a covering based argument over continuous augmentation classes would be more direct. Can the authors comment on the difficulty or feasibility of adapting their argument to this setting? In order to approximate some augmentation classes we require a cover that is exponential in dimension. e.g., rotational transformations. Thus, there can be additional dimensional dependence for augmentations commonly used. How does this affect the rate?\n\n**Response** Thank you for your question. We adopted a uniform distribution on a finite set $\\mathcal{A}$, which refers to a discrete distribution, as we considered the case where $m$ is finite. In fact, it is reasonable since only a finite number of augmentations will be used in numerical experiments or practical applications.\n\n> **Comment** Is the $1/\\min_k\\sqrt{n_t(k)}$ natural here should we expect something that is more balanced as as we get more data for all classes except for one.\n\n**Response** Exactly! In the scenario you mentioned, the model's performance on the exclusive class will be very poor, but it performs well on the others. This makes a lot of sense in the context of meta-learning. In fact, this case can be also captured by our theory. Thanks for your valuable questions.\n\n> **Comment** Biggest concern.\n\n**Response** Thank you for your question. As you mentioned, it is incorrect that $\\mathbb{E}\\_{\\widetilde{D}_{s}} \\sup\\_{G \\in \\widehat{\\mathcal{G}}(f)} \\widehat{\\mathcal{R}}(f, G) = \\mathcal{R}(f, G)$. We only have $\\mathcal{R}(f,G)=\\mathbb{E}\\_{\\widetilde{D}\\_{s}}\\widehat{\\mathcal{R}}(f,G)$. As we discussed in Section 3.2, this unbiased property reduces the gap between the population risk and the empirical risk. It is sufficient to establish our theoretical analysis with the help of this unbiasedness. \n\n> **Comment** Are ReLU networks a Holder class? As their partials may not exist everywhere.\n\n**Response** The ReLU networks used in this work belong to a H\"older's class. Since ReLU networks we used is Lipschitz continuous, they are H{\\\"o}lder continuous with index $\\alpha=1$. It worth noting that we assume the target function $f^{*}$ belongs to a H{\\\"o}lder's class, instead of ReLU neural networks.\n\nIf you have any questions, please feel free to further contact us. Thank you once again for your careful reading, professional suggestions, and inspiring recognitions."}, {"review_id": "8xreO8fFJ2", "reviewer": "Reviewer_41Yc", "summary": "The authors propose an improvement (termed ASSRL) in how self-supervised learning methods regularize their optimization. Specifically, they improve upon the regulization term that encourages alignment of the feature covariance matrix with the identity matrix. Prior work relied on a biased estimate of this term, leading to instability in optimization and preventing some theoretical analysis. The author's proposed method reformulates this term as a minimax optimization problem that can be optimized through an alternating optimization algorithm. This new formulation provides an unbiased estimate. While the authors primarily focuse on the theoretical soundness of their method, they also include empirical results that show their method does in fact enable an improvement over baselines.", "questions": "- How much of an impact does the method have on (empirical) training time?\n- How well does training scale with image/model size (the empirical evaluations all use relatively small image and model sizes).", "limitations": "Limitations adequately addressed.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "STRENGTHS\n\n- Very clearly written.\n- Motivations, background context, and logical flow of paper are very easy to follow.\n- Theory looks good and is clearly explained. Comprehensiveness of the analysis is a big plus.\n- Assumptions used seem reasonable / are similar to assumptions made in prior works. This is important--the theory would be less meaningful and useful if the assumptions were overly restrictive.\n- Empirical evaluations show generalization of theory to practice.\n\n\nWEAKNESSES\n\n- Empirical evaluations are limited in scope. While primary focus is the theory, so I am largely okay with this, evaluations beyond CIFAR and tiny ImageNet would further bolster their results.\n- Additionally, empirical results are all positive, but it is unclear how significant this is in terms of actual utility in situations where self-supervised learning is used in practice--CIFAR and tiny ImageNet are primarily used for small scale testing rather than real world use.\n- Table 2 compares the author's results with results from a prior paper. I think this is mostly fine, but it does slightly detract from the results, since training conditions may not be identical.", "was_revised": true, "final_justification": "I am keeping my rating. Authors addressed my concern about empirical results, but I feel the paper can still be accepted without the additional results.", "rebuttal": "We thank you for your thorough review of our manuscript and for your constructive suggestions. We have revised our manuscript by incorporating all of your suggestions. The revised version is much strengthened. Our point-by-point responses to your comments are given below.\n\n> **Comment**  \n> * Empirical evaluations are limited in scope. While primary focus is the theory, so I am largely okay with this, evaluations beyond CIFAR and tiny ImageNet would further bolster their results. \n> * Additionally, empirical results are all positive, but it is unclear how significant this is in terms of actual utility in situations where self-supervised learning is used in practice--CIFAR and tiny ImageNet are primarily used for small scale testing rather than real world use.\n> * How well does training scale with image/model size (the empirical evaluations all use relatively small image and model sizes).\n\n**Response**\nThank you for your valuable suggestion. We are working to obtain experimental results on ImageNet, but we will need more time to do so. Thank you for your understanding.\n\n> **Comment** \n> Table 2 compares the author's results with results from a prior paper. I think this is mostly fine, but it does slightly detract from the results, since training conditions may not be identical.\n\n**Response**\nThank you for your valuable questions. All implementations totally aligns with the experimental setting in [a] except for $\\lambda$. Therefore, the training conditions are identical.\n\n[a] Whitening for Self-Supervised Representation Learning, ICML 2021\n\n> **Comment**\n> How much of an impact does the method have on (empirical) training time?\n\n**Response** \nWe highly value this important question. First, it is clear that the additional cost of adversarial updates is negligible, as the inner maximization problem has an analytical solution, as shown in Step 8 of Algorithm 1. To further support this view, we provide the costs related to timing and memory below.\n\n| Methods | CIFAR-10 | CIFAR-10 | CIFAR-100 | CIFAR-100 | Tiny ImageNet | Tiny ImageNet | \n| ----- | ----- | ------ | ----- | ----- | ----- | ----- | \n| | Memory | Time | Memory | Time | Memory | Time | \n| Barlow Twins | 5598 MiB | 68s | 5598 MiB | 74s | 8307 MiB | 386s | \n| ASSRL | 5585 MiB | 51s | 5585 MiB | 52s | 8282 MiB | 352s |\n\nAll experiments were conducted using a single Tesla V100 GPU. The time mentioned refers to the time spent per epoch. \n\nThank you once again for your careful reading, professional suggestions, and inspiring recognitions. If you have any questions, please feel free to contact us."}, {"review_id": "kpuIopQ6rB", "reviewer": "Reviewer_5zMo", "summary": "This paper identifies that many self-supervised learning methods suffer from a biased sample risk, which causes optimization instability and prevents theoretical analysis. To solve this, the authors propose Adversarial Self-Supervised Representation Learning (ASSRL), a novel method that reframes the objective as a minimax problem to create an unbiased estimator. This adversarial approach leads to significantly improved classification accuracy, outperforming both the biased methods it aims to correct and other mainstream techniques on several benchmarks.", "questions": "Please see the comments above.", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n-\tThe paper clearly identifies a significant and practical problem in existing SSL methods—the bias in the sample-level risk approximation. The proposed solution, reformulating the objective as a minimax problem to create an unbiased estimator, is elegant and directly addresses this core issue.\n-\tA major strength of this work is the end-to-end theoretical analysis. Unlike prior work that often focused only on population-level risk or generalization error without considering approximation error, this paper provides a complete convergence analysis. The theory formally connects the number of unlabeled source samples to downstream task performance, which is a crucial aspect of transfer learning.\n-\tThe theoretical results offer a formal explanation for the success of SSL in few-shot learning contexts. The paper proves that with a sufficient amount of unlabeled data, ASSRL can learn representations that are well-clustered by category, thereby enabling strong classification with very few labeled samples. This bridges an important gap between the empirical success and theoretical understanding of few-shot learning.\n\nWeaknesses\n-\tThe theoretical guarantees rely on a number of assumptions (Section 3.3), particularly regarding data augmentations (Assumption 4) and the shift between source and target domains (Assumption 5). These assumptions, such as the existence of an augmentation sequence where distances between similar samples converge to zero, might be difficult to verify or guarantee in practice. Could the authors provide more intuition on why these assumptions are reasonable for standard computer vision datasets and augmentation pipelines?\n-\tThe paper introduces an alternating optimization algorithm (Algorithm 1) but does not analyze its practical implications in detail. There is no discussion of the computational overhead of the adversarial updates compared to the simpler direct minimization in methods like Barlow Twins. The ablation study on the regularization parameter λ shows that its optimal value varies significantly across datasets (e.g., 5.0×10−2 for CIFAR-10 vs. 1.0×10−2 for CIFAR-100). This suggests the method may be sensitive to this choice, requiring expensive tuning for new applications. A more in-depth analysis of this sensitivity would be valuable.\n-\tThe baselines in the key comparison table (Table 1) are re-implementations by the authors. While the authors state that their results are close to those in the LightlySSL library, a direct comparison to the numbers reported in the original papers (e.g., [22, 38]) would provide a stronger and more objective benchmark. This would help ensure that the observed performance gap is entirely due to the methodological improvement of ASSRL and not differences in implementation.\n-\tThe paper's checklist (Question 7) states that the experimental results report the best performance over three runs, rather than providing error bars or other measures of statistical significance. While the reported performance gains are large, this approach makes it difficult to assess the stability and variance of the results. Standard practice would be to report the mean and standard deviation over multiple runs, which would make the empirical claims much more robust and convincing.", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your thorough review of our manuscript and for your constructive suggestions. We have revised our manuscript by incorporating all of your suggestions. The revised version is much strengthened. Our point-by-point responses to your comments are given below.\n\n> **Comment**  The theoretical guarantees rely on a number of assumptions (Section 3.3), particularly regarding data augmentations (Assumption 4) and the shift between source and target domains (Assumption 5). These assumptions, such as the existence of an augmentation sequence where distances between similar samples converge to zero, might be difficult to verify or guarantee in practice. Could the authors provide more intuition on why these assumptions are reasonable for standard computer vision datasets and augmentation pipelines?\n\n**Response** Thank you for your question. As you mentioned, it might be difficult to verify in practice. To provide more intuitions, we have illustrated Assumption 4 in Appendix F.2 with toy examples. Meanwhile, the corresponding explanation of Assumption 5 can be found in Appendix F.3. Thank you for your understanding.\n\n> **Comment**  The paper introduces an alternating optimization algorithm (Algorithm 1) but does not analyze its practical implications in detail. There is no discussion of the computational overhead of the adversarial updates compared to the simpler direct minimization in methods like Barlow Twins. \n\n**Response** We highly value this important question. First, it is clear that the additional cost of adversarial updates is negligible, as the inner maximization problem has an analytical solution, as shown in Step 8 of Algorithm 1. To further support this view, we provide the costs related to timing and memory below.\n\n| Methods | CIFAR-10 | CIFAR-10 | CIFAR-100 | CIFAR-100 | Tiny ImageNet | Tiny ImageNet | \n| ----- | ----- | ------ | ----- | ----- | ----- | ----- | \n| | Memory | Time | Memory | Time | Memory | Time | \n| Barlow Twins | 5598 MiB | 68s | 5598 MiB | 74s | 8307 MiB | 386s | \n| ASSRL | 5585 MiB | 51s | 5585 MiB | 52s | 8282 MiB | 352s |\n\nAll experiments were conducted using a single Tesla V100 GPU. The time mentioned refers to the time spent per epoch. \n\n> **Comment** The ablation study on the regularization parameter $\\lambda$ shows that its optimal value varies significantly across datasets (e.g., 5.0×10−2 for CIFAR-10 vs. 1.0×10−2 for CIFAR-100). This suggests the method may be sensitive to this choice, requiring expensive tuning for new applications. A more in-depth analysis of this sensitivity would be valuable.\n\n**Response** Thank you for your suggestion. We recognize that tuning costs are inevitable for almost all new methods. Additionally, we must emphasize that the results in Table 4 significantly outperform the biased methods shown in Table 1, regardless of the value of $\\lambda$, indicating that the tuning parameters do not impact our experimental advantages. Thank you for your understanding.\n\n> **Comment** The baselines in the key comparison table (Table 1) are re-implementations by the authors. While the authors state that their results are close to those in the LightlySSL library, a direct comparison to the numbers reported in the original papers (e.g., [22, 38]) would provide a stronger and more objective benchmark. This would help ensure that the observed performance gap is entirely due to the methodological improvement of ASSRL and not differences in implementation\n\n**Response** Thank you for your suggestion. However, the original papers did not report corresponding results on the datasets used in our study. To facilitate a comparison, we are actively working to obtain results on ImageNet, but we will need more time to achieve this. Thank you for your understanding.\n\n> **Comment** The paper's checklist (Question 7) states that the experimental results report the best performance over three runs, rather than providing error bars or other measures of statistical significance. While the reported performance gains are large, this approach makes it difficult to assess the stability and variance of the results. Standard practice would be to report the mean and standard deviation over multiple runs, which would make the empirical claims much more robust and convincing.\n\n**Response** Thank you for your valuable suggestion. Our preliminary results are shown as below:\n\n| Method | CIFAR-10 | CIFAR-10 | CIFAR-100 | CIFAR-100 |\n| ----- | ----- | ----- | ----- | ----- |\n| | Mean | Deviation | Mean | deviation |\n| ASSRL | 92.49 | 0.71 | 68.53  | 0.67 |\n\nThank you once again for your careful reading, professional suggestions, and inspiring recognitions. If you have any questions, please feel free to contact us."}, {"review_id": "S42YuBxkXk", "reviewer": "Reviewer_sjVz", "summary": "This paper introduced a new self-supervised learning approach named Adversarial Self-Supervised Representation Learning (ASSRL) for unbiased transfer learning. Through an innovative iteration format, ASSRL eliminates the bias between the population risk and its sample-level counterpart. In this paper, the end-to-end theoretical guarantee for the downstream classification task performance is provided. This theoretical understanding also explains the effectiveness of few-shot learning for downstream tasks with small sample sizes. Experiments are presented in this paper to show the effectiveness of the ASSRL method.", "questions": "1. For the question the authors raised in line 187, do the authors aim to answer this question just by the empirical experiments in Table 1? Or can this question also be answered from the theoretical perspective? Please elaborate on this question in more detail.\n\n2. For the experimental results, why did the authors select some of the existing methods from [14] for comparison? Any reason for choosing only these self-supervised learning methods for comparison? \n\n3. Why is the comparison not made with more state-of-the-art self-supervised learning methods? For example, what about those self-supervised learning methods that are mentioned in the introduction of this paper?", "limitations": "The limitations are discussed in the appendix of this paper, mainly about the minimax rates and the lower bound for the ASSRL method. Other limitations see  the question part.", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. This paper proposed a new adversarial contrastive learning method for unsupervised transfer learning.\n2. End-to-end theoretical analysis for the downstream classification task is given in this paper.\n3. Experimental results are given to show the improved accuracy for this new ASSRL method.\n\nWeaknesses:\n1. The experimental results comparison only covers a few existing self-supervised learning methods.", "was_revised": true, "final_justification": "I tend to keep my original score. As discussed in the reviews and rebuttals, some important insights and clarification (such as those regarding the theorems and assumptions) should be included in the revised version, while maintaining a complete structure of the paper. I also noticed that other reviewers also raised some concerns about the experiments. Therefore, I sincerely hope that the authors can address these points in the revised version of this paper.", "rebuttal": "We thank you for your thorough review of our manuscript and for your constructive suggestions. We have revised our manuscript by incorporating all of your suggestions. The revised version is much strengthened. Our point-by-point responses to your comments are given below.\n\n> **Comment** \n> * The experimental results comparison only covers a few existing self-supervised learning methods.\n> * For the experimental results, why did the authors select some of the existing methods from [14] for comparison? Any reason for choosing only these self-supervised learning methods for comparison?\n> * Why is the comparison not made with more state-of-the-art self-supervised learning methods? For example, what about those self-supervised learning methods that are mentioned in the introduction of this paper?\n\n**Response** \nThank you for your valuable suggestions. We have add the comparison with [a] VICReg: Variance-Invariance-Covariance Regularization for Self-Supervised Learning, ICLR 2022. [b] Geometric View of Soft Decorrelation in Self-Supervised Learning, KDD 2024. The preliminarily results are shown below\n\n\n| Method | CIFAR-10 | CIFAR-10 | CIFAR-100 | CIFAR-100 |  Tiny ImageNet | Tiny ImageNet |\n| ---- | ----- | ----- | ----- | ----- | ---- | ----- |\n|  | Linear | $k$-nn | Linear | $k$-nn | Linear | $k$-nn |\n| VICReg | 91.23 | 89.15 | 67.61 | 57.04 | 48.55 | 35.62 |\n| LogDet | 92.47 | 90.19 | 67.32 | 57.56 | 49.13 | 35.78 |\n| ASSRL | **93.01** | **90.97** | **68.94** |  **58.50** | **50.21** | **37.40** |\n\n> **Comment** \nFor the question the authors raised in line 187, do the authors aim to answer this question just by the empirical experiments in Table 1? Or can this question also be answered from the theoretical perspective? Please elaborate on this question in more detail.\n\n**Response** \nExactly. The question you raised is undeniably important and extremely valuable. We posit that the improvements can be explained from an unbiased perspective, as discussed in the introduction. Roughly speaking, the original iteration method is driven by a biased sampling-level risk, while our revision leads to an unbiased sampling-level risk. This unbiasedness results in better performance of our methods.\n\n> **Comment** The structure of the paper may be incomplete. The authors could at least include a conclusion in the main paper to provide a complete structure of the paper.\n\n**Response** Thank you for your suggestions. I will add a conclusion in the main paper to provide a complete structure of the paper.\n\n> **Comment** More details about the insights and remarks could be given in the main text, for example, the experiments in Section 4. In the current version, it seems that some important information is missing.\n\n**Response** Thank you for your suggestions. Due to the limitation of the space, we move some remarks and illustrations to the appendices. For example, we provide explanations and toy examples of the assumptions in Appendix F, and the experimental details are offered in Appendix E. Some insightful ablation experiments are deferred to Appendix E. In our revised version, we reorganize our manuscript and move some important insights and remarks to our main text.  \n\n\nThank you once again for your careful reading, professional suggestions, and inspiring recognitions. If you have any questions, please feel free to contact us."}]

Author rebuttal:

Meta-review: This paper introduces adversarial self-supervised representation learning (ASSRL) to address the biased sample risk inherent in SSL that aims to align the covariance/correlation matrix to a diagonal matrix. By adopting the adversarial learning idea of performing representation learning via solving a min-max optimization, the paper provides theoretical guarantees on generalization error in transfer learning scenarios under misspecified settings.

Reviewer evaluations are split around the borderline. While the rigor of the theoretical claims is largely appreciated, concerns have been raised about the real-world plausibility of the assumptions used in the theory, the practical implications of the proposed algorithm, and the settings and evaluation methodology of the experiments. In particular, although the direct performance comparisons with existing methods are not necessarily presented in a convincing manner, I judge the authors’ responses to these points to be reasonable since the main contribution of this paper is on the theoretical side. I believe the work will attract interest of the contrastive learning community, so I recommend acceptance.
Decision: Accept (poster)