Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron

• URL: http://arxiv.org/abs/2102.13069v1
• Date: Thu, 25 Feb 2021 18:39:08 GMT
• Title: Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron
• Authors: Emmanuel Abbe, Shuangping Li, Allan Sly
• Abstract summary: We consider the symmetric binary perceptron model, a simple model of neural networks. We establish several conjectures for this model. Our proof technique relies on a dense counter-part of the small graph conditioning method.
• Score: 21.356438315715888
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the symmetric binary perceptron model, a simple model of neural networks that has gathered significant attention in the statistical physics, information theory and probability theory communities, with recent connections made to the performance of learning algorithms in Baldassi et al. '15. We establish that the partition function of this model, normalized by its expected value, converges to a lognormal distribution. As a consequence, this allows us to establish several conjectures for this model: (i) it proves the contiguity conjecture of Aubin et al. '19 between the planted and unplanted models in the satisfiable regime; (ii) it establishes the sharp threshold conjecture; (iii) it proves the frozen 1-RSB conjecture in the symmetric case, conjectured first by Krauth-M\'ezard '89 in the asymmetric case. In a recent concurrent work of Perkins-Xu [PX21], the last two conjectures were also established by proving that the partition function concentrates on an exponential scale. This left open the contiguity conjecture and the lognormal limit characterization, which are established here. In particular, our proof technique relies on a dense counter-part of the small graph conditioning method, which was developed for sparse models in the celebrated work of Robinson and Wormald.

Related papers

• von Mises Quasi-Processes for Bayesian Circular Regression [57.88921637944379]
  We explore a family of expressive and interpretable distributions over circle-valued random functions. The resulting probability model has connections with continuous spin models in statistical physics. For posterior inference, we introduce a new Stratonovich-like augmentation that lends itself to fast Markov Chain Monte Carlo sampling.
  arXiv  Detail & Related papers  (2024-06-19T01:57:21Z)
• Intrinsic Bayesian Cramér-Rao Bound with an Application to Covariance Matrix Estimation [49.67011673289242]
  This paper presents a new performance bound for estimation problems where the parameter to estimate lies in a smooth manifold. It induces a geometry for the parameter manifold, as well as an intrinsic notion of the estimation error measure.
  arXiv  Detail & Related papers  (2023-11-08T15:17:13Z)
• Entanglement asymmetry in the ordered phase of many-body systems: the Ising Field Theory [0.0]
  Global symmetries of quantum many-body systems can be spontaneously broken. In this study, we examine the entanglement asymmetry of a specific region. We also establish a field theoretic framework in the replica theory using twist operators.
  arXiv  Detail & Related papers  (2023-07-22T17:07:56Z)
• Geometric Neural Diffusion Processes [55.891428654434634]
  We extend the framework of diffusion models to incorporate a series of geometric priors in infinite-dimension modelling. We show that with these conditions, the generative functional model admits the same symmetry.
  arXiv  Detail & Related papers  (2023-07-11T16:51:38Z)
• Work statistics, quantum signatures and enhanced work extraction in quadratic fermionic models [62.997667081978825]
  In quadratic fermionic models we determine a quantum correction to the work statistics after a sudden and a time-dependent driving. Such a correction lies in the non-commutativity of the initial quantum state and the time-dependent Hamiltonian. Thanks to the latter, one can assess the onset of non-classical signatures in the KDQ distribution of work.
  arXiv  Detail & Related papers  (2023-02-27T13:42:40Z)
• Numerically Probing the Universal Operator Growth Hypothesis [0.0]
  We numerically test this hypothesis for a variety of exemplary systems. The onset of the hypothesized universal behavior could not be observed in the attainable numerical data for the Heisenberg model.
  arXiv  Detail & Related papers  (2022-03-01T15:15:47Z)
• Conformal field theory from lattice fermions [77.34726150561087]
  We provide a rigorous lattice approximation of conformal field theories given in terms of lattice fermions in 1+1-dimensions. We show how these results lead to explicit error estimates pertaining to the quantum simulation of conformal field theories.
  arXiv  Detail & Related papers  (2021-07-29T08:54:07Z)
• Counterexamples to the Low-Degree Conjecture [80.3668228845075]
  A conjecture of Hopkins posits that for certain high-dimensional hypothesis testing problems, no-time algorithm can outperform so-called "simple statistics" This conjecture formalizes the beliefs surrounding a line of recent work that seeks to understand statistical-versus-computational tradeoffs.
  arXiv  Detail & Related papers  (2020-04-17T21:08:11Z)
• Cram\'er-Rao Lower Bounds Arising from Generalized Csisz\'ar Divergences [17.746238062801293]
  We study the geometry of probability distributions with respect to a generalized family of Csisz'ar $f$-divergences. We show that these formulations lead us to find unbiased and efficient estimators for the escort model.
  arXiv  Detail & Related papers  (2020-01-14T13:41:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.