Diffusion-DPP Gradient Batches

1. Integration point: modify the data-loader minibatch sampler, not the model. Construct a symmetric weighted k-NN graph from frozen training embeddings, using raw inputs for the first experiment and periodically refreshed encoder embeddings in a later experiment. Set edge weights $W_{ij}=\exp(-\|z_i-z_j\|^2/(2\sigma^2))$, form the normalized Laplacian $\mathcal L=I-D^{-1/2}WD^{-1/2}$, and compute its first $r$ eigenpairs with Lanczos. Form $K_t=U\operatorname{diag}(\exp(-t\lambda_j))U^\top$. 2. Pseudocode: inputs are eigenvectors $U$, eigenvalues $\lambda$, batch size $k$, diffusion time $t$, and rank $r$; set $\ell_j=\exp(-t\lambda_j)/(1-\exp(-t\lambda_j))$; sample a size-$k$ subset of eigenvector indices using elementary-symmetric-polynomial dynamic programming; sample data items with the standard projection-DPP Gram-Schmidt procedure; return indices $S$. Compute inclusion probabilities either exactly with a tested k-DPP marginal routine or approximately by running the sampler repeatedly and caching empirical frequencies. Compute each example gradient $g_i$ and use $g_i/\pi_i$ when unbiasedness is required; also compare unweighted updates. 3. The paper supplies the intrinsic-dimension-dependent energy guarantee. Estimate the graph spectrum, bandwidth $\sigma$, and $\pi_i$ empirically. Choose $t$ by targeting effective rank $\sum_j\exp(-t\lambda_j)\approx 2k$ and clip $\pi_i$ below at $0.05k/N$ to control importance-weight variance. 4. First experiment: train a ResNet-18 on CIFAR-10 with batch sizes 64 and 128, comparing uniform sampling, loss-proportional sampling, and diffusion-DPP sampling at equal examples and equal graph-construction overhead. Measure gradient cosine similarity to the full-dataset gradient, minibatch gradient variance, validation accuracy, and wall-clock time. Success means at least 10% lower gradient-estimation variance or faster validation-loss descent at equal optimizer steps without unstable importance-weighted updates.