Non-recovery conjecture for geometric planted matchings

From papers

Let nn be the number of points, dd the dimension, σ2\sigma^2 the noise parameter, and E\mathcal{E} the set of errors made by the maximum-likelihood estimator. Write d=ω(logn)d=\omega(\log n) when d/lognd/\log n\to\infty, and use dalognd\sim a\log n for a fixed positive constant aa. "Non-recovery conjecture." Suppose that any of the following conditions holds:

  1. 1dlogn1\ll d\ll\log n and, for some ϵ>0\epsilon>0, σ2n(2ϵ)/d\sigma^2\geq n^{-(2-\epsilon)/d}.
  2. dalognd\sim a\log n and, for some ϵ>0\epsilon>0, σ21(2e1/a1)21+ϵ\sigma^2\geq \frac{1}{(2e^{1/a}-1)^2-1}+\epsilon.
  3. d=ω(logn)d=\omega(\log n) and, for some ϵ>0\epsilon>0, σ2(14+ϵ)dlogn\sigma^2\geq (\frac14+\epsilon)\frac{d}{\log n}.

Then, for some c=c(ϵ)>0c=c(\epsilon)>0, Ecn|\mathcal{E}|\geq cn with high probability. This conjecture would complete the high-level picture by predicting a macroscopic number of errors in the parameter regimes not covered by the paper's recovery results; the stated thresholds are suggested by first-moment combinatorics of augmenting cycles.

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 and Jonathan Niles-Weed, “Strong recovery of geometric planted matchings”, arXiv:2107.05567 (2021).

Solutions 0

No solutions have been posted yet.