Partially Frozen Random Networks Contain Compact Strong Lottery Tickets

Hikari Otsuka, Daiki Chijiwa, Ángel López García-Arias, Yasuyuki Okoshi, Kazushi Kawamura, Thiem Van Chu, Daichi Fujiki, Susumu Takeuchi, Masato Motomura

Abstract

Randomly initialized dense networks contain subnetworks that achieve high accuracy without weight learning—strong lottery tickets (SLTs). Recently, Gadhikar et al. (2023) demonstrated that SLTs could also be found within a randomly pruned source network. This phenomenon can be exploited to further compress the small memory size required by SLTs. However, their method is limited to SLTs that are even sparser than the source, leading to worse accuracy due to unintentionally high sparsity. This paper proposes a method for reducing the SLT memory size without restricting the sparsity of the SLTs that can be found. A random subset of the initial weights is frozen by either permanently pruning them or locking them as a fixed part of the SLT, resulting in a smaller model size. Experimental results show that Edge-Popup (Ramanujan et al., 2020; Sreenivasan et al., 2022) finds SLTs with better accuracy-to-model size trade-off within frozen networks than within dense or randomly pruned source networks. In particular, freezing 70% of a ResNet on ImageNet provides 3.3× compression compared to the SLT found within a dense counterpart, raises accuracy by up to 14.12 points compared to the SLT found within a randomly pruned counterpart, and offers a better accuracy-model size trade-off than both.

Introduction

The Strong Lottery Ticket Hypothesis (SLTH) suggests that within a large, randomly initialized dense network, there exists a subnetwork (a "ticket") that can achieve high accuracy without ever updating its weights. Finding these tickets involves optimizing a binary mask, or "supermask," which determines which weights are active. While SLTs are efficient—requiring only a bitmask and a random seed—finding them in dense networks still requires a significant memory footprint for that mask.

Recent work attempted to search for tickets within already pruned (sparse) networks to save space. However, this created a "sparsity trap": if the source network is 90% pruned, the final ticket must be at least 90% sparse. Since the most accurate tickets often reside in denser regions, this constraint leads to a substantial drop in performance when forced into extreme sparsity.

Methodology: Partial Freezing

We propose Partial Freezing, a method that reduces the number of parameters to be optimized without forcing the final subnetwork into an ultra-sparse state. At initialization, the network's weights are divided into three categories:

  1. Frozen (Pruned): Randomly selected weights permanently set to zero.
  2. Frozen (Locked): Randomly selected weights permanently "on" (part of the SLT).
  3. Optimization Target: The remaining weights, for which the algorithm (Edge-Popup) searches for the optimal binary mask.
Conceptual comparison of SLT search strategies: Dense, Pruned, and the proposed Frozen (Pruned + Locked) networks.

Because the "Frozen" decisions are random, they can be reconstructed using a simple random seed. Only the mask for the "Optimization Target" region needs to be stored. This allows the search to target the "optimal sparsity" zone for a specific architecture while still benefiting from the compression of a smaller optimized mask.

Experimental Results

We evaluated our method across diverse domains, including image classification (CIFAR-10, ImageNet) and graph node classification (OGBN-Arxiv).

ImageNet Performance

On ImageNet, partial freezing provides a superior accuracy-to-model-size trade-off compared to both dense and randomly pruned source networks. For instance, freezing 70% of a ResNet-50 resulted in a 3.3× compression compared to a dense SLT. Furthermore, the frozen approach outperformed the "randomly pruned" baseline by up to 14.12 points at the same model size.

Accuracy vs. model size trade-off on ImageNet. Partial freezing (green) provides better compression and accuracy than dense (blue) or pruned (orange) baselines.

Key Insights

  • The Sparsity Sweet Spot: Different architectures have different optimal sparsity levels. Freezing allows researchers to "center" the search range around these sweet spots. For example, ResNet-18 on CIFAR-10 performs best at ~90% sparsity, while GNNs prefer denser configurations (~20% sparsity).
  • Locking as a Key Component: By adding "Locked" weights, we can find accurate tickets even in dense regimes while still reducing the number of bits that need to be memorized.
  • Freezing as a Regularizer: Searching within a frozen network sometimes yielded higher accuracy than searching the full dense network, likely because freezing reduces the search space and helps the optimization algorithm avoid poor local minima.
  • Theoretical Backing: The paper extends the subset-sum approximation theory to prove that SLTs still exist with high probability even when a significant portion of the network is randomly locked or pruned.

Conclusion

Partial freezing effectively compresses strong lottery tickets while maintaining or even improving accuracy by avoiding the sparsity trap. While highly effective for CNNs and GNNs, performance on Vision Transformers (DeiT) remains a challenge, suggesting that the SLT phenomenon in Transformers requires further study. Future work will explore hardware implementations to measure real-world energy and latency gains.

Summary updated

Abstract

Randomly initialized dense networks contain subnetworks that achieve high accuracy without weight learning--strong lottery tickets (SLTs). Recently, Gadhikar et al. (2023) demonstrated that SLTs could also be found within a randomly pruned source network. This phenomenon can be exploited to further compress the small memory size required by SLTs. However, their method is limited to SLTs that are even sparser than the source, leading to worse accuracy due to unintentionally high sparsity. This paper proposes a method for reducing the SLT memory size without restricting the sparsity of the SLTs that can be found. A random subset of the initial weights is frozen by either permanently pruning them or locking them as a fixed part of the SLT, resulting in a smaller model size. Experimental results show that Edge-Popup (Ramanujan et al., 2020; Sreenivasan et al., 2022) finds SLTs with better accuracy-to-model size trade-off within frozen networks than within dense or randomly pruned source networks. In particular, freezing $70\%$ of a ResNet on ImageNet provides $3.3 \times$ compression compared to the SLT found within a dense counterpart, raises accuracy by up to $14.12$ points compared to the SLT found within a randomly pruned counterpart, and offers a better accuracy-model size trade-off than both.
BibTeX
@article{otsuka2025partially,
  author = {Hikari Otsuka and Daiki Chijiwa and Ángel López García-Arias and Yasuyuki Okoshi and Kazushi Kawamura and Thiem Van Chu and Daichi Fujiki and Susumu Takeuchi and Masato Motomura},
  title = {{Partially Frozen Random Networks Contain Compact Strong Lottery Tickets}},
  journal = {Trans. Mach. Learn. Res.},
  year = {2025},
  url = {https://openreview.net/forum?id=3WEGJ349jV},
}
Figure