PaperlayerView exact revision on arXiv

Source-linked AI summary

Information Limits of Low-Rank Approximation Certification

Kang Liu, Bohao Qu

arXiv:2610.03321v1math.OCcs.AIcs.ITmath.IT

TL;DR

Deciding whether a low-rank approximation meets its error target can require costly additional matrix–vector products. The paper analyzes certification costs and reuses validation responses across candidate paths, establishing query bounds and comparing the stopping costs of two certificate rules.

  • Problem

    For low-rank approximations accessed through matrix–vector products, the number of queries needed to reliably determine whether error meets a target—and the unavoidable cost of doing so—must be understood.

    Source: §1 · p. 1

  • Method

    The paper analyzes Gaussian residual-probe certificates, constructs hard operator families for lower bounds, and reuses validation responses across independently constructed approximation families.

    Source: §1 · p. 1, §7 · p. 7

  • Results

    One batch certifies an entire nested path, simultaneous certification across W paths has an optimal √log(W + 1) dependence, and two uniformly valid rules yield excess costs of orders N^2/3 and N^1/3 on a common dispersed-spectrum family.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results characterize information requirements for certification and show that stopping costs depend on the certificate rule within the studied family.

    Source: §1 · p. 2

    The guarantees require candidate families independent of validation, exclude candidate-evaluation arithmetic cost, and the stopping-cost separation is within two specified rule families rather than an optimality result over all certificates.

    Source: §5.2 · p. 6, §7 · p. 7

Abstract

from arXiv · show

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 https://anonymous.4open.science/r/Low-rank-approximation-1275/

1 Introduction

Low-rank approximation can save computation and storage, but deciding when its error meets a target may require costly additional matrix–vector products. This paper characterizes the query cost of certification, reuse across approximation paths, and the construction delay associated with validation.

1 Introduction

  • Certification asks how many matrix–vector products suffice to reliably accept approximations below a target and reject those at or above it.The paper considers relative squared Frobenius error and relative mean-square output error, assuming a known input second moment for the latter.Source: §1 · p. 1
  • For one approximation, Gaussian probing gives a sufficient query budget, and a matching lower bound covers adaptive procedures.In the worst case over matrices of arbitrary dimensions, the bounds have the same leading constant as the allowed failure probability tends to zero.Source: §1 · p. 1
  • One validation batch supports an entire nested expansion path without increasing the query budget with the number of checks.Across W paths, the paper gives an optimal √log(W + 1) dependence for fixed interior error targets and sufficiently small gaps.Source: §1 · pp. 1–2
  • On a common dispersed-spectrum family, optimizing validation budgets gives excess costs of orders N^2/3 for the energy-ratio test and N^1/3 for the block-sign certificate.These costs count validation and construction beyond the true target, and the comparison is within the two rule families.Source: §1 · p. 2
  • The paper’s three contributions are an exact single-candidate confidence constant, an optimal width dependence for shared validation, and a stopping-cost separation between two uniformly valid rules.Low-rank approximations represent high-dimensional operators with a small set of basis directions and coefficients; the appropriate rank is often unknown.Source: §1 · pp. 1–2

2 Related Work

The related-work discussion situates certification alongside adaptive low-rank approximation, stochastic trace estimation, and methods for reusing information across simultaneous guarantees. It distinguishes the paper’s matrix–vector oracle and shared-residual structure from prior lines of work.

Adaptive low-rank approximation

  • Adaptive range finding, incremental factorizations, numerical-rank estimation, blockwise deflation, and matrix-free residual indicators address approximation construction and stopping.The paper instead studies certification of a supplied approximation and the additional construction incurred while waiting for a reliable stopping decision.Source: §2 · p. 2

Residual estimation and oracle model

  • Residual-energy certification relates to stochastic trace estimation, while Hutch++ and XTrace combine low-rank approximation with residual sampling or exploit exchangeability and spectral structure.The paper’s oracle returns the full vector Av, revealing ∥Av∥2 but not directly providing A⊤Av; its bounds concern relative error under this oracle.Source: §2 · p. 2

Shared information and simultaneous guarantees

  • Dynamic trace estimation and parameter-dependent estimators reuse information, while supremum bounds for matrix-indexed quadratic processes capture dependencies between estimates.Here the stated structure is a common envelope 0 ⪯ Ei ⪯ T together with ordered residuals along each path.Source: §2 · p. 2

3 Optimal Certification of a Single Approximation

The section formulates certification as a two-decision problem for a supplied approximation and studies its query complexity. Gaussian residual probing supplies certificates, while hard operator families establish matching information limits, including for mean-square output error.

3.1 Problem formulation

  • Certification uses the fraction of Frobenius energy outside the retained output space and must distinguish error at or above ρ from error at or below ρ − g.Decisions in the intervening region are unrestricted; a query returns the full output vector, and directions may adapt to prior responses.Source: §3.1 · pp. 2–3

3.2 Gaussian certification and optimality

  • Gaussian residual probing estimates error from cached responses, and the certificate compares log-odds of estimated and true error using a midpoint threshold.Upper bounds condition on a construction stage independent of validation probes; lower bounds charge for all operator observations available to the procedure.Source: §3.2 · p. 3, §3.1 · p. 3
  • The minimax query bounds have the same exponential rate, yielding the stated exact high-confidence query constant for single-approximation certification.The certificate analyzes residual and captured energy jointly, without assuming independence between their estimates.Source: §3.2 · p. 3
  • For fixed interior ρ, taking the high-confidence limit before g ↓ 0 gives leading cost 32ρ^2(1 − ρ)^2g^-2 log(1/δ); its g^-2 dependence provides the precision scale for the multiple-approximation problem studied next.Source: §3.2 · p. 3
  • For known input second moment K, probing with K^1/2g_i certifies relative mean-square output error, with the same minimax risk when the worst case ranges over admissible K.The input distribution need not be Gaussian.Source: §3.2 · pp. 3–4

4 Reusing Validation Across Approximation Paths

Validation responses can be reused when candidate approximations are fixed independently of those responses. Nested paths admit a budget independent of their lengths, while simultaneous certification across paths has an optimal width dependence driven by shared residual energy.

4 Reusing Validation Across Approximation Paths

  • The candidate family must be constructed independently of validation probes, although validation outcomes may guide traversal and final selection within that family.The guarantee is simultaneous correctness of all required decisions, protecting a selection made using those outcomes.Source: §4 · p. 4

4.1 Repeated checks along a nested path

  • On a nested path, residual energies and their estimates decrease, so correctness reduces to checking at most two boundary approximations.Applying the single-approximation result gives a query budget independent of the number of checks.Source: §4.1 · p. 4

4.2 Optimal cost of comparing multiple paths

  • For path width W, the shared-energy concentration bound and matching lower bound establish an optimal √log(W + 1) dependence for fixed interior targets and sufficiently small gaps.The family’s chain cover describes the instance class; the certification procedure need not compute it, and the lower bound permits adaptive forward queries.Source: §4.2 · pp. 4–5
  • The upper bounds extend to mean-square output error for every given K, and the corresponding minimax lower bounds hold when the worst case ranges over known second moments.The extension uses B = AK^1/2, which preserves residual ordering and implements each probe with one forward matrix–vector product.Source: §4.2 · p. 5

5 Certification Delay in Iterative Approximation

The section studies how validation budget trades off against construction after the true error target has been reached. It establishes uniform safety for two certificates and compares their stopping costs on a dispersed-spectrum family.

5 Certification Delay in Iterative Approximation

  • The stopping-cost objective adds validation queries to expected construction beyond the first position reaching the true target.Validation is paid once, while construction before that target is excluded; early acceptance contributes zero delay and is controlled separately.Source: §5 · p. 5

5.1 Uniform safety and spectrum-dependent power

  • For q ≥ ρ, the energy-ratio rule accepts with probability at most δ, with a threshold margin of Θ(s^-1/2) as s grows.The margin is calibrated uniformly over spectra, and a boundary reduction extends the guarantee to false stopping anywhere along the path.Source: §5.1 · p. 5
  • For b ≥ 2, the block-sign rule accepts with probability at most δ whenever q ≥ ρ, including at positions along an independently constructed nested path.Its pathwise guarantee follows because each block statistic, and thus the count of nonnegative blocks, is nonincreasing along the path.Source: §5.1 · p. 6
  • The block-sign cutoff depends only on L and δ, while its below-target acceptance probability depends on block-statistic fluctuations and therefore on spectral structure.Spectral structure affects power but is not an input to calibration.Source: §5.1 · p. 6

5.2 A separation on the same spectral family

  • The delay comparison concerns one coordinate expansion path that adds directions one at a time after the first M directions, with both certificates using the same operator and reliability level.For mean-square output error, the rules use transformed responses A(K^1/2 g_i); the delay comparison applies when the effective operator and expansion path have the stated spectral structure.Source: §5.2 · p. 6
  • The two uniformly reliable rules have optimized costs of orders N^1/3 and N^2/3, respectively, on the specified dispersed-spectrum family.The comparison assumes M/N→κ∈(0,∞), fixed parameters, and optimization within the two rule families; construction before the true target is excluded.Source: §5.2 · p. 6

6 Numerical Experiments

The experiments examine the single-candidate confidence exponent, shared-validation width dependence, and spectral effects on stopping cost. Their results align with the predicted exponent and cost growth, while showing that the stopping-cost ordering depends on spectral structure.

Single-candidate confidence exponent

  • At s = 4096, the normalized confidence exponents for Δ = 1 and Δ = 2 are 1.029 and 1.009, respectively, approaching the predicted leading exponent of one.The experiment evaluates the F-tail lower bound for the single-candidate result.Source: §6 · p. 7

Shared validation and the width mechanism

  • Over the largest five dimensions, selected shared-validation budgets have log–log slope 0.488 against log W, close to the predicted 1/2 dependence.At fixed s = 4096, mean maximum error has slope 0.256, consistent with the predicted (log W)^1/4/√s scale; these were screening-selected budgets, not exact minima at a common error probability.Source: §6 · p. 7

Spectral structure and stopping cost

  • At N = 2048 and s = 128, dispersing energy over M = N directions gives mean additional construction costs of 673.6 steps for the ratio certificate and 33.6 for block signs.Concentrating the energy in one direction (M = 1) reverses the ordering.Source: §6 · p. 7

Numerical experiments

  • Over the largest four dimensions, grid-selected cost exponents are 0.334 for block signs and 0.668 for the ratio certificate, agreeing with predicted N^1/3 and N^2/3 growth.The costs exclude construction before the true target and are optimized within the two specified rule families.Source: §6 · p. 7

7 Conclusion and Limitations

The paper characterizes certification information for relative error in iterative low-rank approximation, including single-candidate and shared-validation guarantees and a stopping-cost separation. Its guarantees require candidate families independent of validation, and its stopping-cost comparison is limited to two rule families.

7 Conclusion and Limitations

  • The guarantees require candidate families independent of validation, and the stopping-cost separation concerns excess work within two specified certificate families rather than total runtime or optimality over all certificates.Extending the guarantees to candidates constructed using validation responses remains open; query complexity excludes arithmetic costs of evaluating candidates.Source: §7 · p. 7

AI Use Statement

The appendix formalizes the oracle model and develops Gaussian concentration and simulation arguments for upper and lower bounds on low-rank approximation certification. It also reports the authors’ use of generative AI for proofreading, auxiliary reference review, and drafting and checking an appendix section.

AI Use Statement

  • Generative AI tools were used for typographical checks, auxiliary reference review, and drafting and checking the appendix’s sampling-checks and reproducibility section.The authors state that they take full responsibility for the content.Source: AI Use Statement · p. 7

A Proofs for Single-Approximation Certification

  • The proof appendix states that it establishes Theorem 3.1 and Corollary 3.2 through an explicit oracle model, a joint Gaussian bound, and a matching information bound.Its Gaussian innovation argument allows arbitrary positive definite output covariance and also applies to simultaneous certification.Source: A Proofs for Single-Approximation… · p. 10

A.1 Oracle model and dimension-uniform risk

  • Certification distinguishes matrices with residual error at least ρ from those at most ρ − g; procedures make at most s forward matrix–vector queries, and the minimax risk is uniform over dimensions.The procedure’s decision has no prescribed value between the two error regions.Source: §A.1 · p. 10

A.2 A joint exponential moment bound

  • For positive semidefinite energy forms, the joint Gaussian bound controls a log-ratio without requiring independent estimates; orthogonal rank-one forms attain equality.The result supplies the concentration tool used in the certificate analysis.Source: §A.2 · pp. 10–11

A.3 The Gaussian certificate

  • The Gaussian certificate compares residual and captured energy estimates from cached probes and has a uniform upper bound on both decision errors, including exact endpoint classification.The proof handles dependence between the estimates caused by their shared Gaussian inputs.Source: §A.3 · pp. 11–12

A.4 The exact F tail and its prefactor

  • For orthogonal rank-one energy forms, the log-ratio has an exact F-distribution tail whose exponential rate is sharp; the finite-sample exponential bound remains the upper-bound calibration.The exact tail is used below as a testing lower bound.Source: §A.4 · pp. 12–13

A.5 Gaussian innovations under adaptive queries

  • Adaptive forward-query transcripts under Gaussian matrix priors can be simulated from the procedure’s seed and s independent covariance observations through a map that does not depend on the covariance.This reduces transcript-based decisions to tests on those observations without restricting the original procedure to scalar energy statistics.Source: §A.5 · pp. 13–14

A.6 Two covariance hypotheses and finite-dimensional leakage

  • Two determinant-one Gaussian covariance hypotheses yield a testing lower bound for adaptive procedures; the argument keeps priors Gaussian through simulation and accounts for leakage outside the certification regions.The optimal equal-prior error for the simulated observations is the F-tail probability.Source: §A.6 · pp. 14–15

A.7 Minimax risk, confidence asymptotics, and the small gap

The dimension-uniform minimax query cost has a sharp high-confidence asymptotic, with a specified order of limits for its small-gap form. The lower bound is uniform over input dimensions, not a positive lower bound for every fixed dimension.

A.7 Minimax risk, confidence asymptotics, and the small gap

  • As δ ↓ 0, the optimal query budget s⋆(δ; ρ, g) diverges, and matching upper and lower inequalities determine its high-confidence asymptotic.The upper bound is s⋆(δ; ρ, g) ≤ ⌈log(1/δ)/J⌉.Source: §A.7 · p. 15
  • 32ρ^2(1 − ρ)^2g^-2 log(1/δ) is the leading cost when the confidence limit is taken before the gap limit.The iterated-limit statement does not assert uniformity over arbitrary joint limits of g and δ.Source: §A.7 · p. 16
  • The dimension-uniform lower bound takes n → ∞ at fixed query budget and separation before taking the separation parameter to zero.For fixed n, querying all n coordinate vectors recovers A exactly, so this is not a positive lower bound once s ≥ n.Source: §A.7 · p. 16

A.8 Mean-square output error

The appendix extends certification to mean-square output error and develops reusable validation guarantees for independent candidate families. It reduces pathwise checks to boundary candidates and combines Gaussian concentration with a shared energy envelope, while specifying assumptions on the candidate family and target.

A.8 Mean-square output error

  • For known finite K, mean-square output error is a ratio of expectations, and its dimension-uniform minimax risk equals the Frobenius certification risk.The expectation in the target is over inputs; the certification error probability is over probes, and the equality is a worst case over known K, not every prescribed K.Source: §A.8 · p. 16

B Proofs for Validation Reuse and the Shared-Energy Upper Bound

  • The pathwise analysis fixes ρ and g before the sketch and assumes the complete candidate family is independent of validation probes.The required decisions reject qE ≥ ρ and accept qE ≤ ρ − g; no decision is prescribed between them.Source: B Proofs for Validation Reuse and the… · p. 16

B.1 Two boundary candidates per chain

  • At most two boundary candidates per Loewner chain suffice to determine whether all required decisions are correct; countable families follow by finite exhaustion.For decreasing paths these are the last unsafe member and first sufficiently accurate member; the reduction relies on Loewner ordering.Source: §B.1 · p. 17

B.2 The exact confidence constant for a fixed number of paths

  • For width W, the log-odds midpoint threshold gives the fixed-width high-confidence calibration, with matching leading cost for fixed W.The single-candidate lower bound applies because singleton families are included among families of width at most W.Source: §B.2 · pp. 17–18

B.3 Gaussian concentration facts

  • The concentration toolkit includes bounds for Gaussian quadratic forms and Gaussian singular values.The singular-value bounds are invoked when their lower threshold is positive; otherwise positive semidefiniteness controls the lower covariance deviation.Source: §B.3 · p. 18

B.4 Uniform concentration under a shared energy envelope

  • With a shared positive-semidefinite energy envelope, s ≥ 256H_M(α)/ε^2 guarantees simultaneous additive accuracy ε for M candidates.H_M(α) = √log(2M) + log(5/α).Source: §B.4 · pp. 19–20

B.5 Applying uniform concentration to the boundary family

  • The arithmetic midpoint threshold ρ − g/2 maximizes the smaller additive margin to the promise endpoints and supports a simultaneous-certification budget.The uniform concentration result is applied once to the boundary family rather than followed by another union bound over its members.Source: §B.5 · p. 21

B.6 Independent families and validation-dependent visits

  • Validation-dependent visits and selection are allowed when the complete candidate universe was fixed independently of validation, but a realized short path alone is insufficient.The boundary reduction also applies to the specified fixed ρ and g; it does not guarantee simultaneous validity for a target selected after observing the sketch.Source: §B.6 · p. 22

B.7 Reuse for mean-square output error

Known input second moments allow mean-square output-error certification to reuse the Frobenius framework and its cached validation responses. The matching lower-bound transfer applies to the joint worst case over second moments, not necessarily to each fixed second moment.

B.7 Reuse for mean-square output error

  • For known K, transforming the operator by K^1/2 preserves Loewner chains, so a width-W cover remains a cover by at most W chains.The condition tr TK > 0 handles singular K in this argument.Source: §B.7 · p. 22
  • Cached queries B g_j = A(K^1/2 g_j) cost one forward query each and support all candidate projections when K and the complete family are independent of validation.The actual input distribution need not be Gaussian; only its known second moment enters the target.Source: §B.7 · p. 22

C Adaptive Lower Bounds for Simultaneous Certification

  • The lower bounds transfer when the worst case ranges over known second moments, because that class contains K = I_n; this does not establish the same bound for every fixed K.The appendix lower-bound argument allows arbitrary adaptive forward-query procedures.Source: §B.7 · p. 22, C Adaptive Lower Bounds for… · p. 22

C.1 The task and the dimension-uniform quantifiers

This section establishes dimension-uniform limits for simultaneous certification and specifies the calibrated threshold’s guarantees: false acceptance is controlled for each fixed candidate, with the same guarantee extending to false stopping along an independent ordered path.

C.1 The task and the dimension-uniform quantifiers

  • A lower bound already holds for finite families of fixed orthogonal residual projectors, and its numerical constant is not optimized.Source: §C.1 · p. 23

C.2 A subspace packing with quadratic log cardinality

  • For W ≥16, a packing provides exactly W rank-d/2 projectors with d ≤24√log W.The construction uses Haar concentration on SO(k) to obtain a packing with quadratic log cardinality.Source: §C.2 · pp. 23–24

C.3 A covariance family with exactly one acceptable candidate

  • The covariance construction makes exactly one candidate acceptable, while keeping every hypothesis’s total population energy and determinant equal.Candidate i has residual ratio ρ −2g; all other candidates have ratios at least ρ +2g.Source: §C.3 · pp. 24–25

C.4 Transferring covariance information to adaptive queries

  • Adaptive queries reveal no more label information than at most s independent N(0, Σi) vectors, even with private randomness, redundant queries, or early stopping.A simulator produces the transcript from those vectors and the query rule, which does not depend on the unknown covariance.Source: §C.4 · p. 25

C.5 A uniform finite-dimensional leakage bound

  • 128(M + 1)/(ng²) bounds the finite-dimensional leakage probability across M candidates under the stated Gaussian prior.For fixed M and g, this bound vanishes as input dimension n increases, transferring population separation to realized matrices.Source: §C.5 · p. 26

C.6 Decoding and the width-dependent query lower bound

  • Decoding the unique accepted candidate yields a width-dependent query lower bound for families of width W, using both safety and completeness.For W ≥16, the proof selects M = W; the constructed residual projectors are pairwise incomparable and have width exactly W.Source: §C.6 · pp. 26–27

C.7 The confidence term and all integer widths

  • The confidence lower bound applies for every integer width, including W <16, and rules out zero queries at the required error level.The scope is a worst-case lower bound on total counted forward information, not a claim that every width-W family is difficult or that the bound holds at each fixed input dimension.Source: §C.7 · p. 28

D.1 Notation, stopping rules, and probability space

  • Validation probes are independent standard Gaussians, and the complete nested residual path and its construction randomness are independent of those probes.Cached responses Ag_i suffice to compute the block statistics; parameters and thresholds are fixed before validation data are observed.Source: §D.1 · p. 28
  • The distributions and expectations of D_s are unconditional, and r⋆ includes the boundary q = ρ, where safety calibration still controls acceptance.These probabilities are not conditioned on the absence of an early false acceptance.Source: §D.1 · p. 29
  • For every fixed candidate with q ≥ ρ, the rule’s acceptance probability is at most δ; q = 0 and q = 1 cause no undefined-logarithm issue.The threshold satisfies 0 < θ_s(δ) < ρ, and the sampled ratio equals q almost surely at the endpoints.Source: §D.1 · p. 29
  • Along an independent ordered path, the same probability bound controls false stopping anywhere on the path.The argument uses decreasing bq_r and an unsafe-prefix bound.Source: §D.1 · p. 29

D.2 Log-concavity and the exact block-sign calibration

The block-sign calibration gives a dimension-uniform lower bound of e^-1 on the chance that a Gaussian block statistic is nonnegative when its matrix has nonnegative trace. The bound is uniformly sharp, and independent blocks yield a safe binomial cutoff that remains valid along a nested path.

D.2 Log-concavity and the exact block-sign calibration

  • The block-sign rule rejects when the count reaches the prescribed cutoff, with an empty-cutoff convention that guarantees safety but not eventual acceptance.The cutoff is defined through a lower-tail probability for Bin(L, e^-1).Source: §D.2 · p. 29
  • Log-concavity gives the calibration: a nondegenerate log-concave variable has probability at least e^-1 of lying at or above its mean.The block statistic has a log-concave density by Gaussian diagonalization and convolution, and its mean is tr(H).Source: §D.2 · pp. 29–30
  • For b ≥2 and tr(H) ≥0, a Gaussian block statistic is nonnegative with probability at least e^-1, and this constant is uniformly sharp.Sharpness is established across dimensions and block sizes using b = 2; it is not asserted for each fixed b > 2.Source: §D.2 · pp. 29–30
  • With L independent blocks, the count of nonnegative statistics stochastically dominates Bin(L, e^-1), supporting the cutoff kδ(L) for safety.If the cutoff's defining set is empty, the rule rejects identically; that convention is excluded from stopping-time and allocation results requiring eventual acceptance.Source: §D.2 · pp. 29–30
  • Along a nested path, block statistics and their nonnegative count are nonincreasing, so the single-candidate error bound controls the whole unsafe prefix.The finite-prefix argument extends to a countable path by continuity of probability from below; the ratio rule has the same pathwise safety argument.Source: §D.2 · p. 30

D.3 Finite-sample power without spectral inputs

The section analyzes finite-sample power and delay behavior of sign and ratio validation rules on a common spectral family, including their global allocation orders, transfer to mean-square output error, and numerical evaluation. It also reports close numerical agreement between finite-query bounds and normalized exponents approaching one, without implying the same for the risk-bound ratio.

D.3 Finite-sample power without spectral inputs

  • For a fixed candidate with tr(H) = −d < 0, block-sign validation can attain both error probabilities at most δ with a sufficient finite budget, while d and v_H characterize power but are not decision-rule inputs.For a given budget, the block count can be chosen using δ alone; the spectral quantities are not needed to set the acceptance threshold.Source: §D.3 · p. 30

D.4 The common spectral family and its exact block representation

  • On the common coordinate path, the target rank is exactly M; exact delay constants require inspecting every tail position in order, though skipping positions retains the safety guarantee.The path is a truncated singular-vector path only under the stated singular-value ordering condition; that ordering is not otherwise required.Source: §D.4 · p. 31

D.5 The pure sign rule: crossing limit and convergence of means

  • With M/N → κ ∈ (0, ∞) and block size b = o(N), the sign-rule delay has an exact crossing limit, and its expectations converge to a finite, strictly positive constant.The result holds even for bounded block sizes; the block count L and cutoff k are fixed as dimensions and block size vary.Source: §D.5 · p. 32

D.6 The ratio rule on the same diffuse family

  • For the ratio rule, when s → ∞ and s = o(N^2), the scaled delay converges to its stated positive constant, with convergence of means; at fixed s, delay instead scales with N.At a common budget s = Lb → ∞ with fixed L and b = o(N), both rules’ mean delays are those stated in equation (4).Source: §D.6 · pp. 33–34

D.7 Global optimization over integer validation budgets

  • The two global allocation conclusions establish Theorem 5.2’s cost and budget orders; when M ≍ N, constructing the initial M directions can dominate excess cost and must be included in total runtime or construction complexity.Source: Every sequence of global integer… · p. 36

D.8 Transfer to mean-square output error

  • For known input second moment K, the safety and power results transfer by applying Gaussian probes to the effective operator B = AK^1/2, and the delay and allocation results transfer when B and its projection path have the analyzed spectral-family form.This condition is on B and does not imply the same delay for every matrix under a prescribed K; K = I recovers the diffuse family.Source: §D.8 · p. 36

E Experimental Details and Additional Results; E.1 Single-candidate confidence exponent

  • The experiments fix candidates independently of validation and evaluate the relative squared Frobenius criterion using exact Gaussian-response distributions; the single-candidate confidence-exponent bounds are computed deterministically without Monte Carlo trials.The width experiment varies effective dimension and family size, while a separate repeated-check experiment isolates reuse along fixed paths.Source: E Experimental Details and Additional… · p. 36, §E.1 · p. 36

E.1 Single-candidate confidence exponent

  • At s = 4096, the normalized exponents are 1.029007 for Δ= 1 and 1.008754 for Δ= 2; convergence to one concerns the leading exponential rate, not the ratio of finite-query risk bounds.The maximum discrepancy between the two log-probability evaluations is 3.98 × 10−13 over the full grid.Source: §E.1 · p. 36

E.2 The square-root logarithmic width mechanism

The experiments examine how validation costs vary with width and spectral structure, including the square-root logarithmic trend, reuse of checks across a pathwise error event, and distinct certificate cost-growth rates on dispersed spectra. They also report algebraic, distributional, and implementation checks, retaining observed deviations and using separate random streams and archived diagnostics for reproducibility.

E.2 The square-root logarithmic width mechanism

  • 0.488268 was the selected-budget log–log slope against log W over the largest five dimensions, while the mean maximum-error slope was 0.256384.The fixed-family midpoint-rule error occurs exactly when the maximum absolute offset reaches g/2; the empirical slopes are descriptive, not finite-sample thresholds.Source: §E.2 · pp. 37–39

E.3 Validation reuse across nested paths

  • Adding intermediate checks while retaining both decision frontiers leaves the simultaneous error event unchanged for the constructed paths.Across 258048 comparisons, grid-specific frontier computations agreed with the common frontier event; fixed effective dimension eventually imposes saturation, so these experiments do not estimate the dimension-uniform minimax width exponent.Source: §E.3 · pp. 40–41

E.4 Spectral dependence and validation-budget selection

  • The ordering of the two certificates reverses at M = 1, showing that the block-sign advantage depends on the spectrum.The fixed-budget comparison used paired trials on the same sampled energies; when M = N, both energy blocks are dispersed, whereas at M = 1 the captured energy is concentrated.Source: §E.4 · p. 42
  • N^1/3 and N^2/3 are the respective asymptotic minimum-cost orders for sign and ratio certificates on dispersed spectra.The observed cost slopes over the largest four dimensions were 0.333608 for signs and 0.667890 for ratios; these descriptive regressions are not lower bounds, and the selected ratio-budget slope was less precise.Source: §E.4 · p. 43

E.5 Sampling checks and reproducibility

  • 0.002504 was the maximum CDF discrepancy in the Dirichlet crossing-sampler check, below its prespecified 0.006165 tolerance.Across 113319012 Beta draws, no endpoint, nonfinite value, invalid normalized threshold, clipping, or resampling was recorded.Source: §E.5 · p. 43
  • The n = 64, d = 4 reuse operator’s maximum algebraic error was below 7.3 × 10−16, verifying projection, nesting, energy, and response identities.At d = 4, s = 16, 20,000-trial Bartlett and direct Gaussian sampler comparisons yielded one marginal KS p = 0.00826; a supplementary d = 24, s = 1024, W = 64 check gave statistic 0.02246 and p = 0.67997.Source: §E.5 · p. 43
  • For a fixed rank-half projection, tr(QiS)/tr S has an exact Beta(ds/4, ds/4) benchmark, and observed deviations from pointwise 95% intervals were retained.The deviations did not lead to changing seeds.Source: §E.5 · p. 43
  • Means, standard errors, error counts, and selected budgets were independently reconciled with raw arrays.The archive includes sampled maximum bounds, attainment diagnostics, unfiltered coarse and refined results, and plotting code.Source: §E.5 · p. 44
  • Across nine fixed-budget width settings, the largest empirical-versus-exact upper-envelope mean discrepancy was 2.286 Monte Carlo standard errors.The exhaustive maximum and projection-dilation checks are described in Section E.2.Source: §E.5 · p. 44
  • Separate candidate and validation streams were used, with specified seeds and software versions for the reuse and width simulations.The code used Python 3.12.14, NumPy 2.3.5, SciPy 1.17.0, Matplotlib 3.10.8, and threadpoolctl 3.6.0; simulations used batches of 128 and four BLAS threads.Source: §E.5 · p. 44
Loading 2610.03321v1…