PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Giuseppe C. Calafiore

arXiv:2609.01355v1eess.SYcs.LGmath.OC

TL;DR

Classical beta risk laws arise in several distribution-free methods, but random observed boundary sizes create a gap when complexity is treated as fixed. The paper formalizes proper projective boundary schemes and derives an exact profile-based conditional law, recovering the beta law under profile stability and showing that observed complexity alone is insufficient for nontrivial conditional guarantees.

  • Problem

    Existing beta-law formulas do not by themselves determine conditional risk for procedures with random boundary size, and observed complexity alone is insufficient for nontrivial distribution-free conditional guarantees.

  • Method

    The paper represents each rule by an acceptance set and boundary map, then uses proper projectivity to characterize conditional risk through the cross-sample complexity profile.

  • Results

    A stable profile yields Beta(k, N−k+1), while varying profiles require an exact correction; the framework covers scenario, conformal, coordinatewise-envelope, and Pareto-frontier procedures.

  • Takeaways & Limitations

    Sharp conditional certification requires profile information that can be analytic, structurally bounded, or simulator-estimated; treating random complexity as fixed can misassess risk.

  • Takeaways & Limitations

    The framework distinguishes genuine mathematical boundaries from implementation-reported sets, which may contain a proper boundary without satisfying the defining assumptions.

Abstract

from arXiv · show

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.

1 Introduction

The paper studies exact finite-sample laws for conditional violation risk and identifies deterministic boundary structure as the mechanism behind classical beta formulas. It extends the analysis to random boundary sizes through a cross-sample complexity profile.

  • Motivation: Finite samples construct acceptance sets for future observations, with conditional violation risk as the central performance quantity.Scenario optimization and conformal prediction provide motivating examples.
  • Common mechanism: A deterministic boundary property, rather than convexity, scalar scoring, or observed support size alone, explains the shared beta-law mechanism.A new observation is rejected exactly when it would become decision-determining after augmentation.
  • Framework: A proper projective boundary scheme combines an acceptance rule with a boundary map satisfying held-out acceptance and deletion-invariance conditions.These abstract conditions cover convex and nonconvex optimization settings and applications outside optimization.
  • Main result: A stable complexity profile yields Beta(k, N−k+1) conditional risk, whereas profile variation makes the usual beta law generally incorrect.The conditional law is determined by the cross-sample profile {p_n(k)}.
  • Implications: The framework provides profile-corrected laws, conditional certificates, and a no-go result showing that observed complexity alone cannot support nontrivial conditional guarantees.Profiles may be computed analytically, bounded structurally, or estimated using simultaneous finite-sample bands.

3 Proper Projective Boundaries

The paper formalizes boundaries as permutation-equivariant subsets of samples and defines proper projective schemes through boundary equivalence and projectivity. Its exact law expresses conditional risk through the complexity profile, recovering beta laws under stability or fixed size.

  • Boundary concepts: A boundary map selects decision-determining sample indices, and its complexity is the boundary cardinality K_n.The construction is deterministic for each finite sample; randomness enters when applied to i.i.d. data.
  • Boundary equivalence: Boundary equivalence means held-out samples are accepted exactly when none is needed in the full-sample boundary.A held-out violation is precisely a point that would enter that boundary.
  • Projectivity: Projectivity requires that deleting accepted non-boundary samples leaves the boundary unchanged, excluding artificial complexity from irrelevant samples.A proper projective boundary scheme satisfies both assumptions.
  • Exact law: The exact conditional risk law is determined by the cross-sample complexity profile, with uniqueness following from Hausdorff moment determinacy.The profile must satisfy positivity and complete-monotonicity constraints to represent an admissible law.

5 Verifying the Boundary Assumptions

The paper verifies proper projective boundaries across order-statistic, scenario, coordinatewise-envelope, and Pareto-frontier procedures. Deterministic boundary sizes recover classical laws, while random boundaries require profile-based corrections.

  • Order-statistic calibration: Order-statistic calibration forms a proper projective boundary scheme with deterministic boundary size s.The boundary consists of the top s scores, recovering scalar split-conformal calibration after suitable discarding.
  • Scenario programs: Support-reconstructive scenario programs form proper projective boundaries when confirmed-addition stability and reconstruction hold.With deterministic support size, the exact scenario law is recovered; random support size is governed by the profile ratio.
  • Coordinatewise envelope: The coordinatewise envelope has boundary size 1 or 2, depending on whether one sample maximizes both coordinates.Under independent uniform coordinates, its risk is represented by a product of two independent Beta(N,1) variables rather than a fixed boundary dimension.
  • Pareto-frontier calibration: The Pareto-frontier rule is proper and projective, with nondominated calibration scores exactly reconstructing the acceptance set.In two dimensions with uniform scores, the frontier profile is c(n,k)/n!, where c(n,k) is an unsigned Stirling number of the first kind.
  • Profile correction: For the Pareto frontier, the beta mean k/(N+1) is valid only when the profile ratio p_N+1(k)/p_N(k) equals one.The profile correction can therefore change conditional means relative to the beta benchmark.

6 PAC Certificates from the Exact Law

The exact law can be inverted into conditional PAC certificates, with the required profile supplied exactly, bounded structurally, or estimated through validated simulation.

  • The exact law yields a conditional PAC certificate by inverting the conditional distribution.
  • When the complexity profile is unknown, certified families of admissible profiles support robust conditional certificates.
  • Observed boundary size alone cannot provide a nontrivial distribution-free conditional guarantee without prior or auxiliary profile information.
  • Analytic profiles: Analytic profiles can produce exact finite-sample certificates without simulation, including deterministic-size and explicit record-profile cases.
  • Structural profile classes: Structural profile classes convert deterministic constraints into conservative robust quantiles and conditional PAC certificates.
  • Simulation-certified profiles: Simulation-certified profiles use simultaneous binomial bands and admissibility constraints, while approximate simulators transfer their approximation into the profile calculation.

7 About Discarded Samples

Discarded samples support the sharp boundary law only when they form an essential proper projective boundary; arbitrary reported or violated discards require safer alternatives.

  • Theorem 4.1 permits discarded samples when they are true boundary samples, distinguishing essential projective discards from generic violated constraints.
  • Cascaded support removal: Cascaded support removal recovers a no-prefactor beta-type law when the reproducible boundary is essential and projective.
  • Cascaded support removal: In the fully supported case, the boundary combines r discarded support constraints with d final support constraints, giving size r + d.
  • Cascaded support removal: Under non-atomicity, the no-prefactor feasibility guarantee extends to the final optimizer, with equality under the additional tightness assumption.
  • Order-statistic discarding: Scalar conformal prediction with r discarded upper-tail scores forms a fixed boundary of size r + 1 and retains an exact law.
  • Reported versus mathematical boundaries: A reported set may contain superfluous samples and need not satisfy boundary assumptions, so it is safe primarily as an upper bound on genuine boundary size.
  • Reported versus mathematical boundaries: If violated or nonprojective discards are treated as boundary samples, the exact theorem does not apply; specialized discarding, stable-compression, or inner-certificate methods are needed.

8 A Stable-Compression Fallback

Stable compression supplies a fallback PAC bound when retained discard or exception samples reconstruct the decision but do not form a proper projective boundary.

  • Stable compression requires that deleting samples outside the compression and discard sets leave the reconstructed decision unchanged.
  • The stable-compression PAC theorem provides a distribution-free high-probability bound for every distribution, sample size, and confidence level.
  • The fallback is usually looser than the exact profile law but remains valid for stable compression elements that are not proper boundary elements.

9 A Multi-Risk Extension

The multi-risk extension combines independent component boundaries through a vector complexity profile, yielding joint mixed moments and non-Bonferroni certificates when projectivity holds.

  • The extension treats multiple independent risk components with separate sample sizes, distributions, acceptance sets, and boundary maps.
  • The multi-risk boundary condition equates acceptance of all held-out samples with retention of every component boundary.
  • Theorem 9.2 gives a joint profile law for the vector of component complexities and fresh-sample counts.
  • Dedicated reserve sizing: For dedicated reserve regions, retaining each block maximum is sufficient because deleting accepted nonmaximal demands cannot change the component threshold.
  • With stable profiles, component risks are conditionally independent beta variables, including a point mass at zero when k_h = 0.
  • A shared reserve can invalidate componentwise boundary equivalence because individual maxima may not characterize the coupled decision.
  • When profiles vary, the ratio p_N+M(k)/p_N(k) carries dependence information and can support non-Bonferroni certificates.

10 No-Go Results

The no-go results show that observed boundary complexity alone cannot support a universal nontrivial conditional risk guarantee. Valid conditional laws require structural assumptions such as proper projectivity and profile information.

  • Nominal boundaries are insufficient: A nominal two-point boundary does not ensure the s = 2 beta upper bound, even for a permutation-invariant, empirically consistent algorithm.The largest-gap construction on the unit circle violates boundary projectivity because adding an accepted point can split the largest gap.
  • Nominal boundaries are insufficient: Boundary projectivity fails when adding an accepted point can change the decision by splitting the largest circular gap.In the construction, the violation probability is the length of the largest gap, which is almost surely greater than 1/N.
  • Complexity alone: No distribution-free conditional theorem based only on K_N = k can guarantee a nontrivial upper bound uniformly over empirically consistent sample-compressed algorithms.The no-go theorem implies that any universally valid bound u_N(k, beta) must equal 1 for every beta < 1.
  • Complexity alone: A nontrivial conditional certificate based on observed complexity requires structural assumptions, profile information, or both.The counterexample construction uses positive-probability conditioning events and encodes decisions through selected order statistics.

11 Numerical Illustrations

The numerical illustrations compare exact profile-based risk laws with fixed-complexity beta substitutes in random-boundary procedures. Coordinatewise envelopes and Pareto-frontier calibration show that treating random boundary size as fixed can misstate conditional risk.

  • 11.1 A Random-Support Scenario Envelope: The coordinatewise envelope has an exact conditional tail that differs from beta tails obtained by treating random support size as fixed.For 0 <= epsilon < 1, the tail is (1 - epsilon)^N {1 - N log(1 - epsilon)} for both K_N = 1 and K_N = 2.
  • 11.1 A Random-Support Scenario Envelope: For N = 20, fixed-dimension beta means are 1/21 = 0.04762 for k = 1 and 2/21 = 0.09524 for k = 2.These values are compared against the exact conditional means in Figure 1.
  • 11.2 Pareto-Frontier Vector-Score Calibration: The two-dimensional Pareto-frontier size follows the record profile p_n(k) = c(n,k)/n!, rather than a fixed-complexity law.For N = 20, the beta mean is smaller for small observed frontiers and larger for large observed frontiers; neither direction is uniformly safe.
  • 11.2 Pareto-Frontier Vector-Score Calibration: The experiments confirm that exact beta laws require stable complexity profiles, while random-boundary procedures require the cross-sample profile.The conclusion applies to coordinatewise scenario envelopes and Pareto-frontier calibration with vector scores.
  • 11.2 Pareto-Frontier Vector-Score Calibration: The Pareto-frontier rule uses nondominated calibration scores as boundary samples defining a lower-orthant staircase acceptance boundary.A new score vector is rejected when it lies above the staircase and would become a new maximal sample after augmentation.
  • 11.2 Pareto-Frontier Vector-Score Calibration: For K_20 = 3, the fixed-boundary beta comparator is visibly shifted left and gives a smaller 95% quantile than the Monte Carlo conditional CDF.The beta quantile is included only as a comparator, not as the projective-profile law.

A Proof of the Bounded-Boundary Corollary

The proof pads a boundary whose size is at most s with auxiliary-marked non-boundary points, constructs a conservative proper projective scheme, and applies the fixed-size beta law.

  • Padding construction: The padded boundary adds the s−b_n largest auxiliary marks when the original boundary has size b_n≤s, producing size s almost surely for n≥s.Independent uniform marks are used, and ties occur with probability zero.
  • Padding construction: The padded acceptance rule tightens the original rule using a threshold among retained non-boundary auxiliary marks, while handling samples smaller than s separately.It is empty below size s and otherwise uses Γ(T_I)×[0,1] when the original boundary exceeds s.
  • Projectivity verification: Boundary equivalence follows because acceptance of all held-out extended points is equivalent to retaining the original boundary and the selected auxiliary points.The key equivalence is R⊆I if and only if every omitted non-boundary point has an auxiliary mark below the retained threshold.
  • Projectivity verification: The padded scheme is proper and projective, since retaining its boundary preserves both the original boundary and the selected auxiliary marks after re-indexing.This verification is carried out on the full-measure event where auxiliary marks are distinct.
  • Risk law: For N≥s, the padded violation risk follows Beta(s, N−s+1), yielding the corresponding beta-binomial tail identity.The original rule is pointwise no less conservative than the padded rule, so the padded law supplies a conservative certificate.
  • Application: The same boundary mechanism places cascaded support-removal constructions within the projective-boundary framework and transfers fixed-boundary risk bounds to their final optimizers.The appendix identifies this as a route to the no-prefactor formula and an upper bound for the final optimizer.

B.1 The Cascade

The cascade repeatedly removes stagewise support constraints, forming a fixed-size compression boundary for a certified acceptance set under feasibility, unique selection, and full support.

  • B.1 The Cascade: In the fully supported case, each stage support set has cardinality d, so the cascaded support set has the prescribed fixed size ζ=r+d.Here r=ℓd.
  • B.1 The Cascade: At each stage, the cascade solves a scenario program, records its support set, and removes that support set until the final stage.The final support set is retained rather than removed.
  • B.1 The Cascade: The compression proof introduces a certified acceptance set that includes the final optimizer’s feasible set and adds back finitely many scenarios removed during the cascade.The set A_3(C) contains those removed scenarios, while A_1(C) is the final optimizer’s feasible set.
  • B.1 The Cascade: The certified set can be smaller than A_1(C), so its violation probability can be larger than that of the final optimizer while still providing a valid upper bound.This distinction explains why the compression certificate transfers conservatively to the optimizer.
  • B.1 The Cascade: An additional tightness assumption requires every support scenario to be violated by every optimizer obtainable after deleting it from the remaining constraints.This assumption supports the exact tightness result associated with the larger acceptance set.
  • B.1 The Cascade: Unique compression and consistency imply proper projectivity: the selected ζ-point compression set remains unchanged whenever all omitted points are accepted.Lemma B.1 establishes this through boundary equivalence and projectivity for fixed-size compression schemes.

B.3 Application to the Romao–Papachristodoulou–Margellos Cascade

The Romao–Papachristodoulou–Margellos cascade becomes a proper projective boundary of size r+d, recovering beta-law feasibility bounds and, under tightness, the final optimizer’s risk law.

  • B.3 Application to the Romao–Papachristodoulou–Margellos Cascade: Under feasibility, unique selection, and full support, the cascaded support set is the unique compression set of size ζ=(ℓ+1)d for the certified acceptance map.This identifies the cascade’s compression representation with the framework’s fixed-size boundary.
  • B.3 Application to the Romao–Papachristodoulou–Margellos Cascade: The cascaded support set is a proper projective boundary of fixed size ζ=r+d, so the fixed-boundary theorem yields its beta law and beta-binomial tail.This recovers the feasibility bound reported for the cascade.
  • B.3 Application to the Romao–Papachristodoulou–Margellos Cascade: Under a non-atomic scenario law, the finite correction set A_3(C) has probability zero, equating the certified set’s risk with the final optimizer’s violation risk.The certified set has no larger acceptance probability than the final optimizer’s feasible set, so its risk is no smaller before the zero-probability reduction.
  • B.3 Application to the Romao–Papachristodoulou–Margellos Cascade: With the additional tightness assumption, the larger acceptance set A also has a proper projective boundary and its risk equals the usual scenario violation risk.The resulting formula provides the exact equality statement associated with the tightness theorem.
  • B.3 Application to the Romao–Papachristodoulou–Margellos Cascade: Primitive conditions such as confirmed-addition stability, boundary reconstruction, outside-boundary feasibility, and minimality suffice for boundary equivalence.These conditions provide a deterministic route to verifying the projective-boundary property.
  • B.3 Application to the Romao–Papachristodoulou–Margellos Cascade: When an algorithm falls outside the framework, a fixed-size certified inner set can still yield a proper inner certificate and a conservative beta-law bound.This supplies an alternative certification route rather than asserting projectivity for the original reported rule.
Loading 2609.01355v1…