Paper deep dive
Information Limits of Low-Rank Approximation Certification
Kang Liu, Bohao Qu
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:Low-rank approximation can require additional matrix--vector products to verify that its error meets a prescribed tolerance. We characterize this certification cost for both relative matrix error and mean-square output error. For a single approximation matrix candidate, we determine the exact dimension-uniform minimax query constant as the allowed failure probability vanishes. Our main result concerns reusing validation responses as the approximation space expands. For a candidate family constructed independently of validation, one batch supports an entire nested path without increasing the query budget with the number of checks. Across \(W\) paths, a concentration bound exploiting shared residual energy yields a \(\sqrt{\log(W+1)}\) dependence. A matching lower bound establishes its optimality for fixed interior error targets and sufficiently small separation gaps. Finally, we compare two uniformly valid certificates on the same dispersed-spectrum family. Optimizing the validation budget within each rule family yields costs of orders \(N^{1/3}\) and \(N^{2/3}\) for validation and construction beyond the true target. Code is available at this https URL
Tags
Links
- Source: https://arxiv.org/abs/2610.03321v1
- Canonical: https://arxiv.org/abs/2610.03321v1
Trouble viewing inline? Open PDF directly →
Full Text
182,100 characters extracted from source content.
Expand or collapse full text
Information Limits of Low-Rank Approximation Certification Kang Liu Bohao Qu Abstract Low-rank approximation can require additional matrix–vector products to verify that its error meets a prescribed tolerance. We characterize this certification cost for both relative matrix error and mean-square output error. For a single approximation matrix candidate, we determine the exact dimension-uniform minimax query constant as the allowed failure probability vanishes. Our main result concerns reusing validation responses as the approximation space expands. For a candidate family constructed independently of validation, one batch supports an entire nested path without increasing the query budget with the number of checks. Across W paths, a concentration bound exploiting shared residual energy yields a log(W+1) (W+1) dependence. A matching lower bound establishes its optimality for fixed interior error targets and sufficiently small separation gaps. Finally, we compare two uniformly valid certificates on the same dispersed-spectrum family. Optimizing the validation budget within each rule family yields costs of orders N1/3N^1/3 and N2/3N^2/3 for validation and construction beyond the true target. Code is available at https://anonymous.4open.science/r/Low-rank-approximation-1275/. 11footnotetext: School of Future Technology, Xi’an Jiaotong University, Xi’an, China. Corresponding author: Kang Liu (kanyo@foxmail.com). 2Centre for Frontier AI Research (CFAR), A*STAR, Singapore. 1 Introduction Low-rank approximations reduce computation and storage by representing high-dimensional linear operators through a small set of basis directions and their coefficients (Halko et al., 2011), with applications in model compression (Denton et al., 2014), dimensionality reduction, and large Jacobian approximation. Since the appropriate rank is often unknown, algorithms typically expand the approximation space until a prescribed accuracy is reached (Yu et al., 2018; Liu and Yu, 2025). For large operators that can only accessed through matrix–vector products (MVPs), such as neural-network Jacobians, determining whether this accuracy has been reached can itself be costly. An approximation may already meet the target while the algorithm continues working because it lacks sufficient evidence to stop. We study how to reliably decide whether a computed low-rank approximation is accurate enough to stop. The original operator A is accessed through forward MVPs, and its current approximation is PAPA, where P orthogonally projects onto the approximation space. Certification must reject approximations whose error is at or above the target and accept those below it by a prescribed gap, with both types of incorrect decision controlled by a given failure probability. We consider relative squared Frobenius error and relative mean-square output error, assuming a known input second moment for the latter. The question is how many MVPs are sufficient for these guarantees, and how many are unavoidable regardless of the certification procedure. For a given approximation, Gaussian probing provides a concrete way to obtain such guarantees (Halko et al., 2011; Epperly and Tropp, 2024). The squared norms of the residual responses estimate the Frobenius error, while transforming the probes using the known input second moment gives the corresponding output-error estimates. We analyze how often these estimates lead to an incorrect decision, obtaining a sufficient query budget. To establish a lower bound, we construct hard families of operators that require opposite decisions but produce statistically similar observations. This argument covers adaptive procedures that choose new queries using previous responses. In the worst case over matrices of arbitrary dimensions, the upper and lower bounds have the same leading constant as the allowed failure probability tends to zero. As the rank increases, checking each new approximation with fresh probes could repeatedly incur this validation cost. We therefore study whether the previously computed responses of A can support the subsequent checks. For a family of approximations constructed independently of validation, one batch suffices along an entire nested expansion path, with no increase in query budget as more approximations are checked. For simultaneous certification across W such paths, we obtain an optimal log(W+1) (W+1) dependence on W, for fixed interior error targets and sufficiently small gaps. The proof uses the ordering of residuals within each path and a concentration bound exploiting their shared energy constraint across paths. A matching lower bound shows that adaptive forward queries cannot improve this dependence in the worst case. Finally, we study how the validation budget affects the work performed before stopping. Fewer probes reduce the immediate validation cost, but the resulting uncertainty may cause further rank expansion after the approximation has already met its target. We account for this trade-off by adding validation queries to the expected construction cost beyond the true target. On a common dispersed-spectrum matrix family indexed by N, we compare an energy-ratio test and a block-sign certificate along the same expansion path. Both provide uniform reliability guarantees, but optimizing the validation budget within each rule family yields excess costs of orders N2/3N^2/3 and N1/3N^1/3, respectively. This separation quantifies how the choice of certificate affects the balance between collecting more evidence and continuing construction. Our main contributions are summarized as: (1) an exact minimax high-confidence query constant; (2) a shared-energy concentration bound and optimal log(W+1) (W+1) dependence for simultaneous certification; and (3) a stopping-cost separation between two uniformly valid certification rules. 2 Related Work Adaptive low-rank approximation. Randomized range finding constructs approximation spaces from operator applications with probabilistic error guarantees (Halko et al., 2011). Blocked factorizations and incremental QB schemes support adaptive stopping and fixed-precision approximation (Martinsson and Voronin, 2016; Yu et al., 2018), while randomized numerical-rank estimation helps select suitable approximation dimensions (Meier and Nakatsukasa, 2024). Recent work develops blockwise deflation with spectral and Frobenius guarantees (Liu and Yu, 2025), and matrix-free residual indicators with rank pruning and adjoint-free basis construction (Smith et al., 2026). Leave-one-out and jackknife diagnostics additionally assess errors and variances using existing construction data (Epperly and Tropp, 2024). We study the information required to certify a supplied approximation and the additional construction incurred while waiting for a reliable stopping decision. Error estimation and query complexity. The identity ‖R‖F2=tr(R⊤R)\|R\|_F^2=tr(R R) connects residual-energy estimation to stochastic trace estimation. Classical analyses give relative-error sample bounds with prescribed failure probabilities (Avron and Toledo, 2011; Roosta-Khorasani and Ascher, 2015), with further concentration results for indefinite matrices (Cortinovis and Kressner, 2022). Hutch++ and its adaptive variants combine low-rank approximation with residual sampling (Meyer et al., 2021; Persson et al., 2022); XTrace exploits exchangeability and spectral structure (Epperly et al., 2024). Query lower bounds address scalar quadratic-form access (Wimmer et al., 2014) and matrix–vector access (Woodruff et al., 2022). The oracle distinction prevents direct transfer: our oracle returns the full vector AvAv, revealing v⊤A⊤Av=‖Av‖22v A Av=\|Av\|_2^2, but does not directly provide A⊤AvA Av. Our bounds concern relative-error under this oracle, including an exact high-confidence minimax constant. Shared information and simultaneous guarantees. Dynamic trace estimation exploits small matrix updates (Dharangutte and Musco, 2021; Woodruff et al., 2022), while parameter-dependent estimators reuse probes and operator products through polynomial approximation (Matti et al., 2026). More generally, bounds for suprema of matrix-indexed quadratic processes capture dependencies that separate concentration bounds ignore (Krahmer et al., 2014; Dirksen, 2015). Here the relevant structure is the common envelope 0⪯Ei⪯T0 E_i T, together with ordered residuals along each path. Proposition 4.2 controls the normalized energy estimates jointly; boundary reduction and a matching lower bound then give the optimal log(W+1) (W+1) width dependence in Theorem 4.1. The complete candidate family is independent of validation, although its traversal and final selection may be adaptive. 3 Optimal Certification of a Single Approximation We begin with the query cost of certifying an approximation, which establishes the information requirement for decisions before considering repeated checks and stopping along the expansion path. 3.1 Problem formulation Let A∈ℝm×nA ^m× n be nonzero. An orthonormal basis U∈ℝm×rU ^m× r defines the known orthogonal projector P=UU⊤P=U and approximation PAPA. Its relative squared Frobenius error is q(P)=‖(I−P)A‖F2/‖A‖F2q(P)=\|(I-P)A\|_F^2/\|A\|_F^2, the fraction of energy outside the retained output space. Given 0<g<ρ<10<g<ρ<1 and 0<δ<1/20<δ<1/2, certification requires q(P)≥ρ q(P)≥ρ ⟹ℙaccept≤δ, ~P\accept\≤δ, q(P)≤ρ−g q(P)≤ρ-g ⟹ℙreject≤δ. ~P\reject\≤δ. Either decision is allowed in the intervening region. Thus, g specifies the accuracy margin at which acceptance must become reliable. Each forward query v↦Av Av returns the full output vector. Query directions may depend on previous responses and private randomness, but every run uses at most s queries. Let Rs(ρ,g)R_s(ρ,g) be the smallest achievable worst-case error probability over the two decision regions, with the worst case taken over all dimensions, nonzero matrices, and supplied projections. Procedures may use the dimensions and projection. The optimal query budget is s⋆(δ,ρ,g)=mins:Rs(ρ,g)≤δs (δ;ρ,g)= \s:R_s(ρ,g)≤δ\. Upper bounds also apply conditionally on a construction stage independent of the validation probes, counting only additional validation queries. Lower bounds, by contrast, charge for all operator observations available to the procedure, including any supplied construction responses; no construction transcript is provided free of charge. 3.2 Gaussian certification and optimality Following Gaussian residual estimation (Halko et al., 2011), draw independent gi∼(0,In)g_i (0,I_n) and cache Y=AGY=AG, where G=[g1,…,gs]G=[g_1,…,g_s]. These s queries give the estimate q^=‖(I−P)Y‖F2/‖Y‖F2 q=\|(I-P)Y\|_F^2/\|Y\|_F^2. Define the log-odds map ℓ(x)=log[x/(1−x)] (x)= [x/(1-x)] and the transformed gap Δ=ℓ(ρ)−ℓ(ρ−g) = (ρ)- (ρ-g). The certificate accepts when ℓ(q^)≤(ℓ(ρ)+ℓ(ρ−g))/2, ( q)≤( (ρ)+ (ρ-g))/2, with the natural endpoint conventions. This midpoint gives the same deviation margin to the two decision regions. Theorem 3.1 (Information limits for a single approximation). Fix 0<g<ρ<10<g<ρ<1 and Δ=ℓ(ρ)−ℓ(ρ−g) = (ρ)- (ρ-g). Let ps(u)=ℙFs,s≤e−up_s(u)=P\F_s,s≤ e^-u\, where Fs,sF_s,s is the ratio of two independent χs2 _s^2 variables. For every integer s≥1s≥ 1, ps(Δ/2)≤Rs(ρ,g)≤exp[−slogcosh(Δ/4)].p_s( /2)≤ R_s(ρ,g)≤ [-s ( /4)]. Consequently, limδ↓0[s⋆(δ,ρ,g)/log(1/δ)]=1/logcosh(Δ/4). _δ 0[s (δ;ρ,g)/ (1/δ)]=1/ ( /4). Since −s−1logps(u)→logcosh(u/2)-s^-1 p_s(u)→ (u/2), the two bounds share the same exponential rate. The upper bound follows by analyzing residual and captured energy jointly. Write T=A⊤AT=A A, E=A⊤(I−P)AE=A (I-P)A, C=T−EC=T-E, and Z(M)=s−1∑igi⊤MgiZ(M)=s^-1 _ig_i Mg_i. For q=q(P)∈(0,1)q=q(P)∈(0,1), L:=ℓ(q^)−ℓ(q)=log(Z(E)/Z(C))−log(trE/trC).L:= ( q)- (q)= (Z(E)/Z(C))- (trE/trC). The common denominator cancels, leaving a comparison between two energy estimates computed from the same probes. The cases q=0,1q=0,1 are exact almost surely. To control the lower tail, normalize E¯=E/trE E=E/trE and C¯=C/trC C=C/trC. For u>0u>0, the event L≤−uL≤-u is equivalent to Z(H)≤0Z(H)≤ 0, where H=E¯−e−uC¯H= E-e^-u C. If p and r denote the total positive and absolute negative eigenvalue masses of H, then p≤1p≤ 1, r≤e−ur≤ e^-u, and p−r=1−e−up-r=1-e^-u. Grouping the positive and negative eigenvalue factors gives, for 0<t<eu/20<t<e^u/2, det(In+2tH)≥(1+2tp)(1−2tr)≥(1+2t)(1−2te−u). (I_n+2tH)≥(1+2tp)(1-2tr)≥(1+2t)(1-2te^-u). The second inequality uses pr≤e−upr≤ e^-u. For a standard Gaussian vector z, the identity e−tz⊤Hz=det(In+2tH)−1/2Ee^-tz Hz= (I_n+2tH)^-1/2 therefore bounds the exponential moment without assuming independence between the two energy estimates. Exponential Markov with t=(eu−1)/4t=(e^u-1)/4, followed by interchanging E and C, yields ℙL≤−u,ℙL≥u≤exp[−slogcosh(u/2)].P\L≤-u\,~P\L≥ u\≤ [-s (u/2)]. Each incorrect decision requires a deviation of at least Δ/2 /2, proving the upper bound. Appendix A.2 gives the complete moment and tail arguments. For the lower bound, consider two Gaussian matrix priors with P=diag(0,1)P=diag(0,1). Under hypothesis h∈0,1h∈\0,1\, the columns of A are independent (0,Σh/n)N(0, _h/n) vectors. The diagonal, determinant-one covariances are chosen so that the error log-odds concentrate at ℓ(ρ)+η (ρ)+η and ℓ(ρ−g)−η (ρ-g)-η, respectively, for an auxiliary η>0η>0. Therefore, it is necessary to distinguish these priors for reliable certification as n grows. To account for adaptive queries, decompose each new direction as v=v∥+v⟂v=v_ +v_ relative to the span of previous queries. The parallel response is already known, whereas input isotropy gives the conditional representation Av=Av∥+‖v⟂‖2nξ,ξ∼(0,Σh).Av=Av_ + \|v_ \|_2 n\,ξ,~~ξ (0, _h). (1) The innovation is independent of the past. Consequently, at most s independent covariance observations simulate the complete adaptive transcript through a rule independent of h. Lemma A.4 proves this representation and the transcript reduction. For the chosen covariances, the optimal equal-prior test on these observations has error ps(Δ/2+η)p_s( /2+η). The probability that a prior draw lies outside its intended decision region vanishes as n→∞n→∞. Taking this limit and then η↓0η 0 gives the lower bound; Proposition A.5 supplies the explicit test and finite-dimensional correction. Finally, −s−1logps(u)→logcosh(u/2)-s^-1 p_s(u)→ (u/2) by Lemma A.3, so the risk bounds have the same exponential rate and yield the stated query constant. For fixed interior ρ, taking the high-confidence limit before g↓0g 0 gives the leading cost 32ρ2(1−ρ)2g−2log(1/δ)32ρ^2(1-ρ)^2g^-2 (1/δ). Appendix A.7 derives this expansion. Its g−2g^-2 dependence provides the precision scale for the multiple-approximation problem studied next. The same framework also certifies mean-square output error by incorporating the input second moment into the probes. Corollary 3.2 (Mean-square output certification). Suppose K=[xx⊤]⪰0K=E[x ] 0 is known and tr(AKA⊤)>0tr(AKA )>0. With B=AK1/2B=AK^1/2, qK(P):=‖Ax−PAx‖22‖Ax‖22=‖(I−P)B‖F2‖B‖F2.q_K(P):= E\|Ax-PAx\|_2^2E\|Ax\|_2^2= \|(I-P)B\|_F^2\|B\|_F^2. For every given K, probes K1/2giK^1/2g_i give the same Gaussian upper bounds. When the worst case also ranges over all admissible known second moments, the minimax risk equals Rs(ρ,g)R_s(ρ,g), with the same exact high-confidence query constant. The input distribution need not be Gaussian. The reduction and the minimax statement are proved in Appendix A.8. 4 Reusing Validation Across Approximation Paths Once the responses Y=AGY=AG have been computed, another approximation PAPA can be checked by projecting the same Y, without further queries to A. The question is whether these repeated decisions remain jointly reliable. Throughout this section, the complete approximation family is finite or countable and constructed independently of the validation probes G, with ρ,gρ,g fixed in advance. Validation outcomes may guide visits, switches, and final selection within this family, but cannot be used to construct new members. Our guarantees concern the simultaneous correctness of all required decisions, which also protects a selection made using those outcomes. 4.1 Repeated checks along a nested path Suppose each expansion retains the existing approximation space: range(Pj)⊆range(Pj+1)range(P_j) (P_j+1). The residual energy matrices Ej=A⊤(I−Pj)AE_j=A (I-P_j)A then satisfy Ej+1⪯Ej⪯TE_j+1 E_j T. Consequently, both the true errors qjq_j and their estimates q^j=Z(Ej)/Z(T) q_j=Z(E_j)/Z(T) decrease along the path. This ordering reduces repeated certification to two boundary decisions. On a finite path, approximations with qj≥ρq_j≥ρ form a prefix. Under a common acceptance threshold, accepting any member of this prefix implies accepting its last member. Similarly, approximations with qj≤ρ−gq_j≤ρ-g form a suffix, and rejecting any member implies rejecting its first member. Thus, every required decision is correct if these two boundary decisions are correct. The boundaries depend on the true errors and are used only for analysis; the procedure need not identify them. Applying Theorem 3.1 to at most two boundaries gives a query budget independent of the number of checks. Lemma B.1 formalizes this reduction. 4.2 Optimal cost of comparing multiple paths An approximation family has path width at most W if its residual energy matrices can be covered by W chains in the positive semidefinite order. This includes W nested expansion paths, regardless of their lengths. Let ssim⋆(δ,ρ,g,W)s _sim(δ;ρ,g,W) be the least query budget ensuring that all required decisions are correct with probability at least 1−δ1-δ, uniformly over dimensions, operators, and known families of width at most W. We use the query and information-accounting model of Section 3.1. The chain cover describes the instance class; the certification procedure does not need to compute it. Theorem 4.1 (Information limits for simultaneous certification). Fix ρ∈(0,1)ρ∈(0,1), and set w=minρ,1−ρw= \ρ,1-ρ\. For integers W≥1W≥ 1, 0<g≤w/320<g≤ w/32, and 0<δ≤1/40<δ≤ 1/4, under the independent-family model above, ssim⋆(δ;ρ,g,W)≍ρlog(W+1)+log(1/δ)g2.s _sim(δ;ρ,g,W) _ρ (W+1)+ (1/δ)g^2. The comparison constants depend only on ρ. Independent Gaussian probes and the rule q^λ≤ρ−g/2 q_λ≤ρ-g/2 attain the upper bound. The lower bound allows arbitrary adaptive forward queries with a hard budget. The arithmetic midpoint used here targets the additive separation gap. For fixed W,ρ,gW,ρ,g, the log-odds midpoint from the preceding section also preserves the exact high-confidence constant 1/logcosh(Δ/4)1/ ( /4); Proposition B.2 gives this consequence of the boundary reduction. To obtain the smaller dependence on a growing W, we use the additional fact that all residual energies satisfy 0⪯Eλ⪯T0 E_λ T. Proposition 4.2 (Concentration under a shared energy envelope). Let T⪰0T 0 satisfy trT>0trT>0, and let 0⪯Ei⪯T0 E_i T, 1≤i≤M1≤ i≤ M, be fixed independently of the Gaussian probes. Set qi=tr(Ei)/tr(T)q_i=tr(E_i)/tr(T) and q^i=Z(Ei)/Z(T) q_i=Z(E_i)/Z(T). For every integer s≥1s≥ 1 and 0<α<10<α<1, ℙmaxi≤M|q^i−qi|>16log(2M)+log(5/α)s≤α.P\! \ _i≤ M| q_i-q_i|>16 (2M)+ (5/α)s \≤α. (2) To explain the dependence on M, normalize trT=1trT=1 and write Ei=T1/2KiT1/2E_i=T^1/2K_iT^1/2, where 0⪯Ki⪯I0 K_i I. Centering the ratio gives Fi=Ei−qiT,trFi=0,q^i−qi=Z(Fi)/Z(T).F_i=E_i-q_iT,~trF_i=0,~ q_i-q_i=Z(F_i)/Z(T). The shared envelope constrains how these centered matrices can vary across directions. Split T into a head containing its largest r eigenvalues and a remaining tail. For the head, ‖Fi,HH‖∗≤1\|F_i,H\|_*≤ 1, where ∥⋅∥∗\|·\|_* denotes the nuclear norm. Every centered head contribution is therefore bounded by the operator norm of the same centered sample covariance. Gaussian singular-value concentration (Vershynin, 2012, Corollary 5.35) controls all heads together at leading scale r/s r/s, without a union bound over i. For the tail, trace normalization gives ‖TL‖op≤1/r\|T_L\|_op≤ 1/r and ‖Fi,LL‖F2≤1/r\|F_i,L\|_F^2≤ 1/r. A union bound over the tail quadratic forms then gives the leading scale log(2M)/(rs) (2M)/(rs). The interaction between head and tail is controlled by Ki,HLKi,LH⪯Ki,HH−Ki,HH2⪯I/4,K_i,HLK_i,LH K_i,H-K_i,H^2 I/4, which follows from Ki2⪯KiK_i^2 K_i. It yields ‖Fi,HL‖F2≤1/(4r)\|F_i,HL\|_F^2≤ 1/(4r); conditioning on the Gaussian head controls the cross contribution at the same leading scale as the tail. Thus, the argument also covers residual matrices that do not commute. Choosing r=⌈log(2M)⌉r= (2M) balances the two scales: rs≍log(2M)rs≍(log(2M)s)1/2. rs (2M)rs ( (2M)s )^1/2. If the ambient dimension is smaller, using the entire space as the head gives an equal or smaller bound. The estimation error therefore grows as (logM)1/4/s( M)^1/4/ s, producing a logM M query factor when accuracy proportional to g is required. Appendix B.4 supplies the complete block estimates, confidence terms, and control of the common denominator Z(T)Z(T). The spectral split is used only in the proof and requires no spectral information from the procedure. Applying Proposition 4.2 once to the at most 2W2W boundary approximations, with α=δα=δ, proves the upper bound in Theorem 4.1. Indeed, estimation error at most g/3g/3 puts both decision regions strictly on the correct sides of ρ−g/2ρ-g/2. For a countable family, each finite subset still has at most 2W2W boundaries, so the same budget applies uniformly; increasing finite subsets then give the full-family guarantee. Appendix B.5 gives this application and its explicit budget. For the lower bound, begin with a covariance-testing problem. A packing of output subspaces yields M trace-one covariances Σi _i and fixed residual projectors RjR_j, with logM≍d2 M d^2, such that tr(RiΣi)=ρ−2g,tr(RjΣi)≥ρ+2g(j≠i).tr(R_i _i)=ρ-2g,~~tr(R_j _i)≥ρ+2g~(j≠ i). (3) At the same time, the divergence between any two Gaussian observation laws satisfies KL((0,Σi)∥(0,Σj))≲ρg2dKL(N(0, _i)\|N(0, _j)) _ρg^2d. Lemma C.3 gives the packing, and Appendix C.3 constructs the covariances and projectors. For these energy ratios, simultaneous correctness forces the accepted set to be exactly i\i\, identifying the hidden covariance label. Thus, decoding error is no larger than certification error. Fano’s inequality (Scarlett and Cevher, 2019) requires, for a fixed small error probability, sg2d≳ρlogM≍d2,hences≳ρlogM/g2.sg^2d _ρ M d^2,hence~s _ρ M/g^2. To transfer this bound to the operator oracle, draw the columns of A independently from (0,Σi/n)N(0, _i/n). The Gaussian innovation representation (1) reduces every adaptive transcript to at most s covariance observations. As n→∞n→∞, the actual approximation errors concentrate around the separated ratios in (3), so the probability of violating the intended decision regions vanishes. Appendices C.4–C.6 provide the transcript, leakage, and decoding arguments. Taking M=WM=W singleton paths gives the width term. The single-approximation lower bound supplies g−2log(1/δ)g^-2 (1/δ) and handles bounded W; the maximum of these two lower bounds is equivalent to their sum. The uniform treatment of confidence levels and integer widths is given in Appendix C.7. Finally, the transformation B=AK1/2B=AK^1/2 from Corollary 3.2 preserves the residual ordering and implements each probe with one forward MVP. The reuse upper bounds therefore extend to mean-square output error for every given K. The corresponding minimax lower bounds hold when the worst case also ranges over known second moments, since K=InK=I_n recovers the Frobenius problem; see Appendix B.7. 5 Certification Delay in Iterative Approximation We now combine the cost of validation with the construction performed while waiting for acceptance. A smaller validation batch costs less, but may require further rank expansions before there is enough evidence to stop. The resulting trade-off depends on both the certification rule and the spectrum of the operator. The algorithm cannot observe the true error directly; it must certify it from finitely many random probes. To control false acceptance, the acceptance threshold must lie below the target, so reaching the target need not produce immediate acceptance. Fix a nested expansion path constructed independently of validation, and reuse the same s probes throughout. Let r⋆=minr:q(Pr)≤ρr_ = \r:q(P_r)≤ρ\ be the first position reaching the true target, and let τs _s be the first position accepted by the certificate. Define the additional construction and its combined cost by Ds:=(τs−r⋆)+,(s):=cvs+cbDs,D_s:=( _s-r_ )_+,C(s):=c_vs+c_bED_s, where cv,cb>0c_v,c_b>0 are fixed costs per validation query and construction step. Validation is paid for once, while construction before r⋆r_ is excluded. Early acceptance contributes zero delay and is controlled separately by the probability of false stopping. 5.1 Uniform safety and spectrum-dependent power The log-ratio bound from Section 3 gives the energy-ratio stopping rule ℓ(q^)≤ℓ(ρ)−us(δ),us(δ)=2arcosh(δ−1/s). ( q)≤ (ρ)-u_s(δ),~~u_s(δ)=2arcosh(δ^-1/s). For every approximation with q≥ρq≥ρ, the probability of acceptance is at most δ. The boundary reduction from Section 4.1 extends this guarantee to false stopping anywhere along the path. For fixed ρ,δρ,δ, the corresponding threshold θs=ℓ−1(ℓ(ρ)−us(δ)) _s= ^-1( (ρ)-u_s(δ)) satisfies ρ−θs=Θ(s−1/2)ρ- _s= (s^-1/2) as s→∞s→∞. This margin is calibrated uniformly over spectra. To examine how another statistic responds to spectral dispersion, consider a block-sign certificate. Set H=E−ρTH=E-ρ T, partition s=Lbs=Lb probes into L predetermined blocks of size b≥2b≥ 2, and compute Xℓ(H)=1b∑i∈ℐℓgi⊤Hgi,VL(H)=∑ℓ=1LXℓ(H)≥0.X_ (H)= 1b _i _ g_i Hg_i,~~V_L(H)= _ =1^L1\X_ (H)≥ 0\. These statistics use the cached responses because gi⊤Hgi=‖(I−P)Agi‖22−ρ‖Agi‖22g_i Hg_i=\|(I-P)Ag_i\|_2^2-ρ\|Ag_i\|_2^2. A negative block statistic supports acceptance; the rule stops when sufficiently few blocks remain nonnegative. Specifically, define kδ(L) k_δ(L) =maxk∈0,…,L−1: = \k∈\0,…,L-1\: . ℙBin(L,e−1)≤k≤δ, .P\Bin(L,e^-1)≤ k\≤δ \, and accept when VL(H)≤kδ(L)V_L(H)≤ k_δ(L). If the defining set is empty, set kδ(L)=−1k_δ(L)=-1, so the rule always rejects. Proposition 5.1 (Block-sign safety). For b≥2b≥ 2, fixed 0⪯E⪯T0 E T, and trT>0trT>0, the block-sign rule accepts with probability at most δ whenever q≥ρq≥ρ. The same bound controls acceptance at any such position along a nested path constructed independently of validation. Proof. When q≥ρq≥ρ, we have trH≥0trH≥ 0. Lemma D.2 establishes ℙXℓ(H)≥0≥e−1P\X_ (H)≥ 0\≥ e^-1 through a log-concavity argument. The independent blocks therefore give VL(H)∼Bin(L,p)V_L(H) (L,p) for some p≥e−1p≥ e^-1, and the definition of kδ(L)k_δ(L) bounds acceptance by δ. Along a nested path, every block statistic and hence VLV_L is nonincreasing, so the unsafe-prefix boundary argument applies. Appendix D.2 gives the complete sign-probability and pathwise arguments. ∎ The cutoff depends only on L,δL,δ, whereas the probability of acceptance below the target depends on the fluctuations of the block statistics. Appendix D.3 quantifies this dependence through their variance relative to their squared mean. Thus, spectral structure affects power without being an input to the calibration. 5.2 A separation on the same spectral family Consider the family AM,N=diag(1−ρMIM,ρNIN).A_M,N=diag ( 1-ρM\,I_M,\, ρN\,I_N ). A coordinate expansion path first captures the initial M directions and then adds the remaining directions one at a time. Consequently, r⋆=Mr_ =M and q(PM+j)=ρ(1−j/N)q(P_M+j)=ρ(1-j/N). Both certificates use this same operator, path, and reliability level. When kδ(L)≥0k_δ(L)≥ 0, both accept almost surely at full rank, so their stopping costs are finite. Theorem 5.2 (Diffuse-spectrum delay and allocation). Fix ρ∈(0,1)ρ∈(0,1), δ∈(0,1/2)δ∈(0,1/2), and an integer L such that k=kδ(L)≥0k=k_δ(L)≥ 0. Suppose M/N→κ∈(0,∞)M/N→κ∈(0,∞) as N→∞N→∞. For s=Lb→∞s=Lb→∞, with integer b≥2b≥ 2 and b=o(N)b=o(N), Dssign∼CsignN/s,Dsratio∼CratioN/s,ED_s^sign C_sign N/s,~~ED_s^ratio C_ratioN/ s, (4) where the positive constants depend only on the fixed parameters. For fixed positive cost weights cv,cbc_v,c_b, minb∈ℕ,b≥2Nsign(Lb)=Θ(N1/3),mins∈ℕ,s≥1Nratio(s)=Θ(N2/3). _ subarraycb ,b≥ 2 subarrayC_N^sign(Lb)= (N^1/3),~ _ subarraycs ,s≥ 1 subarrayC_N^ratio(s)= (N^2/3). The optimal budgets have the same respective orders. Optimization is within the two specified rule families, keeping L,kL,k fixed for block signs and excluding construction of the initial M directions. The delay scales follow by comparing the initial fluctuations with the error decrease produced by each additional direction. Let Xℓ(j)X_ (j) denote a block statistic after j tail directions have been captured. When M/N→κ∈(0,∞)M/N→κ∈(0,∞), sd(Xℓ(0))≍1bN,Xℓ(j)=−ρjN.sd(X_ (0)) 1 bN,~EX_ (j)=- ρ jN. The accumulated negative drift reaches the initial fluctuation scale after order N/b N/b steps. For fixed L,kL,k, acceptance requires a fixed number of blocks to cross zero, changing the constant but preserving this scale. Since s=Lbs=Lb, the resulting delay is of order N/s N/s. For the energy-ratio rule, the threshold remains order s−1/2s^-1/2 below ρ, while the estimation fluctuations on this family have the smaller scale (sN)−1/2(sN)^-1/2. Each additional direction reduces the true error by ρ/Nρ/N, so covering the calibrated margin requires order N/sN/ s further steps. Propositions D.4 and D.5 establish these crossing limits, prove convergence of the expectations, give the exact constants in (4). Within these asymptotic regimes, the combined costs therefore have the balances Nsign(s)≍s+N/s,Nratio(s)≍s+Ns,C_N^sign(s) s+ N/s,~~C_N^ratio(s) s+ N s, up to fixed positive coefficients. Balancing validation against additional construction produces the respective N1/3N^1/3 and N2/3N^2/3 budgets and costs. Appendix D.7 handles the remaining budget regimes and proves global optimality over the allowed integer budgets. For mean-square output error, both rules use the transformed responses A(K1/2gi)A(K^1/2g_i) from Corollary 3.2, retaining the same safety guarantees. The delay comparison applies when the effective operator B=AK1/2B=AK^1/2 and its expansion path have the spectral structure above; see Appendix D.8. 6 Numerical Experiments The experiments examine three consequences of the theory: the single-candidate confidence exponent, the width-dependent cost of shared validation, and the effect of spectral structure on stopping cost. Synthetic operators provide known errors and controlled candidate families. Gaussian response statistics are sampled from their exact finite-dimensional distributions. Full configurations, sampling checks, and additional results are provided in the appendix. Figure 1: Numerical illustrations of the certification theory. (a) The normalized F-tail exponent approaches one. (b) Selected Gaussian validation budgets versus logW W; dashed and dotted curves indicate square-root logarithmic and logarithmic reference slopes, respectively. (c) Spectral dispersion changes the relative stopping delays of the two certificates. (d) Independently evaluated costs at selected validation budgets; dashed curves show the asymptotic minimum costs within the two rule families. Legend exponents in (b,d) are descriptive log–log fits. Error bars in (c,d) indicate ±2± 2 Monte Carlo standard errors; those in (d) are conditional on the selected budgets. Single-candidate confidence exponent. To examine the finite-query behavior of Theorem 3.1, we numerically evaluate the F-tail lower bound ps(Δ/2)p_s( /2) for Δ∈1,2 ∈\1,2\. Figure 1(a) plots −logps(Δ/2)/(sJ)- p_s( /2)/(sJ), where J=logcosh(Δ/4)J= ( /4). At s=4096s=4096, the normalized exponents are 1.0291.029 and 1.0091.009, respectively. Their approach to one illustrates how the lower and upper bounds acquire the same leading confidence exponent. Shared validation and the width mechanism. To examine the logW W contribution in Theorem 4.1, we construct fixed families of noncommuting residual energy matrices sharing one positive-semidefinite envelope. The effective dimension ranges from d=8d=8 to 128128, with W=2d(d−1)/2W=2^d(d-1)/2 ordered paths. Each path contains candidates at both decision boundaries, ρ=0.5ρ=0.5 and ρ−g=0.49ρ-g=0.49. Increasing dimension together with width avoids the saturation inherent in a fixed-dimensional experiment. The construction permits the maximum validation error over the entire finite family to be computed without enumeration; its attainment is checked for every simulated sketch. Budgets are selected by screening toward a simultaneous error rate of 0.10.1, followed by 81928192 fresh evaluation trials. Over the largest five dimensions, the selected budgets have log–log slope 0.4880.488 against logW W, close to the predicted 1/21/2 (Figure 1(b)). At fixed s=4096s=4096, the mean maximum error has slope 0.2560.256, consistent with the underlying (logW)1/4/s( W)^1/4/ s scale. Independent evaluation rates range from 2.32%2.32\% to 10.72%10.72\%; these are screening-selected budgets, not exact minimum budgets at a common error probability. The results illustrate the width mechanism for Gaussian validation; the lower bound for arbitrary adaptive queries is established by theory. The appendix also reports repeated-check experiments in which retaining both decision boundaries makes the failure event unchanged when intermediate checks are added. Spectral structure and stopping cost. We compare the energy-ratio and block-sign certificates on the diagonal family from Section 5, using ρ=0.1ρ=0.1, δ=0.05δ=0.05, and L=32L=32 sign blocks. Both certificates follow the same coordinate expansion path. At N=2048N=2048 and s=128s=128, dispersing the captured energy over M=NM=N directions yields mean additional construction costs of 673.6673.6 steps for the ratio certificate and 33.633.6 for block signs (Figure 1(c)). Concentrating that energy in one direction (M=1M=1) reverses the ordering, demonstrating the instance dependence of the gain. To assess whether the separation persists after budget selection, we vary M=NM=N from 2122^12 to 2302^30. Each rule selects its budget from the same prespecified geometric grid using screening samples, followed by 81928192 fresh evaluation trials at the selected budget. The cost is s+Ds+ED, excluding construction before the true target. Over the largest four dimensions, the fitted cost exponents are 0.3340.334 for block signs and 0.6680.668 for the ratio certificate (Figure 1(d)). These grid-selected costs agree with the predicted N1/3N^1/3 and N2/3N^2/3 growth within the two specified rule families. 7 Conclusion and Limitations We characterize the information needed to certify relative error in iterative low-rank approximation. The results identify an exact single-candidate confidence constant, an optimal width dependence for shared validation, and a separation between reliable decisions and prompt stopping. The guarantees require candidate families independent of validation, and query complexity excludes the arithmetic cost of evaluating candidates. The stopping-cost separation concerns excess work within two specified rule families, rather than total runtime or optimality over all certificates. Extending these guarantees to candidates constructed using the validation responses remains an open direction. AI Use Statement Generative AI tools were used to check for typographical errors and to provide an auxiliary review for reference. They were also used to draft and check the section SAMPLING CHECKS AND REPRODUCIBILITY in the Appendix. The authors take full responsibility for the content. References Avron and Toledo (2011) H. Avron and S. Toledo Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. Journal of the ACM 58 (2), p. 8:1–8:34. External Links: Document, Link Cited by: §2. Cortinovis and Kressner (2022) A. Cortinovis and D. Kressner On randomized trace estimates for indefinite matrices with an application to determinants. Foundations of Computational Mathematics 22 (3), p. 875–903. External Links: Document Cited by: §2. Denton et al. (2014) R. Denton, W. Zaremba, J. Bruna, Y. LeCun, and R. Fergus Exploiting linear structure within convolutional networks for efficient evaluation. Note: arXiv preprint arXiv:1404.0736 External Links: 1404.0736, Link Cited by: §1. Dharangutte and Musco (2021) P. Dharangutte and C. Musco Dynamic trace estimation. In Advances in Neural Information Processing Systems, Vol. 34. External Links: Link Cited by: §2. Dirksen (2015) S. Dirksen Tail bounds via generic chaining. Electronic Journal of Probability 20 (53), p. 1–29. External Links: Document Cited by: §2. Epperly et al. (2024) E. N. Epperly, J. A. Tropp, and R. J. Webber XTrace: making the most of every sample in stochastic trace estimation. SIAM Journal on Matrix Analysis and Applications 45 (1), p. 1–23. External Links: Link Cited by: §2. Epperly and Tropp (2024) E. N. Epperly and J. A. Tropp Efficient error and variance estimation for randomized matrix computations. SIAM Journal on Scientific Computing 46 (1), p. A508–A528. External Links: Document, Link Cited by: §1, §2. Halko et al. (2011) N. Halko, P. Martinsson, and J. A. Tropp Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review 53 (2), p. 217–288. External Links: Document, Link Cited by: §1, §1, §2, §3.2. Krahmer et al. (2014) F. Krahmer, S. Mendelson, and H. Rauhut Suprema of chaos processes and the restricted isometry property. Communications on Pure and Applied Mathematics 67 (11), p. 1877–1904. External Links: Document Cited by: §2. Liu and Yu (2025) Q. Liu and Y. Yu Efficient adaptive randomized algorithms for fixed-threshold low-rank matrix approximation. Note: arXiv preprint arXiv:2508.07553 External Links: 2508.07553, Link Cited by: §1, §2. Martinsson and Voronin (2016) P. Martinsson and S. Voronin A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices. SIAM Journal on Scientific Computing 38 (5), p. S485–S507. External Links: Document Cited by: §2. Matti et al. (2026) F. Matti, H. He, D. Kressner, and H. Y. Lam Stochastic trace estimation for parameter-dependent matrices applied to spectral density approximation. SIAM Journal on Scientific Computing 48 (4), p. A2287–A2313. External Links: Document, Link Cited by: §2. Meier and Nakatsukasa (2024) M. Meier and Y. Nakatsukasa Fast randomized numerical rank estimation for numerically low-rank matrices. Linear Algebra and its Applications 686, p. 1–32. External Links: Document Cited by: §2. Meyer et al. (2021) R. A. Meyer, C. Musco, C. Musco, and D. P. Woodruff Hutch++: optimal stochastic trace estimation. In Symposium on Simplicity in Algorithms (SOSA), p. 142–155. External Links: Link Cited by: §2. Persson et al. (2022) D. Persson, A. Cortinovis, and D. Kressner Improved variants of the Hutch++ algorithm for trace estimation. SIAM Journal on Matrix Analysis and Applications 43 (3), p. 1162–1185. External Links: Document Cited by: §2. Roosta-Khorasani and Ascher (2015) F. Roosta-Khorasani and U. Ascher Improved bounds on sample size for implicit matrix trace estimators. Foundations of Computational Mathematics 15 (5), p. 1187–1212. External Links: Document Cited by: §2. Saumard and Wellner (2014) A. Saumard and J. A. Wellner Log-concavity and strong log-concavity: a review. Statistics Surveys 8, p. 45–114. External Links: Link Cited by: §D.2. Scarlett and Cevher (2019) J. Scarlett and V. Cevher An introductory guide to Fano’s inequality with applications in statistical estimation. Note: arXiv preprint arXiv:1901.00555 External Links: 1901.00555, Link Cited by: §C.4, §C.6, §4.2. Smith et al. (2026) A. I. Smith, E. Do, and C. Chen Adaptive, matrix-free low-rank approximation. External Links: 2607.06758, Link Cited by: §2. Vershynin (2012) R. Vershynin Introduction to the non-asymptotic analysis of random matrices. In Compressed Sensing: Theory and Applications, Y. C. Eldar and G. Kutyniok (Eds.), p. 210–268. External Links: Link Cited by: §4.2. Wimmer et al. (2014) K. Wimmer, Y. Wu, and P. Zhang Optimal query complexity for estimating the trace of a matrix. In Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science, Vol. 8572, p. 1051–1062. External Links: Document Cited by: §2. Woodruff et al. (2022) D. P. Woodruff, F. Zhang, and R. Zhang Optimal query complexities for dynamic trace estimation. In Advances in Neural Information Processing Systems, Vol. 35, p. 35049–35060. External Links: Link Cited by: §2, §2. Yu et al. (2018) W. Yu, Y. Gu, and Y. Li Efficient randomized algorithms for the fixed-precision low-rank matrix approximation. SIAM Journal on Matrix Analysis and Applications 39 (3), p. 1339–1359. External Links: Document, Link Cited by: §1, §2. Appendix A Proofs for Single-Approximation Certification This appendix proves Theorem 3.1 and Corollary 3.2. We give the oracle model explicitly, prove the joint Gaussian bound used by the certificate, and then establish the matching information bound. The Gaussian innovation argument below allows an arbitrary positive definite output covariance, so it also applies to the multiple-hypothesis construction for simultaneous certification. A.1 Oracle model and dimension-uniform risk Fix 0<g<ρ<10<g<ρ<1. The unknown matrix A∈ℝm×nA ^m× n is nonzero, and the supplied matrix P∈ℝm×mP ^m× m is an orthogonal projection: P=P⊤=P2P=P =P^2. Write q(A,P)=‖(Im−P)A‖F2/‖A‖F2q(A,P)=\|(I_m-P)A\|_F^2/\|A\|_F^2, and define ℋ0(P)=A≠0:q(A,P)≥ρ,ℋ1(P)=A≠0:q(A,P)≤ρ−g.H_0(P)=\A≠ 0:q(A,P)≥ρ\,~~H_1(P)=\A≠ 0:q(A,P)≤ρ-g\. The decision 11 means acceptance and the decision 00 means rejection. Neither decision is prescribed outside ℋ0(P)∪ℋ1(P)H_0(P) _1(P). A procedure receives (m,n,P,ρ,g)(m,n,P,ρ,g), has private randomness independent of A, and observes A only through calls v↦Av Av. Each call returns the full output vector. Query directions, stopping decisions, and the final decision are measurable functions of the supplied information, private randomness, and preceding query–response pairs. The procedure makes at most s calls on every run; equivalently, a procedure that stops earlier can be padded with unused zero queries. All oracle calls made by the procedure count, including any construction responses supplied for use in its decision. There is no additional free transcript depending on A. For a procedure ℳm,n,PM_m,n,P, define α(ℳm,n,P) α(M_m,n,P) =supA∈ℋ0(P)ℙAℳm,n,P=1, = _A _0(P)P_A\M_m,n,P=1\, β(ℳm,n,P) β(M_m,n,P) =supA∈ℋ1(P)ℙAℳm,n,P=0. = _A _1(P)P_A\M_m,n,P=0\. Here the probability concerns the procedure’s randomness for a fixed matrix, and a supremum over an empty hypothesis class is defined as zero. A family of procedures may depend on the known dimensions and projection. The dimension-uniform minimax risk is Rs(ρ,g)=infℳm,n,Psupm,n≥1P=P⊤=P2maxα(ℳm,n,P),β(ℳm,n,P).R_s(ρ,g)= _\M_m,n,P\ _ subarraycm,n≥ 1\\ P=P =P^2 subarray \α(M_m,n,P),β(M_m,n,P)\. (A.1) All procedures in the infimum obey the same budget s. The optimal budget is s⋆(δ,ρ,g)=mins≥1:Rs(ρ,g)≤δs (δ;ρ,g)= \s≥ 1:R_s(ρ,g)≤δ\. For upper bounds, P may instead result from an earlier construction stage: conditional on that stage, the proof applies to fresh independent validation probes. This conditional statement counts additional validation calls. It does not give a lower bound on additional calls when arbitrary construction observations have been supplied for free. A.2 A joint exponential moment bound For independent g1,…,gs∼(0,In)g_1,…,g_s (0,I_n), set Z(M)=1s∑i=1sgi⊤Mgi.Z(M)= 1s _i=1^sg_i Mg_i. All matrices in a comparison use these same probes. If M⪰0M 0 and tr(M)>0tr(M)>0, then Z(M)>0Z(M)>0 almost surely. Lemma A.1 (An exponential moment determined by two traces). Let U,V⪰0U,V 0, with tr(U)=a>0tr(U)=a>0 and tr(V)=b>0tr(V)=b>0. For z∼(0,In)z (0,I_n) and 0≤t<1/(2b)0≤ t<1/(2b), exp−tz⊤(U−V)z≤[(1+2ta)(1−2tb)]−1/2.E \-tz (U-V)z\≤[(1+2ta)(1-2tb)]^-1/2. When n≥2n≥ 2, equality is attained by U=auu⊤U=auu and V=bvv⊤V=bvv for orthogonal unit vectors u,vu,v. Proof. Let D=U−VD=U-V, and denote its positive eigenvalues by λi _i and its negative eigenvalues by −μj- _j, with λi,μj>0 _i, _j>0. Define p=∑iλi,r=∑jμj.p= _i _i,~~r= _j _j. Zero eigenvalues are omitted, and an empty sum is zero. Taking the trace gives p−r=a−bp-r=a-b. If Π− _- is the negative spectral projection of D, then r=−tr(Π−D)=tr(Π−V)−tr(Π−U)≤tr(V)=b.r=-tr( _-D)=tr( _-V)-tr( _-U) (V)=b. Indeed, the trace of a product of positive semidefinite matrices is nonnegative, and 0⪯Π−⪯In0 _- I_n. The positive spectral projection gives p≤ap≤ a in the same way. Thus pr≤abpr≤ ab, and every factor 1−2tμj1-2t _j is positive. For nonnegative xix_i, expansion gives ∏i(1+xi)≥1+∑ixi _i(1+x_i)≥ 1+ _ix_i. For nonnegative yjy_j with ∑jyj<1 _jy_j<1, induction gives ∏j(1−yj)≥1−∑jyj _j(1-y_j)≥ 1- _jy_j. Applying the two inequalities separately yields det(In+2tD) (I_n+2tD) =∏i(1+2tλi)∏j(1−2tμj) = _i(1+2t _i) _j(1-2t _j) ≥(1+2tp)(1−2tr) ≥(1+2tp)(1-2tr) =1+2t(a−b)−4t2pr =1+2t(a-b)-4t^2pr ≥1+2t(a−b)−4t2ab=(1+2ta)(1−2tb). ≥ 1+2t(a-b)-4t^2ab=(1+2ta)(1-2tb). (A.2) In particular, In+2tDI_n+2tD is positive definite. Orthogonal diagonalization preserves independent standard Gaussian coordinates. The one-dimensional Gaussian integral e−tλZ2=(1+2tλ)−1/2Ee^-tλ Z^2=(1+2tλ)^-1/2, valid when 1+2tλ>01+2tλ>0, therefore gives e−tz⊤Dz=det(In+2tD)−1/2.Ee^-tz Dz= (I_n+2tD)^-1/2. Combining this identity with (A.2) proves the bound. For the stated orthogonal rank-one pair, the only nonzero eigenvalues are a and −b-b, so every inequality is an equality. ∎ Lemma A.2 (Two-sided log-ratio concentration). Let B,C⪰0B,C 0 have positive traces. Define Ls=logZ(B)Z(C)−logtr(B)tr(C),I(u)=logcosh(u/2).L_s= Z(B)Z(C)- tr(B)tr(C),~~I(u)= (u/2). For every u>0u>0, ℙLs≤−u≤e−sI(u),ℙLs≥u≤e−sI(u).P\L_s≤-u\≤ e^-sI(u),~~P\L_s≥ u\≤ e^-sI(u). (A.3) No independence between Z(B)Z(B) and Z(C)Z(C) is required. Proof. Write B0=B/tr(B)B_0=B/tr(B), C0=C/tr(C)C_0=C/tr(C), and r=e−u∈(0,1)r=e^-u∈(0,1). The lower-tail event is ∑i=1sgi⊤(B0−rC0)gi≤0 _i=1^sg_i (B_0-rC_0)g_i≤ 0. For 0<t<1/(2r)0<t<1/(2r), exponential Markov and independence across probes give ℙLs≤−u≤∏i=1se−tgi⊤(B0−rC0)gi≤[(1+2t)(1−2tr)]−s/2,P\L_s≤-u\≤ _i=1^sEe^-tg_i (B_0-rC_0)g_i≤[(1+2t)(1-2tr)]^-s/2, where the second step uses Lemma A.1. The quadratic product is maximized at t=(1−r)/(4r)=(eu−1)/4t=(1-r)/(4r)=(e^u-1)/4, which belongs to the allowed interval. At this value, (1+2t)(1−2tr)=(1+r)24r=cosh2(u/2).(1+2t)(1-2tr)= (1+r)^24r= ^2(u/2). This proves the lower-tail bound. Interchanging B and C changes LsL_s into −Ls-L_s and proves the other bound. ∎ A.3 The Gaussian certificate For the supplied projection, set T=A⊤A,E=A⊤(Im−P)A,C=A⊤PA=T−E.T=A A,~~E=A (I_m-P)A,~~C=A PA=T-E. Orthogonality of P implies E,C⪰0E,C 0. Cache Y=[Ag1,…,Ags]Y=[Ag_1,…,Ag_s], so that q^=‖(Im−P)Y‖F2‖Y‖F2=Z(E)Z(T),q=tr(E)tr(T). q= \|(I_m-P)Y\|_F^2\|Y\|_F^2= Z(E)Z(T),~~q= tr(E)tr(T). Although the residual and captured output vectors are orthogonal for each probe, their squared norms need not be statistically independent. Their common Gaussian inputs are handled by Lemma A.2. For q∈(0,1)q∈(0,1), both E and C have positive trace, and ℓ(q^)−ℓ(q)=logZ(E)Z(C)−logtr(E)tr(C),ℓ(x)=logx1−x. ( q)- (q)= Z(E)Z(C)- tr(E)tr(C),~~ (x)= x1-x. Consequently, both tails of this log-odds difference satisfy (A.3). If q=0q=0, positive semidefiniteness gives E=0E=0, and q^=0 q=0 almost surely. If q=1q=1, then C=0C=0, and q^=1 q=1 almost surely. Let Δ=ℓ(ρ)−ℓ(ρ−g)>0,μ=ℓ(ρ)+ℓ(ρ−g)2. = (ρ)- (ρ-g)>0,~~μ= (ρ)+ (ρ-g)2. The Gaussian certificate accepts exactly when ∑i=1s‖(Im−P)Agi‖22≤eμ∑i=1s‖PAgi‖22. _i=1^s\|(I_m-P)Ag_i\|_2^2≤ e^μ _i=1^s\|PAg_i\|_2^2. (A.4) This formulation also covers q=0,1q=0,1 without taking logarithms at an endpoint. For an interior null instance q≥ρq≥ρ, acceptance implies ℓ(q^)−ℓ(q)≤−Δ/2 ( q)- (q)≤- /2. For an interior alternative q≤ρ−gq≤ρ-g, rejection implies ℓ(q^)−ℓ(q)>Δ/2 ( q)- (q)> /2. Hence both errors are at most e−sI(Δ/2)=exp[−slogcosh(Δ/4)].e^-sI( /2)= [-s ( /4)]. The endpoint instances are classified correctly almost surely. This proves the upper bound uniformly over the dimensions, matrix, and projection. A.4 The exact F tail and its prefactor Let Fs,sF_s,s be the ratio of two independent χs2 _s^2 random variables, and write ps(u)=ℙFs,s≤e−up_s(u)=P\F_s,s≤ e^-u\ for u>0u>0. The division by the common degrees of freedom cancels, so this is also the usual F distribution with degrees of freedom (s,s)(s,s). Lemma A.3 (Exact density and endpoint asymptotics). The random variable logFs,s F_s,s has density fs(z)=cse−sI(z),cs=Γ((s+1)/2)2πΓ(s/2),I(z)=logcosh(z/2).f_s(z)=c_se^-sI(z),~~c_s= ((s+1)/2)2 π\, (s/2),~~I(z)= (z/2). (A.5) In particular, ps(u)=cs∫u∞e−sI(t)t.p_s(u)=c_s _u^∞e^-sI(t)\,dt. (A.6) For every integer s≥1s≥ 1 and u>0u>0, 2csse−sI(u)≤ps(u)≤2csstanh(u/2)e−sI(u). 2c_sse^-sI(u)≤ p_s(u)≤ 2c_ss (u/2)e^-sI(u). (A.7) For each fixed u>0u>0, ps(u)∼e−sI(u)2πstanh(u/2)as s→∞.p_s(u) e^-sI(u) 2π s\, (u/2)~as s→∞. (A.8) Proof. Let X,WX,W be independent χs2 _s^2 variables. Substitute X=xwX=xw, W=wW=w into their joint gamma density. The Jacobian is w, and integration over w>0w>0 gives fF(x)=Γ(s)Γ(s/2)2xs/2−1(1+x)s,x>0.f_F(x)= (s) (s/2)^2 x^s/2-1(1+x)^s,~~x>0. With x=ezx=e^z, the density of the logarithm is therefore fs(z)=Γ(s)2sΓ(s/2)2cosh(z/2)−s.f_s(z)= (s)2^s (s/2)^2 (z/2)^-s. The duplication identity Γ(s)=2s−1Γ(s/2)Γ((s+1)/2)/π (s)=2^s-1 (s/2) ((s+1)/2)/ π gives (A.5). Its symmetry implies Fs,s−1=Fs,sF_s,s^-1 d=F_s,s and (A.6). The density is positive and continuous, so ps(u)>0p_s(u)>0 and psp_s is continuous for every finite u>0u>0. For t≥u>0t≥ u>0, I′(t)=12tanh(t/2)I (t)= 12 (t/2) is positive, nondecreasing, and at most 1/21/2. Thus I(u)+I′(u)(t−u)≤I(t)≤I(u)+12(t−u).I(u)+I (u)(t-u)≤ I(t)≤ I(u)+ 12(t-u). Integrating the two exponential bounds proves (A.7). For the sharp prefactor, set t=u+y/st=u+y/s in (A.6): ps(u)=csse−sI(u)∫0∞exp−s[I(u+y/s)−I(u)]y.p_s(u)= c_sse^-sI(u) _0^∞ \-s[I(u+y/s)-I(u)]\\,dy. For each y≥0y≥ 0, the integrand tends to e−I′(u)ye^-I (u)y. Convexity bounds it by this same integrable function for every s. Dominated convergence therefore gives the integral limit 1/I′(u)=2/tanh(u/2)1/I (u)=2/ (u/2). Stirling’s formula gives Γ((s+1)/2)Γ(s/2)=s/2[1+O(s−1)],cs∼s22π. ((s+1)/2) (s/2)= s/2\,[1+O(s^-1)],~~c_s s2 2π. Substitution proves (A.8). ∎ For two orthogonal rank-one energy forms, their normalized estimates are independent χs2/s _s^2/s variables. Hence their log-ratio has exactly the density above. It follows that I(u)I(u) is the sharp exponential rate in (A.3). The general finite-sample calibration remains the exponential bound; the exact F tail is used below as a testing lower bound. A.5 Gaussian innovations under adaptive queries Lemma A.4 (A covariance-independent transcript simulator). Fix m,n,sm,n,s, and let Σ∈ℝm×m ^m× m be positive definite. Suppose the columns of A are independent with law (0,Σ/n)N(0, /n). Consider an adaptive forward-query procedure with at most s queries. Its supplied information is fixed and independent of Σ and A; its private random seed is independent of A and has the same law for every Σ . Its complete transcript can be generated from the seed and s independent vectors with law (0,Σ)N(0, ) through a measurable map that does not depend on Σ . The transcript includes queries, responses, stopping, and the final output. Proof. Draw all private randomness as a seed R before the first query; it is independent of A. The query rule is then deterministic conditional on R and the observed history. After t queries define Vt=[v1,…,vt],Yt=[Av1,…,Avt],Mt=YtVt†,Πt=In−VtVt†,V_t=[v_1,…,v_t],~~Y_t=[Av_1,…,Av_t],~~M_t=Y_tV_t ,~~ _t=I_n-V_tV_t , where † denotes the Moore–Penrose pseudoinverse. The matrix Πt _t projects onto the orthogonal complement of the previous query span. Since Yt=AVtY_t=AV_t, one has Mt=A(In−Πt)M_t=A(I_n- _t), so MtM_t is the known action on that span. Set M0=0M_0=0, Π0=In _0=I_n, and let ℱt=σ(R,Vt,Yt)F_t=σ(R,V_t,Y_t). We prove inductively that, under each fixed covariance, the regular conditional law is ℒ(A∣ℱt)=ℒ(Mt+1nΣ1/2ZΠt|ℱt),L(A _t)=L (M_t+ 1 n ^1/2Z _t\, |\,F_t ), (A.9) where the entries of the auxiliary matrix Z∈ℝm×nZ ^m× n are independent standard normals, independent of ℱtF_t. The equality denotes conditional distributions, rather than a single auxiliary matrix shared across different values of t. At t=0t=0, it is the assumed matrix prior. Conditional on ℱtF_t, the next query v is fixed. If d=‖Πtv‖2=0d=\| _tv\|_2=0, then Av=MtvAv=M_tv is already determined. This query supplies no additional condition on the residual law, and (A.9) remains valid. Otherwise put u=Πtv/du= _tv/d. Under the conditional representation, Av=Mtv+dnξ,ξ=Σ1/2Zu∼(0,Σ).Av=M_tv+ d nξ,~~ξ= ^1/2Zu (0, ). The vector ξ and the matrix Σ1/2Z(Πt−uu⊤) ^1/2Z( _t-u ) are jointly Gaussian and independent. To verify this, for every vector w in the range of Πt−uu⊤ _t-u , their component covariances are determined by Cov(Σ1/2Zu,Σ1/2Zw)=Σ(u⊤w)=0Cov( ^1/2Zu, ^1/2Zw)= (u w)=0. Thus observing the new response reveals ξ and leaves the orthogonal Gaussian component unchanged. The posterior mean and residual projection become Mt+1=Mt+1nξu⊤,Πt+1=Πt−uu⊤.M_t+1=M_t+ 1 nξ u ,~~ _t+1= _t-u . (A.10) These are precisely the known action on the enlarged query span and its orthogonal complement. The independent remaining Gaussian component proves (A.9) at step t+1t+1. Adaptive selection imposes no additional constraint here: conditional on the current history and seed, the selected query is a known vector. A simulator now draws ξ1,…,ξs _1,…, _s independently from (0,Σ)N(0, ), together with R. It follows the procedure’s query rule, returns MtvM_tv for a redundant query, and for a new direction returns Mtv+dξj/nM_tv+d _j/ n, using the next unused vector and updating the known action by (A.10). Early stopping leaves unused vectors. The induction proves equality in law of the full transcripts. Every step of the simulation uses only the supplied information, the seed, the generated history, and the input vectors ξj _j; it never uses Σ . ∎ In particular, if Σ is one of finitely many unknown covariances, this lemma gives a single hypothesis-independent simulation kernel. Any decision from the transcript is consequently a decision based on at most s independent covariance observations and an independent seed. It cannot have smaller Bayes error than the optimal test based on those observations. This is the full-vector information reduction underlying (1); it does not restrict the original procedure to scalar energy statistics. A.6 Two covariance hypotheses and finite-dimensional leakage Proposition A.5 (Finite-dimensional lower bound). Fix m=2m=2, P=diag(0,1)P=diag(0,1), and integers n≥s≥1n≥ s≥ 1. Every procedure using at most s adaptive queries satisfies, for each η>0η>0, maxα(ℳ2,n,P),β(ℳ2,n,P)≥[ps(Δ/2+η)−pn(η)1−pn(η)]+, \α(M_2,n,P),β(M_2,n,P)\≥ [ p_s( /2+η)-p_n(η)1-p_n(η) ]_+, (A.11) where [x]+=maxx,0[x]_+= \x,0\ and Δ=ℓ(ρ)−ℓ(ρ−g) = (ρ)- (ρ-g). Proof. Set λ0=ℓ(ρ)+η,λ1=ℓ(ρ−g)−η,Σh=diag(eλh/2,e−λh/2). _0= (ρ)+η,~~ _1= (ρ-g)-η,~~ _h=diag(e _h/2,e^- _h/2). Under prior hQ_h, draw the columns of A independently from (0,Σh/n)N(0, _h/n). The supplied dimensions and projection are identical under the two priors. Applying Lemma A.4 under both hypotheses gives the same simulation map from s independent vectors ξi∼(0,Σh) _i (0, _h). We first compute the optimal equal-prior error for these vectors. Write μ=λ0+λ12,ω=λ0−λ12=Δ/2+η,S1=∑i=1sξi12,S2=∑i=1sξi22.μ= _0+ _12,~~ω= _0- _12= /2+η,~~S_1= _i=1^s _i1^2,~~S_2= _i=1^s _i2^2. Both covariances have determinant one. If fhf_h is the joint density of the observations under hypothesis h, direct substitution into the Gaussian densities gives logf0f1 f_0f_1 =−12[(e−λ0/2−e−λ1/2)S1+(eλ0/2−eλ1/2)S2] =- 12 [(e^- _0/2-e^- _1/2)S_1+(e _0/2-e _1/2)S_2 ] =sinh(ω/2)(e−μ/2S1−eμ/2S2). = (ω/2) (e^-μ/2S_1-e^μ/2S_2 ). Under equal prior probabilities, selecting the larger density minimizes the average error pointwise. The test therefore chooses hypothesis 11, corresponding to acceptance, when S1/S2≤eμS_1/S_2≤ e^μ. Ties have probability zero. Since the coordinates are independent under either covariance, S1S2=eλhFs,s. S_1S_2 d=e _hF_s,s. The error under hypothesis 00 is ℙFs,s≤e−ω=ps(ω)P\F_s,s≤ e^-ω\=p_s(ω). The error under hypothesis 11 is ℙFs,s>eω=ps(ω)P\F_s,s>e^ω\=p_s(ω), by reciprocal symmetry and continuity. Thus the optimal average error equals ps(Δ/2+η).p_s( /2+η). (A.12) An independent private seed cannot improve this value: conditional on each seed, the same pointwise density comparison remains optimal. The transcript simulation therefore bounds the prior-averaged error of every oracle procedure below by (A.12). The Gaussian matrix priors have not been conditioned to lie in the certification regions. Under hQ_h, their realized error odds satisfy q(A,P)1−q(A,P)=∥A1,:∥22∥A2,:∥22=eλhFn,n. q(A,P)1-q(A,P)= \|A_1,:\|_2^2\|A_2,:\|_2^2 d=e _hF_n,n. Consequently, the two leakage probabilities are exactly 0q<ρ=pn(η),1q>ρ−g=pn(η).Q_0\q<ρ\=p_n(η),~~Q_1\q>ρ-g\=p_n(η). (A.13) Let ε=maxα,β = \α,β\ be the procedure’s worst error on the required regions for this dimension and projection. Its error for each fixed matrix is at most ε inside the intended region and at most one outside. Each prior-averaged error is therefore at most (1−pn(η))ε+pn(η)(1-p_n(η)) +p_n(η). Combining this with (A.12), rearranging, and using ε≥0 ≥ 0 proves (A.11). The denominator is positive because pn(η)<1/2p_n(η)<1/2. ∎ Keeping the priors Gaussian until after the simulation is essential to this argument. Conditioning them on the certification regions at the outset would change their Gaussian conditional laws. Equation (A.13) instead quantifies the discrepancy after the information reduction has been applied. A.7 Minimax risk, confidence asymptotics, and the small gap Proof of Theorem 3.1. The certificate (A.4) gives the upper bound in every dimension. For the lower bound, fix s≥1s≥ 1 and η>0η>0. Proposition A.5 applies uniformly to every procedure in each dimension n≥sn≥ s. Lemma A.3 gives pn(η)→0p_n(η)→ 0 as n→∞n→∞. Taking the supremum over input dimensions in (A.1), followed by the infimum over procedure families, therefore yields Rs(ρ,g)≥ps(Δ/2+η).R_s(ρ,g)≥ p_s( /2+η). Continuity of psp_s permits η↓0η 0. We obtain ps(Δ/2)≤Rs(ρ,g)≤e−sJ,J=logcosh(Δ/4)>0.p_s( /2)≤ R_s(ρ,g)≤ e^-sJ,~~J= ( /4)>0. (A.14) Put L=log(1/δ)L= (1/δ). The constructive upper bound gives s⋆(δ,ρ,g)≤⌈L/J⌉s (δ;ρ,g)≤ L/J . The lower bound is positive at every fixed s, so s⋆(δ,ρ,g)→∞s (δ;ρ,g)→∞ as δ↓0δ 0. If Rs(ρ,g)≤δR_s(ρ,g)≤δ, the lower estimate in (A.7) implies sJ≥L+log2css=L−12logs−12log(2π)+O(s−1).sJ≥ L+ 2c_ss=L- 12 s- 12 (2π)+O(s^-1). At s=s⋆s=s , the constructive upper bound implies logs⋆=O(logL)=o(L) s =O( L)=o(L). Dividing by L and combining the upper and lower inequalities proves limδ↓0s⋆(δ,ρ,g)log(1/δ)=1logcosh(Δ/4). _δ 0 s (δ;ρ,g) (1/δ)= 1 ( /4). ∎ For a fixed interior target ρ, Taylor expansion gives Δ=gρ(1−ρ)+Oρ(g2),logcosh(Δ/4)=Δ232+O(Δ4). = gρ(1-ρ)+O_ρ(g^2),~~ ( /4)= ^232+O( ^4). The precise small-gap consequence is the iterated limit limg↓0g2[limδ↓0s⋆(δ,ρ,g)log(1/δ)]=32ρ2(1−ρ)2. _g 0g^2 [ _δ 0 s (δ;ρ,g) (1/δ) ]=32ρ^2(1-ρ)^2. Thus the expression 32ρ2(1−ρ)2g−2log(1/δ)32ρ^2(1-ρ)^2g^-2 (1/δ) describes the leading cost when the confidence limit is taken before the gap limit. No uniform assertion over arbitrary joint limits of g,δg,δ is needed for this conclusion. Remark A.6 (Why the dimension supremum matters). For a fixed input dimension n, querying all n coordinate vectors recovers A exactly. With uncharged arithmetic, every supplied projection can then be certified without statistical error. The positive risk lower bound (A.14) consequently concerns a guarantee uniform over input dimensions. In its proof, n→∞n→∞ is taken at fixed s,ηs,η, and only afterward is η↓0η 0 taken. It is not a positive lower bound for each fixed n once s≥ns≥ n. A.8 Mean-square output error Proof of Corollary 3.2. Let K=[xx⊤]⪰0K=E[x ] 0 be known and finite, and assume tr(AKA⊤)>0tr(AKA )>0. For every fixed matrix M, linearity of expectation gives ‖Mx‖22=tr(Mxx⊤M⊤)=tr(MKM⊤)=‖MK1/2‖F2.E\|Mx\|_2^2=Etr(Mxx M )=tr(MKM )=\|MK^1/2\|_F^2. Taking M=(Im−P)AM=(I_m-P)A and M=AM=A yields, with B=AK1/2≠0B=AK^1/2≠ 0, qK(A,P)=‖(Im−P)Ax‖22‖Ax‖22=‖(Im−P)B‖F2‖B‖F2.q_K(A,P)= E\|(I_m-P)Ax\|_2^2E\|Ax\|_2^2= \|(I_m-P)B\|_F^2\|B\|_F^2. (A.15) The expectation is over the input distribution, whereas the certification error probability is over the procedure’s probes. In particular, (A.15) is a ratio of expectations, rather than a pointwise relative-error guarantee. Every forward query to B can be implemented as Bv=A(K1/2v)Bv=A(K^1/2v) with one forward query to A. Computing with the known K is part of the uncharged arithmetic in this query model. Therefore any Frobenius certification procedure can be simulated for the functional problem with the same hard budget. In particular, Gaussian queries v=giv=g_i to B become K1/2giK^1/2g_i queries to A, proving the upper bounds for every given K. For the minimax statement, define the functional risk by the same suprema as in (A.1), with an additional supremum over known positive semidefinite K satisfying the positive denominator condition. The procedure receives K. The query simulation shows that this risk is no larger than the Frobenius risk: apply procedures approaching its infimum to B and let their excess risk tend to zero. Conversely, restricting the functional instances to K=InK=I_n recovers exactly the Frobenius problem with the same supplied information and query model. The functional risk is therefore no smaller than Rs(ρ,g)R_s(ρ,g), proving equality and the common high-confidence constant. No Gaussian assumption on the actual inputs x is used. ∎ Remark A.7 (A prescribed second moment). The minimax equality above takes the worst case over known second moments, not over matrices for one fixed second moment. For example, if a prescribed K has rank r, choose a known orthonormal basis w1,…,wrw_1,…,w_r of its range. The r queries Aw1,…,AwrAw_1,…,Aw_r determine AK1/2AK^1/2 exactly, and hence determine (A.15) for every known projection. A rank-one second moment can thus be certified exactly with one query. This is consistent with the uniform result, whose instance class contains K=InK=I_n for arbitrarily large n. Appendix B Proofs for Validation Reuse and the Shared-Energy Upper Bound This appendix proves the pathwise reductions and the upper bound in Theorem 4.1. The matching information lower bound is established in Appendix C. All matrices below are real. For a nonzero positive semidefinite matrix T and residual energies 0⪯E⪯T0 E T, write Z(B)=1s∑j=1sgj⊤Bgj,qE=trEtrT,q^E=Z(E)Z(T),gj∼iidN(0,In).Z(B)= 1s _j=1^sg_j Bg_j,~~q_E= trEtrT,~~ q_E= Z(E)Z(T),~g_j N(0,I_n). The definition of Z applies to any symmetric matrix. Since T≠0T≠ 0, Z(T)>0Z(T)>0 almost surely. Both qEq_E and q^E q_E belong to [0,1][0,1]. The notation ∥⋅∥∗\|·\|_* denotes the nuclear norm. The complete candidate family and T are independent of the validation probes. They may depend on the operator and on independent construction randomness. All statements can first be proved conditionally on these quantities and then averaged. Throughout the pathwise arguments, ρ∈(0,1)ρ∈(0,1) and g∈(0,ρ)g∈(0,ρ) are fixed before observing the sketch. A required decision is rejection at qE≥ρq_E≥ρ and acceptance at qE≤ρ−gq_E≤ρ-g; no decision is prescribed between these regions. B.1 Two boundary candidates per chain Lemma B.1 (Finite-family boundary reduction). Let a finite candidate family be covered by W Loewner chains, and apply the same threshold rule q^E≤θ q_E≤θ to every candidate, where θ is fixed independently of the sketch. There is a set of at most 2W2W candidates, independent of the sketch, such that every required decision is correct if and only if every required decision at these candidates is correct. Proof. Fix a chain. If it contains any member with qE≥ρq_E≥ρ, choose a Loewner-minimal such member EbadE^bad. If it contains any member with qE≤ρ−gq_E≤ρ-g, choose a Loewner-maximal such member EgoodE^good. These extrema exist because the chain is finite. They depend only on the fixed matrices and the true trace ratios. Their identities need not be known to the procedure. If a bad member E is accepted, then Ebad⪯E^bad E, hence Z(Ebad)≤Z(E)Z(E^bad)≤ Z(E) and q^Ebad≤q^E≤θ q_E^bad≤ q_E≤θ. Thus the bad boundary is also accepted. Conversely, an accepted bad boundary is itself a false acceptance. Likewise, if a good member E is rejected, then E⪯EgoodE E^good, giving q^Egood≥q^E>θ q_E^good≥ q_E>θ; the good boundary is rejected as well. The converse again holds because the boundary is a member of the good set. Collecting the boundaries of the W chains proves the claim. Empty bad or good sets contribute no boundary, and repeated boundaries can be removed. ∎ On a decreasing path, these are the last unsafe member of its prefix and the first sufficiently accurate member of its suffix. If only false acceptance is controlled, one boundary per chain suffices. Loewner ordering is essential to the argument: a decrease in the trace alone does not imply a decrease in Z(E)Z(E) for each realized sketch. For a countable family, choose increasing finite subsets whose union is the whole family. Their intersections with the original chain cover still have width at most W. If an error bound with a fixed budget and threshold is uniform in the finite-subset size, it extends to the whole family: the events that some required decision in a finite subset is wrong increase to the event that some required decision in the full family is wrong. Continuity of probability from below therefore gives exactly the same bound. This argument neither requires global boundary extrema to exist nor introduces a sum over subset sizes. B.2 The exact confidence constant for a fixed number of paths Let ℓ(x)=logx1−x,Δ=ℓ(ρ)−ℓ(ρ−g)>0,θlog=[1+exp(−ℓ(ρ)+ℓ(ρ−g)2)]−1. (x)= x1-x,~~ = (ρ)- (ρ-g)>0,~~ _ = [1+ \! (- (ρ)+ (ρ-g)2 ) ]^-1. This is the midpoint in log-odds coordinates. It generally differs from the arithmetic midpoint ρ−g/2ρ-g/2 used below. Proposition B.2 (Fixed-width high-confidence calibration). For any finite or countable family of width at most W, accepting when q^E≤θlog q_E≤ _ gives ℙat least one required decision is incorrect≤2Wexp−slogcosh(Δ/4).P\at least one required decision is incorrect\≤ 2W \-s ( /4)\. (B.1) Consequently, for fixed W,ρ,gW,ρ,g, limδ↓0ssim⋆(δ,ρ,g,W)log(1/δ)=1logcosh(Δ/4). _δ 0 s _sim(δ;ρ,g,W) (1/δ)= 1 ( /4). (B.2) Proof. For a fixed bad boundary with 0<qE<10<q_E<1, acceptance requires ℓ(q^E)−ℓ(qE)≤ℓ(θlog)−ℓ(ρ)=−Δ/2. ( q_E)- (q_E)≤ ( _ )- (ρ)=- /2. For a fixed good boundary with 0<qE<10<q_E<1, rejection requires ℓ(q^E)−ℓ(qE)>ℓ(θlog)−ℓ(ρ−g)=Δ/2. ( q_E)- (q_E)> ( _ )- (ρ-g)= /2. The single-candidate Gaussian bound from Section 3 controls each of these events by exp−slogcosh(Δ/4) \-s ( /4)\. At qE=0q_E=0 or qE=1q_E=1, the sampled ratio equals the true ratio almost surely, so the corresponding error probability is zero. Lemma B.1 and a union bound over at most 2W2W boundaries prove (B.1) for finite families. The finite-subset argument above proves the countable case. In particular, the integer budget ⌈log(2W/δ)logcosh(Δ/4)⌉ (2W/δ) ( /4) is sufficient. The single-candidate minimax lower bound of Theorem 3.1 applies because singleton families are included among families of width at most W. For fixed W, these upper and lower bounds have the same leading coefficient of log(1/δ) (1/δ), proving (B.2). ∎ B.3 Gaussian concentration facts We first record the quadratic-form bounds used below, including their normalizations. Lemma B.3 (Gaussian quadratic forms). For a fixed real symmetric matrix B and u>0u>0, ℙ|Z(B)−trB|>2∥B∥Fu/s+2∥B∥opu/s≤2e−u.P \|Z(B)-trB|>2\|B\|_F u/s+2\|B\|_opu/s \≤ 2e^-u. (B.3) If B⪰0B 0, its lower tail also satisfies ℙZ(B)<trB−2∥B∥Fu/s≤e−u.P \Z(B)<trB-2\|B\|_F u/s \≤ e^-u. (B.4) Proof. Let λ1,…,λn _1,…, _n be the eigenvalues of B. For 0≤θ<s/(2‖B‖op)0≤θ<s/(2\|B\|_op), independence and the Gaussian moment-generating function give logexpθ(Z(B)−trB)=s2∑k=1n[−2θλks−log(1−2θλks)]. \θ(Z(B)-trB)\= s2 _k=1^n [- 2θ _ks- (1- 2θ _ks ) ]. Using −x−log(1−x)≤x2/[2(1−|x|)]-x- (1-x)≤ x^2/[2(1-|x|)] for |x|<1|x|<1 yields logexpθ(Z(B)−trB)≤θ2‖B‖F2/s1−2θ‖B‖op/s. \θ(Z(B)-trB)\≤ θ^2\|B\|_F^2/s1-2θ\|B\|_op/s. The same inequality applies to −B-B. The exponential Markov bound, with θ=u‖B‖F/s+2‖B‖opu/s,θ= u\|B\|_F/ s+2\|B\|_op u/s, gives each one-sided bound with threshold 2‖B‖Fu/s+2‖B‖opu/s2\|B\|_F u/s+2\|B\|_opu/s and probability e−ue^-u. The case B=0B=0 is immediate. Summing the two tails proves (B.3). When B⪰0B 0, the inequality x−log(1+x)≤x2/2x- (1+x)≤ x^2/2 for x≥0x≥ 0 instead gives logexp−θ(Z(B)−trB)≤θ2‖B‖F2/s,θ≥0. \-θ(Z(B)-trB)\≤θ^2\|B\|_F^2/s,~~θ≥ 0. Optimizing the exponential Markov bound proves (B.4). ∎ We also use the Gaussian singular-value inequalities in ([)Corollary 5.35 and its proof]vershynin2012nonasymptotic: if G0∈ℝh×sG_0 ^h× s has independent standard Gaussian entries, then, for every t>0t>0, ℙ∥G0∥op>s+h+2t \\|G_0\|_op> s+ h+ 2t\ ≤e−t, ≤ e^-t, (B.5) ℙσmin(G0)<s−h−2t \ _ (G_0)< s- h- 2t\ ≤e−t(s≥h). ≤ e^-t~~(s≥ h). (B.6) In (B.6), σmin _ is the smallest of the h singular values. The cited proof combines the Gaussian comparison bound of Theorem 5.32 with the one-sided Gaussian concentration inequality of Proposition 5.34, yielding the individual tail probabilities displayed above. In the proof below the lower bound is invoked only when its right-hand threshold is positive; otherwise positive semidefiniteness alone controls the lower covariance deviation. B.4 Uniform concentration under a shared energy envelope Proposition B.4 (Uniform concentration for a finite family). Let M,s≥1M,s≥ 1 be integers and let 0<α<10<α<1. Suppose that T⪰0T 0, trT>0trT>0, and 0⪯Ei⪯T0 E_i T for 1≤i≤M1≤ i≤ M, with all matrices independent of the Gaussian validation probes. Set HM(α)=log(2M)+log(5/α).H_M(α)= (2M)+ (5/α). Then ℙmaxi≤M|q^i−qi|≤min1,16HM(α)/s≥1−α.P \ _i≤ M| q_i-q_i|≤ \1,16 H_M(α)/s\ \≥ 1-α. In particular, s≥256HM(α)/ϵ2s≥ 256H_M(α)/ε^2 guarantees simultaneous additive accuracy ϵε. This proves (2) with the absolute constant C=16C=16. Proof of Proposition B.4. Both ratios are unchanged by a common scaling of all matrices, so assume trT=1trT=1. As T≠0T≠ 0, the denominator Z(T)Z(T) is strictly positive almost surely. The inequality 0⪯Ei⪯T0 E_i T also gives 0≤qi,q^i≤10≤ q_i, q_i≤ 1. On the support of T, write Ei=T1/2KiT1/2,0⪯Ki⪯I,qi=trEi.E_i=T^1/2K_iT^1/2,~~0 K_i I,~~q_i=trE_i. This factorization remains valid for singular T: a vector in the kernel of T lies in the kernel of every EiE_i, and KiK_i can be set to zero on that kernel. Define Fi=Ei−qiT=T1/2(Ki−qiI)T1/2.F_i=E_i-q_iT=T^1/2(K_i-q_iI)T^1/2. Then trFi=0trF_i=0, ‖Ki−qiI‖op≤1\|K_i-q_iI\|_op≤ 1, and q^i−qi=Z(Fi)Z(T). q_i-q_i= Z(F_i)Z(T). Deterministic spectral decomposition. Choose an integer r≥1r≥ 1, diagonalize T, and put its largest h=min(r,n)h= (r,n) eigenvalues in a head block THT_H and the remaining eigenvalues in a tail block TLT_L. The orthogonal change of basis preserves the distribution of the Gaussian probes. If r<nr<n, the eigenvalue ordering and trT=1trT=1 imply ‖TL‖op≤1r+1≤1r.\|T_L\|_op≤ 1r+1≤ 1r. If r≥nr≥ n, the tail and all cross blocks are empty; all bounds for those blocks below are interpreted as zero. This convention allows us to choose r without assuming that the ambient dimension is large. For any symmetric contraction L and PSD matrix D, ‖D1/2LD1/2‖∗ \|D^1/2LD^1/2\|_* ≤‖D1/2‖F‖LD1/2‖F≤trD, ≤\|D^1/2\|_F\|LD^1/2\|_F , ‖D1/2LD1/2‖F2 \|D^1/2LD^1/2\|_F^2 ≤‖D‖optr(DL2)≤‖D‖optrD. ≤\|D\|_optr(DL^2)≤\|D\|_optrD. Applying these inequalities to the principal blocks of Ki−qiIK_i-q_iI gives ‖Fi,HH‖∗≤1,‖Fi,LL‖F2≤1/r,‖Fi,LL‖op≤1/r.\|F_i,H\|_*≤ 1,~~\|F_i,L\|_F^2≤ 1/r,~~\|F_i,L\|_op≤ 1/r. (B.7) The cross block has a sharper bound because KiK_i is a positive contraction. Taking the head principal block of Ki−Ki2⪰0K_i-K_i^2 0 shows that Ki,HLKi,LH⪯Ki,HH−Ki,HH2⪯14I.K_i,HLK_i,LH K_i,H-K_i,H^2 14I. Since T is block diagonal, Fi,HL=Ei,HLF_i,HL=E_i,HL, and therefore ‖Fi,HL‖F2 \|F_i,HL\|_F^2 =tr(TH1/2Ki,HLTLKi,LHTH1/2) =tr (T_H^1/2K_i,HLT_LK_i,LHT_H^1/2 ) ≤‖TL‖optr(THKi,HLKi,LH)≤14r. ≤\|T_L\|_optr (T_HK_i,HLK_i,LH )≤ 14r. None of these estimates requires EiE_i and T to commute. Uniform control of the head. Let GHG_H and GLG_L contain the corresponding rows of the probe matrix. For t>0t>0, set L0=log(2M)+t,a=r+2ts,b=L0rs.L_0= (2M)+t,~~a= r+ 2t s,~~b= L_0rs. By (B.5)–(B.6) and h≤rh≤ r, an event ℋH of probability at least 1−2e−t1-2e^-t satisfies ‖GH‖op≤s(1+a),‖GHGH⊤/s−Ih‖op≤2a+a2.\|G_H\|_op≤ s(1+a),~~ \|G_HG_H /s-I_h \|_op≤ 2a+a^2. (B.8) For completeness, if a<1a<1, then s>r≥hs>r≥ h and the lower singular-value bound gives λmin(GHGH⊤/s)≥(1−a)2 _ (G_HG_H /s)≥(1-a)^2. If a≥1a≥ 1, its lower covariance deviation is at most 11, which is already bounded by 2a+a22a+a^2. Thus (B.8) does not require s≥rs≥ r. On ℋH, (B.7) implies, simultaneously for all candidates, |tr(Fi,HH(GHGH⊤/s−Ih))|≤2a+a2. |tr (F_i,H(G_HG_H /s-I_h) ) |≤ 2a+a^2. Finite-family control of the tail. Apply Lemma B.3 to each Fi,LLF_i,L, with u=L0u=L_0. Equation (B.7) and a union bound show that maxi≤M|1str(GL⊤Fi,LLGL)−trFi,LL|≤2b+2b _i≤ M | 1str(G_L F_i,LG_L)-trF_i,L |≤ 2 b+2b except on an event of probability at most 2Me−L0=e−t2Me^-L_0=e^-t. Conditional control of the cross term. Conditional on GHG_H, each cross contribution Ci=2str(GH⊤Fi,HLGL)C_i= 2str(G_H F_i,HLG_L) is a centered Gaussian random variable, because GLG_L is independent of GHG_H. Its conditional variance satisfies Var(Ci∣GH) (C_i G_H) =4s2‖Fi,LHGH‖F2 = 4s^2\|F_i,LHG_H\|_F^2 ≤4s2‖Fi,HL‖F2‖GH‖op2≤(1+a)2rson ℋ. ≤ 4s^2\|F_i,HL\|_F^2\|G_H\|_op^2≤ (1+a)^2rs~~on H. Consequently, for every realization of GHG_H in ℋH, a conditional Gaussian tail bound and a union bound imply ℙmaxi≤M|Ci|>(1+a)2b|GH≤2Me−L0=e−t.P \ _i≤ M|C_i|>(1+a) 2b\; |\;G_H \≤ 2Me^-L_0=e^-t. Integrating this conditional bound shows that the cross event can fail inside ℋH with probability at most e−te^-t. No independence across candidates is used. Since trFi=0trF_i=0, the centered head, centered tail, and cross contributions sum to Z(Fi)Z(F_i). Combining the preceding events gives maxi≤M|Z(Fi)|≤B:=2a+a2+2b+2b+(1+a)2b _i≤ M|Z(F_i)|≤ B:=2a+a^2+2 b+2b+(1+a) 2b (B.9) with probability at least 1−4e−t1-4e^-t. The denominator. Because T⪰0T 0 and ‖T‖F≤trT=1\|T\|_F =1, (B.4) gives Z(T)≥1−2t/sZ(T)≥ 1-2 t/s except on an event of probability at most e−te^-t. Thus, whenever s>4ts>4t, maxi≤M|q^i−qi|≤B1−2t/s _i≤ M| q_i-q_i|≤ B1-2 t/s (B.10) with probability at least 1−5e−t1-5e^-t. Choice of the split and the explicit constant. Set m=log(2M),r=⌈m⌉,t=log(5/α),H=m+t=HM(α).m= (2M),~~r= m ,~~t= (5/α),~~H= m+t=H_M(α). In particular, r≥1r≥ 1 and t>1t>1. Define x=r+2t+(m+t)/rs.x= r+2t+(m+t)/rs. The ceiling causes no dimension-dependent remainder: since r≤m+1r≤ m+1, m/r≤m/r≤ m, and t/r≤t/r≤ t, x≤2m+1+3ts≤4Hs.x≤ 2 m+1+3ts≤ 4Hs. The empty-tail convention covers r≥nr≥ n. Let h0=(r+2t)/sh_0=(r+2t)/s, so that x=h0+bx=h_0+b and a2≤2h0a^2≤ 2h_0. The square-root terms in (B.9) are at most (2+32)x(2+3 2) x. Moreover, a2b≤2h0b≤xa 2b≤ 2 h_0b≤ x, while a2≤2xa^2≤ 2x and 2b≤2x2b≤ 2x. Hence B≤(2+32)x+5x≤(4+62)H/s+20H/s.B≤(2+3 2) x+5x≤(4+6 2) H/s+20H/s. (B.11) Put z=H/sz= H/s. If s≥256Hs≥ 256H, then z≤1/16z≤ 1/16 and t/s≤z t/s≤ z. Equations (B.10) and (B.11) yield maxi|q^i−qi|≤(4+62)z+20z21−2z≤4+62+20/161−2/16z<16z. _i| q_i-q_i|≤ (4+6 2)z+20z^21-2z≤ 4+6 2+20/161-2/16\,z<16z. The failure probability is at most 5e−t=α5e^-t=α. If s<256Hs<256H, then 16H/s>116 H/s>1 and the desired bound is deterministic, since both ratios lie in [0,1][0,1]. Together these cases prove the stated bound with min1,16HM(α)/s \1,16 H_M(α)/s\. ∎ B.5 Applying uniform concentration to the boundary family We now use the arithmetic midpoint θadd=ρ−g/2. _add=ρ-g/2. This choice maximizes the smaller additive distance to the two promise endpoints. It is used for the additive-gap query bound, whereas θlog _ was used for the exact high-confidence coefficient. Both rules solve the same certification task. Proposition B.5 (An explicit simultaneous-certification budget). Let 0<ρ<10<ρ<1, 0<g<ρ0<g<ρ, 0<δ<10<δ<1, and let the independent candidate family have width at most W. Accepting when q^E≤ρ−g/2 q_E≤ρ-g/2 makes every required decision correct with probability at least 1−δ1-δ whenever s≥2304g2[log(4W)+log(5/δ)].s≥ 2304g^2 [ (4W)+ (5/δ) ]. (B.12) This proves the upper bound in Theorem 4.1; the smaller gap range and ρ-dependent constants in that theorem concern the matching lower bound, not this sufficient budget. The constant 2304=4822304=48^2 comes from requiring the estimation error 16HM(δ)/s16 H_M(δ)/s to be at most g/3g/3. Proof. For a finite family, form the boundary set in Lemma B.1. If it is empty, there are no required decisions. Otherwise let its cardinality be M≤2WM≤ 2W. Apply Proposition B.4 once to the entire boundary set, with α=δα=δ. Since HM(δ)≤log(4W)+log(5/δ),H_M(δ)≤ (4W)+ (5/δ), condition (B.12) implies 16HM(δ)/s≤g/316 H_M(δ)/s≤ g/3. Thus, with probability at least 1−δ1-δ, every boundary estimate has absolute error at most g/3g/3. For each existing bad boundary, q^Ebad≥qEbad−g/3≥ρ−g/3>ρ−g/2, q_E^bad≥ q_E^bad-g/3≥ρ-g/3>ρ-g/2, so it is rejected. For each existing good boundary, q^Egood≤qEgood+g/3≤ρ−2g/3<ρ−g/2, q_E^good≤ q_E^good+g/3≤ρ-2g/3<ρ-g/2, so it is accepted. The strict slack covers both promise endpoints without any argument about ties. The boundary reduction then proves simultaneous correctness for the finite family. For a countable family, apply this same budget and threshold to every finite subset in an increasing exhaustion. Each subset still has at most 2W2W boundary candidates, so its error probability is at most δ, independently of subset size. The increasing error events and continuity of probability give the full-family guarantee. The uniform concentration result has already accounted for all the boundary matrices jointly. No further union bound over the 2W2W boundaries is taken here. Such an additional step would discard the improved dependence on width that the shared-energy analysis provides. ∎ B.6 Independent families and validation-dependent visits On the simultaneous event above, every required decision in the fixed candidate family is correct. Therefore the visiting order, skipped checks, revisits, switches between paths, and the final selection may be arbitrary measurable functions of the validation observations and other available information. No independence is required of the final selected index. Independence is imposed on the complete candidate universe before that selection. It is not enough that each realized run happens to visit a short or ordered path. To see this, take A=InA=I_n, draw G∈ℝn×sG ^n× s with s<ns<n, and let PGP_G be the orthogonal projection onto its column space. The Gaussian matrix has rank s almost surely, and (I−PG)G=0,q^(PG)=0,q(PG)=n−sn.(I-P_G)G=0,~~ q(P_G)=0,~~q(P_G)= n-sn. For any target ρ<(n−s)/nρ<(n-s)/n, both midpoint rules would accept this unsafe candidate almost surely. The realized singleton is trivially ordered, but its construction depends on the validation sketch and falls outside the independent-family assumptions. Finally, the boundary reductions above hold for the fixed target ρ and gap g. Their boundary matrices generally change when the target changes. The proof therefore does not grant simultaneous validity for an arbitrarily selected target after observing the sketch. The finite-family concentration proposition itself controls all the ratios at once, but replacing the full family size by its chain width uses boundaries for the specified, fixed classification problem. B.7 Reuse for mean-square output error Let the input distribution have a known second moment K=[xx⊤]⪰0K=E[x ] 0, and suppose ‖Ax‖22>0E\|Ax\|_2^2>0. Set B=AK1/2B=AK^1/2 and TK=B⊤B=K1/2A⊤AK1/2,EiK=B⊤(I−Pi)B=K1/2A⊤(I−Pi)AK1/2.T_K=B B=K^1/2A AK^1/2,~~E_i^K=B (I-P_i)B=K^1/2A (I-P_i)AK^1/2. For orthogonal PiP_i, these matrices satisfy 0⪯EiK⪯TK0 E_i^K T_K and ‖(I−Pi)Ax‖22‖Ax‖22=trEiKtrTK. E\|(I-P_i)Ax\|_2^2E\|Ax\|_2^2= trE_i^KtrT_K. Congruence preserves the Loewner order: every chain of original residual energies maps to a chain of the transformed energies. Hence a width-W cover remains a cover by at most W chains after this transformation. Singular K causes no difficulty because trTK>0trT_K>0 is assumed. Each Gaussian response needed for the transformed problem is Bgj=A(K1/2gj)Bg_j=A(K^1/2g_j) and therefore costs exactly one forward query to A. Once these responses are cached, all candidate projections use the same cache. The finite- and countable-family reductions, the fixed-width confidence bound, and the shared-energy upper bound above therefore apply for every prescribed K, provided that K and the complete candidate family are independent of the validation probes. The actual input distribution need not be Gaussian; only its known second moment enters the target. When the worst case also ranges over known second moments, the subclass K=InK=I_n contains the Frobenius problem. Thus the matching lower bounds of Appendix C also apply to that joint worst case. This inclusion does not assert the same lower bound for every individual prescribed, possibly singular, K. Appendix C Adaptive Lower Bounds for Simultaneous Certification This appendix proves the lower bound in Theorem 4.1. The argument applies to arbitrary adaptive forward-query procedures, rather than only to the Gaussian ratio estimator. All logarithms are natural. C.1 The task and the dimension-uniform quantifiers Fix ρ∈(0,1)ρ∈(0,1) and a gap g∈(0,ρ)g∈(0,ρ). An unknown, nonzero matrix A∈ℝm×nA ^m× n is accessed through responses AvAv. The public candidate family consists of orthogonal residual projectors R1,…,RM∈ℝm×mR_1,…,R_M ^m× m; the corresponding approximation projectors are Im−RjI_m-R_j. Define qj(A)=tr(A⊤RjA)tr(A⊤A),Ej(A)=A⊤RjA,T(A)=A⊤A.q_j(A)= tr(A R_jA)tr(A A),~~E_j(A)=A R_jA,~~T(A)=A A. (C.1) A decision Dj=1D_j=1 means acceptance. Simultaneous safety and completeness require, for every admissible deterministic A and family, ℙADj=0for all j with qj(A)≥ρ,Dj=1for all j with qj(A)≤ρ−g≥1−δ.P_A\! \ array[]lD_j=0&for all j with q_j(A)≥ρ,\\ D_j=1&for all j with q_j(A)≤ρ-g array \≥ 1-δ. (C.2) Candidates in (ρ−g,ρ)(ρ-g,ρ) impose no decision requirement. The family has width at most W if the matrices Ej(A)E_j(A) can be covered by at most W Loewner chains. In particular, every family with M≤WM≤ W is admissible, regardless of A. The algorithm knows the dimensions, projectors, and testing parameters. Its query and decision maps are measurable and may use private randomness independent of A. Every response concerning A counts toward a hard budget s∈ℤ≥0s _≥ 0, including responses obtained before a putative validation phase. Query directions may depend on the complete preceding transcript, and early stopping is allowed. No construction transcript, matrix factorization, exact energy, or other observation of A is supplied for free. A dimension-uniform budget is one bound s valid for all finite m,nm,n and admissible pairs (A,Rj)(A,\R_j\); the algorithm itself may depend on these public inputs. Theorem C.1 (Simultaneous certification requires width and confidence information). Let W≥1W≥ 1 be an integer and put w=minρ,1−ρw= \ρ,1-ρ\. If 0<g≤w/320<g≤ w/32 and 0<δ≤1/40<δ≤ 1/4, every dimension-uniform procedure satisfying (C.2) on all families of width at most W has s≥w265536g2[log(W+1)+log1δ].s≥ w^265536g^2 [ (W+1)+ 1δ ]. (C.3) The numerical constant is not optimized. The lower bound already holds on finite families of fixed orthogonal residual projectors. We prove the theorem below. The width term is obtained by identifying a hidden covariance label, and the confidence term by testing two covariances. The hard families used for these two terms need not be the same: a uniform procedure must succeed on both. C.2 A subspace packing with quadratic log cardinality For completeness, we state the precise concentration ingredient and derive the packing. The sole geometric input is the standard logarithmic Sobolev inequality for Haar measure on SO(k)SO(k), with its constant specified below. Lemma C.2 (Haar concentration used in the packing). Let k≥3k≥ 3, let U be Haar distributed on SO(k)SO(k), and let F be a smooth function satisfying |F(U)−F(V)|≤L∥U−V∥F|F(U)-F(V)|≤ L U-V _F. For L>0L>0 and t>0t>0, ℙF(U)−F(U)≥t≤exp−(k−2)t224L2.P\F(U)-EF(U)≥ t\≤ \- (k-2)t^224L^2 \. Proof. Write μ for Haar probability measure. With the metric locally induced by the Frobenius norm, the logarithmic Sobolev inequality is Entμ(f2)≤8k−2∫∥∇f∥2μ,Entμ(X)=μ[XlogX]−μXlogμX.Ent_μ(f^2)≤ 8k-2 ∇ f ^2\,dμ,~~Ent_μ(X)=E_μ[X X]-E_μX _μX. (C.4) This is the SO(k)SO(k) case of ([)Theorem 5.16]meckes2019, whose log-Sobolev convention is Ent(f2)≤2C∥∇f∥2Ent(f^2)≤ 2CE ∇ f ^2 with C=4/(k−2)C=4/(k-2). Here is the concentration argument, to make the required normalization explicit. Set ψ(λ)=logeλF(U)ψ(λ)= ^λ F(U). The group is compact, so these exponential moments and their derivatives exist. Apply (C.4) to f=eλF/2f=e^λ F/2 and use ∥∇F∥≤L ∇ F ≤ L: λψ′(λ)−ψ(λ)≤2λ2L2k−2.λψ (λ)-ψ(λ)≤ 2λ^2L^2k-2. Integrating the derivative of ψ(λ)/λψ(λ)/λ from zero gives ψ(λ)−λF≤2λ2L2/(k−2)ψ(λ)- ≤ 2λ^2L^2/(k-2) for λ>0λ>0. Exponential Markov inequality, optimized at λ=(k−2)t/(4L2)λ=(k-2)t/(4L^2), gives the stronger exponent −(k−2)t2/(8L2)-(k-2)t^2/(8L^2). Weakening its denominator to 2424 proves the stated form, which also agrees with the general concentration statement in ([)Theorem 5.17]meckes2019. ∎ Lemma C.3 (A finite projector packing). For every integer k≥3k≥ 3, put d=2kd=2k. There exist at least ⌊ek(k−2)/96⌋ e^k(k-2)/96 rank-d/2d/2 orthogonal projectors Pi∈ℝd×dP_i ^d× d with tr(PiPj)≤3d8whenever i≠j.tr(P_iP_j)≤ 3d8~whenever i≠ j. (C.5) In particular, for every W≥16W≥ 16 one can choose exactly M=WM=W projectors with d≤24logWd≤ 24 W. Proof. For U∈SO(k)U (k) define the graph projector P(U)=12(IkUU⊤Ik).P(U)= 12 pmatrixI_k&U\\ U &I_k pmatrix. Direct multiplication gives P(U)2=P(U)P(U)^2=P(U) and trP(U)=ktrP(U)=k. Also, tr(P(U)P(V))=d4+12tr(U⊤V).tr(P(U)P(V))= d4+ 12tr(U V). Thus pairwise traces tr(U⊤V)≤k/2tr(U V)≤ k/2 imply (C.5). The smooth function F(U)=trUF(U)=trU is k k-Lipschitz by Cauchy–Schwarz. Its Haar mean is zero: multiplying on the left by a diagonal rotation that changes the signs of any prescribed row and one other row changes the sign of the prescribed diagonal entry without changing its distribution. Lemma C.2 now gives ℙtrU>k/2≤e−k(k−2)/96=:pk.P\trU>k/2\≤ e^-k(k-2)/96=:p_k. For each fixed center U0U_0, Haar invariance gives the same upper bound for the set V:tr(U0⊤V)>k/2\V:tr(U_0 V)>k/2\. After choosing j centers, their excluded sets have total measure at most jpkjp_k. Whenever jpk<1jp_k<1, another center exists. This greedy construction supplies at least ⌊pk−1⌋ p_k^-1 centers. The trace relation is symmetric in its two arguments, so every selected pair has the required overlap. For the last assertion take k=⌈96logW⌉+2,d=2k.k= 96 W +2,~~d=2k. (C.6) Then k(k−2)≥96logWk(k-2)≥ 96 W, so at least W members are available. Retain exactly M=WM=W. Since W≥16W≥ 16, d≤296logW+6≤24logWd≤ 2 96 W+6≤ 24 W. ∎ C.3 A covariance family with exactly one acceptable candidate Fix a packing from Lemma C.3, and define Qi=2Pi−IdQ_i=2P_i-I_d and a=16g/wa=16g/w. The gap assumption gives 0<a≤1/20<a≤ 1/2. The matrices QiQ_i satisfy Qi2=IdQ_i^2=I_d and trQi=0trQ_i=0, with each eigenvalue 11 and −1-1 occurring d/2d/2 times. In output dimension m=d+2m=d+2, set Σi _i =diag(wd(Id−aQi),β,ζ), =diag ( wd(I_d-aQ_i),β,ζ ), (C.7) β β =ρ−w2+3wa8,ζ=1−ρ−w2−3wa8, =ρ- w2+ 3wa8,~~ζ=1-ρ- w2- 3wa8, Rj R_j =diag(Pj,1,0),1≤j≤M. =diag(P_j,1,0),~~1≤ j≤ M. The candidates RjR_j are fixed and do not depend on the hidden label i. All blocks of Σi _i are positive definite. More explicitly, wd(Id−aQi)⪰w2dId,β≥ρ2,ζ≥5(1−ρ)16. wd(I_d-aQ_i) w2dI_d,~~β≥ ρ2,~~ζ≥ 5(1-ρ)16. The first bound uses a≤1/2a≤ 1/2. The second uses w≤ρw≤ρ; the third follows from 3wa/8≤3w/163wa/8≤ 3w/16 and w≤1−ρw≤ 1-ρ. Furthermore, trΣi=1,detΣi=(wd)d(1−a2)d/2βζ,tr _i=1,~~ _i= ( wd )^d(1-a^2)^d/2βζ, (C.8) so every hypothesis has the same total population energy and determinant. Write μij=tr(RjΣi) _ij=tr(R_j _i). From (C.7), μij=ρ+3wa8−wadtr(PjQi). _ij=ρ+ 3wa8- wadtr(P_jQ_i). Since PiQi=PiP_iQ_i=P_i, the diagonal case has tr(PiQi)=d/2tr(P_iQ_i)=d/2. For j≠ij≠ i, (C.5) gives tr(PjQi)=2tr(PjPi)−d/2≤d/4.tr(P_jQ_i)=2tr(P_jP_i)-d/2≤ d/4. Consequently, μii=ρ−wa8=ρ−2g,μij≥ρ+wa8=ρ+2g(j≠i). _i=ρ- wa8=ρ-2g,~~ _ij≥ρ+ wa8=ρ+2g~(j≠ i). (C.9) This verifies the separation used in (3): only candidate i lies below ρ−gρ-g, while every other candidate lies above ρ. Both sides have strict slack. The Gaussian pairwise relative entropy can be computed exactly. For positive definite covariances in dimension m, KL(N(0,Σi)∥N(0,Σj))=12[tr(Σj−1Σi)−m+logdetΣjdetΣi].KL (N(0, _i)\|N(0, _j) )= 12 [tr( _j^-1 _i)-m+ _j _i ]. The determinant term vanishes by (C.8). The two scalar blocks each contribute one to the trace. On the first d coordinates, (Id−aQj)−1(Id−aQi)=(Id+aQj)(Id−aQi)1−a2,(I_d-aQ_j)^-1(I_d-aQ_i)= (I_d+aQ_j)(I_d-aQ_i)1-a^2, whose trace is [d−a2tr(QjQi)]/(1−a2)[d-a^2tr(Q_jQ_i)]/(1-a^2). It follows that KL(N(0,Σi)∥N(0,Σj))=a2[d−tr(QiQj)]2(1−a2)≤a2d1−a2. (N(0, _i)\|N(0, _j) )= a^2[d-tr(Q_iQ_j)]2(1-a^2)≤ a^2d1-a^2. Here |tr(QiQj)|≤d|tr(Q_iQ_j)|≤ d because Qi,QjQ_i,Q_j are orthogonal matrices. This upper bound is of order g2d/w2g^2d/w^2. C.4 Transferring covariance information to adaptive queries Under label i, draw the n columns of A independently from N(0,Σi/n)N(0, _i/n). These Gaussian matrices are priors for a lower bound on the deterministic-matrix problem; they do not change the pointwise requirement (C.2). Lemma A.4 proves the Gaussian-innovation representation in (1) for an arbitrary positive definite output covariance, including (C.7). In the present notation, after observing queries Vt=[v1,…,vt]V_t=[v_1,…,v_t] and responses Yt=AVtY_t=AV_t, let Mt=YtVt†M_t=Y_tV_t and Πt=In−VtVt† _t=I_n-V_tV_t . Conditional on the transcript and private seed, the residual A−MtA-M_t is centered matrix Gaussian with covariance Cov((A−Mt)a,u,(A−Mt)b,v∣transcript)=(Σi)abn(Πt)uv.Cov ((A-M_t)_a,u,(A-M_t)_b,v )= ( _i)_abn( _t)_uv. This statement follows by the same Gaussian conditioning induction as for (1). In particular, for the next query v, with v⟂=Πtv_ = _tv, Av=Mtv+∥v⟂∥2nξ,ξ∼N(0,Σi),Av=M_tv+ v_ _2 n\,ξ,~~ξ N(0, _i), where the innovation is fresh and independent of the preceding transcript whenever v⟂≠0v_ ≠ 0. Gaussian components along orthogonal unexplored input directions are independent even though the output coordinates can be correlated. If v⟂=0v_ =0, the response is determined by the past. After a nonredundant query with u=v⟂/∥v⟂∥2u=v_ / v_ _2, the updates are Mt+1=Mt+ξu⊤/nM_t+1=M_t+ξ u / n and Πt+1=Πt−uu⊤ _t+1= _t-u . They preserve the displayed conditional covariance. Thus the entire transcript is a measurable function of the private seed and at most s independent N(0,Σi)N(0, _i) vectors. The function is independent of i and Σi _i: the simulator uses the supplied vectors and the query rule, not the unknown covariance. Redundant queries consume budget but no innovation; after early stopping, unused vectors are discarded. The statement is also valid for s=0s=0. Let i,n P_i,n be the resulting transcript law, including the private seed and output. Data processing and product relative entropy (Scarlett and Cevher, 2019) give, for every pair i,ji,j and every input dimension n, KL(i,n∥j,n)≤sKL(N(0,Σi)∥N(0,Σj))≤sa2d1−a2.KL( P_i,n\| P_j,n)≤ sKL (N(0, _i)\|N(0, _j) )≤ sa^2d1-a^2. The private seed contributes no relative entropy because it has the same distribution under both labels. The bound remains valid for procedures that depend on n. C.5 A uniform finite-dimensional leakage bound The population separation must be transferred to realized matrices. The following elementary estimate makes this step uniform over the finite set of labels and candidates. Lemma C.4 (Finite-dimensional prior leakage). Let Σ≻0 0 have trace one, let the columns of A be independent N(0,Σ/n)N(0, /n) vectors, and let R1,…,RMR_1,…,R_M be fixed orthogonal projectors. Write μj=tr(RjΣ) _j=tr(R_j ) and let qj(A)q_j(A) be as in (C.1). For 0<g<10<g<1, ℙmaxj≤M|qj(A)−μj|≥g/2≤min1,128(M+1)ng2.P \ _j≤ M|q_j(A)- _j|≥ g/2 \≤ \1, 128(M+1)ng^2 \. Proof. Write the columns of A as zℓ/nz_ / n, where the zℓz_ are independent N(0,Σ)N(0, ) vectors, and set Dn=1n∑ℓ=1n∥zℓ∥22,Nj,n=1n∑ℓ=1nzℓ⊤Rjzℓ.D_n= 1n _ =1^n z_ _2^2,~~N_j,n= 1n _ =1^nz_ R_jz_ . Then qj=Nj,n/Dnq_j=N_j,n/D_n, Dn=1ED_n=1, and Nj,n=μj∈[0,1]EN_j,n= _j∈[0,1]. Diagonalizing the relevant Gaussian quadratic form and using Var(χ12)=2Var( _1^2)=2 gives Var(Dn)=2ntr(Σ2)≤2n,Var(Nj,n)=2ntr((Σ1/2RjΣ1/2)2)≤2n.Var(D_n)= 2ntr( ^2)≤ 2n,~~Var(N_j,n)= 2ntr (( ^1/2R_j ^1/2)^2 )≤ 2n. The last inequalities use positivity and trace at most one. Apply Chebyshev’s inequality with h=g/8h=g/8 to these M+1M+1 variables. Except on an event of probability at most 2(M+1)/(nh2)=128(M+1)/(ng2)2(M+1)/(nh^2)=128(M+1)/(ng^2), all their deviations from their means are at most h. On that event, |qj−μj|≤|Nj,n−μj|+μj|Dn−1|Dn≤2h1−h<g2,|q_j- _j|≤ |N_j,n- _j|+ _j|D_n-1|D_n≤ 2h1-h< g2, since g<1g<1. This proves the claim. ∎ Apply the lemma under each Σi _i. Because its bound depends only on the common trace and family size, it yields ηn:=maxiℙimaxj|qj(A)−μij|≥g/2≤min1,128(M+1)ng2⟶0. _n:= _iP_i \ _j|q_j(A)- _ij|≥ g/2 \≤ \1, 128(M+1)ng^2 \ 0. Outside this event, candidate i has qi(A)<ρ−gq_i(A)<ρ-g and every other candidate has qj(A)>ρq_j(A)>ρ, by (C.9). The limit fixes M,d,gM,d,g and s first and then increases n; no joint limiting assumption is needed. C.6 Decoding and the width-dependent query lower bound Choose a label J uniformly from 1,…,M\1,…,M\ and then draw the matrix under the corresponding prior. Let nT_n be the full transcript. Decode J by returning the unique accepted candidate, and return a fixed index if the acceptance vector has no unique one. On the complement of the leakage event, simultaneous correctness forces exactly candidate J to be accepted. Integrating the pointwise guarantee over the prior therefore gives pe,n:=ℙJ^≠J≤δ+ηn.p_e,n:=P\ J≠ J\≤δ+ _n. (C.10) This is where completeness as well as safety is used. For clarity, the needed Fano inequality (Scarlett and Cevher, 2019) follows from a short entropy calculation. The error indicator is determined by (J,n)(J,T_n). Conditioning on it gives H(J∣n)≤log2+pe,nlog(M−1)≤log2+pe,nlogM.H(J _n)≤ 2+p_e,n (M-1)≤ 2+p_e,n M. Since H(J)=logMH(J)= M, for M≥2M≥ 2 this implies pe,n≥1−I(J,n)+log2logM.p_e,n≥ 1- I(J;T_n)+ 2 M. If ¯n=M−1∑j,n P_n=M^-1 _j P_j,n, convexity of relative entropy in its second argument gives I(J,n) (J;T_n) =1M∑iKL(i,n∥¯n) = 1M _iKL( P_i,n\| P_n) ≤1M2∑i,jKL(i,n∥j,n)≤sa2d1−a2. ≤ 1M^2 _i,jKL( P_i,n\| P_j,n)≤ sa^2d1-a^2. (C.11) Thus (C.10)–(C.11) produce the finite-dimensional inequality δ+ηn≥1−sa2d/(1−a2)+log2logM.δ+ _n≥ 1- sa^2d/(1-a^2)+ 2 M. It holds for every n and the algorithm supplied for that n. Consequently, a dimension-uniform budget must satisfy the same inequality with ηn _n removed by letting n→∞n→∞. For M≥16M≥ 16 and δ≤1/4δ≤ 1/4, (1−δ)logM−log2≥12logM,(1-δ) M- 2≥ 12 M, so s≥1−a22a2dlogM≥38a2dlogM.s≥ 1-a^22a^2d M≥ 38a^2d M. For W≥16W≥ 16, take M=WM=W and d from (C.6). Substitution of a=16g/wa=16g/w and d≤24logWd≤ 24 W yields the explicit width term s≥w216384g2logW.s≥ w^216384g^2 W. (C.12) The RjR_j are distinct projectors of the same rank d/2+1d/2+1. They are therefore pairwise incomparable: a nonzero positive semidefinite difference cannot have trace zero. When n≥d+2n≥ d+2, the Gaussian matrix A has full row rank almost surely. If B is any right inverse with AB=Id+2AB=I_d+2, then A⊤RiA⪯A⊤RjA⟹Ri=B⊤A⊤RiAB⪯B⊤A⊤RjAB=Rj.A R_iA A R_jA~ ~R_i=B A R_iAB B A R_jAB=R_j. The reverse implication is immediate by congruence. Thus the input energy matrices are also an antichain and have width exactly M=WM=W. For the uniform lower bound, the weaker fact M≤WM≤ W already ensures the width promise for every matrix, including rank-deficient ones. C.7 The confidence term and all integer widths Use a single residual projector R=diag(1,0)R=diag(1,0) and covariances Σ0=diag(ρ+2g,1−ρ−2g),Σ1=diag(ρ−2g,1−ρ+2g). _0=diag(ρ+2g,1-ρ-2g),~~ _1=diag(ρ-2g,1-ρ+2g). Their entries are positive, their traces equal one, and their population residual ratios lie in the strict null and alternative regions, respectively. The Gaussian priors and transcript simulation above apply with m=2m=2. For the variance ratios appearing in either Gaussian relative entropy, write the ratio as 1+t1+t. The gap assumption implies |t|≤4gw−2g≤215<12.|t|≤ 4gw-2g≤ 215< 12. The identity t−log(1+t)=∫0tu/(1+u)ut- (1+t)= _0^tu/(1+u)\,du gives t−log(1+t)≤t2t- (1+t)≤ t^2 on |t|≤1/2|t|≤ 1/2. Using the two diagonal variance ratios in the Gaussian formula, KL(N(0,Σ1)∥N(0,Σ0))≤(4gw−2g)2≤32g2w2.KL (N(0, _1)\|N(0, _0) )≤ ( 4gw-2g )^2≤ 32 g^2w^2. The middle expression follows because the factor 1/21/2 in the Gaussian formula cancels the number of diagonal terms. Let ph,np_h,n be the probability of accepting the candidate under label h. Lemma C.4, with M=1M=1, gives a number ηn→0 _n→ 0 such that pointwise correctness implies p0,n≤δ+ηn,p1,n≥1−δ−ηn.p_0,n≤δ+ _n,~~p_1,n≥ 1-δ- _n. Data processing from the transcript to this binary decision yields 32sg2w2≥kl(p1,n,p0,n),kl(p,q)=plogpq+(1−p)log1−p1−q.32s g^2w^2 (p_1,n,p_0,n),~~kl(p,q)=p pq+(1-p) 1-p1-q. For all sufficiently large n, δ+ηn<1/2δ+ _n<1/2. Binary relative entropy is increasing in its first argument and decreasing in its second whenever the first exceeds the second. Therefore the right side is at least kl(1−δ−ηn,δ+ηn)kl(1-δ- _n,δ+ _n). Letting n→∞n→∞ gives 32sg2w2≥kl(1−δ,δ)=(1−2δ)log1−δ≥14log1δ,0<δ≤14. 32s g^2w^2 (1-δ,δ)=(1-2δ) 1-δ≥ 14 1δ,0<δ≤ 14. For the final inequality, 1−2δ≥1/21-2δ≥ 1/2 and 1−δ≥δ1-δ≥ δ on this interval. It follows that s≥w2128g2log1δ.s≥ w^2128g^2 1δ. (C.13) We now finish the proof of Theorem C.1 with an explicit constant. If W≥16W≥ 16, then log(W+1)≤2logW (W+1)≤ 2 W. Thus (C.12) bounds s below by w2log(W+1)/(32768g2)w^2 (W+1)/(32768g^2), while (C.13) bounds it below by w2log(1/δ)/(128g2)w^2 (1/δ)/(128g^2). The maximum is at least half the sum with the smaller coefficient, proving (C.3). For 1≤W<161≤ W<16, log(W+1)≤log16≤2log4≤2log(1/δ). (W+1)≤ 16≤ 2 4≤ 2 (1/δ). Hence the confidence term alone implies (C.3), with substantial slack. All inequalities apply to integer budgets s≥0s≥ 0 without assuming s→∞s→∞. In particular, s=0s=0 cannot meet the required error level; an integer version of (C.3) can be written by taking the ceiling of its right side. Scope of the minimax statement. The hard family is selected in the supremum over admissible matrices, projectors, and dimensions. The result neither declares every width-W family difficult nor asserts this lower bound at each fixed input dimension: n coordinate queries can recover a fixed m×nm× n matrix exactly. It lower-bounds the total counted forward information needed for simultaneous safety and completeness. A procedure that receives a construction transcript without charging its responses uses a different information model. At fixed interior ρ, combining this lower bound with the common-envelope upper bound gives the stated order in W,g,δW,g,δ. Appendix D Proofs for Spectrum-Dependent Certification Delay This appendix proves the safety statement in Proposition 5.1, its spectrum-dependent power bound, and all delay and allocation claims in Theorem 5.2. The block count is denoted by L throughout, and δ is the error-probability level. In particular, L is fixed in the stopping-time asymptotics; it is not a matrix dimension or a covariance parameter. D.1 Notation, stopping rules, and probability space Let T≠0T≠ 0 be positive semidefinite and let 0⪯E⪯T0 E T. Define q=tr(E)tr(T),H=E−ρT,0<ρ<1.q= tr(E)tr(T),~~H=E-ρ T,~~0<ρ<1. Fix 0<δ<10<δ<1. The validation probes g1,…,gsg_1,…,g_s are independent standard Gaussian vectors. Write Zs(B)=1s∑i=1sgi⊤Bgi,q^=Zs(E)Zs(T).Z_s(B)= 1s _i=1^sg_i Bg_i,~~ q= Z_s(E)Z_s(T). The denominator is positive almost surely. For projection residuals, T=A⊤AT=A A and E=A⊤(I−P)AE=A (I-P)A, so gi⊤Hgi=‖(I−P)Agi‖22−ρ‖Agi‖22.g_i Hg_i=\|(I-P)Ag_i\|_2^2-ρ\|Ag_i\|_2^2. All block statistics below are therefore computable from the cached forward responses AgiAg_i. For an ordered path, the entire continuation (Er)r≥0(E_r)_r≥ 0 and all construction randomness are independent of the validation probes, and Er+1⪯ErE_r+1 E_r. One can first condition on that construction randomness, prove each probability bound for the resulting deterministic path, and then average. Parameters, partitions, and thresholds are chosen before observing validation data. The path may be inspected at sketch-dependent indices, provided it remains the same independent complete path. Let r⋆=minr:qr≤ρ,Ds=(τs−r⋆)+,r_ = \r:q_r≤ρ\,~~D_s=( _s-r_ )_+, where τs _s is the first acceptance position of the specified rule. All distributions and expectations of DsD_s below are unconditional. In particular, they are not conditioned on the absence of an early false acceptance. The definition of r⋆r_ includes the boundary q=ρq=ρ, while the safety calibration controls acceptance even on that boundary. For the ratio rule, put ℓ(x)=log(x/(1−x)) (x)= (x/(1-x)) and us(δ)=2arcosh(δ−1/s),θs(δ)=ρ+eus(δ)(1−ρ).u_s(δ)=2arcosh(δ^-1/s),~~ _s(δ)= ρ+e^u_s(δ)(1-ρ). (D.1) The rule accepts when q^≤θs(δ) q≤ _s(δ). Since 0<θs(δ)<ρ0< _s(δ)<ρ, the log-ratio bound from Section 3 gives acceptance probability at most δ for every fixed candidate with q≥ρq≥ρ. For q∈0,1q∈\0,1\ the sampled ratio equals q almost surely, so these endpoints cause no undefined-logarithm issue. Along an independent ordered path, q^r q_r decreases and the unsafe-prefix argument below extends the same probability bound to false stopping anywhere on the path. D.2 Log-concavity and the exact block-sign calibration For integers L≥1L≥ 1 and b≥2b≥ 2, let s=Lbs=Lb and partition the probes into L disjoint blocks ℐ1,…,ℐLI_1,…,I_L of size b. Set Xℓ(H)=1b∑i∈ℐℓgi⊤Hgi,VL(H)=∑ℓ=1LXℓ(H)≥0.X_ (H)= 1b _i _ g_i Hg_i,~~V_L(H)= _ =1^L1\X_ (H)≥ 0\. The cutoff and acceptance rule are kδ(L)=maxk∈0,…,L−1:ℙBin(L,e−1)≤k≤δ,accept⟺VL(H)≤kδ(L). splitk_δ(L)&= \k∈\0,…,L-1\:P\Bin(L,e^-1)≤ k\≤δ \,\\ accept&~ ~V_L(H)≤ k_δ(L). split If the defining set is empty, put kδ(L)=−1k_δ(L)=-1 and reject identically. This convention is useful for safety but is excluded from the stopping-time and allocation results, which require eventual acceptance. We use the standard marginalization consequence of the Prékopa–Leindler inequality: integrating a log-concave function over some coordinates preserves log-concavity (Saumard and Wellner, 2014). Applied to f(x−y)h(y)f(x-y)h(y), this shows that convolution preserves log-concavity of densities. Applied to f(x+t)t≥0f(x+t)1\t≥ 0\, it shows that a log-concave density has a log-concave survival function. Lemma D.1 (Mass above the mean). If X has a nondegenerate log-concave density and a finite mean, then ℙ(X≥X)≥e−1P(X )≥ e^-1. Proof. Let S(x)=ℙ(X≥x)S(x)=P(X≥ x). The function S is log-concave. The distribution of X is continuous, so the probability integral transform gives that S(X)S(X) is uniform on (0,1)(0,1). Therefore logS(X)=∫01logtt=−1.E S(X)= _0^1 t\,dt=-1. The mean is in the interior of the interval supporting a nondegenerate integrable log-concave distribution. Jensen’s inequality for the concave function logS S consequently gives logS(X)≥logS(X)=−1. S(EX) S(X)=-1. Exponentiating proves the result. ∎ Lemma D.2 (Sign probability of a Gaussian block). Let H be a real symmetric matrix. For b≥2b≥ 2 independent standard Gaussian vectors, define Xb=b−1∑i=1bgi⊤HgiX_b=b^-1 _i=1^bg_i Hg_i. If tr(H)≥0tr(H)≥ 0, then ℙ(Xb≥0)≥e−1P(X_b≥ 0)≥ e^-1. The constant cannot be increased uniformly over matrix dimensions, symmetric H, and integers b≥2b≥ 2. Proof. If H=0H=0, then Xb=0X_b=0 and the probability is one. Otherwise, orthogonal diagonalization and Gaussian rotation give Xb=∑jλjYjb,Yj∼χb2independently,X_b\ d=\ _j _j Y_jb,~~Y_j _b^2\ independently, where zero eigenvalues are omitted. A χb2 _b^2 density is Gamma with shape b/2≥1b/2≥ 1, hence is log-concave. Scaling by a nonzero coefficient preserves log-concavity; a negative coefficient merely reflects the density. Convolution therefore shows that XbX_b has a nondegenerate log-concave density. Since Xb=tr(H)≥0EX_b=tr(H)≥ 0, Lemma D.1 gives ℙ(Xb≥0)≥ℙ(Xb≥Xb)≥e−1.P(X_b≥ 0) (X_b _b)≥ e^-1. For uniform sharpness, take b=2b=2 and Hn=diag(1,−1/n,…,−1/n)H_n=diag(1,-1/n,…,-1/n) with n negative coordinates. Its trace is zero, and X2(Hn)=χ222−χ2n22n⟹Exp(1)−1.X_2(H_n) d= _2^22- _2n^22n\ \ Exp(1)-1. The limiting distribution has no atom at zero and has probability e−1e^-1 of being nonnegative. This proves the claimed uniform sharpness, without asserting sharpness for each fixed b>2b>2. ∎ Proof of the safety statement in Proposition 5.1. For a fixed q≥ρq≥ρ, tr(H)=tr(T)(q−ρ)≥0tr(H)=tr(T)(q-ρ)≥ 0. The block statistics are independent and identically distributed. By Lemma D.2, the probability p of a nonnegative block is at least e−1e^-1. Thus VL(H)∼Bin(L,p)V_L(H) (L,p) stochastically dominates Bin(L,e−1)Bin(L,e^-1). The definition of kδ(L)k_δ(L) gives ℙVL(H)≤kδ(L)≤δ.P\V_L(H)≤ k_δ(L)\≤δ. The empty-cutoff case rejects deterministically. If H=0H=0, all L blocks are nonnegative, and every allowable cutoff is less than L, so the rule also rejects. For pathwise safety, condition on the independent construction randomness. The contrast matrices Hr=Er−ρTH_r=E_r-ρ T decrease in the Loewner order. Hence every Xℓ(Hr)X_ (H_r) and their count VL(Hr)V_L(H_r) are nonincreasing in r. The true errors qrq_r are nonincreasing as well. On any finite prefix 0,…,J0,…,J, let rJr_J be the last index with qrJ≥ρq_r_J≥ρ, if one exists. Acceptance at any such index is equivalent to acceptance at rJr_J: the acceptance events are nested along this unsafe prefix. The single-candidate bound is therefore a bound of δ on the union of those events. If no unsafe index exists, the union is empty. As J→∞J→∞, these union events increase to acceptance at any qr≥ρq_r≥ρ on the countable path. Continuity of probability from below preserves the bound δ. This argument does not assume a last unsafe index on the entire infinite path. Averaging over the conditioned construction randomness completes the proof. The same argument proves pathwise safety of the ratio rule because its sampled ratios decrease along the same path. ∎ D.3 Finite-sample power without spectral inputs Proposition D.3 (Block-sign power). For a fixed candidate with tr(H)=−d<0tr(H)=-d<0, put vH2=2tr(H2)v_H^2=2tr(H^2). Then ℙreject≤ℙBin(L,vH2vH2+bd2)>kδ(L).P\reject\ \! \Bin\! (L, v_H^2v_H^2+bd^2 )>k_δ(L) \. (D.2) For 0<δ≤1/20<δ≤ 1/2, there are choices of L and b giving both errors at most δ with sufficient total budget s=O(log(1/δ)[1+tr(H2)(trH)2]).s=O\! ( (1/δ) [1+ tr(H^2)(trH)^2 ] ). (D.3) The quantities d and vHv_H characterize when a budget gives power; they are not inputs to the block-sign decision rule. Proof. For a symmetric Gaussian quadratic form, Var(g⊤Hg)=2tr(H2)Var(g Hg)=2tr(H^2). Consequently Xℓ=−d,Var(Xℓ)=vH2/b.EX_ =-d,~~Var(X_ )=v_H^2/b. Cantelli’s inequality gives p:=ℙ(Xℓ≥0)≤vH2/bvH2/b+d2=vH2vH2+bd2.p:=P(X_ ≥ 0)≤ v_H^2/bv_H^2/b+d^2= v_H^2v_H^2+bd^2. Stochastic monotonicity of binomial distributions proves (D.2). For explicit sufficient choices, write kl(a∥p)=alog(a/p)+(1−a)log((1−a)/(1−p))kl(a\|p)=a (a/p)+(1-a) ((1-a)/(1-p)) for Bernoulli relative entropy and define the positive constants d0=kl(1/4∥e−1),d1=kl(1/4∥1/8).d_0=kl(1/4\|e^-1),~~d_1=kl(1/4\|1/8). Choose integers satisfying L≥log(1/δ)mind0,d1,b≥max2,7vH2/d2.L≥ (1/δ) \d_0,d_1\,~~b≥ \2,7v_H^2/d^2\. (D.4) A binomial Chernoff bound yields ℙBin(L,e−1)≤⌊L/4⌋≤e−Ld0≤δ.P\Bin(L,e^-1)≤ L/4 \≤ e^-Ld_0≤δ. Thus kδ(L)≥⌊L/4⌋k_δ(L)≥ L/4 , in particular the cutoff is nonnegative. The condition on b gives p≤1/8p≤ 1/8. Rejection implies VL>⌊L/4⌋V_L> L/4 , hence VL/L>1/4V_L/L>1/4, and a second Chernoff bound gives rejection probability at most e−Ld1≤δe^-Ld_1≤δ. Safety holds by Proposition 5.1. Taking ceilings in (D.4) proves (D.3), with a universal implied constant. Operationally, one may choose L solely from δ and, for a given budget s, use b=⌊s/L⌋≥2b= s/L ≥ 2, discarding any remainder. The second inequality in (D.4) describes when that fixed budget has the stated power. It does not require estimating either spectral quantity to set the acceptance threshold. ∎ D.4 The common spectral family and its exact block representation For positive integers M,NM,N, consider AM,N=diag(1−ρMIM,ρNIN).A_M,N=diag ( 1-ρM\,I_M, ρN\,I_N ). Its squared Frobenius norm is one. Let PrP_r project onto the first r coordinates. This path first captures the initial M directions and then the N tail directions individually. For 0≤r<M0≤ r<M, q(Pr)=1−r(1−ρ)M>ρ,q(P_r)=1- r(1-ρ)M>ρ, and for 0≤j≤N0≤ j≤ N, q(PM+j)=ρ(1−j/N).q(P_M+j)=ρ(1-j/N). Thus r⋆=Mr_ =M exactly under the definition q≤ρq≤ρ. The path is an ordered coordinate path for all M,NM,N. It is also the truncated singular-vector path only when (1−ρ)/M≥ρ/N(1-ρ)/M≥ρ/N; no such additional ordering of singular values is needed for the results below. The delay results assume that every coordinate position is inspected in order, or equivalently that τs _s is the first position on the complete path satisfying the acceptance condition. In particular, all tail positions j=0,…,Nj=0,…,N are inspected unless acceptance has already occurred. Inspecting a subset retains the preceding safety guarantee, but the exact delay constants below do not apply to arbitrary skipped positions. Throughout the remaining subsections, fix ρ∈(0,1)ρ∈(0,1), δ∈(0,1/2)δ∈(0,1/2), and an integer L for which k=kδ(L)≥0k=k_δ(L)≥ 0. In particular, 0≤k<L0≤ k<L. Both L and k remain fixed as M,NM,N and the block size vary. The sign rule is the pure block-sign rule with this cutoff. The ratio rule uses (D.1) at the same level δ. At the full-rank position, E=0E=0, so every sign block equals a strictly negative multiple of a positive Gaussian energy almost surely. Hence VL=0≤kV_L=0≤ k. Also q^=0<θs(δ) q=0< _s(δ) for the ratio rule. Both stopping times are therefore finite, with positive delays at most N. Number tail positions by j=0,…,Nj=0,…,N and write Hj=AM,N⊤(I−PM+j)AM,N−ρAM,N⊤AM,NH_j=A_M,N (I-P_M+j)A_M,N-ρ A_M,N A_M,N. Its eigenvalues are −ρ(1−ρ)M(M times),−ρ2N(j times),ρ(1−ρ)N(N−j times).- ρ(1-ρ)M~(M times),~~- ρ^2N~(j times),~~ ρ(1-ρ)N~(N-j times). Consequently tr(Hj) (H_j) =−ρj/N, =-ρ j/N, (D.5) tr(Hj2) (H_j^2) =ρ2(1−ρ)2M+ρ2(N−j)(1−ρ)2+jρ2N2≤ρ2((1−ρ)2M+1N). = ρ^2(1-ρ)^2M+ ρ^2\(N-j)(1-ρ)^2+jρ^2\N^2≤ρ^2 ( (1-ρ)^2M+ 1N ). (D.6) In particular, Var(Xℓ(H0))=2ρ2(1−ρ)2b(1M+1N).Var(X_ (H_0))= 2ρ^2(1-ρ)^2b ( 1M+ 1N ). For each block ℓ , introduce independent random variables Cℓ∼χMb2Mb,Yℓi∼χb2b,1≤i≤N,Rℓ=1N∑i=1NYℓi.C_ _Mb^2Mb,~~Y_ i _b^2b,~1≤ i≤ N,~~R_ = 1N _i=1^NY_ i. Different blocks are independent. The dependence of RℓR_ on the YℓiY_ i is retained. The exact Gaussian block distribution gives Xℓ(Hj)=ρ(1−ρ)(Rℓ−Cℓ)−ρN∑i=1jYℓi.X_ (H_j)=ρ(1-ρ)(R_ -C_ )- ρN _i=1^jY_ i. (D.7) The block statistic decreases strictly with j almost surely. Define its first strict-negative time by Tℓ,N=min0≤j≤N:Xℓ(Hj)<0.T_ ,N= \0≤ j≤ N:X_ (H_j)<0\. Acceptance requires at least L−kL-k strict-negative blocks, so the first acceptance time when the tail is inspected is the (L−k)(L-k)th smallest of T1,N,…,TL,NT_1,N,…,T_L,N. This time equals the unconditional positive delay (τs−M)+( _s-M)_+ even if the rule is run before M: an acceptance before M forces acceptance at M by monotonicity, and both quantities are then zero. No conditioning on successful certification is used in this identity. D.5 The pure sign rule: crossing limit and convergence of means The following strengthened version of the sign part of Theorem 5.2 permits bounded block sizes. This extension will also be needed to rule out bounded optimal budgets. Proposition D.4 (Exact block-sign delay limit). Assume M/N→κ∈(0,∞)M/N→κ∈(0,∞) and let b=bN≥2b=b_N≥ 2 be integers with bN=o(N)b_N=o(N). Put s=Lbs=Lb, r=L−kr=L-k, and let Z(r)Z_(r) be the rrth smallest of L independent standard normal variables. Then DssignN/b⟹Aκ(Z(r))+,Aκ=(1−ρ)2(1+κ−1). D_s^sign N/b\ \ A_κ(Z_(r))_+,~~A_κ=(1-ρ) 2(1+κ^-1). (D.8) The expectations converge as well. Equivalently, Dssign∼CsignN/s,Csign=(1−ρ)2L(1+κ−1)[(Z(L−k))+].ED_s^sign C_sign N/s,~~C_sign=(1-ρ) 2L(1+κ^-1)\,E[(Z_(L-k))_+]. (D.9) The constant is finite and strictly positive. Proof. Let aN=N/b→∞a_N= N/b→∞. Since Nb→∞Nb→∞ and Mb→∞Mb→∞, the chi-square central limit theorem gives Nb(Rℓ−1)⟹(0,2),Nb(Cℓ−1)⟹(0,2/κ). Nb(R_ -1) (0,2),~~ Nb(C_ -1) (0,2/κ). These two variables are independent for each ℓ , and different blocks are independent. Therefore, jointly over the fixed L blocks, Uℓ,N:=NbρXℓ(H0)=Nb(1−ρ)(Rℓ−Cℓ)⟹AκZℓ,U_ ,N:= NbρX_ (H_0)= Nb(1-ρ)(R_ -C_ )\ \ A_κZ_ , where the ZℓZ_ are independent standard normals. This conclusion does not require b→∞b→∞ because both degrees of freedom already diverge through M,NM,N. By (D.7), NbρXℓ(Hj)=Uℓ,N−b/N∑i=1jYℓi. NbρX_ (H_j)=U_ ,N- b/N _i=1^jY_ i. The centered prefix sums are square-integrable martingales and Var(Yℓi)=2/bVar(Y_ i)=2/b. For fixed R>0R>0, Doob’s L2L^2 maximal inequality yields max0≤j≤⌊RaN⌋|b/N∑i=1j(Yℓi−1)|2≤4bN⌊RaN⌋2b≤8RNb⟶0.E _0≤ j≤ Ra_N | b/N _i=1^j(Y_ i-1) |^2≤ 4 bN Ra_N 2b≤ 8R Nb 0. For sufficiently large N the displayed prefix stays within the tail, since aN/N=1/Nb→0a_N/N=1/ Nb→ 0. Also, b/N⌊aNt⌋→t b/N a_Nt → t uniformly on compact t-intervals. Thus the scaled signed block process has a Gaussian initial offset followed by deterministic drift −t-t. No independence between the initial offset and the removed tail energies is needed: (D.5) makes the centered prefix negligible even with their exact dependence retained. For an explicit hitting-time argument, fix t>0t>0. For large N, monotonicity gives Tℓ,N/aN≤t=Xℓ(H⌊aNt⌋)<0.\T_ ,N/a_N≤ t\=\X_ (H_ a_Nt )<0\. The scaled statistic on the right converges to AκZℓ−tA_κZ_ -t, which has no atom at zero. The corresponding probability converges to ℙ(AκZℓ<t)P(A_κZ_ <t). Applying this argument jointly at positive times t1,…,tLt_1,…,t_L, or using block independence, proves (T1,N,…,TL,N)/aN⟹Aκ((Z1)+,…,(ZL)+).(T_1,N,…,T_L,N)/a_N A_κ((Z_1)_+,…,(Z_L)_+). Positive continuity points suffice to determine this distribution on the nonnegative orthant; its possible atom at zero is retained by the positive part. Sorting is a continuous map on ℝLR^L and commutes with a nondecreasing scalar function such as the positive part. The exact order-statistic representation consequently proves (D.8). To pass to means, let 1≤j≤N1≤ j≤ N. By (D.5) and (D.6), Cantelli’s inequality gives pj:=ℙXℓ(Hj)≥0≤2N2bj2((1−ρ)2M+1N).p_j:=P\X_ (H_j)≥ 0\≤ 2N^2bj^2 ( (1-ρ)^2M+ 1N ). Here the Cantelli expression is further bounded by variance divided by squared mean. Rejection at position j requires at least k+1k+1 nonnegative blocks. Markov’s inequality on their count therefore gives ℙ(Dssign>j)≤min1,Lpjk+1≤min1,C1Nbj2,P(D_s^sign>j)≤ \1, Lp_jk+1 \≤ \1, C_1Nbj^2 \, for 1≤j≤N1≤ j≤ N, with C1C_1 independent of N,b,jN,b,j for large N, because M/NM/N is bounded away from zero. For j>Nj>N the probability is zero. Thus for t≥2t≥ 2 and sufficiently large N, ⌊aNt⌋≥aNt/2 a_Nt ≥ a_Nt/2 and ℙ(Dssign/aN>t)≤4C1/t2.P(D_s^sign/a_N>t)≤ 4C_1/t^2. For R≥2R≥ 2, integrating this tail gives the explicit bound [DssignaNDssign/aN>R]=Rℙ(Dssign/aN>R)+∫R∞ℙ(Dssign/aN>t)dt≤8C1R. [ D_s^signa_N1\D_s^sign/a_N>R\ ]=R\,P(D_s^sign/a_N>R)+ _R^∞P(D_s^sign/a_N>t)\,dt≤ 8C_1R. This proves uniform integrability, rather than inferring it from weak convergence alone. Consequently the expectations in (D.8) converge. Since aN=LN/sa_N= L N/s, the resulting constant is exactly CsignC_sign in (D.9). It is finite because L is fixed and normal variables are integrable. It is positive, for example, because all L normals have a positive probability of exceeding one. ∎ D.6 The ratio rule on the same diffuse family Proposition D.5 (Exact ratio-rule delay limit). Assume M/N→κ∈(0,∞)M/N→κ∈(0,∞) and use the ratio threshold (D.1). If s=sN→∞s=s_N→∞ and sN=o(N2)s_N=o(N^2), then sNDsratio⟶Cratio=(1−ρ)8log(1/δ)in L2. sND_s^ratio C_ratio=(1-ρ) 8 (1/δ)~in L^2. (D.10) In particular, Dsratio∼CratioN/sED_s^ratio C_ratioN/ s. For every fixed integer s≥1s≥ 1, Dsratio/N⟶1−θs(δ)/ρ>0in L2.D_s^ratio/N 1- _s(δ)/ρ>0~in L^2. (D.11) Proof. Let Y1,…,YN∼χs2/sY_1,…,Y_N _s^2/s be independent and let CN∼χMs2/(Ms)C_N _Ms^2/(Ms) be independent of them. Set Bj=1N∑i=1jYi,B0=0.B_j= 1N _i=1^jY_i,~~B_0=0. At tail position j, the exact Gaussian ratio is q^(PM+j)=ρ(BN−Bj)(1−ρ)CN+ρBN. q(P_M+j)= ρ(B_N-B_j)(1-ρ)C_N+ρ B_N. Abbreviate θs=θs(δ) _s= _s(δ). Acceptance is equivalent to Bj≥hNB_j≥ h_N, where hN=(1−θs)BN−θs(1−ρ)ρCN.h_N=(1- _s)B_N- _s(1-ρ)ρC_N. Since BN−hN=θsBN+(1−ρ)CN/ρ>0B_N-h_N= _s\B_N+(1-ρ)C_N/ρ\>0 almost surely, the first crossing jN=min0≤j≤N:Bj≥hNj_N= \0≤ j≤ N:B_j≥ h_N\ exists. As explained for the sign rule, monotonicity makes this tail crossing time equal to the unconditional positive delay DsratioD_s^ratio, including sample paths that accepted before M. Let ΔN=max0≤j≤N|Bj−j/N| _N= _0≤ j≤ N|B_j-j/N|. The following bound is deterministic: |jNN−(hN)+|≤ΔN+1N. | j_NN-(h_N)_+ |≤ _N+ 1N. (D.12) If hN≤0h_N≤ 0, both jNj_N and (hN)+(h_N)_+ are zero. Otherwise, minimality gives BjN−1<hN≤BjNB_j_N-1<h_N≤ B_j_N, and therefore hN−ΔN≤jN/N<hN+ΔN+1/N.h_N- _N≤ j_N/N<h_N+ _N+1/N. For the centered prefix martingale, Doob’s inequality gives ΔN2≤4Var(BN)=8Ns.E _N^2≤ 4Var(B_N)= 8Ns. (D.13) The crossing level has mean and variance hN _N =1−θs/ρ, =1- _s/ρ, (D.14) sVar(hN) sVar(h_N) =2(1−θs)2N+2M(θs(1−ρ)ρ)2⟶0. = 2(1- _s)^2N+ 2M ( _s(1-ρ)ρ )^2 0. (D.15) The last limit is uniform over s≥1s≥ 1 because 0<θs<ρ0< _s<ρ and M/N→κ>0M/N→κ>0. Put λ=log(1/δ)>0λ= (1/δ)>0. For s→∞s→∞, sus(δ)⟶8λ. s\,u_s(δ) 8λ. Expanding the error-scale threshold at u=0u=0 gives 1−θs/ρ=(1−ρ)us(δ)+O(us(δ)2),1- _s/ρ=(1-ρ)u_s(δ)+O(u_s(δ)^2), so shN→Cratio s\,Eh_N→ C_ratio. Together with (D.15), this proves shN→Cratio sh_N→ C_ratio in L2L^2. The positive-part map is 11-Lipschitz and Cratio>0C_ratio>0, so the same is true of s(hN)+ s(h_N)_+. Multiplying (D.12) by s s, using (D.13), and using s/N→0 s/N→ 0 now proves (D.10). In this case convergence of means follows from the stronger L2L^2 convergence. Finally, for a fixed s, equations (D.14) and (D.15) give hN→1−θs/ρ>0h_N→ 1- _s/ρ>0 in L2L^2, while (D.13) gives ΔN→0 _N→ 0 in L2L^2. The same crossing bound proves (D.11). ∎ When the two rules are compared at a common budget s=Lb→∞s=Lb→∞ with fixed L and b=o(N)b=o(N), all conditions of both delay propositions hold. Their means are precisely those stated in (4). The sign statement itself permits bounded b, whereas the ratio statement permits the larger growing budget range s=o(N2)s=o(N^2). D.7 Global optimization over integer validation budgets For fixed cv,cb>0c_v,c_b>0, define Nsign(s)=cvs+cbDssign,Nratio(s)=cvs+cbDsratio.C_N^sign(s)=c_vs+c_bED_s^sign,~~C_N^ratio(s)=c_vs+c_bED_s^ratio. The sign optimization is over L=Lb:b∈ℕ,b≥2S_L=\Lb:b ,\ b≥ 2\, with L and k=kδ(L)k=k_δ(L) fixed. The ratio optimization is over all positive integers s. A minimum exists in each case: the cost is finite at every allowed budget because Ds≤ND_s≤ N, and it is at least cvsc_vs, which diverges with s. Proposition D.6 (Exact global allocations). Let CsignC_sign and CratioC_ratio be as above and put asign=(cbCsign2cv)2/3,aratio=(cbCratio2cv)2/3.a_sign= ( c_bC_sign2c_v )^2/3,~~a_ratio= ( c_bC_ratio2c_v )^2/3. Every sequence of global integer minimizers satisfies sNsign,∗ s_N^sign,* ∼asignN1/3, a_signN^1/3, mins∈LNsign(s) _s _LC_N^sign(s) ∼3cvasignN1/3, 3c_va_signN^1/3, sNratio,∗ s_N^ratio,* ∼aratioN2/3, a_ratioN^2/3, mins∈ℕ,s≥1Nratio(s) _s ,\ s≥ 1C_N^ratio(s) ∼3cvaratioN2/3. 3c_va_ratioN^2/3. (D.16) These statements keep the matrix family, coordinate path, target, confidence level, and the respective rule fixed. They concern the excess costs defined above, excluding construction of the initial M directions, and are not minimax lower bounds over all possible certificates or jointly adaptive budget-allocation schemes. Proof. First consider the sign rule. For any fixed x>0x>0, select sN∈Ls_N _L with sN/N1/3→xs_N/N^1/3→ x; rounding to a multiple of fixed L has asymptotically negligible effect. Then bN=sN/L→∞b_N=s_N/L→∞ and bN=o(N)b_N=o(N), so Proposition D.4 gives Nsign(sN)N1/3⟶fsign(x):=cvx+cbCsignx−1/2. C_N^sign(s_N)N^1/3 f_sign(x):=c_vx+c_bC_signx^-1/2. (D.17) In particular, the global minimum is O(N1/3)O(N^1/3). For any minimizing sequence, its validation cost implies sNsign,∗=O(N1/3)s_N^sign,*=O(N^1/3), hence bN∗=sNsign,∗/L=o(N)b_N^*=s_N^sign,*/L=o(N). The block sizes must also diverge. Otherwise a bounded subsequence of the integer bN∗b_N^* has a constant further subsequence. The bounded-b case of Proposition D.4 gives DLbN∗sign=Θ(N)ED_Lb_N^*^sign= ( N) on that subsequence, with a positive constant. This contradicts the feasible O(N1/3)O(N^1/3) cost. The mean asymptotic thus applies along every minimizing sequence. Write xN=sNsign,∗/N1/3x_N=s_N^sign,*/N^1/3. It is bounded above. If a subsequence had xN→0x_N→ 0, the mean asymptotic would imply Nsign(sNsign,∗)N1/3≥cb(Csign+o(1))xN−1/2⟶∞, C_N^sign(s_N^sign,*)N^1/3≥ c_b(C_sign+o(1))x_N^-1/2 ∞, again contradicting the feasible bound. Thus xNx_N stays in a compact subset of (0,∞)(0,∞). Along any subsequence with xN→x_N→ x, the normalized cost converges to fsign(x)f_sign(x). Comparing with the feasible sequences in (D.17) forces x to minimize fsignf_sign. This limiting function has the unique minimizer x=asign=(cbCsign2cv)2/3.x=a_sign= ( c_bC_sign2c_v )^2/3. Every subsequential limit is therefore asigna_sign, proving the budget asymptotic. Since fsign(asign)=3cvasignf_sign(a_sign)=3c_va_sign, the cost asymptotic follows. For the ratio rule, use instead feasible integers sN∼xN2/3s_N xN^2/3. Proposition D.5 gives Nratio(sN)N2/3⟶fratio(x):=cvx+cbCratiox−1/2. C_N^ratio(s_N)N^2/3 f_ratio(x):=c_vx+c_bC_ratiox^-1/2. The minimum is O(N2/3)O(N^2/3), and every minimizing sequence obeys sNratio,∗=O(N2/3)=o(N2)s_N^ratio,*=O(N^2/3)=o(N^2). It cannot remain bounded on a subsequence: a constant integer further subsequence would have Dsratio=Θ(N)ED_s^ratio= (N) by (D.11), contradicting that feasible cost. Thus sNratio,∗→∞s_N^ratio,*→∞, and the mean asymptotic in Proposition D.5 applies to every minimizing sequence. The normalized widths yN=sNratio,∗/N2/3y_N=s_N^ratio,*/N^2/3 are bounded above and cannot approach zero, since their normalized delay costs would then diverge as cb(Cratio+o(1))/yNc_b(C_ratio+o(1))/ y_N. The same compact-subsequence comparison now forces every limit to be the unique minimizer y=aratio=(cbCratio2cv)2/3y=a_ratio= ( c_bC_ratio2c_v )^2/3 of fratiof_ratio. Evaluating this function there gives 3cvaratio3c_va_ratio, completing (D.16). ∎ The two global allocation conclusions establish the cost and budget orders in Theorem 5.2. Their proofs first locate all minimizers in the appropriate asymptotic regime; simply differentiating a local delay approximation would not establish these global claims. When M≍NM N, constructing the initial M directions can dominate the reported excess cost and must be restored when discussing total runtime or total construction complexity. D.8 Transfer to mean-square output error Let the input second moment K⪰0K 0 be known and put B=AK1/2≠0B=AK^1/2≠ 0, as in Corollary 3.2. For each candidate define TK=B⊤BT_K=B B, EK,r=B⊤(I−Pr)BE_K,r=B (I-P_r)B, and HK,r=EK,r−ρTKH_K,r=E_K,r-ρ T_K. The block statistic is computed by replacing each cached response AgiAg_i with A(K1/2gi)=BgiA(K^1/2g_i)=Bg_i. Each such response still costs one forward query to A. The safety and power proofs above apply to these matrices directly; their assumptions use positivity, ordering, and Gaussian probes for the effective operator B. They impose no Gaussian assumption on the actual input distribution. The delay and allocation conclusions apply when this effective operator and its projection path have the spectral-family form analyzed above. This is a condition on B, and does not assert the same delay on every matrix for each prescribed K. The choice K=IK=I recovers the stated diffuse family exactly. Appendix E Experimental Details and Additional Results This appendix specifies the synthetic operators, certification rules, sampling procedures, and statistical conventions used in the numerical experiments. All random candidates are fixed independently of validation. The simulations evaluate the relative squared Frobenius criterion using the exact distribution of Gaussian response statistics. Large operators need not be materialized, and computational timings are not used as a measure of certification cost. The width experiment varies effective dimension together with family size; a separate repeated-check experiment isolates reuse along fixed paths. All logarithms are natural unless a base is explicitly indicated. E.1 Single-candidate confidence exponent For Δ∈1,2 ∈\1,2\, we evaluate the lower bound ps(Δ/2)=ℙFs,s≤e−Δ/2p_s( /2)=P\F_s,s≤ e^- /2\ and the upper bound exp(−sJ) (-sJ), where J=logcosh(Δ/4)J= ( /4). The query grid contains 81 geometrically spaced values from 8 to 4096, rounded to integers, together with 2j2^j for j=3,…,12j=3,…,12. Removing duplicates leaves 87 budgets per value of Δ . These calculations are deterministic and require no Monte Carlo trials. For a numerical cross-check, the same tail probability is computed from the regularized incomplete beta function: ps(Δ/2)=I(1+eΔ/2)−1(s/2,s/2).p_s( /2)=I_(1+e /2)^-1(s/2,s/2). The maximum discrepancy between the two log-probability evaluations is 3.98×10−133.98× 10^-13 over the full grid. Figure 2 displays the finite-query bounds and their normalized exponents. At s=4096s=4096, the normalized exponents are 1.0290071.029007 for Δ=1 =1 and 1.0087541.008754 for Δ=2 =2. Their convergence to one concerns the leading exponential rate; it does not imply that the two finite-query risk bounds have ratio converging to one. Figure 2: Single-candidate bounds. Left: the F-tail lower bound (solid) and exponential upper bound (dashed). Right: −logps(Δ/2)/(sJ)- p_s( /2)/(sJ), with reference value one. The right panel displays budgets s≥64s≥ 64 for readability. E.2 The square-root logarithmic width mechanism This experiment varies the effective dimension together with the number of fixed candidates. It measures simultaneous decisions made by the Gaussian ratio certificate; it does not experimentally establish a lower bound for arbitrary adaptive query algorithms. A fixed finite family with exponentially many paths. Let ℬdB_d be the set of all symmetric d×d× d matrices with zero diagonal and off-diagonal entries in −1,1\-1,1\. The set contains W=2d(d−1)/2W=2^d(d-1)/2 matrices and is fixed before validation. For every B∈ℬdB _d, define DB=Bmaxcd,‖B‖op,KB,0=ρId+aDB,KB,1=KB,0−gId,D_B= B \c d,\|B\|_op\,~~K_B,0=ρ I_d+aD_B,~~K_B,1=K_B,0-gI_d, where c=3c=3, a=1/4a=1/4, ρ=1/2ρ=1/2, and g=0.01g=0.01. Set T=Id/dT=I_d/d and EB,j=KB,j/dE_B,j=K_B,j/d. Since ‖DB‖op≤1\|D_B\|_op≤ 1 and trDB=0trD_B=0, 0⪯EB,1⪯EB,0⪯T0 E_B,1 E_B,0 T and the true ratios are qB,0=ρq_B,0=ρ and qB,1=ρ−gq_B,1=ρ-g. Each B therefore defines a two-candidate ordered path containing both required decision boundaries. Distinct B give distinct EB,0E_B,0 of the same trace, hence an antichain of size W. Together with the displayed chain cover, this proves that the full family has width exactly W. Realization by one operator and nested projections. The energy construction corresponds to actual orthogonal output projections, rather than to arbitrary residual quadratic forms. Let J=[Id,0,0]⊤∈ℝ3d×dJ=[I_d,0,0] ^3d× d and A=J/dA=J/ d. For each B, the matrix VB=[KB,11/2gId(Id−KB,0)1/2]V_B= bmatrixK_B,1^1/2\\ gI_d\\ (I_d-K_B,0)^1/2 bmatrix is an isometry. Extend it to an orthogonal matrix OBO_B with OBJ=VBO_BJ=V_B, and put RB,0=OB⊤diag(Id,Id,0)OBR_B,0=O_B diag(I_d,I_d,0)O_B and RB,1=OB⊤diag(Id,0,0)OBR_B,1=O_B diag(I_d,0,0)O_B. Then RB,1⪯RB,0R_B,1 R_B,0 and A⊤RB,jA=EB,jA R_B,jA=E_B,j. The approximation projectors are PB,j=I3d−RB,jP_B,j=I_3d-R_B,j. An arbitrarily large ambient input dimension can be introduced by replacing A with AV⊤AV , where V⊤V=IdV V=I_d is fixed independently of validation; this leaves all simulated statistics unchanged. The construction illustrates the behavior of Gaussian validation, not oracle hardness of this particular structured operator. An exactly checkable maximum without enumeration. Generate the actual Gaussian sample covariance S=GG⊤/sS=G /s, with G∈ℝd×sG ^d× s standard Gaussian. Both positions of path B have the same estimation offset, q^B,j−qB,j=atr(DBS)trS. q_B,j-q_B,j= atr(D_BS)trS. Write M(S)M(S) for the maximum absolute offset over ℬdB_d. Let B∗(S)B_*(S) have off-diagonal entries sign(Sij)sign(S_ij) and zero diagonal, assigning either sign at zero, an event of probability zero. Deterministically, U(S)min1,cd‖B∗(S)‖op≤M(S)≤U(S),U(S)=a∑i≠j|Sij|cdtrS.U(S) \1, c d\|B_*(S)\|_op \≤ M(S)≤ U(S),~~U(S)= a _i≠ j|S_ij|c dtrS. The upper bound follows by the triangle inequality and the lower bound by evaluating the member B∗(S)B_*(S) of the fixed family. If ‖B∗(S)‖op≤cd\|B_*(S)\|_op≤ c d, the bounds coincide and give the exact maximum. Selecting its maximizing index after validation does not change the pre-existing candidate family. The family contains B and −B-B. Thus, for the midpoint rule q^≤ρ−g/2 q≤ρ-g/2, any incorrect required decision occurs exactly when M(S)≥g/2M(S)≥ g/2, up to zero-probability ties. Every draw retains both bounds and checks the attainment condition. If attainment were to fail, the implementation would retain an interval for the error event rather than discard or replace that draw. All 749568 draws across the experiments below satisfy attainment; the largest observed ratio ‖B∗(S)‖op/(cd)\|B_*(S)\|_op/(c d) is 0.9347120.934712. An additional exhaustive check at d=4d=4, with all 64 matrices and 100 direct Gaussian sketches, verifies the maximum formula. The same implementation explicitly verifies the projection dilation. Why the construction exposes the width mechanism. There are order d2d^2 off-diagonal entries. Their typical individual fluctuation is of order s−1/2s^-1/2, while the denominator in U(S)U(S) has scale d3/2d^3/2. This gives the error scale d/s≍(logW)1/4/s d/s ( W)^1/4/ s. Meeting a fixed additive gap therefore suggests a budget of order d/g2≍logW/g2d/g^2 W/g^2. As a distributional check, the upper envelope has the exact mean U(S)=2a(d−1)cπdsΓ((s+1)/2)Γ(s/2).EU(S)= 2a(d-1)c π d\,s ((s+1)/2) (s/2). Indeed, tr(GG⊤)tr(G ) is independent of the normalized Gaussian direction, and conditioning on one row gives |(GG⊤)ij|=2Γ((s+1)/2)/(πΓ(s/2))E|(G )_ij|=2 ((s+1)/2)/( π (s/2)). The mean identity concerns U(S)U(S) unconditionally; it is not a claim that the attainment condition holds for every possible sketch. Sampling and budget selection. Use d∈8,12,16,24,32,48,64,96,128d∈\8,12,16,24,32,48,64,96,128\. The fixed-budget experiment uses s=4096s=4096 and 4096 independent trials per dimension. The covariance is generated by the exact Bartlett factorization: for lower triangular L, its subdiagonal entries are independent standard normals and Lii2∼χs−i+12L_i^2 χ^2_s-i+1 independently; set S=LL⊤/sS=L /s. Every budget satisfies s≥ds≥ d. Neither asymptotic error nor delay laws are used to generate observations. An initial dimension-independent budget grid consists of the distinct integers ⌈64(1.18)j⌉ 64(1.18)^j , j=0,…,37j=0,…,37, retaining s≥ds≥ d. Each budget receives 768 screening trials. Select the first whose empirical upper failure rate is at most 0.10.1 and evaluate it and its preceding grid point on 4096 fresh trials. This coarse grid revealed a transition too sharp to resolve at factor 1.181.18, so a documented refinement uses 17 logarithmically spaced, rounded budgets between those two grid points. All original observations are retained. Each refined budget receives 1536 fresh screening trials; select the smallest whose pointwise Wilson 95% upper endpoint is at most 0.10.1. That budget and its immediate predecessor receive 8192 new evaluation trials each. The refinement does not use these evaluation outcomes. Pointwise screening intervals are not simultaneous guarantees for the selected budget. Table 1: Width experiment: independently evaluated, screening-selected Gaussian budgets. Error intervals are pointwise Wilson 95% intervals conditional on the selected budget. Here log2W=d(d−1)/2 _2W=d(d-1)/2. d log2W _2W Selected s Error (%) Interval (%) 8 28 1549 8.997 [8.396, 9.636] 12 66 2295 7.715 [7.157, 8.313] 16 120 2941 10.718 [10.066, 11.406] 24 276 4402 8.533 [7.947, 9.157] 32 496 5881 6.348 [5.840, 6.896] 48 1128 8714 6.519 [6.004, 7.074] 64 2016 11521 6.775 [6.251, 7.340] 96 4560 17247 4.626 [4.192, 5.103] 128 8128 23040 2.319 [2.015, 2.668] The reported budgets are selected from a finite grid, rather than being exact minimum budgets at risk 0.10.1. Independent evaluation risks range from 2.32%2.32\% to 10.72%10.72\%; in particular, the point estimate at d=16d=16 exceeds the screening target and is retained. The steepening transition makes even the refined grid conservative at larger dimensions. Over the largest five dimensions, ordinary least-squares slopes against logW W in log–log coordinates are 0.4882680.488268 for selected budgets, 0.2563840.256384 for mean fixed-budget maximum error, and 0.2446990.244699 for its 90th percentile. The corresponding slopes over the largest four dimensions are 0.4926230.492623, 0.2549070.254907, and 0.2455540.245554; fits over all dimensions are also retained. These are descriptive exponents, not confidence intervals. The reference power curves are anchored at d=32d=32 and are not theoretical finite-sample thresholds. Figure 3: The width mechanism on fixed finite families. (a) Mean and 90th-percentile maximum error at s=4096s=4096; mean error bars show ±2± 2 Monte Carlo standard errors. (b) Selected query budgets compared with square-root logarithmic and logarithmic reference slopes. (c) Fresh evaluation of the selected budgets, with pointwise Wilson 95% intervals and the screening target marked. The family width is W=2d(d−1)/2W=2^d(d-1)/2 throughout. E.3 Validation reuse across nested paths Candidate families. Fix effective dimension d=24d=24, ambient input dimension n=65536n=65536, β=0.4β=0.4, ρ=0.5ρ=0.5, and g=0.01g=0.01. For each family, generate 4096 independent rank-d/2d/2 orthogonal projections Qi=UiUi⊤Q_i=U_iU_i , where UiU_i is obtained by reduced QR factorization of a d×(d/2)d×(d/2) standard Gaussian matrix. All projections are generated before any validation samples. Widths W∈1,4,16,64,256,1024,4096W∈\1,4,16,64,256,1024,4096\ use prefixes of this fixed family. For Jchk∈4,32,256J_chk∈\4,32,256\, the checked error levels consist of Jchk−2J_chk-2 equally spaced points in [0.25,0.75][0.25,0.75], together with ρ=0.5ρ=0.5 and ρ−g=0.49ρ-g=0.49, sorted in decreasing order. Their ordered union has K=284K=284 levels q1>⋯>qKq_1>·s>q_K. Set ak=qk−β/2a_k=q_k-β/2 and define the effective energy matrices Teff=Id/d,Ei,keff=(akId+βQi)/d.T_eff=I_d/d,~~E_i,k^eff=(a_kI_d+β Q_i)/d. They satisfy 0⪯Ei,keff⪯Teff0 E_i,k^eff T_eff and have true relative error qkq_k. Realization by nested output projections. The energy matrices above arise from one fixed operator and actual orthogonal output projections. Let a1=0.55a_1=0.55, aK=0.05a_K=0.05, and form the nonnegative block weights w=(β,aK,a1−a2,…,aK−1−aK,1−β−a1).w=(β,a_K,a_1-a_2,…,a_K-1-a_K,1-β-a_1). These weights sum to one. Construct AeffA_eff by vertically stacking wt/dId w_t/d\,I_d for t=1,…,K+2t=1,…,K+2. Fix any V∈ℝn×dV ^n× d with V⊤V=IdV V=I_d, independently of validation, and set A=AeffV⊤A=A_effV . The output dimension is (K+2)d=6864(K+2)d=6864. On path i, the residual projection in the first block is QiQ_i; the second block remains residual, and the last block is always captured. The intermediate difference blocks are captured successively. At level k, the blocks with weights at−at+1a_t-a_t+1 for t<kt<k have been captured and those for t≥kt≥ k remain residual. The resulting approximation projections Pi,kP_i,k are orthogonal and increase along each path, with A⊤A=VTeffV⊤,A⊤(I−Pi,k)A=VEi,keffV⊤.A A=VT_effV ,~~A (I-P_i,k)A=VE_i,k^effV . Different paths generally do not commute. At a common level, distinct residual energy matrices have equal trace and are therefore incomparable in Loewner order. Together with the W-path cover, this gives width exactly W almost surely. Shared Gaussian responses. Since V⊤g∼(0,Id)V g (0,I_d) for an ambient standard Gaussian probe, all required statistics can be generated in effective coordinates. For each trial, draw S=GG⊤/sS=G /s, where G∈ℝd×sG ^d× s has independent standard Gaussian entries, using the equivalent Bartlett factorization S=BB⊤/sS=B /s. Here B is lower triangular, Baa2∼χs−a+12B_a^2 χ^2_s-a+1 for a=1,…,da=1,…,d, and its strictly lower triangular entries are independent standard Gaussians; all these entries are mutually independent. Every tested budget satisfies s≥ds≥ d. The same S is used for all candidates and widths within a trial. The empirical ratio retains its random denominator and satisfies q^i,k=qk+ηi,ηi=β(tr(QiS)trS−12). q_i,k=q_k+ _i,~~ _i=β ( tr(Q_iS)trS- 12 ). Acceptance uses q^≤ρ−g/2=0.495 q≤ρ-g/2=0.495. Because each grid contains both decision frontiers, a simultaneous error is exactly the event mini≤Wηi≤−g/2∪maxi≤Wηi>g/2. \ _i≤ W _i≤-g/2 \\ ∪\ \ _i≤ W _i>g/2 \. Almost surely, this equals maxi≤W|ηi|>g/2\ _i≤ W| _i|>g/2\. The offset is constant along a path, so adding intermediate checks while retaining the frontiers leaves the error event unchanged. This additive offset structure is specific to the experimental family; the theoretical boundary reduction requires only the Loewner ordering. For all trials, widths, and check counts, the grid-specific frontier computation agrees with the common frontier event, giving 258048 consistent comparisons from 12288 independent validation draws. We additionally evaluate every decision on the complete grids for the first eight trials and first sixteen paths of each family–budget setting; these checks also agree. Repeated checks are not additional independent trials. Settings and results. The budgets are s∈512,1024,2048,4096s∈\512,1024,2048,4096\. Three independently generated candidate families are retained. The primary family uses 2048 trials per budget, and the other two use 512 trials each. Table 2 reports all error counts for the primary family; the three check counts produce identical entries. Table 3 compares the families at s=2048s=2048, W=4096W=4096. Figure 4 additionally reports the empirical 95th percentile of maxi≤W|ηi| _i≤ W| _i|. This percentile describes the sampled error distribution and is not a confidence upper bound. Table 2: Primary-family simultaneous error counts out of 2048 trials per budget, identical for all three check grids. The last column is the empirical 95th percentile of maximum absolute error at s=2048s=2048. W s=512s=512 s=1024s=1024 s=2048s=2048 s=4096s=4096 Error percentile 1 82 15 0 0 0.002509 4 366 43 1 0 0.003137 16 1123 187 4 0 0.003767 64 1944 622 11 0 0.004267 256 2048 1517 43 0 0.004746 1024 2048 2025 154 0 0.005131 4096 2048 2048 568 0 0.005550 Table 3: Independent fixed families at s=2048s=2048, W=4096W=4096. Error probabilities and pointwise Wilson 95% intervals are percentages. Family Trials Failures Error (%) Interval (%) 1 2048 568 27.734 [25.839, 29.714] 2 512 156 30.469 [26.640, 34.589] 3 512 139 27.148 [23.477, 31.160] Figure 4: Additional validation-reuse results. Left: empirical 95th percentile of the maximum absolute ratio error, divided by g, for the primary family; the dashed line marks the half-gap decision margin. No interval for the percentile is shown. Right: simultaneous error probabilities for all three fixed families at s=2048s=2048, with pointwise Wilson 95% intervals. Intervals are pointwise Wilson 95% intervals conditional on the fixed candidate family. Families are reported separately rather than pooled. In particular, zero failures among 2048 trials have Wilson upper endpoint 0.0018720.001872 and do not establish zero risk. As a finite-dimensional diagnostic, the maximum error over all rank-d/2d/2 projections is computed from the eigenvalues of the same S: supQ=Q⊤=Q2rank(Q)=d/2β|tr(QS)trS−12|=β(∑a=1d/2λa↓(S)trS−12). _ subarraycQ=Q =Q^2\\ rank(Q)=d/2 subarrayβ | tr(QS)trS- 12 |=β ( _a=1^d/2 _a (S)trS- 12 ). At W=4096W=4096, the median ratio of the finite-family maximum to this supremum is approximately 0.2540.254–0.2560.256 across the tested conditions. The observed families are thus well below this saturation limit. Nevertheless, fixed effective dimension eventually imposes saturation; these experiments do not estimate the dimension-uniform minimax width exponent. The dimension-varying experiment in Section E.2 instead illustrates the square-root logarithmic mechanism for Gaussian validation. Neither ambient embedding is a hardness construction for arbitrary adaptive queries. E.4 Spectral dependence and validation-budget selection Matrices, paths, and cost. Set ρ=0.1ρ=0.1, δ=0.05δ=0.05, and use AM,N=diag(1−ρMIM,ρNIN).A_M,N=diag ( 1-ρMI_M, ρNI_N ). The coordinate path captures the first M directions and then removes the N tail directions individually. The first position with error at most ρ is r⋆=Mr_ =M, and q(PM+j)=ρ(1−j/N)q(P_M+j)=ρ(1-j/N). Both certificates use the same path, and each validation batch is reused throughout it. If τs _s is the first acceptance position, the measured delay is Ds=(τs−M)+D_s=( _s-M)_+ and the cost is N(s)=s+DsC_N(s)=s+ED_s. Thus validation and each additional direction have unit cost, and the initial M construction steps are excluded. All delay expectations are unconditional. By monotonicity, simulating acceptance from rank M onward gives the exact positive delay even when the full-path rule would have accepted earlier. A zero delay includes acceptance at the null boundary q=ρq=ρ and does not distinguish acceptance at M from acceptance before M. These simulations therefore do not estimate the probability of an unsafe pre-target stop. Certification rules. The energy-ratio rule accepts when q^≤θs q≤ _s, where θs=ℓ−1(ℓ(ρ)−2arcosh(δ−1/s)),ℓ(t)=logt1−t. _s= ^-1 ( (ρ)-2arcosh(δ^-1/s) ),~~ (t)= t1-t. Block signs use L=32L=32 predetermined blocks of size b=s/L≥2b=s/L≥ 2. The cutoff is k=6k=6, since ℙBin(32,e−1)≤6=0.022779P\Bin(32,e^-1)≤ 6\=0.022779, whereas the corresponding probability at 7 is 0.054918>δ0.054918>δ. Both rules are calibrated at the same nominal level δ=0.05δ=0.05; the smaller binomial bound reflects the discrete cutoff. Write CℓC_ for captured energy in block ℓ and UℓiU_ i for its tail-coordinate energies. With the shape–scale convention, independent Gaussian probing gives independent variables Cℓ∼Gamma(Mb2,2(1−ρ)Mb),Uℓi∼Gamma(b2,2ρNb).C_ ( Mb2, 2(1-ρ)Mb ),~~U_ i ( b2, 2ρNb ). Let Tℓ=∑i=1NUℓiT_ = _i=1^NU_ i and Rℓ(j)=Tℓ−∑i=1jUℓiR_ (j)=T_ - _i=1^jU_ i. At tail position j, the two decisions are ∑ℓ=1LRℓ(j)∑ℓ=1L(Cℓ+Tℓ)≤θs,∑ℓ=1LRℓ(j)−ρ(Cℓ+Tℓ)≥0≤6. _ =1^LR_ (j) _ =1^L(C_ +T_ )≤ _s,~~ _ =1^L1\R_ (j)-ρ(C_ +T_ )≥ 0\≤ 6. The ratio uses pooled energies, rather than an average of block ratios. Fixed-budget spectral comparison. For N∈512,2048N∈\512,2048\, M∈1,NM∈\1,N\, and s∈128,256,512s∈\128,256,512\, all coordinate energies are sampled explicitly. Each of the 12 settings has 512 trials, with the two certificates sharing the same energies within each trial. Table 4 reports every mean delay and its Monte Carlo standard error. The curves in Figure 5(a,b) show the same data. For M=NM=N, both energy blocks are dispersed; for M=1M=1, the captured energy is concentrated. The reversal of the ordering at M=1M=1 is retained and illustrates that the advantage of block signs depends on the spectrum. Table 4: Complete fixed-budget spectral results: mean positive delay ± one Monte Carlo standard error from 512 paired trials per setting. Adding s gives the mean excess cost without changing its standard error. N M s Energy ratio Block signs 512 1 128 167.21±1.72167.21± 1.72 263.91±2.04263.91± 2.04 512 1 256 125.88±1.35125.88± 1.35 190.37±1.85190.37± 1.85 512 1 512 91.19±1.0491.19± 1.04 135.18±1.41135.18± 1.41 512 512 128 168.72±0.13168.72± 0.13 17.11±0.2217.11± 0.22 512 512 256 125.54±0.09125.54± 0.09 12.50±0.1612.50± 0.16 512 512 512 91.97±0.0791.97± 0.07 8.91±0.118.91± 0.11 2048 1 128 674.96±7.21674.96± 7.21 1066.37±7.901066.37± 7.90 2048 1 256 494.98±5.14494.98± 5.14 768.80±6.84768.80± 6.84 2048 1 512 373.09±4.27373.09± 4.27 557.42±5.69557.42± 5.69 2048 2048 128 673.62±0.24673.62± 0.24 33.61±0.4533.61± 0.45 2048 2048 256 500.01±0.19500.01± 0.19 23.79±0.3123.79± 0.31 2048 2048 512 366.63±0.15366.63± 0.15 16.98±0.2216.98± 0.22 Exact large-scale delay sampling. The allocation experiment fixes M=NM=N and uses N=2jN=2^j for j∈12,15,18,21,24,27,30j∈\12,15,18,21,24,27,30\. Conditional on their total, independent equal-scale Gamma tail energies have Dirichlet proportions. For one sign block, draw Gc,Gt∼iidGamma(Nb2,2Nb),C=(1−ρ)Gc,T=ρGt.G_c,G_t\ Gamma ( Nb2, 2Nb ),~~C=(1-ρ)G_c,~T=ρ G_t. The normalized tail vector is independent of these totals and has law Dirichlet(b/2,…,b/2)Dirichlet(b/2,…,b/2). If FjF_j is its cumulative mass through coordinate j, the block becomes negative when Fj>hsignF_j>h_sign, where hsign=(1−ρ)(1−Gc/Gt)h_sign=(1-ρ)(1-G_c/G_t). Negative thresholds give zero crossings. Across L independent blocks, the certificate delay is the (L−k)(L-k)th smallest crossing time, here the 26th. For the ratio rule, pool all s probes before sampling: Gc,GtG_c,G_t have shape Ns/2Ns/2 and scale 2/(Ns)2/(Ns), and the Dirichlet coordinate parameter is s/2s/2. Acceptance occurs when Fj≥hratioF_j≥ h_ratio, with hratio=1−θs−θs(1−ρ)GcρGt=1−θsρ+θs(1−ρ)ρGt−GcGt.h_ratio=1- _s- _s(1-ρ)G_cρ G_t=1- _sρ+ _s(1-ρ)ρ G_t-G_cG_t. The implementation uses the latter, more stable expression. Strict versus non-strict crossings agree almost surely for these continuous distributions. For a segment containing n0n_0 coordinates with Dirichlet parameter α, its left-half mass, conditional on the segment total, is Z∼Beta(n0α/2,n0α/2)Z (n_0α/2,n_0α/2). If the threshold lies in the left half, update it to h/Zh/Z; otherwise subtract the left half, add n0/2n_0/2 to the coordinate offset, and update the threshold to (h−Z)/(1−Z)(h-Z)/(1-Z). Repeating this conditional split until a single coordinate remains samples the crossing exactly in O(logN)O( N) steps. Consequently, the large-N observations are generated from the finite Gaussian model, without using the asymptotic delay laws as a simulator. Sign and ratio trials in this experiment use independent streams; they are not paired realizations of one cached response matrix. Budget screening and independent evaluation. For each N, both rules use a common geometric grid of budgets s=32bs=32b. Its block sizes are the distinct values round(2j/2)round(2^j/2) for integers j≥2j≥ 2 satisfying 2j/2≤(N+64)/322^j/2≤(N+64)/32, together with the endpoint (N+64)/32(N+64)/32. Thus the smallest budget is 64 and the largest is N+64N+64. There are respectively 14,20,26,32,38,44,5014,20,26,32,38,44,50 budgets at the seven dimensions, for 224 grid points in total. The upper endpoint follows from Ds≤ND_s≤ N: any s>N+64s>N+64 costs more than the feasible choice s=64s=64. The grid does not use the theoretical optimal validation budget. The ratio search is also restricted to this grid; budgets below 64 and intermediate integers are not searched. Each rule receives 1024 screening trials at every grid point. The budget minimizing its screening mean cost is selected, with ties resolved toward the smaller budget. At that budget, 8192 fresh trials estimate the cost reported in Table 5. No further selection uses the evaluation outcomes. These are independently evaluated grid-selected costs, not exact finite-N global minima. Their standard errors are conditional on the selected budget and do not include screening variability. Table 5: Independent evaluation at screening-selected budgets. Costs are s+Dss+ED_s; entries show means ± one Monte Carlo standard error from 8192 fresh trials. Block signs Energy ratio N Selected s Cost Selected s Cost 2122^12 64 131.40±0.22131.40± 0.22 352 1220.21±0.061220.21± 0.06 2152^15 96 250.26±0.51250.26± 0.51 1440 5054.76±0.095054.76± 0.09 2182^18 192 504.70±1.05504.70± 1.05 5792 20584.19±0.1320584.19± 0.13 2212^21 352 998.34±2.18998.34± 2.18 23168 83098.69±0.1983098.69± 0.19 2242^24 736 1996.60±4.221996.60± 4.22 92672 333937.20±0.27333937.20± 0.27 2272^27 1440 3997.61±8.513997.61± 8.51 524288 1338785.98±0.321338785.98± 0.32 2302^30 2912 7999.00±16.967999.00± 16.96 2097152 5359548.83±0.455359548.83± 0.45 Comparison with the asymptotic laws. For the present parameters, the delay constants are Csign=8.386229C_sign=8.386229 and Cratio=4.405944C_ratio=4.405944. The corresponding continuous asymptotic minimum costs are 3(Csign/2)2/3N1/3,3(Cratio/2)2/3N2/3.3(C_sign/2)^2/3N^1/3,~~3(C_ratio/2)^2/3N^2/3. These expressions provide the reference curves and normalizations; they are not fitted to the observed costs. The cost slopes are obtained by ordinary least squares of log mean evaluation cost against log N over the largest four dimensions. They are 0.3336080.333608 for signs and 0.6678900.667890 for ratios. Using all seven dimensions gives 0.3305090.330509 and 0.6716710.671671. Other fitting windows are retained in the result files. The discrete budget grid produces visible finite-scale effects. At N=4096N=4096, the selected sign budget is the lower endpoint 64. Over the largest four dimensions, the selected ratio budget has slope 0.7333540.733354, even though its evaluated cost has slope 0.6678900.667890. Thus the results support the cost separation but do not provide an equally precise empirical estimate of the budget exponent. These descriptive regressions are not confidence intervals or information-theoretic lower bounds. Figure 5: Additional stopping-cost results. (a,b) All fixed-budget spectral settings, with 512 paired trials per setting. Solid curves use N=2048N=2048 and dashed curves use N=512N=512. (c) Independent evaluation costs divided by the continuous asymptotic minimum within each rule family. (d) The complete screening grid at N=221N=2^21; large markers show fresh evaluation at the selected budgets. Error bars in (a–c) are ±2± 2 Monte Carlo standard errors. All costs exclude construction before the true target. E.5 Sampling checks and reproducibility Implementation checks. For the Dirichlet crossing sampler, the identity ℙD≤j=1−Ih(jα,(N−j)α)P\D≤ j\=1-I_h(jα,(N-j)α), 1≤j<N1≤ j<N, is checked at N=64N=64, α=2α=2, and h=0.37h=0.37, using 100000 samples. The maximum CDF discrepancy is 0.0025040.002504, below the prespecified 99.9% Dvoretzky–Kiefer–Wolfowitz tolerance 0.0061650.006165. At (N,b)=(32,2)(N,b)=(32,2) and (128,8)(128,8), each rule is additionally compared with direct coordinate-energy simulation using 8192 independent trials per sampler. The largest absolute mean difference is 2.1472.147 combined standard errors and the largest empirical CDF discrepancy is 0.0184330.018433. Across 113319012 Beta draws, no endpoint, nonfinite value, invalid normalized threshold, clipping, or resampling was recorded. Threshold updates use extended precision; invalid values cause the sampler to stop rather than silently modify a draw. For reuse, an explicit n=64n=64, d=4d=4 operator verifies projection idempotence, nesting, and the energy and response identities, with maximum algebraic error below 7.3×10−167.3× 10^-16. At d=4d=4, s=16s=16, Bartlett and direct Gaussian sampling are compared using 20000 trials each. The four checked statistics are S11S_11, S12S_12, trStrS, and the rank-half energy fraction. One marginal two-sample Kolmogorov–Smirnov test has p=0.00826p=0.00826; all original diagnostics are retained. An additional implementation check, specified after the unchanged main run, compares the maximum-error statistic at d=24d=24, s=1024s=1024, W=64W=64, using 2048 trials per sampler. It gives KS statistic 0.022460.02246 and p=0.67997p=0.67997. The corresponding error-rate difference is approximately one combined standard error. This supplementary check does not replace or filter any main-experiment outcomes. For a single fixed rank-half projection, tr(QiS)/trS∼Beta(ds/4,ds/4)tr(Q_iS)/trS (ds/4,ds/4) supplies an exact probability benchmark. Not every pointwise 95% interval covers this benchmark; the observed deviations are retained without changing seeds. All saved means, standard errors, error counts, and selected budgets for these experiments were independently reconciled with the raw arrays. For the new width experiment, the exact upper-envelope mean provides an additional distributional check: across the nine fixed-budget settings, the largest absolute discrepancy between the empirical and exact mean is 2.2862.286 Monte Carlo standard errors. The exhaustive maximum and projection-dilation checks are described in Section E.2. Random streams and software. The fixed-budget spectral experiment uses NumPy seed 20260920, iterating over N, then M, then s in the orders listed above. Reuse family seeds are 240901, 240902, and 240903. Validation uses SeedSequence([740901,f,s]), with zero-based family index f; candidate and validation streams are separate. The explicit projection check uses seed 991002, and the two Gaussian sampler checks use SeedSequence([991001,j]), with j=0,1j=0,1 for the original check and j=2,3j=2,3 for the supplementary check. Allocation streams use SeedSequence([202609214731,phase,N,s,method]), where method is 1 for signs and 2 for ratios, and phase is 10 for screening and 20 for evaluation. Separate phases 1–3 are reserved for sampler checks. Random streams for the width experiment use SeedSequence([202609220731,phase,d,s]), with phases 10 and 20 for coarse screening and evaluation, 11 and 21 for refined screening and evaluation, and 30 for fixed-budget sampling. The algebraic checks use seed 202609220732. The archive contains every sampled maximum bound and attainment diagnostic, the unfiltered coarse and refined results, and plotting code. The code uses Python 3.12.14, NumPy 2.3.5, SciPy 1.17.0, Matplotlib 3.10.8, and threadpoolctl 3.6.0. The reuse and width simulations use batches of 128 and four BLAS threads.