Abstract
Methods that sparsify a network at initialization are important in practice because they greatly improve the efficiency of both learning and inference. Our work is based on a recently proposed decomposition of the Neural Tangent Kernel (NTK) that decouples training dynamics into a data-dependent component and an architecture-dependent kernel—the Path Kernel. While previous methods like SynFlow-L2 optimize for convergence speed by maximizing the Path Kernel trace, they often result in "bottleneck" layers that degrade performance. We propose PHEW (Paths with Higher-Edge Weights), a probabilistic network formation method based on biased random walks. PHEW generates much wider layers than SynFlow-L2 while maintaining similar path kernel properties, leading to superior generalization and performance across various network densities without requiring any training data.
Introduction
Pruning at initialization, or finding "winning tickets" before training, is a promising direction for reducing the computational cost of deep learning. Recent theoretical advances have highlighted the role of the Path Kernel in determining convergence speed. However, a singular focus on convergence speed can lead to sub-optimal architectures. Specifically, the SynFlow-L2 algorithm, while optimal for convergence, tends to prune layers so aggressively that it creates narrow bottlenecks, limiting the model's representational capacity.
The PHEW Algorithm
PHEW is a data-agnostic method that constructs sparse networks by selecting paths based on initial weight magnitudes.
- Biased Random Walks: PHEW performs random walks where the probability of choosing an edge is proportional to its weight. This naturally selects paths with high edge-weight products, which correlates with a high Path Kernel trace.
- Probabilistic Selection: Unlike greedy pruning, the stochastic nature of PHEW ensures that connections are distributed across the network's width, preventing the formation of bottlenecks.
- Structural Integrity: By initiating walks from both inputs and outputs in a round-robin fashion, PHEW ensures full connectivity and prevents layer collapse, a common issue in other pruning methods at high sparsity.
Results and Analysis
Convergence and Path Kernel Trace
Experimental results on CIFAR-10 and CIFAR-100 show that PHEW achieves Path Kernel trace values comparable to SynFlow-L2. This confirms that PHEW retains the theoretical advantages for fast convergence without needing data during the pruning phase.
Architectural Width and Performance
The key differentiator for PHEW is its ability to maintain layer width. Visualizing the number of remaining units per layer reveals that PHEW-generated sub-networks are significantly wider than those produced by SynFlow-L2, which often collapses layers to a few units.
This architectural advantage translates to higher Top-1 accuracy. PHEW consistently outperforms other data-independent methods and even rivals or beats data-dependent methods like SNIP and GraSP at extreme sparsity levels.
Conclusion
PHEW provides a powerful, data-agnostic approach to pruning at initialization. By leveraging biased random walks to balance convergence speed with architectural width, it constructs sparse networks that learn fast and generalize well. Its performance relative to data-dependent methods suggests that the initial random weights of a network contain significant structural information that can be exploited for efficient model design.
Summary updated