Clustering Using Pairwise Comparisons

on YouTube ↗33m

" summary

Converts the sparse N × (M choose 2) pairwise matrix into an N × M net-wins matrix, applies spectral projection and then repeats clustering after a random split-into-L-subsets of items (L = Θ(log N)), and combines results by majority vote. Main claim: under a separation condition on expected rows and roughly equal cluster sizes, perfect clustering needs only R·polylog(N) pairwise comparisons per user—rigorously R·log^5 N suffices with probability ≥ 1 − 1/N, within polylog of the simple lower bound ~log N.

AI-written summary · about

" chapters (7)

1. 0:00Introduction and context
2. 2:35Traditional problem setup
3. 5:51Problem formulation
4. 9:27Algorithm and previous work
5. 15:15The proposed algorithm
6. 21:03Theoretical analysis
7. 26:43Experimental results and Q&A

" related talks

• 39mLocalization and Nonmetric Multidimensional Scaling via Paired ComparisonsMark Davenport · Real-Time Decision Making
• 47mCrowdsourcing for Clustering: Algorithms and Information-Theoretic Lower BoundsBabak Hassibi · Real-Time Decision Making
• 53mWhen Does Clustering Become Easy, and Should We Care About Other Cases?Shai Ben-David · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 33mLearning the Best Agorithm for Max-Cut, Clustering, and Other​ ​Partitioning ProblemsVaishnavh Nagarajan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 35mClustering: A Guide for the PerplexedLeland McInnes, John Healy · PyData DC 2016
• 37mPower to the Points: Local Certificates for ClusteringsSuresh Venkatasubramanian · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 25mConstrained Rank Aggregation and Correlation ClusteringOlgica Milenkovic · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 25mLucky Talk: From Coding to ClusteringEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)