# Gradient Based Clustering

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 37 references that are in the map.
- First posted on arXiv 1 Feb 2022.

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

- [The Hardness of Approximation of Euclidean k-means](https://mlsanity.com/paper/1502.03316/) (2015)
- [Uniform Concentration Bounds toward a Unified Framework for Robust Clustering](https://mlsanity.com/paper/2110.14148/) (2021)
- [Clustering with Distributed Data](https://mlsanity.com/paper/1901.00214/) (2019)
- [Resistant convex clustering: How does the fusion penalty enhance resistantance?](https://mlsanity.com/paper/1906.09581/) (2019)

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

- [High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise](https://mlsanity.com/paper/2310.18784/) (2023)
- [A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments](https://mlsanity.com/paper/2209.10866/) (2022)
- [Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization](https://mlsanity.com/paper/2602.05657/) (2026)
- [A Unified Framework for Center-based Clustering of Distributed Data](https://mlsanity.com/paper/2402.01302/) (2024)
- [Distributed Gradient Clustering: Convergence and the Effect of Initialization](https://mlsanity.com/paper/2603.20507/) (2026)

## Abstract (arXiv)

We propose a general approach for distance based clustering, using the gradient of the cost function that measures clustering quality with respect to cluster assignments and cluster center positions. The approach is an iterative two step procedure (alternating between cluster assignment and cluster center updates) and is applicable to a wide range of functions, satisfying some mild assumptions. The main advantage of the proposed approach is a simple and computationally cheap update rule. Unlike previous methods that specialize to a specific formulation of the clustering problem, our approach is applicable to a wide range of costs, including non-Bregman clustering methods based on the Huber loss. We analyze the convergence of the proposed algorithm, and show that it converges to the set of appropriately defined fixed points, under arbitrary center initialization. In the special case of Bregman cost functions, the algorithm converges to the set of centroidal Voronoi partitions, which is consistent with prior works. Numerical experiments on real data demonstrate the effectiveness of the proposed method.