Hardness conjecture for the spiked Wishart model

From papers

Let β[1,)\beta \in [-1,\infty) and γ>0\gamma>0. For each nNn\in\mathbb N, set N=n/γN=\lceil n/\gamma\rceil, and let P\mathbb P and Q\mathbb Q be the spiked Wishart distributions defined by the null model Q\mathbb Q with independent samples yiN(0,In)\bm y_i\sim\mathcal N(\bm 0,\bm I_n) and the planted model P\mathbb P obtained by sampling xUnif({±1}n)\bm x\sim\operatorname{Unif}(\{\pm1\}^n) and then independently sampling yiN(0,In+(β/n)xx)\bm y_i\sim\mathcal N(\bm 0,\bm I_n+(\beta/n)\bm x\bm x^{\top}). Write this sequence of distribution pairs as Wishart(β,γ)\mathsf{Wishart}(\beta,\gamma). Hardness of the Wishart model. If β>1\beta>-1 and β2<γ\beta^2<\gamma, there is no polynomial-time hypothesis test between the distributions of Wishart(β,γ)\mathsf{Wishart}(\beta,\gamma): no randomized algorithm f:(Rn)N{p,q}f:(\mathbb R^n)^N\to\{\mathtt p,\mathtt q\} running in polynomial time in nn satisfies

limnP[f(y1,,yN)=p]=limnQ[f(y1,,yN)=q]=1.\lim_{n\to\infty}\mathbb P[f(\bm y_1,\dots,\bm y_N)=\mathtt p]=\lim_{n\to\infty}\mathbb Q[f(\bm y_1,\dots,\bm y_N)=\mathtt q]=1.

This conjecture is the key computational-hardness assumption used to obtain evidence that the constant 11 in spectral conditions for general-purpose Ising-model sampling and free-energy approximation is optimal; its status is not resolved in the source.

Progress summary

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

Sources & referencesView supporting material

Primary source

Dmitriy Kunisky, “Optimality of Glauber dynamics for general-purpose Ising model sampling and free energy approximation”, arXiv:2307.12581 (2023).

Solutions 0

No solutions have been posted yet.