Computation-Statistics Tradeoffs in Unsupervised Learning via Data Summarization
summary
Shows that summarizing data with coresets gives a provable computation–risk trade-off for k‑means: randomized importance sampling constructions replace n points by s weighted points so solving on s can meet a fixed ε risk while reducing solver time, under mild conditions (solver sublinear in n, summarization cost smaller than solver cost). Proposes a practical exploration algorithm that grows s with validation and, on synthetic and real sets (protein, seismic, Yahoo webscope), hits near‑oracle timings. Tools: importance sampling, streamable two‑stage construction.
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:34Data as a statistical resource
- 1:18Data as a computational resource More data → Lower computational cost.
- 2:52Why would we gain in computation?
- 4:45Statistical k-means = Vector Quantization
- 8:26How do we "weaken" estimators?
- 14:41How do we construct coresets?
- 18:00Summarize-then-Solve Architecture
- 21:15Tradeoffs exist!
- 21:32What does this mean?
- 22:12Can we approach this optimal tradeoff?
- 23:47Explore-Exploit the Summarization Space
- 26:56Contributions, Present and Future • Data-time tradeoff via coreset summarization
related talks
46mRecent Advances in Diversity Maximization in the Offline and Composable Coreset Models
01h 02mTheory and Big Data
41mScalable Spatial Scan Statistics with Coresets
01h 02mImportance Sampling in High Dimensions via Hashing
01h 02mSampling for Linear Algebra, Statistics, and Optimization II
01h 26mStreaming, Sketching and Sufficient Statistics II
12mIterative Methods and High-Dimensional Statistics
01h 24mStreaming, Sketching and Sufficient Statistics I