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$.
Previous 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.
1. 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.
2. 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}$.
"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))$.
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.
**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.
The 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}$.
Note 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.
**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?
In 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}$.
It 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.
**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.
**Restriction to finite domains for Theorem 2.** In page 3, lines 96-98, the authors say,
> *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.*
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 "random rounding" result for continuous domains? What assumptions (e.g., smoothness of the "true" regression function $f^*$) are needed?
In 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.
**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.
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?
2. Are there well-founded reasons to prefer deterministic classifiers over randomized ones?
3. 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?
4. In what sense can the storage requirement be reduced? It seems unlikely that *any* derandomized classifier can be compressed.