Improved Dikin walk mixing bound from d^2.5 to d^2.25

Researchers have improved the convergence bound for the Dikin walk, a method for sampling uniformly from polytopes inspired by interior-point methods. The new proof demonstrates that using a scaled Lee-Sidford metric reduces the mixing time from $d^{2.5}$ to $d^{2.25}$ iterations.

• The Dikin walk with a scaled Lee-Sidford metric mixes in $d^{2.25}$ iterations from a warm start, improving upon the previous $d^{2.5}$ bound established by Chen et al.
• This improvement relies on establishing better average self-concordance for the Lee-Sidford metric, which increases the acceptance probability of the Metropolis filter.
• The analysis employs higher-order techniques, including selective expansion of recursive bottleneck terms and Wiener-chaos decompositions to control Gaussian polynomials.

The result moves closer to the conjectured optimal mixing time of $d^2$ and provides improved cold-start complexity through a known annealing framework.