△ Mechanism confirmed, baseline not beaten 2026

Higher-order Hoeffding interaction regularizer

Implementation & benchmark of arXiv:2608.01364 — U-centering as subset ANOVA: edge regression and higher-order theory

Usefulness7/10

Difficulty6/10

Novelty7/10

Regularization Accuracy Generalization Sample efficiency Loss Regularization Embedding Training Linear algebra Statistics Combinatorics

Source paper: U-centering as subset ANOVA: edge regression and higher-order theory arXiv:2608.01364 ⓘ · analyzed Aug 31, 2026

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

Idea description

Construct differentiable arrays over triples or small r-subsets of examples, remove all lower-order subset effects by an incidence-matrix projection, and penalize or maximize the remaining cross-kernel interaction. This isolates genuinely r-way dependence rather than ordinary pairwise correlation and uses only O(n^r) subset evaluations for fixed r.

Formulas

$$E_r=\binom{[n]}{r},\qquad B_{I,S}=\mathbf 1\{S\subset I\},\quad I\in E_r,\ S\in\binom{[n]}{r-1},$$

$$P_r=I-B(B^\top B)^+B^\top,\qquad \widetilde a=P_r a,$$

$$\operatorname{rank}(P_r)=d_r=\binom nr-\binom n{r-1},\qquad \sum_{I\supset S}\widetilde A_I=0\quad\text{for every }S\in\binom{[n]}{r-1},$$

$$\widehat\theta_r(A,C)=\frac{1}{d_r}\sum_{I\in E_r}\widetilde A_I\widetilde C_I,\qquad \widehat V_r(A)=\frac{1}{d_r}\sum_{I\in E_r}\widetilde A_I^2\ge 0.$$

Mathematical statement

Let E_r=\\binom{[n]}{r} be the set of r-subsets and let a=(A_I)_{I\\in E_r} be a symmetric r-subset array. Define the incidence matrix B in R^{|E_r| x |E_{r-1}|} by B_{I,S}=1 when S is a subset of I; its column span contains effects depending on fewer than r sample labels. The higher-order U-centered residual is \\widetilde a=P_r a with P_r=I-B(B^\ op B)^+B^\ op. For n at least 2r, P_r removes lower-order effects, forces all (r-1)-way margins to vanish, and has rank d_r=\\binom nr-\\binom n{r-1}. For two symmetric kernels A_I and C_I, d_r^{-1}\\langle P_r a,P_r c\\rangle estimates the cross-moment of their r-th Hoeffding components. When A=C, d_r^{-1}\\|P_r a\\|_2^2 is nonnegative and estimates the variance of the highest-order component.

Implementation notes

Use r=3 first, with minibatches of n=32 or 64 examples. Choose two learned representations h(x) and z(x), or two augmented views of each example. For every triple I={i,j,k}, form a symmetric scalar kernel such as A_I=mean_{u in I} ||h_u-mean_{v in I} h_v||^2, and form C_I analogously from z. Enumerate all triples, giving m=binom(n,3) entries. Build the incidence matrix B between triples and pairs, solve the least-squares problem min_b ||a-Bb||^2 using a Cholesky solve or conjugate gradients, and return residual a-Bb. Add lambda times theta_hat_3(A,C) to the training loss to suppress third-order dependence between a representation and a nuisance or augmentation representation; alternatively maximize theta_hat_3 when encouraging compositional interactions. The exact paper machinery is P_r, the zero pair-margin constraints, d_3=binom(n,3)-binom(n,2), and the normalized residual inner product. Compute all subset arrays on each minibatch; tune lambda on validation data. Start on CIFAR-10 with a small MLP or ResNet, comparing this term against covariance and pairwise HSIC regularization at matched batch size and FLOPs. Measure test accuracy under held-out augmentation shifts, nuisance predictability from frozen representations, representation collapse, and regularizer variance. Success is better shift robustness or lower nuisance predictability at equal training loss, with the self-inner-product estimate remaining nonnegative and the minibatch estimator having lower variance than a direct six-sample U-statistic.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: No measurable effect

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 9/10

Built an r=3 higher-order Hoeffding residual using the incidence-matrix orthogonal projector and a normalized self-energy regularizer. The mechanism manifested quantitatively: observed ranks matched C(n,3)-C(n,2), lower-order effects and pair margins were below 1.3e-13, and self-energy followed the predicted quadratic scaling in the array amplitude with zero measured relative error. The scalar nuisance toy task showed identical accuracy, nuisance proxy, weight, and loss for all tested lambda values, so no practical learning improvement was demonstrated.

Agent confidence: 9/10

Baseline: lambda=0: accuracy 0.7635±0.0096, nuisance R2 proxy 0.6644, train loss 0.6368
Idea: lambda in {0.01, 0.1, 1.0}: same accuracy 0.7635±0.0096, nuisance R2 proxy 0.6644, train loss 0.6368; mechanism rank/quadratic predictions matched exactly

Limitations: The downstream experiment is only a scalar toy model, not CIFAR-10 or a neural network; it does not compare covariance or HSIC baselines, held-out augmentation shifts, FLOPs, or estimator variance. The learning sweep was effectively insensitive to lambda, likely because the chosen scalar representation and optimization setup do not expose useful higher-order nuisance structure.

How to run: python3 experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2608.01364) Sep 2, 2026

No significant difference vs. the tuned baseline (−-0.0%, p=1, wins 0 / 8 paired seeds).

Benchmark: Tabular regression (Friedman)
Model: mlp_tiny
Paired seeds: 8
Baseline mean: 13.23
Idea mean: 13.23
Effect (Δ): 0 (−-0.0%; negative = idea better)
Wins: 0 / 8 paired seeds
p-value: 1 (permutation test, 20 000 shuffles)
Smallest detectable effect: ±0.0%
Mechanism: Confirmed ✓
Practical effect: No effect
Baseline tuning: swept over 3 configs

Limitations:

Only the structurally matched built-in tabular track was tested; no vision, sequence, dynamics, CIFAR shift, nuisance-predictability, covariance/HSIC comparison, FLOP, or estimator-variance study was run. The idea sweep evaluated lambda values at the selected baseline learning rate, while learning-rate search-space parity was maintained by evaluating all idea learning rates in the recorded candidate union and all baseline learning rates in the actual baseline sweep.

How to run: python3 bench_stage2.py

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

Stage 2 — Benchmark Aug 31, 2026 latest Failed ✗

Agent confidence: 10/10

Built the r=3 higher-order Hoeffding residual as a differentiable training regularizer for the shared bench mlp_tiny architecture on the tabular Friedman#1 track. The trained-model mechanism signature quantitatively confirmed quartic self-energy scaling with zero relative error. However, the best idea setting was lambda=0; lambda=0.001 and 0.01 were worse on the sweep, and the final paired comparison had no measurable effect, so the idea did not win.

Baseline: Best lr=0.006; test MSE 13.2300 ± 1.8298 over 8 seeds, per-seed [13.4643, 15.9820, 11.2376, 12.5458, 9.8764, 13.7444, 14.4380, 14.5517]. Baseline sweep means: lr 0.0015=19.1115, 0.003=15.9754, 0.006=13.3074.
Idea: Best config lr=0.006, lambda=0.0; test MSE 13.2300 ± 1.8298 over 8 paired seeds. Idea sweep at lr=0.006: lambda=0.001 gave 13.3324 and lambda=0.01 gave 13.4973 on the 4-seed tuning subset. Paired delta=0.0, permutation p=1.0, verdict=no measurable effect.
Mechanism signature: map[confirmed:true max_relative_error:0 observed_energy:[1.2876379489898682 20.60220718383789 329.63531494140625] predicted_energy:[1.2876379489898682 20.60220718383789 329.63531494140625] prediction:For the quadratic triple within-subset kernel, residual self-energy scales as representation amplitude^4. trained_test_mse:16.58521270751953]

Benchmark result