The Hilbert-cube Overlap Gap Property conjecture for even p-spin tensors

About 7 years old · traced to

Let AA and A^\hat A be independent random tensors in (RN)⊗p(\mathbb{R}^N)^{\otimes p} with independent entries distributed as N(0,N−(p−1))\mathcal{N}(0,N^{-(p-1)}), and set

Aτ=1−τA+τA^,0≤τ≤1,A_\tau=\sqrt{1-\tau}A+\sqrt{\tau}\hat A,\qquad 0\leq\tau\leq1,

with A={Aτ:0≤τ≤1}\mathcal{A}=\{A_\tau:0\leq\tau\leq1\}. For a domain SN⊂RN\mathcal{S}_N\subset\mathbb{R}^N, say that A\mathcal{A} satisfies the Overlap Gap Property (OGP) with parameters μ>0\mu>0 and 0<ν1<ν2<10<\nu_1<\nu_2<1 if every Aj∈AA_j\in\mathcal{A} and every uj∈SNu_j\in\mathcal{S}_N satisfying

1NAj(uj)≤1Ninf⁡w∈SNAj(w)+μ\frac{1}{N}A_j(u_j)\leq\frac{1}{N}\inf_{w\in\mathcal{S}_N}A_j(w)+\mu

obey

∣⟨u1,u2⟩∣∥u1∥2∥u2∥2∈[0,ν1]∪[ν2,1].\frac{|\langle u_1,u_2\rangle|}{\|u_1\|_2\|u_2\|_2}\in[0,\nu_1]\cup[\nu_2,1].

Hilbert-cube OGP conjecture. For every even p≥4p\geq4, there exist μ>0\mu>0 and 0<ν1<ν2<10<\nu_1<\nu_2<1 such that A\mathcal{A} satisfies the OGP with domain SN=HN\mathcal{S}_N=\mathcal{H}_N, with probability at least 1−exp⁡(−cN)1-\exp(-cN) for some c>0c>0 and all sufficiently large NN. Furthermore, for every δ>0\delta>0 and every v1,v2∈HNv_1,v_2\in\mathcal{H}_N satisfying

A(v1)/N≤(1−δ)E[ηN],A^(v2)/N≤(1−δ)E[ηN],A(v_1)/N\leq(1-\delta)\mathbb{E}[\eta_N],\qquad \hat A(v_2)/N\leq(1-\delta)\mathbb{E}[\eta_N],

one has ∣⟨v1,v2⟩∣≤δN|\langle v_1,v_2\rangle|\leq\delta N with probability at least 1−exp⁡(−cN)1-\exp(-cN) for some c>0c>0 and all large NN. The OGP has already been proved for the binary domain BN\mathcal{B}_N; the conjecture extends it to the Hilbert cube and is used as an assumption for the paper’s algorithmic barrier. The asserted chaos statement is included as part of the conjecture.

References

Primary source

David Gamarnik and Aukosh Jagannath, “The Overlap Gap Property and Approximate Message Passing Algorithms for p-spin models”, arXiv:1911.06943 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.