Computing Lewis weights to high precision using local relative smoothness

Sander Gribling, Aaron Sidford, Chenyi Zhang
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:2901-2939, 2026.

Abstract

We provide algorithms that compute $\epsilon$-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/\epsilon))$ 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/\epsilon))$ 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, and Sidford.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-gribling26a, title = {Computing {Lewis} weights to high precision using local relative smoothness}, author = {Gribling, Sander and Sidford, Aaron and Zhang, Chenyi}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {2901--2939}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/gribling26a/gribling26a.pdf}, url = {https://proceedings.mlr.press/v336/gribling26a.html}, abstract = {We provide algorithms that compute $\epsilon$-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/\epsilon))$ 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/\epsilon))$ 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, and Sidford.} }
Endnote
%0 Conference Paper %T Computing Lewis weights to high precision using local relative smoothness %A Sander Gribling %A Aaron Sidford %A Chenyi Zhang %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-gribling26a %I PMLR %P 2901--2939 %U https://proceedings.mlr.press/v336/gribling26a.html %V 336 %X We provide algorithms that compute $\epsilon$-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/\epsilon))$ 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/\epsilon))$ 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, and Sidford.
APA
Gribling, S., Sidford, A. & Zhang, C.. (2026). Computing Lewis weights to high precision using local relative smoothness. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:2901-2939 Available from https://proceedings.mlr.press/v336/gribling26a.html.

Related Material