Exponential Capacity of Dense Associative Memories

Recent generalizations of the Hopfield model of associative memories are able to store a number P of random patterns that grows exponentially with the number N of neurons, P=exp(αN). Besides the huge storage capacity, another interesting feature of these networks is their connection to the attention mechanism which is part of the Transformer architecture widely applied in deep learning. In this work, we study a generic family of pattern ensembles using a statistical mechanics analysis which gives exact asymptotic thresholds for the retrieval of a typical pattern, α_{1}, and lower bounds for the maximum of the load α for which all patterns can be retrieved, α_{c}, as well as sizes of attraction basins. We discuss in detail the cases of Gaussian and spherical patterns, and show that they display rich and qualitatively different phase diagrams.

Matrix factorization with neural networks

Matrix factorization is an important mathematical problem encountered in the context of dictionary learning, recommendation systems, and machine learning. We introduce a decimation scheme that maps it to neural network models of associative memory and provide a detailed theoretical analysis of its performance, showing that decimation is able to factorize extensive-rank matrices and to denoise them efficiently. In the case of binary prior on the signal components, we introduce a decimation algorithm based on a ground-state search of the neural network, which shows performances that match the theoretical prediction.

Distribution of diameters for Erdős-Rényi random graphs

We study the distribution of diameters d of Erdős-Rényi random graphs with average connectivity c. The diameter d is the maximum among all the shortest distances between pairs of nodes in a graph and an important quantity for all dynamic processes taking place on graphs. Here we study the distribution P(d) numerically for various values of c, in the nonpercolating and percolating regimes. Using large-deviation techniques, we are able to reach small probabilities like 10^{-100} which allow us to obtain the distribution over basically the full range of the support, for graphs up to N=1000 nodes. For values c<1, our results are in good agreement with analytical results, proving the reliability of our numerical approach. For c>1 the distribution is more complex and no complete analytical results are available. For this parameter range, P(d) exhibits an inflection point, which we found to be related to a structural change of the graphs. For all values of c, we determined the finite-size rate function Φ(d/N) and were able to extrapolate numerically to N→∞, indicating that the large-deviation principle holds.

Mean-field message-passing equations in the Hopfield model and its generalizations

Motivated by recent progress in using restricted Boltzmann machines as preprocessing algorithms for deep neural network, we revisit the mean-field equations [belief-propagation and Thouless-Anderson Palmer (TAP) equations] in the best understood of such machines, namely the Hopfield model of neural networks, and we explicit how they can be used as iterative message-passing algorithms, providing a fast method to compute the local polarizations of neurons. In the "retrieval phase", where neurons polarize in the direction of one memorized pattern, we point out a major difference between the belief propagation and TAP equations: The set of belief propagation equations depends on the pattern which is retrieved, while one can use a unique set of TAP equations. This makes the latter method much better suited for applications in the learning process of restricted Boltzmann machines. In the case where the patterns memorized in the Hopfield model are not independent, but are correlated through a combinatorial structure, we show that the TAP equations have to be modified. This modification can be seen either as an alteration of the reaction term in TAP equations or, more interestingly, as the consequence of message passing on a graphical model with several hidden layers, where the number of hidden layers depends on the depth of the correlations in the memorized patterns. This layered structure is actually necessary when one deals with more general restricted Boltzmann machines.

Dynamic message-passing equations for models with unidirectional dynamics

Understanding and quantifying the dynamics of disordered out-of-equilibrium models is an important problem in many branches of science. Using the dynamic cavity method on time trajectories, we construct a general procedure for deriving the dynamic message-passing equations for a large class of models with unidirectional dynamics, which includes the zero-temperature random-field Ising model, the susceptible-infected-recovered model, and rumor spreading models. We show that unidirectionality of the dynamics is the key ingredient that makes the problem solvable. These equations are applicable to single instances of the corresponding problems with arbitrary initial conditions and are asymptotically exact for problems defined on locally treelike graphs. When applied to real-world networks, they generically provide a good analytic approximation of the real dynamics.

Inferring the origin of an epidemic with a dynamic message-passing algorithm

We study the problem of estimating the origin of an epidemic outbreak: given a contact network and a snapshot of epidemic spread at a certain time, determine the infection source. This problem is important in different contexts of computer or social networks. Assuming that the epidemic spread follows the usual susceptible-infected-recovered model, we introduce an inference algorithm based on dynamic message-passing equations and we show that it leads to significant improvement of performance compared to existing approaches. Importantly, this algorithm remains efficient in the case where the snapshot sees only a part of the network.

Mean-field behavior of the negative-weight percolation model on random regular graphs

We investigate both analytically and numerically the ensemble of minimum-weight loops in the negative-weight percolation model on random graphs with fixed connectivity and bimodal weight distribution. This allows us to study the mean-field behavior of this model. The analytical study is based on a conjectured equivalence with the problem of self-avoiding walks in a random medium. The numerical study is based on a mapping to a standard minimum-weight matching problem for which fast algorithms exist. Both approaches yield results that are in agreement on the location of the phase transition, on the value of critical exponents, and on the absence of any sizable indications of a glass phase. By these results, the previously conjectured upper critical dimension of d(u)=6 is confirmed.

Thermodynamics of the Lévy spin glass

We investigate the Lévy glass, a mean-field spin-glass model with power-law distributed couplings characterized by a divergent second moment. By combining extensively many small couplings with a spare random backbone of strong bonds the model is intermediate between the Sherrington-Kirkpatrick and the Viana-Bray models. A truncated version where couplings smaller than some threshold ε are neglected can be studied within the cavity method developed for spin glasses on locally treelike random graphs. By performing the limit ε→0 in a well-defined way we calculate the thermodynamic functions within replica symmetry and determine the de Almeida-Thouless line in the presence of an external magnetic field. Contrary to previous findings we show that there is no replica-symmetric spin-glass phase. Moreover we determine the leading corrections to the ground-state energy within one-step replica symmetry breaking. The effects due to the breaking of replica symmetry appear to be small in accordance with the intuitive picture that a few strong bonds per spin reduce the degree of frustration in the system.

Disorder-driven quantum phase transitions in superconductors and magnets

We develop an analytical theory, based on the quantum cavity method, describing the quantum phase transitions in low-temperature, strongly disordered ferromagnets and superconductors. At variance with the usual quantum critical points, we find a phase diagram with two critical points separating three phases. When the disorder increases, the systems goes from the ordered phase to an intermediate disordered phase characterized by activated transport and then to a second disordered phase where no transport is possible. Both the ordered and disordered phases exhibit strong inhomogeneity of their basic properties typical of glassy physics.

Emergence of rigidity at the structural glass transition: a first-principles computation

We compute the shear modulus of structural glasses from a first-principles approach based on the cloned liquid theory. We find that the intrastate shear modulus, which corresponds to the plateau modulus measured in linear viscoelastic measurements, strongly depends on temperature and vanishes continuously when the temperature is increased beyond the glass temperature.

Hierarchical random energy model of a spin glass

We introduce a random energy model on a hierarchical lattice where the interaction strength between variables is a decreasing function of their mutual hierarchical distance, making it a non-mean-field model. Through small coupling series expansion and a direct numerical solution of the model, we provide evidence for a spin-glass condensation transition similar to the one occurring in the usual mean-field random energy model. At variance with the mean field, the high temperature branch of the free-energy is nonanalytic at the transition point.

Constraint satisfaction problems and neural networks: A statistical physics perspective

A new field of research is rapidly expanding at the crossroad between statistical physics, information theory and combinatorial optimization. In particular, the use of cutting edge statistical physics concepts and methods allow one to solve very large constraint satisfaction problems like random satisfiability, coloring, or error correction. Several aspects of these developments should be relevant for the understanding of functional complexity in neural networks. On the one hand the message passing procedures which are used in these new algorithms are based on local exchange of information, and succeed in solving some of the hardest computational problems. On the other hand some crucial inference problems in neurobiology, like those generated in multi-electrode recordings, naturally translate into hard constraint satisfaction problems. This paper gives a non-technical introduction to this field, emphasizing the main ideas at work in message passing strategies and their possible relevance to neural networks modelling. It also introduces a new message passing algorithm for inferring interactions between variables from correlation data, which could be useful in the analysis of multi-electrode recording data.

Locked constraint satisfaction problems

We introduce and study the random "locked" constraint satisfaction problems. When increasing the density of constraints, they display a broad "clustered" phase in which the space of solutions is divided into many isolated points. While the phase diagram can be found easily, these problems, in their clustered phase, are extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions. We thus propose new benchmarks of really hard optimization problems and provide insight into the origin of their typical hardness.

Statistical mechanics of the hitting set problem

In this paper we present a detailed study of the hitting set (HS) problem. This problem is a generalization of the standard vertex cover to hypergraphs: one seeks a configuration of particles with minimal density such that every hyperedge of the hypergraph contains at least one particle. It can also be used in important practical tasks, such as the group testing procedures where one wants to detect defective items in a large group by pool testing. Using a statistical mechanics approach based on the cavity method, we study the phase diagram of the HS problem, in the case of random regular hypergraphs. Depending on the values of the variables and tests degrees different situations can occur: The HS problem can be either in a replica symmetric phase, or in a one-step replica symmetry breaking one. In these two cases, we give explicit results on the minimal density of particles, and the structure of the phase space. These problems are thus in some sense simpler than the original vertex cover problem, where the need for a full replica symmetry breaking has prevented the derivation of exact results so far. Finally, we show that decimation procedures based on the belief propagation and the survey propagation algorithms provide very efficient strategies to solve large individual instances of the hitting set problem.

Landscape of solutions in constraint satisfaction problems

We present a theoretical framework for characterizing the geometrical properties of the space of solutions in constraint satisfaction problems, together with practical algorithms for studying this structure on particular instances. We apply our method to the coloring problem, for which we obtain the total number of solutions and analyze in detail the distribution of distances between solutions.

Cavity approach to the random solid state

The cavity approach is used to address the physical properties of random solids in equilibrium. Particular attention is paid to the fraction of localized particles and the distribution of localization lengths characterizing their thermal motion. This approach is of relevance to a wide class of random solids, including rubbery media (formed via the vulcanization of polymer fluids) and chemical gels (formed by the random covalent bonding of fluids of atoms or small molecules). The cavity approach confirms results that have been obtained previously via replica mean-field theory, doing so in a way that sheds new light on their physical origin.

Lossy data compression with random gates

We introduce a new protocol for a lossy data compression algorithm which is based on constraint satisfaction gates. We show that the theoretical capacity of algorithms built from standard parity-check gates converges exponentially fast to the Shannon's bound when the number of variables seen by each gate increases. We then generalize this approach by introducing random gates. They have theoretical performances nearly as good as parity checks, but they offer the great advantage that the encoding can be done in linear time using the survey inspired decimation algorithm, a powerful algorithm for constraint satisfaction problems derived from statistical physics.

Clustering of solutions in the random satisfiability problem

Using elementary rigorous methods we prove the existence of a clustered phase in the random K-SAT problem, for K > or = 8. In this phase the solutions are grouped into clusters which are far away from each other. The results are in agreement with previous predictions of the cavity method and give a rigorous confirmation to one of its main building blocks. It can be generalized to other systems of both physical and computational interest.

Toward a theory of marker-assisted gene pyramiding

We investigate the best way to combine into a single genotype a series of target genes identified in different parents (gene pyramiding). Assuming that individuals can be selected and mated according to their genotype, the best method corresponds to an optimal succession of crosses over several generations (pedigree). For each pedigree, we compute the probability of success from the known recombination fractions between the target loci, as well as the number of individuals (population sizes) that should be genotyped over successive generations until the desired genotype is obtained. We provide an algorithm that generates and compares pedigrees on the basis of the population sizes they require and on their total duration (in number of generations) and finds the best gene-pyramiding scheme. Examples are given for eight target genes and are compared to a reference genotype selection method with random mating. The best gene-pyramiding method combines the eight targets in three generations less than the reference method while requiring fewer genotypings.

Frozen glass phase in the multi-index matching problem

The multi-index matching is an NP-hard combinatorial optimization problem; for two indices it reduces to the well understood bipartite matching problem that belongs to the polynomial complexity class. We use the cavity method to solve the thermodynamics of the multi-index system with random costs. The phase diagram is much richer than for the case of the bipartite matching problem: it shows a finite temperature phase transition to a completely frozen glass phase, similar to what happens in the random energy model. We derive the critical temperature, the ground-state energy density, and properties of the energy landscape and compare the results to numerics based on exact analysis of small systems.

Glassy phases in random heteropolymers with correlated sequences

We develop an analytic approach for the study of lattice heteropolymers and apply it to copolymers with correlated Markovian sequences. According to our analysis, heteropolymers present three different dense phases depending upon the temperature, the nature of the monomer interactions, and the sequence correlations: (i) a liquid phase, (ii) a "soft glass" phase, and (iii) a "frozen glass" phase. The presence of the intermediate "soft glass" phase is predicted, for instance, in the case of polyampholytes with sequences that favor the alternation of monomers. Our approach is based on the cavity method, a refined Bethe-Peierls approximation adapted to frustrated systems. It amounts to a mean-field treatment in which the nearest-neighbor correlations, which are crucial in the dense phases of heteropolymers, are handled exactly. This approach is powerful and versatile; it can be improved systematically and generalized to other polymeric systems.

Phase diagram of random heteropolymers

We propose a new analytic approach to study the phase diagram of random heteropolymers, based on the cavity method. For copolymers we analyze the nature and phenomenology of the glass transition as a function of sequence correlations. Depending on these correlations, we find that two different scenarios for the glass transition can occur. We show that, beside the much studied possibility of an abrupt freezing transition at low temperature, the system can exhibit, upon cooling, a first transition to a soft glass phase with fully broken replica symmetry and a continuously growing degree of freezing as the temperature is lowered.

Physics/computer science. Passing messages between disciplines

Problems in computer science, such as error correction in information transfer and "satisfiability" in optimization, show phase transitions familiar from solid-state physics. In his Perspective, Mézard explains how recent advances in these three fields originate in similar "message passing" procedures. The exchange of elaborate messages between different variables and constraints, used in the study of phase transitions in physical systems, helps to make error correction and satisfiability codes more efficient.

Random K-satisfiability problem: from an analytic solution to an efficient algorithm

We study the problem of satisfiability of randomly chosen clauses, each with K Boolean variables. Using the cavity method at zero temperature, we find the phase diagram for the K=3 case. We show the existence of an intermediate phase in the satisfiable region, where the proliferation of metastable states is at the origin of the slowdown of search algorithms. The fundamental order parameter introduced in the cavity method, which consists of surveys of local magnetic fields in the various possible states of the system, can be computed for one given sample. These surveys can be used to invent new types of algorithms for solving hard combinatorial optimizations problems. One such algorithm is shown here for the K=3 satisfiability problem, with very good performances.

The secondary structure of RNA under tension

We study the force-induced unfolding of random disordered RNA or single-stranded DNA polymers. The system undergoes a second-order phase transition from a collapsed globular phase at low forces to an extensive necklace phase with a macroscopic end-to-end distance at high forces. At low temperatures, the sequence inhomogeneities modify the critical behaviour. We provide numerical evidence for the universality of the critical exponents which, by extrapolation of the scaling laws to zero force, contain useful information on the ground-state (f = 0) properties. This provides a good method for quantitative studies of scaling exponents characterizing the collapsed globule. In order to get rid of the blurring effect of thermal fluctuations, we restrict ourselves to the ground state at fixed external force. We analyze the statistics of rearrangements, in particular below the critical force, and point out its implications for force-extension experiments on single molecules.

Analytic and algorithmic solution of random satisfiability problems

We study the satisfiability of random Boolean expressions built from many clauses with K variables per clause (K-satisfiability). Expressions with a ratio alpha of clauses to variables less than a threshold alphac are almost always satisfiable, whereas those with a ratio above this threshold are almost always unsatisfiable. We show the existence of an intermediate phase below alphac, where the proliferation of metastable states is responsible for the onset of complexity in search algorithms. We introduce a class of optimization algorithms that can deal with these metastable states; one such algorithm has been tested successfully on the largest existing benchmark of K-satisfiability.

Lattice glass models

Motivated by the concept of geometrical frustration, we introduce a class of statistical mechanics lattice models for the glass transition. Monte Carlo simulations in three dimensions show that they display a dynamical glass transition which is very similar to that observed in other off-lattice systems and which does not depend on a specific dynamical rule. A mean-field study shows the existence of a discontinuous glass transition, in agreement with the numerical observations.

Hairpin formation and elongation of biomolecules

We introduce a model of thermalized conformations in space of RNA-or single stranded DNA-molecules, which includes the possibility of hairpin formation. This model contains the usual secondary structure information, but extends it to the study of one element of the ternary structure, namely the end-to-end distance. The computed force-elongation characteristics are in good agreement with some recent measurements on single stranded DNA molecules.

Wandering of a contact line at thermal equilibrium

We reconsider the problem of the solid-liquid-vapor contact-line on a disordered substrate, in the collective pinning regime. We perform a replica variational calculation which confirms the scaling behavior obtained from Larkin-Imry-Ma-like arguments and provides a quantitative prediction for the correlation function of the line. This prediction is in good agreement with experimental findings for the case of superfluid helium on a caesium substrate.