Common Covariance Geometry and Certification for Brownian Kernel Ladders

Mahdi Mohammadigohari

cs.LGAug 25, 2026

Common Covariance Geometry and Certification for Brownian Kernel Ladders

Authors: Mahdi Mohammadigohari

Organizations: Faculty of Engineering, Free University of Bozen–Bolzano Via Bruno Buozzi 1, 39100 Bolzano, Italy

Abstract

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.

Figures & tables

Role	Objects	Meaning
Adaptive family	$\mathscr{K}_{L}(\bm{x})$ , $\mathcal{A}_{L}(\bm{x})$ , $h_{L,\bm{x}}$	closed Gram family, union of evaluation ellipsoids, and its support function
Common covariance	$\tau_{L}$ , $M_{L}$ , $S_{L}$ , $\Lambda_{L}$ , $\Gamma_{L}^{\mathrm{dom}}$	minimum trace, largest single-kernel trace, diagonal scale, normalized profile, and domination inflation
Gaussian geometry	$W_{G,1}$ , $W_{G,2}$ , $\chi_{L}$	first and second Gaussian support moments and certificate defect
Approximation	$d_{m,L}$ , $\omega_{m,L}$	empirical Kolmogorov width and rank- $m$ covariance profile
Certification	$\tau(\mathcal{F})$ , $\operatorname{sep}_{L}$ , $\Psi_{L,\mathcal{E}}$ , $g_{\mathcal{E}}$	active lower value, separation, resistance relaxation, and computable gap
Finite path	$\Sigma_{s}$ , $K_{s}$ , $\tau_{\mathcal{S}}$ , $\widehat{N}$	covariance path, path Gram matrices, finite envelope, and repaired covariance

Table 1: Principal finite-sample objects.

Regime	Assumptions	Profile / defect	Actual complexity scale	Status
One fixed ladder	one empirical kernel	$\Gamma_{L}^{\mathrm{dom}}=1$ , $\Lambda_{L}^{2}=\operatorname{tr}K/S_{L}$	at most $n^{-1/2}$	deterministic upper certificate
Finite controlled family	$M$ kernels fixed independently of multipliers	common covariance: $\Gamma_{L}^{\mathrm{dom}}\leq\sqrt{M}$	common-envelope $\sqrt{M/n}$ ; direct union can give $\sqrt{\log M/n}$	deterministic upper; not claimed sharp
$k$ repeated locations	exactly $k$ distinct input values	$\Lambda_{L}\leq\sqrt{k}$	$\sqrt{k/n}$	deterministic upper
Hierarchical thresholds	decomposition $(q,H)$ ; reverse also needs stable persistence	$\Lambda_{L}\leq\sqrt{2q(H+1)}$ ; $\chi_{L}\lesssim\sqrt{q(H+1)/\kappa}$ under persistence $\kappa$	near $n^{-1/2}$ for bounded $q$ and logarithmic $H$	upper always under decomposition; reverse conditional
Ordered thresholds	at most $q$ intervals; reverse also needs stability or integrated witness	$\Lambda_{L}\lesssim\sqrt{q}\log n$ ; $\chi_{L}\lesssim\sqrt{q}\log n$ under stated witness conditions	$\sqrt{q}\log(n)/\sqrt{n}$	deterministic or high-probability conditional results
Orthogonal / well-conditioned	orthogonal design, or bounded Gram condition number	$\chi_{L}=O(1)$ and $\Lambda_{L}^{2}\asymp n^{1-2^{1-L}}$	$n^{-2^{-L}}$	deterministic two-sided; certificate tight but rate slow

Table 2: Representative regimes. Gaussian richness means tightness of the common-covariance certificate; it does not by itself mean a fast full-class rate. Radius and input-scale factors are suppressed only in the last column.

Dataset	V7 (%)	Conventional (%)	$\Delta_{\mathrm{conv}}$	Endpoint (%)	$\Delta_{\mathrm{end}}$	Paired conv.
CIFAR-10	79.848	80.022	-0.174	79.924	-0.076	1/5
CIFAR-100	45.516	45.046	+0.470	45.598	-0.082	5/5
EuroSAT	91.059	90.596	+0.463	91.078	-0.019	5/5
Oxford-IIIT Pet	88.651	88.874	-0.223	88.738	-0.087	0/5
Flowers102	80.781	80.478	+0.302	80.781	+0.000	5/5
DTD	59.766	59.457	+0.309	59.809	-0.043	4/5

Table 3: Development mean test accuracy and comparisons over five paired seeds. The conventional column is the best mean among ordinary or Fisher-reweighted RBF and Laplace SVC; the endpoint column is the better mean of identity and full-Fisher Brownian SVC. Deltas are percentage points.

Dataset	V7 (%)	Conventional (%)	$\Delta_{\mathrm{conv}}$	Endpoint (%)	$\Delta_{\mathrm{end}}$	Paired conv.
STL10	93.837	94.025	-0.188	93.915	-0.078	0/5
GTSRB	67.219	66.670	+0.549	67.211	+0.008	4/5
Food101	37.640	37.512	+0.128	37.640	+0.000	3/5
Macro average	–	–	+0.163	–	-0.023	7/15

Table 4: Confirmatory mean test accuracy and comparisons over five paired seeds. The conventional column is the best mean among ordinary or Fisher-reweighted RBF and Laplace SVC; the endpoint column is the better mean of identity and full-Fisher Brownian SVC. Deltas are percentage points.

Panel of Figure 2 — Figure 2: Dataset-level mean differences between V7 and the strongest tuned ordinary or Fisher-reweighted RBF/Laplace SVC. The six development datasets informed V7; the three red entries form the locked unseen suite.

Suite	V7 records	$s>0$	$s=1$	Failures	Min. residual	Max. repair
Development	30	29	14	0	9.999e-11	0.0012
Locked confirmation	15	15	8	0	9.999e-11	6.743e-04

Table 5: Selection and common-covariance certificate diagnostics. Residuals are minimum domination eigenvalues after the explicitly reported identity repair.

Explore similar work

The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems
Aug 9, 2026Ibne Farabi Shihab, Adria Binte HabibMinimax Estimation
Department of Computer Science, Iowa State University, USA · Department of Computer Science & Engineering, Independent University of Bangladesh, Bangladesh
Brownian Kernel Ladders
Jun 14, 2026Mahdi Mohammadigohari, Giuseppe Di Fatta, Giuseppe Nicosia +1Hierarchical Representation Learning Reproducing Kernel Hilbert Spaces
Faculty of Engineering, Free University of Bozen-Bolzano, Via Bruno Buozzi 1, Bolzano, 39100, Italy · Department of Biomedical and Biotechnological Sciences, University of Catania, Catania, 95123, Santa Sofia, 97, Italy · Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, FL 32611, Gainesville, USA
Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests
Sep 19, 2026Zihan ZhangCovariance Estimation Differential Privacy
Department of CSE, HKUST

Aug 9, 2026, cs.LGJ/K move · Enter open · S save

The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems

Ibne Farabi Shihab, Adria Binte Habib

Department of Computer Science, Iowa State University, USA · Department of Computer Science & Engineering, Independent University of Bangladesh, Bangladesh

Minimax Estimation

Open paper AskPDF arXiv

Adaptive procedures must work without nuisance information an oracle may use, such as a gradient scale or smoothness index, and robust procedures may have to answer queries whose coordinate and inspection time are chosen only after the data are seen. Such comparisons are meaningful only when the oracle advantage and validity contract are stated explicitly. We formalize nuisance adaptation via a slice-normalized minimax ratio retaining the worst-case instance within each nuisance slice, and separately define the robustness cost of expanding from one preannounced Gaussian query to arbitrary post-hoc inspection. Our main result is a finite-horizon composition law for Gaussian certification: from M independent coordinates, a familywise certifier protecting every coordinate and time up to T pays optimal normalized squared half-width of order log(eM) + log log(e^eT), within the sample-mean-centered rectangular class. Epoch stitching gives the upper bound; independent Gaussian block increments across coordinates and geometric time scales give a matching lower bound, already holding on a geometric checkpoint grid, forcing quantiles of the realized maximum width so selection and stopping taxes add. Two benchmark regimes complete the picture: unknown gradient scale in online convex optimization has constant cost, while pointwise adaptation over nested Holder classes costs order (log n / log log n)^(s1/(2s1+1)). Cast as model monitoring, the law lets an analyst inspect any of M slice metrics at any data-dependent time: the naive fixed-query band's selected coverage degrades sharply, to 0.30 at M=1 and to zero for M>=10, while the epoch-stitched certifier holds familywise coverage at an additive iterated-logarithm width cost. Experiments put both sharp predictions at risk of refutation; both survive.

Abstract

Explore similar work

The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems

Brownian Kernel Ladders

Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests