Polynomial-time sampling despite disorder chaos

Eric Ma, Tselil Schramm
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:4885-4910, 2026.

Abstract

A distribution over instances of a sampling problem is said to exhibit transport disorder chaos if perturbing the instance by a small amount of random noise dramatically changes the stationary distribution (in Wasserstein distance). Seeking to provide evidence that some sampling tasks are hard on average, a recent line of work has demonstrated that disorder chaos is sufficient to rule out “stable” sampling algorithms, such as gradient methods and some diffusion processes. We demonstrate that disorder chaos does not preclude polynomial-time sampling by canonical algorithms in canonical models. We show that with high probability over a random graph $\mathbf{G} \sim G(n,1/2)$: (1) the hardcore model (at fugacity $\lambda = 1$) on $\mathbf{G}$ exhibits disorder chaos, and (2) Glauber dynamics run for $O(n)$ time can approximately sample from the hardcore model on $\mathbf{G}$ (in Wasserstein distance).

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-ma26a, title = {Polynomial-time sampling despite disorder chaos}, author = {Ma, Eric and Schramm, Tselil}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {4885--4910}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/ma26a/ma26a.pdf}, url = {https://proceedings.mlr.press/v336/ma26a.html}, abstract = {A distribution over instances of a sampling problem is said to exhibit transport disorder chaos if perturbing the instance by a small amount of random noise dramatically changes the stationary distribution (in Wasserstein distance). Seeking to provide evidence that some sampling tasks are hard on average, a recent line of work has demonstrated that disorder chaos is sufficient to rule out “stable” sampling algorithms, such as gradient methods and some diffusion processes. We demonstrate that disorder chaos does not preclude polynomial-time sampling by canonical algorithms in canonical models. We show that with high probability over a random graph $\mathbf{G} \sim G(n,1/2)$: (1) the hardcore model (at fugacity $\lambda = 1$) on $\mathbf{G}$ exhibits disorder chaos, and (2) Glauber dynamics run for $O(n)$ time can approximately sample from the hardcore model on $\mathbf{G}$ (in Wasserstein distance).} }
Endnote
%0 Conference Paper %T Polynomial-time sampling despite disorder chaos %A Eric Ma %A Tselil Schramm %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-ma26a %I PMLR %P 4885--4910 %U https://proceedings.mlr.press/v336/ma26a.html %V 336 %X A distribution over instances of a sampling problem is said to exhibit transport disorder chaos if perturbing the instance by a small amount of random noise dramatically changes the stationary distribution (in Wasserstein distance). Seeking to provide evidence that some sampling tasks are hard on average, a recent line of work has demonstrated that disorder chaos is sufficient to rule out “stable” sampling algorithms, such as gradient methods and some diffusion processes. We demonstrate that disorder chaos does not preclude polynomial-time sampling by canonical algorithms in canonical models. We show that with high probability over a random graph $\mathbf{G} \sim G(n,1/2)$: (1) the hardcore model (at fugacity $\lambda = 1$) on $\mathbf{G}$ exhibits disorder chaos, and (2) Glauber dynamics run for $O(n)$ time can approximately sample from the hardcore model on $\mathbf{G}$ (in Wasserstein distance).
APA
Ma, E. & Schramm, T.. (2026). Polynomial-time sampling despite disorder chaos. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:4885-4910 Available from https://proceedings.mlr.press/v336/ma26a.html.

Related Material