Localization and Nonmetric Multidimensional Scaling via Paired Comparisons

on YouTube ↗39m

" summary

Estimates a Euclidean vector X from binary one-bit measurements that compare which of two known points is closer, models paired comparisons as Gaussian random projections plus thresholds, and proves nonadaptive recovery needs roughly M ∝ (R/ε)·(d log(·)) measurements to get ‖X̂−X‖≤ε with high probability. A simple convex program (minimum-norm fit) recovers X, performance peaks for a specific Gaussian variance, and an adaptive recursive centering scheme halves radius per stage to deliver exponential-in-stages improvement; noisy labels handle via SVM-style slack.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 2:46Ideal point model of preference
3. 6:13Applications
4. 11:55How well can we estimate x?
5. 13:44Paired comparisons as binary observations
6. 16:22Normal model
7. 17:17Estimation from binary observations
8. 20:32Consistent recovery guarantee
9. 27:22Can we do better?
10. 28:02Cutting the error in half
11. 29:25A simple adaptive algorithm
12. 30:16Adaptive vs nonadaptive
13. 31:18Robustness to errors
14. 31:45What about localizing items?
15. 33:28Convexification
16. 34:38Nonmetric MDS
17. 35:33Summary

" related talks

• 31mPlanted Geometric Matching ProblemsDmitriy (Tim) Kunisky · Rigorous Evidence for Information-Computation Trade-offs
• 45mHigh Dimensional Robust Sparse RegressionConstantine Caramanis · Sublinear Algorithms and Nearest-Neighbor Search
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 33mClustering Using Pairwise ComparisonsR. Srikant · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 49mMetric Representations: Algorithms and GeometryAnna Gilbert · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 43mMetric Learning for Individual FairnessChristina Ilvento · Beyond Differential Privacy 2019
• 01h 07mRecent Progress in High-Dimensional LearningAnkur Moitra · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 26mUsing Random Projections to Make Sense of High-Dimensional ...Stefan Savev · Berlin Buzzwords 2015