Abstract: The minimax sample complexity of group distributionally robust optimization (GDRO) has been determined up to a $\log(K)$ factor, where $K$ is the number of groups. In this work, we venture beyond the minimax perspective via a novel notion of sparsity that we call $(\lambda, \beta)$-sparsity. In short, this condition means that at any parameter $\theta$, there is a set of at most $\beta$ groups whose risks at $\theta$ are all at least $\lambda$ larger than the risks of the other groups. To find an $\epsilon$-optimal $\theta$, we show via a novel algorithm and analysis that the $\epsilon$-dependent term in the sample complexity can swap a linear dependence on $K$ for a linear dependence on the potentially much smaller $\beta$. This improvement leverages recent progress in sleeping bandits, showing a fundamental connection between the two-player zero-sum game optimization framework for GDRO and per-action regret bounds in sleeping bandits. We next show an adaptive algorithm which, up to logarithmic factors, obtains a sample complexity bound that adapts to the best $(\lambda, \beta)$-sparsity condition that holds. We also show how to obtain a dimension-free semi-adaptive sample complexity bound with a computationally efficient method.Finally, we demonstrate the practicality of the $(\lambda, \beta)$-sparsity condition and the improved sample efficiency of our algorithms on both synthetic and real-life datasets.

Lay Summary:

If someone who already has a motorbike driving license wants to get a car driving license, they would not spend too much time on learning the common knowledge such as the signs of the road or where to get shelter under bad weather. Instead, they would focus on the specific car-driving skills that make driving a car more challenging than driving a motorbike.Similarly, for a machine that has to learn to perform well on different tasks, it is much more resource-efficient to collect and learn from the data of the most difficult tasks so that the machine can do well not only on easy tasks but also on challenging tasks. Our work presents a number of novel machine learning algorithms that efficiently discover the most difficult tasks, accurately estimate how much the tasks differ from each other, and strategically choose the data from the most difficult tasks to learn from.Through rigorous mathematical arguments, we show that these new algorithms are guaranteed to be resource-efficient and have well-balanced performances when learning a multitude of different tasks.