A Law of Data Reconstruction for Random Features (and Beyond)¶

会议: ICLR 2026
arXiv: 2509.22214
代码: https://github.com/iurada/data-reconstruction-law
领域: 机器学习理论 / 隐私
关键词: 数据重构, 过参数化, 随机特征, 记忆化, 隐私

一句话总结¶

从信息论和代数角度证明随机特征模型中存在数据重构定律：当参数量 \(p \gg dn\)（\(d\) 为数据维度，\(n\) 为样本数）时，训练数据可被完整重构，并通过投影损失优化方法在 RF、两层网络和 ResNet 上验证了该阈值的普适性。

研究背景与动机¶

领域现状：已知当参数量 \(p \gg n\) 时神经网络可以插值（记忆标签），经典理论将记忆化等同于标签拟合。
现有痛点：关于从模型参数重构训练数据（而非仅拟合标签），缺乏理论刻画。经验上观察到模型越大重构越容易，但无严格的参数量阈值理论。基础模型（如 GPT-4、Stable Diffusion）的数据提取攻击揭示了隐私风险，亟需理解重构的可行性条件。
核心矛盾：标签拟合需要 \(p \geq n\) 个自由度（\(n\) 个方程），但数据重构需要恢复整个 \(d \times n\) 维输入矩阵，直觉上需要 \(p \geq dn\) 个自由度——但这是否成立缺乏证明。
本文要解决什么？ 建立数据重构的参数量阈值理论，回答"模型需要多大才能记忆训练数据（而非仅记忆标签）"。
切入角度：在可分析的随机特征 (RF) 模型上建立理论，通过特征空间子空间的性质推导重构充分条件，再通过数值实验验证推广到深度网络。
核心 idea 一句话：数据重构存在相变阈值 \(p \approx dn\)——低于此值不可能，高于此值训练数据可从模型参数完整恢复。

方法详解¶

整体框架¶

理论部分在随机特征回归模型 \(f_{RF}(x,\theta) = \varphi(x)^\top \theta\) 上建立两个定理，证明 \(p \gg dn\) 时特征空间子空间唯一确定原始训练数据。实验部分提出基于投影损失的优化重构算法，并在 RF、两层网络、深度 ResNet 上验证阈值。

关键设计¶

Theorem 1: 重构的唯一性:
做什么：证明当 \(p \gg dn\) 时，如果候选重构 \(\hat{X}\) 的特征张成的子空间包含原始特征，则 \(\hat{X}\) 的每行必须接近某个训练样本
核心思路：利用 RF 核集中性保证 \(\Phi\) 行线性无关，然后对非线性 Hermite 分量分析 \(\varphi(\hat{x}) = \sum a_i \varphi(x_i)\) 的约束。通过 \(\varepsilon\)-net 论证实现对所有 \(\hat{x}\) 的一致集中，关键地利用了 \(p \gg dn\) 条件
设计动机：建立"特征子空间相等 → 输入数据相近"的充分条件，为重构提供理论基础
Theorem 2: 排除重复:
做什么：证明在 \(n=2\) 的情况下，重构不会出现重复（两行不会都接近同一个训练样本）
核心思路：反证法+Taylor 展开。假设 \(\hat{x}_1, \hat{x}_2\) 都接近 \(x_1\)，通过对残差 \(\varepsilon_2 - \varepsilon_1\) 方向的投影分析推导矛盾，利用广义 Stein 引理处理高阶非线性项
设计动机：补全 Theorem 1 的缺口——确保整个训练集被完整重构而非部分冗余
投影损失重构算法:
做什么：提出实用的数据重构优化目标 \(\mathcal{L}(\hat{X}) = \|P_{\hat{\Phi}}^\perp \theta^*\|_2^2\)
核心思路：由于训练参数 \(\theta^* = \Phi^+ Y \in \text{span}\{\varphi(x_i)\}\)，要求 \(\theta^*\) 落在重构特征张成的子空间内。用梯度下降优化 \(\hat{X}\)，每步后将行归一化到球面上
设计动机：将理论的子空间包含条件转化为可优化的损失函数，且该方法不限于 RF 模型

损失函数 / 训练策略¶

重构方法使用带动量的梯度下降优化投影损失，无需训练新模型。需要访问训练好的最后一层参数 \(\theta^*\) 和随机特征矩阵 \(V\)（或等价的前层参数）。

实验关键数据¶

主实验¶

CIFAR-10 RF 模型重构 (\(n=100\), \(d=3072\), ReLU):

参数量 \(p\)	训练损失	重构误差 \(\rho\)	状态
\(p = n\)	~0	~1.0	仅标签拟合
\(p = dn\)	~0	~0.5	开始重构
\(p = 10dn\)	~0	~0	完整重构

消融实验¶

配置	重构阈值	说明
RF (球面数据)	\(p \approx dn\)	与理论完全一致
两层网络 (GD训练)	\(p^{(L)} \approx dn\)	最后一层参数量决定
ResNet (GD训练)	\(p^{(L)} \approx dn\)	同样成立
Logistic loss (分类)	\(p \approx dn\)	不限于回归
Cross-entropy	\(p^{(L)} \approx dn\)	同样成立

关键发现¶

标签拟合阈值 \(p = n\) 和数据重构阈值 \(p = dn\) 是两个截然不同的相变——两者之间存在巨大的"灰色地带"（模型记住标签但无法重构数据）
ReLU 的符号歧义：由于 ReLU 的奇数阶 Hermite 系数（\(\geq 3\) 阶）为零，重构可能出现符号翻转。使用 \(\phi(z) = \text{ReLU}(z) + \tanh(z)\) 可消除此问题
阈值 \(p \gg dn\) 与对抗鲁棒性文献中发现的光滑插值阈值一致，暗示对抗鲁棒性与数据重构能力之间存在内在联系
在 \(\hat{n} \neq n\) 的情况下（不知道精确样本数），\(\hat{n} > n\) 时会生成正确样本+部分重复，\(\hat{n} < n\) 时会合并样本

亮点与洞察¶

优雅的相变发现：\(p = n\) 为标签记忆阈值，\(p = dn\) 为数据记忆阈值，两者的比值恰好是数据维度 \(d\)，物理直觉清晰——重构需要恢复 \(dn\) 个自由度
理论指导算法：投影损失不是凭空设计，而是理论分析自然导出的——如果 \(\theta^*\) 在特征子空间内，则重构成功。这种"理论→算法"的路径值得学习
跨架构的普适性：虽然理论仅在 RF 模型上成立，但实验表明阈值在两层网络、ResNet、ViT 上都适用，暗示最后一层的过参数化是关键

局限性 / 可改进方向¶

Theorem 2 仅证明了 \(n=2\) 的情况，\(n \geq 3\) 的排除重复证明存在组合爆炸的技术困难
理论假设激活函数需满足特定 Hermite 系数条件（ReLU 不完全满足），实际实验中 ReLU 仍然工作但有符号歧义
未证明投影损失的全局最优解一定是训练数据的排列——目前在非凸优化层面缺乏保证
对 \(n \ll p \ll dn\) 的"中间区间"信息论是否可能重构单个样本有初步讨论但未定论

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次给出数据重构的参数量相变阈值，理论贡献清晰且有深度
实验充分度: ⭐⭐⭐⭐⭐ 从合成数据到 CIFAR-10/Tiny-ImageNet，从 RF 到 ResNet/ViT，覆盖全面
写作质量: ⭐⭐⭐⭐⭐ 理论和实验结合紧密，Figure 1 的展示极具说服力，证明sketch 清晰
价值: ⭐⭐⭐⭐⭐ 对隐私和安全有重要启示——给出了"模型多大就危险"的定量刻画