Keywords: e-values, conformal risk control, false discovery rate, multiple testing, exchangeability, admissibility.
Introduction
Many statistical procedures turn data into an informed action, while guaranteeing that some expected loss stays below a prescribed level. Statistical decision theory formalizes this task through a decision rule mapping data to actions, a loss depending on the action and an unknown state of nature, and the resulting statewise expected loss, or risk [43 , 9 ] . The bound imposes a risk budget that must hold in every state. Among rules satisfying this constraint, one seeks the most useful decisions, as in the constrained problems of [22 ] .
Multiple testing is a decision problem of exactly this kind. With K K K hypotheses, the action is a rejection set R ⊆ [ K ] R\subseteq[K] R ⊆ [ K ] , so the action space is the collection 2 [ K ] 2^{[K]} 2 [ K ] of all subsets of [ K ] [K] [ K ] , and the unknown state is the set T ⊆ [ K ] T\subseteq[K] T ⊆ [ K ] of true null hypotheses. The false discovery proportion ∣ T ∩ R ∣ / ( ∣ R ∣ ∨ 1 ) |T\cap R|/(|R|\vee1) ∣ T ∩ R ∣/ ( ∣ R ∣ ∨ 1 ) is the loss, and false discovery rate (FDR) control bounds its expectation by α \alpha α . The procedure of [8 ] achieves this by comparing the ordered p-values with linearly increasing thresholds; its e-value analogue, the e-BH procedure of [44 ] , applies the reciprocal thresholds to e-values, which are nonnegative statistics with expectation at most one under their null hypotheses [41 , 34 ] . The recent work of [47 ] introduces the e-closure principle, a general principle that uniformly improves many testing procedures based on e-values, including e-BH. Specifically, given an e-value E T E_T E T for each candidate true-null set T T T , valid when T T T is the set of true nulls, the principle certifies every rejection set R R R that satisfies
∣ T ∩ R ∣ ∣ R ∣ ∨ 1 ≤ α E T for every T ⊆ [ K ] . \begin{equation}
\frac{|T\cap R|}{|R|\vee1}\leq\alpha E_T\qquad\text{for every }T\subseteq[K]. \tag*{(1.1)}
\end{equation} ∣ R ∣ ∨ 1 ∣ T ∩ R ∣ ≤ α E T for every T ⊆ [ K ] . (1.1)
Under the actual null set, the left side is the false discovery proportion and the right side has expectation at most α \alpha α . The false discovery rate is therefore controlled even when the analyst chooses among the certified rejection sets after seeing the data. Conversely, [47 ] show that a procedure controls the false discovery rate simultaneously over the rejection sets it may report if and only if all of them are certified in this way by some family of e-values. The principle applies equally to other error rates that are expected losses, and it contains the classical closed testing principle for the familywise error rate [32 ] as the case of e-values taking only the values 0 0 0 and 1 / α 1/\alpha 1/ α .
Nothing in this argument depends on the actions being rejection sets. In a general decision problem, a state s s s specifies a class of distributions for the data X X X , an action a a a is chosen from an arbitrary set, and each of several losses L t ( s , a ; X ) L_t(s,a;X) L t ( s , a ; X ) , indexed by t t t , carries its own budget α t ( s ) \alpha_t(s) α t ( s ) . A family of e-values, one for each state and risk, certifies the actions whose losses fit within all the budgets it allows. Every data-dependent choice among the certified actions then controls every risk, and every procedure with this guarantee is certified by some such family [20 , 21 , 1 ] . In § 2 we review the e-closure principle at this level of generality, with menus of arbitrary actions, possibly continuously indexed states and risks, and losses that may depend on the data.
The correspondence can be read in both directions, and the direction from procedures to e-values suggests how to improve a procedure. Improving a decision rule directly is difficult: a more liberal rule may have higher power or utility, but it is rarely clear how far a given rule can be pushed before its guarantee fails. By contrast, improving an e-value is easier. If an e-value has expectation strictly below one, and the shortfall can be computed, for instance conditionally on a statistic whose conditional law is known under the null, then adding the shortfall back yields a larger e-value. Through the e-closure correspondence, larger e-values translate back into decisions. Starting from a valid procedure, we apply this construction to its canonical e-values: its losses divided by their risk budgets. Inverting the enlarged certificate yields a menu containing the original actions and potentially more liberal ones, all with the same guarantee. We call this step recertification. It generalizes the anchoring idea of [33 ] , which keeps an existing false discovery rate procedure and spends the slack in its validity proof, and it can be repeated.
We apply recertification to two problems. The first is conformal risk control (CRC) [3 ] , which extends conformal prediction from coverage to general monotone losses. Given n n n exchangeable calibration points and a known family of losses indexed by a conservativeness parameter λ \lambda λ , CRC selects the least conservative λ \lambda λ for which the calibration losses, together with a bound on the loss of the unseen test point, fit within the budget ( n + 1 ) α (n+1)\alpha ( n + 1 ) α . The selected controller typically leaves part of this budget unused. Recertification computes this unused budget on every such sample, redistributes it among the n + 1 n+1 n + 1 held-out positions, and inverts the resulting e-values. The new controller is valid under every finite exchangeable law, and for every calibration sample it is no more conservative than CRC. In this sense, for a fixed loss family and observation domain, it improves CRC uniformly. This recertification step can be repeated, with diminishing returns. For convex losses, the iterates converge geometrically to a controller that admits no further pointwise improvement, and on finite outcome spaces a coordinatewise sweep reaches such a controller without convexity (§ 3 ).
Figure 1. Risk-budget use and mean prediction-set size on CIFAR-100 with confidence-adaptive prediction rules (n = 50 n=50 n = 50 , α = 0.15 \alpha=0.15 α = 0.15 ). Round 0 0 0 is CRC, and later rounds apply recertification. Results are averaged over 300 paired splits, each with 16 test images.
Figure 1 illustrates these gains in hierarchical classification on CIFAR-100 (§ 3.6 ), using rules that give more specific predictions when the classifier is more confident. At a target of 15 % 15\% 15% , CRC attains a mean test risk of 14.21 % 14.21\% 14.21% . Repeated recertification raises it to 14.95 % 14.95\% 14.95% , close to the target, and reduces the mean prediction-set size from 10.77 10.77 10.77 to 8.92 8.92 8.92 labels, a reduction of 17.2 % 17.2\% 17.2% .
The second application returns to multiple testing. The e-BH procedure is valid under arbitrary dependence but can be conservative, and [45 ] showed that external randomization recovers part of the lost power. Their U-eBH procedure boosts the e-values by dividing them by a single uniform random variable and then applies e-BH. In this setting, we treat the conditional law of the rejection set given the e-values as a randomized action. In these terms, U-eBH is certified by the family of e-values behind e-BH, through a version of the self-consistency condition of [10 ] that holds on average over the randomization, and it typically leaves part of the budget allowed by this family unused. Recertification spends this budget and yields a closed-form randomized rule, recertified U-eBH (RU-eBH), which rejects at least as many hypotheses as U-eBH for every realization of the randomization and has the largest expected number of rejections among all randomized procedures certified by the same family.
The same principle applies to closed e-BH, the improvement of e-BH by e-closure [47 ] , whose family of e-values is larger because it adapts to the number of true nulls. Recertifying with this family gives a second closed-form rule, recertified closed e-BH (RC-eBH), whose rejection set contains that of RU-eBH and which has the largest expected number of rejections among all randomized procedures certified by this family, closed e-BH included (§ 4 ). In simulations, both rules are more powerful than e-BH and U-eBH in every setting, and RC-eBH is the most powerful of the eight procedures we compare in nearly every setting.
3.25ex -1em E-values and decisions. E-values have become a standard tool for testing and multiple testing [41 , 34 ] . Their link to decision making is developed by [21 ] , who allows the significance level and the loss to be chosen after seeing the data, and by [26 ] and [11 ] , who study post hoc testing and its admissible procedures. For a single risk, our certified menu is the set of actions whose e-posterior risk bound [20 ] , with each state’s loss divided by its budget, is at most one. [1 ] study decisions reported together with certificates of their loss, and [28 ] give evidence-weighted loss bounds for decisions based on conformal e-prediction sets. Decision-theoretic views of conformal prediction also study how prediction sets should inform downstream actions [31 , 25 ] . These works allow general states and actions; our focus is the constructive use of the correspondence, which keeps the error budget fixed and recertifies an existing procedure.
3.25ex -1em Closure principles. Closed testing [32 ] controls the familywise error rate, and every coherent procedure for that error rate is a closed testing procedure [36 ] . Closed testing also yields simultaneous bounds on the false discovery proportion of every rejection set [17 ] , and only closed testing procedures are admissible for that purpose [18 ] . E-closure [47 ] extends the closure principle to error rates defined by expected losses. Its follow-ups include the uniform improvement of the Benjamini–Hochberg procedure [16 ] , anchoring [33 ] , online versions [46 ] , and complete-class and admissibility results for e-value procedures [38 ] . We note that representation and admissibility are separate questions. Every valid procedure is certified by some family of e-values, while admissibility requires further conditions, and our admissibility results for CRC rely on the structure of that problem.
3.25ex -1em Randomized multiple testing. Randomization is classical in testing, where it makes tests based on discrete statistics exact [30 ] . For false discovery rate control with e-values under arbitrary dependence, [45 ] showed that stochastic rounding of the e-values and U-eBH increase the power of e-BH, and [47 ] combine stochastic rounding with e-closure. These methods randomize the e-values. Our procedures instead choose the distribution of the rejection set directly, subject either to per-hypothesis budgets that form a randomized version of the self-consistency condition of [10 ] or to the constraints that certify closed e-BH. Other uniform improvements of e-BH include its minimally adaptive version [23 ] , closed e-BH [47 ] , and conditional calibration [14 , 29 ] , which recalibrates the e-values given a sufficient statistic.
3.25ex -1em Conformal risk control. CRC already handles several, even infinitely many, risks that share a monotone action parameter [3 Section 4.3] . Risk-Controlling Prediction Sets (RCPS) and Learn then Test (LTT) instead provide high-probability statements about population risks [7 , 4 ] . Extensions of CRC treat non-exchangeable data [13 ] , cross-validation [12 ] , non-monotonic losses [2 ] , and end-to-end training [48 ] . The leave-one-out characterization of validity that we use (Lemma 3.1 ) is the risk-control counterpart of the universality of conformal prediction [42 Proposition 2.9] ; see also [39 ] , and [2 ] for its sufficiency direction. Conformal prediction with e-values is developed by [40 ] , [27 ] , [15 ] , and [28 ] . Apart from the sharper bound on the unseen test loss in envelope CRC [48 ] , which serves as our starting point, we are not aware of work on improving CRC controllers pointwise or on their admissibility. We use CRC to show concretely how large such improvements can be and what they cost in computation.
Organization
§ 2 formulates e-closure for general decision problems, including randomized actions, and introduces recertification. § 3 develops the improvement of CRC, including its admissibility theory, worked examples and a real-data study. § 4 returns to multiple testing, recertifies randomized e-BH with the e-collections of e-BH and closed e-BH, and reports simulations on Gaussian mean testing. § 5 comments on the choice among certified actions and concludes.
Generalized e-closure and recertification
This section sets up the decision framework used throughout the paper. We first describe states, actions and losses, then establish the correspondence between e-values and valid decisions, and finally introduce recertification, which turns this correspondence into a way of improving existing procedures.
States, actions, and a family of risks
Suppose that a statistician observes data X X X taking values in a space X \mathcal X X . The distribution of X X X is governed by an unknown state s ∈ S s\in\mathcal S s ∈ S , and each state specifies a nonempty class P s \mathcal P_s P s of distributions of X X X . After observing X X X , the statistician takes an action a ∈ A a\in\mathcal A a ∈ A , whose quality is measured by a family of known nonnegative losses
L t ( s , a ; x ) , t ∈ T . L_t(s,a;x),\qquad t\in\mathcal T. L t ( s , a ; x ) , t ∈ T .
The index t t t ranges over the kinds of error that the statistician wishes to control, such as several error rates or a continuum of loss functions, and each loss may depend on the observation x x x as well as on the state and the action. The sets S \mathcal S S , A \mathcal A A and T \mathcal T T are arbitrary and may be uncountable.
Each loss comes with a budget. Given fixed positive levels α t ( s ) \alpha_t(s) α t ( s ) , a decision rule A : X → A A:\mathcal X\to\mathcal A A : X → A is valid if
E P [ L t ( s , A ( X ) ; X ) ] ≤ α t ( s ) for every s ∈ S , P ∈ P s , t ∈ T . \begin{equation}
{\mathbb E}_P [L_t(s,A(X);X)] \leq\alpha_t(s)
\quad\text{for every }s\in\mathcal S,\ P\in\mathcal P_s,\ t\in\mathcal T. \tag*{(2.1)}
\end{equation} E P [ L t ( s , A ( X ) ; X )] ≤ α t ( s ) for every s ∈ S , P ∈ P s , t ∈ T . (2.1)
In words, whatever the state and whichever distribution within it generates the data, the expected loss of the selected action stays within its budget, separately for every loss in the family. The expectation is unconditional: it averages over the data and hence over the action that the rule selects. Throughout, we assume that all decision rules and all losses that we evaluate are measurable, and when we discuss sets of actions we also assume that their statewise loss envelopes, defined below, are measurable. Appendix § 6 gives sufficient conditions and discusses the uncountable intersections that arise.
Validity is certified by e-values. Recall that an e-value for a class of distributions is a nonnegative statistic whose expectation is at most one under every distribution in the class. Since (2.1) involves every state and every loss, we use one e-value for each such pair. An e-collection is a family of nonnegative measurable functions E s , t E_{s,t} E s , t satisfying
E P E s , t ( X ) ≤ 1 ( s ∈ S , P ∈ P s , t ∈ T ) . \begin{equation}
{\mathbb E}_P E_{s,t}(X)\leq1\qquad(s\in\mathcal S,\ P\in\mathcal P_s,\ t\in\mathcal T). \tag*{(2.2)}
\end{equation} E P E s , t ( X ) ≤ 1 ( s ∈ S , P ∈ P s , t ∈ T ) . (2.2)
In other words, an e-collection is a set of e-values, one for each combination of state and loss. Because an e-collection will be used to certify actions, we also refer to it as a certificate.
We now make precise the correspondence between e-collections and valid decisions described in the introduction. It is convenient to work with sets of actions rather than with single rules. A menu assigns to each observation x x x a nonempty set M ( x ) ⊆ A \mathcal M(x)\subseteq\mathcal A M ( x ) ⊆ A of actions that the statistician is prepared to take. After seeing the data, the statistician may choose any action from M ( X ) \mathcal M(X) M ( X ) , for instance by maximizing a utility or following a scientific preference. A decision rule is the special case of a menu with a single action at each observation. We first show how an e-collection produces a menu, then how a menu produces an e-collection, and finally that the two constructions are compatible.
3.25ex -1em From e-collections to menus. An e-collection certifies an action at the observation x x x when every loss of that action fits within its budget, scaled by the corresponding e-value. The certified menu of E E E is therefore
C α ( E ; x ) = { a ∈ A : L t ( s , a ; x ) ≤ α t ( s ) E s , t ( x ) ∀ s , t } . \begin{equation}
\mathcal C_\alpha(E;x)=\{a\in\mathcal A:L_t(s,a;x)\leq\alpha_t(s)E_{s,t}(x)\ \forall s,t\}. \tag*{(2.3)}
\end{equation} C α ( E ; x ) = { a ∈ A : L t ( s , a ; x ) ≤ α t ( s ) E s , t ( x ) ∀ s , t } . (2.3)
The constraint for state s s s caps the loss an action may incur if s s s is true, in proportion to E s , t ( x ) E_{s,t}(x) E s , t ( x ) . Intuitively, a large e-value indicates that the data are unlikely under s s s , so the menu may include actions that would perform poorly under s s s ; a small one restricts the menu to actions that perform well under s s s .
3.25ex -1em From menus to e-collections. Conversely, a menu determines the largest loss it can incur in each state. For a menu M \mathcal M M , define its loss envelopes and their normalized versions by
g s , t M ( x ) = sup a ∈ M ( x ) L t ( s , a ; x ) , E s , t M ( x ) = g s , t M ( x ) α t ( s ) . \begin{equation}
g_{s,t}^{\mathcal M}(x)=\sup_{a\in\mathcal M(x)}L_t(s,a;x),
\qquad E_{s,t}^{\mathcal M}(x)=\frac{g_{s,t}^{\mathcal M}(x)}{\alpha_t(s)}. \tag*{(2.4)}
\end{equation} g s , t M ( x ) = a ∈ M ( x ) sup L t ( s , a ; x ) , E s , t M ( x ) = α t ( s ) g s , t M ( x ) . (2.4)
The menu is valid if E P g s , t M ( X ) ≤ α t ( s ) {\mathbb E}_P\,g_{s,t}^{\mathcal M}(X)\leq\alpha_t(s) E P g s , t M ( X ) ≤ α t ( s ) for every s ∈ S s\in\mathcal S s ∈ S , P ∈ P s P\in\mathcal P_s P ∈ P s and t ∈ T t\in\mathcal T t ∈ T . This requires (2.1) to hold for every selection from the menu simultaneously, and it is equivalent to E M E^{\mathcal M} E M being an e-collection, which we call the canonical e-collection of M \mathcal M M . Applying the first construction to it gives the closure of M \mathcal M M ,
\begin{equation}
\overline\mathcal M(x)=\mathcal C_\alpha(E^{\mathcal M};x)=\{a:L_t(s,a;x)\leq g_{s,t}^{\mathcal M}(x)\ \forall s,t\}, \tag*{(2.5)}
\end{equation}
which consists of all actions whose losses never exceed those already incurred by the menu.
The following theorem, which we call generalized e-closure, states that the two constructions describe the same objects: certified menus are valid, and every valid menu is certified by its canonical e-collection.
Theorem 2.1. Let E E E be an e-collection. Every measurable selection A ( X ) ∈ C α ( E ; X ) A(X)\in\mathcal C_\alpha(E;X) A ( X ) ∈ C α ( E ; X ) satisfies (2.1) . More strongly, for every state–loss pair ( s , t ) (s,t) ( s , t ) and every P ∈ P s P\in\mathcal P_s P ∈ P s , E P [ sup a ∈ C α ( E ; X ) L t ( s , a ; X ) ] ≤ α t ( s ) .
{\mathbb E}_P\left[\sup_{a\in\mathcal C_\alpha(E;X)}L_t(s,a;X)\right]\leq\alpha_t(s).
E P [ sup a ∈ C α ( E ; X ) L t ( s , a ; X ) ] ≤ α t ( s ) . Further, a menu M \mathcal M M is valid if and only if M ⊆ C α ( E ) \mathcal M\subseteq\mathcal C_\alpha(E) M ⊆ C α ( E ) for some e-collection E E E . The loss closure (2.5) is extensive, monotone under inclusion of menus and idempotent, and it preserves every loss envelope. In particular, M = C α ( E ) ⟹ M = C α ( E M ) .
\mathcal M=\mathcal C_\alpha(E)\quad\Longrightarrow\quad\mathcal M=\mathcal C_\alpha(E^{\mathcal M}).
M = C α ( E ) ⟹ M = C α ( E M ) .
Proof. For every a ∈ C α ( E ; X ) a\in\mathcal C_\alpha(E;X) a ∈ C α ( E ; X ) , definition (2.3) gives L t ( s , a ; X ) ≤ α t ( s ) E s , t ( X ) L_t(s,a;X)\leq\alpha_t(s)E_{s,t}(X) L t ( s , a ; X ) ≤ α t ( s ) E s , t ( X ) , so the supremum in (2.6) is at most α t ( s ) E s , t ( X ) \alpha_t(s)E_{s,t}(X) α t ( s ) E s , t ( X ) . Taking expectations under P ∈ P s P\in\mathcal P_s P ∈ P s and using (2.2) proves (2.6) , and the validity of every measurable selection follows. If M ⊆ C α ( E ) \mathcal M\subseteq\mathcal C_\alpha(E) M ⊆ C α ( E ) , then g s , t M ≤ α t ( s ) E s , t g^{\mathcal M}_{s,t}\leq\alpha_t(s)E_{s,t} g s , t M ≤ α t ( s ) E s , t , so M \mathcal M M is valid. Conversely, if M \mathcal M M is valid, then E M E^{\mathcal M} E M is an e-collection, and every action in M ( x ) \mathcal M(x) M ( x ) satisfies the constraints defining C α ( E M ; x ) \mathcal C_\alpha(E^{\mathcal M};x) C α ( E M ; x ) , so \mathcal M\subseteq\overline\mathcal M . Every action in \overline\mathcal M(x) has losses at most g s , t M ( x ) g^{\mathcal M}_{s,t}(x) g s , t M ( x ) , so \overline\mathcal M has the same envelopes as M \mathcal M M ; idempotence follows, and monotonicity follows from the monotonicity of the envelopes. Finally, if M = C α ( E ) \mathcal M=\mathcal C_\alpha(E) M = C α ( E ) , then M ⊆ C α ( E M ) \mathcal M\subseteq\mathcal C_\alpha(E^{\mathcal M}) M ⊆ C α ( E M ) , and g s , t M ≤ α t ( s ) E s , t g^{\mathcal M}_{s,t}\leq\alpha_t(s)E_{s,t} g s , t M ≤ α t ( s ) E s , t gives the reverse inclusion C α ( E M ) ⊆ C α ( E ) = M \mathcal C_\alpha(E^{\mathcal M})\subseteq\mathcal C_\alpha(E)=\mathcal M C α ( E M ) ⊆ C α ( E ) = M . ◻
By (2.6) , the guarantee holds simultaneously over all actions in a certified menu. The statistician may therefore choose an action after seeing the data, for instance by maximizing a utility or applying a scientific filter, and every such choice from the menu of a fixed e-collection controls every risk. This is closely related to the post hoc validity of e-values in hypothesis testing, where the significance level, and more generally the loss, may be chosen after the data are observed [21 , 26 , 11 ] . We also note that the e-values may be arbitrarily dependent, because for each loss the proof uses only the corresponding e-value under the true state.
3.25ex -1em Multiple testing as a special case. The e-closure principle for multiple testing is recovered as follows. Take both the state space and the action space to be 2 [ K ] 2^{[K]} 2 [ K ] , let P T \mathcal P_T P T contain the distributions under which T T T is the set of true null hypotheses, and use the loss L ( T , R ) = ∣ T ∩ R ∣ / ( ∣ R ∣ ∨ 1 ) L(T,R)=|T\cap R|/(|R|\vee1) L ( T , R ) = ∣ T ∩ R ∣/ ( ∣ R ∣ ∨ 1 ) . The certified menu (2.3) then consists of the rejection sets certified by (1.1) , which is the e-closure principle for the false discovery rate [47 ] , and the loss L ( T , R ) = 1 { T ∩ R ≠ ∅ } L(T,R)=\mathop{\mathrm{\mathds{1}}}\{T\cap R\ne\varnothing\} L ( T , R ) = 1 { T ∩ R = ∅ } gives its familywise error rate version. E-values for intersection hypotheses, which are valid whenever T T T is contained in the set of true nulls, are in particular valid for the exact-state classes P T \mathcal P_T P T used here. § 4 reviews this setting in more detail. The general framework requires no structure on the actions, such as unions or an ordering, and no monotonicity of the losses. For instance, the false discovery proportion can decrease when a rejection is added.
3.25ex -1em Randomized actions. Actions may also be randomized. A randomized action is a probability measure Q Q Q on A \mathcal A A : once Q Q Q is chosen, an action is drawn from it using randomization independent of the data, and the loss of Q Q Q is the average L ˉ t ( s , Q ; x ) = ∫ L t ( s , a ; x ) Q ( d a ) \bar L_t(s,Q;x)=\int L_t(s,a;x)\,Q(da) L ˉ t ( s , Q ; x ) = ∫ L t ( s , a ; x ) Q ( d a ) . Probability measures on A \mathcal A A form an action space like any other, so Theorem 2.1 applies with these averaged losses. Every data-dependent choice of Q Q Q from the certified menu { Q : L ˉ t ( s , Q ; x ) ≤ α t ( s ) E s , t ( x ) ∀ s , t } \{Q:\bar L_t(s,Q;x)\leq\alpha_t(s)E_{s,t}(x)\ \forall s,t\} { Q : L ˉ t ( s , Q ; x ) ≤ α t ( s ) E s , t ( x ) ∀ s , t } is therefore valid, with a guarantee that averages over the subsequent draw; it does not cover choices made after the draw is seen. This menu can contain randomized actions whose possible realizations are not individually certified, so randomization can enlarge what a fixed e-collection certifies. § 4 uses this to improve randomized multiple testing.
Recertification: spending the unused budget
A valid menu can be enlarged in two ways, and the distinction between them is central to our approach. The first is closing, which adds every action whose losses lie beneath the current envelopes of the menu. By Theorem 2.1 , closing preserves every envelope: the closed menu offers more choice, which in multiple testing is the simultaneity gain described by [47 ] , but it uses exactly the budget that the original menu uses. Any budget that the original procedure leaves unused therefore remains unused after closing. The second way, which we call recertifying, first replaces the envelopes by larger ones that still respect the budgets and then closes with respect to the new envelopes. The recertified menu can therefore contain actions whose losses exceed those of every action in the original menu, and this is how recertification spends the unused budget.
To recertify, we need to quantify the budget that the baseline leaves unused. We do so conditionally on a statistic, chosen for each state–loss pair so that the required conditional expectations are known. When the unused budget can be computed without conditioning, the statistic is simply taken to be constant. Fix a valid baseline menu with envelopes g s , t g_{s,t} g s , t , and let V s , t V_{s,t} V s , t denote the conditioning statistic for the pair ( s , t ) (s,t) ( s , t ) . Suppose that known nonnegative functions H s , t H_{s,t} H s , t and B s , t B_{s,t} B s , t satisfy, for every P ∈ P s P\in\mathcal P_s P ∈ P s ,
E P [ g s , t ( X ) ∣ V s , t ] ≤ H s , t ( V s , t ) ≤ B s , t ( V s , t ) , E P B s , t ( V s , t ) ≤ α t ( s ) . \begin{equation}
{\mathbb E}_P[g_{s,t}(X)\mid V_{s,t}]\leq H_{s,t}(V_{s,t})\leq B_{s,t}(V_{s,t}),
\qquad {\mathbb E}_P B_{s,t}(V_{s,t})\leq\alpha_t(s). \tag*{(2.8)}
\end{equation} E P [ g s , t ( X ) ∣ V s , t ] ≤ H s , t ( V s , t ) ≤ B s , t ( V s , t ) , E P B s , t ( V s , t ) ≤ α t ( s ) . (2.8)
The function H s , t H_{s,t} H s , t bounds the conditional expected loss of the baseline, while B s , t B_{s,t} B s , t is a conditional budget whose expectation does not exceed the original level. Their difference B s , t − H s , t B_{s,t}-H_{s,t} B s , t − H s , t is therefore an allowance that the baseline leaves unused, conditionally on V s , t V_{s,t} V s , t . The following proposition shows that any nonnegative increment within this allowance can be added to the envelopes.
Proposition 2.2 (Conditional recertification). If measurable functions W s , t ( X ) ≥ 0 W_{s,t}(X)\geq0 W s , t ( X ) ≥ 0 satisfy
E P [ W s , t ( X ) ∣ V s , t ] ≤ B s , t ( V s , t ) − H s , t ( V s , t ) ( P ∈ P s ) , \begin{equation}
{\mathbb E}_P[W_{s,t}(X)\mid V_{s,t}]\leq B_{s,t}(V_{s,t})-H_{s,t}(V_{s,t})
\quad(P\in\mathcal P_s), \tag*{(2.9)}
\end{equation} E P [ W s , t ( X ) ∣ V s , t ] ≤ B s , t ( V s , t ) − H s , t ( V s , t ) ( P ∈ P s ) , (2.9) then ( g s , t + W s , t ) / α t ( s ) (g_{s,t}+W_{s,t})/\alpha_t(s) ( g s , t + W s , t ) / α t ( s ) is an e-collection. Its certified menu contains the original menu and every action whose losses are at most g s , t + W s , t g_{s,t}+W_{s,t} g s , t + W s , t for all s s s and t t t .
Proof. Conditionally on V s , t V_{s,t} V s , t , the expectation of g s , t + W s , t g_{s,t}+W_{s,t} g s , t + W s , t is at most H s , t + ( B s , t − H s , t ) = B s , t H_{s,t}+(B_{s,t}-H_{s,t})=B_{s,t} H s , t + ( B s , t − H s , t ) = B s , t . Taking expectations once more, the unconditional expectation is at most α t ( s ) \alpha_t(s) α t ( s ) . The two inclusions follow from W s , t ≥ 0 W_{s,t}\geq0 W s , t ≥ 0 and from the definition (2.3) of the certified menu. ◻
The increments W s , t W_{s,t} W s , t may depend on the data in an arbitrary way; only their conditional expectations are constrained by (2.9) . How the allowance is computed depends on the problem. In CRC (§ 3 ), the state is a hypothetical augmented sample whose law is known by exchangeability, so no further conditioning is needed, and the allowance is shared equally among the held-out points. For randomized e-BH (§ 4 ), the input e-values supply the budget directly, and conditional on the e-values, the averaged losses are known because the law of the external randomization is known. Proposition 2.2 also describes an existing method, the conditional calibration of e-values [14 , 29 ] , which improves e-BH by recalibrating each e-value given a sufficient statistic; there the sufficient statistic provides the conditional expectations (Remark 4.3 ). Finally, the recertified e-collection is again an e-collection, so its certified menu is valid by Theorem 2.1 and can serve as the baseline for another round of recertification.
Improving conformal risk control
We now apply the framework of § 2 to conformal risk control. § 3.1 sets up the problem and two baseline procedures, and § 3.2 characterizes validity exactly through the losses on hypothetical augmented samples. This characterization exposes the budget that a controller leaves unused, which recertification spends in § 3.3 . Repeating the step leads to admissible controllers, which we illustrate on a small example (§ 3.4 ). § 3.5 extends the construction to multiple risks, nonconvex losses and test features, and discusses computation, and § 3.6 reports a real-data study on hierarchical image classification.
Setup and two valid starting rules
Conformal risk control [3 ] calibrates a family of actions so that a prescribed expected loss is controlled at a new test point. The actions are indexed by a parameter λ \lambda λ in a finite ordered grid or a compact interval Λ = [ λ − , λ + ] \Lambda=[\lambda_-,\lambda_+] Λ = [ λ − , λ + ] , where larger values are more conservative. For example, λ \lambda λ may be a threshold that determines a prediction set, with larger λ \lambda λ giving larger sets. The quality of action λ \lambda λ on an observation z ∈ Z z\in\mathcal Z z ∈ Z is measured by a known loss ℓ ( z , λ ) \ell(z,\lambda) ℓ ( z , λ ) , such as the indicator that the prediction set misses the label, or the fraction of true labels that it misses. Following the original work, we assume that
0 ≤ ℓ ( z , λ ) ≤ B , ℓ ( z , λ ) is non-increasing and right-continuous in λ , ℓ ( z , λ + ) ≤ α , \begin{equation}
0\leq\ell(z,\lambda)\leq B,\qquad
\ell(z,\lambda)\text{ is non-increasing and right-continuous in }\lambda,
\qquad \ell(z,\lambda_+)\leq\alpha, \tag*{(3.1)}
\end{equation} 0 ≤ ℓ ( z , λ ) ≤ B , ℓ ( z , λ ) is non-increasing and right-continuous in λ , ℓ ( z , λ + ) ≤ α , (3.1)
where 0 < α < B 0<\alpha<B 0 < α < B is the target level. Thus the losses are bounded, a more conservative action never incurs a larger loss, and the most conservative action always meets the target.
We observe calibration data D = ( Z 1 , … , Z n ) D=(Z_1,\ldots,Z_n) D = ( Z 1 , … , Z n ) and must choose an action for a test observation Z n + 1 Z_{n+1} Z n + 1 , whose loss we cannot see. We assume only that ( Z 1 , … , Z n + 1 ) (Z_1,\ldots,Z_{n+1}) ( Z 1 , … , Z n + 1 ) is exchangeable; if the loss involves a trained prediction model, the model is held fixed, and exchangeability is assumed conditionally on its training data. The goal is a data-dependent action A ( D ) ∈ Λ A(D)\in\Lambda A ( D ) ∈ Λ satisfying
E ℓ ( Z n + 1 , A ( D ) ) ≤ α {\mathbb E}\,\ell(Z_{n+1},A(D))\leq\alpha E ℓ ( Z n + 1 , A ( D )) ≤ α
under every finite exchangeable law on Z n + 1 \mathcal Z^{n+1} Z n + 1 , and, subject to this constraint, as liberal as possible. We call such a rule A A A a controller. The observation space and the loss family are fixed throughout, and controllers are always compared for the same observation space and loss family.
Standard CRC bounds the unobserved test loss by B B B and selects the smallest λ \lambda λ for which the calibration losses, together with this bound, fit within the budget ( n + 1 ) α (n+1)\alpha ( n + 1 ) α :
A C R C ( D ) = min { λ : ∑ i = 1 n ℓ ( Z i , λ ) + B ≤ ( n + 1 ) α } . \begin{equation}
A_{\mathrm{CRC}}(D)=\min\left\{\lambda:\sum_{i=1}^n\ell(Z_i,\lambda)+B\leq (n+1)\alpha\right\}. \tag*{(3.2)}
\end{equation} A CRC ( D ) = min { λ : i = 1 ∑ n ℓ ( Z i , λ ) + B ≤ ( n + 1 ) α } . (3.2)
The bound B B B is the same for every λ \lambda λ , whereas the loss that the test point can incur at a given λ \lambda λ may be much smaller, particularly for conservative actions. [48 ] therefore allow the bound to depend on λ \lambda λ . Given a known non-increasing, right-continuous envelope U U U with
sup z ∈ Z ℓ ( z , λ ) ≤ U ( λ ) ≤ B , \sup_{z\in\mathcal Z}\ell(z,\lambda)\leq U(\lambda)\leq B, z ∈ Z sup ℓ ( z , λ ) ≤ U ( λ ) ≤ B ,
envelope CRC selects
A e n v ( D ) = min { λ : ∑ i = 1 n ℓ ( Z i , λ ) + U ( λ ) ≤ ( n + 1 ) α } . \begin{equation}
A_{\mathrm{env}}(D)=\min\left\{\lambda:\sum_{i=1}^n\ell(Z_i,\lambda)+U(\lambda)\leq (n+1)\alpha\right\}. \tag*{(3.3)}
\end{equation} A env ( D ) = min { λ : i = 1 ∑ n ℓ ( Z i , λ ) + U ( λ ) ≤ ( n + 1 ) α } . (3.3)
In both rules, the safe endpoint λ + \lambda_+ λ + is used if the displayed set is empty. Both rules are valid [3 , 48 ] , and U ≤ B U\leq B U ≤ B gives A e n v ≤ A C R C A_{\mathrm{env}}\leq A_{\mathrm{CRC}} A env ≤ A CRC pointwise. The construction below improves any valid controller, envelope CRC included, and since the goal is an expected-loss bound, it fits the framework of § 2 : the e-values that certify a controller show where it can be improved.
The exact risk budget on a hypothetical augmented sample
Validity under exchangeability can be checked one augmented sample at a time. For an augmented multiset S = ( z 1 , … , z n + 1 ) S=(z_1,\ldots,z_{n+1}) S = ( z 1 , … , z n + 1 ) of n + 1 n+1 n + 1 points, let S − i S_{-i} S − i denote S S S with one occurrence of z i z_i z i removed, and define
r i A ( S ) = ℓ ( z i , A ( S − i ) ) , T A ( S ) = ∑ i = 1 n + 1 r i A ( S ) , Δ A ( S ) = ( n + 1 ) α − T A ( S ) . \begin{equation}
r_i^A(S)=\ell(z_i,A(S_{-i})),\qquad
T_A(S)=\sum_{i=1}^{n+1} r_i^A(S),\qquad
\Delta_A(S)=(n+1)\alpha-T_A(S). \tag*{(3.4)}
\end{equation} r i A ( S ) = ℓ ( z i , A ( S − i )) , T A ( S ) = i = 1 ∑ n + 1 r i A ( S ) , Δ A ( S ) = ( n + 1 ) α − T A ( S ) . (3.4)
Here r i A ( S ) r_i^A(S) r i A ( S ) is the loss incurred when z i z_i z i plays the role of the test point and the remaining n n n points form the calibration data, T A ( S ) T_A(S) T A ( S ) is the total of these held-out losses, and Δ A ( S ) \Delta_A(S) Δ A ( S ) is the part of the budget ( n + 1 ) α (n+1)\alpha ( n + 1 ) α that they leave unused. Repeated observations are counted with their multiplicities.
Lemma 3.1 (Exact leave-one-out characterization). A symmetric controller A A A is valid under every finite exchangeable law if and only if T A ( S ) ≤ ( n + 1 ) α for every deterministic augmented multiset S .
T_A(S)\leq (n+1)\alpha\qquad\text{for every deterministic augmented multiset }S.
T A ( S ) ≤ ( n + 1 ) α for every deterministic augmented multiset S .
Proof. By symmetry of A A A and exchangeability, the test loss has the same distribution as each held-out loss, so E ℓ ( Z n + 1 , A ( Z 1 : n ) ) = ( n + 1 ) − 1 E T A ( Z 1 : n + 1 ) {\mathbb E}\ell(Z_{n+1},A(Z_{1:n}))=(n+1)^{-1}{\mathbb E}T_A(Z_{1:n+1}) E ℓ ( Z n + 1 , A ( Z 1 : n )) = ( n + 1 ) − 1 E T A ( Z 1 : n + 1 ) , which proves sufficiency. For necessity, fix S S S and let the data be a uniformly random ordering of S S S . This law is exchangeable, and its risk is exactly T A ( S ) / ( n + 1 ) T_A(S)/(n+1) T A ( S ) / ( n + 1 ) . ◻
The lemma is closely connected to the orbit-average characterization of exchangeability e-values [40 , 27 ] , and it is the risk-control counterpart of the universality of conformal prediction [42 Proposition 2.9] . Its necessity part uses all finite exchangeable laws, which is why we require validity under exchangeability rather than under i.i.d. sampling alone (Appendix app:iid ).
For a valid controller, Δ A ( S ) ≥ 0 \Delta_A(S)\geq0 Δ A ( S ) ≥ 0 is an exact account of the unused budget of the augmented sample S S S : it is the total amount by which the n + 1 n+1 n + 1 held-out losses on S S S could increase without violating (3.5) . It can be computed from the controller and the known loss once every point of S S S is specified (see the example in § 3.4 ). Finally, we remark that the original CRC also connects to this view: its validity can be derived from conformal e-values [40 , 27 ] that are allowed to depend on the action being certified (Appendix § 7.1 ).
A baseline-preserving refinement
Starting from any valid symmetric controller A A A , recertification spends Δ A ( S ) \Delta_A(S) Δ A ( S ) by distributing it among the held-out positions. For example, with equal sharing,
b i A ( S ) = r i A ( S ) + Δ A ( S ) n + 1 , ∑ i = 1 n + 1 b i A ( S ) = ( n + 1 ) α . \begin{equation}
b_i^A(S)=r_i^A(S)+\frac{\Delta_A(S)}{n+1},
\qquad \sum_{i=1}^{n+1} b_i^A(S)=(n+1)\alpha. \tag*{(3.6)}
\end{equation} b i A ( S ) = r i A ( S ) + n + 1 Δ A ( S ) , i = 1 ∑ n + 1 b i A ( S ) = ( n + 1 ) α . (3.6)
The new budgets still sum to ( n + 1 ) α (n+1)\alpha ( n + 1 ) α on every augmented sample, and each exceeds the corresponding held-out loss of A A A by Δ A ( S ) / ( n + 1 ) \Delta_A(S)/(n+1) Δ A ( S ) / ( n + 1 ) . The recertified controller selects the smallest action whose loss, for every possible test point z z z , stays within its new budget:
( R A ) ( D ) = min { λ ≤ A ( D ) : ℓ ( z , λ ) − ℓ ( z , A ( D ) ) ≤ Δ A ( D ∪ { z } ) n + 1 ∀ z ∈ Z } . \begin{equation}
\quad(\mathcal RA)(D)=\min\left\{\lambda\leq A(D):
\ell(z,\lambda)-\ell(z,A(D))\leq\frac{\Delta_A(D\cup\{z\})}{n+1}\ \forall z\in\mathcal Z\right\}.\quad \tag*{(3.7)}
\end{equation} ( R A ) ( D ) = min { λ ≤ A ( D ) : ℓ ( z , λ ) − ℓ ( z , A ( D )) ≤ n + 1 Δ A ( D ∪ { z }) ∀ z ∈ Z } . (3.7)
The baseline action A ( D ) A(D) A ( D ) satisfies every constraint, so the feasible set is nonempty, and on a finite grid, or on a compact interval under (3.1) , its minimum is attained. We assume that the minimizer is implemented measurably. More generally, any feasible action no larger than A ( D ) A(D) A ( D ) enjoys the following guarantee, so exact minimization is optional.
Theorem 3.2 (Uniform improvement). For every valid symmetric baseline A A A , the controller R A \mathcal RA R A is valid and satisfies R A ≤ A \mathcal RA\leq A R A ≤ A pointwise. In particular, with A ( 0 ) = A e n v A^{(0)}=A_{\mathrm{env}} A ( 0 ) = A env and A ( k + 1 ) = R A ( k ) A^{(k+1)}=\mathcal RA^{(k)} A ( k + 1 ) = R A ( k ) , A ( k + 1 ) ( D ) ≤ A ( k ) ( D ) ≤ A e n v ( D ) ≤ A C R C ( D ) for every D , k ,
A^{(k+1)}(D)\leq A^{(k)}(D)\leq A_{\mathrm{env}}(D)\leq A_{\mathrm{CRC}}(D)
\quad\text{for every }D,k,
A ( k + 1 ) ( D ) ≤ A ( k ) ( D ) ≤ A env ( D ) ≤ A CRC ( D ) for every D , k , and every iterate controls the expected loss at level α \alpha α .
Proof. Fix S S S . The constraint in (3.7) with D = S − i D=S_{-i} D = S − i and z = z i z=z_i z = z i shows that each held-out loss of R A \mathcal RA R A exceeds that of A A A by at most Δ A ( S ) / ( n + 1 ) \Delta_A(S)/(n+1) Δ A ( S ) / ( n + 1 ) . Summing over i i i gives
∑ i = 1 n + 1 ℓ ( z i , ( R A ) ( S − i ) ) ≤ T A ( S ) + Δ A ( S ) = ( n + 1 ) α , \sum_{i=1}^{n+1}\ell(z_i,(\mathcal RA)(S_{-i}))
\leq T_A(S)+\Delta_A(S)=(n+1)\alpha, i = 1 ∑ n + 1 ℓ ( z i , ( R A ) ( S − i )) ≤ T A ( S ) + Δ A ( S ) = ( n + 1 ) α , so R A \mathcal RA R A is valid by Lemma 3.1 . Since A ( D ) A(D) A ( D ) is feasible in (3.7) , R A ≤ A \mathcal RA\leq A R A ≤ A , and the chain (3.8) follows by induction from A e n v ≤ A C R C A_{\mathrm{env}}\leq A_{\mathrm{CRC}} A env ≤ A CRC . ◻
3.25ex -1em Recertified CRC as an instance of generalized e-closure. The improved controller R A \mathcal RA R A is obtained exactly by applying Proposition 2.2 and Theorem 2.1 to the CRC problem, with unordered augmented samples as states. Let the data be the calibration multiset D D D , and let a state be an augmented multiset S = ( z 1 , … , z n + 1 ) S=(z_1,\ldots,z_{n+1}) S = ( z 1 , … , z n + 1 ) . The class P S \mathcal P_S P S consists of a single law, under which D = S − I D=S_{-I} D = S − I for a position I I I drawn uniformly from { 1 , … , n + 1 } \{1,\ldots,n+1\} { 1 , … , n + 1 } . Conditioning a finite exchangeable law on the multiset of its n + 1 n+1 n + 1 values yields such a law, and each such law arises from the exchangeable law that orders S S S uniformly at random. When D ⊆ S D\subseteq S D ⊆ S , the held-out point S ∖ D S\setminus D S ∖ D is determined by S S S and D D D , and the loss is
L ( S , λ ; D ) = ℓ ( S ∖ D , λ ) , L(S,\lambda;D)=\ell(S\setminus D,\lambda), L ( S , λ ; D ) = ℓ ( S ∖ D , λ ) ,
with L ( S , λ ; D ) = 0 L(S,\lambda;D)=0 L ( S , λ ; D ) = 0 when D D D cannot arise from S S S . Validity in state S S S is then exactly the constraint (3.5) for that S S S , so validity in every state is equivalent to validity under every finite exchangeable law.
The canonical e-collection of a valid controller A A A is E S A ( D ) = L ( S , A ( D ) ; D ) / α E^A_S(D)=L(S,A(D);D)/\alpha E S A ( D ) = L ( S , A ( D ) ; D ) / α , whose expectation under P S \mathcal P_S P S is T A ( S ) / ( ( n + 1 ) α ) T_A(S)/((n+1)\alpha) T A ( S ) / (( n + 1 ) α ) . Its shortfall from one is Δ A ( S ) / ( ( n + 1 ) α ) \Delta_A(S)/((n+1)\alpha) Δ A ( S ) / (( n + 1 ) α ) , the unused budget of (3.4) . Since each state specifies a single known law, recertification fills this shortfall without conditioning. In Proposition 2.2 we take V S V_S V S constant, the baseline envelope g S ( D ) = L ( S , A ( D ) ; D ) g_S(D)=L(S,A(D);D) g S ( D ) = L ( S , A ( D ) ; D ) , the bounds H S = T A ( S ) / ( n + 1 ) H_S=T_A(S)/(n+1) H S = T A ( S ) / ( n + 1 ) and B S = α B_S=\alpha B S = α , and the increment W S ( D ) = Δ A ( S ) / ( n + 1 ) W_S(D)=\Delta_A(S)/(n+1) W S ( D ) = Δ A ( S ) / ( n + 1 ) for D ⊆ S D\subseteq S D ⊆ S (and zero otherwise). The recertified e-collection is
E S ′ ( D ) = g S ( D ) + W S ( D ) α = b i A ( S ) α for D = S − i , E'_S(D)=\frac{g_S(D)+W_S(D)}{\alpha}=\frac{b_i^A(S)}{\alpha}\qquad\text{for }D=S_{-i}, E S ′ ( D ) = α g S ( D ) + W S ( D ) = α b i A ( S ) for D = S − i ,
which has expectation exactly one by (3.6) . At an observed D D D , only the states S = D ∪ { z } S=D\cup\{z\} S = D ∪ { z } with z ∈ Z z\in\mathcal Z z ∈ Z impose constraints, and the certified menu (2.3) becomes
C α ( E ′ ; D ) = { λ ∈ Λ : ℓ ( z , λ ) − ℓ ( z , A ( D ) ) ≤ Δ A ( D ∪ { z } ) n + 1 ∀ z ∈ Z } . \mathcal C_\alpha(E';D)=\left\{\lambda\in\Lambda:\ \ell(z,\lambda)-\ell(z,A(D))\leq\frac{\Delta_A(D\cup\{z\})}{n+1}\ \ \forall z\in\mathcal Z\right\}. C α ( E ′ ; D ) = { λ ∈ Λ : ℓ ( z , λ ) − ℓ ( z , A ( D )) ≤ n + 1 Δ A ( D ∪ { z }) ∀ z ∈ Z } .
Each constraint bounds a non-increasing function of λ \lambda λ , and A ( D ) A(D) A ( D ) satisfies all of them, so the menu is an upper set of Λ \Lambda Λ that contains A ( D ) A(D) A ( D ) , and its smallest element is ( R A ) ( D ) (\mathcal RA)(D) ( R A ) ( D ) . The restriction λ ≤ A ( D ) \lambda\leq A(D) λ ≤ A ( D ) in (3.7) is thus automatic: the recertified controller selects the least conservative certified action, and by Theorem 2.1 any other selection from the menu would be valid as well.
\fontsize{10}{12}\selectfont
\caption{One recertification of a known-loss CRC controller}\label{alg:recycle}
\begin{algorithmic}[1]
\REQUIRE A valid symmetric controller $A$, loss $\ell$, calibration multiset $D$, and level $\alpha$.
\STATE Compute $a_0=A(D)$.
\FOR{each hypothetical $z\in\mathcal Z$}
\STATE Compute $T_A(D\cup\{z\})=\ell(z,a_0)+\sum_{j=1}^n\ell(Z_j,A(D_{-j}\cup\{z\}))$.
\STATE Set $s_A(D,z)=\alpha-T_A(D\cup\{z\})/(n+1)$.
\ENDFOR
\STATE Return the smallest $\lambda\leq a_0$ such that $\ell(z,\lambda)-\ell(z,a_0)\leq s_A(D,z)$ for every $z$.
\end{algorithmic}
Algorithm alg:recycle summarizes one round of recertification at an observed calibration multiset D D D . Each round evaluates the current controller on all replacement samples D − j ∪ { z } D_{-j}\cup\{z\} D − j ∪ { z } . Equal sharing is the simplest allocation of the unused budget. Other permutation-respecting allocations are also valid, and every valid pointwise improvement of a controller with monotone losses arises from some allocation (Appendix § 7.2 ); which allocation works best in one step depends on the problem.
Iteration to admissibility under convexity
Since recertification preserves validity, it can be repeated, and each round can only improve the selected action. For convex losses, the iterates converge to an admissible controller that cannot be improved further, in the following pointwise sense.
Definition 3.4 (Pointwise admissibility for CRC). A valid symmetric deterministic controller A A A is pointwise admissible if no other measurable symmetric deterministic controller C C C is valid under every finite exchangeable law and satisfies C ( D ) ≤ A ( D ) C(D)\leq A(D) C ( D ) ≤ A ( D ) for every D D D , strictly at some D D D . The observation domain, loss family, sample size and action space remain fixed.
Admissibility is thus a pointwise notion: controllers are compared on every calibration sample. This is meaningful because Lemma 3.1 imposes a constraint on every augmented multiset, with no exceptional null sets, so changing a controller at even a single calibration multiset can affect its validity. The notion concerns only how conservative the selected actions are. An admissible controller need not be optimal for a particular utility, and several admissible controllers may coexist, as the example at the end of this section shows.
Theorem 3.5 (An admissible limit). Suppose Λ = [ λ − , λ + ] \Lambda=[\lambda_-,\lambda_+] Λ = [ λ − , λ + ] and every ℓ ( z , ⋅ ) \ell(z,\cdot) ℓ ( z , ⋅ ) in (3.1) is convex. Suppose the exact inversions in (3.7) are measurably implemented. From any valid baseline, the iterates decrease to a valid pointwise-admissible controller A ( ∞ ) A^{(\infty)} A ( ∞ ) . With ρ = n / ( n + 1 ) \rho=n/(n+1) ρ = n / ( n + 1 ) , 0 ≤ A ( k ) ( D ) − A ( ∞ ) ( D ) ≤ ρ k ( A ( 0 ) ( D ) − A ( ∞ ) ( D ) ) ≤ ρ k ( λ + − λ − ) .
0\leq A^{(k)}(D)-A^{(\infty)}(D)
\leq\rho^k (A^{(0)}(D)-A^{(\infty)}(D))
\leq\rho^k(\lambda_+-\lambda_-).
0 ≤ A ( k ) ( D ) − A ( ∞ ) ( D ) ≤ ρ k ( A ( 0 ) ( D ) − A ( ∞ ) ( D )) ≤ ρ k ( λ + − λ − ) . A valid controller is admissible if and only if it is an exact fixed point of R \mathcal R R in this setting.
The proof rests on a one-step comparison. Suppose that a valid controller C C C satisfies C ≤ A C\leq A C ≤ A . On every augmented sample, each held-out loss of C C C exceeds that of A A A by a nonnegative amount, and by Lemma 3.1 these increases sum to at most Δ A ( S ) \Delta_A(S) Δ A ( S ) , so each is at most Δ A ( S ) \Delta_A(S) Δ A ( S ) . By convexity, the action ρ A ( D ) + C ( D ) / ( n + 1 ) \rho A(D)+C(D)/(n+1) ρ A ( D ) + C ( D ) / ( n + 1 ) increases each loss by at most a fraction 1 / ( n + 1 ) 1/(n+1) 1/ ( n + 1 ) of this amount, so it is feasible in (3.7) , and therefore
R A ≤ ρ A + C / ( n + 1 ) . \begin{equation}
\mathcal RA\leq\rho A+C/(n+1). \tag*{(3.10)}
\end{equation} R A ≤ ρ A + C / ( n + 1 ) . (3.10)
The iterates decrease to a limit, which is valid by the right continuity of the losses. Applying (3.10) along the iterates and passing to the limit shows that no valid controller strictly dominates the limit, and taking C = A ( ∞ ) C=A^{(\infty)} C = A ( ∞ ) gives the rate (3.9) . Appendix § 7.3 gives the complete proof.
We note that convexity is used only for the admissibility of the limit, and every finite round of recertification is valid without it. The limit theorem also uses an interval of actions, since on a grid the interpolated action in (3.10) may be unavailable; Appendix § 7.5 gives an example. Many common prediction losses, such as miscoverage indicators, are step functions of λ \lambda λ . For such losses the iteration still improves the baseline validly, and § 3.5 describes a different completion that reaches an admissible controller using only monotonicity.
3.25ex -1em A two-type example. A small example makes the iteration concrete. Let the observation space consist of two points, Z = { H , L } \mathcal Z=\{H,L\} Z = { H , L } , with a high and a low loss,
ℓ ( H , λ ) = 1 − λ , ℓ ( L , λ ) = 1 2 ( 1 − λ ) , λ ∈ Λ = [ 0 , 1 ] , \begin{equation}
\ell(H,\lambda)=1-\lambda,\qquad
\ell(L,\lambda)=\tfrac12(1-\lambda),\qquad \lambda\in\Lambda=[0,1], \tag*{(3.11)}
\end{equation} ℓ ( H , λ ) = 1 − λ , ℓ ( L , λ ) = 2 1 ( 1 − λ ) , λ ∈ Λ = [ 0 , 1 ] , (3.11)
and take n = 2 n=2 n = 2 and α = 1 / 2 \alpha=1/2 α = 1/2 . The probabilities of the two points, and the dependence between observations, are arbitrary apart from exchangeability. We write multisets of observations as strings: H L HL H L is the calibration sample with one point of each kind, and H L L HLL H LL is an augmented sample, that is, a state in the formulation of § 3.3 . The sharp envelope is U ( λ ) = 1 − λ U(\lambda)=1-\lambda U ( λ ) = 1 − λ , and Table 1 lists each controller on the three possible calibration samples.
Table 1. The two-type example with n = 2 n=2 n = 2 and α = 1 / 2 \alpha=1/2 α = 1/2 . Rows are the possible calibration samples and columns are controllers; entries are the selected actions, and smaller is preferred. The iterates start at envelope CRC. Every comparison holds for all exchangeable distributions on { H , L } 3 \{H,L\}^3 { H , L } 3 .
For instance, at D = L L D=LL D = LL the envelope action is 1 / 4 1/4 1/4 . Appending H H H gives the augmented sample H L L HLL H LL , whose held-out losses 3 / 4 3/4 3/4 , 3 / 10 3/10 3/10 and 3 / 10 3/10 3/10 total 27 / 20 27/20 27/20 . The equal allowance is 1 / 2 − ( 27 / 20 ) / 3 = 1 / 20 1/2-(27/20)/3=1/20 1/2 − ( 27/20 ) /3 = 1/20 , so the constraint for z = H z=H z = H reads 1 / 4 − λ ≤ 1 / 20 1/4-\lambda\leq1/20 1/4 − λ ≤ 1/20 , that is, λ ≥ 1 / 5 \lambda\geq1/5 λ ≥ 1/5 , while appending L L L permits every λ ≥ 0 \lambda\geq0 λ ≥ 0 . Thus A ( 1 ) ( L L ) = 1 / 5 A^{(1)}(LL)=1/5 A ( 1 ) ( LL ) = 1/5 . The entries converge geometrically, as Theorem 3.5 predicts with ρ = 2 / 3 \rho=2/3 ρ = 2/3 . At the limit, the validity constraints for H H H HHH H H H , H H L HHL H H L and H L L HLL H LL bind, which makes the limit admissible, whereas the constraint for L L L LLL LLL is slack: an admissible controller may leave budget unused on some augmented samples. Appendix § 7.5 gives the exact iteration formulas. Admissible controllers need not be unique either. The controller with entries ( 1 / 2 , 2 / 5 , 1 / 10 ) (1/2,2/5,1/10) ( 1/2 , 2/5 , 1/10 ) on ( H H , H L , L L ) (HH,HL,LL) ( H H , H L , LL ) is also admissible and is incomparable with the limit, and the pointwise minimum of the two is invalid. Which admissible controller is preferable thus generally depends on the specific problem setting.
Extensions and computation
We now extend the construction to multiple risks, to nonconvex losses and to controllers that use test features, and finally discuss its computational cost.
3.25ex -1em Multiple risks. In many applications a single action must control multiple losses at once. A prediction set, for example, may be required to control both its miscoverage and the fraction of true labels it misses, or a whole family of losses indexed by a continuous severity level. CRC handles such families when the losses share the same action [3 Section 4.3] , and recertification extends in the same way.
Let ℓ t ( z , λ ) \ell_t(z,\lambda) ℓ t ( z , λ ) , t ∈ T t\in\mathcal T t ∈ T , be a family of losses indexed by an arbitrary, possibly uncountable, set T \mathcal T T , each satisfying (3.1) with its own level α t > 0 \alpha_t>0 α t > 0 and the same action space Λ \Lambda Λ . A controller A A A is jointly valid if E ℓ t ( Z n + 1 , A ( D ) ) ≤ α t {\mathbb E}\,\ell_t(Z_{n+1},A(D))\leq\alpha_t E ℓ t ( Z n + 1 , A ( D )) ≤ α t for every t ∈ T t\in\mathcal T t ∈ T under every finite exchangeable law. By Lemma 3.1 , applied to each risk, this holds if and only if
T A , t ( S ) = ∑ i = 1 n + 1 ℓ t ( z i , A ( S − i ) ) ≤ ( n + 1 ) α t for every augmented multiset S and every t ∈ T . T_{A,t}(S)=\sum_{i=1}^{n+1}\ell_t(z_i,A(S_{-i}))\leq(n+1)\alpha_t
\qquad\text{for every augmented multiset $S$ and every $t\in\mathcal T$}. T A , t ( S ) = i = 1 ∑ n + 1 ℓ t ( z i , A ( S − i )) ≤ ( n + 1 ) α t for every augmented multiset S and every t ∈ T .
Since all losses are non-increasing in λ \lambda λ , the most conservative of the separate CRC choices, that is, their supremum over t t t , is jointly valid whenever it is measurable, and the same holds for envelope CRC. For a jointly valid A A A , recertification shares each loss-wise unused budget equally among the held-out positions and imposes the resulting constraints for all risks simultaneously:
Δ A , t ( S ) = ( n + 1 ) α t − T A , t ( S ) , ( R A ) ( D ) = min { λ ≤ A ( D ) : ℓ t ( z , λ ) − ℓ t ( z , A ( D ) ) ≤ Δ A , t ( D ∪ { z } ) n + 1 ∀ z ∈ Z , t ∈ T } . \begin{equation}
\begin{aligned}
\Delta_{A,t}(S)&=(n+1)\alpha_t-T_{A,t}(S),\\
(\mathcal RA)(D)&=\min\left\{\lambda\leq A(D):
\ell_t(z,\lambda)-\ell_t(z,A(D))\leq\frac{\Delta_{A,t}(D\cup\{z\})}{n+1}\ \ \forall z\in\mathcal Z,\ t\in\mathcal T\right\}.
\end{aligned} \tag*{(3.12)}
\end{equation} Δ A , t ( S ) ( R A ) ( D ) = ( n + 1 ) α t − T A , t ( S ) , = min { λ ≤ A ( D ) : ℓ t ( z , λ ) − ℓ t ( z , A ( D )) ≤ n + 1 Δ A , t ( D ∪ { z }) ∀ z ∈ Z , t ∈ T } . (3.12)
Proposition 3.6 (Multiple risks). For every jointly valid symmetric controller A A A , the controller R A \mathcal RA R A in (3.12) is jointly valid and satisfies R A ≤ A \mathcal RA\leq A R A ≤ A . If, moreover, Λ = [ λ − , λ + ] \Lambda=[\lambda_-,\lambda_+] Λ = [ λ − , λ + ] and every ℓ t ( z , ⋅ ) \ell_t(z,\cdot) ℓ t ( z , ⋅ ) is convex, the conclusions of Theorem 3.5 hold for the iterates of (3.12) , with the same rate ρ = n / ( n + 1 ) \rho=n/(n+1) ρ = n / ( n + 1 ) , regardless of the index set T \mathcal T T .
The proof of Theorem 3.2 simply applies to each risk separately; see Appendix § 7.3 . The number of risks thus enters neither the rate nor the admissibility conclusion. It matters only for attaining the minimum in (3.12) measurably. Appendix § 7.6 works out a simple two-risk example with a continuum of observations, in which recertification converges to the largest valid rule dominating the joint envelope baseline, a strict improvement at every interior point.
3.25ex -1em Nonconvex losses. Theorem 3.5 relies on convexity, which fails for many prediction losses, such as miscoverage indicators. For general monotone losses, admissibility can instead be characterized one calibration multiset at a time. Let ν D ( z ) \nu_D(z) ν D ( z ) denote the number of copies of z z z in D D D . Lowering the controller only at D D D , from A ( D ) A(D) A ( D ) to a < A ( D ) a<A(D) a < A ( D ) , changes the held-out losses only on the augmented samples D ∪ { z } D\cup\{z\} D ∪ { z } , in each of which z z z is held out ν D ( z ) + 1 \nu_D(z)+1 ν D ( z ) + 1 times. By Lemma 3.1 , the change preserves joint validity if and only if
( ν D ( z ) + 1 ) { ℓ t ( z , a ) − ℓ t ( z , A ( D ) ) } ≤ Δ A , t ( D ∪ { z } ) ∀ z ∈ Z , t ∈ T . \begin{equation}
(\nu_D(z)+1)\{\ell_t(z,a)-\ell_t(z,A(D))\}
\leq\Delta_{A,t}(D\cup\{z\})\qquad\forall z\in\mathcal Z,\ t\in\mathcal T. \tag*{(3.13)}
\end{equation} ( ν D ( z ) + 1 ) { ℓ t ( z , a ) − ℓ t ( z , A ( D ))} ≤ Δ A , t ( D ∪ { z }) ∀ z ∈ Z , t ∈ T . (3.13)
Proposition 3.7. A jointly valid symmetric controller A A A is pointwise admissible if and only if (3.13) fails for every calibration multiset D D D and every a < A ( D ) a<A(D) a < A ( D ) . If the observation space Z \mathcal Z Z is finite, the following sweep produces a pointwise-admissible controller that is no larger than A A A : visit the calibration multisets once in a fixed order, and at each visit replace A ( D ) A(D) A ( D ) by the smallest a a a satisfying (3.13) , holding all other entries fixed.
The sweep uses only monotonicity: lowering one entry can only shrink the allowances of the others, so an entry that cannot be lowered when it is visited cannot be lowered later (Appendix § 7.4 ). Its cost is a single pass over the controller table, which has one entry per calibration multiset.
3.25ex -1em Test features. In prediction problems, the feature x x x of the test point is observed and only its label y y y is unknown, so the controller may depend on it, A ( D , x ) A(D,x) A ( D , x ) . Validity then means E ℓ t ( Z n + 1 , A ( D , X n + 1 ) ) ≤ α t {\mathbb E}\,\ell_t(Z_{n+1},A(D,X_{n+1}))\leq\alpha_t E ℓ t ( Z n + 1 , A ( D , X n + 1 )) ≤ α t , a guarantee that is marginal over test features and labels, as for CRC itself. On an augmented sample, the held-out loss becomes ℓ t ( z i , A ( S − i , x i ) ) \ell_t(z_i,A(S_{-i},x_i)) ℓ t ( z i , A ( S − i , x i )) , and the recertified controller at the observed ( D , x ) (D,x) ( D , x ) is
( R A ) ( D , x ) = min { λ ≤ A ( D , x ) : ℓ t ( ( x , y ) , λ ) − ℓ t ( ( x , y ) , A ( D , x ) ) ≤ Δ A , t ( D ∪ { ( x , y ) } ) n + 1 ∀ y , t } . (\mathcal RA)(D,x)=\min\left\{\lambda\leq A(D,x):
\ell_t((x,y),\lambda)-\ell_t((x,y),A(D,x))\leq\frac{\Delta_{A,t}(D\cup\{(x,y)\})}{n+1}\ \ \forall y,t\right\}. ( R A ) ( D , x ) = min { λ ≤ A ( D , x ) : ℓ t (( x , y ) , λ ) − ℓ t (( x , y ) , A ( D , x )) ≤ n + 1 Δ A , t ( D ∪ {( x , y )}) ∀ y , t } .
The constraints range only over the possible labels y y y , while each unused budget Δ A , t \Delta_{A,t} Δ A , t evaluates the current controller at the feature of every held-out point. Lemma 3.1 continues to hold with these held-out losses, since its proof uses only the symmetry of A A A in D D D and exchangeability. The constraint for the label y y y at ( D , x ) (D,x) ( D , x ) is the constraint for the held-out copy of ( x , y ) (x,y) ( x , y ) in D ∪ { ( x , y ) } D\cup\{(x,y)\} D ∪ {( x , y )} , so the proofs of Theorems 3.2 and 3.5 carry over with D D D replaced by ( D , x ) (D,x) ( D , x ) .
3.25ex -1em Computation. The risk-control guarantees hold after any number of rounds, so the number of rounds is a computational choice, whose cost depends on how the controller depends on the data.
A single round is usually inexpensive. With K K K candidate outcomes, ( R A ) ( D ) (\mathcal RA)(D) ( R A ) ( D ) requires A ( D ) A(D) A ( D ) and the totals T A ( D ∪ { z } ) T_A(D\cup\{z\}) T A ( D ∪ { z }) , that is, the controller evaluated on the n K nK n K replacement samples D − j ∪ { z } D_{-j}\cup\{z\} D − j ∪ { z } , each a recalibration with the prediction model held fixed. For CRC and envelope CRC, these recalibrations share most of their work. A replacement changes a single term of the calibration loss ∑ i = 1 n ℓ ( Z i , λ ) \sum_{i=1}^n\ell(Z_i,\lambda) ∑ i = 1 n ℓ ( Z i , λ ) , so the sum is computed once and adjusted for each replacement, and each replacement action is the smallest λ \lambda λ satisfying a constraint that is monotone in λ \lambda λ . Such an action is found by a binary search for general losses and directly for structured ones, such as piecewise-linear or step losses.
Repeated rounds are more demanding, because the replacements compound. Round k k k evaluates A ( k − 1 ) A^{(k-1)} A ( k − 1 ) on replacement samples, each of which requires A ( k − 2 ) A^{(k-2)} A ( k − 2 ) on samples with a second point replaced, and so on. Hence A ( k ) ( D ) A^{(k)}(D) A ( k ) ( D ) depends on the baseline at every calibration multiset obtained from D D D by replacing up to k k k of its points with candidate outcomes. The cost of many rounds is governed by how many distinct multisets arise and whether they can be shared across calibration samples and test points, and both depend on how the baseline depends on the data.
Finitely many types. Suppose that the loss depends on an observation only through one of K K K types and that the baseline depends on the calibration data only through the type counts. Every iterate then inherits this property, so all the multisets above belong to a single table indexed by count vectors. The table has ( n + K − 1 K − 1 ) \binom{n+K-1}{K-1} ( K − 1 n + K − 1 ) entries, polynomially many in n n n for fixed K K K , and each round is one pass over it. It does not depend on the observed data, so it is computed once and reused for every calibration sample and test point.
Individual scores or features. When the baseline depends on individual observations, for instance through continuous scores or test features, no such table exists. The replacement samples must then be tracked separately for each calibration sample and test point, and their number grows exponentially in the number of calibration points whose loss is not identically zero. Exact reductions, such as grouping points with identical scores, can still make many rounds feasible (Appendix § 7.7 ).
Uncountable outcomes or risks. Here even a single round requires care. The constraints in (3.12) must hold for a continuum of z z z or t t t , and checking them requires a certified optimization or a uniform approximation bound, since finitely many sampled outcomes do not certify feasibility.
Two observations reduce the cost in every case. First, the iterates decrease and the losses are non-increasing, so stopping at a data-dependent round no later than a fixed maximum incurs at most the loss of the maximal round and preserves validity. Computation can therefore stop once a computable bound shows that further rounds cannot change the action appreciably. Second, replacing the allowances Δ A , t \Delta_{A,t} Δ A , t by conservative lower bounds preserves validity and the comparison with the baseline, although the limit may then fall short of admissibility. Exact recertification thus trades computation for a uniform improvement.
Real-data study
We evaluate recertification on hierarchical image classification, one of the applications of CRC in [3 ] , and compare it with ordinary CRC and with envelope CRC [48 ] .
Hierarchical classification
We consider the hierarchical image classification setting, where each observation is Z i = ( X i , Y i ) Z_i=(X_i,Y_i) Z i = ( X i , Y i ) . Here, each X i ∈ X X_i\in\mathcal X X i ∈ X is an image and Y i ∈ Y = { 1 , … , K 1 } Y_i\in\mathcal Y=\{1,\ldots,K_1\} Y i ∈ Y = { 1 , … , K 1 } is its fine-class label. The labels are partitioned into K 2 K_2 K 2 superclasses G 1 , … , G K 2 G_1,\ldots,G_{K_2} G 1 , … , G K 2 , which form a tree of depth two with a root, the superclasses and the fine-class leaves. We identify each node with the set of its descendant labels, so that the root is Y \mathcal Y Y .
A fixed, pretrained classifier outputs class probabilities p ( x ) = ( p 1 ( x ) , … , p K 1 ( x ) ) p(x)=(p_1(x),\ldots,p_{K_1}(x)) p ( x ) = ( p 1 ( x ) , … , p K 1 ( x )) . Let f ( x ) = arg max k p k ( x ) f(x)=\arg\max_k p_k(x) f ( x ) = arg max k p k ( x ) , with ties broken deterministically, and let g ( x ) g(x) g ( x ) be the superclass containing f ( x ) f(x) f ( x ) . For an image x x x , predictions are restricted to the three nodes Y \mathcal Y Y , g ( x ) g(x) g ( x ) and { f ( x ) } \{f(x)\} { f ( x )} on this path. For a reported node v v v and a true class y y y , the hierarchical loss is
L ( v , y ) = 1 2 min u ∈ a n c ( y ) d ( v , u ) , L(v,y)=\frac12\min_{u\in\mathrm{anc}(y)}d(v,u), L ( v , y ) = 2 1 u ∈ anc ( y ) min d ( v , u ) ,
where d d d is the tree distance and a n c ( y ) \mathrm{anc}(y) anc ( y ) consists of the leaf { y } \{y\} { y } and its ancestors. Thus L ( v , y ) = 0 L(v,y)=0 L ( v , y ) = 0 when y ∈ v y\in v y ∈ v , and otherwise L ( v , y ) L(v,y) L ( v , y ) is half the number of upward edges needed to reach a node containing y y y .
To obtain a continuous action space, we allow randomization between adjacent depths. For a ∈ [ 0 , 2 ] a\in[0,2] a ∈ [ 0 , 2 ] , let N a ( x ) N_a(x) N a ( x ) report the root, the superclass and the leaf with probabilities ( ( 1 − a ) + , 1 − ∣ a − 1 ∣ , ( a − 1 ) + ) ((1-a)_+,\,1-|a-1|,\,(a-1)_+) (( 1 − a ) + , 1 − ∣ a − 1∣ , ( a − 1 ) + ) , where r + = max { r , 0 } r_+=\max\{r,0\} r + = max { r , 0 } . Its mean depth is a a a , and its expected loss is
ℓ ( ( x , y ) , a ) = E [ L ( N a ( x ) , y ) ] = { 0 , y = f ( x ) , ( a − 1 ) + / 2 , y ∈ g ( x ) ∖ { f ( x ) } , a / 2 , y ∉ g ( x ) . \begin{equation}
\ell((x,y),a)={\mathbb E}[L(N_a(x),y)]=
\begin{cases}
0, & y=f(x),\\
(a-1)_+/2, & y\in g(x)\setminus\{f(x)\},\\
a/2, & y\notin g(x).
\end{cases} \tag*{(3.14)}
\end{equation} ℓ (( x , y ) , a ) = E [ L ( N a ( x ) , y )] = ⎩ ⎨ ⎧ 0 , ( a − 1 ) + /2 , a /2 , y = f ( x ) , y ∈ g ( x ) ∖ { f ( x )} , y ∈ / g ( x ) . (3.14)
Given calibration data D = ( Z 1 , … , Z n ) D=(Z_1,\ldots,Z_n) D = ( Z 1 , … , Z n ) and a target α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , a procedure chooses a depth rule a ^ : X → [ 0 , 2 ] \widehat a:\mathcal X\to[0,2] a : X → [ 0 , 2 ] and reports N a ^ ( x ) ( x ) N_{\widehat a(x)}(x) N a ( x ) ( x ) for a test image x x x . The aim is to make predictions as specific as possible subject to
E ℓ ( Z n + 1 , a ^ ( X n + 1 ) ) ≤ α , {\mathbb E}\,\ell\bigl(Z_{n+1},\widehat a(X_{n+1})\bigr)\leq\alpha, E ℓ ( Z n + 1 , a ( X n + 1 ) ) ≤ α ,
where Z n + 1 Z_{n+1} Z n + 1 is a test observation exchangeable with D D D , the expectation is over the calibration and test data, and the randomization of the prediction is already integrated into ℓ \ell ℓ . This is the setting of § 3 with test features, in which the depth rule is the controller.
We consider two families of depth rules a t a_t a t , indexed by a parameter t t t . The first uses a common randomized depth, a t ( x ) = t a_t(x)=t a t ( x ) = t for t ∈ [ 0 , 2 ] t\in[0,2] t ∈ [ 0 , 2 ] : every image receives the same distribution over depths, although the reported superclass and leaf still depend on the image through g ( x ) g(x) g ( x ) and f ( x ) f(x) f ( x ) . The second adapts the depth to the confidence of the classifier. Write p f ( x ) = p f ( x ) ( x ) p_f(x)=p_{f(x)}(x) p f ( x ) = p f ( x ) ( x ) for the probability of the most likely class and p g ( x ) = ∑ k ∈ g ( x ) p k ( x ) p_g(x)=\sum_{k\in g(x)}p_k(x) p g ( x ) = ∑ k ∈ g ( x ) p k ( x ) for the total probability of its superclass. For a threshold t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] , set
a t ( x ) = 1 { t > 1 − p g ( x ) } + 1 { t > 1 − p f ( x ) } . a_t(x)=\mathop{\mathrm{\mathds{1}}}\{t>1-p_g(x)\}+\mathop{\mathrm{\mathds{1}}}\{t>1-p_f(x)\}. a t ( x ) = 1 { t > 1 − p g ( x )} + 1 { t > 1 − p f ( x )} .
This rule reports the root when p g ( x ) ≤ 1 − t p_g(x)\le1-t p g ( x ) ≤ 1 − t , the superclass when p f ( x ) ≤ 1 − t < p g ( x ) p_f(x)\le1-t<p_g(x) p f ( x ) ≤ 1 − t < p g ( x ) , and the leaf when p f ( x ) > 1 − t p_f(x)>1-t p f ( x ) > 1 − t , so more confident images receive more specific predictions.
In both families, larger values of t t t are less conservative, so the parameter λ \lambda λ of § 3 corresponds to − t -t − t . CRC selects the largest t t t satisfying
∑ i = 1 n ℓ ( Z i , a t ( X i ) ) + 1 ≤ ( n + 1 ) α , \sum_{i=1}^n\ell(Z_i,a_t(X_i))+1\le(n+1)\alpha, i = 1 ∑ n ℓ ( Z i , a t ( X i )) + 1 ≤ ( n + 1 ) α ,
where 1 1 1 is the largest possible loss. Envelope CRC replaces this bound by the sharper envelope U ( t ) U(t) U ( t ) , which equals t / 2 t/2 t /2 for common depth and 1 1 1 for every t > 0 t>0 t > 0 for confidence-adaptive scores; in the latter family, envelope CRC therefore coincides with CRC. Starting from envelope CRC, we apply one round and 500 500 500 rounds of recertification with equal sharing. Each round recomputes the unused budgets on the augmented samples and increases the depth as far as they permit. In the common-depth family, the recertified rule still assigns one randomized depth to all images and depends on the calibration data only through the counts of the three cases in (3.14) , so it is a finite table of the kind discussed in § 3.5 . In the confidence-adaptive family, the recertified rule depends on the test image and may randomize between adjacent depths beyond the deterministic threshold prediction.
Results
We use CIFAR-100, which has K 1 = 100 K_1=100 K 1 = 100 fine classes and K 2 = 20 K_2=20 K 2 = 20 superclasses of five classes each, so the root, superclass and leaf predictions contain 100 100 100 , 5 5 5 and 1 1 1 labels. The classifier is a frozen ResNet-18, and the data pool consists of its cached predictions on the 10,000 10{,}000 10 , 000 test images [19 ] . We report the mean hierarchical loss (risk), the mean node size ∣ v ∣ |v| ∣ v ∣ , and the correct specificity 1 { y ∈ v } [ 1 − log ∣ v ∣ / log K 1 ] \mathop{\mathrm{\mathds{1}}}\{y\in v\}[1-\log|v|/\log K_1] 1 { y ∈ v } [ 1 − log ∣ v ∣/ log K 1 ] , which rewards predictions that are both correct and informative. All three metrics are averaged analytically over the randomization of the prediction, and gains are absolute differences in correct specificity, in percentage points.
We fix n = 50 n=50 n = 50 and α ∈ { 0.02 , 0.05 , 0.10 , 0.15 } \alpha\in\{0.02,0.05,0.10,0.15\} α ∈ { 0.02 , 0.05 , 0.10 , 0.15 } , and average over 300 300 300 random splits of the pool, each with 50 50 50 calibration images and 16 16 16 disjoint test images. The same splits are used for all families, methods and targets, and standard errors are computed across splits. Appendix § 7.7 gives the implementation details.
Table 2 reports the results. All methods have empirical risk below the target in every setting. In the common-depth family, envelope CRC is much less conservative than CRC, particularly at small targets, and leaves little of the risk budget unused. Recertification therefore adds only a small gain on top of it, which grows with the target from none at α = 0.02 \alpha=0.02 α = 0.02 to 0.44 0.44 0.44 percentage points at α = 0.15 \alpha=0.15 α = 0.15 . In the confidence-adaptive family, envelope CRC coincides with CRC, and the entire improvement comes from recertification. At α = 0.10 \alpha=0.10 α = 0.10 , 500 500 500 rounds raise correct specificity from 67.57 % 67.57\% 67.57% to 68.24 % 68.24\% 68.24% and reduce the mean node size from 19.40 19.40 19.40 to 17.03 17.03 17.03 labels; at α = 0.02 \alpha=0.02 α = 0.02 , the gain is 1.71 1.71 1.71 percentage points.
Table 2. Hierarchical classification on CIFAR-100 with n = 50 n=50 n = 50 , averaged over 300 paired splits. One round and 500 rounds denote recertification of envelope CRC. CS is correct specificity (%) and size is the mean number of labels in the prediction. Time is in milliseconds per build of the reusable common-depth controller and per test image for confidence-adaptive scores.
Timings use an Intel Core i7-12700KF with Python/Numba and exclude model inference and compilation warm-up. Common-depth builds and the faster adaptive methods average 20 repetitions; 500-round adaptive timings cover all 4800 test images, including table construction.
Figure 2 shows how the gains beyond envelope CRC accumulate over rounds. A single round recovers between 10 % 10\% 10% and 26 % 26\% 26% of the gain after 500 500 500 rounds. At α = 0.10 \alpha=0.10 α = 0.10 , for example, one round gains 0.073 0.073 0.073 percentage points for common depth and 0.085 0.085 0.085 for confidence-adaptive scores, compared with 0.337 0.337 0.337 and 0.663 0.663 0.663 after 500 500 500 rounds. The first 50 50 50 rounds recover at least 95 % 95\% 95% of the final gain in every setting, and later rounds change little.
Figure 2. Gains in correct specificity of recertification beyond envelope CRC at n = 50 n=50 n = 50 . Each panel shows mean paired gains over 300 splits, with shaded pointwise 95% Student-t t t intervals. The horizontal axis is logarithmic in k + 1 k+1 k + 1 , where k k k is the number of rounds.
The two families locate the conservativeness of CRC in different places. In the common-depth family, most of it lies in the bound on the unseen loss: the envelope U ( t ) = t / 2 U(t)=t/2 U ( t ) = t /2 is much smaller than one at shallow depths, and envelope CRC removes most of the slack. In the confidence-adaptive family, the envelope equals the worst-case bound, yet recertification still produces more informative predictions, using budget that no choice of envelope can recover.
The possible increase in attained risk is bounded by the gap between the target level and the baseline risk. Since the risk of a controller A A A equals E T A ( S ) / ( n + 1 ) {\mathbb E}\,T_A(S)/(n+1) E T A ( S ) / ( n + 1 ) for an augmented sample S S S , the gap between α \alpha α and the risk is exactly the expected unused budget E Δ A ( S ) / ( n + 1 ) {\mathbb E}\,\Delta_A(S)/(n+1) E Δ A ( S ) / ( n + 1 ) , which is what recertification spends. In the common-depth family, envelope CRC leaves only about 2 % 2\% 2% to 4 % 4\% 4% of the target unused, and at α = 0.02 \alpha=0.02 α = 0.02 its risk is within sampling error of the target, so there is almost nothing to recover. In the confidence-adaptive family, CRC leaves between 5 % 5\% 5% and 39 % 39\% 39% unused, and the gains are correspondingly larger. In this family, the gains also shrink as the target grows, partly because more predictions are already as specific as possible: at α = 0.15 \alpha=0.15 α = 0.15 , 86.3 % 86.3\% 86.3% of the baseline predictions are leaves.
The runtimes reflect the two regimes of § 3.5 . The common-depth controller is a single table, built in about 0.2 0.2 0.2 seconds for 500 500 500 rounds and reused across splits and test images. Confidence-adaptive recertification is computed separately for each test image, and 500 500 500 rounds take from about 3 3 3 to 140 140 140 milliseconds per image, with the cost growing in the target.
Improving randomized e-BH
We now return to multiple testing, the setting of the e-closure principle that inspired this work [47 ] , and recertify a randomized version of the e-BH procedure. Let E = ( E 1 , … , E K ) E=(E_1,\ldots,E_K) E = ( E 1 , … , E K ) be e-values for hypotheses H 1 , … , H K H_1,\ldots,H_K H 1 , … , H K , with arbitrary dependence among them. In the framework of § 2 , the state is the unknown set T ⊆ { 1 , … , K } T\subseteq\{1,\ldots,K\} T ⊆ { 1 , … , K } of true nulls, whose class P T \mathcal P_T P T consists of all laws under which E P E j ≤ 1 {\mathbb E}_PE_j\leq1 E P E j ≤ 1 for every j ∈ T j\in T j ∈ T , and errors are measured by the false discovery proportion FDP T ( R ) = ∣ R ∩ T ∣ / ( ∣ R ∣ ∨ 1 ) \operatorname{FDP}_T(R)=|R\cap T|/(|R|\vee1) FDP T ( R ) = ∣ R ∩ T ∣/ ( ∣ R ∣ ∨ 1 ) of a rejection set R R R , with budget α \alpha α . § 4.1 recalls how e-BH fits this framework. § 4.2 casts randomized e-BH as an instance of generalized e-closure, with randomized decisions as actions, and identifies the budget it leaves unused. § 4.3 recertifies it with the e-collection of e-BH, § 4.4 with the larger e-collection of closed e-BH, and § 4.5 reports simulations.
e-BH and self-consistency
For an observed vector e e e , let e [ 1 ] ≥ ⋯ ≥ e [ K ] e_{[1]}\geq\cdots\geq e_{[K]} e [ 1 ] ≥ ⋯ ≥ e [ K ] be its ordered values, let r ( j ) r(j) r ( j ) be the rank of e j e_j e j , and let R k ( e ) R_k(e) R k ( e ) be the set of the k k k hypotheses with the largest e-values, with ties broken by a fixed convention. The e-BH procedure of [44 ] rejects R k ( e ) R_k(e) R k ( e ) for the largest k k k with k e [ k ] ≥ K / α k\,e_{[k]}\geq K/\alpha k e [ k ] ≥ K / α . With rejection sets as actions, its validity is explained by the e-collection
E T e B H = 1 K ∑ j ∈ T E j , \begin{equation}
E^{\mathrm{eBH}}_T=\frac1K\sum_{j\in T}E_j, \tag*{(4.1)}
\end{equation} E T eBH = K 1 j ∈ T ∑ E j , (4.1)
whose expectation under P T \mathcal P_T P T is at most ∣ T ∣ / K ≤ 1 |T|/K\leq1 ∣ T ∣/ K ≤ 1 . Certification generally imposes one constraint for each state, here one for each of the 2 K 2^K 2 K sets of true nulls, but for this e-collection the constraints collapse to K K K simple ones. Since both sides of FDP T ( R ) ≤ α E T e B H \operatorname{FDP}_T(R)\leq\alpha E^{\mathrm{eBH}}_T FDP T ( R ) ≤ α E T eBH are sums over the hypotheses in T T T , the condition holds for every T T T if and only if it holds for every singleton T = { j } T=\{j\} T = { j } , that is, if and only if e j ≥ K / ( α ∣ R ∣ ) e_j\geq K/(\alpha|R|) e j ≥ K / ( α ∣ R ∣ ) for every j ∈ R j\in R j ∈ R . This is the self-consistency condition of [10 ] , which [44 ] used to establish the validity of e-BH under arbitrary dependence. The certified sets are thus exactly the self-consistent ones, and e-BH is the largest of them (Appendix § 8.1 ).
Randomized e-BH as generalized e-closure
The e-BH procedure can be conservative, because an e-value contributes only once it crosses one of the thresholds K / ( α k ) K/(\alpha k) K / ( α k ) , and an e-value just below its threshold is wasted. [45 ] showed that external randomization recovers part of this loss. The most powerful variant in their simulations, U-eBH, draws a single U ∼ U n i f ( 0 , 1 ) U\sim\mathrm{Unif}(0,1) U ∼ Unif ( 0 , 1 ) independent of E E E , boosts the e-values to ( E 1 / U , … , E K / U ) (E_1/U,\ldots,E_K/U) ( E 1 / U , … , E K / U ) , and applies e-BH to the boosted values; that is, it rejects R κ 0 ( E ) R_{\kappa_0}(E) R κ 0 ( E ) with
κ 0 ( e , U ) = max ( { k : U ≤ α k e [ k ] / K } ∪ { 0 } ) . \kappa_0(e,U)=\max\bigl(\{k:U\leq\alpha k\,e_{[k]}/K\}\cup\{0\}\bigr). κ 0 ( e , U ) = max ( { k : U ≤ α k e [ k ] / K } ∪ { 0 } ) .
U-eBH rejects at least the e-BH set for every value of U U U and controls the FDR at level α \alpha α . Its validity is not a consequence of applying e-BH to e-values, since E j / U E_j/U E j / U has infinite expectation whenever P ( E j > 0 ) > 0 \mathbb P(E_j>0)>0 P ( E j > 0 ) > 0 , but it becomes transparent once the randomization is made part of the action. A second variant, J-eBH, divides each e-value by its own uniform random variable drawn independently of the others and of E E E , and applies e-BH to the boosted values; it is also valid (Appendix § 8.3 ).
3.25ex -1em Actions and losses. Like e-BH, U-eBH rejects the hypotheses with the largest e-values, and only the number of rejections is random. We therefore consider monotone rules, which reject R κ ( e ) R_\kappa(e) R κ ( e ) for a random number κ \kappa κ of rejections, and take an action to be a distribution p = ( p 0 , … , p K ) p=(p_0,\ldots,p_K) p = ( p 0 , … , p K ) of κ \kappa κ . A boosting rule chooses such a distribution p ( e ) p(e) p ( e ) after observing the e-values, draws κ ∼ p ( e ) \kappa\sim p(e) κ ∼ p ( e ) independently of the data, and rejects R κ ( e ) R_\kappa(e) R κ ( e ) . The loss of the action p p p in state T T T is the false discovery proportion averaged over this draw,
L ˉ ( T , p ; e ) = ∑ k = 1 K p k ∣ T ∩ R k ( e ) ∣ k . \begin{equation}
\bar L(T,p;e)=\sum_{k=1}^Kp_k\,\frac{|T\cap R_k(e)|}{k}. \tag*{(4.2)}
\end{equation} L ˉ ( T , p ; e ) = k = 1 ∑ K p k k ∣ T ∩ R k ( e ) ∣ . (4.2)
This loss depends on the observation through the ranking of the e-values, which the framework of § 2 allows, and a boosting rule is valid in the sense of (2.1) exactly when the procedure it implements controls the FDR at level α \alpha α . Randomization can thus also be viewed as part of the action, with probability distributions as the actions, as described in § 2.2 . U-eBH is the boosting rule whose distribution p 0 ( e ) p^0(e) p 0 ( e ) has the tails
P ( κ 0 ≥ r ∣ E = e ) = min { 1 , α K max k ≥ r k e [ k ] } , r = 1 , … , K . \begin{equation}
\mathbb P(\kappa_0\geq r\mid E=e)=\min\left\{1,\frac\alpha K\max_{k\geq r}k\,e_{[k]}\right\},\qquad r=1,\ldots,K. \tag*{(4.3)}
\end{equation} P ( κ 0 ≥ r ∣ E = e ) = min { 1 , K α k ≥ r max k e [ k ] } , r = 1 , … , K . (4.3)
Indeed, dividing every e-value by the same U U U preserves their ranking, so e-BH applied to the boosted values rejects k k k hypotheses when k k k is the largest number satisfying k e [ k ] / U ≥ K / α k\,e_{[k]}/U\geq K/\alpha k e [ k ] / U ≥ K / α , that is, U ≤ α k e [ k ] / K U\leq\alpha k\,e_{[k]}/K U ≤ α k e [ k ] / K . Hence κ 0 ≥ r \kappa_0\geq r κ 0 ≥ r exactly when U ≤ α k e [ k ] / K U\leq\alpha k\,e_{[k]}/K U ≤ α k e [ k ] / K for some k ≥ r k\geq r k ≥ r , equivalently when U ≤ ( α / K ) max k ≥ r k e [ k ] U\leq(\alpha/K)\max_{k\geq r}k\,e_{[k]} U ≤ ( α / K ) max k ≥ r k e [ k ] , and because U U U is uniform on ( 0 , 1 ) (0,1) ( 0 , 1 ) and independent of E E E , this event has the conditional probability (4.3) .
3.25ex -1em The certified menu. The hypothesis of rank r r r is rejected exactly when κ ≥ r \kappa\geq r κ ≥ r , and it then receives the share 1 / κ 1/\kappa 1/ κ of the false discovery proportion, if it is null. The loss (4.2) therefore splits over the hypotheses in T T T ,
L ˉ ( T , p ; e ) = ∑ j ∈ T c [ r ( j ) ] ( p ) , c [ r ] ( p ) = ∑ k ≥ r p k k , \bar L(T,p;e)=\sum_{j\in T}c_{[r(j)]}(p),\qquad c_{[r]}(p)=\sum_{k\geq r}\frac{p_k}{k}, L ˉ ( T , p ; e ) = j ∈ T ∑ c [ r ( j )] ( p ) , c [ r ] ( p ) = k ≥ r ∑ k p k ,
where c [ r ] ( p ) c_{[r]}(p) c [ r ] ( p ) is the expected share charged to the hypothesis of rank r r r , should it be null. Both sides of L ˉ ( T , p ; e ) ≤ α E T e B H ( e ) \bar L(T,p;e)\leq\alpha E^{\mathrm{eBH}}_T(e) L ˉ ( T , p ; e ) ≤ α E T eBH ( e ) are again sums over the hypotheses in T T T , so the reduction of § 4.1 applies verbatim, and the certified menu of E e B H E^{\mathrm{eBH}} E eBH at e e e is
C α ( E e B H ; e ) = { p : c [ r ] ( p ) ≤ α K e [ r ] for r = 1 , … , K } . \begin{equation}
\mathcal C_\alpha(E^{\mathrm{eBH}};e)=\Bigl\{p:\ c_{[r]}(p)\leq\frac\alpha K\,e_{[r]}\ \text{ for } r=1,\ldots,K\Bigr\}. \tag*{(4.4)}
\end{equation} C α ( E eBH ; e ) = { p : c [ r ] ( p ) ≤ K α e [ r ] for r = 1 , … , K } . (4.4)
Each hypothesis may thus be charged at most its own share of the budget, a self-consistency condition that need only hold on average over the randomization. The menu is a polytope of distributions, and by Theorem 2.1 every boosting rule that selects from it has FDR at most α ∣ T ∣ / K ≤ α \alpha|T|/K\leq\alpha α ∣ T ∣/ K ≤ α .
U-eBH selects from the menu (4.4) , which proves its validity, but its distribution usually satisfies the constraints with strict inequality. An intuitive explanation is that the common boosting factor U U U does not respect the different slack structures. Indeed, dividing every e-value by the same U U U ties the hypotheses together: U-eBH rejects at least r r r hypotheses when e-BH, applied to the boosted values, selects some set R k ( e ) R_k(e) R k ( e ) with k ≥ r k\geq r k ≥ r , which happens when U ≤ α k e [ k ] / K U\leq\alpha k\,e_{[k]}/K U ≤ α k e [ k ] / K and therefore depends only on the smallest e-value e [ k ] e_{[k]} e [ k ] in that set. As a result, a hypothesis can be charged as if its e-value were that of a lower-ranked hypothesis, and part of its budget then goes unused (Appendix § 8.1 ).
Recertifying U-eBH
Recertification spends this unused budget. Like every valid rule, U-eBH is certified by its canonical e-collection, its averaged loss divided by the budget, L ˉ ( T , p 0 ( e ) ; e ) / α \bar L(T,p^0(e);e)/\alpha L ˉ ( T , p 0 ( e ) ; e ) / α . As shown above, this e-collection lies below E e B H E^{\mathrm{eBH}} E eBH , hypothesis by hypothesis, and the gap is exactly the unused budget. Recertification replaces the canonical e-collection by the larger e-collection E e B H E^{\mathrm{eBH}} E eBH . This step involves no unknown conditional expectation: the input e-values supply the budget directly, and the averaged losses are known because the law of the external randomization is known (Appendix § 8.1 spells out the correspondence with Proposition 2.2 ). The certified menu of the recertified e-collection is (4.4) . It contains U-eBH, but also distributions that do not arise from boosting all e-values by a common factor, and any of them may be selected. We select the one that rejects the most.
To find this distribution, we turn the budget constraints in (4.4) , which bound the charges of individual hypotheses, into bounds on the quantities that measure power: the probabilities P ( κ ≥ r ) \mathbb P(\kappa\geq r) P ( κ ≥ r ) of rejecting at least r r r hypotheses. Recall that the hypothesis of rank j j j is rejected exactly when κ ≥ j \kappa\geq j κ ≥ j , and then receives the share 1 / κ 1/\kappa 1/ κ , so its charge is c [ j ] ( p ) = E [ 1 { κ ≥ j } / κ ] c_{[j]}(p)={\mathbb E}[\mathop{\mathrm{\mathds{1}}}\{\kappa\geq j\}/\kappa] c [ j ] ( p ) = E [ 1 { κ ≥ j } / κ ] . On an event { κ = k } \{\kappa=k\} { κ = k } with k ≥ r k\geq r k ≥ r , the shares of the k k k rejected hypotheses sum to one: the top r r r hypotheses receive r / k r/k r / k together, and each hypothesis of rank j ∈ { r + 1 , … , k } j\in\{r+1,\ldots,k\} j ∈ { r + 1 , … , k } receives 1 / k 1/k 1/ k . Averaging over the events { κ = k } \{\kappa=k\} { κ = k } with k ≥ r k\geq r k ≥ r , the first part contributes r E [ 1 { κ ≥ r } / κ ] = r c [ r ] ( p ) r\,{\mathbb E}[\mathop{\mathrm{\mathds{1}}}\{\kappa\geq r\}/\kappa]=r\,c_{[r]}(p) r E [ 1 { κ ≥ r } / κ ] = r c [ r ] ( p ) , and the second contributes ∑ j > r E [ 1 { κ ≥ j } / κ ] = ∑ j > r c [ j ] ( p ) \sum_{j>r}{\mathbb E}[\mathop{\mathrm{\mathds{1}}}\{\kappa\geq j\}/\kappa]=\sum_{j>r}c_{[j]}(p) ∑ j > r E [ 1 { κ ≥ j } / κ ] = ∑ j > r c [ j ] ( p ) , because a hypothesis of rank j > r j>r j > r is rejected only on these events. Hence
P ( κ ≥ r ) = r c [ r ] ( p ) + ∑ j > r c [ j ] ( p ) . \mathbb P(\kappa\geq r)=r\,c_{[r]}(p)+\sum_{j>r}c_{[j]}(p). P ( κ ≥ r ) = r c [ r ] ( p ) + j > r ∑ c [ j ] ( p ) .
Bounding each charge by its budget now bounds the probability of rejecting at least r r r hypotheses directly. The top r r r hypotheses can contribute at most r r r times the budget of the hypothesis of rank r r r , and each lower-ranked hypothesis at most its own budget. Every distribution in the certified menu (4.4) therefore obeys
P ( κ ≥ r ∣ E = e ) ≤ q r ∗ ( e ) = min { 1 , α K ( r e [ r ] + ∑ j > r e [ j ] ) } , r = 1 , … , K . \begin{equation}
\mathbb P(\kappa\geq r\mid E=e)\leq q^*_r(e)=\min\left\{1,\frac\alpha K\Bigl(r\,e_{[r]}+\sum_{j>r}e_{[j]}\Bigr)\right\},\qquad r=1,\ldots,K. \tag*{(4.5)}
\end{equation} P ( κ ≥ r ∣ E = e ) ≤ q r ∗ ( e ) = min { 1 , K α ( r e [ r ] + j > r ∑ e [ j ] ) } , r = 1 , … , K . (4.5)
These bounds depend on the e-values alone, and a single distribution attains all K K K of them at once; when ( α / K ) ∑ j e j ≤ 1 (\alpha/K)\sum_je_j\leq1 ( α / K ) ∑ j e j ≤ 1 , it makes every constraint in (4.4) tight (Appendix § 8.2 ). The recertified rule selects this distribution and implements it with the seed of U-eBH, as summarized in Algorithm alg:rebh . Computation requires only sorting the e-values and forming partial sums. U-eBH also selects from the menu, so its tails (4.3) lie below q r ∗ q^*_r q r ∗ – they value the k k k rejected hypotheses as if each had the smallest e-value among them.
\fontsize{10}{12}\selectfont
\caption{Recertified U-eBH}\label{alg:rebh}
\begin{algorithmic}[1]
\REQUIRE E-values $e_1,\ldots,e_K$, level $\alpha$, and $U\sim\mathrm{Unif}(0,1)$ drawn independently of the e-values.
\STATE Order the e-values as $e_{[1]}\geq\cdots\geq e_{[K]}$, with ties broken by a fixed convention.
\STATE Compute the partial sums $s_r=\sum_{j=r}^Ke_{[j]}$ for $r=1,\ldots,K$, and set $s_{K+1}=0$.
\FOR{$r=1,\ldots,K$}
\STATE Set $q^*_r=\min\{1,(\alpha/K)(r\,e_{[r]}+s_{r+1})\}$.
\ENDFOR
\STATE Set $\kappa^*=\max(\{r:U\leq q^*_r\}\cup\{0\})$.
\ENSURE The rejection set $R_{\kappa^*}(e)$, consisting of the $\kappa^*$ hypotheses with the largest e-values.
\end{algorithmic}
The following proposition collects the properties of the recertified rule, which we regard as recertified randomized e-BH or, more precisely, recertified U-eBH (RU-eBH).
Proposition 4.1 (Recertified U-eBH). RU-eBH has the following properties.
Its FDR is at most α ∣ T ∣ / K ≤ α \alpha|T|/K\leq\alpha α ∣ T ∣/ K ≤ α in every state T T T and under every law in P T \mathcal P_T P T .
It contains the U-eBH rejection set, and hence the e-BH rejection set, for every e e e and U U U .
Among boosting rules that select from (4.4) , it has the stochastically largest number of rejections: P ( κ ≥ r ∣ E = e ) ≤ P ( κ ∗ ≥ r ∣ E = e ) \mathbb P(\kappa\geq r\mid E=e)\leq\mathbb P(\kappa^*\geq r\mid E=e) P ( κ ≥ r ∣ E = e ) ≤ P ( κ ∗ ≥ r ∣ E = e ) for every r r r and e e e .
In particular, the probability of rejecting at least one hypothesis rises from ( α / K ) max k k e [ k ] (\alpha/K)\max_kk\,e_{[k]} ( α / K ) max k k e [ k ] to ( α / K ) ∑ j e j (\alpha/K)\sum_je_j ( α / K ) ∑ j e j , capped at one. RU-eBH draws on the budget of every hypothesis, whereas U-eBH draws on that of a single rejection set. We also note that restricting attention to monotone rules costs nothing in the expected number of rejections: for every e e e , no randomized rule over arbitrary rejection sets that is certified by E e B H E^{\mathrm{eBH}} E eBH rejects more hypotheses in expectation than RU-eBH, although such rules need not be stochastically smaller (Proposition C.3 in Appendix § 8.3 ). Finally, RU-eBH can be written as e-BH applied to the randomized e-values ( K / α ) 1 { j ∈ R κ ∗ } / ( ∣ R κ ∗ ∣ ∨ 1 ) (K/\alpha)\mathop{\mathrm{\mathds{1}}}\{j\in R_{\kappa^*}\}/(|R_{\kappa^*}|\vee1) ( K / α ) 1 { j ∈ R κ ∗ } / ( ∣ R κ ∗ ∣ ∨ 1 ) (Corollary C.2 ).
Recertifying closed e-BH
The optimality in Proposition 4.1 is relative to the e-collection E e B H E^{\mathrm{eBH}} E eBH , and a larger e-collection permits a further improvement. A simple example exploits the fact that the bound α ∣ T ∣ / K \alpha|T|/K α ∣ T ∣/ K in Proposition 4.1 (i) is strictly below α \alpha α unless every hypothesis is null. The minimally adaptive principle [35 , 23 ] uses this slack: it runs a procedure at the inflated level K α / ( K − 1 ) K\alpha/(K-1) K α / ( K − 1 ) , but only when the procedure at level α \alpha α rejects at least one hypothesis, which keeps the FDR under the global null at most α \alpha α . In our framework, this corresponds to replacing 1 / K 1/K 1/ K by 1 / ( K − 1 ) 1/(K-1) 1/ ( K − 1 ) in (4.1) for every state other than the full set, which still gives an e-collection because such a state contains at most K − 1 K-1 K − 1 true nulls. Applying recertification to this collection would therefore yield a more powerful rule, and, as a result, RU-eBH is not admissible among all FDR procedures (Appendix § 8.5 ).
A much larger e-collection is introduced by [47 ] ,
E T e B H ‾ = 1 ∣ T ∣ ∑ j ∈ T E j ( T ≠ ∅ ) , \begin{equation}
E^{\overline{\mathrm{eBH}}}_T=\frac1{|T|}\sum_{j\in T}E_j\qquad(T\neq\varnothing), \tag*{(4.6)}
\end{equation} E T eBH = ∣ T ∣ 1 j ∈ T ∑ E j ( T = ∅ ) , (4.6)
whose expectation under P T \mathcal P_T P T is at most one and which certifies the rejection set of closed e-BH. It normalizes by the number of true nulls rather than by K K K , and thus adapts to the unknown proportion of true nulls.
For a monotone rule, the averaged false discovery proportion in state T T T is still the sum ∑ j ∈ T c [ r ( j ) ] ( p ) \sum_{j\in T}c_{[r(j)]}(p) ∑ j ∈ T c [ r ( j )] ( p ) of the charges, but the budget α E T e B H ‾ \alpha E^{\overline{\mathrm{eBH}}}_T α E T eBH no longer splits into budgets for individual hypotheses. The certified menu of E e B H ‾ E^{\overline{\mathrm{eBH}}} E eBH at e e e therefore consists of the distributions p p p that satisfy all 2 K − 1 2^K-1 2 K − 1 constraints
which do not reduce to K K K separate ones.
Nevertheless, the menu has enough structure that the rule with the largest expected number of rejections can be found in closed form. The key is to describe a monotone rule by its cumulative charges from the bottom. Let S s ( p ) = ∑ r ≥ s c [ r ] ( p ) S_s(p)=\sum_{r\geq s}c_{[r]}(p) S s ( p ) = ∑ r ≥ s c [ r ] ( p ) be the total charge of the K − s + 1 K-s+1 K − s + 1 hypotheses with the smallest e-values. A hypothesis is rejected whenever a lower-ranked one is, with the same share, so the charges are non-increasing in the rank and s ↦ S s ( p ) s\mapsto S_s(p) s ↦ S s ( p ) is convex. Conversely, every non-increasing convex sequence with S K + 1 = 0 S_{K+1}=0 S K + 1 = 0 and S 1 ≤ 1 S_1\leq1 S 1 ≤ 1 arises from a unique distribution p p p . The constraint (4.7) for the set { s , … , K } \{s,\ldots,K\} { s , … , K } caps S s ( p ) S_s(p) S s ( p ) at α m s \alpha m_s α m s , where m s = ( K − s + 1 ) − 1 ∑ j ≥ s e [ j ] m_s=(K-s+1)^{-1}\sum_{j\geq s}e_{[j]} m s = ( K − s + 1 ) − 1 ∑ j ≥ s e [ j ] is the mean e-value of that set, and S 1 ( p ) = P ( κ ≥ 1 ) S_1(p)=\mathbb P(\kappa\geq1) S 1 ( p ) = P ( κ ≥ 1 ) is also at most one. Let β 1 = min { 1 , α m 1 } \beta_1=\min\{1,\alpha m_1\} β 1 = min { 1 , α m 1 } , β s = α m s \beta_s=\alpha m_s β s = α m s for 2 ≤ s ≤ K 2\leq s\leq K 2 ≤ s ≤ K and β K + 1 = 0 \beta_{K+1}=0 β K + 1 = 0 . These caps need not form a convex sequence, but among the convex sequences below them there is a pointwise largest one, their greatest convex minorant S ♯ S^\sharp S ♯ , which is the lower convex hull of the points ( s , β s ) (s,\beta_s) ( s , β s ) . Since the expected number of rejections, S 1 ( p ) + 2 ∑ s ≥ 2 S s ( p ) S_1(p)+2\sum_{s\geq2}S_s(p) S 1 ( p ) + 2 ∑ s ≥ 2 S s ( p ) , increases with every S s ( p ) S_s(p) S s ( p ) , we take the rule whose cumulative charges are S ♯ S^\sharp S ♯ ; Proposition 4.2 shows that it satisfies all the other constraints in (4.7) as well. Its tails are
q r ♯ = r S r ♯ − ( r − 1 ) S r + 1 ♯ , r = 1 , … , K . \begin{equation}
q^\sharp_r=r\,S^\sharp_r-(r-1)\,S^\sharp_{r+1},\qquad r=1,\ldots,K. \tag*{(4.8)}
\end{equation} q r ♯ = r S r ♯ − ( r − 1 ) S r + 1 ♯ , r = 1 , … , K . (4.8)
Geometrically, q r ♯ q^\sharp_r q r ♯ is the value at s = 1 s=1 s = 1 of the line that extends the segment of the minorant over [ r , r + 1 ] [r,r+1] [ r , r + 1 ] ; the same construction applied to the convex sequence ( α / K ) ∑ j ≥ s e [ j ] (\alpha/K)\sum_{j\geq s}e_{[j]} ( α / K ) ∑ j ≥ s e [ j ] of cumulative budgets of E e B H E^{\mathrm{eBH}} E eBH gives the bounds q r ∗ q^*_r q r ∗ of (4.5) before capping. We call the resulting procedure recertified closed e-BH (RC-eBH), since it is certified by the e-collection of closed e-BH. It replaces q r ∗ q^*_r q r ∗ by q r ♯ q^\sharp_r q r ♯ in Algorithm alg:rebh , that is, it rejects R κ ♯ ( e ) R_{\kappa^\sharp}(e) R κ ♯ ( e ) with κ ♯ = max ( { r : U ≤ q r ♯ } ∪ { 0 } ) \kappa^\sharp=\max(\{r:U\leq q^\sharp_r\}\cup\{0\}) κ ♯ = max ({ r : U ≤ q r ♯ } ∪ { 0 }) . Since the points ( s , β s ) (s,\beta_s) ( s , β s ) are ordered in s s s , the minorant is computed in O ( K ) O(K) O ( K ) operations once the e-values are sorted.
Proposition 4.2 (Recertified closed e-BH). RC-eBH has the following properties.
Its FDR is at most α \alpha α in every state T T T and under every law in P T \mathcal P_T P T .
Its tails satisfy q r ♯ ≥ q r ∗ q^\sharp_r\geq q^*_r q r ♯ ≥ q r ∗ for every r r r , so it contains the rejection set of RU-eBH, and hence those of U-eBH and e-BH, for every e e e and U U U .
Among all randomized rules that select from the certified menu of E e B H ‾ E^{\overline{\mathrm{eBH}}} E eBH , monotone or not, it has the largest expected number of rejections given E = e E=e E = e . In particular, it rejects at least as many hypotheses in expectation as closed e-BH.
The proof, which we defer to Appendix § 8.4 , shows that, for the charges of the minorant, the hardest constraints of each size are those for the sets of lowest-ranked hypotheses, so the constraints for these sets imply all others in (4.7) . Unlike the menu of E e B H E^{\mathrm{eBH}} E eBH , the menu of the mean e-collection generally has no stochastically largest element, which is why part (iii) concerns the expected number of rejections. Whereas the FDR of RU-eBH is bounded by α ∣ T ∣ / K \alpha|T|/K α ∣ T ∣/ K , that of RC-eBH is bounded by α \alpha α .
Simulations
We compare RU-eBH and RC-eBH with six procedures that, like them, control the FDR under arbitrary dependence. Four are deterministic: e-BH, its minimally adaptive version (MA-eBH) [23 ] , closed e-BH [47 ] and anchored e-BH [33 ] . Two are randomized: U-eBH [45 ] and J-eBH (§ 4.2 ).
There are K = 100 K=100 K = 100 hypotheses, of which 10 10 10 , 50 50 50 or 90 90 90 are false. For each hypothesis we observe a Gaussian statistic Z j Z_j Z j with unit variance, mean 0 0 0 under the null and a common signal mean between 1 1 1 and 4 4 4 otherwise; the statistics are equicorrelated with correlation ρ ∈ { 0 , 0.5 , 0.9 } \rho\in\{0,0.5,0.9\} ρ ∈ { 0 , 0.5 , 0.9 } . All methods use the same e-values, the likelihood ratios E j = exp ( 2 Z j − 2 ) E_j=\exp(2Z_j-2) E j = exp ( 2 Z j − 2 ) of N ( 2 , 1 ) N(2,1) N ( 2 , 1 ) against N ( 0 , 1 ) N(0,1) N ( 0 , 1 ) , at level α = 0.1 \alpha=0.1 α = 0.1 . We report power, the expected fraction of false nulls that are rejected, and the FDR, each averaged over 50,000 50{,}000 50 , 000 data sets. Figure 3 shows all settings. The standard errors are very small, at most 0.0023 0.0023 0.0023 for power and 0.0013 0.0013 0.0013 for the FDR, so they are not shown.
Figure 3. Power and FDR of RU-eBH, RC-eBH and six other procedures that are valid under arbitrary dependence, with 10 10 10 , 50 50 50 and 90 90 90 false nulls among K = 100 K=100 K = 100 hypotheses at α = 0.1 \alpha=0.1 α = 0.1 and three levels of correlation (columns). Each point averages 50,000 50{,}000 50 , 000 data sets. The dotted lines mark α \alpha α .
With 10 10 10 false nulls, RU-eBH and RC-eBH are the most powerful methods in every panel, and they nearly coincide. At signal mean 2.5 2.5 2.5 with independent statistics, for example, RU-eBH has power 0.32 0.32 0.32 , compared with 0.22 0.22 0.22 for U-eBH and J-eBH and at most 0.06 0.06 0.06 for the deterministic procedures. Its FDR stays close to the bound α ∣ T ∣ / K = 0.09 \alpha|T|/K=0.09 α ∣ T ∣/ K = 0.09 of Proposition 4.1 with independent statistics, whereas the FDR of U-eBH is between about 40 % 40\% 40% and 70 % 70\% 70% of this bound, which reflects the budget that U-eBH leaves unused. J-eBH has nearly the same FDR as RU-eBH but much lower power, so the gain of RU-eBH also comes from how it allocates the budget rather than from how much of the budget it spends.
With more false nulls, RU-eBH remains at least as powerful as U-eBH and J-eBH, but the deterministic procedures based on larger e-collections catch up. With 50 50 50 false nulls and independent statistics, closed and anchored e-BH are more powerful than RU-eBH at strong signals, and with 90 90 90 false nulls, closed e-BH is more powerful at moderate and strong signals unless the correlation is high. This is consistent with the theory: the optimality of RU-eBH is relative to E e B H E^{\mathrm{eBH}} E eBH , which normalizes by K K K , whereas closed e-BH is certified by the mean e-collection, which normalizes by ∣ T ∣ |T| ∣ T ∣ and is much larger when few hypotheses are null. RC-eBH, which is certified by the same e-collection as closed e-BH, removes this gap. As part (ii) of Proposition 4.2 guarantees, it is more powerful than RU-eBH in every setting, and the gain grows with the number of false nulls; with 90 90 90 false nulls, independent statistics and signal mean 2 2 2 , its power is 0.64 0.64 0.64 , compared with 0.52 0.52 0.52 for RU-eBH and 0.55 0.55 0.55 for closed e-BH. It is the most powerful of all eight methods, except at the strongest signals with independent statistics, where several methods reject nearly all false nulls and it trails the best of them by less than 0.005 0.005 0.005 . Its FDR stays below α \alpha α but exceeds α ∣ T ∣ / K \alpha|T|/K α ∣ T ∣/ K when many hypotheses are false, as the mean e-collection permits.
Discussion
In both applications, recertification enlarges the menu of certified actions, and we selected its most liberal element – the least conservative controller in CRC, and the boosting rule that rejects the most hypotheses in multiple testing. Nothing in the framework requires this choice. By Theorem 2.1 , every data-dependent selection from a certified menu is valid, so one may instead select the action that maximizes a utility, for instance a posterior expected utility under a prior. Such a selection is Bayes optimal among selections from the menu, and its validity does not depend on the prior. This differs from the constrained problems of [43 ] and [22 ] , which optimize a single rule subject to the risk constraints and, by Theorem 2.1 , amount to optimizing the e-collection and the selection jointly. Similarly, our admissibility results compare procedures on every calibration sample or conditionally on the e-values; they do not address classical risk admissibility, which allows a rule to trade larger losses at some observations for smaller losses at others.
In summary, this paper formulates the e-closure principle for general decision problems and uses the resulting correspondence constructively. Recertification starts by measuring the budget that a valid procedure leaves unused, spends it through larger e-values, and inverts them into an improved procedure with the same guarantee. The source of this budget differs between our two applications. In conformal risk control, exchangeability makes the budget computable on every hypothetical augmented sample, and recertification yields pointwise improvements of CRC and an admissible limit. In multiple testing, the e-values themselves supply the budget once randomized procedures are treated as randomized actions, and recertifying U-eBH yields two closed-form procedures, RU-eBH and RC-eBH, each optimal among the procedures certified by its e-collection.
The two applications also differ in cost. RU-eBH and RC-eBH require only sorting the e-values and, for RC-eBH, a convex minorant, whereas repeated recertification of CRC trades computation for a uniform improvement, with diminishing returns, and can be expensive when the controller depends on individual scores. Exploiting the structure of the loss and the data to compute stronger certificates economically remains an important practical question, and whether RC-eBH is admissible among all FDR procedures is open. More broadly, any procedure whose validity proof leaves an identifiable budget unused is a candidate for recertification, and we expect further applications of this kind, especially those with more complex states, actions or loss structures.
Measurability of the certified menu
The proof of Theorem 2.1 fixes one state–loss pair before taking expectations, so it requires only that the rule and the losses be measurable. The certified menu is different: it intersects possibly uncountably many constraints, which in general need not produce a Borel graph, and selecting from it requires measurable selections. The following conditions are sufficient, though not necessary.
Proposition A.1. Suppose that X \mathcal X X is standard Borel, S \mathcal S S and T \mathcal T T are separable metric spaces, and A \mathcal A A is a compact metric space. Suppose that the losses and the e-collection are finite, that α t ( s ) > 0 \alpha_t(s)>0 α t ( s ) > 0 , and that both L t ( s , a ; x ) L_t(s,a;x) L t ( s , a ; x ) and
f ( x , s , t , a ) = L t ( s , a ; x ) − α t ( s ) E s , t ( x ) f(x,s,t,a)=L_t(s,a;x)-\alpha_t(s)E_{s,t}(x) f ( x , s , t , a ) = L t ( s , a ; x ) − α t ( s ) E s , t ( x ) are Borel in x x x for each fixed ( s , t , a ) (s,t,a) ( s , t , a ) and continuous in ( s , t , a ) (s,t,a) ( s , t , a ) for each fixed x x x . If the certified menu is nonempty for every x x x , then it has a Borel graph and nonempty compact values, and it admits a Borel selection. A utility v ( x , a ) v(x,a) v ( x , a ) that is Borel in x x x and continuous in a a a has a Borel maximizing selection from the menu. Every loss envelope of the menu is Borel in x x x and continuous in ( s , t ) (s,t) ( s , t ) .
Proof. Choose a countable dense set { ( s j , t j ) : j ≥ 1 } \{(s_j,t_j):j\geq1\} {( s j , t j ) : j ≥ 1 } in S × T \mathcal S\times\mathcal T S × T . By continuity,
C α ( E ; x ) = ⋂ j ≥ 1 { a : f ( x , s j , t j , a ) ≤ 0 } . \mathcal C_\alpha(E;x)=\bigcap_{j\geq1}\{a:f(x,s_j,t_j,a)\leq0\}. C α ( E ; x ) = j ≥ 1 ⋂ { a : f ( x , s j , t j , a ) ≤ 0 } . Each constraint is jointly Borel in ( x , a ) (x,a) ( x , a ) , so the graph is Borel, and its sections are closed, hence compact. The Arsenin–Kunugui theorem [37 Theorem 5.12.1] then gives a Borel selection. For a utility v v v , the sets { ( x , a ) : a ∈ C α ( E ; x ) , v ( x , a ) > b } \{(x,a):a\in\mathcal C_\alpha(E;x),\ v(x,a)>b\} {( x , a ) : a ∈ C α ( E ; x ) , v ( x , a ) > b } have σ \sigma σ -compact sections, so their projections are Borel by the same theorem, and the maximum value is Borel in x x x . The maximizing graph is therefore Borel with nonempty compact sections, and a further application gives a maximizing selection. The envelopes are Borel by the same argument applied to each fixed-pair loss, and continuous in ( s , t ) (s,t) ( s , t ) as maxima of jointly continuous functions over the compact set C α ( E ; x ) \mathcal C_\alpha(E;x) C α ( E ; x ) . ◻
Details for conformal risk control
CRC through e-closure
We work in the formulation of § 3.3 , in which a state is an augmented multiset S = ( z 1 , … , z n + 1 ) S=(z_1,\ldots,z_{n+1}) S = ( z 1 , … , z n + 1 ) and P S \mathcal P_S P S deletes a uniformly random point of S S S . For a fixed action λ \lambda λ , the losses ℓ ( z i , λ ) \ell(z_i,\lambda) ℓ ( z i , λ ) act as scores of the points of S S S , and
E S λ ( D ) = ( n + 1 ) ℓ ( S ∖ D , λ ) ∑ i = 1 n + 1 ℓ ( z i , λ ) ( D ⊆ S ) , E^\lambda_S(D)=\frac{(n+1)\,\ell(S\setminus D,\lambda)}{\sum_{i=1}^{n+1}\ell(z_i,\lambda)}\qquad(D\subseteq S), E S λ ( D ) = ∑ i = 1 n + 1 ℓ ( z i , λ ) ( n + 1 ) ℓ ( S ∖ D , λ ) ( D ⊆ S ) ,
with 0 / 0 = 0 0/0=0 0/0 = 0 , is the conformal e-value of the held-out point [40 , 27 ] . Its expectation under P S \mathcal P_S P S is at most one, so E λ E^\lambda E λ is an e-collection for each fixed λ \lambda λ .
Theorem 2.1 certifies all actions with a single e-collection. Here we instead allow each action λ \lambda λ to be certified by its own e-values E λ E^\lambda E λ , and consider, at an observed D D D , the actions that satisfy
ℓ ( z , λ ) ≤ α E D ∪ { z } λ ( D ) for every z ∈ Z . \begin{equation}
\ell(z,\lambda)\leq\alpha E^\lambda_{D\cup\{z\}}(D)\qquad\text{for every }z\in\mathcal Z. \tag*{(7.1)}
\end{equation} ℓ ( z , λ ) ≤ α E D ∪ { z } λ ( D ) for every z ∈ Z . (7.1)
The constraint is trivial when ℓ ( z , λ ) = 0 \ell(z,\lambda)=0 ℓ ( z , λ ) = 0 , and otherwise it reads ∑ i = 1 n ℓ ( Z i , λ ) + ℓ ( z , λ ) ≤ ( n + 1 ) α \sum_{i=1}^n\ell(Z_i,\lambda)+\ell(z,\lambda)\leq(n+1)\alpha ∑ i = 1 n ℓ ( Z i , λ ) + ℓ ( z , λ ) ≤ ( n + 1 ) α . Hence (7.1) holds if and only if
∑ i = 1 n ℓ ( Z i , λ ) + U ∗ ( λ ) ≤ ( n + 1 ) α , U ∗ ( λ ) = sup z ∈ Z ℓ ( z , λ ) , \sum_{i=1}^n\ell(Z_i,\lambda)+U^*(\lambda)\leq(n+1)\alpha,\qquad U^*(\lambda)=\sup_{z\in\mathcal Z}\ell(z,\lambda), i = 1 ∑ n ℓ ( Z i , λ ) + U ∗ ( λ ) ≤ ( n + 1 ) α , U ∗ ( λ ) = z ∈ Z sup ℓ ( z , λ ) ,
which is the envelope CRC test (3.3) with the sharp envelope U ∗ U^* U ∗ , non-increasing and right-continuous as a supremum of such functions. A larger envelope U U U , or the constant B B B of standard CRC, replaces the unobserved test loss ℓ ( z , λ ) \ell(z,\lambda) ℓ ( z , λ ) in the denominator of E λ E^\lambda E λ by an upper bound and gives a more stringent test. Envelope CRC and CRC therefore also select actions that satisfy (7.1) .
In general, letting the e-values depend on the action is not valid: choosing the action after seeing the data then amounts to choosing among e-values, which inflates them. The conformal case avoids this due to a cancellation. Under P S \mathcal P_S P S the augmented sample S S S is fixed, and the data reveal only which of its points is held out. For a held-out point with positive loss, the constraint in (7.1) reads ∑ j = 1 n + 1 ℓ ( z j , λ ) ≤ ( n + 1 ) α \sum_{j=1}^{n+1}\ell(z_j,\lambda)\leq(n+1)\alpha ∑ j = 1 n + 1 ℓ ( z j , λ ) ≤ ( n + 1 ) α , whichever point z z z is held out. Whether an action passes is thus decided by the state alone, and the data cannot be used to choose among the e-values. Formally, let
λ ∗ ( S ) = min { λ ∈ Λ : ∑ j = 1 n + 1 ℓ ( z j , λ ) ≤ ( n + 1 ) α } \lambda^*(S)=\min\left\{\lambda\in\Lambda:\sum_{j=1}^{n+1}\ell(z_j,\lambda)\leq (n+1)\alpha\right\} λ ∗ ( S ) = min { λ ∈ Λ : j = 1 ∑ n + 1 ℓ ( z j , λ ) ≤ ( n + 1 ) α }
be the smallest action that passes on S S S . Since λ ∗ ( S ) \lambda^*(S) λ ∗ ( S ) is permutation invariant in S S S , the values E S ∗ ( D ) = E S λ ∗ ( S ) ( D ) E^*_S(D)=E^{\lambda^*(S)}_S(D) E S ∗ ( D ) = E S λ ∗ ( S ) ( D ) form a single e-collection. If λ \lambda λ satisfies (7.1) at D D D and ℓ ( z , λ ) > 0 \ell(z,\lambda)>0 ℓ ( z , λ ) > 0 , then λ ≥ λ ∗ ( S ) \lambda\geq\lambda^*(S) λ ≥ λ ∗ ( S ) for S = D ∪ { z } S=D\cup\{z\} S = D ∪ { z } , and hence
ℓ ( z , λ ) ≤ ℓ ( z , λ ∗ ( S ) ) ≤ α E S ∗ ( D ) , \ell(z,\lambda)\leq\ell(z,\lambda^*(S))\leq\alpha E^*_S(D), ℓ ( z , λ ) ≤ ℓ ( z , λ ∗ ( S )) ≤ α E S ∗ ( D ) ,
where the second inequality uses ∑ j ℓ ( z j , λ ∗ ( S ) ) ≤ ( n + 1 ) α \sum_j\ell(z_j,\lambda^*(S))\leq(n+1)\alpha ∑ j ℓ ( z j , λ ∗ ( S )) ≤ ( n + 1 ) α . Every action that satisfies (7.1) therefore lies in the certified menu of E ∗ E^* E ∗ , and Theorem 2.1 gives the validity of CRC and envelope CRC.
The e-collection E ∗ E^* E ∗ is obtained by first choosing an action through risk control on the augmented sample and then evaluating conformal e-values at that action. The e-values of [6 ] for selective prediction are built in the same way. There, a selection threshold is chosen by controlling the risk on the augmented sample, and the conformal e-value is evaluated at that threshold, with the unknown test loss handled by an infimum over its possible values, much as (7.1) is imposed for every possible test point.
3.25ex -1em Exchangeability and i.i.d. sampling. Finally, we explain why Lemma 3.1 requires validity under every finite exchangeable law. Validity under i.i.d. sampling extends to mixtures of i.i.d. laws, but finite exchangeable laws need not be such mixtures, and the two requirements already differ for n = 1 n=1 n = 1 . Let Z 1 , Z 2 ∈ { 0 , 1 } Z_1,Z_2\in\{0,1\} Z 1 , Z 2 ∈ { 0 , 1 } , take the miscoverage loss with α = 1 / 2 \alpha=1/2 α = 1/2 , and consider the controller that predicts the set { Z 1 } \{Z_1\} { Z 1 } for Z 2 Z_2 Z 2 . If Z 1 Z_1 Z 1 and Z 2 Z_2 Z 2 are i.i.d. Bernoulli( p ) (p) ( p ) , it miscovers with probability 2 p ( 1 − p ) ≤ 1 / 2 2p(1-p)\leq1/2 2 p ( 1 − p ) ≤ 1/2 , so it is valid under i.i.d. sampling. Under the exchangeable law that is uniform on ( 0 , 1 ) (0,1) ( 0 , 1 ) and ( 1 , 0 ) (1,0) ( 1 , 0 ) , which is not a mixture of i.i.d. laws, it miscovers with probability one. In terms of Lemma 3.1 , both held-out losses on the augmented sample { 0 , 1 } \{0,1\} { 0 , 1 } equal one, so their total exceeds the budget ( n + 1 ) α = 1 (n+1)\alpha=1 ( n + 1 ) α = 1 and the unused budget Δ A ( { 0 , 1 } ) = − 1 \Delta_A(\{0,1\})=-1 Δ A ({ 0 , 1 }) = − 1 is negative. Recertification spends Δ A \Delta_A Δ A and therefore needs validity under exchangeability. CRC and envelope CRC have it, and so satisfy (3.5) .
Other allocations
Equal sharing is one way, but not the only way, to distribute the unused budget among the held-out positions. For each augmented multiset S S S and risk t t t , let w i , t ( S ) ≥ 0 w_{i,t}(S)\geq0 w i , t ( S ) ≥ 0 be measurable weights with ∑ i w i , t ( S ) = 1 \sum_iw_{i,t}(S)=1 ∑ i w i , t ( S ) = 1 that are permutation equivariant: reordering the points of S S S reorders the weights, and identical points receive identical weights. These weights give the budgets
b i , t A ( S ) = ℓ t ( z i , A ( S − i ) ) + Δ A , t ( S ) w i , t ( S ) , \begin{equation}
b_{i,t}^A(S)=\ell_t(z_i,A(S_{-i}))+\Delta_{A,t}(S)\,w_{i,t}(S), \tag*{(7.2)}
\end{equation} b i , t A ( S ) = ℓ t ( z i , A ( S − i )) + Δ A , t ( S ) w i , t ( S ) , (7.2)
which sum to ( n + 1 ) α t (n+1)\alpha_t ( n + 1 ) α t on every augmented sample. Write b t A ( S ; z ) b^A_t(S;z) b t A ( S ; z ) for the common budget of the copies of z z z in S S S . By Lemma 3.1 , every measurable symmetric controller C C C with
ℓ t ( z , C ( D ) ) ≤ b t A ( D ∪ { z } ; z ) for all D , z , t \begin{equation}
\ell_t(z,C(D))\leq b^A_t(D\cup\{z\};z)\qquad\text{for all }D,\ z,\ t \tag*{(7.3)}
\end{equation} ℓ t ( z , C ( D )) ≤ b t A ( D ∪ { z } ; z ) for all D , z , t (7.3)
is jointly valid, since its held-out losses on each S S S sum to at most ( n + 1 ) α t (n+1)\alpha_t ( n + 1 ) α t . Adding the constraint C ≤ A C\leq A C ≤ A makes the improvement pointwise. Equal weights recover (3.12) , and weights proportional to the held-out losses of A A A are another choice. Restricting to allocations loses no generality, since every pointwise improvement satisfies (7.3) for some allocation.
Proposition B.1 (Every pointwise improvement has an allocation). Suppose that every ℓ t ( z , ⋅ ) \ell_t(z,\cdot) ℓ t ( z , ⋅ ) is non-increasing. If A A A and C C C are jointly valid symmetric controllers with C ≤ A C\leq A C ≤ A , then C C C satisfies (7.3) for some permutation-equivariant weights.
Proof. Fix S S S and t t t , and write r i , t A r^A_{i,t} r i , t A and r i , t C r^C_{i,t} r i , t C for the held-out losses of the two controllers. Since C ≤ A C\leq A C ≤ A and the losses are non-increasing, the extra losses d i , t = r i , t C − r i , t A d_{i,t}=r_{i,t}^C-r_{i,t}^A d i , t = r i , t C − r i , t A are nonnegative, and they sum to Δ A , t − Δ C , t \Delta_{A,t}-\Delta_{C,t} Δ A , t − Δ C , t . If Δ A , t > 0 \Delta_{A,t}>0 Δ A , t > 0 , set
w i , t ( S ) = d i , t + Δ C , t / ( n + 1 ) Δ A , t . w_{i,t}(S)=\frac{d_{i,t}+\Delta_{C,t}/(n+1)}{\Delta_{A,t}}. w i , t ( S ) = Δ A , t d i , t + Δ C , t / ( n + 1 ) . These weights are nonnegative and sum to one. They give each position its extra loss together with an equal share of the unused budget of C C C , so the budgets in (7.2) equal r i , t C + Δ C , t / ( n + 1 ) ≥ r i , t C r_{i,t}^C+\Delta_{C,t}/(n+1)\geq r_{i,t}^C r i , t C + Δ C , t / ( n + 1 ) ≥ r i , t C . If Δ A , t = 0 \Delta_{A,t}=0 Δ A , t = 0 , then ∑ i d i , t = − Δ C , t ≤ 0 \sum_id_{i,t}=-\Delta_{C,t}\leq0 ∑ i d i , t = − Δ C , t ≤ 0 forces every d i , t d_{i,t} d i , t to vanish, and any equivariant weights suffice. The weights are equivariant and measurable because both controllers are symmetric and measurable. ◻
By Proposition B.1 and Theorem 3.5 , repeated equal sharing can also be interpreted as an implicit search over allocations. Its admissible limit A ( ∞ ) A^{(\infty)} A ( ∞ ) satisfies (7.3) for some allocation of the unused budget of A ( 0 ) A^{(0)} A ( 0 ) , and no allocation yields a valid controller that improves on it.
Proof of Theorem 3.5 and Proposition 3.6
We prove the second part of Proposition 3.6 , of which Theorem 3.5 is the case of a single risk. Throughout, Λ = [ λ − , λ + ] \Lambda=[\lambda_-,\lambda_+] Λ = [ λ − , λ + ] , and every ℓ t ( z , ⋅ ) \ell_t(z,\cdot) ℓ t ( z , ⋅ ) is non-increasing, right-continuous and convex. By Lemma 3.1 , a controller A A A is jointly valid if and only if T A , t ( S ) ≤ ( n + 1 ) α t T_{A,t}(S)\leq(n+1)\alpha_t T A , t ( S ) ≤ ( n + 1 ) α t for every S S S and t t t .
Lemma B.2 (One-step comparison). If A A A and C C C are jointly valid and C ≤ A C\leq A C ≤ A , then R A ≤ ρ A + C / ( n + 1 ) \mathcal RA\leq\rho A+C/(n+1) R A ≤ ρ A + C / ( n + 1 ) .
Proof. Fix D D D , z z z and t t t , and let S = D ∪ { z } S=D\cup\{z\} S = D ∪ { z } . Since C ≤ A C\leq A C ≤ A and the losses are non-increasing, each held-out loss of C C C on S S S is at least that of A A A , and by joint validity of C C C these differences sum to T C , t ( S ) − T A , t ( S ) ≤ Δ A , t ( S ) T_{C,t}(S)-T_{A,t}(S)\leq\Delta_{A,t}(S) T C , t ( S ) − T A , t ( S ) ≤ Δ A , t ( S ) . Each difference is therefore at most Δ A , t ( S ) \Delta_{A,t}(S) Δ A , t ( S ) , and for the held-out point z z z ,
ℓ t ( z , C ( D ) ) − ℓ t ( z , A ( D ) ) ≤ Δ A , t ( S ) . \ell_t(z,C(D))-\ell_t(z,A(D))\leq\Delta_{A,t}(S). ℓ t ( z , C ( D )) − ℓ t ( z , A ( D )) ≤ Δ A , t ( S ) . The action a = ρ A ( D ) + C ( D ) / ( n + 1 ) a=\rho A(D)+C(D)/(n+1) a = ρ A ( D ) + C ( D ) / ( n + 1 ) lies between C ( D ) C(D) C ( D ) and A ( D ) A(D) A ( D ) , and convexity gives
ℓ t ( z , a ) − ℓ t ( z , A ( D ) ) ≤ ℓ t ( z , C ( D ) ) − ℓ t ( z , A ( D ) ) n + 1 ≤ Δ A , t ( S ) n + 1 . \ell_t(z,a)-\ell_t(z,A(D))
\leq\frac{\ell_t(z,C(D))-\ell_t(z,A(D))}{n+1}
\leq\frac{\Delta_{A,t}(S)}{n+1}. ℓ t ( z , a ) − ℓ t ( z , A ( D )) ≤ n + 1 ℓ t ( z , C ( D )) − ℓ t ( z , A ( D )) ≤ n + 1 Δ A , t ( S ) . Since z z z and t t t are arbitrary, a a a is feasible in (3.12) , and hence ( R A ) ( D ) ≤ a (\mathcal RA)(D)\leq a ( R A ) ( D ) ≤ a . ◻
Proof of Proposition 3.6 . By the first part of the proposition, the iterates are jointly valid and A ( k + 1 ) ≤ A ( k ) A^{(k+1)}\leq A^{(k)} A ( k + 1 ) ≤ A ( k ) . Hence A ( k ) ( D ) A^{(k)}(D) A ( k ) ( D ) decreases to a limit A ( ∞ ) ( D ) ∈ Λ A^{(\infty)}(D)\in\Lambda A ( ∞ ) ( D ) ∈ Λ for every D D D , and A ( ∞ ) A^{(\infty)} A ( ∞ ) is measurable and symmetric as a pointwise limit. For fixed S S S and t t t , the losses are non-increasing and right-continuous, so ℓ t ( z i , A ( k ) ( S − i ) ) ↑ ℓ t ( z i , A ( ∞ ) ( S − i ) ) \ell_t(z_i,A^{(k)}(S_{-i}))\uparrow\ell_t(z_i,A^{(\infty)}(S_{-i})) ℓ t ( z i , A ( k ) ( S − i )) ↑ ℓ t ( z i , A ( ∞ ) ( S − i )) , and T A ( ∞ ) , t ( S ) = lim k T A ( k ) , t ( S ) ≤ ( n + 1 ) α t T_{A^{(\infty)},t}(S)=\lim_kT_{A^{(k)},t}(S)\leq(n+1)\alpha_t T A ( ∞ ) , t ( S ) = lim k T A ( k ) , t ( S ) ≤ ( n + 1 ) α t . Thus A ( ∞ ) A^{(\infty)} A ( ∞ ) is jointly valid.
Let C C C be jointly valid with C ≤ A ( ∞ ) C\leq A^{(\infty)} C ≤ A ( ∞ ) . Then C ≤ A ( k ) C\leq A^{(k)} C ≤ A ( k ) for every k k k , and Lemma B.2 gives A ( k + 1 ) ≤ ρ A ( k ) + C / ( n + 1 ) A^{(k+1)}\leq\rho A^{(k)}+C/(n+1) A ( k + 1 ) ≤ ρ A ( k ) + C / ( n + 1 ) . Letting k → ∞ k\to\infty k → ∞ yields A ( ∞ ) ≤ ρ A ( ∞ ) + C / ( n + 1 ) A^{(\infty)}\leq\rho A^{(\infty)}+C/(n+1) A ( ∞ ) ≤ ρ A ( ∞ ) + C / ( n + 1 ) , that is, A ( ∞ ) ≤ C A^{(\infty)}\leq C A ( ∞ ) ≤ C . Hence C = A ( ∞ ) C=A^{(\infty)} C = A ( ∞ ) , and no jointly valid controller strictly dominates A ( ∞ ) A^{(\infty)} A ( ∞ ) . Taking C = A ( ∞ ) C=A^{(\infty)} C = A ( ∞ ) in Lemma B.2 gives 0 ≤ A ( k + 1 ) − A ( ∞ ) ≤ ρ ( A ( k ) − A ( ∞ ) ) 0\leq A^{(k+1)}-A^{(\infty)}\leq\rho\,(A^{(k)}-A^{(\infty)}) 0 ≤ A ( k + 1 ) − A ( ∞ ) ≤ ρ ( A ( k ) − A ( ∞ ) ) , and induction gives (3.9) .
Finally, if A A A is admissible, then R A \mathcal RA R A is jointly valid with R A ≤ A \mathcal RA\leq A R A ≤ A , so R A = A \mathcal RA=A R A = A and A A A is a fixed point. Conversely, if R A = A \mathcal RA=A R A = A and C ≤ A C\leq A C ≤ A is jointly valid, Lemma B.2 gives A ≤ ρ A + C / ( n + 1 ) A\leq\rho A+C/(n+1) A ≤ ρ A + C / ( n + 1 ) , so A ≤ C A\leq C A ≤ C and C = A C=A C = A . Hence A A A is admissible. ◻
Proof of Proposition 3.7
For a calibration multiset D 0 D_0 D 0 and an action a ∈ Λ a\in\Lambda a ∈ Λ , let A D 0 , a A^{D_0,a} A D 0 , a denote the controller that agrees with A A A except at D 0 D_0 D 0 , where it takes the action a a a . It is symmetric, and measurable since it differs from A A A at a single multiset.
Proof of Proposition 3.7 . Consider changing the controller A A A to A D 0 , a A^{D_0, a} A D 0 , a . The held-out position i i i of an augmented multiset S S S is affected by the change if and only if S − i = D 0 S_{-i}=D_0 S − i = D 0 , that is, if and only if S = D 0 ∪ { z } S=D_0\cup\{z\} S = D 0 ∪ { z } and z i = z z_i=z z i = z for some z z z . Such an S S S contains ν D 0 ( z ) + 1 \nu_{D_0}(z)+1 ν D 0 ( z ) + 1 copies of z z z , so
T A D 0 , a , t ( D 0 ∪ { z } ) = T A , t ( D 0 ∪ { z } ) + ( ν D 0 ( z ) + 1 ) { ℓ t ( z , a ) − ℓ t ( z , A ( D 0 ) ) } , T_{A^{D_0,a},t}(D_0\cup\{z\})=T_{A,t}(D_0\cup\{z\})+(\nu_{D_0}(z)+1)\{\ell_t(z,a)-\ell_t(z,A(D_0))\}, T A D 0 , a , t ( D 0 ∪ { z }) = T A , t ( D 0 ∪ { z }) + ( ν D 0 ( z ) + 1 ) { ℓ t ( z , a ) − ℓ t ( z , A ( D 0 ))} , and every other total is unchanged. By Lemma 3.1 , A D 0 , a A^{D_0,a} A D 0 , a is jointly valid if and only if (3.13) holds at D 0 D_0 D 0 and a a a . If (3.13) holds at some D 0 D_0 D 0 and a < A ( D 0 ) a<A(D_0) a < A ( D 0 ) , then A D 0 , a A^{D_0,a} A D 0 , a is jointly valid and strictly dominates A A A . Conversely, let C ≤ A C\leq A C ≤ A be a jointly valid symmetric controller with C ( D 0 ) < A ( D 0 ) C(D_0)<A(D_0) C ( D 0 ) < A ( D 0 ) for some D 0 D_0 D 0 , and put a = C ( D 0 ) a=C(D_0) a = C ( D 0 ) . Since A D 0 , a ≥ C A^{D_0,a}\geq C A D 0 , a ≥ C pointwise and the losses are non-increasing, each held-out loss of A D 0 , a A^{D_0,a} A D 0 , a is at most that of C C C . Hence A D 0 , a A^{D_0,a} A D 0 , a is jointly valid, and (3.13) holds at D 0 D_0 D 0 and a < A ( D 0 ) a<A(D_0) a < A ( D 0 ) .
Since Z \mathcal Z Z is finite in this case, there are finitely many calibration multisets. Their order is fixed in advance, so that the sweep defines a single controller rather than a data-dependent procedure. At each visit, the actions satisfying (3.13) form a closed upper interval of Λ \Lambda Λ that contains the current entry, by the monotonicity and right continuity of the losses, so the smallest such action a ∗ a^* a ∗ exists, and the update preserves joint validity. Two observations show that a visited entry cannot be lowered afterwards. First, right after the update, an action a < a ∗ a<a^* a < a ∗ satisfies (3.13) at D 0 D_0 D 0 if and only if it did before the update, since the update lowers both sides of (3.13) by the same amount ( ν D 0 ( z ) + 1 ) { ℓ t ( z , a ∗ ) − ℓ t ( z , A ( D 0 ) ) } (\nu_{D_0}(z)+1)\{\ell_t(z,a^*)-\ell_t(z,A(D_0))\} ( ν D 0 ( z ) + 1 ) { ℓ t ( z , a ∗ ) − ℓ t ( z , A ( D 0 ))} . By the choice of a ∗ a^* a ∗ , no such action exists. Second, a later update at another multiset can only increase held-out losses, so it shrinks every unused budget, and hence the right side of (3.13) at D 0 D_0 D 0 , while the entry at D 0 D_0 D 0 , and hence the left side, stays fixed. After one pass, the condition therefore fails at every multiset for every smaller action. The resulting controller is jointly valid and no larger than A A A , and it is admissible by the criterion. ◻
The two-type example
In this subsection, we carefully solve the two-type example in § 3.4 .
We first write out the validity constraints, which describe the valid controllers as the points of [ 0 , 1 ] 3 [0,1]^3 [ 0 , 1 ] 3 that satisfy four linear inequalities. With the losses (3.11) , ℓ ( z , λ ) = g ( z ) ( 1 − λ ) \ell(z,\lambda)=g(z)(1-\lambda) ℓ ( z , λ ) = g ( z ) ( 1 − λ ) with g ( H ) = 1 g(H)=1 g ( H ) = 1 and g ( L ) = 1 / 2 g(L)=1/2 g ( L ) = 1/2 , and the budget is ( n + 1 ) α = 3 / 2 (n+1)\alpha=3/2 ( n + 1 ) α = 3/2 . A symmetric controller A A A is determined by its actions at H H HH H H , H L HL H L and L L LL LL . We write
( h , u , v ) = ( 1 − A ( H H ) , 1 − A ( H L ) , 1 − A ( L L ) ) ∈ [ 0 , 1 ] 3 , (h,u,v)=\bigl(1-A(HH),\,1-A(HL),\,1-A(LL)\bigr)\in[0,1]^3, ( h , u , v ) = ( 1 − A ( H H ) , 1 − A ( H L ) , 1 − A ( LL ) ) ∈ [ 0 , 1 ] 3 ,
so that larger coordinates correspond to less conservative actions. In H H L HHL H H L , for instance, deleting either copy of H H H leaves H L HL H L and deleting L L L leaves H H HH H H , so the held-out losses are u u u , u u u and h / 2 h/2 h /2 . Treating the four augmented multisets in this way, Lemma 3.1 shows that A A A is valid if and only if
3 h ≤ 3 2 ( H H H ) , 2 u + 1 2 h ≤ 3 2 ( H H L ) , u + v ≤ 3 2 ( H L L ) , 3 2 v ≤ 3 2 ( L L L ) . \begin{equation}
3h\leq\tfrac32\ \ (HHH),\qquad
2u+\tfrac12h\leq\tfrac32\ \ (HHL),\qquad
u+v\leq\tfrac32\ \ (HLL),\qquad
\tfrac32v\leq\tfrac32\ \ (LLL). \tag*{(7.4)}
\end{equation} 3 h ≤ 2 3 ( H H H ) , 2 u + 2 1 h ≤ 2 3 ( H H L ) , u + v ≤ 2 3 ( H LL ) , 2 3 v ≤ 2 3 ( LLL ) . (7.4)
Let G D = ∑ z ∈ D g ( z ) G_D=\sum_{z\in D}g(z) G D = ∑ z ∈ D g ( z ) . For the baselines, we verify that standard CRC with B = 1 B=1 B = 1 gives 1 − A C R C ( D ) = 1 / ( 2 G D ) 1-A_{\mathrm{CRC}}(D)=1/(2G_D) 1 − A CRC ( D ) = 1/ ( 2 G D ) , and envelope CRC with the sharp envelope U ( λ ) = 1 − λ U(\lambda)=1-\lambda U ( λ ) = 1 − λ gives 1 − A e n v ( D ) = 3 / ( 2 ( G D + 1 ) ) 1-A_{\mathrm{env}}(D)=3/(2(G_D+1)) 1 − A env ( D ) = 3/ ( 2 ( G D + 1 )) . In particular, envelope CRC has ( h , u , v ) = ( 1 / 2 , 3 / 5 , 3 / 4 ) (h,u,v)=(1/2,3/5,3/4) ( h , u , v ) = ( 1/2 , 3/5 , 3/4 ) .
Starting from the controller of envelope CRC, the update (3.7) at D D D replaces the current coordinate w D w_D w D by the largest w ≤ 1 w\leq1 w ≤ 1 with g ( z ) ( w − w D ) ≤ Δ A ( D ∪ { z } ) / 3 g(z)(w-w_D)\leq\Delta_A(D\cup\{z\})/3 g ( z ) ( w − w D ) ≤ Δ A ( D ∪ { z }) /3 for z ∈ { H , L } z\in\{H,L\} z ∈ { H , L } . The three coordinates evolve as follows:
At H H HH H H , the candidate H H H gives w ≤ h w\leq h w ≤ h , since Δ A ( H H H ) = 3 / 2 − 3 h = 0 \Delta_A(HHH)=3/2-3h=0 Δ A ( H H H ) = 3/2 − 3 h = 0 at h = 1 / 2 h=1/2 h = 1/2 . Hence h = 1 / 2 h=1/2 h = 1/2 throughout.
At H L HL H L , with h = 1 / 2 h=1/2 h = 1/2 , the candidates H H H and L L L give w ≤ u / 3 + 5 / 12 w\leq u/3+5/12 w ≤ u /3 + 5/12 and w ≤ u / 3 + 1 − 2 v / 3 w\leq u/3+1-2v/3 w ≤ u /3 + 1 − 2 v /3 . The first bound is the smaller one whenever v ≤ 7 / 8 v\leq7/8 v ≤ 7/8 .
At L L LL LL , the candidates H H H and L L L give w ≤ 2 v / 3 − u / 3 + 1 / 2 w\leq 2v/3-u/3+1/2 w ≤ 2 v /3 − u /3 + 1/2 and w ≤ 1 w\leq1 w ≤ 1 .
Hence, as long as v k ≤ 7 / 8 v_k\leq7/8 v k ≤ 7/8 and 2 v k / 3 − u k / 3 + 1 / 2 ≤ 1 2v_k/3-u_k/3+1/2\leq1 2 v k /3 − u k /3 + 1/2 ≤ 1 , the iterates satisfy
u k + 1 = 1 3 u k + 5 12 , v k + 1 = 2 3 v k − 1 3 u k + 1 2 , u_{k+1}=\tfrac13u_k+\tfrac5{12},\qquad v_{k+1}=\tfrac23v_k-\tfrac13u_k+\tfrac12, u k + 1 = 3 1 u k + 12 5 , v k + 1 = 3 2 v k − 3 1 u k + 2 1 ,
with u 0 = 3 / 5 u_0=3/5 u 0 = 3/5 and v 0 = 3 / 4 v_0=3/4 v 0 = 3/4 . By induction, the solutions are
u k = 5 8 − 1 40 ( 1 3 ) k , v k = 7 8 − 1 10 ( 2 3 ) k − 1 40 ( 1 3 ) k . u_k=\frac58-\frac1{40}\left(\frac13\right)^k,\qquad
v_k=\frac78-\frac1{10}\left(\frac23\right)^k-\frac1{40}\left(\frac13\right)^k. u k = 8 5 − 40 1 ( 3 1 ) k , v k = 8 7 − 10 1 ( 3 2 ) k − 40 1 ( 3 1 ) k .
They satisfy v k < 7 / 8 v_k<7/8 v k < 7/8 for every k k k , so both conditions hold and the recurrences are the exact updates. In terms of actions,
A ( k ) ( H H ) = 1 2 , A ( k ) ( H L ) = 3 8 + 1 40 ( 1 3 ) k , A ( k ) ( L L ) = 1 8 + 1 10 ( 2 3 ) k + 1 40 ( 1 3 ) k , A^{(k)}(HH)=\frac12,\qquad
A^{(k)}(HL)=\frac38+\frac1{40}\left(\frac13\right)^k,\qquad
A^{(k)}(LL)=\frac18+\frac1{10}\left(\frac23\right)^k+\frac1{40}\left(\frac13\right)^k, A ( k ) ( H H ) = 2 1 , A ( k ) ( H L ) = 8 3 + 40 1 ( 3 1 ) k , A ( k ) ( LL ) = 8 1 + 10 1 ( 3 2 ) k + 40 1 ( 3 1 ) k ,
which give the entries of Table 1 and converge geometrically at rate ρ = 2 / 3 \rho=2/3 ρ = 2/3 to A ( ∞ ) = ( 1 / 2 , 3 / 8 , 1 / 8 ) A^{(\infty)}=(1/2,3/8,1/8) A ( ∞ ) = ( 1/2 , 3/8 , 1/8 ) .
In this case, a valid controller is admissible if and only if no other point satisfying (7.4) is coordinatewise at least as large. We observe the following.
The limit has ( h , u , v ) = ( 1 / 2 , 5 / 8 , 7 / 8 ) (h,u,v)=(1/2,5/8,7/8) ( h , u , v ) = ( 1/2 , 5/8 , 7/8 ) . The constraints for H H H HHH H H H , H H L HHL H H L and H L L HLL H LL bind, and the one for L L L LLL LLL is slack, since 3 2 ⋅ 7 8 = 21 16 < 3 2 \frac32\cdot\frac78=\frac{21}{16}<\frac32 2 3 ⋅ 8 7 = 16 21 < 2 3 . If a feasible point ( h ′ , u ′ , v ′ ) (h',u',v') ( h ′ , u ′ , v ′ ) is at least as large, then H H H HHH H H H forces h ′ = 1 / 2 h'=1/2 h ′ = 1/2 , H H L HHL H H L then forces u ′ = 5 / 8 u'=5/8 u ′ = 5/8 , and H L L HLL H LL then forces v ′ = 7 / 8 v'=7/8 v ′ = 7/8 . Hence the limit is admissible.
The controller ( 1 / 2 , 2 / 5 , 1 / 10 ) (1/2,2/5,1/10) ( 1/2 , 2/5 , 1/10 ) has ( h , u , v ) = ( 1 / 2 , 3 / 5 , 9 / 10 ) (h,u,v)=(1/2,3/5,9/10) ( h , u , v ) = ( 1/2 , 3/5 , 9/10 ) and satisfies (7.4) , with H H H HHH H H H and H L L HLL H LL binding. A feasible point at least as large has h ′ = 1 / 2 h'=1/2 h ′ = 1/2 by H H H HHH H H H , and u ′ ≥ 3 / 5 u'\geq3/5 u ′ ≥ 3/5 , v ′ ≥ 9 / 10 v'\geq9/10 v ′ ≥ 9/10 and u ′ + v ′ ≤ 3 / 2 u'+v'\leq3/2 u ′ + v ′ ≤ 3/2 force u ′ = 3 / 5 u'=3/5 u ′ = 3/5 and v ′ = 9 / 10 v'=9/10 v ′ = 9/10 . Hence this controller is also admissible.
The two controllers are incomparable, and their pointwise minimum has ( h , u , v ) = ( 1 / 2 , 5 / 8 , 9 / 10 ) (h,u,v)=(1/2,5/8,9/10) ( h , u , v ) = ( 1/2 , 5/8 , 9/10 ) , which violates the constraint for H L L HLL H LL , since 5 / 8 + 9 / 10 = 61 / 40 > 3 / 2 5/8+9/10=61/40>3/2 5/8 + 9/10 = 61/40 > 3/2 .
Theorem 3.5 requires Λ \Lambda Λ to be an interval, even for affine losses. On the grid { 1 / 10 , 1 / 4 , 2 / 5 , 1 / 2 , 1 } \{1/10,1/4,2/5,1/2,1\} { 1/10 , 1/4 , 2/5 , 1/2 , 1 } , the envelope controller ( 1 / 2 , 2 / 5 , 1 / 4 ) (1/2,2/5,1/4) ( 1/2 , 2/5 , 1/4 ) is a fixed point of the restricted update, since its feasible sets in (3.7) at H H HH H H , H L HL H L and L L LL LL , namely [ 1 / 2 , 1 / 2 ] [1/2,1/2] [ 1/2 , 1/2 ] , [ 23 / 60 , 2 / 5 ] [23/60,2/5] [ 23/60 , 2/5 ] and [ 1 / 5 , 1 / 4 ] [1/5,1/4] [ 1/5 , 1/4 ] , contain no smaller grid value. Yet the valid grid controller ( 1 / 2 , 2 / 5 , 1 / 10 ) (1/2,2/5,1/10) ( 1/2 , 2/5 , 1/10 ) strictly dominates it. The step that fails is the interpolation in Lemma B.2 : at L L LL LL , the action ρ A ( D ) + C ( D ) / ( n + 1 ) = 1 / 5 \rho A(D)+C(D)/(n+1)=1/5 ρ A ( D ) + C ( D ) / ( n + 1 ) = 1/5 is feasible but not on the grid. Nevertheless, the sweep of Proposition 3.7 needs no interpolation and reaches ( 1 / 2 , 2 / 5 , 1 / 10 ) (1/2,2/5,1/10) ( 1/2 , 2/5 , 1/10 ) in one pass.
A two-risk example with a continuous observation space
We give one more example, with two risks and a continuous observation space, so that a controller is a function rather than a finite table. Recertification converges to the largest valid controller that dominates the joint envelope baseline, and the improvement is strict at every interior point.
Take n = 1 n=1 n = 1 for simplicity, so that a single calibration observation X ∈ [ 0 , 1 ] X\in[0,1] X ∈ [ 0 , 1 ] is used to choose an action for a test observation Y ∈ [ 0 , 1 ] Y\in[0,1] Y ∈ [ 0 , 1 ] , and let Λ = [ 0 , 1 ] \Lambda=[0,1] Λ = [ 0 , 1 ] . Throughout this example we describe actions by a = 1 − λ a=1-\lambda a = 1 − λ , so that larger values are less conservative, and write A ( x ) ∈ [ 0 , 1 ] A(x)\in[0,1] A ( x ) ∈ [ 0 , 1 ] for the value chosen at the calibration observation x x x . The losses y a ya y a and ( 1 − y ) a (1-y)a ( 1 − y ) a must each have risk at most 1 / 4 1/4 1/4 ,
E [ Y A ( X ) ] ≤ 1 4 , E [ ( 1 − Y ) A ( X ) ] ≤ 1 4 , {\mathbb E}[YA(X)]\leq\tfrac14,\qquad {\mathbb E}[(1-Y)A(X)]\leq\tfrac14, E [ Y A ( X )] ≤ 4 1 , E [( 1 − Y ) A ( X )] ≤ 4 1 ,
under every exchangeable law of ( X , Y ) (X,Y) ( X , Y ) . Both losses are affine in λ \lambda λ , with sharp envelope a a a . By Lemma 3.1 , applied to each risk, A A A is jointly valid if and only if
y A ( x ) + x A ( y ) ≤ 1 2 and ( 1 − y ) A ( x ) + ( 1 − x ) A ( y ) ≤ 1 2 for all x , y ∈ [ 0 , 1 ] . \begin{equation}
yA(x)+xA(y)\leq\tfrac12\quad\text{and}\quad
(1-y)A(x)+(1-x)A(y)\leq\tfrac12\qquad\text{for all }x,y\in[0,1]. \tag*{(7.5)}
\end{equation} y A ( x ) + x A ( y ) ≤ 2 1 and ( 1 − y ) A ( x ) + ( 1 − x ) A ( y ) ≤ 2 1 for all x , y ∈ [ 0 , 1 ] . (7.5)
Envelope CRC for the two risks gives A ( x ) ≤ 1 / ( 2 ( 1 + x ) ) A(x)\leq1/(2(1+x)) A ( x ) ≤ 1/ ( 2 ( 1 + x )) and A ( x ) ≤ 1 / ( 2 ( 2 − x ) ) A(x)\leq1/(2(2-x)) A ( x ) ≤ 1/ ( 2 ( 2 − x )) , and the joint envelope baseline A 0 A_0 A 0 takes the more conservative of the two. We compare it with A ∗ A_* A ∗ , where
A 0 ( x ) = 1 2 ( 1 + max ( x , 1 − x ) ) , A ∗ ( x ) = 1 + min ( x , 1 − x ) 4 . A_0(x)=\frac{1}{2(1+\max(x,1-x))},\qquad
A_*(x)=\frac{1+\min(x,1-x)}4. A 0 ( x ) = 2 ( 1 + max ( x , 1 − x )) 1 , A ∗ ( x ) = 4 1 + min ( x , 1 − x ) .
If a jointly valid A A A dominates A 0 A_0 A 0 , then (7.5) at x = y = 1 x=y=1 x = y = 1 and at x = y = 0 x=y=0 x = y = 0 forces A ( 1 ) = A ( 0 ) = 1 / 4 A(1)=A(0)=1/4 A ( 1 ) = A ( 0 ) = 1/4 , the values of A 0 A_0 A 0 there, and the constraints with y = 1 y=1 y = 1 and y = 0 y=0 y = 0 then give A ( x ) ≤ min { ( 2 − x ) / 4 , ( 1 + x ) / 4 } = A ∗ ( x ) A(x)\leq\min\{(2-x)/4,(1+x)/4\}=A_*(x) A ( x ) ≤ min {( 2 − x ) /4 , ( 1 + x ) /4 } = A ∗ ( x ) . Conversely, these two bounds give
y A ∗ ( x ) + x A ∗ ( y ) ≤ 1 − ( 1 − x ) ( 1 − y ) 2 ≤ 1 2 , ( 1 − y ) A ∗ ( x ) + ( 1 − x ) A ∗ ( y ) ≤ 1 − x y 2 ≤ 1 2 , yA_*(x)+xA_*(y)\leq\frac{1-(1-x)(1-y)}2\leq\frac12,\qquad
(1-y)A_*(x)+(1-x)A_*(y)\leq\frac{1-xy}2\leq\frac12, y A ∗ ( x ) + x A ∗ ( y ) ≤ 2 1 − ( 1 − x ) ( 1 − y ) ≤ 2 1 , ( 1 − y ) A ∗ ( x ) + ( 1 − x ) A ∗ ( y ) ≤ 2 1 − x y ≤ 2 1 ,
so A ∗ A_* A ∗ is jointly valid. Hence A ∗ A_* A ∗ is the largest valid controller that dominates A 0 A_0 A 0 , and in particular it is admissible. The improvement is strict at every interior point.
In terms of a a a , the update (3.12) at x x x replaces A ( x ) A(x) A ( x ) by the smallest of the thresholds
A ( x ) 2 + 1 / 2 − x A ( y ) 2 y ( 0 < y ≤ 1 ) , A ( x ) 2 + 1 / 2 − ( 1 − x ) A ( y ) 2 ( 1 − y ) ( 0 ≤ y < 1 ) , \frac{A(x)}2+\frac{1/2-xA(y)}{2y}\quad(0<y\leq1),\qquad
\frac{A(x)}2+\frac{1/2-(1-x)A(y)}{2(1-y)}\quad(0\leq y<1), 2 A ( x ) + 2 y 1/2 − x A ( y ) ( 0 < y ≤ 1 ) , 2 A ( x ) + 2 ( 1 − y ) 1/2 − ( 1 − x ) A ( y ) ( 0 ≤ y < 1 ) ,
which come from the first and the second risk. Suppose that A ≤ A ∗ A\leq A_* A ≤ A ∗ and A ( 0 ) = A ( 1 ) = 1 / 4 A(0)=A(1)=1/4 A ( 0 ) = A ( 1 ) = 1/4 , as for A 0 A_0 A 0 . Then the tightest constraints come from the extreme test points, y = 1 y=1 y = 1 for the first risk and y = 0 y=0 y = 0 for the second. Indeed, for 0 < y ≤ 1 0<y\leq1 0 < y ≤ 1 and c ∈ [ 0 , 1 ] c\in[0,1] c ∈ [ 0 , 1 ] ,
1 2 − c A ( y ) − y ( 1 2 − c 4 ) = 1 − y 2 − c ( A ( y ) − y 4 ) ≥ 1 − y 2 − c ( A ∗ ( y ) − y 4 ) ≥ 0 , \frac12-cA(y)-y\left(\frac12-\frac c4\right)=\frac{1-y}2-c\left(A(y)-\frac y4\right)\geq\frac{1-y}2-c\left(A_*(y)-\frac y4\right)\geq0, 2 1 − c A ( y ) − y ( 2 1 − 4 c ) = 2 1 − y − c ( A ( y ) − 4 y ) ≥ 2 1 − y − c ( A ∗ ( y ) − 4 y ) ≥ 0 ,
since A ∗ ( y ) − y / 4 = min { 1 / 4 , ( 1 − y ) / 2 } ≤ ( 1 − y ) / 2 A_*(y)-y/4=\min\{1/4,(1-y)/2\}\leq(1-y)/2 A ∗ ( y ) − y /4 = min { 1/4 , ( 1 − y ) /2 } ≤ ( 1 − y ) /2 . With c = x c=x c = x , the first family of thresholds is therefore minimized at y = 1 y=1 y = 1 , with value A ( x ) / 2 + ( 2 − x ) / 8 A(x)/2+(2-x)/8 A ( x ) /2 + ( 2 − x ) /8 . Similarly, the second family is minimized at y = 0 y=0 y = 0 , with value A ( x ) / 2 + ( 1 + x ) / 8 A(x)/2+(1+x)/8 A ( x ) /2 + ( 1 + x ) /8 . The smaller of the two values is { A ( x ) + A ∗ ( x ) } / 2 \{A(x)+A_*(x)\}/2 { A ( x ) + A ∗ ( x )} /2 , so
A ( k + 1 ) = 1 2 ( A ( k ) + A ∗ ) . A^{(k+1)}=\tfrac12\bigl(A^{(k)}+A_*\bigr). A ( k + 1 ) = 2 1 ( A ( k ) + A ∗ ) .
The updated controller again satisfies A ≤ A ∗ A\leq A_* A ≤ A ∗ and A ( 0 ) = A ( 1 ) = 1 / 4 A(0)=A(1)=1/4 A ( 0 ) = A ( 1 ) = 1/4 , and by induction
A ( k ) ( x ) = A ∗ ( x ) − 2 − k { A ∗ ( x ) − A 0 ( x ) } . A^{(k)}(x)=A_*(x)-2^{-k}\{A_*(x)-A_0(x)\}. A ( k ) ( x ) = A ∗ ( x ) − 2 − k { A ∗ ( x ) − A 0 ( x )} .
The iterates thus increase to A ∗ A_* A ∗ , and the rate (3.9) of Proposition 3.6 , with ρ = 1 / 2 \rho=1/2 ρ = 1/2 , holds with equality. Each iterate is a convex combination of A 0 A_0 A 0 and A ∗ A_* A ∗ , so its validity can also be read off from the linear constraints (7.5) .
Implementation details for the real-data study
All computations use the cached classifier outputs, and no model is fitted on the calibration or test images. Throughout, A k ( D , x ) A_k(D,x) A k ( D , x ) denotes the depth assigned to a test image x x x after k k k rounds of recertification, starting from envelope CRC A 0 A_0 A 0 ; larger depths are less conservative.
3.25ex -1em Error types. For an observation z = ( x , y ) z=(x,y) z = ( x , y ) , let its type c ( z ) c(z) c ( z ) be 0 0 0 if y = f ( x ) y=f(x) y = f ( x ) , 1 1 1 if y ∈ g ( x ) ∖ { f ( x ) } y\in g(x)\setminus\{f(x)\} y ∈ g ( x ) ∖ { f ( x )} , and 2 2 2 if y ∉ g ( x ) y\notin g(x) y ∈ / g ( x ) . By (3.14) , the loss depends on z z z only through its type,
ℓ 0 ( a ) = 0 , ℓ 1 ( a ) = 1 2 ( a − 1 ) + , ℓ 2 ( a ) = 1 2 a , a ∈ [ 0 , 2 ] . \ell_0(a)=0,\qquad \ell_1(a)=\tfrac12(a-1)_+,\qquad \ell_2(a)=\tfrac12a,\qquad a\in[0,2]. ℓ 0 ( a ) = 0 , ℓ 1 ( a ) = 2 1 ( a − 1 ) + , ℓ 2 ( a ) = 2 1 a , a ∈ [ 0 , 2 ] .
The pool contains 7,300 7{,}300 7 , 300 , 969 969 969 and 1,731 1{,}731 1 , 731 images of the three types.
3.25ex -1em Baselines.
Common depth. With h j h_j h j calibration observations of type j j j , CRC and envelope CRC select the largest a ∈ [ 0 , 2 ] a\in[0,2] a ∈ [ 0 , 2 ] with
h 1 ( a − 1 ) + + h 2 a 2 + U ( a ) ≤ ( n + 1 ) α , U ( a ) = 1 (CRC) , U ( a ) = a / 2 (envelope CRC) , \frac{h_1(a-1)_++h_2a}{2}+U(a)\le (n+1)\alpha,
\qquad
U(a)=1\ \text{(CRC)},\quad U(a)=a/2\ \text{(envelope CRC)}, 2 h 1 ( a − 1 ) + + h 2 a + U ( a ) ≤ ( n + 1 ) α , U ( a ) = 1 (CRC) , U ( a ) = a /2 (envelope CRC) , and the root, a = 0 a=0 a = 0 , if no depth qualifies. The left side is piecewise linear with a kink at a = 1 a=1 a = 1 , so the largest depth is found in closed form on [ 0 , 1 ] [0,1] [ 0 , 1 ] and [ 1 , 2 ] [1,2] [ 1 , 2 ] . It is generally fractional, so these baselines already randomize between adjacent levels.
Confidence-adaptive scores. Write u i = 1 − p g ( X i ) u_i=1-p_g(X_i) u i = 1 − p g ( X i ) and v i = 1 − p f ( X i ) v_i=1-p_f(X_i) v i = 1 − p f ( X i ) , so that u i ≤ v i u_i\leq v_i u i ≤ v i , and, under the threshold t t t , image i i i moves from the root to its superclass when t > u i t>u_i t > u i and to its leaf when t > v i t>v_i t > v i . The calibration loss at t t t is
1 2 ∑ i = 1 n [ 1 { c ( Z i ) = 2 } 1 { u i < t } + 1 { c ( Z i ) ≠ 0 } 1 { v i < t } ] , \frac12\sum_{i=1}^n\left[\mathop{\mathrm{\mathds{1}}}\{c(Z_i)=2\}\mathop{\mathrm{\mathds{1}}}\{u_i<t\}+\mathop{\mathrm{\mathds{1}}}\{c(Z_i)\ne0\}\mathop{\mathrm{\mathds{1}}}\{v_i<t\}\right], 2 1 i = 1 ∑ n [ 1 { c ( Z i ) = 2 } 1 { u i < t } + 1 { c ( Z i ) = 0 } 1 { v i < t } ] , a step function that increases by 1 / 2 1/2 1/2 at the leaf breakpoint of every observation of nonzero type and at the superclass breakpoint of every observation of type 2 2 2 . CRC selects the largest t t t at which at most b 0 = 2 ( ( n + 1 ) α − 1 ) b_0=2((n+1)\alpha-1) b 0 = 2 (( n + 1 ) α − 1 ) of these jumps have occurred. These baselines return integer depths.
3.25ex -1em The update. Fix a calibration sample D D D and a test image x x x ; in the common-depth family, the depth does not depend on x x x . For an augmented sample S = ( z 1 , … , z n + 1 ) S=(z_1,\ldots,z_{n+1}) S = ( z 1 , … , z n + 1 ) , let T k ( S ) = ∑ i = 1 n + 1 ℓ ( z i , A k ( S − i , x i ) ) T_k(S)=\sum_{i=1}^{n+1}\ell(z_i,A_k(S_{-i},x_i)) T k ( S ) = ∑ i = 1 n + 1 ℓ ( z i , A k ( S − i , x i )) be the total held-out loss of A k A_k A k . Since the loss depends on the label only through its type, all labels of the same type give the same constraint in the update of § 3.5 . For c ∈ { 1 , 2 } c\in\{1,2\} c ∈ { 1 , 2 } , let S c S_c S c augment D D D with ( x , y c ) (x,y_c) ( x , y c ) , where y c y_c y c is any label of type c c c for x x x , and let
s k , c ( D , x ) = α − T k ( S c ) n + 1 s_{k,c}(D,x)=\alpha-\frac{T_k(S_c)}{n+1} s k , c ( D , x ) = α − n + 1 T k ( S c )
be the equal share of its unused budget. With a = A k ( D , x ) a=A_k(D,x) a = A k ( D , x ) , the next depth is the largest a ′ ∈ [ a , 2 ] a'\in[a,2] a ′ ∈ [ a , 2 ] with ℓ c ( a ′ ) ≤ ℓ c ( a ) + s k , c ( D , x ) \ell_c(a')\leq\ell_c(a)+s_{k,c}(D,x) ℓ c ( a ′ ) ≤ ℓ c ( a ) + s k , c ( D , x ) for c = 1 , 2 c=1,2 c = 1 , 2 , that is,
A k + 1 ( D , x ) = min { 2 , a + 2 s k , 2 ( D , x ) , 1 + ( a − 1 ) + + 2 s k , 1 ( D , x ) } . \begin{equation}
A_{k+1}(D,x)=\min\left\{2,\ a+2s_{k,2}(D,x),\ 1+(a-1)_++2s_{k,1}(D,x)\right\}. \tag*{(7.6)}
\end{equation} A k + 1 ( D , x ) = min { 2 , a + 2 s k , 2 ( D , x ) , 1 + ( a − 1 ) + + 2 s k , 1 ( D , x ) } . (7.6)
For common depth, every iterate depends on D D D only through the count vector h = ( h 0 , h 1 , h 2 ) h=(h_0,h_1,h_2) h = ( h 0 , h 1 , h 2 ) , so A k A_k A k is a table with ( n + 2 2 ) = 1,326 \binom{n+2}{2}=1{,}326 ( 2 n + 2 ) = 1 , 326 entries at n = 50 n=50 n = 50 . For an augmented count vector q q q with total n + 1 n+1 n + 1 ,
T k ( q ) = ∑ j : q j > 0 q j ℓ j ( A k ( q − e j ) ) , T_k(q)=\sum_{j:\,q_j>0}q_j\,\ell_j\bigl(A_k(q-e_j)\bigr), T k ( q ) = j : q j > 0 ∑ q j ℓ j ( A k ( q − e j ) ) ,
where e j e_j e j is the j j j th unit vector, and the slacks for the entry h h h come from q = h + e 1 q=h+e_1 q = h + e 1 and q = h + e 2 q=h+e_2 q = h + e 2 . Each round updates the whole table at once. The table does not depend on the data, so it is computed once for each target, and each split reads off the entry for its calibration counts.
For confidence-adaptive scores, there is no common table, and for each test image we compute a table of all the depths that the recursion requires. Unrolling (7.6) , A k ( D , x ) A_k(D,x) A k ( D , x ) depends on depths A k − 1 ( S − i , x i ) A_{k-1}(S_{-i},x_i) A k − 1 ( S − i , x i ) , in which a calibration point is held out and the test image carries a hypothetical type, and these depend in turn on further depths of the same form. Every depth that arises is therefore indexed by a held-out point, among the calibration points and the test image, and a type for each remaining point. Calibration points of type 0 0 0 never need to be held out, since their loss is zero, and they keep their type; they enter only through the sample size. If r − 1 r-1 r − 1 calibration points have nonzero types, call them and the test image the r r r active points. The table then holds one depth for each held-out active point and each assignment of type 1 1 1 or 2 2 2 to the other active points, giving r 2 r − 1 r2^{r-1} r 2 r − 1 entries in total. Each round updates all entries from the preceding table, in time linear in its size, and the reported depth is the entry in which the test image is held out and the calibration points carry their observed types. Consequently, the computation can be more demanding than in the common-depth case. Two exact reductions shrink the table without changing any depth.
Capping breakpoints. Let b = ⌊ b 0 ⌋ b=\lfloor b_0\rfloor b = ⌊ b 0 ⌋ be the number of whole jumps within the budget. Every active point has a leaf breakpoint, whatever its type. If there are at least b + 2 b+2 b + 2 active points, let τ \tau τ be the ( b + 2 ) (b+2) ( b + 2 ) th smallest of their leaf breakpoints. After any one point is held out, at least b + 1 b+1 b + 1 jumps at or below τ \tau τ remain, so every CRC threshold in the table is at most τ \tau τ . Replacing each breakpoint above τ \tau τ by τ \tau τ therefore leaves all baseline depths unchanged, and hence all later ones.
Grouping. Active points with identical breakpoint pairs, after capping, are interchangeable, so a group of g g g such points is described by its number of type-2 2 2 points rather than by 2 g 2^g 2 g assignments. With group sizes g 1 , … , g J g_1,\ldots,g_J g 1 , … , g J , the table has ∑ j g j ∏ h ≠ j ( g h + 1 ) \sum_jg_j\prod_{h\ne j}(g_h+1) ∑ j g j ∏ h = j ( g h + 1 ) entries.
A larger nominal level allows more jumps, which raises τ \tau τ and leaves more distinct breakpoints. This explains the longer runtimes at larger levels.
We record rounds 0 , 1 , 3 , 10 , 20 , 50 , 100 , 200 0,1,3,10,20,50,100,200 0 , 1 , 3 , 10 , 20 , 50 , 100 , 200 and 500 500 500 , and the common-depth table is updated for all 500 500 500 rounds. For an adaptive test image, the total slack ( n + 1 ) α − T k ( S c ) (n+1)\alpha-T_k(S_c) ( n + 1 ) α − T k ( S c ) bounds how much its loss can grow in all later rounds. Once this slack allows a depth increase of at most 10 − 8 10^{-8} 1 0 − 8 , we stop updating the image and carry its depth forward, which preserves validity by the first observation at the end of § 3.5 .
3.25ex -1em Evaluation. Each of the 300 300 300 splits draws 50 50 50 calibration images and 16 16 16 test images at random without replacement from the pool of 10,000 10{,}000 10 , 000 images, and all methods, families and targets use the same splits. All metrics are computed exactly over the randomization of the prediction. With π ( a ) = ( ( 1 − a ) + , 1 − ∣ a − 1 ∣ , ( a − 1 ) + ) \pi(a)=((1-a)_+,1-|a-1|,(a-1)_+) π ( a ) = (( 1 − a ) + , 1 − ∣ a − 1∣ , ( a − 1 ) + ) the probabilities of the root, superclass and leaf, a test image of type c c c predicted at depth a a a has risk ℓ c ( a ) \ell_c(a) ℓ c ( a ) , expected node size 100 π 0 ( a ) + 5 π 1 ( a ) + π 2 ( a ) 100\pi_0(a)+5\pi_1(a)+\pi_2(a) 100 π 0 ( a ) + 5 π 1 ( a ) + π 2 ( a ) and expected correct specificity
log 20 log 100 π 1 ( a ) 1 { c ≠ 2 } + π 2 ( a ) 1 { c = 0 } . \frac{\log20}{\log100}\,\pi_1(a)\mathop{\mathrm{\mathds{1}}}\{c\ne2\}+\pi_2(a)\mathop{\mathrm{\mathds{1}}}\{c=0\}. log 100 log 20 π 1 ( a ) 1 { c = 2 } + π 2 ( a ) 1 { c = 0 } .
Each metric is averaged over the 16 16 16 test images of a split and then over the splits, and standard errors are computed across splits. In Figure 2 , let d s d_s d s be the gain over envelope CRC in split s s s , and let d ˉ \bar d d ˉ and s e \mathrm{se} se be the mean and standard error of d 1 , … , d M d_1,\ldots,d_M d 1 , … , d M with M = 300 M=300 M = 300 . The bands are d ˉ ± t M − 1 , 0.975 s e \bar d\pm t_{M-1,0.975}\,\mathrm{se} d ˉ ± t M − 1 , 0.975 se , pointwise intervals that reflect variation across splits of the fixed pool.
Details for randomized e-BH
Throughout, e e e is a fixed nonnegative vector, b [ r ] = ( α / K ) e [ r ] b_{[r]}=(\alpha/K)e_{[r]} b [ r ] = ( α / K ) e [ r ] is the budget of the hypothesis of rank r r r , and c [ r ] ( p ) = ∑ k ≥ r p k / k c_{[r]}(p)=\sum_{k\geq r}p_k/k c [ r ] ( p ) = ∑ k ≥ r p k / k is its charge under a distribution p p p of the number of rejections, as in § 4.2 . We also write a r = r b [ r ] + ∑ j > r b [ j ] a_r=r\,b_{[r]}+\sum_{j>r}b_{[j]} a r = r b [ r ] + ∑ j > r b [ j ] , so that q r ∗ = min { 1 , a r } q^*_r=\min\{1,a_r\} q r ∗ = min { 1 , a r } .
We first check that e-BH is the largest certified set. By § 4.1 , the sets certified by E e B H E^{\mathrm{eBH}} E eBH are the self-consistent ones. Let k ∗ k^* k ∗ be the e-BH count, the largest k k k with k e [ k ] ≥ K / α k\,e_{[k]}\geq K/\alpha k e [ k ] ≥ K / α . The e-BH set is self-consistent, because each of its members has an e-value of at least e [ k ∗ ] ≥ K / ( α k ∗ ) e_{[k^*]}\geq K/(\alpha k^*) e [ k ∗ ] ≥ K / ( α k ∗ ) . Moreover, recall that e-BH rejects every hypothesis j j j with e j ≥ K / ( α k ∗ ) e_j\geq K/(\alpha k^*) e j ≥ K / ( α k ∗ ) . If R R R is self-consistent and ∣ R ∣ = k |R|=k ∣ R ∣ = k , then its k k k members have e-values of at least K / ( α k ) K/(\alpha k) K / ( α k ) , so k e [ k ] ≥ K / α k\,e_{[k]}\geq K/\alpha k e [ k ] ≥ K / α and k ≤ k ∗ k\leq k^* k ≤ k ∗ . Every member of R R R then has e j ≥ K / ( α k ) ≥ K / ( α k ∗ ) e_j\geq K/(\alpha k)\geq K/(\alpha k^*) e j ≥ K / ( α k ) ≥ K / ( α k ∗ ) and is rejected by e-BH.
We also verify explicitly that every boosting rule that selects from the certified menu (4.4) controls the FDR. If p ( e ) p(e) p ( e ) is measurable in e e e and lies in the menu for every e e e , then for P ∈ P T P\in\mathcal P_T P ∈ P T , since the number of rejections is drawn independently of the data,
E FDP T ( R κ ( E ) ) = E P L ˉ ( T , p ( E ) ; E ) = E P ∑ j ∈ T c [ r ( j ) ] ( p ( E ) ) ≤ α K ∑ j ∈ T E P E j ≤ α ∣ T ∣ K . {\mathbb E}\,\operatorname{FDP}_T(R_\kappa(E))={\mathbb E}_P\bar L(T,p(E);E)={\mathbb E}_P\sum_{j\in T}c_{[r(j)]}(p(E))\leq\frac\alpha K\sum_{j\in T}{\mathbb E}_PE_j\leq\frac{\alpha|T|}K . E FDP T ( R κ ( E )) = E P L ˉ ( T , p ( E ) ; E ) = E P j ∈ T ∑ c [ r ( j )] ( p ( E )) ≤ K α j ∈ T ∑ E P E j ≤ K α ∣ T ∣ .
This is Theorem 2.1 for the action space of distributions.
As described in the main text, the rule given by U-eBH leaves a nonnegative unused budget. Fix r r r , and let k r ≥ r k_r\geq r k r ≥ r maximize k e [ k ] k\,e_{[k]} k e [ k ] over k ≥ r k\geq r k ≥ r . By (4.3) , the tails of p 0 p^0 p 0 are equal at all ranks r ′ ∈ { r , … , k r } r'\in\{r,\ldots,k_r\} r ′ ∈ { r , … , k r } , since the maximum of k e [ k ] k\,e_{[k]} k e [ k ] over k ≥ r ′ k\geq r' k ≥ r ′ is still attained at k r k_r k r . Since { κ 0 ≥ k } = { U ≤ P ( κ 0 ≥ k ∣ E = e ) } \{\kappa_0\geq k\}=\{U\leq\mathbb P(\kappa_0\geq k\mid E=e)\} { κ 0 ≥ k } = { U ≤ P ( κ 0 ≥ k ∣ E = e )} , the events { κ 0 ≥ r } \{\kappa_0 \geq r\} { κ 0 ≥ r } and { κ 0 ≥ k r } \{\kappa_0\geq k_r\} { κ 0 ≥ k r } coincide. Whenever U-eBH rejects the hypothesis of rank r r r , it rejects at least k r k_r k r hypotheses, so that hypothesis receives a share of at most 1 / k r 1/k_r 1/ k r . Hence
c [ r ] ( p 0 ) = E [ 1 { κ 0 ≥ r } κ 0 ∣ E = e ] ≤ P ( κ 0 ≥ r ∣ E = e ) k r ≤ α K e [ k r ] ≤ b [ r ] . c_{[r]}(p^0)={\mathbb E}\left[\frac{\mathop{\mathrm{\mathds{1}}}\{\kappa_0\geq r\}}{\kappa_0}\Bigm|E=e\right]\leq\frac{\mathbb P(\kappa_0\geq r\mid E=e)}{k_r}\leq\frac\alpha K\,e_{[k_r]}\leq b_{[r]} . c [ r ] ( p 0 ) = E [ κ 0 1 { κ 0 ≥ r } E = e ] ≤ k r P ( κ 0 ≥ r ∣ E = e ) ≤ K α e [ k r ] ≤ b [ r ] .
U-eBH therefore selects from the menu, and the difference b [ r ] − c [ r ] ( p 0 ) b_{[r]}-c_{[r]}(p^0) b [ r ] − c [ r ] ( p 0 ) is the budget that it leaves unused for the hypothesis of rank r r r , which is positive whenever e [ r ] > e [ k r ] e_{[r]}>e_{[k_r]} e [ r ] > e [ k r ] .
Recertifying U-eBH with E e B H E^{\mathrm{eBH}} E eBH is exactly an instance of Proposition 2.2 . The state is the set T T T of true nulls, and the loss is the averaged false discovery proportion. Since U-eBH selects the single distribution p 0 ( e ) p^0(e) p 0 ( e ) , its canonical envelope is its own loss, g T = L ˉ ( T , p 0 ( E ) ; E ) = ∑ j ∈ T c [ r ( j ) ] ( p 0 ( E ) ) g_T=\bar L(T,p^0(E);E)=\sum_{j\in T}c_{[r(j)]}(p^0(E)) g T = L ˉ ( T , p 0 ( E ) ; E ) = ∑ j ∈ T c [ r ( j )] ( p 0 ( E )) . Take the conditioning statistic V T = E V_T=E V T = E . Given E E E , the loss g T g_T g T is known, because the law of U U U is known, so we may take H T = g T H_T=g_T H T = g T . Take the budget B T = α E T e B H = ( α / K ) ∑ j ∈ T E j B_T=\alpha E^{\mathrm{eBH}}_T=(\alpha/K)\sum_{j\in T}E_j B T = α E T eBH = ( α / K ) ∑ j ∈ T E j . Summing the previous paragraph over j ∈ T j\in T j ∈ T gives H T ≤ B T H_T\leq B_T H T ≤ B T , and E P B T ≤ α ∣ T ∣ / K ≤ α {\mathbb E}_PB_T\leq\alpha|T|/K\leq\alpha E P B T ≤ α ∣ T ∣/ K ≤ α for P ∈ P T P\in\mathcal P_T P ∈ P T , so (2.8) holds. The allowance B T − H T B_T-H_T B T − H T is the unused budget of the previous paragraph, and it is a function of E E E . The increment W T = B T − H T W_T=B_T-H_T W T = B T − H T therefore satisfies (2.9) with equality, and the recertified e-collection ( g T + W T ) / α = B T / α (g_T+W_T)/\alpha=B_T/\alpha ( g T + W T ) / α = B T / α is E T e B H E^{\mathrm{eBH}}_T E T eBH . Its certified menu is (4.4) , which contains p 0 p^0 p 0 and every other distribution whose charges stay within the budgets.
Proof of Proposition 4.1
§ 4.3 shows that every distribution in the menu (4.4) satisfies the tail bounds (4.5) . The following lemma shows that a single distribution in the menu attains all of them. Put e [ K + 1 ] = 0 e_{[K+1]}=0 e [ K + 1 ] = 0 and a K + 1 = 0 a_{K+1}=0 a K + 1 = 0 for notational convenience.
Lemma C.1. Let p ~ k = ( α k / K ) ( e [ k ] − e [ k + 1 ] ) \tilde p_k=(\alpha k/K)(e_{[k]}-e_{[k+1]}) p ~ k = ( α k / K ) ( e [ k ] − e [ k + 1 ] ) for k = 1 , … , K k=1,\ldots,K k = 1 , … , K , define p k ∗ = min { p ~ k , 1 − ∑ l > k p l ∗ } p^*_k=\min\{\tilde p_k,1-\sum_{l>k}p^*_l\} p k ∗ = min { p ~ k , 1 − ∑ l > k p l ∗ } for k = K , K − 1 , … , 1 k=K,K-1,\ldots,1 k = K , K − 1 , … , 1 , and let p 0 ∗ = 1 − ∑ k ≥ 1 p k ∗ p^*_0=1-\sum_{k\geq1}p^*_k p 0 ∗ = 1 − ∑ k ≥ 1 p k ∗ . Then p ∗ p^* p ∗ is a distribution in the menu (4.4) with tails ∑ k ≥ r p k ∗ = q r ∗ \sum_{k\geq r}p^*_k=q^*_r ∑ k ≥ r p k ∗ = q r ∗ for r = 1 , … , K r=1,\ldots,K r = 1 , … , K . If a 1 ≤ 1 a_1\leq1 a 1 ≤ 1 , then p k ∗ = p ~ k p^*_k=\tilde p_k p k ∗ = p ~ k for k ≥ 1 k\geq1 k ≥ 1 , and every constraint in (4.4) holds with equality.
Proof. We check that p ~ k \tilde p_k p ~ k is nonnegative, ∑ k ≥ r p ~ k / k = ( α / K ) ∑ k ≥ r ( e [ k ] − e [ k + 1 ] ) = b [ r ] \sum_{k\geq r}\tilde p_k/k=(\alpha/K)\sum_{k\geq r}(e_{[k]}-e_{[k+1]})=b_{[r]} ∑ k ≥ r p ~ k / k = ( α / K ) ∑ k ≥ r ( e [ k ] − e [ k + 1 ] ) = b [ r ] , and p ~ r = a r − a r + 1 \tilde p_r=a_r-a_{r+1} p ~ r = a r − a r + 1 . By construction, 0 ≤ p k ∗ ≤ p ~ k 0\leq p^*_k\leq\tilde p_k 0 ≤ p k ∗ ≤ p ~ k for k ≥ 1 k\geq1 k ≥ 1 and ∑ k ≥ 1 p k ∗ ≤ 1 \sum_{k\geq1}p^*_k\leq1 ∑ k ≥ 1 p k ∗ ≤ 1 , so p ∗ p^* p ∗ is a distribution whose charges are at most the budgets b [ r ] b_{[r]} b [ r ] , and it lies in the menu. Downward induction in r r r gives
∑ k ≥ r p k ∗ = min { 1 , ∑ k > r p k ∗ + p ~ r } = min { 1 , min { 1 , a r + 1 } + p ~ r } = min { 1 , a r } = q r ∗ . \sum_{k\geq r}p^*_k=\min\Bigl\{1,\sum_{k>r}p^*_k+\tilde p_r\Bigr\}=\min\bigl\{1,\min\{1,a_{r+1}\}+\tilde p_r\bigr\}=\min\{1,a_r\}=q^*_r . k ≥ r ∑ p k ∗ = min { 1 , k > r ∑ p k ∗ + p ~ r } = min { 1 , min { 1 , a r + 1 } + p ~ r } = min { 1 , a r } = q r ∗ . If a 1 ≤ 1 a_1\leq1 a 1 ≤ 1 , then p ~ k ≤ 1 − a k + 1 \tilde p_k\leq1-a_{k+1} p ~ k ≤ 1 − a k + 1 for every k k k , so no truncation occurs, p k ∗ = p ~ k p^*_k=\tilde p_k p k ∗ = p ~ k for k ≥ 1 k\geq1 k ≥ 1 , and every charge equals its budget. ◻
Proof of Proposition 4.1 . By Lemma C.1 , the bounds q r ∗ q^*_r q r ∗ are the tails of the distribution p ∗ p^* p ∗ , so they are non-increasing in r r r . Hence { κ ∗ ≥ r } = { U ≤ q r ∗ } \{\kappa^*\geq r\}=\{U\leq q^*_r\} { κ ∗ ≥ r } = { U ≤ q r ∗ } , and κ ∗ \kappa^* κ ∗ has the distribution p ∗ p^* p ∗ given E = e E=e E = e .
(i) The tails q r ∗ ( e ) q^*_r(e) q r ∗ ( e ) are measurable in e e e , so p ∗ ( e ) p^*(e) p ∗ ( e ) is a measurable selection from the menu (4.4) , and the validity of boosting rules in Appendix § 8.1 gives E FDP T ( R κ ∗ ( E ) ) ≤ α ∣ T ∣ / K {\mathbb E}\,\operatorname{FDP}_T(R_{\kappa^*}(E))\leq\alpha|T|/K E FDP T ( R κ ∗ ( E )) ≤ α ∣ T ∣/ K .
(ii) If k ≥ r k\geq r k ≥ r , then
r e [ r ] + ∑ j > r e [ j ] ≥ r e [ k ] + ∑ j = r + 1 k e [ j ] ≥ k e [ k ] , r\,e_{[r]}+\sum_{j>r}e_{[j]}\geq r\,e_{[k]}+\sum_{j=r+1}^ke_{[j]}\geq k\,e_{[k]}, r e [ r ] + j > r ∑ e [ j ] ≥ r e [ k ] + j = r + 1 ∑ k e [ j ] ≥ k e [ k ] , so q r ∗ q^*_r q r ∗ is at least the U-eBH tail (4.3) . With the same U U U , it follows that { κ 0 ≥ r } ⊆ { κ ∗ ≥ r } \{\kappa_0\geq r\}\subseteq\{\kappa^*\geq r\} { κ 0 ≥ r } ⊆ { κ ∗ ≥ r } for every r r r , so κ ∗ ≥ κ 0 \kappa^*\geq\kappa_0 κ ∗ ≥ κ 0 and R κ 0 ( e ) ⊆ R κ ∗ ( e ) R_{\kappa_0}(e)\subseteq R_{\kappa^*}(e) R κ 0 ( e ) ⊆ R κ ∗ ( e ) . Clearly, U-eBH in turn contains e-BH.
(iii) Every boosting rule that selects from (4.4) has tails at most q r ∗ q^*_r q r ∗ by (4.5) , and κ ∗ \kappa^* κ ∗ attains them. ◻
Corollary C.2. Let E ~ j = ( K / α ) 1 { j ∈ R κ ∗ } / ( ∣ R κ ∗ ∣ ∨ 1 ) \widetilde E_j=(K/\alpha)\mathop{\mathrm{\mathds{1}}}\{j\in R_{\kappa^*}\}/(|R_{\kappa^*}|\vee1) E j = ( K / α ) 1 { j ∈ R κ ∗ } / ( ∣ R κ ∗ ∣ ∨ 1 ) . Then E [ E ~ j ∣ E ] ≤ E j {\mathbb E}[\widetilde E_j\mid E]\leq E_j E [ E j ∣ E ] ≤ E j , so E ~ j \widetilde E_j E j is an e-value whenever E j E_j E j is, and e-BH applied to E ~ \widetilde E E rejects exactly R κ ∗ ( E ) R_{\kappa^*}(E) R κ ∗ ( E ) .
Proof. Given E = e E=e E = e , E [ E ~ j ∣ E = e ] = ( K / α ) c [ r ( j ) ] ( p ∗ ) ≤ ( K / α ) b [ r ( j ) ] = e j {\mathbb E}[\widetilde E_j\mid E=e]=(K/\alpha)\,c_{[r(j)]}(p^*)\leq(K/\alpha)\,b_{[r(j)]}=e_j E [ E j ∣ E = e ] = ( K / α ) c [ r ( j )] ( p ∗ ) ≤ ( K / α ) b [ r ( j )] = e j . Every member of R κ ∗ R_{\kappa^*} R κ ∗ has E ~ j = K / ( α ∣ R κ ∗ ∣ ) \widetilde E_j=K/(\alpha|R_{\kappa^*}|) E j = K / ( α ∣ R κ ∗ ∣ ) and every other hypothesis has E ~ j = 0 \widetilde E_j=0 E j = 0 , so the largest k k k with k E ~ [ k ] ≥ K / α k\,\widetilde E_{[k]}\geq K/\alpha k E [ k ] ≥ K / α is ∣ R κ ∗ ∣ |R_{\kappa^*}| ∣ R κ ∗ ∣ , and e-BH applied to E ~ \widetilde E E rejects exactly R κ ∗ R_{\kappa^*} R κ ∗ . ◻
Randomization over arbitrary rejection sets
The main text considers randomized rules that reject one of the nested sets R k ( e ) R_k(e) R k ( e ) . More generally, a randomized rule may choose, given E = e E=e E = e , any distribution Q Q Q over the subsets R ⊆ { 1 , … , K } R\subseteq\{1,\ldots,K\} R ⊆ { 1 , … , K } . Each rejected null hypothesis contributes 1 / ∣ R ∣ 1/|R| 1/∣ R ∣ to the false discovery proportion, so in state T T T ,
E Q FDP T ( R ) = ∑ j ∈ T c j ( Q ) , c j ( Q ) = E Q [ 1 { j ∈ R } ∣ R ∣ ∨ 1 ] , {\mathbb E}_Q\operatorname{FDP}_T(R)=\sum_{j\in T}c_j(Q),\qquad c_j(Q)={\mathbb E}_Q\biggl[\frac{\mathop{\mathrm{\mathds{1}}}\{j\in R\}}{|R|\vee1}\biggr], E Q FDP T ( R ) = j ∈ T ∑ c j ( Q ) , c j ( Q ) = E Q [ ∣ R ∣ ∨ 1 1 { j ∈ R } ] ,
where c j ( Q ) c_j(Q) c j ( Q ) is the expected share charged to hypothesis j j j . As in § 4.1 , both sides of E Q FDP T ( R ) ≤ α E T e B H ( e ) {\mathbb E}_Q\operatorname{FDP}_T(R)\leq\alpha E^{\mathrm{eBH}}_T(e) E Q FDP T ( R ) ≤ α E T eBH ( e ) are sums over T T T , so Q Q Q is certified by E e B H E^{\mathrm{eBH}} E eBH if and only if c j ( Q ) ≤ b j = ( α / K ) e j c_j(Q)\leq b_j=(\alpha/K)e_j c j ( Q ) ≤ b j = ( α / K ) e j for every j j j .
J-eBH is such a rule whose rejection sets are not nested, and it is certified by E e B H E^{\mathrm{eBH}} E eBH , so that in particular it controls the FDR. To bound the charge of hypothesis j j j , fix E = e E=e E = e and the uniforms U i U_i U i for i ≠ j i\neq j i = j , and let f ( u ) f(u) f ( u ) be the number of rejections when U j = u U_j=u U j = u . Increasing u u u decreases the boosted value e j / u e_j/u e j / u and leaves the others unchanged, so f f f is non-increasing. Since e-BH rejects every hypothesis whose boosted value is at least K / ( α f ( u ) ) K/(\alpha f(u)) K / ( α f ( u )) , hypothesis j j j is rejected exactly when u ≤ ( α / K ) e j f ( u ) u\leq(\alpha/K)e_jf(u) u ≤ ( α / K ) e j f ( u ) . If this condition holds at u u u , it holds at every u ′ < u u'<u u ′ < u , because u ′ < u ≤ ( α / K ) e j f ( u ) ≤ ( α / K ) e j f ( u ′ ) u'<u\leq(\alpha/K)e_jf(u)\leq(\alpha/K)e_jf(u') u ′ < u ≤ ( α / K ) e j f ( u ) ≤ ( α / K ) e j f ( u ′ ) . The values of u u u at which hypothesis j j j is rejected therefore form an interval with left endpoint 0 0 0 and some right endpoint u ∗ u^* u ∗ . If u ∗ > 0 u^*>0 u ∗ > 0 , then f ( u ) ≥ f − ( u ∗ ) ≥ 1 f(u)\geq f^-(u^*)\geq1 f ( u ) ≥ f − ( u ∗ ) ≥ 1 on this interval, where f − ( u ∗ ) f^-(u^*) f − ( u ∗ ) is the left limit of f f f at u ∗ u^* u ∗ , and letting u ↑ u ∗ u\uparrow u^* u ↑ u ∗ in the rejection condition gives u ∗ ≤ ( α / K ) e j f − ( u ∗ ) u^*\leq(\alpha/K)e_jf^-(u^*) u ∗ ≤ ( α / K ) e j f − ( u ∗ ) . Hence
E [ 1 { j ∈ R } ∣ R ∣ ∨ 1 ∣ U i , i ≠ j ] = ∫ 0 u ∗ d u f ( u ) ≤ u ∗ f − ( u ∗ ) ≤ α K e j = b j , {\mathbb E}\biggl[\frac{\mathop{\mathrm{\mathds{1}}}\{j\in R\}}{|R|\vee1}\biggm|U_i,\,i\neq j\biggr]=\int_0^{u^*}\frac{du}{f(u)}\leq\frac{u^*}{f^-(u^*)}\leq\frac\alpha Ke_j=b_j, E [ ∣ R ∣ ∨ 1 1 { j ∈ R } U i , i = j ] = ∫ 0 u ∗ f ( u ) d u ≤ f − ( u ∗ ) u ∗ ≤ K α e j = b j ,
which also holds trivially if u ∗ = 0 u^*=0 u ∗ = 0 , and averaging over the other uniforms gives c j ( Q ) ≤ b j c_j(Q)\leq b_j c j ( Q ) ≤ b j .
Proposition C.3. Every distribution Q Q Q over rejection sets that is certified by E e B H E^{\mathrm{eBH}} E eBH satisfies E Q ∣ R ∣ ≤ E [ κ ∗ ∣ E = e ] {\mathbb E}_Q|R|\leq{\mathbb E}[\kappa^*\mid E=e] E Q ∣ R ∣ ≤ E [ κ ∗ ∣ E = e ] . The stochastic comparison of Proposition 4.1 (iii) does not extend to this class: such a Q Q Q may satisfy Q ( ∣ R ∣ ≥ r ) > q r ∗ Q(|R|\geq r)>q^*_r Q ( ∣ R ∣ ≥ r ) > q r ∗ for some r r r .
Proof. Let m m m be the number of ranks r r r with a r ≥ 1 a_r\geq1 a r ≥ 1 . Since a r a_r a r is non-increasing in r r r , q r ∗ = 1 q^*_r=1 q r ∗ = 1 for r ≤ m r\leq m r ≤ m and q r ∗ = a r q^*_r=a_r q r ∗ = a r for r > m r>m r > m . Summing the tails,
E [ κ ∗ ∣ E = e ] = ∑ r = 1 K q r ∗ = m + ∑ r > m a r = m + ∑ j > m ( 2 j − m − 1 ) b [ j ] , {\mathbb E}[\kappa^*\mid E=e]=\sum_{r=1}^Kq^*_r=m+\sum_{r>m}a_r=m+\sum_{j>m}(2j-m-1)\,b_{[j]}, E [ κ ∗ ∣ E = e ] = r = 1 ∑ K q r ∗ = m + r > m ∑ a r = m + j > m ∑ ( 2 j − m − 1 ) b [ j ] , because for j > m j>m j > m , the budget b [ j ] b_{[j]} b [ j ] enters a j a_j a j with coefficient j j j and a r a_r a r with coefficient one for each m < r < j m<r<j m < r < j . Give the hypothesis j j j the weight y j = 0 y_j=0 y j = 0 if r ( j ) ≤ m r(j)\leq m r ( j ) ≤ m and y j = 2 r ( j ) − m − 1 y_j=2r(j)-m-1 y j = 2 r ( j ) − m − 1 otherwise, so that E [ κ ∗ ∣ E = e ] = m + ∑ j y j b j {\mathbb E}[\kappa^*\mid E=e]=m+\sum_jy_jb_j E [ κ ∗ ∣ E = e ] = m + ∑ j y j b j . The weights, ordered by rank, are m m m zeros followed by m + 1 , m + 3 , m + 5 , … m+1,m+3,m+5,\ldots m + 1 , m + 3 , m + 5 , … , so the weights in a set R R R of size k ≥ 1 k\geq1 k ≥ 1 sum to at least 0 0 0 if k ≤ m k\leq m k ≤ m and at least ∑ i = 1 k − m ( m + 2 i − 1 ) = k ( k − m ) \sum_{i=1}^{k-m}(m+2i-1)=k(k-m) ∑ i = 1 k − m ( m + 2 i − 1 ) = k ( k − m ) otherwise. In both cases ∑ j ∈ R y j ≥ k ( k − m ) \sum_{j\in R}y_j\geq k(k-m) ∑ j ∈ R y j ≥ k ( k − m ) , which leads to
∣ R ∣ ≤ m 1 { R ≠ ∅ } + ∑ j y j 1 { j ∈ R } ∣ R ∣ ∨ 1 . |R|\leq m\,\mathop{\mathrm{\mathds{1}}}\{R\neq\emptyset\}+\sum_jy_j\frac{\mathop{\mathrm{\mathds{1}}}\{j\in R\}}{|R|\vee1}. ∣ R ∣ ≤ m 1 { R = ∅ } + j ∑ y j ∣ R ∣ ∨ 1 1 { j ∈ R } . This also holds for R = ∅ R=\emptyset R = ∅ . Taking expectations under Q Q Q and using c j ( Q ) ≤ b j c_j(Q)\leq b_j c j ( Q ) ≤ b j ,
E Q ∣ R ∣ ≤ m Q ( R ≠ ∅ ) + ∑ j y j c j ( Q ) ≤ m + ∑ j y j b j = E [ κ ∗ ∣ E = e ] . {\mathbb E}_Q|R|\leq m\,Q(R\neq\emptyset)+\sum_jy_j\,c_j(Q)\leq m+\sum_jy_jb_j={\mathbb E}[\kappa^*\mid E=e]. E Q ∣ R ∣ ≤ m Q ( R = ∅ ) + j ∑ y j c j ( Q ) ≤ m + j ∑ y j b j = E [ κ ∗ ∣ E = e ] . The constant m m m and the weights y j y_j y j thus act as a dual certificate for the linear program that maximizes E Q ∣ R ∣ {\mathbb E}_Q|R| E Q ∣ R ∣ subject to the budget constraints.
For the second claim, take K = 5 K=5 K = 5 , α = 0.05 \alpha=0.05 α = 0.05 and e = ( 100 , 1 , 1 , 1 , 1 ) e=(100,1,1,1,1) e = ( 100 , 1 , 1 , 1 , 1 ) , so that b 1 = 1 b_1=1 b 1 = 1 and b j = 0.01 b_j=0.01 b j = 0.01 for j ≥ 2 j\geq2 j ≥ 2 . Let Q Q Q always reject H 1 H_1 H 1 and reject each other hypothesis independently with probability 0.02 0.02 0.02 . Then c 1 ( Q ) ≤ 1 = b 1 c_1(Q)\leq1=b_1 c 1 ( Q ) ≤ 1 = b 1 , and for j ≥ 2 j\geq2 j ≥ 2 , every rejection of H j H_j H j comes with that of H 1 H_1 H 1 , so c j ( Q ) ≤ 0.02 / 2 = b j c_j(Q)\leq0.02/2=b_j c j ( Q ) ≤ 0.02/2 = b j . Hence Q Q Q is certified, yet Q ( ∣ R ∣ ≥ 2 ) = 1 − 0.98 4 ≈ 0.078 Q(|R|\geq2)=1-0.98^4\approx0.078 Q ( ∣ R ∣ ≥ 2 ) = 1 − 0.9 8 4 ≈ 0.078 , whereas q 2 ∗ = 0.05 q^*_2=0.05 q 2 ∗ = 0.05 . Its expected number of rejections, 1.08 1.08 1.08 , is below E [ κ ∗ ∣ E = e ] = 1.2 {\mathbb E}[\kappa^*\mid E=e]=1.2 E [ κ ∗ ∣ E = e ] = 1.2 , as the first claim requires. ◻
Proof of Proposition 4.2
Throughout, e e e is fixed, S = S ♯ S=S^\sharp S = S ♯ , and c r = S r − S r + 1 c_r=S_r-S_{r+1} c r = S r − S r + 1 for r = 1 , … , K r=1,\ldots,K r = 1 , … , K , with c K + 1 = 0 c_{K+1}=0 c K + 1 = 0 . We show below that these are the charges of the rule. A state is identified with the set of ranks of its hypotheses, so that { s , … , K } \{s,\ldots,K\} { s , … , K } denotes the K − s + 1 K-s+1 K − s + 1 hypotheses with the smallest e-values. Write Φ s = α ∑ j ≥ s e [ j ] \Phi_s=\alpha\sum_{j\geq s}e_{[j]} Φ s = α ∑ j ≥ s e [ j ] for s = 1 , … , K + 1 s=1,\ldots,K+1 s = 1 , … , K + 1 , so that α e [ r ] = Φ r − Φ r + 1 \alpha e_{[r]}=\Phi_r-\Phi_{r+1} α e [ r ] = Φ r − Φ r + 1 and Φ s = ( K − s + 1 ) α m s \Phi_s=(K-s+1)\alpha m_s Φ s = ( K − s + 1 ) α m s . The sequence Φ \Phi Φ is convex, because its decrements α e [ s ] \alpha e_{[s]} α e [ s ] are non-increasing. We call s s s a vertex if S s = β s S_s=\beta_s S s = β s . The points 1 1 1 and K + 1 K+1 K + 1 are vertices, and S S S is linear between consecutive vertices. Since S ≤ β S\leq\beta S ≤ β and β s ≤ α m s \beta_s\leq\alpha m_s β s ≤ α m s , we have ( K − s + 1 ) S s ≤ Φ s (K-s+1)S_s\leq\Phi_s ( K − s + 1 ) S s ≤ Φ s for every s s s , with equality at every vertex s ≥ 2 s\geq2 s ≥ 2 . We first prove three lemmas that are central to the proof of Proposition 4.2 .
Lemma C.4. The sequence S S S is nonnegative, non-increasing and convex, and the charges c r c_r c r are nonnegative and non-increasing in r r r . The numbers p k ♯ = k ( c k − c k + 1 ) p^\sharp_k=k(c_k-c_{k+1}) p k ♯ = k ( c k − c k + 1 ) for k = 1 , … , K k=1,\ldots,K k = 1 , … , K and p 0 ♯ = 1 − S 1 p^\sharp_0=1-S_1 p 0 ♯ = 1 − S 1 form a distribution with charges c [ r ] ( p ♯ ) = c r c_{[r]}(p^\sharp)=c_r c [ r ] ( p ♯ ) = c r and tails q r ♯ q^\sharp_r q r ♯ , and κ ♯ \kappa^\sharp κ ♯ has the distribution p ♯ p^\sharp p ♯ given E = e E=e E = e . Moreover, q r ♯ q^\sharp_r q r ♯ is a continuous function of e e e .
Proof. The zero sequence is a convex minorant of β \beta β , so S ≥ 0 S\geq0 S ≥ 0 , and a nonnegative convex sequence that vanishes at K + 1 K+1 K + 1 is non-increasing. Hence c r ≥ 0 c_r\geq0 c r ≥ 0 , and c r c_r c r is non-increasing in r r r by convexity, so p k ♯ ≥ 0 p^\sharp_k\geq0 p k ♯ ≥ 0 for k ≥ 1 k\geq1 k ≥ 1 . Since ∑ k ≥ 1 p k ♯ = ∑ k ≥ 1 c k = S 1 ≤ β 1 ≤ 1 \sum_{k\geq1}p^\sharp_k=\sum_{k\geq1}c_k=S_1\leq\beta_1\leq1 ∑ k ≥ 1 p k ♯ = ∑ k ≥ 1 c k = S 1 ≤ β 1 ≤ 1 , also p 0 ♯ ≥ 0 p^\sharp_0\geq0 p 0 ♯ ≥ 0 , and the numbers sum to one. Telescoping gives ∑ k ≥ r p k ♯ / k = ∑ k ≥ r ( c k − c k + 1 ) = c r \sum_{k\geq r}p^\sharp_k/k=\sum_{k\geq r}(c_k-c_{k+1})=c_r ∑ k ≥ r p k ♯ / k = ∑ k ≥ r ( c k − c k + 1 ) = c r , so p ♯ p^\sharp p ♯ has the charges c r c_r c r , and by the accounting identity of § 4.3 its tails are r c r + ∑ j > r c j = r S r − ( r − 1 ) S r + 1 = q r ♯ r\,c_r+\sum_{j>r}c_j=rS_r-(r-1)S_{r+1}=q^\sharp_r r c r + ∑ j > r c j = r S r − ( r − 1 ) S r + 1 = q r ♯ . Tails of a distribution are non-increasing, so { κ ♯ ≥ r } = { U ≤ q r ♯ } \{\kappa^\sharp\geq r\}=\{U\leq q^\sharp_r\} { κ ♯ ≥ r } = { U ≤ q r ♯ } , and κ ♯ \kappa^\sharp κ ♯ has the distribution p ♯ p^\sharp p ♯ . Finally, β \beta β is continuous in e e e , and so is its greatest convex minorant. ◻
Lemma C.5. If a distribution p p p of the number of rejections satisfies S s ( p ) ≤ α m s S_s(p)\leq\alpha m_s S s ( p ) ≤ α m s for s = 1 , … , K s=1,\ldots,K s = 1 , … , K , then S ( p ) ≤ S S(p)\leq S S ( p ) ≤ S . In particular, this holds for every monotone rule certified by E e B H ‾ E^{\overline{\mathrm{eBH}}} E eBH .
Proof. Since also S 1 ( p ) = ∑ k ≥ 1 p k ≤ 1 S_1(p)=\sum_{k\geq1}p_k\leq1 S 1 ( p ) = ∑ k ≥ 1 p k ≤ 1 , we have S ( p ) ≤ β S(p)\leq\beta S ( p ) ≤ β . The charges c [ r ] ( p ) c_{[r]}(p) c [ r ] ( p ) are non-increasing in r r r , so S ( p ) S(p) S ( p ) is convex with S K + 1 ( p ) = 0 S_{K+1}(p)=0 S K + 1 ( p ) = 0 , and it is therefore a convex minorant of β \beta β , which lies below the greatest one, S S S . The constraints S s ( p ) ≤ α m s S_s(p)\leq\alpha m_s S s ( p ) ≤ α m s are the constraints (4.7) for the states { s , … , K } \{s,\ldots,K\} { s , … , K } . ◻
Lemma C.6. For 1 ≤ r < r ′ ≤ K 1\leq r<r'\leq K 1 ≤ r < r ′ ≤ K , ( K − r ) ( c r − c r ′ ) ≤ α ( e [ r ] − e [ r ′ ] ) .
(K-r)(c_r-c_{r'})\leq\alpha(e_{[r]}-e_{[r']}).
( K − r ) ( c r − c r ′ ) ≤ α ( e [ r ] − e [ r ′ ] ) .
Proof. Let w w w be the smallest vertex greater than r r r , and write γ = c r \gamma=c_r γ = c r , the slope magnitude of the linear piece of S S S that ends at w w w . If r ′ < w r'<w r ′ < w , then c r ′ = γ c_{r'}=\gamma c r ′ = γ , and (8.1) holds because e [ r ] ≥ e [ r ′ ] e_{[r]}\geq e_{[r']} e [ r ] ≥ e [ r ′ ] . Otherwise, let v v v be the largest vertex with v ≤ r ′ v\leq r' v ≤ r ′ , so that 2 ≤ w ≤ v 2\leq w\leq v 2 ≤ w ≤ v , c r ′ = c v = : γ ′ c_{r'}=c_v=:\gamma' c r ′ = c v =: γ ′ and e [ r ′ ] ≤ e [ v ] e_{[r']}\leq e_{[v]} e [ r ′ ] ≤ e [ v ] . We bound e [ r ] e_{[r]} e [ r ] from below and e [ v ] e_{[v]} e [ v ] from above. Since Φ \Phi Φ is convex and r < w r<w r < w , its decrement at r r r is at least its average decrement over [ r , w ] [r,w] [ r , w ] . With Φ r ≥ ( K − r + 1 ) S r \Phi_r\geq(K-r+1)S_r Φ r ≥ ( K − r + 1 ) S r , Φ w = ( K − w + 1 ) S w \Phi_w=(K-w+1)S_w Φ w = ( K − w + 1 ) S w and S r = S w + ( w − r ) γ S_r=S_w+(w-r)\gamma S r = S w + ( w − r ) γ , this gives
α e [ r ] ≥ Φ r − Φ w w − r ≥ ( K − r + 1 ) S r − ( K − w + 1 ) S w w − r = ( K − r + 1 ) γ + S w . \alpha e_{[r]}\geq\frac{\Phi_r-\Phi_w}{w-r}\geq\frac{(K-r+1)S_r-(K-w+1)S_w}{w-r}=(K-r+1)\gamma+S_w. α e [ r ] ≥ w − r Φ r − Φ w ≥ w − r ( K − r + 1 ) S r − ( K − w + 1 ) S w = ( K − r + 1 ) γ + S w . With Φ v = ( K − v + 1 ) S v \Phi_v=(K-v+1)S_v Φ v = ( K − v + 1 ) S v and Φ v + 1 ≥ ( K − v ) S v + 1 \Phi_{v+1}\geq(K-v)S_{v+1} Φ v + 1 ≥ ( K − v ) S v + 1 ,
α e [ v ] = Φ v − Φ v + 1 ≤ ( K − v + 1 ) S v − ( K − v ) S v + 1 = S v + ( K − v ) γ ′ . \alpha e_{[v]}=\Phi_v-\Phi_{v+1}\leq(K-v+1)S_v-(K-v)S_{v+1}=S_v+(K-v)\gamma'. α e [ v ] = Φ v − Φ v + 1 ≤ ( K − v + 1 ) S v − ( K − v ) S v + 1 = S v + ( K − v ) γ ′ . Since the slopes are non-increasing, S w − S v = ∑ i = w v − 1 c i ≥ ( v − w ) γ ′ S_w-S_v=\sum_{i=w}^{v-1}c_i\geq(v-w)\gamma' S w − S v = ∑ i = w v − 1 c i ≥ ( v − w ) γ ′ . Combining the three bounds,
α ( e [ r ] − e [ r ′ ] ) − ( K − r ) ( γ − γ ′ ) ≥ ( K − r + 1 ) γ + ( v − w ) γ ′ − ( K − v ) γ ′ − ( K − r ) ( γ − γ ′ ) = γ + ( 2 v − w − r ) γ ′ ≥ 0 , \alpha(e_{[r]}-e_{[r']})-(K-r)(\gamma-\gamma')\geq(K-r+1)\gamma+(v-w)\gamma'-(K-v)\gamma'-(K-r)(\gamma-\gamma')=\gamma+(2v-w-r)\gamma'\geq0, α ( e [ r ] − e [ r ′ ] ) − ( K − r ) ( γ − γ ′ ) ≥ ( K − r + 1 ) γ + ( v − w ) γ ′ − ( K − v ) γ ′ − ( K − r ) ( γ − γ ′ ) = γ + ( 2 v − w − r ) γ ′ ≥ 0 , since v ≥ w > r v\geq w>r v ≥ w > r . ◻
Proof of Proposition 4.2 . (i) Fix t t t and a state T T T with ∣ T ∣ = t |T|=t ∣ T ∣ = t , let U t = { K − t + 1 , … , K } U_t=\{K-t+1,\ldots,K\} U t = { K − t + 1 , … , K } , and let F ( T ) = ∑ r ∈ T ( t c r − α e [ r ] ) F(T)=\sum_{r\in T}(t\,c_r-\alpha e_{[r]}) F ( T ) = ∑ r ∈ T ( t c r − α e [ r ] ) , so that, by Lemma C.4 , the constraint (4.7) for T T T reads F ( T ) ≤ 0 F(T)\leq0 F ( T ) ≤ 0 . If T ≠ U t T\neq U_t T = U t , choose r ∈ T ∖ U t r\in T\setminus U_t r ∈ T ∖ U t and r ′ ∈ U t ∖ T r'\in U_t\setminus T r ′ ∈ U t ∖ T . Then r ≤ K − t < r ′ r\leq K-t<r' r ≤ K − t < r ′ , so t ≤ K − r t\leq K-r t ≤ K − r , and replacing r r r by r ′ r' r ′ in T T T changes F F F by
α ( e [ r ] − e [ r ′ ] ) − t ( c r − c r ′ ) ≥ α ( e [ r ] − e [ r ′ ] ) − ( K − r ) ( c r − c r ′ ) ≥ 0 , \alpha(e_{[r]}-e_{[r']})-t(c_r-c_{r'})\geq\alpha(e_{[r]}-e_{[r']})-(K-r)(c_r-c_{r'})\geq0, α ( e [ r ] − e [ r ′ ] ) − t ( c r − c r ′ ) ≥ α ( e [ r ] − e [ r ′ ] ) − ( K − r ) ( c r − c r ′ ) ≥ 0 , by c r ≥ c r ′ c_r\geq c_{r'} c r ≥ c r ′ and Lemma C.6 . Repeating such exchanges reaches U t U_t U t , so
F ( T ) ≤ F ( U t ) = t ( S K − t + 1 − α m K − t + 1 ) ≤ 0. F(T)\leq F(U_t)=t\,(S_{K-t+1}-\alpha m_{K-t+1})\leq0. F ( T ) ≤ F ( U t ) = t ( S K − t + 1 − α m K − t + 1 ) ≤ 0. Every constraint in (4.7) therefore holds. By Lemma C.4 , p ♯ ( e ) p^\sharp(e) p ♯ ( e ) is a measurable selection from the certified menu of E e B H ‾ E^{\overline{\mathrm{eBH}}} E eBH , and Theorem 2.1 gives E FDP T ( R κ ♯ ( E ) ) ≤ α E P E T e B H ‾ ≤ α {\mathbb E}\,\operatorname{FDP}_T(R_{\kappa^\sharp}(E))\leq\alpha\,{\mathbb E}_PE^{\overline{\mathrm{eBH}}}_T\leq\alpha E FDP T ( R κ ♯ ( E )) ≤ α E P E T eBH ≤ α for every nonempty T T T and P ∈ P T P\in\mathcal P_T P ∈ P T .
(ii) Fix r r r , and let v < w v<w v < w be consecutive vertices with v ≤ r < w v\leq r<w v ≤ r < w , so that c r = c v c_r=c_v c r = c v and S r = S v − ( r − v ) c v S_r=S_v-(r-v)c_v S r = S v − ( r − v ) c v . Then
q r ♯ = r S r − ( r − 1 ) S r + 1 = S v + ( v − 1 ) c v . q^\sharp_r=rS_r-(r-1)S_{r+1}=S_v+(v-1)c_v. q r ♯ = r S r − ( r − 1 ) S r + 1 = S v + ( v − 1 ) c v . If v = 1 v=1 v = 1 , then q r ♯ = S 1 = min { 1 , α m 1 } = q 1 ∗ ≥ q r ∗ q^\sharp_r=S_1=\min\{1,\alpha m_1\}=q^*_1\geq q^*_r q r ♯ = S 1 = min { 1 , α m 1 } = q 1 ∗ ≥ q r ∗ . If v = K v=K v = K , then r = K r=K r = K , c K = S K = α e [ K ] c_K=S_K=\alpha e_{[K]} c K = S K = α e [ K ] and q K ♯ = K α e [ K ] ≥ q K ∗ q^\sharp_K=K\alpha e_{[K]}\geq q^*_K q K ♯ = K α e [ K ] ≥ q K ∗ . Otherwise 2 ≤ v ≤ K − 1 2\leq v\leq K-1 2 ≤ v ≤ K − 1 , so S v = α m v S_v=\alpha m_v S v = α m v and c v = S v − S v + 1 ≥ α ( m v − m v + 1 ) c_v=S_v-S_{v+1}\geq\alpha(m_v-m_{v+1}) c v = S v − S v + 1 ≥ α ( m v − m v + 1 ) . With d = K − v + 1 d=K-v+1 d = K − v + 1 and e ˉ = m v + 1 \bar e=m_{v+1} e ˉ = m v + 1 , we have m v − m v + 1 = ( e [ v ] − e ˉ ) / d m_v-m_{v+1}=(e_{[v]}-\bar e)/d m v − m v + 1 = ( e [ v ] − e ˉ ) / d and ( d − 1 ) e ˉ = ∑ j > v e [ j ] (d-1)\bar e=\sum_{j>v}e_{[j]} ( d − 1 ) e ˉ = ∑ j > v e [ j ] , and a direct computation gives
q r ♯ ≥ α m v + ( v − 1 ) α e [ v ] − e ˉ d = α K ( v e [ v ] + ∑ j > v e [ j ] ) + α v ( v − 1 ) ( e [ v ] − e ˉ ) d K ≥ q v ∗ ≥ q r ∗ , q^\sharp_r\geq\alpha m_v+(v-1)\,\alpha\,\frac{e_{[v]}-\bar e}{d}
=\frac\alpha K\Bigl(v\,e_{[v]}+\sum_{j>v}e_{[j]}\Bigr)+\frac{\alpha\,v(v-1)(e_{[v]}-\bar e)}{dK}\geq q^*_v\geq q^*_r, q r ♯ ≥ α m v + ( v − 1 ) α d e [ v ] − e ˉ = K α ( v e [ v ] + j > v ∑ e [ j ] ) + d K α v ( v − 1 ) ( e [ v ] − e ˉ ) ≥ q v ∗ ≥ q r ∗ , because e [ v ] ≥ e ˉ e_{[v]}\geq\bar e e [ v ] ≥ e ˉ and q ∗ q^* q ∗ is non-increasing. In all cases q r ♯ ≥ q r ∗ q^\sharp_r\geq q^*_r q r ♯ ≥ q r ∗ , so with the same U U U , { κ ∗ ≥ r } ⊆ { κ ♯ ≥ r } \{\kappa^*\geq r\}\subseteq\{\kappa^\sharp\geq r\} { κ ∗ ≥ r } ⊆ { κ ♯ ≥ r } for every r r r , and R κ ∗ ( e ) ⊆ R κ ♯ ( e ) R_{\kappa^*}(e)\subseteq R_{\kappa^\sharp}(e) R κ ∗ ( e ) ⊆ R κ ♯ ( e ) .
(iii) Consider the linear program that maximizes ∑ k = 1 K k p k \sum_{k=1}^Kk\,p_k ∑ k = 1 K k p k over p 1 , … , p K ≥ 0 p_1,\ldots,p_K\geq0 p 1 , … , p K ≥ 0 with ∑ k p k ≤ 1 \sum_kp_k\leq1 ∑ k p k ≤ 1 , subject only to the constraints for the states { s , … , K } \{s,\ldots,K\} { s , … , K } ,
S s ( p ) = ∑ k = 1 K p k ( k − s + 1 ) + k ≤ α m s , s = 1 , … , K . S_s(p)=\sum_{k=1}^Kp_k\frac{(k-s+1)_+}{k}\leq\alpha m_s,\qquad s=1,\ldots,K. S s ( p ) = k = 1 ∑ K p k k ( k − s + 1 ) + ≤ α m s , s = 1 , … , K . By the accounting identity, its objective is ∑ r ( 2 r − 1 ) c [ r ] ( p ) = S 1 ( p ) + 2 ∑ s ≥ 2 S s ( p ) \sum_r(2r-1)c_{[r]}(p)=S_1(p)+2\sum_{s\geq2}S_s(p) ∑ r ( 2 r − 1 ) c [ r ] ( p ) = S 1 ( p ) + 2 ∑ s ≥ 2 S s ( p ) , which increases with every S s ( p ) S_s(p) S s ( p ) . Every feasible p p p satisfies S ( p ) ≤ S S(p)\leq S S ( p ) ≤ S by Lemma C.5 , and p ♯ p^\sharp p ♯ is feasible with S ( p ♯ ) = S S(p^\sharp)=S S ( p ♯ ) = S , so the value of the program is E [ κ ♯ ∣ E = e ] {\mathbb E}[\kappa^\sharp\mid E=e] E [ κ ♯ ∣ E = e ] . By linear programming duality, there are λ 1 , … , λ K ≥ 0 \lambda_1,\ldots,\lambda_K\geq0 λ 1 , … , λ K ≥ 0 and μ ≥ 0 \mu\geq0 μ ≥ 0 with ∑ s λ s α m s + μ = E [ κ ♯ ∣ E = e ] \sum_s\lambda_s\alpha m_s+\mu={\mathbb E}[\kappa^\sharp\mid E=e] ∑ s λ s α m s + μ = E [ κ ♯ ∣ E = e ] and
∑ s = 1 K λ s ( k − s + 1 ) + k + μ ≥ k , k = 1 , … , K . \sum_{s=1}^K\lambda_s\frac{(k-s+1)_+}{k}+\mu\geq k,\qquad k=1,\ldots,K. s = 1 ∑ K λ s k ( k − s + 1 ) + + μ ≥ k , k = 1 , … , K . A set R R R of size k ≥ 1 k\geq1 k ≥ 1 contains at least ( k − s + 1 ) + (k-s+1)_+ ( k − s + 1 ) + of the K − s + 1 K-s+1 K − s + 1 hypotheses of rank at least s s s , so
∣ R ∣ ≤ ∑ s = 1 K λ s ∣ R ∩ { s , … , K } ∣ ∣ R ∣ ∨ 1 + μ 1 { R ≠ ∅ } , |R|\leq\sum_{s=1}^K\lambda_s\frac{|R\cap\{s,\ldots,K\}|}{|R|\vee1}+\mu\,\mathop{\mathrm{\mathds{1}}}\{R\neq\varnothing\}, ∣ R ∣ ≤ s = 1 ∑ K λ s ∣ R ∣ ∨ 1 ∣ R ∩ { s , … , K } ∣ + μ 1 { R = ∅ } , which also holds for R = ∅ R=\varnothing R = ∅ . Let Q Q Q be a distribution of rejection sets certified by E e B H ‾ E^{\overline{\mathrm{eBH}}} E eBH . Its averaged false discovery proportion in the state { s , … , K } \{s,\ldots,K\} { s , … , K } is at most α m s \alpha m_s α m s , so taking expectations under Q Q Q gives
E Q ∣ R ∣ ≤ ∑ s λ s E Q [ ∣ R ∩ { s , … , K } ∣ ∣ R ∣ ∨ 1 ] + μ Q ( R ≠ ∅ ) ≤ ∑ s λ s α m s + μ = E [ κ ♯ ∣ E = e ] . {\mathbb E}_Q|R|\leq\sum_s\lambda_s\,{\mathbb E}_Q\Bigl[\frac{|R\cap\{s,\ldots,K\}|}{|R|\vee1}\Bigr]+\mu\,Q(R\neq\varnothing)\leq\sum_s\lambda_s\alpha m_s+\mu={\mathbb E}[\kappa^\sharp\mid E=e]. E Q ∣ R ∣ ≤ s ∑ λ s E Q [ ∣ R ∣ ∨ 1 ∣ R ∩ { s , … , K } ∣ ] + μ Q ( R = ∅ ) ≤ s ∑ λ s α m s + μ = E [ κ ♯ ∣ E = e ] . The rejection set of closed e-BH is certified by E e B H ‾ E^{\overline{\mathrm{eBH}}} E eBH , which proves the last assertion. ◻
The minimally adaptive improvement
We show that the minimally adaptive principle yields a valid rule that rejects at least as much as RU-eBH and sometimes strictly more, so that RU-eBH is not admissible. For a level γ > 0 \gamma>0 γ > 0 , write κ γ ∗ \kappa^*_\gamma κ γ ∗ for the rule κ ∗ \kappa^* κ ∗ computed at level γ \gamma γ instead of α \alpha α , with the same U U U , so that κ ∗ = κ α ∗ \kappa^*=\kappa^*_\alpha κ ∗ = κ α ∗ . Let K ≥ 2 K\geq2 K ≥ 2 and α ′ = K α / ( K − 1 ) \alpha'=K\alpha/(K-1) α ′ = K α / ( K − 1 ) , and define
R † = { R κ α ′ ∗ ( E ) , κ α ∗ > 0 , ∅ , κ α ∗ = 0. R^\dagger=\begin{cases}R_{\kappa^*_{\alpha'}}(E),&\kappa^*_\alpha>0,\\ \emptyset,&\kappa^*_\alpha=0.\end{cases} R † = { R κ α ′ ∗ ( E ) , ∅ , κ α ∗ > 0 , κ α ∗ = 0.
Proposition C.7. The rule R † R^\dagger R † has the following properties.
Its FDR is at most α \alpha α in every state T T T and under every law in P T \mathcal P_T P T .
It contains the RU-eBH rejection set for every E E E and U U U , and under some law it makes strictly more true discoveries with positive probability.
It is certified by E e B H ‾ E^{\overline{\mathrm{eBH}}} E eBH , so RC-eBH rejects at least as many hypotheses as R † R^\dagger R † in expectation given E = e E=e E = e .
Proof. Let B T † = E T e B H B^\dagger_T=E^{\mathrm{eBH}}_T B T † = E T eBH for the full set T = { 1 , … , K } T=\{1,\ldots,K\} T = { 1 , … , K } and B T † = ( K − 1 ) − 1 ∑ j ∈ T E j B^\dagger_T=(K-1)^{-1}\sum_{j\in T}E_j B T † = ( K − 1 ) − 1 ∑ j ∈ T E j for every other nonempty T T T . This is an e-collection, because a state other than the full set contains at most K − 1 K-1 K − 1 true nulls, and it exceeds E e B H E^{\mathrm{eBH}} E eBH on every proper nonempty state.
(i) Given E = e E=e E = e , R † R^\dagger R † is a monotone rule, and we bound its averaged loss in each state. In the full state, every rejection is false, so the averaged loss is P ( κ α ∗ > 0 ∣ E = e ) = q 1 ∗ ≤ ( α / K ) ∑ j e j = α B T † \mathbb P(\kappa^*_\alpha>0\mid E=e)=q^*_1\leq(\alpha/K)\sum_je_j=\alpha B^\dagger_T P ( κ α ∗ > 0 ∣ E = e ) = q 1 ∗ ≤ ( α / K ) ∑ j e j = α B T † . In any other nonempty state T T T , the set R † R^\dagger R † is either R κ α ′ ∗ R_{\kappa^*_{\alpha'}} R κ α ′ ∗ or empty, so its averaged loss is at most that of R κ α ′ ∗ R_{\kappa^*_{\alpha'}} R κ α ′ ∗ . By the menu (4.4) at level α ′ \alpha' α ′ , the latter is at most ( α ′ / K ) ∑ j ∈ T e j = α B T † (\alpha'/K)\sum_{j\in T}e_j=\alpha B^\dagger_T ( α ′ / K ) ∑ j ∈ T e j = α B T † . Hence R † R^\dagger R † selects from the certified menu of B † B^\dagger B † , measurably in e e e , and Theorem 2.1 gives an FDR of at most α E P B T † ≤ α \alpha\,{\mathbb E}_PB^\dagger_T\leq\alpha α E P B T † ≤ α .
(ii) The tails q r ∗ q^*_r q r ∗ are non-decreasing in the level, so κ α ′ ∗ ≥ κ α ∗ \kappa^*_{\alpha'}\geq\kappa^*_\alpha κ α ′ ∗ ≥ κ α ∗ , and R † ⊇ R κ α ∗ ( E ) R^\dagger\supseteq R_{\kappa^*_\alpha}(E) R † ⊇ R κ α ∗ ( E ) for every E E E and U U U . For the strict improvement, let e ∘ = ( 1 / α , 1 / ( 2 α ) , … , 1 / ( 2 α ) ) e^\circ=(1/\alpha,1/(2\alpha),\ldots,1/(2\alpha)) e ∘ = ( 1/ α , 1/ ( 2 α ) , … , 1/ ( 2 α )) . At level α \alpha α , q 1 ∗ = ( K + 1 ) / ( 2 K ) q^*_1=(K+1)/(2K) q 1 ∗ = ( K + 1 ) / ( 2 K ) and q r ∗ = 1 / 2 q^*_r=1/2 q r ∗ = 1/2 for r ≥ 2 r\geq2 r ≥ 2 , whereas at level α ′ \alpha' α ′ , every q r ∗ q^*_r q r ∗ is at least K / ( 2 ( K − 1 ) ) > ( K + 1 ) / ( 2 K ) K/(2(K-1))>(K+1)/(2K) K / ( 2 ( K − 1 )) > ( K + 1 ) / ( 2 K ) . For 1 / 2 < U ≤ ( K + 1 ) / ( 2 K ) 1/2<U\leq(K+1)/(2K) 1/2 < U ≤ ( K + 1 ) / ( 2 K ) , RU-eBH therefore rejects only H 1 H_1 H 1 , whereas R † R^\dagger R † rejects all K K K hypotheses. Under the law with T = { 1 } T=\{1\} T = { 1 } in which E = e ∘ E=e^\circ E = e ∘ with probability α \alpha α and E = 0 E=0 E = 0 otherwise, R † R^\dagger R † makes K − 1 K-1 K − 1 more true discoveries than RU-eBH with probability α / ( 2 K ) \alpha/(2K) α / ( 2 K ) .
(iii) Since a nonempty state T ≠ { 1 , … , K } T\neq\{1,\ldots,K\} T = { 1 , … , K } has ∣ T ∣ ≤ K − 1 |T|\leq K-1 ∣ T ∣ ≤ K − 1 , we have B † ≤ E e B H ‾ B^\dagger\leq E^{\overline{\mathrm{eBH}}} B † ≤ E eBH , with equality on the full set. The certified menu of B † B^\dagger B † is therefore contained in that of E e B H ‾ E^{\overline{\mathrm{eBH}}} E eBH , and Proposition 4.2 (iii) applies. ◻
Conditional calibration as recertification
This subsection spells out the correspondence summarized in Remark 4.3 . We restate the e-BH version of conditional calibration of [29 ] in our terms, without modifying it. Let e 1 ( X ) , … , e K ( X ) e_1(X),\ldots,e_K(X) e 1 ( X ) , … , e K ( X ) be finite e-values computed from data X X X , let R 0 = e B H α ( e ( X ) ) R_0=\mathop{\mathrm{eBH}}_\alpha(e(X)) R 0 = eBH α ( e ( X )) and r = ∣ R 0 ∣ r=|R_0| r = ∣ R 0 ∣ , and for each j j j and c ≥ 1 c\geq1 c ≥ 1 let
t j ( X ) = K α ∣ R 0 ∪ { j } ∣ , h j ( c , X ) = t j ( X ) 1 { c e j ( X ) ≥ t j ( X ) } . t_j(X)=\frac{K}{\alpha\,|R_0\cup\{j\}|},\qquad
h_j(c,X)=t_j(X)\mathop{\mathrm{\mathds{1}}}\{c\,e_j(X)\geq t_j(X)\}. t j ( X ) = α ∣ R 0 ∪ { j } ∣ K , h j ( c , X ) = t j ( X ) 1 { c e j ( X ) ≥ t j ( X )} .
For j ∈ R 0 j\in R_0 j ∈ R 0 , t j = K / ( α r ) t_j=K/(\alpha r) t j = K / ( α r ) is the self-consistency threshold that e j e_j e j already passes, and for j ∉ R 0 j\notin R_0 j ∈ / R 0 , t j = K / ( α ( r + 1 ) ) t_j=K/(\alpha(r+1)) t j = K / ( α ( r + 1 )) is the value that e j e_j e j would need for R 0 ∪ { j } R_0\cup\{j\} R 0 ∪ { j } to be self-consistent. The quantity h j ( c , X ) h_j(c,X) h j ( c , X ) inflates e j e_j e j by the factor c c c and then records only whether the threshold is reached; it is non-decreasing in c c c .
At c = 1 c=1 c = 1 , these are the pruned e-values of Remark 4.3 ,
h j ( 1 , X ) = K 1 { j ∈ R 0 } α ( r ∨ 1 ) ≤ e j ( X ) . h_j(1,X)=\frac{K\mathop{\mathrm{\mathds{1}}}\{j\in R_0\}}{\alpha(r\vee1)}\leq e_j(X). h j ( 1 , X ) = α ( r ∨ 1 ) K 1 { j ∈ R 0 } ≤ e j ( X ) .
Indeed, every member of R 0 R_0 R 0 passes its threshold, whereas no j ∉ R 0 j\notin R_0 j ∈ / R 0 can satisfy e j ≥ K / ( α ( r + 1 ) ) e_j\geq K/(\alpha(r+1)) e j ≥ K / ( α ( r + 1 )) , since all r + 1 r+1 r + 1 members of R 0 ∪ { j } R_0\cup\{j\} R 0 ∪ { j } would then reach this value and e-BH would reject at least r + 1 r+1 r + 1 hypotheses. Applying e-BH to the pruned e-values therefore rejects exactly R 0 R_0 R 0 . They retain all the evidence that e-BH uses, and the difference e j − h j ( 1 , X ) ≥ 0 e_j-h_j(1,X)\geq0 e j − h j ( 1 , X ) ≥ 0 is the evidence that it discards.
Conditional calibration spends this discarded evidence. Suppose that under H j H_j H j a statistic S j S_j S j makes the conditional law of X X X given S j S_j S j known and common to all distributions in H j H_j H j . Then
Φ j ( c ; S j ) = E [ h j ( c , X ) − e j ( X ) ∣ S j ] \Phi_j(c;S_j)={\mathbb E}[h_j(c,X)-e_j(X)\mid S_j] Φ j ( c ; S j ) = E [ h j ( c , X ) − e j ( X ) ∣ S j ]
can be computed, for instance by sampling from this conditional law. It is non-decreasing in c c c and nonpositive at c = 1 c=1 c = 1 , so the inflation can be raised until Φ j \Phi_j Φ j reaches zero. For an S j S_j S j -measurable c j ≥ 1 c_j\geq1 c j ≥ 1 with Φ j ( c j ; S j ) ≤ 0 \Phi_j(c_j;S_j)\leq0 Φ j ( c j ; S j ) ≤ 0 , the recalibrated value e j ′ = h j ( c j , X ) e'_j=h_j(c_j,X) e j ′ = h j ( c j , X ) satisfies
E [ e j ′ ∣ S j ] = E [ e j ∣ S j ] + Φ j ( c j ; S j ) ≤ E [ e j ∣ S j ] , {\mathbb E}[e'_j\mid S_j]={\mathbb E}[e_j\mid S_j]+\Phi_j(c_j;S_j)\leq{\mathbb E}[e_j\mid S_j], E [ e j ′ ∣ S j ] = E [ e j ∣ S j ] + Φ j ( c j ; S j ) ≤ E [ e j ∣ S j ] ,
because c j c_j c j is fixed once S j S_j S j is known, and it is therefore an e-value under H j H_j H j . For j ∈ R 0 j\in R_0 j ∈ R 0 , c j e j ≥ e j ≥ t j c_je_j\geq e_j\geq t_j c j e j ≥ e j ≥ t j , so e j ′ = K / ( α r ) e'_j=K/(\alpha r) e j ′ = K / ( α r ) , and e-BH applied to e ′ e' e ′ rejects at least R 0 R_0 R 0 . A hypothesis outside R 0 R_0 R 0 is added whenever its inflated e-value reaches K / ( α ( r + 1 ) ) K/(\alpha(r+1)) K / ( α ( r + 1 )) .
This is exactly Proposition 2.2 in the language of § 2.3 . The conditioning statistic is S j S_j S j , the baseline is the pruned e-value h j ( 1 , X ) h_j(1,X) h j ( 1 , X ) with conditional mean H = E [ h j ( 1 , X ) ∣ S j ] H={\mathbb E}[h_j(1,X)\mid S_j] H = E [ h j ( 1 , X ) ∣ S j ] , and the budget is B = E [ e j ∣ S j ] B={\mathbb E}[e_j\mid S_j] B = E [ e j ∣ S j ] , whose mean is at most one under H j H_j H j , although it may exceed one for some values of S j S_j S j . The increment W = h j ( c j , X ) − h j ( 1 , X ) W=h_j(c_j,X)-h_j(1,X) W = h j ( c j , X ) − h j ( 1 , X ) is nonnegative, and since B − H = E [ e j − h j ( 1 , X ) ∣ S j ] B-H={\mathbb E}[e_j-h_j(1,X)\mid S_j] B − H = E [ e j − h j ( 1 , X ) ∣ S j ] , the condition Φ j ( c j ; S j ) ≤ 0 \Phi_j(c_j;S_j)\leq0 Φ j ( c j ; S j ) ≤ 0 is exactly (2.9) . The recalibrated e-values then certify rejection sets through the e-collection (4.1) evaluated at e ′ e' e ′ , whose largest certified set is e B H α ( e ′ ) \mathop{\mathrm{eBH}}_\alpha(e') eBH α ( e ′ ) . Conditional calibration thus spends unused budget across the values of the data that share the same S j S_j S j , whereas RU-eBH spends it across the values of the external seed.
Finally, [29 ] take the largest admissible factor c j ∗ = sup { c ≥ 1 : Φ j ( c ; S j ) ≤ 0 } c^*_j=\sup\{c\geq1:\Phi_j(c;S_j)\leq0\} c j ∗ = sup { c ≥ 1 : Φ j ( c ; S j ) ≤ 0 } , which need not be attained, because h j ( c , X ) h_j(c,X) h j ( c , X ) jumps in c c c . If Φ j ( c j ∗ ; S j ) > 0 \Phi_j(c^*_j;S_j)>0 Φ j ( c j ∗ ; S j ) > 0 , the value t j ( X ) 1 { c j ∗ e j ( X ) > t j ( X ) } t_j(X)\mathop{\mathrm{\mathds{1}}}\{c^*_je_j(X)>t_j(X)\} t j ( X ) 1 { c j ∗ e j ( X ) > t j ( X )} , with strict inequality, is the increasing limit of h j ( c , X ) h_j(c,X) h j ( c , X ) as c ↑ c j ∗ c\uparrow c^*_j c ↑ c j ∗ , so monotone convergence preserves the bound on its conditional mean, and since c j ∗ > 1 c^*_j>1 c j ∗ > 1 , it still equals K / ( α r ) K/(\alpha r) K / ( α r ) on R 0 R_0 R 0 .