A new theoretical analysis says a carefully retained part of the Metropolis proposal calculation can make the acceptance behavior of Dikin walks tractable enough to prove warm-start mixing bounds. The framework covers walks on polytopes and spectrahedra, two kinds of bounded convex bodies, and centers on an exact cancellation that removes an uncentered term before concentration estimates are applied.
For the polytope case, the formal result gives a soft-O((d² + dL²R²) log(w/δ)) bound on the number of steps needed to reach total-variation distance δ from the target distribution, starting from a warm distribution with parameter w. Here, d is the dimension, L controls how quickly the convex potential can vary, and R bounds the body’s radius. The notation hides logarithmic factors and universal constants, and the statement applies only under the theorem’s geometric and warm-start assumptions.
The work studies mathematical target distributions proportional to e−f on bounded convex bodies rather than an empirical population or dataset. The manuscript is a preprint identified as arXiv:2608.25273v1 [cs.DS], dated 26 Aug 2026 in its front matter, with August 27, 2026 also shown as the manuscript date.
The algebra behind the result
A Metropolis-adjusted walk proposes a move and then accepts or rejects it using a ratio that accounts for the target density and for changes in the proposal distribution. The paper keeps the complete Gaussian proposal log-ratio in view. In its normalized reference-walk setup, the determinant’s linear part and the mean of a random quadratic form are exactly the same uncentered coupling term. They cancel, leaving a centered fluctuation and a second-order determinant remainder.
That identity is the paper’s central proof device. The remaining fluctuation terms are controlled with a combination of Lewis-weight Jacobian calculations, a stability tube, row-dependent Hessian contraction, twice-integrated Gaussian Stein identities, a cutoff, and Gaussian concentration. The goal is to control acceptance fluctuations locally, where nearby proposals can still produce overlapping transition distributions.
The resulting argument moves from local Gaussian overlap to overlap of the full transition kernels. It then uses metric symmetry, cross-ratio isoperimetry, conductance, and Cheeger’s inequality to turn the local acceptance calculation into a mixing estimate for a lazy reversible chain.
Two geometries, two bounds
For polytopes, the reference chain is a lazy Metropolis walk built with exact Lewis weights and an exact acceptance ratio. Its proposal covariance is r²/d times (κHLS(x)+L²I)−1, using regularized Lee–Sidford geometry. The theorem applies to a bounded full-dimensional body K contained in a radius-R Euclidean ball in d dimensions, described by n linear inequalities, with a convex L-Lipschitz potential f and target density proportional to e−f on K.
For spectrahedra, the paper studies bounded bodies inside the same radius-R ball after reduction to a minimal face so that the problem is strictly feasible. The constraints are represented by n×n matrix blocks, and the target again has density proportional to e−f for a convex L-Lipschitz potential. The exact-metric log-det walk is assigned a soft-O((ψ∗+ + nd + dL²R²) log(w/δ)) warm-start bound, with κ selected at a soft-O(ψ∗+) scale. The parameter ψ∗ is the theorem’s leverage quantity, so the rate depends on more than dimension alone.
The authors interpret the two results as evidence that the same acceptance-tail strategy can support dimension-square mixing for polytopes and leverage-dependent mixing for spectrahedra. Those are conditional theorem statements, not measurements of how quickly a software implementation runs on a practical workload.
What an exact implementation would require
The paper also sketches how the reference chains could be transferred to approximate metrics without giving up exact reversibility in its arithmetic model. For polytopes, deterministic Lewis-weight approximations with relative accuracy on the order of 1/d and one-sided padding are stated to produce an exactly reversible walk. The arithmetic cost is soft-O((d²+dL²R²)(ndω−1+dω) log(ew/δ)), alongside soft-O((d²+dL²R²) log(ew/δ)) evaluations of f.
For spectrahedra, a direct or two-seed TensorSRHT sketch is stated to give an exactly reversible implementation when a leverage upper bound ψb satisfying ψb≥ψ∗+ is supplied. Its arithmetic cost is soft-O((ψbnd+dL²R²)(nω+n²d³ω−5) log(ew/δ)). The theorem also states that choosing ψb=d gives an unconditional replacement of ψbnd by nd², although that choice may be looser than a problem-specific bound.
These guarantees concern exact arithmetic and exact conditional density evaluations. They do not cover finite-bit conditioning, rounded Gaussian sampling, inexact Metropolis decisions, or the construction of the warm start. Formal approximate-metric kernels and exact-arithmetic complexity bounds are placed in Appendix A.
An example puts pressure on unscaled proposals
The paper includes an arrow spectrahedron to examine what happens when the proposal is not scaled by leverage. In the stated instance, f is identically zero, L=0, κ=1, and the walk starts at the center x=0. For proposal radius r at most r0 and dimension d at least d0, the lemma bounds acceptance above by e−dr²/10 + 2e−cd. Constant acceptance therefore requires r to be at most on the order of d−1/2, comparable to ψ(0)−1/2.
The result is a warning about acceptance on that family, not a universal lower bound on mixing time. It does not establish an if-and-only-if rule saying every spectrahedron needs leverage scaling. The authors instead interpret the example as showing that leverage scaling is needed for uniform acceptance up to logarithmic factors within the scope of their analysis.
What remains to be checked
The manuscript discloses that proof ideas were generated by GPT-5.6 Sol and Claude Fable 5, and that the resulting proofs were jointly verified by the same models. It says the authors reviewed the manuscript and take full responsibility for it.
The unresolved technical issues include finite-precision and bit-complexity guarantees, including conditioning and rounded sampling; a broader test of whether leverage scaling is pointwise necessary; sharper mixing lower bounds; and independent verification of the model-assisted proof arguments and their imported lemma applications. The paper therefore remains a theoretical account under stated assumptions, not a completed assessment of finite-precision performance.
Paper data and sources
Original title: A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra
Authors: Zhao Song, Lichen Zhang
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text