Source-linked AI summary
Bridging Conformal Prediction and Scenario Optimization: Discarded Constraints and Modular Risk Allocation
Giuseppe C. Calafiore
TL;DR
Scenario optimization and conformal prediction both provide finite-sample safety margins, but their differing terminology obscures the connection between their guarantees. The paper extends the exchangeability-based conformal/scenario bridge to feasible sample-and-discard algorithms with stable retained reconstruction and combines blockwise calibration certificates. Across all three cases, mean trajectory risk remains close to 0.06, while allocation across stages changes substantially.
Problem
Scenario optimization and conformal prediction both provide finite-sample safety margins, but their differing terminology obscures the connection between their guarantees.
Source: §1 · p. 1Method
Results
Across all three cases, mean trajectory risk remains close to 0.06, while allocation across stages changes substantially.
Source: §6.1 · p. 10Takeaways & Limitations
The modular rule makes risk allocation explicit across outputs or horizon steps, allowing local margins to be reshaped while preserving an overall certificate.
Source: §1 · p. 2, §6.1 · p. 10Sharper bounds under coordinate independence are reserved for applications where that independence can be reliably verified.
Source: §5.1 · p. 8
Abstract
from arXiv · showhide
Scenario optimization and conformal prediction share a common goal, that is, turning finite samples into safety margins. Yet, different terminology often obscures the connection between their respective guarantees. This paper revisits that connection directly from a systems-and-control viewpoint. Building on the recent conformal/scenario bridge of \citet{OSullivanRomaoMargellos2026}, we extend the forward direction to feasible sample-and-discard scenario algorithms. Specifically, if the final decision is determined by a stable subset of the retained sampled constraints, the classical mean violation law admits a direct exchangeability-based derivation. In this view, discarded samples naturally appear as admissible exceptions. We also introduce a simple modular composition rule that combines several blockwise calibration certificates into a single joint guarantee. This rule proves particularly useful in multi-output prediction and finite-horizon control, where engineers must distribute risk across coordinates, constraints, or prediction steps. Finally, we provide numerical illustrations using a calibrated multi-step tube around an identified predictor. These examples compare alternative stage-wise risk allocations and highlight the resulting performance and safety trade-offs in a standard constraint-tightening problem.
1 Introduction
Scenario optimization and conformal prediction both turn finite samples into safety margins, but use different terminology for related guarantees. This paper extends their connection to feasible sample-and-discard algorithms and offers a modular way to allocate risk across structured control problems.
1 Introduction
- The paper frames scenario optimization and conformal prediction as finite-sample methods that produce data-driven margins for optimization, monitoring, or safety filtering.Both aim for guarantees about future violations or prediction errors without requiring a fully specified probabilistic model.Source: §1 · p. 1
- The paper extends the conformal/scenario bridge to feasible sample-and-discard algorithms with stable retained reconstruction, interpreting discarded samples as admissible exceptions.It also distinguishes this interpretive extension from deriving sharper numerical bounds.Source: §1 · p. 2
- A modular rule combines blockwise calibration certificates into a joint guarantee, enabling explicit risk budgeting across outputs or horizon steps.The rule is used to compare stage-wise allocations and their resulting calibrated tubes and control trade-offs.Source: §1 · p. 2
2 Background and problem statement
The background introduces conformal calibration as a way to select data-driven prediction margins, then formulates scenario optimization with discarded constraints. The scenario guarantee relies on feasibility and a stable retained reconstruction set, not convexity alone.
2.1 Conformal prediction, calibration, and conditional risk
- Split conformal calibration ranks held-out nonconformity scores to select a threshold; for absolute residuals, that threshold defines an interval around the nominal prediction.A calibration-conditional certificate states that, with confidence at least 1−δ over the calibration sample, conditional risk is at most ϵ.Source: §2.1 · p. 3
2.2 Scenario optimization with discarded constraints
- A sample-and-discard algorithm removes r sampled constraints and returns a decision satisfying every retained constraint; its out-of-sample violation is evaluated on a fresh scenario.The required structural condition is a retained subset that determines the decision, so removing any other retained sample leaves it unchanged.Source: §2.2 · p. 3
- The stable retained reconstruction assumption requires measurable, permutation-equivariant discard and reconstruction sets, with the decision feasible on retained constraints and unchanged by removing samples outside those sets.For many retained convex programs with a unique optimizer and measurable tie-breaking, a support or compression set can serve as the reconstruction set; if its size is bounded by ζ, bounds depend on r + ζ.Source: §2.2 · pp. 3–4
3 A bridge lemma: reconstruction with admissible exceptions
The bridge lemma uses exchangeability to show that a missed future point must be either needed to reconstruct the predictor or among explicitly allowed exceptions. Bounding the sizes of those sets therefore bounds the probability of a miss.
3 A bridge lemma: reconstruction with admissible exceptions
- A future point missed by the predictor must, in the augmented sample, belong to the reconstruction set or the exception set.The lemma isolates the exchangeability mechanism that gives admissible exceptions a conformal-style interpretation.Source: §3 · p. 4
- When reconstruction and exception set sizes are bounded by κ and q, respectively, the lemma gives a corresponding bound on the miss probability.The argument uses exchangeability and permutation equivariance; when the exception set is empty, it reduces to stable-compression logic discussed in the learning literature.Source: §3 · pp. 4–5
4 Forward bridge for discarded scenarios
The forward bridge applies the exchangeability argument to feasible sample-and-discard algorithms with stable retained reconstruction. It yields a mean-risk bound, and the fully supported convex case recovers the classical law; an order-statistic example links the result to split conformal calibration.
4 Forward bridge for discarded scenarios
- The forward bridge bounds mean violation for feasible sample-and-discard algorithms under the stable retained reconstruction assumption; in the fully supported convex case it recovers (r + d)/(m + 1).The proof treats a fresh violating scenario as either discarded or decision-shaping.Source: §4 · p. 5
- The result is a conformal-style derivation for sample discarding, not a sharper numerical bound; discarded samples act as admissible exceptions in the exchangeability argument.This interpretation connects scenario methods in control with compression and sample-and-remove scenario MPC formulations.Source: §4 · p. 6
- In the one-dimensional example, discarding r observations gives the order-statistic predictor Γr(S) = (−∞, qr(S)], with Vr(S) distributed as Beta(r + 1, m −r).The example states that equality holds in the bound and identifies the law as the one underlying one-sided split-conformal calibration.Source: §4 · p. 6
5 A modular rule for multi-output and multi-stage risk allocation
The modular rule combines blockwise calibration certificates into a joint guarantee through a union bound, without requiring independence across blocks. Under coordinate independence, multiplicative bounds can be tighter than additive bounds, while the control example allocates risk across prediction steps.
5 A modular rule for multi-output and multi-stage risk allocation
- The modular rule intersects block predictors to combine blockwise calibration certificates into a joint guarantee without requiring independence across blocks.The composition uses a union bound and allows risk budgeting across coordinates, subsystems, or time steps.Source: §5 · pp. 6–7
5.1 Sharper bounds under coordinate independence
- Under mutual independence across test and calibration coordinates, multiplicative risk and confidence bounds are tighter than their additive counterparts.This tighter formulation is reserved for applications where coordinate independence can be reliably verified.Source: §5.1 · p. 8
- Continuous scalar scores can use the same order-statistic calibration mechanism; in control, a natural choice is the absolute prediction residual at each horizon step.The resulting blockwise predictors have explicit calibration-conditional certificates that can be combined into a joint guarantee.Source: §5.1 · pp. 8–9
- For an identified predictor, calibrated horizon-wise residual margins form an output tube that tightens scalar upper-output constraints and distributes risk across prediction steps.The total risk budget is allocated through the choices of ϵ_k and δ_k.Source: §5.1 · pp. 8–9
- These conditional certificates are not generic guarantees based only on observed support size; each block uses an explicit conditional law inherited from an order-statistic score.The cited discussion distinguishes this construction from generic conditional claims that require additional information.Source: §5.1 · p. 9
6 Numerical illustrations
The illustrations show that equal overall risk budgets can produce different stage-wise margins, trajectory risks, and control trade-offs. Under independent horizon errors, the multiplicative rule also permits a tighter tube at the same trajectory-level budget.
6 Numerical illustrations
- The illustrations use a four-step calibrated tube around an identified linear surrogate, with 120 independent calibration tasks and 1,000 calibration sets per allocation.Each calibration set's stage-wise and joint risks were approximated using 5,000 fresh test tasks.Source: §6.1 · pp. 9–10, §6 · p. 9
6.1 Risk allocation across the prediction horizon
- Across allocations, mean trajectory risk stays close to 0.06 while margins and empirical stage-wise risks shift across steps; increasing-risk gives smaller later margins.Figure 1 plots mean tube half-widths and empirical stage-wise risks; all three allocations use the same total risk budget and rank sum.Source: §6.1 · p. 10, Figure 1 · p. 11, Table 1 · p. 11
Evaluating the Multiplicative Savings under Independence
- With independent horizon errors, the multiplicative rule reduces the certified trajectory-risk upper bound by about 1.74% without changing the tube, or permits ϵk≈0.061 instead of 0.055 at budget 0.22.The larger stage-wise allowance can permit more discards or smaller order statistics, producing a tighter tube while maintaining the same trajectory-level certificate.Source: Evaluating the Multiplicative Savings… · p. 10
6.2 From calibrated tubes to constraint tightening
- Increasing-risk yields mean admissible input 0.3491 and mean violation probability 0.0174; decreasing-risk yields 0.2373 and 0.0025, with uniform allocation between.The increasing-risk allocation also has mean terminal output 0.4190. Figure 2 depicts one such tightened tube alongside the nominal trajectory, true plant trajectories, and output limit.Source: §6.2 · p. 11, Table 2 · p. 12, Figure 2 · p. 12
7 Conclusions
The paper establishes a forward bridge for feasible sample-and-discard algorithms under a stable retained reconstruction set, and introduces modular composition of blockwise calibration certificates. Its illustrations show that stage-wise risk allocations can change calibrated tubes and control trade-offs, while the guarantees remain subject to stated limitations.
7 Conclusions
- Under a stable retained reconstruction set, the forward bridge gives a mean-risk bound in terms of discarded and reconstruction samples, recovering the (r + d)/(m + 1) law for the fully supported convex case.The bound is an expectation bound, not a general sharp arbitrary-r PAC tail law.Source: §7 · p. 12
- Different stage-wise allocations of the same total risk budget produce different calibrated tubes, constraint tightenings, and performance-safety trade-offs in a planning problem.The modular rule combines blockwise certificates into explicit risk allocation across outputs, constraints, or prediction steps.Source: §7 · p. 12
- The modular composition rule relies on a union bound, and the forward bridge does not provide a general sharp arbitrary-r PAC tail law.Future directions include sharper joint constructions that exploit dependence across blocks and closed-loop extensions linking calibration, prediction, and control over time.Source: §7 · pp. 12–13