9:41

E-means: 10x faster k-means at equal loss

, 25 , 1.2 3 . , 10–45× ([2]), 8–15× [1]. , .

e-means against Lloyd’s k-means, in epochs, CPU time and GPU time

= {1, ..., } ⊂ , = (1, ..., ) :

\[ \{}(, ) = \{1}{} \_{=1}^{} \|_ - _{()}\|^2, \ () = \\_{ \ \{1,\,\}} \|_ - _\|^2 \]

\[ \{}(, ) = \{1}{} \_{=1}^{} \|_ - _{()}\|^2 \]

\[ () = \\_{ \ \{1,\,\}} \|_ - _\|^2 \]

, , .

. :

  • .
  • [3],[4],[5], , 1967.
  • .

, [6], . , ( ). , , , . , .

. .

.

. .

α α0 0.1α0, .

.

, .

. . , , , :

\[ _ = _ / _ \]

. , ( ).

[7] , :

\[ _ \ _, \\ _ \ _ \]

. , ( 20 50 ).

[3] :

\[ _ \ _ + _, \\ _ \ _ + _ \]

, , , . [8], . , .

:

\[ _ \ (1-\)\,_ + \\, _, \\ _ \ (1-\)\,_ + \\, _ \]

\[ _ \ (1-\)\,_ + \\, _ \]

\[ _ \ (1-\)\,_ + \\, _ \]

α, . , [6]. ’ , .

é é, . , , . , .

Test error against the effective step for exponential moving averages and plain gradient descent, at a large batch
Test error against the effective step a centroid takes, at a large batch, for exponential-moving-average updates (EMA) and plain gradient descent (SGD), each at every step setting tried. DEEP, 1 million vectors, and SIFT, 10 million vectors, 16,384 clusters, 5 epochs, median over 3 seeds. The vertical axis is percent above the best test error in the panel. At its best setting, gradient descent ends 1.6% (DEEP) and 0.4% (SIFT) above the moving average.

, , .

, = , α = 1, , . . , , . , α: , .

Validation loss for every batch size and constant step at 5 epochs; the lowest losses lie on a diagonal band, and Lloyd, at full batch and step 1, sits in the top-right corner 1.8% above the best
B α n 6 k α

α.

, . 200 , .

. , , .

. α0 (, , ), .

\[ = _ \, ^{_} \, ^{_} \, ^{_} \]

\[ \_0 = \\!\(_\ \, ^{_} \, ^{_} \, ^{_} \, ^{_},\; 1\) \]

= ( − ) / , . : , , [9] . : .

, . “ ” “” . : α0 () ().

The two scaling laws fit on deep1b

.

“” , . , .

, [10], . , . , , : . , , .

1 , = 16,384, 5 , 5 ; . , . : (1 = ). .

24 ( ). 234 (16 , 100 100 ): .

Convergence curves vs Lloyd at 25 iterations
Test MSE, divided by Lloyd’s after 25 epochs. Initialized from random vectors.
Test error against wall-clock time on GPU, 10 million vectors, k=65,536
[2]
Epochs e-means needs to reach Lloyd's 25-epoch test error on the 11 VIBE embedding datasets: 1.6 to 2.4
d k

.._ # = (, , =) # (5 ) , = .() # : (, ) # :

: //_.

, (:2611.09501):

@{2026, ={: ( )}, ={ é é é}, ={2026}, ={2611.09501}, ={}, ={.}, ={://.//2611.09501}, }

  • . , . , . , . , . , .-. é, . , . , . é. " ." :2401.08281, 2024. ↑
  • . , . , . , . , . , . , . , . , . , . , . , . , . . ": ." :2603.09229, 2026. ↑
  • . . " ." , 1:281–297, 1967. ↑
  • . . " ." , 2010. ↑
  • . , . . " ." , 2016. ↑
  • . , . , . . " ." , 2017. ↑
  • . . " ." , 28(2):129–137, 1982 ( 1957). ↑
  • . , . , . , . , . . " ." , 35(10):14424–14436, 2024. ↑
  • . ää, . ö, . , . , . ü. ": ." :2505.17810, 2025. ↑
  • . é, . , . , . . " ." , 2023. :2210.13438. ↑