Research map / Federated learning and privacy / Differential privacy
On Differential Privacy for Adaptively Solving Search Problems via Sketching
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Uses differential privacy over the random strings of ~sqrt(T) oblivious sketches/LSH copies to answer T adaptive search queries (approximate near neighbor and regression solution vectors) with far fewer than T copies.
Problem
Adaptive robustness of randomized search data structures: answering T adaptive queries that return solution points or regression solution vectors (not just numerical costs) without preparing T independent copies.
Approach
Treats the internal randomness of oblivious data structures as a private database; uses a sparse argmax (exponential-noise selection over sparse count vectors) to output a near neighbor, and coordinate-wise private median plus an l_infinity sketch guarantee to output regression solution vectors, with sqrt(T)-scale copies.
Key results
- Adaptive ANN data structure uses sqrt(T)*s copies of an oblivious LSH with space ~ sqrt(T)*s*n^{1+rho}+nd and query time ~ s*n^rho*d, improving over T copies when s = o(sqrt T).
- Adaptive regression with condition number kappa uses space ~ sqrt(T) d^{2.5} kappa^2/alpha^2 and query time ~ d^{omega+1} kappa^2/alpha^2 to output a (1+alpha)-approximate solution.
- Bounded-computation-path variant removes polynomial kappa dependence in preprocessing/space, with logarithmic dependence on kappa in the bound on paths.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace per-query fresh data structures with a sqrt(T)-size pool sampled with differentially private selection (sparse argmax) for adaptive ANN | adaptive (c,r)-ANN data structure · theoretical analysis (ANN with sparse neighborhoods) | number of data structure copies | Helped |
| Regression solution via coordinate-wise private median over sketched solutions, using sqrt(Td) sketches | adaptive regression with updates to U and b · theoretical analysis (well-conditioned regression) | number of sketches / space | Helped |
| Bounded computation path technique replaces sketch-count scaling with condition number, giving logarithmic dependence on kappa | adaptive regression for ill-conditioned instances · theoretical analysis (regression) | dependence on condition number kappa | Helped |
Limitations
- Requires assumption that each query has at most s approximate near neighbors (sparse neighborhoods, s <= n^rho).
- Regression bounds scale polynomially in condition number kappa in the main result; the log-kappa variant pays linear dependence on T.
- Purely theoretical; no experiments reported.
Experimental setup
Baselines: T independent copies of data structure d copies via epsilon-net argument nd copies of sketches
Builds on: differential privacy advanced composition private median framework for adaptive data structures bounded computation paths sketch-and-solve regression
Closest papers by meaning
- Private Query Release Assisted by Public Data (ICML 2020 · similarity 0.88)
- Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms (NeurIPS 2020 · similarity 0.88)
- Differentially Private Query Release Through Adaptive Projection (ICML 2021 · similarity 0.88)
- Perturb-and-Project: Differentially Private Similarities and Marginals (ICML 2024 · similarity 0.87)
- Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph (NeurIPS 2025 · similarity 0.87)
- Instance-Specific Asymmetric Sensitivity in Differential Privacy (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.