Certifying Synthetic Data for a Model Class, Not for Every Event

When people train models on synthetic data instead of real data, they want one assurance: a model fit on the synthetic table will behave on real data roughly as it does on the synthetic data. The textbook route to that assurance runs through total variation (TV) distance, which is the largest gap in probability that the real and synthetic distributions assign to any single event. Small TV bounds the gap in risk for every possible model. Two facts make this route a dead end. First, TV is computationally out of reach. It is #P-hard (a counting-hard class, believed harder than NP) to compute even between independent product distributions, and it stays #P-hard to approximate between marginals of structured models whose full configurations are easy to sample. Second, TV is statistically too strict. Any finite synthetic sample from a continuous or high-cardinality table sits near TV distance 1 from the truth, so a TV-based guarantee is either impossible to evaluate or useless once evaluated.

This note proposes dropping the demand that synthetic data match reality on every event. Instead, we certify it only on the events a chosen family of downstream models can actually distinguish, and only near the model that will be trained. The tool comes from testable learning under distribution shift. That literature builds efficient, provably sound tests of whether a classifier trained on one distribution transfers to another, and it avoids the intractable global discrepancy. We would turn those tests into a synthetic-data auditor that runs on any generator. The auditor would come with a map of which model families admit efficient certification and which inherit the TV hardness results. The practical payoff would be a sound replacement for empirical proxies such as TabStruct's Global Utility. When the auditor accepts, the bound holds for every model in the class and every target column, not just the one model someone happened to evaluate.

Core Claim

Let $P$ be the real distribution over table rows and $Q$ the synthetic one. Let $\mathcal{H}$ be a family of downstream predictors, for example linear classifiers, degree-2 polynomial threshold functions (classifiers that threshold a quadratic in the features), intersections of a few halfspaces, or small decision rules over $k$ columns. The quantity that controls train-on-synthetic, test-on-real error is the class-restricted discrepancy, not TV:

$$d_{\mathcal{H}}(P,Q) = \sup_{h,h' \in \mathcal{H}} \left| \Pr_{P}[h \neq h'] - \Pr_{Q}[h \neq h'] \right| ,$$

where the supremum ranges over pairs of predictors in the class. This quantity is never larger than TV and is often far smaller. Two claims follow. The first is a reinterpretation. The usual hierarchy of synthetic-data checks, 1-way marginals, then pairwise interactions, then leave-one-out conditionals, then the full joint, is exactly $d_{\mathcal{H}}$ for a growing family of "juntas", meaning predictors that look at only $k$ columns. The first two rungs are cheap. Climbing to the joint is where the TV hardness results bite. The second claim is the main one. Localized discrepancy tests certify transfer for dense model families such as halfspaces and low-degree polynomial thresholds, which no junta level captures. These tests check moments, plus a little probability mass near the trained model's decision boundary, and they do so in polynomial time and with polynomially many samples. They should accept useful synthetic data that a global discriminator would reject, and reject synthetic data that fools single-model train-on-synthetic, test-on-real (TSTR) evaluation.

Positioning Against Prior Work

The hardness side motivates the proposal and constrains its design. On the tensorization of the variational distance explains why TV does not decompose over coordinates. Total Variation Distance for Product Distributions is #P-Complete shows exact TV is #P-complete even for independent coordinates. Approximating the total variation distance between spin systems shows approximation stays hard on marginals even when sampling is easy. Together these rule out any auditor whose guarantee is phrased in TV, which is why we target $d_{\mathcal{H}}$. The positive results in Total Variation Distance Meets Probabilistic Inference give an approximation algorithm for TV between Bayesian networks that share a graph of bounded treewidth. That algorithm needs explicit models with identical structure, which a deep tabular generator never provides, so it serves as a special-case reference rather than a method. Total Variation Distance Estimation in Autoregressive Models estimates TV from sequence-model logits. Its measured cross-engine TV of 0.586 for the same weights is a useful warning that TV saturates even between near-identical systems.

The method comes from Efficient Discrepancy Testing for Learning with Distribution Shift. That paper replaces global discrepancy with localized tests: moment matching in the sense of Chow parameters, approximating polynomials that sandwich the indicator of the class, and boundary-mass checks. It gives these tests for constant-depth circuits, degree-2 polynomial thresholds and low-dimensional convex sets, building on Testable Learning with Distribution Shift and Learning Intersections of Halfspaces with Distribution Shift. Those papers treat shift between a training and a test population. None of them treats a generator as the source of training data, or handles mixed categorical and continuous tables, missing values, or the multi-target nature of synthetic-data use. Those adaptations are what we would build.

The closest connecting work is theory for marginal-based private synthesis. Statistical Theory of Differentially Private Marginal-based Data Synthesis Algorithms bounds the TV error of PrivBayes and the TSTR risk gap by TV plus model complexity. Its guarantee is about one specific mechanism's output, and its TV-based risk bound is the one that becomes vacuous on real tables. Bounding the Excess Risk for Linear Models Trained on Marginal-Preserving, Differentially-Private, Synthetic Data uses Bernstein polynomial approximation to show that preserving low-order marginals bounds the excess risk of linear models. This is the nearest idea to ours. It differs in three ways: it certifies a mechanism by construction rather than auditing an arbitrary black-box generator from samples, it is limited to linear models, and it says nothing about which richer classes are hard to certify. Our auditor is generator-agnostic, extends to nonlinear threshold classes, and comes with the corresponding hardness side.

On the evaluation side, three papers motivate the proposal by documenting that existing metrics mislead. Structured Evaluation of Synthetic Tabular Data organizes metrics from marginals to the joint, finds scores fall as structure grows, and explicitly omits distance-based metrics as intractable. We give that hierarchy a formal meaning as junta-class discrepancy. TabStruct shows that SMOTE can win single-target TSTR while destroying structure. It proposes Global Utility, which predicts every column with AutoML, as an empirical fix and states openly that the fix lacks error bounds. Reimagining Synthetic Tabular Data Generation through Data-Centric AI documents the "fidelity paradox": Bayesian-network generators fit marginals well yet train worse classifiers. Our framing predicts this paradox. Matching low-order juntas says nothing about discrepancy on dense halfspace-like decision regions.

Research Program

The work has three parts. The first is a map of what can and cannot be certified. For $k$-column juntas, we would show that $d_{\mathcal{H}}$ reduces to the maximum TV over $k$-way marginals involving the target. That quantity can be estimated from samples in time growing like $d^k$ times the joint cardinality of $k$ columns. Treating every column as a target, as TabStruct does, multiplies the work only by $d$. We would then state what is known about climbing further, under explicit model access, by appealing to the existing hardness results. Here is the regime: the generator is itself an explicit graphical model, as with bn or PrivBayes synthesizers, and its learned graph differs from the reference graph. In that regime, approximating junta discrepancy at growing $k$ inherits the marginal-TV hardness of spin systems through their reductions. This is exactly the open different-graph case left by the shared-graph approximation algorithm. We expect this part to be largely a careful translation of the existing reductions, and we would present it as such.

The second part is the auditor. We would adapt the localized tester of Chandrasekaran et al. to tables. Categorical columns would be one-hot encoded, continuous columns transformed by quantiles, and missingness indicators added. The tester would then run per target column. It matches low-degree moments of $Q$ against held-out real rows, trains the class-$\mathcal{H}$ model on $Q$, and checks that real data does not put excess mass near that model's boundary. The output is accept or reject, plus an upper bound on the real-minus-synthetic risk gap for the trained model. The original guarantees assume concentration conditions on the reference distribution. Part of the work is to measure how often real tables violate them and to fall back to conservative bounds when they do.

The third part is calibration. We would compare the auditor's bound against the true worst-case risk gap in settings where the truth is computable, and against existing proxies in settings where it is not.

Baselines

The naive reference point is the routine fidelity report: mean TV over all 1-way and 2-way column marginals between synthetic and held-out real data, computed on identical splits. The auditor should catch generators that score well here but have large risk gaps. A planted-structure construction (described in the experiments) makes such generators exist by design. Beating this baseline means rejecting those generators while accepting generators whose true gap is small.

The strongest existing method is TabStruct's Global Utility, which runs an AutoGluon ensemble per column and compares synthetic-trained against real-trained performance. Against ground-truth structural scores it reports a Spearman correlation of 0.84 (TabStruct). We would run it with the tiny-default ensemble, which takes 0.64 seconds per 1,000 samples, on the same splits and target columns, and give the auditor a matched wall-clock budget. Beating it requires two things. On the SCM datasets, the auditor's bound must correlate at least as well with the true worst-case gap. On adversarial generators, it must have a strictly lower false-accept rate. Global Utility estimates performance for the models AutoGluon happens to find, while the auditor's acceptance is meant to bound every model in the class.

The second strong competitor is single-model TSTR with CatBoost, the standard utility check. On Adult, TabDDPM reports a CatBoost F1 of 0.815 trained on real data and 0.795 trained on TabDDPM samples. We would reproduce this gap as a sanity anchor. For the private-synthesis regime, Zhou et al. report excess risk below 0.02 and an accuracy drop below 1% at privacy budget $\epsilon = 2$ for linear models on Adult, Compas, Churn, Dutch, Law and Heart. For the linear class, the auditor's bound should be no looser than their analytic bound on the same AIM-generated data.

The third baseline is a classifier two-sample test, sometimes called a discriminator test: train a gradient-boosted classifier to distinguish real rows from synthetic ones and report its accuracy above chance. No reported result for this test on these benchmarks was found on Lacuna.

Two ablations isolate the key ingredient. One removes the boundary-locality step, leaving global moment matching only. The other replaces the sandwiching-degree moment checks with first and second moments only, a MargCTGAN-style check. If the localized auditor does not beat these two, the locality idea is not doing the work.

Why not just…?

Why not just check 1-way and 2-way marginals? These checks certify exactly the 2-junta class and nothing more. A distribution can match every low-order marginal while differing completely on a parity of $k+1$ columns, because TV does not tensorize (Kontorovich). Yang et al. observe scores degrading as structure grows (Structured Evaluation). The planted-parity experiment below shows this failure directly. The more interesting question is whether marginal checks also miss failures on smooth classes like halfspaces in real data, which the fidelity paradox suggests they do.

Why not just use Global Utility or many-model TSTR? This is the real threat. Empirically it may track true transfer as well as our bound on benign benchmarks, and the 0.84 correlation is high. Its weakness is that it estimates performance for the models found by one search procedure, with no uniform guarantee. That weakness only shows under adversarial or unusual generators. The experiments therefore separate the comparison into a benign regime, where we expect rough parity and would report it honestly, and an adversarial regime of SMOTE-like and planted-structure generators, where soundness should differ. If Global Utility also catches the adversarial cases at matched cost, the contribution shrinks to a theoretical explanation of why it works, and we would say so.

Why not just train a discriminator between real and synthetic data? A discriminator over class $\mathcal{H}$ is the natural estimate of $d_{\mathcal{H}}$, but it has two problems. First, it measures global discrepancy, and over a rich enough class that is near maximal for any finite synthetic set, so it rejects useful data. Second, finding the best discriminator over halfspaces is computationally hard in the worst case. Localized testing was designed to avoid both: it asks only whether the specific trained model transfers. The decisive check is generators that are clearly distinguishable from real data yet produce transferable models, such as TabDDPM samples with mild artifacts. On those, the discriminator should reject and the auditor should accept, with the true gap confirming the auditor is right.

Why not just use KL divergence, which decomposes cleanly? KL becomes infinite under any support mismatch. Price et al. find that support truncation accounts for nearly half of a measured discrepancy between serving engines (Price et al.). KL also requires densities that black-box generators do not provide. It does not address the question.

Proposed Experiments

The ground-truth study uses TabStruct's expert-validated SCM datasets, including Hailfinder and Insurance. There $P$ can be sampled without limit, so the true worst-case risk gap over each class can be estimated to high precision by fitting many models on large real and synthetic draws. We would audit samples from 13 generators: CTGAN, TVAE, TabDDPM, TabSyn, TabDiff, GReaT, the bn synthesizer, SMOTE, and AIM and PrivBayes at several privacy budgets. Each would be audited at training sizes from below 640 rows, the regime where MargCTGAN reports CTGAN degrading, up to several thousand. We would report three things for each class (linear, degree-2 polynomial thresholds, intersections of two halfspaces, 3-juntas): the rate of false acceptances when the true gap exceeds the tolerance, the acceptance rate when the true gap is below half the tolerance, and the rank correlation of the bound with the true gap.

The adversarial study plants failures. One construction matches all $k$-way marginals of an SCM while flipping a $(k+1)$-way parity that determines a target column. A second shifts real mass near a halfspace boundary while preserving low moments. A third is SMOTE. Marginal checks should accept the first construction, and Global Utility may or may not catch the second; the auditor should reject both.

The real-data study runs on Adult, the six Zhou et al. datasets, the OpenML suite used in Reimagining Synthetic Tabular Data Generation, and the SDV student, expedia and census tables. Here truth is unknown, so the reference is the measured real-minus-synthetic risk gap of the trained model on a large held-out real split. We would check whether the auditor's verdicts explain the fidelity paradox, that is, whether bn passes junta checks but fails at the halfspace and polynomial-threshold levels.

Three outcomes would settle the proposal. The auditor must be sound in the ground-truth and adversarial studies. On benign data it must be no more conservative than the discriminator test. And at matched compute, it must either agree with Global Utility on benign data while beating it on planted failures, or the honest conclusion is that the uniform guarantee buys little in practice.