AI Paper Atlas

Research map / Learning theory and algorithms / Prediction and decision losses

Adaptive Concentration Inequalities for Sequential Decision Problems

Shengjia Zhao, Enze Zhou, Ashish Sabharwal, Stefano Ermon

NeurIPS 2016 · Learning theory and algorithms › Prediction and decision losses · approach: Adaptive testing and experiments · 26 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
Use adaptive Hoeffding boundary instead of union-bound or LIL boundariesSequential sign testing · Bernoulli mean positiveness testsample count: at least an order of magnitude fewer samplesImproved
Adaptive Hoeffding bound with adaptive stopping vs LIL bound of prior workFinite-time threshold boundary · Boundary width comparison across n and deltaboundary tightness: roughly 1.5x tighterImproved
Halve the adaptive boundary (ablation)Sequential sign testing (AH-RW) · Bernoulli mean positiveness testempirical accuracy: accuracy falls below 0.95 requirement despite ~4x speedupHurt
Exponentially sparse stopping times (batch sampling) applied to the boundary (ablation)Sequential sign testing · Bernoulli mean positiveness testsample count and accuracyNo clear effect
Exponentially sparse stopping times (batch sampling) in best arm identification (ablation)Adaptive Hoeffding race · Best arm identification, Gaussian instancesample countImproved
Replace distribution-based elimination (state-of-the-art asymptotically) with adaptive Hoeffding raceBest arm identification · Gaussian instance, delta=0.05sample countImproved

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy