Researcher profile

Federico Ricci-Tersenghi

Federico Ricci-Tersenghi contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
30works
0followers
10topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

30 published item(s)

preprint2026arXiv

Low energy excitations in a long prism geometry: computing the lower critical dimension of the Ising spin glass

We propose a general method for studying systems that display excitations with arbitrarily low energy in their low-temperature phase. We argue that in a rectangular right prism geometry, with longitudinal size much larger than the transverse size, correlations decay exponentially (at all temperatures) along the longitudinal dimension, but the scaling of the correlation length with the transverse size carries crucial information from which the lower critical dimension can be inferred. The method is applied in the particularly demanding context of Ising spin glasses at zero magnetic field. The lower critical dimension and the multifractal spectrum for the correlation function are computed from large-scale numerical simulations. Several technical novelties (such as the unexpectedly crucial performance of Houdayer's cluster method or the convenience of using open - rather than periodic - boundary conditions) allow us to study three-dimensional prisms with transverse dimensions up to $L=24$ and effectively infinite longitudinal dimensions down to low temperatures. The value that we find for the lower critical dimension turns out to be in agreement with expectations from both the Replica Symmetry Breaking theory and the Droplet model for spin glasses. We argue that our novel setting holds promise in clarifying which of the two competing theories more accurately describes three-dimensional spin glasses.

preprint2023arXiv

Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set

The recent work ``Combinatorial Optimization with Physics-Inspired Graph Neural Networks'' [Nat Mach Intell 4 (2022) 367] introduces a physics-inspired unsupervised Graph Neural Network (GNN) to solve combinatorial optimization problems on sparse graphs. To test the performances of these GNNs, the authors of the work show numerical results for two fundamental problems: maximum cut and maximum independent set (MIS). They conclude that "the graph neural network optimizer performs on par or outperforms existing solvers, with the ability to scale beyond the state of the art to problems with millions of variables." In this comment, we show that a simple greedy algorithm, running in almost linear time, can find solutions for the MIS problem of much better quality than the GNN. The greedy algorithm is faster by a factor of $10^4$ with respect to the GNN for problems with a million variables. We do not see any good reason for solving the MIS with these GNN, as well as for using a sledgehammer to crack nuts. In general, many claims of superiority of neural networks in solving combinatorial problems are at risk of being not solid enough, since we lack standard benchmarks based on really hard problems. We propose one of such hard benchmarks, and we hope to see future neural network optimizers tested on these problems before any claim of superiority is made.

preprint2022arXiv

Low energy excitations of mean-field glasses

We study the linear excitations around typical energy minima of a mean-field disordered model with continuous degrees of freedom undergoing a Random First Order Transition (RFOT). Contrary to naive expectations, the spectra of linear excitations are ungapped and we find the presence of a pseudogap corresponding to localized excitations with arbitrary low excitation energy. Moving to deeper minima in the landscape, the excitations appear increasingly localized while their abundance decreases. Beside typical minima, there also exist rare ultra-stable minima, with an energy gap and no localised excitations.

preprint2022arXiv

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 \le 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.

preprint2021arXiv

Delocalization transition in low energy excitation modes of vector spin glasses

We study the energy minima of the fully-connected $m$-components vector spin glass model at zero temperature in an external magnetic field for $m\ge 3$. The model has a zero temperature transition from a paramagnetic phase at high field to a spin glass phase at low field. We study the eigenvalues and eigenvectors of the Hessian in the minima of the Hamiltonian. The spectrum is gapless both in the paramagnetic and in the spin glass phase, with a pseudo-gap behaving as $λ^{m-1}$ in the paramagnetic phase and as $\sqrtλ$ in the spin glass phase. Despite the long-range nature of the model, the eigenstates close to the edge of the spectrum display quasi-localization properties. We show that the paramagnetic to spin glass transition corresponds to delocalization of the edge eigenvectors. We solve the model by the cavity method in the thermodynamic limit. We also perform numerical minimization of the Hamiltonian for $N\le 2048$ and compute the spectral properties, that show very strong corrections to the asymptotic scaling approaching the critical point.

preprint2021arXiv

Optimization of the dynamic transition in the continuous coloring problem

Random constraint satisfaction problems can exhibit a phase where the number of constraints per variable $α$ makes the system solvable in theory on the one hand, but also makes the search for a solution hard, meaning that common algorithms such as Monte-Carlo method fail to find a solution. The onset of this hardness is deeply linked to the appearance of a dynamical phase transition where the phase space of the problem breaks into an exponential number of clusters. The exact position of this dynamical phase transition is not universal with respect to the details of the Hamiltonian one chooses to represent a given problem. In this paper, we develop some theoretical tools in order to find a systematic way to build a Hamiltonian that maximizes the dynamic $α_{\rm d}$ threshold. To illustrate our techniques, we will concentrate on the problem of continuous coloring, where one tries to set an angle $x_i \in [0;2π]$ on each node of a network in such a way that no adjacent nodes are closer than some threshold angle $θ$, that is $\cos(x_i - x_j) \leq \cosθ$. This problem can be both seen as a continuous version of the discrete graph coloring problem or as a one-dimensional version of the the Mari-Krzakala-Kurchan (MKK) model. The relevance of this model stems from the fact that continuous constraint satisfaction problems on sparse random graphs remain largely unexplored in statistical physics. We show that for sufficiently small angle $θ$ this model presents a random first order transition and compute the dynamical, condensation and Kesten-Stigum transitions; we also compare the analytical predictions with Monte Carlo simulations for values of $θ= 2π/q$, $q \in \mathbb{N}$. Choosing such values of $q$ allows us to easily compare our results with the renowned problem of discrete coloring.

preprint2021arXiv

Solving the fully-connected spherical $p$-spin model with the cavity method: equivalence with the replica results

The spherical $p$-spin is a fundamental model for glassy physics, thanks to its analytic solution achievable via the replica method. Unfortunately the replica method has some drawbacks: it is very hard to apply to diluted models and the assumptions beyond it are not immediately clear. Both drawbacks can be overcome by the use of the cavity method, which, however, needs to be applied with care to spherical models. Here we show how to write the cavity equations for spherical $p$-spin models on complete graphs, both in the Replica Symmetric (RS) ansatz (corresponding to Belief Propagation) and in the 1-step Replica Symmetry Breaking (1RSB) ansatz (corresponding to Survey Propagation). The cavity equations can be solved by a Gaussian (RS) and multivariate Gaussian (1RSB) ansatz for the distribution of the cavity fields. We compute the free energy in both ansatzes and check that the results are identical to the replica computation, predicting a phase transition to a 1RSB phase at low temperatures. The advantages of solving the model with the cavity method are many. The physical meaning of any ansatz for the cavity marginals is very clear. The cavity method works directly with the distribution of local quantities, which allows to generalize the method to dilute graphs. What we are presenting here is the first step towards the solution of the diluted version of the spherical $p$-spin model, which is a fundamental model in the theory of random lasers and interesting $per~se$ as an easier-to-simulate version of the classical fully-connected $p$-spin model.

preprint2020arXiv

How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA

In many high-dimensional estimation problems the main task consists in minimizing a cost function, which is often strongly non-convex when scanned in the space of parameters to be estimated. A standard solution to flatten the corresponding rough landscape consists in summing the losses associated to different data points and obtain a smoother empirical risk. Here we propose a complementary method that works for a single data point. The main idea is that a large amount of the roughness is uncorrelated in different parts of the landscape. One can then substantially reduce the noise by evaluating an empirical average of the gradient obtained as a sum over many random independent positions in the space of parameters to be optimized. We present an algorithm, called Averaged Gradient Descent, based on this idea and we apply it to tensor PCA, which is a very hard estimation problem. We show that Averaged Gradient Descent over-performs physical algorithms such as gradient descent and approximate message passing and matches the best algorithmic thresholds known so far, obtained by tensor unfolding and methods based on sum-of-squares.

preprint2020arXiv

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 which 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 huge 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.

preprint2019arXiv

Comment on &#34;Real-space renormalization-group methods for hierarchical spin glasses&#34;

In the paper [Angelini M C, Parisi G, and Ricci-Tersenghi F, Ensemble renormalization group for disordered systems, Phys. Rev. B 87 134201 (2013)] we introduced a real-space renormalization group called Ensemble Renormalization Group (ERG) and we applied it to the Edwards-Anderson model, obtaining estimates for the critical exponents in good agreement with those from Monte Carlo simulations. Recently the paper [Castellana M, Real-space renormalization-group methods for hierarchical spin glasses, J. Phys. A: Math. Theor. 52 445002 (2019)] re-examined the ERG method from a different perspective, concluding that the previous results were wrong, and claiming that the ERG method predicts trivially wrong critical exponents. In this comment we explain why the conclusions reached by Castellana are wrong, as they are based on a misinterpretation of finite-size effects. We conclude that the ERG method remains a good RG method to obtain critical exponents in strongly disordered models (if properly used).

preprint2019arXiv

New loop expansion for the Random Magnetic Field Ising Ferromagnets at zero temperature

We apply to the Random Field Ising Model at zero temperature (T= 0) the perturbative loop expansion around the Bethe solution. A comparison with the standard epsilon-expansion is made, highlighting the key differences that make the new expansion much more appropriate to correctly describe strongly disordered systems, especially those controlled by a T = 0 RG fixed point. This new loop expansion produces an effective theory with cubic vertices. We compute the one-loop corrections due to cubic vertices, finding new terms that are absent in the epsilon-expansion. However, these new terms are subdominant with respect to the standard, supersymmetric ones, therefore dimensional reduction is still valid at this order of the loop expansion.

preprint2019arXiv

Rethinking mean-field glassy dynamics and its relation with the energy landscape: the awkward case of the spherical mixed p-spin model

The spherical p-spin model is not only a fundamental model in statistical mechanics of disordered system, but has recently gained popularity since many hard problems in machine learning can be mapped on it. Thus the study of the out of equilibrium dynamics in this model is interesting both for the glass physics and for its implications on algorithms solving NP-hard problems. We revisit the long-time limit of the out of equilibrium dynamics of mean-field spherical mixed p-spin models. We consider quenches (gradient descent dynamics) starting from initial conditions thermalized at some temperature in the ergodic phase. We perform numerical integration of the dynamical mean-field equations of the model and we find an unexpected dynamical phase transition. Below an onset temperature, higher than the dynamical transition temperature, the asymptotic energy goes below the &#34;threshold energy&#34; of the dominant marginal minima of the energy function and memory of the initial condition is kept. This behavior, not present in the pure spherical p-spin model, resembles closely the one observed in simulations of glass-forming liquids. We then investigate the nature of the asymptotic dynamics, finding an aging solution that relaxes towards deep marginal minima, evolving on a restricted marginal manifold. Careful analysis, however, rules out simple aging solutions. We compute the constrained complexity in the aim of connecting the asymptotic solution to the energy landscape.

preprint2019arXiv

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 GPUs, we have been able to run the latter model for more than $2^{64}$ 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 $T<T_c$ 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.

preprint2013arXiv

A mean field method with correlations determined by linear response

We introduce a new mean-field approximation based on the reconciliation of maximum entropy and linear response for correlations in the cluster variation method. Within a general formalism that includes previous mean-field methods, we derive formulas improving upon, e.g., the Bethe approximation and the Sessak-Monasson result at high temperature. Applying the method to direct and inverse Ising problems, we find improvements over standard implementations.

preprint2013arXiv

Compressed sensing with sparse, structured matrices

In the context of the compressed sensing problem, we propose a new ensemble of sparse random matrices which allow one (i) to acquire and compress a ρ0-sparse signal of length N in a time linear in N and (ii) to perfectly recover the original signal, compressed at a rate α, by using a message passing algorithm (Expectation Maximization Belief Propagation) that runs in a time linear in N. In the large N limit, the scheme proposed here closely approaches the theoretical bound ρ0 = α, and so it is both optimal and efficient (linear time complexity). More generally, we show that several ensembles of dense random matrices can be converted into ensembles of sparse random matrices, having the same thresholds, but much lower computational complexity.

preprint2013arXiv

Ensemble renormalization group for disordered systems

We propose and study a renormalization group transformation that can be used also for models with strong quenched disorder, like spin glasses. The method is based on a mapping between disorder distributions, chosen such as to keep some physical properties (e.g., the ratio of correlations averaged over the ensemble) invariant under the transformation. We validate this ensemble renormalization group by applying it to the hierarchical model (both the diluted ferromagnetic version and the spin glass version), finding results in agreement with Monte Carlo simulations.

preprint2013arXiv

Finite size corrections to disordered systems on Erdös-Rényi random graphs

We study the finite size corrections to the free energy density in disorder spin systems on sparse random graphs, using both replica theory and cavity method. We derive an analytical expressions for the $O(1/N)$ corrections in the replica symmetric phase as a linear combination of the free energies of open and closed chains. We perform a numerical check of the formulae on the Random Field Ising Model at zero temperature, by computing finite size corrections to the ground state energy density.

preprint2012arXiv

A note on weakly discontinuous dynamical transitions

We analyze Mode Coupling discontinuous transition in the limit of vanishing discontinuity, approaching the so called &#34;$A_3$&#34; point. In these conditions structural relaxation and fluctuations appear to have universal form independent from the details of the system. The analysis of this limiting case suggests new ways for looking at the Mode Coupling equations in the general case.

preprint2012arXiv

The Bethe approximation for solving the inverse Ising problem: a comparison with other inference methods

The inverse Ising problem consists in inferring the coupling constants of an Ising model given the correlation matrix. The fastest methods for solving this problem are based on mean-field approximations, but which one performs better in the general case is still not completely clear. In the first part of this work, I summarize the formulas for several mean- field approximations and I derive new analytical expressions for the Bethe approximation, which allow to solve the inverse Ising problem without running the Susceptibility Propagation algorithm (thus avoiding the lack of convergence). In the second part, I compare the accuracy of different mean field approximations on several models (diluted ferromagnets and spin glasses) defined on random graphs and regular lattices, showing which one is in general more effective. A simple improvement over these approximations is proposed. Also a fundamental limitation is found in using methods based on TAP and Bethe approximations in presence of an external field.

preprint2011arXiv

A numerical study of the overlap probability distribution and its sample-to-sample fluctuations in a mean-field model

In this paper we study the fluctuations of the probability distributions of the overlap in mean field spin glasses in the presence of a magnetic field on the De Almeida-Thouless line. We find that there is a large tail in the left part of the distribution that is dominated by the contributions of rare samples. Different techniques are used to examine the data and to stress on different aspects of the contribution of rare samples.

preprint2011arXiv

A very fast inference algorithm for finite-dimensional spin glasses: Belief Propagation on the dual lattice

Starting from a Cluster Variational Method, and inspired by the correctness of the paramagnetic Ansatz (at high temperatures in general, and at any temperature in the 2D Edwards-Anderson model) we propose a novel message passing algorithm --- the Dual algorithm --- to estimate the marginal probabilities of spin glasses on finite dimensional lattices. We show that in a wide range of temperatures our algorithm compares very well with Monte Carlo simulations, with the Double Loop algorithm and with exact calculation of the ground state of 2D systems with bimodal and Gaussian interactions. Moreover it is usually 100 times faster than other provably convergent methods, as the Double Loop algorithm.

preprint2011arXiv

Entropic long range order in a 3D spin glass model

We uncover a new kind of entropic long range order in finite dimensional spin glasses. We study the link-diluted version of the Edwards-Anderson spin glass model with bimodal couplings (J=+/-1) on a 3D lattice. By using exact reduction algorithms, we prove that there exists a region of the phase diagram (at zero temperature and link density low enough), where spins are long range correlated, even if the ground states energy stiffness is null. In other words, in this region twisting the boundary conditions cost no energy, but spins are long range correlated by means of pure entropic effects.

preprint2011arXiv

Field Theory of Fluctuations in Glasses

We develop a field-theoretical description of dynamical heterogeneities and fluctuations in supercooled liquids close to the (avoided) MCT singularity. Using quasi-equilibrium arguments we eliminate time from the description and we completely characterize fluctuations in the beta regime. We identify different sources of fluctuations and show that the most relevant ones are associated to variations of &#34;self-induced disorder&#34; in the initial condition of the dynamics. It follows that heterogeneites can be describes through a cubic field theory with an effective random field term. The phenomenon of perturbative dimensional reduction ensues, well known in random field problems, which implies an upper critical dimension of the theory equal to 8. We apply our theory to finite size scaling for mean-field systems and we test its prediction against numerical simulations.

preprint2010arXiv

Critical behaviour of large scale dynamical heterogeneities in glasses: a complete theory

In this talk I will present a complete theory for the behaviour of large-scale dynamical heterogeneities in glasses. Following the work arXiv:1001.1746 I will show that we can write a (physically motivated) simple stochastic differential equation that is potentially able to explain the behaviour of large scale dynamical heterogeneities in glasses. It turns out that this behaviour is in the same universality class of the dynamics near the endpoint of a metastable phase in a disordered system, as far as reparametrization invariant quantities are concerned. Therefore Large scale dynamical heterogeneities in glasses have many points in contact with the Barkhausen noise. Numerical verifications of this theory have not yet done, but they are quite possible.

preprint2010arXiv

Elusive Glassy Phase in the Random Field Ising Model

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

preprint2010arXiv

Finite size scaling of the de Almeida-Thouless instability in random sparse networks

We study, in random sparse networks, finite size scaling of the spin glass susceptibility $χ_{\rm SG}$, which is a proper measure of the de Almeida-Thouless (AT) instability of spin glass systems. Using a phenomenological argument regarding the band edge behavior of the Hessian eigenvalue distribution, we discuss how $χ_{\rm SG}$ is evaluated in infinitely large random sparse networks, which are usually identified with Bethe trees, and how it should be corrected in finite systems. In the high temperature region, data of extensive numerical experiments are generally in good agreement with the theoretical values of $χ_{\rm SG}$ determined from the Bethe tree. In the absence of external fields, the data also show a scaling relation $χ_{\rm SG}=N^{1/3}F(N^{1/3}|T-T_c|/T_c)$, which has been conjectured in the literature, where $T_c$ is the critical temperature. In the presence of external fields, on the other hand, the numerical data are not consistent with this scaling relation. A numerical analysis of Hessian eigenvalues implies that strong finite size corrections of the lower band edge of the eigenvalue distribution, which seem relevant only in the presence of the fields, are a major source of inconsistency. This may be related to the known difficulty in using only numerical methods to detect the AT instability.

preprint2010arXiv

No spin glass phase in ferromagnetic random-field random-temperature scalar Ginzburg-Landau model

Krzakala, Ricci-Tersenghi and Zdeborova have shown recently that the random field Ising model with non-negative interactions and arbitrary external magnetic field on an arbitrary lattice does not have a static spin glass phase. In this paper we generalize the proof to a soft scalar spin version of the Ising model: the Ginzburg-Landau model with random magnetic field and random temperature-parameter. We do so by proving that the spin glass susceptibility cannot diverge unless the ferromagnetic susceptibility does.

preprint2010arXiv

Properties of the perturbative expansion around the mode-coupling dynamical transition in glasses

In this letter we show how to perform a systematic perturbative approach for the mode-coupling theory. The results coincide with those obtained via the replica approach. The upper critical dimension turns out to be always 8 and the correlations have a double pole in momentum space in perturbations theory. Non-perturbative effects are found to be very important. We suggest a possible framework to compute these effects.