跳转至

Sharp proper estimation of fixed-component Gaussian location mixtures in polynomial time

作者: Hengzhi He, Guang Cheng
主题: 高维统计 / 随机矩阵
相关性: 9/10
链接: https://arxiv.org/abs/2608.12701

一、领域脉络与小综述

这个方向是什么

这个子方向研究的是高维高斯混合模型的估计问题，具体设定为：成分数 \(k\) 固定，每个成分的协方差矩阵为单位阵 \(I_d\)，均值位于半径为 \(R\) 的球内，且不要求成分之间的分离条件或最小权重。核心目标是估计混合分布本身（而非参数），度量采用 Hellinger 距离。该问题的根本张力在于：统计上，minimax 最优率是 \(\sqrt{d/n}\)（当 \(d \ll n\) 时），但构造一个多项式时间内达到该率的proper（输出本身是混合模型）估计器，在 \(k \ge 3\) 时长期是开放问题。该方向处于高维统计与计算复杂性的交叉点，其成熟度表现为：统计最优率已被完全刻画，但计算可行性与统计最优性之间的 gap 是当前的核心 frontier。

发展脉络

  1. 奠基工作：统计最优率的刻画与次优算法。Doss et al. (2023) 是该方向的里程碑。他们证明了在 Hellinger 距离下，minimax 率为 \(\Theta(\sqrt{d/n})\)，并构造了一个多项式时间估计器。然而，该估计器仅达到较慢的 \((d/n)^{1/4}\) 率。他们为 \(k=2\) 的特殊情况给出了一个达到最优率的有效算法，但 \(k \ge 3\) 的情况被明确留作开放问题。留下的口子：多项式时间与统计最优率之间的 gap 是 \( (d/n)^{1/4} \) vs \( \sqrt{d/n} \)，即一个平方根的差距。

  2. 主要进展：更一般设定下的算法与下界。后续工作在更广泛的设定下推进了边界。

    • Bakshi et al. (2022) 处理了更一般的问题：在存在任意常数比例异常值的情况下，鲁棒地学习具有任意成分协方差的高斯混合。他们使用 SOS 方法和张量分解，但样本复杂度为 \(d^{O(k)} \text{poly}_k(1/\varepsilon)\)，远高于本文关注的 \(d/\varepsilon^2\) 尺度。留下的口子：他们的方法在球形位置混合的特定设定下，样本复杂度不是最优的。
    • Diakonikolas and Kane (2025) 提出了一个多项式时间的递归伪投影和隐式高阶矩方法，用于有界球形高斯混合。但他们的输出是一个 improper 的压缩多项式/采样预言机，且样本复杂度是通用的多项式，而非本文追求的 sharp \(d/\varepsilon^2\)。留下的口子：他们的方法在密度估计的样本效率上不是最优的，且输出不是 proper 的。
    • Fan and Li (2023) 给出了无分离条件下的高效稀疏矩恢复算法，并应用于已知公共协方差的高斯混合，但保证是在运输距离下，而非 Hellinger 距离下的 sharp 率。留下的口子：他们的矩到参数的转换不产生本文所需的 uniform Hellinger 保证。

  3. 当前 Frontier：弥合计算-统计 gap。本文（He & Cheng）直接解决了 Doss et al. (2023) 留下的开放问题：对于任意固定的 \(k \ge 3\)，构造一个多项式时间内的 proper 估计器，达到 minimax 最优的 Hellinger 率 \(\sqrt{d/n}\)。本文的位置：它填补了统计最优率与已知多项式时间算法所能达到的率之间的 gap，是该子方向的一个关键进展。

子线索聚类

这些被引文献大致落在三条子线索上：

  1. 基于矩的方法（Moment Methods）：这是最核心的线索。Doss et al. (2023) 是代表，他们利用混合分布的矩张量的低秩结构进行估计。本文也属于此线索，但通过“矩-纤维范围查找器”这一新工具，更精细地利用了矩信息。Diakonikolas and Kane (2025) 和 Fan and Li (2023) 也属于此类，但分别侧重于隐式矩计算和稀疏矩恢复。
  2. 基于 SOS（Sum-of-Squares）的方法：Bakshi et al. (2022) 是代表。这类方法通常能处理更一般的设定（如鲁棒性、任意协方差），但往往以更高的样本复杂度或更复杂的算法为代价。本文的路线刻意回避了 SOS 框架，以追求在特定设定下的最优样本效率。
  3. 基于扩散模型/得分匹配的方法：Chen et al. (2025) 是代表。这类方法通过将分布学习转化为得分匹配任务，可以处理无分离条件的混合模型，但样本复杂度是 \(d^{\text{poly}(k/\varepsilon)}\)，远非最优。本文的路线与之不同，直接基于矩结构。

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

  1. 能否在多项式时间内达到统计最优率？ 对于固定成分数 \(k\) 的高斯位置混合，这是最核心的问题。Doss et al. (2023) 证明了最优率，但算法是次优的。本文回答了“是”。
  2. 如何绕过计算障碍？ 直接估计高阶矩张量（\(O(d^\ell)\) 复杂度）在计算上不可行。核心挑战是设计一个算法，其复杂度是 \(d\) 和 \(n\) 的多项式，同时不损失统计效率。本文的答案是通过“矩-纤维”方法，只估计有限个向量值统计量。
  3. Proper 学习 vs. Improper 学习？ 输出一个 proper 的混合模型（而非密度近似或采样预言机）是否可行？本文给出了肯定的答案，而 Diakonikolas and Kane (2025) 的输出是 improper 的。
  4. 已知瓶颈：对于仅使用二次型草图（quadratic sketches）的方法，存在一个局部的四阶根障碍（见本文 Proposition 3），这解释了为什么 Doss et al. (2023) 的原始算法只能达到 \((d/n)^{1/4}\) 率。

⚠️ 作者的 framing

  • 作者的缺口 frame：作者将缺口 frame 为“Doss et al. (2023) 证明了最优率并给出了一个次优的多项式时间算法，但达到最优率的多项式时间算法对于 \(k \ge 3\) 是开放的”。本文通过引入“矩-纤维范围查找器”解决了这个问题，从而将自己定位为“显然的下一步”。
  • 被淡化/回避的竞争路线：作者明确将 Bakshi et al. (2022) 和 Diakonikolas and Kane (2025) 的工作定位为“更一般但样本复杂度非最优”或“输出 improper”。这淡化了这些工作在更广泛设定下的价值，而将本文的贡献聚焦于“sharp proper learning in polynomial time”这一特定但重要的目标。作者也回避了与 SOS 方法的直接比较，因为 SOS 方法通常能处理更复杂的协方差结构，但本文的设定是单位协方差。
  • 什么明显该被引/该存在、却没出现在 intro 里？ 这是一个值得研究者去查的问题。例如，是否有关于“计算-统计 gap”的综述性工作（如 Kunal Talwar 或 Boaz Barak 的相关文章）？是否有关于“低度多项式障碍”（low-degree polynomial barrier）在混合模型上的应用？这些可能为理解本文的“四阶根障碍”提供更广阔的视角。此外，关于“矩方法”在混合模型中的更早期工作（如 Pearson 1894 年的经典论文）可能被省略了，但这是历史背景，不一定是 gap。

张力

未见明显对立引用。所有被引工作都在各自的设定下成立，彼此之间没有直接矛盾。本文的工作可以被视为在更窄的设定下（单位协方差、固定 \(k\)）取得了比更一般方法更优的结果，这是一种“trade-off”而非“矛盾”。

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

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

  • 符号：

    • \(X\)：可观测的随机向量，\(X \in \mathbb{R}^d\)。
    • \(U\)：潜在（latent）的随机向量，代表混合成分的均值，\(U \in \mathbb{R}^d\)。它是不可观测的。
    • \(Z\)：独立于 \(U\) 的噪声，\(Z \sim N(0, I_d)\)。
    • \(\Gamma\)：混合分布（mixing distribution），是 \(U\) 的分布。它是一个离散分布，\(\Gamma = \sum_{j=1}^s w_j \delta_{\mu_j}\)，其中 \(s \le k\)，\(w_j \ge 0, \sum w_j = 1\)，\(\|\mu_j\| \le R\)。这是要估计的对象。
    • \(P_\Gamma\)：可观测数据 \(X\) 的分布，\(P_\Gamma = \Gamma * N(0, I_d)\)。即 \(X = U + Z\) 的分布。
    • \(k\)：混合成分数的上界（固定常数）。
    • \(d\)：数据维度。
    • \(n\)：样本量。
    • \(R\)：均值向量的范数上界（固定常数）。
    • \(H(P, Q)\)：Hellinger 距离，\(H^2(P, Q) = \int (\sqrt{p} - \sqrt{q})^2\)。
    • \(M_\ell(\Gamma)\)：混合分布 \(\Gamma\) 的 \(\ell\) 阶矩张量，\(M_\ell(\Gamma) = \mathbb{E}_\Gamma[U^{\otimes \ell}]\)。
    • \(H_\ell(x)\)：\(\ell\) 阶 Hermite 张量（Hermite tensor）。关键性质：\(\mathbb{E}[H_\ell(U+Z)] = U^{\otimes \ell}\)，因此 \(\mathbb{E}[H_\ell(X)] = M_\ell(\Gamma)\)。
    • \(Y_{\ell, q}(x) = H_\ell(x) \lrcorner q\)：一自由指标统计量（one-free-index statistic），其中 \(q\) 是一个 \(\ell-1\) 阶对称张量。这是一个向量值函数，\(\mathbb{E}[Y_{\ell, q}(X)] = M_\ell(\Gamma) \lrcorner q\)。
    • \(P_A\)：到子空间 \(A\) 的正交投影算子。
    • \(B\)：一个 \(d \times m\) 的矩阵，其列构成子空间 \(H\) 的标准正交基。

  • 模型：

    • 数据生成机制：\(X = U + Z\)，其中 \(U \sim \Gamma\)（一个至多 \(k\) 个原子的离散分布，均值范数 \(\le R\)），\(Z \sim N(0, I_d)\) 且独立于 \(U\)。
    • 统计模型：所有形如 \(P_\Gamma = \Gamma * N(0, I_d)\) 的分布，其中 \(\Gamma\) 是支撑在 \(\mathbb{R}^d\) 中半径为 \(R\) 的球内、至多 \(k\) 个原子的概率分布。
    • 已知量：\(k, R\)。协方差 \(I_d\) 已知。
    • 要估的对象：混合分布 \(\Gamma\)（或等价地，其密度 \(P_\Gamma\)）。

  • 可观测数据：

    • 研究者能观测到的是 \(n\) 个 i.i.d. 样本 \(\{X_i\}_{i=1}^n\)，每个 \(X_i \in \mathbb{R}^d\)。
    • 不可观测的是每个样本对应的潜在变量 \(U_i\)（即它来自哪个成分）以及混合分布 \(\Gamma\) 本身。所有关于 \(\Gamma\) 的信息都必须通过 \(X_i\) 的分布来推断。

第二步：讲最小内核

本文的核心思路可以浓缩为以下问题：如何仅通过观测 \(X\)，在多项式时间内，找到一个低维子空间 \(H\)，使得混合分布 \(\Gamma\) 的所有矩张量 \(M_\ell(\Gamma)\) 在投影到 \(H^{\otimes \ell}\) 上时，损失的信息量被控制在 \(\sqrt{d/n}\) 量级？

最简特例：\(k=2\) 且 \(d\) 很大。

在这个特例下，混合分布 \(\Gamma\) 由两个均值 \(\mu_1, \mu_2\) 和权重 \(w_1, w_2\) 决定。其支撑集是二维的（由 \(\mu_1\) 和 \(\mu_2\) 张成）。Doss et al. (2023) 已经解决了这个特例。

最小内核（针对 \(k \ge 3\) 的一般情况）：

  1. 粗范围（Coarse Range）：首先，利用二阶矩 \(\mathbb{E}[XX^\top] = M_2(\Gamma) + I_d\)。由于 \(M_2(\Gamma) = \sum w_j \mu_j \mu_j^\top\) 的秩至多为 \(k\)，其 top-\(k\) 特征空间 \(A\) 包含了均值向量张成的子空间的大部分能量。然而，由于样本量有限，估计的 \(\hat{M}_2\) 有误差 \(\zeta \approx \sqrt{d/n}\)。这导致投影到 \(A\) 后，丢失的能量 \(\rho = \mathbb{E}\|(I-P_A)U\|^2\) 的量级也是 \(\sqrt{d/n}\)。问题：如果只用 \(A\)，丢失的能量会导致 Hellinger 距离的误差为 \(\rho^{1/2} \approx (d/n)^{1/4}\)，这就是 Doss et al. (2023) 的次优率。

  2. 纤维范围增强（Fiber Range Augmentation）：为了达到 \(\sqrt{d/n}\) 率，需要恢复那些被 \(A\) 丢失的方向。关键洞察是：丢失的能量 \(\rho\) 虽然小，但它是二阶的。而混合分布的更高阶矩（如三阶矩）包含了关于这些丢失方向的一阶信息。具体来说，考虑一个与 \(A\) 正交的方向 \(v\)。三阶矩 \(M_3(\Gamma)\) 在方向 \(v\) 上的信息，可以通过“纤维”（fiber）\(M_3(\Gamma) \lrcorner q\) 来捕捉，其中 \(q\) 是一个在 \(A\) 中的二阶张量。这个纤维是一个 \(d\) 维向量，其分量在 \(v\) 方向上的投影正比于 \(\mathbb{E}[\langle U, v \rangle \langle U, q \rangle]\)。由于 \(q\) 在 \(A\) 中，\(\langle U, q \rangle\) 是已知的（在 \(A\) 内），而 \(\langle U, v \rangle\) 正是我们想要恢复的丢失方向。因此，通过估计有限个这样的纤维（对应不同的 \(q\)），我们可以“看到”丢失的方向 \(v\)。

  3. 核心引理（Lemma 1）：本文的核心技术贡献是证明了，如果子空间 \(H\) 包含了 \(A\) 以及所有估计出的纤维 \(\hat{g}_{s,j}\)，那么对于任意 \(\ell\)，矩张量 \(M_\ell(\Gamma)\) 在投影到 \(H^{\otimes \ell}\) 时的误差可以被分解为两部分：

    • 一阶误差：由纤维估计误差 \(e_s\) 控制，量级为 \(\sqrt{d/n}\)。
    • 二阶误差：由丢失能量 \(\rho\) 控制，量级为 \(\sqrt{d/n}\)。 由于 \(\rho\) 本身已经是 \(\sqrt{d/n}\) 量级，二阶误差的贡献是 \((\sqrt{d/n})^2 = d/n\)，可以忽略。因此，总误差被控制在 \(\sqrt{d/n}\) 量级。

一句话总结：本文的核心想法是，通过估计有限个“一自由指标 Hermite 收缩”（即纤维），将粗子空间 \(A\) 扩展为一个稍大的子空间 \(H\)，使得所有矩张量在 \(H\) 上的投影误差从 \((d/n)^{1/4}\) 降低到 \(\sqrt{d/n}\)。这个子空间 \(H\) 的维度仅依赖于 \(k\)，与 \(d\) 无关，从而使得后续的常维空间穷举搜索成为可能。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：对于成分数 \(k\) 固定、协方差为单位阵、均值位于有界球内的高斯位置混合模型，在无分离条件下，构造一个多项式时间内的 proper 估计器，使其 Hellinger 风险达到 minimax 最优率 \(\sqrt{d/n}\)。
  2. 核心工具/方法：提出了“矩-纤维范围查找器”（moment-fiber range finder），该工具利用二阶矩子空间和有限个一自由指标 Hermite 收缩（向量值统计量）来构建一个低维子空间，使得混合分布的所有矩张量在该子空间上的投影损失被控制在最优率。
  3. 主要结论：对于任意固定的 \(k\) 和 \(R\)，存在一个样本分割的估计器，其期望 Hellinger 风险为 \(O(\sqrt{d/n})\)，且存在一个依赖于置信水平的估计器，其尾风险为 \(O(\sqrt{(d + \log(1/\delta))/n})\)。两个估计器均在多项式算术时间内可计算。

关键设定与假设

  • 设定：模型如 (1.1) 所示，\(X = U + Z\)，\(Z \sim N(0, I_d)\)，\(U \sim \Gamma\)，\(\Gamma\) 支撑在至多 \(k\) 个点上，且 \(\|\mu_j\| \le R\)。
  • 假设：
    • 固定 \(k\) 和 \(R\)：这是核心假设，算法的多项式复杂度依赖于 \(k\) 为常数。如果 \(k\) 随 \(n\) 增长，算法复杂度会爆炸。
    • 单位协方差 \(I_d\)：这是一个很强的假设，简化了 Hermite 张量的结构。与 Bakshi et al. (2022) 处理任意协方差不同。
    • 无分离条件：不要求成分均值之间有 gap，也不要求最小权重。这是该问题设定下的一个关键挑战。
    • 有界均值：\(\|\mu_j\| \le R\)。这是矩方法能够工作的基础，保证了矩的有界性。
  • 与已有文献的对比：相比 Doss et al. (2023)，本文放宽了“多项式时间算法只能达到 \((d/n)^{1/4}\) 率”的限制。相比 Diakonikolas and Kane (2025)，本文强化了“proper 输出”和“sharp \(d/\varepsilon^2\) 样本复杂度”。相比 Bakshi et al. (2022)，本文在更窄的设定下（单位协方差）取得了更优的样本效率。

主要结果

  • 定理 1（Sharp proper polynomial-time estimation）：这是本文的核心定理，包含两个部分：
    1. 期望风险界：存在一个估计器 \(\hat{\Gamma}_E\)，使得 \(\mathbb{E}_\Gamma H(P_{\hat{\Gamma}_E}, P_\Gamma) \le C_{k,R} \min(1, \sqrt{d/n})\)。这证明了在期望 Hellinger 距离下达到 minimax 最优率。
    2. 尾风险界：存在一个依赖于置信水平的估计器 \(\hat{\Gamma}_\delta\)，使得 \(P_\Gamma(H(P_{\hat{\Gamma}_\delta}, P_\Gamma) > C_{k,R} \min(1, \sqrt{(d + \log(1/\delta))/n})) \le \delta\)。这给出了一个高概率的保证。
    3. 直觉：这两个界都达到了 \(\sqrt{d/n}\) 的率，与 Doss et al. (2023) 证明的 minimax 下界匹配，因此是 sharp 的。常数 \(C_{k,R}\) 依赖于 \(k\) 和 \(R\)，但不依赖于 \(d\) 和 \(n\)。
    4. 必要条件：\(k\) 和 \(R\) 是固定的常数。
    5. 解决的技术难点：如何构造一个多项式时间算法，使得其 Hellinger 误差从 \((d/n)^{1/4}\) 降低到 \(\sqrt{d/n}\)。这通过“矩-纤维范围查找器”解决。

证明路线与技术技巧

  • 整体路线：证明分为三个主要步骤，对应三个独立的数据块：

    1. 块 1：粗范围（Coarse Range）：用样本二阶矩 \(\hat{M}_2\) 的 top-\(q\) 特征空间 \(A\) 作为初始子空间。这一步的误差由 \(\rho = \mathbb{E}\|(I-P_A)U\|^2\) 控制，其量级为 \(\sqrt{d/n}\)。
    2. 块 2：矩-纤维范围增强（Moment-Fiber Range Augmentation）：对于 \(s = 0, \ldots, 2k-2\)，选取 \(A\) 中 \(s\) 阶对称张量的基 \(\{E_{s,j}\}\)。然后，用块 2 的数据估计向量值统计量 \(g_{s,j} = M_{s+1}(\Gamma) \lrcorner E_{s,j} = \mathbb{E}[H_{s+1}(X) \lrcorner E_{s,j}]\)。这些估计量 \(\hat{g}_{s,j}\) 与 \(A\) 一起张成子空间 \(H\)。关键跳跃点：Lemma 1 证明了，对于任意 \(\ell\)，矩张量 \(M_\ell(\Gamma)\) 在投影到 \(H^{\otimes \ell}\) 时的误差可以被分解为纤维估计误差 \(e_s\) 和二阶矩丢失能量 \(\rho\) 的线性组合，且 \(e_s\) 的量级也是 \(\sqrt{d/n}\)。因此，总误差被控制在 \(\sqrt{d/n}\)。
    3. 块 3：常维空间穷举拟合（Proper Fitting in Fixed Dimension）：将数据投影到 \(H\) 上（通过矩阵 \(B\)），得到一个 \(m\) 维（\(m\) 仅依赖于 \(k\)）的低维问题。在这个低维空间中，用块 3 的数据估计混合分布 \(\Gamma_H = (B^\top)_\# \Gamma\) 的矩。然后，在一个精细的网格上穷举搜索，找到一个与估计矩匹配的混合分布 \(\hat{\gamma}\)。最后，将 \(\hat{\gamma}\) 通过 \(B\) 提升回原空间，得到最终的估计 \(\hat{\Gamma}\)。关键跳跃点：由于 \(m\) 是常数，网格的大小是 \(O((C/\tau)^{km + k - 1})\)，其中 \(\tau\) 是网格精度（量级为 \(\sqrt{d/n}\)），因此搜索复杂度是 \(n\) 的多项式。Lemma 5 保证了网格搜索的误差可控。

  • 技术技巧点名：

    • Hermite 收缩（Hermite Contractions）：使用 \(Y_{\ell, q}(x) = H_\ell(x) \lrcorner q\) 来避免直接估计高维张量，将问题转化为估计有限个 \(d\) 维向量。
    • 有限协方差鲁棒均值估计（Finite-Covariance Robust Mean Estimation）：Proposition 1 引用了 Hopkins (2020) 和 Cherapanamjeri et al. (2019) 的算法，用于在仅有有限协方差假设下，以子高斯速率估计纤维的均值。这是处理 Hermite 多项式重尾行为的关键。
    • 子空间投影引理（Lemma 1）：这是证明的核心技术引理，它通过将矩张量的投影误差分解为“一自由指标”项和“高阶残差”项，精确地刻画了子空间扩展如何消除投影偏差。
    • 无维矩刻画（Dimension-Free Moment Characterization）：Theorem 2 引用了 Doss et al. (2023) 的结果，该定理表明，对于支撑在至多 \(k\) 个点上的混合分布，其 Hellinger 距离可以被前 \(2k-1\) 阶矩的 Frobenius 范数距离所控制，且常数不依赖于 \(d\)。这保证了在低维空间中的矩拟合可以转化为原空间中的 Hellinger 距离控制。
    • 样本分割（Sample Splitting）：将数据分为三个独立块，分别用于粗范围估计、纤维估计和最终拟合，简化了概率分析。

真实例子与应用

本文为纯理论论文，无实证例子。作者在 Section 8 中讨论了算术复杂度，并以 \(k=3\) 为例，指出最坏情况下网格搜索可能需要 \(O(n^{58})\) 个候选点，但强调这仅证明多项式时间可计算性，并非实用算法。

🔎 结论是否比证明窄

  • 结论：定理 1 声称对于任意固定的 \(k\) 和 \(R\)，存在多项式时间估计器达到最优 Hellinger 率。
  • 证明的窄化：
    1. 多项式时间是在实数算术模型下：作者在 Section 1 明确声明“polynomial time”指的是多项式次精确实数算术运算，而非 Turing 机上的位复杂度。他们讨论了有限精度问题，但未给出完整的 Turing 模型证明。因此，结论的“多项式时间”在严格的计算机科学意义下可能比证明更宽。
    2. 常数依赖：算法的多项式复杂度依赖于 \(k\) 为常数。作者在 Section 1 也明确声明“the result does not claim polynomial complexity when \(k\) is part of the input”。因此，结论不能泛化为“对于任意 \(k\) 的多项式时间算法”。
    3. 算法非实用：作者在 Section 1 承认“it is a complexity-theoretic rather than a practical algorithm”，并以 \(k=3\) 时 \(O(n^{58})\) 的候选点为例。因此，结论的“存在性”是理论上的，而非实用的。
    4. 单位协方差假设：结论严格限制在协方差为单位阵 \(I_d\) 的球形高斯混合。对于更一般的协方差结构，结论不直接适用。

四、开放问题

  1. 未知公共协方差：本文假设协方差为单位阵 \(I_d\)。一个自然的开放问题是，能否将结果推广到已知但非单位的公共协方差 \(\Sigma\)，或者未知的公共协方差？这需要处理白化变换带来的复杂性，以及估计协方差带来的额外误差。扎根点：本文的模型设定 (1.1) 明确假设 \(Z \sim N(0, I_d)\)。作者在 Section 10 讨论 Bakshi et al. (2022) 时，将其处理任意协方差作为更一般但样本复杂度非最优的路线。

  2. 降低计算复杂度：本文的算法在理论上是指数依赖于 \(k\) 的，且对于 \(k=3\) 就有 \(O(n^{58})\) 的复杂度。能否设计一个实际可行的算法，其多项式指数更小，例如 \(O(n^c)\) 其中 \(c\) 是一个小的常数？扎根点：作者在 Section 1 承认“No attempt is made to optimize this exponent”，并在 Section 8 给出了 \(k=3\) 时 \(n^{58}\) 的粗界。

  3. \(k\) 随 \(n\) 增长的情况：本文要求 \(k\) 是固定常数。一个更具挑战性的问题是，当 \(k\) 可以随 \(n\) 缓慢增长（例如 \(k = o(\log n)\) 或 \(k = O(1)\) 但上界未知）时，是否仍能构造多项式时间算法达到最优率？扎根点：作者在 Section 1 明确声明“the result does not claim polynomial complexity when \(k\) is part of the input”。

  4. 其他距离下的最优性：本文在 Hellinger 距离下达到了最优率。能否在Wasserstein 距离或总变差距离下也达到最优率？Doss et al. (2023) 在 Wasserstein 距离下给出了 \(\Theta((d/n)^{1/4} + n^{-1/(4k-2)})\) 的率，本文的算法能否改进这个率？扎根点：本文的 Theorem 2 引用了 Doss et al. (2023) 的矩刻画，该刻画适用于 \(H^2, KL, \chi^2\) 距离，但未提及 Wasserstein 距离。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论