Paper deep dive
Finite-sample certification of coverage regret for budgeted document selection under adaptive stratified auditing
Nora Serdyukova
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Selecting a budget-constrained set of documentary fragments, for instance the knowledge base of a retrieval-augmented generation system, raises a statistical question: how much expected query coverage is lost relative to the best feasible selection when the query distribution is unknown? We construct finite-sample, distribution-free upper confidence bounds for this coverage regret that remain valid after data-dependent selection. A pilot stage may select the document set, screen competitors, build comparison networks and learn an annotation policy. Then an independent audit acquires relevance labels with probabilities that are constant within observable strata. The main result is a simultaneous bound for all retained coverage contrasts. The bound is made observable by empirical-Bernstein variance calibration or by a one-stage construction without calibration, and it accounts for estimated stratum proportions. For maximum-type coverage we prove variance contractions for swaps of redundant fragments, give a condition under which multiscale radii improve on a direct union bound, and show that such redundancy cannot be certified from samples alone. A simulation study confirms validity and quantifies the gains from variance calibration and certified redundancy.
Tags
Links
- Source: https://arxiv.org/abs/2610.19207v1
- Canonical: https://arxiv.org/abs/2610.19207v1
Trouble viewing inline? Open PDF directly →
Full Text
78,487 characters extracted from source content.
Expand or collapse full text
Finite-sample certification of coverage regret for budgeted document selection under adaptive stratified auditing Nora Serdyukova Affiliation: Department of Statistics, University of Concepcion, Chile Email: nserdyukova@udec.cl Abstract Selecting a budget-constrained set of documentary fragments, for instance the knowledge base of a retrieval-augmented generation system, raises a statistical question: how much expected query coverage is lost relative to the best feasible selection when the query distribution is unknown? We construct finite-sample, distribution-free upper confidence bounds for this coverage regret that remain valid after data-dependent selection. A pilot stage may select the document set, screen competitors, build comparison networks and learn an annotation policy. Then an independent audit acquires relevance labels with probabilities that are constant within observable strata. The main result is a simultaneous bound for all retained coverage contrasts. The bound is made observable by empirical-Bernstein variance calibration or by a one-stage construction without calibration, and it accounts for estimated stratum proportions. For maximum-type coverage we prove variance contractions for swaps of redundant fragments, give a condition under which multiscale radii improve on a direct union bound, and show that such redundancy cannot be certified from samples alone. A simulation study confirms validity and quantifies the gains from variance calibration and certified redundancy. MSC2020 subject classifications: Primary 62G15, 60E15; secondary 68P20, 90C27. Keywords and phrases: Regret certification, postselection inference, empirical Bernstein inequalities, chaining, submodular coverage, retrieval-augmented generation. 1 Introduction Constructing a compact knowledge base from a large collection of documentary fragments, for example the retrieval corpus of a retrieval-augmented generation (RAG) system, requires choosing which fragments to retain under a storage or annotation budget. The selected collection should support future queries, whose probability distribution is generally not known in advance. This leads to a stochastic set-optimization problem: maximize expected query coverage, then certify the loss in coverage relative to the best feasible collection. The distinction between a computational approximation guarantee and a statistical coverage certificate is essential. A near-optimal value for the empirical selection objective need not imply a small population regret. For coverage defined by maxima of nonnegative relevance scores, the population objective is monotone and submodular. This connects the selection problem to classical submodular maximization (Nemhauser et al., 1978; Krause and Golovin, 2014). Yet the statistical component is different: relevance assessments may be costly, and queries may be deliberately oversampled in contexts believed to distinguish competing document selections. Such adaptive data acquisition must not be allowed to invalidate a confidence statement about the unknown query population. Concentration for means with unknown variances is classical (Maurer and Pontil, 2009; Boucheron et al., 2013). Stratified empirical-Bernstein methods have been developed for other estimation problems, for instance by Burgess and Chapman (2021), and context-dependent evaluation and inverse-probability correction have substantial precedents (Dudík et al., 2011). Generic chaining (Talagrand, 2005; Dirksen, 2015) and local complexity theory (Bartlett et al., 2005; Koltchinskii, 2006) explain why it may be possible to replace a crude logarithm of the number of candidates by a multiscale complexity. Consequently, neither stratification nor chaining is claimed to be new here. The goal is to give a self-contained and precisely scoped concentration argument for documentary coverage contrasts, including all the conditioning, sampling, and calibration steps needed to turn the inequality into a valid postselection regret certificate. Our results are the following. First, we derive a conditional, variance-sensitive Bernstein bound for increments of the empirical coverage process (Lemma 1). Second, a pre-audit multiscale representation yields a simultaneous pathwise bound for all retained competitors (Theorem 1). Third, the variance factors can be replaced by simultaneous empirical upper confidence bounds (Theorem 2). Fourth, a separate estimate of the unknown context proportions yields an unconditional confidence certificate for reduced-universe regret (Theorem 4); we also give a complementary pooled Bennett formulation (Proposition 4). Finally, a contraction lemma links the edge variances to both semantic redundancy and the frequency with which a swapped fragment is actually responsible for coverage (Lemma 5); Corollary 4 provides an explicit condition for a two-level improvement over a direct union bound. Two complementary refinements are proved: an edgewise allocation of confidence error, which controls each distinct edge only once (Proposition 3), and a one-stage empirical-Bernstein network bound that does not require preliminary variance calibration (Theorem 3). A finite-sample rare-query example (Proposition 5) explains why empirical profile agreement cannot certify uniform approximation envelopes. A simulation study (Section 10) confirms the validity of all certificates at the nominal level and compares their sizes; it shows when variance calibration and the multiscale network pay off, and that the latter requires certified redundancy envelopes. The reader should distinguish validity, which is established under specified assumptions, from efficiency, which depends on the geometry of the competitors and on the audit design. 2 Statistical model, selection problem, and notation 2.1 Query population and document selection Let (,)(Q, Q) be a measurable query space. Let Q have an arbitrary and unknown probability distribution P on this space. The set of available documentary fragments is the finite nonempty set =1,…,KA=\1,…,K\, with deterministic costs cj>0c_j>0. For a budget B≥0B≥ 0, define the feasible selection family ℋB=S⊆:∑j∈Scj≤B.H_B= \S : _j∈ Sc_j≤ B \. (1) The empty set is feasible and is assigned zero coverage. A relevance function rj:→[0,1]r_j:Q→[0,1] is associated with each fragment. Unless stated otherwise, these functions are fixed, measurable and evaluated without labeling error when a query is audited. The coverage of a selection S on query q is hS(q)=maxj∈Srj(q),S≠∅,0,S=∅.F(S)=PhS(Q).h_S(q)= cases _j∈ Sr_j(q),&S≠ ,\\ 0,&S= . cases F(S)=E_Ph_S(Q). (2) Thus 0≤hS,F(S)≤10≤ h_S,F(S)≤ 1. Since ℋBH_B is finite and nonempty, there exists at least one population maximizer. Fix any S⋆∈argmaxS∈ℋBF(S),RB(S)=F(S⋆)−F(S)∈[0,1].S ∈ *arg\,max_S _BF(S), R_B(S)=F(S )-F(S)∈[0,1]. (3) The definition does not presume that the maximum can be calculated computationally on a large instance. It provides the statistical target. Proposition 1 (Monotonicity and submodularity). For every fixed query q, the set function S↦hS(q)S h_S(q) is normalized, monotone and submodular. The population function F possesses the same properties. Proof. Normalization follows from h∅(q)=0h_ (q)=0, while monotonicity follows because a maximum cannot decrease when additional elements are included. If A⊆BA B and j∉Bj∉ B, then hA∪j(q)−hA(q)=[rj(q)−hA(q)]+≥[rj(q)−hB(q)]+=hB∪j(q)−hB(q),h_A∪\j\(q)-h_A(q)=[r_j(q)-h_A(q)]_+≥[r_j(q)-h_B(q)]_+=h_B∪\j\(q)-h_B(q), where [x]+=max(x,0)[x]_+= (x,0). This is the diminishing-returns characterization of submodularity. Expectations preserve normalization, monotonicity and the displayed pointwise inequality. ∎ 2.2 Pilot selection and honest screening We use ℱ0 F_0 to denote the sigma-field generated by all pilot observations and all randomness used before the independent audit and unlabelled-proportion samples. The pilot produces a feasible selected set S^∈ℋB S _B and a finite (possibly random) candidate family ⊆ℋBC _B such that S^∈ S . Both are ℱ0 F_0-measurable. The documentary contrast against a competitor T∈T is DT(q)=hT(q)−hS^(q),ΔT=PDT(Q)=F(T)−F(S^).D_T(q)=h_T(q)-h_ S(q), _T=E_PD_T(Q)=F(T)-F( S). (4) Every contrast is in [−1,1][-1,1] and DS^≡0D_ S≡ 0. The pilot screening guarantee, when screening is used, is ℙsome S⋆∈≥1−αs.P\some S \≥ 1- _s. (5) If =ℋBC=H_B, this property holds deterministically and αs=0 _s=0. Here and below “some” allows non-uniqueness of the population optimum. A sufficient, explicitly verifiable pilot rule is established in Proposition 2. Proposition 2 (A conservative pilot screening rule). Assume that a fully labeled iid pilot of n0n_0 queries from P, independent of subsequent data, is available, and let F^0(S)=n0−1∑i=1n0hS(Qi(0)) F_0(S)=n_0^-1 _i=1^n_0h_S(Q_i^(0)) for all S∈ℋBS _B. For 0<αs<10< _s<1, set r0=log(2|ℋB|/αs)2n0.r_0= (2|H_B|/ _s)2n_0. (6) After choosing any pilot-measurable S^∈ℋB S _B, let =S^∪T∈ℋB:F^0(T)−F^0(S^)+2r0≥0.C=\ S\∪ \T _B: F_0(T)- F_0( S)+2r_0≥ 0 \. (7) Then (5) holds. Proof. By Hoeffding’s inequality (Hoeffding, 1963) and a union bound, with probability at least 1−αs1- _s, |F^0(S)−F(S)|≤r0| F_0(S)-F(S)|≤ r_0 simultaneously for all S∈ℋBS _B. On this event, if S⋆S is a population maximizer, F^0(S⋆)−F^0(S^)+2r0≥F(S⋆)−F(S^)≥0. F_0(S )- F_0( S)+2r_0≥ F(S )-F( S)≥ 0. Thus S⋆∈S . The argument remains valid when S S is chosen adaptively from the same pilot, precisely because the pilot bound is uniform. ∎ 2.3 Observable contexts and the audit design Let X=ϕ(Q)X=φ(Q) be an observable categorical feature, inexpensive to record, with values in =0,…,H−1S=\0,…,H-1\, where H≥2H≥ 2 is fixed. Let πh=ℙ(X=h)>0 _h=P(X=h)>0 and Ph(⋅)=ℙ(Q∈⋅∣X=h)P_h(·)=P(Q∈· X=h). Both πh _h and PhP_h are unknown. We distinguish an unlabelled sample, used to estimate the population proportions, from the labeled audit sample. Assumption 1 (Independent unlabelled queries). The queries Q1(u),…,QNu(u)Q_1^(u),…,Q_N_u^(u) are, conditionally on ℱ0 F_0, iid from P and independent of the queries and relevance labels used for audit. The empirical proportions π^h=1Nu∑i=1Nuϕ(Qi(u))=h π_h= 1N_u _i=1^N_u1\φ(Q_i^(u))=h\ are observed, Nu≥1N_u≥ 1. The multiscale networks and acquisition policy may use this unlabelled sample, but may not use audit relevance labels. Assumption 2 (Stratified, label-ignorable audit). Conditionally on the pilot, the unlabelled sample, and the labeled counts nh≥2n_h≥ 2, the acquired audit queries Qh,1,…,Qh,nhQ_h,1,…,Q_h,n_h are iid from PhP_h within each stratum, and the collections are mutually independent across strata. The counts and the mechanism that chooses them contain no information about the unobserved relevance values beyond the contexts. All relevance values needed to calculate hT(Qh,i)h_T(Q_h,i), T∈T , are observed for an acquired query. An important implementation satisfying Assumption 2 starts with fresh iid queries, observes X, and acquires full relevance labels with probability ph∈(0,1]p_h∈(0,1] in stratum h, where php_h is learned before audit and is constant within the stratum. Conditional on the resulting stratum counts (and the design information), the selected queries have the required conditional law. A design based on a new feature within an existing stratum does not generally satisfy this assumption; its selection bias must be addressed separately, for example through known-propensity estimators as in Dudík et al. (2011). The sample size nhn_h may be random. Every assertion below is conditional on the pre-audit information and on the observed admissible counts, and therefore remains valid after averaging over their joint distribution. If some nh<2n_h<2, our empirical-variance formulas are not used and the trivial regret upper bound 11 can be returned. 2.4 Conditional and population coverage contrasts For every T∈T , write μh,T=[DT(Q)∣X=h],D¯h,T=1nh∑i=1nhDT(Qh,i),Δ^T=∑h∈π^hD¯h,T. _h,T=E[D_T(Q) X=h], D_h,T= 1n_h _i=1^n_hD_T(Q_h,i), _T= _h π_h D_h,T. (8) The population contrast decomposes as ΔT=∑hπhμh,T _T= _h _h _h,T. The centered weighted audit process is ZT=∑h∈π^h(μh,T−D¯h,T),ZS^=0.Z_T= _h π_h( _h,T- D_h,T), Z_ S=0. (9) The symbols Δ^T _T and ZTZ_T will not be confused: the former is observable, while the latter contains unknown conditional means and is used only in the analysis. Table 1: Main notation. All candidate-dependent objects may be random through pre-audit pilot information. Symbol Meaning ℋB,,S^,S⋆H_B,C, S,S feasible, retained, selected, optimal document sets hS,F(S),RB(S)h_S,F(S),R_B(S) query coverage, mean coverage, population regret DT,ΔTD_T, _T contrast against S S and its population mean H,πh,π^h,PhH, _h, π_h,P_h number, true/estimated weights, conditional query law nh,D¯h,T,μh,Tn_h, D_h,T, _h,T audited count, sample/conditional contrast means ZTZ_T weighted, centered audit error ℓ,Πℓ,ℰℓN_ , _ ,E_ networks, parent maps, distinct comparison edges d2,d∞d_2,d_∞ conditional variance and range semimetrics v¯e,b¯e v_e, b_e valid observable variance/range upper bounds αs,αa,αv,απ,αg _s, _a, _v, _π, _g error budgets for screening, audit, variance, weights, means αB,αv′,αact,αrep _B, _v , _act, _rep budgets for Bennett, its variances, activity, representation 3 A local Bernstein inequality for documentary increments For document selections U,VU,V, let GU,V(q)=hU(q)−hV(q)∈[−1,1].G_U,V(q)=h_U(q)-h_V(q)∈[-1,1]. (10) We identify the directed edge e=(U,V)e=(U,V) with Ge=GU,VG_e=G_U,V. For h∈h , denote vh,e=Var(Ge(Q)∣X=h),osch(Ge)=esssupPhGe−essinfPhGe.v_h,e=Var(G_e(Q) X=h), _h(G_e)= ess\,sup_P_hG_e- ess\,inf_P_hG_e. The latter is an essential range, hence is at most 22, while 0≤vh,e≤10≤ v_h,e≤ 1. Condition on ℱ0 F_0, the unlabelled observations and the counts, so that all π^h π_h, nhn_h and pre-audit edges are fixed. Define d22(e) d_2^2(e) =∑hπ^h2nhvh,e, = _h π_h^2n_hv_h,e, (11) d∞(e) d_∞(e) =maxhπ^hnhosch(Ge). = _h π_hn_hosc_h(G_e). (12) These are semimetrics on coverage profiles (they may vanish for distinct selections). For clarity, the square in d22d_2^2 is part of the notation. Lemma 1 (Conditional Bernstein increment). Under Assumption 2, for every pre-audit edge e=(U,V)e=(U,V) and every t>0t>0, conditional on the pre-audit information and counts, ℙZU−ZV>2d22(e)t+13d∞(e)t|pre-audit information, counts≤e−t.P \Z_U-Z_V> 2d_2^2(e)t+ 13d_∞(e)t\ |\ pre-audit information, counts \≤ e^-t. (13) No assumption of independence across different edges is needed. Proof. Since DU−DV=GU,VD_U-D_V=G_U,V, we have ZU−ZV=∑h∈∑i=1nhπ^hnh(hGe−Ge(Qh,i)).Z_U-Z_V= _h _i=1^n_h π_hn_h (E_hG_e-G_e(Q_h,i) ). The summands are conditionally independent and centered. Their total conditional variance equals d22(e)d_2^2(e). Since hGeE_hG_e lies in the essential range of GeG_e under PhP_h, each centered summand is almost surely at most (π^h/nh)osch(Ge)≤d∞(e)( π_h/n_h)osc_h(G_e)≤ d_∞(e). By Theorem 2.10 of Boucheron et al. (2013), if X1,…,XnX_1,…,X_n are independent, ∑iXi2≤v _iEX_i^2≤ v and ∑i[(Xi)+q]≤q!vcq−2/2 _iE[(X_i)_+^q]≤ q!\,v\,c^q-2/2 for all integers q≥3q≥ 3, then ℙ∑i(Xi−Xi)≥2vt+ct≤e−tP\ _i(X_i-EX_i)≥ 2vt+ct\≤ e^-t for all t>0t>0. As noted in Boucheron et al. (2013, p. 38), right after their Corollary 2.11, variables with Xi≤bX_i≤ b almost surely satisfy these conditions with v=∑iXi2v= _iEX_i^2 and c=b/3c=b/3. Apply this to the centered summands above, for which ∑iXi2=d22(e) _iEX_i^2=d_2^2(e) and b=d∞(e)b=d_∞(e); this gives (13). If d∞(e)=0d_∞(e)=0 or d22(e)=0d_2^2(e)=0, the summands vanish almost surely and the claim is trivial. ∎ Remark 1 (On the linear constant). The classical tail form ℙZU−ZV≥u≤exp−u2/(2[d22(e)+d∞(e)u/3]),P\Z_U-Z_V≥ u\≤ \-u^2/ (2[d_2^2(e)+d_∞(e)u/3] ) \, inequality (2.10) of Boucheron et al. (2013), is usually inverted to the weaker radius 2d22(e)t+23d∞(e)t 2d_2^2(e)t+ 23d_∞(e)t. The constant 13 13 in (13) comes from the sub-gamma form cited above; it is the same constant that appears in Bennett’s inequality as stated in Maurer and Pontil (2009, Theorem 3). It is used throughout. Remark 2 (Why the essential range still matters). Low variance alone does not eliminate the Bernstein linear term. A profile may disagree with another only on rare queries, yet a rare observation can produce a large jump. A deterministic envelope, an externally certified uniform approximation, or an explicitly valid bound on osch(Ge)osc_h(G_e) is needed to shrink the linear term; numerical proximity of embeddings is not such a certificate. 4 A simultaneous localized multiscale inequality Definition 1 (Pre-audit comparison network). Given C and S S, fix an integer L≥1L≥ 1, finite nonempty sets of document selections 0,…,L⊆N_0,…,N_L and mappings Πℓ:→ℓ _ :C _ such that 0=S^,Π0(T)=S^,ΠL(T)=Tfor every T∈.N_0=\ S\, _0(T)= S, _L(T)=T every T . (14) The network sets and maps must be measurable with respect to the pre-audit information (which may include independent unlabelled queries). Define eℓ(T)=(Πℓ(T),Πℓ−1(T))e_ (T)=( _ (T), _ -1(T)) and let ℰℓ=eℓ(T):T∈,Πℓ(T)≠Πℓ−1(T),ℰ=⋃ℓ=1Lℰℓ.E_ =\e_ (T):T ,\ _ (T)≠ _ -1(T)\, = _ =1^LE_ . (15) Here the sets count distinct directed edges, not paths: within a level, an edge shared by many candidates is counted once. An edge that appears at several levels is counted in each corresponding ℰℓE_ , because the union bound in Theorem 1 is allocated level by level; Proposition 3 below avoids this repeated charge by a single union bound over distinct edges. For convenience levels with ℰℓ=∅E_ = can be removed. We assume the displayed levels are nonempty. The identity ZS^=0Z_ S=0 gives the exact telescoping representation ZT=∑ℓ=1L[ZΠℓ(T)−ZΠℓ−1(T)].Z_T= _ =1^L [Z_ _ (T)-Z_ _ -1(T) ]. (16) No probabilistic approximation is involved in this equality. Theorem 1 (Conditional simultaneous multiscale Bernstein bound). Assume the model of Section 2. Choose numbers α1,…,αL>0 _1,…, _L>0 with ∑ℓ=1Lαℓ=αa<1 _ =1^L _ = _a<1 and let tℓ=log|ℰℓ|αℓ.t_ = |E_ | _ . (17) Suppose that for all distinct edges e∈ℰe there are nonnegative, possibly audit-data-dependent random variables v¯e,b¯e v_e, b_e such that ℙ∀e∈ℰ:d22(e)≤v¯e,d∞(e)≤b¯e|pre-audit information, counts≥1−αv.P \∀ e :\;d_2^2(e)≤ v_e, d_∞(e)≤ b_e\ |\ pre-audit information, counts \≥ 1- _v. (18) Define the path-dependent radius ℜ(T)=∑ℓ=1Leℓ(T)∈ℰℓ2v¯eℓ(T)tℓ+13b¯eℓ(T)tℓ. R(T)= _ =1^L1\e_ (T) _ \ \ 2 v_e_ (T)t_ + 13 b_e_ (T)t_ \. (19) Then, conditionally on the pre-audit information and counts, ℙ∀T∈:ZT≤ℜ(T)|pre-audit information, counts≥1−αa−αv.P \∀ T :\ Z_T≤ R(T)\ |\ pre-audit information, counts \≥ 1- _a- _v. (20) The result remains valid when C, S S, and the network are arbitrarily data-dependent through the independent pilot and unlabelled information. Proof. For every level ℓ and every e=(U,V)∈ℰℓe=(U,V) _ , apply Lemma 1 with t=tℓt=t_ . Its one-sided failure probability is bounded by e−tℓ=αℓ/|ℰℓ|e^-t_ = _ /|E_ |. A union bound over the distinct edges in ℰℓE_ gives failure probability at most αℓ _ ; a second union bound over levels gives a joint event Ωa _a of probability at least 1−αa1- _a on which ZU−ZV≤2d22(e)tℓ+13d∞(e)tℓfor every e=(U,V)∈ℰℓ,ℓ=1,…,L.Z_U-Z_V≤ 2d_2^2(e)t_ + 13d_∞(e)t_ every e=(U,V) _ ,\ =1,…,L. On Ωa _a, use the telescoping identity (16) for each T∈T and add the corresponding edge inequalities. Intersect with the calibration event in (18). The monotonicity of the square root and of the linear term permits replacement of each unknown d22(e),d∞(e)d_2^2(e),d_∞(e) by v¯e,b¯e v_e, b_e without any independence assumption between Ωa _a and the calibration event. A final union bound proves (20). Conditioning is legitimate because every edge and its allocated failure probability were fixed without examining audit relevance values. ∎ Proposition 3 (A weighted, unique-edge simultaneous inequality). Let ℰ=⋃ℓ=1LℰℓE= _ =1^LE_ be the set of distinct directed edges of a pre-audit network as in Definition 1, and let 0<αa<10< _a<1. Conditionally on the pre-audit information and counts, choose weights ωe>0 _e>0 satisfying ∑e∈ℰωe≤1 _e _e≤ 1. The weights may depend on the pilot, the unlabelled observations and the counts, but not on audit relevance labels. Put te=log1αaωe,e∈ℰ.t_e= 1 _a _e, e . (21) Suppose that the simultaneous edge calibration event (18) holds with conditional failure probability at most αv _v, and define ℜω(T)=∑ℓ=1Leℓ(T)∈ℰℓ2v¯eℓ(T)teℓ(T)+13b¯eℓ(T)teℓ(T). R_ω(T)= _ =1^L1\e_ (T) _ \ \ 2 v_e_ (T)t_e_ (T)+ 13 b_e_ (T)t_e_ (T) \. (22) Then, conditionally on the pre-audit information and counts, ℙ∀T∈:ZT≤ℜω(T)|pre-audit information, counts≥1−αa−αv.P \∀ T :\ Z_T≤ R_ω(T)\ |\ pre-audit information, counts \≥ 1- _a- _v. The same event bounds all candidate paths, even if a directed edge appears at more than one level. Proof. Since αaωe<1 _a _e<1, each tet_e is positive. For each distinct edge e=(U,V)∈ℰe=(U,V) , apply Lemma 1 at t=tet=t_e. Its conditional failure probability is at most e−te=αaωe^-t_e= _a _e. A single union bound over e∈ℰe therefore has failure probability at most αa∑eωe≤αa _a _e _e≤ _a. On its complement every edge inequality holds, regardless of how many times that edge occurs in the telescoping paths. Intersect with the simultaneous calibration event and sum along each path exactly as in Theorem 1. No independence between these events is needed. ∎ Remark 3 (Uniform levels, repeated edges, and pre-audit tuning). If every edge appears at only one level, the allocation ωe=αℓ/(αa|ℰℓ|) _e= _ /( _a|E_ |) for e∈ℰℓe _ gives te=tℓt_e=t_ and recovers Theorem 1. For repeated edges, let ωe=∑ℓ:e∈ℰℓαℓαa|ℰℓ|. _e= _ :\,e _ _ _a|E_ |. These weights sum to 11, and te≤tℓt_e≤ t_ whenever e∈ℰℓe _ . Consequently, the weighted radius is never larger than the levelwise radius (19) for this allocation, and it can be strictly smaller on paths with repeated edges. Other weights may prioritize difficult or frequently used edges, but they must be fixed without the audit relevance labels: optimizing them retrospectively from the audit is not covered by this proposition. Remark 4 (The role of localization). The radius in (19) is pathwise localized: each T pays only for increments along its own approximation path, and an edge with negligible variance or range contributes little. Moreover, the pilot-screened family C can be much smaller than ℋBH_B. This does not establish a universal entropy integral or a new generic chaining inequality; the generic mixed-tail background is developed, for example, by Dirksen (2015). 5 Observable calibration of all edge variances Theorem 1 must not rely on oracle variances. We now provide explicit, fully observable choices of v¯e v_e with separate statistical error control. Recall the unbiased sample variance sn2(y1,…,yn)=1n−1∑i=1n(yi−y¯)2.s_n^2(y_1,…,y_n)= 1n-1 _i=1^n(y_i- y)^2. Lemma 2 (Empirical Bernstein inequality for a single mean). Let Y1,…,YnY_1,…,Y_n be iid in [a,b][a,b] for n≥2n≥ 2 and let sn2s_n^2 be their unbiased sample variance. For 0<δ<10<δ<1, ℙY−Y¯>2sn2log(2/δ)n+7(b−a)log(2/δ)3(n−1)≤δ.P \EY- Y> 2s_n^2 (2/δ)n+ 7(b-a) (2/δ)3(n-1) \≤δ. (23) The same assertion holds with Y¯−Y Y-EY in place of Y−Y¯EY- Y. Proof. For a<ba<b, apply Theorem 4 of Maurer and Pontil (2009) to the rescaled observations (Yi−a)/(b−a)∈[0,1](Y_i-a)/(b-a)∈[0,1], then multiply the resulting inequality by b−ab-a. The sample variance Vn=n(n−1)−1∑i<j(Zi−Zj)2V_n=\n(n-1)\^-1 _i<j(Z_i-Z_j)^2 used by Maurer and Pontil (2009) coincides with the unbiased sample variance sn2s_n^2, and it rescales by (b−a)2(b-a)^2. Apply the same theorem to (b−Yi)/(b−a)(b-Y_i)/(b-a) for the opposite one-sided deviation. If a=ba=b the deviations vanish identically. ∎ Assumption 3 (Pre-audit residual predictors). For every stratum h and every distinct edge e∈ℰe , there is an ℱ0 F_0- and/or unlabelled-sample-measurable predictor mh,e∈[−1,1]m_h,e∈[-1,1]. It is fixed without using the audit relevance labels. Let Yh,i,e=(Ge(Qh,i)−mh,e)2,Mh,e=(1+|mh,e|)2,Y¯h,e=1nh∑iYh,i,e,Y_h,i,e= (G_e(Q_h,i)-m_h,e )^2, M_h,e=(1+|m_h,e|)^2, Y_h,e= 1n_h _iY_h,i,e, (24) and write sY,h,e2s_Y,h,e^2 for the sample variance of the Y’s. Since Ge∈[−1,1]G_e∈[-1,1], 0≤Yh,i,e≤Mh,e≤40≤ Y_h,i,e≤ M_h,e≤ 4. Lemma 3 (Uniform residual-second-moment upper bounds). Let E=|ℰ|≥1E=|E|≥ 1. Set tv=log2HEαv,vh,e+=min1,Y¯h,e+2sY,h,e2tvnh+7Mh,etv3(nh−1).t_v= 2HE _v, v^+_h,e= \1,\ Y_h,e+ 2s_Y,h,e^2t_vn_h+ 7M_h,et_v3(n_h-1) \. Under Assumptions 2 and 3, ℙ∀h,e:vh,e≤vh,e+|pre-audit information, counts≥1−αv.P \∀ h,e: v_h,e≤ v^+_h,e\ |\ pre-audit information, counts \≥ 1- _v. (25) Proof. For each fixed h,eh,e, the bias–variance decomposition gives h(Ge−mh,e)2=Varh(Ge)+(hGe−mh,e)2≥vh,e.E_h(G_e-m_h,e)^2=Var_h(G_e)+(E_hG_e-m_h,e)^2≥ v_h,e. The predictor is fixed under the conditioning, so the residual squares are iid and bounded by Mh,eM_h,e. Apply the one-sided empirical Bernstein inequality of Lemma 2 (equivalently, Corollary 5 of Maurer and Pontil (2009) after rescaling) with δ=αv/(HE)δ= _v/(HE). Since log(2/δ)=tv (2/δ)=t_v, the displayed empirical upper expression bounds hYh,i,eE_hY_h,i,e except on an event of probability at most αv/(HE) _v/(HE). Union over all HEHE pairs. Finally, the separate Popoviciu bound vh,e≤(2)2/4=1v_h,e≤(2)^2/4=1 justifies the minimum with 11. ∎ Theorem 2 (Observable simultaneous chaining radius). Under Assumptions 2 and 3, let b¯h,e∈[0,2] b_h,e∈[0,2] be known pre-audit constants satisfying osch(Ge)≤b¯h,eosc_h(G_e)≤ b_h,e. The universally valid choice is b¯h,e=2 b_h,e=2. Put v¯e=∑hπ^h2nhvh,e+,b¯e=maxhπ^hnhb¯h,e. v_e= _h π_h^2n_hv^+_h,e, b_e= _h π_hn_h b_h,e. (26) Then the radius (19) is observable from the pilot, unlabelled sample and acquired audit labels, and conclusion (20) holds with probability at least 1−αa−αv1- _a- _v. Proof. By Lemma 3, the collection of variance bounds in (26) dominates d22(e)d_2^2(e) simultaneously with conditional probability at least 1−αv1- _v. The deterministic oscillation bounds imply d∞(e)≤b¯ed_∞(e)≤ b_e without additional probability loss. All requirements of Theorem 1 are satisfied. ∎ Remark 5 (No hidden additional labeled sample). The vh,e+v^+_h,e may be estimated on the same audited labels used to form D¯h,T D_h,T. The argument does not condition on the estimated variances; instead it intersects a Bernstein event involving the true variances with an empirical calibration event that holds simultaneously. This avoids an incorrect independence claim and does not double the annotation budget. Remark 6 (A predictor-free alternative). Assumption 3 can be dropped at the price of a different constant. For iid observations in [a,b][a,b], inequality (3) in Theorem 10 of Maurer and Pontil (2009), applied after rescaling to [0,1][0,1], gives ℙσ>sn+(b−a)2log(1/δ)/(n−1)≤δ,P \σ>s_n+(b-a) 2 (1/δ)/(n-1) \≤δ, where σ2σ^2 is the variance and sns_n the unbiased sample standard deviation. (Their theorem is stated for Vn EV_n; in the iid case the expected unbiased sample variance VnEV_n equals σ2σ^2.) With Ge∈[−1,1]G_e∈[-1,1] and δ=αv/(HE)δ= _v/(HE), the choice vh,e+=min1,(sh,e+22log(HE/αv)/(nh−1))2,v^+_h,e= \1, (s_h,e+2 2 (HE/ _v)/(n_h-1) )^2 \, where sh,es_h,e is the sample standard deviation of the Ge(Qh,i)G_e(Q_h,i), satisfies (25) without any pre-audit predictor. Both forms have the same orders in nhn_h, namely terms of order nh−1/2n_h^-1/2 scaled by an empirical standard deviation and terms of order nh−1n_h^-1. They differ in their constants and in the squared bias (hGe−mh,e)2(E_hG_e-m_h,e)^2, which the residual form pays and the predictor-free form avoids; which one is tighter depends on the data and on the quality of the predictor. Theorem 3 (One-stage empirical-Bernstein multiscale certificate). Assume the stratified, label-ignorable audit design (Assumption 2) and a pre-audit network as in Definition 1. For every h and every distinct directed edge e∈ℰe , let G¯h,e=nh−1∑i=1nhGe(Qh,i) G_h,e=n_h^-1 _i=1^n_hG_e(Q_h,i), and let sh,e2s_h,e^2 be the unbiased sample variance of Ge(Qh,1),…,Ge(Qh,nh)G_e(Q_h,1),…,G_e(Q_h,n_h). Let b¯h,e∈[0,2] b_h,e∈[0,2] be the known pre-audit constants of Theorem 2, satisfying osch(Ge)≤b¯h,eosc_h(G_e)≤ b_h,e. For ∑ℓαℓ=αa<1 _ _ = _a<1 set tℓEB=log2H|ℰℓ|αℓt_ ^EB= 2H|E_ | _ (27) and define ℜEB(T)=∑ℓ=1Leℓ(T)∈ℰℓ∑h∈π^h2sh,eℓ(T)2tℓEBnh+7b¯h,eℓ(T)tℓEB3(nh−1). R_EB(T)= _ =1^L1\e_ (T) _ \ _h π_h \ 2s_h,e_ (T)^2t_ ^EBn_h+ 7 b_h,e_ (T)t_ ^EB3(n_h-1) \. (28) Then, conditionally on the pre-audit information and counts, ℙ∀T∈:ZT≤ℜEB(T)|pre-audit information, counts≥1−αa.P \∀ T :\ Z_T≤ R_EB(T)\ |\ pre-audit information, counts \≥ 1- _a. (29) In particular, this certificate requires neither pre-audit residual predictors (Assumption 3) nor the separate calibration budget αv _v. Proof. Condition on the pre-audit information and counts, so that the π^h π_h are fixed and, for each h and e, the values Ge(Qh,i)G_e(Q_h,i) are iid. They lie almost surely in the interval between the essential infimum and supremum of GeG_e under PhP_h, whose length is osch(Ge)≤b¯h,eosc_h(G_e)≤ b_h,e. The endpoints need not be known, since the bound of Lemma 2 depends on the interval only through its length and is nondecreasing in it. For each level ℓ , edge e∈ℰℓe _ and stratum h, apply Lemma 2 with δ=αℓ/(H|ℰℓ|)δ= _ /(H|E_ |), so that log(2/δ)=tℓEB (2/δ)=t_ ^EB. This yields hGe−G¯h,e≤2sh,e2tℓEBnh+7b¯h,etℓEB3(nh−1)E_hG_e- G_h,e≤ 2s_h,e^2t_ ^EBn_h+ 7 b_h,et_ ^EB3(n_h-1) outside an event whose conditional probability does not exceed αℓ/(H|ℰℓ|) _ /(H|E_ |). A union bound over the H|ℰℓ|H|E_ | stratum–edge pairs at level ℓ , and then over levels, gives a single event with probability at least 1−αa1- _a. For e=(U,V)e=(U,V) we have ZU−ZV=∑hπ^h(hGe−G¯h,e).Z_U-Z_V= _h π_h(E_hG_e- G_h,e). On the event just described, multiply each stratum-specific bound by π^h≥0 π_h≥ 0, sum over strata, and telescope along every candidate path as in (16). The result is (29). ∎ Remark 7 (No unconditional dominance). The single-stage radius (28) dispenses with αv _v, but it sums stratumwise deviations and pays the larger empirical-Bernstein linear constant 7/37/3. The calibrated Bernstein radius of Theorem 2 instead pools the variances before applying the square root, but it pays the predictor bias and the split of αv _v. Neither is uniformly smaller. Both should be computed as baselines under comparable confidence and annotation budgets. If the final reported certificate is selected as the minimum of two post-audit certificates, their failure probabilities must first be jointly budgeted (or the choice between them must have been fixed without audit labels); taking their minimum at their individual nominal failure levels does not generally preserve those levels. 6 Unknown stratum probabilities and certified regret Fix stratum 00 as a reference and write, for any T∈T , ΔT−Δ^T _T- _T =ZT+∑h(πh−π^h)μh,T =Z_T+ _h( _h- π_h) _h,T =ZT+∑h=1H−1(πh−π^h)(μh,T−μ0,T). =Z_T+ _h=1^H-1( _h- π_h)( _h,T- _0,T). (30) The second identity exploits ∑h(πh−π^h)=0 _h( _h- π_h)=0 and is useful: the cost of estimating the population weights is small when the contrasts, not necessarily the coverage levels, are similar between strata. Let J=||−1J=|C|-1 be the number of nontrivial competitors, and suppose J≥1J≥ 1 (the case J=0J=0 is handled below). Let eπ=log(2(H−1)/απ)2Nu.e_π= (2(H-1)/ _π)2N_u. (31) For each h,Th,T denote by sh,T2s_h,T^2 the sample variance of the DT(Qh,i)D_T(Q_h,i), and define tg=log4HJαg,rh,T=2sh,T2tgnh+14tg3(nh−1),t_g= 4HJ _g, r_h,T= 2s_h,T^2t_gn_h+ 14t_g3(n_h-1), (32) and, for h=1,…,H−1h=1,…,H-1, the observable factor ρh,T=min2,|D¯h,T−D¯0,T|+rh,T+r0,T. _h,T= \2,\ | D_h,T- D_0,T|+r_h,T+r_0,T \. (33) The level tg=log(4HJ/αg)t_g= (4HJ/ _g) is calibrated exactly: each of the 2HJ2HJ one-sided statements used below is applied with δ=αg/(2HJ)δ= _g/(2HJ), so that log(2/δ)=tg (2/δ)=t_g. No independence between these events and the chaining event is assumed. For T=S^T= S one has μh,S^=D¯h,S^=0 _h, S= D_h, S=0 deterministically, so no probability is spent on S S. Lemma 4 (Uncertainty in unknown context proportions). Under Assumptions 1 and 2, with probability at least 1−απ−αg1- _π- _g, simultaneously for all T∈T , |∑h(πh−π^h)μh,T|≤eπ∑h=1H−1ρh,T. | _h( _h- π_h) _h,T |≤ e_π _h=1^H-1 _h,T. (34) Proof. For each h=1,…,H−1h=1,…,H-1, Hoeffding’s inequality, applied to the Bernoulli indicators ϕ(Qi(u))=h1\φ(Q_i^(u))=h\, gives ℙ|π^h−πh|>eπ≤2exp(−2Nueπ2)=απ/(H−1).P\| π_h- _h|>e_π\≤ 2 (-2N_ue_π^2)= _π/(H-1). Union over the H−1H-1 nonreference strata yields the simultaneous proportion event with probability at least 1−απ1- _π. Every DTD_T takes values in [−1,1][-1,1]. Apply Lemma 2 in both directions, with range 22 and δ=αg/(2HJ)δ= _g/(2HJ) for each tail, and take a union bound over the 2HJ2HJ one-sided statements for the J nontrivial competitors. This gives |μh,T−D¯h,T|≤rh,T| _h,T- D_h,T|≤ r_h,T for every h and every T∈∖S^T \ S\, except with probability at most αg _g; for T=S^T= S the inequality is trivial. Now use (30), bound |πh−π^h|≤eπ| _h- π_h|≤ e_π, and insert |μh,T−μ0,T|≤min2,|D¯h,T−D¯0,T|+rh,T+r0,T=ρh,T,| _h,T- _0,T|≤ \2,\ | D_h,T- D_0,T|+r_h,T+r_0,T \= _h,T, where the bound 22 holds deterministically because μh,T∈[−1,1] _h,T∈[-1,1]. Intersection of the two events and a union bound prove the assertion. ∎ Remark 8 (Where the cardinality of C re-enters). Because ρh,T≤2 _h,T≤ 2, the weight correction never exceeds 2(H−1)eπ2(H-1)e_π. This crude level holds on the proportion event alone, does not depend on |||C|, and requires no mean intervals: if one sets ρh,T≡2 _h,T≡ 2, Lemma 4 holds with probability at least 1−απ1- _π and αg=0 _g=0 may be used in Theorem 4. The empirical refinement through rh,Tr_h,T, in contrast, relies on a flat union bound over the J competitors, so a factor logJ J re-enters the certificate through tgt_g, multiplied by eπe_π. The localization of Theorem 1 therefore concerns the audit fluctuation ZTZ_T; the weight-estimation term is controlled only through the factor eπe_π, of order Nu−1/2N_u^-1/2, which is small when the unlabelled sample is large. Define for every T∈∖S^T \ S\ UT=Δ^T+ℜ(T)+eπ∑h=1H−1ρh,T,U_T= _T+ R(T)+e_π _h=1^H-1 _h,T, (35) and set US^:=0U_ S:=0. The latter convention does not follow from (35), whose terms need not vanish at T=S^T= S (the path of S S in the network may pass through other nodes, and ρh,S^>0 _h, S>0); it is legitimate because ΔS^=0 _ S=0 deterministically, so no confidence statement is required for S S. Let R¯red=min1,max0,maxT∈UT. R_red= \1,\ \0, _T U_T \ \. (36) Theorem 4 (Honest postselection regret certificate). Let Assumptions 1, 2, and 3 hold. Suppose the pilot screening event (5) has probability at least 1−αs1- _s. Construct the pre-audit networks as in Definition 1, use the observable edge radius from Theorem 2, and form (35)–(36). If αs+αa+αv+απ+αg≤α<1, _s+ _a+ _v+ _π+ _g≤α<1, then ℙRB(S^)≤R¯red≥1−α.\ P\R_B( S)≤ R_red\≥ 1-α.\ (37) If =S^C=\ S\, define R¯red=0 R_red=0; the statement remains valid. The distribution P and the proportions πh _h need not be known or parametrically specified. Proof. By Theorem 2 and Lemma 4, with probability at least 1−αa−αv−απ−αg1- _a- _v- _π- _g, we have for every T∈∖S^T \ S\, ΔT=Δ^T+ZT+∑h(πh−π^h)μh,T≤UT, _T= _T+Z_T+ _h( _h- π_h) _h,T≤ U_T, while ΔS^=0=US _ S=0=U_ S holds deterministically. This simultaneous event is valid even though S^, S,C and the network were learned from the pilot, since the relevant concentration statements hold conditionally on the pre-audit information and counts. On the screening event, some population maximizer S⋆∈S . Consequently, RB(S^)=F(S⋆)−F(S^)=ΔS⋆≤US⋆≤maxT∈UT.R_B( S)=F(S )-F( S)= _S ≤ U_S ≤ _T U_T. Because 0≤RB(S^)≤10≤ R_B( S)≤ 1, truncation at 00 and 11 is harmless. The union bound with the screening failure probability proves the result. If =S^C=\ S\, the screening event implies that S S itself is optimal, hence its regret is zero; off the screening event no assertion is made. ∎ Corollary 1 (Postselection certification without variance calibration). Let Assumptions 1 and 2 hold, let the pilot screening event (5) has probability at least 1−αs1- _s, and let the pre-audit networks be constructed as in Definition 1. For T∈∖S^T \ S\ put UTEB=Δ^T+ℜEB(T)+eπ∑h=1H−1ρh,T,U_T^EB= _T+ R_EB(T)+e_π _h=1^H-1 _h,T, with ℜEB R_EB from (28), and set US^EB:=0U_ S^EB:=0, which is legitimate because ΔS^=0 _ S=0. Define R¯EB=min1,max(0,maxT∈UTEB) R_EB= \1, (0, _T U_T^EB)\, with the same singleton convention as in Theorem 4. If αs+αa+απ+αg≤α<1 _s+ _a+ _π+ _g≤α<1, then ℙRB(S^)≤R¯EB≥1−α.P\R_B( S)≤ R_EB\≥ 1-α. No assumption on pre-audit residual predictors is needed. Proof. Intersect the simultaneous event of Theorem 3 with the proportion and mean calibration events of Lemma 4, which uses only Assumptions 1 and 2, and with the screening event. On this intersection, identity (30) gives ΔT≤UTEB _T≤ U_T^EB for every T∈T ; then argue over a screened population optimum exactly as in the proof of Theorem 4. The total failure probability is bounded by αs+αa+απ+αg _s+ _a+ _π+ _g. ∎ Corollary 2 (Reduced universe versus original corpus). Suppose the original corpus contains a larger finite feasible family ℋBfull⊇ℋBH_B^full _B with optimal expected coverage VBfull=maxS∈ℋBfullF(S)V_B^full= _S _B^fullF(S). If, with probability at least 1−αrep1- _rep, 0≤VBfull−maxS∈ℋBF(S)≤ρ¯rep,0≤ V_B^full- _S _BF(S)≤ ρ_rep, then ℙVBfull−F(S^)≤ρ¯rep+R¯red≥1−α−αrep.P \V_B^full-F( S)≤ ρ_rep+ R_red \≥ 1-α- _rep. Proof. Decompose VBfull−F(S^)=[VBfull−maxS∈ℋBF(S)]+RB(S^)V_B^full-F( S)=[V_B^full- _S _BF(S)]+R_B( S) and intersect the two coverage events. ∎ Corollary 3 (Uniformly bounded relevance errors). Suppose the audit measures functions r~j:→[0,1] r_j:Q→[0,1] satisfying the deterministic uniform calibration condition supq,j|r~j(q)−rj(q)|≤η _q,j| r_j(q)-r_j(q)|≤η, and all hypotheses of Theorem 4 hold for the induced measured coverages h~S h_S on the same pre-audit family C. Let U~T U_T be their simultaneous contrast bounds and assume the true-population screening event (5) has probability at least 1−αs1- _s (Remark 9 gives a sufficient rule). Then the true reduced regret is bounded by RB(S^)≤min1,max(0,maxT∈U~T+2η)R_B( S)≤ \1, (0, _T U_T+2η)\ with the same joint confidence level as in Theorem 4. Proof. The map (xj)j∈S↦maxj∈Sxj(x_j)_j∈ S _j∈ Sx_j is 1-Lipschitz under the supremum norm. Thus |hS(q)−h~S(q)|≤η|h_S(q)- h_S(q)|≤η for every S and q, so |ΔT−Δ~T|≤2η| _T- _T|≤ 2η for all T. On the simultaneous measured-contrast event and the true screening event, RB(S^)=ΔS⋆≤U~S⋆+2ηR_B( S)= _S ≤ U_S +2η. Truncation to [0,1][0,1] completes the proof. ∎ Remark 9 (Screening with measured pilot labels). Corollary 3 requires the screening event for the true population. If the pilot of Proposition 2 is itself labeled with the measured functions r~j r_j, its uniform Hoeffding event controls |F^0(S)−F~(S)|| F_0(S)- F(S)|, where F~(S)=Ph~S(Q) F(S)=E_P h_S(Q) and |F~(S)−F(S)|≤η| F(S)-F(S)|≤η. On that event, F^0(S⋆)−F^0(S^)+2r0≥F(S⋆)−F(S^)−2η≥−2η F_0(S )- F_0( S)+2r_0≥ F(S )-F( S)-2η≥-2η. Hence the rule (7) must be widened to F^0(T)−F^0(S^)+2r0+2η≥0 F_0(T)- F_0( S)+2r_0+2η≥ 0; with this change the true-population screening event again has probability at least 1−αs1- _s. 7 A complementary pooled stratified Bennett certificate Before using the full multiscale construction, one may combine the conditional stratum fluctuations using a single exponential tilt. The result is included for completeness and as a benchmark, not claimed to be an original concentration inequality. For each candidate T∈T , denote σh,T2=Var(DT(Q)∣X=h)σ^2_h,T=Var(D_T(Q) X=h). In the formulas below take J=||−1≥1J=|C|-1≥ 1. For every h and every T∈∖S^T \ S\, use a pre-audit predictor mh,T∈[−1,1]m_h,T∈[-1,1] satisfying the analogue of Assumption 3, and replace GeG_e by DTD_T in the construction of Lemma 3. The union bound now runs over the HJHJ pairs (h,T)(h,T), so tvt_v is replaced by tv′=log(2HJ/αv′)t_v = (2HJ/ _v ). This gives simultaneous empirical upper bounds vh,T+≥σh,T2v^+_h,T≥σ^2_h,T with failure probability at most αv′ _v . The budget αv′ _v is distinct from the budget αv _v of Lemma 3; both must be paid if both certificates are reported. Set wh=π^h,βh=2whnh,T+(λ)=∑h∈nhvh,T+4(eλβh−1−λβh).w_h= π_h, _h= 2w_hn_h, _T^+(λ)= _h n_hv^+_h,T4 (e^λ _h-1-λ _h ). (38) If wh=0w_h=0, the corresponding summand is defined to be zero. Proposition 4 (Pooled Bennett bound with certified residual moments). Assume the model of Section 2 and let every λT>0 _T>0 be fixed conditionally on the pre-audit information and the audit stratum counts, without using audit relevance values. Then, with probability at least 1−αB−αv′1- _B- _v , simultaneously for all T∈∖S^T \ S\, ZT≤ℬT:=log(J/αB)+T+(λT)λT.Z_T _T:= (J/ _B)+K_T^+( _T) _T. (39) Combining this with Lemma 4 and pilot screening provides an alternative population-regret certificate R¯Ben=min1,max0,maxT∈[Δ^T+ℬT+eπ∑h=1H−1ρh,T], R_Ben= \1, \0, _T [ _T+B_T+e_π _h=1^H-1 _h,T ] \ \, (40) with coverage at least 1−αs−αB−αv′−απ−αg1- _s- _B- _v - _π- _g. The bracket for T=S^T= S is replaced by 00, which is legitimate because ΔS^=0 _ S=0; if J=0J=0, the certificate is zero on the screening event. Proof. Condition on the pilot, the independent unlabelled sample and the stratum counts. For each T, define the centered summands Yh,i,T=whnh(μh,T−DT(Qh,i)).Y_h,i,T= w_hn_h ( _h,T-D_T(Q_h,i) ). Their sum equals ZTZ_T, their variances are (wh/nh)2σh,T2(w_h/n_h)^2σ^2_h,T, and, since μh,T−DT≤2 _h,T-D_T≤ 2, they are almost surely at most βh _h. Bennett’s moment-generating-function bound (Boucheron et al., 2013, Theorem 2.9), applied with n=1n=1 to a single centered random variable Y≤βY≤β (so that Y2EY^2 is its variance v), gives logeλY≤vβ2(eλβ−1−λβ)(β>0,λ>0). ^λ Y≤ vβ^2(e^λβ-1-λβ) (β>0,\ λ>0). Summing conditional cumulant bounds across the independent queries, we obtain log[eλZT∣pre-audit information, counts]≤∑hnhσh,T24(eλβh−1−λβh). [e^λ Z_T -audit information, counts]≤ _h n_hσ^2_h,T4(e^λ _h-1-λ _h). When βh=0 _h=0 the variables vanish, so their contribution is zero. Applying Markov’s inequality with the fixed λT _T to the event ZT>log(J/αB)+∑hnhσh,T24(eλTβh−1−λTβh)λT.Z_T> (J/ _B)+ _h n_hσ^2_h,T4(e _T _h-1- _T _h) _T. The conditional probability is at most αB/J _B/J. A union bound over the J nontrivial competitors yields an event of probability at least 1−αB1- _B on which all those inequalities hold. Intersect this event with the simultaneous residual-moment event of probability at least 1−αv′1- _v , and replace σh,T2σ^2_h,T by vh,T+v^+_h,T using the monotonicity of the exponential cumulant for λT>0 _T>0. This gives (39). The decomposition (30), Lemma 4, and the screening argument used in Theorem 4 complete the proof of (40) and its stated coverage probability. ∎ Remark 10 (Data-dependent exponential tilting). Optimizing λT _T after seeing the audit labels is not justified by Proposition 4: a fixed-λ Markov inequality is not automatically uniform in λ. A grid with an explicitly allocated union bound or a time-uniform mixture construction would be needed for such an optimization. The same caution applies to choosing a multiscale network on the audit labels without additional sample splitting or a uniform complexity argument. 8 Documentary activity and structural contraction The concentration theory above is valid for arbitrary bounded coverage functions. We now exploit the particular maximum structure in (2). For a nonempty set R, write aR(q)=maxg∈Rrg(q),a∅(q)=0.a_R(q)= _g∈ Rr_g(q), a_ (q)=0. Lemma 5 (Single-fragment swap and activity). Let j,k∉Rj,k∉ R, let S=R∪jS=R∪\j\, T=R∪kT=R∪\k\, and suppose supq∈|rj(q)−rk(q)|≤ε _q |r_j(q)-r_k(q)|≤ . Define the activity event Aj,k,R(q)=max(rj(q),rk(q))>aR(q),A_j,k,R(q)=1\ (r_j(q),r_k(q))>a_R(q)\, (41) and ah=ℙAj,k,R(Q)=1∣X=ha_h=P\A_j,k,R(Q)=1 X=h\. Then for every q, |hS(q)−hT(q)|≤εAj,k,R(q),|h_S(q)-h_T(q)|≤ A_j,k,R(q), (42) and, for every stratum h, Var(hS(Q)−hT(Q)∣X=h)≤ε2ah,osch(hS−hT)≤2ε.Var(h_S(Q)-h_T(Q) X=h)≤ ^2a_h, _h(h_S-h_T)≤ 2 . (43) Consequently the edge e=(S,T)e=(S,T) obeys d22(e)≤ε2∑hπ^h2nhah,d∞(e)≤2εmaxhπ^hnh.d_2^2(e)≤ ^2 _h π_h^2n_ha_h, d_∞(e)≤ 2 _h π_hn_h. (44) Proof. For every a≥0a≥ 0, the scalar map u↦max(a,u)u (a,u) is 11-Lipschitz. Therefore |hS(q)−hT(q)|=|max(aR(q),rj(q))−max(aR(q),rk(q))|≤|rj(q)−rk(q)|≤ε.|h_S(q)-h_T(q)|=| (a_R(q),r_j(q))- (a_R(q),r_k(q))|≤|r_j(q)-r_k(q)|≤ . When Aj,k,R(q)=0A_j,k,R(q)=0, both rj(q)r_j(q) and rk(q)r_k(q) are at most aR(q)a_R(q), and the two coverages are identical. Combining the observations proves (42). Squaring and taking conditional expectations gives Varh(hS−hT)≤h(hS−hT)2≤ε2hAj,k,R=ε2ah.Var_h(h_S-h_T) _h(h_S-h_T)^2≤ ^2E_hA_j,k,R= ^2a_h. The range inequality follows because the difference is in [−ε,ε][- , ]. Substitute these bounds into (11)–(12) to obtain (44). ∎ Proposition 5 (Rare-query obstruction to sample-only uniform envelopes). For every finite pilot size n0≥1n_0≥ 1 and every δ∈(0,1)δ∈(0,1), there exist a two-point query distribution and two relevance functions with values in [0,1][0,1] such that, with probability exceeding 1−δ1-δ, the pilot observes identical relevance scores for both fragments on all n0n_0 queries, although supq|rj(q)−rk(q)|=1 _q|r_j(q)-r_k(q)|=1. Consequently, an empirical supremum of observed relevance differences, without additional structural assumptions, is not a valid distribution-free upper confidence bound for the population uniform envelope. Proof. Let =0,1Q=\0,1\ with P(Q=1)=θ>0P(Q=1)=θ>0. Set rj(0)=rk(0)=0r_j(0)=r_k(0)=0, rj(1)=1r_j(1)=1, and rk(1)=0r_k(1)=0. The true uniform difference equals 11. Yet with probability (1−θ)n0(1-θ)^n_0 the entire iid pilot consists of queries equal to 00, on which the scores agree exactly. Choosing 0<θ<1−(1−δ)1/n00<θ<1-(1-δ)^1/n_0 makes this probability greater than 1−δ1-δ. Thus a pilot-only empirical supremum of zero is compatible with a population uniform difference of one, and it covers the true envelope with probability less than δ. More generally, any procedure whose output on this all-zero pilot sample is some value c<1c<1 covers the true envelope 11 with probability at most 1−(1−θ)n0<δ1-(1-θ)^n_0<δ under this distribution. ∎ Proposition 6 (Simultaneously estimated activity factors). Let W be a finite set of pre-audit swap triples (j,k,R)(j,k,R) with known deterministic envelopes εj,k,R _j,k,R as in Lemma 5, and let W=||≥1W=|W|≥ 1. Assume that, for every acquired audit query Qh,iQ_h,i and every w=(j,k,R)∈w=(j,k,R) , the relevance values rj(Qh,i)r_j(Q_h,i), rk(Qh,i)r_k(Q_h,i) and rg(Qh,i)r_g(Q_h,i), g∈Rg∈ R, are observed, so that the indicators Aw(Qh,i)A_w(Q_h,i) are observed. This does not follow from Assumption 2, which guarantees only the coverages hT(Qh,i)h_T(Q_h,i), T∈T : these determine neither AwA_w when hS=hTh_S=h_T, nor any quantity involving fragments outside the retained competitor family. For each h and triple w, define a^h,w=nh−1∑iAw(Qh,i) a_h,w=n_h^-1 _iA_w(Q_h,i) and ah,w+=min1,a^h,w+log(HW/αact)2nh.a^+_h,w= \1, a_h,w+ (HW/ _act)2n_h \. Then with probability at least 1−αact1- _act, simultaneously for all h,wh,w, ah,w≤ah,w+a_h,w≤ a^+_h,w. In particular, v¯(S,T)act=εj,k,R2∑hπ^h2nhah,w+ v_(S,T)^act= _j,k,R^2 _h π_h^2n_ha^+_h,w is a simultaneous variance bound for all such swap edges. It can be combined by taking the minimum with the residual bound (26), at the additional error cost αact _act. Proof. For each h,wh,w, the random variables Aw(Qh,i)A_w(Q_h,i) are iid Bernoulli with conditional mean ah,wa_h,w. The one-sided Hoeffding inequality gives failure probability at most αact/(HW) _act/(HW) for the displayed upper bound. Union over all HWHW pairs, followed by Lemma 5, proves the variance assertion. To take the minimum with the residual upper bounds, intersect their two simultaneous validity events and use another union bound. ∎ Proposition 7 (Pathwise extension to several swaps). Suppose two selections S,TS,T can be connected by a finite path S=S0,S1,…,Sm=TS=S_0,S_1,…,S_m=T in which each consecutive pair differs by a single fragment swap covered by Lemma 5, with parameters εk,ah,k _k,a_h,k. Then for each h, [(hS−hT)2∣X=h]≤∑k=1mεkah,k. E[(h_S-h_T)^2 X=h]≤ _k=1^m _k a_h,k. (45) In particular, Var(hS−hT∣X=h)≤(∑k=1mεkah,k)2.Var(h_S-h_T X=h)≤ ( _k=1^m _k a_h,k )^2. Proof. Pointwise, hS−hT=∑k=1m(hSk−1−hSk).h_S-h_T= _k=1^m(h_S_k-1-h_S_k). Apply Minkowski’s inequality in L2(Ph)L_2(P_h), then Lemma 5 to each summand. Variance is at most the uncentered second moment. ∎ 9 A two-level sufficient condition for a sharper bound The multiscale construction is not automatically better than a direct union bound, because it splits the error probability across levels. Here is a sufficient condition for improvement. In this section condition on the pre-audit information and counts, and consider only the audit fluctuation ZTZ_T, not the common error from estimating population stratum proportions. Corollary 4 (Two-level improvement over a flat Bernstein union bound). Suppose the J=||−1≥2J=|C|-1≥ 2 nontrivial competitors admit K0K_0 distinct representatives, 1≤K0<J1≤ K_0<J, and a map c:∖S^→1,…,K0c:C \ S\→\1,…,K_0\ such that every candidate T≠S^T≠ S is associated with a representative Vc(T)V_c(T) and supq∈|hT(q)−hVc(T)(q)|≤ε,0≤ε≤1. _q |h_T(q)-h_V_c(T)(q)|≤ , 0≤ ≤ 1. (46) Assume each representative belongs to C, and use the two-level network S^→Vc(T)→T S→ V_c(T)→ T for T≠S^T≠ S, while the selected set follows the constant path S^→S^→S S→ S→ S. The first-level network includes S S and all representatives. Define qn=∑hπ^h2nh,bn=2maxhπ^hnh,Ln(t)=2qnt+13bnt.q_n= _h π_h^2n_h, b_n=2 _h π_hn_h, L_n(t)= 2q_nt+ 13b_nt. (47) For α1+α2=αa _1+ _2= _a, the uniform two-level radius is Cchain=Ln(logK0α1)+εLn(logJα2).C_chain=L_n ( K_0 _1 )+ L_n ( J _2 ). (48) The flat cardinality-based direct Bernstein radius is Cflat=Ln(logJαa).C_flat=L_n ( J _a ). (49) Whenever 0≤ε<Ln(log(J/αa))−Ln(log(K0/α1))Ln(log(J/α2)),0≤ < L_n( (J/ _a))-L_n( (K_0/ _1))L_n( (J/ _2)), (50) with positive numerator, one has Cchain<CflatC_chain<C_flat. Both bounds apply simultaneously to all candidates with conditional failure probability at most αa _a. Proof. For a coarse edge S^→Vk S→ V_k, its coverage difference lies in [−1,1][-1,1], so its variance is at most 11 and its range at most 22 in each stratum. Lemma 1 therefore bounds the coarse fluctuation by Ln(log(K0/α1))L_n( (K_0/ _1)) simultaneously over the K0K_0 distinct edges. For a fine edge Vc(T)→TV_c(T)→ T, (46) implies that the difference is in [−ε,ε][- , ], with variance at most ε2 ^2 and range at most 2ε2 in every stratum. Its Bernstein radius is therefore at most εLn(log(J/α2)) L_n( (J/ _2)), simultaneously over at most J fine edges (at most J−K0J-K_0 when the representatives are themselves nontrivial competitors, since their fine edges are trivial; the cruder count J is kept for simplicity). The telescoping identity yields (48). Because all variance and range bounds used here are deterministic, no calibration budget αv _v is needed. Direct union over the J edges from S S to each candidate yields (49). Subtracting the two deterministic expressions, and dividing by the strictly positive term Ln(log(J/α2))L_n( (J/ _2)), gives the sufficient condition (50). ∎ Remark 11 (Precise scope of the comparison). Corollary 4 compares two conservative Bernstein radii built from variance and range bounds, under common nominal confidence and the same audit design. Numerical illustration (exact arithmetic on the formulas). Take J=5000J=5000, K0=5K_0=5, H=2H=2, an audit count of nh=500n_h=500 in each of the two strata, and π^0=π^1=1/2 π_0= π_1=1/2. Choose αa=0.05 _a=0.05, α1=α2=0.025 _1= _2=0.025, and ε=0.05 =0.05. Then qn=0.001q_n=0.001 and bn=0.002b_n=0.002, so Cflat≈0.15942,Cchain≈0.11469,Cflat−CchainCflat≈0.2806.C_flat≈ 0.15942, C_chain≈ 0.11469, C_flat-C_chainC_flat≈ 0.2806. (51) The threshold on ε in (50) is about 0.32210.3221. This is a deterministic illustration of the algebraic sufficient condition, not a simulation and not an experimentally measured gain in total documentary regret. 10 Simulation study This section examines three questions: whether the certificates attain their nominal level in finite samples; how the observable radii of Sections 4–7 compare in size; and when the two-level network of Corollary 4 improves on a flat union bound. 10.1 Design Query population and fragments. There are H=3H=3 observable strata, with probabilities π=(0.5,0.3,0.2)π=(0.5,0.3,0.2). Given X=hX=h, a latent topic Z∈1,…,6Z∈\1,…,6\ is drawn with probabilities θh _h, θ0 _0 =(.35,.25,.15,.10,.10,.05), =(.35,.25,.15,.10,.10,.05), θ1 _1 =(.05,.10,.15,.20,.20,.30), =(.05,.10,.15,.20,.20,.30), θ2 _2 =(.10,.15,.30,.25,.10,.10). =(.10,.15,.30,.25,.10,.10). Each topic c has a base relevance r~c(q)=0.75 1Z=c+0.25Wc r_c(q)=0.75\,1\Z=c\+0.25\,W_c, with Wc∼Beta(1,3)W_c (1,3) independent. The corpus has K=30K=30 fragments organized in six clusters of five. The first fragment of cluster c has relevance r~c r_c; each other fragment j of the cluster has rj=min1,max0,r~c+εUjr_j= \1, \0, r_c+ U_j\\, with Uj∼U[−1,1]U_j [-1,1] independent. Hence |rj−r~c|≤ε|r_j- r_c|≤ deterministically: ε controls the functional redundancy within clusters, and ε=0 =0 gives exact duplicates. Selection, competitors and samples. All costs equal 11 and B=3B=3, so ℋBH_B consists of the 45264526 subsets of size at most 33. We take =ℋBC=H_B, so that αs=0 _s=0 and J=4525J=4525. In each replication, a fully labelled pilot of n0=1000n_0=1000 iid queries selects S S by exhaustive maximization of F^0 F_0, supplies the residual predictors mh,em_h,e (pilot stratum means of GeG_e) and fixes the Bennett tilts; an independent unlabelled sample of Nu=50 000N_u=50\,000 queries gives π^h π_h; and the audit draws nhn_h queries from each stratum. The population quantities μh,T _h,T, F(T)F(T) and RB(S^)R_B( S) are computed from an independent Monte Carlo sample of 150 000150\,000 queries per stratum, with standard errors below 1.3×10−31.3× 10^-3. Networks. For T∈ℋBT _B let V(T)V(T) be the set of first fragments of the clusters met by T. Then V(T)∈ℋBV(T) _B, and the 11-Lipschitz property of the maximum, used as in the proof of Corollary 3, gives supq|hT(q)−hV(T)(q)|≤ε _q|h_T(q)-h_V(T)(q)|≤ . The two-level network is S^→V(T)→T S→ V(T)→ T, with 4242 coarse and 44834483 fine edges in every replication; the flat network joins every competitor directly to S S. In this design the envelope ε is known by construction; in applications it would have to be certified externally (Proposition 5). Certificates and error budgets. All certificates have total level α=0.05α=0.05. The weight correction of Lemma 4 uses απ=αg=0.005 _π= _g=0.005 and is common to all of them; the remaining 0.040.04 is allocated to the audit fluctuation. We compare seven certificates of the form R¯=min1,max(0,maxTUT) R= \1, (0, _TU_T)\: (i) Hoeffding, flat: a union of one-sided Hoeffding bounds over the HJHJ pairs (h,T)(h,T), which gives ZT≤∑hπ^h 2log(HJ/0.04)/(2nh)1/2Z_T≤ _h π_h\,2\ (HJ/0.04)/(2n_h)\^1/2; (i)–(iv) one-stage empirical Bernstein (Theorem 3, Corollary 1) with αa=0.04 _a=0.04: flat; two-level with α1=α2=0.02 _1= _2=0.02 and the known envelope b¯h,e=2ε b_h,e=2 on fine edges; and two-level with the universal envelope b¯h,e=2 b_h,e=2; (v)–(vi) calibrated Bernstein (Lemma 3, Theorem 2, Theorem 4) with αa=0.03 _a=0.03 and αv=0.01 _v=0.01: flat, and two-level with α1=α2=0.015 _1= _2=0.015. On fine edges, where |Ge|≤ε|G_e|≤ , the residual range is taken as (ε+|mh,e|)2( +|m_h,e|)^2 and the variance bound is truncated at ε2 ^2; both are direct consequences of Lemma 2 and of Popoviciu’s inequality for a variable with range 2ε2 ; (vii) pooled Bennett (Proposition 4) with αB=0.03 _B=0.03 and αv′=0.01 _v =0.01. Each λT _T minimizes, over a fixed grid, the bound (39) in which vh,T+v^+_h,T is replaced by the same residual formula evaluated on the pilot with the known audit counts; thus λT _T uses no audit label. We vary nh∈100,200,400,800,1600n_h∈\100,200,400,800,1600\ at ε=0.05 =0.05, and ε∈0,0.02,0.05,0.1,0.2,0.4 ∈\0,0.02,0.05,0.1,0.2,0.4\ at nh=400n_h=400, with 200200 replications per setting. 10.2 Results Validity. In all 1010 settings and for all seven certificates, the certificate covered the true regret in every replication, and the simultaneous audit event ZT≤radius(T)∀T\Z_T (T)\ ∀ T\ held in every replication. With 200200 replications, the one-sided 95%95\% Clopper–Pearson lower bound for each coverage probability is 0.9850.985. As expected from union bounds with conservative constants, the certificates are valid with room to spare. Table 2: Mean regret certificate R¯ R over 200 replications, ε=0.05 =0.05, as a function of the number nhn_h of audited queries per stratum. Standard errors are below 0.0030.003 in all cells. The last rows give the mean true regret RB(S^)R_B( S) and the mean largest weight-correction term maxTeπ∑h≥1ρh,T _Te_π _h≥ 1 _h,T, common to all certificates. Certificate nh=100n_h=100 nh=200n_h=200 nh=400n_h=400 nh=800n_h=800 nh=1600n_h=1600 Hoeffding, flat 0.550 0.381 0.265 0.187 0.134 One-stage EB, flat (Thm. 3) 0.930 0.507 0.276 0.156 0.092 One-stage EB, two-level 0.744 0.409 0.224 0.129 0.077 One-stage EB, two-level, b¯h,e=2 b_h,e=2 1.000 0.723 0.381 0.208 0.117 Calibrated Bernstein, flat (Thm. 2) 0.340 0.186 0.101 0.061 0.037 Calibrated Bernstein, two-level 0.293 0.161 0.088 0.053 0.033 Pooled Bennett (Prop. 4) 0.332 0.182 0.099 0.060 0.037 True regret 0.0037 0.0027 0.0029 0.0035 0.0044 Weight correction 0.033 0.028 0.019 0.014 0.012 Size of the certificates. Table 2 and Figure 1 report the mean certificates at ε=0.05 =0.05. The calibrated Bernstein certificate of Theorem 4 and the pooled Bennett certificate are nearly indistinguishable, and both are about 2.52.5–2.72.7 times smaller than the one-stage empirical-Bernstein certificate at every nhn_h. The one-stage certificate pays the linear term 7b¯h,et/3(nh−1)7 b_h,et/\3(n_h-1)\ in every stratum; for nh≤400n_h≤ 400 it is even larger than the flat Hoeffding certificate, which it overtakes only for nh≥800n_h≥ 800. In this design, therefore, the separate calibration budget αv _v is well spent, in line with Remark 7. All certificates remain far above the true regret, which is about 0.0030.003: at nh=1600n_h=1600 the smallest certificate is 0.0330.033, of which about 0.0120.012 is the weight-correction term. This gap is the price of a simultaneous, honest guarantee over 45254525 data-dependent competitors. Figure 1: Mean regret certificate R¯ R (logarithmic scales) over 200 replications at ε=0.05 =0.05, as a function of the number of audited queries per stratum. The pooled Bennett certificate (dashed, open marks) nearly coincides with the flat calibrated Bernstein certificate. The dashed black line is the mean true regret. Table 3: Mean regret certificate R¯ R over 200 replications at nh=400n_h=400, as a function of the redundancy envelope ε . Rows marked “ratio” divide the two-level certificate by the corresponding flat one. Certificate ε=0 =0 ε=0.02 =0.02 ε=0.05 =0.05 ε=0.1 =0.1 ε=0.2 =0.2 ε=0.4 =0.4 Calibrated Bernstein, flat 0.101 0.104 0.101 0.104 0.107 0.109 Calibrated Bernstein, two-level 0.082 0.087 0.088 0.097 0.113 0.139 ratio 0.81 0.84 0.87 0.93 1.05 1.27 One-stage EB, flat 0.278 0.280 0.276 0.278 0.280 0.276 One-stage EB, two-level 0.209 0.218 0.224 0.243 0.277 0.337 One-stage EB, two-level, b¯h,e=2 b_h,e=2 0.374 0.380 0.381 0.391 0.409 0.436 ratio (known envelope) 0.75 0.78 0.81 0.87 0.99 1.22 ratio (b¯h,e=2 b_h,e=2) 1.35 1.36 1.38 1.41 1.46 1.58 Pooled Bennett, flat 0.099 0.102 0.099 0.102 0.105 0.107 When does the multiscale network help? Table 3 and Figure 2 vary the redundancy envelope at nh=400n_h=400. With a known envelope, the two-level certificate is smaller than the flat one for small ε : by 19%19\% (ε=0 =0), 13%13\% (ε=0.05 =0.05) and 7%7\% (ε=0.1 =0.1) for the calibrated Bernstein version, and by 25%25\%, 19%19\% and 13%13\% for the one-stage version. The advantage vanishes between ε=0.1 =0.1 and ε=0.2 =0.2 for the calibrated version and at about ε=0.2 =0.2 for the one-stage version, and it turns into a loss at ε=0.4 =0.4. This crossover agrees with the deterministic threshold of Corollary 4, which equals about 0.190.19 for K0=42K_0=42, J=4525J=4525, nh=400n_h=400, α1=α2 _1= _2 and the present weights. The reduction of the radius at the population optimum can be much larger than the reduction of the certificate (from 0.0610.061 to 0.0130.013 at ε=0 =0 for the calibrated version), because the certificate is a maximum over all competitors. Finally, without a certified envelope (b¯h,e=2 b_h,e=2 on fine edges) the two-level certificate is 3535–58%58\% larger than the flat one: splitting the error budget across levels is then not compensated by any reduction of the linear term. This illustrates why the gains of Section 9 require certified, not merely empirical, envelopes (Proposition 5). Figure 2: Ratio of the mean two-level certificate to the mean flat certificate at nh=400n_h=400, as a function of the redundancy envelope ε ; values below 11 indicate a gain from the multiscale network. Summary. All certificates are valid. Among the fully observable ones, variance calibration (Theorem 4) or the pooled Bennett tilt (Proposition 4) gives the smallest flat certificates, and the multiscale network yields an additional reduction of up to about 20%20\% when fragments are strongly redundant and the redundancy is certified, in agreement with Corollary 4. We have specified a complete finite-sample probability argument: pilot screening, conditional concentration of every pre-audit comparison edge, telescoping over finite multiscale networks, simultaneous empirical variance calibration, correction for unknown context proportions, and conversion to postselection regret. The redundancy lemmas give explicit variance contractions for swapping documentary fragments. The confidence level in Theorem 4 is unconditional: it averages over the pilot, whose only contribution is the screening error αs _s, and it requires no model for P. Conditionally on ℱ0 F_0, only the post-screening part of the statement holds, with level 1−αa−αv−απ−αg1- _a- _v- _π- _g. The sets ℓN_ may be constructed using an independent pilot, including estimated similarities. Such a construction does not need to be accurate for the base theorem: validity follows from the edgewise simultaneous concentration with conservative envelopes. References Bartlett et al. (2005) Bartlett, P. L., Bousquet, O., and Mendelson, S. (2005). Local Rademacher complexities. The Annals of Statistics, 33(4), 1497–1537. doi:10.1214/009053605000000282. Boucheron et al. (2013) Boucheron, S., Lugosi, G., and Massart, P. (2013). Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press. doi:10.1093/acprof:oso/9780199535255.001.0001. Burgess and Chapman (2021) Burgess, M. A. and Chapman, A. C. (2021). Approximating the Shapley value using stratified empirical Bernstein sampling. In Proceedings of the 30th International Joint Conference on Artificial Intelligence, p. 73–81. doi:10.24963/ijcai.2021/11. Dirksen (2015) Dirksen, S. (2015). Tail bounds via generic chaining. Electronic Journal of Probability, 20(53), 1–29. doi:10.1214/EJP.v20-3760. Dudík et al. (2011) Dudík, M., Langford, J., and Li, L. (2011). Doubly robust policy evaluation and learning. In Proceedings of the 28th International Conference on Machine Learning, p. 1097–1104. https://icml.c/2011/papers/554_icmlpaper.pdf. Hoeffding (1963) Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301), 13–30. doi:10.1080/01621459.1963.10500830. Howard et al. (2021) Howard, S. R., Ramdas, A., McAuliffe, J., and Sekhon, J. (2021). Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2), 1055–1080. doi:10.1214/20-AOS1991. Koltchinskii (2006) Koltchinskii, V. (2006). Local Rademacher complexities and oracle inequalities in risk minimization. The Annals of Statistics, 34(6), 2593–2656. doi:10.1214/009053606000001019. Krause and Golovin (2014) Krause, A. and Golovin, D. (2014). Submodular function maximization. In Bordeaux, L., Hamadi, Y., and Kohli, P. (eds.), Tractability: Practical Approaches to Hard Problems, Cambridge University Press, p. 71–104. doi:10.1017/CBO9781139177801.004. Maurer and Pontil (2009) Maurer, A. and Pontil, M. (2009). Empirical Bernstein bounds and sample variance penalization. In Proceedings of the 22nd Annual Conference on Learning Theory (COLT). https://arxiv.org/abs/0907.3740. Nemhauser et al. (1978) Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. (1978). An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming, 14, 265–294. doi:10.1007/BF01588971. Talagrand (2005) Talagrand, M. (2005). The Generic Chaining: Upper and Lower Bounds of Stochastic Processes. Springer. doi:10.1007/3-540-27499-5.