Computing Lewis weights to high precision using local relative smoothness

Abstract

We provide algorithms that compute ϵ-estimates of the ℓ_p-Lewis weights of a matrix A ∈ℝ^m × n for p ≥ 4 using O(p^2 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(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 ℓ_p-Lewis weight optimization problem and providing tools to convert between different notions of approximate ℓ_p-Lewis weights. This work subsumes the note “On computing approximate Lewis weights” by Apers, Gribling, and Sidford.