Year: 2021

Abstract:
Self-training algorithms, which train a model to fit pseudolabels predicted by another previously-learned model, have been very successful for learning with unlabeled data using neural networks. However, the current theoretical understanding of self-training only applies to linear models. This work provides a unified theoretical analysis of self-training with deep networks for semi-supervised learning, unsupervised domain adaptation, and unsupervised learning. At the core of our analysis is a simple but realistic “expansion” assumption, which states that a lowprobability subset of the data must expand to a neighborhood with large probability relative to the subset. We also assume that neighborhoods of examples in different classes have minimal overlap. We prove that under these assumptions, the minimizers of population objectives based on self-training and input-consistency regularization will achieve high accuracy with respect to ground-truth labels. By using off-the-shelf generalization bounds, we immediately convert this result to sample complexity guarantees for neural nets that are polynomial in the margin and Lipschitzness. Our results help explain the empirical successes of recently proposed self-training algorithms which use input consistency regularization.

heading: 1 INTRODUCTION
text: Though supervised learning with neural networks has become standard and reliable, it still often requires massive labeled datasets. As labels can be expensive or difficult to obtain, leveraging unlabeled data in deep learning has become an active research area. Recent works in semi-supervised learning (Chapelle et al., 2010; Kingma et al., 2014; Kipf & Welling, 2016; Laine & Aila, 2016; Sohn et al., 2020; Xie et al., 2020) and unsupervised domain adaptation (Ben-David et al., 2010; Ganin & Lempitsky, 2015; Ganin et al., 2016; Tzeng et al., 2017; Hoffman et al., 2018; Shu et al., 2018; Zhang et al., 2019) leverage lots of unlabeled data as well as labeled data from the same distribution or a related distribution. Recent progress in unsupervised learning or representation learning (Hinton et al., 1999; Doersch et al., 2015; Gidaris et al., 2018; Misra & Maaten, 2020; Chen et al., 2020a;b; Grill et al., 2020) learns high-quality representations without using any labels.
Self-training is a common algorithmic paradigm for leveraging unlabeled data with deep networks. Self-training methods train a model to fit pseudolabels, that is, predictions on unlabeled data made by a previously-learned model (Yarowsky, 1995; Grandvalet & Bengio, 2005; Lee, 2013). Recent work also extends these methods to enforce stability of predictions under input transformations such as adversarial perturbations (Miyato et al., 2018) and data augmentation (Xie et al., 2019). These approaches, known as input consistency regularization, have been successful in semi-supervised learning (Sohn et al., 2020; Xie et al., 2020), unsupervised domain adaptation (French et al., 2017; Shu et al., 2018), and unsupervised learning (Hu et al., 2017; Grill et al., 2020).
Despite the empirical successes, theoretical progress in understanding how to use unlabeled data has lagged. Whereas supervised learning is relatively well-understood, statistical tools for reasoning about unlabeled data are not as readily available. Around 25 years ago, Vapnik (1995) proposed the transductive SVM for unlabeled data, which can be viewed as an early version of self-training, yet there is little work showing that this method improves sample complexity (Derbeko et al., 2004).
Working with unlabeled data requires proper assumptions on the input distribution (Ben-David et al., 2008). Recent papers (Carmon et al., 2019; Raghunathan et al., 2020; Chen et al., 2020c; Kumar et al., 2020; Oymak & Gulcu, 2020) analyze self-training in various settings, but mainly for linear models and often require that the data is Gaussian or near-Gaussian. Kumar et al. (2020) also analyze self-training in a setting where gradual domain shift occurs over multiple timesteps but assume a small Wasserstein distance bound on the shift between consecutive timesteps. Another line of work leverages unlabeled data using non-parametric methods, requiring unlabeled sample complexity that is exponential in dimension (Rigollet, 2007; Singh et al., 2009; Urner & Ben-David, 2013).
This paper provides a unified theoretical analysis of self-training with deep networks for semisupervised learning, unsupervised domain adaptation, and unsupervised learning. Under a simple and realistic expansion assumption on the data distribution, we show that self-training with input consistency regularization using a deep network can achieve high accuracy on true labels, using unlabeled sample size that is polynomial in the margin and Lipschitzness of the model. Our analysis provides theoretical intuition for recent empirically successful self-training algorithms which rely on input consistency regularization (Berthelot et al., 2019; Sohn et al., 2020; Xie et al., 2020).
Our expansion assumption intuitively states that the data distribution has good continuity within each class. Concretely, letting Pi be the distribution of data conditioned on class i, expansion states that for small subset S of examples with class i,
Pi(neighborhood of S) ≥ cPi(S) (1.1) where and c > 1 is the expansion factor. The neighborhood will be defined to incorporate data augmentation, but for now can be thought of as a collection of points with a small `2 distance to S. This notion is an extension of the Cheeger constant (or isoperimetric or expansion constant) (Cheeger, 1969) which has been studied extensively in graph theory (Chung & Graham, 1997), combinatorial optimization (Mohar & Poljak, 1993; Raghavendra & Steurer, 2010), sampling (Kannan et al., 1995; Lovász & Vempala, 2007; Zhang et al., 2017), and even in early versions of self-training (Balcan et al., 2005) for the co-training setting (Blum & Mitchell, 1998). Expansion says that the manifold of each class has sufficient connectivity, as every subset S has a neighborhood larger than S. We give examples of distributions satisfying expansion in Section 3.1. We also require a separation condition stating that there are few neighboring pairs from different classes.
Our algorithms leverage expansion by using input consistency regularization (Miyato et al., 2018; Xie et al., 2019) to encourage predictions of a classifierG to be consistent on neighboring examples:
R(G) = Ex[ max neighbor x′
1(G(x) 6= G(x′))] (1.2)
For unsupervised domain adaptation and semi-supervised learning, we analyze an algorithm which fits G to pseudolabels on unlabeled data while regularizing input consistency. Assuming expansion and separation, we prove that the fitted model will denoise the pseudolabels and achieve high accuracy on the true labels (Theorem 4.3). This explains the empirical phenomenon that self-training on pseudolabels often improves over the pseudolabeler, despite no access to true labels.
For unsupervised learning, we consider finding a classifier G that minimizes the input consistency regularizer with the constraint that enough examples are assigned each label. In Theorem 3.6, we show that assuming expansion and separation, the learned classifier will have high accuracy in predicting true classes, up to a permutation of the labels (which can’t be recovered without true labels).
The main intuition of the theorems is as follows: input consistency regularization ensures that the model is locally consistent, and the expansion property magnifies the local consistency to global consistency within the same class. In the unsupervised domain adaptation setting, as shown in Figure 1 (right), the incorrectly pseudolabeled examples (the red area) are gradually denoised by their correctly pseudolabeled neighbors (the green area), whose probability mass is non-trivial (at least c−1 times the mass of the mistaken set by expansion). We note that expansion is only required on the population distribution, but self-training is performed on the empirical samples. Due to the extrapolation power of parametric methods, the local-to-global consistency effect of expansion occurs implicitly on the population. In contrast, nearest-neighbor methods would require expansion to occur explicitly on empirical samples, suffering the curse of dimensionality as a result. We provide more details below, and visualize this effect in Figure 1 (left).
To our best knowledge, this paper gives the first analysis with polynomial sample complexity guarantees for deep neural net models for unsupervised learning, semi-supervised learning, and unsuper-
vised domain adaptation. Prior works (Rigollet, 2007; Singh et al., 2009; Urner & Ben-David, 2013) analyzed nonparametric methods that essentially recover the data distribution exactly with unlabeled data, but require sample complexity exponential in dimension. Our approach optimizes parametric loss functions and regularizers, so guarantees involving the population loss can be converted to finite sample results using off-the-shelf generalization bounds (Theorem 3.7). When a neural net can separate ground-truth classes with large margin, the sample complexities from these bounds can be small, that is, polynomial in dimension.
Finally, we note that our regularizer R(·) corresponds to enforcing consistency w.r.t. adversarial examples, which was shown to be empirically helpful for semi-supervised learning (Miyato et al., 2018; Qiao et al., 2018) and unsupervised domain adaptation (Shu et al., 2018). Moreover, we can extend the notion of neighborhood in (1.1) to include data augmentations of examples, which will increase the neighborhood size and therefore improve the expansion. Thus, our theory can help explain empirical observations that consistency regularization based on aggressive data augmentation or adversarial training can improve performance with unlabeled data (Shu et al., 2018; Xie et al., 2019; Berthelot et al., 2019; Sohn et al., 2020; Xie et al., 2020; Chen et al., 2020a).
In summary, our contributions include: 1) we propose a simple and realistic expansion assumption which states that the data distribution has connectivity within the manifold of a ground-truth class 2) using this expansion assumption, we provide ground-truth accuracy guarantees for self-training algorithms which regularize input consistency on unlabeled data, and 3) our analysis is easily applicable to deep networks with polynomial unlabeled samples via off-the-shelf generalization bounds.

heading: 1.1 ADDITIONAL RELATED WORK
text: Self-training via pseudolabeling (Lee, 2013) or min-entropy objectives (Grandvalet & Bengio, 2005) has been widely used in both semi-supervised learning (Laine & Aila, 2016; Tarvainen & Valpola, 2017; Iscen et al., 2019; Yalniz et al., 2019; Berthelot et al., 2019; Xie et al., 2020; Sohn et al., 2020) and unsupervised domain adaptation (Long et al., 2013; French et al., 2017; Saito et al., 2017; Shu et al., 2018; Zou et al., 2019). Our paper studies input consistency regularization, which enforces stability of the prediction w.r.t transformations of the unlabeled data. In practice, these transformations include adversarial perturbations, which was proposed as the VAT objective (Miyato et al., 2018), as well as data augmentations (Xie et al., 2019).
For unsupervised learning, our self-training objective is closely related to BYOL (Grill et al., 2020), a recent state-of-the-art method which trains a student model to match the representations predicted by a teacher model on strongly augmented versions of the input. Contrastive learning is another popular method for unsupervised representation learning which encourages representations of “positive pairs”, ideally consisting of examples from the same class, to be close, while pushing negative pairs far apart (Mikolov et al., 2013; Oord et al., 2018; Arora et al., 2019). Recent works in contrastive learning achieve state-of-the-art representation quality by using strong data augmentation to form positive pairs (Chen et al., 2020a;b). The role of data augmentation here is in spirit similar to our use of input consistency regularization. Less related to our setting are algorithms which learn representations by solving self-supervised pretext tasks, such as inpainting and predicting rotations (Pathak et al., 2016; Noroozi & Favaro, 2016; Gidaris et al., 2018). Lee et al. (2020) theoretically analyze self-supervised learning, but their analysis applies to a different class of algorithms than ours.
Prior theoretical works analyze contrastive learning by assuming access to document data distributed according to a particular topic modeling setup (Tosh et al., 2020) or pairs of independent samples within the same class (Arora et al., 2019). However, the assumptions required for these analyses do not necessarily apply to vision, where positive pairs apply different data augmentations to the same image, and are therefore strongly correlated. Other papers analyze information-theoretic properties of representation learning (Tian et al., 2020; Tsai et al., 2020).
Prior works analyze continuity or “cluster” assumptions for semi-supervised learning which are related to our notion of expansion (Seeger, 2000; Rigollet, 2007; Singh et al., 2009; Urner & BenDavid, 2013). However, these papers leverage unlabeled data using non-parametric methods, requiring unlabeled sample complexity that is exponential in the dimension. On the other hand, our analysis is for parametric methods, and therefore the unlabeled sample complexity can be low when a neural net can separate the ground-truth classes with large margin.
Co-training is a classical version of self-training which requires two distinct “views” (i.e., feature subsets) of the data, each of which can be used to predict the true label on its own (Blum & Mitchell, 1998; Dasgupta et al., 2002; Balcan et al., 2005). For example, to predict the topic of a webpage, one view could be the incoming links and another view could be the words in the page. The original co-training algorithms (Blum & Mitchell, 1998; Dasgupta et al., 2002) assume that the two views are independent conditioned on the true label and leverage this independence to obtain accurate pseudolabels for the unlabeled data. By contrast, if we cast our setting into the co-training framework by treating an example and a randomly sampled neighbor as the two views of the data, the two views are highly correlated. Balcan et al. (2005) relax the requirement on independent views of co-training, also by using an “expansion” assumption. Our assumption is closely related to theirs and conceptually equivalent if we cast our setting into the co-training framework by treating neighboring examples are two views. However, their analysis requires confident pseudolabels to all be accurate and does not rigorously account for potential propagation of errors from their algorithm. In contrast, our contribution is to propose and analyze an objective function involving input consistency regularization whose minimizer denoises errors from potentially incorrect pseudolabels. We also provide finite sample complexity bounds for the neural network hypothesis class and analyze unsupervised learning algorithms.
Alternative theoretical analyses of unsupervised domain adaptation assume bounded measures of discrepancy between source and target domains (Ben-David et al., 2010; Zhang et al., 2019). Balcan & Blum (2010) propose a PAC-style framework for analyzing semi-supervised learning, but their bounds require the user to specify a notion of compatability which incorporates prior knowledge about the data, and do not apply to domain adaptation. Globerson et al. (2017) demonstrate semisupervised learning can outperform supervised learning in labeled sample complexity but assume full knowledge of the unlabeled distribution. (Mobahi et al., 2020) show that for kernel methods, self-distillation, a variant of self-training, can effectively amplify regularization. Their analysis is for kernel methods, whereas our analysis applies to deep networks under data assumptions.

heading: 2 PRELIMINARIES AND NOTATIONS
text: We let P denote a distribution of unlabeled examples over input spaceX . For unsupervised learning, P is the only relevant distribution. For unsupervised domain adaptation, we also define a source distribution Psrc and let Gpl denote a source classifier trained on a labeled dataset sampled from Psrc.
To translate these definitions to semi-supervised learning, we set Psrc and P to be the same, except Psrc gives access to labels. We analyze algorithms which only depend on Psrc through Gpl.
We consider classification and assume the data is partitioned into K classes, where the class of x ∈ X is given by the ground-truthG?(x) forG? : X → [K]. We let Pi denote the class-conditional distribution of x conditioned on G?(x) = i. We assume that each example x has a unique label, so Pi, Pj have disjoint support for i 6= j. Let P̂ , {x1, . . . , xn} ⊂ X denote n i.i.d. unlabeled training examples from P . We also use P̂ to refer to the uniform distribution over these examples. We let F : X → RK denote a learned scoring function (e.g. the continuous logits output by a neural network), and G : X → [K] the discrete labels induced by F : G(x) , arg maxi F (x)i (where ties are broken lexicographically).
Pseudolabels. Pseudolabeling methods are a form of self-training for semi-supervised learning and domain adaptation where the source classifier Gpl : X → [K] is used to predict pseudolabels on the unlabeled target data (Lee, 2013). These methods then train a fresh classifier to fit these pseudolabels, for example, using the standard cross entropy loss: Lpl(F ) , EP̂ [`cross-ent(F (x), Gpl(x))]. Our theoretical analysis applies to a pseudolabel-based objective. Other forms of self-training include entropy minimization, which is closely related, and in certain settings, equivalent to pseudolabeling where the pseudolabels are updated every iteration (Lee, 2013; Chen et al., 2020c).

heading: 3 EXPANSION PROPERTY AND GUARANTEES FOR UNSUPERVISED LEARNING
text: In this section we will first introduce our key assumption on expansion. We then study the implications of expansion for unsupervised learning. We show that if a classifier is consistent w.r.t. input transformations and predicts each class with decent probability, the learned labels will align with ground-truth classes up to permutation of the class indices (Theorem 3.6).

heading: 3.1 EXPANSION PROPERTY
text: We introduce the notion of expansion. As our theory studies objectives which enforce stability to input transformations, we will first model allowable transformations of the input x by the set B(x), defined below. We let T denote some set of transformations obtained via data augmentation, and define B(x) , {x′ : ∃T ∈ T such that ‖x′−T (x)‖ ≤ r} to be the set of points with distance r from some data augmentation of x. We can think of r as a value much smaller than the typical norm of x, so the probability P (B(x)) is exponentially small in dimension. Our theory easily applies to other choices of B, though we set this definition as default for simplicity. Now we define the neighborhood of x, denoted by N (x), as the set of points whose transformation sets overlap with that of x:
N (x) = {x′ : B(x) ∩ B(x′) 6= ∅} (3.1)
For S ⊆ X , we define the neighborhood of S as the union of neighborhoods of its elements: N (S) , ∪x∈SN (x). We now define the expansion property of the distribution P , which lower bounds the neighborhood size of low probability sets and captures connectivity of the distribution in input space. Definition 3.1 ((a, c)-expansion). We say that the class-conditional distribution Pi satisfies (a, c)expansion if for all V ⊆ X with Pi(V ) ≤ a, the following holds:
Pi(N (V )) ≥ min{cPi(V ), 1} (3.2) If Pi satisfies (a, c)-expansion for all ∀i ∈ [K], then we say P satisfies (a, c)-expansion.
We note that this definition considers the population distribution, and expansion is not expected to hold on the training set, because all empirical examples are far away from each other, and thus the neighborhoods of training examples do not overlap. The notion is closely related to the Cheeger constant, which is used to bound mixing times and hitting times for sampling from continuous distributions (Lovász & Vempala, 2007; Zhang et al., 2017), and small-set expansion, which quantifies connectivity of graphs (Hoory et al., 2006; Raghavendra & Steurer, 2010). In particular, when the neighborhood is defined to be the collection of points with `2 distance at most r from the set, then the expansion factor c is bounded below by exp(ηr), where η is the Cheeger constant (Zhang et al., 2017). In Section E.1, we use GANs to demonstrate that expansion is a realistic property in vision. For unsupervised learning, we require expansion with a = 1/2 and c > 1:
Assumption 3.2 (Expansion requirement for unsupervised learning). We assume that P satisfies (1/2, c)-expansion on X for c > 1.
We also assume that ground-truth classes are separated in input space. We define the population consistency loss RB(G) as the fraction of examples where G is not robust to input transformations:
RB(G) , EP [1(∃x′ ∈ B(x) such that G(x′) 6= G(x))] (3.3) We state our assumption that ground-truth classes are far in input space below: Assumption 3.3 (Separation). We assume P is B-separated with probability 1− µ by ground-truth classifier G?, as follows: RB(G?) ≤ µ.
Our accuracy guarantees in Theorems 4.3 and 3.6 will depend on µ. We expect µ to be small or negligible (e.g. inverse polynomial in dimension). The separation requirement requires the distance between two classes to be larger than 2r, the `2 radius in the definition of B(·). However, r can be much smaller than the norm of a typical example, so our expansion requirement can be weaker than a typical notion of “clustering” which requires intra-class distances to be smaller than inter-class distances. We demonstrate this quantitatively, starting with a mixture of Gaussians.
Example 3.4 (Mixture of isotropic Gaussians). Suppose P is a mixture of K Gaussians Pi , N (τi, 1dId×d) with isotropic covariance andK < d, corresponding toK separate classes.
1 Suppose the transformation set B(x) is an `2-ball with radius 12√d around x, so there is no data augmentation and r = 1
2 √ d . Then P satisfies (0.5, 1.5)-expansion. Furthermore, if the minimum distance between
means satisfies mini,j ‖τi − τj‖2 & √ log d√ d , then P is B-separated with probability 1− 1/poly(d).
In the example above, the population distribution satisfies expansion, but the empirical distribution does not. The minimum distance between any two empirical examples is Ω(1) with high probability, so they cannot be neighbors of each other when r = 1
2 √ d . Furthermore, the intra-class distance, which is Ω(1), is much larger than the distance between the means, which is assumed to be & 1/ √ d. Therefore, trivial distanced-based clustering algorithms on empirical samples do not apply. Our unsupervised learning algorithm in Section 3.2 can approximately recover the mixture components with polynomial samples, up to O(1/poly(d)) error. Furthermore, this is almost information-theoretically optimal: by total variation distance, Ω( 1√
d ) distance between the means is
required to recover the mixture components.
The example extends to log-concave distributions via more general isoperimetric inequalities (Bobkov et al., 1999). Thus, our analysis applies to the setting of prior work (Chen et al., 2020c), which studied self-training with linear models on mixtures of Gaussian or log-concave distributions.
The main benefit of our analysis, however, is that it holds for much richer family of distributions than Gaussians, compared to prior work on self-training which only considered Gaussian or nearGaussian distributions (Raghunathan et al., 2020; Chen et al., 2020c; Kumar et al., 2020). We demonstrate this in the following mixture of manifolds example: Example 3.5 (Mixture of manifolds). Suppose each class-conditional distribution Pi over an ambient space Rd′ , where d′ > d, is generated by some κ-bi-Lipschitz2 generator Qi : Rd → Rd ′ on latent variable z ∈ Rd: x ∼ Pi ⇔ x = Qi(z), z ∼ N (0, 1
d · Id×d)
We set the transformation set B(x) to be an `2-ball with radius κ2√d around x, so there is no data augmentation and r = κ
2 √ d . Then, P satisfies (0.5, 1.5)-expansion.
Figure 1 (right) provides a illustration of expansion on manifolds. Note that as long as κ d1/4, the radius κ/(2 √ d) is much smaller than the norm of the data points (which is at least on the order of 1/κ). This suggests that the generator can non-trivially scramble the space and still maintain meaningful expansion with small radius. In Section C.2, we prove the claims made in our examples.
1The classes are not disjoint, as is assumed by our theory for simplicity. However, they are approximately disjoint, and it is easy to modify our analysis to accomodate this. We provide details in Section C.2.
2A κ-bi-Lipschitz function f satisfies that 1 κ ‖x− y‖ ≤ |f(x)− f(y)| ≤ κ‖x− y‖.

heading: 3.2 POPULATION GUARANTEES FOR UNSUPERVISED LEARNING
text: We design an unsupervised learning objective which leverages the expansion and separation properties. Our objective is on the population distribution, but it is parametric, so we can extend it to the finite sample case in Section 3.3. We wish to learn a classifier G : X → [K] using only unlabeled data, such that predicted classes align with ground-truth classes. Note that without observing any labels, we can only learn ground-truth classes up to permutation, leading to the following permutation-invariant error defined for a classifier G:
Errunsup(G) , min permutation π:[K]→[K]
E[1(π(G(x)) 6= G?(x))]
We study the following unsupervised population objective over classifiers G : X → [K], which encourages input consistency while ensuring that predicted classes have sufficient probability.
min G RB(G) subject to min y∈[K]
EP [1(G(x) = y)] > max { 2
c− 1 , 2
} RB(G) (3.4)
Here c is the expansion coefficient in Assumption 3.2. The constraint ensures that the probability of any predicted class is larger than the input consistency loss. Let ρ , miny∈[K] P ({x : G?(x) = y}) denote the probability of the smallest ground-truth class. The following theorem shows that when P satisfies expansion and separation, the global minimizer of the objective (3.4) will have low error. Theorem 3.6. Suppose that Assumptions 3.2 and 3.3 hold for some c, µ such that ρ > max{ 2c−1 , 2}µ. Then any minimizer Ĝ of (3.4) satisfies
Errunsup(Ĝ) ≤ max { c
c− 1 , 2
} µ (3.5)
In Section C, we provide the proof of Theorem 3.6 as well as a variant of the theorem which holds for a weaker additive notion of expansion. By applying the generalization bounds of Section 3.3, we can convert Theorem 3.6 into a finite-sample guarantees that are polynomial in margin and Lipschitzness of the model (see Theorem D.1).
Our objective is reminiscent of recent methods which achieve state-of-the-art results in unsupervised representation learning: SimCLR (Chen et al., 2020a), MoCov2 (He et al., 2020; Chen et al., 2020b), and BYOL (Grill et al., 2020). Unlike our algorithm, these methods do not predict discrete labels, but rather, directly predict a representation which is consistent under input transformations, However, our analysis still suggests an explanation for why input consistency regularization is so vital for these methods: assuming the data satisfies expansion, it encourages representations to be similar over the entire class, so the representations will capture ground-truth class structure.
Chen et al. (2020a) also observe that using more aggressive data augmentation for regularizing input stability results in significant improvements in representation quality. We remark that our theory offers a potential explanation: in our framework, strengthening augmentation increases the size of the neighborhood, resulting in a larger expansion factor c and improving the accuracy bound (3.5).

heading: 3.3 FINITE SAMPLE GUARANTEES FOR DEEP LEARNING MODELS
text: In this section, we show that if the ground-truth classes are separable by a neural net with large robust margin, then generalization can be good. The main advantage of Theorem 3.6 and Theorem 4.3 over prior work is that they analyze parametric objectives, so finite sample guarantees immediately hold via off-the-shelf generalization bounds. Prior work on continuity or “cluster” assumptions related to expansion require nonparametric techniques with a sample complexity that is exponential in dimension (Seeger, 2000; Rigollet, 2007; Singh et al., 2009; Urner & Ben-David, 2013).
We apply the generalization bound of (Wei & Ma, 2019b) based on a notion of all-layer margin, though any other bound would work. The all-layer margin measures the stability of the neural net to simultaneous perturbations to each hidden layer. Formally, suppose that G(x) , arg maxi F (x)i is the prediction of some feedforward neural network F : X → RK which computes the following function: F (x) = Wpφ(· · ·φ(W1x) · · · ) with weight matrices {Wi}pi=1. Let q denote the maximum dimension of any hidden layer. Let m(F, x, y) ≥ 0 denote the all-layer margin at example x for
label y, defined formally in Section D.2. For now, we simply note that m has the property that if G(x) 6= y, then m(F, x, y) = 0, so we can upper bound the 0-1 loss by thresholding the all-layer margin: 1(G(x) 6= y) ≤ 1(m(F, x, y) ≥ t) for any t > 0. We can also define a variant that measures robustness to input transformations: mB(F, x) , minx′∈B(x)m (F, x′, arg maxi F (x)i). The following result states that large all-layer margin implies good generalization for the input consistency loss, which appears in the objective (3.4).
Theorem 3.7 (Extension of Theorem 3.1 of (Wei & Ma, 2019b)). With probability 1 − δ over the draw of the training set P̂ , all neural networks G = arg maxi Fi of the form F (x) , Wpφ(· · ·φ(W1x)) will satisfy
RB(G) ≤ EP̂ [1(mB(F, x) ≤ t)] + Õ (∑ i √ q‖Wi‖F t √ n ) + ζ (3.6)
for all choices of t > 0, where ζ , O (√ (log(1/δ) + p log n)/n )
is a low-order term, and Õ(·) hides poly-logarithmic factors in n and d.
A similar bound can be expressed for other quantities in (3.4), and is provided in Section D.2. In Section D.1, we plug our bounds into Theorem 3.6 and Theorem 4.3 to provide accuracy guarantees which depend on the unlabeled training set. We provide a proof overview in Section D.2, and in Section D.3, we provide a data-dependent lower bound on the all-layer margin that scales inversely with the Lipschitzness of the model, measured via the Jacobian and hidden layer norms on the training data. These quantities have been shown to be typically well-behaved (Arora et al., 2018; Nagarajan & Kolter, 2019; Wei & Ma, 2019a). In Section E.2, we empirically show that explicitly regularizing the all-layer margin improves the performance of self-training.

heading: 4 DENOISING PSEUDOLABELS FOR SEMI-SUPERVISED LEARNING AND DOMAIN ADAPTATION
text: We study semi-supervised learning and unsupervised domain adaptation settings where we have access to unlabeled data and a pseudolabeler Gpl. This setting requires a more complicated analysis than the unsupervised learning setting because pseudolabels may be inaccurate, and a student classifier could amplify these mistakes. We design a population objective which measures input transformation consistency and pseudolabel accuracy. Assuming expansion and separation, we show that the minimizer of this objective will have high accuracy on ground-truth labels.
We assume access to pseudolabeler Gpl(·), obtained via training a classifier on the labeled source data in the domain adaptation setting or on the labeled data in the semi-supervised setting. With access to pseudolabels, we can aim to recover the true labels exactly, rather than up to permutation as in Section 3.2. For G,G′ : X → [K], define L0-1(G,G′) , EP [1(G(x) 6= G′(x))] to be the disagreement between G and G′. The error metric is the standard 0-1 loss on ground-truth labels: Err(G) , L0-1(G,G?). LetM(Gpl) , {x : Gpl(x) 6= G?(x)} denote the set of mistakenly pseudolabeled examples. We require the following assumption on expansion, which intuitively states that each subset ofM(Gpl) has a large enough neighborhood.
Assumption 4.1 (P expands on sets smaller thanM(Gpl)). Define ā , maxi{Pi(M(Gpl))} to be the maximum fraction of incorrectly pseudolabeled examples in any class. We assume that ā < 1/3 and P satisfies (ā, c̄)-expansion for c̄ > 3. We express our bounds in terms of c , min{1/ā, c̄}.
Note that the above requirement c > 3 is more demanding than the condition c > 1 required in the unsupervised learning setting (Assumption 3.2). The larger c > 3 accounts for the possibility that mistakes in the pseudolabels can adversely affect the learned classifier in a worst-case manner. This concern doesn’t apply to unsupervised learning because pseudolabels are not used. For the toy distributions in Examples 3.4 and 3.5, we can increase the radius of the neighborhood by a factor of 3 to obtain (0.16, 6)-expansion, which is enough to satisfy the requirement in Assumption 4.1.
On the other hand, Assumption 4.1 is less strict than Assumption 3.2 in the sense that expansion is only required for small sets with mass less than ā, the pseudolabeler’s worst-case error on a class, which can be much smaller than a = 1/2 required in Assumption 3.2. Furthermore, the
unsupervised objective (3.4) has the constraint that the input consistency regularizer is not too large, whereas no such constraint is necessary for this setting. We remark that Assumption 4.1 can also be relaxed to directly consider expansion of subsets of incorrectly pseudolabeled examples, also with a looser requirement on the expansion factor c (see Section B.1). We design the following objective over classifiers G, which fits the classifier to the pseudolabels while regularizing input consistency:
min G L(G) , c+ 1 c− 1 L0-1(G,Gpl) + 2c c− 1 RB(G)− Err(Gpl) (4.1)
The objective optimizes weighted combinations of RB(G), the input consistency regularizer, and L0-1(G,Gpl), the loss for fitting pseudolabels, and is related to recent successful algorithms for semi-supervised learning (Sohn et al., 2020; Xie et al., 2020). We can show that L(G) ≥ 0 always holds. The following lemma bounds the error of G in terms of the objective value. Lemma 4.2. Suppose Assumption 4.1 holds. Then the error of classifier G : X → [K] is bounded in terms of consistency w.r.t. input transformations and accuracy on pseudolabels: Err(G) ≤ L(G).
When expansion and separation both hold, we show that minimizing (4.1) leads to a classifier that can denoise the pseudolabels and improve on their ground-truth accuracy.
Theorem 4.3. Suppose Assumptions 4.1 and 3.3 hold. Then for any minimizer Ĝ of (4.1), we have
Err(Ĝ) ≤ 2 c− 1 Err(Gpl) + 2c c− 1 µ (4.2)
We provide a proof sketch in Section A, and the full proof in Section B.1. Our result explains the perhaps surprising fact that self-training with pseudolabeling often improves over the pseudolabeler even though no additional information about true labels is provided. In Theorem D.2, we translate Theorem 4.3 into a finite-sample guarantee by using the generalization bounds in Section 3.3.
At a first glance, the error bound in Theorem 4.3 appears weaker than Theorem 3.6 because of the additional dependence on Err(Gpl). This discrepancy is due to weaker requirements on the expansion and the value of the input consistency regularizer. First, Section 3.2 requires expansion on all sets with probability less than 1/2, whereas Assumption 4.1 only requires expansion on sets with probability less than ā, which can be much smaller than 1/2. Second, the error bounds in Section 3.2 only apply to classifiers with small values ofRB(G), as seen in (3.4). On the other hand, Lemma 4.2 gives an error bound for all classifiers, regardless of RB(G). Indeed, strengthening the expansion requirement to that of Section 3.2 would allow us to obtain accuracy guarantees similar to Theorem 3.6 for pseudolabel-trained classifiers with low input consistency regularizer value.
Experiments In Section E.1, we provide details for the GAN experiment in Figure 1. We also provide empirical evidence for our theoretical intuition that self-training with input consistency regularization succeeds because the algorithm denoises incorrectly pseudolabeled examples with correctly pseudolabeled neighbors (Figure 3). In Section E.2, we perform ablation studies for pseudolabeling which show that components of our theoretical objective (4.1) do improve performance.

heading: 5 CONCLUSION
text: In this work, we propose an expansion assumption on the data which allows for a unified theoretical analysis of self-training for semi-supervised and unsupervised learning. Our assumption is realistic for real-world datasets, particularly in vision. Our analysis is applicable to deep neural networks and can explain why algorithms based on self-training and input consistency regularization can perform so well on unlabeled data. We hope that this assumption can facilitate future theoretical analyses and inspire theoretically-principled algorithms for semi-supervised and unsupervised learning. For example, an interesting question for future work is to extend our assumptions to analyze domain adaptation algorithms based on aligning the source and target (Hoffman et al., 2018).

heading: ACKNOWLEDGEMENTS
text: We would like to thank Ananya Kumar for helpful comments and discussions. CW acknowledges support from a NSF Graduate Research Fellowship. TM is also partially supported by the Google Faculty Award, Stanford Data Science Initiative, and the Stanford Artificial Intelligence Laboratory. The authors would also like to thank the Stanford Graduate Fellowship program for funding.

heading: A PROOF SKETCH FOR THEOREM 4.3
text: We provide a proof sketch for Lemma 4.2 for the extreme case where the input consistency regularizer is 0 for all examples, i.e. G(x) = G(x′) ∀x ∈ X , x′ ∈ B(x), so RB(G) = 0. For this proof sketch, we also make an additional restriction to the case when L0-1(G,Gpl) = Err(Gpl).
We first introduce some general notation. For sets U, V ⊆ X , we use U \ V to denote {x : x ∈ U, x /∈ V }, and ∩,∪ denote set intersection and union, respectively. Let U , X \ U denote the complement of U .
Let Ci , {x : G?(x) = i} denote the set of examples with ground-truth label i. For S ⊆ X , we define N ?(S) to be the neighborhood of S with neighbors restricted to the same class: N ?(S) , ∪i∈[K] (N (S ∩ Ci) ∩ Ci). The following key claims will consider two sets: the set of correctly pseudolabeled examples on which the classifier makes mistakes, {x : G(x) 6= Gpl(x) and x /∈ M(Gpl)}, and the set of examples where both classifier and pseudolabeler disagree with the ground truth,M(F ) ∩M(Gpl). The claims below use the expansion property to show that
P ({x : G(x) 6= Gpl(x) and x /∈M(Gpl)}) > P (M(F ) ∩M(Gpl))
Claim A.1. In the setting of Theorem 4.3, define the set V ,M(G)∩M(Gpl). Define q , Err(Gpl)c−1 . By expansion (Assumption 4.1), if P (V ) > q, then P (N ?(V ) \M(Gpl)) > P (V ).
A more general version of Claim A.1 is given by Lemma B.7 in Section B.2. For a visualization of V and N ?(V ) \M(Gpl), refer to Figure 2. Claim A.2. Suppose the input consistency regularizer is 0 for all examples, i.e., ∀x ∈ X , x′ ∈ B(x), it holds that G(x) = G(x′). Then it follows that
{x : G(x) 6= Gpl(x) and x /∈M(Gpl)} ⊇ N ?(V ) \M(Gpl)
Figure 2 outlines the proof of this claim. Claim B.5 in Section B provides a more general version of Claim A.2 in the case where RB(G) > 0. Given the above, the proof of Lemma 4.2 follows by a counting argument.
Proof sketch of Lemma 4.2 for simplified setting. Assume for the sake of contradiction that P (V ) > q. We can decompose the errors of G on the pseudolabels as follows:
L0-1(G,Gpl) ≥ E[1(G(x) 6= Gpl(x) and x /∈M(Gpl))] + E[1(G(x) 6= Gpl(x) and x ∈M(Gpl))]
We lower bound the first term by P (V ) by Claims A.1 and A.2. For the latter term, we note that if x ∈ M(Gpl) \ V , then G(x) = G?(x) 6= Gpl(x). Thus, the latter term has lower bound P (M(Gpl))− P (V ). As a result, we obtain
L0-1(G,Gpl) > P (V ) + P (M(Gpl))− P (V ) = Err(Gpl)
which contradicts our simplifying assumption that L0-1(G,Gpl) = Err(Gpl). Thus, G disagrees with G? at most q fraction of examples inM(Gpl). To complete the proof, we note that G also disagrees with G? on at most q fraction of examples outside ofM(Gpl), or else L0-1(G,Gpl) would again be too high.

heading: B PROOFS FOR DENOISING PSEUDOLABELS
text: In this section, we will provide the proof of Theorem 4.3. Our analysis will actually rely on a weaker additive notion of expansion, defined below. We show that the multiplicative definition in Definition 3.1 will imply that the additive variant holds.

heading: B.1 RELAXATION OF EXPANSION ASSUMPTION FOR PSEUDOLABELING
text: In this section, we provide a proof of a relaxed version of Theorem 4.3. We will then reduce Theorem 4.3 to this relaxed version in Section B.2. It will be helpful to restrict the notion of neighborhood
to only examples in the same ground-truth class: define N ?(x) , {x′ : x′ ∈ N (x) and G?(x′) = G?(x)} and N ?(S) , ∪x∈SN ?(x). Note that the following relation between N (S) and N ?(S) holds in general:
N ?(S) = ∪i∈[K] (N (S ∩ Ci) ∩ Ci)
We will define the additive notion of expansion on subsets of X below. Definition B.1 ((q, α)-additive-expansion on a set S). We say that P satisfies (q, α)-additiveexpansion on S ⊆ X if for all V ⊆ S with P (V ) > q, the following holds:
P (N ?(V ) \ S) = ∑ i∈[K] P (N (V ∩ Ci) ∩ Ci \ S) > P (V ) + α
In other words, any sufficiently large subset of S must have a sufficiently large neighborhood of examples sharing the same ground-truth label. For the remainder of this section, we will analyze this additive notion of expansion. In Section B.2, we will reduce multiplicative expansion (Definition 3.1) to our additive definition above.
Now for a given classifier, define the robust set of G, SB(G), to be the set of inputs for which G is robust under B-transformations:
SB(G) = {x : G(x) = G(x′) ∀x′ ∈ B(x)}
The following theorem shows that if the classifierG is B-robust and fits the pseudolabels sufficiently well, classification accuracy on true labels will be good. Theorem B.2. For a given pseudolabeler Gpl : X → {1, . . . ,K}, suppose that P has (q, α)additive-expansion onM(Gpl) for some q, α. Suppose that G fits the pseudolabels with sufficient accuracy and robustness:
EP [1(G(x) 6= Gpl(x) or x /∈ SB(G))] ≤ Err(Gpl) + α (B.1)
Then G satisfies the following error bound:
Err(G) ≤ 2(q +RB(G)) + EP [1(G(x) 6= Gpl(x))]− Err(Gpl)
To interpret this statement, supposeG fits the pseudolabels with error rate at most Err(Gpl) and (B.1) holds. Then Err(G) ≤ 2(q + RB(G)), so if G is robust to B-perturbations on the population distribution, the accuracy of G is high.
Towards proving Theorem B.2, we consider three disjoint subsets ofM(G) ∩ SB(G):
M1 , {x : G(x) = Gpl(x), Gpl(x) 6= G?(x), and x ∈ SB(G)} M2 , {x : G(x) 6= Gpl(x), Gpl(x) 6= G?(x), G(x) 6= G?(x), and x ∈ SB(G)} M3 , {x : G(x) 6= Gpl(x), Gpl(x) = G?(x), and x ∈ SB(G)}
We first bound the probability ofM1 ∪M2.
Lemma B.3. In the setting of Theorem B.2, we have P (SB(G) ∩ M(Gpl) ∩ M(G)) ≤ q. As a result, since it holds that M1 ∪ M2 ⊆ SB(G) ∩ M(Gpl) ∩ M(G), it immediately follows that P (M1 ∪M2) ≤ q.
The proof relies on the following claims.
Claim B.4. In the setting of Theorem 4.3, define U , N ?(SB(G) ∩M(Gpl) ∩M(G)) \M(Gpl). For any x ∈ U ∩ SB(G), it holds that Gpl(x) 6= G(x) and G(x) 6= G?(x).
Proof. For any x ∈ U ⊆ N ?(SB(G) ∩M(Gpl) ∩M(G)), there exists x′ ∈ SB(G) ∩M(Gpl) ∩ M(G) such that B(x) ∩ B(x′) 6= ∅ and G?(x) = G?(x′) by definition of N ?(·). Choose z ∈ B(x) ∩ B(x′). As x, x′ ∈ SB(G), by definition of SB(G) we also must have G(x) = G(z) = G(x′). Furthermore, as x′ ∈ M(G), G(x′) 6= G?(x′). Since G?(x) = G?(x′), it follows that G(x) 6= G?(x). As U ∩ M(Gpl) = ∅ by definition of U , Gpl much match the ground-truth classifier on U , so Gpl(x) = G ?(x). It follows that G(x) 6= Gpl(x), as desired.
Claim B.5. In the setting of Theorem B.2, define U , N ?(SB(G) ∩M(Gpl) ∩M(G)) \M(Gpl). If P (SB(G) ∩M(Gpl) ∩M(G)) > q, then
P (U ∩ SB(G)) > P (M(Gpl)) + P (SB(G)) + α− 1− P (SB(G) ∩M(Gpl) ∩M(G))
Proof. Define V , SB(G) ∩M(Gpl) ∩M(G). By the assumption that M(Gpl) satifies (q, α)additive-expansion, if P (V ) > q holds, it follows that P (U) > P (V ) + α. Furthermore, we have U \ SB(G) ⊆ SB(G) ∪M(Gpl) by definition of U and V as U ∩ M(Gpl) = ∅, and so P (U \ SB(G)) ≤ 1− P (SB(G) ∪M(Gpl)). Thus, we obtain
P (U ∩ SB(G)) = P (U)− P (U \ SB(G)) > P (V ) + α− 1 + P (SB(G) ∪M(Gpl))
Now we use the principle of inclusion-exclusion to compute
P (SB(G) ∪M(Gpl)) = P (M(Gpl)) + P (SB(G))− P (SB(G) ∩M(Gpl))
Plugging into the previous, we obtain
P (U ∩ SB(G)) > P (M(Gpl)) + P (SB(G)) + α− 1 + P (V )− P (SB(G) ∩M(Gpl)) = P (M(Gpl)) + P (SB(G)) + α− 1− P (SB(G) ∩M(Gpl) ∩M(G))
where we obtained the last line because V = SB(G)∩M(Gpl)∩M(G) ⊆ SB(G)∩M(Gpl).
Proof of Lemma B.3. To complete the proof of Lemma B.3, we first compose SB(G) into three disjoint sets:
S1 , {x : G(x) = Gpl(x)} ∩ SB(G) S2 , {x : G(x) 6= Gpl(x)} ∩M(Gpl) ∩ SB(G) S3 , {x : G(x) 6= Gpl(x)} ∩M(Gpl) ∩ SB(G)
First, by Claim B.4 and definition ofU , we have ∀x ∈ U∩SB(G),G(x) 6= Gpl(x) and x /∈M(Gpl). Thus, it follows that U ∩ SB(G) ⊆ S3.
Next, we claim that V ′ , M(Gpl) ∩ M(G) ∩ SB(G) ⊆ S2. To see this, note that for x ∈ V ′, G(x) = G?(x) and Gpl(x) 6= G?(x). Thus, G(x) 6= Gpl(x), and x ∈ SB(G) ∩M(Gpl), which implies x ∈ S2. Assume for the sake of contradiction that P (SB(G) ∩M(Gpl) ∩M(G)) > q. Now we have
P (SB(G)) ≥ P (S1) + P (S2) + P (S3) ≥ P (S1) + P (SB(G) ∩M(Gpl) ∩M(G)) + P (U ∩ SB(G)) > P (S1) + P (M(Gpl)) + P (SB(G)) + α− 1 (by Claim B.5)
However, we also have
P (S1) = 1− EP [1(G(x) 6= Gpl(x) or x /∈ SB(G))] ≥ 1− Err(Gpl)− α (by the condition in (B.1))
Plugging this in gives us P (S1)+P (S2)+P (S3) > P (SB(G)), a contradiction. Thus, P (SB(G)∩ M(Gpl) ∩M(G)) ≤ q, as desired.
The next lemma bounds P (M3). Lemma B.6. In the setting of Theorem B.2, the following bound holds:
P (M3) ≤ q +RB(G) + EP [1(G(x) 6= Gpl(x))]− Err(Gpl)
Proof. The proof will follow from basic manipulation. First, we note that
M3 ∪ {x : G(x) = Gpl(x) and x ∈ SB(G)} (B.2) = ( {x : G(x) 6= Gpl(x), Gpl(x) = G?(x)} ∪ {x : G(x) = Gpl(x), Gpl(x) = G?(x)} ∪ {x : G(x) = Gpl(x), Gpl(x) 6= G?(x)} ) ∩ SB(G)
=M1 ∪ {x : Gpl(x) = G?(x) and x ∈ SB(G)} (B.3)
As (B.2) and (B.3) pertain to unions of disjoint sets, it follows that
P (M3) + P ({x : G(x) = Gpl(x) and x ∈ SB(G)}) = P (M1) + P ({x : Gpl(x) = G?(x) and x ∈ SB(G)})
Thus, rearranging we obtain
P (M3) = P (M1) + P ({x : Gpl(x) = G?(x)} ∩ SB(G)}) − P ({x : G(x) = Gpl(x)} ∩ SB(G)}) ≤ P (M1) + P ({x : Gpl(x) = G?(x)})− P ({x : G(x) = Gpl(x)} ∩ SB(G)}) ≤ P (M1) + P ({x : Gpl(x) = G?(x)})− P ({x : G(x) = Gpl(x)})
+ P ({x : G(x) = Gpl(x)} ∩ SB(G)) ≤ P (M1) + P ({x : G(x) 6= Gpl(x)})− P (M(Gpl)) + 1− P (SB(G)) = P (M1) +RB(G) + EP [1(G(x) 6= Gpl(x))]− Err(Gpl)
Substituting P (M1) ≤ q from Lemma B.3 gives the desired result.
Proof of Theorem B.2. To complete the proof, we compute
Err(G) = P (M(G)) ≤ P (M(G) ∩ SB(G)) + P (SB(G)) = P (M1) + P (M2) + P (M3) +RB(G) ≤ 2(q +RB(G)) + EP [1(G(x) 6= Gpl(x))]− Err(Gpl)
(by Lemmas B.3 and B.6)

heading: B.2 PROOF OF THEOREM 4.3
text: In this section, we complete the proof of Theorem 4.3 by reducing Lemma 4.2 to Theorem B.2. This requires converting multiplicative expansion to (q, α)-additive-expansion, which is done in the following lemma. LetMi(Gpl) ,M(Gpl)∩Ci denote the incorrectly pseudolabeled examples with ground-truth class i. Lemma B.7. In the setting of Theorem 4.3, suppose that Assumption 4.1 holds. Then for any β ∈ (0, c− 1], Pi has (q, α)-additive-expansion onMi(Gpl) for the following choice of q, α:
q = βP (Mi(Gpl)) c− 1 α = (β − 1)P (Mi(Gpl))
(B.4)
Proof. Consider any set S ⊆ Mi(Gpl) with Pi(S) > βPi(Mi(Gpl))c−1 . Then by Assumption 4.1, Pi(N (S)) ≥ min{cPi(S), 1} ≥ cPi(S), where we used the fact that Pi(S) ≤ Pi(Mi(Gpl)) and c ≤ 1Pi(Mi(Gpl)) , so cPi(S) ≤ 1. Thus, we can obtain
Pi(N (S) \Mi(Gpl)) ≥ cPi(S)− Pi(Mi(Gpl)) = Pi(S) + (c− 1)Pi(S)− Pi(Mi(Gpl)) > Pi(S) + (β − 1)Pi(Mi(Gpl))
Here the last line used the fact that Pi(S) > βPi(Mi(Gpl))
c−1 . This implies that Pi has (q, α)-additiveexpansion onMi(Gpl) for the (q, α) given in (B.4).
We will now complete the proof of Lemma 4.2. Note that given Lemma 4.2, Theorem 4.3 follows immediately by noting that G? satisfies L0-1(G?, Gpl) = Err(Gpl) and RB(G?) ≤ µ by Assumption 3.3.
We first define the class-conditional pseudolabeling and robustness losses: L(i)0-1(G,G ′) , Pi({x : G(x) 6= G′(x)}), and R(i)B (G) , EPi [1(∃x′ ∈ B(x) such that G(x′) 6= G(x))]. We also define the class-conditional error as follows: Erri(G) , L (i) 0-1(G,G
?). We prove the class-conditional variant of Lemma 4.2 below. Lemma B.8. For any i ∈ [K], define
Li(G) , c+ 1
c− 1 L (i) 0-1(G,Gpl)− Erri(Gpl) +
2c
c− 1 R
(i) B (G) (B.5)
Then in the setting of Theorem 4.3 where Assumption 4.1 holds, we have the following error bound for class i:
Erri(G) ≤ Li(G) (B.6)
Proof. First, we consider the case where L(i)0-1(G,Gpl) + R (i) B (G) ≤ (c − 1)Erri(Gpl). In this case, we can apply Lemma B.7 with β ∈ (0, c− 1] chosen such that (β − 1)Erri(Gpl) = L(i)0-1(G,Gpl) +R (i) B (G)− Erri(Gpl) (B.7) We note that Pi has (q, α)-additive-expansion onMi(Gpl) for
q = β
c− 1 Erri(Gpl) (B.8)
α = (β − 1)Erri(Gpl) (B.9) Now by (B.7), we can apply Theorem B.2 with this choice of (q, α) to obtain
Erri(G) ≤ 2(q +R(i)B (G)) + L (i) 0-1(G,Gpl)− Erri(Gpl) (B.10)
= 2β
c− 1 Erri(Gpl) + 2R
(i) B (G) + L (i) 0-1(G,Gpl)− Erri(Gpl) (B.11)
= c+ 1
c− 1 L (i) 0-1(G,Gpl)− Erri(Gpl) +
2c
c− 1 R
(i) B (G) (plugging in the value of β)
= Li(G) (B.12) Next, we consider the case where L(i)0-1(G,Gpl) +R (i) B (G) > (c− 1)Erri(Gpl). Note that by triangle inequality, we have
Erri(G) = L (i) 0-1(G,G ?) ≤ L(i)0-1(G,Gpl) + L (i) 0-1(Gpl, G ?) (B.13)
= L (i) 0-1(G,Gpl) + 2Erri(Gpl)− Erri(Gpl) (B.14)
≤ L(i)0-1(G,Gpl) + 2
c− 1 (L
(i) 0-1(G,Gpl) +R (i) B (G))− Erri(Gpl) (B.15)
≤ c+ 1 c− 1 (L (i) 0-1(G,Gpl) +R (i) B (G))− Erri(Gpl) (B.16)
≤ c+ 1 c− 1 L (i) 0-1(G,Gpl) + 2c c− 1 R (i) B (G)− Erri(Gpl) (using c > 1)
= Li(G) (B.17)
Lemma 4.2 now follows simply by taking the expectation of the bound in (B.6) over all the classes.

heading: C PROOFS FOR UNSUPERVISED LEARNING
text: We will first prove an analogue of Lemma C.7 for a relaxed notion of expansion. We will then prove Theorem 3.6 by showing that multiplicative expansion implies this relaxed notion, defined below: Definition C.1 ((q, ξ)-constant-expansion). We say that distribution P satisfies (q, ξ)-constantexpansion if for all S ⊆ X satisfying P (S) ≥ q and P (S ∩ Ci) ≤ P (Ci)/2 for all i, the following holds:
P (N ?(S) \ S) ≥ min{ξ, P (S)}
As before, N ?(S) is defined by ∪i∈[K](N (S ∩ Ci) ∩ Ci). We will work with the above notion of expansion for this subsection. We first show that a B-robust labeling function which assigns sufficient probability to each class will align with the true classes. Theorem C.2. Suppose P satisfies (q, ξ)-constant-expansion for some q. If it holds thatRB(G) < ξ and
min i P ({x : G(x) = i}) > 2 max{q,RB(G)}
there exists a permutation π : [K]→ [K] satisfying the following: P ({x : π(G(x)) 6= G?(x)}) ≤ max{q,RB(G)}+RB(G) (C.1)
Define Ĉ1, . . . , ĈK to be the partition induced by G: Ĉi , {x : G(x) = i}. Lemma C.3. In the setting of Theorem C.2, consider any set of the formU , SB(G)∩i∈ICi∩j∈J Ĉj where I,J are arbitrary subsets of [K]. Then N ?(U) \ U ⊆ SB(G).
Proof. Consider any x ∈ N ?(U) \ U . There are two cases. First, if G(x) ∈ J , then by definition of N ?(·), x ∈ ∩i∈ICi ∩j∈J Ĉj . However, x /∈ U , which must imply that x /∈ SB(G). Second, if G(x) /∈ J , by definition of N ?(·) there exists x′ ∈ U such that B(x) ∩ B(x′) 6= ∅. It follows that for z ∈ B(x) ∩ B(x′), G(z) = G(x′) ∈ J . Thus, since G(x) /∈ J , G(x) 6= G(z) so x /∈ SB(G). Thus, it follows that N ?(U) \ U ⊆ SB(G).
Next, we show that every cluster found byGwill take up the majority of labels of some ground-truth class. Lemma C.4. In the setting of Theorem C.2, ∀ j, ∃i such that P (SB(G) ∩ Ci ∩ Ĉj) > P (SB(G)∩Ci)2 .
Proof. Assume for the sake of contradiction that there exists j such that for all i, P (SB(G) ∩ Ci ∩ Ĉj) ≤ P (SB(G)∩Ci)2 . Define the set Ui , SB(G) ∩ Ci ∩ Ĉj , and U , ∪iUi = SB(G) ∩ Ĉj . Note that {Ui}Ki=1 form a partition of U because {Ci}Ki=1 are themselves disjoint from one another. Furthermore, we can apply Lemma C.3 with I = [K] to obtain N ?(U) \ U ⊆ SB(G).
Now we observe that P (U) ≥ P (Ĉj) − P (SB(G)). Using the theorem condition that P (Ĉj) > 2P (SB(G)), it follows that
P (U) > P (Ĉj)
2 > max{q, P (SB(G))}
Furthermore for all i we note that
P (Ci \ Ui) ≥ P (SB(G) ∩ Ci)− P (Ui) ≥ P (SB(G) ∩ Ci)
2 ≥ P (Ui) (C.2)
Thus, P (Ci) ≥ 2P (Ui). Thus, by (q, ξ)-constant-expansion we have
P (N ?(U) \ U) ≥ min{ξ, P (U)} ≥ min{ξ, P (Ĉj)/2}
As N ?(U) \ U ⊆ SB(G), this implies RB(G) = P (SB(G)) ≥ min{ξ, P (Ĉj)/2}, a contradiction.
Lemma C.5. In the setting of Theorem C.2 and Lemma C.4, ∀ j, there exists a unique π(j) such that P (SB(G)∩Cπ(j)∩Ĉj) > P (SB(G)∩Cπ(j)) 2 , and P (SB(G)∩Ci∩Ĉj) ≤ P (SB(G)∩Ci 2 for i 6= π(j). Furthermore, π is a permutation from [K] to [K].
Proof. By the conclusion of Lemma C.4, the only way the existence of such a π might not hold is if there is some j where P (SB(G) ∩ Ci ∩ Ĉj) > P (SB(G)∩Ci2 for i ∈ {i1, i2}, where i1 6= i2. In this case, by the Pigeonhole Principle, as the conclusion of Lemma C.4 applies for all j ∈ [K] and there are K possible choices for i, there must exist i where P (SB(G)∩ Ci ∩ Ĉj) > P (SB(G)∩Ci)2 for j ∈ {j1, j2}, where j1 6= j2. Then P (SB(G)∩Ci ∩ Ĉj1) +P (SB(G)∩Ci ∩ Ĉj2) > P (SB(G)∩Ci), which is a contradiction.
Finally, to see that π is a permutation, note that if π(j1) = π(j2) for j1 6= j2, this would result in the same contradiction as above.
Proof of Theorem C.2. We will prove (C.1) using π defined in Lemma C.5. Define the set Uj , SB(G) ∩ Cπ(j) ∩k 6=j Ĉk. Note that Uj = {x : G(x) 6= j,G?(x) = π(j)} ∩ SB(G). Define U = ∪jUj , and note that {Uj}Kj=1 forms a partition of U . Furthermore, we also have U = {x : π(G(x)) 6= G?(x)}∩SB(G). We first show that P (U) ≤ max{q,RB(G)}. Assume for the sake of contradiction that this does not hold.
First, we claim that {N ?(Uj)\Uj}kj=1 ⊇ N ?(U)\U . To see this, consider any x ∈ Cπ(j)∩N ?(U)\ U . By definition, ∃x′ ∈ U such that B(x′) ∩ B(x) 6= ∅ and G?(x) = G?(x′), or x′ ∈ Cπ(j). Thus, it follows that x ∈ N ?(Cπ(j) ∩ U) \ U = N ?(Uj) \ U = N ?(Uj) \ Uj , where the last equality followed from the fact that N ?(Uj) and Uk are disjoint for j 6= k. Now we apply Lemma C.3 to each N ?(Uj) \ Uj to conclude that N ?(U) \ U ⊆ SB(G). Finally, we observe that
P (Uj) = P (SB(G) ∩ Cπ(j))− P (SB(G) ∩ Cπ(j) ∩ Ĉj) ≤ P (SB(G) ∩ Cπ(j)) 2 ≤ P (Cπ(j)) 2 (C.3)
by the definition of π in Lemma C.5. Now we again apply the (q, ξ)-constant-expansion property, as we assumed P (U) > q, obtaining
P (N ?(U) \ U) ≥ min{ξ, P (U)}
However, as we showed N ?(U) \ U ⊆ SB(G), we also have RB(G) = P (SB(G)) ≥ P (N ?(U) \ U) ≥ min{ξ, P (U)}. This contradicts P (U) > max{q,RB(G)} and RB(G) < ξ, and therefore P (U) ≤ max{q,RB(G)}.
Finally, we note that {x : π(G(x)) 6= G?(x)} ⊆ U ∪ SB(G). Thus, we finally obtain
P ({x : π(G(x)) 6= G?(x)}) ≤ P (U) + P (SB(G)) ≤ max{q,RB(G)}+RB(G)

heading: C.1 PROOF OF THEOREM 3.6
text: In this section, we prove Theorem 3.6 by converting multiplicative expansion to (q, ξ)-constantexpansion and invoking Theorem C.2. The following lemma performs this conversion.
Lemma C.6. Suppose P satisfies (1/2, c)-multiplicative-expansion (Definition 3.1) on X . Then for any choice of ξ > 0, P satisfies ( ξ c−1 , ξ ) -constant expansion.
Proof. Consider any S such that P (S ∩ Ci) ≤ P (Ci)/2 for all i ∈ [K] and P (S) > q. Define Si , S ∩ Ci. First, in the case where c ≥ 2, we have by multiplicative expansion
P (N ?(S) \ S) ≥ ∑ i P (N ?(Si))− P (Si)
≥ ∑ i min{cP (Si), P (Ci)} − P (Si)
≥ ∑ i P (Si) (because c ≥ 2 and P (Si) ≤ P (Ci)/2)
Thus, we immediately obtain constant expansion.
Now we consider the case where 1 ≤ c < 2. By multiplicative expansion, we must have P (N ?(S) \ S) ≥ ∑ i min{cP (Si), P (Ci)} − P (Si)
≥ ∑ i (c− 1)P (Si) (because c < 2 and P (Si) ≤ P (Ci)/2)
≥ (c− 1)q = ξ
The following lemma states an accuracy guarantee for the setting with multiplicative expansion.
Lemma C.7. Suppose Assumption 3.2 holds for some c > 1. If classifier G satisfies
min i
EP [1(G(x) = i)] > max { 2
c− 1 , 2
} RB(G)
then the unsupervised error is small: Errunsup(G) ≤ max { c
c− 1 , 2
} RB(G) (C.4)
We now prove Lemma C.7, which in turn immediately gives a proof of Theorem 3.6. Proof of Lemma C.7. By Lemma C.6, P must satisfy ( RB(G) c−1 , RB(G) ) -constant-expansion. As we
also have mini P ({x : G(x) = i}) > max { 2 c−1 , 2 } RB(G), we can now apply Theorem C.2 to conclude that there exists permutation π : [K]→ [K] such that
P ({x : π(G(x)) 6= G?(x)}) ≤ max { c
c− 1 , 2
} RB(G)
as desired.

heading: C.2 JUSTIFICATION FOR EXAMPLES 3.4 AND 3.5
text: To avoid the disjointness issue of Example 3.4, we can redefine the ground-truth class G?(x) to be the most likely label at x. This also induces truncated class-conditional distributions P 1, P 2 where the overlap is removed. We can apply our theoretical analysis to P 1, P 2 and then translate the result back to P1, P2, only changing the bounds by a small amount when the overlap is minimal.
To justify Example 3.4, we use the Gaussian isoperimetric inequality (Bobkov et al., 1997), which states that for any fixed p such that Pi(S) = p where i ∈ {1, 2}, the choice of S minimizing Pi(N (S)) is given by a halfspace: S = H(p) , {x : w>(x − τi) ≤ Φ−1(p)} for vector w with ‖w‖ = √ d. It then follows that setting r = 1√
d , N (H(p)) ⊇ {x + t w‖w‖2 : x ∈ H(p), 0 ≤ t ≤
r} ⊇ {x : w>(x − τi) ≤ Φ−1(p) + r √ d}, and thus P (N (H(p))) ≥ Φ(Φ−1(p) + r √ d). As P (N (H(p)))/P (H(p)) is decreasing in p for p < 0.5, our claim about expansion follows. To see
our claim about separation, consider the sets Xi , {x : (x − τi)>vij ≤ ‖τi−τj‖2 − r/2 ∀j}, where vij ,
τj−τi ‖τj−τi‖2 . We note that these sets are β-separated from each other, and furthermore, for the
lower bound on ‖τi − τj‖ in the example, note that Xi has probability 1− µ under Pi.
For Example 3.5, we note that for B(x) , {x′ : ‖x′ − x‖2 ≤ r}, N (S) ⊇ M({x′ : ∃x ∈ M−1(S) such that ‖x′ − x‖ ≤ r/κ}). Thus, our claim about expansion reduces to the Gaussian case.

heading: D ALL-LAYER MARGIN GENERALIZATION BOUNDS

heading: D.1 END-TO-END GUARANTEES
text: In this section, we provide end-to-end guarantees for unsupervised learning, semi-supervised learning, and unsupervised domain adaptation for finite training sets. For the following two theorems, we take the notation Õ(·) as a placeholder for some multiplicative quantity that is poly-logarithmic in n, d. We first provide the finite-sample guarantee for unsupervised learning.
Theorem D.1. In the setting of Theorem 3.6 and Section 3.3, suppose that Assumption 3.2 holds. Suppose that G = arg maxi Fi is parametrized as a neural network of the form F (x) , Wpφ(· · ·φ(W1x) · · · ). With probability 1 − δ over the draw of the training sample P̂ , if for any choice of t > 0 and {uy}Ky=1 with uy > 0 ∀y, it holds that
EP̂ [1(m(F, x, y) ≥ uy)]−max { 2
c− 1 , 2
} EP̂ [1(mB(F, x) ≤ t)]
≥ Õ ((∑ i
√ q‖Wi‖F c− 1
)( 1
uy √ n
+ 1
t √ n
)) + ζ for all y ∈ [K]
then it follows that the population unsupervised error is small: Errunsup(G) ≤ max { c
c− 1 , 2
} EP̂ [1(mB(F, x) ≤ t)] + Õ (∑ i √ q‖Wi‖F t √ n ) + ζ
where ζ , O (
1 c−1
√ log(K/δ)+p logn
n
) is a low-order term.
The following theorem provides the finite-sample guarantee for unsupervised domain adaptation and semi-supervised learning.
Theorem D.2. In the setting of Theorem 4.3 and Section 3.3, suppose that Assumption 4.1 holds. Suppose that G = arg maxi Fi is parametrized as a neural network of the form F (x) , Wpφ(· · ·φ(W1x) · · · ). For any t1, t2 > 0, define the following quantities:
B1 , 2EP̂ [1(mB(F, x) ≤ t1)] + EP̂ [1(m(F, x,Gpl(x)) ≤ t2)]
+ Õ ((∑ i √ q‖Wi‖F )( 1 t1 √ n + 1 t2 √ n )) + ζ
B2 , 4EP̂ [1(mB(F, x) ≤ t1)] + 3EP̂ [1(m(F, x,Gpl(x)) ≤ t2)]
+ Õ ((∑ i √ q‖Wi‖F )( 1 t1 √ n + 1 t2 √ n )) + ζ
where ζ , O (
1 c−1
√ log(K/δ)+p logn
n
) is a low-order term. With probability 1− δ over the draw of
the training sample P̂ , for all choices of t1, t2 > 0, it holds that Err(G) ≤ max { B1 − Err(Gpl), B2 − ( 3− 4
c− 1
) Err(Gpl) }

heading: D.2 PROOFS FOR SECTION 3.3
text: In this section, we provide a proof sketch of Theorem 3.7. The proof follows the analysis of (Wei & Ma, 2019b) very closely, but because there are some minor differences we include it here for completeness. We first state additional bounds for the other quantities in our objectives, which are proved in the same manner as Theorem 3.7.
Theorem D.3. With probability 1 − δ over the draw of the training sample P̂ , all neural networks G = arg maxi Fi of the form F (x) ,Wpφ(· · ·φ(W1x)) will satisfy
L0-1(G,Gpl) ≤ EP̂ [1(m(F, x,Gpl(x)) ≤ t)] + Õ (∑ i √ q‖Wi‖F t √ n ) + ζ
for all choices of t > 0, where ζ , O (√
log(1/δ)+p logn n
) is a low-order term, and Õ(·) hides
poly-logarithmic factors in n and d.
Theorem D.4. With probability 1 − δ over the draw of the training sample P̂ , all neural networks G = arg maxi Fi of the form F (x) ,Wpφ(· · ·φ(W1x)) will satisfy
EP [1(G(x) = y)] ≥ EP̂ [1(m(F, x, y) ≥ t)]− Õ (∑ i √ q‖Wi‖F t √ n ) − ζ
for all choices of y ∈ [K], t > 0, where ζ , O (√
log(K/δ)+p logn n
) is a low-order term, and Õ(·)
hides poly-logarithmic factors in n and d.
We now overview the proof of Theorem 3.7, as the proofs of Theorem D.3 and D.4 follow identically. We first formally define the all-layer margin m(F, x, y) for neural net F evaluated on example x with label y. We recall that F computes the function F (x) , Wpφ(· · ·φ(W1x) · · · ). We index the layers of F as follows: define f1(x) , W1x, and fi(h) , Wiφ(h) for 2 ≤ i ≤ p, so that F (x) = fp ◦ · · · ◦ f1(x). Letting δ = (δ1, . . . , δp) denote perturbations for each layer of F , we define the perturbed output F (x, δ) as follows:
h1(x, δ) = f1(x) + δ1‖x‖2 hi(x, δ) = fi(hi−1(x, δ)) + δi‖hi−1(x, δ)‖2 F (x, δ) = hp(x, δ)
Now the all-layer margin m(F, x, y) is defined by
m(F, x, y) , min δ √√√√ p∑ i=1 ‖δi‖22
subject to arg max i F (x, δ) 6= y
As is typical in generalization bound proofs, we define a fixed class of neural net functions to analyze, expressed as
F , {x 7→Wpφ(· · ·φ(W1x) · · · ) : Wi ∈ Wi ∀i}
where Wi is some class of possible instantiations of the i-th weight matrix. We also overload notation and let Wi , {h 7→ Wih : Wi ∈ Wi} denote the class of functions corresponding to matrix multiplication by a weight inWi. Let ‖ · ‖op denote the matrix operator norm. For a function class G, we letN‖·‖( ,G) denote the -covering number of G in norm ‖ · ‖. The following condition will be useful for the analysis: Condition D.5 (Condition A.1 from (Wei & Ma, 2019b)). We say that a function class G satisfies the −2 covering condition with respect to norm ‖ · ‖ with complexity C‖·‖(G) if for all > 0,
logN‖·‖( ,G) ≤ ⌊ C2‖·‖(G) 2 ⌋
To sketch the proof technique, we only provide the proof of (3.6) in Theorem 3.7, as the other bounds follow with the same argument. The following lemma boundsRB(G) in terms of the robust all-layer margin mB. Lemma D.6 (Adaptation of Theorem A.1 of (Wei & Ma, 2019b)). Suppose that weight matrix mappingsWi satisfy Condition D.5 with operator norm ‖ · ‖op and complexity function C‖·‖op(Wi). With probability 1 − δ over the draw of the training data, for all t > 0, all classifiers F ∈ F will satisfy
RB(G) ≤ EP̂ [1(mB(F, x) ≤ t)] +O (∑ i C‖·‖op(Wi) t √ n log n ) + ζ (D.1)
where ζ , O (√
log(1/δ)+logn n
) is a low-order term.
The proof of Lemma D.6 mirrors the proof of Theorem A.1 of (Wei & Ma, 2019b). The primary difference is that because we seek a bound in terms a threshold on the margin whereas (Wei & Ma, 2019b) prove a bound that depends on average margin, we must analyze the generalization of a slightly modified loss. Towards proving Lemma D.6, we first define |||δ||| , ‖(‖δ1‖2, . . . , ‖δp‖2)‖2 for perturbation δ, and |||F ||| , ‖(‖W1‖op, . . . , ‖Wp‖op)‖2. We show that mB(F, x) is Lipschitz in F for fixed x with respect to ||| · |||. Claim D.7. Choose F, F̂ ∈ F . Then for any x ∈ X ,
|mB(F, x)−mB(F̂ , x)| ≤ |||F − F̂ |||
The same conclusion holds if we replace mB with m.
Proof. We consider two cases:
Case 1: arg maxi F (x)i = arg maxi F̂ (x)i. Let y denote the common value. In this case, the desired result immediately follows from Claim E.1 of (Wei & Ma, 2019b).
Case 2: arg maxi F (x)i 6= arg maxi F̂ (x)i. In this case, the construction of Claim A.1 in (Wei & Ma, 2019b) implies that 0 ≤ mB(F, x) ≤ |||F − F̂ |||. (Essentially we choose δ with |||δ||| ≤ |||F − F̂ ||| such that F (x, δ) = F̂ (x).) Likewise, 0 ≤ mB(F̂ , x) ≤ |||F − F̂ |||. As a result, it must follow that |mB(F, x)−mB(F̂ , x)| ≤ |||F − F̂ |||.
For t > 0, define the ramp loss ht as follows:
ht(a) = 1− 1(a ≥ 0) min{a/t, 1}
We now define the hypothesis class Lt , {ht ◦mB(F, ·) : F ∈ F}. We now bound the Rademacher complexity of this hypothesis class: Claim D.8. In the setting of Lemma D.6, suppose that Wi satisfies Condition D.5 with operator norm ‖ · ‖op and complexity C‖·‖op(Wi). Then
Radn(Lt) ≤ O (∑
i C‖·‖op(Wi) t √ n log n ) As the proof of Claim D.8 is standard, we provide a sketch of its proof.
Proof sketch of Claim D.8. First, by Lemma A.3 of (Wei & Ma, 2019b), we obtain that F satisfies Condition D.5 with norm ||| · ||| and complexity C|||·|||(F) , ∑ i C‖·‖op(Fi). Now let F̂ be a t -cover of F in ||| · |||. We define the L2(Pn)-norm of a function f : X → R as follows:
‖f‖L2(Pn) , √ EP̂ [f(x)2]
Then it is standard to show that
L̂t , {ht ◦mB(F̂ , ·) : F̂ ∈ F̂}
is a -cover of Lt in L2(Pn)-norm, because ht is 1/t-Lipschitz and mB(F, x) is 1-Lipschitz in F for norm ||| · ||| for any fixed x. It follows that logNL2(Pn)( ,Lt) ≤ ⌊ C2|||·|||(F) t2 2 ⌋ . Now we apply
Dudley’s Theorem:
Radn(Lt) ≤ inf β>0
( β +
1√ n ∫ ∞ β √ logNL2(Pn)( ,Lt)d )
≤ inf β>0 β + 1√ n ∫ ∞ β √√√√⌊C2|||·|||(F) t2 2 ⌋ d  A standard computation can be used to bound the quantity on the right, giving the desired result.
Proof of Lemma D.6. First, by the standard relationship between Rademacher complexity and generalization, Claim D.8 lets us conclude that with probability 1 − δ, for any fixed t > 0, all F ∈ F satisfy:
EP [ht(mB(F, x))] ≤ EP̂ [ht(mB(F, x))] +O (∑ i C‖·‖op(Wi) t √ n log n+ √ log 1/δ n )
We additionally note that ht(mB(F, x)) = 1 when x /∈ SB(G), because in such cases mB(F, x) = 0. It follows that 1(x /∈ SB(G)) ≤ ht(mB(F, x)). Thus, we obtain
RB(G) ≤ EP̂ [1(mB(F, x) ≤ t)] +O (∑ i C‖·‖op(Wi) t √ n log n+ √ log 1/δ n ) (D.2)
It remains to show that (D.1) holds for all t. It is now standard to perform a union bound over choices of t in the form tj , tmin2j , where tmin , ∑ i C‖·‖op (Wi)√
n log n and 0 ≤ j ≤ O(log n), so
we only sketch the argument here. We union bound over (D.2) for t = tj with failure probability δj = δ/2
j+1, so (D.2) will hold for all t1, . . . , tjmax with probability 1 − δ. For any choice of t, there will either be j such that t/2 ≤ tj ≤ t, or (D.1) must trivially hold. (See Theorem C.1 of (Wei & Ma, 2019b) for a more detailed justification.) As a result, there will be some j such that the right hand side of (D.2) is bounded above by the right hand side of (D.1), as desired.
Proof sketch of Theorem 3.7. By Lemma B.2 of (Wei & Ma, 2019b), we have C‖·‖op({W : ‖W‖F ≤ a}) = O( √ q log qa). Thus, to obtain (3.6), it suffices to apply Lemma D.6 for all choices of a using a standard union bound technique; see for example the proof of Theorem 3.1 in (Wei & Ma, 2019b). To obtain the other generalization bounds, we can follow a similar argument for Lemma D.6 to prove its analogue for other variants of all-layer margin, and then repeat the same union bound over the weight matrix norms as before.

heading: D.3 DATA-DEPENDENT LOWER BOUNDS ON ALL-LAYER MARGIN
text: We will now provide lower bounds on the all-layer margins used in Theorem 3.7 in the case when the activation φ has ν-Lipschitz derivative. In this section, it will be convenient to modify the indexing to count the activation as its own layer, so there are 2p− 1 layers in total. Let s(i)(x) denote the ‖ · ‖2 norm of the layer preceding the i-th matrix multiplication, where the parenthesis in the subscript distinguishes between weight indices and layer indices (which also include the activation layers). Define νj←i(x) to be the Jacobian of the j-th layer with respect to the i− 1-th layer evaluated at x. Define γ(F (x), y) , F (x)y − maxi6=y F (x)i. We use the following quantity to measure stability in the layer following W(i):
κ(i)(x, y) , s(i−1)(x)ν2p−1←2i(x)
γ(F (x), y) + ψ(i)(x, y)
for a secondary term ψ(i)(x, y) given by
ψ(i)(x, y) , p−1∑ j=i s(i−1)(x)ν2j←2i(x) s(j)(x) + ∑ 1≤j≤2i−1≤j′≤2p−1 νj′←2i(x)ν2i−2←j(x) νj′←j(x)
+ ∑
1≤j≤j′≤2p−1 j′∑ j′′=max{2i,j},j′′even ννj′←j′′+1(x)νj′′−1←2i(x)νj′′−1←j(x)s(i−1)(x) νj′←j(x)
We now have the following lower bounds on m(F, x, y) and mB(F, x): Proposition D.9 (Lemma C.1 from (Wei & Ma, 2019b)). In the setting above, if γ(F (x), y) > 0, we have
m(F, x, y) ≥ 1 ‖{κ(i)(x, y)}pi=1‖2
Furthermore, if γ(F (x′), arg maxi F (x)i) > 0 for all x ′ ∈ B(x), then
mB(F, x) ≥ min x′∈B(x)
1
‖{κ(i)(x′, arg maxi F (x)i)} p i=1‖2

heading: E EXPERIMENTS

heading: E.1 EMPIRICAL SUPPORT FOR EXPANSION PROPERTY USING GANS
text: In this section we provide additional details regarding the GAN verification depicted in Figure 1 (left). We use 128 by 128 images sampled from a pre-trained BigGAN (Brock et al., 2018). We categorize images into 10 superclasses chosen in the robustness library of Engstrom et al. (2019): dog, bird, insect, monkey, car, cat, truck, fruit, fungus, boat. These superclasses consist of all ImageNet classes which fall under the category of the superclass. To sample an image from a superclass, we uniformly sample an ImageNet class from the superclass and then sample from the GAN conditioned on this class. We sample 1000 images per superclass and train a ResNet-56 (He et al., 2016) to predict the superclass, achieving 93.74% validation accuracy.
Next, we approximately project GAN images onto the mislabeled set of the trained classifier. We approximate the projection as follows: we optimize an objective consisting of the `2 distance from the original image and the negative cross entropy loss of the pretrained classifier w.r.t the superclass label. Letting M denote the GAN mapping, x the original image, y the label, and F the pre-trained classifier, the objective is as follows:
min z ‖x−M(z)‖22 − λce`cross-ent(F (M(z)), y)
We optimize z for 2000 gradient descent steps using λce = 10 and a learning rate of 0.0003, intialized with the same latent variable as was used to generate x. The resulting M(z) is a neighbor of x in the setM(F ), the mistakenly labeled set of F . After performing this procedure on 200 GAN images sampled from each class, we find that 20% of these images x have a neighbor x′ ∈ M(F ) with ‖x − x′‖2 ≤ 19.765. Note that this corresponds to modifying each pixel by 0.024 on average for pixel values in [0, 1]. We use M̂ to denote the set of mislabeled neighbors found this way. From visual inspection, we find that the neighbors appear very visually similar to the original image, suggesting that it is appropriate to regard these images as “neighbors”. In Figure 1, we visualize typical examples of the neighbors found by this procedure. Thus, setting B(x) = {x′ : ‖x′ − x‖2 ≤ 19.7652 }, the set M(F ), which has probability 0.0626, has a relatively large neighborhood induced by B of probability 0.2. This supports our expansion assumption, especially the additive notion in Section B.
Next, we use this same classifier as a pseudolabeler to perform self-training on a dataset of 10000 additional unlabeled images per superclass, where these images were sampled independently from the 200 GAN images in the previous step. We add input consistency regularization to the selftraining procedure using VAT (Miyato et al., 2018). After self-training, the validation accuracy of new classifier G̃ improves to 95.69%.
Furthermore, we evaluate performance of the self-trained classifier G̃ on a subset of M̂with distance greater than 1 from its neighbor. We let M̂′ denote this subset. We choose to filter M̂ this way to rule out cases where the original neighbor was already misclassified. We find that G̃ achieves 67.27% accuracy on examples from M̂′.
In addition, Figure 3 demonstrates that G̃ is more accurate on examples from M̂′ which are closer to the original neighbor used to initialize the projection. This provides evidence that inputconsistency-regularized self-training is indeed correcting the mistakes of the pseudolabeler by relying on correctly-pseudolabeled neighbors for denoising, because Figure 3 shows that examples which are closer to their neighbors are more likely to be denoised. Finally, we also remark that Figure 3 provides evidence that the denoising mechanism does indeed generalize from the self-training dataset to the population, because neither examples in M̂′ nor their original neighbors appeared in the self-training dataset.

heading: E.2 PSEUDOLABELING EXPERIMENTS
text: In this section, we verify that the theoretical objective in (4.1) works as intended. We consider an unsupervised domain adaptation setting where we perform self-training using pseudolabels from the source classifier. We evaluate the following incremental steps towards optimizing the ideal objective (4.1), with the aim of demonstrating the improvement from adding each component of our theory:
Source: We train a model on the labeled source dataset and directly evaluate it on the target validation set.
PL: Using the classifier obtained above, we produce pseudolabels on the target training set and train a new classifier to fit these pseudolabels.
PL+VAT: We consider the case when the perturbation set B(x) in our theory is given by an `2 ball around x. We train a classifier to fit pseudolabels while regularizing adversarial robustness on the target domain using the VAT loss of (Miyato et al., 2018), obtaining the following loss over classifier F :
L(F ) , Lcross-ent(F,Gpl) + λvLVAT(F )
Note that this loss only enforces true stability on examples where F (x) correctly predicts Gpl(x). For pseudolabels not fit by F , the cross-entropy loss discourages the model from being confident, and therefore the discrete labels may still easily flip under input transformations for such examples.
PL+VAT+AMO: Because the theoretical guarantees in Theorem 4.3 are for the population loss, we apply the AMO algorithm of (Wei & Ma, 2019b) in the VAT loss term to regularize the robust all-layer margin (see Section 3.3). This encourages robustness on the training set to generalize better.
PL+VAT+AMO+MinEnt: Note that PL+VAT only encourages robustness for examples which fit the pseudolabel, but an ideal classifier should not fit pseudolabels which disagree with the groundtruth. As the bound in Theorem 4.3 improves with the robustness of F , we aim to also encourage robustness for examples where F does not match Gpl. To this end, we modify the loss to allow the classifier to ignore c fraction of the pseudolabels and optimize min-entropy loss on these examples instead. We provide additional details on how to select the pseudolabels to ignore below.
MinEnt+VAT+AMO: We investigate the impact of the pseudolabels by removing them from the objective. We instead rely on the following loss which simply performs entropy minimization on the target while fitting the source dataset:
L(F ) , λsLcross-ent, src(F ) + λtLmin-ent, tgt(F ) + λvLVAT, tgt(F )
We include the source loss for training stability. As before, we apply the AMO algorithm in the VAT loss term to encourage robustness of the classifier to generalize.
Table 1 shows the performance of these methods on six unsupervised domain adaptation benchmarks. We see that performance improves as we add additional components to the objective to match the theory. We note that the goal of these experiments is to validate our theory, not to push state-ofthe-art for these datasets, which often relies on domain confusion (Tzeng et al., 2014; Ganin et al., 2016; Tzeng et al., 2017), which is outside the scope of our theory. For example, Shu et al. (2018) achieve strong results on these benchmarks by using a domain confusion technique while optimizing VAT loss and entropy minimization on the target while training on labeled source data. Our results for MinEnt+VAT+AMO show that when the domain confusion is removed, performance suffers and is actually worse than training on the source only for all datasets except STL-10 to CIFAR-10. We provide additional experimental details below. We use the same dataset setup and model architecture for each dataset as (Shu et al., 2018). All classifiers are optimized using SGD with cosine learning rate and weight decay of 5e-4 and target batch size of 128. The value of the learning rate is tuned on the validation set for each dataset and method in the range of values {0.03, 0.01, 0.003, 0.001}. We choose λv , the coefficient of the VAT loss, by tuning in the same manner in the range {3, 10, 30}. For MinEnt+VAT+AMO, we fix the best hyperparameters for PL+VAT+AMO+MinEnt and tune λs ∈ {0.25, 0.5, 1} and fix λt = 1. We also tune the batch size for the source loss in {64, 128}. Table 1 depicts accuracies on the target validation set. We use early stopping and display the best accuracy achieved during training. All displayed accuracies are on one run of the algorithm, except for the (+MinEnt) method, where we average over 3 independent runs with the same hyperparameters.
To compute the VAT loss (Miyato et al., 2018), we take one step of gradient descent in image space to maximize the KL divergence between the perturbed image and the original. We then normalize this gradient to `2 norm 1 and add it to the image to obtain the perturbed version. To incorporate the AMO algorithm of (Wei & Ma, 2019a), we also optimize adversarial perturbations to the three hidden layers preceding pooling layers in the DIRT-T architecture. The initial values of the perturbations are set to 0, and we jointly optimize them with the perturbation to the input using one step of gradient ascent with a learning rate of 1.
Finally, we provide details on how we choose pseudolabels to ignore for the PL+VAT+AMO+MinEnt objective. Some care is required in this step to prevent the optimization objective from falling into bad local minima. We will maintain a model whose weights are the exponential moving average of the past model weights, Fema. Every gradient update, the weights of Fema are updated by Wema ← 0.999Wema + 0.001Wcurr, where Wcurr is the current model weight after the gradient update. Our aim is to throw out τi-fraction of pseudolabels which maximize `cross-ent(Fema(x), Gpl(x)), where Gpl(x) is the pseudolabel for example x, and i indexes the current iteration. We will increase τi linearly from 0 to its final value τ over the course of training. Towards this goal, we maintain an exponential moving average of the (1− τi)- quantile of the loss, which is updated every iteration using the (1−τi)-quantile of the loss `cross-ent(Fema(x), Gpl(x)) computed on the current batch. We ignore pseudolabels where this loss value is above the maintained exponential moving average for the (1− τi)-th loss quantile.

Review summaries:
of the paper: The paper gives a theoretical justification of self-training. It proposes a new notion of "expansion" - the amount of data distribution in the neighbor of an example. Here the neighbor means adding perturbations to the example, or augmentations of the example. When the label distribution satisfies nice expansion properties and that classes are properly separated according to the neighbors, the paper proves distributional guarantees of self-training. Combining with generalization bounds of DNNs, the paper also derives finite sample bounds for DNNs. The paper also verifies the expansion assumption via experiments using a GAN.

This work provides a unified framework to analyze the self-training, semi-supervised algorithms. The key assumptions are 1) the “expansion” assumption which characterizes the low-probability data subset must expand to a neighborhood with large probability; and 2) the neighborhoods of samples from different classes have small overlap.  Then the authors established the upper bound of the prediction error on the population when minimizing the self-training and input-consistency based loss on the population. They also extend their results to a finite-sample setting and semi-supervised setting as well.  

This paper provides a theoretical analysis of self-training for semi-supervised learning, unsupervised domain adaptation, and unsupervised learning. The authors propose a novel assumption that they dub _expansion_ to effect this analysis. The expansion assumption requires that the neighborhood of small sets have a class conditional distribution that is large. Under this assumption, the authors show population results for an algorithm that performs self-training under the objective that enforces input consistency.