{"ID":5552865,"CreatedAt":"2026-07-02T01:54:51.863792489Z","UpdatedAt":"2026-07-03T23:00:58.017711474Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.00252","arxiv_id":"2607.00252","title":"Distributionally Robust Linear Regression With Block Lewis Weights","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.","short_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\\...","url_abs":"https://arxiv.org/abs/2607.00252","url_pdf":"https://arxiv.org/pdf/2607.00252v1","authors":"[\"Naren Sarayu Manoj\",\"Kumar Kshitij Patel\"]","published":"2026-06-30T23:01:08Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.DS\",\"math.OC\",\"stat.ML\"]","methods":"[]","has_code":false}