winning lottery tickets in neural networks via a quantum-inspired classical algo¶

会议: NeurIPS 2026
arXiv: 2605.13979
领域: 模型压缩
关键词: 彩票假设, 模型剪枝, 脊波变换, 量子启发经典算法, 拒绝采样

一句话总结¶

针对浅层神经网络中基于脊波变换寻找彩票中奖子网络的采样问题，本文利用离散脊波变换的正距映射特性将高维稠密矩阵求逆降维到经验数据支撑集上，提出了无需量子硬件即可实现多项式时间采样与子网络抽取的经典算法。

研究背景与动机¶

深度神经网络虽然在各类任务中取得了卓越的预测性能，但庞大的参数量导致训练和部署成本极其高昂。寻找稀疏且可独立训练的子网络一直是模型压缩领域的核心命题，以彩票假设（Lottery Ticket Hypothesis）为代表的研究表明随机初始化的大网络中存在可匹配稠密模型精度的稀疏中奖结构。然而，传统的彩票识别路径多依赖于训练后剪枝、初始化时敏感度剪枝或迭代硬掩码搜索，其实质是在庞大的参数或连接空间中直接操作原始稠密网络进行高开销优化搜索。

借助单隐层神经网络在过参数化极限下的积分表示理论，脊波变换（Ridgelet Transform）提供了一条完全不同的重要性采样路径：将神经元视为基函数，其正则化脊波系数大小直接刻画了隐藏节点对逼近目标函数的重要程度。此前 ICML 2023 的代表性工作 Yamasaki 等人提出了量子脊波变换算法，利用量子奇异值变换（QSVT）实现了在数据维度 $D$ 上的多项式甚至线性复杂度采样；但在经典计算中，由于正则化参数矩阵大小高达 $\exp[O(D)] \times \exp[O(D)]$ 且既不稀疏也不满足常规低秩假设，朴素经典求解不得不面临指数级计算开销，而容错通用量子硬件在近期仍然难以落地。

这便引出了理论机器学习与量子计算交叉领域的核心矛盾：利用脊波变换抽取稀疏彩票子网络的指数级加速，究竟本质上依赖量子相干性，还是可以通过设计特定代数结构的经典算法实现去量子化（Dequantization）？本文切入角度正是深入挖掘离散脊波变换本身的等距映射与正交分解性质。核心 idea：利用离散脊波变换算子 $\bm{R}$ 的正距性消除正交补空间上的稠密求逆，将隐藏节点参数空间的高维矩阵逆降维为数据域上的对角重加权，并结合二叉树采样结构设计高维拒绝采样器，实现全多项式时间经典彩票抽取。

方法详解¶

整体框架¶

本文的目标是在离散有限域 $\mathbb{Z}_P^D$ 上从正则化脊波估计诱导的优化概率分布 $p_{\lambda, \Delta}^*(\bm{a}, b)$ 中抽取隐藏节点参数 $(\bm{a}, b)$。该分布倾向于给高权重的脊波基赋予大采样概率，从而用少量抽取的隐藏节点构成稀疏单隐层网络。传统直接求解需在高维隐藏参数空间中计算稠密矩阵逆 $(\bm{R}\hat{\bm{P}}_{\text{data}}\bm{R}^\top + \lambda P^{-D}\bm{I})^{-1}$，维度为 $P^{D+1} \times P^{D+1}$，带来维数灾难。

本文的整体算法流程主要分为三个阶段：首先在经验数据域（样本量 $K \le M$）上构建稀疏向量 $|\phi\rangle$，避免任何参数空间的矩阵求逆；其次利用二叉树数据结构实现对提议分布 $q(\bm{a}, b)$ 的高效快速采样；最后通过柯西-施瓦茨不等式推导的接收概率执行拒绝采样，并在有限迭代内精确返回服从优化分布的神经元参数 $(\bm{a}, b)$。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入数据集 {(x_m, y_m)}<br/>及正则化超参 λ, Δ"] --> B["算子降维与数据域重加权<br/>消除正交补稠密逆算子"]
    B --> C["量子启发二叉树提议采样<br/>先抽样本点再抽参数 a 与偏置"]
    C --> D["柯西-施瓦茨拒绝采样判定<br/>计算接收概率并判定是否接受"]
    D -->|接受样本| E["输出隐藏节点 (a, b)<br/>拟合输出权重构建稀疏网络"]
    D -->|达到最大迭代上限未命中| F["均匀回退采样 (a, b)"]

关键设计¶

1. 算子降维与数据域重加权：绕过高维参数空间的稠密求逆

针对高维隐藏参数空间 $P^{D+1} \times P^{D+1}$ 矩阵求逆的指数瓶颈，本文关键观察在于离散脊波变换算子 $\bm{R}: \mathbb{R}^{P^D} \to \mathbb{R}^{P^{D+1}}$ 满足正距性质 $\bm{R}^\top\bm{R} = \bm{I}_{P^D}$，其值域与正交补空间可以做正交投影分解。通过将参数空间的稠密正则化逆算子精确展开： $$(\bm{R}\hat{\bm{P}}_{\text{data}}\bm{R}^\top + \lambda P^{-D}\bm{I})^{-1} = \bm{R}(\hat{\bm{P}}_{\text{data}} + \lambda P^{-D}\bm{I})^{-1}\bm{R}^\top + \frac{1}{\lambda P^{-D}}(\bm{I} - \bm{R}\bm{R}^\top)$$ 由于待作用的右侧向量恰好属于 $\bm{R}$ 的值域空间 $\bm{R}|\psi_{\text{in}}\rangle$，位于正交补上的第二项完全湮灭，即 $(\bm{I} - \bm{R}\bm{R}^\top)\bm{R}|\psi_{\text{in}}\rangle = \bm{0}$。于是，原本极其复杂的求逆被精确转化为数据域上的逐点对角除法 $|\phi\rangle = P^{-D/2}(\hat{\bm{P}}_{\text{data}} + \lambda P^{-D}\bm{I})^{-1}\hat{\bm{P}}_{\text{data}}|f\rangle$。由于经验分布只在 $K \le M$ 个离散样本点上有非零测度，计算复杂度直接从指数级 $O(P^{3D})$ 骤降到多项式级 $O(M)$，不仅去除了经典计算的指数瓶颈，也将量子算法中对 $1/\lambda$ 的依赖彻底消除。

2. 量子启发二叉树提议采样：构造覆盖高权重基的高效提议分布

即使能够逐点计算任意单个隐藏节点 $(\bm{a}, b)$ 的非归一化打分，整个参数空间的归一化常数 $Z$ 依然包含 $P^{D+1}$ 项求和，且高重要性节点在空间中高度稀疏集中，常规均匀提议的拒绝采样接收率极低。针对这一痛点，本文利用量子启发算法中基于二叉树范数的 SQ（Sampling and Query）数据结构，预先用 $\tilde{O}(M)$ 时间对数据域稀疏向量 $|\phi\rangle$ 建立分层索引。算法构造的提议分布满足： $$q(\bm{a}, b) = \frac{1}{\gamma} \sum_{\bm{x} \in \mathcal{X}_{\text{data}}} \left| P^{-D/2} \frac{\hat{p}_{\text{data}}(\bm{x}) f(\bm{x})}{\lambda P^{-D} + \hat{p}_{\text{data}}(\bm{x})} \right|^2 \left| P^{-D/2} r((\bm{a}^\top\bm{x} - b) \bmod P) \right|^2$$ 提议采样过程极其优雅高效：首先通过二叉树以正比于分量模平方的概率抽取一个输入样本点 $\bm{x}$；然后均匀抽取方向向量 $\bm{a} \in \mathbb{Z}_P^D$ 并依据脊波函数强度抽取标量 $t$；最后令标量偏置 $b = \bm{a}^\top\bm{x} - t \pmod P$。整个提议过程耗时仅为 $O(D \log P + \text{polylog}(M))$，且能够将提议质量精准锚定在对经验样本有强贡献的脊波参数上。

3. 柯西-施瓦茨拒绝采样判定：以可控偏差界实现多项式总耗时

获得提议样本 $(\bm{a}, b)$ 后，算法依据目标分布与提议分布的比值进行接收判定。利用柯西-施瓦茨不等式，单次提议样本被证明可以严格以上界为 1 的概率被接收： $$\text{Acc}(\bm{a}, b) = \frac{\Delta}{\Delta + s(\bm{a}, b)} \cdot \frac{s(\bm{a}, b)}{K \gamma q(\bm{a}, b)} \le 1$$ 其中 $s(\bm{a}, b) = |P^{-D/2}w_\lambda^*(\bm{a}, b)|^2$ 是目标优化分布在隐藏节点处的未归一化分子。条件接收后的边缘分布与目标优化分布 $p_{\lambda, \Delta}^*(\bm{a}, b)$ 严格一致。更重要的是，每次抽样的单步接收概率下界被严格证明不低于 $\frac{1}{K}\frac{\Delta}{\Delta + \gamma}$。因此，通过设定最多迭代循环次数 $I = \lceil K(1 + \gamma/\Delta) \ln(1/\delta) \rceil$，可以将总失败概率控制在精度阈值 $\delta$ 之内；即便极罕见情况下所有尝试均未命中，算法回退至均匀采样，整体全变差距离 $d_{\text{TV}}$ 依然严格被 $\delta$ 控制，保证了最终采样的无偏性与多项式时间上界。

损失函数 / 训练策略¶

抽取得到 $N$ 个隐藏节点后，算法进行去重得到 $N_{\text{eff}} \le \min(N, P^{D+1})$ 个互异基函数，构建样本矩阵 $\Phi_{S_N} \in \mathbb{R}^{K \times N_{\text{eff}}}$。最后利用岭回归（Ridge Regression）在经验样本上求解输出层权重 $\hat{\theta}_{S_N}$： $$\hat{\theta}_{S_N} \in \arg\min_{\theta \in \mathbb{R}^{N_{\text{eff}}}} \left\| \hat{\bm{P}}_{\text{supp}}^{1/2} (\Phi_{S_N}\theta - \bm{f}_{\text{supp}}) \right\|_2^2 + \lambda P^{-D} \|\theta\|_2^2$$ 这一步可直接通过标准 NumPy 线性代数正规方程快速求解，最终组装成极小规模的高拟合精度单隐层稀疏网络。

实验关键数据¶

主实验¶

实验在有限域 $\mathbb{Z}_P^D$ 上合成正弦目标函数，输入维度 $D \in \{1, \dots, 6\}$，$P=7$，样本量 $M=50D$，对比抽取不同隐藏节点数 $N \in [8, 4096]$ 时的经验拟合风险（Empirical Risk）。

算法 / 采样方法	$D$ 范围	运行时间理论复杂度	经验拟合风险表现	硬件需求
朴素经典精确采样	$D \in [1, 8]$ ($P=3$)	$\exp[O(D)] = O(P^{3D})$	极佳基准（精确服从优化分布）	传统 CPU / 大内存
本文经典采样器 ($\delta=0.1$)	$D \in [1, 128]$	$O(\text{poly}(D)) = \tilde{O}(DM^2 \frac{\gamma}{\Delta} \log\frac{1}{\delta})$	与精确采样高度重合，贴合理论下界	常规单机 CPU
本文经典采样器 ($\delta=0.7$)	$D \in [1, 128]$	$\tilde{O}(DM^2 \frac{\gamma}{\Delta} \log\frac{1}{\delta})$	稍逊于 $\delta=0.1$，但仍大幅优于均匀采样	常规单机 CPU
均匀随机采样 (无优化)	任意 $D$	$O(ND)$	在中等 $N$ 下显著劣于优化采样，收敛极慢	常规 CPU
原前沿量子采样 (Yamasaki 2023)	任意 $D$	$\tilde{O}(D \frac{1}{\lambda} \text{polylog}(M))$	接近理论优化分布	容错量子硬件 (FTQC)

消融实验¶

对输入维度 $D$ 增长下的端到端运行时间缩放特性进行严谨回归分析（$P=3, M=50D$）：

配置 / 采样策略	维度范围 $D$	拟合运行时间缩放曲线	复杂度定性	说明
朴素求解器 (解高维方程组)	$D \in [1, 8]$	$\text{Time} \propto P^{2.85 D}$	指数级增长	当 $D \ge 6$ 耗时急剧爆炸，维度 8 已达硬件内存瓶颈
本文去量子化采样器	$D \in [1, 128]$	$\text{Time} \propto D^{2.55}$	严格多项式级	紧密符合理论预期的 $DM^2 = O(D^3)$ 上界，高效扩展至超大维度
改进后量子算法 (理论推导)	理论分析	$O(D \frac{\gamma}{\Delta} \text{polylog} \frac{MP}{\delta})$	对数多项式	依托本文算子分解，成功消除了对 $1/\lambda$ 的依赖项

关键发现¶

去量子化保真度高：在所有测试维度上，本文提出的经典采样器在拟合风险曲线上紧紧跟随精确优化分布，验证了拒绝采样成功保留了优化分布针对高贡献隐藏神经元的重要偏置；相较之下，未经优化的均匀随机神经元采样需要成倍增加节点数 $N$ 才能达到同等拟合效果。
算子维数灾难被彻底化解：实测运行时间拟合指数由 $P^{2.85D}$ 锐减至 $D^{2.55}$，从数值计算上无可辩驳地支撑了定理 2 的理论多项式复杂度边界，使得原本无法在经典计算机上完成的脊波彩票神经元抽取能够在单机 CPU 上轻松完成。

亮点与洞察¶

代数结构驱动的去量子化：以往量子启发经典算法多局限于低秩或稀疏假设，本文巧妙挖掘了离散脊波变换算子 $\bm{R}$ 本身的正距性质与投影互补性，成功将满秩稠密算子的高维逆降维到低维数据域。
双重贡献的理论突破：本文推导的算子分解不仅为经典计算带来了多项式时间采样器，反向迁移至量子机器学习流程中，也省去了原本必须依赖 QSVT 实现的正则化逆矩阵编码，消除了前作对正则化系数 $1/\lambda$ 的反比依赖。

局限与展望¶

模型结构局限于单隐层浅层网络：理论推导依赖于单隐层网络与积分脊波变换的精准对偶表示，难以直接拓展到多层非线性深度神经网络（如深层 MLP 或 ResNet）的彩票识别。
数据域假设基于离散有限域：当前证明与实验均在离散有限域 $\mathbb{Z}_P^D$ 上建立，如何将其平滑拓展到连续实数空间 $\mathbb{R}^D$ 且保持有限样本多项式复杂度依然是开放问题。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 巧妙利用脊波变换的正距性实现满秩高维矩阵逆向分解，打破了常规量子启发算法需要低秩的限制。
实验充分度: ⭐⭐⭐⭐ 对比了多维度下的拟合风险与运行时间 Scaling 曲线，但实验仅在合成正弦函数与浅层离散网络上进行。
写作质量: ⭐⭐⭐⭐⭐ 数学证明严密自洽，核心设计直观清晰。
价值: ⭐⭐⭐⭐ 为彩票假设及量子机器学习的经典算法边界判定提供了坚实的理论基准。

算法 / 采样方法	\(D\) 范围	运行时间理论复杂度	经验拟合风险表现	硬件需求
朴素经典精确采样	\(D \in [1, 8]\) (\(P=3\))	\(\exp[O(D)] = O(P^{3D})\)	极佳基准（精确服从优化分布）	传统 CPU / 大内存
本文经典采样器 (\(\delta=0.1\))	\(D \in [1, 128]\)	\(O(\text{poly}(D)) = \tilde{O}(DM^2 \frac{\gamma}{\Delta} \log\frac{1}{\delta})\)	与精确采样高度重合，贴合理论下界	常规单机 CPU
本文经典采样器 (\(\delta=0.7\))	\(D \in [1, 128]\)	\(\tilde{O}(DM^2 \frac{\gamma}{\Delta} \log\frac{1}{\delta})\)	稍逊于 \(\delta=0.1\)，但仍大幅优于均匀采样	常规单机 CPU
均匀随机采样 (无优化)	任意 \(D\)	\(O(ND)\)	在中等 \(N\) 下显著劣于优化采样，收敛极慢	常规 CPU
原前沿量子采样 (Yamasaki 2023)	任意 \(D\)	\(\tilde{O}(D \frac{1}{\lambda} \text{polylog}(M))\)	接近理论优化分布	容错量子硬件 (FTQC)

配置 / 采样策略	维度范围 \(D\)	拟合运行时间缩放曲线	复杂度定性	说明
朴素求解器 (解高维方程组)	\(D \in [1, 8]\)	\(\text{Time} \propto P^{2.85 D}\)	指数级增长	当 \(D \ge 6\) 耗时急剧爆炸，维度 8 已达硬件内存瓶颈
本文去量子化采样器	\(D \in [1, 128]\)	\(\text{Time} \propto D^{2.55}\)	严格多项式级	紧密符合理论预期的 \(DM^2 = O(D^3)\) 上界，高效扩展至超大维度
改进后量子算法 (理论推导)	理论分析	\(O(D \frac{\gamma}{\Delta} \text{polylog} \frac{MP}{\delta})\)	对数多项式	依托本文算子分解，成功消除了对 \(1/\lambda\) 的依赖项