Sparse-interaction Bohnenblust–Hille regularizer

(1) Integration point: use an explicit degree-m interaction layer after an embedding h∈R^n. Store only coefficients c_α whose support size w(α)≤M; the layer output is P(h)=Σ c_α∏_j h_j^{α_j}. This fits a polynomial network, factorization-machine layer, or Volterra block, rather than a standard dense MLP without explicit interaction coefficients. Apply the regularizer once per minibatch or every K optimizer steps.

(2) Pseudocode:

p = 2*m/(m+1)
coeff_norm = (sum(abs(c_alpha)**p for alpha in active_terms))**(1/p)
for r in range(R):
    phase = exp(1j * 2*pi * Uniform(0,1,n))
    probe_value[r] = sum(c_alpha * prod(phase[j]**alpha[j]
                          for j in support(alpha)) for alpha in active_terms)
emp_sup = max(abs(probe_value[r]) for r in range(R))
Khat = A_M**(M/m) * m**((M*M-1)/(2*m))
loss = task_loss + lambda_bh * softplus(coeff_norm/(emp_sup+eps)-Khat)**2

Use complex phases directly, or evaluate real and imaginary parts with paired cosine/sine probes. Normalize h before the interaction layer so the unit-polydisc interpretation is meaningful; alternatively use h/(||h||_∞+ε) per sample.

(3) Computed from the paper: the exponent p, the support restriction w(α)≤M, and the explicit upper-bound schedule Khat. Estimated empirically: the supremum norm, using R random probes. Increase R during validation to test whether the regularizer is being fooled by undersampling. A conservative variant maintains an exponential moving maximum of probe responses. The extracted text does not provide a numerical value for A_M, so initialize A_M=2 or use a fixed safety multiplier q≥1 and report sensitivity to q and R.

(4) First experiment: train a degree-8 or degree-16 polynomial regression/classification network on a synthetic teacher containing sparse interactions of support at most M=2 or 3. Compare an unconstrained coefficient ℓ_2 baseline, ordinary ℓ_p coefficient weight decay, and this BH regularizer at matched parameter count and FLOPs. Measure validation error, worst-case response on 10,000 fresh random phase probes, coefficient-to-response ratio, and gradient-norm variance. Success means lower held-out error or improved phase robustness at equal training loss, with the empirical ratio approaching the predicted Khat rather than growing with degree.