Non-recovery conjecture for geometric planted matchings
Non-recovery conjecture for geometric planted matchings
Let be the number of points, the dimension, the noise parameter, and the set of errors made by the maximum-likelihood estimator. Write when , and use for a fixed positive constant . "Non-recovery conjecture." Suppose that any of the following conditions holds:
- and, for some , .
- and, for some , .
- and, for some , .
Then, for some , 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
Sign in to submit a solution.
No solutions have been posted yet.