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 A and b, our algorithm obtains a (1+\varepsilon)-multiplicative optimal solution using \widetilde{O}(\min{rank(A),m}^{1/3}\varepsilon^{-2/3}) linear-system-solves of matrices of the form A^{\top}BA for block-diagonal 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 \ell_{\infty} regression. We also give algorithms that smoothly interpolate between minimizing the average least squares loss and the distributionally robust loss.