Dikin Walks Move Past the d^2.5 Mixing Barrier on Polytopes

Lead

Sampling from high-dimensional polytopes is a central problem in randomized algorithms, convex optimization, and parts of machine learning. Dikin walks address this task by borrowing geometry from interior-point methods: instead of proposing moves in a fixed Euclidean ball, they adapt the proposal distribution to the local barrier geometry of the feasible region. A new arXiv paper, “Beyond the $d^{2.5}$-mixing bound for Dikin walks on polytopes,” reports progress on one of the key theoretical questions in this line of work: how fast such walks mix.

The paper proves that, for exponential sampling over a polytope, a Dikin walk built from a scaled Lee–Sidford metric mixes from a warm start in $d^{2.25}$ iterations. This improves the previously known $d^{2.5}$ bound and moves closer to the conjectured $d^2$ rate.

Key points

• Why Dikin walks matter: Introduced by Kannan and Narayanan in 2009, Dikin walks use barrier-induced local geometry to sample from polytopes. Like interior-point methods, they are affine-invariant, which makes their behavior depend on the geometry of the representation rather than on arbitrary coordinate scaling.
• Earlier milestones: For a polytope in $\mathbb{R}^d$ described by $m$ linear inequalities, the logarithmic-barrier Dikin walk was shown to mix in $md$ iterations. In 2017, Chen, Dwivedi, Wainwright, and Yu improved the dimension dependence to $d^{2.5}$ using a Lewis-weight barrier, and conjectured that the right order should be $d^2$.
• New result: The new work does not fully resolve the conjecture, but it breaks the $d^{2.5}$ barrier by proving a $d^{2.25}$ warm-start mixing bound for exponential sampling with a scaled Lee–Sidford metric.
• Technical ingredient: The central contribution is an improved average self-concordance property for the Lee–Sidford metric. This helps show that a random Dikin proposal is accepted by the Metropolis filter with high probability.
• Higher-order analysis: Prior approaches were effectively constrained by second-order control. This paper develops a more principled higher-order framework, combining selective expansions of recursive bottleneck terms, a moving orthonormal-frame calculus for higher derivatives of Lewis weights, and Wiener-chaos decompositions through multiple stochastic integrals.

Why it matters

The improvement from $d^{2.5}$ to $d^{2.25}$ is a theoretical advance, not a claim of immediate empirical acceleration. Still, such bounds are important because they shape our understanding of what is possible for high-dimensional sampling under linear constraints. The result suggests that the geometry used to define local proposals can still be sharpened, and that higher-order probabilistic control may unlock further progress.

The work is also relevant beyond one exponent. By developing tools to handle the complicated derivatives of Lewis weights and the Gaussian polynomials arising from random proposals, it provides a route for future analyses of Dikin-type walks. If the long-standing $d^2$ conjecture is eventually reached, techniques of this kind may be part of the path.

Source: arXiv