A Fixed, Covariate-Balanced Design via Greedy Pairwise-Swap Search
Source:R/design_fixed_greedy.R
DesignFixedGreedy.RdA fixed-sample-size DesignFixed that searches, among
balanced (\(n/2\)-treated) allocations, for one that directly minimizes a covariate
imbalance criterion \(f(d)\), \(d = M(2w - 1)\), via a native C++ (RcppEigen +
OpenMP) greedy pairwise-swap search (greedy_design_search_cpp()). Unlike
DesignFixedGreedyDOptimal, which optimizes a
model-based information-matrix criterion (D-/A-optimality) implied by an assumed
linear model, this design optimizes a direct covariate-distance criterion between the
treated and control group means/covariance, with no linear-model assumption: the two
supported objectives are
"mahal_dist"(default): \(d = L^{-1} X^\top (2w-1) / n\) where \(\Sigma = LL^\top\) is the Cholesky factor of the covariate covariance matrix, and \(f(d) = \lVert d \rVert_2^2\) — the squared Mahalanobis distance between the treated and control covariate means, accounting for covariate correlation/scale. Falls back to"abs_sum_diff"if the covariate covariance matrix is (numerically) singular, since the Cholesky factorization then fails."abs_sum_diff": \(d = X_{\mathrm{std}}^\top (2w-1) / n\) (covariates standardized to unit variance, no correlation adjustment) and \(f(d) = \lVert d \rVert_1\) — the sum of absolute standardized mean differences across covariates.
Search algorithm. Starting from a random balanced (Fisher-Yates) allocation,
the search runs in one of two modes selected by n_iter: Inf (default)
runs exhaustive best-improvement search — each round scans every
(treated, control) pair, applies the single globally best improving swap, and repeats
until no swap improves \(f(d)\), guaranteeing convergence to a strict local optimum;
a positive integer instead runs exactly that many stochastic steps, each
picking a uniformly random (treated, control) pair and accepting the swap only if it
improves \(f(d)\) (with patience-based early stopping). r independent design
searches (one per requested replicate) run in parallel via OpenMP, each with its own
std::mt19937 generator. This search's
randomization is reproducible via the constructor's seed argument: per-thread
RNGs are seeded from R's own RNG state (GetRNGstate()/unif_rand())
before the parallel region begins, so private$maybe_set_seed() does govern the
resulting allocation, independent of the number of OpenMP threads used.
Same draws as DesignFixedGreedyDOptimal
at the defaults. With objective = "mahal_dist" and n_iter = Inf (the
defaults), this class returns exactly the same allocations as
DesignFixedGreedyDOptimal with its defaults (objective = "D", no
prior_precision) for the same seed. Despite the "no linear-model assumption"
framing above, the default criterion coincides with D-optimality: with the number of
treated subjects fixed, the information about the treatment effect in the linear model
\(y = \beta_T w + \beta_0 + X \gamma + \epsilon\) equals a constant minus a positive
multiple of the squared Mahalanobis distance between the treated and control
covariate means. Both criteria therefore rank every allocation the same way, and the
same swap search from the same starting allocation reaches the same allocation (the
derivation is in DesignFixedGreedyDOptimal's documentation). The draws differ
when this class uses objective = "abs_sum_diff", a finite n_iter, or the
"abs_sum_diff" fallback after a failed Cholesky factorization, and when
DesignFixedGreedyDOptimal uses an unequal prob_T (which this class
does not support), objective = "A" with interest = "all" or a covariate
subset, or a prior_precision.
Constraints and fallbacks. Only exactly balanced allocation
(prob_T = 0.5, \(n\) even) is supported; the constructor errors otherwise. If
no covariates are available, the search degenerates to pure balanced Fisher-Yates
randomization (no swap search, since there is nothing to balance on).
greedy_design_search_cpp()'s output is trusted unvalidated – it guarantees
exactly n x r valid \(\{0,1\}\) columns with \(n/2\) treated subjects per
column by construction (see fix_design_hierarchy.md, "AllocationMatrixValidation").
References
Krieger, A. M., Azriel, D., and Kapelner, A. (2019). "Nearly random designs with greatly improved balance." Biometrika, 106(3), 695-701, doi:10.1093/biomet/asz026 , for the greedy-swap balance-optimization approach this class implements. See also Mahalanobis distance for orientation on the default objective.
Super classes
Design -> DesignFixed -> DesignFixedGreedy
Methods
+ inherited public methods from DesignFixed
+ inherited public methods from Design
Design$add_one_subject_response()Design$any_censoring()Design$applicable_inference_class_names()Design$assert_all_responses_recorded()Design$assert_all_subjects_arrived()Design$assert_even_allocation()Design$assert_fixed_sample()Design$capabilities()Design$check_experiment_completed()Design$draw_ws_according_to_design()Design$duplicate()Design$get_X()Design$get_X_imp()Design$get_X_raw()Design$get_design_formula()Design$get_edi_version_created()Design$get_effective_dead()Design$get_effective_time()Design$get_missingness_method()Design$get_n()Design$get_ordinal_levels()Design$get_original_ordinal_levels()Design$get_prob_T()Design$get_response_type()Design$get_response_type_original()Design$get_t()Design$get_w()Design$get_y()Design$get_y_L()Design$get_y_R()Design$get_y_original()Design$has_general_censoring()Design$incompatible_inference_classes_due_to_design_structure()Design$is_a_bernoulli_capable()Design$is_a_cluster_capable()Design$is_a_kk_matching_capable()Design$is_blocking_design()Design$is_fixed_sample_size()Design$is_matching_design()Design$prepare_for_resampling_replay()Design$randomization_family()Design$supports()Design$supports_randomization_draw()Design$supports_resampling()Design$supports_resampling_replay()Design$transform_y()Design$unavailable_inference_classes_due_to_missing_packages()Design$warm_all_subject_data_cache()
DesignFixedGreedy$new()
Initialize a greedy pairwise-swap search fixed experimental
design. Only prob_T = 0.5 is supported (see class documentation).
Usage
DesignFixedGreedy$new(
response_type,
prob_T = 0.5,
objective = "mahal_dist",
n_iter = Inf,
include_is_missing_as_a_new_feature = TRUE,
n = NULL,
verbose = FALSE,
missingness_method = "impute",
design_formula = ~.,
seed = NULL
)Arguments
response_typeThe data type of response values.
prob_TThe probability of the treatment assignment. Must be 0.5.
objectiveThe covariate-imbalance objective to minimize: either
"mahal_dist"(default, squared Mahalanobis distance between treated and control covariate means) or"abs_sum_diff"(sum of absolute standardized mean differences); see class documentation for the exact criteria.n_iterNumber of swap iterations.
Inf(default) uses exhaustive best-improvement search guaranteed to reach a strict local optimum. A positive integer runs that many stochastic random-pair iterations with patience-based early stopping.include_is_missing_as_a_new_featureFlag for missingness indicators.
nThe sample size.
verboseFlag for verbosity.
missingness_methodHow to handle missing values in covariates.
design_formulaA formula object.
seedInteger seed for reproducibility. This design's search is reproducible via
seed(see class documentation).
DesignFixedGreedy$supports_batch_w_pregeneration()
Returns TRUE so the calling framework pre-generates all
replicate w vectors for a simulation cell in a single batched call
to greedy_design_search_cpp() (which parallelizes the r
independent searches over OpenMP threads internally), rather than issuing
r separate single-replicate C++ calls.