Distributionally Robust Linear Regression With Block Lewis Weights

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 obtains a $(1+\epsilon )$-multiplicative optimal solution using $\tilde{O}(\min \{\mathsf{r}\mathsf{a}\mathsf{n}\mathsf{k}(\mathbf{A}),m{\}}^{1\mathrm{/}3}{\epsilon }^{-2\mathrm{/}3})$ linear-system-solves of matrices of the form ${\mathbf{A}}^{\mathrm{\top }}\mathbf{B}\mathbf{A}$ for block-diagonal $\mathbf{B}$. Our technical methods follow from a recent geometric construction, block Lewis weights, that relates the empirical GDR problem to a carefully chosen least squares problem and an application of accelerated proximal methods. Our algorithm improves over known interior point methods for moderate accuracy regimes and matches the state-of-the-art guarantees for the special case of ${\mathrm{\ell }}_{\mathrm{\infty }}$ regression. We also give algorithms that smoothly interpolate between minimizing the average least squares loss and the distributionally robust loss.