ترغب بنشر مسار تعليمي؟ اضغط هنا

Optimization of Mean-field Spin Glasses

113   0   0.0 ( 0 )
 نشر من قبل Andrea Montanari
 تاريخ النشر 2020
  مجال البحث فيزياء
والبحث باللغة English




اسأل ChatGPT حول البحث

Mean-field spin glasses are families of random energy functions (Hamiltonians) on high-dimensional product spaces. In this paper we consider the case of Ising mixed $p$-spin models, namely Hamiltonians $H_N:Sigma_Nto {mathbb R}$ on the Hamming hypercube $Sigma_N = {pm 1}^N$, which are defined by the property that ${H_N({boldsymbol sigma})}_{{boldsymbol sigma}in Sigma_N}$ is a centered Gaussian process with covariance ${mathbb E}{H_N({boldsymbol sigma}_1)H_N({boldsymbol sigma}_2)}$ depending only on the scalar product $langle {boldsymbol sigma}_1,{boldsymbol sigma}_2rangle$. The asymptotic value of the optimum $max_{{boldsymbol sigma}in Sigma_N}H_N({boldsymbol sigma})$ was characterized in terms of a variational principle known as the Parisi formula, first proved by Talagrand and, in a more general setting, by Panchenko. The structure of superlevel sets is extremely rich and has been studied by a number of authors. Here we ask whether a near optimal configuration ${boldsymbol sigma}$ can be computed in polynomial time. We develop a message passing algorithm whose complexity per-iteration is of the same order as the complexity of evaluating the gradient of $H_N$, and characterize the typical energy value it achieves. When the $p$-spin model $H_N$ satisfies a certain no-overlap gap assumption, for any $varepsilon>0$, the algorithm outputs ${boldsymbol sigma}inSigma_N$ such that $H_N({boldsymbol sigma})ge (1-varepsilon)max_{{boldsymbol sigma}} H_N({boldsymbol sigma})$, with high probability. The number of iterations is bounded in $N$ and depends uniquely on $varepsilon$. More generally, regardless of whether the no-overlap gap assumption holds, the energy achieved is given by an extended variational principle, which generalizes the Parisi formula.



قيم البحث

اقرأ أيضاً

66 - A. Billoire 1999
We discuss temperature chaos in mean field and realistic 3D spin glasses. Our numerical simulations show no trace of a temperature chaotic behavior for the system sizes considered. We discuss the experimental and theoretical implications of these findings.
133 - C.M. Newman 2003
We study chaotic size dependence of the low temperature correlations in the SK spin glass. We prove that as temperature scales to zero with volume, for any typical coupling realization, the correlations cycle through every spin configuration in every fixed observation window. This cannot happen in short-ranged models as there it would mean that every spin configuration is an infinite-volume ground state. Its occurrence in the SK model means that the commonly used `modified clustering notion of states sheds little light on the RSB solution of SK, and conversely, the RSB solution sheds little light on the thermodynamic structure of EA models.
87 - Zhou Fan , Yihong Wu 2021
We study the mean-field Ising spin glass model with external field, where the random symmetric couplings matrix is orthogonally invariant in law. For sufficiently high temperature, we prove that the replica-symmetric prediction is correct for the fir st-order limit of the free energy. Our analysis is an adaption of a conditional quenched equals annealed argument used by Bolthausen to analyze the high-temperature regime of the Sherrington-Kirkpatrick model. We condition on a sigma-field that is generated by the iterates of an Approximate Message Passing algorithm for solving the TAP equations in this model, whose rigorous state evolution was recently established.
Optimizing a high-dimensional non-convex function is, in general, computationally hard and many problems of this type are hard to solve even approximately. Complexity theory characterizes the optimal approximation ratios achievable in polynomial time in the worst case. On the other hand, when the objective function is random, worst case approximation ratios are overly pessimistic. Mean field spin glasses are canonical families of random energy functions over the discrete hypercube ${-1,+1}^N$. The near-optima of these energy landscapes are organized according to an ultrametric tree-like structure, which enjoys a high degree of universality. Recently, a precise connection has begun to emerge between this ultrametric structure and the optimal approximation ratio achievable in polynomial time in the typical case. A new approximate message passing (AMP) algorithm has been proposed that leverages this connection. The asymptotic behavior of this algorithm has been analyzed, conditional on the nature of the solution of a certain variational problem. In this paper we describe the first implementation of this algorithm and the first numerical solution of the associated variational problem. We test our approach on two prototypical mean-field spin glasses: the Sherrington-Kirkpatrick (SK) model, and the $3$-spin Ising spin glass. We observe that the algorithm works well already at moderate sizes ($Ngtrsim 1000$) and its behavior is consistent with theoretical expectations. For the SK model it asymptotically achieves arbitrarily good approximations of the global optimum. For the $3$-spin model, it achieves a constant approximation ratio that is predicted by the theory, and it appears to beat the `threshold energy achieved by Glauber dynamics. Finally, we observe numerically that the intermediate states generated by the algorithm have the properties of ancestor states in the ultrametric tree.
We derive lower bounds for the variance of the difference of energies between incongruent ground states, i.e., states with edge overlaps strictly less than one, of the Edwards-Anderson model on ${mathbb Z}^d$. The bounds highlight a relation between the existence of incongruent ground states and the absence of edge disorder chaos. In particular, it suggests that the presence of disorder chaos is necessary for the variance to be of order less than the volume. In addition, a relation is established between the scale of disorder chaos and the size of critical droplets. The results imply a long-conjectured relation between the droplet theory of Fisher and Huse and the absence of incongruence.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا