Cardinality-Aware Set Prediction and Top-$k$ Classification
Authors: Corinna Cortes
Anqi Mao
Christopher Mohri
Mehryar Mohri
Yutao Zhong
Venue: NeurIPS 2024 poster (2024)
Keywords: top-k classification
cardinality-aware algorithms
consistency
cost-sensitive loss
learning theory
Primary area: learning_theory

Abstract: We present a detailed study of cardinality-aware top-$k$ classification, a novel approach that aims to learn an accurate top-$k$ set predictor while maintaining a low cardinality. We introduce a new target loss function tailored to this setting that accounts for both the classification error and the cardinality of the set predicted. To optimize this loss function, we propose two families of surrogate losses: cost-sensitive comp-sum losses and cost-sensitive constrained losses. Minimizing these loss functions leads to new cardinality-aware algorithms that we describe in detail in the case of both top-$k$ and threshold-based classifiers. We establish $H$-consistency bounds for our cardinality-aware surrogate loss functions, thereby providing a strong theoretical foundation for our algorithms. We report the results of extensive experiments on CIFAR-10, CIFAR-100, ImageNet, and SVHN datasets demonstrating the effectiveness and benefits of our cardinality-aware algorithms.

Cardinality-Aware Set Prediction and Top-k Classification
Corinna Cortes Google Research New York, NY 10011
Anqi Mao Courant Institute New York, NY 10012 aqmao@cims nyu.
Christopher Mohri
Stanford University Stanford, CA 94305
corinna@google.co com
edu edu
xmohr ierrri@ttaffii ord. edd
Mehryar Mohri
Yutao Zhong
Google Research & CIMS New York, NY 10011
Courant Institute
New York, NY 10012 yutao0cims .yu..yu.e.. edu
mohri0google.com com
Abstract
We present a detailed study of cardinality-awar top-k classification, novel approach that aims to learn an accurate top-k set predictor while maintaining a low cardinality. We introduce a new target loss function tailored to this setting that accounts for both the classification error and the cardinality of the set predicted. To optimize this loss function, we propose two families of surrogate losses: cost- sensitive comp-sum losses and cost-sensitive constrained losses. Minimizing these loss functions leads to new cardinality-awarg algorithms that we describe in detail in the case of both top-ı: and threshold-basee classifiers. We establish H-coonistencyy bounds for our cardinality-awar surrogate loss functions, thereby providing a strong theoretical foundation for our algorithms. We report the results extensive experiments on CIFAR 10, CIFAR- 100. ImageNet, and SVHN datasets demonstrating the effectiveness and benefits of our cardinality-awer algorithms.
Introduction
Top-k: classification consists of predicting the & most likely classes for a given input, as opposed to solely predicting the single most likely class. Several compelling reasons support adoption of this framework. First, it enhances accuracy by allowing the model to consider the top & predictions, accommodating uncertainty and providing a more comprehensive prediction. This is particularly valuable in scenarios where multiple correct answers exist, such image tagging, where top-k classifier can identify multiple relevant objects in an image. Second, top-k classification applicable in ranking and recommendation tasks such suggesting the top h most relevant products in commerce based on user queries. The confidence scores associated with the top k predictions also serve means estimate the model's uncertainty, which is crucial in applications requiring insight into the model's confidence level.
The predictions of a top-k classifier are also useful in several natural settings. For example, ensemble learning can benefit from top-k predictions as they can be combined from multiple models, contribut- ing improved overall performance by introducing more robust and diverse set of predictions. In addition, top-k predictions can serve as input for downstream tasks like natural language generation dialogue systems, enhaneing the performance of these tasks by providing broader range of potential candidates. Finally, the interpretability of the model's 's decision-making process enhanced by examining the top & predicted classes, allowing users to gain insights into the rationale behind the model's 's predictions.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The appropriate k for a task at hand may be determined by the application itself like recommendor system always expecting a fixed set size be returned. For other applications, it may be natural to let the cardinality of the returned set vary with the model's confidence or other properties of the task. Designing effective algorithms with learning guarantees for this setting is our main goal.
In this paper, we introduce the problem of cardinality-aware set prediction, which is to learn an accurate set predictor while maintaining low cardinality. The core idea is that an effective algorithm should dynamically adjust the cardinality of its prediction sets based on input instances. For top-k classifiers, this means selecting larger i for difficult inputs to ensure high accuracy, while opting for a smaller k for simpler inputs to maintain low cardinality. Similarly, for threshold based classifiers, a lower threshold can be used for difficult imputs to minimize the risk of misclassification, whereas a higher threshold can be applied to simpler inputs to reduce cardinality.
To tackle this problem, we introduce novel target loss function which captures both the classification error and the cardinality of a prediction set. Minimizing this target loss function directly is an instance-dependent cost-sensitive learning problem, which is intractable for most hypothesis sets. Instead, we derive two families of general surrogate loss functions that benefit from smooth properties and favorable optimization solutions.
To provide theoretical guarantees for our cardinality aware top-k approach, we first study consistency properties of surrogate loss functions for the general top-k problem with fixed k. Unlike standard classification, the consistency of surrogate loss functions for the top-k problem has been relatively unexplored. A crucial property in this context is the asymptotic notion of Bayes-consistency, which has been extensively studied in standard binary and multi-class classification [Zhang. 2004a, Bartlett al., 2006, Zhang, 2004b, Bartlett and Wegkamp, 2008]. While Bayes-consistenge has been explored for various top-k surrogate losses [Lapin et al., 2015, 2016, 2018, Yang and Koyejo, 2020, Thilagar et al., 2022], some face limitations. Non-convex "hinge-like" surrogates [Yang and Koyejo, 2020], surrogates inspired by ranking [Usunier et al., 2009]. and polyhedral surrogates [TThiaaaar et al., 2022] cannot lead effective algorithms as they cannot be efficiently computed and optimized. Negative results also indicate that several convex "hinge-like" surrogates [Lapin et al., 2015, 2016, 2018] fail to achieve Bayes-consisteney [Yang and Koyejo, 2020]. On the positive side, it has been shown that the logistic loss (or cross- cross-yntropy loss used with the softmax activation) is Bayes- consisetnt loss for top-k classification [Lapin et al., 2015, Yang and Koyejo, 2020].
We show that, remarkably, several widely used families of surrogate losses used in standard multi-class classification admit H-consistency bounds [Awasthi, Mao, Mohri, and Zhong, 2022a,b, Mao, Mohri, and Zhong, 2023f,b] with respect to the top-k loss. These are strong non-asymptotic consistency guarantees that are specific to the actual hypothesis set adopted, and therefore also imply asymptotic Bayes-consistency. We establish this property for the broad family of comp-sum losses [Mao, Mohri, and Zhong, 2023f], comprised of the composition of non-decreasing and non-nen non-negative function with the sum exponential losses. This includes the logistic loss, the cum-exponential loss, the mean absolute error loss, and the generalized cross-entropy loss. Additionally, we extend these results to constrained losses, a family originally introduced for multi-class SVM [Lee et al., 2004], which includes the constrained exponential, hinge, squared hinge, and p-margin losses. The guarantees of JC-consistency provide a strong foundation for principled algorithms in top-k classification by directly minimizing these surrogate loss functions.
We then leverage these results to derive strong guarantees for the two families of cardinality-aware surrogate losses: cost-sensitive comp-sum and cost-sensitive constrained losses. Both families are obtained by augmenting their top-k counterparts [Lapin et al., 2015, 2016, Berrada et al., 2018, Reddi al.. 2019, Yang and Koyejo, 2020. Thilagar et al., 2022] with -estedee-de cost terms. We establish strong H-consistencyy bounds, implying mayys-consistencyy for both families relative to the cardinality- aware target loss. Our H-consistency bounds for the top-k problem are further beneficial here in that the cardinality-aware problem can consist of fixing and selecting from family top-k we classifiers- we now know how to effectively learn each top-k classifier.
The rest of the paper is organized as follows. In Section 2, we formally introduce the cardinality-awar set prediction problem along with our new families of surrogate loss functions. Section instantiates our algorithms in the case of both top-k classifiers and threshold-based classifiers, and Section 4 presents strong theoretical guarantees. In Section 5, as well as in Appendix J and Appendix K. we present experimental results on the CIFAR-10, CIFAR- 100, ImageNet, and SVHN datasets, demonstrating the effectiveness of our algorithms.
2

---

2 Cardinalit--wware set prediction
In this section, we introduce cardinality-aware set prediction, where the goal to devise algorithms that dynamically adjust the prediction set's size based on the input instance to both achieve high accuracy and maintain low average cardinality. Specifically, for top-k classifiers, our objective is to determine suitable cardinality k for each input 2, with higher values of l for instances that are more difficult to classify.
To address this problem, we first define a cardinality- loss function that accounts for both the classification error and the cardinality of the set predicted (Section 2.1). However, minimizing this loss function directly is computationally intractable for non-trivial hypothesis sets. Thus, to optimize it, we introduce two families of surrogate losses: cost-sensitive comp-sum losses (Section 2.2) and cost-sensitive constrained losses (Section 2.3). We will later show that these loss functions benefits from favorable guarantees in terms of H-coniisty (Section 4.3).
2.1 Cardinality-awan problem formulation and loss function
The learning setup for cardinality-awan set prediction is as follows.
Problem setup. We denote by X the input space and y [n]:= [I,...,, the label space. Let (gg* e } denote a collection of given set predictors, induced by parameterized set predictor gx=X H 2 where each X c IR is a set of indices. This could be a subset of the family of top-k classifiers induced by some classifier h,
family of threshold-based classifiers based on some scoring function s: X' x y + R. In that case, (z) then comprises the set of ys with a score (z. y) exceeding the threshold тı: defining gk. This formulation covers as special case standard conformal prediction set predictors [Shafer and Vovk, 2008], as well as set predictors defined as confidence sets described in [Denis and Hebiri, 2017]. We will denote by (g(( the cardinality of the set ga (z) predicted by g for the input x. To simplify the discussion, we will assume that lg (x) is an increasing function of k for any x. For a family of top-k classifiers or threshold-
classifiers, this simply means that they are sorted in increasing order of l or decreasing order of the threshold values.
To account for the cost associated with cardinality, we introduce a non-negative and increasing function cost: IR, - IR,, where cost( Ig (=)]) represents the cost associated to the cardinality |gs (x)]. Common choices for cost include cost [gx (z))) = Ig (z)], or a logarithmic function cost(|g (lg (z)))
log(Ig ( (z)]) as in our experiments (see Section 5), to moderate the magnitude of the cost relative to the binary classification loss. Our analysis is general and requires no assumption about cost.
Our goal is to learn to assign to each input instance x the most appropriate index l K to both achieve high accuracy and maintain a low average cardinality.
Cardinality-aware loss function. As in the ordinary multi-class classification problem, we consider family R of scoring functions r: X x K - R. For any x, r(x, (x. denotes the score assigned to the label (or index) & E K, given x E X. The label predicted is r(x) = argmax r(x, k)), with ties broken in favor of the largest index. To account for both classification accuracy and cardinality cost, we define the cardinality-awar loss function for a scoring function r and input-output label pair
(x, v) e X x y as linearized loss of these two criteria:
((r, x., u) 195 (w) (ost(())(())
where the first term is the standard loss for a top-k prediction taking the value one when the correct label y is not included in the top-k set and zero otherwise, and X >> 0 a hyperparameter that governs the balance between prioritizing accuracy versus limiting cardinality. The learning problem then consists of using labeled training sample (z1.91),.. ....))............... (I'm: Vm) drawn i.i.d. from some (unknown) distribution D to select e R with a small expected cardinality- loss E(a.)) [[(r, x v.]]
The loss function (1) can be equivalently expressed in terms of instance-dependent cost function c: X x Xx R,
f(r, xr y) = c(x, r(x).))
where c(ar, k: yygg (x) Acost(1ga (x)). Minimizing (2) is an instance-dependent cost-sensitive learning problem. However, directly minimizing this target loss is intractable. To optimize this loss function, we introduce two families of surrogate losses in the next sections: cost-sensitive comp-sum losses and cost-sensitive constrained losses. Note that throughout this paper, we will denote all target
3

---

(or true) losses on which performance is measured with an L, while surrogate losses introduced for ease of optimization are denoted by L.
2.2 Cost-sensitive comp-sum surrogate losses
Our surrogate cost-sensitive comp-sum, c-comp, losses are defined follows: for all (r, Xxx x y. le-comp(t x, y) Eeex (1 c(,, k. (( ( k,,,, where the comp-sum loss feomp is defined as in [Mao, Mohri, and Zhong, 2023f]. That is, for any r in hypothesis set R and (x, y) X y. (1, 2,,,,) y) & (E e"(x,s/)~<(aaa)) where d R. + R. is non-decreasing. See Section 4.2 for more details. For example, when the logistic loss is used, we obtain the cost-sensitive logistic loss:
- -(d Σ (((esk))((as))) WeEK
(r, keEK
(r, ======ce (((r,,k,)) kEOK
The negative log-term becomes larger as the score r(x, k) increases, Thus, the loss function imposes greater penalty on higher scores r(x,)) k) through penalty term (c(a,,,, that depends on the cost assigned to the expert's prediction (z).
2.3
Cost-sensitive constrained surrogate losses
Constrained losses are defined a summation of function o applied to the scores, subject to constraint, as [Lee et al., 2004]. For any r e R and (x. X x y, they are expressed as
Testud v.
Σ (-r((z,))) with the constraint Σ 2r v) -0 y=y
where Q: R. is non-increasing. See Section 4.2 for a detailed discussion. Inspired by these constrained losses, we introduce a new family of surrogate losses, cost-sensitive con- strained (c-cstnd losses) which are defined, for all (r,z,y) R X y, by (r- Exex c(x, k. (-r((-r k)), with the constraint Σkex r(z,k) k) = O. where & + R. is non- increasing. For example, for ((t) = we obtain the cost-sensitive constrained exponential loss:
Pestnd c-- exp (r, Σ k( with the constraint
Σ r((x,)) = kee
keE
3 Cardinality-awarr algorithms
Minimizing the cost-sensitive surrogate loss functions described in the previous section directly leads to novel cardinality-awar algorithms. In this section, briefly detail the instantiation of our algorithms in the specific cases of top-k classifiers (our main focus) and threshold based classifiers.
Top-A classifiers. Here, the collection of set predictors is a subset of the top-k classifiers, defined by ga (x) = (h, (x)...., h2 (r)), where h1 (x),..., h2 (x) are the induced top-k labels for a classifier h. The cardinality in this coincides with the index: [g)( k. for any æ: X. The cost is defined as c(x, k. y) (x).h,()).....aa(a)))) + Acost(k), where cost(k) can be chosen to be l or lk). Thus, our hardinality-awar algorithms for top-k classification can be described as follows. At training time, assume access to sample set {(,, y1 ) /= and the costs each top-k set incurs. {c(z,, k. ) where le K. pre-fixed subset. The goal is minimize the target cardinality-awan loss function Σm E(r, 24, y1) = E cx r(x;), y:) over a hypothesis set R. Our algorithm consists of minimizing a surrogate loss such as the cost-sensitive logistic loss, defined as A = argmin,eR ΣM Σkex c(x, ks y()) log Ewex e'(x, (((x))))(x..))) At inference time, we use the top-f(x:) set (1e,.....,, for prediction, with the accuracy Lye(h, (x) and cardinality ((x) for that instance.
In Section 5, we compare the accurayy-versu--arddme obtained by varying À with those of top-k classifiers, demonstrating the effectiveness of our algorithms. What select for given application will depend on the desired accuracy. Note that the performance of the algorithm in [Denis and Hebiri, 2017] in this setting is theoretically the same as that of top-k
curves of our cardinality-an aware algorithms

---

classifiers. The algorithm is designed to maximize accuracy within a constrained cardinality of k. and it always reaches maximal accuracy at the boundary K after the cardinality is constrained to k K.
Threshold-based classifiers. Here, the set predictor is defined via a set of thresholds Tı: ge gx(x) {y y: s(x; y) > T When the set is empty, we just return argmmaxyey s(x y) by default. The description of the costs and other components of the algorithms is similar to that of top-k & classifiers. special case of threshold-based classifier is conformal prediction [Shafer and Vovk, 2008], which is a general framework that provides provably valid confidence intervals for a black-box scoring function. Split conformal prediction guarantees that m--1 é Cs.a (Xm+11)) 2 1-a a for some scoring function s: X' x y + I., where Ca,a (Xm=1) = {yr s( sxX (mx, y) 2 4a and 9a is the [a(m + 1/mm empirical quantile of s (XX,, Y;) over a held-out set {(x, Y.)) m drawn i.i.d. from some distribution 'D (or just exchangeably). Note, however, that the framework does not supply an effective guarantee on the size of the sets Cs,a( (Xm-)).
In Appendix K, we present in detail a series of early experiments for our algorithm used with threshold-based classifiers and include more discussion. Our experiments suggest that, when the training sample is sufficiently large, our algorithm can outperform conformal prediction.
4 Theoretical guarantees
Here, we present theory for our cardinality-aware algorithms. Our analysis builds on theory of top-k algorithms, and we start by providing stronger results than previously known for top-k surrogates.
4.1 Preliminaries
We denote by D distribution over X x y and write p(z,y) D(Y = X = x) for the condi- tional probability of Y y given X x, and use p(x) (p(x, p(r,..,,p(I,,)) n)) to denote the corresponding conditional probability vector. We denote by H:Hall x x
IR loss function defined for the family of all measurable functions Kan- Given a hypothesis set H s Han, the conditional error of a hypothesis h and the best-in-class conditional error are defined as follows: x. y) and e; (H. x) infhegr (h, Accordingly, the generalization error of a hypothesis h and the best-in-class generalization error are defined by: (h) = E(r.))- [((h, x, y)] = [x (C, and Ej (3C) = inf &c(h) inf (h, r.]. Given a score vector (h(z. 1).................... . h(x, generated by hypothesis h. we sort its components in decreasing order and write ha (z) to denote the k-th label, that is h(2, h (z)) h(z, h2(2)) 2 ...
Ce (h, x) Eegle [&(h, ..,y,,)) y)] = Eyey p(x, y)((h,
x,
1a,,, hn (x)). Similarly, for a given conditional probability vector p (x) = (p(x, xr, 1)......1 p(x, n)). we
write Pk (x) to denote the k-th element in decreasing order, that is p(x, Pi (x)) p(2, P2(x))
p(x,, Pr, (x)). ). In the event of tie for the k-th highest score or conditional probability, the label (x) or (z) is selected based on the highest index when considering the natural order of labels.
The target generalization error for top-k classification given by the top-k loss, which denoted by la and defined, for any hypothesis h and (x. y) X x y by
Es (h, x, v) 1 (+)).
The loss takes value one when the correct label is not included in the top-k predictions made by the hypothesis h, zero otherwise. In the special case where k this is precisely the familiar zero-one classification loss. Like the zero-one loss, optimizing the top-k loss is NP-hard for common hypothesis sets. Therefore, alternative surrogate losses are typically used design learning algorithms. A crucial property of these surrogate losses is minimizing surrogate loss over the family of all measurable functions leads to the near minimization of the top-k loss over the same family [Steinwart, 2007].
This requires that, asymptotically, nearly
Definition 4.1. A surrogate loss i is said to be Bayes-consistent with respect to the top-k loss lx if, for all given sequences of hypotheses { nere c Hall and any distribution, limn- Eg(hx) (HCa)) 0 implies lim Ee, (h,,) - -E,, (Hal)) 0.
Bayes-consistency is an asymptotic guarantee and applies only to the family of all measurable functions. Recently, Awasthi, Mao, Mohri, and Zhong [2022a,b] (see also [Awasthi et al., 2021a,b, 2023a,b, Mao et al., 2,,,,,d,e,a, 2024c.ba..hid.ffg Mohri et al., 2024]) proposed a stronger consistency guarantee, referred to as K-consistency bounds. These are upper bounds on the target
5

---

estimation eтror in terms of the surrogate estimation error that are non-asymptotic and hypothesis set-specific.
Definition 4.2. Given a hypothesis set H, a surrogate loss ? is said to admit an H-consistency bound with respect to the top-k loss l if, for some non-decreasing function f. the following inequality holds for all h é H and for any distribution: f(Ee, ( E/e (30) & Eg(h) - E
We refer to Er, (h) εú, (H) as the target estimation error and E7(h) Eg (H) as the surrogate estimation error. These bounds imply Bayes-consistency when K Hall by taking the limit.
A key quantity appearing in H--consistnncy bounds is the minimizability gap, which measures the difference between the best-in-class generalization error and the expectation of the best-in- class conditional error, defined for a given hypothesis set HC and a loss function & by: M)( Ej (IC) - Ex [e, (JC, As shown by Mao, Mohri, and Zhong [2023f], the minimizability gap is non-negative and is upper bounded by the approximation eπror ()() = ()a))) < Mx( v A(()). When K = Hall or more generally A²(3) O, the minimizability gap vanishes. However, in general, it is non-zero and provides a finer measure than the approximation error. Thus H-consistency bounds provide stronger guarantee than the excess error bounds.
4.2 Theoretical guarantees for top-k surrogate losses
We study the surrogate loss families of comp-sum losses and constrained losses in multi-class classification,, which have been shown in the past to benefit from H-consistency bounds with respect to the zero-one classification loss, that is Eg with k= = [Awasthi et al., 2022b, Mao et al., 2023f] (see also [Zheng et al., 2023, Mao et al., 2023b]). We extend these results to top-k classification and prove H-consistency bounds for these loss functions with respect Eg for any 1 1 k n.
Another commonly used family of surrogate losses in multi-class classification is the max losses, which are defined through a convex function, such as the hinge loss function applied to the margin [Crammer and Singer, 2001, Awasthi et al., 2022b]. However, as shown in [Awasthi et al., 2022b], no non-trivial F--consistnncy guarantee holds for max losses with respect to é,. even when i = 1.
We first characterize the best-in-class conditional error and the conditional regret of top-k loss, which will be used in the analysis of H-consistencyy bounds. We denote by s (X c S |||] k} the set of all k-subsets of a set S. We will study any hypothesis set that is regular.
Definition 4.3. Let A(n, k) be the set of ordered k-tuples with distinct elements in [n]. We say that a hypothesis set H is regular for top-k classification, if the top-k predictions generated by the hypothesis set cover all possible outcomes: Vx E X, ((h) (x))) h H} = A(n,k))
Common hypothesis sets such that of linear models neural networks, or the family of all measurable functions, are all regular for top-k classification.
Lemma 4.4. Assume that H is regular. Then, for any ε H and x E X, the best-in-class conditional error and the conditional regret of the top-k loss can be expressed as follows:
Ci, (HC, =1 11E(((z.(())) (h,
ΣIr(E,p(<=) - p(x, (x))]. 1=1
The proof is included in Appendix A. For l = 1, the result coincides with the known identities for standard multi-class classification with regular hypothesis sets [Awasthi et al., 2022b, Lemma 3].
As with [Awasthi et al., 2022b, Mao et al., 2023f], in the following sections, we will consider hypothesis sets that are symmetric and complete. This includes the class of linear models and neural networks typically used in practice, as well as the family of all measurable functions. We say that hypothesis set Hi is symmetric if it is independent of the ordering of labels. That is, for all y y. the scoring function x - h(2, y) belongs to some relued family of functions F. We say that hypothesis set is complete if, for all (x, y) e X Yj the set of scores h(,, y) span over the real numbers, that is, (h(2, h):h e H{} = R. Note that any symmetric and complete hypothesis set is regular for top-k classification.
Next, we analyze the broad family of comp-sum losses, which includes the commonly used logistic loss (or cross-entropy loss used with the softmax activation) as special case.

---

Comp-sum losses are defined as the composition of function d with the sum exponential losses, as in [Mao et al., 2023f]. For any h H and (x. 3) E X x y, they are expressed as
E Coomp (h, t, 1) = 1 Σ
where R. R2 is non-decreasing. When & is chosen as the function t log(1+ +), t t, t b 1 I+z and 1 { (1) ( Eeomp (l, æz y) coincides with the most commonly 1
used (multinomial) logistic loss, defined as Blog(h, (h, log(2 (Egrey eh(xrs/)- [Verhulst, 1838, 1845, Berkson, 1944, 1951]. the sum-exponential loss Teep x,, =Eyep eh(ns/)) [Weston and Watkins, 1998, Awasthi et al., 2022b] which is widely used in multi-class boosting (Saberian and Vasconcelos, 2011, Mukherjee and Schapire, 2013, Kuznetsov et al., 2014), the mean absolute error loss Emae (h, x. 1-1_ [Eeey c((x,s))-h(x.p)))
known to be robust to label noise for training neural networks [Ghosh et al., 2017], and the generalized cross-entropy loss (k,, 1 mean absolute error loss for learning deep neural networks with noisy labels [Zhang and Sabuncu, 2018], respectively. We specifically study these loss functions and show that they benefit from H-consistency bounds with respect to the top-k loss.
[Evey (=xx1/)))(()))
g (0, a generalization of the logistic loss and
Theorem 4.5. Assume that K is symmetric and complete. Then, for any S k the following H-consistency bound holds for the comp-sum loss:
Er, (h) - (x
E (H) + (H) s kob 1
( & (h)) E &comp (H) + M Zooup (3)).
In the special case where Ar. (H) = 0, for any 1 S. k n, the following upper bound holds:
Et, (h) Etg (H) S k/b ( (1)) &x
(H)):
Ecomp
where v1( 1 log(1 (1-1) 11) 1 (l)g(++)),.)))1 LE [0, 1] when Ecomp is Elogg (1) 1-11 -1, [0.1] when Feomp is Texpi (t) = t/n when Ecomp is Emaai and (/())=
1-9
(1+1) (1+1) +(11)) 1-7
for all q (0,1). LE [0, 1] when Zoomp is E Egee-
The proof is included in Appendix B. The second part follows from the fact that when Az Az. (H) O. the minimizability gap Mi..mpp16 vanishes. By taking the limit on both sides, Theorem 4.5 implies the H-consistency and Bayes-consistency of comp-sum losses with respect to the top-k loss. It further shows that, when the estimation error of Tcomp is reduced to c > 0, then the estimation error of & is upper bounded by legi (c), which, for a sufficiently small e, is approximately kv for Zoo and Texpp knc for Emae: and k<2n"c for &gce- Note that different from the other loss functions, the bound for the mean absolute error loss is only linear. The downside of this more favorable linear rate is the dependency
the number of classes and the fact that the mean absolute error loss is harder to optimize [Zhang and Sabuncu, 2018]. The bound for the generalized cross-entropy loss depends on both the number of classes and the parameter q.
In the proof, we used the fact that the conditional regret of the top-k loss is the sum of differences between two probabilities. We then upper bounded each difference with the conditional regret of the comp-sum loss, using hypothesis based on the two probabilities. The final bound is derived by summing these differences. In Appendix G. we detail the technical challenges and the novelty.
The key quantities in our K-coosistenccy bounds are the minimizability gaps, which can be upper bounded by the approximation error, or more refined terms, depending on the magnitude of the parameter space, as discussed by Mao et al. [2023f]. As pointed out by these authors, these quantities, along with the functional form, can help compare different comp-sum loss functions. In Appendix C, we further discuss the important role of minimizabilityy gaps under the realizability assumption, and the connection with some negative results of Yang and Koyejo [2020].
7

---

Constrained losses are defined as a summation of function + applied to the scores, subject to constraint, as shown in [Lee al., 2004]. For any h H and (z. y) I y, they are expressed as
Eestnd (h, x, v)=
Σ 2 ((-h((x,))), with the constraint Σ h( v) y
-y
where O. R. is non -on-increasing.. In Appendix E, we study this family of loss functions and show that several benefit from H-consistency bounds with respect the top-k loss. In Appendix H, provide generalization bounds for the top-k loss in terms of finite samples (Theorems H.1 and H.2).
4.3 Theoretical guarantees for cardinality-aware surrogate losses
The strong theoretical results of the previous sections establish the effectiveness of comp-sun and constrained losses as surrogate losses for the target top-k loss for common hypothesis sets used in practice. Building on this foundation, we expand our analysis to their cost-sensitive variants in the study cardinality-awan
set prediction Section 2. We derive H-consistency bounds for these loss functions, thereby also establishing their Bayes-consistency To do so, we characterize the conditional regret of the target cardinality-awan loss function Lemma I.1, which can be found Appendix I. For this analysis, will assume, without loss of generality, that the cost e(z, k, y) takes values in [o, 1] for any kx E E x x x y, which can be achieved by normalizing the cost function.
We will use Eo-log Re-oaps Lo-gr and Eo- denote the corresponding cost sensitive counterparts for Elug. Eexp. Egee and Emee, respectively. Next, we show that these cost-sensitive surrogate loss functions benefit from H-consistency bounds with respect the target loss & given in (1).
Theorem 4.6. Assume that R is symmetric and complete. Then, the following bound holds for the cost-sensitive comp-sum loss: for all r R and for any distribution,
Ee(r) - E Mc $ (57 (T comma (r) - 77-coomp (R) + T (R)
comp
When R- = Rall, the following holds: (r(r) E7 (Ran) 1 <7(E7 (7(E7
comp (r)
E7
(Rai)). where
Ea-oump
(t) 2/7 when Ec-comp is either Ec-log or Ec-expi 7(t) 2//33/ when Ee-comup is lo-goei and
(t) = =3[]t when Zo-comp is Po-mae.
The proof is included in Appendix L.1. The second part follows from the fact that when R Rall- all the minimizability gaps vanish. In particular, Theorem 4.6 implies the sayes-consistency of cost-sensitive comp-sum losses. The bounds for cost-sensitive generalized cross-entropy and mean absolute error loss depend on the number of set predictors, making them less favorable when [X] is large. As pointed earlier, while the cost-sensitive mean absolute error loss admits linear rate, it is difficult to optimize even in the standard classification, as reported by Zhang and Sabuncu [2018].
In the proof, represented the comp-sum loss function of the softmax and introduced softmax- deeeededee function S,, to upper bound the conditional regret of the target cardinality- loss function by that of the cost-sensitive comp-sum loss. This technique is novel and differs from the approach used in the standard scenario (Section 4.2).
We will use e expx (c-eg-hinge, Ec-hinge and To- denote the corresponding cost-sensitive coun- Zestnd T Fig-- Eninge and o,p- respectively. Next, we show that these cost-sensitive surrogate losses benefit from H--oosisstnnyy bounds with respect to the target loss given in (1).
terparts for exp.
Theorem 4.7. Assume that R is symmetric and complete. Then, the following bound holds for the cost-sensitive constrained loss: for all r E R and for any distribution,
Ee(r) - (R) M, 5 ( an (r)- - E (R) M. (R)):
When R = Rall the following holds: Ee(r) E (Ral) (87 (r) & T (Rau)), where
(1) = 2t( when Ec-rstnn is Fristnd or To- (1) 1. when Ec-cstad is fe-hings or Fe-p- ceeep exp
The proof is included in Appendix I.2. The second part follows from the fact that when R = Rull- all the minimizability gaps vanish. particular, Theorem 4.7 implies the Bayes-consistency of cost-sensitive constrained losses. Note that while the constrained hinge loss and p-margin loss have more favorable linear rate the bound, their optimization may be more challenging compared to other smooth loss functions.
8

---

0.35
0.975
0.48
Accuracy
0.98
Accuracy.
0.90
Accuracy
350
Accuracy
0.93
0.23
0.03
0.82
1op4 Clasile cand-umare
lop dass
1p cossiic
0.78
0.75
0.575
0.90
Cardinality
Cardinality
Cardinality
Cardinality
CIFAR-100
ImageNet
CIFAR-I0
SVHN
Figure I: Accuracy versus average cardinality plots obtained by varying À for our cardinality algorithm and top-k classifiers across four datasets, with predictor set K {1, 2, 4,8) and cardinality cost cost(k) = log k. Our cardinality-awar algorithm consistently achieves higher accuracy for any fixed average cardinality across all datasets.
0.58
Accuracy
0.94
0.90
Accuracy
Acuurao
0.90
0.34
0.08
card-nmre, comtit logt
0.80
card-anare, coolit legit)
0.500
card-enare conti) micglh)
0.92
card swars coutt - logik card swars, couti -x
cardenare coxik)=
0.75
card-onare coout)
0.75
cord-anare cosii)
1.0
1.5
2.0
25
1.
15
25 Cardinality
25
3.0
Cardinality
Cardinality
Cardinallty
CIFAR-100
ImageNet
CIFAR-I0
SVHN
Figure 2: Comparison of cardinality costs cost(k) log k and cost(k) k. with predictor set K (1, 4,8), 8). The accuracy versus average cardinality plots for our cardinality-awar algorithm are similar, suggesting that the choice of cardinality cost has minimal impact performance.
Experiments
Here, we report empirical results for our cardinality-awarr algorithm and show that it consistently outperforms top-k classifiers on benchmark datasets CIFAR- 10, CIFAR-100 [Krizhevsky, 2009], SVHN [Netzer et al., 201 1] and ImageNet [Deng et al., 2009].
We used the outputs of the second-to-last layer of ResNet [He et al., 2016] as features for the CIFAR- 10, CIFAR-100 100 and SVHN datasets. For the ImageNet dataset, we used the CLIP [Radford et al., 2021] model to extract features. We adopted a linear model, trained using multinomial logistic loss, for classifier on the extracted features from the datasets. We used
poo-hidden-layer feedforward neural network with ReLU activation functions [Nair and Hinton, 2010] for the cardinality selector Both the classifier and the cardinality selector r were trained using the Adam optimizer [Kingma and Ba, 2014], with learning rate of 10 batch size of 128, and weight decay of 1 x 10-5.
Figure compares the accuracy versus cardinality curves of the cardinality aware algorithm with that of top-k classifiers induced by h for the various datasets. The accuracy of a top-k classifier is measured by s( [1 & (h, x. y. that is the fraction of the sample in which the top-k predictions include the true label. It naturally grows the cardinality & increases, shown in Figure 1. The accuracy of the curnality-awar algorithms is measured by E(a.y))ss (heei)ssssssehheeeeee we (e))....n..)))( J. that is the fraction of the sample in which the predictions selected by the model include the true label, and the corresponding cardinality is measured by (<x=))-[[r(==]]] that is the average size the selected predictions. The cardinality selector was trained by minimizing the cost-sensitive logistic loss Tc-log with the cost c(x, k, y) defined as & (h, x. v) A log(k) and normalized to [o. 1] through division by its maximum value over X K y. We allow for top-k experts with h K = {1, 2, 4, 8} and vary X. Starting from high values of A, as À decreases in Figure 1, our cardinality- yields solutions with higher average cardinality and increased accuracy. This is because À controls the trade-off between cardinality and accuracy. The plots end to the right at À 0.01.
algorithm
Figure 1 shows that the cardinality-awan algorithm is superior across the CIFAR-100. ImageNet, CIFAR-10 and SVHN datasets. For a given average cardinality, the cardinality-awan algorithm always achieves higher accuracy than top-k classifier. In other words, to achieve the same level of accuracy, the predictions made by the cardinality- size compared to those made by the corresponding top-k classifier. In particular, the CIFAR- 100, CIFAR-10 10 and SVHN datasets, the cardinality- awaae algorithm achieves the same accuracy (98%) the top-k classifier while using roughly only half of the cardinality average. As with the ImageNet dataset, it achieves the same accuracy (95%) as the top-k classifier with only two-thirds of the cardinality. This illustrates the effectiveness of our cardinality-
algorithm can be significantly smaller in
algorithm.
Figure presents the comparison of cost( (=)))= = and cost(lg: (=))) ( log k in the same setting (for each dataset, the orange curve in Figure 2 coincides with the orange curve in Figure 1). The

---

CIFAR-100
CIFAR-10
6000
0,55
3000
Count
Count
4000
2000
1000
2000
0
2
4
8
1
2
4
K
k
Figure 3: Cardinality distribution for top-k experts with KK (1, 4,8,, (1,2,44) 100 datasets, analyzed under two À values. For each dataset, increasing À reduces the number of samples with the highest cardinality (k 8) and increases those with lower cardinalities. as higher amplifies the influence of cardinality in the cost function. Across datasets, distributions vary for the same Ả due differing task complexities.
CIFAR-10 and CIFAR-
Thue label: cat
True label: frog
True label: deer
Thue label: airplane
Hard images.
True label: cat
True label: frog
True label: deer
True label: airplane
Easy images.
Figure 4: Illustration of hard and easy images on the CIFAR-I0 dataset as judged by human annotators, for top-k experts K 21, 8). Hard images are those correctly predicted by algorithm with cardinality of 8 but misclassified with cardinality of 4. Easy images are correctly predicted with cardinality of
comparison suggests that the choice between the linear and logarithmic cardinality costs has negligible impact algorithm's 's performance, highlighting its robustness in this regard. We also empirically demonstrate that our algorithm dynamically adjusts the cardinality of prediction sets based on input complexity, selecting larger
for more challenging inputs to ensure high accuracy and smaller sets for simpler inputs to keep the cardinality low, as illustrated in Figure 3 and Figure 4. We present additional experimental results with different choices of set K in Figure and Figure 6 in Appendix J. Our cardinality-awv aware algorithm consistently outperforms top-k classifiers across all configurations.
Conclusion
We introduced a new cardinality- set prediction framework for which we proposed two families of surrogate losses with strong "K-oonssstency guarantees: cost-sensitive comp-sum and constrained losses. This leads to principled and practical cardinality-awan algorithms for top-k classification, which we showed empirically be very effective, Additionally, we established theoretical foun- dation for top-k classification with fixed cardinality & by proving that several common surrogate loss functions, including comp-sum losses and constrained losses in standard classification, admit K-consistency bounds with respect to the top-k loss. This provides a theoretical justification for the use of these loss functions top-k classification and opens new avenues for further research this area.
10

---

References
Awasthi, N. Frank, A. Mao, M. Mohri, and Y. Zhong. Calibration and consistency of adversarial surrogate losses. In Advances in Neural Information Processing Systems, pages 9804-9815, 2021a.
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. A finer calibration analysis for adversarial robustness. arXiv preprint arXiv:2105.01550 2021b
Awasthi, A. Mao, M. Mohri, and Y. Zhong. !!-conisttnccy bounds for surrogate loss minimizers. In International Conference on Machine Learning, pages 1117-1174, 2022a.
P. Awasthi, A. Mao, M. Mohri, and Y. Zhong. Multi-class H Hl-consistency bounds. In Advances in neural information processing systems, pages 782-795, 2022b.
Awasthi, A. Mao, M. Mohri, and Zhong. Theoretically grounded loss functions and algorithms for adversarial robustness. In International Conference on Artificial Intelligence and Statistics, pages 10077-10094, 2023a.
Awasthi, A. Mao, M. Mohri, and Zhong. DC-programming for neural network optimizations. Journal of Global Optimization, 2023b.
P. L. Bartlett and M. H. Wegkamp. Classification with reject option using hinge loss. Journal of Machine Learning Research, 98), 2008.
L. Bartlett, M. Jordan, and J. McAuliffe, Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-155 2006.
J. Berkson. Application of the logistic function to bio-assay. Journal of the American Statistical Association, 199:37-3665 1944.
Berkson. Why prefer logits to probits. Biometrics, 7(4):327-339, 1951.
Berrada, A. Zisserman, and M. P. Kumar. Smooth loss functions for deep top-k classification. In International Conference Learning Representations, 2018.
K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based vector machines. Journal of machine learning research, 2(Dec): 2001.
Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and F.-F. Li. Imagenet: large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages 248-255. Icee, 2009.
C. Denis and Hebiri. Confidence sets with expected sizes for multiclass classification. Journal of Machine Learning Research, 18(102):1-28, 2017.
A. Ghosh, H. Kumar, and P. S. Sastry. Robust loss functions under label noise for deep neural networks. In Proceedings of the AAAI conference on artificial intelligence, 2017.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770-778, 2016.
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
A. Krizhevsky. Learning multiple layers features from tiny images. Technical report, Toronto University, 2009.
V. Kuznetsov, M. Mohri, and U. Syed. Multi-class deep boosting. In Advances in Neural Information Processing Systems, pages 2501-2509, 2014.
M. Lapin, M. Hein, and B. Schiele. Top-k multiclass SVM. In Advances in neural information processing systems, 2015.
M. Lapin, M. Hein, and B. Schiele. Loss functions for top-k error: Analysis and insights. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1468-1477, 2016.
11

---

M. Lapin, M. Hein, and B. Schiele. Analysis and optimization of loss functions for multiclass, top-k. and multilabel classification. IEEE Transactions on Pattern Analysis & Machine Intelligence, 40 (07):1533-1554 2018
Y. Lee, Lin, and G. Wahba. Multicategory support vector machines: Theory and application to the classification of microarray data and satellite radiance data. Journal of the American Statistical Association, 99(465):67-81, 2004.
P. Long and R. Servedio. Consistency versus realizable H-consistency for multiclass classification. In Interaational Conference on Machine Learning, pages 801-809, 2013.
A. Mao, C. Mohri, M. Mohri, and Y. Zhong. Twoostage learning to defer with multiple experts. In Advances in neural information processing systems, 2023a.
A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds: Characterization and extensions. In Advances in Neural Information Processing Systems, 2023b.
A. Mao, M. Mohri, and Y. Zhong. H-consistency bounds for pairwise misranking loss surrogates, In International conference on Machine leurning, 2023c.
A. Mao, M. Mohri, and Y. Zhong. Ranking with abstention. In ICML 2023 Workshop The Many Facets of Preference-Basee Based Learning, 2023d.
A. Mao, M. Mohri, and Y. Zhong. Structured prediction with stronger consistency guarantees. In Advances in Neural Information Processing Systems, 2023e.
A. Mao, M. Mohri, and Y. Zhong. Cross-entropy loss functions: Theoretical analysis and applications. In International Conference on Machine Learning. 2023f.
A. Mao, M. Mohri, and Y. Zhong. Principled approaches for learning defer with multiple experts. In International Symposium on Artificial Intelligence and Mathematics, 2024a.
A. Mao, M. Mohri, and Y. Zhong. Predictor-rejector multi-class abstention: Theoretical analysis and algorithms. In International Conference on Algorithmic Learning Theory, 2024b.
A. Mao, M. Mohri, and Y. Zhong. Theoretically grounded loss functions and algorithms for score- based multi-class abstention. In International Conference Artificial Intelligence and Statistics, 2024c.
A. Mao, M. Mohri, and Y. Zhong, Enhanced H-cconisttnccy bounds. arXiv preprint urXiv:2407.33722 2024d.
A. Mao, M. Mohri, and Y. Zhong. HI-consistency guarantees for regression. In International Conference on Machine Learning, pages 34712-34737, 2024e.
A. Mao, M. Mohri, and Y. Zhong. Multi-label learning with stronger consistency guarantees. In Advances in neural information processing systems, 2024f.
A. Mao, M. Mohri, and Y. Zhong. Realizable H-consistent and Bayes-consistent loss functions for learning to defer. In Advances in neural information processing systems, 2024g.
A. Mao, M. Mohri, and Y. Zhong. Regression with multi-expert deferral. In International Conference on Machine Learning, pages 14738-34759) 2024h.
A. Mao, M. Mohri, and Y. Zhong. A universal growth rate for learning with smooth surrogate losses. In Advances neural information processing systems, 2024i.
C. Mohri, D. Andor, E. Choi, M. Collins, A. Mao, and Y. Zhong. Learning reject with fixed predictor: Application to decontextualization. In International Conference on Learning Representations, 2024.
M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of machine learning. MIT press, 2018
Mukherjee and Schapire. theory of multiclass boosting. Journal of Machine Learning Research, 2013.
12

---

V. Nair and G. E. Hinton. Rectified linear units improve restricted boltzmann machines. In Pro- ceedings of the 27th international conference on machine learning (ICML-10), pages 807-814, 2010.
Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Ng. Reading digits in natural images with unsupervised feature learning. In Advances Neural Information Processing Systems, 2011.
A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, Mishkin, J. Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pages 8748-8763. PMLR, 2021.
S. J. Reddi, S. Kale, F. Yu, D. Holtmann- Rice, J. Chen, and S. Kumar. Stochastic negative mining for learning with large output spaces. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1940-1949, 2019.
M. Saberian and N. Vasconcelos. Multiclass boosting: Theory and algorithms. Advances in neural information processing systems, 24, 2011.
G. Shafer and V. Vovk. tutorial on conformal prediction. Journal of Machine Learning Research, (3), 2008.
I. Steinwart. How to compare different loss functions and their risks. Constructive Approximation, 26(2):225-287, 2007.
A. Thilagar, R. Frongillo, J. J. Finocchiaro, and E. Goodwill. Consistent polyhedral surrogates for top-k classification and variants. In International Conference on Machine Learning, pages 21329-2 21359, 2022.
N. Usunier, D. Buffoni, and P. Gallinari. Ranking with ordered weighted pairwise classification. In International conference on machine learning, pages 1057-1064, 2009.
F. Verhulst. Notice sur loi que la population suit dans son accroissement. Correspondance mathématique et physique, 10:113 1838.
F. Verhulst. Recherches mathématiques sur la loi d'accroissement de la population. Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Leitres de Bruxelles,
1845.
J. Weston and C. Watkins. Multi-class support vector machines. Technical report, Citeseer, 1998.
F. Yang and S. Koyejo. On the consistency of top-k surrogate losses. In International Conference on Machine Learning, pages 10727-10735, 2020.
Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56 85, 2004a.
Zhang. Statistical analysis of some multi-category large margin classification methods. Journal of Machine Learning Research, 5(Oct): 1225-1251, 2004b.
Z. Zhang and M. Sabuncu. Generalized cross entropy loss for training deep neural networks with noisy labels. In Advances in neural information processing systems, 2018.
C. Zheng, G. Wu, F. Bao, Y. Cao, C. Li, and Zhu, Revisiting discriminative vs. generative classifier:: Theory and implications. In International Conference on Machine Learning, 2023.
13

---

Contents of Appendix
Proof of Lemma 4.4
15
B Proofs of K-consistency bounds for comp-sum losses
15
Minimizability gaps and realizability
20
D Proofs of realizable H--consistency for comp-sum losses
20
JH-Consistnney bounds for constrained losses
F Proofs of K-consistency bounds for constrained losses
22
Technical challenges and novelty in Section 4.2
26
H Generalization bounds
27
Proofs K--consistency bounds for cost-sensitive losses
29
1.1 Proof of Theorem 4.6
29
I.2 Proof of Theorem 4.7
33
J Additional experimental results: top-k classifiers
37
K Additional experimental results: threshold- classifiers
38
Future work
39
14

---

A Proof of Lemma 4.4
Lemma 4.4. Assume that H is regular. Then, for any H and X, the best-in-class conditional error and the conditional regret of the top-k loss can be expressed as follows:
- - e7, (IC, x) = (.0-(((( (b,
&
Proof. By definition, for any h E H and é X, the conditional error of top-k loss can be written as
(h, = Σ
p(x, ye (e) = -1 -,,,,,,,
yey
By definition of the labels Pa (x),, which are the most likely top-k labels, Ce2 (h, x)) is minimized for (x) Kmin (I), e [k.. Since H. is regular, this choice is realizable for some h e H. Thus, we have
ej, (H,
inf Ce, (h, = Ep(x))(<)).
hell
Furthermore, the calibration gap can be expressed as
ACC, ac (h, = Cea xh) Cú2 xH) -()))))(((()()))))))))
which completes the proof.
B Proofs of K-consistency bounds for comp-sum losses
Theorem 4.5. Assume that K is symmetric and complete. Then, for any s k n, the following H-consistency bound holds for the comp-sum loss:
(h) - (H) Me, (H)) s lobb 1o
87 7zomp (h)- E Ecomp (H) Mocmm (30).
In the special case where Ay (H) = 0, for any S k n, the following upper bound holds:
El2 (h) E7, (3C) S Ko ( - Exoopp
Ecomp (30)):
where v1() 1-t (og((1t)) 1+t (og((+))),,))).. E [0, 1] when Toomp is Elogi (1()) = 1- [
(1et) (1)- 1-9
when Toomp Texpi (t) = t/n when Tcomp Emaei and (/())= 9ma
for all E (0,1), e [0, 1] when Teomp is Egce-
Proof. Case I: Zeomp Toge For logistic loss Bug. the conditional regret be written
x
AC Blog or (1,z)
Σ
p(x, y) Bog 2,)
inf helk
Σ
p(x, 8) y)o (h, 2. 2.
"
Σ y=1
( 4) Foog (h. inf Σ neR y-1
p(x, y) Eo0g (,,,,,,
where for any i [k].
h1(z,)) (( + +H)
" (p(()),,,
ha y)
y y= (x)
log ((xhh)(z.))())))
y (x).
Note that such choice of h leads the following equality holds:
Σ
p(x, y) (h, x.))
Σ vt(h.()).p.()))
p(z, Eog x.
(+))
15

---

Therefore, for any E [k:] the conditional regret of logistic loss can be lower bounded as ch(x.h(())
) p(=,
(((x((()) Eyey eb(())))
Ving (h, -p(x, h, (x)) log
Eyey ed(ONs) (eME)p(())) + Eyeyehlapp
- (((x,,P(()))
log
+
sup NeR
p (())
(((x, log
(ble.))))))) ch(a.((()))
p(z, log Maa ch(z,h((a))
sup
p(), log
By the concavity of the function, differentiate with respect to μ., we obtain that the supremum is achieved by μ² (t). (ateee))ellaatto-pptd((a)ddd---d (() Plug in ju, we obtain
((
AC Too or (h,2)
((x,
M(c.h(())) + (((A((()))
2 log
p(x, hi(x)))))))))))))))))))))) + p(x,
el(x,h(()))
p(I,
M(z,(())) (()P((())
+ + log
(z), + p( ((;
ch(xxp(()))
2p(x,
30(xx,((x)))
2 2x(x,,;(z)) log
p(5, h:())) + p(=, p(zz, log p(r, (x)) p(x p(xx))())))
(minimum is achieved when h(r, (x)) (x))
let S; p(x,,,
+ +p h, (x))))
and A, = p(x,p; (x)), have
S A: S. A
S: A
S S
AC 1e (h,
log(
log(
S
S
1 A 2
1 1+
log(1 A;) +
log( 1 + A:) (minimum is achieved when S; = 1)
2
2
= (p(2,, (I)) - ((,,) (x)))
where (t) = L-f log(1 1 1 1) + let log(1 + 1), EE [0, 1]. Therefore, the conditional regret of the top-k loss can be upper bounded as follows:
2
2
AC Ae,,
- - s kD = (nn i-1
By the concavity of 1 taking expectations on both sides of the preceding equation, we obtain
Es. (h)- Ei (Hf) Mr, (II) kabb" 1 (h) Ex Fiog
(E
(IC) My (30).
The second part follows from the fact that when Ag (H) 0, the minimizability gap Mgng (H) vanishes.
Case 11: Zoomp Texp- For sum exponential loss Texps the conditional regret can be written as
x1, = Σ
p(x, ()r, (,, (h, inf Σ helk y=1
p(r, y) x,,
y=1
n
72 inf Σ p(x, 4) (ox H),, pell
2 Σ p(x, y) (h,
y=1
y=1
where for any e [k:].
h(z, y): (() +1)
F h,(()),,,(>))
hx, y)
= hz(x)
log log(e" ((e,h()))))())) - #)
y (x))
Note that such a choice of hp leads to the following equality holds:
Σ
p(z, 2 (h, x,,
Σ. p(z, v) (h,.s, (t((.()).p.()))
9f (z))
16

---

Therefore, for any é [k:] the conditional regret of sum exponential loss can be lower bounded as
exp(h(z,hixx))) + p(x,
p(),h;(x))
Ee (h) 2 Σ exp(h(x,v'))
exp(h((,,p(x)))
y'ey
((),h;()))
P(
+ sup peR
Σ exp(((<x,))) y'oy
pxp(h((, + hx((h(
By the concavity of the functioon differentiate with respect to μs we obtain that the supremum is achieved by n² wwK.acatllllleaaaalloaaaaaaaaaaa
Plug in n², we obtain
AC * x))
2 Σ exp(h(z,y))) y'y
p(x,hi(z)) p(z,pi(z))
(xp(h(r,h,,x))) exp(M(e,)((z))) (epplaaa
2 exp(b(z,p((z))) p(2,h((x))
exp(M(z,h((x)))
h, p(x) (Vp( (Vp(z, V/ p(())
exp(h((,,
Evey exp((xx)(((xx (((p(((( exp(h((z,hxx)))
2 - --pp...pp (z(z) 2
exp(h(z.p.(r))
(minimum is attained when exp(((z.h(a))) = 1)
+ h,)))),))))))))))))))))))))))))) let S p and A; = = px)), p(z, h.(2)),, we have
S A;
S A
ACrep. (1, 2S,
(1+ --,,)
2
(minimum achieved when S; 1)
= =1 -1- (2,)²
v (p(x, (z())) - p(x, hx()))
where (1) =1 1- V1 12, le [0, 1]. Therefore, the conditional regret of the top-k loss can be upper bounded follows:
Ae x) -
ke (h,
i-1
By the concavity of 1b-1, taking expectations on both sides of the preceding equation, we obtain
Ee, (h) Eig (H) Me, (H) lab E (7) E Taxpp
(H) My (H)).
The second part follows from the fact that when A7 (H) O. the minimizability gap My (H) vanishes.
Case II1: Zoomp Zmne. For mean absolute error loss Emaes the conditional regret can be written as
ACT (1, Σ (z, Emao (h, inf Σ p(a,, y) Emac (h, x,
hET y-!
g-l
Σ
p(x, v) Am (h, inf Σ p(x, 1) (hyne weR y-1
4-1
17

---

where for any é [k]]
h)z.y).
u hx)))
(2,(2, y)
log(e"((p)(()) + n))
y (x)
log log(e)(z.h.(o))) - 14
y = Px))
Note that such choice of hyy leads the following equality holds:
Σ
p(z,y) (h, x. x2
Σ
p(z,
(e(h(()).p.(:))
(h((()))):)()))
Therefore, for any i [k], the conditional regret of mean absolute error loss can be lower bounded as AC Fimne 30 (h,
2 p((x, 1- (x((h(z,h(x))))
p(E.p(())) exp(M((x)p(x)))
E Evey exp(h(x, v)))
Evey exp(h(zx,)))
-pla, ((t)) exp(h(æ, he (2(1))
Evey exteee))((( ((t, 1 exp(h(a,
Evey - +1
)
+ sup NeR
By the concavity of the function, differentiate with respect μa, obtain that the supremum is achieved by n exp[/(xx p())), Plug in μ¹,, we obtain
A Te (h,
exp(h(e,h,(x))) p(x, exp(h(x,h,,x))) p(x,h;(z)), Evey (xpMee))(((
Egeey (x)(( (p(x,) - p(x,h:(x)))
exp(h(x.h,(<r)) Exc
2 4
Therefore, the conditional regret of the top-k loss can be upper bounded as follows:
A (c,, (h E(r(,, ((((,,,(())) (x)))) - p(x, (,)))) s (n(Ae, mm (h
Take expectations on both sides of the preceding equation, we obtain
Eip (h) - 87, (IC) Me, (Ht) S kn E (h) - Emue (H) + My (30).
The second part follows from the fact that when Ay (H) O, the minimizabilityy gap My (H) vanishes.
Case IV: Zcomp = Tgeer For generalized cross-entropy loss Eyee the conditional regret be written as
AC Ar (h,
Σ p(x, Eyco inf Σ p(x, { (h, 2h,
y=1
2 Σ
p(x, 4) Ege (h, inf Σ peR
p(x, 8) goe ( (hp.),
9-1
y=1
where for any i [k]]
h(x,y); log (x)) +1)
y (p(x),,,,x))
(x,
y h=
log log( (sthh)))))())) -n)
y (x).
Note that such choice of hng leads to the following equality holds:
Σ
p(a, v) x.)
Σ (t))
p(z, v) goo x.
2f (())
18

---

Therefore, for any i e [1:], the conditional regret of generalized cross-entropy loss can be lower bounded
qdez 2e (k)
2 p((x, 1- (xp(h)Grch(0))))
Egeey exp(h + -"ttttppp)=(===++==+11) Ever Ever exp(h((x,)) 1))
exp(h(a;pi(x)))
exp(h(x, (z)))) Exeyeep(((ee exp(1(x, 1x) p((e, -(eepp))))
Evey exp(((xxp((x)))) |')
(xp((((z,h(()))
+ sup peR
(D((x
p(a,
By the concavity of the function, differentiate with respect to 14, we obtain that the supremum is achieved by μ² -xt.eetteelldccccee===== httpa//jcaaaaaaaao.o//o/aaaaaaaa
Plug in μ², we obtain
qAe B0o0 It (h) (h
[exp(h(x, [ogpudehhhc))--oooouppphdhhhhhEr 7
2 (()x,,(()))
bly exp(h(z,h((x))) 1"
- -xx),
Eveyy exp((xxp(((z
+ +x(x,p((x))
Σ Even /x
(x)()(
-(())
Eveyy (xc(eex(((22
(x)),
7 (()))((z))
h(
1e (x,hh())) नं pa, (T))
2p (p(r, (z)) +
((x))
px(z,p((x)
((2,h((z)) ग. + p(2 (z))
(x)()(m.p
and minimum is attained when exp(h((.pp()))
(xp()(x.h.(:)) 1)
Egecy (xp(((x)))
let S, = =;=((E,)(E))) (x))),;())) and A. p( px)))) -(,,h,,x) we have
(S: (Si+A,) - (S. --) 1-9
1
AC ACg (h
qna
2
(1+ -
1
qna
(minimum achieved when S; = 1)
((((z,p(<z) hx))),
ب 1-9
where (()
-1
l [0. 1]. Therefore, the conditional regret of the
top-k loss can be upper bounded as follows:
AC AC,,, E((x, (x(a)) p(x,, s kn (h.,
==1
By the concavity of 11 taking expectations on both sides of the preceding equation, we obtain
(h) E7, (H) + Mr, (H) s ke ( (h) E (H) My (3))
19

---

The second part follows from the fact that when A7 (JC) = 0, the minimizability gap Mr (J() vanishes.
C Minimizability gaps and realizability
The key quantities in our JCconsistency bounds are the minimizabilityy gaps, which can be upper bounded by the approximation error, or more refined terms, depending on the magnitude of the parameter space, as discussed by Mao et al. [2023f]. As pointed out by these authors, these quantities, along with the functional form, help compare different comp-sum loss functions.
Here, we further discuss the important role of minimizability gaps under the realizability assumption, and the connection with some negative results of Yang and Koyejo [2020].
Definition C.1 exists a hypothesis H such that ((x.))-< (1(x, y) l((,, hg+1 (z))) =.
A distribution D over X x is top-k----realizable, if there
This extends the H-rrealizability definition from standard (top-1) classification [Long and Servedio, 2013] to top-k classification for any k 1.
Definition C.2. We say that hypothesis set K is closed under scaling, if it is cone, that is for all E H. and R,, .h H.
Definition C.3. We say that a surrogate loss is realizable K-consistent with respect to &s, if for all n.], and for any sequence of hypotheses {hp) ney and top-k-9-rrealiaable distribution, lim En(hn - = 0 implies lim Ete (ht) E7,, (3C) = 0.
When H is closed under scaling, for and all comp-sum loss functions 8 = Fexpp T and Emae. it can shown that (T() (IC) for any H-realizable distribution. For example, for f Bog by using the Lebesgue dominated convergence theorem, have
Mg (3() Eg (IC)
lim E (8h")= lim log 1 Σ (x:')) =0, A00+000
8-+000
where h² satisfies F(..))- (h" (x,y) (z, h2())) = Therefore, Theorem 4.5 implies that all these loss functions are realizable H-consistent with respect to fo (Cx for k 1) when H is closed under scaling.
Theorem C.4. Assume that DC is closed under scaling. Then, Tog. Texps Egce and Eme are realizable H-consistent with respect to fo-1-
The formal proof presented in Appendix D. However, for k: 1, since the realizability assumption, h(x, y) is only larger than f(2,, hiv (x)) and can be smaller than h(x, h (x)), there may exist an H-realizable distribution DD such that M7 (H) > O. This explains the inconsistency of the logistic
loss on top-k separable data with linear predictors, when & 2 and > 2, as shown in [Yang and Koyejo, 2020]. More generally, the exact same example [Yang and Koyejo, 2020, Proposition 5.1] can be used show that all the comp-sum losses, Eoog- Toxp- Egeo and Emao are not realizable K- consistent with respect to l.- Nevertheless, previously shown, when the hypothesis set HC adopted sufficiently rich such that M)H()) or even Az()() they are guaranteed be H-conssitentt. This is typically the case in practice when using deep neural networks.
D Proofs of realizable H-cconsistnccy for comp-sum losses
Theorem C.4. Assume that H is closed under scaling. Then, Tragy Texps Egoe and Eman are realizable K-consistent with respect to fo-1-
Proof. Since the distribution is realizable, there exists hypothesis e H such that
((ay)) (h' (I,z) > h h2()))) =.
20

---

Therefore, for the logistic loss, by using the Lebesgue dominated convergence theorem,
M7, (JC) & E For the sum exponential loss, by using the Lebesgue dominated convergence theorem,
(IC) lim Fr (3h) lim --++00
log + Σ
(((((e)))) 0.
flog 3-++00
y'*y
Mr (3) S 87 Enopp (H) S
lim 87 (3h) lim B-++00 yf+y
Σ
2(h ((H 0.
B-+-00
For the generalized cross entropy loss, by using Lebesgue dominated convergence theorem,
1
(ln())/)) = 0.
M7 (I() S E7 (H) s lim ET (3h) B3-000
lim $1++00
Lvey
For the mean absolute error loss, by using the Lebesgue dominated convergence theorem,
Mimuc (3)) s 87 (H) S lim & (Bh) = lim 1
Σ
(h 0.
8-++00
B-++00
v'ey
Therefore, by Theorem 4.5, the proof is completed.
E HC-Consistency bounds for constrained losses
Constrained losses are defined as summation of function & applied to the scores, subject to constraint, as shown in [Lee et al., 2004, Awasthi et al., 2022b]. For any e H and (æ, y) E X y, they are expressed as
Esstua (h, (h,
Σ #(-h(z,'')), y/
with the constraint Eyey h(,, = 0, where c: R R, is non-increasing. When & is chosen as the function t e I (0, 1)² t max 1 t) and t ++ min/max(0, 1- t/p), 1}, P Eestna (hana(h,22, (h, v) y) are referred to as the constrained exponential loss festnd (h, 2, 1/ = Σ En M2,,', Cexp
the constrained squared hinge loss hine (h, x, x. = Eveoy max M(r, 2 the con- strained hinge loss Ehingo v) Ey max (0, 1 h(z, v)), and the constrained p-margin loss (h,, x. y) Eyeey min max (0, h(r, y/ s/)/p/////////p 1}. respectively [Awasthi et al., 2022b]. We now study these loss functions and show that they benefit from K-consistency bounds with respect to the top-k loss.
Theorem E.1. Assume that H is symmetric and complete. Then, for any k n, the following H-conssitency bound holds for the constrained loss:
Ee, E (3() Me. (Jt) kn/( (ry(E (b) Eimena (H) + My (30).
In the special case where Ar.nn (H) = for any 1 S k the following bound holds:
Ee2 (h) E7 (H) k-/( ( (hi) Ey E (3)).
where (t)) = 2/t when Eestnd is either Zz
Testad or Exq-hingei (t) when Tostna is either Eninge or exp
The proof is included in Appendix F. The second part follows from the fact that when the hypothesis set H. is sufficiently rich such that A7 (H) O, we have Mr (H) 0. Therefore, the constrained loss is JC-consistent and Bayes-consistent with respect to Cx. If the surrogate estimation error Ey E (h)- E E (3() is c, then, the target estimation error satisfies & (h) - E (H) & kc) Note that the constrained exponential loss and the constrained squared hinge loss both admit square root JC-consistnncy bound while the bounds for the constrained hinge loss and p-margin loss are both linear.
21

---

Proofs of H-consistency bounds for constrained losses
The conditional error for the constrained loss can be expressed as follows:
Tentua ()) p(E, (h, x,
E(( Σ {--((a,))))
( (-
1pm
y-1
y-y
yey
Theorem E.1. Assume that H symmetric and complete. Then, for any l n, the following H-consistency bound holds for the constrained loss:
Ete (h) - (30) + Mr. (H) s ( ( (1) - - Eornd (H() + M (30)
In the special case where Arrann (I() = for any S k S n, the following bound holds:
(h) E (H) ( (h) Festnm (30):
where 7(1) = 2 when Eratnd is either Festnd or hingne 7(1) I when Festnd is either Eränge or Ep-
Proof. Case I: Testad pestnd exx
For the constrained exponential loss Festad eex
the conditional regret can
be written as
n Σ p(x, Rexppe ( (,)
a Σ
Forrnd oe (h, =
inf hESk
p(x, o, y) Testra (h, x, v)
y=1
2 Σ
p( y)
Bestnd (h, exp
inf Σ pel y=1
pl x. y)
(hr,s x; 8).
exp
y=
where for any i [k].
h(x,v); (z)) y= (z)
y (z))
(2,
h();,,()))- (=).
Note that such choice of hp leads to the following equality holds:
Σ
p(x, ()
(h, x),)=
p(z, Cesp (hmar (+))
Σ
yt (x)
Let q(x, (x())) =1 1 ((()) and q(z, hx)))) = 11 p(z, (x))). Therefore, for any i e [1s], the conditional regret constrained exponential loss can lower bounded as
AC
Areand a..cccchg xh) cap
inf sup (MMA)))((MMMM(())))MMMMMM q(2, -aaa
helf uell
(V(l=p(t))
(differentiating with respect to μ. h to optimize)
((tx,(())))=((((((()))
(((x:h(()))-(ccpp(()))
(s ((x 1)
1 ((( p(a,
Therefore, by Lemma 4.4, the conditional regret of the top-k loss can be upper bounded as follows:
ACC, or (h, ((,, 2 A Ersardd .x (cc (h,
22

---

By the concavity, taking expectations on both sides of the preceding equation, we obtain Ere (h) E (H) + Me, (H) 2
Eeanna (1i) Toernd
(H)
M
Mycsina Eoe
(H)
cxp
The second part follows from the fact that when yourad (H) O, we have M
Mysund (H) 0.
Case II: Pestud Eeq- hinger For the constrained squared hinge loss Eeg hingee the conditional regret can be written as
AC A. H (h,x)
Σ
p2,, Exq hingo (,,
inf heSt y-1
Σ p( v) hinge (h, y)
y-1
2
Σ
p( vr 1) laa--hing hingo (1,
inf Σ weR y-1
p( (r, 3) sog- (M H.Y),
hingo
5-1
where for any i [k],
h(x,y);
u hp)())),,;))
h v)
h(r, (x())) + (x) (x,,,;())) -
y (=).
Note that such a choice of hp leads to the following equality holds:
Σ p(a, Caq- (h,
Σ 14 (h, (1))
p(x, () hingo (1
1/ (h.())))..())))
Let q(x, (x)) 1- p(=, (x)) and g(x, (x)) =1 11 p(, (x)) Therefore, for any i e [A=]. the conditional regret of the constrained squared hinge loss can be lower bounded as
A nengo. 1))
2 inf sup p.(x)) (la. (mx((,1--((2,, 1)²) heTe yeR
(differentiating with respect to μ,, h to optimize)
p(t,
Therefore, by Lemma 4.4, the conditional regret of the top-k loss can be upper bounded as follows:
AC, (h, x) E(r(s, -(x))(()()( 2k AC hingo oe (h, (h,)))
By the concavity, taking expectations on both sides the preceding equation, we obtain
(Ht) + Mr, (9I) s 2k Enptting (h) Eee (h) (.,(H,)))
E
(H) + My Zap-
(37)
hinghinge
The second part follows from the fact that when the hypothesis set HC is sufficiently rich such that Ag Ang-iin (I)) = 0, we have Ming- (H) O.
Case III: Pestad
Eninge- For the constrained hinge loss Eninger the conditional regret can be written
A 2 (h1 =
Σ
p (r,
inf Σ p(x, 1) Eninge xr y) heSf 7-1
1-1
n inf Σ p(,, y) (han
2 Σ
p(2,, y) Eninge (h,
4-1
HER y-1
23

---

where for any é [k]]
M(x,u),
y yc (p)()));;;)))
( v)
hz) + h(),,;())) μ y=p((x).
(x)
Note that such a choice of hpd leads to the following equality holds:
Σ
p) Pninge (h, x. (h:
Σ
p( Cinggo (r,
(=(()()))p.())))
Let q (x))) 1 p(x, p=())) and ((x, h.))) = p(r,, (x))). Therefore, for any i e [Re], the conditional regret of the constrained hinge loss can be lower-bounded as
A J6 (1) inf sup helt peR
(( h(, max (0, 1+ (mxx (x)) 11) + ( - max 1+ h(z, pı(()) pn)
2 -(c,, P({
(differentiating with respect to μa, h to optimize)
Therefore, by Lemma 4.4, the conditional regret of the top-k loss can be upper bounded follows:
AC (k,, (h, - ((x))((())))p,,,)) -
kAC Iningn (h,
By the concavity, taking expectations on both sides the preceding equation, we obtain
El2 (h) E7, (3C) Me, (3() S k( Enange (h) E
Eninge (H) + M (30):
The second part follows from the fact that when the hypothesis set H is sufficiently rich such that AT A (H) O, have My (H) O.
Case IV: Festnd = p. For the constrained p-margin loss 7pp the conditional regret can be written
AC; ge xh,
Σ
plxxx (t,,,), heTf y-1
inf Σ p(x, (h,
5-1
p(x. v) (b,,,, Σ
inf Σ p(2, y) (hp,,, v); uei y-1
1-1
where for any i [k],
h(x,v),
y h,))))),,,
h2, v)
(z))
y= (2)
hx), - y (x))
Note that such choice of a leads the following equality holds:
Σ p(a, (,, ve (h)(
Σ
plz.y) (h..s
(x))
Let q(x, (x)) 1- p(z, (x)) and g(z, hx))) = 1- p(x, h (z)). Therefore, for any i e [1e] the conditional regret of the constrained p-margin loss can be lower-boune bounded as
(er,,e((,,))
((I,, (x))) min max (, 0, 1+ (xx
,1 min max 0, M(r, (x,,h1())))1 -1
2 inf sup besk uez
P
0,1 + ((x,,,(x))) min max((,, 0, 0, h(z,
min max 0,1+ h(z, + -( P
2 2g(z, - (((()))))(((,(()) (x))
(differentiating with respect to μ. h to optimize)
-() h(),
24

---

Therefore, by Lemma 4.4, the conditional regret of the top-k loss can be upper bounded as follows:
Ar, (h, p6ote. KAC, 3x T (h,
By the concavity, taking expectations on both sides the preceding equation, we obtain
Eee (h) εú, (IC) Me, (3C) (z, (h) E7, (3() + My, (16).
The second part follows from the fact that when the hypothesis set HC is sufficiently rich such that Ar, (IC) = O, we have My, (I() = O.
25

---

G Technical challenges and novelty in Section 4.2
The technical challenges and novelty of proofs in Section 4.2 lie in the following three aspects:
(1) Conditional regret of the top-k loss: This involves a comprehensive analysis of the conditional regret associated with the top-k loss, which is significantly more complex than that of the zero-one loss in a standard setting. The conditional regret of the top-k loss incorporates both the top-k conditional probabilities (x))), for I....,,k, k, and the top-k scores h:()), for 1,...,, k; as characterized in Lemma 4.4.
(2) Relating to the conditional regret of the surrogate loss: To establish H-consisteney bounds, it is necessary to upper bound the conditional regret of the top-k loss with that of the surrogate loss. This task is particularly challenging in the top-k setting due to the intricate nature of the top-k loss's 's conditional regret. A pivotal observation is that the conditional regret of the top-k loss can be expressed the sum of & terms (p(x, p.(2)) p(z, (æ))) for i 1...... k. Each term (p(x,,;()) p(x, h; (x))) exhibits structural similarities to the conditional regret of the zero-one introduce series of auxiliary hypotheses ha,, each dependent on hx) and pz()) for i [k]. This approach transforms the challenge of upper bounding the conditional regret of the top-k loss into & subproblems, each focusing upper bounding the term (p(x, (+)) - pp(2, (x))) with the conditional regret of the surrogate loss.
loss, (p(2, Pi (z)) p(z, hi (x))). Consequently,
(3) Upper bounding each term (p(x, (=)))) (())) Following the approach in prior work [Mao et al., 2023f] for top-1 classification, we define (y,( as:
M(r,y), (og(e)(e.)(())) + #) log ((xhet()))))))) pb)
u$ h,,))
h (x,
y )=)(
y p=))
for the proof of comp-sum losses (Theorem 4.5). The subsequent proof is considered straightforward.
However, for the proof of constrained losses (Theorem I) adopt different hypothesis formula- tion for à (I, y). leveraging the constraint that the scores sum to zero and the specific structure of constrained losses. The hypothesis is defined as:
h(2,y): v): + pz) ((),h, p (z)(x)).
y (p)))))
(x,
(z),
The remainder of the proof then specifically addresses the peculiarities of constrained losses, which significantly diverges from the previous work.
In summary, aspects (1) and (2) are novel and represent significant advancements that have not been explored previously. For aspect (3), the proof for comp-sum loss closely follows the approach in [Mao al., 2023f], which appears straightforward due to the innovative ideas presented in aspects (1) and (2). However, the proof for constrained losses significantly deviates from the previous work, particularly in terms of the new auxiliary hypothesis formulation and the specific constrained losses examined.
We would like to further emphasize that these results are significant and useful. They demonstrate that comp-sum losses, which include the cross-entropy loss commonly used in top-1 classification, and constrained losses, H-coonistentt in top-k classification for any k. Notably, the cross-entropy loss is the only Bayes-consistent smooth surrogate loss for top-k classification identified to date. Furthermore, the Bayes-consistency of loss functions within the constrained loss family is novel exploration in the context of top-k classification. These findings are pivotal as they highlight two broad families of smooth loss functions that are Bayes-consistent in top-k classification. Additionally, they reveal that these families, including the cross-entrops loss, benefit from stronger, non-asymptotic and hypothesis set-specific guarantess--f-conisstt bounds-in top-k classification.
26

---

H Generalization bounds
Given finite sample S ((11, (11,,,1),--- (3im; (m)) drawn from D let hig be the minimizer of the empirical loss within H with respect the top-k surrogate loss E: hg argmin (
argmin Ei= 2 Vs). Next, will show that we use K-consistency bounds for i to derive generalization bounds for the top-k loss by upper bounding the surrogate estimation error (gsss) Eg (H) with the complexity (e.g. the Rademacher complexity) of the family of functions associated with Z and H: Hy ((x, g) ~ =(,, E...
Let R (HI) be the Rademacher complexity of Hy and By upper bound of the surrogate loss Č. Then, we obtain the following generalization bounds for the top-k loss.
Theorem H.1 (Generalization bound with comp-sum losses). Assume that H is symmetric and complete. Then, for any 1 k n, the following top-k generalization bound holds for hs: for any O, with probability at least 1 over the draw of an i.i.d sample S of size m.
Exg (Tis - E7g (H) MA, (H) S kap-1 (3) (3)) 2BBV
log 3
+ M2(30)
2m
log(1 1 - where (11) = 1et
ltt log(1 (1 1), LE [0,1] when E. is Flogi v1(1) = 1 v1 12, l [0.1]
2
2
(1+1) 1 (1-()) 1-2
when e is Tespi (t)) t/n when E is Emncc and (t) gred
for all
E (0, 1). E [0, 1] when is Egon-
Proof. By using the standard Rademacher complexity bounds [Mohri al., 2018), for any 8 with probability at least 1 - 5, the following holds for all h E HH:
[ex(1) - -0,0) (t)) (
(H) + BaV
[og(2/5)
2m.
Fix By the definition of the infimum, there exists h" 36 such that Eg(h²) s EG(3) + By definition of hs, have
{7()ss -
Eg(his - Eg, (hi)) + Zg, (3()
83(hs) Eg (hs) + E g (J(
Eh(hs) E7,0 (hs) + E (h') Eg(h" +
2 29 (H) BTV
(og(2/6)
+
2m
Since the inequality holds for all > 0, it implies:
- & 49 (J) 2BBV
log(2/8)
Plugging in this inequality in the bounds of Theorem 4.5 completes the proof.
Theorem H.2 (Generalization bound with constrained losses). Assume that H. is symmetric and complete. Then, for any & k S n, the following lop-k generalization bound holds for Tis: for any 8 with probability at least 1 - 8 over the draw of an i.i.d sample S of size m.
Etg, (Ti) Ei, (H) M,) S koy 499 ()()) (H) 2BB
log
MG(0).
where ((t) 2 when ? is either foxp or E hinge (t) when is either Eninge or pp..
Proof. By using the standard Rademacher complexity bounds [Mohri et al., 2018], for any 8 0. with probability at least - 8, the following holds for all h H::
[,7hh) - - (h)) 2
12R (3() + BTV
log lng(2/8) (2
27

---

Fix e O. By the definition of the infimum, there exists h" H such that Ez(h") s (7(3)) + c. By
definition of hgg we have
- (H)
Eg(hs) 22 (1s) &[, ()()
s Ez(hs) - Eg (s)) + (
(h') (J()
8hshs) 8g,3 (1s) + Eg hh*) Eg(h" + e
2 20 (H( + BB log(2/6)
+ c.
2m
Since the inequality holds for all E > 0, it implies:
(hs) - (J)) & 49 (3() 2B
log(2/6)
2m
Plugging in this inequality in the bounds of Theorem E.1 completes the proof.
To the best of our knowledge, Theorems H.l and H.2 provide the first finite-sample guarantees for the estimation error of the minimizer of comp-sum losses and constrained losses, with respect the
top-k loss, for any S S n. The proof' use our H-conssstency bounds with respect to the top-k loss, as well as standard Rademacher complexity guarantees.
28

---

I Proofs of H-consistency bounds for cost-sensitive losses
We first characterize the best-in class conditional error and the conditional regret of the target cardinality aware loss function (2), which will be used in the analysis of H-consistency bounds.
Lemma 1.1. Assume that R is symmetric and complete. Then, for any K and x X, the best-in class conditional error and the conditional regret of the target cardinality aware loss function can be expressed as follows:
e7 (R, min
yey
AC (r,
Σ E( yey
min Σ (((x,))(xz,kk)))
keek yey
Proof. By definition, for any r R and é X, the conditional error the target cardinality aware loss function can be written
Cx(r,z)= = Ep(e,))((er(()..))
BEy
Since R symmetric and complete, have
ej (R. inf Σ ((z ret yey
min Ep(x,y) hesk yey
Furthermore, the calibration gap can be expressed as (r, (e(r, (R, Σ E((x,))ce
min Ep(x,y)(aa,k: keck
y
yey
which completes the proof.
L1 Proof of Theorem 4.6
For convenience, let clr,k.y) (=.))
c(t,kyy, ((.,k) Eyey p () We also let (1) argmin (1 q(., k))
[0,1] and 8(r,k) Expreraa argminkex Eyey p(u, v)((r,kyy)
Theorem 4.6. Assume that R is symmetric and complete. Then, the following bound holds for the cost-sensitive comp-sum loss: for all r R and for any distribution,
(r(r) - Ex (R) Mc(R) (87 & (r) 87 Tomo (R) + M 7 (R)):
When R = Rall, the following holds: (r(r) E, (Rat)) S 1.877-0m (r) E7
En-aam (Ran)): where
(t) 2-7 when Ec-comp either To-log or Ex-expi 7(t) 2//x3/ when Ec-comp le-goei and
(t)) = [J[tt when Eo- Eo-comp is Pc-mae.
Proof. Case I: To-comp To-log For the cost-sensitive logistic loss Ec-log the conditional error can be written
(z,A)
Cr log (1,z)= (r,))=-Ep(r: E(z,k, log
Σ (og(
e ex(z,(r)
ye
keX
beck
The conditional regret can written as
AC, R (r,2) = Σ (og(5(z,))))(z.
inf
- Σ 1og(5(zz
keck
neR
back
2
Σ 1o)
inf μel ())_
Σ (0
keck
bec
29

---

8(I,y),
$ (kmiu (x), r(x))
where for any I and k e X. (z, S(I, Kerikiiin (x)) +
y r(z)
Note that
8(x,r(x)) p
y = Kmin (x).
such choice of s leads to the following equality holds:
Σ (og(8(z,)))T(z:)) ke)r(s).
E
log(S (z,
ke(r(z) Ammtn
Therefore, the conditional regret of cost-sensitive logistic loss can lower bounded as
AC₃ 26
2
sup + + (())(()))) (og (8(x, r(x)))
(xx, kmiu
kiii (x))) (()) -()))
(e)))()
((,(S(z, Kimin (x)) + m)]
By the concavity of the function, differentiate with respect to μt, we obtain that the supremum is achieved by n² ((x.))))) (2)) (=r)((()))))))) Plug in j²,, we obtain
(zz (T)
AC Ae or (h,z)
(8(x, r(x))) + 8(x, kimin (I) (z))) kmin
2 (,, kmin (min(()) log
8(x, kmin (z)) (z, kimn (x) (x)))
(8(x, ((:)) (xx Kmin (v) (x))) r(x))
+ r(xxr(())) log
S(z, ((z) (F kmin (x) (zz,
2g(2: Φ. Kimin (x))
27(x,r(1)))
2 (2,, Kmin (x)) log ((x, (imin())) (I)) (æ, r(x)) { r(x)) log (2. kiiin (x)) + ((. r(x))
(minimum is achieved when 8(x, (1)) 8(2; Kimin (z)))
(7(2, (())) (2 kmin (z)))
2(7(x, ((:)) + (1,, Kmia (x))
(a log a+b
2a
blog 2b
(e-b)² (a+b)
Va, b [0, [Mohri al., 2018, Proposition E.7])
a+b
r(x)) ((x, kmin (x)))
(0 ((x,, (x,, kinin (+)) s 2)
Therefore, by Lemma I.1, the conditional regret of the target cardinality aware loss function can be upper bounded as follows:
ACt,((, 7(2 kimi (x))
-z))) (x,,
(n (T.z))²
By the concavity, taking expectations on both sides of the preceding equation, we obtain
Ex(r) - & (R) + MR) S 2( & (r) E (R) + My (R) 1
The second part follows from the fact that My (Ral)= 0.
Case H: To-comp = Te-esp For the cost-sensitive exponential loss Tc-exp- the conditional error can be written as
Cr (r, Σ E((,,)) Σ k1 Σ (())))(())))) Σ
8(x,k) 1 )(( A:).
yey
beck
Kakk
keck
The conditional regret can be written as
Ae R (r, = Σ
[1,kk)
inf reR
Σ
1 (((x
8(x,k)
8(2,k)
keck
keek
Σ
1
- 1)((x,t)
inf
Σ
1
keck
8(2,
k)
w (2)),
Welk
S,(2,k)
30

---

8(I,y),
$ (kmiu (x), r(x)) r(z)
where for any I and k e X. (z,
S(x, Kinik (x))
Note that
8(1, 1
y Kmin (2)).
such choice of s leads to the following equality holds:
((1,k)=
E ke(r(a) Mann (2))
1 Jace,A).
8(x,k)
(x,
Aoe (r(r(()) (1))
Therefore, the conditional regret of cost-sensitive sum exponential loss can be lower bounded as
1 8(x; kimin()) S(x, - pa
C exp (h. wel (m
sup
((x, kmii(())
+ (1, (x)))
8(x,r(x)) 8(x, Kmin (2)) +
By the concavity of the function, differentiate with respect to μ4, we obtain that the supremum is achieved by n
(o Plug in μ², we obtain (mia()))))((((()))))))))))))))))
(=))
AC, Ce (h,
(o(mn,iimmn ((x, kmin (I)) ((,r((x))) (Vile, (Vi (i)in()))++ ((())
(i), (x)) 8(x,r(x))) 8(x,kimin (x)) S(x, r()))
2 ( (1x, kiii
( (<))))
(minimum achieved when 8(x, r(x)) 8(x, kmin (x)) =
7(x, Kmin (x)))
(V)(z,((x))) (Ix kmin (x))
2 (q(x,r(x))) ((,, kimin (ini)))))) (1)))²
Vb++bss,y Va, be [0,1],a 2)
4
Therefore, by Lemma 1.1, the conditional regret of the target cardinality aware loss function be upper bounded as follows:
A ((2r, kimin (x)) ((x,,(x))) s Ae com (r:
By the concavity, taking expectations on both sides the preceding equation, obtain
Ex(r) & (R) (R) s 2 & exp (r) - Ex cay
(R) + Mr cap
(R))
The second part follows from the fact that My (Rall) = =0.
Case III: T c-coomp -oo-gee For the cost-sensitive generalized cross-entropy loss To-gro the condi- tional error can written as
Σ El k.) ( (a,,))
Evee (
Croggo (1,z) = Σ p(x,))
yEy
beek
ketk
The conditional regret can be written as
DCT Ae
(1-
inf reaR
(1-8(z,))) (zz,)))
9 kelk
ke
[ {(=),((c,)))))(.t)))
Σ (1 - S(x, {z))
inf
ke
[el-S(2.kmnn (=)).
kex
31

---

8(I,y),
$ (kmiu ( (2), r(x)) r(z) y Kmin (2))
where for any I and k e X. (z,
S(x, Kerikiii (x))
Note that
8(2, 1
such choice of s leads to the following equality holds:
Σ 1
Σ ke(r(ss (x)) keeK
E1 (1- (x1
kmmr( (1)) 9 ke
Therefore, the conditional regret of cost-sensitive generaaiie generaliizedooss-entrrryy loss can be lower bounded as
1
A Te 26 (h,
sup 9 (el-8
((1, Niniiiiinn (innn)innn (xnin))))))))) (())
+ + (=)), (8(z, Kmin (1)) [1) [})
By the concavity of the function, differentiate with respect μ. obtain that the supremum is achieved by n = (((..()))) Fi (isthmant)) Plug in p², we obtain a(2,kmin (x))
-()(r)))))
A se se (1)
(S(x, S(x, kmi, (m) kmi (() 1-9
(e, kimin (x)) Kmin (z))² q
(()
q
29((( kimi (x)) a(x ((x))))) ( - (0x, kmin (x)) - ((x; (+))
2
(minimum is achieved when 8(xr, rx))) 8(x, (x)) xt)))
(Txxr(()) T(x, Kinin (I)))²
4/370
1-g
1- +6
1-
ath 2
{a (a-b)) Va, [0, 10.10,0s0 sa
2
Therefore, by Lemma I.I, the conditional regret of the target cardinality aware loss function can be upper bounded as follows:
AC (r, x)) qxx,, himin (x)) g(<, r(x))) & 2/x1 (se; xce. x (r, (r,
By the concavity, taking expectations on both sides of the preceding equation, obtain
Ex(r) - E Mc(R) 2
( ( (r) E (R) + + 200
(R)
The second part follows from the fact that M7 go0 (Ral)) O.
Case IV: Eo-camp = Fe-mae- For the cost-sensitive mean absolute error loss Fc-maes the conditional error be written
(zz k.w) 11)
Exres en(en)) -xeeeeenzan)))
e'(2,(t)
))= Σ (1 (1- (())
e mac
(r, Σp(r,))
ye
ked
ke
The conditional regret can written as
DCC & (r, = Σ
inf FeR
- (11-8(2,k)
keck
ke
2 Σ (1-
inf me ((1-S(z (=)))
Σ ((1
k
ke
32

---

8(I,y),
$ (kmiu ( r(x)) r(z)
where for any I and k e X. (z,
S(x, Kinin (2))
Note that
8(1,r(x))
1
y Kmin (x).
such choice of s leads to the following equality holds:
E(- 811
ke
Therefore, the conditional regret of cost-sensitive mean absolute error can be lower bounded
AC, AC M Ne (h, 2
sup (4-
7(2, kmia (x)) kmmn (z)) + 8(x,r(x)) -4
((,,
+ S(x, kimin (x)) ml]
By the concavity of the function, differentiate with respect to μt, we obtain that the supremum achieved by μ² -81r kmin km)n(r)). Plug in μ we obtain
A T mar x (h, x)
2 (x, kmin x ) 22 - ((2,
(7(2, Kmin (x)) -ar, [
(minimum is achieved when (xx,,(()) {
Therefore, by Lemma I.I, the conditional regret the target cardinality aware loss function can be upper bounded as follows:
( (x,,, kmin (x)) - (xx (a:)) [ (Ae F & (r,
By the concavity, taking expectations on both sides of the preceding equation, we obtain
Ex(r) E7 (R) Mc(R) (X7( Ez-maoo (r) Ex
(R) My (R))
Eg-mae
The second part follows from the fact that My Yo-man (Rall) =0.
I.2 Proof of Theorem 4.7
The conditional error for the cost-sensitive constrained loss be expressed follows:
Ca (1,x)
Ep(r, Po-rstt (r,
wey
Σ p(x.v) Σ [dd
yey
beek
Σ ((),
where ((r,k) k) ((,,), e [0, 1]. Let kimin (2) argminkex ((x,k) k). We denote by P Pexpit it -t the exponential loss function, o D hinge: t + max (0, 1 t)² the squared hinge loss function, $ Diugee i + max 1 1- the hinge loss function, and 4 pp min min(max (0, t/p), 1}. p> O the p-margin loss function.
Theorem 4.7. Assume that R is symmetric and complete. Then, the following bound holds for the cost-sensitive constrained loss: for all r R and for any distribution,
Ex(r) E7) M,,+) s 7
[E cand (r) - E7 caund (R) M
cound (R)):
When R = Ran. the following holds: Ex(r) (Rai)) 7(27, (r) Ex En (Rau)), where Testud
(t) 2vt when Fo-ested is c exp or he-sq-hinger (tt) when Eo-ostad is le-hinge to-p-
33

---

Proof. Case I: f== festnd regret can be written as
For the cost-sensitive constrained exponential loss festnd
c- exp: the conditional
c- exp'
Karnd exp
Rt (T) = Σ [(2 (xxpp())))
inf reR
Σ
k) Pexp (-r(x,
be
kE
2
Σ
((. k) 2 exp (-xx((x((,)))
inf Σ
7
x, k
Pexp (-r
kec
peR
ke
r(w,y):
y {kmin (r),
where for any k E K, (2, R-)
(xx kmiu ( ( r(z,r(z)) 4
y (x)
Note that such choice
y kmin (x).
of ry leads to the following equality holds:
Σ kl (-r((=(x,),))
Σ
ke(r(=))Nnnin(>)) (1))
Rair())) (x)) kelk
Therefore, the conditional regret of cost-sensitive constrained exponential loss can be lower bounded as
AFornd eap se (r, x)
2 inf Sup(T(z kmin + -( (1))+))) recl NeR
(Volz, kmnn VV r(())
(differentiating with respect to μ., r to optimize)
2
((x,((x)) T5,, kimin (2:)
Vi(z, hinin (x)) v 7 (xx))
2 4
WI, Kiinn (x)))
(0 < q(, k) s 1)
Therefore, by Lemma I.1, the conditional regret the target cardinality aware loss function can be upper bounded as follows:
ACe,((r,
[ kinin (x)) s 22 Ferend at (r, exg
By the concavity, taking expectations on both sides of the preceding equation, obtain
Ee(r) ER) M,(RR) 2 Eoornd (r)
Exentta (R) cap
M Mysund (R)
The second part follows from the fact that M Missudd (Rau) 0.
Case II: é hinge- For the cost-sensitive constrained squared hinge loss To-eg-hinge, the conditional regret can be written as
AC Varm--iingo R (r,
Σ
(x. c k) Mirge
inf reR keck
Σ n k:) 1 sq- hinge (-r(z,)))
keck
Σ bee
(x, k) hing (-s-- (-r(z,h))
hinge
inf peR
Σ [(x 2 (irgg-bigng-rr_______
keek
where for any & E K,
r(x,w),
y (x), r(x)}
r(z, kmin (2)) + r(x,)(x)) 1
y r(x)
y = kinn (x).
Note that such choice of rn leads to the following equality holds:
Σ
[x, ko t sq hingo (-r(x,
Σ
ETT, (x, k) hingo (x,
(m(r(2)).Nmin(l)) (1))
( Kumin (x)) keIk
34

---

Therefore, the conditional regret of cost- cost-sensitive constrained squared hinge loss can be lower bounded
AC tim (r,
2 inf sup (xx, limin (x)) max (0, r(2, kimi max (0, 1 r(2, m)²) rel pel?
[(. ((xx)()))))) (max
max(0,1++(z; kmin /1) 1²)²)
1
2 kmin (()
(differentiating with respect to μ4, r to optimize)
Therefore, by Lemma I.1, the conditional regret the target cardinality aware loss function can be upper bounded as follows:
A (r, x) = q(z, r(x) (xx, kmin (x)) s 2 Ae
mingige x (7, (r))))
By the concavity, taking expectations on both sides of the preceding equation, obtain
Ee(r) E (R) Mc(R)
2 E (r) E
(R) My Zoreoggg-ingg hings (R)
hinge
The second part follows from the fact that M7 (Rall) = O.
Case III: = Zo For the cost-sensitive constrained hinge loss Eo hingos the conditional regret can be written as
ACt Ae (r,
Σ [(. P (- inf Σ T(x, P (-r(2; (0.k))))) k))
beek
ret be
Σ beck
(x. kb Phinge (-r(x,k))
inf
Σ ( k) 8 Phingol--7709 (2)))))
k)
k)),
fe kec
where for any & K,
r(x,y):
$ {kimi (x), r(x)}
(x( k)
r(z, kmin (I)) +
(x)
r(x, (x))
y kiin (x))
Note that such choice of ru leads the following equality holds:
Σ (r, ()nnno))nnoo(r (-xx,) ké(r(x) (x)) ke
Σ Σ
(-r k)).
(6(r(x).kmmnnf (x))
Therefore, the conditional regret of cost-sensitive constrained hinge loss can be lower bounded
AC, ie (r,
2 inf sup q((,, kmiu netk pelt
kmin kmin
- p3)
-m Kmin (x)) n1))
+ (()))(
2 29(2,r(z)) qx, Kmiin (=)).
(differentiating with respect to p. r to optimize)
Therefore, by Lemma I.1, the conditional regret of the target cardinality aware loss function can be upper bounded as follows:
AC, A (()r((2)) - (x, Sm)n(x)) ACT tinge R 2).
By the concavity, taking expectations on both sides the preceding equation, we obtain
Eς(r) - ( (R) MM(R) E (r) Ex
E..nninn (R) M
My Eg-hingg (R).
The second part follows from the fact that M hinge (Rait) O.
35

---

Case IV: 1V: For the cost-sensitive constrained p-margin loss Ec-ps the conditional regret can be written
CC R (r, Σ ((2,k)
inf (( ()
heN
NER keEK
2 Σ
inf Σ T(r,k) ((
ke
weR bex
where for any & K,
rx,,))
1/ $ {kimin (2), r(x))
(r, k)
r(z, kmin (a)in(()))) +
= ((x)
r r(x,r(x))
y = kimn (z).
Note that such choice of Tp leads the following equality holds:
Σ (<<, (4(((()).mmin) (x)) ketk
Σ ((
k+(r(=)) Fmin (1))
Therefore, the conditional regret of cost-sensitive constrained p-margin loss can be lower bounded as
ACT ACT.,. (T.2)
(x, kmin (I)) min max 0,1+
r(x, Kein (x))
f.1 min max 0,1+ r(x,)())) )11) )1
2 inf sup rec pel
).)) min max 0, r(x, kmin (m)nk)))) + min max 0,1+ r(a,)(x))
+ ाअ, rxx))
P
2 72, (())) [x, kmin
(differentiating with respect to μ. r to optimize)
Therefore, by Lemma I.1, the conditional regret of the target cardinality aware loss function can be upper bounded as follows:
AC (())) (xx k=))n())) s AC (r,
By the concavity, taking expectations on both sides of the preceding equation, obtain
(x(r) (R) + Mc(R) εq (r) - E7 (R) My (R). The second part follows from the fact that My (Rall) = 0.
36

---

0.90
0.95
0.94
0.90
0.90
0.86
classifier
topk
cardinality aware, = 0.05
cardinality A 0.05
0.82
cardinalit aware,
0.80
cardinality-ware. A-
cardinality-sware =
0.75
cardinality 0.01
0.78
12
Cardinality
Cardinality
CIFAR-100
ImageNet
0.30
0.96
Accuracy
0.96
0.92
classitter
0.30
cardinaliy--waars A- 0.05
0.92
cardinalityssware, A00.0
cardinality aware, A
cardinality aware, 0
cardinality- A=0.01
0.90
cardinally-awere. A=0.01
2.0
2
Cardinality
Cardinality
CIFAR-I0
SVHN
Figure 5: Accuracy versus cardinality on various datasets for cost(Ig((x))) = log k. Each curve of the cardinality- aware algorithm is for fixed value of À and the points the curve obtained by varying the number of experts.
0.94
Accuracy
Accuracy
0.85
0.86
top-k
0.80
top-k
wardnsilty-wware, d8) look
cardinality aware, dl logk
cardinalty-sware. d(k) k
cardinality-aware dl =
0.76
10
10
Cardinality
Cardinality
CIFAR-100
ImageNet
0.98
0.90
0.96
Accuracy
Accuracy
0.94
0.92
0.90
top-k
serdin llog
cardinality logk
0.88
cardinality aware, ckk
0.90
cardinality-aware ckk-
1.0
1.5
2.0
255
3.0
35
4.0
1.0
15
2.0
25
3.0
35
4.0
Cardinality
Cardinality
CIFAR-10
SVHN
Figure 6: Accuracy versus cardinality various datasets for (ost((x((x))) log k and cost((g((x)) k, with À = 0.05. The points on each curve of the cardinality-aware algorithm obtained by varying the number of experts.
Additional experimental results: top-k classifiers
Here, we report additional experimental results with different choices set K and cost( (=)) on benchmark datasets 100, CIFAR- 100 [Krizhevsky, 2009], SVHN [Netzer al., 2011], 1]. and ImageNet [Deng et al., 2009] and show that our aodinaality-waar algorithm consistently outperforms top-k classifiers across all configurations.
In Figure 5 and Figure 6, we began with set K {1) for the loss function and then progressively expanded it by adding choices of larger cardinality, each of which doubles the largest value currently in K. The largest set K for the CIFAR-100 and ImageNet datasets is 21, 4, 8, 16, 32, 64), whereas for the CIFAR-IN 10 and SVHN datasets, is {1, 2, 4, 8}. As the set K expands, there is increase in
37

---

0.35
0.90
Accuracy
0.85
0.80
conformal prediction card-aware, 500,000
0.70
Cardinality
Figure 7: Accuracy versus cardinality on an artificial dataset for different training sample sizes m.
both the average cardinality and the accuracy. Figure shows that the accuracy versus cardinality curve of the cardinality aware algorithm is above that of top-k classifiers for various values of X. Figure 6 presents the comparison cost gx (=)]) = and cost(lg((2)) = log & for X 0.05. These results demonstrate that different À and different cost( ga (x))) basically lead the same curve, which verifies the effectiveness and benefit of our algorithm.
K
Additional experimental results: threshold-based classifiers
We first characterize the Bayes predictor r' this setting. We say that the scenario deterministic if for all X, there exists some true label y such that p(x, v) 1; otherwise, we say that the scenario is stochastic. To simplify the discussion, we will assume that [gx())) is an increasing function of k. for any x.
Lemma K.1. Consider the deterministic scenario. Assume that (c)))((ga()))) 1 for all & and x E X. Then, the Bayes predictor r" for the cardinality- aware loss function satisfies: r rx() argminkyeesss) ki that is the smallest k such that the true label y in (x)).
Proof. By the assumption, for < rr' (a). , we can write c(ar, (x),,) (co) s 1 (tta(>) Acost(lgx (z)l) c(2,k; k. y). Furthermore, since |gx (x)) is an increasing function of have c(x, r" (x). = (cost((Er(s)) s Acost(lg (x)1) = cxx, k', .)) for (2).
Lemma K.2. Consider the stochastic scenario. The Bayes predictor r² for the cardinalit-awaare loss function satisfies:
r' (x) = -rrggin Acost((B((x))) Σ p(c.1))
bEE
vEg((*)
Proof. The conditional error can be written follows:
Ce(r,n,y) ((xx,)c(xx,r()))
yey p(z v) (() (x))(()())())))
wey
Σ v) v )cost((
gey
Σ
p(x,y) (cost((B(()))))
(a)
Thus, the Bayes predictor can be characterized as
r" (I) argmin
(cost((B((x))) Σ p(z.v) (=))(*)
keek
38

---

0.95
Accuracy
0.90
Accuracy
0.90
0.85
0.80
conformel prediction
0.80
conformal prediction
cardinality aware aware
cardinality-
0.75
20
30
40
60
300
400
500
600
700
800
Cardinality
Cardinality
CIFAR- 100
ImageNet
0.95
0.55
Accuracy
0.90
Accuracu
0.85
confornal prediction
0.80
confermal prediction
cardinality-aware
cardinalit--awine
0.75
Cardinality
Cardinality
CIFAR-10
SVHN
Figure 8: Accuracy versus cardinality on CIFAR-100, ImageNet, CIFAR-IO, and SVHN datasets.
It is clear that Lemma K.2 implies Lemma K.1 when there exists true y y such that p(r, and (cost((Bx<x))) s 1.
We first consider artificial dataset containing 10 classes. Each class is modeled by Gaussian distribution in 100-dimensional space. As in Section 5, we plot the accuracy versus cardinality curve of the cardinality-awai algorithm by varying A, where the set predictors used are ptreshold-based classifiers, and compare with that of conformal prediction. In Figure 7, we also indicate the point corresponding r". The problem is close to being realizable, almost as well as y* on the test set. Thus, the minimizability gaps vanish, and our H-consistency bounds (Theorems 4.6 and 4.7) then suggest that with sufficient training data, we can get close to the optimal solution and therefore outperform conformal prediction. For some tasks, however, the problem is hard, and it appears that very large training sample would be needed. Figure 7 demonstrates that on the artificial dataset, with training sample size m 50,000, the performance of our cardinality-aware algorithm is only slightly better than that of conformal prediction.
can train predictor that performs
increase the training sample size to m 500, 000,, then the curve of our algorithm becomes much closer to the optimal point and significantly outperforms conformal prediction.
Additionally, for a weaker scoring function, smaller training sample suffices in many cases, and cardinality- algorithm can outperform conformal prediction real datasets shown in Figure 8.
L Future work
While our framework of cardinality-aware set prediction is very general-applicate any collection of set predictors (Section 2)-and and leads to novel cardinality-aware algorithms (Section 3), benefits from theoretical guarantees with sufficient training data (Section 4), and demonstrates effectiveness and empirical advantages in top-k classification (Section 5), the learning problem can be challenging for certain tasks, often requiring a very large training sample (as shown Appendix K). This underscores the need for more detailed investigation to enhance our algorithms in these scenarios.
39

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See lines 81-86 in Section 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Appendix L.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
40

---

Justification:
See Section 4, Appendix A, B, D, H. and I.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yss]
Justification: See Section Section 5, Appendix and Appendix K.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
41

---

Answer: [Yes]
Justification:
See Section 5, Appendix and Appendix K.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/ /otdddee/ooeeuummissttteseeeesee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips. wttpccccppppcccaceee /ttie//euuieeeeouuuuuibiiiiii
/Codeeeooiissseeeeee cestsummissioooo ssion onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See Section 5, Appendix and Appendix K.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
See Figure 2, Figure 5, and Figure 6.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
42

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
For each model training, we use an Nvidia A100 GPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: / http///eerip...// wwwtrrps.ccppuuuue
Answer: [Yes]
Justification:
The authors have reviewed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is theoretical in nature and we do not anticipate any immediate negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
43

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: See Section 5, Appendix J and Appendix K.
Guidelines:
existing assets. The authors should cite the original paper that produced the code package or dataset.
The answer NA means that the paper does
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (c.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
44

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
45


Reviews:
[{"review_id": "VDq57KiuYL", "reviewer": "Reviewer_TDsY", "summary": "The paper introduced a new cardinality-aware set prediction algorithm with cost-sensitive comp-sum and constrained surrogate losses. Additionally, the paper established theoretical guarantees for top-k classification with fixed cardinality k using the H-consistency bounds. Finally, experiments on linear classifiers show the superiority of their algorithms.", "questions": "1. Can we estimate the $M$ in H-consistency bounds?\n2. Authors claim the framework includes the standard conformal prediction, so do some relationships exist between the H-consistency bounds and coverage bounds?", "limitations": "The authors have adequately discussed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is presented clearly and is easy to follow.\n2. The paper considers the set prediction, which is a novel setting in recent years.\n3. The paper proposes new algorithms with rigorous guarantees and good performance on various datasets.", "weaknesses": "1. Since the theoretical results include the neural network class as a special case, the experiments should additionally consider training whole neural networks on the mentioned datasets (at least CIFAR), which is more important in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your encouraging review. We will take your suggestions into account when preparing the final version. Please find responses to your specific questions below.\n\n**Weaknesses:**\n\n**1. Since the theoretical results include the neural network class as a special case, the experiments should additionally consider training whole neural networks on the mentioned datasets (at least CIFAR), which is more important in practice.**\n\n**Response:** The main focus of our cardinality-aware algorithm is in training the cardinality selector $r$, which we do in fact implement as a neural network. We used a two-hidden-layer feedforward neural network, which aligns with the assumptions of our theoretical guarantees for cardinality-aware surrogate losses. The base classifier $h$ is derived from well-trained neural networks (ResNet for CIFAR-10, CIFAR-100, and SVHN datasets; CLIP for ImageNet) with an additional linear model on top. This setup mirrors common practices in the field such as linear probing, resembling the fine-tuning of existing neural network models. \n\nFurthermore, we are happy to report additional experimental results in which the base classifier $h$ is trained on entire neural networks without fine-tuning in the final version. However, we do not anticipate significant differences in results, as our algorithm focuses on training the cardinality selector $r$. The base classifier $h$ in our approach is pre-trained and remains fixed, providing specified costs and inputs to the algorithm.\n\nWe would also like to clarify that our theoretical guarantees in Section 4.3 make no assumptions about the base classifier $h$, which appears in the cost functions. We also assume only symmetry and completeness for the cardinality selector $r$.\n\n**Questions:**\n\n**1. Can we estimate the $M$ in H-consistency bounds?**\n\n**Response:** This is an excellent question. Currently, no general method exists for accurately estimating $M$ from finite samples because the problem seems to require estimating both the best-in-class loss and the average pointwise infimum. However, useful upper bounds can be derived in specific cases. For instance, Theorems 4.1 and 4.2 in Mao et al.'s paper [1] provide bounds for the family of comp-sum losses.\n\nThe challenge of deriving more precise estimates based on samples, along with leveraging known information about the hypothesis set and distribution, remains an interesting avenue for future research.\n\nAdditionally, minimizability gaps are upper bounded by the approximation error, which is often small or even zero in practical applications of neural networks. In cases where the approximation error is zero, minimizability gaps also vanish.\n\n[1] Mao et al., \"Cross-Entropy Loss Functions: Theoretical Analysis and Applications,\" ICML 2023.\n\n**2. Authors claim the framework includes the standard conformal prediction, so do some relationships exist between the H-consistency bounds and coverage bounds?**\n\n**Response:** Yes, our framework covers threshold-based classifiers, including those used in conformal prediction. In conformal prediction, the threshold is determined using an $\\alpha$-quantile based on a scoring function derived from a validation set. However, while standard conformal prediction provides coverage bounds that guarantee a desired $(1 - \\alpha)$ accuracy, it does not provide any guarantee regarding the size of the prediction set.\n\nIn contrast, our approach offers guarantees that account for both accuracy and the size of the prediction set. Specifically, for our cardinality-aware algorithms, $H$-consistency bounds ensure that the cardinality selector $r$ is optimized to minimize the cardinality-aware loss function. This means that each input instance $x$ is assigned the most appropriate prediction set to achieve high accuracy while also keeping the average cardinality low.\n\nTherefore, $H$-consistency bounds provide a stronger guarantee than standard coverage bounds, as they address both accuracy and cardinality, rather than focusing solely on accuracy.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RlKYujAnPX", "reviewer": "Reviewer_5ki4", "summary": "This paper introduces a new loss function for top-k set prediction where k may vary as a function of the input, which the authors call cardinality-aware top-k classification. However, this loss is intractable to optimize in all but trivial cases, so the authors introduce surrogate loss functions for learning these cardinality-aware set predictors, and provide a theoretical analysis of these surrogate losses. The paper also explores the proposed algorithms empirically, on benchmark computer vision datasets.", "questions": "- Out of curiosity, have the authors considered simpler techniques for cardinality-varying top-k prediction, such as setting a total probability threshold on prediction probabilities, and returns the top-k that maximizes the probability, subject to the threshold? At least empirically, it seems like simpler techniques such as this one should be included as a baseline. \n- Is it in fact the case that for \"harder\" examples, the top-k cardinality of the predictions are larger in this framework? Have the authors explored this empirically? Examples of this would strengthen the argument for this new type of prediction.", "limitations": "The authors discuss limitations.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The contribution seems novel -- the authors identify a new type of prediction problem in which top-k sets of input-varying size can be predicted. \n- The introduction of two new surrogate loss functions for optimizing the proposed (but intractable) cardinality-aware top-k loss seems to be a good contribution. \n- Empirically, the authors show on benchmark datasets that by giving up control over specific cardinalities, their top-k predictors can outperform existing top-k predictors that prescribe specific cardinalities a priori.", "weaknesses": "- It isn't immediately clear why the cost-constrained surrogate loss is tractable to optimize, while the original (non-surrogate) loss is intractable. Please clarify this in the text. \n- (clarity of the abstract) The abstract should elaborate on H-consistency and the types of losses being introduced, or discuss these at a higher level. Without knowing what these are prior to reading the abstract, the significance of these is unclear. \n- The usage of the term \"accuracy\" in Figure 1 is strange, as the actual \"accuracy\" definitions vary slightly between the two methods being compared. Additionally, the expected cardinality is used, which makes the comparison strange. Furthermore, this comparison on four benchmark computer vision datasets makes up the bulk of the experimental results. The experimental results section could be additionally strengthened by analyzing other aspects of the predictors generated by the authors' framework, such as the distribution of cardinalities, whether or not harder examples indeed correspond to higher cardinality, the top-k accuracy scores of worst-case cardinalities and best-case cardinalities, and so on. \n- The value of Figure 2 is unclear. What is the significance of making the cost function linear?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback and suggestions. We will take them all into account when preparing the final version. Below please find responses to specific questions.\n\n**Weaknesses:**\n\n**1. It isn't immediately clear why the cost-constrained surrogate loss is tractable to optimize, while the original (non-surrogate) loss is intractable. Please clarify this in the text.**\n\n**Response:** The original loss comprises indicator functions, which are discrete and non-continuous, making them difficult to optimize. In contrast, the cost-sensitive surrogate loss is continuous, smooth, and differentiable, which makes it tractable for optimization. This is analogous to how the zero-one loss is intractable to optimize in standard classification, whereas the standard constrained loss is tractable. We will clarify this point in the text.\n\n**2. (clarity of the abstract) The abstract should elaborate on H-consistency and the types of losses being introduced, or discuss these at a higher level. Without knowing what these are prior to reading the abstract, the significance of these is unclear.**\n\n**Response:** Thank you for the suggestion. We will certainly provide additional explanations about the new cost-sensitive loss functions proposed and their H-consistency guarantees. This will highlight the novelty of our surrogate losses and underscore the strong theoretical foundation of our algorithms.\n\n**3. The usage of the term \"accuracy\" ... and so on.**\n\n**Response:** We use the same definition of accuracy for both methods: for top-$k$ classifiers and cardinality-aware algorithms, accuracy measures the fraction of samples where the prediction sets include the true label. However, the definition of the prediction set differs between the methods. In top-$k$ classifiers, the prediction set consists of the labels associated with the top $k$ scores. In contrast, for cardinality-aware algorithms, the prediction set is determined by the set predictor $\\mathsf g_k$ chosen by the selector $r$.\n\nThe average cardinality appears to be a natural measure of the size of the prediction sets. But, we are open to alternative metrics suggested by reviewers and would be happy to include results based on such alternatives.\n\nWe appreciate the feedback on enhancing the experimental section. We will provide a more detailed analysis of our cardinality-aware algorithms in the final version. Our algorithm dynamically adjusts prediction set cardinality based on input complexity—choosing larger sets for more challenging inputs to ensure high accuracy and smaller sets for simpler inputs to keep the cardinality low. This dynamic adjustment has been validated through our experiments.\n\nIn the global response, we have included two additional experimental results related to this analysis:\n\nFigure 1 illustrates the cardinality distribution for top-$k$ experts $\\mathcal{K} =  \\\\{1, 2, 4, 8\\\\}$ for the CIFAR-10 and CIFAR-100 datasets, analyzed under two different $\\lambda$ values. For a given dataset, increasing $\\lambda$ results in fewer samples with the largest cardinality of $8$, and more samples with smaller cardinalities. This is because increasing $\\lambda$ amplifies the impact of cardinality in the cost functions. When comparing across different datasets, the distribution differs for the same $\\lambda$ due to the varying complexity levels of the classification tasks.\n\nFigure 2 illustrates the comparison of hard and easy images as judged by humans in original quality on the CIFAR-10 dataset for top-$k$ experts $\\mathcal{K} =  \\\\{1, 2, 4, 8\\\\}$. *Hard images* are predicted correctly by our algorithms with a cardinality of $8$ but predicted incorrectly when using a cardinality of $4$ instead. *Easy images* are correctly predicted by our algorithms with a cardinality of $1$.\n\nAdditionally, we wish to emphasize that further experiments with top-$k$ classifiers (see Figures 3 and 4 in Appendix J) and threshold-based classifiers (see Figures 5 and 6 in Appendix K) illustrate the robustness and superiority of our cardinality-aware algorithms.\n\n**4. The value of Figure 2 is unclear. What is the significance of making the cost function linear?**\n\n**Response:** The value of Figure 2 lies in demonstrating that the choice of the cost function—whether linear or logarithmic—has a negligible impact on our algorithm's performance. This highlights its robustness in this regard, as our framework is very general and allows for the choice of any cost function. \n\n**Questions:**\n\n**1. Out of curiosity, have the authors ... included as a baseline.**\n\n**Response:** We have included additional experiments with threshold-based classifiers (Figures 5 and 6) in Appendix K, which demonstrate the superiority of our cardinality-aware algorithms in these scenarios. These include a comparison to conformal prediction, which provides cardinality-varying prediction sets using a threshold on prediction probabilities. We are happy to provide more comparisons as requested by the reviewers.\n\n**2. Is it in fact the case that for \"harder\" examples ... this new type of prediction.**\n\n**Response:** Yes, our algorithm dynamically adjusts the cardinality of its prediction sets based on input instances. It selects larger sets for more difficult inputs to ensure high accuracy and opts for smaller sets for simpler inputs to maintain low cardinality. This property of our algorithm has been substantiated through our experimental analysis. In the global response, we present one example (Figure 2) from the analysis, with additional examples to be included in the final version. Figure 2 illustrates the comparison of hard and easy images as judged by humans in original quality on the CIFAR-10 dataset for top-$k$ experts $\\mathcal{K} =  \\\\{1, 2, 4, 8\\\\}$. *Hard images* are predicted correctly by our algorithms with a cardinality of $8$ but predicted incorrectly when using a cardinality of $4$ instead. *Easy images* are correctly predicted by our algorithms with a cardinality of $1$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GthnlSVGIY", "reviewer": "Reviewer_a6WU", "summary": "This paper proposes a method to handle cardinality-aware top-k classification. It designs an optimization problem where the cardinality of  set selectors is also considered. The authors then generalize it to two types of surrogate losses. Given certain assumptions on the hypothesis set H, the authors theoretically justify their method.\n\n**I must say I am no expert on this domain, so the AC must take my comments wisely.**", "questions": "In some cases, like those generative modeling questions, the cardinality of predictors may be evaluated by measure, meaning the true answer assembles a region of infinite points. Can your method apply to those scenarios where the cardinality is evaluated by measures?", "limitations": "As said in weakness.", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "This paper tackles a very important problem. And achieves, according to my view, a very nice result. The authors manage to transfer the cardinality-aware term into surrogate terms, and theoretically demonstrate their sub-optimal properties. This paper is also very well written.", "weaknesses": "No error bar, very limited evaluation, very strong assumption on the hypothesis set, which is usually not easy to achieve in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your appreciation of our work. We will take your suggestions into account when preparing the final version. Below please find responses to specific questions.\n\n**Weaknesses: No error bar, very limited evaluation, very strong assumption on the hypothesis set, which is usually not easy to achieve in practice.**\n\n**Response:** We will include error bars in the final version, which show minimal variability and do not impact the demonstrated superiority of our cardinality-aware algorithms. We will also follow Reviewer 5ki4's suggestions to provide a more comprehensive experimental analysis of various aspects of our cardinality-aware algorithms in the final version. In the global response, we have included two additional experimental results related to this analysis. The assumptions of symmetry and completeness in Section 4.3 can be met by common hypothesis sets, including classes of linear models and multilayer feedforward neural networks typically used in practice. Note that these assumptions are made on the hypothesis set $\\mathcal{R}$ of the cardinality selector, which we can choose ourselves. We impose no specific assumptions about the hypothesis set of base classifiers $h$ used in our cardinality-aware algorithms, which can be any practical hypothesis set used for various tasks.\n\n**Questions: In some cases, like those generative modeling questions, the cardinality of predictors may be evaluated by measure, meaning the true answer assembles a region of infinite points. Can your method apply to those scenarios where the cardinality is evaluated by measures?**\n\n**Response:** That's a great question. Our method can indeed be applied to those scenarios as well, where the corresponding measure—rather than standard cardinality—is taken into account in the cost function. Our analysis is general and makes no assumptions about costs, which provides flexibility in choosing costs adapted to different cases, including the one the reviewer pointed out. We will elaborate on this in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their insightful comments. We share additional experimental results in the attached PDF, as suggested by Reviewer 5ki4.

Figure 1 illustrates the cardinality distribution for top-$k$ experts $\mathcal{K} =  \\{1, 2, 4, 8\\}$ for the CIFAR-10 and CIFAR-100 datasets, analyzed under two different $\lambda$ values. For a given dataset, increasing $\lambda$ results in fewer samples with the largest cardinality of $8$, and more samples with smaller cardinalities. This is because increasing $\lambda$ amplifies the impact of cardinality in the cost functions. When comparing across different datasets, the distribution differs for the same $\lambda$ due to the varying complexity levels of the classification tasks.

Figure 2 illustrates the comparison of hard and easy images as judged by humans in original quality on the CIFAR-10 dataset for top-$k$ experts $\mathcal{K} =  \\{1, 2, 4, 8\\}$. *Hard images* are predicted correctly by our algorithms with a cardinality of $8$ but predicted incorrectly when using a cardinality of $4$ instead. *Easy images* are correctly predicted by our algorithms with a cardinality of $1$.

Meta-review: The paper introduces a novel cardinality-aware set prediction algorithm that incorporates cost-sensitive comp-sum and constrained surrogate losses. It also provides theoretical guarantees for top-k classification with a fixed cardinality k using H-consistency bounds. Experimental results with linear classifiers demonstrate the superior performance of the proposed algorithms.

Although the paper has a mixed rating, reviewer 5ki4 (with a rating of 4) didn't participate in the discussion nor respond to the rebuttal. I have read the comments, which are mostly related to the presentation, and believe that the rebuttal has clarified the issues.

Therefore, I recommend acceptance.
Decision: Accept (poster)