# Distributionally Robust Linear Regression With Block Lewis Weights

arXiv: https://arxiv.org/abs/2607.00252 · HTML: https://mlsanity.com/paper/2607.00252/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 2 references that are in the map.
- First posted on arXiv 30 Jun 2026.

## Abstract (arXiv)

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.