Stochastic Gradient Descent-like relaxation is equivalent to Metropolis dynamics in discrete optimization and inference problems.

Is Stochastic Gradient Descent (SGD) substantially different from Metropolis Monte Carlo dynamics? This is a fundamental question at the time of understanding the most used training algorithm in the field of Machine Learning, but it received no answer until now. Here we show that in discrete optimization and inference problems, the dynamics of an SGD-like algorithm resemble very closely that of Metropolis Monte Carlo with a properly chosen temperature, which depends on the mini-batch size. This quantitative matching holds both at equilibrium and in the out-of-equilibrium regime, despite the two algorithms having fundamental differences (e.g. SGD does not satisfy detailed balance). Such equivalence allows us to use results about performances and limits of Monte Carlo algorithms to optimize the mini-batch size in the SGD-like algorithm and make it efficient at recovering the signal in hard inference problems.

Multifractality in spin glasses.

We unveil the multifractal behavior of Ising spin glasses in their low-temperature phase. Using the Janus II custom-built supercomputer, the spin-glass correlation function is studied locally. Dramatic fluctuations are found when pairs of sites at the same distance are compared. The scaling of these fluctuations, as the spin-glass coherence length grows with time, is characterized through the computation of the singularity spectrum and its corresponding Legendre transform. A comparatively small number of site pairs controls the average correlation that governs the response to a magnetic field. We explain how this scenario of dramatic fluctuations (at length scales smaller than the coherence length) can be reconciled with the smooth, self-averaging behavior that has long been considered to describe spin-glass dynamics.

Hard-sphere jamming through the lens of linear optimization.

The jamming transition is ubiquitous. It is present in granular matter, foams, colloids, structural glasses, and many other systems. Yet, it defines a critical point whose properties still need to be fully understood. Recently, a major breakthrough came about when the replica formalism was extended to build a mean-field theory that provides an exact description of the jamming transition of spherical particles in the infinite-dimensional limit. While such theory explains the jamming critical behavior of both soft and hard spheres, investigating the transition in finite-dimensional systems poses very difficult and different problems, in particular from the numerical point of view. Soft particles are modeled by continuous potentials; thus, their jamming point can be reached through efficient energy minimization algorithms. In contrast, the latter methods are inapplicable to hard-sphere (HS) systems since the interaction energy among the particles is always zero by construction. To overcome these difficulties, here we recast the jamming of hard spheres as a constrained optimization problem and introduce the CALiPPSO algorithm, capable of readily producing jammed HS packings without including any effective potential. This algorithm brings a HS configuration of arbitrary dimensions to its jamming point by solving a chain of linear optimization problems. We show that there is a strict correspondence between the force balance conditions of jammed packings and the properties of the optimal solutions of CALiPPSO, whence we prove analytically that our packings are always isostatic and in mechanical equilibrium. Furthermore, using extensive numerical simulations, we show that our algorithm is able to probe the complex structure of the free-energy landscape, finding qualitative agreement with mean-field predictions. We also characterize the algorithmic complexity of CALiPPSO and provide an open-source implementation of it.

Closest-vector problem and the zero-temperature p-spin landscape for lossy compression.

We consider a high-dimensional random constrained optimization problem in which a set of binary variables is subjected to a linear system of equations. The cost function is a simple linear cost, measuring the Hamming distance with respect to a reference configuration. Despite its apparent simplicity, this problem exhibits a rich phenomenology. We show that different situations arise depending on the random ensemble of linear systems. When each variable is involved in at most two linear constraints, we show that the problem can be partially solved analytically, in particular we show that upon convergence, the zero-temperature limit of the cavity equations returns the optimal solution. We then study the geometrical properties of more general random ensembles. In particular we observe a range in the density of constraints at which the system enters a glassy phase where the cost function has many minima. Interestingly, the algorithmic performances are only sensitive to another phase transition affecting the structure of configurations allowed by the linear constraints. We also extend our results to variables belonging to GF(q), the Galois field of order q. We show that increasing the value of q allows to achieve a better optimum, which is confirmed by the replica-symmetric cavity method predictions.

Unexpected Upper Critical Dimension for Spin Glass Models in a Field Predicted by the Loop Expansion around the Bethe Solution at Zero Temperature.

The spin-glass transition in a field in finite dimension is analyzed directly at zero temperature using a perturbative loop expansion around the Bethe lattice solution. The loop expansion is generated by the M-layer construction whose first diagrams are evaluated numerically and analytically. The generalized Ginzburg criterion reveals that the upper critical dimension below which mean-field theory fails is D_{U}≥8, at variance with the classical result D_{U}=6 yielded by finite-temperature replica field theory. Our expansion around the Bethe lattice has two crucial differences with respect to the classical one. The finite connectivity z of the lattice is directly included from the beginning in the Bethe lattice, while in the classical computation the finite connectivity is obtained through an expansion in 1/z. Moreover, if one is interested in the zero temperature (T=0) transition, one can directly expand around the T=0 Bethe transition. The expansion directly at T=0 is not possible in the classical framework because the fully connected spin glass does not have a transition at T=0, being in the broken phase for any value of the external field.

Finite-size effects in the microscopic critical properties of jammed configurations: A comprehensive study of the effects of different types of disorder.

Jamming criticality defines a universality class that includes systems as diverse as glasses, colloids, foams, amorphous solids, constraint satisfaction problems, neural networks, etc. A particularly interesting feature of this class is that small interparticle forces (f) and gaps (h) are distributed according to nontrivial power laws. A recently developed mean-field (MF) theory predicts the characteristic exponents of these distributions in the limit of very high spatial dimension, d→∞ and, remarkably, their values seemingly agree with numerical estimates in physically relevant dimensions, d=2 and 3. These exponents are further connected through a pair of inequalities derived from stability conditions, and both theoretical predictions and previous numerical investigations suggest that these inequalities are saturated. Systems at the jamming point are thus only marginally stable. Despite the key physical role played by these exponents, their systematic evaluation has yet to be attempted. Here, we carefully test their value by analyzing the finite-size scaling of the distributions of f and h for various particle-based models for jamming. Both dimension and the direction of approach to the jamming point are also considered. We show that, in all models, finite-size effects are much more pronounced in the distribution of h than in that of f. We thus conclude that gaps are correlated over considerably longer scales than forces. Additionally, remarkable agreement with MF predictions is obtained in all but one model, namely near-crystalline packings. Our results thus help to better delineate the domain of the jamming universality class. We furthermore uncover a secondary linear regime in the distribution tails of both f and h. This surprisingly robust feature is understood to follow from the (near) isostaticity of our configurations.

Inferring the particle-wise dynamics of amorphous solids from the local structure at the jamming point.

Jamming is a phenomenon shared by a wide variety of systems, such as granular materials, foams, and glasses in their high density regime. This has motivated the development of a theoretical framework capable of explaining many of their static critical properties with a unified approach. However, the dynamics occurring in the vicinity of the jamming point has received little attention and the problem of finding a connection with the local structure of the configuration remains unexplored. Here we address this issue by constructing physically well defined structural variables using the information contained in the network of contacts of jammed configurations, and then showing that such variables yield a resilient statistical description of the particle-wise dynamics near this critical point. Our results are based on extensive numerical simulations of systems of spherical particles that allow us to statistically characterize the trajectories of individual particles in terms of their first two moments. We first demonstrate that, besides displaying a broad distribution of mobilities, particles may also have preferential directions of motion. Next, we associate each of these features with a structural variable computed uniquely in terms of the contact vectors at jamming, obtaining considerably high statistical correlations. The robustness of our approach is confirmed by testing two types of dynamical protocols, namely molecular dynamics and Monte Carlo, with different types of interaction. We also provide evidence that the dynamical regime we study here is dominated by anharmonic effects and therefore it cannot be described properly in terms of vibrational modes. Finally, we show that correlations decay slowly and in an interaction-independent fashion, suggesting a universal rate of information loss.

SpaRTA Tracking Across Occlusions via Partitioning of 3D Clouds of Points.

Any 3D tracking algorithm has to deal with occlusions: multiple targets get so close to each other that the loss of their identities becomes likely; hence, potentially affecting the very quality of the data with interrupted trajectories and identity switches. Here, we present a novel tracking method that addresses the problem of occlusions within large groups of featureless objects by means of three steps: i) it represents each target as a cloud of points in 3D; ii) once a 3D cluster corresponding to an occlusion occurs, it defines a partitioning problem by introducing a cost function that uses both attractive and repulsive spatio-temporal proximity links; and iii) it minimizes the cost function through a semi-definite optimization technique specifically designed to cope with the presence of multi-minima landscapes. The algorithm is designed to work on 3D data regardless of the experimental method used: multicamera systems, lidars, radars, and RGB-D systems. By performing tests on public data-sets, we show that the new algorithm produces a significant improvement over the state-of-the-art tracking methods, both by reducing the number of identity switches and by increasing the accuracy of the estimated positions of the targets in real space.

Spin Glasses in a Field Show a Phase Transition Varying the Distance among Real Replicas (And How to Exploit It to Find the Critical Line in a Field).

We discuss a phase transition in spin glass models that have been rarely considered in the past, namely, the phase transition that may take place when two real replicas are forced to be at a larger distance (i.e., at a smaller overlap) than the typical one. In the first part of the work, by solving analytically the Sherrington-Kirkpatrick model in a field close to its critical point, we show that, even in a paramagnetic phase, the forcing of two real replicas to an overlap small enough leads the model to a phase transition where the symmetry between replicas is spontaneously broken. More importantly, this phase transition is related to the de Almeida-Thouless (dAT) critical line. In the second part of the work, we exploit the phase transition in the overlap between two real replicas to identify the critical line in a field in finite dimensional spin glasses. This is a notoriously difficult computational problem, because of considerable finite size corrections. We introduce a new method of analysis of Monte Carlo data for disordered systems, where the overlap between two real replicas is used as a conditioning variate. We apply this analysis to equilibrium measurements collected in the paramagnetic phase in a field, h > 0 and T c ( h ) < T < T c ( h = 0 ) , of the d = 1 spin glass model with long range interactions decaying fast enough to be outside the regime of validity of the mean field theory. We thus provide very reliable estimates for the thermodynamic critical temperature in a field.

Strong ergodicity breaking in aging of mean-field spin glasses.

Out-of-equilibrium relaxation processes show aging if they become slower as time passes. Aging processes are ubiquitous and play a fundamental role in the physics of glasses and spin glasses and in other applications (e.g., in algorithms minimizing complex cost/loss functions). The theory of aging in the out-of-equilibrium dynamics of mean-field spin glass models has achieved a fundamental role, thanks to the asymptotic analytic solution found by Cugliandolo and Kurchan. However, this solution is based on assumptions (e.g., the weak ergodicity breaking hypothesis) which have never been put under a strong test until now. In the present work, we present the results of an extraordinary large set of numerical simulations of the prototypical mean-field spin glass models, namely the Sherrington-Kirkpatrick and the Viana-Bray models. Thanks to a very intensive use of graphics processing units (GPUs), we have been able to run the latter model for more than [Formula: see text] spin updates and thus safely extrapolate the numerical data both in the thermodynamical limit and in the large times limit. The measurements of the two-times correlation functions in isothermal aging after a quench from a random initial configuration to a temperature [Formula: see text] provides clear evidence that, at large times, such correlations do not decay to zero as expected by assuming weak ergodicity breaking. We conclude that strong ergodicity breaking takes place in mean-field spin glasses aging dynamics which, asymptotically, takes place in a confined configurational space. Theoretical models for the aging dynamics need to be revised accordingly.

Loop expansion around the Bethe solution for the random magnetic field Ising ferromagnets at zero temperature.

We apply to the random-field Ising model at zero temperature ([Formula: see text]) the perturbative loop expansion around the Bethe solution. A comparison with the standard ϵ expansion is made, highlighting the key differences that make the expansion around the Bethe solution much more appropriate to correctly describe strongly disordered systems, especially those controlled by a [Formula: see text] renormalization group (RG) fixed point. The latter loop expansion produces an effective theory with cubic vertices. We compute the one-loop corrections due to cubic vertices, finding additional terms that are absent in the ϵ expansion. However, these additional terms are subdominant with respect to the standard, supersymmetric ones; therefore, dimensional reduction is still valid at this order of the loop expansion.

Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs.

The effectiveness of stochastic algorithms based on Monte Carlo dynamics in solving hard optimization problems is mostly unknown. Beyond the basic statement that at a dynamical phase transition the ergodicity breaks and a Monte Carlo dynamics cannot sample correctly the probability distribution in times linear in the system size, there are almost no predictions or intuitions on the behavior of this class of stochastic dynamics. The situation is particularly intricate because, when using a Monte Carlo-based algorithm as an optimization algorithm, one is usually interested in the out-of-equilibrium behavior, which is very hard to analyze. Here we focus on the use of parallel tempering in the search for the largest independent set in a sparse random graph, showing that it can find solutions well beyond the dynamical threshold. Comparison with state-of-the-art message passing algorithms reveals that parallel tempering is definitely the algorithm performing best, although a theory explaining its behavior is still lacking.

The Mpemba effect in spin glasses is a persistent memory effect.

The Mpemba effect occurs when a hot system cools faster than an initially colder one, when both are refrigerated in the same thermal reservoir. Using the custom-built supercomputer Janus II, we study the Mpemba effect in spin glasses and show that it is a nonequilibrium process, governed by the coherence length ξ of the system. The effect occurs when the bath temperature lies in the glassy phase, but it is not necessary for the thermal protocol to cross the critical temperature. In fact, the Mpemba effect follows from a strong relationship between the internal energy and ξ that turns out to be a sure-tell sign of being in the glassy phase. Thus, the Mpemba effect presents itself as an intriguing avenue for the experimental study of the coherence length in supercooled liquids and other glass formers.

Typology of phase transitions in Bayesian inference problems.

Many inference problems undergo phase transitions as a function of the signal-to-noise ratio, a prominent example of this phenomenon being found in the stochastic block model (SBM) that generates a random graph with a hidden community structure. Some of these phase transitions affect the information-theoretic optimal (but possibly computationally expensive) estimation procedure, others concern the behavior of efficient iterative algorithms. A computational gap opens when the phase transitions for these two aspects do not coincide, leading to a hard phase in which optimal inference is computationally challenging. In this paper we refine this description in two ways. From a qualitative perspective, we emphasize the existence of more generic phase diagrams with a hybrid-hard phase, in which it is computationally easy to reach a nontrivial inference accuracy but computationally hard to match the information-theoretic optimal one. We support this discussion by quantitative expansions of the functional cavity equations that describe inference problems on sparse graphs, around their trivial solution. These expansions shed light on the existence of hybrid-hard phases, for a large class of planted constraint satisfaction problems, and on the question of the tightness of the Kesten-Stigum (KS) bound for the associated tree reconstruction problem. Our results show that the instability of the trivial fixed point is not generic evidence for the Bayes optimality of the message-passing algorithms. We clarify in particular the status of the symmetric SBM with four communities and of the tree reconstruction of the associated Potts model: In the assortative (ferromagnetic) case the KS bound is always tight, whereas in the disassortative (antiferromagnetic) case we exhibit an explicit criterion involving the degree distribution that separates a large-degree regime where the KS bound is tight and a low-degree regime where it is not. We also investigate the SBM with two communities of different sizes, also known as the asymmetric Ising model, and describe quantitatively its computational gap as a function of its asymmetry, as well as a version of the SBM with two groups of q_{1} and q_{2} communities. We complement this study with numerical simulations of the belief propagation iterative algorithm, confirming that its behavior on large samples is well described by the cavity method.

Gauge-free cluster variational method by maximal messages and moment matching.

We present an implementation of the cluster variational method (CVM) as a message passing algorithm. The kind of message passing algorithm used for CVM, usually named generalized belief propagation (GBP), is a generalization of the belief propagation algorithm in the same way that CVM is a generalization of the Bethe approximation for estimating the partition function. However, the connection between fixed points of GBP and the extremal points of the CVM free energy is usually not a one-to-one correspondence because of the existence of a gauge transformation involving the GBP messages. Our contribution is twofold. First, we propose a way of defining messages (fields) in a generic CVM approximation, such that messages arrive on a given region from all its ancestors, and not only from its direct parents, as in the standard parent-to-child GBP. We call this approach maximal messages. Second, we focus on the case of binary variables, reinterpreting the messages as fields enforcing the consistency between the moments of the local (marginal) probability distributions. We provide a precise rule to enforce all consistencies, avoiding any redundancy, that would otherwise lead to a gauge transformation on the messages. This moment matching method is gauge free, i.e., it guarantees that the resulting GBP is not gauge invariant. We apply our maximal messages and moment matching GBP to obtain an analytical expression for the critical temperature of the Ising model in general dimensions at the level of plaquette CVM. The values obtained outperform Bethe estimates, and are comparable with loop corrected belief propagation equations. The method allows for a straightforward generalization to disordered systems.

A statics-dynamics equivalence through the fluctuation-dissipation ratio provides a window into the spin-glass phase from nonequilibrium measurements.

We have performed a very accurate computation of the nonequilibrium fluctuation-dissipation ratio for the 3D Edwards-Anderson Ising spin glass, by means of large-scale simulations on the special-purpose computers Janus and Janus II. This ratio (computed for finite times on very large, effectively infinite, systems) is compared with the equilibrium probability distribution of the spin overlap for finite sizes. Our main result is a quantitative statics-dynamics dictionary, which could allow the experimental exploration of important features of the spin-glass phase without requiring uncontrollable extrapolations to infinite times or system sizes.

The backtracking survey propagation algorithm for solving random K-SAT problems.

Discrete combinatorial optimization has a central role in many scientific disciplines, however, for hard problems we lack linear time algorithms that would allow us to solve very large instances. Moreover, it is still unclear what are the key features that make a discrete combinatorial optimization problem hard to solve. Here we study random K-satisfiability problems with K=3,4, which are known to be very hard close to the SAT-UNSAT threshold, where problems stop having solutions. We show that the backtracking survey propagation algorithm, in a time practically linear in the problem size, is able to find solutions very close to the threshold, in a region unreachable by any other algorithm. All solutions found have no frozen variables, thus supporting the conjecture that only unfrozen solutions can be found in linear time, and that a problem becomes impossible to solve in linear time when all solutions contain frozen variables.

Solving the inverse Ising problem by mean-field methods in a clustered phase space with many states.

In this work we explain how to properly use mean-field methods to solve the inverse Ising problem when the phase space is clustered, that is, many states are present. The clustering of the phase space can occur for many reasons, e.g., when a system undergoes a phase transition, but also when data are collected in different regimes (e.g., quiescent and spiking regimes in neural networks). Mean-field methods for the inverse Ising problem are typically used without taking into account the eventual clustered structure of the input configurations and may lead to very poor inference (e.g., in the low-temperature phase of the Curie-Weiss model). In this work we explain how to modify mean-field approaches when the phase space is clustered and we illustrate the effectiveness of our method on different clustered structures (low-temperature phases of Curie-Weiss and Hopfield models).

Phase transitions in semidefinite relaxations.

Statistical inference problems arising within signal processing, data mining, and machine learning naturally give rise to hard combinatorial optimization problems. These problems become intractable when the dimensionality of the data is large, as is often the case for modern datasets. A popular idea is to construct convex relaxations of these combinatorial problems, which can be solved efficiently for large-scale datasets. Semidefinite programming (SDP) relaxations are among the most powerful methods in this family and are surprisingly well suited for a broad range of problems where data take the form of matrices or graphs. It has been observed several times that when the statistical noise is small enough, SDP relaxations correctly detect the underlying combinatorial structures. In this paper we develop asymptotic predictions for several detection thresholds, as well as for the estimation error above these thresholds. We study some classical SDP relaxations for statistical problems motivated by graph synchronization and community detection in networks. We map these optimization problems to statistical mechanics models with vector spins and use nonrigorous techniques from statistical mechanics to characterize the corresponding phase transitions. Our results clarify the effectiveness of SDP relaxations in solving high-dimensional statistical problems.

Multiple phases in modularity-based community detection.

Detecting communities in a network, based only on the adjacency matrix, is a problem of interest to several scientific disciplines. Recently, Zhang and Moore have introduced an algorithm [Proc. Natl. Acad. Sci. USA 111, 18144 (2014)], called mod-bp, that avoids overfitting the data by optimizing a weighted average of modularity (a popular goodness-of-fit measure in community detection) and entropy (i.e., number of configurations with a given modularity). The adjustment of the relative weight, the "temperature" of the model, is crucial for getting a correct result from mod-bp. In this work we study the many phase transitions that mod-bp may undergo by changing the two parameters of the algorithm: the temperature T and the maximum number of groups q. We introduce a new set of order parameters that allow us to determine the actual number of groups q̂, and we observe on both synthetic and real networks the existence of phases with any q̂∈{1,q}, which were unknown before. We discuss how to interpret the results of mod-bp and how to make the optimal choice for the problem of detecting significant communities.