Research map / Learning theory and algorithms / Sample complexity
Statistical-Computational Trade-offs for Density Estimation
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 a list-of-points lower bound showing that density estimation data structures using about n/s samples and polynomial space must have query time k^{1-O(1)/log s}, and gives a simple matching algorithm for half-uniform distributions.
Problem
Density estimation over k discrete distributions given query samples: existing data structures trade off sampling complexity and query time, and it is unknown how much both can be sublinearly improved with polynomial space.
Approach
Reduces random Gap Subset Search (a list-of-points hard instance) to uniform random density estimation via Poisson sampling, solves the resulting optimization analytically to obtain an explicit statistical-computational trade-off, and gives a simple subset-based data structure that matches it asymptotically for half-uniform distributions.
Key results
- Lower bound: any list-of-points structure with n/s samples and polynomial space needs query exponent rho_q >= 1 - O(rho_u)/log s, so with s = log^c k query time is k^{1-O(1)/log log k}.
- Simple algorithm for half-uniform distributions matches the lower bound asymptotically, with leading constant log 2 instead of 1 in the exponent.
- Experiments: the Subset algorithm uses up to 6x fewer operations per query than the Elimination baseline while reaching 100% accuracy on 100 queries.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Subset instead of Elimination | Half-uniform density estimation · Synthetic random half-uniform queries | number of operations: over 6× reduction | Helped |
| Use Subset instead of Elimination | Half-uniform density estimation · Synthetic random half-uniform queries, varying k, n, S, and ℓ | query time | Mixed |
| Increase domain size n | Subset algorithm · Synthetic random half-uniform queries | number of operations | Hurt |
| Set subset size ℓ to 5 | Subset algorithm · Synthetic random half-uniform queries | query time | No clear effect |
Surprising findings
- Query time for general density estimation cannot be improved by a polynomial factor below linear while keeping samples below n/polylog(n) in the list-of-points model.
Limitations
- Lower bound holds only for list-of-points data structures and data-independent hashing; data-dependent approaches are not ruled out.
- Matching upper bound is only for half-uniform distributions in the realizable case; general distributions remain open.
- Experiments are on synthetic random half-uniform data only.
Experimental setup
Datasets: synthetic random half-uniform distributions
Benchmarks: synthetic half-uniform density estimation instances
Metrics: number of membership operations per query query time in seconds accuracy on 100 random queries
Baselines: Subset algorithm of Aamand et al. Elimination algorithm
Builds on: Gap Subset Search lower bound (Ahle et al.) Aamand et al. density estimation data structure Locality-sensitive hashing
Closest papers by meaning
- Data Structures for Density Estimation (ICML 2023 · similarity 0.94)
- Breaking the curse of dimensionality in structured density estimation (NeurIPS 2024 · similarity 0.86)
- Query Lower Bounds for Diffusion Sampling (NeurIPS 2026 · similarity 0.85)
- Nearly-Linear Time Private Hypothesis Selection with the Optimal Approximation Factor (NeurIPS 2025 · similarity 0.85)
- Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.84)
- Optimal Hypothesis Selection in (Almost) Linear Time (NeurIPS 2024 · similarity 0.84)
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.