📊 statistics

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

Cet article établit que l'algorithme des $K$ -moyennes de Lloyd est un cas particulier de la méthode de Frank-Wolfe, dérivant ainsi un taux de convergence non asymptotique en $\mathcal{O}(1/t)$ vers un minimum local pour l'objectif de la somme des erreurs quadratiques et étendant cette analyse pour gérer les clusters vides via une variante semi-lisse.

Auteurs originaux : Michael Pokojovy, J. Marcus Jobe, Simon Lacoste-Julien

Publié 2026-07-29

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Michael Pokojovy, J. Marcus Jobe, Simon Lacoste-Julien

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous soyez un détective tentant de résoudre un mystère, mais au lieu d'empreintes digitales, vous avez des milliers d'indices éparpillés — des points sur une carte, des pixels dans une photo ou des mots dans un livre. Votre tâche consiste à regrouper ces indices en piles significatives basées sur leur similitude visuelle. C'est le cœur du clustering (regroupement), un superpouvoir du monde de l'apprentissage automatique qui aide les ordinateurs à trouver des motifs cachés dans des données désordonnées sans qu'un enseignant ne leur dise quoi chercher.

L'une des méthodes les plus anciennes et les plus célèbres pour y parvenir s'appelle K-means. Voyez cela comme un jeu de chaises musicales avec un twist : vous choisissez quelques « capitaines » (centres) pour vos groupes, et chaque point de donnée court vers le capitaine vers lequel il se sent le plus proche. Ensuite, les capitaines se déplacent vers l'emplacement moyen de leur nouvelle équipe, et tout le monde court à nouveau. Vous continuez ainsi jusqu'à ce que tout le monde cesse de bouger. C'est un processus gourmand, étape par étape, qui fonctionne généralement très bien, mais pendant des décennies, des mathématiciens se sont creusé la tête pour comprendre exactement à quelle vitesse il trouve la meilleure solution et pourquoi il reste parfois bloqué dans une boucle.

Entrez dans la scène : l'algorithme de Frank-Wolfe, un outil d'optimisation différent utilisé par les mathématiciens pour résoudre des problèmes complexes sans avoir besoin de rebondir contre des murs (une technique appelée « projection »). C'est comme un randonneur qui choisit toujours le chemin le plus escarpé pour descendre une colline, faisant de grands pas jusqu'à atteindre le bas. Pendant longtemps, ces deux méthodes — K-means et Frank-Wolfe — semblaient vivre dans des quartiers différents. Mais un nouvel article suggère qu'elles sont en réalité la même personne portant des chapeaux différents.

La grande révélation : K-means est un Frank-Wolfe déguisé

Dans cet article, les auteurs, Michael Pokojovy, J. Marcus Jobe et Simon Lacoste-Julien, lèvent le rideau pour montrer que l'algorithme K-means de Lloyd (la version standard que tout le monde utilise) est en fait une version spéciale et rusée de l'algorithme Frank-Wolfe.

Pour comprendre la magie, imaginez que vous essayez d'organiser une fête massive. Vous voulez regrouper les invités de sorte que les personnes qui aiment la même musique s'assoient ensemble.

L'ancienne méthode (K-means) : Vous choisissez quelques tables (centres), vous demandez à chacun de s'asseoir à la table la plus proche, puis vous déplacez les tables vers le centre des personnes qui y sont assises. Vous répétez l'opération jusqu'à ce que les tables cessent de bouger.
La nouvelle intuition : Les auteurs ont réalisé que lorsque K-means déplace une table vers le centre de ses invités, il fait mathématiquement exactement la même chose que l'algorithme de Frank-Wolfe effectuant un grand pas vers le bas d'une colline.

Pourquoi est-ce important ? Parce que l'algorithme de Frank-Wolfe est un outil mathématiquement « propre » et bien élevé, doté d'une limite de vitesse connue. En réalisant que K-means n'est qu'un Frank-Wolfe portant un chapeau de fête, les auteurs peuvent utiliser les mathématiques propres de Frank-Wolfe pour prouver exactement la vitesse à laquelle K-means terminera sa tâche.

Le problème de la « chaise vide »

Il y a un aspect délicat dans le jeu du K-means : parfois, une table se retrouve avec personne assis autour. Dans l'analogie de la fête, un capitaine pourrait se retrouver seul car tout le monde a couru vers une autre table. En termes mathématiques, cela crée un « écart » ou une zone rugueuse dans la colline lisse sur laquelle Frank-Wolfe roule habituellement.

Les auteurs n'ont pas ignoré ce problème ; ils l'ont affronté de front. Ils ont développé une nouvelle version de l'algorithme de Frank-Wolfe, légèrement plus flexible, capable de gérer ces moments de « chaises vides » (qu'ils appellent des objectifs semismooth ou semi-lisses). Ils ont prouvé que même lorsque des clusters se vident, l'algorithme ne s'embrouille pas et ne ralentit pas. Il continue de descendre la colline, tout aussi efficacement qu'auparavant.

À quelle vitesse est « rapide » ?

La découverte la plus excitante est la vitesse. Les auteurs ont prouvé que l'algorithme K-means converge vers une bonne solution à une vitesse de O(1/t).

Décomposons cela avec une métaphore simple : imaginez que vous marchez vers un coffre au trésor.

Si vous marchiez à une vitesse de O(1/√t), vous feriez un grand pas au début, mais vos pas deviendraient de plus en plus petits très rapidement, comme si vous marchiez dans de la boue épaisse.
Mais parce que K-means est en réalité un Frank-Wolfe, il marche à une vitesse de O(1/t). Cela signifie que vos pas deviennent plus petits, mais vous êtes garanti de vous rapprocher du trésor de manière beaucoup plus prévisible.

Crucialement, les auteurs ont montré que cette vitesse dépend uniquement de la distance à laquelle vous avez commencé par rapport à la meilleure solution possible. Peu importe que vous ayez un million de points de données (une fête géante) ou seulement quelques-uns ; la garantie de vitesse reste vraie. C'est un événement majeur car les théories précédentes devenaient souvent confuses et compliquées lorsque le nombre de points de données augmentait.

Tester la théorie

Pour s'assurer qu'il ne s'agissait pas seulement d'un joli tour de passe-passe mathématique, l'équipe a lancé des simulations massives.

Ils ont créé des données fictives ressemblant à des « amas » de points (comme des nuages colorés de confettis) et ont exécuté l'algorithme K-means des milliers de fois.
Ils ont également testé l'algorithme sur un ensemble de données réelles de segmentation d'image, où l'objectif est de regrouper les pixels d'une photo pour séparer le ciel, l'herbe et les bâtiments.

Dans chaque test, l'« écart » entre l'endroit où l'algorithme se trouvait et l'endroit où il voulait être s'est réduit exactement comme la mathématique le prédisait. Lorsqu'ils ont tracé les résultats sur un graphique, la ligne descendait avec une pente de -1.0, ce qui est la signature mathématique de la vitesse O(1/t). Même lorsque les données étaient désordonnées ou que les clusters avaient des formes étranges, l'algorithme a gardé son sang-froid.

Une nouvelle façon d'arrêter l'algorithme

L'un des enseignements les plus pratiques est de savoir quand arrêter la fête. Habituellement, les ordinateurs arrêtent K-means lorsque les centres cessent de bouger de manière significative. Mais les auteurs suggèrent une meilleure méthode : arrêter lorsque l'écart de Frank-Wolfe (la différence de score entre l'arrangement actuel et l'arrangement suivant possible) devient suffisamment petit.

Cette nouvelle règle d'arrêt est comparable à avoir une jauge de carburant qui vous indique exactement quelle quantité de « travail » reste à accomplir. C'est plus fiable que de deviner, et cela donne une limite stricte au nombre d'étapes que l'algorithme devra prendre.

L'essentiel à retenir

Ce papier n'invente pas une nouvelle façon de faire du K-means ; il révèle plutôt que la vieille méthode de confiance que nous utilisons depuis des décennies est en fait une version déguisée d'un outil mathématique moderne et puissant. En reliant ces deux mondes, les auteurs nous ont donné une limite de vitesse claire et prouvée pour le K-means, ainsi qu'une meilleure façon de savoir quand la tâche est terminée. C'est un rappel que, parfois, les outils les plus familiers de la science ne portent simplement pas le costume que nous pensions.

Résumé technique : L'algorithme de partitionnement K-means de Lloyd est un algorithme de Frank-Wolfe déguisé

Énoncé du problème
L'algorithme K-means de Lloyd (K-means naïf) est une heuristique omniprésente pour minimiser la somme des carrés des erreurs (SSE) à travers les $K$ -partitions d'un ensemble de données. Malgré son utilisation généralisée, la compréhension théorique de sa convergence reste limitée, particulièrement en ce qui concerne les taux non asymptotiques qui soient uniformes par rapport à la taille de l'échantillon ( $n$ ), la dimension ( $d$ ) et le nombre de clusters ( $K$ ). Les analyses de convergence existantes reposent souvent sur des $\epsilon$ -coreset, où les bornes ont tendance à exploser lorsque $\epsilon \to 0$ , ou se concentrent sur le comportement asymptotique. De plus, les cadres d'optimisation standard peinent face à la nature « gourmande » de l'assignation de Lloyd, qui peut conduire à des clusters vides, rendant la fonction objectif non lisse (semi-lisse) et difficile à analyser avec les outils d'optimisation classique de fonctions lisses.

Méthodologie
Les auteurs établissent une nouvelle connexion théorique en démontrant que l'algorithme K-means de Lloyd est un cas particulier de l'algorithme de Frank-Wolfe (FW) (également connu sous le nom de descente de gradient conditionnelle) appliqué à une fonction objective concave sur un ensemble polyédrique.

Formulation comme optimisation continue : Le problème de partitionnement discret K-means est encodé à l'aide d'un vecteur « one-hot » $w \in \{0, 1\}^{n \times K}$ . L'objectif SSE $f(w)$ est étendu continûment au corps convexe de ces partitions, $M = \text{conv}(M_0)$ .
Concavité et semi-lissité : Les auteurs prouvent que l'objectif SSE étendu est une fonction concave. Crucialement, bien que la fonction soit lisse à l'intérieur de l'ensemble admissible (où tous les clusters sont non vides), elle devient semi-lisse lorsque les clusters deviennent vides.
Équivalence FW :
- Clusters non vides : Lorsque tous les clusters sont non vides, l'étape d'assignation gourmande de Lloyd correspond exactement à une étape FW avec un pas unitaire ( $\gamma_t = 1$ ) sur le polytope des partitions admissibles.
- Clusters vides : Pour gérer les clusters vides, les auteurs développent une variante de l'algorithme FW pour des objectifs concaves généraux et semi-lisses. Ils utilisent le sous-différentiel de Clarke (plutôt que le sous-gradient de Goldstein) pour définir un écart FW de Clarke généralisé. Ils montrent que la stratégie de Lloyd consistant à conserver le centroïde précédent pour un cluster vide correspond à la sélection d'un élément du sous-différentiel de Clarke de l'objectif étendu.
Analyse de convergence : En s'appuyant sur les avancées récentes des méthodes FW pour les objectifs concaves (spécifiquement Yurtsever et Sra, 2022), les auteurs dérivent un taux de convergence non asymptotique. Ils définissent une mesure de stationnarité basée sur l'écart FW de Clarke, $g_C(x)$ , et prouvent que l'écart minimal rencontré après $t$ itérations satisfait $\tilde{g}_t \leq h_0 / (t+1)$ , où $h_0$ est la sous-optimalité globale initiale.

Principales contributions

Unification théorique : L'article prouve que l'algorithme de Lloyd avec assignation gourmande est un cas particulier de l'algorithme FW avec un pas unitaire pour un objectif concave semi-lisse sur un ensemble polyédrique.
Taux de convergence : Les auteurs établissent un taux de convergence non asymptotique en $O(1/t)$ vers un minimum local de l'objectif SSE. Ce taux est contrôlé uniquement par la valeur SSE initiale ( $h_0$ ) et est uniforme par rapport à $n$ , $d$ et $K$ . Il évite la dépendance aux paramètres de $\epsilon$ -coreset qui pénalisent les analyses précédentes.
Gestion des clusters vides : Une nouvelle variante de FW pour les objectifs concaves semi-lisses est développée, utilisant le sous-différentiel de Clarke. Cela permet au cadre théorique d'intégrer le scénario, pourtant pertinent en pratique, des clusters vides sans sacrifier le taux de convergence.
Nouvelle mesure d'erreur : Le travail propose l'écart FW (équivalent à la diminution de la SSE, $\Delta SSE_t$ ) comme critère d'arrêt. Contrairement à la métrique standard de mouvement des centroïdes, cette mesure est invariante par transformation affine et s'accompagne d'une garantie théorique sur le nombre maximal d'étapes requises pour atteindre une tolérance donnée.

Résultats

Étude de simulation : Les auteurs ont mené des simulations de Monte Carlo approfondies sur des mélanges gaussiens sphériques synthétiques (« blobs ») et un jeu de données de segmentation d'images réel.
- Données synthétiques : À travers diverses configurations de $n$ , $d$ et $K$ , l'écart FW dans le pire des cas a décroît de manière monotone. L'analyse de régression des graphiques log-log a confirmé une pente cohérente avec $-1$, soutenant le taux $O(1/t)$ .
- Données réelles : Sur le jeu de données de segmentation d'images de l'UCI (qui viole les hypothèses gaussiennes et sphériques), le taux de convergence empirique a également soutenu la borne $O(1/t)$ , l'hypothèse nulle d'une pente de $-1$ n'étant pas rejetée.
Bornes théoriques : La borne dérivée $h_0/(t+1)$ fournit une estimation concrète de la sous-optimalité initiale, qui évolue linéairement avec $n$ et la trace de la matrice de covariance de l'échantillon.

Signification et affirmations
L'article affirme que l'examen de l'algorithme K-means de Lloyd à travers le prisme de l'optimisation FW semi-lisse offre un « nouvel outil simple, mais puissant » qui propose :

Garanties de convergence : Des taux $O(1/t)$ non asymptotiques rigoureux qui sont uniformes par rapport aux dimensions du problème, une amélioration significative par rapport aux analyses heuristiques précédentes.
Contrôle d'erreur pratique : Une règle d'arrêt théoriquement fondée basée sur l'écart FW (diminution de la SSE) plutôt que sur des seuils arbitraires de mouvement des centroïdes. Cela permet de calculer le nombre maximal d'itérations nécessaires pour atteindre une précision donnée.
Robustesse : L'approche est robuste aux modifications et extensions, telles que le K-means élagué (trimmed K-means) ou l'analyse de clusters robuste, car elle repose sur la géométrie convexe générale plutôt que sur des structures de polytopes spécifiques ou des arguments combinatoires.

Les auteurs notent que bien que les résultats soient significatifs pour le K-means standard et robuste, les extensions aux contextes en ligne/stochastiques et aux mélanges elliptiques généraux restent des défis ouverts. Ce travail est présenté comme une étape fondamentale pour l'application des techniques d'optimisation sans projection aux problèmes de partitionnement combinatoire.