Embedded Files
Guilhem Semerjian
Guilhem Semerjian
Random constraint satisfaction problems exhibit several phase transitions related to the replica symmetry breaking phenomenon. In particular the set of solutions of such problems breaks into several clusters, or pure states, at the dynamic transition, inducing long-range point-to-set correlations in the Gibbs measure and the solvability of the associated tree reconstruction problem. In this talk I will present two results on this transition, one on the possibility to delay it to larger constraint densities by breaking the uniformity between solutions, and one on the asymptotic expansions of its location when some additional parameters (the arity of the constraints, or the size of the domain of the variables) are sent to infinity, discussing the subtle interplay that appears between the dynamic and rigidity transitions in this limit.
In recent years many conjectures on the fundamental limits in high-dimensional inference, based on the replica method, have been turned into theorems. The proofs of «replica formulas» are often asymptotic in nature, and are valid in the thermodynamic limit. In this talk I will present recent results, based on interpolation techniques, that tackle finite-size corrections. In will consider a simple model of sparse principal component analysis, and show that finite size corrections to the replica formula can be precisely computed. An important consequence is that the various control parameters in the problem which are usually fixed in the replica method, such as the signal sparsity or the noise level, can now depend on the number of variables in the problem. This allows to probe the «corners» of the phase diagram, regimes often difficult to access. As an application we show that in the very high sparsity regime, sparse PCA exhibits an «all-or-nothing» phase transition: the optimal inference is or perfect, or as bad as it can be.
The perceptron is a toy model of a simple neural network that stores a collection of (randomly) given patterns. Its analysis reduces to a simple problem in high-dimensional geometry, namely, understanding the intersection of the cube (or sphere) with a collection of random half-spaces. Although a heuristic analysis of the model was successfully completed by physicists in the 1980s, it remains open to develop a mathematical understanding. I will summarize what is known, and present some recent progress. This talk is based on joint work with Jian Ding.
I will review different works regarding the characterization of the phase transition in the three dimensional Edwards-Anderson model in absence of a magnetic field. Furthermore, I will describe properties of the associated low temperature spin glass phase which can be understood using the framework of the Replica Symmetry Breaking (RSB) theory. Hereafter, I will discuss the appearance or not of RSB in finite dimensional spin glasses (three and four dimensions) in presence of a magnetic field. Finally, I will point out some open problems.
We present numerical results on the long time behavior of the autocorrelation function in isothermal aging of mean field spin glass models, namely the Sherrington-Kirkpatrick model and the Ising spin glass on the random regular graph. We simulated very large sizes for very long times thanks to the intensive use of GPUs and carefully extrapolated to the thermodynamic limit and the asymptotic time behavior, obtaining clear evidences of non-zero residual correlations.
I shall briefly review our numerical investigation of the critical behavior of the Random Field Ising model at zero temperature, as a function of the space dimension [1-6]. After careful consideration of corrections to scaling, one concludes that universality, one of the most basic predictions of the perturbative Renormalization Group (PRG), holds. Nevertheless, the PRG is found to be fundamentally flawed below five spatial dimensions. On the other hand, we have found that two crucial PRG predictions, namely dimensional reduction [5] and super-symmetry [6], are fulfilled in five spatial dimensions.[1] N.G. Fytas and V. Martin-Mayor, Phys. Rev. Lett. 110, 227201 (2013).[2] N.G. Fytas, V. Martin-Mayor, M. Picco, and N. Sourlas, Phys. Rev. Lett. 116, 227201 (2016).[3] N.G. Fytas, V. Martin-Mayor, M. Picco, and N. Sourlas, J. Stat. Mech.: Theory Exp. (2017) 033302.[4] N.G. Fytas, V. Martin-Mayor, M. Picco, and N. Sourlas, Phys. Rev. E 95, 042117 (2017).[5] N.G. Fytas, V. Martin-Mayor, G. Parisi, M. Picco, and N. Sourlas, J. Stat. Mech.: Theory Exp. (2019), in press.[6] N.G. Fytas, V. Martin-Mayor, G. Parisi, M. Picco, and N. Sourlas, Phys. Rev. Lett. 122, 240603 (2019).
To describe spin glasses in terms of "pure states", it is necessary to average over the distribution of (possibly chaotic) states in a central region as one grows the system to infinite size. Newman and Stein have termed this distribution over states the "metastate". Recently Read has computed analytically the nature of correlations in the metastate in the mean field regime (d > 6) assuming replica symmetry breaking, finding results which agree with earlier work of Parisi et al.~for a presumably related quantity. The metastate may also be related to the non-equilibrium dynamics following a quench, in which correlations at short distance come to a steady state, one which may be influenced by the (out of equilibrium) fluctuations of spins at greater distance. Fisher and White term this the "maturation metastate". We [1] have computed the non-equilibrium dynamics of a one-dimensional model with long-range (LR) interactions corresponding to a short-range (SR) model in d = 8, i.e., in the mean field regime. Our results for correlations in this dynamic (maturation) metastate agree with the results of Read for the static metastate obtained using RSB. Hence, within the limits of the numerics, these results indicate that (i) RSB is valid in the mean field regime, and (ii) the dynamic and static metastates agree, at least in the mean field regime. The latter is particularly useful since static quantities are easier to calculate than dynamic ones.[1] Matthew Wittmann and A. P. Young, J. Stat. Mech. Theor. Exp. 013301 (2016), arXiv:1504.07709
The Ising spin glass in 2D exhibits rich behavior with subtle differences in the scaling for different coupling distributions. We use combinatorial optimization methods to determine exact ground states for systems with up to 10 000 x 10 000 spins. A combination of new algorithms allows us to treat samples with fully periodic boundaries and to sample uniformly from degenerate ground states for the +/- J model. To establish a unified framework for studying both discrete and continuous coupling distributions in arbitrary dimensions, we introduce the binomial spin glass. In this model, the couplings are the sum of m identically distributed Bernoulli random variables. In the continuum limit m→∞, this system reduces to the Edwards-Anderson model with Gaussian couplings, while m = 1 corresponds to the +/- J spin glass. Using this model, we derive a rigorous bound for the degeneracy of any energy level. Studying the defect energies in this model, we uncover intriguing subtleties in the behavior of the model with respect to the order in which the thermodynamic (N→∞) and continuum (m→∞) limits are taken.
Yoshiyuki Kabashima
Yoshiyuki Kabashima
In Sherrington-Kirkpatrick model, it is known that (1) the macroscopic dynamics of belief propagation (BP), which is sometimes referred to as "state evolution" of "approximate message passing", is described by the naive iterative substitution of the replica symmetric (RS) saddle point equation, and (2) the instability condition of BP's fixed point accords with the de Almeida-Thouless condition of the RS solution. (1) and (2) also hold when the coupling matrix is given by the Gram matrix of random matrices composed of independent entries from identical distributions. We discuss whether these correspondences are further generalized or not for spin glass models characterized by rotationally invariant matrix ensembles.
The experimental measure of the complete equilibrium distribution of the overlap in a replica symmetry breaking thermodynamic phase is a challenging objective since the introduction of the Parisi solution to the Sherrington-Kirkpatrick model and, later on, since the conception of the idea of stochastic stability. The measure is a complicated problem because large disordered systems take a very long time to thermalize and because microscopic spin configurations have to be measured to evaluate overlap values. In this presentation we tackle the problem on a spin-glass related model in which the spins are, actually, light modes, established and coupled in an optically random medium because of multiple light scattering. In presence of external power pumping this model reproduces the behavior of a particular kind of so-called random lasers, that we will term glassy random lasers. We therefore, introduce a theory of multimode light amplification in random media. The leading model, derived from fundamental light-matter interaction, is a phasor spin-glass model with multi-mode coupling, undergoing an overall intensity constraint induced by gain saturation, i. e., a spherical complex multi-p-spin model. Through analytic theoretical approaches, numerical simulations and experimental measurements we investigate this class of random laser models, displaying properties such as a lasing phase transition, ergodicity breaking, glassiness at high power pumping, energy condensation, and nonlinear mode-locking.Replica Symmetry Breaking theory allows to identify a laser critical point at a certain pumping power and a glassy regime in the high pumping regime. An intensity fluctuation overlap (IFO) parameter is introduced, measuring the correlation between intensity fluctuations of light waves. In mean-field fully connected spherical models the IFO can be proved to be in a one-to-one correspondence with the Parisi overlap, and it allows to identify the laser transition and the high pumping glassy phase in terms of emission spectra data, the only data so far accessible in random laser experimental measurements. Though phasors configurations are not accessible, intensity configurations might, thus, be observed by means of emission spectra.Investigating pulse-to-pulse fluctuations in organic solid random lasers, indeed, the distribution of intensity fluctuation overlaps can be constructed and yields evidence of a transition to a glassy light phase compatible with a replica symmetry breaking. To bridge exact analytic results and coarse-grained experimental results we, eventually, present numerical simulation of realistic models of random lasers. Going beyond the fully connected approximation, in a diluted interaction network, a breakdown of energy equipartition among light modes is observed right at the glass transition point.
I will illustrate a new loop expansion for the study of the second-order phase transitions that is particularly useful in the case of disordered models. While the standard expansion is around the fully connected mean-field version of the model, the new expansion is around the Bethe mean-field model. I will show that the new expansion gives the same results of the standard expansion when the fixed points of the fully connected and the Bethe model are the same, as in the case of the spin-glass in a field at finite temperature; conversely the two expansions can give different results when the fully connected and the Bethe fixed points are different, as in the case of the Random Field Ising Model.
A number of models are known to exhibit a glass transition characterized by one step replica symmetry breaking. This talk will present a series of recent results for such systems:1. How finite size effects transform a one step replica symmetry breaking into a full replica symmetry breaking in the case of the directed polymer on a tree;2. How the Parisi scheme has to be adapted to calculate the overlaps between two temperatures or to understand finite size effects.All our results follow from comparing an exact (replica-free) approach with the replica method. Joint work with Peter Mottishaw (University of Edinburgh).
Google Sites
Report abuse