Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Sample-Adaptivity Tradeoff in On-Demand Sampling
Authors: Nika Haghtalab, Omar Montasser, Mingda Qiao
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the tradeoff between sample complexity and round complexity in ondemand 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 e O((d + k)/ε2) within e O(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 e O(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. The paper does not include experiments. |
| Researcher Affiliation | Academia | Nika Haghtalab University of California, Berkeley EMAIL Omar Montasser Yale University EMAIL Mingda Qiao University of Massachusetts Amherst EMAIL |
| Pseudocode | Yes | Algorithm 1: Trade-off Multi-Distribution Learning Algorithm 2: Lazy Hedge: Hedge with Lazy Updates Algorithm 3: Lazy Hedge: Hedge with Lazy Updates |
| Open Source Code | No | Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: The paper does not include experiments requiring code. |
| Open Datasets | No | Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [NA] Justification: The paper does not include experiments. |
| Dataset Splits | No | Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [NA] Justification: The paper does not include experiments. |
| Hardware Specification | No | For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [NA] Justification: The paper does not include experiments. |
| Software Dependencies | No | Does the paper provide SPECIFIC ANCILLARY SOFTWARE DETAILS (e.g., library or solver names with version numbers like Python 3.8, CPLEX 12.4) needed to replicate the experiment? Answer: [NA] Justification: The paper does not include experiments. |
| Experiment Setup | No | Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [NA] Justification: The paper does not include experiments. |