# Support-Budgeted Hamming Polynomial Layer

- ID: 444
- Canonical URL: https://synthcore.org/idea/444/support-budgeted-hamming-polynomial-layer
- API JSON: https://synthcore.org/api/idea/444.json
- API Markdown: https://synthcore.org/api/idea/444.md
- Verification status: mechanism_failed
- Source: [arXiv:2607.05594](https://arxiv.org/abs/2607.05594)
- Category: architecture
- Solves: accuracy, stability, sample-efficiency
- ML areas: mlp, embedding, regularization, training
- Math tags: harmonic-analysis, functional-analysis, combinatorics, probability
- Ratings: usefulness 6/10; difficulty 5/10; novelty 7/10

## Idea description

Replace the first dense layer on q-ary categorical features by a Fourier interaction layer containing only monomials whose coordinate support is at most s. Use a Bohnenblust–Hille-inspired quasi-norm on coefficients, separately for each interaction order, to prevent a small number of high-order interactions from dominating the output. The resulting model has an explicit interaction-order knob and can be tested against a dense MLP at matched parameter count.

## Mathematical statement

The paper works on the finite Abelian group C_q^N, where C_q={omega^0,...,omega^{q-1}}, omega=e^{2 pi i/q}, and the normalized expectation and inner product are E[f]=q^{-N} sum_{x in C_q^N} f(x) and <f,g>=E[f overline{g}]. For k=(k_1,...,k_N) in {0,...,q-1}^N, define the character chi_k(x)=product_{j=1}^N x_j^{k_j}, and define its interaction support supp(k)={j:k_j != 0}, with order |supp(k)|. A degree/order-s component is f_s(x)=sum_{|supp(k)|=s} a_k chi_k(x). The support-sensitive Bohnenblust–Hille principle asserted by the paper can be implemented in the form (sum_{|supp(k)|=s}|a_k|^{p_s})^{1/p_s} <= B_{q,s} ||f_s||_infinity, where p_s=2s/(s+1), ||f_s||_infinity=max_{x in C_q^N}|f_s(x)|, and B_{q,s} is independent of the ambient dimension N. For a network, use this as a coefficient budget or penalty: R_BH=sum_{s=1}^S lambda_s (sum_{|supp(k)|=s}|a_k|^{p_s})^{1/p_s}. The transferable property is dimension-free control indexed by interaction support rather than the number of available coordinates.

## Key formulas

- $$C_q=\{\omega^0,\omega^1,\ldots,\omega^{q-1}\},\qquad \omega=e^{2\pi i/q},\qquad C_q^N=\underbrace{C_q\times\cdots\times C_q}_{N\ \mathrm{times}}.$$
- $$\mathbb{E}[f]=\frac{1}{q^N}\sum_{x\in C_q^N}f(x),\qquad \langle f,g\rangle=\mathbb{E}[f\,\overline{g}].$$
- $$f_s(x)=\sum_{|\operatorname{supp}(k)|=s}a_k\chi_k(x),\qquad \chi_k(x)=\prod_{j=1}^N x_j^{k_j},\qquad p_s=\frac{2s}{s+1},$$
- $$\left(\sum_{|\operatorname{supp}(k)|=s}|a_k|^{p_s}\right)^{1/p_s}\le B_{q,s}\,\|f_s\|_\infty,\qquad \|f_s\|_\infty=\max_{x\in C_q^N}|f_s(x)|,\qquad R_{\mathrm{BH}}=\sum_{s=1}^{S}\lambda_s\left(\sum_{|\operatorname{supp}(k)|=s}|a_k|^{p_s}\right)^{1/p_s}.$$

## Implementation notes

Integrate this as the first feature-mixing layer for data represented by N categorical variables, binary attributes, or token-level indicator features. Encode each variable x_j as a q-th root of unity or as its real and imaginary parts. Choose a maximum interaction order S, usually 2 or 3. Enumerate interaction tuples (j_1,...,j_s) with distinct coordinates and Fourier frequencies k_{j_r} in {1,...,q-1}; omit the constant frequency. The layer computes y=base(x)+sum_{s=1}^S sum_{|supp(k)|=s} a_k product_j x_j^{k_j}, followed by a real projection and normalization. Attach the penalty R_BH to the training objective, using p_s=2s/(s+1); for numerical stability, implement the p_s quasi-norm as (sum_k (|a_k|^2+epsilon)^{p_s/2})^{1/p_s}. If the full interaction list is too large, sample a fixed number of tuples per order, maintain their coefficients in a hashed table, and rescale sampled sums by inverse inclusion probability. Estimate ||f_s||_infinity empirically as the maximum absolute order-s contribution over the current minibatch; optionally clip each order when its empirical coefficient norm exceeds B_hat_s times this maximum. The exact mathematical quantities are the support partition and p_s exponents; B_{q,s} can initially be treated as a tunable constant or estimated from random batch evaluations. First test on synthetic parity/XOR tasks and a small categorical tabular benchmark using a 2-layer MLP baseline with equal parameter count. Compare dense features, unrestricted Fourier interactions, and S=2 or S=3 support-budgeted layers. Success means better validation accuracy or sample efficiency at equal parameters, reduced sensitivity to learning rate, and lower contribution from high-order terms without degradation on tasks requiring only low-order interactions.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built a q=2 Fourier interaction layer with configurable support order, order-wise Bohnenblust–Hille quasi-norm penalty, exact finite-group sanity checks, and matched-parameter parity benchmarks. The coefficient quasi-norm to sup-norm ratios stayed approximately dimension-stable for N=3–8, and the penalty consistently improved Fourier generalization over the unpenalized Fourier model. However, the budgeted layer did not beat the parameter-matched MLP: on 2-way parity it averaged 0.887 validation accuracy versus 1.000 for the MLP, and on 3-way parity it averaged 0.585 versus 0.878, so the claimed overall win was not observed.

### Mechanism check

- Verdict: Built a q=2 Fourier interaction layer with configurable support order, order-wise Bohnenblust–Hille quasi-norm penalty, exact finite-group sanity checks, and matched-parameter parity benchmarks. The coefficient quasi-norm to sup-norm ratios stayed approximately dimension-stable for N=3–8, and the penalty consistently improved Fourier generalization over the unpenalized Fourier model. However, the budgeted layer did not beat the parameter-matched MLP: on 2-way parity it averaged 0.887 validation accuracy versus 1.000 for the MLP, and on 3-way parity it averaged 0.585 versus 0.878, so the claimed overall win was not observed.
- Confidence: 9/10
- Limitations: Only q=2 synthetic parity tasks were tested; no q>2 categorical benchmark, real tabular data, S=3 unrestricted-versus-budgeted support ablation, FLOP/runtime measurement, coefficient clipping, hashed sampling, or systematic hyperparameter tuning was performed. The implementation uses real {-1,+1} characters and a scalar output rather than the full complex q-ary multi-output layer.

## Artifacts

- [experiment.py](https://synthcore.org/code/1304/experiment.py)
- [report.md](https://synthcore.org/code/1304/report.md)
- [Download all files as ZIP](https://synthcore.org/download/1304)

## Disclaimer

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