TY - GEN

T1 - Binary perceptron

T2 - 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022

AU - Abbe, Emmanuel Auguste

AU - Li, Shuangping

AU - Sly, Allan

N1 - Funding Information:
A.S. was partially supported in part by NSF grant DMS-1855527, a Simons Investigator grant and a MacArthur Fellowship. E.A. was partially supported by NSF grant CCF-1552131.
Publisher Copyright:
© 2022 Owner/Author.

PY - 2022/9/6

Y1 - 2022/9/6

N2 - It was recently shown that almost all solutions in the symmetric binary perceptron are isolated, even at low constraint densities, suggesting that finding typical solutions is hard. In contrast, some algorithms have been shown empirically to succeed in finding solutions at low density. This phenomenon has been justified numerically by the existence of subdominant and dense connected regions of solutions, which are accessible by simple learning algorithms. In this paper, we establish formally such a phenomenon for both the symmetric and asymmetric binary perceptrons. We show that at low constraint density (equivalently for overparametrized perceptrons), there exists indeed a subdominant connected cluster of solutions with almost maximal diameter, and that an efficient multiscale majority algorithm can find solutions in such a cluster with high probability, settling in particular an open problem posed by Perkins-Xu in STOC'21. In addition, even close to the critical threshold, we show that there exist clusters of linear diameter for the symmetric perceptron, as well as for the asymmetric perceptron under additional assumptions.

AB - It was recently shown that almost all solutions in the symmetric binary perceptron are isolated, even at low constraint densities, suggesting that finding typical solutions is hard. In contrast, some algorithms have been shown empirically to succeed in finding solutions at low density. This phenomenon has been justified numerically by the existence of subdominant and dense connected regions of solutions, which are accessible by simple learning algorithms. In this paper, we establish formally such a phenomenon for both the symmetric and asymmetric binary perceptrons. We show that at low constraint density (equivalently for overparametrized perceptrons), there exists indeed a subdominant connected cluster of solutions with almost maximal diameter, and that an efficient multiscale majority algorithm can find solutions in such a cluster with high probability, settling in particular an open problem posed by Perkins-Xu in STOC'21. In addition, even close to the critical threshold, we show that there exist clusters of linear diameter for the symmetric perceptron, as well as for the asymmetric perceptron under additional assumptions.

KW - binary perceptron

KW - efficient algorithm

KW - neural networks

KW - perceptron model

KW - solution space

UR - http://www.scopus.com/inward/record.url?scp=85132751829&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85132751829&partnerID=8YFLogxK

U2 - 10.1145/3519935.3519975

DO - 10.1145/3519935.3519975

M3 - Conference contribution

AN - SCOPUS:85132751829

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 860

EP - 873

BT - STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Leonardi, Stefano

A2 - Gupta, Anupam

PB - Association for Computing Machinery

Y2 - 20 June 2022 through 24 June 2022

ER -