Distributionally Robust Linear Regression With Block Lewis Weights
2026-06-30 • Machine Learning
Machine LearningData Structures and Algorithms
AI summaryⓘ
The authors developed a new method to solve a type of robust regression problem that works well across multiple groups of data. Their algorithm finds nearly the best solution using fewer complex calculations than previous methods, especially when moderate accuracy is needed. They used advanced math tools called block Lewis weights and accelerated optimization techniques. Their approach also bridges between focusing on average error and worst-case group error. This improves on older algorithms and matches the best known results for a related problem called infinity-norm regression.
group distributionally robust regressionleast squaresblock Lewis weightsaccelerated proximal methodslinear system solvesinterior point methodsepsilon-approximationrobust optimizationℓ∞ regressionmatrix rank
Authors
Naren Sarayu Manoj, Kumar Kshitij Patel
Abstract
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+\varepsilon)$-multiplicative optimal solution using $\widetilde{O}(\min\{\mathsf{rank}(\mathbf{A}),m\}^{1/3}\varepsilon^{-2/3})$ linear-system-solves of matrices of the form $\mathbf{A}^{\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 $\ell_{\infty}$ regression. We also give algorithms that smoothly interpolate between minimizing the average least squares loss and the distributionally robust loss.