Technical Summary: A Unified Framework for Quantized and Continuous Strong Lottery Tickets

Problem Statement

The Strong Lottery Ticket Hypothesis (SLTH) posits that sufficiently overparameterized, randomly initialized neural networks contain sparse subnetworks capable of matching the performance of a smaller trained network without any weight updates. While the theoretical foundations of SLTH rely heavily on the Random Subset Sum Problem (RSSP), existing literature has largely been confined to the continuous setting (arbitrary-precision weights).

Recent extensions to the quantized setting, where weights are sampled from discrete sets, have faced significant limitations. Prior works in this domain (e.g., Diffenderfer and Kailkhura [2021], Sreenivasan et al. [2022], Kumar and Natale [2025]) either restricted target networks to continuous weights while approximating with binary networks, or provided guarantees for exact representations in quantized settings with only inverse-polynomial decay in failure probability. Furthermore, these approaches treated approximate representations (continuous) and exact representations (quantized) as disjoint lines of inquiry, lacking a unified theoretical framework that accounts for both rounding and approximation errors simultaneously.

Methodology

The authors address these gaps by developing a rigorous analysis of the RSSP in the discrete setting and applying it to the quantized SLTH.

1. Discrete Random Subset Sum Problem (RSSP)

The core mathematical contribution is a new analysis of the discrete RSSP. The authors define the problem where random variables $X_1, \dots, X_n$ are sampled uniformly from a discrete set $\{-M, \dots, M\}$, and the goal is to find a subset summing to a target $z$ within a tolerance $\Delta$.

• Recurrence Relation: The analysis utilizes a recurrence relation for the indicator function $f_t(z)$, representing whether a target $z$ is $\Delta$-approximated at time $t$.
• Volume Growth Analysis: The authors track the growth of the "volume" $v_t$, defined as the number of distinct values in the range $\{-M, \dots, M\}$ that can be $\Delta$-approximated. They prove that $v_t$ grows in two distinct phases:
  1. Rapid Growth: $v_t$ quickly reaches $M+1$.
  2. Slow Growth: $v_t$ slowly rises to cover the entire range $2M+1$.
• Probabilistic Bounds: By analyzing these phases using martingale-like arguments and concentration inequalities (specifically leveraging reverse Markov's inequality and Hoeffding's bound), the authors derive tight bounds on the time $\tau$ required for the entire set to be $\Delta$-approximated.

2. Application to Quantized SLTH

The authors extend the results of Cunha et al. [2023] from the continuous RSSP to the discrete setting to establish SLTH guarantees for quantized networks.

• Network Construction: They consider a randomly initialized, overparameterized network $g$ with $2\ell$ layers, where weights are drawn uniformly from a discrete set $S_\delta$ (precision $\delta$).
• Pruning Strategy: The target is to prune $g$ to approximate a target $\ell$-layer network $f$ with weights in $S_\delta$. The pruning process is decomposed into solving a collection of independent RSSP instances for individual weights and neurons.
• Error Propagation: The proof follows the strategy of Pensia et al. [2020], lifting the approximation guarantee from a single weight to a neuron, then to a layer, and finally to the entire network. Crucially, the analysis tracks error propagation through nonlinearities (ReLU) and accounts for the accumulation of errors across layers.

Key Contributions

1. Tight Bounds for Discrete RSSP: The paper establishes new, sharp probabilistic bounds for the discrete RSSP. Unlike previous discrete analyses (e.g., Kumar and Natale [2025]) which yielded inverse-polynomial decay of failure probability, this work proves an exponentially small failure probability in the number of precision bits.
2. Unified Framework: The proposed framework unifies the literature by demonstrating that:
   • Approximate representations in the continuous setting (as in Malach et al. [2020], Pensia et al. [2020]) emerge as a limiting case when the precision $\delta \to 0$.
   • Exact representations in the quantized setting (as in Kumar and Natale [2025]) emerge as a limiting case when the tolerance $\Delta = 0$.
   • The framework simultaneously handles both rounding errors (due to quantization) and approximation errors (due to pruning).
3. Improved Overparameterization Guarantees: The authors derive that a depth-$2\ell$ random network with width $O(d \log(1/\delta))$ (where $d$ is the target width and $\delta$ is precision) can be pruned to $\epsilon$-approximate any target network of depth $\ell$ and width $d$.

Results

• Theoretical Guarantees: The main theorem (Theorem 3) states that with high probability ($1 - 4d^{2\ell} \exp(-C'n)$), a randomly initialized $2\ell$-layer quantized network can be pruned to approximate any target $\ell$-layer quantized network within error $\epsilon$. The failure probability decays exponentially with the overparameterization factor.
• Experimental Validation:
  • Subset Sum Experiments: The authors empirically validated the discrete RSSP theory, observing that the probability of solving an exact subset sum problem ($\Delta=0$) approaches 1 when the number of samples $n \gtrsim C \log(M)$, with $C \approx 1.5$.
  • Pruning Efficiency: In a practical test, the authors successfully identified a subnetwork approximating a ResNet-50 (25 million parameters, FP8 precision) by solving the required RSSP instances. This process took approximately 33 minutes on a single CPU without parallelization, demonstrating computational feasibility.

Significance and Claims

The paper claims to provide a fundamental step toward a cohesive theory of strong lottery tickets that bridges the gap between continuous and quantized settings. By unifying these previously separate lines of research, the work:

• Sharpens existing bounds: It improves the failure probability guarantee from inverse-polynomial to exponential decay in the quantized regime.
• Broadens practical relevance: It addresses the reality of finite-precision computation (quantization) while maintaining the theoretical rigor of approximation guarantees.
• Unifies the field: It shows that both approximate continuous representations and exact quantized representations are special cases of a single, more general framework.

The authors emphasize that their results support existing empirical observations regarding the existence of lottery tickets in quantized networks and provide a stronger theoretical foundation for the use of pruning in resource-constrained, finite-precision environments.