REVIEW 3 major objections 4 minor 1 cited by
On Differential Privacy for Adaptively Solving Search Problems via Sketching
T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper claims that differential privacy can convert any oblivious nearest-neighbor data structure into one that withstands T adaptive queries using only $\widetilde{O}(\sqrt{T} s)$ copies, and can return regression solution vectors…
desk verdict First DP-based adaptive data structures that return solution vectors rather than costs; the ANN and small-kappa regression results look solid, but the large-kappa Theorem 1.10 has an unsupported update-time claim as written. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Two mechanisms carry the argument. For ANN, the paper makes the random strings of the oblivious structures the private database: each structure is asked to return all near neighbors it finds, producing a sparse binary count vector over dataset points; the sparse argmax mechanism adds exponential noise to the counts without touching the zero entries, using the largest order statistic of the exponential distribution and a biased coin flip, which provably matches dense noisy-max in $O(s \log n)$ time. For regression, the algorithm builds $k = \widetilde{O}(\sqrt{T} d)$ sketches that are compositions of a Count Sketch with an SRHT matrix, solves the sketched regression on a sampled few, and applies a coordinate-wise private median; the $\ell_\infty$ guarantee of these sketches is what turns coordinate-wise closeness into a $(1+\alpha)$ cost guarantee, scaled by the condition number.
What would settle it
Run the paper's adaptive ANN construction on a Hamming dataset of dimension $d = n^{0.1}$ against the isolated-point attack of [KMS24]; if the data structure returns a false negative with probability bounded away from 0 after $T = O(\log(cr) \cdot \lambda)$ queries, then the claimed $\sqrt{T} s$ copy bound would not hold in that regime.
Extended reading notes
Core claim
The central claim is that differentially private selection and aggregation reduce the overhead of adaptivity for search problems from $T$ copies of an oblivious data structure to roughly $\sqrt{T}$ times a parameter measuring the problem's local simplicity. Theorem 1.5 states that any oblivious $(c,r)$-ANN structure with preprocessing time $T_{\mathrm{prep}}$, space $S_{\mathrm{space}}$, and query time $T_{\mathrm{query}}$ can be made adaptive: for $T$ adaptive queries in which no query has more than $s$ points of $U$ within distance $cr$, the adaptive structure uses $\widetilde{O}(\sqrt{T} s)$ copies, preprocesses in $\widetilde{O}(\sqrt{T} s) \cdot T_{\mathrm{prep}}$ time, answers each query in $\widetilde{O}(s) \cdot T_{\mathrm{query}}$ time, and succeeds with probability $1-\delta$. Theorem 1.8 gives the analogous regression result under a bounded condition number $\kappa$: space $\widetilde{O}(\sqrt{T} d^{2.5} \kappa^2/\alpha^2)$, update time $\widetilde{O}(\sqrt{T} d (\mathrm{nnz}(v_t)+d^3+d^2 \kappa^2/\alpha^2))$, and query time $\widetilde{O}(d^{\omega+1} \kappa^2/\alpha^2)$ to output a $(1+\alpha)$-approximate solution vector. The paper also gives a bounded-computation-path variant with only polylogarithmic dependence on $\kappa$, and a preconditioned variant for sparse label shifts with $\widetilde{O}(d^2)$ query time.
Load-bearing premise
The load-bearing premise is that the input is locally simple: for ANN, every adaptive query has at most $s$ dataset points within distance $cr$; for regression, the condition number of the design matrix stays bounded by $\kappa$ through all updates.
Editorial extensions
If this is right
- For ANN with $s = \mathrm{polylog}\, n$, adaptive LSH can be built with $\sqrt{T} s$ copies, so when preprocessing dominates, the amortized preprocessing cost drops from $n^{1+\rho} d$ to roughly $(s/\sqrt{T}) n^{1+\rho} d$ per query.
- Hamming LSH with $d = n^{o(1)}$ becomes robust to the known isolated-point attack using a factor $\sqrt{\log(cr) \lambda}$ more copies, rather than $d$ or $T$ copies.
- For regression, the solution vector, not just the cost, can be maintained under adaptive turnstile updates in sublinear-in-$T$ space when the condition number is bounded.
- Sparse label shifts with a fixed design matrix can be handled with $\widetilde{O}(d^2)$ query time after preconditioning, removing the $\kappa^2$ factor.
- Online weighted matching and terminal embeddings inherit faster adaptive data structures, with deletions supported through batched fast rectangular matrix multiplication.
Reading between the lines
- The sparse-neighborhood assumption is the true price of the result: in dense datasets where $s$ approaches $n^\rho$, the construction degrades toward the trivial $T$-copy approach, so the practical win is concentrated in locally sparse or low-dimensional regimes.
- The two-stage 'privacy first, then utility' proof pattern suggests that any Monte Carlo search structure whose outputs can be encoded as sparse indicator vectors could be made adaptive at the same $\sqrt{T} s$ cost, not just ANN.
- The $\ell_\infty$ guarantee route for regression is arguably more broadly useful than the median step: any downstream algorithm that needs per-coordinate accuracy from a sketch could plug the same SRHT-plus-Count-Sketch composition in.
- One could test the sparse argmax mechanism on standard LSH libraries to see whether the $O(s \log n)$ noise-generation bound and the order-statistics equivalence hold in practice, and whether the privacy/utility tradeoff survives non-DP implementation artifacts.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper develops a differential-privacy-based reduction for turning oblivious search data structures into adaptive ones, and applies it to two search problems: approximate near neighbor (ANN) and least-squares regression under adaptive turnstile updates. For ANN, the main claim (Theorem 1.5) is that any oblivious ANN data structure can be converted into an adaptive one that answers T adaptive queries satisfying Assumption 1.2 using O~(sqrt(T)*s) copies, preprocessing in O~(sqrt(T)*s)*T_prep time, and answering each query in O~(s)*T_query time. The technical engine is a differentially private noisy-max selection over characteristic vectors of the sampled data structures, made efficient by a sparse argmax mechanism. For regression, Theorem 1.8 gives an algorithm for well-conditioned instances using coordinate-wise private median of sketched solutions and an l_infinity guarantee, with space O~(sqrt(T)*d^{2.5}*kappa^2/alpha^2). Theorem 1.10 claims a bounded-computation-path variant with only logarithmic dependence on kappa, and Theorem 1.9 handles sparse label shifts with a preconditioner. The paper also gives applications to online weighted matching, terminal embeddings, and robustness to the KMS24 Hamming-space attack, plus an adaptive approximate counting procedure for locating the thin level.
Significance. If the ANN and well-conditioned regression results are correct, this is a meaningful advance: it extends the BKM+22 private-median framework from scalar estimation to problems that return solution objects, with explicit dependence on the number of approximate near neighbors s or the condition number kappa. The paper is honest about the strong assumptions, and the main reduction uses standard DP composition and generalization theorems as black boxes rather than circular reasoning. The ANN reduction is modular and the small-kappa regression algorithm is plausible. However, the headline large-kappa result (Theorem 1.10) has an unsupported update time that is load-bearing for the paper's contribution in that regime, and the sparse argmax lemma that underpins the ANN query time is not proven cleanly. These issues need repair before the claims can be accepted.
major comments (3)
- [Section 8.3, Theorem 8.14 and Theorem 1.10] The claimed update time is not achieved by the algorithm as described. The Update step says to compute S v_t using r_G and Lemma 8.13, but Lemma 8.13 bounds only the time to generate the matrix S, namely O~(rn); it says nothing about applying S to an arbitrary vector v_t. For a turnstile update v_t with nnz(v_t) nonzeros, evaluating S v_t requires reading all nonzero entries and accumulating r-dimensional columns, which costs Omega(nnz(v_t)*r), and Omega(nr) when v_t is dense. Assumption 1.4 imposes no sparsity bound on updates. The proof of Theorem 8.14 states that 'we compute the inner product between this column and the update, which takes at most O~(r) time,' which confuses the length of a column of S (namely n) with the number of rows r. Since Theorem 1.10 is the main mechanism advertised for avoiding the kappa^2 dependence in adaptive regression, and the corresponding row in Table 2 rests on this update bound, this is a load-bearing gap. The algorithm needs either an explicitly stated sparsity assumption on updates, a stored S with an additional rn space charge, or a different input-sparsity sketching distribution that still supports the bounded-path union bound with r = O~((d+log|P|)/alpha^2).
- [Section 6.3, Lemma 6.14] The proof of the distributional equivalence between the dense exponential noisy-max mechanism and the sparse order-statistics simulation is not correct as written. In the first displayed formula for F_2, substituting g(x) = n F(x)^{n-1} f(x) together with the leading 1/n factor yields an integrand proportional to f(x) F(x)^{n-2} times a product of F(x_j)/F(x) terms, whereas the next line uses f(x) F(x)^{n-1}; the re-indexing from the x_i's to the sorted values x*_j also introduces factors (n-j+1) that are not justified by the displayed calculation. In addition, the description of A2 uses the symbol mu where the input vector u is meant, which makes the pseudocode hard to parse. Since this lemma is the only justification for the O(s log n) noise-generation time and hence for the eO(s)*T_query term in Theorem 1.5, the proof must be rewritten with correct normalizations and indexing, or replaced by a precise reference.
- [Section 8.3, Lemma 8.12 and Claim 8.10] The union bound over computation paths misses the number T of rounds. Claim 8.10 is phrased as a per-round guarantee: for an oblivious stream, 'at each round t ... with probability at least 1-beta_0.' If a fixed stream can fail in any of its T rounds, the per-stream failure probability is at most T*beta_0. Lemma 8.12 sets beta_0 = beta/(C*|P|) and then union-bounds over the |P| streams, which gives a failure probability of T*beta/C rather than beta. This is fixable by setting beta_0 = beta/(C*T*|P|), which only adds a log T factor absorbed by the O~ notation, but as written the probability bound in Theorem 8.14 and Theorem 1.10 is not derived.
minor comments (4)
- [Section 6.3, Lemma 6.14] In the description of A2, the symbol mu is used where the input vector u is meant; please fix the notation throughout the pseudocode and proof.
- [Section 1.1.1, Theorem 1.5] The predicate f_v is given the codomain (R^d)^s, but Assumption 1.2 and the surrounding text require f_v(U) to be a subset of the dataset U; please state the codomain as a power set or otherwise clarify the notation.
- [Section 8.3, Lemma 8.12] The proof says 'we may assume the adversary to be deterministic'; this is standard, but the manuscript should state explicitly that this means fixing the adversary's random coins before applying the union bound over P, and that the rounding step is deterministic so that P is well-defined.
- [Section 8.3, Theorem 1.10] The bound |P| <= (n kappa)^{Theta(dT)} is asserted without proof or citation; since all log|P| terms in the theorem depend on it, please provide a derivation or a concrete reference.
Circularity Check
No significant circularity: central reductions are black-box DP composition/generalization arguments plus external sketching guarantees; the Theorem 1.10 update-time concern is a complexity gap, not a self-referential reduction.
full rationale
The ANN reduction (Sections 6.2 and 6.3) is self-contained: privacy is proved via ReportOneSidedNoisyArgMax, subsampling amplification, and advanced composition (Lemmas 6.7 and 6.8), and utility is a counting argument in Lemma 6.12: under Assumption 1.2 each characteristic vector has support at most s, so with l=O(s log^2 n) sampled copies, the true near-neighbor class receives a signal of size Omega(log^2 n) versus DP noise of size O(log n). No parameter is fitted to the target output and the success event is the standard (c,r)-ANN specification, not an equality with the assumption. The regression results (Section 8.2) rely on the l-infinity sketching guarantee quoted from [PSW17, SYYZ23b]; although some authors overlap, that guarantee is a parameter-free theorem whose assumptions do not include the adaptive-regression target, so under the stated rules it is independent evidence rather than a self-citation chain. The bounded-computation-path algorithm (Section 8.3) uses a standard union bound over a rounded output set P; the dependence on log|P| is a complexity parameter, and correctness is not defined in terms of P. The skeptic's concern about Theorem 1.10 / Theorem 8.14 is legitimate but is not circularity: Lemma 8.13 only bounds the time to generate columns of the pseudo-random Gaussian sketch, whereas applying the sketch to a dense turnstile update v_t costs Omega(nnz(v_t) r) as written, so the claimed update time lacks a valid procedure; this is an omitted proof or complexity gap, not an equivalence between input and output.
Assumptions & free parameters
assumptions (8)
- domain assumption Assumption 1.2: each query v_t has at most s points of U within distance cr
- domain assumption Assumption 1.3: each point's cr-ball intersects at most s other cr-balls in U
- domain assumption Assumption 1.4: condition number kappa(U_t) <= kappa for all t
- standard math SRHT-composed sketches satisfy the l_infinity guarantee (Equation 2)
- standard math Differential privacy generalization theorem (Theorem 6.4)
- standard math Advanced composition of DP mechanisms (Theorem 6.2)
- domain assumption Entries of U_t, b_t and candidate solutions lie in [-n^gamma, n^gamma]
- domain assumption Existence of an oblivious ANN data structure with constant success probability and query time n^rho d (LSH)
Cite this review
Pith. "Pith review of On Differential Privacy for Adaptively Solving Search Problems via Sketching." pith.science (2026). https://pith.science/paper/UBLPZ2HP
@misc{pith2026250605503,
author = {Pith},
title = {Pith review of: On Differential Privacy for Adaptively Solving Search Problems via Sketching},
year = {2026},
howpublished = {\url{https://pith.science/paper/UBLPZ2HP}},
note = {Machine review of arXiv:2506.05503}
}
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 numerical estimation problems, and only return the cost of an optimization problem rather than the solution itself. In this paper, we investigate the use of differential privacy for adaptive queries to search problems, which are significantly more challenging since the responses to queries can reveal much more about the internal randomness than a single numerical query. We focus on two classical search problems: nearest neighbor queries and regression with arbitrary turnstile updates. We identify key parameters to these problems, such as the number of $c$-approximate near neighbors and the matrix condition number, and use different differential privacy techniques to design algorithms returning the solution vector with memory and time depending on these parameters. We give algorithms for each of these problems that achieve similar tradeoffs.
Forward citations
Cited by 1 Pith paper
-
The Adversarial Robustness of Sketching and Streaming Algorithms
A survey monograph unifying the field of adversarially robust streaming: near-optimal robustness for insertion-only streams, poly(n)-space impossibility for turnstile linear sketches, and crypto-based white-box algorithms.
Reference graph
Works this paper leans on
-
[6]
Differentially private attention computation
[GSY23] Yeqi Gao, Zhao Song, and Xin Yang. Differentially private attention computation. arXiv preprint arXiv:2305.04701,
-
[7]
On Differentially Private String Distances
[HLL+24] Jerry Yao-Chieh Hu, Erzhi Liu, Han Liu, Zhao Song, and Lichen Zhang. On differ- entially private string distances.arXiv preprint arXiv:2411.05750,
-
[13]
Differential privacy of cross- attention with provable guarantee.arXiv preprint arXiv:2407.14717,
[LSSZ24] Yingyu Liang, Zhenmei Shi, Zhao Song, and Yufa Zhou. Differential privacy of cross- attention with provable guarantee.arXiv preprint arXiv:2407.14717,
-
[16]
On efficient retrieval of top similarity vectors
[TZXL19] Shulong Tan, Zhixin Zhou, Zhaozhuo Xu, and Ping Li. On efficient retrieval of top similarity vectors. InProceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 5239–5249,
work page 2019
-
[17]
New bounds for matrix multiplication: from alpha to omega
[WXXZ24] Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3792–3835. SIAM,
work page 2024
-
[18]
[WZ24] David P. Woodruff and Samson Zhou. Adversarially robust dense-sparse tradeoffs via heavy-hitters. InAdvances in Neural Information Processing Systems 37 (NeurIPS 2024),
work page 2024
-
[19]
[YDW+21] Xiang Yue, Minxin Du, Tianhao Wang, Yaliang Li, Huan Sun, and Sherman S. M. Chow. Differential privacy for text analytics via natural text sanitization. InFindings, ACL-IJCNLP 2021,
work page 2021
-
[20]
[YNB+22] Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A. Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin, and Huishuai Zhang. Differentially private fine-tuning of language models. InThe Tenth International Conference on Learning Representations, ICLR 2022,
work page 2022
Show all 20 references
-
[2004]
Dpbloomfilter: Securing bloom filters with differential privacy.arXiv preprint arXiv:2502.00693,
[KLS+25] Yekun Ke, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, and Zhao Song. Dpbloomfilter: Securing bloom filters with differential privacy.arXiv preprint arXiv:2502.00693,
-
[2006]
Evaluating differentially private machine learn- ing in practice
[JE19] Bargav Jayaraman and David Evans. Evaluating differentially private machine learn- ing in practice. In28th USENIX Security Symposium (USENIX Security 19), pages 1895–1912,
1912
-
[2012]
[CS21] Benjamin Coleman and Anshumali Shrivastava
Association for Computing Machinery. [CS21] Benjamin Coleman and Anshumali Shrivastava. A one-pass distributed and private sketch for kernel sums with applications to machine learning at scale. InProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Secu...
2021
-
[2013]
Faster rectangular matrix multiplication by combination loss anal- ysis
[LG24] Fran¸ cois Le Gall. Faster rectangular matrix multiplication by combination loss anal- ysis. InProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algo- rithms (SODA), pages 3765–3791. SIAM,
2024
-
[2014]
Announcing scann: Efficient vector similarity search.https: // blog
[Sun20] Philip Sun. Announcing scann: Efficient vector similarity search.https: // blog. research. google/ 2020/ 07/ announcing-scann-efficient-vector. html,
2020
-
[2019]
Near-optimal private and scalablek-clustering
39 [CAEM+22] Vincent Cohen-Addad, Alessandro Epasto, Vahab Mirrokni, Shyam Narayanan, and Peilin Zhong. Near-optimal private and scalablek-clustering. InAdvances in Neural Information Processing Systems 35 (NeurIPS 2022), pages 1–13,
2022
-
[2020]
Liu, Richard Peng, and Aaron Sidford
[BGJ+22] Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, and Aaron Sidford. Faster maxflow via improved dynamic spectral vertex sparsifiers. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 543–5...
2022
-
[2021]
Li, and Quanquan C
[DLL23] Laxman Dhulipala, George Z. Li, and Quanquan C. Liu. Near-optimal differentially private k-core decomposition.arXiv preprint arXiv:2312.07706,
-
[2022]
Deep learning with differential privacy
[ACG+16] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. InProceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318,
2016
-
[2023]
A survey of collaborative filtering tech- niques.Advances in artificial intelligence, 2009,
[SK09] Xiaoyuan Su and Taghi M Khoshgoftaar. A survey of collaborative filtering tech- niques.Advances in artificial intelligence, 2009,
2009
-
[2024]
Differentially private kernel density estimation.arXiv preprint arXiv:2409.01688,
[LHR+24] Erzhi Liu, Jerry Yao-Chieh Hu, Alex Reneau, Zhao Song, and Han Liu. Differentially private kernel density estimation.arXiv preprint arXiv:2409.01688,
-
[2025]
Li, Dung Nguyen, and Anil Vullikanti
[LNV23] George Z. Li, Dung Nguyen, and Anil Vullikanti. Differentially private partial set cover with applications to facility location. InProceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI 2023), pages 4803–4811. Interna- tional Joint Con...
2023
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.