K-Means as the Zero-Temperature Limit of Normalized RBF Assignments: Rates, Trajectories, and Exact Recovery with Entmax

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.

arXiv comment63 pages, 14 figures, 17 tables