Efficient Algorithms for Empirical Group Distributional Robust
  Optimization and Beyond
Dingzhi Yu Yunuo Cai Wei Jiang Lijun Zhang
We investigate the empirical counterpart of group distributionally robust
optimization (GDRO), which aims to minimize the maximal empirical risk across
$m$ distinct groups. We formulate empirical GDRO as a $\textit{two-level}$
finite-sum convex-concave minimax optimization problem and develop a stochastic
variance reduced mirror prox algorithm. Unlike existing methods, we construct
the stochastic gradient by per-group sampling technique and perform variance
reduction for all groups, which fully exploits the $\textit{two-level}$
finite-sum structure of empirical GDRO. Furthermore, we compute the snapshot
and mirror snapshot point by a one-index-shifted weighted average, which
distinguishes us from the naive ergodic average. Our algorithm also supports
non-constant learning rates, which is different from existing literature. We
establish convergence guarantees both in expectation and with high probability,
demonstrating a complexity of
$\mathcal{O}\left(\frac{m\sqrt{\bar{n}\ln{m}}}{\varepsilon}\right)$, where
$\bar n$ is the average number of samples among $m$ groups. Remarkably, our
approach outperforms the state-of-the-art method by a factor of $\sqrt{m}$.
Furthermore, we extend our methodology to deal with the empirical minimax
excess risk optimization (MERO) problem and manage to give the expectation
bound and the high probability bound, accordingly. The complexity of our
empirical MERO algorithm matches that of empirical GDRO at
$\mathcal{O}\left(\frac{m\sqrt{\bar{n}\ln{m}}}{\varepsilon}\right)$,
significantly surpassing the bounds of existing methods.