Towards strong pruning for lottery tickets with non-zero biases

Jonas Fischer, Rebekka BurkholzarXiv 2021 · OpenReview

Introduction

The Lottery Ticket Hypothesis (LTH) has revolutionized our understanding of neural network overparameterization, suggesting that large networks contain small "winning tickets" capable of matching full-network performance when trained. The Strong Lottery Ticket Hypothesis (SLTH) takes this further, proposing that these tickets exist at initialization and can be discovered solely through pruning, without any weight updates.

However, a significant gap exists in the current SLTH literature: the omission of biases. While mathematically convenient for proofs, zero-bias networks are fundamentally limited. This paper addresses this gap by providing the first formal existence proofs and practical initialization schemes for strong lottery tickets with non-zero biases.

The Necessity of Non-Zero Biases

The authors identify a critical theoretical flaw in previous SLTH research. ReLU networks without biases are not universal function approximators. For instance, a univariate ReLU network without biases is restricted to representing functions that are factorizations of two linear pieces meeting at the origin. Such networks cannot represent a simple constant offset, such as $f(x) = 0.5$, across a domain.

Comparison of function approximation with zero vs. non-zero bias.

As shown in Figure 1, zero-bias networks (dotted orange) fail to capture the behavior of target functions that do not pass through the origin, whereas non-zero bias networks (dashed purple) can approximate them with high fidelity. This realization is crucial because successful deep learning models in practice rely heavily on non-zero biases to achieve their expressive power.

Theoretical Extension and Methodology

To bridge the gap, the authors extend existing existence proofs to include non-zero biases. They treat the bias as an additional weight connected to a constant input of 1. This allows them to adapt "subset sum" approximation techniques to show that a sufficiently large random network contains a "strong" ticket with high probability.

The process of finding a strong lottery ticket from a mother network to approximate a target.

The framework involves three main components:

  1. Existence Proofs: Formally proving that SLTs with biases are universal approximators.
  2. Initialization Schemes: Generalizing standard schemes like He and Glorot, and introducing a "looks-linear" orthogonal initialization. The latter ensures stable signal propagation through deep networks before pruning.
  3. Edge-Popup-Scaled Algorithm: An improvement over the standard edge-popup algorithm. It introduces a learnable scaling factor ($\lambda$) and a sparsity annealing schedule to handle the broken "homogeneity" in non-zero bias networks, where weights and biases must be scaled together.

Experimental Validation

The proposed methods were evaluated across several benchmarks:

  • Synthetic Tasks: On the "Shifted ReLU" regression task, non-zero bias initialization reduced error by orders of magnitude compared to zero-bias counterparts. On the "Onion Slice" classification task, the edge-popup-scaled algorithm improved accuracy by 10% at extreme sparsities.
  • MNIST: The authors successfully "constructed" a ticket based on their mathematical proof that achieved ~98% accuracy without any weight training, validating the theoretical existence of these tickets.
  • CIFAR-10: While the benefits were less pronounced on complex image data, the authors attribute this to the "parameter-inefficiency" of current pruning algorithms rather than a lack of theoretical potential.

Conclusion

By incorporating non-zero biases, this work elevates the Strong Lottery Ticket Hypothesis from a theoretical curiosity to a framework capable of universal approximation. While finding these tickets in high-dimensional spaces remains a challenge for current algorithms, this paper provides the necessary theoretical foundation and initialization strategies to move toward pruning-only alternatives to traditional gradient-based training.

Summary updated

BibTeX
@misc{fischer2021towards,
  author = {Jonas Fischer and Rebekka Burkholz},
  title = {{Towards strong pruning for lottery tickets with non-zero biases}},
  year = {2021},
  url = {https://openreview.net/forum?id=diRlP4NzeBu},
}
Figure