Research map / Learning theory and algorithms / Prediction and decision losses
Peeking with PEAK: Sequential, Nonparametric Composite Hypothesis Tests for Means of Multiple Data Streams
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PEAK, a nonparametric betting-based e-process test for composite hypotheses on means of multiple bounded data streams, averaging evidence across arms to avoid union bounds and grid search.
Problem
Sequential, anytime-valid testing of composite hypotheses about means of multiple bounded data streams under nonparametric, adaptive sampling, where existing testing-by-betting methods need grid searches whose cost grows exponentially with the number of streams.
Approach
A novel betting scheme with bet lambda_t(m) = (running mean - m)/c yields a convex, strictly convex-in-m capital process with type-I error control and power one; PEAK averages the per-arm capital processes into one e-process so composite hypotheses can be tested by convex optimization instead of grid search or union bounds.
Key results
- On THR with Beta arms, PEAK stops at 725.81 samples vs 4534.31 for the union-bound Base rule, and the Bernoulli BAI setting is also reduced relative to Base.
- In the HeartSteps case study, PEAK identifies 8 users whose treatment benefit is established before trial end, saving 18,563 samples (roughly 10%).
- For fixed-horizon BAI tests (T=2000), PEAK runs in 5.21 s versus 3.72 s to 14.50 s for Hedged across grid fidelities, with Hedged's cost growing with grid resolution.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PEAK instead of Base | THR stopping rule · THR, Beta | stopping time: 4534.31 $\pm$ 482.94 -> 725.81 $\pm$ 218.49 | Helped |
| Use PEAK instead of Hedged | THR stopping rule · THR, Beta | stopping time: \textbf{479.16 $\pm$ 205.97} -> 725.81 $\pm$ 218.49 | Hurt |
| Use PEAK instead of Base | THR stopping rule · THR, Bernoulli | stopping time: 4795.51 $\pm$ 1101.09 -> \textbf{1678.08$\pm$ 666.39} | Helped |
| Use PEAK instead of Hedged | THR stopping rule · THR, Bernoulli | stopping time: 2241.18 $\pm$ 1092.49 -> \textbf{1678.08$\pm$ 666.39} | Helped |
| Use PEAK instead of Base | BAI stopping rule · BAI, Beta | stopping time: 4686.1 $\pm$ 565.24 -> 708.52 $\pm$ 266.34 | Helped |
| Use PEAK instead of Hedged | BAI stopping rule · BAI, Beta | stopping time: \textbf{500.12 $\pm$ 214.08} -> 708.52 $\pm$ 266.34 | Hurt |
| Use PEAK instead of Base | BAI stopping rule · BAI, Bernoulli | stopping time: 4631.66 $\pm$ 896.51 -> \textbf{1318.14 $\pm$ 489.29} | Helped |
| Use PEAK instead of Hedged | BAI stopping rule · BAI, Bernoulli | stopping time: 1734.64 $\pm$ 858.66 -> \textbf{1318.14 $\pm$ 489.29} | Helped |
| Increase Hedged grid fidelity from 1 \times 10^{-2} to 5 \times 10^{-3} | Hedged BAI test · BAI, Bernoulli, fixed horizon T=2000 | runtime (s): 3.72 $\pm$ 0.19 -> 6.982 $\pm$ 0.17 | Hurt |
| Increase Hedged grid fidelity from 5 \times 10^{-3} to 2.5 \times 10^{-3} | Hedged BAI test · BAI, Bernoulli, fixed horizon T=2000 | runtime (s): 6.982 $\pm$ 0.17 -> 14.50 $\pm$ 0.65 | Hurt |
| Use PEAK instead of Sub-B | HeartSteps BAI termination rule · HeartSteps, 37 users | users with stopping time before trial end: Sub-B fails to conclude for any user; PEAK provides stopping times for 8 different patients | Helped |
| Use PEAK instead of Hedged | HeartSteps BAI termination rule · HeartSteps, 37 users | users with stopping time before trial end: Hedged concludes for User 22; PEAK provides stopping times for 8 different patients | Helped |
Surprising findings
- The Hedged betting scheme achieves the fewest samples for THR Beta and BAI Beta settings, beating PEAK in low-variance settings.
- Sub-Bernoulli fails to conclude treatment effect for any HeartSteps user within the horizon, while betting methods do.
Limitations
- PEAK requires solvers for hypothesis testing, whereas existing parametric e-processes have minimal overhead.
- Only the Hedged betting scheme is competitive; PEAK is second-best in many single-arm settings rather than best.
- Case study uses a stylized two-arm analysis with alpha=0.3 due to weak signal in the dataset.
Experimental setup
Datasets: HeartSteps
Benchmarks: HeartSteps synthetic Bernoulli and Beta multi-arm streams
Metrics: stopping time confidence sequence log-width runtime (s)
Baselines: Sub-Bernoulli confidence sequences Empirical Bernstein confidence sequences Hoeffding-based confidence sequences (PrPlH) Hedged capital process Base stopping rule (union bound)
Builds on: testing-by-betting e-processes AGRAPA Ville's inequality
Closest papers by meaning
- Sequential Kernel Goodness-of-fit Testing (ICML 2024 · similarity 0.86)
- Time-Sensitive Anytime-Valid Testing (NeurIPS 2026 · similarity 0.85)
- On the Limits of Test-Time Compute: Sequential Reward Filtering for Better Inference (ICML 2026 · similarity 0.85)
- Nearly Tight Bounds for Exploration in Streaming Multi-Armed Bandits with Known Optimality Gap (AAAI 2025 · similarity 0.85)
- Testing the Feasibility of Linear Programs with Bandit Feedback (ICML 2024 · similarity 0.85)
- Strategic Scaling of Test-Time Compute: A Bandit Learning Approach (ICLR 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.