Constrained Binary Decision Making
Authors: Daniel Průša
Vojtech Franc
Venue: NeurIPS 2024 poster (2024)
Keywords: binary statistical decision making
constrained optimization
Neyman-Pearson problem
selective classification
Primary area: probabilistic_methods

Abstract: Binary statistical decision making involves choosing between two states based on statistical evidence. The optimal decision strategy is typically formulated through a constrained optimization problem, where both the objective and constraints are expressed as integrals involving two Lebesgue measurable functions, one of which represents the strategy being optimized. In this work, we present a comprehensive formulation of the binary decision making problem and provide a detailed characterization of the optimal solution. Our framework encompasses a wide range of well-known and recently proposed decision making problems as specific cases. We demonstrate how our generic approach can be used to derive the optimal decision strategies for these diverse instances. Our results offer a robust mathematical tool that simplifies the process of solving both existing and novel formulations of binary decision making problems which are in the core of many Machine Learning algorithms.

Constrained Binary Decision Making
Daniel Prúša
Vojtéch Franc
Department of Cybernetics Faculty of Electrical Engineering Czech Technical University Prague {prusapal, xfrancv)@fel cvut.
Abstract
Binary statistical decision making involves choosing between two states based on statistical evidence. The optimal decision strategy is typically formulated through a constrained optimization problem, where both the objective and constraints are expressed integrals involving two Lebesgue measurable functions, one of which represents the strategy being optimized. In this work, we present a comprehensive formulation of the binary decision making problem and provide a detailed characterization of the optimal solution. Our framework encompasses wide range of well-known and recently proposed decision making problems as specific cases. We demonstrate how our generic approach can be used to derive the optimal decision strategies for these diverse instances. Our results offer a robust mathematical tool that simplifies the process of solving both existing and novel formulations of binary decision making problems which are in the core of many Machine Learning algorithms.
Introduction
Binary statistical decision making (BDM) involves selecting between two possible states using statistical evidence. This approach applied across various fields, from classical statistics machine learning. A notable example is the Neyman-Pearson problem [18), which establishes the optimal strategy for testing two hypotheses and serves the foundation for optimal detectors. Beyond classical statistics, BDM problems are used in many machine learning applications, such as detecting oftt----dittiitti (OOD) samples
20 22 23). designing selective g 91 and developing selective classification in the presence of OOD data
10
classifiers [13] 12
(SCOD) 24 16
name a few.
Instances of BDM determine the best decision-making strategy by solving constrained optimization problem involving Lebesgue measurable functions in both the objective and constraints. Understand- ing the structure of this optimal strategy is crucial before deploying efficient methods to find it. The Neyman-Pearson lemma, well-known example found in many statistics textbooks,, states that an optimal detection strategy relies on comparing the likelihood ratio of the underlying distributions with threshold. Therefore, learning a detector from examples involves effectively approximating the likelihood ratio and then tuning the decision threshold.
However, defining the optimal strategy for various BDM problems is generally challenging, often taking several years to discover. For instance, the Bounded- counded-Improvemeend and Bounded-Abssention models, serving formal definitions of optimal selective classifiers, The optimal strategies for these two BDM problems were initially described in [8). marking a 14-year period of development. Another recent example is the work of [24), who developed method for learning a selective classifier handling inputs contaminated by out-of-distribution data, so called SCOD problem. Although they formulated an optimal SCOD selection strategy accept input samples as a solution to novel BDM problem, they did not analyze the optimal strategy directly.
first introduced in (19).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Instead, they proposed a selector strategy named SIRC, combining two detectors using heuristically chosen non-lineat functions. In recently published paper [16], the authors derived an optimal solution for the SCOD problem, demonstrating that the optimal selective strategy involves simple linear combination of the two detectors. Empirical evidence confirmed that the optimal linear strategy consistently outperforms the heuristic SIRC, despite its minor change. This example underscores the advantages of understanding the structure of the optimal solution to underlying BDM problems.
In this paper, we present comprehensive formulation of the BDM problem and thoroughly charac- terize the optimal strategy. Our framework encompasses various BDM problems as special cases, enabling us to derive optimal decision strategies for these instances. This provides robust mathe- matical tool for solving both existing and new BDM problems. The related theorem is highly general. applying to both discrete and continuous instance spaces without requiring the differentiability of decision and loss functions, unlike common proof techniques based on Lagrange duality.
To illustrate the impact of our work, in Section 2 we formulate several practical modifications of existing BDM problems. In Section we demonstrate the derivation of their optimal strategies using our main result, which characterizes the optimal strategies of a generic BDM as presented in Section 3
2 Examples of existing binary decision making problems
In this section, we present various examples of BDM problems, with a focus on the significant application of designing selective classifier in the presence of out-of-distribution (SCOD) sam- ples [24] [6]. We note that while selective classification itself is not the contribution of this paper, it serves to illustrate the practical importance and diversity of BDM formulations in addressing recently emerging problem in the machine learning community.
Consider a given classifier h: X' + V, where X' is the instance space and } a finite set of labels. We assume the classifier h was designed to minimize the prediction loss f: y x y - R. Our task is to equip the classifier h with binary stochastic decision strategy e: X -> [0, 1]. The strategy acts as a selector for input samples. The input sample x E X' accepted for prediction by h with probability c(x) and is rejected otherwise. Thus, the pair ch: X + YU {reject) forms reject option classifier 33;
(h, (z))) {{
h(x)) with probability c(z). reject with probability 1 1-c(x).
We assume the following statistical model of the data. Input samples are generated from a mixture of two distributions: the in-distribution (ID) Pr: X - RR and the out- distribtiii (OOD)
po: X + R4. Thus, the input sample E X' is generated from
p(z) pr (x) (1 7) + PO(x)=,
(1)
where π E [0, 1] represents the portion of OOD samples in the mixture. Furthermore, if the sample I E y is generated from the in-distribution, a latent label y E y is generated according to the distribution p(y z).
In the outlined statistical model, prediction uncertainty arises from two main sources: i) inherent data uncertainty (aleatoric uncertainty), stemming from the stochastic relationship between the input x and the latent label y. and ti) distribution uncertainty, which arises from input samples potentially coming from either in-distribution or nut-of-distribution sources. We will explore six different BDM instances to develop a selector e that admits an input sample æ for classification with only when the prediction uncertainty is below an acceptable threshold. Each instance defines an optimal selector in a unique way. In Section 2. we described the Jeymann-Paaree formulation of the OOD optimal detector [18), Improvement and Bounded- Absttnttn models [9], addressing only data uncertainty. In Section 2.4 we describe the SCOD problem [24), which defines the optimal selector addressing both distribution and data
which addresses only distribution uncertainty. Sections 2.2 and 2.3 cover the
uncertainty. Additionally, Sections 2.5 and 2.6 give examples of two novel practical variants of the
SCOD problem.
The primary contribution of this paper is a framework for solving a broad range of BDM problems. In Section 3 we detail the main theorem that characterizes the optimal solution for a generic BDM problem. Section 4. we demonstrate how to apply this theorem to find solutions easily for all the BDM instances described here.

---

2.1 Neyman-Pearson (NP) detector
Assume our goal is design selector strategy c: X [0, 1] that accepts only in in-distribution (ID) samples and rejects out out-of- of-distribution (OOD) samples. In other words, functions as binary classifier to distinguish ID and OOD samples. We will characterize the strategy e using two metrics. First, using the True Positive Rate (TPR) representing the probability that ID sample x is correctly accepted by the strategy:
tpr(c) 1 pr (x( c(x) dr.
(2)
Second, using the False Positive Rate (FPR) representing the probability that OOD sample x is incorrectly accepted by
fpr(c) J po(z) c(x) dr.
0, the NP task is to find strategy ct that solves the Given maximal acceptable FPR, max following BDM problem [8]
max tpr(c) s.t. fpr(c) S fprmax c: X [01]
(4)
well-known solution to the NP task 4 is the strategy:
if g(x) < 0 g(x) 0 0 if g(x) > A
(((x)
(5)
where g(x)
is the likelihood ratio, E IR is a decision threshold, and т E [0, is probability of acceptance when g(z) O.
pofa) pr(
Knowing the structure of the optimal strategy simplifies its construction significantly. The key to an optimal decision is accurately modeling the likelihood ratio g(z). Once the likelihood ratio is known, finding the optimal strategy involves setting the threshold 0 and the randomization parameter typically done by tuning these parameters validation sample. Moreover, if pr(x) and po (2) are continuous, the randonization parameter T can be arbitrary since the event g(x) = has zero probability of occurring.
2.2 Selective Classification: Bounded-absseetion model
Let us consider the ideal scenario where the input instances E X' are solely generated by the in-distribution Pr (z),, meaning the out-of-distributin portion in the model (1) is π O. Our aim devise selection strategy et X' - [o, 1] that accepts only those input samples x E X' where the prediction loss {v, h(x)) is likely to be small. We will characterize the strategy e using two metrics. First, we employ the notion of coverage:
<(c) / pr(x)) c(x) dz
(6)
which reflects the probability of accepting an input sample. Secondly, we introduce the concept of "selective risk":
1 Σ pr v) lly, h(z)) c(x) dr
R (h,
X' vEy
Φ(c)
representing the expected prediction loss é: y x y + R on the accepted samples.
Given minimal acceptable coverage > 0, the bounded-abstennion model defines the optimal selector strategy as the solution to the following BDM problem 19
min heyx
R R (h,,c)
s.t. ((c) 2 w.
(8)
The solution to the sasteedd-abtttttion model 8 consists of the Bayes predictor
h (a:) argmin,, Σ Pi(y x)((u.v')

---

and the strategy 8 9
r(x) < 8
(x)
if r(x) = 80 r(z) > 8
(9)
where
r(x) = E'E prly x) h())
(10)
DEV
the conditional risk of the classifier for the input x, 0 R decision threshold, and 7 E [0, 1] is a probability of acceptance when r(x) O.
Note that the BDM problem (8 was formulated in 19 but the optimal solution was not derived until 14 years later [].
The values of 0 and depend on (r. y) and w, and in practice, they are tuned on validation data once a good model of the conditional risk r(x) is established. While this process can be challenging and needs be addressed for each problem separately, it is still significantly easier than tuning an unknown function. For example, discretizing the possible values of 0 and r and conducting an exhaustive search, although not always optimal, has proven effective in practice.
The additivity of the risk R$ allows h to be optimized independently of resulting in the Bayes predictor for all problems discussed in the following sections. Therefore, from this point on, we will focus solely on optimal strategies for c.
2.3 Selective Classification: Hounded-improvemeee rejection model
A symmetric definition of the optimal selector strategy is provided by the bounded- improdement model. Given maximum acceptable selective risk X 0, the optimal selector the solution the following BDM problem:
max ó(c) A,C
s.t.
(h, S.
(11)
The solution to the Nounded-improveedd model 11 is similar to the strategy 9 differing only in the specific values of the decision threshold 0 and the randomization parameter
2.4 Selective Classification in the presence of OOD data (SCOD)
The SCOD problem integrates the objectives of the Seyman--Parseee task and bounded-abstention models. The aim is to design a selector strategy e E X' + [0, 1] that accepts an input sample x if is likely to be correctly predicted by h and unlikely to be generated from the OOD. Formally, the objective is defined using three metrics: True Positive Rate lpr(c), equation (2). False Positive Rate [pr(c). equation (3) and selective risk R (h, c). equation (7). Given the relative cost a 0 and the minimum acceptable TPR, (prmin min > 0, the goal is to find a strategy e* that solves the following BDM problem (24):
min Ney ce j.j
[11 a) RR, a fpr(c)
tpr(c) 2 tpr min
(12)
The solution to the SCOD problem
12 is the strategy [6 7:
if s(x) > 0, if s(x) 0 where s(x) r(x) otprmmn
(x) 0
g(x)
(13)
8(x)
a
for E [0, 1) and s(x) g(x) for 1. Here, r(x) is the conditional risk (10) g(xr)
(x) is
pr (x)
the likelihood ratio, 0 a decision threshold, and E [o, the acceptance probability for the case s(x) r(x).
The BDM problem was formulated in 24 The optimal solution for continuous distributions was recently derived in 16), and the solution for the general case provided in [7].

---

2.5 SCOD: bounded TPR-FPR
To demonstrate the versatility of our framework, we will present two novel variants of the SCOD problem in in this section and the next. While the optimal solutions to these new formulations are unknown, they can be easily derived using the framework proposed in this paper, we will later show.
The original formulation of the SCOD problem 12 relies the user-defined relative cost However, this assumes that the prediction loss l: y the OOD sample share the same units, which is not always practical. In such cases, it can be useful to remove the FPR from the objective and impose a hard constraint on it instead. Specifically, we can alternatively formulate the SCOD problem follows. Given tprmin >> 0 and fpr mprmax > O, the goal is to find strategy c* that solves the following BDM problem:
IR and the cost for incorrectly accepting
min he(oj1
Rd (h,c)
(pr(c) 2 (p"min and [pr(c) [prmax
(14)
In Section we will prove that the optimal solution the problem (4) is the strategy:
if s(x) 0, if s(x) 0, s(x) > 0,
(x)
where s(x) = r<)) Bg(x),
(15)
with 8 E R as the decision threshold, т E [o, 1] as the acceptance probability when s(x) = and IR constant depending on the problem setup.
2.6 SCOD: bounded Precision-Recal
Assume the portion of OOD samples и known or can be estimated. some applications, useful to replace FPR with precision, which is the proportion of true ID samples among all accepted inputs. Precision prec(e) defined as:
(1 - TT) tpr(c)
prec(c) fpr(c) + tpr(c) (1-
If we want to avoid defining the relative cost, as in [14. we can formulate the SCOD problem as follows. Given tpr > and precmin > 0, the goal is find strategy et which solves the following BDM problem:
min (S c) s.t.
tpr(c) 2 tprmin and prec(c) precmin
(16)
key keya"ceeoo.n ce/o0.1
In Section 4. we will prove that the optimal solution to the problem 166 is strategy similar to (5) differing only in specific values of the decision threshold r, the randomization parameter t and the multiplier 3.
2.7 Summary
In the previous sections, we described six BDM problems, each with unique optimal selector strategy. The first four are established formulations, while the last two are novel SCOD modifications potentially useful for specific applications. As ML applications grow, new formulations are likely to emerge to address specific setups.
Deriving the optimal strategy for given BDM problem proved to be the essential first step. Although the statistical model is often unknown in practice, understanding the structure of the optimal strategy crucial for designing efficient algorithms learn the selector from examples. This knowledge can narrow the search space or simplify the problem using divide-and-conquee approaches.
For instance, consider constructing selector strategy for the SCOD problem. Whether using the
original cost-based formulation (12) or the two novel variants (4) and (16), takes the form (15), the optimal strategy c* relies uncertainty score s(x) r(x) + Bg(x). The strategy accepts input s(x) is below a threshold f, and with probability т s(x) = This analysis shows that the core problem reduces to approximating the two components: the conditional risk
r(x)
Σpt Epv ()((),(())
DEy
5

---

and the OOD/ID likelihood ratio g(x)) (z))/pp (r.. provides methods to approximate g (e.g. [TT 14
Extensive literature on OOD detection and there are 22
6
15
TO
20
methods to construct good proxies for r (e.g. [3 12 4 R
9
Once and g are known, constructing the selector strategy involves determining the scalars 0, T, and 3. These parameters can be tuned using held-out data, which is much easier than solving the original problem. Moreover, for continuous distributions, the event s(x) has zero probability, making arbitrary. In the cost-based formulation, the multiplier 3 has an analytical solution, leaving only 0 to be determined.
This example shows that deriving an optimal strategy for BDM problems allows us to use existing methods from OOD detection and selective classification to approximate various SCOD problem formulations. Conversely, skipping the optimal strategy derivation and using heuristic rules, such as the SIRC strategy from the original SCOD paper [24]. can lead to sub-optimal performance [16]
3
Main result
In this section, we formulate a generic BDM problem, characterize its optimal solutions, and provide straightforward instance of the optimal strategy.
For measurable set X' in a measure space, Lebesgue measurable functions P. X - 0, 0o)
with finite integrals on X', and fixed non-negative real values 8 and a, we define the following optimization problem:
( R(z)c(x)dr s.t. ( 2 and J (()))()) So. (17) c: (=- 00
min
Note that we do not pose any additional requirements on the functions, like continuity or differentia- bility, neither do we differentiate between discrete and continuous sets X; they can be arbitrary.
Theorem 1. For every optimal solution cº X + [0, 1] to Problem 17 there exist real numbers X, μ such that
/ (z) p(x) dr, x
(18)
x=
/ x>
(x) 0,
(19)
where
x² E X p(x)) > 0 R(x)
g(x)
(20)
p(z)
p(x)
R(x)
g(x)
X> E X p(z)
> 0 A
(21)
p(z)
p(z)
Informally, equation 188)
states that any optimal c" attains the value 1 on X except subset
of measure zero. Similarly, by equation (9).. ex attains the value on X², again up to a subset of R(x)
measure zero. The sets X' and X contain the points x for which p(a) + μ [(=) the threshold X, respectively, excluding any insignificant elements where p(x) 0.
p(a] is below and above
Based on these observations, the next lemma suggests a way to construct a single score function that determines an optimal decision strategy.
Lemma 1. An optimal solution ex X + [0, 1] to Problem can be found among the forms
s()) > X if s( X,
c1(x)=
(wx)
ifs(z) < X,
where
R(x) p(m)
g(x) p(x)
if > 0, otherwise,
(xx)
0

---

is a score function, X, are suitable real numbers, and T X + [0,1] is a function implicitly defined by the problem parameters.
Proof. Let c: X + [0, 1] be an optimal solution to Problem
Consider real numbers X,
yielded by Theorem ! and define
af > X, sfr X, s < X.
(x)) c(x)
To show that e* is optimal, decompose X' into the pairwise disjoint sets X (see 20 ). x (see (1 X' = { E X p(x) 0} and X² {a X s(x) 사}. Equalities (T8) and ensure that and e" are nearly identical on sets X and X² respectively, up to subsets of measure zero. By the definition of c', they are identical
X Consequently, the criterion and constraints attain the same is independent of X",
values for both c and c" on X² U X UX Finally, the first constraint of (17
and c* (x) S c(z) for all E X' ensures
J (a)
/ R(z)((x), x
fx (o)) & S q()))().
In conclusion, c² is an optimal solution.
Tool solve the BDM problems Lemma iis key tool for simplifying the BDM problem 17
p(z)- Once these ratios are known, determining the score involves finding the multiplier With the score s, the optimal strategy c* depends on finding the decision threshold À and the function T(x). However, in the cases where X' is continuous space, the boundary set {ar E X' | s(x) = }} typically has measure zero, except in some pathological instances. Consequently, 5 (x) can be chosen arbitrarily and does not play significant role. Thus, in continuous spaces, one only needs to find the scalars μ and X, which can be tuned using held-out data, making the process much simpler than solving the original problem from scratch.
shows that the main challenge is approximating the ratios R(w))
p(zn) and ((w)
The problem feasibility In the special case where only one constraint is given, i.e., when either p(x:) g(x) 0, checking feasibility is straightforward. In the general case, determine the feasibility of Problem (17), we can formulate the task as:
/ (())((x)dr s.t. / p(z)c(z)dz 2 e: X (0.0
min
(22)
We obtaín a similar problem but with only one constraint. Problem is feasible if and only Problem 22 attains value less than equal to
Proof technique Problem 17 represents an instance of infinite linear programming, grounded in established theory [17]. Especially, when X' is a finite set, it reduces to a standard linear program. allowing the use of Lagrange duality derive optimality conditions, as characterized in Theorem [ However, when A' is arbitrary and the functions R. P. q are essentially unrestricted, this approach becomes substantially more complex. In such cases, more general duality theorem would be required, and even then, deducing the desired results would involve handling significantly more intricate optimality conditions. Given these challenges and drawing inspiration from techniques in related works (e.g. [9] 16 [8] and other studies on the Neyman-Pearson problem), we instead pursue a direct proof, provided in Appendix A By introducing forbidden point configurations, this proof shows that each optimal solution is determined by line separating the images of the sets X and
X²> in the plane, mapped by the function x(x) = p(=))
R(x) g(x)
Extensions It remains open problem whether our results can be generalized to the extended formulation
es X x- ( R(z)c(x), s.t. [ p(s) 2 and J q1())c()),d do S oi i 1,
min
(23)
where is a finite index set, the functions qi are Lebesgue measurable with finite integrals on X, and are non-negative bounds. A key question is whether there is a scoring function with 1 + [7] parameters (instead of 2) for this case. It is important to note that generalizing the current proof would involve addressing significantly greater combinatorial complexity in the point configurations.
7

---

General tasks
In this section, we introduce several special cases of problem 17 follow from Theorem I as we will show. These cases encompass all the examples in Section 2 Thus, all the mentioned BDM problems can solved their general form using the single framework proposed in this paper.
whose forms of solutions directly
To simplify notation, we represent the Lebesgue measurable functions in (17 p.: X [0, (0) i {0, 1.2). Furthermore, for Lebesgue measurable X' - [0, 1]. we define the functionals:
/ pr(x) dx) E {0,
F((c)
The generic BDM problem
17
then requires solving for given non-negative scalars å and p:
min
Fo(c)
s.t.
Fi 8 and F2(c) s
(24)
0: X [0.1)
Note that Fo here does not depend on the classier h, which is consistent with the assumption that h is the Bayes predictor.
Problem 1: Given 8 > 0, the task is to solve:
min Fo(c)
s.t.
(i(c) 2 8.
(25)
(011
A special case is the Neyman-Pearson task
We derive this formulation from (24) by setting p2(2) 0 for all X. Lemma implies that if the problem is feasible, it has an optimal solution c* such that
(= X
P1 x
(x)
T(x)
if x
P1 X
P)
X.
Pi(e)
Note that here, Lemma does not fully replicate the Neyman- Pearson strategy, which 7 is constant.
Problem 2: Given 8 > 0, the task is to solve:
Fo(c)
min X-10 Fi(c)
s.t. (i(e) 2
(26)
Special cases are the Bounded-Abstention model
S and the original SCOD problem (12)
This formulation equivalently be transformed to 25 by showing that there is optimal solution
c" such that Fi(c*) = Indeed, some optimal c X + [0, 20) fulfills Fi (c() > then we can define c* = (ij c, and holds that Fi Fi(c) and
Fo(e*)
Fi(e) Fo(c) Folc)
Fi(ct)
Fi(c)
Hence, such a e* is preserved in the set of optimal solutions the problem
Fo(c)
min [0,1]
s.t.
Fi(e) 8.
Problem 3: Given 8 > the task is solve:
Fo(c)
(i())
s.t.
8. Fi(c)
(27)
X-1
A special case is the Gounded-Improoeene model [I]

---

Let c² be an optimal solution to (27) Define problem:
Fo(c)
min [010 (i(c)
s.t. Fi(e) 2 Fi(c").
Clearly, ot is feasible for the new problem, which is of the form 26 Moreover, any optimal solution to this problem is also optimal to (7 because it attains the maximum Fi(c") and satisfies the constraint:
Fo(c)
S Fo(c*) 88.
Fi(e) F((ct)
Problem 4: Given 5 > 0, a >> O, the task is to solve:
(o(c)
min c: X- X- 0,11 (i
S.t.
2 and Fa(c) a
(28)
A special case is the SCOD problem formulation with constraints on FPR and TPR
14
In this case, transform the problem to (24) in the same way we did it for the formulation 26)
Problem 5: Given > 0, a > O, the task to solve:
Fo(c)
(2(c)
min
s.t.
Fi(e) 2 8
and
0a.
(29)
[0.1] Fi
Fi
A special case is the SCOD problem formulation with the constraints on TPR and Precision (16 because the second constraint in (T6) can be rewritten
spr(c) tpr(c) S (T 1) (prec -),,
which matches the form
F2(c)
Fi
Again, the problem transforms to
24
using the same approach as in the case of the formulation (26).
5 Conclusion
In this paper, we presented comprehensive framework for solving binary decision Docision-making (BDM) problems, which define optimal decision strategies through constrained optimization involving Lebesgue measurable functions. We characterize all optimal strategies for generic BDM problem and derive specific class of optimal strategies based on comparing single score with a decision threshold. Our framework covers variety of BDM problems, from well-known instances like the Neyman-Pearson problem to recent developments such as the SCOD problem. We demonstrated the versatility and robustness of our framework by deriving optimal solutions for all the BDM problems discussed in paper. This work provides a foundational approach that can be adapted to future needs in machine learning and statistical decision making, ensuring more effective and theoretically grounded solutions.
6 Acknowledgement
This research was supported by the CTU institutional support (future fund).
References
[1] Constantin Carathéodory. Über den variabilitätsbereicch der koeffizienten von potenzreihen, die gegebene werte nicht annehmen. Mathematische Annalen, 64:95-115, 1907.
[2] Guangyao Chen, Peixi Peng. Xiangqian Wang, and Yonghong Tian. Adversarial reciprocal points learning for open set recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(1) 44(11):806 80:65 8081, 2022.

---

[3] C. K. Chow. On optimum recognition error and reject tradeoff. IEEE Trunsactions on Information Theory. 16(1):11-46, 1970.
[4] C. Corbiere. N. Thome, A. Bar- Hen, M. Cord, and P. Perez. Addressing failure prediction by learning model confidence. In Advances in Neural Information Processing Systems, volume 32, pages 2902-2913, 2019.
[5] Terrance DeVries and Graham W Taylor. Learning confidence for outoof-distribution detection in neural networks. arXiv preprint arXiv:1802.00 8802044655 2018.
[6] Akshay Raj Dhamija, Manuel Günther, and Terrance Boult. Reducing network agnostophobia. In S. Bengio. H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[7] Vojtech Franc, Jakub Paplham, and Daniel Prusa. SCOD: From heuristics to theory. In Proceedings of European Conference on Computer Vision, 2024.
[8] Vojtech Franc and Daniel Prusa. On discriminative learning of prediction uncertainty, In Proc. of Machine Learning Research International Conference on Machine Learning, June 2019.
Vojtcch Franc, Daniel Prusa, and Vaclav Voracek. Optimal strategies for reject option classifiers. Journal of Machine Learning Research, 24(11):1-45 2023.
[10] Federica Granese, Marco Romanelli, Daniele Gorla, Catuscia Palamidessi, and Pablo Piantanida. Doctor: A simple method for detecting misclassification errors. In M. Ranzato, Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 5669-5681. Curran Associates, Inc., 2021.
[11] Dan Hendrycks and Kevin Gimpel. A baseline for detecting misclassified and out-of-distribution examples in neural networks. In Proceedings of International Conference on Learning Representations, 2017.
[12] H. Jiang, B. Kim, M. Y. Guan, and M. Gupta. To trust or not to trust classifier. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, page 5546-5557, 2018.
[13] B. Lakshminarayanan, A. Pritzel, and C. Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems, volume 30, pages 6402- 6413, 2017.
[14] Shiyu Liang, Yixuan Li, and R. Srikant, Enhancing the reliability of nut-of-distributioo image detection in neural networks. In International Conference on Learning Representations, 2018.
[15] Andrey Malinin and Mark Gales. Predictive uncertainty estimation via prior networks. In S. Bengio. H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[16] Harikrishna Narasimhan, Aditya Krishna Menon, Wittawat Jitkrittum, and Sanjiv Kumar. Plugin estimator of selective classification with out-o--distinuution detection. In ICI.R, 2024.
[17] P. Nash and Edward James Anderson. Linear programming in infinite-dimensione spaces: theory and applications. Wiley, 1987.
[18] Jerzy Neyman and Egon Pearson. On the use and interpretation of certain test criteria for purpose of statistical inference. Hiometrica, pages 175-240, 1928.
[19] Tadeusz Pietraszek. Optimizing abstaining classifiers using ROC analysis. In Proceedings of the 22nd International Conference on Machine Learning, page 665-672, 2005.
[20] Yue Song, Nicu Sebe, and Wei Wang. Rankfeat: Rank-1 feature removal for out-of-distribution detection. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 17885-17898. Curran Associates, Inc., 2022.
[21] Yiyou Sun, Chuan Guo, and Yixuan Li. React: Qut-of-distributtio detection with rectified activations. In M. Ranzato, A. Beygelzimer. Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 144-157. Curran Associates, Inc., 2021.
[22] Yiyou Sun, Yifei Ming. Xiaojin Zhu, and Yixuan Li. Out-of-distributin detection with deep nearest neighbors. In Kamalika Chaudhuri, Stefanie Jegelka. Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 20827-20840. PMLR, Jul 2022.
10

---

[23] Haoqi Wang, Zhizhong Li, Litong Feng, and Wayne Zhang. Vim: Out-of-distribution with virtual-logit matching. In 2022 IELE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pages 491 1911, 2022.
[24] Guoxuan Xia and Mhristos-Savear Bouganis. Augmenting softmax information for selective classification with -fito--distrbuttion data. Proceedings of the Asian Conference on Computer Vision (ACCV), pages 1915-2012, December 2022.

---

A Appendix (proof of the main theorem)
For metric vector space V and its subset S V, we write conv(A), int(A) and span(A) to denote the convex hull, interior, and span of A, respectively.
Lemma 2. Let A be a subset of R² with dim span(A) = 2. Given a point x located in the interior of the convex hull of A, there exists a convex polygon P such that æ lies in the interior of P. Moreover, all vertices of the polygon P are elements of the set A.
Proof. Given that x E int(conv(A)), there triangle T C conv(A) such that a E int According to Carathéodory's ss theorem [ each vertex of T lies in some simplex whose vertices are in the set A. Let these simplices be denoted as S1, S2, and S3. Defining P = conv(Si U U Sa) forms convex polygon P with vertices in A, and is in the interior of P.
Proof of Theorem ! Let X {x E X p(x) 0}. For all x X, we define g(z)
2(z) and
piz)
r(x) R(ar)
p(x] We will associate elements of X' with points in a plane by introducing the mapping
x + R such that x(x) f((=),(()))
X
The open b-ball of T (2) in IR2 is denoted as Bg (z).
For a measurable S RR2 define
p(A) = Sx((1)) p(x)de,
(30)
(2)
c(A) { p(A) (o--(ca) p(x))(x)dd p(o))))))
p() otherwise.
(31)
0
Problem 17 depends only on the subset
x+ fo E & Vz 0: p(B.((()) > 00 X.
To see this, let us define V1 = fo E X p(x) = =0 and Y22 = f-x E X Ff > 0: :::((p(()) = -).
Then have
Jayxr p(z) dz /
yy, p(z)dx + / p(x)dr =0,
(32)
since, for each open balll (2(x), there exists a circle Q(x) C (xx) that contains x and has rational radius and center coordinates. Thus, Y2 be covered by countably many such circles which the integral of p is zero. As a result, (32) implies that the elements of x do not affect the left-hand side of the first constraint and do not negatively impact the objective function the second constraint.
More precisely, for any feasible function c: X' + [0, 1]. if
d(x) {
{ c(x) E otherwise,
(33)
then it holds Jxx (x))d(2)dz & Sxx R(z)c(z)dd, (x Px)(()(())dz, and Sx (x)) & fxx (())c(z)dz.
For the next considerations, we further distinguish three significant subsets of X with respect to fixed optimal solution
1].
Xg = E x 00 =}
X1 f x [3>>0: =
N₂ = {o E x [=>::<<c <1]
Note that
No UUXUUX x+
* cB((((F)) 0 40 é Se: (Be (B:(x)) (x)) = 0, and
12

---

(= = + 0A e Se: c = 1.
To confirm the existence of suitable À and μa, stated by the theorem for c², is sufficient to demonstrate that the sets
Ag {x(x) x E No}
(34)
A {x(2)
x E X1}
(35)
A {x(2)
x E A22
(36)
are "almost" linearly separable. This necessitates finding a line I. C R² that includes A2 and linearly separates Ao L and A1 \ L. The existence of such an L is ensured if
dim span ((conv n conv
A2) <.
(37)
The proof continues by listing some general configurations of points from An. A1, A2 that contra- dict the optimality of c² These forbidden configurations will be used to confirm the validity of condition (37).
But we firstly establish estimates on Sx (>-1(B.(w)) ((x)c* (x) and fx (x-1(B.())) M(x)c* (x)dr, for each y E X' and e > 0.
For given y X, let scyy) (a. b)
q(v) R(
p(u) plv)
Since, for all E x (B. it holds
((x)
a
5 p(x)
S a + 2
(38)
2
R(x)
< + 2
(39)
p(x)
we easily obtain
(a- ((Belw)) < /
((x)c S (a+ (a+)))(BB D(Bel)))) (B.(()) (40)
(x=((((())
and
(1-5) - (B)
(x))c S ( p(B,(w)) (41)
Claim 1.1. Lei 3T, 82 X+,, a(x1) g(ma) D2 E X..
and R(a
R(wa) p(r)) plan)
Ifc" is optimal, then in E No or
p(z1) p(a))'
Proof of the claim. We proceed by contradiction. Assume that E X U U22 and 22 E Xy U This implies the existence of an E > such that c* (B((t))) > 0 and e* (Be(xz) <. Without loss of generality, choose e sufficiently small so that
g(11)
(x22)
E < p(x1)
(42)
p(x2)
and
R(x1)
R(x2)
(43)
p(x1)
p(zz)
which further implies By (z ) Bx = 0.
q(u.) For i E (1,2), denote B: = By (x;),, p(a.) and 6;
R(x.)
p(x,)
Define function d' X + [0, 1] as follows:
c² (x) v p( B,)
(B, e² (x)
if E B
d(x)
('(x)
pl B1)
c² (x))
if Bg. otherwise.
p(Bb) - (Ba)
cx(x)
13

---

Here, the parameter // is defined as:
min c (Bi),
P(B2) p(Bi)
(1 cBaaa) 20,
which ensures 0 < y 11 well 0
- I 1. hence e' is defined conrectly.
p B1
c(B.)
By comparing c* and c', will show that is not optimal.
Observe that
J/ plx)d /
p(Bi) (B(B)) +v pBB1)
(p(B2) - -B2(B)) = 0,
(B1)
p(B2) - c(22)
Moreover,
Je ((x) / (()))" ((Bi)
(BB) (BB) (x)d
p(Bi)
v p( B2) - -e2 (B2)
((x)(1 - (c)()dd
10
p(B1) (a1 E
BBB))
02 + E)
V (Bi)
2
(Bii) + p2B2) - e* (B2)
(o(Ba)-c - (B2))
12
=p(Bi) +
0.
Analogously, we can derive
J R(a)d(r)dr
/ R(z)c s vp((B) - by +e)
43
0.
The relationships above contradict the optimality of c*
Claim 1.2. Let 21, 22, be distinct elements of X+t and let on 02; 3 be non-negative real numbers such that on + Org = 1, # O, and (x((x)) = o1 x(x)))) + a22((2)) If is optimal, holds:
1 < 1, then either 23 E Ng or {21, x2) 0 1 * 0,
8 > 1, then either I3 E Xi or {21, x2 } n X + 0.
Proof of the claim. We will give proof for 3 < 1 and note that the steps for B > 1 are analogous.
i (1,2,3), denote x(x;) (a;, b.). Find an such that
< (1 f))33
(44)
E << (1 - 3)b3, and (x)),, (222)). (xaa are pairwise disjoint. By contradiction, assume that (BBe( < 1, e" (BB((22)) 1, and c² CB (xa)) 0.
(45)
To simplify the notation, for E 2,, let B, = B, = c (B.), and p. = p(B.). Note that, according to the definition of x it holds Pl, P2. 0.
Define selective function
X [0, 1] as follows:
c² (x) + 201Ps
(x))
if E Br, if E Ba, if E Ba, otherwise.
Cs IP1
(x) + yeapi
(x))
d(x)
(x
v c (x)
(x)
14

---

Taking 0 = oo for any 2 > 0, the value of y/ is given by:
P1 (1 c1);
P2 (1 02)
min
C3
01
a2p3
is easy to see that > O, and 0 <
parps L S 1.
(1-c)pr
(1-0a)p3
Now, observe that
f p(z) (()))
(x-1 - (1-G) p(z)(11cc (x))
VO1p3
+ (B2)
V02p3
p(x)(1 c² (x))ddr
vps p(x))c (x)
62)
xx (Ba)
vaips + V0223 1/3 = vps(a1 + 1) =
Next, derive
J (()) / (())c x ( -1- (1-1)pi ((x) - c² (x)))
vonps
(Bz) - (2-c2)p2 g(x)(1 c'(x))dx (x-1(B)) Up3 g(x))c (x)
V02P3
40
@2 + 8)
8)
vanp3
(1 2 + vQ2p3
2)
up3
03 2
(a + ax)) + E
1Ps [1101 + +0202
az + 2
2)
ups (303- 03 +
Quite similarly,
I R(z)d(x))r - | R(x)c" (x)dx S vp3 (9bs - 63 +
0.
Claim 1.3. Let 21...., 2n E X+ and x E X+, and let P be a convex polygon with vertices ((1),... x(ya), with x(x) as its inner point. The function c" not optimal one of the following cases holds:
1. All zi's 's are from No and x E Xi.
2. All z 's are from Xi and a E No.
Proof of the claim. For the first case, we identify an edge of the polygon that is first intersected by the half-line H starting from the origin (0, 0) and passing through the point x(x) (see Figure lap.
This edge has vertices x(y1) and x(y2) for some 31, 3/2 E {z1...., 2. The points x(x), x(11). and x(12) are non-collinear and satisfy (x(()) ai x(1) + x2 for some non-negative real
numbers 01, 02 and B, where an + 02 = 1 and B < 1. According to Claim 1.2 these points contradict the optimality of c*.
Similarly, for the second case, we identify an edge of P that is the last one to be intersected by the half- line H (see Figure lb]. Let x(v1) and x(y2) be vertices of this edge for some y1, {=1,-.., Zn The points x(x), x(y)) ) and x(y2) satisfy 3x(x) = On x(y)) + 0:2 (222(2) for some non-negative real numbers 01, 02 and 18, where 01 02 and 3 > 1. Again, Claim 1.2 contradicts the optimality of c²
Claim 1.4. 1f Xn and 13, E X1, and the line segments with endpoints x(x1), x(x2), and x(x3), x(x4) intersect a point lying in the interior of both segments, then the function e not optimal.
15

---

91
1/2
1/2
91
9
(a) Case 1
(b) Case 2
Figure I: The infeasible configuration described by Claim 1.3 their pre-images from x++.
For simplicity, points are denoted by
91
T1
22
B
B
T2
1/2
y2 0
9
(a) Case
(b) Case
Figure 2: The infeasible configuration described by Claim 1.4
Proof of the claim.
We consider two possible situations depicted in Figure
First, we examine the scenario where one of the points 1) x(x2) ) is located lower-left relative to the other one, specifically, we assume g(x)) S g(x2) and r(x,) r(x2). as illustrated in Figure According to Claim 1.1 the points x(y1), ). x(y2) cannot be situated within the shaded rectangular area. Since the line segments intersect, one the points x(y1). x(U2) must positioned upper-left from x(x2), while the other lies lower-right from x(x2) (these regions are labeled A and B,
respectively, Figure lap. However, such an arrangement contradicts Claim I.2
One of the points x(y1), x(y2) must lie within the half-plane bounded by the line passing through x(x1). xxx2), and containing the origin (0, 0). Let's assume this point is y2- As per Claim I.I x(12) cannot reside in the shaded area. Within this considered half-po paln-p there are three remaining triangular regions denoted A, B, and C. Nevertheless, Claim 1.2 prohibits x(12) from lying within region B (by applying the claim to the triple 31, 22, and y2). region C' (consider the triple y1, y/2 and 22), as well region A (consider the triple y1, and r.).
Secondly, we consider the configuration depicted in Figure 2b
Claim 1.5. 21, 22 E X2 and x(21), xx22) are distinct points, then the slope of the line passing through x(21) and xx(22) is not positive. Moreover, the open half-plane determined by L and the origin (0, 0) does not contain any point from A U Ag, and similarly, the opposite open half-plane does not contain any point from Ao U Az-
Proof of the claim. the slope L is positive, as shown in Figure 3a then the points x(21) and x(22) conform to Claim 1.I implying that c* is not optimal.
slope of not positive, referring to Figure 3b we deduce that the open half-plane Ho does not contain any point x(x) from Ao U A2. By Claim 1.1 such point P cannot be in the shaded
area. It neither can in areas A, B, C' because each case, the points v, 22, and 21, or 21, 22.
and æ, 21, and 22 would conform to Claim
16

---

L
A
22
B
22
Ho
C
9
(a) Case 1
(b) Case 2
Figure The infeasible configuration described by Claim 1.5
1/2
12
E
:/2
//1
21
B
F
L
(a) Case
(b) Case
Figure The infeasible configuration described by Claim 1.6
Similarly, it can be argued that point from A U A2 cannot lie in the opposite open half-plane.
Claim 1.6. Let Lt, I2 E X, V1, E No. 2 2 If x(x)), x(x2). x(y1), and x(y2) are distinct points lying line L in such way that x(y) is between x(x1) and x(x2), and x(x2) is between x(y)) and x(y2), then x(2) lies on L unless the function c* is not optimal.
Proof of the claim.
Firstly, observe that the configuration in Figure 4alis not admissible for an optimal c*, because x is located in the shaded area containing points to the left and down from x(x2) (Claim 1.1 applies here).
Hence, suffices to inspect the case with the opposite slope of depicted in Figure 4b
Note that,
without loss of generality, assume that the highest point L x(22). The when the highest point is either x(x,) or x(x22 is handled similarly. c* is optimal, then x(2) cannot lie in the two shaded areas (Claim 1.1) The remaining area is split into 6 different parts by L, denoted from A to F. If x(z) lies in any of these parts, then we can always select two elements from {21, 02, 31, y2 that together with conform Claim T.2 These selections are as follows:
A: 2, 21,
B:I1,
C: 2. 2,1
D: z, 22,
91,32.
F: z, 22.
37 by listing all the potential infeasible cases and showing that We are ready to confirm condition they contradict the optimality c
1. dim span(conv(An) (Ag) n conv(A)) 2. We distinguish three subcases.
Assume that, for some Xn. x(x:) is in the interior of conv (Ag) O conv(Ar). By
Lemma 2 there convex polygon P with vertices in x(X) such that the interior of P contains Apply Claim 1.3
17

---

Next, assumee that a belongs to 21 instead of Xg. Analogously, find a convex polygon P with vertices in xxX)), containing x in its interior. Apply Claim 1.3
Finally, if conv(A1)) By Carathéodory's s theorem, there exists simplex So line segment or triangle) with vertices in Ag such that x(x)) E in)) Similarly, there exists a simplex S₁ (a line segment or triangle) with vertices in Ai such that x(x) int(S It is not difficult see that the boundary line segments of So and Si intersect, meaning there are two intersecting line segments, one with endpoints Ag. and the other with endpoints in Aj. Hence, Claim 1.4 contradicts the optimality of c"
(oon)
= take an arbitrary & E int(conv (Ag) nn
2. dim span(A2) = 2. There exist Iı, #1, 23 E X2 such that x(x1), x(x2), x(x3)) are non- collinear. Such a configuration prohibited by Claim 1.3
3. dim span(conv(A) (Ao) n conv(Ai)) 1, dim span span(A2)
and dim span((conv(Ao))
conv(A,) U A2) = 2. There are 21, E No. 23, E X1, I5 E X2 conforming to Claim 1.6
4. dim span(conv (oooooo))))))oooooooooo n conv(Ai))
and dim span( conv(A)) U A2) = 2. There are 21, 22 E Ar such that x(2) and x(22) conform to Claim L.5 i.e., the line passing through x(21) and x(22) determines two opposite half-planes, Ho and H1. By Claim [.5] Ao S Ho and A1 S H1. This means that conv(Ag) n (Anv(Ai S L, which contradicts the assumption dim span((convAAo) conv(AA) U A2) = 2.
dim span(A2)
18

---

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 contribution summarized the abstract and explained the introductory section.
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
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The paper explains that tuning the parameters of the score function that charac- terizes optimal solutions must be approached individually for each problem. Additionally, it notes that extending the main result to incorporate more constraints remains an open problem.
Justification:
Guidelines:
The answer NA means that the paper has 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 on 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play 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
19

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The full proof of the main theorem is in the appendix, the assumptions are stated the main paper.
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 provide short proof sketch to 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
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken 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 be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to 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.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome 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 possible for other researchers to have some path to reproducing verifying the results.
20

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include any experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While encourage the release of code and data, 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 NeurlPS code and data submission guidelines (https for more details.
7 //nips. hwcp//blccggudeeeeeeeeeeeeeeeeee
The authors should provide instructions on 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 are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary 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
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, 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).
21

---

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 the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include any experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, 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 estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't I make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Our research conducted in the paper conforms with the NeurIPS Code of Ethics which have reviewed.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We present mathematical result which does not have any societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
22

---

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 does not utilize any data nor models.
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: [NA]
Justification:
The paper does not use any assets.
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.
23

---

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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. 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.


Reviews:
[{"review_id": "lPYRktuXQV", "reviewer": "Reviewer_ALNx", "summary": "The paper presents a framework for binary statistical decision-making (BDM), where decisions are made between two states based on statistical evidence. The authors introduce a constrained optimization problem formulation for BDM, involving integrals of Lebesgue measurable functions, and provide a detailed characterization of the optimal decision strategies. The paper encompasses a wide range of existing and newly proposed BDM problems as specific instances of the presented framework, demonstrating how to derive optimal strategies for these problems. This framework aims to simplify the process of solving both established and novel BDM problems, which are fundamental to many machine learning algorithms.", "questions": "Have the authors considered conducting empirical experiments to validate the proposed framework? Demonstrating the practical effectiveness of the optimal strategies in real-world BDM problems could significantly strengthen the paper's contributions.\nHandling Unknown Distributions:\n\nHow would the framework handle cases where the underlying data distributions are unknown or difficult to estimate? Are there potential extensions or modifications that could make the framework more robust to distributional uncertainty?\nComputational Efficiency:", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality:\nThe paper introduces a novel and general framework that unifies various binary decision-making problems under a single constrained optimization formulation. This generalization is a significant contribution, as it provides a robust mathematical tool that can be applied to a wide range of existing and newly proposed BDM problems.\nQuality:\n\nThe paper is rigorous in its theoretical treatment, providing detailed proofs and a clear characterization of the optimal strategies for BDM problems. The use of Lebesgue measurable functions and the generality of the framework allow it to cover both discrete and continuous instances without requiring differentiability of decision and loss functions.\n\nClarity:\nI like it a lot that the authors provided lots of examples in section 2. The paper is well-organized, with clear explanations of the problem formulations and the derivation of optimal strategies. The inclusion of examples from classical statistics and machine learning applications enhances the clarity and relevance of the work. The theoretical results are presented in a step-by-step manner, making the paper accessible to readers with a background in optimization and decision theory.\n\nSignificance:\nThe significance of the paper lies in its potential to impact a broad range of applications in machine learning and statistical decision-making. By providing a unified framework for BDM problems, the paper simplifies the process of deriving optimal strategies, which can be crucial for designing efficient algorithms in areas such as selective classification, out-of-distribution detection, and hypothesis testing.", "weaknesses": "Limited Empirical Validation:\nThe paper primarily focuses on the theoretical aspects of BDM and does not provide empirical validation of the proposed framework. While the theoretical results are strong, it would be beneficial to see experimental evaluations that demonstrate the practical effectiveness of the framework in real-world scenarios.\n\n\nComputational Complexity:\nThe proposed optimization problems involve integrals of Lebesgue measurable functions, which may be computationally expensive to solve, especially for high-dimensional data. The paper does not fully address the computational challenges associated with solving these problems, which could be a barrier to practical implementation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "pDSO6xcK74", "reviewer": "Reviewer_aUyF", "summary": "This paper characterizes optimal solutions to a class of binary statistical decision-making (BDM) problems. The problem recovers as special cases the likelihood-ratio problem and variants of classification with rejection problems. The optimal solutions characterized in this paper coincide with the known solutions to the aforementioned problems, and thanks to this paper, new solutions are found to some new variants of the BDM problem.", "questions": "- At the beginning of the paper, it is said that the BDM problem involves Lebesgue measurable functions. It is not clear to me whether all the literature is specifically focused on basically density functions. Can the authors confirm this and add a more in-depth discussion, please?\n- Why is there a focus on \"robust\" keyword in this work? Especially because we assume data-generating distributions like $p_I$ are known, there is no robustness. I am a little confused. Some of the work on the \"classification with rejection\" literature has motivation for robustness, but I don't see how this is generalized for BDMs in general. \n- Are defining the distributions as $p: \\mathcal{X} \\mapsto \\mathbb{R}_+$ the formal way? Is this how the literature defines them?\n- Line 77, \"only when prediction uncertainty is minimal\": I don't understand this sentence. Also, there are uses of $p(x, y)$ and $p(y \\mid x)$. Please formally define them.\n- Can you discuss the measurability of the functions, such as terms in (7)?\n- Equation (12): Aren't there work in the literature that also constrains $\\phi(c)$?\n- Line 232 says \"the combinatorial complexity of the proof\" will be increased if we have more constraints. How do the authors know the proof will still go through? If the authors are convinced, I would at least propose a high-level proof sketch in the appendix.", "limitations": "The limitations are addressed to some extent, and the checklist is complete. However, further focus on the computational issues about the proposed model should be highlighted.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I like the paper. It is written very cleanly. The motivation is clear. I also enjoy how the paper starts with a slow pace, gives a \"tutorial\" on BDMs, and then uses this to connect with their results -- since the Neyman-Pearson lemma is very old and there exist many variants of the notation, this way of presentation was particularly useful. I like Theorem 1 and Lemma 1, and the proofs use smart techniques (e.g., even Lemma 1 looks simple, but the construction of c* from an optimal c is very clear in my view).", "weaknesses": "In my view, the following points are the weaknesses of the paper and I kindly invite the authors to address them:\n- In general, problem (17) is an infinite-dimensional linear program. There is a huge literature, many books, etc., on this. These resources devote significant time to characterizing optimal solutions and the existence of feasibility. Could the authors add more discussion on why the existing literature on infinite linear programs (ILPs) cannot be used here? One can look at \"Linear programming in infinite-dimensional spaces: theory and applications\" by Nash and Anderson, or related papers. \n- Section 2.5: It is said optimal solutions to the given problem are unknown. But this problem variant is also defined in this paper. Can the authors also motivate \"it is not known, and can *not* be derived by the existing machinery\"? Currently, the flow is ad-hoc in the sense that the authors define a new problem, discuss there is no known solution, and derive one that resembles the solutions to similar problems from the earlier subsections. \n- Section 2.5: In line 145, it is said SCOD is using different units in the objective function. However, there are many multi-objective problems with different units. For example, portfolio optimization involves balancing between returns and covariances, which have different units. This problem needs further motivation in my view.\n- Please make the notation consistent: (14) is using $R^\\mathrm{S}(h,c)$ but earlier it was $R^\\mathrm{S}(c)$. I think the former is better, but please be consistent across the paper. Furthermore, Lemma 1 has $\\rho$ and $\\pi$, which I believe should be $q$ and $p$.\n- After Theorem 1, before immediately presenting Lemma 1, can the authors discuss Theorem 1? I like the idea of having a single function to use in the optimal solution characterization via piece-wise functions (as this resembles existing results), however, equations (20) and (21) do not give much intuition currently. \n- Some of the computational challenges are presented as it is easy. For example line 215: \"Once these ratios are known, determining the score $s$ involves finding the multiplier $\\mu$\". Can the authors discuss how to find $\\mu$? Similarly \"one **only** needs to find the scalars $\\mu$ and $\\lambda$\". Same for line 224, \"we obtain a similar problem but with only one constraint.\": how do you solve this problem, there is no mention. \n- The paper would greatly benefit from some numerical experiments. Currently, it is highly theoretical and there are strong assumptions like the knowledge of underlying distributions. There are mentions of cross-validation (or estimation from held-out data), which is more of a computational task than statistical in my view, and I would like to see some mini-experiments on this. \n\nSome minor typos and issues:\n- Line 70: \"is\" generated from the in-distribution\n- Line 91: \"to distinguishes\" has a typo\n- Line 107, \"reflects the probability of accepting an input sample\": I don't think this is about an input sample. Isn't $\\phi$ returning the measure of the set that we \"reject\"? The input of $\\phi$ is $c$, not $x$. \n- Equation (10): Missing comma \",\"\n- Some references to (15) should be (14) instead. Examples are line 149, and 172. \n- Line 157: \"solvers\" should be \"solves\"? That said \"the strategy\" should be \"a strategy\" if there can be alternative optima.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weaknesses**\n\nR: *In general, problem (17) is an infinite-dimensional linear program (ILP). There is a huge literature on this.* \n\nA: We agree that BDM is an instance of ILP, enabling the use of tools like duality and KKT conditions. However, it is unclear if these tools can provide the same characterization of the optimal decision strategy for BDM or simplify our proof. We do not see an immediate, straightforward application. Furthermore, existing proofs related to the Neyman-Pearson problem, to our knowledge, do not consider ILP. We will include a discussion on this topic.\n\nR: *Section 2.5: It is said optimal solutions to the given problem are unknown. But this problem variant is also defined in this paper. Can the authors also motivate \"it is not known, and can not be derived by the existing machinery\"?*\n\nA: Our goal is to demonstrate the generic nature of the proposed framework. Therefore, we introduced novel modifications to the existing SCOD problem (12). These modifications, which include additional constraints and an optimized function in the denominator when defining precision, are more complex but can be readily resolved. We will clarify this in the text.\n\nR: *Section 2.5: It is said SCOD is using different units in the objective function. However, there are many multi-objective problems with different units. This problem needs further motivation.*\n\nA: We do not intend to criticize multi-objective problems. Instead, we aim to demonstrate that alternative formulations, which may be more appropriate in certain cases, exist and can be readily solved.\n\nR: *Please make the notation consistent in (14), Lemma 1.*\n\nA: Thanks for pointing this. We will make the notation consistent. There is a typo, these functions should be $p(x)$ and $q(x)$. \n\nR: *Can the authors discuss Theorem 1?*\n\nA: We will add a discussion on equations (18)-(21). The sets ${\\cal X}^{<}$, ${\\cal X}^{>}$ are subsets of ${\\cal X}$ separated by the score function; they ignore insignificant $x\\in {\\cal X}$ for which $p(x)=0$. \n\nR: *Some of the computational challenges are presented as it is easy. Can the authors discuss how to find $\\mu$ and $\\lambda$\"?*\n\nA: The method for finding unknown multipliers varies by problem. In some cases, such as the optimal strategy for the SCOD problem (13), the multiplier can be calculated from the problem's input parameters. If no explicit formula exists, the standard approach is to tune the parameters using calibration data. Notably, tuning one or two parameters, while challenging, is significantly easier than tuning an unknown function, which would be required without the optimal strategy characterization.\n\n**Questions**\n\nR: *At the beginning of the paper, it is said that the BDM problem involves Lebesgue measurable functions. It is not clear to me whether all the literature is specifically focused on basically density functions. Can the authors confirm this and add a more in-depth discussion, please?*\n\nA: At least in all the example problems from Sec 2, the functions involved are either probability density functions (p.d.f.s) or p.d.f.s multiplied by loss functions, all of which are Lebesgue measurable.\n\nR: *Why is there a focus on \"robust\" keyword?*\n\nA: We use the term \"robust\" to indicate that the tools proposed in the paper i) require very weak assumptions for application and ii) are applicable to a broad range of BDM problems.\n\nR: *Are defining the distributions as $p\\colon{\\cal X}\\rightarrow\\mathbb{R}_+$ the formal way? Is this how the literature defines them?*\n\nA: In defining the functions used in the problem formulations, we specify only their domains and co-domains, such as $p\\colon{\\cal X}\\rightarrow\\mathbb{R}_+$. Probability density functions (p.d.f.s) must also be Lebesgue integrable with an integral equal to one. We assume this well-known standard definition, therefore, we have not included it.\n\nR: *Line 77, \"only when prediction uncertainty is minimal\": I don't understand this sentence. Also, there are uses of $p(x,y)$ and $p(y|y)$. Please formally define them.*\n\nA: We agree that the sentence is confusing. A clearer explanation would be: \"We will explore six different BDM instances to develop a selector $c$ that admits an input sample $x$ for classification with $h$ only when the prediction uncertainty is below an acceptable threshold.\" \n\nWe use $p(x,y)$ to denote joint probability distribution of random variables $X$ and $Y$. In our setup, these variables be either discrete or continuous; however, in the example problems, $Y$ is always discrete. We use $p(y \\mid x)$ to represent the conditional probability of a discrete random variable $Y$ given another random variable $X$. \n\nR: *Can you discuss the measurability of the functions, such as terms in (7)?*\n \nA: Yes, this is a valid point. We should state that functions such as $c$ and $\\ell$ are assumed to be measurable.\n\nR: *Equation (12): Aren't there work in the literature that also constrains $\\phi(c)$?*\n\nA: The constraint in (12) imposes a lower bound on the true positive rate, ${\\rm tpr}(c)$, which is defined identically to the coverage $\\phi(c)$ . In the context of SCOD, this is referred to as the \"true positive rate,\" whereas in selective classification, it is called \"coverage.\"\n\nR: *Line 232 says \"the combinatorial complexity of the proof\" will be increased if we have more constraints. How do the authors know the proof will still go through? If the authors are convinced, I would at least propose a high-level proof sketch in the appendix.*\n\nA: To be cautious, we will present the extension as a hypothesis for future exploration. The Appendix will include a remark suggesting potential avenues for generalization.\n\nR: *The limitations are addressed to some extent, and the checklist is complete. However, further focus on the computational issues about the proposed model should be highlighted.*\n\nA: We will extend the discussion by explaining that tuning the multipliers needs be addressed for each problem separately.", "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": "upiHJCi8Js", "reviewer": "Reviewer_bcuc", "summary": "This paper studies a class of optimality criteria for what it calls \"binary decision making\" which is basically binary classification but with a randomized classifier. It characterizes the solutions for thes criteria, recovering some known results and also establishing new ones. The paper is entirely theoretical.", "questions": "In the previous box, a ** or *** next to a comment means I would be interested in hearing the authors' response, with *** indicating higher priority. Responses to other comments are also welcome.", "limitations": "There are no anticipated negative societal impacts.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main strength of the paper is that it provides a very general treatment of optimality criteria for binary classification , where the criteria include an objective to be minimized, and also one or two constraints to be satisfied. It subsumes prior work on statistical optimality in \"selective classification.\" The proof appears to be original, nontrivial, and, for the most part, clearly written.", "weaknesses": "The main weakness concerns the impact. Of course impact on practitioners is desired, but even the theoretical impact was unclear to me at times. I think this stems from how the paper is motivated. The motivation uses the notion of \"selective classification,\" where you have a classifier and a selection function, and your optimality criterion concerns both of them. But the actual results in the paper only discuss the selection function, so there is a disconnect. So if the authors could clarify that issue, and also make a sincere effort to explain realistic settings where the novel criteria are potentially useful, that would go a long way toward resolving the main weakness.\n\nThe other notable weakness is that the motivation involves a classifier h and a selection function c, but then h goes away at some point.\n\nBelow I include a section by section list of comments that I made while reading the paper.\n\nIntroduction: Writing could be improved. For example, the Neyman-Pearson lemma is introduced in both the first and second paragraphs. Selective classification is not so well known, and it would be helpful to define it here, and explain why it is an important class of criteria. Most importantly, BDM is never precisely defined.\n\n*** What is the impact of the contribution? Does it help us train selective classifiers? Some optimal solutions seem to require knowledge of the underlying distributions. In line 165 it is stated that the results are “potentially useful for specific applications”, but no concrete examples are given. Thus the impact could be more convincingly argued. This is probably the main weakness.\n\nThe sentence “Therefore, learning a detector from examples involves effectively approximating the likelihood ratio and then tuning the decision threshold” is seemingly false, as you just need the decision boundary\n\nReference [17]: “Person” should be “Pearson”\n\n** Sec 2: What is the learning problem? Do we just get data from the “in distribution”?\n\nThe statement “We assume the classifier h was designed to minimize the prediction loss … ” is unclear – usually one chooses h to minimize an expected loss. But it is not clear what that expectation (joint distribution) is at this point in the presentation.\n\nEqn. (7): The notation p(x,y), to me, assumes x and y are jointly discrete. Better to just use E for expectation and eliminate the integral and sum.\n\nEqn. (10): missing “)”\n\n*** The review of BDM problems discussed the optimal c, but the optimal h is not mentioned.\n\nSelective risk: notation varies, e.g., R^S vs R_S\n\n** The final example assumes that pi is known or can be estimated. Well, it will not be known in practice, and if estimated, the estimate won’t equal the true pi. Thus, it would be important to understand how having an estimate of pi impacts the usefulness of this case.\n\nThere are several papers that cover classes of optimal prediction functions in different setups, and I think it would be appropriate to mention this work and discussion connections. For example,  \nConsistent Binary Classification with Generalized Performance Metrics, Oluwasanmi O. Koyejo, Nagarajan Natarajan, Pradeep K. Ravikumar, Inderjit S. Dhillon\nHarikrishna Narasimhan, Rohit Vaish, and Shivani Agarwal. On the statistical consistency of plugin classifiers for non-decomposable performance measures.\nKrzysztof Dembczy´nski, Wojciech Kotłowski, Oluwasanmi Koyejo, and Nagarajan Natarajan. Consistency analysis for binary classification revisited.\nClayton Scott, A Generalized Neyman-Pearson Criterion for Optimal Domain Adaptation\n\nOne common theme is that the optimal decision rule is always a likelihood ratio test. If it’s not, it means the criterion being optimized is not sensible. So you could use that to frame your contribution. \n\nI would also recommend looking a the simple idea presented in the section on “Birdsall’s Insight” in Statistical Signal Processing by Louis Scharf.\n\nAnother potentially related paper is Classification with confidence by Jing Lei\n\nSec 3 \n\nIn the setup, the functions are assumed to be Lebesgue measurable. This means \\mathcal{X} should be a Euclidean space, which has not been indicated.\n\nIn the statement of Lemma 1, the notations rho(x) and pi(x) appear out of nowhere.\n\n*** The function R depends on c, whereas before it depended on c and h. An explanation is needed. The whole motivation involved h, but now h has been lost.\n\nSec 4\n\nLine 235: “useful variants” -> “special cases”\n\nLine 235: “whose solutions can be derived” – the full solution would require specification of tau(x) and lambda, so instead you could say that you are characterizing the form of the solution.\n\nProblem 1: mention that this does not fully recover the NP lemma because in the NP lemma, tau is a constant.\n\nIn the discussion of problems 4 and 5, I *think* you mean to say that these can be transformed to (25), not (24).\n\n** Can you give an example of where it does not suffice for tau(x) to be a constant? In all of the examples, tau(x) is neglected.\n\nProofs\n\nLine 337: what notion of dimension is meant? Do you mean it has positive Lebesgue measure on R^2?\n\nLine 348: why is C’ a compact set?\n\nLine 353: Need to discuss why pi is measurable, and presumably here A is a Borel set.\n\nLine 357-358: It’s clear that such x do not impact the first constraint, but it’s not clear that it doesn’t impact the objective function or second constraint. \n\nLine 360: contains pi(x)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Priority questions**\n\nR: *What is the impact of the contribution? Does it help us train selective classifiers? Some optimal solutions seem to require knowledge of the underlying distributions. In line 165 it is stated that the results are “potentially useful for specific applications”, but no concrete examples are given. Thus the impact could be more convincingly argued. This is probably the main weakness.*\n\nA: Our paper characterizes optimal strategies for various BDM decision problems, such as those used to define optimal selective classifiers. Although the formulations and derived optimal strategies rely on known data distributions, our results have two immediate practical impacts at least. First, learning involves finding a decision strategy within a predefined hypothesis space based on data. Knowing the optimal strategy's form allows to define a hypothesis space that includes the optimal strategy, essential for a statistically consistent algorithm. For reference, see the introduction, where we discuss prior SCOD works that used heuristically chosen hypothesis spaces that did not contain the optimal strategy, and a follow-up paper that improved results by modifying the heuristic to match the optimal rule. Second, our results allow the construction of plug-in optimal strategies for various problems.\n\nR: *Sec 2: What is the learning problem? Do we just get data from the “in distribution”?*\n\nA: Section 2 does not address any learning problems. Its goal is to provide examples of BDM problems and their optimal solutions (strategies). These formulations and strategies assume the data distribution is known. The significance of knowing the optimal strategy's form for designing learning algorithms is discussed in the previous answer.\n\nR: *The review of BDM problems discussed the optimal c, but the optimal h is not mentioned.*\n\nA: Our paper focuses on finding the optimal $c$ by solving various instances of the BDM problem. Except for the Neyman-Pearson problem, the example problems also involve finding the predictor $h$. However, in all the examples determining the optimal strategy for $h$ is straightforward. In all case, Bayes predictor $h^*(x)= {\\rm argmin_{y'}} \\sum_{y}p(y\\mid x)\\ell(y,y')$ is optimal due to additivity of the risk $R^S$, which allows $h$ to be optimized independently for each instance $x$.\n\nR: *The final example assumes that pi is known or can be estimated. Well, it will not be known in practice, and if estimated, the estimate won’t equal the true pi. Thus, it would be important to understand how having an estimate of pi impacts the usefulness of this case.*\n\nA: Yes, the formulation in Sec 2.6 is applicable only if $\\pi$ is known or can be estimated. If $\\pi$ is unknown, the formulations in Sec 2.4 and 2.5 should be used. While analyzing the sensitivity of the solution to the OOD ratio $\\pi$ in Sec 2.6 could be an interesting topic for future research, it is not the focus of our current paper.\n\nR: *The function R depends on c, whereas before it depended on c and h. An explanation is needed. The whole motivation involved h, but now h has been lost.*\n\nA: Thanks for point this out this inconsistency. We will include $h$ and emphasize that finding the optimal $h$ is not an issues (see the answer above).\n\nR: *Can you give an example of where it does not suffice for tau(x) to be a constant? In all of the examples, tau(x) is neglected.*\n\nA: There is a degenerate case when the score $s(x)$ equals the threshold $\\lambda$ for all $x\\in {\\cal X}$, and $\\tau(x)$ acts as a selection function. In this scenario, the points $(R(x)/p(x),q(x)/p(x))$ lie on a line $L$. Consequently, $\\tau(x)$ equals 1 for a line segment subset of $L$, and 0 otherwise. In practice, the degenerate cases occur when the instance space ${\\cal X}$ is finite.\n\nR: *In the statement of Lemma 1, the notations rho(x) and pi(x) appear out of nowhere.*\n\nA: Yes, it is a typo, these functions should be $p(x)$ and $q(x)$.\n\n**Proofs**\n\nR: *Line 337: what notion of dimension is meant? Do you mean it has positive Lebesgue measure on $\\mathbb{R}^2$?*\n\nA: It is the dimension of $\\rm{span}(A)$ in the vector space $\\mathbb{R}^2$.\n\nR: *Line 348: why is $C'$ a compact set?*\n\nA: We will provide details to show that $C'$ is both complete and totally bounded, i.e. compact. Essentially, a Cauchy sequence of feasible $c$'s cannot converge to a function that violates any of the constraints by some $\\varepsilon > 0$.\n\nR: *Line 353: Need to discuss why $\\pi$ is measurable, and presumably here $A$ is a Borel set.*\n\nA: Agreed, a discussion is required. We need to define $p(A)$, $c(A)$ only for those $A$ that are epsilon-balls in $\\mathbb{R}^2$. Then, we need to show that $\\pi^{-1}(A)$ is a measurable subset of ${\\cal X}$. It is fulfilled since this subset is determined by mesuarable functions derived from the functions $p(x), q(x), R(x)$. \n\nR: *Line 357-358: It’s clear that such $x$ do not impact the first constraint, but it’s not clear that it doesn’t impact the objective function or second constraint.*\n\nA: For such $x$ we can set $c^*(x)=0$ since this does not impact the first constrain and does not worsen the criterion or the second constraint. We will give a more detailed explanation.\n\nR: *Line 360: contains $\\pi(x)$*\n\nA: You are right.\n____\n\nThank you for highlighting these issues. We will revise and enhance the proof accordingly.\n\nWe will also apply the other suggested corrections to the main text.", "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": "w3mrKzuaAm", "reviewer": "Reviewer_oCzV", "summary": "The paper titled \"Constrained Binary Decision Making\" presents a comprehensive framework for binary statistical decision making (BDM), a critical area in both classical statistics and modern machine learning. The authors formulated BDM problems as constrained optimization tasks and provide a detailed characterization of the optimal solutions. The paper covers well-known and recent BDM problems, demonstrating the applicability of their generic approach to derive optimal decision strategies.", "questions": "- In Lemma 1, I do not know what $\\pi(x)$ and $\\rho(x)$ stand for. Should they be $p(x)$ and $q(x)$, respectively?", "limitations": "The authors claimed that \"The paper presents a theoretical result on an optimization problem, hence, in its essence, it has no limitations.\" I think in the **Extensions** section, I'm wondering that whether the proposed approach can be adapted to handle the case where more than one **$\\geq$** constraints exist, could this be a limitation of the current framework?", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- This paper is very well-written paper, and easy to follow.\n\n- The authors proposed an interesting framework that encompasses several popular BDM problems and presented solid proof.", "weaknesses": "- The authors claimed \"Conversely, skipping the optimal strategy derivation and using heuristic rules, such as the SIRC strategy from the original SCOD paper [23], can lead to sub-optimal performance\". I think it would be interesting (but not required) to conduct experiments to compare the proposed approach against the one in [23].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "R: *The authors claimed \"Conversely, skipping the optimal strategy derivation and using heuristic rules, such as the SIRC strategy from the original SCOD paper [23], can lead to sub-optimal performance\". I think it would be interesting (but not required) to conduct experiments to compare the proposed approach against the one in [23].*\n\nA: Recent papers [7] and [16] independently provided empirical evidence that the optimal strategy for SCOD outperforms the heuristic strategy SIRC [23].\n\nR: *The authors claimed that \"The paper presents a theoretical result on an optimization problem, hence, in its essence, it has no limitations.\" I think in the Extensions section, I'm wondering that whether the proposed approach can be adapted to handle the case where more than one constraints exist, could this be a limitation of the current framework?*\n\nA: We agree with the comment. Since the proposed extension is an unproven hypothesis, we will list it among the paper's limitations.\n\nR: *In Lemma 1, I do not know what $\\pi(x)$ and $\\rho(x)$ stand for. Should they be $p(x)$ and $q(x)$, respectively?*\n\nA: Yes, it is a typo, these functions should be $p(x)$ and $q(x)$.", "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": "rE7ks7ZkYn", "reviewer": "Reviewer_CrjX", "summary": "The authors proposed an optimization problem which has specific form of solutions that can be leveraged to solve various types of binary statistical decision making problems.", "questions": "As above.", "limitations": "adequately addressed", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The formulation of the optimization is general and there are many applications in binary statistical decision making problem.", "weaknesses": "The motivation for characterizing the optimal solution is quote the authors: \"This exmaple underscores the advantages of understanding the structure of the optimal solution to underlying BDM problems\". So it seems reasonable to me to add some experiments to validate the claim.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "R: *The motivation for characterizing the optimal solution is quote the authors: \"This example underscores the advantages of understanding the structure of the optimal solution to underlying BDM problems\". So it seems reasonable to me to add some experiments to validate the claim.*\n\nA: Recent papers [7] and [16] independently provided empirical evidence that the optimal strategy for SCOD outperforms the heuristic strategy SIRC [23].", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their efforts and valuable comments. Our responses are submitted separately for each review.

Meta-review: The authors develop a rigorous, theoretical approach to binary classification with a randomized classifier. The reviewers find the approach new and the proof techniques interesting. The expert reviewers do have a long list of changes that they're requesting and I would appreciate if the authors would please pay careful attention to these changes before the camera-ready deadline.
Decision: Accept (poster)