Research map / Learning theory and algorithms / Combinatorial and search optimization
Constrained Binary Decision Making
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a general theorem characterizing optimal solutions of binary decision making problems (linear-fractional and constrained integral forms) as thresholding a two-parameter score, and applies it to NP detection, bounded-abstention/improvement, SCOD and two new SCOD variants.
Problem
Optimal binary decision strategies are defined by constrained optimization over Lebesgue-measurable functions in both objective and constraints, and their structure has historically been derived case by case, taking years.
Approach
A single generic constrained linear problem with one objective integral and two integral constraints is shown to have optimal solutions that threshold a score R/p + mu*q/p, proved via a direct geometric argument (forbidden point configurations in the plane of ratios) rather than Lagrange duality, without differentiability or discreteness assumptions.
Key results
- Theorem 1 shows every optimal strategy for the generic constrained problem equals 1 on a set where the score is below a threshold and 0 where it is above, with two real parameters (lambda, mu).
- Lemma 1 gives a single score function s(x)=R/p+mu q/p whose threshold yields an optimal strategy, and feasibility reduces to a one-constraint problem.
- Derives optimal strategies for NP, bounded-abstention, bounded-improvement, SCOD and two new SCOD variants (bounded TPR-FPR and bounded TPR-precision); no experiments are reported.
Limitations
- Extension to more than two constraints (|I|>1) remains an open problem.
- Tuning the score parameters (mu, lambda) must be done per problem, typically on held-out data.
- The paper contains no experiments; practical value is shown only through derivations.
Experimental setup
Baselines: SIRC
Builds on: Neyman-Pearson lemma bounded-abstention model bounded-improvement model SCOD (SIRC)
Closest papers by meaning
- What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization (NeurIPS 2025 · similarity 0.83)
- Statistical Methodologies for Decision-Making and Uncertainty Reduction in Machine Learning (AAAI 2025 · similarity 0.83)
- Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms (ICML 2025 · similarity 0.82)
- Decision Theoretic Foundations for Conformal Prediction: Optimal Uncertainty Quantification for Risk-Averse Agents (ICML 2025 · similarity 0.82)
- Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability (NeurIPS 2024 · similarity 0.82)
- Solver-Free Decision-Focused Learning for Linear Optimization Problems (NeurIPS 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.