Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond

This paper investigates group distributionally robust optimization (GDRO) with the goal of learning a model that performs well over m different distributions. First, we formulate GDRO as a stochastic convex-concave saddle-point problem and solve it using stochastic mirror descent (SMD) with m samples per iteration, attaining a nearly optimal sample complexity. To reduce the number of samples required in each round from m to 1, we cast GDRO as a two-player game, where one player conducts SMD and the other executes an online algorithm for non-oblivious multi-armed bandits, maintaining the same sample complexity. Next, we extend GDRO to address heterogeneous distributions that contain outliers. In such a scenario, we propose to optimize the average top-k risk instead of the maximum risk, thereby mitigating the impact of outlier distributions. Similar to the case of vanilla GDRO, we develop two stochastic approaches: one uses m samples per iteration via SMD, and the other consumes k samples per iteration through SMD and an online algorithm for non-oblivious combinatorial semi-bandits. Moreover, we propose anytime versions of the proposed algorithms, which can return solutions at any time without predefining the number of iterations.