跳转至

Data Reconstruction: Identifiability and Optimization with Sample Splitting

讲者: Qi Lei
会场: Recent Advances in Statistical Methods and Theory
报告题目: Data Reconstruction: Identifiability and Optimization with Sample Splitting
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述

这个方向是什么

本文研究的子方向是 从训练好的神经网络参数中重建训练数据集（dataset reconstruction）。给定一个已训练好的模型参数 \(\theta\)（无训练数据、无梯度、无中间状态），目标是恢复出训练样本 \(\{(x_i, y_i)\}_{i=1}^n\)。这是一个比成员推断（membership inference）和模型反转（model inversion）更强的隐私攻击形式，同时也为理解神经网络的记忆化行为提供了直接工具。当前该方向处于 从经验成功走向理论理解 的阶段：已有若干实证上有效的重建方法，但关于“何时重建是理论上可能的”以及“如何可靠地求解对应的非凸优化问题”仍缺乏系统理论。

发展脉络（history）

奠基工作：Haim et al. (2022) 首次展示了从训练好的二分类 MLP 参数中重建大量训练样本的可能性。他们利用隐式偏差理论（Ji & Telgarsky, 2020; Lyu & Li, 2020）——齐次网络在梯度流下收敛到最大间隔问题的 KKT 点——将重建转化为求解 KKT 方程组。该工作开启了“KKT-based reconstruction”这一子线索。

主要进展： - Buzaglo et al. (2024) 将 Haim 等人的方案扩展到多类分类、带权重衰减的训练以及更一般的损失函数（如回归损失），并观察到权重衰减反而增强可重建性。 - Loo et al. (2024) 从 NTK（Neural Tangent Kernel）视角出发，证明在无限宽极限下，若已知参数初始化，整个训练集可被 可证明地 重建。该工作给出了第一个严格的重建保证，但依赖初始化信息这一强假设。 - 平行地，梯度反转攻击（Zhu et al., 2019; Zhao et al., 2020; Geiping et al., 2020）在分布式学习场景中通过匹配梯度重建单样本，但目标不同（单样本 vs 全集）。

当前 frontier 与本文位置：现有 KKT-based 方法缺乏可识别性理论——KKT 方程可能有多解，重建成功与否依赖数据特性和超参数调优。本文填补了这一空白：对两层网络多项式激活，给出 KKT 系统唯一确定训练样本的充分条件（定理 4.1）。同时，针对重建目标的高维非凸性，提出 样本分裂（sample splitting） 算法，从优化角度改善重建质量。本文是第一个同时处理可识别性与优化两个互补问题的理论工作。

子线索聚类

  1. KKT-based reconstruction（Haim 2022, Buzaglo 2024）：利用隐式偏差，将重建转化为求解 KKT 方程组。优点是无需初始化信息，缺点是缺乏可识别性保证，且优化困难。
  2. NTK-based reconstruction（Loo 2024）：在 NTK 极限下，重建问题退化为线性逆问题，可证明重建整个训练集。缺点是需要完整的参数初始化，且实际网络往往偏离 NTK 极限。
  3. 梯度反转与成员推断（Zhu 2019, Shokri 2016, Fredrikson 2015）：目标不同（单样本或属性），但共享“从模型输出/梯度反推训练数据”的思想。本文的样本分裂算法可视为一种通用的优化增强手段，不限于 KKT 目标。

这个方向在追问的核心问题

  1. 可识别性：给定模型参数，训练数据是否被唯一确定？需要什么条件（网络结构、激活函数、宽度、训练算法）？
  2. 优化：即使理论上可识别，如何高效求解对应的非凸逆问题？现有方法常陷入平坦区域或鞍点。
  3. 近似重建：当完全重建不可能时，能否部分重建（如重建“异常值”样本）？能否给出误差界？
  4. 与记忆化的关系：哪些样本更容易被重建？是否与长尾分布、影响函数等概念对应？

当前主流方法与瓶颈：KKT-based 方法在经验上有效，但缺乏理论保证；NTK-based 方法有理论保证但假设过强。两者都面临优化困难——重建目标高度非凸，梯度下降常停滞。

⚠️ 作者的 framing（必须明确标注为作者说法）

作者将缺口 frame 成两个互补问题：“identifiability”和“optimization”（见引言 Question 1 & 2）。他们声称：“Despite encouraging empirical success, two fundamental and closely interconnected challenges remain: …” 并分别用第4节和第5节回应。作者淡化了 NTK-based 方法的竞争地位：仅在第2节提及 Loo et al. (2024) 需要“access to the full parameter initialization”，而本文的 KKT-based 方法不需要。什么明显该被引/该存在、却没出现在 intro 里？ 本文未讨论 更深网络（>2层） 或 ReLU 等非多项式激活 的可识别性——这些是更实际但更难的设定。此外，统计-计算权衡（如低度多项式障碍）未被提及，尽管张量分解本身有计算复杂度问题（见开放问题）。

张力

未见明显对立引用。各被引工作之间在结论上互补而非矛盾：Haim 等展示经验成功，Loo 等给出 NTK 极限下的理论保证，本文给出多项式激活下的可识别性条件。但注意：Loo 等声称“entire training set can be provably reconstructed”，而本文只保证“active samples”（即 \(\lambda_i>0\) 的边界样本）可恢复——两者覆盖的样本集不同，不直接冲突。

二、最核心、最简单的例子 / 数学问题

第一步：符号、模型、可观测数据交代清楚

  • 符号：
  • \(\theta \in \mathbb{R}^P\)：训练好的网络参数（可观测）。
  • \(\Phi(\theta; x) : \mathbb{R}^d \to \mathbb{R}\)：网络输出（标量，二分类）。
  • \(\{(x_i, y_i)\}_{i=1}^n\)：未知的训练样本，\(x_i \in \mathbb{R}^d\)，\(y_i \in \{\pm1\}\)。
  • \(\lambda_i \ge 0\)：KKT 乘子，对应第 \(i\) 个样本的约束 \(y_i \Phi(\theta; x_i) \ge 1\)。活跃集 \(S = \{i: \lambda_i > 0\}\)。
  • \(b_i := \lambda_i y_i\)：带符号的权重。
  • 两层网络：\(\Phi(\theta; x) = \sum_{j=1}^m a_j \sigma(w_j^\top x)\)，其中 \(a \in \mathbb{R}^m, W \in \mathbb{R}^{m \times d}\)，\(\sigma\) 为激活函数。
  • 激活函数：本文主要考虑齐次多项式 \(\sigma(t) = t^\alpha\)（\(\alpha \ge 3\)），以及通过 homogenization 推广到一般多项式。
  • 张量 \(T := \sum_{i \in S} b_i \, x_i^{\otimes \alpha}\)（\(\alpha\) 阶对称张量）。
  • 收缩映射 \(f(w) := T(\cdot, w, \dots, w) = \sum_{i \in S} b_i (x_i^\top w)^{\alpha-1} x_i\)，这是一个 \(\mathbb{R}^d \to \mathbb{R}^d\) 的齐次多项式映射（次数 \(\alpha-1\)）。
  • \(N := \binom{d+\alpha-2}{\alpha-1}\)：\(d\) 元 \(\alpha-1\) 次齐次多项式空间的维数。

  • Gram 矩阵 \(K \in \mathbb{R}^{m \times m}\)：\(K_{pq} = (W_p^\top W_q)^{\alpha-1}\)。

  • 模型：

  • 数据生成机制：训练集 \(\{(x_i, y_i)\}\) 由某个未知分布生成，网络通过梯度流（或梯度下降）在 logistic 损失下训练至收敛。由于隐式偏差，齐次网络的参数方向收敛到最大间隔问题的 KKT 点。

  • 统计模型：无显式概率模型；重建问题是一个 确定性逆问题：给定 \(\theta\)，求解满足 KKT 条件的 \(\{(x_i, y_i)\}\)。

  • 可观测数据：

  • 可观测：训练好的参数 \(\theta = (a, W)\)（以及可能的网络架构信息，如层数、激活函数）。注意：初始化 \(\theta_0\) 通常不可观测（除非 NTK 方法）。
  • 想要但观测不到：训练样本 \(x_i\)、标签 \(y_i\)、KKT 乘子 \(\lambda_i\)、活跃集 \(S\)。
  • 关键假设：网络是齐次的（或通过 homogenization 近似齐次），且训练已收敛到 KKT 点。

第二步：最小内核

最简特例：考虑一个 两层网络，激活函数为 \(\sigma(t) = t^3\)（\(\alpha=3\)），只有一个隐藏神经元（\(m=1\)）。但单个神经元无法提供足够方程——实际上需要 \(m\) 足够大使得 Gram 矩阵满秩。因此更合适的最小内核是：\(m\) 个神经元，激活 \(t^3\)，训练集只有 1 个活跃样本（\(|S|=1\)）。此时 \(T = b_1 x_1^{\otimes 3}\)，\(f(w) = b_1 (x_1^\top w)^2 x_1\)。KKT 方程给出：

\[W_j = 3 a_j f(W_j) = 3 a_j b_1 (x_1^\top W_j)^2 x_1, \quad j=1,\dots,m.\]
若 \(a_j \neq 0\)，则 \(f(W_j) = W_j / (3 a_j)\)。现在我们有 \(m\) 个向量值方程，每个方程给出 \(f\) 在点 \(W_j\) 处的值。由于 \(f\) 是二次齐次多项式映射（\(\alpha-1=2\)），其系数空间维数 \(N = \binom{d+1}{2}\)。当 \(m \ge N\) 且 Gram 矩阵 \(K_{pq} = (W_p^\top W_q)^2\) 满秩时，可以通过插值唯一确定 \(f\)，进而得到 \(T\)。然后从 \(T\) 中分解出 \(x_1\)（因为 \(T\) 是秩-1 张量，可通过幂法或特征分解恢复）。核心思路：KKT 方程提供了 \(f\) 在多个点上的值，利用多项式插值唯一确定 \(f\)，再通过张量分解恢复样本。一般情形（多个活跃样本）只是这个思路的推广：\(T\) 是秩-\(|S|\) 张量，通过构造矩阵切片并利用特征值分解可恢复每个 \(x_i\)（见定理 4.1 证明 Step 2）。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：从训练好的两层神经网络参数中重建训练数据，聚焦于两个互补问题——KKT 系统的可识别性（何时解唯一）以及重建目标的高维非凸优化。
  2. 核心工具/方法：对多项式激活（次数 \(\ge 3\)），利用多项式核插值和对称张量分解证明可识别性；提出样本分裂（sample splitting）算法，通过沿负曲率方向分裂候选样本来逃离平坦区域，改善优化。
  3. 主要结论：在 Gram 矩阵满秩条件下，活跃训练样本（\(\lambda_i>0\)）可被唯一恢复（几乎必然）；样本分裂算法收敛到近似二阶稳定点，且实验表明能提升多种现有重建方法的质量。

关键设定与假设

  • 网络结构：两层网络 \(\Phi(x) = \sum_{j=1}^m a_j \sigma(w_j^\top x)\)，激活 \(\sigma\) 为多项式（齐次或通过 homogenization 处理）。
  • 训练算法：梯度流（或梯度下降）在 logistic 损失下训练至收敛，参数方向收敛到最大间隔问题的 KKT 点（隐式偏差假设）。
  • 可识别性假设（定理 4.1）：
  • 激活次数 \(\alpha \ge 3\)。
  • 插值条件：Gram 矩阵 \(K \in \mathbb{R}^{m \times m}\) 满足 \(\text{rank}(K) = N = \binom{d+\alpha-2}{\alpha-1}\)。这要求神经元数量 \(m\) 足够大，且权重向量 \(W_j\) 处于一般位置。
  • 活跃样本 \(\{x_i\}_{i \in S}\) 线性独立，且 \(\|x_i\|=1\)（归一化）。
  • 优化假设（定理 5.1）：
  • 重建目标 \(L(x,\lambda)\) 关于 \(x\) 三阶可微，且 Hessian 和 Hessian 的 Lipschitz 常数有界（标准光滑性假设）。
  • 梯度下降步长 \(\eta_g \le 1/l\)，分裂步长 \(\eta \le \frac{3}{2}\sqrt{\epsilon/\rho}\)。
  • 相比已有文献：放宽了 Loo et al. (2024) 对初始化信息的需求；强化了 Haim et al. (2022) 的理论基础（从经验到可识别性）。

主要结果

定理 4.1（可识别性）：设 \((a, W)\) 是训练集 \(\{(x_i, y_i)\}\) 对应的 KKT 点，激活 \(\sigma(t)=t^\alpha\)，\(\alpha \ge 3\)。若 \(\text{rank}(K) = N\)，则张量 \(T = \sum_{i \in S} b_i x_i^{\otimes \alpha}\) 被 \((a, W)\) 唯一确定。进一步，若 \(\{x_i\}_{i \in S}\) 线性独立且 \(\|x_i\|=1\)，则可从 \(T\) 中恢复 \(\{(x_i, b_i)\}_{i \in S}\)（几乎必然，至多置换和缩放）。

  • 直觉：KKT 方程给出 \(f(W_j) = W_j/(\alpha a_j)\)，即 \(f\) 在 \(m\) 个点上的值。由于 \(f\) 是次数 \(\alpha-1\) 的齐次多项式映射，其系数空间维数为 \(N\)。当 Gram 矩阵满秩时，插值问题有唯一解，从而确定 \(f\)，进而确定 \(T\)。第二步利用 \(T\) 的矩阵切片 \(M(v) = \sum b_i (x_i^\top v)^{\alpha-2} x_i x_i^\top\)，通过随机投影和特征分解恢复每个 \(x_i\)。
  • 必要条件：\(m \ge N\)（神经元数至少等于多项式基的维数）。这是“moderately wide networks”的含义。
  • 解决的技术难点：从非线性 KKT 方程中提取出线性插值结构，以及从高阶张量中恢复多个分量（利用随机投影使特征值分离）。

定理 5.1（优化收敛性）：在标准光滑性假设下，样本分裂算法在 \(O(\epsilon^{-2})\) 次迭代内达到 \(\epsilon\)-二阶稳定点（\(\|\nabla_x L\| \le \epsilon\)，\(\lambda_{\min}(\nabla_x^2 L) \ge -\sqrt{\rho\epsilon}\)）。

  • 直觉：算法交替进行梯度下降（Phase I）和样本分裂（Phase II）。Phase I 保证梯度范数降到 \(\epsilon\)；Phase II 通过分裂矩阵 \(S(x_i)\) 检测负曲率，若存在 \(\lambda_{\min}(S(x_i)) < -\sqrt{\rho\epsilon}\)，则分裂可带来 \(\Omega(\eta^2 \sqrt{\rho\epsilon})\) 的损失下降。由于损失有下界，分裂次数有限。总迭代次数与维度 \(d\) 无关。
  • 技术技巧：利用分裂矩阵 \(S(x_i)\) 作为全 Hessian 负曲率的代理（引理 B.2），避免显式计算全 Hessian；分裂方向取最小特征向量，通过 Lanczos 方法近似计算。

证明路线与技术技巧

可识别性证明路线（定理 4.1）： 1. 从 KKT 到函数值：由 KKT 方程 \(W_j = \alpha a_j f(W_j)\)，当 \(a_j \neq 0\) 时得到 \(f(W_j) = W_j/(\alpha a_j)\)。这提供了 \(f\) 在 \(m\) 个点上的精确值。 2. 多项式插值唯一确定 \(f\)：将 \(f\) 表示为 \(f(w) = A \phi(w)\)，其中 \(\phi(w)\) 是次数 \(\alpha-1\) 的单项式向量。特征矩阵 \(V\) 满足 \(V_{j,:} = \phi(W_j)^\top\)，则 \(K = V V^\top\)。\(\text{rank}(K)=N\) 意味着 \(V\) 列满秩，从而线性系统 \(F = V A^\top\) 有唯一解 \(A\)。等价地，可用核形式 \(f(w) = F^\top K^\dagger k(w)\) 表达。 3. 从 \(f\) 到张量 \(T\)：定义 \(p(w) = \langle w, f(w) \rangle = \sum b_i (x_i^\top w)^\alpha = T(w,\dots,w)\)。通过极化恒等式可从 \(p\) 恢复对称多线性形式 \(T\)。 4. 从 \(T\) 恢复活跃样本：构造矩阵切片 \(M(v) = T(\cdot,\cdot,v,\dots,v) = \sum b_i (x_i^\top v)^{\alpha-2} x_i x_i^\top\)。随机选择两个向量 \(v_1, v_2\)，计算 \(A = M(v_1), B = M(v_2)\)。通过广义特征值问题 \(C = (U^\top A U)^{-1} (U^\top B U)\) 的特征分解，可恢复 \(x_i\) 的方向（至多置换和缩放）。关键在于 \(\alpha \ge 3\) 时，权重 \((x_i^\top v)^{\alpha-2}\) 随 \(v\) 变化，使得 \(C\) 的特征值几乎必然互异，从而可分离各分量。

技术技巧点名： - 多项式核插值：利用核技巧将插值问题转化为 Gram 矩阵求逆，避免显式构造高维单项式基。 - 极化恒等式：从对角形式恢复多线性形式，标准技巧。 - 随机投影 + 广义特征值：通过随机选择 \(v\) 使特征值分离，这是张量分解中常用的“whitening + 特征分解”思路。 - Lanczos 方法：实验中用于近似计算分裂矩阵的最小特征向量（附录 C.1）。

优化证明路线（定理 5.1）： 1. Phase I 梯度下降：标准下降引理，每次迭代损失下降 \(\Omega(\eta_g \epsilon^2)\)，故 \(O(\epsilon^{-2})\) 次后梯度范数 \(\le \epsilon\)。 2. Phase II 分裂：当梯度范数已小，检查每个样本的分裂矩阵 \(S(x_i)\)。若存在 \(\lambda_{\min}(S(x_i)) < -\epsilon_H\)，则沿对应特征向量方向分裂（一分为二，权重各半）。利用二阶泰勒展开（引理 B.1），分裂后损失下降 \(\Omega(\eta^2 \epsilon_H)\)。由于 \(\epsilon_H = \sqrt{\rho\epsilon}\) 且 \(\eta = O(\sqrt{\epsilon/\rho})\)，下降量为 \(\Omega(\epsilon^{3/2})\)。损失有下界，故分裂次数有限。 3. 终止条件：当所有 \(\lambda_{\min}(S(x_i)) \ge -\epsilon_H\) 时，由引理 B.2 知全 Hessian 的最小特征值 \(\ge -\epsilon_H = -\sqrt{\rho\epsilon}\)，满足二阶稳定点定义。

技术技巧： - 分裂矩阵作为曲率代理：引理 B.2 证明 \(\lambda_{\min}(\nabla_x^2 L) \ge \min_i \lambda_{\min}(S(x_i))\)，因此只需检查每个样本的 \(S(x_i)\) 即可保证全局二阶条件。 - 二阶泰勒展开的精确控制：引理 B.1 给出分裂后损失变化的显式表达式，并证明最优分裂是沿最小特征向量对称分裂（定理 B.1）。

真实例子与应用

本文在 MNIST 和 CIFAR-10 上进行了实验，使用三种重建方法（Haim 2022, Buzaglo 2024, Loo 2024）作为 baseline，对比加入样本分裂后的效果。

  • 数据：MNIST（灰度手写数字，28×28）和 CIFAR-10（彩色自然图像，32×32）。随机选取小规模训练子集（100 或 500 样本），训练一个全连接网络（架构 d-1000-1000-1）。
  • 方法：对每种 baseline，在相同初始化下运行两次：一次不加分裂，一次周期性加入分裂（每 20000-40000 步检查一次）。分裂阈值 \(\lambda^* = -0.1\)，最大分裂步长 0.01，分裂样本数上限为当前批次的 50%。
  • 结果：
  • Loo et al. (2024) 方法（100 训练样本）：CIFAR-10 上 21/25 的 top 样本 SSIM 提升；MNIST 上 21/25 的 top 样本 L2 距离下降（图 1）。全样本对比显示改善集中在基线质量较高的样本（图 2）。
  • Haim et al. (2022) 方法（500 样本）：分裂后损失下降更平稳，指标在分裂事件附近改善（图 3）。单个样本轨迹显示分裂后 SSIM 持续上升，而不分裂则下降（图 4）。
  • Buzaglo et al. (2024) 方法（多类）：类似趋势，但多类设定下优化更不稳定，分裂有时带来大幅改善（附录 C.3）。
  • 例子想说明什么：样本分裂作为一种通用优化增强手段，能帮助逃离平坦区域，提升重建质量，尤其对基线已部分成功的样本效果明显。分裂很少降低质量，是一种保守的 refinement。

本文为纯理论 + 实证例子：既有严格定理，也有真实数据实验。

🔎 结论是否比证明窄

  • 定理 4.1 只覆盖两层网络和多项式激活，但论文在实验中使用的是更深网络（d-1000-1000-1）和 ReLU 激活（通过 NTK 方法？实际上 Loo 方法使用 NTK，但 NTK 对应无限宽网络，不是两层多项式）。作者在 4.3 节通过 homogenization 将非齐次多项式激活归约到齐次情形，但 homogenization 需要强可分性假设（Assumption 2 in Cai et al. 2025），且只保证极限方向满足 KKT，实际有限宽网络可能不严格满足。论文未证明对 ReLU 或更深网络的可识别性，但实验却在这些设定下进行——这是一个 gap。
  • 定理 5.1 的收敛性分析假设重建目标为特定形式（5.1），但实验中的 NTK-based 方法（Loo 2024）的目标函数形式略有不同（\(f(\theta; x_i) = \nabla_\theta \Phi_{\theta_0}(x_i)\) 依赖于初始化 \(\theta_0\)）。论文声称“subsumes several representative reconstruction methods”，但未验证 NTK 目标是否满足 Assumption 5.1 中的三阶可微性和 Lipschitz 条件（NTK 核本身是光滑的，但 \(\nabla_\theta \Phi_{\theta_0}(x_i)\) 关于 \(x_i\) 的 Hessian 可能涉及高阶导数，需检查）。
  • 实验中的“improvement”是相对 baseline 而言，未与理论最优比较。例如，定理 4.1 保证可识别，但实验中的重建质量远未达到完美（SSIM 通常 <0.6），说明优化仍未找到全局最优，或理论假设（如 Gram 矩阵满秩）在实际中不满足。

四、开放问题（点到为止，扎根具体语句）

  1. 扩展到更深的网络和更一般的激活：本文的可识别性定理仅针对两层网络和多项式激活。作者在 Discussion 中写道：“As future work, we would like to extend the identifiability results to a robust analysis (approximate reconstruction) and partial reconstruction.” 但未提及更深网络或 ReLU。一个自然的问题是：对于深度 ReLU 网络，KKT 系统是否仍能唯一确定训练数据？ 这需要新的数学工具（ReLU 不是多项式，homogenization 不直接适用）。

  2. 近似重建与部分重建：当插值条件不满足（如 \(m < N\)）或网络宽度不足时，完全重建不可能。作者在 Discussion 中 conjecture：“when the interpolation condition is violated or even in the under-determined regime, samples associated with spectrally isolated eigenmodes of the induced tensor can be approximately reconstructed.” 这是一个具体的开放问题：刻画可重建样本的谱特征，并给出近似误差界。扎根于论文第 7 段最后一句。

  3. 样本分裂算法的理论保证在更一般目标下的验证：定理 5.1 的证明依赖于重建目标的具体形式（5.1）和光滑性假设。对于 NTK-based 方法（Loo 2024），目标函数涉及 \(\nabla_\theta \Phi_{\theta_0}(x_i)\)，其关于 \(x_i\) 的 Hessian 可能不满足 Lipschitz 条件，或分裂矩阵的代理性质（引理 B.2）不再成立。需要验证：样本分裂是否仍能保证收敛到二阶稳定点？ 扎根于第 5.1 节“subsumes several representative reconstruction methods”这一声称，但未提供理论验证。

  4. 统计-计算权衡：本文的可识别性条件（\(m \ge N\)）意味着神经元数需随维度 \(d\) 和激活次数 \(\alpha\) 多项式增长（\(N = \binom{d+\alpha-2}{\alpha-1}\)）。当 \(d\) 或 \(\alpha\) 较大时，即使理论上可识别，计算上求解张量分解可能困难（NP-hard 一般情况）。是否存在计算上高效（多项式时间）的重建算法，还是说重建本身需要指数时间？ 这与研究者的统计-计算权衡兴趣直接相关。论文未讨论此问题，但定理 4.1 的证明中使用了随机投影和特征分解，这些步骤在 \(d\) 较大时可能面临维数灾难。这是一个值得探索的方向。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论