On sampling diluted Spin-Glasses using Glauber Dynamics |
Original Papers |
{\em Spin-glasses} are natural Gibbs distributions that have been studied in theoretical computer science for many decades. Recently, they have been gaining renewed attention from the community as they emerge naturally in {\em neural computation} and {\em learning}, {\em network inference}, {\em optimisation} and many other areas. Here we consider the {\em {2-spin model}} at inverse temperature $\beta$ when the underlying graph is an instance of $G(n,d/n)$, i.e., the random graph on $n$ vertices such that each edge appears independently with probability $d/n$, where the expected degree $d=\Theta(1)$. We study the problem of efficiently sampling from the aforementioned distribution using the well-known Markov chain called {\em Glauber dynamics}. For a certain range of $\beta$, that depends only on the expected degree $d$ of the graph, and for typical instances of the {2-spin model} on $G(n,d/n)$, we show that the corresponding (single-site) Glauber dynamics exhibits mixing time $O\left(n^{2+\frac{3}{\log^2 d}}\right)$. The range of $\beta$ for which we obtain our rapid mixing result corresponds to the expected influence being smaller than $1/d$. We establish our results by utilising the well-known {\em path-coupling} technique. In the standard setting of Glauber dynamics on $G(n,d/n)$ one has to deal with the so-called effect of high degree vertices. % in the path-coupling analysis. Here, with the spin-glasses, rather than considering vertex-degrees, it is more natural to use a different measure on the vertices of the graph, that we call {\em aggregate influence}. We build on the block-construction approach proposed by [Dyer, Flaxman, Frieze and Vigoda: 2006] to circumvent the problem with the high degrees in the path-coupling analysis. Specifically, to obtain our results, we first establish rapid mixing for an appropriately defined block-dynamics. We design this dynamics such that vertices of large aggregate influence are placed deep inside their blocks. Then, we obtain rapid mixing for the (single-site) Glauber dynamics by utilising a comparison argument. |
inproceedings |
Proceedings of Machine Learning Research |
PMLR |
2640-3498 |
efthymiou24a |
0 |
On sampling diluted Spin-Glasses using Glauber Dynamics |
1501 |
1515 |
1501-1515 |
1501 |
false |
Efthymiou, Charilaos and Zampetakis, Kostas |
| given |
family |
Charilaos |
Efthymiou |
|
| given |
family |
Kostas |
Zampetakis |
|
|
2024-06-30 |
|
Proceedings of Thirty Seventh Conference on Learning Theory |
247 |
inproceedings |
|
|
|