Sample-Adaptivity Tradeoff in On-Demand Sampling
Authors: Nika Haghtalab
Omar Montasser
Mingda Qiao
Venue: NeurIPS 2025 spotlight ()
Keywords: On-demand sampling
multi-distribution learning
adaptivity
Primary area: theory
TL;DR: We study the tradeoff between sample complexity and round complexity in on-demand sampling.

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^{\Theta(1/r)} / \epsilon$. For the general agnostic case, we present an algorithm that achieves near-optimal sample complexity of $\widetilde O((d + k) / \epsilon^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.

Sample-Adaptivity Tradeoff in On-Demand Sampling
Nika Haghtalab University California, Berkeley ni nika@berkeley.eed edu
Omar Montasser Yale University
omar wwt...ontassee@@yleeccoom
Mingda Qiao
University of Massachusetts Amherst mqiao@umass edu
Abstract
We study the tradeoff between sample complexity and round complexity in on- demand sampling, where the learning algorithm adaptively samples from dis- tributions over limited number of rounds. In the realizable setting of Multi- Distribution Learning (MDL), we show that the optimal sample complexity an r-round algorithm scales approximately dl /E. For the general agnostic case, present an algorithm that achieves near-optimal sample complexity of (((d + k))"²) within Ō(Vk) rounds. Of independent interest, introduce new framework, Optimization via On-Demand Sampling (OODS), which abstracts the comple-adaptivee
tradeoff and captures most existing MDL algorithms. We establish nearly tight bounds on the round complexity the OODS setting. The
upper bounds directly yield the ((Vk)) 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.
Introduction
Modern machine learning pipelines increasingly treat the training set mutable resource- the data collection process in response to intermediate learning signals in order to focus effort where it matters most. This adaptivity arises in range of settings. In multi-distribution learning (see e.g. [BPPQ17]] HJ the on-demand sampling framework allows algorithms to adaptively select domains from which to sample to minimize the worst-case loss. Similarly in multi-armed bandit problems, adaptively selecting which arm to pull next is an important aspect of algorithm design. In practice, pipelines for training models adaptively decide how to reweigh or augment their datasets to improve downstream accuracy (XPD*23) SRC24). While these paradigms demonstrate- both theoretically and empirically-thai adaptive data collection significantly improve performance and sample efficiency, adaptivity is often an undesirable feature. It requires the MI. practitioner to collect data sequentially, slowing down the end-to-end training process and limiting opportunities for parallelism and scalability. This tension raises a central question:
resouree-adapting adapting
what extent is adaptive sample collection necessary to achieve the observed gains in learning performance? ? And what are the quantitative tradeoffs between the number of adaptive rounds and sample complexity?
We study this question in the context of on-demand sampling within the framework of multi- distribution learning HIZ22] Multi-distribution learning extends the classical agnostic learning setting by giving the learner sampling access to l distributions DI.....D Dj. with the goal of learning a single predictor that minimizes the worst-case error across all distributions. This framework has
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

emerged as a central model for studying algorithmic dataset selection, offering both a method of allocating a fixed sampling budget across heterogeneous data sources and a unifying perspective on several recent advances in federated learning. multi-task learning, domain adaptation, and fair and robust machine learning [KNRWT8 MSST9 SKHH120
RY21
TH22 HJZ23 7ZC 24)].
Prior work on multi-distribution learning has established optimal on-demand sample complexities of O((d= + k)/=) in the realizable case [BHPQI7] CZZI8 [Z18] and ((log(()H)) + k)/=²) in the agnostic case [HLIZ22), where d is the VC dimension of hypothesis class H. The latter was recently extended to ((d++))/e* for infinite hypothesis classes [ZZC+24 Pen24]. However, these algorithms rely on large number of adaptive rounds ootennoften polynomial in 1/E and the complexity of H and with a mild sublinear dependence on (see Table dettaaiss.. details). In some cases, these algorithms collect a single sample per round, resulting in number of rounds that is large the sample complexity itself! In contrast, the best known fully non-adaptive algorithms incur significantly higher sample complexities of O(dk/s) and (ddk/=²) in the realizable and agnostic settings, respectively.
Despite this gap, the complexity landscape between the two extremes full adaptivity and full non- rempisss largely unexplored. In particular, it is unknown whether a constant number of adaptive rounds, or even one that is merely independent of the accuracy level E, could suffice to recover the optimal sample complexities achieved in the fully adaptive setting.
Our Contributions and Results In this work, we formalize the problem of studying the tradeoffs between adaptivity and sample complexity of on-demand sampling algorithms. Specifically, we aim for achieving the optimal sample complexity with a number of adaptive rounds that is nearly independent of e and d and with only sublinear dependence on k. We refer to the number of adaptive rounds as the round complexity of an algorithm.
In the realizable case, we provide tight characterization of the sumple-adaptiitty tradeoff. In particular, we prove that a round complexity allows for sample complexity of dl& yielding a smooth tradeoff between round complexity and sample complexity. In addition to confirming that log A rounds are necessary for achieving the optimal sample complexity in the realizable setting, this also indicates that a small constant number of rounds-say, 3 rounds (!>-are sufficient to achieve an Ö(dvk/e sample complexity, which is significant improvement over fully non-adaptive approaches. In the agnostic case, we show that ((Vk) k)) rounds of adaptivity is sufficient to achieve the optimal sample complexity of Ö(dd + k))=?).
From a technical perspective, we establish the tradeoff between adaptivity and sample complexity through two approaches. In the realizable case, our algorithms are based on novel application of a variant of the AdaBoost algorithm with a particular notion of margin. the agnostic setting, we introduce a general and abstract optimization problem called Optimization via On-Deman Sampling (OODS). In this framework, the goal is to optimize a concave function f over [0, 1] representing weights over & distributions. There is notion of sample complexity in this setting; instead, the algorithm can only access value and gradient information about f within a restricted trust region, which the algorithm as a proxy for sample complexity: the more a distribution is sampled, the better we can estimate the performance of predictors on it. The number of times the trust region is expanded before finding the optimum of f corresponds to the round complexity. We establish both upper and lower bounds on the round complexity in the OODS setting.
expand in every round. At high level, the extent of the trust region serves
strength of the OODS framework is that algorithms developed for OODS naturally transfer to the agnostic
learning problem, forming the foundation for our performance guarantees. Additionally, the optimization formulation gives rise to more natural algorithm-indee independent lower bounds on adaptivity. In particular, we prove poly(k) lower bounds on the round complexity of the OODS problem. These lower bounds shed light on the challenges of achieving the optimal sample complexity in agnostic multi-distribution learning using sub- nub-polynomial number of rounds.
1.1 Related Work
Dnsti-Disttibution Learning Blum, Haghtalab, Procaccia and Qiao [HPQ17 introduced the realizable setting of multi-distribution learning, for which several O k round algorithms with
near-optimal sample complexity of ((d+))//E) were given [HHPQ17 CZZI8 18 NZ18) On the other

---

Setting
Sample Complexity
Round Complexity
Reference
Realizable
(((d+)))
O k)
BHРQ17
CZZ NZ18
Agnostic
((])og(HH) + k)/=²)
(((log( + k)/=²)
HJZ22
Agnostic
O(d/E*+ +//²²
(llog())/E²)
AHZ23
Agnostic
k(/e) (log b (0000(((1/)) (((e+)
(log k)) (()
Pen24
Agnostic
O(log(k)/EE)
ZZC 24
Realizable
Ö((k2/ d+ -k))/EE)
Theorem
Realizable
2(k4/rd//
Theorem
Agnostic
O((d+))/e)
min m log k))
Propositions 2 and
Table 1: An overview of sample-adaptivity tradeoff in multi-distribution learning. k is the number of distributions. H the hypothesis class and its VC dimension. r denotes a tunable round complexity between 1 and Olog k). (-) and 12(-) suppress polylog k. 1/e, 1/6) factors.
hand, it is folklore that the sample complexity is ((dk/=)) without adaptive sampling. For the more challenging agnostic setting where a "perfect" predictor may not exist, the optimal sample complexity
was shown to be Ö((d + k))=²) in a series of recent work [HJZ22, AHZ23 24 Pen24]. Interestingly, all these algorithms have round complexity of at least poly (1/y(1/s) (see Table for details), Other variants of the problem, where some data sources might be adversarial or differently labeled, have also been studied [ial8 DQ24
Power of Adaptivity in Learning and Beyond Agarwal, Agarwal, Assadi and Khanna [АAAК1 systematically formulated the tradeoff between adaptivity and sample complexity in several learning problems, including batched setting multi-armed bandits that was previously introduced by Jun, Jamieson, Nowak and Zhu [JNZ16 and subsequently studied in [HRZI9 JYT 24 [ZZ25], Chen, Papadimitriou and Peng [CPP22] proposed a PAC learning framework of continual learning, and quantified the tradeoff between the number of sequential passes and the memory usage of the learning algorithm. Another recent line of work focused on the adaptivity- tradeoff submodular
optimization [SS88 9MZ19
EN19
CQ19b
BRSI9 CQ19a ENV19 LLV20].
2 Preliminaries
mntti-Distriiution Learning (MDL) We follow the formulation of MDL in [HZ22]. Let X' be the instance space and y {0, 1) be the binary label space. Let H y be hypothesis class and be its VC dimension. There are & unknown data distributions D1, D2...., D3 over x y. In each round, the algorithm draws samples from the distributions. The number of samples may differ on the k distributions. and may be chosen adaptively based on samples drawn in previous rounds. The sample complexity the total number of samples drawn from all distributions in all rounds. An r-round algorithm draws r rounds of samples and has a round complexity of r.
The goal is to learn a predictor h X' + + that performs well on all distributions Di,..., DR. Formally, letting err(h. D) (r [((z)) * y) denote the population error of predictor on distribution D, an MDL algorithm (s, 8)AA (Probably Approximately Correct) if
max (r (h, D.) < OPT where OPT EE(k]
min max err(h, D.)
BEH KE(k)
holds with probability at least 5 over the randomness in both the algorithm and the samples.
In the realizable setting, the data distributions are promised to satisfy OPT 0, i.e., there exists perfect predictor ht H such that err(h" D.) = 0 for every i [k]. We also refer to the general MDL setting-where OPT can be non-zero- the agnostic setting.

---

MDL via Game Dynamics Most previous agnostic MDL algorithms (e.g, [HZZ22 Pen24] view the learning problem as zero-sum game, in which the "min player" chooses hypothesis (or a mixture of multiple hypotheses) and the "max player" chooses a mixture of the k data distributions. These algorithms solve MDL. by simulating the game dynamics when the two players follow certain strategies, e.g., best response then boils down to finding the sample size that suffices for simulating the game dynamics accurately, For instance, simulating "min player" that best-responds to the "max player" is equivalent to finding a hypothesis that approximately minimizes the error on a given mixture of the distributions.
ZZC 24
no-regret online learning algorithm. The analysis
Sample-Adaptivity Tradeoff for Realizable MDL
3.1 Overview of Upper Bound
For the realizable setting of MDL, we present an algorithm that establishes a tradcoff between sample complexity and round complexity.
Theorem 1 (Informal version of Theorem 10 Algorithm
7 is an r-round (e, 8)-PAC algorithm for realizable MDL with sample complexity Ok22/r log k klog(M) log(k/8)
We highlight two special cases of the general tradeoff above. First, when r = log k. Algorithm D is most sample-efficient and recovers the near-optimal sample complexity bound of Ö(d + k))/) for realizable MDL [BHPQ17 CZZ18 NZ18). Second, with small constant number of adaptive rounds (e.g., r = 4), Algorithm ! has a sample complexity of (((vkk + k)/E). Thus, our result demonstrates that even in the limited-an -ndatedddaptiiiity regime of O1), we can improve the ((dk/s)) sample complexity required in the fully non-a -daatidee case of r =
Remark 1. Using more sophisticated variants of boosting such as boajoryy (SF12) Chap- ter 13] or recursive boosting [Sch90], is possible to achieve a sample complexity of ((dd(k+)))))) using exactly 3 rounds. Formal claims are deferred to Appendix
A Additional Notations distribution D, we write Dam as its m-fold product distribution, and S ~ Dam is shorthand for drawing size-m sample S from D. At each iteration & of the algorithm, we maintain weights ge (1), ge (2)..... ........lll... ge(K (k) 2 0 that sum up to 1. We also abuse the notation and write q as the mixture distribution Σn= 9c(i)-D, While distributions D1, D2...., D2 are unknown, the algorithm may still sample from the mixture qe easily: it suffices to first draw a random index i such that Pr li jl = (j) for each j [k] and then sample from Dj.
To state our algorithm succinctly, we introduce few more notations. For
Algorithm 1: Trade-off Multi Distribution Learning
Input:
Sample access to & unknown distributions Dı,..., Day an optimal PAC learner for class H. number of rounds target error E, and failure probability 8.
Set margin& 0 = 2 [ko P = _/2 (4 -10-0) 1+770. and 2/2 In 1-2
p
Set E = 7. 8A 2r
5 and m = O (
( (+Hog(1/6w) en
3 Initialize q1 (j) = 1
& for each j E (I,..., k). and let (1 Et
for = 11,2...., do
Call learner A on sample S. @ and let he be the returned predictor.
for 1,2,,.... k do
Draw a sample Sj, DSn where 12 log(2rk/0).
Update:
((())
{ e ererrhe, Sf,) < I Ze ca
(++(())
if crr(,,,,
where Z, is normalization constant that ensures Σ/=1 441(()) 1.
Output: Majority- Vote Predictor F: +
I hx(x) 2 1/2].

---

Technical Overview We explain here the main ideas behind Algorithm 1 the full proof and analysis deferred to Appendix[A] We rum variant of the classical AdaBoost algorithm [SF12] to maximize particular notion of "margin" that is defined on distributions Di..... Da. Specifically, in each round S S A calls learner to learn a predictor he that has a low enror on gr:
Σ ()))) err(h, Dj) crr(he, 9t) S tp.
1=1
Then, by Markov's inequality, hy also minimizes the fraction of distributions (as weighted by q:) that have error more than 7:
Σ (:(ii [err(he, Dj) >]
Subsequently, Algorithm [ Juddates the weighted mixture g over the k distributions based on the thresholded loss function I [err(h;, Dj) > 7] (as is done in AdaBoost). After rounds, the margin- maximization property of AdaBoost guarantees that
& Σ h
0
(err(h,, D2) >
S
2 (1 p)pppp) 110
By choosing the margin parameter 0 and p such that guaranteed that, on each of the k distributions, at least 1/2 + 0/2 fraction of the predictors have error most т. Formally, holds for every j [K] that
I 2 (1 (1 1/k, we are
(err((h, D2) >
2
2
Finally, with this margin property, invoking Lemma implies that the majority-vote predictor will have eтror at most (1 + 1/0)r E on all & distributions.
3.2 Overview of Lower Bound
The following theorem complements Theorem by showing that R0(1/r) overhead is unavoidable. Theorem 2 (Informal version of Theorem 16]. For every r O(log k) and sufficiently large d, every //= <log*
r-round algorithu for realizable MDL has an Q
sample complexiry.
This sample complexity lower bound nearly matches the dk2/r lk2/ term in Theorem up to poly(r, log k) factor and factor of 2 in the exponent of ((1//))
We briefly sketch the proof the r = 2 case, i.e., an ((dvk) lower bound against two-round algorithms. We consider the class of linear functions over = F2, which has a VC dimension of d. The ground truth classifier h" is drawn uniformly at random from all the 2d linear functions. To construct the & data distributions, we choose k difficulty levels diff, diff,,... diff; as a uniformly random permutation of: (1) 1 copy of (d)); (2) Vk copies of ((d/ Vk); (3) k - vk - 1 copies of (dd/k). Note that Σ i=1 diff; < d. Each data distribution D; is the uniform distribution over randomly chosen diff, diff,-dime dimensional subspace Vi C Fg. Furthermore, the subspaces V,, V2,... ...., Vv are chosen such that they are linearly independent, i.e.,
Σt diff,
Intuitively, diff, measures the "effective sample complexity" for learning D;: @(diff,) samples are sufficient and necessary learn an accurate classifier for D,. addition, since ht* is randomly chosen and the subspaces V1, Vz...., V/2 are independent, samples collected from one distribution D; provide no information about the value of h" on V, (except for the zero vector) for every j # i. Furthermore, if diff, E (d(d/v) (k), O(d) and m & d/Víi samples have been drawn from D;. holds with high probability that the vectors in these samples are linearly independent. Then, the learner gains information for distinguishing whether diff, (dd/ vk) diff; O(d).
three-round learner has a simple strategy: (1) In Round 1, draw (d/kk) samples from each distribution, thereby identifying the distributions with diff, (dd/k) as well as learning the value
5

---

of h² on each V;; (2) In Round
2. draw ((d/Vh) samples from each of the vk + +1 remaining
distributions, which is sufficient for all distributions except the one with diff, = (dd): (3) In Round learn the only remaining distribution using ( samples. The resulting sample complexity is O(d).
In contrast, two-round learner must "skip" of the three steps. For example, in Round 2 where there are still vk + "suspects" among which one distribution has difficulty level (dd) the learner could draw (d) samples from each of them. Alternatively, the learner could draw ((d/ /k) samples from each distribution in Round 1, so that the distribution with diff; (d) can be identified and then learned in Round 2. However, both strategies would have an ((dvk) sample complexity.
The formal proof (in Appendix B extends the hard instance construction to all O k) by using r + different difficulty levels separated by a k2/r factor. We then formalize the intuition that every r-round MDL algorithm must "skip" step and thus incur k//r overhead in the sample complexity.
Sample-Adaptivity Tradeoff for Agnostic MDL
For the agnostic setting, we show that the near-optimal sample complexity of Ö((d k)/=²) can be achieved by a poly(k) prooudd algorithm.
Proposition 1 (Corollaries 21 and 22
There is min log ) MDL algorithm
with sample complexity Õ(dd + k))
The MDL Algorithm of 2 Our starting point is the approach of 777-24 Algo-
rithm 1], which we briefly describe below. For brevity, we use Õ(+) and O()) to suppress polylog(k, i d, 1/8) factors, and let err(h, S) = [S] E (ay)es 1 [h(x)) # y) denote the empir-
1
ical error of hypothesis h X + y on dataset S C X ))
The algorithm maintains datasets S1, S2.... ........., Sk. where each S, contains training examples drawn from D;. The algorithm runs the Hedge algorithm for T O k)//²) iterations starting at (1) (1/k, 1/k, 1/k:). Each iteration / E [T' consists of the following two steps:
ERM step: For each E [k), draw additional samples from D, and add them to St until |S|| 2 w (t) ((d k)) Then, find hypothesis (1) H that minimizes the empirical error f.hh) = Σt_ m/ err(h, 5;), which is an estimate of the error of h on Σx= me D,.
Hedge update step: For each i E [k]. draw w/" ((k) fresh samples from D, to obtain an estimate (t)
ri x 1r D.). Compute (t+1)) from ((()) and y() via a Hedge update.
The crux of the analysis of (ZCC+44 to show that the dataset sizes in the two steps above sufficiently large, so that (+) approximately minimizes the error on mixture Σ w D.. and the reward vector n:(1) is accurate enough for the Hedge update.
A straightforward implementation of the algorithm needs T = O(llog))/ rounds of sampling. In comparison, the Ö(Vk) K) round complexity in Proposition is lower when < 1/K2/4,
Hedge with Lazy Updates We prove Proposition by modifying the algorithm of iZc 22 so that it draws samples more lazily. The resulting algorithm is termed LazyHedge and formally defined in Algorithm 2 There are two versions of the algorithm- -he "box" version and the "cllipsoid" version- give the O k)) and Ö(Vk) round complexity bounds, respectively.
Similar to the Hedge algorithm, LazyHedge maintains weight vector (t() at each iteration t. In addition, it maintains a cap vector T.!) as a proxy for the size of dataset S, time t. At the start of iteration t, it checks whether (t) is "observable" under cap (t--1) in the sense that w(() E (w)(t))) If the condition holds, no additional samples are drawn and the cap vector is left unchanged. Otherwise, the cap (t)) is updated to times the entrywise maximum of all weight vectors so far, and additional samples are drawn so that both |Sa| and |Sa,el match :!!) Finally, LazyHedge computes the next weight vector (t+1) from (t using the Hedge update rule.

---

Algorithm 2: LazyHedge: Hedge with Lazy Updates
Input: Number of distributions k, number of iterations T = ((log /))/ step size (
margin parameter C' > 1.
Box version: Define (w) == {w E A k-1 - W2 Vi E [}}}}-
Ellipsoid version: Define ( = {w : Di=1 /w, - 1}. 3 Set (1()) (1/k, 1/k,.... 1/k) and ml() = (0,0, .......... 0).
Set S, for E [k] and S for i [K] and t [T].
5 for t = ........7 do
if (t) E (ww(t-1) then
Set wl(t) = ((1-1)
else
Set w = max w (1)
(1) for every i E [k].
w w;
Add samples from D; to S; until |S 2 w. (0) O(dd k)/=²) for every E [A:]
10
Add samples from D; to St, until |St 2 w ((k) for every i E [k] and t I t' S T.
11
ERM step: Set (())) E #argmin Σ with err( (h, St).
12
Hedge update step: Set r( crr(h()) S..)). Compute (1+1)) E Ak such that
13
(1+1) mm!
(c)
Σラ 1n nese for every i E [k].
Output: Randomized classifier uniformly distributed over (h(W) ..... h()).
The correctness and sample complexity of LazyHedge follow from the analysis of ZZC 24] At a high level, either version of LazyHedge ensures that using St in the ERM step and using S., in the Hedge update step lead to low-variance estimates, which allow the analysis of [ZZC [Z]++4] to go through. We provide more detailed analysis in Appendix C.44
remains to upper bound the round complexity of LazyHedge, namely, the number of times the cap vector is updated in Line For the box version, we have an O log k) upper bound.
Proposition 2. The box version of LazyHedge takes at most O(k log k) rounds.
Proof sketch. If the cap vector is updated in the t-th iteration, there exists i E [k] such that w.") w(t-1) We call such index the culprit of this cap update. For index i to be the culprit, the historical high of w
(1) must have increased by a factor of C' since the last cap update. As this historical high is non-decreasing and in [1/k, 1). each index can be the culprit at most Ologg k) times. Thus, the round complexity is at most l: O(loge k) O(k log k) for any constant C > 1.
For the ellipsoid version, a more involved analysis gives an Ö(V)) round complexity bound. Proposition 3. The ellipsoid version of LazyHedge takes at most Ö(V)) rounds.
The analysis applies the following technical lemma shown by (ZZC*
Lemma 3 (Lemma 3 of 24). For some choice of T O(log k)/²²))))))))))))))))) and n O(s) in (0) LazyHedge, it holds with probability - that Σ i= max w < O(log (k/(Eō))) = Õ(1).
Proof sketch of Proposition 3 We classify the cap updates into two types: A "Typp I' update is when some coordinate W; reaches historical high of > 1/Vk, and "Type II" update is one without significant increase in any coordinate. We show that either type of cap updates happen Ö(Vk) times.
The upper bound for Type updates follows from Lemma 3. which implies that there are at most Õ(1) . V Type updates where the coordinate reaches = 1/v at most Õ(1) vk/2 Type updates where the coordinate reaches 2s VT, and so These upper bounds sum up O(Vk).
The analysis for Type updates is more involved. Roughly speaking, we say that a coordinate i E [k] gains a potential of a when the historical high of w; increases from b to through the
7

---

Hedge dynamics. The Ö(Vk) bound follows from two technical claims: (1) Each Type II update may happen only if total potential of (?(1) accrued over all k coordinates; (2) The total potential that the I coordinates may contribute to Type II updates is at most ((Vi).
5
A General Framework: Optimization via On-Demand Sampling
5.1 Problem Setup
In Optimization via On-Demand Sampling (OODS), the goal is to maximize a concave function f over the probability simplex A := {w E E > W; 1, w; > 0 Vi E [A]]] by "sampling" from the coordinates. The algorithm does not have full access to f: instead, it maintains a cap vector wh E [0, 1J that specifies the observable region of the simplex. We focus on two concrete settings the problem, where the observable region is either box or an ellipsoid defined by w.
Definition 1 (Optimization via On-Demand Sampling). f: A - [0. 1] is an unknown concave function. In each round / = 1, 2...., r. the algorithm chooses cap w (*) E [0, 1] that is lower bounded by ( entry-wise (if t > 1). Then, the algorithm makes arbitrarily many queries to a first-order oracle of f w-wch returns the value and a supergradient at any w E O(T(())
). where ( =
{w E A"-1; w, I W. Vi E [k]] in the box setting, and ( = w E A &--1, > w //; S 1} in the ellipsoid setting. The goal is to find vi E A such that (()) 2 max max f(w) while
(r) and the round complexity r. minimizing the sample overhead E W
To how OODS connects to MDL and on-demand sampling in general, we view the l coordinates as distributions D1, D2...., D2 from which the algorithm may sample. Maximizing (w) can then be viewed as optimizing the mixing weights in mixture Σ wo D,. The cap W; is proxy for and proportional to the number of samples that have already been drawn from D,. In light of this analogy, the sample overhead Σ i== m|(") is simply proxy for the total number of samples that the algorithm draws, while the round complexity r is the number of rounds of on on-demand sampling.
The observable region (w)) represents the mixing weights w E A on which f(w) can be accurately estimated using the current dataset specified by w. In the box setting, the algorithm is only allowed to query f(w) if w; < W; holds for every i E [k),, which can be viewed as a sufficient condition for the algorithm to obtain an accurate estimate for mixture Σ Di=1 w; W, using the (TT))) samples collected from each D;. In the ellipsoid setting, we use the more refined condition E "2 /T. I 1, where the summation is proxy for the variance in estimating the mixture En W; using the datasets. More details on how the box and ellipsoid settings connect to MDL can be found in Appendix C.4
5.2 Overview of Upper Bounds
For the OODS problem, give a simple algorithm with a poly(k) round complexity. The algorithm is also termed LazyHedge, as it is almost identical to the agmostic MDL algorithm in Section[4 We formally define the algorithm (Algorithm (3) in Appendix forr completeness. To guarantee sample overhead of Ö(s), the algorithm takes (kk/s) rounds in the box setting and ((Vk/s) rounds in the ellipsoid setting. Here, the Ö(-) notation hides polylog(k/s) factors, where e is the accuracy parameter in OODS.
Theorem 4 (Informal version of Theorems 8 and 20). There is an OODS algorithm with sample overhead Öss) that takes (kk/)) s) rounds in box setting and ((skk(s s) rounds in ellipsoid setting.
Hedge with Lazy Updates We apply the same LazyHedge strategy as in Algorithm for MDL. LazyHedge maintains weight vector we(t) each iteration L. At the start of iteration f, it checks whether ( is still in the observable region (w((t))) specified by the previous cap (--1)) If so, the cap is left unchanged; otherwise, the cap (t) is set to C times the entrywise maximum of all weight vectors so far. Then, LazyHedge queries the first-order oracle to obtain supergradient y(() at
(t)), and computes the next weight vector (1+1) using the Hedge update. While LazyHedge takes
8

---

T = e (log k)/=²) iterations, its round complexity is the number of times the cap is updated, which can be much lower than T.
Analysis for the Box Setting We sketch the analysis for the box setting, and defer the ellipsoid setting to Appendix The standard regret analysis of Hedge shows that LazyHedge finds an O(e)-
approximate maximum. We prove the following lemma in Appendix C.1
Lemma 5. LazyHedge oulputs v E A such that f()) 2 max maX f(w) O(e).
Next, we show that the sample overhead of LazyHedge is low. Recall that C > 1 is the margin parameter used in LazyHedge for the cap updates.
Lemma 6. LazyHedge has an O log" (k/=)) sample overhead.
Proof. LazyHedge guarantees that (T) S C maxigisT W. for every i E [k]. By Lemma
3 the
sample overhead is Σ W C C.E. maxigisT w OCC log (k/e)).
remains to upper bound the round complexity of LazyHedge in the box setting. The proof of the following lemma resembles and extends that of Proposition in the MDI. setting.
Lemma 7. LazyHedge takes min (k; O(kk/C) logg (k/e)) Olloge k) rounds in the box setting.
Proof sketch. If the cap is updated in the t-th iteration of LazyHedge, there exists i E [k] such that argument in 2 each index can be the culprit of at most Ollgg k) cap updates. It remains to bound the number of indices that become the culprit of least one cap update. This number is trivially most k. Furthermore, since LazyHedge sets (t) (C/k, C/k...., C/Kk) in the first iteration, for index to become the culprit of a later cap update, uz must reach C/k for some t. By Lemma at most (C1)/CC/k) Ōk/CC) indices satisfy this. Thus, the round complexity is at most min(k, Ok//O)) Ollogg k).
w!!") m (t-1) We call such index i the culprit of this cap update. By the
Proposition
Combining Lemmas 5 6 and immediately gives the first part of Theorem 4
Theorem For any C [2, k),, in the
box setting. LazyHedge finds an (())aapproximate maximum with an OC log (k/=)) sample overhead in min log k), O(kkCC) log (k/E))) rounds.
5.3 Overview of Lower Bounds
The following theorem shows that the poly(k/s round complexity in Theorem 4 cannot be avoided when E < 1/ poly((k). For exponentially small E, the exponents on k/s also match Theorem
Theorem (Informal version Theorems 25 and 28). If S O(1/k), every OODS algorithm with sample overhead s must take Ω1 kk/s) rounds in the box setting and (((k/s))44 rounds in the ellipsoid setting. If S -Q(k), every OODS algorithm with sample overhead s must take (kk/s) rounds in the box setting and (KV/k// kk/s) rounds in the ellipsoid setting.
As a corollary, if < (1)k), every OODS algorithm has either poly(k) round complexity or a sample overhead that is almost linear in k. While these lower bounds do not directly imply lower bounds for agnostic MDL., they show that further improving the round complexity in Proposition requires substantially different approach. Roughly speaking, the MDL algorithm of 24 fits into the OODS framework because: (1) It uses samples in a restricted way: finding an ERM on mixture Σ Ei=1 W. Dj for some weight vector w in an "observable region",, and estimating the error of h on every D;; (2) By solving the MDL instance, it finds a "hard" mixture > d; on which the best hypothesis in 7. has an error close to the minimax value. The first property ensures that the MDL algorithm requires no more information than what the first-order oracle provides in OODS. The second ensures that the MDL algorithm implicitly solves the OODS problem. Theorem 9 then suggests that every algorithm with the two properties faces an inherent obstacle in achieving a sub-polynomial round complexity.

---

We sketch the proof of Theorem 9 in the box setting and the - O(1/k) regime; the formal proofs are deferred to Appendix D We consider the objective function f(w) == min + j 3/m²) }. where i7 ......., im E [k] are m I k different critical indices sampled uniformly at random. The lower bound builds two observations on f: (1) (Lemma 23) I S O(1/k), every e-approximate maximum must put an (11mm) weight on at least half of the critical indices ii:... , (2) (Lemma 24 Unless we put weight of >> 1/mm² on each of fi, i22............ ........ 1j. the value of f'wr) is determined by the first. terms in the minimum. Intuitively, unless we already "know" the first j critical indices, we cannot learn the values of 1 i. from the first-order oracle.
There is a natural m-round algorithm that solves the instance above. In the first round, we query the uniform weight vector w (I/k, 1/kk................... 1/k) to learn the value of i7. In the second round, we query f on some w with waz >> 1 1/m²², thereby learning the value of izz Repeating this m times recovers all the critical indices. One might hope to be "more clever" and learn many critical indices in a round. For example, the algorithm might put a cap of > 1/m2 on several coordinates in the first round, in the hope of hitting more than one indices in ii, 22 ... However, if the algorithm has sample overhead of s, only O(m²s) such guesses can be made. In particular, assuming m << / Vk/s. the (mm²s < k guesses only cover a tiny fraction of the indices. Thus, over the uniform randomness in i", the algorithm learns only (1)) critical indices within each round in expectation.
Discussion
In this work, we formalized the trade-off between sample and round complexities in nulti-ddistibbuton learning (MDL). For the realizable case, we obtained a nearly tight characterization: when the learner is allowed r rounds of sampling, the optimal sample complexity is proportional to k(1/r) In particular, constant number of rounds suffice achieve a sublinear dependence on k. whereas nearly log & rounds are necessary to reach near-optimal sample complexity.
For the more general agnostic setting, introduced the optimizatiin via on-demand sampling (OODS) problem as an abstraction of the common approach shared by many recent MDL algorithms. We then leveraged the intuition behind the OODS algorithms to obtain an improved round complexity of O(vR( R). On the negative side, any MDL algorithm based on the OODS approach must take poly (k) rounds to match the near-optimal sample complexity of Ö(d + k)/=²).
To further understand the landscape of sample-adaptivity trade-off in agnostic MDL, we highlight the following concrete open question:
Open Question 1. Does there exist an agnostic MDL algorithm that simultaneously achieves sample complexity Ö ( d+t and round complexity polylog(k/s)?
Our results on OODS may shed light on both directions. The lower bounds for OODS suggest that any such algorithm must leverage the data in more sophisticated manner-beyone invoking an ERM oracle or merely evaluating empirical risks. Notably, a recent algorithm of Peng [Pen24] is one such candidate: despite having high round complexity (cf. Table [ it uses the collected data to construct a "refined" hypothesis class and might therefore circumvent the OODS lower bounds.
Conversely, to establish a round lower bound for sample-optimal MDL algorithms, a natural approach would be to recast our hard instances for OODS MDL instances. The key challenge, however, lies in ensuring that every MDL algorithm gains no more information from the samples than OODS- based learners do. Developing such a reduction would establish a deeper connection between MDL and OODS, and represent a major step toward a complete understanding of the sample-adaptivity trade-off.
Acknowledgments and Disclosure of Funding
This work was supported in part by the National Science Foundation under grant CCF-2145898, by the Office of Naval Research under grant N00014-24-1-21599 an Alfred P. Sloan fellowship. and a Schmidr Science AI2050 fellowship. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of sponsoring agencies.
10

---

References
[AAAK17] Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna. Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, volume 65 of Proceedings of Machine Learning Research, pages 39-75. PMLR, 2017.
[AHZ23] Pranjal Awasthi, Nika Haghtalab, and Eric Zhao. Open problem: The sample complexity of muuti-distributtin learning for VC classes. In Gergely Neu and Lorenzo Rosasco, editors, The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pages 5943-5949. PMLR, 2023.
[BHPQ17] Avrim Blum, Nika Haghtalab, Ariel D. Procaccia, and Mingda Qiao. Collaborative PAC learning. Isabelle Guyon, Ulrke von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Pro- cessing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 2392-2401, 2017.
[BRS19] Eric Balkanski, Aviad Rubinstein, and Yaron Singer. An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. In Moses Charikar and Edith Cohen, editors, Proceedings of the 5 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 66 77. ACM, 2019.
[BS18] Eric Balkanski and Yaron Singer. The adaptive complexity maximizing a submodular function. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceed- ings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1138-1151. ACM, 2018.
[CPP22] Xi Chen, Christos H. Papadimitriou, and Binghui Peng. Memory bounds for continual learning. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31- November 2022, pages 519-530. IEEE, 2022.
[CQ19a] Chandra Chekuri and Kent Quanrud. Parallelizing greedy for submodular set function maximization in matroids and beyond. In Moses Charikar and Edith Cohen, editors, Proceedings of the S1 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 78-89. ACM, 2019.
[CQ19b] Chandra Chekuri and Kent Quanrud. Submodular function maximization in parallel via the multilinear relaxation. In Timothy M. Chan, editor, Proceedings of the Thirti- eth Annual ACM-SIAM Symposium on Discrete Algorithmss, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 303-322. SIAM, 2019.
[CZZ18] Jiecao Chen, Qin Zhang, and Yuan Zhou. Tight bounds for collaborative PAC learning via multiplicative weights. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 3602-3611, 2018
[DQ24] Yuyang Deng and Mingda Qiao. Collaborative learning with different labeling functions. In Forty-first International Conference on Machine Learning. ICML 2024, Vienna, Austria, July 21-27, 2024, pages 10530-105533 OpenReview.net, 2024.
[EN19] Alina Ene and Huy L. Nguyen. Submodular maximization with nearly-optimal approxi- mation and adaptivity in nearly-linear time. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM- Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 274-282. SIAM, 2019.
11

---

[ENV19] Alina Ene, Huy L. Nguyen, and Adrian Vladu. Submodular maximization with matroid and packing constraints in parallel. In Moses Charikar and Edith Cohen, editors, Proceedings of the st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 90-101. ACM, 2019.
[FMZ19] Matthew Fahrbach, Vahab S. Mirrokni, and Morteza Zadimoghaddam. Submodular maximization with nearly optimal approximation, adaptivity and query complexity. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 255-273. SIAM, 2019.
[GHRZ19] Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengging Zhou. Batched multi-armed bandits problem. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché- Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8- 8-14, 2019, Vancouver, BC, Canada, pages 501-511, 2019.
6] Steve Hanneke. Refined error bounds for several learning algorithms. J. Mach. Learn. Res., 17:135:1-135:55 2016.
[HJZ22] Nika Haghtalab, Michael I. Jordan, and Eric Zhao. On-demand sampling: Learning optimally from multiple distributions. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Process- ing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
[HJ223] Nika Haghtalab, Michael I. Jordan, and Eric Zhao. A unifying perspective on multi- calibration: Game dynamics for multi-objective learning. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
[JINZ16] Kwang-Sune Jun, Kevin G. Jamieson, Robert D. Nowak, and Xiaojin Zhu. Top arm identification in multi-armed bandits with batch arm pulls. In Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016, Cadiz, Spuin, May 9-11, 2016, volume 51 JMLR Workshop and Conference Proceedings, pages 139-148. JMLR.org. 2016.
[JY++24] Tianyuan Jin, Yu Yang, Jing Tang, Xiaokui Xiao, and Pan Xu. Optimal batched best arm identification. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomezak, and Cheng Zhang, editors, Advances in Neural Infor- mation Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver. BC, Canada, December 10 15, 2024, 2024.
[JZZ25] Tianyuan Jin, Qin Zhang, and Dongruo Zhou. Breaking the log(1/Az) barrier: Better batched best arm identification with adaptive grids. In International Conference Learning Representations (ICLR), 2025.
[KNRW18] Michael J. Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerrymandering: Auditing and learning for subgroup faimess. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 2569-2577. PMLR, 2018.
[Lar23] Kasper Green Larsen. Bagging an optimal PAC learner. In Gergely Neu and Lorenzo Rosasco, editors, The Thirty Sixth Annual Conference on Leurning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pages 450-468 PMLR, 2023.
12

---

[LLV20] Wenzheng Li, Paul Liu, and Jan Vondrák. A polynomial lower bound on adaptive complexity of submodular maximization. In Konstantin Makarychev. Yury Makarychev. Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, H.., USA, June 22-26, 2020, pages 140-152. ACM, 2020.
[MRT18] M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning, second edition. Adaptive Computation and Machine Learning series. MIT Press, 2018.
[MSS19] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agmostic federated learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 4615 4625. PMLR, 2019.
[NZ18] Huy L. Nguyen and Lydia Zakynthinou. Improved algorithms for collaborative PAC learning. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NewrlPS 2018, December 3-8, 2018, Montréal, Canada, pages 7642-7650, 2018.
[Pen24] Binghui Peng. The sample complexity of multi-distribution learning. In Shipra Agrawal and Aaron Roth, editors, The Thirty Seventh Annual Conference on Learning Theory, June 30 July 3, 2023, Edmonion, Canada, volume 247 of Proceedings of Machine Learning Research, pages 4185-4204. PMLR, 2024.
[Qia18] Mingda Qiao. Do outliers ruin collaboration? In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceed- ings of Machine Learning Research, pages 4177-4184 PMLR, 2018.
[RY21] Guy N. Rothblum and Gal Yona. Multi-group agnostic PAC learnability. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 9107-9115. PMLR, 2021.
[Sch90] Robert E. Schapire. The strength of weak learnability. Mach. Learn., 5:197-227, 1990.
[SF12] Robert E. Schapire and Yoav Freund. Boosting: Foundations and Algorithms. The MIT Press, 2012.
[SKHL200] Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang. Distribu- tionally robust neural networks. In 8th International Conference on Learning Repre- sentations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[SRC24] Judy Hanwen Shen, Inioluwa Deborah Raji, and Irene Y. Chen. The data addition dilemma. In Machine Learning for Healthcare Conference, 2024.
[TH22] Christopher J. Tosh and Daniel Hsu. Simple and near-optimal algorithms for hidden strat- ification and multi-group learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 21633-21657. PMLR, 2022.
[XPD*23] Sang Michael Xie, Hieu Pham, Xuanyi Dong. Nan Du, Hanxiao Liu, Yifeng Lu, Percy S Liang, Quoe V Le, Tengyu Ma, and Adams Wei Yu. Doremi: Optimizing data mixtures speeds up language model pretraining. In Advances in Neural Information Processing Systems, pages 19799-668111 2023.
IZZC 24] Zihan Zhang, Wenhao Zhan, Yuxin Chen, Simon S. Du, and Jason D. Lee. Optimal multi-distribution learning. In Shipra Agrawal and Aaron Roth, editors, The Thirty Seventh Annual Conference on Learning Theory, June 30 July 3, 2023, Edmonton, Canada, volume 247 of Proceedings of Machine Learning Research, pages 5220-5223. PMLR, 2024.
13

---

A Upper Bound for Realizable MDL
In this section, we prove the following upper bound sample-adaptivin tradeoff for realizable multi-distribution learning:
Theorem 10. For any k unknown distributions Di...., Dj, any class H such that OPT = 0, and any target enror and number of rounds r I log(k), the output predictor F of Algorithm satisfies with probability at least 1 6,
AA j k: (j)
Furthermore, Algorithm 7 uses adaptive rounds and has sample complexity of
o 0 (122 2/ lkg(k)
k klog(k)
k 8 ))
+
log
Before proceeding with the proof of Theorem 10 we state a few lemmas that will be useful in the proof. First, instead of using plain ERM which incurs a sample complexity of O (1) ) will be particularly udvantageous for us to use an optimal PAC learner that avoids the log(1/e (1/s) factor in sample complexity.
Lemma 11 (Optimal Sample Complexity of PAC Learning, [6nn Lar23)). ). For any class H. there
exists an improper learner A, such that for any distribution D where inf err(h, D) = O, with probability least over 1 where 0 d+log(1/8) ), err( err(A (()), D) S e. In particular, as shown by Lr233 bagging combined with ERM yields an optimal PAC learner A.
Next, the lemma below essentially allows us to argue that we can perform weight updates in Algorithm based on empirical error instead of population error.
Lemma 12 (Empirical Samples and Population Error). For any fixed predictor ht X + V, any distribution D over X x V, any 8 (0, 1), any (0, 1/2), with probability at least 1 ô over ~ D where 12 log(1/5), the followings holds:
1. If err(h,, D) then err (h, 5) T/2, and
2. if erer(h, 5) > 7/2 then err(h, D) 7 /4.
Proof. We apply a standard Chernoff bound.
Finally, the lemma below shows that, when at least a 1/2 0/2 fraction of predictors achieve error at most distribution D, the majority-vote achieves error at most (1 + 1/0)r on D.
Lemma 13 (Weighted-Majje Majority Error Bound). Let D be an arbitrary distribution over X Y, (0, 1), (0,1) For any predictors hy...., by with corresponding (non-negative) weights 01,..., Oty that satisfy
Σ a D) 5| 7| Σ aerr(hh D)
2 > at
holds that
1 )
Pr (D
1
Σ (x))
a4
#
t=1
Proof. Let G, (1Sis:: err(hy, D) ST), and B, [r] \ Gr. Without loss of generality, we will consider the normalized weights, i.c. assume Σ 2t=1 at 1. Let We Eieo, at and
14

---

WB = ELEB, ac. Observe that
1
Σ
2
S Pr
(1) + u 22
1=1
Pr
Σ
a4 a11
+ y
2
WB
LEG
Eieo. aperr(he, D)
<WG
--WB
WB
1
WB
2
2WG
2WG
1- 2WB TT
Wc WB
(Wo WB)
(WG WB)
Wa - WB
We WB + S [ 11
1
where we have used Markov's inequality and the fact that We WB 2 0.
We are now ready proceed with the proof of Theorem TO
Proof of Theorem 10 Before analyzing Algorithm with probability at least - 5/2 over sampling in Line have the following PAC learning guarantee
1A sttr: r: crr(h..g) = Σ ge Werre,, Dj) S EA 4
tp
Ideally, we would compute weight updates in round E [r] in Line 8 in Algorithm based on evaluating the population error err(h,, D,) for each j E [I....,k} A... to samples from each D,. In the analysis below, we show that we can effectively carry out the weight updates based on samples. This hinges on following property which follows from invoking Lemma 12: with probability at least 1 - 6/2 over sampling in Line we are guaranteed
However, we only have access
Vistenvisisk
crr(he, D2) = crr(he, S3,) T/2, err (he, Sz,) > 7/2 crr(h,, Dj) > r/4.
(2)
We now proceed with analysis of Algorithm Sacorittmmssuunn assuming Equations 1 and 2 hold simultaneously.
which happens with probability at least 1 5. The essence the proof lics in analyzing an appropriate "margin-type" loss function defined based on the majority-vote predictor F(x)
[ E6 (z) 2 1/2] and the distributions DI...., Dr. Specifically, for each distribution D,. we will analyze the following 0-1 loss function:
(. =1
Σ 1 (he, Dj) ST]-
Σ 1=1
(hr, D2) -))
This loss function considers the "margin" which in this context is the fraction of good predictors achieving error below threshold 7 minus the fraction of bad predictors which have error above 7:
Σ 1 (er Dj) S7 Σ (err(he D,) > 211 1=1
The loss function L F. Dj) evaluates to 0 if and only the margin is greater than 6, i.e. the fraction of predictors h, achieving population error err(h,, D,) below the threshold r is greater than
15

---

Observe now that when (r, 1, by definition,
al (err(he, D2) -| al [err(1e, Dj) > r] < Σ a
1=1
(1 [err(he, D,)> -| corr(h Dj) T|) + + Σ a 20
Σ (1 [err(he, D₂) 7| (err(he, P3) +
Σ a 21.
exp
Thus, we can bound from above the fraction of distributions D, for which LT, Dj) follows
as
(r,
1
Σ exp Σ a (1 (,) >] [err(h, S +
a
h
[err(h,, Σ D,)) 1 Dj) S ri)
exp
exp
1=1
1=1
1=1
< exp
θ
Σ
a
exp
Σ a (1 [err(hy, Sz,) r/2] [err(he, SI,0) S T 7/21)
1=1
where the last inequality follows from Equation Algorithm
Observe now that by the update rule in Line 9 in
(r+1 (1(5) exp Et=r a (1 [err(h, Sp,)) > T/2] 1 [err(h,, S4,) S <T22))
I1: Z.
Thus, by combining the above, it follows that
T Σ (FF S exp
0
Σ
11 2=1
Z.
8a
Zt,
(3)
t=l
t=1
where the normalization constant
d Zi
Σ
qe exp (a (1 [err(he, Sy,) > T/2] - 1 [err(hz, (5,) S T/2)))
Observe that, by Equation 2 if err(h,, Sy,) 7/2 then err(h, D,) 7/4, thus we can bound Z, from above as follows
= Z S Σ ex (1 (orr(he: Dy) > T r/4] (err(h,, = p.) + epp..
1=1
where Pt = Prymqq [err(hy: D2) > 7/4]. Next, we bound p. from above by the parameter To do this, we invoke Markov's 's inequality and the PAC learning guarantee in Equation (I).
Pt = Pri-ae [err(he, D2) T/4) Ejng [err(he, D;)1
EA 7/4
p.
7/4
Since 1 In
1-B and 1 > combined with the above, we get
Z, S (1 - p) + e p
P
p)
P
p=
p01(1111 p). p).
p
16

---

Combining Equation 3 with the above bound on Z,, we get
1 k (F,,))
s II
( 60 2vp(1 p) II
2 p)1-0p1-0.
(5)
t=1
t=1
Observe that by the bound established in Equation O and p such that
what remains is to solve for suitable values of
II 2 p)1+ 1
because that would imply 1 E L o (F. 1/k, and hence the majority-vote predictor F has "margin" all k distributions:
A1 S k Σ al (err(hs, Dj) S Σ al [err(hy. Dj) > T) _
Combining this margin guarantee and Lemma distributions, i.e., for every j [
13 implies that F achieves error at most on all
1
err(F, ar,F,D,)
Pr (r
hx(x)
*
2
1+ 1/0
We now turn to choosing p and 0 to guarantee the above.
1 (1 +1)--)
(4(1 (4(1-p) pp) 1/2 (
k
1=1
4(1 - p)) <
22/r
Observe that (1 ()00+ < for all p. E (0, 1).
Thus, it suffices to choose p, A so that
1-0
1
-
4k
(6)
p
which can be satisfied by setting
4//%/) 1/1-0)
= 2
Plugging-in in these parameters, the total sample complexity is
r. [o 11 + 1/0) (42.% V/--0
(d log
2r 5
) + k
1+0 log
2rk
To conclude, we optimize the bound above by choosing = Tlog This choice ensures that 1 + 1/0 (log(k))/)) Since - log k, we also have 0 S 1/2, which implies 1/(1 0)
1+0/(1 - 0) < + 20, Hence, (4k*/-) 1/a < (4K7th) (4 O(k2/r). This yields the
20
following sample complexity bound:
o ( 12/ log(k) (k)))
d I log(k)
k log
) 8
We sketch below alternative bounds that can be achieved by employing slightly more sophisticated variants of boosting such as boost-by-majority [SF12 Chapter 13] or recursive boosting [Sch90]. The general idea remains the same as in our application of AdaBoost, where we optimize particular
"margin" loss function defined on the distributions, but the bounds below can be favorable in the regime where is small (c.g., constant).
17

---

Claim 14 (Recursive Boosting Base Case). For any > 0 and any mixture q = (W1.... wk),
suppose that predictors h1, h2, h3 satisfy:
1. Pring [orr(h1, Dj) + p
2. Prjucp (err(hz. h2, D2) 7] S P. where 92
39c + 33c
291. qC is conditioned on crr(h,, , D2) > 7).
{j E [M]
aerrhhi D2) - r) and qı q conditioned on {j É [k]
3. Pri-a (err(ha, Dj) 7] S p. where q3 is q conditioned on
{j E [k] [errr(h1, D2) > 7] + [err D2) T|}.
Then, the majority vote predictor F obtained from h1, h2, and hy satisfies Pr cerr(E (F, D₃) > 2T| I 3p² 2p².
follows from the claim above as corollary, by choosing p 1/v 1/V4k, that only 3 rounds of adaptive sampling suffice to achieve a sample complexity of (dd/k/c) for realizable MDL.
More generally, by employing variant of Boost-by-Majority SF12 Chapter 13, Exercise 13.5], we get the following guarantee:
Claim 15 (Boost-by- Majority)) For any target for any number of rounds > 1, for any p (0, $ and a suitably chosen 0 E (0, 1), running a modified version of Boost-by- byjMoorrty (SF12 Chapter 13,
Exercise 13.5] for rounds making calls to a
:= T+ 177.0 ( A., outputs a predictor
F [ E
he(x) 2 b] that satisfies
(r,
1 r, 1p)
1 [err (F,D5) > 7] S Binom
k
To invoke the claim above, would need to solve for p and such that Binom (r, (+e) 1/k. See [SF12] Chapter 13, Figure 13.3] for an illustrative comparison between AdaBoost and Boost-by-Mo -aajortty terms of performance based on number of rounds r.
r, r, <
B Lower Bound for Realizable MDL
In this section, we prove the following sample complexity lower bound against r-round MDL algorithms. The lower bound nearly matches the upper bound in Theorem [O, and holds even for MDL algorithms that only work in the realizable setting. For brevity, we treat the PAC parameters e and 8 sufficiently small constants (below 1/100).
O(log k) and d Z (2 log k), 1(k'-1/r log(r)) there exists a hypothesis class of VC dimension d such that every r-round, (0.01, 0-01)-PAC algorithm for realizable MDL on l distributions has a sample complexity of
Theorem 16 (Formal version of Theorem - For l 2
dk dk
Ω
r log
k
In particular, to achieve a near-optimal sample complexity of O((d + +k) polylog(k)), the learning algorithm must have round complexity of Ω
Ing log log
Remark 2. While the lower bound in Theorem
16 is stated for a constant accuracy parameter (i.e., dk2/r
0.01) for brevity, it is easy derive an C argument. We start with the construction for Eg 0.01. Then, we obtain a new MDL instance by "diluting" each data distribution by a factor of 100c: we scale the probability mass on each example by a factor of 100c, and put the remaining mass of 100c on "trivial" example (1,0), where is a dummy instance that is labeled with O by every hypothesis. Learning this new instance up to error e is equivalent to learning the original instance (before diluting) up to error e e/110ee = 0.01 = eg- Intuitively, the exumple (1. 0) provides no information, and the learning algorithm has to draw e) samples in expectation to see an informative example. This leads to a lower bound with an additional factor.
glog= lower bound for general via standard
18

---

B.1 Intuition
We start by explaining the intuition behind the construction the hard MDL instance. For simplicity, we start with the 2 case and sketch the proof of an ()(vk)) lower bound.
Hard Instance against Two-Round Algorithms We will consider the class of linear functions over X' Fg, namely, the hypothesis class
Ha. = hw w 12) where bi x FL w 122.
The ground truth h- is drawn uniformly at random from Hd.
To construct the & data distributions, we will randomly choose difficulty levels diff diff ..fff diff& such that Σ Li=1 diff; S d. (We will specify the distribution of (diff ) later.) Then, we randomly choose subspaces V1, V2, ..... Va S Fi such that: (1) dim((V)
diff,; (2) dim(Span(Vi U V/2 ... .v)) = Σx= diff,; (3) The k-tuple (V1, V2...., V&) is uniformly distributed over all possible choices that satisfy Constraints (1) and (2). Finally, each D; is set to the uniform distribution over V,.
remains to specify the choice of diff, through diff Let do and kg be integers be chosen later. We will choose diff diffi..... diff to be a uniform permutation of: (1) 1 copy of do: (2) Vko copies of do/ / Ko; (3) 2 0i copies of do/ ko. For this to be valid, we need
I + ko + kD S k and 1 do + v ko da/ / ko + k do/ ko S d,
both of which can be satisfied for some do = (dd) and Ko ((k). In the following, we will drop the subscripts in dy and ko for brevity.
deter- Two-Round vs. Three-Roumd Algorithms Given labeled examples ((r,, [e())
mine the value of ht" (x: for every x E Span(f21, #2. ........... Fm }). Since the prior distribution of h* is uniform over Ha. for every a E F Span([r1, 22,...,......................... Tm }), the conditional distribution of h (ar) uniform. Intuitively, this means that, for every such instance x, we cannot predict label better than random guessing. Therefore, to learn a classifier with error < 0.01 on Dj we must observe diff, linearly independent instances from Vg. In particular, we must draw at least diff, samples from D;.
Suppose that the learner were allowed three rounds of sampling. The following is natural algorithm:
Draw d/k samples from each distribution. This allows us identify the distributions with diff, = d/k as well as to find an accurate classifier for each such distribution.
From each of the Vl distributions except the one with diff, = d.
remaining distributions, draw d/vk samples. This satisfies all
Finally, draw = d samples from the only remaining distribution.
Note that each step draws (d) samples, so the total sample complexity is Od)).
If only two rounds allowed, the learner must "skip" one of the three steps above, and use either of the following two strategies, both of which lead to ((dvk) sample complexity:
Strategy 1: In the first round, draw ss d/ V samples from each of the k distribution to identify the only distribution with diff; = d. In the second round, draw &s d samples from the remaining distribution.
Strategy 2: As before, draw ss d/k samples from each distribution to identify the distributions with diff; > d/ dk. Then, there are still Vi 1 "suspects" among which one distribution has difficulty level diff; = d. The learner must draw z samples from each of them in the second round.
Hard Instance against r-Ronnd Algorithms For the general case, we set a = k2/r, We extend the construction above such that diff, through diff, is random permutation of
rig = A copies of dg = drkr).
71 k/a copies of di ad/ (rk).
722 k/a² copies of d2 a (rk/).
19

---

ny 1//aa
copy of = copy a'd/(rk) = d/r.
As long as < logg k. we have k2/r 2, which implies that ri.,.... ...,,........................... decreases geometrically, follows that
no + n1 + n2 S 2k and
n4 d. - -r (d/r) S 2d.
Thus, the above would give valid instance after scaling every n. down by a factor of 2.
Again, (r 1)-round learner would spend O d:-1) O(d/r) samples in the i-th round to learn the distributions with difficulty levels I d;-1- Then, there are only O(n;) remaining distributions, each of which has difficulty level d,. The sample complexity is thus (d/r).(r+)) O(d).
When the learner is only allowed rounds of adaptive sampling, intuitively, the learner must "skip" one of the r + 1 rounds outlined above. Suppose that, for some E [r]. the learner decides to draw ((d,) samples from each of the ((n,-1) remaining distributions, in the hope of learning the distributions with difficulty levels both d and d,. Note that the parameters n, and d, are chosen such that 74-1- dj = dk2/r/r /r, so the learner must incur a k2/r blowup the sample complexity.
B.2 Towards Formal Proof
To formalize the intuition outlined above, we slightly modify the construction into a k-fold direct sum of single-distribution version.
Random MDL Instance I Let a = k2/r, For some dg 2 k. let Ddiff be the probability distribution over [do] such that Ddif (do) and
(d a='
a² a
Ddiff
Vi E [r].
k
Here and in the rest of this section, we abuse the notation Ddif for its probability mass function. We also assume for brevity that do/a² is an integer; if not, the same proof would go through after proper rounding. Note that
do at a
(r+ do
E
diff
diff ~ Dun
Now define distribution over MDL instances with & distributions.
Definition (Multi-distribution instance). Given do, k, and a sufficiently large d = ((do log k), we construct MDL instance I follows:
Independently sample diff,, diff2..... .... diff Ddiff Repeat until Σ diff, S d.
Sample subspaces Vi, V,,..., V& C Fd uniformly at random, subject to dim(V,) diff, and dim(Span( V1 U V/2 -... VV)) = Σ diff,
Let I be the MDL instance the class Hy of linear functions over F where the i-th data distribution D; is the uniform distribution over V4, and the ground truth classifier At Ha is chosen uniformly at random.
Random Single-Distribution Instance T' We also consider a closely-related single-distribution version of the problem, where only one difficulty level diff is sampled from diff Definition 3 (Single-distree dintribuitt instance). Given d > dg 2 1 and distribution Ddiff over [do], construct the single-distribution learning instance I' as follows:
Sample diff ~ difff and a uniformly random diff diff-siimnsiinal subspace V C Fy..
Let I' be the realizable PAC learning instance on the class H. of linear functions over Rd. where the data distribution D is the uniform distribution over V, and the ground truth classifier ht Ha is chosen uniformly at random.
20

---

Roadmap
We prove Theorem 16 by combining the following two technical lemmas:
Lemma 17
An r-round, (0.01, 1...0011PPPCCCC MDL algorithm with sample complexity M can be transformed into an r-round (0.02, (11K)))-PAC algorithm for with sample complexity bound (((M/k) log k).
Lemma 18 An r-rouud,, in expectation.
algorithm for I' must draw ((dokk//((kk)) samples
Lemma 17. For any do 2 k N 1 and S S (llog k). if there is an r-round (0.01, 0.01)- PAC MDL algorithm A with sample complexity M on k distributions and hypothesis classes of VC-dimension d = (dd log k), there is another r-round algorithm A' such that:
On a random distibiiittiittionn instance I' (Definition 3) A' learns an 0.02-accurate classifier with probability at least
100K
On random dintie-distribution instance I', A'' takes (((M/k) log k) samples in expectation.
The probability and expectation above are over the randomness in instance I', the learning algorithm A', as well as the drawing of samples.
Lemma 18. Suppose that k Z 1, r. S O(log k) and do 2 ((k21// logr)} If r-round learning algorithm outputs a 0.02-accurate classifier with probability 2 100k on random instance I' with parameters (do, k. r). A must take ((dok"/r (rkk)) samples in expectation.
Proof of Theorem 16 assuming Lemmas 17 and 18 Let do (dd/ log k). The assumption that d > max{{2(( (S2(k log k), 12(k111/r log( kk) log(r))} ensures that do h and do z Q(k1-1/r log r). Suppose that AA is an r-round, (0.01, P MDL algorithm with sample complexity M for distributions and hypothesis classes of VC dimension S d. By Lemma [7, there is another algorithm A' that, on a random instance I' from Definition 3 returns O. 0.02-accurate classifier with probability Took and takes ((MM/H ) log k) samples in expectation. By Lemma 18
least 1
we have
0
( M k
log k:
2 Ω
dgkh//r
)
dk./rr
rk
rk log k:
It follows that M 2 Ω
d/ <log*
B.3 Proof of Lemma 17
To prove Lemma 17 suffices to show that we can solve a random single-distribution instance I' (from Definition 5) by running an MDL algorithm A in black-box way. Naturally, we plant I'' into an MDL instance I with & distributions (from Definition 2) solve instance I using A, and use the output of A to solve the actual instance I', While the idea is simple, some care needs to be taken to carry out this plan correctly.
First, we draw i' uniformly at random from [k], and let the i*-th data distribution in I correspond to the distribution I'. For each E [K] \ {i*) we draw diff, from Ddiff independently. Let Vi, denote the subspace of F& corresponding to the task I', where == O(do log k) is the ambient dimension. diffendaimniionall subspace V; to construct the MDL instance. This ensures that (V1, Vz,... V&) form a random MDL instance (from Definition 2 in which the & distributions are symmetric, obstacle is that we cannot construct Vú for i + i" without knowing the subspace Vo.. In particular, knowing V, or just the value of dlm(V, ) would make the single-distribution version too easy.
Intuitively, for each ش it, want to sample
that the identity of i" would not be revealed. Here,
Our workaround to slightly modify the definition of the single-distribution task. We allow the algorithm for the single-distribution instance to speciffy an integer mo 2 0 at the beginning. Then, the algorithm receives my vectors in Fg chosen uniformly at random subject to that, along with any basis of Vi., these mo (tim(Ve) vectors are linearly independent. Intuitively, the algorithm is provided with information about the "complement" of V₁, in Fd, which allows it to construct the k fictitious subspaces [Vi and thus an MDL. instance on distributions. mg diff,- = d dim ). the learner fails the learning task immediately. Note that we cannot simply give all the d - diff.- the learner would know diff.-, which makes the single-
vectors to the learner distribution instance easy.
21

---

Proof of Lemma 77 Let I' be a dingle-distribution instance generated randomly with parameters lt
and dg according to Definition? 3 Recall that the hypothesis class Ha. where d = (dg log k) is the ambient dimension. The data distribution D is uniform over an unknown subspace V S F2 with an unknown dimension diff ~ Ddift.
We consider the following procedure for solving I' using the given algorithm AA:
Draw from [k] uniformly at random. For each E [k] \ (i*). draw diff; independently from Ddiff
Set mo = SiEMNN (2r) diff,. Request mo random vectors in F3 that are linearly independent the unknown subspace V. In this step, the algorithm might fail due to my > diff,-, where diff,- is the unknown difficulty level of the Ainle-distribuut instance I'.
Use these vectors to construct diff,-diimenional subspace V; for each i [k] (i*). Let D, be the uniform distribution over V4.
Simulate the MDL algorithm A on distributions D1, D2.... DR, where D;- is the alias of the data distribution in instance T'. In addition, when A draws the first round of samples, we draw (log k) additional samples from D,- form validation dataset.
When A terminates and outputs classifier h, check whether has an error I 0.01+00.02 on the validation dataset. so, output h as the answer; otherwise, report "failure".
Let _4sim denote the algorithm defined above, In the following, we will show that: (1) 4 can be implemented using A as black box; (2) A solves instance I' with good probability; (3) .4sim does not draw too many samples from D.
Details of the Simulation When , simulates algorithm A. it maintains set S; C F2 x F2 for each i + i", which is empty at the beginning. Whenever A requests samples from Di., A A draws from 1) and forwards the labeled examples A. When A requests sample from D; for some i * it, .Assm first draws x ~ D.. If x lies in Span( E By (x,y) E S, By E F2)), A computes the unique label y E F2 such that (I, y) remains consistent with the labeled examples in S;; otherwise, _Assm draws random y to A, and then added to the dataset S.. By doing so, we defer the randomness in the ground truth classifier ht, namely, we realize bit of information of h² whenever this information is needed to determine the label of an example.
(1nnoulli(1/2))) The labeled example (z, is forwarded
Equivalence To analyze the performance of Asiim, the key observation is the following: Condition ing on that A does not fail when requesting the mg vectors, from the perspective of the simulated copy of A. it is running on random MDL instance I from Definition 2 This is because conditioning on that A does not fail has the same effect the conditioning Furthermore, both the marginals of Dj through Dr RY and the choice of the labels identical to those in the definition of I.
Σ diff, S d in Definition 2
Boost the Success Probability Since A (0.01, 0.01)-PAC, it holds with probability 2 0.99 that its output h is 0.01-accurate classifier for each D;. In particular, h is 0.01-accurate for distribution D = Drr, and thus a valid answer for instance I'. However, this only guarantees a success probability of 0.99, falling short of the desired 1 1/(100)).
Fortunately, suffices to run | O(lo k) independent copies of algorithm A' to boost the success probability. Note that these copies must be simulated in parallel, so that the resulting algorithm still takes rounds of samples. Furthermore, we share the vectors requested at the beginning of different copies of A', so that the number of vectors that we actually request, ma. is the maximum realization of Ex diff, over the simulations. Whenever one of the simulations outputs a classifier h. we test it on the Size-O(log k) validation dataset and verify whether its empirical error below 0.014-0.0
2
We output h as the answer to I' only if it passes the test. Let A' denote the above algorithm.
22

---

Correctness of A'' Now, we analyze the probability that A'' fails to output 0.01-accurate classifier for I'. There are three possible reasons:
Reason 1: mo > d d diff This happens when Σ diff, > d holds in one of the copies of _.ssmm. Note that in each fixed copy of A diff1, diffz..... 2..... diff, independently follow Ddift Recall that Edif- Da# [diff] O(rdo/K and (dg log k). It follows from multiplicative Chernoff bound that Σx= diff; > d happens with probability 1/ poly(k), which is still < 1/k after union bound over the I (log k) copies.
In more detail, let random variable X; denote the value of diff, / Since D is supported over [dol. X; E [0, 1]. Furthermore, E [X,] Biff- [diff do] O(rds/ (trd//k)/dd / Orr/k). Then,
1 X; is the sum of random variables in [0, 1] and has an expectation of μ == k: ((r/k) =
Assuming that = (log k) holds with a sufficiently small constant factor, we have μ = 0(r) S
In k. Let 8 (5 In k)/u 2 4. Also recall that d = ( log k), so we may assume d/do 2 5 Then, we have
Pr Σ diff, d Pr
X X
d/do
I Pr
Σ i=1
x,
5l = Pr
Σ X; > (1 (1+8)
A multiplicative Chernoff bound gives
821r 1 (-2+
(-
20pu
811 k
Pr Σ x; (1+ x1+ 8)ا0 S exp
S exp
S exp
<
3
k
where the second step applies 8 2 4 and the third step applies 8/s = 5 In 1 2 In
Reason 2: None of the simulations succeeds. Note that conditioning on the realization of instance I', the copies of the simulation are independent. Furthermore, since A is (0.01, 0.01)- PAC, each copy fails with probability & 0.01. The probability for all / = O(log k) copies to fail is thus most 0 < 1/k.
Reason The validation procedure fails. We need to validate at most = Olog k) classifiers that are generated independently of the validation set. For each classifier h, we need to distinguish the two cases err(h, D) < 0.01 and err(h, D) > 0.02. By Chernoff bound and the union bound, the validation of size Olog k) sufficient for upper bounding the failure probability by L. Oglog k) S 1/ poly(k) (k) < 1/k.
Combining the three cases above, for all sufficiently large k, the total failure probability is smaller I_. than 1ODE In other words, algorithm A' outputs 0.01-accurate classifier with probability Took on a random single-distribution instance I'.
Sample Complexity Each of the / O(log k) simulated copies of A draws at most M samples from Dj through D2 in total, as each simulated copy of A effectively runs on a valid MDL instance. Furthermore, from the perspective of each simulated copy of A, the distributions Di...., Dy are generated symmetrically, so the expected number of actual samples drawn from D;- = D is at most M/k. Therefore, the 7 copies of A together draw (M/k) I O(M//k) log k) samples in expectation. Note that this dominates the Olog k) samples drawn for the purpose of validation, so the overall sample complexity of A' is O(M/k) log k).
B.4 Proof of Lemma 18
It remains to prove sample complexity lower bound for solving the single-distributin instance I' from Definition 3 within r rounds. Recall that I' is defined as the task of learning linear functions over the hypercube of dimension d = (dg log k). and the data distribution is uniform over random subspace of dimension diff ~ Ddiff Also recall that = k!/r 2 2, Ddift (do) = i and Difff (do/a') ) (a' - -a'-l)/k for every i E [r].
23

---

Proof of Lemmal 78
Suppose towards contradiction that there exists an r-round learning algorithm such that outputs 0.02-accurate To0rk samples in expectation.
A for the lungledistribution instance T' defined in Definition 3 classifier with probability 1
- and takes most
ado
1ODE
Typical Events Consider the execution of A on the random instance I', We introduce 2r + 1 "typical events", which will be shown to happen simultaneously with high probability:
Event Eg Enum: Let random variable Mo denote the value of mg, i.c. the number of lincarly indepen- dent vectors requested by A at the beginning. Egum is defined the event that Mo d do.
Events Equm, .E2 E,u For each i E [r], let random variable M; denote the number of samples that draws in the i-th round. E, Enum is defined the event that M; I a'do 4/:
Events eiro, 0 ......, gird. For each i E [r], gind is defined as the event that, among the labeled examples that A draws in the first i rounds, all the instances (namely, the vectors in F2) are linearly independent.
For i E {0, 1,...,, r) we use the shorthands
& Euum n n&n E .... Eg and
Egg
gind
cind E1
cind n... gind
Moreover, we shorthand _:ll for the event diff a'
Induction Hypothesis We will prove the following statement by induction on i: For every i E (0.1....,77 r) and every i* E ( .T,, holds that
Pr cnum ne E 0.99
4i
(7)
25r
We first show that the above leads to a contradiction and thus proves the lemma. When i = r, Equation (7) reduces
Pr @num
gind
diff do} 2
Recall that k1/r 2 2. Thus, with probability 1/2 conditioning diff do. draws
ado
ad
a" do 2- a do do
Σ M.
4k
4k
4k
samples in total. Then, over the remaining randomness the ground truth classifier h* Ha. the correct label of every instance outside the span of the observed instances is still uniformly distributed over {0. 1). In particular, regardless of how A outputs a classifier, the error of the classifier is at least (1 - 2] do 2 in expectation. By Markov's inequality, the conditional probability of outputting classifier with error < 0.02 is most
(1 (1-21du/) 2ldo/21--dp //2
1.02
5"
Therefore, the probability that A fails output classifier with error < 0.02 on random single- distribution instance I' is at least
1 1
Preift-Dan [diff = do] Pr [Eaum n ginn diff do]
2
100k
contradicting the assumption on A.
The remainder of the proof will establish Equation 7 by induction.
Base Case
We start by verifying the base case that = 0. namely,
Pr Mo I d do
editt &
> 0.99, Vi* (0.
Note that A chooses My before drawing any samples, so Mo is independent of diff. Suppose towards do] 0.01. Then, we have
contradiction that Pr [o
1 1
Pr [Mo do A diff dol = Pr [Mo
dol Proif- [diff dol 0.01
k 100k
Moreover, when both Mo > dg and diff dg hold, A would fail due to M, > d diff. This shows that the failure probability of AA is strictly higher than 10og a contradiction.
24

---

Inductive Step: Event &uum Fix i E [r] and i" E fi, f1,i+1,, 1, r). Suppose that the induction
hypothesis (Equation holds for - 1: shorthanding goood = E Si- j E {a 1.i.....77 } that
n gind
Si-1 it holds for every
Pr
goood
editi
0.99
4(i 1)
1
25r
In the following, we condition on goood and E and aim lower bound the conditional probabilities of events Equm and gind.
We observe that, conditioning on ggood, the labeled examples that A draws in the first i-1 rounds are conditionally independent of diff. In partieular, the conditional distribution of M; goood identical Egood]
to that of M; (g9ood n Editt). Then, we note that E have
[M;
S
a'da must hold; otherwise, we 50rk
addo
E
M
E
M
goood]
Pr [goood]
Pr [E
50rk
Furthermore, the induction hypothesis implies
Pr ggood]
Pr
ediff
Pr
ggood
Edlffi
a diff
do
Pr
k
j=i-1
1
1-1 do a²
diff
2
2nx
would then follow that contradicting the assumption that A has an expected sample complexity of at most T0UPE
a do
ado
E
[M,]
50rk
20²-1
100rk'
ado
Thus, we have E
[M; goood
n g
IE
M; ggood]
a'da 50rk
Markov's inequality then gives
a'do
E
Mr goood n EdiM
a'du/(50rk) 2 25r
Pr
M₁
Egood
n Edit
I
4k
a (4k)
a a'do/
Therefore, we have
Pr
enum n ggood
ediff
2 Pr
ggood
ediff Ci+
Pr
gnum
ggood n ediff
4(i
1)
2
4i - 2
0.99
2 0.99
25r
25r
25r
Inductive Step: Event gind Now, we condition on event Enum Egood n & and aim to lower bound the conditional probability of gind After the conditioning, it holds that
adg
a²do
a a'do
a'do
a do
M1 + M2
M₁
diff/2.
4k
4k:
4k
4k
2k
Regardless of the N = M1 + M2 .... + Mi- samples that draws in the first rounds. the probability that the next instance falls into the subspace spanned by those N instances is at most d-iff By the same argument, for every
{0, 10. M, 1}. after samples have been drawn in the i-th round, the next instance is outside the span of the first N + instances except with probability ++++) diff By the union bound, the M, additional instances in the i-th round are linearly independent together with the previous N instances. except with probability
2 N diff + + 11)+1idiff diff
+ (; diff < 2 N M; -iff diff
< 2diff/2 diff 2 dift/2
25

---

Recall that diff d' it holds that 2-diff/2 <
oda gー- Therefore, for all sufficiently large do 12(1-- log r).
i
It then follows that
25r
Pr
gind
&qui
goood
Ediff
2
25r
which further implies
Pr
chum
sind
Edit
Pr
n ggood
Pr
glnd
goood
n Edit
4i
2
4i
0.99
2
0.99
25r
25r
25r
This completes the inductive step and concludes the proof.
C Upper Bounds for OODS
We analyze the correctness and the round complexity of the LazyHedge algorithm (Algorithm 3 We then show how the ideas in both the algorithm and its analysis be easily transferred the agnostic MDL setting, resulting in an algorithm with Ö(Vk) round complexity and near-optimal sample complexity.
Algorithm LazyHedge: Hedge with Lazy Updates
Input: Number of dimensions k, number of iterations T
step size = O(s).
22
margin parameter C' >>> 1, and access first-order oracle of f. Set w (1/k, 1/k, ..... 1/k) and m (0, (0,)....,0) 0). do
2 for f = 1.2, .........7 T.....TT
(t) E ((w((-1) then
Set wt(t) = (1-1))
else
Set ((
max { w (2) _n!
10 for every E [k).
Start a new OODS round with cap ((().
Query the first-order oracle to obtain supergradient (1) Vs(w()).
Compute w(++1) A such that for every E [k],
w (t) 00
(t+1)
w
Σラ=1 w (1) (0)
Output: Average weight vector 1 ΣT w(!)
C.1 Proof of Lemma
Recall that Lemma states that LazyHedge finds an O(s)) maximizer of f on 4-1
Proof of Lemma The standard regret analysis of the Hedge algorithm (e.g., MRT18 Theorem
8.6]) gives
T
T
())
2 max [
(r(t))
ex)
R
[ml
where R =
luk 17
rT
0
logk
Let w
A 1-1 be maximizer of f over k-1 Then,
T
(t) w²)
< max
(1, es)
(t) w(()) + R.
2e M
26

---

Rearranging gives E(=1 (r(1) w¹ - -w!)) S R. Since f is concave and r()) E vf(w!!) for every
t e [T], we have f(w") S f(w(()) + (r(t), w - w(t)). It follows that
T Ei(ww)) [[( Σ
r
(1, " -w( R.
Dividing both sides by gives
1 T
[ww)
Σ (w(lt S T - 0(e).
T
1=1
Finally, applying the concavity of f again gives
1 ((0) s
witt
(wll9) 2 -(e))
= max ((w) O(e).
T
T
wEA
1=1
1=1
C.2 Upper Bound for the Box Setting
We formally prove Lemma which states upper bound of min {k, O((k/C) log (k/e)) (logg k) on the round complexity of LazyHedge in the box setting. The proof proceeds in the following three steps. First, whenever the cap is updated in LazyHedge, to this update and call it the culprit of this cap update. Then, we show that every an index can become the culprit of at most (loge k) cap updates. Finally, we control the number of indices that become the culprit least once by min O(k//C)) log (k))))) so the lemma immediately follows.
find an index i that leads
Proof of Lemmal 7 If the cap is updated in the t-th iteration of LazyHedge, i.e., w/(t) + w((-1)), by definition of Algorithm 3 it must hold that (t()) & (w By definition of the box setting, there
exists i [k] such that w (t) > >= w(--1), We call the smallest such index the culprit of the cap update in iteration f. For each i E [k:]. we define
T, = (1 [7] i is the culprit of the cap update in iteration 1).
Then, the round complexity of LazyHedge is exactly Σ [T].-
Every T/ is Small We show that |T| I Olloge k)) holds for every i [k]. Fix i [k] and let t < to < < tm be the m = |Ti elements of T in increasing order. For each j E [m], let aj = maxigigi, wi denote the maximum weight the i-th coordinate among all weight vectors up to time fj- Fix j Recall that, at iteration - the cap w(()-1) is updated such that
Since i is the culprit at time ij, it holds that aj 2 w((s) > w.
(ts C max { (w.h) w w
1) C. a0-1-
Moreover, LazyHedge ensures that w/") is non-decreasing in t. Therefore, we have
C.a (t $ w/ (ty-1) < S.j-
follows that am 2 Cm-laa 01. Since 01 2 w (1) = 1 lk and a. S 1, we have m 1 S
loga(am/aj) & logg k. which gives [T. m 0(log k).
Only a Few T.s are Non-empty The number of indices i [k] such that To * 0 is trivially upper bounded by k. Next, we give another upper bound of O({:CC)- log (k/=)). Fix E [k]. Suppose that T; non-empty and let & be the smallest element in T. Either one of the following must be true:
t = 1. This can only hold for i 1.
27

---

f1 > 1. By definition of Algorithm 3 the cap is set to w(l) = D/k,../ C/K) in the first
iteration. For index to be the culprit at time t we must have
W
(41)
i (1)
= C/K,
which implies maxigieT i 2 C/k. k. By Lemma 3 at most
Σ Zi=1 Ei=1 maxIsIST
Ollog((//e))
C/k
different indices can satisfy this condition.
Thus, the number of non-empty sets T; is at most O((k/C) logo/////// (k/E)).
Putting everything together, the round complexity of LazyHedge is given by
Ti <
Σ
O(loge k) S min {k, O((k/C) - logooo/ (k//))) O(logo k).
C.3 Upper Bound for the Ellipsoid Setting
In the ellipsoid setting, we have an improved upper bound Ö(VF) on the round complexity of LazyHedge.
Lemma 19. For any e [4, k). LazyHedge takes Ol OlVk/C log (k/E)) rounds in the ellipsoid setting.
Again, combining Lemmas 6 and 19 immediately shows that the ellipsoid setting of OODS be solved with an OCC) sample overhead in ((Vk/C) rounds.
Theorem 20. For any C E [4, k), in the ellipsoid setting, LazyHedge finds an a(p)axppriiimate maximum with an OC'log (k/s)) sample overhead in O O(vk/C log" (k/e)) rounds.
The proof of Lemma 19 is significantly more technical than that of Lemma 7 We classify the cap updates (except the one in the first iteration) into two types: A "Type I" update is when some coordinate exceeds 1 /k/C, and a "Type II" update is one without significant increase in any of the coordinates. We bound the number of Type and Type updates by Ö(Vk//C separately.
The upper bound for Type I updates is a simple consequence of the polylog(k/e upper bound on the Hedge trajectory shown by [77C+24] (Lemma 3 This bound implies that there are at most Õ(1) Vk/C Type updates where the coordinate reaches R 1/ /k/CC, at most Õ(1) /2/C/2 Type I updates where the coordinate reaches Rs 2/ / /k/C. and so on. These upper bounds sum to Ö(Vk/C).
The analysis for Type updates more involved. Roughly speaking, we say that a coordinate E [k] gains potential of a² /b when it increases from b to through the Hedge dynamics. Then, we prove the following two claims: (1) Each Type update may happen only if Q(1) potential accrued over all k coordinates; (2) The total amount of potential that the & coordinates may contribute to
Type II updates is most ((yk:((/ /k/C). Combining these two claims proves the Ö(vk/CC upper bound on the number of Type updates.
Proof of Lemma 19 Consider iteration 1 E (2, T} of LazyHedge in which the cap is updated, i.e., w $ O(w(t-1)) D)) By definition of the ellipsoid setting (Definition 1). we have
1.
Let I = (i [k] ( 2 w. ([( /2) denote the set of significant indices on which the weight
w exceeds half of the cap :. (1-1) Let
insig
= {i [k] w." !!! ((-1)
/2/ [k] I be the set
28

---

of insignificant indices. Then, the contribution from insignificant indices to the left-hand side can be upper bounded:
2
Σ
2w
(2)
2
VEI,"
where the first step applies i Z Therefore, the contribution from the significant indices is at least
Wi
(1-1)
2w
(1)
and the last step applies w(t) A
12
1
2
2 2
VEI
VEZ
We say that the cap update in iteration is Type if there exists an index E I, such that
max { (w W w W (1))
Vk/C
otherwise, the update is Type Let S [2] and S [T] denote the iterations in which Type I and Type II cap update happens, respectively. Then, the round complexity is simply [Ti| + [72l 1, where the ++1" accounts for the cap update at 1, which is neither Type nor Type
Number of Type I Updates We further classify the Type cap updates (in TT) into Ollog k) sub-types. For each integer j E logz Vk/C1, let Ti, denote the set of pairs (t, E Ti x [k] such that: (1) A Type cap update happens in iteration t; (2) I is the smallest index such that
(8) max { w!m m w
(1)
(2)
2 1/Vk//;
(3) It holds that
(1) (2)
!1)
2
20+1
max
w w
w
VkyCC Vk/C)
Then, it remains to control the size of each Ti.j.
We first argue that only few indices [k] may appear the second coordinate of (1, i) (lpiir in Tijj- Indeed, (lo, i) E Ti.j. we must have maxigieT (1) 2 maxigrgto (1)
VK/C Recall
from Lemma that Σ* maxicigr w!") O(log (k/=)), the aforementioned condition hold for at most 2 O( /k/Clog" (e/Cel))(k/e)) different values of [k].
Then, we argue that no Ti.j may contain two pairs (f), and (t2, for t # t2. In other words, no index i contribute to the same sub-type j twice. Suppose towards contradiction that for some I < l/ and E [b). (), (42,1) E Ti.. By definition of Tıjj maxigest, w 2 2 22/kk/CC Then, by the cap update in LazyHedge, have
(e)
2
(bo 1)
(1) w.!t) =C. max w 2 C. 1sthh
Vk/C
On the other hand, since (12 Ti.j. we have i I which further implies
(l2-1) C 2
2/+1
(12)
u 2 2
VkCC
Vk/C¹
where the last step applies C 2 4. We then have maxiçisi, w 2 wita) 2 / which contradicts (t2, i) E Tı.j-
Therefore, the number Type updates is at most
llog, Vk/C Σ
[loga / k//C
Ti
2 OLKK/Clog = O( O(Kk/Clog"(k//))
29

---

Number of Type II Updates: Overview
Recall that if a cap update happens in iteration t 2 2, we
have Σ 1:
2' Summing over E T2 gives
10
ΣΣ TETRIET!
T2
Next, we upper bound the double summation on the left-hand side of (8) by changing the order of summation. We will show that, for every [ki], it holds that
W 12
Σ
min
A C
max ISIST
(9)
tET2:
Furthermore, we will upper bound the sum of the right-hand side of (9)
follows:
Σ min
k
max
w!th)
1 s OlVk/Cllkooo (k/e)).
(10)
C
ISAT
Then, combining Equations
through (T)) immediately gives [ S OlVk/Clog (k/e)) and and (TO) in the remainder of the proof.
completes the proof. We prove Equations
9
Proof of Equation 9 Towards proving Equation
(). we fix E [A:] and list the elements in T2
that satisfies E I in increasing order: 2 < ti tz < ... fm S T. We write to 1 and
aj = maxigist, w, for every j E {0.1,...,m]
We first upper bound the left-hand side of in terms of (az) For each E [m]. we have
(t) m (t)) < max ii;
0j and w (1-1) 2 w.
(15-1) C. max
w (t) C aj-1-
Iststz
15tst--1
Then, each j E [m]] contributes term of
(ty)
a3
d
C.
aj-1
C
aj-1
a?
the left-hand side of (9) Thus, it suffices upper bound
aj-1
Next, examine the sequence (ag)) Fix [m]. Since Inje
we have
aj (1))
1 (4,
11)
(1--1)
w
w
2
The cap update at time 1--1 ensures that
(ty (15-1) C
(1) C ajj-1
:
max 1Stst,-1
w
Combining the above and applying the assumption that C 2 4 gives aj 2 aj-1 20j-1.
The sequence (a, (o)) starts with ag = w (1) 1/k and ends with am max w Moreover, since the cap update iteration fm Type and E I holds that
(0)
max 15tstn
W
Vk/C
(0) maxisesT w Vk/C
Therefore, we have the upper bound am <
min
In summary,
(oo, O1,...,, am) is a sequence of positive numbers such that:
aj 20j-1.
30

---

du 1/k and Om S min
max wi
(t)
vk/C
For any positive numbers a, b, that satisfy a/b and b/c 2 have
a²
3
0
a² (a/2)² a² 6²
4
Rearranging gives a² may repeatedly remove the elements 1m-1, 1, am- 22n-2;-- 2...,, 01 one by one. By doing so, the invariant aj/a,-1 2 is always maintained, and the value of Σ a /2jaa11 never decreases. Therefore, have
d 5 < c.
Therefore, starting from the sequence (4o, .1..... am), we
Vk/c })
2
min maxi SIST w.
(9)
m
a
max wn!() ISST
2 :c.
min
k
a0
1/k
Recalling that the left-hand side of (9) most 1 C
as-1" we have proved the inequality.
Proof of Equation (10 For each integer j [0, logg ke.
2
2 k
I = E [k] max w.
E
151ST
denote the set of indices E [k] on which the maximum weight over the T iterations is roughly Then, the upper bound Σ maxigigT w!" < (O(log"(k/e)) from Lemma implies [Iy| S
2
//. /k.
2 j. Oak (o///l)g))))) (k/s)). Note that Io. II..... I form a partition [k), so we have
min { {c
Mlgg k] 2 1
max ws! 1SSS
.
Σ min
[
max we SIST
(t)
.1
j=0
YEI
Mona A1]
k
21+1
[z,l min
1
C
k
)=
[oog
kk
/2++1
s Okk (k//))
2- min
1
C
k
where the second step follows from E I3
- maxigigT 1
!
< 2/+1 and the third step
applies the upper bound [zyl < - Olklog" ((k/e))
The summation Σl1og= A1
2 min
1241 x
1 is further upper bounded by
+00
2 Ck
0(1)
min
2-
0=
The summand min { 2' 2- is given by the first term and thus geometrically increasing when Ck
4 < Ck. The summand geometrically decreasing when 4 2 Ck. Therefore, the summation is dominated by the term at j = [log, namely, 2- = 0 ((//CC)). Therefore, we have
1 < O(k (og (k/e)) 0(I/VCk) O Og/k/Clog
min
k
max wi ISEST
(1)
111
This proves Equation (0) and completes the proof.
31

---

C.4 Applications to Multi-Distribttion Learning
We sketch how our proofs of Theorem g and Theorem 20 can be easily adapted to give MDL
algorithms with near-optimal sample complexities that run either O(k) or O(vi) rounds. We prove these results by modifying algorithm of (ZZC+24) which we briefly describe below. We refer the reader to (ZZC+24] Algorithm 1] for the full pseudocode description.
The MDL Algorithm of IZZC+24 24 Let H be the hypothesis class with VC dimension d. For
brevity, treat the failure probability 5 as constant, and use the O(-) and (()) notations suppress polylog (kd/e) factors. The algorithm maintains & datasets S1, S2..... Sk. where each S, contains
training examples drawn from the i-th data distribution D,. The algorithm runs the Hedge dynamics
for T ((log k))=²) iterations starting w(!) (1/k, 1/k, ................................ 1/k). Each iteration t E [T] consists of the following two steps:
ERM step: For each [k), draw additional samples from D; and add them S, until
S 2 w!" - k))=+)
Then, find hypothesis 10(0) E H that approximate minimizes the empirical error
k
L(h)
[h(x) * yl.
(s.,))
which is estimate of the error of h on Σx=1 w (1) Di-
Hedge update step: For each i draw i ((k) fresh samples from D, to obtain estimate
of the error of (0()) on D.. Compute (t-1)) from w(()) and y:(1) via a Hedge update.
The crux of the analysis of [7C+24 to show that the dataset sizes in the two steps above sufficient for finding sufficiently accurate ERM (1() well as computing the loss vector ((()) that is sufficiently accurate for the Hedge update.
Note that straightforward implementation of the algorithm needs T = ( k)/=²) rounds of sampling. While this round complexity is logarithmic in k. has a polynomial dependence in 1/e. In the following, we apply the ideas behind our OODS upper bounds to improve this round complexity (kk) and then O(Vk), which is lower than (log k in the < 1/k1/4 regime.
Ökk) -Round MDL from Theorem 8 The LazyHedge algorithm (Algorithm suggests a natural modification to the algorithm of +4): To ensure |S 2 w!!h (()++))ee instead of drawing additional samples at every round, we maintain a cap vector ()()) E [0, 1] We ensure the invariant
that, at the end of every iteration I, holds for every E [k] that [S] w
(4) e((d + k)/s²).
< T w (t-1) already holds for every i E [k]. we use the current datasets to perform the ERM step. Since |.ai] 2 wi (-(11) ē((d + k)/=²) 2 w!" ē((d + k)/e²) holds for every E [k), the uniform convergence result of 777C+24 Lemma 1] guarantees that A(9 is an ((c)-accurate ERM. Otherwise, we update the cap vector to ( according to LazyHedge, and then add fresh samples each S, until [S, > !. @((d+ + +)/=²).
At each round t, if w
remains handle the sampling in the Hedge update step. which requires w(t) @(k) fresh samples from each D;. If we draw these samples in each round, the MDL algorithm would still need T Q (log k)) rounds of sampling. Instead, we maintain dataset Sr, for each pair (i, f) kk] x [T] that is reserved for the Hedge update step for distribution D; in the 1-th iteration. We ensure the invariant that, at any iteration 1,
SS 2 w."h (k))
holds for every i E [k] and 1' 2 To this end, whenever the cap vector to(() is updated, we add fresh samples to each Suy (where t' > t) that the invariant above still holds. By doing so, we ensure
32

---

that in the Hedge update step at any iteration we have | 2 , Furthermore, we only need one round of sampling whenever the cap vector is updated.
(kk) 2 w: (0) (kk) samples.
The above exactly corresponds to the LazyHedge algorithm in the box setting of OODS: Whenever the Hedge dynamics reaches a point w(t), the algorithm must update the cap ((( to ensure that w-(() 2 (()) Every cap update in LazyHedge corresponds to a round of adaptive sampling in MDL. By Lemma 7 the resulting MDL. algorithm has O log k) round complexity. Moreover, the sample complexity of the MDL algorithm is at most
k
k
= - E2
Σ
10
b(dd+))/e) + T
1
(())
OOllog"kk//e) = Õ(C) from Lemma 6. which in turn follows from [ZZC+24 Lemma 3J. Setting C. O(1) gives the following result for MDL.
where we apply = Ō(1/E²) and the bound Σ wi
(k/e))
Corollary 21. There is an O(k log rr-und MDL algorithm with an Ö((d + k)/=²) sample com- plexity.
Ö(Vk)-Round MDL from Theorem 20 We further improve the round complexity to Ö(vk)
using our results for the ellipsoid setting (Theorem
20 The key observation is that the analysis
of [ZZC+24] does not require the "box" constraint We;
I uu for every E [k.]. Instead, the weaker
"ellipsoid" constraint
(0) ///m! < suffices.
To this, note that the analysis of IZZC+24 uses the lower bounds the sample size two different places, both of which go through under the ellipsoid constraint. The first place is the proof of the uniform convergence result 2 Lemma 1]. For fixed w E A No and h H. the analysis boils down to showing that, if every dataset S; contains n,, independent samples from D.,
W
[[(xx) b (x.y)ES
Σ
74
is an estimate for the population error of h on the mixture distribution Σ w; D; with sub-Gaussian and thus concentrates around the population error up error of O(a (log/oo(1/0)) except with probability 6. In particular, assuming that 2 w; O(dd k)/=), we have
parameter o² < Li=l w
w
W ([(d+))/e) = θ d+k
w; T
d d+k
We note that the same bound hold under the weaker assumption that, for some cap vector w, it holds that Σi=1 w²/W, and n, w. .((d + k)²;
&
w?
k
g2 +
= θ
Σ
" //;; = H
wi S((d + k)
d
The second place is Step 3 in the proof of 27 Lemma 17]. This step uses the fact that w.
(k) samples are used to compute the estimate r so that the estimate has a variance of
Fortunately, this variance bound is only used in aggregate over all E [k] in their
ku CTT
Equation (111), which shows that the weighted average Σ
w r (t) has a variance of at most
Σ To 10 o (Ara (1d))) O(1kk)
=
W = 0(1/k)
Again, this step would still go through under the ellipsoid constraint Σt_ (w] 12 w (t), As long as at least w." @(k) fresh samples used to estimate Ti the weighted average Σ w has
(1) (0)
33

---

variance of at most
W 12
10 O
12
O(1kk)
OL1/k).
kw
1=1
Therefore, Theorem
20 implies the following result for MDL.
Corollary 22. There is an O(VR)-roond MDL. algorithm with an O + k)/e²² sample complexity.
D Lower Bounds for OODS
We prove lower bounds on the sample-adaptivty tradeoff in the OODS model using two different hard instances: one for the "large-e" regime where E O(1/k), and the other for the "small-e" regime where E S -((k)
Q())
D.1 Hard Instance for Large
Definition (Hard instance for large z). Given kt 2 2 draw m different indices i 12, ....,,,. [k] uniformly random. The objective function f A [0, is
f(w) = min {
Wij + m
Waz
+ m
Whe
m
m
Note that we allow the co-domain of f to be [0.2] instead of [0, 1] for brevity; scaling everything down by a factor of gives hard instance and thus lower bounds for the formulation in Definition
Before we formally state and prove the lower bounds, we make a few simple observations and then sketch the intuition behind the lower bound proof.
Characterization Approximate Maxima If we set Waz
3m+1 2m
1 m²
for every E [m]] and
W4 = 0 for every E [M] \ {i, i2 bm) we have
m
3m +
Way + m
=
Way +
War
m
m
2m2
which gives f(w) = 3m+1
Furthermore. it can be easily verified that w E k-1 We note that w
2m
the maximizer of over k- since achieving an objective strictly higher than 2m
3m+1 requires
strict increase in each of wiy...... Wi;,, which would violate the constraint that A 1-1
More generally, we have a "robust" version of this observation: As long as < O(L/k), every e-approximate maximum indices i; ii.....i im
must put a significant weight of 22(1m)) on at least half of the critical
Lemma 23. For every < 1/(2k) and every w E A-1 that satisfies (ww 2 3m++1 have
Hi [k] w, 2 1/(2m))
................... m/2.
Ht ..............
Proof. Suppose towards contradiction that strictly fewer than m/2 entries among Wiy, Wag ..., Wip least 1/(2)). Then, there exists j E (1,2,... [mm.... such that wa; 1/(2m). It follows that
f f(w) < W3z + m
(m + 1)/2
2m +1
<
+
2m
m2
2m2
On the other hand, since m E and < 1/(2k), we have
3m
3m +
2m +
E 2
> f(w),
2m3 2
2m2
2m
2m?
contradiction.
34

---

Limited Information from First-Order Oracle Therefore, it remains to argue that an OODS algorithm cannot identify (2()) critical indices using < m rounds while incurring polylog(k) (k) sample overhead. To this end, we observe that first-order oracle provides little information on the critical indices, unless we have already found many such indices.
By definition of f from Definition 4 the following is valid first-order oracle: Given w E A find the minimum j [ma]] such that f(w) - wi; +//m². Return the value of f (w) and the supergradient eig. In other words, via a first-order oracle, the optimization algorithm only gets to know the critical index that accounts for the value of f(w).
Our next lemma suggests that, unless we put weight of > 1/m² on each of i ...... fj. the value of f(w) is determined by the first terms in the minimum. In other words, unless we already "know" the first j critical indices, we cannot learn the value of ".+1r-..,hh, from the oracle.
Lemma 24. For every w A and j E [m]] assuming minfw;; way Wiy S 1/m², we have
2
[ww) min Wi; + m² wig + m
Wig + m2
Proof. Suppose towards a contradiction that some w E A
A satisfies w/;, S 11/m² for some j1 $ j.
but f(w) # min wi; + m.
Wii
m Way
Then, there exists j2 > j such that
j2 m
j
< may + ji
W
< min Wig + m²
Wag +
m
Wig +
m
m
which implies wig, W + (j2 51)/m² 2 1/m², contradiction.
Intuition behind Lower Bound There natural m-round algorithm for solving the instance from Definition 4 In the first round, we query the uniform weight vector to learn the value of ij. In the second round, we query f on some w with w;; >> 1/m², thereby learning the value of iz. Repeating this gives m-round algorithm with a low sample overhead.
(1/k, 1/k,.... ... 1/k)
One might hope be "more clever" and lear more than one critical index in each round. For example, the algorithm might put cap of > 1/m² on several coordinates in the first round, in the hope of hitting more than one indices in i 12. of 8, only 0(m²s) s) such guesses can be made. In particular, if m² < k, the guesses only cover tiny fraction of the indices. Thus, over the uniform randomness in i*, the algorithm can still only learn (1) critical indices in expectation within each round.
However, if the algorithm has sample overhead
D.2 Lower Bounds for Large
Now, we formally state and prove the lower bounds the e S O(1/k) regime, for both the box and the ellipsoid settings.
Theorem 25. The following holds for all sufficiently large k, E S $/111/20 1/(kk) and s 2 1: (1) In the box setting. for m == 1 /k/ss, no OODS algorithm with r S mm/4 rounds and sample overhead s can find an E-approximate maximumn with probability at least 9/10; (2) In the ellipsoid setting. for m = [=((/))///1 no OODS algorithm with r S m m/24 rounds and sample overhead can find an e-upproximate maximum with probability at least 9/10.
In particular, have sample overhead s S polylog(k)) any OODS algorithm must take ((Vk) rounds in the box setting, and 1/4) rounds in the ellipsoid setting.
Proof. We will focus on the box setting; the ellipsoid setting follows easily with only a few changes in the proof.
Suppose towards contradiction that an OODS algorithm A for the box setting takes r <m/24 rounds and succeeds with probability at least 9/10. Consider the execution of A on a random OODS
instance defined in Definition 4 with m
k/8
35

---

For each round L E [r]. let 700 = {i [m]] : / 1/m²} denote the indices which algorithm A sets cap strictly higher than 1/m2 Since A has sample overhead of 8, we have || S and thus [ m2s. By definition of the box setting, within each round t, A cannot query the oracle if w; 1/m² holds for some i [k] 7(5) Therefore, Lemma 24 implies the following: Unless {8t, 22 ... 13) S r(0) for every point that A queries in round t, it holds that
2 m²
f(w) = min wij + m² waz +
Wgg + m2
Deferring Randomness Rather than drawing all the m critical indices the beginning. in analysis, we choose these indices "on demand" as the OODS algorithm expands the observable region. We do this carefully, so that the distribution of i is not biased.
In the first round, after w(() (and thus the set ( has been determined by A, we draw ii from [k] uniformly at random. If i & 7(1, we stop the process; otherwise, we draw i2 from [K] \ {tt uniformly random. We keep doing this, until either all the m critical indices are determined, or we draw some i3 $ / f(1), Let (1 denote the number of critical indices drawn in the first round. By Lemma 24 for every w E ((w()) observable to A in the first round, fw) is determined by the first (2) critical indices. In particular, the remaining m - (2) critical indices (1) through im are still uniformly distributed among [k]] \ {ii..... a J. conditioned on any information that A obtains
from the first-order oracle.
More generally, at the beginning of each round & E [r]. we observe the set (() is determined by algorithm AA We keep sampling " (001111 22 ... until either all m indices are chosen or we encounter an index outside {(t), Let (2()) denote the total number of critical indices that have been sampled, including those sampled the first t 1 rounds. Then, all queries made by A during the t-th round can be answered solely based on the values of i through it (1)) they do not depend on the m
(*) indices that have not been decided.
Control the Progress Measure Let random variable (1) denote the value of (9) in round t, over the randomness in both algorithm A and the random drawing of the critical indices. Next, upper bound the expectation of (r(r) after all rounds.
In each round i [r). whenever we sample critical index 1j (j E [m)). there are k- (j-1) 1) h - m possible choices (namely, [k] \ (ii,... ()-1)). Among these choices, at most |700| < m² fall into the set (t)) Recall our choice of m == 2 / which ensures m² 8 I k/4 and m - k/22
Thus, the probability of not stopping after drawing i is at most k-m k/2 1- It follows that the number of critical indices sampled in each round t is stochastically dominated by geometric random variable with parameter 1/2. Therefore, we conclude that E [N[r]]] < 2r.
m=² - k/4
Control the Success Probability Finally, we derive a contradiction by arguing that the probability that A finds an e e-approximate maximum of f is below 9/10. Let á denote the output of A, and i = (i E [k]] w; 2 1/(2m)} be the indices on which v puts a weight of at least 1/(2m). Since the entries of áe E k sum up to 1, |/| < 2m. By Lemma 23 for ve to be an e-approximate maximum, in (i1, i2 } must have size 2 m//2
Conditioning on the event that (T S mm/4, at least 3m/4 critical indices have not been chosen, and they are uniformly distributed among the k - -N0) remaining indices. For the condition j (17, ..... et H1 2 m/2 to hold, we must have |ř NO) 2 m/4. For any choice of i, over the remaining randomness in (i mm + holds that
N2042 .% 2 m/2
[ (1 "ea4 1
s $/4 k - NO) S 2m
m N(r)
m
4m 2
k - m/4
k
36

---

Recall that m s kk/ I vk/2. Markov's inequality gives
Pr [ (Noe
2 m// N 5m/4
E
[ (1
H N(r) - m/4
m/4
4m² /k
8
1
m/4
Vh
3'
where the last step holds for all sufficiently large k 2 576. In other words, conditioning NO0 & m/4, the probability of finding an e-approximate maximum is at most 1/3. On the other hand, by Markov's 's incquality and the assumption that r 2 m/24,
E [N(r]]
Pr NO > m/4
2r
<
m/4
m/4 3'
Therefore, the overall probability for A to output an e-approximate maximum is at most 2/3 < 9/10, contradiction.
The Ellipsoid Setting this setting, we consider the execution of A on random OODS instance defined in Definition 4 with m (k/ss)//44 Different from the analysis for the box setting, we (t) 1/m²3 using threshold 1 1/m² instead of 1 1/m². Then, have an analogous implication of Lemma 24 Unless {it 12 ................................ .,7 S _()), for every point that A queries in round f, it holds that
define 7(0) (i E [m] w
f(w) = min
wi; +
wi; +
Wig +
m²
m
m2
To see this, note that if 17 (t) holds for some jo E [i], we have (t)
1/m². Then, for any
E O (w(()) we must have
k
w
W
f=1
W
which implies Wit S
w
S 1/m2. Then, Lemma 24
implies
2 m
f(w) min
Wiz + m²
Wig +
Weg +
m2
To control the expectation of (Or), we note that the definition of 7(0) and the assumption on having a sample overhead of s together imply [ < m Then, the choice of m < (k/ss) < k/2
guarantees that the sampling process stops at each step except with probability m k/16
S 1/2.
k-m 4/2
The rest of the proof goes through.
D.3 Hard Instance for Small
When the accuracy parameter e is exponentially small, we give a slightly different instance on which any OODS algorithm must take 22(k) rounds in the box setting and 2( rounds in the ellipsoid setting, matching the exponents in Theorems g and 20
Definition 5 (Hard instance for small e). Given l: 2 m 2 1, draw m different indices i1, i2...., .% E
[k] uniformly at random. The objective function f A 1- + [0,2] 2]
f(w) = min (a. Wez + by), JE[m]
where aj 2- and by (1 2/
Again, we allow the co-domain of f to be [0. 2) instead of [0, 1] for brevity. We start with a few simple observations and the intuition behind the lower bound proof.
37

---

Characterization of Approximate Maxima the following vector wt w; 1/m for every E {it fm and w, = 0 for i E [k] \ (......, m. Indeed, such w ensures that
We first note that the maximizer of f over AR-1 is
1 m
2
0g . W + b, = 2
m
m
for every j [m]] and thus f(w) 1/m. Furthermore, to achieve an objective strictly higher than 1 1/m, we must strictly increase each of wi;..... w which would violate w A--1
Analogous to Lemma 23 the following lemma states that for every e every s-approximate maximum of f must put significant weight of (2(1m)) on at least half of the critical indices .i....... mm
Lemma 26. For every e S 2- ((2k) and every w E A k-1 that satisfies f(w) 2 1 E, we have
Hi E [k] : w, 2 1/(2)) n {i ......
a :
m/2
Proof. Suppose towards contradiction that strictly fewer than m/2 entries among Wiy, Wiz ......... ..... Wig. are at least 1/(2m). Then, there exists j E (1. ................................ . [m/2]] such that Wi; < 1/(2m). It follows that
2
1 - 2-
2-1
1
2 2-(m+1)/2
f(w) S a, Wi + bj
+
S
2m
m
m
2m
1
2m
On the other hand, since m I k and
S 2 1k+1)// /2//1///// (2k:, we have
1
2
(k++1)//2
1
2 1m+12/2
2k
m
2m
This contradicts the assumption that f(w)
Limited Information from a First-Order Oracle Again, the lower bound proof amounts to showing that an OODS algorithm cannot identify (mm) critical indices using < m rounds while having a low sample overhead. To this end, we note that the following a valid first-order oracle for f: Given E A k-1, find the minimum j E [m] such that f(w) a, Wty by- Return the value of (w) and the supergradient aj egg. Again, the optimization algorithm only gets to know the critical index that accounts for the value of fww).
The following lemma is analogue of Lemma 24
We must put weight of ((1/m) on each of i E2,82,... to learn the values of "j+ im from the first-order oracle.
Lemma 27. For every E A- and [m]. assuming min(wi, (Wiz. wag..... we S 1/(2m), we have
f(w) min far wy bi, a2 waz + b2. ......... ag w bbb}
Proof. Suppose towards a contradiction that some w k-1 satisfies wi;, S 1/(2m) for some
ji S j. but ((w) + min 01 wi; + bi,a2 a2 way + bb...., wiy + by Then, there exists j2 > j such that
ajz Wiy + biz < min { a1 W/3 bi, 02 wiz + by b2..... aj wiy + bj S aji Wiz + bjr-
Plugging 05 = 2 and by (1 2 / into the above gives
+ 1 - 2-
2-h
2 2- 12
Wazp
2 Way
Recalling the assumption that wi;,
5 1/2m), we have
1
1
Why < 2 in
wiy
S
11 < 0,
m
m
m
2m
contradiction.
38

---

Intuition behind Lower Bound in the large-s regime, there is natural m-round algorithm for solving the instance from Definition [ so the proof amounts to arguing that the OODS algorithm cannot be "more clever" and learn more than one critical index in each round. For example, the algorithm might put a cap of > 1/m on several coordinates in the first round, in the hope of hitting more than one indices in 12. ..... However, any algorithm with a sample overhead of can make only ((ms) such guesses. Then, assuming ms < k, the guesses only cover a tiny fraction of the indices. Thus, over the uniform randomness in i", the algorithm can still only learn ((1) critical indices in expectation within each round.
D.4 Lower Bounds for Small
Finally, we state and prove the lower bounds in the E S -R(k) regime, for both the box and the ellipsoid settings.
Theorem 28. The following holds for all sufficientll large k. < 2- (2k) and 2 1: (1) In the box setting, for m == min [8s( [ no OODS algorithm with S. m/24 rounds and sample overhead can find an s-approximate maximum with probability least 9/10; (2) In the ellipsoid setting, for m == min and sample overhead can find an e-approximate maximum with probability at least 9/10.
no OODS algorithm with r S m/ m//4 24 rounds
In particular, to have sample overhead polylog(k), any OODS algorithm must take (2(k) rounds in the box setting, and [?( (()) rounds in the ellipsoid setting. These match the exponents in the upper bounds (Theorems 8 and 20).
The proof is analogous to the one for Theorem 25
will be brief.
Proof. Again, we focus on the box setting; the ellipsoid setting follows easily with only few changes in the proof.
Suppose towards contradiction that an OODS algorithm AA for the box setting takes r S mm/24 rounds and succeeds with probability at least 9/10. Consider the execution of A on a random OODS instance defined in Definition with m == min { [l/ [8)]] [A/48]]. For each round E [r], let
((0) = {i E [m]] : w. (2) > 1/(2m)) denote the indices which algorithm A sets a cap of (11mm). Since A has sample overhead of s, we have | S and thus [ - 2ms. By definition of the box setting, within each round f, A cannot query the oracle on w if w; > 1/(2m) holds for some
i E [k] \\
7(0) Therefore, Lemma 27 implies the following: Unless {ij, .2,,,,,,77 1j} S 1(t), for every point wo that A queries in round holds that
f(w) = min [a Wi; + bi, a2 wi; + b2....,, .a............ a.. we; + by b
Deferring Randomness Again, we draw the m critical indices "on demand" in our analysis. We start with (0) = 0. In each round & E [r]. after A decides on ((() and 7((), we keep sampling Ga R t 1.2--... until either all m indices are chosen or we encounter an index outside 7(0) Let (2) denote the total number of critical indices that have been sampled by the end of round t. By the implication of Lemma 27 all queries made by A during the f-th round can be answered solely based on the values of i through i,,,, as they do not depend on the m - (t) indices that have not been decided.
Control the Progress Measure Let random variable (9) denote the value of (*) over the random- ness in both algorithm A and the critical indices. In each round / E [r]. whenever we sample critical index i (j (m]), there are k - [j 1) > k m possible choices (namely, [k] \ (ii,...,gj..) Among these choices, at most [ < 2ms fall into the set I(9, Recall our choice of m < k/(Ss). which ensures both 2ms < k/4 and m S k/2. Thus, the probability of not stopping after drawing ij
is most expectation,
2ma
k/4 k/2
3. follows that most critical indices are sampled in each round in
m
have E [N(]]] 2r.
Control the Success Probability Finally, we derive a contradiction by arguing that the probability that A finds an s-approximate maximum of f is below 9/10. Let i denote the output of A, and
39

---

1= fi E [k] : 0b 2 1/(m) be the indices on which úi puts weight of at least 12mm... Since the entries of ④ A sum up to 1, |4| S 2m. By Lemma 26 for v to be an s-approximate maximum, in (ii, 2 . } must have size 2 mn/2.
Conditioning on the event that N(r) - m/4, at least 3m/4 critical indices have not been chosen, and they are uniformly distributed among the k .N remaining indices. For the condition L {i7, 22 ....... im 2 m/2 to hold, we must have If (1 4204411.. NO) 2 m/4. For any choice of I, over the remaining randomness in ( (fo044 +2 A J. it
2 m/2
holds that
m N()
4m 2
E [ U 42042 ..g.....h Gnll [
s 1/1-
S 2m
m
1: N(r
m/44
1:
Recall that m s /2/k k/s S vk/2. Markov's inequality gives
Pr [ (w i Vo042....... f 2 m/4 ( S 5m/4
E
[inn (i M H N(r) S m/4
m/4
4m3 /k: m/4
16m 1
k
3
where the last step follows from our choice of S k/48. In other words, conditioning N()) < m/4. the probability of finding an e-approximate maximum is at most 1/3. On the other hand, by Markov's inequality and the assumption that S m/24,
Pr NO))
m/4
E N
2r
m/4
m/4
3
Therefore, the overall probability for A to output an e-approximate maximum is at most 2/3 < 9/10, a contradiction.
The Ellipsoid Setting Finally, for the ellipsoid setting, we instead consider the execution of AA on a random OODS instance defined in Definition 4 with m == min [1] / /k/s], [k/48] }}, and define 7 = (i E [m] : w > 1/(4m²) using threshold 1/(4m²) instead of 1 1/(2m). Then, we have an analogous implication Lemma Unless {it, . it) C 7(0), for every point w that A queries in round I, it holds that
2
fww min
Wig + m Wig
Wiy + m² f
m
To see this, note that if k $ 7(0 holds for some jo E [i]. we have w < 1/((m²?. Then, for any E ((T(!)), we must have
2
1.
(t)
TT
which implies Wiy < !
1/(2)). Then, Lemma 27 implies
2 m²
f(w) min Wi: + m² Wig +
Wey + m²
To control the expectation of (rr), we note that the definition of 7(0) and the assumption on A having
a sample overhead of together imply [7(6| < 4m²s. Then, the choice of m < /k/s guarantees
that the sampling process stops at each step except with probability k-m the proof goes through.
4m < X/2
k/1 = 1/2. The rest of
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction are formally stated in the main paper and the appendices, and they apply to the problem setting that formally introduced. They accurately reflect the paper's 's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The theoretical results apply the specific problem settings (which
formally defined) and under specific parameter regimes (which appear in the formal theorem statements).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
41

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The assumptions are clearly stated as part of the problem formulation or the formal theorem statements. All the theoretical results have proofs, in either the main paper or the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
42

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://mips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7 //nips. hwcp//blccggudeeeeeeeeeeee/eeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
43

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http:///wwurrr....caaaaaacccctta
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is purely theoretical and there is no immediate societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
44

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
45

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
46

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy buctps://neure wwwparipppscccoooeeeeeeeee cc/Conferencess///////e for what should or should be described.
47


Reviews:
[{"review_id": "9IT2eTpXK0", "reviewer": "Reviewer_ajYw", "summary": "This work studies on-demand sampling, where there are $K$ distributions and the goal of Learner is to learn a hypothesis that minimizes the worst-case error. They consider two classical settings in statistical learning: the realizable setting and the agnostic setting. They present both the upper and lower bounds results. For this work, they study the fundamental trade-off between sample complexity and round complexity, which is very important.", "questions": "1. What is adaptive sampling, or how to decide in each round, whether it is adaptive sampling or non-adaptive sampling? And what is full adaptivity and full non-adaptivity? I hope to see more background knowledge of adaptive sampling.\n\n2. Is my understanding right the provided results in the realizable setting can only improve the existing non-adaptive sampling results? From the content below Theorem 1, it seems it cannot improve the results shown in [BHPQ17, CZZ18, NZ18].\n\n3. Can you give more explanations and intuitions about the agnostic results such as how to get rid of the $\\epsilon$ in your new results? And why the round complexity does not need to be dependent on $\\epsilon$? For me, the existing results make more sense.\n\n4. For Algorithm 1, how to decide the number of samples that are distributed according to each of the K distribution in each round? Can it be varied among distributions?\n\n5. The discussion below Theorem 1, it will make it look nicer if, the two special cases, the case where $r = \\log k$ and  $r = O(1)$, are presented in Table 1.\n\n6. Also, for the discussion below Theorem 1, it seems that when $r = \\log K$, it cannot recover the existing results.  Why claim it is almost recovered? I think it only improves the non-adaptive sampling results. \n\n7. Algorithm 1 inputs round $r$, can it be chosen adaptively, for example, based on the past collected data? \n\n8. Maybe I missed something in  Algorithm~1. what are $q_t^m$ and $D_j^n$  ? \n\n9. In algorithm 1, in step 3, it seems we do not know $D_i$ right? So, how to compute $q_1$?\n\n10. For Theorem 2, it is a minimax lower bound or a lower bound for this specific algorithm? If it is a minimax lower bound, it seems to be contradicted with the existing results in [BHPQ17, CZZ18, NZ18] in the realizable setting.", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strength: the studied trade-off is very fundamental. \n\nWeakness: for some part about the presented Algorithm 1, it is not clear. The details are in the box below.", "was_revised": true, "final_justification": "There are some space for the improvement in terms of presentation. So, I keep my current score.", "rebuttal": "Thank you for your review! We answer your questions in the following:\n\n1. 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.\n\nPut 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.\n\n\"Full adaptivity\" means that there is no limit on the number of rounds. \"Full non-adaptivity\" means that there is only one round.\n\n2. 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$.\n\n3. 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$.\n\n4. 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$.\n\n5. Thank you for this comment!\n\n6. 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$.)\n\n7. 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.\n\n8. $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!\n\n9. 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$.\n\n10. 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$)."}, {"review_id": "5c3bPHaYYr", "reviewer": "Reviewer_EyU1", "summary": "This paper studies an adaptive learning process in the Multi-Distribution Learning (MDL) setting, and characterizes a tradeoff between the sample complexity and round complexity. Specifically, it studies to what extent an adaptive sample collection can achieve a near-optimal sample complexity while maintaining a beneficial round complexity. Under the realizable setting, it characterizes the sample complexity as $dk^{\\Theta(1/r)}/\\epsilon$, where $r$ is the round complexity, using a variant of the classical AdaBoost algorithm. In the agnostic case, it shows that with $\\tilde{O}(\\sqrt{k})$ rounds, a sample complexity of $\\tilde{O}((d+k)/\\epsilon^2)$ can be achieved through an revised algorithm from that of [ZZC+24] (by allowing laze sampling with a cap). From a theoretical perspective, the paper also introduces the framework of Optimization via On-Demand Sampling that naturally connects to the multi-distributional learning problems, which implies both the upper and lower bounds for the round complexity with specified sample overhead.", "questions": "Did authors consider other boosting algorithms that might further reduce the sample complexity?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper considers an important problem of multi-distributional learning under the adaptive setting, and provides a theoretical foundation for studying the tradeoff between the sample and round complexity. It studies the problem in both realizable and agnostic settings, providing both upper (through well-designed algorithms) and lower bounds (through rigorous analysis). The paper is very well presented with original and insightful discussions. The work is very influential in adaptive learning settings, and could benefit in this area of research, including on-demanding sampling, multi-arm bandit problems, continual learning, to name a few.", "was_revised": true, "final_justification": "The paper is of high quality. During the discussion period, the authors provided further clarification on its related work. I have checked other reviews, and all reviewers showed support for acceptance. Hence, I believe the paper is definitely above the acceptance bar.", "rebuttal": "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)$."}, {"review_id": "K88ph2Tf64", "reviewer": "Reviewer_npZF", "summary": "This paper works on reducing the round complexity for multi-distributional learning problem. Multi-distribution learning (MDL) focuses on learning multiple distributions with on-demand sampling. Recent work established near-optimal sample complexity for MDL. In this work, the authors try to reduce the round complexity with lazy updates. They provide a trade-off between the round complexity and the sample complexity for the realizable case, and prove a sub-linear round complexity for the agnostic case.", "questions": "1. Can you provide some intuition for why the lower bound is not polynomial in $\\epsilon$?  Is there any method to combine your arguments with the classical $\\tilde{\\Omega}( \\frac{d+k}{\\epsilon^2})$ lower bound (without limitation on round complexity) to obtain a better rate?\n2. I wonder whether there is substantial difficulty in extending the upper bounds for realizable setting to the agnostic setting. In particular, fix $r\\leq \\sqrt{k}$, could you prove a sample complexity upper bound better than the trivial bound $dk/\\epsilon^2$ for the agnostic setting?", "limitations": "The theoretical results only apply to the specific parameter regimes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The major contribution of this work is to establish the trade-off between the adaptivity and the sample complexity. This represents a valuable contribution to related fields. \n2. In technique, the major contribution is  a novel application of a variant of the AdaBoost algorithm with a particular notion of margin.  The construct of the lower bound is also a significant technical contribution.\n\nWeakness:\n1. The results in the agnostic setting are relatively weak due to the absence of statistical lower bounds.", "was_revised": true, "final_justification": "My major concerns are resolved, so I would like to keep my evaluation as 4.", "rebuttal": "Thank you for your review! We answer your questions in the following:\n\n1. 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.\n\nWe 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.\n\n2. 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$."}, {"review_id": "oKm6z9P23J", "reviewer": "Reviewer_7PVT", "summary": "The paper studies the problem of adaptive data collection for multi-distribution binary classification. Multi-distribution refers to the learner being evaluated on the error for data coming from across $k$ distributions. The adaptive data collection is formalised by a procedure over $r$ rounds where in each round the learner can choose the number of samples to collect from each of the distributions (and this can be based on samples collected in previous rounds). The aim of the paper is to understand the trade-off between $r$ and the total number of samples needed for $\\epsilon$ accuracy (on the multi-distribution error in a PAC sense). In the realizable case (where a perfect predictor exists), they provide upper and lower bounds that characterise the (near) optimal trade-off. In particular, O(log k) adaptive rounds is optimal to achieve the optimal sample complexity. In the more challenging agnostic case (where a perfect predictor does not exist), an algorithm is provided that achieves the near-optimal sample-complexity in a number of rounds that is independent of $\\epsilon$. The optimization via on-demand sampling framework is introduced whose connection to the multi-distribution problem allows to motivate the difficulties in improving the round-complexity of the agnostic case, as well as establish general results on the trade-off between sample complexity and adaptivity.", "questions": "1. In the discussion following Theorem 1, I am not sure about the claim at l.130 that $r = \\log k$ is the “most sample-efficient”. Given the upper-bound in Theorem 1, the most sample efficient is when $r \\rightarrow \\infty$ - I guess what was meant is that $r = \\log k$ already allows to recover the order of the optimal sample complexity. But really if we ignore what we know to be the optimal sample-complexity, the bound in Theorem 1 suggests that we should set $r$ to match the second term of the bound. And at a higher level, what it says is that the adaptivity level (the value of $r$) should be set as a function of k and d and in particular will behave somewhat differently when k>d or d>k. Have you thought about this ? And also how this might be relevant to settings where $k$ may be unknown, how hard would it be to extend these results ?\n2. In l.132, when $r = 5$ is chosen in Theorem 1, why is it $\\sqrt{k}$ in the sample complexity and not $k^{2/5}$, is this a typo ? I think there is also a typo l.157: it should be $\\sqrt{k}d$ not $\\sqrt{d}k$, right?\n3. In weakness 4., it was mentioned that no lower-bound is provided for the round-complexity in the agnostic case. In section 5.3, it was discussed the improving the round-complexity required a different approach. Could you comment on whether you believe the $\\sqrt{k}$ round-complexity could be improved and if so what the optimal round-complexity could be?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper is generally well-written and easy to follow (except a few parts – see weaknesses). The algorithms are well explained and the proof sketches provided in the main text are nice and provide some useful intuitions.\n2. Realizable case: An upper-bound is established that captures a trade-off between adaptivity and sample-complexity. In particular, I believe the main point that can be concluded from the upper and lower bound is about the optimality (sufficiency + necessity) of $\\log k$ rounds to achieve the optimal sample-complexity, completing the characterization of optimality for adaptive sample-complexity.\n3. Agnostic case: An upper-bound is established that achieves the near-optimal sample-complexity with a round-complexity that is independent of the accuracy $\\epsilon$, improving on prior work whose algorithms had round-complexity that depended polynomially on $\\epsilon$.\n4. The algorithms are non-trivial extensions of algorithms from prior work.\n\nWeaknesses:\n1. Some of the technical description is a bit unclear. There seems to be some missing notation in the description of Algorithm 1, e.g. $q_t^m$ is not defined (I guess this means m samples from $q_t$ ?), $q_{t+1}$ / $q_t$ is not defined (only $q_{t+1}(j)$ is). Additionally, it is not clear where $p$ and $\\varepsilon_A$ are used in the algorithm, which then makes the following discussion of the technical overview a bit unclear. In particular, my understanding is that the learner $A$ is called to to learn a predictor $q_t$ that minimizes the fraction of distributions (as weighted by $q_t$) where the weights $q_t(j)$ have been adjusted in previous rounds according to the errors being more or less than $\\tau/2$ but I don’t see how the equation below l.142 fits in.\nThe proof sketch of Theorem 2 for $r=2$ provides some nice intuition but the explanation of the way $diff_i$ as uniformly random permutations is not clear. It is not clear to me what is meant by a uniformly random permutation of a copy of $\\Theta(d)$. Is $diff_1$ a sample from a permutation of $[1,…,d]$ ? Is $diff_1$ itself a permutation, though my understanding is that $diff_i$ is the dimension of subspaces that more or less partition the space, I.e.\\ an integer. Also, if possible I think it would be clearer to avoid using $\\Theta$ notation here and explicitly put the values. \n2. The lower-bound in Theorem 2 has a $k^{1/r}$ dependence while the upper bound is $k^{2/r}$. However, this is enough to establish the necessity of the $\\log k$ rounds, which in my understanding is the main contribution this result allows to establish for the realizable case (and perhaps should be stressed more ?), especially since known algorithms with optimal sample-complexity already had a round complexity of $\\log k$. Indeed, for the case where $r$ is a small constant, the upper-bound from Theorem 1 is an interesting result, but does not match the lower-bound.\n3. The high-level connection between optimization via on-demand sampling and MDL is discussed in lines 260-265 (and again in Section 5.3), however it is unclear how the results from each section are connected. What is the connection between Theorem 4 and proposition 1 ? And with this absence of connection, it is a bit unclear how the results from Section 5 fit in with the rest of the paper. In particular, I understand how Theorem 9 provides some insight into how well lazy-hedge can perform for MDL but it is unclear how Theorem 4 does this from an upper-bound perspective. More generally, while Section 3 has a clear structure that is easy to follow, it becomes a bit harder to follow the narrative through Sections 4 and 5. Also, in Section 4 a bit more discussion could be provided as currently the results are simply stated without much discussion.\n4. Proposition 1 provides an algorithm with near-optimal sample-complexity with a poly(k) round-complexity but no lower-bound is provided.", "was_revised": true, "final_justification": "The paper is well-written and presents a substantial set of results, significantly improving upon prior work. There are a few weaknesses to the work but they are sufficiently minor to not be an obstacle to acceptance.", "rebuttal": "Thank you for your detailed review! We start by clarifying the notations that you mentioned in the \"weaknesses\" part:\n\n- We will define the notations $q_t$ and $q_t^m$ in Algorithm 1. Thank you for your comment!\n\n- 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).\n\n- 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$.\n\n- 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.)\n\nWe answer your questions in the following:\n\n1. 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).\n\nRegarding 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.\n\nWe were unsure about the setting with an unknown $k$: how would the learner sample from the distributions if the number is unknown?\n\n2. 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!\n\n3. 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."}]

Author rebuttal:

Meta-review: The reviewers agree that the paper studies a fundamental tradeoff. Moreover, the paper is well-written and presents a substantial set of results. The Algorithms are well explained as well as the proof sketches.
And the results altogether for the realizable and agnostic case make an interesting and deep contribution, which is very relevant to the field.
I will therefore accept.
Decision: Accept (spotlight)