Crowdsourcing for Clustering: Algorithms and Information-Theoretic Lower Bounds

on YouTube ↗47m

" summary

Uses a low-rank plus sparse convex program (nuclear norm + L1) to recover cluster blocks from partially observed stochastic block graphs, proves success requires minimum cluster size on the order of sqrt(N) under constant P,Q,R, and connects to planted-clique limits. Runs Amazon Mechanical Turk on 473 dog images (15% edges observed, worker edge-error ≈24%): spectral on cleaned L reduces label errors from 193 to 13. Finds triangle queries cost ~1.5× edge and, for same budget, show ~2× effective edges and error drops (dogs 25%→20%, birds 14%→11%).

AI-written summary · about

" chapters (18)

1. 0:00Introduction
2. 8:35The Simple Idea
3. 10:42The Algorithm
4. 12:50Motivation
5. 20:52Simulation
6. 23:28Related work
7. 25:30Simulation result
8. 26:30Crowdsourcing
9. 31:03Triangle Queries
10. 32:53Birds
11. 33:28Triangle Query
12. 34:16Probability of Success
13. 35:23Bottom Line
14. 37:35Cost
15. 40:47Summary
16. 41:21Empirical Evidence
17. 42:35Crowdsourcing for Clustering
18. 43:13Question of Interest

" related talks

• 25mLucky Talk: From Coding to ClusteringEmmanuel Abbe · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 53mWhen Does Clustering Become Easy, and Should We Care About Other Cases?Shai Ben-David · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 29mApplying Randomized Methods for Zonotope Enumeration and...David Gleich · Randomized Numerical Linear Algebra and Applications 2018
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 33mClustering Using Pairwise ComparisonsR. Srikant · Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016)
• 25mConstrained Rank Aggregation and Correlation ClusteringOlgica Milenkovic · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 07mA Few Simple Average-Case Reduction Techniques And Their Surprising EffectivenessGuy Bresler · Rigorous Evidence for Information-Computation Trade-offs
• 33mLearning the Best Agorithm for Max-Cut, Clustering, and Other​ ​Partitioning ProblemsVaishnavh Nagarajan · Learning, Algorithm Design and Beyond Worst-Case Analysis