# The sample complexity of multi-distribution learning

Binghui Peng
Columbia University
<EMAIL_ADDRESS>
###### Abstract

Multi-distribution learning generalizes the classic PAC learning to handle
data coming from multiple distributions. Given a set of $k$ data distributions
and a hypothesis class of VC dimension $d$, the goal is to learn a hypothesis
that minimizes the maximum population loss over $k$ distributions, up to
$\epsilon$ additive error. In this paper, we settle the sample complexity of
multi-distribution learning by giving an algorithm of sample complexity
$\widetilde{O}((d+k)\epsilon^{-2})\cdot(k/\epsilon)^{o(1)}$. This matches the
lower bound up to sub-polynomial factor and resolves the COLT 2023 open
problem of Awasthi, Haghtalab and Zhao [AHZ23].

##  1 Introduction

Multi-distribution learning is a natural generalization of the classic PAC
learning [Val84] to multiple distributions setting. Given a hypothesis class
$\mathcal{H}$ and a set of $k$ distributions
$\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$ over the data universe
$\mathcal{X}\times\\{0,1\\}$, multi-distribution learning seeks for a
hypothesis $f$ that achieves near optimal worst case guarantee over all
distributions

$\displaystyle\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f)\leq\operatorname*{arg\,min}_{h^{*}\in\mathcal{H}}\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(h^{*})+\epsilon\quad\text{where}\quad\ell_{\mathcal{D}}(h):=\Pr_{(x,y)\sim\mathcal{D}}[h(x)\neq
y].$

The formulation of multi-distribution learning captures many important
applications: For fairness consideration, the distributions represent
heterogeneous populations of protected attributes and multi-distribution
learning yields the minimax group fairness [MSS19, SFGJ21, RY21, DGK+21,
TH22]; In the context of multi-task or federated learning, multi-distribution
learning captures the notion of robustness and yields worst case guarantees
[SK18]; For group distributional robustness optimization, multi-distribution
learning obtains uniform guarantee to all pre-defined groups of distributions
[RM19, SKHL19, SRKL20, DN21].

Similar to the study of PAC learning [BEHW89, AO04, Han16, Lar23, AACSZ23],
one important research question is to characterize the sample complexity of
multi-distribution learning. It is not hard to see that the learnability is
still captured by the VC dimension [VC71], and
$\widetilde{\Theta}(kd/\epsilon^{2})$ samples are both necessary and
sufficient to guarantee uniform convergence [BHPQ17]. There is a long line of
work [BHPQ17, NZ18, CZZ18, HJZ22, AHZ23] that try to pin down the optimal
sample complexity. In the realizable setting, where the optimal hypothesis
$h^{*}\in\mathcal{H}$ has zero error, [BHPQ17, NZ18, CZZ18] give algorithms of
sample complexity $\widetilde{O}((d+k)/\epsilon)$ using the idea of
multiplicative weight update. The sample complexity for the general agnostic
learning setting is more challenging. A recent breakthrough of Haghtalab,
Jordan and Zhao [HJZ22] gives an algorithm of sample complexity
$\widetilde{O}((k+\log(|\mathcal{H}|))/\epsilon^{2})$, this is optimal
assuming the hypothesis class $\mathcal{H}$ is finite. For infinite hypothesis
class, [AHZ23] gives two algorithms: One bases on the multiplicative weight
update and has sample complexity $\widetilde{O}((d+k)/\epsilon^{4})$; The
other bases on the finite hypothesis algorithm [HJZ22] and has sample
complexity $\widetilde{O}((d+k)/\epsilon^{2}+kd/\epsilon)$. Nevertheless,
there is still a significant gap between the upper and lower bound
($\widetilde{O}(\min\\{(d+k)/\epsilon^{4},(d+k)/\epsilon^{2}+kd/\epsilon\\})$
vs. $\widetilde{\Omega}((d+k)/\epsilon^{2})$), and as elaborated in the COLT
2023 open problem publication [AHZ23], fundamental barriers exist for all
current approaches. They pose the open question of obtaining the optimal
sample complexity for multi-distribution learning.

In this paper, we address the open question of [AHZ23] and give an algorithm
of optimal sample complexity (up to sub-polynomial factor). Our result is
formally stated as below.

######  Theorem 1.1 (Multi-distribution learning).

Let $k$ be the number of distributions, $d$ be the VC dimension of the
hypothesis class. For any $\epsilon>0$, there is an algorithm that outputs an
$\epsilon$-optimal classifier with probability $1-\delta$, and has sample
complexity

$\frac{(d+k)\log(d/\delta)}{\epsilon^{2}}\cdot(k/\epsilon)^{o(1)}.$

An immediate implication of Theorem 1.1 is that multi-distribution learning is
no harder than (single-distribution) PAC learning for sample complexity
consideration.

###  1.1 Technical overview: Achieving optimal sample complexity via recursive
width reduction

We give an overview of our algorithm for Theorem 1.1, the key ingredient is a
recursive width reduction procedure.

#### The MWU framework

The major technique used by all previous works [BHPQ17, NZ18, CZZ18, HJZ22,
AHZ23] is the multiplicative weight update (MWU) framework [AHK12]. We first
review this framework. The algorithm views the $k$ distributions
$\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$ as $k$ experts and runs MWU for $T$
rounds. At each round $t\in[T]$, the algorithm performs empirical risk
minimization (ERM) and obtains an $\epsilon$-optimal hypothesis
$f_{t}\in\mathcal{H}$ over the mixed distribution
$\mathcal{D}^{(t)}=\sum_{i\in[k]}p_{t}(i)\mathcal{D}_{i}$. Here $p_{t}$ is the
strategy of MWU, and it is updated by the loss of $f_{t}$ over distributions
$(\mathcal{D}_{i})_{i\in[k]}$, i.e.
$\ell_{t}=(\ell_{\mathcal{D}_{i}}(f_{t}))_{i\in[k]}\in[0,1]^{k}$. The final
output is taken to be $f=\frac{1}{T}\sum_{t\in[T]}f_{t}$. The regret guarantee
of MWU ensures that the worst case error of $f$ over
$\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$ is close to the average error of
$f_{t}$ over $\mathcal{D}^{(t)}$, which is at most $\epsilon$. For the sample
complexity, in the realizable setting, the sample complexity per round is
$\widetilde{O}((k+d)/\epsilon)$ and $T=\Omega(\log(k))$ rounds are needed;
under the agnostic learning setting, the sample complexity per round is
$\widetilde{O}((k+d)/\epsilon^{2})$ and $T=\widetilde{\Omega}(1/\epsilon^{2})$
rounds are needed. It is not hard to see that both terms are tight in the
worst case and they form the major technical obstacle for obtaining the
optimal sample complexity.

#### Width reduction

Our approach also falls into this MWU framework and the key idea for
improvement is recursive width reduction. In the literature of online
learning, width refers to the maximum range of the loss vector, i.e.,
$\max_{i\in[k]}\ell_{t}(i)-\min_{i\in[k]}\ell_{t}(i)$. To get a quick sense of
how width reduction works, recall the regret guarantee of MWU equals
$O(\sqrt{\log(k)/T}B)$, where $B$ is the width of the loss vector $\ell_{t}$
and it equals $1$ in the above framework. In order to get $\epsilon$-regret,
one needs to take $T\geq\widetilde{\Omega}(1/\epsilon^{2})$. If one can reduce
the width, then it immediately reduces the number of iterations for MWU, and
consequently, reduces the sample complexity.

For now, we assume the optimal error
$\operatorname{OPT}:=\min_{h^{*}\in\mathcal{H}}\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(h^{*})$
is known to the algorithm, this assumption can be easily removed and we defer
the discussion to the end. Our idea is to reduce the width using the algorithm
itself. Recall we have an algorithm of sample complexity
$\widetilde{O}((d+k)/\epsilon^{4})$ using MWU. Now at each round $t\in[T]$, we
first draw $\widetilde{O}(d/\epsilon^{2})$ samples from $\mathcal{D}^{(t)}$.
Instead of running ERM, we first obtain a subset of the hypothesis
$\mathcal{H}^{\prime}\subseteq\mathcal{H}$ by removing all hypothesis
$h\in\mathcal{H}$ that has error more than $\operatorname{OPT}+\epsilon$. We
then run the MWU algorithm with error parameter
$\epsilon^{\prime}=\epsilon^{1/2}$ over hypothesis class
$\mathcal{H}^{\prime}$ (so the additional samples it needs is still
$\widetilde{O}((d+k)/(\epsilon^{\prime})^{4})=\widetilde{O}((d+k)/\epsilon^{2})$),
and obtain a hypothesis $f_{t}$. The hypothesis $f_{t}$ has additional
guarantees on the maximum loss, i.e.,
$\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f_{t})\leq\operatorname{OPT}+\epsilon^{1/2}$.
This reduces the maximum loss from $1$ to $\operatorname{OPT}+\epsilon^{1/2}$.
However, we have no guarantee on the minimum loss, and the width could still
be as large as $\operatorname{OPT}+\epsilon^{1/2}\approx\Theta(1)$.

To get a lower bound on $\ell_{t}$, we can truncate small entries: If an entry
$\ell_{t}(i)=\ell_{\mathcal{D}_{i}}(f_{t})\leq\operatorname{OPT}-\epsilon^{1/2}$
is small, then we take it as $\ell_{t}(i)=\operatorname{OPT}-\epsilon^{1/2}$.
In this way, the width reduces to
$(\operatorname{OPT}+\epsilon^{1/2})-(\operatorname{OPT}-\epsilon^{1/2})=2\epsilon^{1/2}$.
However, there is a fatal issue here: There is no reason we can arbitrarily
truncate the loss. Recall we need the average loss
$\sum_{i\in[k]}p_{t}(i)\ell_{t}(i)$ to be close to
$\operatorname{OPT}+\epsilon$. If we truncate the small entries, then we
increase its value. As a concrete example, if $\operatorname{OPT}=1/2$, there
are $2\epsilon^{1/2}$-fraction of $(\ell_{\mathcal{D}_{i}}(f_{t}))_{i\in[k]}$
equal $0$, and the other $1-2\epsilon^{1/2}$ fraction equal
$\operatorname{OPT}+\epsilon^{1/2}$, then there is no way one can truncate the
loss.

The next idea is, instead of relying on uniform convergence and selecting the
hypothesis class $\mathcal{H}^{\prime}$ that are $\epsilon$-optimal on
$\mathcal{D}^{(t)}$, we need more refined properties of $\mathcal{H}^{\prime}$
that make the loss $(\ell_{\mathcal{D}_{i}}(f_{t}))_{i\in[k]}$ more balanced.
To this end, we want the hypothesis class $\mathcal{H}^{\prime}$ satisfies the
following two properties:

  * •

Soundness. The optimal classifier survives, i.e.,
$h^{*}\in\mathcal{H}^{\prime}$, where
$h^{*}=\operatorname*{arg\,min}_{h\in\mathcal{H}}\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(h)$.

  * •

Completeness. For any hypothesis $h\in\mathcal{H}^{\prime}$ that survives, it
satisfies the following guarantee. For any subset of distributions
$\mathcal{I}\subseteq[k]$, if their weights $\sum_{i\in[n]}p_{t}(i)\geq 1/2$,
then the loss of $h$ on the distribution
$\sum_{i\in\mathcal{I}}\frac{p_{t}(i)}{\sum_{i\in\mathcal{I}}p_{t}(i)}\mathcal{D}_{i}$
is at most $\operatorname{OPT}+O(\epsilon)$.

The first property states that the optimal classifier $h^{*}$ survives, this
ensures that it is safe to work with $\mathcal{H}^{\prime}$ instead of
$\mathcal{H}$. The second property is more complicated, but from a high level,
it says that any surviving hypothesis in $\mathcal{H}^{\prime}$ is robust –
not only their loss is small on the entire distribution
$\mathcal{D}^{(t)}=\sum_{i\in[k]}p_{t}(i)\mathcal{D}_{i}$, but also small on
any sub-populations $\\{\mathcal{D}_{i}\\}_{i\in\mathcal{I}}$ of mass at least
$1/2$. Suppose for now, we have achieved these two properties with
$\widetilde{O}((d+k)/\epsilon^{2})$ samples. Then we can safely truncate the
loss
$\ell_{t}(i)=\max\\{\ell_{\mathcal{D}_{i}}(f_{t}),\operatorname{OPT}-\epsilon^{1/2}\\}$
and reduce the width of
$\ell_{t}\in[\operatorname{OPT}-\epsilon^{1/2},\operatorname{OPT}+\epsilon^{1/2}]^{k}$
to $2\epsilon^{1/2}$. It remains to argue that the average loss satisfies
$\sum_{i\in[k]}p_{t}(i)\ell_{t}(i)\leq\operatorname{OPT}+O(\epsilon)$.111We
also need to ensure $\ell_{t}(i)$ is an overestimate of
$\ell_{\mathcal{D}_{i}}(f_{t})$, but this is trivial from the definition. To
this end, we sort the loss $\\{\ell_{\mathcal{D}_{i}}(f_{t})\\}_{i\in[k]}$ and
assume
$\ell_{\mathcal{D}_{1}}(f_{t})\geq\cdots\geq\ell_{\mathcal{D}_{k}}(f_{t})$
w.l.o.g. Suppose $k^{\prime}\in[k]$ is the smallest index such that
$\sum_{i\leq k^{\prime}}p_{t}(i)\geq 1/2$.

  * •

Case 1. If
$\ell_{\mathcal{D}_{k^{\prime}}}(f_{t})\geq\operatorname{OPT}-\epsilon^{1/2}$
(i.e., no truncation at the larger half), then by the completeness
property,222We actually need the hypothesis $f_{t}$ to be a weighted average
of hypothesis in $\mathcal{H}^{\prime}$ in order to inherit the completeness
property of $\mathcal{H}^{\prime}$, this is naturally satisfied by algorithms
in the MWU framework. the larger half has loss at most
$\operatorname{OPT}+O(\epsilon)$, since there is no truncation. Meanwhile, the
loss of the smaller half is no more than the larger half, so the average loss
is at most $\operatorname{OPT}+O(\epsilon)$.

  * •

Case 2. Otherwise, if
$\ell_{\mathcal{D}_{k^{\prime}}}(f_{t})<\operatorname{OPT}-\epsilon^{1/2}$,
then performing truncation is still fine, because more than $1/2$-fraction of
distributions have loss smaller than $\operatorname{OPT}-\epsilon^{1/2}$,
while the rest of them (at most $1/2$-fraction) have loss at most
$\operatorname{OPT}+\epsilon^{1/2}$.

Now we elaborate a bit on how we achieve both soundness and completeness. It
proceeds in two steps. First, we draw $\widetilde{O}(d/\epsilon)$ samples
$S^{(t)}_{1}$ from $\mathcal{D}^{(t)}$ and look at the projection of
$\mathcal{H}$ on $S^{(t)}_{1}$. We construct an $\epsilon$-cover
$\mathcal{C}_{\mathcal{H}}$ of $\mathcal{H}$ by including an arbitrary
hypothesis for each projection. This is a fairly standard trick (e.g. see
[ABM19]). Next, we draw another $\widetilde{O}((d+k)/\epsilon^{2})$ samples
$S^{(t)}_{2}$ from $\mathcal{D}^{(t)}$ and run the following test on
$S^{(t)}_{2}$. For each hypothesis $h\in\mathcal{C}_{\mathcal{H}}$ in the
$\epsilon$-cover, if there exists a subset $\mathcal{I}\subseteq[k]$ of
distributions such that (1) $\sum_{i\in\mathcal{I}}p_{t}(i)\geq 1/2$ and (2)
the empirical loss of $h$ on
$\sum_{i\in\mathcal{I}}\frac{p_{t}(i)}{\sum_{i\in\mathcal{I}}p_{t}(i)}\mathcal{D}_{i}$
is larger that $\operatorname{OPT}+O(\epsilon)$, then we remove $h$, as well
as all hypothesis that have the same projection as $h$ on $S_{1}^{(t)}$, from
$\mathcal{H}^{\prime}$. In the proof, we show that this test guarantees
soundness and completeness with high probability.

#### Recursive width reduction

The width reduction procedure described above reduces the width from $1$ to
$2\epsilon^{1/2}$. The regret now becomes
$\widetilde{O}(\epsilon^{1/2}/\sqrt{T})$, and it suffices to take
$T=\widetilde{O}(1/\epsilon)$. The sample complexity per round remains
$\widetilde{O}((d+k)/\epsilon^{2})$ and there are
$T=\widetilde{O}(1/\epsilon)$ rounds, so we improve the sample complexity from
$\widetilde{O}((d+k)/\epsilon^{4})$ to $\widetilde{O}((d+k)/\epsilon^{3})$. We
can continue this process, and use this new algorithm for width reduction. In
particular, at each round, we can take the error parameter
$\epsilon^{\prime}=\epsilon^{2/3}$ and use
$\widetilde{O}((d+k)/(\epsilon^{\prime})^{3})=\widetilde{O}((d+k)/(\epsilon)^{2})$
samples to reduce the maximum loss to
$\operatorname{OPT}+\epsilon^{\prime}=\operatorname{OPT}+\epsilon^{2/3}$
(instead of $\operatorname{OPT}+\epsilon^{1/2}$). The regret now becomes
$\widetilde{O}(\epsilon^{2/3}/\sqrt{T})$ and we can further reduce the number
of rounds to $T=\widetilde{O}(\epsilon^{-2/3})$ and the sample complexity to
$\widetilde{O}((d+k)/\epsilon^{8/3})$. We repeat the above process and obtain
an algorithm of sample complexity
$O((d+k)/\epsilon^{2})\cdot(k/\epsilon)^{o(1)}$.

#### Remove prior knowledge on $\operatorname{OPT}$

The above algorithm requires prior knowledge on the optimal value (for both
the testing step and the truncation step), we next remove this assumption. It
is not hard to see that the above algorithm succeeds with an
$\epsilon$-approximate
$\operatorname{OPT}^{\prime}\in[\operatorname{OPT}-\epsilon,\operatorname{OPT}+\epsilon]$
(i.e., no need for the exact value of $\operatorname{OPT}$). Hence, we can run
$1/\epsilon$ threads of the algorithm with
$\operatorname{OPT}^{\prime}=\epsilon,2\epsilon,\ldots,1$ and take the best
one. This has sample complexity
$(k+d)/\epsilon^{2}\cdot(1/\epsilon)=(k+d)/\epsilon^{3}$ (we omit the $o(1)$
term for simplicity) and does not require any knowledge of
$\operatorname{OPT}$. Next, we take $\epsilon^{\prime}=\epsilon^{2/3}$ and
runs the algorithm with $(k+d)/(\epsilon^{\prime})^{3}=(k+d)/\epsilon^{2}$
samples . The output hypothesis has error at most
$\operatorname{OPT}+O(\epsilon^{\prime})=\operatorname{OPT}+O(\epsilon^{2/3})$.
Now, we can reduce the size of the grid search and only search for
$\epsilon^{2/3}/\epsilon=\epsilon^{-1/3}$ possible value of
$\operatorname{OPT}^{\prime}$ (instead of $1/\epsilon$), this reduces the
sample complexity from $(k+d)/\epsilon^{3}$ to $(k+d)/\epsilon^{7/3}$. Again,
we repeat this process and get an algorithm of sample complexity
$O((d+k)/\epsilon^{2})\cdot(k/\epsilon)^{o(1)}$ without any knowledge of
$\operatorname{OPT}$.

###  1.2 Related work

The sample complexity of multi-distribution learning has been extensively
studied in the past decade [BHPQ17, NZ18, Qia18, CZZ18, TZZ19, BHPS21, HJZ22,
AHZ23]. The optimal sample complexity has been derived in the realizable
setting [BHPQ17, NZ18, CZZ18]. For the more general agnostic learning setting,
the optimal sample complexity has been obtained for finite hypothesis class
[HJZ22] but the question is widely open for VC classes, we refer interesting
readers for the open problem publication of [AHZ23] for an excellent coverage
on the literature.

The multi-distribution learning has applications to fairness [HJKRR18, MSS19,
SFGJ21, RY21, TH22] and group distributional robust optimization [BTEGN09,
RM19, SKHL19, SRKL20, DN21]. It is also closely related to multi-task learning
[Car97], distributed learning [BBFM12], federated learning [MMR+17], meta
learning [FAL17] and continual learning [CPP22].

Our approach can be seen as a boosting framework for (agnostic) multi-
distribution learning. It converts a weak multi-distribution learner into one
with better sample complexity guarantee. There is a vast literature on
boosting [Sch90, FS97, FSA99, BDLM01, MM02, KS03, KMV08, BBFM12, Sch13, BKL15,
BCHM20, AGHM21, BHM+21, BHM23], but to the best of our knowledge, it is the
first time that width reduction has been used – we hope it could find broad
applications for boosting. The idea of width reduction traces back to the
seminal work of positive LP solver [GK07] and approximate max flow [CKM+11],
which use separate subroutines for width reduction. The idea of recursive
width reduction (recursively applying the algorithm itself to reduce the
width) has been introduced recently by [PZ23] and it is crucial for the recent
development of low memory online learning algorithm [PZ23, PR23]. These
previous work are very inspiring, but our way of width reduction, which forms
the major challenging part of the proof, is unique and different.

##  2 Preliminary

Let $\mathcal{X}$ be the data universe and $\mathcal{Y}=\\{0,1\\}$ be binary
labels. Let $\mathcal{H}$ be a hypothesis class of VC dimension $d$, a
hypothesis $h\in\mathcal{H}$ maps the data universe $\mathcal{X}$ to the
binary label $\mathcal{Y}$. For any hypothesis
$f:\mathcal{X}\rightarrow\mathcal{Y}$ and any distribution $\mathcal{D}$ over
$\mathcal{X}\times\mathcal{Y}$, the population loss of $f$ over $\mathcal{D}$
equals $\ell_{\mathcal{D}}(f):=\Pr_{(x,y)\sim\mathcal{D}}[f(x)\neq y].$

######  Definition 2.1 (Multi-distribution learning).

Let $\epsilon>0$ be the error parameter. In the task of multi-distribution
learning, there are $k$ distributions $\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$
over $\mathcal{X}\times\mathcal{Y}$. The goal is to learn a hypothesis $f$
that minimizes the maximum loss, i.e.,

$\displaystyle\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f)\leq\min_{h^{*}\in\mathcal{H}}\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(h^{*})+\epsilon.$
(1)

We say an algorithm is an $(\epsilon,\delta)$-multi-distribution learner if
its output satisfies Eq. (1) with probability at least $1-\delta$. In the rest
of this paper, we write $h^{*}\in\mathcal{H}$ to be the hypothesis that
obtains the minimum loss and $\operatorname{OPT}$ be the minimum loss, i.e.,

$\displaystyle
h^{*}=\operatorname*{arg\,min}\limits_{h\in\mathcal{H}}\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(h)\quad\quad\text{and}\quad\quad\operatorname{OPT}=\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(h^{*}).$

For any set $S=\\{x_{1},\ldots,x_{n}\\}\in\mathcal{X}^{d}$, let
$\mathcal{H}(S):=\\{(h(x_{1}),\ldots,h(x_{n})):h\in\mathcal{H}\\}\subseteq\\{0,1\\}^{n}$
be the projection of $\mathcal{H}$ onto $S$. The Sauer–Shelah Lemma gives an
upper bound on the size $|\mathcal{H}(S)|$.

######  Lemma 2.2 (Sauer–Shelah Lemma [Sau72, She72]).

Let $\mathcal{H}$ be a hypothesis class with VC dimension $d$, then for any
$S\subseteq\mathcal{X}$ with $|S|=n$,
$|\mathcal{H}(S)|\leq\sum_{i=0}^{d}\binom{n}{i}$. In particular,
$|\mathcal{H}(S)|\leq(en/d)^{d}$ if $n\geq d$.

The multiplicative weight updating [LW94] is a classic algorithm for online
learning. An online learning task can be seen as a repeated game between an
algorithm and the nature for a sequence of $T$ rounds. Let
$[n]=\\{1,2,\ldots,n\\}$ and let $\Delta_{n}$ be all probability distributions
over $[n]$. The MWU algorithm commits a distribution $p_{t}\in\Delta_{n}$ over
a set of $n$ experts at each round $t\in[T]$, and then the nature reveals the
loss $\ell_{t}\in\mathbb{R}^{n}$ for experts $[n]$. The goal is to minimize
the regret $\sum_{t\in[T]}\langle
p_{t},\ell_{t}\rangle-\min_{i^{*}\in[n]}\sum_{t\in[T]}\ell_{t}(i^{*})$

Algorithm 1 Multiplicative weight update

1:for $t=1,2,\ldots,T$ do

2: Compute $p_{t}\in\Delta_{n}$ over experts such that
$p_{t}(i)\propto\exp(-\eta\sum_{\tau=1}^{t-1}\ell_{\tau}(i))$ for $i\in[n]$

3: Observe the loss vector $\ell_{t}$ and receives loss $\langle
p_{t},\ell_{t}\rangle$

4:end for

######  Lemma 2.3 (Regret guarantee of MWU [AHK12]).

Let $n$ be the number of experts, $T$ be the number of days, $B$ be the width
of the loss sequence, i.e., the loss vector
$\ell_{t}\in[\rho_{t},\rho_{t}+B]^{n}$ at each day $t\in[T]$. Let
$\eta=\sqrt{\log(n)/T}/B$ be the learning rate, then the MWU algorithm
guarantees

$\displaystyle\sum_{t\in[T]}\langle
p_{t},\ell_{t}\rangle-\min_{i^{*}\in[n]}\sum_{t\in[T]}\ell_{t}(i^{*})\leq\frac{\log
n}{\eta}+\eta TB^{2}=2\sqrt{\log(n)T}B.$

##  3 The boosting framework

We provide a general boosting framework that takes an arbitrary multi-
distribution learning algorithm, reduces its error while incurring a mild
overhead on the sample complexity. The boosting framework is formally
described in Algorithm 2. It contains several subroutines, whose pseudocodes
are presented in Algorithm 3-5. The input of BoostLearner (Algorithm 2)
consists of the hypothesis class $\mathcal{H}$, $k$ distributions
$\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$, a multi-distribution learning
algorithm MultiLearnerOracle, as well as an estimate
$\operatorname{OPT}^{\prime}$ on the optimal loss.

BoostLearner views $\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$ as $k$ experts,
and runs MWU over them for $T$ rounds. At each round $t\in[T]$, BoostLearner
maintains a strategy $p_{t}\in\Delta_{k}$ over $k$ data distributions, and let
$\mathcal{D}^{(t)}=\sum_{i\in[k]}p_{t}(i)\mathcal{D}_{i}$ be the mixed
distribution of $\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$. BoostLearner
proceeds in a few steps.

Construct $\epsilon$-cover of $\mathcal{H}$ The first step is to construct an
$\epsilon$-cover of the hypothesis $\mathcal{H}$ on the distribution
$\mathcal{D}^{(t)}$ (Line 3 of Algorithm 2). ConstructCover (Algorithm 3)
samples $m_{1}=\widetilde{O}(d/\epsilon)$ data points $S_{1}^{(t)}$ from
$\mathcal{D}^{(t)}$, the cover $\mathcal{C}_{\mathcal{H}}\subseteq\mathcal{H}$
is constructed by including an arbitrary hypothesis $h\in\mathcal{H}$ for each
projection of $\mathcal{H}(S_{1}^{(t)})$.

Filter $\mathcal{H}$ Given the $\epsilon$-cover $\mathcal{C}_{\mathcal{H}}$,
the next step is to filter $\mathcal{H}$ and only keep a subset of good
hypothesis $\mathcal{H}^{\prime}\subseteq\mathcal{H}$ (Line 4 of Algorithm 2).
The Filter procedure (Algorithm 4) draws
$m_{2}=\widetilde{O}(\frac{d+k}{\epsilon^{2}})$ samples $S^{(t)}_{2}$ from
$\mathcal{D}^{(t)}$ as a test set. For each hypothesis $h$ in the cover
$\mathcal{C}_{\mathcal{H}}$, it goes through all subsets $\mathcal{I}$ of
$[k]$ . If the probability mass $\sum_{i\in\mathcal{I}}p_{t}(i)$ is large
enough (i.e., greater than $1/2$) and the empirical loss of $h$ on the mixture
distribution
$\sum_{i\in\mathcal{I}}\tfrac{p_{t}(i)}{\sum_{i\in\mathcal{I}}p_{t}(i)}\mathcal{D}_{i}$
is large (i.e., great than $\operatorname{OPT}^{\prime}+8\epsilon$), then it
removes $h$, as well as any hypothesis $h^{\prime}\in\mathcal{H}$ that has the
same projection as $h$ on $S_{1}^{(t)}$, from $\mathcal{H}^{\prime}$.

Evoke the oracle  After obtaining the new hypothesis class
$\mathcal{H}^{\prime}\subseteq\mathcal{H}$, BoostLearner evokes the oracle
MultiLearnerOracle with hypothesis $\mathcal{H}^{\prime}$ and distributions
$\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$, and obtains a hypothesis $f_{t}$.

Construct the loss vector  Given the hypothesis $f_{t}$, BoostLearner
constructs the loss vector $\ell_{t}$ and feeds it to MWU (Line 6-7 of
Algorithm 2). Estimate (Algorithm 5) draws $\widetilde{O}(1/\epsilon^{2})$
samples from each distribution $\mathcal{D}_{i}$ and compute the empirical
loss $\hat{\ell}_{\mathcal{D}_{i}}(f_{t})$ of $f_{t}$ on $\mathcal{D}_{i}$.
Instead directly using this empirical loss, Estimate further truncates loss
entries that are below $\operatorname{OPT}^{\prime}-\alpha$ (Line 4 of
Algorithm 5), here $\alpha$ is the error of MultiLearnerOracle.

Final output  The final output is taken to be the average of
$\\{f_{t}\\}_{t\in[T]}$. In particular, the output
$f=\frac{1}{T}\sum_{t\in[T]}f_{t}$ is defined as

$\Pr[f(x)=1]=\frac{1}{T}\sum_{t\in[T]}\Pr[f_{t}(x)=1]\quad\quad\forall
x\in\mathcal{X}.$

Algorithm 2
$\textsc{BoostLearner}(\mathcal{H},\mathcal{D}_{1},\mathcal{D}_{2},\ldots,\mathcal{D}_{k},\textsc{MultiLearnerOracle},\operatorname{OPT}^{\prime})$

1:for $t=1,2,\ldots,T$ do

2: $\mathcal{D}^{(t)}\leftarrow\sum_{i\in[k]}p_{t}(i)\mathcal{D}_{i}$
$\triangleright$ $p_{t}\in\Delta_{k}$ is the strategy of MWU

3:
$\mathcal{C}_{\mathcal{H}}\leftarrow\textsc{ConstructCover}(\mathcal{H},\mathcal{D}^{(t)})$

4:
$\mathcal{H}^{\prime}\leftarrow\textsc{Filter}(\mathcal{H},\mathcal{D}^{(t)},\mathcal{C}_{\mathcal{H}},\operatorname{OPT}^{\prime})$

5:
$f_{t}\leftarrow\textsc{MultiLearnerOracle}(\mathcal{H}^{\prime},\mathcal{D}_{1},\ldots,\mathcal{D}_{k},\operatorname{OPT}^{\prime})$

6: $\ell_{t}\leftarrow\textsc{Estimate}(f_{t})$

7: Update the strategy of MWU with loss vector $-\ell_{t}$

8:end for

9:return $f=\frac{1}{T}\sum_{t\in[T]}f_{t}$

Algorithm 3 $\textsc{ConstructCover}(\mathcal{H},\mathcal{D}^{(t)})$

1:Sample $m_{1}=O(\frac{d\log(kd/\epsilon\delta)}{\epsilon})$ data points
$S_{1}^{(t)}=\\{(x_{j},y_{j})\\}_{j\in[m_{1}]}$ from $\mathcal{D}^{(t)}$

2:$\mathcal{C}_{\mathcal{H}}\leftarrow\emptyset$

3:for $(z_{1},\ldots,z_{m_{1}})\in\mathcal{H}(S^{(t)}_{1})$ do
$\triangleright$ $\mathcal{H}(S^{(t)}_{1})$ is the projection of $\mathcal{H}$
onto $S^{(t)}_{1}$

4: Let $h\in\mathcal{H}$ be an arbitrary hypothesis that satisfies
$h(x_{j})=z_{j}$ for all $j\in[m_{1}]$

5: $\mathcal{C}_{\mathcal{H}}\leftarrow\mathcal{C}_{\mathcal{H}}\cup\\{h\\}$

6:end for

7:return $\mathcal{C}_{\mathcal{H}}$

Algorithm 4
$\textsc{Filter}(\mathcal{H},\mathcal{D}^{(t)},\mathcal{C}_{\mathcal{H}},\operatorname{OPT}^{\prime})$

1:Sample $m_{2}=O(\frac{(k+d)\log(kd/\epsilon\delta)}{\epsilon^{2}})$ data
points $S^{(t)}_{2}=\\{(x_{j},y_{j})\\}_{j\in[m_{2}]}$ from
$\mathcal{D}^{(t)}$

2:$\mathcal{H}^{\prime}\leftarrow\mathcal{H}$

3:for $h\in\mathcal{C}_{\mathcal{H}}$ do

4: for $\mathcal{I}\subseteq[k]$ do

5: if $\sum_{i\in\mathcal{I}}p_{t}(i)\geq 1/2$ and
$\frac{\sum_{j\in[m_{2}]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\wedge
h(x_{j})\neq
y_{j}\\}}{\sum_{j\in[m_{2}]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\\}}\geq\operatorname{OPT}^{\prime}+8\epsilon$
then $\triangleright$
$\mathcal{D}_{\mathcal{I}}:=\cup_{i\in\mathcal{I}}\mathcal{D}_{i}$

6:
$\mathcal{H}^{\prime}\leftarrow\mathcal{H}^{\prime}\backslash\\{h^{\prime}\in\mathcal{H}:h(x)=h^{\prime}(x)\,\forall
x\in S_{1}^{(t)}\\}$

7: end if

8: end for

9:end for

10:return $\mathcal{H}^{\prime}$

Algorithm 5 $\textsc{Estimate}(f_{t})$

1:for $i=1,2,\ldots,k$ do

2: Sample $m_{3}=O(\log(kd/\epsilon\delta)/\epsilon^{2})$ data points
$S_{3,i}^{(t)}$ from $\mathcal{D}_{i}$

3: $\hat{\ell}_{\mathcal{D}_{i}}(f_{t})\leftarrow\Pr_{(x,y)\sim
S_{3,i}^{(t)}}[f_{t}(x)\neq y]$

4:
$\ell_{t}(i)\leftarrow\max\\{\hat{\ell}_{\mathcal{D}_{i}}(f_{t}),\operatorname{OPT}^{\prime}-\alpha\\}$
$\triangleright$ $\alpha$ is the error of MultiLearnerOracle

5:end for

6:return $\ell_{t}$

###  3.1 Analysis

Given an (infinite) hypothesis class $\mathcal{H}$, let $\Delta(\mathcal{H})$
be all distributions over $\mathcal{H}$ with finite support. Our goal is to
prove

######  Lemma 3.1 (Boosting framework).

Suppose
$\operatorname{OPT}^{\prime}\in[\operatorname{OPT}-\epsilon,\operatorname{OPT}+\epsilon]$
and MultiLearnerOracle is an $(\alpha,\delta/16T)$-multi-distribution learner
whose output $f_{t}\in\Delta(\mathcal{H})$. Let
$T=\log(k)(\alpha/\epsilon)^{2}$, then with probability at least $1-\delta$,
BoostLearner guarantees

$\displaystyle\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f)\leq\operatorname{OPT}+32\epsilon.$

We devote to prove Lemma 3.1 in the rest of this section, and we always make
the assumptions that
$\operatorname{OPT}^{\prime}\in[\operatorname{OPT}-\epsilon,\operatorname{OPT}+\epsilon]$
and MultiLearnerOracle is an $(\alpha,\delta/32T)$-multi-distribution learner
whose output $f_{t}\in\Delta(\mathcal{H})$. We further assume
$\epsilon\leq\alpha/32$, otherwise we do not need BoostLearner.

We first state the guarantee of ConstructCover.

######  Lemma 3.2 (Guarantee of ConstructCover, adapted from Lemma 3.3 of
[ABM19]).

For any $t\in[T]$, with probability at least $1-\delta/32T$,
$\mathcal{C}_{\mathcal{H}}$ is an $\epsilon$-cover of $\mathcal{H}$. Moreover,
for any hypothesis $h\in\mathcal{H}$, let
$h^{\prime}\in\mathcal{C}_{\mathcal{H}}$ be the hypothesis with the same
projection over $S_{1}^{(t)}$, we have

$\Pr_{x\sim\mathcal{D}^{(t)}}[h(x)\neq h^{\prime}(x)]\leq\epsilon.$

We next provide the guarantee of Filter.

######  Lemma 3.3 (Guarantee of Filter, Part 1).

For each $t\in[T]$, with probability at least $1-\delta/16T$, we have
$h^{*}\in\mathcal{H}^{\prime}$.

###### Proof.

For each $t\in[T]$, we condition on the high probability event of Lemma 3.2.
Suppose $h^{*}_{\mathcal{C}}\in\mathcal{C}_{\mathcal{H}}$ has the same
projection as $h^{*}$ on $S_{1}^{(t)}$, it suffices to prove
$h^{*}_{\mathcal{C}}\in\mathcal{H}^{\prime}$. By Lemma 3.2, we have

$\displaystyle\Pr_{x\sim\mathcal{D}^{(t)}}[h^{*}(x)\neq
h^{*}_{\mathcal{C}}(x)]\leq\epsilon.$ (2)

For any set $\mathcal{I}\subseteq[k]$ with $\sum_{i\in\mathcal{I}}p_{t}(i)\geq
1/2$, we have

$\displaystyle\frac{\sum_{i\in\mathcal{I}}p_{t}(i)\ell_{\mathcal{D}_{i}}(h^{*}_{\mathcal{C}})}{\sum_{i\in\mathcal{I}}p_{t}(i)}\leq\frac{\sum_{i\in\mathcal{I}}p_{t}(i)\ell_{\mathcal{D}_{i}}(h^{*})+\epsilon}{\sum_{i\in\mathcal{I}}p_{t}(i)}\leq\operatorname{OPT}+2\epsilon$
(3)

Here the first step follows from Eq. (2), the second step holds since
$\ell_{\mathcal{D}_{i}}(h^{*})\leq\operatorname{OPT}$ ($\forall i\in[k]$) and
$\sum_{i\in\mathcal{I}}p_{t}(i)\geq 1/2$.

Next, we have

$\displaystyle~{}\Pr\left[\frac{\sum_{j\in[m_{2}]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\wedge
h^{*}_{\mathcal{C}}(x_{j})\neq
y_{j}\\}}{\sum_{j\in[m_{2}]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\\}}\geq\operatorname{OPT}^{\prime}+8\epsilon\right]$
$\displaystyle\leq$
$\displaystyle~{}\Pr\left[\frac{\sum_{j\in[m_{2}]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\wedge
h^{*}_{\mathcal{C}}(x_{j})\neq
y_{j}\\}}{\sum_{j\in[m_{2}]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\\}}\geq\operatorname{OPT}+7\epsilon\right]$
$\displaystyle\leq$
$\displaystyle~{}\Pr\left[\sum_{j\in[m_{2}]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\\}\leq\frac{1}{4}m_{2}\right]$
$\displaystyle~{}+\Pr\left[\frac{\sum_{j\in[m_{2}]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\wedge
h^{*}_{\mathcal{C}}(x_{j})\neq
y_{j}\\}}{\sum_{j\in[m_{2}]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\\}}\geq\operatorname{OPT}+7\epsilon\mid\sum_{j\in[m_{2}]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\\}\geq\frac{1}{4}m_{2}\right]$
$\displaystyle\leq$
$\displaystyle~{}\exp(-m_{2}/8)+\exp(-2\cdot(m_{2}/4)\cdot(5\epsilon)^{2})$
$\displaystyle\leq$ $\displaystyle~{}2^{-k}\cdot\frac{\delta}{32T}.$

The first step follows from
$\operatorname{OPT}\leq\operatorname{OPT}^{\prime}+\epsilon$, the third step
follows from Chernoff bound, $\sum_{i\in\mathcal{I}}p_{t}(i)\geq 1/2$ and Eq.
(3). The last step follows from the choice of
$m_{2}\geq\Omega(k\log(kd/\epsilon\delta)/\epsilon^{2})$.

Taking a union bound over all subsets $\mathcal{I}\subseteq[k]$, we have

$\Pr[h^{*}\in\mathcal{H}^{\prime}]=\Pr[h^{*}_{\mathcal{C}}\in\mathcal{H}^{\prime}]\geq
1-2^{k}\cdot 2^{-k}\cdot\frac{\delta}{32T}\geq 1-\frac{\delta}{32T}.$

This finishes the proof. ∎

######  Lemma 3.4 (Guarantee of Filter, Part 2).

For each $t\in[T]$, with probability at least $1-\delta/16T$, it holds that
for every hypothesis $h\in\mathcal{H}^{\prime}$ and every set
$\mathcal{I}\subseteq[k]$, if $\sum_{i\in\mathcal{I}}p_{t}(i)\geq 1/2$, then

$\frac{\sum_{i\in\mathcal{I}}p_{t}(i)\ell_{\mathcal{D}_{i}}(h)}{\sum_{i\in\mathcal{I}}p_{t}(i)}\leq\operatorname{OPT}+16\epsilon.$

###### Proof.

For each $t\in[T]$, we condition on the high probability event of Lemma 3.2.
For each $h\in\mathcal{C}_{\mathcal{H}}$, if there exists
$h^{\prime}\in\mathcal{H}$ that has the same projection as $h$ on
$S_{1}^{(t)}$, and there exists a subset $\mathcal{I}\subseteq[k]$ with
$\sum_{i\in\mathcal{I}}p_{t}(i)\geq 1/2$, such that

$\displaystyle\frac{\sum_{i\in\mathcal{I}}p_{t}(i)\ell_{\mathcal{D}_{i}}(h^{\prime})}{\sum_{i\in\mathcal{I}}p_{t}(i)}\geq\operatorname{OPT}+16\epsilon$
(4)

then we prove $h$ would be removed from $\mathcal{H}^{\prime}$ with high
probability.

On the same subset $\mathcal{I}$, we have

$\displaystyle\frac{\sum_{i\in\mathcal{I}}p_{t}(i)\ell_{\mathcal{D}_{i}}(h)}{\sum_{i\in\mathcal{I}}p_{t}(i)}\geq\frac{\sum_{i\in\mathcal{I}}p_{t}(i)\ell_{\mathcal{D}_{i}}(h^{\prime})-\epsilon}{\sum_{i\in\mathcal{I}}p_{t}(i)}\geq\operatorname{OPT}+14\epsilon\geq\operatorname{OPT}^{\prime}+13\epsilon$
(5)

where the first step holds from Lemma 3.2, the second step holds since
$\sum_{i\in\mathcal{I}}p_{t}(i)\geq 1/2$, the third step follows from Eq. (4),
and the last step follows from
$\operatorname{OPT}^{\prime}\leq\operatorname{OPT}+\epsilon$.

Now, we have

$\displaystyle~{}\Pr\left[\frac{\sum_{j\in[m_{2}]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\wedge
h(x_{j})\neq
y_{j}\\}}{\sum_{j\in[m_{2}]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\\}}<\operatorname{OPT}^{\prime}+8\epsilon\right]$
$\displaystyle\leq$
$\displaystyle~{}\Pr\left[\sum_{j\in[m_{2}]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\\}<\frac{1}{4}m_{2}\right]$
$\displaystyle~{}+\Pr\left[\frac{\sum_{j\in[m_{2}]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\wedge
h(x_{j})\neq
y_{j}\\}}{\sum_{j\in[m_{2}]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\\}}<\operatorname{OPT}^{\prime}+8\epsilon\mid\sum_{j\in[n]}\mathsf{1}\\{x_{j}\in\mathcal{D}_{\mathcal{I}}\\}\geq\frac{1}{4}m_{2}\right]$
$\displaystyle\leq$
$\displaystyle~{}\exp(-m_{2}/8)+\exp(-2\cdot(m_{2}/4)\cdot(5\epsilon)^{2})$
$\displaystyle\leq$
$\displaystyle~{}(kd/\epsilon^{2}\delta)^{-d}\cdot\frac{\delta}{32T}.$

The second step follows from Chernoff bound,
$\sum_{i\in\mathcal{I}}p_{t}(i)\geq 1/2$ and Eq. (5). The third step holds
from the choice $m_{2}\geq\Omega(d\log(kd/\epsilon\delta)/\epsilon^{2})$.

Take a union bound over $\mathcal{C}_{\mathcal{H}}$ and note that
$|C_{\mathcal{H}}|\leq(kd/\epsilon^{2}\delta)^{d}$ by Sauer–Shelah Lemma (see
Lemma 2.2), we complete the proof. ∎

Next we make some observations on the output $f_{t}$ of MultiLearnerOracle.

######  Lemma 3.5.

For each $t\in[T]$, with probability at least $1-\delta/4T$, we have

  * •

$\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f_{t})\leq\operatorname{OPT}+\alpha$

  * •

For any set $\mathcal{I}\subseteq[k]$ with $\sum_{i\in\mathcal{I}}p_{t}(i)\geq
1/2$,
$\frac{\sum_{i\in\mathcal{I}}p_{t}(i)\ell_{\mathcal{D}_{i}}(f_{t})}{\sum_{i\in\mathcal{I}}p_{t}(i)}\leq\operatorname{OPT}+16\epsilon$.

###### Proof.

We condition on the high probability event of Lemma 3.3 and Lemma 3.4. The
first claim follows from

$\displaystyle\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f_{t})\leq\operatorname*{arg\,min}_{h\in\mathcal{H}^{\prime}}\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(h)+\alpha=\operatorname{OPT}+\alpha$

The first step follows from the guarantee of MultiLearnerOracle, the second
step holds since $h^{*}\in\mathcal{H}^{\prime}$.

For the second claim, since $f_{t}\in\Delta(\mathcal{H}^{\prime})$, we can
write $f_{t}=\sum_{j}q_{j}h_{j}$ for some $h_{j}\in\mathcal{H}^{\prime}$ and
$\sum_{j}q_{j}=1$. Then for any set $\mathcal{I}\subseteq[k]$ with
$\sum_{i\in\mathcal{I}}p_{t}(i)\geq 1/2$, we have

$\displaystyle\frac{\sum_{i\in\mathcal{I}}p_{t}(i)\ell_{\mathcal{D}_{i}}(f_{t})}{\sum_{i\in\mathcal{I}}p_{t}(i)}=\frac{\sum_{j}q_{j}\sum_{i\in\mathcal{I}}p_{t}(i)\ell_{\mathcal{D}_{i}}(h_{j})}{\sum_{i\in\mathcal{I}}p_{t}(i)}\leq\sum_{j}q_{j}(\operatorname{OPT}+16\epsilon)=\operatorname{OPT}+16\epsilon.$

Here the first step holds since

$\ell_{\mathcal{D}_{i}}(f_{t})=\Pr_{(x,y)\sim\mathcal{D}_{i}}[f_{t}(x)\neq
y]=\sum_{j}q_{j}\Pr_{(x,y)\sim\mathcal{D}_{i}}[h_{j}(x)\neq
y]=\sum_{j}q_{j}\ell_{\mathcal{D}_{i}}(h_{j}).$

and the second step holds due to Lemma 3.4. ∎

Finally, we make some observations on the loss vector $\ell_{t}$ constructed
by Estimate.

######  Lemma 3.6 (Guarantee of Estimate).

For any $t\in[T]$, with probability at least $1-\frac{\delta}{2T}$, we have

  * •

$\ell_{t}(i)\geq\ell_{\mathcal{D}_{i}}(f_{t})-\epsilon$

  * •

$\ell_{t}(i)\in[\operatorname{OPT}-2\alpha,\operatorname{OPT}+2\alpha]$

  * •

$\sum_{i\in[k]}p_{t}(i)\ell_{t}(i)\leq\operatorname{OPT}+20\epsilon$

###### Proof.

For each $t\in[T]$, we condition on the high probability event of Lemma 3.5.
For each $i\in[k]$, since
$m_{3}\geq\Omega(\log(kd/\epsilon\delta)/\epsilon^{2})$, by Chernoff bound,
with probability at least $1-\frac{\delta}{32kT}$, the empirical loss
$\hat{\ell}_{\mathcal{D}_{i}}(f_{t})$ is $\epsilon$-close to the population
loss $\ell_{\mathcal{D}_{i}}(f_{t})$. Taking a union bound, we have

$\displaystyle\hat{\ell}_{\mathcal{D}_{i}}(f_{t})\in[\ell_{\mathcal{D}_{i}}(f_{t})-\epsilon,\ell_{\mathcal{D}_{i}}(f_{t})+\epsilon]\quad\forall
i\in[k]$ (6)

holds with probability at least $1-\frac{\delta}{32T}$.

For the first claim, we have

$\displaystyle\ell_{t}(i)=\max\\{\hat{\ell}_{\mathcal{D}_{i}}(f_{t}),\operatorname{OPT}^{\prime}-\alpha\\}\geq\hat{\ell}_{\mathcal{D}_{i}}(f)\geq\ell_{\mathcal{D}_{i}}(f_{t})-\epsilon.$

For the second claim, we have

$\ell_{t}(i)=\max\\{\hat{\ell}_{\mathcal{D}_{i}}(f_{t}),\operatorname{OPT}^{\prime}-\alpha\\}\geq\operatorname{OPT}^{\prime}-\alpha\geq\operatorname{OPT}-2\alpha$

and

$\ell_{t}(i)=\max\\{\hat{\ell}_{\mathcal{D}_{i}}(f_{t}),\operatorname{OPT}^{\prime}-\alpha\\}\leq\max\\{\ell_{\mathcal{D}_{i}}(f_{t}),\operatorname{OPT}-\alpha\\}+\epsilon\leq\operatorname{OPT}+2\alpha,$

where the second step follows from Eq. (6) and
$\operatorname{OPT}^{\prime}\leq\operatorname{OPT}+\epsilon$, the third step
holds since $\ell_{\mathcal{D}_{i}}(f_{t})\leq\operatorname{OPT}+\alpha$
(Lemma 3.5).

For the last claim, w.l.o.g., we can assume
$\ell_{\mathcal{D}_{1}}(f_{t})\geq\cdots\geq\ell_{\mathcal{D}_{k}}(f_{t})$.
Let $k^{\prime}\in[k]$ be the smallest index such that $\sum_{i\leq
k^{\prime}}p_{t}(i)\geq 1/2$. We divide into two cases based on the value of
$\ell_{D_{k^{\prime}}}(f_{t})$.

If $\ell_{D_{k^{\prime}}}(f_{t})\geq\operatorname{OPT}-\alpha$, then we have

$\displaystyle\sum_{i\in[k]}p_{t}(i)\ell_{t}(i)=$ $\displaystyle~{}\sum_{i\leq
k^{\prime}}p_{t}(i)\ell_{t}(i)+\sum_{i\geq k^{\prime}+1}p_{t}(i)\ell_{t}(i)$
$\displaystyle=$ $\displaystyle~{}\sum_{i\leq
k^{\prime}}p_{t}(i)\cdot\max\\{\hat{\ell}_{\mathcal{D}_{i}}(f_{t}),\operatorname{OPT}^{\prime}-\alpha\\}+\sum_{i\geq
k^{\prime}+1}p_{t}(i)\cdot\max\\{\hat{\ell}_{\mathcal{D}_{i}}(f_{t}),\operatorname{OPT}^{\prime}-\alpha\\}$
(7)

For the first term, we have

$\displaystyle\sum_{i\leq
k^{\prime}}p_{t}(i)\cdot\max\\{\hat{\ell}_{\mathcal{D}_{i}}(f_{t}),\operatorname{OPT}^{\prime}-\alpha\\}\leq$
$\displaystyle~{}\sum_{i\leq
k^{\prime}}p_{t}(i)\cdot(\max\\{\ell_{\mathcal{D}_{i}}(f_{t}),\operatorname{OPT}-\alpha\\}+\epsilon)$
$\displaystyle=$ $\displaystyle~{}\sum_{i\leq
k^{\prime}}p_{t}(i)\cdot(\ell_{\mathcal{D}_{i}}(f_{t})+\epsilon)$
$\displaystyle\leq$ $\displaystyle~{}\sum_{i\leq
k^{\prime}}p_{t}(i)\cdot(\operatorname{OPT}+17\epsilon).$ (8)

The first step follows from
$\operatorname{OPT}^{\prime}\leq\operatorname{OPT}+\epsilon$ and Eq. (6), the
second step follows from the assumption that
$\ell_{D_{k^{\prime}}}(f_{t})\geq\operatorname{OPT}-\alpha$, the third step
holds due to Lemma 3.5.

For the second term, we have

$\displaystyle\sum_{i\geq
k^{\prime}+1}p_{t}(i)\cdot\max\\{\hat{\ell}_{\mathcal{D}_{i}}(f_{t}),\operatorname{OPT}^{\prime}-\alpha\\}\leq$
$\displaystyle~{}\sum_{i\geq
k^{\prime}+1}p_{t}(i)(\max\\{\ell_{\mathcal{D}_{i}}(f_{t}),\operatorname{OPT}-\alpha\\}+\epsilon)$
$\displaystyle\leq$ $\displaystyle~{}\sum_{i\geq
k^{\prime}+1}p_{t}(i)(\max\\{\ell_{\mathcal{D}_{k^{\prime}}}(f_{t}),\operatorname{OPT}-\alpha\\}+\epsilon)$
$\displaystyle=$ $\displaystyle~{}\sum_{i\geq
k^{\prime}+1}p_{t}(i)(\ell_{\mathcal{D}_{k^{\prime}}}(f_{t})+\epsilon)$
$\displaystyle\leq$ $\displaystyle~{}\sum_{i\geq
k^{\prime}+1}p_{t}(i)(\operatorname{OPT}+17\epsilon)$ (9)

The first step follows from
$\operatorname{OPT}^{\prime}\leq\operatorname{OPT}+\epsilon$ and Eq. (6), the
third step follows from the assumption that
$\ell_{D_{k^{\prime}}}(f_{t})\geq\operatorname{OPT}-\alpha$, the last step
follows from
$\ell_{\mathcal{D}_{k^{\prime}}}(f_{t})\leq\ell_{\mathcal{D}_{i}}(f_{t})$
($i\leq k^{\prime}$) and Lemma 3.5.

Combining Eq. (7)(8)(9), we have proved
$\sum_{i\in[k]}p_{t}(i)\ell_{t}(i)\leq\operatorname{OPT}+17\epsilon.$

If $\ell_{D_{k^{\prime}}}(f_{t})<\operatorname{OPT}-\alpha$, then we have

$\displaystyle\sum_{i\in[k]}p_{t}(i)\ell_{t}(i)=$ $\displaystyle~{}\sum_{i\leq
k^{\prime}-1}p_{t}(i)\ell_{t}(i)+\sum_{i\geq k^{\prime}}p_{t}(i)\ell_{t}(i)$
$\displaystyle=$ $\displaystyle~{}\sum_{i\leq
k^{\prime}-1}p_{t}(i)\cdot\max\\{\hat{\ell}_{\mathcal{D}_{i}}(f_{t}),\operatorname{OPT}^{\prime}-\alpha\\}+\sum_{i\geq
k^{\prime}}p_{t}(i)\cdot\max\\{\hat{\ell}_{\mathcal{D}_{i}}(f_{t}),\operatorname{OPT}^{\prime}-\alpha\\}$
$\displaystyle\leq$ $\displaystyle~{}\sum_{i\leq
k^{\prime}-1}p_{t}(i)\cdot(\operatorname{OPT}+\alpha+\epsilon)+\sum_{i\geq
k^{\prime}}p_{t}(i)\cdot(\operatorname{OPT}-\alpha+\epsilon)$
$\displaystyle\leq$ $\displaystyle~{}\operatorname{OPT}+\epsilon.$

Here the third step holds since (1)
$\hat{\ell}_{\mathcal{D}_{i}}(f_{t})\leq\ell_{\mathcal{D}_{i}}(f_{t})+\epsilon\leq\operatorname{OPT}+\alpha+\epsilon$
for any $i\in[k^{\prime}-1]$ (Lemma 3.5), and (2)
$\hat{\ell}_{\mathcal{D}_{i}}(f_{t})\leq\ell_{\mathcal{D}_{i}}(f_{t})+\epsilon\leq\ell_{D_{k^{\prime}}}(f_{t})+\epsilon\leq\operatorname{OPT}-\alpha+\epsilon$
for any $i\geq k^{\prime}$ due to the assumption
$\ell_{D_{k^{\prime}}}(f_{t})<\operatorname{OPT}-\alpha$. The last step holds
since $\sum_{i\leq k^{\prime}-1}p_{t}(i)<1/2$. This completes the proof for
all three claims. ∎

Finally, we can prove our main Lemma 3.1.

###### Proof of Lemma 3.1.

We condition on the high probability events of Lemma 3.2 – 3.6. For any
$i\in[k]$, due to the regret guarantee of MWU, we have

$\displaystyle(\operatorname{OPT}+20\epsilon)T\geq$
$\displaystyle~{}\sum_{t\in[T]}\langle
p_{t},\ell_{t}\rangle\geq\sum_{t\in[T]}\ell_{t}(i)-2\sqrt{\log(k)T}\cdot
4\alpha$ $\displaystyle\geq$
$\displaystyle~{}\sum_{t\in[T]}\ell_{\mathcal{D}_{i}}(f_{t})-\epsilon
T-8\sqrt{\log(k)T}\alpha.$

The first step follows from the third claim of Lemma 3.6, the second step
follows from the regret guarantee of MWU (Lemma 2.3) and the width is at most
$4\alpha$ (the second claim of Lemma 3.6). The third step follows from the
first claim of Lemma 3.6.

Hence, we have

$\displaystyle\ell_{\mathcal{D}_{i}}(f)=\frac{1}{T}\sum_{t\in[T]}\ell_{\mathcal{D}_{i}}(f_{t})\leq\operatorname{OPT}+21\epsilon+8\sqrt{\log(k)/T}\alpha\leq\operatorname{OPT}+32\epsilon.$

Here the first step holds since

$\ell_{\mathcal{D}_{i}}(f)=\Pr_{(x,y)\sim\mathcal{D}_{i}}[f(x)\neq
y]=\frac{1}{T}\sum_{t\in[T]}\Pr_{(x,y)\sim\mathcal{D}_{i}}[f_{t}(x)\neq
y]=\frac{1}{T}\sum_{t\in[T]}\ell_{\mathcal{D}_{i}}(f_{t}).$

and the last step holds due to the choice of $T=\log(k)(\alpha/\epsilon)^{2}$.
We complete the proof here. ∎

##  4 Final algorithm

BoostLearner gives a way of converting a weak multi-distribution learner into
a strong one. Recursively evoking itself, we have

######  Lemma 4.1 (Recursive application of BoostLearner).

Let $\mathcal{H}$ be a hypothesis class of VC dimension at most $d$ and
$\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$ be $k$ distributions. Given
$\operatorname{OPT}^{\prime}\in[\operatorname{OPT}-\epsilon,\operatorname{OPT}+\epsilon]$,
for any integer $r\geq 1$, there is an algorithm with sample complexity

$O\left(\frac{(k+d)(\log(k))^{2r}\log(kd/\epsilon\delta)}{\epsilon^{2(1+1/r)}}\right)$

and with probability at least $1-\delta$, returns a hypothesis
$f\in\Delta(\mathcal{H})$ such that

$\displaystyle\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f)\leq\operatorname{OPT}+32\epsilon.$

###### Proof.

We prove by induction. For $r=1$, we run BoostLearner with MultiLearnerOracle
selecting an arbitrary hypothesis in $\mathcal{H}^{\prime}$. In this way,
MultiLearnerOracle takes $0$ additional samples and $\alpha=1$. By Lemma 3.1,
the output $f\in\Delta(\mathcal{H})$ satisfies

$\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f)\leq\operatorname{OPT}+32\epsilon.$

The total number of sample it takes equals

$T\cdot(m_{1}+m_{2}+km_{3})=O(\log(k)\epsilon^{-2}\cdot(k+d)\epsilon^{-2}\log(kd/\epsilon\delta))=O((k+d)\epsilon^{-4}\log(k)\log(kd/\epsilon\delta)).$

Suppose the claim continues to hold up to $r$, then for $r+1$, we run
BoostLearner and set MultiLearnerOracle to be the level $r$ algorithm, with
error parameter $\epsilon^{\prime}=\epsilon^{\frac{r}{r+1}}$ and confidence
parameter $\delta^{\prime}=\delta/16T$. At each round $t\in[T]$, the VC
dimension of $\mathcal{H}^{\prime}$ is at most $d$, and with high probability,
$h^{*}\in\mathcal{H}^{\prime}$ (Lemma 3.3). Therefore, MultiLearnerOracle
draws

$m=O\left(\frac{(k+d)(\log(k))^{2r}\log(kd/\epsilon^{\prime}\delta^{\prime})}{(\epsilon^{\prime})^{2(1+1/r)}}\right)=O\left(\frac{(k+d)(\log(k))^{2r}\log(kd/\epsilon\delta)}{\epsilon^{2}}\right)$

samples, and with probability at least $1-\delta/16T$, the hypothesis
$f_{t}\in\Delta(\mathcal{H})$ it returns has error at most

$\alpha=32\epsilon^{\prime}=32\epsilon^{\frac{r}{r+1}}.$

Therefore, by Lemma 3.1, we obtain an $(32\epsilon,\delta)$-multi-distribution
learner and its sample complexity equals

$\displaystyle T(m_{1}+m_{2}+km_{3}+m)=$
$\displaystyle~{}O\left(\log(k)\alpha^{2}\epsilon^{-2}\cdot\frac{(k+d)(\log(k))^{2r}\log(kd/\epsilon\delta)}{\epsilon^{2}}\right)$
$\displaystyle=$
$\displaystyle~{}O\left(\frac{(k+d)(\log(k))^{2r+2}\log(kd/\epsilon\delta)}{\epsilon^{2(1+\frac{1}{r+1})}}\right).$

This completes the proof. ∎

The algorithm described in lemma 4.1 still requires the prior knowledge of
$\operatorname{OPT}$. Next, we give a way of removing this prior knowledge.

######  Lemma 4.2 (Remove prior knowledge of $\operatorname{OPT}$).

For any $\kappa\geq 2$, suppose there exists an algorithm that receives
$\operatorname{OPT}^{\prime}\in[\operatorname{OPT}-\epsilon,\operatorname{OPT}+\epsilon]$,
returns a hypothesis of error at most $32\epsilon$ and has sample complexity
$g(k,d,\delta)\epsilon^{-\kappa}$. Then there is an algorithm of sample
complexity
$g(k,d,\epsilon^{2}\delta/80)\cdot\epsilon^{-\kappa}\log(1/\epsilon)$ and
returns a hypothesis of error at most $33\epsilon$. Here $g(k,d,\delta)$ is a
function of $k,d,\delta$.

###### Proof.

We prove the following claim by induction: For any $r\geq 1$, let
$\delta_{r}=\epsilon\delta/2^{r}80$, there is an algorithm that draws
$O\left(g(k,d,\delta_{r})\cdot
40r\cdot\epsilon^{-\kappa-\frac{1}{\kappa^{r-1}}}\right)$ samples and obtains
a hypothesis $f$ such that
$\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f)\leq\operatorname{OPT}+33\epsilon$,
without knowing $\operatorname{OPT}$.

Let $\operatorname{ALG}$ be the input algorithm that requires prior knowledge
of $\operatorname{OPT}$. For the base case $r=1$, we instantiate
$B=1/\epsilon$ threads of $\operatorname{ALG}$, with
$\operatorname{OPT}^{\prime}=b\cdot\epsilon$ ($b\in[B]$), and obtain
$\\{f_{b}\\}_{b\in[B]}$. We select the best hypothesis among
$\\{f_{b}\\}_{b\in[B]}$, by drawing $O(\log(k/\epsilon\delta)/\epsilon^{2})$
samples from each distribution and estimating the empirical loss of
$\\{f_{b}\\}_{b\in[B]}$. The output hypothesis $f$ satisfies

$\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f)\leq\min_{b\in[B]}\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f_{b})+\epsilon\leq\operatorname{OPT}+33\epsilon.$

since one of the guess $\operatorname{OPT}^{\prime}$ has error at most
$\epsilon$. The sample complexity equals
$g(k,d,\epsilon\delta/2)\epsilon^{-\kappa-1}+O(k\log(k/\epsilon\delta)/\epsilon^{2})\leq
g(k,d,\delta_{1})\epsilon^{-\kappa-1}$.

Suppose the claim continues to hold for $r$, then for $r+1$, the algorithm
first runs the level $r$ algorithm with error parameter
$\epsilon^{\prime}=\epsilon^{(\kappa+\frac{1}{\kappa^{r}})/(\kappa+\frac{1}{\kappa^{r-1}})}$.
In particular, it draws

$n_{1}=g(k,d,\delta_{r}/2)\cdot
40r\cdot(\epsilon^{\prime})^{-\kappa-\frac{1}{\kappa^{r-1}}}=g(k,d,\delta_{r+1})\cdot
40r\cdot\epsilon^{-\kappa-\frac{1}{\kappa^{r}}}$

samples and obtains a hypothesis $f^{\prime}$ of error at most
$33\epsilon^{\prime}$. It then draws
$n_{2}=O(\log(k/\epsilon\delta)/\epsilon^{2})$ samples from each distribution
and estimates the empirical loss $\hat{\ell}_{\mathcal{D}_{i}}(f^{\prime})$ of
$f^{\prime}$ on each distribution $\mathcal{D}_{i}$ ($i\in[n]$). Next, it
instantiates $B=33\epsilon^{\prime}/\epsilon$ threads of $\operatorname{ALG}$,
with
$\operatorname{OPT}^{\prime}=\max_{i\in[k]}\hat{\ell}_{\mathcal{D}_{i}}(f^{\prime})-b\epsilon$
($b\in[B]$), and obtains $\\{f_{b}\\}_{b\in[B]}$. The number of samples taken
in this step equals

$\displaystyle n_{3}=$ $\displaystyle~{}33(\epsilon^{\prime}/\epsilon)\cdot
g(k,d,\epsilon\delta/80)\cdot\epsilon^{-\kappa}=33g(k,d,\delta_{1})\cdot\epsilon^{-\kappa-1+(\kappa+\frac{1}{\kappa^{r}})/(\kappa+\frac{1}{\kappa^{r-1}})}$
$\displaystyle\leq$
$\displaystyle~{}33g(k,d,\delta_{r+1})\cdot\epsilon^{-\kappa-\frac{1}{\kappa^{r}}}.$

The final output $f$ is the best hypothesis among $f^{\prime}$ and
$\\{f_{b}\\}_{b\in[B]}$, measured with their empirical loss. The sample
complexity of the algorithm equals

$\displaystyle n_{1}+kn_{2}+n_{3}\leq g(k,d,\delta_{r+1})\cdot
40(r+1)\cdot\epsilon^{-\kappa-\frac{1}{\kappa^{r}}}.$ (10)

For the output hypothesis $f$, if
$\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f^{\prime})\leq\operatorname{OPT}+30\epsilon$,
then we have

$\displaystyle\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f)\leq\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f^{\prime})+\epsilon\leq\operatorname{OPT}+31\epsilon.$
(11)

Otherwise, if
$\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f^{\prime})\geq\operatorname{OPT}+30\epsilon$,
the one of the guess
$\\{\max_{i\in[k]}\hat{\ell}_{\mathcal{D}_{i}}(f^{\prime})-b\epsilon\\}_{b\in[B]}$
of $\operatorname{OPT}^{\prime}$ is $\epsilon$-close to $\operatorname{OPT}$,
and therefore, we have

$\displaystyle\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f)\leq\min_{b\in[B]}\max_{i\in[k]}\ell_{\mathcal{D}_{i}}(f_{b})+\epsilon\leq\operatorname{OPT}+33\epsilon$
(12)

where the last step follows from the guarantee of $\operatorname{ALG}$.
Combining Eq. (10)(11)(12), we complete the induction. Taking
$r=\log(1/\epsilon)$, we finish the proof. ∎

Combining Lemma 4.2 and Lemma 4.1 (taking $r=\omega(1)$) we complete the proof
of Theorem 1.1.

## References

  * [AACSZ23] Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy.  Optimal pac bounds without uniform convergence.  In 2023 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 2023.
  * [ABM19] Noga Alon, Raef Bassily, and Shay Moran.  Limits of private learning with access to public data.  Advances in neural information processing systems, 32, 2019.
  * [AGHM21] Noga Alon, Alon Gonen, Elad Hazan, and Shay Moran.  Boosting simple learners.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 481–489, 2021.
  * [AHK12] Sanjeev Arora, Elad Hazan, and Satyen Kale.  The multiplicative weights update method: a meta-algorithm and applications.  Theory of Computing, 8(1):121–164, 2012.
  * [AHZ23] Pranjal Awasthi, Nika Haghtalab, and Eric Zhao.  Open problem: The sample complexity of multi-distribution learning for vc classes.  In The Thirty Sixth Annual Conference on Learning Theory, pages 5943–5949. PMLR, 2023.
  * [AO04] Peter Auer and Ronald Ortner.  A new pac bound for intersection-closed concept classes.  In International Conference on Computational Learning Theory, pages 408–414. Springer, 2004.
  * [BBFM12] Maria Florina Balcan, Avrim Blum, Shai Fine, and Yishay Mansour.  Distributed learning, communication complexity and privacy.  In Conference on Learning Theory, pages 26–1. JMLR Workshop and Conference Proceedings, 2012.
  * [BCHM20] Nataly Brukhim, Xinyi Chen, Elad Hazan, and Shay Moran.  Online agnostic boosting via regret minimization.  Advances in Neural Information Processing Systems, 33:644–654, 2020\.
  * [BDLM01] Shai Ben-David, Philip M Long, and Yishay Mansour.  Agnostic boosting.  In Computational Learning Theory: 14th Annual Conference on Computational Learning Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001 Amsterdam, The Netherlands, July 16–19, 2001 Proceedings 14, pages 507–516. Springer, 2001.
  * [BEHW89] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth.  Learnability and the vapnik-chervonenkis dimension.  Journal of the ACM (JACM), 36(4):929–965, 1989.
  * [BHM+21] Nataly Brukhim, Elad Hazan, Shay Moran, Indraneel Mukherjee, and Robert E Schapire.  Multiclass boosting and the cost of weak learning.  Advances in Neural Information Processing Systems, 34:3057–3067, 2021.
  * [BHM23] Nataly Brukhim, Steve Hanneke, and Shay Moran.  Improper multiclass boosting.  In The Thirty Sixth Annual Conference on Learning Theory, pages 5433–5452. PMLR, 2023.
  * [BHPQ17] Avrim Blum, Nika Haghtalab, Ariel D Procaccia, and Mingda Qiao.  Collaborative pac learning.  Advances in Neural Information Processing Systems, 30, 2017.
  * [BHPS21] Avrim Blum, Nika Haghtalab, Richard Lanas Phillips, and Han Shao.  One for one, or all for all: Equilibria and optimality of collaboration in federated learning.  In International Conference on Machine Learning, pages 1005–1014. PMLR, 2021.
  * [BKL15] Alina Beygelzimer, Satyen Kale, and Haipeng Luo.  Optimal and adaptive algorithms for online boosting.  In International Conference on Machine Learning, pages 2323–2331. PMLR, 2015.
  * [BTEGN09] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski.  Robust optimization, volume 28.  Princeton university press, 2009.
  * [Car97] Rich Caruana.  Multitask learning.  Machine learning, 28:41–75, 1997.
  * [CKM+11] Paul Christiano, Jonathan A Kelner, Aleksander Madry, Daniel A Spielman, and Shang-Hua Teng.  Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs.  In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 273–282, 2011.
  * [CPP22] Xi Chen, Christos Papadimitriou, and Binghui Peng.  Memory bounds for continual learning.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 519–530. IEEE, 2022.
  * [CZZ18] Jiecao Chen, Qin Zhang, and Yuan Zhou.  Tight bounds for collaborative pac learning via multiplicative weights.  Advances in neural information processing systems, 31, 2018.
  * [DGK+21] Emily Diana, Wesley Gill, Michael Kearns, Krishnaram Kenthapadi, and Aaron Roth.  Minimax group fairness: Algorithms and experiments.  In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 66–76, 2021.
  * [DN21] John C Duchi and Hongseok Namkoong.  Learning models with uniform performance via distributionally robust optimization.  The Annals of Statistics, 49(3):1378–1406, 2021.
  * [FAL17] Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  In International conference on machine learning, pages 1126–1135. PMLR, 2017.
  * [FS97] Yoav Freund and Robert E Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  Journal of computer and system sciences, 55(1):119–139, 1997.
  * [FSA99] Yoav Freund, Robert Schapire, and Naoki Abe.  A short introduction to boosting.  Journal-Japanese Society For Artificial Intelligence, 14(771-780):1612, 1999.
  * [GK07] Naveen Garg and Jochen Könemann.  Faster and simpler algorithms for multicommodity flow and other fractional packing problems.  SIAM Journal on Computing, 37(2):630–652, 2007.
  * [Han16] Steve Hanneke.  The optimal sample complexity of pac learning.  The Journal of Machine Learning Research, 17(1):1319–1333, 2016\.
  * [HJKRR18] Ursula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum.  Multicalibration: Calibration for the (computationally-identifiable) masses.  In International Conference on Machine Learning, pages 1939–1948. PMLR, 2018.
  * [HJZ22] Nika Haghtalab, Michael Jordan, and Eric Zhao.  On-demand sampling: Learning optimally from multiple distributions.  Advances in Neural Information Processing Systems, 35:406–419, 2022\.
  * [KMV08] Adam Tauman Kalai, Yishay Mansour, and Elad Verbin.  On agnostic boosting and parity learning.  In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 629–638, 2008.
  * [KS03] Adam Kalai and Rocco A Servedio.  Boosting in the presence of noise.  In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 195–205, 2003.
  * [Lar23] Kasper Green Larsen.  Bagging is an optimal pac learner.  In The Thirty Sixth Annual Conference on Learning Theory, pages 450–468. PMLR, 2023.
  * [LW94] Nick Littlestone and Manfred K Warmuth.  The weighted majority algorithm.  Information and computation, 108(2):212–261, 1994.
  * [MM02] Yishay Mansour and David McAllester.  Boosting using branching programs.  Journal of Computer and System Sciences, 64(1):103–112, 2002.
  * [MMR+17] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In Artificial intelligence and statistics, pages 1273–1282. PMLR, 2017.
  * [MSS19] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh.  Agnostic federated learning.  In International Conference on Machine Learning, pages 4615–4625. PMLR, 2019.
  * [NZ18] Huy Nguyen and Lydia Zakynthinou.  Improved algorithms for collaborative pac learning.  Advances in Neural Information Processing Systems, 31, 2018.
  * [PR23] Binghui Peng and Aviad Rubinstein.  Near optimal memory-regret tradeoff for online learning.  In 2023 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 2023.
  * [PZ23] Binghui Peng and Fred Zhang.  Online prediction in sub-linear space.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1611–1634. SIAM, 2023.
  * [Qia18] Mingda Qiao.  Do outliers ruin collaboration?  In International Conference on Machine Learning, pages 4180–4187. PMLR, 2018.
  * [RM19] Hamed Rahimian and Sanjay Mehrotra.  Distributionally robust optimization: A review.  arXiv preprint arXiv:1908.05659, 2019.
  * [RY21] Guy N Rothblum and Gal Yona.  Multi-group agnostic pac learnability.  In International Conference on Machine Learning, pages 9107–9115. PMLR, 2021.
  * [Sau72] Norbert Sauer.  On the density of families of sets.  Journal of Combinatorial Theory, Series A, 13(1):145–147, 1972\.
  * [Sch90] Robert E Schapire.  The strength of weak learnability.  Machine learning, 5:197–227, 1990.
  * [Sch13] Robert E Schapire.  Explaining adaboost.  In Empirical Inference: Festschrift in Honor of Vladimir N. Vapnik, pages 37–52. Springer, 2013.
  * [SFGJ21] Shubhanshu Shekhar, Greg Fields, Mohammad Ghavamzadeh, and Tara Javidi.  Adaptive sampling for minimax fair classification.  Advances in Neural Information Processing Systems, 34:24535–24544, 2021.
  * [She72] Saharon Shelah.  A combinatorial problem; stability and order for models and theories in infinitary languages.  Pacific Journal of Mathematics, 41(1):247–261, 1972.
  * [SK18] Ozan Sener and Vladlen Koltun.  Multi-task learning as multi-objective optimization.  Advances in neural information processing systems, 31, 2018.
  * [SKHL19] Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang.  Distributionally robust neural networks.  In International Conference on Learning Representations, 2019.
  * [SRKL20] Shiori Sagawa, Aditi Raghunathan, Pang Wei Koh, and Percy Liang.  An investigation of why overparameterization exacerbates spurious correlations.  In International Conference on Machine Learning, pages 8346–8356. PMLR, 2020.
  * [TH22] Christopher J Tosh and Daniel Hsu.  Simple and near-optimal algorithms for hidden stratification and multi-group learning.  In International Conference on Machine Learning, pages 21633–21657. PMLR, 2022.
  * [TZZ19] Chao Tao, Qin Zhang, and Yuan Zhou.  Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 126–146. IEEE, 2019.
  * [Val84] Leslie G Valiant.  A theory of the learnable.  Communications of the ACM, 27(11):1134–1142, 1984.
  * [VC71] VN Vapnik and A Ya Chervonenkis.  On the uniform convergence of relative frequencies of events to their probabilities.  Theory of Probability & Its Applications, 16(2):264–280, 1971\.