# Isoperimetric Coordinate Hit-and-Run Negatives

- ID: 2776
- Canonical URL: https://synthcore.org/idea/2776/isoperimetric-coordinate-hit-and-run-negatives
- API JSON: https://synthcore.org/api/idea/2776.json
- API Markdown: https://synthcore.org/api/idea/2776.md
- Verification status: unverified
- Source: [arXiv:2608.27854](https://arxiv.org/abs/2608.27854)
- Category: sampling
- Solves: sample-efficiency, stability, accuracy
- ML areas: sampling, vae, world-model
- Math tags: geometry, convex-analysis, probability
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

## Idea description

Use coordinate hit-and-run rather than isotropic Gaussian random walks to generate latent negatives or augmentation trajectories inside a convex latent domain K. At each step, select one coordinate and resample the entire feasible chord along that coordinate; the paper's l0-isoperimetric theorem predicts that sets of non-negligible mass cannot be separated by severe coordinate-only bottlenecks when K is well-conditioned relative to an unconditional body Q.

## Mathematical statement

For a Borel set S contained in K, define its coordinate boundary by partial_0^K S = {y in K minus S: there exists x in S such that y and x differ in at most one coordinate}. If Q is an unconditional convex body in R^n and x_0 + rQ is contained in K, while K is contained in y_0 + RQ, with r,R greater than zero, and s = vol(S)/vol(K) is at most 1/2, the paper proves vol(partial_0^K S)/vol(S) is at least (c r/(n R)) min{1, log(e/s)/n}, where c is an absolute positive constant. The resulting l0-isoperimetric coefficient is at least c r/(n^2 R). The transferable quantity is the guaranteed coordinate expansion: a low-mass region must have a relatively large one-coordinate-reachable boundary. For a box K = [-1,1]^d, use Q = B_infinity^d and r = R = 1. A coordinate chord is C_i(z) = {z + t e_i : t is real} intersected with K, where e_i is the i-th standard basis vector.

## Key formulas

- $$x_{0}+rQ\subset K\subset y_{0}+RQ.$$
- $$\partial_{0}^{K}S=\{y\in K\setminus S:\exists x\in S\text{ such that }y_j=x_j\text{ for all but at most one }j\}.$$
- $$\frac{\operatorname{vol}(\partial_{0}^{K}S)}{\operatorname{vol}(S)}\ge\frac{cr}{nR}\min\left\{1,\frac{\log(e/s)}{n}\right\},\qquad s=\frac{\operatorname{vol}(S)}{\operatorname{vol}(K)},\quad 0<s\le\frac12.$$
- $$z' = z+t e_i,\quad i\sim\operatorname{Unif}\{1,\ldots,d\},\quad t\sim\operatorname{Unif}\{t:C_i(z)=\{z+t e_i\}\cap K\}.$$

## Implementation notes

(1) Integration point: replace the negative-sample or latent-augmentation sampler in a VAE, latent energy-based model, or world model. Let the neural network define an energy E_theta(z) or score on latent vectors z in K. Use K = [-1,1]^d initially, so chord endpoints are computed exactly. Do not change the encoder or decoder in the first experiment. (2) Pseudocode: initialize z from an encoder posterior or replay-buffer latent. For each step, draw i uniformly from {1,...,d}, compute the feasible interval [a_i(z), b_i(z)] satisfying z + u e_i in K, draw u uniformly from that interval, and set z_new = z + u e_i. For a learned target p_theta(z) proportional to exp(-E_theta(z)) on K, use Metropolis-Hastings acceptance min(1, exp(-E_theta(z_new)+E_theta(z)) times q(z | z_new)/q(z_new | z)); compute the proposal ratio from the two chord lengths when they differ. (3) The paper supplies the expansion lower bound and its dependence on r/R, n, and s. Estimate actual mixing empirically using integrated autocorrelation time, cross-chain disagreement, mode coverage, and coordinate-boundary crossing rates. For non-box K, compute chord endpoints with a convex feasibility solver and estimate r/R from known inner and outer bodies. (4) First cheap experiment: train a 2D or 4D latent energy-based model or VAE on MNIST and compare coordinate hit-and-run against Gaussian random-walk Metropolis and iid Gaussian negatives at equal numbers of network evaluations. Measure effective sample size per energy evaluation, mode coverage on a synthetic multimodal target, validation loss, reconstruction quality, FID, and gradient variance. Success means higher ESS and mode coverage at equal FLOPs, followed by lower validation loss or better FID when the sampler supplies training negatives.

## Disclaimer

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