A Tighter Complexity Analysis of SparseGPT
<|reference_start|>A Tighter Complexity Analysis of SparseGPT: In this work, we improved the analysis of the running time of SparseGPT [Frantar, Alistarh ICML 2023] from $O(d^{3})$ to $O(d^{\omega} + d^{2+a+o(1)} + d^{1+\omega(1,1,a)-a})$ for any $a \in [0, 1]$, where $\omega$ is the exponent of matrix multiplication. In particular, for the current $\omega \approx 2.371$ [Alman, Duan, Williams, Xu, Xu, Zhou 2024], our running times boil 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].<|reference_end|>
@article{li2024a,
    title={A Tighter Complexity Analysis of SparseGPT},
    author={Xiaoyu Li, Yingyu Liang, Zhenmei Shi, Zhao Song},
    journal={arXiv preprint arXiv:2408.12151},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.12151},
    primaryClass={cs.DS cs.AI cs.CL cs.LG}
}