{"id":"arxiv/2607.00252","url":"https://arxiv.org/abs/2607.00252","tags":["cs.LG","cs.DS","math.OC","stat.ML"],"score":0,"title":"Distributionally Robust Linear Regression With Block Lewis Weights","domain":"cs.LG","source":"arxiv","authors":["Naren Sarayu Manoj","Kumar Kshitij Patel"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-30","reactions":{}}