Derandomizing Multi-Distribution Learning

Thanks a lot for the review.

Let us answer question 1 last as it has the longest reply.

Question 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.

Question 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.

Question 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.

Question 1: We 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:

First, 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).

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).

A 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.

M 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}$.

Now 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$.

Thank you for addressing my questions and being receptive. I've increased my ratings based on the authors' clarifications, especially their responses to my Q1 and Q2.

We thank the reviewer for the review.

For 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.

For 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.

Thanks a lot for your review.

To answer your questions:

For 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.

For 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.

For 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.

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.

We discuss this at the end of Introduction in lines 99-110.

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.