acceptodds
Under review as a conference paper at ICLR 2027

Classification with Abstention under Class-Conditional Error Constraints: Minimax Rate and Algorithm

Abstract

We study binary classification with abstention under separate class-conditional error constraints, with the objective of minimizing abstention while keeping both errors below prescribed thresholds. We characterize the distribution-free minimax rate of excess abstention risk, up to logarithmic factors, in terms of the complexity of the hypothesis class and the sample size. To make the framework amenable to computation with models such as neural networks, we introduce surrogate-loss formulations and derive finite-sample guarantees for excess surrogate ambiguity risk. We formulate the resulting learning task as a constrained optimization problem and characterize its computational complexity in the convex setting. Finally, we evaluate our approach on various datasets and compare its performance with a competing method for this problem.

Primary area:
learning theory
Keywords:
CLASSIFICATION, ABSTENTION, MINIMAX

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_3j3YOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper extends the classical paper Lei (2014) "Classification with Confidence": under the ambiguity minimization problem subject to controlled positive and negative errors, the authors consider to deal with the surrogate risks of the ambiguity, positive, and negative errors, instead of Lei's plug-in classifiers. The paper progresses as follows: Section 3 discusses the generalization analysis of this problem under the 0-1 loss, Section 4 discusses its minimax lower bound, Section 5 discusses the surrogate generalization analysis, and Section 6 discusses SGD complexity. Finally, the proposed method is instantiated with a linear/MLP classifier with the hinge/squared-hinge losses, tested against Lei's approach, achieving lower ambiguity overall.

Critical strengths
  1. The paper is clearly written and well-organized. The paper structure "generalization analysis of 0-1 loss => lower bound => generalization analysis of surrogate loss => optimization" is very clear. Each section is concisely summarized with transparent mathematical backgrounds. Moreover, the lower bound proof is nicely illustrated in the main body.
  2. Well-motivated and natural extension of Lei (2014). While it is a bit surprising that nobody has extended Lei's plug-in classifier to the surrogate framework during the past decade, this work did it. This is not merely a straightforward extension but needs some discussions on the additive and multiplicative structures to aggregate positive and negative classifiers (in Definition 4), which is also nice.
Critical weaknesses
  1. Not very surprising techniques. The generalization analysis of the 0-1 loss and surrogate losses follows the standard approaches based on the Rademacher complexity. The analysis itself does not carry a lot of new techniques. The lower bound analysis may need a smart construction of the hard instance, which is not very immediate. The optimization guarantee is also standard; instead of dealing with heavy-tailed noises, bounded noises are supposed, which leads to the basic guarantee.
    • Note that I would not say this undermines the contributions of this paper; what is solved in this paper is already great enough.
  2. The classification error controls are sometimes violated in practice. By looking at Table 1, R0R_0 and R1R_1 are sometimes larger than the prespecified budgets 0.050.05, under for example, MLP/hinge/Add. and MLP/hinge/Prod. of Vertebral Column---actually, this is the case for Lei's approach as well, though. Can we have some discussions? Given Theorem 4, the violation could possibly come from the excess error ϵϕ\epsilon_\phi, which can be controlled in theory by using a large sample or controlling the Lipschitz continuity etc. Can any of these mitigate the constraint violation? Hopefully this point becomes another advantage over Lei's approach because we do not need the hypothesis space is well-specified.
Questions for authors

I don't have many questions. Just a few minor comments follow:

  • In L.132, I don't think the subscript jj is necessary for the candidate region CjC_j. The same applies to L.185, ϵj\epsilon_j.
  • In L.187, does "slack parameters ϵ0/2\epsilon_0/2 and ϵ1/2\epsilon_1/2" indicates ϵ0(n0,δ)\epsilon_0(n_0,\delta) and ϵ1(n1,δ)\epsilon_1(n_1,\delta), respectively?
  • In L.231, the spacing is strange at "... σ\sigma determines ,in each pair ..."
  • In L.263, should it be 1−δ1-\delta in the lower side of the inequality, instead of 1−δ01-\delta_0?
Reviewer_uGwBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies binary classification with abstention under separate class conditional error constraints. It establishes nearly matching upper and lower bounds on excess ambiguity risk in terms of VC dimension and sample size, then proposes additive and multiplicative surrogate losses for training score based models. Experiments on five real datasets and one Gaussian synthetic dataset compare the proposed methods with Lei (2014). My main concerns relate to how these experiments support the claimed practical improvement.

Critical strengths
  • The paper is clear written, and its main results are presented clearly.
  • The paper provides an interesting formal characterization of minimizing the abstention region under class conditional error constraints. The analysis follows the standard constrained ERM and VC dimension framework, while applying it to this specific problem.
Critical weaknesses

The baseline comparison does not isolate the benefit of the proposed training method.

Appendix H describes the Lei (2014) baseline as thresholding nonparametric estimates of conditional class probabilities, but does not sufficiently specify the estimator, its hyperparameters and tuning procedure, or how the thresholds are selected. The reported gain could therefore reflect the MLP’s greater suitability for these datasets rather than an advantage of the proposed constrained objective. A comparison using an MLP to estimate class probabilities, followed by Lei’s thresholding procedure, would help resolve this.

The experimental scope could be broader.

Additional benchmark datasets and synthetic distributions beyond the Gaussian setting would make it easier to judge whether the observed gains hold across different data structures.

The choice of configurations needs explanation.

All six datasets include the common MLP–hinge–additive and MLP–hinge–multiplicative comparison, which is useful. Linear models and squared hinge losses, however, appear only for selected datasets without a stated rationale. The authors should report the results for the full set of configurations they evaluated, or explain how the reported configurations were chosen.

One result is inconsistent across tables.

The Lei baseline’s R1R_1 on BCI is 0.0522 in the main paper’s Table 1 but 0.0252 in Appendix Table 4. The authors should verify and correct this value.

Positioning relative to closely related work.

The related work discussion omits Wang and Qiao (NeurIPS 2018), which studies essentially the same class specific coverage and ambiguity minimization problem using a directly trained, hinge based support vector method. It also provides statistical guarantees. As a result, the paper does not clearly establish which aspects of its surrogate formulation and practical algorithm are new relative to existing direct learning approaches.

These are minor comments

  • Lines 164–165: “... the statistical complexity of equation 1.”
  • p. 4, around line 209: “Let EζE_\zeta denote denote expectation with respect to the auxiliary random variables …”
  • p. 5, Fig. 1 caption, around line 228: “... the feasibility constraints, orce overlap between the two regions ...”
  • p. 8, around line 395: “, The problem can then be rewritten as follows:”
Questions for authors
  1. Why were linear models evaluated only on BCI, and squared hinge losses only on BCI and the synthetic dataset? Were other model–loss combinations evaluated but omitted?
  2. For the Lei baseline on BCI, R1R_1 is 0.0522 in Table 1 and 0.0252 in Appendix Table 4. Which value is correct, and does correcting it affect any comparison or conclusion?
  3. The synthetic study uses one Gaussian setting. Could you add distributions with different overlap or boundary structures, or explain which aspects of the empirical claim this setting is intended to test?
  4. What conditional probability estimator was used for the Lei (2014) baseline on each dataset? How were its hyperparameters and class specific thresholds selected, and what tuning budget was used?
  5. Could you compare your method with a plug-in implementation that uses a comparably sized MLP to estimate class probabilities, followed by Lei’s thresholding procedure? This would help establish whether the gain comes from the constrained training objective or from the choice of prediction model.
  6. How does the proposed method differ technically from Wang and Qiao (2018), particularly in the expressiveness of the decision regions, the surrogate risk guarantees, and the applicable assumptions? Could you include their method as an experimental baseline under the same data splits and class conditional error targets, or explain why such a comparison is inappropriate?
Reviewer_4UZKOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary
  • This paper studies the binary classification problem with abstention. In particular, the goal is to minimize abstention while ensuring bounded class-conditional errors.
  • Considers the distribution-free statistical complexity for binary classification with abstention with 0-1 loss and show the minimax rate upto some logarithmic factors.
  • Show matching upper and lower bounds on ERM for hypothesis classes that have a finite VC dimension.
  • Introduce a new surrogate loss function that they solve using a stochastic primal dual algorithm.
  • Evaluation on synthetic and read world datasets
Critical strengths
  • The paper provides a complete story with proving matching bounds for the standard 0-1 loss and then introducing a new surrogate loss that is more computable and optimizable. The proofs are well written and seem sound.
  • The experiments show a considerable improvement over the previous best knows results and back the theory developed in the paper
Critical weaknesses

See below.

Questions for authors
  • Why would a formulation that considers three classes instead of two, where the third class if the ambiguous region not work?
  • The experiments have a fixed α0\alpha_0 and α1\alpha_1. What happens for different values of these parameters? Would be nice to have results with different values of these parameters or a justification of why those values were chosen

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.