Abstract
In this work, we improved the analysis of the running time of SparseGPT [Frantar, Alistarh ICML 2023] from O(d³) to O(d^ω + d^2+a+o(1) + d^1+ω(1,1,a)-a) for any a ∈ [0, 1], where ω is the exponent of matrix multiplication. In particular, for the current ω ≈ 2.371 [Alman, Duan, Williams, Xu, Xu, Zhou 2024], our running time boils down to O(d^2.53). This running time is due to the analysis of the lazy update behavior in iterative maintenance problems such as [Deng, Song, Weinstein 2022; Brand, Song, Zhou ICML 2024].