On Differential Privacy for Adaptively Solving Search Problems via Sketching
Shiyuan Feng, Ying Feng, George Z. Li, Zhao Song, David P. Woodruff, Lichen Zhang · 2025
Read On Differential Privacy for Adaptively Solving Search Problems via Sketching by Shiyuan Feng, Ying Feng, George Z. Li, Zhao Song, David P. Woodruff, Lichen Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-05503.txt.
Introduction
Shiyuan Feng and co-authors use differential privacy to protect sketching data structures under adaptive queries, in this 2025 paper. Privacy tools can hide a structure's inner randomness from attackers. That hiding lets many adaptive queries run without breaking the answers.
Past results covered problems that return a number, like a cost estimate. Search problems must return the solution itself, a harder demand. The team investigate how far the privacy trick stretches in that setting. Their work links privacy, streaming algorithms, and dynamic graphs. Data holders could answer repeated searches with less risk of leaking records. The results set limits on how many queries a fixed budget can serve.
Catalog record
| CREATOR | Shiyuan Feng, Ying Feng, George Z. Li, Zhao Song, David P. Woodruff, Lichen Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 132 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-05503
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Differential Privacy for Adaptively Solving Search Problems via Sketching Shiyuan Feng, Ying Feng, George Z. Li, Zhao Song, David P. Woodruff, Lichen Zhang Abstract Recently differential privacy has been used for a number of streaming, data structure, and dynamic graph problems as a means of hiding the internal randomness of the data structure, so that multiple possibly adaptive queries can be made without sacrificing the correctness of the responses. Although these works use differential privacy to show that for some problems it is possible to tolerate T T queries using O ~ ( T ) \widetilde{O}(\sqrt{T}) copies of a data structure, such results only apply to numerical estimation problems , and only return the cost of an optimization problem rather than the solution itself. In this paper, we investigate the use of differential privacy for adaptive queries to search problems, which are significantly more challenging since the responses to queries can reveal much more about the internal randomness than a single numerical query. We focus on two classical search problems: nearest neighbor queries and regression with arbitrary turnstile updates. We identify key parameters to these problems, such as the number of c c -approximate near neighbors and the matrix condition number, and use different differential privacy techniques to design algorithms returning the solution vector with memory and time depending on these parameters. We give algorithms for each of these problems that achieve similar tradeoffs. 1 Introduction In modern algorithmic design, data structures are playing a more and more important role, in particular in the recent breakthroughs in optimization, machine learning and graph problems. These highly efficient data structures are usually randomized, with one crucial distinction from traditional data structures: one needs these data structures to be robust against an adaptive adversary , in which the adversary could design the input to the data structure based on the prior outputs of the data structure. This is often because these data structures are incorporated in an iterative process, where the data structure takes an input formed by the process, returns a result, and the process utilizes the output to form a new input. Hence, the input to a data structure may be highly correlated with the internal randomness of the data structure. Most traditional randomized data structures, unfortunately, are not robust enough to handle this type of task, as they only have probabilistic guarantees against oblivious adversaries 1 1 1 In the remainder of the paper, we will refer to data structures that are robust against an adaptive adversary as adaptive data structures, and data structures that are robust against an oblivious adversary as oblivious data structures. , in which the input sequence to the data structure is predetermined, and independent of its internal randomness. To address this challenge, various reductions have been proposed to build an adaptive data structure from oblivious data structures [ 8 , 24 , 26 , 12 , 48 , 9 , 86 , 7 ] . These reductions usually proceed as follows: (1) create k independent copies of the oblivious data structure, (2) during the query phase sample and query a subset of the data structures, and (3) aggregate the subsampled answers. We focus on the following search data structure problem: we are given n points in \mathbb{R}^{d} represented by a matrix U\in\mathbb{R}^{n\times d} that is allowed to be preprocessed. Given a sequence of adaptive queries or updates \{v_{1},\ldots,v_{T}\} , we need to design a data structure that answers queries efficiently and succeeds with high probability. Throughout the paper we will consider two key examples of this: (1) the first type of problem is the approximate near-neighbor problem, where a query is a c -approximate near-neighbor of v_{t} in U , and (2) the second type of problem is the regression problem, where U is in addition augmented by a response vector b\in\mathbb{R}^{n} , it could be the solution to the regression problem \arg\min_{x\in\mathbb{R}^{d}}\|Ux-b\|_{2}^{2} where either U or b can also be updated by v_{t} . Note that one can interpret regression as an unconstrained search problem over \mathbb{R}^{d} . For a sequence of T adaptive queries or updates, perhaps the simplest reduction is to prepare T copies of an oblivious data structure and for each query, use a fresh new data structure to respond. Since a data structure is never used more than once, an adaptive adversary cannot design adversarial inputs to this data structure, and hence we obtain an adaptive data structure. In fact, this simple approach already has led to many improvements in convex optimization [ 73 , 84 , 57 , 78 ] . However, in many applications, the overhead T in both preprocessing time and space usage is prohibitive, and more time- and space-efficient alternatives are needed. If in addition the adaptive queries are vectors in \mathbb{R}^{d} and each data structure succeeds with constant probability, then one can adapt an \varepsilon -net argument and show that \widetilde{O}(d) 2 2 2 We use \widetilde{O}(\cdot) to suppress polylogarithmic factors in n , d and 1/\delta where \delta is the failure probability of the data structure. oblivious data structures suffice; at query time, one can then sample a logarithmic number of these data structures and output the the best answer. This approach has been widely adapted for problems such as distance estimation [ 24 , 26 ] and approximate near-neighbor search [ 83 , 7 ] , but is insufficient if d\approx T or even d\gg T , which is the case for convex optimization. Moreover, for many machine learning applications, T is often a hyperparameter that could be chosen and is much smaller than d , making the approach based on \varepsilon -net arguments inefficient for these applications. Is it possible to improve upon the solutions that use \min\{d,T\} data structures? In pioneering work of [ 48 ] and further extended by [ 12 ] , it was shown that differential privacy could be utilized to reduce such overhead. In particular, for numerical estimation problems, where one only needs to output a numerical value, these works show that \widetilde{O}(\sqrt{T}) data structures are sufficient. The idea is to view the internal randomness of the oblivious data structures as the private database one would like to protect. Concretely, one prepares \widetilde{O}(\sqrt{T}) oblivious data structures, and for each adaptive query, samples \widetilde{O}(1) of the data structures, and outputs the differentially private median of the answers [ 12 ] . By the advanced composition theorem [ 37 ] , \widetilde{O}(\sqrt{T}) data structures suffice to provide a correct answer to the numerical estimation problem. This leads to drastically improved algorithms when \sqrt{T}\ll d , and in [ 12 ] they apply it to a large number of graph algorithms. This technique was later extended in [ 29 ] for estimating the cost of a regression problem and the value of kernel density estimation. Can these techniques be extended beyond numerical estimation, to search problems? This is a natural question, as instead of the regression cost, one could naturally be more interested in estimating the regression solution and using it to, e.g., label future examples. On the other hand, simply extending the private median framework to high dimensions seems insufficient, as the regression solution could potentially reveal