Active, anytime-valid risk controlling prediction sets
Authors: Ziyu Xu
Nikos Karampatziakis
Paul Mineiro
Venue: NeurIPS 2024 poster (2024)
Keywords: distribution free
conformal prediction
e-process
confidence sequence
Primary area: active_learning
TL;DR: An extension of risk controlling prediction sets to anytime-valid and active labeling regime.

Abstract: Rigorously establishing the safety of black-box machine learning models with respect to critical risk measures is important for providing guarantees about the behavior of the model.
Recently, a notion of a risk controlling prediction set (RCPS) has been introduced by Bates et. al. (JACM '24) for producing prediction sets that are statistically guaranteed to have low risk from machine learning models.
Our method extends this notion to the sequential setting, where we provide guarantees even when the data is collected adaptively, and ensures the risk guarantee is anytime-valid, i.e., simultaneously holds at all time steps. Further, we propose a framework for constructing RCPSes for active labeling, i.e., allowing one to use a labeling policy that chooses whether to query the true label for each received data point, and ensures the expected proportion data points whose labels are queried are below a predetermined label budget. We also describe how to use predictors (e.g., the machine learning model we are providing risk control guarantees for) to further improve the utility of our RCPSes by estimating the expected risk conditioned on the covariates.
We characterize the optimal choices of label policy under a fixed label budget, and predictor, and show a regret result that relates the estimation error of the optimal labeling policy and predictor to the wealth process that underlies our RCPSes.
Lastly, we present practical ways of formulating label policies and we empirically show that our label policies use fewer labels to reach higher utility than naive baseline labeling strategies on both simulations and real data.

Active, anytime-valid risk controlling prediction sets
Ziyu Xu" Department Statistics and Data Science Camegie Mellon University xzy@cmu.
Nikos Karampatziakis
Microsoft
fakkos@@microsoft.. com
Paul Mineiro
Mierosoft pmineirocmmccrssot..cc
Abstract
Rigorously establishing the safety of black-box machine learning models con- cerning critical risk measures is important for providing guarantees about model behavior. Recently, Bates et. al. (JACM '24) introduced the notion of a risk controlling prediction set (RCPS) for producing prediction sets that are statisti- cally guaranteed low risk from machine learning models. Our method extends this notion to the sequential setting, where we provide guarantees even when the data is collected adaptively, and ensures that the risk guarantee is anytime-valit i.e., simultaneously holds all time steps. Further, we propose framework for constructing RCPSes for active labeling, i.e., allowing one use labeling policy that chooses whether to query the true label for each received data point and ensures that the expected proportion of data points whose labels are queried are below a predetermined label budget. We also describe how to use predictors (i.e., the machine learning model for which provide risk control guarantees) to further improve the utility of our RCPSes by estimating the expected risk conditioned on the covariates. We characterize the optimal choices of label policy and predictor under a fixed label budget and show regret result that relates the estimation error of the optimal labeling policy and predictor the wealth process that underlies our RCPSes. Lastly, we present practical ways of formulating label policies and empirically show that our label policies fewer labels reach higher utility than naive baseline labeling strategies on both simulations and real data.
Introduction
One of the core problems of modern deep learning systems the lack of rigorous statistical guarantees one can ensure about the performance of model in practice. In particular, we are interested in ensuring the safety a deep learning system so that does not incur undue risk while optimizing for an objective of interest. This type of guarantee arises in many applications. For example, deep learning based medical imaging segmentation system that detects lesions [36, 10, 29] should guarantee that it does not miss most of the lesion tissue while remaining precise and minimizing
the total amount of tissue that highlighted. Hence, it is crucial to provide a statistical guarantee about the "safety" of any machine learning system to be deployed. Bates et al. [4] introduced the notion of a risk controlling prediction set as method to derive such guarantees on top of the outputs of wide range of black-box models. They consider the setting where all the calibration data for verifying statistical safety guarantees is available before deployment and the model only needs to be
Part of work done while interning at Microsoft.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

calibrated once, i.e., the batch setting. However, this is often unrealistic in production setup when we have no data concerning the performance of a model on the distribution of interest before we deploy it, and we wish to update our calibration each time new data point (or group of data points) arrives. Consequently, is natural to calibrate the machine learning model in an online fashion while receiving new data sequentially. Unfortunately, methods for obtaining statistical guarantees in the batch setting of Bates et al. [4] do not ensure risk control guarantees in the sequential regime. Further, when one uses data from production, the raw data is unlabeled, and one must expend resources (either paying experts or utilizing a more powerful model) to create gold labels for these data points. Hence, generalize the sequential setup to an active setting in which see the covariate X (e.g., an image, a natural language query from the user, etc.) and choose whether to query the true label Y. Concretely, consider the following scenarios where active and sequential method is relevant.
Reduce query cost in medical imaging. A medical imaging system that outputs scores for for each pixel of image that determines whether there is a lesion or not would want to utilize labels given by medical experts for unlabeled images from new patients. Since the cost of asking experts to label these images is quite high, one would want to query experts efficiently, and only on data that would be most helpful for reducing the number of highlighted pixels.
Domain adaptation for behavior prediction. Often, the post-deployment distribution is different from that which has been seen before. For example, during a navigation task for robot, we may want to predict the actions of other agents and avoid colliding into them when travelling between two points [20]. Since agents may behave differently in every environment, it makes sense to collect the behavior data in the test environment and update the behavior prediction in an online fashion to get accurate predictions calibrated for that specific environment.
Safe outputs for large language models (LLMs). One of the goals with large language models is to ensure their responses are not harmful in some fashion (e.g., factually wrong, toxic, etc.). One can view this as producing a prediction set for the binary label set of Y E {harmful, not harmful ull }. Many pipelines for modern LLMs include some form of a safety classifier, which scores the risk level of an output, and determines whether it should be output to the user or not [21, 15), or a default backup response should be used instead. One would want to label production data acquired from user interaction with the LLM and used to calibrate cutoff for the scores that are considered low enough for the response be allowed through.
Example: image classification Let us assume we wish to classify an image X E XY and we have access a probabilistic classifier X' - A where A is the probability simplex over distributions over all possible classes, V. Let 88 (a)) denote the probability of class in the distribution s(r). Based on the probabilities from s(X), we can define C(X, B) to have the labels with the largest probabilities that sum to _ E [0, 1] in the following fashion:
(X, max 7 1] E
yEY
3)x,3)== = fy E y: s (X) 2 (X,
Now, we can define the miscoverage error of our label set C(X, 3) as follows:
Y, = 1 & C(X,
Now, assume that We want to find a choice of /3 such that p(3) == (Xr 3)] is guaranteed to be at most 0 E [0, 1]. i.e. the expected miscoverage over the population of images and labels is at most 0.
PD, i.e., the images and class are jointly drawn from a fixed distribution.
In the above image classification example, we do not setting 3 = would trivially ensure this guarantee for any 0 E [0, 1]. We also want to minimize the size of our uncertainty set C(X,3) 9).. To present this formulation in more general terms, we are interested in solving the following problem for a fixed level of risk control 0 E [0, 1]:
not simply wish to find any / that ensures p( <
max ((3)
subject p(3) < 0.
where g the utility of our choice. We make the following natural assumption about r. P, and g. Assumption 1. g and are monotonically decreasing w.r.t. 3 and we assume p(1) = 0. addition, P is right-continuous.

---

Our image classification example has an expected risk and utility that satisfy the respective mono- tonicity assumptions, and such risk measures arise in many applications such as natural language question answering [26]. image segmentation [1], and behavior control for robotics [20, 16]. As- sumption I implies that maximizing g(3) is equivalent to minimizing (3, as g is decreasing in 8. and the right-continuity of p allows us to define the notion of an optimal calibration parameter that is the solution to (2):
3 min {B E [0, :B))= (8)
Our goal in this paper is to derive sequence of upper bounds on 9 that quickly approach the true 3 but provide "anytime-var valid risk control" in the sense that they are always greater the smallest "safe" parameter 3 and induce risk under 8, i.e., B 2 8 implies that p(3) S (((3) < 0. Since we
are guaranteed by Assumption 1 that p(1) = 0 S 6, we always have safe option of 3 1 to start with as our upper bound.
Our contributions. The primary contributions of this paper are follows.
1. Extensions of RCPS to anytime-valid and active settings. We extend the notion of RCPS in two ways: (1) to enable anytime-valie valid RCPS which allows one to refine the set as one receives more samples in stream while maintaining risk control throughout the entire stream, and (2) to define an RCPS that is valid under active learning, i.e., enable us to decide whether to label each example based on the covariates. We also define way for incorporating risk predictions from the machine learning model to decrease variance further and reduce the number of labels needed estimate 3*. We formulate this betting framework in Section 2.
2. Deriving powerful labeling policies and predictors. We show in Section 3 that our active, anytime- valid RCPS methods are practically powerful and converge to 3 in label efficient manner by also deriving formulations for the optimal labeling policy and predictors under the standard log-optimality criterion that is used for evaluating anytime-valin valid methods [13, 34, 19]. We derive explicit regret bounds w.r.t. a lower bound on the growth rate on the wealth processes that underlie our RCPS methods. These bounds characterize how the deviation of any labeling policy and predictor from the log-optimal policy and predictor affect the growth rate of our wealth processes (and hence the earliest time at which a candidate Section 4 we also show that machine learning model based estimators of the optimal policy and predictors are label efficient practice through experiments.
removed from consideration as 33*). In
Related work. Most relevant to this paper is the recent work from Zrnic and Candès [37] that provides a rigorous framework for statistical inference with active labeling policies, and leverages machine learning predictions through peediction-powerty inference [2]. However, their focus is on M-estimation and deriving asymptotic, martingale central-limit theorem based results for a parameter. On the other hand, provide finite sample anytime- -vald results that are also valid at adaptive stopping times that directly utilize e- e-process [28] construction of sequential tests. Further, our goal is provide time-uniforn statistical guarantee in the RCPS framework rather than directly estimating a parameter with adaptively collected data. We discuss additional related work in depth in Section 5.
2 Anytime-valid risk control through betting
We use (Xt)teI to denote a sequence that is indexed by t with index set I. If the index set or indexing variable is apparent in context, we drop it for brevity. In our setup, we assume that our data points arrive in a stream (X1, Yi), (X2, Y2).... that proceeds indefinitely. Let (F,) be the canonical filtration on the data, i.e., F; == a(((,, Yi))en)) is the sigma-algebra over the first points. Recall that we assumed (Xe, Y2) ~ p are i.i.d. draws for each t E N == 31, J. and want to control the risk p(3)= = E(x,y)--> [r(X, Y,]) where the expectation is take only over (X, Y). We illustrate an overview of our methodology (which we describe in the sequel) in Figure 1.
We desire to output a sequence of calibration parameters, (Bt), such that every 3 is "safe", i.c., ensures that the resulting risk of the output is provably controlled under a fixed level.
Definition 1. A sequence of calibration parameters control it possesses the following property:
(3t) is said have (0, -aaanttime--alid risk
P(p(3.) s 0 for all t E N) 2
(3)
3

---

Black-box model
do query label
label oracle
(1 = 1)
(e.g,, human labeler, powerful LLM)
Features X, (e.g., user prompt LLM response)
Flip coin w/ label prob. q,(X,)
don't 't query label 11, 0)
Gold label Y, (e.g.. toxicity of response)
Risk estimate PAXX, ()) for each [0.1]
Incurred risk x(x, V for each & [0.1]
Treat risk
varianed
Update threshold //-1 B,
Deploy P. with risk control
Ensures p()) E[x(, Y. AN 0 all 1,2,...
with prob.
Figure Diagram of the active labeling setup for ensuring anytime-vall valid risk control.
We name this as "anytime-valid" since the risk control condition (i.e., p(3) S guaranteed to hold simultaneously at all E N. Hence, this allows for the user to process continuous stream of data and control the probability that 3e is chosen at any time / that is "unsafe", i.e., p(33)) 0. We build on recent work that develops a framework for hypothesis testing and parameter estimation with sequential data collection based martingales and gambling with virtual wealth known as testing by betting [30]. In this framework, the goal is to design an e-process, (E,), w.r.. a null hy Ho. which satisfies the following properties when true:
Definition An e-process, (Ex) w.r.. hypothesis Ho. nonnegative process for which there exists another nonnegative process, (Me) (Me),,, s.t. the following is true when Ho is true: (I) M[M (2) M, 2 E, for all almost surely and (3) E[M, Fi-1] < Mc-1 for all N,. i.c., (M,) is supermartingale.
E- E-processes will be the main tool we use to construct (f:). We leverage the probabilistic bound on e-processes provided by Ville's inequality prove anytime-vall risk control guarantee. Fact (Ville's inequality [33]). For any e-process, (Ex), with initial expectation bounded by 1, i.c. E E.Fo] < 1, we have that
P (exists E:N: M, a) for each a E 10.
In this paper, all our e-processes will also be nonnegative supermartingales, so we denote them as (M.). Now, we will specify the null hypotheses in our risk control setting. For each 3 [0, 1]. we test the null hypothesis H p(3) for fixed risk control level [0, 1]. Note that include equality to 0 in the null hypothesis since we do not wish to reject H²" Let (8))
family of e-processes where (M) is e-process for H Then, we can derive B, for each e N as follows:
8, = min min {B E [0,1] Mx(3') 2 1/a for all 3' 33
Theorem 1. The sequence of estimates (3x) in (4) satisfies the anytime-valid risk control guarantee (3), i.e. (()( < for all E N) 2
Proof. First, note that
B, < = E M(8') ( 2 1/a). [3 E N: ((.)) > 0) + (3rEN

---

Since H6 is always true by definition of 3",, we get that (3*) is an e-process by Proposition 1.
Thus, by applying Ville's inequality, we get that:
P( N. p(3.) > 0) PPree M(8) 2 1/a) aa
Now, we will present a concrete example of e-process. Denote (3) = r(X,, Yt, B). We test Hy using the betting e-process from Waudby-Smin -mith and Ramdas [34]:
M1(3) = II (1+ (R-
(5)
2m1
where (Ax) is predictable w.r.t. (Fi), i.e., d can be determined by Ji-1 for each t E N. and
A E [0, (1 -0 0) "].
Proposition 1. (Mc(3) in (5) is e-process for all B where H. is true, i.e., where ( 2 A.
Proof. We note that (5)) is nonnegative by the support of X being limited, i.e.,
Ae r(x,, Y, 8)) 2 1+ \, 1) 2
Now, we will also show that (Mr(5)) supermartingale when H1 true.
B[M(3) Fi-1] [1[ + (0 R.(B)) Fi-I ( = (1 + ( - (3) F--I)) -M)) S M2-1(B).
The second equality is because d is measurable w.r.t. F:-1 and the last inequality is by (3) being independent of Fr-1 and (B)] < 0 being true under Hg Thus, we have our desired result. O
Now, we have concrete way to derive (3:) that ensures the risk p(3.), is controlled at every time step t E N. However, this requires one to label every example that arrives, i.c., it requires access to entire stream of labels (Yz). We will now derive more label efficient way for constructing (B.). Remark 1. Ramdas et al. [27] show that e-processes of the form in (5) characterize the set of admissible e- e-processes (and hence anytime-valid sequential tests) for testing the mean of bounded random variables. Hence, it is optimal choice of e-process for our setting, and have been shown to perform better both theoretically and empirically than other sequential tests for bounded random variables (e.g., Hoeffding and empirical-Bernsee based tests [34]).
2.1 Active sampling for risk control
Now, we describe active learning for risk control, where an algorithm sees X, decides whether label, for the current point, Yr, should be queried or not. At each step E N, the algorithm produces a label policy 4: : X + [qt 1] based on the observed data (i.e., Ft 1). It then queries the label, Y,, with probability q: (X.) that is lower bounded by constant, gmin Let L, be the indicator random variable for whether the 7th label is queried, i.e., L, ~ Bern(ge
To produce label efficient method, would hope to label the most "impactful" data points that result in the largest growth of M3) for choices of 3 E (0, B,), i.e. that still in consideration for the next 3411 For the labeling policies we consider in this paper, we let qilin E [0, 1] be a lower bound on the labeling probability. i.c., qo (X,, 2 qi almost surely. Thus, we can derive the following e-process for any sequence of labeling policies (4:).
M.()) = II
1 1+
>: (o
L; T: (X,))
Rd R2(3))
Proposition 2. Let (g:) be a sequence of labeling policies, and (Xe) be a sequence of betting parameters, and let both sequences be predictable w.r.t (Fx) (iee. and X are measurable w.r.t. For each t N). Then, (Mc(3) in (6) is e-process for all B where H is true.
5

---

Proof. The proof of this is similar to that of inverse propensity weeghtte e e-processes derived in Waudby-Smith al. [35]. We know that (M)( is nonnegative by the support of X, being limited:
1 X (0- L
Ra(3)
2 1+ do (0- (at ) >))= 2 0,
(x+)
where the first inequality is by (8) I 1 and (X,, 2 grinn, and the second inequality is by
de I ((g.min) ) 0)-1 Now, we will also show that (5) is supermartingale. We first show
the following upper bound:
L (3) Fi-1 1 =
L X1. RB( Fi-1 ([R Fi-1l O. (7)
()(),,)
(x()))
The first equality is by further conditioning on X,, and the second equality is since L1 is defined to be a Bernoulli random variable with parameter (xx)) that is independent of all other randomness
when conditioned on X₂ and Fr-1. 1. The last inequality by Hy being true. Now, we have that
L (x,,
(5--1) Mc-1 - M))
((M((8) Fi-1= = 1 de
0 - E
RB(3)
where the inequality is by (7). Hence, we have shown that (M,(3) is a nonnegative supermartingale, and hence also an e-process, under H."
Theorem 2. (3:) defined w.r.t. (6) satisfies the anytime-valid risk control guarantee (3). This is result of Proposition 2 and Ville's inequality, similar to the proof of Theorem 1. Theorem 2 essentially shows that we can still design e-processes by allowing for a probabilistic label policy.
2.2 Variance reduction through prediction
Often, we also have an estimate of the risk we incur, e.g., in the example given for classification, we have an estimated probability distribution over possible outcomes. As result, we also have an empirical estimate of (1,,X,33) | X = x] for each 8 E [0, 1] that we can use to reduce the variance of our estimate. This is similar to the usage of control variates for improving Monte Carlo estimation [3, $ V.2]. and of predictors in the recently formulated prediction-powered inference framework [2]. Let Fr X x [0, + [0, 1] be estimator of the risk incurred by parameter B conditional on x E X' for each time step E N. (Fr) is predictable w.r.t. (Fi).
Where does ñ come from? We note that often machine learning models have some estimate P()) of the conditional distribution of Y X (e.g, class probabilities, conditional diffusion models, LLMs. etc.). Thus, for any realized covariate x. we can derive use Ey-P(s) [xX, 3) X = x] from the machine learning model as our choice of f(x, B). This expectation can either be calculated analytically (as we do in or classification examples in our experiments) Carlo approximation (for generative models such as LLMs, one can sample from the conditional distribution). In essence, we can obtain predictor from the very model we are calibrating. We may also update our predictor using new (X,, Y) pairs we receive for calibrating (3)).
derived using Monte
Now, we define our e-process that utilizes our predictor as follows:
R((01) where Ri(3)= = -R((3)- - -fe(Xe,, 3), M, II 1+ M (0 (0- (x (xx)))
Li
(8)
and we restrict A E [0, ((ghim)-1 01 (or in other words, giin > > >e/ + X,O)). Note that this e-process recovers the active e-process defined in (6) if we set P:(., 3) = for all i E N.
Proposition 3. (M,( as defined in (8) is an e-process for H.
Proof. Since the restriction on (At) ensures M3) is nonnegative, to show that (Mc(B) is an e-process, is sufficient to show:
E[>.(0 - (X,,,, (3) L, R. F-
= Ae - EX,, 3) + L.
(B) [[-1l))
=Ar(0- (X,, 9) + +ELL (x.) X,, -R((8) Fi-1))
= =A(00 (X, 9) + (B) F. = \, - ((R F.-1l) S 0.

---

The 3rd equality is by definition of Lt, the last equality by the definition of Re, and the last inequality is due to Hy being true.
The role of (x,,,, 3) is to accurately predict (3). Bad predictions can increase the variance of R2 (3) and lead to slower growth of (3),, but do not compromise the risk control guarantee. On the other hand, accurate predictions, which come from pretrained models, decrease variance and improve the growth of (3). We characterize the optimal predictor (Proposition 4) and relate the accuracy of a predictor to its effect on the e-process (Theorem 3) in the next section.
Optimal labeling policies
Since the goal of having active labeling policy is to label fewer data points, one reasonable way of doing this is to maximize the growth rate of our e-process (Mr(5) defined in (8). Define the following function, for some 3 [0, 1]. of labeling policy q. predictor i, and betting parameter where we let L X Bern( (x)) and (X,Y) ~ P
G (g =
log log (1+ A ( - ((x)
L
(((3))
where ((3)= -(,
Define the growth rate at the 1th step of (Mc(3) as G. = B.G (4: Fr, Ar)], where we let G be identical to G, but with X and Y replaced with X, and Y,, respectively. It is a standard notion of power or sample efficiency for e-processes. Typically, our goal when designing an e-process based test is to maximize such metric, i.e., want e-process to be log-optimal [13, 34, 19]. Log-optimality is also called the Kelly criterion in finance [18] and is known that maximizing the growth rate of process is equivalent to minimizing the expected time for the process to exceed threshold, i.e., for our sequential test to reject a value of 3, in the limit as the threshold approaches infinity [5]. Thus, in asymptotic sense, maximizing the growth rate is equivalent to minimizing the expected time for rejection. Our goal is to maximize the growth rate while having a constraint on the number of labels can produce.
Let B E J0, 1] be the constraint on our labeling budget, i.e., we label, in expectation, a B fraction of all data points that we receive. To achieve both of these goals, we wish to choose qt, Ft, and X that are the solutions to the following optimization problem:
max E EL x) | (q, A)] s.t. Elg(X)) < B. g.F.A
Since solving the above optimization problem is analytically difficult, one can instead maximize lower bound on the expected growth [32, 25, 24]:
(a = x -0
L
R((3)) - X2 ( F(X,3) (F-((3) ((x)
L R(3) M3)
x(X)
which holds when À E [0, (2(1 20)
20) -1. where q :- infzex q(x). We can further simplify We can use the lower bound (9) to formulate the following optimization problem.
max E [ (a. s.t. B[a(X)) S B F.F.A
(10)
Let (g", ,rr,,"" X²) be the tuple that the solution to (10). We can analytically show what y* is.
Proposition 4. The optimal predictor r" in the solution to (10) is rx( B) Er | 2) for each x E X.
We defer the proof to Appendix A.1. The optimal choice of q² has the following formulation.
Proposition 5. we fix e and X, the solution to the optimization problem in (10) is given by g where (x) x X R X for each x X if such a q3 exists.
We defer the proof to Appendix A.2. Let (T(()) == Vr Y,8) X 2] be the conditional standard deviation of r(X, 3). Now, we can argue that the solution the optimization problem on the growth rate lower bound in (10) has the following characterization.
7

---

Corollary 1. The optimal choice of q and X that solves (10) is
(2(x)
x 1
0 ((3)
(3)))
[X) B,
0 Blo
B- Vr((X (,5)
(x) E [0, for & E X, and S (2(inlmex (2)))
20) The resulting growth rate
has the following lower bound:
El r", Xlx 2 (d
1
(0 - p(3)2 Elo B-1 VIr(X,X,
4 10 (00))
We can show this is true consequence of Proposition 4, Proposition 5, and solving the quadratic equation that arises for the growth rate derive the optimal choice of X Further, we note that we can define regret of a sequence (Ae) compared to X on G as follows.
Definition 3. The G -regret at the /th step of a sequence of betting parameters (Ae) for a risk upper
bound 0 E [0, 1]. and sequence of labeling policies (4: and predictors (Ft) where qi (x) 2 6 0
for all x E X' and E N almost surely is defined as follows:
Reg.
max (2 1020 1
Σ EIG (qc Fe, A) F (9.. Fe, Xe) Fr-1).
Since G. (g. F, X) is exp-concave X, existing online learning algorithms such as Online Newton Step (ONS) [8] get o(T) regret guarantees, which means that the growth rate of (At) averaged over time will approach (or exceed) the optimal growth rate under A For simplicity of analysis, we make the following assumption about the labeling probability of the optimal policy, 43-
Assumption 2. Let E > 0 be a positive constant. Assume that g3 (z) 2 for each x E X.
The lower bound in the above assumption is analog of the propensity score lower bound optimal policies that is needed for proving valid inference in adaptive experimentation [17. 7]. Further, we do need this assumption to hold on every since we not necessarily interested in log-optimality w.r.t fringe 3 that are quite far away from 8 - in practice having this assumption hold for values of B near 8 suffices to develop an estimator 3 that shrinks toward / quickly. Now, we describe how much the growth rates deviates based on on how well qº and r* are estimated.
Theorem 3. Let (Ax) be sequence with - -rerrttt (Reg,) and (q:) and (fr) are sequences of labeling policies and predictors that are all predictable w.ntt (Ft). For positive constant e >> 0, let (x(x) 2 E > 0 for each t E N and x E X almost surely. Under Assumption 2 for the same E, the following bound holds:
& (g" (et, Aell & Reg, Σ O(E]](((x)) ([l6(xx))((xxx))) - (X),
We defer the proof to Appendix A.3. The proof idea follows similar idea that of the regret bound in Kato et al. [17] for deriving an estimator that is close to the optimal estimator for the average treatment effect in an adaptive experimentation setup. Thcorem 3 relates the estimation error of g (x) and r (z. 3) to how quickly will be deemed "safe". Hence, if have good estimates of those quantities, then we can produce an estimates (3x) that are small and close to 3 while remaining safe. We will now describe some practical methods for calculating dt and Ft, and demonstrate their empirical performance in some experiments.
Experiments
We use PyTorch model our (gr) and (ft), and we consider the following formulations.
1. Baseline labeling policies. We have baseline labeling policies of labeling all data that arrives, and a policy that just randomly samples B proportion of samples to label these are denoted respectively as "all" and "oblivious".
"Code github. cwwm///illexa/acctiieeregr

---

2. Pretrain: We derive an estimate of r" from pretrained machine learning model, frrerr to be our choice of predictor for all time steps. We also derive an estimate of o B), (x, from the pretrained model. We also learn sequence of normalizing constants (Ct) s.t. the budget is satisfied. Our labeling policy in this case is qr (2z) (ar, /) where we want to optimize our policy for the previous best bound on B", 3 We denote this method as "pretrain".
3. Estimating 4j and r": We learn sequences of models (ap and (F using the labeled data points. We preprocess the outputs from Geretr and freer use the input features these models, respectively. Each of these sequences of models are then updated at every step. We also similarly learn sequence of normalization constants (C₂) for deriving the final labeling policy (4t).
We provide more details on how are methods are formulated in Appendix B. We run all our experi- ments on a 48-core CPU on the Azure platform, after using GPU to precompute the predictions made by neural network models. We set 0.1, = 0.05, and B 0.3 for all our experiments.
4.1 Numerical simulations
We have a simple data generating process of sampling Pa Uniform(0, 1] and let Y, X, ~ (e)n This simulates the setting have with our real data where have accurate pretrained classifier that have a probability estimate of Y, of being or 1. We let our covariates X; = Pt. As result, our risk function is the false positive rate TFPR (X, Y, () == (X B, Y = 0}. We run 100 trials where each trial runs until 2500 labels are queried. We compare our methods based on their label efficiency, i.e., how close is 3t to 8* = 11 /2a after set number of queried labels. In Figure 2, we plot the average Be reached after given number of labels queried across trials. The shaded areas denotes pointwise 95% confidence intervals on the uncertainty of the average estimate. We can see that the "pretrain" and "learned" methods outperform both the "all" and "oblivious" strategies uniformly numbers across labels queried. In Figure 2a, we show the average rate of safety violations, i.e., the average proportion of trials that 3, was unsafe and p(ß²) > 0 at any time step. We can see that all methods control the desired safety violation rate at the predetermined level a.
1.0
Method
all ablivious
0.100
0.075
0.8
pretrain
0.7
gretran
1000
2000
Method
Method
Labels queried
(a) Average rate of safety viola- tions 3.
(b) Average final value 3 (lower is better).
(c) Average 3, vs. labels queried (lower is better).
Figure 2: Experimental results for different methods for our numerical simulation setup. We that "pretrain" and "learned" perform better by getting lower average 3, uniformly across number of labels queried- - the dotted line in Figures 2b and 2c is f = 0.5578. Each method also has low safety violation rate, i.e., is below the dotted line of = 0.05 Figure 2a.
4.2 Imagenet
We also evaluate our methods on the Imagenet dataset [9], and we used the pretrained neural network classifiers from Bates et al. [4] to provide estimates of the class probabilities.
Since Imagenet a classification task with label support on y = [1000], our goal is to ensure that the miscoverage rate of the true class is controlled. We follow the same setup as descibed in the introduction, i.e., with our risk measure r specified according to (1). For Imagenet, we reshuffle our dataset for each trial, and run each method till we have queried 3000 labels.

---

Method
0:88
0.06
Ero rate
0.04
0.
0.95
learred ablivious
0.86
0.02
pretrain
0.00
0.85
pretrein
leam
2000
Method
Method
queried
(a) Average rate of safety viola- tions 3..
(b) Average final value of 3, (lower better).
(c) Average 3, labels queried (lower is better).
Figure 3: Experimental results for different methods on Imagenet. Again, we see that "pretrain" and "learned" are the best performing, and they have very similar performance and hence overlap in Figure 3c. Here, 3 0.8349, and is delineated by the dotted line in Figures 3b and 3c. Again, each method also has low safety violation rate, i.c., is below the dotted line of a = 0.05 in Figure 3a.
In Figure 3, we plot the average 3, across trials. Once again, we can see that the "pretrain" and "learned" methods outperform both the "all" and "oblivious" strategies here as well. On Imagenet the average safety violation rate is also controlled well under the predetermined level of 0.05.
5 Additional related work
Casgrain et al. [6] provide anytime-vall valid sequential tests for identifiable functions, which result in similar hypotheses being tested as this paper albeit with equality instead of equality. They, in addition to other recent work [25. 24, 31], using regret bounds for betting- -aaedd-badddde e-processes to show either derivations for the growth rate of betting strategy w.r.t. to the optimal growth rate. However, none of these settings incorporate the ability to perform adaptive sampling or inverse propensity weights. Prior work in anytime-vale valid inference have included inverse propensity weights have been for off policy evaluation [35], adaptive experimentation [7], or estimating the weighted mean of a finite population [32]. However, none of these works explicitly characterize deviation in the sampling policy away from the optimal sampling policy ultimately affects the growth rate as we do in Theorem 3.
Our analysis of power and regret for our algorithm is quite similar to methods in adaptive experimen- tation for average treatment effect estimation [14, 17] that attempt to derive a no regret treatment policy and outcome regressor that produces estimator with variance that approaches the variance of the optimal estimator. Unlike the adaptive experimentation setting, however, we have an additional label budget constraint on our formulation that results in different optimal policy.
6 Conclusion, limitations, and future work
We have shown that we can extend the RCPS formulation to be anytime-valid, and retain validity and increase label efficiency in active learning setting. We use the theory of betting and e-processes to develop this framework and show it is verifiably safe, and we verified this with our experimental results. We have primarily considered the i.i.d. setting here for anytime valid calibration, and one key area in which one can extend this line of work is to account for distribution shift during test time. The empirical Bernstein supermartingales in Waudby-Smin -Siihh et al. [35] can likely be used to extend our framework control risk in an average sense, but stronger guarantees could be made about the provided risk control if more realistic assumptions are made about the nature of the distribution (e.g., covariate shift, label shift, etc). It may also be possible extend a notion of adaptive conformal inference (ACT) [11, 12] anytime-valid risk control. Another limitation of this work is the bounded label policy assumption (i.e., Assumption 2) and existence assumption in Proposition 5. We believe that more careful analysis can get rid of these assumptions future work.
References
[1] A. N. Angelopoulos, A. P. Kohli, S. Bates, M. I. Jordan, J. Malik, and Y. Romano. Image-to-Image Regression with Distribution-Fre Uncertainty Quantification and Applications in Imaging. In International Conference Machine Learning, 2022.
T. Alshaabi, S. Upadhyayula,
10

---

[2] A. N. Angelopoulos, S. Bates, C. Fannjiang, M. I. Jordan, and T. Zmic. Prediction-poweee inference. Science, 382(66771):66 674, 2023.
[3] S. Asmussen and P. W. Glynn. Stochastic Simulation: Algorithms and Analysis. Stochastic Modelling and Applied Probability. Springer, New York, edition, 2007.
[4] S. Bates, A. Angelopoulos, L. Lei, J. Malik, and M. Jordan. Distribution-free, Risk-controliing Prediction Sets. Journal of the ACM, 68(6):43:1443:44 2024.
[5] L. Breiman. Optimal Gambling Systems for Favorable Games. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, pages 65-79, 1961.
[6] P. Casgrain, M. Larsson, and J. Ziegel. Sequential testing for elicitable functionals via super- martingales. Bernoulli, 30(2):147-11374, 2024.
[7] T. Cook, A. Mishler, and A. Ramdas. Semiparametric Efficient Inference in Adaptive Experi- ments. Conference on Causal Learning and Reasoning, 2024.
[8] A. Cutkosky and F. Orabona. Black-Box Reductions for Parameter-free Online Learning in Banach Spaces. In Conference On Learning Theory, 2018
[9] J. Deng, W. Dong, R. Socher, Li, K. Li, and L. Fei-Fei. Imagenet: A large-scale hierarchical image database. IEEE Conference on Computer Vision and Pattern Recognition, 2009.
[10] A. M. Flores, F. Demsas, N. J. Leeper, and E. G. Ross. Leveraging Machine Learning and Artificial Intelligence to Improve Peripheral Artery Disease Detection, Treatment, and Outcomes. -8500, 2021.
Circulation Research,
[11] I. Gibbs and E. Candes. Adaptive Conformal Inference Under Distribution Shift. In Neural Information Processing Systems, 2021.
[12] I. Gibbs and E. Candès. Conformal Inference for Online Prediction with Arbitrary Distribution Shifts. Journal of Machine Learning Research, 25(162): 2024.
[13] P. Grünwald, R. de Heide, and W. Koolen. Safe Testing. Journal of the Royal Statistical Society: Series B (Statistical Methodology). 2024.
[14] J. Hahn, K. Hirano, and D. Karlan. Adaptive Experimental Design Using the Propensity Score. Journal of Business & Economic Statistics, 29(1):96-108, 2011.
[15] I. Hanu and Unitary team. Detoxify. Github. https://gthhb..comm/iiiaaaaa/adt 2020.
[16] H. Huang, S. Sharma, A. Loquercio, A. Angelopoulos, K. Goldberg, and J. Malik. Conformal Policy Learning for Sensorimotor Control Under Distribution Shifts. In IEEE International Conference on Robotics and Automation, 2024.
[17] M. Kato, T. Ishihara, J. Honda, and Y. Narita, Efficient Adaptive Experimental Design for Average Treatment Effect Estimation. arXiv:2002.05308, 2021.
[18] J. L. Kelly. A New Interpretation of Information Rate. The Bell System Technical Journal, page 10, 1956.
[19] M. Larsson, A. Ramdas, and Ruf. The numeraire v-variable and reverse information projection. 1XXi:24022.18100 2024.
[20] Lekeufack, A. N. Angelopoulos, A. Bajesy, M. Jordan, and Malik. Conformal Decision Theory: Safe Autonomous Decisions from Imperfect Predictions. In IEEE International Conference on Robotics and Automation, 2024.
[21] T. Markov, C. Zhang, S. Agarwal, F. E. Nekoul, T. Lee, S. Adler, A. Jiang, and L. Weng. A Holistic Approach to Undesired Content Detection in the Real World. AAAI Conference on Artificial Intelligence, 2023.

---

[22] F. Orabona and T. Tommasi. Training Deep Networks without Learning Rates Through Coin Betting. In Neural Information Processing Systems, 2017.
[23] A. B. Owen. Monte Carlo theory, methods and examples. attpp://arttnn au domains/ 2013.
[24] A. Podkopaev and A. Ramdas. Sequential Predictive Two-Sample and Independence Testing.
In Neural Information Processing Systems, 2023.
[25] A. Podkopaev, P. Blöbaum, S. Kasiviswanathan, and A. Ramdas. Sequential Kernelized Independence Testing. In International Conference on Machine Learning, 2023.
[26] V. Quach, A. Fisch, T. Schuster, A. Yala, H. Sohn, T. Jaakkola, and R. Barzilay. Conformal Language Modeling. In International Conference on Learning Representations, 2024.
[27] A. Ramdas, J. Ruf, M. Larsson, and W. Koolen. Admissible anytime-valid sequential inference must rely on nonnegative martingales. arXiv:2009.03 2022.
[28] A. Ramdas, P. Grünwald, V. Vovk, and G. Shafer. Theoreti Statistics and Safe Anytime- Valid Inference. Statistical Science, 38(4):576 601, 2023.
[29] I.. Saba, S. S. Sanagala, S. K. Gupta, V. K. Koppula, A. M. Johri, N. N. Khanna, S. Mavrogeni,
J. R. Laird, G. Pareek, M. Miner, P. P. Sfikakis, A. Protogerou, D. P. Misra, V. Agarwal, A. M. Sharma, V. Viswanathan, V. S. Rathore, M. Turk, R. Kolluri, Viskovic, E. Cuadrado-Godia,
G. D. Kitas, N. Sharma, A. Nicolaides, and J. S. Suri. Multimodality carotid plaque tissue characterization and classification the artificial intelligence paradigm: narrative review for stroke application. Annals of Translational Medicine, 9(14): 2021.
[30] G. Shafer. Testing by betting: A strategy for statistical and scientific communication. Journal of the Royal Statistical Society: Series (Statistics in Society), 184(2)4407-331, 2021.
[31] S. Shekhar and A. Ramdas. Nonparametric Two-Sample Testing by Betting. IEEE Transactions on Information Theory,
2024.
[32] S. Shekhar, Z. Xu, Z. Lipton, P. Liang, and A. Ramdas. Risk-limiting financial audits via weighted sampling without replacement. In Conference on Uncertainty in Artificial Intelligence, 2023.
[33] Ville. Érude Critique de Notion de Collectif. PhD thesis, University of Paris, Paris, 1939.
[34] Waudby- Smith and Ramdas. Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society Series B (Statistical Methodology), 2023.
[35] I. Waudby-Smith. L. Wu, A. Ramdas, N. Karampatziakis, and P. Mineiro. Anytime-valid off-policy inference for contextual bandits. ACM IMS Journal of Data Science, 2024.
[36] J. Wu, J. Xin, X. Yang. J. Sun, D. Xu, N. Zheng, and C. Yuan. Deep morphology aided diagnosis network for segmentation of carotid artery vessel wall and diagnosis of carotid atherosclerosis on black-blood vessel wall MRI. Medical Physics, 46(14) 46(12):5544-555
2019.
[37] T. Zmnc and E. J. Candès. Active Statistical Inference. In International Conference on Machine Learning, 2024.
12

---

A
Omitted proofs
Proofs that have been deferred from the main body of the paper are contained here.
A.1 Proof of Proposition 4
We rewrite the objective in the following way:
x 0 F(X,3) ((X) R(3)) X² (0- (D-P(X,3) ((x)
1.
L.
2
E[G(g, F. A) E
R(3)
= x0 r()) - X² (00 (0- p(3))² +V 3)x,3) ((x) R(3)
L.
(II)
Maximizing (11) is the same as minimizing the following equivalent expressions:
F 3(,
I
R(B)
((x)
L
R(3) X x] + V
L 9) + ((x) R(B) | x
F(X, 3)
(())
L
R
R(B) X
+ V[R(3))
((X)
R(3)
X ([( x}2 + +V[((3)]
9(X)
TE [()) X =x]
E[R(3) x = xt|? =)]²
p(z) dx + V[R(8)).
(12)
((x)
where we derive the 1st equality from the law of total variance, and the 2nd equality from the fact that f(X, 33 is fixed given X.
Since the only term that F affects is the integral term in (12), choose each F(x: (3 for each x E X' to minimize the following:
E R(3)²² X x|
R()) X = x
(())
[[ Y, 9) - f(z, 9))²
X = (16r((X,Y,)) X -
((x)
Bir(X,Y, Y, Y,3
X = =i]
| = 2²
((x)
1
1) (2 Y, B) = 2)f(2, B) - F(z, 3)2)
(13)
((x))
If we remove the constants (i.e., terms unaffected by f(x, B)), and note that g(x)) 1 0, we get that minimizing (13) is equivalent to minimizing
2E(r(X, Y. | X ,)) 3).
This is equivalent to minimizng the squared error, i.e., (E(r(X, x -f which means that r* (z. B) = E/r(X,Y,3) X z),, which gets us desired result.
A.2 Proof of Proposition 5
Since we have shown that maximizing (10) is equivalent to minimizing (12), we can isolate the terms that change wiht q and see that we are looking for the solution to the following optimization problem:
p(z)
min
E R(R())
X = x] do
q(
f poo))(o)) do < B.
13

---

We can define xp()) == p(x)g(x) rewrite this as
p(x)² min / ((x)
B(R(3) X; - x] dx
s.t. / ((()) dr - B.
Assume we can define valid de where (z(2) E [0, 1] for each æ E X' that satisfies the following conditions:
(xx) x p(x)
R(3)2 X x (3(2) E [[(3) X x
Explicitly, we define g as follows:
E R(3)2
X
(x))
B.
E
E [(())
X-
One can show its optimality by considering some other labeling policy o' where Elg((X)] = B (we use a similar proof technique from importance sampling Owen [23, $ 9.1]). Now, let ('((x) = p(x))1(()) (x) and v0 (a:) p(x))'( (x)
p(x)2 (T)
E[R(B)
X; = x] dæ
p(z)
E
E [((3)2 X X=
B[R(9)2
X; x] de
B
E
[[((B)2 X m]
-
(
p(a)
(1(x)) IB [R(3)) X = dr
B-1
('(x)
(1
(((x)
2
B
((())
B V E [[(}] x x/ dx
p(x)
[R(3) x = x| dr.
(((x)
where the last line is by desired result.
since (x(x)/ B is a valid p.d.f. Hence, we have shown our
A.3 Proof of Theorem 3
By definition of Reg,, we know that
Σ (g,,,)))) (g:, Fr, Ac) S <Rg,
by taking an expectation over F,-1 for each term in the summation Hence, what remains be shown is the following:
EI ,x)) - (G. X*)]
O(Ella(()) ( -r"((x,
(14)
14

---

Let Rc(3) = r r xX, B) and (3) - (x (6 We first note the following
identity using (12):
E|Ga(19 (q r" {²) E|G (gc. X')
11)
=(>9}
E
V
Fx( 3)
Rc(3) Fi-1 - V (x)
R' (()
(x()
(x)
Now, we make the following derivations for the difference between the variance (V) terms:
L
L R3)
3) (x())
Re(3)
Fi-1 V (x,
(x(X)
[3)2
XX=
B (3)2 X x]
((R((3) X x =x=x
-p(x) dæ
(x(
(2(
(g)(1) - [x)) = (1) (x)) (x,,,
pp(x) da
(<())1(())
$ / (())(a)) (x())) + (f((z) -z, ())3) p(x) dr 9e (x.) (0(B(1(((x)) Fi-1l B[( (X,, 3))2 F(-1))-
(15)
The 1st equality is by substituting in the identity from (12). The 1st inequality is result of V[r(X, Y, B) = x] S J. since r(X, Y, 3) E [0, 1J. and (x),,, (x()) E [s, 1] almost surely. The 2nd inequality is by upper bounding (x) (x(x) by its absolute value.
Now, if we plug (15) into (14), take the expectation over Fz-1, and take the summation over get our desired result.
B Experiment details
In this section, we discuss additional details about how implement our methods described in Section 4.
B.1 Formulation of the labeling policy
For the "pretrain" policy, estimate of the conditional mean and variance derived from
ppeet B) = (x)),
(EC(a,
p (x,,8)= / ppree B)) -prett (I. B3))
These estimates may not be accurate, but might still represent a reasonable partitioning of the feature space where (ax .) and r" (x,,9) are similar. Hence, for aplugin and pplugin we model them as linear regresssion models where inputs are a binning of ppretr (sx, (3) and preir (x, respectively. We then learn the regression model parameters on training data.
B.2 Optimization to maintain the budget constraint
For any predictor ã we optimize the Lagrangian corresponding to (10), which is defined as follows for fixed dç.
15

---

((v..0))
B[G((q, Ae)1 14 (Elg( - B)
Ia r(x, (xx, ((x,,,9) -b)(2)) (0 (((x)
=B de 0
(((( B)
9c(X)
Ae p(B)) XB (0-(
L
|
(x R(3)
ue (e B)
Since we know the optimal form of Fr. we optimize it separately by taking an optimization step with the loss of squared error, (r(X, 8) (X, 8)) for each labeled example for grid of 3 values.
To derive the solution, we simplify playing the minimax game with the above Lagrangian to following objective:
max min E
(x(X) (r(X,Y,3) - - Ds (T((((()) - B)
the case of both "pretrain" and "learned" methods, we parameterize our y in the following fashion:
4: (2) (x. (1-1)
exp(c:)
where normalization constant C exp(ce) for some value G R ensure it is nonnegative.
Ge updated separately. For "pretrain", fixed from the beginning, and for "learned", we take an optimization step to minimize the squared loss against the squared residual, i.e., we update to minimize ((r(X, Y) (x(,,))) 0e (X, 3)
Hence, the only thing that remains to optimize c. which now simply means we need to solve the following problem (where we treat B, fixed):
max min - c + exp(c.) (X,
The actual game payoff we play is the stochastic approximation of the Lagrangian in the following form:
(r.(X,. B--1) exp(ci)
Live, ct) - -it
At each step, take optimization step e2 towards maximizing the above loss, and determine v by playing either best response or a windowed best response that takes an average of best responses over recent rounds. We use the COCOB optimizer [22] for all of learning and optimization which requires no hyperparameter or learning rate selection.
16

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA]. .
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation. While "[Yes] " is generally preferable "[No] ", is perfectly acceptable answer "[No] provided a proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased binary way, we acknowledge that the true amswer is often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide exactly what we describe the abstract/introduccion, i.e., method for constructing active, anytime- antiime-valid
valid risk controlling prediction sets along with theoretical guarantees and experiments demonstrating its efficacy.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
17

---

Justification:
We elaborate on the limitations of the paper in Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approxinations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
We provide proofs and assumptions for each result (clearly delineated) in the
paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide the code for reproducing the experiments in supplement.
Guidelines:
18

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide all code for reproducing the experiments in the paper in a supple- ment (see above).
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (bttps://nips.co cc/ Seeeii/guudds//eeeuuueeeee
www.ubiiiisiooooisoiiooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ ttips.cc/publicc/e wttpc///ggge///eeeoeoo httpb///iiiguiieee////eettiiiiii Swtoe//odeeissaiiiooeaea wtw.iiiiiiiiooiiiiiii for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
19

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide experimental overview in Section 4, and we provide additional details in both the code and the appendix (Appendix B).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We show error bars (from 95% normal Cls) for all our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
We specify our compute resources in Section
Guidelines:
The answer NA means that the paper does not include experiments.
20

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://
Answer: [Yes]
Justification: have reviewed the ethics guidelines and this paper conforms with it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is statistical methodologyytheory for enabling active labeling for risk control - it may allow users of machine learning models more cost-effectively calibrate their models to control measures of harmful risk when using them practice, but there no direct societal impacts as far as we can discern.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML..
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
21

---

Answer: [NA]
Justification:
Our paper does not release new data/models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Yes, we properly cite the papers for which we models, code, and data from (e.g, Imagenet, RCPS, etc.).
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswithe wwwdwetteeeeee.ooo com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-pace se-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide our experimental code in the supplement and provide details about it in Appendix B.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
22

---

14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicabll, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We don't perform human research for this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
We don't 't perform human research in this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
23


Reviews:
[{"review_id": "ownj8JWXgu", "reviewer": "Reviewer_1rh6", "summary": "The setting extends the model of Bates et al.---which provide confidence-bound type guarantees on the performance of a trained ``black-box\" predictor which are parametrised, and nested with respect to a monotonic parameter $\\beta$---to the online setting. The goal of the original setting is to provide risk-controlling prediction sets (RCPS) mapping a feature $X$ to a set $\\mathcal{T}(X)$ in the label space, which is judged on the basis of a predetermined safety criterion. The online extension is then well-justified by the observation that the calibration data itself is often limited without deploying the model in practice, particularly if training occurs in an online fashion. \\\\\nThe contributions of the paper are:\n\n1. An extension of the RCPS notion to the online setting, and a derivation of guarantees that are anytime-valid. In other words, confidence sets are refined as data is accrued, nevertheless maintaining risk control over the entire stream.\n2. An extension of the RCPS which is valid under active learning, where a learner may choose to obtain a label based on the covariates, and a fixed total query budget.\n\nIn addition, the authors provide guarantees in the regret sense on the performance of derived methods in terms of the log-optimality criterion common for evaluating anytime-valid methods, which decouples into the regret of an exp-concave sequence dependent only on a quantity called the betting fraction, which due to log-concavity may be estimated sub-linearly in the number of rounds $T$ (due to exp-concavity of the log-optimality with respect to the betting fraction, this should be $O(\\log(T))$) plus two concentration-type terms dependent on the convergence of two additional parameters derived from the risk, which may be estimated from the data. The convergence of such estimates will depend on the variance of the classifier's risk, and is determined on a case-by case basis. Experiments are included for verification of theoretical guarantees. \n\n\nConclusion:\nWhile there are some weaknesses with regard to the communicability of the results for the intended audience, I believe on balance that the ideas in this paper will turn out to be of broad interest to the experimental community, and have clear practical relevance. From the theoretical perspective, although many of the ideas are directly generated from the theory of e-statistics, this is an encouraging example of tailoring theory to a clear practical need.", "questions": "1. To my understanding, the convergence rate of the estimation terms largely dominate the $O(\\log(T))$ rate from the $G^{\\beta}$-contribution. Are there any non-trivial examples where this isn't the case?\n2. Is there any hope of obtaining an adaptive rate in the growth function---perhaps by means of a tailored variance-reduced estimator---which could yield an instance-dependent result, if the true risk-variance is low? The estimation of $q$ and $r$ seems like it might be particularly troublesome if one tries to derive something for a general case, but this might be a misunderstanding on my part.", "limitations": "I have discussed limitations of the work above, and it seems that the authors have laid out the limitations of the degree of practicability due to the i.i.d. assumption (i.e., if training is coupled to the observed data stream). Nevertheless, I still think this is a solid contribution. With regard to the societal impact, the development of a robust theory of confidence in machine learning is undoubtedly a good thing.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. The formalism is well developed, and demonstrates a high-degree of understanding of the use of e-variables as diagnostic tools of testing processes, and the derived confidence methods are a natural extension of the theory to a very practical setting.\n2. The extension to label-efficient active learning further pushes the abstract theory into the realms of practicability, and the authors provide an example of a set of estimators for the various relevant quantities in the experiments. This gives an (somewhat implicit) recipe for practitioners looking to deploy the tools developed.\n3. The regret bound derived gives an interpretable decomposition of the optimality of the regret of the growth-function (used to bound the log-optimality criterion), which decouples statistical quantities from the betting fraction, which is obtainable from standard online learning methods. \n4. The experiments (although arguably non-extensive) provide minimal necessary examples and concrete estimators for the relevant quantities present in the regret bounds, and demonstrate empirically the convergence of the sum total of relevant components to their optimal values.", "weaknesses": "1. A few more examples of the method being used in practice, along with the guarantees from the regret bound explicated, conditional upon the estimators idiosyncratic to the exact settings treated would be much more helpful than the abstract bound. Although for a theorist these results make sense, and keeping the general form due to the presence of the risk estimator variance and other empirical quantities does find some justification due to the variability of these quantities (which may alter the order of the regret bound), a few examples would really help illustrate the process + guarantees for a practitioner, which I guess would be the intended audience. I think this paper highlights the difficulty of the communicability of theoretical results in a digestible fashion, but does not constitute a weakness of the results themselves. \n2. The experiments are not particularly extensive, and only encompass two examples; a contrived example of uniformly drawn features with Bernoulli labels (which is still a demonstrative diagnostic for the methods described, but have very well-behaved associated estimates), and a more realistic example based on the Imagenet dataset. Furthermore, as mentioned above, the comparison of online performance with respect to the regret bound would be even more helpful.\n3. It would be nice to see some experiments illustrated with harder examples, for example in cases where the convergence of estimates would have a different than $O(\\sqrt{T})$ rate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Here are our point-by-point responses to each of the highlighted weaknesses.\n\n1. **More examples of the method being used in practice, along with examples of choice of estimators for the labeling policy and control variate regression.** We agree that providing more examples would illustrate the utility of our method better, and will add more concrete examples to our final draft. In particular, we note that often machine learning models have some estimate $\\hat{P}(X)$ of the conditional distribution of $Y \\mid X$ (e.g, class probabilities, conditional diffusion models, LLMs, etc.). Thus, for any realized covariate $x$,  we can derive use $\\mathbb{E}_{Y \\sim \\hat{P}(x)}[r(X, Y, \\beta) \\mid X = x]$ from the machine learning model as our choice of $\\widehat{r}(x)$. This expectation can either be calculated analytically (as we do in or classification examples in our experiments) or derived using Monte Carlo (for generative models/LLMs where one can sample from the conditional distribution). In essence, we are already getting a predictor (for free in some sense) from the very model we are calibrating. \n2. **More extensive experiments and empirical analysis of regret bound**. We will aim to add more experiments from different machine learning methods and risk functions to illustrate the efficacy of our procedure (i.e., QA task for LLMs, and image labeling using the COCO-MS dataset), as well as an empirical analysis of our regret bound in our experiments.\n3. **Experiments with estimators of varying rates of convergence.** We agree that more experiments in easier or harder settings could illustrate how different rates of convergence affect our method. However, in practice, one would not train a model from scratch on the labeled data, but use the labeled data to fine-tune existing pretrained models. In fact, our framework is able to learn a labeling policy or predictor using outputs of the pretrained machine learning model we are calibrating, making the learning task much easier. The regret bound elucidates how the error of the label policy and predictor propagates into the growth rate. We do agree that the efficacy of these pretrained models would be different for different tasks, and we will be sure to include empirical analysis of how the accuracy pretrained (or learned) label policies and predictors affect the accuracy of our $\\hat{\\beta}$ estimate.\n\nOur responses to your questions are as follows.\n\n1. **Does the convergence rate of the estimation terms largely dominate the $O(\\log(T))$ rate from the $G^\\beta$-contribution?**\nIn terms of asymptotic rates, we agree with your point that the $O(\\log(T))$ regret incurred by online Newton step (or other online learning algorithms) will be dominated by a typical estimation rate that scales with $O(1 / \\sqrt{T})$ if we are training the label policy and predictor completely from scratch. When our pretrained machine learning models are already accurate, however, we can have fast rates. An example of this is if we assume that the optimal policy/predictor lies in a class of functions that is formed by a linear combination of multiple existing pretrained models we have access to (or we are only interested in comparing against the best linear combination). In that case, the estimation error is the regret of an online linear regression algorithm, and it will have $O(\\log(T) / T)$ convergence (although we would be directly using the $G^\\beta$ regret result, rather than the estimation error result). So our convergence rate does depend on the assumption we make about the accuracy of our pretrained models.\n2. **Obtaining an adaptive rate.** Our result is already instance-adaptive in the sense that the optimal $G^\\beta$ is adaptive to the $X$-conditional variance of the risk, i.e., it is lower bounded by a term that increases as $\\mathbb{E}[\\sigma_\\beta(X)]$ decreases. \nIt is possible that when $\\mathbb{E}[\\sigma_\\beta(X)]$ is low, the optimal predictor is estimated more quickly, and we believe exploration of adaptive convergence rates of different estimators would be an interesting problem to solve in future work. Our focus in this work is to show that the $G^\\beta$ regret depends on estimator error of the policy and predictor in a direct way, and hence having pretrained models that can approximate those well will also improve the efficiency of estimating $\\beta^*$.", "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": "pWmyandDuy", "reviewer": "Reviewer_qKw8", "summary": "The authors, in their work, extend the framework of Risk Controlling Prediction Sets (RCPS) to a sequential setting where data is collected adaptively, providing anytime-valid risk guarantees. Additionally, it proposes a framework for active labeling, which allows for selective querying of true labels within a predefined budget, enhancing the utility of RCPS by leveraging predictors to estimate expected risk based on covariates. Next, the authors extend the setting further and develop an active learning setting and optimal labeling policy and under a fixed label budget.", "questions": "- What are other examples of applications for the proposed framework?\n- How in practise one should select $\\theta$ and $\\alpha$?", "limitations": "I see no potential negative social impact of this work. Discussion on limitations is limited.", "rating": 4, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Extended setting of a risk-controlling prediction set setting.\n- Possibly rigorous in theoretical analysis.", "weaknesses": "- The paper is notation-heavy, considers complex settings, and uses concepts that are not so commonly known. Unfortunately, the authors are doing nothing to help readers understand their work.\n- Many symbols (and there are many) are only introduced once.\n- The goal of the method is easy to miss in the body of the text.\n- The experimental section is hard to understand without reading the theory sections, and there are no meaningful conclusions.\n- There are no summaries, conclusions, schemas, pseudo-codes, or additional intuitions to help the reader understand the paper.\n- Experiments feel very limited.\n- I have doubts about the practicality of the introduced setting, as the paper needs better application examples.\n\nDue to very limited time, I was not able to read related works that were necessary to fully understand this paper, verify the theory, and possibly appreciate it fully. I would like to believe that all the theories presented in the paper are right, but even assuming that. I think the paper is below acceptance due to quite a poor presentation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Our response to each highlighted weakness and question are as follows.\n- **Notational usage and clearer introduction of concepts.** We will clean up our notational usage and introduce more unfamiliar concepts more comprehensively (e.g., risk controlling prediction sets, e-processes, anytime-validity, etc.) in our final draft.\n- **Symbol usage.** We will simplify this as well to make it more accessible, including incorporating the suggestions put forth by reviewer XpAy about the notation for the problem setting.\n- **Goal of method is easy to miss.** The goal of our method is specified in Definition 1 and (3) in our paper --- we will highlight this definition and make it more apparent in the final version.\n- **Experimental section requires reading theory section.** We will separate out the methods we are employing from the theoretical section so they can be read in a standalone fashion (i.e., in an algorithm environment). We do have meaningful conclusions concerning our experiments --- the \"pretrain\" and \"learned\" label policy/predictor combinations that both utilize the machine learning model being calibrated outperform (in terms of label querying efficiency) the naive baseline labeling policies/predictor combos. This shows that, in practice, the models we are calibrating can be used to estimate the conditional risk and variance to a sufficient degree of accuracy such that it significantly improves the label efficiency over the baseline approaches. We will clarify this emphasis in our final version.\n- **Limited experiments**: We will aim to add more experiments from different machine learning methods and risk functions to illustrate the efficacy of our procedure (i.e., QA task for LLMs, and image labeling using the COCO-MS dataset).\n- **Practicality of methods.** We will provide more concrete examples of applications, but we think our framework is quite widely applicable. Here are some examples of applications:\n    - *Reduce query cost in medical imaging.* A medical imaging system that outputs scores for each pixel of image that determines whether there is a lesion or not would want to utilize labels given by medical experts for unlabeled images from new patients. Since the cost of asking experts to label these images is quite high, one would want to query experts efficiently, and only on data that would be most helpful for reducing the number of highlighted pixels.\n    - *Domain adaptation for behavior prediction.* One reason we would want online calibration in a production setting is that we may have much different distribution of data that we do not have access to before deployment. For example, during a navigation task for a robot, we may want to predict the actions of other agents and avoid colliding into them when travelling between two points [1]. Since agents may behave differently in every environment, it makes sense to collect the behavior data in the test environment and update the behavior prediction in an online fashion to get accurate predictions calibrated for specifically the test environment.\n    - *Safe outputs for large language models (LLMs).* One of the goals with large language models is to ensure their responses are not harmful in some fashion (e.g., factually wrong, toxic, etc.). One can view this as outputting a prediction set for the binary label set of $Y \\in \\\\{\\texttt{harmful},\\ \\texttt{not harmful}\\\\}$. Many pipelines for modern LLMs include some form of a safety classifier, which scores the risk level of an output, and determines whether it should be output to the user or not [2, 3], or a default backup response should be used instead. One would want to label production data acquired from user interaction with the LLM and used to calibrate cutoff for the scores that are considered low enough for the response to be allowed through.\n- **Choice of $\\theta$ and $\\alpha$.** The choice of $\\theta$ and $\\alpha$ will depend on the application the user has in mind. Though, since $\\alpha$ is determines the probability the bound holds, reasonable default is to choose it $\\alpha=0.05$. We would like to reiterate that a particular utility of our method is that the probability bound holds *uniformly over every time step*, that is the probability that there is a single $\\hat{\\beta}_t$ for all $t \\in \\mathbb{N}$ that has risk greater than $\\theta$ is less than $\\alpha = 0.05$. $\\theta$ should be chosen based on the risk metric being controlled, and a reasonable default choice could also to be choose $\\theta=0.05$. In the context of image classification, this would mean that the prediction set of possible classes will not cover the true label only 5\\% of the time on average. We will elucidate this point more in the final version. \n\n\n**References**\n\n[1] J. Lekeufack, A. N. Angelopoulos, A. Bajcsy, M. I. Jordan, and J. Malik. Conformal Decision Theory: Safe Autonomous Decisions from Imperfect Predictions. arXiv:2310.05921, 2024.\n\n[2] T. Markov, C. Zhang, S. Agarwal, F. E. Nekoul, T. Lee, S. Adler, A. Jiang, and L. Weng. A Holistic Approach to Undesired Content Detection in the Real World. *AAAI*, 2023\n\n[3] L. Hanu and Unitary team. Detoxify. Github. https://github.com/unitaryai/detoxify, 2020.", "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": "oVW9AH0YuN", "reviewer": "Reviewer_XpAy", "summary": "This paper proposes a probabilistic strategy for stream-based active learning which allows for construction of anytime valid prediction sets. The strategy stems from maximizing the variance process of an e-process, which is also used in designing the prediction sets. Relevant theoretical guarantees (validity and regret) and proof-of-concept experiments are presented.", "questions": "1) Why is assumption 1 in terms of $\\rho$ and not just $r$? Is this needed? If possible, stating the assumption in terms of $r$ is cleaner in my opinion, since this way $\\mathcal X$ and $\\mathcal Y$ become assumption free.\n2) The way section 2.2 is stated, what I collect from it is that the $M_t$ process is robust to adding a $\\mathcal F_t$-adapted and bounded bias term. I can imagine that adding this bias may help with rapid increase of variance process of $M_t$. But I did not understand the motivation of this variance reduction, within the context of section 2. Could you please elaborate?\n3) The proposed optimal labeling policy in Section 3 somewhat resembles a variance maximization techniques which are standard practice in stream-based active learning. Have you looked into the connections? How do these relate?\n4) Doesn't the problem setting allow for comparison to standard active learning policies? Adding these would make the paper relevant to a considerable larger community.", "limitations": "Limitations and assumptions are adequately stated.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "For me, the most interesting contribution of the paper, is that it brings the perspective of safe betting to active learning.\nThe results are not written in the most flashy way, but the overall thought process is straightforward to follow and proofs are clear.", "weaknesses": "- My assessment is that Section 2 lacks novelty, as in, very similar results have been proposed in earlier work under slightly different problem setting. Would be nice to make section 3 the main contribution of the paper, and present section 2 as a background/recipe section which leads to results of Section 3.\n  - The proposed e-processes of Eq (5) and (6) are both from results of Waudby-Smith [2023 & 2024]. If i understand correctly, both of these processes are proposed for a more general frame-work, and the current paper applies it to its problem setting.\n  - Proposition 1 and Theorem 1 are immediate corollaries by definition of the betting e-processes. \n    - It is best that this is merged together and presented as a corollary for the specific choice of $M_t$. \n    - Theorem 1 holds true for any $M_t$ is an e-process under the null. In the proof however, Proposition 1 is invoked. Would be good if the statement is updated and the assumption on $M_t$ is stated in it.\n\n- I am not widely aware of the literature. I just wanted to raise this flag that the related works section might be inadequate. I was expecting more work to have been done in this area. After reading the paper, I do not have a clear image of short history of results leading to this work, and I think this speaks of an incomplete literature review. There's no related work from active learning literature, while they aim to solve a relatively close problem (in cases identical).\n\n\n- The contributions section, particularly the second paragraph, is too technical given what it is already introduced. I would generally shorten the introduction and present a more thorough literature review in the main text.\n- I think parts of the problem setting are confusing, if not incorrect and lines 44-52 should be re-written. \n  - Line 47 says $f$ outputs and action $A$ within a set $\\mathcal A$. But later in Line 50, it is written that $f$ is a prediction set for $Y$.\n  - Connection between $\\mathcal A$ and $\\mathcal Y$ is missing. I'm assuming $f$ output subsets of $\\mathcal Y$ and I don't understand the auxiliary confusing notation of $A$ and $\\mathcal A$.\n  - If $f$ outputs a prediction set, then the notation $A$ and calling it an action is utterly confusing. Within active learning literature, $X$ is typically the action.\n  - It is not evident in the notation of the risk that $\\rho$ depends on $f$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Our responses to the highlighted weaknesses are as follows.\n\n- **Novelty of e-processes.** Thank you for pointing out the error in the proof of Theorem 1 --- we will correct as you have described. While we agree that betting e-process was introduced in [1] and an inverse propensity weighted form was proposed in [2], we disagree that is simply an application of existing work. Our methods are novel in several ways.\n    1. The betting processes of [1, 2] are used to derive confidence sequences for the mean of a bounded (or lower bounded with bounded mean) random variable. In our setting, each betting process does not assume there is a different mean of the random variable tested under the null --- it assumes the same lower bound on the mean, that is $E[r(X, Y, \\beta)] \\geq \\theta$, for each value of $\\beta$. Here, our goal is to estimate $\\beta^*$ --- we only use the fact that under the null, we can derive a random variable that has a bounded mean, and has a lower bound. Our methods are more similar to those in Lemmas 3.1 and 3.2 in [3]. In that work, however, the authors are only interested in designing confidence sequences for estimation, rather than outputting a parameter with risk control. \n    2. The anytime-valid risk control guarantee in Definition 1 is not the same as a merely providing a confidence sequence (CS) for $\\beta^\\*$. If one only provided a confidence sequence, it would not be clear which $\\beta$ one should choose in the CS to ensure that $\\rho(\\beta) \\leq \\theta$ --- one of them is $\\beta^*$ with high probability, but no guarantees would be made about any of the risk of any other $\\beta$, we would not be able to guarantee we can always output a $\\hat{\\beta}_t$ that has risk control at each time step. Thus, key to showing the risk control guarantee in Definition 1 is also the assumption that $\\rho$ is monotonic in $\\beta$. The choice of $\\beta$ that are safe and provide risk control are the ones that have been eliminated from the CS. In fact, the null of our e-process is *the opposite* of the risk control we want to achieve, since our resulting CS captures the set of $\\beta$ that still might have risk that is *at least* $\\beta$. This is a relatively novel formulation. Creating a CS to capture the opposite of the desired result one would want probabilistic guarantees for (in some sense) has been used in auditing election results with risk-limiting audits [4], but the guarantees and use in that application are quite different than ours.\n    3. In [2], there is an assumption that one always has access to an outcome $Y$ for each time step(i.e., the reward), since the application of interest is off policy evaluation, and some action is taken at each time step, and the corresponding reward is obtained. In our setting, we do not receive the outcome $Y$ at all if we did not query a label --- however, the weighted estimator is an unbiased estimator of the actual $r(X, Y, \\beta)$ incurred at each time step, so our e-process is still correct.\n- **Relate work on active learning.** See our point on comparing with active learning in the top-level rebuttal.\n- **Problem setting seems confusing.** In line 50, we say that our action is a prediction set for $Y$ in many applications, b/c the risk we wish to control miscoverage. However, the action doesn't need to be a prediction set (e.g., could be the behavior policy of a safe robot [5]). Our usage of $X$ and $Y$ as covariate and label is standard from previous papers on RCPS, but we will make clear what $A$ means and refers to in our final version. We will also clarify the relationship between $\\rho$ and $f$ explicitly. The relationship is as follows: we define $\\rho(\\beta) = E[r(X, Y, \\beta)] = E[\\ell(Y, f(X, \\beta))]$.\n\nOur responses to the questions are as follows.\n\n1. **Assumption of monotonicity on $\\rho$.** The assumption on $\\rho$ is slightly more general than assuming $r$ is monotonic directly. We appreciate the suggestion and will clarify that monotonicity of $r$ implies monotonicity of $\\rho$ and this is a useful special case of our assumption that is distribution free.\n2. **How the predictor reduces variance.** The e-process in section 2.2 has $\\bar{R}(\\beta)$ inversely weighted by the probability of labeling when a label is queried. We can see that without the predictor set to always output 0, the variance of $\\hat{r}(X, \\beta) + L / q(X) * \\bar{R}(\\beta)$ is larger than $r(X, Y, \\beta)$. However, in the extreme, if we had a perfect predictor, i.e., $r^*(X, \\beta) = r(X, Y, \\beta)$, then we recover exactly $r(X, Y, \\beta)$. This has lower variance, and would result in our growth rate being identical to the e-process in Section 2 that queries every label. For more formal analysis, Theorem 3 encapsulates how the accuracy of the predictor results in changes in the growth rate of our e-processes.\n3. **Relationship to variance maximization in active learning.** Our optimal policy aims to sample covariates $X$ with probability proportional to square root of the expected conditional risk squared --- when the optimal predictor is used, this quantity is the same as the conditional standard deviation of the risk. This is similar in spirit to existing active learning algorithms that aim to select data points that have the highest variance of predictions (e.g., [6]). There is a subtle point here that variance in predictions is not precisely the same as the variance in risk (i.e., in a prediction set setting, if the different predictions are covered by the prediction set anyways, then there is no variance in risk). In addition, many active learning algorithms are deterministic, i.e., they pick the points that best fit a criterion(e.g., conditional variance, disagreement, diversity, etc.) rather than sampling them with some probability.\n4. **Comparison to standard active learning policies.** See previous points on related work in active learning and the relationship to variance maximization.", "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:
We have made point-by-point responses to each review, and posted our rebuttals to each review below. We would also like to note the following.

1. We appreciate the suggestions and concerns the reviewers have brought up about the paper. We will incorporate their suggestions for clarification and make our introduction and setup more accessible to the reader.
2. We will also provide more concrete application examples in the text. We address this in our response to reviewer qKw8, which we replicate here.
    - *Reduce query cost in medical imaging.* A medical imaging system that outputs scores for each pixel of image that determines whether there is a lesion or not would want to utilize labels given by medical experts for unlabeled images from new patients. Since the cost of asking experts to label these images is quite high, one would want to query experts efficiently, and only on data that would be most helpful for reducing the number of highlighted pixels.
    - *Domain adaptation for behavior prediction.* One reason we would want online calibration in a production setting is that we may have much different distribution of data that we do not have access to before deployment. For example, during a navigation task for a robot, we may want to predict the actions of other agents and avoid colliding into them when travelling between two points [1]. Since agents may behave differently in every environment, it makes sense to collect the behavior data in the test environment and update the behavior prediction in an online fashion to get accurate predictions calibrated for specifically the test environment.
    - *Safe outputs for large language models (LLMs).* One of the goals with large language models is to ensure their responses are not harmful in some fashion (e.g., factually wrong, toxic, etc.). One can view this as outputting a prediction set for the binary label set of $Y \in \\{\texttt{harmful},\ \texttt{not harmful}\\}$. Many pipelines for modern LLMs include some form of a safety classifier, which scores the risk level of an output, and determines whether it should be output to the user or not [2, 3], or a default backup response should be used instead. One would want to label production data acquired from user interaction with the LLM and used to calibrate cutoff for the scores that are considered low enough for the response to be allowed through.
3. We appreciate the reviewers' concern about experiments and we will aim to provide more experiments in the final version (i.e., QA factuality task for LLMs, and image labeling for COCO-MS dataset). 

4. **Comparison to active learning.** We briefly summarize the differences and similarities between active learning and our problem. Our problem objective and the methods use to prove their validity are different from typical active learning methods. Active learning (stream-based and pool-based) aims to minimize label queries and still learn the best possible machine learning predictor. Guarantees in this area usually are model-based or learning theoretic, i.e., they propose a model update/selection procedure and query procedure that minimizes the true risk of the model over a known or arbitrary function class, and derive results using a notion of class complexity (when one is developing a procedure that agnostic to the exact function class), or the methods are evaluated empirically for specific models, without guarantees. In contrast, our procedure tunes a calibration parameter that can be wrapped around any black-box model to provide a statistically rigorous risk guarantee. As a result, it means that other types of querying strategies that are deterministic (e.g., disagreement based, diversity based, etc.) cannot be directly imported to our problem setting, since the statistical guarantees we derive require that our queries are probabilistic. Further, we do not think existing active learning necessarily tackle the same objective, since they focus primarily on optimizing the performance of a classifier, rather than guaranteeing risk control while calibrating a parameter. Further development of how to leverage active learning methods in our setting is a fruitful direction for future work.

**References**

[1] J. Lekeufack, A. N. Angelopoulos, A. Bajcsy, M. I. Jordan, and J. Malik. Conformal Decision Theory: Safe Autonomous Decisions from Imperfect Predictions. arXiv:2310.05921, 2024.

[2] T. Markov, C. Zhang, S. Agarwal, F. E. Nekoul, T. Lee, S. Adler, A. Jiang, and L. Weng. A Holistic Approach to Undesired Content Detection in the Real World. *AAAI*, 2023

[3] L. Hanu and Unitary team. Detoxify. Github. https://github.com/unitaryai/detoxify, 2020.

Meta-review: The paper focuses on extending the concept of Risk Controlling Prediction Sets (RCPS) to a sequential setting, where data is collected over time. This extension ensures that risk guarantees are anytime-valid, i.e. simultaneously hold at all time steps. The authors also introduce a framework for active labeling, allowing a model to selectively query labels within a predefined budget while maintaining low risk. They further propose methods to improve the utility of RCPS by leveraging model predictions to estimate conditional risks. The paper characterizes optimal labeling policies under a fixed budget, presents a regret analysis linking estimation errors to the RCPS framework, and demonstrates the effectiveness of these methods through empirical results, showing that their approach requires fewer labels to achieve higher utility compared to traditional labeling strategies.

The reviewers were generally positive in their evaluation of the paper. I recommend accepting it, provided that the authors incorporate the reviewers' suggestions, particularly those related to improving the presentation, in the final version.
Decision: Accept (poster)