Research map / Learning theory and algorithms / Sample complexity
Adaptive Sampling for Estimating Probability Distributions
Shubhanshu Shekhar, Tara Javidi, Mohammad Ghavamzadeh
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive optimistic tracking instead of uniform allocation | Distribution sampling · Synthetic distributions, ℓ₂² distance, ε=0.5 and ε=0.9 | objective gap to approx-oracle | Improved |
| Use adaptive optimistic tracking instead of uniform allocation | Distribution sampling · Synthetic distributions, ℓ₁ distance, ε=0.5 and ε=0.9 | objective gap to approx-oracle | Improved |
| Use adaptive optimistic tracking instead of uniform allocation | Distribution sampling · Synthetic distributions, separation distance, ε=0.5 and ε=0.9 | objective gap to approx-oracle | Improved |
| Use adaptive optimistic tracking instead of greedy allocation | Distribution sampling · Synthetic distributions, ℓ₂² and ℓ₁ distances, ε=0.9 | objective gap to approx-oracle | Improved |
| Use adaptive optimistic tracking instead of forced exploration | Distribution sampling · Synthetic distributions, ℓ₂² and ℓ₁ distances, ε=0.9 | objective gap to approx-oracle | Improved |
| Use adaptive optimistic tracking instead of greedy or forced exploration | Distribution sampling · Synthetic distributions, separation distance, ε=0.9 | allocation variance | Improved |
| Replace adaptive tracking with greedy or forced exploration | Distribution sampling · Synthetic distributions, ℓ₂² and ℓ₁ distances, ε=0.5 | objective gap to approx-oracle | No clear effect |
| Use uniform allocation instead of adaptive allocation | Distribution sampling · Synthetic distributions, KL-divergence | performance | No clear effect |
| Use the first-order KL objective \((l-1)/2T_i\) and omit the higher-order term | Adaptive KL · KL-divergence | regret: \mc{O}(n^{-2}) | Hurt |
Closest papers by meaning
- Learning discrete distributions with infinite support (NeurIPS 2020 · similarity 0.87)
- Approximation Guarantees for Adaptive Sampling (ICML 2018 · similarity 0.87)
- Query Lower Bounds for Diffusion Sampling (NeurIPS 2026 · similarity 0.86)
- Sample-Adaptivity Tradeoff in On-Demand Sampling (NeurIPS 2025 · similarity 0.86)
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.85)
- A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers (NeurIPS 2024 · similarity 0.85)
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.
