Analyse lisse d'algorithme

En informatique théorique, l'analyse lisse d'algorithme (smoothed analysis) est une manière de mesurer la complexité d'un algorithme, c'est-à-dire ses performances. Elle complète et améliore les mesures classiques de complexité : la complexité dans le pire des cas, la complexité en moyenne et la complexité amortie. Elle a été inventée dans les années 2000 par Daniel Spielman et Shang-Hua Teng.

L'introduction de cette nouvelle mesure de complexité a été motivée, d'une part par l'existence de certains algorithmes fonctionnant très bien en pratique mais dont l'analyse dans le pire des cas ne montrait pas l'efficacité, et d'autre part par la difficulté de l'analyse en moyenne en général.

Le principe de l'analyse lisse est de mesurer les performances de l'algorithme sur les pires cas, mais avec une légère perturbation des instances. On calcule donc une espérance de performance. D'une certaine manière, c'est une méthode « locale »^[1].

Plus précisément, on ajoute un bruit gaussien aux entrées, c'est-à-dire une variation aléatoire des données qui suit une loi normale. La complexité mesurée dépend alors de deux paramètres : la taille de l'entrée mais aussi l'écart-type de la gaussienne utilisée.

Si l'analyse lisse annonce pour un algorithme de bonnes performances parmi l'espace des valeurs centrées autour d'une donnée en ajoutant du bruit (gaussien) à cette donnée, cela signifie que, dans la pratique, il devrait y avoir aussi de bonnes performances pour cet algorithme dans tous les cas.

Conceptuellement, l'analyse lisse se place entre l'analyse de la complexité dans le pire cas, puisque l'on s’intéresse aux pires performances, et l'analyse de la complexité moyenne, puisque l'on considère une perturbation aléatoire.

Cette méthode ne peut pas toujours être facilement mise en pratique : il faut pouvoir définir une perturbation gaussienne, ce qui est assez naturel pour le cas de l'optimisation linéaire par exemple, mais l'est beaucoup moins pour d'autres problèmes plus combinatoires.

L'une des applications majeures de l'analyse lisse est une démonstration de l'efficacité du simplexe, un algorithme utilisé en optimisation linéaire et connu pour son efficacité pratique et pour sa complexité exponentielle dans le pire cas. Il a été démontré que la complexité lisse du simplexe est polynomiale (Spielman et Teng 2004).

Plus précisément, un problème d'optimisation linéaire s'écrit sous la forme :

${\displaystyle \left\{{\begin{array}{l}{\max }_{x}\;c^{\top }x\\Ax\leqslant b.\end{array}}\right.}$

On s’intéresse alors à des instances du problème de la forme

${\displaystyle \left\{{\begin{array}{l}{\max }_{x}\;c^{\top }x\\{\tilde {A}}x\leqslant {\tilde {b}}.\end{array}}\right.}$

où la matrice ${\displaystyle {\tilde {A}}}$ et le vecteur ${\displaystyle {\tilde {b}}}$ sont les résultats d'une perturbation gaussienne de ${\displaystyle A}$ et ${\displaystyle b}$, d'écart-type ${\displaystyle \sigma \max(a_{ij},b_{j})}$.

Le maximum sur ${\displaystyle A}$, ${\displaystyle b}$, et ${\displaystyle c}$, de l'espérance du temps de calcul du simplexe^[2] sur ${\displaystyle {\tilde {A}}}$ et le vecteur ${\displaystyle {\tilde {b}}}$, est polynomiale en la taille de ${\displaystyle A}$ et en ${\displaystyle 1/\sigma }$.

Il avait été démontré précédemment que le simplexe a une complexité polynomiale en espérance (pour plusieurs distributions naturelles des instances)^[3].

L'analyse lisse a entre autres été utilisée dans les domaines de l'apprentissage automatique (par exemple pour le problème des k-moyennes^[4] et dans le cadre de l'apprentissage PAC^[5]) et de l'exploration de données^[6].

En algorithmique plus classique elle a permis une nouvelle approche de certains algorithmes connus, comme le pivot de Gauss^[7] ou le tri rapide^[8],[9].

L'analyse lisse a été inventée en 2000 par Daniel Spielman et Shang-Hua Teng (Spielman et Teng 2004). Pour cela, ils ont reçu le prestigieux prix Gödel 2008^[10] et le prix Fulkerson 2009. Spielman a aussi reçu le prix Nevanlinna en 2010, pour ses travaux sur l'analyse lisse^[11].

Le nom smoothed analysis a été proposé par Alan Edelman^[12],[13].

• Daniel A. Spielman et Shang-Hua Teng, « Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time », Journal of the ACM, vol. 51, n^o 3,‎ 2004, p. 385–463 (lire en ligne)
• Daniel A. Spielman et Shang-Hua Teng, « Smoothed analysis: an attempt to explain the behavior of algorithms in practice », Communications of the ACM, vol. 52, n^o 10,‎ 2009, p. 76–84 (lire en ligne)
• (en) David Arthur, Bodo Manthey et Heiko Roglin, « k-Means Has Polynomial Smoothed Complexity », dans Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 2009 (lire en ligne), p. 405--414
• Cyril Banderier, Rene Beier et Kurt Mehlhorn, « Smoothed analysis of three combinatorial problems », Lecture notes in computer science,‎ 2003, p. 198-207 (lire en ligne)
• Arvind Sankar, Daniel Spielman et Shang-Hua Teng, « Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices », SIAM J. Matrix Analysis Applications, vol. 28, n^o 2,‎ 2006, p. 446-476
• (en) Adam Tauman Kalai, Alex Samorodnitsky et Shang-Hua Teng, « Learning and smoothed analysis », dans Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, IEEE Computer Society, 2009, p. 395--404

• Étienne Ghys, « Des événements rares... », Images des Mathématiques,‎ 2010 (lire en ligne)

• Smoothed Analysis Homepage

• Portail de l'informatique théorique