Quantization vs Pruning: Insights from the Strong Lottery Ticket Hypothesis

Aakash Kumar, Emanuele Natale · 2025

Read Quantization vs Pruning: Insights from the Strong Lottery Ticket Hypothesis by Aakash Kumar, Emanuele Natale (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-11020.txt.

Introduction

Aakash Kumar and Emanuele Natale compare two ways to shrink neural networks, quantization and pruning, in a 2025 theory paper. Quantization cuts the precision of each weight, while pruning cuts whole weights away. Old results showed that pruning a huge random network can carve out a sharp low-precision one. A theory line called the strong lottery ticket hypothesis grew from those results, but it spoke only to smooth, full-precision targets.

The pair extend the theory to networks that live on a finite grid of values. There, the carved network can match the target exactly, not just closely. They also prove the best possible bound on how much bigger the starting network must be, as a function of the target's precision. The math leans on classic results about splitting number sets.

Catalog record

CREATORAakash Kumar, Emanuele Natale
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-11020

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantization vs Pruning: Insights from the Strong Lottery Ticket Hypothesis Aakash Kumar, Emanuele Natale Abstract Quantization is an essential technique for making neural networks more efficient, yet our theoretical understanding of it remains limited. Previous works demonstrated that extremely low-precision networks, such as binary networks, can be constructed by pruning large, randomly-initialized networks, and showed that the ratio between the size of the original and the pruned networks is at most polylogarithmic. The specific pruning method they employed inspired a line of theoretical work known as the Strong Lottery Ticket Hypothesis (SLTH), which leverages insights from the Random Subset Sum Problem. However, these results primarily address the continuous setting and cannot be applied to extend SLTH results to the quantized setting. In this work, we build on foundational results by Borgs et al. on the Number Partitioning Problem to derive new theoretical results for the Random Subset Sum Problem in a quantized setting. Using these results, we then extend the SLTH framework to finite-precision networks. While prior work on SLTH showed that pruning allows approximation of a certain class of neural networks, we demonstrate that, in the quantized setting, the analogous class of target discrete neural networks can be represented exactly, and we prove optimal bounds on the necessary overparameterization of the initial network as a function of the precision of the target network. 1 Introduction Deep neural networks (DNNs) have become ubiquitous in modern machine-learning systems, yet their ever - growing size quickly collides with the energy, memory, and latency constraints of real - world hardware. Quantization —representing weights with a small number of bits—is arguably the most hardware - friendly compression technique, and recent empirical work shows that aggressive quantization can preserve accuracy even down to the few bits regime. Unfortunately, our theoretical understanding of why and when such extreme precision reduction is possible still lags far behind in practice. An interesting step in this direction was the Multi - prize Lottery Ticket Hypothesis (MPLTH) put forward by Diffenderfer and Kailkhura 2021 . They empirically demonstrated that a sufficiently large, randomly initialized network contains sparse binary subnetworks that match the performance of a target network with real - valued weights. They also provided theoretical guarantees regarding the existence of such highly quantized networks, showing that, with respect to the target network, the initial random network need only be larger by a polynomial factor . Sreenivasan et al. 2022 subsequently improved this bound, by showing that a polylogarithmic factor is sufficient (See Section 2 ). These works fall within the research topic known as the Strong Lottery Ticket Hypothesis (SLTH), which states that sufficiently-large randomly initialized neural networks contain subnetworks, called lottery tickets , that perform well on a given task, without requiring weight adjustments. The main theoretical question, therefore, is: how large should the initial network be to ensure it contains a lottery ticket capable of approximating a given family of target neural networks? Research on the SLTH, however, has mainly focused on investigating pruning in the continuous-weight (i.e., not quantized) setting, drawing on results for the Random Subset Sum Problem (RSSP) ( Lueker 1998 ) to show that over - parameterized networks can be pruned to approximate any target network without further training ( Orseau et al. 2020 ; Pensia et al. 2020 ; Burkholz 2022a ) (for additional context on this body of literature, we kindly refer the reader to the Related Work in Section 2 ). However, the analytic RSSP results used for SLTH rely heavily on real - valued weights and therefore do not extend to the finite - precision regime considered in the MPLTH. This gap left open a fundamental question: What is the over - parameterization needed to obtain quantized strong lottery tickets? Our contributions. We address the aforementioned gap by revisiting the classic Number Partitioning Problem (NPP), which is closely related to the RSSP. Building on the seminal results of Borgs et al. 2001 concerning the phase transition of NPP, we derive new, sharp bounds for the discrete RSSP . These bounds are precise enough to adapt the SLTH proof strategy to the finite precision setting and, in doing so, establish optimal bounds for the MPLTH. Crucially, our results account for arbitrary quantization in both the initial and target networks, and demonstrate that the lottery ticket can represent the target network exactly . In contrast, prior work limited the initial network to binary weights and assumed continuous weights for the larger (target) network ( Diffenderfer and Kailkhura 2021 ; Sreenivasan et al. 2022 ) , requiring a cubic overparameterization relative to the lower bound and additional dependencies on network parameters absent in our bound. Concretely, let \delta_{t} denote the precision (i.e., quantization level) of a target network N_{t} , \delta_{\text{in}} the precision of a randomly initialized larger network N_{\text{in}} , and \delta any parameter satisfying \delta_{t}\geq\delta^{2}\geq\delta_{\text{in}}^{2} . Denote by d and \ell the width and depth of the target network, respectively. Our results can be summarized by the following simplified, informal theorem (refer to the formal statements for full generality). Theorem (Informal version of Theorems 1 , 2 , and 3 ) . With high probability 1 1 1 As customary in the literature on randomized algorithms, with the expression with high probability we refer to a probability of failure which scales as the inverse of a polynomial in the parameter of interest (the number of precision bits \log 1/\delta) in our case). , a depth - 2\ell network N_{\text{in}} of width \mathcal{O}\bigl(d\log(1/\delta)\bigr) can be quantized to precision \delta and pruned to become functionally equivalent to any \delta_{t} -quantized target network N_{t} with layers of width at most d (Theorem 1 ). This result is optimal, as no two - layer network of precision \delta with fewer than \Omega\bigl(d\log(1/\delta)\bigr) parameters can be pruned to represent \delta -quantized neural networks of width d (Theorem 3 ). Furthermore, the depth of N_{\text{in}} can be reduced to (\ell+1) at the cost of an additional \log(1/\delta) factor in its width (Theorem 2 ). These are the first theoretical results that (i) characterize the precise interplay between weight precision and over - parameterization, and (ii) certify that pruning can yield exact , not just approximate, quantized subnetworks. Besides contributing to the theory of network compression, our analysis showcases the versatility of classical combinatorial insights—such as the theory of NPP—in deep - learning theory. Paper organization. In Section 2 , we review prior work on SLTH and quantization. In Section 3 , we prove a new quantized version of the RSSP, after first recalling classical results on RNPP in subsection 3.1 . Our new theorems on the quantized SLTH are proved in Sections 4 , after recalling necessary notation and definitions in subsection 4.1 . Finally, in Section 5 , we discuss the conclusion of our work and future directions. 2 Related Work Strong Lottery Ticket Hypothesis. In 2018, Frankle and Carbin 2019 proposed the Lottery Ticket Hypothesis, which states that every dense network contains a sparse subnetwork that can be trained from scratch, and performs equally well as the dense network. Rather surprisingly, Zhou et al. 2019 , Ramanujan et al. 2020 and Wang et al. 2019 empirically showed that it is possible to efficiently find

Read the complete text