Les chercheurs ont amélioré la borne de convergence de la marche de Dikin, une méthode pour échantillonner uniformément à partir de polytopes inspirée des méthodes de point intérieur. La nouvelle preuve démontre que l'utilisation d'une métrique de Lee-Sidford mise à l'échelle réduit le temps de mélange de $d^{2.5}$ itérations à $d^{2.25}$ itérations.
- La marche de Dikin avec une métrique de Lee-Sidford mise à l'échelle se mélange en $d^{2.25}$ itérations à partir d'un démarrage chaud, améliorant la borne précédente de $d^{2.5}$ établie par Chen et al.
- Cette amélioration repose sur l'établissement d'une auto-concordance moyenne meilleure pour la métrique de Lee-Sidford, ce qui augmente la probabilité d'acceptation du filtre de Metropolis.
- L'analyse emploie des techniques d'ordre supérieur, y compris le développement sélectif des termes de goulot d'étranglement récursifs et les décompositions de chaos de Wiener pour contrôler les polynômes gaussiens.
Le résultat se rapproche du temps de mélange optimal conjecturé de $d^2$ et fournit une complexité de démarrage à froid améliorée grâce à un cadre d'annealing connu.