Research map / Learning theory and algorithms / Sample complexity
Tight Bounds for Answering Adaptively Chosen Concentrated 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.
Proves an Ω(min{1/γ, ε⁻² ln(1/(εβγ))}) query upper-limit for noise-addition and subsampling mechanisms answering adaptive concentrated queries on correlated data, and gives a simpler DP-based analysis of noise addition that supports more queries (O(min{1/γ, 1/(ε² ln²(1/ε))})).
Problem
Adaptive data analysis when samples are correlated: how many adaptively chosen concentrated queries can be answered accurately, given that the analyst's queries only need to be concentrated around their true means. Known efficient algorithms only support O(n) such queries versus O(n^2) in the i.i.d.
Approach
Shows that the O(n) barrier is inherent for noise-addition and subsampling mechanisms via an explicit correlated distribution (repeated elements across subsets) and an attack that identifies the sample; and proves accuracy of noisy empirical-mean Laplace mechanisms via differential-privacy advanced composition applied to a hybrid/oracle thought experiment, avoiding typical stability.
Key results
- NS mechanisms cannot answer more than O(n) adaptive (eps,gamma)-concentrated queries under Hoeffding-matching concentration, via a lower bound k = Omega(min{1/gamma, eps^-2 ln(1/(eps beta gamma))}).
- Laplace noise addition on empirical means is (alpha,beta)-accurate for k = O(min{beta/gamma, beta eps^-2, alpha^2 beta^2/(eps^2 ln^2(1/eps) ln(1/beta))}) adaptive concentrated queries, improving log factors over prior typical-stability analysis.
- The positive result is proved via DP advanced composition on a hybrid/oracle thought experiment, without typical stability.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the simplified differential-privacy analysis for the Laplace mechanism instead of the prior typical-stability analysis | Laplace mechanism for concentrated queries · Adaptive (ε, γ)-concentrated queries | maximum queries k: O\left(\min\left\{\frac{1}{\gamma},\;\frac{1}{\varepsilon^{2}[\ln(1/\varepsilon)]^{2}}\right\}\right) | Helped |
| Allow correlated data while restricting queries to Hoeffding-style concentration | Noise and Subsampling (NS) mechanisms · Hoeffding-style concentration, adaptive queries | maximum queries: O(n) | Hurt |
Surprising findings
- Under Hoeffding-matching concentration the O(n) barrier holds for all eps, meaning the gap to the i.i.d. O(n^2) regime is inherent for NS mechanisms.
Limitations
- Lower bound applies only to noise-addition and subsampling mechanisms, not to all mechanisms.
- Upper bound on k is tied to the current concentrated-query formulation and carries an extra ln(1/eps) factor in the positive result.
- Positive-result accuracy stated for constant (0.01,0.01) targets in the headline theorem.
Experimental setup
Metrics: statistical accuracy (alpha, beta) number of supported queries k
Baselines: typical stability noise addition (Bassily and Freund 2016 / Bassily et al.) compression-based algorithms
Builds on: Bassily and Freund 2016 concentrated queries typical stability advanced composition theorem Laplace mechanism
Closest papers by meaning
- Adaptive Data Analysis for Growing Data (NeurIPS 2025 · similarity 0.87)
- Clustering with Non-adaptive Subset Queries (NeurIPS 2024 · similarity 0.85)
- Efficient Adaptive Data Analysis over Dense Data Distributions (NeurIPS 2026 · similarity 0.84)
- A Near Linear Query Lower Bound for Submodular Maximization (ICML 2025 · similarity 0.83)
- Learning Distributions from Multiple Data Providers (NeurIPS 2026 · similarity 0.83)
- Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries (ICML 2025 · similarity 0.83)
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.