Research map / Learning theory and algorithms / Sample complexity
Learning the Optimal Stopping for Early Classification within Finite Horizons via Sequential Probability Ratio Test
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 FIRMBOUND, an SPRT-based early classification framework that estimates the finite-horizon backward induction solution from data via density ratio estimation, convex function learning (or GP regression as a faster alternative).
Problem
Optimal stopping for early classification of time series under a finite horizon requires backward induction, which is computationally expensive and needs true log-likelihood ratios that are unavailable in practice.
Approach
Estimate the continuation risk (conditional expectation in backward induction) directly from training data via convex function learning (concavity-constrained ADMM) or GP regression, and estimate the sufficient statistic (LLRs/posteriors) with sequential density ratio estimation (SPRT-TANDEM), so that the Bayes-optimal stopping region can be applied at test time without re-solving backward inducti
Key results
- On SiW, HMDB51, UCF101 and FordA, FIRMBOUND reaches the Pareto front of the speed-accuracy tradeoff and extends it in a few datasets.
- Variance of hitting time is statistically significantly smaller than vanilla SPRT across datasets (Wilcoxon signed-rank test, p=2.00e-8).
- GP regression training is reported to be about 30 times faster than CFL training (about 20 min vs 10 h on RTX 2080Ti for the two-class Gaussian dataset).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace vanilla SPRT with static thresholds by FIRMBOUND with CFL | Vanilla SPRT · Gauss2est. | MVHT: 10.47 -> 9.01 | Helped |
| Replace vanilla SPRT with static thresholds by FIRMBOUND with CFL | Vanilla SPRT · Gauss3est. | MVHT: 44.02 -> 42.78 | Helped |
| Replace vanilla SPRT with static thresholds by FIRMBOUND with CFL | Vanilla SPRT · DOL | MVHT: 489.89 -> 405.78 | Helped |
| Replace vanilla SPRT with static thresholds by FIRMBOUND with CFL | Vanilla SPRT · SiW | MVHT: 2.87 -> 1.97 | Helped |
| Replace vanilla SPRT with static thresholds by FIRMBOUND with CFL | Vanilla SPRT · HMDB | MVHT: 199.31 -> 195.35 | Helped |
| Replace vanilla SPRT with static thresholds by FIRMBOUND with CFL | Vanilla SPRT · UCF101 | MVHT: 0.55 -> 0.53 | Helped |
| Replace vanilla SPRT with static thresholds by FIRMBOUND with CFL | Vanilla SPRT · FordA | MVHT: 32.15 -> 23.39 | Helped |
| Use GP regression instead of CFL to estimate continuation risk (ablation) | FIRMBOUND · Two-class sequential Gaussian dataset | training time: 30 times faster | Helped |
| Use random stopping times instead of the learned stopping rule (ablation) | FIRMBOUND · Ablation datasets | AAPR | Hurt |
| Use monotonically descending artificial decision boundaries instead of the learned stopping rule (ablation) | FIRMBOUND · Ablation datasets | AAPR | Hurt |
Surprising findings
- FIRMBOUND does not always improve mean hitting time or error over vanilla SPRT, though it consistently reaches the Pareto-optimal point and reduces hitting-time variance.
Limitations
- GP regression trades statistical consistency for speed.
- Consistency theorem relies on several technical assumptions (large dataset, ADMM iterations, large network).
- Does not always outperform vanilla SPRT in mean hitting time or error rate.
Experimental setup
Datasets: sequential i.i.d. Gaussian (synthetic) damped-oscillating LLR (synthetic) Spoofing in the Wild (SiW) HMDB51 UCF101 FordA
Benchmarks: SiW HMDB51 UCF101 FordA sequential Gaussian (2- and 3-class) damped-oscillating LLR
Metrics: averaged a posteriori risk (AAPR) speed-accuracy tradeoff curve (macro-averaged recall vs mean mean variance of hitting time
Baselines: SPRT with static thresholds LSTMms EARLIEST TCN-Transformer (TCNT) CALIMERA
Builds on: SPRT-TANDEM Wald's SPRT LSTMms EARLIEST CALIMERA
Closest papers by meaning
- Early Time Classification with Accumulated Accuracy Gap Control (ICML 2024 · similarity 0.84)
- Martingale Posterior Neural Networks for Fast Sequential Decision Making (NeurIPS 2025 · similarity 0.84)
- Minimax Optimal Early-Stopped Gradient Descent for Gaussian Mixture Classification (NeurIPS 2026 · similarity 0.84)
- How Patterns Dictate Learnability in Sequential Data (NeurIPS 2025 · similarity 0.84)
- Instance-Conditional Timescales of Decay for Non-Stationary Learning (AAAI 2024 · similarity 0.84)
- Density Ratio Estimation-based Bayesian Optimization with Semi-Supervised Learning (ICML 2025 · similarity 0.84)
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.