Unverified 2026

Support-cutoff sparse polynomial block

Implementation & benchmark of arXiv:2608.13753 — Orbit compression and asymptotic contractivity for symmetric Bohnenblust--Hille inequalities

Usefulness6/10

Difficulty5/10

Novelty8/10

Memory Memory Speedup Generalization Mlp Inference speedup Regularization Embedding Combinatorics Approximation theory Functional analysis Inequalities

Source paper: Orbit compression and asymptotic contractivity for symmetric Bohnenblust--Hille inequalities arXiv:2608.13753 ⓘ · analyzed Sep 1, 2026

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

Idea description

Separate low-support monomials, which involve only a few distinct input coordinates, from high-support monomials in a high-degree symmetric interaction layer. Compute the low-support orbit features exactly and prune, sample, or factorize the high-support tail, using the paper's cutoff scale as the initial sparsity rule.

Formulas

$$s(\alpha)=\left|\{j:\alpha_j>0\}\right|,\qquad L_m\asymp\sqrt{\frac{m}{\log m}}.$$

$$\sum_{s(\alpha)\leq L_m}N_{\alpha}|T_{\alpha}|^{q}=O(m^{-1})\ \text{after the Bohnenblust--Hille power},\qquad q=\frac{2m}{m+1}.$$

$$\text{high-support tail}\ \lesssim\exp\!\left[-c\sqrt{m\log m}\right].$$

$$P_{\mathrm{sparse}}(x)=\sum_{\substack{|\alpha|=m\\s(\alpha)\leq L_m}}N_{\alpha}T_{\alpha}x^{\alpha}+R_{\psi}(x).$$

Mathematical statement

For alpha in N^d with |alpha|=m, define support s(alpha)=|{j:alpha_j>0}|. The paper uses the cutoff L_m asymp sqrt(m/log m): low-support levels receive a support-sensitive coefficient estimate, while the global high-support tail is exponentially small on the scale sqrt(m log m). The extracted result states that the low-support contribution is O(m^{-1}) after taking the Bohnenblust-Hille power and that the remaining tail is exponentially small. In the neural layer, m is interaction degree, d is input dimension, alpha is an exponent vector, N_alpha=m!/prod_j alpha_j! is its orbit multiplicity, and T_alpha is its shared coefficient. The adaptation keeps terms with s(alpha)<=L_m and approximates the rest. The theorem requires assumptions such as bounded inputs and suitable coefficient normalization, so the tail must be measured empirically rather than assumed negligible.

Implementation notes

Add this block after an embedding projection in a permutation-invariant model. Enumerate exponent vectors alpha with |alpha|=m, compute s(alpha), and partition them into A_low={alpha:s(alpha)<=L_m} and A_high={alpha:s(alpha)>L_m}, using L_m=max(1,round(kappa*sqrt(m/log(m+1)))) with kappa selected on validation data. Evaluate all low-support monomials exactly, using N_alpha=m!/prod_j alpha_j! and output sum_{A_low} N_alpha*T_alpha*x^alpha. For the high-support set, first use random feature sampling with probabilities p_alpha proportional to N_alpha*abs(T_alpha), applying importance correction 1/p_alpha; alternatively use a rank-r residual R_psi(x)=sum_l a_l*prod_j f_lj(x_j), where r is much smaller than the number of high-support monomials. Pseudocode: compute the cutoff; build low/high masks; calculate exact low-support features; sample or factorize high-support features; add both outputs. On every batch, estimate the omitted-tail RMS by evaluating a small random subset of high-support terms and compare it with the full output norm. The cutoff scale and exponential-tail form come from the paper, while c and kappa are empirical. Test d=64,m=8 on invariant polynomial regression and a two-layer DeepSets classifier against dense symmetric and fully orbit-compressed baselines. Success is at least 2x inference speed or memory reduction with below 1% validation degradation and stable importance weights.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.