A Tighter Complexity Analysis of SparseGPT

Li, Xiaoyu, Liang, Yingyu, Shi, Zhenmei, Song, Zhao

arXiv.org Artificial Intelligence 

In particular, for the current ω 2.371 [Alman, Duan, Williams, Xu, Xu, Zhou 2024], our running times boil down to O(d 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]. Large Language Models (LLMs) have been widely applied in many AI applications.