One-Shot Perturbation for Non-Interactive Differential Privacy

45 concepts31 papers1 proposal

In traditional differentially private machine learning, privacy is often treated as a tax paid at every step of an iterative process. In algorithms like Differentially Private Stochastic Gradient Descent (DP-SGD), noise is injected into every gradient update. Because each update touches the sensitive data, the privacy budget $\epsilon$ accumulates, forcing a trade-off: either stop training early to save privacy or continue training and accept a massive, utility-destroying noise floor.

A growing body of research suggests a different path: one-shot perturbation. Instead of spreading the privacy budget across hundreds of iterations, these methods inject noise into a single, carefully chosen summary of the data. Once this summary is privatized, the "Post-Processing Lemma" of differential privacy allows for unlimited subsequent computation without any further privacy loss.

The Efficiency of Sufficient Statistics

The core intuition behind one-shot methods is that we often don't need the raw data to train a model; we only need its sufficient statistics. If we can privatize these statistics once, we can iterate to convergence without the "privacy budget depletion" typical of gradient-based methods.

Krichene et al. demonstrate this by adding noise to the underlying data statistics of recommendation systems before training begins. This decoupling allows the model to reach full convergence—a feat often impossible with per-step noise addition—while running up to 1,000x faster than standard private training. Similarly, Harder et al. propose DP-MERF, which privatizes the mean embeddings of a dataset in a single step. This allows researchers to train generative models for an unlimited number of iterations, ensuring that the generator's convergence is never throttled by a dwindling privacy budget.

This "privatize once, analyze forever" philosophy extends to Bayesian inference and clustering as well:

  • Bayesian Inference: Kulkarni et al. show that by perturbing summary statistics rather than individual gradients, one can perform an unlimited number of posterior sampling iterations.
  • Expectation Maximization: Park et al. demonstrate that for models where updates depend on fixed summaries (like Gaussian Mixtures), the privacy budget is consumed only during the initial privatization, treating all subsequent EM iterations as free post-processing.

Perturbing the Objective, Not the Path

Another way to achieve one-shot privacy is to move the noise from the optimization process to the optimization goal. In vertically partitioned learning—where different features of the same individuals are held by different parties—Xu et al. propose injecting noise into the model's objective function coefficients. By perturbing the objective itself in a single step, they avoid the rapid budget depletion seen in iterative gradient-based optimization.

For certain models, we can bypass optimization entirely. Qiu et al. derive closed-form private estimators for Generalized Linear Models (GLMs). By adding noise directly to the estimator's sensitivity in a single round, they achieve high accuracy and lower communication overhead than multi-round methods.

The Non-Interactive Local Constraint

The most extreme version of the one-shot approach is Non-Interactive Local Differential Privacy (NLDP). In this setting, the server cannot interact with users; each user must send a single, privatized message. This is the gold standard for real-world deployment (used by companies like Apple and Google) because it eliminates the latency and synchronization issues of multi-round protocols.

However, NLDP introduces a "curse of dimensionality." Without the ability to adaptively query users, the amount of data required to maintain accuracy often grows exponentially with the number of features. To break this curse, Wang et al. and Xu et al. leverage small amounts of public unlabeled data. This public "anchor" allows the server to reconstruct global statistical properties from independent, single-message perturbations, reducing sample complexity from exponential to polynomial.

Even complex tasks like $k$-means clustering, which traditionally require multiple rounds of interaction to refine cluster centers, can be compressed into a single round. Chang et al. proved that by using hierarchical spatial data structures, one-round algorithms can achieve accuracy nearly identical to non-private versions, demonstrating that interactivity is not a fundamental requirement for high-utility private clustering.

Why One-Shot Wins in Consensus

The superiority of one-shot noise is perhaps most visible in distributed consensus problems. When multiple agents try to agree on an average value (like a sensor reading) while keeping their individual values private, how should they add noise?

Nozari et al. proved a fundamental impossibility: you cannot achieve exact consensus with differential privacy. However, they found that the best way to minimize the variance of the final estimate is to inject the entire privacy budget at the very first step. Spreading noise across iterations only causes the variance to grow over time. A single, initial "one-shot" perturbation provides the optimal balance between privacy and the precision of the final agreement.

Key Foundational Work

Differentially Private M-Estimators (2011) — contributed 1 concept elements to this direction.
Differentially Private Average Consensus with Optimal Noise Selection (2015) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_interactive_local_differential_priva_7fef1686,
  title = {non-interactive local differential privacy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-interactive-local-differential-privacy/rdr_7fef1686f5ae4ab5ba79db32e203a3c2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_interactive_local_differential_priva_7fef1686_v1,
  title = {non-interactive local differential privacy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-interactive-local-differential-privacy/rdr_7fef1686f5ae4ab5ba79db32e203a3c2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake