analiza aiqbench
This paper gives a theoretical bridge between K-Means clustering and differentiable neural layers. It shows that entropy-regularized soft assignments converge to Lloyd's algorithm as temperature goes to zero, with explicit rates, a critical-temperature phenomenon, and an exact-recovery threshold under Entmax-1.5. For ML readers, the practical takeaways are that K-Means-style codebooks can be trained with gradients that don't vanish, and that the temperature choice determines whether soft training reproduces hard clustering.
K-Means as the Zero-Temperature Limit of Normalized RBF Assignments: Rates, Trajectories, and Exact Recovery with Entmax
arXiv:2603.04625v2 Announce Type: replace 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.
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.
Machine Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML)
arXiv:2603.04625 [cs.LG]
(or arXiv:2603.04625v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2603.04625 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 356 cuvinte