技术摘要：切比雪夫矩匹配的更紧界及其应用

问题陈述

本文解决了在给定矩的含噪测量值下，近似恢复支撑在 $[-1, 1]$ 上的概率分布 $p$ 这一基本问题。尽管矩匹配在统计学和数值线性代数中作为核心工具已有一百多年的历史，但标准矩匹配（使用幂次 $x^i$）以病态著称。具体而言，若要实现 $O(1/k)$ 的 Wasserstein-1 误差，标准矩必须以指数级小的误差 $O(1/2^k)$ 进行估计，这使得该方法在含噪场景下不切实际。

切比雪夫矩匹配利用形式为 $\mathbb{E}[T_j(x)]$ 的矩（其中 $T_j$ 为切比雪夫多项式），提供了更好的条件数。然而，先前的工作表明，若要实现 $O(1/k)$ 的 Wasserstein 误差，前 $k$ 个切比雪夫矩仍需要大致为 $O(1/k)$ 的一致估计误差。作者指出了这些理论界与特定应用（例如，差分隐私合成数据）中替代方法的性能之间的差距，这表明切比雪夫矩误差与分布恢复误差之间的关系可能显著更紧。

方法论

本文方法论的核心是对连接切比雪夫矩差异与 Wasserstein 距离的误差分析进行理论细化。证明依赖于逼近论中的两个主要组成部分：

1. 构造性 Jackson 定理：作者利用“阻尼”截断切比雪夫级数来逼近任意 Lipschitz 函数 $f$。与在误差界中产生 $\log k$ 因子的标准截断不同，阻尼级数（将系数乘以因子 $b_j \in [0, 1]$）实现了 $O(1/k)$ 的逼近误差，且无对数惩罚。
2. 全局系数衰减界：作者证明了关于 Lipschitz 函数切比雪夫系数衰减的一个新颖且更强的界。虽然众所周知，Lipschitz 函数的第 $j$ 个系数 $c_j$ 满足 $|c_j| = O(1/j)$（一种“局部”界），但作者证明了一个“全局”界：$\sum_{j=1}^\infty j^2 c_j^2 = O(1)$。这意味着系数不能同时饱和局部 $O(1/j)$ 界；相反，在加权 $\ell_2$ 意义上，它们的平均衰减必须更快。

通过将上述工具与 Kantorovich-Rubinstein 对偶性（将 Wasserstein-1 距离刻画为 1-Lipschitz 函数期望的上确界）相结合，作者推导出了基于切比雪夫矩差异的加权 $\ell_2$ 范数的两个分布 $p$ 和 $q$ 之间 Wasserstein 距离的新界。

主要贡献与结果

1. 理论主要结果（定理 1）

本文证明，如果分布 $p$ 和 $q$ 的前 $k$ 个切比雪夫矩满足加权误差界：
$$\sum_{j=1}^k \frac{1}{j^2} \left( \mathbb{E}_{x \sim p}[T_j(x)] - \mathbb{E}_{x \sim q}[T_j(x)] \right)^2 \le \Gamma^2$$
则 Wasserstein-1 距离被限制为：
$$W_1(p, q) \le O\left(\frac{1}{k} + \Gamma\right)$$
这比先前的结果（例如 [BKM22]）有了显著改进，后者要求每一个矩 $j \in \{1, \dots, k\}$ 的误差均为 $O(1/k)$ 才能保证相同的 Wasserstein 界。新结果允许高阶矩具有更大的误差（随 $\sqrt{j}$ 缩放），同时保持相同的整体恢复精度。

2. 在差分隐私合成数据中的应用

作者将其界应用于生成差分隐私合成数据的问题。

• 结果：他们提出了一种算法，给定包含 $n$ 个点的数据集，返回一个期望 Wasserstein-1 误差为 $\tilde{O}(1/n)$ 的分布 $q$。
• 意义：这达到了最优速率（在对数因子范围内），与 Boedihardjo 等人 [BSV24] 复杂的“超正则随机游走”方法相当，但通过更简单的“选择、测量、投影”框架实现，该框架在矩上使用标准高斯噪声。这改进了先前切比雪夫矩匹配方法的 $\tilde{O}(1/n^{1/3})$ 界。
• 实证验证：在真实世界数据集（如收入、住房、健康指标）上的实验证实，Wasserstein 误差按理论预测的比例缩放。

3. 在谱密度估计 (SDE) 中的应用

本文解决了利用矩阵 - 向量乘积估计对称 $n \times n$ 矩阵 $A$ 的谱密度的问题。

• 结果：提供了一种算法，使用 $\tilde{O}(1/\epsilon)$ 次矩阵 - 向量乘积输出分布 $q$，使得 $W_1(p, q) \le \epsilon \|A\|_2$。
• 意义：先前的方法需要对 $1/\epsilon$ 的多项式依赖，这对于较小的 $n$ 而言并非最优。新界消除了这种依赖，表明对于任意 $n$，$\tilde{O}(1/\epsilon)$ 次乘积已足够。这基本上解决了矩阵 - 向量查询模型中 SDE 问题的复杂度，在对数因子范围内与已知下界相匹配。

4. 在参数群体学习中的应用

作者分析了“参数群体”问题（从含噪观测中估计硬币偏好的分布）的最大似然估计量 (MLE)。

• 结果：通过将他们的全局系数衰减界直接应用于先前工作 [VKVK19] 中使用的 Bernstein 多项式分析，他们扩展了 MLE 实现 $O(1/\sqrt{t} \log N)$ 误差的“中等样本”区域。样本范围 $t$ 从 $O(N^{2/9})$ 扩展到了 $O(N^{1/4})$。
• 意义：这收紧了对 MLE 性能的理论理解。作者指出，将他们的改进与 [VKVK19] 中的一个猜想相结合，可能会将其扩展到 $O(N^{1-\epsilon})$，这将是本质上最优的。

5. 扩展到更高维度

本文将主要定理和全局衰减界扩展到了 $d > 1$ 维的分布。

• 结果：他们证明了多元版本的全局切比雪夫系数衰减界以及相应的 Wasserstein 误差界。
• 应用：这产生了一种用于 $d$ 维差分隐私合成数据的算法，其期望误差为 $\tilde{O}((1/n)^{1/d})$，在对数因子范围内与先前工作相匹配。

意义与声明

本文声称其主要贡献是关于切比雪夫矩匹配所需精度的更紧理论界。通过利用 Lipschitz 函数切比雪夫系数的全局衰减性质，作者证明了分布恢复对高阶矩中的噪声比之前理解的更具鲁棒性。

作者指出，这一理论改进立即转化为：

1. 更简单的算法：无需复杂的随机游走构造即可实现私有合成数据的最优速率。
2. 更快的线性代数：通过减少所需的矩阵 - 向量乘积数量来加速谱密度估计。
3. 更紧的统计分析：细化了群体学习问题中最优估计的参数区域。

本文在界中的常数方面保持了适度的语气，指出虽然他们证明了特定的常数（例如 36），但数值证据表明这些常数可以得到改进（例如到 $2\pi$）。此外，作者承认，虽然他们的方法改进了对 $n$ 和 $\epsilon$ 的依赖关系，但这些问题的基本下界（例如 $\Omega(1/\epsilon)$ 次矩阵 - 向量乘积）保持不变，且他们的结果在对数因子范围内是最优的。