A Tighter Complexity Analysis of SparseGPT
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929549020758016 |
|---|---|
| author | Li, Xiaoyu Liang, Yingyu Shi, Zhenmei Song, Zhao |
| author_facet | Li, Xiaoyu Liang, Yingyu Shi, Zhenmei Song, Zhao |
| contents | In this work, we improved the analysis of the running time of SparseGPT [Frantar, Alistarh ICML 2023] from $O(d^{3})$ to $O(d^ω + d^{2+a+o(1)} + d^{1+ω(1,1,a)-a})$ for any $a \in [0, 1]$, where $ω$ is the exponent of matrix multiplication. In particular, for the current $ω\approx 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]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_12151 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Tighter Complexity Analysis of SparseGPT Li, Xiaoyu Liang, Yingyu Shi, Zhenmei Song, Zhao Data Structures and Algorithms Artificial Intelligence Computation and Language Machine Learning In this work, we improved the analysis of the running time of SparseGPT [Frantar, Alistarh ICML 2023] from $O(d^{3})$ to $O(d^ω + d^{2+a+o(1)} + d^{1+ω(1,1,a)-a})$ for any $a \in [0, 1]$, where $ω$ is the exponent of matrix multiplication. In particular, for the current $ω\approx 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]. |
| title | A Tighter Complexity Analysis of SparseGPT |
| topic | Data Structures and Algorithms Artificial Intelligence Computation and Language Machine Learning |
| url | https://arxiv.org/abs/2408.12151 |