TY - JOUR
T1 - Local Minima in Disordered Mean-Field Ferromagnets
AU - Song, Eric Yilun
AU - Gheissari, Reza
AU - Newman, Charles M.
AU - Stein, Daniel L.
N1 - Funding Information:
This work was supported in part through the NYU IT High Performance Computing resources, services, and staff expertise. The research of EYS, RG and CMN was supported in part by US NSF grant DMS-1507019. RG thanks the Miller Institute for Basic Research in Science, University of California Berkeley, for its support during some of the time when this work was completed. DLS thanks the Aspen Center for Physics, supported by National Science Foundation grant PHY-1607611, where part of this work was performed. The authors thank an anonymous referee for several useful suggestions, which have been incorporated in the current version of the paper.
Funding Information:
This work was supported in part through the NYU IT High Performance Computing resources, services, and staff expertise. The research of EYS, RG and CMN was supported in part by US NSF grant DMS-1507019. RG thanks the Miller Institute for Basic Research in Science, University of California Berkeley, for its support during some of the time when this work was completed. DLS thanks the Aspen Center for Physics, supported by National Science Foundation grant PHY-1607611, where part of this work was performed. The authors thank an anonymous referee for several useful suggestions, which have been incorporated in the current version of the paper.
Publisher Copyright:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2020/9/1
Y1 - 2020/9/1
N2 - We consider the complexity of random ferromagnetic landscapes on the hypercube {±1}N given by Ising models on the complete graph with i.i.d. non-negative edge-weights. This includes, in particular, the case of Bernoulli disorder corresponding to the Ising model on a dense random graph G(N, p). Previous results had shown that, with high probability as N→ ∞, the gradient search (energy-lowering) algorithm, initialized uniformly at random, converges to one of the homogeneous global minima (all-plus or all-minus). Here, we devise two modified algorithms tailored to explore the landscape at near-zero magnetizations (where the effect of the ferromagnetic drift is minimized). With these, we numerically verify the landscape complexity of random ferromagnets, finding a diverging number of (1-spin-flip-stable) local minima as N→ ∞. We then investigate some of the properties of these local minima (e.g., typical energy and magnetization) and compare to the situation where the edge-weights are drawn from a heavy-tailed distribution.
AB - We consider the complexity of random ferromagnetic landscapes on the hypercube {±1}N given by Ising models on the complete graph with i.i.d. non-negative edge-weights. This includes, in particular, the case of Bernoulli disorder corresponding to the Ising model on a dense random graph G(N, p). Previous results had shown that, with high probability as N→ ∞, the gradient search (energy-lowering) algorithm, initialized uniformly at random, converges to one of the homogeneous global minima (all-plus or all-minus). Here, we devise two modified algorithms tailored to explore the landscape at near-zero magnetizations (where the effect of the ferromagnetic drift is minimized). With these, we numerically verify the landscape complexity of random ferromagnets, finding a diverging number of (1-spin-flip-stable) local minima as N→ ∞. We then investigate some of the properties of these local minima (e.g., typical energy and magnetization) and compare to the situation where the edge-weights are drawn from a heavy-tailed distribution.
KW - Complex landscapes
KW - Constrained optimization
KW - Disordered ferromagnets
KW - Dynamics in dilute Curie–Weiss models
KW - Landscape search algorithms
KW - Local MINCUT
KW - Local energy minima
KW - Mean-field ferromagnets
KW - Metastable traps
KW - Quenched disorder
UR - http://www.scopus.com/inward/record.url?scp=85078134565&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85078134565&partnerID=8YFLogxK
U2 - 10.1007/s10955-019-02480-4
DO - 10.1007/s10955-019-02480-4
M3 - Article
AN - SCOPUS:85078134565
SN - 0022-4715
VL - 180
SP - 576
EP - 596
JO - Journal of Statistical Physics
JF - Journal of Statistical Physics
IS - 1-6
ER -