ALSD: paper summary and package mapping

Overview

This vignette summarizes the ALSD method and maps the technical details to functions in the activesampling package. Abbreviations: ALSD = Adaptive Learning Sampling Design; RDD = Random-Digit Dialing.

Goal: adaptively set stratum-level selection probabilities to minimize the expected Kish design effect from weighting, increasing the effective sample size.
Strategies implemented:
- alsd_simple: match cumulative stratum shares to population shares.
- alsd_modelled: parameterize stratum selection probabilities with a logistic model and choose parameters to minimize expected design effect, subject to an expected-respondent budget constraint. Optimization uses ADAM by default.

ALSD balances exploration (learning response propensities) with exploitation (allocating to strata that reduce variance after weighting) under a fixed budget per wave. We use a smooth penalty to target the expected number of respondents in the next wave and optionally enforce it exactly via an intercept shift on the logit scale.

Notation and data structure

$H$ strata indexed by $h$ .
$N_h$ : population size in stratum $h$ . $\mathrm{pop\_pct}_h = N_h / \sum_h N_h$ .
$n_h^\omega$ : cumulative respondents so far in stratum $h$ ; $n_\omega = \sum_h n_h^\omega$ .
$u_h^\omega = N_h - n_h^\omega$ : available units for next wave (to first order), and $\pi_h$ : estimated response propensity among those units.
$X \in \mathbb{R}^{H\times K}$ : model matrix (e.g., one-hot indicators for strata); $\beta \in \mathbb{R}^K$ parameters.
Selection probability for next wave: $p_h(\beta) = \sigma(X_h\, \beta)$ , where $\sigma(z) = 1/(1+e^{-z})$ .
Expected respondents in next wave: $\mathrm{AS}(\beta) = \sum_h u_h^\omega\, \pi_h\, p_h(\beta)$ . Define $A_h = u_h^\omega\, \pi_h$ .

After the next wave, the expected total respondents is $S(\beta) = n_\omega + \mathrm{AS}(\beta)$ , and the expected respondents in stratum $h$ is $S_h(\beta) = n_h^\omega + A_h\, p_h(\beta)$ .

Objective: expected Kish design effect

Let $W_h(\beta)$ be the post-stratification “weight factor” comparing the population share to the expected sample share after the next wave:

$W_h(\beta) = \mathrm{pop\_pct}_h\, \frac{S(\beta)}{S_h(\beta)}.$

We approximate the Kish design effect for the next wave by

$\mathrm{D\_eff}(\beta) = 1 + \frac{1}{S(\beta)} \sum_h S_h(\beta)\, \bigl(W_h(\beta) - 1\bigr)^2.$

This is exactly what calculate_deff() computes given $(\beta, X, \mathrm{pop\_pct}, u_h^{\omega}, n_h^{\omega}, \pi_h)$ .

Constraint via penalty

We encourage hitting a target number $t$ for expected respondents in the next wave via a quadratic penalty:

$\mathcal{L}(\beta) = \mathrm{D\_eff}(\beta) + \lambda\,\bigl( \mathrm{AS}(\beta) - t \bigr)^2,$

where $\lambda > 0$ is a hyper-parameter. This matches objective_deff_constrained().

Gradient structure

For optimization we use the analytic gradient. Define:

$p_h(\beta) = \sigma(X_h\, \beta)$ , $K_h(\beta) = A_h\, p_h(\beta)\, [1 - p_h(\beta)]$ .
$S(\beta) = n_\omega + \sum_h A_h\, p_h(\beta)$ ; $S_h(\beta) = n_h^\omega + A_h\, p_h(\beta)$ .
$W_h(\beta) = \mathrm{pop\_pct}_h\, S(\beta)/S_h(\beta)$ .

Then calculate_deff_gradient() computes $\partial \mathrm{D\_eff} / \partial \beta_j$ via

$$ \frac{\partial\, \mathrm{D\_eff}}{\partial\, \beta_j} = -\frac{1}{S(\beta)^2}\,\Bigl(\sum_h K_h X_{h j}\Bigr)\, \sum_h S_h\,(W_h-1)^2\\ \quad + \frac{1}{S(\beta)} \sum_h \Bigl[ K_h X_{h j}\,(W_h-1)^2 + 2 (W_h-1)\, \mathrm{pop\_pct}_h\, \frac{ (\sum_{h'} K_{h'} X_{h' j}) S_h - K_h X_{h j} S }{S_h} \Bigr]. $$

The gradient of the penalty term is:

$\frac{\partial}{\partial\, \beta_j} \bigl\{ \lambda (\mathrm{AS}-t)^2 \bigr\} = 2\lambda\,(\mathrm{AS}-t)\, \sum_h K_h X_{h j}.$

gradient_deff_constrained() returns the sum of these two parts.

Algorithms

alsd_simple (greedy share matching):

Compute remaining availability $u_h^{\omega}$ and current respondent counts $n_h^{\omega}$ .
Allocate next-wave draws to move cumulative sample shares toward pop_pct_h, capped by remaining availability.
Sample and observe responses; update $n_h^{\omega}$ and $u_h^{\omega}$ ; repeat until budget.

alsd_modelled (gradient-based):

Build $X$ from strata indicators; initialize $\beta = 0$ .
Choose $\lambda$ and target $t$ (e.g., the wave’s expected respondents).
Minimize $\mathcal{L}(\beta)$ with ADAM using gradient_deff_constrained(); stop on convergence or max iters.
Set $p_h = \sigma(X_h\, \beta)$ , clip to [0,1], derive integer allocations by stratum with availability caps.
Sample and observe responses; update counts; repeat until budget.

See run_alsd_simulation() for both flows.

Package mapping

calculate_deff(beta, X, pop_pct, u_h_omega, n_h_omega, pi_h, ...): computes $D_\mathrm{eff}(\beta)$ .
calculate_deff_gradient(...): analytic $\Nabla D_\mathrm{eff}(\beta)$.
objective_deff_constrained(...), gradient_deff_constrained(...): penalized objective $L(\beta)$ and gradient.
run_alsd_simulation(...): wrapper that drives either alsd_simple or alsd_modelled across waves.

A minimal example

Consistency and small discrepancies

Our implementation follows the equations in the manuscript:

Expected design effect matches the Kish-based expression with stratum weights: $W_h(\beta) = \mathrm{pop\_pct}_h\, S(\beta)/S_h(\beta)$ and $\mathrm{D\_eff}(\beta) = 1 + [1/S(\beta)] \sum_h S_h(\beta) (W_h(\beta) - 1)^2$ , with analytic gradient identical to the derivation used in the legacy scripts.
The simple strategy uses $t_h^{\omega+1} = \mathrm{pop\_pct}_h\, (n_\omega + t^{\omega+1}) - n_h^{\omega}$ and converts this to stratum selection via $p_h \approx (t_h^{\omega+1}/\pi_h)/u_h^{\omega}$ , equivalent to the “response rate sampling” expression in the paper.
The constrained objective adds a quadratic penalty $\lambda(\mathrm{AS}(\beta) - t)^2$ with $\mathrm{AS}(\beta) = \sum_h u_h^{\omega} \, \pi_h \, p_h(\beta)$ ; in practice, we optionally enforce the target exactly via a final intercept shift on the logit scale (documented in the function reference).

Clarifications and minor differences:

Realized vs expected $D_\mathrm{eff}$ : during simulation logging we report a realized Kish design effect computed from respondents’ post-stratification weights (normalize to mean 1, then $D_\mathrm{eff} = \mathrm{mean}(w^2)$ ). The optimizer uses the expected $D_\mathrm{eff}$ formula above, as in the paper.
Estimation error shown in vignettes is the unweighted sample mean for simplicity; the manuscript discusses weighted estimators more broadly. We can add a weighted-estimator variant if desired.
Numerical safety: when $S_h(\beta)$ is near zero, we guard divisions using a small positive floor and clip probabilities to [0,1]. These do not change the objective’s intent, but avoid degenerate cases in tiny strata.

Alternative objective: cross-entropy. In addition to design-effect minimization, we also expose a cross-entropy/KL objective between population shares and the expected next-wave respondent shares. Select it via objective = “entropy” in run_alsd_simulation (or call calculate_entropy/objective_entropy_constrained directly). It uses the same budget penalty and an analytic gradient.

Notes, warnings, and planned features

Scope: This package refactors the original analysis scripts into a reusable tool. Some components in the original repo are exploratory and not ported verbatim.
Differences vs original scripts:
- Optimizer is optimg ADAM by default; no custom ADAM or Stan backends.
- Realized design effect reported here is Kish from post-strat weights with $\mathrm{mean}(w)=1$ ; some legacy plots show $\mathrm{var}(w)$ only.
- No raking step in simulation summaries; that’s deliberate to isolate the design-effect mechanics.
Planned:
- Weighted-estimator summaries as an option.
- Richer convergence diagnostics and early-stopping.
- Optional reporting of both $\mathrm{var}(w)$ and $1 + \mathrm{var}(w)$ in summaries for legacy comparability.

We run a tiny simulation on the included zimbabwe_minisample so the vignette renders quickly.

library(activesampling)
library(dplyr)

set.seed(1)
data(zimbabwe_minisample)

# Keep a small subset for a fast example
mini <- zimbabwe_minisample %>% slice(1:3000)

res <- run_alsd_simulation(
  population_df = mini,
  strata_vars   = c("gender", "region"),
  outcome_var   = "fcs_insuff_flag",
  method        = "alsd_modelled",   # uses ADAM by default
  initial_sample_size = 80,
  wave_size     = 40,
  total_budget  = 200,
  optimizer     = "adam"
)
#> 
#> --- Wave 1 ---
#> Respondents collected: 0/200
#> 
#> --- Wave 2 ---
#> Respondents collected: 90/200
#> 
#> --- Wave 3 ---
#> Respondents collected: 121/200
#> 
#> --- Wave 4 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 5 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 6 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 7 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 8 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 9 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 10 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 11 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 12 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 13 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 14 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 15 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 16 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 17 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 18 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 19 ---
#> Respondents collected: 156/200
#> 
#> --- Wave 20 ---
#> Respondents collected: 156/200
#> Termination reason: Reached maximum waves

head(res$summary)
#>   wave        method n_respondents y_estimate       error     deff varw
#> 1    1 alsd_modelled            90  0.1888889 -0.02611111 1.195729   NA
#> 2    2 alsd_modelled           121  0.1983471 -0.01665289 1.064193   NA
#> 3    3 alsd_modelled           156  0.1987179 -0.01628205 1.037166   NA
#> 4    4 alsd_modelled           156  0.1987179 -0.01628205 1.037166   NA
#> 5    5 alsd_modelled           156  0.1987179 -0.01628205 1.037166   NA
#> 6    6 alsd_modelled           156  0.1987179 -0.01628205 1.037166   NA
#>   y_estimate_weighted error_weighted
#> 1                  NA             NA
#> 2                  NA             NA
#> 3                  NA             NA
#> 4                  NA             NA
#> 5                  NA             NA
#> 6                  NA             NA

The summary data frame reports, by wave, the cumulative number of respondents, the current outcome estimate and error vs. the true mean in the simulation, and the current expected design effect from weights.

Practical notes

Response propensity modelling uses a simple logistic regression on stratum labels with a safe fallback when only one level is present.
Selection probabilities are clipped to [0, 1]; integer sample sizes are derived per stratum and limited by remaining unsampled units.
The optimizer defaults to ADAM via optimg. You can set optimizer = "bfgs" to use stats::optim instead.
To enforce the next-wave respondent target exactly, set enforce_target = TRUE in run_alsd_simulation, which applies a post-optimization intercept shift to match the expected respondents.

Motivation and discussion

Minimizing expected Kish design effect targets variance inflation from weighting, thereby increasing effective sample size n_eff.
A quadratic penalty for the expected-respondents target t provides a smooth trade-off between balance and progress toward the budget, avoiding brittle hard constraints.
The logistic parameterization ensures valid selection probabilities in (0,1) and a smooth surface for gradient methods.

Link to DDC and cost-aware extensions

Data Defect Correlation (DDC): Under the decomposition in Meng (2018), the absolute error of a weighted mean can be written as $\lvert\mathrm{error}\rvert \approx \lvert\rho_{G, R_w}\rvert \times \sqrt{N/n_w - 1} \times \sigma_G$ . For a fixed outcome scale and budget, reducing the variance inflation from weights (captured by $\mathrm{D\_eff}$ ) reduces the $\sqrt{N/n_w - 1}$ factor via increased effective $n$ , and tends to lower the overall error even when modest residual correlation remains. Our focus on expected Kish $\mathrm{D\_eff}$ is thus aligned with controlling the DDC term’s impact on error.
Costs: Some ALSD variants may include heterogeneous per-complete costs $c_h$ . A practical extension replaces the respondent-target penalty with a cost penalty (or constraint), e.g., $\lambda_{\text{cost}}\,\bigl(\sum_h c_h A_h p_h - \mathrm{budget}_{\text{wave}}\bigr)^2$ . This is a drop-in change to objective_deff_constrained() and gradient_deff_constrained() with $A_h$ unchanged and an extra linear form in $p_h(\beta)$ added to the penalty and its gradient. We keep the default implementation cost-neutral but the interface allows easy adaptation via the penalty term.

Hyperparameters and convergence

Penalty weight $\lambda$ : start with $\lambda \approx 1.0$ and adjust so that $AS(\hat{\beta})$ is close to $t$ ; larger $\lambda$ enforces the target more tightly but can slow convergence. In practice, we found values in $[0.5, 5]$ adequate for typical wave sizes.
Step/iterations: ADAM uses its internal step-size schedule; maxit = 200 usually suffices. If the design effect plateaus but $AS(\beta)$ misses $t$ appreciably, slightly increase $\lambda$ and re-optimize from the current $\beta$ .
Stopping: use either a gradient-norm or relative objective change criterion. The default optimg settings with maxit act as a safe cap; in our routines we also clip probabilities to [0,1] after optimization for numerical safety.

What’s missing (roadmap)

Weighted estimators in summaries: Report both unweighted and post-stratified (or raked) estimates and errors by wave.
Diagnostics: Surface convergence stats (objective trace, gradient norm) and per-stratum p_h, with simple stop criteria toggles.
Dual D_eff reporting: Optionally log var(w) in addition to Kish D_eff = mean(w^2) for easier comparison to some legacy plots.
Cost-aware extensions: Support heterogeneous per-complete costs via a cost-penalty or constraint in the objective wiring.
Reproducibility knobs: Expose seeds and optimizer hyperparameters more explicitly in the top-level API.

References

Kish, L. (1965). Survey Sampling. John Wiley & Sons.
Meng, X.-L. (2018). Statistical paradises and paradoxes in big data (I). Annals of Applied Statistics.

Notation-to-code mapping

$A_h = u_h^\omega\, \pi_h$ → pass as u_h_omega and pi_h; products are formed internally.
$\mathrm{pop\_pct}_h$ → pop_pct vector.
$X$ and $\beta$ → X via model.matrix(~h, data = pop_frame), beta optimized.
$p_h(\beta) = \sigma(X_h\beta)$ → computed internally via sigmoid.
$S_h(\beta), S(\beta), W_h(\beta)$ → derived inside objective/gradient functions.
Penalty target $t$ → t_omega_1; weight $\lambda$ → lambda.

The ALSD authors