Title: ITERATIVELY LEARNING FROM THE BEST

Abstract: We study a simple generic framework to address the issue of bad training data; both bad labels in supervised problems, and bad samples in unsupervised ones. Our approach starts by fitting a model to the whole training dataset, but then iteratively improves it by alternating between (a) revisiting the training data to select samples with lowest current loss, and (b) re-training the model on only these selected samples. It can be applied to any existing model training setting which provides a loss measure for samples, and a way to refit on new ones. We show the merit of this approach in both theory and practice. We first prove statistical consistency, and linear convergence to the ground truth and global optimum, for two simpler model settings: mixed linear regression, and gaussian mixture models. We then demonstrate its success empirically in (a) saving the accuracy of existing deep image classifiers when there are errors in the labels of training images, and (b) improving the quality of samples generated by existing DC-GAN models, when it is given training data that contains a fraction of the images from a different and unintended dataset. The experimental results show significant improvement over the baseline methods that ignore the existence of bad labels/samples.

1. INTRODUCTION:

This paper is motivated by the problem that training large machine learning models requires wellcurated training sets with lots of samples. This is an issue in both supervised and unsupervised settings. For supervised problems (e.g. multi-label classification) we need very many properly labeled examples; generating these requires a lot of human effort. Errors in labels can significantly affect the accuracy of naive training. For example, a faulty CIFAR-10 dataset with 20% of automobile images mis-labeled as "airplane" (and so on for the other classes) leads to the accuracy of a neural architecture like WRN of Zagoruyko & Komodakis (2016) to go from over 90% to about 70%. Even in unsupervised problems, where there are no labels, spurious samples are a nuisance. Consider for example the task of training a generative adversarial network (GAN) Goodfellow et al. (2014) to produce realistic images of faces. While this has been shown to work well using a dataset of face images1 , like Celeb-A Liu et al. (2015) , it degrades quickly if the training dataset is corrupted with non-face images. Our experiments illustrate these issues.

Main idea We study a simple framework that addresses the problem of spurious data in both supervised and unsupervised settings. Note that if we knew which samples were clean, we could learn a model; conversely, if we had a good model, we could find the clean samples. But we do not have either; instead we have a chicken-and-egg problem: finding the best subset of samples needs a model, but finding a model needs a subset of samples. In this paper, we take the natural approach to this problem by (0) fitting an initial model on all samples, and then alternating between (1) finding the best subset of samples given a model, and (2) fitting a model given a subset. 2 Our approach is most related to the works of Bhatia et al. (2015) and Vainsencher et al. (2017) , and we contrast to these in the related work section.

Our approach can be applied to any existing model that provides (a) confidence scores for samples, and (b) a way to train the model for a set of samples. Indeed in our experiments we use existing models and training code, but with iterative (re)selections of samples as above. In supervised settings, any model that maps features to responses typically associates a confidence to every sample, e.g., in linear regression, given a model θ, the confidence in a sample (x i , y i ) increases as its squared error (y i -x i θ) 2 decreases. For a neural network classifier, on the other hand, the confidence can be measured by the cross entropy loss between the output probability distribution and the true distribution. In unsupervised settings, the confidence of a sample is given by its "likelihood" under the model. If we are lucky, e.g., in Gaussian mixture models, this likelihood is explicit and can be evaluated. However, if there is no explicit likelihood, we need to rely on a surrogate. E.g., in our GAN setting below, we rely on the output of the discriminator as a confidence measure. We also note an important caveat: this paper is not focused on (and may not be effective for) the settings of adversarial examples, or of gross corruptions of features. Rather, our focus is to address the issue of bad labeling or curation of data, as motivated above.

OUR RESULTS AND PAPER OUTLINE:

We show that our framework (outlined in Section 3) can address the spurious sample problem, both theoretically and empirically and for both supervised and unsupervised problems:

(1) Mixed linear regression (Section 4) and Gaussian mixture models (Section 5): For each of these mixture problem settings, under the standard statistical assumptions, we establish both statistical consistency and linear convergence of our iteratively updated model parameters. This holds true from any initial point; the convergence is to the mixture component that is closest to the initial point.

(2) Neural network classifiers (Section 6) : We investigate image classification in CIFAR-100, CIFAR-10 and MNIST datasets (each with a different and appropriate existing neural architecture) in the setting where there are systematic errors in the labels -i.e. every bad example in one label class comes from the same other label class. We show that our framework can significantly improve the classification accuracy over the baseline method that ignores the existence of bad samples.

(3) Deep generative models (Section 7): We show both quantitatively and qualitatively the improvement of using our algorithm for image generation when the dataset consists of two types of images. Specifically, investigate training a GAN to (a) generate face images as in the "intended" Celeb-A dataset, but when the given training data has a fraction of the samples being the "spurious" CIFAR-10 images, and (b) generate intended MNIST digits when training data contains a fraction of samples from the spurious Fashion-MNIST dataset. A crucial innovation here is that the output of the discriminator network in the GAN can be used as a confidence metric for the training samples.

In Section 8, we discuss the positives and negatives of our results, underlying intuition and also some future directions. All of our experiments were done on clearly identified publicly available neural network architectures, datasets, and training software. We also clearly describe our error and noise effects; we expect them to be easily reproducible.

2. RELATED WORK:

Alternating minimization for robustness Two works are most related to ours. Bhatia et al. (2015) proposes an iterative hard thresholding algorithm for adversarial noise in linear regression responses; they establish statistical guarantees and linear convergence under this harder noise model. We focus on multiple mixed linear regression, a different setting that results in an easier noise model, and we provide convergence guarantee for recovering any single mixture component starting from a local region. In addition we also prove these for Gaussian mixture models, which is not studied in their work. Vainsencher et al. (2017) proposes what is essentially a soft version of our method, and proves local convergence and generalization. However they do not have any initialization, and hence no global or consistency guarantees. Neither of these empirically explore the overall approach for more complex / neural network models.

Robust regression:

Recent work on robust regression consider strong robustness in terms of both the inputs and the outputs and provide guarantees for constant corruption ratio Diakonikolas et al. (2018) ; Prasad et al. (2018) ; Klivans et al. (2018) . Chen et al. (2013) ; Balakrishnan et al. (2017a) ; Liu et al. (2018) study the high dimensional setting under this regime. These algorithms usually require much more computation, compared with methods for dealing with noisy outputs, e.g., Bhatia et al. (2015) . Another type of robustness considers heteroscedastic noise for every sample. From the learning perspective, Anava & Mannor (2016) ; Chaudhuri et al. (2017) both require strong constraints on the noise model which largely reduces the degree of freedom. Anava & Mannor (2016) considers the online learning setting, while Chaudhuri et al. (2017) considers the active learning setting.

Mixed linear regression:

Alternating minimization type algorithms are used for mixed linear regression with convergence guarantee Yi et al. (2014) . Chen et al. (2014) provides a convex formulation for the problem. Balakrishnan et al. (2017b) shows expectation-maximization (EM) algorithm is provably effective for a set of tasks including the basic setting of mixed linear regression and Gaussian mixture model. Sedghi et al. (2016) extends to the multiple component setting, where provable tensor decomposition methods are used. More recently, Li & Liang (2018) gives a more general result for learning mixtures of linear regression. On the other hand, Ray et al. (2018) studies the problem of finding a single component in mixed linear regression problem using side information.

Noisy labels Classification tasks with noisy labels are also of wide interest. Frénay et al. (2014) gives an overview of the related methods. Theoretical guarantee for noisy binary classification has been studied under different settings Scott et al. (2013) ; Natarajan et al. (2013); Menon et al. (2016) . More recently, noisy label problems have been studied for deep neural network based models. Reed et al. (2014) and Malach & Shalev-Shwartz (2017) develop the idea of bootstrapping and query-bycommittee into neural network based models. On the other hand, Khetan et al. (2018) and Zhang & Sabuncu (2018) provide new losses for training under the noise. Sukhbaatar & Fergus (2014) adds a noise layer into the training process, while Ren et al. (2018b) provides a meta-algorithm for learning the weights of all samples by referencing to a clean subset of validation data during training. Ren et al. (2018a) consider building robust classifiers for the positive-unlabeled classification problem using l 0 norm penalization.

Others Bora et al. (2018) studies the problem of noisy images for GANs. In their setting, all images are of low quality under some measurements, while in our problem, we consider the image dataset consists of (possibly more than) two types of images, which is different. There are also studies that consider noisy samples more generally. The classical RANSAC method Fischler & Bolles (1981) provides a paradigm for fitting a model to experimental data, and can be potentially used for the noisy data setting. However, the algorithm requires multiple times of random sampling to find a valid consensus score, which is conceptually different from our idea of doing iterative filtering. EM algorithm Moon (1996) can also be used for detecting noisy samples, e.g., in the setting of mixture models Balakrishnan et al. (2017b) . However, our algorithm does not need to know the likelihood for the bad samples for the iterative updates.

3. ITERATIVELY LEARNING FROM THE BEST ( ILFB ):

We now describe the setup and algorithm, in a unified way that covers both supervised and unsupervised settings. We will then specialize to the many specific problems we study. We are provided with samples s 1 , • • • , s n , using which we want to train a model parameterized by θ ∈ R d . We are also provided with a loss function; let f θ (s) denote the loss of a sample s when the parameters are θ. Let τ ∈ [0, 1] be the fraction of data we want to fit. With this setup, the idea of learning from the best can be viewed as trying to solve

min θ min S:|S|=τ n i∈S f θ (s i ).

We do this by alternating between finding S and finding θ, as described below in Alg. 1. t ← t + 1 8: return: θ T Comments Steps 4, 5 and 6 above can be done approximately, when exact solutions are unavailable. For example, in our experiments involving deep neural networks (both the classifiers and the generative models), for step 6 we do not fit a model exactly, but rather do training using stochastic gradient descent. Also, for our experiments on training GANs on the best subset, we do not have an explicit loss; we instead use the loss at the output of the discriminator as a surrogate (more details on that below). Similarly, the initialization step above can possibly be replaced with some problem-setting dependent alternative, if one is available.

In the following, we describe how this directly specializes to each of our four settings.

4. ILFB FOR MIXED LINEAR REGRESSION:

We first describe ILFB as specialized to the case when the θ represents the parameters of a linear regression, and then describe the statistical setting of mixed linear regression where we provide rigorous statistical guarantees on its performance. Algorithm The samples are s i = (x i , y i ) with features x i ∈ R d and responses y i ∈ R, and θ ∈ R d are the parameters of the linear model. The loss is f θ (x, y) = (y -x θ) 2 . The algorithm thus initializes θ 0 by doing an ordinary least squares (OLS) on all the samples, and then alternates between finding the set of τ n samples with the lowest squared error for the current θ, and then finding the new θ by doing an OLS on this set.

Statistical Setting:

In the standard and widely studied mixed linear regression problem there are n samples (x i , y i ), with features x i ∼ N (0, I d ) being standard gaussians in d dimensions. The full set of samples S = [n] can be splitted into m sets S = ∪ j∈[m] S j , each corresponding to samples that generate from one mixture component, |S j | = τ j n. The response variables y i are given by:

EQUATION

where i ∼ N (0, σ 2 ) is the additive noise, and θ (j) s are assumed to be unit norm vectors. We analyze our algorithm in the fresh sample setting, where iteration t finds θ t+1 from θ t using a new set of samples. This too is standard in the statistical analysis of mixed linear regression, and corresponds to the case of using mini-batches of samples to learn a model.

We now prove two results: the first shows that the iterates converge linearly to some θ (j) once θ t is closer enough to θ (j) than any of the other components, and the second shows that the simple initialization step ensures a θ 0 that is close enough to the dominant component θ (j) under mild assumptions.

Theorem 1 (local linear convergence). For the mixed linear regression setting as above, we run ILFB as shown in Algorithm 1. Suppose for some j ∈ [m], the iterate θ t and τ satisfy:

(C1) τ ≤ 0.99τ j ; (C2) θ t -θ (j) 2 ≤ C(τ ) min l∈[m]\{j} θ t -θ (l) 2 -1 -C 2 (τ )σ, where C(τ ) = min{ c1c3τ 1-τ , 1}.

Then, the next iterate θ t+1 of the algorithm satisfies

θ t+1 -θ (j) 2 ≤ c 1 θ t -θ (j) 2 + (c 1 + c 2 )σ

with high probability (i.e., with probability 1 -n -c0 ), provided the number of samples n ≥ c d log d c 2 2 τ , where c 1 ∈ (0, 1), c, c 0 , c 2 , c 3 are constants.

Theorem 1 establishes a linear dependence of the sample complexity on the dimension d. The required sample size increases as τ gets smaller. For τ large enough such that C(τ ) = 1, the condition on θ t does not depend on σ. However, notice that for smaller τ , the condition of θ t tolerates smaller noise. This is because, even if θ t is very close to θ (j) , when the noise and the density of samples from other mixture components are both high, the number of samples from other components selected by the current θ t would still be quite large, and the update will not converge to θ (j) .

The proof for the theorem is in Appendix C.1, and synthetic experiments verifying the performance of ILFB are in Appendix C.2. In Appendix C.2, we show that our guarantee for the algorithm is tight, in the sense that there always exist a σ dependency even if we take infinite samples. In the noiselss setting, our theorem guarantees local linear convergence with exact recovery.

5. ILFB FOR GAUSSIAN MIXTURE MODEL:

In this section, we describe ILFB applied to the setting of Gaussian mixture model, and provide statistical guarantees on its performance.

Algorithm:

The samples s i = x i are points in R d , θ ∈ R d is the mean we want to estimate, and f θ (x) is proportional to the negative log-likelihood, i.e., f θ (x) = x -θ 2 2 . The algorithm thus initializes the mean by finding the average of all n points, and then iteratively finds the set of τ n points closest to the current mean, and updating the mean to be the average of this set.

Statistical setting Given a dataset:

D = {x i | i ∈ S = {1, • • • , n}}, where S can be splitted into disjoint sets S = ∪ j∈[m] S j , |S j | = τ j n.

The samples are generated following:

x i ∼ N θ (j) , σ 2 I , for i ∈ S j .

(2)

We now prove two results: the first shows that iterates converge linearly under the fresh sample setting in a local region, while the second shows with some additional conditions, that the initialization of ILFB falls into the local region of the dominant component.

Theorem 2 (local linear convergence). We run Alg. 1 on the given dataset D generated following (2). Suppose for some j ∈ [m], the iterate θ t and parameter τ in Algorithm 1 satisfy:

(C1) τ ≤ 0.99τ j ; (C2) θ t -θ (j) 2 ≤ 0.9 min l∈[m]\{j} θ t -θ (l) 2 -c 3 σ log 2(1-τ ) τ 1 {τ < 1 2 }

then, with high probability (i.e., with probability 1 -n -c0 ),

θ t+1 -θ (j) 2 ≤ c 1 θ t -θ (j) 2 + c 2 √ dσ,

where c 1 ∈ (0, 1), c 0 , c 2 , c 3 are constants. Here, the 0.9 factor in the assumption is chosen for convenience of the analysis. Essentially, what we need is this value being less than one. For τ < 1 2 , we require an additional separation term that depends on σ. This term essentially implies a √ log kσ separation distance (consider all mixture components have weights 1/k), which is the lower bound for computationally efficient algorithm to learn a Gaussian mixture model according to Regev & Vijayaraghavan (2017) . Intuitively, given the required initialization condition, the samples selected by the initialization parameter contain more than half of the good samples, and we can show that the algorithm is guaranteed to converge. Notice that there is no dependency between n and d. In the extreme case where σ = 0, we only need n to be a constant value: from any good initialization point, the algorithm will converge to θ (j) in one step.

The proof for the theorem is in Appendix D.1, and synthetic experiments verifying the performance of ILFB are in Appendix D.2. Again, in Appendix D.2, we show that the our guarantee of the algorithm is tight.

6. ILFB FOR DEEP IMAGE CLASSIFICATION WITH SYSTEMATIC TRAINING LABEL ERROR:

Experimental setting We consider systematic errors in labels, i.e. the setting where all the samples that actually come from a class "a" are given the same bad label "b", a setting that is less benign than one with more randomness in the errors. We investigated the ability of our framework to account for these errors for the following dataset -neural architecture pairs: Further details When training on all the samples, we run simple stochastic gradient descent algorithm with initial learning rate 0.5/0.1/0.1 and batch size 1000/256/64 for MNIST/CIFAR-10/CIFAR-100, respectively. The learning rate is divided by 5 at the 50-th epoch and each ex-Table 2 : Generative models from mixed training data: A quantitative measure of the efficacy of our approach is to find how many of the good training samples the final discriminator can identify; this is shown here for the three different "good"/"bad" dataset pairs. For each pair, the fraction of "good" samples is 90%, 80% or 70%. The table depicts the ratio of the good samples in the training data that are recovered by the discriminator when it is run on the training samples. The higher this fraction, the more effective the generator. For MNIST-Fashion and CelebA-CIFAR10, our approach shows significant improvements with iteration count. For CIFAR10-CelebA dataset, the error is extremely simple to be corrected, likely because faces are easier to discriminate against when compared to natural images. periment runs for 80 epochs. For each iteration of update using our ILFB algorithm, since less samples are used at each epoch, we adjust the total epoch number accordingly, so that the training for every iteration uses the same number of SGD updates. We set τ to be 5% less than the true ratio of "good" samples.

Results Table 1 shows the results for the baseline, oracle and our methods. Please see the caption thereof. We observe significant improvement over the baseline under all experiments. In Appendix B, we provide a comparison of using different initialization methods, where ILFB performs better than its counterpart with random initialization. In Appendix E, we provide more experimental results illustrating that ILFB is not sensitive to mis-specified τ , the improvement of this iterative procedure compared with a single iteration, the advantage over other outlier removal options, and its capability of handling random label noise.

7. ILFB FOR DEEP GENERATIVE MODELS WITH MIXED TRAINING DATA:

Experimental setting We consider training a GAN -specifically, the DC-GAN architecture Radford et al. ( 2015) -to generate images similar to those from a good dataset, but when the training data given to it contains some fraction of the samples from a different bad dataset. All images are unlabeled, and we do not know which training sample comes from which dataset. We investigated the efficacy of our approach in three such settings: (a) When the good dataset is the Celeb-A face images, and the bad dataset is CIFAR-10. (b) When the good dataset is the CIFAR-10 face images, and the bad dataset is Celeb-A.

(c) When the good dataset is MNIST digits, and the bad is Fashion- MNIST Xiao et al. (2017) .

For each of these, we consider different fractions of bad samples in the training data, evaluate their effect on standard GAN training, and then the efficacy of our approach as we execute it for upto 5 iterations.

Algorithm Recall that training a GAN consists of updating the weights of both a generator network and a discriminator network; our model θ is the parameters of both of these networks. Unlike the classification seeing, we now need to develop a loss f θ (s) -and unlike in the simple Gaussian mixture model setting we do not have explicit access to a likelihood function for the generative model. Our crucial innovation is to use the loss7 at the output of the discriminator -the same one used to train the discriminator -as the f θ (s). The algorithm starts by training on all samples, and then alternates between picking training samples with the smallest discriminator loss, and retraining CelebA "good" images + 30% CIFAR-10 "bad" images, the four panels above each show the performance after iterations of our ILFB algorithm. First we choose 18 random vectors in latent pace, and fix them for all iterations. In each iteration, we retrain the GAN on corresponding selected samples to get new weighs, which are then used to generate the 18 fake images. Baseline refers to the standard training where we fit to all the samples (this is also our initialization). Visually, we can see that the generator is able to improve its generation quality and only generate face-like images after the 5th iteration.

the model on these picked samples. Here training means updating both the generator and discriminator network weights, which is done via SGD. Again, we set τ to be 5% less than the true ratio of "good" samples. This figure shows that when the fraction of "bad" samples is too large, ILFB cannot clean them out. The setting is exactly the same as in Figure 1 , but now with 60% MNIST "good" images + 40% Fashion-MNIST "bad" images. We can see that now the 5 th iteration still retains the fake fashion images. Please see the discussion section for some intuition on this.

Results:

We evaluate the effect of bad training samples, and the improvement by our approach, in two ways: quantitatively in Table 2 and qualitatively in Figures 1 and 2 . Figure 3 illustrates a failure case, when the bad set is too big, which we feel gives insight into what is going on. Please see the respective captions. The failure example happens for MNIST-Fashion dataset when ratio of MNIST images is 60%. In fact, for every iteration, ILFB selects all images from FashionMNIST (which counts for 0.4n) and 0.15n MNIST images (the least number of MNIST images the algorithm can select). See Fig. 3 for qualitative evaluation of the results. In Appendix E, we provide more experimental results illustrating that ILFB is not sensitive to mis-specified τ and the advantage over other outlier removal options.

8. DISCUSSION:

We demonstrated, both theoretically for simpler settings, and empirically for more challenging neural network ones, the merit of iteratively fitting to the best samples -in both supervised and unsupervised problems. The underlying intuition is that ILFB can focus in on the "good" samples, provided it is properly initailized; and when the number of bad samples is significant but not overwhelming, initial fitting on all the data is good enough to get started. We now add several discussions on the merits and otherwise of our results:

(1) One way to view the effect of ILFB in the GAN setting: a discriminator is likely least certain on the smallest modes of a distribution, and our process of dropping training samples based on this results in the elimination of smaller modes, which correspond to modes from the bad samples. This is illustrated by the failure case in Fig. 3 , where the presence of a high fraction of "bad" fashion-MNIST samples makes their modes comparable to those of the "good" MNIST.

(2) Retaining samples best fit by the current model is inherently local, in the sense that samples with large errors are ignored. Finding a good initialization to start with is thus important; without this we may have bad performance. When the size of the good samples is comparatively large, an initial fit on all the samples is good enough; otherwise, we may use other alternatives to initialize the model, e.g., fit the model on a smaller dataset with clean data.

(3) The ILFB algorithm is simple and efficient enough to be applied to most modern machine learning tasks. When there exists extra computation power or knowledge on the specific dataset, it is certainly possible to improve based on ILFB . However, we believe ILFB is simple and general enough, and may serve as a strong result when more complicated outlier detection or noisy label algorithms are proposed.

A EFFECT OF MIS-SPECIFICATION:



A.1 MIS-SPECIFICATION FOR A CLEAN DATASET:

We test the performance of ILFB under mis-specified τ when the dataset is clean, i.e., there is only a single component. We choose random θ ∈ R d with unit norm, the mis-specified τ is set as 0.95, dimension d = 100, and sample size n ∈ {500, 1000, 1500}, T = 30. As shown in Fig. 4 , as σ gets larger, the gap between ILFB and OLS estimator (in terms of 2 distance) increases linearly. We further show the performance of ILFB as sample size increases. In Fig. 6 , the asymptotic performance under different noise levels is shown. For the clean dataset, ILFB is observed to give consistent estimate. We observe similar performance in the Gaussian setting as well. 

A.2 MIS-SPECIFICATION FOR A NOISY DATASET:

In this part, we test the performance when using different τ values for a noisy dataset. Again, we present the result for the mixed linear regression setting. We run ILFB for 10 iterations and the results are based on an average of 50 random runs. In Fig. 5 , we see that the performance is not sensitive to the mis-specified τ in a large region. Interestingly, ILFB still performs well when τ is slightly larger than the true ratio of the component we are interested in.

B RANDOM INITIALIZATION FOR CLASSIFICATION:

We study the effect of initialization for the classification problem using MNIST (5%) dataset. In Table 3 , we present the accuracy after 5-th iteration of training for both random initialization and the original ILFB methods. Even with random initialization, the performance is consistently better than the baseline, however, the improvement of accuracy is smaller when compared to the original ILFB , which uses all samples for training as initialization.

# 

y i = x i θ + i , if i ∈ S good x i θ (j) + i , if i ∈ S j bad

where i ∼ N (0, σ 2 ) is the additive noise, and θ as well as all the θ (j) are assumed to be unit norm vectors.

C.1 PROOF FOR UPDATE STEPS IN LINEAR REGRESSION MODEL:

For simplicity of the notation, we present the proof by assuming y i for bad samples have the form y i = n i + e i , where n i corresponds to x i θ (j) , such that i ∈ S j bad . Let θ t be the current learned parameter. θ t+1 is learned by using one iteration in Algorithm 1. Namely, we first select a subset S t of size τ n with the smallest loss (y i -x i θ t ) 2 , then re-calculate the MLE estimator only using those samples. Denote W t as the diagonal matrix whose diagonal entry W ii equals 1 when the i-th sample is in set S t , otherwise equals 0. Then,

EQUATION

where we used the fact that W 2 t = W t . Notice that W is the ground truth for W t (accordingly, define S for the ground truth of S t ). For clearness of the presentation, we ignore the subscript t when there is no ambiguation. Then, according to the definition of y and reorganizing the terms, (3) can be expanded as

θ t+1 -θ = X WX -1 X W (W Xθ + (I -W ) n + e) -θ = X WX -1 X WW Xθ + X Wn -X WW n -X WXθ + X We = X WX -1 X (WW -W) (Xθ -n -e) + X WX -1 X WW e

where as we addressed at the beginning of this section, for vector n, given i ∈ S bad , n i = x i θ (j) for some j ∈ [m]. Therefore,

EQUATION

We bound the three terms on the right hand side of (4) separately.

Helpful lemmas:

Lemma 3 (Sub-Gamma property for the q-quantile). Let n ≥ 3, let X (1) ≥ • • • ≥ X (n) be the order statistics of the absolute value of standard Gaussian samples. qn is an integer for some constant q ∈ (0, 1). Let v n = 8 qn log 2 . For all 0 ≤ λ < qn

2 √ vn , log E e λ(X (qn) -E[X (qn)]) ≤ v n λ 2 2 1 -2λ vn qn (5)

This shows the sub-gamma property of X (qn) , and as a result, for all t > 0, and constant 1 2 < q < 1,

EQUATION

)

This result is generalized from the result in Boucheron et al. (2012) .

Lemma 4. Suppose we have two Gaussian distributions D 1 = N (0, ∆ 2 ), D 2 = N (0, 1). We have f n i.i.d. samples from D 1 and (1 -f )n i.i.d. samples from D 2 . Denote the set of the top f n samples with smallest abstract values as S f n , where f ≤ f . Then, with high probability, for ∆ ≤ 1, at most

c max ∆ (1 -f ) n √ log n, log n samples in S f n are from D 2 .

Proof of Lemma 4. First, let us consider the probability of a random variable from D 2 has smaller abstract value than a random variable from D 1 . This would give us a rough idea about the occupancy of the samples from D 2 in the top set. Denote the two variables from D 1 , D 2 as u 1 , u 2 respectively. Then, with basic calculations, we have

P [|u 2 | ≤ |u 1 |] = ∞ 0 P [|u 1 | ≥ s] 2 √ 2π e -s 2 2 ds ≤ ∞ 0 2e -s 2 2∆ 2 2 √ 2π e -s 2 2 ds =2 ∆ √ 1 + ∆ 2 .

This calculation implies that if given same number of samples from D 1 and D 2 , it is reasonable to expect that only around 2∆ fraction of the top set samples are from D 2 , when ∆ is small. In the original setting where we have f n samples from D 1 and 1 -

f n from D 2 , we should expect around 2∆ 1- f f f n = 2∆ 1 -f samples in the top set are from D 2 .

Now, we aim for a rigorous proof of the result with good concentration. Our idea is to first show concentration result for the maximum value from distribution D 1 , and then, we show the high probability upper bound for the number of samples from D 2 that are less than the maximum value.

Step I -the sample with maximum abstract value from D 1 . We know that for random normal i.i.d. Gaussian variables

x i , i ∈ [n], P max i∈[n] |x i | ≥ 2 log 2n + t ≤ 2e -t 2 2 .

Therefore, for f n samples from D 1 , with high probability, the maximum abstract value is in the order of O( √ log n∆).

Step II. On the other hand, for a random u 2 ∼ D 2 , we know that for small positive values δ =

c √ log n∆, P [|u 2 | ≤ δ] ≤ 2

π δ gives a tight upper bound. Let M δ,i be the event sample u i from D 2 has abstract value less than δ, and a Bernoulli random variable m i,δ that is the indicator of event M δ,i holds or not. Then,

E   (1-f )n i=1 m i,δ   ≤ 2 π δ (1 -f ) n.

For independent random variable x i s, i ∈ [ñ] that lie in interval [0, 1], with X = i x i and µ = E[X], Chernoff's inequality tells us

P [X ≥ (1 + γ) µ] ≤ e -µγ 2 3 , ∀γ ∈ [0, 1] P [X ≥ (1 + γ) µ] ≤ e -µγ 3

, ∀γ > 1 As a consequence, for m i,δ s, we have

P   (1-f )n i=1 m i,δ ≥ (1 + γ) 2 π δ (1 -f ) n   ≤ e - γ 2 √ 2 π δ(1-f )n 3 , ∀γ ∈ [0, 1] P   (1-f )n i=1 m i,δ ≥ (1 + γ) 2 π δ (1 -f ) n   ≤ e - γ √ 2 π δ(1-f )n 3 , ∀γ > 1.

For the first case, where γ ∈ [0, 1], we can set γ = c log n δ(1-f )n to get high probability guarantee. The constraint on γ requires δn > c log n for some fixed c. On the contrary, when this is violated, i.e., when δ is much smaller, then, by the Chernoff bound for the case γ > 1, we can set γ = c log n δ(1-f )n .

Combining Step I and:

Step II. To summarize, for some fixed constant c, with high probability:

• For ∆ > c √ log n n , at most 2cδ (1 -f ) n = c √ log n∆ (1 -f ) n samples in S f n are from D 2 . • For ∆ ≤ c √ log n n , at most (1 + γ) δ (1 -f ) n = c log n samples in S f n are from D 2 .

Lemma 5. Assume τ < τ ( τ /τ = c τ < 1 is a constant), with high probability, we have:

EQUATION

where c 0 , • • • , c m , c are constants.

Proof of Lemma 5. We focus on finding concentration results for the smallest eigenvalue of X WX. Rewrite X WX as

X WX = i x i x i 1 [l i,t ∈ arg τ n-min (l 1,t , • • • , l n,t )] = i x i x i 1 [l i,t ∈ arg τ n-min (l 1,t , • • • , l n,t )] 1 [i ∈ S ] + j∈[m] i x i x i 1 [l i,t ∈ arg τ n-min (l 1,t , • • • , l n,t )] 1 i ∈ S j (9)

where 1[•] is the indicator function. Note that the values {l i,t } n i=1 are defined as:

l i,t = y i -x i θ t 2 .

More specifically, consider the model setting, we have:

l i,t = x i (θ -θ t ) + i 2 , i ∈ S l i,t = x i (θ j -θ t ) + i 2 , i ∈ S j , j ∈ [m]

For all i ∈ S , l i,t s have the same distribution as δµ, where µ is a χ 2 (1) random variable, and δ is the magnitude δ = θ -θ t 2 2 + σ 2 . The bad samples i ∈ [n]\S , for i ∈ S j bad have the same distribution as (σ 2 + θ (j) -θ t 2 2 )µ. Also, the assumption in θ t assumes that the magnitude of the good distribution is smaller. Applying the results in Lemma 3 and Lemma 4, assuming the condition in Theorem 1 holds, for given θ t , θ , there exists a constant c 1 such that the separation value for deciding top-τ n or not is lower bounded by cδ with high probability. For a fixed c 0 , we consider the following quantity:

Σ(c 0 ) = E x i x i | |x i (θ -θ t ) + i | ≤ c 0 θ -θ t 2 2 + σ 2 .

By the geometry of the constraint, we have that

σ min (Σ (c)) ≥ c -c s 2 1 √ 2π e -s 2 2 ds = 1 -2ψ(c) -ce -c 2 2

In other words, the lower bound we have for the smallest eigenvalue of the expectation of ( 9) monotonically increases with c, and can be substituted with another constant 2c 0 (notice that previously, we have a lower bound on the separation value). Therefore, considering the sub-exponential property, we get the concentration result based on the above expected value:

σ min i x i x i 1 [l i,t ∈ arg τ n-min (l 1,t , • • • , l n,t )] 1 [i ∈ S ] ≥ c 0 2 |S t ∩ S | ,

Similarly, since θ j -θ t ≤ 3, we have a lower bound O(|S t ∩ S j |) for i ∈ S t ∩ S j as well, as long as the set |S t ∩ S j | ≥ c log 2 n. In any case, we have the minimum eigenvalue is lower bounded by cτ n.

T 2 in (4) T 2 can be bounded as follows:

T 2 2 = i∈St\S x i θ -n i -e i x i 2 2 =(Xθ -n -e) (W -WW )XX (W -WW )(Xθ -n -e) ≤σ (W -WW )XX (W -WW ) (Xθ -n -e) (W -WW )(Xθ -n -e) =σ (W -WW )XX (W -WW ) j∈[m] k∈St∩S (j) \S x k θ -x k θ (j) -e k 2 ≤σ (W -WW )XX (W -WW ) j∈[m] k∈St∩S (j) \S x k (θ -θ t ) 2 + x k (θ t -θ (j) ) -e k 2 ≤σ (W -WW )XX (W -WW ) 2 θ t -θ 2 2 + cσ (W -WW )XX (W -WW ) |S t \S | θ t -θ 2 2 + σ 2 ≤c|S t \S | 2 θ t -θ 2 2 + σ 2 for |S t \S | ≥ c log 2 n (when |S t \S | < c log 2 n

, the final convergence result still holds true). As a consequence,

EQUATION

T 3 in (4) For this part, we can reuse the result we proved for T 1 . Also, notice that with high probability:

X WW e 2 2 = e W WXX WW e ≤ cd log nnσ 2 (11)

Putting things together Combining Lemma 5, (10), and (11), we have:

θ t+1 -θ 2 ≤ c |S t \S |( θ t -θ 2 + σ) τ n + c √ nd log n τ n σ ≤c 3 θ t -θ 2 + (c 3 + c 4 )σ.

We require n ≥ cd log d c 2 4 τ . Also, according to Lemma 4, given

θ t -θ 2 ≤ c 3 c τ 1-τ min j∈[m] θ t - θ j 2 -1 -c3cτ 1-τ 2 σ (for c 3 ∈ (0, 1)), then with high probability, |S t \S | ≤ c3 c τ n.

Notice that for small τ , the noise should not be too large. Otherwise, even if θ t is very close to θ , because of the noise and the high density of bad samples, |S t \S | would still be quite large, and the update will not converge. We verify the performance of ILFB on mixed linear regression model via synthetic experiments. When constructing the dataset, we consider a special case where all bad samples are generated from a single β j . The parameters for both the good and bad components are generated randomly on a unit sphere. First, in Fig. 7 (left), we test the performance when τ varies in the interval [0.5, 0.8] with σ = 0.2. We compare:

(1) MLE: All samples are treated as good samples to find the best parameter;

(2) Oracle: learn from the τ n good samples given oracle access;

(3) Super-Oracle: learn from n samples given oracle access;

(4) R-Init+ILFB : ILFB with random initialization;

(5) M-Init+ILFB : ILFB using MLE as initialization.

The parameter recovery (y-axis) is measured by θ alg -θ 2 . We can see that ILFB with MLE as initialization performs better than the random initialization counterpart, which shows the effectiveness of taking good initailizations. Next, we show experimentally the speed of convergence in Fig. 7 (right) with multiple levels of measurement noise (in the small noise regime). The plots show linear convergence of each update step, which matches the result in Theorem 1.

C.2.2 ASYMPTOTIC PERFORMANCE:

Next, we check the performance of ILFB asymptotically. Our theory implies that the final recovery will get to a noise ball centered at the true parameter, but does not ensure the algorithm goes to the true parameter, even when sample size goes to infinity. In this section, we show experimentally that this noise ball guarantee is indeed tight, i.e., one should not expect ILFB to give exact recovery even in the infinite sample case.

Our experimental setting is as follows: we consider mixed linear regression with two components, where 60% of the samples comes from the interested component, and all x i s follow isotropic normal Gaussian distribution. The parameters for the two components are set as unit norm, and orthogonal to each other, with d = 10. We run ILFB for 15 iterations with τ set as 5% less than that of the true ratio. Number of samples varies from 100 to 51200. Standard deviation is calculated based on 100 runs for each experiment.

Fig. 8 provides the comparison between ILFB and oracle performance under different noise regime, i.e., σ = 0.1, 1, 10. We observe the performance of ILFB is close to the oracle in the small noise regime, while when the noise is comparable to the signal, there exists a gap between ILFB and the oracle, as the result of ILFB falls within the noise ball and stops decreasing, while the oracle will go to the exact solution asymptotically. Similar performance appears in the large noise regime, however, for n ≤ 51200, the gap between the two seems not too far apart, which is due to the dominance of the noise. For small noise (left plot), the performance of ILFB decreases along with the oracle performance. When the noise gets larger (middle plot), we observe a gap between ILFB and the oracle when sample size n increases. When the noise gets dominate the signal (right plot), the performance of ILFB and the oracle are not far apart for n ≤ 51200, but the gap will get larger asymptotically. Notice that for all experiments, the standard deviation of the true signal is 1.

C.3 INITIALIZATION FOR LINEAR REGRESSION MODEL:

Theorem 6 (initialization). Given the model described in (1), for some j

∈ [m], define d j m := min l∈[m]\{j} θ (j) -θ (l) 2 , if l∈[m]\{j} θ (j) -θ (l) 2 |S l | ≤ n κ d j m

holds for some κ. We have:

θ (j) -θ 0 2 ≤ 1.1 κ d j m

with high probability, where

θ 0 = θ OLS , n ≥ c max{ κ 2 dσ 2 (d j m ) 2 , mκ 2 log(mκ) (d j m ) 2 }.

The assumption in Theorem 6 requires the total sum of distances of the parameters for samples from other components should not be too large. For a fixed d j m , if the distance for some θ (l) becomes larger, it may become harder for the OLS estimator to be in the local region close to θ (j) . When the condition holds for some large κ, e.g., κ > 2.2(1 + 1-τ c1c3τ ) and σ < c1c3τ dm 2

√:

(1-τ ) 2 -c 2 1 c 2 3 τ 2 when C(τ ) < 1 (or for some large τ , κ > 2.2), following Theorem 1, the algorithm converges to a local O(σ) ball around θ (j) .

Proof. We write out the OLS estimator as follows:

θ OLS = X X -1 X y = X X -1 X (W Xθ + (I -W ) n + e) = X X -1 X (Xθ -(I -W )Xθ + (I -W )n + e) =θ -X X -1 X (I -W ) (Xθ -n) + X X -1 X e

Therefore, with high probability,

θ OLS -θ 2 ≤ m j=1 i∈S j bad X X -1 x i x i θ -θ (j) 2 + X X -1 X e 2 ≤ j∈[m] θ -θ (j) 2 • |S j bad | + c m(1 -τ )n log n n -c √ n log n + (d + c √ d log n)(n + c √ n log n) n -c √ n log n σ ≤ j∈[m] θ -θ (j) 2 • |S j bad | + c m(1 -τ )n log n n 1 + c log n n + 2(d + c √ d log n) √ n 1 + c log n n σ ≤ 1 κ d m + c m(1 -τ ) log n n + 2(d + c √ d log n) √ n σ 1 + c log n n (12) ≤ 1.1 κ d m , for n ≥ c max{ κ 2 dσ 2 d 2 m , mκ 2 log(mκ) d 2 m

}, where in (12), we use the assumption

j∈[m] θ - θ (j) 2 |S j bad | ≤ n κ min j∈[m] θ -θ (j) 2 .

D GAUSSIAN MIXTURE MODEL:

Similar to Section C, we refer to the targeted component as the 'good' component and the rest are 'bad' components. More speifically, S can be splitted into disjoint sets S = S good ∪S 1 bad ∪• • •∪S m bad , the samples follows:

x i ∼ N θ , σ 2 I , if i ∈ S good x i ∼ N θ (j) , σ 2 I , if i ∈ S j bad D.1 PROOF FOR UPDATE STEPS IN GAUSSIAN MIXTURE MODEL

Similar to the proof for linear regression setting, we use S t to denote the set of selected samples according to parameter θ t . Then,

EQUATION

)

Assume S ⊂ S good to be the set of good samples that are closest to θ , and |S | = |S t | = τ n. In other words, S is selected by growing a ball centered at θ , until τ n of the good samples fall into this ball, and we select them to be the set S . Accordingly, let

EQUATION

) With high probability, θ -θ 2 ≤ c √ dσ log n √ τ n = o(σ √ d). For i ∈ S bad ∩ S t , the norm of x i -θ t is small. More specifically, x i -θ t 2 ≤ x l -θ t 2 , ∀i ∈ S bad ∩ S t , ∀l ∈ S \S t .

For any good sample with index l, the value x l -θ t 2 ≤ x l -θ 2 + θ -θ t 2 by triangle inequality, where the square of 1 σ x l -θ 2 follows χ 2 (d) distribution. Denote B d (q) be the qquantile value of χ 2 (d) distribution, with high probability, the q-quantile of 1 σ x l -θ 2 for all good samples is bounded by 2 B d (q). Next, we have

θ t+1 -θ = 1 τ n   i∈St\S x i - i∈S \St x i   + θ -θ

which is based on the definition in ( 13) and ( 14). Then,

EQUATION

(15) makes an expansion for each term: the norm of x i -θ t for i ∈ S t \S should be small because of the selection rule, while the norm of x i -θ for i ∈ S \S t should be small because they are good samples. B d

|S ∩St| τ n:

= O(d). Inequality ( 16) splits ( 15) into 4 terms. The second term in ( 16) is bounded based on triangle inequality and the fact that if a sequence is element-wise larger than the other sequence, then the order statistics is also larger. For the second last term in (17), since the set S is selected by spanning a ball centered at θ , the distance to the center from any sample in set S is bounded by cσ √ d for some constant c. Therefore,

EQUATION

In order for (18) to converge, we expect |S \S t | < τ n/2. For τ ≥ 1 2 , given θ t -θ 2 ≤ 0.9 min j∈[m] θ t -θ j 2 , there exists c 1 ∈ (0, 1), such that |S \S t | ≤ c1 2 τ n with high probability (i.e., more than half of samples in S t are from the correct component). As a consequence,

EQUATION

For τ < 1 2 , in order to guarantee |S \S t | < τ n/2, we not only require θ t -θ 2 ≤ 0.9 min j∈[m] θ t -θ j 2 . This is because, the samples generated from θ may be a small fraction of the whole dataset (less than half), and when θ t is slighly closer to θ , it will still collect more bad samples because of the higher density. Intuitively, when σ is large enough, for any θ t ∈ R d , |S \S t | can be larger than τ n/2. Observe that the median of squared distance from the good samples to θ t (denoted as med good ) concentrates at the sample mean, which concentrates at the expected mean, which is θ t -θ 2 2 + σ 2 d. On the other hand, we require the number of bad samples whose squared distance to θ t is less than med good is less than τ n/2, which corresponds to the τ 2(1-τ ) -quantile value to be greater than med good . Therefore, a valid θ t should satisfy:

P σ 2 n n + 2σn (θ t -θ (j) ) < θ t -θ 2 2 -θ t -θ (j) 2 2 + σ 2 d ≤ τ 2(1 -τ ) ,

where n ∼ N (0, I d ) is a normal Gaussian vector. By sub-exponential inequality, and reorganizing the terms, a sufficient condition we require is θ

t -θ 2 ≤ min j∈[m] θ t -θ j 2 -c log 2(1-τ ) τ

σ. This condition essentially implies a √ log kσ separation distance, which is the lower bound for computationally efficient algorithm to learn a Gaussian mixture model according to Regev & Vijayaraghavan (2017) .

We also want to point out that this pheonema of non-exact recovery when the noise is large is not a problem introduced by our algorithm. In fact, for a series of work on learning Gaussian mixture models (estimating the means given identity covariance matrix), a separation between every pair of mixture components is required in order to learn in polynomial time (notice that this polynomial time is usually much larger compared to our algorithm which is near-linear). For Fig. 10 (middle and right), this separation requirement is clearly not satisfied. For small noise (left plot), the performance of ILFB decreases along with the oracle performance. When the noise gets larger (middle plot), we observe a gap between ILFB and the oracle when sample size n increases. When the noise gets dominate the signal (right plot), the performance of ILFB and the oracle are not far apart for n ≤ 51200, but the gap will get larger asymptotically.

D.3 INITIALIZATION FOR GAUSSIAN MIXTURE MODEL:

We present a performance guarantee of the simple initialization step, which takes the average over all the samples. More specifically, we show that the initialization will be closer to the dominant component under mild assumptions. Theorem 7 (initialization). Given a dataset D generated following (2), for a certain j, define d j m := min l∈[m]\{j} θ (j) -θ (l) 2 . Consider taking the overall mean as the initialization θ 0 , then, if l∈[m]\{j} (θ (j) -θ (l) )|S l | 2 ≤ αnd j m , and n ≥ cdσ 2 ( 9 19 -α) 2 (d j m ) 2 , we have θ 0 -θ (j) 2 ≤ 0.9 min l∈[m]\{j} θ 0 -θ (l) 2 with high probability.

Proof. Assume x i .

We have with high probability, . This will imply θ 0 -θ 2 ≤ 0.9 min j∈[m] θ 0 -θ (j) 2 . Experimental settings: In this section, we present additional experimental results, in order to verify the performance of ILFB under different parameter settings, and compare with other algorithms. More specifically, we present the results using the following methods/algorithms:

θ 0 -θ 2 = 1 n n i=1 x i -θ 2 = 1 n   i∈S good x i -θ + i∈S bad x i -θ   2 ≤ 1 n j∈[m]

E MORE EXPERIMENTAL RESULTS:

• Baseline: naive trainig using all the samples;

• ILFB : our proposed iterative learning algorithm with 5 iterations, using a mis-specified τ which is 5% less than the true value; • Centroid: using the centroid of the input data to filter out outliers. For classification task, we calculate the centroids for the samples with the same label/class and filter each class separately; • 1-Step: ILFB algorithm with a single iteration;

• ∆τ = τ -τ ∈ {10%, 15%, 20%}: ILFB under different mis-specified τ value, under the following three problem settings:

• Classification with systematic error;

• MNIST generation with Fashion-MNIST images ;

• Classification with random label error.

For classification tasks (Table 4 and Table 6 ), we show the best accuracy on the validation set. For the generation task (Table 5 ), we present the ratio of true MNIST samples selected by each method. For the baseline method, since the DC-GAN is trained using all samples, the reported value is exactly the τ .

Results: Table 4 shows the performance under systematic error, for τ varies from 60% to 90%. ILFB not only performs better than the baseline, but also outperform the centroid method by a large margin, especially when the dataset is noisy (τ is small). By comparing ILFB with its 1-step counterpart, we see the benefit brought by doing the iterative updating is also significant. Table 5 shows the performance of generation quality under different noise levels. We observe that centroid method does not work, which may due to the fact that all MNIST and Fashion-MNIST images are hard to be distinguished as two clusters in the pixel space. Notice that there are in fact 20 clusters (10 from MNIST, and 10 from Fashion-MNIST), and we are interested in 10 of them. ILFB works well since it automatically learns a clustering rule when generating on the noisy dataset. For example, for τ = 80%, even with a mis-specified τ = 60%, ILFB is capable of ignoring almost all bad samples. Again, we also observe significant improvement of ILFB over its 1-step counterpart. In Table 6 , we show the performance of ILFB in the random error setting. Again, ILFB performs much better in the extremely noisy setting.

We also have results showing that ILFB works well for generation when the corrupted samples are pure Gaussian noise. However, we do not think it is a practical assumption, and the result is not presented here.

:

https://github.com/carpedm20/DCGAN-tensorflow

Our framework sounds initially similar to EM-style algorithms like k-means. Note however that EM needs to postulate a model for all the data points, while we search over a subset and do not worry about the loss on corrupted points. We are alternating between a simple search over subsets and a fitting problem on only the selected subset; this is not an instance of EM.

follow the implementation in https://mxnet.incubator.apache.org/tutorials/python/mnist.html

cifar wideresnet16 10 from the online model zoo: https://gluon-cv.mxnet.io/api/model zoo.html

We use the coarse labels as the classification target

WideResNet: depth 28, width factor 10, dropout rate 0.3

Notice that for different GAN architectures, the loss function for training the discriminator varies, however, we can always find a surrogate loss by modifying the original loss function, and use the loss of the discriminator for real images as the surrogate loss for ILFB .

Figures and Tables:

(a) MNIST LeCun et al. (1998) dataset with a standard 2-layer CNN 3 (b) CIFAR-10 Krizhevsky & Hinton (2009) with a 16-layer WideResNet 4 Zagoruyko & Komodakis (2016) (c) CIFAR-100 5 with a 28-layer WideResNet 6 In each of these cases, the neural network has excellent performance when there are no label errors in training; this degrades significantly as the fraction of spurious samples increases. Algorithm In each case, the algorithm involves first training the NN on all the samples, and then iteratively alternating between (a) picking the fraction τ of samples in each label class with the lowest cross-entropy loss under the current θ, and (b) retraining the model from scratch with these picked samples, to get a new θ. Training was done on MXNet. Mapping back to the development in Section 3, here θ represents the weights of the neural network, and f θ (s) is the standard crossentropy loss used in training.

Figure1: Qualitative performance of ILFB for GANs: We apply ILFB to a dataset of 80% MNIST "good" images + 20% Fashion-MNIST "bad". The panels show the fake images from 32 randomly chosen (and then fixed) latent vectors, as ILFB iterations update the GAN weights. Baseline is the standard training of fitting to all samples. We can see that the baseline generates both digit and fashion images, but by the 5th iteration it hones in on digit images.

Figure 2: Qualitative performance of ILFB for GANs: Given training data consisting of 70%CelebA "good" images + 30% CIFAR-10 "bad" images, the four panels above each show the performance after iterations of our ILFB algorithm. First we choose 18 random vectors in latent pace, and fix them for all iterations. In each iteration, we retrain the GAN on corresponding selected samples to get new weighs, which are then used to generate the 18 fake images. Baseline refers to the standard training where we fit to all the samples (this is also our initialization). Visually, we can see that the generator is able to improve its generation quality and only generate face-like images after the 5th iteration.

Figure 3: Illustrative failure case:This figure shows that when the fraction of "bad" samples is too large, ILFB cannot clean them out. The setting is exactly the same as in Figure1, but now with 60% MNIST "good" images + 40% Fashion-MNIST "bad" images. We can see that now the 5 th iteration still retains the fake fashion images. Please see the discussion section for some intuition on this.

Figure 5: Effect of mis-specification for mixed linear regression

Figure 6: Consistency of ILFB linear regression under different noise levels (σ = 0.1, 1, 10 from left to right).

Figure 7: Left: 2 loss of recovered parameter to the true parameter for (a) MLE: naive MLE/OLS estimator; (b) Oracle: MLE estimator for the subset of good samples; (c) Super-Oracle: MLE estimator for the whole set of samples given the correct output for bad samples; (d) R-Init+ILFB: our algorithm with random initialization; (e)M-Init+ILFB: our algorithm with MLE as initialization. σ = 0.2, systematic error setting. Right: Speed of convergence under systematic error setting, number of good samples is set as 600. M-Init: ILFB using MLE initialization; R-Init: ILFB using random initialization.

Figure8: Performance of ILFB for mixed linear regression under different noise levels (σ = 0.1, 1, 10 from left to right). For small noise (left plot), the performance of ILFB decreases along with the oracle performance. When the noise gets larger (middle plot), we observe a gap between ILFB and the oracle when sample size n increases. When the noise gets dominate the signal (right plot), the performance of ILFB and the oracle are not far apart for n ≤ 51200, but the gap will get larger asymptotically. Notice that for all experiments, the standard deviation of the true signal is 1.

Figure10: Performance of ILFB for Gaussian mixture model under different noise levels (σ = 0.1, 1, 10 from left to right). For small noise (left plot), the performance of ILFB decreases along with the oracle performance. When the noise gets larger (middle plot), we observe a gap between ILFB and the oracle when sample size n increases. When the noise gets dominate the signal (right plot), the performance of ILFB and the oracle are not far apart for n ≤ 51200, but the gap will get larger asymptotically.

j∈[m] (θ -θ (j) )|S j bad | αn min j∈[m] θ -θ (j)2 . Consider the initialization

Algorithm 1 ILFB Update 1: input: samples {s i } n i=1 , fraction τ , max. iteration number T 2: (optional) initialize: set t ← 0 and initially fit all samples θ 0 ← arg min θ i∈[n] f θ (s i ), 3: while t < T do

Table content: <table><tr><td>4:</td><td colspan="3">calculate current losses f θt (s i ) for all samples s i , i ∈ [n]</td></tr><tr><td>5:</td><td>find new best set of samples</td><td/></tr><tr><td/><td>S t ← arg min S:|S|=τ n</td><td>i∈S</td><td>f θt (s i )</td></tr><tr><td/><td colspan="3">by sorting them according to losses f θt (s i ) and choosing the ones with smallest losses.</td></tr><tr><td>6:</td><td>fit a model for this new set</td><td/></tr><tr><td/><td>θ t+1 ← arg min θ</td><td>i∈St</td><td>f θ (s i )</td></tr><tr><td>7:</td><td/><td/></tr></table>

Classification with systematic label error: Performance for MNIST, CIFAR-10, CIFAR-100 datasets as the ratio of good samples varies from 60% to 90%. Here Baseline : Naive training using all the samples; ILFB : Our iterative update algorithm; Oracle : Training with all good samples. We see significant improvement of ILFB over Baseline for all the settings.

Table content: <table><tr><td>dataset</td><td/><td>MNIST</td><td/><td/><td>CIFAR-10</td><td/><td/><td>CIFAR-100</td><td/></tr><tr><td># good # total</td><td colspan="2">Baseline ILFB</td><td colspan="3">Oracle Baseline ILFB</td><td colspan="3">Oracle Baseline ILFB</td><td>Oracle</td></tr><tr><td>60%</td><td>70.26</td><td>90.00</td><td>94.30</td><td>64.63</td><td>75.16</td><td>91.26</td><td>58.28</td><td>65.25</td><td>80.39</td></tr><tr><td>70%</td><td>85.95</td><td>92.09</td><td>94.50</td><td>71.05</td><td>86.09</td><td>92.25</td><td>66.75</td><td>73.83</td><td>81.65</td></tr><tr><td>80%</td><td>92.62</td><td>94.30</td><td>94.61</td><td>78.84</td><td>89.14</td><td>92.85</td><td>72.68</td><td>78.70</td><td>82.50</td></tr><tr><td>90%</td><td>93.88</td><td>94.41</td><td>94.92</td><td>84.12</td><td>91.03</td><td>93.47</td><td>78.12</td><td>81.10</td><td>83.41</td></tr></table>

we focus on recovering the parameters of one mixture component from the mixed linear regression model, we refer to the targeted component as the 'good' component, and the rest are 'bad' components. More specifically, the full set of samples S = [n] can be splitted into a set of "good" samples S good , and m sets of "bad" samples ∪ j∈[m] S j bad . The response variables y i are given by:

Table content: <table><tr><td>good # total</td><td>60%</td><td>70%</td><td>80%</td><td>90%</td></tr><tr><td>Baseline</td><td colspan="4">70.26 85.95 92.62 93.88</td></tr><tr><td colspan="5">Random Initialization + ILFB 82.05 91.48 93.80 93.79</td></tr><tr><td>ILFB</td><td colspan="4">90.00 92.09 94.30 94.41</td></tr><tr><td colspan="5">Table 3: MNIST-5% dataset with systematic label error using ILFB with different initialization</td></tr><tr><td colspan="5">methods. The accuracy at the 5-th iteration is shown for both initialization methods. Results are</td></tr><tr><td>averaged over 5 runs.</td><td/><td/><td/><td/></tr><tr><td>C LINEAR REGRESSION MODEL</td><td/><td/><td/><td/></tr></table>

MNIST classification: comparison with other choices

Table content: <table><tr><td colspan="2">dataset</td><td/><td/><td/><td>MNIST</td><td/><td/></tr><tr><td>τ =</td><td># good # total</td><td colspan="2">Baseline ILFB</td><td colspan="5">Centroid 1-Step ∆τ = 10% ∆τ = 15% ∆τ = 20%</td></tr><tr><td>60%</td><td/><td>70.26</td><td>90.00</td><td>74.52</td><td>78.48</td><td>88.24</td><td>86.48</td><td>84.49</td></tr><tr><td>70%</td><td/><td>85.95</td><td>92.09</td><td>88.47</td><td>89.31</td><td>90.83</td><td>89.19</td><td>88.10</td></tr><tr><td>80%</td><td/><td>92.62</td><td>94.30</td><td>92.79</td><td>92.78</td><td>92.78</td><td>90.17</td><td>88.63</td></tr><tr><td>90%</td><td/><td>93.88</td><td>94.41</td><td>94.32</td><td>93.94</td><td>92.88</td><td>91.21</td><td>89.90</td></tr><tr><td/><td/><td colspan="6">Table 5: MNIST GAN: comparison with other choices</td></tr><tr><td colspan="2">dataset</td><td/><td/><td/><td>MNIST</td><td/><td/></tr><tr><td>τ =</td><td># good # total</td><td colspan="2">Baseline ILFB</td><td colspan="5">Centroid 1-Step ∆τ = 10% ∆τ = 15% ∆τ = 20%</td></tr><tr><td>70%</td><td/><td>70</td><td>97.00</td><td>61.46</td><td>77.77</td><td>83.33</td><td>78.06</td><td>83.59</td></tr><tr><td>80%</td><td/><td>80</td><td>100.00</td><td>77.46</td><td>76.84</td><td>98.80</td><td>99.56</td><td>97.77</td></tr><tr><td>90%</td><td/><td>90</td><td>100.00</td><td>89.57</td><td>91.90</td><td>98.85</td><td>99.01</td><td>98.04</td></tr></table>

MNIST classification with random error.

Table content: <table><tr><td colspan="2">dataset</td><td/><td/><td/><td>MNIST</td><td/><td/></tr><tr><td>τ =</td><td># good # total</td><td colspan="2">Baseline ILFB</td><td colspan="5">Centroid 1-Step ∆τ = 10% ∆τ = 15% ∆τ = 20%</td></tr><tr><td>30%</td><td/><td>82.74</td><td>87.88</td><td>82.72</td><td>85.17</td><td>85.30</td><td>75.14</td><td>61.52</td></tr><tr><td>50%</td><td/><td>90.57</td><td>91.80</td><td>91.00</td><td>91.48</td><td>90.43</td><td>87.37</td><td>78.21</td></tr><tr><td>70%</td><td/><td>93.04</td><td>92.40</td><td>93.47</td><td>92.55</td><td>91.14</td><td>89.39</td><td>87.90</td></tr><tr><td>90%</td><td/><td>93.98</td><td>93.93</td><td>94.14</td><td>93.58</td><td>92.32</td><td>90.61</td><td>89.95</td></tr></table>

Peer review (iclr2019):
 The authors propose an iterative method for discarding outlying training data: first, learn a model on the entire training dataset; second, identify the training examples that have high loss under the learned model; and then alternate between re-learning the model on the training examples that do not have high loss, and re-identifying the training examples with high loss under the new model. This method works for both supervised and unsupervised learning, and the authors show that in theory, their method has some convergence properties in the mixed linear regression and Gaussian mixture model settings. The authors also run some experiments on neural networks and datasets with synthetic noise to show the benefits of their proposed method. The problem of noisy datasets is relevant to almost all machine learning problems in the real world, and the authors* method shows promise as a straightforward way to increase performance on such noisy data. However, my opinion is that the authors need to make a stronger case, theoretically and/or experimentally, for why their method should be preferred to other methods. Detailed comments follow. == Experiments == 1) No comparisons are provided to other outlier detector methods (e.g., based on nearest neighbors, distance to centroid, influence functions, etc.) or techniques that also purport to deal with noisy labels (e.g., by modifying the learning algorithm or loss function). While there are too many existing methods to expect the authors to benchmark against all of them, it*s important to at least have a couple of representative comparisons. 2) It*d be nice to have an ablative analysis to tease out the factors behind the gain in accuracy. For example, is the iteration important, or would a single pass suffice? How robust is the algorithm to tau, the fraction of data to discard? (The authors do test initializing randomly vs. initializing on the full dataset.) 3) The systematic label noise scenario seems to favor the authors* method (though the authors claim that it is a harder scenario than random label noise). It*d be helpful to see if the method works against random noise. == Theory == 4) The assumptions seem very restrictive. For example, for mixed linear regression (section 4), the features of all examples are assumed to be drawn i.i.d. from an isotropic Gaussian (so even the bad samples are drawn from the same distribution as the good samples; and all features are independent). To my knowledge, this is not a "standard and widely studied" assumption. For the Gaussian mixture model (section 5), a similar isotropic Gaussian assumption is made for each mixture. 5) Beyond the independence assumptions mentioned above, the initialization results make additional assumptions on the "bad" data (e.g., average distance of the good vs. bad parameters) that I found hard to parse. How strong are these assumptions? Do they hold on real datasets? 6) The convergence results (Theorems 1 and 3) have a constant term sigma in them. This is surprising and seems to me to considerably weaken the result -- one would expect that the dependence on sigma will decrease with n. I think either a strong experimental or strong theoretical section would be sufficient for me to recommend acceptance. However, the paper currently shows potentially interesting experimental/theoretical results but does not do a comprehensive job of either side.