Unverified 2026

Warm-start hit-and-run augmentation

Implementation & benchmark of arXiv:2608.13487 — Hit-and-Run Mixes as Fast as the Ball Walk

Usefulness5/10
Difficulty5/10
Novelty7/10

Source paper: Hit-and-Run Mixes as Fast as the Ball Walk arXiv:2608.13487 ⓘ · analyzed Sep 1, 2026

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

Idea description

Replace rejection sampling or short biased random walks inside a convex latent constraint set with hit-and-run. At each step, choose a uniformly random direction and sample uniformly along the entire chord through the current point; the paper's mixing result predicts that a chain initialized by a crude approximate sampler becomes close to uniform with only logarithmic dependence on initialization bias and target error.

Formulas

$$T(x,A)=\frac{1}{\sigma(\mathbb S^{n-1})}\int_{\mathbb S^{n-1}}\frac{\lambda\bigl(A\cap I(x,u)\bigr)}{\lambda\bigl(I(x,u)\bigr)}\,d\sigma(u),\qquad I(x,u)=\{x+s u:s\in\mathbb R,\ x+s u\in K\}.$$
$$\tau_{\mathrm{mix}}(M,\varepsilon)=O\!\left(n^{2}\psi_{n}^{-2}\log^{3}\!\left(\frac{M}{\varepsilon}\right)\right).$$
$$\tau_{\mathrm{prior}}(M,\varepsilon)=O\!\left(n^{2}\psi_{n}^{-2}\left(\frac{M}{\varepsilon}\right)^{11}\log^{5}\!\left(\frac{M}{\varepsilon}\right)\right),$$
$$x_{t+1}=x_t+s_tu_t,\qquad u_t\sim\mathrm{Unif}(\mathbb S^{n-1}),\quad s_t\sim\mathrm{Unif}\{s:x_t+s u_t\in K\}.$$

Mathematical statement

The paper studies an isotropic convex body K contained in R^n, meaning K is convex, has uniform measure with mean zero, and has covariance matrix I_n. An M-warm start is a distribution mu_0 whose density satisfies d mu_0/d pi <= M almost everywhere, where pi is the uniform distribution on K. The hit-and-run transition chooses u uniformly from the unit sphere S^{n-1}, computes the chord I(x,u)={x+s u:s in R and x+s u in K}, and chooses the next point uniformly on that chord. The stated guarantee is that the total-variation distance from uniformity becomes at most epsilon after O(n^2 psi_n^{-2} log^3(M/epsilon)) steps, where psi_n is the smallest Cheeger constant over isotropic log-concave probability measures in R^n and psi_n^{-1} is the KLS constant. The earlier comparison bound has polynomial warm-start dependence, O(n^2 psi_n^{-2}(M/epsilon)^{11} log^5(M/epsilon)); the useful transferable property is the replacement of (M/epsilon)^{11} by log^3(M/epsilon). For a non-isotropic feasible region, estimate its mean m and covariance C, transform z=C^{-1/2}(x-m), run the chain in z-coordinates, and map samples back with x=m+C^{1/2}z.

Implementation notes

1. Integration point: add a CPU or GPU sampler before the data-loader collate step, or use it as a latent-augmentation module for a VAE or diffusion model. Define a convex feasible region K in feature or latent coordinates, such as the intersection of box constraints, linear safety constraints, and a trust-region polytope. The sampler outputs augmented vectors that are decoded or fed directly to the network. 2. Pseudocode: estimate the empirical mean m and covariance C of feasible pilot points; whiten z=C^{-1/2}(x-m). Initialize z_0 from a cheap feasible point, truncated Gaussian, or previous minibatch. For t=0,...,L-1, draw g~N(0,I_n), set u=g/(||g||_2+1e-8), compute every scalar interval constraint for z_t+s u, intersect the intervals to obtain [s_min,s_max], draw s~Uniform[s_min,s_max], and set z_{t+1}=z_t+s u. Return x_t=m+C^{1/2}z_t after burn-in and thin every q steps. 3. The paper supplies the chord transition and logarithmic warm-start mixing dependence; estimate m, C, chord endpoints, and effective warmness empirically. Use C+delta I for numerical stability and reject or repair points outside K. 4. First experiment: use a 32- or 64-dimensional VAE latent space on CIFAR-10, constraining augmentations to a convex polytope formed by latent coordinate bounds and linear classifier-margin constraints. Compare hit-and-run against rejection sampling and Gaussian random-walk Metropolis at equal generated samples and wall-clock cost. Measure constraint violations, pairwise diversity, effective sample size, and downstream classifier accuracy. Success is higher effective sample size and validation accuracy at equal sampler time, especially for strongly biased initialization and small target tolerance.

Verification

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.