# Computing Lewis weights to high precision using local relative smoothness

arXiv: https://arxiv.org/abs/2606.29186 · HTML: https://mlsanity.com/paper/2606.29186/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2026.

## Built on by (most cited first, 1 of 1)

- [A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra](https://mlsanity.com/paper/2608.25273/) (2026)

## Abstract (arXiv)

We provide algorithms that compute ε-estimates of the ℓp-Lewis weights of a matrix A ∈ ℝm × n for p ≥ 4 using O(p2 log(m/ε)) rounds of leverage score computation, where ℓ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(p3 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 ℓp-Lewis weight optimization problem and providing tools to convert between different notions of approximate ℓp-Lewis weights.