Sample-Adaptivity Tradeoff in On-Demand Sampling

• URL: http://arxiv.org/abs/2511.15507v1
• Date: Wed, 19 Nov 2025 14:59:47 GMT
• Title: Sample-Adaptivity Tradeoff in On-Demand Sampling
• Authors: Nika Haghtalab, Omar Montasser, Mingda Qiao,
• Abstract summary: We study the tradeoff between sample complexity and round complexity in on-demand sampling, where the learning algorithm adaptively samples from $k$ distributions over a limited number of rounds.<n>We present an algorithm that achieves near-optimal sample complexity of $widetilde O((d + k) / 2)$ within $widetilde O(sqrtk)$ rounds.
• Score: 27.212536031930643
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the tradeoff between sample complexity and round complexity in on-demand sampling, where the learning algorithm adaptively samples from $k$ distributions over a limited number of rounds. In the realizable setting of Multi-Distribution Learning (MDL), we show that the optimal sample complexity of an $r$-round algorithm scales approximately as $dk^{Θ(1/r)} / ε$. For the general agnostic case, we present an algorithm that achieves near-optimal sample complexity of $\widetilde O((d + k) / ε^2)$ within $\widetilde O(\sqrt{k})$ rounds. Of independent interest, we introduce a new framework, Optimization via On-Demand Sampling (OODS), which abstracts the sample-adaptivity tradeoff and captures most existing MDL algorithms. We establish nearly tight bounds on the round complexity in the OODS setting. The upper bounds directly yield the $\widetilde O(\sqrt{k})$-round algorithm for agnostic MDL, while the lower bounds imply that achieving sub-polynomial round complexity would require fundamentally new techniques that bypass the inherent hardness of OODS.

Related papers

• Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models [55.07411490538404]
  We propose a novel parallel sampling method that improves adaptive complexity dependence on dimension $d$.<n>Our approach builds on parallel simulation techniques from scientific computing.
  arXiv  Detail & Related papers  (2024-12-10T11:50:46Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  We study the problem of PAC $gamma$-margin halfspaces with Random Classification Noise. We establish an information-computation tradeoff suggesting an inherent gap between the sample complexity of the problem and the sample complexity of computationally efficient algorithms.
  arXiv  Detail & Related papers  (2023-06-28T16:33:39Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  This paper investigates group distributionally robust optimization (GDRO) with the goal of learning a model that performs well over $m$ different distributions. To reduce the number of samples in each round from $m$ to 1, we cast GDRO as a two-player game, where one player conducts and the other executes an online algorithm for non-oblivious multi-armed bandits. In the second scenario, we propose to optimize the average top-$k$ risk instead of the maximum risk, thereby mitigating the impact of distributions.
  arXiv  Detail & Related papers  (2023-02-18T09:24:15Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  Social and real-world considerations have given rise to multi-distribution learning paradigms. We establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving zero-sum games.
  arXiv  Detail & Related papers  (2022-10-22T19:07:26Z)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  We study the problem of high-dimensional sparse mean estimation in the presence of an $epsilon$-fraction of adversarial outliers. Our algorithms follow the Sum-of-Squares based, to algorithms approach.
  arXiv  Detail & Related papers  (2022-06-07T16:49:54Z)
• Rejection sampling from shape-constrained distributions in sublinear time [14.18847457501901]
  We study the query complexity of rejection sampling in a minimax framework for various classes of discrete distributions. Our results provide new algorithms for sampling whose complexity scales sublinearly with the alphabet size.
  arXiv  Detail & Related papers  (2021-05-29T01:00:42Z)
• Sample-Optimal PAC Learning of Halfspaces with Malicious Noise [4.8728183994912415]
  We study efficient PAC learning of halfspaces in $mathRd$ in the presence of malicious noise of Valiant(1985) We present a new analysis for the algorithm of Awasthi et al.( 2017) and show that it essentially achieves the near-optimal sample complexity bound of $tildeO(d)$. We extend the algorithm and analysis to the more general and stronger nasty noise model of Bbbshoutyetal (2002), showing that it is still possible to achieve near-optimal noise tolerance and sample complexity in time.
  arXiv  Detail & Related papers  (2021-02-11T20:18:20Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  We show that model-based MARL achieves a sample complexity of $tilde O(|S||B|(gamma)-3epsilon-2)$ for finding the Nash equilibrium (NE) value up to some $epsilon$ error. We also show that such a sample bound is minimax-optimal (up to logarithmic factors) if the algorithm is reward-agnostic, where the algorithm queries state transition samples without reward knowledge.
  arXiv  Detail & Related papers  (2020-07-15T03:25:24Z)
• A Provably Efficient Sample Collection Strategy for Reinforcement Learning [123.69175280309226]
  One of the challenges in online reinforcement learning (RL) is that the agent needs to trade off the exploration of the environment and the exploitation of the samples to optimize its behavior. We propose to tackle the exploration-exploitation problem following a decoupled approach composed of: 1) An "objective-specific" algorithm that prescribes how many samples to collect at which states, as if it has access to a generative model (i.e., sparse simulator of the environment); 2) An "objective-agnostic" sample collection responsible for generating the prescribed samples as fast as possible.
  arXiv  Detail & Related papers  (2020-07-13T15:17:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.