Exact Risk-Complexity Laws for Projective Boundaries in Scenario Optimization and Distribution-Free Certification
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
- SOVER: Formal Certification of Optimization Reformulations via LLM-Assisted SMT Verification
- Exact certification for conic optimization over quadratic modules: partitions of unity and recession directions
- Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms
- The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
- A note on the complexity of random subspace model-based methods for derivative-free optimization
BibTeX
@misc{calafiore2026exact,
title = {{Exact Risk-Complexity Laws for Projective Boundaries in Scenario Optimization and Distribution-Free Certification}},
author = {Giuseppe C. Calafiore},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.01355},
eprint = {2609.01355},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.01355},
}
RIS
TY - UNPB
TI - Exact Risk-Complexity Laws for Projective Boundaries in Scenario Optimization and Distribution-Free Certification
AU - Giuseppe C. Calafiore
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.01355
UR - https://arxiv.org/abs/2609.01355
AB - 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.
ER -