Distribution-Dependent Rates for Multi-Distribution Learning
Rafael Hanashiro Patrick Jaillet
To address the needs of modeling uncertainty in sensitive machine learning
applications, the setup of distributionally robust optimization (DRO) seeks
good performance uniformly across a variety of tasks. The recent
multi-distribution learning (MDL) framework tackles this objective in a dynamic
interaction with the environment, where the learner has sampling access to each
target distribution. Drawing inspiration from the field of pure-exploration
multi-armed bandits, we provide distribution-dependent guarantees in the MDL
regime, that scale with suboptimality gaps and result in superior dependence on
the sample size when compared to the existing distribution-independent
analyses. We investigate two non-adaptive strategies, uniform and non-uniform
exploration, and present non-asymptotic regret bounds using novel tools from
empirical process theory. Furthermore, we devise an adaptive optimistic
algorithm, LCB-DR, that showcases enhanced dependence on the gaps, mirroring
the contrast between uniform and optimistic allocation in the multi-armed
bandit literature.