Sampling with flows, diffusion, and autoregressive neural networks from a spin-glass perspective.

Recent years witnessed the development of powerful generative models based on flows, diffusion, or autoregressive neural networks, achieving remarkable success in generating data from examples with applications in a broad range of areas. A theoretical analysis of the performance and understanding of the limitations of these methods remain, however, challenging. In this paper, we undertake a step in this direction by analyzing the efficiency of sampling by these methods on a class of problems with a known probability distribution and comparing it with the sampling performance of more traditional methods such as the Monte Carlo Markov chain and Langevin dynamics.

Gaussian universality of perceptrons with random labels.

While classical in many theoretical settings-and in particular in statistical physics-inspired works-the assumption of Gaussian i.i.d.

Bayesian reconstruction of memories stored in neural networks from their connectivity.

The advent of comprehensive synaptic wiring diagrams of large neural circuits has created the field of connectomics and given rise to a number of open research questions. One such question is whether it is possible to reconstruct the information stored in a recurrent network of neurons, given its synaptic connectivity matrix. Here, we address this question by determining when solving such an inference problem is theoretically possible in specific attractor network models and by providing a practical algorithm to do so.

Epidemic mitigation by statistical inference from contact tracing data.

Contact tracing is an essential tool to mitigate the impact of a pandemic, such as the COVID-19 pandemic. In order to achieve efficient and scalable contact tracing in real time, digital devices can play an important role. While a lot of attention has been paid to analyzing the privacy and ethical risks of the associated mobile applications, so far much less research has been devoted to optimizing their performance and assessing their impact on the mitigation of the epidemic.

Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup.

Deep neural networks achieve stellar generalisation even when they have enough parameters to easily fit all their training data. We study this phenomenon by analysing the dynamics and the performance of over-parameterised two-layer neural networks in the teacher-student setup, where one network, the student, is trained on data generated by another network, called the teacher. We show how the dynamics of stochastic gradient descent (SGD) is captured by a set of differential equations and prove that this description is asymptotically exact in the limit of large inputs.

Optimal errors and phase transitions in high-dimensional generalized linear models.

Generalized linear models (GLMs) are used in high-dimensional machine learning, statistics, communications, and signal processing. In this paper we analyze GLMs when the data matrix is random, as relevant in problems such as compressed sensing, error-correcting codes, or benchmark models in neural networks. We evaluate the mutual information (or "free entropy") from which we deduce the Bayes-optimal estimation and generalization errors.

Reference-less measurement of the transmission matrix of a highly scattering material using a DMD and phase retrieval techniques.

This paper investigates experimental means of measuring the transmission matrix (TM) of a highly scattering medium, with the simplest optical setup. Spatial light modulation is performed by a digital micromirror device (DMD), allowing high rates and high pixel counts but only binary amplitude modulation. On the sensor side, without a reference beam, the CCD camera provides only intensity measurements.

Model selection for degree-corrected block models.

The proliferation of models for networks raises challenging problems of model selection: the data are sparse and globally dependent, and models are typically high-dimensional and have large numbers of latent variables. Together, these issues mean that the usual model-selection criteria do not work properly for networks. We illustrate these challenges, and show one way to resolve them, by considering the key network-analysis problem of dividing a graph into communities or blocks of nodes with homogeneous patterns of links to the rest of the network.

Spectral redemption in clustering sparse networks.

Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal, in some cases completely failing to detect communities even when other algorithms such as belief propagation can do so. Here, we present a class of spectral algorithms based on a nonbacktracking walk on the directed edges of the graph.

Fragility and hysteretic creep in frictional granular jamming.

The granular jamming transition is experimentally investigated in a two-dimensional system of frictional, bidispersed disks subject to quasistatic, uniaxial compression without vibrational disturbances (zero granular temperature). Three primary results are presented in this experimental study. First, using disks with different static friction coefficients (μ), we experimentally verify numerical results that predict jamming onset at progressively lower packing fractions with increasing friction.

Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications.

In this paper we extend our previous work on the stochastic block model, a commonly used generative model for social and biological networks, and the problem of inferring functional groups or communities from the topology of the network. We use the cavity method of statistical physics to obtain an asymptotically exact analysis of the phase diagram. We describe in detail properties of the detectability-undetectability phase transition and the easy-hard phase transition for the community detection problem.

Inference and phase transitions in the detection of modules in sparse networks.

We present an asymptotically exact analysis of the problem of detecting communities in sparse random networks generated by stochastic block models. Using the cavity method of statistical physics and its relationship to belief propagation, we unveil a phase transition from a regime where we can infer the correct group assignments of the nodes to one where these groups are undetectable. Our approach yields an optimal inference algorithm for detecting modules, including both assortative and disassortative functional modules, assessing their significance, and learning the parameters of the underlying block model.

On melting dynamics and the glass transition. II. Glassy dynamics as a melting process.

There are deep analogies between the melting dynamics in systems with a first-order phase transition and the dynamics from equilibrium in super-cooled liquids. For a class of Ising spin models undergoing a first-order transition--namely p-spin models on the so-called Nishimori line--it can be shown that the melting dynamics can be exactly mapped to the equilibrium dynamics. In this mapping the dynamical--or mode-coupling--glass transition corresponds to the spinodal point, while the Kauzmann transition corresponds to the first-order phase transition itself.

On melting dynamics and the glass transition. I. Glassy aspects of melting dynamics.

The following properties are in the present literature associated with the behavior of supercooled glass-forming liquids: faster than exponential growth of the relaxation time, dynamical heterogeneities, growing point-to-set correlation length, crossover from mean-field behavior to activated dynamics. In this paper we argue that these properties are also present in a much simpler situation, namely the melting of the bulk of an ordered phase beyond a first order phase transition point. This is a promising path toward a better theoretical, numerical and experimental understanding of the above phenomena and of the physics of supercooled liquids.

Elusive spin-glass phase in the random field Ising model.

We show rigorously that the spin-glass susceptibility in the random field Ising model is always bounded by the ferromagnetic susceptibility, and therefore that no spin-glass phase can be present at equilibrium out of the ferromagnetic critical line. When the magnetization is, however, fixed to values smaller than the equilibrium value, a spin-glass phase can exist, as we show explicitly on the Bethe lattice.

First-order transitions and the performance of quantum algorithms in random optimization problems.

We present a study of the phase diagram of a random optimization problem in the presence of quantum fluctuations. Our main result is the characterization of the nature of the phase transition, which we find to be a first-order quantum phase transition. We provide evidence that the gap vanishes exponentially with the system size at the transition.

Inference in particle tracking experiments by passing messages between images.

Methods to extract information from the tracking of mobile objects/particles have broad interest in biological and physical sciences. Techniques based on simple criteria of proximity in time-consecutive snapshots are useful to identify the trajectories of the particles. However, they become problematic as the motility and/or the density of the particles increases due to uncertainties on the trajectories that particles followed during the images' acquisition time.

Jamming versus glass transitions.

Recent ideas based on the properties of assemblies of frictionless particles in mechanical equilibrium provide a perspective of amorphous systems different from that offered by the traditional approach originating in liquid theory. The relation, if any, between these two points of view, and the relevance of the former to the glass phase, has been difficult to ascertain. In this Letter, we introduce a model for which both theories apply strictly: it exhibits on the one hand an ideal glass transition and on the other "jamming" features (fragility, soft modes) virtually identical to that of real systems.

Hiding quiet solutions in random constraint satisfaction problems.

We study constraint satisfaction problems on the so-called planted random ensemble. We show that for a certain class of problems, e.g.

Lattice model for colloidal gels and glasses.

We study a lattice model of attractive colloids. It is exactly solvable on sparse random graphs. As the pressure and temperature are varied, it reproduces many characteristic phenomena of liquids, glasses, and colloidal systems such as ideal gel formation, liquid-glass phase coexistence, jamming, or the re-entrance of the glass transition.

Simple glass models and their quantum annealing.

We study first-order quantum phase transitions in mean-field spin glasses. We solve the quantum random energy model using elementary methods and show that at the transition the eigenstate suddenly projects onto the unperturbed ground state and that the gap between the lowest states is exponentially small in the system size. We argue that this is a generic feature of all "random first-order" models, which includes benchmarks such as random satisfiability.

Behavior of Ising spin glasses in a magnetic field.

We study the existence of a spin-glass phase in a field using Monte Carlo simulations performed along a nontrivial path in the field-temperature plane that must cross any putative de Almeida-Thouless instability line. The method is first tested on the Ising spin glass on a Bethe lattice where the instability line separating the spin glass from the paramagnetic state is also computed analytically. While the instability line is reproduced by our simulations on the mean-field Bethe lattice, no such instability line can be found numerically for the short-range three-dimensional model.

Phase transitions in the coloring of random graphs.

We consider the problem of coloring the vertices of a large sparse random graph with a given number of colors so that no adjacent vertices have the same color. Using the cavity method, we present a detailed and systematic analytical study of the space of proper colorings (solutions). We show that for a fixed number of colors and as the average vertex degree (number of constraints) increases, the set of solutions undergoes several phase transitions similar to those observed in the mean field theory of glasses.

Landscape analysis of constraint satisfaction problems.

We discuss an analysis of constraint satisfaction problems, such as sphere packing, K-SAT, and graph coloring, in terms of an effective energy landscape. Several intriguing geometrical properties of the solution space become in this light familiar in terms of the well-studied ones of rugged (glassy) energy landscapes. A benchmark algorithm naturally suggested by this construction finds solutions in polynomial time up to a point beyond the clustering and in some cases even the thermodynamic transitions.