English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the Sherrington-Kirkpatrick model of spin glasses athigh-temperature and no external field, and study the problem of sampling fromthe Gibbs distribution $\mu$ in polynomial time. We prove that, for any inversetemperature $\beta<1/2$, there exists an algorithm with complexity $O(n^2)$that samples from a distribution $\mu^{alg}$ which is close in normalizedWasserstein distance to $\mu$. Namely, there exists a coupling of $\mu$ and$\mu^{alg}$ such that if $(x,x^{alg})\in\{-1,+1\}^n\times \{-1,+1\}^n$ is apair drawn from this coupling, then $n^{-1}\mathbbE\{||x-x^{alg}||_2^2\}=o_n(1)$. The best previous results, by Bauerschmidt andBodineau and by Eldan, Koehler, and Zeitouni, implied efficient algorithms toapproximately sample (under a stronger metric) for $\beta<1/4$.  We complement this result with a negative one, by introducing a suitable"stability" property for sampling algorithms, which is verified by manystandard techniques. We prove that no stable algorithm can approximately samplefor $\beta>1$, even under the normalized Wasserstein metric.  Our sampling method is based on an algorithmic implementation of stochasticlocalization, which progressively tilts the measure $\mu$ towards a singleconfiguration, together with an approximate message passing algorithm that isused to approximate the mean of the tilted measure.

Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization