Learning to Abstain from Uninformative Data
Authors: Yikai Zhang
Songzhu Zheng
Mina Dalirrooyfard
Pengxiang Wu
Anderson Schneider
Yuriy Nevmyvaka
Chao Chen
Venue: Submitted to ICLR 2023 (2023)
Keywords: PAC Learning
Sample Complexity
Selective Learning
Uninformative Data

Abstract: Learning and decision making in domains with naturally high noise-to-signal ratios – such as Finance or Healthcare – can be challenging yet extremely important. In this paper, we study a problem of learning and decision making under a general noisy generative process. The  distribution has a significant proportion of uninformative data with high noise in label, while part of the data contains useful information represented by low label noise. This dichotomy is present during both training and inference, which requires the proper handling of uninformative data at testing time. We propose a novel approach to learn under these conditions via a loss inspired by the selective learning theory. By minimizing the loss, the model is guaranteed to make a near-optimal decision by distinguishing informative data from the uninformative data and making predictions.  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 settings.

Under review as a conference paper at ICLR 2023
LEARNING TO ABSTAIN FROM UNINFORMATIVE 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 Healthcare can be challenging yet extremely important. In this paper, we study a problem of learning and decision making under general noisy generative process. The distribution has a significant proportion of unin- formative data with high noise in label, while part of the data contains useful information represented by low label noise. This dichotomy is present during both training and inference, which requires the proper handling of uninformative data testing time. We propose novel approach to learn under these conditions via a loss inspired by the selective learning theory. By minimizing the loss, the model is guaranteed to make near-optimal decision by distinguishing informative data from the uninformative data and making predictions. 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 variety of settings.
INTRODUCTION
Despite the success of machine learning in computer vision (Krizhessky et al. 2009 He et al.
201 6a
Huang al. 2017) and natural language processing (Vaswani et al.) [001] Devlin et al. 2018). the power of ML is yet to make significant impact in other areas such as finance and public health. One major challenge is the inherently high noise-to-signal ratio in certain domains. In financial statistical arbitrage, the spread between two assets are usually modeled using Orstein-Uhlember Uhlembeck processes (Øksendal] 2003) Avellaneda & Lee 2010). Spread behaves almost purely random near zero and are naturally unpredictable. They become predictable in certain rare pockets/scenarios, For example, when spread exceeds certain threshold, with high probability it will move toward zero, making arbitrage possible. In cancer research, due to limited resources, only a small number of the most popular gene mutations are routinely tested for differential diagnosis and prognosis. However, due to the long tail distribution of mutation frequencies across genes, these popular gene mutations can only capture a small proportion of the relevant list of driver mutations of a patient (Reddy et al., 2017). For significant number of patients, the tested gene mutations may not be in the relevant list of driver mutations and its relationship w.r.t. the outcome may appear completely random. Identifying these patients automatically will justify additional gene mutation testing.
These high noise-to-signal ratio datasets pose new challenges to learning. New methods are required deal with large fraction of uninformaaive/high-nooi
data in both training and testing stages. The source of uninformative data can be either due to the random nature of the data generating process, or due to the fact that the real causing factor is captured during data collection. Direct application of standard supervised learning methods to such datasets is both challenging and unwarranted. Deep neural networks are even more affected by the presence of noise, due their strong memorization power (Zhang et al. 2017a]: they are likely to overfit the noise and make overly confident predictions where weak/no real structure exists.
In this paper, we propose a novel method for learning on datasets where a significant portion of content has high noise. Instead of forcing the classifier to make predictions for every sample, we learn to decide whether a datapoint is informative not. Our idea is inspired by the classic selective prediction problem (Chow) 1957). in which one learns to select a subset of the data and only predict on that subset. However, the goal of selective prediction is very different from ours. A selective prediction method pursues a balance between coverage (i.e. proportion of the data selected) and conditional accuracy on the selected data, and does not explicitly model the underlying generative

---

Under review as a conference paper at ICLR 2023
process. In particular, the aforementioned balance needs to be specified by human expert, as opposed to being derived directly from the data. In our problem. we assume that uninformative data is an integral part of the underlying generative process and needs to be accounted for. By definition, no learning method, no matter how powerful, can successfully make predictions on uninformative data. Our goal is therefore identify these uninformative/ligh noise samples, and at the same time, to train a classifier that suffers less from the noisy data.
Our method learns selector, g. to approximate the optimal indicator function of informative data, g" We assume that 9" exists as a part of the data generation process, but it is never revealed to us, even during training. Instead of direct supervision, we therefore must rely on the predictor's 's mistakes to train the selector. To achieve this goal, we propose a novel selector loss enforcing that (1) the selected data best fits the predictor, and (2) the portion of the data where we abstain from forecasting, does not contain many correct predictions. This loss function is quite different from the loss in classic selective prediction, which penalizes all unselected data equally.
We theoretically analyze our method under general noisy data generation process which follows
the standard data dependent label noise model (Massart & Nédélec, 2006 Hanneke 2009). We distinguish informativv/uuiiformaaa this paper is the derivation of theoretical guarantees for the empirical minimizer of our loss. A minimax-optimm sample complexity bound for approximating the optimal selector is provided. We show that optimizing the selector loss can recover nearly all the informative data in a PAC fashion (Valiant 1984). This guarantee holds even in challenging setting where the uninformative data has purely random labels, and dominates the training set.
data via gap in label noise ratio. A major contribution of
This theoretical guarantee empowers us expand more realistic setting where sample size is limited, and the initial predictor is not sufficiently close to the ground truth. Our method extends to an iterative algorithm, in which both the predictor and the selector are progressively optimized. The selector is improved by optimizing our novel selector loss. Mcanwhile, the predictor is improved by optimizing the empirical risk, we-whittted based on the selector's output; uninformative samples identified by the selector will be down-weighed. Experiments on both synthetic and real-world datasets demonstrate the merit of our method compared to existing baselines.
2 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. [013] Han et al.] 2018 Yu et al., [2019; /Zheng et al., 2020
Zhang et al.) 2020). Massart Noise (Massart & Nédélec 2006; Awasthi et al., 2015] Hanneke
2009:
Hanneke & Yang 2015) Yan & Zhhng] 2017 Diakonikolas et 2019 2
Cheng et al.
2020
Xia et al. Zhang& & 2i[20 and adversarial noise (Kearns & Li 1993 Kearns et al.
1994 Kalai et al., 2008, Klivans et al. 2009| Awasthi et al. 2017). Our noise model is similar
to General Massart Noise (Massart Nédélec 2006) Hanneke| 2009 Diakonikolas et al., 2019), where the label noise is data dependent and label can be generated via a purely random coin flipping. The major distinct formulation in our noisy generative model is the existence of some uninformative data with high noise in label compared informative data with low noise in label. We characterize such wwwtformativeeinfrmaaat gap. While there exists long history of literature studying learning classitiers with label noise in the training stage (Thulasidasan et al. 20119) Cheng et al. 2020; Xia et al. 2020). we are the first work to investigate learning model for inference stage under label noise setting. We study the case where label noise is an integral part of the generative process and thus will appear during inference stage as well, where must be detected and discarded once more. We view this as a realistic setup in industries like Finance and Healthcare.
data structure via non-vanishing label noise ratio
2010 Kalai et al. 1970 El- Yaniv et al. Selective learning an active research area (Chow 1957
2012 Nan & Saligrama| 2017 Ni et al. 2019 Acar et al. 2020 Gangrade et al. 2021a It extends the classic selective prediction problem and studies how to select a subset of data for different learning tasks, and has also been generalized to other problems, e.g., learning to defer human expert (Madras)
et al. 2018 Mozannar & Sontag 2020). We can summarize existing methods into 4 categories: Monte Carlo sampling based methods (Gal & Ghahramani 2016] Kendall & Gall [017 |eaaree et al.
2020). margin based methods (Fumera & Roli 2002) Bartlett & Wegkamp 2008]]0rana Grandvalet et al.
2008 Wegkamp et al. 2011 /Zhang et al. 2018), confidence based methods (Wiener & El-Yaniv
2

---

Under review as a conference paper at ICLR 2023
2011
Geifman & EI- Yaniv
2017; Jiang et al. 2018) and customized selective loss (Cortes et al. 2016
Geifman & EI- Yaniy| 2019 Liu et al. 2019; Gangrade et al., (021b). Notably, several works propose customized losses, and incorporate them into neural networks. In (Geifman & El- Yaniv 2019) the
network maintains an extra output neuron to indicate rejection of datapoints, Liu et al. (019 uses Gambler loss where cost term is associated with each output neuron and doubling-rates
loss function is used to balance rejections and predictions. Thulasidasan et al. (019)) also applies an extra output neuron for identifying noise label to improve the robustness in learning. Huang et al. (2020) adopts progressive label smoothing method which prevents DNN from overfitting and improves selective risk when applied to selective classification task. CCottes et al., (2016) perform data selection with an extra model and introduce a selective loss that helps maximize the coverage ratio, thus trading off a small fraction of data for better precision. Sharing a similar spirit with (Kalai al. (0012). (Gangrade et al. 2021b) applies an one-side prediction method to model high confidence region for each individual class, and maximizes coverage while maintains a low risk level.
Existing works on selective prediction are all motivated by the trade off between accuracy and coverage - i.e. one wants to make safe prediction to achieve higher precision while maintaining a reasonable recall. Our paper is the first to investigate the case where some (or even majority) of the data is uninformative, and thus must be discarded at test time. Unlike the selective prediction, there is latent ground truth indicator function of whether data point should be selected not. Our method is guaranteed to identify those uninformative samples.
PROBLEM FORMULATION
In this section, we describe our model for the inherently-noise data generation process that we aim to study.
Definition (Noisy Generative Process). We define Noisy Generative Process by the following
notation x ~ Do where
1 ~ DU with prob. --a a (Uninformative) ~ Dj with prob. a (Informative).
Da =
Let the ground truth labeling function f (+1,, +1+1,-11 be in hypothesis class F. Let Qpp C Rd
be the support of Drr Suppose (aw, } is partition of l.D. Let X(x) E (X, 2 with X >> 0, the latent informativeeniinfomaatvve status E {+1, -1} has posterior distribution:
M(x), if E Qy
P| = 1|2]
(2)
+ \(x), x E Ω4
The observed data (x. v) is generated according
x ~ Dai
z Piz[æ];
(e.5
if =- =
y = (x).
Since A(az) > O, from fy has lower chance to be observed with true label compared f2,, thus can be viewed as uninformative data, in a relative sense. On the contrary, x from 22 can be viewed as informative data. Our Noisy Generative Process follows standard data dependent label noise, e.g..
Massart Noise (Massart & Nédélec 2006) and Benign Label Noise (Hanneke) 2009 Hanneke & Yang 2015 Diakonikolas et al. 2019 Indeed, one can always choose A(x) E [0, J and a E 1,
replicate General Massart noise. Compared to classical label noise models, the assumption A(x) > X
introduces a label noise ratio gap, which distinguishes the informative and uninformative data. In Equation
label noise serves as proxy for "white noise" in label corruption. When X( [ = 1 and x: E Sy (ernoulli(O.5) random label noise can viewed as the strongest known non-adveraarial label noise, of both theoretical and practical interest (Diakonikolas et al.) 2019). Such Bernoulli(0.5) random label noise could happen when card-so-classify examples are shown to human annotator (Klebanov & Beigman 2010), or when fluctuations in financial market closely resemble random walks (205).
3 the Bernoulli
2
A typical setting that is studied in this work is the case that both value of a and À are non-vanis,ing, ie., there are significant fraction of uninformative data (large a) and the label noise ratio gap is distinguishable between informative and uninformative data (large A).
3

---

Under review as a conference paper at ICLR 2023
Next definition describes recoverable condition of the optimal function for the latent informa- tive/uninformative status 2.
Definition 2 (G-realizable Given support Ωt and X(x) (A, 2) let the posterior distribution of be defined in Equation ( We say Q is G-realizable if there exists g" E 9
{+1,
satisfying 9" (x) [1 1 --11
Ideally, one wish to select all informative data where signal dominates noise. This can be done via recovering g (-), which we view as the ground truth selector we wish recover. The G-realizable condition is analogous to the realizability condition (Massart & Nédélec 2006 Hanneke & Yang 2015) classical label noise problem. The major difference and challenge in recovering ("(:) compared to learning a classifier, is that there is no direct observation on the informative/non- informative status z. The major contribution of this work is proposing a natural selector risk which recovers 9* (.) without observing latent variable z.
Having introduced the data generation process, we now describe the learning task:
Assumption Data Sn {æ:, Y: Vi is i.i.d generated according to the Noisy Generative Process (Definition 7.. with I* E F and support Ω satisfies G-realizable condition.
Given the above assumption, we are interested in the following learning task:
Problem 1 (Abstain from Uninformative Data). Under Assumption 7 with i..d observations from
Dao given f E F sufficiently close to f (x)), we aim to learn a selector 9 E G that is close to g (a:).
Claspite Outout y=00
Classfier
Uninfomative
Trediction
informative Data Uninformtivv Dats
Claspiter Comect
Selective Srediction y
Chasoher incomests
Selector Abstained
(a) InformativeCUninfoomaiiee data
(b) Correct/Incorreet classification result
(c) Selective classification
result
Figure 1: Illustration of the learning strategy with mixture of Gaussian data. We replace the 0-1 loss with hinge loss and train SVM models for f and g. (a) upper panel shows original dataset and bottom panel shows the region of informative (casy) and uninformative (hard) data. (b) shows that the classifier has high accuracy in the informative region, but low accuracy in the uninformative region. In (c), the selector trained with f successfully recovers informative support thus resulting in low selective risk, and we abstain from making prediction elsewhere.
4 OUR METHOD
In this section, we present our approach for learning and abstaining in the presence uninformative data (Problem The main challenge is that the latent infommaive/lninformaaii status of datapoint unknown. Our main idea is to introduce a novel yet natural selector loss function that trains selector based on the performance of the best predictor (Section 4.1) In Section 4. we present our main theoretical result. We show that, given any reasonably good classifier, finding a selector minimizing the proposed selector loss, complexity. Inspired by the theoretical results, Section 6 we propose a heuristic algorithm that iteratively optimizes the predictor and the selector.
solve Problem [ with minimax-optimall sample
4

---

Under review as a conference paper at ICLR 2023
4.1
SELECTOR LOSS
In idealized setting, when access to latent rrformatieeuminnormativeee variables {(z,, 24) [=] is available, recovering g shares a similar spirit with learning classfier under label noise. suffices to minimize following classical classification risk:
Non-Realizable Risk(g: S,)) = Σ 1g(0))) + 23}
(4)
However, in practice is never revealed. To learn selector without direct supervision, we have to leverage the performance of predictor f. We propose replace 2 in the Equation [ with pseudl-informative label {(x))) # y), which has randomness coming from z and noisy label y- Definition (Selector Loss). Given f E F and its selector g 9, we define the following empirical version of weighted 0-1 type risk w.r. g() as selector risk:
Rs, (g: (, Σ (BI((()) + (.)))(())))) > 03 1[(())) = 50) (5)
The selector loss is also a natural metric to evaluate the quality of the selector. This loss penalizes when (I) the predictor makes a correct prediction on a datapoint that the selector considers uninformative and abstains from, or (2) the predictor makes an incorrect prediction on datapoint that the selector considers informative. Intuitively, 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 more accurate. Meanwhile, within the uninformative region, the label random and the predictor is supposed to be more prone to error.
Note that there are two types of errors penalized the selector loss: an incorrect prediction on a selected datapoint, (f(x) ) * y) A (o(x) > 0), and correct prediction
unselected datapoint, (f(x) = y) A (g( x)) S 0). Since the label noise is non-adversarial, y tends to have higher probability of coincidence with f (a=), introducing imbalance
the beeuo-informative label. We thus use / to weigh these two types of errors the loss. An analysis can be found in section [A.] on the choice of B. Our theoretical analysis suggests that for wide range of the accuracy of the selector is guaranteed. Empirical study also shows stability with regard to these choices.
Learning selector with the novel loss. To learn selector, one follow standard procedure e.g.. empirical risk minimizationnERMM), to estimate predictor f with reasonable quality. The selector can be estimated by minimizing the selector loss g = arg mingeg Rs. (g. f. 3). conditioned on the estimated predictor f.
In Figure D
we show an example of using the ERM strategy using SVM with 0-1 loss replaced by hinge loss. In this case, the losses are all convex and the empirical minimizers I and ğ can be computed exactly.
In practice, however, empirical minimization is not always possible, as optimization for complex models (c.g., DNNs) and non-convex losses remains open. We therefore propose a heuristic algorithm in the spirit of our thcoretical results it jointly learns f and g by minimizing the selector loss and reweighed classification risk iteratively (see Section 6
MINIMAX-OPITMA RISK BOUND
In this section we present our main theoretical results. The main result can be summarized in following (informal) statement.
Main Result (Informal) For any reasonably good predictor f. with sufficient data, the selector 9 estimated using و arg min Rss,, (g. f. B) is sufficiently close to the targets g" with high probability.
Remark 1. The toolkit we use in the proof is a Bernstein type inequality for fast generalization rate under margin condition (Massart & Nédélec 2006; Van Erven et al. 2015 Li & Liu (021). We also provide an information theoretic lower bound construction in section|A22 show our risk bound is minimax-optimal. Our construction of the lower bound is motivated from (Ehrenfeucht al. 1989
5

---

Under review as a conference paper at ICLR 2023
1997 Due space constraints, detailed proofs of our theorems are provided in the Appendix. We also present our extension from finite hypothesis class to VC-class using Local Rademacher Average tools (Bartlett et al. 2005) in section In the analysis, we do not pursue risk bounds for learning I since it has been thorough studied in existing
Blumer et al., 1989) and Le Cam's method Yu
literatures [Blum al. 2016 Mohri al. 201tlBartlet et al. 2005 Massart & Nédélec 2006).
Bartlett
Instead, the theorem admits any classifier that is close f in PAC fashion, providing additional flexibility choosing classifier S.
Theorem 1 (Risk Bound). Let Sn {(x,, y:) be i.i.d sample from Data Generative Pro-
cess described in Definition [ under Assumption 1 with f-) E F and g* G. [F] < co
1-122 10)] For any f(.) E F, F, let g arg min Rs, (9: Then for any > 0, there is 8 > 0 such that the following holds:
[0| Given X, let 3 E Li42x + X, man(
3+22
>
1-2X
gEG
For 2 max{ 326² log( ) 248 log( (F
}, for f that satisfies one of the following condition:
For any f(.) E F that E. Ez (xx) # 4 (x) - 83 with prob at least - 5,
If 1 for any f() EF that Eg If f fx)) 22 S 88a with prob least 1 8,
The following holds with probability at least 1 26:
R(ğ; f", .3) - Rig": 8), S
Remark 2. The assumption that [=( + (' S could be achieved via an ERM classifi-
cation loss Ei= 1{f(2,, + ys} under some margin condtions (Massart & Nédélec 2006 Bartlet
also apply some methods beyond ERM to obtain (Namkoong & Duchi 2017 Zhang et al. 2017b Huang et al. 2020). In particular, in case
al. 2005 In practice,
2. the data in
support Ly un-learnable as are purety random. While approximating f the full support
not possible in general, one can control the conditional risk (x) * f*(x)) x E Ω21] via standard ERM schema (see proof in appendix Section A.5). We stress that Theorem hholds for any classifier that is close to fr, even the case where f and ğ are trained on the same dataset.
Corollary (Recovering 9²) Given conditions in Theorem ! if we choose B = 3. we have:
(x(L(((x) # # (x))))) 4e(1 + 2A)
(6)
A
Corollary [ suggests that by minimizing the empirical version of the loss from Definitions 3 one can recover g* in PAC fashion. The theoretical guarnatee holds even under very challenging case were >> 0.5 and À = 2, .eg, majority of the data have purely random labels.
The analysis of the selector loss (Theorem relies on the quality of the classifier f. But since we know that δ is able to abstain from uninformative data, we can retrain f beyond standard ERM, with up weighted informative data, therefore improving the accuracy of f. Such circular logic naturally leads to a practical iterative algorithm that present in the next section.
Algorithm I Iterative Soft Abstain
1: Input: Data set S, = {(x11 y1 )11,-.. .... (In, }), weight parameter,3, random initial fo and go, 0 Vi [n], meta learning rate n,, number of iterations T 3: for 1- 1, do
initial sample weights 7, n
2:
4: Optimize loss to update predictor ft En_ 7 lo)( y) log f(x:))
5:
Approximate the 'pseudo-inte infulooiifooaaivee label : 2 = (() 0.5) y:}
6: Optimize loss to update selector g" Em= {
log(g((() + B( (0)=)))ogg( (001-g(x)))) g(x:)))
1+1 71 ( (0)))
7: Update sample weights using gf : : Σn 13
8: end for
9: Output: fT.gT

---

Under review as a conference paper at ICLR 2023
6 A PRACTICAL HEURISTIC ALGORITHM
Motivated by our theoretical analysis, we propose a practical algorithm sharing a similar spirit with the selector loss. From a computational standpoint, we replace the binary loss by cross-entropy loss instead and require that both f and g have continuous- valued output, ranging between 0 and 1 instead of binary output {-1,-1] The labels y also needs to be processed so that the values are in the {0. 1} range. We also relax the requirement for minimization oracles, allowing the practical algorithm to jointly optimize the predictor and the selector in an iterative manner. At each iteration, we update the predictor using the informative data selected by the selector, and then update the selector based on the predictor's output. See Algorithm I for the pseudo-code. A pictorial example of Algorithm performance can be found in Figure 3 of the Appendix.
During the joint optimization process, the predictor counting on the selector to upweigh informative data. By putting more effort the informative data, wish to improve the performance of predictor via learning beyond ERM (Zhang et al.] 2017b) Ren et al.] 2018) Huang et al.] (0200)
However, the initial selector is not trustworthy. To update the predictor J, turn to so-called soft abstention scheme: use a weight vector y that progressively down-weighs samples abstained by g. in the spirit of multiplicative weights update (MWU) algorithms (Cesa-Bianchi & Lugosi] 2006) Arora et al. 2012). Specifically, we increase the weight of i-th sample % if the selector accepts
that Σ 7/ We call this a soft abstention approach because the algorithm decreases the weight of uninformative data gradually. We count on MWU mechanism serve as a soft version of the selector, allowing the classifier to put less effort on learning uninformative data.
2e 7/4 %i 7 ({g())) > 0.5]) and then normalize
7 EXPERIMENTS
In this section, we test the efficacy of our heuristic algorithm (Algorithm datasets. The empirical study aims to answer following questions.
T on aablicly-available
Q Is Algorithm Aaporithmabble able to approximate ground truth selector g" The Answer is yes. The empirical result on Semi-synthetic dataset (Figure in Section 7.1 suggests that Algorithm| recovers ground truth selector g" within reasonable error range.
Q2: How does Algorithm compare to baselines on semi-synthetic dataset in recovering ground truth selector g²?
The results are presented in table T in Section 7.2 All baselines are simply not equipped with the functionality distinguish informative/uminformaati data automatically. They all suffers from poor estimation of a, the proportion of informative data in the dataset, which must be given as a hyper-parameter. However, our method does not require such prior information and provably recovers a ( (which is implied by recovery of g²), thus consistently behaves well.
Qs How does Algorithm work on real world datasets compared to selective learning baselines? On real world datasets, Algorithm [ consistently gains competitive performance against other baselines in low coverage regime, e.g., the proportion of data chosen by selector < 20%. These empirical results suggest that that our method is good picking out strongly informative data,
Baselines. We compare our method to two of the recently proposed selective learning algorithms. (1) SelectiveNet (Geifman & El- Yaniv 2019). which integrates extra neuron as data selector in the output layer and also introduces a loss term to control the coverage ratio; (2) DeepGambler (Liu) et al. 2019), which also maintains an extra neuron for abstention and uses doubling-rate -aateii---eeekkeeeeeee 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 Confidence. The intuition behind this heuristic baseline is that informative data should have higher confidence compared to uninformative data.
Experiment Details and Ablation Study: Due to limited space, all experiment setting details given Appendix Section B.1 Detailed ablation studies are provided in Appendix Section
7.1 EXPERIMENTS USING SEMI-SYNTIETIC DATA FOR Q1
7

---

Under review as a conference paper at ICLR 2023
Table 1: Synthetic Data Experiment on MNIST+Fashion and SVHN
Dataset
Uninformative Num.
Informative Num.
Criterion
Confidence
SLNet
DeepGambler
Ours
SR(%)
59.3240.83
45.44=0.68
45,37=1.29
00.35:00.31
60000
15000
Precision
0.46+0.79
0.61 +00.1
0.61+00.01
1.00 0.00
Recall
0,9420,07
1,00 1: 0.00
1.0000.00
0.85 0.01
SR(%)
39,23:0477
28.15=0.:3
2777
12.03=1.06
60000
30000
Precision
0.68+
0.80 +0.01
0.80++0.00
1.00 0.00
MNIST Fashion
0.9000.00
0.00
0,92
SR(
28.9220449
20.220038
19.990041
12.58.2.00
60000
45000
Precision
0.7910.29
0.88 10.86
0.8910.00
1.00 0.00
Recall
0.9910000
1,00 0.00
1.00 = 0.00
0.97 0.03
SR()))
218820039
13,38=0:32
14:20:0.62
1..6
60000
60000
Precision
0.86+0466
0.92+0.22
0,94+0000
1.00
Recall
1.00:0.00
1,00 0.00
0,00 1.00
0.01 0.97
SR(55)
04.31 = 0.89
48.61
+ 23.37
18.24 + 2.00
7.033 1L01
9200
0.80
0.01
Recall
0.98:00.0
0.89 0.10
0.96
= 0.01
0.85 0.01
SR(%)
47.64 0.89
28.15 1. 22.74
12:03 0.99
0.97
33800
18300
Precision
0.70 0.01
0.75 1: 0.18
0.88
0.02
0.9510.01
SVHN
Rocall
0,99:0000
0.96 0.100
0,98 0.01
0.88 0:01
SR(%)
36.53 1.57
12.96 1.70
8.65
4.05+-0.67
33800
26200
Precision
0.79 1 0.01
0.5% 1.0.01
0.91 0.01
0,97.10.0
Recall
0.99+0.00
0.96
0.98 0.00
0.89
SR(%)
34.48 1.15
12.10 1.21
8.31 0.84
0.86
33800
28400
Precision
0.80 0.01
0.59 0.01
0.92 0.01
0.96.10.01
Recall
0.99:0.00
0.98 1 0.00
0.98 = 0.00
0.89 = 0.01
Dataset Construction: We explicitly control the
support of informative/uninformaai data. For UIIIS--FashionMNIST dataset, images from MNIST are set to be uninformative and images from Beshion-MNIS, are set to be informative. For SVHN(Netzer et al.) 2011) dataset, class 5-9 are set to be uninformative and class 0-4 are set to be informative. Datasets are constructed with different values of informative data fraction and label noise ratio gap À according to the noisy generative process. We inject label noise accordingly to Definition by setting X(x) = A. We shuffle the labels of infor- mative/uninformmtive data according to different values data according
0.90
0.85
0.00
0.75
MMIST: 0.25
uN
SVHN 025
a 0.50
0.60
0.30
2.35
0.40
of A and mix informative/uninfrmaas to a. In particular, we choose E (25%. 50% and A E {0.3, 0.350, 0.4)
Figure 2: Recover g" using Algorithm under different label noise ratio gap
!
Results and Discussion. The average accuracy of the selector given by Algorithm compared to the ground truth selector is presented in Figure As one can observe, Algorithm recovers g within reasonable error range. In addition, the accuracy improves as X increases, which supports our bound in Equation D MNIST-FashhonMNIIST data turns out to be more challenging than SVHN in recovering g². We believe this is because informative data in ANISSTFFashonMNIIST has 10-classes, which is more challenging for learning predictor compared to SVHN with 5 classes. The quality of selector suffers from imprecise f.
7.2 EXPERIMENTS USING
DATA FOR Q2
The construction of informative/uninformaiiee data follows Section 7.1 We uniformly shuffle the labels for uninformative data and keep original labels of informative data. Informative and uninformative datasets are mixed in different proportions as proxy for noisy generative process with different a. The construction of dataset mimies the noisy generative process with À = 2- The choice of X ensures that the informative data has no label noise. Such noiseless setting allows three baselines to estimate/set a to the best of their ability, according to accuracy of estimated predictor f.
Dataset Construction:
Evaluation Metric. We use three criteria to jointly evaluate selective learning outcome. (1) Selective risk (SR). Selective risk is the empirical risk measured over data points selected by the
algorithm. This is a metric that is also adopted in (Geifman & El- Yaniy 2019: Liu et al.) 2019). (2) Precision. Precision is the proportion of true informative data point among all the data picked out by the selector. (3) Recall. Recall is the proportion of true informative samples picked out by the
8

---

Under review as a conference paper at ICLR 2023
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 for the selector. An ideal algorithm should have low SR, high precision and high recall.
Results and discussion. Table T presents the results of MNIST-FashionMNISTT and SVHN dataset with different fractions (a) of informative data. The selective learning methods, SelectiveNet and DeepGambler, perform poorly because they require prior information a to be given as input. The estimation of a turns
be very challenging in practice due the presence of noisy uninformative data. In contrast, our method provably recovers a automatically and is robust against the choice of cyyeer-arametee (B). The ablation study in Appendix Fig 7 exhibits this stability: our method consistently behaves well given different values of B. A thorough exploration of the estimation of and corresponding performance of baselines is provided also provide ablation study on the MWU mechanism in Figure 4 weight up informative data and improve algorithm's performance.
Appendix Tables T0 T1 and [2] We and Table 13 showing its ability to
7.3 EXPERIMENTS USING WORLD DATA FOR Q3
In this section, we report our empirical study on 3 publicly-available datasets: (1) breast ultrasound images (BUS) (Al-Dhabyani et al. 2020), (2) lending club dataset (LC), and (3) Oxford realized volatility (Volatility) data set (Heber al. 2009). We aim to demonstrate the potential application of
the proposed algorithm in real- application and its advantages in selecting useful information out of noisy dataset.
Evaluation Metric. Unlike synthetic experiments, in real-world data set, the ground-truth labels showing which data informative and which is uninformative is not available. Metries like preci- sion/recall are not applicable. Instead, we report the selective risk of each algorithm given different coverage level. Specifically, we pick testing data points that have top coverage% selective confidence given by each selector, and calculate the testing selective risk at different coverage level accordingly.
Result and Discussion. From Table 2 we can see our method gains competitive performance against other baselines at low coverage level. This suggests that our method is especially good picking out strongly informative data. Strongly informative data are easier to learn thus the classifier is more consistent with the ground-truth model. Such low risk regime can be captured by our selector loss, leading to low selective risk.
Table 2: Woald Experiments: Selective Risk v.s Coverage
Dataset
Coverage
Confidence
SLNet
DeepGambler
Ours
0.02
0.072:00002
0.074110000
0.267:1.033
0.046:10.00
0.05
0.088+:0.002
0.091=0.000
0.281#00013
0.073=0.003
Volatility
0.10
0.118:10.005
0.127=0.003
0.327#0.012
0.116=1.004
0.20
0.000
0.200+00004
0.374++00008
0.192+
0.02
0.04010.007
0.01410.020
0.000-10.000
0.000
0.05
0.040+10.007
0.014+0.020
0.000=00.000
0.000
BUS
0.10
0.040=0.007
0.014=0.020
0.000=10.000
0.042+0.059
0.20
0.007
0.023
0.073+10.15
0.083+10.02
0.02
0.46910.014
0.21210.022
0.136 0.153
0.05
0.286+-0.008
0.207+
0.026
0.177 +
LCC
0.10
0.239+00008
0.218 0.009 0.009
0.190
0.221 0.010
0.20
0.208
0.251
0.218
0.201700007
CONCLUSION AND FUTURE WORK
In this work, we take the first step towards principled learning in domains where a lot of data is naturally uninformative/higlly noisy and should be discarded in learning and inference stage. We propose a general noisy generative process that formally describes such setting. A novel loss is designed for the training of the selector model with theoretical guarantees. Based on this loss, we design a heuristic algorithm that jointly learns the predictor and selector. Our empirical study support merit of our methods. We believe the Noisy Generative Process be generalize to solve different problem, such as active learning (Cohn et al. 1994) and out of distribution generalization (Arjovsky et al. 2019). We look forward to these extensions in future work.

---

Under review as a conference paper at ICLR 2023
9 REPRODUCIBILITY STATEMENT
We describe a synthetic data generation procedure, evaluation metrics in Appendix section 7 For the convenience of the reader to reproduce the experiment, also summarize the experiment setting and give implementation details section B. The source code as well as parameters to reproduce the experimental results will be made available together with the publication of the paper.
10 ETHICS STATEMENT
This paper focuses theoretical discussion about learning from data that contains different portion of non-informative samples. Our experiments only use publicly available datasets. Our discussion, analysis, data shouldn't '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. our future efforts in this area, we aim to address and resolve possible negative impact.
REFERENCES
Durmus Alp Emre Acar, Aditya Gangrade, and Venkatesh Saligrama. Budget learning via bracketing. In International Conference on Artificial Intelligence and Statisties, pp. 4109-4119. PMIR, 2020.
Walid Al-Dhabyani, Mohammed Gomaa, Hussien Khaled, and Aly Fahmy. Dataset of breast ultrasound images. Data in brief. 28: 28:104863, 2020.
Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz. Invariant risk minimization. arXiv preprint arXiv:1907.02555 022993 2019.
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: meta- algorithm and applications. Theory of Computing, 8(1):121-164, 2012.
Marco Avellaneda and Jeong-Hyun Hyun Lee, Statistical arbitrage in the us equities market. Quantitative Finance, 10(7):761-77) 2010.
Pranjal Awasthi, Maria-Florin Balcan, Nika Haghtalab, and Ruth Urner. Efficient learning of linear separators under bounded noise. Conference on Learning Theory, pp. 167-190. PMLR, 2015.
Pranjal Awasthi, Maria Florina Balcan, and Philip Long. The power of localization for efficiently learning linear separators with noise. Journal of the ACM (JACM), 63(6): 2017.
Peter L Bartlett and Marten H Wegkamp. Classification with a reject option using hinge loss. JMLR, 9(8), 2008
Peter I. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. The Annals of Statistics, 33(4): 1497-137777, 2005.
Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations data science. Vorabversion eines Lehrbuchs, 5, 2016.
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-chervonenkis dimension. Journal of the ACM (JACM), 36(4):629 1989.
Olivier Bousquet, Stéphane Boucheron, and Gábor Lugosi. Introduction to statistical learning theory. In Summer school on machine learning, pp. 169-207. Springer, 2003.
Tom Bylander. Learning linear threshold functions in the presence of classification noise. In Proceedings of the seventh annual conference on Computational learning theory, pp. 340-347, 1994.
Nicolo Desa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Jiacheng Cheng. Tongliang Liu, Kotagiri Ranamohanarao, and Dacheng Tao. Learning with bounded instance and label-dependent label noise. International Conference on Machine Learning, pp. 1789-1799. PMLR, 2020.
10

---

Under review as a conference paper at ICLR 2023
Chi- Chi-Keung Chow. An optimum character recognition system using decision functions. IRE Transac- tions on Electronic Computers, (4):247-254, 1957.
CK Chow, On optimum recognition error and reject tradcoff. IEEE Transactions on information theory, 16(1):444)))))) (111):44446,)) 1970.
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine learning, 15(2):201-221, 1994.
Corinna Cortes, Giulia DeSalvo, and Mehryar Mohri. Learning with rejection. In ICALT, pp. 67-82, 2016.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 2018,
Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distrbution-iideeeeddnn pac learning of halfspaces with massart noise. Advances in Neural Information Processing Systems, 32, 2019.
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning halfspaces with massart noise under structured distributions. Conference on Learning Theory, pp. 1486-1513.
PMLR, 2020.
Richard M Dudley. Uniform central limit theorems, volume 142. Cambridge university press, 2014.
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 Yaniv et al. On the foundations of noise-free selective classification. JMLR, 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-88 02- 2002.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In ICML. pp. 1059-1059, 2016.
Aditya Gangrade, Anil Kag, Ashok Cutkosky, and Venkatesh Saligrama. Online selective classifica- tion with limited feedback. Advances in Neural Information Processing Systems, 34, 2021a.
Aditya Gangrade, Anil Kag, and Venkatesh Saligrama. Selective classification via one-sided predic- tion. In International Conference on Artificial Intelligence and Statistics, pp. 2179-2187. PMLR, 2021b.
Yonatan Geifima and Ran El- Yaniv. Selective classification for deep neural networks. In NeurIPS, 2017.
Yonatan Geifman and Ran Blniv.... Selectivenet: A deep neural network with an integrated reject option. In JCML, 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. Theoretical foundations of active learning. Carnegie Mellon University, 2009.
Steve Hanneke and Liu Yang. Minimax analysis of active learning. J. Mach. Learn. Res., 16(1): 3487-3602, 2015.
David Haussler. Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik- chervonenkis dimension. Journal of Combinatorial Theory, Series A, 69(2):217-232, 1995.
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, 20.
11

---

Under review as a conference paper at ICLR 2023
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pp. 770-778, 2016b.
Heber, Gerd, Lunde Asger, Shephard Neil, and Kevin Sheppard. Oxford-man institute's 's realized library, 2009. URL
oxford man. ox ac. uk/data
Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Lang Huang. Chao Zhang, and Hongyang Zhang. Self-adaptive training: beyond empirical risk minimization. Advances in neural information processing systems, 33:19365-19376, 2020.
Heinrich Jiang, Been Kim, Melody Y Guan, and Maya Gupta. To trust or not to trust classifier. In NeurlPS, pp. 5546-5557, 2018.
Adam Tauman Kalai, Adam Klivans, Yishay Mansour, and Rocco A Servedio. Agnostically learning halfspaces. SIAM Journal on Computing, 3766)1777-1805, 2008.
Adam Tauman Kalai, Varun Kanade, and Yishay Mansour. Reliable agnostic learning. Journal of Computer and System Sciences, 18(5):1481-149) 2012.
Michael Kearns and Ming Li. Learning in the presence of malicious errors. SIAM Journal Computing, 22(4):807-883 1993.
Michael J Kearns, Robert E Schapire, and Linda M Sellie. Toward efficient agnostic learning. Machine Learning, 17(2-3):11--441 1994.
Alex Kendall and Yarin Gal. What uncertainties do we need in bayesian deep learning for computer vision? NeurIPS, pp. 5580-5590, 2017.
Beata Beigman Klebanov and Eyal Beigman. Some empirical evidence for annotation noise in
benchmarked dataset. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 438-446, 2010.
Adam R Klivans, Philip Long, and Rocco 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.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes, volume 23, Springer Science & Business Media, 1991.
Shaojie Li and Yong Liu. High probability generalization bounds with fast rates for minimax problems. In International Conference on Learning Representations, 2021.
Ziyin Liu, Zhikang Wang, Paul Pu Liang, Russ Salakhutdinov, Chiis-Philippe Morency, and Masahito Ueda. Deep gamblers: Learning to abstain with portfolio theory. In NewrlPS, 2019.
David Madras, Toni Pitassi, and Richard Zemel. Predict responsibly: improving fairness and accuracy by learning to defer. Advances in Neural Information Processing Systems, 31, 2018.
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.
Hussein Mozannar and David Sontag. Consistent estimators for learning to defer to an expert. In International Conference Machine Learning, pp. 7076-7087. PMLR, 2020.
Hongseok Namkoong and John Duchi. setiance-based regularization with convex objectives.
Advances in neural information processing systems, 30, 2017.
12

---

Under review as a conference paper at ICLR 2023
Feng Nan and Venkatesh Saligrama. Adaptive classification for prediction under budget. arXiv preprint arXiv: 1014,4 2017.
Nagarajan Natarajan, Inderjit S Dhillon, Pradeep Ravikumar, and Ambuj Tewari. Learning with noisy labels. In NIPS, volume 26, pp. 1196-1204, 2013.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Chenri Ni, Nontawat Charoenphakdee, Junya Honda, and Masashi Sugiyama. On the calibration of multiclass classification with rejection. arXiv preprint 19111:190..16655, 2019.
Bernt Øksendal. Stochastic differential equations. In Stochastic differential equations, pp. 65-84. Springer, 2003.
Tim Pearce, Felix Leibfried, and Alexandra Brintrup. Uncertainty in neural networks: Approximately bayesian ensembling. In AISTATS, pp. 234 244,244422 2020.
Anupama Reddy, Jenny Zhang, Nicholas S Davis, Andrea B Moffitt, Cassandra L Love, Alexander Waldrop, Sirpa Leppa, Annika Pasanen, Leo Meriranta, Marja-Liss Karjalainen-LLnndseer,, et al. Genetic and functional drivers of diffuse large cell lymphoma. Cell, 171(2):481-99,,
2017. 2017.
Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In International conference on machine learning, pp. 4334 4343. PMLR, 2018.
Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1): 145-147, 1972.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
Sunil Thulasidasan, Tanmoy Bhattacharya, Jeff Bilmes, Gopinath Chennupati, and Jamal Mohd- Yusof. Combating label noise in deep learning using abstention. arXiv preprint 1rXiv:1905.1096. 2019.
Ruey S Tsay. Analysis of financial time series, volume 543. John wiley & sons, 2005.
Leslie G Valiant. A theory of the learnable. Communications of the ACM,
1984.
Tim Van Erven, Peter Grunwald, Nishant A Mehta, Mark Reid, Robert Williamson, et al. Fast rates in statistical and online learning. 2015.
Vladimir N Vapnik and Ya Chervonenkis. On the uniform convergence of 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 Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. arXiv preprint arXiv:1706.03766 2017.
Marten Wegkamp, Ming Yuan, et al. Support vector machines with reject option. Bernoulli, 17(4): 1368-1385, 2011.
Jon Wellner et al. Weak convergence and empirical processes: with applications to statistics. Springer Science & Business Media, 2013.
Yair Wiener and Ran Elniv.... Agnostic selective classification. NeurIPS, 24: 24:1665-1673. 2011.
Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang. Mingming Gong, Haifeng Liu, Gang Niu, Dacheng Tao, and Masashi Sugiyama. Part-dependent label noise: Towards instance-dependent label noise. Advances in Neural Information Processing Systems, 33:7597-7610, 2020.
Songbai Yan and Chicheng Zhang. Revisiting perceptron: Efficient and label-optimal learning of halfspaces. pp. 1056-1066, 2017.
Bin Yu. Assouad, fano, and le cam. In Festschrifi for Lucien Le Cam, pp. 423-435. Springer, 1997.
13

---

Under review as a conference paper at ICLR 2023
Xingrui Yu, Bo Han, Jiangchao Yao, Gang Niu, Ivor Tsang, and Masashi Sugiyama. How does
disagreement help generalization against label corruption? ICML, pp. 7164-7173, 2019.
Chicheng Zhang and Yinan Li. Improved algorithms for efficient active learning halfspaces with massart and tsybakov noise. arXiv preprint arXiv:2102.0531,, 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017a.
Chong Zhang, Wenbo Wang, and Xingye Qiao. On reject and refine options in multicategory classification. JASA, 113(522):730-745 2018.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint arXiv: 2017b.
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.
A
THEORETIC RESULTS DETAILS
In this appendix section, present the missing proof's well as additional empirical results.
A.1 PRELIMINARY
We describe the risk for selector loss on (æ,y) X C Fd x (+1,
R(g: f. B)
+ y) {gg()) + 1}1(f(z) =y]
(7)
The choice of |3 should ensure that given Bayes optimal classifier (*), g (-) the minimizer for the selector risk R(g: f 3). We have that given f* the risk gap between any selector g and g" is R(g: f*, 3) Rig": frr 33) could be written as:
ff = Em.,y (g](())) = 1)1[(({) *
+51(g(x) = 1]] #v)
()]14(1))))0= =
E.
(8)
+1100) =)(0)))= = =
X(x)
X())
3
+
11g(z) = 1} (x) *1
4
2
4
2
3
((x)
1
X(x)
+E
1(g(x) # (x)(g((x) = 1}}
1
2
4
2
Since X(x) is data dependent, to ensure that R(g. 3) > R(g": ;) for all g E G. suffices to Max)
pick 3(1 1 + 2 - +
Ma)
and
\(x) 8(1 X(x) 0, need B 2 sup 1+2X())
3-2X(z) and
5 inf 3+2X(a) which implies that it suffices to pick 3 E m [-2
3-24 3+21
1+2X
1-21
14

---

Under review as a conference paper at ICLR 2023
Assuming X(x) X, pick 3 within certain margin of the above interval: by picking
33-2A
1+2A
X, 1-2A 1-4X2
3+22A
we have
R(g: fo B) of 4(1 2X)
Bellig(a) # (x))))
(9)
A.2 PROOF OF INFORMATION THEORETIC LOWER BOUND
In this section we quantify the hardness of recovering g", from an information theoretic perspective.
S 1} where ed Let (x: y) X' y Rd x {+1,- -1], we set X' {T ele (et ..... ed ). |
represents the j-th cannonical basis. Let uo be vector of ones, w = 1, we set (a) 21 (w x > 0} - Let G be the hypothesis class that contains g (x)) In our lower bound construction 9 2d
and g(x)= = =1 - 1(x
e * - 2 1-aa)($+ + ||:|| S a).c2-1fa- I ||^||| - a
where Ç E (+1,-114
For example, suppose for each j = I,... d. el is the vector with the jth
entry one and the other entries zero. Then for = T e for some j {I..... d}. (x) is 1 i
positive and it is -1 if is negative. Moreover, g(x) is - if ||| 2 1 - a, it Ç² if | I a. and it is -1 otherwise.
Let a E 1+11-11 be a d-dimensional Rademacher vector and we set g'(x)) = Σラ= 1(x Te el + - 2 a1-a--aa a² + + - a 1aa S ||||| s 1 11-a)) where {+1, -11" In e If = -1, the informative part of Q is {æ|||>|] 2 1 1- a} otherwise the informative part of Q becomes {œ|||>| s a}. Assuming (xx is deterministic and let S {(x,, b) be generated from following process which we denote as Q:
another word, the support of Da - where @ {
Uniif(+l,-ly
g" gx(x) = Σ j=1
1/ Te # f01 |||=|| 2 1 a-
+ |||z||| S a) o² 1fa -<| 11-
Generate S = (<i;, 3:) according to:
(10)
j
with prob 1 c with prob 5
j (i~ Unif(2,.... d}
X
T ~ Unifl-1,1]
x = =
y = (())), (ff with prob 1 (a))
with prob 3 + 8" (=)A
Let A be any (potentially randomized) algorithm that takes dataset S,, as input where S, is generated from the process described in Equation 10 Let ğ be the hypothesis ouput of algorithm A. For parameter / we define
R(A(Sa); B) R(]()),
(1)1((((a) w}].
(1I)
Theorem 2. Consider the noisy generative process defined in Definition 7 with Q being G-realizable. For any e < X, to achieve
Es, [R(A(S)), R",", 8(1 + 2A)
with 3 E
2- 1+2X
+ X
3421 1-2X
,any algorithm will take at least log(())
many samples.
T
Xe
Proof. The lower bound construction is presented in Equation 10 Note when X 1. y becomes
purely random. Our lower bound construction in case À = works for any ʃ that is consistent with
15

---

Under review as a conference paper at ICLR 2023
f on f2 From equation p the risk gap f" RRg", ,8) averaged over and So can be written as
Es Bs, R f 3))
R ,))
A 4(1 + 2X)
R2 B.g.
Eu 1 (ī(x) + g" (z:)
A 4(1 + 2A)
E B...
Pr x E P ( + g" (z)))) (
(12)
j=2
8
Pa (a # g" E = 0}
2
B
Es.
4 + 2A)d
)=2
In the last inequality we use the fact that Pa E 22 = c/(Ad) for j 1 2.
Let / be a Rademacher vector conditional on coordinates {1, - 1, + 1, I...d Let (->)) be a vector equal except the jth entry. Above equation becomes:
Eg Es, [R f" 3)
","",,,,))))
2 6
Pa + Es,
+ (z)) E
8(1 + 2Ajd
1=2
Pa [(x) + g (2) x E 10 0/3
+ EE (-1)
(13)
d
Σ
8
P Psi. [0(x) + gx() 22
2d-T
8(1 + 2A)d
o/se|+1--11
j=2
P [-
[(x) + 9" (x) x E s2'
We make our notation more specific. Let A(S.) To and A(Sa(-1)) = To-s. Notice that (x) also depends on a. We let g be g" (xx) conditioned on a and Jー-, be g (xx conditioned on f(-1) In particular, for all æ E 12, ;) (x) # 92 could happen only when a 2 ||>||| or ||>||| 2 1 - a.
So equation becomes
Es, E, f".) RR(g,, "0,"
Σ
Σ
P S (x0 + (x) x e 2
2d-1
8(1 2A)d
ofEE(+1,
j=2
+ +Ps [oo :(x) -z- (a: 1 E s24]
Σ
as
P S [x(x)) + (x) e e
| ||l 2
2d-1
8(1 + 2X)d
0/1g(+1.11p=)
1=
| N a}}
+ +Ps. (-1) (2) * -6 (z)
x E Q a ||||||
a0
P a (x) (x) E E 2 or| 21 1
2d-I
8(1 + 2X)d
a/1c(+1,-1já-1
+ Ps.. / f) [ * -x( E 22 a |,||| 1-
(14)
16

---

Under review as a conference paper at ICLR 2023
Next make Equation 14 independent of x.
Eg Es f"
,
1
Σ
PP S (x) + (x) x S |||| |
2d-1
8(1 + 2A)d
o'iE(+1,-1)u)
j=2
|0||, | al
+ P 2 (0))(())
* 9o (z)
x 12,
Σ
aE
Es, (1) * (b(() 2. a 2 || or, | 21
2d-1
8(1 + 2Ajd
aliE(+1,-1j4
02 12,1, |||||| 2 11-aa al}
+ Es (-sp
+ -o ( (1)0-:1
Σ
Es, 2 1 + _o E E00 |0]|, ||]|| 1
1
2d-1
8(1 + 2Xjd
aliE(+1,-1)a-)
||||| 2 1 al }
+ Es (-s) {
11/0 i + got x E S2, 2
#
Σ
ae 8(1 2A)d
Pss. go + So + +Ps 100 + 966
2d-I
oE(+1,-14--1
Σ
Σ
Pso. fo [ol + P. P ( + -96o
2d-1
8(1 2
oE(+1,-1)d-)
Σ
a
{ 1 1- - Σ
d
2d-1
8(1+ + 2A)d olig(+1,-1ja=
(15)
where Q89) Q oo is the product distribution of samples for S, andS, The last step of inequality follows from the Le Cam 's method. In the Equation * we use the fact that for all x s.t., | a or | Z a, 1 (x) # - (x)) = 1 (ā + gh } is free of
Let Qo be distribution of S. and Qa(-s) be distribution of S.-3. The total variation distance can be bounded using the Hellinger distance, which is denoted H(--)). Below bound the TV distance using Hellinger distance
1( - -0
H²(Q! (m)
sH(Q!") 0 207-11)
H²(Q(()) (z) 2.2
(16)
(o
SViH(Q0.
17

---

3nae Under review as a conference paper at ICLR 2023
Now bound the Hellinger distance.
H2 (0(-5))
[ (VQo(ar)) v Qoi 5) (x. dady
a.
MEniilllsa (=f((a) (vQo(z,)) (01-1:;2011) daxdy
+
(vQa(ar,)) -Qol-1111 (2,, dady
IEEM 1/ 121l:121-a0 12122-a (=)-a)))(()) (=f((a)
œEEI 1/2 Isa 1
(17)
+
(vQo(z,))) V QQi-ii dxdy
(+1((()
+
(VQr(ar v Vo+ (0) (2. v))
dxdy
LENI | 121-1aa- (x)
X
3
1 x
1 X
}
2
V
2
V
4
V4
3
d
Thus we can bound the total variation distance as:
|10 - 207 l1rv $
(18)
d
Note inequality
18 together with inequality
13 we have and inequality 15
E F.s, [R(A(S=),,)) 3) R(g", 3)) E. s, [R(]. ft, B) RRgg .f"
f .11
(19)
1 1 00
1 3aae
d 8(1 + 22)
d
Above implies
sup
Es, [R(A(So), fr, B) - Ríg", f0, 2 (REs,
d-1 R(g", ,) d 8(1+2A)
3nas
Since | = 2d, any algorithm A will needs number
of samples at least n = Ω
log 19)1 Asa
so that there is a hope to achieve
ar
sup Es, (R(A(S)). B)]
S
32(1 + 2A)
Replacing as with a finishes the proof.
Remark 3. From the second inequality in Equation 12 it can be observed that the construction of information theoretic lower bound for risk function Rig, B) can also be applied to construction an ((log((91((ee)) sample complexity lower bound for E.n (g))) + g" (x:). Thus our Corollary I also achieves minimax-optimal rate for recovering g" for family of Noise Generative Process.
A.3 PROOF OF SAMPLE COMPLEXITY UPPER BOUND
Here we prove Theorem in which we bound the risk gap f( - f" Recall that the empirical version of the selector loss
Rs. 1 n A=1
(1(g(z.) = 1}]1f(2;;) # m1 (g((x) = 1}1(f(x;) = =vil }
18

---

Under review as a conference paper at ICLR 2023
Our high level approach is follows. We first analyze the gap between Rs, [ and Rs, [ f () and provide an upper bound for it. Then we use this upper bound to get an up- per bound for the gap between R(g: f" (3 and : f using concentration properties and Bernstein inequality.
CASE I: f()) E F and (T) + (x) S 83 with probability at least 1 - 8. To upper bound (.,))
Rs, G (", Rs, f B), we use Rs, (0: 3.3) and Rss ( () as a middle step. Since the empirical risk minimizer, we have
Rs. (.. S Rs, (...)
(20)
Next we leverage on the fact that is consistent with f to establish an inequality in following fashion:
Rs, (ū: 3) S Rs, ; ;) + const-
Note we have that
Rss (0: 1,)
f(x.) # ((x)) (ata)/a
vil
}
n
n 1
vi
(21)
Recall that
Rs, (3) Σ
- + - = -
1=1
So
Rs. (ā: f.9)
Rs, (3: f* ,3)
1 f(ai) ((x))) {
= 1311f( -
# 1((a)) = (=1(f((x;) = =mib
==1
((v.)) * M(x))) H (1(((a))) = 1311f((;)) +1 1]11f(2.)) 10) = vil
i=1
Rs, (o: (3 3-1 n
Σ 1 (ass) # Max)}
n
(22)
Recall that in the theorem assumptions we have Eg (()) + f*(x)) S 83 with probability at least
1-5. By Lemma 2 if >
24 log(151/6) have with probability least 8, n En= 1ff(x.) #
(xx)) S T3. so we have
Rs. (o: Rs. (0)
With similar approach we get that
Rs, (9 f.8) < Rs, (9": f) +
Thus using 20 we have following inequality holds with probability at least 8
Rss, (ā; f", < Rs. : ( +
(23)
To get bound for R( ff 3)). first define f(g: f. v) _1(g(x) =
f))( # y} + Hg([)) = [}){f(x)) = y}. Note that at this point we think B as fixed and have not included it in the arguments of E(-) for simplicity.
19

---

Under review as a conference paper at ICLR 2023
Observe that Rs,, (9 2. Σi= Egg: f", a. y) and R(g. f)) Ex,y [((: f xx, v)l for any g. First we have the following simple inequality directly taken from (23)
R(g. R(g" .9)
= y xx,) Ex y (ggg if" x.
(24)
R f 3) Ns.-Rs.,2 (0: fr 3) (g: ff" x. y) p( f" x.,y)) + E/2
By defining Ag .9. x, v) E(g"; f x. x) E(g: f x. x) for any 9, we can express the above inequality as follows:
Ba ( f x. v) E0 : f x. y)
(25)
Allg" I 2i v) - En Al(g" D. v) + e/2
To bound 1 Ei=
with high probability over all Sn, we need to find a bound on 1 Σx= Al(g". 99, 0z, 01, - Em.y Al(g" g, x. y) that is true for all simultaneously with high probability. We have:
Allg", 3. x..
Psa
3g E Allg" , 0i vi) - En.y gi v)]
2V Var (a(", , x, log (0//))
> 3
log(191/8) +
(26)
1
$ Σ PsS.
Al(g" gg. vi) Exz,y Delg" 9: x. 8)
SEG
2V avar(A(g ,ag,g gg. v)) log (|)/0)
> log(191/0) +
Now to bound 1 we need to bound V ar æ.y Al(g" I.
E Ag(g" g. xr, y) E, Al(gg; g, æ.y) we use Bernstein inequality. For that x. v)]. We first expand Al(g", ,9, x. v).
Al(g" "ll""99,2.0 9,)
-", - f(g;
=
So we have
A lgg x.
= -1 *v)
=1 = -101)))))-----
+ =0)
1(g(z) 1)
13 -100()) 1) 1f(
y
()) (8)((())) + +1)+ - v) -]060) 1 + = =1} < 32 16g (x) + g(t)}
(27) Ae(l" g. x) < A & ( +
Hence we conclude that Var 2.y
[(x)). On the other hand, Equation implies that R(g: f", R(g": Z T (+)
g(0}). Thus we can use the following inequality to achieve fast rate of convergence using the
Bernstein Inequality:
B² +2)
Var (Alg"" g: x. v) <
(R(g:f", (8)) - :f"";f",8)
(28)
A
20

---

Under review as a conference paper at ICLR 2023
We use following version of the Bernstein Inequality, with X1, ...., Xn i..d random variable uniformly bounded by
b log(1/6) + 2V ar log(1/0)
P
Σ X, E
2 21 -
Using union bounds, the Bernstein Inequality implies that with probability for all E G simultane- ously:
Ps..
Alig": J. 34 ms) E E. (D(l( g: ac أ)]
(29)
2Vrr(A(g 9: m v)) log (191/8)
log (191/0) +
2 -1-
Thus by applying inequality 29 with 5 we have:
Ps.
.000 - Ea 9: x. vil
B < log (1G)/0) +
2 AVa((A(g 0: x. v)) log ( /6)
21 -1-6
By inequality 23 we have m Al(g"
gg..,,y:) Al(g',
Rs, f fr
Rs, (g:f% -E/2
holds with probability 1 - 8. Note R(0: (")) R(g": = En. De ,9, v)}. So we have
Ps..
(R(O: 1")8) - "('""""",0))
3 <= log (191/0) + 203211 + 22) (R fr, f)) R(g"; f,, log (0]//)
8/2
71
An
21 28
16,9 log(
The choice of n 2 R(g"; (3) S.
ensures that with probability at least 1 - 26, R 1*,
Ae
CASE II: A = 1, f(-) F that satisfies E. (f(x) # fx) [ seas with probability at least 5. When 1. achieving (=( # (x)) S Eof in general impossible. One can
only approximate (-) on the informative support Ω. since y is generated by coin flipping when E Sy. For simplicity of analysis, we introduce 'pscudo' version of f-(() denoted as f Let F be following hypothesis class:
{ (f(l)) (2(2), a e Ωr
[f((z), (Jie)) a E ae
if fEFFEEF
and we let (*)) be:
(x) [(x)) fly (a)),, a E e
Clearly, 8 E F. Note such hypothesis class is only introduced in analysis and is potentially
impractical. The cardinality of hypothesis class [ < |.|2. The construction of f is to make
21

---

Under review as a conference paper at ICLR 2023
R(g(z).f'38) - fx), () 2 0 for all g E g. To see this:
[( (z)
= -Ea, | = (4 +
- (
(30)
- (
(B 1
( [1((())))) = ()) 11
+ B [[g()) + (x) = 1}
20
Meanwhile (-) also satisfies the property that E Exf + f(x)] S 83 with probability at
2 if n 2 240" log( 4
least - 8. Thus by Lemma
we have with probability at least 1 - 6,
E. + S 8/
The rest of the proof is the same as the proof in CASE by replacing f with f leveraging on the fact that
f*, 3) =
Remark 4. Let us point out that our proposed selective strategy is different from the consistent selective strategy
Yaniv et al.] (2100) Instead of rejecting by looking for consistent outpur from all hypothesis in the version space, our approach deals with one single reasonably accurate hypothesis (the empirical minimizer). We leverage empirical mistakes made by the predictor in order to learn a selector, uiming to reject (only) the mistakes in a data driven manner. This avoids dealing with the issues found in Theorem 14 in (El-Yaniv et al. 2010 where the selector fails to select any data points.
Remark 5. In (Cortes al. 2016). a second hypothesis for the selector is introduced and analyzed, and at the same time, multiple commonly used loss functions are scrutinized and generalization results are provided. The major difference between this work and (Cortes el al. 2016 Geifman
& FI- Yaniv (019) is the motivation pertaining to selective learning. While in (Cortes et al. 2016 Geifman & El- Yaniv 2019) the selective loss is designed from a coverage ratio perspective, i.e. one wants to trade coverage ratio for higher precision (selective loss), our approach is designed to distinguish data that is naturally unlearnable and unpredictable. This difference leads to an alternative theoretical result. While the analysis in (Cortes et al.) (0166) focuses selective risk, our theoretical analysis focuses on the quality of the selector in distinguishing infommative/niiformaaty data, without adjusting rejection cost given by human.
A.4 MISSING PROOF FOR COROLLARY 6
It can be easily verified that A = 3 is in the interval 3 E the choice of B, from (9) we have
33-2A l1+2X
+ X, min 3+22
1-422, 10)] By
1-22
X
R(g. f) f" 4(1 + 2X)
[x(1(0(x) + g" (x)),
together with the conclusion in Theorem I Itat
R(ā: f,, - R(g"; 10,
we can conclude that Equation o holds.
A.5 MISSING PROOF FOR CONTROLLING CONDITIONAL RISK E, lf(x) + f((x)( e 2y]
Lemma 1 (Sauer-Shelat Lemma(See (lum al. 2016 Mohri al. 2018 due(G) be the VC-dimension of hypothesis class G, for all n N,
Sauer 1972))) Let
duc
en doo(9) doo(g)
(n <
12
<
1=0
22

---

Under review as a conference paper at ICLR 2023
Definition 4 (Growth Function Vapnik & Chervonenkis 2015)). Let G be the hypothesis class of The growth function is defined to be the maximum number of ways in which points can be classified by the function class:
function f and Fa........ = (ff(x)).... ff.) f(xx)
(r) = supa. tt...... [Fa Far.........
tt
Theorem 3. For every > O, there is a 8 > O such that under Assumption 4 given a set of samples S, {(x). v1), (I yn)} drawn i..dd from the Noisy Generative Process and
f = arg min IEF
{(f(z),) + ysh.
if n is chosen such that
32 (Fc log(;) + log(1)
2
2a2
then with probability least 1 -
28:
1
Ex,v (x) + yl
7 (x) + 2ea
Furthermore,
(x)f + f(w))x Qnd 2
Proof. We first bound the probability of the event that E,, Eg. (f(x)) + y) S }1 aa) + 26a
By Lemma 3 and Hoeffiding inequality have:
Ps, [sup feF n
1ff(x)) + y.) Eu, [1f(()) + vBll S (2n)en)e 32
(31)
32(4 (og(15> (( log( we have with probability of at least - ō:
By setting / = and 2
a²c"
(f(a.) + wi) Em. (f(x)) + v)l
n
The term By(2n) could be bounded by Sauer's lemma. Next we apply the fact that f
arg argmin 1 Em= 1(f(),) 4.). We have:
En (1))) # u}1l s at 1 Σ (f(a,) A
S ac + + I
1 (( 34}
2
2
n
Since E (x;) * y/
S 1 (1 a) + ca with failure probability at most 8 (Lemma we
have with probability at least 26:
Exy [1f((((())))))))))))))))){{))) + wll - 1 {1 -a) + 2ea.
Next we prove the claim that:
PAND, [f" (x) + f(x)] 2c.
Since [x.y(1(f(<)) + v}1 < [1 a) + 2ca::
Ex,y [1 11f(z) + vHl
-mmm,)>> D. [1 (1 # wHl
= Bla [1 [z) + y) æ E Awl P( (o Pvi
1
1-a
+ E (( [f(x) + y) x x E (2ww) x L 22)
(32)
1 (1 a) +ap (fP.....((()) f" 21
1
5 (1 1 -a) 2ea
P
p. [1(f(x) & (x))) E 0n s 2e
23

---

Under review as a conference paper at ICLR 2023
A.6 EXTENTION TO VC-CLASS
In order to leverage the margin condition of distribution of to obtain minimax-optimal general- ization rate, we leverage on the Local Rademacher Average tool. Our analysis tool largely follows from (Bousquet al. 2003; Bartlett al. 2005). Throughout this section, S and represent as shorthand for the I and 2 that ignores universal constants.
Definition 5 (Lv-Covering Number). (Wellner al.) 2013) Let Fi be set points. sei of ç Ik" an 8-cover w.r. Lz-norm of F on Vim, if E J, Bu E U, s.I. V E/ [(;)| s e. where [u]; is the i-th coordinate of u. We define the covering number N2(e, F,
N2(e, F, (imm) == min U is an E-cover of F on T
Let (2 F, F,n) be the maximum cardinality N2, F, mmm) over all Fım. Formally Fe, defined as:
N2, Fin FinEX EX
sup [i] U is an e-cover of F on Fim3
Definition 6 (Local Rademacher Average (Bartlett al. 2005 Bousquet et al. 2003)). Let din be Rademacher sequence of length n, the Empirical Local Rademacher Complexity at distributional and empirical radius
0 for the class F are defined
Rn <r) Eoiml
sup feF feF.Balaa)s5 n i=1
oxf();;]
Rr P ST) Boonn
sup
a. (a:))
FEF E f(
and their distributional Average as: R(F,PF < = Es, Es, [R, PF,2 r)].
Pf2 < r)) and R Paf
Definition 7 (Star Hull). (artlettt et al. FF is defined as
2005
Bousquet al. 2003) The star hull set of functions
+J == taf: aF [0, 1}}
Definition (Sub-Rowd Root Function). 2003) A function vp R + IR is sub-root if
Bartlett et al. 2005 Massart & Nédélec 2006
Bousquet et al.
vb is non- nec-eecrg
+b is non-negative
((r)/ fr is non-increasing
And we say T" is fixed point of u if (br") -
Theorem 4. [Risk Bound VC-Class Let Sn = ((0,, y/ ) be i.id sample from Data Generative
Process described in Definition| 7 under Assumption 1 with f-) E F and g" 9 with VC-
dimension dvc (J) do dve(g) < xc. Given X, let E 22-22 + min) 3423
1-2X , 10)].
For any f(-) F. let g arg min Rs., (g: Then for any > there is a 5 > such that the geg
following holds: For Ti Z max
B ("dvo(G) log( + 8 log(?) (dvc(F) log( dve(F) + log()))
de
and for J that satisfies one of the following condition:
For any F(.) E F that satisfies W. [ (x)) & with probability at least
24

---

Under review as a conference paper at ICLR 2023
1f 1
2 for any f(.) F that satisfies Bxlf(x) f*)))x 21) z Na with probability at least 1 8,
The following holds with probability at least 1 - -3:: R f" 33
Proof. The major difference from the proof for Theorem is the fact that 9 and F are not finite hypothesis class. To achieve fast generalization rate, we leverage the Local Rademacher Complexity Tool from (Bartlett et al. 2005).
CASE :f(-) F and
/ with probability at least - 6.
We proof similar to the one in Theorem 1 invoke Lemma 8 instead of Lemma probability least 1 that
up Equation 21 Since F is VC-class, will ((dye(F) log ( Hlg(()))) it can be achieved with
Since
Rs, (: 2 Rs, ( f) c/4
and
Rs. (g:: f.p) S Rss (g' ff" ,) +
Thus following hold with probability at least 6:
Rs. (3: f* B) < Rs (g f () + 8
(33)
Next we turn to bound the risk gap using R(:: f) :f B) using concentration property of inequality 33 Similar to the proof in Theorem
1 we define e(g; f, x. v) 31 - + y} 1 [gg + 1 = y}. Based on f, we define following hypothesis class:
Aolog {
A 2.8) = l(g: x0, - (z. 9EG
(34)
To invoke Lemma 6 we need establish some hypothesis class H. that satisfies condition Var(M] < BE] Next we show A a f o 9 satisfies the condition that Vas Var(h] < BE(h and thus we can apply Lemma 6 with H. AotaG, G. To begin with, one can apply Equation 27 show that,
(xr) + g(x)) < 23l g ar 9)
B (g (x) + g()))
Above implies that Var Al 9. 3) < Ex, A3 9. x) - 8 [1 (1 (x) # g(x})
On the other hand, Equation implics that
R(g: f 3)
2
Eg [11 # g(x)))
+ 2A
Thus have following holds:
(9(122)
Varn.y Ae(gig" ,x,y)] <
Em.,y (Algggg x.,))
(35)
Thus apply Lemma with H = Aolo G. Thh) E[h?] and B (2+2)
Now we find subroot function (r) that
((r)) B + 2A)
ER, ER. H H: E}})
To find ((r). we show
some
analysis
on the Local Rademacher Average
ER, (Al(g:g)) H E& v r).
25

---

Under review as a conference paper at ICLR 2023
ER. ol =R,,
sup geg,Ba. ( E(ggg 1r
o,"((gg))))
Rs Rg
sup (E Er n o, o,
(36)
1(000" ) (((gso')))
sup g 1s 7
o,1g(a;) + g" (xx)))
Talagrand Contraction Inequality
Ledoux Talagrand 1991
In the last inequality, we use the fact that
( A((g2:g")) s (((g)) - {(g2) S $)1 = # g²) 1(g2 g²)).
Define 1 g [{g(z) * (z), e 9). The indicator function [(g(x) * g" (x)) is Boolean function taking as imput, thus dvc(1 o g) s dyc(g). Thus we have
B + 22)
ER, [
H E|h?) sr
(37)
(1 + 2A)
ER, [1g + (" E g ( sr}
Above implies that can pick (r) to be
(b(r) 83 2A)
+11 log
ER [=10: +
(38)
A
n
By Equation
we have:
a n
1500A
log(1/0)(118 + 52)
E A 9" x. v) s
Al :.,33)) +
+
(39)
8²
n
Al g a. v.) Rs. (T: f", B) Rs. ; 3) < e/2 holds with probability 1 - 6. By Lemma we have r* S 80 we have that 2 (9vcc(()) log( () (106(1/0)) suffices to achieve Ex,, ( g" x, w)1 Se.
By inequality 33 we have + S.
(9) Plugging in Equation 49 27
As
CASE II:
A= 2' f(-) E F that satisfies Ex(f(x) + (x E 21 sa with probability at
least 1 5.
The proof similar the one in Theorem I except for that we need to bound the VC-dimension of pseudo hypothesis class F. Since I can be viewed as Boolean function given [I [2(x) as input, with two hypothesis fI, f2 E F, by Lemma 3.2.3 in (Blumer et al., 1989) we know dyc(F) (F)
The rest of the proof follows from the one in Theorem
Next we present our extension of information theoretic lower bound to VC-class. The lower bounds suggest that the risk bound in Theorem is tight up to some logarithmic factor.
Theorem 5. There exists noisy generative process defined in Definition with Ω being G-realizable, for any ε < to achieve
Es, ((((())) f*, R( 8(1 + 2A)
with
33-2A 1+2X
+A,
3+2A 1-2X
-
any algorithm A will take at least log(dy (g))xe many samples.
dyc
Proof. The proof follows from the proof of Theorem T for the fact that we need to have an upper bound on the VC-dimension of our hypothesis construction G. Since & consists of composition of interval hypothesis and each individual interval has VC-dimension at most 3. By Lemma 3.2.3 in dvc(g) (Blumer et al. 1989) we know dgc(g) < 6d log(d) which implies (o)(dve()))A lower bound. [
26

---

Under review as a conference paper at ICLR 2023
A.7 TECHNICAL LEMMAS
Lemma 2. Let Sn - {1 }i)} be i..dd sample from Data Generative Process described in Defini-
3log 12
tion For every > O, there exist a ô > 0 such that if 2
sollowing inequality holds
simullaneously for all f with [F] < oo with probability at least 1
1lf(x)) + fx))) Bxllf(a) fx)) +E
(40)
Proof. By taking union bound one can ensure that
Psn
sup fEr
((((s)) + (m:) - ((a)) (x))) ( (
+ne
1=1
SPs
- # ( n f(x) + ne
FEF
S
1 (f(m)) + - -1 # ('(x)) 2 n ([(()) # (xx) + ne
FEF
(41)
We next apply following version of Chernoff inequality with a 2 1: Let X; E {0, 1). Then
E.= X; where
a² EX) I exp EXX
P[X 2 (1 + x)Xx S exp
(-xEX
a
2+a
3
(- a
F[X < (1 - axE S exp
EX)= < exp (-3 " EX)
2
3
So we have
P| - EX > xEX] < exp 1-p(-3 EX)
For any fixed f FF B/ (f(()) # f (z)) by Chernoff Inequality we have
PsS.
Σ
( (2:)) nL 1 [f(x)) + [*))]] 2 nÊ (((xx) + [())] + ne
1=1
< <exp TelE
(ff())) ff (a) exp (-3 3
nE
(42)
Using 41 and setting 8 F (csppnne/)) finishes the proof.
Lemma 3. Suppose Sn {(11, ...,... (In: yn)} are i.id sampled, I(f,0,v) E [0, bj and
Ls. (f) A Ei Lffæi; W.). Given parameter t such that
nt² 262
then have:
P Ps.wD(so [sup Ls., (f) 2 $ 4By m2
FEF
Proof: For sample sets Sn and Sy if we have [Ls, (f) I(f) 2 t and [Lss (f) L(f) S 5 'thn
we get that Lss. - Ls; 2 $. Thus we have
1 ssup Ls. (f) L(f)) 2 t) 1 1(sup L2; (f) L(f) = ;
/EF
feF
(43)
$ 1ssup (f) Ls; (f) > "
feF
27

---

Under review as a conference paper at ICLR 2023
Taking expectation w.r.t Sn ~ D and S/ D we have
Ls; (f) - L(f) - "
PS sup /EF
Ls. (f) - L(f) 2 2 Ps ND
sup SEF
(44)
S P ~D sup Ls. (f) Ls₁ (f) _
IEF
Next we lower bound
P[ sup Ls, (f) L(f)l 2 1.
Since L(f v)
[0, b] and so
fEF
(ar(L((,,,,)) u)) < 62/4, using nl? 2 21² we have that:
Ls. (f) - L(D1 4VarLLs.)
Ps.
sup FEF
ni?2
So we have Ps; sup SEF
Ls; (f) - L(f) $ 5/ N
Combining this incquality with (44) we have
P
D Isup
Ls, (f) L(f) 2
fer
Ls, (f) Ls; (f) _
<2P S S/ /sup FEF
Ls, (ʃ) - Ls, (n) 2 t z
sup -2Ps
f(x))Fb22
<2P Spn
P S2n S% M(a))FF2n
sup
[Ls (f) Lss (f) " |152n]
<2P Szn
PS 82n - 8% Is, (f) - Lsy (f) t " |120l]]
(45)
2
1(x))FFB2
2112 le"
<2P Szn [2]Fsen] San
46
[52n]]
ne² le 462
<2P Son.
(supl San
[2n]]
<2 sup [Fsm [IP San
[e-
1]
San
m13 40
<2Br(2n)e
Lemma 4 (Hoeffding's Inequality). Let Zi,... Zn be independent bounded random variables with Z; [a, for all where -0 a ac. Then for all t 0:
1 n P - Σ Z. B|Z.j1 1) n i=1
2n12
2e
(46)
Lemma 5. Consider set of samples = {(x1, y1),, (In, }n)} drawn i.idd. from the Noisy Generative Process and S in the hypothesis class F satisfying (xx E [-1,+1}, If:
(
n> 2
Then we have with probability at least 1 - -6
10 (x.) + vi) < 711 - a) +
(47)
Proof:
Since 1 1(.((z) # ") is bounded the interval [0, 1] and given f E F, 1(f(x,, + fyJiiE [n] form of independent random variables. By setting b
1, f. = in Equation 46 the choice of
28

---

Under review as a conference paper at ICLR 2023
ensures that
-2n (b-u)a
I 6log(o). Thus
PS.DD. 11
Σ 1=1
1f (x:) + - (x.) # wlll 2 cal Só.
where we have
E (a,y)~DD [ (z) + n}}
(m..))-D.. [1 (x) + y - ly.1P/z E St
]f(wEOu] Since is labeled by coin flipping in Re
+ (D..w)D. (f + y E 22 |P| x: 9t)
(48)
Since labeled by S" with Bayes Risk in f2
1
21 a))
This way we have:
1 Σ (m)) #w) -0 -a)) 2 Ea) 5.
P ~ D.
which implies that Equation 47 holds with probability least -
Lemma (Theorem 3.3 in (Bartlett et 2005 Let F be class of functions with range in [a, bj
and assume that there are some functionl T H + R+ and some constant B such that for every
H. Var(h) S Thh) S BP[h). Let vp be a subroot function and be the fixed point of ab. Assume the db satisfies, for any r 2 r",
((r) 2 BER (h E H T(h))))= S Sr}
Then with c1 = 704 and = 26, for any K > 1 and every t > with probability at least - e
K
P. KK r" + f(11(b a) + c2BK)
Vh E H, P[h] < K
(49)
B
Also with probability at least 1 - -t
K 1
9 r*
t(11(b a) B2)
Vh E H. Pa[h] <
Ph +
(50)
K
B
where Pf (x.((((r)) and P Eim
Lemma 7. Given hypothesis class F : X + i-b, b) with some universal constant b and its VC-
dimension dFc(F) < oc. following sub-root function with B 2 1:
(r) = FA 11b logn
Let r" be fixed point of vp(r) so that ('r"), suppose n 2 dvc(F), we have
B² B² log( (og((arr))))
n
Proof. The proof largely follows from the proof in Corollary 3.7 in (Bartlett et al. 2005). We
include here for completeness. Since f uniformly bounded by for any r 2 v(r), Corollart 2.2 in
(Bartlett et al. 2005) implies that with probability at least 1 1. E +F Pf <r) C ( E +F
P. < 2r
Let & be event that {f E +F Pf² <r) C (f +F P.f < 2r holds, above
implies
ER <r}
<P *F. Pp FE Pf < <THEa>
(51)
b
<E (*F Paf 2r
n
29

---

Under review as a conference paper at ICLR 2023
Since r* (r("), r- satisfies
b 11b log n
r' S ( S 2r
(52)
n2
Next we leverage Dudley's s chaining bound (Dudley 2014) to upper bound ER ( < 2r") using integral of covering number. We first bound the covering number of hull of F. It follows from (Bartlett et al. 2003) Corollary 3.7 that
log N22 ( 2
(
log Nog,N(e, Bim))
F,
And covering number log N2, F, n) can be bounded using VC-dimension of F using Haussler's bound on the covering number (Haussler 1995; Wellner et al.) 2013):
I cidyc log (
log. 2 F.n
where ej some universal constant. Now we are ready to apply the chaining bound, it follows from Theorem B.7 (Bartlett et al.
2005) that
18 R
(+F,
Prf
S 2r")]
/2
C2
N2(,, #F, Lim)de
J0
C2
E log.N2
(1)++1)))
<
nn
2
(53)
J0
(wo(F)r"log411) log(1/r*)
Sc3
n
(Fy(F) + loggn//o (og(n/edvo(F)) B² (F 2
ScaV
n Where 2g and es universal constants. Together with Equation 52 one solve for r*
n²
Lemma 8.
Let Sn ((24,,1)) be i.i.d sample from Data Generative Process described in Def-
inition I For every there exist 8 >> such that if 2 Avc(F)loo(] () following inequality holds simultaneously for all f F with dvc(F) < cc, with probability at least 1
1(f(x:) + f S B. 1.f((()) (x)) +e
(54)
Proof. The proof invokes Lemma in particular, the Equation 50 Let 1 oFF: [1/(x) * (*),, F} be the hypothesis class H. in Lemma 6 Since f is deterministic boolean function, does not increase the number of points that can be shattered by F. We have dvc(1 o F) & dvc(F). In particular, we choose the functional T(.) = B[.) and it is easy verify that
Var(1if(=) + (x))) < [=(1(f(x) # (=))) = E. [1 + (x)
Let (rr = 100ER, ( (=F < lo We have
ER, [ff < < ER., [+F 2 r) < 100ER ( E2 Sr) + 11 log = (b(r
Since local Rademacher averages of the star-hull is sub-root function, know for all 2 r", (b(r) 2 (rrr)=(=)))) r* By Equation 50 in Lemma 6 we have
Σ H(f()) ff < 2E (ff((()) # f(()) + 15r" log(1/6) + 5200
(55)
n
Next we bound
A direct application Lemma 7 show that dvc(1 F) log( ave dvc(F) log( dve(F))
n The rest of the proof follows from plugging r in Equation 50 and removing absolute constants. n
n
30

---

Under review as a conference paper at ICLR 2023
A.8 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 3: Illustration of Algorithm| 1 when À 1.- a) shows mix of informative/uniiforratiy data. b) and с) show classifiers trained on weighted samples with different number of iterations. By up-weighing the informative datapoints, the algorithm progressively improves the classifier. d) shows the sum of weights of informative over total selected, i.c Lis,co Tc (See y in Algorithm the algorithm converges an all all-informative dataset.
Weight Strudtred
0.7
structured frac-0.50
structured frac-0.43
0.3
structured frac=0.33
structured frap-0.20
10
30
#pach
Figure 4: We show case the effecacy of the MWU mechanism on MNIST dataset. We plot the weight of informative data function of training epoch and the ratio of informative data. The y axis the percentage of weight put on the iformative data, i.c Dinea %
in the notation of Algorithm Σn
B MORE EXPERIMENT RESULTS AND DETAILS
B.1 EXPERIMENT SETTING AND IMPLEMENTATION DETAILS
Extension to multi-class. Our method extends to the multi-class setting naturally. In the case of K-class classification, selector loss remains the same while the predictor becomes f(x) f()) + K where A the K- K-simplex. Meanwhile, we use multi-class cross entropy loss to train the classifter. The pseudo-informatto label becomes 2, 1 {arg max
f(x;){ v.).
Semi-Synthetic Experiment Setting. For experiments in Section 7. and 7.2 We use same backbone TinyCNN models for all baselines. is light- CNN with 2 convolutional layers and fully connected layers. We adopt same training scheme for all bascline algorithm. We use Adam optimizer with learning rate le-3 and weight weight decay rate 1c-4. We train 220 epochs using batch size 196 for all baselines and the leanring rate is reduced by 50% at 45th epoch and 90th epoch.
For experiments Section 7.2 we use the default hyper- parameters for every method as recommended in the respective original paper (i.e., internal selective learning-specifie defaults, reported in (Geifman & EI- Yaniy 22199) Liu et al. 2019), and / = 2 and MWU step-size r = 2 for our algorithm It simulates practical scenario where hypae-par optimization is impossible, since the
31

---

Under review as a conference paper at ICLR 2023
ground truth regarding which datapoints are actually informative is never revealed. For SelectiveNet, the default
are the weight for coverage rate penalty Xa1 = 32 and the weight for selective net loss 0.5. For DeepGambler, the sole hyper-parameter "reward" should lie between I and 10, and we choose the default value recommended by the author which is 2.2.
For the SVHN experiment, we use 8 (He et al., 2016b) the backbone model for every candidate. We set the batch size to 128, and use Adam as the optimizer with learning rate 1e-3 and weight decay le-4, We train each algorithm for 162 epochs, and shrink our learning rate both epoch 45 and 90 by half each time.
We assume that the ratio of informative data, a, is unknown all methods. This is necessary in practice; the ratio and strength of noise are not known in most real world scenarios. For SelectiveNet and DeepGambler, such ratio is a required input. To run these baselines, we first run the original backbone for 60 epochs, and then estimate a using backbone's 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 num classos then the frequency estimation of is â num of classesetrain acc- which num classes-
the estimation of a we give to baselines. Note such estimation can only be applied when À = 2-
Real-World Experiment Setting. We use same backbone model for all baseline methods. Specifi- cally, we use 1-layer LSTM for volatility data. We use (GGI6/Simonyan & Zisserman (2014) for BUS data. We use 3-layer multi-layer perceptron for LC data. We adopt same training scheme for all baseline algorithm. We use Adam optimizer with learning rate le-4 and weight decay rate le-4 for all experiments. The learning rate is reduced by 50% every 10 epochs. We use batchsize 128 for volatility data, batch size 32 for BUS data and batch size 256 for LC data, which is determined according to the searching
size of the data. We further split the training set and perform 30 random for each baseline. For BUS and LC, we set the training epoch to be 50. For financial time-series volatility data, since each baseline is quite sensitive to the running epoch, we add the training epoch as hyper-parameter searching dimension during the HPO process.
B.2 REAL- WORLD DATASET DESCRIPTION
The first dataset is the Oxford realized volatility (Volatility) (Heber et al. 2009) data set containing 5-min realized volatility of 31 stock indices from 2000 to 2022 which contains 155107 records in total. We use past volatility and returns as features, and the task here to predict whether the next day volatility will be higher than current one, making it binary classification. We choose data from 2000 to 2020 as our training set and the rest for the testing (2020 Jan. to 2021 Oct.). This data set is used as an example to show our algorithm's 's possible application in selectively forecasting financial time series.
The second one is the dataset of breast ultrasound images (BUS) (Al-Dhabyani et al., 2020). BUS contains 780 gray-seale breast ultrasound images among women in ages between 25 and 75 years old. These images have average size 500 x 500 pixels and can be categorized into 3 classes (487 benign, 210 malign and 133 healthy). We randomly choose 80% of data as training dataset and the rest 20% for testing. We are going to use this dataset an example to show possible application of our algorithm in automatic diagnosis. The machine can generate diagnosis result only on selected cases and deliver unsure cases human expert for further investigation.
The third one is the lending club dataset (LC). Lending club is a peer-to-peer ppeor lending company that matches borrowers with investors through online platform. The lending club dataset (LC) contains loan data of its customers from 2007 to 2018. We compare different version of existing dataset of LC and remove all inconsistent and incomplete records. There are different status of loans record in this dataset, we keep 3 types of these record that consist the major part of the dataset (261442 charged off cases, 1035418 fully paid cases and 25757 late cases). We use 20% of the dataset as the testing set. This example shows our algorithm can be use to grant loan given on different risk preference.
Table 3 presents the original accuracy given by neural network on each of these 3 real-world data set. For all dataset, the neural network without using selection mechanism cannot give reliable inference. In mortgage granting. high risk like this can cause significant loss. In medical diagnosis which is healthy issue critical, a diagnosis with miss-diagnose rate as high as 15% is not acceptable. However, we apply our selective algorithm, we can see that the risk on all dataset sharply reduced. In BUS
32

---

Under review as a conference paper at ICLR 2023
dataset, can even almost perfectly guarantee the diagnosis result empirically for our most confident cases. These evidence are of practical interest.
Table 3: DNN Original Risk on Each Dataset
Volatility
BUS
LC
Risk
0.340+0.002
0.152+00008
0.392-+0.001
C ABLATION STUDY
C.I ABLATION STUDY: EFFECT OF INFORMATIVE RATIO a..
We provide several ablation studies that further elucidate the reasons of our advantages. We stick with case that À = so that baselines are able to estimate the value of a according to the 'no label noise' assumption for informative data. Firstly, we try to reduce the total data size by sampling the original dataset. We test each baseline with these partial dataset to evaluate their performance under data shortage scenario. The results are presented in Appendix Table and Table In this study, follow the setting of our synthetic experiment and fully shuffle the labels of the uninformative data and keep all the informative data intact. We can see that in this setting, our method still outperform all baselines.
Then we conduct experiments where we reveal the ground truth a each baseline. We test all baselines on both complete dataset and partial dataset. We always completely permute labels of MNIST to impose high label noise in uninformative data and keep informative data clean. The results are presented in Appendix Table 6 9 algorithm is handed the true a, our method still wins out. We believe that this is partially due the MWU mechanism. We will have section discussing MWU later.
We can see that even in the "easier" scenario, where every
Finally, we provide ablation study investigation the effect of the choice of epoch to estimate the a. For all baselines, the estimation of is non-trivial step, yet it is crucial to the results. We hypothesize that this is the main cause of the suboptimal performance of these baselines. Here we provide additional results by training for 120 epochs instead of 60 in section 7.2 The estimation error for a at 120 epochs is shown in Table T0 One can see that the error's magnitude is significant. This results in worse performance of both selector and classifier (Tables 11 and 12 Our method's 's result stay the same as it in Table since it doesn't It require a as an input.
Table 4: (MNIST- Partial Dataset- Unknown a) Uninformativelllfommaieee MNIST/Fashion using 25% shuffled data as proxy for noise. Uninformative Data Num.
Informative Data Num.
Criterion
Confidence
Ne.Net
DeepGambler
Ours
SR(()
79.87 : 0.40
74.03 1 1.38
73.22:0.31
20.24 1 9.25
15000
3750
Precision
0.22 + 0.00
0.29
0.02
0.30
1.00 + 0.00
Recall
0.85 + 0.00
1.00 :1 0.00
1.00 0.00
0.88 + 0.07
SR(%)
65.83 0.22
57.76 1.97
58.1320.68
13.71:0.24
15000
7500
Precision
0.38 + 0.00
0.48
0.02
0.48 + 0.01
1.00 + 0.00
Recall
0.92 0.01
1.00
2: 0.01
1.00 0.00
0.83 + 0.01
SR(%)
55.99 = 0.19
17.39 : 1.85
46.9620.50
13.06:11.86
15000
11250
Precision
0.49 0.01
0.60 0.02
0.60 1: 0.01
0.99 + 0.00
Recall
0.91
1.00 : 0.00
1.00 0
0.84 + 0.02
SR(%)
0.25
30.23 + 0.90
39,85-0.366
19.50
15000
15000
Precision
0.57 + 0.00
0.68 0.00
0.68 + 0.00
0.99 + 0.01
Recall
0.95 + 0.00
1.00 0.00
1.00 + +.000
0.91 + 0.04
C.2 ABLATION STUDY: EFFECT OF MULTIPLICATIVE WEIGHT UPDATE
As mentioned in the discussion of a's effect, we can see that our method win in the "easier" scenario, where every algorithm is handed the true a, our method still wins out. We believe that this is partially due to the MWU mechanism. It guides the classifier put more emphasis the informative data. This is confirmed via an ablation study reported in Table [3] when MWU turned off, our algorithm's performance deteriorates.
33

---

Under review as a conference paper at ICLR 2023
Table 5: (SVHN- Partial Dataset- Unknown a)) Uninformattive/ltformaaay SVHN using 25% of
shuffled classes as proxy for noise.
Unintormative Data Num.
Informative Data Num.
Cniterion
Confidence
SelectiveNet
DeepGambler
Ours
SR(%)
74.47 4:15
64.68 + 20.32
34.48 13.46
14.36 0,08
9200
2285
Precision
0.41 = 0.05
0.37 : 0.22
0.68
0.87 0.07
Recall
0.94 + 0.01
0.85 + 0.23
0.83 0.24
0.80 + 0.02
SR(S)
61.44 1 0.64
48.42 1: 23.42
26.42 1 1.68
7.46 1: 0.87
9200
4600
Precision
0.57 0.00
0.58 + 0.17
0.77 + 0.02
0.94 0.07
Recall
0.95 0.01
0.97 + 0.03
0.96 0.01
0.85 + 0.01
SR(%)
62.41:00.70
3.01
20.83
1.25
9200
6900
Precision
0.76 + 0.03
0.82 + 0.02
0.94 + 0.01
Recall
0.96
0.96 - 0.03
0.97 0.01
0.87 + 0.01
SR(%)
49.45
24.69 3.08
18.81 1.47
0.22
9200
9200
Precision
0.67 = 0.00
0.77 = 0.03
0.83 0.01
0.94 + 0.01
Recall
0.96 0.000
0.98
0.98 0.00
0.88
Table 6: (MNIST - Full Data Setting Known a) Results on a synthetic dataset consisting of
uninformative MNIST data and informative Mashion-MNIST data using the entire MNIST.
Uninfommtive Informative
Criterionn
Contdence
SeleetiveNet
DeepGambler
Ours
SR(%)
10,00 i 0.32
10.11 0.42
9.77 0.51
9,18 0.49
60000
15000
Precision
0.99 0.00
1.00 1. 0.00
1.00 1 0.00
1.00 0.00
Recall
0,99 0.00
1.00 + 0.00
1.00 + 0.00
1.00 0.00
SR(%)
9.41 + 0.200
9.91 0.48
9,39 = 0.26
9.03 2 0.73
60000
30000
Precision
0.99 0.00
1.00 + 0.00
1.00 + 0.00
1.00 0.00
Recall
0.99 +
1.00 0.00
1.00 + 0.00
1.00 + 0.00
SR(%)
8.63
0.35
8.58 0.26
60000
45000
Precisiom
1.00 1 0.00
1.00 1 0.00
1,00 1 0.00
1.00 0.00
Recall
0.00
1.00
1.00 0.00
SR(%)
8.11
8.21 0.12
8,16 + 0.05
8.04 0
60000
Precision
1.00 0.00
1.00
1.00 0.00
Recall
0.99 0.00
1,00 + 0.00
1,00 + 0.00
1.00 + 0.00
Table 7: (MNIST- Partial Data Setting Known a) Results on synthetic dataset consisting of
uninformative MNIST data and informative Bashion-MNIST data using 25% of MNIST.
Uninformative Data Num.
Informative Data Num.
Criterion
Conlidence
SelectiveNet
DeepGambler
Ours
SR(3)
16.71 1 0.31
13.50 0.30
14.1113655
11.38
0.49
15000
3750
Precision
0.94 = 0.02
1.00
0.00
1.00 = 0.00
1.00 1 0.00
Recall
0.90 1 0.04
1.00 0.00
1.00 :: 0.00
1.00 1 0.00
SR(%)
13.93 0.400
13.34 1044=10 1.23
11,20 + 0.22
11.29:0.44
15000
7500
Precision
0.96 1 0.01
0.99 0.01
1.00 :: 0.00
1.00 1: 0.00
Recall
0.95 0,02
0,13
1,00 = 0.00
1.00 1 01.00
SR(3)
12.29 1 0.31
11.45 0.37
10.61 0012
10.42 0.48
15000
11250
Precision
0.97 + 0.01
+.00
1.00 = 0.00
0.99 + 0.00
Recall
0.95 1: 0.03
1.004:0.00
1.00 :: 0.00
1.00 1: 0.00
SK(%)
11.76
11.24 [1.24=033
10.12=0.28
9.97=0.33
15000
15000
Precision
0.97 = 0.01
1.00
1.00 = 0.00
0.99 + 0.01
Recall
0.95 0.02
0.00
1.00 0.00
1.00 + 0.00
Table 8: (SVHN- Full Data Setting Known a) Results on a synthetic dataset consisting of
uninformative SVHN and informative SVHN using the entire uninformative data.
Uninformative Data Nun.
Informative Data Num.
Criterion
Contidence
SelectiveNet
DespGambler
SR(S)
6.45 1 0.93
55.06
35.91
4.58 1 0.61
4,48
33800
9200
Precision
0.01
0.41
0.96 0.00
Recall
0.89 0.01
0.37
1 0.34
0.86 1 0.02
0.86 0.01
SR(3)
0.31
80.42 1.55
3.08 0.15
33800 18300
Precision
0.96 1 0.00
0.35
1 0.00
0.97 1 0.00
0.97 0.00
Recall
0.01
0.38 0.05
0.90
0.88 0.01
SR(%)
4.49 = 0.68
5.22
0.11
3.65=0.17
33800
26200
Precision
0.68
0.95
0.97
0.96 0.00
Recall
0.94 1 0.01
0.92 0.03
0.94 1 0.00
0.93 1 0.01
SK(S)
10.57 0.68
8.27 5.03
7.65
33800
28400
Precision
0.89 + 0.00
0.92 0002+00.0 0.05
0.92 + 0.01
0.93 0.01
0.00
0.95 0.04
0.97 0.01
0.95 0.01
C.3 ABLATION STUDY: EFFECT OF NOISE RATIO GAP X.
We inject different level of noise into each part of the data according to Definition by X(x) = X. The higher the À is. the larger the gap of the information noise ratio between informative and uninformative partition. Specifically, for informative data, we inject 100 ( -)% uniform
by setting
34

---

Under review as a conference paper at ICLR 2023
Table 9: (SVHN- Partial Data Setting- Known a) Results synthetic dataset consisting of
uninformative SVHN and informative SVHN using 25% uninformative data.
Uninlormative Data Num.
Informative Data Num.
Criterion
Conñidenee
SelectiveNet
DeepGambler
Curs
SR(S)
55.91 20.49
10.48
11.14 2.32
9200
2285
Precisson
0.70 = 0.35
0.19
0.933 0.01
0.90 +: 0.02
0.67
0.16
0.78 0.02
SR(S)
10.41
36.46 28.65
9.70 1.05
8,12 = 0.87
9200
4600
0.00
0.90 4:008
0.93
Recall
0.87 = 0.01
0.60 0.24
0.79 + 0.04
0.78 + 0.08
SR(%)
8.51 + 0.85
34,97 + 30.15
7.49:1..47
7.67-0.63
9200
6900
Precision
0.92 0.02
0.73 0.21
0.94 0.01
0.92 1: 0.02
Recall
0.91 0.02
0.74 = 0.22
0.83 0.01
0,86 =: 0.01
SR(%)
9.06 0.82
13:66 1 1.39
7.88 0.29
7.57
9200
9200
Precision
0.91 0.01
0.88 = 0.02
0.93 0.01
0.92 = 0.01
Recall
0.94 = 0.01
0.92 = 0.01
0.88 0.03
0.91 = 0.01
Table 10: Real and Estimation Error (120 epochs)
Uninformative Data Num.
Informative Data Num.
600X0
60000
0.05 0.00
0.50
60000
45000
0.08 0.00
0.33
60000
30000
0.11 0.00
0.25
60000
15000
0.17 0.20
15000
15000
0.00
0.50
15000
11250
0.40 0.00
0.33
15000
7500
0.49 + 0.01
0.25
15000
3750
0.63 -: 0.01
0.20
Table 11: (MNIST Full Dataset- Unknown a Run 120 Epochs for â). Results on a synthetic datasct consisting of uninformative MNIST and informative Fashion-MNIST using the entirety of shuffled MNIST as proxy for noise.
Unintormative Data Num.
Informative Daia Num.
Criterion
Contidence
SclectiveNet
DoepGambier
Ours
SR(%)
51.81 0.47
53.01100
1.00
0.31
60000
15000
Precision
0.34 = 0.00
0.52::0.00
0.53 = 0.01
1.00 = 0.00
0.00
0.00
1,00
0.01
SR(3)
31.86 1 0.73
35.00
0::00:000 1.00
34.0 1.00
12403 L.6
60000
30000
Precision
0.01
0.72
0.00
Recall
0.98 4 0.00
1.00 1: 0.00
1.00 :: 0.00
0.92 : 0.04
SR(%)
22.29
26.0000000
24.00 0.00
2000
60000
45000
Precision
0.79 i: 0.29
0,88 1: 0.86
0.89 :: 0.00
1.00 : 0.00
1,00
SR(S)
16.29 1 0.42
11.00 2.00
18.00 1 0.00
11.61 0.79
60000
60000
Precision
0.00
0.98
0.02
1.00 +
Recall
1.00 à: 0.00
0.98 1: 0.02
1.00 0.00
0.97 4: 0.01
Table 12: (MNIST Partial Data Setting- Unknown a- a-Run 120 epochs for à) Results on a synthetic dataset consisting of uninformative MNIST data and informative Fashion-MNIST data using 25% of MNIST.
Uniformative Data Nuan.
Informalive Data Numn
Criterion
Confidence
SelectiveNer
DeepGambler
Ours
SR(%)
72.06 : 0.68
78.00 1.00
78.00 = 0.00
11.38 0.49
15000
3750
Precision
0.29 0.01
0.24 0.01
0.24 = 0.00
1.00 + 0.00
Recall
0.70 :: 0.01
1.00
1:00..0.00 0.01
1.00 0.00
1.00 1: 0.00
SK(%)
54.00 0.44
65.00 1.00
64.00 + 0.00
11.29:0.44
15000
7500
Precision
0.49 = 0.00
0.40
0.41 = 0.00
1.00 + 0.00
Recall
0.80 0.01
1.00 0.00
1.00 = 0.00
1.00 + 0.00
SR(%)
44.17
55.00
=000=10 1.00
$4.00 = 0.00
10.42 = 0.48
15000
11250
Precision
Recall
0.85 = 0.01
1.00 0.00
1.00 = 0.00
1.00 + 0.00
0.26
1.0
15000
15000
Precision
0.68 = 0.00
0.58 0.01
0.61 = 0.00
0.99 + 0.01
1.00
label noise (each class has chance ( -) to be flipped into the other classes). For uninformative data, we inject 100 * 1 (1 + 7)% uniform label noise. We test each baseline on these semi-synthesized dataset. The result is presented in Table 14
For all baselines, we give as prior information to calculate a according to the realized accuracy of predictor f. In Table 14] we can see that our method can effectively recover informative data out of the uninformative ones compared with existing baselines. We put top of selective risk number
35

---

Under review as a conference paper at ICLR 2023
Table 13: (MNIST- -Fll Data Setring- Known a Turn off MWU) Results synthetic dataset
consisting of uninformative MNIST data and informative Fashion-MNIST data using the entire MNIST.
Uninformative Data Num.
Informative Data Num.
SR
Recall
Precision
60000
60000
0.09000.00
0.9910.01
0,9910.01
60000
45000
0.09+00.00
1.00+0.000
1.00+0.000
60000
30000
0.10:00.00
1.00=0.000
1.0010.00
60000
15000
0.10=00.00
1.00=0.00
1.00+0.00
15000
15000
0.11=0.01
1.00=0.00
100000.00
15000
11250
0.11=00.00
1.00:10.00
1.00+:.00
15000
7500
0.12=00.00
1.00=0.00
1.00+0.00
15000
3750
0.12.00.00
1,00.1..00
1.0010.00
where the corresponding algorithm fail to select reasonable amount of data (low recall) and thus result in degenerated performance. All baselines have the same problem with learning given noisy labels. The key input a cannot be properly estimated due to the poor accuracy, which in turn leads to poor selection result. Our method doesn't have this issue because it learns to abstain uninformative data and thus doesn' 't require knowing a.)
Table 14: Synthetic Experiment on MNIST+FashhonMNNISTT Fix
and Vary À
A
Criterion
Confidence
SLNet
DeepGambler
Ours
SR(%)
0.00 = 0.001
38.57:19.95
66.67=57.73
28.27:14.62
0.30
Precision
0.67=0.58
0.96=10.07
0.67=0.58
0.78
Recall
0.00=0.00
0.08+10.07
0.00+10.00
0.28:10.08
SR(%)
0.00 = 0.00
44.11=51.03
0.00 = 0.00
27.92+22.39
0.35
Precision
1.00+0000
0.60++0.53
1.00++0.00
0.92++0.14
Recall
0.00=0000
0.11+0018
0.00+0000
0.51+
SR(%)
33.331557.73
27.5916..29
33.33=57.73
23.46.14.13
0.40
Precision
1.00=0.00
1.00+10.00
1.00+00000
0.99
Recall 0.00=0000
0.33
0.00+10.00
0.55
C.4 ABLATION STUDY: CHOICE OF HYPER-PARAMETER
In this section, we provide ablation study on sensitivity of different algorithms w.r.t their hyper- parameter. We study under the same setting as Table and g For SelectiveNet, we first fix Aa to 32 (default setting that is recommended by the author in the original paper) and then we vary a from 0.1 to 0.7. Then we fix to be 0.5 (default setting) and then we vary X&ı from to 66. For DeepGambler, we vary o from 1 to 7. For our algorithm, we progressively increase the hyper-parament parameter 3 from to 10. As presented in Fig 7 3 and Fi the baselines' performance relies heavily their key hyperparameters. On the other hand, our method is much more robust w.r.t. its hyperparameter, 3.
We
that the performance of all baselines quite sensitive to the choice of hlyper-paametee and are expected to experience large fluctuations. In contrast, our algorithm is more stable with hyper-parameters. This empirical observation supports that the choice of
regard to the choice is flexible, as it is stated in Theorem [ Furthermore, in all scenarios, our algorithm's 's performance better than these two baselines as following. Firstly, our selector has better precision such that we can recover almost all informative data while the two baselines cannot. These two baselines tend to select the whole data set indistinguishably (low precision and high recall). Secondly, these baselines consistently show deteriorated risk performance compared against ours, mainly because of their selector fails pick informative data.
We also present the convergence curve of each evaluation metric for the partial data blind setting where a = 50% in Fig g We pick different combination 3 and MWU step-size 7). We can see that both recall and precision can converge in very quick and smooth manner. The performance of our algorithm is very robust against different combination of slightly recall drop and precision increase when 3 is chosen be some extreme values, e.g., f 10. We include such case to illustrate that while the method is not sensitive to parammtrr 3, the trade off between precision and recall, controlled by B, do exists.
There can be some
36

---

Under review as a conference paper at ICLR 2023
100
60C00/60000
60000/15000
Selective Risk (55)
0.8
15000/3750
0.8
0.6
60000/e00120
80000/80000
00000/15000
15000/15000
0.2
0.2
15000/15000
15000/5750
15000/3750
Selective Risk (%)
Precision
Recall
Figure 5: Ablation Study on Hyper- syper-parameter DeepGambler.
G030366000
1.0
50000/6C000
50000/1500 1500
Selective Sisk (%)
35000/17000
15998/3550
0.8
15000/15000
15000/3250
Prectsion
0.0
0.0
0.4
60000/15000
0.2
0.2
15000/15000
15000/3750
0.1
0.3
0.5
0.7
0.0
01
0.3
0.5
0.7
0.0
0.1
0.3
0.5
0.7
100
60002/60000
00000/15000
15000/15000
Selective Risk (%))
0.8
15000/3730
018
Practpion
0.0
0.0
62000/60000
60000/60030
60000/15000
13000/13000
0.2
0.2
15000/15000
15000/3750
15000/3750
18
32
50
66
10
37
50
05
16
50
60
Selective Risk (%)
Precision
Recall
Figure 6: Ablation Study on Hyper-parameter and Aut SelectiveNet.
100
00303/80000
1.0
60003/15000
Selective Risk (%)
80
13000/15000
15000/3150
0.8
0.8
60
Pracision
40-
0.4
0.4
5000R/60080
80000/80000
60003/15000
60000/15000
15000/15000
15000/3750
15000/3750
0.0
0.0
8
B
8
Selective Risk (%)
Precision
Recall
Figure 7: Ablation Study Hyper-paramette 3 Our Method.
C.5 ABLATION STUDY: SELECTIVE RISK U.S COVERAGE LEVEL
In this section, also the ablation study where vary the coverage threshold and compare the selective risk of each baseline under the same coverage level (See Figure C.5). Each bascline is trained with comppted dataset containing 50% and 20% informative data. We the same setting
37

---

Under review as a conference paper at ICLR 2023
2.-
jest Precision
Test ACC
2-0
mm1.0
0.6
111.0
8-4.0
ym3.n
Ama.
1-1.0
5.5.0
g=2.0
8-50
9=1.0
p. p-10.
D-10.
n-10
9=3.0
n=0.1
p-3.0
Q=0.1
8-3.0
7-0.5
B-3.0
9-0.5
8-3.0
0-1.0
A-3.0
9-1.0
8-5.0
n=2.0
0.-
q=2.0
100
120
100
140
Training Epoch
Training Epoch
1.0
9-1.0
f-5.0
Q-1.0
0.8
0.8
$-10.0
m=1.0
f=2.
q-0.05
Test Recall
A-2.0
9-1.0
9-0.1
p-4.0
mm1.
8-5.0
pm3.0
1-1.0
0.4
8=100
m=110
0.4
$=3.0
Q=2.0
$-3.0
7=0.05
8-3.0
9-0.1
n-0.5
$+3.0
/m10
A-3.0
4m2.0
20
40
60
80
100
120
180
260
20
40
60
150
200
120
140
180
Training Epoch
Training Epoch
Figure 8: Convergence Curve. Experiment on Partial MNIST with 50%
did in section 7.2 The selective risk computed by selecting the top coverage% confident data point. The selection confidence is measured using each baseline's 's selector module.
The ideal coverage(a) indicated by the black dash line the plot. An selective learning algorithm achieves the ideal coverage if it just cover all informative data. Coverage rate goes beyond ideal level will make the algorithm select uninformative data, which has purely random label in this case. We can see that when coverage ratio is within reasonable range compared to ground truth our method outperforms all baselines. The advantage of our method bigger when the noise ratio high, where all other baselines show a reverse-shape coverage v.s selective risk curve. This curve implies an sever noise-over fitting issue of baseline method given few data under high noise regime.
38

---

Under review as a conference paper at ICLR 2023
typerpane
1.0
1.0
ahw 6.30-22.
shrdloe0.5 Am15.
0.8
-l.dia-b..--330 A-S10
0gee1.3 1amm-10
dgge wamee1
Scrective
wa.3-10
6.4
04
6.2
0.4 Coveregge
0.6
0.9
1.0
0.0
0.2
0,5
0.6
0.0
1.0
Coveragee
Figure 9: Coverage v.8 Selective Risk Curve under Different Hyper-parameter Setting. We refer 'conf' to Confidence, 'slnet' to Selective-Net, 'dg" to DeepGambler. We plot the curve of different methods with varying byper-parameters, c.g., 3 for our method, and a for Selective-Net, warm up epoch and O for DeepGambler.
39


Reviews:
[{"review_id": "eA0J5GJ1s0W", "reviewer": "Reviewer_3Edq", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study learning with abstention in the regime where a large fraction of data is “uninformative,” both at train and test time. In particular the authors study a natural realizable formalization of this setting where there is a dataset X, a ground truth binary classifier $f \\in \\mathscr{F}$, and a ground truth `selector’ $g \\in \\mathscr{G}$ that determines what data is informative. Given $f$ and $g$, examples are then generated (roughly) via the following process: $x \\in X$ is sampled from some arbitrary (fixed) marginal distribution, then if g(x)=1 (informative) the label y is the ground truth f(x), while if g(x)=0 (uninformative) the label y is simply Ber(1/2) purely random noise. In fact the authors consider a generalized version of this model which adds an additional Massart-like data-dependent noise parameter $\\lambda$ to the second step, such that elements selected by $g(x)$ are Ber(1/2) w.p. $1-\\lambda(x)$, while non-selected elements are Ber(1/2) w.p $1/2+\\lambda(x)$\n\nGiven this setup, the main goal is two-fold: learn a selector g’ close to the ground truth, and a classifier on the support of g’ (informative data) with high accuracy. The authors provide two main results in this direction. \n\nFirst, the authors provide a minimax optimal strategy to recover the ground truth selector given access to a good estimate of the classifier $f$ (in many settings the latter can be obtained by classical techniques such as ERM). In particular, the authors show that $g$ can be recovered up to $\\varepsilon$ classification error in $\\frac{\\max(VC(G),VC(F))}{\\varepsilon}$ along with a matching lower bound in VC(G). The algorithm and analysis are based on empirical risk minimization of a surrogate loss on g based on the accuracy of f itself, as g(x) is not revealed to the learner.\n\nSecond, the authors develop a heuristic algorithm inspired by their theoretical analysis for jointly learning a classifier f’ and selector g’ based on the classical multiplicative weights update method. They show that this algorithm outperforms other types of learning with abstention (that typically aim to balance coverage and accuracy rather than learn a ground truth selector) in scenarios where a large fraction (e.g. 80%) of the data us un-informative, both on synthetic and real datasets.", "summary_of_the_review": "I recommend accepting this work on grounds of a theoretically interesting model for learning in the presence of uninformative data, minimax optimal sample complexity bounds, and an interesting heuristic algorithm + strong empirical performance in the regime of interest.", "strength_and_weaknesses": "Learning in settings with low signal-to-noise ratio is an important problem, especially in cases such as healthcare where the wrong diagnosis can be extremely costly. The model studied in this work is novel and theoretically natural, and the authors provide significant progress towards successful algorithms (minimax optimal bounds assuming a known classifier, and strong empirical results without). Furthermore, the paper is well written and provides many helpful comparisons to prior work in selective classification throughout. \n\nThe only real weakness in this paper is that the model itself seems fairly restrictive in application and it is not clear to me the extent one could truly apply the approach e.g. in healthcare, but I view this as minor since the work is theoretically interesting and a worthwhile start in modeling/approaching ML in such applications.\n\nMinor complaint: `Shattering’ typically refers to a data subset that can take all possible values. I’d recommend calling your assumption ``G-realizable,’’ since it exactly corresponds to the typical notion of realizable setting in learning.", "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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "OOnwxcbg3E", "reviewer": "Reviewer_8f3z", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": " Authors propose a method for learning with high label noise that is based on learning a predictor and a selector function. They introduce a loss function that weights the abstained points by the predictor’s correctness. They present a theoretical analysis in the noisy setting for picking the best selector function given the availability of a good predictor f. They derive an algorithm that jointly optimizes the predictor and selector along with some empirical evidence. ", "summary_of_the_review": "Even though I commend the authors for deriving both theoretical analysis and testing their proposed methods in practice, both the theoretical and experimental sections admit several weaknesses that combined together place the paper below acceptance threshold. In the theory section, they claim that predictor f and selector g do not need to be optimized jointly and present a result based on the availability of a good prediction function f, but then in the empirical section proceed to present an algorithm that optimizes f and g jointly. This conceptual mismatch needs to be addressed. I do believe that if the authors strengthen their empirical section by showing more results in the real world dataset regime, this paper will be easily accepted into a top tier conference. \n", "strength_and_weaknesses": "Strengths of the paper\n\n1. Introduce an interesting loss to quantify the benefits of the selector g according to the correctness of the predictor f. \n2. Authors present both theoretical and empirical aspects of the framework. \n3. Proposed algorithm optimizes simultaneously the predictor and selector function. \n\nWeakness of the paper: \n\nTheoretically: \n1. Theorem 1 is only a statement about selecting the selector g given that there is an \\hat{f} that is a good predictor. Having a joint result on (f,g) would greatly improve the paper. Even though a good predictor \\hat{f} may be achieved on the noisy data under some assumptions, couldn’t an even better predictor be learned on the data selected by g, that is on data that is ideally less noisy? \n2. More detailed discussion on how a good predictor \\hat{f} can be achieved is needed. They claim that it could be achieved  “under some margin condition” – are these additional assumptions or can it be part of assumption 1?  \n3. There is a large gap between the theoretical analysis and the presented algorithm as a series of relaxations are undertaken. In the theory section, they claim that “In practice, one can also apply some methods beyond ERM to obtain \\hat{f} ”, yet they do not apply these methods in the presented algorithm and instead try to solve a joint optimization over f and g. \n4. Compared to the abstention loss in Cortes et al., the main difference is that the cost of abstention is replaced by 1_{f(x) = y}. This should be highlighted in the main body. It is also unclear why a joint analysis on (f,g) as was done in Cortes et al could not be extended in this case since having a term 1_{f(x) = y} 1_{g>0} is as difficult to deal with as the already present term 1_{f(x) != y} 1_{g<0} in the abstention loss. \n\nExperimentally: \n\n1. Metrics are not clearly defined. \n2. I may have misunderstood the metrics since they are not clearly defined, but as far as I can tell the experiments using the semi-synthetic data for Q2 are not convincing since recall for their method is always lower than other methods. If their algorithm selects very few examples – leading to low recall, then it will have naturally high precision and high SR. Thus it is hard to compare the methods.  \n3. Experiments using real world datasets only test 3 datasets and the proposed method outperforms DeepGambler on only 1 dataset. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Mq22VekMyOs", "reviewer": "Reviewer_vmrJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The submission aims to distinguish informative data and uninformative data under a designed probabilistic setting. Under this setting, the true labels of informative v.s. uninformative are missing. To deal with this issue, the authors propose a learning method simultaneously learning the predictor and the selector, with a novel loss function for the selector constructed using the learned predictor. \n\nBoth theoretical analysis and empirical results are provided to support the proposed method.  ", "summary_of_the_review": "The submission is in high quality with novelty. The results are rich to support the proposed method, and the writing is also good. However, the studied problem setting (the assumed data-generating model) is a not shown to be realistic enough. There were not enough support for this assumed model in the submission. (comment 1)\n\nOn the other hand, if considered as a pure theoretical work, I am not quite sure whether the theoretical contribution of the submission is strong enough for comment 2. \n\n\n\n\n", "strength_and_weaknesses": "Strength\n\n1. The submission is well written and easy to follow. The notations are clearly defined and the rationale of the whole submission flows smoothly. \n\n2. The results of the submission is thorough and complete with both empirical and theoretical analysis provided for the method. \n\n3. The methodology is also novel under the described probabilistic setting. \n\nWeakness\n\n1. My biggest concern is the probabilistic setting focused on by the submission. The authors assume that the informative and uninformative data are different so that can be distinguished. I could not imagine a real-world case where the data really has informative and uninformative observations, and where the two can be so different. Such a case is not provided in the real-world experiments of the submission either. All of the studied real-world experiments do not seem to satisfy the assumed data-generating model. Further, the only example mentioned that seems to satisfy this strong model, the gene mutation example, is not thoroughly studied but just mentioned in the intro. \n\nTherefore, I am wondering whether it might be possible for authors to empirically study one real-world case, where it can be either theoretically or empirically shown that the assumed generative model is consistent with the data-generating process?\n\n2. I am wondering what might be the main technical challenge of the proof given the assumed model and a fixed good $f$ estimator? After fixing $f$, what is the difference between the considered problem compared with a empirical risk minimization or generative model estimation? Given that the model assumed is a little strong (comment 1), would it be possible for authors to provide some theoretical analysis on the performance of the algorithm 1, without fixing the $f$ as a good estimator but learned by the algorithm? This can further strengthen the theoretical contribution of the submission.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "L2yk3rRrnI", "reviewer": "Reviewer_rpJe", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper studies the Selective classification problem when data contains many noisy samples which should be filtered out. The authors present a novel loss function to train the selector g (used to classify whether data samples are informative or uninformative) given predictor f. They also prove that the optimal selector can be approximated when training with the proposed loss function. Finally, this paper presents an iterative algorithm that trains the selector in parallel with the predictor and provides empirical results demonstrating promising performance over baselines in both small datasets (Fashion Mnist + mnist, SVHN), semi-synthetic datasets and real-world datasets (breast ultrasound images, lending club dataset, and Oxford realized volatility dataset).\n", "summary_of_the_review": "The paper is heavy on the theoretical side (Theorem 1), however, it is not clear whether this bound is of significance for scientific understanding and future research.\n\nThere is a big gap between the theory (Section 5) and the practice (Section 6). I wish the paper can establish a coherent setup throughout with minimal relaxations.\n", "strength_and_weaknesses": "Strength:\n-Theory: the paper provides a minimax risk bound for the selector $g$\n-Practice: the paper contains an iterative algorithm to find the pair of predictor-selector (f, g). \n-  Even though the algorithm is heuristics, the performance is relatively well.\n\nWeakness:\n-Theorem 1 depends on the parameter $\\lambda$, which is rarely known.\n-The risk bound is only for the selector $\\hat g$, and there is no joint risk bound for the pair $(\\hat f, \\hat g)$.\n-There is a huge gap between Section 5 and Section 6. The algorithm in Section 6 contains several relaxations, including (i) cross-entropy loss replacing the binary loss, (ii) continuous output of $f$ and $g$ instead of binary. Thus, it is unclear how the bound in Section 5 can provide any guarantees on the performance of the predictor-selector pair found in Section 6.\n-There is no convergence guarantee for Algorithm 1. It is not clear how to choose $T$ and $\\eta$ so that we can have favorable convergence results.\n- It is desirable to provide experimental comparisons against Gangrade et al. (2021) [Selective classification via one-sided prediction] because the method therein outperforms both DeepGambler and SelectiveNetwork.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "HQGRBdS6KQs", "reviewer": "Reviewer_UQnf", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "The authors propose a method for learning when there is high amount of label noise present, using an iterative bi-level optimization. Their method in an iterative fashion first trains a classifier (predictor), then defines a pseudo-labels for the selector (abstain) classifier using confidence of the trained predictor on the target class. These pseudo-labels are used to train the selector classifier. The selector classifier then updates sample weights for the training of the next round of predictor.\nThey also formulate a noisy generative process to describe how the data was generated and provide bounds on the accuracy of the selector given a reasonably good predictor.\n\nTheir method is validated using both synthetically generated datasets (by combining MNIST and Fashion MNIST as well as a noisy SVHN) and real datasets (breast ultrasound images, lending club, and Oxford realized volatility). The method is however only compared with three baselines: DeepGambler, SelectiveNet, and a simple (singe-level) confidence-based selector.", "summary_of_the_review": "I cannot comment on the theory and am not an expert in this field, but the empirical results are not convincing for me. The model can simply trade-off lower recall for higher-precision to get low Selective Risk. A metric such as average precision could have been more convincing. I would also like to know how the selector and predictor adapt as the number of iterations (T) increases. I am not confident that this paper reaches the threshold for acceptance.", "strength_and_weaknesses": "Strengths:\n- Theoretically grounded\n- The method seems to perform better than baselines on synthetic data\n\nWeaknesses:\n- I find the metrics confusing. Selective Risk by definition seems to favor methods with high-precision and low recall, so I'm not sure if by itself this is such a useful metric\n- Relatedly, we also see that their method has high-precision but low recall. In Table 1: their method out-performs baselines in selective risk, but has lower recall and higher precision. The same is also seen in Table 2: the method is out-performing baselines at low coverage values, but drops off at 20% and higher coverage numbers are not provided. I'm not sure if the results validate the claim.\n- Only two baselines are compared. One related baseline to use could be DAC (Combating Label Noise in Deep Learning Using Abstention, Sunil Thulasidasan et. al., 2019).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": {}}]

Author rebuttal:

Decision: Reject