Robustness to Adversarial Perturbations in Learning from Incomplete Data

Introduction

Robustness to adversarial perturbations has become an essential feature in the design of modern classifiers —in particular, of deep neural networks. This phenomenon originates from several empirical observations, such as and , which show deep networks are vulnerable to adversarial attacks in the input space. So far, plenty of novel methodologies have been introduced to compensate for this shortcoming. Adversarial Training (AT) , Virtual AT or Distillation are just examples of some promising methods in this area. The majority of these approaches seek an effective defense against a point-wise adversary, who shifts input data-points toward adversarial directions, in a separate manner. However, as shown by , a distributional adversary who can shift the data distribution instead of the input data-points is provably more detrimental to learning. This suggests that one can greatly improve the robustness of a classifier by improving its defense against a distributional adversary rather than a point-wise one. This motivation has led to the development of Distributionally Robust Learning (DRL) , which has attracted intensive research interest over the last few years .

Despite of all the advancements in supervised or unsupervised DRL, the amount of researches tackling this problem from a semi-supervised angle is slim to none . Motivated by this fact, we set out to propose a distributionally robust method that can handle Semi-Supervised Learning (SSL) scenarios. Our proposed method is an extension of self-learning , and can cope with all existing learning frameworks, such as neural networks. Intuitively, we first try to infer soft-labels for the unlabeled data, and then search for suitable classification rules that demonstrate low sensitivity to perturbation around these soft-label distributions.

Parts of this paper can be considered as a semi-supervised extension of the general supervised DRL developed in . Computational complexity of our method, for a moderate label-set size, is only slightly above those of its fully-supervised rivals. To optimize our model, we design a Stochastic Gradient Descent (SGD)-based algorithm with a theoretically-guaranteed convergence rate. In order to address the generalization of our framework, we introduce a set of novel complexity measures such as Adversarial Rademacher Complexity and Minimal Supervision Ratio (MSR), each of which are defined w.r.t. the hypothesis set and probability distribution that underlies input data-points. As long as the ratio of the labeled samples in a dataset (supervision ratio) exceeds MSR, true adversarial risk can be bounded. Also, one can arbitrarily decrease MSR by tuning the model parameters at the cost of increasing the generalization bound; This means our theoretical guarantees hold for all semi-supervised scenarios. We summarize the theoretical contribution of our work in Table 1.

We have also investigated the applicability of our method, denoted by SSDRL, via extensive computer experiments on datasets such as MNIST , SVHN , and CIFAR-10 . When implemented with deep neural networks, SSDRL outperforms rivals such as Pseudo-Labeling (PL) and the supervised DRL in (simply denoted as DRL) on all the above-mentioned datasets. In addition, SSDRL demonstrates a comparable performance to that of Virtual Adversarial Training (VAT) on MNIST and CIFAR-10, while outperforms VAT on SVHN.

The rest of the paper is organized as follows: Section 1.1 specifies the notations, and Section 1.2 reviews the related works. The basic idea behind the proposed method is outlined in Section 2.1, parameter optimization is described in Section 2.2 and generalization is analyzed in Section 2.3. Section 3 is devoted to experimental results. Finally, Section 4 concludes the paper.

The Wasserstein distance between two distributions $P$ and $Q$ in $M\left(\mathcal{Z}\right)$, with respect to cost $c$ is defined as:

where $M\left(\mathcal{Z}^{2}\right)$ represents the set of all couplings between any two random variables supported on $\mathcal{Z}$. Also, $\mu\left(\mathcal{Z},\cdot\right)$ and $\mu\left(\cdot,\mathcal{Z}\right)$ denote the marginals of $\mu$ taken w.r.t. the first and second variables, respectively.

$W_{c}\left(P,Q\right)$ measures the minimal cost of moving $P$ to $Q$, where the cost of moving one unit of mass from $\boldsymbol{z}$ to $\boldsymbol{z}^{\prime}$ is given by $c\left(\boldsymbol{z},\boldsymbol{z}^{\prime}\right)$. Also, for $\epsilon\geq 0$ and an arbitrary distribution $Q\in M\left(\mathcal{Z}\right)$, we define an $\epsilon$-ambiguity set (or a Wasserstein $\epsilon$-ball) as

2 Background and Related Works

Wasserstein metric has been widely used to quantify the strength of adversarial attacks , thanks to (i) its fundamental relations to adversarial robustness and (ii) its mathematically well-studied dual-form properties . In , authors have reformulated DRL into a convex program for the particular case of logistic regression. Convergence and generalization analysis of DRL have been addressed in in a general context, while the finding of a proper ambiguity set size, i.e. $\epsilon$, has been tackled in . An interesting analysis on DRL methods with $f$-divergences is given in . Sample complexity of DRL has been reviewed by and . We conjecture that there might be close relations between our complexity analysis in Section 2.3 and some of the results in the latter studies. However, a careful investigation regarding this issue goes beyond the scope of this paper.

On the other hand, recent abundance of unlabeled data has made SSL methods widely popular . See for a comprehensive review on classical SSL approaches. Many robust SSL algorithms have been proposed so far , however, their notion of robustness is mostly different from the one considered in this paper. In , author has proposed a pessimistic SSL approach which is guaranteed to have a better, or at least equal, performance when it takes unlabeled data into account.We show that a special case of our method reduces to an adversarial extension of . From a theoretical perspective, guarantees on the generalization of SSL can only be provided under certain assumptions on the choice of hypothesis set and the true data distribution . For example, in a compatibility function is introduced to restrict the relation between a model set and an input data distribution. Also, author of has theoretically analyzed SSL under the so-called cluster assumption, in order to establish an improvement guarantee for a situation where unlabeled data had been experimentally shown to be helpful. The fundamental reason behind such assumptions is that lack of any prior knowledge about the information-theoretic relations between a feature vector and its corresponding label, simply makes unlabeled data to be useless for classification. Not to mention that improper assumptions about the relation of feature-label pairs, for example by employing unsuitable hypothesis sets, could actually degrade the classification accuracy in semi-supervised scenarios. In Section 2.3, we propose a novel compatibility function that works under a general setting and enables us to theoretically establish a generalization bound for our method.

Finally, the only work prior to this paper that also falls in the cross section of DRL and SSL is . However, the method in severely restricts the support of adversarially-altered distributions, so that the adversary is left to choose from a set of delta-spikes over only labeled and augmented unlabeled samples. Thus, one cannot expect a considerable improvement in the distributional robustness in this case, because it does not let the adversary to freely perturb training data-points toward arbitrary directions.

Proposed Framework

where $\phi_{\gamma}\left(\boldsymbol{X},y;\theta\right)$, called adversarial loss, is defined as

Let $\theta^{*}\in\Theta$ be a minimizer of (5) for a given set of parameters $\epsilon\geq 0$ and $\lambda<0$. Then, there exists $\gamma\geq 0$ such that $\theta^{*}$ is also a minimizer of (7) with the same corresponding parameters $\epsilon$ and $\lambda$.

2 Numerical Optimization

becomes $\left(\gamma-L_{zz}\right)$-strongly concave for all $\left(\boldsymbol{X},y\right)\in\mathcal{Z}$.

Then, the gradient of (7) w.r.t. $\theta\in\Theta$ can be attained as

where $q(y;\theta)\triangleq\exp(\lambda J_{i}\left(y;\theta\right))/\left(\sum_{y^{\prime}\in\mathcal{Y}}\exp(\lambda J_{i}\left(y^{\prime};\theta\right))\right)$.

the outputs of Algorithm 1 with parameter set $k=1$, $\delta>0$, $\alpha=\alpha^{*}$ after $T$ iterations, say $\theta_{1},\ldots,\theta_{T}$, satisfy the following inequality:

3 Generalization Guarantees

Conventional Rademacher complexity, denoted by $\mathcal{R}_{n}\left(\mathcal{F}\right)$, is a tool to measure the richness of a function set $\mathcal{F}$ in classical learning theory . In fact, this measure tells us about how much a function set is able to learn noise, and thus is exposed to overfitting on small datasets. We give a novel adversarial extension for Rademacher complexity which also appears in our generalization bound at the end of this section. Moreover, we show that our complexity measure converges to zero when $n\rightarrow\infty$, for all function sets with a finite VC-dimension, regardless of the strength of adversary. Before that, let us define the set of $\epsilon$-Monge maps $\mathcal{A}_{\epsilon}$ as the following function set:

Then, the Semi-Supervised Monge (SSM) Rademacher complexity can be defined as follows:

where \boldsymbol{Z}_{1:n}\mathrel{\overset{i.i.d.}{\scalebox{1.5}[1.0]{\sim}}}P_{0} and \boldsymbol{X}_{1:n}\mathrel{\overset{i.i.d.}{\scalebox{1.5}[1.0]{\sim}}}P_{0_{\boldsymbol{X}}}. $\mathcal{A}_{\epsilon}$ represents the set of $\epsilon$-Monge maps. Also, $\boldsymbol{\sigma}\in\left\{-1,+1\right\}^{n}$ indicates a vector of independent Rademacher random variables. Then, for a supervision ratio $\eta\in\left[0,1\right]$, the SSM Rademacher complexity of $\mathcal{F}$ is defined as

The above definition is necessary when $\epsilon>0$, since learnability of a function class w.r.t. some distribution $P_{0}$ does not necessarily guarantee its adversarial learnability. In fact, an adversary can shift the data points and forces the learner to experience regions in $\mathcal{X}\times\mathcal{Y}$ that cannot be accessed by $P_{0}$ alone. However, one may be concerned about how to numerically compute this measure in practice? The main difference between $\mathcal{R}_{n}$ and SSM Rademacher complexity is that the latter alters input samples (or distribution) by an adversary. Fortunately, several distribution-free bounds have been established on $\mathcal{R}_{n}$ so far , which work for a variety of function classes of practical interest, e.g. classifiers with a bounded VC-dimension (including neural networks), polynomial regression tools with a bounded degree, and etc.

We show that in case of having a distribution-free bound on the Rademacher complexity of $\mathcal{F}$, the SSM Rademacher complexity can be bounded as well. Mathematically speaking, assuming there exists an asymptotically decreasing upper-bound $\Delta\left(n\right)$ such that $\mathcal{R}_{n}\left(\mathcal{F}\right)\leq\Delta\left(n\right),~{}\forall P_{0}\in M\left(\mathcal{X}\times\mathcal{Y}\right)$. Then for all $\eta\in\left[0,1\right]$ and $\epsilon\geq 0$ the following holds (Lemma D.1):

3.2 Minimum Supervision Ratio

As discussed earlier in Section 1.2, generalization guarantees for SSL frameworks generally require a compatibility assumption on the hypothesis set $\mathcal{F}$ and data distribution $P_{0}$. In Appendix B (and in particular, Definition B.4), a new compatibility function, denoted by Minimum Supervision Ratio (MSR), is introduced which has the following functional form:

For negative values of $\lambda$ (optimistic learning), MSR remains small as long as there exists a strong dependency between the distribution of feature vectors $P_{0_{\boldsymbol{X}}}$ and label conditionals $P_{0_{|\boldsymbol{X}}}$. This dependency can be obtained, for example, by the cluster assumption. However, MSR does not require such explicit assumptions and thus is able to impose a compatibility condition on the pair $\left(\mathcal{F},P_{0}\right)$ in a more fundamental way compared to existing works in SSL theory. Additionally, some loss functions in $\mathcal{F}$ need to be capable of capturing such dependencies, e.g. at least one loss function in $\mathcal{F}$ should resemble the true negative log-likelihood $-\log P_{0}\left(\boldsymbol{X},y\right)$. Conversely, absence of any dependency between $P_{0_{\boldsymbol{X}}}$ and $P_{0_{|\boldsymbol{X}}}$, or the lack of sufficiently “good” loss functions in $\mathcal{F}$ increases the MSR toward $1$, which forces the learner to choose a large $\lambda$ (in the extreme case $+\infty$) to be able to use the generalization bound of Theorem 3. Not to mention that a large $\lambda$ increases the empirical loss which then loosens the bound. This fact, however, should not be surprising since improper usage of unlabeled data is known to be harmful to the generalization instead of improving it.Based on previous discussions, Theorem 3 gives a generalization bound for our proposed framework in (7):

Then, with probability at least $1-\delta$, the following bound holds for all $\epsilon\geq 0$:

For a fixed $\epsilon$, $\gamma$ should be tuned to minimize the upper-bound for a better generalization. On the other hand, for every $\gamma$ there exists $\epsilon\geq 0$ where (20) becomes asymptotically tight. More importantly, the limiting cases of Theorem 3, i.e. $\epsilon=0$ and $\eta=1$, provide us with a new generalization bound for non-robust SSL, and an already-established bound for supervised DRL in , respectively.

Experimental Results

According to Figures 1 and 2, the proposed method is always superior to DRL and PL. Also, SSDRL outperforms VAT on SVHN dataset regardless of the attack type, while it has a comparable error-rate on MNIST and CIFAR-10 based on Figures 1(a) and 2(c), respectively. The superiority over DRL highlights the fact that exploitation of unlabeled data has improved the performance. However, SSDRL under-performs VAT on MNIST and CIFAR-10 datasets if the order of attacks are reversed. According to Figure 2(a), accuracy of PL degrades quite slowly as PGM’s $\varepsilon$ increases, although the loss values increase in Figure 5(a). This phenomenon is due to the fact that the adversarial directions for increasing the loss and error-rate are not correlated in this particular case.

Table 2 shows the test error-rates on clean examples for F-SSDRL, VAT, PL and DRL on MNIST, SVHN and CIFAR-10 datasets. In fact, Table 2 characterizes the non-adversarial generalization that can be attained via distributional robustness. Again, F-SSDRL outperforms both PL and DRL in almost all experimental settings. It also surpasses VAT on SVHN dataset. F-SSDRL under-performs VAT on MNIST and CIFAR-10, however, the difference in error-rates remains small and the two methods have close performances.

Conclusions

This paper aims to investigate the applications of distributionally robust learning in partially labeled datasets. The core idea is to focus on a well-known semi-supervised technique, known as self-learning, and make it robust to adversarial attacks. A novel framework, called SSDRL, has been proposed which builds upon an existing general scheme in supervised DRL. SSDRL encompasses many existing methods such as Pseud-Labeling (PL) and EM algorithm as its special cases. Computational complexity of our method is shown to be only slightly higher than those of its supervised counterparts. We have also derived convergence and generalization guarantees for SSDRL, where for the latter, a number of novel complexity measures have been introduced. We have proposed an adversarial extension of the Rademacher complexity in classical learning theory, and showed that it can be bounded for a broad range of learning frameworks, including neural networks, that have a finite VC-dimension. Moreover, our theoretical analysis reveals a more fundamental way to quantify the role unlabeled data in the generalization through a new complexity measure called Minimum Supervision Ratio (MSR). This is in contrast to many existing works that need more restrictive conditions such as cluster assumption to be applicable. Extensive computer simulation on real-world benchmark datasets demonstrate a comparable-to-superior performance for our method compared with those of the state-of-the-art. In future, one may attempt to improve the generalization bounds, for example, by finding empirical estimations for MSR function. Fitting a broader range of SSL methods into the core idea of Section 2.1 could be another good research direction.

References

Appendix A Additional Simulations and Experimental Settings

This section presents a number of additional experiments w.r.t. the proposed method and shows more comparison with rival methodologies. We also give an extensive description of the experimental setting that we have used for our computer simulations.

Figure A.1 is a complete version of Figure 1 from Section 3, where the performances of SSDRL, fully-supervised DRL, PL and VAT are extensively investigated on three benchmark datasets, i.e. MNIST, SVHN and CIFAR-10. SSDRL and VAT have been tested with a variety of their corresponding hyper-parameters $\gamma$ and $\epsilon$. Figure A.2 is the counterpart of Figure A.1, where the attack strategy is replaced with Projected-Gradient Method (PGM). Again, error-rates have been depicted as a function of PGM’s attack strength, i.e. $\varepsilon$. Even though more variation in hyper-parameters has been considered, we have not observed any significant sensitivity that is caused by a slight change of parameter values. As a result, one can say that DRL, SSDRL and VAT are all stable algorithms w.r.t. to their parameter values, at least up to some certain levels.

Figures A.3 and A.4 represent the performance (again in terms of error-rate) over clean examples from different datasets, and for SSDRL and VAT, respectively. In Figure A.3, different values of $\gamma$ have been used for training and the test error-rate is depicted as a function of $\gamma^{-1}$. Also, $\lambda$ is set to $-1$ for SSDRL. Apparently, SSDRL (or F-SSDRL), for a particular range of parameters, overfits during the training stage on MNIST and as a result its performance is degraded when compared to that of DRL. However, SSDRL outperforms DRL (its fully-supervised counterpart) on SVHN and CIFAR-10 datasets. Also, SSDRL and VAT have comparable performances on clean examples, specifically on SVHN and CIFAR-10 datasets. This observation is in agreement with Table 2.

A.2 Experimental Settings

In this part, we present a detailed description of the experimental settings which have been used for Section 3. It should be noted that the majority of the settings used for SVHN and CIFAR-10 datasets follow the same procedure as described in .

Three main datasets have been used during the experiments: MNIST, SVHN and CIFAR-10.

The MNIST dataset consists of $28\times 28$ pixel, gray-scale images of handwritten digits together with their corresponding labels. Each label is a natural number from to $9$. The number of training examples and test examples in the dataset are $60,000$ and $10,000$, respectively.

The SVHN dataset consists of $32\times 32\times 3$ pixel RGB images of street view house numbers with their corresponding labels. Again, labels are natural numbers ranging from to $9$. The number of training and test samples in the dataset are $73,257$ and $26,032$, respectively.

CIFAR-10 dataset consists of $32\times 32\times 3$ pixel RGB images of categorized objects, i.e., cars, trucks, planes, animals, and humans. The number of training examples and test examples in the dataset are $50,000$ and $10,000$, respectively. For CIFAR-10 dataset, we conducted Zero-phase Component Analysis (ZCA) as a pre-processing stage prior to the experiments.

A.2.2 Supervision Ratio and Training Data-points

In order to create a dataset (training+testing) for the semi-supervised learning task in the paper, we selected a subset of size $1,000$ as the labeled dataset from MNIST and SVHN, while the size goes up to $4,000$ for CIFAR-10. The rest of the samples in the training partition are treated as unlabeled data. We repeated the experiment three times with different choices of labeled and unlabeled data-points on all of the three datasets. For MNIST, a mini-batch of size $64$ is used for both the labeled and unlabeled term, and for SVHN and CIFAR-10, a mini-batch of size $32$ is used for the calculation of the labeled term, while a mini-batch of size $128$ is employed for the unlabeled term during the implementation of each method. We trained each model with $50,000$ updates for MNIST and $48,000$ updates for SVHN and CIFAR10. We have used ADAM optimizer in the training stage. In this regard, the initial learning rate of ADAM is set to $0.001$ and then linearly decayed over the last $10,000$ updates for MNIST, and the last $16,000$ updates for SVHN and CIFAR-10.

As for the transportation cost function $c$, we follow the work presented in and thus employed the following cost function throughout all our experiments:

where $\boldsymbol{1}\left(\cdot\right)$ is an indicator function which returns $1$ if its input condition holds and zero, otherwise. It should be noted that this choice is solely for the sake of simplicity, and as described before, every valid lower semi-continuous function is a legitimate choice for $c$.

Also, the pessimism/optimism trade-off parameter $\lambda$ is always set to $-1$, except when stated otherwise. This option yields certain degrees of optimism during the learning stage, which is motivated by the fact that Deep Neural Networks (DNN) have already proven to work well on all the above-mentioned three datasets. Thus, trusting the learner to assign soft pseudo-labels to the unlabeled data is somehow encouraged which in turn indicates a negative value for $\lambda$.

A.2.3 Creating Adversarial Examples

To solve the inner maximization problem in (8) and (10) for each pair of $\left(\boldsymbol{X},y\right)\in\mathcal{X}\times\mathcal{Y}$, we simply apply Gradient Ascent with the following update rule:

where the initial value $\boldsymbol{X}_{0}$ is set to $\boldsymbol{X}$, and the ascent rate is defined as $r_{t}\triangleq\frac{\kappa/\gamma}{(t+1)}$, where $\kappa$ is a hyper-parameter. We set $\kappa$ to 1.0 for MNIST and CIFAR-10, and $0.5$ for SVHN. During the training, we repeat the update in (A.2) $5$ times for both the DRL and SSDRL method. However, we repeat it $15$ times during the evaluation.

While generating the adversarial examples via the Projected-Gradient Method (PGM), we applied the following update rule which is also used in some previous works in this area :

A.2.4 Architecture of Deep Neural Networks

Appendix B Minimum Supervision Ratio: Definition and Implications

In this section, we present some complementary discussions with respect to our generalization bound in Section 2.3. In particular, the mathematical definition and intuitive implications behind one of our proposed complexity measures, i.e. the Minimum Supervision Ratio, are explained in details.

In order to better understand the intuition behind the proposed optimization programs in (5) or (7), it is necessary to investigate them under the asymptotic regime of $n\rightarrow\infty$. In this regard, this section provides a rigorous mathematical framework to study the semi-supervised learning in general (and its distributionally robust extension in particular), under the specific problem setting of this paper. We then provide conditions on the hypothesis set and data-generating distribution, under which unlabeled data can help the overall learning procedure. Final bounds on the performance improvement through incorporation of unlabeled samples (which is mostly from the generalization aspect), are given with mathematical details in Theorem 3 and its proof. In order to achieve the above-mentioned goal, first let us make the following definition:

It can be easily verified that the following properties hold for the conditional composition distribution of any two corresponding distributions:

where the first relation means: the marginal of the composition distribution w.r.t. $\boldsymbol{X}$ (which is a measure supported on $\mathcal{X}$) is the same as that of $P$, while the second property states that: conditional distribution over $\mathcal{Y}$ (given $\boldsymbol{X}\in\mathcal{X}$) is a weighted mixture of conditional distributions $P_{|\boldsymbol{X}}$ and $\Omega_{|\boldsymbol{X}}$.

An interesting asymptotic property of a consistent distribution set (see Definition 2) is that, given both fully and partially-observed samples in $\boldsymbol{D}$ are i.i.d. samples generated from a single arbitrary distribution $P_{0}\in M\left(\mathcal{X}\times\mathcal{Y}\right)$, the following relation holds almost surely w.r.t. $P_{0}$:

where the asymptotic equality in the above relation corresponds to a member-wise convergence between the two sets. Consequently, rewriting (7) in the asymptotic regime of $n\rightarrow\infty$ would give us the following equalities:

The first term in the r.h.s. of (B.4) is proportional to the true risk which we intend to bound. However, the second term models the asymptotic effect of unlabeled data for a fixed supervision ratio $\eta$. The main question that we try to answer in this section can be intuitively stated as: under what conditions, the second term becomes approximately proportional to the true risk as well?

$P_{0_{|\boldsymbol{X}}}$ is a distribution over $\mathcal{Y}$, thus can be considered as a vector in a simplex, i.e. all components are non-negative and sum up to one. Then, the lemma’s argument can be justified by the fact that

where $\langle\cdot|\cdot\rangle$ denotes the inner product. More precisely, one can write:

The last inequality is a direct result of the fact that inside of the expectation operator is non-negative. This completes the proof. ∎

We give a theoretical solution for the non-trivial case of the above-mentioned problem ($\lambda<+\infty$). This way, one can still choose small (or generally negative) values of $\lambda$, which substantially lower the empirical loss and improve the generalization bound. The following definitions provide us with more generalized means to achieve this goal.

By simple mathematical manipulations, it can be easily verified that

In this regard, in order to prove the lemma one can alternatively try to show that there exists $\zeta\geq 0$, such that

Theorem B.1 provides a mathematical foundation for establishing a general learning-theoretic bound on the generalization aspect of self-learning paradigm, that can be applied to our distributionally robust setting as well. Intuitively, it states that for good choices of the pair $\left(\eta,\lambda\right)$, one can guarantee the following two outcomes:

Appendix C Auxiliary Theorems and Proofs

The proof proceeds by the substitution of original proposed semi-supervised problem in (5) by its dual form. This way, we can take advantage of the good mathematical properties that this dual form can provide, specially w.r.t. maximization over $P\in\mathcal{B}_{\epsilon}\left(S\right)$. The following lemma (see Theorem $1$ and Remark $1$ of ), formulates the dual form:

Proof is explained in details in the original reference. Based on the duality equation in Lemma C.1, the following chain of relations hold:

where $const$ deos not depend on $\gamma$ or $\theta$, and the last equality is due to the following lemma:

The main idea is to replace the term $\boldsymbol{q}^{T}\boldsymbol{b}$ with

for all $\alpha>0$. Then, it can be readily verified that by setting $\alpha^{-1}\triangleq\frac{1}{d}\sum_{i\in\mathcal{F}}e^{\lambda b_{i}}$, the optimization problem in lemma becomes

whose solution always happens to be $q^{*}_{i}=\frac{\alpha}{d}e^{-b_{i}/\lambda}$, regardless of the sign of $\lambda$. Therefore, the solution of the primary optimization problem in lemma would be

According to the duality relation between $\gamma$ and $\epsilon$, the minimization over $\gamma$ is not necessary in almost all practical situations, where the same methodologies for evaluating a practically good value for $\epsilon$, such as cross-validation, can be used for $\gamma$ as well. ∎

The proof is based on a number of techniques used in , and can be considered as a generalization of Theorem $2$ of for the semi-supervised settings. Similarly, let us define the following set of Lipschitz constants, based on the smoothness constraints assumed in Theorem 2:

where $\left\{L_{\theta\theta},L_{\theta\boldsymbol{z}},L_{\boldsymbol{z}\theta},L_{\boldsymbol{z}\boldsymbol{z}}\right\}$ are a set of Lipschitz constants, $\left\|\cdot\right\|$ can be any valid norm (generally different norms should be used for $\mathcal{Z}$ and $\Theta$) and $\left\|\cdot\right\|_{*}$ denotes the corresponding dual norm(s). Also, the inequalities should hold for all $\boldsymbol{z},\boldsymbol{z}^{\prime}\in\mathcal{Z}$ and all $\theta,\theta^{\prime}\in\Theta$.

for all $\boldsymbol{Z}\in\mathcal{Z}$ and $\theta,\theta^{\prime}\in\Theta$.

In order to avoid discontinuity in the proof, the proof of Lemma C.4 is presented in Appendix D instead of here. Also, let $B\triangleq\frac{1}{2}\left(L_{\theta\theta}+\frac{L_{z\theta}L_{\theta z}}{\gamma-L_{zz}}\right)$, where $B$ represents one of the constants mentioned in Theorem 2.

The last lemma which is needed to finalize the proof of Theorem 2 aims to bound the maximum discrepancy that one might observe, given that the inner maximization in (10) (corresponds to line $6$ of Algorithm 1) is solved up to an approximation error of $\delta>0$.

Proof of Lemma C.5 is given in Appendix D. Also, Let $C\triangleq\frac{L_{z\theta}L_{\theta z}}{\gamma-L_{zz}}$, recalling $C$ as another constant mentioned in Theorem 2.

Algorithm 1 for a mini-batch size of $k=1$ picks one data-point randomly from $\boldsymbol{D}$ at each iteration. Also, data points at $\boldsymbol{D}$ are assumed to be drawn independently from an unknown but fixed distribution $P_{0}$. Therefore, one can consider a two-step data generation model in order to analyze the semi-supervised stochastic gradient descent as follows:

Consider a coupled first-order Markov stochastic process defined as $\left(h_{0},\theta_{0}\right),\ldots,\left(h_{T},\theta_{T}\right)$, where $h_{i}$s denote the observation variables and $\theta_{i}$s are the consequent outputs of Algorithm 1 after $T$ iterations. Here, $\theta_{0}$ can have any initial distribution over $\Theta$. Using the techniques reviewed in (also similar to Theorem $2$ of ), the following result holds for for $1<t\leq T$:

Combining the above arguments with (C.11) directly leads us to the claims in Theorem 2 and completes the proof. ∎

For the case of $\lambda=-\infty$, we show that by choosing sufficiently small values for $\alpha_{i}$ and $\delta_{i}$ for $i=1,2,\ldots$, the objective of the optimization always decreases, and thus convergence to a stable point is guaranteed. First, let us define

On the other hand, while transitioning from the $t_{f}$th to $\left(t_{f}+1\right)$th iteration, where at least one $y^{*}_{i}\left(\theta\right)$ changes by assumption, again we have

then we have $\phi_{\gamma}\left(\boldsymbol{z}_{0};\theta\right)=\max_{\boldsymbol{z}}f_{\boldsymbol{z}_{0}}\left(\theta,\boldsymbol{z}\right)$. Since $f$ is twice differentiable and convex w.r.t. $\theta$, $\phi_{\gamma}$ also shares these two properties based on Danskin’s theorem . Thus, the $d\times d$ hessian matrix $\nabla^{2}_{\theta\theta}\phi_{\gamma}$ is well-defined and positive definite for all $\left(\boldsymbol{z}_{0},\theta\right)\in\mathcal{Z}\times\Theta$.

where $\beta_{y}\left(\theta\right)$ (with $0\leq\beta_{y}\left(\theta\right)\leq 1$ for $y\in\mathcal{Y}$ and $\theta\in\Theta$) is defined as

Some mathematical simplifications reveal that

Note that for each $y\in\mathcal{Y}$, the $d\times d$ matrix $\nabla_{\theta}\phi_{\gamma}\left(\boldsymbol{X},y;\theta\right)\nabla_{\theta}^{T}\phi_{\gamma}\left(\boldsymbol{X},y;\theta\right)$ is rank-one, positive semi-definite and its only non-zero eigenvalue equals to $\left\|\nabla_{\theta}\phi_{\gamma}\left(\boldsymbol{X},y;\theta\right)\right\|^{2}_{2}\leq\sigma^{2}$. Therefore, the matrix corresponding to the second summand in the r.h.s. of (C.27) is negative semi-definite only if $\lambda<0$. In this case, i.e. having a negative $\lambda$, the following upper-bound holds for the magnitude of its largest eigenvalue:

On the other hand, the first summand in the r.h.s. of (C.27) is always positive definite and (since $\beta_{y}\left(\theta\right)$s sum up to $1$) its smallest eigenvalue satisfies the following lower-bound:

On the other hand, we have $\left|\phi_{\gamma}\left(\boldsymbol{z};\theta\right)\right|\leq B$, for all $\boldsymbol{z}\in\mathcal{Z}$ and $\theta\in\Theta$. This can be deduced from the definition of adversarial loss $\phi_{\gamma}$ as follows:

for all $\boldsymbol{X}\in\mathcal{X}$ and $\theta\in\Theta$. Now, assume the two partially observed data sets $\boldsymbol{D}$ and $\boldsymbol{D}^{\prime}$, both with size $n$, where the only difference between them is a single data point. Then, it can be readily deduced that

In this regard, one can use the McDiarmid’s inequality and show that: For all $0<\delta\leq 1$, with probability at least $1-\delta$, the following inequality holds:

which also implies that the following uniform upper-bound exists for all $\theta\in\Theta$:

where the rest of parameters are omitted from the input arguments of $f$ for the sake of simplicity in notation. It should be noted that we can write:

where $\boldsymbol{\sigma}\in\left\{-1,+1\right\}^{n}$ represents a vector of $n$ i.i.d. Rademacher random variables. Based on this result and its preceding discussions, one can write:

The first term in the r.h.s. of (C.39) can be more analytically investigated. In order to do so, let us define the $\epsilon$-neighborhood around $\boldsymbol{z}_{0}$ as $\mathcal{N}_{\epsilon}\left(\boldsymbol{z}_{0}\right)\triangleq\left\{\boldsymbol{z}\in\mathcal{Z}|c\left(\boldsymbol{z},\boldsymbol{z}_{0}\right)\leq\epsilon\right\}$, for $\epsilon\geq 0$. Then, there exists $\epsilon\geq 0$ such that

where $\mathcal{R}_{n}\left(\cdot\right)$ denotes the $n$-point expected Rademacher complexity w.r.t. to the same distribution that generates the samples in $\boldsymbol{Z}$.

where $\mathcal{C}\triangleq\left\{a-b|~{}a\in\mathcal{A},~{}b\in\mathcal{B}\right\}$. It can be readily verified that $\mathcal{R}_{n}\left(\mathcal{C}\right)\leq\mathcal{R}_{n}\left(\mathcal{A}\right)+\mathcal{R}_{n}\left(\mathcal{B}\right)$. Also, Talagrand’s contraction lemma in statistical learning theory states that given the above properties for a 1-Lipschitz function $h_{\lambda,\alpha,\beta}\left(\cdot\right)$, we have $\mathcal{R}_{n}\left(h_{\lambda,\alpha,\beta}\circ\mathcal{C}\right)\leq\mathcal{R}_{n}\left(\mathcal{C}\right)$. Therefore, the previous chain of inequalities can be concluded as

which can be verified through a simple substitution of parameters. By using (C.48), we have

Repeating the above inequality for $d$ consecutive times gives us the desired result and completes the proof. ∎

According to Definition 4, the previous upper-bounds can be simplified into the following statement: With probability at least $1-\delta$, and for all $\theta\in\Theta$, we have

Combining relations given in (C.51), (C.53) and (C.54) gives the desired result and completes the proof. ∎

Appendix D Auxiliary Lemmas and Proofs

where $\sum_{y\in\mathcal{Y}}\beta_{y}\left(\theta\right)=1$, for all $\theta\in\Theta$. Hence, the following inequalities hold:

where $\omega$ denotes the Lipschitz constant of $\beta_{y}\left(\theta\right)$ w.r.t. $\theta$, for all $y\in\mathcal{Y}$. The last inequality is a direct consequence of assuming $\left\|\nabla_{\theta}\phi_{\gamma}\left(\boldsymbol{X},y;\theta\right)\right\|_{*}\leq\sigma$, which can be validated through the following mathematical argument: There exists $\epsilon\geq 0$, such that

where $\mathcal{T}\left(\theta\rightarrow\theta^{\prime}\right)$ is the set of all continuous paths from $\theta$ to $\theta^{\prime}$ that entirely lie in $\Theta$. It is not hard to verify that the gradient $\nabla_{\theta}\beta_{y}\left(\theta\right)$ has the following formulation:

and hence satisfies the subsequent inequalities:

Combining (D.5) with (D.7) provides us with the safe choice of $\omega=2\sigma\left|\lambda\right|$. Therefore, $\nabla_{\theta}f$ is $\left(L_{\theta\theta}+\frac{L_{\boldsymbol{z}\theta}L_{\theta\boldsymbol{z}}}{\gamma-L_{\boldsymbol{z}\boldsymbol{z}}}+{2\sigma^{2}}{\left|\lambda\right|}\left|\mathcal{Y}\right|\right)$-Lipschitz w.r.t. $\theta$, and the proof is complete. ∎

The proof is simple and directly results from the assumptions. According to the differentiablility of $\phi_{\gamma}$ w.r.t. $\theta$ which is a consequence of an extended version of Danskin’s theorem (see Lemma C.4), the following relations hold:

On the other hand, due to $\left(\gamma-L_{zz}\right)$-strict-concavity of (10), a $\delta$-approximation maximizer, i.e. $\hat{\boldsymbol{z}}^{*}$, satisfies

Substituting the above into (D.8) completes the proof. ∎

for all distributions in $M\left(\mathcal{Z}\right)$, any $\epsilon\geq 0$ and $\eta\in\left[0,1\right]$.

According to the assumption, $\Delta\left(n\right)$ is an upper-bound for Rademacher complexity of $\mathcal{F}$, regardless of the probability measure that generates the data samples. Therefore, one can write

is a valid upper-bound on the Rademacher complexity of $\mathcal{F}$ regardless of $P_{0}$. Then, one can write

This will also prove the claim on SSM Rademacher complexity in Section 2.3. ∎