Let $K\subset\mathbb{R}^n$ be an isotropic convex body. We prove that the hit-and-run walk, started from any $M$-warm distribution, reaches total-variation distance $\varepsilon$ from the uniform distribution on $K$ in $O\!\left(n^2\psi_n^{-2}\log^3(M/\varepsilon)\right)$ steps, where $\psi_n^{-1}$ is the Kannan-Lov\'asz-Simonovits (KLS) constant. Up to logarithmic factors, this matches the best-known warm-start mixing time for the ball walk. Chen and Eldan [Discrete Comput. Geom. 2026] obtained the same $n^2\psi_n^{-2}$ dependence for hit-and-run, but with polynomial dependence on $M/\varepsilon$. Our result improves that polynomial dependence to a polylogarithmic one, fully resolving their open question about warm-start mixing of hit-and-run in isotropic convex bodies.
For any convex body $\mathcal{K}\subset\mathbb{R}^{n}$ containing a unit ball, the spectral gap of Hit-and-Run is $\Omega(1/(n^2 C_{\mathsf{PI}}))$, where $C_{\mathsf{PI}}$ is the Poincar\'e constant of the uniform distribution $\pi$ over $\mathcal{K}$. This implies that Hit-and-Run converges to a distribution within $\chi^2$-divergence $\varepsilon$ of the uniform distribution $\pi$ in $O(n^2 C_{\mathsf{PI}}\log(M/\varepsilon))$ steps from any starting distribution $\pi_0$ with $M=\chi^2(\pi_{0}\,\|\,\pi)$, thus refining the known bound of $O(n^2 R^2 \log(M/\varepsilon))$ by Lov\'asz and Vempala (2004) in terms of the outer radius $R$; for nearly isotropic bodies, together with progress on the KLS conjecture, the complexity is $O(n^2\log n\log(M/\varepsilon))$, improving the dimension dependence from cubic to nearly quadratic while maintaining logarithmic dependence on the initial distance. It was an open problem to connect the convergence of Hit-and-Run to Poincar\'e/KLS constants as was done for the Ball walk by Kannan, Lov\'asz and Simonovits (1997). Unlike Hit-and-Run, the Ball walk has an unavoidable linear dependence on (a stronger notion) of the initial warmness. We directly bound the spectral gap of the Hit-and-Run Markov chain by connecting it to functional isoperimetric constants, inspired by the recent analysis of In-and-Out. Rewriting the spectral gap in terms of dual certificates leads to the Babu\v{s}ka--Aziz constant studied in the analysis of PDEs; it is asymptotically bounded by the improved Poincar\'e constant, which we show can be bounded in terms of the usual Poincar\'e constant. The proof is based on duality and calculus, unlike known proofs of convergence for Hit-and-Run which are based on bounding the conductance. The same technique can be applied to Coordinate Hit-and-Run, resulting in a much improved mixing time of $O(n^3C_{\mathsf{PI}}\log(M/\varepsilon))$.
In this paper, we study the random walk on the symmetric group $\mathfrak{S}_n$ generated by the conjugacy class of $k$-cycles, where $2\le k=o(n/(\log n)^4)$. We prove that the walk exhibits hitting-time mixing: at the first time when every card has been touched, the distribution is already close to equilibrium. For odd $k$, the equilibrium measure is the uniform measure on $\mathfrak{A}_n$. For even $k$, the walk first mixes to the parity mixture determined by the hitting time, and in our range this mixture is asymptotically $U_{\mathfrak{S}_n}$. Our argument combines a refined fixed-time approximation for the random $k$-cycle walk near the cutoff window with an auxiliary marking scheme inspired by Jain-Sawhney's work (arXiv:2410.23944) on random transpositions. The main new feature is a parity-compatible coupling which handles both odd and even $k$-cycles in a unified framework. We also prove a hitting-time mixing result in the opposite regime $k\ge n-o(n^{1/2})$, and formulate a conjecture for all $2\le k\le n-1$.
Chen Shang, Jiahe Shen, Jiyue Zeng et al.· 1 citation
Let $f:\mathbb{R}^d \rightarrow \mathbb{R}$. We consider gradient descent $x_{n+1} = x_n - \tau_n \nabla f(x_n)$, where the stepsize $\tau_n = \tau \cdot e^{rn}$ is exponentially growing (with $\tau>0$ and $0<r \ll 1$). This diverges for almost all initial values. We show that restarting the algorithm whenever $\|x_{n+1} - x_n\| \geq e^r\|x_n - x_{n-1}\|$ has good properties: it works very well in practice; we determine the limiting convergence rate in the case of convergence to a non-degenerate local minimum: it improves on classic gradient descent even though computational cost is comparable. The precise choice of $0<r \ll 1$ does not matter much and the method is virtually independent of an initial stepsize $\tau$ that is too small: while the convergence rate for gradient descent decays linearly as $\tau \rightarrow 0$, it decays as $1/\log(1/\tau)$ in this modified version; numerical examples illustrate the results.
Franccois Cl'ement, Stefan Steinerberger· 0 citations
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/\delta))$ steps for the regularized Lee--Sidford walk. For a spectrahedron with $n\times n$ blocks, the log-det walk mixes in $\widetilde O((\psi^\star nd+dL^{2}R^{2})\log(w/\delta))$ steps, where $\psi^\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\psi\ge\psi^\star$, a direct-or-two-seed TensorSRHT construction gives an exact-arithmetic implementation with $\psi^\star$ replaced by $\widehat\psi$ in the mixing bound.
Let $C_n$ be the optimal constant with the following property. For every even, continuous, strictly positive density $f$ on $R^n$ and all origin-symmetric convex bodies $K,L\subset R^n$, the inequalities $$ \int_{K\cap\xi^\perp}f \leq \int_{L\cap\xi^\perp}f \qquad\text{for all }\xi\in S^{n-1} $$ imply $\int_Kf\leq C_n\int_Lf$. In an earlier paper the authors proved that $C_n\leq\sqrt n$. In this paper, we prove the matching lower bound $C_n\geq c\sqrt n$. To simplify the exposition, we first give a complete one-scale construction, based on earlier work of Klartag and Koldobsky, which yields $C_n\geq c\sqrt{n/\log n}$. For the sharp result, we use the random-rounding construction of Klartag and Livshyts as a black box and combine it with a spherical-averaging support-separation argument.
We provide a direct injection for the well-known strong log-convexity of the Bell numbers $B_n$, that is $B_mB_n\le B_{m-1}B_{n+1}$ for every $1\le m\le n$. Our injection $\Pi_m\times\Pi_n\to \Pi_{m-1}\times\Pi_{n+1}$, where $\Pi_n$ denotes the set of all partitions of $[n]$, preserves the total number of blocks in the pair of partitions. In other words, it is also an injection for the strong $q$-log-convexity of Touchard polynomials, a result established by Chen, Wang, and Yang using analytical arguments. As an application of the injection, we also recover a related result of Chern, Diaconis, Kane, and Rhoades.
