When users privatize their data on their own devices and send a single noisy message to an untrusted server, that noise is usually treated as pure damage to the model. This note argues it is also something useful: a known, random perturbation of every training point, which is exactly what certified robustness methods add deliberately. A classifier trained directly on these noisy reports is heavily smoothed. It is robust but inaccurate. A classifier trained after statistically "undoing" the noise is sharp, but it is fragile and expensive in data. The proposal is to make this choice explicit. Because the noise distribution is public, the server can undo any chosen fraction of it after collection. That yields a whole family of classifiers, from robust to accurate, from one round of privatized data and at no extra privacy cost.
The setting is non-interactive local differential privacy: each client adds calibrated noise to its own data and sends one message, and the server never sees raw data. The robustness side is the familiar trade-off in which defending against worst-case perturbations lowers accuracy on clean inputs. The new prediction is that under local privacy this trade-off has an unusual price structure. Robustness up to the privacy noise level is free. Clean accuracy is what costs samples, and the cost grows exponentially with feature dimension in a way we can write down. If this holds, the usual intuition flips. Private data is naturally robust-leaning, and the server spends its sample size to buy back accuracy.
Core Claim
Clients encode an image with a frozen public encoder, reduce it to $k$ dimensions with a public projection, clip it to norm $C$, and add Gaussian noise $z \sim N(0, \sigma^2 I)$. They also privatize their label by randomized response and send both once. The server represents each class distribution with random Fourier features $\phi_\omega(x) = e^{i\omega^\top x}$, as in the one-shot mean-embedding approach of DP-MERF.
Gaussian noise multiplies each frequency's expectation by $e^{-\sigma^2\|\omega\|^2/2}$. So for any target smoothing level $r \le \sigma$, an unbiased estimate of the class embedding of the data blurred by $N(0, r^2 I)$ is
$$\hat\mu_c^{(r)}(\omega) = e^{(\sigma^2 - r^2)\|\omega\|^2/2}\,\frac{1}{n_c}\sum_{j \in c} \phi_\omega(\tilde x_j),$$
where $\tilde x_j$ are the noisy reports of the $n_c$ clients in class $c$. In practice class membership is itself recovered from the label noise by standard debiasing.
The classifier is the plug-in Bayes rule on these $r$-smoothed class densities. At $r=\sigma$ it is "train on what you received". At $r=0$ it is full deconvolution. Every point in between is post-processing, so it costs no privacy.
The price of choosing a small $r$ is variance. Frequencies are drawn from a Gaussian kernel of bandwidth $h$, meaning $\omega \sim N(0, h^{-2}I)$. Averaging the amplification factor over these frequencies, using the moment generating function of a chi-square variable, gives an estimator variance that scales as
$$\mathrm{Var} \approx \frac{1}{n_c}\Big(1 - \tfrac{2(\sigma^2 - r^2)}{h^2}\Big)^{-k/2}, \qquad h^2 > 2(\sigma^2 - r^2).$$
The resulting classifier is smoothed at effective scale $\sqrt{h^2 + r^2}$. This one expression links the four quantities the subfields usually treat separately: the privacy level (through $\sigma$), the sample size, the robustness radius, and the feature dimension.
The exponential dependence on $k$ is the same barrier that limits non-interactive private learning. Polynomial-approximation methods face it in Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited, which reports usable regimes only for small dimensions. Projection methods also face it, in Collect at Once, Use Effectively. We do not escape it. We make it measurable and show which end of the robustness-accuracy curve it taxes.
Using noise as a smoother also determines how the classifier is certified. At test time we apply Gaussian randomized smoothing with noise matched to the effective scale. This yields a certified L2 radius in the encoder's feature space. Replacing Gaussian with Laplace noise (pure local privacy) changes the damping from $e^{-\sigma^2\|\omega\|^2/2}$ to a polynomial factor. Undoing it is then far cheaper, but certification shifts toward L1. We treat this as a secondary axis.
Relation to Prior Work
Two papers motivate the work by showing that iterative private training harms robustness. Robustness Threats of Differential Privacy found that DP-SGD (private stochastic gradient descent with per-step noise and clipping) pulls decision boundaries about 15% closer to data and raises curvature. It reported up to a 15.4% larger accuracy drop under the FGSM attack on MNIST. Augment then Smooth (DP-CERT) repairs certified robustness inside central DP-SGD by averaging gradients over noisy augmentations. Both stay inside the iterative, trusted-curator regime. We work where clients send one message and the server never touches raw data. Our smoothing comes from the privacy noise itself rather than from extra augmentation passes.
Our method draws on the one-shot line of work. One-Shot Perturbation for Non-Interactive Differential Privacy, DP-MERF, and DP-MEPF privatize fixed summaries once and then optimize freely. DP-MEPF also shows that public pretrained perceptual features make low privacy budgets usable. We reuse the public-encoder idea and the random-feature embedding. Unlike these papers, we privatize per client rather than through a central aggregate, and we use the known noise law to pick a robustness level after the fact.
The closest theory, On robustness and local differential privacy, shows that the costs of outlier contamination and local privacy decouple for low-dimensional mean, median and density estimation. It concerns contamination of the training data, not test-time perturbations, and it does not touch classifiers or clean accuracy. Our variance expression sits in the opposite place. It says that for classification, privacy and robustness are coupled by design, since they share the same noise.
TRADES supplies the conceptual frame: robust error splits into natural error plus "boundary error", traded off by a weight $\lambda$. Our $r$ plays the role of $\lambda$ but is set at the server without any inner maximization. TART shows that perturbations off the data manifold are what cost clean accuracy. That constrains our design. Isotropic noise in a $k$-dimensional public projection spends most of its energy off the manifold, so the choice of public projection is expected to matter as much as $\sigma$.
Research Program
The first component is the protocol and its analysis. We will specify the client mechanism with full privacy accounting for features and labels: the Gaussian mechanism on clipped projected features and randomized response on labels, with budgets added together. We will derive finite-sample bounds for the plug-in classifier as a function of $(\sigma, r, h, k, n)$, and the optimal $r^*(n)$ that maximizes certified accuracy at a target radius. We predict that $r^*$ shrinks toward zero only logarithmically in $n$ at fixed $k$.
The second component asks how the encoder and projection choice interact with the smoothing. We will compare a generic ImageNet-pretrained encoder with a CLIP-style encoder, and plain PCA with class-agnostic projections fit on public data. Following TART's insight, we expect projections that keep the directions the data actually varies along to shift the whole curve upward.
The third component is a geometry study that closes the open question raised by Robustness Threats of Differential Privacy. Using that paper's protocol, we will measure margin to the decision boundary and curvature for our classifiers against DP-SGD heads trained on the same features at matched privacy.
Proposed Experiments
The main testbeds are CIFAR-10, MNIST and FashionMNIST, with MNIST-C for corruption robustness and EMNIST for a many-client population. Each uses public ImageNet-pretrained features as in DP-MEPF. We sweep $\epsilon \in \{0.5, 1, 2, 4, 8\}$, $k \in \{8, 16, 32, 64\}$, and the client fraction used.
The metrics are clean accuracy, certified accuracy at a range of feature-space L2 radii, and empirical robust accuracy under PGD attacks run end-to-end through the frozen encoder. We report the PGD results honestly as uncertified, since our certificate covers the head only. MNIST-C accuracy gaps complete the set.
The main figure plots the clean-versus-certified frontier traced by $r$, at each $(\epsilon, n)$.
Baselines
The naive reference point trains the same plug-in classifier, and separately a small neural head, directly on the noisy reports, with no undoing of the noise. This is the $r=\sigma$ endpoint. It isolates whether the server-side deconvolution adds anything at all. A second ablation fixes $r=0$ (full deconvolution) and adds test-time smoothing. This separates "learn sharp, then smooth" from "learn at the right smoothness". Beating these means a strictly better frontier at matched $\epsilon$ and $n$.
The strongest competitor under the same trust model is a two-step pipeline. The server first fits a DP-MERF/DP-MEPF generator from privatized embeddings. It then runs TRADES on synthetic features across a sweep of $\lambda$. Like our method, this is pure post-processing and can trace a frontier. We run it on the same encoder, the same projection, the same privatized embedding, and the same total server compute and tuning budget. For context, DP-MEPF reports 80% downstream MNIST accuracy at $\epsilon = 0.2$ with an MLP, from DP-MEPF, though that is a central-aggregate privacy guarantee. There is no reported result on Lacuna for CIFAR-10 classification under non-interactive local privacy, so this baseline must be run fresh. Beating it means higher certified accuracy at matched clean accuracy at two or more radii.
The stronger-trust references are central DP-SGD and DP-CERT on the same frozen features. Here the published anchors are 88.67% clean CIFAR-10 accuracy for DP-SGD and 89.53% for the label-only ALIBI mechanism (ResNet50 fine-tuning), both from Does Differential Privacy Prevent Backdoor Attacks in Practice?. DP-CERT reports a 2.5× certified-accuracy gain at large radii over its prior baseline, but the file gives no absolute value. These models see unnoised features, so we do not expect to beat them on clean accuracy. The test is whether our certified accuracy at moderate radii comes within a stated gap of them while offering local privacy.
The non-private ceiling is TRADES on the same features. The file reports 88.64% natural and 56.61% PGD-robust accuracy for TRADES at its endpoints on full CIFAR-10 networks, from TRADES. We will recompute both on frozen features.
Why not just…?
Why not just train on the noisy reports and accept what comes out? That is our $r=\sigma$ point. At realistic budgets ($\sigma$ several times the clip norm), it should be robust but low in clean accuracy. The claim that a better choice exists is falsifiable. If the naive endpoint matches the frontier at every $n$ we test, the deconvolution machinery is useless and we will report that.
Why not just generate synthetic data from a private embedding and run adversarial training on it? This is the real threat, because it is also free post-processing. Our argument is that a generator adds approximation error on top of the same deconvolution variance, without removing that variance. The generator still needs the information that the noisy reports damp exponentially. Our closed form exposes that cost directly and needs no minimax training. If the two-step DP-MEPF+TRADES pipeline matches our frontier, the contribution narrows to the variance law and the geometry study. The head-to-head experiment above settles this.
Why not just use DP-SGD, or DP-CERT, in a federated setup? These need many rounds of client participation and trusted aggregation. The federated evidence in Local and Central Differential Privacy for Robustness and Privacy in FL shows that clients who skip local noise gain leverage. DP-SGD also produces closer, more curved boundaries. Our geometry study tests directly whether one-shot noise avoids that.
Why not just use label-only privacy? ALIBI's 89.53% clean accuracy is strong, but it leaves features unprotected. Where features themselves are sensitive, it does not meet the requirement. We include it only as an accuracy reference.
Decisive Checks
Three outcomes decide the proposal.
First, does the empirical variance follow the predicted $(1 - 2(\sigma^2 - r^2)/h^2)^{-k/2}/n$ scaling across $k$ and $n$? We test this with synthetic Gaussian class mixtures, where the ground truth is known.
Second, on CIFAR-10 features at $\epsilon = 2$, does some intermediate $r$ dominate both endpoints and the synthetic-data TRADES baseline on the clean-versus-certified frontier?
Third, do our classifiers show larger margins and lower curvature than DP-SGD heads at matched privacy? A no on the second check with a yes on the first would still deliver a useful negative result: one-shot local privacy fixes the robustness side for free but cannot buy clean accuracy back at practical dimensions.
References
- DP-MERF: Differentially Private Mean Embeddings with RandomFeatures for Practical Privacy-preserving Data Generation
- Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited
- Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible
- Robustness Threats of Differential Privacy
- Augment then Smooth: Reconciling Differential Privacy with Certified Robustness
- Private Learning with Public Features
- Pre-trained Perceptual Features Improve Differentially Private Image Generation
- On robustness and local differential privacy
- Theoretically Principled Trade-off between Robustness and Accuracy
- TART: Boosting Clean Accuracy Through Tangent Direction Guided Adversarial Training
- Does Differential Privacy Prevent Backdoor Attacks in Practice?
- Local and Central Differential Privacy for Robustness and Privacy in Federated Learning