Greedy Approximation Algorithms for Active Sequential Hypothesis Testing
summary
Proposes greedy algorithms for active sequential hypothesis testing with approximation guarantees that are independent of the number of actions and grow only logarithmically in the number of hypotheses: a log H bound for the partially adaptive policy and log^2 H for the fully adaptive policy. Uses submodular function ranking and optimal decision‑tree tools, models binary (Bernoulli) outcomes with uniform action cost and a separability parameter S in the bounds, repeats actions (~hundreds, typically <800) to reduce noise, evaluates on synthetic and COSMIC mutation data, and reports large gains over LP heuristics and prior two‑stage methods.
AI-written summary · about
chapters (9)
- 0:00Introduction to speaker
- 1:14Liquid biopsy application
- 4:44Problem formulation
- 10:38Algorithmic approach
- 14:26Performance comparisons
- 22:00Algorithm mechanisms
- 28:30Theoretical guarantees
- 36:16Experimental results
- 39:18Closing Q&A
related talks
40mApproximation Algorithms for Optimization under Uncertainty
32mHypothesis selection with computational constraints
01h 00mContinuous Methods 4
28mNear-Optimal Hypothesis Testing via Convex Optimization
34mPandora's Box with Correlations: Learning and Approximation
32mDesigning Adaptive Experiments For Policy Learning And Inference
55mWhat Are the Statistical Limits of Offline Reinforcement Learning With Function Approximation?
41mOnline Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization