Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization¶

会议: NeurIPS 2025 arXiv: 2510.23485 代码: 无领域: 模型压缩 关键词: generalization bounds, conditional mutual information, stochastic projection, lossy compression, memorization

一句话总结¶

通过在 CMI（条件互信息）框架中引入随机投影和有损压缩，推导出更紧的泛化界，解决了经典 CMI 界在 SCO 反例上失效的问题，并证明记忆化对良好泛化并非必要。

研究背景与动机¶

领域现状：信息论方法是分析学习算法泛化误差的重要工具。互信息（MI）界 [Xu & Raginsky 2017] 和条件互信息（CMI）界 [Steinke & Zakynthinou 2020] 提供了直观的泛化保证——算法输出对训练数据揭示的信息越少，泛化越好。CMI 通过 "super-sample" 构造避免了 MI 界在连续/确定性情形下的发散问题。
现有痛点：近期 Attias et al. [2024] 和 Livni [2023] 构造了精巧的反例，表明经典 CMI 界在某些随机凸优化（SCO）问题上变得空洞无意义——泛化界不随训练集大小 $n$ 衰减，而是保持 $\Theta(LR)$ 量级。这一发现甚至引发了对信息论泛化界实用性的根本质疑。
核心矛盾：反例的关键在于假设空间维度 $D$ 随 $n$ 增长为 $\Omega(n^4 \log n)$（过参数化），使得 CMI 项爆炸。但实际上学习算法可能只在低维子空间上有意义。经典 CMI 界未能利用"模型的有效维度远低于名义维度"这一结构性质。
本文要解决什么：(1) 修复 CMI 界在 SCO 反例上的失效；(2) 证明引入投影和压缩后的新 CMI 界仍能给出 $\mathcal{O}(1/\sqrt{n})$ 的正确泛化行为；(3) 证明记忆化对良好泛化并非必要。
切入角度：既然反例依赖于高维假设空间，那么通过随机投影到低维子空间 + 量化来压缩模型，同时控制投影引入的失真，就可以使 CMI 项保持有界。
核心 idea 一句话：用随机投影 $\Theta^\top W$ 将 $D$ 维模型压缩到 $d$ 维（$d$ 可选为 1），再量化为 $\hat{W}$，这样 CMI 界依赖低维 $d$ 而不依赖可能爆炸的 $D$。

方法详解¶

整体框架¶

给定学习算法 $\mathcal{A}: \mathcal{Z}^n \to \mathcal{W} \subseteq \mathbb{R}^D$，构造辅助算法： 1. 随机投影：$\Theta \in \mathbb{R}^{D \times d}$ 将 $W$ 投影到 $d$ 维（$d \ll D$） 2. 有损压缩：对投影后的 $\Theta^\top W$ 进行量化得到 $\hat{W}$ 3. 投影回原空间：辅助模型 $\Theta \hat{W}$ 替代原模型 $W$

关键设计¶

1. 主定理 (Theorem 1)¶

核心公式： $$\text{gen}(\mu, \mathcal{A}) \leq \inf_{P_{\hat{W}|\Theta^\top W}} \inf_{P_\Theta} \mathbb{E}_{P_{\tilde{\mathbf{S}}} P_\Theta} \left[\sqrt{\frac{2\Delta\ell_{\hat{w}}(\tilde{\mathbf{S}}, \Theta)}{n} \mathsf{CMI}^\Theta(\tilde{\mathbf{S}}, \hat{\mathcal{A}})}\right] + \epsilon$$

其中 $\epsilon$ 衡量辅助模型与原模型的泛化误差之差，$\Delta\ell_{\hat{w}}$ 是损失波动项。

设计动机：原始 CMI 界依赖 $D$ 维模型的 CMI，可能很大；新界依赖 $d$ 维压缩模型的 CMI，$d$ 可以任意选择以使界非空洞。关键是 $\epsilon$（失真项）可通过集中不等式控制。

2. CLB 反例的求解 (Theorem 3)¶

问题设定：$\ell_c(z, w) = -L\langle w, z \rangle$，$\mathcal{W} = \mathcal{B}_D(R)$，$D = \Omega(n^4 \log n)$。

核心结果： $$\text{gen}(\mu, \mathcal{A}) \leq \frac{8LR}{\sqrt{n}}$$

对最优样本复杂度 $N(\varepsilon, \delta) = \Theta(L^2 R^2 / \varepsilon^2)$，得到 $\text{gen}(\mu, \mathcal{A}) = \mathcal{O}(\varepsilon)$。

关键技术：投影到 $d = 1$ 维即可！使用 Johnson-Lindenstrauss 投影 + 在低维空间加噪，通过 Markov 链 $(S_n, \Theta, W) - \Theta^\top W - \hat{W}$ 控制信息流。

3. 记忆化非必要性 (Theorem 6)¶

做什么：证明对任意学习算法 $\mathcal{A}$，存在辅助算法 $\mathcal{A}^* = \Theta \tilde{\mathcal{A}}(\Theta^\top \mathcal{A}(S_n))$，满足： - 泛化误差与原算法差距 $\mathcal{O}(n^{-r})$（任意 $r > 0$） - 任何对手均无法追踪训练数据

投影维度：$d = 500r \log(n)$。

损失函数/训练策略¶

本文是纯理论工作，没有训练策略。核心构造是： - 投影矩阵 $\Theta$：使用 JL 随机投影（各行 i.i.d. 高斯） - 量化器 $P_{\hat{W}|\Theta^\top W}$：在投影空间加独立高斯噪声 - 失真控制：利用凸-Lipschitz 性质 + 集中不等式

实验关键数据¶

主实验¶

本文为纯理论工作，无数值实验。主要理论结果对比：

问题实例	经典 CMI 界	本文新界	改进
CLB ($\mathcal{P}_{cvx}^{(D)}$)	$\Theta(LR)$（不衰减）	$8LR/\sqrt{n}$	从不衰减到 $\mathcal{O}(1/\sqrt{n})$
CSL ($\mathcal{P}_{scvx}^{(D)}$)	不衰减	$8L_cR/\sqrt{n}$	从不衰减到 $\mathcal{O}(1/\sqrt{n})$
Livni SCO	MI 界空洞	$\mathcal{O}(1/\sqrt{n})$	从空洞到有意义
广义线性 SCO	-	$\mathcal{O}(1/n^{1/4})$	非凸扩展

消融实验¶

投影维度 $d$ 的影响：

问题	所需 $d$	说明
CLB 反例	$d = 1$	极端压缩即可
CSL 反例	$d = 1$	强凸性不改变投影需求
广义线性 SCO	$d = \Theta(\sqrt{n})$	更大问题类需更高维投影
记忆化分析	$d = \Theta(\log n)$	对数增长已足够

关键发现¶

经典 CMI 界失效不是 CMI 框架的固有缺陷，而是未利用模型的低维结构
仅需 $d = 1$ 维投影即可修复 CLB 和 CSL 反例
记忆化对泛化非必要：辅助算法可以不记忆训练数据同时保持可比的泛化性能
但辅助算法的范数可能增长为 $\Omega(n^3)$，这是阻止 Attias et al. 记忆化必要性定理适用的关键

亮点与洞察¶

修复了 CMI 框架的"危机"：直接回应了 Attias et al. 和 Livni 提出的负面结果，展示了 CMI + 投影/压缩的强大能力
记忆化的新理解：给出了建设性证明——任何记忆化算法都可构造一个等效的非记忆化变体，揭示记忆化与泛化的深层关系
与率失真理论的联系：投影+量化的构造本质上是经典信息论中率失真编码的思想在学习理论中的应用
洞察深刻：过参数化导致的 CMI 爆炸可通过投影到有效子空间来消除，这提供了理解深度学习泛化的新视角

局限性/可改进方向¶

纯理论工作：无实验验证，不确定理论界的数值紧度
投影选择：最优投影矩阵的选择是开放问题；JL 投影可能不是最优的
凸限制：最优 $\mathcal{O}(1/\sqrt{n})$ 速率仅对 SCO 问题证明；广义非凸版本衰减更慢 $\mathcal{O}(1/n^{1/4})$
实用算法设计：如何将投影+压缩思想转化为实用的正则化或训练策略仍是开放问题
辅助模型范数增长：辅助算法的范数可能很大，在实际中可能带来数值不稳定性

评分¶

⭐⭐⭐⭐ (4/5)

理论贡献重大，优雅地解决了 CMI 框架的"危机"，并深化了对记忆化的理解。但纯理论无实验，与实际算法设计的距离较远。

问题实例	经典 CMI 界	本文新界	改进
CLB (\(\mathcal{P}_{cvx}^{(D)}\))	\(\Theta(LR)\)（不衰减）	\(8LR/\sqrt{n}\)	从不衰减到 \(\mathcal{O}(1/\sqrt{n})\)
CSL (\(\mathcal{P}_{scvx}^{(D)}\))	不衰减	\(8L_cR/\sqrt{n}\)	从不衰减到 \(\mathcal{O}(1/\sqrt{n})\)
Livni SCO	MI 界空洞	\(\mathcal{O}(1/\sqrt{n})\)	从空洞到有意义
广义线性 SCO	-	\(\mathcal{O}(1/n^{1/4})\)	非凸扩展

问题	所需 \(d\)	说明
CLB 反例	\(d = 1\)	极端压缩即可
CSL 反例	\(d = 1\)	强凸性不改变投影需求
广义线性 SCO	\(d = \Theta(\sqrt{n})\)	更大问题类需更高维投影
记忆化分析	\(d = \Theta(\log n)\)	对数增长已足够