디킨 워크의 혼합 시간 상한을 d^2.5 에서 d^2.25 로 개선

연구자들은 다면체에서 균일하게 샘플링하는 방법인 디킨 워크(Dikin walk)의 수렴 상한을 개선했습니다. 이 방법은 내점법(interior-point methods)에 영감을 받았습니다. 새로운 증명에 따르면, 스케일된 리-시드포드 계량(Lee-Sidford metric)을 사용하면 혼합 시간이 $d^{2.5}$ 반복에서 $d^{2.25}$ 반복으로 단축됩니다.

• 스케일된 리-시드포드 계량을 사용한 디킨 워크는 따뜻한 시작(warm start)으로부터 $d^{2.25}$ 반복 만에 혼합되며, Chen等人이 확립한 이전의 $d^{2.5}$ 상한을 개선합니다.
• 이 개선은 리-시드포드 계량의 평균 자기공명성(self-concordance)을 더 잘 설정하는 데 기반하며, 이는 메트로폴리스 필터의 수용 확률을 증가시킵니다.
• 이 분석에는 재귀적 병목 현상 항의 선택적 전개와 가우스 다항식을 제어하기 위한 위너-카오스 분해(Wiener-chaos decompositions)를 포함한 고차 기법이 사용됩니다.

이 결과는 가정된 최적 혼합 시간 $d^2$ 에 더 가까워지며, 알려진 아네일링 프레임워크를 통해 차가운 시작(cold-start) 복잡성도 개선합니다.