Constrained Binary Decision Making

Authors: daniel  pr
vojtěch  franc
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 09:26:04

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.

Main paper: 
 introduction: 
 Binary statistical decision making (BDM) involves selecting between two possible states using statistical evidence. This approach is applied across various fields, from classical statistics to machine learning. A notable example is the Neyman-Pearson problem [18] , which establishes the optimal strategy for testing two hypotheses and serves as the foundation for optimal detectors. Beyond classical statistics, BDM problems are used in many machine learning applications, such as detecting out-of-distribution (OOD) samples [11, 14, 6, 5, 15, 10, 2, 21, 20, 22, 23] , designing selective classifiers [13, 12, 4, 8, 9] , and developing selective classification in the presence of OOD data (SCOD) [24, 16, 7] to name a few.Instances of BDM determine the best decision-making strategy by solving a constrained optimization problem involving Lebesgue measurable functions in both the objective and constraints. Understanding the structure of this optimal strategy is crucial before deploying efficient methods to find it. The Neyman-Pearson lemma, a 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 a 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-Improvement and Bounded-Abstention models, serving as formal definitions of optimal selective classifiers, were first introduced in [19] . 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 a 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 to accept input samples as a solution to a novel BDM problem, they did not analyze the optimal strategy directly.Instead, they proposed a selector strategy named SIRC, combining two detectors using heuristically chosen non-linear functions. In a recently published paper [16] , the authors derived an optimal solution for the SCOD problem, demonstrating that the optimal selective strategy involves a 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 a comprehensive formulation of the BDM problem and thoroughly characterize the optimal strategy. Our framework encompasses various BDM problems as special cases, enabling us to derive optimal decision strategies for these instances. This provides a robust mathematical 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 4, 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.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: The contribution is summarized in the abstract and explained in 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 or 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
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 a selective classifier in the presence of out-of-distribution (SCOD) samples [24, 16] . 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 a recently emerging problem in the machine learning community.Consider a given classifier h : X → Y, where X is the instance space and Y a finite set of labels. We assume the classifier h was designed to minimize the prediction loss ℓ : Y × Y → R. Our task is to equip the classifier h with a binary stochastic decision strategy c : X → [0, 1]. The strategy c acts as a selector for input samples. The input sample x ∈ X is accepted for prediction by h with probability c(x) and reject otherwise. Thus, the pair (h, c) : X → Y ∪ {reject} forms a reject option classifier [3] :(h, c)(x) = h(x)with probability c(x) , reject with probability 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) p I : X → R + and the out-of-distribution (OOD) p O : X → R + . Thus, the input sample x ∈ X is generated fromEQUATIONwhere π ∈ [0, 1] represents the portion of OOD samples in the mixture. Additionally, if the sample x ∈ Y is generated from the in-distribution, a latent label y ∈ Y is generated according to the distribution p(y | x).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 ii) distribution uncertainty, which arises from input samples potentially coming from either in-distribution or out-of-distribution sources. 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. Each instance defines an optimal selector in a unique way. In Section 2.1, we described the Neyman-Pearson formulation of the OOD optimal detector [18] , which addresses only distribution uncertainty. Sections 2.2 and 2.3 cover the Bounded-Improvement and Bounded-Abstention models [19] , addressing only data uncertainty. In Section 2.4, we describe the SCOD problem [24] , which defines the optimal selector addressing both distribution and data 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. In Section 4, we demonstrate how to apply this theorem to easily find solutions for all the BDM instances described here.Assume our goal is to design a selector strategy c : X → [0, 1] that accepts only in-distribution (ID) samples and rejects out-of-distribution (OOD) samples. In other words, c functions as a binary classifier to distinguish ID and OOD samples. We will characterize the strategy c using two metrics. First, using the True Positive Rate (TPR) representing the probability that ID sample x is correctly accepted by the strategy:EQUATIONSecond, using the False Positive Rate (FPR) representing the probability that OOD sample x is incorrectly accepted by c:EQUATIONGiven maximal acceptable FPR, fpr max > 0, the NP task is to find a strategy c * that solves the following BDM problem [18] :EQUATIONA well-known solution to the NP task 4 is the strategy:EQUATIONwhere g(x) = p O (x) p I (x) is the likelihood ratio, θ ∈ R is a decision threshold, and τ ∈ [0, 1] is a probability of acceptance when g(x) = θ.Knowing the structure of the optimal strategy simplifies its construction significantly. The key to an optimal decision is accurately modeling the likelihood ratio g(x). Once the likelihood ratio is known, finding the optimal strategy involves setting the threshold θ and the randomization parameter τ , typically done by tuning these parameters on a validation sample. Moreover, if p I (x) and p O (x) are continuous, the randomization parameter τ can be arbitrary since the event g(x) = θ has zero probability of occurring.Let us consider the ideal scenario where the input instances x ∈ X are solely generated by the in-distribution p I (x), meaning the out-of-distribution portion in the model ( 1) is π = 0. Our aim is devise a selection strategy c : X → [0, 1] that accepts only those input samples x ∈ X where the prediction loss ℓ(y, h(x)) is likely to be small. We will characterize the strategy c using two metrics. First, we employ the notion of coverage:EQUATIONwhich reflects the probability of accepting an input sample. Secondly, we introduce the concept of "selective risk":EQUATION)representing the expected prediction loss ℓ : Y × Y → R on the accepted samples.Given a minimal acceptable coverage ω > 0, the bounded-abstention model defines the optimal selector strategy as the solution to the following BDM problem [19] :EQUATIONThe solution to the bounded-abstention model (8) consists of the Bayes predictorh * (x) = argmin y ′ y p(y | x)ℓ(y, y ′ )and the strategy [8, 9] :EQUATIONwhere r(x)EQUATIONis the conditional risk of the classifier h for the input x, θ ∈ R is a decision threshold and τ ∈ [0, 1] is a probability of acceptance when r(x) = 0.Note that the BDM problem (8) was formulated in [19] , but the optimal solution (9) was not derived until 14 years later in [8] .The values of θ and τ depend on p I (x, y) and ω, 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 θ and τ and and conducting an exhaustive search, although not always optimal, has proven effective in practice.The additivity of the risk R S allows h to be optimized independently of c, resulting in the Bayes predictor for all the problems discussed in the following sections. Therefore, from this point on, we will focus solely on optimal strategies for c.A symmetric definition of the optimal selector strategy is provided by the bounded-improvement model. Given a maximum acceptable selective risk λ > 0, the optimal selector is the solution to the following BDM problem:EQUATION)The solution to the bounded-improvement model (11) is similar to the strategy (9) , differing only in the specific values of the decision threshold θ and the randomization parameter τ [9] .The SCOD problem integrates the objectives of the Neyman-Pearson task and bounded-abstention models. The aim is to design a selector strategy c ∈ X → [0, 1] that accepts an input sample x if it 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 tpr(c), equation (2), False Positive Rate fpr(c), equation (3) and the selective risk R S (c), equation (7) . Given the relative cost α > 0 and the minimum acceptable TPR, tpr min > 0, the goal is to find a strategy c * that solves the following BDM problem [24] :EQUATION)The solution to the SCOD problem (12) is the strategy [16, 7] :EQUATIONfor α ∈ [0, 1) and s(x) = g(x) for α = 1. Here, r(x) is the conditional risk (10) , g(x) = p O (x) p I (x) is the likelihood ratio, θ ∈ R is a decision threshold, and τ ∈ [0, 1] the acceptance probability for the case s(x) = r(x).The BDM problem (12) was formulated in [24] . The optimal solution for continuous distributions was recently derived in [16] , and the solution for the general case was provided in [7] .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, as we will later show.The original formulation of the SCOD problem (12) relies on the user-defined relative cost α. However, this assumes that the prediction loss ℓ : Y × Y → R and the cost for incorrectly accepting 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 as follows. Given tpr min > 0 and fpr max > 0, the goal is to find a strategy c * that solves the following BDM problem:EQUATIONIn Section 4, we will prove that the optimal solution to the problem ( 14) is the strategy:c * (x) = 1 if s(x) < θ , τ if s(x) = θ , 0 if s(x) > θ ,whereEQUATIONwith θ ∈ R as the decision threshold, τ ∈ [0, 1] as the acceptance probability when s(x) = θ, and β ∈ R as a constant depending on the problem setup.Assume the portion of OOD samples π is known or can be estimated. In some applications, it is useful to replace FPR with precision, which is the proportion of true ID samples among all accepted inputs. Precision prec(c) is defined as:prec(c) = (1 -π) tpr(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 min > 0 and prec min > 0, the goal is to find a strategy c * which solves the following BDM problem:min h∈Y X ,c∈[0,1] X R S (h, c) s.t.tpr(c) ≥ tpr min and prec(c) ≥ prec min (16) In Section 4, we will prove that the optimal solution to the problem ( 16) is a strategy similar to (15) , differing only in the specific values of the decision threshold τ , the randomization parameter τ and the multiplier β.In the previous sections, we described six BDM problems, each with a 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 a 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 is crucial for designing efficient algorithms to learn the selector from examples. This knowledge can narrow the search space or simplify the problem using divide-and-conquer approaches.For instance, consider constructing a selector strategy for the SCOD problem. Whether using the original cost-based formulation (12) or the two novel variants ( 14) and ( 16), takes the form (15), the optimal strategy c * relies on an uncertainty score s(x) = r(x) + βg(x). The strategy accepts input x if s(x) is below a threshold θ, and with probability τ if s(x) = θ. This analysis shows that the core problem reduces to approximating the two components: the conditional riskr(x) = y∈Y p(y | x)ℓ(y, h(x))and the OOD/ID likelihood ratio g(x) = p O (x)/p I (x). Extensive literature on OOD detection provides methods to approximate g (e.g. [11, 14, 6, 5, 15, 10, 2, 21, 20, 22, 23] ), and there are methods to construct good proxies for r (e.g. [13, 12, 4, 8, 9] ).Once r and g are known, constructing the selector strategy involves determining the scalars θ, τ , and β. 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 β has an analytical solution, leaving only θ 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] .Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes]Justification: The paper explains that tuning the parameters of the score function that characterizes 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.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a 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 on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
main result: 
 In this section, we formulate a generic BDM problem, characterize its optimal solutions, and provide a straightforward instance of the optimal strategy.For a measurable set X in a measure space, Lebesgue measurable functions R, p, q : X → [0, ∞) with finite integrals on X , and fixed non-negative real values δ and σ, we define the following optimization problem:EQUATIONNote that we do not pose any additional requirements on the functions, like continuity or differentiability, 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 λ, µ such thatEQUATIONEQUATIONwhereEQUATIONEQUATIONInformally, equation (18) states that any optimal c * attains the value 1 on X < , except on a subset of measure zero. Similarly, by equation ( 19), c * attains the value 0 on X > , again up to a subset of measure zero. The sets X < and X > contain the points x for which R(x) p(x) + µ q(x) p(x) is below and above the threshold λ, respectively, excluding any insignificant elements where p(x) = 0.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 c * : X → [0, 1] to Problem (17) can be found among the formsc * (x) = 0 if s(x) > λ , τ (x) if s(x) = λ , 1 if s(x) < λ ,wheres(x) = R(x) p(x) + µ q(x) p(x) if p(x) > 0 , ∞ otherwise,is a score function, λ, µ are suitable real numbers, and τ : X → [0, 1] is a function implicitly defined by the problem parameters.Proof. Let c : X → [0, 1] be an optimal solution to Problem (17) . Consider real numbers λ, µ yielded by Theorem 1 and definec * (x) = 0 if s(x) > λ , c(x) if s(x) = λ , 1 if s(x) < λ .To show that c * is optimal, decompose X into the pairwise disjoint sets X < (see (20) ), X > (see (21) ), 18) and (19) ensure that c and c * are nearly identical on sets X < and X > , respectively, up to subsets of measure zero. By the definition of c * , they are identical on X = . Consequently, the criterion and constraints attain the same values for both c and c * on X < ∪ X > ∪ X = . Finally, the first constraint of ( 17) is independent of X ′ , and c * (x) ≤ c(x) for all x ∈ X ′ ensuresX ′ = {x ∈ X | p(x) = 0} and X = = {x ∈ X | s(x) = λ}. Equalities (X ′ R(x)c * (x) ≤ X ′ R(x)c(x) , X ′ q(x)c * (x) ≤ X ′ q(x)c(x) .In conclusion, c * is an optimal solution.Tool to solve the BDM problems Lemma 1 is a key tool for simplifying the BDM problem (17) . It shows that the main challenge is approximating the ratios R(x) p(x) and q(x) p(x) . Once these ratios are known, determining the score s involves finding the multiplier µ. With the score s, the optimal strategy c * depends on finding the decision threshold λ and the function τ (x). However, in cases where X is a continuous space, the boundary set {x ∈ X | s(x) = λ} typically has measure zero, except in some pathological instances. Consequently, τ (x) can be chosen arbitrarily and does not play a significant role. Thus, in continuous spaces, one only needs to find the scalars µ and λ, which can be tuned using held-out data, making the process much simpler than solving the original problem from scratch.The problem feasibility In the special case where only one constraint is given, i.e., when either p(x) = 0 or q(x) = 0, checking feasibility is straightforward. In the general case, to determine the feasibility of Problem (17) , we can formulate the task as:EQUATION)We obtain a similar problem but with only one constraint. Problem (17) is feasible if and only if Problem (22) attains a value less than or 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 to derive optimality conditions, as characterized in Theorem 1. However, when X is arbitrary and the functions R, p, q are essentially unrestricted, this approach becomes substantially more complex. In such cases, a 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, 18] 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 a line separating the images of the sets X < and X > in the plane, mapped by the function κ(x) = R(x) p(x) , q(x) p(x) .Extensions It remains an open problem whether our results can be generalized to the extended formulationEQUATIONwhere I is a finite index set, the functions q i are Lebesgue measurable with finite integrals on X , and σ i are non-negative bounds. A key question is whether a scoring function with 1 + |I| parameters (instead of 2) exists for this case. It is important to note that generalizing the current proof would involve addressing a significantly greater combinatorial complexity in the point configurations.0 ) ∩ conv(A 1 )) = 1, dim span(A 2 ) ≤ 1 and dim span((conv(A 0 ) ∩ conv(A 1 )) ∪ A 2 ) = 2. There are x 1 , x 2 ∈ X 0 , x 3 , x 4 ∈ X 1 , x 5 ∈ X 2 conforming to Claim 1.6.4. dim span(conv(A 0 ) ∩ conv(A 1 )) = 0, dim span(A 2 ) = 1, and dim span((conv(A 0 ) ∩ conv(A 1 )) ∪ A 2 ) = 2. There are z 1 , z 2 ∈ X 2 such that κ(z 1 ) and κ(z 2 ) conform to Claim 1.5, i.e., the line L passing through κ(z 1 ) and κ(z 2 ) determines two opposite half-planes, H 0 and H 1 . By Claim 1.5, A 0 ⊆ H 0 and A 1 ⊆ H 1 . This means that conv(A 0 ) ∩ conv(A 1 ) ⊆ L, which contradicts the assumption dim span((conv(A 0 ) ∩ conv(A 1 )) ∪ A 2 ) = 2.NeurIPS Paper Checklist• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
general tasks: 
 In this section, we introduce several special cases of problem (17) , whose forms of solutions directly follow from Theorem 1, as we will show. These cases encompass all the examples in Section 2. Thus, all the mentioned BDM problems can be solved in their general form using the single framework proposed in this paper.To simplify notation, we represent the Lebesgue measurable functions in (17) as p i : X → [0, ∞), i ∈ {0, 1, 2}. Furthermore, for Lebesgue measurable c : X → [0, 1], we define the functionals:F i (c) = X p i (x) c(x) dx , i ∈ {0, 1, 2} .The generic BDM problem (17) then requires solving for given non-negative scalars δ and ρ:EQUATION)Note that F 0 here does not depend on the classier h, which is consistent with the assumption that h is the Bayes predictor.Problem 1: Given δ > 0, the task is to solve:EQUATIONA special case is the Neyman-Pearson task (4).We derive this formulation from (24) by setting p 2 (x) = 0 for all x ∈ X . Lemma 1 implies that if the problem is feasible, it has an optimal solution c * such thatc * (x) =      0 if p0(x) p1(x) > λ , τ (x) if p0(x) p1(x) = λ , 1 if p0(x) p1(x) < λ .Note that here, Lemma 1 does not fully replicate the Neyman-Pearson strategy, in which τ is constant.Problem 2: Given δ > 0, the task is to solve:EQUATIONSpecial cases are the Bounded-Abstention model (8) and the original SCOD problem (12) .This formulation can equivalently be transformed to (25) by showing that there is an optimal solution c * such that F 1 (c * ) = δ. Indeed, if some optimal c : X → [0, ∞) fulfills F 1 (c) > δ, then we can define c * = δ F1(c) c, and it holds that F 1 (c * ) = δ andF 0 (c * ) F 1 (c * ) = δ F1(c) F 0 (c) δ = F 0 (c) F 1 (c) .Hence, such a c * is preserved in the set of optimal solutions of the problemmin c : X →[0,1] F 0 (c) δ s.t. F 1 (c) ≥ δ .Problem 3: Given δ > 0, the task is to solve:EQUATIONA special case is the Bounded-Improvement model (11) .Let c * be an optimal solution to (27). Define a problem:min c : X →[0,1] F 0 (c) F 1 (c) s.t. F 1 (c) ≥ F 1 (c * ) .Clearly, c * is feasible for the new problem, which is of the form (26). Moreover, any optimal solution c to this problem is also optimal to (27) because it attains the maximum F 1 (c * ) and satisfies the constraint:F 0 (c) F 1 (c) ≤ F 0 (c * ) F 1 (c * ) ≤ δ .Problem 4: Given δ > 0, σ > 0, the task is to solve:EQUATIONA special case is the SCOD problem formulation with constraints on FPR and TPR (14) .In this case, we can transform the problem to (24) in the same way as we did it for the formulation (26).Problem 5: Given δ > 0, σ > 0, the task is to solve:EQUATIONA special case is the SCOD problem formulation with the constraints on TPR and Precision ( 16) because the second constraint in ( 16) can be rewritten asfpr(c) tpr(c) ≤ (π -1 -1)(prec -1 min -1) , which matches the form F 2 (c) F 1 (c) ≤ σ .Again, the problem transforms to (24) using the same approach as in the case of the formulation (26). 
conclusion: 
 In this paper, we presented a comprehensive framework for solving binary decision-making (BDM) problems, which define optimal decision strategies through constrained optimization involving Lebesgue measurable functions. We characterize all optimal strategies for a generic BDM problem and derive a specific class of optimal strategies based on comparing a single score with a decision threshold. Our framework covers a 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 our 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. 
acknowledgement: 
 This research was supported by the CTU institutional support (future fund).A Appendix (proof of the main theorem)For a metric vector space V and its subset A ⊆ 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 2 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 x lies in the interior of P . Moreover, all vertices of the polygon P are elements of the set A.Proof. Given that x ∈ int(conv(A)), there is a triangle T ⊆ conv(A) such that x ∈ int(T ).According to Carathéodory's theorem [1] , each vertex of T lies in some simplex whose vertices are in the set A. Let these simplices be denoted as S 1 , S 2 , and S 3 . Defining P = conv(S 1 ∪ S 2 ∪ S 3 ) forms a convex polygon P with vertices in A, and x is in the interior of P .Proof of Theorem 1. Let X = {x ∈ X | p(x) > 0}. For all x ∈ X , we define g(x) = q(x) p(x) and r(x) = R(x) p(x) . We will associate elements of X with points in a plane by introducing the mapping κ :X → R 2 + such that κ(x) = (g(x), r(x)). The open ε-ball of π(x) in R 2 is denoted as B ε (x).For a measurable A ⊆ R 2 + , defineEQUATIONEQUATIONProblem ( 17) depends only on the subsetX + = x ∈ X | ∀ε > 0 : p(B ε (x)) > 0 ⊆ X .To see this, let us defineY 1 = {x ∈ X | p(x) = 0} and Y 2 = {x ∈ X | ∃ε > 0 : p(B ε (x)) = 0}.Then we haveEQUATIONsince, for each open ε-ball B ε (x), there exists a circle Q(x) ⊂ B ε (x) that contains x and has rational radius and center coordinates. Thus, Y 2 can be covered by countably many such circles on which the integral of p is zero. As a result, (32) implies that elements of X \ X + do not affect the left-hand side of the first constraint and do not negatively impact either the objective function or the second constraint. More precisely, for any feasible function c :EQUATION) then it holds X R(x)c ′ (x)dx ≤ X R(x)c(x)dx, X p(x)c ′ (x)dx = X p(x)c(x) 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: We present a 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 or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe 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)? 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 a 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 a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: The paper does not use any assets. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 Appendix: X q(x)c ′ (x)dx ≤ X q(x)c(x)dx. For the next considerations, we further distinguish three significant subsets of X + with respect to a fixed optimal solution c * : X → [0, 1].X 0 = x ∈ X + | ∃ε > 0 : c * (B ε (x)) = 0 , X 1 = x ∈ X + | ∃ε > 0 : c * (B ε (x)) = 1 , X 2 = x ∈ X + | ∀ε > 0 : 0 < c * (B ε (x)) < 1 . Note that • X 0 ∪ X 1 ∪ X 2 = X + , • c * (B ε (x)) = 0 ⇒ ∀ 0 < ε ′ ≤ ε : c * (B ε ′ (x)) = 0, and • c * (B ε (x)) = 1 ⇒ ∀ 0 < ε ′ ≤ ε : c * (B ε ′ (x)) = 1.To confirm the existence of suitable λ and µ, stated by the theorem for c * , it is sufficient to demonstrate that the setsEQUATION) A 2 = {κ(x) | x ∈ X 2 } (36)are "almost" linearly separable. This necessitates finding a line L ⊂ R 2 that includes A 2 and linearly separates A 0 \ L and A 1 \ L. The existence of such an L is ensured ifEQUATION)The proof continues by listing some general configurations of points from A 0 , A 1 , A 2 that contradict the optimality of c * . These forbidden configurations will be used to confirm the validity of condition (37).But we firstly establish estimates on κ -1 (Bε(y)) q(x)c * (x)dx and κ -1 (Bε(y)) R(x)c * (x)dx, for each y ∈ X and ε > 0.For a given y ∈ X , let κ(y) = (a, b) = q(y) p(y) , R(y) p(y) .Since, for allEQUATIONEQUATIONwe easily obtaina - ε 2 p(B ε (y))c * (B ε (y)) ≤ κ -1 (Bε(y)) q(x)c * (x)dx ≤ a + ε 2 p(B ε (y))c * (B ε (y)) , (40) and b - ε 2 p(B ε (y))c * (B ε (y)) ≤ κ -1 (Bε(y)) R(x)c * (x)dx ≤ b + ε 2 p(B ε (y))c * (B ε (y)) . (41) Claim 1.1. Let x 1 , x 2 ∈ X + , q(x1) p(x1) > q(x2) p(x2) , and R(x1) p(x1) > R(x2) p(x2) . If c * is optimal, then x 1 ∈ X 0 or x 2 ∈ X 1 .Proof of the claim. We proceed by contradiction. Assume that x 1 ∈ X 1 ∪ X 2 and x 2 ∈ X 0 ∪ X 2 . This implies the existence of an ε > 0 such that c * (B ε (x 1 )) > 0 and c * (B ε (x 2 )) < 1. Without loss of generality, choose ε sufficiently small so thatEQUATIONandEQUATION) which further implies B ε (x 1 ) ∩ B ε (x 2 ) = ∅. For i ∈ {1, 2}, denote B i = B ε (x i ), a i = q(xi) p(xi), and b i = R(xi) p(xi) . Define a function c ′ : X → [0, 1] as follows:c ′ (x) =      c * (x) -ν p(B1) c * (B1) c * (x) if x ∈ B 1 , c * (x) + ν p(B1) p(B2)-c * (B2) (1 -c * (x)) if x ∈ B 2 , c * (x)otherwise.Here, the parameter ν is defined as:ν = min c * (B 1 ), p(B 2 ) p(B 1 ) (1 -c * (B 2 )) > 0 ,which ensures 0 < ν p(B1) c(B1) ≤ 1 as well as 0 < ν p(B1) p(B2)-c(B2) ≤ 1, hence c ′ is defined correctly. By comparing c * and c ′ , we will show that c * is not optimal.Observe thatEQUATION< 0 .Analogously, we can deriveEQUATION< 0 .The relationships above contradict the optimality of c * . ■ Claim 1.2. Let x 1 , x 2 , x 3 be distinct elements of X + , and let α 1 , α 2 , β be non-negative real numbers such that α 1 + α 2 = 1, β ̸ = 0, and βκ(x 3 ) = α 1 κ(x 1 ) + α 2 κ(x 2 ). If c * is optimal, it holds:• If β < 1, then either x 3 ∈ X 0 or {x 1 , x 2 } ∩ X 1 ̸ = ∅, • if β > 1, then either x 3 ∈ X 1 or {x 1 , x 2 } ∩ X 0 ̸ = ∅.Proof of the claim. We will give a proof for β < 1 and note that the steps for β > 1 are analogous.EQUATIONEQUATIONandB ε (x 1 ), B ε (x 2 ), B ε (x 3 ) are pairwise disjoint. By contradiction, assume that c * (B ε (x 1 )) < 1, c * (B ε (x 2 )) < 1, and c * (B ε (x 3 )) > 0.To simplify the notation, for i ∈ {1, 2, 3}, letB i = B ε (x i ), c i = c * (B i ), and p i = p(B i ). Note that, according to the definition of X + , it holds p 1 , p 2 , p 3 > 0.Define a selective function c ′ : X → [0, 1] as follows:c ′ (x) =        c * (x) + να1p3 (1-c1)p1 (1 -c * (x)) if x ∈ B 1 , c * (x) + να2p3 (1-c2)p2 (1 -c * (x)) if x ∈ B 2 , c * (x) -ν c3 c * (x) if x ∈ B 3 , c * (x)otherwise.Taking z 0 = ∞ for any z > 0, the value of ν is given by:ν = min c 3 , p 1 α 1 p 3 (1 -c 1 ), p 2 α 2 p 3 (1 -c 2 ) .It is easy to see that ν > 0, and 0 < να1p3(1-c1)p1 , να2p3 (1-c2)p2 , ν c3 ≤ 1. Now, observe that X p(x)c ′ (x)dx - X p(x)c * (x)dx = κ -1 (B1) να 1 p 3 (1 -c 1 )p 1 p(x)(1 -c * (x))dx + κ -1 (B2) να 2 p 3 (1 -c 2 )p 2 p(x)(1 -c * (x))dx - κ -1 (B3) νp 3 c 3 p(x)c * (x)dx = να 1 p 3 + να 2 p 3 -νp 3 = νp 3 (α 1 + α 2 -1) = 0 . Next, derive X q(x)c ′ (x)dx - X q(x)c * (x)dx = κ -1 (B1) να 1 p 3 (1 -c 1 )p 1 q(x)(1 -c * (x))dx + κ -1 (B2) να 2 p 3 (1 -c 2 )p 2 q(x)(1 -c * (x))dx - κ -1 (B3) νp 3 c 3 q(x)c * (x)dx (40) ≤ να 1 p 3 a 1 + ε 2 + να 2 p 3 a 2 + ε 2 -νp 3 a 3 - ε 2 = νp 3 α 1 a 1 + α 2 a 2 -a 3 + ε 2 (α 1 + α 2 ) + ε 2 = νp 3 (βa 3 -a 3 + ε) (44) < 0 Quite similarly, X R(x)c ′ (x)dx - X R(x)c * (x)dx ≤ νp 3 (βb 3 -b 3 + ε) (45) < 0 . ■ Claim 1.3. Let z 1 , .. . , z n ∈ X + and x ∈ X + , and let P be a convex polygon with vertices κ(y 1 ), . . . , κ(y n ), with κ(x) as its inner point. The function c * is not optimal if one of the following cases holds:1. All z i 's are from X 0 and x ∈ X 1 .2. All z i 's are from X 1 and x ∈ X 0 .Proof of the claim. For the first case, we identify an edge of the polygon P that is first intersected by the half-line H starting from the origin (0, 0) and passing through the point κ(x) (see Figure 1a ). This edge has vertices κ(y 1 ) and κ(y 2 ) for some y 1 , y 2 ∈ {z 1 , . . . , z n }. The points κ(x), κ(y 1 ), and κ(y 2 ) are non-collinear and satisfy βκ(x) = α 1 κ(z 1 ) + α 2 κ(z 2 ) for some non-negative real numbers α 1 , α 2 , and β, where α 1 + α 2 = 1 and β < 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 halfline H (see Figure 1b ). Let κ(y 1 ) and κ(y 2 ) be vertices of this edge for some y 1 , y 2 ∈ {z 1 , . . . , z n }. The points κ(x), κ(y 1 ), and κ(y 2 ) satisfy βκ(x) = α 1 κ(y 1 ) + α 2 κ(y 2 ) for some non-negative real numbers α 1 , α 2 , and β, where α 1 + α 2 = 1 and β > 1. Again, Claim 1.2 contradicts the optimality of c * . ■ Claim 1.4. If x 1 , x 2 ∈ X 0 and x 3 , x 4 ∈ X 1 , and the line segments with endpoints κ(x 1 ), κ(x 2 ), and κ(x 3 ), κ(x 4 ) intersect at a point lying in the interior of both segments, then the function c * is not optimal. Proof of the claim.We consider two possible situations depicted in Figure 2 .First, we examine the scenario where one of the points κ(x 1 ), κ(x 2 ) is located lower-left relative to the other one, specifically, we assume g(x 1 ) ≤ g(x 2 ) and r(x 1 ) ≤ r(x 2 ), as illustrated in Figure 2a .According to Claim 1.1, the points κ(y 1 ), κ(y 2 ) cannot be situated within the shaded rectangular area. Since the line segments intersect, one of the points κ(y 1 ), κ(y 2 ) must be positioned upper-left from κ(x 2 ), while the other lies lower-right from κ(x 2 ) (these regions are labeled as A and B, respectively, in Figure 1a ). However, such an arrangement contradicts Claim 1.2.Secondly, we consider the configuration depicted in Figure 2b . One of the points κ(y 1 ), κ(y 2 ) must lie within the half-plane bounded by the line passing through κ(x 1 ), κ(x 2 ), and containing the origin (0, 0). Let's assume this point is y 2 . As per Claim 1.1, κ(y 2 ) cannot reside in the shaded area. Within this considered half-plane, there are three remaining triangular regions denoted as A, B, and C. Nevertheless, Claim 1.2 prohibits κ(y 2 ) from lying within region B (by applying the claim to the triple x 1 , x 2 , and y 2 ), region C (consider the triple y 1 , y 2 , and x 2 ), as well as region A (consider the triple y 1 , y 2 , and x 1 ). ■ Claim 1.5. If z 1 , z 2 ∈ X 2 and κ(z 1 ), κ(z 2 ) are distinct points, then the slope of the line L passing through κ(z 1 ) and κ(z 2 ) is not positive. Moreover, the open half-plane determined by L and the origin (0, 0) does not contain any point from A 1 ∪ A 2 , and similarly, the opposite open half-plane does not contain any point fromA 0 ∪ A 2 .Proof of the claim. If the slope of L is positive, as shown in Figure 3a , then the points κ(z 1 ) and κ(z 2 ) conform to Claim 1.1, implying that c * is not optimal. If the slope of L is not positive, referring to Figure 3b , we deduce that the open half-plane H 0 does not contain any point κ(x) from A 0 ∪ A 2 . By Claim 1.1, such a point P cannot be in the shaded area. It neither can be in areas A, B, or C because in each case, the points x, z 2 , and z 1 , or z 1 , z 2 , and x, or z 1 , x, and z 2 would conform to Claim 1.2. Similarly, it can be argued that a point from A 1 ∪ A 2 cannot lie in the opposite open half-plane. ■ Claim 1.6. Let x 1 , x 2 ∈ X 1 , y 1 , y 2 ∈ X 0 , z ∈ X 2 . If κ(x 1 ), κ(x 2 ), κ(y 1 ), and κ(y 2 ) are distinct points lying on a line L in such a way that κ(y 1 ) is between κ(x 1 ) and κ(x 2 ), and κ(x 2 ) is between κ(y 1 ) and κ(y 2 ), then κ(z) lies on L unless the function c * is not optimal.Proof of the claim.Firstly, observe that the configuration in Figure 4a is not admissible for an optimal c * , because κ(y 1 ) is located in the shaded area containing points to the left and down from κ(x 2 ) (Claim 1.1 applies here).Hence, it suffices to inspect the case with the opposite slope of L depicted in Figure 4b . Note that, without loss of generality, we assume that the highest point on L is κ(y 2 ). The case when the highest point is either κ(x 1 ) or κ(x 2 ) is handled similarly. If c * is optimal, then κ(z) 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 κ(z) lies in any of these parts, then we can always select two elements from {x 1 , x 2 , y 1 , y 2 } that together with z conform to Claim 1.2. These selections are as follows:A : z, y 1 , x 2 , B : x 1 , x 2 , z, C : z, y 1 , x 1 , D : z, x 2 , y 2 , E : y 1 , y 2 , z, F : z, x 2 , y 1 .We are ready to confirm condition (37), by listing all the potential infeasible cases and showing that they contradict the optimality of c * .1. dim span(conv(A 0 ) ∩ conv(A 1 )) = 2. We distinguish three subcases.Assume that, for some x ∈ X 0 , κ(x) is in the interior of conv(A 0 ) ∩ conv(A 1 ). By Lemma 2, there is a convex polygon P with vertices in κ(X 1 ) such that the interior of P contains x. Apply Claim 1.3.Next, assume that x belongs to X 1 instead of X 0 . Analogously, find a convex polygon P ′ with vertices in κ(X 0 ), containing x in its interior. Apply Claim 1.3.Finally, if int(conv(A 0 )∩conv(A 1 ))∩(A 0 ∪A 1 ) = ∅, take an arbitrary x ∈ int(conv(A 0 )∩ conv(A 1 )). By Carathéodory's theorem, there exists a simplex S 0 (a line segment or triangle) with vertices in A 0 such that κ(x) ∈ int(S 0 ). Similarly, there exists a simplex S 1 (a line segment or triangle) with vertices in A 1 such that κ(x) ∈ int(S 1 ). It is not difficult to see that the boundary line segments of S 0 and S 1 intersect, meaning there are two intersecting line segments, one with endpoints in A 0 , and the other with endpoints in A 1 . Hence, Claim 1.4 contradicts the optimality of c * .2. dim span(A 2 ) = 2. There exist x 1 , x 2 , x 3 ∈ X 2 such that κ(x 1 ), κ(x 2 ), κ(x 3 ) are noncollinear. Such a configuration is prohibited by Claim 1.5. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: Limited Empirical Validation:
The 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.


Computational Complexity:
The 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.
questions: 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.
Handling Unknown Distributions:

How 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?
Computational Efficiency:
limitations: limitations: NA
paper_summary: paper_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.
strength_weakness: strength_weakness: In my view, the following points are the weaknesses of the paper and I kindly invite the authors to address them:
- 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. 
- 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. 
- 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.
- 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$.
- 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. 
- 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. 
- 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. 

Some minor typos and issues:
- Line 70: "is" generated from the in-distribution
- Line 91: "to distinguishes" has a typo
- 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$. 
- Equation (10): Missing comma ","
- Some references to (15) should be (14) instead. Examples are line 149, and 172. 
- Line 157: "solvers" should be "solves"? That said "the strategy" should be "a strategy" if there can be alternative optima.
questions: 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?
- 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. 
- Are defining the distributions as $p: \mathcal{X} \mapsto \mathbb{R}_+$ the formal way? Is this how the literature defines them?
- 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.
- Can you discuss the measurability of the functions, such as terms in (7)?
- Equation (12): Aren't there work in the literature that also constrains $\phi(c)$?
- 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

The other notable weakness is that the motivation involves a classifier h and a selection function c, but then h goes away at some point.

Below I include a section by section list of comments that I made while reading the paper.

Introduction: 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.

*** 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.

The 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

Reference [17]: “Person” should be “Pearson”

** Sec 2: What is the learning problem? Do we just get data from the “in distribution”?

The 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.

Eqn. (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.

Eqn. (10): missing “)”

*** The review of BDM problems discussed the optimal c, but the optimal h is not mentioned.

Selective risk: notation varies, e.g., R^S vs R_S

** 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.

There 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,  
Consistent Binary Classification with Generalized Performance Metrics, Oluwasanmi O. Koyejo, Nagarajan Natarajan, Pradeep K. Ravikumar, Inderjit S. Dhillon
Harikrishna Narasimhan, Rohit Vaish, and Shivani Agarwal. On the statistical consistency of plugin classifiers for non-decomposable performance measures.
Krzysztof Dembczy´nski, Wojciech Kotłowski, Oluwasanmi Koyejo, and Nagarajan Natarajan. Consistency analysis for binary classification revisited.
Clayton Scott, A Generalized Neyman-Pearson Criterion for Optimal Domain Adaptation

One 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. 

I would also recommend looking a the simple idea presented in the section on “Birdsall’s Insight” in Statistical Signal Processing by Louis Scharf.

Another potentially related paper is Classification with confidence by Jing Lei

Sec 3 

In the setup, the functions are assumed to be Lebesgue measurable. This means \mathcal{X} should be a Euclidean space, which has not been indicated.

In the statement of Lemma 1, the notations rho(x) and pi(x) appear out of nowhere.

*** 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.

Sec 4

Line 235: “useful variants” -> “special cases”

Line 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.

Problem 1: mention that this does not fully recover the NP lemma because in the NP lemma, tau is a constant.

In the discussion of problems 4 and 5, I *think* you mean to say that these can be transformed to (25), not (24).

** 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.

Proofs

Line 337: what notion of dimension is meant? Do you mean it has positive Lebesgue measure on R^2?

Line 348: why is C’ a compact set?

Line 353: Need to discuss why pi is measurable, and presumably here A is a Borel set.

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. 

Line 360: contains pi(x)
questions: 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: limitations: There are no anticipated negative societal impacts.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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].
questions: 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: 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?
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: As above.
limitations: limitations: adequately addressed

Comments: title: Authors answers to reviewer's questions
Reply to rebuttal
Reviewer response?
Detailed answers.
Thank you & I am concerned
comment: R: Have the authors considered conducting empirical experiments to validate the proposed framework? ...

A: Our paper focuses solely on providing a mathematical tool for deriving optimal strategies in various BDM problems. Our theorem implies these optimal strategies cannot perform worse than any alternatives, and in the worst case, the improvement might be small. However, there are instances where BDM problems initially addressed with heuristic strategies were later shown to perform significantly better when optimal strategies were identified and empirically validated.

A recent example from the machine learning field is the BDM in the SCOD problem (please, see paragraph 3 of the introduction). Initially solved with the SIRC selection strategy [23], it was later shown to be suboptimal in [16], with empirical evidence supporting this. Similarly, the Neyman-Pearson problem in statistics, one of the earliest BDM examples, offers ample empirical proof that the likelihood ratio outperforms alternative methods for separating two distributions.

R: How 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?

A: Yes, distribution uncertainty can be addressed by formulating the BDM problem. The SCOD problem is a good example of this. By definition, there is no clear sample of Out-Of-Distribution (OOD) data. However, the optimal strategy shows that modeling the ratio of OOD to In-Distribution (ID) samples is sufficient for making optimal decisions (see Equation 13). Methods for estimating this OOD/ID ratio, such as using an unlabeled mixture of ID and OOD data, have been discussed in [16] and other papers.
Sorry for the late reply. I thank the reviewer for their clarification. Their reply addresses my concern, and I would like to keep my score.
Reviewer CrjX, could you please review the authors' response and see whether it addresses your questions? Please acknowledge having done so in a comment. Thanks.
R: Although I appreciate the authors going through each of my comments, I would like to kindly state that this rebuttal is not satisfactory to me. None of my comments are addressed in any depth. 

A: Since there was no priority list, we addressed all the reviewer's questions. However, due to the 6,000-character limit, we had to keep our responses concise.

R: For multi-objective discussion, the authors ...

A: The inability to assign the same physical units to individual decisions (and hidden states) often prevents straightforward weighting of multiple errors with different meanings. As a result, constraints on specific errors are commonly used, especially when certain errors need explicit control in specific applications. This approach is standard in multi-criteria decision-making and not unique to the SCOD problem. For example, similar strategies are applied in selective classification, as seen in Sections 2.2 and 2.3, which offer alternatives to the traditional cost-based reject-option classifier [3]. We applied this same strategy to the SCOD problem.

However, please note that our paper's primary focus is not on revising existing SCOD formulations. We use them to demonstrate the versatility and usefulness of our framework.

R: More importantly, to my understanding, the known ...

A: We initially considered using the principle of Lagrange duality to address our ILP problem, as it offers a way to establish optimality conditions that could potentially characterize the solutions. We applied duality to finite domains ${\cal X}$, transforming the ILP into an LP, which gave us some insight into the general solution form. However, extending this approach to an arbitrary domain ${\cal X}$ and functions $R$, $p$, $q$ (with finite integrals) would require a more general duality theorem, and even then, deducing the desired result would be far from straightforward due to the increased complexity of the optimality conditions. Given these challenges and inspired by techniques used in related work (e.g., [9, 16, 17] and others on the Neyman-Pearson problem), we decided to pursue a direct proof instead. This approach provided us with solid insights, leaving only the technical details to be completed. While we do not dismiss the possibility that ILP techniques could yield the same result, potentially with a simpler proof, we believe that this path is not as straightforward as it might seem.

R: Finally, I would like to strongly recommend not using ...

A: We respectfully disagree with the suggestion that optimizing two or three scalars is not "significantly easier" than optimizing an entire function. In all existing examples, tuning these parameters by discretizing their values and performing an exhaustive search, though not necessarily optimal, has proven effective in practice.
Thanks for addressing my comments. I will keep my score unchanged.
I would like to thank the authors for responding to my review. I will maintain my score of weak accept. I have no doubt the authors can improve the paper, but there are enough changes that I would want to re-review the entire paper before making a stronger recommendation.
I would like to thank the authors for their rebuttal. 

Although I appreciate the authors going through each of my comments, I would like to kindly state that this rebuttal is not satisfactory to me. None of my comments are addressed in any depth. To give some examples:

- For multi-objective discussion, the authors say "We do not intend to criticize multi-objective problems" but regardless of what the authors intend, it's just an informal and unusual motivation to revise multi-objective programs just because of differences in units. 

- More importantly, to my understanding, the known proofs of Neyman-Pearson lemma do not use any infinite-dimensional LP field. But this paper does take that approach. It is still ok if such a result is known out there, but I don't think "We do not see an immediate, straightforward application." is a convincing argument. I am not even sure KKT conditions are common in ILP literature. In general, I was hoping to see more than "We will include a discussion on this topic." 

Finally, I would like to strongly recommend not using statements like "mu and lambda tuning is significantly easier". It can still be intractable in many settings. Just because we have less variables to tune should not imply this paper presents a tractable approach.