提出分布式K均值算法，降低通信开销但需更高信噪比。
LocalKMeans: Convergence of Lloyd's Algorithm with Distributed Local Iterations
- 在多机上并行本地迭代，每L步才同步一次
- 本地迭代使收敛所需信噪比提高，但减少通信量
- 首次分析非凸非光滑目标下的局部迭代收敛性
本文研究在数据分布式场景下，对高斯混合模型采用局部迭代的经典K均值算法（即Lloyd算法）。假设无标签数据分布在多个机器上，提出LocalKMeans算法：各机器在本地数据上并行执行Lloyd算法的迭代步骤，仅每隔L步进行一次全局同步。我们分析了这种局部迭代带来的代价，发现其要求更高的信号-噪声比。此前局部迭代主要在基于梯度的学习方法中被研究，而无监督学习因存在隐变量（如簇身份）导致分析更复杂。为获得结果，我们改进了虚拟迭代法以处理非凸、非光滑的目标函数，并结合紧致的统计分析推导出关键收敛结论。
原文摘要 · Abstract (English)
In this paper, we analyze the classical $K$-means alternating-minimization algorithm, also known as Lloyd's algorithm (Lloyd, 1956), for a mixture of Gaussians in a data-distributed setting that incorporates local iteration steps. Assuming unlabeled data distributed across multiple machines, we propose an algorithm, LocalKMeans, that performs Lloyd's algorithm in parallel in the machines by running its iterations on local data, synchronizing only every $L$ of such local steps. We characterize the cost of these local iterations against the non-distributed setting, and show that the price paid for the local steps is a higher required signal-to-noise ratio. While local iterations were theoretically studied in the past for gradient-based learning methods, the analysis of unsupervised learning methods is more involved owing to the presence of latent variables, e.g. cluster identities, than that of an iterative gradient-based algorithm. To obtain our results, we adapt a virtual iterate method to work with a non-convex, non-smooth objective function, in conjunction with a tight statistical analysis of Lloyd steps.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。