Building a stable classifier with the inflated argmax
Authors: Jake A Soloff
Rina Foygel Barber
Rebecca Willett
Venue: NeurIPS 2024 poster (2024)
Keywords: Algorithmic stability
set-valued classification
bagging
Primary area: learning_theory

Abstract: We propose a new framework for algorithmic stability in the context of multiclass classification. In practice, classification algorithms often operate by first assigning a continuous score (for instance, an estimated probability) to each possible label, then taking the maximizer---i.e., selecting the class that has the highest score. A drawback of this type of approach is that it is inherently unstable, meaning that it is very sensitive to slight perturbations of the training data, since taking the maximizer is discontinuous. Motivated by this challenge, we propose a pipeline for constructing stable classifiers from data, using bagging (i.e., resampling and averaging) to produce stable continuous scores, and then using a stable relaxation of argmax, which we call the "inflated argmax", to convert these scores to a set of candidate labels. The resulting stability guarantee places no distributional assumptions on the data, does not depend on the number of classes or dimensionality of the covariates, and holds for any base classifier. Using a common benchmark data set, we demonstrate that the inflated argmax provides necessary protection against unstable classifiers, without loss of accuracy.

Building a stable classifier with the inflated argmax
Jake A. Soloff Department of Statistics University of Chicago Chicago, IL 60637 soloffeuchicago. edu
Rina Foygel Barber Department of Statistics University of Chicago Chicago, 60637 rina@uchicago edu
Rebecca Willett
Departments of Statistics and Computer Science NSF-Simons National Institute for Theory and Mathematics in Biology
University of Chicago
Chicago, II. 60637
willett@uchicant cago.icaag..ed edu
Abstract
We propose new framework for algorithmic stability in the context of multiclass classification. In practice, classification algorithms often operate by first assigning continuous score (for instance, an estimated probability) each possible label, then taking the maximizer-ia drawback of this type of approach is that it is inherently unstable, meaning that it is very sensitive to slight perturbations of the training data, since taking the maximizer is discontinuous. Motivated by this challenge, we propose a pipeline for constructing stable classifiers from data, using bagging (i.e., resampling and averaging) to produce stable continuous scores, and then using a stable relaxation of argmax, which we call the "inflated argmax", to convert these scores to set of candidate labels. The resulting stability guarantee places no distributional assump- tions on the data, does not depend on the number of classes or dimensionality of the covariates, and holds for any base classifier. Using a common benchmark data set, we demonstrate that the inflated argmax provides necessary protection against unstable classifiers, without loss of accuracy.
selecting the class that has the highest score, A
Introduction
An algorithm that learns from data considered to stable if small perturbations of the training data do not lead large changes in its output. Algorithmic stability is an important consideration in many statistical applications. Within the faimess literature, for instance, stability is one aspect of reliable decision-making systems (FSVC19) HV19.. In interpretable machine learning, it similarly serves as a form of reproducibility [MSKA]] 19 YK20 YB24). [CMXIT] relates stability to robustness, where machine learning algorithm robust if two samples with similar feature vectors have similar test eттor. In the context of generalization bounds, (BE02) and subsequent authors study stability of an algorithm's 's real-valde valued output-for instance, values of regression function. In the setting of a multiclass classification problem, where the data consists of features X E X' and labels Y E [Z] = {1..... L}. the results of this literature can thus be applied to analyzing a classifier's predicted probabilities (x) E [0, 1e. our learned estimates of the conditional probabilities Pr(Y X}. for each E [L]. However, as we will see, stability of these predicted probabilities by no means implies stability of the predicted label itself, ý argmax [r.] pe(x)) an arbitrarily
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

small perturbation in (x) might completely change the predicted label j. The distinction matters: for system trustworthiness, we care about the model's 's final output, on which users base their decisions.
In this paper, we propose a new framework for algorithmic stability in the context of multiclass classification, to define-and achieve-a meaningful notion of stability when the output of the algorithm consists of predicted labels, rather than predicted probabilities. Our work connects to other approaches to allowing for ambiguous classification, including set-valued classification [Gry93 DDB09 [SLW19; CDHL21] and conformal inference (PPVG02] VGS05 Leil4. AB23 discuss related work further, below).
(we will
1.1 Problem setting
sefm] consisting of n observations, and In supervised classification, we take a data set D = ((X,, Yi)) (i))
train a classifier that maps from the feature space to the set [L] of possible labels 1T Typically, this map is constructed in two stages. First we run some form of regression to learn a map X - A from features to predicted probabilities, with pe(x)) denoting our learned estimate of the conditional label probability. Pr = E X x} (here A {w E Rt w, 0. 0,E, w, 1} denotes the probability simplex in L dimensions). We will write p = A(D), where A denotes the learning algorithm mapping data set D (of any size) the map ý. Then the second step is to convert the predicted probabilities (x())) to a predicted label, which is typically done by taking the argmax, i.e., ý argmax, (x( (with some mechanism for breaking ties). This two-stage procedure can be represented in the following diagram:
Test features E X
Learning algorithm A
Selection (via argmax)
Predicted probabilities p(x) E A
Training data D = ((x,, Y:))
Predicted label
g E [L]
When predictions are ambiguous, meaning two more classes nearly achieve the maximum predicted probability, the selected label becomes unstable and can change based on seemingly inconsequential perturbations to the training data. In other words, the above workflow is fundamentally incompatible with the goal of algorithmic stability. Consequently, in this paper we instead work with set-valued classifiers, which return a set of candidate labels- practice, this typically leads to a singleton set for examples where we have high confidence in the label, but allows for larger set in the case of ambiguous examples. While the idea of returning a set of candidate labels is not itself new, we will see that the novelty of our work lies in finding construction that offers provable stability guarantees.
In this framework, a feature vector x E X' is now mapped to set of candidate labels S C [4] (rather than single label f)), via selection rule s, illustrated here:
Test features x E X
Learning algorithm
Selection rule s
Predicted probabilities p(x) E Ar.-1
Training data D ((X,, Y.)) sc[m]
Candidate labels S C [4]
Formally, given a test point I E X, this two-stage procedure returns S = s(((x)) S [4]. where I A(D) is the output of the regression algorithm A trained on data D. Here s: - + ((L)) denotes a selection rule, mapping a vector of estimated probabilities to the set of candidate labels, and (([L)) denotes the set of subsets of [L]. Of course, the earlier setting where the procedure returns a single label ÿ = argmax, (e())) rather than a subset can be viewed as special case by simply taking s to be the argmaxx operator.
We remark that all the results of this paper apply also to the case of countably infinitely many labels, L = co. in which case should take N to be the label space instead of [L].

---

If we instead allow for S to contain multiple candidate labels, commonly used version of this framework is given by top-S procedure (or top-k, for any fixed k). That is, after running learning algorithm A to estimate probabilities p(r), the selection rule then returns the top 5 labels the labels ,,,..., fs [r.] corresponding to the highest values of pe(ar). This approach more stable than a standard argmax. However, the choice of 5 in this setting is somewhat arbitrary, and the set $ always contains 5 candidate labels, regardless of the difficulty of the test sample- -while intuitively, might expect that it should be possible to return smaller $ for test points x: that easier to classify (and larger S if more ambiguous). In contrast, in our work we seek more principled approach, where we provide provable stability guarantees while also aiming for the set S be as small as possible.
1.2 Overview of main results
In this work, we introduce selection stability, a new definition of algorithmic stability in the context of classification, which focuses on the stability of the predicted label. We reduce the problem of stabilizing a classifier to separately stabilizing the learning and selection stages, described above. For the selection rule 8 of the two-stage procedure, we propose the inflated argmax operation:
Definition (Inflated argmax). For any w E TRL,, define the inflated argmax as
argmax (w) {i [4] dist(w,RF) RJ) < <)),
(I)
where dws RB) inlveRs ||w v|1. and where
Rj = w
W B R wy 2 max + + 843
j e argmax" (p(z)) indicates that a small perturbation of the predicted probabilities, p(z). would lead to the jth label's predicted probability being largest by some margin. In particular, by construction, the inflated argmax will always include any maximal index that is, p(z), is the (possibly non- unique)
Our procedure will then return the set S argmax (f(z)) of candidate
largest estimated probability, then we must have j E $ = argmax (f(x)) (this fact, and other properties of the inflated argmax, will be established formally in Proposition TO beloow..
In this work, we derive the stabilizing properties of the inflated argmax, and give an algorithm to compute it efficiently. We prove that combining this operation with bagging the learning step will provably stabilize any classifier. In particular, our guarantee holds with no assumptions on the data, and no constraints on the dimensionality of the covariates nor on the number of classes.
2 Framework: stable classification
In this section, we propose a definition of algorithmic stability in the setting of multiclass classification. To begin, we formally define a classification algorithm a mar
C: Un20 x [L]) x X - (((L)),
which maps a training data set D of any size n, together with a test feature vector x E X, candidate set of labels $ = CDD, .z). To relate this notation to our earlier terminology, the two-stage selection procedure described in Section [.1 corresponds to the classification algorithm
C(D, x) sf(xx)) where ÿ = A(D).
Abusing notation, we will write this as C o A, indicating that C is obtained by applying the selection rule s to the output of the learning algorithm A.
We now present our definition of algorithmic stability for classification algorithm C. As is common in the algorithmic stability literature, we focus on the stability of the algorithm's 's output with respect
We will assume without comment that C measurable. Furthermore, in practice classification algorithms often incorporate randomization (either in the learning stage, such as via stochastic gradient descent, and/or in the selection stage, such as by using random tie- brebbra rule for argmax). All of our definitions and results in this paper can be naturally extended to randomized algorithms Appendix B
3

---

to randomly dropping a data point: does the output of C on a test point change substantially if we drop single data point from the training data D? the algorithm's 's output were a real-valued prediction i E R, we could assess this by measuring the real-valued change in y when a single data point is dropped. For classification, however, we will need to take different approach:
Definition 2 (Selection stability). We say classification algorithm C has selection stability 8 at sample size n if. for all datasets E (X' x [L|)" and all test features a E X.
1 Σ
1 1(snsv [Isnsv= =}{6 so
i=1
where 3 = x)) and where S = C(D'è for each E [n]]
Here the notation D' denotes the data set D with data point removed that is, for data set D (I), jE(N] the leave-one-out data is given by D ((X,, X)) jeln]V
2.1 Interpreting the definition
Intuitively, selection stability controls the probability that our algorithm makes wholly inconsistent claims when dropping a single data point at random from the training set. If we interpret $ as making the claim that the true label Y is equal to one the labels in the candidate set $, and similarly for SV then as soon as there is even one single value that lies in both Š and ŠY this means that the two the sets are large and are mostly nonoverlapping.
claims are contradictory-
At first glance, this condition appears to be too mild, in the sense that we require the two prediction sets only to have some way of being compatible, and allows for substantial difference between the sets $ and 5A However, since standard classification algorithms always output a single label, they often cannot be said to be stable even in this basic sense. Thus, we can view this definition as providing a minimal notion of stability that we should require any interpretable method to satisfy.
2.2 Connection to classical algorithmic stability
Most prior work on algorithmic stability concerns algorithms with continuous outputs- for example, in notation above, the algorithm A that returns estimated probabilities f(x). With such algorithms, there are more standard tools at our disposal for quantifying and ensuring stability. In this section, we connect classical algorithmic stability to our notion of selection stability (Definition) 2 recall the following definition.
We first
Definition 3 (Tail stability). (SBW24b) learning algorithm A has tail stability (5, at sample size n if. for all datasets DD of size and all test features x E X,
Σ 1 (1b(aa
-5 DV())) 2 58.
where á A(D) and g: A(D'), and where denotes the usual Euclidean norm on R
This intuitive notion of stability is achieved by many well-known algorithms A, such as nearest- neighbor type methods or methods based on bagging or ensembling established by (SBW24a) SBW24b see Section below for details).
2.3 From stability to selection stability
To construct classification algorithm using the two-stage procedure outlined in Section 1.1 to apply a selection rule s to the output of our learning algorithm AA We might expect that choosing a stable A will lead to selection stability in the resulting classification algorithm-but in fact, this the case: even the learning algorithm A is itself extremely stable in the sense of Definition 3 the classification rule obtained by applying argmax the output of A can still be extremely unstable.
need
The underlying issue is that argmax is extremely discontinuous the perturbation [|p(z)) -
in the predicted probabilities can be arbitrarily small but still lead to different predicted labels, i.e.,
argmax, (x) * argmax, 2)"( (x).

---

Since combining argmax with a stable learning algorithm A will not suffice, we instead seek different selection rule s-one that will ensure selection stability (when paired with stable learning algorithm A). To formalize this aim, we introduce another definition:
Definition 4 (s-compatibility) A selection rule 8 e, w.W. E L-1
- (PL() is e-compatible if. for any
= s(v) ( sss((w)))))) * Ø. || - w|| <E =
This notion of e-compatibility allows us to construct classification algorithms with selection stability. Combining the above definitions leads immediately to the following result:
Proposition 5. Let A be a learning algorithm with tail stability (s, 6) at sample size n, and let s be selection rule satisfying e-compatibility. Then the classification algoritho C A has selection stability at sample size n.
Therefore, by pairing a stable learning algorithm with compatible selection rule s, we will automatically ensure selection stability of the resulting classification algorithm 5 A.
Of course, e-compatibility of the selection rule might be achieved in trivial way-for for instance, returns the entire set [L] for any input. As is common in statistical settings (e.g., a tradeoff between Type I error and power, in hypothesis testing problems), our goal is to ensure selection stability while returning an output $ that is informative possible. In particular, later will consider the specific aim of constructing $ to be singleton set often possible.
3 Methodology: assumption-free stable classification
In this section, we formally define our pipeline for building stable classification procedure using any base learning algorithm A. At high level, we leverage Proposition (5aaatiioonnaaa [5n separately address the learning and selection stages described in Section 2
we construct bagged (i.e., ensembled) version of the base learning algo- rithm A. The recent work of (SBW24b) ensures that the resulting bagged algorithm has tail stability (e, 6). with Vnd"
Section 3.1
2. In Section 3.2 introduce new selection rule, the inflated argmax, and establish its e-compatibility. Combined with the bagged algorithm, then, the resulting classification algorithm will be guaranteed to have selection stability 8 (by Proposition 5).
Before describing these two steps in detail, we first present our main theorem that characterizes the selection stability guarantee of the resulting procedure. Given sample size for the training data set D, the notation Am. will denote bagged version of the base algorithm A, obtained by averaging over subsamples of 'D comprised of m data points sampled either with replacement ("bootstrapping". commonly run with m = n) or without replacement ("subbagging" commonly run with n nee below for details.
Theorem 6. Fix any sample size n, any bag size m, and any inflation parameter O. For any base learning algorithm A, the classification algorithm C = argmax oAm, obtained by combining the bugged version of together with the inflated argmax, satisfies selection stability ê where
6= 1 1/L
Pn.m
(2)
71 1-1
Pn.m
where Pr.m = 11--111
m m for bootstrapping. and Pa.m m for subbagging.
The guarantee in Theorem holds Gholds for any base learning algorithm A, and applies regardless of the complexity of the feature space X' and allows the test feature x E X' to be chosen adversarially. The dependence on the number of classes L is mild-in fact, the tail stability parameter in (2) differs only by factor of two for L = 2 versus L = do. Of course, the guarantee does depend on the choice of the bag size m. In general, smaller value of leads to stronger stability guarantee (since Pa.m increases with m), but this comes at the expense of accuracy since we are training the base algorithm A on subsampled data sets D" of size m (rather than n). For the common choices of for bootstrap or m = n2/2 for subbagging, we have Pr
O(1) for each.
I-pm.m
5

---

3.1 Bagging classifier weights
In this section, we formally define the construction of a bagged algorithm to recap the tail stability result that our framework leverages. We consider the two most common variants of this ensembling method: bagging (based on bootstrapping training points) and subbagging (based on subsampling). For any data set 'D E (X x [L]", we can define a subsampled data set of size m as follows: for sequence r = (f,,..., .m))
[m] mh (which is called bag), we define the corresponding subsampled E (X' x [L]) Note that if the bag r contains repeated indices (i.e.,
data set 2 ((X,, Yi)) jer
2 ie for some lo * E), then the same data point from the original data set D will appear multiple times in D
Definition 7 (Bootstrapping or subbagging a base learning algorithm A). Given a data set D E (X x [4]) and some E X. return the output Am (D) = E,(A(D") (x)), where the expected
value is taken with respect bag that is sampled as follows:
Bootstrapping (sometimes simply referred to as bagging) Bre Bre96b] constructs each bag by sampling m indices r (fi.....hun uniformly with replacement from [n]]
Subbagging | constructs each bag by sampling m S indices r = (i1..... km)
uniformly without replacement from [ni].
The following result (SBW24b) ensures tail stability for any bootstrapped or subbagged algorithm: Theorem 8 (SBW24b)) ). For any base learning algorithm A returning outputs in Ar.-1, the bagged algorithm Am has tail stability (e, () for any e, 5 > satisfying
Computational cost of bagging, In this section, we have worked with the ideal, derandomized ver- sion of bagging for simplicity- that is, we assume that the expected value E, [A("") is calculated exactly with respect to the distribution of r. In practice, of course, this is computationally infeasible (since for bootstrapping, say, there are n² possible bags r), and so we typically resort Monte
Carlo sampling to approximate this expected value, defining Am (z) = B Σ A(D*))(z)) for B i..dd bags f....... ................................ l' our main result, Theorem 6 to the finite version of the method.
. sampled via bootstrapping or subbagging. See Appendix C for extensions of
3.2 The inflated argmax
We now return to the inflated argmax operator, as defined in Definition] This operator, in place of the standard argmax, allows for stability in classification.
While argmax" is defined as an operator on IR' in the context of classification algorithms, we only apply vectors w lying in the simplex A--1 1 (in particular, in the context of a two-stage classification procedure as in Section [.]] we will apply the inflated argmax to the vector w = p(x)
of estimated probabilities). Figure 1 we visualize the inflated argmax applied to the simplex in a
setting with three possible labels, L. 3. 3. Each different shaded area corresponds to the region of the simplex A 1 where argmax (w) returns a particular subset.
3.2.1 Inflated argmax leads to selection stability
Unlike the standard argmax, the inflated argmax allows to achieve stability in the context of classification. This is due to the following theorem, which shows that the inflated argmax is e- compatible, introduced in Definition 4 (The proofs of this result and all properties of the inflated argmax are deferred to Appendix A
Theorem 9. For any ε > 0 and any v, w IR-, if|lu-w|l In particular, viewing argmax as a map on the simplex A argmax is e-compatible.
w|l <
then argmax (v) nargmax (w) + Ø.
To gain a more concrete understanding of this theorem, we can look again at Figure tt examine the case L = 3. Theorem Jensures that any two regions corresponding to disjoint subsets e.g., the top corner region corresonding to (2), and the bottom center region corresponding to (1,3) (rre) are distance at least apart. In particular, the region in the center, corresponding to vectors w that map
to the full set (1, 2, is a curved triangle of constant width e, also known as Reuleaux triangle [Reu76 Wei05).

---

(0,1.0)
1.
(2)
(2)
(122)
(2.3)
(.3)
(
(3)
(1,6,0)
(0.0, 1)
(1,6,0)
00,0,1]
Figure 1: The left plot illustrates the inflated argmax IT) over the simplex År-1 when =. The numbers in brackets correspond to the output of the inflated argmax, arginax" (w). for various points w in the simplex. The right plot shows the same for the standard argmax, which corresponds to the limit of argina* (w=
O.
Proof of Theorem With the above results in place, we can now see that the inflated argmax allows achieve selection stability, when combined with a bagged algorithm. In particular, combining Theorem Theorem 9 and Proposition iimediately implies our main result, Theorem 6
3.2.2 Additional properties of the inflated argmax
The following result establishes some natural properties obeyed by the inflated argmax, and also compares to the standard argmax.
Proposition 10 (Basic properties of the inflated argmax). Fix any e 0. The inflated argmax operator satisfies the following properties:
1. (Including the argmax.) For any E Rt, argmax(w) S argmax (w) Moreover, Neso argmax (w) argmax(w)..
2. (Monotonicity in e.) For any E R_ and any < 6', argmax (w) S argmax (w).
3. (Monotonicity in w.) For any w E RR,, if wi S wh. then j E argmax (w) = k E argmax- (w))
4. (Permutation invariance.) For any IR4, if (Wol1).... Wo(L)) for some permula- tion on [L]. then j E argmax" (v) o(j) E argmax"
Next, while have established that inflated argmax offers favorable stability properties, have not yet asked whether can be efficiently computed-in particular, it is not immediately clear how verify the condition dist(w, I25) in ( in order determine whether j E argmax (w)). The following result offers an efficient algorithm for computing the inflated argmax set.
Proposition 11 (Computing the inflated argmax). Fix any R and denote the order statistics of w, and define
0. Let wil) 2[r]
k((w)= max { k kE [4]:
E
② E=1
-
(w )(a))²
Σ E=1
(im) wmii) < <
Then
argmax" (w) = E [L] w V2
8
Áι(w) kk(w) + V k(w)
62 (Ar(w))2 - Aa(w))
where ([(w)= tii t..gtt..rrraaa and Ag (w) wit
t (
k(w)
k(w))
In this result, argmax(w) (w) should be interpreted as the set of all maximizing entries of w. iee. in the case of ties, argmax(w) (w) may singleton set.
7

---

Stability comparison with B 1, 1,000 bags
10"
argrana
orgnnn a.
88
arguanaAmm
argmann' a.
118,
10-2
10
10
0.0
1.0
8
Figure 2: Results on the Fashion MNIST data set. The figure shows the instability 6, (defined in (4) over all test points j = l..... N. The curves display the fraction of ó, 's that exceed for each value 5 E [0, 1]. The vertical axis is on a log scale. See Section for details.
Finally, thus far have established that argmax" enables us to achieve stable classification with computationally efficient selection rule-but we do not yet know whether argmax" is optimal, or whether some other choice of s might lead to smaller output sets (while still offering assumption- free stability). For instance, we might consider
margin rule,
$ mangin (w) = {j W >> max w, - e/V2].
(3)
for which e-compatibility also holds-might might this simpler rule be better than the inflated argmax? Our next result establishes that-under some natural constraints argmaxx is in fact the optimal choice of selection rule, in the sense of returning singleton set (i.e., S 1) as often as possible.
Proposition 12 (Optimality of the inflated argmax). Let AL-1 (P(()) be any selection rule. Suppose is e-compatible (Definition 4) permutation invariant (in the sense of Proposition TO and contains the argmax. Then for any w Ar.1 and any [L].
s(w) ( = argmax (w) = (j).
In other words, for any selection rule s satisfying the assumptions of the proposition (which includes the fixed-margin rule, mmagin). ), if sww) is a singleton set then so is argmax (w). (See also Appendix D for a closer comparison between the inflated argmax and the fixed-margin selection rule given in
Experiments
In this section, we evaluate our proposed pipeline, combining subbagging with the inflated argmax, with deep learning models and on common benchmark data set
Data and models. We use Fashion-MNiS [RRV7]], which consists of n 60, 000 training pairs (X,, Y,), N 10, 000 test pairs (X,, Y2), and 10 classes. For each data point (X, YY. X is a 28 x 28 grayscale image that pictures a clothing item, and Y E [L] indicates the type of item, e.g., dress, coat, etc. The base model we use variant of LeNet-5, implemented in Py PyTorch [9GML19) tutorials as GarmentClassifirr).. The base algorithm A trains this classifier using 5 epochs of stochastic gradient descent.
Methods and evaluation.
We compare four methods:
The argmax the base learning algorithm A.
*Code to fully reproduce the experiment is available at httpp:://githbb com/ jake-ja soloff/ stable- argmax- experiments Training all of the models for this experiment took total of four hours 10 CPUs running in parallel single computing cluster.

---

Selection rule Algo.
Peorrect-single
Psot-size
maax- maxttiitaaility
argmax
A
0.879 (0.003)
1.000 (0.000)
1.000
argmax
A
0.873 (0.003)
1.015 (0.001)
1.000
argmax
Am
0.893 (0.003)
1.000 (0.000)
0.966
argmax
Am 0.886 (0.003)
1.018 (0.001)
0.000
Table I: Results on the Fashion MNIST data set. We display the frequency of returning the correct
label as a singleton, Peonnet-single and the average size, Seet-size both of which are defined in (6). Standard errors for these averages shown in parentheses. The final column shows the worst-case instability over the test set, Pmax-instability- defined in (5). For each metric, the symbol / indicates that higher values desirable, while indicates that lower values are desirable.
2. The s-inflated argmax the base learning algorithm A with tolerance : = .05.
3. The argmax of the subbagged algorithm Am. with B = 1, 000 bags of size = n1/2.
4. The e-inflated argmax of the subbagged algorithm Ams with 1, 000 bags of size = n1/2 and tolerance e = .05.
We evaluate each method based on several metrics. First, to assess selection stability, for each test point l,...,, N we compute its instability
500
6, :- Σ
((( =0
500
where ......, 4500 are sampled uniformly without replacement from [rx] (i.e., we are sampling 500 leave-one-out models pi to compare to the model ý trained on the full training set). Since our theory concerns worst-case instability over all possible test points, evaluate the maximum instability
3 mmax-instabllit
:- max 65- ]E[N]
(5)
Second, to evaluate how accurate each method is, we compute how often the method returns the correct label as a singleton Beomrect single and set size Size (the number of labels in the candidate set):
ceereect-singee
1 I(((((()))) N
(8))).
Bsec-size
1 N
Σ ((((X))))
(6)
Ideally would want method return the correct singleton frequently possible (a large value of Scurrectsingle E [0, 1] that is close to 1) and small set size (a value of Sset 2 that close to 1).
present results for the instability of each method, plotting the survival function of the instability for all test points (8y))E(N]- The standard argmax applied to the base algorithm, argmax c,4, has the longest tail, meaning 6, is large for many test points The inflated argmax applied to the base algorithm, argmax oA, offers only a very small improvement on the stability. By contrast, applying the standard argmax to the subbagged algorithm, argmax c,Am, offers a much more substantial improvement, since the red dashed curve is much smaller than both of the solid curves. Still, some of the largest 6, for this method are near 1, meaning for these test points the returned set is sensitive dropping single training instance. Combining the inflated argmax with subbagging, argmax" oAm, offers a dramatic improvement: in this case ò, = for every j = N.
Results. In Figure
In Table we present the average measures, Seurrect-ingle and Seet-size and the worst-case measure 3max -max-instability- For both the base algorithm and the subbagged algorithm, applying the inflated argmax incurs a small cost both terms the frequency of returning the correct label as a singleton and the average size. The inflated argmax increases set size only very slightly, but when combined with subbagging. we improve upon the Reonect single of original method and achieve an extremely high level of stability (8 (Pmax-instabiliity 0), while returning singleton set in the vast majority of cases.

---

We extend our experiment in Appendix In particular, we compare the inflated argmax to some existing methods for set-valued classification, including simple thresholding and top- rules as well as more involved methods, all of which are Bayes rules for various utility functions [MWDH21]) We also evaluate each method using some additional metries from set-valued classification, including uility-discounted predictive accuracy (ZCM12).
5
Discussion
Related work. There is an enormous literature set-valued classification, so we only reference some of the most relevant works. Much prior work has considered the possibility of a more relaxed argmax to allow for uncertainty [Bri90, BV16 MA16 [MN20 ZLYW23]. The more recent papers in this line of work have focused on producing sparse set of weights, but none of these works offer formal stability guarantee for the support of the weights. Our work is the first to propose version of the argmax that can provably control a notion of stability for the classification setting.
Our definition of selection stability relies a notion of consistency between sets-twe sets of candidate labels are consistent if they have at least one common element. This is similar in flavor to conformal classification [Lei 14, SLWI9], where a set of candidate values is valid if it contains the correct label; this method does not rely on any distributional assumptions, and consequently has been applied to complex and high-dimensional applications such as generative language models (QFSY23). These frameworks share the motivation of avoiding 'overconfidence in the assignment of a definite label" (HPW18).
Overview, limitations and open questions. We prove guarantee on the selection stability based on our methodology combining bagging with the inflated argmax. Theorem O does not place any assumptions on the learning algorithm nor on the data, including any distributional assumptions. In fact, the training data and test point may be chosen adversarially based on the algorithm, and the output will still be stable. Moreover, we do not assume that the sample size large: the guarantee holds for any fixed training set size n and improves as n increases. Furthermore, the inflated argmax selection rule ensures that the returned sets of candidate labels are as small as possible (i.e., that there is as little ambiguity as possible about the predicted label for any given test point æ).
While our theorem does not require assumptions, our method does require bagging the base learning algorithm. The main limitation of our work is that bagging is computationally intensive. However, training different bags is easily parallelizable, which is what allowed us easily train a convolutional neural network on B = 1. 000 total subsets of the training data. Moreover, while the original definition of bagging uses the conventional bootstrap, where each bag contains as many samples as the original data set, i.e. m = in our framework we allow for arbitrary bag size m, which could be much smaller than the sample size n. Massively subsampling the data (m < n) can actually help scale learning algorithms to large data sets (KTS/14). Moreover, bagging with m = n can be expensive, but there are still many areas of machine learning where it is used, notably in Random Forests. Finally, our experiments also show that modest number of bags (B 1, 000) is all that we really need to start seeing major gains in selection stability.
We leave open several avenues for future work. Practitioners may be interested in other forms of discrete stability, which are more strict than requiring one common element between $ and SV For
18n&91 instance one popular way to measure set similarity is the Jaccard index, given by [SusVi]* open problem is extend the stability framework and methods studied here to more structured discrete outputs, such as in clustering and variable selection, where nontrivial metrics on the output are more common.
Another
Acknowledgements
We gratefully acknowledge the support of the National Science Foundation via grant DMS-2023109 DMS-20233 R.F.B. and J.A.S. gratefully acknowledge the support of the Office of Naval Research via grant N00014-20-1-2337
R.M.W. W. gratefully acknowledges the support of the NSF-Simons National Institute for Theory and Mathematics in Biology (NSF DMS-2235451 Simons Foundation PP-TMPPS-00005300) and AFOSR 149550018-1-0166 The authors thank Melissa Adrian for help with running the experiments.
10

---

References
[AB23]
Anastasios N Angelopoulos, Stephen Bates, al. "Conformal prediction: gentle introduction". In: Foundations and Trends@ in Machine Learning 16.4 (2023), pp. 494- 591.
[AEEPO2]
Savina Andonova et al. "A simple algorithm for learning stable machines". In: Euro- pean Conference Artificial Intelligence (ECAI). 2002, pp- 513-517.
[BE02]
Olivier Bousquet and André Elisseeff. "Stability and generalization., In: The Journal of Machine Learning Research 2 (2002), pp. 499-526.
[BMN20]
Mathieu Blondel, André F. T. Martins, and Vlad Niculae. "leearning with Fenchel- Young losses". In: J. Mach. Learn. Res. 21 (2020), Paper No. 35, 69. ISSN: 1532-
4435,1533-7928.
[Bre96a]
Leo Breiman. "Bagging predictors". In: Machine learning 24.2 (1996), pp. 123-140 Leo Breiman. "Heuristics of instability and stabilization in model selection". In: The Annals of Statistics 24.6 (1996), pp. 2350-2383.
[Bre66]]
[Bri90]
John S. Bridle. "Probabilistic interpretation of feedforward classification network outputs, with relationships to statistical pattern recognition". In: Neurocomputing (Les Arcs, 1989). Vol. 68. NATO Adv. Sci. Inst. Ser. F: Comput. Systems Sci. Springer, Berlin, 1990, pp. 227-236. ISBN: 3-540-53278-1.
[BV16]
Alexandre de Brébisson and Pascal Vincent. "An exploration of softmax alternatives belonging to the spherical loss family". In: International Conference on Learning Representations (ICLR). 2016.
[CDHL21]
Evgeni Chzhen et al. "Set-valued classiiication-overiiie via unified framework". In: arXiv preprint wr.iv:2102.12331 (2021).
[CMX11]
Constantine Caramanis, Shie Mannor, and Huan Xu. "Robust optimization in machine learning". In: (2011).
[DDB09]
Juan José Del Coz, Jorge Díez, and Antonio Bahamonde. "Learning Nondeterministic Classifiers." In: J. Mach. Learn. Res. 10.10 (2009).
[FSVC19]
Sorelle A Friedler et al. "A comparative study of fairness-enine fairness-enhancing interventions in machine learning". In: Proceedings of the conference on fairness, accountability, and transparency. 2019, pp. 329-338.
[Gry93]
Eugen Grycko. "Classification with set-valued decision functions" In: Information and Classification: Concepts. Methods and Applications Proceedings of the 16th Annual Conference of the "Gesellschaft für Klassifikation eV" University of Dortmund, April 1-3, 1992. Springer. 1993, pp. 218-224.
[HPW18]
Yotam Hechtlinger, Barnabás Póczos, and Larry Wasserman. "Cautious deep learning". In: arXiv preprint I 0904000 (2018).
[HV19]
Lingxiao Huang and Nisheeth Vishnoi. "Stable and fair classification". In: Interna- tional Conference on Machine Learning. PMLR. 2019, pp. 2879-2890.
[KTSJ14]
Ariel Kleiner et al. scalable bootstrap for massive data". In: Journal of the Royal Statisfical Society: Series B: Statistical Methodology (2014), pp. 795-816.
[Lei14]
Jing Lei. "Classification with confidence". In: Biometrika 101.4 (2014), pp. 755- 769. ISSN: 300e-3344,11444444 //doi.org// 10/g/10.20 wwt.///iieee////eeeeeeeeee assu03
DOE: 10. 1093 http://mmmettt/eee asu038 URL: https
[MA16]
Andre Martins and Ramon Astudillo. "From softmax sparsemax: sparse model of attention and multi-label classification" In: International conference on machine learning. PMLR. 2016, pp. 1614-1623.
[MSKA19]
W James Murdoch et al. "Definitions, methods, and applications in interpretable machine learning". In: Proceedings of the National Academy of Sciences 116.44 (2019), pp. 2207 1-22080.
[MWDH21] Thomas Mortier et al. "Efficient set-valued prediction in multi-class classification". In: Data Mining and Knowledge Discovery 35.4 (2021), pp. 1435-1469.
INDMH18]
VL Nguyen al. "Reliable multi-class classification based on pairwise epistemic and aleatoric uncertainty". In: 27th international joint conference on artificial intelligence (IJCAI). 2018 pp. 5089-5095.

---

[PGML19] Adam Paszke et al. "PyTorch: An imperative style, hegh-performance deep learning library". In: Advances in neural information processing systems 32 (2019).
[PPVG02]
Harris Papadopoulos et al. "Inductive confidence machines for regression". In: Ma- chine learning: ECML 2002: 13th European conference machine learning Helsinki, Finland, August 19-23, 2002 proceedings 13. Springer. 2002, PP. 345-356.
[QFSY23]
Victor Quach et al. "Conformal language modeling". In: arXiv preprint arXiv:2306. 10193 (2023).
[Reu76]
Reuleaux. Kinematics of machinery: outlines of a theury of machines. Reprinted as "The Kinematics of Machinery", New York: Dover, 1876.
[SBW24a]
Jake A. Soloff, Rina Foygel Barber, and Rebecca Willett. "Bagging Provides Assumption-free Stability". In: Journal of Machine Learning Research 25.131 (2024),
pp. 1-35. URL: http::htt//// htpp://mmmrrr
htt//aapers/v25/2222 .536.htmll
[SBW24b]
Jake A. Soloff, Rina Foygel Barber, and Rebecca Willett. "Stability via resampling: statistical problems beyond the real line". In: arXiv preprint arXiv:2405.095/ (2024).
[SLW19]
Mauricio Sadinle, Jing Lei, and Larry Wasserman. "Least ambiguous set-valued clas-
sifters with bounded error levels". In: J. Amen. Statist. Assoc. 1 14.525 (2019), pp. 223-
234. ISSN: 1552--14,,,137774451 DOL: 10 000.//062225999.... 2017 1395341 URL:
https: /ttps://doi.. org/10.g//..... 1080/01621499. 2017 1395341
[VGS05]
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in random world. Springer, New York, 2005, pp. xvi+324.
[Wei05]
Eric W Weisstein. "Reuleaux Triangle". In: MathWorld A Wolfram Web Resource (2005). https::/mathworr:
wolfram cww/ wwt.ccoo//eeeeeee htt///Ruleuxxriiinng/// .tmll
[XRV17]
Han Xiao, Kashif Rasul, and Roland Vollgraf. Mashion-MNIST: a Novel Image Dalaset for Benchmarking Machine Learming Algorithms. 2017. arXiv: 1708 07747 [G]
[YB24]
Bin Yu and Rebecca Barter. Veridical Data Science: The Practice of Responsible Data Analysis and Decision Making. MIT Press, 2024.
[YK20]
Bin Yu and Karl Kumbier. "Veridical data science". In: Proceedings of the National
Academy of Sciences 117.8 (2020), pp. 3920-3929.
[ZCM12]
Marco Zaffalon, Giorgio Corani, and Denis Mauá. "Evaluating credal classifiers by utisity-discounned predictive accuracy". In: Internat. Approx. Reason. 53.8 (2012). pp. 1282- 1301, ISSN: 0888 61888-613X,,600 613X,11133-3221.. 1873-47311 DOr: 10. 1016/j.ijar 2012. 06. 022 URL: wttpt:::///ettt //dii. org 1016/j jijar. 2012. 06.022
[ZLYW23]
Shuai Zhao et al. "From softmax to nucleusmax: novel sparse language model for chinese radiology report summarization".. In: ACM Transactions Asian and Row-Resorrce Language Information Processing 22.6 (2023), pp. 1-21.
12

---

A Proofs of properties of the inflated argmax
In this section, we prove all the results of Section 3.2 establishing the various properties of the inflated argmax. In fact, all the proofs will rely on the following theorem, which gives an alternative characterization of the set argmax (w).
Theorem 13. Fix E > O. Define the map Ce R + as
(my o)+ )
(ww is the unique solution to
Σ SELL]
+ Σ (wy c) =
jELL]
and define the map by R- + R as
(c(w)) cw( + 8/V2-
Σ
(my (c(w))+
SE(L]
Then for any w E R it holds that
arginax (w) [L] wj > (e(w)}.
Moreover, te (w) S (eww) for all w and all E, and (ww) and ce ca(w) are both nondecreasing functions of E, and both nondecreasing functions of w (i.e., if w S w/ holds coordinatewise, then Ce (z(w) I Cg (w')) and (w) S (w))).
With this key result in place, now ready to turn to the proofs of the results stated in Section 3.2 Throughout all the proofs below, the functions ee (w) and to (w) are defined as in the statement of Theorem B
A.1 Proof of Theorem
Let w, w/ E R² be any vectors with argmax" (w) n argmax= = Ø. Define
B= Li E [4] : wy > ce(w),, B' = (j E [4] noj > ce (<ww)),
and note that we must have B argmax (w) since for j & argmax (w) w, I (w) ce (w) by Theorem 13 Similarly, B' S argmax (w'). We also must have B (and similarly B') nonempty by
definition of (w)).
For convenience, define c = ce(w), d (= (e(w), = =e((w). We then have
|| 2'12 2 IwB - w'n'' + 1w'r - wpr 1|
(d w + (c-t') | 1| - (fg ( 11
where the first step holds since n B² = Ø due to argmax (w) n argmax" = Ø. Next we will need a technical lemma.
Lemma 14. Let k k 2 1 be integers and let > O. Then for any x, R x', v E RK and
T, E R. if
(x 1x)2 + || ( 1x +
(8)
and
1 + x 1s r + + +ev2,
(9)
then
| + y + rl 1 + || + 1/ + + M 21 2 2
To apply this lemma, first we let = B 2 and = B3 ž 1, and define
x = wp - clB, = f'1 - w/g. x' w'g. é' 1 2/ = f1g WB
and note that all these vectors have nonnegative entries (specifically, x and x' are nonnegative by definition of B and B', while y and y are nonnegative by Theorem 13 using the fact that
13

---

B s(s())) B' s(w) 2). Then the condition 8 is satisfied by definition of c = ce (w) and
= ce("") Define also
-=c-t,r=
and note that
r (c-r
Ewn - - Σ JELL]
(w/) - cc)+ -
JELL
= x T 1 + x 12 - EV2,
where the second step holds by definition of / = le(w) and 1' = le(w"). Therefore, 9 is also satisfied. Returning 7. Lemma 14 then implies that || w'11 2 E which completes the proof of the theorem.
A.2 Proof of Proposition 10
First we verify that argmax(w) S argmax (w). Let j E argmax(w). i..., wy = max we. Let + 0, // 22, where e; (0,... 0, .., 0) is the jth canonical basis vector. Then E Rj. and ||w - e|| = e/V2 <, so we have dist(w,, R2) < e and therefore j E argmax" We also need to verify that na>o argmax (w) = argmax(w). i.e., for j & argmax(w), there some s with j & argmax (w). Let k E [4] be an index with wk > wj, and let = v2(wx wy). Then for any Rj, we have
||w 2/22 (wg 2 + (wk vx)2 (wn - 8/V2 - -1;)²
3-2+, + (wk vx
(1 (1- (e/v2/ (wy (uy-1hh (w)= + 12 _ (6/v22 (1z -vx))² 2 8²,
1
inf BER
where the last step holds since V/j Uk e/ 22. This means that (w, R7) 2 and so j & argmax (w) at this value of 0.
Next we check monotonicity E. Fix <' Then for any j E [L].
j E argmax (e) Wy (g(w) my > (w) j E argmax (16),
where each step holds by Theorem
Next we verify monotonicity in w. If u I Wk, then by Theorem 13
j E argmax (w) - Wj > te (w) = wk > (w)
k E argmax (w))
Finally we check permutation invariance. Suppose & = (1o )o(L)) is a permutation w. Then by construction, we have (v) = ce (w) and te (v(v) = te (w). In particular,
j E argmax (v) = Uy > (e(v) = worr > (w(w) = a(j) E argmax"(w)
A.3
Proof of Proposition
Define function fw
Σ (wj c)+ ) jE(L]
Σ JE(L]
(w, c)2.
(10)
Then k(w) can equivalently be defined
k(w) = max E [Z] : Su (mpp)) - {2
(Note that this maximum is well defined, since (w( 0 and the set is nonempty.) Since + (c) is strictly decreasing over W[I), that the solution (w(w) the equation
14

---

fw = 2 must satisfy c=(w)= S (k(o))) and (if k(w) < L) also ce(w) > [k(w)+1]] In particular,
this implies
2
e²
Σ JELA
E(wy- (wy - -c((w))+
+
Σ c
jEL
k(w)
k(w)
Σ (wy- -c((w))
+
Σ
ww - ce (w))2
j=1
(k(w) (Ai(w) c<(ww))
2
+ (k(w)A2(w) - 2k(w) (w)cc( ( (w)))
(k(w)((()) 1) ce(ww)2 2c Ai (w)) + As(w)
k(w) +1
This is quadratic function of cz (w:, and is solved by
(e(w) = A (Ai(u)))2 Áz(w) + R(W))
k(w) +
We also have
te(w) = (w))) + +
Σ
(w, cx)(w))
SE(L]
k(w)
= =c((w) + e/V2
(w])) - Ce (w)
j=1
= (k(ww + [)c
+ ((w))
V2
Plugging in our above expression for cg (w), then,
E2
tu( V22
+l(w)) kk(w) + 1/ (AI(w))2 A2(w) +
k(w)
Since argmax (w) = {j : w/ > (w)) by Theorem 13 this completes the proof.
A.4 Proof of Proposition 12
First we will need lemma:
Lemma 15. Fix R-, Then w Rł if and only if argmax (w) = {ii.
For intuition on this result, we can look back at Figure D for instance, the blue region marked by {1} illustrates the set of vectors u E AL-1 such that argmax" (w) {1}, and according to this lemma, this is equal to the region RÇ.
Using this lemma, we now need to show that, for any e-compatible and permutation invariant selection rule if sww) {j} for some
A and j E [L], then E Rj for some j. First, we must have j argmax(w). since is assumed to contain the argmax. Fix any k: # j, and define vector v E A 1--1 by permuting wi and uy:
Wki = j.
Uy Wj, = k,
we, + j, k.
Then by permutation invariance we have s(v) {k}. Since s is e-compatible, we therefore have
8 < || w|l = (wy n2 + (wN v2 + Σ (wo vz)2 = 22 - wx)
Therefore we have wj we 2 8/v2 for all k + j. which proves E Rj and therefore argmax (w) {}}
15

---

A.5 Proof of Theorem 13
Step 1: verifying that Ce (w) is well defined. First we check that the solution ce (=(w) exists and is unique. Fix w and define the function fw as in (TO). Note that f (c) 0 for max; ws, and e+ [c( is strictly decreasing over с S max; wi, with lime---oo (c) = oo; therefore, a unique solution Ce (w) the equation [n) g² must exist.
Step 2: verifying (w) S (u((w) Next we check that the claim 1g (xx) Co (w: must hold. First, by definition of ce (w), we have
2 (wg ce (w=)) )
è² = Σ (w, ce (w))+
+
Σ JELL]
wy
(e(w) 2
Σ JELL
JELL]
where the inequality holds by the properties of the l and Eg norms. Therefore,
Σ jE(L]
w c)+ 2 E/V2.
which verifies that
t=(w) = (w) + +e/V2- (wg- ce()))+ S (ce(w).
JELL]
Step 3: checking monotonicity. Now to verifying the monotonicity properties of tg (w) and ce (w). First we check that these functions are nonincreasing in s. First, since fw. is nonincreasing c, and ce (w) the solution to (c) 22, this immediately implies that (w(w) nonincreasing e. Next we turn to & (w). Define
2
((c)=
1 /2
Σ JE(2]
(wy - c)+
-c)-
Σ JE(L]
w
c)
Σ JE[L]
(wi
c)+,
so that we have f=(w)) = (c(cc by construction. We can verify that < 1' (c(c) is nondecreasing. and therefore, te(w) (w)( (w)) (w),, where the inequality holds since ce(w) S (w).
Next check that 1s (w) and cs (w) are nondecreasing functions of w. Fix any w S w' (where the inequality coordinatewise, i.e., wy S w/ for all E [L]) Since w + J (c) is a nondecreasing function, we have (c) < (c) for all We therefore have for (cx > (w)()(ww) = s² fwr (c, (w")). Since e + for (c) is nonincreasing, therefore, Ce czww)) 2 ce (w). Next we consider f.. Let (c) c e/ve//2-222 - (wy - c)+, which is nondecreasing function of c. Then we have te (w) = (w)) & (w=()) = (w0'
Step 4: returning the inflated argmax. Finally, fixing any w R will prove that argmax"((1) = {j wj > tz(w)}. First choose any [L] with wy > to (w). We need to verify that j E argmax (w). Define e E R with entries
(ax + +e/V2, k= j (w)) wk),
+ j.
16

---

By construction, we have Rj. We calculate
(is R2)² ||0 v/2
[wy m
Σ kjj
(wk
min min((c(w)) wx })
(ce(w)) +2/V2 w3 ) 2
+
Σ
ww - C2 (w))
(c(w)) + +//V2 - te(ww)
+
(wo - ce (2()))
kマj
(wk c=(wi)+
+
Σ kE[L]
(wx co cx))) = ==²
RE(L]
where the last two steps hold by definition of te (w) and ca (w(w), while the strict inequality holds since (w) I (w(w) < ce (w) + e/V2 as established above, while wy > (w)) by assumption. Therefore j E argmax" (w).
Now we check the converse. For this last step, we will need a lemma. The following result characterizes the projection of the set Rř..
Lemma 16. Fix any E Re and any j [L]. Then there is unique R satisfying
wi = =
Σ b
[wk a)+-
(II)
Moreover, defining the vector u R24 as
Up = fa+e/V2, k= j. k # j.
(12)
aa wk.
it holds that argmin ||w
u/|, ie., v is the projection ofw w to the set It.
Next suppose wj < to (w). We need to verify that j & argmnax" (w). Let and v be defined in Lemma 16 above. We can compare the equation I1 to the definition of le (w),
(w( = ce(w) +E/V2-
Σ (wy c+ cc +e/V2- -wn ce()))+ KE
kdj
where the last step holds since wy < (w) by assumption, and (ww) S (w(w) as proved above. Since + c e/v2 Enzr (wx c)+ is an increasing function, and wy to (w), this implies
17

---

a (w)). We then calculate
dist(w, 22 = w| - xil2
= Wi (a (a (a+e/v2))
Σ (wk as wx)) by
+
Wj- - (a+e/v2))
2 +
Σ (w)- a)
k
Σ Ngj
(wck= - a)+
+
Σ
Wwk a) by
2
(wkk -c((w))+
+
Σ
(ook c=(w)) since a S ce(w)
ligf
(wx ce (w))+
+
(wk (w))) since wy (t((w)) s (w)
RE[L
kE[T]
e² by definition of ce (w).
Therefore, dist(w, Ry) 2 E, and so j & argmax"
A.6 Proofs of technical lemmas
A.6.1 Proof of Lemma 14
First, since y is constrained to have nonnegative entries,
| + y + r1,11 2 11x r1.)
where for vector (UI,..., U2) E R', write (v)+ to denote the vector with jth entry given by (Uz)+ = max max[1y, 0} for each j. The analogous bound holds for ||æl + y' + r'1r''
||x + y + 11 + ||x' + y' 11 2 [[(x + r11)+112 + (1(x' + r 1111)4113
We now need to show that
11 (1x)+1 11 +r(w))+1" 2
Next let
r r' ==
x 1. + 1 =V2
A = +r
2
2
2
so that we can write
-= A
for some A e R. We we therefore need to show inf SER f(A) 2 22, where
S(A) (1x (F A)1x)+ (1 (F + A)
First, we observe that we can restrict the range of A. Specifically, for any A 2 maxje(r.) zy + F, we have f(A) (a + (F+ + A)1x)+ which is nondecreasing function; therefore,
inf A2maxjejr +F S(A) = max Jj + ++) (E(T)
meaning that we do not need to consider values of A beyond this upper bound. Applying a similar argument for lower bound, we that from this point we only need to verify that
f(A) > 22 for
max dty jE(k)
A max Ty + JE(T]
Moreover, for any A, we have
( A))² (z, + (F a)) + (xz, + (F - A))² < (z, + ( + (F (F-A)² A)²
18

---

for all j, by nonnegativity of x. Furthermore we must have
(xy + ( -)) = (z, + (F
for at least one j E [L] when A < [ =, + as specified above (i.e., because for j maximizing the entry 2j, the value (æ + (f- ر)رز nonnegative). Therefore,
[1 + (7 A)1+)+11 > 1 + A)1x11 (k- -)
Similarly, we can show that
11(2'= + (F + A) )1| 11 2 |2' + ( 12 (K' - -1)(T + +))F++)) A)..
We then calculate
f(A) ||(x + (F A)1+)+ + +
2 || + (F- 1)1x|1 2 - (k: - () |// + (F+ (F - (W' - 1)(F A)²
||0|| + 2(7 A) 1x + -)2 | + - +A)a' 1 + (F+
= - - (x 1x)²² (a' 11 + 2(F A)x 01 1 + 2( + A)xx T 1x + 27 + 2A?
where the last step holds by
Writing 2 x 1 and 2' x T 1 for convenience, we have
S(A) 2 25 2 - =² - =²2 + 2(F - +)=+ A)= + 27 + 22
2 + eV2
2 z'
EV2
= 2
- =² 12 +2
2 +
+ A
2
2
2
2
2 oV2
+ 2
+ 2A
2
z- z') 2
= 6² +4 (3-e/V2)
(2' (z'ee/V e/v2)
+2
A
2
2 6" + 4 (2 (2-e/V2) e\v2) (z'
(3'-)/V2)
where the second step holds because f rtr' 2 by 9
2
Finally, also have T1, ||x||| 2 ||.|||, where the first step holds since is nonnegative,
and so by assumption 8 we have z x =T1, 1x s/V2. Similarly, z' 2 s/v2. Therefore,
4 (= e/22) (2' v/v2)
2 > 0, and so we have shown that f(A) 2 62, as desired.
A.6.2 Proof of Lemma 15
First, suppose w E RÝ. Then argmax(ur) (w)) = [i),, and so E argmaxa (we) by Proposition 10 Next,
let c = wij- 22.2. Then we S e for all l ( j. and so defining fw as in 10 we have
(c) (w, - c)² + (u; c)² = 8² = ce (w) = c-
w - -//V2.
Then
(w) (w) + + - Σ (wi ce (w))+ =(w; -
+e/V2 - e/V2 wy - =/V2, e//22 (wy-e/V2)
and so for all l + j, we have we S Wy e/V2 = (w) and thus l & argmax'(w) This verifies that arginax (w) = {j}.
To prove the converse, suppose argmax (w) {i}. By Proposition 10 we then have argmax(w) =
{j}. Let & E a we, then to show w E R5 it suffices to show that wy 2 wk + + e2. Define E IR as
Wk:
{=
02- = Wk + E/ 5/V2,
{= k, ( j,k.
Weg
Then U E Ri, and so we must have ||W - e|| 2 E since k & argmax (w). We calculate
||w- - 21|2 (w, - 02 + (wk 01)² = (w, - wx)² + (e/V2)². This implies that must have (wy w2 2 > e² /2, which completes the proof.
19

---

A.6.3 Proof of Lemma 16
First we verify existence and uniqueness of a. Let
f(a) w
Σ ky
(wk a)+.
Then / R - IR continuous and strictly decreasing bijection, so f(a) = e/V2 must have a unique solution.
Next let this unique solution and let be defined as in 12 Now we verify that is the unique solution to the optimization problem
211l w|l2 u 2 uy + for all k $1}.
t argmin
which defines the projection w to Rt.. By the Karush-Kuhn-Tuuce (KKT) conditions for first-order optimality, it is sufficient verify that
Σ Eulee cx) =0
(13)
where A 2 0 for all k; and 0 = 0 for any inactive constraints, i.e., any for which > U/ + +e/V2 Let AE= = (Wy- a)+ for each k + j. Note that if v2 > Uk + e/22 (i.e., an inactive constraint), then we must have wk < and so A
by construction of v. Then, for any + j.
- w
Σ K
Xu
ex)
= 22 we + d = a A we - we + (we - a)+ = 0,
where e₁ denotes the kth canonical basis vector in R.d_ This proves that the 4th coordinate of the system of equations (13) holds for each & + j. Now we verify the jth coordinate. We have
Xu(e; -ex)
Σ A
Uj Wi
KØ$
a + 8/ 8/V2 Wj
(wn a)+ =
k$j
by our choice of as the solution f(a) = = =/V2.. This verifies the KKT conditions, and thus, is the projection w to By as claimed.
B Extension to randomized algorithms
As mentioned in Section in many applications it is common to use randomization in the construction of classification procedure, in the learning algorithm A and/or in the selection rule In this section we formalize this more general framework, and will see how our results apply.
First, in the non-random setting, learning algorithm A maps data set D (X' [Z]])" to a fitted probability estimate function p X' + Â write the regression procedure as ş A(D). In the randomized setting, also allow for external randomness, ý A(D; E), where & ~ Uniform [0, 1] is random seed (e.g., we might use to randomly shuffle the training data when running stochastic gradient descent).
Next, the non-random setting, a selection rule s is map from A to subsets of [L], resulting in candidate set of labels Š = s(f(z)). In the randomized setting (for instance, if' is the argmax but with ties broken at random), we instead include random seed Ç Uniform[0, 1], and write S = =(f(xr);( (). Formally, then, we have Ar.- [0 (([T)). (Note that the selection rule proposed in this the inflated argmax- is itself not random.)
20

---

Combining the two stages of the procedure, then, the classification algorithm is given by C = s A. where given training set D and a test point x, along with i.i.d. random seeds ç. Uniform 1]. we return the candidate set of labels given by
(, s(f(x): () where ý A(D;E)- derive the non-random setting special case, simply by designing A and to
Of course, not depend on the random seeds ç and Ç.
Now, how do the results of this paper extend to this randomized setting? First, we need to reconsider our definition of selection stability (Definition 2. We will now define
Pr frr8nnt 2
=6 so.
where $ C(D,,; and SV C(D E <), and where the probabilities are taken with respect to the distribution of the random seeds. We can also consider a notion of algorithmic stability (Definition 3) that allows for randomization: we say that A has tail stability (e, 6) if
Pr (1((()) - )) 2 56.
where 9 = 5 and pV : {), and where again probability is taken with respect to the distribution of g.
With these definitions in place, we observe that the result of Proposition 5 still holds in this more general setting for the selection rule argmaxf: A is a randomized algorithm with tail stability (c, (under the new definition given above), then the randomized classification algorithm given by argmax" o.A has selection stability d (again, under the new definition given above), simply due to the e-compatibility property of argmax= (Theorem 2). [SBW24b] proved Theorem 8 in this more general setting of randomized learning algorithms A. so Theorem 6 holds for randomized A under this more general definition of selection stability.
C Extension to finitely many bags
In Section 3.1
discussed how in practice, the bagged algorithm A., would be constructed by taking an empirical average over some large number of sampled bags, rather than computing the exact expectation (,[[A(D()z)) Now that have allowed for randomized learning algorithms (as in Appendix we can formalize this setting: for a random seed & ~ Uniform (0, 1]. we define
(D,E)) = Σ (a))
where the random draw of B many bags, 71, TB. is generated using the random seed g. Recall that (SBW24b) showed tail stability for the bagged version of any algorithm (as restated in Theorem 8 their work also gives a result for the finite-B B case, as follows:
Theorem 17 (SBW24b)). For any base learning algorithm A returning outputs in AL-1, the bagged algorithm Åm (computed with a finite number of bags, B) has tail stability (E, 6) for any e, satisfying
8 2-
Pa.m
16E²
1- Pn.m
B
In particular, combined with our result on the e-compatibility of the inflated argmax, we have the following generalization of our main result (Theorem
Theorem 18. Fix any sample size any bag size m, any inflation parameter O, and any number of bags B Z 1. For any base learning algorithm A, the classification algorithu C = argmax cAm. obtained by combining the bagged version of A (with B many bags) together with the inflated argmax, satisfies selection stability 8 where
8= (1-11/L)
Pn.m
16E²
(14)
n2
Pa.m
B
21

---

(0.1.0)
1.
(2)
[2)
(122)
(2.3)
[1,2]
(2.3)
2,3)
(})
(.3)
(8)
(13)
(1,6,0)
(0,0,
0,0)
(0,0,
Figure 3: The fixed-mant axed-margin selection rule 33. left, and the inflated argmax TT. right, when -= 3.
Comparing to our main result for the derandomized case (Theorem 6 which can be interpreted as taking B + oo), we see that this finite-B B result is essentially the same as Theorem once B > n.
D Compare to simpler selection rule: the fixed-margin rule
In this section, we compare to the simpler axed-margin selection rule, which was defined earlier in for convenience, we define it again here:
margin (w) = { E [L] wy max We - e/V2
EE[L]
the set of all indices j that are within some margin being the maximum.
In this section, will see that this fixed-margin selection rule is s-compatible. Since this rule clearly has advantage of being much simpler than inflated argmax (both terms of definition and interpretability, and in terms of its computation), to the more complex inflated argmax. However, we will also see that the exed-margin selection rule can be very inefficient compared to the inflated argmax: the inflated argmax never return larger set, and will often return substantially smaller one.
might ask whether this rule is perhaps preferable
D.1 Theoretical results
First, we verify that this simple rule satisfies e-copattibility (Definition 4 Proposition 19, For any & > 0, the selection rule sé "margin e-compatible.
In particular, since sf imagin clearly contains the argmax (i.e., argmax(w) Siaagin (w)) and satisfies permutation invariance (in the of Proposition 10), by Proposition 12 this immediately implies that
manginn (w) { argmax (w) {i}
for all w R_, i.c., argmax" at least as good as Smargin at returning a singleton set. However, for this particular selection rule, we can state an even stronger result:
Proposition 20. For any E E and any O,
imaggia (w) 2 argmax (w).
In particular, this theoretical result ensures that the set of candidate labels á returned by the inflated argmax never be larger than for the fixed-margh margin selection rule. In low dimensions, however, the improvement is small. Indeed, for L = 2, we actually have of Smargin (w) = argmax (w) for all w. For = 3, Figure 3 shows that the inflated argmax strictly better (i.e., the set inclusion result of Proposition 20 can, for certain values of be strict inclusion), but the difference in this low-dimensional setting appears minor. Next, however, we will see empirically that as the dimension L grows, the benefit of the inflated argmax be substantial.
22

---

Expected size
40
Method
Fixed-margin Inflated argmax
30
20-
25 Number of classes L
Figure 4: Simulation to compare the selection rules argmax" and margin" The figure shows the average set size, argmaxx (w)l and mmmggin (w)), averaged over 1, 000 random draws of w (with standard error bars shown). See Appendix D.2 for details.
D.2 Simulation to compare the selection rules
In this section, compare the fixed-margin rule the inflated argmax using randomly generated probability weights. For our simulation, we consider the size of the two sets for various values of To sample the weights, we draw standard Gaussian random vector Z NN0,, It) and define as softmax of i.e.
W/ Eteryy e
for j [L]. We then compute argmax" (w) and Smargin (w). where E 0.1. Figure 4 results comparing the average size of the sets returned by each of the two methods. In this setting, we see that the inflated argmax has substantial gains over the fixed-margin selection rule when the number of classes L is large. Even when L 25, the ratio of the expected sizes about 78%, so the inflated argmax has a nontrivial advantage in that setting. When L = 100, the ratio of expected sizes 48%, meaning the inflated argmax on average more than twice as small.
we present
D.3 Proofs for the fixed-margin selection rule
D.3.1 Proof Proposition 19
Let w, R. with s "margin (w) n margin (v) R. Let e argmax, wy and argmax, vs. Then clearly E margin (w), so since Sf smugiin (w) (w) (v) Ø, this implies j & s (mngin()). By definition,
then, 0y I maxt UE e/V2 us s/V2. By identical argument, we have wy I w, e/V2. Then
||w 01/2 > (w, 32 + (wk 22)²
(w, n (vk wx) 12
Wj - (rk e/ e/V2) ²² +
+ -wu (w, (10 (e)2))
> inf (e/V22 - 1) (e/V22 + + eeR
2(e/V2)²= =
This proves || e|l 2 and therefore, have shown that E-compatibility is satisfied.
23

---

D.3.2 Proof of Proposition 20
Suppose j E argmax (w)) Then dist(w, Rí) < so we can find some v E Rt with 1|w - w/1 < c. Then, for any * J.
j wk Uj U2 (w, uy)) (ek -wk)
2 // 2 + (wy - U2) + (oy - wx) since E Rj
2\/22 - (lw, - 0yl wwn vxel
2 e/ V2 - v2v (wy w₁)² + (we - 0x)²
2 s/ - v2wlw vll
$/ /2 V2.-
e/V2..
Since this holds for all l + j. then,
wy > max wkk - E/V2, kE[L]
which proves that j E margin (w).
E
Additional experimental results
In this section, extend our experiment from Section 4 to consider some additional existing methods as baselines and evaluate each method using some common metrics from set-valued classification.
Selection rules.
We compare the following selection rules:
1. Standard argmax.
2. e-inflated argmax with tolerance = .05.
3. Top-K classification with K- 2.
4. Thresholding: including classes in the output set until the sum of probabilities becomes at least 7 = 0.8, i.e.,
(w) = [L] we 2
[() } where
= min(k wp + ... + w|A 2 T). 5. Nondeterministic classification optimized for Fi-score DDB099
NDCF, (w) { [4] we 2 w where
k min k Wt1 + w 2 (k + 1)
with the convention w L+1]
6. Set-valued Baycsaoptimal prediction MWDH21 for any utility a [L] x 2
(10) - Rt.
SVBOP, := argmax Σ we S).
[E(L]
We consider two utility functions based ues and Ugo, defined below.
Evaluation metries. We evaluate each method based on a variety metrics. addition to Spee and Bactsizze defined in Section 4 we assess each method in terms of utility-discounted predictive
accuracy ZCM12 For a set S C [L] and label E [L], define for some parameters a, B > 0,
13
u(t, : fle s}
S
S
24

---

Sel. rule
Algo.
Deorrect-ingle
/
Suet-size
166
/
1800
/
Sup.. inn.
argmax
A
0.879 (0.003)
1.000 (0.000)
0.879 (0.003)
0.879 (0.003)
argmax
Am
0.892 (0.003)
1.000 (0.000)
0.892 (0.003)
0.893 (0.003)
argmax
A
0.873 (0.003)
1.015 (0.001)
0.881 (0.003)
0.883 (0.003)
0.496 (0.005)
argmax
Am
0.886 (0.003)
1.017 (0.001)
0.895 (0.003)
0.897 (0.003)
0.474 (0.005)
top-2
A
0.000 (0.000)
2.000 (0.000)
0.632 (0.001)
0.777 (0.001)
0.905 (0.003)
top-2
Am
0.000 (0.000)
2.000 (0.000)
0.632 (0.001)
0.777 (0.001)
0.918 (0.003)
A
0.756 (0.004)
1.248 (0.005)
0.880 (0.002)
0.909 (0.002)
0.622 (0.005)
Tö.
Am
0.704 (0.005)
1,356 (0.006)
0.867 (0.002)
0.907 (0.002)
0.701 (0.005)
NDC for Fi
A
0.832 (0.004)
1.105 (0.003)
0.889 (0.003)
0.902 (0.003)
0.531 (0.005)
NDC for
Am 0.825 (0.004)
1.138 (0.004)
0.898 (0.003)
0.915 (0.002)
0.586 (0.005)
SVBOP Mes
A
0.838 (0.004)
1.091 (0.003)
0.889 (0.003)
0.901 (0.003)
0.525 (0.005)
SVBOP Mus
Am
0.833 (0.004)
1.119 (0.003)
0.899 (0.003)
0.915 (0.002)
0.577 (0.005)
SVBOP 1480
AA
0.777 (0.004)
1.190 (0.004)
0.885 (0.003)
0.910 (0.002)
0.611 (0.005)
SVBOP
Am
0.744 (0.004)
1.245 (0.005)
0.882 (0.002)
0.914 (0.002)
0.690 (0.005)
Table 2: Results on the Fashion MNIST data set. The table displays the frequency of returning the correct label singleton single average size Biee-size, utility-discounted predictive accuracies M6s and Uso. and the superftuous inflation, Ssu.. indt. For each metric, the symbol / indicates that higher values are desirable, while Y indicates that lower values are desirable. Results for the base algorithm are in white, and results for the subbagged algorithm are in gray. Standard errors are in parentheses.
We use the measures uss with (o. = (1.6, 0.6) and uga with (a, (.22, which respec- tively give small and large rewards for being cautious (NDMH18]
Finally, we directly assess the extent to which each selection rule resorts returning non-singleton set on difficult instances. Specifically, we define the superfluous inflation, which, for a selection rule 8, the ratio of the accuracy of the standard argmax given returns at least two labels divided by the accuracy of s given 8 returns at least two labels:
N Σラ 1 {8g (rgmax( 22
Ssu.. inf.
Σx- 1 (T,, E ,((((,,) )) | 2
If this ratio is close to 1, it means the standard argmax is correct as often as (when the latter expresses uncertainty by returning multiple labels), so outputting multiple labels could be seen as overly conservative. Note that the argmax never returns more than a singleton, so its superfluous inflation is left blank in our results.
Results. This experiment shows that the inflated argmax combined with the subbagged algo- rithm Am has accuracy (according to a variety of metrics) comparable with several alternative methods, does not output overly large sets of candidate labels, and at the same time admits rigorous stability guarantees. That is, our algorithmic framework does not unduly harm empirical performance.
In Table 2 we present results for each selection rule applied to the base algorithm A and the subbagged algorithm A,, described in Section The inflated argmax has significantly higher average precision and significantly smaller set sizes than all of the alternative set-valued classifiers. These two measures are related, since selection rule can only have high precision if frequently returns the correct label as singleton set. The inflated argmax also has the lowest superfluous inflation, meaning that it tends return multiple labels on difficult instances. The ugs of the inflated argmax is also within two standard errors of the was of SVBOPs5. 85. which seeks to optimize this utility. Our method does have a significantly lower uso than many of the competing methods, since this utility more forgiving of returning multiple labels.
25

---

While this experiment considers many different perspectives on set-valued classification, we reiterate that our chief contribution distribution free stability guarantees. This means that, regardless of the dataset or base algorithm used, we can guarantee that our method will be stable. In the context of our experiment, Theorem 6 guarantees that 6j 8" c 1-1/L
n-1 I-Pn.m 0.006 for every test point j = N. Furthermore, our optimality result shows that the inflated argmax returns a singleton as often as possible among all e-compatible selection rules.
26

---

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:
The abstract and Section 1.2 in the introduction clearly state our contributions.
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 to 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:
We discuss limitations the work in Section S
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are 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]
27

---

All the theorems are numbered and cross-referenced in the supplemental material, where the proofs appear.
Justification:
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 or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be 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 of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide all necessary details reproduce the analysis in Section R To reproduce the learning algorithm A, we both provide reference and release own documented code using the same architecture.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer 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.
the contribution is a 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 a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to 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 NeurIPS does not require releasing code, the conference does require 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 it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it 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 reproducing verifying the results.
5. Open access to data and code
28

---

reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We attach our code in our submission to OpenReview, and we will de- anonymize the link to the Github repository after the review process.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://niis.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is 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
/
Cooee//ddeeeSbmimcia ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to 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. only subset of experiments 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 as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is 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: The experimental setting is presented in the core of the paper with enough detail to appreciate the results. The full details are provided with the code.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core 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, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Results in Table 1 are reported with standard errors.
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, or statistical significance tests, least for the experiments that support the 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, or overall with given experimental conditions).
29

---

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).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables 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 execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Section 4 we provide details on the type and quantity of compute workers and total time for the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: htttt:::///eurips..tt cc. http://rwp.ppp..plooccccccccacaa
Answer: [Yes]
Justification:
We have reviewed the Code of Ethics and our work conforms to it.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our research contribution is primarily theoretical and does not have immedi- ately foreseeable impacts on society on a large scale,
Guidelines:
The answer NA means that there 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.
30

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to 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 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 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 intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are 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 of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a 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 no 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 to 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. Licenses for existing assets
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?
Question:
Answer: [Yes]
Justification: Porch and Fashion MNIST are properly credited.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
31

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
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 the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset 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. Crowdsoureing 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 not involve crowdsourcing nor research with human subjects.
Including this information 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 the main paper.
According the NeurIPS Code of Ethics, 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 equivalent approval/review based 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 not involve crowdsourcing nor research with human subjects.
Depending 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 NeurIPS 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.
32


Reviews:
[{"review_id": "bmz0gHjMSa", "reviewer": "Reviewer_mVCr", "summary": "The paper considers the stability of classifiers in multi-class classification. In the considered framework, the classifier is allowed to return a set of candidate classes instead of only one class. The stability is defined as the frequency of a set predicted by one classifier having no union with a set predicted with a classifier trained on the same training set with only one sample removed. The authors proposed the construction of a stable classifier in this framework using bagging and inflated argmax. The proposed approach is proven to have stability guarantees. Additionally, the effectiveness of the approach in terms of increased stability is confirmed in the empirical experiment.", "questions": "- What are the specific applications benefiting from this notation of stability?\n- How does the introduced inflated argmax compare with other set-valued classifiers?", "limitations": "Limitations are discussed. I see no negative social impact of this work.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper is nicely written and easy to follow.\n- The inflated argmax is shown theoretically to be the maximizer of classifier stability.", "weaknesses": "- The authors argue that the argmax is a hard operator that may make the classifier unstable if even small changes of the outputs occur, but the definition of stability used in the paper also uses the hard operator of the set union being equal to an empty set. \n- The definition of the stable classifier as defined in this paper is new to me, and based on the paper, I struggle to find a good motivation for using this specific definition and focusing on it.\n- The method requires bagging, what makes it difficult to apply with heavy architectures.\n- The empirical results are limited to a single experiment. \n- The empirical experiment uses baselines that do not work in the framework of set-valued prediction and always predict only one class, which puts them at a clear disadvantage under the considered task. The comparison should include other set-valued classifiers. E.g., classifiers mentioned in related works or classifiers that optimize simple set-utility functions like in [1] and [2], that can be very efficiently optimized as discussed in [3].\n\n[1] Del Coz JJ, Díez J, Bahamonde A. Learning nondeterministic classifiers. 2009\n[2] Zaffalon M, Giorgio C, Maua DD. Evaluating credal classifiers by utility-discounted predictive accuracy. 2012\n[3] Mortier T, Wydmuch M, Dembczynski K, Hullermeier E, Waegeman W. Efficient set-valued prediction in multi-class classification. 2021\n\n\nNITs:\n- \"The more recent literature has focused on producing a sparse set of weights, but none of these works offer a formal stability guarantee for the support of the weights.\" This statement needs citation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. *“The authors argue that the argmax is a hard operator… but the definition of stability used in the paper also uses the hard operator of the set union being equal to an empty set”*\n\n    The argmax does not satisfy $\\epsilon$ compatibility. The point of the paper is to introduce an $\\epsilon$ compatible relaxation of the argmax, which can be combined with bagging to stabilize any classifier. This relaxation is necessary even though the definition of stability uses a hard operator.\n\n2. *“The definition of the stable classifier … I struggle to find a good motivation for using this specific definition and focusing on it.”* and *“What are the specific applications benefiting from this notation of stability?”*\n\n    Selection stability controls the probability that our algorithm makes contradictory claims when dropping a single data point at random from the training set. In set-valued classification, $\\hat{S}$ represents the set of candidate labels returned by the model. This set should not totally change just by dropping a single observation from the training set. In our revision, we will expand Section 2 of the paper with a more extensive discussion motivating this definition.\n\n3. *“The method requires bagging, what makes it difficult to apply with heavy architectures.”*\n\n    Please see discussion point 2 in our global response.\n\n\n4. *“The empirical results are limited to a single experiment.”*\n\n    The main contribution of our paper is theoretical: we show how to guarantee selection stability for any classifier. Our emphasis is thus on the idea and the theoretical contribution. Our experiment in Section 4 and simulation in Section D.2 serve merely as illustrations of these results to show how they work in practice. \n\n\n5. *“The empirical experiment uses baselines that do not work in the framework of set-valued prediction…”* and *“How does the introduced inflated argmax compare with other set-valued classifiers?”*\n\n    Please see discussion point 1 in our global response.\n\n6. *“‘The more recent literature…’ This statement needs citation.”*\n\n    We should have said ‘the more recent papers in this line of work’ to make it clear that we were referencing the specific citations in the previous sentence. We will make this clearer in the revision.", "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": "QGHwQz6UV0", "reviewer": "Reviewer_FNaQ", "summary": "This submission studies the problem of making set-valued predictions, in which the classifier should strive for an optimal balance between the correctness (the true class is among the candidates) and the precision (the candidates are not too many) of its prediction. \n\nYet, this submission mentions one method for this purpose [1], which predicts, for each query instance, a Bayes-optimal set valued prediction optimizing the F-measure. It seems to miss a discussion on (several) related methods, which are constructed based on both the probability theory and imprecise probability, e.g., the ones discussed in [3, 4, 6] and references therein. \n\nOn the abstract level, the inflated argmax presented in Section 3.2  might be seen as a way to distort/imprecise the given singleton conditional probability distribution. It might enlarge the set of existing approaches targeting similar purposes, such as the ones discussed in [2, 5] and references therein, meaningfully. \n\nThe proposed algorithm is compared with a variant of LeNet-5, implemented in PyTorch [PGML19] tutorials as GarmentClassifier(), and its ensemble version on the Fashion-MNIST data set. Empirical evidence suggests that the proposed algorithm provides better $\\beta_{\\text{prec}}$ than the single classifier, but worse than the ensemble version. The average set size produced by the proposed algorithm seems to be reasonably small.  Results on the selection instability $\\delta_j$ defined in (4), i.e., an approximate of the loss version of the stability $\\delta$ defined in (1), which essentially measures the robustness of the set-valued predictions under tiny changes in the training data set, seems to be in favor of the proposed algorithm. \n\n[1] Del Coz, J. J., Díez, J., & Bahamonde, A. (2009). Learning Nondeterministic Classifiers. Journal of Machine Learning Research, 10(10).\n\n[2] Montes, I., Miranda, E., & Destercke, S. (2020). Unifying neighbourhood and distortion models: part I–new results on old models. International Journal of General Systems, 49(6), 602-635.\n\n[3] Mortier, T., Wydmuch, M., Dembczyński, K., Hüllermeier, E., & Waegeman, W. (2021). Efficient set-valued prediction in multi-class classification. Data Mining and Knowledge Discovery, 35(4), 1435-1469.  \n\n[4] Nguyen, V. L., Destercke, S., Masson, M. H., & Hüllermeier, E. (2018, July). Reliable multi-class classification based on pairwise epistemic and aleatoric uncertainty. In 27th International Joint Conference on Artificial Intelligence (IJCAI 2018) (pp. 5089-5095).\n\n[5] Nguyen, V. L., Zhang, H., & Destercke, S. (2023, September). Learning Sets of Probabilities Through Ensemble Methods. In European Conference on Symbolic and Quantitative Approaches with Uncertainty (pp. 270-283). Cham: Springer Nature Switzerland.\n\n[6] Troffaes, M. C. (2007). Decision making under uncertainty using imprecise probabilities. International journal of approximate reasoning, 45(1), 17-29.", "questions": "Q1: Please refer to \"Weaknesses\" for detailed comments and suggestions for further revision.  \n\nQ2: The notion of selection stability $\\delta$ at sample size $n$ seems to be interesting. I guess the experimental setting provides the necessary information to compute the value of the selection stability $\\delta$ given in (1) . To provide an idea of how empirical evidence may differ from the theoretical results, it might be helpful to compute that value and report the proportion of test instances whose empirical values $1 - \\delta_j$ are smaller than $\\delta$. \n\nQ3: I guess re-defining (4) as $\\delta_j = \\frac{1}{500}\\sum_{k=1}^{500} 1{s(\\hat{p}(\\tilde{X}_j)) \\cap s(\\hat{p}^{\\setminus i_k}(\\tilde{X}_j)) = \\emptyset}$ and changing the description of Figure 2 accordingly (to be consistent with the notion of the selection stability $\\delta$ defined in Definition 1) might make things a bit clearer.", "limitations": "L1: Discussions on related work might need to be extended.\n\nL2:  the empirical study might need to be enlarged with closely related algorithms.  \n\nPlease refer to \"Weaknesses\" for detailed comments and suggestions for further revision.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1: I think taking into account the instability, due to tiny changes in the training data set, when making set-valued prediction is interesting. Yet, assessing this aspect of classifiers seems to be costly, i.e., requiring a sufficiently large number of leave-one-out models.  \n\nS2: Empirical evidence seems to be promising. For example, $\\beta_{\\text{prec}}$ seems to suggest that the proposed algorithm tends to produce a reasonably high proportion of correct singleton predictions. The average set size seems to suggest that the set-valued predictions produced by the proposed algorithms are reasonably small. Empirical evidence regarding the instability defined in (4) seems to be in favor of the proposed algorithm.", "weaknesses": "W1: I think adding a few more competitors would be useful in assessing the potential advantages of the proposed algorithms. For example, threshold-based algorithms, which produce Bayes-optimal predictions of F-measure [1], and $U_{65}$ and $U_{80}$ [3], would be a good choice. They would cost $O(L\\log(L))$ time to sort the labels according to the decreasing order of the predicted conditional probability masses and select the optimal threshold.   \n\nW2: Assessing the classifiers with respect to utility-discounted predictive accuracies, such as $U_{65}$ and $U_{80}$ which respectively give small and large rewards for being cautious [7] , would help to further highlight the potential (dis)advantages of the classifiers. \n \nW3: Moreover, an imprecise classifier should abstain (i.e., provide set-valued predictions) on difficult cases, on which the precise classifier is likely to fail. This would be assessed in different ways. For example, one might consider reporting the correctness of the cautious classifiers in the case of abstention versus the accuracy of the precise classifiers [4].\n\nW4: The tolerance $\\epsilon$ is set to be $.05$. Please provide arguments supporting this choice. Yet, choosing this hyperparameter using a validation set might be challenging. Providing a sensitivity analysis on the choice of  $\\epsilon$ would be helpful. \n\n[1] Del Coz, J. J., Díez, J., & Bahamonde, A. (2009). Learning Nondeterministic Classifiers. Journal of Machine Learning Research, 10(10).\n\n[3] Mortier, T., Wydmuch, M., Dembczyński, K., Hüllermeier, E., & Waegeman, W. (2021). Efficient set-valued prediction in multi-class classification. Data Mining and Knowledge Discovery, 35(4), 1435-1469.\n\n[4] Nguyen, V. L., Destercke, S., Masson, M. H., & Hüllermeier, E. (2018, July). Reliable multi-class classification based on pairwise epistemic and aleatoric uncertainty. In 27th International Joint Conference on Artificial Intelligence (IJCAI 2018) (pp. 5089-5095).  \n\n[7] Zaffalon, M., Corani, G., & Mauá, D. (2012). Evaluating credal classifiers by utility-discounted predictive accuracy. International Journal of Approximate Reasoning, 53(8), 1282-1301.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. *“W1: I think adding a few more competitors would be useful in assessing the potential advantages of the proposed algorithms…”*, *“W2: Assessing the classifiers with respect to utility-discounted predictive accuracies, …”* and “L2: the empirical study might need to be enlarged with closely related algorithms.” \n\n    Please see discussion point 1 in our global response. Below we compare algorithms based on $u_{65}$ and $u_{80}$ per your suggestion in W2. However, we stress that the inflated argmax $\\text{argmax}^\\varepsilon$ is *not* meant to compete with any of these alternative set-valued classification methods, nor is it optimizing for $u_{65}$ or $u_{80}$. It is meant to improve upon the argmax by guaranteeing selection stability. None of these other methods have been shown to satisfy selection stability, and even if they were, ours satisfies the optimality result of Proposition 11.\n\n|| Results for |Base Algorithm $\\mathcal{A}$||| Results with |Subbagging $\\widetilde{\\mathcal{A}}_m$||\n| --- | --- | --- | --- | --- | --- | --- |  --- |\n| |  $u_{65}$ | $u_{80}$ | $\\beta_{\\text{size}}$ | | $u_{65}$ | $u_{80}$ | $\\beta_{\\text{size}}$ |\n| $\\text{argmax}$  |  0.879 (0.003)  |  0.879 (0.003)  |  1.000 (0.000)  | | 0.893 (0.003)  |  0.893 (0.003)  | 1.000 (0.000)  | \n| $\\text{argmax}^\\varepsilon$  |  0.881 (0.003)  |  0.883 (0.003)  |  1.015 (0.001)  | | 0.895 (0.003)  |  0.897 (0.003)  | 1.015 (0.001)  | \n| $\\text{top-}2$  |  0.632 (0.001)  |  0.777 (0.001)  |  2.000 (0.000)  | | 0.631 (0.001)  |  0.777 (0.001)  | 2.000 (0.000)  | \n| Thresholding $\\Gamma^*_{0.8}$  |  0.880 (0.002)  |  0.909 (0.002)  |  1.248 (0.005)  | | 0.868 (0.002)  |  0.907 (0.002)  | 1.248 (0.005)  | \n| NDC for $F_1$ [1] | 0.889 (0.003)  |  0.902 (0.003)  |  1.105 (0.003)  | | 0.898 (0.003)  |  0.915 (0.002)  | 1.105 (0.003)  | \n\n2. *“W3: Moreover, an imprecise classifier should abstain (i.e., provide set-valued predictions) on difficult cases, on which the precise classifier is likely to fail. This would be assessed in different ways. For example, one might consider reporting the correctness of the cautious classifiers in the case of abstention versus the accuracy of the precise classifiers [4].”*\n\n    The idea of \"abstention\" is a useful framework, but in fact, this does actually appear implicitly for any a set valued classifier — if we return the entire set $\\hat{S} = $ {$1,\\dots,L$}, this means that we are not able to say anything about the true value of the label, i.e., this is equivalent to an abstention. In fact, set-valued classification has the capacity to return strictly more information than a label-or-abstain scheme: if we always either return a label (i.e., $\\hat{S} =$ {$y$} for some $y$) or an abstention (equivalently, $\\hat{S} =$ {$1,\\dots,L$}), we do not have the opportunity to express partial information (for example, $\\hat{S} =$ {$y_1,y_2$} — this allows us to express that we have partial information about the true label for a particular sample $X$, i.e., we are allowing adaptivity to our level of uncertainty in different instances). \n\n    Turning to the question of empirical comparison, in a label-or-abstain scheme, measuring the frequency of abstaining is equivalent to measuring how often $|\\hat{S}|=1$, which is related to our precision measure in our experiments.\n\n3. *“W4: The tolerance $\\epsilon$ is set to be .05. Please provide arguments supporting this choice. Yet, choosing this hyperparameter using a validation set might be challenging. Providing a sensitivity analysis on the choice of $\\epsilon$ would be helpful.”*\n\n    The tolerance parameter $\\epsilon$ has an intrinsic meaning; it is different from a tuning parameter such as the regularization parameter $\\lambda$ for Lasso where there is no intrinsic meaning and therefore tuning is the only reasonable way to choose a value. In our setting, $\\epsilon$ represents the margin by which we inflate the argmax — for example setting $\\epsilon$ = 0.05 can, in a sense, be viewed as saying that an estimated probability of 0.45 versus 0.4 is sufficiently close to be ambiguous in terms of which label should be the “winner”. For this reason, it does not seem appropriate to perform a sensitivity analysis.  (Of course, as we see in our theory, it’s also possible for the user to instead choose a desired value of $\\delta$, and then specify $\\epsilon$ accordingly via Theorem 5; again, here $\\epsilon$ would then be determined by the user’s desired value of $\\delta$, and does not need to be tuned.)\n\n4. *“Q2: The notion of selection stability $\\delta$ at sample size $n$ seems to be interesting. I guess the experimental setting provides the necessary information to compute the value of the selection stability $\\delta$ given in (1) . To provide an idea of how empirical evidence may differ from the theoretical results, it might be helpful to compute that value and report the proportion of test instances whose empirical values... are smaller than $\\delta$.”*\n\n    Note that various $\\delta_j$ range over different points in the test set $X_j$, and selection stability holds for all test points $x$. Thus, selection stability means that *all* of the $\\delta_j$ are at most $\\delta$. We will clarify this point in our discussion of the experiment results in our revision.\n\n5. *“Q3: I guess re-defining (4) as... and changing the description of Figure 2 accordingly (to be consistent with the notion of the selection stability $\\delta$ defined in Definition 1) might make things a bit clearer.”*\n\n    Thank you for catching this—we will fix the definition in our revision.\n\n6. *“L1: Discussions on related work might need to be extended.”*\n\n    In discussion point 1 of our global response, we discuss other set-valued classification methods that we have added to the experiments. We will add discussion of these methods to the related work section, including all of the references you suggest. We also welcome any additional suggestions for related work that we should discuss.", "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": "MWqI12zcrQ", "reviewer": "Reviewer_sBU3", "summary": "This paper focuses on the stability of learning multiclass classfiers. It proposes a notion of selection stability for the learning algorithm as well as a modified argmax that returns a set of labels. Evaluations have been conducted using FashionMNIST and simple models.", "questions": "- How tail stability and selection stability relates to $\\epsilon$-compatibility differently? To confirm, do bagging classfiers only satisfy tail stablity? Are there other algorithm designs satisfy these stabilities?\n- How to better interpreter the empirical evaluation results. With similar accuracy shown in Table 1, the proposed method should show better stability in Figure 2?", "limitations": "Practical limitations are presented in section 5.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- This paper focuses on the problem of classifier stability, which has high practical interest.\n- This paper proposes a relaxed form of argmax, which contributes concretely to the problem.\n- Propositions and theoretical relations to existing results are soundly presented.", "weaknesses": "- The presentation of the proposed contribution can be improved.\n  - The core proposal of inflated argmax is introduced in section 3.2, which is too late.\n  - Bagging is not part of proposal, and shows low relation to the contribution, which can be demonstrated using fewer space.\n  - Additional properties of the inflated argmax is also not directly related to the problem.\n  - \"learning stability by leave-one-out data\" and \"prediction stability when using argmax for similar probabilities\" seem to be mixed and not clearly addressed.\n  - Some sentences such as `workflow is fundamentally incompatible with the goal of algorithmic stability` is too extreme, for example, simple streament using proper regularization terms can somehow mitigate the problem.\n- The demonstration of empirical evaluation does not match the last sentence in abstract.\n  - The combination of $\\epsilon$-inflated argmax on the base learning algorithm should be compared.\n  - It is also nice to show results on at least two datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. *“The presentation of the proposed contribution can be improved.”*\n\n     a. *“The core proposal of inflated argmax is introduced in section 3.2, which is too late.”*\n\n      Thank you for this feedback. We agree that introducing inflated argmax earlier in the paper would be better and will try to reorganize if possible in order to do so. However, we would like to point out that the framework of selection stability and its connections to classical algorithmic stability are core contributions, and these are given in Section 2 -- in other words, the inflated argmax definition is not the first novel contribution presented in the paper.\n\n     b. *“Bagging is not part of proposal, and shows low relation to the contribution, which can be demonstrated using fewer space.”*\n\n     While the section on bagging is indeed background material, in order to be able to use bagging as the first stage of our two-stage procedure, we need to recap the requisite tail stability result for bagging -- this is an essential ingredient of our selection stability framework. However, in our revision we will add a sentence to the start of this section to clarify that this is background material and explain its role in what follows.\n\n     c. *“Additional properties of the inflated argmax is also not directly related to the problem.”*\n\n     Section 3.2.2 (on additional properties of the inflated argmax) covers a lot of highly relevant material. We show how to compute our inflated argmax. The properties in Proposition 9 illustrate how the inflated argmax in many ways acts as a natural extension of the argmax. Our optimality result, Proposition 11, connects back to these additional properties by establishing that the inflated argmax is the *most parsimonious $\\epsilon$-compatible extension of the argmax*. In our revision, we will add clarifications to the text to explain the significance of these results and how they relate to the main aims of the paper.\n\n\n     d. *“‘learning stability by leave-one-out data’ and ‘prediction stability when using argmax for similar probabilities’ seem to be mixed and not clearly addressed.”*\n\n     Neither of these phrases are used in the paper. Could you please clarify what you mean?\n\n\n     e. *“Some sentences such as workflow is fundamentally incompatible with the goal of algorithmic stability is too extreme, for example, simple streament using proper regularization terms can somehow mitigate the problem.”*\n\n     It may be possible that regularization can make the predicted probabilities more stable. However, as we point out in Sections 1.1 and 2.3, this is not enough to ensure selection stability *because the argmax is discontinuous.* The issue is that *selection* is unstable whenever the model is nearly equally confident in multiple classes.\n\n2. *“The demonstration of empirical evaluation does not match the last sentence in abstract.”*\n\n    The last sentence of the abstract states, \"we demonstrate that the inflated argmax provides necessary protection against unstable classifiers, without loss of accuracy.\" This does match our empirical evaluation. In Figure 2 we see a dramatic improvement in stability (see also the revised Figure 2 attached as a pdf to the global rebuttal). While $\\beta_{\\text{prec}}$ in Table 1 decreases slightly with the inflated argmax, the difference is not statistically significant. Specifically, comparing the average precision between argmax+subbagging and inflated-argmax+subbagging, the pooled $Z$-score is around 1.5, which is not statistically significant. Despite having $N=10,000$ test samples, there is not a detectable difference in $\\beta_{\\text{prec}}$ before and after employing the inflated argmax. We will make this point more clearly in our revision.\n\n     a. *“The combination of 𝜖-inflated argmax on the base learning algorithm should be compared.”*\n\n     We have added this baseline to our table: please see discussion point 1 in our global response. We have also added it to the revised Figure 2, which is attached in our global response.\n\n\n     b. *“It is also nice to show results on at least two datasets.”*\n\n     We agree that additional experiments may be useful, and would be happy to add more experiments to the supplement to pose the same questions under different settings and different data generating processes, in our revision. However, the main contribution of our paper is theoretical: we show how to guarantee selection stability for *any classifier* on *any dataset*. Our emphasis is thus on the idea and the theoretical contribution. Our experiment in Section 4 and simulation in Section D.2 serve as illustrations of these results to show how they work in practice. That being said, we will add more experiments to the supplement to reinforce these results.\n\n3. *“How tail stability and selection stability relates to 𝜖-compatibility differently? To confirm, do bagging classfiers only satisfy tail stablity? Are there other algorithm designs satisfy these stabilities?”*\n\n    For the first question, we address the relationship between all three criteria in Proposition 4. We can expand the discussion around Proposition 4 in our revision to explain the relationship more clearly. For the latter two questions, other meta-algorithms may satisfy tail stability. This is an interesting open question. \n\n\n4. *“How to better interpreter the empirical evaluation results. With similar accuracy shown in Table 1, the proposed method should show better stability in Figure 2?”*\n\n    Our proposed method does show much better stability. Note in Figure 2 that smaller curves are more stable. In our revised Figure 2 (attached to our global response), the instability measure $\\delta_j = 0$ for *every* test point for our proposed method.", "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": "XSgLjD0aAl", "reviewer": "Reviewer_m1xX", "summary": "An algorithm is considered stable if small perturbations in the training data do not result in significant changes to its output. Stability has been previously explored in the context of regression. This paper extends this concept to the multiclass framework, where previous work has focused on stability in terms of output probability rather than label selection processes. Given that argmax is not a continuous function, it can lead to instability in the classifier. To address this issue, the authors first define stability for the multiclass domain and then demonstrate that a stable classifier alone is insufficient; a corresponding label selection strategy is also necessary. The authors propose a framework combining bagging and inflated argmax to derive such a combination, which they validate experimentally, showing that their approach achieves higher stability while maintaining precision at a minimal cost.", "questions": "1. From the definition of stability given in 4, it is evident that the authors trained the classifiers multiple times while removing training samples. How does the overall average of average precision look like in such cases? Such a metric might show the advantage the proposed framework.\n2. My other main question is related to practicality. I would like to know the author's thought more regarding that limitation.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The authors introduce a novel definition of algorithmic stability in classification, shifting the focus from output probability to predicted labels. They demonstrate that, according to this definition, a stable classifier is insufficient for achieving overall stability. Furthermore, they establish a connection between this notion of stability and classical algorithmic stability concepts. Building on these insights, the authors propose an approach that leverages bagging and inflated argmax to achieve said stability.\n2. It is essential to emphasize that the proposed framework operates without assuming any specific distribution on the data. Additionally, it does not rely on the number of classes or dimensionality of the covariates, making it versatile and applicable to various algorithms.\n3.The experimental findings demonstrate the stability of the proposed framework. Moreover, they reveal the negative impact of argmax on stability. Notably, the results show that the proposed approach incurs only a minor penalty to precision, underscoring its effectiveness.", "weaknesses": "1.The authors point out my primary concern in their discussion section, highlighting the practicality of the proposed framework. Notably, bagging is an computationally expensive procedure, and while the authors suggest that parallelization can mitigate this issue, I agree that this does not necessarily translate to a reduction in overall cost. This becomes particularly challenging when dealing with large datasets commonly encountered in modern classifiers (e.g., image classification), where the sheer scale of computation required can be prohibitively expensive even with multiple GPUs.\n2. The experimental section relies heavily on a single dataset and classifier combination. To fully demonstrate the benefits of the proposed framework, I believe it would be necessary to conduct a more comprehensive set of experiments. Specifically, I suggest that the authors provide additional evidence through experimentation to illustrate how the slight tradeoff in precision is justified by the gained stability in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. *“The authors point out my primary concern in their discussion section, highlighting the practicality of the proposed framework. Notably, bagging is an computationally expensive procedure, and while the authors suggest that parallelization can mitigate this issue, I agree that this does not necessarily translate to a reduction in overall cost. This becomes particularly challenging when dealing with large datasets commonly encountered in modern classifiers (e.g., image classification), where the sheer scale of computation required can be prohibitively expensive even with multiple GPUs.”* and *“My other main question is related to practicality. I would like to know the author's thought more regarding that limitation.”*\n\n    Please see discussion point 2 in our global response, and let us know if you have any additional concerns regarding practicality.\n\n\n2. *“The experimental section relies heavily on a single dataset and classifier combination. To fully demonstrate the benefits of the proposed framework, I believe it would be necessary to conduct a more comprehensive set of experiments. Specifically, I suggest that the authors provide additional evidence through experimentation to illustrate how the slight tradeoff in precision is justified by the gained stability in practice.”*\n\n    We agree that additional experiments may be useful for a more detailed understanding of this tradeoff, and would be happy to add more experiments to the supplement to pose the same questions under different settings and different data generating processes, in our revision. However, we would like to point out that, in our view, this experimental comparison is not central to the main point of the paper. While from an empirical point of view, our method versus a competing method are simply two different points along the tradeoff between precision and stability, from the theoretical point of view they are not on equal footing at all: our method offers a theoretical guarantee of selection stability, and there is no guarantee of this type at all for competing options. \n\n\n3. *“From the definition of stability given in 4, it is evident that the authors trained the classifiers multiple times while removing training samples. How does the overall average of average precision look like in such cases? Such a metric might show the advantage the proposed framework.”*\n\n    In the table below, we compare $\\beta_{\\text{prec}}$ (as defined in the paper) to the \"overall average of average precision\" over all $500$ leave-one-out models. In this experiment, there is not a substantial difference between $\\beta_{\\text{prec}}$ (the original precision measure) and $\\beta^{\\text{LOO}}_{\\text{prec}}$ (this new measure).\n\n|  | Results for Base Algorithm $\\mathcal{A}$ | | | Results with Subbagging $\\widetilde{\\mathcal{A}}_m$ | |\n| -------- | ------- | ------- | ------- | ------- | ------- |\n|          |  $\\beta_{\\text{prec}}$ | $\\beta^{\\text{LOO}}_{\\text{prec}}$ | | $\\beta_{\\text{prec}}$ | $\\beta^{\\text{LOO}}_{\\text{prec}}$ |\n|  $\\text{argmax}$  |  0.879 (0.003)  |  0.884 (0.002)  | | 0.893 (0.003)  |  0.893 (0.003)  |\n|  $\\text{argmax}^\\varepsilon$  |  0.873 (0.003)  |  0.879 (0.003)  | | 0.886 (0.003)  |  0.886 (0.003)  |\n|  $\\text{top-}2$  |  0.000 (0.000)  |  0.000 (0.000)  | | 0.000 (0.000)  |  0.000 (0.000)  |\n|  Thresholding $\\Gamma^*_{0.8}$  |  0.756 (0.004)  |  0.761 (0.004)  | | 0.704 (0.005)  |  0.703 (0.005)  |\n|  NDC for $F_1$ [1]  |  0.832 (0.004)  |  0.836 (0.003)  | | 0.825 (0.004)  |  0.825 (0.004)  |", "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": "yUNhBIEr6E", "reviewer": "Reviewer_LzW3", "summary": "This paper studies and proposes a new theoretical framework to study algorithmic stability for multiclass classification with a focus on a stable class selection given predicted class probability. Based on the proposed theory, the proposed selection criterion based on bagging called \"inflated argmax\" was proposed. Theoretical analysis suggests that the proposed inflated argmax is stable, while also give a relatively tight decision for the candidate prediction set. Simple experiments using Fashion-MNIST were also provided to show the stability of inflated argmax as well as how tight the candidate set can be.", "questions": "1. Can we also see the performance of inflated argmax *without bagging* in the experiment? In my understanding, this should also be possible with the proposed efficient algorithm. This can be useful to see how important the bagging method is needed for the proposed algorithm. \n2. Visualizing the number of bags needed to perform reasonably in the experiment can also be useful. Because it can be expensive if we use more sophisticated algorithm or using larger dataset.\n3. In deep learning, overconfident problem of probability can often be an issue when one wants to use probability score. How does this problem affect the proposed inflated argmax in practice?\n4. Can we know that it is likely that the second class to be chosen as a candidate class is likely to be the second-largest probability class?\n5. Is it reasonable to say that precision is similar given different average precision and standard error provided (Lines 293--294)?\n6. I was wondering if there are other possible baselines in related work that could be used in the experiments? \n7. Suggestions on simple baselines\n7.1 Top-2 class prediction, size of beta will be 2.\n7.2 Predicting classes until sum of probability becomes a certain constant, e.g., if we set threshold = 0.8 and prediction probability vector is [0.1, 0.1, 0.1, 0.2, 0.6], then we will pick the last two classes (0.2 and 0.6). This simple idea looks intuitive and gives flexible set and this is the most simple baseline I had in mind that could be effective when I first read this paper. How do you think about this baseline?\n\nI think the core contribution of this paper is the theory of stable classification rule. Therefore, although the experiment looks quite weak, my current rating is on the accept side (weak accept). I know it can be too much to ask to improve experiments a lot and I do not expect authors to fix everything according to my suggestions. But I would appreciate if the authors can reply to make sure that my understanding is correct.", "limitations": "Discussion of limitations of the proposed method and potential future work were appropriate.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides strong theoretical framework for future study of stable selection criteria for the multiclass classification problem given predicted class probability.\n2. The proposed notion of $\\epsilon$- compatible is simple to understand and a reasonable extension of classical algorithmic stability noted in Definition 2. I feel this notion is neat and also very useful for further analysis in Proposition 4 and beyond.\n3. The simple rule that satisfies the stability but could give a looser quality than inflated argmax was also provided to give a better understanding of the problem. The study was quite detailed in Appendix D., which I find quite amazing.\n4. Despite the complicated notion of inflated argmax, the efficient computation of selection rule once bagging is done is nicely provided in Proposition 10.", "weaknesses": "1. Experiments were quite weak in my opinion to highlight the effectiveness of inflated argmax. For example, more reasonable baseline that has larger than 1 $\\beta_{\\mathrm{size}}$ could have been provided to show that inflated argmax is quite favorable if it allows to predict more than one class. Curreent baselines are restrictive in the sense that only one class can be chosen (argmax). Several improvements could also be done (please see the questions section for possible improvements). \n2. The proposed inflated argmax requires bagging, which can be quite computationally expensive, or prohibitive in some scenarios under limited resources or large dataset/model.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. *“Experiments were quite weak in my opinion to highlight the effectiveness of inflated argmax. For example, more reasonable baseline that has larger than 1 𝛽_size could have been provided to show that inflated argmax is quite favorable if it allows to predict more than one class. Curreent baselines are restrictive in the sense that only one class can be chosen (argmax). Several improvements could also be done (please see the questions section for possible improvements).”*\n\n    Please see discussion point 1 in our global response.\n\n\n2. *“The proposed inflated argmax requires bagging, which can be quite computationally expensive, or prohibitive in some scenarios under limited resources or large dataset/model.”*\n\n    The inflated argmax operates on the predicted probabilities, so it does not require bagging per se. The inflated argmax on its own is very computationally efficient. Please see discussion point 2 in our global response for discussion on the computational cost of bagging. \n\n\n3. *“Can we also see the performance of inflated argmax without bagging in the experiment? In my understanding, this should also be possible with the proposed efficient algorithm. This can be useful to see how important the bagging method is needed for the proposed algorithm.”*\n\n    We have added this comparison—please see the pdf attached to our global response. As we can see, both bagging and the inflated argmax are important for selection stability.\n\n\n4. *“Visualizing the number of bags needed to perform reasonably in the experiment can also be useful. Because it can be expensive if we use more sophisticated algorithm or using larger dataset.”*\n\n    We have rerun the experiment with a larger number of bags—please see the pdf attached to our global response. As you can see, this dramatically improves selection stability, especially with the inflated argmax. In our revised appendix, we will investigate more thoroughly how the number of bags impacts stability in practice.\n\n\n5. *“In deep learning, overconfident problem of probability can often be an issue when one wants to use probability score. How does this problem affect the proposed inflated argmax in practice?”*\n\n    This is an interesting question. Overconfident probability scores mean that the top label is ahead by a large margin, so the inflated argmax will frequently return a singleton if $\\epsilon$ is sufficiently small. In our global response, per your suggestion, we have attached a pdf which shows the stability of the base algorithm with the inflated argmax. On its own, the inflated argmax does not lead to selection stability *precisely because of overconfident probabilities.* Bagging addresses the problem of overconfidence, and then the inflated argmax captures the fact that several labels have similar probability scores after bagging.\n\n\n6. *“Can we know that it is likely that the second class to be chosen as a candidate class is likely to be the second-largest probability class?”*\n\n    Yes, this is guaranteed by the 3rd statement of Proposition 9.\n\n\n7. *“Is it reasonable to say that precision is similar given different average precision and standard error provided (Lines 293--294)?”*\n\n    Yes, it is reasonable. For example, if we compare the average precision between argmax+subbagging and inflated-argmax+subbagging, the pooled Z-score is around 1.5, which is not statistically significant. Considering further that we’re making multiple comparisons in the table, it would be unreasonable to say the rates are very different.\n\n\n8. *“I was wondering if there are other possible baselines in related work that could be used in the experiments?”* and *“Suggestions on simple baselines 7.1 Top-2 class prediction, size of beta will be 2. 7.2 Predicting classes until sum of probability becomes a certain constant, e.g., if we set threshold = 0.8 and prediction probability vector is [0.1, 0.1, 0.1, 0.2, 0.6], then we will pick the last two classes (0.2 and 0.6). This simple idea looks intuitive and gives flexible set and this is the most simple baseline I had in mind that could be effective when I first read this paper. How do you think about this baseline?”*\n\n    We have added both of your suggestions and others. Please see discussion point 1 in our global response.", "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 of the reviewers for their insightful comments and effort in reviewing the paper. Below we discuss two topics that came up in multiple reviews.

1. **Improvements to the experiments section.** Based on feedback from several reviewers, we have expanded our experiments section by adding some additional existing methods as baselines to our table of results. We added several methods for set-valued classification suggested by the reviewers. 

    The old version of our experiment served to illustrate what would happen if, as is most common in classification, you only return a single label. The experiment showed that practical learning algorithms can indeed be unstable for selection, even with bagging. The experiment illustrates our theory that the inflated argmax, combined with bagging, can ameliorate this issue for any dataset and any learning algorithm.

    Based on feedback, we added the following baselines:
     - Top-2 class prediction.
     - Thresholding: Predicting classes until sum of probability becomes at least 0.8, 
     - Non-deterministic classification (NDC) [1] optimized for $F_1$-score.

    We stress, however, that these methods are not in direct competition with the inflated argmax since, since our stability framework is one of the main contributions of our paper. That is, no existing method for set-valued classification can guarantee selection stability.

    Below we present the updated table of results. Recall that $\beta_{\text{prec}}$ is the precision, meaning the probability that the algorithm returns the correct singleton, and $\beta_{\text{size}}$ is the average size of the set of candidate labels. Note that the inflated argmax is smaller than all competing set-valued methods and has a higher value of $\beta_{\text{prec}}$.

    We also reran the experiment with a larger number of bags—**please see the attached pdf for the stability curves**. We find that increasing the number of bags improves stability even further, especially with the inflated argmax.

|  | Results for Base Algorithm $\mathcal{A}$ || | Results with Subbagging $\widetilde{\mathcal{A}}_m$ |  |
| -------- | ------- | ------- | ------- | ------- | ------- |
|          |  $\beta_{\text{prec}}$ | $\beta_{\text{size}}$ | | $\beta_{\text{prec}}$ | $\beta_{\text{size}}$ |
|  $\text{argmax}$  |  0.879 (0.003)  |  1.000 (0.000)  | | 0.893 (0.003)  |  1.000 (0.000)  |
|  $\text{argmax}^\varepsilon$  |  0.873 (0.003)  |  1.015 (0.001)  | | 0.886 (0.003)  |  1.016 (0.001)  |
|  $\text{top-}2$  |  0.000 (0.000)  |  2.000 (0.000)  | | 0.000 (0.000)  |  2.000 (0.000)  |
|  Thresholding $\Gamma^*_{0.8}$  |  0.756 (0.004)  |  1.248 (0.005)  | | 0.704 (0.005)  |  1.354 (0.006)  |
|  NDC for $F_1$ [1]  |  0.832 (0.004)  |  1.105 (0.003)  | | 0.825 (0.004)  |  1.137 (0.004)  |

2. **Computational cost of bagging.**   Several reviewers pointed out that bagging may be computationally very demanding for modern large-scale algorithms. We would like to discuss this point here in a bit more detail (and will also add discussion into our revised paper).

    First, our paper is the first work demonstrating that guaranteed black-box classifier stability is possible at all — certainly it is very interesting and important to consider whether there are computationally efficient methods that can achieve this aim, but a first question is whether the aim is achievable at all. Our paper lays out the key definitions and theoretical groundwork for this problem, opening up new avenues for future research.  Moreover, if more efficient learning algorithms could in future be shown to satisfy tail stability (i.e., without bagging) then the main contribution of our paper—the inflated argmax—will be equally applicable and relevant. The inflated argmax is computationally efficient and, due to the two-stage structure of our theory, can be combined with any method shown to have tail stability at the first stage, i.e., can be separated from bagging.

    Next, to return to the question of bagging, we would like to justify why we feel that using bagging for the first stage of the procedure may in many cases be very feasible from the computational point of view. While the original definition of bagging uses the conventional bootstrap, where each bag contains as many samples as the original data set, i.e. $m = n$, in our framework we allow for arbitrary bag size $m$, which could be much smaller than the sample size $n$. Massively subsampling the data ($m \ll n$) can actually help scale learning algorithms to large data sets [2]. Moreover, bagging with $m \approx n$ can be expensive, but there are still many areas of machine learning where it is used, notably in Random Forests. Finally, our experiments also show that a modest number of bags ($B=200$) is all that we really need to start seeing major gains in selection stability.

   

References:

[1] Juan José Del Coz, Jorge Díez, and Antonio Bahamonde (2009). "Learning Nondeterministic Classifiers." *Journal of Machine Learning Research* 10(10).

[2] Ariel Kleiner, Ameet Talwalkar, Purnamrita Sarkar, and Michael I. Jordan (2014). "A scalable bootstrap for massive data." *Journal of the Royal Statistical Society Series B: Statistical Methodology* 76(4): 795-816.

Meta-review: The reviewers have essentially converged around the idea that the paper is a worthy addition to NeurIPS; the paper indeed contains an interesting theoretical framework to build stability, and I commend the authors for elaborating further on experiments at rebuttal / discussion time.

At camera-ready time, I strongly suggest that the authors integrate not just their additional experimental results, but also make clear(er) point 2. in their rebuttal.
Decision: Accept (poster)