一句话总结

这项工作建立了随机凸优化中超额误差与条件互信息之间的精确权衡，证明了 $L ^ { 2 }$L2 利普希茨有界情形下条件互信息下界为 $\Omega ( 1 / \varepsilon ^ { 2 } )$Ω(1/ε2)，强凸情形下为 $\Omega ( 1 / \varepsilon )$Ω(1/ε)，并通过构造能够识别相当比例训练样本的对抗者，证明记忆化是不可避免的。

核心贡献

• 记忆化定义为学习器透露出的关于其训练样本的信息，并用条件互信息度量；对于任意超额误差为 ε 的学习器，在 L2 利普希茨有界情形下可得下界 Ω(1/ε^2)，在强凸情形下可得下界 Ω(1/ε)。
• 针对特定随机凸优化实例构造了对抗者，能够准确识别相当比例的训练样本，这表明记忆化对于学习这些问题是必要的。
• 推论证明：当维度至少为 Ω(n^4 log n) 时，达到样本复杂度 Θ(1/ε^2)（利普希茨有界损失）或 Θ(1/ε)（强凸损失）的样本压缩方案需要大小为 Ω(n)，这揭示了基于 CMI 的泛化界以及随机凸优化中样本不可压缩性的局限。

引言

这篇论文重新审视学习器为了泛化必须知道关于训练数据的多少。在机器学习中，随机凸优化 (SCO) 为现代基于梯度的训练提供了可处理模型，尤其是一阶算法即使参数维度很大通常也能良好泛化。这使 SCO 成为检验理想学习与深度模型之间张力的自然试验场：理想学习在不记忆噪声的情况下提取结构，而深度模型能够在保留训练样本的同时达到高准确率。早期的信息论解释主要使用输入输出互信息，但该度量将记忆点数与每个点中存储的熵混为一谈，并且已知其随维度扩大而恶化。基于条件互信息，作者证明了 SCO 中 ε-学习器的紧 CMI 与准确率权衡，表明样本高效的学习需要与最优样本规模同阶的 CMI。他们还表明这一信息可解释为记忆化，因为对抗者能够识别出固定比例的训练样本，并且他们推导了泛化界以及常量大小样本压缩不可能性的相关推论。

方法

分析被组织为一条信息论流水线，用于刻画准确的 $\varepsilon$ε-学习器必须透露多少关于其训练样本的信息。该方法没有研究具体神经网络架构或训练循环，而是把学习算法 $\mathcal{A}_n$An​ 视为一个随机通道，将训练集 $S_n$Sn​ 映射为估计量 $\widehat{\theta}=\mathcal{A}_n(S_n)$θ=An​(Sn​)，并询问当学习器达到目标准确率时，必须有多少比特的样本信息通过该通道泄露。所得框架将随机凸优化问题下的超额风险、样本复杂度、条件互信息和算法信息使用量联系起来。

框架的核心是随机凸优化问题 $(\Theta,\mathcal{Z},f)$(Θ,Z,f) 的超额误差分解。对于数据分布 $\mathcal{D}$D，定义总体目标和经验目标

$$\mathrm{F}_{\mathcal{D}}(\theta)=\mathbb{E}_{Z\sim\mathcal{D}}[f(\theta,Z)], \qquad \widehat{\mathrm{F}}_{S_n}(\theta)=\frac{1}{n}\sum_{i=1}^n f(\theta,Z_i).$$FD​(θ)=EZ∼D​[f(θ,Z)],FSn​​(θ)=n1​i=1∑n​f(θ,Zi​).

控制期望总体超额误差的一种标准方式，是将其拆分为泛化项和优化项：

$$\mathbb{E}\left[\mathrm{F}_{\mathcal{D}}(\mathcal{A}_n(S_n))\right] - \min_{\theta\in\Theta}\mathrm{F}_{\mathcal{D}}(\theta) \le \operatorname{EGE}_{\mathcal{D}}(\mathcal{A}_n) + \mathbb{E}\left[ \widehat{\mathrm{F}}_{S_n}(\mathcal{A}_n(S_n)) - \min_{\theta\in\Theta}\widehat{\mathrm{F}}_{S_n}(\theta) \right].$$E[FD​(An​(Sn​))]−θ∈Θmin​FD​(θ)≤EGED​(An​)+E[FSn​​(An​(Sn​))−θ∈Θmin​FSn​​(θ)].

对于直径不超过 $R$R 的参数空间上凸的 $L$L-利普希茨损失，基于条件互信息的泛化界用以下项控制泛化项：

$$\operatorname{EGE}_{\mathcal{D}}(\mathcal{A}_n) \le LR\sqrt{\frac{8\,\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n)}{n}}.$$EGED​(An​)≤LRn8CMID​(An​)​​.

由此得到依赖于信息的超额误差控制

$$\mathbb{E}\left[\mathrm{F}_{\mathcal{D}}(\mathcal{A}_n(S_n))\right] - \min_{\theta\in\Theta}\mathrm{F}_{\mathcal{D}}(\theta) \le LR\sqrt{\frac{8\,\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n)}{n}} + \mathbb{E}\left[ \widehat{\mathrm{F}}_{S_n}(\mathcal{A}_n(S_n)) - \min_{\theta\in\Theta}\widehat{\mathrm{F}}_{S_n}(\theta) \right].$$E[FD​(An​(Sn​))]−θ∈Θmin​FD​(θ)≤LRn8CMID​(An​)​​+E[FSn​​(An​(Sn​))−θ∈Θmin​FSn​​(θ)].

第一个分析模块检查该分解对于最优学习器是否紧致。以准确率 $\varepsilon$ε 学习凸利普希茨损失的最优样本复杂度量级为

$$\Theta\left(\left(\frac{LR}{\varepsilon}\right)^2\right).$$Θ((εLR​)2).

随后框架构造分布，使得任何样本复杂度接近最优的学习器都拥有较大的条件互信息。在归一化情形 $L=R=1$L=R=1 中，任意 $\varepsilon$ε-学习器的条件互信息按以下量级增长

$$\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n) = \Omega\left(\frac{1}{\varepsilon^2}\right).$$CMID​(An​)=Ω(ε21​).

恢复对 $L$L 和 $R$R 的依赖后，这意味着条件互信息项必须足够大，以至于

$$LR\sqrt{\frac{\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n)}{n}} = \Theta(LR),$$LRnCMID​(An​)​​=Θ(LR),

尽管学习器可能实现至多为 $\varepsilon$ε 的超额误差。因此，对于此类问题，基于条件互信息的泛化界无法为每个最优样本复杂度学习器保证最优超额风险。该局限并非绑定于某一具体算法，而是在样本复杂度达到统计最小值的算法之间普遍存在。

下界构造分阶段进行。第一阶段构造一个困难的凸利普希茨问题。在简化的归一化情形下，设

$$\mathcal{Z}=\left\{\pm \frac{1}{\sqrt d}\right\}^d, \qquad \Theta=B_d(1), \qquad f(\theta,z)=-\langle\theta,z\rangle.$$Z={±d​1​}d,Θ=Bd​(1),f(θ,z)=−⟨θ,z⟩.

该损失是凸的且为 $1$1-利普希茨。其总体最优解由分布均值确定

$$\mu=\mathbb{E}_{Z\sim\mathcal{D}}[Z].$$μ=EZ∼D​[Z].

第二阶段证明，任何准确学习器都必须产生与 $\mu$μ 强对齐的输出。更具体地说，对于每个准确学习器和适当分布，可以建立如下形式的相关性

$$\|\mu\|-\varepsilon \le \mathbb{E}\left[\langle \widehat{\theta},\mu\rangle\right], \qquad \widehat{\theta}=\mathcal{A}_n(S_n).$$∥μ∥−ε≤E[⟨θ,μ⟩],θ=An​(Sn​).

这意味着平均预测表现良好的学习器必须隐式编码关于未知数据分布均值的信息。由于学习器只能观测有限样本，框架随后将这种与均值的相关性转换为与单个训练样本的相关性。使用如下形式的加权坐标相关表达式

$$\mathbb{E}\left[ \sum_{i=1}^n\sum_{k=1}^d \frac{144\varepsilon^2-d(\mu^{(k)})^2}{1-d(\mu^{(k)})^2} \, \widehat{\theta}^{(k)} \left(Z_i^{(k)}-\mu^{(k)}\right) \right] \ge 2\varepsilon-4\delta$$E[i=1∑n​k=1∑d​1−d(μ(k))2144ε2−d(μ(k))2​θ(k)(Zi(k)​−μ(k))]≥2ε−4δ

来量化学习到的参数如何追踪样本围绕均值的波动。等价地，可以通过对角加权矩阵 $A$A 聚合这些坐标，并定义样本级统计量

$$T_{0,i}=\langle \widehat{\theta},A(Z_{0,i}-\mu)\rangle, \qquad T_{1,i}=\langle \widehat{\theta},A(Z_{1,i}-\mu)\rangle.$$T0,i​=⟨θ,A(Z0,i​−μ)⟩,T1,i​=⟨θ,A(Z1,i​−μ)⟩.

条件互信息构造为每个样本坐标引入两个可能实现 $Z_{0,i}$Z0,i​ 和 $Z_{1,i}$Z1,i​，并引入一个隐藏比特 $U_i$Ui​ 指示实际训练集使用了哪一个实现。随后从 $U_i$Ui​ 的视角审视学习器输出和这些统计量。

关键的信息计数思想，是识别两个可能实现跨越某个精心选择阈值的坐标。设

$$\tau=\Theta\left(\frac{\varepsilon}{n}\right),$$τ=Θ(nε​),

定义

$$\mathcal{I} = \left\{ i: \max\{T_{0,i},T_{1,i}\}>\tau \ \text{and}\ \min\{T_{0,i},T_{1,i}\}<\tau \right\}.$$I={i:max{T0,i​,T1,i​}>τ and min{T0,i​,T1,i​}<τ}.

对于 $\mathcal{I}$I 中的坐标，学习器统计量对存在哪一个实现敏感，因此这些坐标倾向于揭示隐藏比特 $U_i$Ui​。高维参数 $d\ge \Omega(n^4\log n)$d≥Ω(n4logn) 确保对应未使用实现的统计量以高概率很小，同时与实际样本的聚合相关性仍保持很大。$\mathcal{I}$I 的基数随后与求和比值相关：

$$|\mathcal{I}| = \Omega\left( \frac{\left(\sum_{i=1}^n T_{U_i,i}\right)^2} {\sum_{i=1}^n T_{U_i,i}^2} \right).$$∣I∣=Ω(∑i=1n​TUi​,i2​(∑i=1n​TUi​,i​)2​).

利用聚合相关性下界以及平方聚合上界，可得

$$\mathbb{E}|\mathcal{I}| = \Omega\left(\frac{1}{\varepsilon^2}\right),$$E∣I∣=Ω(ε21​),

这转化为

$$\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n) = \Omega\left(\frac{1}{\varepsilon^2}\right)$$CMID​(An​)=Ω(ε21​)

对归一化凸利普希茨实例而言。重新缩放后，这给出一般 $L$L 和 $R$R 的相应下界。

下一个模块将论证从正确学习器扩展到非正确学习器；前者的输出位于 $B_d(1)$Bd​(1) 中，后者的输出可位于 $\mathbb{R}^d$Rd 中的任意位置。做法是将原始约束损失替换为在全空间上的扩展：

$$\widetilde{f}(\theta,z) = \inf_{w\in B_d(1)} \left\{ f(w,z)+\|\theta-w\| \right\}.$$f​(θ,z)=w∈Bd​(1)inf​{f(w,z)+∥θ−w∥}.

对于线性损失 $f(\theta,z)=-\langle\theta,z\rangle$f(θ,z)=−⟨θ,z⟩，该修改损失仍为凸且 $1$1-利普希茨。随后分析将任何非正确学习器的输出投影回 $B_d(1)$Bd​(1)：

$$\Pi(\widehat{\theta}) = \Pi(\mathcal{A}_n(S_n)),$$Π(θ)=Π(An​(Sn​)),

其中 $\Pi$Π 表示到单位球的投影。由于数据处理不等式，投影不会增加条件互信息。此外，如果非正确学习器对扩展问题准确，则投影后的学习器对原始约束问题准确。因此非正确情形归约到正确情形，并得到相同的条件互信息下界。

框架还包含匹配的上界，表明下界并非特定困难实例造成的假象。对于凸利普希茨损失，存在一个正确 $\varepsilon$ε-学习器，其样本复杂度为

$$N(\varepsilon,\delta) = \frac{128(LR)^2}{\varepsilon^2}\log\left(\frac{2}{\delta}\right),$$N(ε,δ)=ε2128(LR)2​log(δ2​),

使得只要 $n\ge N(\varepsilon,\delta)$n≥N(ε,δ)，该学习器以至少 $1-\delta$1−δ 的概率满足

$$\mathrm{F}_{\mathcal{D}}(\mathcal{A}_n(S_n)) - \min_{\theta\in\Theta}\mathrm{F}_{\mathcal{D}}(\theta) \le \varepsilon$$FD​(An​(Sn​))−θ∈Θmin​FD​(θ)≤ε

并且其信息复杂度满足

$$\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n) \le \frac{128(LR)^2}{\varepsilon^2}\log\left(\frac{2}{\delta}\right).$$CMID​(An​)≤ε2128(LR)2​log(δ2​).

这一匹配构造为最优学习器所需样本信息量给出上包络。它表明，对于这一类问题，学习所需条件互信息与达到准确率所需样本复杂度以相互兼容的 $\varepsilon^{-2}$ε−2 方式缩放。

一条并行流水线处理强凸损失。困难问题定义为

$$\Theta=\mathbb{R}^d, \qquad \mathcal{Z}=\left\{\pm \frac{1}{\sqrt d}\right\}^d, \qquad f(\theta,z)=-\langle\theta,z\rangle+\frac{1}{2}\|\theta\|^2.$$Θ=Rd,Z={±d​1​}d,f(θ,z)=−⟨θ,z⟩+21​∥θ∥2.

总体最优解仍然是均值 $\mu=\mathbb{E}_{\mathcal{D}}[Z]$μ=ED​[Z]，并且对于任何输出 $\widehat{\theta}$θ，总体超额风险归约为欧几里得距离平方：

$$\mathrm{F}_{\mathcal{D}}(\widehat{\theta}) - \min_{\theta\in\mathbb{R}^d}\mathrm{F}_{\mathcal{D}}(\theta) = \frac{1}{2}\|\widehat{\theta}-\mu\|^2.$$FD​(θ)−θ∈Rdmin​FD​(θ)=21​∥θ−μ∥2.

由于数据均值位于 $B_d(1)$Bd​(1) 内部，任何输出都可以投影到 $B_d(1)$Bd​(1) 上而不增加超额风险。投影同样不会增加条件互信息，因此分析可以聚焦于输出位于单位球内的学习器。

对于这些学习器，准确率不仅意味着与 $\mu$μ 对齐，也意味着接近 $\mu$μ：

$$\|\widehat{\theta}-\mu\|^2\le 2\varepsilon$$∥θ−μ∥2≤2ε

以高概率成立。随后，一个指纹式引理保证存在某个分布，使学习器输出与样本波动相关：

$$\mathbb{E}\left[ \sum_{i=1}^n \langle \widehat{\theta}-\mu, Z_i-\mu\rangle \right] \ge \frac{1}{3}-2\varepsilon-3\delta.$$E[i=1∑n​⟨θ−μ,Zi​−μ⟩]≥31​−2ε−3δ.

条件互信息构造使用统计量

$$T_{0,i}=\langle \widehat{\theta}-\mu, Z_{0,i}-\mu\rangle, \qquad T_{1,i}=\langle \widehat{\theta}-\mu, Z_{1,i}-\mu\rangle.$$T0,i​=⟨θ−μ,Z0,i​−μ⟩,T1,i​=⟨θ−μ,Z1,i​−μ⟩.

再次使用阈值 $\tau=\Theta(1/n)$τ=Θ(1/n) 定义边界集：

$$\mathcal{I} = \left\{ i: \max\{T_{0,i},T_{1,i}\}>\tau \ \text{and}\ \min\{T_{0,i},T_{1,i}\}<\tau \right\}.$$I={i:max{T0,i​,T1,i​}>τ and min{T0,i​,T1,i​}<τ}.

相同的信息计数逻辑适用。$\mathcal{I}$I 的基数下界为一个聚合相关性项之比：

$$|\mathcal{I}| = \Omega\left( \frac{\left(\sum_{i=1}^n T_{U_i,i}\right)^2} {\sum_{i=1}^n T_{U_i,i}^2} \right).$$∣I∣=Ω(∑i=1n​TUi​,i2​(∑i=1n​TUi​,i​)2​).

在强凸情形中，在该构造下分子有常数下界，而分母按 $O(\varepsilon)$O(ε) 缩放。由此得到

$$\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n) = \Omega\left(\frac{1}{\varepsilon}\right).$$CMID​(An​)=Ω(ε1​).

针对强凸利普希茨损失的匹配上界表明，存在一个学习器，其样本复杂度依赖于 $L^2/(\lambda\varepsilon)$L2/(λε)，其中 $\lambda$λ 表示强凸性参数，使得

$$\mathbb{E}[\mathrm{F}_{\mathcal{D}}(\mathcal{A}_n(S_n))] - \min_{\theta\in\Theta}\mathrm{F}_{\mathcal{D}}(\theta) \le \varepsilon,$$E[FD​(An​(Sn​))]−θ∈Θmin​FD​(θ)≤ε,

以及

$$\mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n) \le O\left(\frac{L^2}{\lambda\varepsilon}\right).$$CMID​(An​)≤O(λεL2​).

因此强凸流水线得到更紧的 $\varepsilon^{-1}$ε−1 依赖，而非凸利普希茨情形的 $\varepsilon^{-2}$ε−2 依赖。

框架还考虑一种精化的信息度量，称为单样本条件互信息，其定义为

$$\mathrm{ISCMI}_{\mathcal{D}}(\mathcal{A}_n) = \sum_{i=1}^n I\left( \mathcal{A}_n(S); U_i \mid Z_{0,i},Z_{1,i} \right).$$ISCMID​(An​)=i=1∑n​I(An​(S);Ui​∣Z0,i​,Z1,i​).

该量旨在避开标准条件互信息的条件化结构；即便对某些自然的确定性学习器，标准条件互信息也可能很大。该量始终受标准条件互信息上界限制：

$$\mathrm{ISCMI}_{\mathcal{D}}(\mathcal{A}_n) \le \mathrm{CMI}_{\mathcal{D}}(\mathcal{A}_n).$$ISCMID​(An​)≤CMID​(An​).

因此下界构造检查此前导出的权衡是否仅依赖于标准条件互信息所用的更强条件化。答案为否：对于凸利普希茨学习，同样的 $\Omega(1/\varepsilon^2)$Ω(1/ε2) 下界，以及对于强凸学习的同样 $\Omega(1/\varepsilon)$Ω(1/ε) 下界，对单样本条件互信息仍然成立。换言之，准确学习器所揭示样本信息的必要性能经受这种精化。

总体而言，方法论结构是一系列归约步骤：首先将超额风险与信息泄露联系起来，其次构造困难的几何问题实例，然后证明准确学习器必须与分布均值和单个样本相关，再将该相关性转化为隐藏比特恢复，最后用显式构造的学习器匹配下界。所得框架不仅刻画泛化界是否在数学上有效，也刻画该界能否紧追踪最优学习器在训练过程中被迫暴露的信息。

实验

评估研究随机凸优化中互信息与准确率的关系，方法是考虑高维设置中的利普希茨凸目标和强凸目标。结果建立 ε-学习器的信息下界，并通过子采样和基于稳定性学习获得的匹配上界证明这些下界是紧的。基于召回的记忆化博弈进一步验证，学习器捕获的信息可被对抗者利用来识别真实训练样本，从而将较大的 CMI 与具体记忆化行为连接起来。