Escaping Self-Confirming Fixed Points in EM Imputation

Many of the best methods for filling in missing table entries work by expectation-maximization (EM): guess the missing values, fit a model of the data to the completed table, use that model to re-guess the missing values, and repeat. The loop has a known weakness that has never been measured in modern imputers. The model is trained on its own guesses. A wrong but self-consistent completion can therefore become a resting point. A model trained on mean-filled columns learns that those columns cluster at the mean, and it then fills them with the mean again. Classical work on EM imputation flagged this local-optimum trap as an open limitation. The current diffusion-based imputer converges in 4 to 5 rounds from a single mean-filled start, and it never asks whether a different start would have ended somewhere better.

This note proposes two things. The first is to measure that trap directly. The second is to escape it with a small population of EM chains that trade imputations column by column. A fitness score computed only from the observed data decides which chain's imputation of a given column should spread. The score comes from re-hiding some observed entries and checking how well each chain recovers them. The claim to test is narrow and falsifiable. At equal training compute, coordinated exchange between chains should beat independent random restarts with the same selection score, smarter single-chain initialization, and plain averaging across chains. If it does not, the measurement study still establishes how much initialization-driven entrapment actually costs imputation accuracy.

Core Claim

EM imputers fail in a specific way that differs from generic local optima. The completed dataset produced in one round is the training set for the next, so errors that agree with themselves are reinforced rather than corrected. This is why the remedy should act on completed datasets, and act column by column, rather than as a global restart.

Supervised learning from incomplete data via an EM approach fits Gaussian or Bernoulli mixtures jointly over observed and missing features. It retains over 80% accuracy on Iris at 90% missingness, against roughly 35–40% for mean imputation. It also states plainly that EM can stall in poor likelihood maxima depending on initialization, and it offers no remedy. This paper motivates the work. DiffPuter places a diffusion model inside the EM loop. Its M-step trains a 5-layer MLP denoiser on the current completed table. Its E-step runs a reverse-sampling scheme proven to give the posterior mean of the missing entries. It reports an average 8.10% MAE and 5.64% RMSE improvement over the strongest of 17 baselines. Every run starts from mean imputation along a single trajectory. DiffPuter supplies our base method and our main opponent.

The key observation is that tabular imputation decomposes partly by column. One chain may have found a good completion for a column with multiple modes. Another may hold a better completion of a nearly linear column. Restarts throw this information away, while whole-chain copying, as in population-based training, overwrites it.

Research Program

The program has three stages: a diagnosis, a method, and a set of controls.

The diagnosis comes first. In EM with Gaussian mixtures, the likelihood can be computed exactly. We run many initializations: mean, noise around the mean, MICE, and kNN. The test cases are synthetic manifolds with known multimodal structure, namely the S-curve and concentric-circle settings used by Missing Data Imputation using Optimal Transport to show that chained equations collapse to the conditional mean. We also use Iris. We then run DiffPuter from the same initializations on its tabular suite. For each dataset we record the spread of final true imputation error across starts. If the spread is negligible, entrapment does not matter in practice. That would be a useful negative result, and the method stage would be dropped.

The method keeps $K$ EM chains of 4 to 8 members. Before training, we hide a random fraction $\rho$ of the observed entries in each column $j$. Call this held-out set $H_j$. Each chain imputes the hidden entries along with the truly missing ones. Its column-level fitness is

$$S_k(j) = \frac{1}{|H_j|}\sum_{i \in H_j} \left| \hat{x}^{(k)}_{ij} - x_{ij} \right|,$$

where $\hat{x}^{(k)}_{ij}$ is chain $k$'s imputation of held-out entry $(i,j)$ and $x_{ij}$ is its true observed value.

After each EM round, an exchange step runs. For each column, the chain with the lowest $S_k(j)$ copies its imputed column into the worst chain's completed table. All other columns of the worst chain are left untouched. Exploration is gated by disagreement between chains, so diversity is spent only where the landscape appears rugged. A column counts as contested when the spread of $S_k(j)$ across chains exceeds the noise level estimated by bootstrapping $H_j$. Only for contested columns do the receiving chains draw their next E-step at an elevated sampling temperature. This gating borrows the trigger idea from ePF, which raises temperature only when effective sample size collapses and fires in about 10–12% of steps. It is our direct answer to the cost reported for DPSO: DPSO's always-on repulsion gains 2x to 8x on multimodal functions but loses precision on the unimodal Sphere function.

The asymmetric, partial copying follows Multiple-Frequencies Population-Based Training. That work reports a Humanoid interquartile-mean reward of 23,793 at 1B steps, against 16,171 for standard PBT and 17,713 for random search. Its lesson is that structured, partial transfer beats both greedy copying and isolated restarts. We do not import its hyperparameter schedule. We import only the principle that winners should overwrite part of the loser, not all of it.

The controls test the fitness score itself. Using the Gaussian-mixture testbed, we measure how well $S_k(j)$ ranks chains relative to the true likelihood and the true error on missing entries. Under MNAR, the hidden observed entries are not distributed like the truly missing ones, so the score may be biased. ePF notes that diversity mechanisms cannot fix a biased scorer, which constrains what we can claim here. We will report MNAR separately and treat it as the regime where the method is most likely to fail.

Baselines

The naive reference is DiffPuter run as published: one chain, mean initialization, about 5 EM rounds. On Lacuna the only reported result is its average 8.10% MAE and 5.64% RMSE gain over the most competitive of 17 baselines. No per-dataset numbers were found on Lacuna, so we rerun it with the published settings, including $M=50$ sampling steps, as the anchor. Beating it means lower MAE and RMSE on most of the nine datasets in each missingness regime. Gains must be averaged over at least five random masks and must exceed the spread across masks.

The strongest competitor is K independent DiffPuter restarts. Each restart begins from a different initialization: mean, perturbed mean, MICE, or kNN. At the end, the restart with the best total held-out score $\sum_j S_k(j)$ is selected. This baseline gets the same fitness signal, the same number of chains, and the same total denoiser-training epochs as our method. It differs only in having no exchange, so it isolates coordination as the ingredient under test. Beating it at matched compute is the central result.

Two further baselines complete the set. The first is restarts with column-wise selection performed once at the end, which separates exchange during training from simply picking the best chain per column after the fact. The second is a uniform-averaging ensemble across the K chains.

Two ablations remove one component each. One drops the disagreement gating, so temperature is raised on every column. The other drops partial copying in favor of whole-table copying, as standard PBT would do. As a classical reference, we include TDM. TDM matches distributions after an invertible network transform. It reports the lowest MAE and RMSE on almost all of its 12 UCI datasets, with no table values available on Lacuna, and it runs at 2–3x the cost of non-parametric transport. We also include MICE and Sinkhorn imputation, with every method given the same tuning budget.

Why not just…?

Why not just run random restarts and keep the best? This is the real threat, and it is built in as the main baseline with the identical selection score. The evidence that coordination helps comes from other domains: MF-PBT beat random search in reinforcement learning, and 8 coordinated ePF particles matched 32 uncoordinated ones on AIME-2024. Neither result is about imputation. If restarts with end-of-run column-wise selection match exchange during training, we will report that the cheap version suffices.

Why not just start DiffPuter from MICE or kNN instead of the mean? If entrapment is purely an initialization effect, a better single start could close most of the gap at 1/K of the cost. The diagnosis stage measures exactly this, with the spread of outcomes across initializations reported per dataset. Our method must beat the best single initialization chosen after the fact, not only the mean start.

Why not just anneal the E-step temperature, as in classical deterministic annealing? The corpus contains Deterministic Annealing for Stochastic Variational Inference and Annealing Techniques For Unsupervised Statistical Language Learning, both of which smooth the objective early in training. Neither has been tested on modern imputation benchmarks. A single annealed chain is a cheaper alternative and enters as an extra baseline. Annealing applies the same schedule to every column, and DPSO's Sphere result suggests uniform exploration hurts on easy dimensions. The ungated ablation tests this cost directly.

Why not just average the chains? Averaging lowers variance and often lowers MAE, so it is a plausible match. However, on multimodal columns it places imputations between modes, which is the collapse that Missing Data Imputation using Optimal Transport documented for chained equations. We therefore report a distributional metric, the Wasserstein distance to held-out complete data, alongside MAE. Averaging can win on MAE while losing on distribution shape.

Decisive Checks

The experiments use the DiffPuter datasets. The continuous ones are California Housing, Letter, Gesture, Magic, and Dry Bean. The mixed-type ones are Adult, Default, Shoppers, and News. Each is tested under MCAR, MAR, and MNAR at 30% and 50% missingness. The Gaussian-mixture testbed on synthetic manifolds and Iris uses the >80% accuracy at 90% missingness result from Supervised learning from incomplete data via an EM approach as a sanity anchor. We report MAE, RMSE, the Wasserstein distance above, downstream accuracy for datasets with labels, and wall-clock overhead relative to K=1.

Three outcomes would settle the question. First, the diagnosis must show a spread across initializations larger than the spread across masks; otherwise the program stops. Second, on the Gaussian-mixture testbed, $S_k(j)$ must rank chains consistently with the true likelihood under MCAR and MAR. Third, at matched epochs, exchange must beat restarts with column-wise selection on columns flagged as contested, while showing no loss on uncontested columns. That last pattern would separate a real escape from entrapment from an ensembling effect.