On Differential Privacy for Adaptively Solving Search Problems via Sketching
Authors: Shiyuan Feng
Ying Feng
George Zhaoqi Li
Zhao Song
David Woodruff
Lichen Zhang
Venue: ICML 2025 oral (2025)
Keywords: data structure
adaptive robustness
differential privacy
Primary area: theory->optimization
TL;DR: We develop data structures for search problems such as regression and nearest neighbor search that are robust against an adaptive adversary.

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$ queries using $\widetilde{O}(\sqrt{T})$ copies of a data structure, such results only apply to {\it numerical estimation problems}, and only return the {\it cost} of an optimization problem rather than the solution itself. In this paper we investigate the use of differential privacy for adaptive queries to {\it 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$-approximate near neighbors and the matrix condition number, and use different differential privacy techniques to design algorithms returning the solution point or solution vector with memory and time depending on these parameters. We give algorithms for each of these problems that achieve similar tradeoffs.

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Shiyuan Feng' Ying Feng? 2 George Z. Li
Zhao Song" 4 David P. Woodruff Lichen Zhang?
Abstract
data structures: one needs these data structures to be robust against adaptive adversary, in which the adversary could design the input to the data structure based on the prior out- puts 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 result, and the process utilizes the output to form 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 adver- saries', in which the input sequence to the data structure predetermined, and independent of its internal randomness.
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 multi- ple possibly adaptive queries can be made with- out sacrificing the correctness of the responses. Although these works use differential privacy to show that for some problems it is possible to tol- erate T queries using Ö(VT) copies of data structure, such results only apply to numerical estimation problems, and only return the cost of optimization problem rather than the solution itself. In this paper, we investigate the use of dif- ferential privacy for adaptive queries to search problems, which are significantly more challeng- ing since the responses to queries can reveal much more about the internal randomness than 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-approximate near neighbors and the matrix condition number, and use different differential privacy techniques design algorithms returning the solution vector with memory and time depend- ing these parameters. We give algorithms for each of these problems that achieve similar trade- offs.
To address this challenge, various reductions have been proposed to build adaptive data structure from oblivious data structures & Nelson, 2020; 2022; Beimel et al., 2022; Hassidim et al., 2022; Brand et al., 2022; Song et al., 2023b; Bateni et al., 2024). These reductions usually proceed as follows: (1) create 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.
et al., 2020; Cherapanamjeri
We focus on the following search data structure problem: we are given n points in Id represented by matrix U e Rnxd that is allowed to be preprocessed. Given a sequence of adaptive queries or updates {uI...., UT). 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 query is c-approximate near- yeir-neighbor of in U, and (2) the second type of problem is the regression problem, where U is in addition augmented by a response vector E IR", it could be the solution to the regression problem arg minger< ||Ux bll2 where either U b can also be updated by ut. Note that one can interpret regression an unconstrained search problem over Rd.
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
'Peking University *MIT *Carnegie Mellon University *University of California, Berkeley. Correspondence to: Zhao Song <magic.linuxkcr wew.liinnndd@@mmllcoom... com, Lichen Zhang Bitchenz@mit.cde
For a sequence of T adaptive queries or updates, perhaps
'In the remainder of the paper, will refer to data struc- tures that are robust against adaptive adversary adaptive data structures, and data structures that are robust against an oblivious adversary as oblivious data structures.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
the simplest reduction is to prepare T copies of an oblivi- ous data structure and for each query, use fresh new data structure to respond. Since a data structure is never used more than once, an adaptive adversary cannot design adver- sarial inputs to this data structure, and hence we obtain an adaptive data structure. In fact, this simple approach already has led to many improvements convex optimization (Lee et al., 2019; Song & Yu, 2021: Jiang et al., 2021: Qin et al., 2023). However, in many applications, the overhead 7 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 I2 and each data structure succeeds with constant probability, then one can adapt an e-net argument and show that (d) 2 obliv- ious 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 (Chera- panamjeri & Nelson, 2020; 2022) and approximate near- neighbor search (Song et al., 2022; Bateni et al., 2024), but is insufficient if d Re T or even d >> T, which is the case for convex optimization. Moreover, for many machine learning applications. T' is often hyperparameter that could be cho- sen and is much smaller than d, making the approach based on c-net arguments inefficient for these applications.
to, e-g., label future examples. On the other hand, simply extending the private median framework to high dimensions seems insufficient, the regression solution could poten- tially reveal much more about the internal randomness of a data structure than what only the cost would reveal. This problem becomes more evident for approximate near neigh- bor search: for this problem, if there exists a row u² of U for which ||ue - =Il S r for an adaptively chosen query v E Rd and a distance parameter r. then the data structure needs to output row ū of U with ö vll S cr for c >> 1. It is not clear how to extend the differential privacy framework to such a scenario, as we will have to return row of U, while the private median mechanism would not be able to do this. Motivated by these problems and barriers, we ask
Is it possible design robust search data structures with fewer than min{d, T} independent copies?
We provide an affirmative answer to this question under mild assumptions on these problems. We start by introducing the definition of the (c. r)-ppoooiimtte Near Neighbor ((e, r) ANN) problem and its corresponding assumption.
Definition 1.1 ((pro)-Ape Near Neighbor). Let U C dd Rd be dataset, E gd be query point, <> 1 be the approximation parameter, and r > 0 be the distance parameter. The (c, aapppooximet near neighbor problem asks, if there exists a point u, E U with l|u, - bll S r, then return a point ū E U with l|ū - -ll S cr. Otherwise, the data structure can either return nothing or any point ū E U with l|ū vll S er.
Is it possible to improve upon the solutions that use min,d, }} data structures? In pionecring work of (Has- sidim et al., 2022) and further extended by (Beimel et al., 2022), it was shown that differential privacy could be uti- lized to reduce such overhead. In particular, for numerical estimation problems, where one only needs to output nu- merical value, these works show that Ö(VT) 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 Ö(VT) oblivious data structures, and for each adaptive query, sam- ples (1) of the data structures, and outputs the differen- tially private median of the answers (Beimel et al., 2022). By the advanced composition theorem (Dwork et al., 2010), Ö(VT)) data structures suffice to provide a correct answer to the numerical estimation problem. This leads to drastically improved algorithms when VT < d, and in (Beimel et al., 2022) they apply to a large number of graph algorithms. This technique was later extended in (Cherapanamjeri et al., 2023) for estimating the cost of regression problem and the value of kernel density estimation.
We now state the assumption imposed on the ANN problem, in its most general form. Given a query v and data matrix U, we will use (U) to denote the set of candidate solu- tion of querying v, For example, the predicate function for (c. r-)-NN can be defined as fU) = U n B(u, cr) where B(u er) is the ball centered at with radius under some norm. The assumption is:
Assumption 1.2. Let U C Rd be an n-point dataset, and let
{uI, .2..., JT} S IR be sequence of (possibly adaptive) queries. We assume for all E [T], (U) S s.
The assumption states that the ball around et of radius or cannot intersect with more than points in U, which is equivalent to that the query 2, cannot have too many approx- imate near neighbors in U, when U, has an r-near neighbor. To facilitate a comparison with other popular assumptions for this task, such as constant expansion and bounded dou- bling dimension, we state a version of the assumption for ANN that solely depends on the matrix U:
Can these techniques be extended beyond numerical esti- mation, 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
"The standard (c, r)-ANN definition allows the data structure to output any point in U if there is no point within distance of the query v. Here we restrict it to either return nothing return point within distance er, as most popular ANN data structures, such as locality-sensitive hashing, satisfy this specification.
We use Ö(-) to suppress polylogarithmic factors in n,, d and 1/8 where 8 is the failure probability of the data structure.
2

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Assumption 1.3. Let U C RR, and let (BuJue be the collection of norm balls with B,, = B(u, cr). We assume for each u E U, that B. intersects at most other distinct balls in the collection.
As a final note, we would like point out that when work- ing with U C {00, 1] and when the norm is || 1|2, i.e., the Hamming ANN problem, Assumption 1.3 automatically holds for d = n² and a S L.. In particular for Hamming (Indyk & Motwani, 1 1998) and thus we
I.SH, P = ( only need d S n ((1/(c>)) Our result will provide a Ham- ming LSH that is robust against adaptive adversaries, and in particular against the attack of (Kapralov et al., 2024) in low dimensions.
Let us first see how this assumption implies the condition (U). By the triangle inequality, any two points in (vv, cr) have distance at most 2cr, that is, the norm balls with these two points being the respective centers with radius or must intersect. If e has more than s approximate nearest neigh- bors, then there must exist some E B(u, cr) whose norm ball intersects with more than s distinct balls, contradic- tion. Intuitively, Assumption 1.3 states that the dataset U is not too dense, and in particular each point in U does not have too many close neighbors. This structural assumption can also be achieved by preprocessing U: one could run a clustering algorithm on to group points that are close to each other into a cluster, and replace a cluster using its center. Then, the downstream ANN algorithm is performed on these centers; once a center is returned, one could re- turn a point in the corresponding cluster. This approach has been implemented in various approximate nearest neighbor search libraries in practice, and has been a driving force for the Google ScaNN framework (Sun, 2020; Guo et al., 2020). For efficiency reasons, we will restrict & S nP:
Next, we consider the problem of adaptively updating the regression problem, and outputting the regression solution vector whenever queried.
Assumption 1.4. Let U E Buxd be the design matrix and b E R" be the response vector. Let {ui....,vy ..) } be a sequence of (possibly) adaptive updates to the problem in one of two forms: (1) Update U: ot E gaxd and U is updated via U t U Uzi (2) Update b: v, E RR" and b is updated via b t b+ We will use (Ug,b)) to denote the pair after being updated by ut- The goal is to design a data structure such that for any t E [T]. it outputs a (1 + =)-- approximate solution It E R for which || - - 13 S (1 + a)- minzers |[ - bell3 holds with high probability. For all E [T], we assume the condition number of U² defined as n(U,)) == Twan is upper bounded by k. amin
We also compare Assumption 1.3 to two popular assump- tions for nearest neighbor search: constant expansion (Karger& & 2002; Beygelzimer et al., 2006) and dou- bling dimension (Gupta et al., 2003; Krauthgamer & Lee, 2004a;b). The constant (local) expansion states that if (B(,rr) n U| 2 logn, then [B(u, 2r) n U] S Cexp [B(,,) r) | for constant Cexp- The query time of near- est neighbor search data structures under the constant ex- pansion assumption usually has a polylogarithmie depen- dence on n but a large polynomial dependence On the other hand, we only need [B(e, cr) n UI I n². If we let [Ber,)) n UI = logn, n, then one can see that [B( T²r) n U| S nº. Thus, for any c < n²" (which is a very large approximation factor), our assumption is strictly weaker. Moreover, we note that constant expansion restricts the growth across different distances, while our assumption only requires relatively sparse neighborhood at the final level. A more robust version of constant expansion is the notion of doubling dimension, which asks how many balls of radius r are needed to cover a ball of radius 2r. It has been shown in (Krauthgamer & Lee, 2004b) that bounded doubling dimension a strictly stronger assumption than constant expansion, and it provides a bound of the form [B, cr) n nu| < diim()), where A > 2 is the aspect ratio of U and X is the metric space. If X = IRd with any norm, then dim = ((d), and therefore for this bound to be meaningful, one must have d = oloog n). Moreover, data structures with a doubling dimension assumption often have their preprocessing time and space exponential in dim(X).
The problem and assumption can be succinctly described as follows: an adversary could adaptively perturb entries of U and b, and our goal is to design a data structure that outputs the regression solution in the presence of these perturbations. In addition, we assume the perturbations are bounded, in the sense that they do not change the conditioning of the design matrix by too much. For this problem, note that one could naively store the matrix U and solve the regression problem exactly. In this case, as the algorithm is deterministic, automatically adaptive. However, this approach would re- quire Ω M(nd) space and 11d time, which is both space- and time-inefficient for large Alternatively, one could prepare T independent sketching matrices Si,..., Sr, one for each query, and store S,U, Syb for all f E [Z'. When receiving an update to U or b, one can simply update the cor- responding entries of S,Uand and S,b, as sketching matrices are linear. This approach requires Q(T poly(d) space, a pre- processing time of O (nd + poly(d))). and query time of poly(d). While the query time is much more efficient for n >> d, the space and preprocessing time are prohibitive given that T is large. Hence, our goal is to design algo- rithms that use o(T . poly(d)) space, have a sublinear in T dependence in the preprocessing time, and have a query time of poly
Gexp-
1.1. Main Results
We state the main results for ANN and adaptive regression in this section.
3

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
1.1.1. ADAPTIVE ANN FOR SPARSE NEIGHBORHHOODS
runtime for problems such as online weighted matching with adversarial arrival, and terminal embeddings. We refer the reader to Section 4 for more details. In addition, when these data structures need to be updated (insert or delete points from the data structures), we provide procedures based on fast rectangular matrix multiplication that beat the alternative of simply updating all data structures (Section C). In Table I, we compare our result with prior works that use d or T copies of the LSH's.
Our most general result for ANN is as follows:
Theorem 1.5. Let U S R be an n-point dataset and let fo : (z + gz be the predicate function. Let A be an oblivious algorithm, Le.,for a fixed query v E R2, with probability at least 1 - 5, A returns a point (or a subset) of fuLU) if [U) is non-empty. Moreover, A has preprocess- ing time Tpreps space usage Sapace and query time Tauery- Then there exists an adaptive algorithm A such that given a sequence of adaptive queries {vi...., Vrr satisfying As- sumption 1.2:() (1) Preprocesses U in time Ö(VT. 8). .prepp (2) Uses space Ö(VT SSppace (3) For all t [T), given query Vt, it returns a point (or a subset) of Ju, (U) in time (6) Tanory with probability at least 1-5. In particular, the amortized cost per query is (s// (////T)- -Trepp + +Ö()). (S)).querry.
1.1.2. ADAPTIVE REGRESSION FOR WELL-CONDITIONED INSTANCES
For adaptive regression, we can use fewer than T copies of an oblivious data structures if the condition number upper bound i is small:
Theorem 1.8. Let U E R b R. and {ei..... vr) be sequence of adaptive updates to (), satisfying Assump- tion 1.4. Then, there exists an adaptive algorithm that (1) Preprocesses (U, b) in time Ö( Ö(vTd. (nnz(U) + mnz(b)= + d' + d' ddx?? /a21); (2) Uses space Ö(vT de (2-5k//a)) (3) For all t [T], it updates (U--1, to (Ur, b() in time Ö(vTd- (nnz(v)) + d 4+ +xxx2/a)) (4) For all E [T], given update Ut. it returns a solution Dt that is a (1 + a)- approximation to the regression problem using (U,, bi) in time Ō(d x² /a²), with probability at least 8.
Let us interpret Theorem 1.5, It states that long as s o(vT), then we can turn an oblivious data structure into an adaptive data structure using fewer than T inddpnn- dent copies of the oblivious data structure. Of course, this comes at a cost of a slightly worse query time by a factor of Ös). However, if we consider the amortized cost per query for using T data structures, the cost is dominated by Trrpp as the algorithm needs to prepare a fresh data structure for each query. In contrast, Theorem 1.5 has amortized cost of (ss/ (Lsss/TT)TTTa -Trrep + O(s))Tqqery Tquery per query. Typically, Tquery is much smaller than Tprep; for example, for LSH, Tprep = Pdd and Tquery = ndd, so it is much more important to obtain a reduction on the number of data structures. Applying Theorem 1.5, we immediately obtain adaptive algorithms for LSH under different norms, using fewer than T data structures.
Theorem 1.8 offers an algorithm with extremely efficient query time. When the condition number bound k is small, it provides space bound of vT poly(d), both sublinear in I' and with no polynomial dependence on n. The pre- processing time outperforms the simple algorithm which generates T sketches when < T and α is small. While for ANN, one could prepare Ö(d) data structures during pre- processing to prepare for all possible queries, and at query time just sample a small number of these, this is not possible for regression. Indeed, for regression one would need to prepare Ö(nd) such data structures, given the number of possible design matrices, which would be prohibitive. We again compare our result with prior approaches that use nd or copies of sketches, in Table 2.
Theorem 1.6. Let U C Rd be an n-point dataset satisfying Assumption 1.3. There exists an adaptive algorithm A such that given a sequence of adaptive queries {ui,.... UT), it solves the (c,r)-ANN problem (Definition 1.1) and (1) Preprocesses U time Ö(VT. 8 n. Pd); (2) Uses space Ö(VT s. n nlte + nd): (3) For all t E [T], given query ve, returns a point in B(u, NU if B(v, nU + 0 in time Ö(s - -dd), with probability at least 1- 1-6 8.
We next study the model in (Cherapanamjeri et al., 2023), where only the response vector b is allowed to be updated in at most positions. In (Cherapanamjeri et al., 2023), it is shown that one can corporate the techniques of (Beimel et al., 2022) to output the cost of the regression problems, but a key open question was whether one could output the actual solution vector to the regression problems. We re- solve this question by utilizing the tools we developed in Theorem 1.8 in conjunction with a preconditioner for U to remove the dependence on k. Below, we will use nnz(
A generic LSH data structure template restricts the number of points it looks at per query to n², so if I n², obtain the following results:
Corollary 1.7. Let U C Rd satisfy Assumption 1.3 with 8 S nP. Then there exists an adaptive algorithm A such that given a sequence of adaptive queries {uI,..., U, the data structure (1) Preprocesses U in time (=+(e)))))))))) (2) Uses space Ö(VT-n1 (+0pp) +nd); (3) For all t E [T]. given query U, it returns a point in ((,,cr)nn nU if Bu,, + 0 in time (()) d), with probability at least 1 - 8.
"We use (Uo, denote (U, b). the initial design matrix and response vector.
Utilizing these adaptive data structures, we obtain improved
4

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Method
Space
Amortized Prep Time
Query Time
Update Time
T copies
Tn + and n n-ted
n pd
n'd
Tn'd nfd
d copies
7 ted
d
n/d
This paper
VTsn + nd
tPd
sn'd
VIsn'd
vT
Table 1: Specifications of data structures given sequence of T adaptive queries and updates for ANN problem. We ignore O() notation for clarity. We use to denote the parameter for Assumption 1.3.
Method T' copies
Space
Amortized Prep Time
Query Time
Update Time
Tdd /a2
nnz(U, b) + d + L/a² nd (mnz U, b) + d + a²
aut1/a²
T(nnz(v;) + d + /a²) nd(nnz(es) + + d² /a")
nd copies
ndl /a²
/a
This paper
(nnz(U,bb d (Pn2//²)
dutt22//a /02
vTd(nnz(v)) + d8 + /22)
Table 2: Specifications of data structures given a sequence of 'T adaptive queries and updates for regression. We ignore Ö()) notation for clarity. We use nnz(U,) b) as a shorthand for nnz(U) + nnz(b), and let k be the parameter for Assumption 1.4.
denote the number of nonzero entries in U.
Compared to Theorem 1.8, Theorem 1.10 offers better dependence on the condition number k at the expense of linear dependence on the length of update sequence T. While one might be tempted to simply generate an inde- pendent sketch for each update, it is worth noting that [P] could be much smaller than (nxx)(drr) whenever the up- dates and the solutions are known to be relatively stable. As a concrete example, when only one entry changes in between queries, then the number of computation paths is only (nd)", which may be much less than (nx))(ddT) In such scenario, it requires smaller number of sketches with improved space, preprocessing and update time. This is similar to past work where the complexity depends on a stability parameter (Hassidim et al., 2022).
Theorem 1.9. Let U E Raxd and b E E.."" Let {vi, .2)....) C Th" be a sequence of adaptive updates to b, such that for all t, l[vello S Let I be a batch size parameter. There exists adaptive algorithm that (I) It has amortized update time Ō Dd/T/T (nnz(U) + nnz(b)- + ds + d= (a2)) + +VTd (s d + d² )); (2) It outputs (1 + appproxiiae solution zt in time (dd))
The main advantage of Theorem 1.9 over Theorem 1.8 is that the quadratic dependence on the condition number can be removed via choosing a proper preconditioner in this setting, since U is not changing. We also have extremely fast query time, as the solution vector can be quickly updated via matrix- matrix-vector product instead of solving the regression problem from scratch.
2. Related Work
When the condition number k is as large as (oly(z) and U is dynamically changing, Theorem 1.8 no longer gives effi- cient space and preprocessing time. To address this problem, we develop an algorithm with only logarithmic dependence on the condition number K. based on the bounded computa- tion path technique (Ben-Eliezer et al., 2020).
Differential privacy is a central con- cept in data privacy, introduced in (Dwork et al., 2006). The main idea of differential privacy is that when the inputs to the algorithm are close to each other, it would be almost im- possible to differentiate the outputs. Since its introduction, differential privacy has seen rich applications in general ma- chine learning (Chaudhuri & Monteleoni, 2008; Williams & McSherry, 2010; Jayaraman & Evans, 2019; Triasteyn & Faltings, 2020), deep neural network (Abadi et al., 2016; Bagdasaryan et al., 2019), computer vision (Zhu et al., 2020; Luo et al., 2021; Tan et al., 2019), natural language process- ing (Yue et al., 2021; Weggenmann & Kerschbaum, 2018), federated learning (Sun et al., 2023; Song et al., 2023a) and large language model (Yu et al., 2022; Gao et al., 2023; Liang et al., 2024; Gu et al., 2025; Nagesh et al., 2025). Designing data structures with differential privacy guaran- tees is crucial, as it automatically ensures the privacy of any downstream tasks (Cohen-Addad et al., 2022; Dhulipala et al., 2023; Li et al., 2023; Chen et al., 2023; Andoni et al.,
Differential Privacy.
Theorem 1.10. Let U E Raxd b E R" and (T} be a sequence of adaptive updates to (U, b). satisfying Assumption 1.4. Let P denote set of possible output sequences the algorithm can provide to the adversary; note that we always have [P] < (nx)8(dT), There ex- ists adaptive algorithm that (1) Preprocesses (U,b) in time Ö(nd" 2 (d + log [P] + log ))² (2) Uses space )) (3) For all 1. E [T], it updates (U,-1, to (U,, b,) in time O(d++log Po|+log| })/²²); (4) For all L E [T), returns a (1 a)-apprxximate solution Ie to the regression problem using (U,, bz) in time 0(d ((d (d+ + log (PI + log a)), with probability at least 1 - 8.
Öd(d++og [P|+
5

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
2023; Li et al., 2024). It is of particular interest design differentially private data structure in the function release model, where the quality of the output won't degrade as the data structure processes more queries (Hall et al., 2013; Huang & Roth, 2014; Wang et al. 2016; Aldà & Rubinstein, 2017; Coleman & Shrivastava, 2021; Wagner et al., 2023;
in B(v, 2r) only grows by constant factor compared to the number of points in B(U, r) (Clarkson, 1997; Karger & Ruhl, 2002; Beygelzimer et al., 2006; Krauthgamer & Lee, 2004b), then it is possible to design a data structure with polynomial preprocessing time and space (note that the dependence on the growth constant or doubling dimension is large, but still polynomial), and logarithmic query time. However, these assumptions are strong, as they greatly limit the potential geometric structure of the dataset.
Backurs et al., 2024; Liu et al., 2024; Hu et al., 2024; Ke et al., 2025; Li et al., 2025).
Adaptive Data Structure. In recent years, data structures have been integrated into iterative processes to speed up the algorithm. This has been the foundation for various recent breakthroughs in fast convex optimization (Cohen Lee et al., 2019; Brand et al., 2020; 2022; Jiang et al., 2021; Qin et al., 2023). These data structures possess the ability answer adaptive queries, that could depend previous outputs from the data structure, with high success probability. For streaming problems, the adversary could also be adaptive, in the sense that it would feed the streaming algorithm with updates, after observing the prior decisions of the algorithm (Ben-Fliezer et al., 2020; Woodruff & Zhou, 2021; Ajtai et al., 2022: Feng & Woodruff, 2023; Woodruff Feng et al., 2024; Gribelyuk et al., 2024; Gu et al., 2025). In this work, we focus in particular on the adaptive data structures based on differential privacy (Has- sidim et al., 2022; Beimel et al., 2022; Song et al., 2023b; Cherapanamjeri et al., 2023).
The celebrated work of Indyk and Motwani (Indyk & Mot- wani, 1998) shows that if one relaxes the problem to allow for answering c-approximate near neighbor queries instead, then one can achieve (slightly) super-lineat preprocessing time and space, and sublinear query time. These data struc- tures are inherently random, as they rely on partitioning the space using random directions. As this randomness is determined during the preprocessing phase, these data struc- tures are not robust against an adaptive adversary. In fact, for Hamming approximate near neighbor search, (Kapralov et al., 2024) provides an efficient attack that can always force the data structure to output a false negative if there exists at least one point that is isolated from other points.
et al., 2019;
& Zhou, 2024;
Since the issue of false negatives is most prevalent for Monte Carlo data structures, one might consider to use a class of Las Vegas ANN data structures whose running times are ran- dom variables, but are guaranteed to output a correct answer with no false negatives (Kushilevitz et al., 1998; Pagh, 2016; Ahle, 2017; Wei, 2022). Unfortunately. the space and run- time analysis of these data structures are performed based the assumption that the query sequence is oblivious. An adaptive adversary could design sequence of queries with much higher average response time than an oblivious one.
3. Technical Overview
We divide the technical overview into two parts. For adap- tive ANN, we demonstrate novel framework based on differentially private selection over a sparse vector. For adaptive regression, we show how to upgrade the private median framework of (Beimel et al., 2022) to output the solution vector, and how to obtain utility guarantees through novel use of foo guarantees provided by the sketch-and- solve framework (Price al., 2017).
Reduction To Differentially Private Selection. We start by introducing the differentially private selection problem. Given n categories, a collection of s binary vectors over 10, denoted by b(.)..... category j arg maxje(n) Σi=1 b().j- i.e., the most com- mon category among all vectors. This can be achieved via the following mechanism: 1). Compute the overall count vector B == Σ; biay; 2). Add independent Laplace noise Lap(1/E) to each of the counts; 3). Report the index with the largest noisy count. The privacy parameter & does not scale with either the number n of categories or the number of vectors, as it only outputs a single index.
the goal is find the
3.1. Adaptive ANN via Differentially Private Selection
Existing Results. Before providing an overview of our techniques, start by examining existing results for adap- tive approximate nearest neighbor search data structures. The first candidates are of course deterministic data struc- tures. Deterministic approximate nearest neighbor data structures have been a central topic of study since the 1970s (de Berg et al., 2008; Cormen et al., 2022). However, with- out any structural assumptions on the query or dataset, these data structures suffer from the curse of dimensionality, i.e., their preprocessing time and space usage scale exponentially in d, making them infeasible for slightly large dimensions. If one is willing to make strong structural assumptions on the dataset, e.g., given any query point v. the number of points
We now show how to frame approximate near neighbor search as a differentially private selection problem. We create a category for each point u E U, and for each data structure, and we ask it to output all the near neighbors it finds instead of a single one of them. This creates an indicator vector for the points: if the data structure finds ui then the corresponding vector has its i-th entry equal to 1. We can then apply the differentially private selection
6

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
procedure for these indicator vectors, and output the point with maximum noisy count. To see this mechanism indeed protects the privacy of the internal randomness of the data structures, note that fixing the dataset U and the adaptive query point v, the indicator vector is determined by the ran- dom strings of these data structures. Thus, the mechanism is (e, 0)-DP, and we can apply the advanced composition theorem of differential privacy to reduce the number of data structures from T to (VT)).
The second issue is algorithmie: if we naively implement the differentially private selection mechanism for each query, we will have to generate noise for each count which in- evitably takes (m)) time. On the other hand, the count vector B is s-sparse, and these non-zero entries have magni- tude larger than the noise. This problem has been studied before in the context of publishing a private database for sparse data (Cormode et al., 2012); however, existing so- lutions either require modifying the problem definition so that the privacy becomes challenging to prove, or converting Monte Carlo algorithm into Las Vegas one, with only expected runtime guarantees. We develop a novel algorithm to resolve these issues termed as the sparse argmax mech- anism: given an s-sparse vector, (1) Adding 8 exponential noises Exp(1/E) to the support of the sparse vector; (2) Generating the X from the n-th order statisties distribution of Exp(1/e); (3) Flip biased coin with head probability s if head, generate 1 i.i.d. exponential noises until none of them exceed X, add them including X to the support, and output the maximum entry index; (4) If tail, generate s i.i.d. exponential noises until none of them exceed X, add these noises to the support, assign X random index in the n s non-support, output the maximum index associated with the noisy entries and X. We prove that with high probability. generating these noises can be done O(s log n) time, and the output distribution with sparse noises is the same as the generating n i...d. exponential noises.
This is, however, not sufficient to provide a utility guarantee, as the Laplace noise could have large magnitude, thus mak- ing all counts too noisy. While it is fortunate that we can set E= = 0(1), and with high probability, the magnitude of the noise is O(log n). this might still be too large to be useful. To see how this issue can be resolved, let us consider the case that the query point only has one approximate near neighbor, i.e., there exists only one u. for which ||0- ||v-u| S r and ||0 w|l S cr. In this case, the data structure can only output (conditioned on the data structure succeeding). If we were to sample nl data structures and compute the count vector, we can guarantee that the entry corresponding to the near-neighbor has larger magnitude than the noise. Thus, as long as constant fraction of the data structures succeed, we can ensure we output the correct point with high probability.
Note that our above argument assumes that a constant frac- tion of data structures succeed, which is not guaranteed when facing an adaptive adversary! Fortunately, we can circumvent this problem by proving the algorithm is differ- entially private first; subsequently, we can apply the gener- alization property of DP to ensure that indeed, constant fraction of data structures succeed. Note the two-stage na- ture of this argument: we can only argue about the utility if the privacy is preserved. There are two main issues left: (1) the assumption that the query has only one neighbor too restrictive, and (2) the differentially private selection procedure takes (n) time respond to each query, mak- ing the data structure very inefficient. For the first issue, we note that we can extend this to the setting when v has only s approximate near-neighbors. In this setting, we can sample (is log n) data structures for each query. By the pigeonhole principle, there must exist at least one point whose count has magnitude larger than the noise, and we obtain the desired utility guarantee. Since the LSH data structures only output n" points for each query, we could pick s = O(n)), i.e., allow the query to have O(n²) near- neighbors. We can alternatively translate this assumption into a structural property on the dataset: as long as the ball centered at each point with radius or intersects at most s other balls, then we are guaranteed that the query has at most near-neighbors. We note that this assumption is au- tomatically satisfied for Hamming nearest- search and for the setting of (Kapralov et al., 2024).
3.2. Adaptive Regression via Differentially Private Median and foo Guarantee
Existing Results We first recall the standard setup of solving the over-constrained lg regression problem. Given a design matrix U Rnxd with n >> and response vector b, the goal is to compute x == arg mingers ||xx- -12.. In the static setting, xx can be computed via the normal equa- tions: x² (U U)LUb, but this is usually too expensive to be directly solved. The sketch-and and-solve paradigm (see, e.g., (Woodruff, 2014) for survey) provides a wide array of algo- rithmic tools to speed up this process. In particular, one can pick a random matrix S E R from a certain structured family of random matrices, so that r is small polynomial in d, and S can be quickly applied to U. One can then solve the sketched la regression problem min 1| - Sb1 for which the optimal solution is a good approximation to x². The l regression problem has also been extensively in the streaming (Clarkson & Woodruff, 2009; Braverman et al., 2021) and dynamic (Jiang et al., 2023; Cherapanam- jeri et al., 2023) models, where either the design matrix U or the response vector b can be updated, and one has to produce high quality approximate solution after each update. These works are either not robust to adaptive adver- saries (Clarkson & Woodruff, 2009), only support inserting or removing entire rows at once (Braverman et al., 2021;
7

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Jiang et al., 2023), or can only return the cost instead of the solution vector (Cherapanamjerii et al., 2023). In the realistic settings, the design matrix needs to tolerate perturbations to its entries due to the presence of noise or updated data. We consider the most general model where U can be updated by perturbation V/ E Raxd that can be adaptively chosen.
sketched solution in fact has much stronger bx guaran- tee (Price et al., 2017; Song et al., 2023c): ||0()) - x =1 e| S & va ||xx bll2 (m)) By properly choosing the pa- rameters for the the private median estimator, we can show that with high probability this also holds for g. Hence, we have [[ - 9)ll2 S Tmax ||2- gllx S ax(U)) ||Ux* bll2- To offset the blowup in condition number, we scale down a by factor of K, and thus es- tablish the utility of the coordinate-wise private median mechanism. We find the private median to be a surprising application of sketching with the fo guarantee, which is a less studied guarantee in the sketching literature.
Coordinate-wise Private Median and the lo Guarantee. One natural idea is extend the private median framework of (Beimel et al., 2022) to outputting an approximation to the solution vector. Our algorithm follows the generic template: prepare k copies of sketching matrices Si,..., Sk and preprocess (U, b) as (S,U, S,b) for all i E [b]] During an adaptive update, we simply update the corresponding sketches of the design matrix and of the response vector. At query time, we sample s = Ö(1) of our sketches and solve these sketched regression problems. Let 2(1)..... ................................ (s)) be the returned solution vectors. We next need to perform private aggregation on these vectors to craft our output.
To further speed up the preprocessing and update time, we compose the SRHT sketch with Count Sketch matri- ces (Charikar et al., 2002) so that both operations can be realized in input sparsity time. In addition, these sketches and the sketched design matrices can be stored in x(dxx2/on /a²) words of space. Since we use Ö in- dependent sketches, the space usage is OVVT 32.3 x² /a²).
The (Beimel et al., 2022) approach for private aggregation is to compute the private median of these numbers. We first consider a natural extension: for each E [d]. we compute gi (MEDIAN(EF (x)) and output 9 (91. ........2. 9.). The privacy of this approach is readily es- tablished: since each entry of g is private, we can conclude the final privacy guarantee by using the advanced compo- sition theorem. This comes at a price of requiring v sketches instead of the vT data structures of (Beimel et al., 2022), but still offers an improvement as long as d < T. The main challenge now lies in proving the utility of our approach, where we need to show that g is in fact a good enough solution to the regression problem.
4. Applications
In this section, we utilize our adaptive ANN data structures to speed up range of optimization processes and other data structures. Let Tmat b, c) to be the time complexity of multiplying an a x 6 matrix with a b x c matrix.
4.1. Online Weighted Matching
Consider the following online weighted matching problem on bipartite graphs: we are given a set of left vertices U C Rd and we will receive a sequence of online right vertices V == { Un. C Rd. The edge weight be- tween left vertex E U and a right vertex E V is defined to be To- for some norm || ||. Our goal is to design an algorithm that given a vertex Vr, make an im- mediate decision to match with point U, E U with edge weight | The goal is to compute an online matching that maximizes the total weight Σ -o. The online weighted matching problem has been widely studied in the edge-arrival model (Fahrbach et al., 2022), but in many prac- tical machine learning applications, one usually encounters the vertex-arrived model (Karp et al., 1990). For example, the left vertices of the graph represent Uber/I.fft drivers, and the right vertices represent customers. The goal is to match each incoming customer with a driver that is closest in geographical distance. Another common application is movie recommendations on streaming platforms such as Netflix. Here the left vertices are movies, and the right ver- tices are viewers, and the goal is to find each viewer his/her favorite movie, defined by the distance between the feature embeddings of movies and viewers (Koren et al., 2009; Su
To quantify ||Ug - bll2. note that ||U' bll2 < 1 bll2 + ||U(<= - 12,, where the second term can be bounded by [|((x* - g)ll2 S mU) ||x= - glle S max m (U) ||a- glloo. In other words, if we can get a good han- dle on ||=- glloo. then we can hopefully obtain useful bound on the error. Since g is the coordinate-wis. private median of _(.)..... ((s)) which are solutions of sketched le regression problems, the standard sketching error guar- antee only ensures that the forward error is small, i.e., [Uz(() - b < (1 + = - b||2 for any i E [s]. For a backward error type guarantee, i.e., a bound on [| (00))=="p 2|2. one could convert directly from the forward error guaran- tee. If U is reasonably well-conditioned, then closeness in forward emror implies closeness in backward error.
However, for the private median guarantee, it is important that each entry of z2() - x= is small, rather than just the bound that (| - z²112 2| is small. While the ideal scenario would be || - x bloo & |/ - x* 112, this is gener- ally not true for most sketching matrices. Fortunately, for sketching matrices such as the Subsampled Randomized Hadamard Transform (SRHT), it has been shown that the
8

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
& Khoshgoftaar, 2009; Shi et al., 2014).*
4.2. Terminal Embedding
We consider the vertex-arrival online weighted matching problem when the right vertices are chosen by an adap- tive adversary. i..., the next vertex 1t+1 could depend on previous matching results {[u, r=)) This setting is par- ticularly common for practical applications such as Ride Apps, since if a certain app raises its price due high de- mand, the customers might choose to use another app. or move to new location with smaller demand. A good ap- proximation scheme for this problem is the greedy matching approach, i... each time we observe U2. we simply choose U4 to be the point which maximizes ||u,- (Karp et al., 1990). One could reduce this problem to nearest neighbor search problem against an adaptive adversary. There is a caveat though: if we restrict it to be a bipartite matching, then once a vertex u is matched, it should not be matched again. This means our adaptive LSH should delete the point that has been outputted by the data structure after each query. We show that it is possible to further augment our framework for the data structure to be decremental, and the deletion can be performed efficiently using fast rect- angular matrix multiplication (Duan et al., 2023). Before proceeding, we let ((a, b) for a, > be the value for which Tiat (a, b, ((a, b)) (ab)1+0(1)
A terminal embedding concerns the following prob- lem: given a metric space dx) and set of points U1...., Un X, the goal is to design embedding to another metric space (Y,dy) such that for any q E X, C dx(u,, q) S dy q) S Cp- (u;, q) for all i E [n]. where C > is a constant and p 2 1 is the distortion fac- tor. In contrast to metric embeddings such as the Johnson- Lindenstrauss lemma, a terminal embedding requires the distance to be preserved between fixed set of terminals and all points in the metric space. When both X and Y are the Euclidean metric, it has been shown that an em- bedding dimension of 00g-2log n) is possible for 1 + E distortion. (Cherapanamjeri & Nelson, 2021) shows that it is possible to implement a data structure that answers queries in time (n, + d) and space O(dn)+o(1)). At the core of their algorithm is an adaptive ANN data structure. In particular, they create ((d) independent copies to deal with issues of adaptivity. If you know in advance that you only need to answer T adaptive queries for T I d, then the (d) copies via a net argument is sub-optimal. For a fair com- parison, in the following we will assume (Cherapanamjeri & Nelson, 2021) uses T copies of data structures instead of d. We apply the adaptive LSH data structure we have designed to obtain an improvement in the space complexity of (Cherapanamjeri & Nelson, 2021)'s data structure when VT 8 I d and the query points q satisfy Assumption 1.2. Before proceeding, we need to introduce few concepts. Definition 4.2. Given U = {ui,..., Un} Rd and O. we say a matrix S E BRx is convex hull distortion for U for any 2 E conv(T)) where T = 11 ل : u, E UJ, we have |||S=||| - |==|| S..
Theorem 4.1 (Online Weighted Matching). Let C Rd be an n-point dataset satisfying Assumption 1.3 with parameter Given a possibly adaptive sequence {Vi,..., vn) C Rd, we can design an adaptive data structure which (1) Preprocesses U in time Ö (irnut/TT-- s, d, n)n-n---TTs +P); (vT-s,
(2) Uses space Sapace = Ö(VT 8 n p + nd): (3) Given a point vt, it returns point in U \ (uI,...,
that is 1.1e -ll-approximate near neighbor of Us, in time
Theorem 4.3 (Terminal Embedding). Let U C Rd be an n-point dataset and V = {ui,..., UT} S Rdd be a se- quence T
This step succeeds with probability at least 1-ast1-5, (4) Deletes point u E U from the data structure in amortized time Ó((VT s- d) 14011)) (40())/B(/T /0(VT s. d) + VT. s..... s.n)).
T adaptive queries that satisfy Assumption 1.2 with parameter Let p1: P2, (2,PP, P4 and Prep > 0 be pa- rameters. There exists randomized algorithm that com- putes a data structure 'D and a linear map S E Rkxd, such that (1) S is a convex hull distortion for U: (2) Given any Vs E V, DD produces a vector 2o, E R k++ such that with probability at least 1 - 1/poyy()), (1 e) 11 - ull S
To get a better perspective on the deletion time, suppose s = poly log n. Also note that if VT 2 d, then we could simply use d independent copies via a net argument, so we assume vT < d. Hence, 0(VT, d) 2 B(VT, VT) 2 T0/2 where a 0.32 is the dual matrix multiplication exponent (Williams et al., 2024; Le Gall, 2024). The runtime can be further simplified to (T1/2-a/2 1+o(1) + T1/2. n?. We compare this result updating all Õ(VT) data structures, which takes total of 1/2 d 1/2 n2" time. By utilizing fast rectangular matrix multiplication and batch updates, we improve the exponent on /T for the first term.
Su
S (1+ - 1|1e - =ll for all u U. 3) For any E V, the runtime of computing zo, is ((s-(d +nds (1tst Pocttes-p--A-ae p=-Pee))s)) (4) The space complexity of D is O(VT (n..snnnnntttt (1Prp + (L
Zv.
0
To interpret our result, we note that the query time is in- creased by a factor of s, as in all previous results. The space complexity is reduced from T to vT s. If s = poly log n, then the query time is only increased by a polylogarithmic factor, and the space complexity is improved by a factor of VT.
'ee note that in movie recommendations, one movie could he matched with multiple viewers. This scenario has also heen studied and our results would also apply (Fahrbach et al., 2022).
9

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Acknowledgement
Bagdasaryan, E., Poursaeed, O., and Shmatikov, V. Dif- ferential privacy has disparate impact model accu- racy. Advances in Neural Information Processing Systems (NeurIPS), 32:15479-15444 2019.
Ying Feng was supported by an MIT Akamai Presidential Fellowship. David Woodruff would like to acknowledge sup- port from a Simons Investigator Award and Office of Naval Research (ONR) award number N0001421 12647. Lichen Zhang was supported in part by NSF CCF-1955217 and NSF DMS-2022448.
Bateni, M., Dhulipala, L., Fletcher, W., Gowda, K. N., Her- shkowitz, D. E., Jayaram, R., and Lacki, J. Efficient centroid linkoe clustering. In Proceedings of the 38th International Conference on Neural Information Process- ing Systems, 2024.
Impact Statement
Beimel, A., Kaplan, H., Mansour, Y., Nissim, K., Saranurak, T., and Stemmer, U. Dynamic algorithms against an adap- tive adversary: Generic constructions and lower bounds. In Proceedings of the 54th Annual ACM SIGACT Sympo- sium on Theory of Computing, pp. 1671-1688 2022.
This paper develops novel adaptive data structures to speed up machine learning tasks. It potentially would lead effi ciency improvement and reduction in carbon emission. We do not foresee any societal consequences worth highlight- ing.
Ben-Eliezer, O.., Jayaram, R., Woodruff, D. P., and Yogev, A framework for adversarially robust streaming al- gorithms. In Proceedings of the 39th ACM SIGMOD- SIGACT-SIGAI symposium on principles of database sys- tems, pp. 63-80, 2020.
References
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L.. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Beygelzimer, A., Kakade, S., and Langford, J. Cover trees for nearest neighbor. In Proceedings of the 23rd inter- national conference on Machine learning (ICML), pp. 97-104, 2006.
Ahle, T. D. Optimal las vegas locality sensitive data struc- tures. In 2017 IEEE 58th Anmual Symposium Founda- tions of Computer Science (FOCS), pp. 938-949. IEEE, 2017.
Brand, J. v. d., Lee, T., Sidford, A., and Song. Z. Solving tall dense linear programs in nearly linear time. In Pro- ceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 775-788, 2020.
Ajtai, M., Braverman, V., Jayram, T., Silwal, S., Sun, A., Woodruff, D. P., and Zhou, S. The white-box box adversarial data stream model. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIIG Symposium on Principles of Database Systems (PODS), pp. 15-27. ACM, 2022.
Brand, J. v. d., Gao, Y., Jambulapati, A., Lee, Y. T., Liu, Y. P., Peng, R., and Sidford, A. Faster maxflow via improved dynamic spectral vertex sparsifiers. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pp. 543-556, New York, NY, USA, 2022. Association for Computing Machinery.
Alda, F. and Rubinstein, B. I. The bernstein mechanism: function release under differential privacy. In Proceedings of the Thirty-Firss AAAI Conference on Artificial Intelli- gence, AAAI 17, pp. 1705-1711, AAAI Press, 2017.
Braverman, V., Hassidim, A., Matias, Y., Schain, M., Silwal, S., and Zhou, S. Adversarial robustness of streaming algo- rithms through importance sampling. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NeurlPS '21, 2021.
Andoni, A., Laarhoven, T., Razenshteyn, I., and Waingarten, E. Optimal bashing-based time-space trade-offs for ap- proximate near neighbors. In Proceedings of the Twenty- Eighth Annual CEM- Symposium on Discrete Algo- rithms (SODA), pp. 47-66. SIAM, 2017.
Bun, M., Nissim, K., Stemmer, U., and Vadhan, S. Differen- tially private release and learning of threshold functions. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 634-649, 2015.
Andoni, A., Indyk, P., Mahabadi, S., and Narayanan, S. Differentially private approximate near neighbor counting in high dimensions. In seirth- Conference Neural Information Processing Systems, 2023.
Charikar, M., Chen, K., and Farach-Colton, M. Finding frequent items in data streams. In International Collo- quium on Automata, Languages, and Programming, pp. 693-703. Springer, 2002.
Backurs, A., Lin, Z., Mahabadi, S., Silwal, S., and Tar- nawski, J. Efficiently computing similarities to private datasets. In The Twelfth International Conference on Learning Representations, 2024.
Chaudhuri, K. and Monteleoni, C. trivacy-preserving logis- tic regression. In NIPS, volume 8, pp. 289-296. Citeseer 2008
10

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Chen, J. Y., Ghazi, B., Kumar, R., Manurangsi, P., Narayanan, S., Nelson, J., and Xu, Y. Differentillly private all-pairs shortest path distances: Improved algo- rithms and lower bounds. In SODA, 2023. Merge of two independent and concurrent works by Chen, Narayanan, and Xu and by Ghazi, Kumar, Manurangsi, and Nelson.
Datar, M., Immorlica, N., Indyk, P., and Mirrokni, V. S. Locality-sensitee hashing scheme based on p-stable dis- tributions. In Proceedings of the twentieth annual sympo- sium on Computational geometry (SoCG), pp. 253-262. 2004.
de Berg, M., Cheong, O., van Kreveld, M., and Overmars, M. Computational Geometry: Algorithms and Applications. Springer. 2008.
Cherapanamjeri, Y. and Nelson, J. On adaptive distance estimation. Advances in Neural Information Processing Systems, 33:1 1 1711178811 11190, 2020.
Dhulipala, L.,, Li, G. Z.. and Liu, Q. C. Near-optimal dif- ferentially private k-core decomposition. arXiv preprint arXiv:2312.07706, 2023.
Cherapanamjeri, Y. and Nelson, J. Terminal embeddings in sublinear time. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2021.
Ding, Z., Kifer, D., E., S. M. S. N., Steinke, T., Wang, Y.,
Cherapanamjeri, and Nelson, Uniform approximations for randomized hadamard transforms with applications. In Proceedings of the 51st Annual ACM SIGACT Sympo- sium on Theory of Computing (STOC), 2022.
Xiao, Y., and Zhang, D. The permute-and-fiig mech- anism is identical to report-noisy-max with exponen- org/abs////////
tial noise, 2021.
2105. 07260.
Cherapanamjeri, Y., Silwal, S., Woodruff, D., Zhang, F., Zhang, Q., and Zhou, S. Robust algorithms on adap- tive inputs from bounded adversaries. In The Eleventh International Conference on Learning Representations, 2023.
Duan, R., Wu, H., and Zhou, R. Faster matrix multiplication via asymmetric hashing. In FOCS, 2023.
Dwork, C. and Roth, A. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 2014.
Clarkson, K. L. Nearest neighbor queries in metric spaces. In Proceedings of the twenty-ninth annual ACM sympo- sium on Theory of computing, pp. 609-617, 1997.
the
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrat- ing noise to sensitivity in private data analysis. In Theory of Cryptography Conference (TCC), volume 3876 of Lec- ture Notes in Computer Science, pp. 265 284. Springer, 2006.
Clarkson, K. and Woodruff, P. Numerical linear al- gebra in the streaming model. In Proceedings of the Forty-First Annual ACM Symposium Theory of Com- puting, STOC '09, 2009.
Dwork, C., Rothblum, G. N., and Vadhan, S. Boosting and differential privacy. In 2010 IEEE 51st Annual Sympo- sium on Foundations of Computer Science (FOCS), pp. 51-60. IEEE, 2010.
Cohen, M. B., Lee, Y. T., and Song, Z. Solving linear programs in the current matrix multiplication time. In STOC, 2019.
Cohen-Addad, V., Epasto, A., Mirrokni, V., Narayanan, S., and Zhong, P. Near-optimal private and scalable k- clustering. In Advances in Neural Information Processing Systems 35 (NeurIPS 2022), pp. 1-13, 2022.
Fahrbach, M., Huang, Z., Tao, R., and Zadimoghaddam, M. Edge-weighted online bipartite matching. Journal of the ACM, 69(6):1-35. 2022.
Feng, Y. and Woodruff, D. P. Improved algorithms for white-box adversarial streams. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 9962-9975. PMLR, 2023.
Coleman, B. and Shrivastava, A. A one-pass distributed and private sketch for kernel sums with applications to ma- chine learning at scale. In Proceedings of the 2021 ACM SIGSAC Conference Computer and Communications Security, CCS '21, pp. 9252-3265, New York, NY, USA, 2021. Association for Computing Machinery.
Feng, Y., Jain, A., and Woodruff, D. Fast white-box adver- sarial streaming without a random oracle. In Proceedings of the 41st International Conference Machine Learn- ing, volume 235 of Proceedings of Machine Learning Research, pp. 13199 13224. PMLR, 2024.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to algorithms. MIT press, 2022.
Cormode, G., Procopiue, C., Srivastava, D., and Tran, T. T. L. Differentially private summaries for sparse data. In Proceedings of the 15th International Conference on Database Theory, ICDT 12, pp. 299-311, New York, NY, USA, 2012. Association for Computing Machinery.
Gao, Y., Song, Z., and Yang, X. Differentially private attention computation. arXiv preprint arXiv:2305.04701, 2023.

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Gathen, J. and Gerhard, J. Fast polynomial evaluation and interpolation, pp- 295-312. Cambridge University Press, 2013.
the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 823-832, 2021.
Jiang, S., Peng. B., and Weinstein, O. The complexity of dynamic least-squares regression. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), Los Alamitos, CA, USA, 2023.
Gribelyuk, E., Lin, H., Woodruff, D. P., Yu, H., and Zhou, S. strong separation for adversarially robust Eo estimation for linear sketches. In Proceedings of the 65th IEEE Symposium Foundations of Computer Science (FOCS). IEEE, 2024.
Johnson, W. B. and Lindenstrauss, J. Extensions of lipschitz mappings into a hilbert space. Contemporary mathemat- ics, 26(189-206):. 1984.
Gu, J., Liang Y., Sha, Z., Shi, Z., and Song, Z. Differential privacy mechanisms in neural tangent kernel regression. In Proceedings of the IEEE/CVF winter conference on applications of computer vision, 2025.
Kapralov, M., Makarov, M., and Sohler, C. On the adversar- ial robustness of locality-sensitive hashing in hamming space, 2024.
Guo, R., Sun, P., Lindgren, E., Geng, Q., Simcha, D., Chern, F., and Kumar, S. Accelerating large-scale inference with anisotropic vector quantization. In International Con- ference on Machine Learning (ICML), pp. 3887-3896. PMLR, 2020.
Karger, D. R. and Ruhl, M. Finding nearest neighbors in nrowth-restricter metrics. In Proceedings of the thiry- fourth annual ACM symposium on Theory of computing (STOC), pp. 741-750, 2002.
Gupta, A., Krauthgamer, R., and Lee, J. R. Bounded geome- tries, fractals, and low-distortion embeddings. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.. pp. 534-543. IEEE, 2003.
Karp, R. M., Vazirani, U. V., and Vazirani, V. V. An optimal algorithm for on-line bipartite matching. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pp. 352-358, 1990.
Hall, R., Rinaldo, A., and Wasserman, L. Differential pri- vacy for functions and functional data. J. Mach. Learn. Res., 2013.
Ke, Y., Liang, Y., Sha, Z., Shi, Z., and Song, Z. Dpbloomfil ter: Securing bloom filters with differential privacy. arXiv preprint arXiv:2502.0080
2025.
Hassidim, A., Kaplan, H., Mansour, Y., Matias, Y., and Stemmer, U. Adversarially robust streaming algorithms via differential privacy. J. ACM, 69(6), 2022.
Koren, Y., Bell, R., and Volinsky, C. Matrix factorization techniques for recommender systems. Computer, 42(8): 30-37, 2009.
Hu, Y.-C., Liu, E., Liu, H., Song, Z., and Zhang, L.
Krauthgamer, R. and Lee, J. R. The black-box complexity of nearest neighbor search. In International Colloquium on Automata, Languages, and Programming, pp. 258-869. Springer, 2004a.
On differentially private string distances. arXiv preprint arXiv:2411.057555 2024.
Huang, 7. and Roth, A. Exploiting metric structure for efficient private query release. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 14, pp. 523-534, 2014.
Krauthgamer, R. and Lee, J. R. Navigating nets: Simple algorithmss for proximity search. In Proceedings of the fifteenth annual ACM-SIAM symposium Discrete algo- rithms (SODA), pp. 798 807. Citeseer, 2004b.
Indyk, P. Stable distributions, pseudorandom generators, embeddings, and data stream computation. J. ACM, 2006.
Kushilevitz, E., Ostrovsky, R., and Rabani, Y. Efficient search for approximate nearest neighbor in high dimen- sional spaces. Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 614-623, 1998.
Indyk, P. and Motwani, R. Approximate nearest neigh- bors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annuul ACM symposium Theory of computing (STOC), pp. 604-613, 1998.
Le Gall, F. Faster rectangular matrix multiplication by combination loss analysis. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3765-3791. SIAM, 2024.
Jayaraman, and Evans, Evaluating differentially pri- vate machine learning in practice. In 28th USENIX Secu- rity Symposiun (USENIX Security 19), pp. 1895-1912, 2019.
Lee, Y. T., Song, Z., and Zhang, Q. Solving empirical risk minimization in the current matrix multiplication time. COLT, 2019.
Jiang, S., Song, Z., Weinstein, O., and Zhang, H. A faster algorithm for solving general lps. In Proceedings of
12

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Li, G. Z., Nguyen, D., and Vullikanti, A. Differentillly private partial set cover with applications facility lo- cation. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI 2023), pp. 4803-4811. International Joint Conferences on Artificial Intelligence Organization, 2023,
Song, Z. and Yu, Z. Oblivious sketching-basee central path
method for solving linear programming problems. In 38th International Conference on Machine Learning (ICML), 2021.
Song, Z., Xu, Z., and Zhang, L. Speeding up sparsification using inner product search data structures, 2022.
Li, G. Z., Nguyen, D., and Vullikanti, A. Computing epi- demic metrics with edge differential privacy. In Dasgupta, S., Mandt, S., and Li, Y. (eds.), Proceedings of the 27th International Conference Artificial Intelligence and Statisties, volume 238 of Proceedings of Machine Learn- ing Research, pp. 4303-4311 PMLR, 2024.
Song, Z., Wang. Y., Yu, Z.., and Zhang, Sketching for first order method: efficient algorithm for oww-badwiitth channel and vulnerability. In International Conference Machine Learning (ICML), pp. 32365-32417. PMLR, 2023a.
Song, Z., Yang, X., Yang, Y., and Zhang, L. Sketching meets differential privacy: fast algorithm for dynamic kronecker projection maintenance. In International Conference on Machine Learning (ICML), pp. 32418-32462. PMLR, 2023b.
Li, X., Liang, Y., Shi, Z., Song, Z.,, and Yu, J. Fast john ellipsoid computation with differential privacy optimiza- tion. In Conference on Parsimony and Learning. PMLR, 2025.
Liang, Y., Shi, Z., Song, 7., and Zhou, Y. Differential privacy of cross-attention with provable guarantee. arXiv preprint ar orXhv:2407.1471, 2024.
Song, Z., Ye, M., Yin, J., and Zhang, L. A nearly-optimal bound for fast regression with Loo guarantec. In Inter- national Conference on Machine Learning (ICML), pp. 32463-32482. PMLR, 2023c.
Liu, E., Hu, J. Y.-C., Reneau, A., Song, Z., and Liu, H. Differentially private kernel density estimation. arXiv preprint ar arXiv:2409.00 01688, 2024.
Su, X. and Khoshgoftaar, T. M. A survey of collaborative filtering techniques. Advances in artificial intelligence, 2009, 2009.
Lu, Y., Dhillon, P., Foster, D. P., and Ungar, L. Faster ridge regression via the subsampled randomized hadamard transform. In Advances in neural information processing systems, pp. 369-377, 2013.
Sun, J., Yang, X., Yao, Y., Xie, J., Wu, D., and Wang, C. Dpauc: differentially private auc compu- tation in federated learning. In Proceedings of the Thirty-Sevent Seventh AAAI Conference on Artificial Intelli- gence and Thirty-Fifth Conference on Innovative Appli- cations of Artificial Intelligence and Thirteenth Sympo- sium on Educational Advances in Artificial Intelligence, AAAT23AAAT233AATT AAAI Press, 2023.
Luo, Z., Wu, D. J., Adeli, E., and Li, F.F. Scalable differen- tial privacy with sparse network finetuning. In Proceed- ings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pp. 5059-5068, 2021.
Nagesh*, S., Chen J. Y., Mishra, N., and Wagner, T. Pri- vate text generation by seeding large language model prompts. Preprint, 2025.
Sun, P. Announcing scann: Efficient vector similarity search. https: http:://..oo...e.aarrooooooo////
htm1, 2020.
Pagh, R. Locality-sensitiv hashing without false negatives. In Proceedings of the twenty-seventh seventh annual ACM-SIAM symposium on Discrete algorithms, pp. 1-9. SIAM, 2016.
Tan, S., Zhou, Z., Xu, Z., and Li, P. On efficient retrieval of top similarity vectors. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-JJCNLP), pp- 5239-5249 2019.
Price, E., Song, Z., and Woodruff, D. P. Fast regression with an for guarantee. In ICALP, 2017.
Qin, L., Song, Z.,, Zhang, I.,, and Zhuo, D. An online and unified algorithm for projection matrix vector multiplica- tion with application to empirical risk minimization. In AISTATS, 2023.
Triastcyn, A. and Faltings, B. Bayesian differential privacy for machine learning. In International Conference on Machine Learning, pp. 9583-9592, PMLR, 2020.
Shi, Y., Larson, M., and Hanjalic, A. Collaborative filtering beyond the user-item matrix: A survey of the state of the art and future challenges. ACM Computing Surveys (CSUR), 47(1):1-45, 2014.
Wagner, T., Naamad, Y., and Mishra, N. Fast private ker- nel density estimation via locality sensitive quantization. Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org, 2023.
13

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Wang, Z., Jin, C., Fan, K., Zhang, J., Huang, J., Zhong, Y., and Wang, L. Differentially private data releasing for smooth queries. Journal of Machine Learning Research, 2016.
In Proceedings of the IEEE/CVF Conference on Com- puter Vision and Pattern Recognition (CVPR), pp. 11854- 11862, 2020.
Weggenmann, B. and Kerschbaum, Syntf: Synthetic and differentially private term frequency vectors for privacy- preserving text mining. In The s1st International ACM SIGIR Conference on Research & Development in Infor- mation Retrieval, pp. 305-314, 2018.
Wei, Optimal las vegas approximate near neighbors in Ep- ACM Transactions on Algorithms (TALG), 18(1):1-27, 2022.
Williams, O. and McSherry, F. Probabilistic inference and differential privacy. Advances Neural Information Processing Systems (NeurIPS), 23:2451 2459,, 2010.
Williams, V. V. Multiplying matrices faster than snneersmit-wwinggrae In Proceedings of the forty-fourth annual ACM symposium on Theory of computing (STOC), pp. 887- 898. ACM, 2012.
Williams, V. V., Xu, Y., Xu, Z., and Zhou, R. New bounds for matrix multiplication: from alpha to omega. Pro- ceedings of the 2024 Annual ACM-SIAM Symposium Discrete Algorithms (SODA). pp. 3792-3835. SIAM, 2024.
Woodruff, D. P. Sketching as a tool for numerical linear alge- bra. Foundations and Trends@ in Theoretical Computer Science, 10(1-2): (011-2):1-157, 2014.
Woodruff, D. P. and Zhou, S. Tight bounds for adversari- ally robust streams and sliding windows via difference estimators. In Proceedings of the 62nd IEEE Sympo- sium Foundations of Computer Science (FOCS), pp. 1183-1196. IEEE, 2021.
Woodruff, D. P. and Zhou, S. Adversarially robust dense- sparse tradeoffs via heavy-hitters. In Advances in Neu- ral Information Processing Systems 37 (NeurIPS 2024), 2024.
Yu. D., Naik, S., Backurs, A., Gopi, S., Iman, H. A., Kamath, G., Kulkarni, J., Lee, Y. T., Manoel, A., Wutschitz, L.., Yekhanin, S., and Zhang, H. Differentially private fine- tuning of language models. In The Tenth International Conference Learning Representations, ICLR 2022, 2022.
Yue, X., Du, M., Wang. T., Li, Y., Sun, H., and Chow, S. S. M. Differential privacy for text analytics via natural text sanitization. In Findings, ACL-IJCNLP 2021, 2021.
Zhu, Y., Yu, X., Chandraker, M., and Wang, Y.-X. Private- knn: Practical differential privacy for computer vision.
14

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Appendix
A. Preliminaries
We use Ö() to suppress poly log factors in n, d, 1/6. We use [E[]] and Pr[:] to denote expectation and probability. We use Tmat (n, m, d) denote the time to multiply an m matrix with an m d matrix. For positive integer n, we use [n] to denote the set [n]
use x: denote the transpose of æ. For vector I I?, ||ll| to denote its i2 norm, i.e., ||z]||2 :- (
{1, ... .n). For vector /2/1/2, For two real numbers a, b > O, we will use (1 + a}b to denote
E [[1- a,,,, (1 + a-66 for > 0.
For a point v E Rd and r > O, we use Bi|- (v, r) to denote the ball centered at v of radius r in some norm. When the norm ||- is clear from the context, we abbreviate this with (uu, r). We use g to denote the unit sphere of dimension d. Let F) be measurable space and let probability measures P, Q be defined on FD) The total variation (TV) distance between P and Q is defined to be drv(P. (P.Q) Q) = supлez (P(4) - Q(4)-
We will be using exponential random variables extensively, and we recall its definition here.
Definition A.1 (Exponential Distribution). The exponential distribution with parameter X, denoted by Exp(A), is the distribution with PDF
f(z;A)= = { De--d fA>20, 0,
0,
otherwise.
We will also work with order statistics.
Definition A.2 (Order Statistics), Let X1,..., Xn be i..dd random samples, the k-th order statistics, denoted by X(xe)> is the random variable associated with the k-th smallest value over the samples.
For extreme order statistics such as X(1) and ((n), they could be generated efficiently via inverse CDF sampling.
Fact A.3. Let n 21 be a positive integer, suppose we can generate U ~ Unif 1) in O(1) time, then for any distribution with a closed-form CDF distribution, X(1) and X(n) can be generated in (1) time.
B. Augmenting Oblivious ANN Data Structures with Differential Privacy
We develop generic algorithm that takes oblivious ANN data structure, and transforms it to one that is adaptive. We will start with a simple but inefficient algorithm, and improve its efficiency afterwards.
We require these data structures to output all answers they find (within their runtime budget, which we will formalize) instead of outputting only single answer. In the context of LSH, this means that instead of outputting one approximate near neighbor, it needs to output all approximate near neighbors it finds. As the runtime budget for a query n², can output at most n approximate near neighbors.
Before introducing the algorithm, give some background in differential privacy.
B.1. Preliminaries Differential Privacy
Differential privacy refers a class of algorithms for which, when one slightly perturbs the input, the output distribution remains relatively close. This intuitively will mean that for adversary, it cannot learn useful information by adaptively adjusting its input to an algorithm.
Definition B.1 (Differential Privacy). We say a randomized algorithm A is (e, diiffeerettl private if for any two databases S and S' that differ only by one row and any subset of outputs T, the following
Pr[A(S) E TI e
e Pr[A(S') +
holds. Here the probability is over the randomness of A.
Differential privacy can be composed, and the advanced composition theorem says that k-fold adaptive composition only blows up the parameter by a factor of roughly Vie instead of k. Similar to (Beimel et al., 2022), we will utilize advanced composition reduce the number of oblivious data structures required and gain runtime improvements.
15

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Theorem B.2 (Advanced Composition, see (Dwork al., 2010)). Given three parameters e, do, 8 2 1f Af: ... Ap. are each (c, ()DP algorithms, then the k-fold adaptive composition Ase .... A1 is (Co, ón kö)-DP where
50 v 2k (1166)) E 2ke²
One can boost the privacy budget by subsampling the dataset first, then running the differentially private algorithm on the subsampled set. We state version where 0. Note that it can be easily extended account for non-zero 6.
Theorem B.3 (Amplification via Sampling (Lemma 4.12 of (Bun et al., 2015))). Let (0, 1] be parameters. Let A denote an OP algorithm. Let S denote dataset.
Suppose that A' is algorithm that,
constructs database T SS by subsampling with repetition k S n2/2 rows from S,
returns A(T).
Then, we have
66k n 0,
A' is
DP.
Theorem B.4 (Generalization of Differential Privacy (DP)). Given two accuracy parameters E (0, and 5 E (0,e/4). suppose that the parameter t satisfies that t 2==² loo((2/6))
We use D to represent distribution over a domain X. Suppose S ~ Dt is database containing elements sampled independently from D. Let A be an algorithm that, given any database S size t, outputs a predicate + {0, 1}.
If (s, 6)DD, then the empirical average of h on sample S, i.e.
1(S)
1
Σ h(x),
S
EE
and h expectation over underlying distribution D, i.e.,
h(D) = E [h(x]]
xnD
are within 10s with probability at least 1 88e:
MMS)) M(D) 2 10c s 8/E.
Pr S-D A+-A))
We next consider the task of differentially private selection: we have a discrete space of outcomes, and the goal is to output the largest histogram cell:
Definition B.5 (Differentially Private Selection). Given n categories, let the database S be such that, each of its rows is a binary vector of length n, with each entry corresponding to whether the row belongs to the i-th category or not. We say an algorithm is an (e, -)-differentialll private selection it releases the index of the approximately most popular calegory over the database S, and is (s,0) O)-P.
For any differentially private mechanism, cares about privacy but also utility, i.e., after adding noise, how good are the estimates compared to the algorithm without adding noise? Here, we focus privacy, and we will later use the privacy to provide utility guarantees. For count queries, the most common approach is the Laplace mechanism, where properly chosen Laplace noises are added to each count. Here, we use a similar approach that instead adds exponential noises. This approach more widely adopted for Exponential Mechanism, yet it still offers the same privacy budget as that of the standard Laplace Mechanism for reporting the noisy max index. See e.g., (Dwork & Roth, 2014; Ding et al., 2021) for more details.
Theorem 3.13 of (Dwork & Roth, 2014)). Given a database S with each row being a binary vector of length n, consider the following algorithm:
Theorem B.6 RREFORRONESDDEDDOOOYYAAAAC
16

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Compute the count for each calegory;
Add an i..dd exponential noise Exp(1/E) to euch count;
Ouipud the category with the maximum noisy count.
The algorithm gives (e, 0) differreetiil private selection.
B.2. Reducing Monte Carlo Search to Selection: A Slow Algorithm
In this section, we show how to utilize the REPORTNOISYMAX procedure for adaptive data structure design. Recall the framework introduced in (Hassidim et al., 2022) for streaming and later extended for improving the preprocessing and update time for dynamic data structures (Beimel et al., 2022; Song et al., 2023b; Cherapanamjeri et al., 2023): the idea to set up the database the random strings used by oblivious data structures. Suppose we have A1, . As. oblivious data structures, each with their associated random strings r1....:PA 1 E {0, 1)" The database is R. where the i-th row is the random string r;. Notions such as sensitivity are in turn defined with respect these random strings. We will now illustrate how to tie these Monte Carlo search data structures to the selection problem. We will use r)NNN as an example, but our reduction does not exploit any additional structure on (c, rc,NN,NNN, so it can be well-extended to more general search data structures.
Given a dataset U E Rdd and a possibly adaptive query u E Rdd recall that a (c,r)-ANN data structure would have the following behavior:
If there exists some u E U with ||u- vll < r, then it outputs some point w' E U with -ww-ool S cr. This succeeds TO (note we do not need probability boosting for our base data structure, at this stage). We modify the data structure to output all such points has found.
with probability at least 9
If there is no such point, report NULL.
Note that ANN data structures can only produce false negatives but no false positives. We can associate the output of the data structure with a binary vector of length n as follows: the i-th entry of the vector corresponds to the decision the data structure has made on the point ug, i.e., if outputs u,, then we set the i-th entry to be 1, and otherwise. If the data structure outputs nothing, we set the vector to be O,, Fixing dataset U and query v, these binary vectors are completely determined by "l....,7h Denote these binary vectors 62 bt. We then execute the on these vectors, and output the corresponding index. We now describe the details of our algorithm.
mechanism
We will use T to denote the number of queries, and & to denote the total number of data structures. We assume each data structure succeeds with probability at least 1 - 6. We let EDP denote the DP parameter for REPORTONESIDED- NOISYARGMAX. We will use 6tal to denote the overall failure probability of our algorithm, and B = 6ta/ to denote the failure probability of single query step. The algorithm is as follows.
Initialization.
Prepare independent copies of oblivious data structures, denoted by Al.... Ag, over the dataset U.
Query.
Receive query vector e IR..
Sample Ö(s) indices independent and uniformly from [k] with replacement. Denote the corresponding data structures by A()) A A().
Feed v into A(1) Agt receive binary vectors (f(1) (0)
Compute REFORFOOWESSDDERXXOOXVVAKCAAAAA ((0) with parameter EDr. Let be the corresponding index.
17

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Output u, ul v|12 er, otherwise output NULL.
Update.
Receive update vector u E R4.
Update AI with u.
We will specify the parameters show that the algorithm is indeed differentially private with respect to the internal randomness of the data structures.
Setting Parameters. We start by setting the parameter EDP which affects the privacy guarantee of REPORTONESIDED- NOISYARGMAX, We will set ēDP 1/2 (in fact, for our analysis, EDP can be any constant smaller than 1). Set the number of samples e to be
= O(s log (nn=3))))))))
and the total number of data structures & be
200 61 EDP : V 2T 22 (1000/33)
= =(VVT.s)
Privacy Guarantees. Our analysis differs from standard DP analysis, in which one could reason over the privacy and utility simultaneously. We will start by showing that the algorithm is indeed differentially private, then use this fact to argue the output of the algorithm provides good utility.
To understand the privacy of the algorithm, we adapt the framework from (Beimel al., 2022): let -1;-.., 7% E {0,1)* denote the random strings used by data structures ,I,...,AA, Ar and let R {ri.....77 J } be the database whose i-th row is т₁. We will prove the transcript of the interaction between the adaptive adversary and algorithm is differentially private with respect to R. Fix a time step f. We let out, (R) denote the index output by the algorithm at time t. Even fixing R, the output out, (R) is still a random variable as it depends on i.i.d. exponential noise that oblivious to the algorithm. Similar to (Beimel et al., 2022), we define the transcript at time as (R) = (v,, (R); Define the overall transcript as T(R) (R)),, ..., (R).
We view Ti and as algorithms that given database R, output the transcripts. This enables us reason about differential privacy with respect R.
Lemma B.7. For any time step t, To is (%) EDP, DP with respect to R.
Proof. Note that Ti( = (v,, out, (R)). For any fixed single step I, i2 does not provide extra information about Rt so we only need to consider out,(R).
b(0) with parameter éDp. As we have argued in the preceding discussion, the binary vectors are determined by (r())...,,P()) C R which are subsampled from R. As out, (R) (ÉDP, ODP with respect to the subset (Theorem B.6), by Theorem B.3, it is ( EED,, 0)-DP with respect to R. Finally, observe that out, (It) is a post-processing of (ut) as it's a deterministic mapping that only depends on the output of out,(R). (R) Hence, we conclude that out, (R) is 6t EDP, O)- with respect to R, as desired.
We let out, (ft)= == RUPORTOONSSSDDDDNOISAAARMMM
Given that single step is DP with respect to R, we can then perform advanced composition to prove the privacy of T.
Lemma B.8. T is ( (000 100
8 >DP with respect to R.
Proof. By Lemma B.7, we know that for any fixed t E [T), T((R) is (8) EDD, 0D- with respect to R. Further, observe that T is adaptive composition of Tr o... Ti, so we can apply Theorem B.2 with EEP and 5 0, 8/100. 100. This yields a mechanism that is (Eo, -DP with respect to R, where
eo = / (n1001))/)) - e
18

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
1
+
200
200
1
100"
Thus, we conclude T is (000 ( )DP with respect R.
Accuracy: Differentiating Signals from Noise. Given the privacy guarantees of T, we are ready to prove accuracy against an adaptive adversary. Similar to (Beimel et al., 2022), define V, = (t), U2,...., 24) to be the query sequence up to time t and consider fceding a random string r (for initialization) and 7. to an oblivious data structure A. Let A(r, T.) denote the output. Finally, define accs, (r) be the indicator of whether A(r; Fe) succeeds, i.e., if i2 is "yes" instance, then A(r, U.) most er away from v4. We will prove that with high probability, large indeed outputs a subset of points in U that constant fraction of all data structures succeed.
Lemma B.9. For any fixed time step E [T') we have Σj=1 acc,, (ri) 2 f with probability at least 1 - 3.
Proof. The proof will rely the generalization property of DP. First note that accs, is determined by the transcript T, vs is substring of T and U, determines acCv, To invoke Theorem B.4, first note that each row of R is drawn uniformly, and due to Lemma B.8, we know that T is 100 100 ]DP with respect to R. Thus, we have that the empirical average of acCo, over I which is & Σ5= acc., (r²) and the expectation of acc,, over the uniform distribution Elacc,, (r)) are close. Setting e = 1/100, 8 = 3/100 and k >> 2 1og(2e/6), we conclude
k
Pr
accs, (ry) - Elacco, (r))
2
S 3.
10
It remains to get a good handle on the expectation. If we let 27 denote the uniform distribution we sample r from, then we can write the expectation EE-zu[acer, (r)] = Pro-ul (acea, (r) = 1] as acc,, (r) is an indicator. The crucial point here is that the probability is taken over the randomness of when the sequence of queries T. is fixed. Thus, we can utilize the property of our oblivious data structure, i.e., Pry-z((acor) (r) = 1] N
9 To put it together, we have
To
k
acCT (r₂) 2
10
10
j=1
5"
Thus, we complete the proof.
To improve the efficiency of querying, recall that we resort to sampling, We prove that sampling does not hurt the accuracy. Lemma B.10. For all t E [T], let I be the sampled indices of time i, we have Σ5=1 acc,, (rG)) 2 21 with probability at least 1 Stall
Proof. Fix any L E [T], we condition on the event that Lemma B.9. Therefore Σ acc,, (ry) 2 kk This means that any i..dd sample (with replacement) from these & indices succeeds with probability at least 4/5. Consequently E acc,, (rG)) L.. By Hoeffding's bound, have
2a²
Pr
acc (r()) E
acc (r())) 2 a
2expl (isp(--1)
and setting a L,, we conclude that Σ ac07, (r6)) 2 L1 with probability at least - -exp(-0(0)
19

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
We present abstract way to reason over the data structure task. Fix the preprocessed dataset U E IR4 Consider any (possibly adaptive) query E Rd, and let b E (0. 1 denote the characteristic vector of with respect to U, in terms of (c, J..NN if there exists some u, E U with l|u, - w/| S r, then: for any E [r/] with ||u; - = S cr, we set bj- = 1. Note that if no point in U is r-close to v, then b is either the all-Os vector or it has some nonzero entries that are cr-close to v. Similarly, for each data structure AI,...,
and their corresponding random strings ri,-..,, .kk, we use 669) to denote the characteristic vector under the random string r,, i.e., 06) 1 if and only if the LSH A, discovers that |u w|l Note that it is completely possible that the vector b has large support size, but some (( = O,,-
Now, imagine we have an (nn) time budget. Then our algorithm is essentially identical to reporting the noisy max: we first sum over all characteristic vectors: (rum = Σxm1 600) Note that the i-th entry of banm counts the total number of successful data structures that report point u4 Then, we sample n independent Laplacian noise variables of scale 1/EDP. and then add these noise variables to each entry of Jaum, Then we simply report the maximum index of the noisy counts with a simple post-processing by directly computing the distance between the corresponding point and the query. The algorithm is naturally (EDP, O)-DP with respect to the random strings "',...., P
To prove the utility of the algorithm, i.e., that we can actually differentiate the signal from the noise, we require the following tail bound for exponential random variables:
Lemma B.11. Let Y ~ Exp(b), then
Pr[y 2 b. S exp(-()
Let us choose t = Colog n for some absolute constant C > 0. This means that even if we choose &Dr to be 1/2, the magnitude of the noise will be roughly O(log n1). Consider a simple case, where the query v only has one point u E U with - ||u-
S r and ||u - u|I2 I cr. Then, for a successful data structure A,, it will have exactly one non-zero entry. Let us assume that we sample/ = Ollgg" n)) independent data structures to perform the mechanism, using EDP = 1/2. Then by amplification via subsampling, the algorithm is 6f conclude the algorithm is "oo (00- JDP. We can then use the generalization property of DP to conclude that, with probability at least 1 - 1/ (oly(n), at least a 3/ 4-frrction of the sampled data structures succeed.
& DDP Performing an advanced composition over all queries, we
Conditioning on these events, we argue that the noisy max is indeed the correct answer: we know that large constant fraction of data structures succeed, therefore the corresponding point in balm has count 52(log n). On the other hand, the exponential noise itself has magnitude at most Olog n). This means that adding the exponential noise, we still differentiate the point. We formalize this argument with the following lemma.
Lemma B.12. For all E [T), the algorithm outputs a point u, that is c-ANN for the adaptive query v, if U, satisfies Assumption 1.2, with probability at least 1 - - - 1/ (n)y
Proof. By Lemma 10 among the I samples, at least - -fraction of the data structures succeed, i.c., if there exists an r-near neighbor of u, then at least / data structures have their characteristic vectors with at least 1 non-zero entry. By Assumption 1.2, the support size of each characteristic vector can be most 8; since we set / O(s log" (n/B),, by the pigeonhole principle, there exists at least one entry in baum with magnitude ((log"(n/33) (n/ Now, conditioning the event that all n Laplacian noise variables have magnitude Ologg r)); this holds with probability 1 - 1/ (nly(n). Thus, we know that there exists at least one entry of baum which has magnitude 2(log" n) and we can differentiate this entry from all the noise added.
Now, consider the case that there is no point u E U with ||u- - | < r. Then the data structure is allowed to either return points that are er-near neighbors of vt, or return nothing. Since the base data structure either outputs false negative (a er-near neighbor) outputs nothing, we analyze two cases:
| 300 2 C Coog" n for some fixed constant C. In this case, we know that the max index before adding the noise must correspond to a cr-near neighbor. Hence, adding the noise and outputting the noisy max will not hide this large entry, and so we can return and satisfy the specification of an c-ANN data structure.
Case 1:
Case 2: || Ioo < Clog² n. In this case, it must be the case there is no r-near neighbor. Regarding the mechanism, since the magnitude of the signal in this case is (log n) and with high probability, the exponential noise has magnitude O(log n), we have that
SEPPOROONESIDEDNOSSYARROO
20

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
outputs a noisy index (meaning that the corresponding index is not cr-near neighbor). In the post-processing phase, ensure the algorithm outputs only er-near neighbor by checking the distance.
This concludes the proof of correctness.
To compute the failure probability, note that constant fraction of the data structures succeed with probability at least
1 - ofai and all exponential random variables have magnitude (llog n) with probability at least 1 1-1, 1/ //poly()). A union bound concludes the bound on the failure probability.
Of course, this algorithm is by no means efficient - it takes ((n) time to generate all noise variables per query, making the sublinear query time linear. In the next section, we will show it is sufficient to generate & exponential variables for the support of (aum, and take the noisy max over these entries.
B.3. Sparse Noise and Order Statisties: A Fast Algorithm
We make the following observation for the EEPOORTONESIDEDNOOSYAARRO with the max noise must be the one contains X(n). the largest order statistics of the exponential distribution. If from has s nonzero entries, then there are two cases: if X(n) is among the nonzero entries, since those entries are all positive, the max entry must be within the nonzero entries; if ((x) is not among the nonzero entries, then the max entry is among the entry contains X (m), and the nonzero entry with the largest magnitude after adding noises. Note that the first event happens with probability A and for this case, we generate
algorithm: if feum = On. then the entry
i..dd noises until they do not exceed X(x) so that they obey the order statistics distribution. For the second case, we generate s i.i.d. noises until they do not exceed X(n), randomly assign zero entry to (n)) and output the max between ((n) and the largest nonzero noisy entry. Note that this algorithm is extremely efficient - according to Fact A.3, (in) can be generated O(1) time, and the above procedure runs in ( log n)) time with high probability, proportional to the support size.
Fact B.13. Let Z be a geometric random variable with success probability p E (0, 1), then for any positive integer k. we have
Pr|Y > k] I exp(-klog((/(1-))
Proof. Note that by definition,
Pr|Y > k] = (1 - p)*
= exp t log(1 (1 p))
exp(-k: log(_-log(1/(1- p))).
Lemma B.14. Let A1, be Iwo algorithms, with the following behavior: Let > 0:
AA, at time t, it receives an s-sparse vector E No and let U. S. [m] denote the support of u. We add a dense exponential noise vector with parameter 2, denoted by 1) IR. and add this RR. and output index such that i, arg maxje|n] (u + n)s;
As. at time receives an s-sparse vector u E N" and let U, S. [n]] denote the support of u. We flip a biased coin with probability of being head 3. head, we generate a max noise X from the distribution X(n) of parameter 2, and then repeatedly generating - i.i.d. exponential noises of parameter until none of them exceed X, and let .p..... Ma-1 denote these noises, form vecior 7) E Tp with the support being Ut, and the values being randomly assigned from :......7s-1,.. Then output i. = arg maxje(n] (7 + p)j If the coin flips tail, then generate X from X(n). and generate 8 i.i.d. exponential noises until none of them exceed X. Randomly assign X to one of the non-support entry denoted by in, and let n denote the noises for the support, output in if X > maxje[m] (μ + 7)s and output arg max (u ς) otherwise.
Then, Ai and Ag have the same output distribution. Moreover, Ag runs in Osslog n) time.
Proof. We will prove that As has exactly the same output distribution as Al. We do so by analyzing an hypothetical algorithm A²2 that generates from X(n) first and assign it to a uniformly chosen entry i., then generate the noises for all
21

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
other entries conditioning they smaller than X. We will prove the distribution of the noise generated by A₂ identical A1, then it's easy that the output distribution of A2 is the same as A1-
Suppose the noise 77 is generated from distribution with PDF ff and CDF F, then the CDF of ((n) is G(a) F(x)". and PDF g(x) = nF nF(=)""" Let the joint CDF of noise generated by A₁ be Fi FI and the PDF noise generated by A2 be F Let the sorted array of Fi,-..,, En be -i,-.. Fn and z6 = 00
#n) F(x1) F -... FT,)).
we have:
F(ay)
Fa Fn)
( II
dæ
F(z)
i=1
F( F(x)
F())
dx
i= j=1
1=1
Σ (n -++ 1- f(x)F(x)"
J-1
II F(r dr k=1
Σ
F(xx())) (F(z))--st) F(aj-1) )
j=1
F( F(x
= F (Z In)
Hence, the noise distributions of these two algorithms are identical.
To see A and Al have the same noise distribution, consider two cases. If the max noise X is in the support (happens with probability 4), then we know that the max index must be within the support. For the noise distribution, it's easy to see that identical. For the tail case, the reasoning is similar,
as long as all n7," 's are smaller than X, then the noise distributions except that maximum must be over X and the noisy entries in the support.
Regarding the running time, we only need to examine the probability that the noises 7), ,,,,..., V ....... 7/s do not exceed X. We without loss of generality prove for the case where we generate independent exponential noises. Let A be the parameter, note that this is equivalent to the probability that Y(s) I X(x), where Y(s) is the max order statistics for another independent sequence of exponential noises. The CDF of Y(s) is FY (v) = (1 - e Auy",, , and the PDF of X(n) is fx... (x) nde -x- (1 Azyn-1, then have
Pr(V() S X(m))= = Ju Pr[V(e) S x))x(,)) (x) dx
(1 - --- dryysnde do Anga-1 dr
nde nde-bo(1 (1111 e --doynnto1 dx jo
we do change of variable 1 1 Au so du de dr, and for 0, 0 and for oc, == 1, therefore
fo nde nde- -x - -oyn dx {' + du
n
similarly, for s noises, the probability is n+s-I' In both cases, we have that the success probability is at least } 2, and note that this is geometric random variable Z. by Fact B.13, we have that
Pr|Z k] s exp(-k).
22

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
set k cloog ri for some large enough constant that k is integer, have this happens with probability at most / (n)y(n), hence with high probability, we only need to generate the noises for k O(log n) times. Moreover, X can be efficiently generated via inverse CDF sampling, the overall runtime for generating these noises is O(s log n), as desired.
C. Speeding Up Updates via Batching
In this section, we focus on developing fast update procedure for decremental & LSH against an adaptive adversary. This crucial for applications such as online weighted matching (see Section 4.1).
C.1. Adaptive Low-Dimensional LSH
We start by reviewing the algorithm for low-dimensional & LSH, against an oblivious adversary. Throughout, we let e, 8 E (0, denote the precision and failure probability.
Initialization.
Prepare Johnson-LLindenstrauss (Johnson & Lindenstrauss, 1984) transform S Rd - Rm where O log(n/6)).
Compute SU.
Initialize an (c,r)-L2 LSH data structure on SU.
Query.
Given query point Rd, first compute Se.
Query the LSH with Sv, output the corresponding point.
Deletion.
Given a point u E U to-be-deleted, first compute Su.
Locate Su the hash buckets of the LSH, remove Su.
The deletion procedure first computes the embedded point time kd = 2d then locates the hash bucket in (nn)) time. order to make such data structure adaptive, we need to create vT independent copies, and naïvely update all vT. data structures takes time (up to polylogarithmic factors and assume O(1)):
VT s nd+
While the term VT s n' seems to be unavoidable as we will have to update all L.S data structures, the first step of applying Johnson-Lindeensrrass could be further acclerated via batching and fast rectangular matrix multiplication.
C.2. Faster Update via Batching
Recall that we define (a. b) for b 0 to be the value such that Tmat (a, b, 0(a b)) (ab))+o(1), Note that 0 is monotone in its argument, i.c., fixing one argument, 0 grows or decreases with the other argument. Our idea is the following: instead of eagerly updating all data structures whenever point deleted, we can delay the deletion until the data structure is queried, which is when the update must be performed. We will partition the length-T query sequence into blocks of size 0( 8(VT s, d) and for simplicity, we will denote in the following.
23

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Initialization.
Prepare h = VT JL transforms (Johnson & Lindenstrauss, 1984) Si...., Sk Rd 7 R where m Olg=21og(n/6).
S1
S2
Set S =
E Rkxx
Sp
Compute SU.
Initialize & (c,r)-f2 LSH's on SJU, SUU, S S.U.
Associate a deletion list to each data structure. The initial deletion lists are empty. Also initialize a global deletion that keeps track of all points deleted far.
Query.
Receive query point E Rd.
Sample (s log" 2 n) data structures, denote the sampled JLs as S(i).... S()-
(11)
Batch compute :
E (m
S
Update the sampled data structures that up-to-date, update their corresponding deletion lists.
Query corresponding LSH's with
S(n)
Compute the characteristic vectors of these LSH's outputs, apply sparse REPORRONNSSIDDDNOOSVAAKGAA to the count vector and compute the order statistics.
Output the noisy max index.
Deletion.
If the algorithm is at the end of block:
Update all & data structures with 0 points in the block. particular, let u())....; U(0)) denote the points to-be- deleted.
Compute S ((1))
((())
Delete S,un)..... ..... Son from the i-th LSH.
Update the deletion list all data structures and the global deletion list.
Otherwise, update the global deletion list.
We first note that the correctness of the data structure follows directly from the design: for each query, will update the data structures first. So we focus analyzing the runtime.
Theorem C.1. Let U C Rdd satisfy Assumption 1.3 and (vi...., UT C R be sequence of adaptive queries. There exists
randomized data structure with the following guarantees:
It preprocesses U time Ö(Tmat s, + /T 8 I.t))
24

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
It uses space OVTT - nd);
Given a query for t [T], it returns point u U with l|u - - S cr if B(,,)) + and NULL otherwise, with probability at least --1/ 1/ poly(n). This procedure takes time Ō(s (d + n)));
If ue is the ouiput of er. it deletes in amortized time Ö((VT d) 10 VT 8, + VT (..n))
Proof. We note that preprocessing time, space and query time, together with their guarantees are straightforward, so we will focus on bounding the deletion time. Our analysis will be over a block of size 0, and the final update time will be amortized over A steps. There are two cases to consider.
Case 1. Update during the query. Each time we receive query, we need to sample O(s log n) data structures and update these data structures accordingly. Suppose we are the i-th step of the block. Then in the worst case, all of these data structures need to be updated for all prior points deleted. We can compute the update time over the block as follows:
max (1, d.
iln
Σ Óiis (d + n²))
time to apply JL
time to update LSH
= (d + n²)).
Thus, the amortized cost per update-during-the theeggg-th---eeeee querr is Ö(0s (d + n²)))
Case 2. Update at the end of the block. In this case, we need to update all k = Ö(VT s) data structures with points.
Applying JL takes time
Tiaat (VT- 8, d, B(V s, d)) = Ō(((TTTTTTT) s. (ddd) +
by the definition of 0, and updating LSH's takes time Ö(e VT s n²). Thus, the amortized cost per step is s- /0 + vT s-n)).
As the second cost dominates, we obtain the desired update time.
Remark C.2. As our data structure gains an advantage over using d copies via net argument when VT 8 S d, we know that 0( (VVT. 8, d) Z 0(vT 8, VT. s) = (VT 8)a as 0 is monotone, and a RS 0.32 is the dual matrix multiplication exponent (Williams et al., 2024; Le Gall, 2024) where (mac(n, n, n²) ) = n 2+11)_ This implies an amortized cost per update of
(VT 5)2-0+011) +l+0(1) VT 8 n (VT 8) 0.60+((1)) (++0(1) + VT 8 n
Compared to the naive update in which the first term is VT d, this improvement is significant for relatively large vT
C.3. Generalization to LSH
We note that the above algorithm does not exploit any particular structure of lgj use the Johnson- Lindenstrauss transform (Johnson & Lindenstrauss, 1984) in its most general formulation, the speedup we obtain comes from batch matrix multiplication. Thus, we could generalize the algorithm to any lp norm for E (0, 2). using p-stable sketches (Indyk, 2006; Datar et al., 2004).
Corollary C.3. Let S Rdd satisfying Assumption 1.3 and (ui,..., uT S R.d be a sequence of adaptive queries. Let p E (0, 2). There exists randomized data structure with the following guarantees:
It preprocesses U in time D(Tmat(VT) -...-s.d 8, d, ) + (.tt))
It uses space Ö(VT s 1 + nd);
Given a query is for t E [T) it returns a point u E U with 1/ve u/lp s cr B(rr)) # and NULL otherwise, with probability least - 1/ (n)y This procedure takes time O(s (d n²)):
If ue the output of vt. deletes un in amortized time Ö((VT do-ddye 1 /0( vT s, + VT s.n
25

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
D. Adaptive Regression with Private Median and &o Guarantee
In this section, we provide the necessary background for adaptive regression problem under turnstile updates, with a variety of algorithms with diverse guarantees.
D.I. Preliminaries on Adpative Regression and Sketching
The adaptive regression we will be studying is defined in Assumption 1.4, we will state here again for completeness.
Let U Rnxd be a design matrix and E R" be response vector with n > d, the goal is solve the ég regression problem:
r
=
arg min ||Uz bll2. #ER
with the optimal solution given by the normal equation:
with Mt being the Moore-Penrose inverse of the matrix M. As solving the normal equation exactly is time- and space- consuming, one is usually interested in finding approximate solution ö Rd such that
| - bll2 s (1 + U3) - bbl2
for some 0.
In the adaptive turnstile update model, we assume adversary could curate sequence of updates (Ui,..., .r) adaptively, where each v, for E [T] could take one of the two forms:
Bxd i.e., is an update to the design matrix;
0t RR, ie., U/ is update to the response vector.
We need to design algorithm that processes these adaptive updates to either U or b, for simplicity will use (U,, be) to denote the design matrix and response vector after the t-th update. Our algorithm needs to respond with an approximate solution 2t to the 1-th & regression:
|1 - S (1 + a:) min |U: blll..
The main objective is to design an algorithm that
Uses space that sublinear in n, sublinear in T and small polynomial in d;
Has efficient update that depends on the size of or and small polynomial in d.
In the following, for the simplicity of presentation, we will make common assumptions that the length the stream T = (oly(n), and that in any round < T, entries Ug, b are always in the range [-n", n²) for some constant y >> 0. These assumptions can be removed at the expense of introducing additional factors our results.
Sketching will be key algorithmic tool to speed up the procedure of solving &2 regression, we introduce them in the following.
Definition D.1 (Oblivious Subspace Embedding). Fix dimension parameters d, approximation factor and failure probability B. Suppose D is a distribution on r x n matrices S. where r is a function of n, d, a, and B. Suppose that with probability at least for any fixed matrix U, a matrix S drawn from D satisfies: for all vectors x E Rd
|| (1 [x
then we call D an (o,, -obliv-Ol Subspace Embedding (OSE).
26

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
We will mainly need the OSE property with a = Q(1) and / 0(1). We refer this 0(1)-OSE. We list a collection of sketching matrices that will be used throughout this section.
Definition D.2 (Count Sketch (Charikar et al., 2002)). Let S E x be constructed via the following procedure: Randomly
draw h: [n|] + [r] from a pairwise independent hash family, and draw o : [n] + {-1,1] from a 4-wise independent hash family. For each of the n columns (ie(n). choose row h(i) E [r] and an element o(i) from {-1,1}. We set
Sp(0), = (i) for all i E [n], and set all other entries of S to be O. We call such S a Count Sketch matrix.
Definition D.3 (Gaussian Sketching Matrix). We say S Tgrx is Gaussian sketching matrix if all entries are indepen- dently sampled from the distribution (0/r)
Definition D.4 (Subspace Randomized Hardamard Transform (SRHT) (Lu et al., 2013)). The Subspace Randomized Hardamard Transform (SRHT) matrix S E T is defined as the scaled matrix product S := PHD. where each row of matrix P E {0, 1) j contains exactly one at a random position, H is the n x n Hadamard matrix, and D is a X n1 diagonal matrix with each diagonal entry being a value in [-1,1} with equal probability.
We will use the following differentially private median procedure:
Theorem D.5. There exists an (c, O)differrentiall private algorithm that given a database S E X", outputs an element x E X such that with probability at least 1 - 3, there are at least |S|/2 I elements in S that are bigger or equal to z, and there at least |S|/2- I elements in S that are smaller or equal x, where I 0 log (x)). Moreover, private median runs in time
O( "S) (1x11/)))))) poly log [S|).
We will use PMEDIAN(211.... to denote the invocation of private median on .1,..., Zs.
D.2. Generie Algorithm with Private Median
A critical property we will be leveraging in designing the algorithm is the foe guarantee of the sketched solution (Price et al., 2017; Song et al., 2023c): this guarantee states that the sketched solution and the optimal solution x² are close not only in terms of their costs, i.e., | bll2 (1 = a) - bll2. but are close the sense that | - 20 is small. Note that naïve bound of | xx lloe is just [ x² 112, as could have the scenario that all the discrepancy concentrate in few coordinates with most coordinates are the same. When S is an SRHT matrix, (Price et al., 2017) shows that | x= |2
is too pessimistic and stronger bound exists, in particular, they prove
J - x 1ox S
UUx
b112- (U)
(2)
Va
holds with probability 1 1-33. 3. The number of rows required is further improved in (Song et al., 2023c). To improve the space usage and runtime efficiency, we further compose the SRHT matrix with Count Sketch matrix.
Lemma D.6. Let D be a distribution of matrix product SSRHT Scs, where SSRHT E Rrxx is an SRHT matrix and Scs ma is Count Sketch matrix. For some O dlogg (llo"( in Equation We will refer this property as (a. acccuracy
(n/3) and O + 2²3)), D satisfies the loo guarantee
Proof. As shown in (Price et al., 2017), all we need is that both SSRHT and Ses are drawn from distributions that individually satisfy Equation (2) (up to a constant factor loss in failure probability and approximation factor). The main result of (Song et al., 2023c) proves that SRHT with r rows satisfies Equation (2).
For Scs, following the core lemma in (Song al., 2023c), it suffices show that it is an Oblivious Subspace Embedding (OSE) with an (1)) approximation factor, and it satisfies the following Matrix Multiplication guarantee: for any fixed vectors g, / E I
Pr[lg] T Sysh -Th]
vm ||lla|111aal S B.
is shown, e.g. in (Woodruff, 2014) that
27

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
1. Count Sketch with m (dd poly log d) is 0(1)-OSE, and
2. Count Sketch with m = OOd/((/a)) a satisfies the Approximate Matrix Multiplication property.
This concludes that D satisfies the &o guarantee in Equation (2).
We now ready to describe our algorithm. Throughout, will let E (0, be the approximation factor, 3 E (0, 1) be the failure probability and we require an extra parameter which is an upper bound on the condition number of U; throughout the update sequence. Since our algorithm would utilize private median, we let ēDP to denote the privacy parameter which will be specified later. We will refer this algorithm to ADAPTIVEREGDP.
Initialization.
(Parameters for sketches): Let a' 2 and 3' 0.01, set r 0 logg" (n/8') x
and m = 0(d + a'
a²
(Parameters for privacy): Let r O
n. ,..., n² log Td where X (-n7...., -2 ,,,
set h:
SDp
O(EDP I (Tdlog(//B):
Prepare independent copies Si,... Sy E RR"x according Lemma D.6;
Let sky SUU and ski, S.b for all i [k]. Update.
Receive update Us;
by is an update to U, then update sky, + sky + Say for all E [k], otherwise update skf, + skj, + S
Query.
Sample with replacement = Ō(1 indices from [k)) let ji....,j is denote the sampled indices;
Compute F5, = arg minzerd |/sk skilla for all i [s];
Compute PMEDIAN(ES,))........ (x;,, with privacy budget EDP (Theorem D.5) for all | E [d];
Output (g1, 02, .... 9a).
We now prove the privacy and utility of our algorithm.
Lemma D.7. The algorithm ADAPTIVEREGDP satisfies (s, -)differrnnti privacy w.r.. the collection of random strings R. for E = 1/100 and 8 3/100.
Proof. By Theorem D.5, each instance of primed is (EDP, -)diifferential private. But since we sample = Ö(1) copies of the oblivious algorithm to use, this amplifies the privacy of each PMEDIAN call to sD,, 0)-DP by Theorem B.3. In total, we have at most d T instances of PMEDIAN.
By the advanced composition theorem, the entire algorithm is (s, didfferrrel private for
6s (2Tdl1(100/3))
6s ( EDP) 2Td- EDP)² < 1/100 k
and 100/3, since we set K 200 6S8DP 2Td1n(100/3).
In the following discussion, we follow previous work (Hassidim et al., 2022) and assume the returned solution vectors to the regressions have their coordinates in the range [-n", 11/n"] U {0) U (1/n",,
28

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Lemma D.8. With probability at least in all rounds
[T] during the update sequence, The algorithm ADAP-
TIVEREGDP outputs g that satisfies
1 - ball2 S (1+ a) min
|Ua - bell2.
2ER"
for underlying design matrix U2 and vector by
Proof. Consider any round [I'] during the stream, let (U,, b.) be the underlying vectors defined by the stream up to round f. And let min denote the minimum singular value of U2 and max denote the maximum. Let fu (r) be the indicator for the following event:
a' Vd
|| - xello0 S
|10x00 - be mmin
(i..., Equation (2))
x² == arg min 10a0 -
bell2
2E3
21 = arg min ze
|S(Urz be)ll2 where S is generated Lemma D.6, using random string
For 1/100 and 3/100,, observe that >> _tz log( 25). Thus, we can apply Theorem B.4 with to show that
E Elfu,,.. (r)
Σ (ry)l & 10c = 1/10.
with probability at least 8/8 = 1 B. In the following, we condition on the event that this holds.
We have E. [fu, by (r)) 2 9/10 by the (a', Jaccuurcyyyyy of each copy of sketch. Therefore, at least 4s/5 of the samples {zy, : : [s]} satisfies ||x= Iy, ol I L UU'" bell2 1. We call such I,, a "good approximation".
The algorithm runs PMEDIAN each coordinate [d] across all approximated vectors Z "2zz , For each I E [d]. Theorem D.5 combined with our choice of 100r guarantees that with probability at least 1 (/(dd), we have
Hi E [s] (z))) 2 (o) 2 4s/10 and Ki E [s] (1g)) S (g):) 2 4s/10.
Since there least 4s/5 good approximations satisfying Equation (2), this means there exist good approximations
Tig Ri such that (g), E [(x,,); ): ). thus [(g); - (xx)xl v 5 |1,x b,l12 Omin This holds simultaneously for all I [d] and all & independent copies with probability at least 8.
Condition on the above event, we have
U0a bell2 S |Ua bell2 + [[u( - x²' )||2
$ |Uax * bell2 + mmax 11 z²1/2
|Ux bell2 mmax (vd. 11ğ (1o0)
max (vd a'
UU bell2
Vd |1 - bell2)
Jmin
(1 Tmax a (')lU belle-
Umin
By setting a' 2 this gives a (1 +1+ approxxxiatni.n. Overall, with probability at least 3, all the approximation vectors are accurate to within a multiplicative error of (1 a).
x
remains show that ADAPTIVEREGDPis both time- and space-efficient.
Theorem D.9. Given a sequence of T adaptive updates {U1....,oy, vr algorithm ADAPTIVEREGDP has the following specifications:
29

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
It preprocesses (U,b) time O(yTd. (Inz(U) + mnz(b) + d + dd2n2/a2)),
It uses space OVVT d2.5x2 /aa));
Given an update v, for t E (T], it takes time Ö(VTd. (unz(vr) + d + dd22/a2)) to update;
It output (1 appproximmat solution 2, in time (dd n² /²//2²)
Proof. We prove the theorem item by item.
Preprocessing time. During preprocessing, we prepare k: = ((VT(())) independent copies of sketching matrices due to Lemma D.6 and compute S,U, S,b for all i E [k]. Note that S; is a composition of a Count Sketch matrix and an SRHT matrix, so S.U takes time (Un)(()) for the Count Sketch, and this results in matrix of size m x d, applying SRHT to this matrix takes time (mm)) = O(d + d2x²/a²) Hence, the overall time for preprocessing is
Ö(VTd. (nnz(U) nnz(b) d /ox))
Space usage. The algorithm stores R and sky, skğ for all E [k]. We start by considering the random strings to generate k pairs of SRHT and Count Sketch matrices. To store the pairwise and 4-wise independent hash functions for Count Sketch, we only need (1) bits of space. To store an X SRHT matrix SSKHT = vi. PHD, since H is deterministic, we only consider P E R and E Rmxm, P contains exactly one each row (and contains 0 everywhere else), thus can be stored Or log m) bits of space. a diagonal matrix containing {-1,1}, which can be stored in ((m) bits of space.
Therefore, R in total takes
dloog 3 a2
dn.² poly log
0
log + dl xx2) 0 0(
+ +d²
a
bits of space.
For ský, skj for i [k:), the total bits of space is
T {
1)
dR² log" n a²
O(k .log n) Opooly logn log( 3
Tdlog(
(
d dooggn
= =0 =0 x2
poly (n, L, 1/3))
a²
assuming a word size of Ologgn bits. This is also asymptotically the total space usage.
Update time. For update, we simply apply the sketch S; to the update for all E [K)]. hence the total update time is Ö(VTd. (unz(v.) d + d2 /a²)).
Query time. To answer the query, we need to solve a sketched regression for instances, where each regression could be solved in time ((rd~11) = 0(d=t1x//a")) The private median is then performed over numbers, and each private median runs in time Öss). Repeating this procedure for all d coordinates, the overall time for forming g is then Ö(d). Hence, the query time is
1 222
D.3. Improved Algorithm with Bounded Computation Path Technique
When the condition number is as large as poly n, a quadratic dependence on is prohibitive. We provide an algorithm for such case based on the bounded computation path technique (Hassidim et al., 2022). Let P denote the set of all possible computation paths given the adaptive update sequence {"I,.... VT). The intuition is that the total number of possible computation paths (P| is at most n O(dT), hence we could prepare a large Gaussian sketching matrix with size roughly log [P), that is guaranteed to succeed against all such paths. In the case where the updates are stable, e.g., when the updates are always concentrated in a few coordinates, then [P] could be much smaller than n 9(T), This leads to a more efficient alternative and a better dependence on the condition number K. We will refer this algorithm as ADAPTIVEREGPA
30

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Initialization.
(Parameters for rounding): Let P the set of all possible output sequences of the algorithm and let (3 3/(CC, (P)) for large constant C:
(Parameters for sketches): Let log(/) generate the Gaussian sketching matrix S E R by a length-O(r) bits random seed
Let SU and sk,- Sb.
Update.
Receive update b45
Compute So, using ro and Lemma D.13, if oy is an update to U then sky <- sky + Suz, otherwise sky, +- skb + Su..
Query.
Compute arg min ||sky, skk, l12;
Round 2; the nearest point in any sequence in P, denote by g:
Output g.
We start by showing the utility guarantee of ADAPTIVEREGPATH when the updates are oblivious.
Claim D.10. If the update sequence is oblivious, at each round t. E (7). ADAPTIVEREGPATH outputs a vector that satisfies
||Ugg bell2 S a1+ min ||U,æ bell2 3E3d
for underlying input matrix Ug and vector by, with probability at least 1 - Bo-
This follows from our setting of r = O((d + log(1/3)))/a²)) which is sufficient for the distribution of Gaussian matrices be an (a: OS)-OSE (Woodruff, 2014).
Lemma D.11. The Gaussian sketching matrix ADPATIVEREGPATII can be pseudo-rundomly generated using a random seed of length Ö(d + log(1/3))/a²) bits, while still satisfying Claim D.10.
Proof Sketch. This can be seen by opening up the proof e.g., in Section 2.1 of (Woodruff, 2014) that the Gaussian distribution satisfies OSE The i.i.d. property is used for showing that the random Gaussian matrix is JL transform (Lemma 2. 2.12 in (Williams, 2012)). However, there needs to consider at most (log(9 (3)) //6)//² /ttppe of Gaussian variables, where 9d is the size of the 1/2-net for unit sphere in the subspace that we hope to embed in. Therefore the proof goes through as long as the entries of S are generated using at least = O(d log(1/Po)/a² - independence. It is well known that such w-wi independent hash function can be compressed length - seed, which concludes the proof.
Lemma D.12. With probability least in all rounds i. [T], ADAPTIVERFGPPAT given adaptive update us outputs vector g that satisfies:
|U.g - ba1l2 S (1 + a) min
|Ua - ball2,
2ERd
for underlying input matrix U2 and vector b,.
Proof. As argued in (Ben-Eliezer et al., 2020), we may assume the adversary to be deterministic. This means, in particular, that the output sequence we provide to the adversary fully determines its stream of updates U1, U2, Pr. Note that the collection of all distinct output sequence after the rounding step is at most [P]. Each output sequence as above uniquely determines corresponding stream of updates for the deterministic adversary. For every stream, with probability least
31

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
1 Sy. ADAPTIVEREGPATH will be correct in every round. Applying the union bound these streams, can conclude that with probability at least 1 O(PP)) fo 1 3, it outputs a (1 apprrooxxxiiio in every round against any adversary.
Lemma D.13. The time to generate S via rG is Ö(r)..
Proof Sketch. Note that to generate one column S, of the sketching matrix, we need r evaluations of the r-wise independent hash function. Using fast multipoint evaluation of polynomials (Gathen Gerhard, 2013), these evaluations can be done in ((r) time. Hence, generating S takes ((rn) time, as desired.
Theorem D.14. Given sequence Tf adaptive updates {01,... ,r), algorithm ADAPTIVEREGPATE has the following specifications:
It preprocesses (U.b) time Ö(nd" 2(d log Pl + log ))/a²)
It uses space (dd(d log [P] + log ))²;))
Given an update u, for E [T], it takes time Ö(d + log [P| + log /)/ to update;
It oututs (1 + appproxmmmmt solution 2, in time ( (d + log pP| log /)/
Here 3 denotes the failure probability.
Proof. We prove the theorem item by item. The parameter r is expanded as + log [P] + log 3
1 to obtain the theorem.
Preprocessing time. During preprocessing, we generate the sketching matrix S using our random seed, which by Lemma takes Ö(rn) time. Afterward, computing the sketches is dominated by computing the matrix product of r-by-n matrix S and n-by-d matrix U, which is O(rdd==))
Space usage. The sketches sky and sky, together take Ö(dr) bits of space, and the random seed takes Ö(r) bits of space.
Update time. We first generate one column of the sketching matrix, which takes Ö(r) time. Then we compute the inner product between this column and the update, which takes at most Ö(r) time.
Query time. To answer the query, we solve a sketched regression instance in time Ö(rd-=1). After that, we round it to the nearest point in P, which can be done in Ö(log (Pl) time using binary search.
D.4. Handling Sparse Label Shifts with Preconditioner
In machine learning, it is common that the design or data matrix remains unchanged. it might be generated via embedding raw data into high dimensional vectors, and these embeddings are expensive to compute. The response or label vector, in contrary, might constantly drift. Hence (Cherapanamjeri et al., 2023) studies model where only receives a sparse update 2 with |læyllo S s. For example, could be the count of a large class of images, and only a few popular classes get their counts incremented frequently. In (Cherapanamjeri et al., 2023), they are only able to output regression cost against sparse, adaptive updates Here, we develop an algorithm based on ADAPTIVEREGDP to output the solution vector. We will use ADAPIIVER:CPRECONDTTTTTT to denote this algorithm.
Initialization.
(Parameters for sketches): Let a' a and 8 = 0.01, set do (on/8")(n/8)) and m O a a2
(Parameters for privacy): Let I O 1
log
X B
where X = {-12, ...., - 7, 7,0, x, ",....,??? n2 set
Epp
O P. /Tdlog(///
32

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
(Parameters for batch size): Let 7' be parameter denote the batch size depending on nnz(U), d and a. Let counter be the batch counter parameter.
Prepare independent copies Si...., Sk R according to Lemma D.6;
Compute preconditioner P IRdxd such m(AP) O(1);
Prepare M, (S,UP)1S, and = Mib for all
[k].
Update.
If counter T, regenerate sketching matrices ,,, Sk R set M, (S,UP) and sk' M, for all E [R:]. Reset the counter = 1;
Receive update Uz;
Update b +- b + es and sk' + sk* + M, for all i [k].
Query.
Sample with replacement = (() indices from [kc], let J1.... .e denote the sampled indices; Compute = PMEDIAN((sk") )i,..... ((sk²))) with privacy budget EDP (Theorem D.5) for all / E [d];
Let g = (g1. 92. ga), output Pg.
We note that the privacy and utility guarantee remains the same as ADAPTIVEREGDP, so we focus on the complexity. Instead of fixing the length of update sequence in advance, allow for arbitrary length of update sequence, and we will restart the data structure every T updates.
Theorem D.15. Given a sequence of adaptive updates {U1, U2, ... b, algorithm A has the following specifications:
It has amortized update time Ö d/yd/T- (nnz(U) (b)(b) d + do /a²) VTd (s + d & /2/2)))
It outputs a (1 + cap-roxxxie solution D4 in time (dd)).
Proof. We analyze over batches. At the start of each batch, we generate k sketching matrices and S.U for all E [k]] this step takes Ö(vTu (nnz(U) d dd/a²)) time. Right multiplying by P then computing the pseudoinverse takes Ö(VTd- d= /a²) time. Finally, note that don't need to right multiply by S. rather we could first compute S,b in nnz(b) + d + d/a² time, then multiplying the matrix with the vector in Ó( rd) = Ö(VTd d2 d2/a²) time. Hence, the amortized time for this process over steps is
Ō((Vd- (nnz(U) + nnn(b)) + 83.5 + d=+0.3 (e+t0s/a²)) //3)/
When receiving vs it takes time to update the response vector, and d3 + de a time to update sk' Hence, the overall time is
Õ(VT (sdu.5 + 3.5 + 2 2225/2²))
Now, to output query, we simply compute private median over sampled solution vectors in d coordinates, and output Pi in d² time.
In the next few paragraphs, we will explain how to make choice for
For the case when nnz(U) terms are small, and the ideal w the right choice of T O(1).
For the case when nnz(U) terms small, and
the current omega, the right choice is T= O(d--2)
For the case when mnz(U) terms are large, then we just need to balance vddnz(U))// with (d3.5 + cB.5 (..5/02)) /o2) VoT which mnz(U))
means need chose T O( ( (244"
33

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
To obtain the optimal choice for the batch size T, case on nnz(U). Let C' be some constant.
Claim D.16. If uuz(U) Σ C. (d + dth /a²). then let T be O((d + d /s)) the update time of the algorithm is O(ys- (& + d0/2200 /a))- Claim D.17. If nnz(U) C. (d + /o2),, then let T be ((nnz(U))s) the update time of the algorithm is O(v d- (U)s)
E. Improved Algorithm Against Adversarial Attack for Hamming Space LSH
In recent work, (Kapralov et al., 2024) shows that for Hamming space. there exists query efficient algorithm that can quickly compute point adaptively, such that there exists E U such that I|u øll S r (here || is the Hamming distance) but the data structure returns nothing. We state their result here.
Definition E.1. Let U C I be an n-point dataset, we say point z E is an isolated point for all points u E U with u * 2, || - 2|| 2 2cr. Here || || is the Hamming distance.
Theorem E.2 ((Kapralov al., 2024)). Let n denote the size of dataset, the dimension, (c,r) r) be the parameters for ANN, A be complexity parameter. Suppose they satisfy the following relations:
S d;
In'n S d/ Inn;
A S min( Inn
r n//8
c 1+ In
mn
Then with probability at least 1/4 - 1/n, there exists an algorithm that finds point q such that an isolated point in the dataset is at most r away from q, but the algorithm returns nothing. The algorithm makes (llog(rr) X) queries to the LSH.
In their original theorem statement, they also require S In n. This is unnecessary, as is derived using the upper bound S d/ and or I If much smaller, then e can be larger. Their algorithm starts from the isolated point 2, then gradually moves away from while ensuring no other points could collide with it. In the end, it moves most r-away from 2, but with high probability, point in U has been hashed to the same bucket as it.
To combat such an adversarial attack, one could either repeat the data structures d times or T times, which are both relatively inefficient. We will show that whenever the dimension d is relatively small, then we could use Theorem 1.6 with /T data structures, against the attack of (Kapralov et al., 2024).
Lemma E.3. Let n, d be positive integers and c 2 1 and r > 0 be parameters. Let p E (0, 1) be a parameter. If = s 2cr' then Assumption 1.3 holds for any n-point set C (0, In particular, if S n then Assumption 1.3
and a S 1. holds for all nP.
Proof. We note that Assumption 1.3 could be rephrased as for each U, it can have 2cr-near neighbors. In the Hamming space, it means that they could differ by most 2cr bits. Fix vector The total number of points that differ by at most 2cr bits from is at most
2 Σ 1=1
d
< 2cr
2cr
< (d e)2or
(2er)
(3d) 2cr
as long as 2cr log, (3d) < 1, we are guaranteed the total number of possible near neighbors is at most s. By a simple calculation, this also gives the bound when s I n?.
For Hamming space LSH, known that = O(1cc,, and thus the bound on d becomes d s n (()((er))) In order for to be useful against Theorem E.2, we could let r = In n and = + o(1). Thus the bound on d becomes I exp(-0((lo) n)) (1) We obtain a corollary against Theorem E.2 this setting.
34

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Corollary E.4. Ifd n1(1) and with the parameters in Theorem E.2, there exists an adaptive LSH data structure for Hamming space with
Preprocessing time Ö(VT (
Space usage Ö(VT n2+0(p) + nd);
For all t E [ with high probability, if B( r) n + then it returns a point in ((u,, Nu in time (() d). Here B(.,)) is the Hamming ball.
In particular, to be robust against the attack of Theorem E.2, it suffices to pick = (log(er)) X).
The above corollary essentially asserts that, to be robust against the attack of (Kapralov et al., 2024), it is sufficient to blow up the number of data structures by Vlog(er) À factor, even in the presence of an isolated point.
F. Locating the Thin Level via Approximate Counting
If one considers Assumption 1.2 for (c, r)-ANN, it states that for an adaptive query v, if ((,, r) nu * 0 then [Bu,, cr) n. U| S s. In an iterative process, one usually does not care for a particular r but only wants to find an approximate nearest neighbor, and this is often achieved via binary search over the choice of r. We also note that since our assumption is strictly weaker than constant expansion and doubling dimension, holds for query and it no longer holds for 2r. In fact, even if (v,, cr) nV is small, (B( 2cr) n U| could be the entirety of U if the diameter of U is between and 2cr. Thus, in order to deploy our data structure, it is erucial that have the ability to identify the thin level, i.e., given v, the largest possible for which the assumption holds. Recall that due to efficiency concerns and the nature of LSH data structures, we set S n².
completely possible that for some small r, Assumption 1.2
To do so, we will utilize an approximate near neighbor counting procedure for le norm, developed in (Andoni et al., 2023). In essence, they develop an algorithm based on the LSH scheme of (Andoni et al., 2017) that, given an oblivious query v, it can with high probability return an approximate count ans such that
- (()) ( UI S < (B) ((n
We first note this provides a tool for us to do binary search on r, to locate the thin level: we could start with small r, and run the approximate counting procedure of (Andoni et al., 2023). Conditioned on these counts being accurate, whenever we are still below or at the thin level, ans must be below O(n(+o())) ). If we are at a level where [B(,, r) n nU| 2 (() then the counting data structure could successfully detect it, so the only troublesome case is when (B(,,)) n Ul small but [B,, cr) U 2 (n) We can indeed detect this case by searching over the range (er, c²r). and the data structure should indeed report that the count is already too large. We could then refine our search by looking at the range (r/c, r), in which the correct thin level is guaranteed to be in this interval.
One last issue remains: the (Andoni et al., 2023) data structure only works for oblivious queries; for adaptive queries, they run a net argument with d independent copies. To improve upon that, we note that the data structure only outputs a real number, and thus falls into the category of estimation data structures, which can be augmented via the framework of (Beimel et al., 2022).
Theorem F. (Adaptive Approximate Near Neighbor Counting). Let U S IRdd be an n-point dataset and {ui,..., vT Rd be a sequence of adaptive queries. Let e > 1, r 2 0 be parameters and p E (0, 1) be a parameter that depends e, There exists randomized data structure with
Preprocessing time Ö(VT. -n++0()))))
Spuce usage Ö(VT n=+oo(),d);
Given Ut, oulputs number ans such that
(1)) lla (vr, r) nu ans S B.01|BB-jg (v,, cr) cU) (neto((1)
holds with probability at least 1 1/ (n)y(n). The time to output ans is ((n++o(1)d)
35

---

On Differential Privacy for Adaptively Solving Search Problems via Sketching
Proof. The proof is combination of the data structure of (Andoni al., 2023) and augmentation of (Beimel et al., 2022). We start from the oblivious data structure. In the proof of Lemma 3.3 from (Andoni al., 2023), note that their argument is to first provide bound the noiseless count, and then bound the error incurred by Laplacian noise. The noiseless count ans indeed has bound
(1 (1-o(1))
|H (v,, nu] S ans [B|-l|a (v,, er) n U] + ((nto(())
with high probability, albeit for oblivious ty. To augment it for adaptive ad adversary, we apply Theorem 3.1 of (Beimel et al., 2022), which states one could use vT copies of the data structure when the output is real number. Regarding the output quality, only the upper bound is increased by a factor of 1 + a, we set a = 0.01, we obtain the desired result.
Given such an adaptive data structure for approximate near neighbor counting, we could then instantiate meta algorithm for f2 LSH under Assumption 1.2. Without loss of generality, assume U C s and all queries lie on the unit sphere. We first
[1
pick small discretization value and apply the transformation x +
all points in U and all queries. We
[ma/~]
U and V to denote transformed points. Note that these points have their entries being a multiple of r, and the difference of the norm ||ar - 2r|22 S /ni, if we choose T = n-C for a large enough constant C, then the difference is 1/ poly(n), which negligible. The advantage of this discretization framework that the difference of norms for points over the unit sphere could also be discretized into O(1/T) levels. Hence could perform binary search over these discrete (1/r)) levels in (log(1//)) O(log n) steps. We will prepare (1lg((1/)) data structures by initializing LSH for r = (c/2)'r where i E (0, ..... log(1/r) for 2 2. This ensures that for any in this form, there exists node in between r/c and c, as desired.
36


Reviews:
[{"review_id": "lqx3aWQnjm", "reviewer": "Reviewer_MeYi", "summary": "The paper explores using differential privacy for answering adaptively chosen queries (potentially by and adversary) for search problems. The authors consider approximate nearest neighbor and regression as the main problems in this work. The main contributions are showing that under reasonable assumptions, it is possible to maintain $O(\\sqrt{T})$ copies of data structure to answer $T$ queries for both problems, matching the bounds from previous work that uses DP for adversarial streaming. For the ANN problem, they reduce the problem to private selection and provide a new mechanism that obtains better runtime for sparse vectors. For regression problem with updates to both design matrix and response vector, the approach involves maintaining and updating multiple sketch matrices, solving to generate multiple solution vectors and using DP median to generate the final solution. The authors also show application to online weighted matching and computing terminal embeddings.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your very helpful comments and we would like to address your comments on the quadratic dependence on $\\kappa$ and linear dependence on $T$ for the alternative.\n\nFor the $\\kappa^2$ dependence, the main reason is that by using the $\\ell_\\infty$ guarantee together with the standard relative error guarantee of sketched regression, we can show that the regression cost of the private median estimator $g$ satisfies $\\\\|Ug-b\\\\|_2 \\leq (1+\\kappa \\alpha’)\\\\|Ux^*-b\\\\|_2$. Hence, to account for the blowup in condition number, we need to scale down the approximation factor by $\\kappa$. Since the sketching dimension depends inverse quadratically on the approximation factor, we have a $\\kappa^2$ dependence in the runtime. One could argue that known sketching-based methods based on the following framework need to incur such a dependence: our algorithm estimates each coordinate to high precision, and this inevitably incurs a dependence on the condition number for the error, and the sketching dimension in turn depends quadratically on the condition number. When there are no updates to $U$, we could use an iterative method instead to remove the polynomial condition number dependence. It is an interesting open question to develop an iterative algorithm that can remove the dependence on the condition number while also supporting updates to $U$. Therefore, while the $\\kappa^2$ dependence is a consequence of our current sketching approach for worst-case guarantees, we believe the overall framework offers significant advantages, and reducing this dependence under updates is an important avenue for future work.\n\nThe alternative method based on the bounded path technique can be treated as a refinement to the method of using a fresh sketch for each update and query. Specifically, the algorithm depends on $\\log |{\\cal P}|$, and $|{\\cal P}|$ can be naively upper bounded by $(n\\kappa)^{dT}$, making it less appealing. However, we note that $|{\\cal P}|$ is a more fine-grained parameter that could capture the structure of the input, e.g., if only entry changes between queries are allowed, then the upper bound reduces to $(nd)^T$. If the updates are infrequent, e.g., only $\\sqrt T$ updates are performed, then the bound becomes $(nd)^{\\sqrt T}$. Hence, while the alternative is no more efficient in the most general sense, it provides more fine-grained control and a speedup in situations for which the instance has extra structure.", "claims_and_evidence": "All the claims made in paper are accompanied with proofs. Reasoning and justification for the assumptions made are also provided.", "methods_and_evaluation_criteria": "The paper does not have experiments.", "theoretical_claims": "The proofs are correct to the best of my knowledge. The contributions sublinear dependence on $T$ for time/space complexity in answering queries. The baseline comparison are the naive or existing bounds of $O(T)$ and $O(dim)$. \nThe accuracy guarantees follow from success probability for the data structure or the generalization guarantee for DP algorithms.", "experimental_designs_or_analyses": "This is a theoretical work, no experiments are provided.", "relation_to_broader_scientific_literature": "This work contributes line of prior work that explores connection between differential privacy and robustness to adaptivity.\nThe paper makes novel contribution in this field by giving approaches that work for search problems.", "essential_references_not_discussed": "Not to the extent of my knowledge.", "other_strengths_and_weaknesses": "The sparse argmax mechanism is a nice contribution and might be of interest to broader DP community. For regression problem, the dependence on $\\kappa$ is quadratic which might be suboptimal -- in addition the alternative approach suggested obtains linear in $T$.", "other_comments_or_suggestions": "No additional comments.", "questions_for_authors": "No additional questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tsKXTULnc3", "reviewer": "Reviewer_Qdd6", "summary": "The paper studies the problem of adaptive algorithms: the algorithms where the adversary interacts with a randomized algorithm and the goal of the adversary is to increase the error probability.\n\nIt is known that differential privacy could be used to design such algorithms, but the existing applications were for algorithms computing numeric results; this paper generalizes the approach to vector-valued algorithms. As a result, it builds an algorithm for the nearest neighbor problem with better than previously known running and preprocessing time.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your encouraging and helpful comments. Regarding your comments:\n\n- **Line 40:**  \n  We will clarify this sentence. Our intention is to express both ANN and regression in a unified way, and we will revise it to clearly explain the query and update models in each problem.\n\n- **Line 94:**  \n  The assumption states that the predicate function $f_{v_t}$ is sparse, and we define the predicate as the intersection of the dataset $U$ and the $cr$-ball around $v_t$—that is, all points in $U$ within distance $cr$ of the query. We acknowledge that the current formulation does not make this connection explicit and will revise it for clarity.\n\n- **Line 258:**  \n  We will fix the missing index $j$.", "claims_and_evidence": "The evidence sufficiently supports the claims.", "methods_and_evaluation_criteria": "Methods and evaluations are appropriate for the problem at hand.", "theoretical_claims": "The proofs presented in the paper are correct.", "experimental_designs_or_analyses": "There are no experiments in the paper.", "relation_to_broader_scientific_literature": "For me, personally, the idea of using differential privacy for designing adaptive algorithms is one of the most exciting ideas in the last couple of years: it connects the fields that from the first glance have almost nothing in common. \nWhile this is not the first paper in this direction, it generalizes the idea to a much wider class of problems.", "essential_references_not_discussed": "I don’t think any specific reference is missing.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "Line 40: It would be better to rephrase the sentence about queries; it is a bit confusing in the current form.\nLine 94: The assumption doesn’t say anything about neighbours, it only talks about cr balls. Perhaps the explanation needs to be rewritten.\nLine 258: It should be argmax \\sum b_{(i), j}; the j index is missing in the paper.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pBL1H7a6sv", "reviewer": "Reviewer_EdyH", "summary": "The paper addresses the problem of hiding internal randomness of data structures using differential privacy. Specifically, the authors focus on nearest neighbor search and regression problem and aim to protect the internal randomness against adaptive adversary using differentially private techniques.\n\n## Update after rebuttal\nThe author response provided during the rebuttal clearly addressed my questions regarding the interaction between the privacy mechanism and the underlying data structure, and the privacy loss accumulation. I have raised my rating.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your very helpful comments. We would also like to address your questions and comments regarding differential privacy.\n\nLet us start with a high-level overview of the framework, first introduced in [Hassidim et al., 2022; Beimel et al., 2022]. The rough idea is to treat the random seeds used by data structures as the database for which we want to preserve privacy. In the simplest setting, to achieve a target privacy level $\\epsilon$, one might need to aggregate the responses of $T$ data structures in a differentially private manner. However, by the **advanced composition theorem**, the same level of privacy in terms of $\\epsilon$ can be achieved using only $\\widetilde{O}(\\sqrt{T})$ independent outputs—at the cost of moving from pure DP to approximate DP with $\\delta > 0$. As long as $\\delta$ is small, the approximation is acceptable.\n\n### Responses to Specific Questions\n\n> **Q: Can the Gaussian mechanism be used for $(\\epsilon, \\delta)$-DP? In that case, how does it affect the final guarantees?**\n\n**A:** Yes, the Gaussian mechanism is valid for achieving $(\\epsilon, \\delta)$-DP, provided that $\\delta$ is not too large. Suppose we want the data structure to succeed with probability at least $1 - \\beta$. Let $\\delta_{\\text{final}}$ denote the total privacy loss, composed of:\n\n- $\\delta_{\\text{Gaussian}}$: from the Gaussian mechanism  \n- $\\delta_{\\text{advanced}}$: from advanced composition\n\nThen:  \n$$\n\\delta_{\\text{final}} = \\delta_{\\text{advanced}} + T \\cdot \\delta_{\\text{Gaussian}}.\n$$\n\nIn our original setting, we set $\\delta_{\\text{advanced}} = \\beta / 100$ using an appropriate $\\epsilon$. To use the Gaussian mechanism instead, we may set $\\delta_{\\text{Gaussian}} = \\frac{\\beta}{200T}$ and reduce $\\delta_{\\text{advanced}}$ to $\\beta/200$. This still yields $\\delta_{\\text{final}} = \\beta / 100$, matching the Laplace mechanism’s privacy loss.\n\nWe chose the Laplace mechanism for conceptual simplicity and because the task is essentially a counting problem, where Laplace noise is more natural.\n\n> **Q: In DP, privacy loss accumulates with repeated queries, so mechanisms are often shut down after a limit. Does your adaptive data structure exhibit this behavior?**\n\n**A:** Yes, the adaptive data structure’s ability to handle $T$ queries hinges on **privacy composition**. Using the advanced composition theorem, we guarantee $(\\epsilon, \\delta)$-DP across $T$ interactions by using $\\widetilde{O}(T)$ resources (e.g., data structure copies or random seeds), rather than $O(T)$.\n\nHowever, this requires $T$ to be fixed in advance. For indefinite querying, a standard approach is to **rebuild the data structure periodically after every $T$ queries**. This permits optimization of $T$ to balance space, amortized preprocessing time, and query/update efficiency.\n\n### Additional Comments\n\n> **It would be better to discuss more on differential privacy, such as composition and loss accumulation.**\n\n**A:** Thank you for pointing this out. We will ensure that the final version includes a more detailed discussion on differential privacy, particularly covering composition theorems and cumulative privacy loss (please refer to our high-level overview and answers regarding loss accumulation above).\n\n> **Including figures and diagrams would be helpful for explaining the techniques.**\n\n**A:** We appreciate the suggestion. We agree that visualizations—especially for illustrating how the sparse argmax mechanism is applied in our ANN algorithm—would enhance clarity and intuitively explain why our algorithm is both correct and efficient. We will include appropriate figures and diagrams to better illustrate the framework in the revision.", "claims_and_evidence": "A sequence of theorems presented in Section 1.1 clearly demonstrates improvements over existing algorithms. They provide probabilistic utility guarantees as well as time and memory complexity, but it is not immediately clear how differential privacy interacts with these bounds. While I understand that characterizing the interplay between data structure and differential privacy is not the main focus, it could be of interest to a broader audience.", "methods_and_evaluation_criteria": "* Section 2 provides explanation on how the search problem can be formulated as differentially private selection, which completely makes sense. The authors use the standard Laplace mechanism to achieve pure $(\\epsilon, 0)$-DP. I wonder if the Gaussian mechanism can be used instead to achieve $(\\epsilon, \\delta)$-DP. In that case, how does it affect the guarantees stated in theorems in Section 1?\n\n* Another aspect not discussed in the paper is the accumulation of privacy loss. In differential\nprivacy, the total privacy loss accumulates as the mechanism releases private answers to successive\nqueries, which means the mechanism must shut down the database and stop answering after a\ncertain number of queries. However, it is unclear from the paper whether there is a limit to the\nnumber of queries the underlying data structure can handle.", "theoretical_claims": "I didn’t thoroughly check the correctness of the proofs.", "experimental_designs_or_analyses": "This is a theory paper that doesn't contain experimental results.", "relation_to_broader_scientific_literature": "This paper develops efficient data structures that protect their internal randomness from adaptive\nadversaries, offering a secure and private foundation for machine learning tasks.", "essential_references_not_discussed": "I don't find any missing related work.", "other_strengths_and_weaknesses": "* Strength\n  - The paper presents a sequence of theorems that describe improvements over existing results.\n  - The authors provide interpretations of theorems.\n* Weakness\n  - This may not be a weakness, but rather a comment. While the paper is clear about the algorithmic properties of underlying data structures, e.g., how its time and storage complexities scale with input size, they don’t reveal much about the properties of differential privacy, such as composition and privacy loss accumulation.\n  - I believe that including some figures or diagrams would have been helpful for better understanding the proposed technique.", "other_comments_or_suggestions": "None", "questions_for_authors": "See above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KLGPumsCyV", "reviewer": "Reviewer_vS4r", "summary": "First the authors consider the differentially private ANN problem. They reduce this problem of differentially private ANN to differentially private selection problem, and then solve the differentially private selection problem via differentialy private selection methods.  Next, the authors consider the problem of differentially private linear regression. They solve this problem by applying matrix sketching techniques.  The key idea is to use standard a number of different random matrix sketches, and then to aggregate the solutions in a differentially private manner via an extension of a differentially private median approach of (Beimel et all 2022).  Finally, to bound the utility they use they compute an ell-infinity bound on the error introduced by sketching.  As the authors note, this is an interesting approach to bounding the utility as it is an uncommon use of ell-infinity bounds in matrix sketching.\n\n## update after rebuttal\n\nThank you for the helpful clarifications. I have raised my score accordingly. Please include these clarifications in the final version.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their question about prior work, which we address below:\n\n1) Prior works using differential privacy for adaptivity focus on numerical estimates [Hassidim et al., 2022; Beimel et al., 2022; Song et al., 2023; Cherapanamjeri et al., 2023]. Our work instead tackles the *search* problem—returning a point using an adaptive DP data structure. While differentially private heavy hitter algorithms (e.g., [Chadha et al., 2023]) relate to private search, they lack adaptivity. To our knowledge, this is the first work combining DP with adaptive search.\n\n2) Because of this, prior adaptive search methods either (a) build $T$ data structures (one per query), or (b) use a net argument over the space, requiring $\\widetilde{O}(d)$ structures.\n\nBelow we compare our method to these baselines for ANN and regression. We omit $\\widetilde{O}(\\cdot)$ for clarity.\n\n### **Approximate Nearest Neighbor (ANN)**\n\n| Method      | Space                        | Amortized Prep Time           | Query Time     | Update Time             |\n|-------------|------------------------------|-------------------------------|----------------|--------------------------|\n| $T$ copies  | $T n^{1+\\rho} + nd$          | $n^{1+\\rho} d$                | $n^\\rho d$     | $T n^\\rho d$            |\n| $d$ copies  | $n^{1+\\rho} d$               | $\\frac{d}{T} n^{1+\\rho} d$    | $n^\\rho d$     | $d n^\\rho d$            |\n| **Ours**    | $\\sqrt{T} s n^{1+\\rho} + nd$ | $\\frac{s}{\\sqrt{T}} n^{1+\\rho} d$ | $s n^\\rho d$ | $\\sqrt{T} s n^\\rho d$   |\n\nFor $T$ adaptive queries/updates, the exact method scans the dataset. If $T \\leq d$, we outperform $T$-copies when $s \\leq \\min\\\\{\\sqrt{T}, n\\\\}$; if $d \\leq T$, we outperform $d$-copies when $s \\leq \\min\\\\{\\frac{d}{\\sqrt{T}}, n\\\\}$.\n\n---\n\n### **Regression**\n\nLet $U \\in \\mathbb{R}^{n \\times d}$ and $b \\in \\mathbb{R}^n$, with goal to compute $x$ minimizing $\\\\|Ux - b\\\\|_2$ up to $(1+\\alpha)$. Each step updates $U$, $b$ via $v_t$; $\\kappa$ bounds $U$'s condition number.\n\n| Method      | Space                           | Amortized Prep Time                          | Query Time                     | Update Time                                     |\n|-------------|----------------------------------|----------------------------------------------|--------------------------------|--------------------------------------------------|\n| $T$ copies  | $\\frac{T d^2}{\\alpha^2}$         | $\\text{nnz}(U,b)+d^3+\\frac{d^2}{\\alpha^2}$   | $\\frac{d^{\\omega+1}}{\\alpha^2}$ | $T(\\text{nnz}(v_t)+d^3+\\frac{d^2}{\\alpha^2})$   |\n| $nd$ copies | $\\frac{n d^3}{\\alpha^2}$         | $\\frac{nd}{T}(\\text{nnz}(U, b)+d^3+\\frac{d^2}{\\alpha^2})$ | $\\frac{d^{\\omega+1}}{\\alpha^2}$            | $nd(\\text{nnz}(v_t)+d^3+\\frac{d^2}{\\alpha^2})$   |\n| **Ours**    | $\\frac{\\sqrt{T} d^{2.5} \\kappa^2}{\\alpha^2}$ | $\\sqrt{\\frac{d}{T}}(\\text{nnz}(U, b)+d^3+\\frac{d^2 \\kappa^2}{\\alpha^2})$ | $\\frac{d^{\\omega+1} \\kappa^2}{\\alpha^2}$ | $\\sqrt{T d}(\\text{nnz}(v_t)+d^3+\\frac{d^2 \\kappa^2}{\\alpha^2})$ |\n\nWe outperform $T$-copies when $\\kappa^2 \\leq \\sqrt{T/d}$, and $nd$-copies when $\\kappa^2 \\leq n \\sqrt{d/T}$—conditions often met in practice.\n\n---\n\n### **Regression with Sparse Label Updates**\n\nIf only $b$ is updated and each $v_t$ changes at most $s$ entries, $\\kappa^2$ dependence can be reduced to polylogarithmic.\n\n| Method      | Space                       | Amortized Prep Time                         | Query Time | Update Time                              |\n|-------------|-----------------------------|---------------------------------------------|------------|-------------------------------------------|\n| $T$ copies  | $\\frac{T d^2}{\\alpha^2}$    | $\\text{nnz}(U)+d^3+\\frac{d^2}{\\alpha^2}$    | $d^2$      | $T(s+d^3+\\frac{d^2}{\\alpha^2})$          |\n| $n$ copies  | $\\frac{n d^2}{\\alpha^2}$    | $\\frac{n}{T}(\\text{nnz}(U)+d^3+\\frac{d^2}{\\alpha^2})$ | $d^2$ | $n(s+d^3+\\frac{d^2}{\\alpha^2})$          |\n| **Ours**    | $\\frac{\\sqrt{T d} \\cdot d^2}{\\alpha^2}$ | $\\sqrt{\\frac{d}{T}}(\\text{nnz}(U)+d^3+\\frac{d^2}{\\alpha^2})$ | $d^2$ | $\\sqrt{T d}(s+d^3+\\frac{d^2}{\\alpha^2})$  |\n\nOnly $n$ copies are needed. Our method is faster when $T \\leq n$ and $d \\leq T$, or when $n \\leq T$ and $\\sqrt{T d} \\leq n$. Since $T$ is user-chosen (rebuilding occurs every $T$ queries), trade-offs can be tuned (see Claims D.16–D.17).\n\n---\n\n**Summary:**  \nOur method leverages DP with advanced composition, achieving $\\widetilde{O}(T)$ scaling and improved space, preprocessing, query, and update complexity. These advantages are especially notable when $T$ is large, or when sparsity $s$ and condition number $\\kappa$ are favorable. We will ensure these comparisons are clearly included in the revision.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I read the technical overview, but did not carefully check the proofs.", "experimental_designs_or_analyses": "There are no experiments in the paper.", "relation_to_broader_scientific_literature": "The authors do a good job of discussing which previous techniques they build on.\n\nHowever, as far as I can tell, the authors do not provide much comparison to prior related works.  It would be good if the authors could clarify how their work improves on prior works, or point to where the improvement over prior works is discussed in the paper.", "essential_references_not_discussed": "Please see \"Relation To Broader Scientific Literature\" question above.", "other_strengths_and_weaknesses": "I think the strength of the paper is in the techniques, which are well explained in the technical overview.  However, the comparison to prior works can be improved.  Specifically, it would be good if the authors could clarify how their work improves on prior works.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "It would be good if the authors could clarify how their work improves on prior works.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper extends the literature on using differential privacy as a tool to design randomized data structures that maintain their correctness properties against adaptive (rather than oblivious) adversaries. The main contribution is the development of techniques that allow solving search problems under adaptive queries, in particular approximate near neighbor search. The paper addresses important problems, and introduces interesting techniques. The reviewer consensus is that the paper would be a strong contribution to the ICML program.
Decision: Accept (oral)