Pesquisadores melhoraram o limite de convergência para o passeio de Dikin, um método para amostrar uniformemente a partir de politopos inspirado em métodos de ponto interior. A nova prova demonstra que usar uma métrica escalada de Lee-Sidford reduz o tempo de mistura de $d^{2.5}$ para $d^{2.25}$ iterações.
- O passeio de Dikin com uma métrica escalada de Lee-Sidford se mistura em $d^{2.25}$ iterações a partir de um início quente, melhorando o limite anterior de $d^{2.5}$ estabelecido por Chen et al.
- Essa melhoria depende de estabelecer uma melhor autoconcordância média para a métrica de Lee-Sidford, o que aumenta a probabilidade de aceitação do filtro de Metropolis.
- A análise emprega técnicas de ordem superior, incluindo expansão seletiva de termos de gargalo recursivo e decomposições de Wiener-chaos para controlar polinômios gaussianos.
O resultado se aproxima do tempo de mistura ótimo conjecturado de $d^2$ e fornece complexidade de início frio melhorada através de um framework de annealing conhecido.