Taming Heavy-Tailed Features Before Private Training

Differential privacy (DP) is a formal guarantee that a trained model reveals little about any single record. The standard way to train under DP adds noise to each gradient step, scaled to how much one record could move that step. When the input features have heavy tails, as lab values, incomes and transaction amounts usually do, one record can move the gradient a great deal. Training then either adds so much noise that little signal survives, or it clips gradients so hard that the model is biased. Most of the literature on heavy-tailed private learning fixes this inside the optimizer. It clips averaged gradients, bins data into groups, or iteratively shrinks a bounding region. A separate literature on preprocessing sensitivity shows that choices made before the model sees the data, such as imputation, scaling and cohort filters, often move benchmark results more than the choice of model does.

This note proposes to join the two literatures at one specific point. The claim is that, for tabular models trained with DP, a cheap per-feature transform fit privately removes most of the heavy-tail problem before the optimizer runs. The transform maps each feature through its own privately estimated quantiles onto a bounded range. With it, plain DP stochastic gradient descent (DP-SGD) should match or beat heavy-tail-specific optimizers. A consequence we can test is that published comparisons between private optimizers on real tabular data are confounded by preprocessing, which is an unreported variable. We will build the transform, measure what it costs in privacy budget, and run an audit of how often optimizer rankings flip when only the preprocessing changes.

Core Claim

In a generalized linear model, which is linear regression or logistic regression with a link function, the per-example gradient is $g = \ell'(w^\top x, y)\,x$. Here $\ell'$ is the derivative of the loss with respect to the prediction, $w$ the weights and $x$ the feature vector. If $|\ell'| \le L$, the gradient norm is at most $L\|x\|$. The heavy tail of the gradient is then inherited almost entirely from the heavy tail of the features.

Suppose each coordinate is replaced by $T_j(x_j) = 2\hat F_j(x_j) - 1$, where $\hat F_j$ is a private, piecewise-linear estimate of feature $j$'s distribution function built from $K$ private quantiles. Then

$$\|g\| \le L\,\|T(x)\| \le L\sqrt{d},$$

where $d$ is the number of features. This bound holds deterministically and does not depend on any moment order $p$ or moment bound $M_p$.

The transform does not bias the estimate of a fixed parameter. It changes the hypothesis class to one that is monotone in each rank-transformed feature. For prediction tasks this is usually harmless and often helpful. For estimating the parameters of the original linear model it is not a valid substitute, and we do not claim it is.

This is different from the closest work. The importance of feature preprocessing for differentially private linear optimization introduces DPSGD-F, which privately centers the data. That moves the noise dependence from the maximum feature norm to the dataset diameter. The paper assumes bounded diameter, and centering a power-law feature leaves its diameter unbounded. That paper motivates this proposal and supplies the budget-splitting template. Our transform targets exactly the case DPSGD-F leaves open.

Individual Sensitivity Preprocessing for Data Privacy preprocesses scalar queries rather than features, and proves its guarantees break for $d \ge 3$. That result constrains us. It is one reason we work per coordinate rather than on a joint multivariate surrogate.

Differentially Private Regression with Unbounded Covariates privately preconditions covariates, but only under Gaussian marginals. It names heavy-tailed covariates as open.

Research Program

The transform uses private quantiles computed with exponential-mechanism or interior-point techniques of the kind in Differentially Private Medians and Interior Points for Non-Pathological Data. That paper supplies the method. We estimate $K$ quantiles per feature, with $K$ between 8 and 32. The costs across all features are composed under zero-concentrated DP, a variant of DP that composes cleanly across many queries. The transform takes a fixed fraction $\epsilon_T$ of the total budget, swept from 2% to 20%.

Missing values get their own indicator column before the transform. This deliberately ties the method to the imputation choices that the preprocessing literature flags as decisive.

The program then asks three questions.

The first is whether the transform helps under controlled tails. We use synthetic features drawn from multivariate Student-t distributions. As the degrees of freedom fall, the gain over DPSGD-F should grow. On Gaussian features the gain should vanish.

The second is whether the gain carries over to real heavy-tailed tabular data, with convex models and with small non-convex models. The non-convex case matters because the optimality results for heavy-tailed private optimization in Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates are convex-only. The same holds for Efficient private SCO for heavy-tailed data via averaged clipping.

The third is the audit. We cross a grid of preprocessing choices (raw, z-score, log, fixed winsorization, DPSGD-F centering, private quantile transform) with a set of private optimizers. For each dataset and budget we compute Kendall's tau between optimizer rankings under different preprocessings. This rank-flip style of analysis follows Offspring from Reproduction Problems: What Replication Failure Teaches Us and The Devil is in the Details: On the Pitfalls of Event Extraction Evaluation. Those papers showed that unreported preprocessing flips method rankings in NLP. We apply their evaluation lens to DP.

The scope limit is stated in advance. A feature transform does nothing for heavy-tailed labels. Length of stay is one example, and so is the response setting of Differentially Private Sparse Linear Regression with Heavy-tailed Responses. For such tasks we expect optimizer-side methods to remain necessary, and we report them separately.

Baselines

The naive reference point is standard DP-SGD on z-scored features. The z-scoring uses non-private statistics, which quietly leaks information, and we report this explicitly because published pipelines commonly do it. We also run a strictly private version with a fixed data-independent clip. We use Opacus-style per-example gradient clipping, with the clipping threshold tuned over the same grid for every method.

The strongest preprocessing competitor is DPSGD-F from The importance of feature preprocessing for differentially private linear optimization. It reports 92.0% versus 87.4% accuracy for DP-SGD on MNIST at $\epsilon=1$, $\delta=10^{-5}$. On Fashion-MNIST it reports 84.0% versus 77.2%. We rerun it at the same preprocessing-budget fraction as ours, so the only difference is centering versus quantile mapping. We also reproduce its MNIST number as a sanity check before trusting our implementation.

The strongest optimizer-side competitor is AClipped-dpSGD from Efficient private SCO for heavy-tailed data via averaged clipping. It reports about 64.2% versus about 63.1% test accuracy on CIFAR-10 at $\epsilon=2$. On Adult and Diabetes it reports lower estimation error than DP-SGD, but no reported number was found on Lacuna for those tabular results. We also run the simple-clipping variant of Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates. Its moment parameters are set by the same tuning grid, and we flag that this tuning is itself not private.

The key ablation separates the privacy cost of the transform from its geometric effect. We run the quantile transform with non-private quantiles, which is an upper bound. We also run private winsorization at the same private quantiles without rank mapping. This tests whether bounding alone, rather than reshaping the distribution, produces the gain.

Fairness conditions are the same across all methods: identical splits, total $(\epsilon,\delta)$ inclusive of preprocessing, 50 tuning configurations per method, and 5 seeds.

Beating the baselines means two things. On the heavy-tailed tabular tasks, the private quantile transform with plain DP-SGD must exceed both DPSGD-F and AClipped-dpSGD by more than seed variation at $\epsilon \le 1$. And stacking AClip on top of the transform must add little.

Why not just…?

Why not just log-transform or winsorize at fixed, data-independent thresholds? These cost no privacy budget, and for positive, right-skewed lab values a log transform may capture most of the benefit. This is the most serious threat. It is in the grid as a first-class arm. If it matches the private quantile transform within noise on YAIB and Adult, the method contribution shrinks to "use a sensible data-independent transform." The audit then becomes the main result. The case where log should fail is features with mixed sign, multimodal shape, or unknown scale. The synthetic Student-t features and the cross-center experiments below test exactly those.

Why not just use a heavy-tail-robust optimizer on the raw features? AClip and the iterative updating methods have guarantees only for convex losses. They also need moment knowledge that is unknown in practice, as Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates itself leaves open. The transform bounds sensitivity without any moment assumption. The comparison with a small multilayer perceptron, and with AClip stacked on the transform, settles whether the two approaches are substitutes or complements.

Why not just take quantiles from public data? Private Estimation with Public Data shows that a small public sample can anchor private estimation. In the clinical setting we test this directly by fitting quantiles on one YAIB center and applying them to another. Yet Another ICU Benchmark: A Flexible Multi-Center Framework for Clinical ML documents that measurement practices shift across centers. We therefore expect transferred quantiles to be miscalibrated where lab distributions differ. When they are not, public anchoring is the cheaper option and we will say so.

Proposed Experiments

The synthetic study uses 50-dimensional Student-t features, matching the dimensionality of the synthetic study in CoinPress: Practical Private Mean and Covariance Estimation. We vary the degrees of freedom from 2.5 to infinity and generate labels from a logistic model on rank-transformed features. We also generate labels from a model that is linear in the raw features, to expose the cost of changing the hypothesis class.

The real-data studies use Adult, Diabetes, and YAIB in-hospital mortality on MIMIC-IV, eICU, HiRID and AUMCdb. For non-private context on YAIB, the benchmark reports AUROC between 0.84 and 0.87. We train logistic regression and a two-layer network. Metrics are AUROC and AUPRC, because mortality prevalence varies by center, plus test accuracy on Adult. Budgets are $\epsilon \in \{0.5, 1, 2, 4\}$ with $\delta=10^{-5}$.

The cross-center check trains with private in-center quantiles and evaluates on other centers. It compares this against quantiles transferred from a different center. This tests whether the preprocessing that wins internal validation causes the external-validation collapse YAIB warns about.

Three results would be decisive. First, the gain over DPSGD-F should widen monotonically as tails get heavier and disappear at Gaussian features. Second, stacking AClip on top of the transform should give near-zero additional gain. Third, the Kendall tau between optimizer rankings computed under z-scoring and under the quantile transform should fall substantially below one. If the first check fails, the mechanism is wrong. If the data-independent log arm matches ours, the privatized transform is unnecessary. We state both outcomes in advance.