Computing Lewis weights to high precision using local relative smoothness

Abstract

We provide algorithms that compute $\hat{I}\mu$-estimates of the ${\ell }_p$-Lewis weights of a matrix $A\in {\mathbb{R}}^{m\times n}$ for $p\ge 4$ using $O(p^2\log (m/\hat{I}\mu ))$ 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/\hat{I}\mu ))$ 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 and providing tools to convert between different notions of approximate ${\ell }_p$-Lewis weights.

This work subsumes the note "On computing approximate Lewis weights'' by Apers, Gribling, Sidford. To appear at COLT 2026