A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra

• URL: http://arxiv.org/abs/2608.25273v1
• Date: Wed, 26 Aug 2026 01:18:00 GMT
• Title: A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra
• Abstract summary: We analyze exact-metric, Metropolis-adjusted Dikin walks by keeping the proposal determinant and reverse quadratic form together.<n>For a polytope given by $n$ inequalities and a $L$-Lipschitz potential, this yields warm-start mixing in $widetilde O((d2+dL2R2)log(w/)$ steps for the regularized Lee--Sidford walk.
• Score: 12.89814955033651
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We analyze exact-metric, Metropolis-adjusted Dikin walks by keeping the proposal determinant and reverse quadratic form together. Their leading uncentered terms cancel in the complete logarithmic acceptance ratio, leaving centered fluctuations that can be controlled with second-order tools. For a polytope given by $n$ inequalities and a convex $L$-Lipschitz potential, this yields warm-start mixing in $\widetilde O((d^{2}+dL^{2}R^{2})\log(w/δ))$ steps for the regularized Lee--Sidford walk. For a spectrahedron with $n\times n$ blocks, the log-det walk mixes in $\widetilde O((ψ^\star nd+dL^{2}R^{2})\log(w/δ))$ steps, where $ψ^\star$ measures matrix leverage. The two analyses share an acceptance-to-mixing reduction. A proposal-comparison argument transfers the polytope bound to an appropriately padded $O(1/d)$-accurate metric computed from high-precision Lewis weights. For spectrahedra, given $\widehatψ\geψ^\star$, a direct-or-two-seed TensorSRHT construction gives an exact-arithmetic implementation with $ψ^\star$ replaced by $\widehatψ$ in the mixing bound.

Related papers

• On two proofs of $d^2$ mixing of weighted Dikin walks [6.216428054339837]
  We study the mixing time of weighted Dikin walks for sampling from exponential distributions on polytopes and truncated positive-semidefinite (PSD) cones.<n>Applying this framework to the Lee--Sidford, Lewis-weight, and John metrics yields an $widetilde O(d4)$ mixing bound for sampling from polytopes.
  arXiv  Detail & Related papers  (2026-08-28T17:43:58Z)
• Shallow ReLU$^s$ Networks in $L^p$-Type and Sobolev Spaces: Approximation and Path-Norm Controlled Generalization [12.871748162999062]
  In particular, when $_d$ is the uniform measure and $1le p2$, the approximation rate is $O!left(m-fracp(2s+2d+1)-2d2dpright)$ for $1le p*$ and $O!left(m-fracp(4s+3d-1)-2d+24dpright)$ for $p*p2$, where $p*=frac2d+2d+3$.<n>For non
  arXiv  Detail & Related papers  (2026-05-18T14:27:49Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
  arXiv  Detail & Related papers  (2026-03-20T01:53:44Z)
• Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update [62.96781471194877]
  Two principled strategies for handling heavy-tailed noise, truncation and median-of-means, have been introduced to heavy-tailed bandits.<n>We propose a emphone-pass algorithm based on the online mirror descent framework.
  arXiv  Detail & Related papers  (2025-03-01T09:41:45Z)
• Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk [12.842909157175582]
  We consider the problem of sampling from a $d$-dimensional log-concave distribution $pi(theta) propto exp(-f(theta))$ for $L$-Lipschitz $f$. We propose a emphrobust sampling framework that computes spectral approximations to the Hessian of the barrier functions in each iteration.
  arXiv  Detail & Related papers  (2024-10-08T05:32:51Z)
• On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
  This paper considers the RMSProp and its momentum extension and establishes the convergence rate of $frac1Tsum_k=1T.<n>Our convergence rate matches the lower bound with respect to all the coefficients except the dimension $d$.<n>Our convergence rate can be considered to be analogous to the $frac1Tsum_k=1T.
  arXiv  Detail & Related papers  (2024-02-01T07:21:32Z)
• Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein space [10.292118864147097]
  We develop a theory of finite-dimensional polyhedral subsets over the Wasserstein space and optimization of functionals over them via first-order methods.<n>Our main application is to the problem of mean-field variational inference, which seeks to approximate a distribution $pi$ over $mathbbRd$ by a product measure $pistar$.<n>As a byproduct of our analysis, we obtain the first end-to-end analysis for gradient-based algorithms for MFVI.
  arXiv  Detail & Related papers  (2023-12-05T16:02:04Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  We show how to construct variance-aware confidence sets for linear bandits and linear mixture Decision Process (MDP) For linear bandits, we obtain an $widetildeO(mathrmpoly(d)sqrt1 + sum_i=1Ksigma_i2) regret bound, where $d is the feature dimension. For linear mixture MDP, we obtain an $widetildeO(mathrmpoly(d)sqrtK)$ regret bound, where
  arXiv  Detail & Related papers  (2021-01-29T18:57:52Z)
• Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes [91.38793800392108]
  We study reinforcement learning with linear function approximation where the underlying transition probability kernel of the Markov decision process (MDP) is a linear mixture model. We propose a new, computationally efficient algorithm with linear function approximation named $textUCRL-VTR+$ for the aforementioned linear mixture MDPs. To the best of our knowledge, these are the first computationally efficient, nearly minimax optimal algorithms for RL with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-15T18:56:46Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  Solving optimal transport with an entropic regularization requires computing a $ntimes n$ kernel matrix that is repeatedly applied to a vector. We propose to use instead ground costs of the form $c(x,y)=-logdotpvarphi(x)varphi(y)$ where $varphi$ is a map from the ground space onto the positive orthant $RRr_+$, with $rll n$.
  arXiv  Detail & Related papers  (2020-06-12T10:21:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.