Learning to Abstain in the Presence of Uninformative Data
Authors: Yikai Zhang
Songzhu Zheng
Pengxiang Wu
Yuriy Nevmyvaka
Chao Chen
Venue: ICLR 2022 Submitted (2022)
Keywords: Selective learning
Uninformative data
PAC Learning
Sample Complexity

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.

Under review as a conference paper at ICLR 2022
LEARNING TO ABSTAIN IN THE PRESENCE OF UNIN- FORMATIVE DATA
Anonymous authors Paper under double-blind review
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 impor- tant. In this paper, we study problem of learning on datasets in which significant proportion of samples does not contain useful information. To analyze this setting, we introduce noisy generative process with a clear distinction between uninfor- mative/not learnable/purely random data and a structured/ 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 loss inspired by the selective learning theory. By minimizing the loss, our method guaranteed make near-optimal decision by simultancously 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 iterative algorithm, which jointly optimizes both a predictor and a selector, and evaluate its empirical performance under a variety of conditions.
INTRODUCTION
Despite the success of machine learning in computer vision (Deng et al. 2009 Krizhevsky et al. 2009: He al. [0166a] Huang et al., (017)) and natural language processing (Vaswani al.) [0177] 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 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/nott 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., datasets
2010). Therefore, naïve forecasts in magjoity--niiforman Compared to other learning methods, deep neural networks are even more affected by the presence of noise, due to their strong memorization power (Zhang al. 2017]; they are likely to overfit the noise and make overly confident predictions where no real structure exists.
doomed to be unreliable.
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 decide whether a datapoint is informative or not. successful, the method abstains from making decisions where no structure exists, and predominantly learns from the remaining predictable data.
Our idea 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. pursues 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 such data. Our goal is to identify these uninformative samples as well as possible, and at the same time, to train classifier by minimizing conditional risk on the remaining informative data.

---

Under review as a conference paper at ICLR 2022
Our method learns both a predictor, f. that classifies samples, and 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 structuree/iifooratti 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,
therefore must rely the predictor's mistakes to train the selector. To achieve this goal, we propose a novel selector loss enforcing that (I) 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/ifoormaivee data in 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, 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 's output: uninformative or uuuryyyunifoomatiiee 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 left as future work.
1.1 RELATED WORK
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
al. 2020). bounded label noise Massart Nédélec [006]] Awasthi al. [015 Diakonikolas
iet al. 2019 | and adversarial noise (Kearns & Li 1993] Kearns et | 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., [217]] Diakonikolas et al.. 2018). where the best one can do when the proportion of trusted data is less than 0.5, is to return 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 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, 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 20177] | [Pearce et al. (2020). margin based methods (Fumera & Roli [202)] Bartlett Wegkamp 2008; Grandvalet et al. [2008] Wegkammp et al.] 201T Zhang et al. 2018). confidence based methods (Wiener& & EI- Yaniv| [ Geifman & EI- Yaniv | 2217:piam et al. 2018) and customized selective loss (Cortes et al. (2016] Geiffan & EI- Yaniv 2019 et al. 2019). Notably, several works propose customized losses, and incorporate them into neural networks. In (Geifman & El- Yaniy 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. (2066) perform data selection with an extra model and introduce a selective loss that helps maximize the coverage ratio, thus trading off small fraction of data for better precision.
2

---

Under review as a conference paper at ICLR 2022
Existing works selective prediction are all motivated from the coverage perspective i.e. one wants to make safe prediction to achieve higher precision while maintain reasonable recall (EI- Yamiv et al. 2010). Whereas paper is the first investigate the case where some (or even majonty) of the data is uninformative, and thus must be discarded at prediction time. Unlike with the selective prediction, there is latent ground truth indicator function of whether datapoint should be selected not. Our method is guaranteed to identify those uninformative samples.
PROBLEM FORMULATION
In this section, we describe the inherentlynnois data generation process that we aim study. The model has three important features: 1) the uninformative portion of the data has labels generated by coin flipping; the informative datapoints are labeled with latent ground truth function; and 3) the uninformative data has distinguishable support from the informative data. Formally:
Definition 1 (Noisy Generative Process). We define Noisy Generative Process by the following notation I Do where
x Du
with prob. - a with prob. a
(Uninformmaivv/Noissy Data)
D. =
(1)
Dr
(Informaaive//trrctuued Data).
Let UD S Ra be the support of Dr- Suppose {Rg J2y } is partition of Ωdp the ground truth labeling function f" {+1, -13 is in hypothesis class F and data is sampled according to:
(0.,) if x E Sw x ~ Daiy y = (x)x).
i E LD
Note that the f* is defined on the whole domain, although only the part within 22 relevant. a represents the fraction of informative or structured data in the population. For the rest of the paper, we abuse the notation and use (z, 3) ~ 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 (H-Sepprablle.. Given compact set f2 and its partition {Rgr 2r,, (Rv, satisfies H- H-Separable condition if there exists g" E H satisfying 9" (x) X - [+1,-1}
-1, if Z
g'(x)
1, if E Ωz.
One can view g-()) 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 Vi is i..dd generated according to the Noisy Generative Process (Definition) 7 with f E F, support PD... = 2trUn, where 94y S2 are H-Separable.
Throughout this paper, we are interested in the following learning task:
Problem 1 (Abstain from Uninformative Data). Under Assumption Dwith 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 class H. aim learn the selector g" (x))
Evaluation metrics. We define metrics to evaluate the quality of both the prediction and the selection. For the prediction, borrow the selective risk definition from selective learning (El-Yaniv al. 2010 Geifman & El- Yaniv 2019; 2017) using our own notation.
Definition 3 (Selective Risk). Given a predictor f E F and a selector E H. we define the selective risk as: CR(f.g E B [f((z) + v)lg(x) 2 0) and its empirical version:
CRs(f.9)= Dn ΣT 22()))20)
Selective risk measures the average risk conditioned on instances that are picked by the selector g(z). Note here when combined with the ground truth selector 9* the selective risk of the ground truth
3

---

Under review as a conference paper at ICLR 2022
predictor f* goes to zero. Without selector, however, f has classical classification risk (which will be formally defined in Definition 5 later) of more than ( (1-a).
The metric used to evaluate the quality of learned selector g is its false positive/negative rate. When g(x) 2 and g" (x) < O, the selector accepts an uninformative datapoint and thus commits a false positive error. When g(x)) < 0 and g (ar) 2 g rejects/abstains from informative datapoint resulting in a false negative error.
Definition (Evaluation Metric for the Selector). Given distribution Da as defined in Defiiition and 9" target selector, denote the false positive and false negative of a selector g
False Positive: (()( 2 0gg² (x) 0]; False Negative: P(g(()) 00g (x)
3
OUR METHOD
In this section, we present our approach for learning and abstaining in the presence uninformative data (Problem T. The main challenge is that the latent Informaiive/uninformati status of datapoint unknown. Our main idea to introduce novel selector loss function that trains a selector based on the performance of the best predictor (Section 3.1p. In Section 3.2 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, risk and selector eтror rates. During the analysis, we assume an oracle is given for the empirical minimizer. Approximating such empirical minimizer 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
solve Problem [ with controlled selective
we propose 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 (Classification Risk). We denote the classification risk of model as
R()) B(,,))DD (z(x) # v}l
(5)
and the empirical classification risk: (s) 1 Σ. 1(f(x;) # v.). We define fš, to be the empirical minimizer of R.s, (f): f3. = arg min Rs, (f).
3.1 SELECTOR Loss
To learn selector without direct supervision, we have to leverage the performance of given predictor, f. We propose the selector loss, which reweigh the 0-1 loss based on the prediction of This loss penalizes when (I) the predictor makes correct prediction on a datapoint that the selector considers uninformative and abstains from, or (2) the predictor makes an incorrect prediction on datapoint that the selector considers informative.
Definition 6 (Selector Loss). Given f E F and its selector H. we define the following weighted type risk w.rl g() as selector risk:
[\)((a)))) Hom) so}
1-0 -
W W(: f. (a.))D
+1((() # # > 0) +
and its empirical version:
1 11((()) 4 #wd 0) 1 -((x))== (1( 50 (6) Ws. (g: (.0) = - n1
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 rreudo-informatt label is -edependent, the quality of f is crucial for successfully learning g. In the theoretical analysis, leverage the fact that predictor f is close enough the ground truth predictor f*
label given by the predictor, 1 [ff(x)
y). Since such
4

---

Under review as a conference paper at ICLR 2022
Note that there two types of errors penalized in the selector loss: incorrect prediction an informative datapoint, (f(z) * y) A (g(x) > 0), and a correct prediction on an uninformative datapoint, (f(z) = y) A (9(z) & 0). We use 31 = & and B0 = 1- to weigh these two types of error in the loss. Both By and frr are controlled by a parameter and the latent informative data proportion a. We show that for wide range of 0, the accuracy of the selector is guaranteed, long as a is bounded away from 1, i.e. when abstention is necessary. In practice, we can adjust 5 and By freely without knowing exact value of a, empirical performance remains stable with regard to these choices.
I-a
Learning a selector with the novel loss. In an ideal setting, learn selector, first estimate the predictor by minimizing the classification risk, f3. = arg min Rs,,()) Next, we esti- mate the selector by minimizing the selector loss, conditioned on the estimated predictor, fás,, G3 arg gen Ws. f3. .). In Figure 1 we show an example of using the empirical mini- mization 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 f3. and Js can be computed exactly. Our analysis in Section 3.2 will show that the estimated predictor f3., and selector g has bounded selective risk (as in Defimiton 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
Unirommatio
Dooue) Tuth yel Doooal tuth yen
Domeett votarie Croiaee
extive Prodict
extie Regection
(a) Mix of learnablc and not learaalle data
Ourput (2)
(c) Concc/Incorcee classification
(d) Output of selector 83, (x)
(c) Selective
(Lngisric Regression)
classificarion result
Figure I: Illustration of the learning strategy in ideal setting, using synthetic (uniformly distributed noise) data. We replace the 0-1 loss with cross-entropy loss and train logistic regression models for both f and g. (a) shows that the informative and the uninformative supports are separated. (b) demonstrates that the model derived with majority-uninformanl the informative portion. (c) shows that the predictor has high accuracy in the informative region, but low accuracy in the uninformative region. In (d) and (e), the selector trained with fš.. successfully recovers informative support thus resulting low selective risk.
data has reasonable performance on
3.2 THEORETICAL ANALYSIS
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š, = arg min Rs, (f) and selector g3., = arg min Ws. (g. fš., A) are sufficiently close 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 F Fzr...... (f(zz),... (Tr,) ʃ E F) C (11,-1 The growth function is defined to be the maximum num- ber of ways in which points can be classified by the function class: Gz(n) sup | Fzrmnttal
Theorem is standard PAC Learning analysis where show f3 is sufficiently close to the ground truth Tunction f". Note that our analysis does not imply efficient PAC learning since optimizing binary loss is NP-hard. In Theorem [ we bound the statistical error of the selector loss. In Theorem data are distinguishable,
Roadmap of the proof:
3 we leverage the fact that informative and uninformative portions of the
well the fact that f&. has low risk on informative data. This lets us bound the selector loss of gs., given by W (9'S,) -3,,-0 0). By carefully balancing the weight parameter
5

---

Under review as a conference paper at ICLR 2022
8 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 i Lemma (Sauer 1972) to bound the growth function of hypothesis classes in Theorem The toolkit we use is driven by the concept of
VC-dimension in (Vapnik & Chervonenkis, 2015 Blum et al.) 2016 Mohri et al. 2018). We also
provide lower bound construction in the Appendix to show the (near) tightness of our analysis (up to logarithmic factor). We present all the results below, detailed proof' are in the Appendix.
We first prove a theorem about sample complexity of the learning hypothesis optimized over a given dataset, referred to as J'. We show that it approximates the ground truth function f* well.
Theorem 1. Under Assumption 7 given hypothesis class F, a set of samples Sn = {021, y1),,.., ..... (Zn, }n)) drawn i..d from our Noisy Generative Process and f's.
arg mig fer Rs) suppose n. > 3=]log(418)(2m)))) R(fs.) [1 a) + 2ca. Furthermore, PA-D, [f* * f3. (1)) 2c.
then with probability at least 1 28,
cto2
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. J) E H x F, which explains the term |9 ( in the bound for n. the minimum number of sample points.
[g>
Theorem 2. Given hypothesis class H. F, a set of samples Sn = (111 ..., (I yn)) drawn i.i... from the Noisy Generative Process and f's.. = arg argmingee SEF Rs(S),, ((]))))). 9s."" arg min Ws, J'.. O),
gEH
i E (a, 1), E 10,1) and n 2 (20g(1o(4) (2n)) GJ (2(m)))
with probability at least 1 8,
WWs... 0) - Ws. (9S,, f3., 0) S Ea.
Theorem 3 combines the results in Theorems and 2 It shows that, by carefully choosing weight parameter 8, 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 f. We characterize the relationship between 0 and a using variable e = 2a
0 in the theorem and prove that for a wide range of
the false negative rate (FNR) and false positive rate (FPR) are controlled. Intuitively, a larger value of 0 in Ws, (g. JS.,0) implies a higher penalty on the false positive error.
Theorem 3. Under Assumption 7 given set of samples Sn = ([((I111))) from the Noisy Generative Process and I's.. = arg mingerr Rs(J),9s. arg min s,. (g. S3. O),
(1); .., (Fn, Un)) drawn iidd
9EH
O E (a, 1),a a E (0. 1) and n 2 326 [oge GN Gx) (Z00) (200))) if 2ea with 1 < c < 1+0
c²aa
4a
we have with probability at least 1 5:
12cne
Plgs., (z) 2 0lg" S 0] 5
[False Positive]
2c -
P Pla', (z) < 0lg" (x) 2 0] S 20ce
[False Negative]
Next theorem is a formal statement of the main result. is worth mentioning that the theorem assumes that is bounded away from 1, due the fact that when almost all data is informative, there is no need for abstention.
Theorem 4, Under Assumption I given set of samples Sn = ((11)))) (En, yn)) drawn i.i.d. from the Noisy Generative Process, hypothesis class H. with VC-dimension dye (H), F with VC- 73a 72
dimension (F) and S'S. arg ming Rs(J), arr min Ws., [9.
-2) if
9EH
E (0,0.9) and n 2 128 125( (20 log( Hoog 19) We have with probability at least 1 - 6:
I)
Plysš, (w) 2 (x)
s 0 = =(t) [False Positive]
(8)
Plgg, (x) (x) 2 0 s Oc)) [False Negative)
!I)
P PawD. 15 (x) # S3 (z) Iss (x) 2 0] O(c)

---

Under review as a conference paper at ICLR 2022
We provide lower bound construction in the appendix show that our bound in Theorem is tight up to a logarithmic factor. Note that our lower bound is for empirical minimizers of R(f) and W (g. f. 0). therefore the tightness result is not 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 2013 El- Yaniv et al. 2010,, can improve the sample complexity to a rate of (z)) Note that the informative portion of the data (drawn with probability a) by isself only requires 2 samples for an e-xxcessive statistical error. It turns out that our analysis for empirical minimizer is nearly tight, and that the number of samples O (ल)े)) is indeed necessary because the presence of noisy data makes our problem harder.
Remark 1.
Remark 2. Theorem 4 says that by minimizing the empirical version of the loss from Definitions o one can achieve the goal of simultaneously selecting and learning with noisy data i.e. the classification model fs. has sufficiently low selective risk, and the selector I's.. can distinguish informative data from non-informative. The analysis of the selector loss ( (Theorem 3 relies on the quality of the classifier fs... But since we know that gss, is able to abstain from uninformative data, we can retrain fs.., on the informative portion only. therefore guaranteeing its accuracy. Such circular logic naturally leads to a pructical iterative algorithm that we present in the next section.
3.3
A HEURISTIC ALGORITHM IN PRACTICE
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 I. 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 s output. See Algorithm D for the pseudo-code. A pictorial example of Algorithm [
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 ʃ. we turn to a so-called soft abstention scheme: use weight vector that progressively down-weighs samples abstained by g. in the spirit of multiplicative weights algorithms (Cesa-
& Lugosi 2006 Arora et al. 2012). Specifically, we increase the weight of i-th sample "/ if the selector accepts Jy % (1 + (1;;;; > 0.5}) and then normalize so that Σx= % = 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 infuud--ifrrmttive labels to control the
output by the predictor. We also use a single hyper- hyper-paranen parameter / = Br/Bu = a( (1
8(1-a)
ratio of the two types of errors. As suggested by Theorem 3 small selector FPR and small selector FNR can be achieved by a 8 E (1, 1 2). For a scenario when abstention is necessary, i.c. when the noisy data ratio is in reasonable range, can choose our
from wide interval.
Algorithm 1 Iterative Soft Abstain
Require: Data set S, = { "...... (In, Bn))) weight parameter; 3, random initial fo and go, initial sample weights 7, Vi [n], meta learning rate n) number of iterations T
1: for + 1,.... do
2: Optimize loss to update predictor /' of {y, log (x;((((;)))) + (1- 14 log(1 f(x))))
3: Approximate the "pseudo-informatio label' : 2 {({ 0.5) = =
4: Optimize loss to update selector g²: E ( log(g(z;)) + +3(1=2))oog( ((x:))}
5: Update sample weights using g¹: 7/ En 100t
(1+mm (o
6: end for
7: Output f", /F.9T
4 EXPERIMENTS
Datasets. We test the efficacy of our heuristic algorithm (Algorithm 1p. via semi-synthetic experi- ments. 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)
7

---

Under review as a conference paper at ICLR 2022
et al. 1998) and Fashion-MNIST (Xiao et al. 2017p. We uniformly shuffle the labels of MNIST images and keep original labels of Fashion-MMNSS As a result, images from MNIST are uninforma- tive 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 proxy for 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 & EI- Yaniv, 2019). which integrates an extra neuron as data selector in the output layer and also introduces a loss term to control the coverage ratio; (2) DeepGambler (Liu ct 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 Metries. 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 & EI- 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, o, is unknown to all methods. This necessary in practice; the ratio and strength of noise are not known in most real world scenarios. For SelectiveNet and DeepGambler, such ratio is required input. To run these baselines, we first run the original backbone for 60 epochs, and then estimate a 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 mum classes then the frequency estimation of a is ā num of classesvtrain acc-1 which is the value we give to baselines. For more details about the mum classes-
experimental design, please refer to the Appendix (section D).
Results and discussion. T the result where mix the entire uninformative dataset (shuffled MNIST) with different proportions of the informative dataset Pfashion-MNIS" 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-to- informative data ratios, our algorithm wins by an even larger margin (Table
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 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 corrmaaivv-to-unnnfoon algorithm thus gains advantage by learning the underlying uninformative data labeling function in data-driven manner.
data ratio. Our
Our algorithm also outperforms all the baselines on SVHN dataset where noisy data comes from similar domain to the informative data. Each experiment repeated 5 times. Mean and standard deviation are presented in Table and Table
We provide more experimental results in the Appendix (section D). We test the performance of each method in the case where a is given and in the case where datasets contain minority noisy data.
8

---

Under review as a conference paper at ICLR 2022
Table 1:
(MNIST Full Dataset Unknown a). Results on a synthetic dataset consisting of
uninformative MNIST and informative Fashion-MNIST using the entirety of shuffled MNIST I' to proxy for noise.
Uninformative Data Num.
Informative Data Nom.
Criterion
Confidence
SelectiveNer
DeepGambler
Ours
SR(S)
59.32+0.83
45,4420068
45.37=1.29
10.35+0.31
60000
15000
Precision
0.46=0.79
0.61 = 0.01
0.61=0.01
1.00 0.00
Recall
0.94-0.07
1.00 1 0.00
1.00-0.00
0.85 0.01
SK(%)
39.23:0::7
27.7810077
12.03:1006
60000
30000
Precision
0.68-0.56
0.80 10.01
0.80-0.00
1.00 = 0.00
Recall
0.98=0.00
1,00 0.00
1.00=0.00
0.92 0.04
SR(%)
28.92+00.99
20.22+0.558
19.0940.41
12,58+2.00
60000
45000
Precision
0.79=0.29
0.88 40.86
0.89=0.00
1.00 = 0.00
Recall
0.99=0.00
1,00 + 0.00
1.00 0.00
0.97 = 0.03
SR(%)
21.88
15.38.0.322
14,2010622
11.61
60000
60000
Precision
0.86-0.46
0.92400.22
0.94-0.00
1.00 + 0.00
Recall
1.00=0.00
1.00 + 0.00
1.00 0.00
0.97 = 0.01
Table 2: (MNIST - Partial Dataset Unknown a) Results on synthetic dataset consisting of
uninformative MNIST and informative Fashion-MNIST data using 25% of shuffled MNIST for noise.
Unintormative Data Nun.
Informative Dain Num.
Criterion
Confidence
SclectiveNer
DoopGambler
Ours
SR(%)
79.87 00.40
1338
73.22:0.51
9.25
15000
3750
Precision
0.22 0.00
0.29
0.30 = 0.01
1.00 = 0.00
Recall
0.00
1.00
1.00
0.07
SR(S)
61.83 1 0.22
5r.76 2..66:10 1.97
58.13
13.71
15000
7500
Precision
0.00
Recall
0.92 1 0.01
1.00
1 0.01
1.00 1: 0.00
0.83 1. 0.01
SR(%)
65.90 0..49
47.30 1.85
46.96-40.50
13.06
15000
11250
Precision
0.49 1 0.01
0.60
1 0.02
0.60 a: 0.01
0.99 1. 0.00
Recall
0.00
1,00
0.00
SR(S)
48.51 1 0.25
39.23 0.50
10.35
19.10 4.50
15000
15000
Precision
0.00
0.68
0.00
0.68
0.99 + 0.01
Recall
0.95 1: 0.00
1.00 1 0.00
1.00 3: 0.00
0.91 1. 0.04
Table 3: (SVHN- Full Dataset- Unknonw a) Results synthetic dataset consisting of uninforma-
tive SVHN and informative SVHN using all of shuffled classes to proxy for noisy data. Uninformative Data Nun.
Informative Data Num.
Criterion
Contidence
SelectiveNet
DeepGambler
Ours
SR(3)
64.91 1 0.89
48.61 23.37
18.24 1. 2.00
7,03 0.01
33800
9200
Precision
0.53 + 0.01
0.52 + 0.22
0.80 + 0.02
0.93
0.01
Recall
0.98 0.00
0.89 0,100
0,96 1 0.01
0.85
0.01
SR1%)
47.64 0.80
28.15 1015==0 22.74
12.03 + 0.30
5,31-0.77
33800
18300
Precision
0.70 0.01
0.75 0.11
0.88 0.02
0.96 1. 0.01
Recall
0.99 + 0.00
0.96
0.98 +.01
0.88 0.01
SR(%)
36.33 1.57
12:90
8.65
4.08=0067
33800
26200
Precision
0.79 + 0.01
0.88 0.00
0.91 + +.0.1
0.97 0.01
Recall
0.000
0.00
0.98 -
0.89 0.01
SR(%)
34.48 + 1.15
12.10= 1.21
8.31 : 0.61
4.43=0.86
33800
28400
Precision
0.80
0.01
0.92 -
0.96 0.01
Recall
0.99 + 0.00
0.98
3 0.00
0.98 + 0.00
0.80 0.01
Table 4:
synthetic dataset consisting of uninformative SVHN and Informative SVHN using 25% of shuffled classes to proxy for noisy data.
(SVHN Partial Dataset Unknown a) Results
Uninformative Data Num.
Informative Data Num.
Criterion
Confidenc
SclectiveNer
DeqpGambler
Ours
SR(%)
20.32
31.48 13.46
9200
2285
Precision
0.1100005
0.37 0.22
0.68 0.13
0.87 = 0.07
Recall
0.94 +.001
0.85 + 0.23
0.83 0.24
0.50 + 0.02
SK(%)
6..4
48.42 23.12
26.42 1.68
1.46 = 0.87
9200
4600
Precision
0.57 +.000
0.58 0.17
0.77 +.002
0.94 + 0.07
Recall
0.95 1.0.1
0.97
0.03
0.96 0.0.
0.85 0.01
3K(%)
12.4100.71
26.04 3.01
20.83 + 2.00
7.28-0.77
9200
6900
Precision
0.65 1 0.00
0.76 0.03
0.82 1. 0.02
0.94 1 0.01
Recall
0.96 4 0.00
0.96
0.03
0.97 0.01
0.87 + 0.01
SK())
49.45 1 0.45
24.09 3.08
18.81 1 1.47
7.22 0.54
9200
9200
Precision
0.67 0.00
0.77
0.03
0.83
1: 0.01
0.94 = 0.01
Recall
0.00
0.98 = 0.00
0.96 0.00
0.88 = 0.01
5 CONCLUSION
In this work, we propose a natural noisy generative process to model a problem where 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.

---

Under review as a conference paper at ICLR 2022
6 REPRODUCIBILITY STATEMENT
We describe a synthetic data generation procedure, evaluation metrics and experiment setting in section For the convenience of the reader 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.
ETHICS STATEMENT
This paper focuses on 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.
REFERENCES
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta- algorithm and applications. Theory of Compuring. 8(1):121-164, 2012.
Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Ruth Urner. Efficient learning of linear separators under bounded noise. In Conference Learning Theory, pp. 167-190. PMLR, 2015.
Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM (JACM), 63(6):1-27, 2017.
Maria-Florint Balcan, Avrim Blum, and Santosh Vempala. discriminative framework for clustering via similarity functions. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 671 1-600, 2008
Peter Bartlett and Marten H Wegkamp. Classification with a reject option using hinge loss. JMLRR, 9(8), 2008.
Peter L Bartlett Michael I Jordan, and Jon D McAuliffe, Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-156, 2006.
Avrim Blum, John Hoperoft, and Ravindran Kannan. Foundations of data science. Vorabversion eines Lehrbuchs, 5, 2016.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the wapnik-chervonent dimension. Journal of the ACM (JACM), 36(4):929 965, 1989.
Tom Bylander. Learning linear threshold functions in the presence classification noise. In Proceedings of the seventh annual conference Computational learning theory, pp. 340-347, 1994.
Nicolo press, 2006.
and Gábor Lugosi. Prediction, learning, and games. Cambridge university
Moses Charikar, Jacob Steinhardt, and Gregory Valiant, Learning from untrusted data. In Proceedings of the 49th Annual ACM SIGACT Symposium Theory of Computing, pp. 47-60, 2017.
Chi-Keung Chow. An optimum character recognition system using decision functions. IRE Transac- tions Electronic Computers, (4):247-254, 1957.
Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning with rejection. In ICALT, pp. 67-82, 2016.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 JEEE conference on computer vision and pattern recognition, pp. 248-255. leee, 2009.
10

---

Under review as a conference paper at ICLR 2022
Jacob Devlin, Ming-Wei Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprins arXiv: 04000, 2018.
Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart. List-decodable robust mean estimation and learning mixtures spherical gaussians. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pp. 1047-1060, 2018.
Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distrbuttion-indeeendent pac learning of halfspaces with massart noise. arXiv preprint arXiv: 1906. 10075, 2019.
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning halfspacce with massart noise under structured distributions. In Conference on Learning Theory, pp. 1486-1513. PMLR, 2020.
Andrzej Ehrenfeucht, David Haussler, Michael Kearns, and Leslie Valiant. A general lower bound on the number of examples needed for learning. Information and Computation, 82(3):247-261, 1989.
Ran Yl-vaniv et al. On the foundations of noise-free selective classification. JMLR, I 11(5), 2010.
Giorgio Fumera and Fabio Roli. Support vector machines with embedded reject option. In Interna- tional Workshop on Support Vector Machines, pp. 68-82,22 2002.
Yarin Gal and Zoubin Ghahramani. Dropout as bayesian approximation: Representing model uncertainty in deep learning. In ICML, pp. 1050-1059, 2016.
Yonatan Geifman and Ran El- Yaniv. Selective classification for deep neural networks. In NeurlPS, 2017.
Yonatan Geifiman and Ran El- Ylnvv..v. Selectivenet: A deep neural network with an integrated reject option. In ICML, pp. 2151-2159, 2019.
Yves Grandvalet, Alain Rakotomamonjy, Joseph Keshet, and Stéphane Canu. Support vector machines with a reject option. In NeurIPS, 2008
Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor W Tsang, and Masashi Sugiyama. Co-teaching: robust training of deep neural networks with extremely noisy labels. In NeurlPS, pp. 8536-8546, 2018.
Steve Hanneke. The optimal sample complexity of pac learning. The Journal of Machine Learning Research, 17(1):1319-133 1333, 2016.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016a.
Kaiming Hc. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pp. 770-778, 2016b.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Heinrich Jiang, Been Kim, Melody Y Guan, and Maya R Gupta. To trust not to trust classifier. In NeurlPS, pp. 5546-5557, 2018
Adam Tauman Kalai, Adam R Klivans, Yishay Mansour, and Rocco A Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 1777-1777 2008.
Michael Kearns and Ming Li. Learning in the presence of malicious emror.. SIAM Journal on Computing, 22(4))807-837, 1993.
Michael J Kearns, Robert E Schapire, and Linda M Sellie. Toward efficient agnostic learning. Machine Learning, 171--3):15--141, 1994.
11

---

Under review as a conference paper at ICLR 2022
Alex Kendall and Yarin Gal. What uncertainties do we need in bayesian deep learning for computer vision? In NewrIPS, pp. 5580-5590, 2017.
Philip Klein and Neal E Young. On the number of iterations for dantzig -olle optimization and packing-covering approximation algorithms. SIAM Journal on Computing, (M(4):1154-1177 2015.
Adam R Klivans, Philip M Long, and Rocco A Servedio. Learning halfspaces with malicious noise. Journal of Machine Learning Research, 10(12), 2009.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, (11)))228222222 1998.
Ziyin Liu, Zhikang Wang, Paul Pu Liang, Russ Salakhutdinov, Louis-Philippe Morency, and Masahito Ueda. Deep gamblers: Learning to abstain with portfolio theory. In NeurlPS, 2019.
Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, 34 (5):2326-2366 2006.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep Ravikumar, and Ambuj Tewari. Learning with noisy labels. In NIPS, volume 26, pp. 1196-1204 2013.
David F Nettleton, Albert Orriols-Puij and Albert Foreels.. A study of the effect of different types of noise on the precision of supervised learning techniques. Artificial intelligence review, 33(4): 275-306, 2010.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011. 1.
Tim Pearce, Felix Leibfried, and Alexandra Brintrup. Uncertainty in neural networks: Approximately bayesian ensembling. In AISTATS, pp. 234 244, 2020.
Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1): 145-147, 1972.
Hans U Simon. An almost optimal pac algorithm. In Conference on Learning Theory, pp. 1552-1563. PMLR, 2015.
Ruey S Tsay. Analysis of financial time series, volume 543. John wiley & sons, 2005.
Leslie Valiant. Probably approximately correct: natureōs algorithms for learning and prospering in complex world. Basic Books (AZ), 2013.
Leslie G Valiant. A theory of the learnable. Communications of the ACM, 2113231411111311111 1984.
Vladimir N Vapnik and Ya Chervonenkis. On the uniform convergence relative frequencies of events to their probabilities. In Measures of complexity, pp. 11-30. Springer, 2015.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. arXiv preprint 106603776 2017.
Marten Wegkamp. Ming Yuan, et al. Support vector machines with a reject option. Bernoulli, 17(4): 1368-1385, 2011.
Yair Wiener and Ran Elniv..v. Agnostic selective classification. NeurlPS, 24:1665-1677 2011.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 2017.
Xingrui Yu, Bo Han, Jiangehao Yao, Gang Niu, Ivor Tsang, and Masashi Sugiyama. How does disagreement help generalization against label corruption? In ICMI., pp. 7164-7173, 2019.
12

---

Under review as a conference paper at ICLR 2022
Ming Yuan and Marten Wegkamp. Classification methods with reject option based on convex risk minimization. JMLR, 11(1), 2010.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017.
Chong Zhang, Wenbo Wang. and Xingye Qiao. On reject and refine options in multicategory classification. JASA, 113(522):730-755, 2018.
Yikai Zhang, Songzhu Zheng, Pengxiang Wu, Mayank Goswami, and Chao Chen. Learning with feature-dependent label noise: progressive approach. In International Conference on Learning Representations, 2020.
Songzhu Zheng, Pengxiang Wu, Aman Goswami, Mayank Goswami, Dimitris Metaxas, and Chao Chen. Error-bounded correction of noisy labels. In ICML, pp. 11447-11457, 2020.
13

---

Under review as a conference paper at ICLR 2022
A ILLUSTRATIVE EXAMPLE FOR ALGORITHM
(a) Ground Truth value
(b) Classifier in 1-st iteration
(c) Classifier in 12-th iteration
(d) Algorithm up-weighs informative data
Figure 2: Illustration of Algorithm T
By up-weighing the informative datapoints, the algorithm progressively improves the classifier. d) shows the sum weight all informative data over weight
sum of all data, i. Ein " Seee y Algorithm
2i 74
B THEORETICAL ANALYSIS
In this section, we show auxiliary results culminating with the proof of the main result in Theorem 4 In this section, we will the following well-known result repeatedly.
Lemma (Hoeffding's s Inequality). Let Zi,... Zn be independent bounded random variables with Z: E (a, b) for all i, where x < < < cc. Then for all I. >> 0:
1 P
2m
Σ 7
B[Z]]|
2 S 2e
(8-a)2
n i=1
The lemma provides upper bound the empirical risk Rs(s*), if enough samples available.
Lemma 2. Consider set of samples S = ((#1,9),, (In: yn)} drawn i.i.d. from the Noisy Generative Process and f in the hypothesis class F satisfying f(x) E {-1, +13. If:
l
n 2 caa²
Then we have with probability least 1 - 55
1
Rs(f*) - 7 - a) + as
(10)
Proof: By definition:
R() = E(ay) [1((x) +
(11)
and the empirical risk
1 E 1ff(z)) + v Rs()) =
(12)
Note that 1[f(x) * y} is bounded in the interval [0. 1] and given f E F( + } i [M]
form a set of n independent random variables. By setting b a = 1, t = ae in Equation 9 the choice
of n ensures that -2nt² < (llog()). Thus (b-a)²
P PS.DD. "s - ca) Sd.
14

---

Under review as a conference paper at ICLR 2022
where we have
R(f" = (L,)) [1f(z)) + B( (1f + u}1 E Ou]P[r E Pol
PloeEuu]: Since y is labeled by coin flipping in Ou
(...))>p..111" (x) 3 22 [P x E 27
(13)
Since labeled by f" with Bayes Risk in f2
1 (1 aa)
2
This way we have:
Ps.-0_1[s(()--
[0]1--]]=00 2 Ea) S d.
which implies that Equation 10 holds with probability at least - 6.
The proof of Lemma 2 relies the independence between (z;z) + yi across different pairs (xs, y:) E S,- However, there is no guarantee that such independence holds for the empirical minimizer fs.. arg sen (f)
In order to prove Theorem [ we use the growth function Definition 7 for sets of size n and the following symmetrization lemma. Here show its proof for completeness; it can be found in different sources (Mohri et al. 2018 Blum et al. 2016).
Lemma 3. Suppose Sn = {(11, (1),,,))..... (In, Bn)) are i..d sampled, L(f,2, 2, y) E [0, b] and Ls." =
DE L(f v.). If
nt 262
then have:
Ps,- (sup Ls, (J) - L(JI 2 1) S 2P s. St ~ fEF
(su Ls., (ʃ) - Lsy (f) 2 7
feF
Proof: Since I.s,, (f) - L(f) 2 t. and Lsg (f) L()) < implies [T... - Lss 2 thus
sup /e/
I,s, (00-1(((22) 1 1=5
L ( (1-((1) s
(14)
< 1
LLs, (f) Lug, 1
/ef
Taking expectation w.r.t Sn Da and S/ D, have
Lsy - ((0) -
PS.DDa (sup Ls, (f) - L(f) 2 tJIp s ~ Da |sup
FEF
FEF
(15)
< Psss, WD. |sup (s), - Lss (/) 2 !
FEF
Next we lower bound [(ssup
[,s (J) I()) 2 [. Since ((f, E [0, b) and Var(T.(J y)) s
fEF
8a
T we have:
P s D. ssup Lsz (f) L(f) < 1 / 4Var(Ls.) feF
nt² 2
Given the choice of 26², we have P(sup Lsr (f) L(f) 2 {) 2 which implies
fef
P PSANDA (sup Ls. (f) L(f) 2 2P S. D. fEr
ssup fef
Lss (f) Lsg (f) Z
Theorem 1. Under Assumption D given a set of samples S. ((11,11), (In, vn)) drawn i.dd from the Noisy Generative Process and
f3.
arg Rs(f).
JEF
15

---

Under review as a conference paper at ICLR 2022
suppose
32 (2gg(1)2((n)))) + log( !)
n 2
e?a2
Then with probability at least 1 22:
R(f3.) S 2 a) + 2Ea.
Furthermore,
P PI-D,1(((x)) * S3. (1)) S 2e
Proof. We first bound the probability of the event that R((3s.) S 1/2 - (1 -2e)a.
We start with bounding Pss.. St, SD s|,s, (f) R(f) + R(f) Rs, (f)l 2 1 for fixed f. Since
RRs, (f) - R()) + R(J) Rss (f) 2 implies RRs, (f) - R(()I 2 or (R()) - Rs; (/) 2 1 we have
Ps Sy ~D Rs. (f) - R(f) + R(f) - Rsy, (f) 2 t
SPs SD 1.l. (f) R(()I 2 Ú P Rs (f) - R(f) 2 / '
(16)
m12 32
<2c
Let Fs..., = (f(x) : f E EF x U. _ [+1, - 1 with Lemma 3 and Eq 16 we have:
P S, D. /sup Rss, (f) R(f) 2 t|
fEF
RRs, (f) Rsy (f)l 2 t 1/
22F Sn S DD
ssup FEF
|Rs, (f) - Rss (0) 2 t
-2P ~D
sup
fEFsn.
<2
PlJRs (f) - Rsy (f) 2 1
(17)
t
=2
Pl|Rs, (f) - R(f) + +(f)) Rs; (f) 2
2 2
JET sn.sh.
[4|Fst le- '2
<49x(2m)ee na²
32(4 log(S> (20))+ have with probability of at least - 8: a²,²
By setting t and
R(f5.) Rss (fs.) I
ae 2
Next apply the fact that f3., = arg minjer Rs(f). Since Rs. (f*) 2 Rs. (f3,)) ) we have:
R(S,, ) 1 ac + Rs.. (S$,) S ac + Rs. (f*)
2
2
Since Rs. (S*) S (1 - a) + ea with failure probability at most (Lemma 2 we have with
probability at least 1 - 25:
R(f3.) S 5 (1 a:) + 2ea.
Next prove the claim that:
P PAND, (5) # SS, (x)) 2c
16

---

Under review as a conference paper at ICLR 2022
Since R(fs.) 2 a) + 2cc:
R(fs.) -((a,))-D D. (1)
((aa)))D D. [1[s3, (z) +
(may))D, [[S3 ( (4) + u}| Slyl Pl..ii |o Ivl
+ (L(eN)DD, [1[33 (z) + u}ト E Ωr [a (x Ei
(18)
P(an))DD, (10
5 (1 a) +ap xー D. [[ (z) # ( 2d
2
(1 a) 2Ea
2
= Po 1-153, f<)) 2r S 2e
Next we analyze the weighted risk in Definition 6 and its empirical version. In particular, we are interested in the case where a, which implies
I-a For given pair (a,, Wi), we have:
{ θ a
((f(a)
+. (1)(())) 0} + 1- 1-a
= 1 =0} 0
a
is useful to write down explicitly the following decomposition W f.0):
0
1- 1[(()) = = (g(r) (() s0) s0]
Wg..
((
1(f(x) # ()) > 0)
1-a (
((a.))~D.
- 1(((x) #
+ (e.))DD
( (11600000000000100000
0 1(f(x) - (10()))00
+ (.a.))D.
+ (e.))DD
1(5(x)= -0]00
0
((..v) D. [f(x) 0 0,
a
0
+ P. D. [f(x) # (0
<
a
1 l
+ P(ay) [z vlg()) 0
a
!
a + Play)~D, = vll()) 00.0 0Jp
(P (0,
0 P(an))DD
a PPe
> >0]
+
PP
PANDa [g(x) > 0z) 0
2a
1-
+
P PIND (g(x) < 0, 0
2(
a)
1 0
P
((ey))D. [f(x) vlg(z) s 0, 0 (x) > (PInDa. 50,00()) (60 0)
a
(19)
17

---

Under review as a conference paper at ICLR 2022
One can that if f a, then g(x) should reject all x E Dy since 8 1-a For the informative partition S2,, the decomposition suggests acceptance of all such that f(x) y and rejection of f()) + y. This gives the optimal value 1-0 2(1-a) PE-DD [g" (a) I 0]. Note that the optimal value of (gg, f. 0) is not necessarily achieved at (ff'g"), ). For any fixed f. the optimal value W (g. f. 0,0) is achived for long g accepts all datapoints in S2 that are correctly classified by f. and rejects all mistakes made by f in Ω (as well as all datapoints in Sty).
Lemma 4. Given set of samples Sn {( ((11,11),... v1),.., (Ins bn)) drawn ii.d. from the Noisy Generative Process. Suppose (a, 1). E (0, $ 0.1, and:
20 log(t)
2a11
Then with probability at least we have:
[Ws -) ff'""""' s ae
Proof. The following holds for a given (I;, V:):
(1 # (.)1) 0)
1 1 0 - [)) s 0) = 0
1
Since 0 < 1, we can apply Hoeffding's inequality in Lemma with a 0,b a. For fixed
f. E F, (ff()) & v,ii [n] are set of independent random variables. By setting b t = ae in Equation the choice of n ensures that -2n12
[b-aj² I 6og(()). Therefore:
PS.~D. [[s,, (g","""''"' ff" - W(g ""' f0,0) 2 ea. S
Recall the empirical minimizer of Ws, s, (g. fš,, 0):
95. = arg min Ws., (g, fs.. 0).
gEH
Since f3. and 03., data-dependent, it follows that W fz. 0), [n] not independent draws. Our strategy is to use similar logic as in the proof of the Theorem We begin by finding an upper bound on the probability of W s.. (g, f 0) deviating from its expectation. Then take union bound of all the possible pair of (') E H x F restricted to S..
Theorem 2. Consider Generative Process and
of samples S.. {(11,1)) (In, yn)} drawn i..dd from the Noisy
f&. = arg min Rs(f), gs.). = arg min Ws., (g. f8., 0),
JEF
9EH
If (a, e (0, 1) and
320² (log(4[Cu(2n)110 (2m)) + log(})) >
2a4
then with probability least 1 8:
[W 13, Ws. J',, s ca.
18

---

Under review as a conference paper at ICLR 2022
Proof. First apply Lemma 3 with Ls,, (f.g)
Ws, f)). 6 a and t ac, and also using
the condition 2 3262 Gu Gu. (2n) Gr (2m)]) +log( +)
20
in the lemma. Then follows:
Ps. DS (sup WWs. (g. W (g, f3, 0) 2 ac]
gEH
WW s, (g, f3. 0) Ws. (g. f3, 0)1 N ac 2
<2P S 8 DD yEA
sup
W s, (g. f, 0) f. z or
2PP Sn DD. sup
gEH,JEF
Ws. (g. f. Ws: f. 06
<2P St
sup 9EH sn sh JCF sn.9h
2
Σ
St Sy Do [Ws (a.(o. ac
geNsn.st St SE.
Sn.8h
Σ
Sn D. (.. (g. W(g. f.0) Ws, (9. 2
gEH Nn 8
JEF
<4H.s. | PP PSPDD
Ws. (g. f.0) - f. at 4
4
2
(4Gx(2n)G>(22)
m,4
(2n)) 2262
(20)
Next bound the FPR and FNR of Is., leveraging the fact that Ws., (g. fz,,) is sufficiently small.
Theorem 3. Under Assumption ] given of samples S, {2 v1), .... (Eas vn)) drawn i..d from Noisy Generative Process and
f3.
arg min Rs(f). = arg min Ws, (g. fš., 0), jef
9EH
if0 E (a, (), E (0,1) and
320 [log(4[(H( (2n) + log(3)
2a
We have
I) with probability at least 8
W f5. S 2c0 + 2ac + (1-0) 0)
2
II) i 20a with 1 <
Ita 4a
we have with probability at least 8
12cac
Pla', (x) 2 0lg* S 0] <
[False Positive]
(21)
2c
P(g (④) < (z)"(x)) < 20cc/False Negative]
(22)
Proof of
19

---

Under review as a conference paper at ICLR 2022
Proof.
W .3. Ws, Ss. ore
with faiture probabilitt most Theorem
S (9" ff... .) + ae
Optimality 2s
" 0) + 20r
With failure probability at most (Lemma
0
1[s5 (x) + x))lgg()) 0]
- -E
1 - A
((r.y))D
1[fs, (z) xx) s 0}
+ 2ne
0
[[f. (x) # (x) 0 PIND, 10¹(x) 2
=B(z,))-Da
1 - A 1(f%, (z) = v>اا (x) =0 PEND, (2) S 0] 20c
B(ay)DD
-B 0n (x) # 4) (z) 0] BLEDDDD [] (④) = y>) <
=0 PEWD, Ifs, # (x)]
S2e with failure prob at most (Thm !
+ (1 -1-00
=0.5 all y's Du [f$ vl
+ 20c
flppping
(1 0)
<2e0 + 2ae +
2
(23)
Proof of II):
Proof.
W 0)
-E(ay)
1(f5, (z) + v) (z)
(+)> > 0)
1 0
+E
D.
[-a 1(f3, (z) 1)1 (a) =0]
(24)
0
-E(an)~Da
1(f3, (x) # y) (03, (x) 0g (x)
PIND, 10 (x) 0]
a
Term
0
E (ryDDD
1153. (x) + 19's (x) 00gg s
P Pa)
Term 2
+ ((ay))D
1[f3, (x) = y3lio3, (④) 00)0g (x) > 0 Pa- 2x)
Term 3
1 0 1[53, (x) (x)
(ey)D,
Term
20

---

Under review as a conference paper at ICLR 2022
Next we lower bound Term 1, individually and apply upper bound W(93, W03.,, f3., () in Eq 23 for the proof of the statement. Term 1:
0 1[55 (x) (0)) 2 P (x) ol
B (a..)~D Do
-B -B(a,y)-D.
[1[/3, (x) + +1)) 0
(25)
[1if% (1) # velos, (z)=0, PAND. 195, (z) > (x) 2 20]
20
Term 2:
1[5 (1) # 195. (s) S (o)
A(1 a))
[ (x) + E Ba Da
(z)>>)000)))) 0
0(1 - a²)
E R(a.w)~Do Do [[]3 (x) + y) 53 (,)
0| PaNDD 193, (x)> > (x) 0]
P Pa 1/3,, uu,=0.5 Since all y are coin dipping 9 g() 5
(1 - a)
P PaNDa 19s, (x) 0lg
(c) (x)
0
2a
(26)
Term 3:
B(s,a)/D
1[f3, (x) 1) =0) > >0 Pp. (x) 20]
(1 8)a
E (x,D)DD,
[1 (z) = (x) > 0]
(27)
1 a
0)ar
1-a P (a.)))Da [$3, (x) = vlos. (z) < (x) > 0| PAND, (1))
By Theorem [ we have with failure probability at most 28:
P. PaND. I53. # (z)
PAND. 1s3. #
0] S 2e
P PENDD I53. #
P P.-D. D. [s3, ".0"0.....001y00000.0...0...111.
P D. [s',
0g"0)))))
2 PaND. |0,, (2) < ())
(1 f)a E Eyn... D.. [1 = f( (r) (1) 00g'
(x) 0]
A)a { 1PINDa (z) <og (0g7) 2c]
a
(28)
Term 4:
0 1s53, (x) = -4) < Po 50]
T a
(1
[1[f%, (z) - -000
= (1 -))
[1[5s, (x) = -y>lg3, (0) < PaND. Loš, (x) s 0lgg < 0]
Vir s.t.g" (z) coin dip
1-0 0 {1 -P PawD. 103 > (x) < 0]}
(29)
21

---

Under review as a conference paper at ICLR 2022
Combining Equations 25
26
28
29
we have:
2 (11 o0)
1 1 0
1 A
P PIND, PaND,193,(c1)
(x) > 01g (x) - 0
+
2a
2
2
(30)
a(1 0)
1 FENDA 193, (x) S 0lg0 > 0] 2(1 8)ac
and by part 7) in the theorem, have with probability least 1 - 35:
W(9s. 0) S 2c0 2ne + (1 f)
Combined with the failure probability 26 in the bound of Term 3 we have the failure probability at most 56:
[ ( a)
1-
1-0 0
P Pa-Da 103, (x) (x) = 0J +
2a
2
2
a(1 0)
P PANDD D.nD,,ss, (x) S 0lg 0]
2(1 0)
1 - a
1 - a
(1-0)(1 ax)
< 2e0 + 2ac +
2
(31)
{ 0
P PanDa 195, (2) > 0lg' (x) 0]
2a 2
a(1 -0-
0)
1 PAND, (gs, (x) S 01)'(1))))))))))))((())) > 0]
2(1 0)cc
< 2e0 2ae
1 - a
By picking 2ca with 1/2 < <<<<<
1+ 4a
we can ensure that 1)
8 2n
1/2 > 0;2)
a(1-0) T-a
2 a Finaaly
2'
we have:
P x~ Da [0s, (z) > 0lg"(x)) 00 S 4car + 4ae
(32)
12cac
PAND. 195. (I) 0/g (z) < 0] v 2c -
and
a(1 0)
2(1 - -0)a
PIz lgs. (x) < 0lg" (x) > 0] < 4car +
+ 2
1 a
1 a
(33)
P PENDD Is, (x) < 00g (x) 0] < 20cc
Given hypothesis class H. one can bound the growth function Gx(n) through its VC-dimension. Next present the well known Sauer-Shelah Lemma below.
Lemma 5 (Shulr-Shelah Lemma(See (Blum et al. 2016 Mohri et al. 2018 Sauer 1972 )), Let (H) be the VC-dimension of hypothesis class H. for all N,
due
doc(Ht)
(n( <
en dol
Now we are ready to prove the main result.
Theorem 4. Under Assumption 7 given set of samples Sn {(11,11) (111,1),... (In, yn)} drawn ii.d. from the Noisy Generative Process, hypothesis class H with VC-dimension de (H). F with VC-dimension (F) and
73 arg min Ws,, 9g gEH
a²
f3. arg min Rs(f). gs." JeF
72
72
22

---

Under review as a conference paper at ICLR 2022
If a (0,0.9) and:
128 [ddvc(H) (oc( log( }
n 2
ea2
We have with probability at least 1 1 0:
1)
Plg3, (x) 2 00'0 S 0] O(c)
[False Positive]
(34)
Plos, (x) < 0lg"(x) 2 0J S O(t)
[False Negative]
(35)
II)
P PANDA (z) + f3. (z) (x) 2 0J O(e)
Proof. 1) above can proved by observing c
T2 and applying Theorem
3 with Sauer's Lemma
to bound the growth function in terms of VC-dimension. Also notice that
1+ 1te
E ( L+a
de
given < 0.9. II) can be proved by observing that I) implies Plys., (x) + g (x)] O(e) and by invoking Theorem
Remark 3. Let point out that proposed selective strategy is different from the consistent selective strategy in (EI- Yaniv et al.) 2010). Instead of rejecting by looking for consistent output from all hypothesis in the version space, approach deals with single reasonably accurate hypothesis (the empirical minimizer). We leverage empirical mistakes made by the predictor in order 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 Yania et al. 2010, where the selector fails to select any data points.
Remark 4. In (Cortes al. 2016, 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 Geifiaa & El- Yaniv 2019) is the motivation pertaining to selective learning. While in (Cortes et al. 2016 Geifinan & El- Yaniv 2019) the selective loss is designed from a coverage ratio perspective, i.e. one wants to trade coverage ratio for higher precision (selective loss), our approuch is designed to distinguish data that is naturally unlearnable and unpredictable. This difference leads to an alternative theoretical result. While the analysis in (oortes et al. focuses focuses 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.
C TIGHTNESS ANALYSIS
In this section, we investigate whether it is necessary to have ñ (dn((H)+duec()))) samples to achieve
P PA-DA 1f (x) + fš. (x)lg" (x) 2 =
and
max (Fioš, (x) (x)lgg > 0]. Plos, (x) + (x)lgg S 0) = 0(s).
We will show that there exists distribution D. among the Noisy Generative Process family and hypothesis class H. F such that achieving guarantees in Theorem requires 22( (H) samples, thus making our analysis tight within logarithmic factor. Note that our lower bound is for empirical minimizers of R()) and W(g, f,0); 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 f.0) can improve sample complexity to rate of observing that the informative data is realizable, which usually only requires ( samples for an statistical error. Our construction leverages the idea from (Ehrenfeucht jet 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, will leverage the anti-concentration results of the Chernoff bound, with the proof idea that comes from (Klein& & Young 2015):
23

---

Under review as a conference paper at ICLR 2022
Lemma 6 (tightness of the Chernoff bound). Let X be the average of k independent, 0/1 random variables (H..). For any E (0,1/2] and p E (0, 1/2,, assuming eph 2 6, pk 2 6, S 3 we have:
If each nvv. 1 with probability p. then
(1 2 --6
If each nv. 1 with probability p. then
P[x 2 c1p 2 -622ph
Proof. The proof is similar to Lemma 5.2 in parameters. With Stirling's approximation, i! V2ri(i/e)'e with x E [1/(12i + 1), 1/12i] one can show:
Klein & Young, 2015) with a different choice of
(
A
k 2 (1))
(k-e)
(36)
Also note: P[x 1 (1 e)pl = DLL = k.
Let é= [[1 2e) p. Given the fact that epk 2 6, we have (1- 2c) S e (1 22) It
suffices to lower bound - PP[X = E which is at least epk = k From Equation 36
we know that we need to bound A = 2epk/ 2 and B = (4) k-7
k-t //(1 1--))* p)^ For term 2cy
A, since spk 6, / S (1 - 22)pk thus we need pk 2 ge to get
e- -²ppk Since
ev 2/22(11 (1-1)_c) 2c)
E S 1 3 it suffices to have pk 2 16. To bound B we need to show:
k -1
h-1
p'(1
p) 2 1=2ppk
Since (4) [I-26]]
and (1 - p)h-d
h k-1
(1-p)k k-1
we have:
[--
[(1-p)+1+2eph
(1 - (1-)
(1+
1 2xpk)
k-t
S E
2.22t 1
+2ep 2epk+4eppt2 S Seppk
k(1 -
We consider the following distribution. Let (F) = and ej be the standard basis with j- th coordinate equal to 1 and 0 otherwise. We set 5 {+2, - 2} eg, ey,
Uf - ot and 0f = {+1, -1 Q, = 2/ Let F = sign(w" T 2) and = 2 9 1, where (x(x) E (1(le] z 2 cf u (0), l[ee] æ S c}}. By Lemma 3.2.3 in (Blumer et al. 1989 we know (H) s 6d log().. We construct D. as follows: in Sy each standard basis has 72 mass with sign generated via coin flipping (fair). Having generated x, y E {+1, -1] flipping. In 22,, we put (x11 e) mass on e₁ and or
} is generated via a coin d=1 mass on other standard basis ej, with sign
generated via a (fair) coin flipping. Having generated y [++1--1) is generated via sign(w"" x) where wt denotes a vector of ones. The above construction allows one to calculate the expected error by counting the number of basis that not leamed correctly, i.e., each [d] wy 0 implies ae in expectation. Since: an error 2(d-1)
Es, Es. D. [|S, / d-
aEn
by Markov inequality we have
brgn.
1
P PS..D. [1S
6'
24

---

Under review as a conference paper at ICLR 2022
Also note that EE=D,[1{x E f/11fz ud O via empirical minimization, need to bound the following probability:
-2yy
1_a. In order to derive the probability that
P PawDal
y
Σ
yk 3 d-1
6aEn.
1,00 <,
2,20
To do so, consider the following nj random variables that conditioned E D2/: 2; 1 if e ns < 0, or e x, 0, -1 and 2 0 otherwise. One can see 2 2 Zien, 2 n2
Enew Jacc Vi Em. eneess ,0] 2>00 Us. Thus
P PawDul
Σ
yi
Σ
Vi
6agn
(d 1)
:: a;<0
zen ay 4,30
a)
3(1 a)n
$ S, 12 - 3(1 amm
>P P.
d
d
d
P
S
Σ
21
R2
2
(d
3aen
(1 - a)n
d
3(1 - a)n
d
S nn S
3(1 a)n
d
2,E8
3aed
(1-a)n
3(1 - a)n
3(1 a)n
2i
2
2
(d
1) a)
d
d
S Sn S
d
2,E8%
18
1 2,22
(37)
If n S 43 we have for each j. with probability at least 0.40, wy < 0 due to the empirical minimization strategy. Each wy < 0 contributes ac T[ risk in expectation. With probability 0.2, 20% of coordinates can not be learned correctly, thus resulting in risk of least 1 in expectation. Next we show that the selector is going to suffer from poorly learned classifier in terms of its false negative rate. Now lets focus on the case when (,,,,)),, [fs. (x) + yl 2 ) a) + 0. (which happens with probability least 0.2), we will show that Ez-D. [gs, (x) + g (x))g" > > 0.1s. Let J1 be the set of j's s.t. Wi < 0 and J2 for wi > O. Suppose 0 a, and consider empirical minimization:
d
min Ws (fS. 9.
N min W nay (fS..g.9 gEH
(38)
gEH
For je E Jr, 9 E arg min W s.nor (J3 0) if (x(x) = lfe aa 2 cJ,c > 2 (and for other gEH basis j. 9j can be arbitrary). For j' E J2.9 arg min W Sanny ( 9EH
9, 0) if 97 (x) 1 l Txl s
- 2j (x) - 1,)) 1 1(eTT 2 c} with > 2 if ct.c E (1,2). Now consider gs. -111=11,(00
j J1 and gy(x) 1[ee] x| S c),c E (1,2) if E Jz. One can see that such I3. in the intersection of set of minimizers of Ws. nor (JS.. 0) thus attains the minimum. The total mass of
s.t. S.L. g3. (x) + (x) is at least 3i lar since for all x E 2 with j E JT. 93s (x) A g (xr). The d-1 event & : E(nn)>D, [ss. (x) + fx(]]] 2 [1 a: + 0. happens with probability at least 0.2 which implies that [J] 2 0.2d. Thus we have following lower bound on the False Negative:
P PewD_ 193, (x) A #g (x())) (z) 0J N 0.1e.
25

---

Under review as a conference paper at ICLR 2022
D SUPPLEMENTAL MATERIAL FOR EMPIRICAL STUDY
Extension to Multi-class. Our method extends to multi-class setting naturally. In the case of K-class classification, we predictors f(x) f())1KK'
A where A R is the s-simplex. 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 2; = {arg max [X] f(x)): = Wi}-
experiment, the backbone model we use for each candidate is TinyCNN, which is CNN with two consecutive convolution layers and consecutive fully connected layers. This architecture provides enough model capacity for an MNIST-tyye dataset. We use 196 as the batch size. We use Adam as the optimizer with learning rate le-3 and weight decay le-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, reported in Geiffaan El-Yaniv 2019 Liu al. 2019), and 3 c(1-0) for our algorithm). simulates practical scenario where hyper-paramette 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 ResNet18 (He et al. 2016bb) for every candidate. We use 128 as the batch size. We Adam the optimizer with learning rate 1e-3 and weight decay lc-4. We train each algorithm for 162 epochs.
Experiment setting with Unknown a (More Details). For MNIST/Fashion-MNN
0(1-a)
Weight of Informative data. From Figure informative data by the end of training for all informativeeuiinformaty ratios even without knowing the ground-trune
that algorithm can pick out almost all
10
09
Weight on Structuned Data
0.8
0.8
9.7
Weight
structured frac=0.57
structured frac=0.67
0.
frac=0.50
0.4
structured trac=0.43
03-
structured frac=0.43
structured frac-0.33
structured frac=0.33
02
structured trac=0.20
structured frac=0.20
Epach
(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.c Eeregg in the notation of Σ Algorithm|1 [ Each experiment repeated times, and standard deviations are presented as the shaded gray area.
Experiments with Known a. 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 exhaustive HPO (Hyper Parameter Optimization). We use the same backbone, optimizer and the number of training epochs as before. We run a random paramm-rr search 500 times (selective loss weight and parameter À for SelectiveNet and parameter in DeepGambler) and record the best performance of each baseline. this setting, our method still outperform baselines for most levels noise ratios. In this experiment, 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.
two stage training for algorithm. We first run 120 epochs to finish 1st
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 a) and idealized scenario (known a). In practical setting (unknown a), our proposed algorithm still wins by large margin. In the case when is known, DeepGambler outperforms other methods in
26

---

Under review as a conference paper at ICLR 2022
most cases. We hypothesize that when noisy data minority, method doesn't 't get enough samples to fully learn the pattern of uninformative data.
D.1 EXPERIMENT WITH KNOWN
Table 5: (MNIST - Full Data Setting Known a) Results on a synthetic dataset consisting of
uninformative MNIST data and informative Fashion-MNISS -NIIT data using the entire MNIST.
Unilormative Data Num.
Informative Data Num.
Criterionn
Confidencs
SelectiveNet
DeepGambler
SR(%)
10,00 = 0.32
10.11 = 0.42
9.77
0.51
9,18 i: 0.49
Precision
0,99 0.00
1.00
0.000
1.00 0.00
Recall
0,99 + 0.00
1.00 + 0.00
1,00 + 0.00
1.00 2 0.00
SR(%)
9.11 +
9.91
9.03 0.73
60000 30000
Precision
0.99 + 0.00
1.00 + 0.00
1,00 + 0.00
1.00 + 0.00
Recall
0.99 0.00
1.00
1.00 0.00
1.00
SR(%)
8.63 0.23
9.39 0.35
8,58 0.26
60000
45000
Precision
1,00 -
1.00 + 0.00
0.00
1.00 0.00
Recall
0.99 0.00
1,00 + 0.00
1.00 + 0.00
1.00 0.00
SR(%)
8.1I
8.21 0.12
8.16 1 0.05
8.04 1 0:49
60000
60000
Precision
1.00 + 0.00
1,00 0.00
1,00 + 0.00
1.00 0.00
Recall
0.99 1. 0.00
1.00 0.00
1,00 1 0.00
1.00 1. 0.00
Table 6: (MNIST- Partial Data Setting Known a) Results on synthetic dataset consisting of
uninformative MNIST data and informative Fashion-MNIST data using 25% MNIST.
Uninformative Data Num.
Informative Data Num.
Criterian
Confilence
SelectiveNet
DeepGambler
Ours
SK(%)
16.71 0.31
13.50 0.30
14.1143.3
IL.38 0.49
15000
3750
Precision
0.94 1. 0.02
1.00 0.000.0.000
1.00 1 0.00
1.00 1. 0..00
Recall
0.90 0.04
+.00
1.00 - 0.00
1.00 + 0.00
Sk(%)
13.93 0.40
13.31
11.20 = 0.22
11.29:0.44
15000
7500
Precision
0.96 + 0.01
0.99 0.01
1.00 = 0.00
1.00 +
Recall
0.95 1 0.02
0.93 0.93.10.00
1.00 0.00
1.00 1. 0.000
SK(%)
12.25 0.31
11.45 1145-033 0.37
10.61:0.12
10,42 0.48
15000
11250
Precision
0.97 = 0.01
1.00
1.00 0.00
0.99 + 0.00
Recall
0.95 0.03
1.00
1.00 0.00
1.00 + 0.00
Sk(%)
11.76 0.20
11.21 0.35
00.12=0.28
9.9720.33
15000
15000
Precision
0.01
1.000
0.01
Recall
0.95 0.02
1.00 1 0.00
1.00 = 0.00
1.00 + 0.00
Table 7: (SVHN Full Data Setting Known a)) Results on synthetic dataset consisting of uninformative SVHN and informative SVHN using the entire uninformative data.
Unifoormative Data Nua.
Informative Data Num.
Criterion
Confidence
SelectiveNet
DeepGambler
Ours
SR(%)
0.93
38.06 35.91
158 0.61
4.48=0.43
33800
9200
Precision
0.93 = 0.01
0.41 + 0.36
0.96 + 0.00
0.96 0.00
Recall
0.89 0.01
0.37 4 0.34
0.56 0.02
0.86 0.01
SR(%)
4.30 = 0.31
80.42 1.55
3.08 0.15
2.91:0.21
33800 18300
0.00
0.97 :
0.97 0.00
Recall
0.91 + 0.01
0.38 0.05
0.90 0.00
0.88 0.01
SR(%)
1.1920.06
5.22
3.86 0.11
0.65:0.17
33800
26200
Precision
0.96 0.68
0.96
0.97 + 0.00
0.96 0.00
Recall
0.91
0.03
0.91 0.00
0.93 0.01
SR(S)
10.87 0.66
8.27
7.65 0.447
6.3910.66
33800
28400
0.05
0.93 0.01
Recall
0.98 1: 0.00
0.95 0.004
0.97 1 0.01
0.96 0.01
Table 8: (SVHN Partial Data Setting Known a) Results on synthetic dataset consisting of
uninformative SVHN and informative SVHN using 25% uninformative data.
Uninformative Data Num.
Informative Data Num.
Criterion
Confidence
SelectiveNet
DeepGambler
Qurs
SR(%)
30. 10.13331
53.91 = 29.49
7.65-10.48
I1.74 2.432223
9200
2285
Precision
0.70 0.35
0.19 0.10
0.93 0.01
0.90 + 0.02
Recall
0.67 1 0.34
0.16 1 0.13
0.78
0.02
0.80 1 0.06
SR(S)
10.41 0.26
36.46 28.65
9.70 1.05
8.12 - 0.87
9200
4600
Precision
0,91 = 0.00
0.08 0.21
0.90 0.03
0.93 = 0.01
Recall
0.87 0.01
0.24
0.79
0.78 +
SR(%)
8.51=
31.97 = 30.15
7.49:10.47
0.92 + 7.67=0.63
Precision
0.92 0.02
0.21
0.94
Recall
0.91 0.02
0.74 1. 0.22
0.83 0.04
0.86 1 0.01
9.06
7.3710.51
9200
9200
Precision
0.91 = 0.01
0.88 = 0.00
0.93 0.01
0.92 = 0.01
Recall
0.94 0.01
0.92 0.01
0.88 0.03
+ 0.01
27

---

Under review as a conference paper at ICLR 2022
Table 9: Results on low noise level for both MNIST and SVHN Unknown a. We evaluate the
methods over different fractions of informative data.
Data S31
Unialommtivv Dota Num.
Informative Data Num.
Chiesion
Standard
SelectiveNet
DeepKäabler
Ours
SK(S)
21.59 = 0.33
14317 0:00
14:52 0.76
12,97 =: 2.84
MNIST
30000
60000
Precision
0.56 4: 0.00
0.93 1.000
0.91 4: 0.00
1.00 100=000 0.00
Recall
0.98 4: 0.00
1.00
1.004:0:00
0.98 0.00
SK(S)
34.73 + 0.87
06.17+00.00
34.20++0.01
18.72 6.31
MNIST
7500
15000
Procision
0.72 4: 0.01
0.72 0:00
0.74
0.96 = 0.00
Rocall
0.83 + 0.01
1.00 D:00
1.00
0.90 0.07
SR(S)
30.50 + 0.55
8.94
7.32 7.32++0.01
SVHN
18300
28400
Precision
0.71 + 0.01
0.92 +
0.93 + 0.01
0.96 0.00
Rocall
0.80 + 0.00
0.00 +
0.90 + 0:000
0.92 -192=10 0.01
SR(5)
0.00
17.48 0.02
SVHN
2300
9200
Precision
0.85 4: 0.01
0.86 0.02
0.85 4.02
0.95 0.01
Rocall
0.97 + 0.00
0.98 + 0.01
0.98 + 4:00
0.90 0000-001 0.01
Table 10: Results on low noise level for both MNIST and SVHN Known a. We evaluate the
methods over different fractions of informative data.
Data No1 Uninformarive Data Num. Informative Data Nam.
Criterion
Standard
SelectiveNet
DeepGumbler
Ours
SR(S)
8.19 = 0.32
8.17 0.12
8,09 +011
7.97 0.13
MNIST
60000
Precision
1.00
0:00
1,00 0:00
0.00
Recall
0,99 1: 0.00
1.00 0.00
1,00 1 0.00
1.00=0.00 0.00
SR(%)
11,55 = 0.38
11.77 0.21
9.75 0.63
10.37 = 0.13
MNIST
7500
15000
Precision
0.3 + 0.00
0.00
1.00 100+00000
0.00
Recall
0.87 0.01
0.86
0.00
SK(%)
1181 = 0.29
12.18 1118800
6,92 0.44
9.39 = 0.92
SVHN
18300
28400
Precision
0.89 1: 0.00
0.89 0.01
0.93 1 0.00
0.89 0.01
0.00
0.00
SM(S)
8.49 0.13
11.96 t: 1.18
6.81 : 0.60
8.43 = 1.41
SVHN 2300
9200
Precision
0,92 1: 0.01
0.89 0.01
0.95 1 0.01
0.92 0.02
Recall
0.01
0.01
0.90 0.01
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.
experiment where is unknown, the training and testing data set split is listed in Table The backbone we use is TinyCNN (in section D. 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 Ie-3 and weight decay le-4. We shrink our learning rate at epoch 45 and 90 by half each time.
For
For SVHN experiment where is unknown, the training and testing data set split is listed in Table IT The backhone we use is ResNet18. We use 128 as our batch size and train for 162 epochs for all listed methods. We use Adam the optimizer with learning rate 1e-3 and weight decay le-4. We shrink our learning rate at epoch 45 and 90 by half each time. For both experiments where a is known
Table 11: Experiment Data Splitting.
Diis Set
Unidformshee Training Dita N Vmm.
Informative Traming Dant Nam. Uninformative Tesling Dita Num.
Lifomiiive Training Data Num.
00000
00000
10000
40000
45000
7500
10300
2500
MNIST
30000
15000
60000
15000
10000
5000
10000
10000
15000
11250
10000
7500
15000
7500
10000
5000
15000
3750
10000
2500
7500
15000
5000
10000
35300
28200
T1500
33800
11500
9100
33800
11900
6500
33800
9200
11900
3300
SVHN
18300
9200
28400
9200
11900
6500
9600
9800
9200
6900
11900
9100
9200
4600
11500
6500
9200
2300
11900
3300
4600
6500
9800
and HPO is enabled, we maintain the same backbone and optimizer. The hyper-yaramen parameter setting is documented in the code. The code will be open sourced together with the publication of the paper.
28

---

Under review as a conference paper at ICLR 2022
E EXTENTION OF THEOREM 4 ON a IS GIVEN
IN THE CASE WHERE ONLY AN UPPER BOUND
Theorem 5. Under Assumption given set of samples S, {(11, yn ...., (In yn)] drawn iid. from the Noisy Generative Process with a E (0, - E 2 0.2 hy-
pothesis class H with VC-dimension due(H), F with VC-dimension (F) and fs.
arg min Rs(f).9s." = arg min Ws. (g, 0). 1f E : [1+ + 2[1-5] 10ja) and
DEH
3200 (due (70) (n) (F))
loRt HoRk
n
cta
We have with probability at least 8:
I)
Plgs. (x) 2 0lg((x) s 0J = (c) [False Positive)
(39)
Plgs, (x) Olg" (z) 2 0J s O(e)
[False Negativel
II)
PAND, [f (x) + fs. r 05. (x) 2 0] O(c)
III)
Further more, to obtain gs." arg min Ws. (g. f3.. 8) it suffices to minimize following gE
loss with B E (1 + 735-1' min 2(1-E) 10}):
Loss(g: S&., Sn, B) = (S, (x.) + v (g((t))))))))))))))))))))))}))) > 0} + [SG, (x)) = (o(o) 0}}
Proof. I) above can be proved by picking c E this range is valid since a S E. we have
1
min أ }) in Theorem
Note
144
a
1- a
a S 1
-
{
51
21
- 0
1
α
(40)
1 O
<
2(1 8
20
+ a
<
4(1 - g)
4a
By procedure similar to Theorem 4 (using the Sauer's Lemma) we have 7). Note c E ( + 1 1/2 min(1, )))-E))) + E
72 min(1+ 2[--]:: : II) can be proved by observing that I) implies Plgs, (x) * (x)) = O(e) and by invoking Theorem Next we prove III).
13x
E
easy to verify that the minimizer of Ws., (g. fš..) is equivalent to minimizer of Loss(g; f$.. Sn, B) (by replacing B 0(1-a)) ). suffices to analyze that B E (1 73द-1, min + - 10)) implies that ç
0 E (Tee mēn + 2(1 2(1-))) 10}a) First note that 1-x is monotone increasing in (0, 1), it suffices to compute image of ((1-a) and check B E (1 - min + 2 10)) stays such range. and a >> 0 implies the
a(l-0)
be easily verified that a < 1 implies the lower bound 738-T
upper bound + 2(1-))
&
F ABLATION STUDY ON HYPERPARAMETERS
We provide ablation study where vary the byper-parameter in each baseline. For SelectiveNet, we first fix X to be 32 (default setting that is recommended by the author the original paper) and then vary a from 0.1 to 0.7. Then fix be 0.5 (default setting) and then we vary À
29

---

algorithm Under review as a conference paper at ICLR 2022
from to 66. For DeepGambler, vary from 1 to 7. Finally, for our algorithm, we increase the hyper-parameter 3 4 to 10. We can see that the performance of all basclines are quite sensitive to the choice of hyper-parameter and will experience some large fluctuation. On the contrast. stable against the choice of hyper-parametee This empirical observation supports that there exists wide range of 3 that one 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 '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 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.
100
80302/60000
1.0
Selecive Rak (%)
80
25000/11000
25003/3150
0.8
0.8
60-
Praciaion
40-
0.4
0.4
60000/60000
60000/60000
60002/15000
60000/15000
0.2
15000/3750
15000/3750
0.0
0.0
8
8
Selective Risk (%)
Precision
Recall
Figure 4: Ablation Study Hyper-parameter 3 Our Method.
100
10
60000000000
00000/15000
Selectvv Risk (%)
0.8
25000/3750
0.0
Precsion
0.6
0.4
60000/60000
60000/60000
60000/15060
15000/13000
0.2
022
15000/15000
15000/3750
23000/3/30
0.0
Selective Risk (%)
Precision
Recall
Figure 5: Ablation Study on seper-parameter o DeepGambler.
30

---

Under review as a conference paper at ICLR 2022
100
80303/50000
00000-00000
60303/1500
60000/15000
Seloctive Risk (16)
15000/3750
10000/11000
0.8
15000/3750
0.8
Precision
0.6
B0000/00000
60000/15000
0.2
0.2
15000/15000
15000/3750
0.1
0.3
0.7
0.3
0.5
100
10
60002/15000
80
35000/15000
Saloctive Risk (S))
0.8
15000/3750
0.8
Prectsion
0.4
0.4
80001U60000
60000/60000
600C0/15000
80000/15000
15000/1-000
15000/15000
15000/3/50
15000/3750
0.0
32
50
60
10
Selective Risk (%)
Precision
Recall
Figure 6: Ablation Study on Hyper-parameter a and À SelectiveNet.
31


Reviews:
[{"review_id": "p1Abzya9wzQ", "reviewer": "Reviewer_QnTY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of the paper is a new model for prediction with abstention, which postulates that samples in one region of the feature space can be predicted well, while in the rest of the space entirely unpredictable.  Under this model, the authors derive an oracle-based algorithm which can provably recover both the informative-partition (selector) and a good model on it (predictor).  For practical settings one can not always assume exact minimization of the empirical risk, so the authors propose an iterative algorithm which alternates learning the selector and the predictor, using something akin to multiplicative updates. Under the assumed generative models it seems to outperform baselines, sometimes by a wide margin, especially in a setting where the fraction of informative samples is small. \n\nThe paper mostly reads well, has detailed theoretical analysis (which I only had a chance to skim), and presents experimental evidence supporting the claims.\n\nMy main criticism of the paper is: \n1) To me the model seems entirely artificial, and I am not aware of any realistic settings where the data can be partitioned into a region with great classification, and an uninformative region. For high-noise data in my experience it's much more common that there is a fairly weak signal over the entire feature space, with no pockets of high predictability. I'd be very interested to hear evidence on the contrary.  The examples are very stylized, and likely heavily leverage the fact that they match the assumed generative model. Showing how this translates to a more realistic example would have been helpful -- as the analysis may have a chance to be suggestive for more practical settings as well. \n\n2) I am surprised that using methods which allow uncertainty quantification -- e.g. maybe bootstrap resampling, or say Gaussian processes would have a hard time in this setting. I would have expected that it's not that hard to learn to distinguish MNIST from fashion MNIST, and to assign tight confidences around the region of MNIST examples, while giving large error bars to fashion-MNIST. Is the problem that the \"Model prediction confidence\" gives out incorrect (i.e. uncalibrated confidences?).  For DNNs and many other learners this overconfidence is a well-known problem (e.g. there's a nice paper \"On Calibration of Modern Neural Networks\" from Killian Weinberger's group,  and also well known solutions, for example from Charler Elkan and Bianca Zadrozny, \"Obtaining calibrated probability estimates for classifiers\".  \n\n3) If instead of trying to identify the \"predictable region\" -- you try to apply / modify the method to attack the original selective prediction -- is it competitive with existing approaches? My suspicion is that the approach is quite dependent on having data with a well-separated true informative/uninformative partition -- and going after support recovery. \n\n4) How do you incorporate the complexity of the decision boundary for the selector?  If you assume a simple function class -- e.g. linearly separable in low-dimensions I assume it's easy to identify -- but generally the selector region may itself has a complex boundary, which may require regularization to learn.  How do you balance the regularization of the selector vs. the selector accuracy vs. the predictor accuracy (vs predictor regularization)?  It seems practically daunting. \n\n5) You mention that the predictable region has to be high-signal-to-noise. How sensitive it is to this? For example if there are two regions, one already noisy, and another completely unpredictable, how quickly does it break down with the SNR?\n", "summary_of_the_paper": "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. ", "summary_of_the_review": "This paper proposes a novel formulation supervised learning with abstention. It assumes that feature space can be split into an informative region, and a completely unpredictable region.  It offers detailed theoretical analysis showing that recovery is possible, and a heuristic practical algorithms to both recover the partition of the feature-space, as well as learning the model over the predictable region.  The setting is interesting -- but I suspect it's very artificial, so I'd be very curious to know to what extent this has relevance to applications which have no clear-cut partitions (or to traditional selective inference).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "dswtt84LbeN", "reviewer": "Reviewer_zieu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written, clearly organized and easy to follow. The problem of identifying uninformative data is interesting and very relevant in modern machine learning. The theory of the paper---though highly stylized and is based on $0-1$ loss that cannot be optimized efficiently---is revealing and also a good starting point. However, this is also the main weakness of the paper, the algorithm analyzed is based on $0-1$ loss that cannot be solved efficiently, while the heuristic algorithm implemented is based on the cross-entropy surrogate.\n\nSome detailed comments are listed below:\n\n1. In the setup that the uninformative part consists of pure noise while the informative part is noiseless in Eq. (2), which seems a bit unrealistic. Can the authors explain why in the informative part of the data cannot be random? (say $\\mathsf{sign}(P(y=1|x) - 1/2) = f^\\star(x)$ under some Mammen-Tsybakov condition/margin condition)\n2. The empirical studies are not exactly supported by the theory as they are essentially different algorithms.\n3. Can the authors specify what are the hypothesis classes in the experimental setup?\n\n", "summary_of_the_paper": "The authors analyze selective learning when part of the data is pure noise and uninformative. The paper presents an algorithm by a two-phase optimization procedure and provide PAC bounds for both the ground truth predictor $f^\\star$ and the selector $g^\\star$.", "summary_of_the_review": "The paper studies identifying uninformative data in datasets which is a very relevant problem for the machine learning community. The algorithm analyzed in the paper is supported by interesting theoretical results and can be revealing for more realistic algorithms.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_jl4nPeZx7B", "reviewer": "Reviewer_8Gu4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength & Weakness: I am conflicted about the main structure of the paper of cleanly separated completely noisy and completely clean data with both aspects realisable. In my opinion this situation is quite unrealistic, which meaningfully impairs the study. Nevertheless, this seems to be the analogue of realisability relevant to selective classification, and thus a natural setting to investigate tight bounds on the basic aspects of the problem. That said, I don't think the paper makes this case sufficiently well, instead posing the setting as a sort of Huber-type contamination of the data that persists to test time, but is kind enough to be entirely separate from the real data - this is quite unconvincing to me. \n\nStrengths: Modulo the above, I find the basic idea of the scheme and the loss embodying it to be quite interesting, and the analysis supporting it is straightforward, and natural. I find the heuristic to be even more interesting, in particular due to the multiplicative weighting idea, which I think is an elegant way of reinforcing the attention of $f$. The empirical results are, of course, stark and impressive, but I have some reservations about the same (see below)\n\nWeakness:\n\n- Theoretically, there are two gaps - the major one, in my opinion, is that the analysis requires a priori knowledge of $\\alpha$ to appropriately set $\\theta$ for the loss. This I think weakens the results significantly. One way to ameliorate this would be to extend the results so that an upper bound on $\\alpha$ is sufficient (which is a much more realistic assumption, although of course ideally the method should adapt to $\\alpha$). Also important, but less so, is the lack of a lower bound for the problem (it is clear that reliably estimating $f^*$ would necessitate the use of $\\Omega( (\\alpha \\epsilon)^{-2})$ samples, I don't think this fact is all that interesting).\n\n- Specifically regarding the experiments, I have questions about the baselines, and the proposed method's hyperparameter selection.\n\n    - Lack of explanation of the results: The empirical results presented are starkly positive, but the exposition offered does not clarify what aspect of the scheme is buying this performance . For instance, all the methods seem to estimate the underlying $g^*$ well, but the competing methods cannot offer appropriate labels. Is this because of the repeated multiplicative re-weighting in the loss for $f$? Do the results hold if this is turned off? Does a similar iterative training improve the risk for the competing methods? I think ablative analysis along these lines is crucial for understanding the contribution of this paper.\n\n    - Lack of clarity about baselines.\n        - With empirical performances so starkly different, I cannot but help question if the baselines are being fairly executed. The big issue here is whether the hyperparameters for these methods are being selected in an appropriate way - this is bolstered by the situation of Tables 5-8, where $\\alpha$ is assumed to be available to the algorithms, and the baseline hyperparameters are thus  presumably being set appropriately, and the performance gaps are much reduced. This leads me to the following questions:\n            - Does this procedure given on page 8 yield a decent estimate of $\\alpha$? How does performance vary if you train for more epochs?\n            - In the appendix, it is stated that default hyperparameters are used for each method. What does this mean for something like selective net? \n            - The baseline 'Confidence' is never described. Is this the method proposed by Geifman & El-Yaniv 2017? Something else? Does this method have hyperparameters? How are they tuned?\n I understand that choosing the hyperparameter in these prior methods for this particular scenario may be considered beyond the scope of this paper, but in my opinion unless it is justified that the hyperparameters are being selected in a meaningful way, this presentation is meaningless. \n\n    - Hyperparameter selection for the proposed method: how precisely is $\\beta$ selected? This is never described in the text, and the only reference to it appears in Appendix D where it is said that the default parameter $\\frac{\\theta (1-\\alpha)}{\\alpha (1-\\theta)}$ is used. This is both non-informative, because the question then becomes how is $\\theta$ selected, and troubling, because it appears that $\\alpha$ is being used to pick $\\beta$. Is this the case?\n\n\n- Relation to prior literature:\n\nI think the selective classification literature is slightly mischaracterised, in the sense that it is not restricted to coverage oriented designs, as is suggested on page 3. Three explicit references theoretically and methodologically studying low-error selective classification are [1,2,3], all of which give PAC-style definitions regarding attaining low error selective classifiers, and [1] shows various computational reductions regarding the learnability of selective classifiers, and [2,3] provide sample complexity guarantees. In fact I believe Proposition 4 in [3] is directly applicable to the situation of this paper. Further, [3] also proposes a method that empirically dominates both the selective net and deep gamblers methods, and so might be good to compare to.\n\nAdditionally, I think [4] might be a pertinent reference, since it too proposes an alternating minimisation strategy for learning selective classifiers (although I think there's plenty of novelty in the presently proposed method beyond this).\n\n[1] Adam Tauman Kalai, Varun Kanade, and Yishay Mansour. Reliable agnostic learning. Journal of Computer and System Sciences, 2012.\n\n[2] Durmus Alp Emre Acar, Aditya Gangrade, and Venkatesh Saligrama. Budget Learning via Bracketing. AISTATS, 2020.\n\n[3] Aditya Gangrade, Anil Kag, and Venkatesh Saligrama. Selective Classification via One-Sided Prediction. AISTATS, 2021.\n\n[4] Feng Nan, and Venkatesh Saligrama. Adaptive Classification for Prediction Under a Budget. NIPS, 2017.\n\n---\n\nQuestions and Comments:\n\n- Assuming that the experiments are kosher, do you have hypotheses for how the advantage is being gained over the baselines? I noticed that the precision and recall (presumably of the selection with respect to a noisy/not-noisy oracle) of all methods are similar. Does this mean that the other methods are simply not learning the correct predictions on the domain they do select? \n\n- For the theoretical parts, I haven't checked this thoroughly, but it seems like it should be possible to get away with using about $\\frac{d(\\mathcal{F}) + d(\\mathcal{H})}{\\min(\\alpha, 1-\\alpha)\\epsilon}$ labeled and $\\frac{d(\\mathcal{H})}{\\alpha^2 \\epsilon^2}$ labeled datapoints (up to $\\log$s) by picking $g$ to be the maximiser of ${\\hat{P}}_\\{\\lnot \\ell\\}(g = 1)$  subject to the constraint that $\\hat{P}_\\{ \\ell\\}(f \\neq Y, g = 1) = 0$, where $\\hat{P}$s are unlabeled and labelled empirical measures. Note that this is just the scheme of [3]..\n\n\nQuibbles:\n\n- I don't think $f^*$ as defined really makes sense. It is ostensibly defined on all of the space, but it clearly cannot be uniquely defined here in even mildly rich settings - for instance, if $\\mathcal{F}$ has functions that agree on $\\Omega_I$ but differ on $\\Omega_D$. \n- In section 3, the abstention criterion suddenly switches from $g = -1$ to $g < 0$. While mathematically identical, such devices are commonly used in the ML literature to semantically adjust  functions from 'hard' to 'soft'. Is this the intention here? If not, perhaps the authors can stick to one presentation? More importantly, in section 3.3 $g$ suddenly switches to being $[0,1]$ valued, and the abstention criterion to $g < 0.5.$ I understand that this is for the sake of the cross-entropy loss, but this is needlessly confusing - I think consistency here saves your readers needless recalibration.  \n- It is strange that $g$ is taken to lie in $\\mathcal{H}$ rather than $\\mathcal{G}.$  \n", "summary_of_the_paper": "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 \n- The labels are completely noisy ($\\mathrm{Bern}(1/2)$) if the input lies in $\\Omega_U$.\n- The labels are completely clean if the input lies in $\\Omega_I$.\n- The learner has access to hypothesis classes $\\mathcal{F}, \\mathcal{H}$ such that \n    - There exists an $f^* \\in \\mathcal{F}$ with $f^*(x) = y$ on $\\Omega_I$.\n    - There exists a $g^* \\in \\mathcal{H}$ with $g^*(x) = 2\\mathbf{1}\\{x \\in \\Omega_I\\} - 1.$\n\nThe 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.\n\nThis 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})$.\n\nThe 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.", "summary_of_the_review": "On the whole, I think that while I don't find the scenario posed by the paper convincing, I do find the concrete setting itself to be so. The scheme proposed for the same is interesting, and, taken at face value, very effective. Nevertheless, I right now am not convinced that the baselines are being compared to correctly, which needs to be justified, and further, I think that ablative experiments illuminating how the aspects of the proposed contribute to performance are needed. I think without these, though, the theoretical study ultimately produces a sample complexity analysis for a method that uses the knowledge of a key underlying parameter, and even then is not shown to be tight, which is a bit too weak, and I think needs more work.\n\nWith the above consideration, I have reservations about recommending acceptance as the paper stands. I am willing to budge on this if the experiments are clarified, or if the analysis can be improved. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3e4A5I4K_Q", "reviewer": "Reviewer_vqyY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths.\n\nThe paper is organized well with clear problem formulation, definitions & assumptions. The methodology is supported with theoretical results and implemented by an iterative algorithm. While the problem formulation requires uninformative samples are separated from informative ones, the authors also tested more challenging settings in the experiments.\n\nWeaknesses. \n\nThere are previous papers related that are missing here. For example, \"Combating Label Noise in Deep Learning Using Abstention\" by Thulasidasan et al. also seems to do very similar things and has similar title, but is not discussed in the related work. Also, some descriptions to previous works are not accurate, e.g., \"While above works assume the presence of noisy data only in the training stage\" -- some of the works above are in the parameter recovery setting, so it is slightly unfair to compare without the problem setting described clearly. \n\n\n", "summary_of_the_paper": "The paper considers a setting where the label is random noise if the input is in an uninformative subspace, provides theoretical analysis for the estimated predictor/selector that minimizes classification risk/a novel selector loss, proposes a practical iterative algorithm to approximate the estimators based on MWU, and tests on semi-synthetic experiments. ", "summary_of_the_review": "The paper is well written in general. The descriptions on related literature need some improvement. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies a learning scenario in which there exist 2 classes of examples: "predictable" and "noise". Learning theory is provided for this setting and a novel algorithm is devised that identifies predictable examples and makes predictions at the same time. A more practical algorithm is devised as well. Results are supported by experiments.

Reviewers have raised a number of concerns (ranging from how realistic this settings is to missing references). Overall they found this work interesting and relevant to ML community and appreciate the effort that authors have put in in their thoughtful response. However, after a thorough deliberation conference program committee decided that the paper is not sufficiently strong in its current form to be accepted.
Decision: Reject