📊 statistics

Lloyd's $K$ -Means Clustering Algorithm Is Frank-Wolfe in Disguise

Este artículo establece que el algoritmo de $K$ -medias de Lloyd es un caso especial del método de Frank-Wolfe, derivando así una tasa de convergencia no asintótica de $\mathcal{O}(1/t)$ hacia un mínimo local para el objetivo de la suma de errores cuadráticos y extendiendo este análisis para manejar clústeres vacíos mediante una variante semisuave.

Autores originales: Michael Pokojovy, J. Marcus Jobe, Simon Lacoste-Julien

Publicado 2026-07-29

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Michael Pokojovy, J. Marcus Jobe, Simon Lacoste-Julien

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que eres un detective intentando resolver un misterio, pero en lugar de huellas dactilares, tienes miles de pistas dispersas: puntos en un mapa, píxeles en una foto o palabras en un libro. Tu trabajo es agrupar estas pistas en montones significativos basados en qué tan similares se ven. Esto es el corazón del clustering (agrupamiento), un superpoder en el mundo del aprendizaje automático que ayuda a las computadoras a encontrar patrones ocultos en datos desordenados sin que un maestro les diga qué buscar.

Uno de los métodos más antiguos y famosos para hacer esto se llama K-means. Piensa en ello como un juego de sillas musicales con un giro: eliges a unos pocos "capitanes" (centros) para tus grupos, y cada punto de datos corre hacia el capitán con el que se siente más cercano. Luego, los capitanes se mueven al lugar promedio de su nuevo equipo, y todos corren de nuevo. Sigues haciendo esto hasta que todos dejen de moverse. Es un proceso codicioso, paso a paso, que suele funcionar de maravilla, pero durante décadas, los matemáticos se han estrujado la cabeza sobre exactamente qué tan rápido encuentra la mejor solución y por qué a veces se queda atrapado en un bucle.

Entra el algoritmo de Frank-Wolfe, una herramienta de optimización diferente utilizada por matemáticos para resolver problemas complejos sin necesidad de rebotar contra las paredes (una técnica llamada "proyección"). Es como un excursionista que siempre elige el camino más empinado hacia abajo en una colina, dando pasos gigantes hasta llegar al fondo. Durante mucho tiempo, estos dos métodos —K-means y Frank-Wolfe— parecieron vivir en vecindarios diferentes. Pero un nuevo artículo sugiere que en realidad son la misma persona usando sombreros diferentes.

La gran revelación: K-means es Frank-Wolfe disfrazado

En este artículo, los autores, Michael Pokojovy, J. Marcus Jobe y Simon Lacoste-Julien, descorren la cortina para mostrar que el algoritmo K-means de Lloyd (la versión estándar que todo el mundo usa) es en realidad una versión especial y astuta del algoritmo de Frank-Wolfe.

Para entender la magia, imagina que estás tratando de organizar una fiesta masiva. Quieres agrupar a los invitados para que las personas que gustan de la misma música se sienten juntas.

La forma antigua (K-means): Eliges algunas mesas (centros), pides a todos que se sienten en la mesa más cercana, luego mueves las mesas al centro de las personas sentadas allí. Repites esto hasta que las mesas dejan de moverse.
La nueva visión: Los autores se dieron cuenta de que cuando K-means mueve una mesa al centro de sus invitados, está haciendo matemáticamente lo mismo que el algoritmo de Frank-Wolfe al dar un paso gigante colina abajo.

¿Por qué es esto importante? Porque el algoritmo de Frank-Wolfe es una herramienta matemáticamente "limpia" y bien comportada con un límite de velocidad conocido. Al darse cuenta de que K-means es solo Frank-Wolfe con un sombrero de fiesta, los autores pueden usar la matemática limpia de Frank-Wolfe para demostrar exactamente qué tan rápido terminará su trabajo el K-means.

El problema de la "Silla Vacía"

Hay una parte truculenta en el juego de K-means: a veces, una mesa termina sin nadie sentado en ella. En la analogía de la fiesta, un capitán podría quedarse solo porque todos corrieron hacia otra mesa. En términos matemáticos, esto crea un "hueco" o un punto rugoso en la colina suave por la que Frank-Wolfe suele rodar.

Los autores no ignoraron este problema; lo abordaron de frente. Desarrollaron una versión nueva y ligeramente más flexible del algoritmo de Frank-Wolfe que puede manejar estos momentos de "silla vacía" (que ellos llaman objetivos semismooth o semisuaves). Demostraron que incluso cuando los grupos se quedan vacíos, el algoritmo no se confunde ni se ralentiza. Sigue rodando colina abajo, con la misma eficiencia de siempre.

¿Qué tan rápido es rápido?

El hallazgo más emocionante es la velocidad. Los autores demostraron que el algoritmo K-means converge a una buena solución a un ritmo de O(1/t).

Vamos a desglosar eso con una metáfora simple: Imagina que caminas hacia un cofre del tesoro.

Si estuvieras caminando a un ritmo de O(1/√t), darías un gran paso al principio, pero tus pasos se harían más y más pequeños muy rápidamente, como si estuvieras caminando con dificultad a través de un lodo espeso.
Pero debido a que K-means es en realidad Frank-Wolfe, camina a un ritmo de O(1/t). Esto significa que tus pasos se vuelven más pequeños, pero tienes la garantía de que te acercarás al tesoro de manera mucho más predecible.

Crucialmente, los autores demostraron que esta velocidad depende únicamente de qué tan lejos comenzaste de la mejor solución posible. No importa si tienes un millón de puntos de datos (una fiesta enorme) o solo unos pocos; la garantía de velocidad se mantiene. Esto es algo importante porque las teorías anteriores solían volverse desordenadas y complicadas cuando el número de puntos de datos crecía.

Probando la teoría

Para asegurarse de que esto no era solo un truco matemático elegante, el equipo realizó simulaciones masivas.

Crearon datos falsos que parecían "manchas" de puntos (como nubes coloridas de confeti) y ejecutaron el algoritmo K-means miles de veces.
También lo probaron en un conjunto de datos del mundo real de segmentación de imágenes, donde el objetivo es agrupar píxeles en una foto para separar el cielo, la hierba y los edificios.

En cada prueba, la "brecha" entre donde estaba el algoritmo y donde quería estar se redujo exactamente como la matemática predijo. Cuando trazaron los resultados en un gráfico, la línea bajaba con una pendiente de -1.0, que es la firma matemática de la velocidad O(1/t). Incluso cuando los datos eran desordenados o los grupos tenían formas extrañas, el algoritmo mantuvo la calma.

Una nueva forma de detener el algoritmo

Uno de los aspectos más prácticos es saber cuándo detener la fiesta. Usualmente, las computadoras detienen K-means cuando los centros dejan de moverse significativamente. Pero los autores sugieren una mejor manera: detenerse cuando la "brecha de Frank-Wolfe" (la diferencia en la puntuación entre la disposición actual y la siguiente disposición posible) sea lo suficientemente pequeña.

Esta nueva regla de parada es como tener un indicador de combustible que te dice exactamente cuánto "trabajo" queda por hacer. Es más confiable que adivinar, y ofrece un límite estricto de cuántos pasos necesitará tomar el algoritmo.

La conclusión

Este artículo no inventa una nueva forma de hacer K-means; en cambio, revela que la forma antigua y confiable que hemos estado usando durante décadas es en realidad una versión disfrazada de una herramienta matemática poderosa y moderna. Al conectar estos dos mundos, los autores nos han dado un límite de velocidad claro y probado para K-means y una mejor manera de saber cuándo el trabajo ha terminado. Es un recordatorio de que, a veces, las herramientas más familiares en la ciencia son solo versiones con un disfraz diferente de lo que pensábamos.

Resumen Técnico: El algoritmo de agrupamiento K-Means de Lloyd es un Frank-Wolfe disfrazado

Planteamiento del problema
El algoritmo K-means de Lloyd (K-means ingenuo) es un heurístico ubicuo para minimizar la Suma de Errores Cuadráticos (SSE) a través de $K$ -particiones de un conjunto de datos. A pesar de su uso generalizado, la comprensión teórica de su convergencia sigue siendo limitada, particularmente en lo que respecta a las tasas no asintóticas que se mantienen uniformemente a través del tamaño de la muestra ( $n$ ), la dimensión ( $d$ ) y el número de clústeres ( $K$ ). Los análisis de convergencia existentes suelen depender de $\epsilon$ -coresets, donde los límites tienden a explotar cuando $\epsilon \to 0$ , o se centran en el comportamiento asintótico. Además, los marcos de optimización estándar luchan con la naturaleza "codiciosa" (greedy) de la asignación de Lloyd, que puede dar lugar a clústeres vacíos, haciendo que la función objetivo no sea suave (semisuave) y difícil de analizar mediante las herramientas de optimización suave estándar.

Metodología
Los autores establecen una novedosa conexión teórica al demostrar que el algoritmo K-means de Lloyd es un caso especial del algoritmo Frank-Wolfe (FW) (también conocido como descenso de gradiente condicional) aplicado a un objetivo cóncavo sobre un conjunto poliédrico.

Formulación como optimización continua: El problema de particionamiento discreto de K-means se codifica utilizando un vector "one-hot" $w \in \{0, 1\}^{n \times K}$ . La función objetivo SSE $f(w)$ se extiende continuamente al casco convexo de estas particiones, $M = \text{conv}(M_0)$ .
Concavidad y semisuavidad: Los autores demuestran que la función SSE extendida es una función cóncava. Crucialmente, aunque la función es suave dentro del interior del conjunto factible (donde todos los clústeres no están vacíos), se vuelve semisuave cuando los clústeres quedan vacíos.
Equivalencia con FW:
- Clústeres no vacíos: Cuando todos los clústeres no están vacíos, el paso de asignación codiciosa de Lloyd corresponde exactamente a un paso de FW con un tamaño de paso unitario ( $\gamma_t = 1$ ) sobre el politopo de las particiones admisibles.
- Clústeres vacíos: Para manejar los clústeres vacíos, los autores desarrollan una variante del algoritmo FW para objetivos cóncavos de carácter general semisuave. Utilizan el subdiferencial de Clarke (en lugar del subgradiente de Goldstein) para definir un gap de FW generalizado. Demuestran que la estrategia de Lloyd de retener el centroide anterior para un clúster vacío corresponde a la selección de un elemento del subdiferencial de Clarke del objetivo extendido.
Análisis de convergencia: Aprovechando los avances recientes en métodos FW para objetivos cóncavos (específicamente Yurtsever y Sra, 2022), los autores derivan una tasa de convergencia no asintótica. Definen una medida de estacionariedad basada en el gap de FW de Clarke, $g_C(x)$ , y demuestran que el gap mínimo encontrado después de $t$ iteraciones satisface $\tilde{g}_t \leq h_0 / (t+1)$ , donde $h_0$ es la suboptimalidad global inicial.

Contribuciones clave

Unificación teórica: El artículo demuestra que el algoritmo de Lloyd con asignación codiciosa es un caso especial del algoritmo FW con tamaño de paso unitario para un objetivo semisuave sobre un conjunto poliédrico.
Tasa de convergencia: Los autores establecen una tasa de convergencia no asintótica de $O(1/t)$ hacia un mínimo local del objetivo SSE. Esta tasa está controlada únicamente por el valor inicial de la SSE ( $h_0$ ) y es uniforme con respecto a $n$ , $d$ y $K$ . Evita la dependencia de los parámetros de $\epsilon$ -coreset que plagan otros análisis previos.
Manejo de clústeres vacíos: Se desarrolla una nueva variante de FW para objetivos cóncavos semisuaves, utilizando el subdiferencial de Clarke. Esto permite que el marco teórico acomode el escenario, de gran relevancia práctica, de los clústeres vacíos sin sacrificar la tasa de convergencia.
Nueva medida de error: El trabajo propone el gap de FW (equivalente a la disminución de la SSE, $\Delta SSE_t$ ) como un criterio de parada. A diferencia de la métrica estándar de movimiento de centroides, esta medida es afín-invariante y cuenta con una garantía teórica sobre el número máximo de pasos requeridos para alcanzar una tolerancia específica.

Resultados

Estudio de simulación: Los autores realizaron extensas simulaciones de Monte Carlo en mezclas gaussianas esféricas sintéticas ("blobs") y un conjunto de datos real de segmentación de imágenes.
- Datos sintéticos: En varias configuraciones de $n$ , $d$ y $K$ , el gap de FW en el peor de los casos decayó monótonamente. El análisis de regresión de los gráficos log-log confirmó una pendiente consistente con $-1$, lo que respalda la tasa $O(1/t)$ .
- Datos del mundo real: En el conjunto de datos de segmentación de imágenes de UCI (que viola los supuestos gaussianos y esféricos), la tasa de convergencia empírica también respaldó el límite $O(1/t)$ , no rechazándose la hipótesis nula de una pendiente de $-1$.
Límites teóricos: El límite derivado $h_0/(t+1)$ proporciona una estimación concreta de la suboptimalidad inicial, la cual escala linealmente con $n$ y la traza de la matriz de covarianza de la muestra.

Significancia y Reivindicaciones
El artículo sostiene que ver el K-means de Lloyd a través de la lente de la optimización FW semisuave proporciona una "nueva herramienta simple, pero poderosa" que ofrece:

Garantías de convergencia: Tasas no asintóticas rigurosas de $O(1/t)$ que se mantienen uniformemente a través de las dimensiones del problema, una mejora significativa respecto a los análisis heurísticos previos.
Control de error práctico: Una regla de parada teóricamente fundamentada basada en el gap de FW (disminución de la SSE) en lugar de umbrales arbitrarios de movimiento de centroides. Esto permite calcular el número máximo de iteraciones necesarias para lograr una precisión deseada.
Robustez: El enfoque es robusto ante modificaciones y extensiones, tales como el K-means recortado (trimmed K-means) o el análisis de clústeres robustos, debido a que se basa en la geometría convexa general en lugar de estructuras de politopos específicos o argumentos combinatorios.

Los autores señalan que, si bien los resultados son significativos para el K-means estándar y robusto, las extensiones a entornos online/estocásticos y mezclas elípticas generales siguen siendo desafíos abiertos. El trabajo se presenta como un paso fundacional para la aplicación de técnicas de optimización sin proyección a problemas de agrupamiento combinatorio.