A Study on the Ramanujan Graph Property of Winning Lottery Tickets

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

  • Fulltext

    Forlagets udgivne version, 4,54 MB, PDF-dokument

  • 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.

OriginalsprogEngelsk
TitelProceedings of the 39 th International Conference on Machine Learning
Antal sider16
Vol/bind162
ForlagPMLR
Publikationsdato2022
Sider17186-17201
StatusUdgivet - 2022
Begivenhed39th International Conference on Machine Learning, ICML 2022 - Baltimore, USA
Varighed: 17 jul. 202223 jul. 2022

Konference

Konference39th International Conference on Machine Learning, ICML 2022
LandUSA
ByBaltimore
Periode17/07/202223/07/2022
NavnProceedings of Machine Learning Research
Vol/bind162
ISSN2640-3498

Bibliografisk note

Funding Information:
A. Biswas acknowledges the support of the grant ISF 1226/19 of C. Meiri at the Technion and the ERC grant 716424-CASe of K. Adiprasito at the Univ. of Copenhagen.

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

Links

ID: 359598284