Spectral-Gap Convex Perturbation Sampler

Integrate the sampler into adversarial training or convex data augmentation, not into the unconstrained neural-network weight update. Represent each perturbation as \(\delta\in\mathbb R^n\) and define a convex polytope \(\mathcal K=\{\delta:A\delta\le b\}\), such as an intersection of an \(\ell_\infty\) box, color or feature-budget inequalities, and linear semantic constraints. Estimate a diagonal or low-rank whitening matrix \(W\) from feasible pilot samples; run the chain in \(z=W\delta\) coordinates so the transformed set is approximately isotropic, then map samples back with \(\delta=W^{-1}z\). Initialize at any feasible \(z_0\). At each step draw \(u\sim\mathcal N(0,I)\) and normalize it. For every inequality \(a_i^T W^{-1}(z_k+tu)\le b_i\), compute the allowed interval for \(t\); intersect all intervals to obtain \([t_{\min},t_{\max}]\); draw \(t\sim\operatorname{Unif}[t_{\min},t_{\max}]\); and set \(z_{k+1}=z_k+tu\). This is the paper's Hit-and-Run update. Discard a burn-in and retain every \(s\)-th sample. The exact chord update and theoretical contraction come from the paper; the Poincare constant, covariance, burn-in, and thinning interval are estimated empirically using chain autocorrelation and batch covariance. As a cheap test, use CIFAR-10 with a small ResNet-18 and a 3- to 16-dimensional learned color or feature perturbation polytope. Compare Hit-and-Run against rejection sampling and coordinate random walks at equal sampler evaluations. Measure robust accuracy, clean accuracy, effective sample size, lag autocorrelation, and constraint violations. Success means lower autocorrelation or higher effective sample size at equal sampler cost, followed by improved robust accuracy at equal training FLOPs.