🤖 machine learning

Provable Quantization with Randomized Hadamard Transform

本文介绍了一种利用单次随机化哈达玛变换的抖动量化方法，该方法能够实现无偏的、可证明的均方误差界，其渐近性能与稠密随机旋转相当，同时保持了高效的 $O(d \log d)$ 计算成本。

原作者： Ying Feng, Piotr Indyk, Michael Kapralov, Dmitry Krachun, Boris Prokhorov

发布于 2026-05-14

📖 1 分钟阅读☕ 轻松阅读

原作者： Ying Feng, Piotr Indyk, Michael Kapralov, Dmitry Krachun, Boris Prokhorov

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

以下是论文《基于随机哈达玛变换的可证明量化》的解释，已用通俗语言和日常类比进行翻译。

宏观图景：压缩数据而不丢失核心内容

想象你有一个巨大的图书馆（数据），但只有一只小行李箱用来在旅途中携带它们。你需要把书缩小以 fits 进箱子，但同时必须确保当你后来 unpack 它们时，它们依然通顺，没有变成胡言乱语。

在机器学习领域，这种“缩小”被称为量化（quantization）。它是一个将复杂、精确的数字（如 3.14159265）转化为简单、简短的代码（如"3"或"A"）的过程，旨在节省空间并加速计算。

问题在于：如果你过于激进或草率地缩小它们，“书籍”就会失真。这篇论文提出了一种新的、巧妙的方法来缩小这些数字，它既快速，又在数学上保证失真极低。

旧方法：缓慢但完美的缩小器

长期以来，缩小数据的最佳方法涉及一种“魔法洗牌”。想象你有一副扑克牌（你的数据点）。为了压缩它们，你首先完美随机地洗牌，使每张牌都与其他牌充分混合。然后，你拍下每张牌的照片，并写下关于它的简单笔记。

优点：这种洗牌（称为“随机旋转”）保证你写下的笔记非常准确。
缺点：完美随机地洗牌 100 万张牌需要极长的时间。这就像试图用手混合一游泳池的水。对于现代计算机来说，这太慢了。

更快的方法：哈达玛洗牌

为了加快速度，工程师开始使用一种特定的、预先安排好的模式来洗牌，称为哈达玛变换（Hadamard Transform）。

优点：这就像拥有一台能在瞬间洗好牌的机器。它极其快速。
缺点：因为洗牌遵循严格的模式，所以它并非“真正随机”。有时，你写下的笔记会有些许偏差或不准确。这就像使用一个总是留下略微歪斜印记的印章。证明其完美工作的数学依据一直缺失。

论文的解决方案：“抖动”洗牌

这篇论文的作者问道：我们能否保持哈达玛机器的速度，同时修正那些歪斜的印记？

他们的答案是抖动（Dithering）。

类比：抖动相机

想象你正试图用一台快门有点粘滞的相机给移动物体拍照。有时照片会略显模糊或偏移。

技巧：在拍照之前，你向完全随机的方向轻微抖动相机（这就是“抖动”或“随机偏移”）。
结果：即使相机仍然粘滞，那微小的随机抖动也会平均掉误差。在拍摄多张照片后，模糊消失，图像再次变得清晰。

在这篇论文中，“相机”是量化过程，而“抖动”是在压缩数据之前向数据添加一个微小的随机数。

他们的证明

作者们不仅仅是猜测这会奏效；他们进行了繁重的数学推导来证明它。

无偏性：他们证明，如果你使用这种“抖动”过的哈达玛方法，平均结果与使用缓慢但完美的随机洗牌完全相同。你并没有系统性地朝某个方向丢失信息。
与最佳方法同样准确：他们表明，随着你使用更多的位数（笔记中的更多细节），他们快速方法的误差率会越来越接近缓慢但完美方法的误差率。事实上，它达到了理论上可能的最佳性能。
快速：因为他们只使用一次哈达玛洗牌（加上微小的随机抖动），该过程保持极其快速（ $O(d \log d)$ ），使其适用于海量数据集。

针对内积的两阶段过程

这篇论文还解决了一个特定且更困难的任务：比较两个向量（计算“内积”）。你可以将其想象为在不听完整歌曲的情况下，猜测两首歌有多相似。

他们提出了一种两步压缩法：

主要压缩：使用他们快速的“抖动”方法压缩第一首歌。
“剩余”压缩：任何没有完美 fit 的部分（“残差”或真实歌曲与压缩版本之间的差异）使用第二种更简单的技巧单独压缩。

他们证明，即使采用这种两步过程，误差仍然非常低，并且存储的数据总量仍然非常小。

总结

问题：我们需要快速压缩数据，但最快的方法通常缺乏坚实的数学保证。
解决方案：使用快速、结构化的洗牌（哈达玛），但添加微小的随机噪声（抖动）来修正误差。
结果：一种方法，其速度可与工业标准媲美，同时拥有与缓慢但完美的理论标准相同的数学保证。

简而言之：他们找到了一种方法，通过添加一点受控的混乱，使“快速洗牌”变得与“完美洗牌”一样好。

技术摘要：基于随机 Hadamard 变换的可证明量化

问题陈述
向量量化是将 $\mathbb{R}^d$ 中的实值向量压缩为紧凑二进制表示的基本原语，其应用范围涵盖相似度搜索、联邦学习、高效 Transformer 及模型压缩等。一种标准方法是对输入向量 $x$ 应用随机旋转矩阵 $R$ ，随后进行标量量化。虽然稠密随机旋转提供了清晰的理论保证（例如，$Rx $的坐标近似服从高斯分布），但其应用需要$ \Theta(d^2)$ 的时间复杂度，这对于高维向量而言是不可行的。

为解决这一问题，随机 Hadamard 变换（ $H_D$ ）常被用作一种结构化替代方案，其应用时间复杂度为 $O(d \log d)$ 。然而， $H_D$ 并非均匀随机旋转；它具有离散结构，使得理论分析变得复杂。现有针对使用单个 $H_D$ 进行量化的研究结果要么纯属经验性，要么提供的可证明保证较弱（需要更高的维度或更多的比特数），无法达到真正随机旋转所能实现的水平。挑战在于既要保持 Hadamard 变换的速度（ $O(d \log d)$ ），又要保留随机旋转所具备的强理论失真界。

方法论
作者提出了一种向量量化变体，将单个随机 Hadamard 变换与抖动（dithering，即注入随机偏移）相结合。核心方法论包括：

变换：输入向量 $x$ 通过 $y = H_D x$ 进行变换，其中 $H$ 是归一化的 Hadamard 矩阵， $D$ 是包含独立 Rademacher（ $\pm 1$ ）元素的对角矩阵。
抖动标量量化：该方法不对 $y$ $y$ 的坐标直接进行量化，而是先将每个坐标移动一个随机偏移量，再对每个坐标应用标量量化器。
- 该标量量化器基于抖动版本的 Lloyd 量化。
- 它利用了一个特定的映射函数 $F(t)$ ，定义为均值为 0、方差为 3 的高斯随机变量的累积分布函数（CDF）（由密度 $\phi(t)^{1/3}$ 推导得出）。
- 在分位数空间中，将随机偏移参数 $U \sim \text{Unif}[0, 1)$ 应用于量化网格。
无偏性：论文提出了两种算法。算法 1 提供了均方误差（MSE）界，但存在轻微偏差。算法 5 修改了重建规则（使用特定函数 $G$ 代替 $F^{-1}$ ），以确保估计量是无偏的（ $E[\hat{x}] = x$ ），同时保持渐近 MSE 界。
内积量化：为了支持内积估计，作者提出了一种两阶段量化器（算法 4）。在基础量化之后，对残差向量 $r = x - \hat{x}$ $r = x - \overset{x}{^}$ 进行量化。这包括：
- 对残差的尺度进行量化。
- 对残差应用新的随机 Hadamard 变换。
- 使用基于级别的方案和随机符号位对变换后残差的坐标进行量化，以消除误差与查询向量之间的相关性。

主要贡献与结果

渐近最优性：主要的理论贡献在于证明，结合单个随机 Hadamard 变换的抖动量化，其均方误差界在渐近意义上与真正随机旋转矩阵所达到的界相匹配。
- 定理 1.1：对于任意单位向量 $x$ ，无偏估计量 $\hat{x}$ 满足：
  $E[\|\hat{x} - x\|_2^2] \le \left(\frac{\pi\sqrt{3}}{2} + o(1)\right) \cdot 4^{-b}$
  其中 $b$ 是每个坐标的比特宽度。当 $b \to \infty$ 时， $o(1)$ 项在所有维度 $d$ 和单位向量 $x$ 上均匀趋于零。该常数与 TurboQuant（假设完全随机旋转）所达到的界相匹配。
无偏性：所提出的量化器是无偏的，这一特性对于联邦学习等应用至关重要，因为偏差累积可能会损害模型收敛。
内积保证：论文提供了内积估计误差的界（定理 1.2）。结果表明，平方误差按 $O(1/(d \cdot 4^b))$ 缩放，利用 Rademacher 变量的混合四阶矩性质来处理残差与查询向量之间的相关性。
比特复杂度：两阶段内积量化器可以使用 $db + (3 + \frac{1}{2\ln 2})d + O(\log(b + \log d))$ 比特存储，在 $d$ 上保持线性存储复杂度。

意义与主张
论文声称，其方法解决了向量量化中计算效率与理论保证之间的权衡问题。通过引入抖动，作者克服了由 Hadamard 变换的离散结构所带来的分析困难。

理论依据：该工作为在 TurboQuant 和 EDEN 等方法中使用单个随机 Hadamard 矩阵提供了理论依据，这些方法此前依赖完全随机旋转来获得理论保证。
简单性与复杂性：与先前需要组合多个 Hadamard 变换（例如 $H_{D_1}H_{D_2}$ ）来近似随机旋转的方法不同，该方法通过单个变换和简单的抖动实现了可比的保证，从而保持了较低的实现复杂度。
局限性：作者明确指出，这项工作主要是理论性的。它刻画了最坏情况下的均方误差和内积误差，但并未优化有限比特常数，也未在下游系统中提供实证评估。该分析专门针对基于单个随机 Hadamard 变换和随机抖动的数据无关量化器。