Learning the Optimal Stopping for Early Classification within Finite Horizons via Sequential Probability Ratio Test
Authors: Akinori F. Ebihara
Taiki Miyagawa
Kazuyuki Sakurai
Hitoshi Imaoka
Venue: ICLR 2025 Poster (2025)
Keywords: Early Classification of Time Series
Sequential Probability Ratio Test
Primary area: learning on time series and dynamical systems
TL;DR: FIRMBOUND is an SPRT-based early classification framework that provides a statistically consistent and computationally efficient estimator of optimal decision boundaries for time series of finite lengths, tailored for large-scale real-world problems.

Abstract: Time-sensitive machine learning benefits from Sequential Probability Ratio Test (SPRT), which provides an optimal stopping time for early classification of time series. However, in *finite horizon* scenarios, where input lengths are finite, determining the optimal stopping rule becomes computationally intensive due to the need for *backward induction*, limiting practical applicability. We thus introduce FIRMBOUND, an SPRT-based framework that efficiently estimates the solution to backward induction from training data, bridging the gap between optimal stopping theory and real-world deployment. It employs *density ratio estimation* and *convex function learning* to provide statistically consistent estimators for sufficient statistic and conditional expectation, both essential for solving backward induction; consequently, FIRMBOUND minimizes Bayes risk to reach optimality. Additionally, we present a faster alternative using Gaussian process regression, which significantly reduces training time while retaining low deployment overhead, albeit with potential compromise in statistical consistency. Experiments across independent and identically distributed (i.i.d.), non-i.i.d., binary, multiclass, synthetic, and real-world datasets show that FIRMBOUND achieves optimalities in the sense of Bayes risk and speed-accuracy tradeoff. Furthermore, it advances the tradeoff boundary toward optimality when possible and reduces decision-time variance, ensuring reliable decision-making. Code is included in the supplementary materials.

Published as a conference paper at ICLR 2025
LEARNING THE OPTIMAL STOPPING FOR EARLY CLASSIFICATION WITHIN FINITE HORIZONS VIA SEQUENTIAL PROBABILITY RATIO TEST
Akinori F. Ebihara
Taiki Miyagawa
Kazuyuki Sakurai
Hitoshi Imaoka
NEC Corporation sebihara@nec.com
ABSTRACT
Time- sensitive machine learning benefits from Sequential Probability Ratio Test (SPRT), which provides an optimal stopping time for early classification of time series. However, in finiee horizon scenarios, where input lengths are finite, deter- mining the optimal stopping rule becomes computationally intensive due to the need for backward induction, limiting practical applicability. We thus introduce F FIRMBOUND, SPRT-based framework that efficiently estimates the solution backward induction from training data, bridging the gap between optimal stopping theory and real-world deployment. It employs density ratio estimation and convex function learning to provide statistically consistent estimators for sufficient statistic and conditional expectation, both essential for solving backward induction; con- sequently, F FIRMBOUND minimizes Bayes risk to reach optimality. Additionally, we present a faster alternative using Gaussian process regression, which signifi- cantly reduces training time while retaining low deployment overhead, albeit with potential compromise in statistical consistency. Experiments across independent and identically distributed (i.i.d.,, non-i.i.d., binary, multiclass, synthetic, and real- world datasets show that F FIRMBOND achieves optimalities in the sense of Bayes risk and speed-accuracy tradeoff. Furthermore, it advances the tradeoff boundary toward optimality when possible and reduces decision-time variance, ensuring reliable decision-making. making. Code is included in the supplementary materials.
INTRODUCTION
Sequential Probability Ratio Test (SPRT) Wald 1945) offers a theoretically optimal framework for early classification of time series (ECTS) (Xing et al. 2009). ECTS is a task to sequentially observe an input time series and classify it as early and accurately as possible, balancing speed and accuracy (Gupta al., 2020 Mori et al., 2016). This is vital in real-world scenarios with high sampling costs or where delays can have severe implications: e.g., medical diagnosis (Evans et al. 2015 Griffin & Moorman 2001 Vats& & Chan 2016). stock crisis identification (Ghalwash et al. 2014). and autonomous driving (Doná et al. 2019). While the multi-objective nature of ECTS presents challenges, SPRT, with log liaes-oikel ratios (LLRs), is optimal for binary i.i.d. samples and asympiotically optimal for multi-class, non-i.i.d. time series. SPRT's optimality ensures decisions within the shortest possible time with a controlled error rate (Tartakovsky 1998 1999).
A key limitation of SPRT in real-world applications is the finite horizon (Grinold 1977 Xiong et al. 2022): the deadline for classification. While the original SPRT assumes an indefinite sampling period to reach its decision threshold (Tartakovsky et al.) 2014). practical scenarios often demand carlier decisions. For instance, detecting a face spoofing attack at a biometric checkpoint requires classification before the subject passes through (Labati et al. 2016). This constraint frequently results in suboptimal performance, as early thresholds may cause either delayed or rushed decisions (Fig. [b).
Fortumately, the optimal decision boundary for the finite horizon can be derived by solving backward induction, a recursive formula progressing from the horizon to the start of the time series (Chow et al., 1991 Peskir & Shiryaev 2006). It optimizes the boundary by minimizing Bayes risk, or average

---

Published as a conference paper at ICLR 2025
(a)
Performance gain
(b)
Models with different parameters
Sufficient statistic
Wrong
Finite harizon (deadline
FIRMBOUND achieves the Pareto-optimal point given sampling cost
Delayed
Error rate
Optimal
Pareto front (Tradeoff boundary)
Time steps
Optimal decision boundary
high
FIRMBOUND finds a new Pareto-opting point available
Static,
decision boundary
Class sufticient statistic trajectory of Input sequence
Class 0 sumcicnt statistic tra ectoory of input sequence
Time
Figure 1: Visual guide to the optimal stopping under finite horizon. (a) Finite horizon SPRT.
Prematurely set decision boundaries lead to suboptimal results. Starbursts mark the stopping times of three decision boundaries for class I: (Right) static boundary (upper gray line) leads to delayed decision making; (Center) an optimal decision boundary within a finite horizon (yellow curve) achieves faster stopping time; and (Left) lower static boundary (lower gray line) can achieve the same hitting time (center starburst) but increases the risk of classifying another sequence (blue trajectory) wrong class. (b) FIRMBOUND & Pareto front. F FIRBBUNDD's goal delineate the Careto-optingg point (meaning "optimal in the speed-accurage
objeit-beeective optimization problem") on the speed-acees accuracy tradeoff (SAT) curve. It achieves the Pareto-optimal point within the existing front (blue star) or discovers new Pareto-optimal point (red star) if possible.
posteriori risk (AAPR), which accounts for both classification accuracy and sampling costs. The resulting optimal boundary typically tapers monotonically it nears the finite horizon (Fig. [p).
Unfortunately, applying the backward induction under real-world conditions is impractical due to its prohibitively high computational costs and the lack of true LLRs (Tartakovsky et al. 2014). To solve the backward induction, numerically calculating the conditional expectation of future risks (Eq. 5) is required because analytical solution has been identified. This calculation necessitates intensive computational resources when applied to large-scale, high-dimensional real-world datasets. For instance, naive use of sampling-basee because ECTS demands instantaneous evaluation of the conditional expectation on the fly (Wang) Scott 2019). Moreover, the lack of true LLRs, which are the sufficient statistic required for the backward induction and SPRT, further complicates their practical application within finite horizons.
methods, such Monte Carlo integration, is ineffective
Thus, we propose the Flnite-horizon average a posteriori Risk Minimizer for optimal BOUNDary (F (FIRMBOUND), framework designed to estimate the solution to (i) the backward induction and (ii) the sufficient statistic, with theoretical guarantees. For estimating the backward induction, we offer two approaches: first, recognizing the concave nature of the conditional expectation, we formulate its functionn estimation as convex function learning (CFL) to provide a statistically consistent estimator, Second,
due to the high training costs of CFL (Siahkamari al. 2022). we explore faster alternative using Gaussian process (GP) regression (Hensman et al.) 2013). Although it can compromise on statistical consistency, GP regression is trained 30 times faster than CFL with comparable performance. Both CFL and GP regression models offer low deployment overhead during the test phase, making them suitable for real-time ECTS. To address the absence of the sufficient statistic (i.e., true LLRs), F FIRMBOUND integrates a sequential density ratio estimation (DRE) algorithm (Ebíhara et al. 1021 handle both i.i.d. and non-i.i.d. time series of any class size, producing statistically consistent LLR estimates, on which the optimal decision is learned (Fig. D.cc.
Our extensive experiments demonstrate that F FIRMBOUND effectively approaches Bayes optimality (i.c., minimizes the AAPR) and delincates the Pareto-optimal points (meaning "optimal in the speed- accuracy multi-objective optimization problem")) of the speed-accuracy tradeoff (SAT). In contrast to most existing ECTS methods, which lack theoretical guarantees (Gupta et al.) 2020). F RMBOUND significantly outperforms these baselines with less parameter sensitivity, substantiating the theoretical predictions across a wide range of synthetic and real-world datasets: two- and three-class sequential i..d. Gaussian datasets, non-i.i.d damped oscillating LLR (DOL) datasets, and real-world datasets such as Spoofing in the Wild (SiW) (Liu et al. 2018b), the human motion database HMDB51 (Kuehne jet al., (). the action recognition dataset UCF101 (Soomro et al., 2012), and FordA from UCR time series classification archive (Dau et al.
2018 Moreover, FIRMBOUND often achieves lower
2

---

Published as a conference paper at ICLR 2025
(al Estimated a posterfori risk at time stepm48 (b) Learned optimal boundary for two-class test [c] Learned optimal boundary for three-class test
Class 1 sufficient statistic
Prajectory of input sequence
50
Decision boundary
CCCSS
continuation risk
Stopping risk
Decision
20
estimated with GP
and confilence
estimated
Class trajectory
class
Cless 1 trajectory
0.6
Class trajectory
posterior
04
Log licelihood ratio
trajectory of input sequence
Cisss
Class posterlal
10
20
30
50
Time steps
Figure 2: Learning Decision Boundaries. (a) Estimation of the continuation risk function G. Convex Function Learning (CFL) and Gaussian Process (GP) regression Gaussian dataset are used. The decision boundary at the current time step (= 48) is defined by the intersection of & and the stopping risk function G*t (Thm. 2.1 (b, c) Decision boundaries (thresholds) derived from a two-class (b) and three-class(t) sequential Gaussian dataset.
two-class sequential
error rate than SPRT with static thresholds, illustrating its ability to advance the tradeoff boundary to discover new Pareto fronts (see Fig. [p). Importantly, empirically show that FIRMBOUND reduces decision-time variance even when it does not advance the Pareto front, contributing to reliable decision making, which is crucial for practical applications. In summary, our contribution is threefold:
1. Statistically consistent and computationally efficient estimation alternatives of the optimal decision boundaries of SPRT for ECTS within finite horizons.
2. Comprehensive data handling under real-world scenarios, being capable of processing both i.i.d. and non-i.i.d. data series, and both binary to multiple, large class datasets.
3. Pareto-optimal decision making with an ability to identify potential new Pareto fronts and reduce variance of decision making time.
A comprehensive literature review can be found in App. D
2 PRELIMINARIES NOTATIONS AND SPRT
We provide informal definitions here due to page limitations. Detailed mathematical foundations are provided in App. A and Tartakovsky et al. (2014). Let ( == {ax(t)) Yt= and y E [K] == {1....) K} random variables that represent an input sequence with length i E [T] and class label, respectively, where x((') E di is a feature vector, and T E N is the fixed maximum length of sequences, or the finite horizon. (1.1) and y follow the joint density p( ((X)))))))) y)) Their (t')
samples denoted by x(11t) : (amhn) } and you [K] (1,... K} consist of a dataset, where m E [M], and M E N is the dataset size. The log-likelihood ratio (LLR) contrasting class & E [K] and 1 E [K] is defined as ATT(T) = (x = log(p( log(p(X((.TT) (xI.T) = k) p))p(xX(1.1) ly = 1)).
The posterior of class k E [K] given ((1))) is denoted by T (X.))) == p(u = (1.0). Let
de (1.6) + de (X((1))) E [K] and T (1.2)) + ((x(1)))) E [T] denote the terminal decision rule (i.e., class predictor) and stopping time (i.e., decision time or hitting time) of the input sequence, respectively. The terminal decision rule may not depend on f. in which case we omit the subscript t. The stopping time may not require the whole sequence (I,T) and may be able to calculate from the first / samples (1.1), depending its algorithm. Our task to construct the terminal decision rule {de hej which will turn out to be time- lime-indpenndet, and the stopping time that are "optimal" and can be computed efficiently.
Sequential probability ratio test (SPRT). Our model is based SPRT:
Definition 2.1 (SPRT). Given the thresholds a E R (k E [K] and t E (T) for LLRs of input sequences, SPRT is defined as a tuple of iene-independent ferminal decision rule and stopping time,
3

---

Published as a conference paper at ICLR 2025
Forward estimation of log likelihood retio distributions
Time
Continuation risk
[+)
3
Av-1
Conditional expectations estimeted with GP/CFL
kellheed
min
Gr ir G7 G7
1r--2
Time samples
Risk at: time f
Riak at time 12 > 41
Backward induction
min Gr-z
C7-2 Dm-
Estimated optimal
Stopping ASK
decision boundary
Figure 3: Conceptual figure of FIRMBOUND. (a) The intersections of G and G delineates the decision boundary. (b) FIRMBOUND estimates conditional expectations using either GP or CFL, based on available sufficient statistic such as (estimated) posterior probabilities or LLRs X.
denoted by 8 = , TT), such that
d' d'((i.T)) = d" (x E arg max min (x(ee))))) -66 ((= (1)
kE(K] [(())E[K]
= -x((x))))) min(t E [T]
max {
min (x((00)))) dz 2 0}
(0)
(2)
kE[K] ((*R)E[K]
This algebraic definition may seem complex, but the graphical descriptions are given in Figs. I & Note that the terminal decision rule (Eq. [ is equivalent to choosing the argmax the gaps between the class posteriors and the thresholds w.r.t. & E [K] at the stopping time, i.c., choosing the most likely class.
A key feature of SPRT is its various optimalities pptimalitissasymppoooti asymptotic, aon-asymp,, and Bayes- theoretically establish SPRT as the best model for ECTS. In this paper, we exploit the Bayes optimality, with the other optimalities summarized in App. B
To define the Bayes optimality of SPRT, we introduce the sufficient statistic, a posterior risk (APR), and average APR (AAPR). The sufficient statistic for sequential tests here means P (x.())))) (or equivalently, we can use H == ing all necessary information for decision at & and serving as the fundamental variable in SPRT's optimality instead of (1.E) (see also App. C foor the formal definition). Then, for given d,, APR at t E (T] is defined as
interchangeably), provid-
(3) where c E R2o is a sampling cost, and Lg is the k-th element of a penalty vector E R.K with k E [K], which penalizes incorrect classifications of d.- The average APR (AAPR), or the Bayes risk, for (dehe)) and is defined as
((( k)
(1 (x( =) L1 + c
20
(AP
SPRT is Bayes optimal in the sense that it can provide a terminal decision rule and stopping time that minimize AAPR if the thresholds for L.RSs are properly chosen. The following theorem provides how compute the optimal thresholds achieve the Bayes optimality (Arrow et al. 1949 Tartakovsky
ct al. 2014).
Theorem 2.1 (Backward induction equation). Let St be (I1 (X(11)) ..... R xx (X(1,0)) w.l.o.g.
8* is Bayes optimal if fime-dependent thresholds og in Eqs. 2 are given by the intersections of the continuation risk function G. and the stopping risk function G (Ft), which are defined
for a dre-ned density p. not for each sample of x (1I.T), and satisfy the following backward induction equation:
G.(.)) = [Griin (f++1))++ [ tc G (ft) = min [o(( - Fu (x((111)))
(5)
(6)
4

---

Published as a conference paper at ICLR 2025
where G (F) is referred as the minimum risk function:
Ga (At) (*) min (F) (LSt<T).
(t=T)
(7)
Therefore, the optimal stopping region is (X(1))()))) ,.... (xx G((A)) RKXT A similar theorem holds for T (Au(( (R.E(K)) rewriting (xE()))))))(( by (>a(X0.1)))xEE1)))
G*)
The formal proof is provided in Tartakovsky al. (2014). For intuitive explanation, see App.
This theorem indicates that the optimal stopping time is given by ('((()7)) = =x'(X(rr)) minst E (7) G7 I Gx(P)) and that the optimal terminal decision rule simplifies to d' (X(()))) d' (X(L*)) arg min (Lx(1 n (X(2.))) | -(((())) Note that an
explicit formula of the dynamic threshold (t) as function of the sufficient statistic Pt is unnecessary to compute d' and T* (Figs. 2 b, and 33 serve only for visualization). Note also that once the optimal stopping region is determined, calculating 7" longer require backward computation each time sequence arrives because G and G. are defined for the underlying density, not for individual sample sequences.
FIRMBOUND
Unfortunately, solving and deploying 5 in real-world scenarios presents significant challenges. First, these equations lack closed-form solutions. A naive numerical computation, such as Monte Carlo integration, would possible, but suffers from the curse dimensionality (K can > 100, requiring an exponentially large number of samples for convergence) (see also App. D Second, obtaining a well-calibrated sufficient statistic 9 is challenging. Although computing softmax logits class posteriors is common in classification problems (He al. 2016a b Krizhevsky et al. 2012) LeCun et al. 1998), high-dimensional classifiers often produce overconfident or miscalibrated outputs
(Guo et al.) 2017 Melotti et al.) 2022 Müller et al. 2019 Mukhoti al. 2020).
We address these challenges by transforming the backward induction into a pair of estimation
problems and providing statistically consistent estimators (Secs. 3.1 & 3.2). Our proposed model, FIRMBOUND, is then proved to be statistically consistent with the Bayes optimal solution (Thm. 3.2)
3.1 ESTIMATING THE CONDITIONAL EXPECTATION
The first key idea is to transform the computation of the conditional expectation in the backward induction equation into regression problem. An important observation is that the conditional expectation function in Eq. 5 concave (Jarrett & van der Schaar 2020 Tartakovsky et al. 2014):
Theorem 3.1. G. and Gmin are concave functions of vector (TT (T, ..... TK Tx( for all t e [T].
Equipped with the concavity, propose build consistent estimator of the Eq. Jhouuhh convex function learning (CFL).
CFL. CFL aims to build statistically consistent estimator of convex function from noisy data points, assuming the target function is inherently convex (Argyriou et al. 2008 Bach] 2010:: Bartlett et al. 2005 Boyd & Vandenberghe 2010; Mendelson 2004). Assume that we have estimates of the sufficient statistic .9, for all t E [T' estimated on a given training dataset { ((x(!-T) ym M via the algorithm given in Sec. 3.2 Then, task toward solving the backward induction equation (Eq, 7 is estimate (st(( (f)) and (.9) for all t [T). G can be computed from the estimated sufficient
statistic via Eq. 6 Thus, focus the continuation risk (( (G
To
5

---

Published as a conference paper at ICLR 2025
estimate it from the estimated sufficient statistic, first rewrite G₁ as
((()))))))) E x (x -x + (8)
/ (XP(Xit))xx0 =x -x (= (+ +
(9)
G (X (x(()t))) (0 +c =: = (t) + C,
(10)
where g!(+1) == (X
is a properly defined probability measure, and d00
is random variable representing the deviation of (g(t1)) from the expectation integral in Eq. Suppose that the backward induction equation is solved for T, 1, 1,...,t 1; i.e.,. G is given.
Then, gll+1) is computable from the estimated sufficient statistic by definition. Therefore, we regard {9 Im.e as a given dataset henceforth, leading to the idea that the dataset ( Im. can be regarded as a set noisy observations of the ground truth continuation risk (Xxmm))))) of (111)) (up to constant c) because ( = (((+1) - (0) + (Eq 10 +
g(++1) (X + cm
(11)
This change of view, together with the fact that (. ) is concave w.r.t Sr = (T....., ...,,,,k), leads to the following noisy convex regression problem:
((X((TT)) Im=1) E arg min
Σ (I(((X()))) -g(e)2 X|| +c, (12) M
fononcave
where || is a regularizer, a hyperparameter, and (((()))) Jm.) denotes the continuation risk estimated (9th mm, ) or, equivalently, ( 1m= With this novel reformulation, we employ an efficient solver, the 2-block Alternating Direction Method of Multipliers (ADMM) algorithm integrated with the augmented Lagrangian method with concavity constraint (Siahkamari al.) 2022). Specifically, f in Eq. 12 is represented as a piecewise linear function, and [[]] is defined as the Ltt penalty terms (see App. G for the complete algorithm).. This algorithm is known converge
to the ground truth function as M + 50; i.e., it is consistent (Siahkamari et al. 2022).
Consequently, given the estimates of the sufficient statistic, now have the estimates of the continuation risks G, and the stopping risks Gt functions of S, for all E [7]. Therefore, in the
test phase, we can compute the optimal stopping region given in Thm. 2.1 for any P9t and i E [T] without ro-solving the backward induction equation.
Gaussian process (GP) regression. Although the aforementioned CFL algorithm is theoretically sound and computationally tractable, we further propose a more computationally efficient estimator using GP regression. GP regression is a Bayesian approach to regression used for probabilistic predictions, assuming the objective function values follow a Gaussian distribution defined by a covariance kernel (Wang) 2020).
Evaluating the conditional expectation, or the continuation risk, (x9+ [P. ] at any P and t E (T) is formulated below (we omit inducing points here for brevity). Suppose that set of estimated is given. We begin with
sufficient statistics at any E [T]. denoted by {.9t. := (x(x!"))) rE(T]] [M
our reformulation discussed above (Eq.
g(++)) + c= G.(F (t)
We make the following fundamental assumptions of GP regression. First, the observation noise (0) for any 1. E [T] and m E [M] follows Gaussian distribution. Second, (G, t. mE[M] for any t E [T] forms Gaussian process. Under these assumptions, Eq. 11 can be regarded as GP regression problem with the latent function G., the explanatory variable Stm., and the response
variable (g(++) + Therefore, the predictive distribution of the continuation risk can be calculated, using the standard methods for the evidence lower bound (ELBO) maximization. Specifically, use the variational GP with an inducing point method (Hensman et al.) 2013) Matthews 2017) via minibatch training maximize the ELBO.. This algorithm uses standard functions from GPyTorch

---

Published as a conference paper at ICLR 2025
SPRT-TANDEM
CFL/
X (1.4)
DRE
XO.0
Backward induction
Training
DRE models
Save CFUGG models
Load BAAAAE..........................
Creeaaaaaaa Load weights
DRE
XOL0
Evaluate G, and G
Stop or continue?
Test
Figure 4: Training and Testing. (Top) the training phase, the sequential DRE algorithm SPRT- TANDEM is trained, followed by the training of CFL or GP models using the backward induction. (Bottom) In the testing phase, the trained DRE model is loaded to sequentially update the LLRs, with which the trained CFL/GP model calculates G. and compares it with G to make decisions at time
(Gardner et al. 2018 D. For implementation details, see our code. For further detailed mathematical foundations of GP regression, see App. H
Together with the estimated sufficient statistics, the predictive distribution thus obtained provide G and G. for any St and E [7]. Therefore, in the test phase, we can compute the optimal stopping region given in Thm. 2. for any S and E [T) without re-solving the backward induction equation. We empirically validate that the training (sometimes referred to as inference in the Bayesian context) with GP regression is 30 times faster than the CFL training.
3.2 DENSITY RATIO ESTIMATION (DRE) FOR ECTS
Our remaining task is estimate the sufficient statistic S, for all I [T], the second estimation problem mentioned at the beginning of Sec. 3 A simple approach to this end is to estimate I.L.s via a sequential density ratio estimation algorithm. It enhances precision by estimating the ratio of probabilities directly, rather than estimating each probability independently. thus reducing degrees of freedom (Belghazi al. 2018 Gutmann & Hyvärinen] 2012, Hjelm al. 2019 Liu et al. 2018a Moustakides & Basioti 2019 Oord et al. | (Sugiyama et al. [2100] 2008 2012). Specifically, we
employ SARDEA algorithm (Ebihara et al.] [201]] Miyagawa Ebihara [202] Ebiiara et al.)
2023 which involves consistent loss function, named Pog-Sum-Exyy Loss (LSEL):
L. (wr; (((())) you (mm)))))))
KM ΣΣ KE(K] 1ET
1 Mr
log(1 +
Σ [(F))[[K]
vEle
(13)
where w E Rd is the trainable parameters, c.g., the weights a neural network, 43 := (i e [M] = k} is the index set of class k. M₂ == /& is the size of /t, and λs(w, X is the estimated LLR parameterized by w. By minimizing LSEL, the estimated LLRs approaches the true LLRs as M + oc (Miyagawa & Ebihara 2021 i.c. LSEL is consistent. We provide further details of SPRT-TANDEM App.
Finally, integrating CFL and LSEL and solving the backward induction equation, we establish that FIRMBOUND is statistically consistent.
Theorem 3.2 (Informal). Under several technical assumptions, FIRMBOUND with CFL is statistically consistent with the Bayes optimal algorithm for ECTS; i.e., it minimizes AAPR as M - co.
Main assumptions are (i) sufficiently large dataset size, (ii) a sufficiently large number of iterations of the ADMM algorithm in CFL, and (iii) sufficiently large neural network for LSEL. The complete set of assumptions, the formal statement, and the proof are provided in App. [ they are technical and lengthy. In the following, we empirically validate Thm. 3.2 demonstrating that F FIRMBOUND minimizes AAPR, and highlight its practical strengths of F FIRMBOUDD across various datasets.
EXPERIMENTS AND RESULTS
These experiments designed for fair comparison with baseline models without exploring all possible configurations, as such variations would not alter our study's 's conclusion. To ensure fairness, the same feature extractor and feature vector size dret used across all models. All
7

---

Published as a conference paper at ICLR 2025
Noo-cless i.dd Geussian
(B)
chase-dlass lid. Gaussian
[c)
Demped oscillating noniid. LURs (DOL)
Avenage posterior risk
10
20
30
50
40
Average 3 posttton 1ax
6.5
2.4
22 0.
* c 1.22
0.11./7'
SIW
FIRMBOUND ICFLI estimated ?.
FIRMBOUND (CFL)
on true S
HMDB51
2L,TT
0.17/T
Vanilla SPRT
Vanila SPAT
15
0.2
UCF101
* 21.7P
* OT
L/T
on true 2
FIRMSOUND (GP)
12/Z T (APDEM)
estimated LLRs
21
L/7
FIRMBOUND (GP) estimated
D.LL,T
Mean hitting time (aframes)
30
50
10
40 Mean hifting time (rrmmes)
20
Mean hitting Time (atrammes)
Figure 5: Averaged posteriori risk (AAPR) curves. AAPRs of FIRMBOUND compared with static-threshold SPRTs. Horizontal and vertical axes are mean hitting time and AAPR, respectively. Note that we only show models with well-calibrated sufficient statistic here, as ill-calibrated statistic does not necessarily correlate with ECTS performance by definition and thus not meaningful dis- cussing its minima (but see App. M for AAPR of other baseline models). Error bars represent the standard error of the mean.
hyperparameters, including those for the baseline models, are optimized using Optuna (Akiba et al. 2019) with the Tree-structured Parzen Estimator (Bergstra et al.] (01T). Details parameter selection can be found in App. K Additional parameter sensitivity test on GP models can be found in App. L
showing robustness against kernel choice. Fig. shows The training and testing pipeline.
Baselines. We evaluate the performance of FIRMBOUND by comparing it against SPRT with static thresholds and four ECTS models. To conduct SPRT on real-world datasets lacking true LLRs, we
utilize SPRT-TANDEM (Ebihara et al., 2021 Miyagawa & Ebihara [022] Ebihara et al. (023) esti- mate LLRs. ECTS baseline models include: LSTMms, which enhances monotonic score growth (Ma) al. 2016 the reinforcement learning algorithm EARLIEST (with two fixed hyperparameters lambda=10-1 and 10 10-10) (Hartvigsen et al. 2019). the convolutional neural
hybrid, TCN-Transformer (TCNT, with two fixed hyperparameters a 0.3 and 0.5) (Chen et al.)
2022), and Calibrated eArly tIMe sERies clAsifier (CALIMERA, with fixed hyperparameters, delay
penalty= 0.1, 0.0. (Bilski & Jastrzębska 2023)
Evaluation criteria. Our evaluation metrics are AAPR and SAT curve. We compute APR at the decision time using softmax probabilities as class posteriors, with fixed L, = I. = 10 for all [K] and up to three variations of E {L/T,2L/T, 0. 5). where e = L/T is set such that the two terms in APR (Eq. 3 are of comparable magnitude. We do not vary L because decision boundaries are invariant to the scaling of L and e (see App. N for the proof). The SAT curve is derived from the averaged per-class error rate (i.e., macro-averaged recall) measured at the stopping time (Fig. 6).
CFL. CFL model is trained at each time step to estimate the conditional expectation (Eq, Zp. utilizing custom training routine adapted from (Siahkamari et al. 2022). We optimize hyperparameters by randomly sampling 1,000 sequential data points. This process is repeated 30 times to identify the hyperparameters that minimize mean squared error using Optuna (Akiba al. 2019). Once hyperparameter is set, we sample 5,000 sequential data points to model the conditional expectation curve with 5 epochs of training. The requirement of convex function over finite input space lets us use posteriors TR (xx(l:)) as the sufficient statistic Pt. Training on a two-class sequential Gaussian dataset (details provided below) takes approximately 10 hours on NVIDIA RTX 2080Ti.
8

---

Published as a conference paper at ICLR 2025
Two-class iid. Geussian
[B]
Three-class Lid. Coussian
[c]
Damped asciliating non-i..dd LLRs (DOL)
Moan par-class arror rale (%0
19
x L/T
0.1./TT
FIRMBOUND (CFL)
trae
Vanilla SPRT on estimated
Vanilla SPRI on true LLRs
22
20
FIRMBOUND (CFL)
LLRS (SPRE-IANDMM)
0.11/7
estimated.71
20
2
FIRMBOUND KGP)
30
0.I.,T
10
0. T.
on est estimated,
FIRMBOUND (GP)
12
X
10
40
20
20
SIW
HMDB51
UCF101
geo.
LSTMms
EARUEST
12
305
TCNTransformer
13
0.0
0.4
5.0
Moan hitting time (#trames)
Mean Fitting time (Ptrames)
Mean hitting time (atrames)
The performance of ECTS is evaluated through SAT curves. The horizontal axis represents the mean hitting time, while the vertical axis shows the averaged per-class error rate, equivalent to macro- averaged recall. Thus, models closest to the bottom-left corner perform best. Error bars represent the standard error of the mean.
Figure 6: Speed-Accuracy Tradeoff (SAT) Curves.
(8)
AAPIL zurve Clac-cless Eauastent
1b1
SAT curve Itro-ciass Gettelan))
4.5
5.0
5.3
rode
40
30
Unifoomly random hitting time
L/T
L/T
FIRMBOUND (CFI) on true 3/,
on true 3
FIAMBOUND (GP)
0
Tapering power. function bireshold
2.5
Vanilla SPRT LLRs
2.0
10
30
60
50
10
20
30
40
50
Mean fatning time [eframme)
Mcan nitting (Ntramcs)
Figure 7: Additional ablation tests. Random hitting time and artificial tapering thresholds evaluating (a) AAPR curve and (b) SAT curve. The artificial thresholds start with three different magnitude at
t = 1, gradually tapering zero approaching the horizon / = T. See App. O for details.
GP regression. GP model is trained at each time step same CFL. Models trained for 30 epochs with a batch size of 2,000 with 200 randomly selected inducing points. Our empirical comparisons indicate that either LLRs posteriors can serve as the sufficient statistic Pt. yielding similar results (App.C)) In subsequent analyses, we use LLRs for synthetic data and opt for posteriors for data because of their lower dimensionality. Training on a two-class sequential Gaussian dataset (details provided below) typically requires approximately 20 minutes on NVIDIA RTX 2080Ti.
Ablation tests. To assess the impact of different stopping rules, we conducted ablation tests using LLRs. The primary baseline is SPRT with static thresholds on estimated LLRs. as shown Figs. and 6 Additional tests are random stopping times to establish a chance level and monotonically descending decision boundaries generated using power function (see App. O details). Neither variant surpassed FI RMMBOND in terms of AAPR or SAT (Fig. 7 The datasets used in these experiments are detailed below.
Dataset: sequential i.i.d. Gaussian datasets with known LLRs. Preliminary assessments are conducted on sequential Gaussian datasets to find that FIRMBOUND can minimize APR to achieve Pareto-optimal both with ground-truth and estimated LLRs. Let po (x). Pi (x). and p2 (æ) be the 128- dimensional Gaussian densities with identity covariance matrix. The mean vectors are defined as (0.5,0. O, 0), (0, 0.5, O.... 0), and (0, O, 0.5, .... 0) for Pu (x), Pı (æ), and Pa (x). respectively. Only Po(x) and p1 (z) used for the two-class dataset. We randomly sampled sequences of length T 50 from these Gaussian distributions to form the datasets. The sizes of the training, validation, and test datasets are as follows: for the two-class dataset, 80,000, 2,000, and 80,000 samples respectively; for

---

Published as a conference paper at ICLR 2025
the three-class dataset, 60,000, 6,000, and 120,000 samples respectively. SPRT-TANDEM is trained with the sampled vectors to provide estimated LLRs. Fig. [5h b 6n, shows that F FIRMBOUND effectively minimize AAPR to reach the best speed-accuras tradeoff given a sampling cost.
Dataset: sequential non-i.id. Damped- -siiildtisiilllaiing LLRs (DOLs). We explore the potential for mitigating early inadvertent error find a new Pareto-front (Fig. D Nonlinear two-class LLRs ((t) of length 50 are generated as A() = y(
t/T))xp(re) A exp( sin(wt) +N(00, o).
where y E {-1, } denotes the class label value towards which the first term converges, the second term introduces damped oscillation, and the third term represents Gaussian noise. The dataset generated using parameters Ki A, B, w, and a, chosen from predefined parameter space. This results in 20,000 training samples, 2,000 validation samples, and 80,000 test samples. For additional details on LLR trajectories and dataset parameters, see App. P Fig. 6 demonstrate that F FIRMBOUND achieves notably low errors, effectively advancing the Pareto-front to a new optimal level.
Dataset: real-world datasets for ECTS. Four datasets used: SiW (two-class) (Liu al. 2018b), HMDB51 (51-class) (Kuehne et al. 2011). UCF101 (101-class) (Soomro et al. 20 22) and FordA dataset (Iwo-class) (Dau et al. 2018). For the SiW dataset, a ResNet-152 (He al. 2016a b) is trained as feature extractor to generate 512-dimensional feature vectors for each frame. The pretrained Microsoft Vision Model ResNet5(] without fine-tuning, used to extract 2048-
dimensional feature vectors from the HMDB51 datasets. The pretrained vision transformer DINOv2 (the largest model without distillation) with registers (Dosovitskiy al., 2021| Oquab al., 2024 Darcet et al. 2024) is used to extract 1 1,538- 1338-dimensional feature vectors from UCF101 datasets. The dataset sizes and sequence lengths are as follows: SiW comprises 46,729 training. 4,968 validation,
and 43,878 test samples, all with a sequence length of T 50; HMDB51 includes 5,277 training, 519 validation, and 2,434 test samples with T = 79; UCF101 consists of 35,996 training, 4,454 validation, and 15,807 test samples, each with T = 20. Figs. Fig.. and 6f that FIRMBOUND reaches Pareto-front by minimizing AAPR, and extend the frontier in a few datasets. FordA is used experiment non-vision modality dataset, presented in App. Q showing the same trend.
Reducing the variance of hitting time. Although F FIRMBOUND consistently identifies the Pareto- optimal point, it does not always show performance gains compared with the vanilla SPRT. However, the variance of the hitting time is statistically significuntly smaller across the database (Tab. [ Wilcoxon signed-rank test, p = 2.00 x 10- < 0.001), demonstrating F FIRMOUUDDS 'ss advantage in reducing the variance of hitting time to enable reliable decision making across data.
Table 1: Mean variance of hitting time (MVHT), FIRMBOUND with CFL provides smaller variance of hitting times than vanilla SPRT when evaluated at the same mean hitting time and corresponding macro averaged recall. The variance reduction is statistically significant (see main text).
Dataset
Gauss2est.
GaussBest.
DOL
Siw
HMDB
UCF101
FordA
Trial repeats LMVHT, vanilla SPRT with static threshold JMVIIT F IIMBOUND with CFL Difference MVHT
3
5
6
10
2
10.47
44.02
489.89
2.87
199.31
0.55
32.15
9.01
42.78
405.78
1.97
195.35
0.53
23.39
1.45
1.24
84.11
0.90
3.97
0.017
8.76
(positive is better)
5 CONCLUSION
With two statistically consistent estimators for backward induction and the sufficient statistic, FIRMBOUND delineates stable Pareto fronts across diverse datasets. Unlike existing ECTS mod- els, which lack theoretical guarantees and are sensitive to hyperparameters and datasets (l-) FIRMBOUND consistently achieves optimal performance with reduced hitting time variance, ap- proaching optimal performance for ECTS in real-world scenarios. For further discussion, see App
10

---

Published as a conference paper at ICLR 2025
REFERENCES
T. Akiba, S. Sano, T. Yanase, T. Ohta, and M. Koyama. Optuna: A next-generation hyperparameter optimization framework. In KDD, pp. 2623 2623-263) 2631, 2019.
B. Amos, L. Xu, and J. Z. Kolter. Input convex neural networks. In International Conference Machine Learning, 2016.
A. Argyriou, T. Evgeniou, and M. Pontil. Convex multi-task feature learning. Machine Learning, 73: 243-272, 2008.
K. Arrow, D. Blackwell, and M. A. Girshick. Bayes and minimax solutions of sequential decision problems, Econometrica, 17:213, 1949.
R. Bach. Structured sparsity norms through submodular functions. In Neural Information Processing Systems, 2010.
L. Bartlett, O. Bousquet, and Mendelson. Local rademacher complexities. Annals of Statistics, 33:1497-1537, 2005.
M. I. Belghazi, A. Baratin, S. Rajeshwar, S. Ozair, Y. Bengio, A. Courville, and D. Hjelm. Mutual information neural estimation. In International Conference Machine Learning, pp. 531-540, 2018.
Bergstra, R. Bardenet, Y. Bengio, and B. Kégl. Algorithms for hyper-parameter optimization. In J. Shawe-Taylor Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 24, pp. 2546-2554. Curran Associates, Inc., 2011.
J. M. Bilski and A. Jastrzebska. Calimera: A new early time series classification method. Information Processing & Management, 60(5):103465 2023. ISSN 0306-4573.
S. P. Boyd and L. Vandenberghe. Convex optimization. ArXiv, abs/2106.01946, 2010.
H. Chen, A. Tian, Y. Zhang, and Y. Liu. Early time series classification using ICN-transformes 2022 IEEE 4th International Conference Civil Aviation Safety and Information Technology (ICCASIT), pp. 1079-1082, 2022.
Cheng, Y. Chen, Q. Zhang. I.. Gan, and M. Liu. Real-time trajectory planning for autonomous driving with Gaussian process and incremental refinement. 2022 International Conference on Robotics and Automation (ICRA), pp. 8999-9005, 2022.
Y. Chow, H. Robbins, and D. Siegmund. The Theory of Optimal Stopping. Dover books on advanced mathematics. Dover, 1991. ISBN 9780486666501.
T. Darcet, M. Oquab, J. Mairal, and P. Bojanowski. Vision transformers need registers. In The Twelfth International Conference on Learning Representations, 2024.
H. A. Dau, E. Keogh, K. Kamgar, C.-C. M. Yeh, Y. Zhu, S. Gharghabi, C. A. Ratanamahatana, Yan- ping, B. Hu, N. Begum, A. Bagnall, A. Mueen, and G. Batista. The UCR time series classification archive, October 2018.
R. Doná, G. P. R. Papini, and G. Valenti. MSPRT action selection model for bio-inspired autonomous driving and intention prediction. In IROS, 2019.
A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, Minderer, G. Heigold, Gelly, J. Uszkoreit, and N. Houlsby. An image is worth 16x words: Transformers for image recognition scale. In The International Conference on Learning Representations (ICLR), 2021.
A. F. Ebihara, T. Miyagawa, K. Sakurai, and H. Imaoka. Sequential density ratio estimation for simultaneous optimization of speed and accuracy. In The International Conference on Learning Reprexentations (ICLR), 2021.
11

---

Published as a conference paper at ICLR 2025
A. F. Ebihara, T. Miyagawa, K. Sakurai, and H. Imaoka. Toward asymptotic optimality: Sequential unsupervised regression density ratio for early classification. IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 1-5, 2023.
J. Eckstein. Augmented lagrangian and alternating direction methods for convex optimization: A tutorial and some illustrative computational results. 2012.
R. S. Evans, K. G. Kuttler, K. J. Simpson, S. Howe, P. F. Crossno, K. V. Johnson, M. N. Schreiner, J. F. Lloyd, W. H. Tettelbach, R. K. Keddington, A. Tanner, C. Wilde, and T. P. Clemmer, Automated detection of physiologic deterioration in hospitalized patients. J Am Med Inform Assoc, 22(2): 350-360, Mar 2015.
D. Gabay and B. Mercier. dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers & Mathematics With Applications, 2:17-40, 1976.
R. Gardner, G. Pleiss, D. Bindel, K. Q. Weinberger, and A. G. Wilson. GPy GorTo Blackbox matrix- matrix Gaussian process inference with GPU acceleration. In Advances in Neural Information Processing Systems, 2018.
M. Ghalwash, V. Radosavljevic, and Obradovic. Utilizing temporal patterns for estimating uncertainty in interpretable early decision making. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '14, pp. 402-411, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 978 450329569.
R. Glowinski and A. Marroco. Sur l'approximation, par éléments finis d' ordre un, et la résolution, par pénalisation-duallté d' une classe de problèmes de dirichlet non linéaires. 1975.
J. Gonzalvez, E. Lezmi, T. Roncalli, and J. Xu. Financial applications of Gaussian processes and bayesian optimization. Econometric Modeling: Capital Markets Asset Pricing eJournal, 2019.
M. P. Griffin and J. R. Moorman. Toward the early diagnosis of neonatal sepsis and sepsis-like illness using novel heart rate analysis. Pediatrics, 107(1):97-04, Jan 2001.
R. Grinold. Finite horizon approximations of infinite horizon linear programs. Mathematical Programming, 12:1-17,00 01 1977.
C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger. On calibration of modern neural networks. In Proceedings of the 34th International Conference Machine Learning Volume 70, ICML'17, pp. 1331- JMLR.org, 2017.
A. Gupta, H. P. Gupta, B. Biswas, and Dutta. Approaches and applications of early classification of time series: A review. IEEE TAI, 1(1):47-61, 2020.
M. U. Gutmann and A. Hyvärinen. Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics. The journal of machine learning research. 13(1): 307-361, 2012.
T. Hartvigsen, C. Sen, X. Kong, and Rundensteiner. Adaptive-halting policy network for early classification. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, KDD '19, pp. 101-110, New York, NY, USA, 2019. ACM.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016a.
K. He, Zhang, Ren, and Sun. Identity mappings in deep residual networks. In Computer Vision ECCV 2016 14th European Conference. Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part IV, pp. 630-645, 2016b.
J. Hensman, N. Fusi, and N. D. Lawrence. Gaussian processes for big data. In Proceedings of the Tinth Conference on Uncertainty in Artificial Intelligence, UAI' 13, pp. 282-290, Arlington, Virginia, USA, 2013. AUAI Press.
12

---

Published as a conference paper at ICLR 2025
J. Hensman, A. Matthews, and Z. Ghahramani. Scalable variational Gaussian process classification. In G. Lebanon and S. V. N. Vishwanathan (eds.), Proceedings of the Eighteenth International Conference Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pp. 351-360, San Diego, California, USA, 09-12 May 2015. PMLR.
H. Herfurth. Gaussian process regression in computational finance. 2020.
R. D. Hjelm, A. Fedorov, S. Lewoic-Marchildon K. Grewal, P. Bachman, A. Trischler, and Y. Bengio. Learning deep representations by mutual information estimation and maximization. In International Conference on Learning Representations, 2019.
S. Huang. Surrogates: Gaussian process modeling. design, and optimization for the applied sciences. Journal of Quality Technology, 53:440 441, 2020.
K. Jakkala and S. Akella. Multi-robot informative path planning from regression with sparse Gaussian processes. ArXiv, abs/2309.0700 0900000, 2023.
D. Jarrett and M. der Schaar. Inverse active sensing: Modeling and understanding timely decision-making. ArXiv, abs/2006. 14141, 2020.
A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 60:84 90, 2012.
H. Kuehne, H. Jhuang, E. Garrote, T. Poggio, and T. Serre. HMDB: large video database for human motion recognition. In 2011.
2011.
R. D. Labati, A. Genovese, E. Muñoz, V. Piuri, F. Scotti, and G. Sforza. Biometric recognition in automated border control: A survey. ACM Comput. Surv., 49(2). jun 2016. ISSN 0360-0300.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proc. IEEE, 86:2278-281 2324, 1998.
Q. Liu, L. Li, Z. Tang, and D. Zhou. Breaking the curse of horizon: Infinite-horizon off-policy estimation. In Advances in Neural Information Processing Systems, pp. 5356-5366, 2018a.
Y. Liu, A. Jourabloo, and X. Liu, Learning deep models for face anti-spoofing: Binary or auxiliary supervision. In CVPR, June 2018b.
Ma, L. Sigal, and Sclaroff. Learning activity progression Istms for activity detection and early detection. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1942-1950, 2016.
A. G. D. G. Matthews. Scalable Gaussian process inference using variational methods. 2017.
G. Melotti, C. Premebida, J. J. Bird, D. R. Faria, and N. Gonccalves. Reducing overconfidence predictions in autonomous driving perception. IEEE Access, PP:1-1, 2022.
S. Mendelson. Geometric parameters in learning theory. 2004.
T. Miyagawa and A. F. Ebihara. for speed-accuracy optimization. In Proceedings of the 38th International Conference on Machine Learning, pp. 7792-7804, 2021.
The power of log-sum-exp: Sequential density ratio matrix estimation
U. Mori, A. Mendiburu, E. J. Keogh, and J. Lozano. Reliable early classification of time series based on discriminating the classes over time. DMKD, 31:233-266 2016.
G. V. Moustakides and K. Basioti. Training neural networks for likelihood/dennity ratio estimation. ArXiv, 055//9911.00405. 2019.
Mukhoti, Kulharia, A. Sanyal, S. Golodetz, P. S. Torr, and P. Dokania. Calibrating deep neural networks using focal loss. ArXiv, abs/2002.09437. 2020.
R. Müller, S. Kormblith, and G. E. Hinton. When does label smoothing help? In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché- A'uché-Buu, E. Fox, and R. Gamett (eds.), Advances Neural Information Processing Systemx, volume 32, Curran Associates, Inc., 2019.
13

---

Published as a conference paper at ICLR 2025
A. d. Oord, Y. Li, and O. Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv: 1807.0378, 2018.
M. Oquab, T. Darcet, T. Moutakanni, H. V. Vo, M. Szafraniec, V. Khalidov, P. Fernandez, D. HAZIZA, F. Massa, A. El-Nouby, M. Assran, N. Ballas, W. Galuba, R. Howes, P.-Y. Huang, S.-W. Li, I. Misra, M. Rabbat, V. Sharma, G. Synnaeve, H. Xu, H. Jegou, J. Mairal, P. Labatut, A. Joulin, and P. Bojanowski. DINOv2: Learning robust visual features without supervision. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
G. Peskir and A. Shiryaev. Optimal stopping and free-boundar problems, pp. 123-142. Birkhäuser Basel, Basel, 2006. ISBN 978-3-7643-7390-0.
D. Petelin, Sindelát, J. Prikryl, and J. Kocijan. Financial modeling using Gaussian process models. In Proceedings of the 6th IEEE International Conference Intelligent Data Acquisition and Advanced Computing Systems, volume 2. pp. 672-677, 2011.
Richter and M. Toledano-Ayala. Revisiting Gaussian process regression modeling for localization in wireless sensor networks. Sensors (Basel, Switzerland), 15:22587 01122557-2211,,,0 2015.
M. N. Shadlen, R. Kiani, W. T. Newsome, Gold, D. M. Wolpert, A. Zylberberg, J. Ditterich, V. de Lafuente, T. Yang, and J. Roitman. Comment on "Single-trial spike trains in parietal cortex reveal discrete steps during decision-making Science, (52(0)))): 1006, Mar 2016.
A. Siahkamari, A. Gangrade, Kulis, and V. Saligrama. Piecewise linear regression via a difference of convex functions. ArXiv, abs/2007 .2422222222222 2020.
A. Siahkamari, D. A. E. Acar, C. Liao, K. L. Geyer, V. Saligrama, and B. Kulis. Faster algorithms for learning convex functions. In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 20176-20194. PMLR, 17-23 Jul 2022.
K. Soomro, A. R. Zamir, and M. Shah. UCF101: A dataset of 101 human actions classes from videos in the wild. ArXiv, abs/1212.0402, 2012.
M. Sugiyama, T. Suzuki, and T. Kanamori. Density ratio estimation: A comprehensive review. RIMS Kokyaroku, pp. 10-31, 01 2010.
M. Sugiyama, T. Suzuki, S. Nakajima, H. Kashima, P. von Bünau, and M. Kawanabe. Direct impor- tance estimation for covariate shift adaptation. Annals of the Institute of Statistical Mathematics, 60(4):699 2008
M. Sugiyama, T. Suzuki, and T. Kanamori. Density Ratio Estimation in Machine Learning. Cambridge University Press, 2012.
H. Tao, M. M. Hameed, H. A. Marhoon, M. Zounemat-Kermani, H. Salim, K. Sungwon, S. O. Sulaiman, M. L.. Tan, Z. Sa' adi, A. D. Mehr, M. F. Allawi, Abba, M. Zain, M. W. Falah, M. Jamei, N. D. Bokde, M. Bayatvarkeshi, M. Al-Mukhtar, S. K. Bhagat, T. Tiyasha, K. M. Khedher, N. Al-Ansari, S. Shahid, and Z. M. Yaseen. Groundwater level prediction using machine learning models: A comprehensive review. Neurocomputing, 489:271-308, 2022.
A. Tartakovsky. Asymptotic optimality of certain multihypothesis sequential tests: Non-i..d. case. Stat. Inference Stoch. Process., 1:265-295, 1998.
A. Tartakovsky, Asymptotically optimal sequential tests for nonhomogeneous processes. Sequential Analysis, 17, 04 1999.
A. Tartakovsky, Nikiforov, and M. Basseville. Sequential Analysis: Hypothesis Testing and Changepoint Detection. Chapman & Hall/CRC, 1st edition, 2014.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polo- sukhin. Attention is all you need. In NeurIPS, volume 30, pp. 5998-6008, 2017.
E. Vats and C. S. Chan. Early detection of human actions a hybrid approach. Appl. Soft Comput. J., 46:953 966, 2016. ISSN 1568-4946.
14

---

Published as a conference paper at ICLR 2025
A. Wald. Sequential tests of statistical hypotheses. Ann. Math. Statist., 16(2):117-186, 06 1945.
A. Wald. Sequential Analysis. John Wiley and Sons, 1st edition, 1947.
Wang. An intuitive tutorial to Gaussian process regression. Computing in Science & Engineering. 25:4-11,2020 2020.
Z. Wang and D. W. Scott. Nonparametric density estimation for high-dimensional data algorrthhss and applications. Wiley Interdisciplinary Reviews: Computational Statistics, 11, 2019.
Z. Xing, J. Pei, and P. S. Yu. Early prediction on time series: nearest neighbor approach. In IJCAI, pp. 1297-1302, 2009.
G. Xiong, Li, and R. Singh. Reinforcement learning augmented asymptotically optimal index policy for finite-horizon restless bandits. Proceedings of the AAAI Conference on Artificial Intelligence, 36(8):8726 8734, Jun. 2022.
Xu, Qiao, X. Han, Y. He, H. Tian, and Wei. A random sampling-ber -based method via Gaussian process for motion planning in dynamic environments, Applied Sciences, 2022.
ACKNOWLEDGEMENTS
We sincerely thank the anonymous reviewers for their constructive comments and the area chair for thorough, fair, and objective evaluation of our work. The authors also extend their gratitude to Yuka Fujii for reading an early draft of the manuscript and providing invaluable feedback.
AUTHOR CONTRIBUTIONS
A.F.E. and T.M. conceived the overall research direction, developed the theoretical framework, and wrote the manuscript. A.F.E. formulated the methodology, pilot study establish feasibility, conducted the experiments, and organized the code for release. K.S. and H.I. supervised the project.
15

---

Published as a conference paper at ICLR 2025
APPENDIX
CONTENTS
Introduction
2
Preliminaries: Notations and SPRT
3
FIRMBOUND
Estimating the Conditional Expectation
3.2
Density Ratio Estimation (DRE) for ECTS
Experiments and Results
5
Conclusion
10
References
11
Mathematical Foundations
19
A.1 Probability Measure and Data Randomness
19
A.2 Decision Rule, Terminal Decision, and Stopping Rule
19
Sequential Probability Ratio Test and Its Optimality
20
LLRs and Posteriors as Sufficient Statistic
21
Computational Complexity of FIRMBOUND and sampling method
22
D.I Direct Estimation Approach (F IRMBOUND)
22
D.2 Monte Carlo Integration with KDE Approach
22
D.3 Comparison
23
Supplementary Related Work
24
SPRT and Its Optimality
................................
24
Optimal Stopping Theory
24
SPRT's Backward Induction and Conditional Expectation
................................
24
Sequential Design
24
E.5
Reinforcement Learning (RL)
25
................................
E,6
Active Learning
................................
25
Convex Function Learning (CFL)
25
................................
Gaussian Process (GP) Regression
25
E,9
Other ECTS Algorithms
26
10
Neurophysiological underpinnings SPRT.
26
Supplementary Discussion
27
16

---

Published as a conference paper at ICLR 2025
F1
Intuitive Understanding of PIRMBOUND
27
Challenges in Estimating Conditional Expectations Using Monte Carlo and Kernel
Density Estimation
27
F2.1
Curse of Dimensionality
27
F2.2
Computational Complexity
28
F2.3
Bandwidth Selection
28
F22.4
Sampling Efficiency
28
F2.55
Mitigation Strategies
28
F2.6
Advantage of Having Direct Estimator IIRBOUND
28
Performance under Small Datasets
29
44
Broader impact
29
Limitations and future work
30
F.6
Frequently Asked Questions
31
agrangian Function for Convex Function Learning
33
Stochastic Variational ELBO Maximization
35
SPRI-TANDEM
36
J
FIRMBOUND Is Statistically Consistent
37
Assumptions
37
Formal Statement
38
J.3
Proof
38
Experimental Details and Supplementary Results
40
K.
FIRMBOUND with CFL
40
K.2
FIRMBOUND with GP Regression
40
K.3
Dataset Preparation
40
K.4
Training ECTS Models
41
K.4.1
Two-class Gaussian datset
42
K 4.2.2
Three-class Gaussian dataset
42
K.4.3
SiW
43
K 4.44
HMDB51
45
K.4.5
UCF101
47
K.5
Computing Infrastructure
49
On Hyperparameter Sensitivity of FIRMBOUND
50
M AAPR Baseline Models
52
Parameter Space of /. and
53
17

---

Published as a conference paper at ICLR 2025
0 Ablation Study Details
54
Dumped Oscillating Loggiiiiioo Ratio Function
55
Supplementary experiment on the UCR FordA Dataset
56
Supplementary References
57
18

---

Published as a conference paper at ICLR 2025
A MATHEMATICAL FOUNDATIONS
In the main text, we introduced concise notations to avoid delving into unnecessarily technical details. Here, we provide more rigorous definitions. See Tartakovsky et (2014) for details.
A.1 PROBABILITY MEASURE AND DATA RANDOMNESS
We consider standard probability space F, P). where S is sample space, F C P(2) is o-algebra of Ω where P(2)) denotes the power set of Q and P a probability measure satisfying Kolmogorov's ' axioms:
P(2)) = 1,
P(A) 2 for any A AEF,
P U A,) = Ei P(A,) for any countable collection {4]] C of pairwise disjoint sets (i.c., A A for i j).
function X = X(w) defined on the space (Ω, (with values in Rd (d E EN) in our paper) is called random variable if is F-measurable. The probability that a random variable X takes values in set B C Bed is defined as P(X E B) P(X (B)), where X-1 is the preimage of X.
Let (Fe)e20 be a filtration, which is a non-decreasing sequence of sub-o-algeebas of F; i.e., C F, F for all S s S Each element of the filtration can be interpreted as the available information at a given point t. The tuple (S2, F, (Fe)e20, P) is called filtered probability space.
In our problem setting, x in the dataset
(1 m== represents sequence of observations for the m-th sample, which is treated as stochastic process or as a realization of the stochastic
process (L.T) interchangeably in paper. Dm is the fixed class label associated with x(1.2)
A.2 DECISION RULE, TERMINAL DECISION, AND STOPPING RULE
The decision rule 8 is defined as the pair (de, r), where de is the terminal decision rule at time r (1) and r E (I,..., T} the stopping time. We provide their definitions below.
The task of hypothesis testing a time series classification involves identifying which one of the densities Pı.... the sequence ((I,7) is sampled from. Formally, this tests the hypotheses H1 y= 1.... HK: K.
The decision function or test for a stochastic process (I,T) is denoted by (x(,)) Ω + {I....,K' For each realization of X (1.T), we identify dr as a map d; : Re xT + Kl,...,KK
ie., (w) + y. where E f1...., K}. For simplicity, we write d, instead of d, (x(.))))
The stopping time of (1.2) with respect to a filtration {Fihe2 is defined as T == T(X(1)))) Ω - Ro such that (w (1)(w) S Fr.
Accordingly, for fixed T E N and y E {l,..., KJ. the set {de y represents the time-series data for which the decision function accepts the hypothesis H, E (1,.... K}) with a finite stopping time. Specifically, {d: = y) (w Mdd, (dd((( (x(.))) y. ((x(1.7)) < co).
19

---

Published as a conference paper at ICLR 2025
B SEQUENTIAL PROBABILITY RATIO TEST AND ITS OPTIMALITY
Our work centers around the optimality of Wald's SPRT. Below, we briefly review the optimality statements for both i.i.d. and non-i.idd, multiclass classification scenarios. Note that the assumption of increasing LLRs is not applicable under the finite horizon setting discussed in the main manuscript.
SPRT's optimality with i.i.d., binary class data series.
Theorem B.1. L.I.D Optimality Let the time-series data points 2211,, 1. == 1,2,.. be ii.d. with density fo under Ho and with density fi under H1, where fo & ft. Let ao > and a1 > be
fixed constants such that og + ai 1. the thresholds -Og and ai satisfies ag (a0, a1) = ag and
af (go, a1) on, then SPRT 8 = (d", r") satisfies
inf (=(a.))
B Ho]
= 1B(T"|HO
and
inf (=(d.r))C(ao:aa)
B|r|//l|
1 H1) (14)
similar optimality also holds for continuous-time processes (Irle & Schmitz 1984). Thus, SPRT terminates at the earliest expected stopping time compared any other decision rule achieving the same or lower eлrоr rates- eates-establishing the optimality of SPRT.
Thm. B. demonstrates that, given user-defined thresholds, SPRT achieves the optimal mean hitting time. Additionally, these thresholds determine the error rates (Wald 1947). Therefore, SPRT can minimize the required number of samples while maintaining desired upper bounds on false positive and false negative rates.
SPRT's Asymptotic Optimality with Non-Li.d., Multiclass Data Series. Intuitively, Thm. B.2 Tartakkvsky et al. 2014) suggests that if the LLRs λu increase as samples accumulate, SPRT algorithm achieves asymptotic optimality. In this condition, the moments of the stopping time are minimized up order for specified classification error rate.
Theorem B.2 (Asymptotic optimality of SPRT under multiclass, non-i.id. case). Assume that a non-negative increasing function (t) (vtt) t- bO) and positive finite constants Iua (k, I [K], Pa-r-quickly, 1ga. Then for all m E (0,r) and
# () exist, such that for some r > O, ARd (t)/b(t)
E [K]. inf Ex [T] x5 Ex [T"" as max Ogl - 00.
k.1
The precise definition of r-quick convergence and more detailed discussion can be found, e.g., in Tartakovsky et al. 2014). Fig. shows a graphical guide to the Malticlass-SPRe decision rule.
mii) over all time steps above the threshold find
strongest rival
ta compare with
Log-llke like ihood ratio
(i)
max, to find the largest
trajectory after heing compared with the strongest rival
mnin kzll
Time / #sample
Figure 8: Procedure of multiclass SPRT with static thresholds. (a) Example LLR trajectories for a three-class sequential Gaussian dataset, represented as LLR matrix. (b, c) The two minimum operations defined in Def. 2.1 to determine the stopping time r*.
20

---

Published as a conference paper at ICLR 2025
C LLRS AND POSTERIORS AS SUFFICIENT STATISTIC
The backward induction equation (Eq depends on a sufficient statistic, which encapsulates all necessary information for decision-making. In hypothesis testing, true LLRs posterior prob- abilities suffice to make decisions with a predefined error rate (Wald 1947). thus both LLRs and posteriors qualify as sufficient statistics. The conversion is expressed by TA (X((1)) = 1/(1 + Ligt Xik: exp(Axx(X (x(()))))(()))))), where X&I = ply k)/p(y = 1) represents the prior ra- tio. A formal definition sufficient statistic available in Tartakovsky al. (2014), as follows: Definition C.1 (Sufficient Statistic). sequence (zi) is defined to be sufficient statistic for the sequential decision problem it satisfies the following conditions:
1. Transitivity: The sequence is transitive, meaning there exists a function (x(.) such that
S+1 = (. (1+1)) almost surely, for 2 1.
2. Equality of Conditional Probability Density Function (pdf): The conditional pdf of X++1 given the past observations X can be expressed solely in terms of Py:
(1+1(x((+1) (x P1+1(x Ht), almost surely, for 2 1.
3. Equality of Risks: The Posteriori Risk (APR) when using the sufficient statistic Pt equals the APR calculated directly from the observations:
APR(X(10) = APR APR( almost surely. for
Note that the online DRE algorithm SPRT-TANDEM is transitive, providing consistent estimation of the sufficient statistic.
Which statistic to use, LLRs posteriors? In principle, the CFL algorithm can handle either LLRs or posteriors as the sufficient statistic for calculating the conditional expectation. Our ex- periments confirm that both LLRs and posteriors yield equivalent results; however, opt to posteriors to reduce input dimensionality.
Conversely, our use of GP regression is predicated the assumption that the risk distribution is jointly Gaussian, which motivates us to use LLRs as the sufficient statistic. Nonetheless, an experiment with the two-class Gaussian dataset confirms that GP regression provides equivalent results regardless of the type of statistic used (Fig.)
(a) AAPR curcee the beneclss Castodin
1,2" thi
10
10.3
Aveagee peveror nax
2.256
30
10.2
25
2.266
Vanilla SPAT on true LLRs FIRMBOUND (GP) true posteriors FIRMBOUND
10
30 Mean time (efromest
10
20
30
40
Figure 9: Comparing LLRs and posteriors sufficient statistics for GP Regression. LLRs and posteriors are used as sufficient statistics to evaluate (a) the AAPR curve and (b) the SAT curve. The two-class Gaussian dataset provides the ground-truth LLRs and the corresponding converted posteriors.
21

---

Published as a conference paper at ICLR 2025
D COMPUTATIONAL COMPLEXITY OF FIRMBOUND AND SAMPLING METHOD
Here, we provide detailed comparison of the computational complexity for the inference stage of both the direct estimation approach and the Monte Carlo Integration with Kernel Density Estimation (KDE) approach.
D.1 DIRECT ESTIMATION APPROACII (F IRMBOUND)
The direct estimation approach uses the following function to evaluate the conditional expectation:
storch.ne_grad.
def predict (self, X: Tensor, *args, **kwargs) -> Tensor:
prea, torch.max torch.matmul (x, self.a.T) + self.y_hatt reshape (1, -1), dim=1
return pred
In this function:
X is the input tensor size [B K], where B is the batch size and K the number of classes.
self. a and self. hat parameter tensors of size K] and [4]. respectively, where 1 < is the subset data number.
The computational complexity for each step in the inference stage is as follows:
1. Matrix Multiplication: The operation torch. matmul (x, self.a. has a com- plexity of ((B. K T). Broadcasting and Addition: The operation torch. tmul (X, self.a.T) self.y hat reshape (1, -1) involves broadcasting and addition, which has complexity of O(B 1).
2. Maximum Value Selection: The operation torch. max (..., dim=1) finds the maxi- mum value along the specified dimension, which has complexity of O(B- I).
Thus, the total computational complexity for the inference stage of the direct estimation approach is dominated by the matrix multiplication step, resulting in:
O(B K 1)
D.2 MONTE CARLO INTEGRATION WITH KDE APPROACH
The Monte Carlo Integration with KDE approach involves the following steps for the inference stage:
1. Generate samples from the conditional density p(5++1 ..) using KDE.
2. Evaluate the function Ge+1 (1++)) for each sample.
3. Compute the average estimate the conditional expectation.
Assuming:
B is the batch size (number of input samples in .t).
K is the dimensionality (number of classes).
M is the total number of data points.
S is the number of Monte Carlo samples.
In the Monte Carlo Integration with KDE approach, the dimensionality K affects the number of Monte Carlo samples S required for convergence. Let S(K) denote the number of samples as function of K, typically increasing with K. The computational complexity for each step is follows:
22

---

Published as a conference paper at ICLR 2025
1. Sampling from KDE: Generating S(K) samples for each of the B input samples, each requiring O(M K) operations, resulting in complexity of O(B S(K) M K).
2. Function Evaluation:
Evaluating G for each sample with complexity O(K), resulting in a total complexity of ((K) K).
3. Monte Carlo Integration: The averaging step has a complexity of
K).
Thus, the total computational complexity for the inference stage of the Monte Carlo Integration with KDE approach is dominated by the sampling step, resulting in:
O(B S(K) M K)
D.3 COMPARISON
The direct estimation approach has a computational complexity of (O-BK-)) for the inference stage, while the Monte Carlo Integration with KDE approach has complexity of O(B S(K) M K)- Given that < M and considering that higher dimensionality (K) increases the number of samples required for convergence (8)))) the direct estimation approach significantly more efficient in terms of computational complexity during inference. This efficiency is particularly advantageous for real-time applications and large-scale datasets.
Table 2: Comparison of Inference Stage Computational Complexity
Approach
Inference Stage Complexity
Direct Estimation with FIRMBOUND Monte Carlo Integration with KDE
O K I) O S(K) M K)
23

---

Published as a conference paper at ICLR 2025
E SUPPLEMENTARY RELATED WORK
E.1 SPRT AND ITS OPTIMALITY
SPRT is Bayes optimal in binary classification with i.id. samples and is also known to require
the minimal sample size to achieve a predefined error rate (Wald & Wolfowitz, 1948
1950). The
properties of SPRT under multiclass scenarios (Armitage) 1950 Baum & Veeravalli 1994, Chernoff
1959 Dragalin 1987, Dragalin & Novikov 1999/]Kiefer & Sacks 1963 Lorden] [9ndden][997] 1977; Paulson 1963
Pavlov 1991 1984; Simons | & Wald 1949). and with non-i.i.d. samples (Dragalin et al.
1999: Lai 1981; Tartakovsky|1999
have also been studied (App. [B). Several algorithms employ
SPRT with estimated density ratio with kernel method (Teng & Ertin (2166) or boosting (Sochman &
Matas 2005) approach. However, they often assume i.i.d. samples and limited to binary classification,
without considering the finite horizon.
E.2 OPTIMAL STOPPING THEORY
Optimal stopping theory helps decide the best time to act, minimizing expected cost. It applies to various settings like the secretary problem, parking problem, one-armed bandit, change-point detection, and sequential statistical decision problems.
Among these, finite-horizon problems are particularly relevant to our study, which involve a known upper bound on the length of the sequence. Discrete-time, finite-horizon problems are typically solved using dynamic programming techniques like backward induction, a type of Bellman equations. However, backward induction poses significant computational challenges. It requires storing and computing all possible histories, leading to high computational costs and analytical intractability unless the underlying distribution is known and simple (Ferguson) 2006) Tec al. 2023) Several approximation methods, such as k-step and k-time look-ahead rules, have been proposed, but they fall short of optimality unless the problem is monotonic, which is often not the case with real-world data.
E.3 SPRT'S BACKWARD INDUCTION AND CONDITIONAL EXPECTATION
Applying the backward induction under real-world conditions is impractical Tartakovsky et al. 2014). No analytical solution has been identified, and although numerical computation simulated datasets is feasible (Jarrett & van der Schaar (020)) calculating the conditional expectation of future risks-a critical component of backward induction-is computationally intensive. This often necessitates approximations such as assuming conditional independence of temporal evidence (Ahmad)
& Yu 2013 Naghshvar & Javidi 2013). discretizing continuous variables (Frazier Yu (007))
or adopting a one-step look-ahead approach (Kleinegesse et al. 2020 Najemnik & Geisler 2005).
Moreover, ECTS demands instantaneous evaluation of the conditional expectation, precluding the use
of sampling- based methods of the conditional expectation on the fly (Wang & Scott (2019). The lack
of true LLRs, which are the sufficient statistic required for SPRT and backward induction, further complicates their practical application within finite horizons.
E.4 SEQUENTIAL DESIGN
Sequential design, particularly simulation-based Bayesian sequential design, offers a practical ap- proach these challenges. This method, grounded in statistical decision theory, approximates the objective function (c.g.. minimum risk) using simulated trajectories on finite grid points rather than exhaustive computation of all possible histories (Brockwell & Kadane 2003 Müller et al., 2007 Kadane & Vlachos 2002). Notable approaches within this framework include constrained backward induction and sequential design with optimizing decision boundaries. Constrained backward induc- tion iteratively approximates expected utility using simulated trajectories, while sequential design with optimizing decision boundaries transforms the sequential decision problem into a non non-sequential optimization of parametric decision boundaries (Rossell et al. (007). Both methods rely on simulated trajectories, unlike our model, which utilizes real-world data trajectories and avoids the tradeoff between precision and computational cost associated with grid-based methods.
24

---

Published as a conference paper at ICLR 2025
E.5 REINFORCEMENT LEARNING (RL)
RL is another domain where backward induction, often referred to as the Bellman equation, is extensively applied. In RL, algorithms like Q-learning and policy gradient methods can be viewed as constrained backward induction and sequential decision-making with optimizing boundaries, respectively. However, RI. faces significant challenges, including poor sample efficiency and training instability, often leading to catastrophic forgetting and high variance in policy gradient estimates (Atkinson et al. 20188 Bjorck et al. 2021] Cetin et al. [0022 Kumar et al. 2020; Nikishin et al. 2018
Sullivan et al. 2022). RL approach is often combined with the sequential design (Asano| 2022
Blau
et al. 2022).
E.6 ACTIVE LEARNING
Active learning is a machine learning paradigm aimed at achieving high accuracy with minimal labeled data by strategically querying the most informative samples. It encompasses several strategies, including active sensing and active hypothesis testing. In active sensing, the system optimizes sensor placements and parameters to gather the most relevant data, while in active hypothesis testing, the goal is to identify the correct hypothesis as efficiently as possible. One foundational work by (Cohn al. 1996) demonstrated the effectiveness of active learners over passive learners by querying the most informative data points. (Lewis & Gale 1994) introduced uncertainty sampling, where instances with the highest uncertainty are selected for labeling. Another key method, query-by-comminee (QBC) by (Seung et al., 1992), selects instances based on the disagreement among multiple models. More recently, approaches like Bayesian active learning by disagreement (Houlsby et al., 201T)) and cete-set approaches (Sener & Savaresel 2017) have been developed to handle the complexity of neural networks. Parrett & van der Schaar (2000) developed a framework for timely decision decision-making under context-dependen time pressure.
E.7 CONVEX FUNCTION LEARNING (CFL.
CFL aims to infer a convex function from data points, assuming the target funetion is inherently convex. This assumption ensures that any local minimum is also a global minimum (Argyriou ct al. 20088 Bach 2010 Bartlett et al.) 2005; Boyd & Vandenberghe/ (2000). thereby simplifying the optimization landscape and enhancing the efficiency of solving optimization problems (Mendelson 2004). Within this framework, the Alternating Direction Method of Multipliers (ADMM) has proven to be particularly effective (Amos et al.) 2016), allowing for the decomposition of complex optimization tasks into smaller, more manageable subproblems that are solved iteratively (Eckstein) 2012, Gabay & Mercier 1976. Glowinski & Marroco 1975). ADMM's capability extends to solving the augmented Lagrangean equation on a piecewise linear function, optimizing each segment effectively (Siahkamari et al., 2020). However, the standard ADMM can be slow to converge. To address this, enhancements such as the 2-block ADMM have been developed to accelerate convergence, thus improving the overall performance of CFL applications (Siahkamari et al.) 2022).
E.8 GAUSSIAN PROCESS (GP) REGRESSION
GP regression is a Bayesian approach that makes probabilistic predictions (Wang) 2020). Unlike traditional regression methods that presuppose a specific form for the regression function, GP regression treats observed function values as jointly Gaussian, with a mean function and covariance defined by kernel function. The kernel encapsulates assumptions about the function's 's smoothness and the nature of correlation between function values at different points the input space. The inherent flexibility of GP regression, which does not require the explicit specification of the function form, renders GP regression widely applicable in diverse fields including geostatistics often referred to as Kriging (Huangl 2020 Tao et al.) 2022, Richter & Toledano- Ayala, 2015), financial modeling (Gonzalvez et al. 2019 Herfurth 2020 Petelin et al. 2011)) to robotics (Cheng et al. 2022 Jakkala
& Akella 2023 Xu et al. 2022).
Traditional GP model, however, faces significant computational challenges when applied to large datasets due to the O(M3) scaling with respect to the number of data points M. To making it infeasible for large-scale applications. To mitigate this, inducing point methods have been developed to approximate the full GP, substantially reducing the computational load while largely retaining
25

---

Published as a conference paper at ICLR 2025
the model's expressive power (Candela & Rasmussen 2005). By summarizing the dataset with smaller set of m inducing points, the complexity is reduced to O Additionally, stochastic variational inference (SVI) optimizes variational parameters using minibatches of data, which signifi- cantly decreases the computational demands to ((m²) per update, independent of the full dataset size (Hensman et al. 2014). This approach not only makes GP regression scalable but also adapts well to modern computational infrastructures, such as GPUs, enabling the handling of extensive datasets within constrained resource settings (Deisenroth & Ng
2015 Wilson & Nickisch 2013).
E.9 OTHER ECTS ALGORITTM
ECTS is pivotal in scenarios requiring prompt and accurate classification decisions from incomplete
data streams. Applications of ECTS includes, but not limited to, medical diagnosis (Evans et al. 20015]
Griffin & Moorman 2001 Vats & Chan 2016), stock crisis identification (Ghalwash al. 2014).
autonomous driving Dooá et al. 2019), action recognition (Weng et al. 2020), and e-commerce user profiling (Duan et al. 2024). Delays in classification can have critical consequences, positioning ECTS as a key area of research within time series analysis. This field inherently presents a multi- objective optimization challenge aimed at maximizing classification accuracy while minimizing decision time (Mori et al.
[2118] Mori et al. 2015; Xing et al., 2012). Recent advancements have integrated deep learning techniques due their robust representational capacities (Dennis al.,
2019, Lv et al. 2023 Sun et al., 2023: Suzuki et al. 2018 Hartvigsen 2018 Ismail Fawaz et al.
et al. 2021). For example, LSTM-s and LSTM-m, have been developed to impose monotonicity on classification scores and enhance inter-class margins, respectively, thereby accelerating action detection (Ma et al.] 2016). The Early and Adaptive Recurrent Label ESTimator (EARLIEST) leverages combination of reinforcement learning and recurrent neural networks to dynamically decide the timing and classification of data (Hartvigsen et al., 2019). Moreover, the incorporation of transformer technologies, seen in Trn-Tsanst,rmer, merges temporal convolution with transformer architecture to prioritize early classification through specialized loss functions (Chen et al. 2022). Several algorithms empirically predict future risk decide when to halt the sampling (Martinez et al.. 2020; Wang et al. 2024] Zafar et al. (CALIMERA) (Bilski & Jastrzębska
2021). For example, Calibrated eArLy tIMe sERies clAsifier 2023 predicts the minima of risk function where the decision
making should be made.
E.10 NEUROPHY UNDERPINNINGS OF SPRT.
SPRT has been identified as a neural decision mecciinn-making algorithm within the primate brain's lateral intraparietal cortex (LIP, (Roitman & Shadlen )002)). During alternative-chicce tasks, LIP neurons gradually accumulate sensory evidence, represented by an increasing firing rate of single neurons (La
timer et al., 2013), the average population activity (Shadlen et al.) 2016).
high-dimensional manifold of neural populations (Okazawa et al.] (021). Since neural activities are proportional to LLRs, the behavior of LIP neurons and primates' decision strategies can be best explained by SPRT
Kira et al. (2015). For more information, readers are directed to review articles such as (Doya 2008
Gallivan al. 2018 Gold & Shadlen (007).
Multiple studies investigate decision-making under time pressure (Churchland et al. 2008 Dru- gowitsch al. 2012 Hanks al. 2014). Some papers report closing boundaries under such
conditions(Kirz et al. 2024), reminiscent of the optimal decision boundary computed with the back- ward induction (Fig. 2p), while others identify an urgency signal, a linearly increasing offset added to the ramping neural activity (i.e., corresponding to the sufficient statistic in optimal stopping theory), which accelerates decisions as the deadline approaches. Both the closing boundary and the urgency signal have psychophysically equivalent effects, compelling quicker decisions with less confidence as the finite horizon approaches.
26

---

Published as a conference paper at ICLR 2025
F SUPPLEMENTARY DISCUSSION
F.1 INTUITIVE UNDERSTANDING OF F FIRMBOUND
APR. The first term of Eq. imposes heavy penalty if the terminal decision de = k corresponds low posterior probability Tg. The second term accumulates the sampling costs up the current time step t.
Theorem 2.1 (backward induction). Theorem 2.1 can be interpreted as recursive decision- making process that minimizes Bayes risk at each time step. The Sequential Probability Ratio Test (SPRT) at each step must either (i) continue sampling to refine the sufficient statistic, (ii) make final classification decision with the current sufficient statistic. Each choice- (i) continuing or (ii) stopping- incurs a form of risk: the continuation risk, G2 (Eq. (5)), and the stopping risk, G (Eq. (6)). At each time step, the lower of these two values defines the minimum risk, G (Eq. (7)), up to the classification deadline or finite horizon.
Initiation of backward induction. At the finite horizon (t = T),, the minimum risk G is always equal to the stopping risk G setting the initial condition for the risk distribution at time T. Subsequently, G for earlier time steps is recursively calculated using the risk distribution of the subsequent time step (Fig. 3D).
Risk comparison during deployment. Initially, the sufficient statistic is small, leading to a higher G than G. As more samples are collected, the statistic increases, enhancing decision confidence and reducing G below G. The decision made when Ge less than or equal to G, with the decision boundary at f" being the intersection of G and G (Fig. 3d)
F.2 CHALLENGES IN ESTIMATING CONDITIONAL EXPECTATIONS USING MONTE CARLO AND KERNEL. DENSITY ESTIMATION
Estimating conditional expectations such as E (G++1 | .9]] a common problem in various
scientific and engincering disciplines. One approach to achieve this estimation is by employing Monte Carlo integration techniques (Kroese et al. 2011 Robert & Casella 2004) in conjunction with Kernel Density Estimation (KDE, (Scott 1992 [Silverman 1986)) and its application to conditional density, Kernel Conditional Density Estimation (Rosenblati 1969) approximate p(.5,-1 Zd). While this method is theoretically sound and flexible, it comes with several significant challenges, particularly in high-dimensional settings. This section outlines the primary difficulties associated with this estimation method, including issues related to the curse of dimensionality, computational complexity, bandwidth selection, and sampling efficiency.
F.2.1 CURSE OF DIMENSIONALITY
Sparsity of data In high-dimensional spaces, data points tend to become sparse (Botev al. 2010). The volume of the space increases exponentially with the number of dimensions, which means that even large datasets may not provide sufficient coverage of the space. This sparsity makes it difficult to accurately estimate the conditional density p( p(A++1 At) using KCDE because the kernel functions may have cover large regions with very few data points, leading to high variance in the density estimates. Indeed, WWan & Scott (2019) defines nigh-dimensional data for the kernel density method most 50-dimensional, indicating the difficulty of modeling probability distributions over sufficient statistics y, given that y is at least K -ddimensional where K is the class number.
Bandwidth selection. Selecting appropriate bandwidth for the kernel is critical for accurate density estimation (Bashtannyk & Hyndman 2001 Wang & Wang 2007). In high-dimensional settings, single bandwidth parameter is often insufficient, and multicimensional bandwidth matrix is required. However, selecting and optimizing such a bandwidth matrix is computationally intensive and challenging. If the bandwidth is too large, the estimate will be overly smooth, missing important details. Conversely, if it too small, the estimate will be too noisy, capturing random fluctuations rather than the true underlying structure.
27

---

Published as a conference paper at ICLR 2025
F.2.2 COMPUTATIONAL COMPLEXITY
High computational cost. Kernel density estimation involves computing distances between data points and evaluating kernel functions. In high dimensions, these computations become increasingly expensive. The number operations required grows with both the number of data points M and dimensionality of the space. For KCDE, which requires estimating the joint and marginal densities, the computational cost is even higher. Given that our application is online ECTS, waiting for the estimation converge at each time step is very impractical. Rather, F FIRMBOUND provides function that readily be evaluated with convergence guarantee, enabling deployment under real-world scenarios.
F.2.3 BANDWIDTH SELECTION
Data-dependent bandwidth. Adaptive methods, where the bandwidth varies locally depending on the density of data points, can provide better estimates but add another layer of complexity. These methods require careful tuning and can be computationally demanding, especially in high-dimensional spaces.
F.2.4 SAMPLING EFFICIENCY
Efficient sampling techniques. Even with an accurate estimate of the conditional density p(5 Sd. efficiently sampling from this distribution can be challenging. Techniques such rejection sampling or Metropolis-Hasting may be necessary, but these can be computationally intensive and may not scale well with dimensionality.
F.2.5 MITIGATION STRATEGIES
To address these challenges, several strategies can be employed, each with its own assumptions and potential sources of error:
Dimensionality Reduction:
Techniques such as Principal Component Analysis (PCA) or autoen- coders be used to reduce the dimensionality of / while preserving important structures in the data. This can help alleviate the curse of dimensionality and improve the efficiency of density estimation. However, this assumes that the reduced dimensions adequately capture the necessary information, which may not always be true.
Sparse Kernel Methods: based methods) can reduce the computational burden. The assumption here is that the subset is representative of the full dataset, which might hold in all cases, potentially leading to biased estimates.
Utilizing subset of the data points (e-g., random sampling or clustering-
Localized Methods: Adaptive kernel methods, where the bandwidth varies depending on the local density of data points, can provide more accurate estimates in high- nigh-dimensional spaces. These methods assume that local adaptation can adequately capture the density variations, but improper tuning can introduce significant errors.
Grid-Based Methods:
For pooderate-dimenssionn cases, grid- based methods can approximate the density on discretized grid, reducing computational complexity. The main assumption is that the grid resolution fine enough to capture the density details, but this can lead to high memory and computation costs if the dimensionality is still relatively high.
F.2.6 ADVANTAGE OF HAVING DIRECT ESTIMATOR F FIRMBOUND
The development of direct estimator for the conditional expectation (G--1(F441) St) presents significant advantages over the traditional Monte Carlo Integration approach combined with Kernel Density Estimation. Firstly, direct estimator offers computational efficiency by providing instanta- neous evaluations, which is crucial for real-time applications and large-scale datasets. This efficiency eliminates the need for extensive sampling and repeated function evaluations inherent in Monte Carlo methods, thus reducing computational overhead. Additionally, the direct estimator ensures statistical consistency, guaranteeing that as the sample size increases, the estimator converges to the true conditional expectation, thereby enhancing the reliability and accuracy of the estimates. In contrast,
28

---

Published as a conference paper at ICLR 2025
(9)
AAPR curve of small datasets
(b)
SAT curve of small datasets
rate 196
Average postenon nak
M=60000.
M=6000,
L/T
FIRMBOUND (CFU
M=600,
L/T Vanilia
M=5000,
Mean per- class
20
L/T .9,
FIRMBOUND (CFL)
Vanilla SPRT
L/3
10
30
40
10
30 40
Mean hitting time (nframes)
Mean hitting time (ifrrames)
Figure 10: Performance comparison across datasets of different sizes. The three-class Gaussian dataset is reduced from the original size (M 60000) to M 6000 and M 600 for train- ing FIRMBOUND, while using the same test dataset. Hyperparameter settings remain fixed, and experiments repeated five times compute error bars. (a) The AAPR curve and (b) the SAT curve demonstrate that FIRMBOUND maintains competitive performance with datasets one order of magnitude smaller (M 6000).
Monte Carlo methods are prone to sampling errors and require careful tuning of kernel functions and bandwidth parameters, adding complexity and potential sources of error. Furthermore, the direct estimator simplifies the implementation process by obviating the need for density estimation, which can be particularly challenging in high-dimensional spaces due to the curse of dimensionality. This simplicity, coupled with reduced memory requirements, makes the direct estimator more robust and scalable, offering a clear advantage in handling high-dimensional data and real-time decision decision-making scenarios.
F.3 PERFORMANCE UNDER SMALL DATASETS
While F FIRMBOUND ensures statistical consistency, its practicality could be questioned if performance degrades significantly with reduced dataset sizes. To address this concern, we conduct an additional experiment. Using the three-class Gaussian dataset, we train F IRMBOUND with datasets up to two orders of magnitude smaller than the original size while keeping the same test dataset. Specifically, dataset sizes of M 600 and M = 6000 are compared to the original size of M = 60000. Hyperparameter settings are kept fixed, and experiments are repeated five times to compute error bars.
The results show that even with a dataset one order of magnitude smaller (M = 6000), FIRMBOUND demonstrates almost negligible differences in performance compared to the original dataset in terms of mean hitting time, AAPR, and mean per-class error rate. Notably, the real-world HMDB51 dataset has similar order of magnitude (M 5277), further showcasing F FIRMBOUND's robustness in real-world scenarios. However, with the smallest dataset (M 600), AAPR and mean per-class rates increase significantly, indicating that the dataset size insufficient accurately estimate the sufficient statistics. Despite this, the mean hitting time remains close to the original, highlighting F PIRMBOUND'S is stability/ and its ability make reliable best-effort decisions even under highly limited data conditions.
F.4 BROADER IMPACT
F FIRMBOUND enhances the performance of ETCS in real-world settings and prompts further research across both machine learning and neuroscience. facilitates the backward induction on real-world datasets, effectively removing constraints associated with i.i.d. or non-i.i.d. data, thereby expanding its utility for time-sensitive tasks. Furthermore, backward induction instrumental in fields like active sensing and sequential design, where unlike ECTSS an agent proactively selects actions to gather informative evidence. FIRMBOUND is ideally suited for such applications, enabling its deployment in dynamic environments. Additionally, the tapering optimal threshold is reminiscent of decision- decision-making processes observed in humans, providing a potential bridge to understanding neural thresholding mechanisms within finite horizon, which, despite extensive study (Churchland et al.) 2008 Drugowitsch et al.] 2012; Gold & Shadlen 2007: Latimer et al., 2015) Okazawa et al. 2021).
remain elusive.
29

---

Published as a conference paper at ICLR 2025
Our method is designed to optimize the speed-accuracy tradeoff in real-world applications, which is expected to lead to positive societal impacts. The potential for negative effects is minimal and mainly confined to instances where models are intentionally trained to prioritize speed accuracy by using an extreme value of sampling cost, which could compromise decision speed or quality.
F.5 LIMITATIONS AND FUTURE WORK
Domain gap. While F PIRMBOUND provides theoretical guarantee to minimize the AAPR, it is important to acknowledge that it may not achieve the global minimum on test data when there is a domain gap between the training and test sets. A domain gap occurs when the distribution of the test data differs from that of the training data, which can lead to suboptimal performance of the model, even with the optimal stopping rule. FIRMBOUND, as proposed, assumes that the test data follows the same distribution as the training data, and thus, its effectiveness may be compromised in the presence of such domain discrepancies.
We recognize the importance of addressing domain gaps in machine learning research. However, it is important to note that handling domain gaps is beyond the current scope of our paper, which focuses on developing an optimal stopping rule for early classification within finite horizons. Employing a domain adaptation algorithm or foundation models would require different methodological approach and additional research efforts. Potential directions include incorporating domain adaptation techniques and robustifying F IIRBOUUD against such discrepancies.
Future theoretical directions. While PIRMBOUND "doubly consistent* estimator of both the backward induction and log- likeliidddooo ratio, several theoretical directions are yet to be investigated. One example the convergence rate of the algorithm. While it presumably given by the sum of LSEL's and CFL's. The latter is given in the paper, but the former requires an additional extensive analysis because Lemma J.4 (consistency of LSEL), on which our consistency proof relies, is an asymptotics of the probability that the estimated parameters deviates from the optimal parameter set. Similarly, minimax bound cannot be derived straightforwardly. warrant a separate, focused study.
Potential density chasm problem. We observe that Fig. 5p (for the two-class Gaussian dataset) shows discrepancy in the minimal averaged posterior risk (AAPR) locations between true and estimated LLRs. Interestingly, this trend is negligible in Fig. 55p (for the three-class Gaussian dataset), where AAPR locations for true and estimated LLRs align more closely. One possible explanation is the density chasm problem, a known issue specific to density ratio estimation on "casy" problems. which increases the absolute value of the density ratio and could contribute to these errors (Rhodes) let al. 2020). A countermeasure to the density chasm problem, telescoping density ratio estimation, was proposed in (Rhodes et al. 2020), and employing this approach may help mitigate the error on simple datasets.
These issues likely specific simple datasets and are less prevalent in complex real-world datasets with arbitrary class counts. It is important to note that while statistical consistency guarantees minimization of estimation error, it does not address approximation or optimization errors, which may be the main contributing factors here.
Performance gain under dynamic environments. FIRMBOUND often shows limited performance on datasets with monotnic trajectory of sufficient statisties (see also App. F.6 for more detailed discussion). This minimal performance gain does not diminish FIRMBOUND'S practical value. The real-world datasets examined (SiW, HMDB51, UCF101, and FordA) involve relatively small domain gaps and fewer fluctuations, producing stable. monotonic trajectories that limit opportunities for improvement over static thresholds. However, more adversarial real-world scenarios, such as those with dim or variable lighting, we would expect the trajectory to fluctuate similarly to the DOL dataset, where FIRMBOUND shows robust performance gains. Furthermore, as noted in Section 4, FIRMBOUND consistently reduces the variance of hitting times across all datasets. Along with its capability to handle i.idd., non-i.i.d., and multiclass data, this variance reduction demonstrates FIRMBOUND's potential for reliable decision making. In future work, we aim to explore FIRMBOUND's performance under more dynamically adversarial conditions, which we anticipate will reveal greater gains similar those seen in our DOL experiments.
30

---

Published as a conference paper at ICLR 2025
Retraining requirement at cost change. FIRMBOUND effectively delineates the Pareto front on the SAT. A potential limitation arises a user is unsatisfied with the resulting speed or accuracy and wants to select different point on the Pareto front; in such cases, retraining FIRMBOUND with new cost parameter с is required. The training process can be computationally intensive, especially if the CFL algorrihm is used to estimate the conditional expectation. However, there is a remedy for this issue. Without incurring additional computational costs, users can re-evaluate the AAPR curve on the current sufficient statistic y using different values of This allows them efficiently identify the optimal that yields the desired mean hitting time and corresponding error rate on the SAT curve by finding the AAPR curve whose minimum closest the desired mean hitting time. This strategy effectively avoids the need for retraining F FIRMBOUND when specific error rate must be achieved on the SAT curve, which is often crucial in high-security applications.
Extremely large LLRs' magnitude. Large LLRs, which can occur when the classification task is relatively easy, can significantly hinder the training of F IRMBOUND in the following ways. When LLRs are extremely large, the corresponding posterior probabilities derived from them often degen- erate to either zero one, making the training data less informative. This forces F FIRMBOUND to learn from dataset with extreme and non-in non-informative posterior probabilities, potentially leading to overfitting and reduced generalization performance. An alternative approach is to train F RMBOUND directly on the LLRs instead of the posteriors. However, in multiclass classification with K classes, the number of pairwise LLRs required is at least K(K - 1)/2, which can be extremely large. This approach can be prohibitively memory- eeemory-intensive especially when K is large, making training on standard devices challenging. Additionally. the unbounded nature of LLRs into the training process. However, it is important to note that in cases where posterior probabilities be resolved
introduce instability
degenerate, time-series analysis may be necessary. The fact that classification entirely within the first (or first few) steps suggests that F FIRMBOUND may not need to be employed in such scenarios, indicating that this limitation is not a direct weakness of the method.
F.6 FREQUENTLY ASKED QUESTIONS
How would you justify FIRMBOUND's two-component framework, given that it introduces additional complexity and potential error propagation? The doubly consistent estimation -of both the conditional expectation in backward induction and the LLR required by FIRMBOUND ne- cessitates a multi-come multi-component framework. While this design may introduce additional complexity and the potential for error propagation across components, FIRMBOUND guarantees the minimization of estimation errors, particularly in large datasets.
Consistent estimation itself represents a significant advancement in ECTS. Most existing ECTS meth- ods rely on empirical heuristics, whether they follow a two-component approach (e.g.. CALIMERA) or a coe-oomponnnt, end-to-end framework (e.g., LSTMms, Tra-Transformer, EARLIEST), Our experiments demonstrate that these heuristic- approaches are consistently outperformed by FIRMBOUND, emphasizing the practical benefits derived from our theoretically grounded, multi- component framework.
When is a new Pareto-front available? FIRMBOUND extends the Pareto front on some datasets, depending on LLR monotonicity. In Gaussian datasets with monotonically increasing LLRs, expedites decisions without increasing error rates (Fig. T 64. b). Importantly, even without a new Pareto-front, IRMBOUND ensures reliability by reducing hitting time variance (Tab. []. crucial for safe deployment in diverse scenarios. Conversely, in monooonoo DOL datasets with initial noise followed by stabilization, it effectively achieves new Pareto-fronts (Fig, 6C).
Is it possible to establish consistency with GP? When should I use GP? Yes, it is possible to construct a consistent estimator using Gaussian Processes (GP) under certain conditions. The GP regressor be consistent estimator if, with appropriate choice of the kernel, c follows Gaussian distribution for all E [T] and m [M], and (Go (=G,,m) (..)) ) JMM is Gaussian process for all t E [T]. However, these conditions are difficult to guarantee under arbitrary circumstances. Thus, introduced CFL more general and robust solution.
31

---

Published as a conference paper at ICLR 2025
When should I use GP? What's your recommendation? Albeit the consistency loss, our experi- ments show that the GP regressor performs competitively with CFL, which is the theoretically optimal approach. This makes GP practical choice in scenarios with limited computational resources. It is worth noting that GP regression is particularly efficient during the *training* stage. During testing or deployment, both CFL and GP regression are sufficiently fast support real-time decision-making. Therefore. GP regression is an effective option in environments with constrained training resources, such as edge computing settings.
Why some models are excluded from Fig. 5 Effective risk minimization relies on well-calibrated statistics. As shown in Fig. 14 in App. shows that model rankings based on AAPR don't 't always align with their SAT performance due overconfidence miscalibration, where predicted confidence
levels don't 't match actual accuracy Guo et al. (2017); Melotti et al. ) Müller et al. (2019); Mukhoti et al. (2020). While it is feasible minimize AAPR on the miscalibrated outputs, it can lead to suboptimal decision- decision-making. By employing well-calibrated Log-Likelihood Ratios (LLRs), FIRMBOUND effectively minimizes risk, achieving Pareto-optimality at a given sampling cost. This calibration ensures that the model's confidence levels are more aligned with the true probabilities, thereby enhancing the reliability of the decision boundaries used in the stopping rule.
What is the tackled problem? Finite horizon Early Classification of Time Series (ECTS) aims to minimize the decision time 7 T while maintaining a desired error rate a, where T is the maximum possible time step. As mentioned in Sec. 2 SPRT optimally solves ECTS under an infinite horizon, detailed in App. B. For finite horizons (including infinite as a special case, 1. 108), the average a posteriori risk (AAPR) must be defined and minimized via backward induction to find the optimal stopping boundary (Sec. 3
Why does computing the backward induction equation yield minimal AAPR? The mini- mal AAPR is defined as the expected optimal risk at the initial time step, computed recursively from the finite horizon back to the start using the backward equation. For a detailed explanation. see Tartakovsky et al. 2014).
Why FIRMBOUND necessary, given the availability of simulation studies? FIRMBOUND accommodates broad range of time series data, including i..dd,, non-i.i.d., binary, and multiclass series. In contrast, many existing simulation studies focus on artificial datasets with limited classes and do not reflect real-world complexities. Additionally, optimal threshold searching through numerical simulation might require intensive grid sampling, which becomes computationally impractical with large classes for example, assigning unique posterior probabilities to 101 classes with 0.1 steps could result in up to 47 trillion combinations. FIRMBOUND facilitates the application of backward induction real-world datasets without restrictions related to the data distribution, thereby extending its applicability to time-sensitive tasks.
Why are some experimental results not state-of-the-art (SOTA)? As discussed in the Exper- iments and Results section, we do not claim to achieve Klate-of-the-ar results. For example, the pretrained feature extractor ResNet50 was not fine-tuned for HMDB51 I and UCF101 datasets. Our focus is conducting a fair comparison rather than achieving the highest performance, reaching state-of-the-are would not alter the conclusions of our study.
Why don't you include classification penalty in APR? While is feasible to incorporate classification penalty into the APR to potentially reduce errors, we aim to maintain a simple APR
definition as stated in Sec. [3.2] Adding classification penalty is redundant since the estimation of
sufficient statistics inherently addresses error reduction. We utilize density ratio estimation (DRE) algorithm to ensure statistically consistent estimation of LLRs, thereby reducing errors without the need for an additional penalty term in the APR.
32

---

Published as a conference paper at ICLR 2025
G LAGRANGIAN FUNCTION FOR CONVEX FUNCTION LEARNING
In this section, we review the 2-block ADMM algorithm (Siahkamari et al. 2022) used for solving
the convex regression problem (Eq. 12). We solve the following noisy convex regression problem with regularization:
1 Σ 72 ==1
f arg min
vv
fa;))² + X|lfI|,
(15)
where æ, E Rd, and is hyperparameter affecting convergence. Note that regression labels y, are noisy; i..,, they have bounded random discrepancies from the true label.
The 2-block ADMM solves this problem by using piecewise linear functions:
min Σ
(ū: 11)2 + x
max layal i=1
(16)
0..0, 72
1=1
1=1
s.t. D1 U3 (a;, Li - -x,) I 0 i.j E [m] x [n].
(17)
Then, we estimate f(x) via
f(x)) max (a;, x nz D:
(18)
The 2-block ADMM is summarized in Algorithms] 1 & and Updates 1-4 below. The algorithm uses the augmented Lagrange method and leverages the decomposition of the optimization problem into two blocks that updated iteratively. focusing the primal and dual variables. IiiSaahkamari et al. (2022), it is proven that the 2-block ADMM converges to the ground truth function when + oo and if X is in appropriate region (e.g., X Z V2nd is necessary). The convergence rate is also derived. The algorithm is implemented in Python class Convexlegresiionooelll in our code.
Update
(
1 Σ U
a, 2;
0, (0
0:a +
(19)
n
where
x; -
a; I + -1 +
Σ
x j g
3
0, 4 1
p. P. 77 + D(ass + s1,)(2x; =2,)
Update
2y
ÿ Ω-5
(20)
n2p
where y = -....... Unl 5, 19.9- [..,..., 9n] 8 and
B
Og O,jii
81. 8j,8r
x
X,0; + x
Σ X,O
1
1
Σ
of 2,031
n
n
S2
+ 2 x x
1(i j]
Di.i
n2p
Dij A xx²
A Ai
+
Σ A
Dj
-
x
1 Σ AuZj.
n
b
33

---

Published as a conference paper at ICLR 2025
Algorithm L-update
Require: (%, Ca and p/X
1: knol2n..... knol1 &- sort(7: + 7i - -
2: f X/p
3: I' (-)
4: for 221 to 2n do
5:
f' -- f +
6:
f f f f
(knot, knot
7:
if f I then
return (knot, f 9: end if
8:
10:
end for 11: return (knolen- - 1)+
Algorithm 2 Convex regression
Require: {(z,, U:) [:)] X, and T
I: ú; 5i.j aij
2: L a; p; u; 7) = +- 0xx1
3: for fort=1t
do
4: Update ÿ by Eq. 20
5: Update a, by Eq. 19
6: + L_update (Ti,, ma + 0z he()) A/p)
7: Update un,,, Pi,r, s6. by Eq. 21
8: Update aig 76,1, 2,, by Eq.22 22
9: end for
10: return f()) A max max,=1(aa,. 2x,) 0.)
Update 3.
S. (-ai) - 9: + 00 + (a,, Lz x,))+
(21)
14 = (Li -411 |n,, + a,,1l)
1
P 2
(Li 7/,1 W1, + Mit1 + 04,1)
1
Pt, 2
(LI Y..1 24s1 nhd1 o1.1)
Update 4.
0s =as + 8t.j Ss.j
(22)
1/1 03 (a; 32 xzi)
i,j E [n] [n]
+ 1ign + P... PT.
L i, (n] x [d
=il Thl + 1ip p. + P..
i, [n] x [d]
34

---

Published as a conference paper at ICLR 2025
H STOCHASTIC VARIATIONAL ELBO MAXIMIZATION
The problem of evaluating E[ A at each time step is formulated below. Given any set of M values at time (X m= we assume that the joint distribution of the random variables )) M= are multivariate Gaussian distributions. Inducing points Z = {=))<= with The prior distribution of < .M are randomly sampled from the training dataset (f((Xm) ))
)
(J(A((X))
the function is defined as:
1 iz
-
Kyg Kzz2 K&z
(23)
Kzz
where for and fz are latent functions of and 2, and K is the covariance matrix defined with the Redial Basis Function (RBF) kernel: K = k(s, = o² exp
(=-8') Note that and I are 21
trainable model parameters.
To approximate the posterior distribution p(fsr f= G1 We define variational distribution q(f./ = (f=)) where the marginal variational distribution is also defined with a Gaus- sian: (f=) = (J= E). The observed C {ot 1it.1. fi.1.2 giin M are modeled with Gaussian likelihood that assumes homoskedastic noise is used: p(G [f) N (GG f, n, I), compute the marginal log likelihood and its variational evidence lower bound (ELBO);
log(p () log f
> (gg) [lo CCtt [[>]] DxL. (onn.(((11 (f=2211((22)
(24)
where DKL is the Kullback-Leibe divergence (KLD). The r.h.s. of Eq. 24 is defined as LELBO- Given that the second term of LELBO is independent of training data, an empirical approximation of LELBO for minibatch computation can be found as:
M'
LELBO
Σ Eut. Gogn DKL (nfalla(ffa),
(25)
M'
where M' & M is minibatch size.
After the model training, computing the predictive distribution:
predict the distribution of fnew given set of Fnew by
/ [(Sneul(2))g(AA -
p(Sncw (
(26)
Given that p[Jew fa) is multivariate Gaussian distribution, the solution of Eq, 26 analytical and also a Gaussian. Using Prem = St as inputs we thus approximate E[Ganiy R.] with the mean the predictive distribution, K KnewZ K 7
35

---

Published as a conference paper at ICLR 2025
I SPRI-TANDEM
SPRI-TANDEM is a sequential DRE algorithm specifically designed for conducting SPRT on real- world sequential datasets (Ebihara et al. 2021). It employs feature temporal integrator (TI, Fig. TTp. utilizing either recurrent networks or transformers as Tls. In our experiments, both LSTM (Hochreiter & Schmidhuber 1997) and Transformer (Vaswani al. 2017) are implemented. The TI outputs class posteriors, which are converted to LLRs using the TANDEM formula (Thm. [.I in transitive manner. Initially developed for binary-class, SPRI-TANDEM has been adapted for multiclass classification (Miyagawa & Ebihara 202T), incorporating statistically consistent I.I. estimator, LSEEL (Eq. 13). The LLR saturation problem, notably significant when the absolute value of the ground-trutt truth LLR exceeds 100 nats, has also been addressed (Ebihara et al. 2023).
extractor followed by
A distinctive feature of SPRT-TANDEM is its absence of dedicated loss function for promoting earliness, despite its design for ECTS. This is because the precision in estimating the sufficient statistic (i.e.. LLR) ensures the minimum required data sampling to achieve predefined error rate. Thus, SPRT-TANDEM trained using LSEL (Eq. 13) and multiplet cross-entropy loss (MCF, Def. [.T) without specific loss function for earliness.
Theorem 111 (TANDEM formula). Assuming that X(LT) are N-th order Markov series, Au( Jean be approximated as:
The Te(X
Th (X (x(1 (,
)x((((10)
Σ
log
log
log XkI (27)
Tij
Th (s- (s-
s=N+1
S=N+2
where XkI log(p(y = k) ply 1)) is log class prior probability.
Definition 11 (MCE).
M
(1-T-(N+1--1
JACE = M(T N)
Σ
Σ Σ
(-log Ty. (x/h)-bt1)))
(28)
t=k
X(I)
(()
((3
x(N+1)
x(N+2)
Forward estimation
m(X
x(X
miX X-R1
A TANDEM ( NG xu NJ MI, N.N
25i5E NN < else (
A
Xg
Ax42
AT-3
Ar-2
Ar-1
XT
Figure 11: LLR estimation with SPRT-TANDEM. Feature vectors σ, typically extracted by feature vector extractor network, are sequentially fed into the temporal integrator (TI) network to output class posterior probabilities, ग := ( RK). The TANDEM formula (Eq, I.1 denoted as "TANDEM" in the figure) is used convert these posteriors to LLRs, enabling online sequential update of the estimation.
36

---

Published as a conference paper at ICLR 2025
J FIRMBOUND Is STATISTICALLY CONSISTENT
We provide the full assumptions, the formal statement, and the proof of Thm. 3.2
J.1 ASSUMPTIONS
Most of the necessary assumptions are given in the following Lems. J.1 and Thm. 2.1
Lemma J.1 (CFL is statistically consistent (Prop. in (Siahkamari al. 2022 See App. for notations. With the appropriate choice of X which requires knowledge of the bound on f and n 2 d, it holds that with probability at least 1 - ó over the data. the estimator f of Eq. 18 has excess risk upper bounded by
E [[())) (((1))((1))) So
((7)
log(1/0) (1/))
log
+
299)
See (Siahkamari et al. 2022) for the proof. Note that the bound limits to zero as the dataset size n (denoted by M in the main text) limits to infinity. Note also that d used in this lemma corresponds to the number of classes in the main text.
Lemma J.2 (CFL converges (Thm. 2 in (Siahkamari et al. 2022 )) See App. G for notations. Let (it ) be the output of Alg. 2 at the tth iteration, Vi :- 3 Σi=ı if and ā. x.,) + Ør- Assume max,, [r,,ll and Var 1= 1. If we choose
F Σi d:. Denote
for (x) = max,(ā; x
Vdx²
3 and I 2 nvd.
X
2nd
we have:
3Σ ( -wi + +11ls
((x,) - -.)² + +X1(61)
6nvd + g -1 (30)
min
jeF
where F= {f Rd +R ff convex).
See (iahkkaaari et al. 2022) for the proof. The inputs æ and outputs in the lemma correspond to (T) (x(1))) T (x.. and to G,(F((X((+))) respectively. nu (x(())) for all [K] obviously bounded by one, and thus, the assumption maxi, |æa < 1 is satisfied. Also, the
assumption (ar((y) H=)) < is satisfied because we only consider integrable functions, and the
continuation risk Ge is bounded. As corollary of Lem. J.2 we have:
Lemma J.3 (Convergence rate of CFL (Cor. in (Siahkamari al. 2022 See App. G for notations. The CFL algorithm used in F FIRMBOUND, outlined in App. needs Gnvdd iterations to achieve error. Each iteration requires On ndd) flops operations. Preprocessing costs O(nd)).
Therefore the total computational complexity is 22 5 n2, +nd
Note that n and d used in this lemma correspond to M and K in the main text. See Siahkamari et al. 2022 for the proof.
Next, let us define
dx.1 ((x(.)(()))))))) log 1+ Ee Eedeucxaios)
LISEL
[X]
Σ Σ
(31)
KT
(E[K)EE(T)
1(XA)
Let S = ((. Wi) ~ p(X (1.T) M be training dataset, where M E N is the sample size.
The empirical approximation of Eq. 31
in (w: 5) = KT
Σ EE
Σ log 1+ Σ
-
13
Mr
kE[K] +E[T]
SEL+
[(*A)
Mj and In denote the sample size and index set of class k respectively; i.c., M₁ = [gl = lii
[M]b, = k} and Eg M2 M. Let L(w) and Ls(w) denote LLSEL (A:a:/((;:)))) and ( S), respectively. Let wh be the empirical risk minimizer of lug; namely, ug aargmin, i.s(wr)
37

---

Published as a conference paper at ICLR 2025
Lemma J.4 (LSEL is statistically consistent (Thm. 3.1 in MMyagawa & Ebihara 2021))). Let W :=:- " E IRd 1(X0.));; w-) ((x(1.)) (Vt E {TT) be the target parameter set. Assume, for simplicity of the proof. that each w is separated in w"; i.e,, 38 > O such that B(w"; n B(w"", 55) = 0 for arbitrary w² and w"', where B(w;; 0) denotes an open ball at center w with radius 8. Assume the following three conditions:
(a) Vk. E [K], E (T),P(X(0.)) k)= =0 + +
-(x0,011)= =0
(b) sup (Ls(w)- L(w)l 3 0as M + so; Le., Ls(w) converges in probability uniformly over w to L(w).
(c) For all wt E W", there exist E [T], E [K], and I E [K], such that the following d x matrix is fulk-rank:
i dx ((10) (1.0) k)V w )m(X(1,)) w")V (X w0) =²)
Then, Ip(is & W+) M-x0c, 0: ie., uhs converges in probability into W
See (Miyagawa & Ebihara 2021 for the proof. Assumption (a) ensures that LLRs A(x(1.0) ==
(Aaa(X ) k.Ejk] exists and is finite. Assumption (b) can be satisfied under the standard assump- tions of the uniform law of large numbers (compactness, continuity, measurability, and dominance) (Jennrich, 1969; Newey & McFadden 1986). Assumption (c) is a technical requirement, often assumed the literature (Gutmann Hyvärinen 2012). We additionally assume that the neural net- work represented by w is so large that it can represent target LLRs, which can be satisfied according to the universal approximation theorem of neural networks.
J.2 FORMAL STATEMENT
Now, we provide the formal statement of Thm. 3.2
Theorem J.1 (FIRMBOUND is statistically consistent). Suppose that all the assumptions mentioned in App. J. are satisfied. Suppose that we have the sufficient statistics estimated with LSEL on dataset with size M. Suppose also that we have the continuation risk estimated on with CFL the same dataset. Then, with arbitrary precision, which yields the Bayes optimal terminal decision rule d' and stopping time T", with high probability over the data and as M co.
solve the backward induction equation in Thm. 2.7
J.3 PROOF
We provide the proof of Thm. J.1
Proof. We first show that the CFL combined with the density ratio estimation (DRE) with LSEL yields consistent estimate of function G2-
J.3 & J.2 for any dataset, the output function of the CFL Observation 1. According to Lems.
algorithm can be arbitrarily close to any convex function if 7 .M + oo with P > ((MvK), where 22(-) here denotes Landau symbol. Therefore, according to Lem. J.1 with high probability over the data, the output function of the CFL algorithm can be arbitrarily close to any convex function if T, M + oo with T > Q(M KK).
Observation 2. According to Lem. J.4 the estimated LLRs du can be arbitrarily close to the true LLRs AR as M- + co.
CFL with DRE is consistent. Therefore, according to Observation 1 & 2, with high probability the data, as M + 0o, CFL with DRE can estimate any continuation risk Go at any ((((= (Ii...., R))) because G2 is continuous function of St That is, CFL with DRE is a statistically consistent estimator of Ö,
38

---

Published as a conference paper at ICLR 2025
FIRMBOUND is consistent. Using the estimated continuation risk, we solve the backward induction equation in Thm. 2.1 with arbitrary precision, which yields the Bayes optimal terminal decision rule d' and stopping time r", with high probability over the data and as M This means that F FTRMBOUND (= CFL DRE + backward induction) yields a statistically consistent estimator of the Bayes optimal algorithm in the sense of Thm. 2.1 minimizing AAPR.
39

---

Published as a conference paper at ICLR 2025
K EXPERIMENTAL DETAILS AND SUPPLEMENTARY RESULTS
Throughout the experiments, Optuna (Akiba et al. Parzen Estimator (TPE) (Bergstra al. 2011), ) is used to find the best hyperparameter combinations from the predefined search space. TPE is Bayesian optimization algorithm that models beliefs about the optimal hyperparameters using Parzen Estimation and optimizes the search process using tree-like graph. The training procedure described below is common across all datasets unless specified otherwise.
2019 with the default algorithm, Tree-structured
K.1 1
F TRMBOUND WITH CFL
Our custom code enables hyperparameter tuning at each time step, determining the lambda parameter (not be confused with LLR X; maintain the original notation from (iahkamari al. (2022) for consistency) used in the augmented Lagrangian algorithm. The concave conditional expectation is negated for optimizing CFL models. Adam (Kingma Ba 2014 is employed the optimizer.
Tuning. total of 1000 data points (i.e., posteriors т as the sufficient statistic) are randomly selected from the training dataset. Using Optuna, we search for the optimal lambda at each time step as follows: the initial value of lambdd log-uniformly selected from the range [le - 3, 1e1]. A 5-fold cross-validation, consisting of 3 epochs each, is conducted to evaluate the mean squared error between the predictions and observed data points. This tuning trial is repeated 30 times to ensure comprehensive parameter exploration.
Fitting, A subset of 5000 data points is randomly selected from the training dataset. The optimal lambda parameter, identified from the tuning trials, is used train the final CFL models over epochs on training data, which will be used for future online ECTS. The evaluation of AAPR and SAT curves is conducted 5 times on test data to validate performance.
K.2 F IRMBOOUDD WITH GP REGRESSION
Similar to CFL, GP regression models are trained at each time step t. Adam (Kingma & Ba 2014) is utilized as the optimizer.
Initialization. A Cholesky Variational Distribution is used to estimate the true posterior, initialized with 200 inducing points (i.c., sufficient statistics, either LLRs or posteriors) that are randomly selected from the training dataset. The GP model initialized with constant mean and covariance module, the latter employing a Radial Basis Function (RBF) kernel. A Gaussian likelihood module is also initialized evaluate the Evidence Lower Bound (ELBO).
Fitting. The negative variational ELBO is computed and minimized across minibatches of size 2000. After 30 epochs of training on training data, the predictive distribution is evaluated on all sufficient statistics in the training data assess the conditional expectation. The evaluation of AAPR and SAT curves is repeated 30 times on test data.
Supplementary Results. Fig. 12 shows representative fitting results on the two-class sequential
Gaussian dataset.
K.3 DATASET PREPARATION
Following the methodologies described in Ebihara et al. (202)) and Miyagawa & Ebihara 2021), b, we prepare feature vectors for the SiW and action recognition datasets UCF101/HMDB51 respectively. All pixel values are divided by 127.5 and then subtracted by before feeding into the feature extractor. For the SiW videos, we use ResNet152 version 2 (He et al. 2016a to produce 512-dimensional feature vector (trainable parameters: 3.7M). For the UCF101 and HMDB51 videos, we employ the Pretrained Microsoft Vision Model ResNet50, which is used without fine-tuning to extract 2048- dimensional vector elements (trainable parameters: 23.5M). The train/test split for UCF101 and HMDB51 adheres official splitting pattern #1. A validation set is derived from the training dataset
40

---

Published as a conference paper at ICLR 2025
Cartaria
2
Figure 12:
Typical risk curves estimated with GP regression. Two-class Gaussian distribution
dataset is used to generate observed continuation risk G on which GP models are trained to provide estimations of the conditional expectation.
while maintaining the original class frequency. All videos are clipped or repeated to standardize the time steps 50 and 79, respectively.
Table 3: Extracted datasets.
Orig. dataset
Train set
Val.
Test set
Feat, dim
Time steps
SiW
Liu al.
2018b)
46,729
4,968
43,878
512
50
HMDB51
Kuchnee al.
201
1,026
106
105
2,048
79
UCF101
(Soonoo el al.
2012
35,996
4,454
15,807
2,048
50
FordA
Soomro et al.
2012)
6,600
6,005
12,000
24
20
K.4 TRAINING ECTS MODELS
For real-world datasets lacking ground-truth LLRs, train the DRE model SPRT-TANDEM (Ebi-
hara et al.) 2021) to provide a statistically consistent estimator of LLRs. Additionally, ECTS baseline models, including LSTMms (Ma al. 2016), EARLIEST (Hartvigsen al., 2019). TCN- Transformer (Chen et al., 2022), and CALIMERA (Bilski & Jastrzębska 2023) are trained.
Similar to FIRMBOUND, we utilize Optuna for hyperparameter optimization. The evaluation criterion is the averaged per-class error rate, or mmaro-averaagd recall. A conservative 40% percentile pruner used for early stopping of unpromising parameter combinations. The training settings common across models and databases, along with detailed pruner settings, are provided in Tab. E The choice of optimizer includes Adam (Kingma Ba 2014), RMSprop (Graves) 2013), and Lion (Chen et al.) 2023). An exception is CALIMERA, which are trained with fixed parameters. CALIMERA employs linear and ridge classifiers, which leverage closed-fone solutions for parameter estimation, ensuring deterministic and efficient optimization process that is less prone to the hyperparameter sensitivities often associated with deep learning models.
In subsequent analyses, the coefficient " demonstrates that batch size and learning rate can be scaled equivalently to maintain consistent training dynamics, as per the linear scaling law (Goyal et al. 2017).
41

---

Published as a conference paper at ICLR 2025
Table 4: Common Hyperparameter Tuning Setup
Number of iterations
Number of training data Number of epochs Batch size 40% percentile Number of trials / Number of iterations Number of iterations Number of epochs
Pruner lype
Pruner startup trials
Pruner warmup steps
Pruner interval steps
K.4.1 TWO-CLASS GAUSSIAN DATSET
Table 5: SPRT-TANDEM on two-class Gaussian datset: parameter space.
Hyperparameter
Space
Optimal value
Batch size
200
N.A. (fixed)
Fixed parameters
Epochs
13 7
N.A. (fixed)
# Tuning trials
200
N.A. (fixed)
# Repeated test trials
60
N.A. (fixed)
Learning rate
[10 10-31 x
0.0001
Weight decay Optimizer
[0.0, 10-31
0.0005
(Adam, RMSprop, Lion)
Adam
Order SPRT
[0. 1...., 10)
5
Searched hyperparameters
MCE weight
[0.0, 1.0]
1.0
LLR estim. loss weight
[0.0. 1.0]
0.8
FC activation
(B2Bsqrt, tanh. ReLU, GeLU)
ReLU
Temporal integrator
(LSM,, Transformer]
Transformer
num blocks
[1,3]
Backbone-specke specific parameters
num heads
[2. 4]
4
Dropout
[0.0, 0.5]
0.4
MLP units
[32, 64]
64
FF dim
[32, 64]
64
K.4.2 THREE-CLASS GAUSSIAN DATASET
Table 6: SPRT-TANDEM on three-class Gaussian datset: parameter space.
Hyperparameter
Space
Optimal value
Batch size
200 x 7
N.A. (fixed)
Fixed parameters
Epochs
15 x
N.A. (fixed)
# Tuning trials
200
N.A. (fixed)
# Repeated test trials
30
N.A. (fixed)
Learning rate
[10-6 10 10-3 xy
0.0001
Weight decay Optimizer
[0.0, 10-31
0.00025
(Adam, RMSprop, Lion]
Lion
Order SPRT
(0. 1.....
0
Searched hyperparameters
MCE weight
[.0]
0.7
LLR estim. loss weight
[0.0. 1.0]
0.1
FC activation
[B2Bsqrt, tanh. ReLU, GeLU)
ReLU
Temporal integrator
(LSTM, Transformer)
Transformer
num blocks
[1.
1
heads
[2, 4]
2
Backbone-speciie parameters
Dropout
[0.0. 0.5]
0.3
MLP units
[32, 64]
64
FF dim
[32, 64)
32
42

---

Published as a conference paper at ICLR 2025
K.4.3 SIW
Table 7: SPRT-TANDEM SiW: parameter space.
Hyperparameter
Space
Optimal value
Batch size
83
N.A. (fixed)
Fixed parameters
Epochs
18
N.A. (fixed)
Tuning trials
200
N.A. (fixed)
Repeated test trials
200
N.A. (fixed)
Learning rate
[10- 10 $1 x-y
0.0001
Weight decay
[0.0. 10
0.0
Optimizer
[Adam, RMSprop. Lion)
Adam
Order SPRT
(0, 1,..., 10)
Searched hyperparameters
MCE weight
10.0, 1.01
1.0
LLR estim. loss weight
10.0. 1.0]
1.0
FC activation
[B2Bsqrt, tanh, ReLU, GeLU)
ReLU
Temporal integrator
[LSTM, Transformer
LSTM
Backbone-specific
LSTM output activation
[B2Bsqrt, tanh, GeLU)
B2Bsqit
parameters
LSTM hidden dim.
[32, 256]
256
Table 8: LSTMms on SiW: parameter space.
Hyperparameter
Space
Optimal value
Batch size
100 ?
N.A. (fixed)
Fixed parameters
Epochs
15
N.A. (fixed)
Tuning trials
100
N.A. (fixed)
Repeated test trials
26
N.A. (fixed)
Learning rate
[10 10 xy
0,0011
Weight decay Optimizer
[0.0, 10
0.001
(Adam, RMSprop, Lion)
Lion
Searched hyperparameters
Cross entropy weight
[0.0, 1.0]
1.0
Loss typc
(LSTMm, LSTMs)
LSTMs
Loss weight
[0.0, 1.0]
1.0
LSTM hidden dim.
[32, 512]
Table EARLIEST (lambda=le-1) on SiW: parameter space.
Hyperparameter
Space
Optimal value
EARLIEST param. lambda
1e 1
N.A. (fixed)
Batch size
256 7
N.A. (fixed)
Fixed parameters
Epochs
50
N.A. (fixed)
# Tuning trials
200
N.A. (fixed)
# Repeated test trials
30
N.A. (fixed)
I. Learning rate Weight decay Optimizer
[10-5 10 11
0.000951
Searched hyperparameters
[0.0, 10-")
0.0006
(Adam, RMSprop, Lion|
Lion
LSTM hidden dim.
[32, 256]
16
43

---

Published as a conference paper at ICLR 2025
Table 10: EARLIEST (lambda=1c-10) on SiW: parameter space.
Hyperparameter
Space
Optimal value
EARLIEST param. lambda
1c 10
N.A. (fixed)
Batch size
256 x 7
N.A. (fixed)
Fixed parameters
Epochs
N.A. (fixed)
# Tuning trials
200
N.A. (fixed)
# Repeated test trials
30
N.A. (fixed)
Learning rate
[10 10 10 x
0.000441
Searched hyperparameters
Weight decay Optimizer
[0.0, 10
0.001
(Adam, RMSprop, Lion)
RMSprop
LSTM hidden dim.
[32, 256]
16
Table 11: TCNT (alpha=0.3) on SiW: parameter space.
Hyperparameter
Space
Optimal value
TCNT param. alpha
0.3
N.A. (fixed)
Batch size Epochs
256 7
N.A. (fixed)
Fixed parameters
N.A. (fixed)
Tuning trials
100
N.A. (fixed)
# Repeeted test trials
30
N.A. (fixed)
Learning rate
[10-6, 10-31 xy
0,00425
Weight decay Dropout Optimizer
[0.0, 10 10-*]
0.0003
Searched hyperparameters
[0.0, 0.5]
0.3
(Adam, RMSprop. Lion]
Lion
# Blocks
[1.3]
Num heads
[2.4] 4]
TCN channels
[256, 1024]
256
Table 12: TCNT (alpha=0.5) SiW: parameter space.
Hyperparameter
Space
Optimal value
TCNT param. alpha
0.5
N.A. (fixed)
Batch size Epochs
256 Y
N.A. (fixed)
Fixed parameters
N.A. (fixed)
Tuning trials
N.A. (fixed)
Repeated test trials
30
N.A. (fixed)
Learning rate
[10-6, 10-31 x
0.000002
Weight decay
[0.0, 10-31
0.000
Searched hyperparameters
Dropout Optimizer
[0.0, 0.5]
(Adam, RMSprop, Lion)
Lion
# Blocks
[1.3]
1
# Num heads
[]
4
TCN channels
[256. 512]
32
Table 13: CALIMERA on SiW: parameter space.
Hyperparameter
Space
Optimal value
Fixed parameters
Delay penalty
0.51
N.A. (fixed)
# Repeated test trials
5
N.A. (fixed)
44

---

Published as a conference paper at ICLR 2025
K.4.4 HMDB51
Table 14: SPRT-TANDEM HMDB51; parameter space.
Hyperparameter
Space
Optimal value
Batch size
128 x
N.A. (fixed)
Fixed
Epochs
24
N.A. (fixed)
parameters
Tuning trials
200
N.A. (fixed)
Repeated test trials
N.A. (fixed)
Learning rate
[10 6, 10 10-00010 x7
10 10-4
Weight decay
[0.0, 10
10 10-4
Optimizer
[Adam, RMSprop. Lion)
Adam
Order SPRT
[0, 1..... 10]
Searched hyperparameters
MCE weight
[0.0. 1.0]
0.1
L.R estim. loss type
(LLLR, LSEL)
LSEL.
LLR estim. loss weight
10.0, 1.01
1.0
FC activation
(B2Bsqrt, tanh, ReLU, GeLU)
tanh
Temporal integrator
[LSTM, Transformer
LSTM
Backbone-specific
LSTM output activation LSTM hidden dim.
(B2Bsqrt, tanh, GeLU)
B2Bsqrt
parameters
[32, 256]
256
Table 15: LSTMms on HMDB: parameter space.
Hyperparameter
Space
Optimal value
Batch size
100 7
N.A. (fixed)
Fixed parameters
Epochs
15
N.A. (fixed)
Tuning trials
100
N.A. (fixed)
Repeated test trials
20
N.A. (fixed)
Learning rate
[10 10-31 x
0.000594
Weight decay Optimizer
[0.0, 10 (0-"]
0,0009
(Adam. RMSprop, Lion]
Lion
Searched hyperparameters
Cross entropy weight
[0.0. 1.0]
0.7
Loss type
(LSTMm, LSTMs)
LSTMm
Loss weight
[0.0, 1.0]
LSTM hidden dim.
[32, 512]
282
Table 16: EARLIEST (lambda=le-1) on HMDB51: parameter space.
Hyperparameter
Space
Optimal value
EARLIEST param. lambda
1e 1
N.A. (fixed)
Batch size
256 7
N.A. (fixed)
Fixed parameters
Epochs
50
N.A. (fixed)
# Tuning trials
200
N.A. (fixed)
# Repeated test trials
30
N.A. (fixed)
I. Learning rate Weight decay Optimizer
[10-5 10 10
0.000273
Searched hyperparameters
[0.0, 10-")
0.0009
(Adam, RMSprop, Lion]
RMSprop
LSTM hidden dim.
[32, 256]
159
45

---

Published as a conference paper at ICLR 2025
Table 17: EARLIEST (lambda=1e-10) on HMDB51: parameter space.
Hyperparameter
Space
Optimal value
EARLIEST param. lambda
1c 10
N.A. (fixed)
Batch size
256 x 7
N.A. (fixed)
Fixed parameters
Epochs
N.A. (fixed)
# Tuning trials
200
N.A. (fixed)
# Repeated test trials
30
N.A. (fixed)
Learning rate
[10 10 10 x
0,000148
Searched hyperparameters
Weight decay Optimizer
[0.0, 10
0,000
(Adam, RMSprop, Lion]
Lion
LSTM hidden dim.
[32, 256]
147
Table 18: TCNT (alpha=0.3) on HMDB51: parameter space.
Hyperparameter
Space
Optimal value
TCNT param. alpha
0.3
N.A. (fixed)
Batch size
256 7
N.A. (fixed)
Fixed parameters
Epochs
N.A. (fixed)
Tuning trials
300
N.A. (fixed)
# Repeeted test trials
10
N.A. (fixed)
Learning rate
[10-6, 10-31 xy
0,000776
Weight decay Dropout Optimizer
[0.0, 10 10-*]
0.000
Searched hyperparameters
[0.0, 0.5]
0.1
(Adam, RMSprop. Lion]
Adam
# Blocks
[1.3]
Num heads
[2.4] 4]
TCN channels
[256, 1024]
1024
Table 19: TCNT (alpha=0.5) HMDB51: parameter space.
Hyperparameter
Space
Optimal value
TCNT param. alpha
0.5
N.A. (fixed)
Batch size Epochs
256 Y
N.A. (fixed)
Fixed parameters
N.A. (fixed)
Tuning trials
300
N.A. (fixed)
Repeated test trials
10
N.A. (fixed)
Learning rate
[10-6 10 10-31 x
0.000453
Weight decay
[0.0, 10-31
0.010
Searched hyperparameters
Dropout Optimizer
[0.0, 0.5]
(Adam, RMSprop, Lion)
Adam
# Blocks
[1.3]
# Num heads
[].4]
4
TCN channels
[256. 1024]
1024
Table 20: CALIMERA on HMDB51: parameter space.
Hyperparameter
Space
Optimal value
Fixed parameters
Delay penalty
0.51,0.5,1.0)
N.A. (fixed)
# Repeated test trials
5
N.A. (fixed)
46

---

Published as a conference paper at ICLR 2025
K.4.5 UCF101
Table 21: SPRI-TANDEM on UCFI01: parameter space.
Hyperparameter
Space
Optimal value
Batch size
16 x y
N.A. (fixed)
Fixed parameters
Epochs
25
N.A. (fixed)
# Tuning trials
200
N.A. (lixed)
# Repeated test trials
14
N.A. (fixed)
Learning
[10 10 91 xy
0.000027
Weight decay
[0.0, 10
0.0006
Optimizer
(Adam, RMSprop. Lion]
Lion
Order SPRT
(0. I..... 10]
6
MCE weight
[0.0. 1.0]
0.2
Searched hyperparameters
LLR estim. loss type
(LSEL, LLLR)
LSEL
LLR estim. loss weight
[0.0, 1.0]
0.4
FC activation
(B2Bsqrt, tanh, ReLU, GeLU)
tanh
Temporal integrator
[LSTM, Transformer]
Transformer
# Blocks
[]
1
Backbone Backbone-specific parameters
# Heads
4]
4
Dropout
[0.0, 0.5]
0.1
MLP_units units
[256, 416]
288
FF FF_dim
[256, 416]
256
Table 22: LSTMms UCFI01: parameter space.
Hyperparameter
Space
Optimal value
Batch size Epochs
100
N.A. (fixed)
Fixed parameters
15
N.A. (fixed)
Tuning trials
100
N.A. (fixed)
Repeated test trials
11
N.A. (fixed)
Learning rate
[10 10031111110 xy
0,000184
Weight decay Optimizer
[0.0, 10-31
0.008
(Adam, RMSprop. Lion)
RMSprop
Searched hyperparameters
Cross entropy weight
[0.0, 1.0]
Loss type
(LSTMm, LSTMs)
LSTMs
Loss weight
[0.0, 1.0]
0.4
LSTM hidden dim.
[32, 512]
362
Table 23: EARLIEST (lambda=le-1) on UCF101: parameter space.
Hyperparameter
Space
Optimal value
EARLIEST param. lambda
1e 1
N.A. (fixed)
Batch size
256 7
N.A. (fixed)
Fixed parameters
Epochs
50
N.A. (fixed)
# Tuning trials
200
N.A. (fixed)
# Repeated test trials
30
N.A. (fixed)
I. Learning rate Weight decay Optimizer
[10-5 10 10
0.000026
Searched hyperparameters
[0.0, 10-1) "0
0.0005
(Adam, RMSprop, Lion|
Lion
LSTM hidden dim.
[32, 256]
238
47

---

Published as a conference paper at ICLR 2025
Table 24: EARLIEST (lambda=le-10) on UCFI01: parameter space.
Hyperparameter
Space
Optimal value
EARLIEST param. lambda
1c 10
N.A. (fixed)
Batch size
256 x 7
N.A. (fixed)
Fixed parameters
Epochs
N.A. (fixed)
# Tuning trials
200
N.A. (fixed)
# Repeated test trials
30
N.A. (fixed)
Learning rate
[10 10 10 x
0,000758
Searched hyperparameters
Weight decay Optimizer
[0.0, 10
0.0006
(Adam, RMSprop, Lion]
RMSprop
LSTM hidden dim.
[32, 256]
196
Table 25: TCNT (alpha=0.3) on UCF101: parameter space.
Hyperparameter
Space
Optimal value
TCNT param. alpha
0.3
N.A. (fixed)
Batch size Epochs
256 7
N.A. (fixed)
Fixed parameters
N.A. (fixed)
Tuning trials
300
N.A. (fixed)
# Repeeted test trials
15
N.A. (fixed)
Learning rate
[10-6, 10-31 xy
0,000585
Weight decay Dropout Optimizer
[0.0, 10 10-3]
0.001
Searched hyperparameters
[0.0, 0.5]
0.1
(Adam, RMSprop. Lion]
Adam
# Blocks
[1.3]
Num heads
[2.4] 4]
TCN channels
[256, 1024]
512
Table 26: TCNT (alpha=0.5) UCF101: parameter space.
Hyperparameter
Space
Optimal value
TCNT param. alpha
0.5
N.A. (fixed)
Batch size Epochs
256 Y
N.A. (fixed)
Fixed parameters
N.A. (fixed)
Tuning trials
300
N.A. (fixed)
Repeated test trials
15
N.A. (fixed)
Learning rate
[10-6 10 10-31 x
0.001 106
Weight decay
[0.0, 10-31
0.001
Searched hyperparameters
Dropout Optimizer
[0.0, 0.5]
(Adam, RMSprop, Lion)
Adam
# Blocks
[1.3]
# Heads
[].4]
4
TCN channels
[256. 1024]
512
Table 27: CALIMERA UCF: parameter space.
Hyperparameter
Space
Optimal value
Fixed parameters
Delay penalty
0..1,
N.A. (fixed)
# Repeated test trials
5
N.A. (fixed)
48

---

Published as a conference paper at ICLR 2025
K.5 COMPUTING INFRASTRUCTURE
All experiments were carried out using custom Python scripts on NVIDIA GeForce RTX 2080 Ti graphies cards. For mathematical computations, Numpy (Harris al. 2020) and Scipy (Virtanen et al. 2020) were employed. Machine learning frameworks used include py Torch 2.0.0 (Paszke et al. 2019 and TensorFlow 2.8.0 (Abadi al. 2015). Gaussian process regression was performed using stochastic variational inference in GPyTorch (Gardner et al. 2018).
49

---

Published as a conference paper at ICLR 2025
L ON HYPERPARAMETER SENSITIVITY OF FIRMBOUND
Our algorithm either requires minimal hyperparameter tuning or can be easily tuned on the training dataset. Below is a list of major hyperparameters for the two approaches:
Convex Function Learning (CFL)
Lambda
Number of training data for tuning
Number of training data for fitting Tuning trials
Epochs
Gaussian Processes (GP)
Kernel type
Number of inducing points
Batch size
Learning rate
Optimizer
Epochs
The most critical hyperparameter the lambda parameter (do not confuse with the LLR the baseline model EARLIEST's hyperparameter) in CFL, which controls the flexibility of the fitting curves. As described in the Sec. []] we keep the other hyperparameter settings consistent across all datasets. including i.i.d., non-i.i.d., artificial, and real-world. Our experiments show that FIRMBOUND reliably minimizes the average posteriori risk (AAPR) delineate the Pareto front.
As an additional experiment for hyperparameter sensitivity, we tested GP approach with varying kernel and number of inducing points using the two-class Gaussian dataset (Fig. [T3]. The number of inducing points is varied from the default 200 to 50 and 1000, while keeping the original Radial Basis Function (RBF) kernel. Alternatively, the number inducing points fixed 200, and Matérn kernel is used instead of RBF. Matérn kernel is generalization of RBF kernel with parameter controlls its smoothness. As approaches to infinity, Matérn kernel converges to the RBF kernel. In Fig. 13 values, 1.5 and 2.5, used the parameter Cost parameter is I./T. The results are robust against any of the above hyperparameters, while Matérn kernel slightly off from the optimality (also Fig. (5 and Ga of the main manuscript).
50

---

Published as a conference paper at ICLR 2025
GP on Gaussian 2class datasets with varying nyperparameters
35
10.6
RBF ind50
30
*
RBF ind200 (default)
RBF ind1000
*
Mater Matem_nul.$ _aapeuuull___a__e $__d22000
70
71
10.0
*
Matem_nun _utmmm_u225..cm 5__d2000
15
10
%
10
20
30
40
50
Mean hitting time framee))
Figure 13: GP's hyperparameter sensitivity test on the two-class Gaussian dataset. The number of inducing points is varied from 50 to 1000, with the Radial Basis Function (RBF) kernel, or fixed at 200 using the Matérn kernel with values of 1.5 and 2.5. Note that converges to the RBF kernel. c L/T.
51

---

Published as a conference paper at ICLR 2025
M AAPR ON BASELINE MODELS
In this section, we demonstrate that ill-calibrated ECTS models can misleadingly exhibit small AAPRs. LSTMms, EARLIEST, and TCa-Transformer models were trained the two-class Gaussian dataset and evaluated using two performance criteria: AAPR and the SAT curve. As shown in Fig T4h, while LSTMms achieves lower AAPR than FIRMBOUND and SPRT-TANDEM, which maintain well-calibrated statistics, it is outperformed by them in termss of the SAT curve (i.e., ECTS results). This discrepancy arises from overconfidence, which inflates the statistic beyond the calibrated level. Consequently, AAPR alone does not reliably predict SAT performance when using ill-calibrated statistic. Notably, RMBOUND records the minimal AAPR across all models.
AAPR curve on the two class Gaussten dataset. L/T (n)
SAT curve on the two class Gaussian dacaset
L/T F FIRMBOUND (CFL)
posterts rak
16
on estimated V
L/T an estimated A
FIRMBOUND (GP)
Moan par dasss en00
76
L/T
Vanilla SPRT
estimated
12
LSTMms
EARLIEST
TCNTranstormer
CALIMERA
20 30 Mean hitting (#frames)
40
50
100
40
Mcon hitting time (eframes)
Figure 14: AAPR and SAT curve with other ECTS algorithms. ECTS algorithms, LSTMms, EARLIEST, and TCN-TRer Transformer are used to compare the two evaluation criteria on the two-class sequential Gaussian dataset.
52

---

Published as a conference paper at ICLR 2025
N PARAMETER SPACE OF L AND
Here, we prove that the possible parameter search space of coefficients L = L (for all E [K] and с of APR confined, and thus, we only need consider ratio of and c. First, given that the continuation risk (T( concave and G. = Gx(z 1) c, the maximum value of the stopping risk Gf (T) needs to be larger than c in order to have more than one intersection (i.e., threshold):
1
max m (T)((())))))
L 1 > C,
K
(32)
where K is the number of classes.
Second, the intersections of the risk functions (x( and G7 (TT) remain invariant under the scaling transformation of L and c by a factor a E Igz- Specifically, at t T.
GT; = min { aL (1 TT (x( k
a T, (1 TT (x
aG (c)
(33)
thus,
(T; (T;
=aGT (T; L.
(34)
then at =T
GT-((T;aL, ac) = ElGTiin ac)) [X (X(I.T)) + ae
ElaGTiu mmin (T; (T) + ac
E(Grii LT;
(T;
(35)
Gpin (T; aL) min (rin
min Gost (TT
- L.c)
(36)
holds true for scaling factor a E R. By induction, the above linearity holds true for general f < T. Given that the threshold is defined the intersection of Gst and G. scaling L and by constant does not alter the threshold.
To equalize the magnitudes of the terms APR (Eq, 3). we Caef L/T the default in our experiments. This choice consistently balances the speed-accuracy tradeoff and minimizes APR, as elaborated in Sec. 4
53

---

Published as a conference paper at ICLR 2025
O ABLATION STUDY DETAILS
As stated in the main manuscript, vanilla SPRT with static threshold, whether applied to true LLRs or estimated LLRs, is crucial for our ablation studies. Figures a demonstrate that SPRT with a static threshold can lead to either a larger APR or suboptimal speed-accuracy tradeoff. In this supplementary section on ablation studies, we detail the other two conditions tested: random stopping times and artificial tapering thresholds.
Random stopping times. To establish a chance-level baseline, we randomly generate integers of size M within the range [l...., 7'] to use stopping times. This experiment is repeated five times, with the computed AAPR and SAT points plotted in Fig. These points typically fall in the middle of the figures, delineating the chance levels.
Artificial tapering thresholds. Optimal stopping theory suggests that the optimal threshold com- puted with backward induction typically descends monotonically as approaches the finite hori- zon (Tartakovsky et al. 2014). This insight motivates us to create artificial decision thresholds as economical alternatives. The following power function with &. 1155, O, 1.5 is used to generate concave, linear, and convex curves, respectively (Fig. 15
((AAT,,))) A A
(37)
Resulting AAPR and SAT plotted in Fig.
The magnitude A is set a, 2/2/a, 0 where
max (X(X whose result corresponding to the three points in Fig. 7
Example tapering thresholds
1.5
30
- 1.5
25:
nognitude
10:
0
10
20
30
40
50
Time steps (Nframes)
Figure 15: Tapering thresholds generated with the power function. According to Eq. 37 concave, linear, and convex tapering threshold are generated with {-1.5, 0, 1.5), respectively.
54

---

Published as a conference paper at ICLR 2025
P DUMPED OSCILLATING LOG-LIKELIHOOD RATIO FUNCTION
To simulate non-i.idd., non-monotonic LLR trajectories, we generate binary class LLRs according to
Eq. 38
(1 1 1 exp(x)
^(1) =
+ Aexp(-3t) sin(w + (0,
(38)
where 7 E 1-1,1} corresponds to class targets that the trajectories asymptotically approach. A, B, and denote the oscillation amplitude, damping coefficient, and angular frequency of the wave, respectively, a indicates the noise level. Example trajectories are depicted in Fig. 16
The parameters and their respective prior distributions used in this study detailed in Tab. 28 The notation N (1, a)) represents a Gaussian (normal) distribution with mean and standard deviation a.
The notation ((, b) denotes a uniform distribution sampled within the interval [a. 6].
Table 28: Parameter space of DOL dataset.
Parameter
Distribution
A
Gaussian M(p = 2, 2)
Uniform (0.022, 0.2)
Uniform (2(3)))
K
Uniform MI 225,, 0)
Gaussian ((p 0.0, 1.0)
Damped oscillating non-i.i.d. LLRs
log-likelihood ratio
2.
40
Time steps (#frames)
Figure 16: Tapering thresholds generated with the power function (Eq. 38 Note that the
trajectories are generated at a higher sampling rate just for visualization purposes. In the experiment, sample points at each time step E 1,.... T.
55

---

Published as a conference paper at ICLR 2025
Q SUPPLEMENTARY EXPERIMENT ON THE UCR FORDA DATASET
To test FIRMBOUND's ' risk minimization capability on continuous signals, we conduct additional experiments on the UCR FordA dataset. FordA time series binary classification dataset with 500 samples. Each time series is sliced into non-overlapping segments of 100 time steps. Then each 100-step segment was further processed using a sliding window approach with a window size of 24 and stride of 4. This resulted in multiple windows per segment:
The number of windows W generated from each segment is calculated as:
W
+
20
4
Therefore, each 100-step segment was transformed into 20 windows, each of length 24.
The resulting data are reshaped into a 3-dimensional array with dimensions (M x x 24), where M the number of original time series (6,600 and 18,005 for training and test dataset, respectively). T = 20 is time steps, or the number of windows per segment, and 24 is the feature dimension, or the window length.
The result shows that TIRMOONDD find minima of AAPR to optimize the speed-accuracy tradeoff, as shown in Fig.
Speed-accuracy tradeoff curve
Average posteriri fie IAAPHI carve
1.20
5.20
4.5
5.22
1.2
515
75
10.5
17%
15:01
17.
300
7.5
5:2
100
17%
11.8
17%
Figure 17: AAPR and SAT curves UCR FordA dataset. FIRMBOUND effectively find minima of AAPR to optimize the speed-accuracy tradeoff.
56

---

Published as a conference paper at ICLR 2025
SUPPLEMENTARY REFERENCES
M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp. G. Irving, M. Isard, Y. Jia, R. Jozefowiez. L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, Shlens, B. Steiner, Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. Software available from tensorflow.org.
S. Ahmad and A. J. Yu. Active sensing as opyesal sequential decision-making. In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, UAI'13, pp- 12 12-21, Arlington, Virginia, USA, 2013. AUAI Press.
P. Armitage. Sequential analysis with more than two alternative hypotheses, and its relation to discriminant function analysis. Journal of the Royal Statistical Society. Series B (Methodological), 12(1):137-144, 1950.
H. Asano. Sequential bayesian experimental designs via reinforcement learning. arXiv preprint arXiv:2202.07472, 2022.
C. Atkinson, B. McCane, L. Szymanski, and A. V. Robins. Pseudo-rchearsal: Achieving deep reinforcement learning without catastrophic forgetting. Neurocomputing. 428:291-300 2018.
D. M. Bashtannyk and R. J. Hyndman. Bandwidth selection for kernel conditional density estimation. Computational Statistics & Data Analysis, 36:279-296 2001.
C. W. Baum and V. V. Veeravalli. sequential procedure for multihypothesis testing. IEEE Transactions on Information Theory, (966::199-20077 Nov 1994.
J. Bjorck, C. P. Gomes, and K. Q. Weinberger. Is high variance unavoidable in RL? case study in continuous control. ArXiv, abs/2110. 12222 2021.
T. Blau, E. V. Bonilla, I. Chades, and A. Dezfouli. Optimizing sequential experimental design with deep reinforcement learning. In International Conference on Machine Learning, pp. 2107-2128. PMLR, 2022.
Z. Botev, J. Grotowski, and D. Kroese. Kernel density estimation via diffusion. The Annals of Statistics, 38, 11 2010.
A. Brockwell and J. J. B. Kadane. A gridding method for bayesian sequential decision problems. Journal of Computational and Graphical Statistics, 12:566 584, 2003.
Q. Candela and C. E. Rasmussen. A unifying view of sparse approximate Gaussian process regression. J. Mach. Learn. Res., 6:1939-1955 1959, 2005.
E. Cetin, J. Ball, S. Roberts, and O. Çeliktutan. Stabilizing off-policy deep reinforcement learning from pixels. In International Conference on Machine Learning. 2022.
X. Chen, C. Liang, D. Huang, E. Real, K. Wang, H. Pham, X. Dong, T. Luong, C.-J. Hsieh, Y. Lu, and Q. V. Symbolic discovery of optimization algorithms. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, Curran Associates, Inc., 2023.
volume 36, pp.
H. Chernoff. Sequential design of experiments. The Annals of Mathematical Statistics, 30(3): 755-770, 1959.
A. K. Churchland, R. Kiani, and M. N. Shadlen. Decision-making with multiple alternatives. Nature Neuroscience, 11:693-702, 2008.
D. A. Cohn, 7. Ghahramani, and M. I. Jordan. Active learning with statistical models. ArXiv, 11/9666033 1996.
M. P. Deisenroth and W. Ng. Distributed Gaussian processes. International Conference on Machine Learning, 2015.
57

---

Published as a conference paper at ICLR 2025
D. K. Dennis, C. Pabbaraju. H. V. Simhadri, and P. Jain. Multiple instance learning for efficient sequential data classification on resource-constraingg devices. Proceedings of the 32nd Interna- tional Conference Neural Information Processing Systems, NIPS' 18, pp. 10997610987, Red Hook, NY, USA, 2018. Curran Associates Inc.
K. Doya. Modulators of decision making. Nat. Neurosci., 11(4):410-41, Apr 2008.
V. Dragalin, G. Tartakovsky, and V. V. Veeravalli. Multihypothesis sequential probability ratio tests. i. asymptotic optimality. IEEE Transactions on Information Theory, 45(7):2448825)0 November 1999.
V. Dragalin. Asymptotic solution of a problem of detecting a signal from k channels. Russian Mathematical Surveys, 42(3):213, 1987.
V. Dragalin and A. Novikov. Adaptive sequential tests for composite hypotheses. Survey of Applied and Industrial Mathematics, 6:387-398, 1999.
Drugowitsch, R. Moreno-Bote, A. K. Churchland, M. N. Shadlen, and A. Pouget. The cost of accumulating evidence in perceptual decision making. The Journal of Neuroscience, 32:3612- 3628, 2012.
T. Duan, J. Zhao, S. Zhang, J. Tao, and P. Wang. Representation learning of tangled key-value sequence data for early classification. 2024 40th IEEE International Conference on Data Engineering, 2024.
S. Ferguson. Optimal stopping and applications, 2006.
Frazier and A. J. Yu. Sequential hypothesis testing under stochastic deadlines. In Platt, D. Koller, Y. Singer, and Roweis (eds.), Advances Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
J. P. Gallivan, C. S. Chapman, D. M. Wolpert, and J. R. Flanagan. Decision-making in sensorimotor control. Nat. Rev. Neurosci., 19(9):519-534 09 2018.
J. I. Gold and M. N. Shadlen. The neural basis of decision making. Annu. Rev. Neurosci., 30:535-574, 2007.
P. Goyal, P. Dollár, R. B. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia, and K. He. Accurate, large minibatch SGD: training imagenet in hour. CoRR, abs/1706.02677, 2017.
A. Graves. Generating sequences with recurrent neural networks. arXiv preprint arXiv: 10XXv:133..08000 2013.
M. U. Gutmann and A. Hyvärinen. Noise-contrastive estimation of unnormalized statistical models, with applications natural image statistics. The journal machine learning research, 13(1): 307-361, 2012.
T. D. Hanks, R. Kiani, and M. N. Shadlen. A neural mechanism of speed-accuracy tradeoff in macaque area lip. eLife, 3, 2014.
C. R. Harris, K. J. Millman, S. J. van der Walt, R. Gommers, P. Virtanen, D. Cournaeea,, E. Wieser, Taylor, Berg, N. Smith, R. Kern, M. Picus, Hoyer, M. van Kerkwijk, M. Brett, A. Haldane, J. F. Del Río, M. Wiebe, P. Peterson, P. Gérard-Marchant K. Sheppard, T. Reddy, W. Weekesser. H. Abbasi, C. Gohlke, and E. Oliphant. Array programming with NumPy. Nature, 38577825)3377336, 09 2020.
Hartvigsen, W. Gerych, Thadajarassiri, Kong, and Rundensteiner. Stop&hop: Early classification of irregular time series. In CIKM, 2021.
Hensman, A. G. de G. Matthews, and Z. Ghahramani. Scalable variational Gaussian process classification. In International Conference on Artificial Intelligence and Statistics, 2014.
S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural Comput., 1735 1997.
58

---

Published as a conference paper at ICLR 2025
N. Houlsby, F. Huszár, Z. Ghahramani, and M. Lengyel. Bayesian active learning for classification and preference learning. ArXiv, abs/1 12..5745, 2011.
A. Irle and N. Schmitz. On the optimality of the sprt for processes with continuous time parameter. Statistics: A Journal of Theoretical and Applied Statistics, 15(1):91-104, 1984.
H. Ismail Fawaz, G. Forestier, J. Weber, L.. Idoumghar, and P.-A. Muller. Deep learning for time series classification: a review. Data Mining and Knowledge Discovery, 33(4):917-963, July 2019. ISSN 1573-756X.
D. Jarrett and M. der Schaar. Inverse active sensing: Modeling and understanding timely decision-making. ArXiv, 14141,, 2020.
R. I. Jennrich. Asymptotic properties of non-linear least squares estimators. Ann. Math. Statist,, 40 (2):633-64) 04 1969.
B. Kadane and P. K. Vlachos. Hybrid methods for calculating optimal few-stage sequential strategies: Data monitoring for a clinical trial. Statistics and Computing, 12:147-152, 2002.
J. Kiefer and J. Sacks. Asymptotically optimum sequential inference and design. The Annals of Mathematical Statistics, pp. 705-750, 1963.
D. P. Kingma and J. Ba. Adam: method for stochastic optimization. arXiv preprint arXiv: 1412.698.. 2014.
S. Kira, T. Yang, and M. N. Shadlen. A neural implementation of wald's sequential probability rato test. Neuron, 8514)38 February 2015.
Kira, A. Zylberberg. and M. N. Shadlen. Incorporation of cost deliberation time in perceptual decision making. bioRxiv, 2024.
S. Kleinegesse, C. Drovandi, and M. Gutmann. Sequential bayesian experimental design for implicit models via mutual information. Bayesian Analysis. -1, 07 2020.
D. Kroese, T. Taimre, and Botev. Handbook of Monte Carlo Methods. Wiley Series in Probability and Statisties. Wiley, 2011. ISBN 9780470177938.
A. Kumar, A. Gupta, and S. Levine. DisCor: Corrective feedback in reinforcement learning via distribution correction. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2020.
L. Lai. Asymptotic optimality of invariant sequential probability ratio tests. The Annals of Statistics, pp. 318-333, 1981.
K. W. Latimer, J. L. Yates, M. L. Meister, A. C. Huk, and J. W. Pillow. Single-trial spike trains in parietal cortex reveal discrete steps during decision-making Science, 34966244)184-187,, Jul 2015.
D. D. Lewis and W. A. Gale. A sequential algorithm for training text classifiers. In Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 1994.
G. Lorden. Nearly-optimal sequential tests for finitely many parameter values. Annals of Statistics, 5: 1-21, 01 1977.
Lv, Y. Chu, J. Hu, Li, and X. Hu. Second-order confidence network for early classification of time series. ACM Transactions on Intelligent Systems and Technology, 2023.
C. Martinez, E. Ramasso, G. Perrin, and M. Rombaut. Adaptive carly classification of temporal sequences using deep reinforcement learning. Knowledge-Bonl Based Systems, 19090,, 2020. ISSN 0950-7051.
T. Miyagawa and A. F. Ebihara. The power of log-summexpp Sequential density ratio matrix estimation for speed-accuracy optimization. In Proceedings of the 38th International Conference on Machine Learning, pp. 7792-7804, 2021.
59

---

Published as a conference paper at ICLR 2025
U. Mori, A. Mendiburu, S. Dasgupta, and J. A. Lozano. Early classification of time series by simultaneously optimizing the accuracy and earliness. IEEE Transactions on Neural Networks and Learning Systems, (9(1))4569 4578, Oct 2018. ISSN 2162-237X.
U. Mori, A. Mendiburu, Dasgupta, and A. Lozano. Early classification of time series from a cost minimization point of view. In Proceedings of the NIPS Time Series Workshop, 2015.
Müller, D. A. Berry, bayesian design. Journal of Statistical Planning and Inference, 137:3140 17:3110--110, 2007.
Grieve, M. Smith, and M. Krams. Simulation- sequential
M. Naghshvar and T. Javidi. Active sequential hypothesis testing. The Annals of Statistics, 41(6): 2703-2738, 2013. ISSN 00905364, 21688966.
J. Najemnik and W. S. Geisler. Optimal eye movement strategies in visual search. Nature, 434: 387-391, 2005.
W. Newey and D. McFadden. Large sample estimation and hypothesis testing. In R. Engle and D. McFadden (eds.), Handbook of Econometrics, volume 4, chapter 36, pp. 2111-2245. Elsevier, edition, 1986.
E. Nikishin, Izmailov, B. Athiwaratkun, D. Podoprikhin, Garipov, Shvechikov, D. Vetrov, and A. G. Wilson. Improving stability in deep reinforcement learning with weight averaging, In Uncertainty in artificial intelligence workshop on uncertainty in Deep learning. 2018.
G. Okazawa, C. E. Hatch, A. Mancoo, C. K. Machens, and R. Kiani. The geometry of the representa- tion of decision variable and stimulus difficulty in the parietal cortex. bioRxiv, 2021.
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024 8035. Curran Associates, Inc., 2019.
E. Paulson. A sequential decision procedure for choosing one of k hypotheses concerning the unknown mean of a normal distribution. The Annals of Mathematical Statistics, pp. 549-554, 1963.
Pavlov. Sequential procedure of testing composite hypotheses with applications to the kiefer- weiss problem. Theory Probability & Its Applications, 35(2):280-22) 292- 1991.
Pavlov. Sequential decision rule for the case of many complex hypotheses. ENG. CYBER, (6): 19-22, 1984.
B. Rhodes, Xu, and M. Gutmann. Telescoping density-ratio estimation. In NewrIPS, volume 33, pp. 9905-4916; 4916, 2020.
C. Robert and G. Casella. Monte Carlo statistical methods. Springer Verlag, 2004.
D. Roitman and M. N. Shadlen. Response of neurons in the lateral intraparietal area during a combined visual discrimination reaction time task. J. Neurosci., (1111))947--9999 Nov 2002.
M. Rosenblatt. Conditional probability density and regression estimators. In R. Krishnaiah (ed.), Multivariate analysis, II, pp. 25-31. Academic Press, New York, 1969. (Dayton, OH, 17-22 June 1968). MR:254987.
D. Rossell, P. Müller, and G. L.. Rosner. Screening designs for drug development. Biostatistics, 8 3: 595-608, 2007.
D. Scott. Multivariate Density Estimation: Theory, Practice, and Visualization. A Wiley-interscience publication. Wiley, 1992. ISBN 9780471547709.
O. Sener and S. Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv: Machine Learning, 2017.
60

---

Published as a conference paper at ICLR 2025
H. S. Seung, M. Opper, and H. Sompolinsky. Query by committee. In Annual Conference Computa- tional Learning Theory. 1992.
A. Siahkamari, D. A. E. Acar, C. Liao, K. L. Geyer, V. Saligrama, and B. Kulis. Faster algorithms for learning convex functions. K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and
S. Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 20176-20194, PMLR, 17-23 Jul 2022.
B. Silverman. Density Estimation for Statistics and Data Analysis. Chapman & Hall/CRC Mono- graphs on Statisties & Applied Probability. Taylor & Francis, 1986. ISBN 97804 12462003
G. Simons. Lower bounds for average sample number sequential multihypothesis tests. The Annals of Mathematical Statistics, pp. 1343-1364, 1967.
M. Sobel and A. Wald. A sequential decision procedure for choosing one of three hypotheses concerning the unknown mean of a normal distribution. Ann. Math. Statist., 5044):50-- 12 1949.
J. Sochman and J. Matas. Waldboost - learning for time constrained sequential detection. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR '05). volume 2, pp. 150-156 vol. 2, June 2005.
R. Sullivan, J. K. Terry, B. Black, and J. P. Dickerson. Cliff diving: Exploring reward surfaces in reinforcement learning environments. ArXiv, abs/2205.07015. 2022.
C. Sun, H. Li, M. Song, and linda Qiao. A ranking-basse based cross-entropy loss for early classification of time series. IEEE transactions on neural networks and learning systems, PP, 2023.
T. Suzuki, H. Kataoka, Y. Aoki, and Y. Satoh. Anticipating traffic accidents with adaptive loss and large-scale incident db. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3521-3529, 2018.
A. Tartakovsky, Asymptotic optimality of certain multihypothesis sequential tests: Non-i.i.d case. Stat. Inference Stoch. Process., 1:265-295, 1998.
A. Tartakovsky, I. Nikiforov, and M. Basseville. Sequential Analysis: Hypothesis Testing and Changepoint Detection. Chapman & Hall/CRC, 1st edition, 2014.
M. Tec, Y. Duan, and P. Müller. A comparative tutorial of bayesian sequential design and reinforce- ment learning. The American Statistician, 77(2)2233-233 2023.
D. Teng and E. Ertin. Wald-kernel: A method for learning sequential detectors. In 2016 IEEE Statistical Signal Processing Workshop (SSP), pp. 1-5, June 2016.
Virtanen, R. Gommers, T. E. Oliphant, M. Haberland, T. Reddy, D. Cournapeau, E. Burovski, P. Peterson, W. Weckesser, J. Bright, S. J. van der Walt. M. Brett, J. Wilson, K. Jaroo Millman, N. Mayorov, A. R. J. Nelson, F. Jones, R. Kern, E. Larson, C. Carey, i. Polat, Y. Feng, F. W. Moore, J. Vand erPlas, D. Laxalde, J. Perktold, R. Cimrman, Henriksen, E. A. Quintero, C. R. Harris, A. M. Archibald, A. H. Ribeiro, F. Pedregosa, P. van Mulbregt, and S... Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing Python. Nature Methods, 17:
261-272 2020.
A. Wald and J. Wolfowitz. Optimum character of the sequential probability ratio test. Ann. Math. Statist,, 19(3):326-333 09 1948.
A. Wald and Wolfowitz. Bayes solutions of sequential decision problems. The Annals of Mathe- matical Statistics, 21(1):82-99 1950. ISSN 00034851.
B. Wang and X. Wang. Bandwidth selection for weighted kernel density estimation. arXiv. 2007.
Y. Wang, Q. Zhang, L. Ying, and C. Zhou. Deep reinforcement learning for early diagnosis of lung cancer. In M. Wooldridge, J. G. Dy, and S. Natarajan (eds.), AAAI, pp. 12410-22411 AAAI Press, 2024.
61

---

Published as a conference paper at ICLR 2025
Z. Wang and D. W. Scott. Nonparametric density estimation for nigh-dimensional data algorithms and applications. Wiley Interdisciplinary Reviews: Computational Statistics, 11, 2019.
J. Weng, X. Jiang, W.-L. Zheng, and J. Yuan. Early action recognition with category exclusion using policy-based reinforcement learning. IEEE TCSVT, 30:4626-46333 2020.
A. G. Wilson and H. Nickisch. Kernel interpolation for scalable structured Gaussian processes (KISS-GP). In International Conference on Machine Learning. 2015.
Z. Xing. J. Pei, and P. S. Yu. Early classification time series. Knowledge and Information Systems, 31(1):105-127, April 2012.
P.-E. Zafar, Y. Achenchabe, A. Bondu, A. Cornuéjols, and V. Lemaire. Early Classification of Time Series: Cost-based multiclass Algorithms. In 202/ IEEE 8th International Conference Data Science and Advanced Analytics (DSA)), pp. 1-10, Porto, Portugal, October 2021. IEEE.
62


Reviews:
[{"review_id": "TztdbAzc07", "reviewer": "Reviewer_mx42", "summary": "This paper considers sequential probability ratio test (SPRT) under finite horizon. Bayes optimality characterizes backward induction equation, given in Theorem 2.1 in the paper. The contribution of the paper is to provide a statistical method that implements this formulation. This task involves estimating the conditional expectation function as well as density ratio estimation. The former exploits concavity in the backward induction equation and gives an option of Gaussian process (GP) regression for speed-up. Theorem 3.2 indicates that the proposed method is statistically consistent. An extensive set of experiments provides numerical evidence that the propose method works better than vanilla SPRT with static threshold.", "questions": "- It would be helpful to clarify the main contribution of this paper. It seems to me that this paper is a convex combination of three existing results: (i) Bayes optimality via backward induction equation, (ii) convex function learning, and (iii) density ratio estimation. Would it be fair to say that the current paper is novel in the sense that it combines the three above but each of them is already developed by previous works?\n- It is intriguing that Gaussian process (GP) regression gives a substantial speed-up. Would it be possible to establish consistency using GP?\n- There is no theoretical result regarding the convergence rates or minimax lower bound. It might be good to indicate them as possible future research topics.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- SPRT under finite horizon seems very relevant in practice.\n- The proposed method is well grounded in Bayes optimality.\n- The numerical results are extensive.\n- The figures look impressive, although information contained in each of them is very dense.", "weaknesses": "- The paper is very lengthy if we include the appendices (60 pages in the current format). Purely based on the length, one might argue that it might be better to publish this paper in JMLR or a journal outlet.\n- Theorem 3.2 informally states the consistency of the proposed method and Theorem J.1 in Appendix J gives a formal statement. However, assumptions are given in the forms of lemmas and thus they are not low-level or easy-to-understand conditions. In fact, the lemmas are theoretical results from Siahkamari et al. (2022, ICML) titled \"Faster algorithms for learning convex functions\". In view of that, it is not very innovative in terms of proving the consistency of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "H68cHdmFdq", "reviewer": "Reviewer_2NLt", "summary": "This paper presents a framework to enhance early classification in time-sensitive applications by adapting the Sequential Probability Ratio Test (SPRT) for scenarios with finite horizons. The contribution is motivated by applications where decisions must be made within limited timeframes. The paper draws from ideas in Convex Function Learning (CFL), Density Ratio Estimation (DRE), and Gaussian Process (GP) Regression—and develops a framework for achieving optimal stopping in early classification tasks. Notably, CFL is used to estimate continuation risk efficiently, providing theoretically consistent estimations; GP regression is used as a faster, though slightly less statistically consistent, alternative; and integrates Density Ratio Estimation (DRE) algorithm for accurate log-likelihood ratio (LLR) estimates. The authors focus on Bayes-optimal solutions for early classification, which are supported by consistency results for CFL and DRE estimations.", "questions": "While the paper contributes to the question of how Convex Function Learning (CFL) be effectively integrated with Density Ratio Estimation (DRE and Gaussian Process Regression (GPR) for synergistic benefits in early classification tasks, what would be authors’ recommendation on evaluation of their combined advantage and limitations in practical settings?  This overall question relates to items 1-4 in the “weaknesses” section above. \n\nUnder what conditions does the proposed multi-component framework maintain statistical consistency in small sample settings typically found in real-time applications? Although some statistical properties are explored, there is still uncertainty about how these methods perform and remain consistent under stringent data constraints.\n\nFinally, what practical obstacles exist in deploying these methods at scale in time-sensitive applications?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "CFL is chosen specifically for its ability to offer statistically consistent estimates of the continuation risk function, which is concave in nature. This consistency is achieved by leveraging convex regression to estimate the conditional expectations that are key to solving the backward induction. The authors support this choice by citing prior work. \n\nThe DRE algorithm, specifically the SPRT-TANDEM variant, enhances LLR estimation accuracy by directly estimating the density ratios, avoiding the need to estimate individual probability densities. This approach reduces degrees of freedom, resulting in more stable and accurate LLR estimates across various data distributions (both i.i.d. and non-i.i.d.). The resulting approach handles both synthetic and real-world datasets more flexibly.\n\nGP regression is presented as a faster but less consistent alternative, primarily for cases where computational speed outweighs the need for the strict statistical consistency.", "weaknesses": "1. The paper would benefit from more detailed empirical comparisons with traditional methods to demonstrate performance gains in practice. \n\n2. Assessment/comparison of DRE’s advantage with respect to other estimation remains a question. \n\n3. More discussion is needed on scenarios where GP regression’s speed justifies its consistency loss. Overall leaving tradeoff in consistency with GP regression is underexplored. \n\n4. The overall approach becomes multi-component approach – adding implementation complexity and training across datasets. Specialized tuning (e.g., ADMM for CFL) may raise setup complexity. \nSome potentially related work (in terms of ideas/concepts) include: \n\n“Analyzing the discrepancy principle for kernelized spectral filter learning algorithms,” Alain Celisse and Martin Wahl, (2020) J. Mach. Learn. Res.\n\n“WALD-Kernel: A method for learning sequential detectors,” Diyan Teng and Emre Ertin (2016) IEEE Statistical Signal Processing Workshop (SSP)\n\n“Bayesian Optimization Meets Bayesian Optimal Stopping,” Zhongxiang Dai and Haibin Yu and K. H. Low and Patrick Jaillet (2019). Proposes unifying GP-UCB with Bayesian Optimal Stopping (BO-BOS). Focuses on hyperparameter tuning efficiency rather than early classification tasks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DTCH4qPEu7", "reviewer": "Reviewer_81so", "summary": "The paper introduces FIRMBOUND, a framework for early classification of time series tasks that builds on the Sequential Probability Ratio Test (SPRT) to address computational challenges in estimating the solution to backward induction from training data. FIRMBOUND uses density ratio estimation and convex function learning to provide consistent estimators for the sufficient statistic and conditional expectation, enabling to minimize Bayes risk for optimality. The paper then presents a faster alternative using Gaussian process regression, which reduces training time while retaining low deployment overhead, albeit with potential compromise in statistical consistency. Experiments demonstrate that FIRMBOUND achieves optimalities in the sense of Bayes risk and speed-accuracy tradeoff.", "questions": "NA", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Convex function learning could give a consistent estimator of the backward induction functions. The Gaussian process regression gives a computationally more efficient approach for  CFL. \n2. The minimizer of the Log-Sum-Exp Loss gives a consistent estimation of the log density ratio. \n3. Combining the two approaches, FIRMBOUND with CFL is consistent and Bayes optimal for ECTS. \n4. The paper performed experiments across synthetic data and real world data, demonstrating that FIRMBOUND achieves optimalities in the sense of Bayes risk and speed-accuracy tradeoff. \n\nIn general, this paper provides a method that solves an important task and works well in practice.", "weaknesses": "1. The procedure requires a two-step estimation: first estimate the sufficient statistics (log density ratio) with finite samples; then, based on the estimated sufficient statistics, estimate the backward induction function. The error made in the first step could make the second step much harder. Figure 5 seem to show that estimated LLRs indeed perform worse than true LLRs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XiwPlGwrsR", "reviewer": "Reviewer_HH7v", "summary": "The paper studies the problem of optimal stopping time for early classification of time-series. The problem is to identify the best time to stop and identify the correct class of a time-series as the time-progresses. It is known that the optimal method for this problem with a finite time-horizon is the backward induction equation that is computationally and sample complexity wise intractable. The paper makes two contribution (i) reducing the complexity of the backward induction method by observing that conditional expectation in backwards induction is a convex function learning under noise problem which has standard techniques. (ii) Further assuming the conditional expectation sequence follows a gaussian process thus reducing it to GP regression learning. They show their method achieves close to optimal speed accuracy trade-off for the problem against four baselines on synthetic and real world datasets.", "questions": "Asked above.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper tackles an interesting and technically hard problem. \n\n2. The ideas and the algorithm seems sound and practically implementable.\n\n3. The empirical experiments are thorough and has real world datasets.\n\n4. The paper explains the ideas in a nice sequence even though some parts are hard to parse.", "weaknesses": "1. Some parts of the paper are too dense and hard to parse. For instance can the authors expand on the intuition behind the various terms of the backward induction equation in Theorem 2.1. \n\n2. Why does FIRMBOUND not improve upon vanilla SPRT in terms of performance gains on the real datasets?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)