Unverified

The Sample Complexity of Multi-Distribution Learning

For $\epsilon,delta\in(0,1)$ , let $m_{\mathcal H}(\epsilon,\delta,k)$ be the minimum total number of adaptive example-oracle queries needed to return, with probability at least $1-\delta$ , a possibly randomized $h$ satisfying

\max_{D\in\mathcal D}L_D(h) \leq\epsilon+\min_{h^*\in\mathcal H}\max_{D\in\mathcal D}L_D(h^*).

Problem 1.

If $\operatorname{VC}(\mathcal H)=d$ , is

m_{\mathcal H}(\epsilon,\delta,k) =O\!\left(\epsilon^{-2}(d\log k+k\log(k/\delta))\right)?

Problem 2.

Is every general multi-distribution learner subject to a lower bound $\Omega(\epsilon^{-2}d\log k)$ ?

Problem 3.

What is the sample complexity when the output must be a single proper hypothesis $h\in\mathcal H$ , rather than a randomized or improper hypothesis?

Problem 4.

What is the sample complexity of an oracle-efficient learner that accesses $\mathcal H$ only through an empirical-risk-minimization oracle? Is there a statistical--computational tradeoff?

Download

Abstract

Multi-distribution learning generalizes agnostic learning to multiple data distributions. Given sample access to $k$ distributions, the goal is to output one possibly randomized hypothesis whose worst-case loss is within $\epsilon$ of the best hypothesis in the class. We ask whether a class of VC dimension $d$ can be learned with $O(\epsilon^{-2}(d\log k+k\log(k/\delta)))$ samples, and pose related questions about lower bounds, proper learning, and oracle-efficient learning.

Background and progress

Let $\mathcal D=\{D_1,\ldots,D_k\}$ be distributions on $\mathcal X\times\mathcal Y$ , let $\ell$ be a loss, and let $\mathcal H$ be a hypothesis class. Write

L_D(h)=\mathbb E_{(x,y)\sim D}[\ell(h,(x,y))], \qquad \operatorname{OPT}=\min_{h^*\in\mathcal H}\max_{D\in\mathcal D}L_D(h^*).

An $\epsilon$ -optimal solution satisfies $\max_{D\in\mathcal D}L_D(h)\leq\operatorname{OPT}+\epsilon$ . At each round, the learner chooses which example oracle $D_i$ to query and may adapt this choice to all previous observations.

Haghtalab, Jordan, and Zhao introduced this setting and obtained upper and lower bounds that leave a logarithmic and accuracy-dependent gap for infinite VC classes [Haghtalab et al., 2022]. The best general upper bounds either avoid a $dk$ factor at the price of $\epsilon^{-4}$ dependence or achieve $\epsilon^{-2}$ dependence while retaining an additional $dk$ term. The lower bound is $\Omega(\epsilon^{-2}(d+k\log(\min\{d,k\}/\delta))).$ For finite classes, the optimal $\widetilde O(\epsilon^{-2}\log|\mathcal H|)$ dependence is known, and near-optimal bounds are known in realizable and personalized variants.

Existing algorithms formulate the task as a zero-sum game between a learner choosing hypotheses and an adversary choosing distributions. The main obstacles are constructing adaptive covers of an infinite VC class, converting realizable algorithms to the agnostic setting while choosing sample sources online, and bounding the learner's regret using the adversary's behavior.

Reference papers

On-Demand Sampling: Learning Optimally from Multiple DistributionsNika Haghtalab, Michael I. Jordan, Eric ZhaoCoRR · 2022

The Sample Complexity of Multi-Distribution Learning

Problem 1.

Problem 2.

Problem 3.

Problem 4.

Coming soon

Organizer