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 has decoupled the dynamics of the training process into a data-dependent component and an architecture-dependent kernel - the latter referred to as Path Kernel. That work has shown how to design sparse neural networks for faster convergence, without any training data, using the Synflow-L2 algorithm. We first show that even though Synflow-L2 is optimal in terms of convergence, for a given network density, it results in sub-networks with "bottleneck" (narrow) layers - leading to poor performance as compared to other data-agnostic methods that use the same number of parameters. Then we propose a new method to construct sparse networks, without any training data, referred to as Paths with Higher-Edge Weights (PHEW). PHEW is a probabilistic network formation method based on biased random walks that only depends on the initial weights. It has similar path kernel properties as Synflow-L2 but it generates much wider layers, resulting in better generalization and performance. PHEW achieves significant improvements over the data-independent SynFlow and SynFlow-L2 methods at a wide range of network densities.
Introduction
Deep neural networks are typically over-parameterized, necessitating pruning techniques to improve computational efficiency. While traditional pruning occurs after training, recent research focuses on "pruning at initialization" to find "winning tickets" before training starts. Methods like SNIP or GraSP require small amounts of data, while "data-agnostic" methods rely solely on the network's initial structure and weights.
The current state-of-the-art data-agnostic method, SynFlow, is designed to maximize the "Path Kernel trace," a theoretical metric linked to convergence speed. However, maximizing this trace often results in "bottleneck layers"—extremely narrow layers that act as information chokepoints, severely degrading the network's final accuracy and generalization capabilities.
Methods: Paths with Higher-Edge Weights (PHEW)
PHEW is a novel probabilistic approach for pruning at initialization. It leverages the decomposition of the Neural Tangent Kernel (NTK) to identify architectures that learn fast and generalize well.
Instead of scoring individual edges deterministically, PHEW selects entire input-output paths through biased random walks. Starting from both input and output units, the algorithm traverses the network with transition probabilities proportional to the magnitude of the initial weights $|w_{ij}|$. Connections belonging to these selected "high-weight paths" are retained. This probabilistic selection ensures that the resulting sparse network maintains the original width of the layers rather than collapsing into narrow bottlenecks. Furthermore, because PHEW selects complete paths, it is mathematically immune to "layer collapse," a common failure mode where all connections in a single layer are accidentally removed.
Experimental Results
The authors evaluated PHEW across CIFAR-10, CIFAR-100, and Tiny ImageNet benchmarks using ResNet and VGG architectures.
Path Kernel and Convergence
PHEW achieves a Path Kernel trace nearly as high as the theoretically optimal SynFlow-L2. As shown in Figure 1, PHEW maintains high trace values across a wide range of network densities, ensuring fast convergence without the performance penalties associated with previous methods.
Structural Integrity and Layer Width
A defining characteristic of PHEW is its ability to avoid bottleneck layers. While SynFlow and SynFlow-L2 often reduce certain layers to just a few neurons, PHEW maintains a per-layer width nearly identical to the original unpruned network.
As illustrated in Figure 2, SynFlow-based methods exhibit sharp drops in unit counts in specific layers (e.g., layers 14-18 in ResNet20). In contrast, PHEW preserves the structural width, which the authors demonstrate is critical for effective generalization. This structural integrity allows PHEW to consistently achieve higher Top-1 accuracy than other data-agnostic methods and often outperform data-dependent methods like SNIP and GraSP.
Conclusion
PHEW demonstrates that the structural information present in initial random weights is a powerful signal for finding efficient sub-networks. By balancing the maximization of the Path Kernel trace with the preservation of layer width, PHEW provides a robust, data-agnostic solution for pruning at initialization. Future work may explore hybrid approaches that incorporate minimal data or dynamic sparsity adjustments during the path selection process.
Summary updated