Derandomizing Multi-Distribution Learning
Authors: Kasper Green Larsen
Omar Montasser
Nikita Zhivotovskiy
Venue: NeurIPS 2024 poster (2024)
Keywords: pac learning
multi-distribution
derandomization
computational efficiency
discrepancy minimization
Primary area: learning_theory
TL;DR: We show that it is computationally hard to derandomize multi-distribution learning algorithms. We also show this hardness can be alleviated with a structural condition that we identify.

Abstract: Multi-distribution or collaborative learning involves learning a single predictor that works well across multiple data distributions, using samples from each during training. Recent research on multi-distribution learning, focusing on binary loss and finite VC dimension classes, has shown near-optimal sample complexity that is achieved with oracle efficient algorithms. That is, these algorithms are computationally efficient given an efficient ERM for the class. Unlike in classical PAC learning, where the optimal sample complexity is achieved with deterministic predictors, current multi-distribution learning algorithms output randomized predictors. This raises the question: can these algorithms be derandomized to produce a deterministic predictor for multiple distributions? Through a reduction to discrepancy minimization, we show that derandomizing multi-distribution learning is computationally hard, even when ERM is computationally efficient. On the positive side, we identify a structural condition enabling an efficient black-box reduction, converting existing randomized multi-distribution predictors into deterministic ones.

Derandomizing Multi-Distribution Learning
Kasper Green Larsen Department Computer Science Aarhus University larsenEcs au.dk
Omar Montasser'
Department of Statistics and Data Science
Yale University
omar maar.mnttaserr@ylee...e
Nikita Zhivotovskiy
Department of Statisties
University of California, Berkeley zhi zhivotorskiy@@errkeleyy edu
Abstract
Multi-distribution or collaborative learning involves learning single predictor that works well across multiple data distributions, using samples from each dur- ing training. Recent research on multi-distribution learning, focusing binary loss and finite VC dimension classes, has shown near-optimal sample complexity that is achieved with oracle efficient algorithms. That is, these algorithms computationally efficient given an efficient ERM for the class. Unlike in classical PAC learning, where the optimal sample complexity is achieved with deterministic predictors, current multi multi-distribution learning algorithms output randomized pre- dictors. This raises the question: a deterministic predictor for multiple distributions? Through a reduction to dis- crepancy minimization, show that derandomizing multi-distribution learning is computationally hard, even when ERM is computationally efficient. On the positive side, we identify structural condition enabling an efficient black-box reduction, converting existing randomized multi-distribution predictors into deterministic ones.
these algorithms be derandomized produce
Introduction
We consider the problem of multi-distribution learning where there k unknown data distributions P = (D,...., D over X' {-1,1}, where X' is an input domain and {-1,1} are the possible labels. The goal is to learn a classifier f f-1,, 1,,1) that satisfies
esp()) max erD, (f) < min max erp, (h) + e, where (f),()) Pr (x.9)>D,
(s(x) + v)-
(1)
NEW
Here H C (1 is the benchmark hypothesis class of VC-dimension d that the learner competes against, and mingeH max, erp, (h) is the optimal worst-case error that can be achieved with classi- fiers from H. The framework of multi-distribution learning, introduced by Haghtalab al. [10), is
a natural generalization of agnostic PAC learning 22 21 5 and captures several important appli-
cations such min-max fairness 22 18 15 [6].
and group distributionally robust optimization
In the realizable setting, where minsex (h) 0, there is learning algorithm using (((d+k)/e) samples to produce such a deterministic classifier f. see e.g., the works 7 throughout the paper, Ô hides terms that are poly In(dk/(=ō)
Here, and
"This work was primarily done while the author was FODSI-Simons postdoe UC Berkeley.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In the more challenging agnostic setting, where OPT := mingew (h) is greater than O, recent works show that the sample complexity is Ó(dd+ + k)/e²) 10 14 23]. We refer the reader to Table I in [23] for a detailed sample complexity comparison of prior algorithms. Importanlly, the guarantee provided by all existing algorithms is slightly different from the objective ① above. Concretely, all previous algorithms do not produce a deterministic classifier f X + [-1,1) but instead output a
distribution F over H. such that
max E J~ ferD, (f) min max prd, +
(2)
KEH
Due to the fact that classical PAC bounds, which involve learning from a single distribution, are achieved using deterministic predictors it is somewhat unsatisfactory always output randomized predictor in the multi-distribution case. Observe that because, as in ( we want optimal performance simultaneously for all distributions, even using randomized algorithm is somewhat problematic.
Indeed, assume that in practice we want to sample single f according to F and use it as our predictor.
Now, if we seek a guarantee like (T) for f. then the best we can guarantee from is to use Markov's inequality and union bound over all k distributions to ensure that
erp, (f) - 2k
min max maxer,, (h) + (E)) NEE
with probability at least 1/2, which is, of course, too conservative. Let us also remark that there are examples of distributions F for which this is basically tight. Consider e.g. an input domain X' Ii,..... Ix and k hypotheses hi...., ., such that h,,,,) = -1 and h2(
1 for j * i. Let DD; be the distribution that returns (x,, 1) with probability 1. Then for the uniform distribution F F= - Σg h4 over classifiers, we have max, f jer (f) = 1/k, but for any single f in the support of F, we have (fr(f) = max; CTD, (f) = 1. The example also shows that for every fixed distribution D,, if we sample an f from F, then with probability 1/k; its error exceeds the expectation by factor & for that distribution D;. There may thus be large gap between the guarantees of deterministic and randomized classifier, i.e. the bounds in [ and (2) are quite different.
The main focus of our work, is on replacing the random classifiers in previous works on agnostic multi-distribution learning by deterministic classifiers and understanding the inherent complexity of doing so. In particular, we are interested in understanding any inherent statistical or computational gaps multi-distribution learning between deterministic classifiers and randomized classifiers.
Our contributions
Our first contribution is a strong negative result towards derandomizing previous classifiers. Recall that the complexity class BPP denotes bounded-error probabilistic polynomial timefl That is, problems that have polynomial time randomized algorithms that are correct with probability at least 2/3 on every input. It is conjectured that P BPP and thus most likely BPP o NP. Recall that set of points is shattered if each of the 2" possible labelings of the points can be realized by some h E H. Our negative result is then the following.
Theorem 1. lf + NP, then
= (d, k. 1/E} tends to infinity, for every hypothesis class H. of VC-dimension for which one can find n points shattered by H in polynomial time, any multi- distribution learning algorithm for H. that on the set of k input distributions P (Di..... .p). with probability at least 2/3 produces a deterministic classifier f X 1-1, with erp S
mingeR er (h) + E, must have either (1) (i.e. super-polynonial training time, or f has (1) evaluation time.
We remark that this computational hardness result holds even when the class H admits efficient Empirical Risk Minimization (ERM), and even when the distributions algorithm. This highlights that the hardness stems not from the need to sample from the underlying distributions nor from the hardness of ERM, but from the computational problem of deciding which label to assign the points of the input domain.
known to the learning
Note that the assumption in Theorem that one can find a set of n shattered points in polynomial time is not restrictive. Finding such points is trivial for many H. i.e., simply choose 0, e...... cd-1 E [dd11 = X' for linear classifiers with VC-dimension d. More generally, the standard result on the
We refer the monograph 19 as standard reference discussing computational complexity classes.

---

class of classifiers induced by positive halfspaces in R shows that this class has VC dimension d, and for any set of points such that most d of its points are contained on single hyperplane, any subset of size d of this set is shattered. Similar properties are also known for the classes induced by balls TRP and positive sets in the plane defined by polynomials of degree at most p See [9] for
a detailed exposition of these examples.
While this might have been the end of the story, our NP-hardness proof fortunately highlights path to circumventing the lower bound. In particular, the proof carefully uses data distributions Di...., Dr for which (y z) varies between the distributions. Here Di(y | x) denotes the conditional distribution of the label of a sample (z. y) given I E X. We thus consider the following restricted version of collaborative learning in which D;(y x)) D2 2) for all x, j.j. That is, the k different distributions may vary arbitrarily over X. but the label of any I E X' follows the same distribution for all D,. As a particular model of label consistent learning, one may think of a deterministic labeling setup where it is assumed that there is = X + {1, -1] such that across all distributions y (x),, while no assumption is made that f belongs to H. Remarkably, in terms of sample complexity, in the case of single distribution, the case of deterministie labeling is almost as hard as the general agnostic case as shown in [3]. Thus, we believe our label-consistent
multi-distribution learning setup is quite natural and interesting.
Furthermore, this restriction turns out to be sufficient for derandomizing multi-distribun learning algorithms. In particular, we give new algorithm, Algorithm [ that uses randomized (i.e.. an algorithm that outputs a randomized predictor given the training data) multi musti-distribution learning algorithm (like 2 as black-box, and produces from it deterministic classifier, as in ①I.
Theorem 2. For any finite domain X, if the data distributions Di..... Dr are label-consistent, then given multi-distribution learning algorithm A that uses mik,, d, OPT, s, 5) samples and t(k, d, OPT, e, 5) training time to produce, with probability - 8, a distribution F over classifiers from H satisfying max, F FlerD, (f)) < OPT + Algorithm pprouces with probability 1 8 classifier f x - 1-1,1 with er S OPT + s with the sample complexity
m(k, d, e/2, + O(k In (#/(E6))/E=))
Using the additional ideas in Section 3.7 the training time of Algorithm
t(k, d, OPT, E / 6/2)) + Okk/² + In((x(/8)).
If the evaluation time of hypotheses in H is bounded by s, then the evaluation time of the classifier f bounded by
(0s) F1) + (11(k/88) In(()\/=e).
Note that several of the previous randomized multi-distribution learning algorithms are indeed computationally efficient as long ERM is efficient over H. This includes the algorithm in [23] that has near-optimal sample complexity of mn(k d, OPT, s, d) = Ö((d + +k) k)/s") with tkk, d, OPT, 5) = poly(k, d, E I Im(1/5)) t and |F| = poly (k: Inn_)))))))),, where tErM denotes the time complexity of ERM over H. Plugging this into Theorem 2 gives polynomial time deterministic multi-distribution learning algorithm.
We view the restriction to finite domains X' in Theorem 2 as rather mild, as any realistic imple- mentation of learning algorithm requires an input representation that can be stored on a computer. Moreover, our running time dependency on (A') is only logarithmic. Even so, in Section 3.2 we give some initially promising directions for extending our algorithm to infinite X.
Discussion of implications. Prior work has shown that in agnostic multi-distributtin learning, a sample complexity of (dk:/e² which is worse than the optimal ((d++))fe) sample complexity, is unavoidable with proper learning algorithms, which are algorithms restricted to outputting a classifier in the class H. [23] Theorem 18]. In contrast, our negative result in Theorem iimplies that there is no sample-efficient and oracle-efficient multi-disttibution learning algorithm that aggregates multiple ERM predictors in polynomial time. For example, our result rules out the simple majority-vot aggregation approach (which is feasible in the realizable setting when OPT 0). Note, however, that this does not rule out the existence of computationally inefficient aggregation approaches to construct deterministic predictors. That is. putting computational efficiency aside, it is still an open question whether there exists sample-efficient and oracle- multi- multi-distribution learning algorithm that outputs deterministic predictor, and we know from the lower bound of Zhang et al. 23 Theorem 18] that this predictor must be improper.
3

---

2 Hardness of derandomization
In this section, we prove that it is NP-hard to derandomize multi-distribuuie learning in the most general setup of input distributions D; over X' x {-1,1). In particular, the hardness proof carefully exploits that different data distributions may assign different labels the same X.
Our NP-hardness proof goes via a reduction from Discrepancy Minimization. In Discrepancy Minimization, we are given input an
matrix with 0-1 entries. The goal is to find "coloring" E {-1,1}" such that every entry of Az is as small as possible in absolute value. Formally, we seek minimize || oo. The seminal work by Charikar et al. [6] showed NP-hardness of computing the best coloring. In full details, their results are as follows.
Theorem (6)). There is a constant с > such that is NP-hard to distinguish whether an inpur matrix A E {0, 1) 1nn has ||alll 2 en for all z E [-1,1]" or whether there exists 1-1 with A= = 0.
Since || 2 ||Az|la/ this similarly implies that it is NP-hard distinguish whether all have | 2 evn, or there is 2 with A2 =0:0. O.
Let us now use Theorem 3 to prove our hardness result, Theorem I We remark that NP-hardness is formally defined a uniform model of computation where a Turing Machine takes an encoded input on a tape and decides language membership. As we believe our reduction is clear without going into such formalities, we have deferred a discussion of how to formalize multi-distribution learning in a uniform model of computation to Appendix 4
Proof. Let = min e/2, and let H be an arbitrary hypothesis set of VC-dimension d for which we can find a set of n points that are shattered by H in n o(1) time. This is possible due to our assumption.
Let A denote an arbitrary deterministic multi-distribution algorithm. Given a matrix A E (0, 1 such that either || |= 2 cvni for all E 111, or there exists a {-1, 1)"h with Az 0, we will now use A to correctly distinguish these two cases with probability at least 2/3, thus concluding that the running time of A is super- soper-polynomial unless BPP NP.
Start by computing an arbitrary set I1 Ti...., In of n points that are shattered by H. Now define 2n distributions Dtt, ....... Dtt Dr. Distribution D and DD are both defined from the i-th row of A. If m, denotes the number of ones in the i-th of A, let Dj+t return the sample (I), 1) with probability 1/m, for each with ai,j 1. The distribution Dj similarly returns (zzz, -1) with probability 1/m, for each j with dijj = Observe that these distributions can be described using n bits each.
Now consider running the multi-distribution learning algorithm A on distributions DT DT,DT.. Di...., .,, Di D to obtain a deterministic classifier f X {-1,1). Evaluate f on Ti. H, and compute er.p This can be done trivially polynomial time using the definitions of the distributions. If (f) 1/2 + E, then output that there exists 1)1, such that Az = O. Otherwise, output that no such 2 exists. Clearly this runs in polynomial time. It thus
remains to argue correctness.
Consider first the case where there exists = E {-1, 1] with A= 0. Since has inner product with every row of A, it follows that it assigns to precisely half of the non-zero entries of the i-th row and to the remaining half. The labeling z of r1,..., Fy thus has er (=) = er D- (=) = 1/2 and (r = 1/2. Furthermore, since ......; In are shattered by H. it follows that minkeR erp (h) < 1/2. By correctness of A, must hold with probability at least 2/3 that we correctly output that there exists with Az 0.

---

Consider next the case that every 2 E 1-1,11 1 nMh has J|Az|lee 2 cvn. It follows that there is row as such that the vector v (f(x)), ..... ... : (x,)) has 'e" ail 2 cyn. Let a sign(v" az). Then
e m j.0q.5
Σ lff(z)) = m4
1
(1/2)((zz))++11
3:Ri,5
1/2+ 2m
1
Σ
f(zz)o 1122+
σe a;
2m,
j=at,==1
|u''asl
= 1/2 2m,
2 1/2 + c/
Since we chose n = min /d, e² (2/(42)), we have c2(2m) 2 and thus we return with probability that all E (-1 have || 2 cvnn.
Let us end by observing that the distributions used in the above hardness result have OPT > 1/2. The proof can be modified to prove lower bounds for smaller OPT by adding a dummy point xo and letting all distributions return (zo: 1) with probability 1 20PT' and the points in the above distributions with probability 2OPT"/m4 This reduces the value of OPT to around OPT'. However, we also need to reduce n to min(d, /,, (c- OPTT/=)3) This agrees well with the fact that for realizable multi-distribution learning, i.e., OPT = 0, it is in fact possible to compute a deterministic classifier in polynomial time.
3 Deterministic multi-distribution learner
In this section, we give our algorithm for derandomizing multi-disstibution learners for label- consistent distributions, i.e., we assume Di(y x>) = =Dy(y x)) for all i,
We start by presenting the high level ideas of our algorithm. Recall that we defined OPT minAeH erp (h), where P {Di...., Dx First, consider running any of the previous ran- domized multi-distribution learners, producing distribution F over hypotheses in H satisfying max, E perp, (f) < OPT + e/2. Consider randomly rounding this distribution to a deter- ministic classifier f as follows: For every x X' independently (recall that we focus on finite domains), sample an ʃ F and let f(x) = (xx). For any distribution D, we clearly have OPT + e/2. However, as also discussed in the introduction,
EylorD, (f) E (erp, (f) S
not clear that we can union bound over all k distributions and argue that erp, (f) S OPT + for all of them simultaneously. Notice however that the independent choice of f(x)) for each x gets us most of the way. Indeed, if we let Ze be random variable (determined by f(z)) giving Pr Pry-DDalz)]f(C * w]. then er (f) = Erex D.(x) Zz. where D:(r) denotes the probability of x under D, and (2 x) gives the conditional distribution of the label given æ. Now notice random variable taking values in { (1/2 - (3, (1/2 + [8x1)D((x)} where B2 = Pr, Pry-Di((la) |u = 1] 1/2 denotes the bias of the label of æ. Furthermore, these random vari- ables are independent. We also have Elerp, (f) Ey-r(err,([)) Thus by Hoeffding's 's inequality
that (x)
e²
Pr[ erp (f) - E (0) > s/2] < 2 exp
2 Exex X.EExx23,,2 (z)))
Examining this expression closely, we observe that this probability is small if (,D,(x) is small for all x E X.
Using this observation, our algorithm then starts by drawing Ō(=-2) samples from each distribution D; and collecting all x for which the fraction of I's and -1's is so biased towards either 1 or -1, that the majority label almost certainly equals (3xn We then let (xx equal this majority label for all such x, and put these into set T.
What remains all x & T. Here we show that these x have so little bias, i.e., ,3 (a(x) is so small, that the random rounding strategy above suffices. The full algorithm is shown Algorithm
Before giving the formal analysis of the algorithm, note that storing the classifier f is quite expensive, as need to remember the random choice of f(x) for every X \ T. This is one place where we
5

---

Algorithm 1: DETERMINITIC s, A)
Input:
Distributions (Pi...., D Precision 0, failure probability randomized multi-distributton learner A.
Result: Classifier f: X + [-1,1}.
Let C > 0 be large enough constant.
2 Let 7 Ck)(s)).
Let T 0.
Run A with p = (Di...., D and as input, precision s/2 and failure probability 6/2 to obtain distribution F over classifiers in H.
5 for = 1.....k. do
Draw m C'In" (r)/s² samples {( B;)) from D;. 7 For every x E X T such that f4 := [j: = x > 0, let
Pi,z (1{j I
A yj 1} Hj 2, A y =-1))//m,
For every X T' such that ni, if pt. /n(()//m,,.) add x to T and let
f(x) sign (ign(Pi,.)
For every X T. independently draw an f and let f(x) f(z).
return f
10
the assumption that X' is finite. Note however that even for finite X, storing |X| random choices represent the classifier might be infeasible. Furthermore, the sampling of f(x) for every also adds | to the running time, which is again too expensive. We propose method for reducing the storage and running time requirement later in this section. For now, we analyse Algorithm T without worrying about [
Analysis. In our analysis, we separately handle T and & T. The two technical results need are stated next. First, define the hias 32 of an x E N' as Pry 1] 1/2. We say that an x is heavily biased if
D. 8. 1n(4///)))
for at least one i, and lightly biased otherwise. Intuitively, our algorithm ensures that T contains all heavily biased and that all predictions made on x E T are correct. This stated in the following
Lemma It holds with probability at least 8/4 that every heavily biased x is T, and furthermore, for every I T, we have f(x) = s3gn(3x).
Next, we also show that random rounding outside T suffices.
Lemma 5. Assume every heavily biased x is in T after the for-loop. Then with probability at least 1 - 8/4 over the random choice of f(x) with x E X \ T. it holds for all that
Ei-r (E 11x (T))() # wb1l B(a.))-,, $ T f(x) + v}1 S se/2.
Before giving the proof Lemma and Lemma 5 let us use these two results to complete the proof of Theorem 2
Proof of Theorem From a union bound and Lemma and Lemma 5 we have with probability 1 - 8, that all of the following hold
The invocation of A in step 1 of Algorithm returns distribution F with max; Ey-r (y-r(erd,())) s OPT + e/2.
For every x E T, we have f(x) = (3gn
For every distribution D,,
[ EB [1rr ((x) + ulll - E (1xx T (T
+ w1ll S se/2.

---

Assume now that all of the above hold. We rewrite (fp(f) by splitting the contributions to the error into x E T and & T.
crp(f)
max maxerp (f)
max E + wtl (e $ f(x) + wBl)
Using that f(x) = sign(3,) for x E T. we have B(z,)) [1fz E T f(x) * w = + v}}. Thus the above bounded by
( [B,
max
min (2(1-1,17
E LL T (z + yHl HEr 14 FT v + +
Since every f in the support of is deterministic classifier, we have
min ED, 11 E T AA # y - BBt 1B # =f1-11)
We therefore have
erp(f) (f) I max max Baxxery (f)l+
B/ f(z) f +/2
<PT+
This completes the proof of Theorem
Proof of Lemma 4
We first define the two types of failures that may occur:
For every and every with (2)((x) =2/(8In(4k00)) let E denote the event that ni, < (C/2)) Iny.
For every i, let E denote the event that there is an x with ni > 0 and B3g pi,z/21 (16,))
Assume first that none of the which (x) > x² /88 (n(4k/6)). Since E does not occur, we have ni, 2 3, In
occur. Consider heavily biased Then there is i for
Since E? does not occur, we also have 13g- - -t,,//22 S (Im(1)/(16m,.)) Hence |pt.el 2 2 But |3.l 2 V(C/2) (e()))((r)///.))))) and thus |pt.z| 2 (V2C - 1/2) /In(7)/;; For C large enough, this is at least /In(7)/ni.z. which puts æ in T during step 8 of Algorithm
2 2/1n(>)/(6nn,
Thus every heavily biased the for-loop, we have |pt.z| > /in(7)/nu,n Since E? does not occur, we have 13, -Pi,n/2) < )l But this implies 3n E 22,,2/2 - (1(())/(16n,,))) Pt,z/2 + v /In(7)/(16nn,)) Since |pt.-| /In(T)/mi,, every number in this interval has the same sign Pi.z, i.e. f(x) sign(Pi,x) = sign(3z). Thus what remains is to bound the probability of these events.
T. Secondly, note that when an x is added to T in iteration
For E fix and with (x),(x) > ² In (an44//0)) /)), we have E|n,,=] (2(x) m/ In 4k/))) > 18-21n7.
For C large enough, we get from Chernoff bound that Pr[E = Pr|m,, < (C/2)8=2ln7l < 7
For E?, let us first condition on an outcome of the values n4, for all Φ. Then for every x, we have that pi,r == Kj I, x A y = 1}1 Kīj 2 = A Vj = =-1] is distributed as the sum of ni.x independent 11/1 random variables taking the value with probability 3, + 1/2. Hence Elps,z] 23 Since Pi.z= Pi.a/ /n/n. it follows from Hoeffding's inequality that
33 - Pi.z > In(7)/mis
Pr 123 - -iiaa >2/1n(7)ma
8ln(7) = 27
2 eexp
4n
7

---

For any fixed values n1 there are at most m distinct r with non-zero 4, A union bound over all of them implies Pr| Pr[E
E n4.0] < 2my-2 Since this upper bound holds for any outcome of the f4,,* we have also Pr[Eβ] I 2my
We now observe that for every i, there are at most E 2 In (4k/6) distinct with (x),()) > e² e²/(8 (((k)()))))) Hence Pr(U, I E 2-28 281n(4//6)) A union bound over all finally implies
Pr[[U: Uz E...) U (U,E - ky (e 28 (m + 2m)
Since ? (c6( and m C'n (r)/ we have for large enough C that this probability is bounded by 8/4.
Proof of Lemma Fix distribution Dj. Observe that for any x E X \ T, we have that the distribution of f(x) is the same as f(x) for f ~ F. Hence (y(E(aw)>,, [1f2 $ T A f(x) + vHll = Ey-r(B(,,)> [1 & TA f(x) # yH]]. Denote this expectation by If we let Zrr be the random variable (as a function of f(x)) taking the value Pry-Di(ola) (f(x) + v]. then
E (zz,)) T f(x) # y)l
E Di(x) TEXIT
Observe that Z is either 1/2- 1/ or 1/2++ 1.2 depending on whether f(x) = sgg or not. Hence (x)x) Z E (1) 1, (1(2 [321)] and the Zy are independent. We thus get from Hoeffding 's inequality and that æ & T are lightly biased that
2({/222
Pr
Σ TEXAT
D,(x) > M
<
exp
(23,,,,,)))
-62 ExEry D,(x) / In(4k//5)
exp
exp
(- In(4k/8)) = 8/ 6/(4k).
A union bound over all D completes the proof.
3.1 Reducing storage and time
The above description of Algorithm requires the storage of an independent random choice of f(x) for every X. This is infeasible for large X, both in terms of space usage and the time needed for making these random choices. Instead, we can reduce the storage requirements by using an r-wise independent hash function g X + Yd for sufficiently large output domain ) to make the random rounding. Recall that an r-wise independent hash function hashes any set of up to r distinct keys Ii, .......,........................ F, independently and uniformly random into y. Such hash function can be implemented in space O(r [n( [D')) bits and evaluated in time Ö(r (I(())(()))) by e.g., interpreting
X as an index into [| (o..... |X| 1} and letting q(z) Exzo aqz"(mode for a prime |>| > [2'] and the a independent and uniformly random in [p]. Using fast multiplication algorithms, 4(x) can be evaluated in time Ö(r In((x(|[)')) even when In([x(())))) bits does not fit in machine word. The time to sample the hash function only (rr In [DI) (we just need the random coefficients of the polynomial).
Instead of storing f(x) for every x E X A\ T explicitly, the learning algorithm instead stores and the distribution F. Given this information, we evaluate f(x:) by computing g(z) and letting f(z) 1 if q(x) < Pr)~s(f(z)
and -1 otherwise. Since g(z) is uniform over Y for any x, we have Pr(f(x) = = |PT/~eif(2) = 1|D')1/!? This probability satisfies Prバ~e [f(x) =
1}
1] and is thus almost the same rounding probability as in Algorithm [] Since previous multi-distrinne distributionn learning algorithms also store F, this only adds O(r In( [D()) bits to the storage.
1/|2 Pry [f(x)= = =Ptppll((()
What remains to determine an r and | for which this sufficient for the guarantees of Algorithm We will show that
2 (2 and | @ In(k/8)) suffices if we increase the sample
8

---

complexity of Algorithml] 1 by logarithmic factor. Observe that the O(r ((rIn( In /=(/))/=)) extra bits is only proportional to storing (ll()//)) samples from X, provided that in (k/k////// (6/6)/ no larger than polynomial in [ The space overhead is thus very minor.
We only give outline of how to modify the proof in the previous section to work with r-wise independence as it follows the previous proof rather uneventfully. First, redefine the threshold for being heavily biased to (x)) > =²/((C In (4k/6)) for large enough constant C².
For the proof of Lemma 4 to still go through, this requires us increase m by C' l factor, i.c. to CC"In (n)(/=²" and also increase by C" to CC*k/(=6). Then the only change to the proof, is that we have an event Ei,- for every i and every x with (x) > =²/(C" In"C"In"pp (4k:/)) Otherwise, all conditions in the events Ei and E remain the same. Thus the proof still goes through if we can argue Pr[E] I y=2 So fix an and x with (2)((z) > ="/((" (4k/6)) Then [x[ = Dz(x)m > s/mm/(C (tmm("""/ In (4k/8)) > C3,² In This is the same lower bound on Ef as the previous proof and thus we can complete the steps. Finally, note that we finished the proof of Lemma by a union bound. Here we needed 2 (e-22( 281n(4k/8) + 2m) < 6/4. This
still the case for our new m and
Now for the proof of Lemma 5 we used Hoeffding's s inequality. This requires the random rounding to be independent for different z. With our modified approach, the roundings are only riwise independent and thus we need the following variant of Hoeffding" inequality for r-wise independent random variables
Theorem 6 (117). Let Zi...., Zn be sequence of r-wise independent random variables for with I2; - E| S 1 for all outcomes. Let Z >i Zi with E|Z] and let o2) = E.00( (Zi)
denote the variance of Z. Then the following holds for even r and any Q 2 max o
r
f/2
Pr| - 14| 2 2
22/3T2
If we repeat the proof of Lemma
5 define Zy as the random variable (as a function of the random
choice of () taking the value Pr Pryv [f) # y). Note that Z, E {1/2 - | 2 + [8,r]. This
also implies that 124 B[Z,]] < 2| for all outcomes of Zz. When all heavily biased æ are in T,
we have (z))) S (CC( In (4k/5)) for all æ & T. This implies |&pt
Now let (In(4k/k))) Then
Di(x)
B( 11x & T A f(x) + fyll=
Σ Di(x)2a =a
Σ
ZEAiT
TEAVT
The random variable Dx(x) thus satisfies ( < 2D((r)l3
(Dx(z) 1 for all outcomes. This also gives us (D) aa) 3 Di(x) and thus
Dr
o²
Σ ZER'T
S Σ
Dz(x) 1
a
xEXiT
Now consider the expected value (with + b
(a b, a + b))
n1 = E Σ Dx(x)2o)
TEXII
= Σ Ey(
Pr [f(x) + yll ynDi(gla)
TEXVT
E Σ Di(x)
PEP (y)=)
Pr [zx + vlI + 1/D1)
TEX
C By
[1f $ T f(x) # Ulll + 1/D1I

---

Letting By=F ((.)) $ A f(x) # ytll. we then have by Theorem 6 with Q = r that
Pr
Σ Di(x)Z2- - p 2 aT
Pr
Σ
D1(x)Zo - v² 2 aT - -
TEART
FEALT
Di(r)Zz
Pr
11/0 T - a
TEXIT
,2
1/2
(2/3(T /x/11)/
Inserting T = e/(2)) and using r = 2ln(4k/6), | 2 4a /E gives (T a/(3')) 2 e/(4a) and
thus finally implies
Pr
(
-Bl [1fx $ T f(z) + will
N 2//2
116ra22 c2/3g2
(
1/2
64
(7266
r/2
256
r/2
1ne233
C'
C/22/3
5e- = =
Here, the last inequality follows for C' large enough. Thus, if we increase the sample complexity to m(k,d, d, OPT, e/2, 8/2) + In (k<)))()/ then we may sample and store a hash function time.
using only ((I(nn))
extra bits and ((n(n/0
3.2 Infinite Input Domains
In the above presentation of our algorithm, we have assumed a finite input domain X. While we believe this is a very reasonable assumption, we here present some initial ideas for how this restrictions might be circumvented.
Assume that the black-box randomized multi-disstibution learner AA always outputs a distribution F over finite number of classifiers in H. Let be an upper bound on the size of the support. Then since H has VC-dimension d, the dual VC-dimension is at most 2d (T. By Sauer-Shelah, this implies m
that the number of distinct ways E X' may be labeled by the support of F is bounded (2441) i.e. finite. We believe that treating just the distinct ways is labeled by the hypotheses in the support should be sufficient recover our results for finite X.
Acknowledgments
Kasper Green Larsen is co-funded by DFF Sapere Aude Research Leader Grant No. 9064-00068B by the Independent Research Fund Denmark and co-funded by the European Union (ERC, TUCLA, 101125203). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. Omar Montasser was supported by FODSI-Simons postdoctoral fellowship at UC Berkeley.
References
[1] P. Assouad. Densité dimension. Annales de I I'Institut Fourier, 33:233-22 282, 1983.
[2] Awasthi, N. Haghtalab, and Zhao. Open problem: The sample complexity of multi- distribution learning for VC classes. In G. Neu and L. 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.
[3] Ben-David and R. Urner. The sample complexity of agnostic learning under deterministic labels. In Conference Learning Theory, pages 527-542. PMLR, 2014.
10

---

[4] A. Blum, N. Haghtalab, A. D. Procaccia, and M. Qiao. Collaborative PAC learning. In I. Guyon, U. von Luxburg, S. Bengio. H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Gamett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 2392-2401, 2017.
[5] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the vapnik- chervonenkis dimension. J. ACM, 36(4))929-995 965, 1989.
[6] M. Charikar, A. Newman, and A. Nikolov. Tight hardness results for minimizing discrepancy. In D. Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Aigorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1607-1614. SIAM, 2011.
[7] J. Chen, Q Zhang, and Y. Zhou. Tight bounds for collaborative PAC learning via multiplicative weights.
Bengio, H. M. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 3602-3611, 2018.
[8] E. Diana, W. Gill, M. Kearns, K. Kenthapadi, and A. Roth. Minimax group fairness: Algorithms and experiments. In M. Fourcade, B. Kuipers, S. Lazar, and D. K. Mulligan, editors, AIES '21: AAAI/ACM Conference on AI, Ethics, and Society, Virtual Event, USA, May 19-21, 2021, pages 66-76. ACM, 2021.
[9] S. Floyd and M. K. Warmuth. Sample compression, learnability, and the vapnik-chervonenkis dimension. Mach. Learn 21(3):269-34) -04,, 1995.
[10] N. Haghtalab, M. I. Jordan, and E. Zhao. On-demand sampling: Learning optimally from multiple distributions. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35; Annual Conference Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 2022, 2022.
[11] M. J. Kearns and U. V. Vazirani. An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA, USA, 1994.
[12] M. Mohri, G. Sivek, and A. T. Suresh. Agnostic federated learning. In K. Chaudhuri and R. 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.
[13] H. I.. Nguyen and I.. Zakynthinou. Improved algorithms for collaborative PAC learning. In S. Bengio, H. M. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information P Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 7642-7650, 2018.
[14] B. Peng. The sample complexity of multi-distribution learning. CoRR, abs/2312.04027,, 2023.
[15] G. N. Rothblum and G. Yona. Multi-group agnostic PAC learnability. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 9107-9115. PMLR, 2021.
[16] S. Sagawa, P. W. Koh, T. B. Hashimoto, and P. Liang. Distributionally robust neural networks. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia. April 26-30, 2020, OpenReview.net, 2020.
[17] Schmidt, A. Siegel, and Srinivasan. Chernoff-hoeffdingg bounds for applications with limited independence. SIAM Journal Discrete Mathematics, 2(2):223-250, 1995.
11

---

[18] S. Shekhar, G. Fields, M. Ghavamzadeh, and T. Javidi. Adaptive sampling for minimax fair classification. In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan. editors, Advances in Neural Information Processing Systems 34; Annual Conference on Neural Information Processing Systems 2021, NewrlPS 2021, December 6- 14, 2021, virtual, pages 24535-24544 2021.
[19] M. Sipser. Introduction to the theory of computation. SIGACT News, 27(1):27-29, 1996.
[20] C. J. Tosh and D. Hsu. Simple and near-optimal algorithms for hidden stratification and multi-group learning. In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvári, G. Niu, and S. 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.
[21] L. G. Valiant. A theory of the learnable. Commun. ACM, (7(1))11144441111 1984.
[22] V. Vapnik and A. Chervonenkis. Theory of Pattern Recognition. Nauka, Moscow, 1974.
[23] Z. Zhang, W. Zhan, Y. Chen, S. S. Du, and J. D. Lee. Optimal multi-distribution learning, CoRR, abs/2312.05134, 2023.
4 Uniform Model of Computation
For a fully formalized NP-hardness proof, we technically need to define an input encoding of multi-distribution learning problem and argue that the sampling steps may be simulated by a Turing Machine. Furthermore, details such as whether the hypothesis set H. is part of the input or known to the algorithm also needs to be formalized. In this section, we discuss various choices one could make. We note that similar discussions and formalizations of learning in a uniform model of computation has been carefully carried out classic learning theory books 11.
First, we find it most natural that H is part of the learning problem, i.e. not an input to the algorithm, but is allowed to be "hard-coded" into the algorithm. This is the best match to standard learning problems, where c.g. the Support Vector Machine learning algorithm, or Logistic Regression via gradient descent, knows that we are working with linear models. Similarly, the input domain seems best modeled by letting it be known to the algorithm. One tweak could be that if the input is d- dimensional vectors, then d could be part of the input to the algorithm. This again matches how most natural learning algorithms work for arbitrary d (and our proof needs d to grow for our to grow).
Now regarding modeling multi-distribution learning, we find that the following uniform computational model most accurately matches what the community thinks of as multi-distribution learning (here stated for the input domain being n-dimensional vectors and the hypothesis set being linear models).
solution to multi-distribution learning with linear models, is a special Turing machine M. M receives as input a number n the input tape. In addition to a standard input/output tape and tape with random bits, M has a "sample"-ta -tape, a "target distribution" -tape and a special "sample"-stae staate. the bits the "target distribution" tape is interpreted
When M enters the "sample"-stare in and the contents of the "sample"-tar ttape is replaced by a binary description of a fresh sample from a distribution D; (D, is only accessible through the "sample" -statee A natural assumption here would be that D; is only supported over points with integer coordinates bounded by n in magnitude. This gives natural binary representation of each sample using n log n bits, plus one bit for the label.
an index
M runs until terminating in a special halt state, with the promise that regardless of what n distributions Di..... Dn over the input domain that are used for generating samples in the "sample"sstate it holds with probability at least 2/3 over the samples and the random bits on the tape, that the output tape contains binary encoding of a hyperplane with error at most + 1/n for every distribution D, A bit more generally, we could also let it terminate with an encoding of a Turing machine on its output tape. That Turing machine, upon receiving the encoding of n and n-dimensional point on its input tape, outputs a prediction on its tape. This allows more general hypotheses than just outputting something from H.
The above special states and tapes are introduced to most accurately represent multi-distribution learning. Now observe that our reduction from discrepancy minimization still goes through. Given
12

---

such special Turing machine M for multi-distributin learning, observe that we can obtain standard (randomized) Turing machine M' for discrepancy minimization from it. Concretely. in discrepancy minimization, the input is the integer n and an in our reduction, we can easily compute n shattered points for linear models, e-g. just the standard basis c1,..., Cn. Now do in our reduction and interpret each row of A as two distributions over Stapee et...., En. M' can now simulate the "sample"-stee -state "sample" -tape and "target distribution" " tape of M. as it can itself use its random tape to generate samples from the distributions. In this way, M' can simulate M without the need for special tapes and states, and by the guarantees of M (as in reduction), it can distinguish whether A has discrepancy 0 or S2( (n)) by using the final output hypothesis of M and evaluating on ci...., Cn and computing the error on each of the (known) distributions D. obtained from the input matrix A.
binary matrix A. As mentioned
Note that the reduction would also hold if we rephrased multi-distribution learning such that the algorithm receives some binary encoding of ......: D, input. This would make the reduction even more straight-foree forward, as we need not worry about samples. However, we feel the above definition with special state and tapes for sampling more accurately represent multi-distribution learning from a learning theoretic perspective. We thus prefer a slightly more complicated reduction as above to better model the problem.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The theoretical claims are stated in the introduction and abstract. They match the contribution the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in 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 be expected to generalize other settings.
It is fine 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 of the work performed by the authors?
Answer: [Yes]
The paper is theoretical, so given the assumptions of the claims, there are no limitations. However, we discuss that our paper does not exclude the existence of inefficient deterministic predictors (see introduction).
Justification:
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 a 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 on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
13

---

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 to 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 fairness.
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 It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an 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
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
The paper includes all proofs of all claims in the main text.
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 provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs 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 of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: The paper is theoretical, and we have no experiments, data or code in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be 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 is 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 possible for others to replicate the model with the same dataset, or 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 to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
14

---

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 a new algorithm, the paper should make 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)
If the contribution is new model (e.g., . a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset 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 (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: 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?
Answer: [NA]
Justification:
The paper is theoretical, and we have no experiments, data or code in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
public/guides: Saglli/cuulaas//ddeeuuuiisssssss
for more details.
While encourage the release of code and data, we 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 NeurIPS code and data submission guidelines (https
for more details.
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 the paper) is recommended, but including URLs to data and code is 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 is theoretical, and we have no experiments, data or code in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
15

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper is theoretical, and we have no experiments, data or code in the paper.
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, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error 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 to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper is theoretical, and we have experiments, data code in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:p::///arrrp...ccpppbb//eeee
Answer: [Yes]
Justification:
We no violations of the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
16

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in 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: The result of the paper is theoretical/foundatinnal research, so we have no experiments, data or code in the paper.
Guidelines:
The answer NA means that there 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.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeett 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 partieular 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 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 a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as 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
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, scraped datasets)?
Question:
Answer: [NA]
Justification: The paper theoretical, and we have no experiments, data or code in the paper.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a 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 encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: 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?
17

---

Answer: [NA]
Justification:
The paper is theoretical, and have experiments, data code in the paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if 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 of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's ' creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper is theoretical, and have experiments, data code in the paper.
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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an 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 sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper theoretical, and we have no experiments, data or code the paper.
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
18

---

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 on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper is theoretical, and have experiments, data code in the paper.
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 expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
19


Reviews:
[{"review_id": "sxTg4fZ6TB", "reviewer": "Reviewer_xqfu", "summary": "The paper studies the problem of multi-distribution learning in the agnostic setting. The authors provide a a computational lower bound for deterministic classifiers (based on some mild assumption on the hypothesis class, and the assumption $\\text{BPP}\\neq \\text{NP}$), as well as an upper bound: an improper deterministic classifier for a special case of label-consistent distributions (i.e. when $D_i(y | x) = D_j(y | x)$ for all $i,j,x$). Their classifier uses a randomized learner as a black box, and its sample complexity is just almost the same as the sample complexity of the randomized learner.", "questions": "As I already mentioned, it is not clear how restrictive label-consistency is. I'm not an expert in the area, and this assumption looks natural to me, but how is it related to standard assumptions? Was it already studied in prior works?", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The results look interesting to me, they are non-trivial and novel (though I'm not an expert in the field, so I might have a wrong impression). The assumption of label-consistency looks natural to me, though it is not clear to me how restrictive it is.", "weaknesses": "While the results look new and non-trivial, I am not sure how strong the technical contribution is. I did not check the proofs in detail, and at the first glance the ideas don't look very sophisticated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your review. Regarding label consistency, please note that lines 81-86 compare it to the previous definition of deterministic labels by Ben-David and Urner. According to their results, in the case of a single distribution, deterministic labels are statistically almost as hard as the general agnostic case. Clearly our definition is more general and thus our results at least as strong. Furthermore, notice that our definition of label-consistency reduces to the precisely the standard agnostic PAC learning setup when there is just one data distribution. Let us also add that our definition was inspired by the lower bound construction, see lines 75-76. We made the most general definition of data distributions that we could come up with that still allowed circumventing the hardness results. To the best of our knowledge, the exact definition we use has not been studied before. However, this might not be too surprising as it only makes sense in a multi-distribution setting.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "a8T6L7l1ai", "reviewer": "Reviewer_QSLG", "summary": "This paper considers the *multi-distribution learning* setting of Haghtalab et al. (2022), where, given $k$ unknown data distributions $\\\\{\\\\mathcal{D}_1, \\\\dots, \\\\mathcal{D}_k\\\\}$, the goal is to find a classifier $f: \\\\mathcal{X} \\\\rightarrow \\\\{-1, 1\\\\}$ such that $f$ performs almost as well as $\\underset{h \\in \\mathcal{H}}{\\min} \\underset{i \\in [k]}{\\max} \\underset{{(x, y) \\sim \\mathcal{D}_i}}{\\mathrm{Pr}}[h(x) \\not = y]$ on every distribution $\\mathcal{D}_i$ for $i \\in [k]$.\n\nThe paper has two main results. The first is a negative result that states that, under mild conditions on $\\\\mathcal{H}$, any learning algorithm on $\\\\mathcal{H}$ that produces a classifier $f$ satisfying multi-distribution learning must have either super-polynomial training time or $f$ must have super-polynomial evaluation time. This is done through a reduction to the NP-Hard problem of Discrepancy Minimization. The second is a positive result that states that, under the condition of *label-consistency* (the conditional distributions of all the distributions agree, for all $x \\\\in \\\\mathcal{X}$) and finite input space, there does exist a learning algorithm that produces a deterministic classifier $f: \\\\mathcal{X} \\\\rightarrow \\\\{-1, 1\\\\}$ satisfying multi-distribution learning. It produces this classifier via black-box access to an existing multi-distribution learning algorithm that outputs a randomized classifier.", "questions": "I had two major questions about the work: \n1. I was wondering about was whether it is possible to do such a de-randomization from scratch, i.e. without assuming black-box access to an existing multi-distribution learning algorithm. I wonder this because existing algorithms for multi-distribution, to my knowledge, all rely on applying Hedge (or a similar no-regret algorithm) to the $k$ distributions, which can be potentially expensive in situations with many distributions. I wonder if there are techniques to directly obtain a de-randomized classifier, potentially following the lines of the deterministic classifier for the realizable case.\n2. Did the authors consider any other assumptions besides label-consistency that might allow for a deterministic algorithm? \n\nThese last two questions aren't criticism on the work itself -- I was just curious if the authors thought about these issues.\n\nOne other thing that might be worth mentioning is that [Zhang et al. (2023)](https://arxiv.org/abs/2312.05134), Theorem 2 also presents a hardness result on derandomizing multi-distribution learning. However, their result is a statistical hardness result, while yours is computational. It would be helpful to put this paper in context perhaps with a couple of sentences in the Introduction.", "limitations": "The authors have addressed the limitations of the work on a theoretical basis in the main text (see \"Discussion of Implications\"). Because this is mainly a theory paper, negative social impacts or broader impacts to applications seem minimal.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, this paper is well-written and clear. I had no trouble following along with the arguments, and each proof is sketched out nicely before getting into the details. I believe the result does address an important issue in the multi-distribution learning literature, as I have personally found the fact that every existing multi-distribution learning relies on a randomized classifier predicting with a rather opaque distribution (usually obtained by running a no-regret algorithm) unsatisfying. \n\n**Originality:** The paper is original insofar as it provides the first (to my knowledge) derandomized classifier for the agnostic multi-distribution learning problem. I do wonder whether the algorithm itself can be made simpler, as it seems somewhat artificial to me to explicitly designate the outputs of our final classifier (defined as $\\hat{f}$) one-by-one through enumerating part of the input space $\\mathcal{X} \\setminus T$. That being said, taking the result as a purely a proof of existence, the work is novel and addresses an important question.\n\n**Quality:** The quality of the paper itself is good -- there are few typographical issues, the structure of the paper is clear, and the theorems are clearly presented. \n\n**Clarity:** There is no issue with clarity -- the authors have formatted the paper well, and the arguments are clearly presented.\n\n**Significance:** I believe the de-randomization question of multi-distribution learning to be significant, though more applied practitioners may view the paper as too theoretical. On the grounds that this is a learning theory work, however, this addresses an important question presented in COLT 2023 by Awasthi et al. (Open Problem: The Sample Complexity of Multi-Distribution Learning for VC Classes) through demonstrating a statistical-computational gap.", "weaknesses": "One potential weakness in the work is that the final deterministic classifier relies on explicitly defining the outputs for all $x \\not \\in T$ by sampling from the existing multi-distribution learner's distribution. I don't find this to be too much of a weakness, as I do think that it is interesting that a deterministic algorithm *exists* in the first place, but I imagine that this might be viewed as a strong assumption. Perhaps the authors can provide some text motivating this deterministic classifier and its somewhat unwieldy final form (maybe this can be done by a brief discussion on the size of $T$?).\n\nAnother point that the authors could address a bit more is how natural the assumption of label-consistency for the positive result is. There is a brief reference to Ben-David and Urner (2014), but it would be helpful to include a further discussion on this assumption in the context of PAC learning. It seems that this is closely connected to the predominant assumption in the *covariate shift* literature, but a further discussion on perhaps the results of Ben-David and Urner (2014) in the body of this paper would be helpful to judge the strength of this main assumption. This is especially important because we are considering it in the context of multi-distribution learning.\n\nFinally, there are a couple of suggestions I had that may clarify the presentation of the paper:\n\n1. It might be a bit clearer to define $\\underset{\\mathrm{er}}{\\mathcal{P}}$ on a separate line (not in Equation 1). Personally, I took a while trying to find where $\\underset{\\mathrm{er}}{\\mathcal{P}}$ was defined in the paper, and it's an important quantity.\n2. In the Introduction, I would've appreciated some quick details on the existing algorithm for the deterministic classifier in the realizable setting. A one or two sentence sketch would be sufficient.\n3. It is unclear to me why the claim just above \"Our contributions\" about using the random classifier and Markov's inequality is the \"best we can guarantee.\" Can you justify that this is indeed \"the best\" argument for using a classifier drawn from the distribution $F$?\n4. I was initially confused about which definition you were taking for *label-consistent learning*, as you write, \"As a particular model of label-consistent learning, one may think of the deterministic labeling setup...\" so initially I thought you were restricting the assumption for the positive result to the deterministic labeling case with $f^*: \\mathcal{X} \\rightarrow \\{-1, 1\\}$. I would make clear (perhaps in a Definition environment) the label-consistent learning definition is, rather, the $\\mathcal{D}_i(y \\mid x) = \\mathcal{D}_j(y \\mid x)$ for all $i, j, x$ assumption.\n5. Small nitpick: In Section 2, you don't define the matrix $A \\in \\mathbb{R}^{n \\times n}$ before presenting the definition of Discrepancy Minimization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your review.\n\nTo answer your questions:\n\nFor remark 3 regarding \"best we can guarantee\": Well, from the guarantees of a randomized multi-distribution learner alone, the claim in 42-44 indeed seem to be roughly the best possible. Consider for instance k distributions on a domain X of cardinality k. The labels of all k points in the domain are deterministically 1. There are k data distributions, where $D_i$ has all of its probability mass on the $i$'th point of the input domain. There are k hypotheses, each returning 1 on all but a single point where it returns -1. If we look at the randomized predictor that is uniform random over these k hypotheses, then for each $D_i$, the expected error is $1/k$. However, if we draw a hypothesis from the randomized predictor, then it will have error 0 on k-1 of the distributions and error 1 on one of them. Thus a factor k worse, i.e. Markov is the best we can hope for.\n\nFor Question 1 regarding de-randomization from scratch: Indeed this would be possible to attempt. Note however that by giving a general and efficient black-box reduction from randomized multi-distribution learning, we have made it easier to obtain good deterministic classifiers. Indeed, since it is easier to obtain a randomized one, we can just start with that. However, aiming directly for a deterministic classifier to begin with seems like an interesting direction for future research.\n\nFor Question 2 regarding other definitions: As also mention in our reply to reviewer xqfu and in lines 75-79, we came up with our definition of label-consistency by examining the NP hardness result. Concretely, we found the most general definition (least restrictive) that allowed us to circumvent the lower bound. As such, we did not consider other notions. As can be seen in our lower bound, the critical property of the lower bound instance is that the same input point can be assigned label -1 in one distribution and +1 in the other (both with probability 1). Any useful definition must at least prevent this, and our label-consistency seemed the most natural and least restrictive such definition.\n\n> One other thing that might be worth mentioning is that Zhang et al. (2023), Theorem 2 also presents a hardness result on derandomizing multi-distribution learning. However, their result is a statistical hardness result, while yours is computational. It would be helpful to put this paper in context perhaps with a couple of sentences in the Introduction.\n\nWe discuss this at the end of Introduction in lines 99-110.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zs0LeAsb2G", "reviewer": "Reviewer_2SLq", "summary": "This paper explores the setting of multi-distribution learning in the binary label setting, where the goal is to output a classifier that does well with respect to a set of distributions, rather than just a single distribution. In the agnostic case, all existing learning algorithms output a randomized classifier specified as a distribution over classifiers. The authors investigate to what degree this randomization is necessary, and show that in the most general case, de-randomizing may require super-polynomial training or evaluation time. On the positive side, they show that in the case where the set of distributions shares the same conditional label distribution for each covariate, they can give an algorithm for derandomizing a randomized classifier.", "questions": "- Is there any reason why the output is restricted to be a classifier rather than a deterministic predictor for the conditional distribution given x? Does allowing predictors to be outputted make the problem significantly easier?\n\n- Is there a reason why you provide sample complexity rather than runtime and evaluation time results for the label-consistent derandomization algorithm? This would be a better comparison to Theorem 1.", "limitations": "The authors adequately address the assumptions they make and the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is written very clearly, and the proofs and statements are easy to follow, and seem to be correct. \n\n- The question of hardness of derandomization for multidistribution learning seems well motivated, and the hardness result requires minimal assumptions and is proved through an elegant reduction.", "weaknesses": "- It would be great to have some discussion of other related areas where a learning process outputs a randomized predictor that could be derandomized, such as in no-regret learning. \n\n- Similarly, the label-consistent setup seems equivalent to the problem of learning with covariate shift, and comparing the results to prior work in this area would be useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the review.\n\nFor question 1 on predictor for the conditional distribution: If we interpret your question correctly, you are asking whether it would be sensible to ask only that on a given x, we output Pr[y = 1 | x] and Pr[y = -1 | x] instead of a prediction of the class. While this is very natural, like in logistic regression, a central question is what happens to the loss function? Should one instead use a logistic loss rather than a 0/1-loss? While this is an interesting direction for future research, multi-distribution learning in this setup would be a completely different problem and a new question in its own right. Whether easier or harder seems difficult to say at this time.\n\nFor question 2 on why sample complexity: You are correct that it would have been natural to also mention the runtime. Our focus on sample complexity was due to previous works focussing on sample complexity, and we wanted to demonstrate that one can maintain optimal sample complexity. However, our reduction itself is efficient, except possible for the black-box application of randomized multi-distribution learning. We will thus expand our theorem to say that we can solve the deterministic learning problem with a runtime that equals the randomized version, plus a small (linear in the sample complexity) additive term. Regarding the running time of randomized multi-distribution learning, note that some but not all of the previous algorithms are computationally efficient. The algorithm by Haghtalab et al. uses Hedge on the hypothesis class, and as such is not efficient. However, the more recent algorithm by Zhang et al. is computationally efficient if Empirical Risk Minimisation is efficient for the hypothesis class. This efficiency translates to the deterministic setting by our reduction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cZNqwlWtLt", "reviewer": "Reviewer_x5BR", "summary": "Multi-distribution learning is an extension of the agnostic learning setup which defined as follows. Given a collection of k distributions $(D_1, …, D_k)$ over the domain $\\mathcal{X} \\times \\\\{\\pm 1\\\\}$ and baseline hypothesis class $\\mathcal{H}$ find a (potentially randomized) classifier $f: \\mathcal{X} \\to \\\\{\\pm 1\\\\}$ such that its *worst-case* loss $\\max_{i \\in [k]} \\mathbb{E}_{f \\sim \\mathcal{F}}L_i(f)$ is competitive with that of the best fixed classifier in $\\mathcal{H}$. Here, $L_i$ denotes the zero-one loss $L_i(f) = \\Pr_i[f(X) \\neq Y]$ where the probability $\\Pr_i$ defined is over $(X, Y) \\sim D_i$.\n\nPrevious work has shown that one can construct *randomized* classifiers (i.e., a distribution $\\mathcal{F}$ over classifiers) that succeeds in multi-distribution learning with sample complexity proportional to the VC dimension of the baseline class $\\mathcal{H}$. This work addresses the question of whether it is possible to efficiently \"derandomize\" such classifiers to achieve multi-distribution learning with a *deterministic* classifier. The main contributions are twofold.\n\n1. Learning a deterministic classifier in the multi-distribution learning setting is *computationally* hard since **discrepancy minimization**, which is an NP-hard problem, reduces to multi-distribution learning. \n2. If we assume that the given distributions $(D_1,...,D_k)$ share a common conditional distribution $f^*(x) = \\Pr[Y = 1|X=x]$, then derandomization is possible by \"essentially\" (see comment below) labeling *each* $x \\in \\mathcal{X}$ with independently drawn classifiers $f \\sim \\mathcal{F}$.\n\n\"essentially\": the statement is true for marginal distributions with high min-entropy. For distributions with \"heavy\" atoms, there is a simple fix; if $x$ is a heavy element, estimate the conditional probability $f^*(x) = \\Pr[Y=1|X=x]$ with sufficient confidence (which is possible since $x$ is a heavy element) and label it with $\\mathrm{sign}(f^*(x))$.", "questions": "1. What is a formal definition of multi-distribution learning in the uniform computation model? Suppose we want to say a Turing machine M \"solves\" multi-distribution learning. What are the inputs to M? Is it the collection of distributions $(D_1,...,D_k)$? Does it also include the baseline class $\\mathcal{H}$? How are these inputs represented?\n\n2. Are there well-founded reasons to prefer deterministic classifiers over randomized ones?\n\n3. Could the authors elaborate on why the restriction to finite domains seems to be a mere proof technicality? What are some steps towards establishing the \"rounding\" result for continuous domains?\n\n4. In what sense can the storage requirement be reduced? It seems unlikely that *any* derandomized classifier can be compressed.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The main results of this work stem from simple but powerful observations. The insistence on learning *deterministic* classifiers turns the multi-distribution learning problem into a combinatorial one, which already suggests that some NP-hardness result could be right around the corner. The authors drive this intuition home by connecting the multi-distribution learning to discrepancy minimization, which is known to be NP-hard. This connection, though simple to establish, appears to be fundamental and may lead to exciting opportunities for cross-pollination between learning theory and discrepancy theory. Below is a technical description highlighting the key insight of the main reduction.\n\n**Reduction from discrepancy minimization.** Discrepancy minimization is defined as follows. Let $c > 0$ be any fixed constant. Given an $n \\times n$ matrix $A \\in \\\\{0,1\\\\}^{n \\times n}$ distinguish between the case where 1) there exists $z \\in \\\\{\\pm 1\\\\}^n$ such that $Az = \\mathbf{0}$ and 2) $||Az||_\\infty \\ge c \\sqrt{n}$ for all $z \\in \\\\{\\pm 1\\\\}^n$. For some constant $c > 0$, this problem is NP-hard.\n\nThe authors' key insight is the following. Consider two \"antithetical\" distributions $D_1, D_{-1}$ where $D_1, D_{-1}$ share the same marginal distribution $\\mu_1$ supported on an $n$-point set $\\\\{x_1,...,x_n\\\\}$ but $D_1$ assigns all the mass on the set $\\\\{(x,1) | x \\in \\\\{x_1,...,x_n\\\\}\\\\}$ and $D_{-1}$ only on $\\\\{(x,-1) | x \\in \\\\{x_1,...,x_n\\\\}\\\\}$. Then, the worst-case zero-one loss achievable w.r.t. $D_1,D_{-1}$ by *any* classifier is 1/2. Moreover, any *deterministic* classifier that achieves the optimal value OPT = 1/2 \"perfectly balances\" the $n$ points $x_1,...,x_n$ w.r.t. the marginal measure $\\mu_1$. Let $A_i \\in \\\\{0,1\\\\}^n$ be the $i$-th row of the discrepancy instance $A \\in \\\\{0,1\\\\}^{n \\times n}$. If there exists $z \\in \\\\{\\pm 1\\\\}^n$ such that $A z = \\mathbf{0}$, then $A_i z = 0$. We can convert each row $A_i$ into a pair of distributions $D_{i}, D_{-i}$ such that OPT=1/2 if and only if there exists $z \\in \\\\{\\pm 1\\\\}^n$ s.t. $Az = \\mathbf{0}$.\n\nNote the minimal role of the baseline class $\\mathcal{H}$. All we require is that $\\mathcal{H}$ shatter the $n$-point support $\\{x_1,...,x_n\\}$. A sufficient condition that satisfies this is $\\mathrm{VCdim}(\\mathcal{H}) > n$.", "weaknesses": "While this work constitutes a solid contribution to learning theory, it falls a little short in the following aspects.\n\n**Formal definition of a mutli-distribution learning in the uniform computational model?** While the key idea behind the reduction from discrepancy minimization is clear, some formalities in making the reduction rigorous seems to be missing. NP-hardness is a notion defined for uniform computational models (e.g., Turing machines). To use NP-hardness of discrepancy minimization as the basis for the hardness of multi-distribution learning, one needs to define what it means to solve multi-distribution learning using Turing machines. Suppose we want to say a Turing machine M \"solves\" multi-distribution learning. What are the inputs to M? Is it the collection of distributions $(D_1,...,D_k)$? Does the input also include the baseline class $\\mathcal{H}$? How are these inputs represented?\n\nIn addition, computational complexity is an asymptotic notion which requires a *sequence* of problems, not just a single instance. For example, discrepancy minimization instances are binary matrices $A \\in \\\\{0,1\\\\}^{n \\times n}$, which can be seen as a sequence of matrices indexed by $n \\in \\mathbb{N}$.\n\nIt might be helpful to first define a concrete sequence of multi-distribution learning problems that have natural bit representations. For example, one might define the domain ${\\mathcal X}_n = \\\\{0,1\\\\}^n$, the collection $(D_1,...,D_k)$ to be distributions whose marginal on $\\mathcal{X}_n$ is supported on the standard basis $\\\\{e_1,...,e_n\\\\}$, and the baseline class $\\mathcal{H}_n$ to be the set of halfspaces on $\\mathbb{R}^n$. Then, one can show that for each $n \\in \\mathbb{N}$, there is an efficient algorithm that maps a discrepancy minimization instance $A \\in \\\\{0,1\\\\}^{n \\times n}$ to a collection of measures (in bit representation) $(D_1,...,D_k)$ which are all efficiently computable and sampleable.\n\n**Motivation for deterministic classifiers?** While I also lean towards deterministic classifiers over randomized classifiers, are there well-founded reasons to prefer deterministic classifiers? It would be helpful if the authors could provide more motivation behind seeking deterministic classifiers.\n\n**Restriction to finite domains for Theorem 2.** In page 3, lines 96-98, the authors say,\n> *The restriction to finite domains $\\mathcal{X}$ seems to be mostly a technicality in our proofs. Since any realistic implementation of a learning algorithm requires an input representation that can be stored on a computer, we do not view this restriction as severe.*\n\nCould the authors elaborate on why the restriction to finite domains seems to be a mere proof technicality? What are some steps towards establishing the \"random rounding\" result for continuous domains? What assumptions (e.g., smoothness of the \"true\" regression function $f^*$) are needed?\n\nIn addition, I respectfully disagree with the second part of the quote. For example, sample complexity results in learning theory are independent of whether they can be implemented on a computer or not. Without further investigation, it seems rather premature to claim that the restriction to finite domains is not significant.\n\n**Storage reduction seems unlikely**. I am having trouble understanding how the storage requirement for the derandomized classifier could be reduced at all. Consider the following example. Let $\\mathcal{X} = \\\\{0,1\\\\}^n$, let the marginal distribution be the uniform distribution over $\\mathcal{X}$, and let $f^*(x) = 1/2$ for any $x \\in \\mathcal{X}$. Suppose the randomized classifier is a uniform mixture of two constant classifiers: all-ones $f_1(x) = 1$ for any $x \\in \\mathcal{X}$ and all-neg-ones, $f_{-1}(x) = -1$ for any $x \\in \\mathcal{X}$. Then, the random rounding algorithm outputs a purely random truth table indexed by $\\mathcal{X}$. However, random truth tables are incompressible.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for the review.\n\nLet us answer question 1 last as it has the longest reply.\n\nQuestion 2: See also the discussion with reviewer QSLG  on remark 3. Furthermore, you only have Markov's inequality to bound the probability of performing significantly worse than your expected error. Indeed, the example outline for reviewer QSLG shows an expected error of 1/k, but with probability 1/k over drawing a hypothesis from the distribution, it might be as high as 1. A deterministic predictor on the other hand has a strong performance guarantee on all k distributions simultaneously.\n\nQuestion 3: Here is one approach that could probably generalize to continuous domains. Observe that if the VC-dimension of the hypothesis set H is d, then the so-called dual VC-dimension d* is at most 2^d. This implies that if the randomized multi-distribution learner that we invoke as a black-box has created a distribution over a set of M hypotheses, then the infinite input domain X really only consists of (M choose 2^d) distinct points (in terms of how they can be labeled by the M hypotheses). It would thus seem that one can restrict to a finite domain of this size when rounding.\n\nQuestion 4: The important point here is that we are NOT compressing the arbitrary derandomized classifier. Instead, what we show is that there is a small set of derandomized classifiers (those defined from the r-wise independent hash function), such that one of these will have an accuracy that is comparable to the randomized classifier. What this intuitively exploits, is that it is not necessary to independently round each and every single prediction in the input domain X. Instead, we can round them in a dependent way (but still r-wise independent) while maintaining roughly the same accuracy as the randomized classifier.\n\nQuestion 1:\nWe agree with the reviewer that we have not given a completely formal definition of multi-distribution learning in a uniform computation model. This was a choice based on who we thought would be the target audience at NeurIPS. But we'll certainly add such a discussion to the paper (possibly in Appendix). We also note this is related to classical treatments of efficient PAC learning (see e.g., book by Kearns & Vazirani). Here are some further thoughts on the matter:\n\nFirst, we find it most natural that $\\mathcal{H}$ is part of the learning problem, i.e. not an input to the algorithm, but is allowed to be \"hard-coded\" into the algorithm. This is the best match to standard learning problems, where e.g. the Support Vector Machine learning algorithm knows that we are working with linear models. Similarly, the input domain seems best modeled by letting it be known to the algorithm. One tweak could be that if the input is $d$-dimensional vectors, then $d$ could be part of the input to the algorithm. This again matches how most natural learning algorithms work for arbitrary $d$ (and we need $d$ to grow for our $n$ to grow).\n\nNow regarding modeling multi-distribution learning, we find that the following uniform computational model most accurately matches what the community thinks of as multi-distribution learning (here stated for the input domain being $n$-dimensional vectors and the hypothesis set being linear models).\n\nA solution to multi-distribution learning with linear models, is a special Turing machine M. M receives as input a number $n$ on the input tape. In addition to a standard input/output tape and a tape with random bits, M has a \"sample\"-tape, a \"target distribution\"-tape and a special \"sample\"-state. When M enters the \"sample\"-state, the bits on the \"target distribution\" tape is interpreted as an index in $i$ and the contents of the \"sample\"-tape is replaced by a binary description of a fresh sample from a distribution $D_i$ ($D_i$ is only accessible through the \"sample\"-state). A natural assumption here would be that $D_i$ is only supported over points with integer coordinates bounded by $n$ in magnitude. This gives a natural binary representation of each sample using $n \\log n$ bits, plus one bit for the label.\n\nM runs until terminating in a special halt state, with the promise that regardless of what $n$ distributions $D_1,\\dots,D_n$ over the input domain that are used for generating samples in the \"sample\"-state, it holds with probability at least $2/3$ over the samples and the random bits on the tape, that the output tape contains a binary encoding of a hyperplane with error at most $\\tau + 1/n$ for every distribution $D_i$. A bit more generally, we could also let it terminate with an encoding of a Turing machine on its output tape. That Turing machine, upon receiving the encoding of $n$ and an $n$-dimensional point on its input tape, outputs a prediction on its tape. This allows more general hypotheses than just outputting something from $\\mathcal{H}$.\n\nNow observe that our reduction from discrepancy minimization still goes through. Given a special Turing machine M for multi-distribution learning, observe that we can obtain a standard (randomized) Turing machine $M'$ for discrepancy minimization from it. Concretely, in discrepancy minimization, the input is the integer $n$ and an $n \\times n$ binary matrix $A$. As mentioned in our reduction, we can easily compute $n$ shattered points for linear models, e.g. just the standard basis $e_1,\\dots,e_{n}$. Now do as in our reduction and interpret each row of $A$ as two distributions over $e_1,\\dots,e_{n}$. M' can now simulate the \"sample\"-state, \"sample\"-tape and \"target distribution\" tape of M, as it can itself use its random tape to generate samples from the distributions. In this way, M' can simulate M without the need for special tapes and states, and by the guarantees of M (as in our reduction), it can distinguish whether $A$ has discrepancy 0 or $\\Omega(\\sqrt{n})$ by using the final output hypothesis of M and evaluating it on $e_1,\\dots,e_n$ and computing the error on each of the (known) distributions $D_i$ obtained from the input matrix $A$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the recently introduced talk of multi-distribution learning, where roughly speaking the goal is to find a classifier that performs well simultaneously over multiple distributions. Prior work had shown how to obtain randomized classifiers for this task with sample complexity proportional to the VC dimension of the base class. The current work gives two results: (1) First it is hard to construct a deterministic classifier in the general case, and (2) if an additional condition, termed label consistency, is satisfied one can obtain efficiently a deterministic classifier. The consensus from the reviews and discussion was that this is a technically worthy contribution that should be accepted to the conference.
Decision: Accept (poster)