  Multi-distribution learning (MDL), which seeks to learn a shared model that
minimizes the worst-case risk across $k$ distinct data distributions, has
emerged as a unified framework in response to the evolving demand for
robustness, fairness, multi-group collaboration, etc. Achieving data-efficient
MDL necessitates adaptive sampling, also called on-demand sampling, throughout
the learning process. However, there exist substantial gaps between the
state-of-the-art upper and lower bounds on the optimal sample complexity.
Focusing on a hypothesis class of Vapnik-Chervonenkis (VC) dimension d, we
propose a novel algorithm that yields an varepsilon-optimal randomized
hypothesis with a sample complexity on the order of (d+k)/varepsilon^2 (modulo
some logarithmic factor), matching the best-known lower bound. Our algorithmic
ideas and theory are further extended to accommodate Rademacher classes. The
proposed algorithms are oracle-efficient, which access the hypothesis class
solely through an empirical risk minimization oracle.
  Additionally, we establish the necessity of randomization, revealing a large
sample size barrier when only deterministic hypotheses are permitted. These
findings resolve three open problems presented in COLT 2023 (i.e.,
citet[Problems 1, 3 and 4]{awasthi2023sample}).
