Out-Of-Domain Unlabeled Data Improves Generalization
Authors: seyed amir hossein saberi
Amir Najafi
Alireza Heidari
Mohammad Hosein Movasaghinia
Abolfazl Motahari
Babak Khalaj
Venue: ICLR 2024 spotlight (2024)
Keywords: Out-of-domain data
Semi-supervised learing
learning theory
generalization bound
adversarial robustness
Primary area: learning theory
TL;DR: We propose a framework to incorporate unlabeled out-of-domain samples in order to enhance the generalization error. We derive explicit bounds for Gaussian mixture models, and test our method on real datasets.

Abstract: We propose a novel framework for incorporating unlabeled data into semi-supervised classification problems, where scenarios involving the minimization of either i) adversarially robust or ii) non-robust loss functions have been considered. Notably, we allow the unlabeled samples to deviate slightly (in total variation sense) from the in-domain distribution. The core idea behind our framework is to combine Distributionally Robust Optimization (DRO) with self-supervised training. As a result, we also leverage efficient polynomial-time algorithms for the training stage. From a theoretical standpoint, we apply our framework on the classification problem of a mixture of two Gaussians in $\mathbb{R}^d$, where in addition to the $m$ independent and labeled samples from the true distribution, a set of $n$ (usually with $n\gg m$) out of domain and unlabeled samples are gievn as well. Using only the labeled data, it is known that the generalization error can be bounded by $\propto\left(d/m\right)^{1/2}$. However, using our method on both isotropic and non-isotropic Gaussian mixture models, one can derive a new set of analytically explicit and non-asymptotic bounds which show substantial improvement on the generalization error compared ERM. Our results underscore two significant insights: 1) out-of-domain samples, even when unlabeled, can be harnessed to narrow the generalization gap, provided that the true data distribution adheres to a form of the "cluster assumption", and 2) the semi-supervised learning paradigm can be regarded as a special case of our framework when there are no distributional shifts. We validate our claims through experiments conducted on a variety of synthetic and real-world datasets.

Published as a conference paper at ICLR 2024
OUT-OF-DOMAIN UNLABELED DATA IMPROVES GENERALIZATION
Amir Hossein Saberi 1+
Amir Najafi
Alireza Heidari Babak H. Khalaj
Mohammad Hosein Movasaghinia f
Seyed Abolfazl Motahari
Department of Electrical Engineering, Department of Computer Engineering.
$ Sharif Center for Information Systems and Data Science, Sharif Institute for Convergence Science Technology.
Sharif University of Technology, Tehran, Iran
ABSTRACT
We propose novel framework for incorporating unlabeled data into semi- supervised classification problems, where scenarios involving the minimization of either i) adversarially robust or ii) non-robust loss functions have been considered. Notably, we allow the unlabeled samples to deviate slightly (in total variation sense) from the in-domain distribution. The core idea behind our framework is to combine Distributionally Robust Optimization (DRO) with self-super training. As a result, we also leverage efficient polynomial-tin
algorithms for the training stage. From theoretical standpoint, we apply our framework on the classification prob- lem of a mixture of two Gaussians in IRd where in addition to the m independent and labeled samples from the true distribution, a set of n (usually with n >> m) out domain and unlabeled samples are given as well. Using only the labeled data, it is known that the generalization error can be bounded by x (d/m) 1/2 However, using our method on both isotropic and non-isotropic Gaussian mixture models, can derive a new set of analytically explicit and hon-asymptotic bounds which show substantial improvement on the generalization error compared to ERM. Our results underscore two significant insights: 1) out-of-domain samples, even when unlabeled, can be harnessed to narrow the generalization gap, provided that the true data distribution adheres form of the "cluster assumption", and 2) the semi- supervised learning paradigm can be regarded as special case of our framework when there no distributional shifts. We validate our claims through experiments conducted on a variety of synthetic and real-world datasets.
INTRODUCTION
Semi-supervised learning has long been focal point in the machine learning literature, primarily due to the cost-effoctivveness of utilizing unlabeled data compared to labeled counterparts. However, unlabeled data in various domains, such medicine, genetics, imaging, and audio processing, often originates from diverse sources and technologies, leading to distributional differences between labeled and unlabeled samples. Concurrently, the development of robust classifiers against adversarial attacks has emerged as a vibrant research area, driven by the rise of large-scale neural networks (Goodfellow) al. 2014 Biggio & Roli 2018). While the primary objective of these methods is to reduce model sensitivity to minor adversarial perturbations, recent observations suggest that enhancing adversarial
robustness may also improve the utilization of unlabeled samples (Najati et al. 2019 Miyato et al.. 2018).
This paper aims to demonstrate the efficacy of incorporating out-of-domain unlaheled samples to decrease the reliance on labeled in-domain data. To achieve this, we propose novel framework inspired by a fusion of concepts from adversarial robustness and self-training. Specifically, we introduce unique constraint to the conventional Empirical Risk Minimization (ERM) procedure, focusing exclusively on the unlabeled part of the dataset. Our theoretical and experimental analyses
"Corresponding author; motahar 8shari f.edu.

---

Published as a conference paper at ICLR 2024
show that the inclusion of unlabeled data reduces the generalization gap for both robust and non- robust loss functions. Importantl, our alternative optimization criteria are computationalyy efficient and can be solved in polynomial time. We have implemented and validated the effectiveness of our method on various synthetic and real-world datasets.
From a theoretical standpoint, akin to prior research (Schmidt et al. 2018 Carmon et al. 2019 Zhai al. 2019| Alayrac et al., 2019), we also address the binary classification problem involving two Gaussian models in g This problem has been the center of attention in several recent works on theoretical analysis of both semi-supervised and/or adversarially robust learning paradigms. Despite several recent theoretical investigations, the precise trade-off between the sizes of labeled (m) and unlabeled (n) data, even in this specific case, remains incomplete. A number of works have bounded the labeled sample complexity under the assumption of an asymptotically large n (Kumar et al. 2020), while another series of papers have analyzed this task from a completely unsupervised viewpoint. We endeavor to fill this gap by providing the first empirical trade-off between m and n, even when unlabeled data originates from slightly perturbed distribution. We derive explicit bounds for both robust and non-robust losses of linear classifiers in this scenario. Our results show that as long as 12 (m² /d), our proposed algorithm surpasses traditional techniques that solely rely on labeled data. We also consider the more general case of non-isotropic Gaussian models, as explored in previous studies.
The remainder of this paper is structured as follows: Section 1.1 provides an overview of related works in distributionally robust optimization and semi-supervised learning. Section [.3 introduces our notation and definitions. In Section 1.2, we discuss the contributions made by our work. In Section 3 we present our novel method, followed by a theoretical analysis in Section 4 Section 5 showcases our experimental validations, further supporting our theoretical findings. Finally, we draw conclusions in Section 6
1.1
PRIOR WORKS
One of the challenges in adversarially robust learning is the substantial difficulty in increasing the robust accuracy compared to achieving high accuracy in non-robust scenarios (Carlini & Wagner 2017). A study by (Schmidt et al. (2018) posited that this challenge arises from the larger sample complexity associated with learning robust classifiers in general. Specifically, they presented simple model where good classifier with high standard (non-robust) accuracy can be achieved using only a single sample, while a significantly larger training set is needed to attain a classifier with high robust accuracy. Recent works (Carmon et al. 2019 Zhhi et al. 2019, Alayrac et al. 2019) demonstrated that the gap in sample complexity between robust and standard learning, as outlined by [Schmidt et al. (2018) in the context of a two-component Gaussian mixture model, can be bridged with the inclusion of unlabeled samples. Essentially, unlabeled samples can be harnessed to mitigate classification errors even when test samples are perturbed by an adversary. Another study by Najafi et al. (2019) achieved similar result using a different definition of adversarial robustness and a more comprehensive data generation model. Their approach involves the use of 'self-training' to assign soft/hard labels to unlabeled data, contrasting our approach, where unlabeled data is exclusively utilized to constrain the set of classifiers, aiming to avoid crowded regions. While DRO serves as a tool in our approach, it is not necessarily the primary objective. In Deng et al. (202I). authors showed that in the setting of Schmidt et al. (2018), out-of-domain unlabeled samples improve adversarial robustness.
Theoretical analysis of Semi-Supervised Learning (SSL) under the so-called cluster assumption has been long-studied task (Rigollet 2007). However, beyond Najati et al. (2019), several recent
methods leveraging DRO for semi- sunerviieee learning have emerged (Blanchet & Kang 2020
Frogner et al.) 2021). Notably, |Frogner et al. (202T) shares similarities with Najafi et al. (2019);
however, instead of assigning artificial labels to unlabeled samples. |Frogner et al. (2021) employs them to delimit the ambiguity set and enhance understanding of the marginals. Our work primarily focuses on the robustness aspect of the problem rather than advancing the general SSL paradigm.
Defense mechanisms against adversarial attacks usually consider two types of adversaries: i) point- wise attacks similar to Miyato et al. (2018): Nguyen et al. (2015): Szegedy et al. (2013). and ii) distributional attacks (Staib & Jegelka 2017 Shafieezadeh Abadeh et al. 2015; Mohajerin Esfahani & Kuhn 22088), where in the case of the latter adversary can change the distribution of data up to predefined budget. It has been shown that Distributionally Robust Learning (DRL.) achieves
2

---

Published as a conference paper at ICLR 2024
superior robustness compared to point-wise methods (Staib & Jegelka 2017). Namkoong & Duchi (2017) utilized DRL in order to achieve a balance between the bias and variance of classifier's 's error, leading to faster rates of convergence compared empirical risk minimization even in the non-robust case. In DRI,, the learner typically aims to minimize the loss while allowing the data distribution to vary within an uncertainty neighborhood. The central idea used by Namkoong & Duchi (2017) was to regulate the diameter of this uncertainty neighborhood based on the number of samples. Gao (2022) achieved similar results in DRL while utilizing the Wasserstein metric to define the perturbation budget for data distribution. Based on the above arguments, we have also utilized DRL is the main tool in developing our proposed framework.
1.2 MAIN CONTRIBUTIONS
We introduce a novel integration of DRO and Semi-Supervised Learning (SSL), leveraging out-of- domain unlabeled samples to enhance the generalization bound of learning problem. Specifically, we theoretically analyze our method in the setting where samples are generated from a Gaussian mixture model with two components, which is common assumption in several theoretical analyses this field. For example, a simpler format, when two Gaussians are isotropic and well-separated, is the sole focus of many papers such as (chhiddt et al. 2018); Carmon et al. (2019): Alayrac et al. 2019..Som of our notable contributions and improvements over recent works in the field include:
(i) In Theorem 4.1
we present a non-asymptotic bound for adversarially robust lcarning, leveraging both labeled and unlabeled samples jointly. This result builds upon the work of et al. (2019) and Alayrac et al. (2019), which focused on the effectiveness of unlabeled samples when a single labeled sample is sufficient for linear classification of a non-robust classifier. However, these studies do not provide insights into the necessary number of unlabeled samples when multiple labeled samples are involved, particularly in scenarios where the underlying distribution exhibits limited separation between the two classes. Our theoretical bounds address and fill this crucial gap.
(ii) Theorem 4.2 introduces a novel non-asymptotic bound for integrating labeled and unlabeled samples in SSL. To underscore the significance of our findings, consider the following example: In the realizable setting, where positive and negative samples can be completely separated by a hyperplane in Rd. the sample complexity of supervised learning for a linear binary classifier is known to be (dd/e) Mohri et al. (2018). However, in the non-realizable setting, this complexity escalates to Odde²) Mohri et al. (2018) 8).A pivotal question in learning theory revolves around how to approach the sample complexity of (d/e) )) in the realizaliz setting. Insights provided by Namkoong & Duchi (2017) delve into this inquiry. Notably, even with the awareness that the underlying distribution is a Gaussian mixture, the optimal sample complexity, as per AAshtiani et al. (2088), still exceeds (dd/2). Our work demonstrates that in scenarios where the underlying distribution is Gaussian mixture and we possess m O(d/c) labeled samples, coupled with O (..) unlabeled samples (without knowledge of the underlying distribution), one can achieve an error rate lower than or equal
to the case of having access to (dde22) labeled samples.
(iii) We formalize the incorporation of out-of-domain unlabeled samples into the generalization bounds of both robust and non-robust classifiers in Theorems 4.1 4.2 and 4.4 We contend that this represents novel contribution to the field, with its closest counterpart being Deng et al. 2021)) Notably, Deng et al. (202T) addresses scenario where the underlying distribution is a isotropic Gaussian mixture with well-separated Gaussian components, while the separation of components is not a prerequisie for our results.
1.3 NOTATION AND DEFINITIONS
Let us denote the feature space by X' C Rd, and assume 7L as class of binary classifiers parameter- ized by the parameter set O: for each f E Ô, we have a classifier he E H where he : X - {-1, 1}. Assume positive function é: (X' x (-1, 1} x +) + R> as the loss function. Also, let P be the unknown data distribution over X [-1, 13. and = [(X,, ()) bm for m E N be a set of i.i.d.
samples drawn from P. Then, for all 0 E θ the true risk R and the empirical risk it of a classifier w.r.t. P can be defined as follows:
1
R (0, P) Ep [e (X(X,) 2i 0)]
R(0, P
E pg [X(, 21 0)
e (X,.96)) 0); (1)
3

---

Published as a conference paper at ICLR 2024
where Pn denotes empirical estimate of P based on the samples in S. We also need way to measure the distance between various distributions that are supported over X. well-known candidate for this goal is the Wasserstein distance (Definition A.I Subsequently, Wasserstein ball in Definition A.2 in order to effectively constrain a set of probability measures. should be noted that throughout this paper, the Wasserstein distance between any two distributions supported over X' x } is defined as the distance between their respective marginals on X'.
also define
The ultimate goal of classical learning R (0*) is sufficiently close to mina R (0). A well-known approach to achieve this goal is Empirical Risk Minimization (ERM) algorithm, formally defined as follows:
find the parameter 0* O such that with high probability,
m Σ 8Ee Y7
.)] jEHM (S) - arg min Epy Le (0; [.)] arg min 1E0
{0; 3t).
A recent variant of ERM, which has gained huge popularity in both theory and practice, is the so-called Distributionally Robust Learning (DRL) which formulated follows:
Definition 1.1 (Distributionally Robust Learnin(DDRL),, DRL aims training a classifier which is robust against adversarial attacks on data distribution. In this regard, the learner attempts to find a classifier with small robust risk, denoted as Rrobust P), which is defined as
Reobust (0, P)
R (0, P'), P'EBE(P)
sup
for all 0 θ and any 2 0. Therefore, DRL solves the following optimization problem:
@DRL (S) a arg min probust (0. Pm
0Ee
Surprisingly, the sophisticated minimax optimization problem of equation 4 which takes place in subset of the infinite-dimee dimnnesddimniin space of probability measures that corresponds to the constraints, can be substantially simplified when is re- re-written in the dual format:
Lemma 1.2 (From Blanchet et al. (2019)). For a sufficiently small > 0, the minimax optimization has the following dual form:
problem of equation 4
inf BEB (PE)
sup
RO0,P") = inf 720
7E inf Σ sup e (Z,
- (2,
(5)
8EB
m 1=1 ZEX
where and are dual parameters, and there is bijective and reciprocal relation between the and y", Le., the optimal value which minimizes the r.h.s.
As suggested by Sinha et al. (2017), the inf,20 in the r.h.s. part in the above optimization problem can be removed by fixing definddfined value for y. This also means that one attempts to find the optimal value for 6, the additive term Y is ineffective and can be removed as well.
should be noted that this also fixes an (unknown) value for e. In practice, the appropriate value for is not known beforehand and thus can be usually found through same procedure can be applied its dual counterpart, i.e., 7. In other words, the above-mentioned strategy keeps the generality of the problem intact. For the sake of simplicity in relations, throughout the rest of the paper we work with the dual formulation in equation 5aad let y be a fixed and arbitrary value.
cross-validation stage, while the
2 PROBLEM DEFINITION
At this point, we can formally define our problem. Let X' C Rdd and assume Po be an unknown and arbitrary distribution supported on X' x (+1), i.e., Po produces feature-label pairs. For valid cost function X + R20. let P1 represent shifted version of Po such that the marginal distributions of Po and P1 on X' are shifted with W. (Po.x,P..x) = a for some a > O. No assumption on Pi X)) is necessary in this work. Here, the subscript X implies the marginal distribution on X. Let us consider the following two sets samples:
So (( pm
S = (X Plx:
4

---

Published as a conference paper at ICLR 2024
where So indicates the labeled set and S1 represents the unlabeled out-of-domalee data. A classical re- sult from VC-theory states that the generalization gap in learning from only So (with high probability) can be bounded as
R (OURM Po)
min R (o) + (VCCimm (H)/m) + V011/m, dEG
(6)
where VCdim (H) denotes the VC-dimension of hypothesis class H. (Mohri et al. 2018). This bound can be prohibitively large when VCdim (H) grows uncontrollably, e.g., the of linear classifiers in very high dimensions (d > 1).
We aim to propose a general framework that leverages both So and S1 concurrently, and outputs (in polynomial time) estimator, denoted by @RSS, such that the second term in the r.h.s. of equation 6 would decay faster as one increases both m and n.. We are specially interested in cases where n >> m In the next step, we apply our method on simplified theoretical example in order to give explicit bounds. Similar to SShhmidt et al. (2018); Carmon et al. (0119); Zhai et al. (2019; |llarrac et al. (2019), we fully focus the binary classification problem high-dimensional Gaussian mixture model with two components using linear classifiers. Mathematically speaking, for some on Z 0 and 140 E Rd, let Po be the feature-label joint distribution over IR4 x {-1,1} 13 as follows:
1 Po (v 1) 2'
Px = N (1140, rgr).
Also, suppose shifted version of Po. denoted by P1 with Pl.x = En-,) of
where || I1ll configuration, the problem is to estimate the optimal linear classifier which achieves the minimum error rate.
|| I O (a) and |o Øol < O [ Given the two sample sets So and S this
3 PROPOSED METHOD: ROBUST SELF SUPERVISED (RSS) TRAINING
We propose a solution that combines two generally independent paradigms in machine learning: self-training (Grandvalet & Bengio 2004 Amini & Gallinari, 2002), and distributionally robust learning in equation 4 The essence of self-training is to use the currently learned model in order to induce artificial labels the unlabeled data. Thus, for unlabeled sample X3 and any given model parameter 0 E θ, one can temporarily consider a pscudo label given by ha (Xj). In this regard, the
proposed solution denoted by gisss guss (So, S1) can be defined as follows:
Definition 3.1 (Robust Self Supervisee (RSS) Training). The essence of RSS training is to add penalty term to the robust version of the original ERM formulation, which solely evaluated from the out-of-domain unlabeled samples in Sr. Mathematically speaking, for cost function and parameter 7 2 0, let us define the robust loss Φy : X' x {+1} x e Ra
Φy (X, y; 0)
sup f (Z, 0) yC ( X). ZEX
(8)
In this regard, for a given set of parameters 7/5 7 A E R20, ., the proposed RSS estimator is defined as
Ui: 8) + Σ By (X ho (XG) 0) }
RRss A arg min OE0
1 m
(9)
The proposed RSS loss in equation 9 comprises of two main terms. The first term attempts to minimize the empirical robust risk over the labeled data in So, where an adversary can alter the distribution of samples within a Wasserstein radius characterized by 7. In the proceeding sections, we show that y can become asymptotically large (radius becomes infinitesimally small) as m - oo which is similar to Gao 2022)). In fact, small (but non-zero) budget for the adversary can control the generalization. The second term works only on the unlabeled data which are artificially labeled by hgg can be shown that this term regulates the classifier by forcing it to avoid crowded areas. The sensitivity of such regularization is controlled by both À and also '/
'avinn Wasserstein distance of a between two high-dimensional Gaussian distributions implies that both mean vectors no: d4 and variances do, di are within fraction of most O (a) from each other.
5

---

Published as a conference paper at ICLR 2024
3.1 MODEL OPTIMIZATION: ALGORITHM AND THEORETICAL GUARANTEES
It can be shown that the for a convex loss function L, convex cost function c, and sufficiently large and 7 (i.e., sufficiently small Wasserstein radii), the optimization problem of equation 9 is convex and can be solved up to an arbitrarily high precision in polynomial time. Moreover, if l is not convex, e.g.. H the set of all neural networks, a simple Stochastic Gradient Descent (SGD) algorithm is still guaranteed to reach to at least local minimum of equation 9 More specifically, equation 9 is a minimax optimization problem and consists of an inner maximization (formulated in equation g) followed by an outer minimization. As long as the cost function e is strictly convex and or y are chosen sufficiently large, the inner maximization problem of equation g becomes strictly concave (Najafi et al., 2019; Sinha et al., 2017). This interesting property holds regardless the convexity of e, which is of paramount importance since E is not convex in most practical situations. On the other hand, cost function candidates for e which are considered this paper are ||-1|2 and I1-112. which are strictly convex. Hence, equation Saaaatioonnannn can be optimally solved in polynomial time.
The outer minimization problem of equation is also differentiable as long as & is sufficiently smooth (again, convexity is not needed). This means the gradient of equation 9 Texists and can be efficiently computed using the Envelope Theorem. Explicit bounds on the maximum number of steps in simple SGD algorithm (with a mini-batch size of 1) in order reach to an e-neighborhood of the global maximum of equation 8 and local minimum of equation 9 are given by /iinaa et al. (2017). Also, formulating the gradient of minimax loss functions such as equation 9 using the envelope theorem has been carried out, for example, in (Najafi et al., 2019 Sinha et al.) 2017). We have also used the same gradient formulation for the numerical optimization of our model parameters in Section 5 where experimental
results on real data using neural networks have been illustrated.
In the next section, we derive theoretical guarantees for @RSs and show that it leads to improved generalization bounds when n is sufficiently large and a is controlled.
4 THEORETICAL GUARANTEES AND GENERALIZATION BOUNDS
In this section, we discuss the theoretical aspects of using the RSS training method, specially for the classification of a two-component Gaussian mixture model using linear classifiers, i.e., H. é {sign ((,,)) -)): Rd + {=1}| 0 R For the sake of simplicity in results, let us define the loss function as the zero-one loss:
l (X, y: 0) = 1 (y(0, X 2).
(10)
However, extension of the theoretical guarantees in this work to other types of loss functions is straightforward. The following theorem shows that the proposed RSS estimator in 9 can potentially improve the generalization bound in robust learning scenario.
Theorem 4.1. Consider the setup described in Section 2 for the sample generation process (GMM
assumption), and the loss function defined in equation 10 Using RSS training with m labeled and n unlabeled samples in So and S1, respectively, and for any 7, > there exist X and n which can be calculated solety based on input samples such that the following holds with probability at least 6:
Epo [0r
Xx y:: @RSS)
}]
min Ep, J0,, (X, y: 0) AEN
(11)
2d m
2d
2 log (1/8) 2n + m
log (1/8) m
+ 0
7
(1) 112 + +o +
+ V
+
2n + m
The proof, as well as how to calculate and 7 can be found in Appendix Theorem 4.1 presents generalization bound for the proposed estimator when one considers the robust loss under an adversarial budget, which is characterized by 7. Larger values of y correspond to smaller Wasserstein
|
radii for the distributional adversary of equation 3 The residual term in the r.h.s. of equation [] converges to zero with a faster rate compared to that of equation 6 given n is sufficiently large and is sufficiently small. We derive explicit conditions regarding this event in Corollary 4.3 Before that, let us show that for fixed m, as one increases the number of unlabeled samples n, the non-robust excess risk of the RSS-trained classifier decreases well:

---

Published as a conference paper at ICLR 2024
Theorem 4.2. Consider the setting described in Theorem 4.1 Then, the estimator & of equation using respectively m labeled and n unlabeled samples, along with specific values of y', and which can be calculated solety from the input samples, satisfies the following non-robust generalization bound with probability at least 6:
R [ouss,
min R P) BE
(12)
1 1 e
(111112 +o3) 2da
4d V
2d log
3/
2 log
S O
220o22 2n
2n m
Again, the proof and the procedure for calculating 7, 7, and x discussed in Appendix B
Based on the previous results, the following corollary showcases a number of surprising non- asymptotic conditions under which our generalization bound becomes superior conventional approaches.
Corollary 4.3. Consider the setting described in Theorem 4.2 Then, @Ass of equation with m labeled and unlabeled samples has an advantage over the traditional ERM,
a a Od/m))
n. 2 (m² /d)-
(13)
Also, the following conditions sufficient make the minimum required (for given error bound) independent of the dimension d:
a 250
n 2 (d.)
(14)
Proof is given in Appendix. Finally, Theorem 4.2 also implies that if unlabeled samples are drawn from the same distribution as that of the labeled ones, i.e., a = 0, then the excess risk of RSS USS-training satisfies the following inequality with probability least 8:
(( d log 1/8
log 1/8
R (anss P)
min R (0, s dee
(15)
m2 (2n + m))
which again shows the previously-mentinn mentioned improvements when all samples are in-domain.
The assumption of an isotropic GMM with two components has been already studied in the literature (see Section[]. Next, we present a more general case of Theorem|442) where each Gaussian component can have non-diagonal covariance matrix. Mathematically speaking, suppose that Po and P3 are defined as follows:
(v =
= =)
Po (X = N (ypo, Eo),
p = 2 (uI, En) + 11-111135 (-H1, En)
(-H1.
(16)
where [|m - Holl s O (a).1IE Eoll2 s (a))) and || 122 2 A (E1). Assume set of m labeled samples So ~ P and a set of unlabeled samples S1 P
Theorem 4.4 (Generalization Bound for General Gaussian Mixture Models), Consider the setting described in equation [6 Using algorithm in equation 9 with labeled and n unlabeled samples, there exists a set of parameters 7, 7 X for which the following holds with probability at least
R. @RSS,_r .P)
min R R P) BEB
(17)
1/2
eu2
M1 2 + Tr (Ez)
log
drant
log 1/5
Ca
+
m
2n + m
A (2)
m
where
|| + Amin (Ex) ||mol22
0 = 111 2 M11 100 t C=
X2 Xaain
Amax (En)
K/ Amax (E1)
K1 Amin (E1)²
A AEE))
A (E1)= = min (); (21) A (E1),, Vi, A (2i) # X3 (E1),
(18)
and Xe (E) is the i(th) eigenvalue of E.
7

---

Published as a conference paper at ICLR 2024
Table 1: Accuracy of the model trained labeled datasets of sizes 10, 20, 40, and 10, 000 with varying amounts of unlabeled data from the same distribution with a = (left), and different distribution with 0o0l| (right).
Same distribution
Different distribution
Labeled size
Acc
Unlabeled size
Acc
Labeled size
Acc
Unlabeled size
Acc
10
0.63
10
0.61
10
0.59
100
0.66
10
0.59
100
0.65
1,000
0.79
1,000
0.78
10,000
0.82
10,000
0.81
20
0.64
20
0.65
0.62
200
0.69
20
0.62
200
0.65
2,000
0.80
2,000
0.79
10,000
0.82
10,000
0.80
40
0.65
40
0.65
40
0.65
400
0.71
40
0.65
400
0.73
4,000
0.81
4,000
0.78
10,000
0.82
10,000
0.80
10,000
0.83
10,000
0.83
Proof can be found in Appendix. One important difference to note between Theorem and Theorem is the choice 7', which controls the adversarial budget for unlabeled (and oft-of-domain) part of the dataset. In the setting of (..2 we prefer to choose 7 as small as possible. However, in eigenvalues of Σ, and Eg, as well as
the setting of Theorem 44.4 we consider the eigenvectors the direction of μ4 and μo in order to find the optimal value for the adversarial budget. In fact, there are cases in which selecting a large 7 (less freedom for the adversary) may actually be the optimal choice.
EXPRIMENTAL RESULTS
The effectiveness of the proposed method has been assessed through experimenting various datasets, including simulated data, and real-world datasets of histopathology images. Each experiment has been divided into two parts: i) cases in which both labeled and unlabeled data sampled from the same distribution, and ii) the scenarios where the unlabeled data differs in distribution from the labeled ones. First, let specify the datasets used in experiments:
Simulated data consists of binary-labeled data points with dimension of 2000 generated according to the setting described in Section 2
2. NCT-CRC-HE-LOUK consists of 100,000 histopathology images of colon tissue (Katherm et al. 2018). The images have dimensions of 224 x 224 and were captured at 20x magnifi- cation. The dataset is labeled with distinct classes
3. PatchCamelyon is a widely used benchmark dataset for medical image analysis. It consists large collection of 327,680 color histopathology images from lymph node, each with dimensions 96 x 96. The dataset has binary labels for presence/absence of metastatic tissue.
5.1 EXPERIMENT OF SIMULATED DATA
To evaluate the effectiveness of our method on simulated data, we first find the optimal classifier using only labeled samples. Then, we apply our method with varying number of unlabeled samples. The results (see Table show that our proposed method achieves accuracy improvements comparable to models trained only on labeled samples. Moreover, results indicate that our method is effective when labeled and unlabeled data come from the same distribution. However, still demonstrates significant improvement even when the unlabeled samples undergo distribution shift.
8

---

Published as a conference paper at ICLR 2024
Table 2:
Accuracy of the model trained labeled data from NCT-CRC-HE-1ON 100K dataset with varying amounts of unlabeled data from the same distribution (left), as well as when unlabeled samples come from a different distribution (PatchCamelyon (rigse)
Same distribution
Different distribution
Labeled size
Acc
Unlabeled size
Acc
Labeled size
Acc
Unlabeled size
Acc
200
0.71
100
0.78
48
0.65
700
0,80
25
0.78
400
0.79
2,000
0.82
2,000
0.81
500
0.78
200
0.82
240
0.77
1,200
0.82
50
0.82
700
0.86
4,000
0.83
3,000
0.87
3,000
0.87
600
0.88
1040
0.83
10,000
0.89
300
0.87
2,000
0.89
20,000
0.91
8,000
0.90
50,000
0.916
32,000
0.94
5.2
EXPERIMENT OF HISTOPATHOLOGY DATA
The processing pipeline over the real-world dataset of histopathology images is based on using ResNet50 encoder pre-trained on ImageNet (Deng et al. 20099 He et al. (0166, which extracts and stores x 1024 embeddings from input images. Such embeddings are then used to train deep neural network with four layers of size 2048 and one output layer for the class id. Also, we have used LeakyReLU activation function.
Experimental results in this part are shown in Table 2 Under the "same distribution" setting, both labeled and unlabeled data have been taken from the NCT-CRC-HE- 100K dataset. On the other hand, dataset
"different distributions" setting implies that labeled data comes from the NCT-CRC-HE-II (labels are either "Normal" or "Tumor"), while the PatchCamelyon dataset was used for the unlabeled data. As result, the final labeling binary. The experimental results demonstrate that increasing the number of unlabeled data leads to an improvement in accuracy for both the 'same" and 'different' distribution settings.
CONCLUSION
In this study, address the robust and non-robust classification challenges with limited labeled dataset and a larger collection of unlabeled samples, assuming slight perturbation in the distribution of unlabeled data. We present the first non-asymptotic tradeoff between labeled (m) and unlabeled (n) sample sizes when learning two-component Gaussian mixture model. Our analysis reveals that when n 2 Ω (m²/u0 /d), the generalization bound improves compared using only labeled data, even when unlabeled data points are slightly out-of-domain. We derive sophisticated results for the generalization error in both robust and non-robust scenarios, employing technique based on optimizing robust loss and regularization to avoid crowded and dense areas. Our framework integrates tools from self-training, distributionally robust learning, and optimal transport.
Experiments synthetic and real-world datasets validate our theoretical findings, demonstrating improved classification aceuracy, even for non-Gaussian cases, by incorporating out-of-domain unlabeled samples. Our methodology hinges leveraging such data to enhance robust accuracy and adapting the uncertainty neighborhood radius based on labeled and unlabeled sample quantities to strike balance between bias and variance in classification error.
For future work, there's 's room for improving and relaxing the conditions for the utility of unlabeled data. Exploring error lower-bounds and impossibility results presents another intriguing avenue. Additionally, relaxing the constraints on the level of distribution shift for out-of-domain samples could be promising direction.

---

Published as a conference paper at ICLR 2024
REFERENCES
Jean-Baptiste Alayrac, Jonathan Uesato, Po-Sen Huang, Alhussein Fawzi, Robert Stanforth, and Pushmeet Kohli. Are labels required for improving adversarial robustness? Advances Neural Information Processing Systems, 32, 2019.
Massih- Amini and Patrick Gallinari. Semi-supervised logistic regression. In ECAL, volume pp. 11, 2002.
Hassan Ashtiani, Shai Bav-David, Nicholas Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Nearly tight sample complexity bounds for learning mixtures of gaussians via sample compression schemes. Advances in Neural Information Processing Systems, 31, 2018.
J. Linmans B. S. Veeling, J. Winkens, T. Cohen, and M. Welling. Rotation equivariant cnns for digital pathology, September 2018.
Battista Biggio and Fabio Roli. Wild patterns: Ten years after the rise of adversarial machine learning. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 2154-2156, 2018.
Jose Blanchet and Yang Kang. Semi-supervised learning based distributionally robust optimization. Data Analysis and Applications 3: Computational, Classification, Financial, Statistical and Stochastic Methods, 5:1-33, 2020.
Jose Blanchet, Yang Kang. and Karthyek Murthy. Robust wasserstein profile inference and applica- tions to machine learning. Journal of Applied Probability, 56(3):830-857, 2019.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp), pp. 39-57. leee, 2017.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchi, and Percy Liang. Unlabeled data improves adversarial robustness. Advances in neural information processing systems, 32, 2019.
Richard J. Chen and Rahul G. Krishnan. Self-supervised vision transformers learn visual concepts in histopathology. CoRR, abs/2203.00585. 2022.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-255. Icee, 2009.
Zhun Deng, Linjun Zhang, Amirata Ghorbani, and James Zou. Improving adversarial robustness via unlabeled out-of-domain data. In International Conference on Artificial Intelligence and Statistics, pp. 2845-2855 PMLR, 2021.
Charlic Frogner, Sebastian Claici, Edward Chien, and Justin Solomon. Incorporating unlabeled data into distributionally robust learning. Journal of Machine Learning Research, 22((6):1-46, 2021.
Rui Gao. Finite-sample guarantees wasserstein distributionally robust optimization: Breaking the curse of dimensionality. Operations Research, 2022.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 14 2014.
Yves Grandvalet and Yoshua Bengio. Semi-supervised learning by entropy minimization. Advances in neural information processing systems, 17, 2004.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Jakob Nikolas Katherm, Halama, Niels, Marx, and Alexander. 100,000 histological images of human colorectal cancer and healthy tissue, April 2018.
10

---

Published as a conference paper at ICLR 2024
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings. 2015.
Ananya Kumar, Tengyu Ma, and Percy Liang. Understanding self-training for gradual domain adaptation. In International Conference on Machine Learning, pp. 3468-5479 PMLR, 2020.
Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii Virtual adversarial training: a regularization method for supervised and semi-supervised learning. IEEE transactions on pattern analysis and machine intelligence, 11(8):19791199,, 2018.
Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 17 171(1-2)1115-166 2018.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT Press, 2018.
Amir Najañi, Shin-ichi Maeda, Masanori Koyama, and Takeru Miyato. Robustness to adversarial perturbations in learning from incomplete data. Advances in Neural Information Processing Systems, 32, 2019.
Hongseok Namkoong and John Duchi. Variance-based regularization with convex objectives. Advances in neural information processing systems, 30, 2017.
Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 427-4344466 2015.
Philippe Rigollet. Generalization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Learning Research, 8(7), 2007.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Ad- versarially robust generalization requires more data. Advances in neural information processing systems, 31, 2018
Soroosh Shafieezadeh Abadeh, Peyman M Mohajerin Esfahani, and Daniel Kuhn. Distributionally robust logistic regression. Advances in Neural Information Processing Systems, 28, 2015.
Aman Sinha, Hongseok Namkoong, Riccardo Volpi, and John Duchi. Certifying some distributional robustness with principled adversarial training. arXiv preprint arXiv: 10571, 2017.
Matthew Staib and Stefanic Jegelka. Distributionally robust deep learning as generalization of adversarial training. In NIPS workshop on Machine Learning and Computer Security, volume pp. 4, 2017.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.
Martin J Wainwright. High- High-ddimensional statistics: non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Runtian Zhai, Tianle Cai, Di He, Chen Dan, Kun He, John Hopcroft, and Liwei Wang. Adversarially robust generalization just requires more unlabeled data, arXiv preprint /906.0900000000 2019.
A AUXILIARY DEFINITIONS
number of auxiliary definitions presented in this section:
11

---

Published as a conference paper at ICLR 2024
Definition A.1 (Wasserstein Distance). Consider two probability distributions P and Q supported on X. and assume cost function c X' x - R4 a non-negative lower semi-continuous function satisfying c(X,X) denoted as We (P, Q), is defined as
0 for all X E X. Then, the Wasserstein distance between P and Q w.r.t
We (P,Q) = inf Ex,x' (x,, X'),, subject to 1 (X,)) - P, (1 X') Q, (19) (ET(())
where I (X²) denotes the set of all couplings over X X.
Definition A.2 (e-neighborhood of Distribution). The e-neighborhood distribution is defined as the set of all distributions that have Wasserstein distance less than from P. Mathematically. it can be represented as:
- [Q W. (PQQ) Sej.
(20)
B PROOF OF THEOREMS
In this section, we present the proofs for the Theorems and Lemmas from the main manuseript.
With respect discussions from the main manuscript, we already know that gasss is the result of the following optimization problem:
Proof of Theorem 4.7
}.
gnss A arg min age
1 m
m
by ( yz: 0)
n +
Σ
py (X/, ho (X)) :0) g.
(21)
71
where we have O E IR, 110 1]. If we consider the loss function mentioned in Theorem
4.1 along with the cost functions c(X, X') = X X'Il2 and (X,,, X') || X the Slater conditions will be satisfied. Hence, we have strong duality, and therefore, there exists 2 such that gnss is also the result of the following optimization problem:
gass
arg min
m Sy (X, 0):
(22)
8: ン3 o (Xj.aa (a (x)):)))))))))))) :))
To prove the theorem, we need to establish an upper bound on the distance between the expected robust loss of jRSS and the best possible expected robust loss. To achieve this, we first provide a concentration bound for the maximum distance between the empirical and expected robust loss across all parameters with
72 Di (X ho :x < s,
(23)
and then, demonstrate that the parameter 8", which achieves the best possible robust loss, satisfies equation 23 Suppose that the loss function is bounded with b, i.c.,
I ((X, y: 0) < b, X, y d (X, y: b, Vc, 7, 0, X
where the second inequality directly results from the first one. Therefore, 1 = By (X,, De; 0) has the bounded difference property with parameter b/ m, which results that
Φ X. yr: 0) Ero 10S (X, v001
+ So. = =sup #Eô
(24)
m
1=1
also has the bounded difference property with parameter b/m, where Ô is defined as
θ
0
Qy (X) he (x)) 0) S 1101| =
(25)
==1
12

---

Published as a conference paper at ICLR 2024
So, we have the following inequality with probability more than 1-d. 8:
+ (Po. Su. y, c) I E [ Su. 7, + log 1/5
AB é.
(26)
m
In the above inequality inequality as follows:
give upper- upper-bound bound for the first term in the right hand side of the
1
E Φ (Po, So. c.c]] =Eso>Po Pm
sup OEô
Σ
X
Vb:
Ep, [0g (0: X, y)]
m 1=1
sup %0.5%
1
Σ
m
1 m
Φ (X; v/:
m i=1
m i=1
1
$2Bsp.e
sup 0E m (X..))S8
Σ
G09 (0; X, 34)
(27)
Consider the loss function mentioned the Theorem 4.1 and the following cost functions c,
c xX)
X112,
d c(x,'') = | - 1
With these loss and cost functions can rewrite of, and oz as follows:
$ X y: 0) min {1, max {0, Tu(o, X X}),
(28)
XX ho X 0) = max {0. - 7 x0, )
(29)
As we can see Φ (X, y; 0) is a 7-lipschitz function (0, X). Based on the Talagrand's contraction lemma, we can continue the inequalities in equation as
T (P+ 0, So, (,,Y,,) E.s.
sup MEG m (X.
Σ
GØG (X,, yes 0)
Sn.S.a.
sup
(0,
BE m
(X..:))S.
Sy.ss..
inf sup {>0 PEO m (8
Σ
600 Xi)
Σ
& (X;:0 + c5'
()
X/E81
SyEso..
inf sup <>0 P=
Σ
(0, +
Σ
(0, (1) C(1 (1-
(X..))).
X(ESi
=>/Bsa.
inf sup (0, <20 aEe
1 Σ e.xX +5-/0"
Σ
X
0 0- 51 s)
x.ES.
X
(30)
1 Σ x,e C// X and E ( Ex X(X:T). and then continue the inequali-
Let us set v ties in equation as as
[ + 0, So, 7, SyE. E
inf sup (0, +)+ - <(1 s)) (>00ee
(31)
In order to find proper bpper- for the Rademacher complexxty. we attempt to solve the inner maximization problem
sup (0, v) Σ.0
(32)
#
We know that the parameter 0 which maximizes the first term (0, v) is vector with Euclidean norm of 1 in the direction of v. Also, the parameter which maximizes the second term 0 $0 is vector
13

---

Published as a conference paper at ICLR 2024
with norm 1 in the direction of maxx which is the eigenvector of Σ that corresponds to the maximum eigenvalue Amax- Therefore, the solution to the maximization problem equation 32 should belong to the span of and max: i.e.
0 11 |
+
2/2
Mmxxx
Umax
1 ② + 2 Nydimax
(33)
where:
w7 + 22 + 24/12221 = 1,
"1 (t) úmax).
A v
(Ü, umax)
T E"E
(34)
7'
Due to equation 32 equation
33 and equation 34 have the following problem:
sup 1/1 ||11|| 2 + #277
(35)
S.t. v + 2 + 2 2/2 =
$ Amax
w + 2 Amxx11 2 5
The constraints in the above problem can be rewritten
2 + 122 + 2 2/2!1 = 1,
(36)
Amax v (Amax -T) -'s
In the above equations, if we set s' = Amax. then the only 111 which satisfies the constraint is d 0. Suppose that we use set of n i.i.d. samples from PIx (which is different from the S1) estimate the Amax, and name this estimate Åmax- we set
(Va
log 8
Amax a)) 30 30
(1-
(37)
form Theorem 6,5 in Wainwright (019) we have the following relation with probability more than
1 8:
d
log( Ss' Amax (1 - aa) O
d
log(
Amax (1 a) -5
(38)
n
By weakening the constraint in equation means by solving the following optimization problem we have an upper-bound for equation 35
35 the result of the optimization becomes larger, which
sup 1 ||0||| 122..
S.t. / + 2 2//1
log(? z
? (Amax r) S aex + 50
n
where for the Gaussian distribution and the way á built we have:
oz Moo + ozd
| 333
Amax - - || In this regard, the results of optimization problems equation 39 and equation 32 have the following upper-bound:
x²
(40)
||ll2 X
admax + +5
(50(1
1
log(?)
11 Ex.s, e, Xille
admax + 50
log(
71
X
(41)
14

---

Published as a conference paper at ICLR 2024
This way, also have upper-bound for Rademacher complexity in equation 27
Se.so [|| Ex.es c e112
log (
E 1 (P 0, So. c, s
admax +50
X
Ex
X
(v
d +
log(?)
admax + 50
(42)
XVm
n2
where for the Gaussian distribution have:
axxaax 50 (v/
| 2 +
ofd
v/l +
log($)
④ (P+0. Su. r,,)] 5
X m
n
o M 12
+
d +
log(?
(
SY
Xmx + +0
n
m
oF Tigill
1+
log
d
admax + V d
(43)
m
n
Using equation 24 equation 26 and equation 43
we have
d
log
log 1/5
ppm [o, (X, yi 0)] Err Loc (X, yr 0/
50
(1
admmax +
V
+
(44)
for all 0 Ô where θ is defined as in equation 25 Now, we need to demonstrate that the parameter 8" that minimizes the expected robust loss also satisfies the constraint defined in equation 23 Given the data generating distribution in here, we know that 0 also minimizes the expected non-robust loss. Therefore, we have
f arg min Ep, [[XX, u: 0)).
(45)
PE
where for the loss function, cost functions and distributions considered in here we have:
0"
arg min
-~ (0-0((100)))0000000) (u S 0)
8eB
(0, |2
arg min Q
02 0
lEB
Mg
(46)
|oll2
In the setting of the Theorem, also have:
|| lal 1|2 S a.
Due to the Auxiliary Lemma 2 know that if we set
(v
(1- (A
s 3=1->"
(47)
max log n + O(
then with high probability 0r E Ô and the following holds:
E po (5, (x, y; ORSS)
< E (( [05 x, (Ass)]
15

---

Published as a conference paper at ICLR 2024
d
log 2o
log 1/6
+0
admax + V +
+
m
$
B
(i) (0 (X, 1xx, :2:0))
d
log 8
log 1/6
+0
7
axmaax +
+
+
m
S
Exx [0G (X, y; [²
d m
admax + v/
log n
log 1/8 m
+0
(48)
Now, let's consider scenario where we split our labeled samples into two parts, each containing m/2 samples. We then ignore the labels of the second part and add these samples to the unlabeled set. In this situation, we have m//2 labeled samples and m/2 unlabeled samples and the bound above inequalities changes as follows:
E w/oo (0 (x @RSS)]
((x.))) [og (X, 8: 0*)
2d
2d
log
2 log 1/8
+0
7
axmmax +
V 2n + m
+
m
2n + m
m
(49)
which completes the proof.
Proof of Theorem 4.2
Using Theorem 4.1 and Auxiliary Lemma !
with probability more than
we have:
R @RSS
Po
E [X P) (0s X x y; BRSS)]
2d
2d + 2
2 log 1/8 m
E (x [og (X, y: 0*) +0
7
admax +
m
2n + m
zng
2d
2d + 2 log /
2 log 1/8 m (50)
s R (O,,, Po) +
+0
7
admax +
V
27 2youV/T 2
m
2n + m
For the setting described in the statement of the theorem, we know that l" = Huu and 7max S
|| 11 + of +
By setting
n
-1/4
Amax 4n
2d admax +
2d 2 2og 2n + m
log 1/8
2200v2r
and subsequent substitution in equation 50 one has
R Rss Po < (O
12lli e
40
2d +
2d
2d log
2 log 1/8
+
(111112 + +of)
(51)
2200222
2n + m
16

---

Published as a conference paper at ICLR 2024
Proof of Corollary 4.3
Due to the result of Theorem
4.2
to have an advantage the ERM method
we should have:
2dx
2d
2d
(52)
m
m
2n +
m
we have the following inequality can be seen that the above inequality will be satisfied:
m d
α S m
n
(53)
It can be seen that if we have S O (2) and >> Ω (d)),
then with high prohability we have
ep nnss)
log d
0
(54)
m
m
Therefore we aim to have an excess risk less than we should have at least max { samples which is independent from the dimension of data.
log 4
ck 2
Proof of theorem 4.4 From the manuscript we know that QRSS is the result of the following opti- mization problem:
gass A arg min BE0
1
U:: 0) + Σ By (X), ha (Xj) 0)
(55)
m
where we have θ A {0 Rdd ||0| 1). Like the proof of Theorem 4.1 if consider the loss function mentioned in Theorem 4.1 along with the cost functions c(X,X') X X'I1 and o' c'x = || X 2. the Slater conditions will be satisfied. Hence, we have strong duality, and therefore, there exists 2 0 such that jitss is also the result of the following optimization problem:
RSSS
arg min
1
Σ Φy (X V):
m
(56)
0: 0: ΣE d hx (x)):0)
m
To prove the theorem, we need to establish an upper bound on the distance between the expected robust loss of gRSs and the best possible expected robust loss. To achieve this, we first provide concentration bound for the maximum distance between the empirical and expected robust loss across all parameters with
Soe' (Xz, ha :x <
(57)
and then, we demonstrate that the parameter 8", which achieves the best possible robust loss, satisfies equation 57 Suppose that the loss function is bounded with b,
1 1(X yz 0) < b, V0, X, σ9 (x. yj
Vc, 0, X.y.
where the second inequality results from the first one. Therefore, m Σm By (X By: 0) has the bounded difference property with parameter b/m, which results that
+ So. r) sup eeê
1 m m
Σ
by
(Ki, 0)
Epo (09 (X, y1 v111
(58)
also has the bounded difference property with parameter b/m, where θ is defined as
θ
0
Q4
(X) he (X)) :0 S 110112 =
(59)
==1
17

---

Published as a conference paper at ICLR 2024
So, we have the following inequality with probability more than - 8:
+ (oo So, 7, c) I E + (Po. So, 7, + log 1/6
4A E é.
(60)
In the above inequality we can give an upper- inequality follows:
soper-bound bound for the first term in the right hand side of the
E 4 (Po. So. 7.c) -Eso-Po Pr
sup OE
[ Us: 0)
Ep [0 (0: (.xX.,) w0]
1=1
<.s
sup
(X 01:
Φ (X y/:
AE
i=1
==
1
<2Bsp.
sup 8E6 m
E, (0; X Vi)
(61)
(XAM))S
Consider the loss function mentioned in the Theorem 4.4 and the following cost functions c,
c(x = | 12,
c(X,X') X x
With these loss and cost functions we can rewrite of and o as follows:
S X 8) = min {1, max {0, (u(0, X)
(62)
X he ()) = max {0, - (0, x
(63)
As we can see o (X, y/ 0) --liiscciiz function of y( X), therefore due to the Talagrand's lemma continue inequalities in equation 61 as follows:
E Φ (P So 7, c) SEs.
sup Σ OEó
G (X, 11::0
(X,M))
< ByBs
sup 6
Σ
(0,
(X,i))Ss
SyBso.e
sup (8, m X,ES,
Σ -y:X,)
(64)
Now suppose that we weaken the constraint in the above inequalities as follows:
th (X/, he (x)): :)
==1
(o (X, v1 0)]
47 (Tr (Et) || 12)
log x
> Eix.o P.x.0
(65)
Vn
4e 20 2
47 (Tr (Et) + 1111)
log
(66)
3
Vn
where we use Auxiliary Lemma Suppose that we set follows:
in the equation
65 and Auxiliary Lemma
4 in the equation
66
inf Σ S (X,, ho (X) 12 Tr (S() AE0
log
+ 31
n + 16 + (67)
vn
X.ES
where in the above equation S is generated in way but independent of S,, and Σ ($1) is the sample covariance matrix S.. Therefore we have the following upper-bound for s:
of (X,, he (X) 12 Tr (5) ($( + +31
1 Σ X,EX
log 1 z
d +
= inf lee
31
+ 16
Vn
18

---

Published as a conference paper at ICLR 2024
O (X, ho (X)): + 24' (Tr (Ir(E)) -111111))
log à
d
< inf AEB
Exxx
+ 61
+
32
+ a
vn
n
n
(68)
(2 219
4e
24/ (Tr(Ei) + 11110111 11))
log
d
< inf
+ 61
+ 32
+
7
VT
g Au
4e
24' (Zn) + 141113]
log 32
61
321
+
(69)
n
where in the equation 68 use the result of Auxiliary Lemma
In the equation 69 insert
0 ET Wn which minimizes 20 21
We use equation 65 to equation 69 to define o.. which is
a super-set for θ as follows:
4e 2 m
4e S
247/ (Tr (Ex) + 11 (2) 61
log + 32 +
OEO:
3/7
3/7
Vn
10 11)
E ::
2 pb Ei pM
1'
1 m1 (187²2 (Tr (E1) + 11
+ 5n' V log 2/2 + 24v + 400
2/n2
0 ( M1 D pn
(0. 21)²
gTE6 I
m
118/22 (Tr (En) + || l12) + 5y v log 1 + 24vd + 4ayny
(70)
2/n
We can write EΣ +eullaaa where a vector which its Euclidean norm is equal to and belongs to the hyperplane orthogonal to ΣT #1, and e E I.. If we use this new notation we can rewrite O. as follows:
Σ M1
Padl ) o stt o oZ μ1 o, 11110112 110012-13 =1}
: E3 nf'r, un
|Σ M1 + eull2
(71)
118//2 (Er(Ei) + || + +5y /log 1 + +4v/ + 4ayn7
(72)
2/n
where due to Auxiliary Lemma 7 we have:
T Σ1
1 1
(
(73)
/ Σ 11
dx
where
K1 Amia (En) Nij Amax EΣn
Xmax (Σ1)
(Σn)
A min {}1 (Ez) A, (Et)), Vi,j (E) (E.)
Therefore weaken θ.. as follows:
θ.. 0 Σ 14 ev
: 11, o pn = 0, ||00|| = =1} =
(74)
||Σ #1 + ccul22
19

---

Published as a conference paper at ICLR 2024
M m1 (187/2 (Tr (Ei) + | (22)
5y'
log 3 + 24Vd 4a
- (En)
(75)
2/n
Due to the definition of .. in 74 and the fact that it is super-set for è we can continue equation 64 follows:
E E (P 0, So: 7,c)] So.o
sup (0,
Σ
eiyiXi)
AE6
m
X,ESO
sup (0,
EiliXii
ME@
X
mmax (En) E |||
Eyy'
m mal1p1ll 111122 ll2
(1111133 + Tr (E²)) Amax (E-1)
Ent'
(76)
ml m11
Using Inequalities equation 76 and
and equation 60 we have:
m
(11eg Tr (Σn)) Amax (Ez)
log
by (X, yi; Er [ (x, 0]
S 5/l
ml1
m
(77)
Suppose that we define 0" as follows:
arg min Ep, [ (X, 0)].
(78)
dE
For the loss function, cost functions and distributions considered in the Theorem 4.4 have:
8" arg min P. Ww-N((PP (u S 0)
dee
(0, 10)2
arg min Q dEe
ET
Eg 140
(79)
1 1ol12
In the setting of the theorem, also have:
[|100 mill2 S a, |Σ - Eolla S
Due to the Lemma 6 we know that if set and 7 as
12 Tr (SS)
inf 1 PEe X,EX
log 1/
d
Σ
o (X,, ho (X)
+ +
16
ta
vn
n
/ -2c 2 (A (S(S:))
(80)
then with high probability 0- O and have the following:
Ero (5 X y; @RSS)
)]
< Ero [0S, [X,v0")] + g6'
(11 12 + Tr (E1)) Amax (E1)
log
m mallma1
(81)
Using the result of Auxiliary Lemma 5 and the above inequality we have:
10" 40
P(x [xx gass)
(x (XX 0]
e
29 No0r
2
20

---

Published as a conference paper at ICLR 2024
pl 11 Tr (r(E)) Amax (Ez)
log 8
tyl
+
(82)
m m1l111l ll
m
Therefore if we set as follows:
m
(83)
21 Xmax
[1 (S))
then have:
[ x @ASS)]
E P(xx))P
S ( (xx, y; 0)
Amax
(E1) je ll
log 3
+
(84)
Now, if we split our labeled samples into equal parts, each containing m/2 samples, and combine the unlaheled set with the second part, we have m/2 labeled samples and n + m/2 unlaheled samples. When we set t' from equation 75 in this new scenario, the proof will be complete.
C AUXILIARY LEMMAS
Auxiliary Lemma 1. Consider the setting described in Theorem 4.1 let us define fe, (0, 7)
Se.P (0,7) 7) = (x [&S (X, 0) E xx [e (X yū 0)]
v)~
(85)
Then, for the loss and cost functions described in Theorem 4. P Nyu.o (X,y). v). and the class of linear classifiers with 10|2 1, the function fe, (0, 7) satisfies the following inequality:
25
Se.r (0,7) S
(86)
2
Proof. For the setting described in the lemma we have:
u == (0 X) ~ N (10, (2,
(87)
Therefore calculate upper-bound for fe, (0, 7) as follows:
1/7
(0.)))
Ex (09 (X 0) Exxw>~ (X
(1 --y))
du
V2T0²
u=u
1/7
10
(1 771)
20
du
V2T0²
==U
(88)
27 2T
And the proof is complete.
Auxiliary Lemma 2. Consider the setting in Theorem
4.1
we define 0* as follows:
0- 44
(89)
|
then with high probability we have:
Σ j=1
Φv (X), he (x)); ;0) ss,
n1
As long we set:
8= 1-7' (Amax
(1 (Smax(11
a (30
(90)
Amx log n + (
21

---

Published as a conference paper at ICLR 2024
Proof. Due to the boundedness of of with probability more than 8 have the following inequality:
oy (X), ha- (X)):0) SEx~Pix [o (x, ho- (x); + log x
(91)
X
log !
=Ex -ixxPix
max (0",-- +
(92)
where we have the following upper-bound for the first term in 92
Ex~Pix [max {0, 1 -0----a (0','''0 = EXxxPx
[1 (1-7% -0- x
1 1 x)² dPix
10- 10-xx)227
ExxPix
[1 (1",
1
1 1' (0" x N (1I,
2 (0)22) xx)27
1
1 1 7 x)² N N (-H1,0ū1)
2 10+ (1-,2)22
EXxxPxx
11-1(00, x
1 1
7 -
(10", + tou N (0,
[0
1- (- +1) = N (0,
I + (0))))) "IV55
(93)
Now if we
1
A' Mi) a vlogni)
(94)
we can continue inequalities in 93 as follows:
Ex~Pix maxx| {0, - 70000 xx <Ex~Pxx (1)) + vn
1
=1 - y 1000,,1)2220
of) + Vn"
(95)
However, since we lack access to μl, d1, 8", cannot directly obtain 7 from equation 94 Nevertheless, a suitable choice for 7 that satisfies equation 94 and can determined from samples is:
(96)
Xmax log (
where Åmax is the maximum eigenvalue of the sample covariance matrix, of set of n unlabeled samples. Now from Equations 91 and 95 we have:
log 1
Σ Φ. (X 1=1
ho (xx) :))
()) $ 7 (10", .1i² + of) + 2
(97)
To complete the proof we should show that
log
1 - 7/ (10", 21) + of) + 2
< 8,
(98)
n
22

---

Published as a conference paper at ICLR 2024
where due to the setting of this lemma only need to set:
8 = 1 -777 (Amax (1 11-01 -a- -3 30
(99)
Auxiliary Lemma 3. Consider the setting described in Theorem 4.4 if we define the function o as follows
S (X, ho (X); ;) = max {0, (),
(100)
then with probability greater than 1 - 8, for A0 E θ, with |10|2 = 1 we have:
4/ (Tr + (1l3)
log 1
o (X,, ho (X.):
E of (X, he (x):
+
vn
n
(101)
Proof. From the definition of oG we know that this function is bounded between 0 and 1, therefore the following function has the bounded difference property with parameter
+ = sup A
(X ho (X, :0 - E o X ho (X) (x)
(102)
So can write the McDiarmid's inequality for this function as follows:
log
+ < E
[
+
(103)
Now try give upper-bound for the first term in the right-hand side of the above inequality:
E [ [x,
sup OEB
Xi ha :))
E
S (x, ho (x)
im1
< (x,)
sup
1 n 7
Bef (X,, ho (
(X ho (X:); |8
AE
i=1
i=
< (Pxx
sup 6i BEN
X ho (X.) ;)
D (x' ho (X :))
1=1
(104)
<2E (2E(x));-(4)
sup OEG
6 (Xi, hg :)
(0, X,)²
sup
0E0 12
1=1
-2.
sup T AE
xX
1=1
<27/E, (x,
Amax
Σ xX,'7
i=1
1 n [
)
n
'29'
B(x:)1
Tr
12
'29'
B(x,Hr
1
Σ
23

---

Published as a conference paper at ICLR 2024
2 Ex [||
47 (Tr (Ei) M 12)
(105)
where e, in equation are Rademacher's ' random variables, and the last inequality in equation 105 is results from the fact that X,s are sampled from distribution P1 defined in Theorem 4.4 of the manuscript. And the prood is complete.
Auxiliary Lemma 4, Consider the setting described in Theorem 4.4 if we define the function o as follows
ho () max {0,1 7 x)
(106)
then we have the following upper-bound and lower-bound for the expected value of oe when X sampled from the distribution Pi defined in Theorem of the manuscript:
10.pe12 2 4e
(0
26 2
1
S E 0g. (X, he (x):
4e
20 E,
11 (1+
3v4
V78TE,
3/7
v VOOTE Σ,
(107)
Proof. For the expected value of o we can write:
E
pg (X, ho (x);0) max {0, 1- 10,
1 1- (MI,
210 V7
(0,1))
V
Ver
1- V ( 0TE,
N (0. (108)
V
VerE,
Where we have the following upper-bound for the expected value of >> (p11))
E
p X ho
(X):0)
4
(0, H1)
3/7
V/OTE,0
(9 26
(109)
3V7
(0, m1)²
Now without loss of generality we assume that the largest eigenvalue Σ₁ is less than or equal to then we have the following lower-bound if 7
10.1) de
2o 3ig0
E Q [X,
hg (x);
3
(0.
20 EL
(110)
3/7
Auxiliary Lemma 5. Consider any distribution P, loss function é, transportation cost and 0 E O
let us define fe.P (0, 7) as
fe, (0, 7) [x 169, (X, y5 0 - (Exx.))~ [e (x,1;)
(111)
Then, for the loss and cost functions described in Section 4, P = Po. where Po described in Theorem 4.4 in the manuscript, and the class of linear classifiers with |6] 1, the function fe.p (0,y) satisfies the following inequality:
19 (0.
fe.p (0,7) <
e
(112)
2
24

---

Published as a conference paper at ICLR 2024
Proof. For the setting described in the lemma we have:
u =0 x) ~ N ((0, uo); 0 Eo0).
(113)
Therefore we can calculate upper-bound for fe, (0, 7) as follows:
1/7
1
[u- (n
w) [o yx.y0)) - -E(x,))~ (X, yr 0)
(1 - yu)) e
(1-ry)e
20 Sp
du
u=
2 200000000
20 Eq
(114)
27
And the proof is complete.
Auxiliary Lemma 6. Consider the setting in Theorem 4.4
we define 0* as follows:
0" -
Σ
40
(115)
120
Holl2
then with high probability we have:
Σ Sy (X,, ho (X) S s,
as long as we set:
12 Tr ($(5
inf 1 Σ
log 1
d
o (X,, ho (X +
+ 2
+ 161 +
Vni
X,E
7 =2 $ Amar ({)))
(116)
Proof. To prove the lemma we first give bound for s.
12" Tr (E(()
log x
= inf DEN1 ni
Σ
of (X he (X)
+ 31
+ 16
+
Vn
n
X.ES
(X, y: 6]] + 47' (Tr (Er) + (1
log
2 inf ExIx, AEG
Qg (x,
+ a
(117)
vn
n
4e
1 و 'm
4 (Tr (Et) + ||
log +
+
a
(118)
3
n
where inequality
117 due Auxiliary Lemma
To complete the proof we give an upper-bound
for 1 5
-i=1 2
X he (*)
S (Xi, ho (X)) <xpi. ( (X, (..00')) + 4/ (Tr (Ei) +
11
13)
log
+
Vni
n
4e
4y' (Tr (E1) + 11
log n
(119)
3/7
Vn
From equation
119 and equation
118
complete the proof by setting o as follows:
2
16
26 2,
2e 14 2 m
(120)
9
where in the above inequalities we suppose that a is small enough. Suppose that we know || 2 Axaax (E1), then good choice for 7 will be:
= 2e 2 Amnr (S(ss))
(121)
25

---

Published as a conference paper at ICLR 2024
Auxiliary Lemma 7. Consider positive definite d x d matrix, E, and vector R For and vector v E RR, that we know:
||u|| 1, w² D'Σ # 0,
(122)
we have the following:
T
pipe
1 2
Amin A
(123)
Σ
d max
Proof. Suppose that we write as follows:
th + vi v8 + 2 =1
(124)
where ji is unit norm vector in the direction of μa, and j+t is unit norm vector perpendicular to μ.. If we use this new description of v we have:
1n T
vd
Σ
v
=MP Σ
j + (v.2 22/1 Amin (E)
1
1
2 min
p²"
ie, Amia (
(125)
H²
Eu'E-pp
To complete the proof we should find a lower bound for the first term in the right-hand side of the above inequality. To this aim we write fú as follows:
d
p
(126)
where u, the ith eigenvector of Σ, and X₂ its ith eigenvalue, such that S d2 S S Aa- With this new description for f we can write:
d
u4
1
Σ
at
A
a² Σ
1=1
1= X
d
I A
Σ
jzi Aj
1=1
f 0f
a A Il k d I
Σ 0 اهز
E at II II Xx) + Eij=i azaz Ilans Au
Σ a? Ilzz Av
Dij aF (): >13² 1Ixyes dn
2 a? II do
Amin A
(127)
ddmax
where in the last inequality A defined as follows:
A (Σ) min (A: >1). Vi,j x # A,
(128)
An important point the above incqualities is that, ja be in the direction of an eigenvector Σ, then ii (> - 1x j become equal to zero but that case w should be 0. The reason is that, in this situation ju and 21 "a will be in the same direction and we know that ş is perpendicular to E u. therefore we have:
) ps 2 min
Ammin A Amax
AAmiu }
Σ
(129)
4 -I
11/
and the proof is complete.
26

---

on Published as a conference paper at ICLR 2024
D EXPERIMENTS DETAILS
As mentioned in the manuscript, two different experiments were designed and implemented to demonstrate the performance of the proposed method. The codes are written using the Python programming language and the Pytorch 2.0 machine learning framework. The details of each test are explained below.
D.I EXPERIMENT ON SIMULATED DATA
D.1.1 SIMULATED DATA
The data employed in this particular section comprises two distinct classes, namely positive and negative. These classes are generated by sampling from Gaussian distributions with 200 dimensions denoted as N (j, o²1) and (-p,, o² I). respectively. The parameter is initialized randomly such that |||||
Also, for unlabeled out-of-distribution data, two different Gaussian distributions, N(,', o I) and ((-H', I), respectively, have been considered for positive and negative classes, which y = μ + a.vv where a
Lella N and a random normalized vector.
For the training and testing data, two classes, positive and negative, have been uniformly sampled in labeled and unlabeled modes. All the data taken from the main distribution (N(H, of and (--p, off)) and it consists of 10,000 samples, half of which belong to the positive class and the other half belong the negative class.
D.1.2 MODELING
linear model has been used learn these data, the purpose of which obtain optimal values for the weight vector The cost function for when labeled data is used is according to equation 130 where the objective to maximize the margin of the linear classifier.
n
habeled (z.
Σ
min (I, max (o, 1 y.ya. (w".o .x.))).
(130)
In equation 131 SyS are the feature vectors and y/s are their corresponding labels, y is regularization parameter for robust learning, w is the weight vector of the linear model, and n is the number of labeled samples.
The cost function for unlabeled samples is defined according to equation 131 where, due to the lack of access labels for these samples, we use the model's 's predictions their labels. Here too, the goal is to maximize the classifier's margin.
lunlabeled (x')
Σ min (1, max (0, 1 - 711 xx,))')))))
(131)
In the above equation 2/s are the feature vector of unlabeled samples, 7 regularization parameter for robust learning, and m is the number of unlabeled samples.
Finally, according to the proposed method, the combination of previous loss functions used as loss function of the model, when we have both labeled and unlabeled samples. We define this new loss function as follows:
hotal (I, y, x²) = ltabeled (x, v) + X.bunlaboled (x')
(132)
In all of our experiments we use Adam optimizer Kingma & Ba (2015) with regularization term (weight-decay). Considering that the param-paraeeters of the problem must have optimal value for each scenario; A random search process has been performed to find the optimum 7, 7' X, and weight-decay. Finally, we select combination of hyper-parameter that achieved the highest accuracy on a validation dataset, and we report the accuracy of our model, using these the test samples. This process is repeated for each experiment.
The details of the pprammerr values of the experiments reported for simulated data in the manuscript available in the attached file Hype papperrarameteer raweter-Siiiieieee mimul cav. cav.
27

---

Published as a conference paper at ICLR 2024
D.2 EXPERIMENT ON REAL DATA
D.2.1 DATASET
To evaluate the performance of the proposed method on real-world datasets, we selected set of histopathology data. The experiment is divided into two parts: one with labeled and unlabeled data from the same distribution, and another with labeled and unlabeled data from different distributions. The NCT-CRC-HEE-000 dataset used as the main distribution, and the PatchCamelyon dataset as the ditto--diitribttion dataset. Here some additional explanations about each of the datasets used in the experiment:
1. NCT-CRC-HE-100KS This dataset contains 100,000 non-overlapping 224x222 pixels patches that are extracted from 86 whole slide histopathology images of human colorectal cancer (CRC) and normal tissue. contains 9 different classes: Adipose (ADI), background (BACK), debris (DEB). lymphocytes (LYM), mucus (MUC), smooth muscle (MUS), nor- mal colon mucosa (NORM), cancer-associated stroma (STR), colorectal adenocarcinoma epithelium (TUM) Katherm et al. (2018).
2. Patch :amelyon: This dataset contains 327,680 patches with 96x 96 pixels from whole slide histopathology images of lymph node sections. It contains 2 different classes that show the patch is tumor normal B. S. Veeling al. (2018).
We conducted two distinct experiments to evaluate the impact of adding unlabeled data. The first experiment focused assessing the accuracy improvement by incorporating unlabeled data sampled from the same distribution as the imitial dataset. The second experiment aimed to evaluate the accuracy improvement when unlabeled data was sourced from a distribution different from the original dataset. For the experiment involving samples from the same distribution, we used the NCT-CRC-HE: 100K dataset. On the other hand, for the experiment involving out-of-domain samples, we used the PatchCamelyon dataset.
In the first experiment, where both labeled and unlabeled data are from the same distribution (NCT- CRC-HE-100K), we evaluated the performance considering the 9 classes present in the dataset. However, in the second experiment using the PatchCamelyon dataset with only two labels, we needed to align the labels with the NCT-CRC-HE-1OW dataset. For this purpose, merged the sancer-associated stroma (STR) and colorectal adenocarcinoma epithelium (TUM) classes and labeled them as "tumor", while the remaining categories were labeled as "normal".
D.2.2 MODELING
As mentioned in the manuscript, the processing pipeline involves feeding the images through pre-trained ResNet model that has been trained on the ImageNet dataset Deng et al. (2009); He et al. (2066), and the output embedding is saved for each image. In these experiments, implementation of Chen & Krishnan (2022) for ResNet50 to extract the embeddings. The stored deep neural network to perform classification. This deep network consists of four 2048 layers with LeakyReLU activation function and one layer at the end with the size of the number of classes (the input has dimension of 1024). As shown in Algorithm [T] In order to obtain the adversarial perturbed inputs based on the original input, we update the initial value of the input number of times in the direction of the gradient. Algorithm 2 shows the training flow that uses the labeled and unlabeled data. This process can be used based on whether we are in the labeled-only mode or whether we are in the labeled and unlabeled combination mode. In this way, we are in the labeled-only mode, the parts related to unlabeled samples will not be done, and the loss function will only include d;.
the
embeddings then fed
To determine the optimal values for the hyperparameters, namely the Learning rate, weight decay, X, a, 7, and 7', we employ a random search technique across their respective parameter spaces. Through this approach, we systematically explore various combinations of these hyperparameters and identify the most effective values in each experiment. Table Table3prees presents the search space for each hyperparameter used in the experiments.
The details of the hyperparameter values of the experiments reported for histopathology data in the manuscript available in the attached Sxpeeppprantteer-llsttppppattt
28

---

Published as a conference paper at ICLR 2024
Algorithm 1 Findiin the adversarial perturbed input for original input data based on gradient ascent y, 74 N,)
function
x' = xC
for step 1, ,.... N₂ do
Gradient ascent loop
p = model("' (x')
(p, y) - - - x
CE: Cross entropy loss
a/s
x' + VV
end for
return x' end function
Algorithm 2 The training loop
Require: Number of epochs Nep. Number of perturbation steps Ng, Set of hyper- pepee--prramete (7+ ni
X, Leamingg rate of perturbation a}
L (Tr, Mo), (Io: yo). ..., (ZN.
b Labeled data with size of N
U (1/p, x1 F
> Unlabeled data with the size of M
k
La the set of batches of L
batch size N/k >> batch size M/k
Ub the set of batches of U
for epoch 1, ...... Nep do
for (z,, y:), J in Ls, Us do
x ADVERSERRAL-PERTURGGYY V model(z'))
step)
1
ADVERSERIAL-PERTURRE Vyy a', step)
Pt model(
Pj model(x)))
④; CF y1) 7-11a 2:112
Φj CE v/)) - 7 11112x 1B
[ = Ø; + X.o;
backpropagate loss (!) with gradient decent to the deep net and update the weightes
end for end for
Table 3: The hyperparameter search space that we test randomly.
Hyperparameter
Search space (i N)
Description
Learning rate
{10' - 5 i -1}
lcarning rate for adam optimizer
Weight decay
{10' < -2)
regularization term for adam optimizer
X
{10' 5<i<2]
coefficient of the unlabeled term in loss function learning rate for adversarial perturbation function coefficient of norm term in labeled loss function coefficient of norm term unlabeled loss function
a
[10 5
7
[10 7
?
100 7
29


Reviews:
[{"review_id": "J2Kdhv4uVb", "reviewer": "Reviewer_TZRA", "summary": "The paper aims to utilize unlabeled samples from a perturbed distribution to improve the generalization error in both adversarially robust and non-robust settings. It introduces a new algorithm that leverages adversarially robust optimization and self-supervised learning. Subsequently, by focusing on the linear Gaussian mixture model, the paper shows that the use of unlabeled samples can lead to an improvement in error rates compared to traditional ERM, which does not make use of unlabeled samples.", "questions": "When n=0, no out-of-domain samples are utilized and the problem reduces to simple ERM. But in Theorem 4.2, when n=0, the dependence of the error on dimension is d^{3/8}, meaning that this reduction in the exponent of the dimension is not related to the utilization of out-of-domain samples. Furthermore, in the case of n=0, why is the non-robust error better than error obtained through ERM?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper analyzes the generalization error of the newly introduced algorithm, which utilizes self-supervised learning and adversarially robust optimization, demonstrating an improvement in error compared to traditional ERM.\n\n- It provides experimental results corroborating their theoretical findings that unlabeled samples from a perturbed distribution can reduce the test error.", "weaknesses": "- The paper's linear Gaussian mixture model is very restrictive.\n\n- The manuscript dedicates a substantial portion to discussing established definitions and findings in the literature. In contrast, the final three pages primarily center on discussing the paper's contributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2tdlOQcC4S", "reviewer": "Reviewer_v7JJ", "summary": "The advantage of unlabeled data in coming up with sample-efficient robust classifiers is well known and most studied in the canonical case of classifying a mixture of Gaussian models. Prior works that analyze the tradeoff between labeled and unlabeled data for robust classifiers consider robustness w.r.t. perturbing inputs, in other words, adversarial robustness; while this paper views robustness as obtaining unlabeled data from a perturbed distribution in a Wasserstein ball of some radius, commonly known as being 'distributionally robust'. The authors propose an algorithm that adds a regularizer to the conventional ERM loss function and obtain sample complexity bounds for this algorithm to obtain PAC-optimal linear classifiers for classifying a mixture of Gaussian models. The regularization term is derived from the computing a 'robust loss' on the unlabeled data using labels obtained from a model that is trained on the labeled data. The robust loss is taken from the dual form of the distributionally robust optimization problem, Experimental results on both real and simulated data show that using a large amount of unlabeled data almost achieves the performance of the optimal classifier.", "questions": "1) There are multiple anomalies that are unexplained in the experiments. Perhaps addressing that would make the results less surprising. Few examples: i) In the simulated data, it would helpful to know roughly the least number of labeled samples required to obtain the same accuracy as the optimal. ii) In the real dataset case, the different distribution case achieves higher accuracy for fewer labeled samples. It is not clear why this column shouldn't be the same or worse as the same distribution case since it is using only the labeled samples that are drawn both from the NCT-CRC-HE-100K dataset? \n2) It should be possible to empirically verify the dimension dependence? \n3) On Pg5, what is \"crowded areas\"? This notion makes an appearance in the conclusion as well, but there is no explanation about what this is? \n4) In Theorem 4.1, why is the expectation only w.r.t P_0 since we also get unlabeled samples from P_1. If this is included in the high probability statement, then that seems strange because I would assume the algorithm randomness to be separately considered from the unlabeled dataset randomness. \n5) Is there any intuition for why the error in robust loss increases with \\gamma? \n6) Minor comment: I found the notation in (1), \\hat{R}(\\theta, S) confusing and also not used later (unless in the proofs). Isn't this just R(\\theta, \\hat{P}^{m}_S) ?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "While multiple works have proposed algorithms that show the advantage of unlabeled data for obtaining robust classifiers with high accuracy, this paper's contribution lies in providing an algorithm for the distributionally robust framework that has theoretical guarantees for the linear classification for the Gaussian mixture model case. The latter has also been studied in other robustness frameworks thus highlighting the significance of studying it in a different robustness setting. The algorithm seems quite natural since the robust loss has been considered in prior works. While I haven't thoroughly verified the correctness of the proofs, the theorems seem reasonable. The paper is well-written and clear barring a few exceptions.", "weaknesses": "A few correctable weaknesses follow that could help strengthen the paper: \n1) The comparison with related works isn't thorough in the sense that the paper mentions these related works but doesn't provide any comparison of their current work with it. For e.g. the paper doesn't mention that the works of Carlini et al, Carmon et. al. etc. were for the adversarial robustness setting. It would make the contributions stand out more clearly if there is precise comparison as to how earlier work is different from the current. \n2) The experimental results could be more systematic and require more explanation. Please see the following sections for specific questions that can help strengthen this part. \n3) A few minor clarifications are required in the theoretical section. I have elaborated in the following section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CVi35Ai47Y", "reviewer": "Reviewer_Nric", "summary": "The authors propose a robust learning approach that leverages slightly out-of-domain unlabeled observations to improve generalization performance. Both theoretical and empirical analysis of the method are provided. The approach leverages a robust learning objective and minimizes this objective on a combination of labeled data and pseudo-labeled out-of-domain data. This approach forces the decision boundary to avoid crowded areas of the input space.", "questions": "Can the authors add more details about the nature of their bounds in the main text to either confirm or soften claims of novel methodology?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The method pushes the classifier to avoid crowded areas, which is similar in spirit to large margin methods. Making use of unlabeled data seems to improve its ability to do this. The analysis provides a novel non-asymptotic learning bound for Gaussian Mixtures. The method also has well motivated controls for dialing in the bias-variance trade-off.", "weaknesses": "How does this method compare against large-margin based methods? What if one treats the \"slightly out-of-distribution\" data as in distribution? Some comparison with similar approaches is warranted. \n\n\"given\" is misspelled in the abstract.\n\nWhile I did not work through all the details, the \"new set\" of bounds appear to be based heavily on an upper bound of the Rademacher complexity. I feel this really ought to be stated in the abstract and main body of the paper. I don't think that comparing Rademacher complexity with VC dimension based bounds is really an advancement. \n\nWhy doesn't the amount of \"slightly out of domain\" enter into the bound $n>\\Omega(\\frac{m^2}{d})$? Certainly data from totally different domains wouldn't improve generalization, right?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2N2qmhU0YW", "reviewer": "Reviewer_w3Ke", "summary": "The paper proposes techniques for semi-supervised learning using distributional robust optimization and self-training. In addition, the methods proposed can utilize unlabeled samples that come from a different (but similar) underlying distribution. The paper also describes theoretical results that show generalization bounds in situations where the data follows Gaussian distributions.", "questions": "Utilizing bounds as those in (8) does not seem very meaningful for the case of linear classifiers for which a bound based on the norm of the parameters (Rademacher complexity) would be tighter. Is that the case?\n\nAfter (6), “Hilbert space of constrained probability measures\" is a typo?\n\nThe usage of the word self-supervision can be misleading since the methods proposed utilize techniques that obtain pseudo-labels for unsupervised samples that are usually referred to as \"self-training.\"", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The research topic is very relevant since the usage robust learning methods can facilitate the usage of unsupervised samples. In addition, the usage of unsupervised samples corresponding with a different distribution is also of interest and common in practice. Also, the development of theoretical guarantees in these settings is very relevant", "weaknesses": "The paper's contributions are not clear. Firstly, there are several methods for semi-supervision based on DRO [Najafi et al., 2019], [R1], [R2]. The methodological contributions in the submitted paper with respect to those works are unclear. The usage of unsupervised samples from a different distribution seems novel in this topic, but the distribution shift assumed in the paper seems too simplistic and straightforward to address by DRO methods (small change in the covariates' marginal). In addition, the authors should extend the experimental results, compare with existing methods for semi-supervision and use more common benchmark datasets, otherwise it is not possible to assess the relation with existing methods.\n\n[R1] Jose Blanchet and Yang Kang. Semi-supervised learning based on distributionally robust optimization. In Data Analysis and Applications. 2020.\n\n[R2] Charlie Frogner, Sebastian Claici, Edward Chien, and Justin Solomon. Incorporating unlabeled data into distributionally robust learning. Journal of Machine Learning Research. 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)