Capacity lower bound for the Ising perceptron
Interacting random processes; statistical mechanics type models; percolation theory (60K35) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)
In this paper the authors derive a lower bound on the capacity of the Ising perceptron with Gaussian disorder. This is equivalent to considering an \(N\)-dimensional discrete cube intersected by \(M\) random half-spaces. The question is when this intersection is non-empty, and the conjecture by \textit{W. Krauth} and \textit{M. Mézard} [``Storage capacity of memory networks with binary couplings, J. Physique 50, No. 20, 3057--3066 (1989)], based on the physics-based nonrigorous replica method, is that when \(N\) goes to infinity and if and only if \(M < N \times \alpha^*\), this is the case, for a given \(\alpha^*\) which is about 0.83. The authors prove a weak version, which provides a serious step forward towards the conjecture, in which the Krauth-Mezard constant is a lower bound with positive probability. Since then, the result has been improved to a probability-one statement by \textit{S. Nakajima} and \textit{N. Sun} [in: Proceedings of the 34th annual ACM-SIAM symposium on discrete algorithms, SODA 2023, Florence, Italy, January 22--25, 2023. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 638--674 (2023; Zbl 07847988)] and under some technical conditions the full conjecture has been proved by \textit{B. Huang} [``Capacity threshold for the Ising perceptron, Preprint, \url{arXiv:2404.18902}], who provided the upper bound. The authors' proof employs a sophisticated conditional second-moment argument plus ideas inspired by the TAP approach to spin glasses.
- Algorithmic pure states for the negative spherical perceptron
- Algorithms and barriers in the symmetric binary perceptron model
- An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
- Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster
- Bounds for diluted mean-fields spin glass models
- Broken replica symmetry bounds in the mean field spin glass model
- Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
- Covering cubes by random half cubes, with applications to binary neural networks
- Frozen 1-RSB structure of the symmetric Ising perceptron
- Graphical models, exponential families, and variational inference
- Harnessing the Bethe free energy
- High dimensional robust M-estimation: asymptotic variance via approximate message passing
- Information, Physics, and Computation
- Intersecting random half cubes
- Intersecting random half-spaces: Toward the Gardner-Derrida formula.
- Local entropy as a measure for sampling solutions in constraint satisfaction problems
- Mean field models for spin glasses. Volume I: Basic examples.
- Mills' ratio: Monotonicity patterns and functional inequalities
- On the high temperature phase of the Sherrington-Kirkpatrick model.
- On the TAP free energy in the mixed p-spin models
- Proof of the contiguity conjecture and lognormal limit for the symmetric perceptron
- Right-convergence of sparse random graphs
- Rigorous solution of the Gardner problem
- Sharp threshold for the Ising perceptron model
- Sharp threshold sequence and universality for Ising perceptron models
- Some Inequalities on Mill's Ratio and Related Functions
- Spin glasses and Stein's method
- Storage capacity in symmetric binary perceptrons
- The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
- The LASSO Risk for Gaussian Matrices
- The Parisi formula
- The Sherrington-Kirkpatrick model
- The simplest model of jamming
- The space of interactions in neural network models
- The thermodynamic limit in mean field spin glass models
This page was built for publication: Capacity lower bound for the Ising perceptron
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6884235)
