# Scalable Second-order Riemannian Optimization for K-means Clustering

arXiv: https://arxiv.org/abs/2509.21675 · HTML: https://mlsanity.com/paper/2509.21675/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 52 references that are in the map.
- First posted on arXiv 25 Sep 2025.

## Builds on (most cited first, 25 of 25)

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Manopt, a Matlab toolbox for optimization on manifolds](https://mlsanity.com/paper/1308.5200/) (2013)
- [Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation](https://mlsanity.com/paper/1603.03236/) (2016)
- [Global Optimality of Local Search for Low Rank Matrix Recovery](https://mlsanity.com/paper/1605.07221/) (2016)
- [Global rates of convergence for nonconvex optimization on manifolds](https://mlsanity.com/paper/1605.08101/) (2016)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [The effect of smooth parametrizations on nonconvex optimization landscapes](https://mlsanity.com/paper/2207.03512/) (2022)
- [Riemannian preconditioning](https://mlsanity.com/paper/1405.6055/) (2014)
- [Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs](https://mlsanity.com/paper/1804.02008/) (2018)
- [Cutoff for exact recovery of Gaussian mixture models](https://mlsanity.com/paper/2001.01194/) (2020)
- [On the low-rank approach for semidefinite programs arising in synchronization and community detection](https://mlsanity.com/paper/1602.04426/) (2016)
- [Adaptive regularization with cubics on manifolds](https://mlsanity.com/paper/1806.00065/) (2018)
- [Wasserstein K-means for clustering probability distributions](https://mlsanity.com/paper/2209.06975/) (2022)
- [Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming](https://mlsanity.com/paper/2305.18436/) (2023)
- [Structures of Spurious Local Minima in k-means](https://mlsanity.com/paper/2002.06694/) (2020)
- [A Cubic Regularized Newton's Method over Riemannian Manifolds](https://mlsanity.com/paper/1805.05565/) (2018)
- [A low-rank augmented Lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach](https://mlsanity.com/paper/2401.12490/) (2024)
- [A Decomposition Augmented Lagrangian Method for Low-rank Semidefinite Programming](https://mlsanity.com/paper/2109.11707/) (2021)
- [A Riemannian Optimization Approach to Clustering Problems](https://mlsanity.com/paper/2208.03858/) (2022)
- [Solving Low-Rank Semidefinite Programs via Manifold Optimization](https://mlsanity.com/paper/2303.01722/) (2023)
- [A low-rank augmented Lagrangian method for doubly nonnegative relaxations of mixed-binary quadratic programs](https://mlsanity.com/paper/2502.13849/) (2025)
- [Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima](https://mlsanity.com/paper/2505.03717/) (2025)

## Built on by (most cited first, 2 of 2)

- [Riemannian Difference-of-Convex Optimization for K-Means Clustering](https://mlsanity.com/paper/2609.34310/) (2026)
- [GEM-KMeans: Memory-Efficient and Accurate Clustering on Massive Scale with GPU Optimization](https://mlsanity.com/paper/2609.36074/) (2026)

## Abstract (arXiv)

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.