跳转至

Consistency of Lloyd’s algorithm under perturbations

作者: Hui Shen, Dhruv Patel, Shankar Bhamidi, Vladas Pipiras, Yufeng Liu
来源: Electronic Journal of Statistics
主题: 其他
相关性: 6/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么

本方向研究 Lloyd 算法（k-means 迭代算法）在子高斯混合模型下的统计与计算保证。核心问题：给定来自有限混合分布的独立同分布样本，Lloyd 算法（交替执行样本分配和中心更新）经过多少轮迭代、在什么初始化条件下，能够以多快的速度收敛到真实聚类标签，该收敛率是否达到 minimax 最优。该方向处于中等成熟度：奠基工作（Pollard, 1981）建立了弱相合性，但直到 Lu 与 Zhou (2016) 才首次给出非渐近指数界和 minimax 最优性；此后 Gao 与 Zhang (2022) 将框架推广到更一般的离散结构恢复问题。当前前沿正在向更实际的数据生成机制延伸，例如有预处理扰动、网络数据、高维时间序列等。

发展脉络

奠基工作
- Pollard (1981) —— 证明经验最小化 k-means 估计量的强相合性，但只有渐近结果，无收敛率。
- Balakrishnan, Wainwright, Yu (2017) —— 建立 EM 算法的非渐近理论（分“总体”和“有限样本”两阶段），为迭代算法的统计分析提供了通用模板。

核心进展：Lloyd 算法理论突破
- Lu 与 Zhou (2016) —— 第一个非渐近指数界：对子高斯混合，若初始化适当（例如通过 k-means++ 或谱方法），Lloyd 算法在 O(log n) 次迭代后误聚类率以指数衰减到零，且该界是 minimax 最优。这篇是本文的直接前驱。
- Gao 与 Zhang (2022) —— 进一步推广到更一般的离散结构恢复（包括聚类、排序、符号恢复），建立线性收敛性，并泛化了 Lloyd 算法为“迭代特征匹配”框架。

并行的谱聚类与社区检测理论线
- Rohe, Chatterjee, Yu (2011) —— 首次允许簇数随节点数增长，给出谱聚类在随机块模型中的误聚类率界。
- Lei 与 Rinaldo (2015) —— 将谱聚类理论推广到期望度低至 log n 的稀疏图，给出更紧的随机矩阵谱界。
- Löffler, Zhang, Zhou (2021) —— 证明谱聚类在高斯混合模型下是 minimax 最优的（无需谱间隙条件）。
- Abbe (2017) —— 综述随机块模型中的相变与阈值（信息论 vs 计算阈值），为社区检测理论提供全景。

本文（Shen et al. 2024）的位置
作者将 Lu 与 Zhou (2016) 的 Lloyd 算法分析从真实样本直接可用推广到观测样本是真实样本加上扰动的情形。扰动产生于预处理步骤（如谱方法降维、多维缩放等）。作者声称：“in many applications, the true samples are unobserved and need to be learned from the data via pre-processing pipelines”。因此，本文是 Lu-Zhou 框架的自然延伸至更现实的 pipeline 设定。

子线索聚类

根据引言和引用语境，被引工作可归纳为四条子线索：

  1. 迭代聚类算法的理论分析：Lu 与 Zhou (2016)、Gao 与 Zhang (2022)、Balakrishnan et al. (2017)。这一簇为迭代算法（Lloyd、EM）提供非渐近收敛保证，核心工具是概率不等式和局部强凸性。
  2. 谱聚类与随机块模型（SBM）：Lei 与 Rinaldo (2015)、Rohe et al. (2011)、Löffler et al. (2021)、Abbe (2017)、Bordenave et al. (2015)、Krzakala et al. (2013)。这一簇关注用谱方法实现社区检测，给出一致性或最优性，常使用 ℓ₂→ℓₘ（尤其是 ℓ∞）范数下的特征向量扰动界。
  3. 因子模型与时间序列聚类：Bai 与 Ng (2008)、Bhamidi et al. (2023)、Doz et al. (2012)。将因子分析与谱聚类结合，用动态因子模型定义相关网络，再用 k-means 聚类。
  4. 高维分类与聚类 pipeline 的应用：Little et al. (2022)（经典多维缩放的聚类理论）、Chen et al. (2019)（单细胞 RNA-seq 的软件综述）、SigClust 管道（本文提及用于评估聚类的统计显著性）。这一簇为本文提供了具体应用场景。

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

  1. Lloyd 算法需要多好的初始化才能避免局部最优陷阱？ 现有结果（Lu-Zhou, Gao-Zhang）要求初始中心位于真实中心的一个“局部球”内，或者初始标签比随机猜测略好。如何放松这一要求？
  2. 扰动幅度与算法收敛性的关系是什么？ 当数据被预处理器（如谱方法）引入误差后，Lloyd 算法的误聚类率界是否会退化？退化的形式是加法还是乘法？
  3. 能否将 Lloyd 算法的保证推广到非子高斯、重尾或非 i.i.d. 数据（如时间序列或网络依赖）？
  4. 理论保证是否能在实际 pipeline（如社区检测的谱聚类 + k-means）中达到可验证的误聚类率界？

⚠️ 作者的 framing（必须明确标注成“这是作者的说法”）

作者在引言中把缺口 frame 成：“previous works assume the true samples directly available, but in practice samples are unobserved and need to be learned via pre-processing”。因此，本文的贡献是“将 Lu-Zhou 的结论扩展到扰动样本，并在若干 canonical 扰动设定（谱聚类管道中的特征向量估计误差、多维缩放的嵌入误差等）下导出具体误聚类率界”。这是显然的下一步，因为预处理在应用中是标配。

被淡化/回避的竞争路线：作者没有讨论当扰动幅度超过子高斯噪声时 Lloyd 算法是否会失败或退化到随机猜测（他们只给出了一个充分条件）；也没有将结果与直接对观测数据运行谱聚类（非 Lloyd）的错误率进行对比。作者声称“我们的结果可以用于 SigClust 管道”，但没有与直接基于谱聚类的聚类显著性检验做比较。

明显该被引/该存在却没出现在 intro 里的工作：
- Klochkov et al. (2021) 关于“Robust k-means Clustering for Distributions with Two Moments” —— 该文在仅两阶矩条件下给出了 k-means 的非渐近界，与本文的“子高斯”假设不同，且对扰动更鲁棒，但本文 intro 并未引用（仅在参考文献中列出）。值得研究者去查：为什么作者选择子高斯假设而非两阶矩？是不是因为用经验过程方法在扰动下扩展两阶矩结果更困难？
- 关于“统计—计算权衡”的文献（如信息论阈值 vs 计算阈值，Abbe 2017 综述中提及）在本文的社区检测应用中没有被衔接，尽管本文的谱聚类部分涉及了稀疏网络——稀疏网络有著名的 Kesten-Stigum 阈值，但本文没有讨论 Lloyd 算法是否能在该阈值下达到最优检测。

张力

未见明显对立引用。多数被引工作彼此互补（如 Lu-Zhou 的 Lloyd 分析、Lei-Rinaldo 的谱聚类界、Abbe 的 SBM 综述），共同支撑了本文的目标。一个可能的潜在张力是：Löffler et al. (2021) 已经证明谱聚类在 GMM 下 minimax 最优，而本文坚持用 Lloyd 算法而非谱聚类来聚类，这需要论证 Lloyd 在扰动下相比直接谱聚类有何优势。但本文并未提供该论证，只是“假设我们选择 Lloyd 算法作为聚类器”的态度。

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

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

本文的核心记号列表如下（均为 Shen et al. 论文中所用）：

  • 样本量：\(n\)（独立样本数）。
  • 簇数：\(K\)（固定已知）。
  • 真实标签：\(z_i \in \{1,\dots,K\}\)，为每个样本的潜在真类（不可观测）。
  • 真实中心：\(\mu_k \in \mathbb{R}^d\)，每个簇的真均值向量（待估计的对象）。
  • 真实样本：\(X_i \in \mathbb{R}^d\)，从混合分布中生成的 i.i.d. 样本。作者假设混合分布是子高斯的：存在 \(\sigma, s\) 使得每个簇内的 \(X_i - \mu_{z_i}\) 是子高斯向量（协方差谱范数 \(\leq \sigma^2\)），且簇间均值最小间隔 \(s = \min_{k\neq l} \|\mu_k - \mu_l\|_2 > 0\)。
  • 观测样本：\(\widetilde{X}_i \in \mathbb{R}^d\)，是真实样本经过某种预处理后实际可观测的数据。两者的关系写成 \(\widetilde{X}_i = X_i + e_i\)，其中 \(e_i\) 是扰动向量，表示预处理误差。扰动可能是有色的（依赖于整个数据集），但本文假定其范数在很多点上较小。
  • 可观测数据：研究者实际能看到的是 \(\{\widetilde{X}_i\}_{i=1}^n\) 以及某种初始化算法给出的初始中心估计 \(\hat{\mu}_k^{(0)}\)。真实标签和真实样本 \(X_i\) 都不可观测。
  • Lloyd 算法的迭代输出：第 t 轮的中心估计 \(\hat{\mu}_k^{(t)}\) 和分配标签 \(\hat{z}_i^{(t)}\)。
  • 误聚类率：\(M^{(t)} = \frac{1}{n} \sum_{i=1}^n \mathbf{1}\{\hat{z}_i^{(t)} \neq z_i\}\)（若把中心重新排列以匹配真标签）。
  • 扰动条件：定义两个量：最大平均扰动 \(\delta = \max_k \frac{1}{n_k} \|\sum_{i: z_i=k} e_i\|_2\) 和最大逐点扰动范数 \(\eta = \max_i \|e_i\|_2\)。本文要求这些扰动小于某个依赖 \(s, \sigma\) 的阈值。

模型：
- 真实数据来自 K 个分量的子高斯混合，每个分量有等比例（或一般比例但无偏）。
- 扰动生成：不限定具体机制，只假设 \(\delta\) 和 \(\eta\) 以高概率有小上界。这覆盖了谱方法估计的特征向量误差、MDS 嵌入误差等。
- 初始化由一个独立算法（如 k-means++ 或谱初始化）产生，要求初始中心距离真实中心不超过某个与 \(s\) 和 \(\sigma\) 有关的半径。

关键区分：
- 可观测：\(\widetilde{X}_i\) (观测样本) 和通过某种方法获得的初始中心。
- 不可观测：真实样本 \(X_i\)、真实标签 \(z_i\)、真实中心 \(\mu_k\)、扰动 \(e_i\)。
- 要估的对象：真实标签 \(z_i\)（等价于恢复聚类结构）。

第二步：最小内核（最简特例）

去掉一切繁枝（K>2、不等比例、子高斯一般情况、扰动依赖结构等），本文的最小内核可退化为两个等方差球面高斯簇、且扰动为独立设计算子的情况：

  • 设定：\(K=2\)，真中心 \(\mu_1 = -a\)，\(\mu_2 = a\)（间隔 \(s = 2\|a\|\)）。簇内噪声 → 各向同性协方差 \(\sigma^2 I\)。真实样本 \(X_i \sim N(\mu_{z_i}, \sigma^2 I)\)。
  • 扰动：每个真实样本被独立扰动 \(e_i \sim N(0, \tau^2 I)\)（实际上本文的扰动不一定独立同分布，但作为最小特例可假设独立高斯），于是观测样本 \(\widetilde{X}_i = X_i + e_i \sim N(\mu_{z_i}, (\sigma^2 + \tau^2)I)\)。
  • 关键数量：信噪比 \(s/\sigma\) 与扰动比 \(s/\tau\)。本文要求扰动不能太大：\(\tau\) 必须小于 \(\sigma/2\) 之类（实际是要求扰动相对于真实子高斯噪声小）。
  • Lloyd 算法（初始中心由简单谱方法给出，例如计算第一大奇异向量方向的两个端点）。
  • 核心命题（最小版本）：如果初始中心 \(\hat{\mu}_k^{(0)}\) 满足 \(\max_k \|\hat{\mu}_k^{(0)} - \mu_k\|_2 < s/4\)，且扰动满足 \(\max_i \|e_i\|_2 < s/20\)（概率下成立），则 Lloyd 算法每轮迭代后误聚类率以概率至少 \(1 - C n^{-2}\) 指数衰减：
\[M^{(t)} \leq C \exp\big( - \frac{c\, n\, s^2}{\sigma^2} \cdot (1 - \text{扰动影响}) \big)\]

且经过 \(t = O(\log n)\) 轮后，\(M^{(t)} \leq n^{-c}\)。
- 为什么这很小：关键思想是每轮迭代中，误分类的点经过中心更新后，其“坏”样本在估计新中心时的贡献被中心位置误差放大，形成收缩映射。扰动只是给这个映射增加了一个小的加性误差项；只要扰动小于阈值，收缩性保留。Lu-Zhou 2016 已经对无扰动情况证明了这一点，本文证明将扰动项分离出来并加以控制。
- 这个例子包含了全文技术的本质：概率不等式 + 对中心更新映射的局部 contraction + 扰动误差的传播控制。全文的一般情形无非是把两簇推广到多簇、子高斯替换高斯、集总的扰动界替换独立高斯界。

三、这篇论文做了什么

三句话

  1. 研究问题：当 Lloyd 算法的输入不是真实子高斯混合样本，而是经过预处理（如谱方法、MDS）产生的扰动样本时，该算法的误聚类率是否仍然指数衰减。
  2. 核心工具：将 Lu 与 Zhou (2016) 的证明框架（中心更新映射的收缩性 + 子高斯 tail 界）扩展至有额外扰动项的情形，通过引入对扰动幅度（\(\delta\) 和 \(\eta\)）的联合控制，给出迭代收敛的条件和率。
  3. 主要结论：在扰动幅度小于一个与真实子高斯噪声参数有关的常数的条件下，Lloyd 算法在 \(O(\log n)\) 轮迭代后误聚类率指数衰减到零；该界可进一步 derive 出多种应用场景（谱聚类、多维缩放、高维时间序列因子模型）的具体误聚类率。

关键设定与假设

在第二节最小记号基础上，补全完整设定：

  • 数据生成：真实样本 \(\{X_i\}_{i=1}^n\) 来自 K 分量子高斯混合。记 \(\Sigma_k = \text{Cov}(X_i \mid z_i=k)\)，设 \(\max_k \|\Sigma_k\|_{\text{op}} \leq \sigma^2\)。簇间最小间隔 \(s > 0\)。每个簇的占比 \(\pi_k\) 下界为某个正常数 \(c_\pi\)。
  • 扰动模型：观测样本 \(\widetilde{X}_i = X_i + e_i\)。对扰动不做独立同分布假设，但给出两个全局量：
  • 逐点扰动范数 \(\eta = \max_i \|e_i\|_2\)
  • 每簇平均扰动 \(\delta = \max_k \frac{1}{n_k} \|\sum_{i: z_i=k} e_i\|_2\)
    本文假设以高概率有 \(\eta \leq C_1 \sigma\) 和 \(\delta \leq C_2 s\)（具体常数在定理中给出）。
  • 初始化：存在一种初始化算法（如 k-means++ 或谱初始化），能保证初始中心估计满足
    \[\max_{1 \leq k \leq K} \min_{\pi \in \mathcal{S}_K} \|\hat{\mu}_k^{(0)} - \mu_{\pi(k)}\|_2 \leq \frac{s}{4}\]
    式中 \(\pi\) 是标签重排。作者为 k-means++ 和谱初始化也分别给出了条件。
  • 对比已有文献：相比 Lu 与 Zhou (2016)，本文放宽了对数据可直接观测的假设，但强化了对扰动幅度的假设（新假设）。相比 Gao 与 Zhang (2022)，本文专门针对扰动情形，而 Gao-Zhang 假设误差项是关于估计量的条件期望偏差。
  • 额外假设的统计含义：\(\delta\) 和 \(\eta\) 的有界性等价于要求预处理器引入的误差在单个样本水平和平均水平上都不太大。这对于谱方法来说是成立的（当信号强度足够大时，特征向量估计的 ℓ∞ 误差可控，见 Abbe et al. 2020 的 entrywise 结果）。

主要结果

论文有两个主要定理（定理 4.1 和定理 4.2）和一个主推论（Corollary 4.3），以及多个应用场景的推论。

定理 4.1（简化陈述）：
假设上述子高斯混合与扰动条件成立，且初始化满足 \(\max_k \min_\pi \|\hat{\mu}_k^{(0)} - \mu_{\pi(k)}\| \leq s/4\)。则存在常数 \(C, c, N\) 使得对所有 \(n \geq N\)，以概率至少 \(1 - O(n^{-2})\)，有

\[M^{(t)} \leq C \exp\left( -\frac{c n s^2}{\sigma^2} \right) + C \exp(-c n) \quad \text{（计入扰动项后）}\]
经过 \(t \asymp \log n\) 轮后，\(M^{(t)} \leq n^{-c'}\)。
- 直觉：第一项是 Lu-Zhou 原有界，第二项来自扰动。只要扰动项不占主导，收敛仍指数快。
- 必要条件：扰动幅度 \(\eta\) 和 \(\delta\) 要足够小（文中依赖 \(\sigma, s, K, c_\pi\)）。
- 解决的技术难点：如何在每次迭代中把扰动误差从中心更新中“剥离”出来并上界传递。

定理 4.2：
如果初始化由 k-means++ 给出，且采样点对的间隔满足额外条件（\(s \gtrsim \sigma \sqrt{\log n}\)），则初始化条件满足。

应用推论（Corollary 4.3 及后续）：
将上述结果实例化到：
1. 谱聚类管道（社区检测）：来自随机块模型（SBM）的图经过谱嵌入后，节点向量作为 \(\widetilde{X}_i\)，Lloyd 算法聚类，给出误聚类率界。
2. 高维时间序列（CDFM）：来自动态因子模型的估计载荷矩阵近似于真实载荷的变换，作者用 Bhamidi et al. (2023) 的结果对上界做实例化。
3. 经典多维缩放（MDS）：将样本间距离矩阵的低维嵌入作为 \(\widetilde{X}_i\)，Lloyd 算法聚类，给出界。
4. SigClust 管道：用该界推导聚类显著性的检验统计量在零假设下的分布尾部。

证明路线与技术技巧（理论型）

整体路线（3-5 步逻辑主干）：

  1. 初始化保证：通过引理（Lemmas 5.1-5.3）建立存在好的初始化（k-means++ 或谱初始化）的高概率界。
  2. 单轮迭代的 contraction 性质：仿照 Lu-Zhou 2016 的证明，定义“好集合”和“坏集合”，将误分类样本分为两类（远离决策边界的和靠近的）。对无扰动情况，Lloyd 更新映射是局部收缩的：若当前中心误差 \(\leq s/4\)，则下一轮中心误差至少缩小一个常数因子 \(\rho < 1\)。
  3. 引入扰动：当存在 \(e_i\) 时，中心更新的误差项分为真实收缩项和扰动项。关键在于证明：若能控制 \(\eta\) 和 \(\delta\)，则扰动项不会破坏收缩性，即存在常数 \(0 < \rho' < 1\) 使得
    \[\max_k \|\hat{\mu}_k^{(t+1)} - \mu_k\| \leq \rho' \max_k \|\hat{\mu}_k^{(t)} - \mu_k\| + \text{扰动项}(\eta, \delta)\]
  4. 迭代递推：对该递推迭代 \(t\) 轮，得到中心误差的上界，再将中心误差转化为误聚类率的界（利用子高斯 tail 和中心间间隔）。
  5. 高概率结束：整个论证依赖多个事件的同时概率，作者使用子高斯 tail 和矩阵 Bernstein 不等式控制这些事件的并集。

关键跳跃点：
- 最吃功夫的引理：Lemma 6.1 和 Lemma 6.2，它们给出了在扰动下中心更新误差的递推关系。难点在于扰动项 \(e_i\) 不是独立于样本标签的，需要利用 \(\eta\) 和 \(\delta\) 的定义进行集总控制，而不能在每个样本上使用单样本 tail 界。
- 如何绕过：作者将扰动分离为“属于簇内平均扰动”和“剩余波动”两部分，利用 Cauchy-Schwarz 和矩阵范数不等式界定了它们的贡献。

技术技巧点名：
- 子高斯 tail 界与 Bernstein 不等式：用于控制样本均值的偏差。
- 经验过程基本不等式（Pollard 1981；Telgarsky-Dasgupta 2013；Klochkov et al. 2021）：用于建立经验风险最小化下的泛化界，这里作者引用其变体（引理 5.4）来证明 k-means++ 初始化产生的初始中心在子高斯混合下的误差界。
- 矩阵的 ℓ₂ 范数界：用于控制扰动项（如谱嵌入的特征向量误差，通过 Abbe et al. 2020 的 entrywise 分析）。
- 耦合论证 / 逐个事件条件：在每个迭代轮次上定义“好事件”，然后用联合界论证所有事件同时成立的概率。
- 常量追踪：作者给出了显式常数（如 \(\rho = 1/2\)，\(M_n = c \log n\) 等），使结果可量化。

真实例子与应用

本文为纯理论论文，没有真实数据例子。所有“应用”都是理论推导：将一般定理实例化到三个管道（谱聚类、CDFM、MDS），给出每个管道下扰动参数（\(\eta, \delta\)）的具体表达式，然后代入定理 4.1 得到误聚类率界。例如：
- 对于谱聚类+SBM 情形，观测样本 \(\widetilde{X}_i\) 是节点经 Laplacian 谱嵌入后的 d 维向量。作者引用 Rohe et al. (2011) 和 Lei-Rinaldo (2015) 的结果，推导出在这些条件下 \(\eta\) 和 \(\delta\) 渐近趋近于 0，因此 Lloyd 算法在 O(log n) 步后误聚类率指数衰减。
- 对于 CDFM（高维时间序列），观测样本是估计的因子载荷矩阵的行向量，作者引用 Bhamidi et al. (2023) 的定理来界定量化扰动。
- 没有模拟实验、没有真实数据验证，只有纯粹的数学推广。

🔎 结论是否比证明窄

是，部分结论的推广幅度小于证明所能支持的。具体来说：
- 定理 4.1 要求扰动条件（\(\eta\) 和 \(\delta\)）有界。但在应用推论（如谱聚类+SBM）中，作者只是宣称这些界由已知的谱方法误差界满足，却没有显式验证该条件是否在所有可能的参数区域（如稀疏网络、信噪比接近阈值时）都成立。论文第 7 节写“we apply Theorem 4.1 to the SBM setting”，但只引用了 Abbe et al. 2020 的 entrywise 结果来认可 \(\eta\) 和 \(\delta\) 的小性，没有对那个结果的参数范围（信号强度需多大）进行量化合并。因此，严格来说，论文的结论在应用部分依赖于“已知结果中隐含的假设区间”，而作者没有明确这些假设区间是否与定理 4.1 的假设区间完全匹配。这是读者需要校验的地方。
- 此外，论文声称结果可用于 SigClust 的统计分析，但没有给出任何具体推导或引理，只有一句“thus the result gives an upper bound on the mis-clustering rate under the null”（见文本末）。这部分显然只是一个 sketch，远弱于定理的严谨度。

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

  1. 扰动阈值是否可以进一步放宽？ 假设 2 要求扰动幅度相对于 \(\sigma\) 和 \(s\) 小。若扰动幅度与子高斯噪声相当或更大，Lloyd 算法是否仍能收敛？是否会出现新的相变？

  2. 扎根：定理 4.1 的条件（6）和（7）中常量是由 \(C_1\sigma\) 和 \(C_2 s\) 控制的（见原文（4.6）-（4.7））。作者没有讨论如果这些常量增大到超过阈值会发生什么。

  3. 初始化的假定是否可以在扰动下放松？ 定理要求初始中心误差 \(\leq s/4\)。当扰动存在时，初始化的实际性能可能退化。论文虽然给出了 k-means++ 在扰动下的界（定理 4.2），但该界隐含着额外的要求（\(s \gtrsim \sigma \sqrt{\log n}\)），且未证明这是可以放松的。

  4. 扎根：定理 4.2 的证明中使用了引理 5.4，该引理是在无扰动假设下对 k-means++ 的界；作者通过“用观测数据代替真实数据”直接套用该引理，但未处理由此引入的偏差。

  5. 不同扰动结构的统一框架：本文将扰动抽象为两个量 \(\eta, \delta\)，但实际应用中扰动可能具有群组相关或长期记忆（如时间序列的因子的估计误差）。是否存在更精细的扰动模型能给出更好的界？

  6. 扎根：在第 7 节应用部分，作者对每种应用独立给出了具体的 \(\eta, \delta\) 界，说明这些界并非从统一公式得出。一个统一 framework 可能更优美。

  7. 是否可以将 Lloyd 算法替换为更高效的迭代算法（如 mini-batch Lloyd）并保持类似保证？ 论文只讨论 batch Lloyd，未提及变体。

  8. 扎根：无直接语句，但作为 literature 的自然推广。可参考 Gao-Zhang (2022) 已给出更一般的迭代算法框架。

注意：以上问题并非建议研究者去回答，而是供其自行判断是否有价值深挖。要确认某条是不是真 gap，可去读相同子领域近期约 5 篇的 intro（如 JMLR 2022-2023 有关 Lloyd 或 k-means 理论的文章），看它们是否指向相同方向。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论