# Algebraically Scrambled Augmentation Batches

- ID: 1575
- Canonical URL: https://synthcore.org/idea/1575/algebraically-scrambled-augmentation-batches
- API JSON: https://synthcore.org/api/idea/1575.json
- API Markdown: https://synthcore.org/api/idea/1575.md
- Verification status: unverified
- Source: [arXiv:2607.29063](https://arxiv.org/abs/2607.29063)
- Category: sampling
- Solves: sample-efficiency, accuracy
- ML areas: data-augmentation, sampling, training
- Math tags: geometry, probability, combinatorics, linear-algebra
- Ratings: usefulness 6/10; difficulty 4/10; novelty 7/10

## Idea description

Generate augmentation parameters from a binary digital net with matrix or linear scrambling instead of independently sampled uniforms or fully Owen-scrambled points. The construction should cover the augmentation hypercube while avoiding the severe local clustering predicted for random and locally independent scrambling, giving each training window a more uniform set of transformation strengths.

## Mathematical statement

For an N-point set P=(x_n) in [0,1]^d, the paper defines the covering radius h_infty(P)=sup_{z in [0,1]^d} min_n ||z-x_n||_infty, the separation radius q_infty(P)=1/2 min_{n<n'} ||x_n-x_n'||_infty, the minimum interpoint distance R_infty(P)=2q_infty(P), and mesh ratio rho_infty(P)=h_infty(P)/q_infty(P). The abstract reports that Monte Carlo and Latin hypercube sampling have rho_infty(P)=Theta_P(N^{1/d}(log N)^{1/d}), while full Owen scrambling of fixed-t digital nets can have rho_infty(P)=Omega_P(N^{1/(2d)}). In contrast, matrix and linear scrambling of binary digital nets with fixed t and d>=2 satisfy rho_infty(P)=O_P(log N). Here P is the set of augmentation vectors, d is the number of continuous augmentation controls, and N is the number of augmentations in a batch or accumulation window. The transferable property is the much smaller probabilistic mesh ratio, not merely low marginal discrepancy.

## Key formulas

- $$h_{\infty}(P):=\sup_{\boldsymbol z\in[0,1]^d}\min_{0\le n<N}\|\boldsymbol z-\boldsymbol x_n\|_{\infty},\qquad q_{\infty}(P):=\frac12\min_{0\le n<n'<N}\|\boldsymbol x_n-\boldsymbol x_{n'}\|_{\infty}.$$
- $$\rho_{\infty}(P):=\frac{h_{\infty}(P)}{q_{\infty}(P)},\qquad R_{\infty}(P)=2q_{\infty}(P)=\min_{n<n'}\|\boldsymbol x_n-\boldsymbol x_{n'}\|_{\infty}.$$
- $$\rho_{\infty}(P)=O_{\mathbb P}(\log N)\ \text{for matrix/linear scrambling},\qquad \rho_{\infty}(P)=\Omega_{\mathbb P}(N^{1/(2d)})\ \text{for full Owen scrambling of fixed-}t\text{ nets}.$$

## Implementation notes

Integrate this at the data-loader or augmentation-policy sampler, before the augmentation operators are applied. Let d be the number of continuous controls, for example crop scale, aspect ratio, color strength, blur, and rotation; map each digital-net coordinate u in [0,1]^d to a legal parameter through an inverse CDF or affine range map. Build a binary digital net of N points using a Sobol-style generator, then apply a random invertible binary matrix to the direction-number bits for matrix scrambling, or a linear digital scramble; do not use independent random coordinates and do not use full Owen scrambling in the first comparison. For every batch window, use a fresh scramble or a nested prefix of one scrambled sequence. Pseudocode: generate bits B[n,j,k]; sample invertible lower-triangular binary matrices A_j; set B'[n,j,:]=A_j B[n,j,:] mod 2; convert bits to u[n,j]=sum_k B'[n,j,k]2^{-k}; transform u to augmentation parameters; apply one vector per example. Compute R_infty exactly on each batch and estimate h_infty by evaluating distances from a 4,096-point uniform probe grid to P. The theorem supplies the qualitative target rho=O_P(log N); h and q are measured empirically. First test on CIFAR-10 with a ResNet-18 and continuous RandAugment-like policies, comparing IID uniforms, Latin hypercube, Owen-scrambled Sobol, and matrix-scrambled Sobol at identical augmentation FLOPs. Success means higher validation accuracy or faster loss reduction at equal optimizer steps, together with larger R_infty and smaller estimated rho_infty.

## Disclaimer

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