Abstract:Motivated by the increasing availability of low- and mixed-precision arithmetic on modern hardware, we develop mixed-precision variants of Lloyd's algorithm for k-means clustering. The main ingredient is a family of mixed-precision kernels for Euclidean distance computation. These kernels are guided by rounding-error analysis and use a simple reliability test to decide whether the expanded distance formula can be evaluated safely with low precision or a higher-precision correction by the direct distance formula is required. Thus, most distance computations can be carried out with low precision, while high-precision arithmetic is used selectively when cancellation may lead to a loss of accuracy. We evaluate the proposed methods on large-scale distance-computation benchmarks, synthetic clustering problems, and image-segmentation tasks. The experiments verify that the mixed-precision kernels on GPUs can substantially improve performance while retaining the accuracy and convergence behavior of higher-precision baselines. In particular, our CUDA implementations achieve orders-of-magnitude speedups over the CPU implementation in \texttt{scikit-learn} and up to $4\times$ faster than the IEEE double-precision \texttt{cdist} routine of \texttt{PyTorch} on NVIDIA A100 GPU, while providing improved numerical robustness in cancellation-prone regimes. The resulting mixed-precision k-means methods are effective for clustering and image segmentation, although the observed gains depend on the dataset, feature dimension, and number of clusters. These results demonstrate that mixed-precision distance kernels can offer a useful trade-off between performance and accuracy for k-means clustering and suggest that similar ideas may be beneficial for other distance-based machine learning methods.
| Subjects: | Numerical Analysis (math.NA) |
| MSC classes: | 65G50, 62H30, 68T05, 68W10 |
| Cite as: | arXiv:2407.12208 [math.NA] |
| (or arXiv:2407.12208v3 [math.NA] for this version) | |
| https://doi.org/10.48550/arXiv.2407.12208 arXiv-issued DOI via DataCite |
From: Xiaobo Liu [view email]
[v1]
Tue, 16 Jul 2024 22:48:35 UTC (5,736 KB)
[v2]
Sat, 18 Apr 2026 15:51:30 UTC (5,267 KB)
[v3]
Mon, 25 May 2026 12:19:39 UTC (59 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。