CS Paper Radar

Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries

Surendra Ghentiyala, Pritish Kamath, Ravi Kumar, Pasin Manurangsi

cs.CR cs.CC ·submitted 2026-09-02 17:56 UTC · v1

Abstract

We study the question of answering linear queries with differential privacy using few (expected) random bits. We provide a randomness-efficient analog of the $\| \cdot \|_K$-norm mechanism of Hardt and Talwar [HT10]. For the $\ell_\infty$-error, our algorithm can answer $d$ linear queries with $O(d / \varepsilon)$ error using $O(\log d)$ random bits, improving upon algorithms of Canonne et al. and Ghentiyala [CSV25, Ghe26]; this is optimal when $\varepsilon \le 1/d$. We also provide a computationally efficient version of our algorithm, albeit with an $O(\log d)$ multiplicative increase in the error.

Closest papers

Nearest neighbours by meaning across the whole index.

Private Online Release of Adaptive Linear Queries

cs.DS ·2026-11-03 ·Aleksandar Nikolov, Haohua Tang
theory similarity 0.74
Abstract

In this paper we study answering counting and other linear queries online under differential privacy constraints. Recent work by Nikolov, Tang, and Ullman [STOC 2026] gave the first online algorithm that answers \emph{obliviously chosen} online linear queries privately, and achieves poly-logarithmic competitiveness against an optimal offline factorization mechanism. This also implied poly-logarithmic competitiveness against arbitrary private offline mechanisms when the private dataset is large enough. The error guarantees of their algorithm, however, can fail when the queries are adaptive. We give a new algorithm that also achieves poly-logarithmic competitiveness, while being able to handle \emph{adaptively chosen} queries. This implies that there is no large separation between the optimal error bounds for privately answering, respectively, offline linear queries, obliviously chosen online linear queries, and adaptively chosen online linear queries. Our algorithm combines the online factorization approach from prior work with a novel layered Euclidean iterative database construction, presenting a new way to use factorization in private algorithms. We also give a lower bound that shows that some poly-logarithmic factor in the competitive ratio is unavoidable. Our lower bound first shows that any interactive private mechanism implies a deterministic online factorization algorithm, and then gives a new lower bound for the competitive ratio of any deterministic online factorization algorithm.

0.06

Complexity of Differentially Private Selection via Federated APIs

cs.CR cs.DS ·2026-10-28 ·Hilal Asi, Vitaly Feldman, Jelani Nelson, Huy L. Nguyen, Kunal Talwar +1 more
published similarity 0.74
Abstract · NeurIPS 2026

Differential privacy (DP) has become the standard for privacy-preserving data analysis, yet its practical implementation in federated or distributed settings often faces a significant utility gap compared to the central model. While existing frameworks, including local, shuffle, and secure aggregation models, offer vetted primitives, they can incur high error for important tasks such as selection. Our first contribution is to show that this is inherent in the aggregation model: any private selection algorithm relying on the standard noisy aggregation primitive requires $Ω(\sqrt{d}/\varepsilon)$ samples. To address this limitation, we propose adding a new primitive that implements a version of the Sparse Vector Technique (SVT) and argue that it has simple implementations under various trust models. We demonstrate its power by developing an $\varepsilon$-differentially private algorithm for the selection problem. For selection in dimension $d$, our algorithm achieves an additive error of $O\left(\frac{\log(dn)}{\varepsilon}\right)$, matching that of the central model when $n$ is polynomially bounded in $d$. Furthermore, we show that this can be done using a near-optimal expected number $O(d\log^*d)$ of SVT queries. Together with existing lower bounds for the shuffle model, this result establishes an exponential separation between the SVT model and shuffle or aggregation-based models. We demonstrate the model's broad applicability to diverse tasks such as $F_p$ loss minimization, heavy-hitter identification, and sparse mean estimation.

0.20

Gaussian Approximation for Composition and Subsampling of Differentially Private Algorithms

cs.LG ·2026-10-23 ·Vitaly Feldman, Moshe Shenfeld
similarity 0.70
Abstract

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/β)$ 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$ divergence of a single step. For the Gaussian mechanism at sampling rate $1/t$ and $t>\ln^{3}(1/δ)$, this gives the predicted rate for $σ\gtrsim\max\{1,\sqrt{\ln(1/δ)}/\ln(t)\}$, whereas the standard Rényi-divergence analyses need $σ\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.

0.41

Pure Differentially Private Query Release via Laplace Input Smoothing

cs.DS ·2026-11-03 ·Zongrui Zou
theory similarity 0.70
Abstract · 35 pages

We study the offline release of a public family of $k$ statistical queries on a database of $N$ records from a public universe of size $d$, under pure $\varepsilon$-differential privacy. We give an efficient algorithm that, with probability at least $1-β$, answers all queries simultaneously to error $$O\left(\min\left\{1,\sqrt{\frac{\log(d/β)\log k}{N\varepsilon}}\right\}\right).$$ The output is a synthetic histogram on the data universe, and its running time depends polynomially on $N,d$ and $k$. This resolves a conjecture of Nikolov and Ullman (2021) with an efficient, polynomial-time construction. Fitzsimons (2026) recently established the same square-root error scale via an information-theoretic construction that relies on a computationally intractable Lipschitz envelope over the exponential space of possible outputs. In contrast, we introduce an input-side smoothing approach: we run a selection-only multiplicative-weights process after a single sparse Laplace perturbation of the input histogram. Departing from standard first-order stability analyses, we investigate the stability of stability by establishing a uniform lower bound on the second-order log-derivatives of the output transcript across $T$ rounds of multiplicative weight updates. We then develop an analytic smoothing principle showing that this curvature bound allows a sparse, coordinate-wise perturbation to guarantee pure differential privacy globally, attaining optimal utility through a conceptually simple, polynomial-time pure-DP mechanism.

0.18

Tight Lower Bounds for Differentially Private Continual Counting

cs.DS cs.CR ·2026-09-15 ·Charlie Harrison, Ethan Leeman
theory similarity 0.69
Abstract

The Binary Tree Mechanism is a standard algorithm for differentially private continual counting, but its asymptotic optimality under pure differential privacy has remained unresolved since its introduction. We resolve this question. For fixed $0 < \varepsilon \le 1$, we prove asymptotically tight lower bounds of $Ω(\log^2 n)$ for worst-case expected $\ell_\infty$ error and $Ω(\log^3 n)$ for mean and maximum per-coordinate expected squared error. These bounds hold for arbitrary mechanisms, even when the entire stream is available in advance. The same lower bounds hold under approximate differential privacy whenever $δ\le n^{-c}$, for any fixed $c>0$. Our lower bounds match the Binary Tree Mechanism instantiated with Laplace noise, establishing its asymptotic optimality under both pure differential privacy and approximate differential privacy in the standard regime of $δ\ll1/n$. Our proof uses a single hard distribution with a bounded exponential score on a tree. A simple modification of the score allows the same framework to establish tight lower bounds for all three error measures.

0.42

Private Online Prediction from Experts with Small Losses

cs.LG stat.ML ·2026-10-21 ·Bo Li, Peng Ye
theory similarity 0.69
Abstract

We consider online prediction from experts, a fundamental problem in machine learning, under differential privacy constraints. Existing private algorithms achieve near-optimal regret $\tilde{O}(\sqrt{T})$, where $T$ is the time horizon. However, this bound becomes suboptimal when $L^\star$, the cumulative loss of the best expert, is significantly less than $T$. In this work, we present the first differentially private algorithm with regret $\tilde{O}(\sqrt{L^\star})$, offering a substantial improvement in the low-loss regime. Our regret bound matches the non-private lower bound up to poly-logarithmic factors for constant privacy parameters, demonstrating that privacy incurs only a small cost in this setting. Our result assumes that the input sequence is oblivious, i.e., it is fixed in advance and independent of the algorithm's outputs. We also prove that an $\tildeΩ(\sqrt{T})$ regret is inevitable for adaptively generated inputs, even when $L^\star = 0$.

0.17

Residual Privacy Budgeting with Weighted Scarcity Allocation for Online Query Answering

cs.DB cs.DS ·2026-08-23 ·Mina Khoshmehr, Fernando Beltran
theory similarity 0.68
Abstract · 13 pages. Presented as a poster at the Learning Theory Workshop, University of Copenhagen, June 2026

In many practical deployments of differential privacy, queries do not arrive all at once. We study online differentially private query answering under a finite zero-concentrated differential privacy (zCDP) contract. In this setting, queries arrive sequentially, carry different accuracy thresholds, and may overlap with information already released. We formulate this setting as residual privacy budgeting: for each arriving query, the mechanism first credits reusable support from previous DP outputs and then spends new budget only on the remaining support required to satisfy the current threshold. The controller separates feasible cases, where the minimal residual support is allocated exactly, from scarcity cases, where a weighted shortfall-conservation optimiser assigns limited support according to query difficulty. We define the weight using the Query Influence Factor (QIF), a diagnostic signal for query difficulty and instability rather than query importance. For scalar Gaussian exact reuse, inverse-variance fusion justifies additive support. We prove zCDP composition, residual minimality, 1-competitiveness against the offline optimum in the feasible regime, and avoidable expenditure for allocators that ignore released history. A scarcity impossibility result shows that no online allocator can guarantee a competitive ratio better than 1/n in threshold satisfaction, contextualising the QIF scarcity layer as a design choice for an inherently hard online problem.

0.44

Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds

cs.DS cs.CR ·2026-09-11 ·Pritish Kamath, Ravi Kumar, Pasin Manurangsi
theory similarity 0.67
Abstract

We study combinatorial optimization problems under the constraint of $ε$-differential privacy ($ε$-DP). Given the strong lower bounds for explicitly outputting solutions, we work within the implicit representation framework of Gupta et al. (SODA 2010), where a private polynomial-time randomized "encoder" generates a representation of a solution, and a "decoder" uses this representation along with the input to extract a valid final solution. In this work, we generalize this framework by allowing the encoder to run in fixed-parameter tractable time. This circumvents approximation barriers inherent to polynomial-time algorithms and obtains improved guarantees for many fundamental combinatorial optimization problems. Finally, we establish the first representation-independent lower bounds for our framework. Assuming a non-uniform variant of the Gap Exponential Time Hypothesis, for sufficiently small $ε> 0$, we prove that no $ε$-DP encoder-decoder pair can achieve certain approximation guarantees, if the decoder runs in subexponential time. We further provide representation-dependent lower bounds that hold even for larger $ε$.

0.39