Research map / Learning theory and algorithms / Prediction and decision losses
Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
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.
Shows that bottom-k cardinality sketches remain accurate under exponentially many adaptive queries as long as each key participates in at most about k^2 queries, via a fine-grained adaptive data analysis framework with two robust estimators (basic and tracking).
Problem
Adaptive (adversarially chosen) distinct-count queries can break cardinality sketches after about k^2 queries for sketch size k; the question is whether the quadratic barrier can be shifted from the total number of queries t to the per-key participation r.
Approach
Reformulates the differential-privacy robustness wrapper as adaptive data analysis with fine-grained per-key charging (sparse-vector with deactivation of keys reaching charge limit r), so that the sketch's random priorities are a product distribution and the robust bottom-k estimator is analyzed in terms of per-key participation rather than total query count.
Key results
- Basic robust estimator guarantees (1±α) accuracy for k = O(α^-2 √r log^{3/2}(n/β)), i.e., r ≈ k^2 per-key participation allowed while handling exponentially many queries.
- Tracking robust estimator degrades smoothly, remaining accurate as long as at most an α fraction of sketch entries are deactivated.
- Simulations on synthetic query sets show about 100x gain for uniform query sets and 12x (Pareto α=1.5) and 40x (Pareto α=2) gains over the per-query baseline.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use per-key participation analysis with TRobustEst instead of baseline per-query analysis | bottom-k cardinality sketch · Uniform query sets | queries answered effectively: two orders of magnitude | Helped |
| use per-key participation analysis with TRobustEst instead of baseline per-query analysis | bottom-k cardinality sketch · Pareto query sets (α=2) | queries answered effectively: 40× | Helped |
| use per-key participation analysis with TRobustEst instead of baseline per-query analysis | bottom-k cardinality sketch · Pareto query sets (α=1.5) | queries answered effectively: 12× | Helped |
| remove per-key tracking from TRobustEst (use RobustEst) (ablation) | bottom-k cardinality sketch · Uniform query sets | queries answered effectively: two orders of magnitude | Helped |
| add per-key tracking (ablation) | bottom-k cardinality sketch · Pareto query sets | queries answered effectively | Helped |
Limitations
- Analysis is specific to bottom-k sketch; extension to other MinHash variants (k-partition/PCSA) left open.
- Guarantees fail when keys are maxed in a query that has many deactivated entries (more than k/2), and the universal attacks show this is unavoidable.
- Empirical evaluation limited to synthetic Uniform and Pareto query sets.
Experimental setup
Metrics: number of effectively answerable adaptive queries gain factor over baseline analysis
Baselines: standard bottom-k estimator (StdEst) generic DP robustness wrapper (per-query analysis)
Builds on: Hassidim et al. adaptive data analysis via differential privacy bottom-k cardinality sketch fine-grained sparse vector technique (target charging)
Closest papers by meaning
- Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs (ICML 2024 · similarity 0.90)
- Towards Establishing Guaranteed Error for Learned Database Operations (ICLR 2024 · similarity 0.83)
- Tight Bounds for Answering Adaptively Chosen Concentrated Queries (NeurIPS 2025 · similarity 0.83)
- A Near Linear Query Lower Bound for Submodular Maximization (ICML 2025 · similarity 0.82)
- Clustering with Non-adaptive Subset Queries (NeurIPS 2024 · similarity 0.82)
- On Differential Privacy for Adaptively Solving Search Problems via Sketching (ICML 2025 · similarity 0.82)
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.