# Support-cutoff sparse polynomial block

- ID: 2260
- Canonical URL: https://synthcore.org/idea/2260/support-cutoff-sparse-polynomial-block
- API JSON: https://synthcore.org/api/idea/2260.json
- API Markdown: https://synthcore.org/api/idea/2260.md
- Verification status: unverified
- Source: [arXiv:2608.13753](https://arxiv.org/abs/2608.13753)
- Category: memory
- Solves: memory, speedup, generalization
- ML areas: mlp, inference-speedup, regularization, embedding
- Math tags: combinatorics, approximation-theory, functional-analysis, inequalities
- Ratings: usefulness 6/10; difficulty 5/10; novelty 8/10

## 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.

## 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.

## Key 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).$$

## 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.

## Disclaimer

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