🤖 machine learning

A Unified Framework for Quantized and Continuous Strong Lottery Tickets

本文提出了一个针对强彩票假设（Strong Lottery Ticket Hypothesis）的统一框架，该框架通过在离散设置下分析随机子集和问题（Random Subset Sum Problem）来推导出紧致的量化保证，这些保证实现了对先前结果的指数级提升，并自然地将连续和量化机制涵盖为极限情况。

原作者： Aakash Kumar, Emanuele Natale

发布于 2026-07-07

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Aakash Kumar, Emanuele Natale

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

核心思想：在大海捞针（无需寻找）

想象你拥有一个巨大的、混乱的图书馆，里面装满了数百万本书（一个巨大的、随机构建的神经网络）。你正在寻找一个非常特定的、微小的故事（一个较小的、经过训练的神经网络），这个故事讲述了一个完美的故事。

强乐透门票假设 (Strong Lottery Ticket Hypothesis, SLTH) 是一个大胆的断言：它说如果你的图书馆足够大，那个完美的故事已经隐藏在那些随机的书籍之中了。你不需要去编写一个新故事或修改现有的故事（训练）；你只需要找到正确的页面并把其余的部分撕掉（剪枝/pruning）。

长期以来，科学家们已经证明，如果书籍是用无限精度编写的（比如使用一支可以写出任何灰色深浅度的笔），这种方法是行之有效的。但在现实世界中，计算机就像是只能以特定、离散步骤进行打印的打印机（比如只能打印黑、深灰、浅灰和白）。这被称为量化 (Quantization)。

这篇论文提出了一个问题：如果我们的书是按照这些有限的、块状的步骤打印出来的，那么“大海捞针”的技巧是否仍然奏效？

问题所在：“舍入”差距

之前的研究分为两个阵营：

连续派 (The Continuous Camp)： 证明了如果你拥有无限精度，你就能找到那根针，但其数学推导非常复杂，且没有考虑到现实世界计算机的限制。
量化派 (The Quantized Camp)： 试图为这种块状的、有限精度的计算机证明这一点，但其数学论证较弱。它暗示你可能需要一个极其巨大的图书馆才能找到那根针，而且失败的概率下降得非常缓慢（就像轮胎缓慢漏气一样）。

本文的作者想要在两个世界之间搭建一座桥梁。他们想要证明，即使在有限精度的条件下，你也能找到完美的子网络，并且找不到它的概率会下降得极其迅速（就像如果你没有足够的空气，轮胎会瞬间爆裂一样）。

工具：“子集和”游戏

为了解决这个问题，作者使用了一个经典的数学谜题——随机子集和问题 (Random Subset Sum Problem)。

类比：
想象你有一个装满随机砝码的袋子（有些重，有些轻）。你想挑选其中的几个放在秤上，以精确匹配一个特定的目标重量。

旧方法： 如果砝码是平滑且连续的，找到组合来达到目标很容易。
新挑战： 如果砝码是“块状”的（只允许特定的数值），这看起来要困难得多。你可能会认为你永远无法精确达到目标。

作者开发了一种新的、更精确的数学工具来分析这个“块状”游戏。他们证明了，即使使用这些“块状”砝码，只要数量足够多，你几乎肯定能找到一种组合来完美达到目标。

突破点：统一两个世界

这篇论文最大的成就在于展示了“平滑”世界和“块状”世界实际上是同一枚硬币的两面。

“魔数” (The Magic Number)： 作者找到了一个单一的公式，可以计算你的图书馆（网络）需要多大。
极限技巧：
- 如果你让“块状”变得无限小（变得平滑），他们的公式就会转化为关于连续网络的旧有著名结果。
- 如果你保持“块状”较大（量化状态），他们的公式就会转化为关于离散网络的结果。

这意味着他们不仅解决了一个新问题，还表明之前所有的解决方案都只是他们全新的统一理论中的特例。

结果：超强的保证

最令人兴奋的部分是概率。

旧结果： 在“块状”世界中，找不到针的概率下降得很慢（反多项式级）。这就像是在说：“如果你尝试 100 次，你可能会成功。”
新结果： 作者证明了失败的概率是指数级 (Exponentially) 下降的。这就像是在说：“如果你仅仅增加一点点图书馆的空间，失败的概率就会变得几乎为零。”

他们证明了，一个随机初始化的、块状的网络可以通过剪枝来完美模拟一个目标网络，并且数学保证了只要网络足够大，这种情况会以压倒性的确定性发生。

简要总结

目标： 证明巨大的、随机的、“块状”的计算机网络内部包含了它们自身的完美、更小的版本，并等待被切割出来。
方法： 他们专门针对“块状”数字解决了一个困难的数学谜题（子集和问题）。
发现： 他们创建了一个单一的框架，可以同时解释“平滑”网络和“块状”网络。
回报： 他们证明了寻找这些隐藏的网络不仅是可能的，而且是极有可能的（指数级高概率），从而弥补了以往研究中较弱的保证。

简而言之：他们证明了即使在现实世界计算机精度的限制下，“在大规模随机网络中寻找完美子网络”这一神奇现象是真实的、可靠的，并且在数学上是成立的。

技术摘要：量化与连续强乐透票的统一框架

问题陈述

强乐透票假设（Strong Lottery Ticket Hypothesis, SLTH）认为，具有足够过参数化的随机初始化神经网络包含稀疏子网络，这些子网络能够在无需任何权重更新的情况下，达到与较小训练网络相当的性能。虽然 SLTH 的理论基础在很大程度上依赖于随机子集和问题（Random Subset Sum Problem, RSSP），但现有文献主要局限于连续设置（任意精度权重）。

最近向量化设置（即权重从离散集合中采样）的扩展面临着显著的局限性。该领域的先前工作（例如 Diffenderfer 和 Kailkhura [2021], Sreenivasan 等人 [2022], Kumar 和 Natale [2025]）要么将目标网络限制为连续权重以近似二进制网络，要么仅能提供在量化设置下实现精确表示的保证，且其失败概率仅呈反多项式衰减。此外，这些方法将近似表示（连续）和精确表示（量化化）视为互不相干的研究方向，缺乏一个能够同时解释舍入误差和近似误差的统一理论框架。

方法论

作者通过对离散设置下的 RSSP 进行严谨分析，并将其应用于量化 SLTH，解决了这些差距。

1. 离散随机子集和问题 (RSSP)

核心数学贡献是对离散 RSSP 的新分析。作者定义了这样一个问题：随机变量 $X_1, \dots, X_n$ 从离散集合 $\{-M, \dots, M\}$ 中均匀采样，目标是找到一个总和在容差 $\Delta$ 范围内的子集，其和为目标值 $z$ 。

递推关系： 分析利用了指示函数 $f_t(z)$ 的递推关系，该函数表示在时间 $t$ 时，目标 $z$ 是否被 $\Delta$ -近似。
体积增长分析： 作者追踪了“体积” $v_t$ $v_{t}$ 的增长，其中 $v_t$ $v_{t}$ 定义为在范围 $\{-M, \dots, M\}$ ${- M, \dots, M}$ 内可以被 $\Delta$ $Δ$ -近似的截然不同的数值数量。他们证明了 $v_t$ $v_{t}$ 的增长分为两个截然不同的阶段：
1. 快速增长： $v_t$ 迅速达到 $M+1$ 。
2. 缓慢增长： $v_t$ 缓慢上升以覆盖整个范围 $2M+1$ 。
概率界限： 通过使用鞅类论证和集中不等式（具体而言，利用反向马尔可夫不等式和 Hoeffding 界）来分析这些阶段，作者推导出了完成整个集合 $\Delta$ -近似所需时间 $\tau$ 的紧凑界限。

2. 应用于量化 SLTH

作者将 Cunha 等人 [2023] 从连续 RSSP 到离散设置的扩展结果，用于建立量化网络的 SLTH 保证。

网络构建： 他们考虑了一个具有 $2\ell$ 层的随机初始化、过参数化网络 $g$ ，其权重均匀取自离散集 $S_\delta$ （精度为 $\delta$ ）。
剪枝策略： 目标是将 $g$ 剪枝以近似一个具有权重在 $S_\delta$ 中的目标 $\ell$ 层网络 $f$ 。剪枝过程被分解为解决针对单个权重和神经元的独立 RSSP 实例集合。
误差传播： 证明遵循了 Pensia 等人 [2020] 的策略，即将近似保证从单个权重提升到神经元，再到层，最后到整个网络。至关重要的是，分析追踪了通过非线性函数（ReLU）的误差传播，并考虑了跨层误差的累积。

核心贡献

离散 RSSP 的紧凑界限： 本文为离散 RSSP 建立了新的、尖锐的概率界限。不同于以往的离散分析（如 Kumar 和 Natale [2025]）产生的失败概率呈反多项式衰减，这项工作证明了在精度比特数方面具有指数级小的失败概率。
统一框架： 所提出的框架通过证明以下几点统一了文献：
- 连续设置中的近似表示（如 Malach 等人 [2020], Pensia 等人 [2020]）在精度 $\delta \to 0$ 时成为极限情况。
- 量化设置中的精确表示（如 Kumar 和 Natale [2025]）在 $\Delta = 0$ 时成为极限情况。
- 该框架同时处理了由于量化引起的舍入误差和由于剪枝引起的近似误差。
改进的过参数化保证： 作者得出，一个深度为 $2\ell$ 、宽度为 $O(d \log(1/\delta))$ （其中 $d$ 是目标宽度， $\delta$ 是精度）的随机网络，可以被剪枝以 $\epsilon$ -近似任何深度为 $\ell$ 、宽度为 $d$ 的目标网络。

结果

理论保证： 主定理（定理 3）指出，以高概率（ $1 - 4d^{2\ell} \exp(-C'n)$ ），一个随机初始化的 $2\ell$ 层量化网络可以被剪枝以在误差 $\epsilon$ 内近似任何目标 $\ell$ 层量化网络。失败概率随过参数化因子呈指数级衰减。
实验验证：
- 子集和实验： 作者通过经验验证了离散 RSSP 理论，观察到求解精确子集和问题（ $\Delta=0$ ）的概率在样本数 $n \gtrsim C \log(M)$ （其中 $C \approx 1.5$ ）时趋于 1。
- 剪枝效率： 在一项实际测试中，作者通过求解所需的 RSSP 实例，成功识别出了一个近似 ResNet-50（2500 万参数，FP8 精度）的子网络。该过程在单 CPU 上无需并行化仅耗时约 33 分钟，证明了计算上的可行性。

意义与主张

本文声称为连接连续与量化设置的强乐透票凝聚性理论提供了根本性的进展。通过统一这些先前独立的研究路线，该工作：

强化了现有界限： 它将量化机制下的失败概率保证从反多项式衰减提升到了指数级衰减。
扩大了实际相关性： 它在保持近似保证的理论严密性的同时，解决了有限精度计算（量化）的现实问题。
统一了领域： 它表明连续近似表示和精确量化表示都是同一个更通用框架下的特例。

作者强调，其结果支持了关于量化网络中存在乐透票的现有经验观察，并为在资源受限、有限精度的环境下使用剪枝提供了更强大的理论基础。