Good Semi-supervised Learning that Requires a Bad GAN

Introduction

Deep neural networks are usually trained on a large amount of labeled data, and it has been a challenge to apply deep models to datasets with limited labels. Semi-supervised learning (SSL) aims to leverage the large amount of unlabeled data to boost the model performance, particularly focusing on the setting where the amount of available labeled data is limited. Traditional graph-based methods (Belkin et al., 2006; Zhu et al., 2003) were extended to deep neural networks (Weston et al., 2012; Yang et al., 2016; Kipf and Welling, 2016), which involves applying convolutional neural networks (LeCun et al., 1998) and feature learning techniques to graphs so that the underlying manifold structure can be exploited. (Rasmus et al., 2015) employs a Ladder network to minimize the layerwise reconstruction loss in addition to the standard classification loss. Variational auto-encoders have also been used for semi-supervised learning (Kingma et al., 2014; Maaløe et al., 2016) by maximizing the variational lower bound of the unlabeled data log-likelihood.

Recently, generative adversarial networks (GANs) (Goodfellow et al., 2014) were demonstrated to be able to generate visually realistic images. GANs set up an adversarial game between a discriminator and a generator. The goal of the discriminator is to tell whether a sample is drawn from true data or generated by the generator, while the generator is optimized to generate samples that are not distinguishable by the discriminator. Feature matching (FM) GANs (Salimans et al., 2016) apply GANs to semi-supervised learning on $K$-class classification. The objective of the generator is to match the first-order feature statistics between the generator distribution and the true distribution. Instead of binary classification, the discriminator employs a $(K+1)$-class objective, where true samples are classified into the first $K$ classes and generated samples are classified into the $(K+1)$-th class. This $(K+1)$-class discriminator objective leads to strong empirical results, and was later widely used to evaluate the effectiveness of generative models (Dumoulin et al., 2016; Ulyanov et al., 2017).

Though empirically feature matching improves semi-supervised classification performance, the following questions still remain open. First, it is not clear why the formulation of the discriminator can improve the performance when combined with a generator. Second, it seems that good semi-supervised learning and a good generator cannot be obtained at the same time. For example, (Salimans et al., 2016) observed that mini-batch discrimination generates better images than feature matching, but feature matching obtains a much better semi-supervised learning performance. The same phenomenon was also observed in (Ulyanov et al., 2017), where the model generated better images but failed to improve the performance on semi-supervised learning.

In this work, we take a step towards addressing these questions. First, we show that given the current $(K+1)$-class discriminator formulation of GAN-based SSL, good semi-supervised learning requires a “bad” generator. Here by bad we mean the generator distribution should not match the true data distribution. Then, we give the definition of a preferred generator, which is to generate complement samples in the feature space. Theoretically, under mild assumptions, we show that a properly optimized discriminator obtains correct decision boundaries in high-density areas in the feature space if the generator is a complement generator.

Based on our theoretical insights, we analyze why feature matching works on 2-dimensional toy datasets. It turns out that our practical observations align well with our theory. However, we also find that the feature matching objective has several drawbacks. Therefore, we develop a novel formulation of the discriminator and generator objectives to address these drawbacks. In our approach, the generator minimizes the KL divergence between the generator distribution and a target distribution that assigns high densities for data points with low densities in the true distribution, which corresponds to the idea of a complement generator. Furthermore, to enforce our assumptions in the theoretical analysis, we add the conditional entropy term to the discriminator objective.

Empirically, our approach substantially improves over vanilla feature matching GANs, and obtains new state-of-the-art results on MNIST, SVHN, and CIFAR-10 when all methods are compared under the same discriminator architecture. Our results on MNIST and SVHN also represent state-of-the-art amongst all single-model results.

Related Work

Besides the adversarial feature matching approach (Salimans et al., 2016), several previous works have incorporated the idea of adversarial training in semi-supervised learning. Notably, (Springenberg, 2015) proposes categorical generative adversarial networks (CatGAN), which substitutes the binary discriminator in standard GAN with a multi-class classifier, and trains both the generator and the discriminator using information theoretical criteria on unlabeled data. From the perspective of regularization, (Miyato et al., 2015, 2017) propose virtual adversarial training (VAT), which effectively smooths the output distribution of the classifier by seeking virtually adversarial samples. It is worth noting that VAT bears a similar merit to our approach, which is to learn from auxiliary non-realistic samples rather than realistic data samples. Despite the similarity, the principles of VAT and our approach are orthogonal, where VAT aims to enforce a smooth function while we aim to leverage a generator to better detect the low-density boundaries. Different from aforementioned approaches, (Yang et al., 2017) proposes to train conditional generators with adversarial training to obtain complete sample pairs, which can be directly used as additional training cases. Recently, Triple GAN (Li et al., 2017) also employs the idea of conditional generator, but uses adversarial cost to match the two model-defined factorizations of the joint distribution with the one defined by paired data.

Apart from adversarial training, there has been other efforts in semi-supervised learning using deep generative models recently. As an early work, (Kingma et al., 2014) adapts the original Variational Auto-Encoder (VAE) to a semi-supervised learning setting by treating the classification label as an additional latent variable in the directed generative model. (Maaløe et al., 2016) adds auxiliary variables to the deep VAE structure to make variational distribution more expressive. With the boosted model expressiveness, auxiliary deep generative models (ADGM) improve the semi-supervised learning performance upon the semi-supervised VAE. Different from the explicit usage of deep generative models, the Ladder networks (Rasmus et al., 2015) take advantage of the local (layerwise) denoising auto-encoding criterion, and create a more informative unsupervised signal through lateral connection.

Theoretical Analysis

Given a labeled set $\mathcal{L}=\{(x,y)\}$, let $\{1,2,\cdots,K\}$ be the label space for classification. Let $D$ and $G$ denote the discriminator and generator, and $P_{D}$ and $p_{G}$ denote the corresponding distributions. Consider the discriminator objective function of GAN-based semi-supervised learning (Salimans et al., 2016):

where $p$ is the true data distribution. The probability distribution $P_{D}$ is over $K+1$ classes where the first $K$ classes are true classes and the $(K+1)$-th class is the fake class. The objective function consists of three terms. The first term is to maximize the log conditional probability for labeled data, which is the standard cost as in supervised learning setting. The second term is to maximize the log probability of the first $K$ classes for unlabeled data. The third term is to maximize the log probability of the $(K+1)$-th class for generated data. Note that the above objective function bears a similar merit to the original GAN formulation if we treat $P(K+1|x)$ to be the probability of fake samples, while the only difference is that we split the probability of true samples into $K$ sub-classes.

Let $f(x)$ be a nonlinear vector-valued function, and $w_{k}$ be the weight vector for class $k$. As a standard setting in previous work (Salimans et al., 2016; Dumoulin et al., 2016), the discriminator $D$ is defined as $P_{D}(k|x)=\frac{\exp(w_{k}^{\top}f(x))}{\sum_{k^{\prime}=1}^{K+1}\exp(w_{k^{\prime}}^{\top}f(x))}$. Since this is a form of over-parameterization, $w_{K+1}$ is fixed as a zero vector (Salimans et al., 2016). We next discuss the choices of different possible $G$’s.

Here, by perfect generator we mean that the generator distribution $p_{G}$ exactly matches the true data distribution $p$, i.e., $p_{G}=p$. We now show that when the generator is perfect, it does not improve the generalization over the supervised learning setting.

If $p_{G}=p$, and $D$ has infinite capacity, then for any optimal solution $D=(w,f)$ of the following supervised objective,

there exists $D^{*}=(w^{*},f^{*})$ such that $D^{*}$ maximizes Eq. (1) and that for all $x$, $P_{D}(y|x,y\leq K)=P_{D^{*}}(y|x,y\leq K)$.

The proof is provided in the supplementary material. Proposition 1 states that for any optimal solution $D$ of the supervised objective, there exists an optimal solution $D^{*}$ of the $(K+1)$-class objective such that $D$ and $D^{*}$ share the same generalization error. In other words, using the $(K+1)$-class objective does not prevent the model from experiencing any arbitrarily high generalization error that it could suffer from under the supervised objective. Moreover, since all the optimal solutions are equivalent w.r.t. the $(K+1)$-class objective, it is the optimization algorithm that really decides which specific solution the model will reach, and thus what generalization performance it will achieve. This implies that when the generator is perfect, the $(K+1)$-class objective by itself is not able to improve the generalization performance. In fact, in many applications, an almost infinite amount of unlabeled data is available, so learning a perfect generator for purely sampling purposes should not be useful. In this case, our theory suggests that not only the generator does not help, but also unlabeled data is not effectively utilized when the generator is perfect.

2 Complement Generator

Suppose $\cup_{k=1}^{K}F_{k}$ is bounded by a convex set $\mathcal{B}$. If the support $F_{G}$ of a generator $G$ in the feature space is a relative complement set in $\mathcal{B}$, i.e., $F_{G}=\mathcal{B}-\cup_{k=1}^{K}F_{k}$, we call $G$ a complement generator. The reason why we utilize a bounded $\mathcal{B}$ to define the complement is presented in the supplementary material. Note that the definition of complement generator implies that $G$ is a function of $f$. By treating $G$ as function of $f$, theoretically $D$ can optimize the original objective function in Eq. (1).

Now we present the assumption on the convergence conditions of the discriminator. Let $\mathcal{U}$ and $\mathcal{G}$ be the sets of unlabeled data and generated data.

Convergence conditions. When $D$ converges on a finite training set $\{\mathcal{L},\mathcal{U},\mathcal{G}\}$, $D$ learns a (strongly) correct decision boundary for all training data points. More specifically, (1) for any $(x,y)\in\mathcal{L}$, we have $w_{y}^{\top}f(x)>w_{k}^{\top}f(x)$ for any other class $k\not=y$; (2) for any $x\in\mathcal{G}$, we have $0>\max_{k=1}^{K}w_{k}^{\top}f(x)$; (3) for any $x\in\mathcal{U}$, we have $\max_{k=1}^{K}w_{k}^{\top}f(x)>0$.

In Assumption 1, conditions (1) and (2) assume classification correctness on labeled data and true-fake correctness on generated data respectively, which is directly induced by the objective function. Likewise, it is also reasonable to assume true-fake correctness on unlabeled data, i.e., $\log\sum_{k}\exp w_{k}^{\top}f(x)>0$ for $x\in\mathcal{U}$. However, condition (3) goes beyond this and assumes $\max_{k}w_{k}^{\top}f(x)>0$. We discuss this issue in detail in the supplementary material and argue that these assumptions are reasonable. Moreover, in Section 5, our approach addresses this issue explicitly by adding a conditional entropy term to the discriminator objective to enforce condition (3).

Suppose for all $k$, the L2-norms of weights $w_{k}$ are bounded by $\|w_{k}\|_{2}\leq C$. Suppose that there exists $\epsilon>0$ such that for any $f_{G}\in F_{G}$, there exists $f^{\prime}_{G}\in\mathcal{G}$ such that $\|f_{G}-f^{\prime}_{G}\|_{2}\leq\epsilon$. With the conditions in Assumption 1, for all $k\leq K$, we have $w_{k}^{\top}f_{G}<C\epsilon$.

When unlimited generated data samples are available, with the conditions in Lemma 1, we have $\lim_{|\mathcal{G}|\rightarrow\infty}w_{k}^{\top}f_{G}\leq 0$.

See the supplementary material for the proof.

Given the conditions in Corollary 1, for all class $k\leq K$, for all feature space points $f_{k}\in F_{k}$, we have $w_{k}^{\top}f_{k}>w_{j}^{\top}f_{k}$ for any $j\not=k$.

Without loss of generality, suppose $j=\arg\max_{j\not=k}w_{j}^{\top}f_{k}$. Now we prove it by contradiction. Suppose $w_{k}^{\top}f_{k}\leq w_{j}^{\top}f_{k}$. Since $F_{k}$’s are disjoint with a margin, $\mathcal{B}$ is a convex set and $F_{G}=\mathcal{B}-\cup_{k}F_{k}$, there exists $0<\alpha<1$ such that $f_{G}=\alpha f_{k}+(1-\alpha)f_{j}$ with $f_{G}\in F_{G}$ and $f_{j}$ being the feature of a labeled data point in $F_{j}$. By Corollary 1, it follows that $w_{j}^{\top}f_{G}\leq 0$. Thus, $w_{j}^{\top}f_{G}=\alpha w_{j}^{\top}f_{k}+(1-\alpha)w_{j}^{\top}f_{j}\leq 0$. By Assumption 1, $w_{j}^{\top}f_{k}>0$ and $w_{j}^{\top}f_{j}>0$, leading to contradiction. It follows that $w_{k}^{\top}f_{k}>w_{j}^{\top}f_{k}$ for any $j\not=k$. ∎

Proposition 2 guarantees that when $G$ is a complement generator, under mild assumptions, a near-optimal $D$ learns correct decision boundaries in each high-density subset $F_{k}$ (defined by $\epsilon_{k}$) of the data support in the feature space. Intuitively, the generator generates complement samples so the logits of the true classes are forced to be low in the complement. As a result, the discriminator obtains class boundaries in low-density areas. This builds a connection between our approach with manifold-based methods (Belkin et al., 2006; Zhu et al., 2003) which also leverage the low-density boundary assumption.

With our theoretical analysis, we can now answer the questions raised in Section 1. First, the $(K+1)$-class formulation is effective because the generated complement samples encourage the discriminator to place the class boundaries in low-density areas (Proposition 2). Second, good semi-supervised learning indeed requires a bad generator because a perfect generator is not able to improve the generalization performance (Proposition 1).

Case Study on Synthetic Data

In the previous section, we have established the fact a complement generator, instead of a perfect generator, is what makes a good semi-supervised learning algorithm. Now, to get a more intuitive understanding, we conduct a case study based on two 2D synthetic datasets, where we can easily verify our theoretical analysis by visualizing the model behaviors. In addition, by analyzing how feature matching (FM) (Salimans et al., 2016) works in 2D space, we identify some potential problems of it, which motivates our approach to be introduced in the next section. Specifically, two synthetic datasets are four spins and two circles, as shown in Fig. 4.

Firstly, to verify that the complement generator is a preferred choice, we construct the complement generator by uniformly sampling from the a bounded 2D box that contains all unlabeled data, and removing those on the manifold. Based on the complement generator, the result on four spins is visualized in Fig. 4. As expected, both the classification and true-fake decision boundaries are almost perfect. More importantly, the classification decision boundary always lies in the fake data area (left panel), which well matches our theoretical analysis.

Visualization of feature space

Next, to verify our analysis about the feature space, we choose the feature dimension to be 2, apply the FM to the simpler dataset of two circles, and visualize the feature space in Fig. 4. As we can see, most of the generated features (blue points) resides in between the features of two classes (green and orange crosses), although there exists some overlap. As a result, the discriminator can almost perfectly distinguish between true and generated samples as indicated by the black decision boundary, satisfying the our required Assumption 1. Meanwhile, the model obtains a perfect classification boundary (blue line) as our analysis suggests.

Pros and cons of feature matching

Finally, to further understand the strength and weakness of FM, we analyze the solution FM reaches on four spins shown in Fig. 4. From the left panel, we can see many of the generated samples actually fall into the data manifold, while the rest scatters around in the nearby surroundings of data manifold. It suggests that by matching the first-order moment by SGD, FM is performing some kind of distribution matching, though in a rather weak manner. Loosely speaking, FM has the effect of generating samples close to the manifold. But due to its weak power in distribution matching, FM will inevitably generate samples outside of the manifold, especially when the data complexity increases. Consequently, the generator density $p_{G}$ is usually lower than the true data density $p$ within the manifold and higher outside. Hence, an optimal discriminator $P_{D^{*}}(K+1\mid x)=p(x)/(p(x)+p_{G}(x))$ could still distinguish between true and generated samples in many cases. However, there are two types of mistakes the discriminator can still make

Higher density mistake inside manifold: Since the FM generator still assigns a significant amount of probability mass inside the support, wherever $p_{G}>p>0$, an optimal discriminator will incorrectly predict samples in that region as “fake”. Actually, this problem has already shown up when we examine the feature space (Fig. 4).

Collapsing with missing coverage outside manifold: As the feature matching objective for the generator only requires matching the first-order statistics, there exists many trivial solutions the generator can end up with. For example, it can simply collapse to mean of unlabeled features, or a few surrounding modes as along as the feature mean matches. Actually, we do see such collapsing phenomenon in high-dimensional experiments when FM is used (see Fig. 5(a) and Fig. 5(c)) As a result, a collapsed generator will fail to cover some gap areas between manifolds. Since the discriminator is only well-defined on the union of the data supports of $p$ and $p_{G}$, the prediction result in such missing area is under-determined and fully relies on the smoothness of the parametric model. In this case, significant mistakes can also occur.

Approach

As discussed in previous sections, feature matching GANs suffer from the following drawbacks: 1) the first-order moment matching objective does not prevent the generator from collapsing (missing coverage); 2) feature matching can generate high-density samples inside manifold; 3) the discriminator objective does not encourage realization of condition (3) in Assumption 1 as discussed in Section 3.2. Our approach aims to explicitly address the above drawbacks.

Following prior work (Salimans et al., 2016; Goodfellow et al., 2014), we employ a GAN-like implicit generator. We first sample a latent variable $z$ from a uniform distribution $\mathcal{U}(0,1)$ for each dimension, and then apply a deep convolutional network to transform $z$ to a sample $x$.

Fundamentally, the first drawback concerns the entropy of the distribution of generated features, $\mathcal{H}(p_{G}(f))$. This connection is rather intuitive, as the collapsing issue is a clear sign of low entropy. Therefore, to avoid collapsing and increase coverage, we consider explicitly increasing the entropy.

Although the idea sounds simple and straightforward, there are two practical challenges. Firstly, as implicit generative models, GANs only provide samples rather than an analytic density form. As a result, we cannot evaluate the entropy exactly, which rules out the possibility of naive optimization. More problematically, the entropy is defined in a high-dimensional feature space, which is changing dynamically throughout the training process. Consequently, it is difficult to estimate and optimize the generator entropy in the feature space in a stable and reliable way. Faced with these difficulties, we consider two practical solutions.

Alternatively, the second method aims at increasing the generator entropy in the feature space by optimizing an auxiliary objective. Concretely, we adapt the pull-away term (PT) (Zhao et al., 2016) as the auxiliary cost, L_{\text{PT}}=\frac{1}{N(N-1)}\sum_{i=1}^{N}\sum_{j\neq i}\Big{(}\frac{f(x_{i})^{\top}f(x_{j})}{\|f(x_{i})\|\|f(x_{j})\|}\Big{)}^{2}, where $N$ is the size of a mini-batch and $x$ are samples. Intuitively, the pull-away term tries to orthogonalize the features in each mini-batch by minimizing the squared cosine similarity. Hence, it has the effect of increasing the diversity of generated features and thus the generator entropy.

2 Generating Low-Density Samples

The second drawback of feature matching GANs is that high-density samples can be generated in the feature space, which is not desirable according to our analysis. Similar to the argument in Section 5.1, it is infeasible to directly minimize the density of generated features. Instead, we enforce the generation of samples with low density in the input space. Specifically, given a threshold $\epsilon$, we minimize the following term as part of our objective:

3 Generator Objective and Interpretation

Combining our solutions to the first two drawbacks of feature matching GANs, we have the following objective function of the generator:

This objective is closely related to the idea of complement generator discussed in Section 3. To see that, let’s first define a target complement distribution in the input space as follows

where $Z$ is a normalizer, $C$ is a constant, and $\mathcal{B}_{x}$ is the set defined by mapping $\mathcal{B}$ from the feature space to the input space. With the definition, the KL divergence (KLD) between $p_{G}(x)$ and $p^{*}(x)$ is

4 Conditional Entropy

In order for the complement generator to work, according to condition (3) in Assumption 1, the discriminator needs to have strong true-fake belief on unlabeled data, i.e., $\max_{k=1}^{K}w_{k}^{\top}f(x)>0$. However, the objective function of the discriminator in (Salimans et al., 2016) does not enforce a dominant class. Instead, it only needs $\sum_{k=1}^{K}P_{D}(k|x)>P_{D}(K+1|x)$ to obtain a correct decision boundary, while the probabilities $P_{D}(k|x)$ for $k\leq K$ can possibly be uniformly distributed. To guarantee the strong true-fake belief in the optimal conditions, we add a conditional entropy term to the discriminator objective and it becomes,

By optimizing Eq. (5), the discriminator is encouraged to satisfy condition (3) in Assumption 1. Note that the same conditional entropy term has been used in other semi-supervised learning methods (Springenberg, 2015; Miyato et al., 2017) as well, but here we motivate the minimization of conditional entropy based on our theoretical analysis of GAN-based semi-supervised learning.

To train the networks, we alternatively update the generator and the discriminator to optimize Eq. (4) and Eq. (5) based on mini-batches. If an encoder is used to maximize $\mathcal{H}(p_{G})$, the encoder and the generator are updated at the same time.

Experiments

We mainly consider three widely used benchmark datasets, namely MNIST, SVHN, and CIFAR-10. As in previous work, we randomly sample 100, 1,000, and 4,000 labeled samples for MNIST, SVHN, and CIFAR-10 respectively during training, and use the standard data split for testing. We use the 10-quantile log probability to define the threshold $\epsilon$ in Eq. (4). We add instance noise to the input of the discriminator (Arjovsky and Bottou, 2017; Sønderby et al., 2016), and use spatial dropout (Tompson et al., 2015) to obtain faster convergence. Except for these two modifications, we use the same neural network architecture as in (Salimans et al., 2016). For fair comparison, we also report the performance of our FM implementation with the aforementioned differences.

We compare the the results of our best model with state-of-the-art methods on the benchmarks in Table 1. Our proposed methods consistently improve the performance upon feature matching. We achieve new state-of-the-art results on all the datasets when only small discriminator architecture is considered. Our results are also state-of-the-art on MNIST and SVHN among all single-model results, even when compared with methods using self-ensembling and large discriminator architectures. Finally, note that because our method is actually orthogonal to VAT (Miyato et al., 2017), combining VAT with our presented approach should yield further performance improvement in practice.

2 Ablation Study

We report the results of ablation study in Table 2. In the following, we analyze the effects of several components in our model, subject to the intrinsic features of different datasets.

First, the generator entropy terms (VI and PT) (Section 5.1) improve the performance on SVHN and CIFAR by up to 2.2 points in terms of error rate. Moreover, as shown in Fig 5, our model significantly reduces the collapsing effects present in the samples generated by FM, which also indicates that maximizing the generator entropy is beneficial. On MNIST, probably due to its simplicity, no collapsing phenomenon was observed with vanilla FM training Salimans et al. (2016) or in our setting. Under such circumstances, maximizing the generator entropy seems to be unnecessary, and the estimation bias introduced by approximation techniques can even hurt the performance.

Second, the low-density (LD) term is useful when FM indeed generates samples in high-density areas. MNIST is a typical example in this case. When trained with FM, most of the generated hand written digits are highly realistic and have high log probabilities according to the density model (Cf. max log-p in Table 2). Hence, when applied to MNIST, LD improves the performance by a clear margin. By contrast, few of the generated SVHN images are realistic (Cf. Fig. 5(a)). Quantitatively, SVHN samples are assigned very low log probabilities (Cf. Table 2). As expected, LD has a negligible effect on the performance for SVHN. Moreover, the “max log-p” column in Table 2 shows that while LD can reduce the maximum log probability of the generated MNIST samples by a large margin, it does not yield noticeable difference on SVHN. This further justifies our analysis. Based on the above conclusion, we conjecture LD would not help on CIFAR where sample quality is even lower. Thus, we did not train a density model on CIFAR due to the limit of computational resources.

Third, adding the conditional entropy term has mixed effects on different datasets. While the conditional entropy (Ent) is an important factor of achieving the best performance on SVHN, it hurts the performance on MNIST and CIFAR. One possible explanation relates to the classic exploitation-exploration tradeoff, where minimizing Ent favors exploitation and minimizing the classification loss favors exploration. During the initial phase of training, the discriminator is relatively uncertain and thus the gradient of the Ent term might dominate. As a result, the discriminator learns to be more confident even on incorrect predictions, and thus gets trapped in local minima.

Lastly, we vary the values of the hyper-parameter $\epsilon$ in Eq. (4). As shown at the bottom of Table 2, reducing $\epsilon$ clearly leads to better performance, which further justifies our analysis in Sections 4 and 3 that off-manifold samples are favorable.

3 Generated Samples

We compare the generated samples of FM and our approach in Fig. 5. The FM images in Fig. 5(c) are extracted from previous work (Salimans et al., 2016). While collapsing is widely observed in FM samples, our model generates diverse “bad” images, which is consistent with our analysis.

Conclusions

In this work, we present a semi-supervised learning framework that uses generated data to boost task performance. Under this framework, we characterize the properties of various generators and theoretically prove that a complementary (i.e. bad) generator improves generalization. Empirically our proposed method improves the performance of image classification on several benchmark datasets.

Acknowledgement

This work was supported by the DARPA award D17AP00001, the Google focused award, and the Nvidia NVAIL award. The authors would also like to thank Han Zhao for his insightful feedback.

References

Appendix

Given an optimal solution $D=(w,f)$ for the supervised objective, due to the infinite capacity of the discriminator, there exists $D^{*}=(w^{*},f^{*})$ such that for all $x$ and $k\leq K$,

Let $L_{D}$ be the supervised objective in Eq. (1). Since $p=p_{G}$, the objective in Eq. (1) can be written as

Therefore, $D^{*}$ maximizes the second term of $J_{D}$. Because $D$ maximizes $L_{D}$, $D^{*}$ also maximizes $L_{D}$. It follows that $D^{*}$ maximizes $J_{D}$. ∎

2 On the Feature Space Bound Assumption

To obtain our theoretical results, we assume that $\cup_{k=1}^{K}F_{k}$ is bounded by a convex set $\mathcal{B}$. And the definition of complement generator requires that $F_{G}=\mathcal{B}-\cup_{k=1}^{K}F_{k}$. Now we justify the necessity of the introduction of $\mathcal{B}$.

The bounded $\mathcal{B}$ is introduced to ensure that Assumption 1 is realizable. We first show that for Assumption 1 to hold, $F_{G}$ must be a convex set.

We define $S=\{f:\max_{k=1}^{K}w_{k}^{\top}f<0\}$.

We prove it by contradiction. Suppose $S$ is a non-convex set, then there exists $f_{1},f_{2}\in S$, and $0<\alpha<1$, such that $f=\alpha f_{1}+(1-\alpha)f_{2}\not\in S$. For all $k$, we have $w_{k}^{\top}f_{1}<0$ and $w_{k}^{\top}f_{2}<0$, and thus it follows

Therefore, $\max_{k=1}^{K}w_{k}^{\top}f<0$, and we have $f\in S$, leading to contradiction.

3 The Reasonableness of Assumption 1

Here, we justify the proposed Assumption 1.

For (1), it assumes the correctness of classification on labeled data $\mathcal{L}$. This only requires the transformation $f(x)$ to have high enough capacity, such that the limited amount of labeled data points are linearly separable in the feature space. Under the setting of semi-supervised learning, where $|\mathcal{L}|$ is quite limited, this assumption is usually reasonable.

True-Fake correctness on 𝒢𝒢\mathcal{G}

For (2), it assumes that on generated data, the classifier can correctly distinguish between true and generated data. This can be seen by noticing that $w_{K+1}^{\top}f=0$, and the assumption thus reduces to $w_{K+1}^{\top}f(x)>\max_{k=1}^{K}w_{k}^{\top}f(x)$. For this part to hold, again we essentially require a transformation $f(x)$ with high enough capacity to distinguish true and fake data, which is a standard assumption made in GAN literature.

Strong true-fake belief on 𝒰𝒰\mathcal{U}

Finally, part (3) of the assumption is a little bit trickier than the other two.

Firstly, note that (3) is related to the true-fake correctness, because $\max_{k=1}^{K}w_{k}^{\top}f(x)>0=w_{K+1}^{\top}f(x)$ is a sufficient (but not necessary) condition for $x$ being classified as a true data point. Instead, the actual necessary condition is that $\log\sum_{k=1}^{K}\exp(w_{k}^{\top}f(x))\geq w_{K+1}^{\top}f(x)=0$. Thus, it means the condition (3) might be violated.

However, using the relationship $\log\sum_{k=1}^{K}\exp(w_{k}^{\top}f(x))\leq\log K\max_{k=1}^{K}\exp(w_{k}^{\top}f(x))$, to guarantee the necessary condition $\log\sum_{k=1}^{K}\exp(w_{k}^{\top}f(x))\geq 0$, we must have

Hence, if the condition (3) is violated, it means

Note that this is a very small interval for the logit $w_{k}^{\top}f(x)$, whose possible range expands the entire real line $(-\infty,\infty)$. Thus, the region where such violation happens should be limited in size, making the assumption reasonable in practice.

Moreover, even there exists a limited violation region, as long as part (1) and part (2) in Assumption 1 hold, Proposition 2 always hold for regions inside $\mathcal{U}$ where $\max_{k=1}^{K}w_{k}^{\top}f(x)>0$. This can be viewed as a further Corollary.

Empirically, we find that it is easy for the model to satisfy the correctness assumption on labeled data perfectly. To verify the other two assumptions, we keep track of the percentage of test samples that the two assumptions hold under our best models. More specifically, to verify the true-fake correctness on $\mathcal{G}$, we calculate the ratio after each epoch

where $\mathcal{T}$ denotes the test set and $|\mathcal{T}|$ is number of sample in it. Similarly, for the strong true-fake belief on $\mathcal{U}$, we generate the same number of samples as $|\mathcal{T}|$ and calculate

The plot is presented in Fig. 6. As we can see, the two ratios are both above $0.9$ for both SVHN and CIFAR-10, which suggests our assumptions are reasonable in practice.

4 Proof of Lemma 1

Let $\Delta f=f_{G}-f^{\prime}_{G}$, then we have $\|\Delta f\|_{2}\leq\epsilon$. Because $w_{k}^{\top}f^{\prime}_{G}<0$ by assumption, it follows