Search

Following the 2015 migration wave to Europe, numerous French academic institutions organized themselves to welcome refugee students and researchers. As witnessed in the past, initiatives coming from universities largely preceded national dispositions, which took place in a second phase and worked towards reinforcing them. These initiatives provide some examples demonstrating the commitment of academic communities as a whole to crucial societal issues.

We study the distribution of diameters d of Erd\"os-R\'enyi random graphs with average connectivity c. The diameter d is the maximum among all 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 non-percolating and the percolating regime. Using large-deviations 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 c1 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 Phi(d/N) and were able to extrapolate numerically to N->infinity, indicating that the large deviation principle holds., Comment: 9 figures

Improved mean-field technics are a central theme of statistical physics methods applied to inference and learning. We revisit here some of these methods using high-temperature expansions for disordered systems initiated by Plefka, Georges and Yedidia. We derive the Gibbs free entropy and the subsequent self-consistent equations for a generic class of statistical models with correlated matrices and show in particular that many classical approximation schemes, such as adaptive TAP, Expectation-Consistency, or the approximations behind the Vector Approximate Message Passing algorithm all rely on the same assumptions, that are also at the heart of high-temperature expansions. We focus on the case of rotationally invariant random coupling matrices in the `high-dimensional' limit in which the number of samples and the dimension are both large, but with a fixed ratio. This encapsulates many widely studied models, such as Restricted Boltzmann Machines or Generalized Linear Models with correlated data matrices. In this general setting, we show that all the approximation schemes described before are equivalent, and we conjecture that they are exact in the thermodynamic limit in the replica symmetric phases. We achieve this conclusion by resummation of the infinite perturbation series, which generalizes a seminal result of Parisi and Potters. A rigorous derivation of this conjecture is an interesting mathematical challenge. On the way to these conclusions, we uncover several diagrammatical results in connection with free probability and random matrix theory, that are interesting independently of the rest of our work., 59 pages, updated version matching the version published in J. Stat. Mech. Correction of typos in the last version

The analysis of the linearization effect in multifractal analysis, and hence of the estimation of moments for multifractal processes, is revisited borrowing concepts from the statistical physics of disordered systems, notably from the analysis of the so-called Random Energy Model. Considering a standard multifractal process (compound Poisson motion), chosen as a simple representative example, we show: i) the existence of a critical order $q^*$ beyond which moments, though finite, cannot be estimated through empirical averages, irrespective of the sample size of the observation; ii) that multifractal exponents necessarily behave linearly in $q$, for $q > q^*$. Tayloring the analysis conducted for the Random Energy Model to that of Compound Poisson motion, we provide explicative and quantitative predictions for the values of $q^*$ and for the slope controlling the linear behavior of the multifractal exponents. These quantities are shown to be related only to the definition of the multifractal process and not to depend on the sample size of the observation. Monte-Carlo simulations, conducted over a large number of large sample size realizations of compound Poisson motion, comfort and extend these analyses., 11 pages, 1 figure, final version, to appear in Physica D

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 modeling. 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., Prepared for the proceedings of the 2007 Tauc Conference on Complexity in Neural Network Dynamics

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 TAP equations) in the best understood such machine, 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., Comment: 29 pages, 4 figures

The cavity method is introduced as a heuristic framework from a physics perspective to solve probabilistic graphical models and is presented at both the replica symmetry (RS) and one-step replica symmetry breaking (1RSB) levels. This technique has been applied with success to a wide range of models and problems, such as spin glasses, random constraint satisfaction problems (rCSP), and error correcting codes. First, the RS cavity solution for the Sherrington–Kirkpatrick model—a fully connected spin glass model—is derived and its equivalence to the RS solution obtained using replicas is discussed. The general cavity method for diluted graphs is then illustrated at both RS and 1RSB levels. The latter was a significant breakthrough in the last decade and has direct applications to rCSP. Finally, as an example of an actual problem, k-SAT is investigated using belief and survey propagation.

The use of parity-check gates in information theory has proved to be very efficient. In particular, error correcting codes based on parity checks over low-density graphs show excellent performances. Another basic issue of information theory, namely data compression, can be addressed in a similar way by a kind of dual approach. The theoretical performance of such a parity source coder can attain the optimal limit predicted by the general rate-distortion theory. However, in order to turn this approach into an efficient compression code (with fast encoding/decoding algorithms) one must depart from parity checks and use some general random gates. By taking advantage of analytical approaches from the statistical physics of disordered systems and SP-like message passing algorithms, we construct a compressor based on low-density non-linear gates with a very good theoretical and practical performance.

In this note we explain the use of the cavity method directly at zero temperature, in the case of the spin glass on a lattice with a local tree like structure, which is the proper generalization of the usual Bethe lattice to frustrated problems. The computation is done explicitly in the formalism equivalent to “one step replica symmetry breaking;” we compute the energy of the global ground state, as well as the complexity of equilibrium states at a given energy. Full results are presented for a Bethe lattice with connectivity equal to three. The main assumptions underlying the one step cavity approach, namely the existence of many local ground states, are explicitely stated and discussed: some of the main obstacles towards a rigorous study of the problem with the cavity method are outlined.

We derive analytical solutions for p-spin models with finite connectivity at zero temperature. These models are the statistical mechanics equivalent of p-XORSAT problems in theoretical computer science. We give a full characterization of the phase diagram: location of the phase transitions (static and dynamic), together with a description of the clustering phenomenon taking place in configurational space. We use two alternative methods: the cavity approach and a rigorous derivation.

We study the satisfiability of random Boolean expressions built from many clauses with K variables per clause (K-satisfiability). Expressions with a ratio α of clauses to variables less than a threshold α c 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 α c , 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.

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.

So far the problem of a spin glass on a Bethe lattice has been solved only at the replica symmetric level, which is wrong in the spin glass phase. Because of some technical difficulties, attempts at deriving a replica symmetry breaking solution have been confined to some perturbative regimes, high connectivity lattices or temperature close to the critical temperature. Using the cavity method, we propose a general non perturbative solution of the Bethe lattice spin glass problem at a level of approximation which is equivalent to a one step replica symmetry breaking solution. The results compare well with numerical simulations. The method can be used for many finite connectivity problems appearing in combinatorial optimization., 23 pages, 6 figures

We propose a general interpretation for long-range correlation effects in the activity and volatility of financial markets. This interpretation is based on the fact that the choice between 'active' and 'inactive' strategies is subordinated to random-walk-like processes. We numerically demonstrate our scenario in the framework of simplified market models, such as the Minority Game model with an inactive strategy. We show that real market data can be surprisingly well accounted for by these simple models.

We introduce a simple model of economy, where the time evolution is described by an equation capturing both exchange between individuals and random speculative trading, in such a way that the fundamental symmetry of the economy under an arbitrary change of monetary units is insured. We investigate a mean-field limit of this equation and show that the distribution of wealth is of the Pareto (power-law) type. The Pareto behaviour of the tails of this distribution appears to be robust for finite range models, as shown using both a mapping to the random `directed polymer' problem, as well as numerical simulations. In this context, a transition between an economy dominated by a few individuals from a situation where the wealth is more evenly spread out, is found. An interesting outcome is that the distribution of wealth tends to be very broadly distributed when exchanges are limited, either in amplitude or topologically. Favoring exchanges (and, less surprisingly, increasing taxes) seems to be an efficient way to reduce inequalities., Comment: 11 pages, 3 .ps figures

We propose a first principle computation of the equilibrium thermodynamics of simple fragile glasses starting from the two body interatomic potential. A replica formulation translates this problem into that of a gas of interacting molecules, each molecule being built of m atoms, and having a gyration radius (related to the cage size) which vanishes at zero temperature. We use a small cage expansion, valid at low temperatures, which allows to compute the cage size, the specific heat (which follows the Dulong and Petit law), and the configurational entropy., Latex, 40 pages, 9 figures, corrected misprints, improved presentation

The recently proposed strategy for studying the equilibrium thermodynamics of the glass phase using a molecular liquid is reviewed and tested in details on the solvable case of the $p$-spin model. We derive the general phase diagram, and confirm the validity of this procedure. We point out the efficacy of a system of two weakly coupled copies in order to identify the glass transition, and the necessity to study a system with $m, Latex, 17 pages, 6 figures

We discuss the response of aging systems with short-range interactions to a class of random perturbations. Although these systems are out of equilibrium, the limit value of the free energy at long times is equal to the equilibrium free energy. By exploiting this fact, we define a new order parameter function, and we relate it to the ratio between response and fluctuation, which is in principle measurable in an aging experiment. For a class of systems possessing stochastic stability, we show that this new order parameter function is intimately related to the static order parameter function, describing the distribution of overlaps between clustering states. The same method is applied to investigate the geometrical organization of pure states. We show that the ultrametric organization in the dynamics implies static ultrametricity, and we relate these properties to static separability, i.e., the property that the measure of the overlap between pure states is essentially unique. Our results, especially relevant for spin glasses, pave the way to an experimental determination of the order parameter function.

A fast way of finding representative examples in complex data sets may be applicable to a wide range of difficult problems.

We corroborate the idea of a close connection between replica symmetry breaking and aging in the linear response function for a large class of finite-dimensional systems with short-range interactions. In these system, characterized by a continuity condition with respect to weak random perturbations of the Hamiltonian, the ``fluctuation dissipation ratio'' in off-equilibrium dynamics should be equal to the static cumulative distribution function of the overlaps. This allows for an experimental measurement of the equilibrium order parameter function., Comment: 5 pages, LaTeX. The paper has been completely rewritten and shortened

We analyse the matrix factorization problem. Given a noisy measurement of a product of two matrices, the problem is to estimate back the original matrices. It arises in many applications such as dictionary learning, blind matrix calibration, sparse principal component analysis, blind source separation, low rank matrix completion, robust principal component analysis or factor analysis. It is also important in machine learning: unsupervised representation learning can often be studied through matrix factorization. We use the tools of statistical mechanics - the cavity and replica methods - to analyze the achievability and computational tractability of the inference problems in the setting of Bayes-optimal inference, which amounts to assuming that the two matrices have random independent elements generated from some known distribution, and this information is available to the inference algorithm. In this setting, we compute the minimal mean-squared-error achievable in principle in any computational time, and the error that can be achieved by an efficient approximate message passing algorithm. The computation is based on the asymptotic state-evolution analysis of the algorithm. The performance that our analysis predicts, both in terms of the achieved mean-squared-error, and in terms of sample complexity, is extremely promising and motivating for a further development of the algorithm., 50 pages, 10 figures

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. Finding the source is important in different contexts of computer or social networks. We assume that the epidemic spread follows the most commonly used 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 one knows the state of only a fraction of nodes., 9 pages, 8 figures. Revised version, new figures added

We discuss the large scale effective free energy landscape for elastic objects pinned by a random potential. In the static approach, converging analytical results show that this landscape consists in a succession of parabolic wells of random depth, matching on singular points where the effective force is discontinuous. We discuss the consequences for the dynamics of these pinned interfaces.

In compressed sensing one measures sparse signals directly in a compressed form via a linear transform and then reconstructs the original signal. However, it is often the case that the linear transform itself is known only approximately, a situation called matrix uncertainty, and that the measurement process is noisy. Here we present two contributions to this problem: first, we use the replica method to determine the mean-squared error of the Bayes-optimal reconstruction of sparse signals under matrix uncertainty. Second, we consider a robust variant of the approximate message passing algorithm and demonstrate numerically that in the limit of large systems, this algorithm matches the optimal performance in a large region of parameters., Comment: 5 pages, 4 figures

We propose a method to study quantitatively the glass transition in a system of interacting particles. In spite of the absence of any quenched disorder, we introduce a replicated version of the hypernetted chain equations. The solution of these equations, for hard or soft spheres, signals a transition to the glass phase. However the predicted value of the energy and specific heat in the glass phase are wrong, calling for an improvement of this method., 9 pages, four postcript figures attached

We study non-adaptive pooling strategies for detection of rare faulty items. Given a binary sparse N-dimensional signal x, how to construct a sparse binary MxN pooling matrix F such that the signal can be reconstructed from the smallest possible number M of measurements y=Fx? We show that a very low number of measurements is possible for random spatially coupled design of pools F. Our design might find application in genetic screening or compressed genotyping. We show that our results are robust with respect to the uncertainty in the matrix F when some elements are mistaken., 5 pages

We consider dictionary learning and blind calibration for signals and matrices created from a random ensemble. We study the mean-squared error in the limit of large signal dimension using the replica method and unveil the appearance of phase transitions delimiting impossible, possible-but-hard and possible inference regions. We also introduce an approximate message passing algorithm that asymptotically matches the theoretical performance, and show through numerical tests that it performs very well, for the calibration problem, for tractable system sizes., 5 pages

We study the zero temperature limit of a simple model of slow relaxation without energy barriers, proposed by Ritort (1995), as well as two other closely related models with a much faster relaxation. These models can be mapped onto random walk problems, which allows for their analytic study. We analyse, in particular, a specific aspect of the former model, namely the existence of a bias leading to `entropy barriers` and to a very slow relaxation.

We study the Metropolis dynamics of a simple spin system without disorder, which exhibits glassy dynamics at low temperatures. We use an implementation of the algorithm of Bortz, Kalos and Lebowitz \cite{bortz}. This method turns out to be very efficient for the study of glassy systems, which get trapped in local minima on many different time scales. We find strong evidence of aging effects at low temperatures. We relate these effects to the distribution function of the trapping times of single configurations., Comment: 8 pages Revtex, 7 figures uuencoded (Revised version: the figures are now present)

The origin of continuous energy spectra in large disordered interacting quantum systems is one of the key unsolved problems in quantum physics. Although small quantum systems with discrete energy levels are noiseless and stay coherent forever in the absence of any coupling to external world, most large-scale quantum systems are able to produce a thermal bath and excitation decay. This intrinsic decoherence is manifested by a broadening of energy levels, which aquire a finite width. The important question is: what is the driving force and the mechanism of transition(s) between these two types of many-body systems - with and without intrinsic decoherence? Here we address this question via the numerical study of energy-level statistics of a system of interacting spin-1/2 with random transverse fields. We present the first evidence for a well-defined quantum phase transition between domains of discrete and continous many-body spectra in such spin models, implying the appearance of novel insulating phases in the vicinity of the superconductor-insulator transition in InO(x) and similar materials.

In sexual population, recombination reshuffles genetic variation and produces novel combinations of existing alleles, while selection amplifies the fittest genotypes in the population. If recombination is more rapid than selection, populations consist of a diverse mixture of many genotypes, as is observed in many populations. In the opposite regime, which is realized for example in the facultatively sexual populations that outcross in only a fraction of reproductive cycles, selection can amplify individual genotypes into large clones. Such clones emerge when the fitness advantage of some of the genotypes is large enough that they grow to a significant fraction of the population despite being broken down by recombination. The occurrence of this "clonal condensation" depends, in addition to the outcrossing rate, on the heritability of fitness. Clonal condensation leads to a strong genetic heterogeneity of the population which is not adequately described by traditional population genetics measures, such as Linkage Disequilibrium. Here we point out the similarity between clonal condensation and the freezing transition in the Random Energy Model of spin glasses. Guided by this analogy we explicitly calculate the probability, Y, that two individuals are genetically identical as a function of the key parameters of the model. While Y is the analog of the spin-glass order parameter, it is also closely related to rate of coalescence in population genetics: Two individuals that are part of the same clone have a recent common ancestor., revised version

We study the random K-satisfiability problem using a partition function where each solution is reweighted according to the number of variables that satisfy every clause. We apply belief propagation and the related cavity method to the reweighted partition function. This allows us to obtain several new results on the properties of random K-satisfiability problem. In particular the reweighting allows to introduce a planted ensemble that generates instances that are, in some region of parameters, equivalent to random instances. We are hence able to generate at the same time a typical random SAT instance and one of its solutions. We study the relation between clustering and belief propagation fixed points and we give a direct evidence for the existence of purely entropic (rather than energetic) barriers between clusters in some region of parameters in the random K-satisfiability problem. We exhibit, in some large planted instances, solutions with a non-trivial whitening core; such solutions were known to exist but were so far never found on very large instances. Finally, we discuss algorithmic hardness of such planted instances and we determine a region of parameters in which planting leads to satisfiable benchmarks that, up to our knowledge, are the hardest known., 23 pages, 4 figures, revised for readability, stability expression corrected

Compressed sensing is triggering a major evolution in signal acquisition. It consists in sampling a sparse signal at low rate and later using computational power for its exact reconstruction, so that only the necessary information is measured. Currently used reconstruction techniques are, however, limited to acquisition rates larger than the true density of the signal. We design a new procedure which is able to reconstruct exactly the signal with a number of measurements that approaches the theoretical limit in the limit of large systems. It is based on the joint use of three essential ingredients: a probabilistic approach to signal reconstruction, a message-passing algorithm adapted from belief propagation, and a careful design of the measurement matrix inspired from the theory of crystal nucleation. The performance of this new algorithm is analyzed by statistical physics methods. The obtained improvement is confirmed by numerical studies of several cases., 20 pages, 8 figures, 3 tables. Related codes and data are available at http://aspics.krzakala.org

Compressed sensing is a signal processing method that acquires data directly in a compressed form. This allows one to make less measurements than what was considered necessary to record a signal, enabling faster or more precise measurement protocols in a wide range of applications. Using an interdisciplinary approach, we have recently proposed in [arXiv:1109.4424] a strategy that allows compressed sensing to be performed at acquisition rates approaching to the theoretical optimal limits. In this paper, we give a more thorough presentation of our approach, and introduce many new results. We present the probabilistic approach to reconstruction and discuss its optimality and robustness. We detail the derivation of the message passing algorithm for reconstruction and expectation max- imization learning of signal-model parameters. We further develop the asymptotic analysis of the corresponding phase diagrams with and without measurement noise, for different distribution of signals, and discuss the best possible reconstruction performances regardless of the algorithm. We also present new efficient seeding matrices, test them on synthetic data and analyze their performance asymptotically., Comment: 42 pages, 37 figures, 3 appendixes

We study the off equilibrium dynamics of a mean field disordered systems which can be interpreted both as a long range interaction spin glass and as a particle in a random potential. The statics of this problem is well known and exhibits a low temperature spin glass phase with continuous replica symmetry breaking. We study the equations of off equilibrium dynamics with analytical and numerical methods. In the spin glass phase, we find that the usual equilibrium dynamics (observed when the observation time is much smaller than the waiting time) coexists with an aging regime. In this aging regime, we propose a solution implying a hierarchy of crossovers between the observation time and the waiting time., LaTeX, LPTENS preprint 94/05

The high temperature phase of the three dimensional random field Ising model is studied using replica symmetry breaking framework. It is found that, above the ferromagnetic transition temperature T_f, there appears a glassy phase at intermediate temperatures T_fT_b only. Correlation length at T_b is computed and found to be compatible with previous numerical results., Comment: 7 pages, LaTeX file, preprint 1014 - Rome I

We study disordered systems with the replica method keeping the number of replicas finite and negative. This is shown to bias the distribution of samples towards overfrustrated ones. General results on the thermodynamics of such a system is presented. The physical situation described by this finite-n approach is one where the usually quenched variables evolve on long timescales, their evolution being driven by the quasi-equilibrium correlations of the thermalized variables. In the case of neural networks this amounts to a coupled dynamics of neurons (on fast timescales) and synapses (on longer timescales). The storage capacity of the Hopfield model is shown to be substantially increased by these coupled dynamics.