Conceptio › Archive › arXiv CS

arXiv CSopen access

Revisiting Active Sequential Prediction-Powered Mean Estimation

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

Published as a conference paper at ICLR 2026

R EVISITING ACTIVE S EQUENTIAL P OWERED M EAN E STIMATION

P REDICTION -

Jun-Kun Wang University of California San Diego [email protected]

Maria-Eleni Sfyraki University of California San Diego [email protected]

arXiv:2604.18569v1 [stat.ML] 20 Apr 2026

A BSTRACT In this work, we revisit the problem of active sequential prediction-powered mean estimation, where at each round one must decide the query probability of the ground-truth label upon observing the covariates of a sample. Furthermore, if the label is not queried, the prediction from a machine learning model is used instead. Prior work proposed an elegant scheme that determines the query probability by combining an uncertainty-based suggestion with a constant probability that encodes a soft constraint on the query probability. We explored different values of the mixing parameter and observed an intriguing empirical pattern: the smallest confidence width tends to occur when the weight on the constant probability is close to one, thereby reducing the influence of the uncertainty-based component. Motivated by this observation, we develop a non-asymptotic analysis of the estimator and establish a data-dependent bound on its confidence interval. Our analysis further suggests that when a no-regret learning approach is used to determine the query probability and control this bound, the query probability converges to the constraint of the max value of the query probability when it is chosen obliviously to the current covariates. We also conduct simulations that corroborate these theoretical findings.

I NTRODUCTION

The mean estimation problem is a classical inference task that has seen revived interest in machine learning and statistics over the last few years. While the conventional setting is well-understood, numerous works have explored this problem under diverse settings and assumptions, aiming to enhance our understanding of the inherent challenges of learning from limited data. Recently, a line of work has investigated the design of efficient mean estimators under the robust framework, including the setting of a constant fraction of adversarial outliers (Cheng et al., 2020), heavy-tailed symmetric distributions without moment assumptions (Novikov et al., 2023), mean-shift contamination in multivariate identity Gaussian distributions (Diakonikolas et al., 2025), sparse mean estimation in high dimensions (Pensia, 2024), online high-dimensional mean estimation (Kane et al., 2024). A few other recent works have explored other structural considerations, such as collaborative normal mean estimation in the presence of strategic agents (Chen et al., 2023), communication-efficient mean estimation in a distributed setting (Ben-Basat et al., 2024), vector mean estimation under the shuffle model of privacy (Asi et al., 2024), dynamic multi-group mean estimation (Aznag et al., 2023), leveraging favorable distribution structure to improve sub-Gaussian rate (Dang et al., 2023), among others. This variety of scopes in the mean estimation setup highlights its relevance as a foundational task for inference. A direction that has attracted substantial attention with the increasing integration of machine learning is mean estimation through an active inference perspective (Zrnic & Candes, 2024). Specifically, the problem focuses on estimating the mean label from a set of unlabeled observations, by leveraging a limited label collection budget and the abundant but potentially biased predictions of a machine learning model. Under this setup, active statistical inference provides a data collection strategy that utilizes the budget more effectively by taking into consideration which labels it would be more beneficial to acquire. Specifically, it prioritizes the collection of labels where the model exhibits higher uncertainty and uses the model predictions for instances where the model is more confident. The same work considers querying the labels in both the batch and sequential setting, where the latter 1

Published as a conference paper at ICLR 2026

additionally allows updating the model as the ground-truth labels are obtained, and provides asymptotically valid confidence intervals for the estimator in question in both cases. The non-asymptotic analysis of the estimator was not provided in the prior work. 1 In this work, we draw on the sequential active statistical inference perspective by providing nonasymptotic guarantees for the sequential active mean estimation problem. While prior work of Zrnic & Candes (2024) have established the asymptotic normality of their proposed estimator, our work investigates the sequential mean estimation problem further under the light of an online updating scheme and provides a non-asymptotic analysis with guarantees that hold at any time while going through the data. More specifically, we first formulate the scheme of active sequential mean estimation as an online update step, and establish a convergence guarantee √ that incorporates the conditional variance of the update direction and achieves a rate of Õ 1/ t for sufficiently large t. Furthermore, motivated by a series of experimental findings, which reveal an intriguing pattern of the label sampling rule considered by previous work, we are led to examine more closely the role of the model uncertainty component through the current covariate. In particular, to adhere to the budget constraint and ensure a small variance of the estimator, Zrnic & Candes (2024) derive a sampling rule that is a mixture of the uniform rule and a model uncertainty estimator weighted by a mixing constant. Our experimental findings across a variety of tasks indicates that employing the mixture rule or relying solely on the uniform policy results in comparable confidence interval widths, with the uniform policy occasionally producing marginally narrower intervals. This observation suggests that, the contribution of model uncertainty with respect to the label of the current covariate might be brittle in practice. Based on this insight, we formulate the problem of tuning the query policy as an online learning task that does not rely on the current covariate, and whose validity is supported by the strong sublinear regret guarantees of the classical Follow-the-Regularized-Leader (FTRL) algorithm (Abernethy et al., 2012). Remarkably, we demonstrate that under this no-regret learning approach, the query policy converges to the maximum value permitted by the budget constraint. Our theoretical findings are further validated through experiments on three real-world and one synthetic dataset.

P RELIMINARIES AND N OTATION

We begin by introducing the problem setup. We consider the setting where we have access to a sequence of data points x1 , x2 , . . . xT ∈ X ⊂ R from an unknown, fixed distribution PX . Each data point xt is associated with a ground-truth label yt ∈ Y ⊂ R, drawn from an also unknown, fixed distribution PY |X . We assume that the ground-truth labels are not known a priori, and the cost to obtain them could be high. We are interested in estimating the mean label µy = E[yt ]. Additionally, we assume that at each time t ∈ [T ] we have access to a black-box predictive model ft (·) : X → Y, which can continually evolve by using the samples collected up to round t − 1 to update. More specifically, we require ft ∈ Ft−1 , where Ft denotes the σ-algebra generated by the first t data points xs , 1 ≤ s ≤ t. Sequential active mean estimation seeks to construct an efficient estimator by observing data points one at a time and deciding whether to query each ground-truth label. Under a limited labeling budget, the objective is to sequentially acquire labels in a way that most effectively improves the accuracy of the mean estimator. Specifically, if we denote by Tlab the total number of collected labels, we require that the policy of querying the ground-truth label ensures E[Tlab ] ≤ Tb , where we assume that Tb ≪ T . Let πt (xt ) denote the probability of collecting the label of data point xt at time t, where πt ∈ Ft−1 , and let ξt ∼ Bernoulli(πt (xt )) denote the labeling decision used to indicate whether the ground-truth label yt was collected (ξt = 1) or not (ξt = 0). Zrnic & Candes(2024) PT 1 propose the sequential active mean estimator ŵ = T t=1 ft (xt ) + (yt − ft (xt )) πtξ(xt t ) . It is easy to verify that ŵ is unbiased, i.e., E[ŵ] = µy . Notably, Zrnic & Candes (2024) show that the optimal choice of querying policy πtopt is according to the uncertainty of the prediction model, and 1 However, we acknowledge that Appendix C of Zrnic & Candes (2024) outlines a related scheme based on estimating bounded means via testing by betting (Waudby-Smith & Ramdas, 2024), which may come with certain non-asymptotic guarantees. We further provide a discussion in Appendix B.

Published as a conference paper at ICLR 2026

it satisfies πtopt (xt ) ∝

r h i 2 E (yt − ft (xt )) |Ft−1 ,

where the above expression hides a normalization constant to ensure that E[πtopt (xt )] ≤ Tb /T . However, since PY |X is unknown, the authors suggest fitting a model on past data (x, y) to approximate the uncertainty ut (xt ) by |yt − ft (xt )| for a given xt , and then setting the querying policy to be proportional to that estimate. To ensure that the budget constraint is met in practice, the remaining budget at time t is set as the difference between the expected budget to be used up to time t and the budget already used up to time t − 1, i.e. T∆,t = tTb /T − Tlab,t−1 . Then, the querying policy is set to πt (xt ) = min {ηt ut (xt ), T∆,t }[0,1] , where the subscript [0, 1] denotes clipping to [0, 1], ηt is a normalizing constant set to ηt = Tb / (T E [ut (xt )]), and E [ut (xt )] is approximated empirically. This practical rule aims to balance frequent sampling under high uncertainty against overusing the budget. However, since the estimated uncertainty can be consistently low, and thus the budget could be underutilized, the policy is occasionally set to πt (xt ) = (T∆,t )[0,1] . An additional concern is that an inaccurate uncertainty estimate may be close to zero, while the quantity |yt − ft (xt )| is actually large, which would in turn yield an amplified estimator variance. To address this issue, the authors suggest that the policy is set to a mix of the described policy with the uniform rule as (λ)

πt (xt ) = (1 − λ)πt (xt ) + λπtunif (xt ), where πtunif (xt ) = Tb /T , and λ ∈ [0, 1]. In the presence of sufficient historical data, λ can be tuned (λ) by minimizing the empirical estimate of the estimator variance induced by the policy πt . However, due to insufficient historical data in the sequential setting, λ is set to a fixed value.

Interval width

0.07 While the related work simply sets Estimator the mixing parameter to 0.5, we [ZC24] (mixing=0.05) explore different parameter values 0.05 [ZC24] (mixing=0.1) for the mean estimation experiment [ZC24] (mixing=0.5) in Zrnic & Candes (2024) by run[ZC24] (mixing=0.8) 0.04 ning their public implementation on [ZC24] (mixing=1.0) the same post-election survey dataset Center (2020) as in their experiments. 0.03 We keep all their other parameter choices unchanged. Figure 1 shows 0.02 how the interval width varies with 1855 2370 3029 3871 4946 the sampling budget Tb under difTb ferent values of the mixing parame- Figure 1: Post-election survey dataset. Interval width vs. ter in the query policy 2 . We find the sampling budget parameter T for different values of the b that setting λ = 1, corresponding to mixing parameter of the query probability scheme in Zrnic using the uniform query policy that & Candes (2024). Averaged over 10 repeated runs. ignores model uncertainty, produces confidence intervals that are slightly narrower than those obtained with λ = 0.5. We further evaluate the method on two additional real-world datasets and one synthetic dataset, and observe a similar pattern, where the uniform query policy (λ = 1) yields confidence intervals that are comparable to, and often tighter than those from λ = 0.5. Due to space constraints, the corresponding figures are included in Appendix A.

These similar empirical patterns motivate us to further investigate this observation. A plausible initial explanation is that the empirical performance improves when less weight is assigned to the uncertainty-based component, possibly because the uncertainty predictor may not be reliable. However, our theoretical analysis later suggests that this factor alone may not account for the phenomenon, which might be surprising. 2 The code, provided in Jupyter notebook format, to reproduce Figure 1 as well as others in the paper is available in the supplementary material.

Published as a conference paper at ICLR 2026

R ELATED W ORK

Active Statistical Inference. The ideas in this work are motivated by the recent approach of Active Statistical Inference (Zrnic & Candes, 2024). Extending this framework, Angelopoulos et al. (2025) propose a method that optimizes the sampling rate between gold-standard and pseudo-labels rather than relying on a fixed label budget, and derive an improved active sampling policy. A recent work by Gligorić et al. (2025) utilizes LLM verbalized confidence scores to guide their sampling policy and subsequently performs active inference by combining the LLM and human annotations. Prediction Powered Inference. The Active Statistical Inference framework is grounded in the idea of Prediction Powered Inference (PPI) Angelopoulos et al. (2023a), which differs from the former in that it assumes the availability of a small, pre-labeled dataset. The work of Angelopoulos et al. (2023b) introduces PPI++, which improves the computational efficiency of PPI by addressing the intractability of the original confidence interval construction and using a tuning parameter to control the influence of the model predictions based on their quality. Subsequent works (Dorner et al., 2025; Mani et al., 2025) analyze the critical role of the correlation between the gold-standard and model-generated labels for the performance of PPI. Following the original PPI formulation, several works have proposed extensions and refinements in various directions, including addressing estimator bias in the few-label regime (Eyre & Madras, 2025), incorporating an inverse probability weighting (IPW) bias-correction term (Datta & Polson, 2025), combining predictions from multiple foundation models via a hybrid augmented IPW estimator (De Bartolomeis et al., 2025), applying a stratification approach (Fisch et al., 2024), exploring a bootstrap-based variant (Zrnic, 2024), employing Bayes-assisted approaches (Cortinovis & Caron, 2025; Li & Ignatiadis, 2025) and extending the ideas of PPI to e-values (Csillag et al., 2025). Other applications of the PPI framework include LLM-assisted rank-set construction (Chatzi et al., 2024), average treatment effects from multiple datasets (Wang et al., 2025), clinic trial outcomes (Poulet et al., 2025), autoevaluation in machine learning systems (Boyeau et al., 2025; Park et al., 2025), machine learning generated surrogate rewards for multi-armed bandits (Ji et al., 2025b). A few other works have explored alternative machine-learning assisted estimators, e.g., Schmutz et al. (2023); Egami et al. (2023); Miao et al. (2023); Miao & Lu (2024); Gan et al. (2024). We refer the reader to Appendix B for a more detailed discussion on related work.

N ON - ASYMPTOTIC A NALYSIS OF THE M EAN E STIMATOR

In this section, we provide the non-asymptotic analysis of the sequential active mean estimator. Since the sequential active estimation setting requires going over the data points sequentially, we can formulate the active mean estimator of Zrnic & Candes (2024) as an online update step at each time t ∈ [T ], as 1 ξt wt+1 = wt + ft (xt ) + (yt − ft (xt )) , (1) T πt (xt ) where we set the initial point w1 = 0, and let T be the horizon. We denote gt := ft (xt ) + (yt − ft (xt )) πtξ(xt t ) . A simple calculation shows that E[gt ] = µy , the mean of the random variable (yt )t≥1 . Before proceeding with the asymptotic analysis of (1), we will need a technical lemma, known as Freedman’s inequality, which is stated below for completeness. Lemma 1 (Freedman’s inequality (Freedman, 1975), see also e.g., Lemma 3 in Rakhlin et al. (2012)). Let ζ1 , . . . , ζT be a martingale difference sequence with a uniform upper bound |ζt | ≤ b, ∀t. Denote Vt the sum of conditional variances of ζs ’s., i.e., Vt = √ Pt Vt . Then, for any 0 < δ < 1/e and T ≥ 4, s=1 Var(ζs |ζ1 , . . . , ζs−1 ). Also, denote σt := we have ! t op n X p Prob ∃t ≤ T : ζs ≥ 2 max 2σt , b log(1/δ) log(1/δ) ≤ log(T )δ. s=1

Lemma 1 provides a concentration inequality for martingales, yielding a high-probability bound on the deviation of a martingale sum from its mean that adapts to the accumulated conditional 4

Published as a conference paper at ICLR 2026

variance. We are now ready to present the non-asymptotic analysis result for the sequential active mean estimator, as detailed in Theorem 1 Theorem 1. Fix a time horizon T ≥ 4. Assume each random variable gt is bounded, i.e., |gt | ≤ G for a constant G > 0. Denote σt2 := E (gt − µy )2 |Ft−1 the conditional variance, where Ft−1 is the filtration up to t − 1. Then, for any δ ∈ (0, 1/e), with probability at least 1 − δ, ∀t ∈ [T ] : r r √ ) log(T ) 2 max 2 St , (G + |µy |) log log(T log δ δ t |wt+1 − µy | ≤ + 1− |µy | , T T (2) Pt where St = s=1 σs2 . Theorem 1 demonstrates a data-dependent bound on the accuracy of the update wt that holds with high-probability at any time t ∈ [T ]. We make a couple remarks on this result. When t ≪ T and the 1 − Tt |µy | term dominates the other term on (2), it is possible to observe a rate that is slower √ than O(1/ t) in the initial stage, i.e., 1 − Tt ≈ 1. However, after this burn-in stage (i.e., when t is qP t 2 sufficiently large), the first term will eventually become dominant. Furthermore, when s=1 σs p dominates (G + |µy |) log(log(T )/δ), which happens easily when t is sufficiently large and δ is not too small, the rate becomes  qP  p t 2 log(log(T )/δ) s=1 σs . |wt+1 − µy | = O  (3) T

Pt 2 ≤ 2t(G2 s=1 σs ! q √ t (G2 +µ2y ) log(log(T )/δ) 1 √ = O . T t

P OLICY OF Q UERYING THE G ROUND T RUTH

Using the trivial bound

+ µ2y ), we can further express the rate as

√ In the previous section, we discussed that the update wt of (1) will have a rate of O t/T = √ Pt O 1/ t in the worst case. An observation is that when s=1 σs2 ≪ 2t(G2 + µ2y ), one might get √ an even faster rate than O(1/ t). This2 motivates us to control the sum of the conditional variances, Pt Pt 2 i.e., s=1 σs = s=1 E (gs − µy ) |Fs−1 , by proposing an algorithm to determine the query probability of the ground-truth label online, which we detail next. We begin by introducing the following observation on the decomposition of the conditional variance of the update step, which will subsequently guide the choice of the online query policy. Lemma 2. The conditional variance has the following decomposition: " # " 2 2 2 E (gt − µy ) |Ft−1 = E ft (xt ) Ft−1 + E (yt − ft (xt )) "

1 Ft−1 πt (xt )

+ 2E ft (xt )(yt − ft (xt )) Ft−1 − µ2y . Furthermore, assume that the query policy at time t is Ft−1 -measurable, i.e., there exists a random variable pt ∈ [0, 1], measurable with respect to Ft−1 , such that πt (xt ) = pt . Then, we have # " " # 1 1 2 2 E (yt − ft (xt )) Ft−1 = E (yt − ft (xt )) Ft−1 . πt (xt ) pt

Published as a conference paper at ICLR 2026

We observe that the only term involving the query probability πt (xt ) that contributes to 2 1 the conditional variance is E[(yt − ft (xt )) πt (x |Ft−1 ]. We now consider the query policy t) at time t that is fully determined by the information up to t − 1. With this, we can 2 2 1 |Ft−1 ] = p1t E[(yt − ft (xt )) |Ft−1 ]. However, we note that rewrite E[(yt − ft (xt )) πt (x t) 2

E[(yt − ft (xt )) |Ft−1 ] cannot be known since this depends on the unknown distributions of yt and ft (xt ). Therefore, we assume that there is an oracle, denoted as Φt (xt ) ∈ R+ , which is available at time t and provides an approximation of the quantity of interest, i.e., " # 1 2 Φt (xt ) ≤ E (yt − ft (xt )) Ft−1 ≤ c0 Φt (xt ), c1 2

for some constants c0 , c1 > 0 such that Φt (xt ) ≈ E[(yt − ft (xt )) | Ft−1 ]. Equipped with such an oracle, we propose specifying the query probability pt based on the following rule: t−1 X 1 Φs (xs ) pt ← arg min γθt−1 p + p2 , where θt−1 := − , 2 p2s p∈[β,τ ] s=1

(4)

where γ > 0, τ ∈ (0, 1], β ∈ (0, τ ] are user-specified parameters, and we let θ0 := 0. The following lemma shows that pt has a closed-form expression. Lemma 3. The update (4) has a closed-form expression, which is pt = max{β, min{τ, −γθt−1 }}. We note that one can specify τ = TTb , where Tb denotes the targeted maximum number of rounds in which the ground-truth is queried, which ensures that the query probability pt at time t does not exceed the ratio TTb . This constraint is also akin to the sampling rule E[pt ] ≤ TTb considered in Zrnic & Candes (2024). On the other hand, the parameter β encourages certain exploration at each round by preventing the query probability pt from becoming too close to 0. The update (4), in a nutshell, is one of the celebrated online learning algorithms called Follow-theRegularized-Leader (FTRL), (see, e.g., Abernethy et al. (2012); Wang et al. (2024), and Chapter 7 of Orabona (2019)). FTRL is known to enjoy a sublinear regret bound when the sequence of loss functions is convex. We propose leveraging the strong guarantee of FTRL to determine the query probability pt online. More specifically, in our scenario, one first determines the query probability t) pt , after which it receives a loss function defined as ℓ̃t (p) := Φt (x , which is a convex loss function p in (0, 1]. In online learning, a common goal is to minimize the regret. In our setting, the regret against a benchmark p∗ ∈ [β, τ ] over t rounds is defined as: Regrett (p∗ ) :=

t X

ℓ̃s (ps ) −

s=1

t X

ℓ̃s (p∗ ) =

t X Φs (xs ) s=1

s=1

−

t X Φs (xs ) s=1

p∗

(5)

where the first sum is the cumulative loss of the updates (ps )s≥1 and the second one is that of the benchmark. A sublinear regret bound against any benchmark p∗ in the same decision space [β, τ ] of the learner implies that the sequence of query probabilities can compete with the best fixed query probability in hindsight. On the other hand, given that the oracle’s output is non-negative, i.e., ∀s : Φs (·) ≥ 0, it follows that arg minp∗ ∈[β,τ ] ℓ̃s (p) = τ. Combining these implies that an online learner may need to approach τ eventually to achieve a sublinear regret. In other words, to maintain sublinear regret, the query probabilities pt will need to converge toward the constraint upper bound τ = TTb . In particular, we have that the average regret is in fact vanishing (a.k.a. no-regret learning), i.e., Regrett t (p∗ ) → 0 as t → ∞, as the following lemma shows. Lemma 4. (see e.g., Theorem 3 in Luo (2017)) FTRL satisfies Regrett (p∗ ) ≤ γ

t X ˙ 2 R(p∗ ) − minp∈K R(p) ℓ˜s + , γ s=1

Published as a conference paper at ICLR 2026

˙ s (p) for any comparator p∗ ∈ K := [β, τ ], where γ > 0, R(p) := 21 p2 , and ℓ˜s := dℓ̃dp

. p=ps

We note that Lemma 4 is a classical result in online learning literature, see also Orabona (2019); Shalev-Shwartz et al. (2012). The guarantee suggests that if one chooses γ = √1T , then the regret √ of FTRL is O( T ), which grows sublinearly with T , provided that the size of the derivative is bounded. The following lemma shows that the size of the derivative in the regret bound is bounded whenever the oracle’s output is bounded. Lemma 5. Assume that the range of oracle’s output is bounded, i.e., ∀t : Φt (xt ) ≤ B, for a 2 ˙ 2 constant B > 0. Then, ∀t : ℓ̃t ≤ B β4 . Pt ∗2 ∗2 In the following theorem, we denote σ1:t := s=1 σs,(t) , the cumulative conditional variance ob∗ tained under a fixed query probability p1:t ∈ K := [β, τ ], as if the method had committed the best fixed probability in hindsight over t rounds rather than following the query policy from (4), i.e., Pt p∗1:t = arg minp∈[β,τ ] s=1 ℓ̃s (p). Theorem 2. Assume that there is an oracle that outputs Φt (xt ) at each t such that c11 Φt (xt ) ≤ " # 2

E (yt − ft (xt ))

Ft−1 ≤ c0 Φt (xt ) for some constant c0 , c1 > 0 and that ∀t : Φt (xt ) ≤ B. 2

Set the parameter γ = √1T βB . Using the query policy (4), we have that, with probability at least 1 − δ, ∀t ∈ [T ]: r r √ log(T ) log(T ) 2 max 2 Ψt , (G + |µy |) log log δ δ t |wt+1 − µy | ≤ + 1− |µy | , T T for any β

∈

(0, τ ) and τ

c0 (R(p∗ 1:t )−minp∈K R(p)) β2

√

∈

(0, 1), where Ψt

≤

∗2 c0 c1 σ1:t + 2c0 √tT βB2 +

p √ ∗2 + What Theorem 2 shows is a data-dependent bound. We note that Ψt ≤ c0 c1 σ1:t 1/4 O T . From our earlier discussion, once a sufficient burn-in period has elapsed so that the √

first term in the upper bound dominates, the non-asymptotic rate takes the form O √ ∗2 c0 c1 σ1:t 1 O + T 3/4 , provided that δ is not too small. T

Ψt T

E XPERIMENTS

In this section, we report experimental results by comparing the proposed method with two baselines. For clarity, Algorithm 1 presents the protocol for the task of active sequential mean estimation. Compared to the procedure described in Algorithm 2 of Zrnic & Candes (2024), the key difference is that we also update the uncertainty predictor whenever the ML model for label prediction is updated. Furthermore, we split the dataset with ground-truth labels into two disjoint subsets, which are accumulated as described on Line 13, and use these subsets to expand the data available for updating the ML model ft+1 and its uncertainty predictor ut+1 , respectively. This treatment of the disjoint training sets is intended to enable the uncertainty predictor to more accurately estimate the uncertainty of the ML model when it is applied to unseen data at test time. The first baseline was also considered in the prior work of Zrnic & Candes (2024). T (yt − f (xt ))ξt Tb 1X f (xt ) + , where ξt ∼ Bernoulli wTUniform := T t=1 Tb /T T

(6)

For this baseline, we note that the ML predictor is fixed. As discussed in Zrnic & Candes (2024), this comparison can showcase the benefit of data collection. Following the terminology of Zrnic & Candes (2024), we refer to this baseline as “uniform sampling.” 7

Published as a conference paper at ICLR 2026

Algorithm 1 Protocol of Active Sequential Mean Estimation Require: Significance level parameter α ∈ (0, 1), target sampling budget Tb > 0, and batch size B. 1: Initialize a machine learning (ML) model f1 (·) : X → Y to predict the labels of data. 2: Initialize an uncertainty predictor u1 (·, ·) : X × f1 (·) → R+ for the model’s predictions. 3: Initialize the dataset for updating the model Dtrain and the dataset for the uncertainty predictor Duncertainty . 4: Set Dtmp ← ∅, w1 ← 0 5: for t = 1, . . . , T do 6: Observe features xt of a sample and determine the query probability pt for getting its label. 7: Sample the binary random variable ξt ∼ Bernoulli(pt ). 8: if ξt = 1 then 9: Obtain the ground-truth label yt and set Dtmp ← Dtmp ∪ {(xt , yt )}. 10: Increase b by 1. 11: end if 12: if B = b then 13: Randomly split Dtmp into two datasets with equal sizes, D♣ and D♠ . 14: Set Dtrain ← Dtrain ∪ D♣ and set Duncertainty ← Duncertainty ∪ D♠ . 15: Update the ML model to ft+1 (·) using the dataset Dtrain ; similarly, update the uncertainty predictor ut+1 (·, ·) : X × ft+1 (·) → R+ using the dataset Duncertainty . 16: Reset b ← 0. 17: else 18: ft+1 ← ft and ut+1 ← ut . 19: end if 20: Update the estimate wt+1 = wt + T1 ft (xt ) + (yt − ft (xt )) pξtt . 21: end for 2 PT ξt f (x ) + (y − f (x )) − w . 22: Set σ̂ 2 ← T1 t t t t t T +1 t=1 pt 23: Output: (1 − α)-confidence interval CIα = wT +1 ± z1−α/2 √σ̂ . T

The second baseline is the scheme proposed in Zrnic & Candes (2024) for implementing Line 6 in Algorithm 1, which determines the query probability pt , as described in the earlier preliminary section. 6.1

DATASETS AND EXPERIMENTAL SETUP

We compare the algorithms on three real-world datasets. The first dataset concerns the politeness scores of texts based on human annotations, which is available from the works of Ji et al. (2025a) and Gligorić et al. (2025). For each article, there is an associated 21-dimensional feature vector and a score predicted by ChatGPT. We consider the task of regression for this dataset, where the ML model is trained on the 22-dimensional vector (the 21 features plus the ChatGPT score) to predict the average score of 5 human judgments. Following the suggestion in Zrnic & Candes (2024), an uncertainty estimator ut (·, ·) : X × ft (·) → R+ is used to predict the absolute error |ft (xt ) − yt | from xt without seeing the label yt beforehand. This predicted uncertainty is then used as the input to their proposed scheme for determining the query probability pt at round t. The uncertainty estimator is also updated based on the collected samples with queried ground-truth labels once every batch of B labeled samples is collected, as depicted in Algorithm 1. For our proposed scheme, we need to construct the approximation oracle Φt (xt ). In practice, we implement this by performing a linear regression on the squared residual error (ft (xt ) − yt )2 for the samples in Duncertainty , and this estimator is updated regularly after every batch of size B. The second dataset concerns predicting the ratings of wine reviews, which is available in Ji et al. (2025a). Each review is associated with the price of the wine and four additional binary attributes representing the regions, along with the rating predicted by OpenAI’s GPT-4o mini based on the reviewers’ comments. We also consider the task of regression for this dataset, where a linear regression model is trained on the aforementioned covariates to predict the human ratings. The uncertainty 8

Published as a conference paper at ICLR 2026

13.4

13.6

13.8 14.0 confidence width

14.2

1.0

coverage

interval width

0.46 0.40 0.35 0.30 0.27

819

1046

1337

1709

0.9 0.8 0.6 819

2184

FTRL [ZC24] uniform sampling

0.7 1160

1501

1842

2184

Figure 2: Politeness score analysis. Left: Intervals of randomly selected trials. Middle: Average confidence

89.4

89.5

89.6 89.7 89.8 confidence width

89.9

0.29 0.26 0.23 0.21 0.18

1.0

coverage

interval width

width across repeated trials vs. sampling budget Tb . Right: Percentage of trials that cover the true mean.

613

783

1000

1278

0.9 0.8 0.6 613

1634

FTRL [ZC24] uniform sampling

0.7 868

1123

1378

1634

Figure 3: Wine review analysis. Left: Intervals of randomly selected trials. Middle: Average confidence

0.68

0.70 0.72 confidence width

0.74

0.04 0.03 0.03 0.02 0.02

1.0

coverage

interval width

width across repeated trials vs. sampling budget Tb . Right: Percentage of trials that cover the true mean.

1852

2368

3026

3867

4943

0.9 0.8

FTRL [ZC24] uniform sampling

0.7 0.6 1853

2625

3398

4170

4943

Figure 4: Post-election survey.. Left: Intervals of randomly selected trials. Middle: Average confidence width across repeated trials vs. sampling budget Tb . Right: Percentage of trials that cover the true mean.

predictor and the approximation oracle Φt (xt ) have the same form and are updated in the same fashion as for the first dataset. The third dataset is a post-election survey dataset considered in Zrnic & Candes (2024), where the original source is from Center (2020). This dataset includes the approval ratings of two politicians, where approval is represented by yt ∈ {0, 1}. Following the experimental setup in Zrnic & Candes (2024), the ML model f (·) is implemented as an XGBoost model. Since the response yt is binary, the task can be treated as a classification problem. We hence follow the treatment in Zrnic & Candes (2024) by using the uncertainty predictor as ut (xt , ft (·)) = 2 min{ft (xt ), 1 − ft (xt )} for their proposed scheme, where ft (xt ) is the predicted probability of yt = 1 for xt given by the XGBoost model. On the other hand, the required approximation oracle Φt (xt ) is trained in the same fashion as in the first two tasks. We also conduct experiments on a synthetic dataset, the details of which can be found in Appendix E. 6.2

R ESULTS

In this subsection, we report the results of the conducted experiments. Figures 2 - 4 and Figure 6 (provided in Appendix E due to space limitations) show the intervals of randomly selected trials, average confidence width, and coverage for each of the datasets considered over 50 trials. Across all four datasets examined, we find that the FTRL policy yields performance comparable to the mixture policy proposed by Zrnic & Candes (2024), in the sense that both result in confidence intervals of similar width, while both outperform the baseline policy. Notably, in two of the datasets, the FTRL policy attains marginally narrower confidence intervals. With respect to coverage of the true mean, all three policies yield a high proportion of confidence intervals that successfully include the true value. Our theoretical analysis and experimental findings consistently indicate that when the query probability pt at time t is oblivious to the current covariates xt , while still permitted to depend on past covariates or past uncertainty estimates, the optimal strategy is simply to set pt = TTb in accordance with the sampling budget. This result, implies that constructing an uncertainty predictor, or leveraging uncertainty estimates in any form, does not appear to provide a clear advantage for this type 9

Published as a conference paper at ICLR 2026

of policy. Perhaps unexpectedly, this rules out any benefit from conditioning on past covariates or past uncertainty estimates. Furthermore, as our figures illustrate, even when the query probability ignores the current covariates, FTRL, which quickly converges to the constant TTb and then maintains it, performs on par with the more sophisticated scheme of Zrnic & Candes (2024), which explicitly uses the current features xt to determine the query probability. ACKNOWLEDGEMENTS The authors thank the anonymous reviewers for their constructive suggestions, which helped enrich the discussion of related work and clarify the experimental setup. The authors also appreciate the support by NSF CCF-2403392, as well as by the Google Gemma Academic Program and Google Cloud Credits.

R EFERENCES Jacob D Abernethy, Elad Hazan, and Alexander Rakhlin. Interior-point methods for full-information and bandit online learning. IEEE Transactions on Information Theory, 58(7):4164–4175, 2012. Anastasios N Angelopoulos, Stephen Bates, Clara Fannjiang, Michael I Jordan, and Tijana Zrnic. Prediction-powered inference. Science, 382(6671):669–674, 2023a. Anastasios N Angelopoulos, John C Duchi, and Tijana Zrnic. PPI++: Efficient prediction-powered inference. arXiv preprint arXiv:2311.01453, 2023b. Anastasios N Angelopoulos, Jacob Eisenstein, Jonathan Berant, Alekh Agarwal, and Adam Fisch. Cost-optimal active ai model evaluation. arXiv preprint arXiv:2506.07949, 2025. Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy Nguyen, Kunal Talwar, and Samson Zhou. Private vector mean estimation in the shuffle model: Optimal rates require many messages. In International Conference on Machine Learning (ICML), 2024. Abdellah Aznag, Rachel Cummings, and Adam N Elmachtoub. An active learning framework for multi-group mean estimation. Advances in Neural Information Processing Systems (NeurIPS), 36:32602–32635, 2023. William H. Beluch, Tim Genewein, Andreas Nurnberger, and Jan M. Kohler. The power of ensembles for active learning in image classification. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9368–9377, 2018. doi: 10.1109/CVPR.2018.00976. Ran Ben-Basat, Amit Portnoy, Gil Einziger, Yaniv Ben-Itzhak, Michael Mitzenmacher, et al. Accelerating federated learning with quick distributed mean estimation. In International Conference on Machine Learning (ICML), 2024. Pierre Boyeau, Anastasios N. Angelopoulos, Tianle Li, Nir Yosef, Jitendra Malik, and Michael I. Jordan. Autoeval done right: Using synthetic data for model evaluation. In International Conference on Machine Learning (ICML), 2025. Pew Research Center. American trends panel (ATP) Wave 79, 2020. URL https://www. pewresearch.org/science/dataset/american-trends-panel-wave-79/. Accessed: 2025-09-17. Ivi Chatzi, Eleni Straitouri, Suhas Thejaswi, and Manuel Gomez-Rodriguez. Prediction-powered ranking of large language models. In Advances in Neural Information Processing Systems (NeurIPS), 2024. Yiding Chen, Jerry Zhu, and Kirthevasan Kandasamy. Mechanism design for collaborative normal mean estimation. Advances in Neural Information Processing Systems (NeurIPS), 36:49365– 49402, 2023. Yu Cheng, Ilias Diakonikolas, Rong Ge, and Mahdi Soltanolkotabi. High-dimensional robust mean estimation via gradient descent. In International Conference on Machine Learning (ICML), pp. 1768–1778, 2020. 10

Published as a conference paper at ICLR 2026

Stefano Cortinovis and Francois Caron. Ab-ppi: Frequentist, assisted by bayes, prediction-powered inference. In International Conference on Machine Learning (ICML), 2025. Daniel Csillag, Claudio Jose Struchiner, and Guilherme Tegoni Goedert. Prediction-powered evalues. In International Conference on Machine Learning (ICML), 2025. Trung Dang, Jasper Lee, Maoyuan’Raymond’ Song, and Paul Valiant. Optimality in mean estimation: beyond worst-case, beyond sub-gaussian, and beyond 1 + α moments. Advances in Neural Information Processing Systems (NeurIPS), 36:4150–4176, 2023. Sanjoy Dasgupta. Two faces of active learning. Theoretical Computer Science, 412(19):1767–1781, 2011. ISSN 0304-3975. doi: https://doi.org/10.1016/j.tcs.2010.12.054. URL https://www. sciencedirect.com/science/article/pii/S0304397510007620. Algorithmic Learning Theory (ALT 2009). Jyotishka Datta and Nicholas G Polson. Prediction-powered inference with inverse probability weighting. arXiv preprint arXiv:2508.10149, 2025. Piersilvio De Bartolomeis, Javier Abad, Guanbo Wang, Konstantin Donhauser, Raymond M Duch, Fanny Yang, and Issa J Dahabreh. Efficient randomized experiments using foundation models. arXiv preprint arXiv:2502.04262, 2025. Ilias Diakonikolas, Giannis Iakovidis, Daniel Kane, and Thanasis Pittas. Efficient multivariate robust mean estimation under mean-shift contamination. In International Conference on Machine Learning (ICML), 2025. Florian E Dorner, Vivian Yvonne Nastl, and Moritz Hardt. Limits to scalable evaluation at the frontier: Llm as judge won’t beat twice the data. In International Conference on Representation Learning (ICLR), 2025. Melanie Ducoffe and Frederic Precioso. Adversarial active learning for deep networks: a margin based approach, 2018. URL https://arxiv.org/abs/1802.09841. Naoki Egami, Musashi Hinck, Brandon Stewart, and Hanying Wei. Using imperfect surrogates for downstream inference: Design-based supervised learning for social science applications of large language models. Advances in Neural Information Processing Systems (NeurIPS), 36:68589– 68601, 2023. Benjamin Eyre and David Madras. Regression for the mean: Auto-evaluation and inference with few labels through post-hoc regression. In International Conference on Machine Learning (ICML), 2025. Adam Fisch, Joshua Maynez, R. Alex Hofer, Bhuwan Dhingra, Amir Globerson, and William W. Cohen. Stratified prediction-powered inference for effective hybrid evaluation of language models. In Advances in Neural Information Processing Systems (NeurIPS), volume 37, 2024. David A Freedman. On tail probabilities for martingales. the Annals of Probability, pp. 100–118, 1975. Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep Bayesian active learning with image data. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1183–1192. PMLR, 06–11 Aug 2017. URL https://proceedings.mlr.press/v70/ gal17a.html. Feng Gan, Wanfeng Liang, and Changliang Zou. Prediction de-correlated inference: A safe approach for post-prediction inference. Australian & New Zealand Journal of Statistics, 66(4): 417–440, 2024. Kristina Gligorić, Tijana Zrnic, Cinoo Lee, Emmanuel Candes, and Dan Jurafsky. Can unconfident llm annotations be used for confident conclusions? In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pp. 3514–3533, 2025. 11

Published as a conference paper at ICLR 2026

Steve Hanneke. Theory of disagreement-based active learning. Found. Trends Mach. Learn., 7(2–3): 131–309, June 2014. ISSN 1935-8237. doi: 10.1561/2200000037. URL https://doi.org/ 10.1561/2200000037. Wenlong Ji, Lihua Lei, and Tijana Zrnic. Predictions as surrogates: Revisiting surrogate outcomes in the age of ai. arXiv preprint arXiv:2501.09731, 2025a. Wenlong Ji, Yihan Pan, Ruihao Zhu, and Lihua Lei. Multi-armed bandits with machine learninggenerated surrogate rewards. arXiv preprint arXiv:2506.16658, 2025b. Ajay J. Joshi, Fatih Porikli, and Nikolaos Papanikolopoulos. Multi-class active learning for image classification. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 2372– 2379, 2009. doi: 10.1109/CVPR.2009.5206627. Daniel M Kane, Ilias Diakonikolas, Hanshen Xiao, and Sihan Liu. Online robust mean estimation. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3197–3235. SIAM, 2024. Sida Li and Nikolaos Ignatiadis. Prediction-powered adaptive shrinkage estimation. In International Conference on Machine Learning (ICML), 2025. Xiang Li, Yunai Li, Huiying Zhong, Lihua Lei, and Zhun Deng. Statistical inference under performativity. arXiv preprint arXiv:2505.18493, 2025. Haipeng Luo. Introduction to Online Learning CSCI 699. Lecture Note, 2017. URL https: //haipeng-luo.net/courses/CSCI699/lecture2.pdf. Pranav Mani, Peng Xu, Zachary C Lipton, and Michael Oberst. No free lunch: Non-asymptotic analysis of prediction-powered inference. arXiv preprint arXiv:2505.20178, 2025. Jiacheng Miao and Qiongshi Lu. Task-agnostic machine-learning-assisted inference. Advances in Neural Information Processing Systems (NeurIPS), 37:106162–106189, 2024. Jiacheng Miao, Xinran Miao, Yixuan Wu, Jiwei Zhao, and Qiongshi Lu. Assumption-lean and data-adaptive post-prediction inference. arXiv preprint arXiv:2311.14220, 2023. Gleb Novikov, David Steurer, and Stefan Tiegel. Robust mean estimation without moments for symmetric distributions. Advances in Neural Information Processing Systems (NeurIPS), 36: 34371–34409, 2023. Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv:1912.13213, 2019. Art B. Owen. Monte Carlo theory, methods and examples. https://artowen.su.domains/ mc/, 2013. Sangwoo Park, Matteo Zecchin, and Osvaldo Simeone. Adaptive prediction-powered autoeval with reliability and efficiency guarantees. arXiv preprint arXiv:2505.18659, 2025. Ankit Pensia. A subquadratic time algorithm for robust sparse mean estimation. In International Conference on Machine Learning (ICML), 2024. Pierre-Emmanuel Poulet, Maylis Tran, Sophie Tezenas du Montcel, Bruno Dubois, Stanley Durrleman, and Bruno Jedynak. Prediction-powered inference for clinical trials. medRxiv, 2025. Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In International Conference on Machine Learning (ICML), 2012. Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Brij B. Gupta, Xiaojiang Chen, and Xin Wang. A survey of deep active learning, 2021. URL https://arxiv.org/abs/ 2009.00236. 12

Published as a conference paper at ICLR 2026

Hugo Schmutz, Olivier Humbert, and Pierre-Alexandre Mattei. Don’t fear the unlabelled: Safe semisupervised learning via debiasing. In Proceedings of the International Conference on Learning Representations (ICLR), 2023. Greg Schohn and David Cohn. Less is more: Active learning with support vector machines. In Pat Langley (ed.), Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000), Stanford University, Stanford, CA, USA, June 29 - July 2, 2000, pp. 839–846. Morgan Kaufmann, 2000. Burr Settles. Active learning literature survey. Computer Sciences Technical Report 1648, University of Wisconsin–Madison, 2009. URL http://axon.cs.byu.edu/˜martinez/ classes/778/Papers/settles.activelearning.pdf. Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends® in Machine Learning, 4(2):107–194, 2012. Simon Tong and Daphne Koller. Support vector machine active learning with application sto text classification. In Pat Langley (ed.), Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000), Stanford University, Stanford, CA, USA, June 29 - July 2, 2000, pp. 999–1006. Morgan Kaufmann, 2000. Gokhan Tur, Dilek Hakkani-Tür, and Robert E. Schapire. Combining active and semi-supervised learning for spoken language understanding. Speech Communication, 45(2):171–186, 2005. ISSN 0167-6393. doi: https://doi.org/10.1016/j.specom.2004.08.002. URL https://www. sciencedirect.com/science/article/pii/S0167639304000962. Jun-Kun Wang, Jacob Abernethy, and Kfir Y Levy. No-regret dynamics in the fenchel game: A unified framework for algorithmic convex optimization. Mathematical Programming, 205(1): 203–268, 2024. Yuxin Wang, Maresa Schröder, Dennis Frauen, Jonas Schweisthal, Konstantin Hess, and Stefan Feuerriegel. Constructing confidence intervals for average treatment effects from confounded and unconfounded data. In International Conference on Representation Learning (ICLR), 2025. Ian Waudby-Smith and Aaditya Ramdas. Estimating means of bounded random variables by betting. Journal of the Royal Statistical Society Series B: Statistical Methodology, 86(1):1–27, 2024. Zichun Xu, Daniela Witten, and Ali Shojaie. A unified framework for semiparametrically efficient semi-supervised learning. arXiv preprint arXiv:2502.17741, 2025. Tijana Zrnic. A note on the prediction-powered bootstrap. arXiv e-prints, arXiv:2405.18379, 2024. URL https://arxiv.org/abs/2405.18379. Tijana Zrnic and Emmanuel Candès. Cross-prediction-powered inference. Proceedings of the National Academy of Sciences, 120(41):e2322083121, 2023. Tijana Zrnic and Emmanuel Candes. Active statistical inference. In International Conference on Machine Learning, pp. 62993–63010. PMLR, 2024.

Published as a conference paper at ICLR 2026

E XPERIMENTS ON THE E FFECT OF THE M IXING PARAMETER

In this section, we report the results of experiments on tuning the mixing constant in the mixture policy of Zrnic & Candes (2024), evaluated across four different datasets. A detailed description of these datasets is provided in Section 6 and Appendix E. 0.07

[ZC24] (mixing=0.05) [ZC24] (mixing=0.1) [ZC24] (mixing=0.5) [ZC24] (mixing=0.8) [ZC24] (mixing=1.0)

0.04 0.03 0.02

1855

2370

3029

3871

Estimator

[ZC24] (mixing=0.05) [ZC24] (mixing=0.1) [ZC24] (mixing=0.5) [ZC24] (mixing=0.8) [ZC24] (mixing=1.0)

0.86

Interval width

0.05

Interval width

1.27

Estimator

0.58 0.39 0.26

4946

819

(a) Post-election survey dataset. 0.62

613

783

1000

1278

Interval width

1709

2184

Estimator

[ZC24] (mixing=0.05) [ZC24] (mixing=0.1) [ZC24] (mixing=0.5) [ZC24] (mixing=0.8) [ZC24] (mixing=1.0)

0.25

0.24 0.18

0.42

[ZC24] (mixing=0.05) [ZC24] (mixing=0.1) [ZC24] (mixing=0.5) [ZC24] (mixing=0.8) [ZC24] (mixing=1.0)

0.33

1337

(b) Politeness score dataset.

Estimator

0.46

1046

1634

0.15 0.09 0.05

146

187

240

306

391

(d) Synthetic dataset.

Figure 5: Interval width vs. the sampling budget parameter Tb for different values of the mixing parameter of the query probability scheme in Zrnic & Candes (2024). Averaged over 50 repeated runs.

E XTENDED R ELATED W ORK

Published as a conference paper at ICLR 2026

augmented inverse probability weighting (AIPW) estimator and propose an extension, which allows utilizing predictions from multiple foundation models. To address cases where the model accuracy varies across subdomains, Fisch et al. (2024) apply a stratification approach to PPI. Zrnic (2024) explore a bootstrap-based PPI variation to tackle arbitrary estimation problems. Xu et al. (2025) improve the PPI framework by proposing a safe PPI estimator that is always more efficient than the initial supervised estimator and can be used for arbitrary inferential problems. Li et al. (2025) generalize the ideas of PPI to a dynamic performative setting and show improved confidence regions in the task of performative prediction. In a semi-supervised context, Zrnic & Candès (2023) propose a method of using the labeled datapoints for cross-fitting and using the fitted models to compute the desired estimator. Cortinovis & Caron (2025) extend PPI by applying a Bayes-assisted framework that uses prior knowledge on the accuracy of the model predictions. In the case of compound estimation settings, Li & Ignatiadis (2025) adopt an approach that combines PPI with empirical Bayes shrinkage to correct noisy predictions within each problem and subsequently uses these as a shrinkage target. An interesting work by Csillag et al. (2025) presents a PPI framework based on e-values. Other applications of the PPI framework include LLM-assisted rank-set construction (Chatzi et al., 2024), average treatment effects from multiple datasets (Wang et al., 2025), clinic trial outcomes (Poulet et al., 2025), evaluating the accuracy of machine learning systems (Boyeau et al., 2025; Park et al., 2025), machine learning generated surrogate rewards for multi-armed bandits (Ji et al., 2025b). A few other works have explored alternative machine-learning assisted estimators, e.g. Schmutz et al. (2023); Egami et al. (2023); Miao et al. (2023); Miao & Lu (2024); Gan et al. (2024). Active Learning. Similar to the Active Statistical Inference protocol is active learning (Settles, 2009; Dasgupta, 2011; Hanneke, 2014), which frames learning as a process in which a machine learning model selectively queries unlabeled instances to be labeled by an oracle. In contrast to Active Statistical Inference, which focuses on enhancing statistical inference, the goal of active learning is to improve the predictive power of the machine learning model through the strategic use of labeled data. One of the main approaches in active learning, and the one most closely aligned with active estimation, is the uncertainty sampling strategy (Schohn & Cohn, 2000; Tong & Koller, 2000; Tur et al., 2005; Joshi et al., 2009; Gal et al., 2017; Ducoffe & Precioso, 2018; Beluch et al., 2018; Ren et al., 2021), where the model aims to query the labels of the most informative data points, i.e., the ones which the model is most uncertain about. Importance Sampling. The idea of prioritizing the most influencial samples is also closely related to adaptive importance sampling (Owen, 2013), which is a sequential scheme that updates the proposal distribution by learning from previously sampled values in order to better approximate some property of a target distribution. Active mean estimation is analogous to adaptive importance sampling, in that it adaptively selects samples that contribute most to reducing the variance of the estimator based on previously observed data to improve the accuracy of the mean estimator. Non-Asymptotic Results in Zrnic & Candes (2024). We acknowledge that in Appendix C in Zrnic & Candes (2024), the authors consider incorporating the notion of actively querying the ground truth into the technique for estimating means of bounded random variables proposed by Waudby-Smith & Ramdas (2024). Waudby-Smith & Ramdas (2024) leverage the duality between sequential hypothesis testing and the construction of confidence intervals. More concretely, their method reduces the task of constructing a confidence interval for the mean to a potentially infinite number of hypothesis testing problems. Each hypothesis testing problem corresponds to whether the observed samples have a population mean equal to a specific value. Hence, for a continuous random variable, this corresponds to an infinite number of hypotheses. In practice, a discretization is used. The confidence interval Ct at time t then consists of those hypothesized mean values that have not been rejected based on the data observed up to time t, i.e., (ν) (ν) Ct := {ν : H0 is not rejected based on observations up to time t}, where H0 denotes the hypothesis that the population mean is ν. While Zrnic & Candes (2024) provide the valuable idea of integrating these techniques and also provide some simulation results, the specific step-by-step algorithmic details and theoretical guarantees for active sequential mean estimation remain to be explicitly elaborated.

Published as a conference paper at ICLR 2026

P ROOFS OF THE THEORETICAL RESULTS IN S ECTION 4

Theorem 1. Fix a time horizon T ≥ 4. Assume each random variable gt is bounded, i.e., |gt | ≤ G for a constant G > 0. Denote σt2 := E (gt − µy )2 |Ft−1 the conditional variance, where Ft−1 is the filtration up to t − 1. Then, for any δ ∈ (0, 1/e), with probability at least 1 − δ, ∀t ∈ [T ] : r r √ log(T ) log(T ) log 2 max 2 St , (G + |µy |) log δ δ t + 1− |µy | , |wt+1 − µy | ≤ T T Pt where St = s=1 σs2 . Proof. The difference of wt − µy can be decomposed into two terms. Specifically, we have ! t t t 1X 1X wt+1 − µy = gs − µy = (gs − µy ) − 1 − µy . T s=1 T s=1 T

(7)

Pt Let us analyze the second-to-last-term s=1 (gs − µy ) on (7). We note that (gs − µy )s≥1 forms a martingale difference sequence, i.e., E[gs − µy | Fs−1 ] = 0, where Fs−1 encodes all information up to time s − 1. Furthermore, ∀s : |gs − µy | ≤ G + |µy |. Also, the conditional variance is Var (gs − µy |Fs−1 ) = E (gs − µy )2 |Fs−1 = σs2 By Freedman’s inequality (Lemma 1), we have, with probability 1 − δ,   v t t p  u uX X p σs2 , (G + |µy |) log(log(T )/δ) log(log(T )/δ). (gs − µy ) ≤ 2 max 2t ∀t ∈ [T ] :   s=1

s=1

(8) Combining (7) and (8), we obtain the following holds simultaneously at all t ∈ [T ], with probability at least 1 − δ: |wt+1 − µy | q p p Pt 2 , (G + |µ |) log(log(T )/δ) 2 max 2 σ log(log(T )/δ) y s=1 s t + 1− ≤ |µy | . T T

P ROOFS OF THE THEORETICAL RESULTS IN S ECTION 5

Lemma 2. The conditional variance has the following decomposition: E (gt − µy )2 |Ft−1 " # " # " # 1 2 2 Ft−1 + 2E ft (xt )(yt − ft (xt )) Ft−1 − µ2y . = E ft (xt ) Ft−1 + E (yt − ft (xt )) πt (xt ) Furthermore, assume that the query policy at time t is Ft−1 -measurable, i.e., there exists a random variable pt ∈ [0, 1], measurable with respect to Ft−1 , such that πt (xt ) = pt . Then, we have # " # " 1 1 2 2 Ft−1 = E (yt − ft (xt )) Ft−1 . E (yt − ft (xt )) πt (xt ) pt 16

Published as a conference paper at ICLR 2026

Proof. E (gt − µy )2 |Ft−1 = E gt2 |Ft−1 − µ2y # " = E ft (xt ) Ft−1 − µ2y "

" # # ξt ξt2 Ft−1 + 2E ft (xt )(yt − ft (xt )) Ft−1 + E (yt − ft (xt )) 2 πt (xt ) πt (xt ) "

# 2

= E ft (xt ) Ft−1

# " # 1 + E (yt − ft (xt )) Ft−1 + 2E ft (xt )(yt − ft (xt )) Ft−1 − µ2y , πt (xt ) 2

where the first equality follows from that E [gt |Ft−1 ] = µy . Lemma 5. Assume that the range of oracle’s output is bounded, i.e., ∀t : Φ(xt ) ≤ B, for a constant 2 ˙ 2 B > 0. Then, ∀t : ℓ̃t ≤ B β4 . Proof. Φ2 (xt ) B2 B2 ˙ 2 ℓ̃t = t 4 ≤ 4 ≤ 4 , pt pt β where the first inequality follows from that ∀t : Φ(xt ) ≤ B, and the last inequality uses that ∀t : pt ≥ β. ∀t :

Theorem 2. Assume that there is an oracle that outputs Φt (xt ) at each t such that c11 Φt (xt ) ≤ # " E (yt − ft (xt ))

Ft−1 ≤ c0 Φt (xt ) for some constant c0 , c1 > 0 and that ∀t : Φ(xt ) ≤ B. Set 2

the parameter γ = √1T βB . Using the query policy (4), we have that, with probability at least 1 − δ, ∀t ∈ [T ]: r r √ ) ) 2 max 2 Ψt , (G + |µy |) log log(T log log(T δ δ t |wt+1 − µy | ≤ + 1− |µy | , T T √ c (R(p∗ 1:t )−minp∈K R(p)) T B . 2 β

∗2 for any β ∈ (0, τ ) and τ ∈ (0, 1), where Ψt ≤ c0 c1 σ1:t + 2c0 √tT βB2 + 0

Proof. By Lemma 2 and the constraint that the query probability pt is fully determined in Ft−1 , we have " # " # " # 1 2 2 2 σt = E ft (xt ) Ft−1 + E (yt − ft (xt )) Ft−1 + 2E ft (xt )(yt − ft (xt )) Ft−1 − µ2y pt " " # # Φt (xt ) 2 ≤ E ft (xt ) Ft−1 + c0 + 2E ft (xt )(yt − ft (xt )) Ft−1 − µ2y pt " # " # Φt (xt ) Φt (xt ) Φt (xt ) 2 = E ft (xt ) Ft−1 + c0 + − ∗ + 2E ft (xt )(yt − ft (xt )) Ft−1 p∗1:t pt p1:t − µ2y "

# 2

≤ E ft (xt ) Ft−1 "

" # c0 c1 Φt (xt ) Φt (xt ) 2 + ∗ E (yt − ft (xt )) Ft−1 + c0 − ∗ p1:t pt p1:t #

+ 2E ft (xt )(yt − ft (xt )) Ft−1 − µ2y ∗2 ≤ c0 c1 σt,(t) + c0

Φt (xt ) Φt (xt ) − ∗ pt p1:t

Published as a conference paper at ICLR 2026

where the last inequality uses the fact that c0 c1 ≥ 1. We note that the above inequality holds for all t. Hence, we have t X ∗2 σs2 ≤ c0 c1 σ1:t + c0 Regrett (p∗1:t ), (9) s=1

by summing up the above inequality for each round. To proceed, we use the regret bound that we have from Lemma 4: Regrett (p∗1:t ) ≤ 2γ

t ∗ X ˙ 2 R(p1:t ) − minp∈K R(p) ℓ˜s + γ s=1

(i)

≤ 2γt

R(p∗1:t ) − minp∈K R(p) B2 + 4 β γ

√ t B (R(p∗1:t ) − minp∈K R(p)) T B = 2√ + , β2 T β2

(ii)

(10)

where (i) is from Lemma 5 and (ii) is by the choice of γ = √1T βB . Combining (9) and (10), we have t X

√ B c0 (R(p∗1:t ) − minp∈K R(p)) T B + . β2 T β2

t ∗2 σs2 ≤ c0 c1 σ1:t + 2c0 √

s=1

Using the above bound together with Theorem 1 leads to the result. This completes the proof.

A DDITIONAL E XPERIMENTAL D ETAILS

E.1

S YNTHETIC DATASET

The fourth dataset used in the experiments is a synthetic dataset that is generated for binary classification according to a logistic model. More specifically, the covariates xt ∈ Rd are independently drawn from a multivariate normal distribution with zero mean and identity covariance Id , where d = 10. The true parameter vector w∗ is sampled independently from a normal distribution ∗ with zero mean and covariance 0.5 · Id . Gaussian noise ϵt ∼ N (0, 10−5 ) is added to each x⊤ t w to produce the logits. The correspondig binary labels yt ∈ {0, 1} are then generated according to ∗ −z ) denotes the sigmoid function. The ML yt ∼ Bernoulli σ x⊤ t w + ϵt , where σ(z) = 1/(1+e model ft (·) is implemented as a logistic regression model whose uncertainty predictor is estimated in the same way as in the post-election survey dataset, i.e., ut (xt , ft (·)) = 2 min{ft (xt ), 1−ft (xt )} using the predicted probabilities of ft (·). A linear regression model is trained to predict the approximation oracle Φ(xt ) as in the previous tasks.

0.35

0.40

0.45 0.50 confidence width

0.55

0.14 0.11 0.09 0.08 0.06

1.0

coverage

interval width

Figure 6 shows the experimental results on the synthetic dataset.

146

187

240

306

391

0.9 0.8

FTRL [ZC24] uniform sampling

0.7 0.6 147

208

269

330

392

Figure 6: Synthetic dataset. Left: Intervals of randomly selected trials. Middle: Average confidence width across repeated trials vs. sampling budget Tb . Right: Percentage of trials that cover the true mean.

E.2

E XPERIMENTAL S ETUP

All experiments were repeated over 50 trials, and reported results correspond to the averages across these trials. At the start of each trial, the data points were randomly permuted. For each experiment, 18

Published as a conference paper at ICLR 2026

the budget Tb was varied over five uniformly spaced values between 15% and 40% of the total number of data points T . The interval width and coverage plots were obtained by linearly interpolating between the values at these grid points. In the experimental setup, the ML model ft (·), uncertainty estimator ut (·, ·), and oracle Φt (·) were updated periodically after observing a batch of B data points. For the first two datasets (politeness score and wine review analysis), the estimators were updated N = 50 times, while for the last two datasets (post-election survey and synthetic data), they were updated N = 10 times. Accordingly, the batch size was set to B = round TNb . For the FTRL plicy, we set the upper bound hyperparameter to τ = TTb in accordance with our theoretical analysis to ensure that the query probability satisfies the sampling constraint. The lower bound hyperparameter was set to β = τ8 > 0, to prevent the sampling probability from becoming too small, and thereby encouraging exploration, while still remaining sufficiently below τ so that the resulting sampling interval is non-trivial and allows the algorithm to adjust the sampling probability over time. Furthermore, the hyperparameter γ was chosen as γ = √1T , in line with common practice in online learning, to guarantee sublinear regret growth with respect to T , which is necessary for achieving no-regret performance. For the policy of Zrnic & Candes (2024), we set the mixing hyperparameter to λ = 0.5, which is the recommended value used in their experimental setup, to enable a comparison with their proposed policy.

Record · ID 120498 · SHA-256 cb6525fa2efb60ae
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.