Tessera

Differential Privacy Papers

@dppapers.bsky.social

🤖 new arXiv preprints mentioning "differential privacy" or "differentially private" in the title/abstract - unrelated quantum/FL papers + updates from https://differentialprivacy.org [Under construction.]

1548 Posts537 Follower 0 Folgt

Differential Privacy Papers @dppapers.bsky.social · 15h ago

DP-MemView: A Memory Interface for Attribute-Level Transcript Privacy in Long-Term LLM Agents Jong Wook Kim, Byoungjae Min, Kennedy Edemacu, Yoonhyuk Choi, Sae-Hong Cho, Beakcheol Jang http://arxiv.org/abs/2608.03130

Differential Privacy Papers @dppapers.bsky.social · 15h ago

FedGSA: Geometry-Consistent Subspace Aggregation for Differentially Private Federated LoRA Lele Zheng, Ruijie Hu, Tao Zhang, Ke Cheng, Yulong Shen http://arxiv.org/abs/2608.03267

Differential Privacy Papers @dppapers.bsky.social · 15h ago

Noise-Aware Shrinkage for Differentially Private Zeroth-Order Fine-Tuning of Large Language Models Lele Zheng, Weifeng Kong, Xinyi Zhang, Ke Cheng, Tao Zhang, Yulong Shen http://arxiv.org/abs/2608.03277

Differential Privacy Papers @dppapers.bsky.social · 15h ago

Dependency Triad: A Metric to Quantify the Dependencies Between Attributes for Local Differential Privacy Sandaru Jayawardana, Sennur Ulukus, Ming Ding, Kanchana Thilakarathna http://arxiv.org/abs/2608.03737

$Dependency Triad: A Metric to Quantify the Dependencies Between Attributes for Local Differential Privacy Sandaru Jayawardana, Sennur Ulukus, Ming Ding, Kanchana Thilakarathna http://arxiv.org/abs/2608.03737 Collecting multidimensional user data is essential for extracting rich insights across various applications. Local Differential Privacy (LDP) has emerged as a de facto standard for mitigating privacy risks in such scenarios. A key challenge in privacy-preserving multidimensional data collection lies in inter-attribute dependencies, as they can inadvertently reveal correlated information and increase privacy vulnerabilities. Therefore, accurately measuring correlation-induced privacy leakage (CPL) is essential for privacy analysis and privacy-utility trade-off. However, existing CPL analysis solutions either require accurate prior knowledge or face scalability challenges for large numbers of attributes and high-cardinality attributes. These limit their practical applicability in real data. To address this research gap, we propose a novel metric, ``Dependency Triad'' (DT), which summarizes the pairwise dependency information relevant to CPL using three parameters and yields a \emph{constant-time} conservative estimator of pairwise CPL. DT explicitly models uncertainty in prior distributional knowledge through its parameters, delivering robust leakage estimates. Moreover, its robustness to sparse distributions makes it particularly suitable for high-cardinality attributes, while the pairwise formulation serves as a tractable building block for assessing total leakage in multidimensional settings. Extensive experiments on both synthetic and real datasets demonstrate that DT consistently estimates CPL across diverse dependency regimes and prior uncertainties.$

Differential Privacy Papers @dppapers.bsky.social · 2d ago

Similarity Weighted Aggregation with Global Differential Privacy for Federated Brain Lesion Segmentation Muhammad Irfan Khan, Eero Lehtonen, Joni Obradovic, Elina Kontio, Esa Alhoniemi, Suleiman A. Khan, Mojtaba Jafaritadi http://arxiv.org/abs/2608.00872

Differential Privacy Papers @dppapers.bsky.social · 2d ago

Bridging Differential Privacy and Random Triangles Tianxi Ji http://arxiv.org/abs/2608.01412

Differential Privacy Papers @dppapers.bsky.social · 2d ago

Private Generative Bootstrap via Blocking Jinwon Sohn, Veronika Ročková http://arxiv.org/abs/2608.02480

Differential Privacy Papers @dppapers.bsky.social · 3d ago

Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting Awnon Bhowmik, Mahmudul Hasan http://arxiv.org/abs/2607.28703

$Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting Awnon Bhowmik, Mahmudul Hasan http://arxiv.org/abs/2607.28703 Let $T_n$ be the lower-triangular prefix-sum matrix and let $\cfrob(T_n)$ and $\ctwo(T_n)$ be the factorization costs that govern mean and maximum per-coordinate squared error of the Laplace matrix mechanism under pure $\eps$-differential privacy, for $\eps>0$. We prove $\cfrob(T_n),\ctwo(T_n)=Θ\bigl((\log(n+1))^{3/2}\bigr)$ with no sign, sparsity, or squareness restriction and with arbitrary finite inner dimension. Consequently, within the pure-$\eps$-DP matrix-mechanism class the optimized maximum and mean squared errors are both $Θ(\eps^{-2}\log^{3}(n+1))$. Under the factorization contract of Arkhipov and Kalinin (arXiv:2607.08963v1), who prove the matching lower order for factors with entries in $\{0,1\}$ and state the arbitrary-factor extension as open, the theorem below establishes the order for arbitrary real factors. The lower bound runs through a $p$-nuclear obstruction: an aggregate column-width estimate $D_k(T_n)\asymp n^{3/2}k^{-1/2}$, valid in the low-rank range $1\leq k\leq n/16$, for the prefix chain, fed into the classical approximation-space conversion of Pietsch and Hinrichs--Pietsch, becomes harmonic at the critical exponent $p=2/3$, and Hölder's inequality transfers it to both factorization costs. The same computation determines $\nucpow_p(T_n)$ for each fixed $0<p<1$: order $n$ below $2/3$, $n\log n$ at $2/3$, and $n^{3p/2}$ above. A Fenwick interval factorization supplies matching upper bounds. The claims are confined to pure-$\eps$-DP Laplace matrix mechanisms and the two stated squared-error criteria; they do not cover non-matrix continual mechanisms, approximate-DP sensitivity, or expected maxima across coordinates.$

Differential Privacy Papers @dppapers.bsky.social · 3d ago

A Matrix Factorization Approach in Turnstile Streaming Jan Bulanek, Ravi Kumar, Raghu Meka, Jelani Nelson, Tamas Sarlos http://arxiv.org/abs/2607.28819

$A Matrix Factorization Approach in Turnstile Streaming Jan Bulanek, Ravi Kumar, Raghu Meka, Jelani Nelson, Tamas Sarlos http://arxiv.org/abs/2607.28819 We define the $M$-point query problem in data streams. Given a fixed matrix $M$, the goal is to maintain a vector $x$ under turnstile updates and answer each query $u$ with an estimate $\widehat{y}_u$ satisfying $|y_u-\widehat{y}_u| \leq \varepsilon \|x\|_1$, where $y=Mx$. We show that if $M$ admits a factorization $M=AB$, where $A$ and $B$ have space-efficient representations, then there is a streaming algorithm using $O(\varepsilon^{-1}\|A\|_{2\rightarrow\infty}\|B\|_{1\rightarrow 1}+(\varepsilon^{-1}\|A\|_{\infty\rightarrow\infty}\|B\|_{1\rightarrow 1})^{2/3})$ words of memory. An important special case is the lower-triangular all-ones matrix, which corresponds to the quantiles problem with additive error $\pm \varepsilon n$, where $n$ is the database size. Our framework generalizes the dyadic approach of Cormode and Muthukrishnan (J. Algorithms, 2005) for turnstile quantiles, and simplifies and improves the analysis of the state-of-the-art dyadic CountSketch algorithms of Wang et al. (SIGMOD, 2013) and Luo et al. (VLDB, 2016). Our approach is also related to the matrix mechanism of Li et al. (VLDB J., 2015) in differential privacy: given a database $x\in\mathbb{R}^U$ and a matrix $M$, the mechanism outputs a private approximation to $Mx$, with the privacy-error tradeoff governed by a matrix factorization norm of $M$. We also improve the prior lower bound for quantiles with deletions, showing a memory lower bound of $Ω(\varepsilon^{-1}\log U)$ words. We also show any factorization has $\|A\|_{2\rightarrow\infty}\|B\|_{1\rightarrow 1} = Ω((\log^{1.5} U) / \log\log U)$. This lower bound is new, and shows that for quantiles, the dyadic CountSketch is nearly optimal amongst factorization-based approaches.$

Differential Privacy Papers @dppapers.bsky.social · 3d ago

MESS: Fast and Private Semantic Search on Multi-Graph HNSW Haoyu Cui, Zengpeng Li, Tien Tuan Anh Dinh, Mei Wang http://arxiv.org/abs/2607.28999

$MESS: Fast and Private Semantic Search on Multi-Graph HNSW Haoyu Cui, Zengpeng Li, Tien Tuan Anh Dinh, Mei Wang http://arxiv.org/abs/2607.28999 Semantic search systems map data to a high-dimensional vector space and support retrieval of similar data via approximate nearest neighbor search. When the system is hosted by a trusted cloud provider, there is no privacy for the data or the query. Our goal is to design a system with three properties: privacy, accuracy, and efficiency. Existing works adopt either homomorphic encryption (HE), oblivious RAM (ORAM), or a differential privacy (DP) approach. They fall short of achieving all three properties. In this paper, we present MESS, a system that realizes our goal. It maps the original vectors into binary codes, applies locality-sensitive hashing (LSH) and randomized response, and constructs a multi-graph Hierarchical Navigable Small World (HNSW) index over the perturbed codes. MESS ensures data, query, and access pattern privacy. It also ensures search pattern privacy via a two-phase query perturbation mechanism. The multi-graph index mitigates the impact of perturbation on result quality, thereby achieving accuracy. MESS is efficient because search is performed directly over perturbed codes, without the overhead of homomorphic encryption or ORAM. We give formal analysis of the system's privacy and extensive evaluation of its performance. The results show that MESS achieves up to 15.08\times lower latency than state-of-the-art baselines.$

Differential Privacy Papers @dppapers.bsky.social · 3d ago

StraightDP: Geometry-Aware Differential Privacy for Rectified-Flow Transformers Xujun Che, Depeng Xu, Xintao Wu http://arxiv.org/abs/2607.29100

$StraightDP: Geometry-Aware Differential Privacy for Rectified-Flow Transformers Xujun Che, Depeng Xu, Xintao Wu http://arxiv.org/abs/2607.29100 Differentially private (DP) training of text-conditioned generative models suffers a utility cliff at strong privacy. We revisit this problem through the geometry of rectified flows: along the straight interpolation between noise and data, the Bayes-optimal velocity is governed to leading order at the noise end by a few class-conditional moments, and increasingly sample-specific structure matters toward the data end. StraightDP exploits this heterogeneity end to end. A small budget share releases whitened class-conditional moments once, to be distilled into the weights or injected at sampling time. The rest is spent by pre-declared DP-SGD toward the data end, beyond the moments' reach. At $\varepsilon=1$ on MNIST, the released moments alone already attain $0.76$ downstream accuracy with prototype-like samples and an FID of $237$, and uniform DP-SGD attains $0.21$. The pipeline built on the release reaches $0.81$ accuracy at FID $56$ in a public latent space. Constraining per-token stream norms of the multimodal backbone leaves the pretraining loss unchanged yet improves downstream accuracy in the extreme-noise pixel-space regime, and its accuracy effect becomes monotonically more favorable as privacy strengthens. The released moments also port to frozen SD3-medium, where sampling-time injection beats DP-LoRA training at a fraction of the budget.$

Differential Privacy Papers @dppapers.bsky.social · 3d ago

Differentially Private Nonparametric Modal Learning with Applications to Regression and Clustering Arkajyoti Bhattacharjee, Arnab Auddy http://arxiv.org/abs/2607.29675

$Differentially Private Nonparametric Modal Learning with Applications to Regression and Clustering Arkajyoti Bhattacharjee, Arnab Auddy http://arxiv.org/abs/2607.29675 Density modes provide a localized and interpretable summary of multimodal distributions, but their estimation under rigorous differential privacy constraints remains largely unexplored. We study differentially private recovery of density modes for multivariate distributions under local smoothness, curvature, and separation conditions. We propose DP-GRAMS, a mean-shift inspired method that performs noisy ascent on a differentially private score estimator. Assuming the density belongs locally to a Hölder class with smoothness parameter $β> 2$, our score estimator uses bias-reducing higher-order kernels, and then enforces privacy in the gradient ascent steps via gradient clipping and calibrated Gaussian noise. A private initialization scheme combines a density-aware utility with a suppression rule and, with $k\asymp M\log n$ draws over a public $h_{\mathrm{DAP}}$-grid and suppression radius $ρ_{\mathrm{init}}\asymp (\log n)^{-1/d}$, achieves high-probability coverage of the modal basins by successively suppressing selected local neighborhoods in competitive regions, while correlated noise across multiple starts enables joint release under a single $(\varepsilon,δ)$-differential privacy guarantee. We prove that all population modes are recovered with high probability and establish asymptotic error rates of the form $O\!\left((\tfrac{\log n}{n})^{\frac{2(β-1)}{d+2β}}\right) + O\!\left((\tfrac{\mathrm{polylog}(n,δ)}{n^2\varepsilon^2})^{\frac{β-1}{d+β}}\right)$. We also provide minimax lower bounds for private mode estimation, and show that our estimators are nearly optimal, up to a logarithmic factor in the MSE. We present two natural extensions: DP-PMS, a private modal-regression method, and DP-GRAMS-C, a clustering pipeline. Extensive experiments on synthetic and real data demonstrate favorable privacy$

Differential Privacy Papers @dppapers.bsky.social · 6d ago

Robust Estimation of Sparse Numerical Vectors under Local Differential Privacy Puning Zhao, Zhikun Zhang, Shaowei Wang, Sheng Yue, Bangzhou Xin, Tianhang Zheng, Pengfei Zhang, Xiaochun Cao http://arxiv.org/abs/2607.27815

Differential Privacy Papers @dppapers.bsky.social · 7d ago

Sensitivity and Differential Privacy in Metric Voting with Distortion below Three Shinsaku Sakaue, Kaito Fujii, Soh Kumabe, Yuichi Yoshida http://arxiv.org/abs/2607.26388

$Sensitivity and Differential Privacy in Metric Voting with Distortion below Three Shinsaku Sakaue, Kaito Fujii, Soh Kumabe, Yuichi Yoshida http://arxiv.org/abs/2607.26388 Voting rules aggregate individual preferences into collective decisions, but the rankings they receive contain only ordinal information. The metric distortion framework studies ordinal voting rules in settings where voters and candidates are embedded in an unknown metric space. Deterministic rules have optimal worst-case distortion $3$, while recent randomized rules break the $3$ barrier. We study whether such improvements can coexist with low worst-case sensitivity with respect to the Wasserstein distance of lotteries under one-voter deletion and approximate differential privacy under one-voter replacement. On the sensitivity side, we give a randomized rule with distortion at most $3-\varepsilon$ for an absolute constant $\varepsilon>0$ and, for $m$ candidates and $n$ voters, a worst-case sensitivity bound of $O((\log m+1)/n)$. On the privacy side, for every $δ\in(0,1)$ and all $n$ above an absolute constant, we construct a variant rule whose mechanism releasing a single sampled winner has distortion at most $3-\varepsilon$ and is $(O((\log m+\log(1/δ)+1)/n),δ)$-differentially private. Both constructions use the same family of Gibbs distributions over constant-size candidate lists, with only the temperature parameter differing between the sensitivity and differential-privacy guarantees. Our analysis builds on the biased-metric viewpoint behind the recent improvement over the $3$ barrier and proves a stability property for the biased-metric ratio.$

Differential Privacy Papers @dppapers.bsky.social · 7d ago

Function Privatization in the Local Model Yuting Liang, Tian Shu, Ke Yi http://arxiv.org/abs/2607.27164

Differential Privacy Papers @dppapers.bsky.social · last wk.

ScoreShield: Differentially Private Release of Similarity Scores Behrooz Razeghi, Parsa Rahimi http://arxiv.org/abs/2607.25041

$ScoreShield: Differentially Private Release of Similarity Scores Behrooz Razeghi, Parsa Rahimi http://arxiv.org/abs/2607.25041 A growing number of applications, such as biometrics and retrieval-augmented generation (RAG), rely on cosine similarity scores computed between vector embeddings of text, images, or audio. These systems return similarity scores through their APIs for ranking and verification. However, such releases can leak information about individual records and enable membership inference attacks. While differential privacy (DP) provides a principled metric for quantifying attack risks, naïve application of DP mechanisms---such as adding i.i.d. Gaussian noise to vector entries---leads to excessive distortion (i.e., low utility) at a given privacy constraint that scales poorly with the number of released scores. We propose \textsc{ScoreShield}, a perturb-then-project mechanism that adds Gaussian noise calibrated to global sensitivity of the chosen score release regime and then projects the result onto the feasibility set of valid cosine objects. \textsc{ScoreShield} satisfies $(\varepsilon,δ)$-DP for releasing similarity score vectors and Gram matrices. We provide utility guarantees for the exact Frobenius metric projection used in the risk analysis, and prove convergence to feasibility for the practical averaged alternating-projection solver used for large-scale Gram releases. For full pairwise cosine Gram release under record-level replacement adjacency, the exact-projection bound improves the $n$-dependence of squared Frobenius risk from $Θ(n^3)$ for the naïve Gaussian baseline to $\mathcal{O}(n^2)$ for fixed privacy parameters, with sharper local bounds at low-rank Grams. We evaluate the mechanism across RAG, face recognition, semantic retrieval, image similarity, and recommender-system tasks.$

Differential Privacy Papers @dppapers.bsky.social · last wk.

To What Extent Can Inherent Communication Noise Guarantee Privacy in Distributed Cooperative Control? Yuwen Ma, Sarah Spurgeon, Tao Li, Boli Chen http://arxiv.org/abs/2607.25564

Differential Privacy Papers @dppapers.bsky.social · last wk.

E-MagDiP: Electro-Magnetic based Differential Privacy for EEG based Community Sensing Ayanga Imesha Kumari Kalupahana, Vishruti Ranjan, Li-Shiuan Peh http://arxiv.org/abs/2607.25968

Differential Privacy Papers @dppapers.bsky.social · last wk.

DP-IVON-Gradsq: Differentially Private Squared-Gradient Improved Variational Online Newton Nour Jamoussi, Ikram Dridi, Giuseppe Serra, Marios Kountouris http://arxiv.org/abs/2607.23649

$DP-IVON-Gradsq: Differentially Private Squared-Gradient Improved Variational Online Newton Nour Jamoussi, Ikram Dridi, Giuseppe Serra, Marios Kountouris http://arxiv.org/abs/2607.23649 Differential privacy provides formal privacy guarantees for training neural networks on sensitive data, while Bayesian deep learning offers a principled framework for uncertainty-aware prediction. Combining these two objectives remains challenging, as privacy noise can interact with the stochasticity introduced by Bayesian posterior sampling. In this work, we investigate differentially private variational Bayesian learning through the Improved Variational Online Newton (IVON) optimizer. We introduce DP-IVON-Gradsq, a private variant of IVON. The proposed method constructs its curvature estimate from the privatized gradient using a noise-corrected squared-gradient estimator, reducing the direct interaction between posterior-sampling noise and privacy noise while preserving the Adam-like computational efficiency of IVON. We evaluate DP-IVON-Gradsq on CIFAR-10 against the standard private optimizers DP-SGD and DP-Adam over a range of privacy budgets. The results show that DP-IVON-Gradsq is competitive under weak-to-moderate privacy constraints, i.e., large-to-moderate values of $\varepsilon$, while degrading under strong privacy. Code is available at https://github.com/NourJamoussi/DP-IVON-Gradsq.git.$

Differential Privacy Papers @dppapers.bsky.social · last wk.

Sharp Minimax Rates for Smooth Two-Sample Testing under Central Differential Privacy Ilmun Kim http://arxiv.org/abs/2607.23974

$Sharp Minimax Rates for Smooth Two-Sample Testing under Central Differential Privacy Ilmun Kim http://arxiv.org/abs/2607.23974 We establish sharp minimax limits for two-sample testing of Hölder-smooth densities under central differential privacy. Given two independent samples, the goal is to decide whether the underlying distributions are identical or separated in $L_1$ distance, while releasing only an $\varepsilon$-differentially private decision. We show that privacy changes the classical smooth-testing boundary through multiple regimes: the optimal separation radius is the maximum of four terms, consisting of the classical nonprivate rate and three distinct privacy-induced barriers. Which barrier is active depends on the privacy budget and the smoothness-to-dimension ratio, yielding a sharp phase diagram. Our upper bound discretizes the samples, applies a private discrete two-sample test to the resulting histograms, and chooses the bin resolution to balance approximation bias, sampling fluctuations, and privacy noise. The procedure also admits a permutation-calibrated implementation with finite-sample type~I error control. For the lower bounds, we combine smooth perturbation constructions with privacy-specific coupling and transport inequalities, showing that all four terms are unavoidable. Finally, when the smoothness is unknown, we develop a multiscale private test that attains the optimal adaptive rate and prove a matching lower bound. Adaptation costs exactly an iterated-logarithmic factor, and this cost appears only in the classical nonprivate term.$

Differential Privacy Papers @dppapers.bsky.social · last wk.

DCS: A Unified Conditional Sensitivity Framework for Cross-Modal Copyright Infringement Detection Xiafeng Man http://arxiv.org/abs/2607.22035

Differential Privacy Papers @dppapers.bsky.social · last wk.

trasgoDP: An Open Source Framework for Releasing Noised Tabular Microdata under Local Differential Privacy Judith Sáinz-Pardo Díaz, Álvaro López García http://arxiv.org/abs/2607.22230

Differential Privacy Papers @dppapers.bsky.social · last wk.

A Maximum Entropy Implementation of Differential Privacy Under Linear Invariants Ryan Lafferty, Anindya Roy http://arxiv.org/abs/2607.22450

Differential Privacy Papers @dppapers.bsky.social · 2w ago

Edit-Neighboring Data Streams and Privacy under Continual Observation Joel Daniel Andersson, Anamay Chaturvedi, Monika Henzinger, Roodabeh Safavi http://arxiv.org/abs/2607.20727

$Edit-Neighboring Data Streams and Privacy under Continual Observation Joel Daniel Andersson, Anamay Chaturvedi, Monika Henzinger, Roodabeh Safavi http://arxiv.org/abs/2607.20727 Differential privacy under Continual Observation (CO) quantifies the loss in privacy that occurs when outputs generated using a stream of sensitive input data are published in the online setting. In this paper, we consider a more stringent notion of privacy compared to prior work wherein an individual's participation may shift the entire stream by a time-step. We define a new notion of edit-neighboring streams that captures this scenario. Our findings are as follows. First, we prove that on a stream of length $T$, every additive-noise mechanism incurs error $\tildeΩ(\min\{T^{1/3}/\varepsilon^{2/3}, T\})$ when required to be $\varepsilon$-DP under CO for edit-neighboring streams. This includes state-of-the-art continual counters constructed via the factorization mechanism that in the standard neighboring setting incur only polylogarithmic additive error. Second, we construct the first mechanisms with polylogarithmic additive error for our more stringent notion of privacy. We show that we can recover the same additive error as in the standard notion of privacy albeit with worse constant coefficients for both arbitrary input streams and sparse streams. Third, we show that the notion of edit-neighboring streams inhabits a `sweet-spot' in terms of generality and additive error incurred. More precisely, we show that the even more general notion of prefix-sum neighboring streams---which arises naturally in reductions for problems under CO---must incur additive error scaling as $\tildeΩ(\min\{T^{1/3}/\varepsilon^{2/3}, T\})$ for any mechanism that is $\varepsilon$-DP under continual observation. Finally, we show empirically on synthetic data that when compared with prior work, our mechanism achieves a superior trade-off between the success probability of a simple distinguishing attack, and the$

Differential Privacy Papers @dppapers.bsky.social · 2w ago

Recovering Clinical Utility Under Differential Privacy: Empirical Validation of Adaptive Federated Aggregation on Heterogeneous Cardiovascular Datasets Rodrigo Tertulino, Laercio Alencar, Ricardo Almeida http://arxiv.org/abs/2607.19403

Differential Privacy Papers @dppapers.bsky.social · 2w ago

End-to-End Differential Privacy in Training Deep Neural Network Classifiers Huaiyuan Rao, Calvin Hawkins, Alexander Benvenuti, Matthew Hale http://arxiv.org/abs/2607.19580

$End-to-End Differential Privacy in Training Deep Neural Network Classifiers Huaiyuan Rao, Calvin Hawkins, Alexander Benvenuti, Matthew Hale http://arxiv.org/abs/2607.19580 Differentially private machine learning enables model training on sensitive data while ensuring that individual data is unlikely to be recoverable from the parameters of the resulting model. However, existing work often privatizes both training inputs and their labels, and these protections may be conservative when labels are public or can be safely made public. Therefore, in this work we propose a novel private training framework that instead privatizes training inputs while keeping labels public. We consider neural networks with softmax output layers, and thus the mapping from training inputs to the output of the softmax layer is a mapping onto the unit simplex. We randomize softmax outputs during training by applying the Dirichlet mechanism to enforce differential privacy for the training inputs, hence the ``end-to-end'' label. Because training data is reused across multiple training epochs, we use the notion of \Renyi differential privacy to formulate tight bounds on the strength of privacy provided by the Dirichlet mechanism across repeated uses. We show empirically that we attain new state-of-the-art accuracy when training from scratch on CIFAR10, MNIST, MedMNIST, FashionMNIST, and SVHN across all privacy budgets evaluated. Notably, when implementing $(ε, δ)$-differential privacy with $δ=10^{-5}$, we improve the prior state-of-the-art accuracy from $78.37\%$ to $88.17\%$ at $ε=4$ on CIFAR10, and our approach has $82.96\%$ accuracy even for $ε=1$, which significantly outperforms prior work.$

Differential Privacy Papers @dppapers.bsky.social · 2w ago

Pure-DP Statistical Query Release at the Conjectured Square-Root Rate Jack Fitzsimons http://arxiv.org/abs/2607.20418

$Pure-DP Statistical Query Release at the Conjectured Square-Root Rate Jack Fitzsimons http://arxiv.org/abs/2607.20418 Nikolov and Ullman asked whether k statistical queries on a universe of size T can be released under pure differential privacy with expected worst-coordinate error at the square-root rate suggested by known lower bounds. We prove their conjectured upper bound. For every database size n and privacy parameter $\varepsilon>0$, there is an $\varepsilon$-differentially private mechanism with expected error $O(\min\{1,\sqrt{\log(2T)\log(2k)/(\varepsilon n)}\})$. This matches the lower-bound dependence in the standard high-dimensional regimes where those bounds apply; the shifted logarithms and outer minimum make the upper bound valid without additional parameter assumptions. The construction starts from a selection-only private multiplicative weights transcript, then replaces its probability mass function by a distance-penalized likelihood envelope. To prove that the modification preserves accuracy, a likelihood-level Maurey argument upper-bounds each Hamming-ball maximum by a small family of auxiliary PMW laws. Renyi moment bounds control nearby balls, a direct mixture bound controls distant balls, and grouping radii at the privacy scale prevents an additional $1/\varepsilon$ factor in the error. The mechanism is information-theoretic. A companion Lean 4 development machine-checks the finite construction, pure privacy after deterministic decoding, and the displayed all-regimes upper bound.$

Differential Privacy Papers @dppapers.bsky.social · 2w ago

Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers Chenglin Fan, Jingcheng Liu, Pan Peng, Hangyu Xu, Zongrui Zou http://arxiv.org/abs/2607.18846

$Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers Chenglin Fan, Jingcheng Liu, Pan Peng, Hangyu Xu, Zongrui Zou http://arxiv.org/abs/2607.18846 We study the problem of releasing a synthetic graph that approximates the sizes of all cuts of an input graph under edge-level differential privacy. If one insists on purely additive error, the optimal worst-case error is $\widetildeΘ(n^{3/2})$. If one allows a small multiplicative slack, an information-theoretic exponential-time mechanism achieves nearly linear additive error, but the best known polynomial-time algorithms have substantially larger error. We give a polynomial-time $(\varepsilon,δ)$-differentially private algorithm which, for every $n$-vertex unweighted graph $G$, outputs a non-negative weighted synthetic graph $\widetilde G$ such that, with high probability, every cut $S\subseteq V(G)$ satisfies \[ |w_G(S)-w_{\widetilde G}(S)| \le γw_G(S)+\widetilde O_{\varepsilon,δ,γ}(n^{13/12+o(1)}). \] This improves the previous polynomial-time worst-case bound $\widetilde O(n^{5/4+o(1)})$ of Aamand et al. (ICML 2025) for mixed multiplicative/additive private cut approximation. The main technical ingredient is a new set of private spectral primitives for bounded-degree graphs, one of them gives spectral error $\widetilde O_δ((nd)^{1/4}/\sqrt\varepsilon)$ in estimating the graph Laplacian for graphs of maximum degree $d$, being the first to beat the standard $\min\{2d,\widetilde O_δ(\sqrt{n}/\varepsilon)\}$ baseline in the high-degree regime. We further develop a primitive with a sharper error dependence on $n$ and $d$ for the downstream cut approximation. Combined with a new edge-sensitive terminal cut oracle with additive error $\widetilde O(n+(n^2M)^{1/3})$ on graphs with $M$ edges, this yields the final worst-case $\widetilde O(n^{13/12+o(1)})$ private cut-release error.$

Differential Privacy Papers @dppapers.bsky.social · 2w ago

Privacy Cost as Equity Input: A Group Fairness Criterion for Differentially Private Machine Learning Rakshit Naidu http://arxiv.org/abs/2607.16620

$Privacy Cost as Equity Input: A Group Fairness Criterion for Differentially Private Machine Learning Rakshit Naidu http://arxiv.org/abs/2607.16620 Differential privacy (DP) is increasingly deployed to limit membership inference risk in machine-learning systems. Prior work has shown that DP-SGD can widen accuracy disparities across demographic groups, but this framing treats fairness as a purely outcome-side concern. We argue that privacy cost, the information leakage borne by each group, is itself a form of harm, and adopt a compensatory-fairness framework in which a group that involuntarily bears greater privacy exposure is owed proportionally greater benefit from the system. From this principle we derive the \emph{Privacy-Cost Equity Ratio} (PCER), a group fairness metric defined as a group's positive prediction rate normalized by its per-group overfitting gap. By a standard membership inference bound, this overfitting gap upper-bounds each group's vulnerability to inference attacks, making PCER a conservative measure of benefit relative to exposure. PCER needs only per-group train and test accuracy (no shadow models), making it a practical post-hoc audit tool. We evaluate PCER alongside standard fairness metrics across six benchmark--attribute combinations spanning tabular and NLP domains, under DP-SGD at a range of privacy budgets, and validate the overfitting-gap proxy against a direct threshold membership-inference attack. The results reveal patterns that outcome-based metrics miss. On COMPAS, PCER uncovers a persistent double disadvantage: the protected group bears both greater privacy exposure and worse predictive outcomes, something demographic parity gap masks entirely. Sensitivity analysis shows very strong privacy guarantees collapse both groups' overfitting to a numerical floor, rendering exposure-based audits uninformative in that regime. Together, these findings show that fairness audits of privacy-preserving systems must account for who bears the$

Differential Privacy Papers @dppapers.bsky.social · 2w ago

Fast and Private Max-Sum Diversification Ron Zadicario, Tova Milo http://arxiv.org/abs/2607.17196