Frozen 1-RSB structure of the symmetric Ising perceptron
Frozen 1-RSB structure of the symmetric Ising perceptron
复制标题
对称伊辛感知器的冻结 1-RSB 结构
DOI：
10.1145/3406325.3451119
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Xu, Changji
中科院分区：
文献类型：
--
作者：
Perkins, Will;Xu, Changji
在关于实值函数临界点的假设下，我们证明了对称伊辛感知器具有Krauth和Mezard在物理文献中猜想的“冻结的1-RSB”结构，即该模型的典型解存在于熵密度为零的团簇中。此外，我们用Huang，Wong和Kabashima猜想的非常强的形式证明了这一点：模型的一个典型解是高概率孤立的，并且到所有其他解的Hamming距离在维度上是线性的。Baldassi、Ingrosso、Lucibello、Saglietti和ZecChina最近对学习算法的性能进行了耐人寻味的解释，冻结的1-RSB情景是其中的一部分。我们通过将对称伊辛感知器模型与种植模型进行比较并证明了两种模型之间的比较结果，证明了这一结构性结果。我们进行这种比较的主要技术工具是对模型中解的个数的对数的集中度进行归纳论证。
We prove, under an assumption on the critical points of a real-valued function, that the symmetric Ising perceptron exhibits the `frozen 1-RSB' structure conjectured by Krauth and Mezard in the physics literature; that is, typical solutions of the model lie in clusters of vanishing entropy density. Moreover, we prove this in a very strong form conjectured by Huang, Wong, and Kabashima: a typical solution of the model is isolated with high probability and the Hamming distance to all other solutions is linear in the dimension. The frozen 1-RSB scenario is part of a recent and intriguing explanation of the performance of learning algorithms by Baldassi, Ingrosso, Lucibello, Saglietti, and Zecchina. We prove this structural result by comparing the symmetric Ising perceptron model to a planted model and proving a comparison result between the two models. Our main technical tool towards this comparison is an inductive argument for the concentration of the logarithm of number of solutions in the model.
登录
查看更多内容
DOI：
10.1145/3313276.3316383
发表时间：
2018
期刊：
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Jian Ding;Nike Sun
通讯作者：
Nike Sun
DOI：
10.1145/3055399.3055420
发表时间：
2016-11
期刊：
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
A. Coja-Oghlan;Florent Krzakala;Will Perkins;L. Zdeborová
通讯作者：
A. Coja-Oghlan;Florent Krzakala;Will Perkins;L. Zdeborová
DOI：
10.1137/1.9781611973099.22
发表时间：
2011-07
期刊：
--
影响因子：
--
作者：
A. Coja-Oghlan;L. Zdeborová
通讯作者：
A. Coja-Oghlan;L. Zdeborová
影响因子：
0.8
作者：
A. Montanari;R. Restrepo;P. Tetali
通讯作者：
P. Tetali
相交的随机半立方体
DOI：
--
发表时间：
1999
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
M. Talagrand
通讯作者：
M. Talagrand