acceptodds
Under review as a conference paper at ICLR 2027

Towards Calibration for General Crammer-Singer Losses in Multi-Class Classification with Abstention

Abstract

The Crammer-Singer (CS) loss has been a standard multi-class extension of base binary surrogate losses. Despite its solid empirical performance, classical theory of loss functions proves that the CS loss is not classification-calibrated to the 0-1 loss, that is, the minimization of the surrogate risk of the CS loss does not necessarily lead to the minimization of the 0-1 risk. The pitfall of the CS loss is caused by low-confidence samples with their maximum class probability less than . This observation leads to the following question: is the CS loss calibrated when there are no low-confidence input samples? To this end, we consider the CS loss under multi-class classification *with abstention*, and in particular, the predictor-rejector framework, where a learner trains a class predictor as well as a rejector to abstain from making predictions for low-confidence samples. Under this setup, we show that general CS losses can be calibrated, verifying our hypothesis that the CS loss can be safely used even theoretically if all input samples are sufficiently confident. Theoretically, our calibration proof is interesting on its own right because it is applicable to broader losses composed of binary ones; the CS loss under classification with abstention has been considered previously, but the calibration property has been known only for polyhedral losses. Experiments on different datasets empirically validate the effectiveness of our calibrated general CS losses.

Primary area:
learning theory
Keywords:
Crammer-Singer loss, calibration, multi-class classification, abstention

Reviews

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

This paper proposes two families of (rejection) calibrated general Crammer-Singer losses for multi-class classification with abstention in the predictor-rejector setting, where the rejector decides which samples to abstain from (at a cost cc). The main contribution of this work is to derive analytically tractable necessary-sufficient conditions for calibration, that can be used to set the parameters of the calibrated CS loss functions to guarantee calibration. This work further derives excess risk bounds for certain cases of the proposed loss families that have at most linear excess risk rate. A generalisation bound is also proved based on the Rademacher complexities of the predictor and rejector. Four variants of the proposed loss functions are evaluated on five datasets (yeast, Imagenet, vehicle, CIFAR-10, and satimage) with respect to the abstention loss on the test set, where they are shown to be competitive with baselines.

Critical strengths
  • The results show how to modify any general Crammer-Singer loss for the predictor-rejector framework, and prove relatively interpretable necessary sufficient conditions for the modification to be calibrated.
  • The paper is reasonably self-contained, and notation is well-defined, allowing the reader to understand the main results successfully.
Critical weaknesses

The main weakness of the manuscript is its clarity. Important details and discussions are omitted in several places, making it hard to understand the significance and motivation of the key results. Moreover there are some ambiguities in the key definitions and results.

  1. The definition of the point-wise risk WW (Lines 154-161) is ambiguous, and it is not clear if WW takes scalar and vector inputs (r(x),g(x),η(x)r(x), g(x), \eta(x)), or functions as input (r,g,ηr, g, \eta). If WW is a function of r∈R,g∈RKr \in \mathbb{R}, g \in \mathbb{R}^K and parametrised by η∈ΔK\eta \in \Delta^K, this should be made explicit by defining W:R×RK×ΔK→RW : \mathbb{R} \times \mathbb{R}^K \times \Delta^K \to \mathbb{R}.
  2. The definition of rejection calibration (Lines 162-167) is ambiguous, since it does not mention for which xx the condition should hold (presumably for all xx). Similarly, Proposition 5.1 does not make it clear for which xx the inequalities should hold (presumably for all xx).
  3. The significance of Proposition 5.1 is unclear, beyond its use as a helper result to prove Theorems 5.3-5.5. Line 253 refers to Ni et al, which states that it is an "unnatural constraint" and that it is "hard to satisfy in the multi-class case". In what manner, is the constraint unnatural? The comment about it being hard to satisfy is confusing, since the condition is equivalent to rejection calibration, thus the comment seems to imply that rejection calibration is hard in the multi-class case. However, this work exactly proves the opposite.
  4. Similarly, Proposition 5.2 provides limited value to the reader since it is followed by no discussion beyond stating that it underpins the proofs of Theorems 5.3-5.5. In particular, it is hard to judge what or how much progress Proposition 5.2 makes towards the final goal of characterising calibration in this setting.
  5. Theorem 5.3-5.5 derive necessary and sufficient conditions for MCS and ACS losses. However, the central claim of the paper is that "general CS losses can be calibrated" (abstract, line 53). To meet this claim, additional discussion needs to be made about how to choose or construct the MCS and ACS losses (i.e. choose ψ,ψ1,ψ2\psi,\psi_1, \psi_2) so that the conditions in Theorem 5.3-5.5 are satisfied, beyond simply asserting that this can be done, as in lines 308-310.
  6. Indeed, the examples presented in the empirical validation (ACS-Hinge, ACS-Logistic, MCS-Hinge, MCS-Logistic) are never explicitly stated in the main text. Presumably, the parameters of these examples are set to achieve calibration using Theorems 5.3-5.5 (this is briefly touched upon in Appendix E, lines 2682-2690). A complete worked-out example on how to do this would be beneficial.
  7. There are some inconsistencies in the claims. Line 320 states that the excess risk bounds are the main contribution. This is not consistent with the abstract (ignores the excess risk bounds), and introduction (positions it as one of 3 contributions). The claim in the abstract : "our calibration proof is interesting in its own right because it is applicable to broader losses composed of binary ones" is not addressed in the main text, i.e. "broader losses" are not addressed and no dedicated proof sketch is provided.

There are some ambiguities in the proofs of Theorem 5.3 and 5.4 that should be clarified. Specifically, they pertain to the use of Proposition 5.1. For example, in the proof of Theorem 5.3, the goal is to derive the equivalence between the condition H1−cψ1′(0)+ψ2′(0)=0H_{1-c} \psi_1'(0) + \psi_2'(0)=0 and the inequalities in Proposition 5.1. This requires proving both directions. The proof is clear upto the step proving that inf⁡sη=sup⁡sη=Hη⋆ψ1′(0)+ψ2′(0)\inf s_{\eta} = \sup s_{\eta} = H_{\eta^\star} \psi_1'(0) + \psi_2'(0) (it follows from proving that the subdifferential is a singleton). However, the next step, i.e. Equation 35, is a series of equalities. It is not clear why those equalities should hold, or why the equalities imply the equivalence stated above.

Similarly, the proof of Theorem 5.4 attempts to prove the equivalence between the conditions in Theorem 5.4 and Proposition 5.1 at equation 38, which is again a series of equalities. Again, it is not obvious to me why equation 38 implies the equivalence of the two sets of conditions (or why it holds).

I have the following concern about the experimental setup and results. Line 427-428 states that "we choose cc around the best misclassification error with no abstention" and Lines 2678-2682 clarify that setting cc in this way encourages a "reasonable number of samples to be abstained". However, there is a big gap in the rejection ratios of the various predictor-rejector methods, for example, from 38% to 89% in Table 3. Indeed, in Table 5, ACS-Logistic rejects nearly all the samples (99.92% rejection ratio). This indicates that the hyperparameter cc has a disparate effect on different variants of the CS loss during training. Therefore, setting cc to one global value for one dataset may not be a fair comparison. This raises a number of questions :

  1. Should the abstention cost during training be detangled from the abstention cost during evaluation, and the former tuned for each method based on a validation loss?
  2. What threshold (on the maximum class score) is used for the confidence-based baselines? Should this threshold also be tuned for a given value of cc to ensure a fair comparison?
  3. Figure 4 shows that the abstention loss monotonically increases with cc on the CIFAR-10 dataset. Can you give an argument, or intuition, why this is the case?
  4. Continuing the discussion on the validity of evaluating the methods on one value of cc : can you compare all predictor-rejector methods with respect to the three metrics across values of cc, like Figure 4, at least on one dataset?

The following are minor issues and suggestions :

  • The exact training procedure of the predictor and rejector pair is not detailed in the main text, or in the appendix.
  • Figure 4 shows a non-monotonic trend in the rejection ratio with respect to cc on CIFAR-10. Why is it not decreasing, i.e. why does increasing cc not lead to fewer rejections? (This could potentially be explained by the generalization gap between training and test error).
  • Figure 1 is confusing, since it mixes the comparison of the method and baseline on various datasets, and the trend of abstention loss on the test set vs the abstention cost (which also affects training for the proposed method). The latter trend appears to be independent of the dataset (see Figure 4). Consider disentangling the two points, and focusing only on one for this illustration. Also consider that the abstention cost has not been introduced at that point in the text, limiting the value of Figure 1.
  • Consider making the relationship between hηh_{\eta} and HηH_{\eta} explicit in Section 5.
  • Line 1665-1666 : The application of Proposition 5.2 to the given expression for WMCSW_{MCS} is not immediate, consider making the transformation from hηh_\eta to HηH_{\eta} explicit.
  • Theorems 5.3-5.5, 6.2, 6.3 are followed by short descriptions of the proofs. However, they provide limited value, for example, Line 281-282 says that the non-increasing property of HηH_{\eta} is used to make the proof. It is not explained why this is interesting, or indeed, how to interpret the construction HηH_{\eta} itself. Similarly, the comment following Theorem 5.4 saying that "a case-by-case analysis and Prop. 5.4 is needed" is of limited value without context about the cases that are considered. Consider omitting these comments altogether, and instead replacing them with a discussion of the result and its significance (e.g. like in line 353-357 interpreting Theorem 6.3), or expanding these comments into a dedicated proof sketch.
  • The definition of excess risk is made at the end of Section 3, and is out of place with the rest of the section, which deals with calibration. Consider moving it to the end of Section 2.
  • Line 474-477 : the recommendation of choosing logistic variants when cc is small is not justified well. Only a "speculation" is provided that logistic variants are underconfident in this setting. Why are the logistic variants underconfident, and how does this affect the final goal of calibration?
  • Section 3 introduces and defines various notions of calibration which makes the overall presentation confusing. Consider beginning at the definition of the pointwise risk and only defining rejection calibration, since this work only pertains to that. Other definitions of calibration can be discussed in a remark.
  • The authors state (line 151-152) that rejection-calibration is necessary for calibration of (r,g) (defined in line 141-143), while that of gg is not. While a reference is provided, consider justifying both statements, i.e. (a) (r,g) calibration implies r-calibration, and (b) (r,g) calibration does not imply g-calibration, directly in the text.
  • A similar notion of calibration in the predictor-rejector setting is the analogue of (r,g) calibration, where LL is calibrated iff for every minimizer (r′,g′)(r',g') of RR, R0−1−c(r′,g′)=R0−1−c(r⋆,g⋆)R_{0-1-c}(r',g') = R_{0-1-c}(r^\star, g^\star) where r⋆r^\star and g⋆g^\star are the Bayes optimal pair for R0−1−cR_{0-1-c}, as defined in lines 136-139. How does this differ from rejection calibration, and why does this work focus on the latter?
  • Can you include a toy experiment, where the optimal risks and/or Bayes predictor rejector pair can be analytically computed? This would give a direct estimate of the calibration error.
  • Line 256-257 is confusing, it states that "We will reveal that our losses satisfy this constraint" (are the authors referring to the inequalities in Prop. 5.1?) , "that is, W(r,gη†,η)W(r,g_{\eta}^{\dagger}, \eta) only depends on η⋆\eta^\star" (why is it important that WW only depends on η⋆\eta^\star?)
  • Proposition 5.1 should explicitly state that the subdifferential of WW with respect to rr at fixed gg is considered.
  • Typo : line 178 : "predictor-rejector".
  • Theorem 7.2 : Mψ1M_{\psi_1} should be independent of rr.
  • Line 239 : The authors probably mean "non-differentiable" instead of "indifferentiable".
  • Line 422 : Typo : "Thus we also (MISSING) with".
Questions for authors

See weaknesses.

5 comments
AuthorsOpenReview ↗

Responses to Reviewer wsLF

We thank the reviewer for the detailed review and suggestions. Regarding the issues pointed out, we would like to add the following information:

  • [W1] Definition of the point-wise risk WW: Pointwise risk W:R×RK→RW: \mathbb{R}\times\mathbb{R}^K\rightarrow\mathbb{R} takes scalar and vector inputs and is parametrized by η\boldsymbol{\eta}. In lines 155-162, we defined WW in an informal way, which is standard (also see [Ni+2019, Section 2.1]). We will clarify this definition in a future version.
  • [W2] Definition of rejection calibration and Proposition 5.1: We used ηy\eta_y to denote ηy(x)\eta_y(\boldsymbol{x}) for brevity, as clarified in lines 161-162; thus, in the definition of rejection calibration and Proposition 5.1, the statement "for all η∈ΔK\boldsymbol{\eta}\in \Delta_K such that η\*≠1−c\eta^\*\neq 1 - c, where η\*=max⁡yηy\eta^\* = \max_y\eta_y" naturally covers the cases for all x\boldsymbol{x}.
  • [W3] Proposition 5.1: We admit that the word "unnatural" is a bit imprecise, and the meaning we want to express is that W(r,gη†;η)W(r, \boldsymbol{g}^\dagger_{\boldsymbol{\eta}}; \boldsymbol{\eta}) only depends on η∗\eta^*, rather than the class probabilities of other classes (violation of this constraint is also discussed as a negative result in [Mao+2024a, Theorem 1]). Indeed, the rejection calibration is hard in the multi-class case because of this constraint. However, we addressed this difficulty via the special property of Crammer-Singer (CS) loss (as mentioned in lines 256-257), which highlights the contribution of our work.
  • [W4] Discussions about Proposition 5.2: The specific display about how Proposition 5.2 be applied in the proof for Theorem 5.3-5.5 can be found in Appendix D.1-D.3. The key here is that by Proposition 5.2, we can get the form of WMCS(r,gη†;η)W_{\mathrm{MCS}}(r, \boldsymbol{g}^{\dagger}_{\boldsymbol{\eta}};\boldsymbol{\eta}) and WACS(r,gη†;η)W_{\mathrm{ACS}}(r, \boldsymbol{g}^{\dagger}_{\boldsymbol{\eta}};\boldsymbol{\eta}), and then analysis the derivatives of them respect to rr. We admit that adding some proof sketches in the main body is useful and will add them in a future version if space permits.
  • [W5] Choices of ψ,ψ1,ψ2\psi, \psi_1, \psi_2 to satisfy conditions in Theorems 5.3-5.5: The specific choices of ψ,ψ1,ψ2\psi, \psi_1, \psi_2 in our experiments can be found in Table 1 (note that ψ1\psi_1 in Table 1 should be modified to \max\left\\{0, 1 + r\right\\} and log⁡(1+exp⁡(−r))\log (1 + \exp(-r))). By tuning the hyperparameter α\alpha, we can easily satisfy the conditions in Theorems 5.3-5.5 with the above choices of ψ,ψ1,ψ2\psi, \psi_1, \psi_2. Since the enumeration for the detailed value of α\alpha is tedious because it can be directly obtained from Theorems 5.3-5.5 given specific choices of ψ,ψ1,ψ2\psi, \psi_1, \psi_2, the enumeration for the detailed value of α\alpha is placed in Appendix E.
  • [W6] Examples to achieve calibration: As mentioned above, all of the choices of ψ,ψ1,ψ2\psi, \psi_1, \psi_2 in Table 1 can satisfy the conditions in Theorems 5.3-5.5 by tuning the hyperparameter α\alpha. Thus, Table 1 is sufficient as a worked example for calibration, and we will point this out explicitly in a future version.
  • [W7] Inconsistencies in the claim: The abstract and introduction are written mainly from the viewpoint of calibration because whether a loss can be calibrated or not has been a major interest in this area. It is generally more challenging to obtain the excess risk bound, which is a stronger result than calibration (as mentioned in [Mao+2024a, Section 4.1]). Thus, this is elaborated as the main result covering calibration. "broader losses" in the abstract refers to a wider range of losses that includes both polyhedral losses and non-polyhedral losses (which is mentioned in lines 26-28, just the following sentence of the statement with "broader losses" in the abstract). Our proofs for Theorems 5.3-5.5 have covered various cases ranging from polyhedral losses to non-polyhedral losses.
AuthorsOpenReview ↗

Responses to Reviewer wsLF

  • Ambiguities in the proofs of Theorems 5.3 and 5.4: Indeed, in the proof of Theorem 5.3, the goal is to derive the equivalence between the condition H1−cψ1′(0)+ψ2′(0)=0H_{1-c}\psi^{\prime}_1(0) + \psi_2^{\prime}(0) = 0 and the inequalities in Proposition 5.1. In the proof, we are directly proving the equivalence rather than proving two directions separately. The equalities in (35) come from an equivalent transformation of the inequalities in the specific context. This equivalent transformation holds because, in the context where HηH_{\eta} is non-increasing and specific forms of inf⁡sη\inf s_{\boldsymbol{\eta}} and sup⁡sη\sup s_{\boldsymbol{\eta}} are given, the inequalities in Proposition 5.1 can hold only when equality is achieved at the point η\boldsymbol{\eta} such that η∗=1−c\eta^* = 1 - c, and the value for which the equality is achieved is surely H1−cψ1′(0)+ψ2′(0)=0H_{1-c}\psi^{\prime}_1(0) + \psi_2^{\prime}(0) = 0. Then, under the same context, the equalities in (35) can be further simplified to H1−cψ1′(0)+ψ2′(0)=0H_{1-c}\psi^{\prime}_1(0) + \psi_2^{\prime}(0) = 0. In the proof of Theorem 5.4, the equivalent transformation from inequalities in Proposition 5.1 to equalities in (38), and then to ψ′(0)=−2c\psi^{\prime}(0) = -2c, is in a similar way.
  • [Q1] Should the abstention cost cc be detangled during training from that during evaluation: Since our calibration guarantee requires ψ\psi or ψ1\psi_1, ψ2\psi_2 to satisfy some equalities about abstention cc which is used in evaluation (as shown in Theorem 5.3-5.5), fixing the abstention cost cc in training to be the same as that value is reasonable. Otherwise, tuning the abstention cost cc heuristically during training may lead to the calibration guarantee not holding.
  • [Q2] What threshold is used for the confidence-based baselines: Theoretically grounded τ\tau are considered in the submitted version. The updated results with tuned τ\tau can be found in Tables 1-2 in our reply to reviewer 5hds. For both [Ramaswamy+2018] (CS-hinge) and [Ramaswamy+2018] (BEP), the tuned threshold τ\tau is 0.7 on the vehicle dataset and 0.8 on Imagenette.
  • [Q3] Why does the abstention loss monotonically increase with cc in Figure 4: A larger cc means that it is harder for the learner to avoid misclassification on low-confidence samples via abstention, thus tending to have a larger abstention loss.
  • [Q4] Can the methods be compared across values of cc on one dataset: cc is not a hyperparameter, but an environment setting. A reasonable value of cc is around the best misclassification error with no abstention. We will add comparison experiments on different cc in a future version.
  • Training procedure of the predictor and rejector: The formulation of LL is given in Section 4.2, and details like the optimization method are given in Appendix E as mentioned in line 429. We believe that sufficient information is given in Appendix E, but please let us know if some points should be detailed further.
  • Why the trend in Figure 4 is not monotonic: Although the trend in Figure 4 is not absolutely monotonic, the rejection ratio generally tends to decrease with the increasing abstention cost cc. Note that the rejection ratio is affected not only by the rejection ratio, but also by the training condition of the predictor (note that the predictor and the rejector are trained jointly). Thus, when the abstention cost increases, if the predictor is not trained sufficiently due to an insufficient number of samples, the rejection ratio can also increase within a small range.
  • Figure 1: For a given dataset, a reasonable value of cc on this dataset is around the best misclassification error with no abstention on this dataset. Thus, when displaying Figure 1, we actually implicitly assumed that cc is naturally determined from the dataset and meant to focus on comparing different methods on various datasets. The abstention cost indeed has not been introduced formally at that point in the text, and we will move the introduction of cc to an earlier position in a future version.
  • hηh_{\eta} and HηH_{\eta} in Section 5: hηh_{\eta} and HηH_{\eta} are strongly related but not the same quantity. hηh_{\eta} is a more general quantity with rr as input, and HH does not have rr as input. See our reply below for the quantitative relationship between hηh_{\eta} and HηH_{\eta}.
AuthorsOpenReview ↗

Responses to Reviewer wsLF

  • Application of Proposition 5.2 to the given expression for WMCSW_{\mathrm{MCS}}: By Proposition 5.2, WMCSW_{\mathrm{MCS}} can be obtained by the following transformation: \begin{aligned} W_{\mathrm{MCS}}(r, \boldsymbol{g}_{\boldsymbol{\eta}}^{\dagger}; \boldsymbol{\eta}) &= h_{\eta^*}(r)\\ &= \min_{\Delta\geqslant 0}\left\{\eta^*\Phi(\Delta, r) + (1 - \eta^*)\Phi(-\Delta, r)\right\}\\ &= \min_{\Delta\geqslant 0}\left\{\eta^*\phi(\Delta)\psi_1(r) + (1 - \eta^*)\phi(-\Delta)\psi_1(r) + \psi_2(r)\right\}\\ &= \min_{\Delta\geqslant 0}\left\{\eta^*\phi(\Delta) + (1 - \eta^*)\phi(-\Delta)\right\}\psi_1(r)+ \psi_2(r)\\ &= H_{\eta^*}\psi_1(r) + \psi_2(r). \end{aligned} We would like to add a related statement in a future version to make the transform from hη(r)h_{\eta}(r) to HηH_{\eta} explicit.
  • Descriptions for the proofs of Theorems 5.3-5.5, 6.2, 6.3: During the proof of 5.3, The non-increasing of HηH_{\eta} is important because, with this property, we can reduce the equalities in Proposition 5.1 to a calibration condition in equality. During the proof of Theorem 6.2, the different cases of η\*\eta^\* and rr are needed because the infimum of W0-1-cW_{0\text{-}1\text{-}c}, WMCSW_{\mathrm{MCS}}, and WMCS\*W^\*_{\mathrm{MCS}} depends on them. Besides, in Remarks 6.2 and 6.3, we state the significance of Theorems 6.2 and 6.3. We would like to expand the short descriptions of the proofs of Theorems 5.3-5.5, 6.2, and 6.3 in the submitted version into a dedicated proof sketch like the one above in a future version if space permits.
  • Definition of excess risk bound: The definition of the excess risk bound is placed in Section 3 because it has a strong relationship with calibration (as mentioned in our reply to [W7]). We would like to add the statement about the relationship between them at the end of Section 3 to make the connection more fluent in a future version.
  • Reason for lower confidence of logistic variants: As mentioned in lines 2722-2733, the logistic variants are speculated to be more conservative in accepting low-confidence samples. The detailed cause analysis may be an interesting future direction. All of our losses in experiments are calibrated, and the lower confidence of logistic variants does not affect the final goal of calibration because the calibration is under the assumption of infinite samples. However, in a practical scenario with finite samples, there might exist a lower confidence phenomenon in logistic variants.
  • Various notations of calibration: we also think the reviewer's suggestion is reasonable, while the notations of calibration of (r,g)(r, \boldsymbol{g}) and calibration of rr and gg separately can serve as a foundation to introduce the notation of rejection-calibration of LL. The motivation to introduce the rejection-calibration comes from the fact that, for the calibration of (r,g)(r, \boldsymbol{g}), the calibration of rr is necessary while that of g\boldsymbol{g} is not. Besides, the definition of rejection-calibration of LL actually can be interpreted as the rejection-calibration of r†r^\dagger (where r†r^\dagger is the minimizer of the corresponding pointwise risk).
  • Justification for the necessary condition for calibration of (r,g)(r, \boldsymbol{g}): Related justification can be found at the end of [Ramaswamy+2018, Section 1.2], where they take SVM as an example: SVM is consistent for standard binary classification, but it avoids consistent estimation of the conditional probability (calibration for the predictor). Since it is a generally accepted conclusion, we will add discussions in the appendix and add a reference to [Ramaswamy+2018, Section 1.2] considering the space limitation.
  • Calibration condition for LL: Note that, the calibration for LL does not necessarily need the calibration of (r′.g′)(r^\prime. \boldsymbol{g}^\prime), i.e., R0-1-c(r′,g′)=R0-1-c(r\*,g\*)R_{0\text{-}1\text{-}c}(r^\prime, \boldsymbol{g}^\prime) = R_{0\text{-}1\text{-}c}(r^\*, \boldsymbol{g}^\*), while the calibration of r′r^{\prime} is enough (where r′,g′r^{\prime}, \boldsymbol{g}^{\prime} are minimizers for RR, in reviewer's notation). The difference is that rejection calibration is a more streamlined necessary condition. Besides, consider that pointwise risk WW is easier to analyze than RR; in this work we focus on rejection calibration for r†r^{\dagger} (where r†r^{\dagger} is a minimizer for pointwise risk WW).
Reviewer_dJjGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the calibration of CS (Crammer–Singer) losses for classification with rejection. By adopting a predictor–rejector framework, where prediction and rejection are handled by separate models, the paper extends calibration guarantees to a broader class of binary losses, including smooth, non-polyhedral losses that are better suited for gradient-based optimization. The paper has three main contributions:

  • Broader calibration guarantees
  • First result under the predictor-rejector framework to show that the surrogate risk controls the target excess risk in a linear fashion for class of loss functions. They do this by defining two new forms of calibrated losses - multiplicative CS and additive CS
  • Experiments on various datasets to back their theoretical results
Critical strengths

-Very interesting problem and results. The paper develops a framework for studying CS losses calibration with abstention which was not done earlier.

  • The paper also provides a very useful reduction of multiclass conditional surrogate risk to a simpler optimization problem depending only on the maximum class probability. The framework therefore offers methodological value in addition to the individual theoretical guarantees established in the paper.
  • Unlike previous predictor–rejector approaches that rely on non-convex surrogate losses, the proposed ACS loss is jointly convex in the predictor and rejector scores, while the MCS loss is biconvex. These properties provide a potentially more tractable optimization landscape and make the framework attractive for practical learning algorithms.
Critical weaknesses
  • The performance increase is limited to 10 classes. The paper does not mention how their framework performs when the number of classes increase a lot
  • Extremely high rejection rates make it difficult to assess how useful the resulting classifier is. ACS hinge in particular has a very high rejection rate.
  • The experimental gains are fairly small and inconsistent. Even on the best performing dataset, ACS-logistic shows a gain of ~2%. On Imagenette, ACS-hinge shows an improvement of 0.95% while the MCS variants do not show any improvement over the previous best known by Mao et al.
Questions for authors

Couple of typos:

  • Line 69-70: Comparatively is misspelled
  • Line 78-79: Predictor is misspelled
  • Line 146-147: Separately is misspelled
  • Line 216-217: e missing in those

In section 4.2, the authors mention ψ1\psi_1 to be non-decreasing for LMCSL_{MCS} and LhingeL_{hinge}, but that is not the case in Table 1 for the choice of ψ1\psi_1 for MCS-Hinge and MCS-Logistic. Could the authors clarify the reasoning behind this?

1 comment
AuthorsOpenReview ↗

Responses to Reviewer dJjG

We thank the reviewer for the helpful review and for pointing out the weakness of our work. Regarding the concerns mentioned, we would like to make the following statements:

  • Performance when the number of classes increases a lot: As displayed in [Zhu+2023, Tables 7, 9, 11, 13, 15], the performance of CS losses for scenarios with a large number of classes (e.g., CIFAR-100) would be poor. This is due to the inherent attributes of CS loss; that is, it only considers the output score of the label class and the highest one except the label class. Thus, to provide a reasonable practical scenario for CS losses, datasets with a moderate number of classes are adopted to validate our losses (as mentioned in lines 411-415).
  • High rejection ratios: As mentioned in lines 464-466, the high rejection ratios do not necessarily mean that the related methods are overly rejecting, but rather might imply that others were overconfident. The high rejection ratios are under the current cc, which is part of a problem instance, and we choose the current value just for comparison so that most methods give a rejection ratio not equal to 0%0\% or 100%100\%. For rejection cc larger than the current one, the rejection ratio of the proposed method gradually decreases.
  • Experimental gains and consistency: We admit that our methods are not so dominant over [Mao+2024], but via these results we can still validate the effectiveness of our calibrated general CS losses and show their advantages over calibrated CS losses in the scope of polyhedral losses. Since the ACS loss is always convex while the MCS loss is not (although it is bi-convex), the worse performance of the MCS loss than the ACS loss on Imagenette is reasonable. Thus, the results in the experiments can be explained consistently by considering the difference between the MCS and ACS loss.
  • Typos: We will correct the typos in a future version.
  • ψ1\psi_1 in Table 1: Indeed the ψ1\psi_1 in Table 1 should be modified to \max\left\\{0, 1 + r\right\\} and log⁡(1+exp⁡(−r))\log (1 + \exp(-r)). We will modify it in a future version.
Reviewer_7WTgOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

In this paper, the authors consider multi-class classification with the Crammer–Singer (CS) loss. It is known that the CS loss is not calibrated with respect to the 0-1 loss, and the previous positive result was only applicable to the hinge loss. The authors propose a new analysis that extends to other smooth losses.

Since the key problem lies in low-confidence samples, where η∗<1/2\eta^* < 1/2, the authors adopt the predictor-rejector framework, in which a predictor is trained to make predictions and a rejector decides whether to abstain on low-confidence samples.

The authors propose two extensions of the CS loss within the predictor-rejector framework: one that includes the abstention term additively (ACS) and another that includes it multiplicatively (MCS). As their main contributions, they provide:

  • calibration conditions for multi-class classification in the predictor-rejector framework, for ACS and MCS with logistic, exponential and hinge losses
  • excess risk bounds
  • generalization error bounds.

The paper concludes with an experimental section.

Critical strengths

Overall, the paper is interesting and well explained. Provides interesting theoretical results.

Critical weaknesses

This is not the first convex surrogate loss for multi-class classification in the predictor-rejector framework. The authors argue that previous ones are too complicated or non-convex, but this argument is not well developed, either theoretically or empirically.

The assumptions in the generalization error bounds are too strong.

The experimental section is not sufficiently developed:

  • It is unclear whether both rr and gg are modelled with the network described in the appendix, or only gg.
  • Experiments on synthetic data (with fixed XX, η\eta, etc.) could be very illustrative here.
  • Results are reported for a single run.
  • The proposed methods are not clearly better than Mao et al. (2024a) experimentally.
  • The abstention cost cc should be varied or tuned.

There are some typos, for example in line 216.

Questions for authors
  • What exactly is the implementation of rr and gg? Does the architecture described in the appendix correspond only to gg, or to both?
  • What is the specific contribution with respect to Mao et al. (2024a) and Ramaswamy et al. (2018)?
2 comments
AuthorsOpenReview ↗

Responses to reviewer 7WTg

We thank the reviewer for kindly reviewing and recognizing the value of our work. Regarding the concerns mentioned, we provide the following explanation:

  • Complicate nonconvex losses in [Mao+2024a]: We admit that "complicated" here is a bit imprecise; the meaning we want to convey is that [Mao+2024a]'s losses are nonconvex and lead to an unfavorable optimization landscape. The single-stage surrogate losses LL proposed by [Mao+2024a] are in the following form: \begin{align*} \begin{aligned} L(r, \boldsymbol{g};\boldsymbol{x}, y) = \ell(\boldsymbol{g}, \boldsymbol{x}, y)\Phi(-\alpha r(\boldsymbol{x})) + \Psi(c)\Phi(\beta r(\boldsymbol{x})), \end{aligned} \end{align*} where Ψ\Psi is a non-decreasing function, Φ\Phi is a non-increasing function upper bounding t→It⩽0t\rightarrow\mathbb{I}_{t\leqslant0} and α,β\alpha, \beta are positive constants, and ℓ\ell has the following three choices for satisfying theoretical guarantee:

    (i) the mean absolute loss: ℓmae(g;x,y)=1−exp⁡(gy(x))∑y′∈Yexp⁡(gy′(x))\ell_{\mathrm{mae}}(\boldsymbol{g}; \boldsymbol{x}, y) = 1 - \frac{\exp(g_y(\boldsymbol{x}))}{\sum_{y^{\prime}\in \mathcal{Y}}\exp(g_{y^{\prime}}(\boldsymbol{x}))};

    (ii) the constraint ρ\rho-hinge loss: ℓρ−hinge(g;x,y)=∑y′≠yΦρ−hinge(−gy′(x))\ell_{\rho-{\mathrm{hinge}}}(\boldsymbol{g}; \boldsymbol{x}, y) = \sum_{y^{\prime}\neq y}\Phi_{\rho-\mathrm{hinge}}(-g_{y^{\prime}}(\boldsymbol{x})), where ρ>0\rho > 0, \Phi_\{\rho-\mathrm{hinge}\}(t) = \max\left\\{0, 1 - \frac{t}{\rho}\right\\} is the ρ\rho-hinge loss and g\boldsymbol{g} satisfies ∑y′∈Ygy(x)=0\sum_{y^{\prime}\in \mathcal{Y}}g_y(\boldsymbol{x}) = 0;

    (iii) the ρ\rho-Margin loss: ℓρ(g;x,y)=Φρ(ρg(x,y))\ell_{\rho}(\boldsymbol{g}; \boldsymbol{x}, y) = \Phi_{\rho}(\rho_{\boldsymbol{g}}(\boldsymbol{x}, y)), where ρg(x,y)=gy(x)−max⁡y′≠ygy′(x)\rho_{\boldsymbol{g}}(\boldsymbol{x}, y) = g_y(\boldsymbol{x}) - \max_{y^{\prime}\neq y}g_{y^{\prime}}(\boldsymbol{x}) is the confidence margin, \Phi_{\rho}(t) = \min\left\\{\max\left\\{0, 1 - \frac{t}{\rho}\right\\}, 1\right\\} is the ρ\rho-margin loss, and ρ>0\rho > 0.

    All three of the above choices of ℓ\ell are nonconvex. Besides, their two-stage surrogate loss is also nonconvex.

  • Assumptions for generalization bounds: Our assumptions are standard, and similar ones can be found in [Ni+2019, Proposition 9]. Maybe they are a bit strong, while generalization bounds are not the main contribution of this paper, and are mainly used to support the validity of the proposed losses (as mentioned in lines 361-363).

  • Model of rr and g\boldsymbol{g}: Indeed both rr and g\boldsymbol{g} are modeled with the network detailed in Appendix E. We will add information to explicitly state the connection between r,gr, \boldsymbol{g} and the network in a future version.

  • Synthetic data: We also think a synthetic dataset is useful for understanding learning with abstention intuitively, and we add related experiments. Assume the number of classes K=10K=10, feature dimension d=10d=10, and number of samples n=10000n=10000. Then we generate a synthetic dataset in a way similar to [Ni+2019, Appendix C.1] and [Ramaswamy+2018, Section 7.1]:

    • Randomly sample KK-dimensional vectors μ1,⋯ ,μK∈Rd\boldsymbol{\mu}_1,\cdots,\boldsymbol{\mu}_{K}\in \mathbb{R}^{d} from N(0,Id)\mathcal{N}(\boldsymbol{0}, \textbf{I}_d), which correspond to KK classes.

    • Each sample (x,y)(\boldsymbol{x}, y) in sampled from p(y)p(x∣y)p(y)p(\boldsymbol{x}\mid y), where p(y)p(y) is a uniform distribution p(y)=1Kp(y) = \frac{1}{K}, p(x∣y)p(\boldsymbol{x}\mid y) is a Gaussian distribution N(μy,Id)\mathcal{N}(\boldsymbol{\mu}_y, \textbf{I}_d), and Id\textbf{I}_d is a d×dd\times d identity matrix.

    For the synthetic dataset, we set c=0.2c = 0.2. Then we call class samples satisfying max⁡y′p(y′∣x)<1−c\max_{y^{\prime}} p(y^{\prime}\mid \boldsymbol{x}) < 1 - c "low confidence samples". By $W_{\mathrm{0}\text{-}{1}\text{-}c}^* = 1 - \max\left\{\max_{y^{\prime}}p(y^{\prime}\mid \boldsymbol{x}), 1 - c\right\} $ (see lines 1608-1616), after computation on the dataset we have the Bayes-optimal pointwise risk W0-1-c∗=0.1090W_{\mathrm{0}\text{-}{1}\text{-}c}^* = 0.1090. We define rejection precision A = \frac{\\{\\# \mathrm{low\text{ }confidence\text{ }samples\text{ }rejected}\\}}{\\{\\# \mathrm{samples \text{ }rejected}\\}}. On the synthetic dataset, the performance of CE, CS, and our methods, including rejection accuracy, is shown in Table 1. As shown in Table 1, our method shows rejection precision A>50%A > 50\%, which means that our method obtains effective rejection. Besides, our ACS hinge loss achieves both lower abstention loss and higher rejection precision than other compared methods, which further validates the effectiveness of our method.

AuthorsOpenReview ↗

Responses to reviewer 7WTg

Table 1: Performance of CE, CS, and our method on the synthetic dataset.

MethodRejection ratioMisclassification errorAbstention loss
CE0.00%0.2050--
CS0.00%0.2335--
[Mao+2024a]54.80%0.158155.47%
[Ramaswamy+2018] (CS-hinge)100.00%0.200038.35%
[Ramaswamy+2018] (BEP)73.85%0.152751.93%
Ours (MCS-hinge)60.35%0.150754.60%
Ours (ACS-logistic)73.85%0.167268.90%
Ours (ACS-hinge)65.35%0.151765.35%
Ours (ACS-logistic)31.30%0.162169.33%
  • Times for running: Indeed, results for a single run are reported, considering that our method itself does not involve so much randomness and it would take too much time (especially considering the number of datasets). In experimental parts, randomness mainly comes from data splitting, model weight initialization (and newly added synthetic experiments as a reply to reviewer 7WTg). We will update the results by running multiple times in a future version.

  • Comparing with [Mao+2024]: We admit that our methods are not so dominant over [Mao+2024]. However, our main aim for experiments is to validate the effectiveness of our calibrated general CS losses and show their advantages over calibrated CS losses in the scope of polyhedral losses (which is mentioned in lines 418-425). Our experimental results can sufficiently achieve the above aims.

  • Abstention cost cc: As mentioned in lines 426-428, the abstention cost cc is not a hyperparameter, but an environment setting. cc is given externally as an actual cost for making an abstention and is not a tunable parameter. When running comparison experiments, results for too small or large cc are not very meaningful. A reasonable value of cc for comparison is around the best misclassification error with no abstention to moderately predict and reject, so that most methods give a rejection ratio not equal to 0%0\% or 100%100\%.

  • Typos: Indeed, "thos" in line 216 should be modified to "those". We will fix the typos in a future version.

  • Specific contribution with respect to [Mao+2024a] and [Ramaswamy+2018]: Compared with [Mao+2024a], our ACS loss is always convex jointly in (g,r)( \boldsymbol{g}, r) (as mentioned in lines 228-230), while the losses proposed in [Mao+2024a] are non-convex. Compared with [Ramaswamy+2018] (CS) and [Ramaswamy+2018] (BEP), our losses include the smooth non-polyhedral cases, while both of them are non-smooth polyhedral.

Reviewer_5hdsOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper studies calibration of surrogates w.r.t. the abstain-loss in K-class classification, where the classifier has an option of abstaining with a cost of c. In particular, it use the predictor rejector framework, where the algorithm ends up learning K+1 functions, consisting of K-score functions, one for each class, and a rejector function. The final prediction gives the argmax over scores if the rejector is positive and abstains if the rejector is negative. The paper studies the calibration of Crammer-Singer based surrogate that penalise based on how much the score of the true class is lesser than the max non-true class score function. The paper makes theoretical statements on how these surrogates can be calibrated to the abstain loss. It constructs a few such surrogates and demonstrates its superior performance in the abstain loss on some datasets.

Critical strengths

The problem is well defined, and the Theorems 5.3 and 5.4 are well rounded clear to understand theorems.

Critical weaknesses

It is not clear what extra these surrogates bring over already existing surrogates theoretcally. For example confidence based CS loss is already abstain-calibrated what extra technical property does the new surrogates have? Empirical outperformance on a small number of datasets is interesting, but why do these outperform? All the surrogates in the experiments are calibrated with the abstain-loss. If at all there is a systematic reason for the outperformance of ACS and MCS losses, it has to be something else other than calibration? What is it, and why is it so? The paper makes no claims at all on this.

The excess risk bounds section is a special case of previously known results on strongly proper surrogate losses and calibration. (where essentially all "strongly convex proper composite losses" like the exp and logistic can be shown to have O(sqrt(t)) excess risk bound, if they are calibrated). Several papers have discovered this in different forms, (e.g. Composite Multiclass Losses. Robert C. Williamson, Elodie Vernet, Mark D. Reid. JMLR 2016)

Practically speaking,a very strong baseline would be simple cross-entropy loss training with a cross-validated reject threshold. It is missing. Some of the algorithms in Tables 2 and 3 (e.g. CS-Hinge or BEP) also require a cross-validated threshold that rules out an abstain loss exceeding c. Abstaining at all instance even would only get a loss of c, but several entries in Tables 2 and 3 have an abstain loss greater than c=0.2.

As a minor note, the abstain loss is a number between 0 and 1 and not a percentage.

Questions for authors

The main question would be to ask authors to speculate on why these proposed new losses are better than other calibrated losses. SOme new theoretical construct/counter-example demonstrating why these new constructions can outperform would be valuable and insightful.

2 comments
AuthorsOpenReview ↗

Responses to reviewer 5hds

We thank the reviewer for the expert review and for raising constructive questions. Regarding the concerns pointed out, we would like to add the following information:

  • Theoretical advantages over existing calibrated losses: As pointed out, all the losses with abstention in the experimental part have been shown to be calibrated. However, compared with the existing losses, our losses also enjoy other better properties, such as including CS losses generated by smooth losses or enjoying convexity, in addition to the calibration property. Compared to [Ramaswamy+2018] (CS-hinge) and [Ramaswamy+2018] (BEP), as mentioned in lines 76-93, our methods expand the scope of the calibrated CS losses to general CS losses beyond the one generated by the hinge CS. Compared to [Mao+2024a] (two-stage), our ACS loss is always jointly convex in (g,r)(\boldsymbol{g}, r) (as mentioned in lines 228-230), while their two-stage loss trains the predictor and rejecter in different periods, respectively, and is not jointly convex in (g,r)(\boldsymbol{g}, r). In addition, their single-stage losses are all non-convex, and our losses show better optimization properties than theirs (as mentioned in lines 183-185). Besides, in terms of methodology, [Ramaswamy+2018] (CS-hinge) and [Ramaswamy+2018] (BEP) are both confidence-based methods, which have been shown to be suboptimal when the predictor differs from the Bayes predictor [Mao+2024a, Appendix A].
  • Novelty of the excess risk bounds: Our losses show many differences with the proper composite losses presented in [1]. Firstly, gη†\boldsymbol{g}^{\dagger}_{\boldsymbol{\eta}} obtained by minimizing the pointwise risk WW for our method only depends on the maximum class probability η∗=max⁡yηy\eta^* = \max_{y}\eta_y. Thus, it is difficult to estimate the entire class probability η\boldsymbol{\eta} based on learned g\boldsymbol{g}. In addition, our losses are functions of (r,g)(r, \boldsymbol{g}), not only g\boldsymbol{g}. This means that we can not directly write our losses as functions of estimated class probability because it has no direct relation with rr. Here we do not assume rr has a direct relationship with any distribution. Therefore, our proposed losses cannot be written in the form of proper composite losses and their excess risk bounds are inapplicable.
  • Choices of baselines: Actually, a cross-entropy (CE) based method with rejection has been included as [Mao+2024a] (two-stage), which uses CE to train the predictor in the first stage and train the rejector in the second stage. Although training a predictor using CE and rejecting based on a threshold is a practical choice, it has been shown to be suboptimal when the predictor differs from the Bayes classifier (see [Mao+2024a, Appendix A]), and it does not explicitly model the abstention cost cc to adapt the setting to different abstention costs. Thus, from the perspective of theoretical guarantees, the current baseline choices would be appropriate for our work.
AuthorsOpenReview ↗

Responses to reviewer 5hds

  • Cross-validated threshold: We admit that [Ramaswamy+2018] (CS-hinge) and [Ramaswamy+2018] (BEP) in Tables 2-3 need further threshold tuning on the validation set to rule out an abstention loss exceeding cc, and we add experiments. To be consistent with the data splitting in the submitted version, the added experiments on CS-hinge and BEP inherit the hold-out method to tune the threshold τ\tau. The hold-out method splits the dataset into training/validation/test sets, which is standard and also adopted in [Charoenphakdee+2021]. The updated results with tuned τ\tau are displayed in Tables 1-2. Both for [Ramaswamy+2018] (CS-hinge) and [Ramaswamy+2018] (BEP), the threshold τ\tau after tuning is 0.70.7 on the vehicle dataset and 0.80.8 on Imagenette.

    Table 1: Performance of our method and [Ramaswamy+2018] (CS-hinge), [Ramaswamy+2018] (BEP) on the vehicle dataset.

    MethodRejection ratioMisclassification errorAbstention loss
    [Ramaswamy+2018] (CS-hinge)57.65%0.00%0.1153
    [Ramaswamy+2018] (BEP)54.71%3.90%0.1271
    Ours (ACS-hinge)89.41%0.00%0.1788
    Ours (ACS-logistic)39.41%4.85%0.1082

    Table 2: Performance of our method and [Ramaswamy+2018] (CS-hinge), [Ramaswamy+2018] (BEP) on Imagenette.

    MethodRejection ratioMisclassification errorAbstention loss
    [Ramaswamy+2018] (CS-hinge)100.00%--0.2000
    [Ramaswamy+2018] (BEP)100.00%--0.2000
    Ours (ACS-hinge)88.88%7.05%0.1856
    Ours (ACS-logistic)45.69%18.56%0.1922

    As shown in Tables 1-2, the abstention loss exceeding c=0.2c=0.2 has been ruled out, although [Ramaswamy+2018] (CS-hinge) and [Ramaswamy+2018] (BEP) reject overly on Imagenette. Note that here the implementations for [Ramaswamy+2018] (CS-hinge) and [Ramaswamy+2018] (BEP) refer to formulations in [Ramaswamy+2018, Section 6], which also include the abstention cost cc.

  • Unit of the abstention loss: We will modify it in a future version.

[1] Robert C Williamson, Elodie Vernet, and Mark D Reid. Composite multiclass losses. Journal of Machine Learning Research, 17(222):1–52, 2016.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.