Imputation Draws as a Search Budget in AutoML

Automated machine learning (AutoML) systems search over whole prediction pipelines: how to fill in missing values, how to transform features, which model to fit, and with what settings. In current systems the first step is nearly an afterthought. Auto-sklearn fills a missing cell with the column mean, median, or mode and treats that choice as a fixed switch. The statistics literature does something richer. Multiple imputation fills each missing cell several times, drawing each fill from a model of the plausible values, so that the spread across the completed datasets shows how much the missing data could change the answer. This proposal puts multiple imputation inside the AutoML search loop. The completed datasets are not a fixed preprocessing cost. They act as a budget the search spends selectively. A candidate pipeline is first scored on one imputed copy of the data, and further copies are bought only when the scores are close enough that imputation noise could reverse the ranking. The pipeline that wins is deployed as an average of its predictions across the imputed copies.

This matters because the evidence on whether careful imputation helps prediction is mixed. In one benchmark, the best imputer depended strongly on the downstream model, yet plain mean substitution often won on F1. In another, an MLP that simply fills missing values with zero matched elaborate methods that learn imputation and prediction together. Both findings came from settings that did not tune the imputer jointly with the model. Neither treated imputation uncertainty as something a search procedure should reason about. The aim here is to build the missing piece and to report honestly, regime by regime, when it beats the trivial alternatives.

Core Claim

Our main claim is about how to search, not about using a better imputer. AutoML on incomplete tabular data should treat the number of stochastic imputation draws as a second fidelity axis, alongside the usual axis of how much training data or how many iterations a candidate gets. Promotion decisions should use the between-draw variance that multiple imputation already estimates. Formally, after $k$ imputation draws a candidate configuration $\lambda$ has mean validation score $\bar s_k(\lambda)$, average within-draw variance $W_k(\lambda)$ from cross-validation folds, and between-draw variance $B_k(\lambda)$. These are combined with the standard multiple-imputation pooling rule into a total uncertainty:

$$T_k(\lambda) = W_k(\lambda) + \left(1 + \tfrac{1}{k}\right) B_k(\lambda).$$

The search either eliminates $\lambda$ or buys it another draw, based on whether $\bar s_k(\lambda) + c\sqrt{T_k(\lambda)}$ still reaches the incumbent's score. Here $c$ is a confidence multiplier. The $(1+1/k)$ factor comes from the usual multiple-imputation correction for estimating the mean from finitely many draws.

We make two predictions that can be tested. First, under a fixed compute budget, this adaptive scheme should find better pipelines than spending the same budget on one draw per candidate or on a fixed five draws per candidate. Second, averaging the final predictions across draws should improve calibration more than it improves ranking metrics, and more than an equal number of bootstrap refits would.

Relation to Prior Work

Three lines of work motivate the gap. Efficient and Robust Automated Machine Learning defines the joint search over algorithm choice and hyperparameters, using model-based Bayesian optimization, warm starts from past datasets, and ensemble selection. Its data preprocessing covers only four elementary operations, and missing values get single deterministic fills. Auto-Sklearn 2.0: The Next Generation replaces the warm-start step with a fixed portfolio of configurations plus successive halving, a budget-allocation scheme that stops weak candidates early on small data subsets. It keeps the same imputation primitives and treats a dataset with heavy missingness the same as a complete dataset of equal size. We reuse its successive-halving machinery as the method backbone and add a new fidelity axis to it. Does imputation matter? Benchmark for predictive models crosses seven imputers with five models on 13 OpenML datasets. It finds strong pairings, for example chained-equation imputation (MICE) with random forests and XGBoost, and hot-deck imputation ranking best for XGBoost. It uses default hyperparameters throughout and imputes training and test sets separately. We run its pairing question with joint tuning and with imputers fitted inside each cross-validation fold.

Two papers constrain the design. In Defense of Zero Imputation for Tabular Deep Learning shows that zero filling, with or without missing-value indicator columns, matches NeuMiss, SupMIWAE, and GRAPE on six OpenML datasets. That result warns that learned imputation may add only noise, so zero filling with indicators is a required baseline and a required search-space option. Correlation visualization under missing values: a comparison between imputation and direct parameter estimation methods shows that low reconstruction error does not imply preserved correlations. For this reason the search will never score imputers by reconstruction error, only by downstream validation performance. Prediction-based Inference in Electronic Health Record (EHR)-linked Biobanks shows that plugging in machine-learning imputations without accounting for their uncertainty can drive Type I error to 100%, and that validity fails when data are missing not at random. Its setting is inference on a single outcome, but it motivates carrying between-draw variance through the search rather than discarding it.

The closest system is TARImpute: Task-Aware Auto-Recommender System for Missing Value Imputation Algorithms with Clustering Case Studies. It recommends an imputer for a downstream task, but it covers clustering only, selects a single imputation, and does no supervised pipeline search. We differ on all three points.

The joint parameter optimization literature supplies one methodological question rather than a method. Wireless systems such as Delay-Constrained Joint Power Control, User Detection and Passive Beamforming in Intelligent Reflecting Surface-Assisted Uplink mmWave System and Optimization in Mobile Augmented Reality Systems for the Metaverse Over Wireless Communications solve coupled problems by block coordinate descent: they alternate between parameter blocks, each solved with the others held fixed. The value of joint search depends on how strongly the blocks are coupled. We measure that coupling directly for the imputer block and the model block, instead of assuming it.

Research Program

We will build the system on the Auto-sklearn 2.0 code path. The imputation stage becomes a searched component with several options. These are zero or constant filling with indicator columns, mean or mode filling, k-nearest-neighbor imputation with its neighbor count and weighting, hot-deck imputation, missForest-style chained random forests with depth and iteration count, and MICE with predictive mean matching (filling a missing cell with an observed value from a similar row) with its iteration count and ridge penalty. Every stochastic imputer exposes a draw index. Imputers are fitted inside each training fold and applied to the validation fold, so the leakage problem in the earlier benchmark is removed by construction.

Successive halving runs over a two-dimensional budget, data fraction and imputation draws. Promotion follows the pooled-uncertainty rule above. Deterministic imputers have zero between-draw variance and therefore never buy extra draws, so the scheme spends draws only where imputation uncertainty exists. At deployment, the selected pipeline is refit on each of its $k$ draws and the predicted probabilities are averaged. These per-draw fits are also offered to ensemble selection as separate members.

A separate analysis estimates coupling between the imputer and the model. On each dataset we compare three procedures at equal budget. The first tunes the imputer with a default model and then tunes the model, which is the sequential approach. The second alternates between the two blocks, as in block coordinate descent. The third searches both blocks jointly. The gap between the sequential and joint results measures how much coupling exists. We will relate that gap to the missingness rate, the missingness mechanism, and the model family.

Baselines

The naive reference is mean or mode imputation followed by a default random forest. It costs almost nothing, and Does imputation matter? Benchmark for predictive models found mean substitution frequently top-ranked on F1. It runs on the same folds with no search. Any method that fails to beat it on F1 in a given regime has no case there.

The second baseline is zero filling with missing indicators, followed by a tuned estimator. It is selected from a tuned random forest, gradient boosting, and an MLP, and receives the same tuning budget as our system. It is the strongest cheap competitor according to In Defense of Zero Imputation for Tabular Deep Learning. AMLB: an AutoML Benchmark also reports that a tuned random forest often beats AutoML tools under short budgets.

The strongest existing AutoML systems are unmodified Auto-sklearn 2.0 and AutoGluon. AMLB reports that AutoGluon consistently achieves the highest accuracy through stacking. For AutoGluon on incomplete-data tasks specifically, no reported result was found on Lacuna. For Auto-sklearn 2.0, the cited figure is a reduction in relative error "up to a factor of 4.5" over Auto-sklearn 1.0 (Auto-Sklearn 2.0: The Next Generation), but that figure is not specific to missing data. Both systems run with identical wall-clock limits, CPU cores, memory, and outer folds. Beating them means a better mean rank in AUC or log loss across the suite, with a Wilcoxon signed-rank test significant at 0.05. A tie in AUC with lower log loss and no inference-latency penalty larger than AutoGluon's would count as a qualified win.

Three ablations isolate the key ingredient. The first, plain inclusion, gives the same enlarged imputer space with one draw per candidate, which is what anyone would build first. The second gives the same space with a fixed five draws. The third keeps adaptive draws but replaces the final cross-draw average with bootstrap bagging of a single imputation, using the same number of model fits. Our system must beat the first and second at equal budget and beat the third on calibration. If it fails, the core claim is false.

Why not just…?

Why not just use zero imputation with missing indicators? This alternative is a real threat. Van Ness et al. found it competitive with jointly trained deep imputers. Under missingness that depends on the unobserved values, the indicator columns may carry most of the signal. That evidence comes only from MLPs, though, and the benchmark of Does imputation matter? shows tree models preferring specific learned imputers. Our search space includes zero filling with indicators as an option, so the system can choose it. The regime analysis will report where it chooses zero filling and whether the independently run zero-filling baseline ties our system there. A tie across all regimes would be a publishable negative result.

Why not just add MICE as one more option in Auto-sklearn? This is the plain-inclusion ablation, and it may capture most of the gain. If one draw per candidate matches adaptive draws at equal budget, then the draw-as-fidelity idea adds nothing. We would then report the simpler system as the recommendation.

Why not just rely on stacking and bagging, since cross-draw averaging is just another ensemble? Averaging across imputations reduces prediction variance, and AutoGluon's stacking already does that well. The bootstrap-matched ablation separates the two effects. Imputation averaging differs from bagging in that it varies only the missing cells. We therefore expect its advantage to show up in calibration on rows with many missing entries. The evaluation will stratify log loss and expected calibration error by the fraction of missing cells in each row. If the advantage does not appear there, the averaging step should be dropped.

Proposed Experiments

The datasets are the 13 OpenML100 datasets from Does imputation matter?, which allows a direct comparison with its default-hyperparameter results. We add the six OpenML datasets from the zero-imputation paper (higgs, miniboone, philippine, christine, phoneme, volkert), with missingness induced completely at random at probability 0.5 as in that paper. Each of those datasets also gets two additional variants: missingness that depends on observed features, and missingness that depends on the unobserved values. Rates range from 10% to 60%. Finally, we include every AMLB task that has natural missing values. The clinical cohorts in the file, the UNC ICU fluid-overload data and All of Us, are not openly accessible, so they serve only as context. The UNC study reported an AUROC of 0.78 for XGBoost with multiple imputation on 391 patients (Machine learning vs. traditional regression analysis for fluid overload prediction in the ICU).

Metrics are AUC, F1, log loss, expected calibration error, wall-clock time to a target score, and inference latency, all measured on outer test folds whose imputers were fitted only on training data. Budgets are 10 and 60 minutes, to match the regime that Auto-sklearn 2.0 reports.

Two checks are decisive. The first is the anytime performance curve comparing adaptive draws with the one-draw and five-draw variants at equal compute. The second is the regime map showing where the coupling gap and the advantage over zero filling are nonzero, as a function of missingness rate and mechanism. We expect gains to concentrate in the high-rate, observed-feature-dependent regime. If they do not appear there, the proposal's premise fails.