# Polynomial bounded-independence sampler for augmentation

- ID: 2372
- Canonical URL: https://synthcore.org/idea/2372/polynomial-bounded-independence-sampler-for-augmentation
- API JSON: https://synthcore.org/api/idea/2372.json
- API Markdown: https://synthcore.org/api/idea/2372.md
- Verification status: unverified
- Source: [arXiv:2608.15865](https://arxiv.org/abs/2608.15865)
- Category: sampling
- Solves: sample-efficiency, speedup, stability
- ML areas: data-augmentation, training, diffusion
- Math tags: probability, combinatorics, information-theory, discrepancy
- Ratings: usefulness 5/10; difficulty 4/10; novelty 5/10

## Idea description

Replace iid uniform augmentation draws or Monte Carlo quadrature points by a space-filling k-wise independent point set generated from random polynomials over a finite field. The construction uses far fewer random bits and can reduce integration error whenever the network loss as a function of augmentation parameters has moderate Hardy–Krause variation.

## Mathematical statement

The paper defines the star discrepancy of points P=(x_1,...,x_N) in [0,1)^d by D_N^*(P)=sup_{z in [0,1]^d}|N^{-1} sum_n 1_[0,z)(x_n)-prod_j z_j|. The Koksma–Hlawka inequality states that for a function f of bounded Hardy–Krause variation V_HK(f), |N^{-1}sum_n f(x_n)-integral_[0,1]^d f(x)dx| <= V_HK(f)D_N^*(P). Its main probabilistic guarantee is that k-wise independent uniform points X_1,...,X_N with k=O(d(1+log(1+N/d))) satisfy D_N^*(X_1,...,X_N)=O(sqrt(d/N)) with fixed probability at least u, so N=O(d epsilon^{-2}) and k=O(d(1+log epsilon^{-1})) achieve discrepancy at most epsilon. A finite-field realization is obtained by choosing a field F_q with q>=N, distinct evaluation points alpha_1,...,alpha_N in F_q, independent uniform coefficients a_{ell,r} in F_q for coordinates ell=1,...,d and r=0,...,k-1, defining P_ell(t)=sum_{r=0}^{k-1}a_{ell,r}t^r, and mapping P_ell(alpha_n) to a grid value in [0,1). Any k polynomial evaluations are jointly uniform because a degree-(k-1) polynomial is determined by k values. The sampler consequently uses approximately d*k*log_2(q) random bits rather than d*N*log_2(q) bits for iid grid sampling.

## Key formulas

- $$D_N^*(P)=\sup_{\boldsymbol z\in[0,1]^d}\left|\frac{1}{N}\sum_{n=1}^N\mathbf 1_{[\boldsymbol 0,\boldsymbol z)}(\boldsymbol x_n)-\prod_{j=1}^d z_j\right|.$$
- $$\left|\frac{1}{N}\sum_{n=1}^N f(\boldsymbol x_n)-\int_{[0,1]^d}f(\boldsymbol x)\,d\boldsymbol x\right|\leq V_{\mathrm{HK}}(f)D_N^*(P).$$
- $$k=O\!\left(d\left(1+\log\left(1+\frac{N}{d}\right)\right)\right),\qquad D_N^*(\boldsymbol X_1,\ldots,\boldsymbol X_N)=O\!\left(\sqrt{\frac dN}\right)\ \text{with probability at least }u.$$
- $$P_\ell(t)=\sum_{r=0}^{k-1}a_{\ell,r}t^r,\qquad X_{n,\ell}=\frac{\operatorname{int}(P_\ell(\alpha_n))}{q},\quad a_{\ell,r}\overset{\mathrm{iid}}{\sim}\mathrm{Unif}(\mathbb F_q).$$

## Implementation notes

Integrate the sampler at the stochastic-input layer of a small neural network, not in the optimizer. Start with an image classifier that applies d bounded augmentation parameters per example, such as crop offset, color-jitter strength, blur strength, and cutout location. For each training batch of N augmentation evaluations, generate one fixed polynomial point set X in [0,1)^d and map each coordinate through the augmentation parameter range; use a fresh random polynomial seed once per epoch or per batch group. Pseudocode: choose a prime power q>=N and k=ceil(C*d*(1+log(1+N/d))); sample d*k field coefficients a[ell,r]; choose distinct field points alpha[n]; evaluate P_ell(alpha[n])=sum_r a[ell,r]*alpha[n]^r; set u[n,ell]=integer(P_ell(alpha[n]))/q; transform u[n] into augmentation parameters; compute the batch loss and backpropagate. The polynomial evaluation is the paper-inspired sampling mechanism; C, q, and the probability level u are engineering choices, while discrepancy is estimated empirically by testing many random anchored boxes or by comparing the empirical CDF on a grid. For a first cheap experiment, train a ResNet-18 or ViT-Tiny on CIFAR-10 with four-dimensional continuous augmentation parameters, comparing iid uniforms, Sobol points, and polynomial k-wise points at identical augmentation evaluations and FLOPs. Measure validation accuracy, variance of epoch loss across seeds, number of updates needed to reach a fixed accuracy, and random-bit consumption. A useful success signal is lower loss variance or faster accuracy improvement at equal N; separately test discontinuous augmentations, where the bounded-variation motivation may fail, and verify whether the method still beats iid sampling.

## Disclaimer

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