# Replicable Clustering

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 63 references that are in the map.
- First posted on arXiv 20 Feb 2023.

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

- [Improving Reproducibility in Machine Learning Research (A Report from the NeurIPS 2019 Reproducibility Program)](https://mlsanity.com/paper/2003.12206/) (2020)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Reproducibility in Learning](https://mlsanity.com/paper/2201.08430/) (2022)
- [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [Reproducibility in Optimization: Theoretical Framework and Limits](https://mlsanity.com/paper/2202.04598/) (2022)
- [Differentially-Private Clustering of Easy Instances](https://mlsanity.com/paper/2112.14445/) (2021)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [Approximation Algorithms for Minimum Norm and Ordered Optimization Problems](https://mlsanity.com/paper/1811.05022/) (2018)
- [Robust Hierarchical Clustering](https://mlsanity.com/paper/1401.0247/) (2014)
- [The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction](https://mlsanity.com/paper/2205.00371/) (2022)
- [Efficient Kirszbraun Extension with Applications to Regression](https://mlsanity.com/paper/1905.11930/) (2019)

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

- [Replicability in Reinforcement Learning](https://mlsanity.com/paper/2305.19562/) (2023)
- [Statistical Indistinguishability of Learning Algorithms](https://mlsanity.com/paper/2305.14311/) (2023)
- [Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2402.13857/) (2024)
- [Replicability in High Dimensional Statistics](https://mlsanity.com/paper/2406.02628/) (2024)
- [On the Computational Landscape of Replicable Learning](https://mlsanity.com/paper/2405.15599/) (2024)
- [Replicable Online Learning](https://mlsanity.com/paper/2411.13730/) (2024)
- [Stability and List-Replicability for Agnostic Learners](https://mlsanity.com/paper/2501.05333/) (2025)
- [Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces](https://mlsanity.com/paper/2503.15294/) (2025)
- [Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimization](https://mlsanity.com/paper/2310.17759/) (2023)
- [Replicability is Asymptotically Free in Multi-armed Bandits](https://mlsanity.com/paper/2402.07391/) (2024)
- [Replicable Distribution Testing](https://mlsanity.com/paper/2507.02814/) (2025)
- [Simplicial covering dimension of extremal concept classes](https://mlsanity.com/paper/2511.11819/) (2025)
- [The Sample Complexity of Replicable Realizable PAC Learning](https://mlsanity.com/paper/2602.19552/) (2026)
- [Tight list replicability bounds via a novel sphere covering theorem](https://mlsanity.com/paper/2606.06148/) (2026)
- [Sign-Rank, Index, and List Replicability: Connections and Separations](https://mlsanity.com/paper/2606.18236/) (2026)
- [Unsupervised Optimisation of GNNs for Node Clustering](https://mlsanity.com/paper/2402.07845/) (2024)
- [Generalizability of experimental studies](https://mlsanity.com/paper/2406.17374/) (2024)
- [Computationally Efficient Replicable Learning of Parities and Applications](https://mlsanity.com/paper/2602.09499/) (2026)
- [Replicable Bandits with UCB based Exploration](https://mlsanity.com/paper/2604.20024/) (2026)

## Abstract (arXiv)

We design replicable algorithms in the context of statistical clustering under the recently introduced notion of replicability from Impagliazzo et al. [2022]. According to this definition, a clustering algorithm is replicable if, with high probability, its output induces the exact same partition of the sample space after two executions on different inputs drawn from the same distribution, when its internal randomness is shared across the executions. We propose such algorithms for the statistical k-medians, statistical k-means, and statistical k-centers problems by utilizing approximation routines for their combinatorial counterparts in a black-box manner. In particular, we demonstrate a replicable O(1)-approximation algorithm for statistical Euclidean k-medians (k-means) with operatornamepoly(d) sample complexity. We also describe an O(1)-approximation algorithm with an additional O(1)-additive error for statistical Euclidean k-centers, albeit with exp(d) sample complexity. In addition, we provide experiments on synthetic distributions in 2D using the k-means++ implementation from sklearn as a black-box that validate our theoretical results.