用图极限理论解释初始化剪枝,揭示稀疏网络的表达与泛化机制。
Pruning at Initialisation through the lens of Graphon Limit: Convergence, Expressivity, and Generalisation
- 通过图极限理论建立剪枝掩码的连续表征,统一分析各类剪枝方法。
- 发现无结构剪枝收敛到均匀连通图,数据驱动剪枝则编码特征选择。
- 给出稀疏网络的通用逼近定理和基于图极限的泛化界,适合理论研究者。
初始化剪枝方法在训练前发现可训练的稀疏子网络,但其理论机制仍不明确。现有分析多局限于有限宽度统计,缺乏对大网络下全局稀疏模式的严格刻画。本文通过图极限理论(图论)将离散剪枝启发式与图极限联系起来,建立了初始化剪枝掩码的图极限(graphon limit)。提出因子化显著性模型,涵盖主流剪枝准则,并证明在正则条件下,这些算法生成的离散掩码收敛至确定性的双部图极限。该极限框架为稀疏网络提供新拓扑分类:无结构方法(如随机、幅度)收敛至均匀图极限,表示均匀连接;数据驱动方法(如SNIP、GraSP)收敛至异质图极限,编码隐式特征选择。基于此连续表征,我们推导出两个基础理论结果:(i) 稀疏网络的通用逼近定理,仅依赖活跃坐标子空间的内在维度;(ii) 图极限-神经切空间(Graphon-NTK)泛化界,表明极限图极限调节核几何以对齐信息特征。研究将稀疏神经网络分析从组合图问题转化为严格的连续算子框架,为表达能力与泛化提供新机制。
原文摘要 · Abstract (English)
Pruning at Initialisation methods discover sparse, trainable subnetworks before training, but their theoretical mechanisms remain elusive. Existing analyses are often limited to finite-width statistics, lacking a rigorous characterisation of the global sparsity patterns that emerge as networks grow large. In this work, we connect discrete pruning heuristics to graph limit theory via graphons, establishing the graphon limit of PaI masks. We introduce a Factorised Saliency Model that encompasses popular pruning criteria and prove that, under regularity conditions, the discrete masks generated by these algorithms converge to deterministic bipartite graphons. This limit framework establishes a novel topological taxonomy for sparse networks: while unstructured methods (e.g., Random, Magnitude) converge to homogeneous graphons representing uniform connectivity, data-driven methods (e.g., SNIP, GraSP) converge to heterogeneous graphons that encode implicit feature selection. Leveraging this continuous characterisation, we derive two fundamental theoretical results: (i) a Universal Approximation Theorem for sparse networks that depends only on the intrinsic dimension of active coordinate subspaces; and (ii) a Graphon-NTK generalisation bound demonstrating how the limit graphon modulates the kernel geometry to align with informative features. Our results transform the study of sparse neural networks from combinatorial graph problems into a rigorous framework of continuous operators, offering a new mechanism for analysing expressivity and generalisation in sparse neural networks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。