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

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(p1))\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 SNRN\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 AjAA_j\in\mathcal{A} and every ujSNu_j\in\mathcal{S}_N satisfying

1NAj(uj)1NinfwSNAj(w)+μ\frac{1}{N}A_j(u_j)\leq\frac{1}{N}\inf_{w\in\mathcal{S}_N}A_j(w)+\mu

obey

u1,u2u12u22[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 p4p\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 1exp(cN)1-\exp(-cN) for some c>0c>0 and all sufficiently large NN. Furthermore, for every δ>0\delta>0 and every v1,v2HNv_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 1exp(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.

Sources & referencesView supporting material

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.