Overview

Differential privacy studies algorithms whose outputs reveal limited information about any individual record, even when an attacker knows other data. Common approaches add calibrated noise to statistics or clipped gradients, use randomized response for local privacy, or combine privacy with subsampling, shuffling, and secure aggregation. These methods support private statistical estimation, machine learning, federated learning, and synthetic data generation, including for images, tables, and text; evaluation often measures both task utility and membership-inference risk. A central tension is that stronger guarantees can reduce accuracy or increase computational cost, while task-specific structure and tighter privacy accounting may improve the trade-off without resolving all deployment risks.

Latest papers

314 papers39 papers in the last four weeks, up 5% on the four weeks before. 0.3% of all new papers.

Nov 19, 2026

Ask in the Crowd: Differentially Private LLM Inference via Dummy-Augmented Shuffling

Large language models are increasingly deployed as LLM-as-a-Service (LLMaaS), where user queries are sent to remote LLMs for inference, raising severe privacy concerns about the exposure of sensitive user inputs. Differentially private inference mitigates these risks by injecting noise into input embeddings. However, existing methods struggle to balance privacy and utility, as stronger privacy protection often leads to substantial accuracy degradation in LLM inference. In this work, we propose DP-SPD, a differentially private LLM inference framework that protects user queries by hiding the real query among client-generated dummy queries. All queries are randomly shuffled before being sent to the server, preventing direct identification of the user's true intent. To improve inference efficiency, we exploit the shared-prefix structure among queries and reuse transformer key--value (KV) caches during decoding. We analyze the privacy guarantee of DP-SPD and evaluate its utility on classification and generation tasks, as well as its privacy protection under QIA, EIA, and GPT-based attacks. Experimental results show that our method achieves strong inference-time privacy protection and near-plaintext utility while improving inference efficiency through shared-prefix KV-cache reuse.
Nov 19, 2026

Differentially Private Score Estimation with Applications to Score-Based Generative Models

Estimating the score function of a distribution plays a central role in statistics and machine learning, with applications in distribution estimation, sampling, and score-based generative modeling. However, learning scores from sensitive data raises privacy concerns. These concerns are particularly pronounced in score-based generative modeling, where trained models may memorize individual training examples and expose sensitive information through membership inference and data extraction attacks. Although non-private score estimation has been extensively studied, the statistical limits of its private counterpart remain less understood. In this work, we study score estimation under (α,β)(α,β)-differential privacy for dd-dimensional sub-Gaussian distributions with locally γγ-Hölder-continuous scores. We develop a sampling-based private score estimator using quadratic B-splines and the exponential mechanism, and we implement our proposal through projected Langevin Monte Carlo with runtime polynomial in the sample size nn. The proposed estimator satisfies (α,β)(α,β)-differential privacy, and achieves expected density-weighted squared error \mboxpolylog(n)max⁡(n−2γ/(d+2γ+2), (nα)−2γ/(d+γ+1))\mbox{polylog}(n) \max(n^{-2γ/(d+2γ+2)},\,(nα)^{-2γ/(d+γ+1)}). We also establish a nearly matching private minimax lower bound, thereby characterizing the privacy-accuracy trade-off for score estimation. As an application, we construct a differentially private diffusion model whose privacy guarantee is independent of the number of denoising steps. We show that, with an appropriate discretization scheme, the resulting diffusion model attains nearly minimax optimal expected total variation error among all private distribution estimators. We validate our theoretical findings through experiments on both synthetic and real-world datasets.
Nov 19, 2026

Instance-Optimal Moment Estimation in the Add-Remove Model of Differential Privacy

In this paper, we study the problem of estimating empirical means, variances, and covariances under pure differential privacy in the add-remove model. While existing mechanisms achieve optimal worst-case error, they may not be optimal for individual datasets. To measure the performance of mechanisms on individual datasets, we introduce instance-dependent error metrics and prove sharp lower bounds on them. Then, we design mechanisms that achieve these lower bounds and demonstrate that they achieve asymptotically better utility compared to existing methods.
Nov 18, 2026

PriTabICL: Differentially Private Tabular In-Context Learning with Task-Aligned Cluster-Wise Synthesis

Tabular in-context learning (TabICL) enables large language models (LLMs) to predict target records using a handful of labeled demonstrations in their prompts. However, these demonstrations often contain sensitive personal information. Differential privacy (DP) offers principled protection, but noise-based methods introduce substantial noise, distorting the feature-label relationships essential for accurate prediction, especially as data dimensionality grows. In this work, we study DP data synthesis for generating privacy-preserving TabICL demonstrations. We identify two limitations of directly applying general-purpose DP synthesis to entire datasets: modeling a global distribution can obscure local structure and minority patterns in heterogeneous data, while measuring broad attribute dependencies under a limited privacy budget can reduce the accuracy available for relationships most relevant to prediction. More broadly, global statistical fidelity may fail to preserve heterogeneous structures needed by downstream predictive and generative models. To address these challenges, we propose PriTabICL, a general framework compatible with existing DP synthesis algorithms. It partitions records into DP clusters and synthesizes each independently, using a fixed feature-target workload to prioritize prediction-relevant statistical relationships. At inference, each query is routed to a DP cluster, and demonstrations are sampled from its synthetic dataset without additional privacy loss for the original records. Experiments on four real-world datasets demonstrate the effectiveness of our methods across heterogeneous datasets. In particular, one of our instantiations, PriTabICL-PrivSyn, improves over global PrivSyn in 8 out of 12 settings and outperforms existing private TabICL approaches in nearly all evaluated settings. Open-source code is available.
Nov 13, 2026

Privacy-Preserving Clustering Algorithm and Parameter Selection for Collaborative Population Stratification Using Distributed PCA

We propose a privacy-preserving selection layer for collaborative population stratification workflows, enabling an honest-but-curious server to recommend a strong clustering algorithm-hyperparameter configuration from privacy protected shares. Instead of using a fixed workflow such as PCA followed by K-Means with a preset number of clusters, the framework compares multiple clustering methods and parameter settings under privacy constraints. To avoid relying on a public reference basis, we construct a shared low-dimensional representation through a distributed-PCA (DPCA) procedure in which each party computes local top-rr principal-component information and the server aggregates only low-rank summaries to recover a global basis. Building on this representation, the framework supports three LDP-protected pipelines: PCA then Noise, Noise then PCA, and Noise-Only. The server evaluates clustering methods and parameter settings using internal validation metrics and recommends a top-performing configuration from the perturbed data; this step is pure post-processing. Experiments on openSNP and 1000 Genomes show that the server-side selection layer reliably identifies strong settings from LDP-protected data. Across both datasets, the PCA-based pipelines outperform Noise-Only in clustering utility, communication cost, and runtime, and show lower membership-inference attack (MIA) power at small privacy budgets. Overall, they provide the best utility--scalability trade-off in our setting.
Nov 13, 2026

Quantifying Membership Inference Risks in Genomic Data Sharing: The Role of Attacker's Auxiliary Information

Genomic data sharing is essential for biomedical research but introduces significant privacy risks, including membership inference attacks, in which an adversary determines whether a specific individual's data was used in a study. Existing privacy protections are typically applied after a release format has already been chosen, leaving researchers without a principled method to assess dataset-specific risk beforehand. We propose a server-assisted, principal component analysis-based pre-release auditing framework that maps genomic data into a shared low-dimensional space, applies epsilon-local differential privacy via the Laplace mechanism with a formally derived sensitivity for principal component analysis scores, and estimates membership inference attack power at a controlled 5% false-positive rate using a distance-threshold attack. A membership-neutrality diagnostic based on Unbiased Reconstruction Robustness is reported alongside attack power, precision, and recall. Experiments using the openSNP and 1000 Genomes Project datasets across multiple dimensionalities and privacy budgets show that separation between the researcher's dataset and public auxiliary data in principal component analysis space is a dominant determinant of attack success, exceeding the effect of perturbation level alone. Comparison against a genome-wide association study-style likelihood ratio test baseline further contextualizes the measured risk. This framework enables researchers, data repositories, and institutional review bodies to quantify dataset-specific membership inference risk before genomic data publication, supporting more informed and privacy-aware biomedical data-sharing decisions.
Nov 12, 2026

Tractable Importance Sampling for Monte Carlo Privacy Accounting

Evaluating tight Differential Privacy (DP) parameters for DP matrix factorization with privacy amplification by sampling requires analyzing high-dimensional, correlated Gaussian mixtures. Because integrating these mixture distributions to find the exact privacy failure probability (δδ) is analytically intractable, these mechanisms are typically analyzed using Monte Carlo accounting. However, standard sampling suffers from prohibitive variance when estimating small δδ associated with strict privacy guarantees, which in turn requires a large sample complexity, making Monte Carlo accounting inefficient. We demonstrate that Monte Carlo accounting can be made much more efficient via importance sampling. We give a shifted importance sampling proposal distribution parameterized by a stretch factor α>1α> 1. We prove a closed-form bound B(α)<1B(α) < 1 on the support of the importance-weighted estimator that holds identically for both directions of the hockey-stick divergence, show that BB is log-convex so that the optimal αα is a one-dimensional root-finding problem, and show that the resulting estimator seamlessly plugs into the KL-Hoeffding verification protocol used by past work, with a sample complexity reduced by exactly a factor of 1/B(α∗)1/B(α^*).
Nov 10, 2026

MammothDP: Private Boosted Decision Trees Ready for Trusted Hardware and Leakage-free Hyperparameters

Data spaces like the European Health Data Space (EHDS) require the protection of sensitive data in studies during the data's processing and the study's release alike. In this work, we investigate how to implement this mandate using established trusted execution environments (TEEs) and timing side-channel hardening to protect the processing even under a compromised server, and the state-of-the-art differential privacy (DP) notion to protect the release of studies on tabular data. This combined setup could seem to complete the picture, but in fact raises unexpected security challenges that we mitigate by introducing MammothDP: a significant milestone towards a holistic machine learning system based on the recent gradient boosted decision tree learner S-BDT that is provably DP if used within a privacy filter, timing side-channel hardened, and deployed on a TEE. To achieve a strong privacy-utility tradeoff, we introduce two novel components: an early stopping criterion that adaptively selects the number of trees without any privacy overhead, and an improved rollback protection that is no longer vulnerable under timing side-channel attacks.
Nov 10, 2026

Differentially Private Statistical Inference for Rankings from Pairwise Comparisons

Reliable inference for rankings of large language models based on human pairwise comparisons must preserve the privacy of individual preference records. To meet this need, we develop methods for score and rank inference under the Bradley-Terry model with edge differential privacy. For an objective-perturbed estimator, a new leave-one-out analysis establishes finite-sample bounds on Euclidean and entrywise estimation errors. For sufficiently dense comparison graphs, the error bounds extend to smaller privacy budgets, including regimes in which its privacy term dominates its statistical term. A uniform asymptotic expansion yields asymptotically valid confidence intervals for individual scores and pairwise score differences. To improve finite-sample performance, we account for both regularization bias and privacy-induced randomness by combining a plug-in ridge-bias correction with Gaussian-Laplace calibration. We further establish a bootstrap procedure for simultaneous rank inference, providing asymptotically valid confidence sets for individual ranks and tests of top-KK membership. When the comparison probability is public and known, all proposed inferential procedures require no additional privacy budget. We evaluate finite-sample performance through simulations and apply the proposed methods to rank large language models for creative writing.
Nov 9, 2026

Optimal Rates for Adaptive Private kk-PCA

Given nn i.i.d. random matrices Ai∈Rd×dA_i \in \mathbb{R}^{d \times d} with common expectation ΣΣ, the goal of Differentially Private Stochastic PCA is to identify a kk-dimensional subspace capturing the leading variance directions of ΣΣ, while preserving differential privacy~(DP) for each individual sample AiA_i. \citet{dungler2025iterative} introduced \kdppca, the first algorithm to simultaneously (1) achieve sample complexity n=O~(d)n=\widetilde O(d) for sub-Gaussian data, (2) adapt its privacy noise to the intrinsic randomness of the data, and (3) extend seamlessly to any target dimension k≤dk\le d. However, its sample complexity has a suboptimal dependence on kk. We propose the first algorithm that achieves optimal sample complexity in both dd and kk, while retaining properties (2) and (3) of \kdppca. Additionally, prior utility guarantees require a minimum sample size with exponential dependence on the eigengap. Our method removes this dependence. It also improves the dependence on spectral parameters, matching known lower bounds for the spiked covariance model. Unlike deflation-based approaches like \kdppca, our algorithm updates the full d×kd\times k subspace jointly rather than one eigenvector at a time. This non-deflation structure simplifies the algorithm, reduces the number of hyper-parameters, and improves computational efficiency, particularly when using block linear algebra libraries.
Nov 8, 2026

MOMENT-DP: Momentum Aware Evaluation of Correlated Noise for Differentially Private Training

Temporally correlated noise can substantially improve the utility of differentially private optimization, yet candidate mechanisms are commonly designed or evaluated using only partial information about the optimization process, such as workload structure, learning-rate schedules, or local curvature. We study whether persistent optimizer state provides additional information that can change the relative utility of privacy-valid correlated-noise mechanisms. We introduce MOMENT-DP, an optimizer-state-aware framework that models how temporally correlated privacy noise propagates through momentum-based optimization. For locally quadratic objectives, MOMENT-DP expresses privacy-induced final loss through an optimizer transfer operator that jointly captures curvature, learning-rate scheduling, momentum, and temporal noise covariance. NoiseCurve's curvature-aware quadratic criterion is recovered exactly as the zero-momentum, constant-learning-rate special case. Changing only momentum while holding curvature, schedule, privacy calibration, and candidate mechanisms fixed induces genuine mechanism-ranking reversals. The effect persists outside exact quadratic dynamics in per-example-clipped private logistic regression, while remaining unresolved in the neural regime we study. These results establish optimizer state as an under-modeled, decision-relevant axis in evaluating temporally correlated privacy noise.
Nov 6, 2026

Differentially Private GraphRAG: Protecting Relation Connectivity and Semantics

Graph Retrieval-Augmented Generation (GraphRAG) connects information across documents through entity relationships to support relational reasoning. However, black-box access to GraphRAG systems can enable adversaries to reconstruct knowledge graphs and recover both structural connectivity between entities and the semantics of their relationships. Existing defenses lack formal privacy guarantees and provide limited protection against such reconstruction attacks. We propose RelGuard, the first differentially private framework for GraphRAG, which provides formal privacy guarantees by mitigating connectivity leakage and protecting relations and their semantic meaning through relation removal. We formalize relation differential privacy (relation-DP), which bounds the distinguishability of mechanism outputs according to the semantic distance between alternative relations while accounting for relation removal. Building on this definition, we develop a four-step defense mechanism that sanitizes source documents before GraphRAG indexing by perturbing relation predicates or removing their associated connectivity using the exponential mechanism. Experiments across three GraphRAG systems and two targeted reconstruction attacks demonstrate that RelGuard provides stronger protection against reconstruction attacks than four existing defense mechanisms while better preserving downstream utility.
Nov 5, 2026

On Differentially Private Mechanisms for Linear Regression

We study the classic least-squares linear regression problem under differential privacy (DP) in the batch and the continual observation setting. In the latter setting, the mechanism receives a stream of nn data points (xi,yi)(x_i,y_i) (xi∈Rdx_i\in\mathbb{R}^d and yi∈Ry_i\in\mathbb{R}) and must output an estimate of the optimal parameters at each time step ii. Although differentially private linear regression has been extensively studied in the batch setting, the problem remains underexplored for the continual setting, with prior work being restricted to constrained linear regression and update time polynomial in nn. In this work, we introduce ContinualAdaSSP, the first mechanism for unconstrained linear regression under continual differential privacy. Our mechanism's suboptimality gap is proportional to dpolylog⁡(n)\sqrt{d}\operatorname{polylog}(n). It requires O(d2log⁡n)O(d^2\log{n}) space and O(d2log⁡n+dω)O(d^2\log{n}+d^ω) update time, where dd is the dimension of the input space. We also study fundamental limits of differentially private linear regression by showing the first lower bounds for the box-constrained least-squares linear regression problem. Our lower bounds are proportional to min⁡(n,dlog⁡1.5d)\min(n,\frac{\sqrt{d}}{\log^{1.5}d}) for (1,O(1n))(1,O(\frac{1}{n}))-DP, and min⁡(n,dε)\min(n,\frac{d}ε) for εε-DP, and are derived using a reduction from a fingerprinting code problem from [Peter et al., 2024], providing new insights into the inherent hardness of this canonical task. Our experimental evaluation on real-world datasets shows that the accuracy of our continual observation mechanism clearly outperforms any other known differentially private mechanism for this problem such as rerunning the batch algorithm at each time step.
Nov 5, 2026

Statistical and Privacy Guarantees for Deep M-Regression via Stochastic Gradient Langevin Dynamics

In this article, we study deep nonparametric regression trained via stochastic gradient Langevin dynamics (SGLD), a variant of stochastic gradient descent that injects carefully calibrated Gaussian noise during optimization. Using a PAC-Bayesian analysis tailored to deep ReLU networks, we establish an excess-risk bound that simultaneously accounts for network approximation error, statistical complexity, and the algorithmic cost accumulated along the SGLD trajectory. Under a Bernstein condition and within a stable SGLD regime, the excess-risk bound contains a stochastic term whose coefficient is inversely proportional to the variance of injected noise, while the estimator retains the optimal rate for nonparametric regression under the Hölder smoothness condition up to logarithmic factors. This result provides an approximation-error-aware, rate-optimal statistical perspective on the widely observed generalization benefits of moderate SGLD noise. For per-sample clipped SGLD, we further establish an exact f-DP guarantee and the corresponding asymptotic μμ-GDP guarantee for the proposed estimator. We establish statistical convergence rates and differential privacy guarantees for DNN estimators trained using SGLD, while explicitly accounting for both network approximation error and the effect of injected noise in the excess-risk bound. Extensive simulation studies and analyses of two real datasets examine the finite-sample predictive performance and privacy-utility behavior of the proposed procedure.
Nov 4, 2026

Dimension-Free Private Mean Estimation is Impossible Without the Covariance

We study the limits of differentially private Gaussian mean estimation when the covariance matrix is unknown. Prior work shows that when the covariance ΣΣ is known, the optimal sample complexity can depend only on its spectrum, rather than on the ambient dimension dd. We establish new lower bounds for Gaussian mean estimation with Euclidean error which show that private estimators cannot achieve similar guarantees when the covariance is unknown. First, when the sample size nn is smaller than the effective dimension trace(Σ)/∥Σ∥op\mathrm{trace}(Σ)/\|Σ\|_{\text{op}}, the optimal error when the covariance is unknown can be larger than the optimal error when it is known by a factor of d/n\sqrt{d/n}. Second, when the sample size is larger than the effective dimension, even for diagonal covariance matrices with effective dimension bounded by log⁡d\log d, the optimal error when the covariance is unknown can be larger than the optimal error when it is known by a factor of d/n3/2\sqrt{d}/n^{3/2}. Together, these results show that in the unknown covariance setting, exploiting anisotropic structure under differential privacy can require a dimension-dependent error or sample complexity.
Nov 4, 2026

CoRTeC: A Differentially Private Release for Synthetic Tabular Data, Decodable by Any Generator

The records that could train the most useful models, such as a hospital's patient files, are often the ones an institution cannot share. We propose CoRTeC, a method that releases synthetic versions of such records under differential privacy. Differential privacy places a proven limit on what the synthetic data can reveal about any person, and in particular on membership inference. CoRTeC spends the privacy budget once, on a small file of noisy counts designed for training a classifier. For each group of records, the file gives the group's size, its balance of outcomes, a histogram of every column for each outcome and the outcome rate in each of several non-overlapping cells. A reviewer can check every number before the file leaves the institution. Anyone can then turn the counts into synthetic rows, as often as they like and at no further privacy cost. A maximum-entropy decoder can do this without any language model, and so can each of the five frozen language models we tested. None of them ever sees a real record. A selection step then matches the rows to the released counts. Decoded without a language model, the automatically configured release at ε=2\varepsilon = 2 trains classifiers to within 0.02 AUC of a real sample of the same size on the Adult dataset, across three data splits. On NHANES and bank marketing, without the selection step, it stays within 0.05 AUC. On Adult, with a fixed cohort rule, the release carries the outcome rates a deployment names more closely than a real sample does, at some cost in accuracy on pairs of columns. Four controls show that most of the utility comes from the release and the selection step, and that a language model adds what it knows from the column names. No private row ever reaches a model, and no row CoRTeC generates copies a real one. The strongest membership attack stays far below the bound the budget allows.
Nov 3, 2026

Privacy for Free in Efficient Agnostic Halfspace Learning

We provide the first computationally efficient, differentially private algorithms for agnostically learning halfspaces. In particular, we study three different settings of agnostic learning: improper learning under Gaussian and log-concave marginals; proper learning under Gaussian marginals; and semi-agnostic learning under Gaussian marginals. In all three aforementioned settings, the added cost in the sample complexity due to privacy matches the respective non-private sample complexity, implying that we get privacy for free.
Nov 2, 2026

Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing

In this paper, we study when two parties should pool their data to train a machine learning model. Two agents, Alice and Bob, each hold a sensitive labeled dataset and want to train a classifier from a given hypothesis class H\mathcal{H}. Even when each party's dataset can be perfectly classified on its own, the two parties may follow conflicting labeling standards or have selection biases that affect their features and label sets, such that no single classifier in H\mathcal{H} fits their combined data. Before committing to data sharing, Alice and Bob therefore want to test whether a single classifier in H\mathcal{H} can jointly fit both datasets---without revealing their individual data points to one another. We formalize this problem from a learning-theoretic viewpoint via opt⁡H\operatorname{opt}_\mathcal{H}, the minimum number of mistakes made by any hypothesis in H\mathcal{H} on their pooled data. Through interactive communication, the agents must distinguish opt⁡H=0\operatorname{opt}_\mathcal{H}=0 (compatible datasets) from opt⁡H≥t\operatorname{opt}_\mathcal{H}\geq t (conflicting datasets) under pure ε\varepsilon-two-party differential privacy. A trusted curator could do this with t=O(1/ε)t=O(1/\varepsilon), and we ask how small tt can be without one. For thresholds on the real line over a domain of size mm, we show that the optimal tt is Θ~(log⁡log⁡m/ε)\tildeΘ(\log\log m/\varepsilon), exponentially smaller than the Θ(log⁡m/ε)Θ(\log m/\varepsilon) samples needed to privately learn thresholds, even with a curator. For halfspaces in Rd\mathbb{R}^d, the dependence on mm jumps to log⁡(m)\log(m): we give a protocol with t=O~(d3log⁡m/ε)t=\tilde{O}(d^3\log m/\varepsilon) and show that some domains require t=Ω(dlog⁡(m/d)/ε)t=Ω(d\log(m/d)/\varepsilon).
Nov 2, 2026

Improved regret bounds in tabular RL under local differential privacy

We study regret minimization for time-homogeneous episodic tabular reinforcement learning with SS states and AA actions under non-interactive εε-local differential privacy (LDP). In each episode k∈[K]k \in [K], the decision-maker sends a policy to a user, the user executes the policy for HH steps, and sends an εε-locally differentially private message back to the decision-maker. When H=1H=1, the problem reduces to an LDP contextual bandit with SS contexts, AA arms and horizon KK. We prove that the minimax regret is min⁡(K,max⁡(S,exp⁡(ε)+1)SAK(exp⁡(ε)+1)exp⁡(ε)−1)\min\bigg(K, \frac{ \sqrt{\max( S, \exp(ε) + 1) S A K (\exp(ε) + 1)}}{\exp(ε) - 1}\bigg), up to constants and a log⁡(A)\sqrt{\log(A)} factor. The upper bound is achieved by an adaptation of EXP3 and a unary encoding mechanism. When H>1H > 1, and for small εε, we show a lower bound in Ω(HSAKε)Ω(HS\frac{\sqrt{A K}}ε) and an upper bound in O~(H2S2AKε)\tilde{O}(H^2 S^2 \frac{\sqrt{ AK}}ε). The upper bound is achieved by an algorithm based on UCBVI and a unary encoding mechanism. For small εε, these bounds improve the previously known lower bound by a factor S\sqrt{S} and the previously known upper bound by a factor of HAH \sqrt{A}.
Oct 31, 2026

Infinite Quantiles Inference under Local Differential Privacy

We study simultaneous quantile inference under local differential privacy for a number of target probabilities that grows with the sample size. Each user participates once, so learning unknown quantile locations and calibrating their joint uncertainty must share the same private information. We fuse complementary cumulative distribution function (CDF) scores from a single tree report using their exact covariance; the variance at the correct anchor is no larger than that of either score, and anchor error incurs only quadratic excess variance. Three consecutive cohorts then localize the quantiles, estimate their densities, and supply fresh scores for a one-step correction and joint multiplier calibration. Under mild conditions, a uniform representation controls localization and density errors and yields asymptotically valid simultaneous coverage. A fixed-privacy regime permits every polynomially growing target grid. Simulations show consistent same-report precision gains, while comparisons with CDF-band inversion expose the sample cost of learning target locations. Census microdata illustrates how the resulting joint intervals support wage-percentile ratios.
Oct 31, 2026

Private Uniform Language Generation

We study uniform language generation under approximate differential privacy. Given a uniformly bounded number of distinct examples from an unknown target language, a generator must produce infinitely many new examples from that language with probability one while protecting the privacy of its input. We introduce a new combinatorial dimension termed the nested branching dimension and prove that a language class is privately uniformly generatable if and only if both its closure dimension and nested branching dimension are finite. Previous work characterizes non-private uniform generation by the finiteness of the closure dimension alone. Our results therefore identify an additional combinatorial obstruction imposed by privacy.
Oct 30, 2026

Counting on Dummies: Privacy Amplification with Observable Counts and Truncated Batches

In many practical deployments of Differentially Private Stochastic Gradient Descent (DP-SGD), the server processes data in batches. Randomly sampling these batches allows for better privacy bounds via privacy amplification results. Most sampling schemes with provable privacy amplification, including Poisson sampling and random allocation, result in variable batch sizes. The privacy guarantee of these schemes requires that the batch sizes are not revealed. In distributed settings, the server performing the aggregation or any party observing the communication traffic may learn these batch sizes. Furthermore, in both centralized and distributed settings, memory and computation constraints may require each batch to be of some maximum size ss, necessitating truncation of the batch when it exceeds this limit. It is known that this truncation can result in a significant increase in privacy loss. In this work, we address both of these challenges via a simple mechanism that uses a random number of dummy points to privatize the batch size and maintain the privacy guarantee even under truncation. We demonstrate that our mechanism is easy to implement in a distributed setting, and provide a general analysis of this mechanism for both Poisson sampling and random allocation. Our analysis is designed to support efficient and relatively tight privacy accounting. It also effectively amplifies the privacy of the count releases by subsampling, making the expected number of dummy points asymptotically smaller than what is needed to directly privatize the (sensitivity-one) batch sizes with non-negative noise. For Poisson sampling with truncated batches, we demonstrate empirically that our mechanism achieves better privacy--efficiency tradeoffs than the direct accounting for truncation recently given by (Ganesh, 2025).
Oct 30, 2026

Fast Privacy Loss Accounting for Random Allocation via Multiscale FFT

In the random allocation sampling scheme each user's data is used in kk steps chosen randomly and uniformly from a sequence of tt steps. This scheme is known to improve on Poisson sampling in private optimization and in communication-efficient aggregation. The existing privacy loss distribution (PLD) accountant for this scheme runs in time quadratic in the inverse of the accuracy parameter αα (Feldman and Shenfeld, 2026). We give an algorithm, multiscale FFT, that represents likelihood ratios on a grid that is uniform within each dyadic interval and computes the exact rounding of every pairwise sum using FFTs within each interval. It keeps the guarantees of the accountant and improves the dependence of its running time on αα from O(α−2)O(α^{-2}) to O(α−1log⁡(1/α))O(α^{-1}\log(1/α)). In addition, we demonstrate that rounding can be performed via the mean-preserving connect-the-dots projection of (Doroshenko et al., 2026). This reduces the errors that rounding introduces in the mean of the privacy loss and in the χ2χ^2 divergence of the computed pair from the order of αα to O(α2/log⁡(t))O(α^2/\log(t)). In our experiments, our algorithm achieves speedups of several orders of magnitude at high accuracy and gives improved privacy bounds for DP-SGD with PREAMBLE.
Oct 30, 2026

New Lower Bounds for Private PAC Learning

We study realizable PAC learning under approximate differential privacy, and give a framework for proving lower bounds on its sample complexity. We construct classes with identical VC and Littlestone dimensions but different private sample complexities at common privacy and accuracy parameters, showing that these dimensions do not determine the sample complexity, even for improper learners. To address this we introduce the Independent Class Packing (ICP) parameter, the largest total sample complexity of classes in G\mathcal{G} that can be packed independently into a class H\mathcal{H}, and prove that every (ε,δ)(\varepsilon, δ)-DP, (α,β)(α, β)-PAC learner for H\mathcal{H}, possibly improper, uses Ω(ICP(H,G)/(αε))Ω\left(\mathrm{ICP}(\mathcal{H}, \mathcal{G})/(α\varepsilon)\right) examples. Using this framework we prove tight lower bounds for axis-aligned rectangles, union of intervals and linear subspaces and improved lower bounds for halfspaces and convex polygons. Finally we also show that for product classes, and more generally when the same classes pack into H\mathcal{H} and cover its domain so that target labels can be used directly, ICP characterizes private PAC sample complexity up to logarithmic factors.
Oct 30, 2026

TADP: Dual-Branch Temporally Adaptive Differential Privacy for Expression-Aware Video Anonymization

We present TADP, a temporally adaptive differential privacy (DP) framework for inference-time privacy-preserving video generation under fixed-length clip-replacement adjacency. TADP uses a dual-branch design to extract identity and expression representations, clips and privatizes both branches with temporally adaptive Gaussian mechanisms whose noise scales depend only on preceding privatized releases within the same clip and are bounded below by history-uniform calibrated minima, and accounts for their joint release via adaptive Rényi Differential Privacy (RDP) composition. The clip-level RDP guarantee is converted to (ε,δ)(\varepsilon,δ)-differential privacy, while soft quantization and subsequent temporal processing are applied only after privatization as DP post-processing. Experiments on facial expression datasets show reduced identity leakage under evaluated attacks, usable perceptual quality and temporal stability, and high facial expression recognition utility relative to the evaluated privacy-preserving baselines. TADP formally satisfies clip-level DP and empirically provides a favorable privacy--utility trade-off under the evaluated threat models and datasets.
Oct 29, 2026

Communication-Efficient Private Federated Reinforcement Learning with Post-Quantum Authentication for Vehicular Networks

Federated reinforcement learning supports cooperative vehicular routing without centralizing trajectory data, but model updates may reveal private information and incur communication overhead over intermittent vehicle-to-infrastructure links, particularly when post-quantum authentication is required. We study correlated private quantization, using complementary shared randomness between paired vehicles to reduce aggregation mean squared error while preserving the marginal parameter-level local differential privacy and one-bit communication cost of independent quantization. A tunable extension mixes shared and independent randomness to bound privacy leakage given paired outputs and shared-randomness side information. For this extension, Rényi differential privacy accounting establishes vector-level local differential privacy for one model upload even when pairings are revealed. Under matched vector-level privacy and identical local and global parameters, the extension yields 16.5% lower analytical aggregation mean squared error than independent quantization. We evaluate cooperative routing by coupling traffic simulation with packet-level simulation of post-quantum-authenticated vehicle-to-infrastructure communication. Compared to full-precision updates, one-bit uploads reduce authenticated uplink size by 92.4% and increase mean verified updates aggregated per round from 19.6 to 26.5. Under mobility-constrained communication at a parameter-level privacy budget of 1, correlated private quantization reduces mean travel time by 14.3% relative to independent quantization at the same budget and communication cost. At a parameter-level privacy budget of 0.3, a vehicle-origin inference attack trained on independent simulations reaches 30% accuracy with correlated private quantization and 22% with independent quantization after 100 rounds, versus 91% without privacy and 10% for random guessing.
Oct 29, 2026

Propose-Filter-Release: Scaling Noise to Typical Sensitivity via Private Filtering

Differential privacy requires that algorithms be stable to the change of any record in their input, even to an extreme outlier. Private algorithms thus commonly introduce noise scaled to the worst-case possible influence of any single record. This work studies how to build differentially private algorithms that can effectively tailor their noise to the typical case rather than the worst case. We introduce the general propose-filter-release (PFR) framework, which, by privately filtering its input, turns a mechanism that protects the addition or removal of a typical record into one that is differentially private in the standard sense, on every input. We show how to instantiate PFR with a novel filtering step to obtain a general meta-algorithm. Given only a concave friendliness score (which measures how typical a record is with respect to a dataset) and a release mechanism that is friendly-DP (that is, private conditioned on the changed record being typical of the remaining data), it guarantees differential privacy on sufficiently large datasets. The FriendlyCore [TCK+22] and Propose-Test-Release [DL09] algorithms can be viewed as instantiations of our general approach. We illustrate the generality of PFR by instantiating it for scalar statistics, principal subspace estimation with a dimension-independent sample size, the KL divergence of user histograms, the effective resistances in a resistor network, and treatment-rule selection.
Oct 26, 2026

Privately Clipping Heavy-Tailed Data

Summing vectors is a basic task in differentially private data analysis. Standard private sum algorithms clip vectors to some bound, sum them, and add noise scaled to the bound. The differential privacy literature has developed a deep library of noise addition mechanisms, but it offers few tools for privately choosing a clipping bound based on the data. We introduce a method that privately chooses a clipping bound by optimizing residual coherence, the directional alignment of vectors exceeding the bound, against the variance cost of additional noise. We prove a close relationship between residual coherence and bias for a general class of heavy-tailed data regimes and show empirically that, across several datasets, our method outperforms existing baselines.
Oct 24, 2026

Projection-Based Federated Learning on Compact Submanifolds with Geometry-Independent Differential Privacy

Federated learning trains a shared model across clients without exchanging their data, yet the updates they transmit still leak information about individual records. Enforcing differential privacy is harder still when the model parameters lie on a Riemannian manifold. Existing methods rebuild the noise added for privacy in the geometry of each new iterate, aggregate through intrinsic maps that often lack a closed form, and prove convergence only in restricted regimes. We introduce DP-RFedProj, a record-level differentially private federated learning method for compact submanifolds that aggregates through closed-form projections and privatises gradients in a fixed ambient geometry. Each client may run any stochastic first-order optimiser, take several local steps, and participate only intermittently. An explicit record-level ff-DP guarantee holds for the entire training transcript, independently of the manifold, the aggregation scheme and the local optimiser. We establish convergence of DP-RFedProj when each client runs Riemannian SGD locally and the server aggregates by projected averaging, and show that privacy enters the rate through a term scaling with the manifold's intrinsic dimension rather than the ambient one. Synthetic experiments on federated PCA over the Grassmann manifold corroborate these findings. On EEG motor-imagery classification with SPDNet, whose weights lie on the Stiefel manifold, the method outperforms a Euclidean baseline at every privacy budget considered. In both experimental settings, our accounting requires five to six times less noise than that of the closest prior method for the same budget, which translates into higher utility.
Oct 23, 2026

Gaussian Approximation for Composition and Subsampling of Differentially Private Algorithms

The privacy analysis of differentially private stochastic gradient descent (DP-SGD) relies on bounds for the composition of subsampled mechanisms. The privacy of such a composition is bounded by that of a pair of product distributions, whose privacy loss is a sum of independent terms and has been analyzed via a variety of notions and concentration results. Yet, existing closed-form bounds either lose a logarithmic factor or require restrictive conditions on the noise scale and delicate analysis of subsampling. Further, while it is well known that sums of independent random variables are approximately Gaussian, existing CLT-based techniques give an approximation with a large error in δδ. We show that the privacy loss of this pair is approximately Gaussian as long as each step has a small privacy loss except with small probability. Specifically, its privacy loss distribution is close to a Gaussian with the same mean and variance, after truncating the rare large privacy losses. The closeness in both directions is up to a shift of ε\varepsilon that grows only as ln⁡(1/β)\ln(1/β) for an additive error ββ in δδ and is a lower-order term in typical applications. In particular, the composition satisfies Gaussian differential privacy up to a lower-order shift of ε\varepsilon and the additive error ββ. We also give a simple way to analyze the resulting variance-based bounds for subsampled mechanisms which relies on the χ2χ^2 divergence of a single step. For the Gaussian mechanism at sampling rate 1/t1/t and t>ln⁡3(1/δ)t>\ln^{3}(1/δ), this gives the predicted rate for σ≳max⁡{1,ln⁡(1/δ)/ln⁡(t)}σ\gtrsim\max\{1,\sqrt{\ln(1/δ)}/\ln(t)\}, whereas the standard Rényi-divergence analyses need σ≳tln⁡(1/δ)/ln⁡(t)σ\gtrsim\sqrt{t\ln(1/δ)}/\ln(t). We extend these results to random allocation (balls-and-bins sampling), and show that it explains the high accuracy of the connect-the-dots method.