Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies classification with rejection (CwR) in multiclass problems. The proposed method can utilize any classification-calibrated surrogate losses while maintaining theoretical guarantees (consistency). Specifically, the work establishes the equivalence between K-class CwR problem and a (K+1)-class classification problem by showing the two classification risks are equal. Then, using any multiclass surrogate loss as a building block, a formulation of surrogates is proposed to realize the surrogate risk of the (K+1)-class classification problem, with only the original K-class training data needed. An estimation error bound is derived for its ERM. It is then shown that a necessary and sufficient condition for the proposed surrogate to be consistent is that the underlying multiclass surrogate loss is classification-calibrated. Finally, the calibration analysis of the generalized cross entropy (GCE) loss is provided.
strengths_and_weaknesses: This paper is a solid piece of work. It is also well-written and well-presented.

**Originality:**
The proposed method can utilize any classification-calibrated surrogate losses while maintaining consistency guarantees, by showing the equivalence between K-class CwR problem and a (K+1)-class classification problem. It is novel, simple and effective. Related works have been properly cited and discussed.

**Quality:**
The work is sound. Claims are well supported by both the theory and experimental results. Weaknesses and limitations have been discussed.

**Clarity:**
The paper is mostly well-written and well-organized. Some minor problems I found are listed below. The authors are encouraged to proofread more carefully.
- "Lemma X" are referred to several times, while the paper only has "Theorem" and "Corollary" instead of "Lemma". Line 159. Line 173. Line 222. Line 237.
- Line 173: Should be $R_{01c} (c \circ \mathbf{g})$.
- Definition 6 and Theorem 5: inconsistent notations $\Phi_r$ and $\Phi^r$.
- Section 5.2: the flow can be improved. Before Theorem 5, "..., to the best of our knowledge, its calibration results remain unknown, and thus it is unsafe ...". Then the calibration of GCE is presented in Theorem 5. The flow of this part seems a bit abrupt.
- In Table 2, I think 01c, Rej, and 01 correspond to the first paragraph of Section 6, but it would be more clear to include their meanings in the caption of the table.

**Significance:**
The paper is a valuable piece of work in the field classification with rejection. The proposed method is simple, general, and effective. It can also be very useful for practitioners.
questions: - In Section 6, it is mentioned that DEFER is a special case of the proposed method with cross entropy loss as $\Phi$. However, cross entropy loss is also classification-calibrated. Then why the performance of DEFER is not that good?
- For FMNIST, CE and Sigmoid outperformed GCE. Any ideas why that's the case?
limitations: Yes, in the appendix.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper considers the consistency of surrogate losses in classification with rejection (CwR) problem. 

The paper first construct an augmented classification without rejection problem, which is equivalent to the CwR problem. Then,  building upon the classical consistency analyses, the paper defines a family of l_{01c} consistent losses in CwR based on arbitrary l_{01} calibrated loss. Further, it proves that such a relation is a necessary and sufficient condition for l_{01c} consistency. 

Although most of the existing losses are proven consistent, the paper found that the generalized cross-entropy loss has not been investigated before and gives the first proof. 

The GCE induced loss achieves a good performance in practice.
strengths_and_weaknesses: Strengths:
1. The main contribution of the paper is to show that the CwR problem can be reduced to an augmented classification problem without rejection. The theory, as well as the methodology, are insightful. 

2. The theory inspires new surrogate losses in CwR that works well in real data.

Weakness:
1. A very minor concern is that maybe the authors can validate the theory on some synthetic data where everything (e.g, all risks) can be calculated. 
questions: I do not have too much to complain about.
limitations: This is a theoretical work and I did not see a direct negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work proposes a ERM learning algorithm for Classification with Rejection(CwR) problems. The work reveals the connection between CwR and traditional multi-class classification problem and avoids leveraging the less tractable self- augmented distribution in the proposed model.  Both the learning bound and consistency of the algorithm are provided. For consistency, this work provides the necessary and sufficient conditions when a surrogate and calibrated loss is adopted.
strengths_and_weaknesses: Weakness:
1. There are some minor mistakes in the manuscript. For example, in line 159 ‘It is obvious that Lemma1 is a special case of Lemma 1….’’ There is no Lemma 1 in the paper and I assume the author means that corollary 1 is a special case of Theorem 1. 
In line173 ’...indicates the minimization of R01c(\phi g) according to Lemmas 1 and 1.
In line 222 ‘According to Lemma1…’’ again, there is no lemma 1 in the paper.
I assume all the lemma1 in the paper refer to corollary 1 but even corollary 1 itself is problematic. Its main body states that ‘the following inequalities hold..’ but all it got is single equality. 
Those mistakes (and a few more)  make me confused from time to time during the reading and make the paper a bit harder to follow.
2. I feel some of the important arguments need to be further elaborated. For example, in line 172 ‘with a properly chosen surrogate \phi the minimization of \tilde{R_\phi}(g) can lead to that of \tilde{R}_{01}(\phi(g))’. Although some related works are cited, it would be more helpful for the author to briefly explain how the commonly adopted principles for choosing the proper surrogates and the rationale behind them.


Strength
1. This paper presents an effective ERM algorithm for CwR problems. The learning bound and consistency of the algorithm are both provided.
2. This paper offers an interesting view to connect multi-class classification and CwR, which is able to leverage calibrated surrogate loss to avoid directly addressing the c-self-augmented distribution during the learning process.

questions: In line 162 it says that the minimization of \bar{R}_{01} can be seen as ordinary classification risk minimization with a different marginal density p'(x) which does not affect the calibration since class posterior possibilities remain unchanged. I am a bit confused here, I thought the minimization of \bar{R}_{01}  can be seen as ordinary classification risk minimization only if there is no distribution shift between the two problems. But with p(x) changing, could we still treat them as the same?

limitations: None
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper focuses on consistent surrogate losses for multi-class classification with rejection, where consistency means that minimizing the surrogate risk also minimizes the desired target risk. The authors first show that $K$-class classification with rejection is equivalent to a $(K+1)$-class classification problem on a modified probability distribution $\tilde{p}$. They then show how surrogate losses for multi-class classification, operating on the original data distribution, can be modified to compute the risk on the modified distribution $\tilde{p}$. It is claimed that ($\ell_{01}$-)calibration of a surrogate for multi-class classification is a necessary and sufficient condition for consistency of the surrogate for classification with rejection. The paper also provides an estimation error bound for empirical risk minimization (ERM) of surrogates, and establishes the $\ell_{01}$-calibration of the generalized cross entropy (GCE) loss. Experiments compare the proposed approach using two different surrogates, GCE and pairwise-sigmoid, to recent works on classification with rejection on three datasets.
strengths_and_weaknesses: **Strengths:**
+ The equivalence between $K$-class classification with rejection and $(K+1)$-class classification allows a wide range of existing multi-class surrogate losses to be used, where classification calibration in the more usual sense (without rejection) is sufficient for consistency in classification with rejection.
+ The experiments demonstrate the benefit of this flexibility by showing that the proposed approach with GCE and pairwise-sigmoid losses can outperform existing methods that are restricted in their loss function.

**Weaknesses:**

I have several concerns about the proofs.
- Theorem 4, proof of necessity
    - First, should "suppose there are some $\mathbf{u} \in \Delta^{K+1}$" be $\mathbf{p}$ instead? $\mathbf{u}$ is optimized over in the equation below. If yes, then it would be better to change $\mathcal{U}$ to $\mathcal{P}$ as well.
    - I do not see why "any re-permutation of $\mathbf{u}$ ($\mathbf{p}$) also fulfills the equation above." Does this assume that $\Phi$ is permutation-invariant? Please justify further.
    - The statement that "there always exists a distribution $p(y|\mathbf{x})$ and $c$ that $\tilde{p}(\tilde{y}|\mathbf{x}) \in \mathcal{U}$" also needs further justification in my mind. On the surface, $\tilde{p}(K+1 | \mathbf{x})$ can be at most $1/2$ when $c \to 0$, so this seems like a constraint. Perhaps allowing all permutations in $\mathcal{U}$ (contingent on the point above being true) resolves this, but this should be clarified.
- Theorem 5: Two issues between lines 553, 554
    - In taking the expectation to go from the point-wise excess loss to the excess risk, I think the square root should be on the inside of the expectation, at least to begin with. Perhaps there is then an argument (e.g. Jensen's inequality) to move it to the outside.
    - In the exponent of $K$, I see that the $2r/(1-r)$ comes from the $\eta_\max$ term, but where do the $r + r^2$ terms come from?
- Theorem 1
    - Case $f^*(x) \in \{1, \dots, K\}$, $f(x) = R$ (I am using $R$ for reject because I don't know how to typeset the "registered" symbol in OpenReview): I think the right-hand side is missing $-1 + c(\mathbf{x})$.
    - The $y$ in $p(\mathbf{x}, y)$: I think it should be $\tilde{y}$ since this is the dummy variable being summed over.

**Minor comments:**
- A major thing I was looking for upon reading the introduction is the benefit of allowing a full range of surrogate losses. As I wrote above, I think the experiments have shown that benefit with the GCE and pairwise-sigmoid losses. So I think the introduction can state the benefit of this flexibility more strongly, to better motivate the paper, and point to the results in Section 6.
- "class-posterior possibility" and elsewhere: I believe "probability" is the standard term instead of "possibility".
- Line 48, "family of surrogates are the ensembles of arbitrary binary classification losses": This didn't make sense to me, perhaps words are missing.
- Line 84: "competent" --> "confident"?
- Line 116: "remaining" --> "retaining"
- Line 159, "Lemma 1" : I think this should read "Theorem 1 is a special case of Corollary 1." There seem to be several more broken references to Theorem 1 and/or Corollary 1, e.g. lines 173, 237
- Theorem 3: It would be good to clearly define $\hat{\mathbf{g}}$ as the empirical risk minimizer.
- I was a bit confused by the statements before Theorem 4 about "$\ell_{01c}$-consistency of such surrogates still remaining unchecked." It seems that sufficiency follows naturally from the development of the paper and the proof of Theorem 4 does not add anything on sufficiency. Perhaps these statements could be rephrased to say that what remains in question is the necessity of $\ell_{01}$-calibration (assuming that my concerns about Theorem 4 above can be resolved).
- Line 238: $D_c$ --> $D_c^R$ ($R$ for reject)?
- Line 259: $\Phi^\gamma$ --> $\Phi_\gamma$
- Line 292: "classification cost" --> "rejection cost"?

questions: Please respond to my concerns about Theorems 4 and 5 especially. My current score reflects these concerns.

For curiosity:
- Theorem 3: If the identifiability condition were dropped, then could we simply replace $R_{L_c^\Phi}^*$ in (6) with $\min_{g\in\mathcal{G}} R_{L^\Phi_c} (g)$?
- Lines 286-288, "GCE method outperforms the baseline DEFER method, which indicates that CwR cannot be simply solved by the methods used for learning to defer": I am wondering whether it really indicates that, or rather the advantage of using GCE over CE since that is the difference between the two (see lines 278-279).
limitations: OK
review_title: null

Meta-review: metareview: The consensus view was that this was solid and practically relevant theoretical research.

confidence: Certain
Decision: Accept