Beyond the d^2.5-mixing bound for Dikin walks on polytopes

Sampling from high-dimensional polytopes is a fundamental problem in convex geometry and optimization. While the Dikin walk—an affine-invariant algorithm—has long been known to mix in O(md) iterations, researchers have sought to reduce this dependence on the number of constraints (m) to a dependence purely on the dimension (d). This paper addresses the conjecture that the Dikin walk should mix in O(d^2) iterations, specifically focusing on improving the previous best bound of d^2.5.

The author analyzes the Dikin walk using the Lee-Sidford metric, which is based on Lewis weights of the constraint matrix. The primary technical challenge in proving faster mixing is the Average Self-Concordance (ASC) condition, which ensures that the local geometry of the polytope does not change too rapidly along a random proposal. Previous studies were limited to second-order Taylor expansions, which necessitated a larger scaling of the metric and resulted in a d^2.5 mixing bound. The author introduces a principled higher-order analysis, combining a selective expansion of recursive bottleneck terms, a moving orthonormal-frame calculus for higher derivatives, and Wiener-chaos decompositions to control the resulting Gaussian polynomials.

The paper proves that the Dikin walk, when using a scaled Lee-Sidford metric, achieves a warm-start mixing time of O(d^2.25) iterations. By incorporating this result into an existing annealing framework, the author also provides an improved cold-start complexity of approximately d^2.56. This represents the first significant progress toward the d^2-mixing conjecture in nearly a decade.

This work bridges the gap between interior-point methods in optimization and sampling algorithms. By demonstrating that higher-order analysis can yield tighter bounds than previously thought, the paper provides a new roadmap for potentially reaching the optimal d^2-mixing rate. These improvements are relevant for applications in systems biology and high-dimensional statistics where efficient sampling from constrained spaces is critical.