Early time classification algorithms aim to label a stream of features
without processing the full input stream, while maintaining accuracy comparable
to that achieved by applying the classifier to the entire input. In this paper,
we introduce a statistical framework that can be applied to any sequential
classifier, formulating a calibrated stopping rule. This data-driven rule
attains finite-sample, distribution-free control of the accuracy gap between
full and early-time classification. We start by presenting a novel method that
builds on the Learn-then-Test calibration framework to control this gap
marginally, on average over i.i.d. instances. As this algorithm tends to yield
an excessively high accuracy gap for early halt times, our main contribution is
the proposal of a framework that controls a stronger notion of error, where the
accuracy gap is controlled conditionally on the accumulated halt times.
Numerical experiments demonstrate the effectiveness, applicability, and
usefulness of our method. We show that our proposed early stopping mechanism
reduces up to 94% of timesteps used for classification while achieving rigorous
accuracy gap control.

通过引入一种统计框架，本文提出了一种适用于任何连续分类器的校准停止规则，以有限样本、基于分布的方式控制完整和早期分类之间的准确性差距，在平均上具有较高的错误控制能力，并通过数字实验证明了该方法的有效性和实用性。

早期时间分类与累积准确度差控制

Early Time Classification with Accumulated Accuracy Gap Control

Hyperparameter optimization (HPO) is a fundamental problem in automatic
machine learning (AutoML). However, due to the expensive evaluation cost of
models (e.g., training deep learning models or training models on large
datasets), vanilla Bayesian optimization (BO) is typically computationally
infeasible. To alleviate this issue, Hyperband (HB) utilizes the early stopping
mechanism to speed up configuration evaluations by terminating those
badly-performing configurations in advance. This leads to two kinds of quality
measurements: (1) many low-fidelity measurements for configurations that get
early-stopped, and (2) few high-fidelity measurements for configurations that
are evaluated without being early stopped. The state-of-the-art HB-style
method, BOHB, aims to combine the benefits of both BO and HB. Instead of
sampling configurations randomly in HB, BOHB samples configurations based on a
BO surrogate model, which is constructed with the high-fidelity measurements
only. However, the scarcity of high-fidelity measurements greatly hampers the
efficiency of BO to guide the configuration search. In this paper, we present
MFES-HB, an efficient Hyperband method that is capable of utilizing both the
high-fidelity and low-fidelity measurements to accelerate the convergence of
HPO tasks. Designing MFES-HB is not trivial as the low-fidelity measurements
can be biased yet informative to guide the configuration search. Thus we
propose to build a Multi- Fidelity Ensemble Surrogate (MFES) based on the
generalized Product of Experts framework, which can integrate useful
information from multi-fidelity measurements effectively. The empirical studies
on the real-world AutoML tasks demonstrate that MFES-HB can achieve 3.3-8.9x
speedups over the state-of-the-art approach - BOHB.

MFES-HB 是一种高效的超参数优化方法，它结合了高保真度和低保真度度量以加快收敛速度，并使用广义专家乘积框架构建了多重保真度集合代理模型，该方法可在现实世界的自动机器学习任务中比 BOHB 等现有方法快 3.3-8.9 倍。