Non-recovery conjecture for geometric planted matchings

About 5 years old · traced to

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=ω(log⁡n)d=\omega(\log n) when d/log⁡n→∞d/\log n\to\infty, and use d∼alog⁡nd\sim a\log n for a fixed positive constant aa. "Non-recovery conjecture." Suppose that any of the following conditions holds:

  1. 1≪d≪log⁡n1\ll d\ll\log n and, for some ϵ>0\epsilon>0, σ2≥n−(2−ϵ)/d\sigma^2\geq n^{-(2-\epsilon)/d}.
  2. d∼alog⁡nd\sim a\log n and, for some ϵ>0\epsilon>0, σ2≥1(2e1/a−1)2−1+ϵ\sigma^2\geq \frac{1}{(2e^{1/a}-1)^2-1}+\epsilon.
  3. d=ω(log⁡n)d=\omega(\log n) and, for some ϵ>0\epsilon>0, σ2≥(14+ϵ)dlog⁡n\sigma^2\geq (\frac14+\epsilon)\frac{d}{\log n}.

Then, for some c=c(ϵ)>0c=c(\epsilon)>0, ∣E∣≥cn|\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.

References

Primary source

Dmitriy Kunisky and Jonathan Niles-Weed, “Strong recovery of geometric planted matchings”, arXiv:2107.05567 (2021).

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.