Capacity lower bound for the Ising perceptron
© 2019 Association for Computing Machinery. We consider the Ising perceptron with gaussian disorder, which is equivalent to the discrete cube t´1, `1uN intersected by M random half-spaces. The perceptron’s capacity is the largest integer MN for which the intersection is nonempty. It is conjectured b...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137021 |
| _version_ | 1811070512757997568 |
|---|---|
| author | Ding, Jian Sun, Nike |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Ding, Jian Sun, Nike |
| author_sort | Ding, Jian |
| collection | MIT |
| description | © 2019 Association for Computing Machinery. We consider the Ising perceptron with gaussian disorder, which is equivalent to the discrete cube t´1, `1uN intersected by M random half-spaces. The perceptron’s capacity is the largest integer MN for which the intersection is nonempty. It is conjectured by Krauth and Mézard (1989) that the (random) ratio MN (N converges in probability to an explicit constant α 0.83. Kim and Roche (1998) proved the existence of a positive constant γ such that γ ď MN (N ď 1 ´ γ with high probability; see also Talagrand (1999). In this paper we show that the Krauth–Mézard conjecture αis a lower bound with positive probability, under the condition that an explicit univariate function Spλq is maximized at λ “0. Our proof is an application of the second moment method to a certain slice of perceptron configurations, as selected by the so-called TAP (Thouless, Anderson, and Palmer, 1977) or AMP (approximate message passing) iteration, whose scaling limit has been characterized by Bayati and Montanari (2011) and Bolthausen (2012). For verifying the condition on Spλq we outline one approach, which is implemented in the current version using (nonrigorous) numerical integration packages. In a future version of this paper we intend to complete the verification by implementing a rigorous numerical method. |
| first_indexed | 2024-09-23T08:36:55Z |
| format | Article |
| id | mit-1721.1/137021 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:36:55Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1370212023-12-20T16:52:10Z Capacity lower bound for the Ising perceptron Ding, Jian Sun, Nike Massachusetts Institute of Technology. Department of Mathematics © 2019 Association for Computing Machinery. We consider the Ising perceptron with gaussian disorder, which is equivalent to the discrete cube t´1, `1uN intersected by M random half-spaces. The perceptron’s capacity is the largest integer MN for which the intersection is nonempty. It is conjectured by Krauth and Mézard (1989) that the (random) ratio MN (N converges in probability to an explicit constant α 0.83. Kim and Roche (1998) proved the existence of a positive constant γ such that γ ď MN (N ď 1 ´ γ with high probability; see also Talagrand (1999). In this paper we show that the Krauth–Mézard conjecture αis a lower bound with positive probability, under the condition that an explicit univariate function Spλq is maximized at λ “0. Our proof is an application of the second moment method to a certain slice of perceptron configurations, as selected by the so-called TAP (Thouless, Anderson, and Palmer, 1977) or AMP (approximate message passing) iteration, whose scaling limit has been characterized by Bayati and Montanari (2011) and Bolthausen (2012). For verifying the condition on Spλq we outline one approach, which is implemented in the current version using (nonrigorous) numerical integration packages. In a future version of this paper we intend to complete the verification by implementing a rigorous numerical method. 2021-11-01T18:09:22Z 2021-11-01T18:09:22Z 2019 2021-05-26T16:41:55Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137021 Ding, Jian and Sun, Nike. 2019. "Capacity lower bound for the Ising perceptron." Proceedings of the Annual ACM Symposium on Theory of Computing. en 10.1145/3313276.3316383 Proceedings of the Annual ACM Symposium on Theory of Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Ding, Jian Sun, Nike Capacity lower bound for the Ising perceptron |
| title | Capacity lower bound for the Ising perceptron |
| title_full | Capacity lower bound for the Ising perceptron |
| title_fullStr | Capacity lower bound for the Ising perceptron |
| title_full_unstemmed | Capacity lower bound for the Ising perceptron |
| title_short | Capacity lower bound for the Ising perceptron |
| title_sort | capacity lower bound for the ising perceptron |
| url | https://hdl.handle.net/1721.1/137021 |
| work_keys_str_mv | AT dingjian capacitylowerboundfortheisingperceptron AT sunnike capacitylowerboundfortheisingperceptron |