Revisiting Pruning at Initialization Through the Lens of Ramanujan Graph-猫眼课题宝

DOI：

发表时间：

2023

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Duc L. N. Hoang;Shiwei Liu;R. Marculescu;Zhangyang Wang

在初始化时修剪神经网络（派）由于其端到端的节省潜力而受到了极大的关注。派能够在初始化时找到可以实现与完整网络相当的性能的稀疏子网。这些方法可以超越随机修剪的平凡基线，但与训练后修剪相比，存在显着的性能差距。以前的方法在进行派分析时，完全依赖于权重、梯度和健全性检查作为主要信号。为了更好地理解派的潜在机制，我们建议通过拉马努金图的透镜来解释它-拉马努金图是一类稀疏而高度连接的扩展图。人们通常认为Ramanujan图和派之间应该有很强的相关性，因为两者都是关于寻找稀疏和连接良好的神经网络。然而，将高度稀疏和连接的网络与其相对性能（即，在相同的特定全局稀疏度下对不同稀疏结构进行排名）联系起来的更细粒度的链接仍然缺失。我们观察到，不仅稀疏网络的Ramanujan属性与派的相对性能没有显着关系，而且最大化它也会导致形成没有结构意义的伪随机图。我们揭示了根本原因是拉马努金图的强假设的最大非平凡特征值（µ）的上界属于高度稀疏的网络。因此，我们提出了迭代平均差界（IMDB）作为放松上界的一种手段。同样，我们还表明，存在一个下限，我们称之为归一化随机系数（NaRC），它为我们提供了一个准确的评估，当稀疏但高度连接时，

Pruning neural networks at initialization (PaI) has received an upsurge of interest due to its end-to-end saving potential. PaI is able to find sparse subnetworks at initialization that can achieve comparable performance to the full networks. These methods can surpass the trivial baseline of random pruning but suffer from a significant performance gap compared to post-training pruning. Previous approaches firmly rely on weights, gradients, and sanity checks as primary signals when conducting PaI analysis. To better understand the underlying mechanism of PaI, we propose to interpret it through the lens of the Ramanujan Graph - a class of expander graphs that are sparse while being highly connected. It is often believed there should be a strong correlation between the Ramanujan graph and PaI since both are about finding sparse and well-connected neural networks. However, the finer-grained link relating highly sparse and connected networks to their relative performance ( i.e. , ranking of difference sparse structures at the same specific global sparsity) is still missing. We observe that not only the Ramanujan property for sparse networks shows no significant relationship to PaI’s relative performance, but maximizing it can also lead to the formation of pseudo-random graphs with no structural meanings. We reveal the underlying cause to be Ramanujan Graph’s strong assumption on the upper bound of the largest nontrivial eigenvalue ( ˆ µ ) of layers belonging to highly sparse networks. We hence propose Iterative Mean Difference of Bound (IMDB) as a mean to relax the ˆ µ upper bound. Likewise, we also show there exists a lower bound for ˆ µ , which we call the Normalized Random Coefficient (NaRC), that gives us an accurate assessment for when sparse but highly connected

Revisiting Pruning at Initialization Through the Lens of Ramanujan Graph

文献摘要

相似文献