Algorithmic Pure States for the Negative Spherical Perceptron
Algorithmic Pure States for the Negative Spherical Perceptron
复制标题
负球形感知器的算法纯状态
DOI：
10.1007/s10955-022-02976-6
复制
发表时间：
2020
影响因子：
1.6
通讯作者：
Mark Sellke
中科院分区：
文献类型：
--
作者：
Ahmed El Alaoui;Mark Sellke
We consider the spherical perceptron with Gaussian disorder. This is the set S of points σ∈RN\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{\sigma }\in \mathbb {R}^N$$\end{document} on the sphere of radius N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sqrt{N}$$\end{document} satisfying ⟨ga,σ⟩≥κN\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle \varvec{g}_a , \varvec{\sigma }\rangle \ge \kappa \sqrt{N}$$\end{document} for all 1≤a≤M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \le a \le M$$\end{document}, where (ga)a=1M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(\varvec{g}_a)_{a=1}^M$$\end{document} are independent standard gaussian vectors and κ∈R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\kappa \in \mathbb {R}$$\end{document} is fixed. Various characteristics of S such as its measure and the largest M for which it is non-empty, were computed heuristically in statistical physics in the asymptotic regime N→∞\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N \rightarrow \infty $$\end{document}, M/N→α\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M/N \rightarrow \alpha $$\end{document}. The case κ<0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\kappa <0$$\end{document} is of special interest as S is conjectured to exhibit a hierarchical tree-like geometry known as full replica-symmetry breaking (FRSB\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {FRSB}$$\end{document}) close to the satisfiability threshold αSAT(κ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha _{\text {SAT}}(\kappa )$$\end{document}, whose characteristics are captured by a Parisi variational principle akin to the one appearing in the Sherrington–Kirkpatrick model. In this paper we design an efficient algorithm which, given oracle access to the solution of the Parisi variational principle, exploits this conjectured FRSB\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {FRSB}$$\end{document} structure for κ<0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\kappa <0$$\end{document} and outputs a vector σ^\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\varvec{\sigma }}$$\end{document} satisfying ⟨ga,σ^⟩≥κN\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle \varvec{g}_a , \hat{\varvec{\sigma }}\rangle \ge \kappa \sqrt{N}$$\end{document} for all 1≤a≤M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1\le a \le M$$\end{document} and lying on a sphere of non-trivial radius q¯N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sqrt{\bar{q}N}$$\end{document}, where q¯∈(0,1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{q}\in (0,1)$$\end{document} is the right-end of the support of the associated Parisi measure. We expect σ^\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\varvec{\sigma }}$$\end{document} to be approximately the barycenter of a pure state of the spherical perceptron. Moreover we expect that q¯→1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{q}\rightarrow 1$$\end{document} as α→αSAT(κ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha \rightarrow \alpha _{\text {SAT}}(\kappa )$$\end{document}, so that 〈ga,σ^〉/|σ^|≥κ-o(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\big \langle \varvec{g}_a, \hat{\varvec{\sigma }} \big \rangle / \vert \hat{\varvec{\sigma }} \vert \ge \kappa -o(1)$$\end{document} near criticality.
We consider the spherical perceptron with Gaussian disorder. This is the set S of points σ∈RN\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varvec{\sigma }\in \mathbb {R}^N$$\end{document} on the sphere of radius N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sqrt{N}$$\end{document} satisfying ⟨ga,σ⟩≥κN\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle \varvec{g}_a , \varvec{\sigma }\rangle \ge \kappa \sqrt{N}$$\end{document} for all 1≤a≤M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \le a \le M$$\end{document}, where (ga)a=1M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(\varvec{g}_a)_{a=1}^M$$\end{document} are independent standard gaussian vectors and κ∈R\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\kappa \in \mathbb {R}$$\end{document} is fixed. Various characteristics of S such as its measure and the largest M for which it is non-empty, were computed heuristically in statistical physics in the asymptotic regime N→∞\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N \rightarrow \infty $$\end{document}, M/N→α\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M/N \rightarrow \alpha $$\end{document}. The case κ<0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\kappa <0$$\end{document} is of special interest as S is conjectured to exhibit a hierarchical tree-like geometry known as full replica-symmetry breaking (FRSB\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {FRSB}$$\end{document}) close to the satisfiability threshold αSAT(κ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha _{\text {SAT}}(\kappa )$$\end{document}, whose characteristics are captured by a Parisi variational principle akin to the one appearing in the Sherrington–Kirkpatrick model. In this paper we design an efficient algorithm which, given oracle access to the solution of the Parisi variational principle, exploits this conjectured FRSB\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\text {FRSB}$$\end{document} structure for κ<0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\kappa <0$$\end{document} and outputs a vector σ^\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\varvec{\sigma }}$$\end{document} satisfying ⟨ga,σ^⟩≥κN\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\langle \varvec{g}_a , \hat{\varvec{\sigma }}\rangle \ge \kappa \sqrt{N}$$\end{document} for all 1≤a≤M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1\le a \le M$$\end{document} and lying on a sphere of non-trivial radius q¯N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sqrt{\bar{q}N}$$\end{document}, where q¯∈(0,1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{q}\in (0,1)$$\end{document} is the right-end of the support of the associated Parisi measure. We expect σ^\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\varvec{\sigma }}$$\end{document} to be approximately the barycenter of a pure state of the spherical perceptron. Moreover we expect that q¯→1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{q}\rightarrow 1$$\end{document} as α→αSAT(κ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha \rightarrow \alpha _{\text {SAT}}(\kappa )$$\end{document}, so that 〈ga,σ^〉/|σ^|≥κ-o(1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\big \langle \varvec{g}_a, \hat{\varvec{\sigma }} \big \rangle / \vert \hat{\varvec{\sigma }} \vert \ge \kappa -o(1)$$\end{document} near criticality.
登录
查看更多内容
小密度下伊辛感知器模型的加德纳公式
DOI：
--
发表时间：
2022
期刊：
Conference on Learning Theory
影响因子：
--
作者：
Bolthausen, E.;Nakajima, S;Sun, N
通讯作者：
Sun, N
在高维中平衡高斯向量
DOI：
--
发表时间：
2020
期刊：
Proceedings of Machine Learning Research
影响因子：
--
作者：
Turner, Paxton;Meka, Raghu;Rigollet, Philippe
通讯作者：
Rigollet, Philippe
对称伊辛感知器的冻结 1-RSB 结构
DOI：
10.1145/3406325.3451119
发表时间：
2021
期刊：
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Perkins, Will;Xu, Changji
通讯作者：
Xu, Changji
Sherrington-Kirkpatrick 哈密顿量的优化
DOI：
10.1109/focs.2019.00087
发表时间：
2019
期刊：
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Montanari, Andrea
通讯作者：
Montanari, Andrea
影响因子：
2.3
作者：
El Alaoui, Ahmed;Montanari, Andrea;Sellke, Mark
通讯作者：
Sellke, Mark