Active, anytime-valid risk controlling prediction sets

Authors: ziyu  xu
nikos  karampatziakis
paul  mineiro
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 21:31:17

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.

Main paper: 
 introduction: 
 One of the core problems of modern deep learning systems is the lack of rigorous statistical guarantees one can ensure about the performance of a model in practice. In particular, we are interested in ensuring the safety of a deep learning system, that is, it does not incur undue risk while optimizing for some other objective of interest. This type of guarantee arises in many applications. For example, a deep learning based medical imaging segmentation system that detects lesions [37, 10, 30] should guarantee that it does not miss most of the lesion tissue while remaining precise and minimizing the total amount of tissue that is 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 a method to derive such guarantees on top of the outputs of a wide range of black-box models. They consider the setting where all the calibration data are available as a single dataset before deployment and the model only needs to be calibrated once, i.e., the batch setting. However, this is often unrealistic in a production setup when we have no data concerning the performance of a model before we deploy it, and we wish to update our calibration each time a new data point (or group of data points) arrives. Consequently, it 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, the consideration of using data from production also brings up the concern that this data is often unlabeled, and one must expend resources (either paying experts or utilizing a more powerful model) to label these data points. Hence, we also consider an active setting in which we see the covariate X and choose whether to query the true label Y . Consider the following scenarios where an active and sequential method is relevant.• Reduce query cost in medical imaging. As discussed prior, 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. 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 [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 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 ∈ {harmful, 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 [22, 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 to be allowed through.Example: image classification Let us assume we wish to classify an image X ∈ X , and we have access to a probabilistic classifier s : X → ∆ Y where ∆ Y is the probability simplex over distributions over all possible classes, Y. Let s y (x) denote the probability of class y in the distribution s(x).Based on the probabilities from s(X), we can define C(X, β) to have the labels with the largest probabilities that sum to β ∈ [0, 1] in the following fashion:γ(X, β) := max    γ ∈ [0, 1] : y∈Y 1 {s y (X) ≥ γ} • s y (X) ≥ β    , C(X, β) := {y ∈ Y : s y (X) ≥ γ(X, β)}Now, we can define the miscoverage error of our label set C(X, β) as follows:EQUATIONNow, assume that (X, Y ) ∼ P * , i.e., the images and class are jointly drawn from a fixed distribution. We want to find a choice of β such that ρ(β):= E[r(X, Y, β)] is guaranteed to be at most θ ∈ [0, 1],i.e., the expected miscoverage over the population of images and labels is at most θ.In the above image classification example, we do not simply wish to find any β that ensures ρ(β) ≤ θ -setting β = 1 would trivially ensure this guarantee for any θ ∈ [0, 1]. We also want to minimize the size of our uncertainty set C(X, β). To present this formulation in more general terms, we are interested in solving the following problem for a fixed level of risk control θ ∈ [0, 1]:EQUATION)where g is the utility of our choice. We make the following natural assumption about r, ρ, and g. Assumption 1. g and ρ are monotonically decreasing w.r.t. β and we assume ρ(1) = 0. In addition, ρ is right-continuous.Our image classification example has an expected risk and utility that satisfy the respective monotonicity assumptions, and such risk measures arise in many applications such as natural language question answering [27] , image segmentation [1] , and behavior control for robotics [21, 16] . Assumption 1 implies that maximizing g(β) is equivalent to minimizing β, as g is decreasing in β, and the right-continuity of ρ allows us to define the notion of an optimal calibration parameter that is the solution to (2):β * := min {β ∈ [0, 1] : ρ(β) ≤ θ}.Our goal in this paper is to derive a sequence of upper bounds on β * that quickly approach the true β * but are "anytime safe" in the sense that they are always greater the β * and induce risk under θ, i.e., β ≥ β * implies that ρ(β) ≤ ρ(β * ) ≤ θ. Since we are guaranteed by Assumption 1 that ρ(1) = 0 ≤ θ, we always have a safe option of β = 1 to start with as our upper bound.Our contributions. The primary contributions of this paper are as follows.1. Extensions of RCPS to anytime-valid and active settings. We extend the notion of RCPS in two ways: (1) to enable anytime-valid RCPS which allows one to refine the set as one receives more samples in a 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 a way for incorporating risk predictions from the machine learning model to decrease variance further and reduce the number of labels needed to estimate β * . We formulate this betting framework in Section 2.2. Deriving powerful labeling policies and predictors. We show in Section 3 that our active, anytimevalid RCPS methods are practically powerful and converge to β * in a 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-valid methods [13, 35, 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 β is removed from consideration as β * ). In Section 4 we also show that machine learning model based estimators of the optimal policy and predictors are label efficient in practice through experiments.Related work. Most relevant to this paper is the recent work from Zrnic and Candès [38] that provides a rigorous framework for statistical inference with active labeling policies, and leverages machine learning predictions through prediction-powered 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, we provide finite sample anytime-valid results that are also valid at adaptive stopping times that directly utilize e-process [29] construction of sequential tests. Further, our goal is to provide a time-uniform 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 name this as "anytime-valid" since the risk control condition (i.e., ρ( β t ) ≤ θ) is guaranteed to hold simultaneously at all t ∈ N. Hence, this allows for the user to process a continuous stream of data and control the probability that a β t is chosen at any time t that is "unsafe", i.e., ρ( β t ) > θ. We build on recent work that develops a framework for hypothesis testing and parameter estimation with sequential data collection based on martingales and gambling with virtual wealth known as testing by betting [31] . In this framework, the goal is to design an e-process, (E t ), w.r.t. a null hypothesis H 0 , which satisfies the following properties when true: Definition 2. An e-process, (E t ) t∈N0 , w.r.t. a hypothesis H 0 , is a nonnegative process for which there exists another nonnegative process, (M t ) t∈N0 s.t. the following is true when H 0 is true: (1)i ) = 𝔼[r(X, Y, β i )] ≤ θ i ∈ 1,2,… 1 -α optional (decreases risk variance)E[M 0 ] ≤ 1, (2) M t ≥ E t for all t ∈ N almost surely and (3) E[M t | F t-1 ] ≤ M t-1for all t ∈ N,, i.e., (M t ) is a supermartingale. E-processes will be the main tool we use to construct ( β t ). We leverage the probabilistic bound on e-processes provided by Ville's inequality to prove our anytime-valid risk control guarantee. Fact 1 (Ville's inequality [34] ). For any e-process, (E t ), with initial expectation bounded by 1, i.e., E[E 0 ] ≤ 1, we have thatP exists t ∈ N : M t ≥ α -1 ≤ α for each α ∈ [0, 1].In this paper, all our e-processes will also be nonnegative supermartingales, so we denote them as (M t ). Now, we will specify the null hypotheses in our risk control setting. For each β ∈ [0, 1], we test the null hypothesis H β 0 : ρ(β) ≥ θ for a fixed risk control level θ ∈ [0, 1]. Note that we include equality to θ in the null hypothesis since we do not wish to reject H β * 0 . Let {(M t (β))} β∈[0,1] be a family of e-processes where (M t (β)) is an e-process for H β 0 . Then, we can derive β t for each t ∈ N as follows:EQUATION)Theorem 1. The sequence of estimates ( β t ) in (4) satisfies the anytime-valid risk control guarantee (3), i.e., P(ρ( β t ) ≤ θ for all t ∈ N) ≥ 1 -α.Proof. First, we note that{∃t ∈ N : ρ( β t ) > θ} ⇔ {∃t ∈ N : β t < β * } ⇒ {∃t ∈ N : M t (β * ) ≥ 1/α}.Since H β * 0 is always true by definition of β * , we get that (M t (β * )) is an e-process by Proposition 1. Thus, by applying Ville's inequality, we get that:P(∃t ∈ N : ρ( β t ) > θ) ≤ P (∃t ∈ N : M t (β * ) ≥ 1/α) ≤ α.Now, we will present a concrete example of an e-process. Denote R t (β) := r(X t , Y t , β). We test H β 0 using the betting e-process from Waudby-Smith and Ramdas [35] :EQUATIONwhere (λ t ) is predictable w.r.t. (F t ), i.e., λ t can be determined by F t-1 for each t ∈ N, and 5) is an e-process for all β where H β 0 is true, i.e., where ρ(β) ≥ θ.λ t ∈ [0, (1 -θ) -1 ]. Proposition 1. (M t (β)) in (Proof. We note that (M t (β)) is nonnegative by the support of λ t being limited, i.e.,1 + λ t (θ -r(X t , Y t , β)) ≥ 1 + λ t (θ -1) ≥ 0.Now, we will also show that (M t (β)) is a supermartingale when H β 0 is true.E[M t (β) | F t-1 ] = E[1 + λ t (θ -R t (β)) | F t-1 ] • M t-1 (β) = (1 + λ t (θ -E[R t (β) | F t-1 ])) • M t-1 (β) ≤ M t-1 (β).The second equality is because λ t is measurable w.r.t. F t-1 and the last inequality is by R t (β) being independent of F t-1 and E[R t (β)] ≤ θ being true under H β 0 . Thus, we have our desired result. Now, we have a concrete way to derive ( β t ) that ensures the risk ρ( β t ), is controlled at every time step t ∈ N. However, this requires one to label every example that arrives, i.e., it requires access to entire stream of labels (Y t ). We will now derive a more label efficient way for constructing ( β t ). Remark 1. Ramdas et al. [28] show that e-processes of the form in (5) characterize the set of admissible e-processes (and hence anytime-valid sequential tests) for testing the mean of bounded random variables. Hence, it is an 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-Bernstein based tests [35] ). 
active sampling for risk control: 
 Now, we describe active learning for risk control, where an algorithm sees X t decides whether a label, for the current point, Y t , should be queried or not. At each step t ∈ N, the algorithm produces a label policy q t : X → [q min t , 1] based on the observed data (i.e., F t-1 ). It then queries the label, Y t , with probability q t (X t ) that is lower bounded by a constant, q min t . Let L t be the indicator random variable for whether the tth label is queried, i.e., L t ∼ Bern(q t (X t )).To produce a label efficient method, one would hope to label the most "impactful" data points that result in the largest growth of M t (β) for choices of β ∈ (0, β t ), i.e. that are still in consideration for the next β t+1 . For the labeling policies we consider in this paper, we let q min t ∈ [0, 1] be a lower bound on the labeling probability, i.e., q t (X t ) ≥ q min t almost surely. Thus, we can derive the following e-process for any sequence of labeling policies (q t ).EQUATION)Proposition 2. Let (q t ) be a sequence of labeling policies, and (λ t ) be a sequence of betting parameters, and let both sequences be predictable w.r.t. (F t ). Then, (M t (β)) in ( 6) is an e-process for all β where H β 0 is true, i.e., where ρ(β) ≥ θ.Proof. The proof of this is similar to that of inverse propensity-weighted e-processes derived in Waudby-Smith et al. [36] . We know that (M t (β)) is nonnegative by the support of λ t being limited:1 + λ t θ - L t q t (X t ) • R t (β) ≥ 1 + λ t θ -(q min t ) -1 ≥ 0,where the first inequality is by R t (β) ≤ 1 and q t (X t ) ≥ q min t , and the second inequality is by λ t ≤ ((q min t ) -1 -θ) -1 . Now, we will also show that (M t (β)) is a supermartingale. We first show the following upper bound:E L t q t (X t ) • R t (β) | F t-1 = E E[L t | X t , F t-1 ] q t (X t ) R t (β) | F t-1 = E[R t (β) | F t-1 ] ≤ θ. (7)The first equality is by further conditioning on X t , and the second equality is since L t is defined to be a Bernoulli random variable with parameter q t (X t ) when conditioned on X t and F t-1 . The last inequality is by H β 0 being true. Now, we have thatE[M t (β) | F t-1 ] = 1 + λ t θ -E L t q t (X t ) R t (β) | F t-1 M t-1 (β) ≤ M t-1 (β),where the inequality is by (7) . Hence, we have shown that (M t (β)) is a nonnegative supermartingale, and hence also an e-process, under H β 0 .Theorem 2. ( β t ) defined w.r.t. (6) satisfies the anytime-valid risk control guarantee (3). This is a 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.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 a result, we also have an empirical estimate of E[r(X, Y, β) | X = x] for each β ∈ [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 r t : X × [0, 1] → [0, 1] be an estimator of the risk incurred by parameter β conditional on x ∈ X for each time step t ∈ N. ( r t ) is predictable w.r.t. (F t ).Where does r come from? We note that often machine learning models have some estimate P (X) 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 useE Y ∼ P (x) [r(X, Y, β) | X = x]from the machine learning model as our choice of r(x, β). This expectation can either be calculated analytically (as we do in or classification examples in our experiments) or derived using Monte Carlo approximation (for generative models such as LLMs, one can sample from the conditional distribution). In essence, we can obtain a predictor from the very model we are calibrating. Further, we can have a sequence of ( r t ) -we may update our predictor using new (X t , Y t ) pairs we receive for calibrating ( β t ) as well. Now, we define our e-process that utilizes our predictor as follows:EQUATIONand we restrict λ t ∈ [0, ((q min t ) -1 -θ) -1 ] (or in other words, q min t ≥ λ t /(1 + λ t θ)). Note that this e-process recovers the active e-process defined in (6) if we set r t (•, β) = 0 for all t ∈ N. Proposition 3. (M t (β)) as defined in (8) is an e-process for H β 0 .Proof. Since the restriction on (λ t ) ensures M t (β) is nonnegative, to show that (M t (β)) is an e-process, it is sufficient to show:E[λ t (θ -r t (X t , β) -L t • q t (X t ) -1 • Rt (β)+) | F t-1 ] = λ t (θ -E[ r t (X t , β) + L t • q t (X t ) -1 • Rt (β) | F t-1 ]) = λ t (θ -E[ r t (X t , β) + E[L t • q t (X t ) -1 | X t , F t-1 ] • Rt (β) | F t-1 ]) = λ t (θ -E[ r t (X t , β) + Rt (β) | F t-1 ]) = λ t (θ -E[R t (β) | F t-1 ]) ≤ 0.The 3rd equality is by definition of L t , the last equality by the definition of Rt , and the last inequality is due to H β 0 being true.The role of r t (X t , β) is to accurately predict R t (β). Bad predictions can increase the variance of Rr (β) and lead to slower growth of M t (β), 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 M t (β). 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.We derive an estimate of r * from a pretrained machine learning model, r pretr , to be our choice of predictor for all time steps. We also derive an estimate of σ(x, β), σ pretr (x, β), from the pretrained model. We also learn a sequence of normalizing constants (C t ) s.t. the budget is satisfied. Our labeling policy in this case is q t (x) = σ(x, β t-1 )/C t , where we want to optimize our policy for the previous best bound on β * , β t-1 . We denote this method as "pretrain".3. Estimating q * β and r * : We learn sequences of models ( σ plugin t) and ( r plugin t ) using the labeled data points. We preprocess the outputs from σ pretr and r pretr to use as the input features to these models, respectively. Each of these sequences of models are then updated at every step. We also similarly learn a sequence of normalization constants (C t ) for deriving the final labeling policy (q t ).We provide more details on how are methods are formulated in Appendix B. We run all our experiments on a 48-core CPU on the Azure platform, after using a GPU to precompute the predictions made by neural network models. We set θ = 0.1, α = 0.05, and B = 0.3 for all our experiments. 
optimal labeling policies: 
 Since the goal of having an 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 (M t (β)) defined in (8) . Define the following function, for some β ∈ [0, 1], of a labeling policy q, predictor r, and betting parameter λ where we let L ∼ Bern(q(X)) and (X, Y ) ∼ P * :G β (q, r, λ) := log 1 + λ θ -r(X, β) - L q(X) R(β)where R(β) := r(X, Y, β) -r(X, β).Define the growth rate at the tth step of (M t (β)) asG β t := E[G β t (q t , r t , λ t )],where we let G β t be identical to G t but with X and Y replaced with X t and Y t , 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 a metric, i.e., we want our e-process to be log-optimal [13, 35, 19] . Log-optimality is also called the Kelly criterion in finance [18] and it is known that maximizing the growth rate of a process is equivalent to minimizing the expected time for the process to exceed a threshold, i.e., for our sequential test to reject a value of β, in the limit as the threshold approaches infinity [5] . Thus, in an 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 we can produce.Let B ∈ [0, 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 q t , r t , and λ t that are the solutions to the following optimization problem:max q, r,λ E L∼q(X) [G β (q, r, λ)] s.t. E[q(X)] ≤ B.Since solving the above optimization problem is analytically difficult, one can instead maximize a lower bound on the expected growth [33, 26, 25] :EQUATIONwhich holds when λ ∈ [0, (2(q min ) -1 -2θ) -1 ], where q min := inf x∈X q(x). We can further simplify We can use the lower bound in (9) to formulate the following optimization problem.EQUATIONLet (q * , r * , λ * ) be the tuple that is the solution to (10) . We can analytically show what r * is. Proposition 4. The optimal predictor r * in the solution to (10) is r * (x, β) = E[r(X, Y, β) | X = x] for each x ∈ X .We defer the proof to Appendix A.1. The optimal choice of q * has the following formulation. Proposition 5. If we fix r and λ, the solution to the optimization problem in (10) is given by q * β where q* β (x) ∝ E[ R(β) 2 | X = x] for each x ∈ X if such a q * β exists.We defer the proof to Appendix A.2. Let σ β (x) := V[r(X, Y, β) | X = x] be the conditional standard deviation of r(X, Y, β). Now, we can argue that the solution to the optimization problem on the growth rate lower bound in (10) has the following characterization. Corollary 1. The optimal choice of q * β and λ * that solves (10) isq * β (x) := σ β (x) E[σ β (X)] • B, λ * := θ -ρ(β) 2((θ -ρ(β)) 2 + E[σ β (X)] 2 • B -1 + V[r(X, Y, β)]) if q * β (x) ∈ [0, 1] for all x ∈ X , and λ * ≤ (2(inf x∈X q * β (x)) -1 -2θ) -1 .The resulting growth rate has the following lower bound:E[G β t (q * , r * , λ * )] ≥ E[ G β t (q * , r * , λ * )] = (θ -ρ(β)) 2 4((θ -ρ(β)) 2 + E[σ β (X)] 2 • B -1 + V[r(X, Y, β)])We can show this is true as a consequence of Proposition 4, Proposition 5, and solving the quadratic equation that arises for the growth rate to derive the optimal choice of λ * . Further, we note that we can define regret of a sequence (λ t ) compared to λ * on G β t as follows. Definition 3. The G β -regret at the tth step of a sequence of betting parameters (λ t ) for a risk upper bound θ ∈ [0, 1], and a sequence of labeling policies (q t ) and predictors ( r t ) where q t (x) ≥ ε > 0 for all x ∈ X and t ∈ N almost surely is defined as follows:Reg t := max λ∈[0,(2ε -1 -2θ) -1 ] t i=1 E[ G β t (q t , r t , λ) | F t-1 ] -E[ G β t (q t , r t , λ t ) | F t-1 ].Since G β t (q, r, λ) is exp-concave in λ, existing online learning algorithms such as Online Newton Step (ONS) [8] can get o(T ) regret guarantees, which means that the growth rate of (λ t ) averaged over time will approach (or exceed) the optimal growth rate under λ * . For simplicity of analysis, we make the following assumption about the labeling probability of the optimal policy, q * β . Assumption 2. Let ε > 0 be a positive constant. Assume that q * β (x) ≥ ε for each x ∈ X . The lower bound in the above assumption is an analog of the propensity score lower bound on optimal policies for adaptive experimentation which are needed for performing valid inference in that setting [17, 7] . Further, do not need this to hold on every β, since we are not necessarily interested in log-optimality w.r.t. fringe β that are quite far away from β * -in practice having this assumption hold for values of β near β * suffices to develop an estimator β 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 (λ t ) be a sequence with G β -regret (Reg t ) and (q t ) and ( r t ) are sequences of labeling policies and predictors that are all predictable w.r.t. (F t ). For a positive constant ε > 0, let q t (x) ≥ ε > 0 for each t ∈ N and x ∈ X almost surely. Under Assumption 2 for the same ε, the following bound holds:t i=1 E[ G β t (q * , r * , λ * ) -G β t (q t , r t , λ t )] ≤ Reg t + t i=1 O(E[|q(X t ) -q * β (X t )|] + E[( r t (X t ) -r * (X t , β)) 2 ]).We defer the proof to Appendix A.3. The proof idea follows a 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. Theorem 3 relates the estimation error of q * β (x) and r * (x, β) to how quickly β will be deemed "safe". Hence, if we have good estimates of those quantities, then we can produce an estimates ( β t ) that are small and close to β * while remaining safe. We will now describe some practical methods for calculating q t and r t . 
experiments: 
 We use PyTorch to model our (q t ) and ( r t ), and we use the following methods to formulate them. 21. 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".We have a simple data generating process of sampling P t ∼ Uniform[0, 1] and let Y t | X t ∼ Bern(X t ). This simulates the setting we have with our real data where we have an accurate pretrained classifier that have a probability estimate of Y t of being 0 or 1. We let our covariates X t = P t . As a result, our risk function is the false positive rate r FPR (X, Y, β) := 1 {X ≥ β, 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 β t to β * = 1 -√ 2α after a set number of queried labels. In Figure 2 , we plot the average β t reached after a 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 β t was unsafe and ρ( β t ) > θ at any time step. We can see that all methods control the desired safety violation rate at the predetermined level α. Figure 2 : Experimental results for different methods for our numerical simulation setup. We can see that "pretrain" and "learned" perform better by getting lower average β t uniformly across number of labels queried -the dotted line in Figures 2b and 2c is β * = 0.5578. Each method also has low safety violation rate, i.e., is below the dotted line of α = 0.05 in Figure 2a .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 is 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. (c) Average βt vs. 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, β * = 0.8349, and is delineated by the dotted line in Figures 3b and 3c . Again, each method also has low safety violation rate, i.e., is below the dotted line of α = 0.05 in Figure 3a .In Figure 3 , we plot the average β t 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 as well under the predetermined level of α = 0.05. 
additional related work: 
 Casgrain et al. [6] provide anytime-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 [26, 25, 32] , using regret bounds for betting-based e-processes to show either derivations for the growth rate of a 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-valid inference have included inverse propensity weights have been for off policy evaluation [36] , adaptive experimentation [7] , or estimating the weighted mean of a finite population [33] . 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 experimentation for average treatment effect estimation [14, 17] that attempt to derive a no regret treatment policy and outcome regressor that produces an estimator with a 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 a different optimal policy.Question: Does the paper provide open access to the data and code, with sufficient instructions 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 supplement (see above).Guidelines:• The answer NA means that paper does not include experiments requiring code. Justification: Our work is statistical methodology/theory 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 in practice, but there are no direct societal impacts as far as we can discern. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (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 as 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
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 an 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-Smith et al. [36] 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 (ACI) [11, 12] to 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 in future work. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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. 
 
 Appendix: Proofs that have been deferred from the main body of the paper are contained here.We can rewrite the objective in the following way:EQUATIONMaximizing (11) is the same as minimizing the following equivalent expressions:EQUATIONwhere we derive the 1st equality from the law of total variance, and the 2nd equality from the fact that r(X, β) is fixed given X.Since the only term that r affects is the integral term in (12) , we can choose each r(x, β) for each x ∈ X to minimize the following:EQUATION)If we remove the constants (i.e., terms unaffected by r(x, β)), and note that q(x) -1 -1 > 0, we get that minimizing ( 13) is equivalent to minimizing2E[r(X, Y, β) | X = x] r(x, β) -r(x, β) 2 .This is equivalent to minimizng the squared error, i.e., (E[r(X, Y, β)| X = x] -r(x, β)) 2 , which means that r * (x, β) = E[r(X, Y, β) | X = x], which gets us our desired result.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:min q p(x) q(x) E[ R(β) 2 | X = x] dx s.t. p(x)q(x) dx ≤ B.We can define φ(x) := p(x)q(x) rewrite this asmin φ p(x) 2 φ(x) E[ R(β) 2 | X i = x] dx s.t. φ(x) dx ≤ B.Assume we can define a valid q * β where q * β (x) ∈ [0, 1] for each x ∈ X that satisfies the following conditions:φ(x) ∝ p(x) E R(β) 2 | X = x q * β (x) ∝ E R(β) 2 | X = x .Explicitly, we define q * β as follows:q * β (x) = E R(β) 2 | X = x E E R(β) 2 | X = x • B.One can show its optimality by considering some other labeling policy q ′ where E[q ′ (X)] = B (we use a similar proof technique from importance sampling Owen [24, § 9.1]). Now, let φ * (x) := p(x)q * β (x) and φ ′ (x) = p(x)q ′ (x)p(x) 2 φ * (x) E[ R(β) 2 | X i = x] dx = E E R(β) 2 | X = x p(x) B • E[ R(β) 2 | X i = x] dx = E E R(β) 2 | X = x 2 • B -1 = p(x) φ ′ (x) • φ ′ (x) • E R(β) 2 | X = x dx 2 • B -1 = B • p(x) φ ′ (x) • φ ′ (x) B • E R(β) 2 | X = x dx 2 ≤ p(x) 2 φ ′ (x) E R(β) 2 | X = x dx,where the last line is by Cauchy-Schwarz, since φ ′ (x)/B is a valid p.d.f. Hence, we have shown our desired result.By definition of Reg t , we know thatt i=1 E[ G β (q i , r i , λ * )] -E[ G β (q t , r i , λ i )] ≤ Reg tby taking an expectation over F i-1 for each term in the summation Hence, what remains to be shown is the following:EQUATIONLet Rt (β) := r(X, Y, β)-r t (X, β) and R * (β) := r(X, Y, β)-r * (X, β). We first note the following identity using ( 12):E[ G β (q * , r * , λ * )] -E[ G β (q t , r t , λ * )] =(λ * ) 2 E V r t (X, β) - L q t (X) Rt (β) | F t-1 -V r * (X, β) - L q * β (X) R * (β)Now, we make the following derivations for the difference between the variance (V) terms:EQUATIONThe 1st equality is by substituting in the identity from (12) . The 1st inequality is a result ofV[r(X, Y, β) | X = x] ≤ 1 4 , since r(X, Y, β) ∈ [0, 1], and q * β (x), q t (x) ∈ [ε, 1] almost surely. The 2nd inequality is by upper bounding q * β (x) -q t (x) by its absolute value. Now, if we plug ( 15) into ( 14), take the expectation over F t-1 , and take the summation over t, we get our desired result.In this section, we discuss additional details about how we implement our methods described in Section 4.For the "pretrain" policy, we use an estimate of the conditional mean and variance derived from s.r pretr (x, β) := y̸ ∈C(x,β) s y (x), σ pretr (x, β) := r pretr (x, β) • (1 -r pretr (x, β)).These estimates may not be accurate, but might still represent a reasonable partitioning of the feature space where σ(x, β) and r * (x, β) are similar. Hence, for σ plugin t and r plugin t , we model them as linear regresssion models where inputs are a binning of r pretr (x, β) and σ pretr (x, β), respectively. We then learn the regression model parameters on training data.For any predictor σ, we optimize the Lagrangian corresponding to (10) , which is defined as follows for a fixed λ t .L(ν t , q t ) = E[ G(q t , r t , λ t )] -ν t (E[q t (X t )] -B) = E λ t θ - L t q t (X) r(X, Y, β) -ψ(λ t ) θ - L t q t (X) r(X, Y, β) 2 -ν t (E[q t (X)] -B) = λ t (θ -ρ(β)) -λ 2 t E θ -r t (X, β) - L t q t (X) R(β) 2 -ν t (E[q t (X)] -B)Since we know the optimal form of r t , we optimize it separately by taking an optimization step with the loss of squared error, (r(X, Y, β) -r t (X, β)) 2 , for each labeled example for a grid of β values.To derive the solution, we simplify playing the minimax game with the above Lagrangian to the following objective:max qt min νt -E 1 q t (X) • (r(X, Y, β) -r t (X, β)) 2 -ν t (E[q t (X)] -B)In the case of both "pretrain" and "learned" methods, we parameterize our q t in the following fashion:q t (x) = σ t (x, β t-1 ) exp(c t ) ,where our normalization constant C t = exp(c t ) for some value c t ∈ R to ensure it is nonnegative.σ t is updated separately. For "pretrain", it is 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, β) -r t (X, β)) 2 -σ t (X, β) 2 ) 2 .Hence, the only thing that remains to optimize c t , which now simply means we need to solve the following problem (where we treat β t-1 as fixed):max ct min νt -c t + ν t 1 exp(c t ) E[ σ t (X, β t-1 )] -BThe actual game payoff we play is the stochastic approximation of the Lagrangian in the following form:L(ν t , c t ) = -c t -ν t σ t (X t , β t-1 ) exp(c t ) -B .At each step, we take an optimization step on c t towards maximizing the above loss, and determine ν t 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 [23] for all of learning and optimization which requires no hyperparameter or learning rate selection.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to 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 a 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 one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe 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.Code at github.com/neilzxu/active-rcps 


Decision: 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.

Reviews: review: paper_summary: paper_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. \\
The contributions of the paper are:

1. 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.
2. 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.

In 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. 


Conclusion:
While 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.
strength_weakness: strength_weakness: 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. 
2. 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.
3. 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.
questions: 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?
2. 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- Many symbols (and there are many) are only introduced once.
- The goal of the method is easy to miss in the body of the text.
- The experimental section is hard to understand without reading the theory sections, and there are no meaningful conclusions.
- There are no summaries, conclusions, schemas, pseudo-codes, or additional intuitions to help the reader understand the paper.
- Experiments feel very limited.
- I have doubts about the practicality of the introduced setting, as the paper needs better application examples.

Due 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.
questions: questions: - What are other examples of applications for the proposed framework?
- How in practise one should select $\theta$ and $\alpha$?
limitations: limitations: I see no potential negative social impact of this work. Discussion on limitations is limited.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
  - 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.
  - Proposition 1 and Theorem 1 are immediate corollaries by definition of the betting e-processes. 
    - It is best that this is merged together and presented as a corollary for the specific choice of $M_t$. 
    - 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.

- 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).


- 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.
- I think parts of the problem setting are confusing, if not incorrect and lines 44-52 should be re-written. 
  - 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$.
  - 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$.
  - 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.
  - It is not evident in the notation of the risk that $\rho$ depends on $f$.
questions: 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.
2) 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?
3) 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?
4) 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: Limitations and assumptions are adequately stated.

Comments: title: Rebuttal recap
Re: Rebuttal by Authors
Rebuttal (continued)
comment: We thank the reviewers for reading our rebuttals and recommending or approving acceptance of our paper. We also appreciate the thoughtful feedback that we have received throughout the review process, and we will be sure to incorporate this in the ways we've described in our rebuttal.
Thank you for your detailed response to my rather short review. Other reviews also pointed out areas for improvement in terms of the presentation, so I hope you will address them in the next revision of your paper. Since the promised improvement in the presentation cannot be verified at the moment, I keep my score as it is. However, I'm okay with your work being accepted, since the other reviews recommended it.
Thank you for your answers, and I apologize for the late response.

My questions are addressed, and I hope that the paper is updated accordingly -- I still think that the contributions would benefit a lot from a more crisp presentation e.g. by positioning the work more vividly.

Overall, I agree with reviewer 1rh6 and recommend for acceptance.
I acknowledge the authors' response, and thank them for their detailed answers to my points and questions.

While it appears that we've all had some difficulty related to the presentation, I feel that my understanding of the method and its utility/scope has been greatly enhanced by this discussion, and am intrigued to see this line of work built upon from both practice and theory (it's a bias, but the adaptive rates question certainly appeals). Furthermore, I do see this work as a very nice potential bridge between theory and practice, and would like to see more work in machine learning with this kind of scope. 

I would advise a more targeted rework of the presentation of results (for example, by incorporating the concrete suggestions by XpAy) such that researchers with a more practical leaning can get what they need out of it. Otherwise, I stand by my assessment of the paper, and recommend it for acceptance.
**Additional comments on problem setting**. For example, we may wish to calibrate the aggressiveness of a robot's behavior policy that is parameterized by $\beta$ (e.g., [5]), where the goal is to reach a destination while avoiding obstacles. The action $A$ may be the control policy of the robot based on the environment, and the risk would be the distance to the nearest obstacle over the entire trajectory of the robot as it travels to its destination. We may want this risk to be controlled on average over the distribution of environments. Our framework applies to such as setup, and hence we term the output based on the covariate $X$ an action $A = f(X)$ rather than limiting it to only being a prediction set.

We also include our top level comment on related work to active learning here:

**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] I. Waudby-Smith and A. Ramdas. Estimating means of bounded random variables by betting. *Journal of the Royal Statistical Society Series B (Statistical Methodology)*, 2023.

[2] 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.

[3] P. Casgrain, M. Larsson, and J. Ziegel. Sequential testing for elicitable functionals via supermartingales. *Bernoulli*, 2024.

[4] I. Waudby-Smith, P. B. Stark, and A. Ramdas. Rilacs: Risk limiting audits via confidence sequences. *International Joint Conference on Electronic Voting*, 2021.

[5] 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.

[6] D. Cacciarelli and M. Kulahci. Active learning for data streams: a survey. *Machine Learning*, 2024.