# Unlabeled Out-Of-Domain Data Improves Generalization

Amir Hossein Saberi∗ Amir Najafi† Alireza Heidari† Mohammad Hosein
Movasaghinia† Abolfazl Motahari† Babak H. Khalaj∗

(  ∗ Department of Electrical Engineering, † Department of Computer
Engineering, Sharif University of Technology, Tehran, Iran )

###### 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.††All correspondence should be addressed to Abolfazl Motahari (Email:
motahari@sharif.edu).

##  1 introduction

Semi-supervised learning has long been a focal point in the machine learning
literature, primarily due to the cost-effectiveness of utilizing unlabeled
data compared to labeled counterparts. However, unlabeled data in various
domains, such as 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 [1,
2]. 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 [3, 4].

This paper aims to demonstrate the efficacy of incorporating out-of-domain
unlabeled samples to decrease the reliance on labeled in-domain data. To
achieve this, we propose a novel framework inspired by a fusion of concepts
from adversarial robustness and self-training. Specifically, we introduce a
unique constraint to the conventional Empirical Risk Minimization (ERM)
procedure, focusing exclusively on the unlabeled part of the dataset. Our
theoretical and experimental analyses show that the inclusion of unlabeled
data reduces the generalization gap for both robust and non-robust loss
functions. Importantly, our alternative optimization criteria are
computationally 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 [5, 6, 7, 8], we also
address the binary classification problem involving two Gaussian models in
$\mathbb{R}^{d}$. 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$ [9], 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 a 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
$n\geq\Omega\left(m^{2}/d\right)$, 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 1.2 introduces our notation and definitions. 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 that increasing the
robust accuracy is considerably more difficult compared to achieving a high
accuracy in non-robust scenarios [10]. In a study by [5], authors argued that
this difficulty might be attributed to the larger sample complexity of
learning robust classifiers in general. In particular, they showcased a simple
model for which a good classifier with high standard (non-robust) accuracy is
achievable using only a single sample, while a significantly larger training
set is required to find a classifier with high robust accuracy. In a set of
recent works [6, 7, 8], it has been shown that the gap between the sample
complexity of robust and standard learning in the setting of [5] (a two-
component Gaussian mixture model) can be filled with unlabeled samples. In
other words, unlabeled samples can be utilized to mitigate the classification
error even when the test samples are perturbed by an adversary. In a similar
study, [3] obtained a similar result using a different definition of
adversarial robustness and a more comprehensive data generation model. In
[11], authors showed that in the setting of [5], out-of-domain unlabeled
samples improve adversarial robustness.

Defense mechanisms against adversarial attacks usually consider two types of
adversaries: i) point-wise attacks similar to [4, 12, 13], and ii)
distributional attacks [14, 15, 16], where in the case of the latter adversary
can change the distribution of data up to a predefined budget. It has been
shown that Distributionally Robust Learning (DRL) achieves a superior
robustness compared to point-wise methods [14]. [17] utilized DRL in order to
achieve a balance between the bias and variance of classifier’s error, leading
to faster rates of convergence compared to empirical risk minimization even in
the non-robust case. In DRL, the learner typically aims to minimize the loss
while allowing the data distribution to vary within an uncertainty
neighborhood. The central idea used by [17] was to regulate the diameter of
this uncertainty neighborhood based on the number of samples. [18] 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 notation and definitions

Let us denote the feature space by $\mathcal{X}\subseteq\mathbb{R}^{d}$, and
assume $\mathcal{H}$ as a class of binary classifiers parameterized by the
parameter set $\Theta$: for each $\theta\in\Theta$, we have a classifier
$h_{\theta}\in\mathcal{H}$ where
$h_{\theta}:\mathcal{X}\rightarrow\left\\{-1,1\right\\}$. Assume a positive
function
$\ell:\left(\mathcal{X}\times\left\\{-1,1\right\\}\times\Theta\right)\to\mathbb{R}_{\geq
0}$ as the loss function. Also, let $P$ be the unknown data distribution over
$\mathcal{X}\times\left\\{-1,1\right\\}$, and
$S=\left\\{\left(\boldsymbol{X}_{i},y_{i}\right)\right\\}_{i=1}^{m}$ for
$m\in\mathbb{N}$ be a set of i.i.d. samples drawn from $P$. Then, for all
$\theta\in\Theta$ the true risk $R$ and the empirical risk $\hat{R}$ of a
classifier w.r.t. $P$ can be defined as follows:

$\displaystyle
R\left(\theta,P\right)=\mathbb{E}_{P}\left[\ell\left(\boldsymbol{X},y;\theta\right)\right]\quad,\quad\hat{R}\left(\theta,S\right)=\mathbb{E}_{\hat{P}^{m}_{S}}\left[\ell\left(\boldsymbol{X},y;\theta\right)\right]\triangleq\frac{1}{m}\sum_{i=1}^{m}{\ell\left(\boldsymbol{X}_{i},y_{i};\theta\right)},$
(1)

where $\hat{P}^{m}_{S}$ denotes an empirical estimate of $P$ based on the $m$
samples in $S$. We also need a way to measure the distance between various
distributions that are supported over $\mathcal{X}$. A well-known candidate
for this goal is the Wasserstein distance:

######  Definition 1.1 (Wasserstein Distance).

Consider two probability distributions $P$ and $Q$ supported on $\mathcal{X}$,
and assume cost function $c:\mathcal{X}\times\mathcal{X}\to\mathbb{R}_{+}$ is
a non-negative lower semi-continuous function satisfying
$c(\boldsymbol{X},\boldsymbol{X})=0$ for all $\boldsymbol{X}\in\mathcal{X}$.
Then, the Wasserstein distance between $P$ and $Q$ w.r.t. $c$, denoted as
$\mathcal{W}_{c}\left(P,Q\right)$, is defined as

$\displaystyle\mathcal{W}_{c}\left(P,Q\right)=\inf_{\mu\in\Gamma\left(\mathcal{X}^{2}\right)}\mathbb{E}_{\boldsymbol{X},\boldsymbol{X}^{\prime}\sim\mu}\left[c(\boldsymbol{X},\boldsymbol{X}^{\prime})\right],~{}~{}\mathrm{subject~{}to~{}}~{}~{}\mu\left(\boldsymbol{X},\cdot\right)=P~{},~{}\mu\left(\cdot,\boldsymbol{X}^{\prime}\right)=Q,$
(2)

where $\Gamma\left(\mathcal{X}^{2}\right)$ denotes the set of all couplings
over $\mathcal{X}\times\mathcal{X}$.

######  Definition 1.2 ($\epsilon$-neighborhood of a Distribution).

The $\epsilon$-neighborhood of a distribution $P$ is defined as the set of all
distributions that have a Wasserstein distance less than $\epsilon$ from $P$.
Mathematically, it can be represented as:

$\mathcal{B}^{c}_{\epsilon}\left(P\right)=\left\\{Q:\mathcal{W}_{c}\left(P,Q\right)\leq\epsilon\right\\}.$
(3)

It should be noted that throughout this paper, the Wasserstein distance
between any two distributions supported over $\mathcal{X}\times\left\\{\pm
1\right\\}$ is defined as the distance between their respective marginals on
$\mathcal{X}$. The ultimate goal of classical learning is to find the
parameter $\theta^{*}\in\Theta$ such that with high probability,
$R\left({\theta^{*}}\right)$ is sufficiently close to
$\min_{\theta}R\left(\theta\right)$. A well-known approach to achieve this
goal is Empirical Risk Minimization (ERM) algorithm, formally defined as
follows:

$\displaystyle\hat{\theta}^{\mathrm{ERM}}\left(S\right)\triangleq\operatorname*{\arg\\!\min}_{\theta\in\Theta}~{}{\mathbb{E}_{\hat{P}^{m}_{S}}\left[\ell\left(\theta;\boldsymbol{X},y\right)\right]}=\operatorname*{\arg\\!\min}_{\theta\in\Theta}~{}{\frac{1}{m}\sum_{i=1}^{m}{\ell\left(\theta;\boldsymbol{X}_{i},y_{i}\right)}}.$
(4)

A recent variant of ERM, which has gained huge popularity in both theory and
practice, is the so-called Distributionally Robust Learning (DRL) which is
formulated as follows:

######  Definition 1.3 (Distributionally Robust Learning($\mathrm{DRL}$)).

DRL aims at training a classifier which is robust against adversarial attacks
on data distribution. In this regard, the learner attempts to find a
classifier with a small robust risk, denoted as
$R^{\mathrm{robust}}\left(\theta,P\right)$, which is defined as

$R^{\mathrm{robust}}_{\epsilon,c}\left(\theta,P\right)=\sup_{P^{\prime}\in\mathcal{B}_{\epsilon}^{c}\left(P\right)}{R\left(\theta,P^{\prime}\right)},$
(5)

for all $\theta\in\Theta$ and any $\epsilon\geq 0$. Therefore, DRL solves the
following optimization problem:

$\hat{\theta}^{\mathrm{DRL}}_{\epsilon,c}\left(S\right)\triangleq\operatorname*{\arg\\!\min}_{\theta\in\Theta}~{}{R^{\mathrm{robust}}_{\epsilon,c}\left(\theta,\hat{P}^{m}_{S}\right)}.$
(6)

Surprisingly, the sophisticated minimax optimization problem of (6) which
takes place in the infinite-dimensional Hilbert space of constrained
probability measures, can be substantially simplified when is re-written in
the dual format:

######  Lemma 1.4 (From [19]).

For a sufficiently small $\epsilon>0$, the minimax optimization problem of (6)
has the following dual form:

$\displaystyle\inf_{\theta\in\Theta}\sup_{P^{\prime}\in\mathcal{B}_{\epsilon}^{c}\left(\hat{P}^{m}_{S}\right)}{R\left(\theta,P^{\prime}\right)}=\inf_{\gamma\geq
0}\left\\{\gamma\epsilon+\inf_{\theta\in\Theta}\frac{1}{m}\sum_{i=1}^{m}\sup_{\boldsymbol{Z}\in\mathcal{X}}~{}\ell\left(\boldsymbol{Z},y_{i};\theta\right)-\gamma
c\left(\boldsymbol{Z},\boldsymbol{X}_{i}\right)\right\\},$ (7)

where $\gamma$ and $\epsilon$ are dual parameters, and there is a bijective
and reciprocal relation between the $\epsilon$ and $\gamma^{*}$, i.e., the
optimal value which minimizes the r.h.s.

As suggested by [20], the $\inf_{\gamma\geq 0}$ in the r.h.s. part in the
above optimization problem can be removed by fixing a user-defined value for
$\gamma$. This also means that if one attempts to find the optimal value for
$\theta$, the additive term $\gamma\epsilon$ is ineffective and can be removed
as well.

It should be noted that this also fixes an (unknown) value for $\epsilon$. In
practice, the appropriate value for $\epsilon$ is not known beforehand and
thus can be usually found through a cross-validation stage, while the same
procedure can be applied to its dual counterpart, i.e., $\gamma$. 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 (7) and let $\gamma$ be a fixed and
arbitrary value.

##  2 problem definition

At this point, we can formally define our problem. Let
$\mathcal{X}\subseteq\mathbb{R}^{d}$, and assume $P_{0}$ be an unknown and
arbitrary distribution supported on $\mathcal{X}\times\left\\{\pm 1\right\\}$,
i.e., $P_{0}$ produces feature-label pairs. For a valid cost function
$c:\mathcal{X}^{2}\rightarrow\mathbb{R}_{\geq 0}$, let $P_{1}$ represent a
shifted version of $P_{0}$ such that the following two conditions hold: i)
$P_{0}\left(y|\boldsymbol{X}\right)$ and $P_{1}\left(y|\boldsymbol{X}\right)$
are the same. In other words, the labeling law is left unaltered. ii) the
marginal distributions of $P_{0}$ and $P_{1}$ on $\mathcal{X}$ are shifted
such that $\mathcal{W}_{c}\left(P_{0,X},P_{1,X}\right)=\alpha$ for some
$\alpha>0$. Here, the subscript $X$ implies the marginal distribution on
$\mathcal{X}$. Let us consider the following two sets of samples:

$\displaystyle
S_{0}=\left\\{\left(\boldsymbol{X}_{i},y_{i}\right)\right\\}_{i=1}^{m}\sim
P_{0}^{m}\quad,\quad
S_{1}=\left\\{\boldsymbol{X}^{\prime}_{i}\right\\}_{i=1}^{n}\sim P_{1,X}^{n},$

where $S_{0}$ indicates the labeled set and $S_{1}$ represents the unlabeled
out-of-domain data. A classical result from VC-theory states that the
generalization gap in learning from only $S_{0}$ (with high probability) can
be bounded as

$R\left(\hat{\theta}^{\mathrm{ERM}},P_{0}\right)\leq\min_{\theta\in\Theta}R\left(\theta,P_{0}\right)+\mathcal{O}\left(\sqrt{{\mathrm{VCdim}\left(\mathcal{H}\right)}/{m}}\right)+\sqrt{\mathcal{O}(1)/m},$
(8)

where $\mathrm{VCdim}\left(\mathcal{H}\right)$ denotes the VC-dimension of
hypothesis class $\mathcal{H}$ [21]. This bound can be prohibitively large
when $\mathrm{VCdim}\left(\mathcal{H}\right)$ grows uncontrollably, e.g., the
case of linear classifiers in very high dimensions ($d\gg 1$).

We aim to propose a general framework that leverages both $S_{0}$ and $S_{1}$
concurrently, and outputs (in polynomial time) an estimator, denoted by
$\hat{\theta}^{\mathrm{RSS}}$, such that the second term in the r.h.s. of (8)
would decay faster as one increases both $m$ and $n$. We are specially
interested in cases where $n\gg m$. In the next step, we apply our method on a
simplified theoretical example in order to give explicit bounds. Similar to
[5, 6, 7, 8], we fully focus the binary classification problem of a high-
dimensional Gaussian mixture model with two components using linear
classifiers. Mathematically speaking, for some $\sigma_{0}\geq 0$ and
$\boldsymbol{\mu}_{0}\in\mathbb{R}^{d}$, let $P_{0}$ be the feature-label
joint distribution over $\mathbb{R}^{d}\times\left\\{-1,1\right\\}$ as
follows:

$\displaystyle P_{0}\left(y=1\right)=\frac{1}{2},\quad
P_{0}\left(\boldsymbol{X}|y\right)=\mathcal{N}\left(y\boldsymbol{\mu}_{0},\sigma_{0}^{2}\boldsymbol{I}\right).$
(9)

Also, suppose a shifted version of $P_{0}$, denoted by $P_{1}$ with
$P_{1}\left(\cdot|y\right)=\mathcal{N}\left({y\boldsymbol{\mu}_{1}},\sigma^{2}_{1}\boldsymbol{I}\right)$,
where
$\|\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}\|\leq\mathcal{O}\left(\alpha\right)$
and $|\sigma_{1}-\sigma_{0}|\leq\mathcal{O}\left(\alpha\right)$ 111Having a
Wasserstein distance of $\alpha$ between two high-dimensional Gaussian
distributions implies that both mean vectors
$\boldsymbol{\mu}_{0},\boldsymbol{\mu}_{1}$ and variances
$\sigma_{0},\sigma_{1}$ are within a fraction of at most
$\mathcal{O}\left(\alpha\right)$ from each other.. Given the two sample sets
$S_{0}$ and $S_{1}$ in this configuration, the problem is to estimate the
optimal linear classifier which achieves the minimum error rate.

##  3 proposed method: Robust Self Supervised (RSS) training

We propose a solution that combines two generally independent paradigms in
machine learning: self-training [22, 23], and distributionally robust learning
in (6). The essence of self-training is to use the currently learned model in
order to induce artificial labels on the unlabeled data. Thus, for an
unlabeled sample $\boldsymbol{X}^{\prime}_{j}$ and any given model parameter
$\theta\in\Theta$, one can temporarily consider a pseudo label given by
$h_{\theta}\left(\boldsymbol{X}^{\prime}_{j}\right)$. In this regard, the
proposed solution denoted by
$\hat{\theta}^{\mathrm{RSS}}=\hat{\theta}^{\mathrm{RSS}}\left(S_{0},S_{1}\right)$
can be defined as follows:

######  Definition 3.1 (Robust Self-Supervised (RSS) Training).

The essence of RSS training is to add a penalty term to the robust version of
the original ERM formulation, which is solely evaluated from the out-of-domain
unlabeled samples in $S_{1}$. Mathematically speaking, for a cost function $c$
and parameter $\gamma\geq 0$, let us define the robust loss
$\phi_{\gamma}:\mathcal{X}\times\left\\{\pm
1\right\\}\times\Theta\rightarrow\mathbb{R}$ as

$\phi_{\gamma}\left(\boldsymbol{X},y;\theta\right)\triangleq\sup_{\boldsymbol{Z}\in\mathcal{X}}~{}\ell\left(\boldsymbol{Z},y;\theta\right)-\gamma
c\left(\boldsymbol{Z},\boldsymbol{X}\right).$ (10)

In this regard, for a given set of parameters
$\gamma,\gamma^{\prime},\lambda\in\mathbb{R}_{\geq 0}$, the proposed RSS
estimator is defined as

$\hat{\theta}^{\mathrm{RSS}}\triangleq\operatorname*{\arg\\!\min}_{\theta\in\Theta}~{}\left\\{\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i},y_{i};\theta\right)+\frac{\lambda}{n}\sum_{j=1}^{n}\phi_{\gamma^{\prime}}\left(\boldsymbol{X}^{\prime}_{j},h_{\theta}\left(\boldsymbol{X}^{\prime}_{j}\right);\theta\right)\right\\}.$
(11)

The proposed RSS loss in (11) comprises of two main terms. The first term
attempts to minimize the empirical robust risk over the labeled data in
$S_{0}$, where an adversary can alter the distribution of samples within a
Wasserstein radius characterized by $\gamma$. In the proceeding sections, we
show that $\gamma$ can become asymptotically large (radius becomes
infinitesimally small) as $m\rightarrow\infty$ which is similar to [18]. In
fact, a 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 $h_{\theta}$. It 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 $\lambda$ and also $\gamma^{\prime}$.

###  3.1 model optimization: algorithm and theoretical guarantees

It can be shown that the for a convex loss function $\ell$, convex cost
function $c$, and sufficiently large $\gamma$ and $\gamma^{\prime}$ (i.e.,
sufficiently small Wasserstein radii), the optimization problem of (11) is
convex and can be solved up to an arbitrarily high precision in polynomial
time. Moreover, if $\ell$ is not convex, e.g., $\mathcal{H}$ is the set of all
neural networks, a simple Stochastic Gradient Descent (SGD) algorithm is still
guaranteed to reach to at least a local minimum of (11). More specifically,
(11) is a minimax optimization problem and consists of an inner maximization
(formulated in (10)) followed by an outer minimization. As long as the cost
function $c$ is strictly convex and $\gamma$ or $\gamma^{\prime}$ are chosen
sufficiently large, the inner maximization problem of (10) becomes strictly
concave [3, 20]. This interesting property holds regardless the convexity of
$\ell$, which is of paramount importance since $\ell$ is not convex in most
practical situations. On the other hand, cost function candidates for $c$
which are considered in this paper are $\left\|\cdot\right\|_{2}$ and
$\left\|\cdot\right\|_{2}^{2}$, which are strictly convex. Hence, (10) can be
optimally solved in polynomial time.

The outer minimization problem of (11) is also differentiable as long as
$\ell$ is sufficiently smooth (again, convexity is not needed). This means the
gradient of (11) exists and can be efficiently computed using the Envelope
Theorem. Explicit bounds on the maximum number of steps in a simple SGD
algorithm (with a mini-batch size of $1$) in order to reach to an
$\varepsilon$-neighborhood of the global maximum of (10), and a local minimum
of (11) are given by [20]. Also, formulating the gradient of minimax loss
functions such as (11) using the envelope theorem has been carried out, for
example, in [3, 20]. 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
$\hat{\theta}^{\mathrm{RSS}}$ and show that it leads to improved
generalization bounds when $n$ is sufficiently large and $\alpha$ 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.,
$\mathcal{H}\triangleq\left\\{\mathrm{sign}\left(\left\langle\boldsymbol{\theta},\cdot\right\rangle\right):\mathbb{R}^{d}\rightarrow\left\\{\pm
1\right\\}|~{}\boldsymbol{\theta}\in\mathbb{R}^{d}\right\\}$. For the sake of
simplicity in results, let us define the loss function $\ell$ as the zero-one
loss:

$\ell\left(\boldsymbol{X},y;\theta\right)=\boldsymbol{1}\left(y\langle\theta,\boldsymbol{X}\rangle\geq
0\right).$ (12)

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 11 can potentially improve the generalization bound
in a 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 (12). Using RSS training
with $m$ labeled and $n$ unlabeled samples in $S_{0}$ and $S_{1}$,
respectively, and for any $\gamma,\delta>0$, there exist $\lambda$ and
$\gamma^{\prime}$ which can be calculated solely based on input samples such
that the following holds with probability at least $1-\delta$:

$\displaystyle{\mathbb{E}_{P_{0}}\left[\phi_{\gamma}\left(\boldsymbol{X},y;\hat{\theta}^{\mathrm{RSS}}\right)\right]}\leq~{}\min_{\theta\in\Theta}~{}{\mathbb{E}_{P_{0}}\left[\phi_{\gamma}\left(\boldsymbol{X},y;\theta\right)\right]}$
(13) $\displaystyle\hskip
45.52458pt+~{}\mathcal{O}\left(\gamma\sqrt{\frac{2d}{m}\left(\alpha\left(\|\boldsymbol{\mu}_{0}\|_{2}^{2}+\sigma_{0}^{2}\right)+\sqrt{\frac{2d}{2n+m}}+\sqrt{\frac{2\log\left({{1}/{\delta}}\right)}{2n+m}}\right)}+\sqrt{\frac{2\log\left({1/\delta}\right)}{m}}\right).$

The proof, as well as how to calculate $\lambda$ and $\gamma^{\prime}$ can be
found in Appendix A. Theorem 4.1 presents a generalization bound for the
proposed estimator when one considers the robust loss under an adversarial
budget, which is characterized by $\gamma$. Larger values of $\gamma$
correspond to smaller Wasserstein radii for the distributional adversary of
(5). The residual term in the r.h.s. of (13) converges to zero with a faster
rate compared to that of (8), given $n$ is sufficiently large and $\alpha$ is
sufficiently small. We derive explicit conditions regarding this event in
Corollary 4.4. 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 as well:

######  Theorem 4.2.

Consider the setting described in Theorem 4.1. Then, the estimator
$\hat{\theta}^{\mathrm{RSS}}$ of (11) using respectively $m$ labeled and $n$
unlabeled samples, along with specific values of $\gamma$, $\gamma^{\prime}$,
and $\lambda$ which can be calculated solely from the input samples, satisfies
the following non-robust generalization bound with probability at least
$1-\delta$:

$\displaystyle R\left(\hat{\theta}^{\mathrm{RSS}},P\right)$
$\displaystyle-\min_{\theta\in\Theta}R\left(\theta,P\right)$ (14)
$\displaystyle\leq~{}\mathcal{O}\left(\frac{e^{\frac{-\|\boldsymbol{\mu}_{0}\|_{2}^{2}}{4\sigma_{0}^{2}}}}{\sqrt{2\sigma_{0}\sqrt{2\pi}}}\left(\left(\|\boldsymbol{\mu}_{1}\|_{2}^{2}+\sigma_{1}^{2}\right)\frac{2d\alpha}{m}+\frac{4d}{m}\sqrt{\frac{2d+2\log{\frac{1}{\delta}}}{2n+m}}\right)^{1/4}+\sqrt{\frac{2\log{\frac{1}{\delta}}}{m}}\right).$

Again, the proof and the procedure for calculating $\gamma,\gamma^{\prime}$,
and $\lambda$ are discussed in Appendix A.

######  Remark 4.3.

Dependence of the generalization gap, a.k.a. excess risk, in Theorem 4.2 on
dimension is $\mathcal{O}\left(d^{3/8}\right)$, which shows improvement over
$\mathcal{O}\left(d^{1/2}\right)$ of the conventional ERM.

Based on the previous results, the following corollary showcases a number of
surprising non-asymptotic conditions under which our generalization bound
becomes superior to conventional approaches.

######  Corollary 4.4.

Consider the setting described in Theorem 4.2. Then,
$\hat{\theta}^{\mathrm{RSS}}$ of (11) with $m$ labeled and $n$ unlabeled
samples has an advantage over the traditional ERM, if:

$\displaystyle\alpha\leq\mathcal{O}\left({d}/{m}\right)\quad,\quad
n\geq\Omega\left({m^{2}}/{d}\right).$ (15)

Also, the following conditions are sufficient to make the minimum required $m$
(for a given error bound) independent of the dimension $d$:

$\alpha\leq\mathcal{O}\left({d}^{-1}\right)\quad,\quad
n\geq\Omega\left(d^{3}\right).$ (16)

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., $\alpha=0$, then the excess risk of RSS-training satisfies the
following inequality with probability at least $1-\delta$:

$R\left(\hat{\theta}^{\mathrm{RSS}},P\right)-\min_{\theta\in\Theta}R\left(\theta,P\right)\leq\mathcal{O}\left(\left(\frac{d^{3}\log{1/\delta}}{m^{2}\left(2n+m\right)}\right)^{1/8}+\sqrt{\frac{\log{1/\delta}}{m}}\right),$
(17)

which again shows the previously-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 1). Next, we present a more general
case of Theorem 4.2 where each Gaussian component can have a non-diagonal
covariance matrix. Mathematically speaking, suppose that $P_{0}$ and $P_{1}$
are defined as follows:

$\displaystyle P_{0}\left(y=1\right)=1/2\quad,\quad
P_{0}\left(\boldsymbol{X}|y\right)=\mathcal{N}\left(y\boldsymbol{\mu_{0}},\Sigma_{0}\right),$
$\displaystyle
P_{1\boldsymbol{X}}=\frac{1}{2}\mathcal{N}\left(\boldsymbol{\mu_{1}},\Sigma_{1}\right)+\frac{1}{2}\mathcal{N}\left(-\boldsymbol{\mu_{1}},\Sigma_{1}\right),$
(18)

where
$\|\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{0}\|\leq\mathcal{O}\left(\alpha\right)$
and $\|\Sigma_{1}-\Sigma_{0}\|_{2}\leq\mathcal{O}\left(\alpha\right)$. Assume
a set of $m$ labeled samples $S_{0}\sim P_{0}^{m}$, and a set of $n$ unlabeled
samples $S_{1}\sim P_{1\boldsymbol{X}}^{n}$.

######  Theorem 4.5 (Generalization Bound for General Gaussian Mixture
Models).

Consider the setting described in (4). Using algorithm in (11) with $m$
labeled and $n$ unlabeled samples, there exists a set of parameters
$\gamma,\gamma^{\prime},\lambda$ for which the following holds with
probability at least $1-\delta$:

$\displaystyle R\left(\hat{\theta}^{\mathrm{RSS}},P\right)$
$\displaystyle-\min_{\theta\in\Theta}R\left(\theta,P\right)\leq~{}$ (19)
$\displaystyle\mathcal{O}\left(e^{\vartheta^{2}}\left(\sqrt{\frac{\|\boldsymbol{\mu}_{1}\|_{2}^{2}+\operatorname{Tr}{\left(\Sigma_{1}\right)}}{m}}\left(C\alpha+\sqrt{\frac{\log{\frac{1}{\delta}}}{2n+m}}\right)\frac{d\kappa_{1}\kappa_{1}^{\prime}}{\Delta\left(\Sigma\right)}\right)^{1/2}+\sqrt{\frac{\log{1/\delta}}{m}}\right),$

where

$\displaystyle\vartheta$
$\displaystyle=|\boldsymbol{\mu}_{1}\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{0}\Sigma_{0}^{-1}\boldsymbol{\mu}_{0}|,\quad
C=\left(\frac{\|\mu_{0}\|^{2}+\lambda_{\mathrm{min}}\left(\Sigma_{1}\right)\|\mu_{0}\|_{2}}{\lambda_{\mathrm{min}}^{2}}\right),$
$\displaystyle\kappa_{1}$
$\displaystyle=\frac{\lambda_{\mathrm{max}}\left(\Sigma_{1}\right)}{\lambda_{\mathrm{min}}\left(\Sigma_{1}\right)},\quad\quad\quad\quad\quad\quad~{}\kappa_{1}^{\prime}=\frac{\lambda_{\mathrm{max}}\left(\Sigma_{1}\right)}{\Delta\left(\Sigma_{1}\right)},$
$\displaystyle\Delta\left(\Sigma_{1}\right)$
$\displaystyle=\min\left\\{\lambda_{i}\left(\Sigma_{1}\right)-\lambda_{j}\left(\Sigma_{1}\right)\right\\},~{}~{}~{}\forall
i,j:\lambda_{i}\left(\Sigma_{1}\right)\neq\lambda_{j}\left(\Sigma_{1}\right),$
(20)

and $\lambda_{i}\left(\Sigma\right)$ is the $i$(th) eigenvalue of $\Sigma$.

Proof can be found in Appendix. One important difference to note between
Theorem 4.5 and Theorem 4.2 is the choice of $\gamma^{\prime}$, which controls
the adversarial budget for unlabeled (and out-of-domain) part of the dataset.
In the setting of Theorem 4.2, we prefer to choose $\gamma^{\prime}$ as small
as possible. However, in the setting of Theorem 4.5, we consider the
eigenvectors and eigenvalues of $\Sigma_{1}$ and $\Sigma_{0}$, as well as the
direction of $\boldsymbol{\mu}_{1}$ and $\boldsymbol{\mu}_{0}$ in order to
find the optimal value for the adversarial budget. In fact, there are cases in
which selecting a large $\gamma^{\prime}$ (less freedom for the adversary) may
actually be the optimal choice.

##  5 exprimental results

The effectiveness of the proposed method has been assessed through
experimenting on 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 are sampled from the
same distribution, and ii) the scenarios where the unlabeled data differs in
distribution from the labeled ones. First, let us specify the datasets used in
our experiments:

  1. 1.

Simulated data consists of binary-labeled data points with a dimension of
$d=200$, generated according to the setting described in Section 2.

  2. 2.

NCT-CRC-HE-100K consists of 100,000 histopathology images of colon tissue
[24]. The images have dimensions of $224\times 224$ and were captured at
$20\mathrm{x}$ magnification. The dataset is labeled with $9$ distinct classes
.

  3. 3.

PatchCamelyon is a widely used benchmark dataset for medical image analysis.
It consists of a large collection of 327,680 color histopathology images from
lymph node, each with dimensions $96\times 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 a varying number of unlabeled samples. The results (see Table 1) show
that our proposed method achieves accuracy improvements comparable to models
trained only on labeled samples. Moreover, results indicate that our method is
more effective when labeled and unlabeled data come from the same
distribution. However, it still demonstrates significant improvement even when
the unlabeled samples undergo a distribution shift.

Table 1: Accuracy of the model trained on labeled datasets of sizes $10$, $20$, $40$, and $10,000$ with varying amounts of unlabeled data from the same distribution with $\alpha=0$ (left), and different distribution with $\alpha=0.5\|\boldsymbol{\mu}_{0}\|_{2}$ (right). Same distribution | Different distribution
---|---
#Labeled | Acc | #Unlabeled | Acc | #Labeled | Acc | #Unlabeled | 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
20 | 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 | - | -

###  5.2 Experiment of Histopathology Data

The processing pipeline over the real-world dataset of histopathology images
is based on using a ResNet50 encoder pre-trained on ImageNet [25, 26], which
extracts and stores $1\times 1024$ embeddings from input images. Such
embeddings are then used to train a deep neural network with four layers of
size $2048$ and one output layer for the class id. Also, we have used a
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, “different distributions”
setting implies that labeled data comes from the NCT-CRC-HE-100K dataset
(labels are either “Normal” or “Tumor”), while the PatchCamelyon dataset was
used for the unlabeled data. As a result, the final labeling is 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.

Table 2: Accuracy of the model trained on labeled data from NCT-CRC-HE-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 dataset)(right). Same distribution | Different distribution
---|---
#Labeled | Acc | #Unlabeled | Acc | #Labeled | Acc | #Unlabeled | 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 | - | -

##  6 Conclusion

In this work, we have studied both the robust and non-robust classification
problem in the presence of a limited labeled dataset and a relatively larger
collection of unlabeled samples. We further assume that unlabeled data have
come from a slightly perturbed distribution compared to the original data
distribution. To the best of our knowledge, we present the first non-
asymptotic tradeoff between the sizes of the labeled and unlabeled samples,
denoted respectively by $m$ and $n$, in the case of learning a two-component
Gaussian mixture model. In particular, we show when
$n\geq\Omega\left(m^{2}/d\right)$, the generalization bound improves compared
to the case when only labeled data are used even if unlabeled data points are
slightly out-of-domain. More sophisticated results for the generalization
error of the robust and non-robust cases have been derived as well. Our
technique is based on optimizing a robust loss (with an asymptotically
decreasing radius for the uncertainty ball) in addition to a robust
regularization term which forces the classifier to avoid crowded and dense
areas. As a result, we have utilized many existing tools from self-training,
distributionally robust learning and optimal transport to build our framework.

We have validated our theoretical findings through a number of experiments on
both synthetic and public real-world datasets. Our experiments show the
classification accuracy (even for non-Gaussian cases) gets improved through
feeding our method with out-of-domain unlabeled samples. Our proposed
methodology is based on two key ideas: 1) Leveraging unlabeled out-of-domain
data to improve the robust accuracy of a classifier, and 2) Adapting the
radius of the uncertainty neighborhood based on the quantity of labeled and
unlabeled samples to achieve a good trade-off between bias and variance in
classification error.

For future works, one can consider improving the bounds and trying to relax
the conditions under which the utilization of unlabeled data becomes helpful.
Also, deriving error lower-bounds and impossibility results seem to be another
interesting research direction. Finally, we have restricted the level of
distribution shift for the out-of-domain samples in order to achieve
theoretical guarantees. Relaxing such restrictions seems to be another
interesting problem to tackle.

## References

  * [1] I. J. Goodfellow, J. Shlens, and C. Szegedy, “Explaining and harnessing adversarial examples,” arXiv preprint arXiv:1412.6572, 2014.
  * [2] B. Biggio and F. 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.
  * [3] A. Najafi, S.-i. Maeda, M. Koyama, and T. Miyato, “Robustness to adversarial perturbations in learning from incomplete data,” Advances in Neural Information Processing Systems, vol. 32, 2019.
  * [4] T. Miyato, S.-i. Maeda, M. Koyama, and S. Ishii, “Virtual adversarial training: a regularization method for supervised and semi-supervised learning,” IEEE transactions on pattern analysis and machine intelligence, vol. 41, no. 8, pp. 1979–1993, 2018.
  * [5] L. Schmidt, S. Santurkar, D. Tsipras, K. Talwar, and A. Madry, “Adversarially robust generalization requires more data,” Advances in neural information processing systems, vol. 31, 2018.
  * [6] Y. Carmon, A. Raghunathan, L. Schmidt, J. C. Duchi, and P. S. Liang, “Unlabeled data improves adversarial robustness,” Advances in neural information processing systems, vol. 32, 2019.
  * [7] R. Zhai, T. Cai, D. He, C. Dan, K. He, J. Hopcroft, and L. Wang, “Adversarially robust generalization just requires more unlabeled data,” arXiv preprint arXiv:1906.00555, 2019.
  * [8] J.-B. Alayrac, J. Uesato, P.-S. Huang, A. Fawzi, R. Stanforth, and P. Kohli, “Are labels required for improving adversarial robustness?,” Advances in Neural Information Processing Systems, vol. 32, 2019.
  * [9] A. Kumar, T. Ma, and P. Liang, “Understanding self-training for gradual domain adaptation,” in International Conference on Machine Learning, pp. 5468–5479, PMLR, 2020.
  * [10] N. Carlini and D. Wagner, “Towards evaluating the robustness of neural networks,” in 2017 ieee symposium on security and privacy (sp), pp. 39–57, Ieee, 2017.
  * [11] Z. Deng, L. Zhang, A. Ghorbani, and J. Zou, “Improving adversarial robustness via unlabeled out-of-domain data,” in International Conference on Artificial Intelligence and Statistics, pp. 2845–2853, PMLR, 2021.
  * [12] A. Nguyen, J. Yosinski, and J. 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–436, 2015.
  * [13] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus, “Intriguing properties of neural networks,” arXiv preprint arXiv:1312.6199, 2013.
  * [14] M. Staib and S. Jegelka, “Distributionally robust deep learning as a generalization of adversarial training,” in NIPS workshop on Machine Learning and Computer Security, vol. 3, p. 4, 2017.
  * [15] S. Shafieezadeh Abadeh, P. M. Mohajerin Esfahani, and D. Kuhn, “Distributionally robust logistic regression,” Advances in Neural Information Processing Systems, vol. 28, 2015.
  * [16] P. Mohajerin Esfahani and D. Kuhn, “Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations,” Mathematical Programming, vol. 171, no. 1-2, pp. 115–166, 2018.
  * [17] H. Namkoong and J. C. Duchi, “Variance-based regularization with convex objectives,” Advances in neural information processing systems, vol. 30, 2017.
  * [18] R. Gao, “Finite-sample guarantees for wasserstein distributionally robust optimization: Breaking the curse of dimensionality,” Operations Research, 2022.
  * [19] J. Blanchet, Y. Kang, and K. Murthy, “Robust wasserstein profile inference and applications to machine learning,” Journal of Applied Probability, vol. 56, no. 3, pp. 830–857, 2019.
  * [20] A. Sinha, H. Namkoong, R. Volpi, and J. Duchi, “Certifying some distributional robustness with principled adversarial training,” arXiv preprint arXiv:1710.10571, 2017.
  * [21] M. Mohri, A. Rostamizadeh, and A. Talwalkar, Foundations of Machine Learning.  MIT Press, 2018.
  * [22] Y. Grandvalet and Y. Bengio, “Semi-supervised learning by entropy minimization,” Advances in neural information processing systems, vol. 17, 2004.
  * [23] M.-R. Amini and P. Gallinari, “Semi-supervised logistic regression,” in ECAI, vol. 2, p. 11, 2002.
  * [24] J. N. Katherm, Halama, Niels, Marx, and Alexander, “100,000 histological images of human colorectal cancer and healthy tissue,” Apr. 2018.
  * [25] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in 2009 IEEE conference on computer vision and pattern recognition, pp. 248–255, Ieee, 2009.
  * [26] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016.
  * [27] M. J. Wainwright, High-dimensional statistics: A non-asymptotic viewpoint, vol. 48.  Cambridge University Press, 2019.
  * [28] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings (Y. Bengio and Y. LeCun, eds.), 2015.
  * [29] J. L. B. S. Veeling, J. Winkens, T. Cohen, and M. Welling, “Rotation equivariant cnns for digital pathology,” Sept. 2018.
  * [30] R. J. Chen and R. G. Krishnan, “Self-supervised vision transformers learn visual concepts in histopathology,” CoRR, vol. abs/2203.00585, 2022.

##  Appendix A Proof of Theorems

In this section, we present the proofs for the Theorems and Lemmas from the
main manuscript.

###### Proof of Theorem 4.1.

With respect to discussions from the main manuscript, we already know that
$\hat{\theta}^{\mathrm{RSS}}$ is the result of the following optimization
problem:

$\displaystyle\hat{\theta}^{\mathrm{RSS}}\triangleq\operatorname*{\arg\\!\min}_{\theta\in\Theta}~{}\left\\{\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i},y_{i};\theta\right)+\frac{\lambda}{n}\sum_{j=1}^{n}\phi_{\gamma^{\prime}}\left(\boldsymbol{X}^{\prime}_{j},h_{\theta}\left(\boldsymbol{X}^{\prime}_{j}\right);\theta\right)\right\\}.$
(21)

According to Lagrange duality, it is known that there exists $s\geq 0$ such
that $\hat{\theta}^{\mathrm{RSS}}$ is also the result of the following
optimization problem:

$\hat{\theta}^{\mathrm{RSS}}=\operatorname*{\arg\\!\min}_{\theta:\frac{1}{n}\sum_{j=1}^{n}\phi_{\gamma^{\prime}}\left(\boldsymbol{X}^{\prime}_{j},h_{\theta}\left(\boldsymbol{X}^{\prime}_{j}\right);\theta\right)\leq
s}{\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i},y_{i};\theta\right)}.$
(22)

To prove the theorem, we need to establish an upper bound on the distance
between the expected robust loss of $\hat{\theta}^{\mathrm{RSS}}$ 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

$\frac{1}{n}\sum_{j=1}^{n}\phi_{\gamma^{\prime}}\left(\boldsymbol{X}^{\prime}_{j},h_{\theta}\left(\boldsymbol{X}^{\prime}_{j}\right);\theta\right)\leq
s,$ (23)

and then, we demonstrate that the parameter $\theta^{\star}$, which achieves
the best possible robust loss, satisfies (23). Suppose that the loss function
is bounded with $b$, i.e.,

$\displaystyle l\left(\boldsymbol{X},y;\theta\right)\leq
b,~{}\forall\theta,\boldsymbol{X},y,$
$\displaystyle\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta\right)\leq
b,~{}\forall c,\gamma,\theta,\boldsymbol{X},y,$

where the second inequality directly results from the first one. Therefore,
$\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i},y_{i};\theta\right)$
has the bounded difference property with parameter ${b}/{m}$, which results
that

$\displaystyle\Phi\left(P_{0},S_{0},\gamma,c\right)=\sup_{\theta\in\tilde{\Theta}}{\left(\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i},y_{i};\theta\right)-\mathbb{E}_{P_{0}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta\right)\right]\right)},$
(24)

also has the bounded difference property with parameter ${b}/{m}$, where
$\tilde{\Theta}$ is defined as

$\tilde{\Theta}\triangleq\left\\{\theta:\frac{1}{n}\sum_{j=1}^{n}\phi_{\gamma^{\prime}}\left(\boldsymbol{X}^{\prime}_{j},h_{\theta}\left(\boldsymbol{X}^{\prime}_{j}\right);\theta\right)\leq
s\right\\}.$ (25)

So, we have the following inequality with probability more than $1-\delta$:

$\Phi\left(P_{0},S_{0},\gamma,c\right)\leq\mathbb{E}\left[\Phi\left(P_{0},S_{0},\gamma,c\right)\right]+\sqrt{\frac{\log{1/\delta}}{m}},\quad\forall\theta\in\tilde{\Theta}.$
(26)

In the above inequality we can give an upper-bound for the first term in the
right hand side of the inequality as follows:

$\displaystyle\mathbb{E}\left[\Phi\left(P_{0},S_{0},\gamma,c\right)\right]=$
$\displaystyle\mathbb{E}_{S_{0}\sim
P_{0}^{m}}\left[\sup_{\theta\in\tilde{\Theta}}{\left(\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i},y_{i};\theta\right)-\mathbb{E}_{P_{0}}\left[\phi_{\gamma}^{c}\left(\theta;\boldsymbol{X},y\right)\right]\right)}\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{S_{0},S_{0}^{\prime}}\left[\sup_{\theta\in\tilde{\Theta}}{\left(\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i},y_{i};\theta\right)-\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i}^{\prime},y_{i}^{\prime};\theta\right)\right)}\right]$
$\displaystyle\leq$ $\displaystyle
2\mathbb{E}_{S_{0},\epsilon}\left[\sup_{\theta\in\tilde{\Theta}}{\frac{1}{m}\sum_{\left(\boldsymbol{X}_{i},y_{i}\right)\in
S_{0}}{\epsilon_{i}\phi_{\gamma}^{c}\left(\theta;\boldsymbol{X}_{i},y_{i}\right)}}\right].$
(27)

Consider the loss function mentioned in the Theorem 4.1, and the following
cost functions $c,c^{\prime}$

$c(\boldsymbol{X},\boldsymbol{X}^{\prime})=\|\boldsymbol{X}-\boldsymbol{X}^{\prime}\|_{2},\quad
c^{\prime}(\boldsymbol{X},\boldsymbol{X}^{\prime})=\|\boldsymbol{X}-\boldsymbol{X}^{\prime}\|_{2}^{2}.$

With these loss and cost functions we can rewrite $\phi_{\gamma}^{c}$ and
$\phi_{\gamma^{\prime}}^{c^{\prime}}$ as follows:

$\displaystyle\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta\right)=$
$\displaystyle\min\left\\{1,\max\left\\{0,1-\gamma
y\langle\theta,\boldsymbol{X}\rangle\right\\}\right\\},$ (28)
$\displaystyle\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},h_{\theta}\left(\boldsymbol{X}\right);\theta\right)=$
$\displaystyle\max\left\\{0,1-\gamma^{\prime}\langle\theta,\boldsymbol{X}\rangle^{2}\right\\}.$
(29)

As we can see $\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta\right)$ is a
$\gamma$-lipschitz function of $y\langle\theta,\boldsymbol{X}\rangle$. Based
on the Talagrand’s contraction lemma, we can continue the inequalities in (A)
as

$\displaystyle\mathbb{E}\left[\Phi\left(P+0,S_{0},\gamma,c\right)\right]\leq$
$\displaystyle\mathbb{E}_{S_{0},\epsilon}\left[\sup_{\theta\in\tilde{\Theta}}{\frac{1}{m}\sum_{\left(\boldsymbol{X}_{i},y_{i}\right)\in
S_{0}}{\epsilon_{i}\phi_{\gamma}^{c}\left(\boldsymbol{X}_{i},y_{i};\theta\right)}}\right]$
$\displaystyle\leq$
$\displaystyle\gamma\mathbb{E}_{S_{0},\epsilon}\left[\sup_{\theta\in\tilde{\Theta}}{\frac{1}{m}\sum_{\left(\boldsymbol{X}_{i},y_{i}\right)\in
S_{0}}{\epsilon_{i}y_{i}\langle\theta,\boldsymbol{X}_{i}\rangle}}\right]$
$\displaystyle\leq$
$\displaystyle\gamma\mathbb{E}_{S_{0},\epsilon}\left[\inf_{\zeta>0}{\sup_{\theta\in\Theta}{\frac{1}{m}\sum_{\left(\boldsymbol{X}_{i},y_{i}\right)\in
S_{0}}{\epsilon_{i}\langle\theta,y_{i}\boldsymbol{X}_{i}\rangle}}}\right.\left.{{-\frac{\zeta}{n}\sum_{\boldsymbol{X}_{i}^{\prime}\in
S_{1}}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i}^{\prime},h_{\theta}\left(\boldsymbol{X}_{i}^{\prime}\right);\theta\right)}+\zeta
s^{\prime}}}\right]$ $\displaystyle\leq$
$\displaystyle\gamma\mathbb{E}_{S_{0},\epsilon}\left[\inf_{\zeta>0}{\sup_{\theta\in\Theta}{\frac{1}{m}\sum_{\left(\boldsymbol{X}_{i},y_{i}\right)\in
S_{0}}{\epsilon_{i}y_{i}\langle\theta,\boldsymbol{X}_{i}\rangle}}}\right.\left.{{+\frac{\zeta\gamma^{\prime}}{n}\sum_{\boldsymbol{X}_{i}^{\prime}\in
S_{1}}{\langle\theta,\boldsymbol{X}^{\prime}_{i}\rangle^{2}}-\zeta\left(1-s\right)}}\right]$
$\displaystyle=$
$\displaystyle\gamma\mathbb{E}_{S_{0},\epsilon}\left[\inf_{\zeta>0}{\sup_{\theta\in\Theta}{\langle\theta,\frac{1}{m}\sum_{\boldsymbol{X}_{i}\in
S_{0}}{\epsilon_{i}y_{i}\boldsymbol{X}_{i}}\rangle}}\right.\left.{{+\zeta\gamma^{\prime}\theta^{T}\left(\frac{1}{n}\sum_{\boldsymbol{X}_{i}^{\prime}\in
S_{1}}{\boldsymbol{X}_{i}^{\prime}\boldsymbol{X}_{i}^{\prime
T}}\right)\theta-\zeta\left(1-s\right)}}\right].$ (30)

Let us set $\boldsymbol{v}=\frac{1}{m}\sum_{\boldsymbol{X}_{i}\in
S_{0}}{\epsilon_{i}y_{i}\boldsymbol{X}_{i}}$ and
$\hat{\Sigma}=\left(\frac{1}{n}\sum_{\boldsymbol{X}_{i}^{\prime}\in
S_{1}}{\boldsymbol{X}_{i}^{\prime}\boldsymbol{X}_{i}^{\prime T}}\right)$, and
then continue the inequalities in (A) as

$\displaystyle\mathbb{E}\left[\Phi\left(P+0,S_{0},\gamma,c\right)\right]\leq$
$\displaystyle\gamma\mathbb{E}_{S_{0},\epsilon}\left[\inf_{\zeta>0}{\sup_{\theta\in\Theta}{\langle\theta,\boldsymbol{v}\rangle}}{{+\zeta\gamma^{\prime}\theta^{T}\hat{\Sigma}\theta-\zeta\left(1-s\right)}}\right].$
(31)

In order to find a proper upper-bound for the Rademacher complexity, we
attempt to solve the inner maximization problem

$\sup_{\theta\in\Theta}{\langle\theta,\boldsymbol{v}\rangle+\zeta\gamma^{\prime}\theta^{T}\hat{\Sigma}\theta}.$
(32)

We know that the parameter $\theta$ which maximizes the first term
$\langle\theta,\boldsymbol{v}\rangle$ is a vector with Euclidean norm of $1$
in the direction of $\boldsymbol{v}$. Also, the parameter which maximizes the
second term $\theta^{T}\hat{\Sigma}\theta$ is a vector with norm $1$ in the
direction of $\boldsymbol{u}_{\mathrm{max}}$, which is the eigenvector of
$\hat{\Sigma}$ that corresponds to the maximum eigenvalue
$\lambda_{\mathrm{max}}$. Therefore, the solution to the maximization problem
in (32) should belong to the span of $\boldsymbol{v}$ and
$\boldsymbol{u}_{\mathrm{max}}$, i.e.,

$\displaystyle\theta=$
$\displaystyle\psi_{1}\frac{\boldsymbol{v}}{\|\boldsymbol{v}\|_{2}}+\psi_{2}\frac{\boldsymbol{u}_{\mathrm{max}}}{\|\boldsymbol{u}_{\mathrm{max}}\|_{2}}$
$\displaystyle=$
$\displaystyle\psi_{1}\hat{\boldsymbol{v}}+\psi_{2}\hat{\boldsymbol{u}}_{\mathrm{max}},$
(33)

where:

$\displaystyle\psi_{1}^{2}+\psi_{2}^{2}+2\psi_{1}\psi_{2}\eta=1,$
$\displaystyle\eta=\langle\hat{\boldsymbol{v}},\hat{\boldsymbol{u}}_{\mathrm{max}}\rangle,$
$\displaystyle\kappa=\sqrt{1-\langle\hat{\boldsymbol{v}},\hat{\boldsymbol{u}}_{\mathrm{max}}\rangle^{2}}$
$\displaystyle\tau=\hat{\boldsymbol{v}}^{T}\hat{\Sigma}\hat{\boldsymbol{v}}$
$\displaystyle s^{\prime}=\frac{1-s}{\gamma^{\prime}}.$ (34)

Due to (32), (A) and (A), we have the following problem:

$\displaystyle\sup$
$\displaystyle~{}{\psi_{1}\|\boldsymbol{v}\|_{2}+\psi_{2}\eta}.$ (35)
$\displaystyle\mathrm{S.t.}$
$\displaystyle~{}\psi_{1}^{2}+\psi_{2}^{2}+2\psi_{1}\psi_{2}\eta=1,$
$\displaystyle\psi_{2}^{2}\lambda_{\mathrm{max}}+\psi_{1}^{2}\tau+2\psi_{1}\psi_{2}\lambda_{\mathrm{max}}\eta\geq
s^{\prime}$

The constraints in the above problem can be rewritten as

$\displaystyle\psi_{1}^{2}+\psi_{2}^{2}+2\psi_{1}\psi_{2}\eta=1,$ (36)
$\displaystyle\lambda_{\mathrm{max}}-\psi_{1}^{2}\left(\lambda_{\mathrm{max}}-\tau\right)\geq
s^{\prime}.$

In the above equations, if we set $s^{\prime}=\lambda_{\max}$, then the only
$\psi_{1}$ which satisfies the constraint is $\psi_{1}=0$. Suppose that we use
a set of $n$ i.i.d. samples from $\mathbb{P}_{1X}$ (which is different from
the $S_{1}$) to estimate the $\lambda_{\mathrm{max}}$, and name this estimate
$\hat{\lambda}_{\mathrm{max}}$. If we set

$s^{\prime}=\frac{1-s}{\gamma^{\prime}}=\hat{\lambda}_{\mathrm{max}}\left(1-\alpha\right)-3\mathcal{O}\left({\sqrt{\frac{d}{n}}+\sqrt{\frac{\log(\frac{2}{\delta})}{n}}}\right),$
(37)

form Theorem $6.5$ in [27] we have the following relation with probability
more than $1-\delta$:

$\lambda_{\mathrm{max}}\left(1-\alpha\right)-5\mathcal{O}\left(\sqrt{\frac{d}{n}}+\sqrt{\frac{\log(\frac{2}{\delta})}{n}}\right)\leq
s^{\prime}\leq\lambda_{\mathrm{max}}\left(1-\alpha\right)-\mathcal{O}\left(\sqrt{\frac{d}{n}}+\sqrt{\frac{\log(\frac{2}{\delta})}{n}}\right).$
(38)

By weakening the constraint in (35), the result of the optimization becomes
larger, which means by solving the following optimization problem we have an
upper-bound for (35):

$\displaystyle\sup$
$\displaystyle~{}{\psi_{1}\|\boldsymbol{v}\|_{2}+\psi_{2}\eta}.$ (39)
$\displaystyle\mathrm{S.t.}$
$\displaystyle~{}\psi_{1}^{2}+\psi_{2}^{2}+2\psi_{1}\psi_{2}\eta=1$
$\displaystyle\psi_{1}^{2}\left(\lambda_{\mathrm{max}}-\tau\right)\leq\alpha\lambda_{\mathrm{max}}+5\mathcal{O}\left(\sqrt{\frac{d}{n}}+\sqrt{\frac{\log(\frac{2}{\delta})}{n}}\right),$

where for the Gaussian distribution and the way $\hat{\boldsymbol{v}}$ is
built we have:

$\lambda_{\mathrm{max}}-\tau=\|\mu_{1}\|_{2}^{2}\left(1-\frac{\sqrt{\|\mu_{0}\|_{2}^{2}+\sigma_{0}^{2}}}{\sqrt{\|\mu_{0}\|_{2}^{2}+\sigma_{0}^{2}d}}\right)=\chi^{2}.$
(40)

In this regard, the results of optimization problems (39) and (32) have the
following upper-bound:

$\frac{\|v\|_{2}}{\chi}\sqrt{\alpha\lambda_{\mathrm{max}}+5\mathcal{O}\bigg{(}\sqrt{\frac{d}{n}}+\sqrt{\frac{\log(\frac{2}{\delta})}{n}}\bigg{)}}=\frac{\|\frac{1}{m}\sum_{\boldsymbol{X}_{i}\in
S_{0}}{\epsilon_{i}\boldsymbol{X}_{i}}\|_{2}}{\chi}\sqrt{\alpha\lambda_{\mathrm{max}}+5\mathcal{O}\bigg{(}\sqrt{\frac{d}{n}}+\sqrt{\frac{\log(\frac{2}{\delta})}{n}}\bigg{)}}.$
(41)

This way, we also have an upper-bound for Rademacher complexity in (A) as

$\displaystyle\mathbb{E}\left[\Phi\left(P+0,S_{0},\gamma,c\right)\right]$
$\displaystyle\leq\gamma\frac{\mathbb{E}_{\boldsymbol{\epsilon},S_{0}}\left[\|\frac{1}{m}\sum_{\boldsymbol{X}_{i}\in
S_{0}}{\epsilon_{i}\boldsymbol{X}_{i}}\|_{2}\right]}{\chi}\sqrt{\alpha\lambda_{\mathrm{max}}+5\mathcal{O}\left(\sqrt{\frac{d}{n}}+\sqrt{\frac{\log(\frac{2}{\delta})}{n}}\right)}$
$\displaystyle\leq\gamma\frac{\sqrt{\mathbb{E}_{\boldsymbol{X}}\left[\|\boldsymbol{X}\|_{2}^{2}\right]}}{\chi\sqrt{m}}\sqrt{\alpha\lambda_{\mathrm{max}}+5\mathcal{O}\left(\sqrt{\frac{d}{n}}+\sqrt{\frac{\log(\frac{2}{\delta})}{n}}\right)},$
(42)

where for the Gaussian distribution we have:

$\displaystyle\mathbb{E}\left[\Phi\left(P+0,S_{0},\gamma,c\right)\right]$
$\displaystyle\leq\gamma\frac{\sqrt{\|\mu_{1}\|_{2}^{2}+\sigma_{1}^{2}d}}{\chi\sqrt{m}}\sqrt{\alpha\lambda_{\mathrm{max}}+5\mathcal{O}\left(\sqrt{\frac{d}{n}}+\sqrt{\frac{\log(\frac{2}{\delta})}{n}}\right)}$
$\displaystyle\leq\gamma\sqrt{\frac{1+\frac{\sigma_{1}^{2}d}{\|\mu_{1}\|_{2}^{2}}}{m\left(1-\frac{1}{\sqrt{1+\frac{\sigma_{0}^{2}d}{\|\mu_{0}\|_{2}^{2}}}}\right)}}\sqrt{\alpha\lambda_{\mathrm{max}}+5\mathcal{O}\left(\sqrt{\frac{d}{n}}+\sqrt{\frac{\log(\frac{2}{\delta})}{n}}\right)}$
$\displaystyle\leq\mathcal{O}\left(\gamma\sqrt{\frac{d}{m}\left(\alpha\lambda_{\mathrm{max}}+\sqrt{\frac{d}{n}}+\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}\right)}\right).$
(43)

Using (24),(26) and (A), we have

$\displaystyle\bigg{|}\mathbb{E}_{\hat{P}_{0}^{m}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta\right)\right]-\mathbb{E}_{P_{0}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta\right)\right]\bigg{|}\leq$
$\displaystyle\mathcal{O}\left(\gamma\sqrt{\frac{d}{m}\left(\alpha\lambda_{\mathrm{max}}+\sqrt{\frac{d}{n}}+\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}\right)}+\sqrt{\frac{\log{1/\delta}}{m}}\right),$
(44)

for all $\theta\in\tilde{\Theta}$, where $\tilde{\Theta}$ is defined as in
(25). Now, we need to demonstrate that the parameter $\theta^{*}$ that
minimizes the expected robust loss also satisfies the constraint defined in
(23). Given the data generating distribution in here, we know that
$\theta^{*}$ also minimizes the expected non-robust loss. Therefore, we have

$\theta^{*}=\operatorname*{\arg\\!\min}_{\theta\in\Theta}{\mathbb{E}_{P_{0}}\left[l\left(\boldsymbol{X},y;\theta\right)\right]},$
(45)

where for the loss function, cost functions and distributions considered in
here we have:

$\displaystyle\theta^{*}=$
$\displaystyle\operatorname*{\arg\\!\min}_{\theta\in\Theta}{\mathbb{P}_{u\sim\mathcal{N}\left(\langle\theta,\boldsymbol{\mu}_{0}\rangle,\sigma^{2}\|\theta\|_{2}^{2}\right)}\left(u\leq
0\right)}$ $\displaystyle=$
$\displaystyle\operatorname*{\arg\\!\min}_{\theta\in\Theta}{\mathcal{Q}\left(\frac{\langle\theta,\boldsymbol{\mu}_{0}\rangle^{2}}{\sigma^{2}\|\theta\|_{2}^{2}}\right)}$
$\displaystyle=$
$\displaystyle\frac{\boldsymbol{\mu}_{0}}{\|\boldsymbol{\mu}_{0}\|_{2}}.$ (46)

In the setting of the Theorem, we also have:

$\displaystyle\|\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}\|_{2}\leq\alpha.$

Due to the Auxiliary Lemma B.2, we know that if we set

$\gamma^{\prime}=\frac{1}{\hat{\lambda}_{\mathrm{max}}\log{n}+\mathcal{O}(\frac{d}{n})},~{}s=1-\gamma^{\prime}\left(\hat{\lambda}_{\mathrm{max}}\left(1-\alpha\right)-\mathcal{O}\left(\sqrt{\frac{d}{n}}\right)\right),$
(47)

then with high probability $\theta^{*}\in\tilde{\Theta}$ and the following
holds:

$\displaystyle\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P_{0}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\hat{\theta}^{\mathrm{RSS}}\right)\right]\leq~{}$
$\displaystyle\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim{\hat{P}_{0}^{m}}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\hat{\theta}^{\mathrm{RSS}}\right)\right]$
$\displaystyle+\mathcal{O}$
$\displaystyle\left(\gamma\sqrt{\frac{d}{m}\left(\alpha\lambda_{\mathrm{max}}+\sqrt{\frac{d}{n}}+\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}\right)}+\sqrt{\frac{\log{1/\delta}}{m}}\right)$
$\displaystyle\leq~{}$
$\displaystyle\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim{\hat{P}_{0}^{m}}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta^{*}\right)\right]$
$\displaystyle+\mathcal{O}$
$\displaystyle\left(\gamma\sqrt{\frac{d}{m}\left(\alpha\lambda_{\mathrm{max}}+\sqrt{\frac{d}{n}}+\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}\right)}+\sqrt{\frac{\log{1/\delta}}{m}}\right)$
$\displaystyle\leq~{}$
$\displaystyle{\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P_{0}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta^{*}\right)\right]}$
$\displaystyle+\mathcal{O}$
$\displaystyle\left(\gamma\sqrt{\frac{d}{m}\left(\alpha\lambda_{\mathrm{max}}+\sqrt{\frac{d}{n}}+\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}\right)}+\sqrt{\frac{\log{1/\delta}}{m}}\right).$
(48)

Now, let’s consider a 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 $n+m/2$ unlabeled samples and the bound above
inequalities changes as follows:

$\displaystyle\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P_{0}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\hat{\theta}^{\mathrm{RSS}}\right)\right]\leq~{}$
$\displaystyle{\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P_{0}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta^{*}\right)\right]}$
$\displaystyle+\mathcal{O}$
$\displaystyle\left(\gamma\sqrt{\frac{2d}{m}\left(\alpha\lambda_{\mathrm{max}}+\sqrt{\frac{2d}{2n+m}}+\sqrt{\frac{2\log{\frac{1}{\delta}}}{2n+m}}\right)}+\sqrt{\frac{2\log{1/\delta}}{m}}\right),$
(49)

which completes the proof. ∎

###### Proof of Theorem 4.2.

Using Theorem 4.1 and Auxiliary Lemma B.1, with probability more than
$1-\delta$ we have:

$\displaystyle R\left(\hat{\theta}^{\mathrm{RSS}},P_{0}\right)\leq~{}$
$\displaystyle\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P_{0}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\hat{\theta}^{\mathrm{RSS}}\right)\right]$
$\displaystyle\leq~{}$
$\displaystyle{\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P_{0}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta^{*}\right)\right]}+\mathcal{O}\left(\gamma\sqrt{\frac{2d}{m}\left(\alpha\lambda_{\mathrm{max}}+\sqrt{\frac{2d+2\log{\frac{1}{\delta}}}{2n+m}}\right)}+\sqrt{\frac{2\log{1/\delta}}{m}}\right)$
$\displaystyle\leq~{}$ $\displaystyle
R\left(\theta^{*},P_{0}\right)+\frac{e^{\frac{-\langle\theta^{*},\mu_{0}\rangle^{2}}{2\sigma_{0}^{2}}}}{2\gamma\sigma_{0}\sqrt{2\pi}}+\mathcal{O}\left(\gamma\sqrt{\frac{2d}{m}\left(\alpha\lambda_{\mathrm{max}}+\sqrt{\frac{2d+2\log{\frac{1}{\delta}}}{2n+m}}\right)}+\sqrt{\frac{2\log{1/\delta}}{m}}\right).$
(50)

For the setting described in the statement of the theorem, we know that
$\theta^{*}=\mu_{0}$ and
$\hat{\lambda}_{\mathrm{max}}\leq\|\mu_{1}\|_{2}^{2}+\sigma_{1}^{2}+\sqrt{\frac{d}{n}}$.
By setting

$\gamma=\frac{e^{\frac{-\hat{\lambda}_{\mathrm{max}}}{4\sigma_{0}^{2}}}}{\sqrt{2\sigma_{0}\sqrt{2\pi}}}\left(\sqrt{\frac{2d}{m}\left(\alpha\hat{\lambda}_{\mathrm{max}}+\sqrt{\frac{2d+2\log{\frac{1}{\delta}}}{2n+m}}\right)}+\sqrt{2\frac{\log{1/\delta}}{m}}\right)^{-1/4},$

and subsequent substitution in (A), one has

$\displaystyle
R\left(\hat{\theta}^{\mathrm{RSS}},P_{0}\right)\leq~{}R\left(\theta^{*},P_{0}\right)$
$\displaystyle+~{}\mathcal{O}\left(\frac{e^{\frac{-\|\mu_{0}\|_{2}^{2}}{4\sigma_{0}^{2}}}}{\sqrt{2\sigma_{0}\sqrt{2\pi}}}\left(\left(\|\mu_{1}\|_{2}^{2}+\sigma_{1}^{2}\right)\frac{2d}{m}\alpha+\frac{2d}{m}\sqrt{\frac{2d+\log{\frac{1}{\delta}}}{2n+m}}\right)^{1/4}+\sqrt{\frac{2\log{1/\delta}}{m}}\right).$
(51)

∎

###### Proof of Corollary 4.4.

Due to the result of Theorem 4.2, to have an advantage over the ERM method we
should have:

$\left(\frac{2d\alpha}{m}+\frac{2d}{m}\sqrt{\frac{2d}{2n+m}}\right)^{\frac{1}{4}}\leq\sqrt{\frac{d}{m}}.$
(52)

If we have the following inequality it can be seen that the above inequality
will be satisfied:

$\alpha\leq\frac{d}{m},~{}n\geq\frac{m^{2}}{d}.$ (53)

It can be seen that if we have $\alpha\leq\mathcal{O}\left(\frac{1}{d}\right)$
and $n>\Omega\left(d^{3}\right)$, then with high probability we have :

$e_{P}\left(\hat{\theta}^{\mathrm{RSS}}\right)\leq\mathcal{O}\left(\frac{1}{m}\right)^{\frac{1}{4}}+\sqrt{\frac{\log{\frac{1}{\delta}}}{m}}.$
(54)

Therefore if we aim to have an excess risk less than $\epsilon$ we should have
at least
$\max\left\\{\frac{1}{\epsilon^{4}},\frac{\log{\frac{1}{\delta}}}{\epsilon^{2}}\right\\}$
samples which is independent from the dimension of data.

∎

###### Proof of theorem 4.5.

From the manuscript we know that $\hat{\theta}^{\mathrm{RSS}}$ is the result
of the following optimization problem:

$\displaystyle\hat{\theta}^{\mathrm{RSS}}\triangleq\operatorname*{\arg\\!\min}_{\theta\in\Theta}~{}\left\\{\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i},y_{i};\theta\right)+\frac{\lambda}{n}\sum_{j=1}^{n}\phi_{\gamma^{\prime}}\left(\boldsymbol{X}^{\prime}_{j},h_{\theta}\left(\boldsymbol{X}^{\prime}_{j}\right);\theta\right)\right\\}.$
(55)

According to Lagrange duality, it is known that there exists $s\geq 0$ such
that $\hat{\theta}^{\mathrm{RSS}}$ is also the result of the following
optimization problem:

$\hat{\theta}^{\mathrm{RSS}}=\operatorname*{\arg\\!\min}_{\theta:\frac{1}{n}\sum_{j=1}^{n}\phi_{\gamma^{\prime}}\left(\boldsymbol{X}^{\prime}_{j},h_{\theta}\left(\boldsymbol{X}^{\prime}_{j}\right);\theta\right)\leq
s}{\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i},y_{i};\theta\right)}.$
(56)

To prove the theorem, we need to establish an upper bound on the distance
between the expected robust loss of $\hat{\theta}^{\mathrm{RSS}}$ 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

$\frac{1}{n}\sum_{j=1}^{n}\phi_{\gamma^{\prime}}\left(\boldsymbol{X}^{\prime}_{j},h_{\theta}\left(\boldsymbol{X}^{\prime}_{j}\right);\theta\right)\leq
s,$ (57)

and then, we demonstrate that the parameter $\theta^{\star}$, which achieves
the best possible robust loss, satisfies (57). Suppose that the loss function
is bounded with $b$,

$\displaystyle l\left(\boldsymbol{X},y;\theta\right)\leq
b,~{}\forall\theta,\boldsymbol{X},y,$
$\displaystyle\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta\right)\leq
b,~{}\forall c,\gamma,\theta,\boldsymbol{X},y,$

where the second inequality results from the first one. Therefore,
$\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i},y_{i};\theta\right)$
has the bounded difference property with parameter ${b}/{m}$, which results
that

$\displaystyle\Phi\left(P_{0},S_{0},\gamma,c\right)=\sup_{\theta\in\tilde{\Theta}}{\left(\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i},y_{i};\theta\right)-\mathbb{E}_{P_{0}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta\right)\right]\right)},$
(58)

also has the bounded difference property with parameter ${b}/{m}$, where
$\tilde{\Theta}$ is defined as

$\tilde{\Theta}\triangleq\left\\{\theta:\frac{1}{n}\sum_{j=1}^{n}\phi_{\gamma^{\prime}}\left(\boldsymbol{X}^{\prime}_{j},h_{\theta}\left(\boldsymbol{X}^{\prime}_{j}\right);\theta\right)\leq
s\right\\}.$ (59)

So, we have the following inequality with probability more than $1-\delta$:

$\Phi\left(P_{0},S_{0},\gamma,c\right)\leq\mathbb{E}\left[\Phi\left(P_{0},S_{0},\gamma,c\right)\right]+\sqrt{\frac{\log{1/\delta}}{m}},\quad\forall\theta\in\tilde{\Theta}.$
(60)

In the above inequality we can give an upper-bound for the first term in the
right hand side of the inequality as follows:

$\displaystyle\mathbb{E}\left[\Phi\left(P_{0},S_{0},\gamma,c\right)\right]=$
$\displaystyle\mathbb{E}_{S_{0}\sim
P_{0}^{m}}\left[\sup_{\theta\in\tilde{\Theta}}{\left(\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i},y_{i};\theta\right)-\mathbb{E}_{P_{0}}\left[\phi_{\gamma}^{c}\left(\theta;\boldsymbol{X},y\right)\right]\right)}\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{S_{0},S_{0}^{\prime}}\left[\sup_{\theta\in\tilde{\Theta}}{\left(\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i},y_{i};\theta\right)-\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i}^{\prime},y_{i}^{\prime};\theta\right)\right)}\right]$
$\displaystyle\leq$ $\displaystyle
2\mathbb{E}_{S_{0},\epsilon}\left[\sup_{\theta\in\tilde{\Theta}}{\frac{1}{m}\sum_{\left(\boldsymbol{X}_{i},y_{i}\right)\in
S_{0}}{\epsilon_{i}\phi_{\gamma}^{c}\left(\theta;\boldsymbol{X}_{i},y_{i}\right)}}\right].$
(61)

Consider the loss function mentioned in the Theorem 4.5, and the following
cost functions $c,c^{\prime}$

$c(\boldsymbol{X},\boldsymbol{X}^{\prime})=\|\boldsymbol{X}-\boldsymbol{X}^{\prime}\|_{2},\quad
c^{\prime}(\boldsymbol{X},\boldsymbol{X}^{\prime})=\|\boldsymbol{X}-\boldsymbol{X}^{\prime}\|_{2}^{2}.$

With these loss and cost functions we can rewrite $\phi_{\gamma}^{c}$ and
$\phi_{\gamma^{\prime}}^{c^{\prime}}$ as follows:

$\displaystyle\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta\right)=$
$\displaystyle\min\left\\{1,\max\left\\{0,1-\gamma
y\langle\theta,\boldsymbol{X}\rangle\right\\}\right\\},$ (62)
$\displaystyle\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},h_{\theta}\left(\boldsymbol{X}\right);\theta\right)=$
$\displaystyle\max\left\\{0,1-\gamma^{\prime}\langle\theta,\boldsymbol{X}\rangle^{2}\right\\}.$
(63)

As we can see $\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta\right)$ is a
$\gamma$-lipschitz function of $y\langle\theta,\boldsymbol{X}\rangle$,
therefore due to the Talagrand’s lemma we can continue inequalities in (A) as
follows:

$\displaystyle\mathbb{E}\left[\Phi\left(P+0,S_{0},\gamma,c\right)\right]\leq$
$\displaystyle\mathbb{E}_{S_{0},\epsilon}\left[\sup_{\theta\in\tilde{\Theta}}{\frac{1}{m}\sum_{\left(\boldsymbol{X}_{i},y_{i}\right)\in
S_{0}}{\epsilon_{i}\phi_{\gamma}^{c}\left(\boldsymbol{X}_{i},y_{i};\theta\right)}}\right]$
$\displaystyle\leq$
$\displaystyle\gamma\mathbb{E}_{S_{0},\epsilon}\left[\sup_{\theta\in\tilde{\Theta}}{\frac{1}{m}\sum_{\left(\boldsymbol{X}_{i},y_{i}\right)\in
S_{0}}{\epsilon_{i}y_{i}\langle\theta,\boldsymbol{X}_{i}\rangle}}\right]$
$\displaystyle\leq$
$\displaystyle\gamma\mathbb{E}_{S_{0},\epsilon}\left[\sup_{\theta\in\tilde{\Theta}}{\langle\theta,\frac{1}{m}\sum_{\boldsymbol{X}_{i}\in
S_{0}}{\epsilon_{i}y_{i}\boldsymbol{X}_{i}}\rangle}\right].$ (64)

Now suppose that we weaken the constraint in the above inequalities as
follows:

$\displaystyle s\geq$
$\displaystyle\frac{1}{n}\sum_{j=1}^{n}\phi_{\gamma^{\prime}}\left(\boldsymbol{X}^{\prime}_{j},h_{\theta}\left(\boldsymbol{X}^{\prime}_{j}\right);\theta\right)$
$\displaystyle\geq$
$\displaystyle\mathbb{E}_{P_{1X,\theta}}\left[\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},y;\theta\right)\right]-\frac{4\gamma^{\prime}\left(\operatorname{Tr}\left(\Sigma_{1}\right)+\|\boldsymbol{\mu}_{1}\|_{2}^{2}\right)}{\sqrt{n}}-\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}$
(65) $\displaystyle\geq$
$\displaystyle\frac{4e^{-\frac{\langle\theta,\boldsymbol{\mu}_{1}\rangle^{2}}{2\theta^{T}\Sigma_{1}\theta}}}{3\gamma^{\prime}}-\frac{4\gamma^{\prime}\left(\operatorname{Tr}\left(\Sigma_{1}\right)+\|\boldsymbol{\mu}_{1}\|_{2}^{2}\right)}{\sqrt{n}}-\sqrt{\frac{\log{\frac{1}{\delta}}}{n}},$
(66)

where we use Auxiliary Lemma B.3 in the (65) and Auxiliary Lemma B.4 in the
(66). Suppose that we set $s$ as follows:

$s=\sup_{\theta\in\Theta}{\frac{1}{n}\sum_{\boldsymbol{X}_{i}\in
S_{1}^{\prime}}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i},h_{\theta}\left(\boldsymbol{X}_{i}\right);\theta\right)}}+\frac{12\gamma^{\prime}\operatorname{Tr}\left(\hat{\Sigma}\left(S_{1}^{\prime}\right)\right)}{\sqrt{n}}+3\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}+\alpha,$
(67)

where in the above equation $S_{1}^{\prime}$ is generated in a same way but
independent of $S_{1}$, and $\hat{\Sigma}\left(S_{1}^{\prime}\right)$ is the
sample covariance matrix of $S_{1}$. Therefore we have the following upper-
bound for $s$:

$\displaystyle s=$
$\displaystyle\sup_{\theta\in\Theta}{\frac{1}{n}\sum_{\boldsymbol{X}_{i}\in
S_{1}^{\prime}}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i},h_{\theta}\left(\boldsymbol{X}_{i}\right);\theta\right)}}+\frac{12\gamma^{\prime}\operatorname{Tr}\left(\hat{\Sigma}\left(S_{1}^{\prime}\right)\right)}{\sqrt{n}}+3\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}+\alpha$
$\displaystyle\leq$
$\displaystyle\sup_{\theta\in\Theta}{\mathbb{E}_{P_{1X,\theta}}\left[\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},h_{\theta}\left(\boldsymbol{X}_{i}\right);\theta\right)\right]}+\frac{24\gamma^{\prime}\left(\operatorname{Tr}\left(\Sigma_{1}\right)+\|\boldsymbol{\mu}_{1}\|_{2}^{2}\right)}{\sqrt{n}}+6\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}+32\sqrt{\frac{d}{n}}+\alpha$
(68) $\displaystyle\leq$
$\displaystyle\sup_{\theta\in\Theta}{\frac{4e^{-\frac{\langle\theta,\boldsymbol{\mu}_{1}\rangle^{2}}{2\theta^{T}\Sigma_{1}\theta}}}{3\sqrt{\gamma^{\prime}}}}+\frac{24\gamma^{\prime}\left(\operatorname{Tr}\left(\Sigma_{1}\right)+\|\boldsymbol{\mu}_{1}\|_{2}^{2}\right)}{\sqrt{n}}+6\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}+32\sqrt{\frac{d}{n}}+\alpha$
$\displaystyle\leq$
$\displaystyle\frac{4e^{-\frac{\boldsymbol{\mu}_{1}^{T}\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}}{2}}}{3\sqrt{\gamma^{\prime}}}+\frac{24\gamma^{\prime}\left(\operatorname{Tr}\left(\Sigma_{1}\right)+\|\boldsymbol{\mu}_{1}\|_{2}^{2}\right)}{\sqrt{n}}+6\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}+32\sqrt{\frac{d}{n}}+\alpha$
(69)

where in the (68) we use the result of Auxiliary Lemma B.4. In the (69) we
insert $\theta=\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}$ which maximizes
$e^{-\frac{\boldsymbol{\mu}_{1}^{T}\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}}{2}}$.
We use (65) to (69), to define $\tilde{\Theta}_{w}$, which is a super-set for
$\tilde{\Theta}$, as follows:

$\displaystyle\tilde{\Theta}_{w}=$
$\displaystyle\left\\{\theta\in\Theta:\frac{4e^{-\frac{\langle\theta,\boldsymbol{\mu}_{1}\rangle^{2}}{2\theta^{T}\Sigma_{1}\theta}}}{3\sqrt{\gamma^{\prime}}}\leq\frac{4e^{-\frac{\boldsymbol{\mu}_{1}^{T}\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}}{2}}}{3\sqrt{\gamma^{\prime}}}+\frac{24\gamma^{\prime}\left(\operatorname{Tr}\left(\Sigma_{1}\right)+\|\boldsymbol{\mu}_{1}\|_{2}^{2}\right)}{\sqrt{n}}+6\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}+32\sqrt{\frac{d}{n}}+\alpha\right\\}$
$\displaystyle=$
$\displaystyle\bigg{\\{}\theta\in\Theta:\frac{\langle\theta,\boldsymbol{\mu}_{1}\rangle^{2}}{\theta^{T}\Sigma_{1}\theta}\geq\boldsymbol{\mu}_{1}\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}-$
$\displaystyle\frac{e^{\frac{\boldsymbol{\mu}_{1}\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}}{2}}\left(18\gamma^{\prime
2}\left(\operatorname{Tr}\left(\Sigma_{1}\right)+\|\boldsymbol{\mu}_{1}\|_{2}^{2}\right)+5\gamma^{\prime}\sqrt{\log{\frac{1}{\delta}}}+24\sqrt{d}+4\alpha\sqrt{n\gamma^{\prime}}\right)}{2\sqrt{n}}\bigg{\\}}$
$\displaystyle=$
$\displaystyle\bigg{\\{}\theta\in\Theta:\boldsymbol{\mu}_{1}\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}-\frac{\langle\theta,\boldsymbol{\mu}_{1}\rangle^{2}}{\theta^{T}\Sigma_{1}\theta}\leq$
$\displaystyle\frac{e^{\frac{\boldsymbol{\mu}_{1}\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}}{2}}\left(18\gamma^{\prime
2}\left(\operatorname{Tr}\left(\Sigma_{1}\right)+\|\boldsymbol{\mu}_{1}\|_{2}^{2}\right)+5\gamma^{\prime}\sqrt{\log{\frac{1}{\delta}}}+24\sqrt{d}+4\alpha\sqrt{n\gamma^{\prime}}\right)}{2\sqrt{n}}\bigg{\\}}.$
(70)

We can write
$\theta=\frac{\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}+\epsilon\boldsymbol{v}}{\|\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}+\epsilon\boldsymbol{v}\|_{2}}$,
where $v$ is a vector which its Euclidean norm is equal to $1$ and belongs to
the hyperplane orthogonal to $\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}$, and
$\epsilon\in\mathbb{R}$. If we use this new notation we can rewrite
$\tilde{\Theta}_{w}$ as follows:

$\displaystyle\tilde{\Theta}_{w}=$
$\displaystyle\bigg{\\{}\theta=\frac{\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}+\epsilon\boldsymbol{v}}{\|\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}+\epsilon\boldsymbol{v}\|_{2}}:\epsilon^{2}\boldsymbol{v}^{T}\left(\Sigma_{1}-\frac{\boldsymbol{\mu}_{1}\boldsymbol{\mu}_{1}^{T}}{\boldsymbol{\mu}_{1}^{T}\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}}\right)\boldsymbol{v}\leq
t,~{}\boldsymbol{v}^{T}\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}=0,\|\boldsymbol{v}\|_{2}=1\bigg{\\}},$
(71) $\displaystyle t=$
$\displaystyle\frac{e^{\frac{\boldsymbol{\mu}_{1}\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}}{2}}\left(18\gamma^{\prime
2}\left(\operatorname{Tr}\left(\Sigma_{1}\right)+\|\boldsymbol{\mu}_{1}\|_{2}^{2}\right)+5\gamma^{\prime}\sqrt{\log{\frac{1}{\delta}}}+24\sqrt{d}+4\alpha\sqrt{n\gamma^{\prime}}\right)}{2\sqrt{n}}$
(72)

where due to Auxiliary Lemma B.7 we have:

$\boldsymbol{v}^{T}\left(\Sigma_{1}-\frac{\boldsymbol{\mu}_{1}\boldsymbol{\mu}_{1}^{T}}{\boldsymbol{\mu}_{1}^{T}\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}}\right)\boldsymbol{v}\geq\frac{\Delta\left(\Sigma_{1}\right)}{d\kappa_{1}\kappa_{1}^{\prime}},$
(73)

where

$\displaystyle\kappa_{1}=$
$\displaystyle\frac{\lambda_{\mathrm{max}}\left(\Sigma_{1}\right)}{\lambda_{\mathrm{min}}\left(\Sigma_{1}\right)},~{}\kappa_{1}^{\prime}=\frac{\lambda_{\mathrm{max}}\left(\Sigma_{1}\right)}{\Delta\left(\Sigma_{1}\right)}$
$\displaystyle\Delta\left(\Sigma_{1}\right)=$
$\displaystyle\min\left\\{\lambda_{i}\left(\Sigma_{1}\right)-\lambda_{j}\left(\Sigma_{1}\right)\right\\},~{}\forall
i,j:\lambda_{i}\left(\Sigma_{1}\right)\neq\lambda_{j}\left(\Sigma_{1}\right).$

Therefore we can weaken $\tilde{\Theta}_{w}$ as follows:

$\displaystyle\tilde{\Theta}_{w}=$
$\displaystyle\bigg{\\{}\theta=\frac{\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}+\epsilon\boldsymbol{v}}{\|\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}+\epsilon\boldsymbol{v}\|_{2}}:\epsilon\leq
t^{\prime},~{}\boldsymbol{v}^{T}\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}=0,\|\boldsymbol{v}\|_{2}=1\bigg{\\}},$
(74) $\displaystyle t^{\prime}=$
$\displaystyle\sqrt{\frac{d\kappa_{1}\kappa_{1}^{\prime}}{\Delta\left(\Sigma_{1}\right)}\frac{e^{\frac{\boldsymbol{\mu}_{1}\Sigma_{1}^{-1}\boldsymbol{\mu}_{1}}{2}}\left(18\gamma^{\prime
2}\left(\operatorname{Tr}\left(\Sigma_{1}\right)+\|\boldsymbol{\mu}_{1}\|_{2}^{2}\right)+5\gamma^{\prime}\sqrt{\log{\frac{1}{\delta}}}+24\sqrt{d}+4\alpha\sqrt{n\gamma^{\prime}}\right)}{2\sqrt{n}}}.$
(75)

Due to the definition of $\tilde{\Theta}_{w}$ in 74 and the fact that it is a
super-set for $\tilde{\Theta}$ we can continue (A) as follows:

$\displaystyle\mathbb{E}\left[\Phi\left(P+0,S_{0},\gamma,c\right)\right]\leq$
$\displaystyle\gamma\mathbb{E}_{S_{0},\epsilon}\left[\sup_{\theta\in\tilde{\Theta}}{\langle\theta,\frac{1}{m}\sum_{\boldsymbol{X}_{i}\in
S_{0}}{\epsilon_{i}y_{i}\boldsymbol{X}_{i}}\rangle}\right]$
$\displaystyle\leq$
$\displaystyle\gamma\mathbb{E}_{S_{0},\epsilon}\left[\sup_{\theta\in\tilde{\Theta}_{w}}{\langle\theta,\frac{1}{m}\sum_{\boldsymbol{X}_{i}\in
S_{0}}{\epsilon_{i}y_{i}\boldsymbol{X}_{i}}\rangle}\right]$
$\displaystyle\leq$ $\displaystyle\gamma
t^{\prime}\sqrt{\frac{\lambda_{\mathrm{max}}\left(\Sigma_{1}\right)\mathbb{E}\left[\|\boldsymbol{X}\|_{2}^{2}\right]}{m\|\boldsymbol{\mu}_{1}\|_{2}}}$
$\displaystyle\leq$ $\displaystyle\gamma
t^{\prime}\sqrt{\frac{\left(\|\boldsymbol{\mu}_{1}\|_{2}^{2}+\operatorname{Tr}\left(\Sigma_{1}\right)\right)\lambda_{\mathrm{max}}\left(\Sigma_{1}\right)}{m\|\boldsymbol{\mu}_{1}\|_{2}}},$
(76)

Using Inequalities (A) and (60) we have:

$\displaystyle\bigg{|}\frac{1}{m}\sum_{i=1}^{m}\phi_{\gamma}\left(\boldsymbol{X}_{i},y_{i};\theta\right)-\mathbb{E}_{P_{0}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y\right);\theta\right]\bigg{|}\leq\gamma
t^{\prime}\sqrt{\frac{\left(\|\boldsymbol{\mu}_{1}\|_{2}^{2}+\operatorname{Tr}\left(\Sigma_{1}\right)\right)\lambda_{\mathrm{max}}\left(\Sigma_{1}\right)}{m\|\boldsymbol{\mu}_{1}\|_{2}}}+\sqrt{\frac{\log{\frac{1}{\delta}}}{m}}.$
(77)

Suppose that we define $\theta^{*}$ as follows:

$\theta^{*}=\operatorname*{\arg\\!\min}_{\theta\in\Theta}{\mathbb{E}_{P_{0}}\left[l\left(\boldsymbol{X},y;\theta\right)\right]}.$
(78)

For the loss function, cost functions and distributions considered in the
Theorem 4.5 we have:

$\displaystyle\theta^{*}=\operatorname*{\arg\\!\min}_{\theta\in\Theta}{\mathbb{P}_{u\sim\mathcal{N}\left(\langle\theta,\boldsymbol{\mu}_{0}\rangle,\theta^{T}\Sigma_{0}\theta\right)}\left(u\leq
0\right)}=\operatorname*{\arg\\!\min}_{\theta\in\Theta}{\mathcal{Q}\left(\frac{\langle\theta,\boldsymbol{\mu}_{0}\rangle^{2}}{\theta^{T}\Sigma_{0}\theta}\right)}=\frac{\Sigma_{0}^{-1}\boldsymbol{\mu}_{0}}{\|\Sigma_{0}^{-1}\boldsymbol{\mu}_{0}\|_{2}}.$
(79)

In the setting of the theorem, we also have:

$\displaystyle\|\boldsymbol{\mu}_{0}-\boldsymbol{\mu}_{1}\|_{2}\leq\alpha,\|\Sigma_{1}-\Sigma_{0}\|_{2}\leq\alpha$

Due to the Lemma B.6 we know that if we set $s$ as in (67), then with high
probability $\theta^{*}\in\tilde{\Theta}$, and we have the following:

$\displaystyle\mathbb{E}_{P_{0}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\hat{\theta}^{\mathrm{RSS}}\right)\right]\leq\mathbb{E}_{P_{0}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta^{*}\right)\right]+\gamma
t^{\prime}\sqrt{\frac{\left(\|\boldsymbol{\mu}_{1}\|_{2}^{2}+\operatorname{Tr}\left(\Sigma_{1}\right)\right)\lambda_{\mathrm{max}}\left(\Sigma_{1}\right)}{m\|\boldsymbol{\mu}_{1}\|_{2}}}+\sqrt{\frac{\log{\frac{1}{\delta}}}{m}}.$
(80)

Using the result of Auxiliary Lemma B.5 and the above inequality we have:

$\displaystyle\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P_{0}}\left[l\left(\boldsymbol{X},y;\hat{\theta}^{\mathrm{RSS}}\right)\right]\leq$
$\displaystyle\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P_{0}}\left[l\left(\boldsymbol{X},y;\theta^{*}\right)\right]+\frac{e^{-\frac{\langle\theta^{*},\boldsymbol{\mu}_{0}\rangle^{2}}{2\theta^{*T}\Sigma_{0}\theta^{*}}}}{2\gamma}$
$\displaystyle+$ $\displaystyle\gamma
t^{\prime}\sqrt{\frac{\left(\|\boldsymbol{\mu}_{1}\|_{2}^{2}+\operatorname{Tr}\left(\Sigma_{1}\right)\right)\lambda_{\mathrm{max}}\left(\Sigma_{1}\right)}{m\|\boldsymbol{\mu}_{1}\|_{2}}}+\sqrt{\frac{\log{\frac{1}{\delta}}}{m}}.$
(81)

Therefore if we set $\gamma$ as follows:

$\gamma=\sqrt{\frac{\sqrt{m}}{2t^{\prime}\lambda_{\mathrm{max}}\left(\hat{\Sigma_{1}}\left(S_{1}^{\prime}\right)\right)}},$
(82)

then we have:

$\displaystyle\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P_{0}}\left[l\left(\boldsymbol{X},y;\hat{\theta}^{\mathrm{RSS}}\right)\right]\leq$
$\displaystyle\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P_{0}}\left[l\left(\boldsymbol{X},y;\theta^{*}\right)\right]$ $\displaystyle+$
$\displaystyle\sqrt{t^{\prime}\frac{\lambda_{\mathrm{max}}\left(\Sigma_{1}\right)}{\sqrt{m}\|\boldsymbol{\mu}_{1}\|_{2}}}+\sqrt{\frac{\log{\frac{1}{\delta}}}{m}}.$
(83)

Now, if we split our labeled samples into two equal parts, each containing
$m/2$ samples, and combine the unlabeled set with the second part, we have
$m/2$ labeled samples and $n+m/2$ unlabeled samples. When we set $t^{\prime}$
from (75) in this new scenario, the proof will be complete. ∎

##  Appendix B Auxiliary Lemmas

######  Auxiliary Lemma B.1.

Consider the setting described in Theorem 4.1. let us define
$f_{\Theta,P}\left(\theta,\gamma\right)$ as

$f_{\Theta,P}\left(\theta,\gamma\right)=\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta\right)\right]-\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P}\left[\ell\left(\boldsymbol{X},y;\theta\right)\right].$ (84)

Then, for the loss and cost functions described in Theorem 4.1,
$P=\mathcal{N}_{y\boldsymbol{\mu},\sigma}\left(\boldsymbol{X},y\right)$, and
the class of linear classifiers with $|\theta|_{2}=1$, the function
$f_{\Theta,P}\left(\theta,\gamma\right)$ satisfies the following inequality:

$f_{\Theta,P}\left(\theta,\gamma\right)\leq\frac{e^{\frac{-\langle\theta,\mu\rangle^{2}}{2\sigma^{2}}}}{2\gamma\sigma\sqrt{2\pi}}.$
(85)

###### Proof.

For the setting described in the lemma we have:

$u=y\langle\theta,\boldsymbol{X}\rangle\sim\mathcal{N}\left(\langle\theta,\mu\rangle,\sigma^{2}\right).$
(86)

Therefore we can calculate an upper-bound for
$f_{\Theta,P}\left(\theta,\gamma\right)$ as follows:

$\displaystyle\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta\right)\right]-\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P}\left[l\left(\boldsymbol{X},y;\theta\right)\right]$
$\displaystyle=\int_{u=0}^{1/\gamma}{\frac{1}{\sqrt{2\pi\sigma^{2}}}\left(1-\gamma
u\right)e^{-\frac{\left(u-\langle\theta,\mu\rangle\right)^{2}}{2\sigma^{2}}}\,du}$
$\displaystyle\leq\int_{u=0}^{1/\gamma}{\frac{1}{\sqrt{2\pi\sigma^{2}}}\left(1-\gamma
u\right)e^{-\frac{\langle\theta,\mu\rangle^{2}}{2\sigma^{2}}}\,du}$
$\displaystyle\leq\frac{e^{-\frac{\langle\theta,\mu\rangle^{2}}{2\sigma^{2}}}}{2\gamma\sigma\sqrt{2\pi}}.$
(87)

And the proof is complete. ∎

######  Auxiliary Lemma B.2.

Consider the setting in Theorem 4.1 if we define $\theta^{*}$ as follows:

$\theta^{*}\triangleq\frac{\boldsymbol{\mu}_{0}}{\|\boldsymbol{\mu}_{0}\|_{2}},$
(88)

then with high probability we have:

$\frac{1}{n}\sum_{j=1}^{n}\phi_{\gamma^{\prime}}\left(\boldsymbol{X}^{\prime}_{j},h_{\theta}\left(\boldsymbol{X}^{\prime}_{j}\right);\theta\right)\leq
s,$

As long as we set:

$\gamma^{\prime}=\frac{1}{\hat{\lambda}_{\mathrm{max}}\log{n}+\mathcal{O}(\frac{d}{n})},~{}s=1-\gamma^{\prime}\left(\hat{\lambda}_{\mathrm{max}}\left(1-\alpha\right)-\mathcal{O}\left(\sqrt{\frac{d}{n}}\right)\right)$
(89)

###### Proof.

Due to the boundedness of $\phi_{\gamma^{\prime}}^{c^{\prime}}$ with
probability more than $1-\delta$ we have the following inequality:

$\displaystyle\frac{1}{n}\sum_{\boldsymbol{X}_{i}^{\prime}\in
S_{1}}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i}^{\prime},h_{\theta^{*}}\left(\boldsymbol{X}_{i}^{\prime}\right);\theta^{*}\right)}\leq$
$\displaystyle\mathbb{E}_{\boldsymbol{X}\sim
P_{1X}}\left[\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},h_{\theta^{*}}\left(\boldsymbol{X}\right);\theta^{*}\right)\right]+\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}$
(90) $\displaystyle=$ $\displaystyle\mathbb{E}_{\boldsymbol{X}\sim
P_{1X}}\left[\max\left\\{0,1-\gamma^{\prime}\langle\theta^{*},\boldsymbol{X}\rangle^{2}\right\\}\right]+\sqrt{\frac{\log{\frac{1}{\delta}}}{n}},$
(91)

where we have the following upper-bound for the first term in 91:

$\displaystyle\mathbb{E}_{\boldsymbol{X}\sim
P_{1X}}\left[\max\left\\{0,1-\gamma^{\prime}\langle\theta^{*},\boldsymbol{X}\rangle^{2}\right\\}\right]=$
$\displaystyle\mathbb{E}_{\boldsymbol{X}\sim
P_{1X}}\left[1-\gamma^{\prime}\langle\theta^{*},\boldsymbol{X}\rangle^{2}\right]$
$\displaystyle-\int_{\langle\theta^{*},\boldsymbol{X}\rangle^{2}\geq\frac{1}{\gamma^{\prime}}}{1-\gamma^{\prime}\langle\theta^{*},\boldsymbol{X}\rangle^{2}~{}dP_{1X}}$
$\displaystyle=$ $\displaystyle\mathbb{E}_{\boldsymbol{X}\sim
P_{1X}}\left[1-\gamma^{\prime}\langle\theta^{*},\boldsymbol{X}\rangle^{2}\right]$
$\displaystyle-\frac{1}{2}\int_{\langle\theta^{*},\boldsymbol{X}\rangle^{2}\geq\frac{1}{\gamma^{\prime}}}{1-\gamma^{\prime}\langle\theta^{*},\boldsymbol{X}\rangle^{2}~{}\mathcal{N}\left(\boldsymbol{\mu_{1}},\sigma_{1}^{2}I\right)}$
$\displaystyle-\frac{1}{2}\int_{\langle\theta^{*},\boldsymbol{X}\rangle^{2}\geq\frac{1}{\gamma^{\prime}}}{1-\gamma^{\prime}\langle\theta^{*},\boldsymbol{X}\rangle^{2}~{}\mathcal{N}\left(-\boldsymbol{\mu_{1}},\sigma_{1}^{2}I\right)}$
$\displaystyle\leq$ $\displaystyle\mathbb{E}_{\boldsymbol{X}\sim
P_{1X}}\left[1-\gamma^{\prime}\langle\theta^{*},\boldsymbol{X}\rangle^{2}\right]$
$\displaystyle-\int_{u\geq\frac{1}{\sigma_{1}\sqrt{\gamma^{\prime}}}-\frac{\langle\theta^{*},\boldsymbol{\mu}_{1}\rangle}{\sigma_{1}}}{1-\gamma^{\prime}\left(\langle\theta^{*},\boldsymbol{\mu}_{1}\rangle+\sigma_{1}u\right)^{2}~{}\mathcal{N}\left(0,\sigma_{1}^{2}\right)}$
$\displaystyle-\int_{u\leq-\frac{1}{\sigma_{1}\sqrt{\gamma^{\prime}}}+\frac{\langle\theta^{*},\boldsymbol{\mu}_{1}\rangle}{\sigma_{1}}}{1-\gamma^{\prime}\left(-\langle\theta^{*},\boldsymbol{\mu}_{1}\rangle+\sigma_{1}u\right)^{2}~{}\mathcal{N}\left(0,\sigma_{1}^{2}\right)}.$
(92)

Now if we set

$\gamma^{\prime}\leq\frac{1}{\left(\langle\theta^{*},\boldsymbol{\mu}_{1}\rangle+\sigma_{1}\sqrt{\log{n}}\rangle\right)^{2}}$
(93)

we can continue inequalities in B as follows:

$\displaystyle\mathbb{E}_{\boldsymbol{X}\sim
P_{1X}}\left[\max\left\\{0,1-\gamma^{\prime}\langle\theta^{*},\boldsymbol{X}\rangle^{2}\right\\}\right]\leq$
$\displaystyle\mathbb{E}_{\boldsymbol{X}\sim
P_{1X}}\left[1-\gamma^{\prime}\langle\theta^{*},\boldsymbol{X}\rangle^{2}\right]+\frac{1}{\sqrt{n}}$
$\displaystyle=$ $\displaystyle
1-\gamma^{\prime}\left(\langle\theta^{*},\boldsymbol{\mu}_{1}\rangle^{2}+\sigma_{1}^{2}\right)+\frac{1}{\sqrt{n}}.$
(94)

However, since we lack access to $\mu_{1}$, $\sigma_{1}$, or $\theta^{*}$, we
cannot directly obtain $\gamma^{\prime}$ from (93). Nevertheless, a suitable
choice for $\gamma^{\prime}$ that satisfies (93) and can be determined from
samples is:

$\gamma^{\prime}=\frac{1}{\hat{\lambda}_{\mathrm{max}}\log{n}+\mathcal{O}(\frac{d}{n})},$
(95)

where $\hat{\lambda}_{\mathrm{max}}$ is the maximum eigenvalue of the sample
covariance matrix,$\hat{\Sigma}$, of a set of $n$ unlabeled samples. Now from
Equations 90 and B we have:

$\frac{1}{n}\sum_{j=1}^{n}\phi_{\gamma^{\prime}}\left(\boldsymbol{X}^{\prime}_{j},h_{\theta}\left(\boldsymbol{X}^{\prime}_{j}\right);\theta\right)\leq
1-\gamma^{\prime}\left(\langle\theta^{*},\boldsymbol{\mu}_{1}\rangle^{2}+\sigma_{1}^{2}\right)+2\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}.$
(96)

To complete the proof we should show that :

$1-\gamma^{\prime}\left(\langle\theta^{*},\boldsymbol{\mu}_{1}\rangle^{2}+\sigma_{1}^{2}\right)+2\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}\leq
s,$ (97)

where due to the setting of this lemma we only need to set:

$s=1-\gamma^{\prime}\left(\hat{\lambda}_{\mathrm{max}}\left(1-\alpha\right)-\mathcal{O}\left(\sqrt{\frac{d}{n}}\right)\right).$
(98)

∎

######  Auxiliary Lemma B.3.

Consider the setting described in Theorem 4.5, if we define the function
$\phi_{\gamma^{\prime}}^{c^{\prime}}$ as follows

$\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},h_{\theta}\left(\boldsymbol{X}\right);\theta\right)=\max\left\\{0,1-\gamma^{\prime}\langle\theta,\boldsymbol{X}\rangle^{2}\right\\},$
(99)

then with probability greater than $1-\delta$, for $\forall\theta\in\Theta$,
with $\|\theta\|_{2}=1$ we have:

$\bigg{|}\frac{1}{n}\sum_{i=1}^{n}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i},h_{\theta}\left(\boldsymbol{X}_{i}\right);\theta\right)}-\mathbb{E}\left[\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},h_{\theta}\left(\boldsymbol{X}\right);\theta\right)\right]\bigg{|}\leq\frac{4\gamma^{\prime}\left(\operatorname{Tr}\left(\Sigma_{1}\right)+\|\boldsymbol{\mu}_{1}\|_{2}^{2}\right)}{\sqrt{n}}+\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}.$
(100)

###### Proof.

From the definition of $\phi_{\gamma^{\prime}}^{c^{\prime}}$ we know that this
function is bounded between $0$ and $1$, therefore the following function has
the bounded difference property with parameter $\frac{1}{n}$

$\Phi=\sup_{\theta\in\Theta}{\bigg{|}\frac{1}{n}\sum_{i=1}^{n}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i},h_{\theta}\left(\boldsymbol{X}_{i}\right);\theta\right)}-\mathbb{E}\left[\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},h_{\theta}\left(\boldsymbol{X}\right);\theta\right)\right]\bigg{|}}.$
(101)

So we can write the McDiarmid’s inequality for this function as follows:

$\Phi\leq\mathbb{E}\left[\Phi\right]+\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}.$
(102)

Now we try to give an upper-bound for the first term in the right-hand side of
the above inequality:

$\displaystyle\mathbb{E}\left[\Phi\right]=$
$\displaystyle\mathbb{E}_{\left\\{\boldsymbol{X}_{i}\right\\}_{1}^{n}}\left[\sup_{\theta\in\Theta}{\bigg{|}\frac{1}{n}\sum_{i=1}^{n}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i},h_{\theta}\left(\boldsymbol{X}_{i}\right);\theta\right)}-\mathbb{E}\left[\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},h_{\theta}\left(\boldsymbol{X}\right);\theta\right)\right]\bigg{|}}\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{\left\\{\boldsymbol{X}_{i}\right\\}_{1}^{n},\left\\{\boldsymbol{X}_{i}^{\prime}\right\\}_{1}^{n}}\left[\sup_{\theta\in\Theta}{\bigg{|}\frac{1}{n}\sum_{i=1}^{n}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i},h_{\theta}\left(\boldsymbol{X}_{i}\right);\theta\right)}-\frac{1}{n}\sum_{i=1}^{n}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}^{\prime}_{i},h_{\theta}\left(\boldsymbol{X}^{\prime}_{i}\right);\theta\right)}\bigg{|}}\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{\left\\{\boldsymbol{X}_{i}\right\\}_{1}^{n},\left\\{\boldsymbol{X}^{\prime}_{i}\right\\}_{1}^{n},\left\\{\epsilon_{i}\right\\}_{1}^{n}}\left[\sup_{\theta\in\Theta}{\epsilon_{i}\left(\frac{1}{n}\sum_{i=1}^{n}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i},h_{\theta}\left(\boldsymbol{X}_{i}\right);\theta\right)}-\frac{1}{n}\sum_{i=1}^{n}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}^{\prime}_{i},h_{\theta}\left(\boldsymbol{X}^{\prime}_{i}\right);\theta\right)}\right)}\right]$
(103) $\displaystyle\leq$ $\displaystyle
2\mathbb{E}_{\left\\{\boldsymbol{X}_{i}\right\\}_{1}^{n},\left\\{\epsilon_{i}\right\\}_{1}^{n}}\left[\sup_{\theta\in\Theta}{\frac{1}{n}\sum_{i=1}^{n}{\epsilon_{i}\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i},h_{\theta}\left(\boldsymbol{X}_{i}\right);\theta\right)}}\right]$
$\displaystyle\leq$ $\displaystyle
2\gamma^{\prime}\mathbb{E}_{\left\\{\boldsymbol{X}_{i}\right\\}_{1}^{n},\left\\{\epsilon_{i}\right\\}_{1}^{n}}\left[\sup_{\theta\in\Theta}{\frac{1}{n}\sum_{i=1}^{n}{\epsilon_{i}\langle\theta,\boldsymbol{X}_{i}\rangle^{2}}}\right]$
$\displaystyle=$ $\displaystyle
2\gamma^{\prime}\mathbb{E}_{\left\\{\boldsymbol{X}_{i}\right\\}_{1}^{n},\left\\{\epsilon_{i}\right\\}_{1}^{n}}\left[\sup_{\theta\in\Theta}{\theta^{T}\left(\frac{1}{n}\sum_{i=1}^{n}{\epsilon_{i}\boldsymbol{X}_{i}\boldsymbol{X}_{i}^{T}}\right)\theta}\right]$
$\displaystyle\leq$ $\displaystyle
2\gamma^{\prime}\mathbb{E}_{\left\\{\boldsymbol{X}_{i}\right\\}_{1}^{n},\left\\{\epsilon_{i}\right\\}_{1}^{n}}\left[\lambda_{\max}\left(\frac{1}{n}\sum_{i=1}^{n}{\epsilon_{i}\boldsymbol{X}_{i}\boldsymbol{X}_{i}^{T}}\right)\right]$
$\displaystyle\leq$ $\displaystyle
2\gamma^{\prime}\sqrt{\mathbb{E}_{\left\\{\boldsymbol{X}_{i}\right\\}_{1}^{n},\left\\{\epsilon_{i}\right\\}_{1}^{n}}\left[\operatorname{Tr}\left(\frac{1}{n}\sum_{i=1}^{n}{\epsilon_{i}\boldsymbol{X}_{i}\boldsymbol{X}_{i}^{T}}\right)^{T}\left(\frac{1}{n}\sum_{i=1}^{n}{\epsilon_{i}\boldsymbol{X}_{i}\boldsymbol{X}_{i}^{T}}\right)\right]}$
$\displaystyle\leq$ $\displaystyle
2\gamma^{\prime}\sqrt{\mathbb{E}_{\left\\{\boldsymbol{X}_{i}\right\\}_{1}^{n}}\left[\frac{1}{n^{2}}\sum_{i=1}^{n}{\|\boldsymbol{X}_{i}\|_{2}^{4}}\right]}$
$\displaystyle\leq$
$\displaystyle\frac{2\gamma^{\prime}}{\sqrt{n}}\sqrt{\mathbb{E}_{\boldsymbol{X}}\left[\|\boldsymbol{X}\|_{2}^{4}\right]}$
$\displaystyle\leq$
$\displaystyle\frac{4\gamma^{\prime}\left(\operatorname{Tr}\left(\Sigma_{1}\right)+\|\boldsymbol{\mu}_{1}\|_{2}^{2}\right)}{\sqrt{n}},$
(104)

where $\epsilon_{i}$s in (103) are Rademacher’s random variables, and the last
inequality in (104) is results from the fact that $\boldsymbol{X}_{i}$s are
sampled from distribution $P_{1}$ defined in Theorem 4.5 of the manuscript.
And the prood is complete. ∎

######  Auxiliary Lemma B.4.

Consider the setting described in Theorem 4.5, if we define the function
$\phi_{\gamma^{\prime}}^{c^{\prime}}$ as follows

$\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},h_{\theta}\left(\boldsymbol{X}\right);\theta\right)=\max\left\\{0,1-\gamma^{\prime}\langle\theta,\boldsymbol{X}\rangle^{2}\right\\},$
(105)

then we have the following upper-bound and lower-bound for the expected value
of $\phi_{\gamma^{\prime}}^{c^{\prime}}$ when $\boldsymbol{X}$ sampled from
the distribution $P_{1}$ defined in Theorem 4.5 of the manuscript:

$\frac{4e^{-\frac{\langle\theta,\boldsymbol{\mu}_{1}\rangle^{2}}{2\theta^{T}\Sigma_{1}\theta}}}{3\sqrt{\gamma^{\prime}}}\left(1-\frac{1}{\sqrt{\gamma^{\prime}\theta^{T}\Sigma_{1}\theta}}\right)\leq\mathbb{E}\left[\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},h_{\theta}\left(\boldsymbol{X}\right);\theta\right)\right]\leq\frac{4e^{-\frac{\langle\theta,\boldsymbol{\mu}_{1}\rangle^{2}}{2\theta^{T}\Sigma_{1}\theta}}}{3\sqrt{\gamma^{\prime}}}\left(1+\frac{1}{\sqrt{\gamma^{\prime}\theta^{T}\Sigma_{1}\theta}}\right).$
(106)

###### Proof.

For the expected value of $\phi_{\gamma^{\prime}}^{c^{\prime}}$ we can write:

$\displaystyle\mathbb{E}\left[\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},h_{\theta}\left(\boldsymbol{X}\right);\theta\right)\right]=$
$\displaystyle\max\left\\{0,1-\gamma^{\prime}\langle\theta,\boldsymbol{X}\rangle^{2}\right\\}$
$\displaystyle=$
$\displaystyle\int_{-\frac{1}{\sqrt{\gamma^{\prime}}}\leq\langle\theta,\boldsymbol{X}\rangle\leq\frac{1}{\sqrt{\gamma^{\prime}}}}{1-\gamma^{\prime}\langle\theta,\boldsymbol{X}\rangle^{2}\mathcal{N}\left(\boldsymbol{\mu}_{1},\Sigma_{1}\right)}$
$\displaystyle=$
$\displaystyle\int_{-\frac{1}{\sqrt{\gamma^{\prime}\theta^{T}\Sigma_{1}\theta}}-\frac{\langle\theta,\boldsymbol{\mu}_{1}\rangle}{\sqrt{\theta^{T}\Sigma_{1}\theta}}}^{\frac{1}{\sqrt{\gamma^{\prime}\theta^{T}\Sigma_{1}\theta}}-\frac{\langle\theta,\boldsymbol{\mu}_{1}\rangle}{\sqrt{\theta^{T}\Sigma_{1}\theta}}}{1-\gamma^{\prime}\left(\langle\theta,\boldsymbol{\mu}_{1}\rangle+u\sqrt{\theta^{T}\Sigma_{1}\theta}\right)^{2}\mathcal{N}\left(0,1\right)}.$
(107)

Where we have the following upper-bound for the expected value if
$\gamma^{\prime}>>\frac{1}{\langle\theta,\boldsymbol{\mu}_{1}\rangle^{2}}$ :

$\displaystyle\mathbb{E}\left[\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},h_{\theta}\left(\boldsymbol{X}\right);\theta\right)\right]\leq$
$\displaystyle\frac{4}{3\sqrt{\gamma^{\prime}}}\mathcal{Q}\left(\frac{\langle\theta,\boldsymbol{\mu}_{1}\rangle}{\sqrt{\theta^{T}\Sigma_{1}\theta}}-\frac{1}{\sqrt{\gamma^{\prime}\theta^{T}\Sigma_{1}\theta}}\right)$
$\displaystyle\leq$
$\displaystyle\frac{4e^{-\frac{\langle\theta,\boldsymbol{\mu}_{1}\rangle^{2}}{2\theta^{T}\Sigma_{1}\theta}}}{3\sqrt{\gamma^{\prime}}}\left(1+\frac{1}{\sqrt{\gamma^{\prime}\langle\theta,\boldsymbol{\mu}_{1}\rangle^{2}}}\right).$
(108)

Now without loss of generality we assume that the largest eigenvalue of
$\Sigma_{1}$ is less than or equal to $1$, then we have the following lower-
bound if
$\gamma^{\prime}>>\frac{1}{\langle\theta,\boldsymbol{\mu}_{1}\rangle^{2}}$:

$\displaystyle\mathbb{E}\left[\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},h_{\theta}\left(\boldsymbol{X}\right);\theta\right)\right]\geq$
$\displaystyle\frac{4e^{-\frac{\langle\theta,\boldsymbol{\mu}_{1}\rangle^{2}}{2\theta^{T}\Sigma_{1}\theta}}}{3\sqrt{\gamma^{\prime}\theta^{T}\Sigma_{1}\theta}}\left(1-\frac{1}{\sqrt{\gamma^{\prime}\langle\theta,\boldsymbol{\mu}_{1}\rangle^{2}}}\right)$
$\displaystyle\geq$
$\displaystyle\frac{4e^{-\frac{\langle\theta,\boldsymbol{\mu}_{1}\rangle^{2}}{2\theta^{T}\Sigma_{1}\theta}}}{3\sqrt{\gamma^{\prime}}}\left(1-\frac{1}{\sqrt{\gamma^{\prime}\langle\theta,\boldsymbol{\mu}_{1}\rangle^{2}}}\right).$
(109)

∎

######  Auxiliary Lemma B.5.

Consider any distribution $P$, loss function $\ell$, transportation cost $c$,
and $\theta\in\Theta$. let us define $f_{\Theta,P}\left(\theta,\gamma\right)$
as

$f_{\Theta,P}\left(\theta,\gamma\right)=\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta\right)\right]-\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P}\left[\ell\left(\boldsymbol{X},y;\theta\right)\right].$ (110)

Then, for the loss and cost functions described in Section $4$, $P=P_{0}$,
where $P_{0}$ described in Theorem 4.5, in the manuscript, and the class of
linear classifiers with $|\theta|_{2}=1$, the function
$f_{\Theta,P}\left(\theta,\gamma\right)$ satisfies the following inequality:

$f_{\Theta,P}\left(\theta,\gamma\right)\leq\frac{e^{-\frac{\langle\theta,\boldsymbol{\mu}_{0}\rangle^{2}}{2\theta^{T}\Sigma_{0}\theta}}}{2\gamma}.$
(111)

###### Proof.

For the setting described in the lemma we have:

$u=y\langle\theta,\boldsymbol{X}\rangle\sim\mathcal{N}\left(\langle\theta,\boldsymbol{\mu}_{0}\rangle,\theta^{T}\Sigma_{0}\theta\right).$
(112)

Therefore we can calculate an upper-bound for
$f_{\Theta,P}\left(\theta,\gamma\right)$ as follows:

$\displaystyle\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P_{0}}\left[\phi_{\gamma}^{c}\left(\boldsymbol{X},y;\theta\right)\right]-\mathbb{E}_{\left(\boldsymbol{X},y\right)\sim
P_{0}}\left[l\left(\boldsymbol{X},y;\theta\right)\right]$
$\displaystyle=\int_{u=0}^{1/\gamma}{\frac{1}{\sqrt{2\pi\theta^{T}\Sigma_{0}\theta}}\left(1-\gamma
u\right)e^{\frac{\left(u-\langle\theta,\boldsymbol{\mu}_{0}\rangle\right)^{2}}{2\theta^{T}\Sigma_{0}\theta}}\,du}$
$\displaystyle\leq\frac{e^{-\frac{\langle\theta,\boldsymbol{\mu}_{0}\rangle^{2}}{2\theta^{T}\Sigma_{0}\theta}}}{2\gamma}.$
(113)

And the proof is complete. ∎

######  Auxiliary Lemma B.6.

Consider the setting in Theorem 4.5 if we define $\theta^{*}$ as follows:

$\theta^{*}\triangleq\frac{\Sigma_{0}^{-1}\boldsymbol{\mu}_{0}}{\|\Sigma_{0}^{-1}\boldsymbol{\mu}_{0}\|_{2}},$
(114)

then with high probability we have:

$\frac{1}{n}\sum_{i=1}^{n}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i},h_{\theta}\left(\boldsymbol{X}_{i}\right);\theta\right)}\leq
s,$

for any $\gamma^{\prime}$, as long as we set:

$s=\sup_{\theta\in\Theta}{\frac{1}{n}\sum_{\boldsymbol{X}_{i}\in
S_{1}^{\prime}}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i},h_{\theta}\left(\boldsymbol{X}_{i}\right);\theta\right)}}+\frac{12\gamma^{\prime}\operatorname{Tr}\left(\hat{\Sigma}\left(S_{1}^{\prime}\right)\right)}{\sqrt{n}}+2\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}+16\sqrt{\frac{d}{n}}$
(115)

###### Proof.

To prove the lemma we first give a lower-bound for $s$.

$\displaystyle s=$
$\displaystyle\sup_{\theta\in\Theta}{\frac{1}{n}\sum_{\boldsymbol{X}_{i}\in
S_{1}^{\prime}}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i},h_{\theta}\left(\boldsymbol{X}_{i}\right);\theta\right)}}+\frac{12\gamma^{\prime}\operatorname{Tr}\left(\hat{\Sigma}\left(S_{1}^{\prime}\right)\right)}{\sqrt{n}}+3\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}+16\sqrt{\frac{d}{n}}$
$\displaystyle\geq$
$\displaystyle\sup_{\theta\in\Theta}{\mathbb{E}_{P_{1X,\theta}}\left[\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},y;\theta\right)\right]}+\frac{4\gamma^{\prime}\left(\operatorname{Tr}\left(\Sigma_{1}\right)+\|\boldsymbol{\mu}_{1}\|_{2}^{2}\right)}{\sqrt{n}}+\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}$
(116)

where inequality 116 is due to Auxiliary Lemma B.3. To complete the proof we
give an upper-bound for
$\frac{1}{n}\sum_{i=1}^{n}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i},h_{\theta}\left(\boldsymbol{X}_{i}\right);\theta^{*}\right)}$
:

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i},h_{\theta}\left(\boldsymbol{X}_{i}\right);\theta^{*}\right)}\leq$
$\displaystyle\mathbb{E}_{P_{1X,\theta}}\left[\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},y;\theta^{*}\right)\right]+\frac{4\gamma^{\prime}\left(\operatorname{Tr}\left(\Sigma_{1}\right)+\|\boldsymbol{\mu}_{1}\|_{2}^{2}\right)}{\sqrt{n}}+\sqrt{\frac{\log{\frac{1}{\delta}}}{n}}.$
(117)

From (117) and (116), and the fact that

$\mathbb{E}_{P_{1X,\theta}}\left[\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},y;\theta^{*}\right)\right]\leq\sup_{\theta\in\Theta}{\mathbb{E}_{P_{1X,\theta}}\left[\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X},y;\theta\right)\right]},$

we conclude that for any $\gamma^{\prime}$ we have:

$\frac{1}{n}\sum_{i=1}^{n}{\phi_{\gamma^{\prime}}^{c^{\prime}}\left(\boldsymbol{X}_{i},h_{\theta}\left(\boldsymbol{X}_{i}\right);\theta^{*}\right)}\leq
s,$ (118)

and therfore the proof is complete. ∎

######  Auxiliary Lemma B.7.

Consider a positive definite $d\times d$ matrix, $\Sigma$, and a vector
$\boldsymbol{\mu}\in\mathbb{R}^{d}$. For and vector
$\boldsymbol{v}\in\mathbb{R}^{d}$, that we know:

$\|\boldsymbol{v}\|_{2}=1,~{}\boldsymbol{v}^{T}\Sigma_{1}^{-1}\boldsymbol{\mu}=0,$
(119)

we have the following:

$\boldsymbol{v}^{T}\left(\Sigma-\frac{\boldsymbol{\mu}\boldsymbol{\mu}^{T}}{\boldsymbol{\mu}^{T}\Sigma^{-1}\boldsymbol{\mu}}\right)\boldsymbol{v}\geq\frac{\lambda_{\mathrm{min}}\Delta^{2}}{d\lambda_{\mathrm{max}}^{2}}.$
(120)

###### Proof.

Suppose that we write $\boldsymbol{v}$ as follows:

$\boldsymbol{v}=\psi_{1}\hat{\boldsymbol{\mu}}+\psi_{1}\hat{\boldsymbol{\mu}}^{\perp},~{}\psi_{1}^{2}+\psi_{2}^{2}=1,$
(121)

where $\hat{\boldsymbol{\mu}}$ is a unit norm vector in the direction of
$\boldsymbol{\mu}$, and $\hat{\boldsymbol{\mu}}^{\perp}$ is a unit norm vector
perpendicular to $\boldsymbol{\mu}$. If we use this new description of
$\boldsymbol{v}$ we have:

$\displaystyle\boldsymbol{v}^{T}\left(\Sigma-\frac{\boldsymbol{\mu}\boldsymbol{\mu}^{T}}{\boldsymbol{\mu}^{T}\Sigma^{-1}\boldsymbol{\mu}}\right)\boldsymbol{v}=$
$\displaystyle\psi_{1}^{2}\hat{\boldsymbol{\mu}}^{T}\left(\Sigma-\frac{\boldsymbol{\mu}\boldsymbol{\mu}^{T}}{\boldsymbol{\mu}^{T}\Sigma^{-1}\boldsymbol{\mu}}\right)\hat{\boldsymbol{\mu}}+\left(\psi_{2}^{2}+2\psi_{1}\psi_{2}\right)\lambda_{\mathrm{min}}\left(\Sigma\right)$
$\displaystyle\geq$
$\displaystyle\min\left\\{\hat{\boldsymbol{\mu}}^{T}\left(\Sigma-\frac{\boldsymbol{\mu}\boldsymbol{\mu}^{T}}{\boldsymbol{\mu}^{T}\Sigma^{-1}\boldsymbol{\mu}}\right)\hat{\boldsymbol{\mu}},\lambda_{\mathrm{min}}\left(\Sigma\right)\right\\}.$
(122)

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
$\hat{\boldsymbol{\mu}}$ as follows:

$\hat{\boldsymbol{\mu}}=\sum_{i=1}^{d}{a_{i}\boldsymbol{u}_{i}},$ (123)

where $\boldsymbol{u}_{i}$ is the $i$th eigenvector of $\Sigma$, and
$\lambda_{i}$ is its $i$th eigenvalue, such that
$\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{d}$. With this new
description for $\hat{\boldsymbol{\mu}}$ we can write:

$\displaystyle\hat{\boldsymbol{\mu}}^{T}\left(\Sigma-\frac{\boldsymbol{\mu}\boldsymbol{\mu}^{T}}{\boldsymbol{\mu}^{T}\Sigma^{-1}\boldsymbol{\mu}}\right)\hat{\boldsymbol{\mu}}=$
$\displaystyle\sum_{i=1}^{d}{a_{i}^{2}\lambda_{i}}-\frac{1}{\sum_{i=1}^{d}{\frac{a_{i}^{2}}{\lambda_{i}}}}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{d}{a_{i}^{2}\lambda_{i}}-\frac{\prod_{i=1}^{d}{\lambda_{i}}}{\sum_{i=1}^{d}{a_{i}^{2}\prod_{j\neq
i}{\lambda_{i}}}}$ $\displaystyle=$
$\displaystyle\frac{\sum_{i,j=1}^{d}{a_{i}^{2}a_{j}^{2}\lambda_{i}\prod_{k\neq
j}{\lambda_{k}}}-\prod_{i=1}^{d}{\lambda_{i}}}{\sum_{i=1}^{d}{a_{i}^{2}\prod_{j\neq
i}{\lambda_{i}}}}$ $\displaystyle=$
$\displaystyle\frac{\left(\sum_{i=1}^{d}{a_{i}^{4}\prod_{i=1}^{d}{\lambda_{i}}}-\prod_{i=1}^{d}{\lambda_{i}}\right)+\sum_{i,j=1}^{d}{a_{i}^{2}a_{j}^{2}\lambda_{i}\prod_{k\neq
j}{\lambda_{k}}}}{\sum_{i=1}^{d}{a_{i}^{2}\prod_{j\neq i}{\lambda_{i}}}}$
$\displaystyle=$
$\displaystyle\frac{\sum_{i,j=1}^{d}{a_{i}^{2}a_{j}^{2}\left(\lambda_{i}-\lambda_{j}\right)^{2}\prod_{k\neq
i,j}{\lambda_{k}}}}{2\sum_{i=1}^{d}{a_{i}^{2}\prod_{j\neq i}{\lambda_{i}}}}$
$\displaystyle\geq$
$\displaystyle\frac{\lambda_{\mathrm{min}}\Delta^{2}}{d\lambda_{\mathrm{max}}},$
(124)

where in the last inequality $\Delta$ is defined as follows:

$\Delta\left(\Sigma\right)=\min\left\\{\lambda_{i}-\lambda_{j}\right\\},~{}\forall
i,j:\lambda_{i}\neq\lambda_{j}.$ (125)

An important point in the above inequalities is that, if
$\hat{\boldsymbol{\mu}}$ be in the direction of an eigenvector of $\Sigma$,
then
$\hat{\boldsymbol{\mu}}^{T}\left(\Sigma-\frac{\boldsymbol{\mu}\boldsymbol{\mu}^{T}}{\boldsymbol{\mu}^{T}\Sigma^{-1}\boldsymbol{\mu}}\right)\hat{\boldsymbol{\mu}}$
become equal to zero but in that case $\psi_{1}$ should be $0$. The reason is
that, in this situation $\hat{\boldsymbol{\mu}}$ and
$\Sigma_{1}^{-1}\boldsymbol{\mu}$ will be in the same direction and we know
that $\hat{\boldsymbol{\mu}}$ is perpendicular to
$\Sigma_{1}^{-1}\boldsymbol{\mu}$. therefore we have:

$\hat{\boldsymbol{\mu}}^{T}\left(\Sigma-\frac{\boldsymbol{\mu}\boldsymbol{\mu}^{T}}{\boldsymbol{\mu}^{T}\Sigma^{-1}\boldsymbol{\mu}}\right)\hat{\boldsymbol{\mu}}\geq\min\left\\{\frac{\lambda_{\mathrm{min}}\Delta}{\lambda_{\mathrm{max}}},\lambda_{\mathrm{min}}\right\\},$
(126)

and the proof is complete. ∎

##  Appendix C 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.

###  C.1 Experiment on simulated data

####  C.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(\mu,\sigma^{2}I)$ and
$N(-\mu,\sigma^{2}I)$, respectively. The parameter $\mu$ is initialized
randomly such that $||\mu||_{2}=1$. Also, for unlabeled out-of-distribution
data, two different Gaussian distributions, $N(\mu^{\prime},\sigma^{2}I)$ and
$N(-\mu^{\prime},\sigma^{2}I)$, respectively, have been considered for
positive and negative classes, which $\mu^{\prime}=\mu+\alpha.v$ where
$\alpha=\frac{||\mu||_{2}}{k},k\in\mathbb{N}$ and $v$ is 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 test data are
taken from the main distribution ($N(\mu,\sigma^{2}I)$ and
$N(-\mu,\sigma^{2}I)$) and it consists of 10,000 samples, half of which belong
to the positive class and the other half belong to the negative class.

####  C.1.2 Modeling

A linear model has been used to learn these data, the purpose of which is to
obtain optimal values for the weight vector w. The cost function for when
labeled data is used is according to (127), where the objective is to maximize
the margin of the linear classifier.

$\displaystyle
l_{\mathrm{labeled}}(x,y)=\sum_{i=0}^{n}\min\left(1,\max\left(0,1-\gamma.y_{i}.\left(w^{T}.x_{i}\right)\right)\right).$
(127)

In (128), $x_{i}$s are the feature vectors and $y_{i}$s are their
corresponding labels, $\gamma$ is a 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 (128), where,
due to the lack of access to labels for these samples, we use the model’s
predictions as their labels. Here too, the goal is to maximize the
classifier’s margin.

$\displaystyle
l_{\mathrm{unlabeled}}\left(x^{\prime}\right)=\sum_{j=0}^{m}\min\left(1,\max\left(0,1-\gamma^{\prime}.\|w^{T}.x^{\prime}_{j}\|^{2}\right)\right)$
(128)

In the above equation $x^{\prime}_{i}$s are the feature vector of unlabeled
samples, $\gamma^{\prime}$ is a 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 is used as the loss function of the model, when we have both labeled
and unlabeled samples. We define this new loss function as follows:

$\displaystyle
l_{\mathrm{total}}\left(x,y,x^{\prime}\right)=l_{\mathrm{labeled}}\left(x,y\right)+\lambda.l_{\mathrm{unlabeled}}\left(x^{\prime}\right)$
(129)

In all of our experiments we use Adam optimizer [28] with regularization term
(weight-decay). Considering that the hyper-parameters of the problem must have
an optimal value for each scenario; A random search process has been performed
to find the optimum $\gamma$, $\gamma^{\prime}$, $\lambda$, and weight-decay.
Finally, we select a combination of hyper-parameters that achieved the highest
accuracy on a validation dataset, and we report the accuracy of our model,
using these hyper-parameters, on the test samples. This process is repeated
for each experiment.

The details of the hyper-parameter values of the experiments reported for
simulated data in the manuscript are available in the attached file
Hyperparameter-Simulated.csv.

###  C.2 Experiment on real data

####  C.2.1 Dataset

To evaluate the performance of the proposed method on real-world datasets, we
selected a 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-HE-100K dataset is used as the main distribution, and the PatchCamelyon
dataset as the out-of-distribution dataset. Here are some additional
explanations about each of the datasets used in the experiment:

  1. 1.

NCT-CRC-HE-100K: This dataset contains 100,000 non-overlapping 224$\times$224
pixels patches that are extracted from 86 whole slide histopathology images of
human colorectal cancer (CRC) and normal tissue. It contains 9 different
classes: Adipose (ADI), background (BACK), debris (DEB), lymphocytes (LYM),
mucus (MUC), smooth muscle (MUS), normal colon mucosa (NORM), cancer-
associated stroma (STR), colorectal adenocarcinoma epithelium (TUM) [24].

  2. 2.

PatchCamelyon: This dataset contains 327,680 patches with 96$\times$96 pixels
from whole slide histopathology images of lymph node sections. It contains 2
different classes that show the patch is a tumor or normal [29].

We conducted two distinct experiments to evaluate the impact of adding
unlabeled data. The first experiment focused on assessing the accuracy
improvement by incorporating unlabeled data sampled from the same distribution
as the initial 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-100K dataset. For this purpose, we merged the cancer-
associated stroma (STR) and colorectal adenocarcinoma epithelium (TUM) classes
and labeled them as ”tumor”, while the remaining categories were labeled as
”normal”.

####  C.2.2 Modeling

As mentioned in the manuscript, the processing pipeline involves feeding the
images through a pre-trained ResNet model that has been trained on the
ImageNet dataset [25, 26], and the output embedding is saved for each image.
In these experiments, we use the implementation of [30] for ResNet50 to
extract the embeddings. The stored embeddings are then fed to a 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 a dimension of 1024). As shown in
Algorithm 1; In order to obtain the adversarial perturbed inputs based on the
original input, we update the initial value of the input a 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, if we are in the labeled-only mode, the parts
related to unlabeled samples will not be done, and the loss function will only
include $\phi_{i}$.

Algorithm 1 Finding the adversarial perturbed input for original input data
based on gradient ascent

function Adversarial-Perturb($x,y,\gamma,\alpha,N_{s}$)

$x^{\prime}=x$

for step = $1,...,N_{s}$ do $\triangleright$ Gradient ascent loop

$p=model(x^{\prime})$

$\phi=CE(p,y)-\gamma.||x^{\prime}-x||_{2}^{2}$ $\triangleright$ CE: Cross
entropy loss

$\alpha=\alpha/s$

$x^{\prime}=x^{\prime}+\alpha\nabla_{x^{\prime}}{\phi}$

end for

return $x^{\prime}$

end function

Algorithm 2 The training loop

Number of epochs $N_{ep}$, Number of perturbation steps $N_{s}$, Set of hyper-
parameter {$\gamma$, $\gamma^{\prime}$, $\lambda$, Learning rate of
perturbation $\alpha$}

$L=\\{(x_{0},y_{0}),(x_{0},y_{0}),\dots,(x_{N},y_{N})\\}$ $\triangleright$
Labeled data with size of N

$U=\\{x_{0}^{\prime},x_{1}^{\prime},\dots,x_{M}^{\prime}\\}$ $\triangleright$
Unlabeled data with the size of M

$k=2$

$L_{b}=$ the set of batches of $L$ $\triangleright$ batch size = N/k

$U_{b}=$ the set of batches of $U$ $\triangleright$ batch size = M/k

for epoch = $1,\dots,N_{ep}$ do

for $(x_{i},y_{i}),x_{j}^{\prime}$ in $L_{b},U_{b}$ do

$x_{i}^{p}=$ Adverserial-Perturb($x_{i},y_{i},\gamma,\alpha,step$)

$y_{j}^{\prime}=model(x_{j}^{\prime})$

$x_{j}^{\prime p}=$ Adverserial-
Perturb($x_{j}^{\prime},y_{j}^{\prime},\gamma^{\prime},\alpha,step$)

$p_{i}=model(x_{i}^{p})$

$p_{j}=model(x_{j}^{\prime p})$

$\phi_{i}=CE(p_{i},y_{i})-\gamma.||x_{i}^{p}-x_{i}||_{2}^{2}$

$\phi_{j}=CE(p_{j},y_{j}^{\prime})-\gamma^{\prime}.||x_{j}^{\prime
p}-x_{j}||_{2}^{2}$

$l=\phi_{i}+\lambda.\phi_{j}$

backpropagate loss ($l$) with gradient decent to the deep net and update the
weightes

end for

end for

To determine the optimal values for the hyperparameters, namely the Learning
rate, weight decay, $\lambda$, $\alpha$, $\gamma$, and $\gamma^{\prime}$, 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 3 presents the search space for each hyperparameter used in the
experiments.

Table 3: The hyperparameter search space that we test randomly. Hyperparameter | Search space ($i\in\mathbb{N}$) | Description
---|---|---
Learning rate | {$10^{i}|-5\leqslant i\leqslant-1$} | learning rate for adam optimizer
Weight decay | {$10^{i}|-7\leqslant i\leqslant-2$} | regularization term for adam optimizer
$\lambda$ | {$10^{i}|-5\leqslant i\leqslant 2$} | coefficient of the unlabeled term in loss function
$\alpha$ | {$10^{i}|-5\leqslant i\leqslant 1$} | learning rate for adversarial perturbation function
$\gamma$ | {$10^{i}|-7\leqslant i\leqslant 2$} | coefficient of norm term in labeled loss function
$\gamma^{\prime}$ | {$10^{i}|-7\leqslant i\leqslant 2$} | coefficient of norm term in unlabeled loss function

The details of the hyperparameter values of the experiments reported for
histopathology data in the manuscript are available in the attached file
Hyperparameter-Histopathology.csv.