Distributionally Robust Linear Regression with Block Lewis Weights

We present an algorithm for the empirical group distributionally robust (GDR) least squares problem. Given m groups, a parameter vector in R d , and stacked design matrices and responses A and b, our algorithm obtains a (1+ε)-multiplicative optimal solution using O(minrank(A), m 1/3 ε -2/3 ) linear-system-solves of matrices of the form A ⊤ 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-ofthe-art guarantees for the special case of ℓ ∞ regression. We also give algorithms that smoothly interpolate between minimizing the average least squares loss and the distributionally robust loss. * This work was partly done while the author was a fellow at the Simons Institute for Theory of Computing. Combining gives , completing the proof of Lemma D.14.