Year: 2021

Abstract:
Learning and decision making in domains with naturally high noise-to-signal ratios – such as Finance or Public Health – can be challenging and yet extremely important. In this paper, we study a problem of learning on datasets in which a significant proportion of samples does not contain useful information. To analyze this setting, we introduce a noisy generative process with a clear distinction between uninformative/not learnable/purely random data and a structured/informative component. This dichotomy is present both during the training and in the inference phase. We propose a novel approach to learn under these conditions via a loss inspired by the selective learning theory. By minimizing the loss, our method is guaranteed to make a near-optimal decision by simultaneously distinguishing structured data from the non-learnable and making predictions, even in a highly imbalanced setting. We build upon the strength of our theoretical guarantees by describing an iterative algorithm, which jointly optimizes both a predictor and a selector, and evaluate its empirical performance under a variety of conditions.

heading: 1 INTRODUCTION
text: Despite the success of machine learning in computer vision (Deng et al., 2009; Krizhevsky et al., 2009; He et al., 2016a; Huang et al., 2017) and natural language processing (Vaswani et al., 2017; Devlin et al., 2018), the power of ML is yet to make significant impact in other areas. One major challenge is the inherently high noise-to-signal ratio in certain domains. For example, in Finance, while stock prices generally reflect the information about financial health of their companies, over the short term, their fluctuations most closely resemble random walks - which are naturally unpredictable - and are usually modeled as such (Tsay, 2005). In biomedical research, the underlying phenomena are often highly complex and are affected by unobservable factors. The outcome may appear highly random to the measurements (gene expression, medical histories), if the true causing factor is not included or is overwhelmed by others.
We are interested in dealing with datasets that may contain large fraction of noisy/uninformative/not learnable data in both training and testing stages. Direct application of standard supervised learning methods to such datasets is both challenging and unwarranted. At the training stage, the uninformative data can significantly bias the model or even completely overwhelm the true signal (Nettleton et al., 2010). Therefore, naïve forecasts in majority-uninformative datasets are doomed to be unreliable. Compared to other learning methods, deep neural networks are even more affected by the presence of noise, due to their strong memorization power (Zhang et al., 2017): they are likely to overfit the noise and make overly confident predictions where no real structure exists.
In this paper, we propose a novel method for learning on datasets where a significant portion of content is pure noise. Instead of forcing the classifier to make predictions for every sample, we learn to decide whether a datapoint is informative or not. If successful, the method abstains from making decisions where no structure exists, and predominantly learns from the remaining predictable data.
Our idea is inspired by the classic selective prediction problem (Chow, 1957), in which one learns to select a subset of data and only predict on that subset. However, the goal of selective prediction is very different from ours. A selective prediction method considers all data relevant. It pursues a balance between coverage (i.e. proportion of the data selected) and conditional accuracy on the selected data. In our problem, we assume that uninformative data is an integral part of the data generative process. No learning method, no matter how powerful, can be successful on such data. Our goal is to identify these uninformative samples as well as possible, and at the same time, to train a classifier by minimizing conditional risk on the remaining informative data.
Our method learns both a predictor, f , that classifies samples, and a selector, g, that selects learnable data for the predictor and rejects/abstains from the uninformative data. We are using g to approximate the ground truth indicator function of structured/informative data, g∗. We assume that g∗ exists as a part of the data generation process, but it is never revealed to us, even during training. Instead of direct supervision, we therefore must rely on the predictor’s mistakes to train the selector. To achieve this goal, we propose a novel selector loss enforcing that (1) the selected data best fits the predictor, and (2) the portion of the data where we abstain from forecasting, does not contain many correct predictions. This loss function is quite different from the loss in classic selective prediction, which penalizes all unselected data equally.
A major contribution of this paper is the derivation of theoretical guarantees for the empirical minimizer of our loss. We analyze the proposed selector loss function and provide sample complexity for learning a nearly optimal selector. We show that optimizing such loss can recover nearly all the structured/informative data in a PAC fashion (Valiant, 1984; Kearns et al., 1994; Valiant, 2013), i.e. one can approximate the ground truth selector function g∗ well with high probability, given sufficient samples. What may be surprising is that this guarantee holds even in a challenging setting where the uninformative data represents the majority of the training set.
This theoretical guarantee lets us expand to a more challenging and realistic setting. When the sample size is limited and the initially learned predictor is not sufficiently close to the ground truth, we extend our method to an iterative algorithm, in which we progressively optimize both the predictor and the selector. The selector is improved by optimizing our novel selector loss. Meanwhile, the predictor is improved by optimizing the empirical risk, reweighted based on the selector’s output; uninformative or nearly-uninformative samples identified by the selector will be down-weighed. Experiments on real-world datasets demonstrate superiority of our method to existing baselines. Note that in this paper, we assume that each sample is either informative or not. Extending our method to a more general setting with continuous transitions between informative and uninformative is non-trivial and is left as future work.

heading: 1.1 RELATED WORK
text: Learning with untrusted data aims to recover the ground truth model from a partially corrupted dataset. Different noise models for untrusted data have been studied, including random label noise (Bylander, 1994; Natarajan et al., 2013; Han et al., 2018; Yu et al., 2019; Zheng et al., 2020; Zhang et al., 2020), bounded label noise (Massart & Nédélec, 2006; Awasthi et al., 2015; Diakonikolas et al., 2019; 2020) and adversarial noise (Kearns & Li, 1993; Kearns et al., 1994; Kalai et al., 2008; Klivans et al., 2009; Awasthi et al., 2017). In the most pessimistic setting, if the majority data is corrupted by arbitrary adversarial noise, even mean estimation may be impossible. This is known as List-Decodable problem (Balcan et al., 2008; Charikar et al., 2017; Diakonikolas et al., 2018), where the best one can do when the proportion of trusted data α is less than 0.5, is to return 1α many hypotheses of the mean, knowing one of them is promising. We, on the other hand, aim to produce a single accurate model even in a setting where the majority of the data is uninformative (the noise, of course, must be of a certain type, see next section). While above works assume the presence of noisy data only in the training stage, we study the case where noise is an integral part of the generative process and thus will appear during inference as well, where it must be detected and discarded once more.
Selective learning is an active research area. It extends the classic selective prediction problem and studies how to select a subset of data for different learning tasks. We can summarize existing methods into 4 categories: Monte Carlo sampling based methods (Gal & Ghahramani, 2016; Kendall & Gal, 2017; Pearce et al., 2020), margin based methods (Fumera & Roli, 2002; Bartlett & Wegkamp, 2008; Grandvalet et al., 2008; Wegkamp et al., 2011; Zhang et al., 2018), confidence based methods (Wiener & El-Yaniv, 2011; Geifman & El-Yaniv, 2017; Jiang et al., 2018) and customized selective loss (Cortes et al., 2016; Geifman & El-Yaniv, 2019; Liu et al., 2019). Notably, several works propose customized losses, and incorporate them into neural networks. In (Geifman & El-Yaniv, 2019), the network maintains an extra output neuron to indicate rejection of datapoints. Liu et al. (2019) use Gambler loss where a cost term is associated with each output neuron and a doubling-rate-like loss function is used to balance rejections and predictions. Cortes et al. (2016) perform data selection with an extra model and introduce a selective loss that helps maximize the coverage ratio, thus trading off a small fraction of data for a better precision.
Existing works on selective prediction are all motivated from the coverage perspective - i.e. one wants to make safe prediction to achieve higher precision while maintain a reasonable recall (El-Yaniv et al., 2010). Whereas our paper is the first to investigate the case where some (or even majority) of the data is uninformative, and thus must be discarded at prediction time. Unlike with the selective prediction, there is a latent ground truth indicator function of whether a datapoint should be selected or not. Our method is guaranteed to identify those uninformative samples.

heading: 2 PROBLEM FORMULATION
text: In this section, we describe the inherently-noisy data generation process that we aim to study. The model has three important features: 1) the uninformative portion of the data has labels generated by coin flipping; 2) the informative datapoints are labeled with a latent ground truth function; and 3) the uninformative data has a distinguishable support from the informative data. Formally: Definition 1 (Noisy Generative Process). We define Noisy Generative Process by the following notation x ∼ Dα where
Dα ≡ { x ∼ DU with prob. 1− α (Uninformative/Noisy Data) x ∼ DI with prob. α (Informative/Structured Data).
(1)
Let ΩD ⊆ Rd be the support of Dα. Suppose {ΩU ,ΩI} is a partition of ΩD, the ground truth labeling function f∗ : X → {+1,−1} is in hypothesis class F and data is sampled according to:
x ∼ Dα; y ≡ {
Bernoulli(0.5), if x ∈ ΩU f∗(x), if x ∈ ΩI .
(2)
Note that the f∗ is defined on the whole domain, although only the part within ΩI is relevant. α represents the fraction of informative or structured data in the population. For the rest of the paper, we abuse the notation and use (x, y) ∼ Dα to refer to samples generated from this process. Next definition describes a separability condition between informative and uninformative data. It allows to distinguish noise from structure and enables us to approximate the ground truth selector via empirical minimization. Definition 2 (H-Separable). Given compact set Ω and its partition {ΩU ,ΩI}, {ΩU ,ΩI} satisfies H-Separable condition if there exists g∗ ∈ H satisfying g∗(x) : X → {+1,−1}:
g∗(x) ≡ { −1, if x ∈ ΩU 1, if x ∈ ΩI .
(3)
One can view g∗(·) in definition 2 as the target selector we wish to recover. Having introduced the data generation process and the separability condition, we now describe our main assumption for the remainder of the paper. Assumption 1. Data Sn = {xi, yi}Ni=1 is i.i.d generated according to the Noisy Generative Process (Definition 1), with f∗ ∈ F , support ΩDα = ΩU ∪̇ΩI where ΩU ,ΩI areH-Separable.
Throughout this paper, we are interested in the following learning task: Problem 1 (Abstain from Uninformative Data). Under Assumption 1 with enough i.i.d observations from Dα: 1) given hypothesis class F , we aim to learn the underlying ground truth classifier f∗(x); and 2) given the hypothesis classH, we aim to learn the selector g∗(x).
Evaluation metrics. We define metrics to evaluate the quality of both the prediction and the selection. For the prediction, we borrow the selective risk definition from selective learning (El-Yaniv et al., 2010; Geifman & El-Yaniv, 2019; 2017) using our own notation. Definition 3 (Selective Risk). Given a predictor f ∈ F and a selector g ∈ H, we define the selective risk as: CR(f, g) = E(x,y)∼Dα [1{f(x) 6= y}|g(x) ≥ 0] and its empirical version: CRS(f, g) = ∑n i=1 1{f(xi)6=yi}1{g(xi)≥0}∑n
i=1 1{g(xi)≥0} .
Selective risk measures the average risk conditioned on instances that are picked by the selector g(x). Note here when combined with the ground truth selector g∗, the selective risk of the ground truth
predictor f∗ goes to zero. Without a selector, however, f∗ has classical classification risk (which will be formally defined in Definition 5 later) of more than 12 (1− α). The metric used to evaluate the quality of a learned selector g is its false positive/negative rate. When g(x) ≥ 0 and g∗(x) < 0, the selector g accepts an uninformative datapoint and thus commits a false positive error. When g(x) < 0 and g∗(x) ≥ 0, g rejects/abstains from an informative datapoint resulting in a false negative error.
Definition 4 (Evaluation Metric for the Selector). Given distribution Dα as defined in Defnition 1 and g∗ as target selector, we denote the false positive and false negative of a selector g as
False Positive: P[g(x) ≥ 0|g∗(x) < 0]; False Negative: P[g(x) < 0|g∗(x) ≥ 0] (4)

heading: 3 OUR METHOD
text: In this section, we present our approach for learning and abstaining in the presence of uninformative data (Problem 1). The main challenge is that the latent informative/uninformative status of a datapoint is unknown. Our main idea is to introduce a novel selector loss function that trains a selector based on the performance of the best predictor (Section 3.1). In Section 3.2, we present our main theoretical result. We show that by jointly finding a predictor minimizing the classification risk and finding a selector minimizing the proposed selector loss, we can solve Problem 1 with controlled selective risk and selector error rates. During the analysis, we assume an oracle is given for the empirical minimizer. Approximating such empirical minimizer is a different topic beyond the scope of this paper (Bartlett et al., 2006; Yuan & Wegkamp, 2010). Inspired by the theoretical results, in Section 3.3, we propose a heuristic algorithm that iteratively optimizes the predictor and the selector.
Throughout the analysis, we focus on the 0-1 classification loss to optimize the predictor. This follows the standard for analyzing generalization performance and sample complexity. Formally:
Definition 5 (Classification Risk). We denote the classification risk of a model f as
R(f) ≡ E(x,y)∼Dα [1{f(x) 6= y}] (5)
and the empirical classification risk: RSn(f) = 1 n ∑n i=1 1{f(xi) 6= yi}. We define f∗Sn to be the empirical minimizer of RSn(f): f ∗ Sn = arg minf∈F RSn(f).

heading: 3.1 SELECTOR LOSS
text: To learn a selector without direct supervision, we have to leverage the performance of a given predictor, f . We propose the selector loss, which reweigh the 0-1 loss based on the prediction of f . This loss penalizes when (1) the predictor makes a correct prediction on a datapoint that the selector considers uninformative and abstains from, or (2) the predictor makes an incorrect prediction on a datapoint that the selector considers informative.
Definition 6 (Selector Loss). Given f ∈ F and its selector g ∈ H, we define the following weighted 0− 1 type risk w.r.t g(·) as selector risk:
W (g; f, θ) ≡ E(x,y)∼Dα [ θ α 1{f(x) 6= y}1{g(x) > 0}+ 1− θ 1− α 1{f(x) = y}1{g(x) ≤ 0} ] .
and its empirical version:
WSn(g; f, θ) = 1
n n∑ i=1 θ α 1{f(xi) 6= yi}1{g(xi) > 0}+ 1− θ 1− α 1{f(xi) = yi}1{g(xi) ≤ 0} (6)
Intuitively speaking, the loss will drive the selector to partition the domain into informative and uninformative regions. Within the informative region, the predictor is supposed to fit the data well, and should be more accurate. Meanwhile, within the uninformative region, the label is random and the predictor is supposed to be more prone to error. Another view of the loss is that we are learning to fit the selector g(x) to a pseudo-informative label given by the predictor, 1{f(x) = y}. Since such label is f -dependent, the quality of f is crucial for successfully learning g. In the theoretical analysis, we leverage the fact that predictor f is close enough to the ground truth predictor f∗.
Note that there are two types of errors penalized in the selector loss: an incorrect prediction on an informative datapoint, (f(x) 6= y) ∧ (g(x) > 0), and a correct prediction on an uninformative datapoint, (f(x) = y) ∧ (g(x) ≤ 0). We use βI = θα and βU = 1−θ 1−α to weigh these two types of error in the loss. Both βI and βU are controlled by a parameter θ and the latent informative data proportion α. We show that for a wide range of θ, the accuracy of the selector is guaranteed, as long as α is bounded away from 1, i.e., when abstention is necessary. In practice, we can adjust βI and βU freely without knowing exact value of α, as empirical performance remains stable with regard to these choices.
Learning a selector with the novel loss. In an ideal setting, to learn a selector, we first estimate the predictor by minimizing the classification risk, f∗Sn = arg minf∈F RSn(f). Next, we estimate the selector by minimizing the selector loss, conditioned on the estimated predictor, f∗Sn , g∗Sn = arg ming∈HWSn(g, f ∗ Sn , θ). In Figure 1, we show an example of using the empirical minimization strategy with logistic regression and with 0-1 loss replaced by cross-entropy loss. In this case, the losses are all convex and the empirical minimizers f∗Sn and g ∗ Sn
can be computed exactly. Our analysis in Section 3.2 will show that the estimated predictor f∗Sn and selector g ∗ Sn
has bounded selective risk (as in Definition 3), as well as bounded false positive and false negative selector errors (as in Definition 4).
In practice, however, empirical minimization is not always possible, as optimization for complex models (e.g., DNNs) and non-convex losses remains open. We therefore propose a heuristic algorithm in the spirit of our theoretical results - it jointly learns f and g by minimizing the selector loss and a reweighed classification risk iteratively (see Section 3.3).

heading: 3.2 THEORETICAL ANALYSIS
text: In this section we report our theoretical results. The main result can be summarized in the following (informal) statement. Main Result (Informal) With sufficient data, the estimated predictor f∗Sn = arg minf∈F RSn(f) and selector g∗Sn = arg ming∈HWSn(g, f ∗ Sn , θ) are sufficiently close to the targets f∗ and g∗ with high probability.
The proof requires the classic growth function definition (Vapnik & Chervonenkis, 2015).
Definition 7 (Growth Function). Let H be the hypothesis class of function f and Fx1,...,xn = {f(x1), ..., f(xn) : f ∈ F} ⊆ {+1,−1}n. The growth function is defined to be the maximum number of ways in which n points can be classified by the function class: GF (n) = supx1,...,xn |Fx1,...,xn |.
Roadmap of the proof: Theorem 1 is a standard PAC Learning analysis where we show f∗Sn is sufficiently close to the ground truth function f∗. Note that our analysis does not imply efficient PAC learning since optimizing binary loss is NP-hard. In Theorem 2, we bound the statistical error of the selector loss. In Theorem 3, we leverage the fact that informative and uninformative portions of the data are distinguishable, as well as the fact that f∗Sn has low risk on informative data. This lets us bound the selector loss of g∗Sn given by W (g ∗ Sn , f∗Sn , θ). By carefully balancing the weight parameter
θ of selector loss, we derive the false positive and false negative guarantees in Theorem 3. Theorem 4 is a formal version of the main result, which applies Sauer’s Lemma (Sauer, 1972) to bound the growth function of hypothesis classes in Theorem 3. The toolkit we use is driven by the concept of a VC-dimension in (Vapnik & Chervonenkis, 2015; Blum et al., 2016; Mohri et al., 2018). We also provide a lower bound construction in the Appendix to show the (near) tightness of our analysis (up to a logarithmic factor). We present all the results below, detailed proofs are in the Appendix.
We first prove a theorem about sample complexity of the learning hypothesis optimized over a given dataset, referred to as f∗Sn . We show that it approximates the ground truth function f
∗ well. Theorem 1. Under Assumption 1, given hypothesis class F , a set of samples Sn = {(x1, y1), ..., (xn, yn)} drawn i.i.d from our Noisy Generative Process and f∗Sn = arg minf∈F RS(f), suppose n ≥ 32[log(4|GF (2n)|)+log( 1δ )]
2α2 , then with probability at least 1 − 2δ, R(f∗Sn) ≤ 1 2 (1− α) + 2 α. Furthermore, Px∼DI [f ∗(x) 6= f∗Sn(x)] ≤ 2 .
Next theorem states the sample requirements in order to achieve a small gap between the empirical selector loss and the true selector loss. The proof takes a union bound over all possible pairs of hypothesis (g, f) ∈ H × F , which explains the term |GH(2n)||GF (2n)| in the bound for n, the minimum number of sample points. Theorem 2. Given hypothesis classH,F , a set of samples Sn = {(x1, y1), ..., (xn, yn)} drawn i.i.d. from the Noisy Generative Process and f∗Sn = arg minf∈F RS(f), gSn
∗ = arg min g∈H WSn(g, f ∗ Sn , θ),
if θ ∈ (α, 1), α ∈ (0, 1) and n ≥ 32θ 2[log(4|GH(2n)||GF (2n)|)+log( 1δ )]
2α4 , with probability at least 1− δ,
|W (g∗Sn , f ∗ Sn , θ)−WSn(g ∗ Sn , f ∗ Sn , θ)| ≤ α.
Theorem 3 combines the results in Theorems 1 and 2. It shows that, by carefully choosing weight parameter θ, minimizing the selector loss with sufficiently large amount of data ensures a low false positive/negative rate of the selector with high probability. In particular, the analysis points to a trade off between false positive and negative rates faced by the selector in terms of θ. We characterize the relationship between θ and α using variable c = θ2α in the theorem and prove that for a wide range of c the false negative rate (FNR) and false positive rate (FPR) are controlled. Intuitively, a larger value of θ in WSn(g, f ∗ Sn , θ) implies a higher penalty on the false positive error.
Theorem 3. Under Assumption 1, given a set of samples Sn = {(x1, y1), ..., (xn, yn)} drawn i.i.d. from the Noisy Generative Process and f∗Sn = arg minf∈F RS(f), gSn
∗ = arg min g∈H WSn(g, f ∗ Sn , θ),
if θ ∈ (α, 1), α ∈ (0, 1) and n ≥ 32θ 2[log(4|GH(2n)||GF (2n)|)+log( 5δ )]
2α2 , if θ = 2cα with 1 2 < c < 1+α 4α ,
we have with probability at least 1− δ:
P[g∗Sn(x) ≥ 0|g ∗(x) ≤ 0] ≤ 12cα
2c− 1 [False Positive]
P[g∗Sn(x) < 0|g ∗(x) ≥ 0] ≤ 20c [False Negative]
(7)
Next theorem is a formal statement of the main result. It is worth mentioning that the theorem assumes that α is bounded away from 1, due to the fact that when almost all data is informative, there is no need for abstention. Theorem 4. Under Assumption 1, given set of samples Sn = {(x1, y1), ..., (xn, yn)} drawn i.i.d. from the Noisy Generative Process, hypothesis class H with VC-dimension dvc(H), F with VCdimension dvc(F) and f∗Sn = arg minf∈F RS(f), gSn
∗ = arg min g∈H WSn
( g, f∗Sn , 73α 72 + α2 72 ) , if
α ∈ (0, 0.9) and n ≥ 128[(dvc(H)+dvc(F)) log( 1 ε )+log( 16 δ )]
2α2 . We have with probability at least 1− δ: I)
P[g∗Sn(x) ≥ 0|g ∗(x) ≤ 0] = O( ) [False Positive] P[g∗Sn(x) < 0|g ∗(x) ≥ 0] ≤ O( ) [False Negative]
(8)
II) Px∼Dα [f∗(x) 6= f∗Sn(x)|g ∗ Sn(x) ≥ 0] = O( )
Remark 1. We provide a lower bound construction in the appendix to show that our bound in Theorem 4 is tight up to a logarithmic factor. Note that our lower bound is for empirical minimizers of R(f) and W (g, f, θ), therefore the tightness result is not an information theoretic bound for this family of problems. It remains an open question about whether or not strategies other than the empirical minimization, as in (Hanneke, 2016; Simon, 2015; El-Yaniv et al., 2010), can improve the sample complexity to a rate of O ( 1 αε ) . Note that the informative portion of the data (drawn with probability α) by itself only requires O( 1ε ) samples for an -excessive statistical error. It turns out that our analysis for empirical minimizer is nearly tight, and that the number of samples O ( 1
α2ε2
) is
indeed necessary because the presence of noisy data makes our problem harder. Remark 2. Theorem 4 says that by minimizing the empirical version of the loss from Definitions 5 and 6, one can achieve the goal of simultaneously selecting and learning with noisy data - i.e. the classification model f∗Sn has sufficiently low selective risk, and the selector g ∗ Sn
can distinguish informative data from non-informative. The analysis of the selector loss (Theorem 3) relies on the quality of the classifier f∗Sn . But since we know that g ∗ Sn
is able to abstain from uninformative data, we can retrain f∗Sn on the informative portion only, therefore guaranteeing its accuracy. Such circular logic naturally leads to a practical iterative algorithm that we present in the next section.

heading: 3.3 A HEURISTIC ALGORITHM IN PRACTICE
text: In Section 3.2, we analyzed an empirical minimizer of a conceptual 0-1 loss for the classifier f and the selector g. Binary loss, however, is impractical from the computational standpoint. In practice, we use cross-entropy loss instead and require that both f and g have continuous-valued output, ranging between 0 and 1. We also relax the requirement for empirical minimization oracles, allowing the practical algorithm to jointly optimize the predictor and the selector in an iterative manner. At each iteration, we update the predictor using the informative data selected by the selector, and then update the selector based on the predictor’s output. See Algorithm 1 for the pseudo-code. A pictorial example of Algorithm 1’s performance can be found in Figure 2 in the Appendix.
During the joint optimization process, the predictor is counting on the selector to show it only the informative data. However, the initial selector is not trustworthy. To update the predictor f , we turn to a so-called soft abstention scheme: use a weight vector γ that progressively down-weighs samples abstained by g, in the spirit of multiplicative weights algorithms (Cesa-Bianchi & Lugosi, 2006; Arora et al., 2012). Specifically, we increase the weight of i-th sample γi if the selector accepts xi: γi = γi(1 + η · 1{g(xi) > 0.5}) and then normalize so that ∑n i=1 γi = 1. We call this a soft abstention approach because the algorithm decreases the weight of uninformative data gradually.
In the heuristic algorithm, we use cross-entropy loss to fit the selector to pseudo-informative labels output by the predictor. We also use a single hyper-parameter β = βI/βU = θ(1−α) α(1−θ) to control the ratio of the two types of errors. As suggested by Theorem 3, small selector FPR and small selector FNR can be achieved by a β ∈ ( 1, 1 + 1α ) . For a scenario when abstention is necessary, i.e. when the noisy data ratio is in a reasonable range, we can choose our hyper-parameter from a wide interval.
Algorithm 1 Iterative Soft Abstain Require: Data set Sn = {(x1, y1), ..., (xn, yn))}, weight parameter:β, random initial f0 and g0,
initial sample weights γ0i = 1 n ,∀i ∈ [n], meta learning rate η, number of iterations T
1: for t← 1, · · · , T do 2: Optimize loss to update predictor f t: ∑n i=1 γ t i {yi log(f(xi)) + (1− yi) log(1− f(xi))} 3: Approximate the ‘pseudo-informative label’ : zti = 1{1{f t(xi) > 0.5} = yi} 4: Optimize loss to update selector gt: ∑n i=1 {zti log(g(xi)) + β(1− zti) log(1− g(xi))} 5: Update sample weights using gt: γt+1i = γti (1+η1{g t(xi)>0.5})∑n j=1 γ t j(1+η1{gt(xj)>0.5})
. 6: end for 7: Output fT , gT

heading: 4 EXPERIMENTS
text: Datasets. We test the efficacy of our heuristic algorithm (Algorithm 1), via semi-synthetic experiments. We synthesize the noisy data by mixing datasets from two different domains and uniformly shuffling all labels in one of them. Our first synthetic noisy dataset is composed of MNIST (LeCun
et al., 1998) and Fashion-MNIST (Xiao et al., 2017). We uniformly shuffle the labels of MNIST images and keep original labels of Fashion-MNIST. As a result, images from MNIST are uninformative while images from Fashion-MNIST are considered informative. The fact that one dataset has hand-written digits and the other one contains pictures of clothes ensures distinct supports. We mix these two datasets in different proportions to proxy for our Noisy Generative Process.
We also perform experiments on another synthetic dataset, where noisy and informative portions come from similar domains. To achieve this, we use SVHN (Netzer et al., 2011). We uniformly at random flip labels of classes 5-9 into classes 0-4 and mix them with intact data from classes 0-4. In this case, we consider the data from classes 5-9 uninformative. In this mixed dataset, informative and uninformative data have similar domains, which makes it more challenging to correctly identify informative data (and harder to argue separate support).
Baselines. We compare our method to two of the most recently proposed selective learning algorithms. (1) SelectiveNet (Geifman & El-Yaniv, 2019), which integrates an extra neuron as a data selector in the output layer and also introduces a loss term to control the coverage ratio; (2) DeepGambler (Liu et al., 2019), which also maintains an extra neuron for abstention and uses a doubling-rate-like loss term (i.e., gambler loss) to train the model. (3) We also create a third baseline that selects data using model prediction confidence, which we refer to as Confidence. The hypothesis is that informative data should have higher prediction confidence compared to uninformative data.
Evaluation Metrics. We use three criteria to jointly evaluate a selective learning outcome. (1) Selective risk (SR). Selective risk is the empirical risk measured over the datapoints selected by the algorithm. This is a metric that is also adopted in (Geifman & El-Yaniv, 2019; Liu et al., 2019). (2) Precision. Precision is the proportion of true informative datapoints among all the data picked out by the selector. (3) Recall. Recall is the proportion of true informative samples picked out by the selector out of all the informative samples in the dataset. SR evaluates the quality of the classifier, Precision and Recall are the standard ML metrics of the selector. An ideal selective learning algorithm should have low SR, high precision and high recall.
Experiment setting. We assume that the ratio of informative data, α, is unknown to all methods. This is necessary in practice; the ratio and strength of noise are not known in most real world scenarios. For SelectiveNet and DeepGambler, such ratio is a required input. To run these baselines, we first run the original backbone for 60 epochs, and then estimate α using backbone’s training accuracy. Assume that the backbone fits all of the informative data perfectly and also makes some correct guesses on noisy data with probability 1num of classes , then the frequency estimation of α is α̂ = num of classes∗train acc−1num of classes−1 , which is the value we give to baselines. For more details about the experimental design, please refer to the Appendix (section D).
Results and discussion. Table 1 presents the result where we mix the entire uninformative dataset (shuffled MNIST) with different proportions of the informative dataset (Fashion-MNIST). Our algorithm outperforms all the baselines in this setting. If we use partial dataset by decreasing the number of noisy datapoints and repeating previous experiments with the same uninformative-toinformative data ratios, our algorithm wins by an even larger margin (Table 2).
We can see that both SelectiveNet and DeepGambler fall apart in the setting where informative data are sparse. Neither of them achieve a risk below 40% when we mix in only 25% of informative data. The reason is that both of these two methods are only designed to achieve predetermined coverage and cannot dynamically adapt to settings with unknown informative-to-uninformative data ratio. Our algorithm thus gains advantage by learning the underlying uninformative data labeling function in a data-driven manner.
Our algorithm also outperforms all the baselines on SVHN dataset where noisy data comes from a similar domain to the informative data. Each experiment is repeated 5 times. Mean and standard deviation are presented in Table 3 and Table 4.
We provide more experimental results in the Appendix (section D). We test the performance of each method in the case where α is given and in the case where datasets contain minority noisy data.

heading: 5 CONCLUSION
text: In this work, we propose a natural noisy generative process to model a problem where a significant proportion of datapoints are purely random. We solve it by learning both a predictor for classification and a selector to abstain from the uninformative data. We propose a novel selector loss to learn selector with theoretical guarantees. Based on the selector loss, we design a heuristic algorithm that jointly learns the predictor and selector. Our empirical study shows promising results of our method.

heading: 6 REPRODUCIBILITY STATEMENT
text: We describe a synthetic data generation procedure, evaluation metrics and experiment setting in section 4. For the convenience of the reader to reproduce the experiment, we also summarize the setting and give implementation details in section D.3. The source code as well as parameters to reproduce the experimental results will be made available together with the publication of the paper.

heading: 7 ETHICS STATEMENT
text: This paper focuses on a theoretical discussion about learning from data that contains different portion of non-informative samples. Our experiments only use publicly available datasets. Our discussion, analysis, or data shouldn’t raise any ethics-related issues. The learning method proposed in this paper, however, can be potentially used in applications with fairness and privacy concerns. It our future efforts in this area, we aim to address and resolve possible negative impact.

heading: B THEORETICAL ANALYSIS
text: In this section, we show auxiliary results culminating with the proof of the main result in Theorem 4. In this section, we will use the following well-known result repeatedly.
Lemma 1 (Hoeffding’s Inequality). Let Z1, ..., Zn be independent bounded random variables with Zi ∈ [a, b] for all i, where −∞ < a < b <∞. Then for all t > 0:
P( 1 n | n∑ i=1 Zi − E[Zi]| ≥ t) ≤ 2e − 2nt2 (b−a)2 (9)
The next lemma provides an upper bound on the empirical risk RS(f∗), if enough samples are available.
Lemma 2. Consider a set of samples S = {(x1, y1), ..., (xn, yn)} drawn i.i.d. from the Noisy Generative Process and f∗ in the hypothesis class F satisfying f(x) ∈ {−1,+1}. If:
n ≥ 3 log(1δ )
2α2
Then we have with probability at least 1− δ :
RS(f ∗) ≤ 1
2 (1− α) + αε (10)
Proof: By definition: R(f) = E(x,y)∼Dα [1f(x) 6= y] (11)
and the empirical risk
RS(f) = 1
n n∑ i=1 1{f(xi) 6= yi} (12)
Note that 1{f(x) 6= y} is bounded in the interval [0, 1] and given f∗ ∈ F , 1{f(xi) 6= yi}, i ∈ [n] form a set of n independent random variables. By setting b− a = 1, t = α in Equation 9, the choice of n ensures that −2nt 2
(b−a)2 ≤ 6 log(δ). Thus
PSn∼Dα [|RS(f∗)−R(f∗)| ≥ α] ≤ δ.
where we have R(f∗) = E(x,y)∼Dα [1f(x) 6= y]
=E(x,y)∼Dα [1{f ∗(x) 6= y}|x ∈ ΩU ]P[x ∈ ΩU ]︸ ︷︷ ︸
1 2P[x∈ΩU ]: Since y is labeled by coin flipping in ΩU
+ E(x,y)∼Dα [1{f ∗(x) 6= y}|x ∈ ΩI ]P[x ∈ ΩI ]︸ ︷︷ ︸
0: Since y is labeled by f∗ with 0 Bayes Risk in ΩI
= 1
2 (1− α)
(13)
This way we have:
PSn∼Dα [|RS(f∗)− 1
2 (1− α)| ≥ α] ≤ δ.
which implies that Equation 10 holds with probability at least 1− δ. The proof of Lemma 2 relies on the independence between 1f(xi) 6= yi across different pairs (xi, yi) ∈ Sn. However, there is no guarantee that such independence holds for the empirical minimizer f∗Sn = arg minf∈F RS(f)..
In order to prove Theorem 1, we use the growth function in Definition 7 for sets of size n and the following symmetrization lemma. Here we show its proof for completeness; it can be found in different sources (Mohri et al., 2018; Blum et al., 2016). Lemma 3. Suppose Sn = {(x1, y1), ..., (xn, yn)} are i.i.d sampled , L(f, x, y) ∈ [0, b] and LSn = 1 n ∑n i=1 L(f, xi, yi). If
nt2 ≥ 2b2
then we have:
PSn∼Dα [sup f∈F |LSn(f)− L(f)| ≥ t] ≤ 2PSn,S′n∼Dα [sup f∈F |LSn(f)− LS′n(f)| ≥
t 2 ].
Proof: Since |LSn(f)− L(f)| ≥ t and |LS′n(f)− L(f)| ≤ t 2 implies |LSn − LS′n | ≥ t 2 thus
1 sup f∈F |LSn (f)−L(f)|≥t1 sup f∈F |LS′n (f)−L(f)|≤ t 2
≤ 1 sup f∈F |LSn (f)−LS′n (f)|≥ t 2
(14)
Taking expectation w.r.t Sn ∼ Dα and S′n ∼ Dα we have
PSn∼Dα [sup f∈F |LSn(f)− L(f)| ≥ t]PS′n∼Dα [sup f∈F |LS′n(f)− L(f)| ≤
t 2 ]
≤ PSn,S′n∼Dα [sup f∈F |LSn(f)− LS′n(f)| ≥
t 2 ]
(15)
Next we lower bound P[sup f∈F |LS′n(f)−L(f)| ≥ t 2 ]. Since L(f, x, y) ∈ [0, b] and V ar(L(f, x, y)) ≤ b2
4 , we have:
PS′n∼Dα [sup f∈F |LS′n(f)− L(f)| ≤
t 2 ] ≤ 4V ar(LSn) nt2 ≤ 1 2
Given the choice of n ≥ 2b2, we have P[sup f∈F |LS′n(f)− L(f)| ≥ t 2 ] ≥ 1 2 which implies
PSn∼Dα [sup f∈F |LSn(f)− L(f)| ≥ t] ≤ 2PSn,S′n∼Dα [sup f∈F |LSn(f)− LS′n(f)| ≥
t 2 ].
Theorem 1. Under Assumption 1, given a set of samples Sn = {(x1, y1), ..., (xn, yn)} drawn i.i.d. from the Noisy Generative Process and
f∗Sn = arg min f∈F RS(f),
suppose
n ≥ 32 [ log(4|GH(2n)|) + log( 1δ ) ] 2α2
Then with probability at least 1− 2δ:
R(f∗Sn) ≤ 1
2 (1− α) + 2 α.
Furthermore, Px∼DI [f∗(x) 6= f∗Sn(x)] ≤ 2
Proof. : We first bound the probability of the event that R(f∗Sn) ≤ 1 2 − (1− 2 )α.
We start with bounding PSn,S′n∼Dα [|RSn(f)−R(f) +R(f)−RS′n(f)| ≥ t 2 ] for a fixed f . Since |RSn(f)−R(f) +R(f)−RS′n(f)| ≥ t 2 implies |RSn(f)−R(f)| ≥ t 4 or |R(f)−RS′n(f)| ≥ t 4 we have
PSn,S′n∼Dα [|RSn(f)−R(f) +R(f)−RS′n(f)| ≥ t
2 ]
≤PSn∼Dα [|RSn(f)−R(f)| ≥ t
4 ] + PS′n∼Dα [|RS′n(f)−R(f)| ≥
t 4 ]
≤2e−nt 2 32
(16)
Let FSn,S′n = {f(x) : f ∈ F , x ∈ Sn ∪ S ′ n} ⊆ {+1,−1}2n with Lemma 3 and Eq 16 we have:
PSn∼Dα [sup f∈F |RSn(f)−R(f)| ≥ t]
≤2PSn,S′n∼Dα [sup f∈F |RSn(f)−RS′n(f)| ≥
t 2 ].
=2PSn,S′n∼Dα [ sup f∈FSn,S′n
|RSn(f)−RS′n(f)| ≥ t
2 ]
≤2 ∑
f∈FSn,S′n
P[|RSn(f)−RS′n(f)| ≥ t
2 ]
=2 ∑
f∈FSn,S′n
P[|RSn(f)−R(f) +R(f)−RS′n(f)| ≥ t
2 ]
≤4|FS′n,Sn |e −nt232 ≤4GF (2n)e− nt2 32
(17)
By setting t = α and n ≥ 32(4 log(GF (2n))+log( 1 δ ))
α2 2 we have with probability of at least 1− δ:
R(f∗Sn)−RSn(f ∗ Sn) ≤
α
2
Next we apply the fact that f∗Sn = arg minf∈F RS(f). Since RSn(f ∗) ≥ RSn(f∗Sn), we have:
R(f∗Sn) ≤ α
2 +RSn(f
∗ Sn) ≤
α
2 +RSn(f
∗)
Since RSn(f ∗) ≤ 12 (1 − α) + α with failure probability at most δ (Lemma 2), we have with probability at least 1− 2δ:
R(f∗Sn) ≤ 1
2 (1− α) + 2 α.
Next we prove the claim that:
Px∼DI [f∗(x) 6= f∗Sn(x)] ≤ 2 .
Since R(f∗Sn) ≤ 1 2 (1− α) + 2 α:
R(f∗Sn) =E(x,y)∼Dα [1{f ∗ Sn(x) 6= y}]
=P(x,y)∼Dα [1{f ∗ Sn(x) 6= y}] =P(x,y)∼Dα [1{f ∗ Sn(x) 6= y}|x ∈ ΩU ]︸ ︷︷ ︸
1 2
P(x,y)∼Dα [x ∈ ΩU ]︸ ︷︷ ︸ 1−α
+P(x,y)∼Dα [1{f ∗ Sn(x) 6= y}|x ∈ ΩI ]︸ ︷︷ ︸
P(x,y)∼Dα [1{f∗Sn (x)6=f ∗(x)}|x∈ΩI ]
P(x,y)∼Dα [x ∈ ΩI ]︸ ︷︷ ︸ α
= 1
2 (1− α) + αPx∼Dα [1{f∗Sn(x) 6= f ∗(x)}|x ∈ ΩI ]
≤1 2 (1− α) + 2 α
=⇒Px∼Dα [1{f∗Sn(x) 6= f ∗(x)}|x ∈ ΩI ] ≤ 2
(18)
Next we analyze the weighted risk in Definition 6 and its empirical version. In particular, we are interested in the case where θ > α, which implies θα ≥
1−θ 1−α . For a given pair (xi, yi), we have:{
θ α 1{f(xi) 6= yi}1{g(xi) > 0}+ 1− θ 1− α 1{f(xi) = yi}1{g(xi) ≤ 0 } ≤ θ α
.
It is useful to write down explicitly the following decomposition of W (g, f, θ):
W (g, f, θ) = E(x,y)∼Dα
[ θ
α 1{f(x) 6= y}1{g(x) > 0}+ 1− θ 1− α 1{f(x) = y}1{g(x) ≤ 0} ] = E(x,y)∼Dα [ θ
α 1{f(x) 6= y}1{g(x) > 0}1{g∗(x) > 0} ] + E(x,y)∼Dα [ θ
α 1{f(x) 6= y}1{g(x) > 0}1{g∗(x) ≤ 0} ] + E(x,y)∼Dα [ 1− θ 1− α 1{f(x) = y}1{g(x) ≤ 0}1{g∗(x) ≤ 0} ]
+ E(x,y)∼Dα [ 1− θ 1− α 1{f(x) = y}1{g(x) ≤ 0}1{g∗(x) > 0} ]
= θ
α P(x,y)∼Dα [f(x) 6= y|g(x) > 0, g ∗(x) > 0]Px∼Dα [g(x) > 0, g∗(x) > 0]
+ θ
α P(x,y)∼Dα [f(x) 6= y|g(x) > 0, g ∗(x) ≤ 0]Px∼Dα [g(x) > 0, g∗(x) ≤ 0]
+ 1− θ 1− α P(x,y)∼Dα [f(x) = y|g(x) ≤ 0, g ∗(x) ≤ 0] + 1− θ 1− α P(x,y)∼Dα [f(x) = y|g(x) ≤ 0, g ∗(x) > 0]Px∼Dα [g(x) ≤ 0, g∗(x) > 0]
= θ
α P(x,y)∼Dα [f(x) 6= y|g(x) > 0, g ∗(x) > 0]Px∼Dα [g(x) > 0, g∗(x) > 0]
+ θ
2α Px∼Dα [g(x) > 0, g∗(x) ≤ 0]
+ 1− θ
2(1− α) Px∼Dα [g(x) ≤ 0, g∗(x) ≤ 0]
+ 1− θ 1− α P(x,y)∼Dα [f(x) = y|g(x) ≤ 0, g ∗(x) > 0]Px∼Dα [g(x) ≤ 0, g∗(x) > 0]
(19)
One can see that if θ > α, then g(x) should reject all x ∈ ΩU since θα > 1−θ 1−α . For the informative partition x ∈ ΩI , the decomposition suggests acceptance of all x such that f(x) = y and rejection of f(x) 6= y. This gives the optimal value 1−θ2(1−α)Px∼Dα [g
∗(x) ≤ 0]. Note that the optimal value of W (g, f, θ) is not necessarily achieved at (f∗, g∗). For any fixed f , the optimal value of W (g, f, θ) is achived for g as long as g accepts all datapoints in ΩI that are correctly classified by f , and rejects all mistakes made by f in ΩI (as well as all datapoints in ΩU ).
Lemma 4. Given a set of samples Sn = {(x1, y1), ..., (xn, yn)} drawn i.i.d. from the Noisy Generative Process. Suppose θ ∈ (α, 1), α ∈ (0, 1), ≤ 0.1, and:
n ≥ 2θ2 log( 1δ )
2α4
Then with probability at least 1− δ we have:
|WSn(g∗, f∗, θ)−W (g∗, f∗, θ)| ≤ α
Proof. The following holds for a given (xi, yi):{ θ
α 1{f(xi) 6= yi}1{g(xi) > 0}+ 1− θ 1− α 1{f(xi) = yi}1{g(xi) ≤ 0} } ≤ θ α .
Since θ < 12 , we can apply Hoeffding’s inequality in Lemma 1 with a = 0, b = θ α . For fixed g, f ∈ F , 1{f(xi) 6= yi}, i ∈ [n] are set of n independent random variables. By setting b− a = θα , t = α in Equation 9, the choice of n ensures that −2nt 2
(b−a)2 ≤ 6 log(δ). Therefore:
PSn∼Dα [|WSn(g∗, f∗, θ)−W (g∗, f∗, θ)| ≥ α] ≤ δ.
Recall the empirical minimizer of WSn(g, f ∗ Sn , θ):
gSn ∗ = arg min
g∈H WSn(g, f
∗ Sn , θ).
Since f∗Sn and g ∗ Sn are data-dependent, it follows that Wi(g∗Sn , f ∗ Sn , θ), i ∈ [n] are not independent draws. Our strategy is to use similar logic as in the proof of the Theorem 1. We begin by finding an upper bound on the probability of WSn(g, f, θ) deviating from its expectation. Then we take a union bound of all the possible pair of (g, f) ∈ H ×F restricted to Sn. Theorem 2. Consider a set of samples Sn = {(x1, y1), ..., (xn, yn)} drawn i.i.d. from the Noisy Generative Process and
f∗Sn = arg min f∈F RS(f), gSn ∗ = arg min g∈H WSn(g, f ∗ Sn , θ),
If θ ∈ (α, 1), α ∈ (0, 1) and
n ≥ 32θ2
( log(4|GH(2n)||GF (2n)|) + log( 1δ ) ) 2α4
then with probability at least 1− δ:
|W (g∗Sn , f ∗ Sn , θ)−WSn(g ∗ Sn , f ∗ Sn , θ)| ≤ α.
Proof. First we apply Lemma 3 with LSn(f, g) = WSn(g, f, θ), b = θ α and t = α , and also using the condition n ≥ 32θ 2log(2|GH(2n)|GF (2n)|)+log( 1δ )
2α4 ≥ 2θ2 2α4 in the lemma. Then it follows:
PSn∼Dα [sup g∈H |WSn(g, f∗Sn , θ)−W (g, f ∗ Sn , θ)| ≥ α ]
≤2PSn,S′n∼Dα [sup g∈H |WSn(g, f∗Sn , θ)−WS′n(g, f ∗ Sn , θ)| ≥
α
2 ]
≤2PSn,S′n∼Dα [ sup g∈H,f∈F
|WSn(g, f, θ)−WS′n(g, f, θ)| ≥ α
2 ]
≤2PSn,S′n∼Dα [ sup g∈HSn,S′n ,f∈FSn,S′n
|WSn(g, f, θ)−WS′n(g, f, θ)| ≥ α
2 ]
≤2 ∑
g∈HSn,S′n ,f∈FSn,S′n
PSn,S′n∼Dα [|WSn(g, f, θ)−WS′n(g, f, θ)| ≥ α
2 ]
≤2 ∑
g∈HSn,S′n ,f∈FSn,S′n
PSn,S′n∼Dα [|WSn(g, f, θ)−W (g, f, θ) +W (g, f, θ)−WS′n(g, f, θ)| ≥ α
2 ]
≤4|HSn,S′n ||FSn,S′n |PSn∼Dα [|WSn(g, f, θ)−W (g, f, θ)| ≥ α
4 ]
≤4GH(2n)GF (2n)e −nα2 2 32 θ 2 α2
=4GH(2n)GF (2n)e− nα4 2 32θ2
(20)
Next we bound the FPR and FNR of g∗Sn leveraging on the fact that WSn(g, f ∗ Sn ) is sufficiently small.
Theorem 3. Under Assumption 1, given a set of samples Sn = {(x1, y1), ..., (xn, yn)} drawn i.i.d. from Noisy Generative Process and
f∗Sn = arg min f∈F RS(f), gSn ∗ = arg min g∈H WSn(g, f ∗ Sn , θ),
if θ ∈ (α, 1), α ∈ (0, 1) and
n ≥ 32θ2
[ log(4|GH(2n)||GF (2n)|) + log( 5δ ) ] 2α4
We have
I) with probability at least 1− δ
W (g∗Sn , f ∗ Sn , θ) ≤ 2 θ + 2α + (1− θ) 2
II) if θ = 2cα with 12 < c < 1+α 4α , we have with probability at least 1− δ
P[g∗Sn(x) ≥ 0|g ∗(x) ≤ 0] ≤ 12cα
2c− 1 [False Positive] (21)
P[g∗Sn(x) < 0|g ∗(x) ≥ 0] ≤ 20c [False Negative] (22)
Proof of I)
Proof.
W (g∗Sn , f ∗ Sn , θ)
≤ WSn(g∗Sn , f ∗ Sn , θ) + α ︸ ︷︷ ︸
with failure probability at most δ Theorem 2)
≤WSn(g∗, f∗Sn , θ) + α ︸ ︷︷ ︸ Optimality of g∗Sn ≤ W (g∗, f∗Sn , θ) + 2α ︸ ︷︷ ︸ With failure probability at most δ (Lemma 4)
=E(x,y)∼Dα
[ θ
α 1{f∗Sn(x) 6= y}1{g
∗(x) > 0} ]
+ E(x,y)∼Dα [ 1− θ 1− α 1{f∗Sn(x) = y}1{g ∗(x) ≤ 0} ] + 2α
=E(x,y)∼Dα
[ θ
α 1{f∗Sn(x) 6= y}|g ∗(x) > 0
] Px∼Dα [g∗(x) ≥ 0]
+ E(x,y)∼Dα [ 1− θ 1− α 1{f∗Sn(x) = y}|g ∗(x) ≤ 0 ] Px∼Dα [g∗(x) ≤ 0] + 2α
=E(x,y)∼Dα [ θ1{f∗Sn(x) 6= y}|g ∗(x) > 0 ] + E(x,y)∼Dα [ (1− θ)1{f∗Sn(x) = y}|g ∗(x) ≤ 0 ] =θ Px∼DI [f∗Sn 6= f ∗(x)]
≤2 with failure prob at most δ (Thm 1)
+ (1− θ)Px∼DU [f∗Sn = y] =0.5 since all y’s in ΩU are coin flipping + 2α
≤2 θ + 2α + (1− θ) 2
(23)
Proof of II):
Proof.
W (g∗Sn , f ∗ Sn , θ)
=E(x,y)∼Dα
[ θ
α 1{f∗Sn(x) 6= y}1{g ∗ Sn(x) > 0} ] + E(x,y)∼Dα [ 1− θ 1− α 1{f∗Sn(x) = y}1{g ∗ Sn(x) ≤ 0}
] =E(x,y)∼Dα [ θ
α 1{f∗Sn(x) 6= y}1{g ∗ Sn(x) > 0}|g ∗(x) ≥ 0 ] Px∼Dα [g∗(x) ≥ 0]︸ ︷︷ ︸
Term 1
(24)
+ E(x,y)∼Dα
[ θ
α 1{f∗Sn(x) 6= y}1{g ∗ Sn(x) > 0}|g ∗(x) ≤ 0 ] Px∼Dα [g∗(x) ≤ 0]︸ ︷︷ ︸
Term 2
+ E(x,y)∼Dα [ 1− θ 1− α 1{f∗Sn(x) = y}1{g ∗ Sn(x) ≤ 0}|g ∗(x) > 0 ] Px∼Dα [g∗(x) ≥ 0]︸ ︷︷ ︸
Term 3
+ E(x,y)∼Dα [ 1− θ 1− α 1{f∗Sn(x) = y}1{g ∗ Sn(x) ≤ 0}|g ∗(x) ≤ 0 ] Px∼Dα [g∗(x) ≤ 0]︸ ︷︷ ︸
Term 4
Next we lower bound Term 1, 2, 3, 4 individually and apply upper bound on W (g∗Sn , f ∗ Sn , θ) in Eq 23 for the proof of the statement. Term 1:
E(x,y)∼Dα
[ θ
α 1{f∗Sn(x) 6= y}1{g ∗ Sn(x) > 0}|g
∗(x) ≥ 0 ] Px∼Dα [g∗(x) ≥ 0]
=E(x,y)∼Dα [ 1{f∗Sn(x) 6= y}1{g ∗ Sn(x) > 0}|g ∗(x) ≥ 0 ] θ
=θE(x,y)∼Dα [ 1{f∗Sn(x) 6= y}|g ∗ Sn(x) > 0, g ∗(x) ≥ 0 ] Px∼Dα [g∗Sn(x) > 0|g
∗(x) ≥ 0] ≥0
(25)
Term 2:
E(x,y)∼Dα
[ θ
α 1{f∗Sn(x) 6= y}1{g ∗ Sn(x) > 0}|g
∗(x) ≤ 0 ] Px∼Dα [g∗(x) ≤ 0]
= θ(1− α)
α E(x,y)∼Dα
[ 1{f∗Sn(x) 6= y}1{g ∗ Sn(x) > 0}|g ∗(x) ≤ 0 ]
= θ(1− α)
α E(x,y)∼Dα
[ 1{f∗Sn(x) 6= y}|g ∗ Sn(x) > 0, g ∗(x) ≤ 0 ]
Px∼DU [f ∗ Sn 6=y]=0.5 Since all y are coin flipping if g∗(x) ≤ 0
Px∼Dα [g∗Sn(x) > 0|g ∗(x) ≤ 0]
= θ(1− α)
2α Px∼Dα [g∗Sn(x) > 0|g ∗(x) ≤ 0] (26)
Term 3:
E(x,y)∼Dα [ 1− θ 1− α 1{f∗Sn(x) = y}1{g ∗ Sn(x) ≤ 0}|g ∗(x) > 0 ] PDα [g∗(x) ≥ 0]
= (1− θ)α
1− α E(x,y)∼Dα
[ 1{f∗Sn(x) = y}1{g ∗ Sn(x) ≤ 0}|g ∗(x) > 0 ]
= (1− θ)α
1− α P(x,y)∼Dα
[ f∗Sn(x) = y|g ∗ Sn(x) ≤ 0, g ∗(x) > 0 ] Px∼Dα [g∗Sn(x) ≤ 0|g ∗(x) > 0]
(27)
By Theorem 1 we have with failure probability at most 2δ:
Px∼Dα [f∗Sn 6= f ∗(x)|g∗(x) ≥ 0] ≤ 2
=⇒Px∼Dα [f∗Sn 6= f ∗(x), g∗Sn(x) > 0|g ∗(x) > 0] + Px∼Dα [f∗Sn 6= f ∗(x), g∗Sn(x) ≤ 0|g ∗(x) > 0] ≤ 2 =⇒Px∼Dα [f∗Sn 6= f ∗(x)|g∗Sn(x) ≤ 0, g ∗(x) > 0]Px∼Dα [g∗Sn(x) ≤ 0|g
∗(x) > 0] ≤ 2 =⇒ { 1− Px∼Dα [f∗Sn = f ∗(x)|g∗Sn(x) ≤ 0, g ∗(x) > 0] } Px∼Dα [g∗Sn(x) ≤ 0|g
∗(x) > 0] ≤ 2 =⇒ Px∼Dα [f∗Sn = f ∗(x)|g∗Sn(x) ≤ 0, g ∗(x) > 0]Px∼Dα [g∗Sn(x) ≤ 0|g ∗(x) > 0]
≥ Px∼Dα [g∗Sn(x) ≤ 0|g ∗(x) > 0]− 2
=⇒ (1− θ)α 1− α Ex∼Dα [1{f∗Sn = f ∗(x)}|g∗Sn(x) ≤ 0, g ∗(x) > 0]Px∼Dα [g∗Sn(x) ≤ 0|g ∗(x) > 0]
≥ (1− θ)α 1− α { Px∼Dα [g∗Sn(x) ≤ 0|g ∗(x) > 0]− 2 }
(28)
Term 4:
E(x,y)∼Dα [ 1− θ 1− α 1{f∗Sn(x) = y}1{g ∗ Sn(x) ≤ 0}|g ∗(x) ≤ 0 ] Px∼Dα [g∗(x) ≤ 0]
= (1− θ)E(x,y)∼Dα [ 1{f∗Sn(x) = y}1{g ∗ Sn(x) ≤ 0}|g ∗(x) ≤ 0 ]
= (1− θ)E(x,y)∼Dα [ 1{f∗Sn(x) = y}|g ∗ Sn(x) ≤ 0, g ∗(x) ≤ 0 ]
∀x s.t.g∗(x)≤0,y is coin flip Px∼Dα [g∗Sn(x) ≤ 0|g ∗(x) ≤ 0]
= 1− θ
2
{ 1− Px∼Dα [g∗Sn(x) > 0|g ∗(x) ≤ 0] }
(29)
Combining Equations 25, 26, 28, 29 we have:
W (g∗Sn , f ∗ Sn , θ) ≥
{ θ(1− α)
2α − 1− θ 2 } Px∼Dα [g∗Sn(x) > 0|g ∗(x) ≤ 0] + 1− θ 2
+ α(1− θ)
1− α Px∼Dα [g∗Sn(x) ≤ 0|g ∗(x) > 0]− 2(1− θ)α 1− α
(30)
and by part I) in the theorem, we have with probability at least 1− 3δ:
W (g∗Sn , f ∗ Sn , θ) ≤ 2 θ + 2α + (1− θ) 2
Combined with the failure probability 2δ in the bound of Term 3 we have the failure probability at most 5δ: {
θ(1− α) 2α − 1− θ 2 } Px∼Dα [g∗Sn(x) > 0|g ∗(x) ≤ 0] + 1− θ 2
+ α(1− θ)
1− α Px∼Dα [g∗Sn(x) ≤ 0|g ∗(x) > 0]− 2(1− θ)α 1− α
≤ 2 θ + 2α + (1− θ)(1− α) 2
=⇒ { θ
2α − 1 2 } Px∼Dα [g∗Sn(x) > 0|g ∗(x) ≤ 0]
+ α(1− θ)
1− α Px∼Dα [g∗Sn(x) ≤ 0|g ∗(x) > 0]
≤ 2 θ + 2α + 2(1− θ)α 1− α
(31)
By picking θ = 2cα with 12 < c < 1+α 4α we can ensure that 1) θ 2α − 1 2 > 0; 2) α(1−θ) 1−α ≥ α 2 . Finally we have: { c− 1
2
} Px∼Dα [g∗Sn(x) > 0|g ∗(x) ≤ 0] ≤ 4cα + 4α
=⇒Px∼Dα [g∗Sn(x) > 0|g ∗(x) ≤ 0] ≤ 12cα
2c− 1
(32)
and α(1− θ)
1− α Px∼Dα [g∗Sn(x) ≤ 0|g ∗(x) > 0] ≤ 4cα + 2(1− θ)α 1− α + 2α
=⇒Px∼Dα [g∗Sn(x) ≤ 0|g ∗(x) > 0] ≤ 20c
(33)
Given hypothesis class H, one can bound the growth function GH(n) through its VC-dimension. Next we present the well known Sauer–Shelah Lemma below. Lemma 5 (Sauer–Shelah Lemma(See (Blum et al., 2016; Mohri et al., 2018; Sauer, 1972))). Let dvc(H) be the VC-dimension of hypothesis classH, for all n ∈ N,
GH(n) ≤ dvc∑ i=0 ( n i ) ≤ ( en dvc(H) )dvc(H) Now we are ready to prove the main result. Theorem 4. Under Assumption 1, given a set of samples Sn = {(x1, y1), ..., (xn, yn)} drawn i.i.d. from the Noisy Generative Process, hypothesis class H with VC-dimension dvc(H), F with VC-dimension dvc(F) and
f∗Sn = arg min f∈F RS(f), gSn ∗ = arg min g∈H WSn
( g, f∗Sn , 73
72 α+
α2
72
) ,
If α ∈ (0, 0.9) and:
n ≥ 128
[ (dvc(H) + dvc(F)) log(1ε ) + log( 16 δ ) ]
2α2
We have with probability at least 1− δ:
I) P[g∗Sn(x) ≥ 0|g
∗(x) ≤ 0] = O( ) [False Positive] (34) P[g∗Sn(x) < 0|g ∗(x) ≥ 0] ≤ O( ) [False Negative] (35)
II) Px∼Dα [f∗(x) 6= f∗Sn(x)|g ∗ Sn(x) ≥ 0] = O( )
Proof. I) above can be proved by observing c = 1+ 1+α 72
2 and applying Theorem 3 with Sauer’s Lemma
to bound the growth function in terms of VC-dimension. Also notice that c = 1+ 1+α 72
2 ∈ ( 1 2 , 1+α 4α )
given α < 0.9. II) can be proved by observing that I) implies P[g∗Sn(x) 6= g ∗(x)] = O(ε) and by invoking Theorem 1.
Remark 3. Let us point out that our proposed selective strategy is different from the consistent selective strategy in (El-Yaniv et al., 2010). Instead of rejecting by looking for consistent output from all hypothesis in the version space, our approach deals with one single reasonably accurate hypothesis (the empirical minimizer). We leverage empirical mistakes made by the predictor in order to learn a selector, aiming to reject (only) the mistakes in a data driven manner. This avoids dealing with the issues found in Theorem 14 in (El-Yaniv et al., 2010), where the selector fails to select any data points.
Remark 4. In (Cortes et al., 2016), a second hypothesis for the selector is introduced and analyzed, and at the same time, multiple commonly used loss functions are scrutinized and generalization results are provided. The major difference between this work and (Cortes et al., 2016; Geifman & El-Yaniv, 2019) is the motivation pertaining to selective learning. While in (Cortes et al., 2016; Geifman & El-Yaniv, 2019) the selective loss is designed from a coverage ratio perspective, i.e. one wants to trade coverage ratio for a higher precision (selective loss), our approach is designed to distinguish data that is naturally unlearnable and unpredictable. This difference leads to an alternative theoretical result. While the analysis in (Cortes et al., 2016) focuses on selective risk, our theoretical analysis focuses on the quality of the selector in terms of both the false positive and false negative errors with the final goal of rejecting uninformative data with high probability.

heading: C TIGHTNESS ANALYSIS
text: In this section, we investigate whether it is necessary to have Ω̃ ( dvc(H)+dvc(F)
α2 2
) samples to achieve
Px∼Dα [f∗(x) 6= f∗Sn(x)|g ∗(x) ≥ 0] = O( )
and max { P[g∗Sn(x) 6= g ∗(x)|g∗(x) > 0],P[g∗Sn(x) 6= g ∗(x)|g∗(x) ≤ 0 } = O(ε). We will show that there exists a distribution Dα among the Noisy Generative Process family and hypothesis class H,F such that achieving guarantees in Theorem 4 requires Ω̃(dvc(H)+dvc(F)α2 2 ) samples, thus making our analysis tight within logarithmic factor. Note that our lower bound is for empirical minimizers of R(f) and W (g, f, θ); it only illustrates the tightness of our analysis, and thus is not an information theoretic bound for this family of problem - it remains unknown whether strategies other than the empirical minimization of R(f) and W (g, f, θ) can improve sample complexity to a rate of 1αε , observing that the informative data is realizable, which usually only requiresO( 1ε ) samples for an statistical error. Our construction leverages the idea from (Ehrenfeucht et al., 1989) about the support of the informative data. Over the support of uninformative data, noise buries the signal of the informative data, thus misleading the empirical minimizer. In our analysis, we will leverage the anti-concentration results of the Chernoff bound, with the proof idea that comes from (Klein & Young, 2015):
Lemma 6 (tightness of the Chernoff bound). Let X be the average of k independent, 0/1 random variables (r.v.). For any ∈ (0, 1/2] and p ∈ (0, 1/2], assuming pk ≥ 6, pk ≥ 6, ε ≤ 13 , we have:
• If each r.v. is 1 with probability p, then
P[X ≤ (1− )p] ≥ e−6 2pk.
• If each r.v. is 1 with probability p, then
P[X ≥ (1 + )p] ≥ e−6 2pk.
Proof. The proof is similar to Lemma 5.2 in (Klein & Young, 2015) with a different choice of parameters. With Stirling’s approximation, i! = √ 2πi(i/e)ieλ with λ ∈ [1/(12i + 1), 1/12i] one
can show: ( k
`
) ≥ 1
e √ 2π` (k ` )`( k k − ` )k−` (36)
Also note: P[X ≤ (1− )p] = ∑(1−ε)p i=0 P[X = i k ].
Let ` = b(1− 2 )pkc. Given the fact that εpk ≥ 6, we have (1− 2 )pk − 1 ≤ ` ≤ (1− 2 )pk. It suffices to lower bound ∑(1−ε)p i=(1−2ε)p P[X = i k ] which is at least εpkP[X = ` k ]. From Equation 36 we know that we need to bound A = 2e pk/ √ 2π` and B = ( k ` )`( k k−` )k−`
p`(1− p)k−`. For term A, since εpk ≥ 6, l ≤ (1 − 2ε)pk thus we need pk ≥ 9e −2ε ε to get 2ε √ pk e √ 2π(1−2ε) ≥ e−ε2pk. Since ε ≤ 13 , it suffices to have pk ≥ 16. To bound B we need to show:( k
`
)`( k
k − l
)k−l pl(1− p)k−l ≥ e−4ε 2pk
Since ( k ` )` p` ≥ ( 1 (1−2ε) )l and (1− p)k−l ( k k−l )k−l = ( (1−p)k k(1−p)+1+2εpk )k−l we have:
(1− 2ε)` ( 1 + 1 + 2εpk
k(1− p)
)k−` ≤ e− 4ε2p2k 1−p +2εpk−2εpk+4ε 2pk+2 ≤ e5ε 2pk
We consider the following distribution. Let dvc(F) = d and ej be the standard basis with jth coordinate equal to 1 and 0 otherwise. We set ΩjU = {+2,−2} · ej ,ΩU = ∪dj=1Ω j U and ΩjI = {+1,−1} · ej ,ΩI = ∪dj=1Ω j I . Let F = sign(w>x) and H = 2 ∏n i=1 gj(x) − 1, where gj(x) ∈ {1{|e>j x| ≥ c} ∪ {0},1{|e>j x| ≤ c}}. By Lemma 3.2.3 in (Blumer et al., 1989) we know dvc(H) ≤ 6d log(d). We construct Dα as follows: in ΩU , each standard basis has 1−αd mass with sign generated via coin flipping (fair). Having generated x, y ∈ {+1,−1} is generated via a coin flipping. In ΩI , we put α(1 − ε) mass on e1 and αεd−1 mass on other standard basis ej , with sign generated via a (fair) coin flipping. Having generated x, y ∈ {+1,−1} is generated via sign(w∗>x) where w∗ denotes a vector of ones. The above construction allows one to calculate the expected error by counting the number of basis that are not learned correctly, i.e., each j ∈ [d] s.t. wj < 0 implies an error αε2(d−1) in expectation. Since:
ESn∼Dα [|Sn ∩ Ω j I | |] =
αεn
d− 1 ,
by Markov inequality we have :
PSn∼Dα [|Sn ∩ Ω j I | | ≥
6αεn d− 1 ] ≤ 1 6 .
Also note that Ex∼Dα [1{x ∈ Ω j 1}1{x = −2ej}] = 1−α2d . In order to derive the probability that wj < 0 via empirical minimization, we need to bound the following probability:
Px∼Dα [ ∑
xi∈Ωj1,e>j xi<0
yi − ∑
xi∈Ωj1,e>j xi>0
yi ≥ 6αεn
d− 1 ]
To do so, we consider the following nj random variables that are conditioned on x ∈ Ωj1: zi = 1 if e>j xi < 0, yi = 1 or e > j xi ≥ 0, yi = −1 and zi = 0 otherwise. One can see 2 ∑ i∈nj zi − nj =∑
xi∈Ωj ,e>j xi<0 yi − ∑ xi∈Ωj ,e>j xi>0 yi. Thus :
Px∼Dα [ ∑
xi∈Ωj ,e>j xi<0
yi − ∑
xi∈Ωj ,e>j xi>0
yi ≥ 6αεn
(d− 1) ]
≥Px∼Dα [ (1− α)n d − √ 3(1− α)n d ≤ |Sn ∩ Ωj1| ≤ 3(1− α)n d ]
· Pz∼Sjn [ ∑ zi∈Sjn zi − nj 2 ≥ 3αεn (d− 1) | (1− α)n d − √ 3(1− α)n d ≤ nj ≤ 3(1− α)n d ]
≥1 2 Pz∼Sjn [ 1
nj ∑ zi∈Sjn zi − 1 2 ≥ 3αεd (d− 1)(1− α) | (1− α)n d − √ 3(1− α)n d ≤ nj ≤ 3(1− α)n d ]
≥ 1 2 e−18α 2ε2nj ≥ 1 2 e− 54α2ε2n d
(37)
If n ≤ d432ε2α2 , we have for each j, with probability at least 0.40, wj < 0 due to the empirical minimization strategy. Each wj < 0 contributes αε2(d−1) risk in expectation. With probability 0.2, 20% of coordinates can not be learned correctly, thus resulting in a risk of at least 0.1εα in expectation. Next we show that the selector is going to suffer from a poorly learned classifier in terms of its false negative rate. Now lets focus on the case when E(x,y)∼Dα [fSn(x) 6= y] ≥ 12 (1− α) + 0.1αε (which happens with probability at least 0.2), we will show that Ex∼Dα [1{gSn(x) 6= g∗(x)}|g∗(x) > 0] ≥ 0.1ε. Let J1 be the set of j’s s.t. wj < 0 and J2 for wj > 0. Suppose θ > α, and consider empirical minimization:
min g∈H
WSn(f ∗ Sn , g, θ) ≥ d∑ j=1 min g∈H WSn∩Ωj (f ∗ Sn , g, θ) (38)
For j′ ∈ J1, g ∈ arg min g∈H WSn∩Ωj′ (f ∗ Sn , g, θ) if gj′(x) = 1{|ej′>x| ≥ c}, c > 2 (and for other basis j, gj can be arbitrary). For j′ ∈ J2, g ∈ arg min g∈H WSn∩Ωj′ (f ∗ Sn , g, θ) if gj′(x) = 1{|ej′>x| ≤
c}, c ∈ [1, 2). Now consider g∗Sn = 2 ∏d j=1 gj(x) − 1, gj(x) = 1{|e>j x| ≥ c} with c > 2 if j ∈ J1 and gj(x) = 1{|e>j x| ≤ c}, c ∈ [1, 2) if j ∈ J2. One can see that such g∗Sn is in the intersection of set of minimizers of WSn∩Ωj (f ∗ Sn , g, θ) thus attains the minimum. The total mass of x s.t. g∗Sn(x) 6= g ∗(x) is at least |J1|αεd−1 since for all x ∈ Ω j with j ∈ J1, g∗Sn(x) 6= g ∗(x). The event E : E(x,y)∼Dα [fSn(x) 6= f∗(x)] ≥ 12 (1 − α) + 0.1αε happens with probability at least 0.2 which implies that |J1| ≥ 0.2d. Thus we have following lower bound on the False Negative:
Px∼Dα [g∗Sn(x) 6= g ∗(x)|g∗(x) > 0] ≥ 0.1ε.

heading: D SUPPLEMENTAL MATERIAL FOR EMPIRICAL STUDY
text: Extension to Multi-class. Our method extends to multi-class setting naturally. In the case ofK-class classification, we predictors f(x) = f(x)1:K : X → ∆K where ∆K is theK-simplex. In multi-class scenario, our selector loss remains the same. Meanwhile, we use multi-class cross entropy loss to train classifier. The pseudo-informative label becomes zi = 1{arg maxk∈[K] f(xi)k = yi}.
Experiment setting with Unknown α (More Details). For MNIST/Fashion-MNIST experiment, the backbone model we use for each candidate is TinyCNN, which is a CNN with two consecutive convolution layers and 3 consecutive fully connected layers. This architecture provides enough model capacity for an MNIST-type dataset. We use 196 as the batch size. We use Adam as the optimizer with learning rate 1e-3 and weight decay 1e-4. We train with each algorithm for 162 epochs. We use the default hyper-parameters for every method (i.e., internal selective learning-specific defaults, as reported in (Geifman & El-Yaniv, 2019; Liu et al., 2019), and β = θ(1−α)α(1−θ) for our algorithm). It simulates a practical scenario where hyper-parameter optimization is impossible, since the ground truth regarding which datapoints are actually learnable is never revealed. For the SVHN experiment, the backbone model we use is ResNet18 (He et al., 2016b) for every candidate. We use 128 as the batch size. We use Adam as the optimizer with learning rate 1e-3 and weight decay 1e-4. We train each algorithm for 162 epochs.
Weight of Informative data. From Figure 3, we can see that our algorithm can pick out almost all informative data by the end of training for all informative/uninformative ratios even without knowing the ground-truth α.
(a) MNIST. Weight on Informative Data (b) SVHN. Weight on Informative Data
Figure 3: Weight of informative data as a function of training epoch and the ratio of informative data.
The y axis is the percentage of weight put on the iformative data, i.e
∑
i:xi∈ΩI
γi∑n i γi
in the notation of Algorithm 1. Each experiment is repeated 3 times, and 3 standard deviations are presented as the shaded gray area.
Experiments with Known α. We also test the performance of each method in the idealized case. In this experiment, we give the groud-truth α to each baseline and perform an exhaustive HPO (Hyper Parameter Optimization). We use the same backbone, optimizer and the number of training epochs as before. We run a random hyper-parameter search 500 times (selective loss weight and parameter λ for SelectiveNet and parameter o in DeepGambler) and record the best performance of each baseline. In this setting, our method still outperform baselines for most levels of noise ratios. In this experiment, we use two stage training for our algorithm. We first run 120 epochs to finish 1st round data selection and then run 42 epochs to train a classifier only with these selected data. The performance is measured with this refined the classifier.
Experiment with Low Ratio of Uninformative Data. We also conduct experiments with datasets that contain minority stochastic data. This experiment is conducted under both practical (unknown α) and idealized scenario (known α). In practical setting (unknown α), our proposed algorithm still wins by a large margin. In the case when α is known, DeepGambler outperforms other methods in
most cases. We hypothesize that when noisy data minority, our method doesn’t get enough samples to fully learn the pattern of uninformative data.
D.1 EXPERIMENT WITH KNOWN α
D.2 EXPERIMENT WITH LOW RATIO OF UNINFORMATIVE DATA D.3 IMPLEMENTATION DETAIL
For all our experiments, we are using NVIDIA Tesla V100 GPUs, and we use AWS Sagemaker service for our HPO processes. We repeat each experiment 5 times with random seed 77, 78, 79, 80, 81.
For MNIST/Fashion-MNIST experiment where α is unknown, the training and testing data set split is listed in Table 11. The backbone we use is TinyCNN (in section 4). We use 196 as our batch size and train for 162 epochs for all listed methods. We use Adam as the optimizer with learning rate 1e-3 and weight decay 1e-4. We shrink our learning rate at epoch 45 and 90 by half each time.
For SVHN experiment where α is unknown, the training and testing data set split is listed in Table 11. The backbone we use is ResNet18. We use 128 as our batch size and train for 162 epochs for all listed methods. We use Adam as the optimizer with learning rate 1e-3 and weight decay 1e-4. We shrink our learning rate at epoch 45 and 90 by half each time. For both experiments where α is known
and HPO is enabled, we maintain the same backbone and optimizer. The hyper-parameter setting is documented in the code. The code will be open sourced together with the publication of the paper.

heading: E EXTENTION OF THEOREM 4 IN THE CASE WHERE ONLY AN UPPER BOUND
text: ON α IS GIVEN
Theorem 5. Under Assumption 1, given set of samples Sn = {(x1, y1), ..., (xn, yn)} drawn i.i.d. from the Noisy Generative Process with α ∈ (0, 1 − ξ], ξ ≥ 0.2 , hypothesis class H with VC-dimension dvc(H), F with VC-dimension dvc(F) and f∗Sn = arg minf∈F RS(f), gSn
∗ = arg min g∈H
WSn ( g, f∗Sn , θ ) . If θ ∈ ( 73α 72 ,min{1 + ξ 2(1−ξ) , 10}α ) and
n ≥ 3200[(dvc(H)+dvc(F)) log( 1 ε )+log( 16 δ )]
2α2 . We have with probability at least 1− δ: I)
P[g∗Sn(x) ≥ 0|g ∗(x) ≤ 0] = O( ) [False Positive] P[g∗Sn(x) < 0|g ∗(x) ≥ 0] ≤ O( ) [False Negative]
(39)
II) Px∼Dα [f∗(x) 6= f∗Sn(x)|g ∗ Sn(x) ≥ 0] = O( )
III) Further more, to obtain gSn ∗ = arg min
g∈H WSn
( g, f∗Sn , θ ) it suffices to minimize following
loss with β ∈ (1 + 173ξ−1 ,min{1 + ξ 2(1−ξ) , 10}):
Loss(g; f∗Sn , Sn, β) = n∑ i=1 { β1{f∗Sn(xi) 6= yi}1{g(xi) > 0}+ 1{f ∗ Sn(xi) = yi}1{g(xi) ≤ 0} } Proof. I) above can be proved by picking c ∈ ( 12 + 1 144 , 1 2 +min{ 9 2 , ξ 4(1−ξ)}) in Theorem 3. Note this range is valid since α ≤ 1− ξ, we have
α ≤ 1− ξ ⇐⇒ α 1− ξ ≤1 ≤ 1− α ξ ≥1
⇐⇒ ξ 1− ξ ≤ 1− α α
⇐⇒ ξ 2(1− ξ) ≤ 1 + α 2α − 1
⇐⇒ ξ 4(1− ξ) + 1 2 ≤ 1 + α 4α
(40)
By a procedure similar to Theorem 4 (using the Sauer’s Lemma) we have I). Note c ∈ ( 12 + 1 144 , 1 2 + min{1, ξ4(1−ξ)}) ⇐⇒ θ ∈ ( 73α 72 ,min{1 + ξ 2(1−ξ) , 2}α ) . II) can be proved by observing that I) implies P[g∗Sn(x) 6= g ∗(x)] = O(ε) and by invoking Theorem 1. Next we prove III). It is easy to verify that the minimizer of WSn(g, f ∗ Sn
) is equivalent to minimizer of Loss(g; f∗Sn , Sn, β) (by replacing β = θ(1−α)α(1−θ) ). It suffices to analyze that β ∈ (1+ 1 73ξ−1 ,min{1+ ξ 2(1−ξ) , 10}) implies that
θ ∈ (
73α 72 ,min{1 + ξ 2(1−ξ) , 10}α ) . First note that x1−x is monotone increasing in (0, 1), it suffices
to compute image of θ(1−α)α(1−θ) and check if β ∈ (1 + 1 73ξ−1 ,min{1 + ξ
2(1−ξ) , 10}) stays in such range. It can be easily verified that α ≤ 1− ξ implies the lower bound 1 + 173ξ−1 and α > 0 implies the upper bound 1 + ξ2(1−ξ) .

heading: F ABLATION STUDY ON HYPERPARAMETERS
text: We provide an ablation study where we vary the hyper-parameter in each baseline. For SelectiveNet, we first fix λ to be 32 (default setting that is recommended by the author in the original paper) and then we vary a from 0.1 to 0.7. Then we fix a to be 0.5 (default setting) and then we vary λ
from 1 to 66. For DeepGambler, we vary o from 1 to 7. Finally, for our algorithm, we increase the hyper-parameter β 4 to 10. We can see that the performance of all baselines are quite sensitive to the choice of hyper-parameter and will experience some large fluctuation. On the contrast, our algorithm is stable against the choice of hyper-parameter. This empirical observation supports that there exists a wide range of β so that one can control the FNR and FPR if α is bounded away from 1 as it is implied in Theorem 5. Furthermore, in all scenario, our algorithm’s performance is better than these two baselines in two sense. On one hand, our selector has better precision such that we can recover almost all informative data while the other two cannot. These two baseline tend to to select the whole data set indistinguishably (low precision and high recall). On the other hand, these baselines show consistently deteriorated risk performance than ours because of their selector fails to pick informative data.

Review summaries:
The paper is concerned with selective classification in a stylised 'realisably noisy' data model, wherein the support of the input distribution is partitioned into two chunks, the "informative" $\Omega_I$ and the "uninformative" $\Omega_U,$ such that  - The labels are completely noisy ($\mathrm{Bern}(1/2)$) if the input lies in $\Omega_U$. - The labels are completely clean if the input lies in $\Omega_I$. - The learner has access to hypothesis classes $\mathcal{F}, \mathcal{H}$ such that      - There exists an $f^* \in \mathcal{F}$ with $f^*(x) = y$ on $\Omega_I$.     - There exists a $g^* \in \mathcal{H}$ with $g^*(x) = 2\mathbf{1}\{x \in \Omega_I\} - 1.$  The paper studies the problem of learning a pair $(f,g),$ with $g$ serving as a selector, and $f$ as a predictor, such that $g \approx g^*$ and $f \approx y$ on $\{g \ge 0\}$ (and $\approx f^*$ on $\Omega_I$ if $g$ is learnt well), with the concrete goal of attaining both small selective risk ($P(f^*(x) \neq y|g(x) \ge 0)$) and both low false alarm and low missed detection for $g$ with respect to $g^*$. As is standard in selective classification, supervision of the value of $g^*$ is not given, and instead only $(x,y)$ pairs are provided.  This is approached by designing a new loss for learning a selector given a predictor $f$, denoted $W(g;f, \theta)$, that basically uses $\mathbf{1}\{f(x) = y\}$ as proxy supervision for when $g < 0$ or $g > 0$ is preferred, but weighted by a factor to account for the prevalence of uninformative versus informative data. It is first shown, using uniform convergence techniques, that if the indicator ERM problem can be solved, then given  if $f^*_{S_n}$ is taken to be a minimiser of standard empirical risk, and $g^*_{S_n}$ to be the minimiser of an empirical version of $W(g;f^*_{S_n}, \theta)$ for appropriately chosen $\theta$ (in a way which depends on the prevalence of informative data $\alpha$), then these goals can be attained in a PAC sense, with sample complexity scaling as $\tilde\{O\}( \frac{d_\{\mathrm{vc}\}(\mathcal{F}) + d_\{\mathrm{vc}\}(\mathcal{H}) }{\epsilon^2 \alpha^2})$.  The paper then switches gears, and a alternating minimisation based heuristic method for practically learning $(f,g)$ is proposed. The idea is to first learn (soft functions) $f$ and then $g$ using relaxed versions of the above losses, and then multiplicatively increase the weight of points that are selected by the $g$ in their contribution to the loss for $f$, and repeat. The remainder of the paper is devoted to empirical evaluation of this method in two situations - firstly, uniformative (randomised labels) MNIST data is given along with varying amounts of clean Fashion MNIST data; and secondly, part of the classes from the SVHN dataset have their labels randomised to represent uninformative data, while the rest remain clean. While the scheme is observed to have similar performance in how well the selector identifies the underlying $g^*$, the proposed method has remarkably better selective risk compared to baselines from the recent selective classification literature.

This paper considers supervised learning with abstention -- where the learning method can decide to make prediction in some region of the feature space, and declare the rest of the feature space unpredictable. The setting is related to but different from the classical selective prediction, and to prediction uncertainty quantification (i.e. imbuing predictions with calibrated confidence intervals). Classical selective prediction balances coverage vs. accuracy -- whereas in the setting here the authors assume that there is a "true" split into an informative and uninformative partition of the feature-space,  and the goal is to both recover the partition and learn a good model on the informative partition.  The paper focuses on theoretical analysis, and also has experimental results suggesting that if the data is generated according to the author's model, than a heuristic algorithm inspired by the analysis indeed outperforms other selective prediction baselines.