A Study on the Ramanujan Graph Property of Winning Lottery Tickets
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Fulltext
Final published version, 4.54 MB, PDF document
Winning lottery tickets refer to sparse subgraphs of deep neural networks which have classification accuracy close to the original dense networks. Resilient connectivity properties of such sparse networks play an important role in their performance. The attempt is to identify a sparse and yet well-connected network to guarantee unhindered information flow. Connectivity in a graph is best characterized by its spectral expansion property. Ramanujan graphs are robust expanders which lead to sparse but highly-connected networks, and thus aid in studying the winning tickets. A feed-forward neural network consists of a sequence of bipartite graphs representing its layers. We analyze the Ramanujan graph property of such bipartite layers in terms of their spectral characteristics using the Cheeger's inequality for irregular graphs. It is empirically observed that the winning ticket networks preserve the Ramanujan graph property and achieve a high accuracy even when the layers are sparse. Accuracy and robustness to noise start declining as many of the layers lose the property. Next we find a robust winning lottery ticket by pruning individual layers while retaining their respective Ramanujan graph property. This strategy is observed to improve the performance of existing network pruning algorithms.
Original language | English |
---|---|
Title of host publication | Proceedings of the 39 th International Conference on Machine Learning |
Number of pages | 16 |
Volume | 162 |
Publisher | PMLR |
Publication date | 2022 |
Pages | 17186-17201 |
Publication status | Published - 2022 |
Event | 39th International Conference on Machine Learning, ICML 2022 - Baltimore, United States Duration: 17 Jul 2022 → 23 Jul 2022 |
Conference
Conference | 39th International Conference on Machine Learning, ICML 2022 |
---|---|
Land | United States |
By | Baltimore |
Periode | 17/07/2022 → 23/07/2022 |
Series | Proceedings of Machine Learning Research |
---|---|
Volume | 162 |
ISSN | 2640-3498 |
Bibliographical note
Publisher Copyright:
Copyright © 2022 by the author(s)
Links
- https://proceedings.mlr.press/v162/pal22a.html
Final published version
ID: 359598284