Research map / Learning theory and algorithms / Sample complexity
Sample-Adaptivity Tradeoff in On-Demand Sampling
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.
Characterizes the sample-round tradeoff in on-demand sampling for multi-distribution learning: realizable r-round sample complexity ~dk^{Θ(1/r)}/ε, agnostic Õ((d+k)/ε²) in Õ(√k) rounds, and poly(k) round lower bounds for the OODS abstraction.
Problem
How many adaptive sampling rounds are needed to achieve optimal sample complexity in multi-distribution learning (MDL) with k distributions, and what is the tradeoff between round and sample complexity?
Approach
Realizable case: an AdaBoost variant with a thresholded margin over k distributions yields r-round algorithms with sample complexity scaling as k^{2/r}, matched by a k^{1/r} lower bound via a hard instance with geometrically spaced difficulty levels. Agnostic case: a lazy-update Hedge (LazyHedge) that only draws samples when the cap is exceeded, framed as an abstract Optimization via On-Demand Sam
Key results
- Realizable MDL: r-round algorithm with sample complexity Õ(k^{2/r} d/ε + k/ε), matched up to k^{1/r} by an Ω(d k^{1/r}/(r log^2 k)) lower bound.
- Agnostic MDL: Õ((d+k)/ε²) sample complexity achieved in Õ(√k) rounds via ellipsoid LazyHedge.
- OODS lower bounds: for ε ≤ O(1/k), any algorithm with sample overhead s needs Ω(√(k/s)) rounds (box) or Ω((k/s)^{1/4}) rounds (ellipsoid).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase adaptivity from fully non-adaptive sampling to 3 rounds | Realizable MDL · Realizable MDL | sample complexity: \Omega(dk/\varepsilon) -> \widetilde{O}(d\sqrt{k}/\varepsilon) | Helped |
| Use r adaptive rounds rather than unrestricted adaptivity | Realizable MDL · Realizable MDL | sample complexity: \widetilde O((k^{2/r}\cdot d + k) / \varepsilon); lower bound \widetilde \Omega(k^{1/r}\cdot d/r) | Mixed |
| Use lazy Hedge updates with ellipsoid observable regions | Agnostic MDL · Agnostic MDL | round complexity: \widetilde O(\sqrt{k}) | Helped |
| Use lazy Hedge updates with ellipsoid rather than box observable regions | LazyHedge for agnostic MDL · Agnostic MDL | round complexity: O(k\log k) -> \widetilde O(\sqrt{k}) | Helped |
| Use sample overhead \widetilde O(s) | OODS in the box setting · OODS box setting | round complexity: upper bound \widetilde O(k/s); lower bound \Omega(\sqrt{k/s}) | Mixed |
Surprising findings
- Agnostic MDL algorithms that fit the OODS framework need poly(k) rounds to reach near-optimal sample complexity, so sub-polynomial round complexity would require new techniques.
- Three rounds suffice for Õ(d√k/ε) realizable sample complexity using recursive or boost-by-majority variants, a significant improvement over non-adaptive Ω(dk/ε).
Limitations
- Realizable upper and lower bounds differ by poly(r, log k) and a factor of 2 in the exponent of k.
- Agnostic round complexity Õ(√k) is not polylogarithmic; open whether polylog(k/ε) rounds are achievable with near-optimal samples.
- OODS lower bounds apply only to OODS-style algorithms, not directly to all MDL algorithms.
Experimental setup
Metrics: sample complexity round complexity
Baselines: Blum et al. realizable MDL algorithm Hedge-based agnostic MDL algorithm (Haghtalab et al.) Peng agnostic MDL algorithm fully non-adaptive MDL
Builds on: AdaBoost Hedge (multiplicative weights) Boost-by-Majority Blum et al. multi-distribution learning
Closest papers by meaning
- On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization (NeurIPS 2026 · similarity 0.86)
- Query Lower Bounds for Diffusion Sampling (NeurIPS 2026 · similarity 0.86)
- Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.86)
- Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity (ICLR 2024 · similarity 0.85)
- Sample complexity of stochastic optimization with integer variables (NeurIPS 2026 · similarity 0.85)
- Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization (ICML 2025 · 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.