Year: 2018

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.

text: 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.

heading: 1 INTRODUCTION
text: 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 images 1, 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.
1https://github.com/carpedm20/DCGAN-tensorflow 2Our 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.
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 (xi, yi) increases as its squared error (yi − 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.

heading: OUR RESULTS AND PAPER OUTLINE
text: 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.

heading: 2 RELATED WORK
text: 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. Fré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 l0 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.

heading: 3 ITERATIVELY LEARNING FROM THE BEST ( ILFB )
text: 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 s1, · · · , sn, using which we want to train a model parameterized by θ ∈ Rd. 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θ(si).
We do this by alternating between finding S and finding θ, as described below in Alg. 1.
Algorithm 1 ILFB Update 1: input: samples {si}ni=1, fraction τ , max. iteration number T 2: (optional) initialize: set t← 0 and initially fit all samples θ0 ← arg minθ ∑ i∈[n] fθ(si),
3: while t < T do 4: calculate current losses fθt(si) for all samples si, i ∈ [n] 5: find new best set of samples
St ← arg min S:|S|=τn ∑ i∈S fθt(si)
by sorting them according to losses fθt(si) and choosing the ones with smallest losses. 6: fit a model for this new set
θt+1 ← arg min θ ∑ i∈St fθ(si)
7: 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.

heading: 4 ILFB FOR MIXED LINEAR REGRESSION
text: 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 si = (xi, yi) with features xi ∈ Rd and responses yi ∈ R, and θ ∈ Rd 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 (xi, yi), with features xi ∼ N (0, Id) being standard gaussians in d dimensions. The full set of samples S = [n] can be splitted into m sets S = ∪j∈[m]Sj , each corresponding to samples that generate from one mixture component, |Sj | = τ?j n. The response variables yi are given by:
yi = x > i θ (j) + i, for i ∈ Sj (1)
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(τ) minl∈[m]\{j} ‖θt − θ(l)‖2 − √
1− C2(τ)σ, where C(τ) = min{ c1c3τ1−τ , 1}.
Then, the next iterate θt+1 of the algorithm satisfies
‖θt+1 − θ(j)‖2 ≤ c1‖θt − θ(j)‖2 + (c1 + c2)σ
with high probability (i.e., with probability 1− n−c0 ), provided the number of samples n ≥ cd log d c22τ , where c1 ∈ (0, 1), c, c0, c2, c3 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.

heading: 5 ILFB FOR GAUSSIAN MIXTURE MODEL
text: In this section, we describe ILFB applied to the setting of Gaussian mixture model, and provide statistical guarantees on its performance.
Algorithm The samples si = xi are points in Rd, θ ∈ Rd is the mean we want to estimate, and fθ(x) is proportional to the negative log-likelihood, i.e., fθ(x) = ‖x − θ‖22. 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 = {xi | i ∈ S = {1, · · · , n}}, where S can be splitted into disjoint sets S = ∪j∈[m]Sj , |Sj | = τ?j n. The samples are generated following:
xi ∼ N ( θ(j), σ2I ) , for i ∈ Sj . (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 minl∈[m]\{j} ‖θt − θ(l)‖2 − c3σ √
log 2(1−τ)τ 1{τ< 12}
then, with high probability (i.e., with probability 1− n−c0 ),
‖θt+1 − θ(j)‖2 ≤ c1‖θt − θ(j)‖2 + c2 √ dσ,
where c1 ∈ (0, 1), c0, c2, c3 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 τ < 12 , 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.

heading: 6 ILFB FOR DEEP IMAGE CLASSIFICATION WITH SYSTEMATIC TRAINING LABEL ERROR
text: 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: (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.
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/CIFAR10/CIFAR-100, respectively. The learning rate is divided by 5 at the 50-th epoch and each ex-
3follow the implementation in https://mxnet.incubator.apache.org/tutorials/python/mnist.html 4cifar wideresnet16 10 from the online model zoo: https://gluon-cv.mxnet.io/api/model zoo.html 5We use the coarse labels as the classification target 6WideResNet: depth 28, width factor 10, dropout rate 0.3
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.

heading: 7 ILFB FOR DEEP GENERATIVE MODELS WITH MIXED TRAINING DATA
text: 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
7Notice 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 .
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.
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.15nMNIST 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.

heading: 8 DISCUSSION
text: 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” fashionMNIST 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.

heading: A EFFECT OF MIS-SPECIFICATION

heading: A.1 MIS-SPECIFICATION FOR A CLEAN DATASET
text: 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 θ? ∈ Rd 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.

heading: A.2 MIS-SPECIFICATION FOR A NOISY DATASET
text: 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.

heading: B RANDOM INITIALIZATION FOR CLASSIFICATION
text: 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.

heading: C LINEAR REGRESSION MODEL
text: Since 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 Sgood, and m sets of “bad” samples ∪j∈[m]Sjbad. The response variables yi are given by:
yi =
{ x>i θ
? + i, if i ∈ Sgood x>i θ (j) + i, if i ∈ Sjbad
where i ∼ N (0, σ2) is the additive noise, and θ? as well as all the θ(j) are assumed to be unit norm vectors.

heading: C.1 PROOF FOR UPDATE STEPS IN LINEAR REGRESSION MODEL
text: For simplicity of the notation, we present the proof by assuming yi for bad samples have the form yi = ni + ei, where ni corresponds to x>i θ
(j), such that i ∈ Sjbad. Let θt be the current learned parameter. θt+1 is learned by using one iteration in Algorithm 1. Namely, we first select a subset St of size τn with the smallest loss (yi − x>i θt)2, then re-calculate the MLE estimator only using those samples. Denote Wt as the diagonal matrix whose diagonal entry Wii equals 1 when the i-th sample is in set St, otherwise equals 0. Then,
θt+1 = ( X>WtX )−1 X>Wty, (3)
where we used the fact that W2t = Wt. Notice that W ? is the ground truth for Wt (accordingly, define S? for the ground truth of St). 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 ∈ Sbad, ni = x>i θ(j) for some j ∈ [m]. Therefore,
‖θt+1 − θ?‖2 = ( X>WX )−1 X> (WW? −W) (Xθ? −Xθt + Xθt − n− e) + ( X>WX )−1 X>WW?e
≤ ∥∥∥(X>WX)−1∥∥∥
2︸ ︷︷ ︸ T1
· ∥∥X> (WW? −W) (Xθ? − n− e)∥∥
2︸ ︷︷ ︸ T2
+ ∥∥∥(X>WX)−1 X>WW?e∥∥∥
2︸ ︷︷ ︸ T3
(4)
We bound the three terms on the right hand side of (4) separately.

heading: Helpful lemmas
text: Lemma 3 (Sub-Gamma property for the q-quantile). Let n ≥ 3, letX(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 vn = 8qn log 2 . For all 0 ≤ λ < qn 2 √ vn ,
log E [ eλ(X(qn)−E[X(qn)]) ] ≤ vnλ 2
2 ( 1− 2λ √
vn qn ) (5) This shows the sub-gamma property ofX(qn), and as a result, for all t > 0, and constant 12 < q < 1,
E [ X(qn) ] = ψ−1
( 1− q
2
) (6)
P [∣∣X(qn) − E [X(qn)]∣∣ ≥√2c1vn log n+ 2c1√ vn
qn log n
] ≤ n−c1 . (7)
This result is generalized from the result in Boucheron et al. (2012).
Lemma 4. Suppose we have two Gaussian distributions D1 = N (0,∆2),D2 = N (0, 1). We have fn i.i.d. samples fromD1 and (1−f)n i.i.d. samples fromD2. Denote the set of the top f̄n samples with smallest abstract values as Sf̄n, where f̄ ≤ f . Then, with high probability, for ∆ ≤ 1, at most( cmax { ∆ (1− f)n √ log n, log n }) samples in Sf̄n are from D2.
Proof of Lemma 4. First, let us consider the probability of a random variable from D2 has smaller abstract value than a random variable fromD1. This would give us a rough idea about the occupancy of the samples from D2 in the top set. Denote the two variables from D1,D2 as u1, u2 respectively. Then, with basic calculations, we have
P [|u2| ≤ |u1|]
= ∫ ∞ 0 P [|u1| ≥ s] 2√ 2π e− s2 2 ds
≤ ∫ ∞
0
2e− s2 2∆2 2√ 2π e− s2 2 ds
=2 ∆√
1 + ∆2 .
This calculation implies that if given same number of samples from D1 and D2, it is reasonable to expect that only around 2∆ fraction of the top set samples are from D2, when ∆ is small. In the original setting where we have f̄n samples from D1 and ( 1− f̄ ) n from D2, we should expect around 2∆ 1−f̄ f̄ f̄n = 2∆ ( 1− f̄ ) samples in the top set are from D2.
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 D1, and then, we show the high probability upper bound for the number of samples from D2 that are less than the maximum value.
Step I – the sample with maximum abstract value from D1. We know that for random normal i.i.d. Gaussian variables xi, i ∈ [n],
P [ max i∈[n] |xi| ≥ √ 2 log 2n+ t ] ≤ 2e− t 2 2 .
Therefore, for fn samples from D1, with high probability, the maximum abstract value is in the order of O( √ log n∆).
Step II. On the other hand, for a random u2 ∼ D2, we know that for small positive values δ = c √ log n∆, P [|u2| ≤ δ] ≤ √ 2 π δ gives a tight upper bound. LetMδ,i be the event sample ui from
D2 has abstract value less than δ, and a Bernoulli random variablemi,δ that is the indicator of event Mδ,i holds or not. Then,
E (1−f)n∑ i=1 mi,δ  ≤√ 2 π δ (1− f)n.
For independent random variable xis, i ∈ [ñ] that lie in interval [0, 1], with X = ∑ i xi 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 mi,δs, we have
P (1−f)n∑ i=1 mi,δ ≥ (1 + γ) √ 2 π δ (1− f)n  ≤ e− γ2√ 2π δ(1−f)n3 , ∀γ ∈ [0, 1] P
(1−f)n∑ i=1 mi,δ ≥ (1 + γ) √ 2 π δ (1− f)n  ≤ e− γ√ 2π δ(1−f)n3 , ∀γ > 1. For the first case, where γ ∈ [0, 1], we can set γ = c √ logn
δ(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 lognδ(1−f)n .
Combining Step I and Step II. To summarize, for some fixed constant c, with high probability:
• For ∆ > c √
logn n , at most 2cδ (1− f)n = c √ log n∆ (1− f)n samples in Sf̄n are from
D2.
• For ∆ ≤ c √
logn n , at most (1 + γ) δ (1− f)n = c log n samples in Sf̄n are from D2.
Lemma 5. Assume τ < τ? ( τ/τ? = cτ < 1 is a constant), with high probability, we have: σmin ( X>WX ) ≥c0|St ∩ S?|+ ∑ j∈[m] cj |St ∩ Sj | ≥ cτn, (8)
where c0, · · · , cm, 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 xix > i 1 [li,t ∈ arg τn- min (l1,t, · · · , ln,t)]
= ∑ i xix > i 1 [li,t ∈ arg τn- min (l1,t, · · · , ln,t)] 1 [i ∈ S?]
+ ∑ j∈[m] ∑ i xix > i 1 [li,t ∈ arg τn- min (l1,t, · · · , ln,t)] 1 [ i ∈ Sj ] (9)
where 1[·] is the indicator function. Note that the values {li,t}ni=1 are defined as: li,t = ( yi − x>i θt )2 .
More specifically, consider the model setting, we have: li,t = [ x>i (θ ? − θt) + i ]2 , i ∈ S?
li,t = ( x>i (θ j − θt) + i )2 , i ∈ Sj , j ∈ [m]
For all i ∈ S?, li,ts have the same distribution as δµ, where µ is a χ2(1) random variable, and δ is the magnitude δ = ‖θ? − θt‖22 + σ2. The bad samples i ∈ [n]\S?, for i ∈ S j bad have the same distribution as (σ2 + ‖θ(j) − θt‖22)µ. 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 c1 such that the separation value for deciding top-τn or not is lower bounded by cδ with high probability. For a fixed c0, we consider the following quantity:
Σ(c0) = E [ xix > i | |x>i (θ? − θt) + i| ≤ c0 √ ‖θ? − θt‖22 + σ2 ] .
By the geometry of the constraint, we have that σmin (Σ (c)) ≥ ∫ c −c s2 1√ 2π e− s2 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 2c0 (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 xix > i 1 [li,t ∈ arg τn- min (l1,t, · · · , ln,t)] 1 [i ∈ S?] ) ≥ c0 2 |St ∩ S?| ,
Similarly, since ‖θj − θt‖ ≤ 3, we have a lower bound O(|St ∩Sj |) for i ∈ St ∩Sj as well, as long as the set |St ∩ Sj | ≥ c log2 n. In any case, we have the minimum eigenvalue is lower bounded by cτn.
T2 in (4) T2 can be bounded as follows:
T 22 = ∥∥∥∥∥∥ ∑
i∈St\S?
( x>i θ ? − ni − ei ) xi ∥∥∥∥∥∥ 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) − ek )2
≤σ ( (W −WW?)XX>(W −WW?) ) ∑ j∈[m] ∑ k∈St∩S(j)\S? [( x>k (θ ? − θt) )2 + ( x>k (θt − θ(j))− ek )2] ≤σ ( (W −WW?)XX>(W −WW?)
)2 ‖θt − θ?‖22 + cσ ( (W −WW?)XX>(W −WW?) ) |St\S?| ( ‖θt − θ?‖22 + σ2
) ≤c|St\S?|2 ( ‖θt − θ?‖22 + σ2
) for |St\S?| ≥ c log2 n (when |St\S?| < c log2 n, the final convergence result still holds true). As a consequence,
T2 ≤c|St\S?|(‖θt − θ?‖2 + σ). (10)
T3 in (4) For this part, we can reuse the result we proved for T1. 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 ′|St\S?|(‖θt − θ?‖2 + σ) τn + c √ nd log n τn σ ≤c3‖θt − θ?‖2 + (c3 + c4)σ.
We require n ≥ cd log d c24τ . Also, according to Lemma 4, given ‖θt − θ?‖2 ≤ c3c τ1−τ minj∈[m] ‖θt − θj‖2 − √ 1− ( c3cτ 1−τ )2 σ (for c3 ∈ (0, 1)), then with high probability, |St\S?| ≤ c3c′ τ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, |St\S?| would still be quite large, and the update will not converge.

heading: C.2 SIMULATIONS
text: C.2.1 ILFB ON MIXED LINEAR REGRESSION
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.

heading: C.2.2 ASYMPTOTIC PERFORMANCE
text: 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 xis 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.
C.3 INITIALIZATION FOR LINEAR REGRESSION MODEL
Theorem 6 (initialization). Given the model described in (1), for some j ∈ [m], define djm := minl∈[m]\{j} ‖θ(j) − θ(l)‖2, if ∑ l∈[m]\{j} ‖θ(j) − θ(l)‖2|Sl| ≤ n κd j m holds for some κ. We have:
‖θ(j) − θ0‖2 ≤ 1.1
κ djm
with high probability, where θ0 = θOLS, n ≥ cmax{κ 2dσ2 (djm)2 , mκ 2 log(mκ) (djm)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 djm, 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−c21c23τ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∈Sjbad ( X>X )−1 xix > 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
κ dm + c
√ m(1− τ) log n
n +
√ 2(d+ c
√ d log n)√
n σ
)( 1 + c √ log n
n
) (12)
≤1.1 κ dm,
for n ≥ cmax{κ 2dσ2 d2m , mκ 2 log(mκ) d2m }, where in (12), we use the assumption ∑ j∈[m] ‖θ? − θ(j)‖2|Sjbad| ≤ n κ minj∈[m] ‖θ ? − θ(j)‖2.

heading: D GAUSSIAN MIXTURE MODEL
text: 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 = Sgood∪S1bad∪· · ·∪Smbad, the samples follows:
xi ∼ N ( θ?, σ2I ) , if i ∈ Sgood
xi ∼ N ( θ(j), σ2I ) , if i ∈ Sjbad

heading: D.1 PROOF FOR UPDATE STEPS IN GAUSSIAN MIXTURE MODEL
text: Similar to the proof for linear regression setting, we use St to denote the set of selected samples according to parameter θt. Then,
θt+1 = 1
τn ∑ i∈St xi. (13)
Assume S? ⊂ Sgood to be the set of good samples that are closest to θ?, and |S?| = |St| = τ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
θ̄ = 1
τn ∑ i∈S? xi. (14)
With high probability, ‖θ̄ − θ?‖2 ≤ c √ dσ logn√ τn = o(σ √ d). For i ∈ Sbad ∩ St, the norm of xi − θt is small. More specifically,
‖xi − θt‖2 ≤ ‖xl − θt‖2 ,∀i ∈ Sbad ∩ St,∀l ∈ S ?\St.
For any good sample with index l, the value ‖xl − θt‖2 ≤ ‖xl − θ?‖2 + ‖θ? − θt‖2 by triangle inequality, where the square of 1σ‖xl − θ
?‖2 follows χ2(d) distribution. Denote Bd(q) be the qquantile value of χ2(d) distribution, with high probability, the q-quantile of 1σ‖xl − θ
?‖2 for all good samples is bounded by 2 √ Bd(q). Next, we have
θt+1 − θ? = 1
τn  ∑ i∈St\S? xi − ∑ i∈S?\St xi + (θ̄ − θ?) which is based on the definition in (13) and (14). Then, ‖θt+1 − θ?‖2
= 1
τn ∥∥∥∥∥∥ ∑ i∈St\S? (xi − θt + θt)− ∑ i∈S?\St (xi − θ? + θ?) + ( θ̄ − θ? )∥∥∥∥∥∥ 2
(15)
≤ 1 τn |S?\St| ‖θ? − θt‖2 + ∥∥∥∥∥∥ ∑ j∈[m] ∑ i∈Sjbad∩St (xi − θt) ∥∥∥∥∥∥ 2 + ∥∥∥∥∥∥ ∑ i∈S?\St xi − θ? ∥∥∥∥∥∥ 2 + ∥∥θ̄ − θ?∥∥2 (16)
≤ 1 τn
|S?\St| ‖θ? − θt‖2 + |St\S?| ( ‖θt − θ?‖2 + 2σ √ Bd( |St ∩ S?| τ?n ) ) + ∥∥∥∥∥∥ ∑
i∈S?\St
xi − θ? ∥∥∥∥∥∥
2
+ ∥∥θ̄ − θ?∥∥ 2
(17)
(15) makes an expansion for each term: the norm of xi − θt for i ∈ St\S? should be small because of the selection rule, while the norm of xi−θ? for i ∈ S?\St should be small because they are good samples. Bd ( |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,
‖θt+1 − θ?‖2 ≤ 2|S?\St| τn ‖θ? − θt‖2 + c|S?\St| τn σ √ d+ c log n√ τn σ √ d. (18)
In order for (18) to converge, we expect |S?\St| < τn/2. For τ? ≥ 12 , given ‖θt − θ ?‖2 ≤ 0.9 minj∈[m] ‖θt − θj‖2, there exists c1 ∈ (0, 1), such that |S?\St| ≤ c12 τn with high probability (i.e., more than half of samples in St are from the correct component). As a consequence,
‖θt+1 − θ?‖ ≤ c1 ‖θt − θ?‖+ c2σ √ d. (19)
For τ < 12 , in order to guarantee |S ?\St| < τn/2, we not only require ‖θt − θ?‖2 ≤ 0.9 minj∈[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 ∈ Rd, |S?\St| can be larger than τn/2. Observe that the median of squared distance from the good samples to θt (denoted as medgood) concentrates at the sample mean, which concentrates at the expected mean, which is ‖θt−θ?‖22 +σ2d. On the other hand, we require the number of bad samples whose squared distance to θt is less than medgood is less than τn/2, which corresponds to the τ2(1−τ) -quantile value to be greater than medgood. Therefore, a valid θt should satisfy:
P [ σ2n>n + 2σn>(θt − θ(j)) < ‖θt − θ?‖22 − ‖θt − θ(j)‖22 + σ2d ] ≤ τ
2(1− τ) ,
where n ∼ N (0, Id) is a normal Gaussian vector. By sub-exponential inequality, and reorganizing the terms, a sufficient condition we require is ‖θt− θ?‖2 ≤ minj∈[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).

heading: D.2 SIMULATION RESULTS
text: In this part, we provide synthetic experimental results for the Gaussian mixture model. Most of the settings are similar to the settings for mixed linear regression in Section C.2. For clearness, we will re-state some of the definitions/settings.
D.2.1 ILFB ON GAUSSIAN MIXTURE MODEL
We verify the performance of ILFB for Gaussian mixture model through synthetic experiments. In Gaussian mean estimation, we are interested in recovering the mean of the dominant mixture component. The bad samples are generated from another Gaussian distribution, and the distance of the two centers is set as 1 for convenience. We test the performance when τ? varies in the interval [0.5, 0.8] with σ = 0.15. 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.
According to Fig. 9 (left), ILFB performs close to the oracle, and is much better than the naive method and ILFB with random initialization. In Fig. 9 (right), we see linear convergence at the first few rounds until reaching a static point.

heading: D.2.2 ASYMPTOTIC PERFORMANCE
text: Next, we check the asymptotic behavior of ILFB for Gaussian mixture model under different noise levels. As we stated in our theorem, ILFB will converge to the noise ball centered at the true parameter, which does not guarantee consistency. In fact, our experiments verifies that the result is tight.
Our experimental setting is as follows: we consider mixture of two Gaussian distributions, where 60% of the data comes from the interested component. The distance between two centers is 1. We test the performance under different sample sizes, varies from 100 to 51200. The standard deviation of each result is calculated based on 100 random runs.
In Fig. 10 (middle), there exists a gap between ILFB and the oracle, i.e., the oracle goes asymptotically to the true parameter as n gets larger, while the performance of ILFB does not decrease with n after some threshold. The same problem exists when the noise becomes larger, as shown in Fig. 10, however, for n ≤ 51200, the results for both ILFB and the oracle are dominated by the noise. In the small noise regime, both ILFB and the oracle perform well.
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.
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 djm := minl∈[m]\{j} ‖θ(j) − θ(l)‖2. Consider taking the overall mean as the initialization θ0, then, if ∥∥∥∑l∈[m]\{j}(θ(j) − θ(l))|Sl|∥∥∥
2 ≤ αndjm, and n ≥ cdσ
2
( 919−α)2(d j m)2
, we have ‖θ0 − θ(j)‖2 ≤ 0.9 minl∈[m]\{j} ∥∥θ0 − θ(l)∥∥2 with high probability.
Proof. Assume ∥∥∥∑j∈[m](θ? − θ(j))|Sjbad|∥∥∥
2 ≤ αnminj∈[m]
∥∥θ? − θ(j)∥∥ 2 . Consider the initial-
ization
θ0 = 1
n n∑ i=1 xi.
We have with high probability,
‖θ0 − θ?‖2 = 1
n ∥∥∥∥∥ n∑ i=1 xi − θ? ∥∥∥∥∥
2
= 1
n ∥∥∥∥∥∥  ∑ i∈Sgood xi − θ? + ∑ i∈Sbad xi − θ? ∥∥∥∥∥∥
2
≤ 1 n ∥∥∥∥∥∥ ∑ j∈[m] (θ? − θ(j))|Sjbad| ∥∥∥∥∥∥ 2 + cσ √ d n
≤ 1 n αn min j∈[m] ∥∥∥θ? − θ(j)∥∥∥ 2 + cσ √ d n
≤ 9 19 min j∈[m] ∥∥∥θ? − θ(j)∥∥∥ 2
if n ≥ cdσ 2
( 919−α)2d 2 k
. This will imply ‖θ0 − θ?‖2 ≤ 0.9 minj∈[m] ∥∥θ0 − θ(j)∥∥2.

heading: E MORE EXPERIMENTAL RESULTS
text: 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:
• 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.

Review summaries:
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.

This paper introduces a framework for situation when the training samples are not pure. The idea is a simple approach by training a model and removing a portion of examples from the training set based on the loss of the model. The authors provide some theoretical study on two models: linear regression and Gaussian mixture model and utilize deep neural network to show their framework performs well experimentally.