Hypothesis selection with computational constraints
summary
Presents a concrete, nearly-linear-time procedure that attains a 3·OPT guarantee (plus O(ε)) for proper hypothesis selection while keeping optimal sample usage of log n / ε^2 samples. It builds on Scheffé sets and semi-distances, replaces all-pairs comparisons with a bucketing + heavy-updater scan that performs structured edge updates, and proves termination/time ≈ Θ(n/ε) (ignoring sample-cost factors). Shows the factor 3 is information-theoretically necessary for proper algorithms and the method succeeds with the stated bounds.
AI-written summary · about
chapters (8)
- 0:00Introduction to problem
- 2:26Formal definition and goals
- 5:17Overview of research results
- 7:55Core concepts and definitions
- 14:10Minimum distance estimation
- 17:09New bucket-based algorithm
- 22:26Proof sketch and correctness
- 26:45Q&A session
related talks
28mNear-Optimal Hypothesis Testing via Convex Optimization
43mGreedy Approximation Algorithms for Active Sequential Hypothesis Testing
44mSomething for Almost Nothing: Advances in Sub-Linear Time Algorithms
44mParsimonious Learning-Augmented Algorithms
48mVariable Selection with Error Control: Another Look at Stability Selection
29mSampling Algorithms for Combinatorial Pure Exploration
43mHypothesis Testing Stop Criterion with "Precision Is The Goal"
21mTesting Distribution Families