Differentially private training adds random noise to each update so that no single person's data can be inferred from the trained model. The noise must be scaled to how much one example can move the update. A recent line of theory stops assuming that every example's gradient is bounded and assumes only that gradients are bounded on average, through their higher moments (the average of the gradient norm raised to a power $k$). This theory has produced near-optimal algorithms for data with heavy tails, meaning data where a few examples have very large gradients. Almost all of it is checked on synthetic data, typically isotropic Pareto-style noise whose tails look the same in every direction. Optimization research outside privacy has learned that this is risky. Real problems differ structurally from synthetic test functions, so a method that wins on synthetic tests can stall on real ones.
We propose to measure what the tails of real per-example gradients actually look like. We will summarize them in a small "tail fingerprint": how heavy the tail is along each direction, how many directions are heavy, how unevenly coordinates are scaled, and how close the problem is to interpolation (fitting every example exactly). We then test two claims. First, rankings of private heavy-tailed optimizers on standard isotropic synthetic data do not predict their rankings on real tasks. Second, a synthetic generator calibrated to the fingerprint restores that predictive power and explains which method wins where. Put briefly, the privacy theory's "moment" assumption is the point where the synthetic-to-real gap enters, and we propose to measure it rather than assume it.
Core Claim
Our hypothesis is that real per-example gradients have anisotropic heavy tails. Large-gradient mass sits in a few directions, and those directions coincide with badly scaled coordinates. The standard isotropic assumption hides exactly the structure that decides which private method works. This would explain several empirical findings that currently have no shared account.
The first is from SoK: A Review of Differentially Private Linear Models For High-Dimensional Data, which benchmarked 16 private linear-model algorithms on six real datasets. Heavy-tailed sparse optimization and greedy coordinate descent won consistently. The authors attribute the wins to robust statistics and coordinate-specific noise, but they never characterize the data geometry that makes this so. The second is from Beyond Uniform Lipschitz Condition in Differentially Private Optimization. That paper showed that clipping every gradient down to the smallest per-example bound beats clipping to the largest, by over 23% accuracy on Caltech-256 at $\epsilon=2$ and 11% on Food-101. The theory behind it is proven only near interpolation, and it is silent on anisotropy.
What is new here is the measurement instrument, plus a falsifiable test of whether synthetic tail models transfer. A new optimizer is not the goal.
To make "anisotropic tails" testable, we write the structure we expect. Let $g(w;x)$ be the per-example gradient at parameters $w$. Let $U_r$ be an $r$-dimensional subspace and $P_U$, $P_{U^\perp}$ the projections onto it and onto its complement. The low-rank heavy tail hypothesis states:
$$\mathbb{E}\|P_{U^\perp} g\|^{k_{\text{hi}}} \le M_{\text{hi}}^{k_{\text{hi}}}, \qquad \mathbb{E}\|P_{U} g\|^{k_{\text{lo}}} \le M_{\text{lo}}^{k_{\text{lo}}}, \qquad r \ll d,\; k_{\text{lo}} < k_{\text{hi}}.$$
In words, only $r$ of the $d$ directions carry the heavy tail, with moment order $k_{\text{lo}}$. The rest are light-tailed, with order $k_{\text{hi}}$. Existing rates assume a single moment order across all of $\mathbb{R}^d$. These include the near-optimal bound $G_2/\sqrt{n} + G_k(\sqrt{d}/n\epsilon)^{1-1/k}$ from Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions and the minimax rate from Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates. Under the low-rank model, we conjecture that the heavy-tail penalty should scale with $r$ rather than $d$ for any method that clips or truncates along the heavy subspace separately. The conjecture rests on the fact that the dimension factor in these rates comes from paying the tail cost in every direction. This is exactly the advantage greedy coordinate descent and discriminative clipping (Haichao Sha et al.) could exploit when $U_r$ happens to align with coordinates.
Research Program
The first component is the fingerprint itself. On each real task, we compute per-example gradients at three checkpoints: initialization, mid-training, and near the non-private optimum. From these we extract four quantities. The first is tail indices of the gradient norm and of projections onto the top eigendirections of the gradient covariance, estimated with a Hill estimator and bootstrap intervals. The second is the "heavy rank" $r$, the number of directions whose estimated tail index falls below 2. The third is the dispersion of coordinate-wise scale and kurtosis. The fourth is the ratios between the smallest, median, and largest per-example gradient bounds, with the gradient norm at the optimum serving as a near-interpolation indicator.
This plays the role that exploratory landscape analysis played for hyperparameter tuning. There, HPO ˟ ELA separated real XGBoost tuning landscapes from the BBOB synthetic suite with 96.46% accuracy and explained why simulated annealing failed on real plateaus. Our features differ in one important way. They describe the noise distribution of per-example gradients, not the shape of the loss surface, and that distribution is what privacy noise is calibrated to.
The second component is a calibrated synthetic generator. It draws per-example gradient-producing data, either linear-model covariates and labels or last-layer features, so as to match a target fingerprint. It plants $r$ heavy directions with a chosen tail index, coordinate scales with the measured dispersion, and a chosen distance from interpolation. Standard heavy-tailed testbeds are recovered as the special case $r=d$ with isotropic scale.
The third component is a ranking study. We run a fixed panel of private heavy-tailed optimizers on real tasks, on isotropic synthetic data, and on calibrated synthetic data. We then ask which synthetic ranking predicts the real one. A lighter theoretical component tries to prove the $r$-instead-of-$d$ conjecture for generalized linear models. We pick that class because Asi, Liu and Tian showed that clipping preserves contraction there. We do not claim non-convex results.
Measuring a fingerprint on private data itself leaks information. In the benchmark study, fingerprints are computed on publicly available benchmark datasets as a research instrument, so no privacy claim attaches to them. For the deployment question, namely whether a practitioner can use the fingerprint to choose a method, we estimate only three scalars privately: heavy rank, coordinate-scale dispersion, and the minimum-to-median bound ratio. These are charged against a fixed budget of $\epsilon=0.3$. That mirrors the Report Noisy Max allocation of Beyond Uniform Lipschitz Condition, and every competing method is charged the same amount.
Baselines
The naive reference point is standard DP-SGD with a single global clipping threshold set by a standard heuristic, the way the SoK ran it. On PAH, the SoK reports a mean squared error of about 0.091 for DP-SGD against about 0.035 for heavy-tailed sparse optimization; the file does not state the privacy budget for these numbers, so we will rerun both at matched budgets rather than compare to them directly.
The strongest existing competitors depend on the regime. On the linear-model tasks they are heavy-tailed sparse optimization (Tao et al.) and greedy coordinate descent. The SoK reports about 83% accuracy for coordinate descent on Heart against about 82% non-private, so on that dataset there is essentially no headroom in accuracy. On the last-layer vision tasks it is clip-to-minimum from Das et al., with its reported gains over maximum clipping of over 23% on Caltech-256 at $\epsilon=2$ and 11% on Food-101. Theory-driven methods fill out the panel. These are discriminative clipping (Sha et al.), private mean-estimation gradient descent (Kamath et al.), the iterative updating method of Zhao et al., and the localization reduction of Asi et al.. The last has no reported empirical result on Lacuna, so our implementation will be a first empirical check. On CIFAR-10 we use the ScatterNet-plus-linear features from Differentially Private Learning Needs Better Features, which reports 67.0% at $\epsilon=3$; we aim to match that operating point with DP-SGD before comparing alternatives.
Fairness rules apply to all methods. Every method gets the same data splits, the same privacy accounting (zero-concentrated DP converted to a common $(\epsilon,\delta)$), the same number of private hyperparameter trials with tuning cost charged to the budget, and the same wall-clock cap. We also report wall-clock time, given the SoK's hours-versus-seconds finding.
The comparison that decides the proposal concerns predictors of the winning method, not individual optimizers. We compare four. The first is the isotropic synthetic testbed ranking. The second is landscape-analysis (ELA) features computed on the private loss. The third is a feature-standardization predictor that ignores tails. The fourth is our fingerprint. The key ablation calibrates the synthetic generator to everything except anisotropy, setting $r=d$ while matching the overall tail index and coordinate scales. If this ablated generator transfers as well as the full one, the low-rank-tail claim is wrong. The fingerprint wins if its calibrated-generator ranking has a Kendall rank correlation with the real ranking that is clearly higher than the isotropic one, with a bootstrap interval excluding zero difference. It must also pick a method within one standard error of the real winner on most tasks.
Why not just…?
Why not just tune the clipping threshold and pick the best method by private hyperparameter search on each real task? This is the honest practical alternative, and it may well be the best deployment answer. It produces no explanation and no benchmark for designing future methods, though, and every trial costs privacy budget, which matters on datasets like PAH ($n=80$) and DBworld ($n=64$). We include it as a predictor arm with its tuning cost charged. If it matches fingerprint-guided selection at equal total budget, we will report that the fingerprint's value is scientific (explaining and building benchmarks) rather than operational.
Why not just always use greedy coordinate descent or heavy-tailed sparse optimization, since the SoK already found they win? The SoK's evidence covers six small linear tasks, most reduced to $d\le 500$. It also reports that coordinate methods are extremely slow. Our hypothesis predicts that their advantage depends on heavy directions aligning with coordinates. When the heavy subspace is rotated, as we expect for last-layer features of pretrained networks, they should lose to clip-to-minimum. The rotated-versus-axis-aligned calibrated experiments test this directly.
Why not just standardize each feature and run DP-SGD? This is a real threat. If anisotropy is only coordinate scaling, per-feature standardization removes it, and much of the reported gap could disappear. Standardization cannot, however, remove heavy tails that live in non-axis directions or come from the labels and residuals rather than the features. We run standardized DP-SGD as a baseline on every task, with statistics estimated privately. If it closes most of the gap to the best method, we will conclude that "heavy tails" in these benchmarks were largely a scaling artifact. That would be a useful negative result.
Why not just use exploratory landscape analysis features, which already separate real from synthetic problems? Those features summarize the shape of the loss surface from sampled function values. Private optimizers instead react to the spread of per-example gradients, which a loss-surface sample does not see. A surface can be benign and unimodal, as HPO ˟ ELA found for XGBoost tuning, while its per-example gradients are heavy-tailed. We include landscape features as a competing predictor, so the comparison settles which description matters.
Proposed Experiments
The real tasks are the six SoK datasets (Bodyfat, PAH, E2006, Heart, DBworld, RCV1). We add RCV1 and E2006 at larger, less-reduced sizes, because tail estimates from $n=64$ are unreliable and will be reported only with bootstrap intervals. We also include last-layer private training on Caltech-256 and Food-101 following Das et al., and CIFAR-10, MNIST and Fashion-MNIST on ScatterNet features. The budgets are $\epsilon \in \{0.5, 1, 2, 3\}$.
The first decisive check is descriptive: is the measured heavy rank $r$ much smaller than $d$ on most real tasks, with tighter tails off the heavy subspace? If real tails are isotropic, the central hypothesis fails at this step.
The second check is predictive. Across tasks and budgets, the calibrated generator's method ranking should correlate with the real ranking substantially better than the isotropic testbed's ranking does. The $r=d$ ablation should lose most of that gain.
The third check is mechanistic. On calibrated synthetic data, we sweep $r$ and rotate the heavy subspace away from the coordinate axes. If our account is right, the coordinate methods' advantage should vanish under rotation, and the gain of clip-to-minimum over maximum clipping should shrink as the gradient norm at the optimum grows, moving the problem away from interpolation.
The fourth check covers deployment. We test whether the three privately estimated scalars choose a method within one standard error of the real winner more often than tuned DP-SGD, standardized DP-SGD, or private hyperparameter search do at equal total budget.
Taken together, the outcomes either show that moment assumptions must be stated per direction to transfer to real data, or show that the isotropic testbeds were adequate all along.
References
- SoK: A Review of Differentially Private Linear Models For High-Dimensional Data
- Beyond Uniform Lipschitz Condition in Differentially Private Optimization
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions
- Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates
- Clip Body and Tail Separately: High Probability Guarantees for DP-SGD with Heavy Tails
- HPO ˟ ELA: Investigating Hyperparameter Optimization Landscapes by Means of Exploratory Landscape Analysis
- Private Stochastic Convex Optimization and Sparse Learning with Heavy-tailed Data Revisited
- Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data
- Differentially Private Learning Needs Better Features (or Much More Data)