Research map / Learning theory and algorithms / Prediction and decision losses
Early Time Classification with Accumulated Accuracy Gap Control
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 a distribution-free, finite-sample calibrated stopping rule for early time classification that controls the accuracy gap conditionally on accumulated halt times, via a two-stage greedy screening plus fixed-sequence testing on Learn-then-Test.
Problem
Early time classification of sequential inputs requires stopping early while keeping accuracy close to full-input classification; existing stopping rules lack finite-sample statistical guarantees, and marginal risk control permits high accuracy gaps for early halt times.
Approach
Builds on Learn-then-Test: a greedy candidate-screening stage finds a threshold vector on one calibration split, then fixed-sequence testing with suffix-structured hypotheses on a held-out split certifies conditional accuracy-gap control over accumulated halt times.
Key results
- On the NLP task, the conditional method controls the conditional accuracy gap at the 10% level across halt times while the marginal method exceeds it for early halts; average normalized halt time is 0.831 for conditional vs 0.483 for marginal.
- Across five structured datasets averaged over 100 splits, the conditional method keeps the 20% earliest accuracy gap around 0.03-0.065 while the marginal method reaches up to 0.171 (PenDigits).
- The proposed early stopping reduces up to 94% of timesteps used for classification while achieving accuracy gap control.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use conditional rather than marginal risk control | Early time classification with LSTM · ElectricDevices | accuracy gap, 20% earliest halt times: 0.117 -> 0.030 | Helped |
| Use conditional rather than marginal risk control | Early time classification with LSTM · Crop | average normalized halt time: 0.580 -> 0.450 | Helped |
| Use conditional rather than marginal risk control | Early time classification with LSTM · Tiselac | average normalized halt time: 0.209 -> 0.215 | Hurt |
| Use conditional rather than marginal risk control | Early time classification with LSTM · Structured datasets | accuracy gap on earliest halt times | Helped |
| Use conditional rather than marginal risk control | Vicuna-13B on QuALITY · QuALITY | average normalized halt time: 0.483 vs 0.831 | Hurt |
| Add the Stage 2 testing procedure after candidate screening (ablation) | Conditional method · QuALITY | conditional accuracy gap | Helped |
Surprising findings
- The marginal method, though controlling the marginal gap, has accumulated accuracy gaps above 10% for early halt times (e.g., 0.117 on Tiselac 20% earliest), so marginal guarantees can hide poor early-stopping reliability.
Limitations
- Relies on the i.i.d. assumption between calibration and test data, which may be violated in practice.
- Exact binary-loss p-value is not directly applicable to non-binary losses such as regression.
- Candidate screening is heuristic and not guaranteed to control risk; testing stage is required.
Experimental setup
Datasets: Tiselac ElectricDevices PenDigits Crop WalkingSittingStanding QuALITY
Benchmarks: Tiselac ElectricDevices PenDigits Crop WalkingSittingStanding QuALITY
Metrics: conditional accuracy gap marginal accuracy gap average normalized halt time
Baselines: marginal risk control method
Builds on: Learn then Test early exit calibration for transformers split fixed sequence testing
Closest papers by meaning
- Conformal Inference is (almost) Free for Neural Networks Trained with Early Stopping (ICML 2023 · similarity 0.85)
- Learning the Optimal Stopping for Early Classification within Finite Horizons via Sequential Probability Ratio Test (ICLR 2025 · similarity 0.84)
- What Does It Take to Build a Performant Selective Classifier? (NeurIPS 2025 · similarity 0.83)
- Testing Calibration in Nearly-Linear Time (NeurIPS 2024 · similarity 0.83)
- Instance-dependent Early Stopping (ICLR 2025 · similarity 0.82)
- Prediction Error-based Classification for Class-Incremental Learning (ICLR 2024 · similarity 0.82)
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.