We present 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. This improves upon the state-of-the-art round complexity of $O(p^3 \log(m/\epsilon))$ from Fazel et al. (2022). Our results are derived by carefully applying a local variant of relatively smooth gradient descent to the primal and dual forms of the $\ell_p$-Lewis weight optimization problem, and we provide tools to convert between different notions of approximate $\ell_p$-Lewis weights.
Blogger's Review: The algorithm proposed in this paper significantly enhances the efficiency of computing Lewis weights by reducing computational complexity, making it applicable to higher-dimensional matrices. The application of relatively smooth gradient descent demonstrates the powerful potential of optimization algorithms in practical problems.