# Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond

arXiv: https://arxiv.org/abs/2302.09267 · HTML: https://mlsanity.com/paper/2302.09267/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 64 references that are in the map.
- First posted on arXiv 18 Feb 2023.

## Builds on (most cited first, 15 of 15)

- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Large-Scale Methods for Distributionally Robust Optimization](https://mlsanity.com/paper/2010.05893/) (2020)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Coping with Label Shift via Distributionally Robust Optimisation](https://mlsanity.com/paper/2010.12230/) (2020)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives](https://mlsanity.com/paper/2006.10138/) (2020)
- [On-Demand Sampling: Learning Optimally from Multiple Distributions](https://mlsanity.com/paper/2210.12529/) (2022)
- [Does Distributionally Robust Supervised Learning Give Robust Classifiers?](https://mlsanity.com/paper/1611.02041/) (2016)
- [Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2109.11926/) (2021)
- [Minimax Regret Optimization for Robust Machine Learning under Distribution Shift](https://mlsanity.com/paper/2202.05436/) (2022)
- [Class-Weighted Classification: Trade-offs and Robust Approaches](https://mlsanity.com/paper/2005.12914/) (2020)
- [Near-Optimal Algorithms for Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2212.13669/) (2022)
- [Distributionally Robust Optimization via Ball Oracle Acceleration](https://mlsanity.com/paper/2203.13225/) (2022)

## Built on by (most cited first, 4 of 4)

- [StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models](https://mlsanity.com/paper/2604.15416/) (2026)
- [Maximum Risk Minimization with Random Forests](https://mlsanity.com/paper/2512.10445/) (2025)
- [Group Distributionally Robust Optimization with Flexible Sample Queries](https://mlsanity.com/paper/2505.15212/) (2025)
- [Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compression](https://mlsanity.com/paper/2609.36610/) (2026)

## Abstract (arXiv)

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, which is then solved by stochastic mirror descent (SMD) with m samples in each iteration, and attain 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 scenarios involving imbalanced data and heterogeneous distributions. In the first scenario, we introduce a weighted variant of GDRO, enabling distribution-dependent convergence rates that rely on the number of samples from each distribution. We design two strategies to meet the sample budget: one integrates non-uniform sampling into SMD, and the other employs the stochastic mirror-prox algorithm with mini-batches, both of which deliver faster rates for distributions with more samples. In the second 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 an online algorithm for non-oblivious combinatorial semi-bandits.