PaperlayerView exact revision on arXiv

Source-linked AI summary

Common Covariance Geometry and Certification for Brownian Kernel Ladders

Mahdi Mohammadigohari

arXiv:2609.29525v1cs.LG

TL;DR

Representation-adaptive kernels form a union of empirical RKHS ellipsoids, for which the paper develops a minimum-trace common covariance. Its exact formulations and Brownian-specific reductions support simultaneous approximation and computational certification, but successful covariance certificates do not establish predictive superiority.

  • Problem

    Representation-adaptive kernels produce a union of empirical RKHS ellipsoids, creating a need for one covariance that remains useful for statistical analysis, simultaneous approximation, and certification.

    Source: §1.1 · p. 3

  • Method

    The paper develops a minimum-trace covariance dominating the unrestricted empirical BKL union, with exact operator and multiplier formulations and Brownian threshold and graph reductions.

    Source: §1.1 · p. 3, §9 · p. 36

  • Results

    All repaired finite-path covariance certificates succeed, but the locked predictive study records 7/15 paired wins or ties against a predeclared 8/15 requirement and fails its confirmatory gate.

    Source: §8.2 · p. 35, §9 · p. 37

  • Takeaways & Limitations

    The common covariance spectrum gives an exact empirical width formula and a transductive subspace for simultaneous approximation of the adaptive union.

    Source: §9 · p. 36

    Common eigenspaces are sample-dependent, and conditional Gaussian reverses require additional regime-specific hypotheses.

    Source: §9 · pp. 36–37

Abstract

from arXiv · show

A representation-adaptive kernel class produces, on a fixed sample, a union of reproducing-kernel Hilbert-space ellipsoids rather than one ellipsoid. We introduce the minimum-trace common covariance that dominates the unrestricted empirical union generated by Brownian kernel ladders and develop its statistical, approximation-theoretic, and computational consequences. The covariance value admits exact formulations through absolutely two-summing operators and covariance-dominated multipliers, and it yields a universal Gaussian-complexity bound. A closed last-layer Dirac-trace reduction and a signed Brownian threshold representation convert the generic covariance problem into threshold, graph-coarea, and effective-resistance geometry. These tools give deterministic depth laws, conditional Gaussian reverses, random-design and perturbation transfers, and an exact empirical Kolmogorov-width formula whose leading covariance eigenspaces approximate the complete adaptive ball simultaneously. Finite contact, active semidefinite programs, verified separation, and a convex resistance-design relaxation provide complementary lower and upper certificates. A finite covariance-indexed Brownian path on frozen representations illustrates the distinction between successful covariance certification and predictive selection: all reported path certificates succeed, whereas the locked predictive study misses one predeclared aggregate criterion. The paper thereby identifies one finite-dimensional covariance object linking unrestricted kernel adaptation, Gaussian geometry, common subspaces, and certifiable computation.

1 Introduction and Main Results

Representation-adaptive kernels create a union of empirical RKHS ellipsoids, motivating a common covariance that can support statistical analysis, simultaneous approximation, and certification. The paper develops exact covariance formulations and Brownian-specific reductions, then studies their statistical regimes and computational certificates.

1.1 The unrestricted adaptive-kernel problem

  • The empirical BKL ball is a union of RKHS ellipsoids, and one minimum-trace common covariance links Gaussian support, simultaneous approximation, and certification.Its spectrum supplies a sample-dependent approximation space for the full adaptive ball, while active constraints support finite certificates.Source: §1.1 · pp. 3–4

1.2 Main contributions

  • The common-covariance value exactly matches the absolutely two-summing norm of the adaptive evaluation operator at finite resolution.A covariance-dominated multiplier formulation provides a second exact characterization; bounded Gaussian defect indicates certificate tightness, not a fast statistical rate.Source: §1.2 · p. 4
  • A closed last-layer Dirac-trace reduction and signed layer-cake identity turn BKL covariance domination into threshold, graph-coarea, and effective-resistance geometry.These reductions connect the problem to set systems and ordered or hierarchical traces.Source: §1.2 · p. 4
  • Orthogonal samples have an explicit depth law, while bounded Gaussian defect can coexist with a slow sign-rich full-class rate; leading common-covariance eigenspaces approximate the adaptive ball simultaneously.Sharper conclusions for repeated, categorical, hierarchical, ordered, and perturbed models require stated occupancy, threshold, conditioning, or margin hypotheses.Source: §1.2 · p. 4
  • Finite Brownian contact matrices determine the exact empirical optimum existentially; active SDPs, verified separation, and resistance design provide complementary certificates.All 45 selected-path covariance certificates succeed, but the locked predictive study records 7/15 paired wins or ties, below its 8/15 requirement.Source: §1.2 · p. 4

1.3 Relation to previous work

  • The novelty claimed is the exact empirical realization of generic theories for unrestricted BKLs and its Brownian-specific geometric, statistical, approximation, and certification consequences.The related-work discussion distinguishes the complete recursive empirical BKL union from finite or parametrised kernel families.Source: §1.3 · p. 5

1.4 Organization

  • The paper proceeds from empirical covariance geometry through operator, multiplier, Brownian-geometric, statistical, approximation, and certification results to a finite computational study.Detailed proofs are integrated in the appendices.Source: §1.4 · p. 5

2 Empirical BKL Covariance Geometry

The section sets conventions for canonical Brownian kernel ladders, then represents their empirical adaptive ball through a finite covariance family. It studies a minimum-trace common covariance and illustrates finite path evaluation separately from certification of the unrestricted family.

2.1 Notation and logical conventions

  • The sample is x=(x1,...,xn), unrestricted covariance matrices act on Rn, and the paper distinguishes exact identities from conditional reverses and relaxations.The common eigenspaces are initially empirical and transductive; certificate tightness does not itself imply a fast learning rate.Source: §2.1 · p. 6

2.2 Canonical Brownian Kernel Ladders

  • When VX={0}, every BKL function and empirical Gram matrix vanishes; otherwise the section proceeds with nonzero VX.The first level is the RKHS of the restricted linear kernel.Source: §2.2 · p. 6

2.3 Empirical Kernel and Trace Families

  • Closing the family of depth-L empirical Gram matrices gives a compact positive-semidefinite covariance family and reduces the complete function-space union to a finite-dimensional covariance problem.The closure is essential because the infimum defining the functional complexity need not be attained.Source: §2.3 · pp. 7–8

2.4 The Minimum-Trace Common Covariance

  • The minimum-trace common covariance exists and dominates every admissible kernel covariance; the normalized common-covariance and domination-inflation profiles are bounded by √n.The covariance defines one ellipsoid containing each admissible kernel ellipsoid.Source: §2.4 · p. 9

2.5 A finite covariance-path model

  • The exact spherical Brownian mixture is a positive-semidefinite depth-two BKL-type kernel, and path Gram matrices can be evaluated without new d-dimensional pairwise products.The finite path is not a certificate for the unrestricted covariance family.Source: §2.5 · pp. 10–11

3 Operator Factorization and Gaussian Geometry

The section identifies the robust minimum-trace covariance with an operator-ideal quantity and gives an exact multiplier-law characterization. It then separates this covariance certificate from standard-Gaussian sharpness, whose gap is quantified by an empirical Gaussian defect.

3 Operator Factorization and Gaussian Geometry

  • The robust minimum-trace covariance value equals the finite-resolution 2-summing norm of the adaptive evaluation operator.The identity is exact, not merely a generic factorization upper bound.Source: §3 · p. 11

3.1 Finite-Family Primal and Dual Programs

  • Finite semidefinite programs approximate the robust profile monotonically from below; an upper certificate requires verifying domination over the complete family.In the finite-family dual, positive semidefinite directional weights may assign mass to different kernels.Source: §3.1 · p. 12

3.2.1 A covariance-dominated multiplier minimax identity

  • The robust covariance profile is an exact minimax value over centred multiplier laws whose second-moment matrices are bounded by the identity.The characterization specifies the covariance information used by the common-covariance relaxation; it is not a supervised-learning excess-risk lower bound.Source: §3.2.1 · p. 12
  • For arbitrary covariance families, covariance domination alone cannot guarantee a reverse bound for the standard Gaussian law.The BKL reverse relies on additional structure from recursive Brownian trace geometry.Source: §3.2.1 · p. 13

3.2.2 Gaussian cotype and the exact Gaussian defect

  • The empirical Gaussian defect quantifies the exact loss when the worst covariance-dominated multiplier law is replaced by the standard Gaussian law.Empirical Gaussian cotype provides a reverse bound, while the defect measures the multiplier-to-Gaussian gap.Source: §3.2.2 · p. 13

4 Brownian Dirac, Threshold, and Graph Geometry

The section reduces Brownian kernel covariance domination to previous-layer traces, then expresses it through signed threshold geometry. Recursive threshold structure and graph-based certificates yield deterministic complexity bounds under stated conditions.

4.1 Reduction to the Closed Last-Layer Dirac Trace Family

  • Top-layer kernel domination is equivalent to domination of Brownian matrices indexed by admissible previous-layer traces, so the final mixing measure disappears.Every top kernel is an integral of these matrices, while each admissible unit atom is itself allowed.Source: §4.1 · p. 14

4.2 Threshold Covariance Representation

  • The Brownian layer-cake representation turns the covariance profile into a continuous aggregation of factorization problems for threshold set systems.Minimum trace, rather than maximum diagonal, is identified as the natural objective for Gaussian average width.Source: §4.2 · p. 14

4.3 Recursive Threshold Factorization

  • The recursive threshold sandwich leaves the full adaptive BKL ball unchanged, expressing its statistical price through signed threshold geometry realizable by the preceding layer.The layer-cake representation retains which coordinates can occur together in signed superlevel sets; the generated signed-threshold family is finite.Source: §4.3 · pp. 14–15
  • Under a bounded-q laminar hierarchy of height H, the full-class rate is O(log n/n), up to the displayed radius factors.The result assumes every preceding-layer signed-threshold set is a union of at most q tree nodes.Source: §4.3 · p. 16
  • When signed-threshold sets are unions of at most q ordered intervals, bounded empirical oscillation gives O(log n/√n) full-class complexity uniformly in depth.The explicit radius exponent tends to zero as L →∞.Source: §4.3 · p. 16
  • The structured hierarchy and ordering conditions are not automatic; unrestricted traces cannot have a uniform bounded-q conclusion.The conditions must be verified from trace geometry or covariance certification.Source: §4.3 · p. 16

4.4 A Graph-Coarea/Effective-Resistance Majorant

  • For SL(x) > 0, any connected positively weighted graph supplies an explicit normalized certificate through deterministic Loewner-order majorization that preserves covariance structure.If SL(x) = 0, every empirical kernel and ΛL(x) are zero.Source: §4.4 · p. 16

5 Deterministic, Random, and Perturbative Regimes

This section characterizes common-covariance bounds across fixed and finite kernel families, orthogonal designs, and random or perturbed samples, including reverse bounds from stable-threshold Gaussian richness and perturbation stability under explicit scale and margin conditions. It develops integrated-profile guarantees for ordered or laminar traces, depth-two models, and random-design transfers, while leaving the amplitude-weighted oscillation of unrestricted recursive Brownian traces unresolved.

5.1 Fixed, Finite, and Repeated-Location Families

  • A single kernel gives common-covariance value 1; finite families admit a shared covariance bound, while repeated locations motivate effective-support variants.The shared bound need not be as sharp as a direct finite-union Gaussian bound, but supplies one spectral approximation object for all family members.Source: §5.1 · pp. 17–18

5.2 Orthogonal Designs: Worst-Case Growth

  • For orthogonal designs, the depth profile approaches the universal maximum order √n as depth increases, making the full empirical union less representable by one low-trace covariance body.The paper contrasts this growth with the fact that each individual ladder remains an RKHS.Source: §5.2 · p. 18

5.3.1 A Brownian stable-threshold Gaussian reverse

  • Stable-threshold Gaussian richness supplies reverse bounds to the covariance certificate; orthogonal designs are tight up to constants, and structured reverses require stable thresholds.A small decomposition dictionary alone does not ensure a large threshold set persists over an interval of nonnegligible length.Source: §5.3.1 · pp. 19–20

5.3.2 Random-design Gaussian richness

  • Each additional Brownian layer takes the square root of preceding Loewner distortion, and well-conditioned designs have bounded or controlled Gaussian richness.The stable-threshold comparison is a sufficient certificate for bounded Gaussian defect, not an equivalent characterization; the exact loss is χ_L.Source: §5.3.2 · pp. 20–21

The empirical Gaussian complexity satisfies

  • High-dimensional isotropic spherical designs are Gaussian rich with high probability, although the resulting sharp full-class rate remains the sign-rich rate.The guarantee holds simultaneously for every depth L ≥ 2 under the stated sample-size condition.Source: The empirical Gaussian complexity… · p. 21
  • Balanced repetitions transfer Gaussian richness from finite latent supports; fixed K yields the usual n^-1/2 rate, while polylogarithmic K gives a near-parametric rate up to polylogarithms.The exact orthogonal scale K = n comes from sampling without replacement, not the iid occupancy result.Source: The empirical Gaussian complexity… · pp. 21–22

5.3.3 Perturbation stability and integrated latent-parameter profiles

  • Matched-sample and stable-threshold comparisons persist under perturbations smaller than the relevant covariance scale and threshold margin, including for noisy random repetitions.The sufficient scale becomes more restrictive with depth; the stated conditions do not establish robustness to generic fixed-size noise.Source: §5.3.3 · pp. 23–24
  • An integrated threshold-domination profile replaces reliance on one stable interval by a trace-cost integral over covariance fields across threshold levels.The passage defines this profile and establishes that admissible fields exist; it does not provide a resulting comparison bound here.Source: §5.3.3 · pp. 24–25
  • The integrated threshold profile sharpens the global decomposition certificate by accumulating threshold mass across levels, remaining informative even when no stable-threshold interval is macroscopically long.Theorem 5.22 gives the integrated threshold sandwich.Source: §5.3.3 · p. 25
  • Under ordered or laminar signed-superlevel structure, Theorem 5.23 bounds trace complexity through amplitude-weighted threshold oscillation, with laminar models depending on tree height.The number of intervals or nodes may grow near zero; the bound uses their amplitude-weighted integral.Source: §5.3.3 · p. 25

5.3.4 Concrete ordered models at depth two

  • At depth two, ray traces have one interval per signed superlevel set, while polynomial feature curves of degree p have at most p components; this bounded oscillation is not claimed for L > 2.The ray example uses q(s) = 1, and the polynomial example uses q(s) = qp.Source: §5.3.4 · p. 26
  • For non-atomic latent-parameter designs satisfying ordered or laminar hypotheses, the corollary transfers the guarantees given bounded U,V and a deterministic witness.Non-atomicity ensures almost-surely distinct latent parameters, but a non-injective γ need not give a non-atomic distribution for X; the unrestricted recursive oscillation remains unresolved.Source: §5.3.4 · pp. 26–27

6 Common Approximation Spaces and Learning Consequences

The common covariance supplies one sample-dependent subspace for simultaneous approximation of the full adaptive BKL ball, with its spectrum describing approximation requirements beyond the trace. Profile-dependent deviation results recover the usual n^-1/2 exponent when Λ_L stays bounded, a condition that cannot hold uniformly over the unchanged full class.

6 Common Approximation Spaces and Learning Consequences

  • The exact empirical Kolmogorov width is characterized by the common-covariance profile, whose leading eigenvectors provide a subspace that approximates the complete adaptive trace body simultaneously.The uniform approximation guarantee is empirical and the subspace does not depend on the target function or on which ladder realizes it.Source: §6 · pp. 27–28
  • Recursive spectral compression controls both statistical width and approximation width, and can be sharper than a trace-only estimate when the recursive covariance has spectral decay.The covariance constructed from threshold geometry dominates every admissible kernel in the ladder family.Source: §6 · p. 28
  • Under a balanced binary hierarchy with bounded tree-node decompositions and equal input norms, the common approximation space can use the constant vector and coarsest discrete Haar wavelets.The hierarchical width avoids the tree-height factor appearing in the trace estimate because it depends on an eigenvalue rather than the sum of eigenvalues.Source: §6 · p. 29
  • Stable disjoint threshold blocks provide a width lower bound, making the m^-1/2 upper rate sharp when their persistence length is comparable to the preceding-layer amplitude.The stated equal-partition case uses M = 2m with m ≥ 1.Source: §6 · p. 29
  • The covariance spectrum supplies a full approximation profile: finite rank permits exact recovery, while exponential eigenvalue decay yields exponential linear approximation.The trace captures only an aggregate statistical scale, not this full approximation spectrum.Source: §6 · pp. 27, 29

6.1.1 Uniform deviation

  • Profile-dependent uniform deviation recovers the n^-1/2 exponent when Λ_L remains bounded, but the orthogonal lower bound rules this out uniformly over the unchanged full class.The squared-loss consequence assumes bounded responses and predictions; no assertion is made for unbounded responses or predictions.Source: §6.1.1 · p. 30

7 Certification and Computational Methods

The section develops finite and convex certificates for the full covariance profile, alongside computational tools for Brownian separation. Exact finite contact is guaranteed, but finding contacts and verifying a global upper bound require distinct procedures.

7.1 Sparse Brownian Contact Certificates

  • The exact profile is determined by at most O(n^2) Brownian matrices from the closed last-layer Dirac trace family, although the finite contact theorem does not locate them.The contact directions identify where the covariance constraints touch the optimal envelope; some contacts may only be limits of realized Dirac kernels.Source: §7.1 · p. 31

7.2 Certified Active-Set Bounds

  • Active semidefinite programs provide monotone lower bounds, while a verified separation bound is required for a valid full-family upper certificate.A local witness can improve the active family but is not itself a global upper certificate.Source: §7.2 · pp. 31–32, Figure 1 · p. 32

7.3 Convex Resistance-Design Upper Certificates

  • A convex resistance-design program supplies a conservative upper certificate with a computable optimality gap, without solving recursive separation.Its stated setup assumes distinct sample locations; repeated locations require occupancy-weighted replication.Source: §7.3 · pp. 32–33

7.4 Brownian Separation Computations

  • Brownian quadratic forms can be evaluated in O(n log n) arithmetic operations after sorting, and their derivatives support ascent under stated non-tie and simple-eigenvalue conditions.Locally optimized witnesses can strengthen an active-set lower certificate, but global separation or a convex certificate is still needed for an upper bound.Source: §7.4 · p. 34

8 Finite Covariance-Path Illustration

On the locked suite, the selected path had a positive macro-average difference but failed its predeclared paired-win criterion. The study selected the path using training-only cross-validation, and all reported finite-path covariance certificates succeeded.

8.1 Training-only path selection

  • Table 3 compares development mean test accuracy over five paired seeds against the strongest conventional control and the better Brownian endpoint.Its deltas are in percentage points.Source: Table 3 · p. 35
  • For fixed training features, labels, split seeds, and candidate grids, cross-validation selects a path pair using only the labelled training sample, not test labels.Candidates share splits, with ties resolved by smaller standard error, then smaller C, then smaller s.Source: §8.1 · p. 35

8.2 Protocol and predictive results

  • The study used frozen 512-dimensional ResNet-18 features and locked STL10, GTSRB, and Food101 before fitting, including their acceptance criteria.Six development datasets informed the selector; each dataset–seed pair used 1,000 training examples, three folds, and five repeats.Source: §8.2 · p. 35
  • +0.163 percentage points on the locked suite, but 7/15 paired wins or ties missed the predeclared 8/15 requirement, so the confirmatory decision was failure.The positive macro-average difference does not alter that decision.Source: §8.2 · p. 35

8.3 Finite-path certificates and interpretation

  • All 45 selected-path certificates succeeded, and 44 selected covariance strengths were strictly positive, but the certificates cover only five chosen path kernels on the empirical anchor.They do not certify the unrestricted recursive BKL family, and the identity repair is not itself a realizable Brownian mixture.Source: §8.3 · p. 36

9 Discussion, Limitations, and Open Problems

The discussion separates exact finite-sample conclusions from conditional Gaussian reverses and computational guarantees. It identifies sample dependence, existential contacts, conservative certificates, and unresolved extensions as boundaries of the results.

Exact conclusions

  • At finite sample size, the minimum-trace covariance and its two-summing and covariance-dominated multiplier formulations are exact, and its spectrum gives empirical widths and a transductive subspace.Finite contact is exact but existential.Source: §9 · p. 36

Conditional conclusions

  • Gaussian reverses require additional conditions, and a bounded Gaussian defect establishes certificate tightness rather than a parametric full-class learning rate.Orthogonal and high-dimensional spherical samples illustrate this distinction.Source: §9 · pp. 36–37

Computational conclusions

  • Finite active SDPs give lower certificates; verified global separation or resistance design gives upper certificates, while local witness search alone does not verify global separation.In the finite path illustration, certificates succeed even though the locked predictive gate fails, so the two require separate evaluation.Source: §9 · p. 37

Open problems

  • Open problems include population and out-of-sample common covariances, global separation relaxations, and protocols for supervised metrics and additional learning settings.The current eigenspaces are sample-dependent, the contact theorem does not locate contacts, and the resistance certificate may be conservative.Source: §9 · p. 37

A Proofs for Empirical Trace Geometry

The appendix proves empirical trace geometry by reducing RKHS evaluation to finite-dimensional Gram-matrix geometry, then extending the result to the closure of realized ladders. It also derives recursive evaluation-scale estimates from Brownian kernel identities.

A.1 Recursive Diagonal Scale and Empirical Covariance Body

  • The Brownian diagonal identity supplies a recursive evaluation scale, while induction and the RKHS evaluation inequality extend the resulting bounds across ladder levels.The appendix also establishes a recursive Hölder estimate using the Brownian metric identity.Source: §A.1 · pp. 37, 38, 40
  • For a fixed RKHS and sample Gram matrix, the evaluation operator has covariance equal to that Gram matrix, yielding a pseudoinverse description of the unit-ball evaluation ellipsoid.Projection onto the span of sample kernel sections preserves evaluations and cannot increase the RKHS norm.Source: §A.1 · pp. 38–39
  • The adaptive empirical trace body is obtained by taking the closure of the union of ellipsoids from actual ladders, using approximation by realized ladders and continuity of the matrix square root.The proof first relates each realized ladder's unit RKHS ball to its Gram-matrix ellipsoid.Source: §A.1 · p. 39

B Proofs for Absolutely Two-Summing Duality

The proof connects finite-family semidefinite duality to an absolutely two-summing supremum, then extends the equality to the full compact kernel family.

B Proofs for Absolutely Two-Summing Duality

  • The finite primal and dual values coincide by Slater’s condition, and the dual value is shown to equal the supremum over admissible sequences.The proof establishes both inequalities between the dual value and Q, then invokes strong duality.Source: B Proofs for Absolutely Two-Summing… · pp. 40–41
  • For finite subfamilies, the two-summing value equals the supremum of the family’s covariance-envelope values.The proof first shows t* ≤ QL, then proves the reverse inequality by approximating kernels for each admissible sequence.Source: B Proofs for Absolutely Two-Summing… · pp. 41–42
  • Compactness and the finite-intersection property extend finite-subfamily feasibility to the full compact kernel family.Every finite set of kernel constraints admits a common feasible matrix, so compactness yields a matrix feasible for all kernels.Source: B Proofs for Absolutely Two-Summing… · p. 42

C.1 Proof of the Robust Multiplier Minimax Identity

These proofs establish the robust multiplier identity, Gaussian reverse bounds, and Brownian structural reductions. The arguments connect covariance domination to 2-summing sequences, Gaussian seminorms, and threshold representations.

C.1 Proof of the Robust Multiplier Minimax Identity

  • The robust multiplier identity follows by matching a covariance-envelope upper bound with laws generated from admissible 2-summing sequences.The proof constructs covariance-dominated probability measures from admissible sequences and uses the exact 2-summing identity.Source: §C.1 · pp. 42–43

C.2 Proof of the Gaussian Cotype Reverse

  • The Gaussian cotype reverse provides the lower bound in (54), while Theorem 2.4 supplies its upper bound.The proof passes from a second Gaussian moment to a first-moment bound using the Gaussian seminorm estimate.Source: §C.2 · pp. 45–46
  • The proof also establishes that χL(x) is at least 1 and bounded above as stated in (56).It derives the upper bound using the Gaussian reverse and substitutes the robust multiplier identity.Source: §C.2 · p. 47

D Proofs for Brownian Recursive Structure

  • A signed layer-cake identity expresses the Brownian kernel through threshold indicators applied to each coordinate pair.The scalar identity is checked separately for same-sign and opposite-sign inputs, yielding (62).Source: D Proofs for Brownian Recursive… · p. 47
  • The last-layer covariance problem reduces exactly to domination of the closed family of Dirac Gram matrices.The supremum over top kernels equals the supremum over closed trace atoms, and domination extends between mixtures and Dirac matrices.Source: D Proofs for Brownian Recursive… · p. 47

D.1 Proof of the Recursive Threshold-Factorization Theorem

The proof establishes recursive threshold-factorization bounds using threshold-localized covariances and constructs a sign-cube lower bound from the signed two-sided kernel’s anchored RKHS and recursively built unit-sphere atoms. It applies the factorization bounds to tree, interval, graph, and orthogonal-sample regimes, and combines the lower construction with a Gaussian-complexity upper bound to prove Theorem 5.5.

D.1 Proof of the Recursive Threshold-Factorization Theorem

  • The recursive threshold-factorization proof establishes matching upper and lower bounds, with the upper covariance built by integrating localized dictionary covariances.The resulting covariance also yields the stated Gaussian-complexity consequence.Source: §D.1 · pp. 49–50
  • For laminar partition trees, the decomposition parameter and tree height control the covariance bound; when H = O(log n) and q = O(1), the theorem gives its stated logarithmic-depth regime.Each threshold set is a union of at most q dictionary nodes, while each coordinate belongs to at most H + 1 tree levels.Source: §D.1 · p. 51
  • A dyadic interval dictionary decomposes each threshold set that is a union of q intervals into O(q log n) pieces, with coordinate overlap O(log n), yielding the stated interval-regime bound.The construction pads to a power-of-two interval tree and uses maximal dyadic nodes contained in each interval.Source: §D.1 · p. 51
  • For connected weighted graphs, rank-one estimates and the weighted graph coarea identity produce a common covariance majorant and the stated trace and atom bounds.The proof obtains the coarea representation by integrating positive- and negative-threshold contributions.Source: §D.1 · p. 52

E Proofs for Geometric Regimes

  • When sample values repeat, every empirical BKL Gram matrix factors through the distinct sample locations, yielding the stated bound for the duplicate-sample regime.The proof uses an incidence matrix from observations to distinct values and dominates the reduced Gram matrices.Source: E Proofs for Geometric Regimes · p. 53

E.1 Orthogonal Growth Law

  • The two-sided Brownian-kernel RKHS consists of locally absolutely continuous functions vanishing at zero with square-integrable derivative; kernel pullbacks contract RKHS norms.The Brownian feature representation uses disjoint positive- and negative-half-line supports.Source: §E.1 · pp. 53–54
  • For orthogonal samples, the upper-bound recursion starts at β1 = 1/2 and gives βℓ = 1 − 2^-ℓ, bounding the representation dimension by nβℓ.The supplied proof part begins the matching lower-bound argument but does not include its conclusion.Source: §E.1 · p. 55
  • The two-sided kernel has the anchored RKHS and derivative norm of (256)–(257), not the one-sided min(s, t) RKHS.The associated ψ_a is anchored at zero, with derivative b/a on (−a, a) and zero elsewhere.Source: §E.1 · p. 56
  • Recursive unit-sphere atom construction yields a sign cube in the full BKL unit ball, even without an attainment assumption.When the pullback norm q is in (0, 1], dividing by q produces a next-level unit-sphere atom and increases trace amplitude; scalar contraction handles a larger amplitude.Source: §E.1 · p. 56
  • For the stated quantities, the upper bound is bG(e_i)(B_L(1)) ≤ ΛL(e_1, …, e_n)√n, with dependence on the listed e_1 through e_n terms and a √n factor.Source: §E.1 · p. 56

F.1 Proof of the Stable-Threshold Gaussian Reverse

The proofs establish stable-threshold Gaussian lower bounds and Gaussian-richness comparisons using threshold domination and signed layer-cake representations, and extend them to random designs, repeated samples, and perturbations. They also give integrated threshold-profile bounds for ordered-interval and laminar structures and identify conditions supporting these comparisons, including macroscopic stable thresholds, well-conditioned subgaussian designs, and adequate category occupancy.

F.1 Proof of the Stable-Threshold Gaussian Reverse

  • Optimizing over threshold intervals turns threshold domination into stable-threshold reverse bounds for Gaussian width, Gaussian complexity, and the common-covariance certificate.The proof uses signed layer-cake representations to obtain a pointwise support-function lower bound from each stable set.Source: §F.1 · pp. 57–58
  • A macroscopic stable threshold guarantees nonvanishing Gaussian richness; on the orthogonal design, the lower and upper common-covariance Gaussian bounds agree up to universal constants.The proof also uses the macroscopic-threshold lemma to derive the stated comparison factor in Theorem 5.9.Source: §F.1 · p. 59

F.2 Proofs for Random-Design Gaussian Richness

  • One-step domination between actual kernel families transfers through Brownian lifting, and compactness extends the domination to the closed kernel families.The construction maps sphere elements between RKHSs while preserving a positive-semidefinite domination of the next-layer kernels.Source: §F.2 · p. 61
  • For unit-norm isotropic subgaussian designs, a Gram event with condition number at most nine yields Theorem 5.12’s conclusions simultaneously for every depth L ≥ 2.The same event applies across depths, and the unit-norm assumption gives SL(X1:n) = n.Source: §F.2 · p. 64
  • Repeated observations preserve the base design’s common-covariance and stable-threshold comparisons, while category-count concentration transfers the bounds under the stated occupancy conditions.The proof lifts stable subsets across repeated observations and applies multiplicative Chernoff bounds to category counts.Source: §F.2 · pp. 65–66
  • A matching stable-threshold lower estimate completes (134), while the macroscopic-threshold condition enables random-design bounds (132)–(136) on the stated occupancy event.The proof combines a profile upper bound with the stable-threshold lower bound; the later bounds use the high-probability occupancy event and (104).Source: §F.2 · pp. 66–67

F.3 Proofs for Perturbation Stability

  • The perturbation proof establishes bounds (138)–(144) for matched samples, including a relative Gaussian-width comparison under the stated assumptions.The argument uses symmetry, Minkowski’s inequality, and a summed coordinatewise scale bound; applying it to matched samples yields (150).Source: §F.3 · pp. 68–70
  • Threshold sets remain stable after trimming both interval ends by η when δ > 2η, yielding the lower bound (146) and, with relative-error assumptions, comparison (147).When δ ≤ 2η, the lower bound in (146) is zero.Source: §F.3 · pp. 69–70

F.4 Proofs for Integrated Threshold Profiles

  • The proof of (154) establishes lower and upper integrated-threshold bounds and compares the integrated profile with the global decomposition profile.The upper-bound construction integrates an admissible threshold covariance field to obtain a feasible common covariance.Source: §F.4 · pp. 70–72
  • For ordered interval traces, dyadic decomposition and closure over trace limits yield the integrated-profile bound (158).The proof uses a complete dyadic interval tree; almost every signed threshold set is a union of at most q(s) intervals.Source: §F.4 · pp. 72–73
  • For laminar models, the construction bounds trace cost by q(s)(H + 1)|Is|, proving (159) and the witness lower bound (160).The proof uses that each sample index belongs to at most H + 1 tree nodes.Source: §F.4 · p. 73
  • Under a non-atomic law, sampled parameters are distinct almost surely, so the deterministic interval result applies and concentration yields (162).The proof uses Hoeffding’s inequality and a union bound to control failure probability by δ.Source: §F.4 · p. 73

G Proofs for Approximation Widths

The width proofs reduce approximation of the adaptive trace body to orthogonal residuals and connect common-covariance spectra to explicit subspaces. Tree-based results identify Haar eigenspaces and use stable disjoint blocks to bound approximation from below.

G Proofs for Approximation Widths

  • The width proof reduces approximation of the closed adaptive trace body to worst orthogonal residuals, then minimizes over subspaces of dimension at most m.The residual supremum is unchanged when passing to the closure of the radius-r trace body.Source: G Proofs for Approximation Widths · p. 74
  • The common-covariance argument selects the m leading eigenvectors of N*; when m=n, the approximation width is zero.The proof uses that N* dominates every admissible covariance.Source: G Proofs for Approximation Widths · p. 74
  • For a complete balanced binary tree, the constant vector has eigenvalue 2n −1, each internal-node Haar wavelet has eigenvalue s−1, and λm+1(CT) ≤ 2n/(m+1).The constant vector and Haar wavelets form an orthonormal eigenbasis.Source: G Proofs for Approximation Widths · pp. 75–76
  • When each realizable signed threshold set is a union of at most q tree nodes, the resulting trace subspace uses the leading constant and coarse-to-fine Haar modes.The cited proof combines the tree dictionary bound with the balanced-tree spectrum to obtain (174).Source: G Proofs for Approximation Widths · pp. 76–77
  • Pairwise disjoint equal-size stable blocks force a lower width bound for every m-dimensional subspace; with M=2m, each block has size n/(2m).The lower-bound argument uses normalized indicators of the disjoint blocks; for M=2m, the stated factor 1−m/M equals 1/2.Source: G Proofs for Approximation Widths · p. 78

H Proof of the Learning Consequence

This section proves the learning consequence by reducing uniform deviation to the adaptive ball’s Gaussian complexity, and develops finite certificates and computational methods for the covariance problem. It also derives Brownian separation identities and a spherical mixture, establishes exact path evaluation and training-only selection, and clarifies the scope of the finite certificate.

H Proof of the Learning Consequence

  • The proof obtains the learning bound through two-sided empirical Rademacher deviation, Lipschitz contraction, and comparison with Gaussian complexity.The Rademacher complexities of a class and its negative agree; the proof then uses the support function and Jensen’s inequality to compare Rademacher and Gaussian complexities.Source: H Proof of the Learning Consequence · pp. 78–79

I.1 Sparse Contact Certificates

  • An exact finite contact certificate uses at most n(n + 1)/2 + 1 terms and restricts the full covariance problem without changing its optimum.The proof establishes contact equations and a finite dual certificate attaining the full value.Source: §I.1 · pp. 80–81

I.2 Certified Active-Set Brackets

  • Inflating a finite active-set solution by εI_n and scaling by its separation value gives a full-family feasible covariance upper bound.The finite primal values are lower bounds on the full optimum and are monotone as the active constraint sets grow.Source: §I.2 · p. 82

I.3 Convex Resistance Design

  • The resistance-design objective is convex on connected-support weights, and its edge leverage conditions yield a computable optimality gap.The gap is nonnegative and vanishes at an optimizer.Source: §I.3 · pp. 82–84
  • For tree-supported weights, the trace of the Laplacian pseudoinverse is represented by a weighted sum of pairwise effective resistances.The proof counts the vertex-pair paths traversing each edge to derive the tree formula.Source: §I.3 · pp. 84–85

I.4 Brownian Separation Computations

  • Brownian separation reduces to sorting magnitudes within positive- and negative-sign blocks, followed by linear-time suffix sums and summation.The blocks follow from the signed Brownian quadratic form and a scalar layer-cake identity.Source: §I.4 · p. 85
  • Under nonzero and no-tie assumptions, differentiating the separation objective and a simple largest eigenvalue yields identities (207) and (208).Source: §I.4 · p. 86

J.1 Proof of the exact spherical Brownian mixture

  • For uniform spherical Θ, E|⟨Θ,u⟩| = c_d∥u∥₂; the resulting expectation of positive-semidefinite kernels is positive semidefinite.Source: §J.1 · p. 86

J.2 Proof of exact two-basis path evaluation

  • The five path kernels on one anchor sample are evaluated exactly from the identity and Fisher squared components.The kernel is formed from the nonnegative square roots of three affine squared quantities.Source: §J.2 · p. 86

J.3 Proof of training-only selection

  • With fixed split seeds, finite maximization and deterministic tie breaking depend only on the labelled training sample and seeds; no operation reads a test label.Source: §J.3 · p. 87

J.5 Scope of the finite certificate

  • The finite certificate establishes domination only for its five-kernel active family at the reported tolerance, not unrestricted optimality or a global recursive separation oracle.Source: §J.5 · p. 87
Loading 2609.29525v1…