Planted Geometric Matching Problems
summary
Model: points Xi ~ N(0,I) get Gaussian displacements with variance sigma^2, then permuted; estimator is the maximum likelihood estimator solved as a linear assignment minimizing sum of squared distances. Main claim: when d << log n there are three regimes in sigma: sigma << n^{-4/d} gives perfect recovery, sigma between n^{-4/d} and n^{-2/d} yields polynomially many errors with exponent that varies linearly with a parameter alpha, and sigma >= n^{-2/d} yields Theta(n) errors. Proofs count augmenting 2-cycles using first/second moment methods. Additional facts: a jump at d ≈ log n connects to the independent-entry model, and d=2 vs d>=3 produces qualitatively different tracking time scalings.
AI-written summary · about
chapters (7)
- 0:00Introduction and motivation
- 4:10Modeling the matching problem
- 7:48Maximum likelihood estimator
- 10:48Prior work and context
- 15:47Error analysis and thresholds
- 22:04Counting augmenting cycles
- 26:00Dimensionality and conclusion
related talks
34mInformation/Computation Gaps in Heavy-Tailed Statistics
39mLocalization and Nonmetric Multidimensional Scaling via Paired Comparisons
01h 00mAlgorithmic High Dimensional Robust Statistics I
39mAbove Average-Case Analysis?
48mComputational-Statistical Tradeoffs in Robust High-Dimensional Estimation
01h 30mHigh-Dimensional Statistics I
53mDesigning Robust Learners
01h 18mReconsidering Overfitting in the Age of Overparameterized Models