A Study on the Ramanujan Graph Property of Winning Lottery Tickets

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

  • Fulltext

    Final published version, 4.54 MB, PDF document

  • Bithika Pal
  • Arindam Biswas
  • Sudeshna Kolay
  • Pabitra Mitra
  • Biswajit Basu

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 languageEnglish
Title of host publicationProceedings of the 39 th International Conference on Machine Learning
Number of pages16
Volume162
PublisherPMLR
Publication date2022
Pages17186-17201
Publication statusPublished - 2022
Event39th International Conference on Machine Learning, ICML 2022 - Baltimore, United States
Duration: 17 Jul 202223 Jul 2022

Conference

Conference39th International Conference on Machine Learning, ICML 2022
LandUnited States
ByBaltimore
Periode17/07/202223/07/2022
SeriesProceedings of Machine Learning Research
Volume162
ISSN2640-3498

Bibliographical note

Publisher Copyright:
Copyright © 2022 by the author(s)

ID: 359598284