Distribution-Dependent Rates for Multi-Distribution Learning
This work addresses uncertainty modeling in sensitive ML applications by advancing the MDL framework, offering incremental improvements in sample efficiency for distributionally robust optimization.
The paper tackled the problem of multi-distribution learning (MDL) by providing distribution-dependent guarantees that scale with suboptimality gaps, resulting in improved sample size dependence compared to existing distribution-independent analyses, with non-asymptotic regret bounds and an adaptive algorithm (LCB-DR) showing enhanced gap dependence.
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.