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.
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.