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

Felipe de Jesus Felix Arredondo; Manuel Alejandro Ucan Puc; Carlos Astengo Nouguez

cs.LGMar 4, 2026

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

Authors: Felipe de Jesus Felix Arredondo, Manuel Alejandro Ucan Puc, Carlos Astengo Nouguez

Organizations: School of Engineering and Sciences, Tecnológico de Monterrey, Monterrey, Mexico · School of Engineering and Sciences, Tecnológico de Monterrey, Guadalajara, Mexico

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_σ$ with $0\le J-F_σ\le 2nσ^2\log k$ , so $F_σ$ $Γ$ -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 $σ^2=λ_{\max}$ all centroids at the mean form a strict local minimizer. For optimization, alternating minimization is a preconditioned gradient method on $F_σ$ whose hard limit is Lloyd's algorithm. For one update, under a margin $Δ_{\min}>0$ , the soft centroid map approaches Lloyd's at rate $O(e^{-Δ_{\min}/2σ^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 $σ\le\sqrt{Δ_{\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_σ$ 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.

Figures & tables

Figure 1: The results of the paper along the temperature axis, on three Gaussian clusters in the plane (

n=300

k=3

). Top: fixed points of the alternating updates at the temperatures marked by triangles, reached by deterministic annealing; each point is colored by its responsibilities, as in Figure 2 , and circled when they are not one-hot to within

10^{-12}

; white disks are the centroids. Above the critical temperature

\lambda_{\max}

, the largest eigenvalue of the data covariance, every Softmax centroid sits at the data mean (Proposition 9 ). Between the two thresholds the assignments are soft, the reduced objective is within

2n\sigma^{2}\log k

of the K-Means distortion (Theorem 4 ), and the alternating update is a preconditioned gradient step (Section 5 ). Below

\sigma_{\mathrm{id}}^{2}=\Delta_{\min}/4

, with

\Delta_{\min}

the margin of the K-Means fixed point, Softmax remains soft near the cluster boundaries, whereas Entmax-1.5 is exactly hard and its fixed point is Lloyd’s (crosses), as are its iterates (Section 6 ).

Level	Shannon entropy (Softmax)	Tsallis entropy of order $3/2$ (Entmax-1.5)
Objective	$0\leq J-F_{\sigma}\leq 2n\sigma^{2}\log k$ , hence $\Gamma$ -convergence (Thm. 4 ); gap $O(n\sigma^{2}e^{-\beta})$ under a margin (Prop. 8 )	$F_{\sigma}<F_{\sigma}^{(3/2)}\leq J$ , gap at most $\tfrac{8}{3}n\sigma^{2}(1-1/\sqrt{k})$ ; $F_{\sigma}^{(3/2)}=J$ for $\sigma\leq\sigma_{\mathrm{id}}$ (Props. 6 , 7 , 8 )
Optimization	alternating update $=$ preconditioned gradient step (EM); descent, whole-sequence convergence (Thm. 13 )	descent with sufficient decrease (Prop. 15 )
One update	$\\|T_{\sigma}-T_{\mathrm{Lloyd}}\\|=O(e^{-\beta})$ with explicit constants (Thm. 18 )	$T^{(3/2)}_{\sigma}=T_{\mathrm{Lloyd}}$ for $\sigma\leq\sigma_{\mathrm{id}}$ , sharp (Cor. 21 )
Fixed points	unique soft fixed point within $O(e^{-\beta})$ of each nondegenerate Lloyd fixed point (Thm. 24 )	Lloyd fixed points with margin $\geq 4\sigma^{2}$ are fixed points
Trajectories	same partitions as Lloyd while its iterates keep a margin (Thm. 25 )	identical iterates while Lloyd’s keep a margin $\geq 4\sigma^{2}$ (Cor. 26 )

Table 1: The statements of the paper, by level, with

\beta=\Delta_{\min}/(2\sigma^{2})

and

\sigma_{\mathrm{id}}=\sqrt{\Delta_{\min}}/2

. The trajectory statements require their margin condition along Lloyd’s path; the others hold at any configuration with a positive margin, or everywhere for the objective bounds.

Figure 2: Softmax (top) and Entmax-1.5 (bottom) responsibilities in the plane for three fixed centroids (white circles), at three temperatures. Each point is colored by the responsibility-weighted mix of the three cluster colors, so pure colors are hard assignments and blends are soft ones. Top: outside the dotted contour the Softmax responsibilities are within $10^{-6}$ of one-hot, and no point is exactly one-hot; at $\sigma^{2}=0.6$ no point of the window is within $10^{-6}$ . Bottom: outside the solid contours the Entmax-1.5 responsibilities are exactly one-hot. The soft region is the band of points closer than $2\sigma^{2}/\|\mu_{j}-\mu_{\ell}\|$ to a bisector (Proposition 22 ). Softmax responsibilities are within $\varepsilon$ of one-hot only outside a band wider by the factor $\tfrac{1}{2}\log((k-1)/\varepsilon)$ , about $7$ for $\varepsilon=10^{-6}$ , and exactly one-hot nowhere.

Figure 3: The objectives on one-dimensional data (

n=200

points in two symmetric groups around

\pm 2

) and the configurations

\mu=(-a,a)

k=2

. Left: per observation,

F_{\sigma}<F_{\sigma}^{(3/2)}\leq J

\sigma^{2}=\lambda_{\max}/4

(Proposition 7 ), with

F_{\sigma}

inside the band

[J-2\sigma^{2}\log k,\,J]

of Theorem 4 . At

a=0

the two centroids coincide and

F_{\sigma}

attains the lower edge of the band; near the K-Means minimizer the three objectives almost coincide, as Proposition 8 predicts. Right: the minimizer of

F_{\sigma}

over these configurations against

\sigma^{2}/\lambda_{\max}

. Above the critical temperature

\sigma^{2}=\lambda_{\max}

both centroids sit at the data mean (Proposition 9 ); below it they split and approach the K-Means minimizer (dashed) as

\sigma\to 0

Figure 4: One step size against the preconditioned step, on two unbalanced clusters (

270

and

30

points,

k=2

\sigma^{2}=0.05

). Gradient descent on

F_{\sigma}

uses the common step

1/(2\max_{j}m_{j}^{\sigma})

, the largest that is safe for the heavy cluster; the alternating update uses the step

1/(2m_{j}^{\sigma})

of each cluster. Left: centroid paths from the same initialization. Right: distance of each centroid to the fixed point. The alternating update reaches it in two iterations; with one step size the light centroid contracts only by the factor

1-m_{\mathrm{light}}/m_{\mathrm{heavy}}\approx 0.89

per iteration.

Figure 5: The responsibility of the nearest centroid for one observation with

k=3

whose two competitors both lie at its margin

\Delta_{i}

, against

\beta=\Delta_{i}/(2\sigma^{2})

. Left: Softmax approaches the hard assignment only asymptotically, while Entmax-1.5 reaches it exactly at

\beta=2

, that is, at

\sigma=\sqrt{\Delta_{i}}/2

(Lemma 19 ). Right: the same on a logarithmic scale; the Softmax error follows the bound

(k-1)e^{-\beta}

of Lemma 17 , which is tight for this observation, and the Entmax-1.5 error is exactly zero for every

\beta\geq 2

Figure 6: Trajectories from one initialization (open circles) on three Gaussian clusters (

n=240

k=3

), with

\delta

the smallest margin along Lloyd’s path. Left: Lloyd’s iterates (black), alternating Entmax-1.5 at a temperature with

\sigma\leq\sigma_{\mathrm{id}}

at every Lloyd iterate, whose iterates coincide with Lloyd’s (Corollary 26 ), and alternating Softmax at

\delta/(2\sigma^{2})=1

, outside the hypotheses of Theorem 25 , which still follows Lloyd’s path closely. Right: the largest discrepancy from Lloyd’s iterates over the whole trajectory, against

\delta/(2\sigma^{2})

. It decays exponentially for Softmax and is exactly zero for Entmax-1.5 from

\delta/(2\sigma^{2})=2

on (markers at the bottom).

Dataset	Regime	Parameters
Gaussian blobs	Separated Euclidean clusters	std $0.6$
Two moons	Nonlinear manifold	noise $0.05$
Spiral	Nonconvex polar structure	radius $3$ , noise $0.05$
Circles	Radial separation	factor $0.5$ , noise $0.05$
Separation	Isotropic blobs, set gap	std $0.35$ , $\delta\in\{0.5,1,2,4,8\}$
Blobs, $d$ -dim.	Isotropic blobs in $d$ dim.	std $1$ , centers $\mathcal{N}(0,6^{2}I)$ , $d\in\{5,10,50\}$

Table 2: Datasets. The synthetic datasets have

n=300

points;

n

d

and

k

for every dataset are listed in Table 7 (Appendix D ). All datasets except the separation sweep are standardized to zero mean and unit variance per coordinate; the separation sweep is left unscaled so that the gap

\delta

controls the margin directly.

Panel of Figure 7 — Figure 7: Softmax rate diagnostics on the theoretically dictated axes. ( 7(a) ) Gaussian blobs: responsibility and centroid-map errors, averaged over the admissible reference runs at each $\beta$ , on a $\log$ scale against $1/(2\sigma^{2})=\beta/\widetilde{\Delta}_{\min}$ , with $\widetilde{\Delta}_{\min}$ the median margin over runs, together with the analytic bounds ( 58 )–( 59 ). The theory predicts straight lines of slope $-\Delta_{\min}$ ; the panel reports the median over runs of the per-run fitted slope divided by that run’s $\Delta_{\min}$ , which is predicted to equal $-1$ . At the coldest temperatures $E_{T}$ is exactly zero in floating point and cannot be drawn on the logarithmic axis. ( 7(b) ) Mean responsibility error against the margin-normalized inverse temperature $\beta=\Delta_{\min}/(2\sigma^{2})$ for all 16 datasets, one line per dataset, colored by family; the dashed line is the bound $(k-1)e^{-\beta}$ for the largest $k$ used ( $k=10$ ). All curves collapse onto a single line of slope $-1$ , as the margin normalization implies.

Figure 8: Entmax-

1.5

finite identification: fraction of admissible reference runs whose Entmax responsibilities are exactly one-hot (error at most

\varepsilon_{\mathrm{id}}

), against

\beta

, for all 16 datasets (3,196 runs), colored by family. The responsibility and centroid-map errors are predicted to vanish exactly for

\beta\geq 2

, i.e.

\sigma\leq\sigma_{\mathrm{id}}=\sqrt{\Delta_{\min}}/2

, and, by the sharpness in Remark 28 , not for any

\beta<2

: a step rather than a decay. The dashed line marks

\beta=2

and the shaded region the identification regime. The fraction is observed only on the

\beta

grid, so it is drawn as markers; families are offset horizontally by a few percent so that coincident markers remain visible.

Figure 9: Dependence on the sample size. Left: median and interquartile band of

\Delta_{\min}

against

n

, at the population configuration

\mu^{\star}

(solid) and at the sample’s Lloyd fixed point (dotted); the dashed line has slope

-1

. Right: mean fraction

N_{\sigma}/n

of observations not identified by Entmax-

1.5

\mu^{\star}

, for

4\sigma^{2}

equal to

0.01

and

0.1

times the median observation margin

\widetilde{\Delta}

; thin horizontal lines: the bound of Proposition 22 (d) for the mixtures.

Figure 10: Value-function

\Gamma

-convergence on Gaussian blobs. The gaps

J-F_{\sigma}

and

J-F_{\sigma}^{(3/2)}

at the Lloyd reference configurations, averaged over runs at each temperature, against

\sigma^{2}

, on logarithmic axes, overlaid with the uniform ceilings

2n\sigma^{2}\log k

and

\tfrac{8n\sigma^{2}}{3}(1-1/\sqrt{k})

. The ceilings grow linearly in

\sigma^{2}

, whereas the observed Softmax gap decays exponentially in

\beta=\Delta_{\min}/(2\sigma^{2})

(Proposition 8 ). The Entmax gap lies strictly below the Softmax gap at every temperature (Proposition 7 ), and it is exactly zero for

\sigma\leq\sigma_{\mathrm{id}}

, so it is not drawn there.

Method	Iter.	Conv. %	ms/iter.	Mono. %	Suff. %	$\\|\nabla F_{\sigma}\\|$	$J<J_{\mathrm{L}}$ %	$J>J_{\mathrm{L}}$ %
Lloyd	$5$	$100.0$	$0.0323$	$100.0$	–	–	–	–
Alt. Softmax	$8$	$100.0$	$0.0426$	$100.0$	$100.0$	$7.06\times 10^{-6}$	$23.3$	$1.9$
GD on $F_{\sigma}$	$11$	$93.8$	$0.0927$	$100.0$	–	$2.64\times 10^{-5}$	$23.0$	$9.9$
Alt. Entmax	$6$	$100.0$	$0.668$	$100.0$	$100.0$	–	$16.6$	$2.3$

Table 3: Per-method summary pooled over all datasets (3,196 paired runs per method). Iter.: median iterations. Conv.: percentage of runs that met the stopping criterion before the cap. ms/iter.: median wall-clock time per iteration, counting only each method’s own update step, with the runs executed one at a time on an otherwise idle laptop CPU. Mono.: percentage of runs whose own objective (

J

for Lloyd,

F_{\sigma}

for alternating Softmax and gradient descent,

F_{\sigma}^{(3/2)}

for alternating Entmax) never increased. Suff.: percentage of steps satisfying ( 40 ).

\|\nabla F_{\sigma}\|

: median terminal gradient norm, for the two methods that minimize

F_{\sigma}

J\lessgtr J_{\mathrm{L}}

: percentage of runs whose hard distortion, after a Lloyd polish of the terminal centroids, is lower (respectively higher) than that of Lloyd’s algorithm from the same initialization by more than a relative

10^{-6}

; the polish removes the

O(q(\sigma))

offset of soft fixed points, so a difference means that another basin was reached. Clusters left without mass in a step: 0 in total.

Figure 11: Fraction of runs, over the sixteen datasets, in which each soft method induces the same hard partition as Lloyd’s algorithm at every iteration, against the temperature

\beta=\widetilde{\Delta}_{\min}/(2\sigma^{2})

. Dashed: fraction of runs in which every Lloyd iterate has margin at least

4\sigma^{2}

, the hypothesis of Corollary 26 ; in all of them alternating Entmax follows Lloyd’s path.

Panel of Figure 12 — Figure 12: Deterministic-annealing paths of alternating Softmax on four planar geometries ( $k=3$ for blobs and spiral, $k=2$ for moons and circles). Open circle: all centroids at $\sigma=2$ , where they coincide at the data mean. Lines: centroid positions as $\sigma$ decreases geometrically to $0.02$ , each temperature warm-started from the previous one. Filled circles: end of the schedule, an exact fixed point of Lloyd’s map in every panel. Hollow stars: Lloyd’s solution from the k-means++ initialization that starts the schedule. On blobs and moons the two coincide; on spiral and circles annealing reaches a different K-Means fixed point, with lower distortion.

Figure 13: Relative deviation of the per-observation gradients of

F_{\sigma}

F_{\sigma}^{(3/2)}

and

D_{\sigma}

from that of the hard distortion

J

(the maximum over observations, then the median over the

3{,}196

reference configurations), and the largest Frobenius norm of the Softmax Jacobian, against

\beta=\Delta_{\min}/(2\sigma^{2})

. Missing points are exact zeros.

Method	MNIST	Fashion-MNIST	USPS	CIFAR-10	STL-10	Var.
AE + K-Means	$0.783\pm 0.013$	$0.498\pm 0.020$	$0.712\pm 0.006$	$0.596\pm 0.028$	$0.581\pm 0.030$	$1$
DEC	$0.790\pm 0.015$	$0.527\pm 0.015$	$0.780\pm 0.008$	$0.623\pm 0.045$	$0.628\pm 0.035$	$1.2$
IDEC	$0.818\pm 0.013$	$\mathbf{0.535\pm 0.020}$	$\mathbf{0.789\pm 0.004}$	$\mathbf{0.648\pm 0.049}$	$\mathbf{0.638\pm 0.036}$	$1.5$
DCN (hard)	$0.814\pm 0.024$	$0.475\pm 0.010$	$0.725\pm 0.013$	$0.524\pm 0.060$	$0.470\pm 0.043$	$0.14$
$D_{\sigma}$	$0.828\pm 0.023$	$0.462\pm 0.017$	$0.679\pm 0.042$	$0.494\pm 0.069$	$0.467\pm 0.052$	$0.26$
$F_{\sigma}$ (ours)	$0.830\pm 0.014$	$0.454\pm 0.020$	$0.668\pm 0.023$	$0.574\pm 0.054$	$0.580\pm 0.041$	$0.047$

Table 4: End-to-end clustering accuracy (ACC) with a

d

-500-500-2000-10 autoencoder, mean

\pm

standard deviation over 5 seeds; best non-ablation method in bold. MNIST, Fashion-MNIST and USPS use pixels, CIFAR-10 and STL-10 the features of an ImageNet-pretrained ResNet-50. All methods start from the same pretrained network and the same K-Means centroids.

D_{\sigma}

: expected soft distortion, the objective type of Deep k-Means. Below the rule, ablations of

F_{\sigma}

: centroids trained by Adam instead of the closed-form update, no reconstruction loss, temperature fixed at its initial value, and temperature annealed. Var.: total variance of the embeddings after fine-tuning divided by its value before (median over datasets and seeds). NMI and ARI are in Table 14 .

Figure 14: Every run of the critical-temperature check (five datasets, three seeds): the smallest value of

\lambda_{\max}(C_{Z})/\sigma^{2}

during fine-tuning against the number of clusters used at the end (left, jittered vertically) and the accuracy (right). Shaded:

\sigma^{2}>\lambda_{\max}(C_{Z})

, where the configuration with all centroids at the mean is a strict local minimizer of

F_{\sigma}

(Proposition 9 ). With a fixed temperature the contracting representation crosses this threshold on four datasets and the clustering collapses to one or two clusters; with the temperature tied to the scale of the representation no run crosses it. The Fashion-MNIST runs with a fixed temperature (squares at

5

7

) keep two clusters without crossing it. Hollow markers:

F_{\sigma}^{(3/2)}

, whose smallest ratio coincides with that of

F_{\sigma}

in every run.

Assignment	Update	MSE	Perplexity	Used
Hard	Gradient	$4.16\pm 0.09$	$323\pm 47$	$372$
Hard + reset	Gradient	$3.96\pm 0.16$	$436\pm 4$	$512$
Hard	Closed form	$4.98\pm 0.17$	$92\pm 18$	$104$
Hard + reset	Closed form	$3.98\pm 0.10$	$439\pm 5$	$512$
Softmax	Gradient	$3.93\pm 0.19$	$448\pm 4$	$511$
Softmax	Closed form	$4.06\pm 0.16$	$446\pm 13$	$504$

Table 5: Codebook learning in a VQ-VAE on CIFAR-10 (

K=512

codes of dimension 64), mean

\pm

standard deviation over 3 seeds. Assignment: responsibilities used to update the codebook (the forward pass always quantizes to the nearest code). Update: gradient step on the codebook loss, or closed-form update of the codes as responsibility-weighted means maintained by exponential moving averages. Hard + reset: the standard dead-code remedy, which moves every code whose moving-average usage falls below one assignment per step to a random encoder output every 100 steps ( Dhariwal et al., 2020 ) . MSE: test reconstruction error (

\times 10^{-3}

). Perplexity and Used: exponential of the entropy of the code frequencies on the test set and number of codes used.

$n$	$k$	Iter.	scikit-learn	FAISS	Lloyd (GPU)	Lloyd	Softmax	Entmax	$\|\Delta J\|$
			Time to the fixed point			Time per iteration (GPU)
$10{,}000$	$10$	$3$	$11.7$	$2.78$	$1.79$	$0.596$	$0.530$	$1.10$	$2.6\times 10^{-13}$
$10{,}000$	$100$	$3$	$8.09$	$6.93$	$3.23$	$1.08$	$0.610$	$1.06$	$2.0\times 10^{-14}$
$10{,}000$	$1{,}000$	$4$	$35.2$	$51.3$	$4.32$	$1.08$	$2.01$	$12.3$	$1.2\times 10^{-15}$
$100{,}000$	$10$	$3$	$34.7$	$26.5$	$3.33$	$1.11$	$0.911$	$5.18$	$2.6\times 10^{-12}$
$100{,}000$	$100$	$3$	$31.4$	$58.3$	$5.59$	$1.86$	$2.66$	$15.0$	$2.7\times 10^{-13}$

Table 6: Cost at scale on mixtures of

k

Gaussians in

d=64

, in float32, from the same initial centroids; median over 3 calls after one warm-up call. Left: total time (ms) for three implementations of Lloyd’s algorithm to reach the same fixed point, in the number of iterations (Iter.) after which scikit-learn stops because the assignments no longer change; FAISS and our GPU Lloyd update run exactly that number, and all three produce the same iterates. Right: time per iteration (ms) on the GPU of Lloyd’s update and of the alternating Softmax and Entmax-1.5 updates, the soft updates over

T=20

iterations. Entmax-1.5 uses the exact sorting-based threshold. CPU: scikit-learn and FAISS with all threads of a 24-thread laptop CPU; GPU: our implementation on an RTX 5070 Ti Laptop GPU, with the data resident on the device.

|\Delta J|

: relative difference between the final distortion of the GPU Lloyd update and that of scikit-learn.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	$n$	$d$	$k$	Adm./ $M$	$\Delta_{\min}$ (med.)	$\Delta_{\min}$ (min)	$\rho$ (med.)	$B$ (med.)
Blobs	300	2	3	200/200	$0.0993$	$3.35\times 10^{-3}$	$0.333$	$3.54$
Moons	300	2	2	200/200	$0.0780$	$0.0780$	$0.490$	$2.93$
Spiral	300	2	3	200/200	$0.0148$	$2.36\times 10^{-5}$	$0.263$	$3.59$
Circles	300	2	2	200/200	$0.0254$	$2.37\times 10^{-4}$	$0.493$	$2.82$
Separation, $\delta{=}0.5$	300	2	3	200/200	$3.87\times 10^{-3}$	$9.05\times 10^{-5}$	$0.280$	$1.81$
Separation, $\delta{=}1$	300	2	3	200/200	$0.0291$	$0.0120$	$0.323$	$2.78$

Appendix

Table 7: Datasets, admissibility and the governing constants. Admissible runs are those whose Lloyd reference configuration has

\Delta_{\min}>0

and no empty cluster.

\Delta_{\min}

, the balance ratio

\rho=\min_{j}|S_{j}|/n

and the radius

B

are computed at each admissible reference configuration and summarized over runs.

Dataset	Slope $E_{r}$	Slope $E_{T}$	Slope $G_{\sigma}$	Runs	Checks	Id. $\beta<2$
Blobs	$-0.998$ [0.000]	$-1.005$ [0.000]	$-1.002$ [0.000]	200	$1.000$	$0.000$
Moons	$-0.998$ [0.000]	$-0.987$ [0.000]	$-1.002$ [0.000]	200	$1.000$	$0.000$
Spiral	$-0.998$ [0.000]	$-1.000$ [0.013]	$-1.002$ [0.005]	200	$1.000$	$0.000$
Circles	$-0.998$ [0.000]	$-0.997$ [0.018]	$-1.001$ [0.010]	200	$1.000$	$0.000$
Separation, $\delta{=}0.5$	$-0.998$ [0.000]	$-0.998$ [0.031]	$-1.008$ [0.009]	200	$1.000$	$0.000$
Separation, $\delta{=}1$	$-0.998$ [0.000]	$-1.001$ [0.005]	$-1.008$ [0.008]	200	$1.000$	$0.000$

Appendix

Table 8: Rates and bound checks. Slopes: per-run least-squares slope of

\log E_{r}

\log E_{T}

and

\log(G_{\sigma}/\sigma^{2})

against

\beta

over

\beta\geq 2

, with

E_{r}

and

E_{T}

censored at the declared tolerance; median [interquartile range] over runs, predicted

-1

. Runs: number of admissible runs fitted. Checks: smallest, over the seven bound checks of Section 7.1 (responsibility and centroid-map bounds, uniform and margin estimates of the value gaps, exact Entmax gap for

\beta\geq 2

, and

G_{\mathrm{ent}}<G_{\sigma}

), of the fraction of records satisfying the check within its tolerance. Id. viol.: records with

\beta\geq 2

that are not exactly identified. Id.

\beta<2

: fraction identified below the threshold, predicted

0

Dataset	Lloyd	Softmax	GD	Entmax	conv. %	Softmax	GD	Entmax
	Iterations (median)				GD	$d_{\mathrm{match}}$ to Lloyd (median)
Blobs	$4$	$6$	$6$	$4$	$99$	$1.75\times 10^{-4}$	$1.75\times 10^{-4}$	$0$
Moons	$6$	$8$	$9$	$6$	$100$	$1.50\times 10^{-4}$	$1.50\times 10^{-4}$	$0$
Spiral	$12$	$20$	$37$	$15$	$100$	$0.0106$	$0.0222$	$7.84\times 10^{-3}$
Circles	$7$	$11$	$13$	$8$	$100$	$3.05\times 10^{-4}$	$0.0364$	$0$
Separation, $\delta{=}0.5$	$12$	$18$	$34$	$16$	$100$	$1.34\times 10^{-4}$	$0.0162$	$0$

Appendix

Table 9: Optimization dynamics at

\widetilde{\beta}=4

, from the paired initializations of the admissible runs. Iterations: median number of iterations until the stopping criterion ( 61 ) or the cap

T

. GD conv.: percentage of gradient-descent runs that met the stopping criterion before the cap.

d_{\mathrm{match}}

: median permutation-invariant distance between the terminal centroids and Lloyd’s terminal centroids from the same initialization.

	Same path (%)			Same end (%)
Dataset	Softmax	Entmax	GD	Softmax	Entmax	GD
Blobs	$87$	$88$	$62$	$98$	$98$	$97$
Moons	$62$	$72$	$26$	$100$	$100$	$100$
Spiral	$12$	$24$	$0$	$32$	$48$	$18$
Circles	$38$	$46$	$6$	$57$	$64$	$32$
Separation, $\delta{=}0.5$	$18$	$21$	$0$	$55$	$57$	$37$

Appendix

Table 10: Trajectory experiment at

\widetilde{\beta}=4

. Each soft method is run from the same paired initializations as Lloyd’s algorithm. Same path: percentage of runs whose hard partition equals Lloyd’s at every iteration. Same end: percentage of runs with the same terminal partition. Over all datasets and temperatures, the hypotheses of Theorem 25 hold in 1,663 alternating-Softmax runs, with 0 violations of its prediction, and those of Corollary 26 hold in 5,644 alternating-Entmax runs, with 0 violations.

	Better/worse than Lloyd (%)			Best found (%)
Dataset	DA-Soft.	DA-Ent.	EM-GMM	Lloyd	DA-Soft.	DA-Ent.	EM-GMM
Blobs	$2/0$	$2/0$	$0/2$	$98$	$100$	$100$	$97$
Moons	$0/0$	$0/0$	$0/0$	$100$	$100$	$100$	$100$
Spiral	$100/0$	$100/0$	$46/22$	$0$	$100$	$100$	$2$
Circles	$90/0$	$90/0$	$37/13$	$10$	$100$	$100$	$12$
Separation, $\delta{=}0.5$	$89/0$	$89/0$	$33/24$	$11$	$100$	$100$	$28$

Appendix

Table 11: Quality of the K-Means fixed point reached from each paired k-means++ initialization. DA-Soft., DA-Ent.: deterministic annealing with alternating Softmax or Entmax-1.5 along a geometric temperature schedule starting above the critical temperature of Proposition 9 ; EM-GMM: EM for a spherical Gaussian mixture initialized at the same centroids. Every method ends with Lloyd’s algorithm. Better/worse: percentage of runs whose final distortion is lower/higher than that of Lloyd’s algorithm from the same initialization by more than a relative

10^{-6}

. Best: percentage of runs reaching the lowest distortion found by any method on that dataset.

		Slope $E_{r}$		Slope $G_{\sigma}$
Dataset	Runs	Mean (sd)	95% CI of median	Mean (sd)	95% CI of median
Blobs	200	$-0.998$ (4e-16)	$[-0.998,\,-0.998]$	$-1.002$ (0.0005)	$[-1.002,\,-1.002]$
Moons	200	$-0.998$ (2e-16)	$[-0.998,\,-0.998]$	$-1.002$ (2e-16)	$[-1.002,\,-1.002]$
Spiral	200	$-0.998$ (2e-06)	$[-0.998,\,-0.998]$	$-1.003$ (0.004)	$[-1.003,\,-1.000]$
Circles	200	$-0.998$ (3e-14)	$[-0.998,\,-0.998]$	$-1.006$ (0.007)	$[-1.004,\,-1.000]$
Separation, $\delta{=}0.5$	200	$-0.998$ (3e-14)	$[-0.998,\,-0.998]$	$-1.005$ (0.005)	$[-1.008,\,-1.005]$

Appendix

Table 12: Full summaries of the per-run slopes of

E_{r}

and

G_{\sigma}

in Table 8 : mean (standard deviation) over the admissible runs, and a distribution-free 95% confidence interval for the median, from order statistics.

	Alt. Softmax		Alt. Entmax		GD on $F_{\sigma}$		DA-Softmax
Dataset	L/H	$p$	L/H	$p$	L/H	$p$	L/H	$p$
Blobs	$4/0$	$0.12$	$3/0$	$0.25$	$3/1$	$0.62$	$4/0$	$0.12$
Moons	$0/0$	$1$	$0/0$	$1$	$0/0$	$1$	$0/0$	$1$
Spiral	$99/36$	$<10^{-7}$	$66/37$	$0.0055$	$96/68$	$0.035$	$200/0$	$<10^{-59}$
Circles	$81/4$	$<10^{-18}$	$69/2$	$<10^{-17}$	$94/43$	$<10^{-4}$	$180/0$	$<10^{-53}$
Separation, $\delta{=}0.5$	$90/1$	$<10^{-25}$	$84/2$	$<10^{-22}$	$99/27$	$<10^{-10}$	$178/0$	$<10^{-53}$

Appendix

Table 13: Paired comparison of the hard distortion after a Lloyd polish of the terminal centroids with that of Lloyd’s algorithm from the same initialization: number of runs with a lower/higher distortion by more than a relative

10^{-6}

, and the two-sided

p

-value of the exact sign test on these runs (ties excluded, no correction for multiple comparisons). L/H: lower/higher. Alternating methods at

\beta=4

(Section 7.6 ); DA-Softmax: deterministic annealing (Section 7.8 ). Up to 200 paired runs per cell.

	MNIST		Fashion-MNIST		USPS		CIFAR-10		STL-10
Method	NMI	ARI	NMI	ARI	NMI	ARI	NMI	ARI	NMI	ARI
AE + K-Means	$0.757$	$0.692$	$0.553$	$0.383$	$0.692$	$0.602$	$0.559$	$0.448$	$0.683$	$0.527$
DEC	$0.776$	$0.716$	$0.577$	$0.403$	$0.785$	$0.713$	$0.593$	$0.500$	$0.738$	$0.592$
IDEC	$0.830$	$0.767$	$0.602$	$0.421$	$0.793$	$0.722$	$0.621$	$0.532$	$0.741$	$0.599$
DCN (hard)	$0.820$	$0.735$	$0.588$	$0.394$	$0.741$	$0.624$	$0.583$	$0.381$	$0.695$	$0.455$
$D_{\sigma}$	$0.830$	$0.750$	$0.584$	$0.367$	$0.729$	$0.585$	$0.567$	$0.352$	$0.700$	$0.456$

Appendix

Table 14: NMI and ARI of the methods of Table 4 , mean over 5 seeds.

Quantity	Reported	Seeds 1–5	$n=1000$
Smallest fraction satisfying a bound check	$1.000$	$1.000$	$1.000$
Entmax identification violations ( $\beta\geq 2$ )	$0$	$0$	$0$
Median slope of $E_{r}$ (range over datasets)	$[-1.017,-0.998]$	$[-1.020,-0.998]$	$[-1.016,-0.998]$
Median slope of $G_{\sigma}$ (range over datasets)	$[-1.088,-1.001]$	$[-1.092,-1.000]$	$[-1.100,-1.000]$
Gradient descent converged (%)	$93.8$	$92.5--93.9$	$93.7$
Alt. Softmax: lower / higher $J$ than Lloyd (%)	$23.3$ / $1.9$	$19.6--28.1$ / $1.0--1.4$	$19.5$ / $1.0$

Appendix

Table 15: Replication of the headline results. Reported: the runs of the main text (

300

points per synthetic dataset, seed

0

). Seeds

1

–

5

: five further draws of every synthetic dataset and of every paired initialization, summarized by the range over the five draws (counts are summed).

n=1000

: the main experiments with

1{,}000

points per synthetic dataset (the real datasets are unchanged); the additional experiments were not repeated at this size. The comparisons of

J

use the Lloyd polish of Section 7.6 .

Weight $\gamma$ (relative temperature $0.1$ )
	MNIST			USPS			CIFAR-10
Method	$0.01$	$0.1$	$1$	$0.01$	$0.1$	$1$	$0.01$	$0.1$	$1$
IDEC	$\mathbf{0.830}$	$0.820$	$0.798$	$0.753$	$\mathbf{0.787}$	$0.778$	$0.600$	$\mathbf{0.644}$	$0.636$
DCN (hard)	$\mathbf{0.825}$	$0.812$	$0.794$	$\mathbf{0.746}$	$0.722$	$0.692$	$\mathbf{0.591}$	$0.531$	$0.281$
$D_{\sigma}$	$\mathbf{0.831}$	$0.823$	$0.811$	$\mathbf{0.740}$	$0.666$	$0.666$	$\mathbf{0.537}$	$0.504$	$0.358$
$F_{\sigma}$ (ours)	$0.822$	$\mathbf{0.827}$	$0.782$	$\mathbf{0.734}$	$0.657$	$0.531$	$\mathbf{0.647}$	$0.560$	$0.299$

Appendix

Table 16: Sensitivity of the deep-clustering losses: accuracy, mean over 3 seeds, from the same pretrained networks as Table 4 . Top: weight

\gamma

of the clustering term; bottom: relative temperature

\sigma^{2}/\overline{d}_{\min}

of the soft objectives. Best value of each row and dataset in bold.

Method	Centroid learning rate	MNIST	USPS	CIFAR-10
$F_{\sigma}$ , closed form	–	$0.830\pm 0.014$	$0.668\pm 0.023$	$0.574\pm 0.054$
$F_{\sigma}^{(3/2)}$ , closed form	–	$0.831\pm 0.012$	$0.681\pm 0.023$	$0.569\pm 0.027$
DEC	$10^{-4}$	$0.790\pm 0.015$	$0.780\pm 0.007$	$0.624\pm 0.045$
DEC	$10^{-3}$	$0.790\pm 0.013$	$0.775\pm 0.007$	$0.622\pm 0.043$
DEC	$10^{-2}$	$0.788\pm 0.013$	$0.765\pm 0.011$	$0.617\pm 0.045$
IDEC	$10^{-4}$	$0.818\pm 0.013$	$0.789\pm 0.004$	$0.648\pm 0.049$

Appendix

Table 17: Learning rate of Adam on the centroids: accuracy, mean

\pm

standard deviation over 5 seeds, from the same pretrained networks as Table 4 . The closed-form methods have no centroid learning rate; the network is trained with Adam at

10^{-4}

in every row.

		$K=128$		$K=512$		$K=1024$
Assignment	Update	MSE	Used	MSE	Used	MSE	Used
Hard	Gradient	$4.80$	$124$	$4.16$	$372$	$3.86$	$524$
Hard	Closed form	$5.58$	$56$	$4.98$	$104$	$4.80$	$132$
Softmax	Gradient	$4.77$	$128$	$3.93$	$511$	$3.53$	$1023$
Softmax	Closed form	$4.83$	$128$	$4.06$	$504$	$3.61$	$991$
Entmax-1.5	Gradient	$4.78$	$127$	$3.99$	$455$	$3.62$	$798$

Appendix

Table 18: Sensitivity of the VQ-VAE codebook rules of Table 5 , mean over 3 seeds: test reconstruction error (

\times 10^{-3}

) and number of codes used. Top: codebook size

K

at relative temperature

0.1

; bottom: relative temperature of the soft rules at

K=512

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 345 papers

Riemannian Difference-of-Convex Optimization for K-Means Clustering
Sep 28, 2026Meng Xu, Bo Jiang, Hanfu Zhang +2Riemannian Optimization Clustering
AMSS, Chinese Academy of Sciences, and University of Chinese Academy of Sciences, Beijing, China · Ministry of Education Key Laboratory of NSLSCS, School of Mathematical Sciences, Nanjing Normal University, Nanjing, China · Ministry of Education Key Laboratory of Mathematics and Information Networks, School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing, China +1
Distributionally Robust K-Means Clustering
Apr 13, 2026Vikrant Malik, Taylan Kargin, Babak HassibiClustering Distribution Shift Robustness
Department of Electrical Engineering, California Institute of Technology, Pasadena, CA 91125 USA. · California Institute of Technology, Pasadena, CA 91125 USA · Massachusetts Institute of Technology, Cambridge, MA 02139 USA.
An Algebraic Approach to Constrained K-means Clustering
Oct 10, 2026Hiroki Oohori, Kentaro Fukushima, Michio YamamotoClustering
Graduate School of Human Sciences, The University of Osaka, Osaka, Japan · Graduate School of Education, The University of Tokyo, Tokyo, Japan · Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan +1

Sep 28, 2026J/K move · Enter open · S save

Riemannian Difference-of-Convex Optimization for K-Means Clustering

Meng Xu, Bo Jiang, Hanfu Zhang, Ya-Feng Liu+1

AMSS, Chinese Academy of Sciences, and University of Chinese Academy of Sciences, Beijing, China · Ministry of Education Key Laboratory of NSLSCS, School of Mathematical Sciences, Nanjing Normal University, Nanjing, China · Ministry of Education Key Laboratory of Mathematics and Information Networks, School of Mathematical Sciences, Beijing University of Posts and Telecommunications, Beijing, China+1

Riemannian Optimization Clustering Constrained Optimization

Open paper AskPDF arXiv

K-means is a widely adopted clustering approach in signal processing and machine learning. In this paper, we study K-means clustering through a cardinality-constrained formulation on a compact embedded submanifold. We replace the cardinality constraint with a difference-of-convex (DC) penalty and establish a global error bound to prove that the penalized and constrained formulations share the same global minimizers whenever the penalty parameter exceeds a finite threshold. To solve the resulting nonsmooth Riemannian DC problem, we reformulate it as a minimax problem and propose RADA-DC, a Riemannian alternating descent ascent method combining dual regularization with DC linearization. Under standard assumptions and suitable parameter choices, RADA-DC finds an

ε

-Riemannian critical point within

O(ε^{-3})

iterations. We conduct experiments on synthetic and real-world datasets to demonstrate that the proposed method outperforms the tested baselines, including K-means++, in solution quality at competitive computational cost when the number of clusters is large.

Abstract

Clustering

Explore similar work

Riemannian Difference-of-Convex Optimization for K-Means Clustering

Distributionally Robust K-Means Clustering

An Algebraic Approach to Constrained K-means Clustering