Sampling Algorithms for Combinatorial Pure Exploration
summary
Takes the max-weight spanning-tree and matroid best-set problems from unknown edge means and gives sample-complexity bounds: adaptive elimination matches the classic 1/Δ^2 · log(1/δ) per-arm lower bound summed over arms (and N/ε^2 · log(K/δ) for top-K) using Chernoff and round-robin median-style rounds, while a Karger-style subsampling routine shrinks a graph to O(|V|) edges in expectation (surprising constant 2|V|). Proves a per-instance convex-program lower bound via change-of-distribution and gives an algorithm matching it up to a log|F| factor but not generally polytime; general partition version incurs an annoying n^3 term.
AI-written summary · about
chapters (15)
- 0:00Intro
- 0:32max-weight spanning tree
- 2:05stochastic multi-armed bandits
- 4:11today's menu
- 5:38upper bounds: best arm identification
- 10:07median elimination for top k
- 11:15lower bounds: change of distribution and mannor-tsitsiklis
- 11:38combinatorial pure exploration
- 12:32the main idea
- 16:37algo for max.spanning tree
- 17:38more general constraints?
- 22:11the lower bound
- 22:39upper bound: the hurdles
- 23:14sampling algorithm: from solution to strategy
- 24:34general sampling problem
related talks
47mSuccinct Representations and Efficient Algorithms Based on Linear Programming
46mRecent Advances in Diversity Maximization in the Offline and Composable Coreset Models
52mConstrained Subset Selection Problems under Diversity Measures
29mPure Exploration Problems
42mLearning What Works Best When
31mSimple Models and Exact Algorithms for Computing Network Modules
35mLocal Statistics, Semidefinite Programming, and Community Detection II
01h 26mStreaming, Sketching and Sufficient Statistics II