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 ℝd, and stacked design matrices and responses A and b, our algorithm obtains a (1+varepsilon)-multiplicative optimal solution using widetildeO(minmathsfrank(A),m1/3varepsilon-2/3) linear-system-solves of matrices of the form AtopBA 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 ℓ∞ regression. We also give algorithms that smoothly interpolate between minimizing the average least squares loss and the distributionally robust loss.