Introduction
Estimating a population mean—such as disease prevalence, the proportion of households below the poverty line, or the fraction of files containing malware—is fundamental across scientific and policy applications. However, collecting ground-truth outcomes can be prohibitively expensive, often requiring human expert annotation, specialized testing, or additional surveys. In many modern settings, however, covariates and machine learning (ML) predictions are readily available for the entire population , even when ground-truth outcomes can only be obtained for a small subset. How can we fully leverage this information to decide which outcomes to collect and efficiently estimate a population mean, with valid confidence intervals?
As a concrete example, consider a policymaker seeking to estimate the proportion of households living below the poverty line following a major economic disruption. Suppose demographic information is available for many households, but determining their current economic circumstances requires costly surveys. An ML model trained on historical data could predict each household’s probability of poverty, although its predictions may be imperfect, particularly under changing economic conditions. Given a limited survey budget, the policymaker could survey households uniformly at random, obtaining a statistically valid sample mean but potentially leaving efficiency gains from ML predictions untapped. Alternatively, they could preferentially survey households whose poverty status the model is most uncertain about, update the model as new responses arrive, and adapt subsequent sampling accordingly. However, simply averaging the adaptively collected responses can introduce selection bias, while relying on ML predictions alone risks bias from prediction errors.
The challenge, therefore, is to leverage the full covariate pool and progressively acquired responses to construct efficient estimators and confidence intervals under adaptive, nonuniform sampling.
Problem setup Formally, suppose we observe covariates x 1 , … , x N x_1,\ldots,x_N x 1 , … , x N with corresponding unobserved responses y 1 , … , y N y_1,\ldots,y_N y 1 , … , y N , each of which may be collected at a (potentially substantial) cost. Given a labeling budget n ≪ N n \ll N n ≪ N , we seek to sequentially label data points, so as to construct an estimator and confidence interval, by leveraging, at each timestep, the full covariate pool, previously observed responses, and a black-box ML model that can be updated as new responses arrive. Specifically, we aim to use ML predictions both to adaptively select which responses to collect and to improve the resulting estimator through regression adjustment. Our primary goal is to construct an efficient estimator and statistically valid confidence interval for the finite-population mean
θ : = 1 N ∑ i = 1 N y i , (1) \theta:= \frac{1}{N}\sum_{i=1}^{N} y_i, \tag*{(1)} θ := N 1 i = 1 ∑ N y i , (1)
treating the population as fixed and the sampling process alone as random. We also consider inference for the superpopulation mean E [ Y ] \mathbb{E}[Y] E [ Y ] when the ( x i , y i ) (x_i,y_i) ( x i , y i ) are assumed to have been drawn i.i.d. from an underlying distribution.
Positioning A natural starting point for the above problem is Active Statistical Inference (ASI) (Zrnic & Candès, 2024), which leverages ML predictions to guide label acquisition and construct statistically valid estimators and confidence intervals. In its sequential formulation (SAI), observations are processed in a fixed, predetermined order, with the ML model potentially updated as labels are acquired. Crucially, at round t t t , SAI can only make a Bernoulli decision to either acquire or skip the response y t y_t y t associated with the current observation x t x_t x t . Once an observation is skipped, its response cannot be acquired later. When the full covariate pool is available in advance, however, why restrict each round to a label-skip decision about the current observation, rather than proactively selecting which observation to label next from the entire remaining pool?
Motivated by this question, our earlier work [27 ] introduced Pro-Active Inference (PAI) in the context of LLM evaluation, combining proactive acquisition with online-updated ML predictions and regression adjustment. However, this initial formulation sampled with replacement, potentially revisiting previously labeled observations and wasting sampling opportunities. Extending PAI to sampling without replacement, however, requires more than modifying the acquisition policy: the estimator and its underlying martingale-based analysis must also be reformulated, as naive modifications can violate conditional unbiasedness and lead to severe confidence-interval miscoverage.
Our contributions In the present work, we therefore develop a general, without-replacement formulation of PAI, together with a reformulated estimator and corresponding martingale-based inferential guarantees. We establish its finite-sample unbiasedness and asymptotic validity, develop an improved finite-sample variance estimator, and extend PAI to superpopulation inference without requiring Bonferroni corrections or α \alpha α -splitting. Theoretically, we characterize PAI’s potential efficiency gains over Batch Active Inference (BAI) in a quasi-oracle setting, highlighting the role of prediction-residual imbalance. Empirically, through experiments across eight diverse testbeds, we investigate PAI’s statistical efficiency and confidence-interval coverage relative to existing methods. Beyond comparing performance, we develop interpretable diagnostics of residual imbalance, the relative difficulty of direct versus prediction-adjusted estimation, and the quality of online ML updates, together with targeted ablations, to understand when and why PAI gains or loses efficiency, and, more broadly, when ML-assisted statistical inference is beneficial.1
Towards the completion of this manuscript, we also became aware of the closely related works of Ashouritaklimi et al. [4 ] ; Hamilton et al. [15 ] , which develop alternative approaches to adaptive sampling without replacement. While these approaches share important methodological features with PAI, they differ in their estimator constructions and uses of ML predictions. We discuss these and other related approaches in § 2 and empirically compare PAI with the former in § 6 .
Related work
Prediction-powered inference A natural starting point for estimating a population mean is uniform sampling, which yields statistically valid inference without involving an ML model, but may leave substantial efficiency gains from available ML predictions untapped. Prediction-Powered Inference (PPI; Angelopoulos et al. [1 ] ) leverages ML predictions to impute unobserved outcomes and corrects the resulting estimation error using a smaller sample of observed labels. Subsequent extensions include PPI++ (Angelopoulos et al., [3 ] ), which adapts the strength of the prediction-based adjustment to improve statistical efficiency, and cross-PPI (Zrnic & Candès, 2024), which allows the available labeled data to be used for both training ML predictors and constructing inference through cross-fitting. While these approaches primarily consider nonadaptively acquired labels, PAI additionally uses ML predictions to guide which outcomes to acquire, potentially updating both its regression adjustment and acquisition policy as new labels are observed.
Active statistical inference Our work builds on the Active Statistical Inference (ASI) framework of Zrnic & Candès (2024), which leverages ML predictions to guide label acquisition while constructing statistically valid estimators and confidence intervals for statistical estimands. In its sequential formulation (Sequential Active Inference; SAI), observations arrive in a stream, with covariates modeled as i.i.d. draws from a superpopulation, and the method makes Bernoulli label-skip decisions according to a potentially updated ML-based acquisition policy, subject to a prespecified labeling budget. Once an observation is skipped, however, its label cannot be acquired later. When the full covariate pool is available in advance, PAI instead proactively selects which observation to label next from the remaining unlabeled pool, using the full covariate information and previously acquired labels to update its ML-based regression adjustment and acquisition policy. Related developments include optimized and robust acquisition policies for ASI (Ma & Candès, [20 ] ; Li et al., [19 ] ), as well as applications to human annotation and evaluation of LLM outputs (Gligorić et al., [13 ] ; Angelopoulos et al., [2 ] ).
In our earlier work ([27 ] ), we introduced a with-replacement formulation of PAI for LLM evaluation, using sampling policies and regression adjustments based on an online-updated working Bayesian factor model. However, this formulation allowed previously labeled observations to be sampled again, potentially wasting part of the labeling budget on repeated queries. The present work instead samples exclusively from the remaining unlabeled observations, ensuring that each query acquires a new label and that the full budget is spent on distinct observations, while developing the corresponding estimator and inferential guarantees. Finally, Tolochinsky et al. (2026) also consider sampling without replacement in the context of best-model identification for LLMs, but use uniform sampling rather than an adaptive, ML-guided acquisition policy.
Active testing and measurement PAI is also closely connected to a growing literature on efficient statistical inference in the presence of missing outcome data, particularly when labels are acquired adaptively. Most closely related is a line of work studying importance-weighted estimation under adaptive label acquisition [11 , 18 , 15 , 4 ] . With the exception of Hamilton et al. [15 ] , these works focus primarily on estimating the risk of a fixed ML model, but their core methods readily apply to our population mean estimation task outlined in § 1 . In particular, the active-testing literature [11 , 18 ] develops unbiased estimators under adaptive sampling without replacement.
Building on this literature, one of the methods most closely related to PAI is Active Measurement [15 ] , which studies the estimation of finite-population quantities, such as bird counts, rather than the prediction risk of a fixed ML model. AM uses online-updated ML predictions to guide acquisition and develops alternative weighting schemes and variance estimators for combining importance-weighted estimates. In particular, AM generalizes the estimation framework underlying Farquhar et al. [11 ] ’s LURE estimator by considering alternative schemes for aggregating conditionally unbiased per-round estimates. Indeed, at the level of the per-round estimator, AM coincides with PAI when our prediction-based regression adjustment is omitted. PAI instead incorporates online-updated ML predictions into both acquisition and regression adjustment, potentially improving sampling efficiency while preserving finite-sample unbiasedness.
Another closely related method is Prediction-Powered Active Testing [4 ] , which similarly builds on the active-testing literature, but additionally incorporates ML predictions directly into the estimator through a prediction-powered control variate. In all of their experiments, PPAT uses a fixed ML proxy for regression adjustment and a potentially updated surrogate model to guide acquisition, with a tunable control-variate coefficient. The authors further note that the control-variate proxy could also be updated as new labels are acquired, although they do not investigate this extension experimentally. In contrast to their experimental implementation, PAI directly incorporates online-updated ML predictions into its imputation and residual correction.
Like PAI, AM and PPAT construct their estimators by aggregating per-round importance-weighted estimates, which are conditionally unbiased under fixed tuning parameters. Under suitable regularity conditions, both approaches establish asymptotic Gaussian limiting distributions through martingale arguments, enabling the construction of asymptotically valid confidence intervals using corresponding variance estimators. However, PPAT aggregates its per-round estimates using nonuniform LURE-based weights [11 ] , whereas PAI weights them equally.
Among these closely related approaches, we focus our empirical comparisons on PPAT, since its use of ML predictions in both acquisition and regression-adjusted estimation makes it a particularly direct methodological comparator to PAI.
Pro-Active Inference methodology
We first describe PAI’s adaptive sampling procedure, then develop estimators and confidence intervals for finite-population means, before extending our methodology to superpopulation inference.
Sampling setup and notation
Let I = ( 1 , … , N ) \mathcal{I} = (1,\ldots,N) I = ( 1 , … , N ) index the finite population, and let O t − 1 ⊆ I O_{t-1} \subseteq\mathcal{I} O t − 1 ⊆ I denote the indices with observed responses before round t t t , with O 0 = ∅ O_0 = \varnothing O 0 = ∅ . Given a labeling budget n ≪ N n \ll N n ≪ N , at each round t = 1 , … , n t = 1,\ldots,n t = 1 , … , n , PAI constructs an acquisition distribution (or sampling policy q t q_t q t ) over the remaining unlabeled indices R t − 1 : = I ∖ O t − 1 R_{t-1}:=\mathcal{I}\setminus O_{t-1} R t − 1 := I ∖ O t − 1 , using the full covariate pool and all previously acquired responses. It then samples an index I t ∼ q t I_t\sim q_t I t ∼ q t , observes its response y I t y_{I_t} y I t , and updates O t : = O t − 1 ∪ { I t } O_t:=O_{t-1}\cup\{I_t\} O t := O t − 1 ∪ { I t } . We denote by f ^ ( t − 1 ) \hat{f}^{(t-1)} f ^ ( t − 1 ) the ML predictor available before round t t t , initialized at f ^ ( 0 ) \hat{f}^{(0)} f ^ ( 0 ) and potentially updated after each newly acquired response. Formally, let F t − 1 : = σ ( { I s , y I s } s = 1 t − 1 ) \mathcal{F}_{t-1}:=\sigma(\{I_s,y_{I_s}\}_{s=1}^{t-1}) F t − 1 := σ ({ I s , y I s } s = 1 t − 1 ) . We require f ^ ( t − 1 ) \hat{f}^{(t-1)} f ^ ( t − 1 ) and q t q_t q t to be F t − 1 \mathcal{F}_{t-1} F t − 1 -measurable: depending only on past queries/labels.
The sampling policy q t q_t q t may depend on both the full covariate pool and previously acquired labels, but not on the unobserved responses. A natural strategy is to assign higher sampling probabilities to observations where the ML predictor is most uncertain. For binary outcomes, writing p t ( x ) : = f ^ ( t − 1 ) ( x ) p_t(x):=\hat{f}^{(t-1)}(x) p t ( x ) := f ^ ( t − 1 ) ( x ) , common uncertainty scores include u t ( x ) = 2 min ( p t ( x ) , 1 − p t ( x ) ) u_t(x)=2\min(p_t(x),1-p_t(x)) u t ( x ) = 2 min ( p t ( x ) , 1 − p t ( x )) (Zrnic & Candès, 2024) and u t ( x ) = p t ( x ) ( 1 − p t ( x ) ) u_t(x)=\sqrt{p_t(x)(1-p_t(x))} u t ( x ) = p t ( x ) ( 1 − p t ( x )) , the latter motivated by Neyman allocation. Our experiments use the former, with uniform mixing to ensure positive sampling probabilities (§ 5 ), although our theoretical framework supports general adaptive sampling policies satisfying the regularity conditions below.
Pro-Active Inference estimator for finite-population estimands
After adaptively collecting n n n labels without replacement, we propose the following Pro-Active Inference (PAI) estimator of the finite-population mean:
θ ^ n : = 1 n ∑ t = 1 n ϕ t , ϕ t : = 1 N ( ∑ i ∈ O t − 1 y i + ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) + 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) . (2) \hat{\theta}_n:=\frac{1}{n}\sum_{t=1}^{n}\phi_t,\qquad
\phi_t:=\frac{1}{N}\left(\sum_{i\in O_{t-1}}y_i+\sum_{i\notin O_{t-1}}\hat{f}^{(t-1)}(x_i)\right)+\frac{1}{N}\frac{y_{I_t}-\hat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}. \tag*{(2)} θ ^ n := n 1 t = 1 ∑ n ϕ t , ϕ t := N 1 i ∈ O t − 1 ∑ y i + i ∈ / O t − 1 ∑ f ^ ( t − 1 ) ( x i ) + N 1 q t ( I t ) y I t − f ^ ( t − 1 ) ( x I t ) . (2)
Intuitively, the first term in ϕ t \phi_t ϕ t represents our current plug-in estimate of θ \theta θ —using observed labels where available and imputing ML predictions for the remaining unobserved labels—while the second term provides an importance-weighted bias correction for prediction errors. In Theorem 1, we show that θ ^ n \hat{\theta}_n θ ^ n is unbiased for θ \theta θ at every finite n n n and derive its asymptotic distribution using a martingale central limit theorem under mild regularity conditions.
Theorem 1. Consider a triangular array of problems (indexed by m m m ) such that n m ↑ ∞ n_m\uparrow\infty n m ↑ ∞ , N m ↑ ∞ N_m\uparrow\infty N m ↑ ∞ , and n m / N m → ρ ∈ [ 0 , 1 − ϵ ] n_m/N_m\to\rho\in[0,1-\epsilon] n m / N m → ρ ∈ [ 0 , 1 − ϵ ] for some ϵ > 0 \epsilon>0 ϵ > 0 .2 For each t t t , suppose that (a) f ^ ( t − 1 ) ( ⋅ ) \hat{f}^{(t-1)}(\cdot) f ^ ( t − 1 ) ( ⋅ ) and q t ( ⋅ ) q_t(\cdot) q t ( ⋅ ) are F t − 1 \mathcal{F}_{t-1} F t − 1 -measurable, and that (b) conditional on F t − 1 \mathcal{F}_{t-1} F t − 1 , q t ( ⋅ ) q_t(\cdot) q t ( ⋅ ) is a probability distribution on R t − 1 : = I ∖ O t − 1 R_{t-1}:=\mathcal{I}\setminus O_{t-1} R t − 1 := I ∖ O t − 1 with q t ( i ) ≥ τ / ∣ R t − 1 ∣ = τ / ( N − t + 1 ) q_t(i)\ge\tau/|R_{t-1}|=\tau/(N-t+1) q t ( i ) ≥ τ /∣ R t − 1 ∣ = τ / ( N − t + 1 ) for all i ∈ R t − 1 i\in R_{t-1} i ∈ R t − 1 , for some fixed τ ∈ ( 0 , 1 ] \tau\in(0,1] τ ∈ ( 0 , 1 ] .
Then, θ ^ n \hat{\theta}_n θ ^ n is unbiased for θ \theta θ at every finite n n n . Furthermore, under mild regularity conditions (variance stabilization, Lindeberg, and uniform fourth-moment control for weighted residuals; Assumptions 4–6 in Appendix § 9 .§ 1 ), θ ^ n \hat{\theta}_n θ ^ n obeys the following limiting distribution:
n ( θ ^ n − θ ) / σ ^ n → d N ( 0 , 1 ) . (3) \sqrt{n}\left(\hat{\theta}_n-\theta\right)/\hat{\sigma}_n\xrightarrow{d}\mathcal{N}(0,1). \tag*{(3)} n ( θ ^ n − θ ) / σ ^ n d N ( 0 , 1 ) . (3)
And, the variance estimator is given by the following, where θ ^ t − 1 : = 1 t − 1 ∑ s = 1 t − 1 ϕ s \hat{\theta}_{t-1}:=\frac{1}{t-1}\sum_{s=1}^{t-1}\phi_s θ ^ t − 1 := t − 1 1 ∑ s = 1 t − 1 ϕ s for t ≥ 2 t\ge2 t ≥ 2 :
σ ^ n 2 : = A ^ n − B ^ n (4) \hat{\sigma}_n^2:=\hat{A}_n-\hat{B}_n \tag*{(4)} σ ^ n 2 := A ^ n − B ^ n (4)
: = 1 n N 2 ∑ t = 1 n ( y I t − f ^ ( t − 1 ) ( x I t ) ) 2 q t ( I t ) 2 − 1 n N 2 ∑ t = 2 n ( N θ ^ t − 1 − ∑ i ∈ O t − 1 y i − ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) 2 . (5) :=\frac{1}{nN^2}\sum_{t=1}^{n}\frac{\left(y_{I_t}-\hat{f}^{(t-1)}(x_{I_t})\right)^2}{q_t(I_t)^2}
-\frac{1}{nN^2}\sum_{t=2}^{n}\left(N\hat{\theta}_{t-1}-\sum_{i\in O_{t-1}}y_i-\sum_{i\notin O_{t-1}}\hat{f}^{(t-1)}(x_i)\right)^2. \tag*{(5)} := n N 2 1 t = 1 ∑ n q t ( I t ) 2 ( y I t − f ^ ( t − 1 ) ( x I t ) ) 2 − n N 2 1 t = 2 ∑ n N θ ^ t − 1 − i ∈ O t − 1 ∑ y i − i ∈ / O t − 1 ∑ f ^ ( t − 1 ) ( x i ) 2 . (5)
Proof. Please see Appendix § 9 .§ 2 .
By Theorem 1, it follows that an asymptotic ( 1 − α ) (1-\alpha) ( 1 − α ) -level confidence interval for θ \theta θ is given by
[ θ ^ n ± z 1 − α / 2 ( σ ^ n / n ) ] . (6) \left[\hat{\theta}_n\pm z_{1-\alpha/2}\left(\hat{\sigma}_n/\sqrt{n}\right)\right]. \tag*{(6)} [ θ ^ n ± z 1 − α /2 ( σ ^ n / n ) ] . (6)
An improved finite-sample variance estimator
Although σ ^ n 2 : = A ^ n − B ^ n \hat{\sigma}_n^2 := \hat{A}_n-\hat{B}_n σ ^ n 2 := A ^ n − B ^ n is consistent for the limiting variance σ 2 \sigma^2 σ 2 governing the martingale CLT in Theorem 1 (see proof in Appendix § 9 .§ 2 ), empirically, it can occasionally underestimate variance at finite labeling budgets, yielding confidence intervals that are too narrow and coverage below the nominal 1 − α 1-\alpha 1 − α level.
Inspired by the higher-order bias-correction philosophy of the ABC and BCa bootstrap methods (c.f. Efron [10 ] ; Diciccio & Efron [8 ] ), we derive an additive correction to σ ^ n 2 \hat{\sigma}_n^2 σ ^ n 2 using a second-order Taylor expansion. Specifically, we examine the finite-sample error introduced by substituting θ ^ t − 1 \hat{\theta}_{t-1} θ ^ t − 1 for the unknown population mean θ \theta θ in our variance estimator (Equation (4) ). This motivates the following bias-corrected variance estimator σ ^ n , c o r 2 \hat{\sigma}_{n,\mathrm{cor}}^2 σ ^ n , cor 2 , where A ^ n \hat{A}_n A ^ n and B ^ n \hat{B}_n B ^ n are defined above in Theorem 1 :
σ ^ n , c o r 2 : = A ^ n − B ^ n + C ^ n , with C ^ n : = 1 n ∑ s = 1 n − 1 ( 1 N y I s − f ^ ( s − 1 ) ( x I s ) q s ( I s ) ) 2 w s and w s : = ∑ k = s n − 1 1 k 2 . \hat{\sigma}_{n,\mathrm{cor}}^2 := \hat{A}_n-\hat{B}_n+\hat{C}_n,\qquad\text{with }\hat{C}_n := \frac{1}{n}\sum_{s=1}^{n-1}\left(\frac{1}{N}\frac{y_{I_s}-\hat{f}^{(s-1)}(x_{I_s})}{q_s(I_s)}\right)^2w_s\quad\text{and}\quad w_s := \sum_{k=s}^{n-1}\frac{1}{k^2}. σ ^ n , cor 2 := A ^ n − B ^ n + C ^ n , with C ^ n := n 1 s = 1 ∑ n − 1 ( N 1 q s ( I s ) y I s − f ^ ( s − 1 ) ( x I s ) ) 2 w s and w s := k = s ∑ n − 1 k 2 1 .
Importantly, the correction C ^ n \hat{C}_n C ^ n is nonnegative and vanishes asymptotically, preserving the asymptotic normality guarantee of Theorem 1 . We provide the full derivation, proof of preserved asymptotic validity, and a characterization of when the correction reduces mean squared error in Appendix § 9 .§ 3 . We use the bias-corrected variance estimator σ ^ n , c o r 2 \hat{\sigma}_{n,\mathrm{cor}}^2 σ ^ n , cor 2 in all our experiments and recommend it as the default for practitioners.
Pro-Active Inference estimator for superpopulation estimands
In the preceding subsections, we focused on the finite-population mean θ : = N − 1 ∑ i = 1 N y i \theta:= N^{-1}\sum_{i=1}^{N}y_i θ := N − 1 ∑ i = 1 N y i as our estimand, treating { ( x i , y i ) } i = 1 N \{(x_i,y_i)\}_{i=1}^{N} {( x i , y i ) } i = 1 N as a fixed finite population.
However, oftentimes scientists may instead wish to adaptively sample from a finite population without replacement while making inference about the larger superpopulation from which the finite population was drawn. For example, following a natural disaster, policymakers may survey a subset of households from a representative sample of residents to assess their economic circumstances, while seeking to draw statistically principled conclusions about the broader population of affected households. In this subsection, we extend PAI to accommodate such superpopulation estimands.
Formally, we assume a superpopulation model with ( x i , y i ) ∼ i . i . d . F (x_i,y_i)\overset{\mathrm{i.i.d.}}{\sim}F ( x i , y i ) ∼ i.i.d. F , with mean θ : = E [ y i ] \theta:= \mathbb{E}[y_i] θ := E [ y i ] and variance τ 2 : = Var ( y i ) \tau^2 := \operatorname{Var}(y_i) τ 2 := Var ( y i ) . Our goal is to construct a confidence interval for the superpopulation mean θ \theta θ . For this subsection only, define θ N : = N − 1 ∑ i = 1 N y i \theta_N := N^{-1}\sum_{i=1}^{N}y_i θ N := N − 1 ∑ i = 1 N y i to be the size-N N N finite-population mean of y 1 , … , y N y_1,\ldots,y_N y 1 , … , y N , where the y i y_i y i are now treated as random variables.
Let θ ^ n \hat{\theta}_n θ ^ n be our PAI estimator for θ N \theta_N θ N from Equation (2) . The critical observation is that
n ( θ ^ n − θ ) = n ( θ ^ n − θ N ) ⏟ finite-population sampling error + n N N ( θ N − θ ) ⏟ superpopulation error . (7) \sqrt{n}\left(\hat{\theta}_n-\theta\right)=\underbrace{\sqrt{n}\left(\hat{\theta}_n-\theta_N\right)}_{\text{finite-population sampling error}}+\underbrace{\frac{\sqrt{n}}{\sqrt{N}}\sqrt{N}\left(\theta_N-\theta\right)}_{\text{superpopulation error}}. \tag*{(7)} n ( θ ^ n − θ ) = finite-population sampling error n ( θ ^ n − θ N ) + superpopulation error N n N ( θ N − θ ) . (7)
Intuitively, this decomposition separates the uncertainty from observing only a subset of the finite population from the additional uncertainty arising because the finite population itself is a sample from a larger superpopulation. Using this decomposition, we obtain the following limiting distribution.
Proposition 2. Retain the setup and assumptions of Theorem 1 , where σ 2 \sigma^2 σ 2 denotes the limiting variance governing PAI’s finite-population martingale CLT. Further suppose that ( x i , y i ) ∼ i . i . d . F (x_i,y_i)\overset{\mathrm{i.i.d.}}{\sim}F ( x i , y i ) ∼ i.i.d. F with mean θ : = E [ y i ] \theta:= \mathbb{E}[y_i] θ := E [ y i ] and variance τ 2 : = Var ( y i ) \tau^2 := \operatorname{Var}(y_i) τ 2 := Var ( y i ) . Then,
n ( θ ^ n − θ ) → d N ( 0 , σ 2 + ρ τ 2 ) , (8) \sqrt{n}\left(\hat{\theta}_n-\theta\right)\xrightarrow{d}\mathcal{N}\left(0,\sigma^2+\rho\tau^2\right), \tag*{(8)} n ( θ ^ n − θ ) d N ( 0 , σ 2 + ρ τ 2 ) , (8) where ρ : = lim n / N \rho:= \lim n/N ρ := lim n / N from Theorem 1 .
Proof. Please see Appendix § 9 .§ 4 .
By Proposition 2 and Slutsky’s Theorem, an asymptotically valid ( 1 − α ) (1-\alpha) ( 1 − α ) -confidence interval for the superpopulation mean θ \theta θ is
θ ^ n ± z 1 − α / 2 σ ^ n , c o r 2 + ( n / N ) τ ^ n 2 n , (9) \hat{\theta}_n \pm z_{1-\alpha/2}\sqrt{\frac{\hat{\sigma}_{n,\mathrm{cor}}^2+(n/N)\hat{\tau}_n^2}{n}}, \tag*{(9)} θ ^ n ± z 1 − α /2 n σ ^ n , cor 2 + ( n / N ) τ ^ n 2 , (9)
where σ ^ n , c o r 2 \hat{\sigma}_{n,\mathrm{cor}}^2 σ ^ n , cor 2 is our consistent bias-corrected variance estimator from Section 3.3, and τ ^ n 2 \hat{\tau}_n^2 τ ^ n 2 is any consistent estimator of τ 2 \tau^2 τ 2 . To estimate the superpopulation variance τ 2 = E [ y i 2 ] − θ 2 \tau^2 = \mathbb{E}[y_i^2] - \theta^2 τ 2 = E [ y i 2 ] − θ 2 , one simple approach is to apply PAI again to estimate the finite-population second moment θ N , 2 : = N − 1 ∑ i = 1 N y i 2 \theta_{N,2} := N^{-1}\sum_{i=1}^{N} y_i^2 θ N , 2 := N − 1 ∑ i = 1 N y i 2 , using the exact same queried indices I 1 , … , I n I_1,\ldots,I_n I 1 , … , I n used to construct θ ^ n \hat{\theta}_n θ ^ n . This procedure simply treats y i 2 y_i^2 y i 2 as the outcome, with corresponding ML predictions (e.g., g ^ ( t ) ( x i ) : = ( f ^ ( t ) ( x i ) ) 2 \hat{g}^{(t)}(x_i) := (\hat{f}^{(t)}(x_i))^2 g ^ ( t ) ( x i ) := ( f ^ ( t ) ( x i ) ) 2 ). Denoting the resulting PAI estimator by θ ^ n , 2 \hat{\theta}_{n,2} θ ^ n , 2 , we construct
τ ^ n 2 : = θ ^ n , 2 − θ ^ n 2 , (10) \hat{\tau}_n^2 := \hat{\theta}_{n,2} - \hat{\theta}_n^2, \tag*{(10)} τ ^ n 2 := θ ^ n , 2 − θ ^ n 2 , (10)
which is consistent for τ 2 \tau^2 τ 2 under the corresponding regularity conditions of Theorem 1 . Importantly, this procedure requires no additional labels , since observing y I t y_{I_t} y I t also reveals y I t 2 y_{I_t}^2 y I t 2 . For binary outcomes y i ∈ { 0 , 1 } y_i \in\{0,1\} y i ∈ { 0 , 1 } , we can alternatively use the even simpler τ ^ n 2 = θ ^ n ( 1 − θ ^ n ) \hat{\tau}_n^2 = \hat{\theta}_n(1-\hat{\theta}_n) τ ^ n 2 = θ ^ n ( 1 − θ ^ n ) , since y i 2 = y i y_i^2 = y_i y i 2 = y i .
Furthermore, we note that our superpopulation confidence interval avoids both Bonferroni corrections and α \alpha α -splitting by directly accounting for both finite-population sampling uncertainty and superpopulation variability in a single asymptotic distribution.
A theoretical characterization of PAI’s efficiency
Having established the PAI estimator and its inferential guarantees in Section 3, we now theoretically investigate when and why PAI can yield efficiency gains over active inference in the finite-population setting.
For our theoretical analysis, we consider a quasi-oracle setting where both PAI and Batch Active Inference (BAI), the batch variant of SAI, share the same fixed ML model f f f , with oracle-known prediction residuals e i : = y i − f ( x i ) e_i := y_i-f(x_i) e i := y i − f ( x i ) and absolute residuals r i : = ∣ e i ∣ r_i := |e_i| r i := ∣ e i ∣ .3 Recall that BAI estimates the finite-population mean using
θ ^ a c t i v e : = 1 N ∑ t = 1 N Γ t , Γ t = f ( x t ) + ( y t − f ( x t ) ) ξ t π t ( x t ) , (11) \hat{\theta}_{\mathrm{active}} := \frac{1}{N}\sum_{t=1}^{N}\Gamma_t,\qquad\Gamma_t = f(x_t) + (y_t-f(x_t))\frac{\xi_t}{\pi_t(x_t)}, \tag*{(11)} θ ^ active := N 1 t = 1 ∑ N Γ t , Γ t = f ( x t ) + ( y t − f ( x t )) π t ( x t ) ξ t , (11)
where π t ( x t ) \pi_t(x_t) π t ( x t ) is the probability of labeling observation t t t at time t t t and ξ t ∼ Bern ( π t ( x t ) ) \xi_t \sim\operatorname{Bern}(\pi_t(x_t)) ξ t ∼ Bern ( π t ( x t )) indicates whether its label was acquired. Following Zrnic & Candès (2024)’s recommended oracle sampling rule, we let both BAI and PAI sample proportionally to the true absolute prediction residuals:
B A I : π t ( x t ) ∝ r t ⟹ π t ( x t ) = n r t ∑ i = 1 N r i , P A I : q t ( i ) ∝ r i ⟹ q t ( i ) = r i ∑ k ∉ O t − 1 r k , (12) \mathrm{BAI:}\quad\pi_t(x_t) \propto r_t \quad\Longrightarrow\quad\pi_t(x_t)=\frac{n r_t}{\sum_{i=1}^{N}r_i},\qquad\mathrm{PAI:}\quad q_t(i)\propto r_i \quad\Longrightarrow\quad q_t(i)=\frac{r_i}{\sum_{k\notin O_{t-1}}r_k}, \tag*{(12)} BAI : π t ( x t ) ∝ r t ⟹ π t ( x t ) = ∑ i = 1 N r i n r t , PAI : q t ( i ) ∝ r i ⟹ q t ( i ) = ∑ k ∈ / O t − 1 r k r i , (12)
with the n n n present in BAI’s label-skip probability because we want the expected number of BAI queries to be n n n .4 By construction, PAI will achieve an exact budget of n n n labels.
We adopt this quasi-oracle comparison setting to isolate the efficiency differences between PAI and BAI, giving both methods access to the same fixed ML model and analogous oracle sampling policies based on the true absolute prediction residuals. Fixing the ML model and omitting uniform mixing and budget stabilization also makes our theoretical comparison analytically tractable.
Because both PAI and BAI are unbiased for θ \theta θ , to characterize their performance differences, it suffices to compare their variances. Let R t − 1 = I ∖ O t − 1 R_{t-1} = \mathcal{I} \setminus O_{t-1} R t − 1 = I ∖ O t − 1 represent the set of unlabeled indices after PAI sampling round t − 1 t-1 t − 1 , where I = [ 1 : N ] \mathcal{I}=[1:N] I = [ 1 : N ] is our full set of indices. Furthermore, for any set of indices R ⊆ I R\subseteq\mathcal{I} R ⊆ I , define the sums of unsigned and signed residuals U ( R ) U(R) U ( R ) and S ( R ) S(R) S ( R ) , respectively:
U ( R ) : = ∑ i ∈ R r i , S ( R ) : = ∑ i ∈ R e i . (13) U(R):=\sum_{i\in R}r_i,\qquad S(R):=\sum_{i\in R}e_i. \tag*{(13)} U ( R ) := i ∈ R ∑ r i , S ( R ) := i ∈ R ∑ e i . (13)
Finally, define b t b_t b t to be the net signed direction of the residual mass before PAI sampling round t t t , and define b ˉ 2 \bar{b}^2 b ˉ 2 to be the weighted-average squared net signed direction of the residual mass over the n n n PAI sampling rounds:
b t : = S ( R t − 1 ) U ( R t − 1 ) = ∑ i ∈ R t − 1 ( y i − f ( x i ) ) ∑ i ∈ R t − 1 ∣ y i − f ( x i ) ∣ , b ˉ 2 : = ∑ t = 1 n E [ U ( R t − 1 ) 2 b t 2 ] ∑ t = 1 n E [ U ( R t − 1 ) 2 ] ∈ [ 0 , 1 ] . (14) b_t:=\frac{S(R_{t-1})}{U(R_{t-1})}=\frac{\sum_{i\in R_{t-1}}(y_i-f(x_i))}{\sum_{i\in R_{t-1}}|y_i-f(x_i)|},\qquad
\bar{b}^2:=\frac{\sum_{t=1}^{n}\mathbb{E}\left[U(R_{t-1})^2b_t^2\right]}{\sum_{t=1}^{n}\mathbb{E}\left[U(R_{t-1})^2\right]}\in[0,1]. \tag*{(14)} b t := U ( R t − 1 ) S ( R t − 1 ) = ∑ i ∈ R t − 1 ∣ y i − f ( x i ) ∣ ∑ i ∈ R t − 1 ( y i − f ( x i )) , b ˉ 2 := ∑ t = 1 n E [ U ( R t − 1 ) 2 ] ∑ t = 1 n E [ U ( R t − 1 ) 2 b t 2 ] ∈ [ 0 , 1 ] . (14)
Under the above setup, we obtain a theoretical characterization of PAI’s sampling efficiency over BAI.
Theorem 3. Under the quasi-oracle setting above, assuming the below relative variance ratio is well-defined, we have
Var ( θ ^ a c t i v e ) Var ( θ ^ P A I ) = 1 1 − b ˉ 2 ⋅ 1 1 + η n , (15) \frac{\operatorname{Var}(\hat{\theta}_{active})}{\operatorname{Var}(\hat{\theta}_{PAI})}
=
\frac{1}{1-\bar{b}^2}\cdot\frac{1}{1+\eta_n}, \tag*{(15)} Var ( θ ^ P A I ) Var ( θ ^ a c t i v e ) = 1 − b ˉ 2 1 ⋅ 1 + η n 1 , (15) where η n ≥ 0 \eta_n\geq0 η n ≥ 0 is a remainder term capturing additional finite-budget and residual-magnitude effects (see Appendix § 9 .§ 5 for the full derivation). Furthermore, if n r max / U ( R 0 ) → 0 nr_{\max}/U(R_0)\to0 n r m a x / U ( R 0 ) → 0 , with r max = max i ∈ [ 1 : N ] r i r_{\max}=\max_{i\in[1:N]}r_i r m a x = max i ∈ [ 1 : N ] r i , then η n → 0 \eta_n\to0 η n → 0 , yielding
Var ( θ ^ a c t i v e ) Var ( θ ^ P A I ) = 1 + o ( 1 ) 1 − b ˉ 2 . \frac{\operatorname{Var}(\hat{\theta}_{active})}{\operatorname{Var}(\hat{\theta}_{PAI})}
=
\frac{1+o(1)}{1-\bar{b}^2}. Var ( θ ^ P A I ) Var ( θ ^ a c t i v e ) = 1 − b ˉ 2 1 + o ( 1 ) .
Proof. Please see Appendix § 9 .§ 5 .
In context, Theorem 3 suggests that PAI can substantially outperform BAI when (i) the ML model’s prediction residuals systematically point in the same direction, rather than canceling each other out (i.e., when b ˉ 2 \bar{b}^2 b ˉ 2 is large); and (ii) the sampling policy effectively prioritizes observations with large absolute prediction residuals (as in our quasi-oracle setting). We do emphasize that such prediction residual imbalance is not a measure of predictive accuracy: a highly accurate model can still have a large b ˉ 2 \bar{b}^2 b ˉ 2 if its small residuals consistently point in one direction. Alternatively, a large b ˉ 2 \bar{b}^2 b ˉ 2 could arise when the ML model predicts most observations accurately, but exhibits a systematic bias on a small subgroup of the population.
In § 6 , we will investigate whether this theoretical insight empirically carries over to more realistic settings with learned acquisition policies and online ML updates.
Experimental setup
Our empirical experiments seek to characterize PAI’s sampling efficiency and statistical coverage relative to its intellectual predecessor Sequential Active Inference (SAI) (Zrnic & Candès, 2024), the closely related contemporary method Prediction-Powered Active Testing (PPAT) [4 ] , and the simpler baselines Prediction-Powered Inference (PPI) [1 ] and uniform sampling. We evaluate these methods across eight real-world datasets spanning computational biology, LLM evaluations, economics, fraud detection, and cybersecurity.
We focus on finite-population mean estimation with binary outcomes y i ∈ { 0 , 1 } y_i\in\{0,1\} y i ∈ { 0 , 1 } . The finite-population setting allows us to directly evaluate statistical coverage against the known population mean, whereas the superpopulation mean is generally unknown for our testbeds. Focusing on binary outcomes also provides simple, well-established uncertainty scores for guiding acquisition (e.g., u t ( x ) = 2 min ( f ( x ) , 1 − f ( x ) ) u_t(x)=2\min(f(x),1-f(x)) u t ( x ) = 2 min ( f ( x ) , 1 − f ( x )) , where f f f is a probabilistic ML predictor; see Zrnic & Candès (2024, Section 4), avoiding additional modeling5 and acquisition-policy choices that arise in regression settings and could complicate the interpretation of performance differences. We emphasize that none of these methods are restricted to binary outcomes.
Importantly, to isolate differences between the inferential methods, we use the same underlying ML model and initialization across PAI, SAI, PPI, and PPAT, as well as the same online learning procedure wherever applicable. We also use the same underlying uncertainty scores and uniform-mixing parameter for PAI and SAI, following the recommendations of Zrnic & Candès (2024), while respecting PPAT’s own estimator and recommended acquisition mechanisms. Rather than engaging in extensive dataset-specific hyperparameter tuning, our goal is to understand how effectively these methods leverage the same underlying predictive information for statistical inference.
Datasets and ML models
All dataset processing routines can be found in the data_processing notebook in our Github repository.
ACS We use the ACSIncome task [9 ] , where the binary outcome indicates whether an individual’s annual income exceeds $50, 000, using demographic covariates. Adapting their distribution-shift setting, we train the initial ML model on California and evaluate on Puerto Rico, motivated by the importance of label-efficient data collection in resource-constrained settings, such as following natural disasters. Our test population consists of 9, 071 individuals with 11 covariates.
AlphaFold We use the protein-disorder dataset from Angelopoulos et al. [1 ] , originally derived from Bludau et al. [6 ] . Each observation corresponds to an amino-acid residue, with a binary outcome indicating whether it belongs to an intrinsically disordered region. We estimate the proportion of disordered residues among 10, 802 observations, using probabilistic ML predictions obtained from a logistic regression model fitted to AlphaFold-derived structural features. Since this dataset provides only the predictions and labels, without the underlying covariates, all ML-assisted methods use fixed predictions without online updates. For SAI, this corresponds to the Batch Active Inference (BAI) setting.
LLM evaluations We study estimation of LLM accuracy on two benchmark suites: MMLU-Pro [26 ] , containing 12, 032 questions, and a composite of BBH, GPQA, IFEval, MATH, and MuSR [22 , 30 , 16 , 23 ] (Suzgun et al. 2023), containing 9, 574 questions. Following Wu et al. [27 ] , we use their train/test splits and 64-dimensional question and model factors fitted to historical evaluation data from Fourrier et al. [12 ] ; ); Myrzakhan et al. [21 ] , with approximately 2.2K held-out LLMs per suite. For each held-out LLM, we fix the historical question factors and initialize its model factor at the empirical mean of historical model factors, using their empirical marginal variances to initialize the diagonal curvature for online logistic regression updates. These testbeds also allow us to directly assess the sampling efficiency of our without-replacement PAI estimator against its with-replacement predecessor from Wu et al. [27 ] .
BODMAS We use the BODMAS malware detection dataset [29 ] , where each observation represents a software sample with a binary label indicating whether it is malicious or benign. We employ a chronological 50/50 train-test split, fitting the initial ML model on the earlier observations and performing inference on the later 67, 218 observations. After removing features that are identically zero in the training split, each observation has 2, 330 covariates.
HIV We use the HIV molecular activity dataset from MoleculeNet [28 ] , accessed through DeepChem. Each observation represents a chemical compound screened for its ability to inhibit HIV replication, with confirmed or moderately active compounds labeled as positive and inactive compounds labeled as negative. We represent compounds using ECFP molecular fingerprints and employ a 50/50 train-test split, yielding a test population of 20, 560 compounds with 1, 025 covariates.
Pew We use Wave 168 of the Pew Research Center’s American Trends Panel, which surveys U.S. adults about online scams and related topics. Our binary outcome indicates whether a respondent reports having ever lost money because of an online scam or attack. We use demographic covariates and responses to other scam-related survey questions and employ a 50/50 train-test split, yielding a test population of 4,273 respondents with 53 covariates.
ULB We use the ULB Credit Card Fraud Detection dataset (Dal Pozzolo et al. [7 ] ), containing anonymized credit card transactions from European cardholders, with a binary outcome indicating whether a transaction is fraudulent. The covariates comprise 28 PCA-transformed features, transaction time, and amount. We employ a 50/50 train-test split, yielding a test population of 142,404 transactions with 30 covariates. This highly imbalanced dataset, with approximately 0.17% fraudulent transactions, allows us to investigate statistical inference for rare events.
ML models and online updates For all ML-assisted methods (i.e., PAI, SAI, PPI, and PPAT), we use the same underlying probabilistic ML model and online updating procedure whenever applicable. For all datasets except the LLM evaluation suites and AlphaFold, we standardize covariates using training-split statistics and fit an initial logistic regression on the training data, initializing its diagonal curvature approximation to the identity. For the two LLM evaluation suites, following Wu et al. [27 ] , we instead initialize the model coefficients using the empirical mean of historical model factors and the diagonal curvature using their inverse empirical marginal variances, retaining the original question-factor representations. For all datasets except AlphaFold, we update the logistic regression model after every acquired label using computationally-efficient diagonal stochastic Newton updates adapted from Bercu et al. [5 ] , as detailed in Appendix § 9 .§ 6 . AlphaFold is the sole exception, since only fixed ML predictions are available.
Baselines and competitor methods
PAI and SAI For PAI and SAI, we use the same underlying ML predictor and online updating procedure. Following Zrnic & Candès (2024, Sections 4 and 7.2), both methods also use the uncertainty score u t ( x ) = 2 min ( f ^ ( t − 1 ) ( x ) , 1 − f ^ ( t − 1 ) ( x ) ) u_t(x)=2\min(\hat{f}^{(t-1)}(x),1-\hat{f}^{(t-1)}(x)) u t ( x ) = 2 min ( f ^ ( t − 1 ) ( x ) , 1 − f ^ ( t − 1 ) ( x )) and uniform-mixing parameter τ = 0.5 \tau=0.5 τ = 0.5 . At each round t t t , PAI samples without replacement from the remaining unlabeled pool R t − 1 R_{t-1} R t − 1 according to the acquisition policy
q t ( i ) = τ ∣ R t − 1 ∣ + ( 1 − τ ) u t ( x i ) ∑ j ∈ R t − 1 u t ( x j ) . (16) q_t(i)=\frac{\tau}{\lvert R_{t-1}\rvert}+(1-\tau)\frac{u_t(x_i)}{\sum_{j\in R_{t-1}}u_t(x_j)}. \tag*{(16)} q t ( i ) = ∣ R t − 1 ∣ τ + ( 1 − τ ) ∑ j ∈ R t − 1 u t ( x j ) u t ( x i ) . (16)
In contrast, SAI processes the test observations sequentially, at round t t t choosing whether to acquire label y t y_t y t with probability π t ( x t ) \pi_t(x_t) π t ( x t ) . Its mean estimator is
θ ^ a c t i v e : = 1 N ∑ t = 1 N ( f ^ ( t − 1 ) ( x t ) + ( y t − f ^ ( t − 1 ) ( x t ) ) ξ t π t ( x t ) ) , (17) \hat{\theta}_{\mathrm{active}}:=\frac{1}{N}\sum_{t=1}^{N}\left(\hat{f}^{(t-1)}(x_t)+(y_t-\hat{f}^{(t-1)}(x_t))\frac{\xi_t}{\pi_t(x_t)}\right), \tag*{(17)} θ ^ active := N 1 t = 1 ∑ N ( f ^ ( t − 1 ) ( x t ) + ( y t − f ^ ( t − 1 ) ( x t )) π t ( x t ) ξ t ) , (17)
where ξ t ∼ Bern ( π t ( x t ) ) \xi_t\sim\operatorname{Bern}(\pi_t(x_t)) ξ t ∼ Bern ( π t ( x t )) indicates whether the label is acquired. To target a labeling budget of n n n observations from a test population of size N N N , we use the following nominal acquisition probability:
π t n o m ( x t ) = τ ( n N ) + ( 1 − τ ) n u t ( x t ) ∑ j = 1 N u t ( x j ) . (18) \pi_t^{\mathrm{nom}}(x_t)=\tau\left(\frac{n}{N}\right)+(1-\tau)\frac{n u_t(x_t)}{\sum_{j=1}^{N}u_t(x_j)}. \tag*{(18)} π t nom ( x t ) = τ ( N n ) + ( 1 − τ ) ∑ j = 1 N u t ( x j ) n u t ( x t ) . (18)
To prevent budget underutilization and ensure good-faith comparisons, we additionally implement the SAI budget-stabilization rule of Zrnic & Candès (2024, Equation 8) and their periodic budget catch-up heuristic from Section 8.4. These adjustments are applied to the uncertainty-based probabilities before mixing with the uniform component, with the resulting acquisition probabilities π t ( x t ) \pi_t(x_t) π t ( x t ) used in the SAI estimator.
PPI and uniform sampling We implement PPI as SAI (Equation (17) ) with uniform Bernoulli acquisition probabilities π t ( x t ) = n / N \pi_t(x_t)=n/N π t ( x t ) = n / N , retaining the shared ML predictions and online updates in the estimator. Our implementation of uniform sampling, while preserving the SAI estimator structure, additionally removes the ML predictions, recovering the corresponding inverse-probability-weighted estimator. Thus, PPI isolates the benefits of ML-assisted inference without adaptive acquisition, while uniform sampling serves as a baseline without any ML assistance. Because both methods use fixed acquisition probabilities, neither requires SAI’s budget-stabilization rule or periodic budget catch-up heuristic.
PPAT We implement the online-tuned λ ^ M \hat{\lambda}_{M} λ ^ M variant of PPAT from Ashouritaklimi et al. [4 ] , using its prediction-powered control-variate estimator and proposed acquisition policy specialized to binary outcomes (§ 3.2 ). Following § 5.1 , we initialize λ ^ M = 0.5 \hat{\lambda}_{M} = 0.5 λ ^ M = 0.5 and update it after every 100 acquired labels. We also use uniform mixing with τ = 0.5 \tau= 0.5 τ = 0.5 , matching PAI and SAI for consistency. We initialize PPAT’s control-variate proxy and acquisition surrogate using the same initial ML predictor as the other ML-assisted methods. During sampling, we update the acquisition surrogate after every acquired label using our shared online learning procedure, while keeping the control-variate proxy fixed. Importantly, this is precisely the fixed-proxy configuration adopted by the PPAT authors themselves when benchmarking against Active Statistical Inference in Appendix C.4.3, combined with their online surrogate updates in § 5.1 . Finally, we select the online-tuned λ ^ M \hat{\lambda}_{M} λ ^ M variant over the fixed choices λ ∈ { 0.5 , 1 } \lambda\in\{0.5, 1\} λ ∈ { 0.5 , 1 } because it had the strongest performance in our preliminary comparisons.
Budgets, metrics, and coverage
Budgets and coverage For each dataset, we consider ten evenly-spaced budgets n ∈ [ 2.5 % , 25 % ] n \in[2.5\%, 25\%] n ∈ [ 2.5% , 25% ] of the test population and target 95% nominal coverage for all experiments. All methods construct nominal 95% Wald-type confidence intervals of the form [ θ ^ m e t h o d ( n ) ± 1.96 σ ^ m e t h o d ( n ) ] [\hat{\theta}_{\mathrm{method}}(n) \pm1.96\hat{\sigma}_{\mathrm{method}}(n)] [ θ ^ method ( n ) ± 1.96 σ ^ method ( n )] , using their respective plug-in variance estimators. For each method and budget, we run 1000 random seeds on the non-LLM datasets, and 100 random seeds for each of approximately 2.2K held-out LLMs on the two LLM evaluation suites. We compute empirical coverage as the proportion of confidence intervals containing the true finite-population mean θ \theta θ , averaging over random seeds and, for the LLM evaluation suites, held-out LLMs.
Metrics To quantify sampling efficiency, we use effective sample size multipliers (ESS multipliers) based on estimated variances. For a method M M M and reference method B B B , both evaluated at labeling budget n n n , we define the ESS multiplier of M M M with respect to B B B as
γ e f f M / B ( n ) : = σ ^ B 2 ( n ) σ ^ M 2 ( n ) . (19) \gamma_{\mathrm{eff}}^{M/B}(n) := \frac{\hat{\sigma}_{B}^{2}(n)}{\hat{\sigma}_{M}^{2}(n)}. \tag*{(19)} γ eff M / B ( n ) := σ ^ M 2 ( n ) σ ^ B 2 ( n ) . (19)
In particular, taking uniform sampling U U U as the reference, the effective sample size (ESS) of method M M M is
n e f f : = γ e f f M / U ( n ) ⋅ n . (20) n_{\mathrm{eff}} := \gamma_{\mathrm{eff}}^{M/U}(n) \cdot n. \tag*{(20)} n eff := γ eff M / U ( n ) ⋅ n . (20)
with uniform sampling having ESS n n n by definition. An ESS multiplier greater than 1 indicates higher sampling efficiency than the reference method. For example, at budget n n n , a multiplier of 1.5 with respect to uniform sampling means achieving approximately the same confidence interval width as uniform sampling with 1.5 n 1.5n 1.5 n labels, corresponding to roughly 33% fewer labels for comparable precision. We report ESS multipliers relative to uniform sampling, SAI, PPI, and PPAT to facilitate comparisons across methods.
Results
Our empirical results seek to investigate four primary questions. First, how does PAI compare in sampling efficiency and statistical coverage against its predecessors: uniform sampling, PPI, and SAI? Second, to what extent does our theoretical characterization of PAI’s efficiency over active inference (Theorem 3 ) carry over to real-data settings with learned acquisition policies and online ML updates? Third, how does PAI compare against the closely related contemporary method PPAT? Fourth, and perhaps most importantly, beyond simply reporting wins and losses, can we identify interpretable explanations for when and why PAI outperforms or underperforms these competing methods, yielding insights applicable to ML-assisted adaptive statistical inference more broadly?
We investigate each of these questions below. Before proceeding, however, we first discuss an important coverage failure on the ULB Credit Card Fraud dataset.
Coverages on the ULB dataset We observe that all three methods using ML predictions to guide acquisition—PAI, SAI, and PPAT—severely undercover the nominal 95% level at the smallest labeling budgets. At the 2.5% budget, empirical coverages are 64.6%, 82.0%, and 63.4% for PAI, SAI, and PPAT, respectively, compared to 92.1% for both PPI and Uniform.
We hypothesize that this undercoverage is driven by the rarity of positive labels, potentially exacerbated by confidently mispredicted positives under ML-guided acquisition. Of the N = 142,404 N = 142{,}404 N = 142 , 404 observations in the ULB test set, only N 1 = 223 N_1 = 223 N 1 = 223 (approximately 0.15%) are fraudulent transactions (y i = 1 y_i = 1 y i = 1 ). At the 2.5% labeling budget, even uniform sampling would acquire only approximately 5.6 positive labels in expectation, potentially compromising the accuracy of normal-approximation confidence intervals. Of these 223 positive observations, the shared initial ML model assigns 39 of them a fraud probability below 1%. These confidently mispredicted positives have large prediction residuals, yet can receive low acquisition probabilities under the ML-guided sampling policies.
Crucially, observing one of these confidently mispredicted positives can provide both (i) a substantial upward correction to the estimated population mean θ ^ \hat{\theta} θ ^ ; and (ii) evidence of substantial sampling variability, particularly through inverse-probability weighting contributions to the variance estimators. Sampling trajectories that fail to acquire these observations can therefore underestimate both θ ^ \hat{\theta} θ ^ and its standard error σ ^ \hat{\sigma} σ ^ , yielding overly narrow confidence intervals that fail to cover the true population mean.
Although the rarity of positive outcomes does not itself invalidate asymptotic inference, we suspect that the normal approximations underlying these methods are unreliable at the labeling budgets considered, with ML-guided acquisition potentially compounding this problem by undersampling rare but consequential positive observations.
Because apparent gains in sampling efficiency are not meaningful without adequate statistical coverage, we exclude ULB from the subsequent ESS comparisons and focus on the remaining seven datasets.
Figure 2. ESS multipliers of PAI over SAI as a function of initial residual imbalance b 0 2 b_0^2 b 0 2 . Each color represents one dataset, with ten points corresponding to the ten labeling budgets tested. Unlike Figure 1, ESS multipliers here are measured with respect to SAI rather than uniform sampling. For example, an ESS multiplier of 2.5 means that PAI matches the confidence interval width of SAI while using only 40% as many labels. Higher ESS multipliers indicate better sampling efficiency, with values above 1 indicating that PAI outperforms SAI. Spearman rank correlations were computed across the seven datasets at each fixed budget, and we report the median, interquartile range (IQR), and minimum of the resulting ten correlations.
On the remaining seven datasets, all methods achieve near-nominal coverage (Figure 6 ), enabling meaningful comparisons of sampling efficiency. First, PAI achieves higher ESS than SAI on all 10 of 10 tested budgets on ACS, BBH+GPQA+IFEval+MATH+MuSR, BODMAS, MMLU-Pro, and Pew; on 9 of 10 tested budgets on AlphaFold; and on 3 of 10 tested budgets on HIV (Figure 1 ). One of the motivations for developing without-replacement PAI was to address limitations of our earlier with-replacement PAI formulation encountered in LLM evaluations (Wu et al. [27 ] ). Reassuringly, on both LLM evaluation suites, without-replacement PAI consistently outperforms its with-replacement predecessor in sampling efficiency (Appendix Figure 7). In short, PAI represents a compelling improvement over SAI in pool-based settings, supporting its role as a natural successor to SAI when the full covariate bank is available for proactive sampling.
Figure 1. Comparing sampling efficiency of Pro-Active Inference (PAI), Sequential Active Inference (SAI), and Prediction-Powered Inference (PPI) with respect to uniform sampling across seven datasets. Each subplot shows the effective sample size (ESS) multiplier with respect to uniform sampling as a function of labeling budget for PAI, SAI, and PPI. For example, on ACS at a 10% budget, an ESS multiplier of 1.6 means PAI matches the confidence interval width of uniform sampling at a 16% budget. Standard errors are shown, but negligible on the plot scale. Higher ESS multipliers indicate better sampling efficiency, with values above 1 indicating an improvement over uniform sampling.
Figure 6. Comparing empirical coverages of Pro-Active Inference (PAI), Sequential Active Inference (SAI), Prediction-Powered Inference (PPI), Uniform Sampling (Uniform), and Prediction-Powered Active Testing (PPAT) across seven datasets. Each subplot shows the empirical coverage of nominal 95% normal-approximation confidence intervals as a function of labeling budget. For all datasets except the two LLM evaluation suites (MMLU-Pro and BBH+GPQA+IFEval+MATH+MusR), empirical coverages are computed over 1000 random seeds. For the two LLM evaluation suites, empirical coverages are averaged over 2.2K test models per evaluation suite and 100 seeds for computational efficiency. Standard errors are shown, but are negligible at the plotted scale.
However, this does not mean that more sophisticated adaptive inference necessarily outperforms simpler methods such as Uniform and PPI. Somewhat surprisingly, PAI only outperforms uniform sampling on 5 of 7 datasets (albeit across all tested budgets), while considerably underperforming on HIV and Pew at all tested budgets (Figure 1 ). Against PPI, PAI outperforms on 4 of 7 datasets (again, across all tested budgets), while substantially underperforming on BODMAS, HIV, and Pew. We defer a detailed investigation of these performance trends to Section 6.4.
Does our theoretical efficiency characterization hold empirically?
Motivated by Theorem 3 , we define the quasi-oracle initial residual imbalance (IRB) diagnostic b 0 2 b_0^2 b 0 2 as a one-step analogue of the b ~ 2 \tilde{b}^2 b ~ 2 quantity in our theoretical characterization, which can be computed without running full sample trajectories:
b 0 2 : = ( ∑ i = 1 N ( y i − f ^ ( 0 ) ( x i ) ) ∑ i = 1 N ∣ y i − f ^ ( 0 ) ( x i ) ∣ ) 2 . (21) b_0^2 := \left(\frac{\sum_{i=1}^{N}\left(y_i-\hat{f}^{(0)}(x_i)\right)}{\sum_{i=1}^{N}\left|y_i-\hat{f}^{(0)}(x_i)\right|}\right)^2 . \tag*{(21)} b 0 2 := ∑ i = 1 N y i − f ^ ( 0 ) ( x i ) ∑ i = 1 N ( y i − f ^ ( 0 ) ( x i ) ) 2 . (21)
Intuitively, IRB measures the extent to which the initial ML model’s prediction residuals systematically point in the same direction, rather than canceling each other out. Values near 0 indicate that positive and negative residuals largely cancel, while values near 1 indicate that residuals of one sign dominate in aggregate magnitude. As discussed in § 4 , IRB is not necessarily indicative of predictive accuracy.
Figure 2 provides strong empirical corroboration of the qualitative prediction from Theorem 3 . Even with online-updated ML models and acquisition policies, IRB exhibits a strong positive rank correlation with PAI’s ESS multiplier gains over SAI across labeling budgets. While we cannot expect the exact 1 / ( 1 − b ˉ 2 ) 1/(1-\bar{b}^{2}) 1/ ( 1 − b ˉ 2 ) functional form to carry over to these more realistic settings, the empirical relationship is striking: larger initial residual imbalance is consistently associated with greater efficiency gains for PAI over SAI.
On quasi-oracle diagnostics We emphasize that the diagnostics in this section (i.e., IRB, ECB, and IVR in Equations (21) -(23) , respectively) are quasi-oracle, computed using the full test population of covariates and labels. These labels are used only for retrospective diagnostic analysis, not for guiding the estimators’ acquisition policies or constructing their estimates. Our goal is to identify interpretable properties associated with sampling efficiency, without relying on post-hoc analyses of the realized sampling trajectories.
How does PAI compare against PPAT?
PAI outperforms PPAT on 10 of 10 tested budgets on AlphaFold; on 9 of 10 budgets each on ACS and MMLU-Pro; and on 8 of 10 budgets on BBH+GPQA+IFEval+MATH+MuSR (Figure 3 ). However, PAI considerably underperforms PPAT on all tested budgets on BODMAS, HIV, and Pew. Curiously, these are precisely the same three datasets where PAI also underperforms PPI (Section 6.1). This common pattern motivates our investigation into when and why PAI gains or loses efficiency relative to competing methods, which we pursue in the following subsection.
Figure 3. ESS multipliers of PAI over PPAT across seven datasets. Each subplot shows PAI’s ESS multiplier with respect to PPAT as a function of labeling budget. For example, on AlphaFold at a 2.5% budget, an ESS multiplier of 1.3 means PAI matches the confidence interval width of PPAT at a 3.25% budget. Standard errors are shown but are generally negligible at the plot scale. Higher ESS multipliers indicate better sampling efficiency, with values above 1 indicating that PAI outperforms PPAT.
What can we learn from PAI’s efficiency gains and losses?
One potential explanation for PAI’s relative efficiency gains and losses against PPI and PPAT lies in its increased sensitivity to the quality of online ML updates. Specifically, PAI incorporates updated ML predictions into both (i) its plug-in estimate and residual correction; and (ii) its acquisition policy. In contrast, PPI, implemented in our experiments as SAI with a uniform acquisition policy, is only affected by online ML updates through its prediction-powered regression adjustment. Similarly, PPAT, as implemented in our experiments, only uses the online-updated ML model to guide acquisition (which Ashouritaklimi et al. [4 ] refer to as the “surrogate”), while the prediction-based control variate retains the initial ML predictions (which the authors refer to as the “proxy”). Importantly, this fixed-proxy formulation is also used by the PPAT authors themselves in their empirical comparisons against Active Statistical Inference (Ashouritaklimi et al. [4 ] , Section 5.1 and Appendix C.4.3).
Thus, while PAI has two channels of sensitivity to online prediction quality, PPI and PPAT, as implemented in our experiments, each have only one. We hypothesize that deteriorating online ML predictions can harm PAI’s sampling efficiency through both channels: less accurate imputations can increase residual-estimation variability, while poorly-guided acquisition can further inflate variance by assigning unfavorable sampling probabilities to observations with large prediction residuals. Conversely, when online ML updates improve predictions, PAI can potentially benefit from both improved imputation and better-guided acquisition.
To investigate this hypothesis, we quantify how the initial online ML update affects probabilistic prediction quality. For each dataset, we define the expected 1-step relative change in Brier score (ECB) as follows:
ECB : = ∑ i = 1 N q 1 ( i ) Brier − i ( f ^ ( 0 , + i ) ) ∑ i = 1 N q 1 ( i ) Brier − i ( f ^ ( 0 ) ) − 1 , where Brier − i ( f ) : = 1 N − 1 ∑ j = 1 j ≠ i N ( y j − f ( x j ) ) 2 . (22) \operatorname{ECB} := \frac{\sum_{i=1}^{N} q_1(i)\operatorname{Brier}_{-i}\left(\hat{f}^{(0,+i)}\right)}{\sum_{i=1}^{N} q_1(i)\operatorname{Brier}_{-i}\left(\hat{f}^{(0)}\right)} - 1,\qquad\text{where }\operatorname{Brier}_{-i}(f) := \frac{1}{N-1}\sum_{\substack{j=1\\j\ne i}}^{N}\left(y_j-f(x_j)\right)^2. \tag*{(22)} ECB := ∑ i = 1 N q 1 ( i ) Brier − i ( f ^ ( 0 ) ) ∑ i = 1 N q 1 ( i ) Brier − i ( f ^ ( 0 , + i ) ) − 1 , where Brier − i ( f ) := N − 1 1 j = 1 j = i ∑ N ( y j − f ( x j ) ) 2 . (22)
Here, q 1 ( i ) q_1(i) q 1 ( i ) is PAI’s initial sampling policy (Equation (16) ), Brier − i ( f ) \operatorname{Brier}_{-i}(f) Brier − i ( f ) is the Brier score of model f f f evaluated over the test population excluding index i i i , and f ^ ( 0 , + i ) \hat{f}^{(0,+i)} f ^ ( 0 , + i ) is the online-updated ML model obtained after observing ( x i , y i ) (x_i,y_i) ( x i , y i ) (see Equation (28) in Appendix § 9 .§ 6 ). Intuitively, ECB measures the relative change in our ML model’s expected probabilistic prediction error after one online update, averaging over the initial PAI sampling policy. Negative ECB values indicate model improvement , while positive values indicate deterioration .
Figure 4 provides strong empirical support for our hypothesis. Among the six datasets with online ML updates,6 all three datasets where PAI outperforms both PPI and PPAT on the majority of tested budgets (ACS, MMLU-Pro, and BBH+GPQA+IFEval+MATH+MuSR) correspond to negative ECB values, while all three datasets where PAI underperforms both methods (BODMAS, HIV, and Pew) correspond to positive ECB values. Beyond this striking separation, ECB is also strongly negatively rank-correlated with PAI’s ESS multipliers over both competing methods across the tested labeling budgets.
Figure 4. ESS multipliers of PAI over PPI and PPAT as a function of the expected 1-step relative change in Brier score (ECB). Each color represents one dataset, with ten points corresponding to the ten labeling budgets tested. The left and right subplots show ESS multipliers with respect to PPI and PPAT, respectively. For example, on ACS in the left subplot, an ESS multiplier of 1.25 means that PAI matches the confidence interval width of PPI while using 20% fewer labels. Higher ESS multipliers indicate better sampling efficiency, with values above 1 indicating that PAI outperforms the corresponding competitor. Spearman rank correlations were computed across the six datasets at each fixed budget, and we report the minimum and maximum of the resulting ten correlations in each subplot.
To further investigate this hypothesis, we conduct a frozen-ML ablation across all six datasets, holding PAI’s initial ML model fixed throughout sampling and thereby disabling online updates in both imputation and acquisition (Appendix Figure 8). Strikingly, on the three datasets with negative ECB values and where PAI outperformed both PPI and PPAT (ACS and the two LLM evaluation suites), freezing substantially reduces PAI’s relative sampling efficiency, reversing its advantages over both PPI and PPAT. Conversely, on the three datasets with positive ECB values (BODMAS, HIV, and Pew), freezing substantially improves PAI’s relative efficiency, reversing its disadvantages against PPI on all three datasets and against PPAT on Pew and 6 of 10 budgets on HIV. On BODMAS, freezing substantially narrows PAI’s disadvantage against PPAT, although it does not eliminate it.
We emphasize that the competing methods’ implementations remain unchanged throughout these ablations, as our goal is to understand the effect of online updating on PAI’s relative efficiency, using the competing methods as fixed reference points, rather than attempting to optimize PAI’s performance against them. Furthermore, because freezing simultaneously affects PAI’s imputation and acquisition, these ablations identify the combined effect of online updating without isolating the contribution of either channel.
Our empirical results raise an important question: when is it advantageous to use ML predictions and adaptive acquisition to estimate a population mean, rather than simply estimating the mean directly through uniform sampling? Intuitively, PAI uses ML predictions to reduce the estimation problem to estimating a residual correction. However, this residual-estimation problem is not necessarily less variable than directly estimating the population mean, particularly if the acquisition policy assigns unfavorable sampling probabilities to observations with large prediction residuals.
Interestingly, the two datasets where PAI underperforms uniform sampling (HIV and Pew) constitute a strict subset of the three datasets where PAI underperforms both PPI and PPAT (BODMAS, HIV, and Pew).
To investigate when residual estimation under PAI is more favorable than direct estimation under uniform sampling, we define the initial variance ratio (IVR) at labeling budget n n n as
IVR ( n ) : = Var ( θ ^ u n i f , n ) n − 1 Var ( φ 1 ) = ( 1 − n / N ) θ ∑ i = 1 N q 1 ( i ) ( f ˉ ( 0 ) + 1 N y i − f ^ ( 0 ) ( x i ) q 1 ( i ) − θ ) 2 , where f ˉ ( 0 ) : = 1 N ∑ i = 1 N f ^ ( 0 ) ( x i ) . (23) \operatorname{IVR}(n) := \frac{\operatorname{Var}(\hat{\theta}_{\mathrm{unif},n})}{n^{-1}\operatorname{Var}(\varphi_1)} = \frac{(1-n/N)\theta}{\sum_{i=1}^{N}q_1(i)\left(\bar{f}^{(0)}+\frac{1}{N}\frac{y_i-\hat{f}^{(0)}(x_i)}{q_1(i)}-\theta\right)^2},
\qquad\text{where }\bar{f}^{(0)}:=\frac{1}{N}\sum_{i=1}^{N}\hat{f}^{(0)}(x_i). \tag*{(23)} IVR ( n ) := n − 1 Var ( φ 1 ) Var ( θ ^ unif , n ) = ∑ i = 1 N q 1 ( i ) ( f ˉ ( 0 ) + N 1 q 1 ( i ) y i − f ^ ( 0 ) ( x i ) − θ ) 2 ( 1 − n / N ) θ , where f ˉ ( 0 ) := N 1 i = 1 ∑ N f ^ ( 0 ) ( x i ) . (23)
Here, uniform sampling is implemented using the no-ML Bernoulli label-skip estimator of Zrnic & Candès (2024), with uniform inclusion probability n / N n/N n / N . The second equality in Equation (23) holds for binary outcomes y i ∈ { 0 , 1 } y_i \in\{0,1\} y i ∈ { 0 , 1 } under this sampling design.
Intuitively, IVR compares the variance of directly estimating the population mean under uniform sampling against the initial variance of estimating the ML model’s mean residual under PAI’s acquisition policy. Larger IVR values suggest that the residual-estimation problem is less noisy than directly estimating the outcome mean, and thus greater potential efficiency gains for PAI over uniform sampling. To obtain a simple, interpretable diagnostic without relying on realized sampling trajectories, we approximate PAI’s variance at budget n n n using its initial one-step variance, scaled by 1 / n 1/n 1/ n . Thus, IVR captures the joint effect of the initial ML predictions and acquisition policy, without accounting for subsequent online model updates, corresponding changes in the acquisition policy, or without-replacement effects.
Figure 5 shows a strong positive rank correlation between IVR and PAI’s realized ESS multipliers over uniform sampling across labeling budgets. This suggests that even the initial ML predictions and acquisition policy already contain substantial information about PAI’s eventual relative sampling efficiency, despite the subsequent complexities of online ML updates and adaptive sampling.
Figure 5. ESS multipliers of PAI over uniform sampling as a function of initial variance ratio (IVR). Each color represents one dataset, with ten points corresponding to the ten labeling budgets tested. An IVR(n n n ) greater than 1 indicates that the initial variance approximation favors PAI over uniform sampling, suggesting a potential efficiency advantage for PAI. Higher ESS multipliers indicate better sampling efficiency, with values above 1 indicating that PAI outperforms uniform sampling. Spearman rank correlations were computed across the seven datasets at each fixed budget, and we report the minimum and maximum of the resulting ten correlations.
What did we learn? Tying together our insights from both Sections 6.4.1 and 6.4.2, we note that IVR and ECB offer complementary perspectives on PAI’s sampling efficiency. While IVR characterizes the relative difficulty of the initial residual-estimation problem under PAI’s acquisition policy, ECB characterizes how the quality of ML predictions changes after an initial online update. Our frozen-ML PAI ablations (described in Section 6.4.1; results in Appendix Figure 8) further demonstrate that subsequent online learning can substantially improve or deteriorate PAI’s realized efficiency relative to its frozen-model counterpart. Thus, understanding when ML-assisted adaptive inference is advantageous requires considering both the initial difficulty of the residual-estimation problem and the subsequent behavior of the online learner.
Discussion and conclusion
Contributions In this work, we develop a more general, without-replacement formulation of Pro-Active Inference (PAI), building on our earlier formulation for efficient LLM evaluation (Wu et al. [27 ] ), and provide a comprehensive statistical treatment of its properties and broader applicability to ML-assisted statistical inference. Our original goal was to build upon the Active Statistical Inference framework of Zrnic & Candès (2024) while pursuing two key desiderata: (i) making fuller use of the available covariate information by proactively selecting observations for labeling from the entire remaining pool, rather than restricting each round to a label-skip decision about the current observation in a predetermined sequence; and (ii) sampling without replacement.
Methodologically, we establish PAI’s finite-sample unbiasedness and asymptotic validity, develop an improved finite-sample variance estimator, and extend PAI to superpopulation inference without the need for Bonferroni corrections or α \alpha α -splitting. We further characterize PAI’s potential efficiency gains over Active Statistical Inference through a theoretical analysis highlighting the role of prediction-residual imbalance. Empirically, through extensive experiments across eight datasets, interpretable theory-motivated diagnostics, and frozen-ML ablations, we investigated when and why PAI outperforms or underperforms competing inference methods, with the broader goal of understanding when ML-assisted adaptive statistical inference itself is advantageous.
On our original goal of building upon Active Statistical Inference Turning to our original goal of building upon Active Statistical Inference, we believe PAI largely achieves both of our stated desiderata. Beyond satisfying them by construction, PAI achieves greater sampling efficiency than SAI across the vast majority of our tested settings, while using the same underlying ML predictor and uncertainty score. Unlike SAI, which processes observations in a predetermined order and cannot revisit skipped observations, PAI can reconsider all remaining unlabeled observations after each acquisition. This flexibility can be particularly valuable when certain observations have large prediction residuals, as PAI retains opportunities to acquire their labels even if they were not selected initially. Our theoretical characterization further identifies prediction-residual imbalance as a key condition under which PAI can achieve substantial efficiency gains over Batch Active Inference. Reassuringly, our empirical initial residual imbalance (IRB) diagnostic strongly corroborates this theoretical intuition, even in more realistic settings with online ML updates and learned acquisition policies.
Understanding the efficiency of ML-assisted adaptive inference Beyond PAI’s improvements over SAI, our experiments highlight that more sophisticated ML-assisted adaptive inference does not necessarily outperform simpler methods such as PPI and uniform sampling. Our proposed diagnostics offer two complementary perspectives on when and why these efficiency gains or losses occur: (i) IVR characterizes how much easier it is to estimate the ML model’s prediction residuals rather than the population mean directly; while (ii) ECB characterizes whether online ML updates improve or deteriorate prediction quality. Our frozen-ML ablations further corroborate the importance of online learning dynamics, while our comparisons with PPAT highlight how different uses of updated ML predictions in acquisition and estimation can affect efficiency.
From retrospective diagnostics to prospective guidance Although our proposed diagnostics IRB, ECB, and IVR were computed retrospectively using the fully labeled test population, an appealing feature is that they summarize important characteristics of the inference problem into a small number of interpretable statistics, without requiring full sampling trajectories. This raises the possibility of approximating these diagnostics using representative validation data or small pilot samples, or reasoning about their values using domain-specific knowledge. For example, IVR depends partly on the unknown population mean θ \theta θ , for which domain scientists may be able to provide plausible ranges, allowing sensitivity analyses when combined with validation- or pilot-based estimates of the relevant residual moments. Similarly, preliminary assessments of online ML updates could help inform whether to continually update or freeze the predictor, or perhaps consider a different update rule. Such assessments could eventually guide the choice of inference method, acquisition policy, or online updating strategy before committing to expensive label collection. Developing and validating these prospective diagnostics constitutes promising future work, particularly given their dependence on the quality and representativeness of the available auxiliary data.
Other limitations and future directions Our experiments deliberately focused on binary outcomes, standardized the underlying ML predictors, and, for PAI and SAI, the acquisition heuristics, to facilitate interpretable comparisons. However, a growing literature investigates optimized and robust acquisition policies for Active Statistical Inference [20 , 19 ] , and alternative ML models and online updating procedures could yield different method-specific relative efficiencies. Rather than extensively tuning each method’s acquisition policy and ML model, our goal was to understand how effectively the competing inferential procedures leverage comparable predictive information. Exploring alternatively potentially domain-specific acquisition policies and online learning strategies for PAI therefore constitutes an important direction for future work.
Furthermore, the severe undercoverage observed on the ULB dataset highlights the challenges of ML-assisted adaptive inference for rare events at finite labeling budgets. Other promising directions include extending our empirical investigations to continuous outcomes and superpopulation settings, developing PAI for more general estimands such as M-estimation, and exploring further domain-specific applications.
More broadly, we hope this work provides a foundation for developing statistically reliable, label-efficient inference methods that make effective use of the increasingly abundant ML predictions and covariate information available in modern applications.
Acknowledgments
We thank Kevin Luo, Alexandru Lopotenco, Etaash Katiyar, Valérie Ho, Noah Cowan, and Ginnie Ma for their many insightful comments, objective outside advice, and helpful discussions. S.W. and Y.N. were both supported by the National Science Foundation Graduate Research Fellowship Program. E.J.C. was supported by the Office of Naval Research grant N000014-20-1-2157. We also gratefully acknowledge support from Arena Intelligence’s Academic Partnerships Program. This work used Marlowe [17 ] , Stanford University’s GPU-based Computational Instrument, supported by Stanford HAI and Stanford Research Computing. We thank Stanford University and the Stanford Research Computing Center for providing the computational resources and support that contributed to these research results.
Proofs and other formulas
Regularity assumptions for Theorem 1
We enumerate some mild regularity conditions for Theorem 1: Assumptions 4-5 are standard conditions for martingale central limit theorems (c.f. [14 Corollary 3.2] ) while Assumption 6 is mild and used to facilitate consistency of our variance estimator. Define Δ t : = ϕ t − θ \Delta_t := \phi_t - \theta Δ t := ϕ t − θ .
Assumption 4 (Variance stabilization). The average conditional variance converges in probability to a positive deterministic limit σ 2 \sigma^2 σ 2 , which does not depend on m m m :
1 n ∑ t = 1 n Var ( Δ t ∣ F t − 1 ) → p σ 2 . \frac{1}{n}\sum_{t=1}^{n}\operatorname{Var}(\Delta_t \mid\mathcal{F}_{t-1}) \xrightarrow{p} \sigma^2. n 1 t = 1 ∑ n Var ( Δ t ∣ F t − 1 ) p σ 2 .
Assumption 5 (Lindeberg condition). The triangular array of problem instances in conjunction with the sampling policies q t ( ⋅ ) q_t(\cdot) q t ( ⋅ ) obey the Lindeberg condition. Specifically, for every ϵ > 0 \epsilon> 0 ϵ > 0 ,
1 n ∑ t = 1 n E [ Δ t 2 1 ( ∣ Δ t ∣ > ϵ n ) ∣ F t − 1 ] → p 0. \frac{1}{n}\sum_{t=1}^{n}\mathbb{E}\left[\Delta_t^2\mathbb{1}\left(\lvert\Delta_t\rvert> \epsilon\sqrt{n}\right)\mid\mathcal{F}_{t-1}\right]\xrightarrow{p}0. n 1 t = 1 ∑ n E [ Δ t 2 1 ( ∣ Δ t ∣ > ϵ n ) ∣ F t − 1 ] p 0.
Assumption 6 (Uniform fourth-moment control for weighted residuals). There exists a deterministic constant C < ∞ C < \infty C < ∞ such that
sup m ≥ 1 sup 1 ≤ t ≤ n m E [ ( 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) ) 4 ] ≤ C . \sup_{m\geq1}\sup_{1\leq t\leq n_m}\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_t}-\hat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}\right)^4\right]\leq C. m ≥ 1 sup 1 ≤ t ≤ n m sup E ( N 1 q t ( I t ) y I t − f ^ ( t − 1 ) ( x I t ) ) 4 ≤ C .
Proof of Theorem 1
Proof. We begin by showing that the Δ t \Delta_t Δ t are martingale differences—that their cumulative sums form a martingale. By definition of F t − 1 \mathcal{F}_{t-1} F t − 1 and q t ( ⋅ ) : = P ( I t = ⋅ ∣ F t − 1 ) q_t(\cdot):=P(I_t=\cdot\mid\mathcal{F}_{t-1}) q t ( ⋅ ) := P ( I t = ⋅ ∣ F t − 1 ) , with division by q t ( ⋅ ) q_t(\cdot) q t ( ⋅ ) well-defined by assumption,
E [ Δ t ∣ F t − 1 ] = E [ 1 N ( ∑ i ∈ O t − 1 y i + ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) + 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) − θ ∣ F t − 1 ] = 1 N ∑ i ∈ O t − 1 y i + 1 N ( ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) + E [ 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) ∣ F t − 1 ] − θ = 1 N ∑ i ∈ O t − 1 y i + 1 N ( ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) + 1 N ∑ i ∉ O t − 1 ( y i − f ^ ( t − 1 ) ( x i ) q t ( i ) ) q t ( i ) − θ = 1 N ∑ i ∈ I y i − θ = 0 , \begin{aligned}
\mathbb{E}[\Delta_t\mid\mathcal{F}_{t-1}]
&=\mathbb{E}\left[\left.\frac{1}{N}\left(\sum_{i\in O_{t-1}}y_i+\sum_{i\notin O_{t-1}}\hat{f}^{(t-1)}(x_i)\right)+\frac{1}{N}\frac{y_{I_t}-\hat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}-\theta\right|\mathcal{F}_{t-1}\right]\\
&=\frac{1}{N}\sum_{i\in O_{t-1}}y_i+\frac{1}{N}\left(\sum_{i\notin O_{t-1}}\hat{f}^{(t-1)}(x_i)\right)+\mathbb{E}\left[\left.\frac{1}{N}\frac{y_{I_t}-\hat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}\right|\mathcal{F}_{t-1}\right]-\theta\\
&=\frac{1}{N}\sum_{i\in O_{t-1}}y_i+\frac{1}{N}\left(\sum_{i\notin O_{t-1}}\hat{f}^{(t-1)}(x_i)\right)+\frac{1}{N}\sum_{i\notin O_{t-1}}\left(\frac{y_i-\hat{f}^{(t-1)}(x_i)}{q_t(i)}\right)q_t(i)-\theta\\
&=\frac{1}{N}\sum_{i\in\mathcal{I}}y_i-\theta=0,
\end{aligned} E [ Δ t ∣ F t − 1 ] = E N 1 i ∈ O t − 1 ∑ y i + i ∈ / O t − 1 ∑ f ^ ( t − 1 ) ( x i ) + N 1 q t ( I t ) y I t − f ^ ( t − 1 ) ( x I t ) − θ F t − 1 = N 1 i ∈ O t − 1 ∑ y i + N 1 i ∈ / O t − 1 ∑ f ^ ( t − 1 ) ( x i ) + E [ N 1 q t ( I t ) y I t − f ^ ( t − 1 ) ( x I t ) F t − 1 ] − θ = N 1 i ∈ O t − 1 ∑ y i + N 1 i ∈ / O t − 1 ∑ f ^ ( t − 1 ) ( x i ) + N 1 i ∈ / O t − 1 ∑ ( q t ( i ) y i − f ^ ( t − 1 ) ( x i ) ) q t ( i ) − θ = N 1 i ∈ I ∑ y i − θ = 0 ,
which implies that ( Δ t , F t ) (\Delta_t,\mathcal{F}_t) ( Δ t , F t ) is a martingale difference array. Now, it immediately follows that
E [ θ ^ n − θ ] = E [ 1 n ∑ t = 1 n ϕ t − θ ] = E [ 1 n ∑ t = 1 n ( ϕ t − θ ) ] = E [ 1 n ∑ t = 1 n Δ t ] = 0 , \mathbb{E}\left[\hat{\theta}_n-\theta\right]=\mathbb{E}\left[\frac{1}{n}\sum_{t=1}^{n}\phi_t-\theta\right]=\mathbb{E}\left[\frac{1}{n}\sum_{t=1}^{n}(\phi_t-\theta)\right]=\mathbb{E}\left[\frac{1}{n}\sum_{t=1}^{n}\Delta_t\right]=0, E [ θ ^ n − θ ] = E [ n 1 t = 1 ∑ n ϕ t − θ ] = E [ n 1 t = 1 ∑ n ( ϕ t − θ ) ] = E [ n 1 t = 1 ∑ n Δ t ] = 0 ,
implying that θ ^ n \hat{\theta}_n θ ^ n is unbiased for θ \theta θ at every finite n n n . Now, by Assumptions 4-5, the martingale central limit theorem as presented in Corollary 3.2 of Hall & Heyde [14 ] tells us that
n ( θ ^ n − θ ) → d N ( 0 , σ 2 ) . \sqrt{n}\left(\hat{\theta}_n-\theta\right)\xrightarrow{d}\mathcal{N}(0,\sigma^2). n ( θ ^ n − θ ) d N ( 0 , σ 2 ) .
To compute a consistent estimator for σ 2 \sigma^2 σ 2 , we proceed by computing the martingale increment conditional variances. By definition of F t − 1 \mathcal{F}_{t-1} F t − 1 , we have
Var ( Δ t ∣ F t − 1 ) = Var ( 1 N ( ∑ i ∈ O t − 1 y i + ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) + 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) − θ ∣ F t − 1 ) = Var ( 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) ∣ F t − 1 ) = E [ ( 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) ) 2 ∣ F t − 1 ] − ( E [ 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) ∣ F t − 1 ] ) 2 = 1 N 2 ∑ i ∉ O t − 1 ( y i − f ^ ( t − 1 ) ( x i ) ) 2 q t ( i ) − 1 N 2 ( ∑ i ∉ O t − 1 ( y i − f ^ ( t − 1 ) ( x i ) ) ) 2 . \begin{aligned}
\operatorname{Var}(\Delta_t \mid\mathcal{F}_{t-1})
&= \operatorname{Var}\left(\frac{1}{N}\left(\sum_{i\in O_{t-1}} y_i+\sum_{i\notin O_{t-1}}\widehat{f}^{(t-1)}(x_i)\right)+\frac{1}{N}\frac{y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}-\theta\mid\mathcal{F}_{t-1}\right)\\
&= \operatorname{Var}\left(\frac{1}{N}\frac{y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}\mid\mathcal{F}_{t-1}\right)\\
&= \mathbb{E}\left[\left.\left(\frac{1}{N}\frac{y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}\right)^2\right|\mathcal{F}_{t-1}\right]-\left(\mathbb{E}\left[\left.\frac{1}{N}\frac{y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}\right|\mathcal{F}_{t-1}\right]\right)^2\\
&= \frac{1}{N^2}\sum_{i\notin O_{t-1}}\frac{\left(y_i-\widehat{f}^{(t-1)}(x_i)\right)^2}{q_t(i)}-\frac{1}{N^2}\left(\sum_{i\notin O_{t-1}}\left(y_i-\widehat{f}^{(t-1)}(x_i)\right)\right)^2.
\end{aligned} Var ( Δ t ∣ F t − 1 ) = Var N 1 i ∈ O t − 1 ∑ y i + i ∈ / O t − 1 ∑ f ( t − 1 ) ( x i ) + N 1 q t ( I t ) y I t − f ( t − 1 ) ( x I t ) − θ ∣ F t − 1 = Var ( N 1 q t ( I t ) y I t − f ( t − 1 ) ( x I t ) ∣ F t − 1 ) = E ( N 1 q t ( I t ) y I t − f ( t − 1 ) ( x I t ) ) 2 F t − 1 − ( E [ N 1 q t ( I t ) y I t − f ( t − 1 ) ( x I t ) F t − 1 ] ) 2 = N 2 1 i ∈ / O t − 1 ∑ q t ( i ) ( y i − f ( t − 1 ) ( x i ) ) 2 − N 2 1 i ∈ / O t − 1 ∑ ( y i − f ( t − 1 ) ( x i ) ) 2 .
By Assumption 4 and substitution, we know that
1 n ∑ t = 1 n Var ( Δ t ∣ F t − 1 ) = 1 n ∑ t = 1 n ( 1 N 2 ∑ i ∉ O t − 1 ( y i − f ^ ( t − 1 ) ( x i ) ) 2 q t ( i ) − 1 N 2 ( ∑ i ∉ O t − 1 ( y i − f ^ ( t − 1 ) ( x i ) ) ) 2 ) = 1 n N 2 ∑ t = 1 n ( ∑ i ∉ O t − 1 ( y i − f ^ ( t − 1 ) ( x i ) ) 2 q t ( i ) ) − 1 n N 2 ∑ t = 1 n ( ∑ i ∉ O t − 1 ( y i − f ^ ( t − 1 ) ( x i ) ) ) 2 = : A n − B n → p σ 2 . \begin{aligned}
\frac{1}{n}\sum_{t=1}^{n}\operatorname{Var}(\Delta_t\mid\mathcal{F}_{t-1})
&=\frac{1}{n}\sum_{t=1}^{n}\left(\frac{1}{N^2}\sum_{i\notin O_{t-1}}\frac{\left(y_i-\widehat{f}^{(t-1)}(x_i)\right)^2}{q_t(i)}-\frac{1}{N^2}\left(\sum_{i\notin O_{t-1}}\left(y_i-\widehat{f}^{(t-1)}(x_i)\right)\right)^2\right)\\
&=\frac{1}{nN^2}\sum_{t=1}^{n}\left(\sum_{i\notin O_{t-1}}\frac{\left(y_i-\widehat{f}^{(t-1)}(x_i)\right)^2}{q_t(i)}\right)-\frac{1}{nN^2}\sum_{t=1}^{n}\left(\sum_{i\notin O_{t-1}}\left(y_i-\widehat{f}^{(t-1)}(x_i)\right)\right)^2\\
&=: A_n-B_n \xrightarrow{p}\sigma^2.
\end{aligned} n 1 t = 1 ∑ n Var ( Δ t ∣ F t − 1 ) = n 1 t = 1 ∑ n N 2 1 i ∈ / O t − 1 ∑ q t ( i ) ( y i − f ( t − 1 ) ( x i ) ) 2 − N 2 1 i ∈ / O t − 1 ∑ ( y i − f ( t − 1 ) ( x i ) ) 2 = n N 2 1 t = 1 ∑ n i ∈ / O t − 1 ∑ q t ( i ) ( y i − f ( t − 1 ) ( x i ) ) 2 − n N 2 1 t = 1 ∑ n i ∈ / O t − 1 ∑ ( y i − f ( t − 1 ) ( x i ) ) 2 =: A n − B n p σ 2 .
To show that σ ^ n 2 → p σ 2 \widehat{\sigma}_n^2\xrightarrow{p}\sigma^2 σ n 2 p σ 2 , it suffices to show that (a) A ^ n − A n = o p ( 1 ) \widehat{A}_n-A_n=o_p(1) A n − A n = o p ( 1 ) and (b) B ^ n − B n = o p ( 1 ) \widehat{B}_n-B_n=o_p(1) B n − B n = o p ( 1 ) . Beginning with the first statement,
A ^ n − A n = 1 n N 2 ∑ t = 1 n ( y I t − f ^ ( t − 1 ) ( x I t ) ) 2 q t ( I t ) 2 − 1 n N 2 ∑ t = 1 n ( ∑ i ∉ O t − 1 ( y i − f ^ ( t − 1 ) ( x i ) ) 2 q t ( i ) ) = 1 n ∑ t = 1 n 1 N 2 ( ( y I t − f ^ ( t − 1 ) ( x I t ) ) 2 q t ( I t ) 2 − ∑ i ∉ O t − 1 ( y i − f ^ ( t − 1 ) ( x i ) ) 2 q t ( i ) ) = : 1 n ∑ t = 1 n C t . \begin{aligned}
\widehat{A}_n-A_n
&=\frac{1}{nN^2}\sum_{t=1}^{n}\frac{\left(y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})\right)^2}{q_t(I_t)^2}-\frac{1}{nN^2}\sum_{t=1}^{n}\left(\sum_{i\notin O_{t-1}}\frac{\left(y_i-\widehat{f}^{(t-1)}(x_i)\right)^2}{q_t(i)}\right)\\
&=\frac{1}{n}\sum_{t=1}^{n}\frac{1}{N^2}\left(\frac{\left(y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})\right)^2}{q_t(I_t)^2}-\sum_{i\notin O_{t-1}}\frac{\left(y_i-\widehat{f}^{(t-1)}(x_i)\right)^2}{q_t(i)}\right)=:\frac{1}{n}\sum_{t=1}^{n}C_t.
\end{aligned} A n − A n = n N 2 1 t = 1 ∑ n q t ( I t ) 2 ( y I t − f ( t − 1 ) ( x I t ) ) 2 − n N 2 1 t = 1 ∑ n i ∈ / O t − 1 ∑ q t ( i ) ( y i − f ( t − 1 ) ( x i ) ) 2 = n 1 t = 1 ∑ n N 2 1 q t ( I t ) 2 ( y I t − f ( t − 1 ) ( x I t ) ) 2 − i ∈ / O t − 1 ∑ q t ( i ) ( y i − f ( t − 1 ) ( x i ) ) 2 =: n 1 t = 1 ∑ n C t .
Because we have
E [ C t ∣ F t − 1 ] = E [ 1 N 2 ( ( y I t − f ^ ( t − 1 ) ( x I t ) ) 2 q t ( I t ) 2 − ∑ i ∉ O t − 1 ( y i − f ^ ( t − 1 ) ( x i ) ) 2 q t ( i ) ) ∣ F t − 1 ] = E [ 1 N 2 ( ( y I t − f ^ ( t − 1 ) ( x I t ) ) 2 q t ( I t ) 2 ) ∣ F t − 1 ] − 1 N 2 ( ∑ i ∉ O t − 1 ( y i − f ^ ( t − 1 ) ( x i ) ) 2 q t ( i ) ) = ∑ i ∉ O t − 1 1 N 2 ( ( y i − f ^ ( t − 1 ) ( x i ) ) 2 q t ( i ) 2 ) q t ( i ) − 1 N 2 ( ∑ i ∉ O t − 1 ( y i − f ^ ( t − 1 ) ( x i ) ) 2 q t ( i ) ) = 0 , \begin{aligned}
\mathbb{E}[C_t\mid\mathcal{F}_{t-1}]
&=\mathbb{E}\left[\left.\frac{1}{N^2}\left(\frac{\left(y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})\right)^2}{q_t(I_t)^2}-\sum_{i\notin O_{t-1}}\frac{\left(y_i-\widehat{f}^{(t-1)}(x_i)\right)^2}{q_t(i)}\right)\right|\mathcal{F}_{t-1}\right]\\
&=\mathbb{E}\left[\left.\frac{1}{N^2}\left(\frac{\left(y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})\right)^2}{q_t(I_t)^2}\right)\right|\mathcal{F}_{t-1}\right]-\frac{1}{N^2}\left(\sum_{i\notin O_{t-1}}\frac{\left(y_i-\widehat{f}^{(t-1)}(x_i)\right)^2}{q_t(i)}\right)\\
&=\sum_{i\notin O_{t-1}}\frac{1}{N^2}\left(\frac{\left(y_i-\widehat{f}^{(t-1)}(x_i)\right)^2}{q_t(i)^2}\right)q_t(i)-\frac{1}{N^2}\left(\sum_{i\notin O_{t-1}}\frac{\left(y_i-\widehat{f}^{(t-1)}(x_i)\right)^2}{q_t(i)}\right)=0,
\end{aligned} E [ C t ∣ F t − 1 ] = E N 2 1 q t ( I t ) 2 ( y I t − f ( t − 1 ) ( x I t ) ) 2 − i ∈ / O t − 1 ∑ q t ( i ) ( y i − f ( t − 1 ) ( x i ) ) 2 F t − 1 = E N 2 1 q t ( I t ) 2 ( y I t − f ( t − 1 ) ( x I t ) ) 2 F t − 1 − N 2 1 i ∈ / O t − 1 ∑ q t ( i ) ( y i − f ( t − 1 ) ( x i ) ) 2 = i ∈ / O t − 1 ∑ N 2 1 q t ( i ) 2 ( y i − f ( t − 1 ) ( x i ) ) 2 q t ( i ) − N 2 1 i ∈ / O t − 1 ∑ q t ( i ) ( y i − f ( t − 1 ) ( x i ) ) 2 = 0 ,
we can deduce that ( C t , F t ) (\mathcal{C}_t,\mathcal{F}_t) ( C t , F t ) is a martingale difference array. By orthogonality of martingale increments (i.e., tower property), we further find that
E [ ( A ^ n − A n ) 2 ] = E [ ( 1 n ∑ t = 1 n C t ) 2 ] = 1 n 2 ∑ t = 1 n E [ C t 2 ] . \mathbb{E}\left[\left(\widehat{A}_n-A_n\right)^2\right]=\mathbb{E}\left[\left(\frac{1}{n}\sum_{t=1}^{n}C_t\right)^2\right]=\frac{1}{n^2}\sum_{t=1}^{n}\mathbb{E}\left[C_t^2\right]. E [ ( A n − A n ) 2 ] = E ( n 1 t = 1 ∑ n C t ) 2 = n 2 1 t = 1 ∑ n E [ C t 2 ] .
Now, because ( a − b ) 2 ≤ 2 a 2 + 2 b 2 (a-b)^2\leq2a^2+2b^2 ( a − b ) 2 ≤ 2 a 2 + 2 b 2 ,
E [ C t 2 ] ≤ E [ 2 ( 1 N 2 y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) 2 ) 2 + 2 ( 1 N 2 ∑ i ∉ O t − 1 y i − f ^ ( t − 1 ) ( x i ) q t ( i ) ) 2 ] = 2 E [ ( 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) ) 4 ] + 2 E [ ( E [ 1 N 2 ( y I t − f ^ ( t − 1 ) ( x I t ) ) 2 q t ( I t ) 2 | F t − 1 ] ) 2 ] = 2 E [ ( 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) ) 4 ] + 2 E [ E [ ( 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) ) 4 | F t − 1 ] ] = 4 E [ ( 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) ) 4 ] ≤ 4 C , \begin{aligned}
\mathbb{E}\left[C_t^2\right]&\leq\mathbb{E}\left[2\left(\frac{1}{N^2}\frac{y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)^2}\right)^2+2\left(\frac{1}{N^2}\sum_{i\notin O_{t-1}}\frac{y_i-\widehat{f}^{(t-1)}(x_i)}{q_t(i)}\right)^2\right]\\
&=2\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}\right)^4\right]+2\mathbb{E}\left[\left(\mathbb{E}\left[\frac{1}{N^2}\frac{\left(y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})\right)^2}{q_t(I_t)^2}\,\middle|\,\mathcal{F}_{t-1}\right]\right)^2\right]\\
&=2\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}\right)^4\right]+2\mathbb{E}\left[\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}\right)^4\,\middle|\,\mathcal{F}_{t-1}\right]\right]\\
&=4\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}\right)^4\right]\leq4C,
\end{aligned} E [ C t 2 ] ≤ E 2 ( N 2 1 q t ( I t ) 2 y I t − f ( t − 1 ) ( x I t ) ) 2 + 2 N 2 1 i ∈ / O t − 1 ∑ q t ( i ) y i − f ( t − 1 ) ( x i ) 2 = 2 E ( N 1 q t ( I t ) y I t − f ( t − 1 ) ( x I t ) ) 4 + 2 E E N 2 1 q t ( I t ) 2 ( y I t − f ( t − 1 ) ( x I t ) ) 2 F t − 1 2 = 2 E ( N 1 q t ( I t ) y I t − f ( t − 1 ) ( x I t ) ) 4 + 2 E E ( N 1 q t ( I t ) y I t − f ( t − 1 ) ( x I t ) ) 4 F t − 1 = 4 E ( N 1 q t ( I t ) y I t − f ( t − 1 ) ( x I t ) ) 4 ≤ 4 C ,
with the last step by Assumption 6. As such, we deduce that E [ ( A ^ n − A n ) 2 ] → 0 \mathbb{E}\left[\left(\widehat{A}_n-A_n\right)^2\right]\to0 E [ ( A n − A n ) 2 ] → 0 , which implies that A ^ n − A n = o p ( 1 ) \widehat{A}_n-A_n=o_p(1) A n − A n = o p ( 1 ) . Working on the second term, we first observe that
B n = 1 n N 2 ∑ t = 1 n ( ∑ i ∉ O t − 1 ( y i − f ^ ( t − 1 ) ( x i ) ) ) 2 = 1 n N 2 ∑ t = 1 n ( N θ − ∑ i ∈ O t − 1 y i − ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) 2 = 1 n N 2 ∑ t = 2 n ( N θ − ∑ i ∈ O t − 1 y i − ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) 2 + 1 n N 2 ( N θ − ∑ i = 1 N f ^ ( t − 1 ) ( x i ) ) 2 . \begin{aligned}
B_n&=\frac{1}{nN^2}\sum_{t=1}^{n}\left(\sum_{i\notin O_{t-1}}\left(y_i-\widehat{f}^{(t-1)}(x_i)\right)\right)^2\\
&=\frac{1}{nN^2}\sum_{t=1}^{n}\left(N\theta-\sum_{i\in O_{t-1}}y_i-\sum_{i\notin O_{t-1}}\widehat{f}^{(t-1)}(x_i)\right)^2\\
&=\frac{1}{nN^2}\sum_{t=2}^{n}\left(N\theta-\sum_{i\in O_{t-1}}y_i-\sum_{i\notin O_{t-1}}\widehat{f}^{(t-1)}(x_i)\right)^2+\frac{1}{nN^2}\left(N\theta-\sum_{i=1}^{N}\widehat{f}^{(t-1)}(x_i)\right)^2.
\end{aligned} B n = n N 2 1 t = 1 ∑ n i ∈ / O t − 1 ∑ ( y i − f ( t − 1 ) ( x i ) ) 2 = n N 2 1 t = 1 ∑ n N θ − i ∈ O t − 1 ∑ y i − i ∈ / O t − 1 ∑ f ( t − 1 ) ( x i ) 2 = n N 2 1 t = 2 ∑ n N θ − i ∈ O t − 1 ∑ y i − i ∈ / O t − 1 ∑ f ( t − 1 ) ( x i ) 2 + n N 2 1 ( N θ − i = 1 ∑ N f ( t − 1 ) ( x i ) ) 2 .
With this alternative form, and using the equality that a 2 − b 2 = ( a − b ) 2 + 2 b ( a − b ) a^2-b^2=(a-b)^2+2b(a-b) a 2 − b 2 = ( a − b ) 2 + 2 b ( a − b ) to combine similar terms, we have the following:
B ^ n − B n = 1 n N 2 ∑ t = 2 n ( N θ ^ t − 1 − ∑ i ∈ O t − 1 y i − ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) 2 − 1 n N 2 ∑ t = 2 n ( N θ − ∑ i ∈ O t − 1 y i − ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) 2 − 1 n N 2 ( N θ − ∑ i = 1 N f ^ ( 0 ) ( x i ) ) 2 = 1 n N 2 ∑ t = 2 n [ ( N θ ^ t − 1 − ∑ i ∈ O t − 1 y i − ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) 2 − ( N θ − ∑ i ∈ O t − 1 y i − ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) 2 ] − 1 n N 2 ( N θ − ∑ i = 1 N f ^ ( 0 ) ( x i ) ) 2 = 1 n ∑ t = 2 n ( θ ^ t − 1 − θ ) 2 + 2 n ∑ t = 2 n ( θ − ∑ i ∈ O t − 1 y i + ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) N ) ( θ ^ t − 1 − θ ) − 1 n ( θ − ∑ i = 1 N f ^ ( 0 ) ( x i ) N ) 2 . \begin{aligned}
\widehat{B}_n-B_n
={}&\frac{1}{nN^2}\sum_{t=2}^{n}\left(N\widehat{\theta}_{t-1}-\sum_{i\in O_{t-1}}y_i-\sum_{i\notin O_{t-1}}\widehat{f}^{(t-1)}(x_i)\right)^2\\
&-\frac{1}{nN^2}\sum_{t=2}^{n}\left(N\theta-\sum_{i\in O_{t-1}}y_i-\sum_{i\notin O_{t-1}}\widehat{f}^{(t-1)}(x_i)\right)^2-\frac{1}{nN^2}\left(N\theta-\sum_{i=1}^{N}\widehat{f}^{(0)}(x_i)\right)^2\\
={}&\frac{1}{nN^2}\sum_{t=2}^{n}\left[\left(N\widehat{\theta}_{t-1}-\sum_{i\in O_{t-1}}y_i-\sum_{i\notin O_{t-1}}\widehat{f}^{(t-1)}(x_i)\right)^2-\left(N\theta-\sum_{i\in O_{t-1}}y_i-\sum_{i\notin O_{t-1}}\widehat{f}^{(t-1)}(x_i)\right)^2\right]\\
&-\frac{1}{nN^2}\left(N\theta-\sum_{i=1}^{N}\widehat{f}^{(0)}(x_i)\right)^2\\
={}&\frac{1}{n}\sum_{t=2}^{n}\left(\widehat{\theta}_{t-1}-\theta\right)^2+\frac{2}{n}\sum_{t=2}^{n}\left(\theta-\frac{\sum_{i\in O_{t-1}}y_i+\sum_{i\notin O_{t-1}}\widehat{f}^{(t-1)}(x_i)}{N}\right)\left(\widehat{\theta}_{t-1}-\theta\right)\\
&-\frac{1}{n}\left(\theta-\frac{\sum_{i=1}^{N}\widehat{f}^{(0)}(x_i)}{N}\right)^2.
\end{aligned} B n − B n = = = n N 2 1 t = 2 ∑ n N θ t − 1 − i ∈ O t − 1 ∑ y i − i ∈ / O t − 1 ∑ f ( t − 1 ) ( x i ) 2 − n N 2 1 t = 2 ∑ n N θ − i ∈ O t − 1 ∑ y i − i ∈ / O t − 1 ∑ f ( t − 1 ) ( x i ) 2 − n N 2 1 ( N θ − i = 1 ∑ N f ( 0 ) ( x i ) ) 2 n N 2 1 t = 2 ∑ n N θ t − 1 − i ∈ O t − 1 ∑ y i − i ∈ / O t − 1 ∑ f ( t − 1 ) ( x i ) 2 − N θ − i ∈ O t − 1 ∑ y i − i ∈ / O t − 1 ∑ f ( t − 1 ) ( x i ) 2 − n N 2 1 ( N θ − i = 1 ∑ N f ( 0 ) ( x i ) ) 2 n 1 t = 2 ∑ n ( θ t − 1 − θ ) 2 + n 2 t = 2 ∑ n ( θ − N ∑ i ∈ O t − 1 y i + ∑ i ∈ / O t − 1 f ( t − 1 ) ( x i ) ) ( θ t − 1 − θ ) − n 1 ( θ − N ∑ i = 1 N f ( 0 ) ( x i ) ) 2 .
Taking absolute values, we have
∣ B ^ n − B n ∣ ≤ 1 n ∑ t = 2 n ( θ ^ t − 1 − θ ) 2 ⏟ T 1 + 2 n ∑ t = 2 n ∣ θ − ∑ i ∈ O t − 1 y i + ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) N ∣ ∣ θ ^ t − 1 − θ ∣ ⏟ T 2 + 1 n ( θ − ∑ i = 1 N f ^ ( 0 ) ( x i ) N ) 2 ⏟ T 3 . \left|\widehat{B}_n-B_n\right|\leq\underbrace{\frac{1}{n}\sum_{t=2}^{n}\left(\widehat{\theta}_{t-1}-\theta\right)^2}_{T_1}+\underbrace{\frac{2}{n}\sum_{t=2}^{n}\left|\theta-\frac{\sum_{i\in O_{t-1}}y_i+\sum_{i\notin O_{t-1}}\widehat{f}^{(t-1)}(x_i)}{N}\right|\left|\widehat{\theta}_{t-1}-\theta\right|}_{T_2}+\underbrace{\frac{1}{n}\left(\theta-\frac{\sum_{i=1}^{N}\widehat{f}^{(0)}(x_i)}{N}\right)^2}_{T_3}. B n − B n ≤ T 1 n 1 t = 2 ∑ n ( θ t − 1 − θ ) 2 + T 2 n 2 t = 2 ∑ n θ − N ∑ i ∈ O t − 1 y i + ∑ i ∈ / O t − 1 f ( t − 1 ) ( x i ) θ t − 1 − θ + T 3 n 1 ( θ − N ∑ i = 1 N f ( 0 ) ( x i ) ) 2 .
Working on T 1 T_1 T 1 , we have the following because the Δ s \Delta_s Δ s are martingale differences and by orthogonality of martingale increments:
θ ^ t − 1 − θ = 1 t − 1 ∑ s = 1 t − 1 Δ s ⟹ E [ ( θ ^ t − 1 − θ ) 2 ] = 1 ( t − 1 ) 2 ∑ s = 1 t − 1 E [ Δ s 2 ] . \widehat{\theta}_{t-1}-\theta=\frac{1}{t-1}\sum_{s=1}^{t-1}\Delta_s\ \Longrightarrow\ \mathbb{E}\left[\left(\widehat{\theta}_{t-1}-\theta\right)^2\right]=\frac{1}{(t-1)^2}\sum_{s=1}^{t-1}\mathbb{E}\left[\Delta_s^2\right]. θ t − 1 − θ = t − 1 1 s = 1 ∑ t − 1 Δ s ⟹ E [ ( θ t − 1 − θ ) 2 ] = ( t − 1 ) 2 1 s = 1 ∑ t − 1 E [ Δ s 2 ] .
Now, by Jensen’s Inequality, the fact that ( a − b ) 2 ≤ 2 a 2 + 2 b 2 (a-b)^2\leq2a^2+2b^2 ( a − b ) 2 ≤ 2 a 2 + 2 b 2 , and the following fact:
E [ 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) ∣ F t − 1 ] = 1 N ∑ i ∉ O t − 1 ( y i − f ^ ( t − 1 ) ( x i ) ) , \mathbb{E}\left[\left.\frac{1}{N}\frac{y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}\right|\mathcal{F}_{t-1}\right]=\frac{1}{N}\sum_{i\notin O_{t-1}}\left(y_i-\widehat{f}^{(t-1)}(x_i)\right), E [ N 1 q t ( I t ) y I t − f ( t − 1 ) ( x I t ) F t − 1 ] = N 1 i ∈ / O t − 1 ∑ ( y i − f ( t − 1 ) ( x i ) ) ,
we have the following, noting that θ − 1 N ∑ i ∈ O s − 1 y i = 1 N ∑ i ∉ O s − 1 y i \theta-\frac{1}{N}\sum_{i\in O_{s-1}}y_i=\frac{1}{N}\sum_{i\notin O_{s-1}}y_i θ − N 1 ∑ i ∈ O s − 1 y i = N 1 ∑ i ∈ / O s − 1 y i :
E [ Δ s 2 ] = E [ ( 1 N ( ∑ i ∈ O s − 1 y i + ∑ i ∉ O s − 1 f ^ ( s − 1 ) ( x i ) ) + 1 N y I s − f ^ ( s − 1 ) ( x I s ) q s ( I s ) − θ ) 2 ] ≤ 2 E [ ( 1 N y I s − f ^ ( s − 1 ) ( x I s ) q s ( I s ) ) 2 ] + 2 E [ ( θ − 1 N ( ∑ i ∈ O s − 1 y i + ∑ i ∉ O s − 1 f ^ ( s − 1 ) ( x i ) ) ) 2 ] ≤ 2 ( E [ ( 1 N y I s − f ^ ( s − 1 ) ( x I s ) q s ( I s ) ) 4 ] ) 1 / 2 + 2 E [ ( 1 N ∑ i ∉ O s − 1 y i − 1 N ∑ i ∉ O s − 1 f ^ ( s − 1 ) ( x i ) ) 2 ] = 2 ( E [ ( 1 N y I s − f ^ ( s − 1 ) ( x I s ) q s ( I s ) ) 4 ] ) 1 / 2 + 2 E [ ( E [ 1 N y I s − f ^ ( s − 1 ) ( x I s ) q s ( I s ) ∣ F s − 1 ] ) 2 ] ≤ 2 ( E [ ( 1 N y I s − f ^ ( s − 1 ) ( x I s ) q s ( I s ) ) 4 ] ) 1 / 2 + 2 E [ E [ ( 1 N y I s − f ^ ( s − 1 ) ( x I s ) q s ( I s ) ) 2 ∣ F s − 1 ] ] ≤ 2 ( E [ ( 1 N y I s − f ^ ( s − 1 ) ( x I s ) q s ( I s ) ) 4 ] ) 1 / 2 + 2 E [ ( 1 N y I s − f ^ ( s − 1 ) ( x I s ) q s ( I s ) ) 2 ] ≤ 2 ( E [ ( 1 N y I s − f ^ ( s − 1 ) ( x I s ) q s ( I s ) ) 4 ] ) 1 / 2 + 2 ( E [ ( 1 N y I s − f ^ ( s − 1 ) ( x I s ) q s ( I s ) ) 4 ] ) 1 / 2 ≤ 4 C 1 / 2 . \begin{aligned}
\mathbb{E}\left[\Delta_s^2\right]
&=\mathbb{E}\left[\left(\frac{1}{N}\left(\sum_{i\in O_{s-1}}y_i+\sum_{i\notin O_{s-1}}\hat{f}^{(s-1)}(x_i)\right)+\frac{1}{N}\frac{y_{I_s}-\hat{f}^{(s-1)}(x_{I_s})}{q_s(I_s)}-\theta\right)^2\right]\\
&\leq2\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_s}-\hat{f}^{(s-1)}(x_{I_s})}{q_s(I_s)}\right)^2\right]+2\mathbb{E}\left[\left(\theta-\frac{1}{N}\left(\sum_{i\in O_{s-1}}y_i+\sum_{i\notin O_{s-1}}\hat{f}^{(s-1)}(x_i)\right)\right)^2\right]\\
&\leq2\left(\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_s}-\hat{f}^{(s-1)}(x_{I_s})}{q_s(I_s)}\right)^4\right]\right)^{1/2}+2\mathbb{E}\left[\left(\frac{1}{N}\sum_{i\notin O_{s-1}}y_i-\frac{1}{N}\sum_{i\notin O_{s-1}}\hat{f}^{(s-1)}(x_i)\right)^2\right]\\
&=2\left(\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_s}-\hat{f}^{(s-1)}(x_{I_s})}{q_s(I_s)}\right)^4\right]\right)^{1/2}+2\mathbb{E}\left[\left(\mathbb{E}\left[\left.\frac{1}{N}\frac{y_{I_s}-\hat{f}^{(s-1)}(x_{I_s})}{q_s(I_s)}\right|\mathcal{F}_{s-1}\right]\right)^2\right]\\
&\leq2\left(\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_s}-\hat{f}^{(s-1)}(x_{I_s})}{q_s(I_s)}\right)^4\right]\right)^{1/2}+2\mathbb{E}\left[\mathbb{E}\left[\left.\left(\frac{1}{N}\frac{y_{I_s}-\hat{f}^{(s-1)}(x_{I_s})}{q_s(I_s)}\right)^2\right|\mathcal{F}_{s-1}\right]\right]\\
&\leq2\left(\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_s}-\hat{f}^{(s-1)}(x_{I_s})}{q_s(I_s)}\right)^4\right]\right)^{1/2}+2\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_s}-\hat{f}^{(s-1)}(x_{I_s})}{q_s(I_s)}\right)^2\right]\\
&\leq2\left(\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_s}-\hat{f}^{(s-1)}(x_{I_s})}{q_s(I_s)}\right)^4\right]\right)^{1/2}+2\left(\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_s}-\hat{f}^{(s-1)}(x_{I_s})}{q_s(I_s)}\right)^4\right]\right)^{1/2}\leq4C^{1/2}.
\end{aligned} E [ Δ s 2 ] = E N 1 i ∈ O s − 1 ∑ y i + i ∈ / O s − 1 ∑ f ^ ( s − 1 ) ( x i ) + N 1 q s ( I s ) y I s − f ^ ( s − 1 ) ( x I s ) − θ 2 ≤ 2 E ( N 1 q s ( I s ) y I s − f ^ ( s − 1 ) ( x I s ) ) 2 + 2 E θ − N 1 i ∈ O s − 1 ∑ y i + i ∈ / O s − 1 ∑ f ^ ( s − 1 ) ( x i ) 2 ≤ 2 E ( N 1 q s ( I s ) y I s − f ^ ( s − 1 ) ( x I s ) ) 4 1/2 + 2 E N 1 i ∈ / O s − 1 ∑ y i − N 1 i ∈ / O s − 1 ∑ f ^ ( s − 1 ) ( x i ) 2 = 2 E ( N 1 q s ( I s ) y I s − f ^ ( s − 1 ) ( x I s ) ) 4 1/2 + 2 E ( E [ N 1 q s ( I s ) y I s − f ^ ( s − 1 ) ( x I s ) F s − 1 ] ) 2 ≤ 2 E ( N 1 q s ( I s ) y I s − f ^ ( s − 1 ) ( x I s ) ) 4 1/2 + 2 E E ( N 1 q s ( I s ) y I s − f ^ ( s − 1 ) ( x I s ) ) 2 F s − 1 ≤ 2 E ( N 1 q s ( I s ) y I s − f ^ ( s − 1 ) ( x I s ) ) 4 1/2 + 2 E ( N 1 q s ( I s ) y I s − f ^ ( s − 1 ) ( x I s ) ) 2 ≤ 2 E ( N 1 q s ( I s ) y I s − f ^ ( s − 1 ) ( x I s ) ) 4 1/2 + 2 E ( N 1 q s ( I s ) y I s − f ^ ( s − 1 ) ( x I s ) ) 4 1/2 ≤ 4 C 1/2 .
Thus, we conclude that
E [ T 1 ] = 1 n ∑ t = 2 n E [ ( θ ^ t − 1 − θ ) 2 ] = 1 n ∑ t = 2 n 1 ( t − 1 ) 2 ∑ s = 1 t − 1 E [ Δ s 2 ] ≤ 1 n ∑ t = 2 n 4 C 1 / 2 t − 1 = O ( log n n ) . \mathbb{E}[T_1]=\frac{1}{n}\sum_{t=2}^{n}\mathbb{E}\left[\left(\hat{\theta}_{t-1}-\theta\right)^2\right]=\frac{1}{n}\sum_{t=2}^{n}\frac{1}{(t-1)^2}\sum_{s=1}^{t-1}\mathbb{E}\left[\Delta_s^2\right]\leq\frac{1}{n}\sum_{t=2}^{n}\frac{4C^{1/2}}{t-1}=O\left(\frac{\log n}{n}\right). E [ T 1 ] = n 1 t = 2 ∑ n E [ ( θ ^ t − 1 − θ ) 2 ] = n 1 t = 2 ∑ n ( t − 1 ) 2 1 s = 1 ∑ t − 1 E [ Δ s 2 ] ≤ n 1 t = 2 ∑ n t − 1 4 C 1/2 = O ( n log n ) .
Moving on to T 3 T_3 T 3 , we note that for any t t t , by definition of θ \theta θ ,
θ − 1 N ∑ i ∈ O t − 1 y i − 1 N ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) = 1 N ∑ i ∉ O t − 1 ( y i − f ^ ( t − 1 ) ( x i ) ) = E [ 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) ∣ F t − 1 ] . \begin{aligned}
\theta-\frac{1}{N}\sum_{i\in O_{t-1}}y_i-\frac{1}{N}\sum_{i\notin O_{t-1}}\hat{f}^{(t-1)}(x_i)
&=\frac{1}{N}\sum_{i\notin O_{t-1}}\left(y_i-\hat{f}^{(t-1)}(x_i)\right)\\
&=\mathbb{E}\left[\left.\frac{1}{N}\frac{y_{I_t}-\hat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}\right|\mathcal{F}_{t-1}\right].
\end{aligned} θ − N 1 i ∈ O t − 1 ∑ y i − N 1 i ∈ / O t − 1 ∑ f ^ ( t − 1 ) ( x i ) = N 1 i ∈ / O t − 1 ∑ ( y i − f ^ ( t − 1 ) ( x i ) ) = E [ N 1 q t ( I t ) y I t − f ^ ( t − 1 ) ( x I t ) F t − 1 ] .
By Jensen’s inequality, we deduce that for any t t t ,
E [ ( θ − 1 N ∑ i ∈ O t − 1 y i − 1 N ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) 2 ] = E [ ( E [ 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) ∣ F t − 1 ] ) 2 ] ≤ E [ E [ ( 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) ) 2 ∣ F t − 1 ] ] = E [ ( 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) ) 2 ] ≤ ( E [ ( 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) ) 4 ] ) 1 / 2 ≤ C 1 / 2 . \begin{aligned}
\mathbb{E}\left[\left(\theta-\frac{1}{N}\sum_{i\in O_{t-1}}y_i-\frac{1}{N}\sum_{i\notin O_{t-1}}\hat{f}^{(t-1)}(x_i)\right)^2\right]
&=\mathbb{E}\left[\left(\mathbb{E}\left[\left.\frac{1}{N}\frac{y_{I_t}-\hat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}\right|\mathcal{F}_{t-1}\right]\right)^2\right]\\
&\leq\mathbb{E}\left[\mathbb{E}\left[\left.\left(\frac{1}{N}\frac{y_{I_t}-\hat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}\right)^2\right|\mathcal{F}_{t-1}\right]\right]
=\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_t}-\hat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}\right)^2\right]\\
&\leq\left(\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_t}-\hat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}\right)^4\right]\right)^{1/2}\leq C^{1/2}.
\end{aligned} E θ − N 1 i ∈ O t − 1 ∑ y i − N 1 i ∈ / O t − 1 ∑ f ^ ( t − 1 ) ( x i ) 2 = E ( E [ N 1 q t ( I t ) y I t − f ^ ( t − 1 ) ( x I t ) F t − 1 ] ) 2 ≤ E E ( N 1 q t ( I t ) y I t − f ^ ( t − 1 ) ( x I t ) ) 2 F t − 1 = E ( N 1 q t ( I t ) y I t − f ^ ( t − 1 ) ( x I t ) ) 2 ≤ E ( N 1 q t ( I t ) y I t − f ^ ( t − 1 ) ( x I t ) ) 4 1/2 ≤ C 1/2 .
Thus, it also follows that, corresponding to t = 1 t=1 t = 1 ,
E [ T 3 ] = E [ 1 n ( θ − ∑ i = 1 N f ^ ( 0 ) ( x i ) N ) 2 ] ≤ C 1 / 2 n = O ( 1 n ) . \mathbb{E}[T_3]=\mathbb{E}\left[\frac{1}{n}\left(\theta-\frac{\sum_{i=1}^{N}\hat{f}^{(0)}(x_i)}{N}\right)^2\right]\leq\frac{C^{1/2}}{n}=O\left(\frac{1}{n}\right). E [ T 3 ] = E n 1 ( θ − N ∑ i = 1 N f ^ ( 0 ) ( x i ) ) 2 ≤ n C 1/2 = O ( n 1 ) .
Now, working on T 2 T_2 T 2 , by Cauchy–Schwarz, and using our above facts,
E [ T 2 ] = 2 n ∑ t = 2 n E [ ∣ θ − ∑ i ∈ O t − 1 y i + ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) N ∣ ∣ θ ^ t − 1 − θ ∣ ] ≤ 2 n ∑ t = 2 n E [ ( θ − ∑ i ∈ O t − 1 y i + ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) N ) 2 ] 1 / 2 E [ ( θ ^ t − 1 − θ ) 2 ] 1 / 2 ≤ 2 n ∑ t = 2 n ( C 1 / 2 ) 1 / 2 ( 4 C 1 / 2 t − 1 ) 1 / 2 = 4 C 1 / 2 n ∑ t = 2 n 1 t − 1 = O ( 1 n ) . \begin{aligned}
\mathbb{E}[T_2]=\frac{2}{n}\sum_{t=2}^{n}\mathbb{E}\left[\left|\theta-\frac{\sum_{i\in O_{t-1}}y_i+\sum_{i\notin O_{t-1}}\hat{f}^{(t-1)}(x_i)}{N}\right|\left|\hat{\theta}_{t-1}-\theta\right|\right] \\
&\leq\frac{2}{n}\sum_{t=2}^{n}\mathbb{E}\left[\left(\theta-\frac{\sum_{i\in O_{t-1}}y_i+\sum_{i\notin O_{t-1}}\hat{f}^{(t-1)}(x_i)}{N}\right)^2\right]^{1/2}\mathbb{E}\left[\left(\hat{\theta}_{t-1}-\theta\right)^2\right]^{1/2} \\
&\leq\frac{2}{n}\sum_{t=2}^{n}\left(C^{1/2}\right)^{1/2}\left(\frac{4C^{1/2}}{t-1}\right)^{1/2}=\frac{4C^{1/2}}{n}\sum_{t=2}^{n}\frac{1}{\sqrt{t-1}}=O\left(\frac{1}{\sqrt{n}}\right).
\end{aligned} E [ T 2 ] = n 2 t = 2 ∑ n E [ θ − N ∑ i ∈ O t − 1 y i + ∑ i ∈ / O t − 1 f ^ ( t − 1 ) ( x i ) θ ^ t − 1 − θ ] ≤ n 2 t = 2 ∑ n E ( θ − N ∑ i ∈ O t − 1 y i + ∑ i ∈ / O t − 1 f ^ ( t − 1 ) ( x i ) ) 2 1/2 E [ ( θ ^ t − 1 − θ ) 2 ] 1/2 ≤ n 2 t = 2 ∑ n ( C 1/2 ) 1/2 ( t − 1 4 C 1/2 ) 1/2 = n 4 C 1/2 t = 2 ∑ n t − 1 1 = O ( n 1 ) .
Putting everything together, we deduce that
E [ ∣ B ^ n − B n ∣ ] ≤ E [ T 1 ] + E [ T 2 ] + E [ T 3 ] = O ( log n n ) + O ( 1 n ) + O ( 1 n ) → 0. \mathbb{E}\left[|\hat{B}_n-B_n|\right]\leq\mathbb{E}[T_1]+\mathbb{E}[T_2]+\mathbb{E}[T_3]=O\left(\frac{\log n}{n}\right)+O\left(\frac{1}{\sqrt{n}}\right)+O\left(\frac{1}{n}\right)\to0. E [ ∣ B ^ n − B n ∣ ] ≤ E [ T 1 ] + E [ T 2 ] + E [ T 3 ] = O ( n log n ) + O ( n 1 ) + O ( n 1 ) → 0.
which implies that B ^ n → L 1 B n \hat{B}_n\xrightarrow{L^1}B_n B ^ n L 1 B n , which implies B ^ n − B n = o p ( 1 ) \hat{B}_n-B_n=o_p(1) B ^ n − B n = o p ( 1 ) . Thus, we conclude that σ ^ n 2 → p σ 2 \hat{\sigma}_n^2\xrightarrow{p}\sigma^2 σ ^ n 2 p σ 2 , which by Slutsky’s gives us our desired final result:
n ( θ ^ n − θ ) / σ ^ n → d N ( 0 , 1 ) . \sqrt{n}\left(\hat{\theta}_n-\theta\right)/\hat{\sigma}_n\xrightarrow{d}\mathcal{N}(0,1). n ( θ ^ n − θ ) / σ ^ n d N ( 0 , 1 ) .
Derivation and properties of the improved finite-sample variance estimator
In this section, we motivate, derive, and provide commentary on the improved finite-sample variance estimator σ ^ n , c o r 2 \hat{\sigma}_{n,\mathrm{cor}}^2 σ ^ n , cor 2 introduced in Section 3.3.
Inspirations from second-order Taylor expansions and the ABC and BCa bootstraps
Before starting our derivation, recall from the proof of Theorem 1 in Appendix A.2 that we assumed the following variance stabilization to facilitate our martingale CLT:
1 n ∑ t = 1 n Var ( Δ t ∣ F t − 1 ) : = A n − B n → p σ 2 , \frac{1}{n}\sum_{t=1}^{n}\operatorname{Var}(\Delta_t\mid\mathcal{F}_{t-1}):=A_n-B_n\xrightarrow{p}\sigma^2, n 1 t = 1 ∑ n Var ( Δ t ∣ F t − 1 ) := A n − B n p σ 2 ,
where A ^ n \hat{A}_n A ^ n and B ^ n \hat{B}_n B ^ n are the plug-in estimates for A n A_n A n and B n B_n B n , respectively. From the aforementioned proof, we know that A ^ n \hat{A}_n A ^ n is unbiased for A n A_n A n because A n − A ^ n A_n-\hat{A}_n A n − A ^ n is a martingale sequence. Thus, we elect to bias-correct by working on B ^ n \hat{B}_n B ^ n , which is biased for B n B_n B n because we plugged in θ ^ t − 1 \hat{\theta}_{t-1} θ ^ t − 1 in place of θ \theta θ . Specifically, we proceed to derive a correction term C ^ n \hat{C}_n C ^ n via a second-order Taylor expansion B ^ n − B n \hat{B}_n-B_n B ^ n − B n around θ \theta θ , inspired philosophically by the ABC and BCa bootstrap methods (c.f. Efron [10 ] ; Diciccio & Efron [8 ] ). From the aforementioned proof, we know that
B ^ n − B n = 1 n N 2 ∑ t = 2 n ( N θ ^ t − 1 − ∑ i ∈ O t − 1 y i − ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) 2 − 1 n N 2 ∑ t = 2 n ( N θ − ∑ i ∈ O t − 1 y i − ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) 2 − 1 n N 2 ( N θ − ∑ i = 1 N f ^ ( 0 ) ( x i ) ) 2 . \begin{aligned}
\widehat{B}_n-B_n={}&\frac{1}{nN^2}\sum_{t=2}^{n}\left(N\widehat{\theta}_{t-1}-\sum_{i\in O_{t-1}}y_i-\sum_{i\notin O_{t-1}}\widehat{f}^{(t-1)}(x_i)\right)^2\\
&-\frac{1}{nN^2}\sum_{t=2}^{n}\left(N\theta-\sum_{i\in O_{t-1}}y_i-\sum_{i\notin O_{t-1}}\widehat{f}^{(t-1)}(x_i)\right)^2\\
&-\frac{1}{nN^2}\left(N\theta-\sum_{i=1}^{N}\widehat{f}^{(0)}(x_i)\right)^2.
\end{aligned} B n − B n = n N 2 1 t = 2 ∑ n N θ t − 1 − i ∈ O t − 1 ∑ y i − i ∈ / O t − 1 ∑ f ( t − 1 ) ( x i ) 2 − n N 2 1 t = 2 ∑ n N θ − i ∈ O t − 1 ∑ y i − i ∈ / O t − 1 ∑ f ( t − 1 ) ( x i ) 2 − n N 2 1 ( N θ − i = 1 ∑ N f ( 0 ) ( x i ) ) 2 .
Now, for t = 1 , … , n t=1,\ldots,n t = 1 , … , n , define ψ t : = 1 N ( ∑ i ∈ O t − 1 y i + ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) \psi_t:=\frac{1}{N}\left(\sum_{i\in O_{t-1}}y_i+\sum_{i\notin O_{t-1}}\widehat{f}^{(t-1)}(x_i)\right) ψ t := N 1 ( ∑ i ∈ O t − 1 y i + ∑ i ∈ / O t − 1 f ( t − 1 ) ( x i ) ) and g t ( θ ) = ( θ − ψ t ) 2 g_t(\theta)=(\theta-\psi_t)^2 g t ( θ ) = ( θ − ψ t ) 2 . Then, by substitution, we have the following, where g 1 ( θ ) g_1(\theta) g 1 ( θ ) can be interpreted as a boundary term:
B ^ n − B n = 1 n ∑ t = 2 n ( g t ( θ ^ t − 1 ) − g t ( θ ) ) − 1 n g 1 ( θ ) . \widehat{B}_n-B_n=\frac{1}{n}\sum_{t=2}^{n}\left(g_t(\widehat{\theta}_{t-1})-g_t(\theta)\right)-\frac{1}{n}g_1(\theta). B n − B n = n 1 t = 2 ∑ n ( g t ( θ t − 1 ) − g t ( θ ) ) − n 1 g 1 ( θ ) .
Taylor-expanding each g t g_t g t around θ \theta θ , we have, after noting that g t ′ ( θ ) = 2 ( θ − ψ t ) g_t'(\theta)=2(\theta-\psi_t) g t ′ ( θ ) = 2 ( θ − ψ t ) and that g t ′ ′ ( θ ) = 2 g_t''(\theta)=2 g t ′′ ( θ ) = 2 , the following exact expression as the g t g_t g t were originally quadratic:
g t ( θ ^ t − 1 ) = g t ( θ ) + g t ′ ( θ ) ( θ ^ t − 1 − θ ) + 1 2 g t ′ ′ ( θ ) ( θ ^ t − 1 − θ ) 2 = g t ( θ ) + 2 ( θ − ψ t ) ( θ ^ t − 1 − θ ) + ( θ ^ t − 1 − θ ) 2 . \begin{aligned}
g_t(\widehat{\theta}_{t-1})&=g_t(\theta)+g_t'(\theta)(\widehat{\theta}_{t-1}-\theta)+\frac{1}{2}g_t''(\theta)(\widehat{\theta}_{t-1}-\theta)^2\\
&=g_t(\theta)+2(\theta-\psi_t)(\widehat{\theta}_{t-1}-\theta)+(\widehat{\theta}_{t-1}-\theta)^2.
\end{aligned} g t ( θ t − 1 ) = g t ( θ ) + g t ′ ( θ ) ( θ t − 1 − θ ) + 2 1 g t ′′ ( θ ) ( θ t − 1 − θ ) 2 = g t ( θ ) + 2 ( θ − ψ t ) ( θ t − 1 − θ ) + ( θ t − 1 − θ ) 2 .
Substituting, we have the following, with our boundary term having no θ ^ t − 1 \widehat{\theta}_{t-1} θ t − 1 analog:
B ^ n − B n = 1 n ∑ t = 2 n ( θ ^ t − 1 − θ ) 2 ⏟ second-order Taylor curvature term + 1 n ∑ t = 2 n 2 ( θ − ψ t ) ( θ ^ t − 1 − θ ) ⏟ first-order Taylor term − 1 n g 1 ( θ ) ⏟ boundary term . \widehat{B}_n-B_n=
\underbrace{\frac{1}{n}\sum_{t=2}^{n}(\widehat{\theta}_{t-1}-\theta)^2}_{\text{second-order Taylor curvature term}}
+\underbrace{\frac{1}{n}\sum_{t=2}^{n}2(\theta-\psi_t)(\widehat{\theta}_{t-1}-\theta)}_{\text{first-order Taylor term}}
-\underbrace{\frac{1}{n}g_1(\theta)}_{\text{boundary term}}. B n − B n = second-order Taylor curvature term n 1 t = 2 ∑ n ( θ t − 1 − θ ) 2 + first-order Taylor term n 1 t = 2 ∑ n 2 ( θ − ψ t ) ( θ t − 1 − θ ) − boundary term n 1 g 1 ( θ ) .
Because the purpose of a second-order Taylor correction is to correct the second-order curvature term, we thus explore a correction C ^ n \widehat{C}_n C n that well-approximates 1 n ∑ t = 2 n ( θ ^ t − 1 − θ ) 2 \frac{1}{n}\sum_{t=2}^{n}(\widehat{\theta}_{t-1}-\theta)^2 n 1 ∑ t = 2 n ( θ t − 1 − θ ) 2 . In particular, we do not attempt to bias-correct the first-order Taylor term because it is (a) sign-indefinite; (b) generally not safely estimable without plugging in θ ^ \widehat{\theta} θ for θ \theta θ (and risk introducing another layer of finite-sample bias); and (c) better treated as a component of the stochastic error.
Constructing the correction
Recall our notation in Theorem 1 of
Δ t : = ϕ t − θ , with ϕ t : = 1 N ( ∑ i ∈ O t − 1 y i + ∑ i ∉ O t − 1 f ^ ( t − 1 ) ( x i ) ) + 1 N y I t − f ^ ( t − 1 ) ( x I t ) q t ( I t ) . \Delta_t:=\phi_t-\theta,\qquad\text{with}\quad\phi_t:=\frac{1}{N}\left(\sum_{i\in O_{t-1}}y_i+\sum_{i\notin O_{t-1}}\widehat{f}^{(t-1)}(x_i)\right)+\frac{1}{N}\frac{y_{I_t}-\widehat{f}^{(t-1)}(x_{I_t})}{q_t(I_t)}. Δ t := ϕ t − θ , with ϕ t := N 1 i ∈ O t − 1 ∑ y i + i ∈ / O t − 1 ∑ f ( t − 1 ) ( x i ) + N 1 q t ( I t ) y I t − f ( t − 1 ) ( x I t ) .
recalling that θ ^ t − 1 : = 1 t − 1 ∑ s = 1 t − 1 ϕ s \widehat{\theta}_{t-1}:=\frac{1}{t-1}\sum_{s=1}^{t-1}\phi_s θ t − 1 := t − 1 1 ∑ s = 1 t − 1 ϕ s . Since θ ^ t − 1 = θ + 1 t − 1 ∑ s = 1 t − 1 Δ s \widehat{\theta}_{t-1}=\theta+\frac{1}{t-1}\sum_{s=1}^{t-1}\Delta_s θ t − 1 = θ + t − 1 1 ∑ s = 1 t − 1 Δ s and the Δ s \Delta_s Δ s are martingale differences, by orthogonality we have the following expectation of the target second-order Taylor curvature:
E [ 1 n ∑ t = 2 n ( θ ^ t − 1 − θ ) 2 ] = 1 n ∑ t = 2 n 1 ( t − 1 ) 2 ∑ s = 1 t − 1 E [ v s ] = 1 n ∑ s = 1 n − 1 E [ v s ] w s , with w s : = ∑ k = s n − 1 1 k 2 , (24) \mathbb{E}\left[\frac{1}{n}\sum_{t=2}^{n}(\widehat{\theta}_{t-1}-\theta)^2\right]=\frac{1}{n}\sum_{t=2}^{n}\frac{1}{(t-1)^2}\sum_{s=1}^{t-1}\mathbb{E}[v_s]=\frac{1}{n}\sum_{s=1}^{n-1}\mathbb{E}[v_s]\,w_s,\quad\text{with}\quad w_s:=\sum_{k=s}^{n-1}\frac{1}{k^2}, \tag*{(24)} E [ n 1 t = 2 ∑ n ( θ t − 1 − θ ) 2 ] = n 1 t = 2 ∑ n ( t − 1 ) 2 1 s = 1 ∑ t − 1 E [ v s ] = n 1 s = 1 ∑ n − 1 E [ v s ] w s , with w s := k = s ∑ n − 1 k 2 1 , (24)
where the second equality exchanges the order of summation, and reusing computations from our proof of Theorem 1 in Appendix § 9 .§ 2 , we have per-step conditional variances v s v_s v s as follows:
v s : = Var ( Δ s ∣ F s − 1 ) = 1 N 2 ∑ i ∉ O s − 1 ( y i − f ^ ( s − 1 ) ( x i ) ) 2 q s ( i ) − 1 N 2 ( ∑ i ∉ O s − 1 ( y i − f ^ ( s − 1 ) ( x i ) ) ) 2 = 1 N 2 ∑ i ∉ O s − 1 ( y i − f ^ ( s − 1 ) ( x i ) ) 2 q s ( i ) − ( θ − 1 N ∑ i ∈ O s − 1 y i − 1 N ∑ i ∉ O s − 1 f ^ ( s − 1 ) ( x i ) ) 2 = 1 N 2 ∑ i ∉ O s − 1 ( y i − f ^ ( s − 1 ) ( x i ) ) 2 q s ( i ) − ( θ − ψ s ) 2 . = 1 N 2 ∑ i ∉ O s − 1 ( y i − f ^ ( s − 1 ) ( x i ) ) 2 q s ( i ) − g s ( θ ) . \begin{aligned}
v_s := \operatorname{Var}(\Delta_s \mid\mathcal{F}_{s-1}) \\
&= \frac{1}{N^2}\sum_{i\notin O_{s-1}}\frac{\left(y_i-\hat{f}^{(s-1)}(x_i)\right)^2}{q_s(i)}-\frac{1}{N^2}\left(\sum_{i\notin O_{s-1}}\left(y_i-\hat{f}^{(s-1)}(x_i)\right)\right)^2 \\
&= \frac{1}{N^2}\sum_{i\notin O_{s-1}}\frac{\left(y_i-\hat{f}^{(s-1)}(x_i)\right)^2}{q_s(i)}-\left(\theta-\frac{1}{N}\sum_{i\in O_{s-1}}y_i-\frac{1}{N}\sum_{i\notin O_{s-1}}\hat{f}^{(s-1)}(x_i)\right)^2 \\
&= \frac{1}{N^2}\sum_{i\notin O_{s-1}}\frac{\left(y_i-\hat{f}^{(s-1)}(x_i)\right)^2}{q_s(i)}-(\theta-\psi_s)^2. \\
&= \frac{1}{N^2}\sum_{i\notin O_{s-1}}\frac{\left(y_i-\hat{f}^{(s-1)}(x_i)\right)^2}{q_s(i)}-g_s(\theta).
\end{aligned} v s := Var ( Δ s ∣ F s − 1 ) = N 2 1 i ∈ / O s − 1 ∑ q s ( i ) ( y i − f ^ ( s − 1 ) ( x i ) ) 2 − N 2 1 i ∈ / O s − 1 ∑ ( y i − f ^ ( s − 1 ) ( x i ) ) 2 = N 2 1 i ∈ / O s − 1 ∑ q s ( i ) ( y i − f ^ ( s − 1 ) ( x i ) ) 2 − θ − N 1 i ∈ O s − 1 ∑ y i − N 1 i ∈ / O s − 1 ∑ f ^ ( s − 1 ) ( x i ) 2 = N 2 1 i ∈ / O s − 1 ∑ q s ( i ) ( y i − f ^ ( s − 1 ) ( x i ) ) 2 − ( θ − ψ s ) 2 . = N 2 1 i ∈ / O s − 1 ∑ q s ( i ) ( y i − f ^ ( s − 1 ) ( x i ) ) 2 − g s ( θ ) .
Ideally, our oracle correction term would just be C ^ n ∗ : = 1 n ∑ s = 1 n − 1 v s w s \hat{C}_n^* := \frac{1}{n}\sum_{s=1}^{n-1}v_sw_s C ^ n ∗ := n 1 ∑ s = 1 n − 1 v s w s , but it is clear from above that v s v_s v s is unknown as it involves θ \theta θ . To find a data-driven proxy for the above v s v_s v s , we note that letting
ζ s = 1 N y I s − f ^ ( s − 1 ) ( x I s ) q s ( I s ) , \zeta_s=\frac{1}{N}\frac{y_{I_s}-\hat{f}^{(s-1)}(x_{I_s})}{q_s(I_s)}, ζ s = N 1 q s ( I s ) y I s − f ^ ( s − 1 ) ( x I s ) ,
we have
E [ ζ s 2 ∣ F s − 1 ] = ∑ i ∉ O s − 1 ( 1 N y i − f ^ ( s − 1 ) ( x i ) q s ( i ) ) 2 P ( I s = i ∣ F s − 1 ) = ∑ i ∉ O s − 1 ( 1 N y i − f ^ ( s − 1 ) ( x i ) q s ( i ) ) 2 q s ( i ) = 1 N 2 ∑ i ∉ O s − 1 ( y i − f ^ ( s − 1 ) ( x i ) ) 2 q s ( i ) . \begin{aligned}
\mathbb{E}[\zeta_s^2\mid\mathcal{F}_{s-1}]=\sum_{i\notin O_{s-1}}\left(\frac{1}{N}\frac{y_i-\hat{f}^{(s-1)}(x_i)}{q_s(i)}\right)^2P(I_s=i\mid\mathcal{F}_{s-1}) \\
&=\sum_{i\notin O_{s-1}}\left(\frac{1}{N}\frac{y_i-\hat{f}^{(s-1)}(x_i)}{q_s(i)}\right)^2q_s(i)=\frac{1}{N^2}\sum_{i\notin O_{s-1}}\frac{\left(y_i-\hat{f}^{(s-1)}(x_i)\right)^2}{q_s(i)}.
\end{aligned} E [ ζ s 2 ∣ F s − 1 ] = i ∈ / O s − 1 ∑ ( N 1 q s ( i ) y i − f ^ ( s − 1 ) ( x i ) ) 2 P ( I s = i ∣ F s − 1 ) = i ∈ / O s − 1 ∑ ( N 1 q s ( i ) y i − f ^ ( s − 1 ) ( x i ) ) 2 q s ( i ) = N 2 1 i ∈ / O s − 1 ∑ q s ( i ) ( y i − f ^ ( s − 1 ) ( x i ) ) 2 .
Thus, our derived additive correction is
C ^ n : = 1 n ∑ s = 1 n − 1 ( 1 N y I s − f ^ ( s − 1 ) ( x I s ) q s ( I s ) ) 2 w s , with w s : = ∑ k = s n − 1 1 k 2 . \hat{C}_n:=\frac{1}{n}\sum_{s=1}^{n-1}\left(\frac{1}{N}\frac{y_{I_s}-\hat{f}^{(s-1)}(x_{I_s})}{q_s(I_s)}\right)^2w_s,\quad\text{with}\quad w_s:=\sum_{k=s}^{n-1}\frac{1}{k^2}. C ^ n := n 1 s = 1 ∑ n − 1 ( N 1 q s ( I s ) y I s − f ^ ( s − 1 ) ( x I s ) ) 2 w s , with w s := k = s ∑ n − 1 k 2 1 .
Our bias-corrected variance estimator is thus σ ^ n , c o r 2 : = A ^ n − B ^ n + C ^ n \hat{\sigma}_{n,\mathrm{cor}}^2:=\hat{A}_n-\hat{B}_n+\hat{C}_n σ ^ n , cor 2 := A ^ n − B ^ n + C ^ n . As a follow-up, we do not directly target g s ( θ ) g_s(\theta) g s ( θ ) for correction. Although g s ( θ ) g_s(\theta) g s ( θ ) appears in the analytical second-order curvature expression, estimating it would require an additional plug-in approximation for θ \theta θ , which risks introducing a second layer of finite-sample bias. We therefore use C ^ n \hat{C}_n C ^ n as a feasible positive surrogate: it targets the directly estimable component of the curvature correction and preserves consistency (see below).
Preserving consistency and asymptotic normality
To prove that σ ^ n , c o r 2 → p σ 2 \hat{\sigma}_{n,\mathrm{cor}}^2 \xrightarrow{p} \sigma^2 σ ^ n , cor 2 p σ 2 , where σ 2 \sigma^2 σ 2 is the limiting average increment variance that governs the martingale CLT in Theorem 1 , by Slutsky’s it suffices to prove that C ^ n → p 0 \hat{C}_n \xrightarrow{p} 0 C ^ n p 0 , as we already know that A ^ n − B ^ n → p σ 2 \hat{A}_n-\hat{B}_n \xrightarrow{p}\sigma^2 A ^ n − B ^ n p σ 2 from the corresponding proof in Appendix § 9 .§ 2 . By Jensen’s Inequality and Assumption 6, we know that
E [ C ^ n ] = 1 n ∑ s = 1 n − 1 E [ ( 1 N y I s − f ^ ( s − 1 ) ( x I s ) q s ( I s ) ) 2 ] w s ≤ C 1 / 2 n ∑ s = 1 n − 1 w s = C 1 / 2 n ∑ s = 1 n − 1 ∑ k = s n − 1 1 k 2 → 0. \mathbb{E}[\hat{C}_n]=\frac{1}{n}\sum_{s=1}^{n-1}\mathbb{E}\left[\left(\frac{1}{N}\frac{y_{I_s}-\hat{f}^{(s-1)}(x_{I_s})}{q_s(I_s)}\right)^2\right]w_s\leq\frac{C^{1/2}}{n}\sum_{s=1}^{n-1}w_s=\frac{C^{1/2}}{n}\sum_{s=1}^{n-1}\sum_{k=s}^{n-1}\frac{1}{k^2}\to0. E [ C ^ n ] = n 1 s = 1 ∑ n − 1 E ( N 1 q s ( I s ) y I s − f ^ ( s − 1 ) ( x I s ) ) 2 w s ≤ n C 1/2 s = 1 ∑ n − 1 w s = n C 1/2 s = 1 ∑ n − 1 k = s ∑ n − 1 k 2 1 → 0.
Because C ^ n ≥ 0 \widehat{C}_n \ge0 C n ≥ 0 , it follows that E [ ∣ C ^ n ∣ ] → 0 \mathbb{E}[|\widehat{C}_n|] \to0 E [ ∣ C n ∣ ] → 0 , which implies that C ^ n → L 1 0 \widehat{C}_n \xrightarrow{L^1} 0 C n L 1 0 , which implies that C ^ n = o p ( 1 ) \widehat{C}_n = o_p(1) C n = o p ( 1 ) . Immediately by Slutsky’s Theorem, under the assumptions of Theorem 1 , we have
n ( θ ^ n − θ ) / σ ^ n , c o r → d N ( 0 , 1 ) . \sqrt{n}(\widehat{\theta}_n-\theta)/\widehat{\sigma}_{n,\mathrm{cor}} \xrightarrow{d} \mathcal{N}(0,1). n ( θ n − θ ) / σ n , cor d N ( 0 , 1 ) .
An MSE reduction argument for σ ^ n , c o r 2 \widehat{\sigma}_{n,\mathrm{cor}}^2 σ n , cor 2
We proceed to characterize when σ ^ n , c o r 2 \widehat{\sigma}_{n,\mathrm{cor}}^2 σ n , cor 2 will have a lower MSE than σ ^ n 2 \widehat{\sigma}_n^2 σ n 2 . Expanding and substituting above, we have the following decomposition after adding and subtracting A n − B n A_n-B_n A n − B n :
σ ^ n 2 − σ 2 = A ^ n − B ^ n − σ 2 = ( A ^ n − A n ) − ( B ^ n − B n ) + ( A n − B n − σ 2 ) = ( A ^ n − A n ) − ( 1 n ∑ t = 2 n ( θ ^ t − 1 − θ ) 2 + 1 n ∑ t = 2 n 2 ( θ − ψ t ) ( θ ^ t − 1 − θ ) − 1 n g 1 ( θ ) ) + ( A n − B n − σ 2 ) = ( A ^ n − A n ) + ( A n − B n − σ 2 ) − 1 n ∑ t = 2 n 2 ( θ − ψ t ) ( θ ^ t − 1 − θ ) + 1 n ( θ − ψ 1 ) 2 − 1 n ∑ t = 2 n ( θ ^ t − 1 − θ ) 2 . \begin{aligned}
\widehat{\sigma}_n^2-\sigma^2=\widehat{A}_n-\widehat{B}_n-\sigma^2=(\widehat{A}_n-A_n)-(\widehat{B}_n-B_n)+(A_n-B_n-\sigma^2) \\
&=(\widehat{A}_n-A_n)-\left(\frac{1}{n}\sum_{t=2}^{n}(\widehat{\theta}_{t-1}-\theta)^2+\frac{1}{n}\sum_{t=2}^{n}2(\theta-\psi_t)(\widehat{\theta}_{t-1}-\theta)-\frac{1}{n}g_1(\theta)\right)+(A_n-B_n-\sigma^2) \\
&=(\widehat{A}_n-A_n)+(A_n-B_n-\sigma^2)-\frac{1}{n}\sum_{t=2}^{n}2(\theta-\psi_t)(\widehat{\theta}_{t-1}-\theta)+\frac{1}{n}(\theta-\psi_1)^2-\frac{1}{n}\sum_{t=2}^{n}(\widehat{\theta}_{t-1}-\theta)^2.
\end{aligned} σ n 2 − σ 2 = A n − B n − σ 2 = ( A n − A n ) − ( B n − B n ) + ( A n − B n − σ 2 ) = ( A n − A n ) − ( n 1 t = 2 ∑ n ( θ t − 1 − θ ) 2 + n 1 t = 2 ∑ n 2 ( θ − ψ t ) ( θ t − 1 − θ ) − n 1 g 1 ( θ ) ) + ( A n − B n − σ 2 ) = ( A n − A n ) + ( A n − B n − σ 2 ) − n 1 t = 2 ∑ n 2 ( θ − ψ t ) ( θ t − 1 − θ ) + n 1 ( θ − ψ 1 ) 2 − n 1 t = 2 ∑ n ( θ t − 1 − θ ) 2 .
Reusing the same scaffolding, for σ ^ n , c o r 2 = A ^ n − B ^ n + C ^ n \widehat{\sigma}_{n,\mathrm{cor}}^2=\widehat{A}_n-\widehat{B}_n+\widehat{C}_n σ n , cor 2 = A n − B n + C n , we have
σ ^ n , c o r 2 − σ 2 = E n − T n + C ^ n . \widehat{\sigma}_{n,\mathrm{cor}}^2-\sigma^2=E_n-T_n+\widehat{C}_n. σ n , cor 2 − σ 2 = E n − T n + C n .
Squaring and simplifying, we have
MSE ( σ ^ n , c o r 2 ) − MSE ( σ ^ n 2 ) = E [ ( E n − T n + C ^ n ) 2 ] − E [ ( E n − T n ) 2 ] = E [ ( C ^ n − T n ) 2 ] + 2 E [ C ^ n E n ] − E [ T n 2 ] . \begin{aligned}
\operatorname{MSE}(\widehat{\sigma}_{n,\mathrm{cor}}^2)-\operatorname{MSE}(\widehat{\sigma}_n^2)=\mathbb{E}\left[(E_n-T_n+\widehat{C}_n)^2\right]-\mathbb{E}\left[(E_n-T_n)^2\right] \\
&=\mathbb{E}\left[(\widehat{C}_n-T_n)^2\right]+2\mathbb{E}\left[\widehat{C}_nE_n\right]-\mathbb{E}\left[T_n^2\right].
\end{aligned} MSE ( σ n , cor 2 ) − MSE ( σ n 2 ) = E [ ( E n − T n + C n ) 2 ] − E [ ( E n − T n ) 2 ] = E [ ( C n − T n ) 2 ] + 2 E [ C n E n ] − E [ T n 2 ] .
Finally, we have the following necessary and sufficient criteria for when MSE ( σ ^ n , c o r 2 ) ≤ MSE ( σ ^ n 2 ) \operatorname{MSE}(\widehat{\sigma}_{n,\mathrm{cor}}^2)\le\operatorname{MSE}(\widehat{\sigma}_n^2) MSE ( σ n , cor 2 ) ≤ MSE ( σ n 2 ) :
MSE ( σ ^ n , c o r 2 ) ≤ MSE ( σ ^ n 2 ) ⟺ E [ ( C ^ n − T n ) 2 ] E [ T n 2 ] + 2 E [ C ^ n E n ] E [ T n 2 ] ≤ 1. \operatorname{MSE}(\widehat{\sigma}_{n,\mathrm{cor}}^2)\le\operatorname{MSE}(\widehat{\sigma}_n^2)\Longleftrightarrow\frac{\mathbb{E}\left[(\widehat{C}_n-T_n)^2\right]}{\mathbb{E}[T_n^2]}+\frac{2\mathbb{E}[\widehat{C}_nE_n]}{\mathbb{E}[T_n^2]}\le1. MSE ( σ n , cor 2 ) ≤ MSE ( σ n 2 ) ⟺ E [ T n 2 ] E [ ( C n − T n ) 2 ] + E [ T n 2 ] 2 E [ C n E n ] ≤ 1.
In context, C ^ n \widehat{C}_n C n is our data-driven plug-in estimate for T n T_n T n . In words, the result above tells us that so long as (a) C ^ n \widehat{C}_n C n predicts T n T_n T n better than had we used 0 (i.e., α n \alpha_n α n small); and (b) our correction term C ^ n \widehat{C}_n C n is not excessively7 adversarially positively correlated with the common remaining error term E n E_n E n (i.e., β n \beta_n β n small), then we should expect σ ^ n , c o r 2 \widehat{\sigma}_{n,\mathrm{cor}}^2 σ n , cor 2 to have a lower MSE for σ 2 \sigma^2 σ 2 than σ ^ n 2 \widehat{\sigma}_n^2 σ n 2 .
Proof of Proposition 2
Let θ ^ n \widehat{\theta}_n θ n be our PAI estimator for θ N \theta_N θ N from Equation (2) . We first observe that
n ( θ ^ n − θ ) = n ( θ ^ n − θ N ) + n N N ( θ N − θ ) . \sqrt{n}(\widehat{\theta}_n-\theta)=\sqrt{n}(\widehat{\theta}_n-\theta_N)+\frac{\sqrt{n}}{\sqrt{N}}\sqrt{N}(\theta_N-\theta). n ( θ n − θ ) = n ( θ n − θ N ) + N n N ( θ N − θ ) .
For any s , t s,t s , t , we have the following, noting that θ N \theta_N θ N is a deterministic function of y 1 , … , y N y_1,\ldots,y_N y 1 , … , y N . Formally, the limits here are taken with respect to ( n , N ) ↑ ∞ (n,N)\uparrow\infty ( n , N ) ↑ ∞ in Theorem 1 ’s triangular array setup, letting F N = \mathcal{F}_N= F N = σ ( { ( x i , y i ) } i = 1 N ) \sigma\left(\{(x_i,y_i)\}_{i=1}^{N}\right) σ ( {( x i , y i ) } i = 1 N ) :
lim P ( n ( θ ^ n − θ N ) ≤ s , N ( θ N − θ ) ≤ t ) = lim E [ 1 ( n ( θ ^ n − θ N ) ≤ s , N ( θ N − θ ) ≤ t ) ] = lim E [ 1 ( n ( θ ^ n − θ N ) ≤ s ) 1 ( N ( θ N − θ ) ≤ t ) ] = lim E [ E [ 1 ( n ( θ ^ n − θ N ) ≤ s ) 1 ( N ( θ N − θ ) ≤ t ) ∣ F N ] ] = lim E [ 1 ( N ( θ N − θ ) ≤ t ) E [ 1 ( n ( θ ^ n − θ N ) ≤ s ) ∣ F N ] ] = Φ ( s σ ) lim E [ 1 ( N ( θ N − θ ) ≤ t ) ] = Φ ( s σ ) Φ ( t τ ) , \begin{aligned}
\lim P\left(\sqrt{n}(\hat{\theta}_n-\theta_N)\le s,\sqrt{N}(\theta_N-\theta)\le t\right)
&=\lim\mathbb{E}\left[\mathbf{1}\left(\sqrt{n}(\hat{\theta}_n-\theta_N)\le s,\sqrt{N}(\theta_N-\theta)\le t\right)\right]\\
&=\lim\mathbb{E}\left[\mathbf{1}\left(\sqrt{n}(\hat{\theta}_n-\theta_N)\le s\right)\mathbf{1}\left(\sqrt{N}(\theta_N-\theta)\le t\right)\right]\\
&=\lim\mathbb{E}\left[\mathbb{E}\left[\mathbf{1}\left(\sqrt{n}(\hat{\theta}_n-\theta_N)\le s\right)\mathbf{1}\left(\sqrt{N}(\theta_N-\theta)\le t\right)\mid\mathcal{F}_N\right]\right]\\
&=\lim\mathbb{E}\left[\mathbf{1}\left(\sqrt{N}(\theta_N-\theta)\le t\right)\mathbb{E}\left[\mathbf{1}\left(\sqrt{n}(\hat{\theta}_n-\theta_N)\le s\right)\mid\mathcal{F}_N\right]\right]\\
&=\Phi\left(\frac{s}{\sigma}\right)\lim\mathbb{E}\left[\mathbf{1}\left(\sqrt{N}(\theta_N-\theta)\le t\right)\right]=\Phi\left(\frac{s}{\sigma}\right)\Phi\left(\frac{t}{\tau}\right),
\end{aligned} lim P ( n ( θ ^ n − θ N ) ≤ s , N ( θ N − θ ) ≤ t ) = lim E [ 1 ( n ( θ ^ n − θ N ) ≤ s , N ( θ N − θ ) ≤ t ) ] = lim E [ 1 ( n ( θ ^ n − θ N ) ≤ s ) 1 ( N ( θ N − θ ) ≤ t ) ] = lim E [ E [ 1 ( n ( θ ^ n − θ N ) ≤ s ) 1 ( N ( θ N − θ ) ≤ t ) ∣ F N ] ] = lim E [ 1 ( N ( θ N − θ ) ≤ t ) E [ 1 ( n ( θ ^ n − θ N ) ≤ s ) ∣ F N ] ] = Φ ( σ s ) lim E [ 1 ( N ( θ N − θ ) ≤ t ) ] = Φ ( σ s ) Φ ( τ t ) ,
where σ 2 \sigma^2 σ 2 is the limit of the average conditional variances of the Δ t \Delta_t Δ t (c.f. Theorem 1 and Assumption 4). The last two equalities come from the asymptotic normality of θ ^ n \hat{\theta}_n θ ^ n proven in Theorem 1 , the Dominated Convergence Theorem, and the standard Central Limit Theorem for i.i.d. random variables. Because the joint CDF factors into two independent terms, we deduce that
( n ( θ ^ n − θ N ) , N ( θ N − θ ) ) → d N ( 0 , diag ( σ 2 , τ 2 ) ) . \left(\sqrt{n}(\hat{\theta}_n-\theta_N),\sqrt{N}(\theta_N-\theta)\right)\xrightarrow{d}\mathcal{N}\left(0,\operatorname{diag}\left(\sigma^2,\tau^2\right)\right). ( n ( θ ^ n − θ N ) , N ( θ N − θ ) ) d N ( 0 , diag ( σ 2 , τ 2 ) ) .
By the Continuous Mapping Theorem, it follows that
n ( θ ^ n − θ ) → d N ( 0 , σ 2 + ρ τ 2 ) , (25) \sqrt{n}\left(\hat{\theta}_n-\theta\right)\xrightarrow{d}\mathcal{N}\left(0,\sigma^2+\rho\tau^2\right), \tag*{(25)} n ( θ ^ n − θ ) d N ( 0 , σ 2 + ρ τ 2 ) , (25)
where ρ : = lim n / N \rho:=\lim n/N ρ := lim n / N from Theorem 1 .
Proof of Theorem 3
From the proof of Theorem 1 in Appendix A.2, we have the following after substituting in PAI’s oracle sampling rule, with the expectation necessary because we have to average over all random sampling paths, and permissible because of orthogonality of martingale increments:
Var ( θ ^ P A I ) = 1 n 2 N 2 ∑ t = 1 n E [ ( ∑ i ∉ O t − 1 ( y i − f ( x i ) ) 2 q t ( i ) ) − ( ∑ i ∉ O t − 1 ( y i − f ( x i ) ) ) 2 ] = 1 n 2 N 2 ∑ t = 1 n E [ ( ∑ i ∈ R t − 1 r i 2 q t ( i ) ) − ( ∑ i ∈ R t − 1 e i ) 2 ] = 1 n 2 N 2 ∑ t = 1 n E [ U ( R t − 1 ) 2 − S ( R t − 1 ) 2 ] : = 1 n 2 N 2 ∑ t = 1 n E [ U ( R t − 1 ) 2 ( 1 − b t 2 ) ] = 1 n 2 N 2 ∑ t = 1 n E [ U ( R t − 1 ) 2 ] − E [ U ( R t − 1 ) 2 b t 2 ] , \begin{aligned}
\operatorname{Var}(\hat{\theta}_{\mathrm{PAI}})&=\frac{1}{n^2N^2}\sum_{t=1}^{n}\mathbb{E}\left[\left(\sum_{i\notin\mathcal{O}_{t-1}}\frac{(y_i-f(x_i))^2}{q_t(i)}\right)-\left(\sum_{i\notin\mathcal{O}_{t-1}}(y_i-f(x_i))\right)^2\right]\\
&=\frac{1}{n^2N^2}\sum_{t=1}^{n}\mathbb{E}\left[\left(\sum_{i\in\mathcal{R}_{t-1}}\frac{r_i^2}{q_t(i)}\right)-\left(\sum_{i\in\mathcal{R}_{t-1}}e_i\right)^2\right]\\
&=\frac{1}{n^2N^2}\sum_{t=1}^{n}\mathbb{E}\left[U(R_{t-1})^2-S(R_{t-1})^2\right]:=\frac{1}{n^2N^2}\sum_{t=1}^{n}\mathbb{E}\left[U(R_{t-1})^2(1-b_t^2)\right]\\
&=\frac{1}{n^2N^2}\sum_{t=1}^{n}\mathbb{E}\left[U(R_{t-1})^2\right]-\mathbb{E}\left[U(R_{t-1})^2b_t^2\right],
\end{aligned} Var ( θ ^ PAI ) = n 2 N 2 1 t = 1 ∑ n E i ∈ / O t − 1 ∑ q t ( i ) ( y i − f ( x i ) ) 2 − i ∈ / O t − 1 ∑ ( y i − f ( x i )) 2 = n 2 N 2 1 t = 1 ∑ n E i ∈ R t − 1 ∑ q t ( i ) r i 2 − i ∈ R t − 1 ∑ e i 2 = n 2 N 2 1 t = 1 ∑ n E [ U ( R t − 1 ) 2 − S ( R t − 1 ) 2 ] := n 2 N 2 1 t = 1 ∑ n E [ U ( R t − 1 ) 2 ( 1 − b t 2 ) ] = n 2 N 2 1 t = 1 ∑ n E [ U ( R t − 1 ) 2 ] − E [ U ( R t − 1 ) 2 b t 2 ] ,
if we define b t b_t b t as capturing the net signed direction of the residual mass:
b t = S ( R t − 1 ) U ( R t − 1 ) = ∑ i ∈ R t − 1 y i − f ( x i ) ∑ i ∈ R t − 1 ∣ y i − f ( x i ) ∣ . b_t=\frac{S(R_{t-1})}{U(R_{t-1})}=\frac{\sum_{i\in\mathcal{R}_{t-1}}y_i-f(x_i)}{\sum_{i\in\mathcal{R}_{t-1}}|y_i-f(x_i)|}. b t = U ( R t − 1 ) S ( R t − 1 ) = ∑ i ∈ R t − 1 ∣ y i − f ( x i ) ∣ ∑ i ∈ R t − 1 y i − f ( x i ) .
To formalize, define b ˉ 2 \bar{b}^2 b ˉ 2 to be the weighted-average (squared) net signed direction of the residual mass over the n n n sampling rounds (weighted by U ( R t − 1 ) 2 U(R_{t-1})^2 U ( R t − 1 ) 2 ):
b ˉ 2 : = ∑ t = 1 n E [ U ( R t − 1 ) 2 b t 2 ] ∑ t = 1 n E [ U ( R t − 1 ) 2 ] . (26) \bar{b}^2:=\frac{\sum_{t=1}^{n}\mathbb{E}\left[U(R_{t-1})^2b_t^2\right]}{\sum_{t=1}^{n}\mathbb{E}\left[U(R_{t-1})^2\right]}. \tag*{(26)} b ˉ 2 := ∑ t = 1 n E [ U ( R t − 1 ) 2 ] ∑ t = 1 n E [ U ( R t − 1 ) 2 b t 2 ] . (26)
Then, we have
Var ( θ ^ P A I ) = 1 n 2 N 2 ∑ t = 1 n E [ U ( R t − 1 ) 2 ] − b ˉ 2 E [ U ( R t − 1 ) 2 ] = 1 − b ˉ 2 n 2 N 2 ∑ t = 1 n E [ U ( R t − 1 ) 2 ] : = ( 1 − b ˉ 2 ) A P A I . \operatorname{Var}(\hat{\theta}_{\mathrm{PAI}})=\frac{1}{n^{2}N^{2}}\sum_{t=1}^{n}\mathbb{E}\left[U(R_{t-1})^{2}\right]-\bar{b}^{2}\mathbb{E}\left[U(R_{t-1})^{2}\right]=\frac{1-\bar{b}^{2}}{n^{2}N^{2}}\sum_{t=1}^{n}\mathbb{E}\left[U(R_{t-1})^{2}\right]:=(1-\bar{b}^{2})A_{\mathrm{PAI}}. Var ( θ ^ PAI ) = n 2 N 2 1 t = 1 ∑ n E [ U ( R t − 1 ) 2 ] − b ˉ 2 E [ U ( R t − 1 ) 2 ] = n 2 N 2 1 − b ˉ 2 t = 1 ∑ n E [ U ( R t − 1 ) 2 ] := ( 1 − b ˉ 2 ) A PAI .
Working on the expectation term, letting I t I_t I t represent the index sampled at time t t t , letting Q ( R ) = ∑ i ∈ R r i 2 Q(R)=\sum_{i\in R}r_i^2 Q ( R ) = ∑ i ∈ R r i 2 (“quadratic”), and letting C ( R ) = ∑ i ∈ R r i 3 C(R)=\sum_{i\in R}r_i^3 C ( R ) = ∑ i ∈ R r i 3 (“cubic”), we have by LOTE the following:
E [ U ( R t ) 2 ∣ R t − 1 ] = E [ ( U ( R t − 1 ) − r I t ) 2 ∣ R t − 1 ] = E [ U ( R t − 1 ) 2 − 2 r I t U ( R t − 1 ) + r I t 2 ∣ R t − 1 ] = U ( R t − 1 ) 2 − 2 U ( R t − 1 ) ∑ i ∈ R t − 1 r i 2 U ( R t − 1 ) + ∑ i ∈ R t − 1 r i 3 U ( R t − 1 ) = U ( R t − 1 ) 2 − 2 Q ( R t − 1 ) + C ( R t − 1 ) U ( R t − 1 ) . \begin{aligned}
\mathbb{E}\left[U(R_t)^2\mid R_{t-1}\right]=\mathbb{E}\left[(U(R_{t-1})-r_{I_t})^2\mid R_{t-1}\right]=\mathbb{E}\left[U(R_{t-1})^2-2r_{I_t}U(R_{t-1})+r_{I_t}^2\mid R_{t-1}\right] \\
&=U(R_{t-1})^2-2U(R_{t-1})\sum_{i\in R_{t-1}}\frac{r_i^2}{U(R_{t-1})}+\sum_{i\in R_{t-1}}\frac{r_i^3}{U(R_{t-1})}=U(R_{t-1})^2-2Q(R_{t-1})+\frac{C(R_{t-1})}{U(R_{t-1})}.
\end{aligned} E [ U ( R t ) 2 ∣ R t − 1 ] = E [ ( U ( R t − 1 ) − r I t ) 2 ∣ R t − 1 ] = E [ U ( R t − 1 ) 2 − 2 r I t U ( R t − 1 ) + r I t 2 ∣ R t − 1 ] = U ( R t − 1 ) 2 − 2 U ( R t − 1 ) i ∈ R t − 1 ∑ U ( R t − 1 ) r i 2 + i ∈ R t − 1 ∑ U ( R t − 1 ) r i 3 = U ( R t − 1 ) 2 − 2 Q ( R t − 1 ) + U ( R t − 1 ) C ( R t − 1 ) .
By Tower, we have the following recursion:
E [ U ( R t ) 2 ] = E [ U ( R t − 1 ) 2 ] − E [ 2 Q ( R t − 1 ) − C ( R t − 1 ) U ( R t − 1 ) ] . \mathbb{E}\left[U(R_t)^2\right]=\mathbb{E}\left[U(R_{t-1})^2\right]-\mathbb{E}\left[2Q(R_{t-1})-\frac{C(R_{t-1})}{U(R_{t-1})}\right]. E [ U ( R t ) 2 ] = E [ U ( R t − 1 ) 2 ] − E [ 2 Q ( R t − 1 ) − U ( R t − 1 ) C ( R t − 1 ) ] .
Applying the recursion t t t times, and letting R 0 = I R_0=I R 0 = I , we have
E [ U ( R t ) 2 ] = U ( R 0 ) 2 − ∑ s = 0 t − 1 E [ 2 Q ( R s ) − C ( R s ) U ( R s ) ] . \mathbb{E}\left[U(R_t)^2\right]=U(R_0)^2-\sum_{s=0}^{t-1}\mathbb{E}\left[2Q(R_s)-\frac{C(R_s)}{U(R_s)}\right]. E [ U ( R t ) 2 ] = U ( R 0 ) 2 − s = 0 ∑ t − 1 E [ 2 Q ( R s ) − U ( R s ) C ( R s ) ] .
which tells us the following, after switching the second order of summation and reindexing:
A P A I = 1 n 2 N 2 ∑ t = 1 n E [ U ( R t − 1 ) 2 ] = 1 n 2 N 2 ∑ t = 0 n − 1 E [ U ( R t ) 2 ] = 1 n 2 N 2 ∑ t = 0 n − 1 ( U ( R 0 ) 2 − ∑ s = 0 t − 1 E [ 2 Q ( R s ) − C ( R s ) U ( R s ) ] ) = 1 n N 2 U ( R 0 ) 2 − 1 n 2 N 2 ∑ s = 0 n − 2 ( n − s − 1 ) E [ 2 Q ( R s ) − C ( R s ) U ( R s ) ] . \begin{aligned}
A_{\mathrm{PAI}}=\frac{1}{n^2N^2}\sum_{t=1}^{n}\mathbb{E}\left[U(R_{t-1})^2\right]=\frac{1}{n^2N^2}\sum_{t=0}^{n-1}\mathbb{E}\left[U(R_t)^2\right] \\
&=\frac{1}{n^2N^2}\sum_{t=0}^{n-1}\left(U(R_0)^2-\sum_{s=0}^{t-1}\mathbb{E}\left[2Q(R_s)-\frac{C(R_s)}{U(R_s)}\right]\right) \\
&=\frac{1}{nN^2}U(R_0)^2-\frac{1}{n^2N^2}\sum_{s=0}^{n-2}(n-s-1)\mathbb{E}\left[2Q(R_s)-\frac{C(R_s)}{U(R_s)}\right].
\end{aligned} A PAI = n 2 N 2 1 t = 1 ∑ n E [ U ( R t − 1 ) 2 ] = n 2 N 2 1 t = 0 ∑ n − 1 E [ U ( R t ) 2 ] = n 2 N 2 1 t = 0 ∑ n − 1 ( U ( R 0 ) 2 − s = 0 ∑ t − 1 E [ 2 Q ( R s ) − U ( R s ) C ( R s ) ] ) = n N 2 1 U ( R 0 ) 2 − n 2 N 2 1 s = 0 ∑ n − 2 ( n − s − 1 ) E [ 2 Q ( R s ) − U ( R s ) C ( R s ) ] .
Now, because Q ( R s ) ≤ Q ( R 0 ) Q(R_s)\leq Q(R_0) Q ( R s ) ≤ Q ( R 0 ) and because C ( R s ) / U ( R s ) ≥ 0 C(R_s)/U(R_s)\geq0 C ( R s ) / U ( R s ) ≥ 0 for all s s s , we know by property of arithmetic sums that
A P A I ≥ 1 n N 2 U ( R 0 ) 2 − 1 n 2 N 2 ∑ s = 0 n − 2 ( n − s − 1 ) 2 Q ( R 0 ) = 1 n N 2 U ( R 0 ) 2 − Q ( R 0 ) ( n − 1 ) n N 2 = 1 N 2 ( U ( R 0 ) 2 n − n − 1 n Q ( R 0 ) ) . \begin{aligned}
A_{\mathrm{PAI}}\geq\frac{1}{nN^2}U(R_0)^2-\frac{1}{n^2N^2}\sum_{s=0}^{n-2}(n-s-1)2Q(R_0) \\
&=\frac{1}{nN^2}U(R_0)^2-\frac{Q(R_0)(n-1)}{nN^2}=\frac{1}{N^2}\left(\frac{U(R_0)^2}{n}-\frac{n-1}{n}Q(R_0)\right).
\end{aligned} A PAI ≥ n N 2 1 U ( R 0 ) 2 − n 2 N 2 1 s = 0 ∑ n − 2 ( n − s − 1 ) 2 Q ( R 0 ) = n N 2 1 U ( R 0 ) 2 − n N 2 Q ( R 0 ) ( n − 1 ) = N 2 1 ( n U ( R 0 ) 2 − n n − 1 Q ( R 0 ) ) .
Computing BAI/SAI’s variance (c.f. Equation (11) ), we have
Var ( θ ^ a c t i v e ) = 1 N 2 ∑ t = 1 N ( y t − f ( x t ) ) 2 ( 1 − π t ( x t ) ) π t ( x t ) = 1 N 2 ∑ t = 1 N r t 2 ( 1 π t ( x t ) − 1 ) . \operatorname{Var}(\hat{\theta}_{\mathrm{active}})=\frac{1}{N^2}\sum_{t=1}^{N}\frac{(y_t-f(x_t))^2(1-\pi_t(x_t))}{\pi_t(x_t)}=\frac{1}{N^2}\sum_{t=1}^{N}r_t^2\left(\frac{1}{\pi_t(x_t)}-1\right). Var ( θ ^ active ) = N 2 1 t = 1 ∑ N π t ( x t ) ( y t − f ( x t ) ) 2 ( 1 − π t ( x t )) = N 2 1 t = 1 ∑ N r t 2 ( π t ( x t ) 1 − 1 ) .
After substituting in SAI/BAI’s oracle policy, we have:
Var ( θ ^ a c t i v e ) = 1 N 2 ∑ t = 1 N r t 2 ( 1 π t ( x t ) − 1 ) = 1 N 2 ( U ( R 0 ) 2 n − Q ( R 0 ) ) . \operatorname{Var}(\hat{\theta}_{\mathrm{active}})=\frac{1}{N^2}\sum_{t=1}^{N}r_t^2\left(\frac{1}{\pi_t(x_t)}-1\right)=\frac{1}{N^2}\left(\frac{U(R_0)^2}{n}-Q(R_0)\right). Var ( θ ^ active ) = N 2 1 t = 1 ∑ N r t 2 ( π t ( x t ) 1 − 1 ) = N 2 1 ( n U ( R 0 ) 2 − Q ( R 0 ) ) .
This is very convenient, because it tells us that
A P A I ≥ Var ( θ ^ a c t i v e ) + Q ( R 0 ) n N 2 . A_{\mathrm{PAI}}\geq\operatorname{Var}(\hat{\theta}_{\mathrm{active}})+\frac{Q(R_0)}{nN^2}. A PAI ≥ Var ( θ ^ active ) + n N 2 Q ( R 0 ) .
Working on an upper bound, recall that
A P A I = 1 n N 2 U ( R 0 ) 2 − 1 n 2 N 2 ∑ s = 0 n − 2 ( n − s − 1 ) E [ 2 Q ( R s ) − C ( R s ) U ( R s ) ] . A_{\mathrm{PAI}}=\frac{1}{nN^2}U(R_0)^2-\frac{1}{n^2N^2}\sum_{s=0}^{n-2}(n-s-1)\mathbb{E}\left[2Q(R_s)-\frac{C(R_s)}{U(R_s)}\right]. A PAI = n N 2 1 U ( R 0 ) 2 − n 2 N 2 1 s = 0 ∑ n − 2 ( n − s − 1 ) E [ 2 Q ( R s ) − U ( R s ) C ( R s ) ] .
Because only one unit is removed at each timestep, letting r max = max i ∈ R 0 r i r_{\max}=\max_{i\in R_0}r_i r m a x = max i ∈ R 0 r i we have
Q ( R s ) ≥ Q ( R 0 ) − s r max 2 . Q(R_s)\geq Q(R_0)-sr_{\max}^2. Q ( R s ) ≥ Q ( R 0 ) − s r m a x 2 .
Moreover,
C ( R s ) U ( R s ) = ∑ i ∈ R s r i 3 ∑ i ∈ R s r i ≤ r max 2 ∑ i ∈ R s r i ∑ i ∈ R s r i = r max 2 . \frac{C(R_s)}{U(R_s)}=\frac{\sum_{i\in R_s}r_i^3}{\sum_{i\in R_s}r_i}\leq\frac{r_{\max}^2\sum_{i\in R_s}r_i}{\sum_{i\in R_s}r_i}=r_{\max}^2. U ( R s ) C ( R s ) = ∑ i ∈ R s r i ∑ i ∈ R s r i 3 ≤ ∑ i ∈ R s r i r m a x 2 ∑ i ∈ R s r i = r m a x 2 .
Thus, we have
A P A I ≤ 1 n N 2 U ( R 0 ) 2 − 1 n 2 N 2 ∑ s = 0 n − 2 ( n − s − 1 ) ( 2 Q ( R 0 ) − ( 2 s + 1 ) r max 2 ) = 1 N 2 ( U ( R 0 ) 2 n − n − 1 n Q ( R 0 ) ) + r max 2 n 2 N 2 ∑ s = 0 n − 2 ( n − s − 1 ) ( 2 s + 1 ) . \begin{aligned}
A_{\mathrm{PAI}}\leq\frac{1}{nN^2}U(R_0)^2-\frac{1}{n^2N^2}\sum_{s=0}^{n-2}(n-s-1)\left(2Q(R_0)-(2s+1)r_{\max}^2\right) \\
&=\frac{1}{N^2}\left(\frac{U(R_0)^2}{n}-\frac{n-1}{n}Q(R_0)\right)+\frac{r_{\max}^2}{n^2N^2}\sum_{s=0}^{n-2}(n-s-1)(2s+1).
\end{aligned} A PAI ≤ n N 2 1 U ( R 0 ) 2 − n 2 N 2 1 s = 0 ∑ n − 2 ( n − s − 1 ) ( 2 Q ( R 0 ) − ( 2 s + 1 ) r m a x 2 ) = N 2 1 ( n U ( R 0 ) 2 − n n − 1 Q ( R 0 ) ) + n 2 N 2 r m a x 2 s = 0 ∑ n − 2 ( n − s − 1 ) ( 2 s + 1 ) .
Working on the last summation, we have
∑ s = 0 n − 2 ( n − s − 1 ) ( 2 s + 1 ) = ∑ s = 0 n − 2 ( n − 1 ) ( 2 s + 1 ) − s ( 2 s + 1 ) = ( n − 1 ) ∑ s = 0 n − 2 ( 2 s + 1 ) − 2 ∑ s = 0 n − 2 s 2 − ∑ s = 0 n − 2 s = ( n − 1 ) 3 − ( 2 ∑ s = 0 n − 2 s 2 + ∑ s = 0 n − 2 s ) = n ( n − 1 ) ( 2 n − 1 ) 6 . \begin{aligned}
\sum_{s=0}^{n-2}(n-s-1)(2s+1)=\sum_{s=0}^{n-2}(n-1)(2s+1)-s(2s+1) \\
&=(n-1)\sum_{s=0}^{n-2}(2s+1)-2\sum_{s=0}^{n-2}s^2-\sum_{s=0}^{n-2}s=(n-1)^3-\left(2\sum_{s=0}^{n-2}s^2+\sum_{s=0}^{n-2}s\right)=\frac{n(n-1)(2n-1)}{6}.
\end{aligned} s = 0 ∑ n − 2 ( n − s − 1 ) ( 2 s + 1 ) = s = 0 ∑ n − 2 ( n − 1 ) ( 2 s + 1 ) − s ( 2 s + 1 ) = ( n − 1 ) s = 0 ∑ n − 2 ( 2 s + 1 ) − 2 s = 0 ∑ n − 2 s 2 − s = 0 ∑ n − 2 s = ( n − 1 ) 3 − ( 2 s = 0 ∑ n − 2 s 2 + s = 0 ∑ n − 2 s ) = 6 n ( n − 1 ) ( 2 n − 1 ) .
Thus, we conclude that
A P A I ≤ 1 N 2 ( U ( R 0 ) 2 n − n − 1 n Q ( R 0 ) ) + ( n − 1 ) ( 2 n − 1 ) r max 2 6 n N 2 = Var ( θ ^ a c t i v e ) + Q ( R 0 ) n N 2 + ( n − 1 ) ( 2 n − 1 ) r max 2 6 n N 2 . \begin{aligned}
A_{\mathrm{PAI}}\leq\frac{1}{N^2}\left(\frac{U(R_0)^2}{n}-\frac{n-1}{n}Q(R_0)\right)+\frac{(n-1)(2n-1)r_{\max}^2}{6nN^2} \\
&=\operatorname{Var}(\hat{\theta}_{\mathrm{active}})+\frac{Q(R_0)}{nN^2}+\frac{(n-1)(2n-1)r_{\max}^2}{6nN^2}.
\end{aligned} A PAI ≤ N 2 1 ( n U ( R 0 ) 2 − n n − 1 Q ( R 0 ) ) + 6 n N 2 ( n − 1 ) ( 2 n − 1 ) r m a x 2 = Var ( θ ^ active ) + n N 2 Q ( R 0 ) + 6 n N 2 ( n − 1 ) ( 2 n − 1 ) r m a x 2 .
Putting everything together, we deduce that
Var ( θ ^ a c t i v e ) + Q ( R 0 ) n N 2 ≤ A P A I ≤ Var ( θ ^ a c t i v e ) + Q ( R 0 ) n N 2 + ( n − 1 ) ( 2 n − 1 ) r max 2 6 n N 2 . \operatorname{Var}(\hat{\theta}_{\mathrm{active}})+\frac{Q(R_0)}{nN^2}\leq A_{\mathrm{PAI}}\leq\operatorname{Var}(\hat{\theta}_{\mathrm{active}})+\frac{Q(R_0)}{nN^2}+\frac{(n-1)(2n-1)r_{\max}^2}{6nN^2}. Var ( θ ^ active ) + n N 2 Q ( R 0 ) ≤ A PAI ≤ Var ( θ ^ active ) + n N 2 Q ( R 0 ) + 6 n N 2 ( n − 1 ) ( 2 n − 1 ) r m a x 2 .
which implies that
( 1 − b ˉ 2 ) ( Var ( θ ^ a c t i v e ) + Q ( R 0 ) n N 2 ) ≤ Var ( θ ^ P A I ) ≤ ( 1 − b ˉ 2 ) ( Var ( θ ^ a c t i v e ) + Q ( R 0 ) n N 2 + ( n − 1 ) ( 2 n − 1 ) r max 2 6 n N 2 ) , \begin{aligned}
(1-\bar{b}^2)\left(\operatorname{Var}(\hat{\theta}_{\mathrm{active}})+\frac{Q(R_0)}{nN^2}\right)\leq\operatorname{Var}(\hat{\theta}_{\mathrm{PAI}}) \\
&\leq(1-\bar{b}^2)\left(\operatorname{Var}(\hat{\theta}_{\mathrm{active}})+\frac{Q(R_0)}{nN^2}+\frac{(n-1)(2n-1)r_{\max}^2}{6nN^2}\right),
\end{aligned} ( 1 − b ˉ 2 ) ( Var ( θ ^ active ) + n N 2 Q ( R 0 ) ) ≤ Var ( θ ^ PAI ) ≤ ( 1 − b ˉ 2 ) ( Var ( θ ^ active ) + n N 2 Q ( R 0 ) + 6 n N 2 ( n − 1 ) ( 2 n − 1 ) r m a x 2 ) ,
or, more suggestively, recalling that (i) Q ( R 0 ) = ∑ i = 1 N ( y i − f ( x i ) ) 2 Q(R_0)=\sum_{i=1}^{N}(y_i-f(x_i))^2 Q ( R 0 ) = ∑ i = 1 N ( y i − f ( x i ) ) 2 ; (ii) r max = max i ∈ [ 1 : N ] ∣ y i − f ( x i ) ∣ r_{\max}=\max_{i\in[1:N]}|y_i-f(x_i)| r m a x = max i ∈ [ 1 : N ] ∣ y i − f ( x i ) ∣ ; and (iii) b ˉ 2 \bar{b}^2 b ˉ 2 is the weighted-average (squared) net signed direction of the residual mass over the n n n sampling rounds (c.f. Equation 26):
1 1 − b ˉ 2 ⋅ 1 1 + Q ( R 0 ) n N 2 Var ( θ ^ a c t i v e ) + ( n − 1 ) ( 2 n − 1 ) r max 2 6 n N 2 Var ( θ ^ a c t i v e ) ≤ Var ( θ ^ a c t i v e ) Var ( θ ^ P A I ) ≤ 1 1 − b ˉ 2 ⋅ 1 1 + Q ( R 0 ) n N 2 Var ( θ ^ a c t i v e ) . \frac{1}{1-\bar{b}^2}\cdot\frac{1}{1+\frac{Q(R_0)}{nN^2\operatorname{Var}(\hat{\theta}_{\mathrm{active}})}+\frac{(n-1)(2n-1)r_{\max}^2}{6nN^2\operatorname{Var}(\hat{\theta}_{\mathrm{active}})}}\leq\frac{\operatorname{Var}(\hat{\theta}_{\mathrm{active}})}{\operatorname{Var}(\hat{\theta}_{\mathrm{PAI}})}\leq\frac{1}{1-\bar{b}^2}\cdot\frac{1}{1+\frac{Q(R_0)}{nN^2\operatorname{Var}(\hat{\theta}_{\mathrm{active}})}}. 1 − b ˉ 2 1 ⋅ 1 + n N 2 Var ( θ ^ active ) Q ( R 0 ) + 6 n N 2 Var ( θ ^ active ) ( n − 1 ) ( 2 n − 1 ) r m a x 2 1 ≤ Var ( θ ^ PAI ) Var ( θ ^ active ) ≤ 1 − b ˉ 2 1 ⋅ 1 + n N 2 Var ( θ ^ active ) Q ( R 0 ) 1 .
or, with one final substitution of Var ( θ ^ a c t i v e ) = 1 N 2 ( U ( R 0 ) 2 n − Q ( R 0 ) ) \operatorname{Var}(\widehat{\theta}_{\mathrm{active}})=\frac{1}{N^2}\left(\frac{U(R_0)^2}{n}-Q(R_0)\right) Var ( θ active ) = N 2 1 ( n U ( R 0 ) 2 − Q ( R 0 ) ) ,
1 1 − b ˉ 2 ⋅ 1 1 + Q ( R 0 ) U ( R 0 ) 2 − n Q ( R 0 ) + ( n − 1 ) ( 2 n − 1 ) r max 2 6 ( U ( R 0 ) 2 − n Q ( R 0 ) ) ≤ Var ( θ ^ a c t i v e ) Var ( θ ^ P A I ) ≤ 1 1 − b ˉ 2 1 1 + Q ( R 0 ) U ( R 0 ) 2 − n Q ( R 0 ) . \frac{1}{1-\bar{b}^{2}}\cdot\frac{1}{1+\frac{Q(R_0)}{U(R_0)^2-nQ(R_0)}+\frac{(n-1)(2n-1)r_{\max}^{2}}{6(U(R_0)^2-nQ(R_0))}}\leq\frac{\operatorname{Var}(\widehat{\theta}_{\mathrm{active}})}{\operatorname{Var}(\widehat{\theta}_{\mathrm{PAI}})}\leq\frac{1}{1-\bar{b}^{2}}\frac{1}{1+\frac{Q(R_0)}{U(R_0)^2-nQ(R_0)}}. 1 − b ˉ 2 1 ⋅ 1 + U ( R 0 ) 2 − n Q ( R 0 ) Q ( R 0 ) + 6 ( U ( R 0 ) 2 − n Q ( R 0 )) ( n − 1 ) ( 2 n − 1 ) r m a x 2 1 ≤ Var ( θ PAI ) Var ( θ active ) ≤ 1 − b ˉ 2 1 1 + U ( R 0 ) 2 − n Q ( R 0 ) Q ( R 0 ) 1 .
Formally, when n r max / U ( R 0 ) → 0 nr_{\max}/U(R_0)\to0 n r m a x / U ( R 0 ) → 0 ,8 both remainder terms Q ( R 0 ) U ( R 0 ) 2 − n Q ( R 0 ) \frac{Q(R_0)}{U(R_0)^2-nQ(R_0)} U ( R 0 ) 2 − n Q ( R 0 ) Q ( R 0 ) and ( n − 1 ) ( 2 n − 1 ) r max 2 6 ( U ( R 0 ) 2 − n Q ( R 0 ) ) \frac{(n-1)(2n-1)r_{\max}^{2}}{6(U(R_0)^2-nQ(R_0))} 6 ( U ( R 0 ) 2 − n Q ( R 0 )) ( n − 1 ) ( 2 n − 1 ) r m a x 2 vanish asymptotically,9 yielding the following asymptotic relative-efficiency relationship:
Var ( θ ^ a c t i v e ) Var ( θ ^ P A I ) = 1 + o ( 1 ) 1 − b ˉ 2 . \frac{\operatorname{Var}(\widehat{\theta}_{\mathrm{active}})}{\operatorname{Var}(\widehat{\theta}_{\mathrm{PAI}})}=\frac{1+o(1)}{1-\bar{b}^{2}}. Var ( θ PAI ) Var ( θ active ) = 1 − b ˉ 2 1 + o ( 1 ) .
The sufficient condition above admits an intuitive decomposition:
n r max U ( R 0 ) = n N ⋅ r max r ˉ , where r ˉ : = 1 N U ( R 0 ) = 1 N ∑ i = 1 N ∣ y i − f ( x i ) ∣ . \frac{nr_{\max}}{U(R_0)}=\frac{n}{N}\cdot\frac{r_{\max}}{\bar{r}},\qquad\text{where }\bar{r}:=\frac{1}{N}U(R_0)=\frac{1}{N}\sum_{i=1}^{N}|y_i-f(x_i)|. U ( R 0 ) n r m a x = N n ⋅ r ˉ r m a x , where r ˉ := N 1 U ( R 0 ) = N 1 i = 1 ∑ N ∣ y i − f ( x i ) ∣.
Since r max ≥ r ˉ r_{\max}\geq\bar{r} r m a x ≥ r ˉ , this condition necessarily requires n / N → 0 n/N\to0 n / N → 0 , which is permitted by Theorem 1 . More precisely, the labeling fraction must vanish sufficiently quickly relative to r max / r ˉ r_{\max}/\bar{r} r m a x / r ˉ . In particular, n / N → 0 n/N\to0 n / N → 0 suffices if r max / r ˉ = O ( 1 ) r_{\max}/\bar{r}=O(1) r m a x / r ˉ = O ( 1 ) .
Diagonal stochastic Newton updates for online logistic regression
The following is adapted from Equations 3.1–3.3 of Bercu et al. [5 ] , who maintain a dense D × D D\times D D × D curvature matrix, whereas we use a diagonal approximation.
Let β t ∈ R D \beta_t\in\mathbb{R}^{D} β t ∈ R D denote our logistic regression coefficients at round t t t , and let h t ∈ R D h_t\in\mathbb{R}^{D} h t ∈ R D denote our accumulated diagonal curvature vector. For all datasets except for AlphaFold (which provides fixed probabilistic ML predictions without model access) and the two LLM evaluation suites MMLU-Pro and BBH+GPQA+IFEval+MATH+MusR, we initialize β 0 = β i n i t \beta_0=\beta_{\mathrm{init}} β 0 = β init by fitting on a training split of the data and initialize h 0 = 1 D h_0=\mathbf{1}_{D} h 0 = 1 D . For the two LLM evaluation suites, we use the historical-data regimen described in Wu et al. [27 ] : fitted question factors are held fixed, while β 0 \beta_0 β 0 and h 0 h_0 h 0 are initialized to the empirical mean and inverse marginal variances, respectively, of the historical LLMs’ fitted model factors. These initializations are identical across all new LLMs.
After observing ( x I t , y I t ) (x_{I_t},y_{I_t}) ( x I t , y I t ) , we compute
h t = h t − 1 + σ ( β t − 1 T x I t ) ( 1 − σ ( β t − 1 T x I t ) ) x I t ⊙ 2 , (27) h_t=h_{t-1}+\sigma\left(\beta_{t-1}^{\mathsf{T}}x_{I_t}\right)\left(1-\sigma\left(\beta_{t-1}^{\mathsf{T}}x_{I_t}\right)\right)x_{I_t}^{\odot2}, \tag*{(27)} h t = h t − 1 + σ ( β t − 1 T x I t ) ( 1 − σ ( β t − 1 T x I t ) ) x I t ⊙ 2 , (27)
β t = β t − 1 + ( y I t − σ ( β t − 1 T x I t ) ) x I t ⊘ h t , (28) \beta_t=\beta_{t-1}+\left(y_{I_t}-\sigma\left(\beta_{t-1}^{\mathsf{T}}x_{I_t}\right)\right)x_{I_t}\oslash h_t, \tag*{(28)} β t = β t − 1 + ( y I t − σ ( β t − 1 T x I t ) ) x I t ⊘ h t , (28)
where ⊙ 2 \odot2 ⊙ 2 represents elementwise squaring, and ⊘ \oslash ⊘ represents elementwise division.
Additional results
Figure 7. ESS multipliers of without-replacement PAI over with-replacement PAI across the two LLM evaluation suites. Each subplot shows the ESS multiplier of without-replacement PAI with respect to with-replacement PAI as a function of labeling budget. For example, on MMLU-Pro at a 22.5% budget, an ESS multiplier of 1.3 means that without-replacement PAI matches the confidence interval width of with-replacement PAI at a 29.25% budget. Standard errors are shown, but are negligible at the plotted scale. Higher ESS multipliers indicate better sampling efficiency, with values above 1 indicating that without-replacement PAI outperforms with-replacement PAI.
Figure 8. ESS multipliers of PAI and its frozen-ML ablation over PPI, PPAT, and uniform sampling across six datasets. Each row corresponds to one competitor (PPI, PPAT, or Uniform) and each column corresponds to one dataset. Each subplot shows the ESS multipliers of standard PAI (blue triangles) and frozen-ML PAI (red circles) with respect to the corresponding competitor method as a function of labeling budget. In the frozen-ML ablation, the initial ML model is held fixed throughout sampling, affecting both imputation and acquisition. The competing methods remain unchanged from their specifications in § 5 . Higher ESS multipliers indicate better sampling efficiency, with values above 1 indicating that the corresponding PAI variant outperforms the competitor.