Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
strength_and_weaknesses: Strengths of the paper

1. Introduce an interesting loss to quantify the benefits of the selector g according to the correctness of the predictor f. 
2. Authors present both theoretical and empirical aspects of the framework. 
3. Proposed algorithm optimizes simultaneously the predictor and selector function. 

Weakness of the paper: 

Theoretically: 
1. 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? 
2. 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?  
3. 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. 
4. 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. 

Experimentally: 

1. Metrics are not clearly defined. 
2. 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.  
3. Experiments using real world datasets only test 3 datasets and the proposed method outperforms DeepGambler on only 1 dataset. 


clarity,_quality,_novelty_and_reproducibility: The paper is well written except some further discussions and clarifications are needed. See section above. 

Novelty lies in including a different cost associated with the abstained points, deriving new theory and algorithms under the high noise setting.

The results seem reproducible. 

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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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).

strength_and_weaknesses: Strength:
-Theory: the paper provides a minimax risk bound for the selector $g$
-Practice: the paper contains an iterative algorithm to find the pair of predictor-selector (f, g). 
-  Even though the algorithm is heuristics, the performance is relatively well.

Weakness:
-Theorem 1 depends on the parameter $\lambda$, which is rarely known.
-The risk bound is only for the selector $\hat g$, and there is no joint risk bound for the pair $(\hat f, \hat g)$.
-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.
-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.
- 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.

clarity,_quality,_novelty_and_reproducibility: The paper is dense and rather long for a short reviewing period. I did not fully check all the mathematical derivations.

No source code is submitted so I could not comment on the reproducibility.
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.

There 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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
They 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.

Their 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.
strength_and_weaknesses: Strengths:
- Theoretically grounded
- The method seems to perform better than baselines on synthetic data

Weaknesses:
- 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
- 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.
- 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).
clarity,_quality,_novelty_and_reproducibility: Clarity: the method in Algorithm 1 is clear. The metrics are not.

Novelty: I cannot comment on the theoretical novelty. The method as a whole is novel, but the iterative optimization of selector and predictor seems like a natural extension of the problem.

Reproducible: Yes, as the authors promise to release the code with the final submission.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 

Both theoretical analysis and empirical results are provided to support the proposed method.  
strength_and_weaknesses: Strength

1. The submission is well written and easy to follow. The notations are clearly defined and the rationale of the whole submission flows smoothly. 

2. The results of the submission is thorough and complete with both empirical and theoretical analysis provided for the method. 

3. The methodology is also novel under the described probabilistic setting. 

Weakness

1. 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. 

Therefore, 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?

2. 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.  
clarity,_quality,_novelty_and_reproducibility: Clarity 

The submission is clearly written and easy to follow. 

Novelty

The methodology and the generative model are novel to me. The methodological design are interesting and inspiring. 

Reproducibility 

The experiment setup is provided to reproduce the experiments. 
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)

On 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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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)$

Given 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. 

First, 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.

Second, 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.
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. 

The 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.

Minor 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.
clarity,_quality,_novelty_and_reproducibility: The work is well-written, the theoretical results are of good quality (optimal within an interesting regime), and the studied problem is interesting and (to my knowledge) novel.
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work analyzes a learning with abstention setting, which assumes the data distribution is generated as a mixture of informative and uninformative points. Under this setting, the authors provide an "selector loss" to train an abstaining function "g" and, furthermore show minimizing the loss (in the presence of a good classifier "f") results in an abstainer that is near optimal.  Finally, the authors present a practical iterative algorithm to simultaneously train f and g and demonstrate that the proposed method provides benefits in the highly selective regime, i.e., when it is assumed a large number of examples are noisy and, thus, only a small fraction of points should receive predictions.

The AC would like to acknowledge and commend the authors detailed responses during the discussion phase, which includes additional empirical evidence. Although the submission does make valuable contributions, the shortcomings, when considered together, keep this paper just below the bar for publication at this venue.

(1) The theory is presented wrt fixed "f" and consider the optimization of "g", however, the practical algorithm optimizes both f and g in an alternating fashion.  As the authors say in their feedback, they present "one-shot bound for the iterative algorithm" and a bound on the iterative algorithm is significantly more challenging. But going from the single-shot to iterative setting is a big jump and fundamental questions, like "does the alternating optimization converge (and to what solution)?", are critical to understand in a theoretical work.

(2) If we take the algorithm as a heuristic inspired by the single-shot theory, then the expectation is to see a very thorough and compelling empirical analysis. The authors do show on several benchmarks that the suggested algorithm is superior to a few other baselines in settings where higher precision (at lower recall) is desired, in particular, when few predictions are required (low coverage setting). This is a useful observation, but it's not clear from the experiments (or theory) why that is the case, or if there is any way to adjust the balance of precision/recall for the different target coverage level settings.

justification_for_why_not_higher_score: Although there are some interesting and potential important theoretical results provided by this work, there is jump to get to the practical setting which is analyzed empirically.  Neither the theory or empirical studies are strong enough to stand on their own and their connection would need to be made stronger to truly be coherent.
Decision: Reject