Quand la randomisation accélère-t-elle les algorithmes et ne devrait-elle pas?

La preuve de Adleman que est contenu dans montre que s'il existe un algorithme aléatoire pour un problème qui fonctionne en temps sur les entrées de taille , alors il y a aussi un algorithme déterministe pour le problème qui fonctionne en temps sur les entrées de taille [l’algorithme exécute l’algorithme randomisé sur des chaînes aléatoires indépendantes. Il doit y avoir un hasard pour l'algorithme répété qui est bon pour tous lesP / p o l y t ( n ) n Θ ( t ( n ) ⋅ n ) n Θ ( n ) 2 $BPP$$P/poly$$t(n)$$n$$\Theta(t(n)\cdot n)$$n$$\Theta(n)$$2^n$entrées possibles]. L'algorithme déterministe n'est pas uniforme - il peut se comporter différemment pour différentes tailles d'entrée. Ainsi, l'argument d'Adleman montre que - si l'on ne se soucie pas de l'uniformité - la randomisation ne peut accélérer les algorithmes que par un facteur linéaire dans la taille de l'entrée.

Quels sont quelques exemples concrets où la randomisation accélère le calcul (à notre connaissance)?

Un exemple est le test d'identité polynomiale. Ici, l'entrée est un circuit arithmétique de taille n qui calcule un polynôme m-variable sur un champ et la tâche consiste à déterminer si le polynôme est identique à zéro. Un algorithme randomisé peut évaluer le polynôme sur un point aléatoire, tandis que le meilleur algorithme déterministe que nous connaissons (et éventuellement le meilleur qui existe) évalue le polynôme sur de nombreux points.

Un autre exemple est le Spanning Tree minimum, où le meilleur algorithme randomisé de Karger-Klein-Tarjan est le temps linéaire (et la probabilité d'erreur est exponentiellement faible!), Tandis que le meilleur algorithme déterministe de Chazelle s'exécute dans le temps ( est la fonction inverse d'Ackermann, donc la vitesse de randomisation est vraiment petite). Fait intéressant, Pettie et Ramachandran ont prouvé que s’il existait un algorithme de temps linéaire déterministe non uniforme pour l’espacement minimal, il existait également un algorithme de temps linéaire déterministe uniforme.$O(m\alpha(m,n))$$\alpha$

Quels sont d'autres exemples? Quels exemples connaissez-vous où l’accélération de la randomisation est importante, mais c’est peut-être simplement parce que nous n’avons pas encore trouvé d’algorithmes déterministes suffisamment efficaces?

Je ne sais pas si aléatoire « devrait » ou « ne devrait pas » l' aide, cependant, les tests de primalité entier peut être fait dans le temps en utilisant Miller-Rabin aléatoire, tout autant que je sache, le plus connu algorithmes déterministes sont ~ O ( n 4 ) en supposant HGR (Miller-Rabin déterministe) ou ~ O ( n 6 ) sans conditions (variantes de AKS).$\tilde O(n^2)$$\tilde O(n^4)$$\tilde O(n^6)$

Un ancien exemple est le calcul de volume. Compte tenu d' un polytope décrit par un oracle d'appartenance, il y a un algorithme aléatoire en cours d' exécution en temps polynomial pour estimer le volume à un facteur, mais aucun algorithme déterministe peut venir même près sans conditions .$1+\epsilon$

Le premier exemple d'une telle stratégie randomisée a été fourni par Dyer, Frieze et Kannan, et le résultat de la dureté pour les algorithmes déterministes est fourni par Bárány et Füredi. Alistair Sinclair a de bonnes notes de cours à ce sujet .

Je ne suis pas sûr de bien comprendre la partie "et cela ne devrait pas" de la question, donc je ne suis pas sûr que cela corresponde à la facture.

Je ne sais pas si cela répond à votre question (ou au moins une partie de celle-ci). Mais pour des exemples concrets dans lesquels la randomisation peut fournir une accélération, il s’agit de problèmes d’optimisation et de la relation avec le théorème No Free Lunch ( NFL ) .

Il existe un article "Peut-être pas un repas gratuit, mais au moins un apéritif gratuit" où il est montré que l'utilisation d'algorithmes de randomisation (optimisation) peut avoir de meilleures performances.

Abstrait:

On prétend souvent que les algorithmes évolutifs sont supérieurs aux autres techniques d'optimisation, en particulier dans les situations où l'on ne sait pas grand-chose de la fonction objectif à optimiser. Contrairement à cela, Wolpert et Macready (1997) ont prouvé que toutes les techniques d'optimisation ont le même comportement - en moyenne sur tous les où X et $f : X \rightarrow Y$$X$$Y$sont des ensembles finis. Ce résultat s'appelle [le] théorème sans repas gratuit. Ici, différents scénarios d'optimisation sont présentés. On explique pourquoi le scénario sur lequel est basé le théorème du sans repas gratuit ne modélise pas l'optimisation réelle. Pour des scénarios plus réalistes, on explique pourquoi les techniques d'optimisation diffèrent par leur efficacité. Pour un petit exemple, cette affirmation est prouvée.

Les références:

1. Aucun théorème de repas gratuit pour l'optimisation ( théorème original de la NFL pour l'optimisation)
2. Peut-être pas un repas gratuit mais au moins un apéritif gratuit
3. Durée sans description et sans repas (indique que les résultats de la NFL sont valables pour tout sous-ensemble de l'ensemble des fonctions possibles si et seulement si F est fermé par permutation, coupelle )$F$$F$
4. Sur les classes de fonctions pour lesquelles les résultats No Free Lunch sont valables (il est prouvé que la fraction des sous-ensembles constituant une tasse est négligeable)
5. Deux grandes catégories de fonctions pour lesquelles un résultat «pas de repas libre» n'est pas valable (indique qu'un résultat NFL ne s'applique pas à un ensemble de fonctions lorsque la longueur de description des fonctions est suffisamment limitée)
6. Les déjeuners continus sont gratuits et la conception d’algorithmes d’optimisation optimaux (montre que pour les domaines continus, la version officielle de la NFL ne tient pas. Ce théorème du déjeuner libre est basé sur la formalisation du concept de fonction de fitness aléatoire à l’aide de champs aléatoires. )
7. Au-delà de l'absence de repas libre: algorithmes réalistes pour les classes de problèmes arbitraires (indique que "toutes les violations des théorèmes de l'absence de repas libre peuvent être exprimées sous forme de distributions uniformes non bloc sur des sous-ensembles de problèmes qui sont une coupe ")
8. Algorithmes métaheuristiques en essaim et théorèmes de repas sans repas gratuits ("[... tasse nécessaire pour prouver les théorèmes de la NFL (Marshall et Hinton, 2010) ")
9. Pas de repas gratuit et de hasard algorithmique
10. Pas de repas et de points de repère gratuits (une approche fondée sur la théorie des ensembles est généralisée à des critères non spécifiques à la coupe , mais note néanmoins que les algorithmes aléatoires (non triviaux) peuvent surperformer les algorithmes déterministes en moyenne, "[...] a démontré que la probabilité est insuffisante pour affirmer des résultats NFL sans contrainte dans le cas général. [..] cet article abandonne la probabilité, préférant un cadre théorique d'ensemble qui supprime les limitations théoriques de la mesure en se dispensant complètement de la probabilité ")

Résumé sur les déjeuners gratuits (et les déjeuners gratuits) de David H. Wolpert, Que coûte le dîner? ( notez que les théorèmes de type NFL ne spécifient jamais de " prix " réel en raison de leur type de preuve)

en particulier pour l'optimisation généralisée (GO):

1. $X$$Z$$X$$Z$

2. $f: X \to Z$

3. $m$$f$

   $$d_m = \{d_m(1), d_m(2), ..., d_m(m)\}$$ $\forall t$ $$d_m(t) =\{d^X_m(t),d^Z_m(t)\}$$ $d^Z_m(t)$$f[d^X_m(t)]$

4. $a = \{d_t \to d^X_m(t) : t=0..m\}$

5. $C(f, d_m)$

6. $C(., .)$

$C$$f$$C$$f$$C$$(f, d_m)$$f = f^*$

Enfin, une remarque simple (et pas si simple) qui explique pourquoi la randomisation (sous une forme ou une autre) peut fournir des performances supérieures à celles des algorithmes strictement déterministes.

1. Dans le contexte de l' optimisation (bien que cela ne soit pas limité à cela), une procédure de recherche aléatoire peut en moyenne échapper mieux aux extrema locaux que la recherche déterministe et atteindre des extrema globaux.
2. $2^A$$A$$A$$A$$A$

Le meilleur exemple est dans la zone actuellement considérée comme la meilleure candidate pour les fichiers OWF, où il semble que chaque fichier OWF populaire cuit de manière surprenante possède un algorithme sous-exponentiel aléatoire alors qu'il n'existe aucun algorithme sous-exponentiel déterministe (par exemple, la factorisation entière). En fait, dans de nombreux cas, il existe probablement un algorithme efficace avec quelques chaînes de conseil (analyse cryptographique).

Si vous avez un algorithme utilisant la randomisation, vous pouvez toujours le remplacer par un algorithme déterministe utilisant des nombres pseudo-aléatoires: Prenez la description du problème, calculez un code de hachage, utilisez ce code de hachage comme germe pour un bon générateur de nombres pseudo-aléatoires. . En pratique, c'est ce qui risque de se produire lorsque quelqu'un implémente un algorithme en utilisant la randomisation.

Si nous omettons le code de hachage, la différence entre cet algorithme et un algorithme utilisant la vraie randomisation est que je peux prédire la séquence de nombres aléatoires générés et que je pourrais produire un problème tel que le nombre aléatoire prédit appliqué à mon problème sera toujours. prendre la pire décision possible. Par exemple, pour Quicksort avec un pivot pseudo-aléatoire, je pourrais construire un tableau en entrée où le pivot pseudo-aléatoire trouvera toujours la valeur la plus grande possible dans le tableau. Avec le vrai hasard, ce n'est pas possible.

Avec le code de hachage, il me serait très difficile de construire un problème où les nombres pseudo-aléatoires produisent les pires résultats. Je peux toujours prédire les nombres aléatoires, mais si je modifie le problème, la séquence des nombres pseudo-aléatoires change complètement. Néanmoins, il serait presque impossible pour vous de prouver que je ne peux pas construire un tel problème.