Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper is concerned with selective classification in a stylised 'realisably noisy' data model, wherein the support of the input distribution is partitioned into two chunks, the "informative" $\Omega_I$ and the "uninformative" $\Omega_U,$ such that 
- The labels are completely noisy ($\mathrm{Bern}(1/2)$) if the input lies in $\Omega_U$.
- The labels are completely clean if the input lies in $\Omega_I$.
- The learner has access to hypothesis classes $\mathcal{F}, \mathcal{H}$ such that 
    - There exists an $f^* \in \mathcal{F}$ with $f^*(x) = y$ on $\Omega_I$.
    - There exists a $g^* \in \mathcal{H}$ with $g^*(x) = 2\mathbf{1}\{x \in \Omega_I\} - 1.$

The paper studies the problem of learning a pair $(f,g),$ with $g$ serving as a selector, and $f$ as a predictor, such that $g \approx g^*$ and $f \approx y$ on $\{g \ge 0\}$ (and $\approx f^*$ on $\Omega_I$ if $g$ is learnt well), with the concrete goal of attaining both small selective risk ($P(f^*(x) \neq y|g(x) \ge 0)$) and both low false alarm and low missed detection for $g$ with respect to $g^*$. As is standard in selective classification, supervision of the value of $g^*$ is not given, and instead only $(x,y)$ pairs are provided.

This is approached by designing a new loss for learning a selector given a predictor $f$, denoted $W(g;f, \theta)$, that basically uses $\mathbf{1}\{f(x) = y\}$ as proxy supervision for when $g < 0$ or $g > 0$ is preferred, but weighted by a factor to account for the prevalence of uninformative versus informative data. It is first shown, using uniform convergence techniques, that if the indicator ERM problem can be solved, then given  if $f^*_{S_n}$ is taken to be a minimiser of standard empirical risk, and $g^*_{S_n}$ to be the minimiser of an empirical version of $W(g;f^*_{S_n}, \theta)$ for appropriately chosen $\theta$ (in a way which depends on the prevalence of informative data $\alpha$), then these goals can be attained in a PAC sense, with sample complexity scaling as $\tilde\{O\}( \frac{d_\{\mathrm{vc}\}(\mathcal{F}) + d_\{\mathrm{vc}\}(\mathcal{H}) }{\epsilon^2 \alpha^2})$.

The paper then switches gears, and a alternating minimisation based heuristic method for practically learning $(f,g)$ is proposed. The idea is to first learn (soft functions) $f$ and then $g$ using relaxed versions of the above losses, and then multiplicatively increase the weight of points that are selected by the $g$ in their contribution to the loss for $f$, and repeat. The remainder of the paper is devoted to empirical evaluation of this method in two situations - firstly, uniformative (randomised labels) MNIST data is given along with varying amounts of clean Fashion MNIST data; and secondly, part of the classes from the SVHN dataset have their labels randomised to represent uninformative data, while the rest remain clean. While the scheme is observed to have similar performance in how well the selector identifies the underlying $g^*$, the proposed method has remarkably better selective risk compared to baselines from the recent selective classification literature.
main_review: Strength & Weakness: I am conflicted about the main structure of the paper of cleanly separated completely noisy and completely clean data with both aspects realisable. In my opinion this situation is quite unrealistic, which meaningfully impairs the study. Nevertheless, this seems to be the analogue of realisability relevant to selective classification, and thus a natural setting to investigate tight bounds on the basic aspects of the problem. That said, I don't think the paper makes this case sufficiently well, instead posing the setting as a sort of Huber-type contamination of the data that persists to test time, but is kind enough to be entirely separate from the real data - this is quite unconvincing to me. 

Strengths: Modulo the above, I find the basic idea of the scheme and the loss embodying it to be quite interesting, and the analysis supporting it is straightforward, and natural. I find the heuristic to be even more interesting, in particular due to the multiplicative weighting idea, which I think is an elegant way of reinforcing the attention of $f$. The empirical results are, of course, stark and impressive, but I have some reservations about the same (see below)

Weakness:

- Theoretically, there are two gaps - the major one, in my opinion, is that the analysis requires a priori knowledge of $\alpha$ to appropriately set $\theta$ for the loss. This I think weakens the results significantly. One way to ameliorate this would be to extend the results so that an upper bound on $\alpha$ is sufficient (which is a much more realistic assumption, although of course ideally the method should adapt to $\alpha$). Also important, but less so, is the lack of a lower bound for the problem (it is clear that reliably estimating $f^*$ would necessitate the use of $\Omega( (\alpha \epsilon)^{-2})$ samples, I don't think this fact is all that interesting).

- Specifically regarding the experiments, I have questions about the baselines, and the proposed method's hyperparameter selection.

    - Lack of explanation of the results: The empirical results presented are starkly positive, but the exposition offered does not clarify what aspect of the scheme is buying this performance . For instance, all the methods seem to estimate the underlying $g^*$ well, but the competing methods cannot offer appropriate labels. Is this because of the repeated multiplicative re-weighting in the loss for $f$? Do the results hold if this is turned off? Does a similar iterative training improve the risk for the competing methods? I think ablative analysis along these lines is crucial for understanding the contribution of this paper.

    - Lack of clarity about baselines.
        - With empirical performances so starkly different, I cannot but help question if the baselines are being fairly executed. The big issue here is whether the hyperparameters for these methods are being selected in an appropriate way - this is bolstered by the situation of Tables 5-8, where $\alpha$ is assumed to be available to the algorithms, and the baseline hyperparameters are thus  presumably being set appropriately, and the performance gaps are much reduced. This leads me to the following questions:
            - Does this procedure given on page 8 yield a decent estimate of $\alpha$? How does performance vary if you train for more epochs?
            - In the appendix, it is stated that default hyperparameters are used for each method. What does this mean for something like selective net? 
            - The baseline 'Confidence' is never described. Is this the method proposed by Geifman & El-Yaniv 2017? Something else? Does this method have hyperparameters? How are they tuned?
 I understand that choosing the hyperparameter in these prior methods for this particular scenario may be considered beyond the scope of this paper, but in my opinion unless it is justified that the hyperparameters are being selected in a meaningful way, this presentation is meaningless. 

    - Hyperparameter selection for the proposed method: how precisely is $\beta$ selected? This is never described in the text, and the only reference to it appears in Appendix D where it is said that the default parameter $\frac{\theta (1-\alpha)}{\alpha (1-\theta)}$ is used. This is both non-informative, because the question then becomes how is $\theta$ selected, and troubling, because it appears that $\alpha$ is being used to pick $\beta$. Is this the case?


- Relation to prior literature:

I think the selective classification literature is slightly mischaracterised, in the sense that it is not restricted to coverage oriented designs, as is suggested on page 3. Three explicit references theoretically and methodologically studying low-error selective classification are [1,2,3], all of which give PAC-style definitions regarding attaining low error selective classifiers, and [1] shows various computational reductions regarding the learnability of selective classifiers, and [2,3] provide sample complexity guarantees. In fact I believe Proposition 4 in [3] is directly applicable to the situation of this paper. Further, [3] also proposes a method that empirically dominates both the selective net and deep gamblers methods, and so might be good to compare to.

Additionally, I think [4] might be a pertinent reference, since it too proposes an alternating minimisation strategy for learning selective classifiers (although I think there's plenty of novelty in the presently proposed method beyond this).

[1] Adam Tauman Kalai, Varun Kanade, and Yishay Mansour. Reliable agnostic learning. Journal of Computer and System Sciences, 2012.

[2] Durmus Alp Emre Acar, Aditya Gangrade, and Venkatesh Saligrama. Budget Learning via Bracketing. AISTATS, 2020.

[3] Aditya Gangrade, Anil Kag, and Venkatesh Saligrama. Selective Classification via One-Sided Prediction. AISTATS, 2021.

[4] Feng Nan, and Venkatesh Saligrama. Adaptive Classification for Prediction Under a Budget. NIPS, 2017.

---

Questions and Comments:

- Assuming that the experiments are kosher, do you have hypotheses for how the advantage is being gained over the baselines? I noticed that the precision and recall (presumably of the selection with respect to a noisy/not-noisy oracle) of all methods are similar. Does this mean that the other methods are simply not learning the correct predictions on the domain they do select? 

- For the theoretical parts, I haven't checked this thoroughly, but it seems like it should be possible to get away with using about $\frac{d(\mathcal{F}) + d(\mathcal{H})}{\min(\alpha, 1-\alpha)\epsilon}$ labeled and $\frac{d(\mathcal{H})}{\alpha^2 \epsilon^2}$ labeled datapoints (up to $\log$s) by picking $g$ to be the maximiser of ${\hat{P}}_\{\lnot \ell\}(g = 1)$  subject to the constraint that $\hat{P}_\{ \ell\}(f \neq Y, g = 1) = 0$, where $\hat{P}$s are unlabeled and labelled empirical measures. Note that this is just the scheme of [3]..


Quibbles:

- I don't think $f^*$ as defined really makes sense. It is ostensibly defined on all of the space, but it clearly cannot be uniquely defined here in even mildly rich settings - for instance, if $\mathcal{F}$ has functions that agree on $\Omega_I$ but differ on $\Omega_D$. 
- In section 3, the abstention criterion suddenly switches from $g = -1$ to $g < 0$. While mathematically identical, such devices are commonly used in the ML literature to semantically adjust  functions from 'hard' to 'soft'. Is this the intention here? If not, perhaps the authors can stick to one presentation? More importantly, in section 3.3 $g$ suddenly switches to being $[0,1]$ valued, and the abstention criterion to $g < 0.5.$ I understand that this is for the sake of the cross-entropy loss, but this is needlessly confusing - I think consistency here saves your readers needless recalibration.  
- It is strange that $g$ is taken to lie in $\mathcal{H}$ rather than $\mathcal{G}.$  

summary_of_the_review: On the whole, I think that while I don't find the scenario posed by the paper convincing, I do find the concrete setting itself to be so. The scheme proposed for the same is interesting, and, taken at face value, very effective. Nevertheless, I right now am not convinced that the baselines are being compared to correctly, which needs to be justified, and further, I think that ablative experiments illuminating how the aspects of the proposed contribute to performance are needed. I think without these, though, the theoretical study ultimately produces a sample complexity analysis for a method that uses the knowledge of a key underlying parameter, and even then is not shown to be tight, which is a bit too weak, and I think needs more work.

With the above consideration, I have reservations about recommending acceptance as the paper stands. I am willing to budge on this if the experiments are clarified, or if the analysis can be improved.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers a setting where the label is random noise if the input is in an uninformative subspace, provides theoretical analysis for the estimated predictor/selector that minimizes classification risk/a novel selector loss, proposes a practical iterative algorithm to approximate the estimators based on MWU, and tests on semi-synthetic experiments. 
main_review: Strengths.

The paper is organized well with clear problem formulation, definitions & assumptions. The methodology is supported with theoretical results and implemented by an iterative algorithm. While the problem formulation requires uninformative samples are separated from informative ones, the authors also tested more challenging settings in the experiments.

Weaknesses. 

There are previous papers related that are missing here. For example, "Combating Label Noise in Deep Learning Using Abstention" by Thulasidasan et al. also seems to do very similar things and has similar title, but is not discussed in the related work. Also, some descriptions to previous works are not accurate, e.g., "While above works assume the presence of noisy data only in the training stage" -- some of the works above are in the parameter recovery setting, so it is slightly unfair to compare without the problem setting described clearly. 



summary_of_the_review: The paper is well written in general. The descriptions on related literature need some improvement.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers supervised learning with abstention -- where the learning method can decide to make prediction in some region of the feature space, and declare the rest of the feature space unpredictable. The setting is related to but different from the classical selective prediction, and to prediction uncertainty quantification (i.e. imbuing predictions with calibrated confidence intervals). Classical selective prediction balances coverage vs. accuracy -- whereas in the setting here the authors assume that there is a "true" split into an informative and uninformative partition of the feature-space,  and the goal is to both recover the partition and learn a good model on the informative partition.  The paper focuses on theoretical analysis, and also has experimental results suggesting that if the data is generated according to the author's model, than a heuristic algorithm inspired by the analysis indeed outperforms other selective prediction baselines. 
main_review: The main contribution of the paper is a new model for prediction with abstention, which postulates that samples in one region of the feature space can be predicted well, while in the rest of the space entirely unpredictable.  Under this model, the authors derive an oracle-based algorithm which can provably recover both the informative-partition (selector) and a good model on it (predictor).  For practical settings one can not always assume exact minimization of the empirical risk, so the authors propose an iterative algorithm which alternates learning the selector and the predictor, using something akin to multiplicative updates. Under the assumed generative models it seems to outperform baselines, sometimes by a wide margin, especially in a setting where the fraction of informative samples is small. 

The paper mostly reads well, has detailed theoretical analysis (which I only had a chance to skim), and presents experimental evidence supporting the claims.

My main criticism of the paper is: 
1) To me the model seems entirely artificial, and I am not aware of any realistic settings where the data can be partitioned into a region with great classification, and an uninformative region. For high-noise data in my experience it's much more common that there is a fairly weak signal over the entire feature space, with no pockets of high predictability. I'd be very interested to hear evidence on the contrary.  The examples are very stylized, and likely heavily leverage the fact that they match the assumed generative model. Showing how this translates to a more realistic example would have been helpful -- as the analysis may have a chance to be suggestive for more practical settings as well. 

2) I am surprised that using methods which allow uncertainty quantification -- e.g. maybe bootstrap resampling, or say Gaussian processes would have a hard time in this setting. I would have expected that it's not that hard to learn to distinguish MNIST from fashion MNIST, and to assign tight confidences around the region of MNIST examples, while giving large error bars to fashion-MNIST. Is the problem that the "Model prediction confidence" gives out incorrect (i.e. uncalibrated confidences?).  For DNNs and many other learners this overconfidence is a well-known problem (e.g. there's a nice paper "On Calibration of Modern Neural Networks" from Killian Weinberger's group,  and also well known solutions, for example from Charler Elkan and Bianca Zadrozny, "Obtaining calibrated probability estimates for classifiers".  

3) If instead of trying to identify the "predictable region" -- you try to apply / modify the method to attack the original selective prediction -- is it competitive with existing approaches? My suspicion is that the approach is quite dependent on having data with a well-separated true informative/uninformative partition -- and going after support recovery. 

4) How do you incorporate the complexity of the decision boundary for the selector?  If you assume a simple function class -- e.g. linearly separable in low-dimensions I assume it's easy to identify -- but generally the selector region may itself has a complex boundary, which may require regularization to learn.  How do you balance the regularization of the selector vs. the selector accuracy vs. the predictor accuracy (vs predictor regularization)?  It seems practically daunting. 

5) You mention that the predictable region has to be high-signal-to-noise. How sensitive it is to this? For example if there are two regions, one already noisy, and another completely unpredictable, how quickly does it break down with the SNR?

summary_of_the_review: This paper proposes a novel formulation supervised learning with abstention. It assumes that feature space can be split into an informative region, and a completely unpredictable region.  It offers detailed theoretical analysis showing that recovery is possible, and a heuristic practical algorithms to both recover the partition of the feature-space, as well as learning the model over the predictable region.  The setting is interesting -- but I suspect it's very artificial, so I'd be very curious to know to what extent this has relevance to applications which have no clear-cut partitions (or to traditional selective inference).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors analyze selective learning when part of the data is pure noise and uninformative. The paper presents an algorithm by a two-phase optimization procedure and provide PAC bounds for both the ground truth predictor $f^\star$ and the selector $g^\star$.
main_review: The paper is well-written, clearly organized and easy to follow. The problem of identifying uninformative data is interesting and very relevant in modern machine learning. The theory of the paper---though highly stylized and is based on $0-1$ loss that cannot be optimized efficiently---is revealing and also a good starting point. However, this is also the main weakness of the paper, the algorithm analyzed is based on $0-1$ loss that cannot be solved efficiently, while the heuristic algorithm implemented is based on the cross-entropy surrogate.

Some detailed comments are listed below:

1. In the setup that the uninformative part consists of pure noise while the informative part is noiseless in Eq. (2), which seems a bit unrealistic. Can the authors explain why in the informative part of the data cannot be random? (say $\mathsf{sign}(P(y=1|x) - 1/2) = f^\star(x)$ under some Mammen-Tsybakov condition/margin condition)
2. The empirical studies are not exactly supported by the theory as they are essentially different algorithms.
3. Can the authors specify what are the hypothesis classes in the experimental setup?


summary_of_the_review: The paper studies identifying uninformative data in datasets which is a very relevant problem for the machine learning community. The algorithm analyzed in the paper is supported by interesting theoretical results and can be revealing for more realistic algorithms.
review_title: null

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

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