Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions

Kangke Cheng; Shihong Song; Guanlin Mo; Hu Ding

cs.DSMar 11, 2026

Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions

Authors: Kangke Cheng, Shihong Song, Guanlin Mo, Hu Ding

Organizations: University of Science and Technology of China, Hefei, China · School of Informatics, University of Edinburgh, Edinburgh, UK

Abstract

In this paper, we investigate the learning-augmented $k$ -median clustering problem, which aims to improve the performance of traditional clustering algorithms by preprocessing the point set with a predictor of error rate $α\in [0,1)$ . This preprocessing step assigns potential labels to the points before clustering. We introduce an algorithm for this problem based on a simple yet effective sampling method, which substantially improves upon the time complexities of existing algorithms. Moreover, we mitigate their exponential dependency on the dimensionality of the Euclidean space. Lastly, we conduct experiments to compare our method with several state-of-the-art learning-augmented $k$ -median clustering methods. The experimental results suggest that our proposed approach can significantly reduce the computational complexity in practice, while achieving a lower clustering cost.

Figures & tables

Methods	Approximation Ratio	Label Error Range	Time Complexity
Ergun et al. (2022)	$1+O((k\alpha)^{1/4})$	$\tilde{O}(\frac{1}{k})$	$O(nd\log^{3}n+\text{poly}(k,\log n))$
Nguyen et al. (2023)	$1+\frac{7\alpha+10\alpha^{2}-10\alpha^{3}}{(1-\alpha)(1-2\alpha)}$	$[0,1/2)$	$O(\frac{1}{1-2\alpha}nd\log^{3}n\log^{2}\frac{k}{\delta})$
Huang et al. (2025)	$1+\frac{(6+\epsilon)\alpha-4\alpha^{2}}{(1-\alpha)(1-2\alpha)}$	$[0,1/2)$	$O(nd\log(kd)\log(n\Delta)\cdot(\frac{\sqrt{d}}{\alpha\epsilon})^{O(d)})$
Sample-and-Search (ours)	$1+\frac{(6+\epsilon)\alpha-4\alpha^{2}}{(1-\alpha)(1-2\alpha)}$	$[0,1/2)$	$O(2^{O(1/(\alpha\varepsilon)^{4})}nd{\log\frac{k}{\delta}})$

Table 1: A comparison of our Sample-and-Search algorithm with state-of-the-art methods. Here, the terms

\epsilon>0

and

\delta\in(0,1)

are the parameters that control the approximation precision and success probability.

\Delta

denotes the aspect ratio of the given point set.

Figure 1: Comparison of the Approximation Ratios for our algorithm (set $\epsilon=0.1$ ) and the NCN algorithm in term of the change of error rate $\alpha$ . This plot shows that our algorithm (green dashed line) consistently achieves a lower approximation ratio than the NCN algorithm ( Nguyen et al. 2023 ) (blue solid line) across all values of the error rate $\alpha\in[0,1/2)$ . The purple shaded area highlights this performance gap, which becomes more pronounced as $\alpha$ increases.

Figure 2: (a) provides a simplified illustration of how a subspace is generated. We sample a subset $S$ (denoted by the blue points) from the original point set $P$ (denoted by the black points), and $S$ forms a subspace $\mathtt{span}(S)$ . (b) shows that $\mathtt{span}(S)$ contains a projection of $\mathtt{Med}(P)$ , denoted by $\mathtt{Proj}(\mathtt{Med}(P))$ , which is close to $\mathtt{Med}(P)$ . Moreover, $S$ contains a point ( e.g., $s_{1}$ ) that is within a bounded distance from $\mathtt{Med}(P))$ .

Condition		Cost		Time(s)
$\alpha$	Method	Avg.	Std. Dev.	Avg.	Std. Dev.
$0$ KMed++		8.4054e+07	-	-	-
0.1	Predictor	8.4259e+07	-	-	-
	EFS+	8.4050e+07	115.17	270.47	12.97
	HFH+	8.4049e+07	834.92	749.72	18.47
	NCN	8.4050e+07	181.80	272.22	4.37

Table 2: Performance comparison on Fashion-MNIST dataset with

k=10

and varied

\alpha

Condition		Cost		Time(s)
k	Method	Avg.	Std. Dev.	Avg.	Std. Dev.
10	KMed++	2.0224e+08	-	-	-
	Predictor	2.0427e+08	-	-	-
	EFS+	2.0204e+08	4444.80	362.31	52.30
	HFH+	2.0147e+08	105661.96	42.33	1.91
	NCN	2.0163e+08	109131.95	160.15	14.33

Table 3: Performance comparison on PHY dataset with fixed

\alpha=0.2

and varied

k

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Methods and References	Approximation Ratio	Label Error Range	Time Complexity
Ergun et al. (2022)	$1+20\alpha$	$[\frac{10\log m}{\sqrt{m}},1/7]$	$O(nd\log n)$
Nguyen et al. (2023)	$1+\frac{\alpha}{1-\alpha}+\frac{4\alpha}{(1-2\alpha)(1-\alpha)}$	$[0,1/2)$	$O(nd\log n)$
Huang et al. (2025)	$1+\frac{\alpha}{1-\alpha}+\frac{4\alpha+\alpha\epsilon}{(1-2\alpha)(1-\alpha)}$	$[0,1/2)$	$O(\epsilon^{-1/2}nd\log(kd))$
Huang et al. (2025)	$1+\frac{\alpha}{1-\alpha}+\frac{12\alpha-18\alpha^{2}}{(1-3\alpha-\epsilon)(1-2\alpha-\epsilon)}$	$(0,1/3-\epsilon)$	$O(nd)+\tilde{O}(\epsilon^{-5}kd)$
Sample-and-Search (ours)	$1+\frac{\alpha}{1-\alpha}+\frac{4\alpha+\alpha\epsilon}{(1-2\alpha)(1-\alpha)}$	$[0,1/2)$	$O(2^{O(1/\epsilon)}nd\log k)$

Appendix

Table 4: Comparison results of learning augmented

k

-means algorithms

Condition		Cost		Time(s)		NMI		ARI
$\alpha$	Method	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.
0	K-Med++	2.7492e+07	-	-	-	-	-	-	-
0.1	Predictor	2.7528e+07	-	-	-	-	-	-	-
	EFSplus	2.7406e+07	1109.14	29.87	14.76	0.6631	0.0012	0.5918	0.0026
	HFHplus	2.7401e+07	3929.91	184.22	1.45	0.6562	0.0078	0.5862	0.0107
	NCN	2.7404e+07	3466.13	34.43	7.95	0.6588	0.0050	0.5862	0.0065

Appendix

Table 5: Performance comparison on Cifar10 dataset with fixed

k=10

and varied

\alpha

Condition		Cost		Time(s)		NMI		ARI
$\alpha$	Method	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.
0	K-Med++	8.4054e+07	-	-	-	-	-	-	-
0.1	Predictor	8.4259e+07	-	-	-	-	-	-	-
	EFSplus	8.4050e+07	115.17	270.47	12.97	0.9558	0.0003	0.9642	0.0003
	HFHplus	8.4049e+07	834.92	749.72	18.47	0.9528	0.0036	0.9591	0.0050
	NCN	8.4050e+07	181.80	272.22	4.37	0.9552	0.0008	0.9636	0.0007

Appendix

Table 6: Performance comparison on Fashion-MNIST dataset with fixed

k=10

and varied

\alpha

Condition		Cost		Time(s)		NMI		ARI
$\alpha$	Method	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.
0	K-Med++	1.9797e+08	-	-	-	-	-	-	-
0.1	Predictor	1.9849e+08	-	-	-	-	-	-	-
	EFSplus	1.9800e+08	478.11	392.68	99.57	0.9882	0.0001	0.9900	0.0001
	HFHplus	1.9799e+08	6778.35	39.54	6.32	0.9896	0.0017	0.9913	0.0017
	NCN	1.9800e+08	4363.70	376.60	102.88	0.9883	0.0005	0.9900	0.0005

Appendix

Table 7: Performance comparison on PHY dataset with fixed

k=10

and varied

\alpha

Condition		Cost		Time(s)		NMI		ARI
$\alpha$	Method	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.
0	K-Med++	44696.31	-	-	-	-	-	-	-
0.1	Predictor	44795.92	-	-	-	-	-	-	-
	EFSplus	44695.47	0.78	25.23	6.42	0.9721	0.0030	0.9722	0.0038
	HFHplus	44695.66	0.40	3.58	1.09	0.9682	0.0069	0.9688	0.0071
	NCN	44695.55	0.47	24.97	6.58	0.9739	0.0053	0.9746	0.0056

Appendix

Table 8: Performance comparison on MNIST dataset with fixed

k=10

and varied

\alpha

Condition		Cost		Time(s)		NMI		ARI
k	Method	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.
10	K-Med++	8.4058e+07	-	-	-	-	-	-	-
	Predictor	8.4938e+07	-	-	-	-	-	-	-
	EFSplus	8.4059e+07	305.75	281.82	11.34	0.9460	0.0005	0.9547	0.0006
	HFHplus	8.4053e+07	1129.16	733.73	24.48	0.9419	0.0035	0.9489	0.0057
	NCN	8.4059e+07	811.26	285.90	2.63	0.9455	0.0015	0.9541	0.0016

Appendix

Table 9: Performance comparison on Fashion-MNIST dataset with fixed

\alpha=0.2

and varied

k

Condition		Cost		Time(s)		NMI		ARI
k	Method	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.
10	K-Med++	2.0224e+08	-	-	-	-	-	-	-
	Predictor	2.0428e+08	-	-	-	-	-	-	-
	EFSplus	2.0205e+08	4444.80	362.31	52.30	0.9369	0.0002	0.9192	0.0003
	HFHplus	2.0147e+08	105661.96	42.33	1.91	0.9289	0.0139	0.9036	0.0240
	NCN	2.0163e+08	109131.95	160.15	14.33	0.9173	0.0097	0.8866	0.0150

Appendix

Table 10: Performance comparison on PHY dataset with fixed

\alpha=0.2

and varied

k

Condition		Cost		Time(s)		NMI		ARI
k	Method	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.
10	K-Med++	44695.78	-	-	-	1.0000	-	1.0000	-
	Predictor	45101.25	-	-	-	-	-	-	-
	NCN	44700.26	0.66	4.68	0.36	0.9738	0.0031	0.9768	0.0026
	Fast-Estimation	44698.33	0.78	2.18	0.15	0.9655	0.0037	0.9670	0.0044
	Ngu	44701.73	0.97	4.53	0.44	0.9745	0.0016	0.9774	0.0013

Appendix

Table 11: Performance comparison on MNIST dataset with fixed

\alpha=0.2

and varied

k

Condition		Cost		Time(s)		NMI		ARI
$\alpha$	Method	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.
0	KMe++	3.9481e+11	-	-	-	-	-	-	-
0.1	Predictor	3.9680e+11	-	-	-	-	-	-	-
	EFSplus	4.2240e+11	6.5569e+07	7.86	0.22	0.8930	0.0004	0.8853	0.0005
	NCN	3.9869e+11	0	127.44	6.20	0.8980	0.0000	0.8943	0.0000
	Fast-Estimation	3.9747e+11	5.5532e+08	7.62	0.29	0.8777	0.0093	0.8681	0.0122

Appendix

Table 12: Performance comparison on CIFAR-10 dataset with fixed

k=10

and varied

\alpha

Condition		Cost		Time(s)		NMI		ARI
$\alpha$	Method	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.
0	K-Med++	1.2450e+11	-	-	-	-	-	-	-
0.1	Predictor	1.2613e+11	-	-	-	-	-	-	-
	EFSplus	1.2669e+11	7.7786e+06	2.917	0.556	0.8991	0.0002	0.8898	0.0004
	NCN	1.2567e+11	0.00	3.367	0.814	0.9510	0.0000	0.9570	0.0000
	Fast-Estimation	1.2575e+11	8.3179e+07	2.637	0.791	0.9325	0.0115	0.9339	0.0142

Appendix

Table 13: Performance comparison on Fashion-MNIST dataset with fixed

k=10

and varied

\alpha

Condition		Cost		Time(s)		NMI		ARI
$\alpha$	Method	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.
0	KMe++	1.1653e+06	-	-	-	-	-	-	-
0.1	Predictor	1.1790e+06	-	-	-	-	-	-	-
	EFSplus	1.1867e+06	1057.86	0.080	0.050	0.9687	0.0034	0.9714	0.0033
	NCN	1.1747e+06	0.00	0.057	0.035	0.9778	0.0000	0.9801	0.0000
	Fast-Estimation	1.1757e+06	315.60	0.087	0.037	0.9770	0.0017	0.9793	0.0021

Appendix

Table 14: Performance comparison on MNIST dataset with fixed

k=10

and varied

\alpha

Condition		Cost		Time(s)		NMI		ARI
$\alpha$	Method	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.
0	K-Med++	1.0147e+12	-	-	-	-	-	-	-
0.1	Predictor	1.1078e+12	-	-	-	-	-	-	-
	EFSplus	1.0230e+12	6.5840e+08	0.357	0.138	0.9769	0.0052	0.9758	0.0066
	NCN	1.0167e+12	0.00	1.083	0.274	0.9937	0.0000	0.9953	0.0000
	Fast-Estimation	1.0239e+12	3.2252e+09	0.284	0.090	0.9776	0.0063	0.9778	0.0079

Appendix

Table 15: Performance comparison on PHY dataset with fixed

k=10

and varied

\alpha

Condition		Cost		Time(s)		NMI		ARI
k	Method	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.
10	K-Med++	7.8584e+10	-	-	-	-	-	-	-
	Predictor	8.0164e+10	-	-	-	-	-	-	-
	EFSplus	7.9181e+10	2.64e+06	1.347	0.025	0.8625	0.0008	0.8403	0.0008
	NCN	7.9408e+10	0.00	3.678	0.030	0.8282	0.0000	0.7948	0.0000
	Fast-Estimation	7.9677e+10	2.54e+08	1.345	0.022	0.7905	0.0183	0.7350	0.0259

Appendix

Table 16: Performance comparison on CIFAR-10 dataset with fixed

\alpha=0.2

and varied

k

Condition		Cost		Time(s)		NMI		ARI
k	Method	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.
10	K-Med++	1.2454e+11	-	-	-	-	-	-	-
	Predictor	1.3036e+11	-	-	-	-	-	-	-
	EFSplus	1.3029e+11	1.07e+07	1.227	0.004	0.8876	0.0005	0.8857	0.0006
	NCN	1.2941e+11	0.00	1.446	0.002	0.9215	0.0000	0.9266	0.0000
	Fast-Estimation	1.2933e+11	6.37e+08	1.203	0.003	0.9091	0.0214	0.9105	0.0267

Appendix

Table 17: Performance comparison on Fashion-MNIST dataset with fixed

\alpha=0.2

and varied

k

Condition		Cost		Time(s)		NMI		ARI
k	Method	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.	Avg.	Std. Dev.
10	K-Med++	1.0147e+12	-	-	-	-	-	-	-
	Predictor	1.3965e+12	-	-	-	-	-	-	-
	EFSplus	1.0562e+12	4.32e+09	0.109	0.000	0.9591	0.0045	0.9523	0.0068
	NCN	1.0209e+12	0.00	0.411	0.001	0.9829	0.0000	0.9834	0.0000
	Fast-Estimation	1.0657e+12	1.48e+10	0.096	0.000	0.9530	0.0149	0.9439	0.0218

Appendix

Table 18: Performance comparison on PHY dataset with fixed

\alpha=0.2

and varied

k

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 347 papers

Learning-Augmented Algorithms for $k$ -median via Online Learning
Mar 18, 2026Anish Hebbar, Rong Ge, Amit Kumar +1Learning-Augmented Algorithms Clustering
Duke University · IIT Delhi
Sensitivity Sampling with Predictions for k-Means Clustering
Jul 6, 2026Cristian Boldrin, Fabio VandinClustering Importance Sampling
University of Padova, Padova, Italy
Faster and Simpler Greedy Algorithm for $k$ -Median and $k$ -Means
Jul 15, 2024Max Dupré la Tour, David SaulpicClustering Approximation Algorithms

Mar 18, 2026J/K move · Enter open · S save

Learning-Augmented Algorithms for $k$ -median via Online Learning

Anish Hebbar, Rong Ge, Amit Kumar, Debmalya Panigrahi

Duke University · IIT Delhi

Learning-Augmented Algorithms Clustering Online Learning

Open paper AskPDF arXiv

The field of learning-augmented algorithms seeks to use ML techniques on past instances of a problem to inform an algorithm designed for a future instance. In this paper, we introduce a novel model for learning-augmented algorithms inspired by online learning. In this model, we are given a sequence of instances of a problem and the goal of the learning-augmented algorithm is to use prior instances to propose a solution to a future instance of the problem. The performance of the algorithm is measured by its average performance across all the instances, where the performance on a single instance is the ratio between the cost of the algorithm's solution and that of an optimal solution for that instance. We apply this framework to the classic

k

-median clustering problem, and give an efficient learning algorithm that can approximately match the average performance of the best fixed

k

-median solution in hindsight across all the instances. We also experimentally evaluate our algorithm and show that its empirical performance is close to optimal, and also that it automatically adapts the solution to a dynamically changing sequence.

Abstract

Clustering

Explore similar work

Learning-Augmented Algorithms for kkk-median via Online Learning

Sensitivity Sampling with Predictions for k-Means Clustering

Faster and Simpler Greedy Algorithm for kkk-Median and kkk-Means

Learning-Augmented Algorithms for $k$ -median via Online Learning

Faster and Simpler Greedy Algorithm for $k$ -Median and $k$ -Means