Gardner formula for Ising perceptron models at small densities
We consider the Ising perceptron model with N spins and M = N*alpha patterns, with a general activation function U that is bounded above. For U bounded away from zero, or U a one-sided threshold function, it was shown by Talagrand (2000, 2011) that for small densities alpha, the free energy of the model converges in the large-N limit to the replica symmetric formula conjectured in the physics literature (Krauth–Mezard 1989, see also Gardner–Derrida 1988). We give a new proof of this result, which covers the more general class of all functions U that are bounded above and satisfy a certain variance bound. The proof uses the (first and second) moment method conditional on the approximate message passing iterates of the model. In order to deduce our main theorem, we also prove a new concentration result for the perceptron model in the case where U is not bounded away from zero.
Authors:
; ; ;
Award ID(s):
Publication Date:
NSF-PAR ID:
10344272
Journal Name:
Conference on Learning Theory
1. Extremal combinatorics often deals with problems of maximizing a specific quantity related to substructures in large discrete structures. The first question of this kind that comes to one's mind is perhaps determining the maximum possible number of induced subgraphs isomorphic to a fixed graph $H$ in an $n$-vertex graph. The asymptotic behavior of this number is captured by the limit of the ratio of the maximum number of induced subgraphs isomorphic to $H$ and the number of all subgraphs with the same number vertices as $H$; this quantity is known as the _inducibility_ of $H$. More generally, one can define the inducibility of a family of graphs in the analogous way.Among all graphs with $k$ vertices, the only two graphs with inducibility equal to one are the empty graph and the complete graph. However, how large can the inducibility of other graphs with $k$ vertices be? Fix $k$, consider a graph with $n$ vertices join each pair of vertices independently by an edge with probability $\binom{k}{2}^{-1}$. The expected number of $k$-vertex induced subgraphs with exactly one edge is $e^{-1}+o(1)$. So, the inducibility of large graphs with a single edge is at least $e^{-1}+o(1)$. This article establishes that this bound ismore »
3. We establish a relation between the "large r" asymptotics of the Turaev-Viro invariants $TV_r$and the Gromov norm of 3-manifolds. We show that for any orientable, compact 3-manifold $M$, with (possibly empty) toroidal boundary, $log|TVr(M)|$ is bounded above by a function linear in $r$ and whose slope is a positive universal constant times the Gromov norm of $M$. The proof combines TQFT techniques, geometric decomposition theory of 3-manifolds and analytical estimates of $6j$-symbols. We obtain topological criteria that can be used to check whether the growth is actually exponential; that is one has $log|TVr(M)|\geq B r$, for some $B>0$. We use these criteria to construct infinite families of hyperbolic 3-manifolds whose $SO(3)$- Turaev-Viro invariants grow exponentially. These constructions are essential for the results of article [3] where we make progress on a conjecture of Andersen, Masbaum and Ueno about the geometric properties of surface mapping class groups detected by the quantum representations. We also study the behavior of the Turaev-Viro invariants under cutting and gluing of 3-manifolds along tori. In particular, we show that, like the Gromov norm, the values of the invariants do not increase under Dehn filling and we give applications of this result on the question ofmore »