Research map / Learning theory and algorithms / Prediction and decision losses
Understanding Fixed Predictions via Confined Regions
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.
Proposes finding confined boxes (regions where all individuals receive fixed predictions) for linear classifiers via a MIQCP built on Farkas certificates, enabling data-free, out-of-sample recourse auditing.
Problem
Existing recourse verification audits fixed predictions pointwise on observed data, so it misses fixed predictions for out-of-sample individuals and cannot be used when no representative dataset is available.
Approach
Verify recourse over entire regions rather than individuals by searching for the largest axis-aligned box in which every individual has no feasible recourse, certified via Farkas certificates of infeasibility cast as a MIQCP; under linear recourse constraints the discrete problem reduces to a linear relaxation via total unimodularity.
Key results
- Pointwise baselines produce blindspots on 2.8% to 37.4% of audited regions and loopholes on 0.6% to 20% of regions.
- The proposed Region Verification method finds zero blindspots and zero loopholes across all three datasets.
- The approach runs in under 5 seconds on average across datasets, and enumerates at least 100 confined regions on benchmark datasets with fewer than 50 features.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use region-level verification instead of Data pointwise auditing | L1-regularized logistic regression · FICO | blindspot rate: 12.3% -> 0.0% | Helped |
| Use region-level verification instead of Data pointwise auditing | L1-regularized logistic regression · FICO | loophole rate: 0.6% -> 0.0% | Helped |
| Use region-level verification instead of Data pointwise auditing | L1-regularized logistic regression · GiveMeCredit | blindspot rate: 0.0% -> 0.0% | No clear effect |
| Use region-level verification instead of Region pointwise auditing | L1-regularized logistic regression · GiveMeCredit | loophole rate: 0.8% -> 0.0% | Helped |
| Use region-level verification instead of Region pointwise auditing | L1-regularized logistic regression · Twitterbot | blindspot rate: 0.0% -> 0.0% | No clear effect |
| Use region-level verification instead of Region pointwise auditing | L1-regularized logistic regression · Twitterbot | loophole rate: 20.0% -> 0.0% | Helped |
Surprising findings
- Pointwise audits using observed data can output responsive for regions that actually contain confined individuals (blindspots), even with 100 sampled points or the full training data.
Limitations
- Limited to linear classifiers and MILP-representable models; tree ensembles would need intractable MIQCPs.
- Confined boxes have limited expressive power and may need many boxes to characterize regions.
- Relaxed FCP gives only weaker guarantees when non-linear recourse constraints are present.
Experimental setup
Datasets: heloc givemecredit twitterbot Pennsylvania Sentencing Risk Assessment Instrument (SRAI)
Benchmarks: heloc givemecredit twitterbot
Metrics: certifies responsive outputs responsive blindspot rate certifies confined outputs confined loophole rate runtime
Baselines: Data pointwise audit Region sampling audit Score-based pointwise audit
Builds on: Farkas' lemma recourse verification Reach package
Closest papers by meaning
- Kandinsky Conformal Prediction: Beyond Class- and Covariate-Conditional Coverage (ICML 2025 · similarity 0.83)
- Self-Organized Conformal Prediction: Reducing Regional Coverage Gaps with Unsupervised Group Discovery (NeurIPS 2026 · similarity 0.83)
- Conformal Prediction with Learned Features (ICML 2024 · similarity 0.83)
- Prediction without Preclusion: Recourse Verification with Reachable Sets (ICLR 2024 · similarity 0.82)
- Regional Explanations: Bridging Local and Global Variable Importance (NeurIPS 2025 · similarity 0.82)
- Conformal Prediction Regions for Time Series Using Linear Complementarity Programming (AAAI 2024 · similarity 0.82)
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.