Open Source
K-Means as the Zero-Temperature Limit of Normalized RBF Assignments: Rates, Trajectories, and Exact Recovery with Entmax
arXiv stat.TH0 views
arXiv:2603.04625v2 Announce Type: replace-cross Abstract: K-Means is usually treated as a discrete procedure outside gradient-based learning, whereas normalized radial basis function (RBF) layers are smooth. We make precise the sense in which K-Means is the zero-temperature limit of such a layer. Relaxing the K-Means assignments to the simplex with a Shannon entropy penalty yields the normalized Gaussian RBF responsibilities and a reduced objective $F_\sigma$ with $0\le J-F_\sigma\le 2n\sigma^2\log k$, so $F_\sigma$ $\Gamma$-converges to the K-Means distortion $J$. We keep four levels of statement apart. For the objective, minimal values and minimizers converge, and above the critical temperature $\sigma^2=\lambda_{\max}$ all centroids at the mean form a strict local minimizer. For optimization, alternating minimization is a preconditioned gradient method on $F_\sigma$ whose hard limit is Lloyd's algorithm. For one update, under a margin $\Delta_{\min}>0$, the soft centroid map approaches Lloyd's at rate $O(e^{-\Delta_{\min}/2\sigma^2})$. For fixed points and trajectories, every nondegenerate Lloyd fixed point has a nearby soft local minimizer, and soft iterates keep Lloyd's partitions while Lloyd's path keeps a margin. With the Tsallis entropy of order 3/2, Entmax-1.5 recovers the hard assignments, the Lloyd update and, along a path with margin, Lloyd's trajectory exactly for $\sigma\le\sqrt{\Delta_{\min}}/2$, a sharp threshold. Experiments on sixteen datasets confirm every bound, rate and threshold, and the trajectory statements at the edge of their hypotheses. As a differentiable K-Means term, $F_\sigma$ shows the predicted effects: its gradients do not vanish at low temperature, its closed-form centroid update needs no learning rate, a fixed temperature crosses the critical one as representations contract, and soft responsibilities keep a vector-quantized codebook in use.
Source:https://arxiv.org/abs/2603.04625PreviousNear-Optimal Regret for KL-Regularized Multi-Armed BanditsNextConsistent but Biased: Chair Personas Trade Noise for Bias in Multi-Agent Clinical Decisions
Related posts
Anime Expeditions Codes (November 2026)
0FOSS Bytes

Karpathy built HackerTube in 2 hours. I rebuilt it in the open and measured it
0dev.to AI
Show HN: Poinky – Claude Code you talk to, that sees your screen
0Hacker News Show
Show HN: DeskAccess – Open-source remote access for Raspberry Pi
0Hacker News Show
Show HN: The Public Eye – Agentic search for congressional bill legibility
0Hacker News Show
NASA’s Perseverance Mars rover breaks historic record after traveling 28 miles
0Science Daily Tech