1,721,024 research outputs found
The decimation scheme for symmetric matrix factorization
Full text linkMatrix factorization is an inference problem that has acquired importance due
to its vast range of applications that go from dictionary learning to
recommendation systems and machine learning with deep networks. The study of
its fundamental statistical limits represents a true challenge, and despite a
decade-long history of efforts in the community, there is still no closed
formula able to describe its optimal performances in the case where the rank of
the matrix scales linearly with its size. In the present paper, we study this
extensive rank problem, extending the alternative 'decimation' procedure that
we recently introduced, and carry out a thorough study of its performance.
Decimation aims at recovering one column/line of the factors at a time, by
mapping the problem into a sequence of neural network models of associative
memory at a tunable temperature. Though being sub-optimal, decimation has the
advantage of being theoretically analyzable. We extend its scope and analysis
to two families of matrices. For a large class of compactly supported priors,
we show that the replica symmetric free entropy of the neural network models
takes a universal form in the low temperature limit. For sparse Ising prior, we
show that the storage capacity of the neural network models diverges as
sparsity in the patterns increases, and we introduce a simple algorithm based
on a ground state search that implements decimation and performs matrix
factorization, with no need of an informative initialization
Distribution of diameters for Erdős-Rényi random graphs
Full text linkWe study the distribution of diameters d of Erdos-Renyi random graphs with average connectivity c. The diameter d is the maximum among all the shortest distances between pairs of nodes in a graph and an important quantity for all dynamic processes taking place on graphs. Here we study the distribution P(d) numerically for various values of c, in the nonpercolating and percolating regimes. Using large-deviation techniques, we are able to reach small probabilities like 10(-100) which allow us to obtain the distribution over basically the full range of the support, for graphs up to N = 1000 nodes. For values c 1 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
Sparse representations, inference and learning
Full text linkIn recent years statistical physics has proven to be a valuable tool to probe into large dimensional inference problems such as the ones occurring in machine learning. Statistical physics provides analytical tools to study fundamental limitations in their solutions and proposes algorithms to solve individual instances. In these notes, based on the lectures by Marc Mezard in 2022 at the summer school in Les Houches, we will present a general framework that can be used in a large variety of problems with weak long-range interactions, including the compressed sensing problem, or the problem of learning in a perceptron. We shall see how these problems can be studied at the replica symmetric level, using developments of the cavity methods, both as a theoretical tool and as analgorithm
Eigenvector dreaming
Full text linkAmong the performance-enhancing procedures for Hopfield-type networks that
implement associative memory, Hebbian Unlearning (or dreaming) strikes for its
simplicity and its clear biological interpretation. Yet, it does not easily
lend itself to a clear analytical understanding. Here we show how Hebbian
Unlearning can be effectively described in terms of a simple evolution of the
spectrum and the eigenvectors of the coupling matrix. We use these ideas to
design new dreaming algorithms that are effective from a computational point of
view, and are analytically far more transparent than the original scheme
On a universal mechanism for long-range volatility correlations
No full textWe 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
Proliferation assisted barrier crossing and population dynamics
No full textWe investigate a model of population dynamics in a random force field, where two competing mechanisms of barrier slowing down and proliferation induced super-diffusion are present simultaneously. A one-loop rg analysis close to the critical dimension dc=2 shows that the random force fixed point is unstable in the presence of a small proliferation term, and flows towards an uncontrolled strong coupling regime. Numerical results in d=1 suggest that a new intermediate diffusion behavior appears, consistent with the rg analysis. We introduce the idea of proliferation assisted barrier crossing and give a Flory like argument to understand qualitatively this non trivial diffusive behavior
Compressed sensing under matrix uncertainty: Optimum thresholds and robust approximate message passing
No full text
Effect of coupling asymmetry on mean-field solutions of the direct and inverse Sherrington–Kirkpatrick model
No full textWe study how the degree of symmetry in the couplings influences the performance of three mean field methods used for solving the direct and inverse problems for generalized Sherrington-Kirkpatrick models. In this context, the direct problem is predicting the potentially time-varying magnetizations. The three theories include the first and second order Plefka expansions, referred to as naive mean field (nMF) and TAP, respectively, and a mean field theory which is exact for fully asymmetric couplings. We call the last of these simply MF theory. We show that for the direct problem, nMF performs worse than the other two approximations, TAP outperforms MF when the coupling matrix is nearly symmetric, while MF works better when it is strongly asymmetric. For the inverse problem, MF performs better than both TAP and nMF, although an ad hoc adjustment of TAP can make it comparable to MF. For high temperatures the performance of TAP and MF approach each other
- …
