Research map / Federated learning and privacy / Differential privacy

Efficient Adaptive Data Analysis over Dense Data Distributions

NeurIPS 2026 · Federated learning and privacy › Differential privacy · approach: Private data analysis frameworks

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.

Proposes a computationally efficient adaptive data analysis mechanism (lazy online gradient descent sketch) achieving O(log T) sample complexity for data distributions dense in a known prior, yielding a sample-efficient distribution-specific SQ oracle and PSO security.

Problem

Adaptive data analysis with T adaptive linear queries typically needs O(sqrt T) samples for computationally efficient mechanisms, while O(log T) is achieved only by computationally intractable methods like PMW; the paper asks whether a natural distribution class admits both.

Approach

For distributions that are lambda-dense in a known efficiently sampleable prior, maintain a sketch of the data as a vector in the unit ball via a lazy online gradient descent update (updating only when error exceeds a threshold), answering queries by randomized inner-product estimation; a transcript of the few updates enables a union bound over a small set of possible query sequences, giving O(log

Key results

• Mechanism answers T adaptive queries to within eps using O(lambda^-2 eps^-4 log T) samples in time poly(n, 1/eps, 1/lambda, T) for lambda-dense distributions.
• Yields a distribution-specific SQ oracle with O(eps^-4 log(T/eps)) samples and poly(log N, 1/eps, T) runtime.
• Mechanism satisfies PSO security with success probability bounded by eps^-1 T^{128/(lambda eps)^2} negl(M) without added noise.

Surprising findings

• The mechanism achieves O(log T) sample complexity without differential privacy or noise addition, while remaining computationally efficient for dense distributions.

Limitations

• Applies only to distributions dense (or pseudodense) with respect to a known prior, not to arbitrary distributions.
• Sample complexity has eps^-4 and lambda^-2 dependence; PSO bound is weak, scaling as T^{128/(lambda eps)^2}.
• No experimental evaluation is reported.

Experimental setup

Metrics: sample complexity runtime PSO success probability bound

Baselines: Private Multiplicative Weights

Builds on: Private Multiplicative Weights online gradient descent Hoeffding inequality union bound Predicate Singling Out

Closest papers by meaning

• Adaptive Data Analysis for Growing Data (NeurIPS 2025 · similarity 0.87)
• On Inherent Privacy of Posterior Sampling: A Unified R\'enyi-Divergence Framework (NeurIPS 2026 · similarity 0.85)
• Oracle-Efficient Differentially Private Learning with Public Data (NeurIPS 2024 · similarity 0.85)
• Computationally Efficient Replicable Learning of Parities and Applications (NeurIPS 2026 · similarity 0.85)
• On Differential Privacy for Adaptively Solving Search Problems via Sketching (ICML 2025 · similarity 0.85)
• Minimax Optimal Two-Sample Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.85)