We present an algorithm for the group distributionally robust (GDR) least squares problem. Given $m$ groups, a parameter vector in $\mathbb{R}^d$, and stacked design matrices and responses $\mathbf{A}$ and $\mathbf{b}$, our algorithm achieves a $(1+\epsilon)$-multiplicative optimal solution using $\tilde{O}(\min\{\operatorname{rank}(\mathbf{A}),m\}^{1/3}\epsilon^{-2/3})$ linear system solves of matrices of the form $\mathbf{A}^{\top}\mathbf{B}\mathbf{A}$ for block-diagonal $\mathbf{B}$.
Our technical methods follow from a recent geometric construction, block Lewis weights, which relates the empirical GDR problem to a carefully chosen least squares problem, along with the application of accelerated proximal methods.
Our algorithm improves upon known interior point methods for moderate accuracy regimes and matches the state-of-the-art guarantees for the special case of $\ell_{\infty}$ regression. We also provide algorithms that smoothly interpolate between minimizing the average least squares loss and the distributionally robust loss.
Blogger's Review: The algorithm presented in this paper reveals a new approach to the group distributionally robust least squares problem, integrating geometric constructions with acceleration methods, which holds significant theoretical and practical value. Its advantages in accuracy and flexibility make this research outcome worthy of in-depth attention and exploration.