Sample-Adaptivity Tradeoff in On-Demand Sampling

Thank you for your detailed review! We start by clarifying the notations that you mentioned in the "weaknesses" part:

• We will define the notations $q_t$ and $q_t^m$ in Algorithm 1. Thank you for your comment!

• Parameters $p$ and $\epsilon_{\mathbb{A}}$ are used for setting the learning rate $\alpha$ (Lines 1 and 8) and the sample size $m$ for each round (Lines 2 and 5).

• The equation below Line 142 is a consequence of Markov's inequality when $h_t$ has an $O(\tau p)$ error on the mixture distribution $q_t$.

• The notation $\mathrm{diff}$ stands for a length-$k$ vector $(\mathrm{diff}_1, \mathrm{diff}_2, \ldots, \mathrm{diff}_k)$, which is in turn a uniformly random permutation of the following $k$ numbers: one copy of $c_1 \cdot d$, $\sqrt{k}$ copies of $c_2 \cdot d/\sqrt{k}$, and $(k - \sqrt{k} - 1)$ copies of $c_3 \cdot d / k$. (The constant factors $c_1, c_2, c_3 > 0$ are chosen such that these $k$ numbers sum up to at most $d$, and they are suppressed by the $\Theta(\cdot)$ notation on Lines 161--162.)

We answer your questions in the following:

1. Thanks for catching this! Yes, we meant that setting $r = \log k$ is sufficient for the $k^{1/r}$ factor to be $O(1)$, so larger values of $r$ will not help (modulo constant factors).

Regarding setting $r$ so that the two terms match, that is a very nice observation and thanks for suggesting it! For example, when $d = O(1)$, setting $r = 3$ would be sufficient for the first term to be dominated by the second. What we had in mind was the $d \gg k$ regime (e.g., the setup of Theorem 16 (formal version of Theorem 2)), in which case the first term would dominate.

We were unsure about the setting with an unknown $k$: how would the learner sample from the distributions if the number is unknown?

2. Yes, it is a typo (or at least, a loose bound) on Line 132: $r = 4$ rounds should be sufficient. And yes, it should have been $d\sqrt{k}$ on Line 157---thank you catching that!

3. We believe that the right round complexity for the agnostic setting should be $O(\log k)$, mirroring the realizable setting. That is, our lower bounds for the OODS framework suggest a barrier in achieving this round complexity if the learning algorithm treats MDL as an optimization problem in a black-box way. A concrete starting point towards breaking this barrier would be the alternative MDL algorithms (e.g., the one of [Peng, COLT'24]) that use the samples in a more sophisticated way (beyond running ERM or evaluating empirical errors) and sidestep the OODS barrier.

Thank you for your detailed response. Most of my points have been cleared up. I still don't fully understand the eq. below line 142, is it saying the weights distribution errors should be less than p rather than just minimized ? I would encourage the authors to add some more detail explaining what it means / represents in the final version. I also would encourage the authors to think about clarifying the part mentioned in the third weakness. For the unknown $k$, I guess you are right it does not make sense. Otherwise, I am happy to keep my score.

Thank you for your review! We answer your questions in the following:

1. While the lower bound in Theorem 2 is stated for constant $\epsilon$ (and thus does not have an $\epsilon$ dependence), it is easy to derive an $\Omega(\frac{1}{\epsilon} \cdot \frac{dk^{1/r}}{r\log^2 k})$ lower bound for general $\epsilon$ via the standard argument below. (The dependence would be $1/\epsilon$ instead of $1/\epsilon^2$ since the hard instance that we use is realizable.) We focused on the constant-$\epsilon$ regime for brevity. We will add the following discussion to our paper and point to it after the statement of Theorem 2.

We start with the construction for constant accuracy parameter $\epsilon_0 = 0.01$. Then, we obtain a new MDL instance by "diluting" each data distribution by a factor of $100\epsilon$: we scale the probability mass on each example by a factor of $100\epsilon$, and put the remaining mass of $1 - 100\epsilon$ on a "trivial" example $(\bot, 0)$, where $\bot$ is a dummy instance that is labeled with $0$ by every hypothesis. Learn this new instance up to error $\epsilon$ is equivalent to learning the original instance (before diluting) up to error $\epsilon / (100\epsilon) = 0.01 = \epsilon_0$. Intuitively, the example $(\bot, 0)$ provides no information, and the learning algorithm has to draw $\Omega(1 / \epsilon)$ samples in expectation to see an informative example. This leads to a lower bound with a $1/\epsilon$ factor.

2. Yes, Theorem 20 and the discussion in Appendix C.4 imply an $\widetilde O(\sqrt{k/C})$-round algorithm for agnostic MDL with sample complexity $\widetilde O(C \cdot (d + k) / \epsilon^2)$ for any $C \in [4, k]$. For example, setting $C = k^{0.8}$ gives an $\widetilde O(k^{0.1})$-round algorithm with sample complexity $\widetilde O(k^{0.8} \cdot (d + k) / \epsilon^2)$, which is generally better than the trivial bound of $dk/\epsilon^2$.

Thank you for your review! For the realizable setting, in Appendix A (Lines 584--607), we discuss using other boosting algorithms based on recursive boosting [Schapire, 1990] and boost-by-majority [Schapire and Freund, 2012]. They yield similar quantitative bounds in terms of tradeoff between sample complexity and round complexity, but can be favorable in the regime of constant rounds. For example, as mentioned in Lines 597--598, only 3 rounds of adaptive sampling suffice to achieve a sample complexity of $\widetilde{O}(d\sqrt{k}/\epsilon)$.

Thank you for your review! We answer your questions in the following:

1. The term adaptive sampling refers to that the sampling is done in multiple rounds (see Lines 104--107). The learner does not get to "decide" whether each round is adaptive or not---every round counts toward the round complexity.

Put in a different way: If the learner wants the second round of sampling to be non-adaptive (i.e., independent of the samples drawn in the first round), they could have merged the first two rounds into a single round.

"Full adaptivity" means that there is no limit on the number of rounds. "Full non-adaptivity" means that there is only one round.

2. The algorithms of [BHPQ17, CZZ18, NZ18] all require $r = \Theta(\log k)$ rounds. In comparison, our results for the realizable setting (Theorems 1 and 2) apply to a general value of $r$ (between $1$ and $\Theta(\log k)$) and not just the fully non-adaptive case. As mentioned on Lines 47--50, little was known in the regime that $2 \le r \ll \log k$.

3. To see why the $\epsilon$-dependence can be removed, it would be the most informative to check Proposition 2 and its proof sketch, which we outline in the following. The round complexity of the algorithm in [ZZC+24] has an $\epsilon$-dependence because the Hedge algorithm needs $(\log k) / \epsilon^2$ iterations, and each iteration requires one round of sampling. In comparison, the box version of our $\mathsf{LazyHedge}$ algorithm only samples when the weight assigned to one of the $k$ distributions substantially increases (say, by a factor of $2$). Since the weight of each distribution starts at $1/k$ and is at most $1$, each weight can double at most $\log k$ times. There are $k$ distributions in total, so the round complexity of the algorithm is at most $k \log k$, which is independent of $\epsilon$.

4. In each round $t$, the numbers of samples to be drawn from the $k$ distributions are computed from the mixing weights $q_t(1), q_t(2), \ldots, q_t(k)$. On Line 5 of Algorithm 1, $m$ samples are drawn from the mixture distribution $q_t = \sum_{i=1}^{k}q_t(i) \cdot D_i$. Drawing a single sample from $q_t$ is equivalent to the following two steps: (1) Sample $j \in [k]$ according to the distribution specified by $(q_t(1), q_t(2), \ldots, q_t(k))$, i.e., $j$ is set to each $j' \in [k]$ with probability $q_t(j')$; (2) Draw a sample from $D_j$. By repeating this $m$ times, Algorithm 1 obtains the number of samples that need to be drawn from each $D_i$.

5. Thank you for this comment!

6. Setting $r = \log k$ in Theorem 1 gives a sample complexity of $O(\frac{d\log k}{\epsilon} + \frac{k\log(k)\log(k/\delta)}{\epsilon}) = \widetilde O((d + k) / \epsilon)$, recovering the existing results in the first row of Table 1. (Note that the $k^{2/r}$ factor reduces to $O(1)$ when $r = \log k$.)

7. As stated, $r$ is a parameter of the algorithm and is specified before drawing any samples. It is an interesting direction for future work to design learning algorithms that set $r$ adaptively, and thereby using as few rounds as possible on each MDL instance.

8. $q_t$ is the mixture distribution specified by the mixing weights $(q_t(1), q_t(2), \ldots, q_t(k))$, i.e., $q_t = \sum_{i=1}^{k}q_t(i) \cdot D_i$. For a distribution $D$ and positive integer $m$, $D^m$ denotes the product distribution formed by $m$ copies of $D$. That is, $S \sim D^m$ is a shorthand for drawing $m$ independent samples from $m$. We will clarify these notations---thank you for catching these!

9. Note that $q_1$ is only used on Line 5, where Algorithm 1 draws $m$ independent samples from $q_1$. As mentioned in the answer to Question 4, the algorithm does not need to know $D_i$ to sample from $q_1$---to sample from $q_1 = \frac{1}{k}\sum_{i=1}^{k}D_i$, it suffices to draw an index $j$ from $\{1, 2, \ldots, k\}$ uniformly at random and sample from $D_j$.

10. Theorem 2 is a minimax lower bound that holds for all learning algorithms. It does not contradict the results of [BHPQ17, CZZ18, NZ18], since the algorithms in these work all require at least $\log k$ rounds. At $r = \log k$, the lower bound in Theorem 2 reduces to $\Omega(d / \log^3 k)$, which is consistent with the prior results (namely, the $\widetilde O(d + k)$ sample complexity for constant $\epsilon$).