提出新方法加速求解K均值聚类的二阶临界点，兼具速度快与精度高。
Scalable Second-order Riemannian Optimization for $K$-means Clustering
- 将K均值重构为流形上的光滑无约束优化问题
- 线性时间求解每轮牛顿子问题，收敛速度远超现有方法
- 适合需要高精度聚类结果的科研与工业场景
聚类是困难的离散优化问题。近年来，低秩半定规划（SDP）等非凸方法在聚类恢复上展现出优异的统计和局部算法保证。由于K均值问题的组合结构，现有松弛算法难以兼顾约束可行性与目标最优性，导致计算二阶临界点时面临巨大挑战。本文将K均值问题重新表述为流形上的光滑无约束优化，并刻画其黎曼结构，从而可用二阶立方正则化黎曼牛顿法求解。通过将K均值流形分解为乘积流形，我们证明每个牛顿子问题可在线性时间内求解。数值实验表明，所提方法收敛速度显著快于当前最优的一阶非负低秩因子化方法，同时达到相似的最优统计精度。
原文摘要 · Abstract (English)
Clustering is a hard discrete optimization problem. Nonconvex approaches such as low-rank semidefinite programming (SDP) have recently demonstrated promising statistical and local algorithmic guarantees for cluster recovery. Due to the combinatorial structure of the $K$-means clustering problem, current relaxation algorithms struggle to balance their constraint feasibility and objective optimality, presenting tremendous challenges in computing the second-order critical points with rigorous guarantees. In this paper, we provide a new formulation of the $K$-means problem as a smooth unconstrained optimization over a submanifold and characterize its Riemannian structures to allow it to be solved using a second-order cubic-regularized Riemannian Newton algorithm. By factorizing the $K$-means manifold into a product manifold, we show how each Newton subproblem can be solved in linear time. Our numerical experiments show that the proposed method converges significantly faster than the state-of-the-art first-order nonnegative low-rank factorization method, while achieving similarly optimal statistical accuracy.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。