跳转至

Minimax Private Estimation of Smooth Optimal-Transport Maps

会议: NeurIPS 2026
arXiv: 2606.04683
论文: https://arxiv.org/abs/2606.04683
领域: 优化/理论
关键词: 最优传输、差分隐私、极大极小最优速率、小波密度估计、分位数估计

一句话总结

本文针对概率分布间光滑最优传输映射的私有化估计问题，基于紧支撑小波密度估计与分位数回归机制，首次提出了在中心差分隐私与局部差分隐私下达到（近）极大极小最优收敛速率的即插即用估计框架，并严格建立了匹配的极大极小下界。

研究背景与动机

最优传输（Optimal Transport, OT）已成为现代机器学习、计算机视觉与统计推断中连接几何度量与概率分布的核心数学工具，广泛应用于跨域领域自适应、生成模型潜空间映射以及算法公平性设计等关键前沿方向。在诸多高敏感度的实际业务场景中，最优传输映射不仅是一个抽象的测度论构造，更是直接部署于个人敏感数据（例如全基因组关联分析、医疗电子病历、人脸生物特征与金融信贷行为画像）之上的数据处理引擎。因此，如何在从有限经验样本中估计源分布与目标分布之间的平滑最优传输映射时，提供具备严格数学证明的差分隐私（Differential Privacy, DP）保障，成为了现代统计学习理论与隐私计算交叉领域迫切需要攻克的理论难题。

在经典的非私有统计最优传输理论中，无结构假设的分布估计通常饱受维数灾难的困扰，而源与目标密度的 Hölder 光滑性 \(s\) 被证明是缓解维数诅咒的核心机制。近年来的前沿研究确立了光滑传输映射在 \(L^2(P_X)\) 范数下的非私有极大极小最优收敛速率为 \(\mathcal{O}(n^{-1} + n^{-\frac{2(s+1)}{2s+d}})\)。然而，一旦引入差分隐私约束，机制注入的校准随机噪声将极大加剧对环境空间维度的依赖。此前针对私有最优传输映射估计的开创性工作（Lalanne et al., ICML 2025）尝试基于半对偶位势形式与有限网格覆盖构建私有假设检验选择器，但该路径遭遇了双重根本性瓶颈：在计算层面，对高维平滑凸位势空间构建精确的 \(\varepsilon\)-覆盖集在算法复杂度上呈现指数级膨胀，完全不可行；在理论层面，其导出的隐私误差阶数为 \((n\epsilon)^{-\frac{2(s+1)}{2s+d+2}}\)，相比非私有项存在无法弥合的次优间隙，且理论框架完全无法适应分布式无信任实体的局部差分隐私（Local DP）场景。

攻克这一理论断层的根本切入点在于重构从私有边际密度到整体传输几何映射的稳定泛函链条。核心 idea：放弃对高维连续对偶位势空间的指数级覆盖搜索，转而利用正交小波基的紧支撑多尺度解耦特性分别构建源密度与目标密度的私有投影估计量，结合最优传输映射的负 Sobolev 稳定性界实现「私有密度即插即用映射估计」；在一维场景下则归约为私有多分位数估计，在中心与局部隐私模型下全面封闭极大极小最优速率间隙。

方法详解

整体框架

本文构建了一套模块化、严格满足差分隐私后处理免疫性的光滑最优传输映射估计系统。考虑紧支撑超立方体空间 \(\Omega = [0, 1]^d\) 上的两组独立样本观测序列 \(X_1, \dots, X_n \sim P_X\) 与 \(Y_1, \dots, Y_n \sim P_Y\)。在整体流程中，算法首先利用具备紧支撑特性的边界修正 Daubechies 小波基系统将连续密度逼近问题投影到多尺度系数空间；随后依据所选取的差分隐私模型（中心 DP 或局部 DP），计算全尺度小波系数向量的全局 \(\ell_1\) 敏感度上界，并向经验系数中注入校准的 Laplace 随机扰动噪声；接着对可能产生局部轻微负值的重构函数实施非负截断与全域积分归一化，得到合法的概率密度估计量 \(\hat{f}_{X, \mathrm{priv}}\) 与 \(\hat{f}_{Y, \mathrm{priv}}\)；最后，基于差分隐私的后处理性质，直接求解这两个确定性私有密度之间的最优传输映射 \(\hat{T}_{\mathrm{priv}} = \mathrm{OT\text{-}MAP}(\hat{f}_{X, \mathrm{priv}}, \hat{f}_{Y, \mathrm{priv}})\)。在具体算法落地时，下游映射通过私有密度的拒绝采样粒子化与非私有熵正则化重心投影高效逼近。针对 \(d=1\) 的特殊场景，算法设计了基于私有多分位数网格的单调阶梯插值映射。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：敏感样本观测集 X 与 Y"] --> B["边界修正小波基投影与敏感度控制<br/>多尺度小波分解与紧支撑局部覆盖分解"]
    B --> C["双模型私有小波系数扰动机制<br/>中心DP全局注入 / 局部DP单体通道扰动"]
    C --> D["密度合法化与最优传输后处理映射<br/>非负截断重归一化 + 拒绝重采样离线求解"]
    D --> E["一维私有多分位数阶梯插值估计<br/>Kaplan机制求解分位数网格并单调保序拟合"]
    E --> F["输出：差分隐私最优传输映射 T̂_priv"]

关键设计

1. 边界修正小波基投影与敏感度控制：限制高频膨胀实现紧致全局敏感度 为了在有限样本下充分捕捉 Hölder 空间 \(\mathcal{C}^s(\Omega)\) 的平滑特征，同时避免隐私噪声随基函数维数失控，估计器采用了边界修正的正交 Daubechies 小波基系统 \(\Psi = \Phi \cup \bigcup_{j=j_0}^J \Psi_j\)。在非参数隐私估计中，传统基函数（如高维傅里叶级数或多项式）在单个数据点变化时，全空间展开系数都会发生全局响应，导致敏感度随截止维度多项式甚至指数爆炸。本文系统挖掘了小波函数的紧支撑性与多尺度空间划分特质：在每一分辨率层级 \(j \geq j_0\)，包含小波函数基基元支集的超矩形族在空间任意一点的重叠覆盖次数一致受限于常数 \(C_3\)，且各基函数无穷范数严格满足 \(\sup_{\xi \in \Psi_j} \|\xi\|_\infty \leq C_4 2^{jd/2}\)。通过对尺度空间与各级小波子空间进行几何分块求和，成功证明了查询向量 \(q(z) = (\xi(z); \xi \in \Phi \cup \bigcup_{j=j_0}^J \Psi_j)\) 在替换单个样本点时的全维度 \(\ell_1\) 敏感度可严格收敛并受控于： $\(\Delta = \sup_{z, z' \in \Omega} \|q(z) - q(z')\|_1 \leq 2 C_1 C_2 + 6 C_3 C_4 2^{(J+1)d/2}.\)$ 该界证明了高维多尺度小波系数的累积敏感度仅仅取决于最大截止深度 \(J\) 的最高分辨率层级单尺度量级，从而将敏感度膨胀抑制在理论紧致界。

2. 双模型私有小波系数扰动机制：中心与局部差分隐私的统一噪声校准 在严格限定敏感度 \(\Delta\) 后，算法在中心与局部差分隐私下分别设计了最优加噪算子。在具备可信聚合器的中心 DP 模式下，中央服务器直接在经验系数向量 \(\frac{1}{n} \sum_{i=1}^n \xi(Z_i)\) 上注入尺度为 \(\frac{\Delta}{n\epsilon}\) 的独立同分布 Laplace 噪声 \(\mathcal{L}(1)\)，整体满足标准 \(\epsilon\)-DP；而在缺乏可信第三方的局部 DP 模式下，每一位分布式个体对自身私有特征向量 \(\xi(Z_i)\) 本地添加尺度为 \(\frac{\Delta}{\epsilon} \mathcal{L}(1)\) 的随机扰动后上传，中心服务器聚合求平均时利用大数定律使方差缩减为 \(\frac{\Delta^2}{n\epsilon^2}\)。定义统一隐私有效样本规模参数 \(\pi_{n,\epsilon}\)，在中心 DP 下 \(\pi_{n,\epsilon} = n\epsilon\)，在局部 DP 下 \(\pi_{n,\epsilon} = \sqrt{n}\epsilon\)。通过在负 Besov 空间 \(\mathfrak{B}_{2,1}^{-1}(\Omega)\) 中展开统计风险的三项正交分解（模型逼近偏差、样本经验方差与差分隐私噪声）： $\(\|\tilde{f}_{Z, \mathrm{priv}} - f_Z\|_{\mathfrak{B}_{2,1}^{-1}}^2 \lesssim 2^{-2J(s+1)} + \frac{1}{n} 2^{(d-2)J} + \frac{2^{Jd}}{\pi_{n,\epsilon}^2} 2^{(d-2)J},\)$ 通过变分求导得到最优空间截止尺度选择准则： $\(2^J \asymp \min\left( n^{\frac{1}{d+2s}}, (\pi_{n,\epsilon})^{\frac{1}{\max(d, 3/2)+s}} \right).\)$ 该调谐使私有密度估计量在负 Sobolev / Besov 范数下同时达到最优统计逼近界。

3. 密度合法化与最优传输后处理映射：规避位势覆盖的即插即用求解 加噪重构后的小波投影函数 \(\tilde{f}_{Z, \mathrm{priv}}\) 可能由于局部 Laplace 尾部抽样产生局部负值且全域积分不为 1。算法引入了非线性投影合法化操作：\(\hat{f}_{Z, \mathrm{priv}} = (\tilde{f}_{Z, \mathrm{priv}} \vee 0) / \int_{\Omega} (\tilde{f}_{Z, \mathrm{priv}} \vee 0)\)。由微分隐私的基本后处理性质定理（Post-Processing Property），任何对私有输出的确定性或独立随机变换均不消耗额外隐私预算。随后，结合 Balakrishnan & Manole (2025) 关于强凸 Brenier 位势关于源与目标测度的二阶稳定性理论，两概率测度间最优传输映射的均方误差可直接由边际密度的负 Besov 距离控制：\(\|\hat{T}_{\mathrm{priv}} - T\|_{L^2(P_X)}^2 \lesssim \|\hat{f}_{X, \mathrm{priv}} - f_X\|_{\mathfrak{B}_{2,1}^{-1}}^2 + \|\hat{f}_{Y, \mathrm{priv}} - f_Y\|_{\mathfrak{B}_{2,1}^{-1}}^2\)。该解耦机制彻底解放了下游计算：无需在高维光滑位势空间进行不可行的组合覆盖搜索，实践中仅需通过高效的拒绝采样从连续密度 \(\hat{f}_{X, \mathrm{priv}}\) 与 \(\hat{f}_{Y, \mathrm{priv}}\) 中抽取合成粒子点云，并调用现成的非私有熵正则化重心投影求解器（Pooladian & Niles-Weed, 2021），首次将私有传输映射算法推进至可实际运行的算法范畴。

4. 一维私有多分位数阶梯插值估计：降维破局的最优分位数逼近 在空间维度 \(d=1\) 下，基于负 Besov 范数的小波即插即用上界推导受到嵌入维数常数限制，出现额外的 \(1/2\) 阶速率损失。为了解决这一一维退化，本文基于一维最优传输映射与累积分布函数（CDF）的紧密解析解 \(T(x) = F_{f_Y}^{-1}(F_{f_X}(x))\)，提出了一种独立的分位数规约机制。设定均匀分位数网格 \(\mathbf{p} = (1/m, 2/m, \dots, (m-1)/m)\)，调用具备近最优效用保证的 Kaplan et al. (2022) 私有多分位数机制，分别从敏感样本中以中心差分隐私方式提取保序分位数向量 \(\mathbf{q}_X\) 与 \(\mathbf{q}_Y\)。进而构造一维阶梯分段插值估计器： $\(\hat{T}(x) = \begin{cases} \mathbf{q}_Y[1], & x \in [0, \mathbf{q}_X[1]], \\ \mathbf{q}_Y[k], & x \in (\mathbf{q}_X[k-1], \mathbf{q}_X[k]], \quad 2 \leq k \leq m-1, \\ 1, & x \in (\mathbf{q}_X[m-1], 1]. \end{cases}\)$ 当满足常规非退化隐私预算假设 \(\epsilon = \Omega(n^{-1+\gamma})\) 时，通过自适应调谐网格密度 \(m \asymp \min(n^{1/2}, (n\epsilon)^{1/2})\)，该估计器在中心 DP 下取得了对数因子意义下的纯参数化极限速率 \(\mathrm{PolyLog}(n,\epsilon) \cdot \max(n^{-1}, n^{-2}\epsilon^{-2})\)，完美弥补了小波方法在一维的理论空缺。

实验关键数据

主实验

为了精确量化最优传输映射估计的均方误差（Mean Squared Error, MSE），实验在具备解析解闭式最优传输映射 \(T_0\) 的合成基准上进行（如二维与三维立方体上的均匀分布到均匀分布单调线性映射）。将本文提出的私有小波即插即用估计量（Private Wavelet OT）与两种非私有基准进行横向对比：基于经验样本重心投影的朴素非私有 OT 基线（OT baseline）以及非私有熵正则化最优传输基线（EOT baseline）。在不同样本量 \(n \in [10^2, 10^5]\) 与中心隐私预算 \(\epsilon \in \{0.5, 1.0, 2.0\}\) 下展开评测，每组配置基于 5 次独立随机实验取均值。

实验设置 (\(N=2, J=2\)) 评估指标 本文私有小波 OT (\(\epsilon=2.0\)) 本文私有小波 OT (\(\epsilon=0.5\)) 非私有 EOT 基线 非私有经验 OT 基线 理论预测最优速率
\(d=2\) (unif-unif), \(n=10^4\) MSE (\(\downarrow\)) \(1.8 \times 10^{-3}\) \(4.2 \times 10^{-3}\) \(1.2 \times 10^{-3}\) \(2.5 \times 10^{-3}\) \(\tilde{\mathcal{O}}(n^{-1} + (n\epsilon)^{-\frac{2(s+1)}{s+2}})\)
\(d=2\) (unif-unif), \(n=5 \times 10^4\) MSE (\(\downarrow\)) \(3.5 \times 10^{-4}\) \(8.9 \times 10^{-4}\) \(2.1 \times 10^{-4}\) \(1.1 \times 10^{-3}\) \(\tilde{\mathcal{O}}(n^{-1} + (n\epsilon)^{-\frac{2(s+1)}{s+2}})\)
\(d=3\) (unif-unif), \(n=10^4\) MSE (\(\downarrow\)) \(6.2 \times 10^{-3}\) \(1.6 \times 10^{-2}\) \(3.1 \times 10^{-3}\) \(7.8 \times 10^{-3}\) \(\mathcal{O}(n^{-\frac{2(s+1)}{2s+3}} + (n\epsilon)^{-\frac{2(s+1)}{s+3}})\)
\(d=3\) (unif-unif), \(n=5 \times 10^4\) MSE (\(\downarrow\)) \(1.5 \times 10^{-3}\) \(3.9 \times 10^{-3}\) \(7.5 \times 10^{-4}\) \(3.2 \times 10^{-3}\) \(\mathcal{O}(n^{-\frac{2(s+1)}{2s+3}} + (n\epsilon)^{-\frac{2(s+1)}{s+3}})\)

消融实验

表 2 评估了小波多尺度截断深度 \(J\) 对私有估计总误差中「平滑逼近截断偏差」与「高频差分隐私噪声放大」的动态消融平衡（固定 \(d=2, \epsilon=1.0\)）。

小波分解深度配置 估计误差 MSE (\(n=10^3\)) 估计误差 MSE (\(n=10^4\)) 估计误差 MSE (\(n=10^5\)) 现象与机理说明
欠分解配置 (\(J=1\)) \(1.85 \times 10^{-2}\) \(8.20 \times 10^{-3}\) \(7.10 \times 10^{-3}\) 隐私噪声较小但高频逼近偏差受阻，大样本下误差迅速饱和
理论最优配置 (\(J=2\)) \(9.40 \times 10^{-3}\) \(2.60 \times 10^{-3}\) \(4.80 \times 10^{-4}\) 完美平衡样本方差、多尺度截断偏差与 Laplace 隐私噪声
过分解配置 (\(J=3\)) \(3.40 \times 10^{-2}\) \(6.80 \times 10^{-3}\) \(7.90 \times 10^{-4}\) 敏感度 \(\Delta \propto 2^{J d/2}\) 膨胀导致强隐私噪声恶化

关键发现

  • 光滑性先验驱动的大样本超越：在小样本阶段，差分隐私机制注入的 Laplace 噪声对几何映射估计产生明显的效用损失；但随着样本规模 \(n\) 持续增加，利用小波平滑性先验的私有估计器展现出显著快于经验 OT 的收敛斜率（在 log-log 图上表现为更陡的下降线）。在 \(d=2\) 且 \(n \ge 5 \times 10^4\) 时，充分利用光滑性的小波私有估计量甚至超越了完全没有隐私噪声干扰的朴素经验 OT 基线。
  • 维度阶跃（Dimension Jump）现象：在经典非私有设置下，最优传输映射估计在 \(d=1\) 与 \(d=2\) 均保持纯参数化收敛速度 \(\mathcal{O}(1/n)\)，只有当 \(d \geq 3\) 时才退化至非参数速率；而在差分隐私约束下，私有参数化速率 \(\mathcal{O}(n^{-1} + n^{-2}\epsilon^{-2})\) 在 \(d=2\) 时即宣告失效，立即跌落至维数相关的代数收敛区间 \(\mathcal{O}((n\epsilon)^{-\frac{2(s+1)}{s+2}})\)。这表明隐私机制使得维数灾难的临界点整整提前了一个维度。

亮点与洞察

  • 消除了长久存在的极大极小理论间隙：推导建立了私有光滑最优传输映射的下界，证明了当 \(d \ge 3\) 时上界完全匹配下界，当 \(d=2\) 时在对数因子意义下匹配，消除了前人工作中由于半对偶有限网格覆盖引发的次优阶数，首次在信息论层面彻底定解了该问题的极大极小复杂度。
  • 解耦架构打破计算坚冰：通过将最优传输映射估计规约为独立边际密度的多尺度小波滤波与后处理重采样求解，从数学底层规避了传统方法对无穷维凸势函数空间进行指数覆盖搜索的计算死锁，给出了首个在算法层面实际可解的数值方案。
  • 隐私免费临界相变区间的严格刻画：精确锁定了决定「隐私是否免费」的临界信噪比预算边界 \(\epsilon \asymp n^{-\frac{s}{2s+d}}\)。当光滑度 \(s\) 较高时，该阈值急剧向小 \(\epsilon\) 移动，揭示了数据分布的平滑先验是抵御差分隐私扰动最强有力的天然屏障。
  • 跨隐私模型的统一分析范式：通过提炼特征参数 \(\pi_{n,\epsilon}\)，将中心差分隐私与局部差分隐私的分析框架无缝统一，证明了局部隐私对样本量的有效损耗本质上等价于有效样本从 \(n\) 下降至 \(\sqrt{n}\)，为后续非参数私有几何统计算法提供了标准分析模板。

局限与展望

  • 拒绝采样的维数瓶颈：现阶段数值实现中，从私有小波代理密度抽取合成粒子依靠拒绝采样法。随着空间维度 \(d\) 进一步升高，高维超立方体中的接受概率呈指数级坍缩，限制了算法向极高维感知特征空间的拓展。
  • 一维局部差分隐私的理论留白：在局部差分隐私（LDP）下，当 \(d=1\) 时本方法推导的上界为 \((\sqrt{n}\epsilon)^{-\frac{2(s+1)}{s+3/2}}\)，与下界 \((\sqrt{n}\epsilon)^{-\frac{2(s+1)}{s+1}}\) 仍存在 \(1/2\) 阶的差距，未来需依赖局部私有多分位数估计技术的进一步突破。
  • 严格正密度与强凸位势的强假设限制：当前理论分析建立在密度严格远离零以及最优传输势函数的 Hessian 矩阵一致有界等正则性条件之上，未能覆盖带有退化低维流形支撑或边界不规则的分布场景。
  • 离散网格超参数调优的经验依赖：小波最大深度 \(J\) 的选取依赖于底层密度的真实 Hölder 光滑度 \(s\)，而在完全隐私保护的黑盒场景下，自适应且私有地估计未知光滑度参数 \(s\) 仍是一个极具挑战的开放性统计问题。

相关工作与启发

  • vs Lalanne et al. (2025)：后者基于半对偶形式与候选位势的有限覆盖搜索，仅支持中心 DP，隐私收敛速率为 \((n\epsilon)^{-\frac{2(s+1)}{2s+d+2}}\) 存在系统性次优间隙，且算力上完全不可运行；本文基于小波密度即插即用框架，同时覆盖中心与局部 DP，达到近最优收敛速率并给出了实际数值实现。
  • vs Hütter & Rigollet (2021) / Manole et al. (2024)：奠定了非私有统计最优传输的光滑性收敛框架；本文通过构建具有严格支撑重叠界的小波分析技术，将确定性稳定性界延拓至差分隐私统计物理极限，揭示了差分隐私诱发的维度阶跃现象。
  • vs Pooladian & Niles-Weed (2021)：提出了非私有熵正则化重心投影经验估计量；本文将其作为后处理求解器，与私有密度代理紧密配合，验证了后处理隐私不变性在连接现代连续算法与隐私保护中的关键工程价值。

评分

  • 新颖性: ⭐⭐⭐⭐⭐ 首次建立私有光滑最优传输映射估计的（近）极大极小最优速率并给出匹配下界。
  • 实验充分度: ⭐⭐⭐⭐☆ 理论推导极其完备，合成基准数值曲线充分印证了渐近斜率与维数跳跃；受限于拒绝采样未展开极高维实测。
  • 写作质量: ⭐⭐⭐⭐⭐ 概念铺垫清晰，误差分解与小波敏感度控制逻辑层层递进，数学表达极为严谨。
  • 价值: ⭐⭐⭐⭐⭐ 为差分隐私下的现代几何数据分析提供了坚实的理论基石与可落地的算法范式。

相关论文