Search ResultsShowing 1-19 of 19
-
arXiv:2309.09240 (Published 2023-09-17)
High-dimensional manifold of solutions in neural networks: insights from statistical physics
Comments: 22 pages, 9 figures, based on a set of lectures done at the "School of the Italian Society of Statistical Physics", IMT, LuccaKeywords: neural networks, high-dimensional manifold, statistical physics, binary weight models, linear mode connectivityTags: lecture notesIn these pedagogic notes I review the statistical mechanics approach to neural networks, focusing on the paradigmatic example of the perceptron architecture with binary an continuous weights, in the classification setting. I will review the Gardner's approach based on replica method and the derivation of the SAT/UNSAT transition in the storage setting. Then, I discuss some recent works that unveiled how the zero training error configurations are geometrically arranged, and how this arrangement changes as the size of the training set increases. I also illustrate how different regions of solution space can be explored analytically and how the landscape in the vicinity of a solution can be characterized. I give evidence how, in binary weight models, algorithmic hardness is a consequence of the disappearance of a clustered region of solutions that extends to very large distances. Finally, I demonstrate how the study of linear mode connectivity between solutions can give insights into the average shape of the solution manifold.
-
arXiv:2302.14112 (Published 2023-02-27)
Injectivity of ReLU networks: perspectives from statistical physics
Comments: 60 pagesWhen can the input of a ReLU neural network be inferred from its output? In other words, when is the network injective? We consider a single layer, $x \mapsto \mathrm{ReLU}(Wx)$, with a random Gaussian $m \times n$ matrix $W$, in a high-dimensional setting where $n, m \to \infty$. Recent work connects this problem to spherical integral geometry giving rise to a conjectured sharp injectivity threshold for $\alpha = \frac{m}{n}$ by studying the expected Euler characteristic of a certain random set. We adopt a different perspective and show that injectivity is equivalent to a property of the ground state of the spherical perceptron, an important spin glass model in statistical physics. By leveraging the (non-rigorous) replica symmetry-breaking theory, we derive analytical equations for the threshold whose solution is at odds with that from the Euler characteristic. Furthermore, we use Gordon's min--max theorem to prove that a replica-symmetric upper bound refutes the Euler characteristic prediction. Along the way we aim to give a tutorial-style introduction to key ideas from statistical physics in an effort to make the exposition accessible to a broad audience. Our analysis establishes a connection between spin glasses and integral geometry but leaves open the problem of explaining the discrepancies.
-
arXiv:2302.10841 (Published 2023-02-21)
The Power of an Adversary in Glauber Dynamics
Comments: 12 pagesCategories: math.PRGlauber dynamics are a natural model of dynamics of dependent systems. While originally introduced in statistical physics, they have found important applications in the study of social networks, computer vision and other domains. In this work, we introduce a model of corrupted Glauber dynamics whereby instead of updating according to the prescribed conditional probabilities, some of the vertices and their updates are controlled by an adversary. We study the effect of such corruptions on global features of the system. Among the questions we study are: How many nodes need to be controlled in order to change the average statistics of the system in polynomial time? And how many nodes are needed to obstruct approximate convergence of the dynamics? Our results can be viewed as studying the robustness of classical sampling methods and are thus related to robust inference. The proofs connect to classical theory of Glauber dynamics from statistical physics.
-
arXiv:2002.00342 (Published 2020-02-02)
Probability Theory in Statistical Physics, Percolation, and Other Random Topics: The Work of C. Newman
Comments: 38 pages (including many references), introduction to Festschrift in honor of C.M. NewmanJournal: Sojourns in Probability Theory and Statistical Physics - I, part of the Springer Proceedings in Mathematics & Statistics book series (PROMS, volume 298, 2019)Keywords: probability theory, random topics, statistical physics, first covering chucks work, continuum scaling limitsTags: journal articleIn the introduction to this volume, we discuss some of the highlights of the research career of Chuck Newman. This introduction is divided into two main sections, the first covering Chuck's work in statistical mechanics and the second his work in percolation theory, continuum scaling limits, and related topics.
-
arXiv:1901.06596 (Published 2019-01-19)
Constants of de Bruijn-Newman type in analytic number theory and statistical physics
Comments: A review, for Bull. A.M.S., of 100 years work on the Riemann Hypothesis (RH) and zeros of stat. physics partition functions, since P\'{o}lya's $\lambda$-perturbation of Riemann's xi-function with $\lambda$ real. The de Bruijn(1950)-Newman(1976) constant $\Lambda$ is the $\lambda$ below which some zeros are off the critical line; RH is equivalent to $\Lambda \leq 0$One formulation in 1859 of the Riemann Hypothesis (RH) was that the Fourier transform $H_f(z)$ of $f$ for $ z \in \mathbb{C}$ has only real zeros when $f(t)$ is a specific function $\Phi (t)$. P\'{o}lya's 1920s approach to RH extended $H_f$ to $H_{f,\lambda}$, the Fourier transform of $e^{\lambda t^2} f(t)$. We review developments of this approach to RH and related ones in statistical physics where $f(t)$ is replaced by a measure $d \rho (t)$. P\'{o}lya's work together with 1950 and 1976 results of de Bruijn and Newman, respectively, imply the existence of a finite constant $\Lambda_{DN} = \Lambda_{DN} (\Phi)$ in $(-\infty, 1/2]$ such that $H_{\Phi,\lambda}$ has only real zeros if and only if $\lambda \geq \Lambda_{DN}$; RH is then equivalent to $\Lambda_{DN} \leq 0$. Recent developments include the Rodgers and Tao proof of the 1976 conjecture that $\Lambda_{DN} \geq 0$ (that RH, if true, is only barely so) and the Polymath 15 project improving the $1/2$ upper bound to about $0.22$. We also present examples of $\rho$'s with differing $H_{\rho,\lambda}$ and $\Lambda_{DN} (\rho)$ behaviors; some of these are new and based on a recent weak convergence theorem of the authors.
-
arXiv:1810.03384 (Published 2018-10-08)
Sharp threshold phenomena in statistical physics
Comments: 19 pagesCategories: math.PRThis text describes the content of the Takagi lectures given by the author in Kyoto in 2017. The lectures present some aspects of the theory of sharp thresholds for boolean functions and its application to the study of phase transitions in statistical physics.
-
arXiv:1712.04911 (Published 2017-12-13)
Statistical physics on a product of trees
Comments: 11 pagesLet $G$ be the product of finitely many trees $T_1\times T_2 \cdots \times T_N$, each of which is regular with degree at least three. We consider Bernoulli bond percolation and the Ising model on this graph, giving a short proof that the model undergoes a second order phase transition with mean-field critical exponents in each case. The result concerning percolation recovers a result of Kozma (2013), while the result concerning the Ising model is new. We also present a new proof, using similar techniques, of a lemma of Schramm concerning the decay of the critical two-point function along a random walk, as well as some generalizations of this lemma.
-
arXiv:1608.02282 (Published 2016-08-07)
Computing the independence polynomial in Shearer's region for the LLL
Comments: 23 pagesThe independence polynomial has been widely studied in algebraic graph theory, in statistical physics, and in algorithms for counting and sampling problems. Seminal results of Weitz (2006) and Sly (2010) have shown the that the computational complexity of approximating the independence polynomial with positive activities is tightly linked to a uniqueness phase transition for a Gibbs measure. We study algorithms for approximating the independence polynomial with negative and complex arguments. The independence polynomial with complex arguments may not have a counting interpretation, but it does have strong connections to combinatorics and to statistical physics. The independence polynomial with negative arguments determines the maximal region of probabilities to which the Lov\'{a}sz Local Lemma (LLL) can be extended, and also gives a lower bound on the probability in the LLL's conclusion (Shearer 1985). In statistical physics, complex (and negative) zeros of the independence polynomial relate to existence of phase transitions (Penrose 1963). Whereas many algorithms for computing combinatorial polynomials are restricted to the univariate setting, we consider the multivariate independence polynomial, since there is a natural multivariate region of interest -- Shearer's region for the LLL. Our main result is: for any $n$-vertex graph of degree at most $d$, any $\alpha \in (0,1]$, and any complex vector $p$ such that $(1+\alpha) \cdot p$ lies in Shearer's region, there is a deterministic algorithm to approximate the independence polynomial at $p$ within $(1+\epsilon)$ multiplicative error and with runtime $(\frac{n}{\epsilon \alpha})^{O(\log(d)/\alpha)}$. Our results also extend to graphs of unbounded degree that have a bounded connective constant. We also give hardness results addressing the dependence of the runtime of the algorithm on the above parameters.
-
arXiv:1507.03721 (Published 2015-07-14)
Some measure-theoretic properties of U-statistics applied in statistical physics
This paper investigates the relationship between various measure-theoretic properties of U-statistics with fixed sample size $N$ and the same properties of their kernels. Specifically, the random variables are replaced with elements in some measure space $(\Lambda; dx)$, the resultant real-valued functions on $\Lambda^N$ being called generalized $N$-means. It is shown that a.e. convergence of sequences, measurability, essential boundedness and, under certain conditions, integrability with respect to probability measures of generalized $N$-means and their kernels are equivalent. These results are crucial for the solution of the inverse problem in classical statistical mechanics in the canonical formulation.
-
arXiv:1409.3777 (Published 2014-09-12)
Explicit formulae in probability and in statistical physics
Comments: 14 pages, 2 figures. Submitted to Special Issue Marc Yor, Seminaire de ProbabilitesWe consider two aspects of Marc Yor's work that have had an impact in statistical physics: firstly, his results on the windings of planar Brownian motion and their implications for the study of polymers; secondly, his theory of exponential functionals of Levy processes and its connections with disordered systems. Particular emphasis is placed on techniques leading to explicit calculations.
-
arXiv:1306.3980 (Published 2013-06-17)
Negative spherical perceptron
Comments: arXiv admin note: substantial text overlap with arXiv:1306.3809, arXiv:1306.3979In this paper we consider the classical spherical perceptron problem. This problem and its variants have been studied in a great detail in a broad literature ranging from statistical physics and neural networks to computer science and pure geometry. Among the most well known results are those created using the machinery of statistical physics in \cite{Gar88}. They typically relate to various features ranging from the storage capacity to typical overlap of the optimal configurations and the number of incorrectly stored patterns. In \cite{SchTir02,SchTir03,TalBook} many of the predictions of the statistical mechanics were rigorously shown to be correct. In our own work \cite{StojnicGardGen13} we then presented an alternative way that can be used to study the spherical perceptrons as well. Among other things we reaffirmed many of the results obtained in \cite{SchTir02,SchTir03,TalBook} and thereby confirmed many of the predictions established by the statistical mechanics. Those mostly relate to spherical perceptrons with positive thresholds (which we will typically refer to as the positive spherical perceptrons). In this paper we go a step further and attack the negative counterpart, i.e. the perceptron with negative thresholds. We present a mechanism that can be used to analyze many features of such a model. As a concrete example, we specialize our results for a particular feature, namely the storage capacity. The results we obtain for the storage capacity seem to indicate that the negative case could be more combinatorial in nature and as such a somewhat harder challenge than the positive counterpart.
-
arXiv:1002.0115 (Published 2010-01-31)
Left and right convergence of graphs with bounded degree
Comments: 26 pagesThe theory of convergent graph sequences has been worked out in two extreme cases, dense graphs and bounded degree graphs. One can define convergence in terms of counting homomorphisms from fixed graphs into members of the sequence (left-convergence), or counting homomorphisms into fixed graphs (right-convergence). Under appropriate conditions, these two ways of defining convergence was proved to be equivalent in the dense case by Borgs, Chayes, Lov\'asz, S\'os and Vesztergombi. In this paper a similar equivalence is established in the bounded degree case. In terms of statistical physics, the implication that left convergence implies right convergence means that for a left-convergent sequence, partition functions of a large class of statistical physics models converge. The proof relies on techniques from statistical physics, like cluster expansion and Dobrushin Uniqueness.
-
Painlevé Functions in Statistical Physics
Comments: Revised version updates some referencesJournal: Publ. RIMS Kyoto Univ., 47 (2011), 361-374DOI: 10.2977/PRIMS/38Keywords: statistical physics, one-dimensional asymmetric simple exclusion process, limit laws, integer lattice, brief surveyTags: journal articleWe review recent progress in limit laws for the one-dimensional asymmetric simple exclusion process (ASEP) on the integer lattice. The limit laws are expressed in terms of a certain Painlev\'e II function. Furthermore, we take this opportunity to give a brief survey of the appearance of Painlev\'e functions in statistical physics.
-
Reconstruction of Random Colourings
Comments: Added references, updated notationCategories: math.PRKeywords: random colourings, reconstruction problem, information theory, ary tree, statistical physicsTags: journal articleReconstruction problems have been studied in a number of contexts including biology, information theory and and statistical physics. We consider the reconstruction problem for random $k$-colourings on the $\Delta$-ary tree for large $k$. Bhatnagar et. al. showed non-reconstruction when $\Delta \leq \frac12 k\log k - o(k\log k)$ and reconstruction when $\Delta \geq k\log k + o(k\log k)$. We tighten this result and show non-reconstruction when $\Delta \leq k[\log k + \log \log k + 1 - \ln 2 -o(1)]$ and reconstruction when $\Delta \geq k[\log k + \log \log k + 1+o(1)]$.
-
arXiv:math/0510471 (Published 2005-10-21)
Counting without sampling. New algorithms for enumeration problems using statistical physics
We propose a new type of approximate counting algorithms for the problems of enumerating the number of independent sets and proper colorings in low degree graphs with large girth. Our algorithms are not based on a commonly used Markov chain technique, but rather are inspired by developments in statistical physics in connection with correlation decay properties of Gibbs measures and its implications to uniqueness of Gibbs measures on infinite trees, reconstruction problems and local weak convergence methods. On a negative side, our algorithms provide $\epsilon$-approximations only to the logarithms of the size of a feasible set (also known as free energy in statistical physics). But on the positive side, our approach provides deterministic as opposed to probabilistic guarantee on approximations. Moreover, for some regular graphs we obtain explicit values for the counting problem. For example, we show that every 4-regular $n$-node graph with large girth has approximately $(1.494...)^n$ independent sets, and in every $r$-regular graph with $n$ nodes and large girth the number of $q\geq r+1$-proper colorings is approximately $[q(1-{1\over q})^{r\over 2}]^n$, for large $n$. In statistical physics terminology, we compute explicitly the limit of the log-partition function. We extend our results to random regular graphs. Our explicit results would be hard to derive via the Markov chain method.
-
arXiv:math/0406446 (Published 2004-06-23)
Survey: Information flow on trees
Consider a tree network T, where each edge acts as an independent copy of a given channel M, and information is propagated from the root. For which T and M does the configuration obtained at level n of T typically contain significant information on the root variable? This model appeared independently in biology, information theory, and statistical physics. Its analysis uses techniques from the theory of finite markov chains, statistics, statistical physics, information theory, cryptography and noisy computation. In this paper, we survey developments and challenges related to this problem.
-
arXiv:math/0110127 (Published 2001-10-12)
2D models of statistical physics with continuous symmetry: the case of singular interactions
Comments: 29 pagesJournal: Comm. Math. Phys., Vol. 226, Nr. 2 (2002) , p. 433--454Keywords: continuous symmetry, singular interactions, 2d models, statistical physics, 2d lattice systemsTags: journal articleWe show the absence of continuous symmetry breaking in 2D lattice systems without any smoothness assumptions on the interaction. We treat certain cases of interactions with integrable singularities. We also present cases of singular interactions with continuous symmetry, when the symmetry is broken in the thermodynamic limit.
-
Phase Transitions on Nonamenable Graphs
Journal: J.Math.Phys. 41 (2000) 1099-1126DOI: 10.1063/1.533179Subjects: 82B26Tags: journal articleWe survey known results about phase transitions in various models of statistical physics when the underlying space is a nonamenable graph. Most attention is devoted to transitive graphs and trees.
-
arXiv:cond-mat/9812205 (Published 1998-12-11)
Statistics of knots and entangled random walks
Comments: Extended version of lectures presented at Les Houches 1998 summer school "Topological Aspects of Low Dimensional Systems", July 7 - 31, 1998; revtex, 79 pages, 16 eps-figuresKeywords: entangled random walks, statistics, polymer chains, statistical physics, 2d disordered potts modelTags: lecture notesThe lectures review the state of affairs in modern branch of mathematical physics called probabilistic topology. In particular we consider the following problems: (i) We estimate the probability of a trivial knot formation on the lattice using the Kauffman algebraic invariants and show the connection of this problem with the thermodynamic properties of 2D disordered Potts model; (ii) We investigate the limit behavior of random walks in multi-connected spaces and on non-commutative groups related to the knot theory. We discuss the application of the above mentioned problems in statistical physics of polymer chains. On the basis of non-commutative probability theory we derive some new results in statistical physics of entangled polymer chains which unite rigorous mathematical facts with more intuitive physical arguments.