Theoretical Analysis of Self-Training with Deep Networks on Unlabeled Data
Authors: Colin Wei
Kendrick Shen
Yining Chen
Tengyu Ma
Venue: ICLR 2021 Oral (2021)
Keywords: deep learning theory
domain adaptation theory
unsupervised learning theory
semi-supervised learning theory

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 low-probability 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.

Published as a conference paper at ICLR 2021
THEORETICAL ANALYSIS OF SELF-TRAINING WITH DEEP NETWORKS ON UNLABELED DATA
Colin Wei & Kendrick Shen & Yining Chen & Tengyu Ma
Department of Computer Science Stanford University Stanford, CA 94305, USA
[colinwei, kshen6, cynnjjs, tengyuma Beergyuma@sstanforceee @stanford.edu
ABSTRACT
Self-training algorithms, which train a model fit pseudolabels predicted by an- other previously-learned model, have been very successful for learning with unla- beled data using neural networks. However, the current theoretical understanding of self-training only applies to linear models. This work provides unified theo- retical analysis of self 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 low- probability subset of the data must expand neighborhood with large probabil- ity relative to the subset. We also assume that neighborhoods of examples in dif- ferent 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-truit -ruth labels. By using off- off-the-shelf generalization bounds, we immediately convert this result to sample complexity guarantees for neural nets that are polynomial the margin and Lipschitzness. Our results help explain the empirical successes of recently proposed self-training algorithms which use input consistency regularization.
INTRODUCTION
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 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-Davis et al., 2010; Ganin & Lempitsky, 2015; Ganin et al., 2016; Tzeng 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 a related distribution. Recent progress in unsupervised learning 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.
representation
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 previously leamed model (Yarowsky, 1995; Grandvalet & Bengio, 2005; Lee, 2013). Recent work also extends these methods enforce stability of predictions under input transformations such as adversarial perturbations (Miyato et al., 2018) 10 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 use unlabeled data has lagged. Whereas supervised learning is relatively well-understood, statistical tools for reasoning about unlabeled data not 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 al., 2004).

---

Published as a conference paper at ICLR 2021
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 Gaussian. Kumar et al. (2020) also analyze self-training in setring where gradual domain shift occurs over multiple timesteps but assume 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- 2013).
This paper provides a unified theoretical analysis of self-training with deep networks for semi- supervised 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 deep network can achieve high accuracy on true labels, using un- labeled sample size that 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 P. be the distribution of data conditioned on class i, expansion states that for small subset S of examples with class i,
P: (neighborhood of S) 2 cP.(S)
(1.1)
where and c >>> 1 is the expansion factor. The neighborhood will be defined to incorporate data aug- mentation, but for now can be thought of as collection of points with 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 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 classifier G to be consistent on neighboring examples:
R(G) = Fzz max
neighbor af (G(x) o G(z'))
(1.2)
For unsupervised domain adaptation and semi-supervised learning, we analyze an algorithm which fits 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 accu- racy 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 pre- dicting true classes, up to 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 e- times the mass of the mistaken set by expansion). We note that expansion only required on the population distribution, but self-training is performed on the empirical samples. Due to the extrapolation power of parametric methods, the sical-to-global consistency effect of expansion occurs implicitly on the population. In contrast, reigrort 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 guar- antees for deep neural net models for unsupervised learning, semi-supervised learning, and unsuper-
2

---

Published as a conference paper at ICLR 2021
Paostsfaaael: dlg
Pseucoahel
montey
Pseudolabel:
closs: dog
Soparable by
Class:
cow
Pseudolabel:
cat
Poeudstabel: Insect
Preucoiabel: teline
P(Neighbors of 2 cP(5)
Neightor cornect
seeucolabel entine domain
Nearest neightor trainingg set
preudolabeled neighbors
Correctlyy
pseudelabeled
Mistakenly
Set
Figure 1: Left: demonstrating expansion assumption. Verifying the expansion assumption quires access to the population distribution and therefore we use the distribution generated by Big- GAN (Brock al., 2018). We display typical examples of mistakenly classified images and their correctly classified neighbors, found by searching the entire GAN manifold (not just the training set). For contrast, we also display their nearest neighbors in the training of 100K GAN images, which are much further away. This supports the intuition and assumption that expansion holds for the population set but not the empirical set. (More details are in Section E.1.) Right: assump- tions and setting for pseudolabeling. For self-training with pseudolabels, the region of correctly pseudolaheled examples (in green) will be used denoise examples with incorrect pseudolabels (in red), because by expansion, the green area will have large mass which is least - 1 times the mass of the red area. As explained in the introduction, this ensures that classifier which fits the pseudolabels and is consistent w.r.t. input transformations will achieve high accuracy true labels.
vised domain adaptation. Prior works (Rigollet, 2007; Singh 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, guarantees involving the population loss can be converted to fi- nite sample results using off-the-shelf generalization bounds (Theorem 3.7). When a neural net can separate ground-truth truth classes with large margin, the sample complexities from these bounds can be small, that is, polynomial in dimension.
Finally, note that our regularizer R(-) corresponds to enforcing consistency w.r.. 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 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 ex- plain empirical observations that consistency regularization based on aggressive data augmentation or adversarial training can improve performance with unlabeled data (Shu et al., 2018; Xie al., 2019; Berthelot et al., 2019; Sohn et al., 2020; Xie et al., 2020; Chen et al., 2020a).
In summary, our contributions include: we propose a simple and realistic expansion assumption which states that the data distribution has connectivity within the manifold of 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 appli- cable to deep networks with polynomial unlabeled samples via off thel- generalization bounds.
1.1 ADDITIONAL RELATED WORK
Self-training via pseudolaheling (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 al., 2018), well data augmentations (Xie et al., 2019).
3

---

Published as a conference paper at ICLR 2021
For unsupervised learning, self-training objective is closely related to BYOL (Grill al., 2020), a recent state-of-the-an 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 pop- ular 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 our setting are algorithms which learn represen- tations 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 different class of algorithms than ours.
Prior theoretical works analyze contrastive learning by assuming access to document data distributed according to 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 cnarmation-theoredee properties of representation learning (Tian et al., 2020; Tsai 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 & Ben- David, 2013). However, these papers leverage unlabeled data using non-parametric methods, re- quiring unlabeled sample complexity that 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- 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 wehpage, 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 setting into the co-training frame- work 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 neigh- boring 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 consis- tency 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 Been-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 domain adaptation. Globerson et al. (2017) demonstrate semi- supervised learning can outperform supervised learning in labeled sample complexity but assume full knowledge of the unlabeled distribution. (Mobahi 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.
2 PRELIMINARIES AND NOTATIONS
We let P denote distribution of unlabeled examples over input space X. For unsupervised learning, P is the only relevant distribution. For unsupervised domain adaptation, we also define a source distribution P.r. and let Gp denote a source classifier trained on a labeled dataset sampled from P.n-
4

---

Published as a conference paper at ICLR 2021
To translate these definitions to semi-supervised learning, we set Pac and P to be the same, except Pare gives access to labels. We amalyze algorithms which only depend on Pate through Gpt.
We consider classification and assume the data is partitioned into K classes, where the class of I E X' is given by the ground-trutt G*(x) (x) for G* : + [K]. We let P. denote the classcconditional distribution of I conditioned on G* (2) = i. We assume that each example x has unique label, so P., P3 have disjoint support for * j. Let P A fai,...., ..)) C 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 + IRK 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 max; F(z);: (where ties are broken lexicographically).
Pseudolabels. Pseudolabeling methods are form of self-training for semi- sunii-spereised learning and domain adaptation where the source classifier Gpt X + [K] is used to predict pseudolabels on the unlabeled target data (Lee, 2013). These methods then train a fresh classifier to fit these pseudola- bels, for example, using the standard cross entropy loss: (F) a Ep (eressss-cal (F(z), Gp(()))] Our theoretical analysis applies to a greudolabel-based objective. Other forms of self- self-training include entropy minimization, which closely related, and in certain settings, equivalent to pseudolabeling where the pseudolabels are updated every iteration (Lee, 2013; Chen et al., 2020c).
3 EXPANSION PROPERTY AND GUARANTEES FOR UNSUPERVISED LEARNING
In this section we will first introduce our key assumption on expansion. We then study the implica- tions of expansion for unsupervised learning. We show that 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).
3.1 EXPANSION PROPERTY
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)= A {x's 3T E T such that [Tx)l < r to be the set of points with distance from some data augmentation of x. We can think of r as a value much smaller than the typical norm of a, so the probability P(B(zz) is exponentially small in dimension. Our theory easily applies other choices of B, though we set this definition as default for simplicity. Now we define the neighborhood of x, denoted by (x), as the of points whose transformation sets overlap with that of 2:
N(x)= = {a' B(z) n B(x')= + 0}
(3.1)
For S. X, we define the neighborhood of S as the union of neighborhoods of its elements: N(S) e UzesN 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, ex-eannss.. We say that the class-conditional distribution P; satisfies (a, c)- expansion for all V C X with P.(V) I a, the following holds:
P((N(V)) 2 min(cP:(V).
(3.2)
If P; satisfies (a, -)-exaansion for all Vi E [K], then we say P satisfies (a, -)eexannsion.
We note that this definition considers the population distribution, and expansion 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 dis- tributions (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 &g distance at most r from the set, then the expansion factor c is bounded below by exp(nr), where 7) is the Cheeger constant (Zhang al., 2017). In Section 1. we use GANs to demonstrate that expansion is a realistic property in vision. For unsupervised learning, require expansion with 1/2 and >>> 1:
5

---

Published as a conference paper at ICLR 2021
Assumption 3.2 (Expansion requirement for unsupervised learning). We assume that P satisfies (1/2, (e..c)-xxppaiicc on X for c
We also assume that ground-truth classes are separated in input space. We define the population consistency loss Rs (G) as the fraction of examples where G is not robust to input transformations:
(g( & Ep[1(Bx' E B(x) such that G(z') + G(=))]
(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 - p by ground-truth classifier G as follows: Rg(G*) n.
Our accuracy guarantees in Theorems 4.3 and 3.6 will depend on p.. 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 & radius in the definition of B(.). However, r can be much smaller than the norm of typical example, 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 P; & N(T á aaxa) with isotropic covariance and K < d, corresponding to K separate classes." Suppose the transformation set B(x) is an Ez-ball with radius 1 around x, there is no data augmentation 2/a and 2/8 Then P satisfies (0.5, 1.5) -ep)-exxpnssoo. Furthermore, if the minimum distance between vlogd
means satisfies mins,j || Tyll2 ズ
tten P is B-separated with probability 1/poly(d). vd
In the example above, the population distribution satisfies expansion, but the empirical distribution does not. The minimum distance between any two empirical examples is 52(1) with high prob- ability, so they cannot be neighbors of each other when r 2V4 Furthermore, the intra-class distance, which is 22(1), is much larger than the distance between the means, which is assumed be 2 1/vd. Therefore, trivial distanced- based clustering algorithms on empirical samples do not apply. Our unsupervised learning algorithm in Section 3.2 can approximately recover the mix- ture components with polynomial samples, up to (1)) error. Furthermore, this is almost iformation-tteoretiioe optimal: by total variation distance, Qi (a) distance between the means is required recover the mixture components.
The example extends to log-concave distributions via more general isoperimetric inequali- ties (Bobkov al., 1999). Thus, our analysis applies the setting of prior work (Chen 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 near- Gaussian 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 P. over an am- bient space RRd where d' > is generated by some b-pi-Lipschitz' generator Qi Rd + Rd on latent variable 2 Rdd
1 j -axa)
x P. + = Qu(()) NNO.
We set the transformation set B(x) to be an bz-ball with radius augmentation and xx
zia around so there is no data 2ạā Then, P satisfies (0.5, -.5)-expanniion
Figure (right) provides a illustration of expansion on manifolds. Note that as long as < d/44 the radius x/(2vd) is much smaller than the norm of the data points (which is at least on the order of 1/K). 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 our examples.
1 'The classes are not disjoint, as is assumed by our theory for simplicity. However, they are approximately disjoint, and it is casy to modify our analysis to accomodate this. We provide details in Section C.2. A w-bi-L hischhizz function f satisfies that 1 ||æ vll S (f(z) f(v) S x||x vll-

---

Published as a conference paper at ICLR 2021
3.2 POPULATION GUARANTEES FOR UNSUPERVISED LEARNING
We design an unsupervised learning objective which leverages the expansion and separation prop- erties. Our objective is on the population distribution, but it 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 un- labeled data, such that predicted classes align with ground-truth classes. Note that without observ- ing any labels, we can only learn ground-trute classes up to permutation, leading to the following permutation- invaarinn error defined for a classifier G:
ErTunsup (G)
min permulation [[]]
([(((((())
We study the following unsupervised population objective over classifiers G & + [K], which encourages input consistency while ensuring that predicted classes have sufficient probability.
min RB(G) subject to min Ep[1(G(z) y)] max (--1.2] RB(G)
(3.4)
vE[K]
Here 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 p - minye[K] P((x: (x) = y}) denote the probability of the smallest ground-truth class. The following theorem shows that when 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 p > max max 23p. Then any minimizer G of (3.4) satisfies
ETT (G) < max cc (--1.231
(3.5)
In Section C, we provide the proof of Theorem 3.6 as well as a variant of the theorem which holds for weaker additive notion of expansion. By applying the generalization bounds of Section 3.3, can convert Theorem 3.6 into a finite-sample guarantees that are polynomial in margin and Lipschitzness of the model (see Theorem D.I).
Our objective is reminiscent of recent methods which achieve state-of-the-arr results in unsupervised representation learning: SimCLR (Chen al., 2020a), MoCov2 (He et al., 2020; Chen et al., 2020b), and B BYL (Grill et al., 2020). Unlike our algorithm, these methods do not predict discrete labels, but rather, directly predict 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, encourages representations to be similar over the entire class, so the representations will capture ground-truth class structure.
Chen et (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 larger expansion factor and improving the accuracy bound (3.5).
3.3 FINITE SAMPLE GUARANTEES FOR DEEP LEARNING MODELS
In this section, we show that if the ground-truth classes are separable by 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 sample complexity that is exponential in dimension (Seeger, 2000; Rigollet, 2007; Singh et al., 2009; Urner Ben- -evid, 2013).
We apply the generalization bound of (Wei & Ma. 2019b) based 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(z) arg max, F(x); is the prediction of some feedforward neural network F X -> IR K which computes the following function: F(x) = W, W, (W ...) with weight matrices [W;YP_1- Let g denote the maximum dimension of any hidden layer. Let m (F, y) 0 denote the all-layer margin example for

---

Published as a conference paper at ICLR 2021
label y, defined formally in Section D.2. For now, simply note that m has the property that if G(x) * y, then m(F, xz, v) = O, so we can upper bound the 0-1 loss by thresholding the all-layer margin: 1(G(x) * y) 1(m(F, y) 2 t) for any t > O. We can also define variant that measures robustness to input transformations: mB(F,z) _ minngeB(ar m (F, arg max; F(x))). 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- 8 over the draw of the training set P. all neural networks G arg max, Ft of the form F()) & W Wpp(... .. < (W1z)) will satisfy
E. Eilll
RB(G) S [B][(m((F())
+
(3.6)
for all choices of > O, where Ç - O ( / (log (1/)) + plogn//n) is low-order term, and Ō() 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. 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 proof overview Section D.3, we provide 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.
Section D.2, and in
4 DENOISING PSEUDOLABELS FOR SEMI-SUPERVISED LEARNING AND DOMAIN ADAPTATION
We study semi-supervised learning and unsupervised domain adaptation settings where we have ac- cess to unlabeled data and a pseudolabeler Gpt- This setting requires a more complicated analysis than the unsupervised learning setting because pseudolabels may be inaccurate, and student clas- sifier could amplify these mistakes. We design a population objective which measures input trans- formation consistency and pseudolabel accuracy. Assuming expansion and separation, show that the minimizer of this objective will have high accuracy on ground-truth labels.
We assume access to pseudolabeler Gp((),, obtained via training 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 (G, G*) & Ep (G(x) * G'(x))] to be the disagreement between G and G'. The error metric is the standard 0-1 loss on ground-truth labels: Er GG) - LG, G*). Let M(Gp)) - {x Gp(z) 4 G*())} denote the set of mistakenly pseudolabeled examples. We require the following assumption on expansion, which intuitively states that each subset of M(Gp)) has large enough neighborhood.
Assumption 4.1 (P expands on sets smaller than M(G,)). Define a A max, (P)(((())))) to be the maximum fraction of incorrectly pseudolabeled examples in any class. We assume that 1/3 and P satisfies (ā, -xxpxnsssinnnnnnooooaaaa.aooaoie for ē 3. We express our bounds in terms of c 4 min{1/a, e).
Note that the above requirement > 3 is more demanding than the condition > 1 required in the unsupervised learning setting (Assumption 3.2). The larger e > 3 accounts for the possibility that mistakes in the pscudolabels can adversely affect the learned classifier in a worst-case manner. This concern doesn't I apply to unsupervised learning because pscudolabels are not used. For the toy distributions in Examples 3.4 and 3.5, we increase the radius of the neighborhood by a factor of 3 to obtain (0.16, 6)-exannn, which is enough to satisfy the requirement in Assumption 4.1.
On the other hand, Assumption 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 1/2 required in Assumption 3.2. Furthermore, the
8

---

Published as a conference paper at ICLR 2021
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 looser requirement on the expansion factor e (see Section B.I). We design the following objective over classifiers G, which fits the classifier to the pseudolahels while regularizing input consistency:
min ((G) - c+1 La. (G, Gpl) + c- RB((C) - Em((pi)
2c
(4.1)
G
c-
The objective optimizes weighted combinations of Rg(G), the input consistency regularizer, and Lo-1 (G, Gp)), the loss for fitting pseudolabels, and is related recent successful algorithms for semi-supervised learning (Sohn et al., 2020; Xie et al., 2020). We can show that L(G) 2 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 : X + [K] is bounded in terms of consistency w.r.t input transformations and accuracy on pseudolabels; Er((G) S L(G).
When expansion and separation both hold, we show that minimizing (4.1) leads classifier that can denoise the pscudolabels and improve on their ground-truth accuracy.
Theorem 4.3. Suppose Assumptions 4.1 and 3.3 hold. Then any minimizer G of (4.1), we have
2
2c
Er S c- Err(Gp))
(4.2)
c
We provide a proof sketch in Section A, and the full proof in Section B. 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 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 Grr( This discrepancy 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. only requires expansion on sets with probability less than u. which can be much smaller than 1/2. Second, the error bounds in Section 3.2 only apply to classifiers with small values of (G) as seen in (3.4). On the other hand, Lemma 4.2 gives an error bound for all classifiers, regardless of RG) Indeed, strengthening the expansion requirement to that of Scction 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 1. we provide details for the GAN experiment in Figure 1. We also pro- vide empirical evidence for our theoretical intuition that self-training with input consistency regular- ization 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.
5 CONCLUSION
In this work, we propose an expansion assumption on the data which allows for a unified theoretical analysis of self- self-training for cemi-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-trainin and input consistency regularization can perform so well on unlabeled data. We hope that this assumption can facilitate future theoretical analyses and inspire theoreticalll-principl example, an interesting question for future work to extend our assumptions to analyze domain adaptation algorithms based on aligning the source and target (Hoffman et al., 2018).
algorithms for semi-supervised and unsupervised learning. For
ACKNOWLEDGEMENTT
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.

---

Published as a conference paper at ICLR 2021
REFERENCES
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. arXiv preprint /02.00560 2018.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv: /wtp:/902..00 09229, 2019.
Maria-Florins Balcan and Avrim Blum. A discriminative model for semi-supervised learning. Jour- nal of the ACM (JACM), 5763)1146, 2010.
Maria-FForina Balcan, Avrim Blum, and Ke Yang. Co-training and expansion: Towards bridging theory and practice. In Advances in neural information processing systems, pp. 89-96, 2005.
Shai Ben-David, Tyler Lu, and Dávid Pál. Does unlabeled data provably help? worst-case analysis of the sample complexity semi-supervised learning. 2008.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- man Vaughan. A theory of learning from different domains. Machine learning, 79(1-2):151-175, 2010.
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel. Mixmatch: A holistic approach to semi-supervised learning. In Advances in Neural Information Processing Systems, pp. 5049-5059 2019.
Avrim Blum and Tom Mitchell. Combining labeled and unlabeled data with co-training, In Pro- ceedings of the eleventh annual conference on Computational learning theory, pp. 92-100, 1998.
Sergey G Bobkov et al. An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality gauss space. The Annals of Probability, 25(1):206 214, 1997.
Sergey G Bobkov et al. Isoperimetric and analytic inequalities for log-concave probability measures. The Annals of Probability, 27(4) 1703-119911 1999.
Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale gan training for high fidelity natural image synthesis. arXiv preprint arXiv: 1096, 2018.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, John C Duchii, and Percy S Liang. Unlabeled data improves adversarial robustness. In Advances in Neural Information Processing Systems, pp- 11192 1203, 2019.
Olivier Chapelle, Bernhard Schlkopf. and Alexander Zien. Semi-Supervised Learning. The MIT Press, 1st edition, 2010. ISBN 0262514125.
Jeff Cheeger. lower bound for the smallest eigenvalue of the laplacian. Proceedings of the Princeton conference in honor of Professor S. Bochner, pp. 195-199, 1969.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. arXiv preprint arXiv:2002.05700 0500009 2020a.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003.04297 2020b.
Yining Chen, Colin Wei, Ananya Kumar, and Tengyu Ma. Self-training avoids using spurious features under domain shift. arXiv preprint arXiv:2006. 10032, 2020c.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92. American Mathematical Soc., 1997.
Sanjoy Dasgupta, Michael Littman, and David A McAllester. Pac generalization bounds for co- training. In Advances in neural information processing systems, pp. 375-382, 2002.
Philip Derbeko, Ran El- El-Yaniy, and Ron Meir. Error bounds for transductive learning via compres- sion and clustering. Advances in Neural Information Processing Systems, pp. 1085-1092, 2004.
10

---

Published as a conference paper at ICLR 2021
Carl Doersch, Abhinav Gupta, and Alexei A Efros. Unsupervised visual representation learning by context prediction. Proceedings of the IEEE international conference on computer vision, pp- 1422-1430, 2015.
Logan Engstrom, Andrew Ilyas, Hadi Salman, Shibani Santurkar, and Dimitris Tsipras. Robustness (python library), 2019. URL https: / /tttttb.tthgggoggggoog. com/Madryyala http://ddrrlalbbbbousstssesss robustness.
Geoffrey French, Michal Mackiewicz, and Mark Fisher. Self-ensembling for visual domain adapta- tion. arXiv preprint arXiv:/706.052088 2017.
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In International conference on machine learning, pp. 1180-1189. PMLR, 2015.
Yaroslav Ganin, Eygeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarial training of neural net- works. The Journal of Machine Learning Research, 170))2096-2030, 2016.
Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. arXiv preprint / 2018.
Amir Globerson, Roi Livni, and Shai Shalev-Shwartz. Effective semisupervised learning mani- folds. In Conference on Learning Theory, pp. 978-1003, 2017.
Yves Grandvalet and Yoshua Bengio. Semi-supervised learning by entropy minimization. In Ad- vances neural information processing systems, pp. 529-536, 2005.
-aan-Battien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent: A new approach to self-supervised learning. arXiv preprint arXiv:2006.07733 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.
2020.
Geoffrey E Hinton, Terrence Joseph Sejnowski, Tomaso A Poggio, al. Unsupervised learning: foundations of neural computation. MIT press, 1999.
Judy Hoffman, Eric Tzeng, Taesung Park, Jun- Yan Zhu, Phillip Isola, Kate Saenko, Alexei Efros, and Trevor Darrell. Cycada: Cycle-consistent adversarial domain adaptation. In International conference on machine learning, pp. 1989-1998. PMLR, 2018.
Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 4344)4439-561, 2006.
Weihua Hu, Takeru Miyato, Seiya Tokui, Eiichi Matsumoto, and Masashi Sugiyama. Learning discrete representations via information maximizing self-augmented training. arXiv preprint 1rXiv:1702.08820, 2017.
Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, and Ondrej Chum. Label propagation for deep semi- supervised learning. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 5070-5079, 2019.
Ravi Kannan, László Lovász, and Miklós Simonovits. Isoperimetric problems for convex bodies and a localization lemma. Discrete & Computational Geometry, 13(3-4):541-55)) 1995.
Durk P Kingma, Shakir Mohamed, Danilo Jimenez Rezende, and Max Welling. Semi-supervise learning with deep generative models. In Advances in neural information processing systems, pp. 3581-3589, 2014.
11

---

Published as a conference paper at ICLR 2021
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv:1609.02900 2016.
Ananya Kumar, Tengyu Ma, and Percy Liang. Understanding self-training for gradual domain adaptation. arXiv preprint arXiv:2002. 1361, 2020.
Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised leamiig. arXiv preprint arXiv:1610.02242, 2016.
Dong-Hyun Lee. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. 2013.
Jason Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps:
Provable self-supervise learning. arXiv preprint arXiv:2008 0/064, 2020.
Mingsheng Long, Jianmin Wang. Guiguang Ding, Jiaguang Sun, and Philip S Yu. Transfer feature learning with joint distribution adaptation. In Proceedings of the IEEE international conference on computer vision, pp. 2200-2207, 2013.
László Lovász and Santosh Vempala. The geometry of logconcave functions and sampling algo- rithms. Random Structures Algorithms, 30(3):307-358, 2007.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations words and phrases and their compositionality. In Advances in neural information pro- cessing systems, pp. 311 111111111 19, 2013.
Ishan Misra and I Laurens van der Maaten. Self-supervised learning of pretext-invariant representa- tions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6707-6717, 2020.
Takeru Miyato, Shin-ichi Maeda, Masanori Koyama, and Shin Ishii. Virtual adversarial training: regularization method for supervised and cupi-vupee learning. JEEE transactions on pattern analysis and machine intelligence, 41(8):1979-199 1993, 2018.
Hossein Mobahi, Mehrdad Farajtabar, and Peter L Bartlett. Self-distillation amplifies regularization in hilbert space. arXiv preprint (xXi::2002.05755. 2020.
Bojan Mohar and Svatopluk Poljak. Eigenvalues in combinatorial optimization. In Combinatorial and graph-theoretica problems linear algebra, pp. 107-151. Springer, 1993.
Vaishnavh Nagarajan and Zico Kolter. Deterministic pac-bayesian generalization bounds for deep networks via generalizing noise- resilieese arXiv preprint arXiv:/905.133444 2019.
Mehdi Noroozi and Paolo Favaro. Unsupervised learning of visual representations by solving jigsaw puzzles. In European Conference on Computer Vision, pp. 69-84. Springer, 2016.
Aaron den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint arXiv: 2018
Samet Oymak and Talha Cihad Gulcu. Statistical and algorithmic insights for semi-supervised learning with self-training ArXiv, abs/2006. 1006, 2020.
Deepak Pathak, Philipp Krahenbuhl, Jeff Donahue, Trevor Darrell, and Alexei A Efros. Context encoders: Feature learning by inpainting- In Proceedings of the IEEE conference computer vision and pallern recognition, pp. 2536-2544, 2016.
Siyuan Qiao, Wei Shen, Zhishuai Zhang, Bo Wang, and Alan Yuille. Deep co-training for semi- supervised image recognition. Proceedings of the european conference on computer vision (eccv), pp. 135-152, 2018.
Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In Proceedings of the forty- ACM symposium Theory of computing, pp. 755-764, 2010.
12

---

Published as a conference paper at ICLR 2021
Aditi Raghunathan, Sang Michael Xie, Fanny Yang. John Duchi, and Percy Liang. Understanding and mitigating the tradeoff between robustness and accuracy. arXiv preprint arXiv:2002.10716, 2020.
Philippe Rigollet. Generalization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Learning Research, 8(Jul) 2007.
Kuniaki Saito, Yoshitaka Ushiku, and Tatsuya Harada. Asymmetric tri-training for unsupervised domain adaptation. arXiv preprint arXiv:1702.08440 2017.
Matthias Seeger. Learning with labeled and unlabeled data. Technical report, 2000.
Rui Shu, Hung H Bui, Hirokazu Narui, and Stefano Ermon. A dirt-t approach to unsupervised
domain adaptation. arXiv preprint arXiv:1802.08735. 2018.
Aarti Singh, Robert Nowak, and Jerry Zhu. Unlabeled data: Now it helps, now it doesn't. In Advances in neural information processing systems, pp. 1513-1520, 2009.
Kihyuk Sohn, David Berthelot, Chun-Liang Li, Zizhao Zhang, Nicholas Carlini, Ekin Cubuk, Alex Kurakin, Han Zhang, and Colin Raffel. Fixmatch: Simplifying semi-supervised learning with consistency and confidence. arXiv preprint arXiv:2001.07655 2020.
Antti Tarvainen and Harri Valpola. Mean teachers are better role models: Weight- consis- tency targets improve semi-supervised deep learning results. In Advances in neural information processing systems, pp. 1195-1204 2017.
Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. What makes for good views for contrastive learning. arXiv preprint arXiv:2005. 2020.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive estimation reveals topic posterior information to linear models. arXiv preprint arXiv:2003.0223: 2020.
Yao-Hung Hubert Tsai, Yue Wu, Ruslan Salakhutdinov, and Louis-Philippe Morency. De- mystifying sule-super learning: An information-theorrtioo framework. arXiv preprint arXiv:2006.0557,, 2020.
Eric Tzeng, Judy Hoffman, Ning Zhang, Kate Saenko, and Trevor Darrell. Deep domain confusion: Maximizing for domain invariance. arXiv preprint
2014.
Eric Tzeng, Judy Hoffman, Kate Saenko, and Trevor Darrell. Adversarial discriminative domain adaptation. In Proceedings of the IEEE conference computer vision and paltern recognition, pp. 7167-7176, 2017.
Ruth Urner and Shai Ben-David, Probabilistic lipschitzness: A niceness assumption for determinis- tic labels. 2013.
Vladimir Vapnik. The nature of statistical learning theory. Springer science business media, 1995.
Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. In Advances in Neural Information Processing Systems, pp. 9725-9736, 2019a.
Colin Wei and Tengyu Ma. Improved sample complexities for deep networks and robust classifica- tion via an all-layer margin. arXiv preprint arXiv: (11i::/91000284,, 2019b.
Qizhe Xie, Zihang Dai, Eduard Hovy, Minh-Thang Luong, and Quoe V Le. Unsupervised data augmentation for consisteney training. arXiv preprint arXiv: /2848, 2019.
Qizhe Xie, Minh-Thang Luong, Eduard Hovy, and Quoc V Le. Self-training with noisy student improves imagenet classification. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 10687-10698, 2020.
I Zeki Yalniz, Hervé Jégou, Kan Chen, Manohar Paluri, and Dhruv Mahajan. Billion-scal. semi-
supervised learning for image classification. arXiv preprint arXiv: 1900.00550000 2019.
13

---

Published as a conference paper at ICLR 2021
David Yarowsky. Unsupervised word sense disambiguation rivaling supervised methods. In 33rd annual meeting of the association for computational linguistics, pp. 189-196, 1995.
Yuchen Zhang, Percy Liang, and Moses Charikar. A hitting time analysis of stochastic gradient langevin dynamics. In Conference on Learning Theory, pp. 1980-2022, 2017.
Yuchen Zhang. Tianle Liu, Mingsheng Long, and Michael I Jordan. Bridging theory and algorithm for domain adaptation. arXiv preprint 1904:09004.58800 2019.
Yang Zou, Zhiding Yu, Xiaofeng Liu, BVK Kumar, and Jinsong Wang. Confidence regularized self-training. In Proceedings of the IEEE International Conference on Computer Vision, pp- 5982-5991, 2019.
14

---

Published as a conference paper at ICLR 2021
A PROOF SKETCH FOR THEOREM 4.3
We provide a proof sketch for Lemma 4.2 for the extreme case where the input consistency regular- izer is 0 for all examples, i.e. G(x) G(z') Va X, e B(x), so Rg(G) 0. For this proof sketch, we also make an additional restriction to the case when La- Gpt) = Br((GG).
We first introduce some general notation. For sets U, V S X, we use U \ V to denote {x : x U x & V.. and n, U denote set intersection and union, respectively. Let U _ X denote the complement of U.
Let C, - fx (*) = i} denote the set of examples with ground-trute label i. For S S X, we define (S) to be the neighborhood of S with neighbors restricted to the same class: ( e UsE[K] (WSSnc) nc,). The following key claims will consider two sets: the set of correctly pseudolabeled examples on which the classifier makes mistakes, {i G(z) * Gpi(z) and & M(Gr)), and the set of examples where both classifier and pseudolabeler disagree with the ground truth, (FF) (M,))... The claims below use the expansion property to show that
P((x G(x) + Gp(z) and & M())))) > P(M(F) N (.G()))
Claim A.1. In the setting of Theorem 4.3, define the set V & M(C) Define q A Br((.a) By expansion (Assumption 4. if P(V) > q, then P(N* \ (MG))) P(V).
c-1
A more general version of Claim A.1 is given by Lemma B.7 in Section B.2. For visualization of V and N (V) \ (())), refer to Figure 2.
Claim A.2. Suppose the input consistency regularizer is for all examples, i.e, Va E X, a' E B(x), it holds that G(x) G(x'). Then follows that
{x : G(z) + Gp((a) and & M(G 2 (V M(G))
Figure outlines the proof of this claim. Claim B.5 in Section provides a more general version of Claim A.2 in the case where (G( 0. Given the above, the proof of Lemma 4.2 follows by 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:
La-1 (G, Gpi) [[1()(x) + (z)( and & MM(G))))] ([(()(x) E()((()) + Gp((z) and x M(GP)))]
We lower bound the first term by P(V) by Claims A.1 and A.2. For the latter term, we note that x E M(G V. then G(x)= = (z) + Gz(Z)) Thus, the latter term has lower bound P(M(Gp)) - P(V). As result, we obtain
Lo- (G)) > P(V) + P(M - P(V) = Err(Gp)
which contradicts our simplifying assumption that La-1 Gpt) = Er Thus, G disagrees with G most y fraction of examples in M(G,)). To complete the proof, note that G also disagrees with G on at most y fraction of examples outside of ((G)), or else La.1 (G, Gpt) would again be high.
B PROOFS FOR DENOISING PSEUDOLABELS
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.
B. RELAXATION OF EXPANSION ASSUMPTION FOR PSRUDOLABELING
In this section, we provide a proof of a relaxed version of Theorem 4.3. We will then reduce Theo- rem 4.3 to this relaxed version in Section B.2. It will be helpful to restrict the notion of neighborhood
15

---

Published as a conference paper at ICLR 2021
ATOON MIG)
B(x)
(
G(rr) m G(x)
G(z)) = Gix)
800)
Yr' E(())
MCCRY
( G(2)
6iz) (x) =x)=='()
Figure 2: To prove Claim A.2, we first note that in the simplified setting, if ((x) n B(z) + 0 then G(x) G(z) by the assumption that Rg(G)- 0 (see left). By the definition of A this implies that all points E (VVVV) MM(Gp) must satisfy G(z) * (z),, as matches the label of its neighbor in V M(G). However, all points in X' MM(Gp)) must satisfy Gp((x) G (x), and therefore (xx) o (z)).. These sets are depicted on the right.
to only examples in the same ground-truth class: define (x) - { of E (x() and G*''') = (*)) and (*) & UzesN*(z)) Note that the following relation between (N(S and (*))) holds in general:
(S = Usen ((Snc))ne)
We will define the additive notion of expansion on subsets of X' below.
Definition B.1 ((g, a) addiiive-eexpaasoo
set S). We say that P satisfies (g, addditiee expansion on S S X if for all V S S with P(V) > q. the following holds:
P(N* (V) ( 5)
Σ RE[K]
P(W(VGG)GG))
P(V)+a
In other words, any sufficiently large subset of must have a sufficiently large neighborhood of examples sharing the same ground-truth label. For the remainder of this section, will analyze this additive notion of expansion. In Section B.2, we will reduce multiplicative expansion (Defini- tion 3.1)
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--rransformaiion::
Sg(G) = G(z) = G(z²) Va' e B(x)}
The following theorem shows that if the classifier 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 + {l...., K}, suppose that P has (g, a)- additive-expansion on M(G ) for some q, a. Suppose that G fits the pseudolabels with sufficient accuracy and robustness:
(p()(((()) * Gp(()) or & Ss(G))) S Err(Gp) +
(B.1)
Then G satisfies the following error bound:
Err(G) < 2(g + RB(G)) + Ep[1(G(x) + Gp(z))] Err(Gp)
To interpret this statement, suppose G fits the pseudolabels with error rate at most Err(G,) and (B.1) holds. Then ET((G < 2(g + Rg(G)), so if G is robust to B-perturbations on the population distribution, the accuracy of high.
Towards proving Theorem B.2, we consider three disjoint subsets of n
Mi - {a: G(x) Gp((), Gp(x) Gp(x).G((z) + (*(z), and x E Sg(G))
M2 2 {a G(z) Gp(z), Gp(z) + G (z), G(x) G* and Ss(G))
Mg ف {o: G(x) + Gp(z), Gp( G
G* (z), and x E Sz(G)}
We first bound the probability of Mi M2.
16

---

Published as a conference paper at ICLR 2021
Lemma B.3. In the setting of Theorem B.2, we have P(Sg(G) n M() n M(G)) I 9. As
result, since it holds that M1 U M2 - SB(G) M(Gp) n M(G), it immediately follows that P(M1 MM) S q.
The proof relies on the following claims.
Claim B.4. In the setting of Theorem 4.3, define U & ((G))) n.G \ M For any x E U (G) holds that Gp((a) # G(z) and G(r) # (z))
Proof. For any I E EU S ("(Ss(G) n M(G)), there exists x' E ((GG))
M(G) such that B(x) n B(x') + 0 and (z = G by definition of (-).). Choose 2 E
B(x) n B(x'). As x, Sg(G). by definition of Sg(G) we also must have ((x) = G(22)
G(r'). Furthermore, as x' E M(G), G(a") * G*(r'). Since (* = G (x'). it follows that
G(x) * (z)..
As U M(G)) 0 by definition of U. Gpt much match the ground-truie truth classifier on U, so Gp(()) = (r). follows that G(x) + Gp((z), as desired.
Claim B.5. In the setting of Theorem B.2, define U A N*(SE(GG nMG() MM
If PG) ( M(G)) > q, then
P(U SBUNS)(G)) P(M(G))) + P(SB(G)) + 1- P(SE(G) n M(G))
Proof. Define V _ (G) n M(G)) n MGG). By the assumption that M(Gp) satifies (q, a additive-expansion, if P(V) holds, it follows that P(U) > P(V) + Furthermore, we have U \ SB(G) C S5(G) M(Ga by definition of U and V as U M(pp) 0, and so P(U (B(()) 1 P
Thus, we obtain
P(U n Sg( P(U) P(U SB(G))
P(V) + a - 1 P(Se(C)
Now we use the principle of inclusion-exclusion to compute
P(S U M(G P(M(G)))++( P(SE(G)).M(G.))
Plugging into the previous, we obtain
P(U SB(G)) P(M(G))) + P(SB(G)) + a 1+ 1--)())) P(Se()))MG))
1 1- (ll-((((())MMGG))) A M(G)) P(M(G,I) + P(Ss(G)) + a-
where we obtained the last line because V = Sa(G) ((G n (M) S SB(G) M(Gp))
Proof of Lemma B.3. To complete the proof of Lemma B.3, we first compose SB(C) into three disjoint sets:
S A (x: G(x) = S(((C)
S2 a (z G(x) + ((G))) SB((G)
S₃ - (x G(x) + Gp(r)) ((G))) (G)
First, by Claim B.4 and definition of U, we have Va E UnS G(z) + Gp(z)) and & M(Gp). Thus, it follows that U n SB(G) C Sz.
Next, we claim that V M(G n (GG) n SE(G) C Sz. To this, note that for e V", G(x) = (z) and Gp((z) 4 (*)).. Thus, G(z) + Gp(()), and E Sg(G) n M(G,), which implies S2.
Assume for the sake of contradiction that ((S n M( n M(G)) > Now we have
PG)) Z P(S.) +
2 P(S)) + P(Sg(()) (.SS(G)).MMGG)) M(G)) + P(U SB()))
P(S,) P(M((),)) P(S --1
(by Claim B.5)
17

---

Published as a conference paper at ICLR 2021
However, also have
P(Si) = Ep(1(((x)) + Gp(z) or & Ss(G))]
Br((Gp))
(by the condition in (B.1))
Plugging this in gives us P(S)) + + > P(S)(G)), a contradiction. Thus, P(S8( G) M(G (MGG)) S q, as desired.
The next lemma bounds P(Ms)- Lemma B.6. In the setting of Theorem B.2, the following bound holds:
P(Ma) S g + Rg(G) Ep[1(G(<)) + Gp(())) Err(Gp)
Proof. The proof will follow from basic manipulation. First, note that
Ma u fo: G(x) = Gp(()) and x E Ss()))
(B.2)
=(x G(z) # (p(z) = (z)) U (x G(z)
(z))
(x: G(z) (pl) (z)))) Ss((G)
UM Gp((z) = (x) and x E Ss(G)}
(B.3)
As (B.2) and (B.3) pertain to unions of disjoint sets, it follows that
P(Ms) P((x G(x)
(x(z) and æ E P(M;) + P({x Gp(() = = and x E SB())))
Thus, rearranging we obtain
P(Ma) = CMM
< P(Mi) + Gpp)
P( : G(x) (
< P(M1) + P({x: = Gx)))) P(zx G(z) Gp(z)))
+ +P((# G(x) = G)(())))
S P(Mi) P((x: # P(M))) + P(Ss(G))
= -P(Mi) +
+ (p)((((()) # Gn(x))) - Brr(Gp)
Substituting P(M1) S q from Lemma B.3 gives the desired result.
Proof of Theorem B.2. To complete the proof, compute
En((G) P(M(G)) < P(M(G) P(SB(G))
= P(Mi) + P(M2) P(Ma) + Rs(G)
< 2( + Rs(G)) + Ep(1(G(x)) # Gn())) Err(Gp)
(by Lemmas B.3 and B.6)
B.2
PROOF OF THEOREM 4.3
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 (g. aa)-aaddiiive-eppasiin which is done in the following lemma. Let Mc & (C, 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), Pt has (g, or) -aaaaiiiveeepaaniii on MD(Gpa) for the following choice of q, ac
(Pa))(Ga))
g = c-1 a = (8 - ())M))
(B.4)
18

---

Published as a conference paper at ICLR 2021
Proof. Consider any Mi(Gp)) with P:(S) >
(M,((M Then by Assumption 4.1, c-1
P((N(S)) 2 min(cP,(S)..1 1} 2 cPi(S), where we used the fact that P.(S) I P.(Mi(Gpi) and Cs (.(M)(()))) so (P((S) I 1. Thus, we can obtain
(((((S) \Mi(Gp)) 2 cP((5) - P.(M.(Gp))
P:(S) ()-()) P.(M(()))))))
> P((S) + (3 - ())(()))))))
Here the last line used the fact that P.(S) > (P.),.(Ga)) This implies that P. has (4, -daddiiveee- expansion on (Gp) for the a) 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 Lo- Gpi) Er((G)) and Rg(G*) S p by Assump- tion 3.3.
We first define the class-conditional pseudolabeling and robustness losses: [ & P:((::
G(x) * (z)z))), and R (G) - Ep, Ep,11(Er' E B(x)) such that G(x²) * G(z))). We also define the class-conditional error as follows: (Gr & ( (G, G*). We prove the class-conditional variant of Lemma 4.2 below.
Lemma B.8. For any i [K]. define
L((G) &
(0 c c 1 Gpt) (Gpp))) e
2c R (G)
(B.5)
Then in the setting of Theorem 4.3 where Assumption 4. holds, we have the following error bound for class
(m, S L((G)
(B.6)
Proof. First, we consider the case where T, [ (G, Gp)) + R(O (G) S (c - GGpr)(Gpp). In this case, can apply Lemma B.7 with 3 (0, chosen such that
(3 (Gp)) = (G,
R (Gp)
(B.7)
We note that P. has addd)))-ddieeeeexpaaaa on M; for
Err, (Gn)
(B.8)
--
(B 1)Em (Gp1)
(B.9)
Now by (B.7), we can apply Theorem B.2 with this choice of (g, a) obtain R()
(G) s 2(q + R (G)) + [ (G, Gpi) (Gpp)
(B.10)
2
Em, (Gp)) 2 8 (G) 1 (G, Gpt)
Err, Err,(Gg) (Gp))
(B.11)
c
C
1
L
(1)
(G, Gpt) Em, (Gp)
2c
((0) (G)
(plugging in the value of (3
c c-1
c
GG)
(B.
Next, we consider the case where (1) (G) Gp)) + (1) (G) > (c- (Gpt). Note that by triangle inequality, we have
(10 Eir, (G) (G, G*
(g)
G*)
(B.13)
(1) (G, + 2 (Gp)) (G,)
(B.14)
2 (6)
- (G, (G, + c-1 11
Gp)
Gpl) + R (G)) - (rr
(B.15)
< c+1 (G, Gp)) + R p (G)) - EErr (Gp)
(B.16)
< c+1
(i) (G, Gp)) + c-1
2c
R (G) - Err,(Gp))
(using e >>>> 1)
C.(
(B.17)
19

---

Published as a conference paper at ICLR 2021
Lemma 4.2 now follows simply by taking the expectation of the bound in (B.6) over all the classes.
C PROOFS FOR UNSUPERVISED LEARNING
We will first prove an analogue of Lemma C.7 for 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 ((g. J-coostaat-expaasionn) We say that distribution P satisfies (g. -constann- expansion if for all S S X' satisfying P(S) 2 9 and P(SnC,) S P(C.)/2 for all the following holds:
(S) 8) min(f,P(SS)
As before, (S) is defined by Use K (WSS n C,) C.). 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 each class will align with the true classes.
Theorem C.2. Suppose P satisfies (g, Coonstannt-expannion for some If holds that Rg(G) < E and
min P(fx: G(x) = =}) > >2 max Rg(G)}
there exists permutation [K] > [K] satisfying the following:
P((z : (G((=) * G (z))) s max(g, RB(G)) + RB(G)
(C.1)
Cx Lemma C.3. In the setting of Theorem C.2, consider any set of the form U & Se(()nee
Define C,,...,Cx to be the partition induced by G: C, a fx: : G(z) i}.
where I are arbitrary subsets of [K) Then N (U) \ U S (G))
Proof. Consider any x E EU*(U)) U. There are two cases. First, if G(x) E J. then by definition of (=*((,), x E OverC, Ojeg C, However, x & U, which must imply that x & Sg(G). Second, G(x)) J, by definition of (-) there exists x' E U such that B(x) B(x') ) # D. It follows that for z E B(x) n B(x'), G(z) = G(x') E J. Thus, since G(x) & J. (()) * G(2) so x & (B(
Thus, it follows that (* U S SB(G).
Next, we show that every cluster found by G will take up the majority of labels of some ground-truth class.
Lemma C.4. In the setting of Theorem C.2, j. Ei such that P(SB(G)
((Sx()))C.)
2
Proof. Assume for the sake of contradiction that there exists such that for all P(S P(Sa(G)nC.)) Define the set U, - Sy (G) n C. n Ej and U - U,U, = SB(G) n Cj. Note that KK form partition of U because {C, ] are themselves disjoint from one another. Furthermore, we can apply Lemma C.3 with I = [K] to obtain (U) U C SB(G).
C,) <
2
Now observe that P(U) > P(CC) P(Sa(G) Using the theorem condition that P(C,) GG)), follows that
P(C,) 2
P(U)
max P(Sp(G)
Furthermore for all we note that
P(C: (U)) 2 2 P(Sa(G)nCC) P(U.)
P(U.)
(C.2)
Thus, P(C.) 2 2P(U.). Thus, by (q. (g.E) (g..))-costaattexpaasii we have
P(N*(U) \ U) Z min(s, min P(C))/2)
As \ \U C Sg(G), this implies Rg(G) = P(S min(g, P(C))/) a contradiction.
20

---

Published as a conference paper at ICLR 2021
Lemma C.5. In the setting of Theorem C.2 and Lemma C.4, V there exists unique x(j) such that P(S ((S)(G))Cm()) and (C,,n)) < P for i + T()..
Furthermore, x is a permutaation from [ to []]
Proof. By the conclusion of Lemma C.4, the only way the existence of such x might not hold is if there is some where (G) n n nC,) P(Sa(G)nCc for E (2, where i1 * i2. In this case, by the Pigeonhole Principle, as the conclusion Lemma C.4 applies for all j E [K] and there are K possible choices for i, there must exist i where n nC,) ((Sg()) for j E (21. where j1 + j2. Then ((Sa(G) nč, P(S > P(S)) which is contradiction.
Finally, to see that и is a permutation, note that m(1) = x(j2) for ji # j2. this would result in the same contradiction above.
Proof of Theorem C.2. We will prove (C.1) using и defined in Lemma C.5. Define the set Uy & (B) n Cxa) Okys G.. Note that Uj = for G(x) * (x) = x()) n SE(G). Define U U,U and note that {U;} forms partition of U. Furthermore, we also have U = fa (G(()) & (z)) SS()G). We first show that P(U) S max(q, Rs(G)). Assume for the sake of contradiction that this does not hold.
2 (U))U. To see this, consider any E C U. By definition, 3x' E U such that B(x') B(x)) * 0 and (*(x) = G*' or x' Czty- Thus, it follows that x E (Cri)) n nU) UU AU= -U,(U, U = (V,(,)) Uy. where the last equality followed from the fact that (U,) and UR are disjoint for j * k. Now we apply Lemma C.3 to each (U3) Uj to conclude that (U) AU C SB(G).
First, we claim that
Finally, we observe that
P(U,) ((S nC P(S nē)) P(SB(G))CC(o))
P(C+G)) (C.3)
by the definition of in Lemma C.5. Now again apply the (q. cxsstattcoontttnnnnsiiionn property, as we assumed P(U)= > obtaining
P(V"()X min(s.
However, as we showed (U) C (B) we also have (G) = P(SB(G)) 2 PU) U) > min(E, P(U)). This contradicts P(U) max(q, Rg(G)) and Rs(G) &, and therefore P(U) < max(q, (.)
Finally, we note that {x ( SB()). Thus, we finally obtain
P(U) + + ((S+(G) S max(g, Rs(G)} + Rg(G)
C.1 PROOF OF THEOREM 3.6
In this section, we prove Theorem 3.6 by converting multiplicative expansion to (q, E) conntaant- expansion and invoking Theorem C.2. The following lemma performs this conversion.
Lemma C.6. Suppose P satisfies (1/2, c) ceapppliccatie-eepasiiiii (Definition 3.1) on X. Then for any choice of & > 0, P satisfies (E=: -constant expansion.
21

---

Published as a conference paper at ICLR 2021
Proof. Consider any S such that P(S & P(C,)/2 for all i E [K] and P(S) q. Define S _ SSc First, in the where 2 have by multiplicative expansion
(S) \ \S 2 Σ (S.) - P(S.)
2 Σ min(cP(s.), P(C,)) - P(S.)
Σ P(S.)
(because c and P(S.) - P(C.)/2)
Thus, we immediately obtain constant expansion.
Now we consider the case where - << < 2. By multiplicative expansion, we must have
((NM(S) 2 Σ (in(c P(S.)
2 E (c- P))))
(because c < < and P(S.) S P(C.)/2)
2 (c 1)9 =
The following lemma states accuracy guarantee for the setting with multiplicative expansion.
Lemma C.7. Suppose Assumption 3.2 holds for some 1. If classifier G satisfies
min Ep|1(G(()) = i)) > max { 2 __1,2 RB(
cc-1²
then the unsupervised error is small:
c cc-1'2 { RB)
EIT unsuu (G) S max
(C.4)
now prove Lemma C.7, which turn immediately gives proof of Theorem 3.6.
Proof of Lemma C.7. By Lemma C.6, must satisfy
[aiG)] RB(G) consstat--xppansion As we c-1
also have min; P((x G(x) i}) > max 2 c-T 2 RE(G), we can now apply Theorem C.2 to
conclude that there exists permutation ग [K] + [K] such that
P((x: # G* (z))) & max { c
c- (c-1:2/ Rs(()
as desired.
C.2 JUSTIRICATION FOR EXAMPLES 3.4 AND 3.5
To avoid the disjointness issue of Example 3.4, we can redefine the ground-truth class G (+(r) to be the most likely label x. This also induces truncated class-conditional distributions Pi, Pp where the overlap is removed. We can apply our theoretical analysis to Pr. Pa and then translate the result back P2. only changing the bounds by 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 P.(S) p where (1,2), the choice of S minimizing
(S))(S)) is given by a halfspace: 5 H(p) A (a w T(x 7.) S $ (<1() for vector with ||l||| Vd. It then follows that setting r v (HH(p)) 2 {z + | : H(p) <
r} 2 {a T TT T.) < Φ (p) + rvdd,, and thus ((N(H( 2 2 (( (p) +vd).. As
P(N(H))))P(HH() is decreasing in for p < 0.5, claim about expansion follows. To
22

---

Published as a conference paper at ICLR 2021
-لااا r/2 Vj), where 13-7; ||5-- We note that these sets are 3-separated from each other, and furthermore, for the lower bound on T, Tyll in the example, note that X; has probability 1 μ under P..
claim about separation, consider the sets X; _ {ar (x-+; Uij S
Vij
For Example 3.5, we note that for ((x) - {x' ||=s x|| r), M(S) M( Ex (S) such that ||x' - =il s r/ Thus, our claim about expansion reduces to the Gaussian case.
D ALL-LAYER MARGIN GENERALIZATION BOUNDS
D.1 END-TO-END GUARANTEES
In this section, we provide end-to-end guarantees for unsupervised learning, semi-supervised learn- ing, and unsupervised domain adaptation for finite training sets. For the following two theorems, we take the notation (.) 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.I. In the setting of Theorem 3.6 and Section 3.3, suppose that Assumption 3.2 holds. Suppose that G arg max; F3 is parametrized a neural nelwork of the form F(x) - Wpp(.-- (W)()) (W(z))...) With probability
over the draw of the training sample P. if for any y=1 with uy > Vy, it holds that
choice of > 0 and {uy]
(f[1m((F,..)) 2 uy)l max { 2 (p(((m)(FFx)) s)
cc-1:2
(Liv unyn ( + for all y E [K]
then it follows that the population unsupervised error is small:
EivalWalle + W/
EtT (G) S maxx
{c- 2 Enls (0)
log(K/5)+ppoo pog c-
where
is a low-order term.
a
The following theorem provides the finite-samlle 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 max; F, is parametrized a neural network of the form F(x) 2 Wpp(-- - ( ..). For any t1,t2 1, > O, define the following quantities:
Bi A (M S 41) + Ep[1 (mm x, Gp(()) S 12)
+ Valllwllla
(i + levn) )) +c
1
B₂ (Ep(1(ms(FFa)) s (1) + 3.p[1(m(FFF))) Gp((z)) s t2)
+ vallall))
(1i + +
1
where < o (2 Ing K K/A))tllogn
is low-order term. With probability 1 - 8 over the draw of
the training sample P. for all choices tf to 0, it holds that
Emr(G) S max { B Err(G)), Bg - (3 --
Em(Gp)
c-1
23

---

Published as a conference paper at ICLR 2021
D.2 PROOFS FOR SECTION 3.3
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 some minor differences 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 8 over the draw of the training sample P, all neural networks G = arg max; Fs of the form F(x) & Wpp(.... ((W(=)) will satisfy
(2 (2ivellWlll +
(
Lo. Gpt) S E5p11m((E)))) Gp(()) - -0]+==s++++ +Ō
W/
for all choices of t > O, where Ç _ o poly-logarithmic factors in n and d.
(0000//1/0)tploo is a low-order term, and Ō(-) hides
Theorem D.4. With probability 8 over the draw of the training sample P, all neural networks G= = arg max; F; of the form F(x) & wpe(... <W,zz) will satisfy
[p()(G(x) = ->)l Ep[1(m((,F)) x. 2 D) - (~ w/n
E, vallaale)
for all choices of E [K] 1 O, where Ç a O hides poly-logarithmic factors in and d.
logi K (8) log
a low-order term, and (-))
n
We now overview the proof of Theorem 3.7, as the proof's of Theorem D.3 and D.4 follow identically. We first formally define the all-layer margin m(F,2, 2.,) y) for neural net I' evaluated on example with label y. We recall that F computes the function F(x) A Wpdh(... (W ...). We index the layers of as follows: define f1(x) - Wix, and fa(h) & W2 for 2 < i S p, so that F(x) = fp .... fz()). Letting 8 (81....,6p) 6p) denote perturbations for each layer of F,
define the perturbed output F(x, 8) as follows:
(, 8) f(()) 5n ||=|||
14(2, 8) = fi(h-- d)) + 6: 2///;;- 1 8)112
F(x, 6) (2,
Now the all-layer margin m(F, v) is defined by
min Σ | l1
m F, x2
subject to arg max F(x, +y
As is typical in generalization bound proofs, we define a fixed class of neural net functions to ana- lyze, expressed as
J (I W,d( (Wia. W, E WA Vi}
where W; is some class of possible instantiations of the i-th weight matrix. We also overload notation and let W, & {h + W,h W. E W.} denote the class of functions corresponding to matrix multiplication by a weight W,. Let || llop denote the matrix operator norm. For function class G. we let N (e. G) denote the e-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 function class G satisfies with complexity (g-1(9) for all e > 0.
the covering condition with respect to norm ||
c (G)
log (og,Ni-j(e.)))
5
2
24

---

Published as a conference paper at ICLR 2021
To sketch the proof technique, only provide the proof of (3.6) in Theorem 3.7, the other bounds follow with the same argument. The following lemma bounds RB(GT (G) in terms of the robust all-layer margin m-
Lemma D.6 (Adaptation of Theorem A.1 of (Wei & Ma. 2019b)), Suppose that weight matrix mappings W; satisfy Condition D.5 with operator norm || llop and complexity function Cii (W.).
With probability 1 - 8 over the draw of the training data, for all i >> 0, all classifiers F E F will satisfy
( GHI (W:) tvn
RB(G) I [Ep(((m((F,)) +t]]+0
logn +
(D.1)
where ç a O (V log(1/6)+logm (V
is a low-order term.
n
The proof of Lemma D.6 mirrors the proof of Theorem A.I 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 bound that depends slightly modified loss. Towards proving Lemma D.6, first define ||6||| & [|[ (///:l2:.......
average margin, must analyze the generalization of
1| ll2)
for perturbation 8, and I|I & IKIlWillop..... [Wpllo))ll-- We show that mF(FF x)) is Lipschitz in F for fixed x with respect to III III.
Claim D.7. Choose F, F F. Then for any x X,
(mg(F,2) 2) mg F, Fx2) IIF Fll
The same conclusion holds if we replace mg with m.
Proof. We consider two cases:
Case I: arg max, F(x); arg max, F(r);- Let y denote the common value. this case, the desired result immediately follows from Claim E.1 of (Wei & Ma, 2019b).
Case 2: arg max; F(x); + arg max; F(x): In this case, the construction of Claim A.l in (Wei Ma, 2019b) implies that 0 S mm((Fx)) S || Fll- (Essentially we choose 8 with ||] s || 11-FP Flll such that F(x, 6) = F(x).) Likewise, 0 S ms(F x) s F| Flll- As a result, it must follow that (mB(F,x) ms (F,(F.2) x)) < F Fll--
For > 0, define the ramp loss hú as follows: h (a) 1 1(a 0) min(a/t,1]
We now define the hypothesis class L, A (h.oms(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 W; satisfies Condition D.5 with operator norm || llp and complexity Cijll,,, (W... Then
Rad,, s o CHI,
logn
tyn
As the proof of Claim D.8 is standard, provide 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 I|I -Il and complexity (IF & Σ, C111 (Fi). Now let F be te-cover of F in I||. We define the (2(PP)-nom) -norm of a function f X + R as follows:
Then it is standard to show that
E, (h, m F)
25

---

Published as a conference paper at ICLR 2021
e-cover of L in (x(P))-nomm because h, is 1/t-Lipschitz and ms(F, is 1-Lipschitz in F
for norm I|I || for any fixed z. It follows that log log.Nig(r.)ee, C.) -
c 1260
(F)
Now we apply
Dudley's ' Theorem:
Rad, (Ci) < iuf
B
1 Vn
{
NoogNee Li)de
320
ci l2e2
(
x inf
8
de
8>0
A standard computation can be used to bound the quantity the right, giving the desired result.
Proof of Lemma D.6. First, by the standard relationship between Rademacher complexity and gen- eralization, Claim D.8 lets us conclude that with probability - 6, for any fixed > all F satisfy:
(p]h((m((F;x)) (F)) + +0 (1 (M3)) tv"
log 1/8
log n +
n
We additionally note that (1(mm((FFx) when x & SB(G), because in such cases m8(F,x)
0. It follows that 1(x & Ss(G)) < (F), Thus, we obtain
Σ, C(l. log + log 1/8 W/
(B( S Ep(1(mE(FFF) St]
(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 in the form 1, - mmin 2', where mmin E.Ci-,,, (W.) log n. and 0 S j S O(log n). so we only sketch the argument here. We union bound over (D.2) for & tj with failure probability 5, = 6//2+1, so (D.2) will hold for all fi...., t.maa with probability 1 1-d 5. For any choice of t, there will either be j such that 1/2 S Ij S or (D.1) must trivially hold. (See Theorem C. of (Wei & Ma, 2019b) for a more detailed justification.) As a result, there will be some 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 Cj- I.p ([W || <
a}}) = O( / q log ga). Thus, to obtain (3.6), suffices to apply Lemma D.6 for all choices of a using standard union bound technique;
for example the proof of Theorem 3. 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.
D.3 DEPENDETN LOWER BOUNDS ON ALL-LAYER MARGIN
We will now provide lower bounds on the all- margins used in Theorem 3.7 in the case when the activation has 7- L--iischitz derivative. In this section, it will be convenient modify the indexing to count the activation as its own layer, so there are 2p - layers in total. Let (()) denote the 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 ()=)(1)) to be the Jacobian of the j-th layer with respect the i 1-th layer evaluated at x.
Define (FF(x, y) A F(x), maxi4y y F(x).. We use the following quantity to measure stability in the layer following W():
(() A 5(1
(((()).)
26

---

Published as a conference paper at ICLR 2021
for secondary term (1()) (z, y) given by
p
8 (z) 21(x)
(2 v)
-
(Z)
(3)
==
Σ
1S/S''s2-- (".
We now have the following lower bounds on m(F, x, y) and mg( z): Proposition D.9 (Lemma C.I from (Wei & Ma, 2019b)). In the setting above, if (F((),))))) 0. we have
m(F z
HR (z. y) y)
Furthermore, if (F((() arg max; F(x):) > for all x' E B(x), then
1
mg(F,x) 2 min x' EB(x) (1 arg max, F(z)))==1l
E EXPERIMENTS
E. EMPIRICAL SUPPORT FOR EXPANSION PROPERTY USING GANS
In this section we provide additional details regarding the GAN verification depicted in Figure (left). We use 128 by 128 images sampled from a pre-trained BigGAN (Brock et al., 2018). We categorize images into superclasses chosen in the robustness library of Engstrom 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, uniformly sample 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 follows: optimize objective consisting of the f2 distance from the original image and the negative cross entropy loss of the pretrained classifier w.nt the superclass label. Letting M denote the GAN mapping, x the original image, y the label, and I the pre-trained classifier, the objective is as follows:
min || M() Aooheross-eut (F
We optimize for 2000 gradient descent steps using Ace 10 and learning rate of 0.0003, intial- ized with the same latent variable as was used to generate x. The resulting M (2) is neighbor of æ in the set M(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 neighbor x' E M(F) with | 2' ||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 is appropriate to regard these images as "neighbors". In Figure
visualize typical examples of the neighbors found by this procedure. 19.765 the set MMF), which has probability 0.0626, Thus, setting B(x) {x' ||x' - z|I2 < 2 has 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 pseudolaheler 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 self- training procedure using VAT (Miyato al., 2018). After self-training, the validation accuracy of new classifier G improves to 95.69%.
27

---

Published as a conference paper at ICLR 2021
% corrected by self-training
80
60
40
1-16
16-22 22-28
28-37
> 37
42 distance from neighbor
Figure 3: Self-training corrects mistakenly labeled examples that are close correctly labeled neighbors. We partition examples in M'M (defined in Section E.1) into 5 bins based on their & distance from the neighbor used initialize the projection, and plot the percentage of examples in each bin whose labels were corrected by self-training. The bins are chosen to be equally sized. The plot suggests that as mistakenly labeled example is closer correctly labeled example input space, it is more likely to be corrected by self- self-training. This supports our theoretical intuition that soaat-connistenc-rreglllee
self-training denoises pseudolabels by bootstrapping an incorrectly pseudolabeled example with its correctly pseudolabeled neighbors.
Furthermore, evaluate performance of the self-trained classifier & on subset of M with distance greater than I from its neighbor. We let M' denote this subset. We choose to filter M this way 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 is more accurate on examples from M' which are closer to the original neighbor used to initialize the projection. This provides evidence that input- consistency-regulane lying on which are closer their neighbors are more likely to be denoised. Finally, we also remark that Fig- ure 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- eeff-training dataset.
self-training is indeed correcting the mistakes of the pseudolabeler by re- neighbors for denoising, because Figure shows that examples
E.2 PSEUDOLABELING EXPERIMENTS
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 model on the labeled source dataset and directly evaluate it on the target valida- tion set.
PL: Using the classifier obtained above, 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 & ball
around x. We train a classifier to fit pscudolabels while regularizing adversarial robustness on the target domain using the VAT loss of (Miyato et al., 2018), obtaining the following loss over classifier F:
C(F) A Leross-e F,, Gpt) + LNLr
Note that this loss only enforces true stability examples where F(z) correctly predicts (z()). 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.
28

---

Published as a conference paper at ICLR 2021
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 This encourages robustness on the training set to generalize better.
PL+ MAM+ 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 ground- truth. 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 Gpt. To this end, we modify the loss allow the classifier to ignore с 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.
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:
C(F) _ XgLeaossennt sre (F) + Ae tgt (F) + Ly (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 shows the performance of these methods on six unsupervised domain adaptation bench- marks. 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-of- the-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 for VATEnn++VTTANN
the target while training on labeled source data. Our results 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- CIFAR-10. We provide additional experimental details below. We use the same dataset setup and model architecture for each dataset as (Shu al., 2018). All classifiers are optimized using SGD with cosine learning rate and weight decay of 5c-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 A. the coefficient of the VAT loss, by tuning in the same manner in the range (3, 10, 30). For MinEnt+ AMOO we fix the best hyperparameters for 1. We also tune the batch size for the source loss in {64, 128). X. E {0.25, 0.5, }} and fix A Table depicts accuracies on the target validation set. We use early stopping and display the best ac- curacy achieved during training. All displayed accuracies
and tune
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 lg norm 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 pertur- bations are set to O. and we jointly optimize them with the perturbation to the input using one step of gradient ascent with 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 opti- mization objective from falling into bad local minima. We will maintain model whose weights are the exponential moving average of the past model weights, Fema. Every gradient update, the weights of Fema are updated by W +- 0.999W ema + 1001W where Wam is the current model weight after the gradient update. Our aim is to throw out f--fraction of pseudolabels which maximize Leross-cut (Fae (Fomma (x))(x)) Gz),)), where (z) is the pseudolabel for example z, and indexes the current iteration. We will increase T; linearly from 0 to its final value 7 over the course of training. Towards this goal, we maintain an exponential moving average of the (1 T.)- quantile of the loss, which is updated every iteration using the (1 - T -quantile of the loss furows (F (x), Gp(()) computed on the current batch. We ignore pseudolabels where this loss value above the maintained exponential moving average for the (1 - T; -th loss quantile.
29

---

Published as a conference paper at ICLR 2021
Table 1:
Validation accuracy on the target data various self-training methods. We see that perfor-
mance improves we add components of our theoretical objective (4.1).
Source
MNIST SVHN
MNIST MNIST-M
SVHN MNIST
SynDigits SVHN
SynSigns GTSRB
STL-10
Target
CIFAR-
Source Only
35.8%
57.3%
85.4%
86.3%
77.8%
58.7%
MinEnt + VAT + AMO
20.6%
28.9%
83.2%
83.6%
42.8%
67.6%
PL Only
38.3%
60.7%
92.3%
90.6%
85.7%
62.0%
+ VAT
41.7%
79.8%
97.6%
93.4%
90.5%
62.3%
AMO
42.5%
81.4%
97.9%
93.8%
93.0%
63.9%
+ MinEnt
46.8%
93.8%
98.9%
94.8%
95.4%
67.0%
30


Reviews:
[{"review_id": "pImZKtEe4UV", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary 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.\n\nReview: Overall, the paper is written nicely and gives a novel perspective on self-training. Several questions:\n\t1) It is a bit strange that semi-supervised learning requires a stronger assumption on expansion than unsupervised learning. Is it possible to use the unsupervised method and then somehow align it with the semi-supervised labels?\n\t2) The assumptions depends heavily on $\\mathcal{B}$ - if $\\mathcal{B}$ is too large than we have inconsistency, if it is too small than we lose expansion. How will the results change if $\\mathcal{B}$ is of other forms (e.g., coming from a model)?\n\nI feel that the paper gives an interesting notion to consider for self-training and the statements are rigorous. I would recommend acceptance.", "extra_scores": {}, "extra_text": {}}, {"review_id": "lXk8Uhgyu9d", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary:**\nThis 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. \nThey also provide finite sample guarantees based on off-the-shelf generalization bounds for unsupervised learning. \n\n**+ves**\n+ The expansion property seems neat, and seems like a natural quantity for making progress in understanding self-training theoretically \n+ The authors also provide support for this empirically in Section D. \n+ The paper is very well written. In particular, the summary of the theoretical results in the main paper is very well done. I also appreciated the proof intuition for Theorem 4.3's proof\n\n**Concerns/Comments:**\n- I think it would be helpful for the reader to have a brief proof sketch of the theorems immediately after the statement. The results are already summarized (well!) informally in the introduction. \n- It is unclear to me how realistic Assumption 4.1 is. \n\n**Questions for the Authors:**\n- Can you expand on the optimization objective of (4.1)? How may one implement this in practice? Or, how is this analogous to what is being done in practice? \n- Can you comment on the realism of Assumption 4.1? Is it possible to verify this on toy examples as you have done with the assumptions in Section 3? \n- Can you comment on obtaining a finite sample version of Theorem 4.3? \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Vpp_yDmBCVY", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In general, it is not clear, at least theoretically, how, and when unsupervised data helps to generalization of nonlinear methods. In the literature there are important and elegant works exists that analyses the impact of usage of unlabelled data during training, however, (if I am not mistaken) all these analyses have been done for linear models. Authors analyse and shed some light to several aspects of using unlabelled data during training. They formalize their analyses based on expansion assumption. I think it can be restated as the similarity between members of the same classes is bounded by below. Intuitively such an assumption is quite reasonable. The authors use the term input consistency for defining a broad set of methods e.g. transformations of the image should be similar to each other, and they also couple their analysis using the expansion assumption with input consistency. In their view input consistency brings a local stability/generalization and expansion property brings global stability/generalization. This is again quite reasonable way of thinking because intuitively just forcing an input point to be close to transformed version of itself sounds a weak property for a good generalization performance. The authors supply quite a bit of theoretical novel material to support their intuition and analysis. \nFurthermore, they present some supportive experiments albeit not an extensive one. \n\nStrong and weak points:\na)\tStrong points: Please see above.\nb)\tThe paper is quite dense, and the reader needs to be familiar with learning theory concepts. I wonder if authors would have focused on only one aspect of the problem which they are dealing. In the current version semi-supervised learning methods, unsupervised domain adaptation and unsupervised learning are covered. Every of them is a field by itself. I understand the desire of a unified and generic framework however I can imagine that there is a risk of diluting the message.\nc)\tAnother understandably weak point is the experiments. I personally think that conducting an experimental study in the scope of this quite challenging however it will be nice see expansion property on a real dataset.\nRecommendation:\nOverall, I would like this paper to get published because (if I am not mistaken) paper develops an initial understanding extremely important field e.g. self-training/self-supervised learning. \n\nSupporting arguments:\na)\tI found the assumptions paper quite intuitive and necessary. Authors also supply population level guarantees for unsupervised learning. Moreover, they extend their work finite-sample guarantees by using margin concept and Lipschitz continuity. They extend their work to domain adaptation and semi-supervised learning. The novel material in the paper is extensive.\n\n\nQuestions:\na)\tAs I mentioned before I would like to expansion property on some real-world datasets. For example, can authors present some evidence of expansion property for a chosen deep neural network on a dataset (or multiple datasets) and quantify the expansion property based on some metric.  \nImprovement Suggestions:\na)\tThe paper is quite dense, and the reader needs to be familiar with learning theory concepts. I would recommend authors to decrease density of the paper and may be move some parts to the supplementary material.\n\nAlthough I am quite positive about paper, I would like to see the discussion and comments. I am open to change my review to any direction if some new evidence/discussion/published work supplied.\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "GYCQ3ygXVfI", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.  \n\nmerits\n1) In the theoretical aspect, the established results can explain the success of self-training training and is of high quality. \n\n2) Moreover, this work is well written and easy to follow. \n\nQuestions\n1) Though this work provides good theoretical results, it seems that the results do not bring any practical insights to further improve the analyzed algorithms. E.g. the population-based loss in Eq. (3.4) is not used in practice, since the loss is on expectation and is relatively complex. Actually, when the network is large, then sampling data to estimate E_p[1(G(x)=y)] and R_B(G) is of the high cost. \n\n2) About the assumption that neighborhoods of samples from different classes have a small overlap, it also may be restrictive. For example, in imagenet, there are many images that contain several objects actually. This means that the overlap between samples from different classes may be not small. \n\n3) Finally, the key expansion constant c is not investigated on the toy and real datasets. What is the magnitude of c? this is very important since the upper bound will be large if (c/(c-1)) is hugh.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper looks into theoretical analysis of self-training beyond the existing linear case and considers deep networks under additional assumption on data. namely: expansion and minimal overlap in the neighborhood of examples in different classes. The results shed some light on self-training algorithms that use input consistency regularizers.
Although the assumptions are very hard to check for all input distributions, the authors make an attempt by considering output of BigGAN generator. In summary, the paper is a great first step in understanding self-training for deep networks.

The paper is overall clearly written. please add the explanation of  Assumption 4.1 as requested by Reviewer 4.

Pros: - given the extensive use of self-training the paper is of great importance to the community
-extending the analysis of self-training to deep networks
-the paper is clearly written and easy to follow

cons: -the assumptions are very hard to validate on all datasets

Decision: Accept (Oral)