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.