PHEW: Constructing Sparse Networks that Learn Fast and Generalize Well\n without Training Data

Shreyas Malakarjun Patil, Constantine Dovrolis

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.

  1. 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.
  2. 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.
  3. 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.

Figure 1: Trace of Path Kernel (Log Scale) vs. Network Density. PHEW (blue circles) achieves a high trace similar to SynFlow-L2, indicating efficient training dynamics.

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.

Figure 5: Comparison of layer widths (remaining units) across different models and datasets. PHEW (blue circles) consistently maintains wider layers compared to SynFlow-based methods, avoiding the bottlenecks that hamper generalization.

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

Abstract

Methods that sparsify a network at initialization are important in practice\nbecause they greatly improve the efficiency of both learning and inference. Our\nwork is based on a recently proposed decomposition of the Neural Tangent Kernel\n(NTK) that has decoupled the dynamics of the training process into a\ndata-dependent component and an architecture-dependent kernel - the latter\nreferred to as Path Kernel. That work has shown how to design sparse neural\nnetworks for faster convergence, without any training data, using the\nSynflow-L2 algorithm. We first show that even though Synflow-L2 is optimal in\nterms of convergence, for a given network density, it results in sub-networks\nwith "bottleneck" (narrow) layers - leading to poor performance as compared to\nother data-agnostic methods that use the same number of parameters. Then we\npropose a new method to construct sparse networks, without any training data,\nreferred to as Paths with Higher-Edge Weights (PHEW). PHEW is a probabilistic\nnetwork formation method based on biased random walks that only depends on the\ninitial weights. It has similar path kernel properties as Synflow-L2 but it\ngenerates much wider layers, resulting in better generalization and\nperformance. PHEW achieves significant improvements over the data-independent\nSynFlow and SynFlow-L2 methods at a wide range of network densities.\n
BibTeX
@inproceedings{patil2021phew,
  author = {Shreyas Malakarjun Patil and Constantine Dovrolis},
  title = {{PHEW: Constructing Sparse Networks that Learn Fast and Generalize Well\textbackslash\{\}n without Training Data}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=2kjQPCNKVep},
}
Figure