Exact Risk-Complexity Laws for Projective Boundaries in Scenario Optimization and Distribution-Free Certification

• URL: http://arxiv.org/abs/2609.01355v1
• Date: Tue, 01 Sep 2026 14:58:38 GMT
• Title: Exact Risk-Complexity Laws for Projective Boundaries in Scenario Optimization and Distribution-Free Certification
• Abstract summary: Conditional violation risk follows an exact beta law, whose tail has a beta-binomial representation and whose parameter is a support, calibration, or compression dimension.<n>This paper identifies the deterministic boundary mechanism behind these formulas and derives the corresponding law when the observed boundary size is random.<n>It also yields conditional probabilistic certificates and a no-go result explaining why observed complexity alone is insufficient.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Scenario optimization, conformal prediction, and related distribution-free certification methods use finite samples to construct decisions or prediction sets with violation-risk guarantees for fresh observations. In several classical settings, the conditional violation risk follows an exact beta law, whose tail has a beta-binomial representation and whose parameter is a support, calibration, or compression dimension. This paper identifies the deterministic boundary mechanism behind these formulas and derives the corresponding law when the observed boundary size is random. A decision rule is represented by an acceptance set for future observations, together with a boundary map selecting the sample points responsible for that set. The resulting pair is called a {\em proper projective boundary scheme} when held-out samples are accepted precisely if the full-sample boundary is retained, and accepted non-boundary samples can be deleted without changing that boundary. For every such scheme, the conditional law of the violation risk given the observed boundary size is determined by the boundary's cross-sample complexity profile. A stable profile yields the usual beta law, whereas a varying profile produces an exact profile correction. The framework covers scalar order-statistic calibration, support-reconstructive scenario programs, cascaded support-removal certificates, coordinatewise envelopes, and Pareto-frontier calibration with vector scores. It also yields conditional probabilistic certificates and a no-go result explaining why observed complexity alone is insufficient.

Related papers

• Conformal-DRO: Distributionally Robust Optimization with Conformalized Ambiguity Set [9.492534748349316]
  This paper studies latent distributional heterogeneity, where each instance has an unobserved law but contributes only one observation.<n>We propose Conformal-DRO, which uses nested conformal regions to construct an ambiguity set for the future latent law.<n>The resulting robust value provides a finite-sample certificate for the selected decision's expected cost.
  arXiv  Detail & Related papers  (2026-09-10T04:30:21Z)
• Conformal Prediction via Transported Beta Laws [0.0]
  We study the law of the calibration-conditional coverage induced by a realized conformal threshold.<n>We take this beta law as a finite-sample reference object and quantify departures from it using Wasserstein distances.
  arXiv  Detail & Related papers  (2026-05-18T18:46:39Z)
• Bridging Conformal Prediction and Scenario Optimization: Discarded Constraints and Modular Risk Allocation [0.0]
  This paper revisits that connection directly from a systems-and-control viewpoint.<n>We introduce a simple modular composition rule that combines several blockwise calibration certificates into a single joint guarantee.
  arXiv  Detail & Related papers  (2026-03-19T18:37:58Z)
• Conformal Tradeoffs: Guarantees Beyond Coverage [0.02648566468224904]
  Deployed conformal predictors are long-lived decision infrastructure operating over finite operational windows.<n> Marginal coverage does not determine deployment-facing quantities.<n>We provide a framework for operational certification and planning beyond coverage.
  arXiv  Detail & Related papers  (2026-02-20T07:58:25Z)
• Flow-Based Conformal Predictive Distributions [1.2691047660244335]
  We show that a differentiable nonconformity score induces a deterministic flow on the output space whose trajectories converge to the boundary of the corresponding conformal prediction set.<n>This leads to a computationally efficient, training-free method for sampling conformal boundaries in arbitrary dimensions.<n>We evaluate the approach on PDE inverse problems, precipitation downscaling, climate model debiasing, and hurricane trajectory forecasting.
  arXiv  Detail & Related papers  (2026-02-07T17:26:50Z)
• Distribution-informed Online Conformal Prediction [53.674678995825666]
  We propose Conformal Optimistic Prediction (COP), an online conformal prediction algorithm incorporating underlying data pattern into the update rule.<n>COP produces tighter prediction sets when predictable pattern exists, while retaining valid coverage guarantees even when estimates are inaccurate.<n>We prove that COP can achieve valid coverage and construct shorter prediction intervals than other baselines.
  arXiv  Detail & Related papers  (2025-12-08T17:51:49Z)
• LEC: Linear Expectation Constraints for False-Discovery Control in Selective Prediction and Routing Systems [95.35293543918762]
  Large language models (LLMs) often generate unreliable answers, while uncertainty methods fail to fully distinguish correct from incorrect predictions.<n>We address this issue through the lens of false discovery rate (FDR) control, ensuring that among all accepted predictions, the proportion of errors does not exceed a target risk level.<n>We propose LEC, which reinterprets selective prediction as a constrained decision problem by enforcing a Linear Expectation Constraint.
  arXiv  Detail & Related papers  (2025-12-01T11:27:09Z)
• Beyond Uncertainty Sets: Leveraging Optimal Transport to Extend Conformal Predictive Distribution to Multivariate Settings [0.14504054468850666]
  Conformal prediction (CP) constructs uncertainty sets for model outputs with finite-sample coverage guarantees.<n>We show that optimal assignment is piecewise-constant across a fixed polyhedral partition of the score space.<n>This allows us to characterize the entire prediction set tractably, and provides the machinery to address a deeper limitation of prediction sets.
  arXiv  Detail & Related papers  (2025-11-19T05:59:01Z)
• Unsupervised Conformal Inference: Bootstrapping and Alignment to Control LLM Uncertainty [49.19257648205146]
  We propose an unsupervised conformal inference framework for generation.<n>Our gates achieve close-to-nominal coverage and provide tighter, more stable thresholds than split UCP.<n>The result is a label-free, API-compatible gate for test-time filtering.
  arXiv  Detail & Related papers  (2025-09-26T23:40:47Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• SConU: Selective Conformal Uncertainty in Large Language Models [59.25881667640868]
  We propose a novel approach termed Selective Conformal Uncertainty (SConU)<n>We develop two conformal p-values that are instrumental in determining whether a given sample deviates from the uncertainty distribution of the calibration set at a specific manageable risk level.<n>Our approach not only facilitates rigorous management of miscoverage rates across both single-domain and interdisciplinary contexts, but also enhances the efficiency of predictions.
  arXiv  Detail & Related papers  (2025-04-19T03:01:45Z)
• Conformal Generative Modeling with Improved Sample Efficiency through Sequential Greedy Filtering [55.15192437680943]
  Generative models lack rigorous statistical guarantees for their outputs.<n>We propose a sequential conformal prediction method producing prediction sets that satisfy a rigorous statistical guarantee.<n>This guarantee states that with high probability, the prediction sets contain at least one admissible (or valid) example.
  arXiv  Detail & Related papers  (2024-10-02T15:26:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.