Variance reduction techniques improve the efficiency of drawing conclusions from data. Recent proposals for variance-reduction use two complementary techniques to reduce variance: incorporating machine learning predictions into estimators and weighted sampling. A popular weighted sampling algorithm is Poisson Sampling (PS), which independently flips a biased coin at each unit and includes all heads in the sample. A fundamental flaw with PS is that it has a random sample size, which presents practical challenges and introduces variance into the estimator. We show that a fixed-size alternative, known in survey sampling as Conditional Poisson Sampling (CPS), is a drop-in replacement for PS on general multivariate Z-estimation problems, which include convex M-estimation considered in prior work. Notably, we show that the asymptotic variance of CPS is no worse than that of PS, and can be substantially better in realistic scenarios where predictions are imperfect. We illustrate these advantages on both synthetic and real datasets, and release a Python package implementing CPS. In light of our contributions, there is no need to suffer a variable sample size.
Figures & tables
RMSE vs.
E [width] vs.
Dataset
f bias
SRS
PS
SRS
PS
CPS cov.
Synthetic DGP0, HT
–
−1% †
−.2% †
−.1%
−.1% †
0.899
Synthetic DGP1, HT
–
−1% †
−26%
−.1%
−26%
0.899
Synthetic DGP0, flin , DE
–
−.7% †
+.9% †
+.1% †
0% †
0.899
Synthetic DGP0, fbias , DE
–
−.7% †
−30%
+.1% †
−29%
0.899
Pew-Biden, shifted f
+35%
−11%
−16%
−12%
−17%
0.890
Table 1: For every experiment, we report the percent change in RMSE and expected CI width for CPS against SRS and PS, with † indicating when a difference is not significant (within 2× Monte Carlo SE of 0 with paired seed bootstrap). CPS is not significantly worse than PS on any dataset, and beats SRS on all but “Pew-Trump, shifted f ” because the policy π depends on the heavily biased f . We report RMSE to show that the expected width comparison is not an artifact of variance estimation, and we report coverage to show similarly that CPS has coverage approximately at the target of 0.9 on all datasets. We report the bias of f to show that it approximately tracks the degree of improvement of CPS over PS, and that SRS beats CPS when it is too large.
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
N
n
CPS build (s)
PS draw (ms)
CPS draw (ms)
SAIPE AL
26,607
1000
2.42
1.05
1.89
SAIPE OR
25,186
1000
1.95
0.93
0.60
SAIPE MA
45,372
1000
3.46
1.61
1.69
SAIPE TX
157,386
1000
8.68
5.54
9.40
Census
190,046
1000
16.82
7.22
10.95
Pew-Biden
6,189
1000
0.38
0.29
0.11
Appendix
Table 2: Runtime of PS vs. CPS per experiment. π is a shared input and is not timed. PS has no build step; the CPS build time is the π→p solve plus the table fill, averaged over 5 cold runs (cache wiped each run). Times are wall-clock on a single machine.
Figure 1: PS variance is inflated when the residuals have non-zero mean—either from a non-zero population mean (left) or a biased predictor (right).
Figure 2: Expected width of confidence intervals (CIs) as a function of sample size budget for SRS, PS, and CPS on the Pew dataset. Solid lines show the original predictor f , and dotted lines show the logit-shifted fbias , with b=3 . For the original f , CPS and PS have comparable widths, lower than SRS. For the biased f on Biden, CPS has narrower CIs than SRS, which in turn is narrower than PS. For the biased f on Trump, CPS still dominates PS, but both are worse than SRS.
Figure 3: Expected width of confidence intervals as a function of the budget n for SRS, PS, and CPS on SAIPE, where f is trained on California and deployed in each target state. CPS is narrower than PS at every budget in Alabama and Oregon, the two states where f is most biased, and CPS and PS are close in Massachusetts and Texas. Both weighted designs are narrower than SRS in every state.
RMSE vs.
E [width] vs.
Target
f bias
SRS
PS
SRS
PS
CPS cov.
AL
+29%
−15%
−3%
−16%
−4%
0.894
OR
+23%
−15%
−4%
−15%
−3%
0.899
MA
+8%
−15%
−.6% †
−15%
−.2% †
0.897
TX
+14%
−15%
+.4% †
−16%
−1%
0.891
Appendix
Table 3: SAIPE experiment where f is trained on CA and used to design a sample and estimate the mean in a different state. The two states with the highest bias show a significant advantage of CPS over PS and SRS in both RMSE and expected width, which aligns with the prediction of Corollary 2 . Cells are averaged over budgets and indicated with a † when a difference is not significant. We also note that the coverage of CPS is close to the target 0.90 , and that the RMSE results show that the difference in expected width is not an artifact of variance estimation.
Algorithm
n=300
500
700
1000
Algorithm
n=300
500
700
1000
AlphaFold
Census
SRS
1.47
1.10
.91
.75
SRS
445
353
300
251
PS
1.37
1.03
.84
.68
PS
262
205
174
146
CPS
1.37
1.03
.84
.67
CPS
259
202
171
143
Pew (Biden)
Pew (Trump)
SRS
.06
.05
.04
.03
SRS
.06
.04
.04
.03
Appendix
Table 4: Expected confidence interval (CI) width on the datasets from ASI [ Zrnic and Candès, 2024 ] . Smaller widths are better. For each dataset, we compare SRS, PS, and CPS using DE and the inclusion probabilities of Zrnic and Candès [2024] described in Section C.1.4 . Coverage is similar across all methods (see Section C.3 ). Notably, PS and CPS have near-identical expected widths, which the theory predicts when v=\mathdsEm[w⋆(1−π⋆)] is small (see Section 4.2 ). This holds even for Census, where f is biased in the mean ( Table 1 ): v weights the residuals w⋆ by 1−π⋆ , so a bias in the mean of Y need not make v large.
Dataset
Method
E[v^]/MCvar
CI width / SRS
Coverage
Synthetic DGP0, HT
SRS
0.99
1.00
0.89
PS
1.00
1.00
0.90
CPS
1.00
1.00
0.90
Synthetic DGP1, HT
SRS
0.99
1.00
0.89
PS
1.02
1.35
0.90
CPS
1.00
1.00
0.90
Appendix
Table 5: Quality of the design-based variance estimators. For each dataset and design: the ratio of the average estimated variance to the Monte Carlo variance of the point estimate over 5000 seeds, the expected CI width relative to SRS, and the empirical coverage of nominal 90% intervals. All ratios are close to 1 and all coverages are close to 0.90 (with slight undercoverage on AlphaFold for PS and CPS, and on Census for SRS), so comparing designs by RMSE and expected CI width is valid.
Algorithm
n=300
n=500
n=700
n=1000
AlphaFold
SRS
0.90
0.90
0.90
0.89
PS
0.85
0.87
0.89
0.89
CPS
0.84
0.86
0.88
0.89
Census
SRS
0.86
0.87
0.88
0.88
Appendix
Table 6: Empirical coverage of nominal 90% confidence intervals for SRS, PS, and CPS on the datasets from ASI.
Algorithm
n=300
n=500
n=700
n=1000
AlphaFold
SRS
0
0
0
0
PS
278
443
602
804
CPS
0
0
0
0
Census
SRS
0
0
0
0
Appendix
Table 7: Variance of the realized sample size n~ (zero for SRS and CPS by design). Under PS, the exact variance is ∑iπi(1−πi)<n . The Census entries slightly exceed n , which we attribute to Monte Carlo error over the seeds.
Figure 4: Two sources of randomness in the joint design–model framework formalized in Definition 10 . A realization ω∈Ω determines an i.i.d. super-population sequence; truncating to the first N elements yields the finite population DN(ω) (red box). Conditional on this finite population, the sampling design pN draws a random sample s of size n (blue box; selected units shown filled), where the selection may depend on the auxiliary information ZN(ω) .
Variance reduction develops methods that make Monte Carlo estimates, gradients, and experimental comparisons more precise with limited data or computation.
Silicon sampling can produce surprisingly good population estimates at times. Does doing it fast attenuate such fidelity? In this study, we extend and assess ongoing work in silicon sampling by comparing the algorithmic fidelity of "fast" and "slow" modes of silicon sampling among a nationally representative sample of Singaporean survey respondents. We find that silicon sampling with contemporary frontier models remains a method in early development to be used only with great caution. While silicon samples are able to produce moderately faithful estimates of population means, they continue to understate opinion variance and distort the latent contextual space behind human opinions. Conditional on such limitations, we find "fast" modes of silicon sampling to be relatively superior to traditional "slow" modes of silicon sampling. Fast silicon sampling is significantly more efficient in compute resources and run-time while being monotonically superior to slower modes of sampling in algorithmic fidelity.
Population-based adaptive importance sampling (AIS) methods use a set of proposal densities to approximate complex target distributions. Their performance is commonly assessed through effective sample size (ESS) and related weight-based diagnostics, which measure the concentration of normalized importance weights. However, a large ESS only indicates that the normalized sample weights are not strongly concentrated; it does not describe how the proposal components are arranged in the sampling space. In population-based AIS, several proposal components may generate samples in the same region of the target, so the sample weights can appear well balanced even though the effective number of distinct proposal components is small. This letter introduces the effective number of proposals (ENP), a similarity-aware proposal-level diagnostic for population-based AIS. ENP combines the total normalized weight assigned to each proposal with a redundancy measure computed from similarities among target-weighted samples, estimating the number of non-redundant empirical proposal contributions to the approximation. We establish basic effective-number properties and show that ENP detects proposal collapse and duplication missed by standard ESS. We also illustrate its use as a targeted feedback signal for proposal rejuvenation.
Ali Mousavi, Victor Elvira
Department of Computer Engineering, Islamic Azad University, Neyshabur Branch, Neyshabur, Iran · School of Mathematics, University of Edinburgh, United Kingdom
Sampling from high-dimensional, non-log-concave distributions with unnormalized densities is a fundamental challenge in machine learning, particularly when the exact gradient of the potential is unavailable and must be approximated via stochastic gradients that exhibit high variance under a fixed budget of gradient computations per iteration. Although variance reduction techniques such as SGD with momentum, STORM, and PAGE have demonstrated improved convergence properties in non-convex optimization, their implications for sampling from non-log-concave distributions remain largely unexplored. In this work, we develop the first unified analysis of these estimators for sampling from non-log-concave distributions. We establish improved non-asymptotic convergence rates in ε-relative Fisher information and, under a Poincaré inequality assumption, in squared total variation distance, and further prove weak convergence to the target distribution. We extend our analysis to solving inverse problems with score-based generative priors. We empirically validate our theory and demonstrate that, under a fixed gradient computations per iteration, variance-reduction techniques consistently improve sample quality in two standard imaging applications.
M. Berk Sahin, Ahmet Ege Tanriverdi, Behzad Sharif +1
School of Electrical and Computer Engineering, Purdue University, West Lafayette, Indiana, USA · School of Electrical and Computer Engineering, University of Southern California, California, USA · School of Biomedical Engineering, Purdue University, West Lafayette, Indiana, USA