{"id":"arxiv/2606.29186","url":"https://arxiv.org/abs/2606.29186","tags":["cs.DS","math.OC"],"score":0,"title":"Computing Lewis weights to high precision using local relative smoothness","domain":"cs.DS","source":"arxiv","authors":["Sander Gribling","Aaron Sidford","Chenyi Zhang"],"reviews":0,"subject":"cs.DS","summary":"We provide algorithms that compute $ε$-estimates of the $\\ell_p$-Lewis weights of a matrix $A \\in \\mathbb{R}^{m \\times n}$ for $p \\geq 4$ using $O(p^2 \\log(m/ε))$ rounds of leverage score computation, where $\\ell_p$-Lewis weights and leverage scores are both standard measures of row importance. This improves upon the state-of-the-art round complexity of $O(p^3 \\log(m/ε))$ due to Fazel, Lee, Padmanabha, and Sidford (2022). We obtain our results by carefully applying a local variant of relatively smooth gradient descent to primal and dual forms of the $\\ell_p$-Lewis weight optimization problem…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-28","reactions":{}}