A Unified Framework for Quantized and Continuous Strong Lottery Tickets

• URL: http://arxiv.org/abs/2607.03860v1
• Date: Sat, 04 Jul 2026 13:00:39 GMT
• Title: A Unified Framework for Quantized and Continuous Strong Lottery Tickets
• Abstract summary: We provide an analysis of the Random Subset Sum Problem (RSSP) in the discrete setting, and use it to derive tight SLTH guarantees in the quantized case.<n>Our analysis obtains tight bounds on the failure probability of finding a strong lottery ticket in the quantized regime, providing an exponential improvement over previous results.
• Score: 3.772827533440353
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Strong Lottery Ticket Hypothesis (SLTH) asserts that sufficiently overparameterized, randomly initialized neural networks contain sparse subnetworks that, even without any training, can match the performance of a small trained network on a given dataset. A key mathematical tool in the theoretical study of SLTH has been the Random Subset Sum Problem (RSSP). The SLTH has recently been extended to the quantized setting, where the network weights are sampled from a discrete set rather than from a continuous interval. These new results are however far from those in arbitrary-precision setting in several ways. In this work, we provide an analysis of the RSSP in the discrete setting, and use it to derive tight SLTH guarantees in the quantized case. Our analysis obtain tight bounds on the failure probability of finding a strong lottery ticket in the quantized regime, providing an exponential improvement over previous results. Most importantly, it unifies the literature by showing that both approximate representations in the continuous setting and exact representations in quantized settings naturally emerge as limiting cases of our results. This perspective not only sharpens existing bounds but also provides a cohesive framework that simultaneously handles approximation and rounding errors.

Related papers

• Sharp Convergence Rates for Masked Diffusion Models [53.117058231393834]
  We develop a total-variation based analysis for the Euler method that overcomes limitations.<n>Our results relax assumptions on score estimation, improve parameter dependencies, and establish convergence guarantees.<n>Overall, our analysis introduces a direct TV-based error decomposition along the CTMC trajectory and a decoupling-based path-wise analysis for FHS.
  arXiv  Detail & Related papers  (2026-02-26T00:47:51Z)
• Quantization vs Pruning: Insights from the Strong Lottery Ticket Hypothesis [5.494111035517599]
  Quantization is an essential technique for making neural networks more efficient, yet our theoretical understanding of it remains limited.<n>Previous works demonstrated that extremely low-precision networks, such as binary networks, can be constructed by pruning large, randomly- approximationd networks.<n>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.
  arXiv  Detail & Related papers  (2025-08-14T18:51:34Z)
• On the Hölder Stability of Multiset and Graph Neural Networks [3.396731589928944]
  We propose a novel pair-wise separation quality analysis framework based on an adaptation of Lipschitz and Holder stability to parametric functions.<n>We prove that common sum-based models are lower-Holder in expectation, with an exponent that decays rapidly with the network's depth.<n>We show these MPNNs can easily classify our adversarial examples, and compare favorably with standard MPNNs on standard graph learning tasks.
  arXiv  Detail & Related papers  (2024-06-11T06:28:21Z)
• Polynomially Over-Parameterized Convolutional Neural Networks Contain Structured Strong Winning Lottery Tickets [4.020829863982153]
  We prove the existence of structured Neuralworks that can approximate any sufficiently smaller network. This result provides the first sub-exponential bound around the Strong Lottery Ticket Hypothesis.
  arXiv  Detail & Related papers  (2023-11-16T12:38:45Z)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  We propose a straightforward and efficient Shapley estimator, SimSHAP, by eliminating redundant techniques. In our analysis of existing approaches, we observe that estimators can be unified as a linear transformation of randomly summed values from feature subsets. Our experiments validate the effectiveness of our SimSHAP, which significantly accelerates the computation of accurate Shapley values.
  arXiv  Detail & Related papers  (2023-11-02T06:09:24Z)
• Collapsed Inference for Bayesian Deep Learning [36.1725075097107]
  We introduce a novel collapsed inference scheme that performs Bayesian model averaging using collapsed samples. A collapsed sample represents uncountably many models drawn from the approximate posterior. Our proposed use of collapsed samples achieves a balance between scalability and accuracy.
  arXiv  Detail & Related papers  (2023-06-16T08:34:42Z)
• Dual Lottery Ticket Hypothesis [71.95937879869334]
  Lottery Ticket Hypothesis (LTH) provides a novel view to investigate sparse network training and maintain its capacity. In this work, we regard the winning ticket from LTH as the subnetwork which is in trainable condition and its performance as our benchmark. We propose a simple sparse network training strategy, Random Sparse Network Transformation (RST), to substantiate our DLTH.
  arXiv  Detail & Related papers  (2022-03-08T18:06:26Z)
• Cluster-Promoting Quantization with Bit-Drop for Minimizing Network Quantization Loss [61.26793005355441]
  Cluster-Promoting Quantization (CPQ) finds the optimal quantization grids for neural networks. DropBits is a new bit-drop technique that revises the standard dropout regularization to randomly drop bits instead of neurons. We experimentally validate our method on various benchmark datasets and network architectures.
  arXiv  Detail & Related papers  (2021-09-05T15:15:07Z)
• Multi-Scale Positive Sample Refinement for Few-Shot Object Detection [61.60255654558682]
  Few-shot object detection (FSOD) helps detectors adapt to unseen classes with few training instances. We propose a Multi-scale Positive Sample Refinement (MPSR) approach to enrich object scales in FSOD. MPSR generates multi-scale positive samples as object pyramids and refines the prediction at various scales.
  arXiv  Detail & Related papers  (2020-07-18T09:48:29Z)
• Proving the Lottery Ticket Hypothesis: Pruning is All You Need [56.25432563818297]
  The lottery ticket hypothesis states that a randomly-d network contains a small subnetwork such that, when trained in isolation, can compete with the performance of the original network. We prove an even stronger hypothesis, showing that for every bounded distribution and every target network with bounded weights, a sufficiently over- parameterized neural network with random weights contains a subnetwork with roughly the same accuracy as the target network, without any further training.
  arXiv  Detail & Related papers  (2020-02-03T07:23:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.