✓ Mechanism works 2026

Complete-U Moment Regularizer

Implementation & benchmark of arXiv:2608.22962 — Batched and Complete U-Statistics for Trace-Polynomial Estimation from Classical Shadows

Usefulness6/10
Difficulty4/10
Novelty5/10

Source paper: Batched and Complete U-Statistics for Trace-Polynomial Estimation from Classical Shadows arXiv:2608.22962 ⓘ · analyzed Aug 29, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Replace disjoint-pair estimates of embedding covariance moments with a complete U-statistic over every distinct pair in a minibatch. For embeddings z, the degree-two kernel h(z_i,z_j)=(z_i^T z_j)^2 estimates the spectral moment tr(M^2), where M=E[zz^T]; complete symmetrization reduces the degenerate component of estimator variance from O(1/B) to O(1/B^2).

Formulas

$$\Phi_p(A):=\operatorname{tr}p(A)=\sum_{k=1}^{L}a_k\operatorname{tr}(A^k)$$
$$U_B=\binom{B}{2}^{-1}\sum_{1\le i<j\le B}h(X_i,X_j),\qquad \operatorname{Var}(U_B)=\frac{4\zeta_1}{B}+\frac{2\zeta_2}{B(B-1)}$$
$$V_{\mathrm{batch}}=\frac{1}{m}\sum_{r=1}^{m}h(X_{2r-1},X_{2r}),\quad B=2m,\qquad \operatorname{Var}(V_{\mathrm{batch}})=\frac{4\zeta_1}{B}+\frac{2\zeta_2}{B}$$
$$h(z_i,z_j)=(z_i^{\mathsf T}z_j)^2,\qquad \widehat{\operatorname{tr}(M^2)}_{\mathrm{U}}=\binom{B}{2}^{-1}\sum_{i<j}(z_i^{\mathsf T}z_j)^2,\quad M=\mathbb{E}[zz^{\mathsf T}]$$

Mathematical statement

The paper defines Phi_p(A)=tr p(A)=sum_{k=1}^L a_k tr(A^k) and compares disjoint batching with complete U-statistics. For iid samples X_1,...,X_B and a symmetric degree-two kernel h, let theta=E[h(X_1,X_2)], zeta_1=Var(E[h(X_1,X_2)|X_1]), and zeta_2=Var(h(X_1,X_2))-2 zeta_1, where zeta_2 is the variance of the canonical degenerate Hoeffding component. The complete estimator U_B=binom(B,2)^(-1) sum_{i<j} h(X_i,X_j) satisfies Var(U_B)=4 zeta_1/B + 2 zeta_2/[B(B-1)]. If B=2m samples are split into m disjoint pairs, V_batch=m^(-1) sum_{r=1}^m h(X_{2r-1},X_{2r}) has Var(V_batch)=4 zeta_1/B+2 zeta_2/B. Thus the first-order component has the same scaling, while the degenerate component is smaller by approximately a factor B under complete symmetrization. In the neural adaptation, z_i=f_theta(x_i) is an embedding in R^d, M=E[zz^T], and h(z_i,z_j)=(z_i^T z_j)^2, giving E[h]=tr(M^2).

Implementation notes

1. Integration point: add a spectral-moment regularizer to an encoder, projector, or representation model immediately after the embedding tensor z=f_theta(x) is produced. Start with degree two because it is O(B^2) and directly tests the variance mechanism. For z in R^(Bxd), compute the Gram matrix G=z z^T, remove its diagonal, and define U as the mean squared off-diagonal Gram entry. Add lambda*(U-target)^2 when matching a desired second spectral moment, or lambda*U when the goal is to suppress correlation and spectral concentration. 2. Pseudocode: z=encoder(x); G=z @ z.T; off=(G**2)*(1-eye(B)); U=off.sum()/(B*(B-1)); loss=task_loss + lambda*(U-target)2; loss.backward(); optimizer.step(). The baseline uses m=B/2 random disjoint pairs and V=mean((z[2r]^T z[2r+1])2). 3. Compute the paper's predicted variance terms empirically: estimate Var(h) from all off-diagonal pair values, estimate zeta_1 using the variance across i of row means mean_{j!=i} h_ij, and set zeta_2_hat=Var(h)_hat-2*zeta_1_hat. Compare the predicted complete-versus-batched variance with repeated minibatch measurements. 4. First experiment: train a small CIFAR-10 ResNet-18 or MNIST two-layer MLP with identical optimizer, batch size, and regularization coefficient under complete pairs and disjoint pairs. Log regularizer variance, parameter-gradient variance, loss curves, validation accuracy, and wall-clock time. Success is at least 20% lower gradient variance or smoother descent at equal batch size, with no more than 2x overhead and no accuracy loss.

Verification

Mechanism works

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Not tested

Stage 2 · Practical benchmark result: Not run

Methodology: Toy-system gate first; the benchmark stage runs only after a pass. How verification works

Stage 1 — Mechanism check agent confidence 8/10

Built a complete-U versus disjoint-pair spectral-moment regularizer in experiment.py, with analytic/numerical Hoeffding variance verification and matched synthetic regression training. The variance check matched corrected Gaussian predictions closely, and complete pairing reduced regularizer variance by 4.31x with about 1.03x runtime overhead. Total parameter-gradient variance was not reduced, but complete pairing produced better final full-data MSE, so this is a promising regularizer-level win rather than a demonstrated gradient-noise win.

Agent confidence
8/10
Baseline
Disjoint pairs: regularizer variance 0.0004614; gradient trace variance 0.5148; final full MSE 0.4093; 0.466 s.
Idea
Complete U-statistic: regularizer variance 0.0001071 (4.31x lower); gradient trace variance 0.5711; final full MSE 0.2815; 0.481 s. At B=64, empirical/predicted variance was 0.529/0.520 for complete and 1.748/1.750 for disjoint.

Limitations: Only one fixed seed and a small synthetic regression task were tested; no MNIST/CIFAR benchmark, multiple regularization settings, memory profiling, or larger-batch scaling study was performed. The gradient metric includes task-gradient noise, which masked the regularizer variance reduction.

How to run: python3 experiment.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Artifacts

Implementation overview ⬇ Download all as ZIP 3 files · code, reports and structured results