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

Sep 28, 2026

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

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.

Meng Xu, Bo Jiang, Hanfu Zhang +2

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

Ask PDF

Apr 13, 2026

Distributionally Robust K-Means Clustering

K-means clustering is a workhorse of unsupervised learning, but it is notoriously brittle to outliers, distribution shifts, and limited sample sizes. Viewing k-means as Lloyd--Max quantization of the empirical distribution, we develop a distributionally robust variant that protects against such pathologies. We posit that the unknown population distribution lies within a Wasserstein-2 ball around the empirical distribution. In this setting, one seeks cluster centers that minimize the worst-case expected squared distance over this ambiguity set, leading to a minimax formulation. A tractable dual yields a soft-clustering scheme that replaces hard assignments with smoothly weighted ones. We propose an efficient block coordinate descent algorithm with provable monotonic decrease and local linear convergence. Experiments on standard benchmarks and large-scale synthetic data demonstrate substantial gains in outlier detection and robustness to noise.

Vikrant Malik, Taylan Kargin, Babak Hassibi

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.

Clustering Distribution Shift Robustness Wasserstein Distributionally Robust Optimization

Ask PDF

Oct 10, 2026

An Algebraic Approach to Constrained K-means Clustering

Clustering is typically performed using only object features, although additional information about relationships between objects may be available and can be incorporated through constraints. Among these, pairwise constraints require two objects to belong to the same cluster or to different clusters. Several extensions of the k-means algorithm accommodate such constraints, but they sometimes fail to find a feasible assignment or incur high computational cost. Motivated by these limitations, we propose an algebraic approach to k-means clustering with pairwise constraints. The algorithm simplifies the constraints using Gröbner bases before optimization, improving the efficiency of cluster assignment. It can also detect whether the constraint set has a feasible assignment before optimization. Comparative experiments with existing algorithms showed that the proposed algorithm achieved comparable or better clustering quality at a lower computational cost, particularly when the numbers of constraints and clusters were small.

Hiroki Oohori, Kentaro Fukushima, Michio Yamamoto

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

Clustering

Ask PDF

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