Exact Multiple-Risk Control Requires Randomization: Fractional Safe Certification and a Sharp Deterministic–Randomized Separation

Jeff Pickhardt

Loading document…

Exact Multiple-Risk Control Requires Randomization: Fractional Safe Certification and a Sharp Deterministic–Randomized Separation

Abstract

We study finite-sample distribution-free control of several expected losses produced by a common data-dependent policy, and establish a matched possibility and impossibility. On the possibility side we give fractional safe certification: a candidate policy learned on one sample is evaluated on an independent certification sample and mixed with an exactly safe policy through a closed-form deployment probability. Under exchangeability the resulting randomized policy controls every bounded expected test loss at its prescribed level in finite samples, with no conservative slack and no Bonferroni division of the budgets, so risk multiplicity is free. The principle is graph agnostic; specialized to threshold selection on a directed acyclic graph with possibly non-monotone graph-triggered losses, it yields an oracle inequality against the best feasible deterministic graph-threshold policy, with explicit dependence on sample size, the number of risks, budgets, and ancestral threshold complexity. On the impossibility side the randomization is substantive rather than cosmetic: exact control at an active boundary requires it, already for a single risk. On an atomic one-node instance we characterize every permutation-invariant randomized rule valid for all exchangeable laws and show that fractional safe deployment is pointwise maximal; every valid deterministic symmetric rule then has asymptotic objective regret at least 1/2 at the boundary, whereas the optimal randomized regret decays as n−1/2, a sharp deterministic–randomized separation. Atomlessness, population slack, approximate validity, non-symmetric use of sample order, or monotone structure can each relax the obstruction. Safe-reference regulation and randomized exact inference are established ideas; the contributions here are the vector-risk certificate, this separation, and the graph-threshold oracle analysis of the certificate.

File Details

v1 paper.pdf