English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We propose and analyze two new MCMC sampling algorithms, the Vaidya walk andthe John walk, for generating samples from the uniform distribution over apolytope. Both random walks are sampling algorithms derived from interior pointmethods. The former is based on volumetric-logarithmic barrier introduced byVaidya whereas the latter uses John's ellipsoids. We show that the Vaidya walkmixes in significantly fewer steps than the logarithmic-barrier based Dikinwalk studied in past work. For a polytope in $\mathbb{R}^d$ defined by $n >d$linear constraints, we show that the mixing time from a warm start is boundedas $\mathcal{O}(n^{0.5}d^{1.5})$, compared to the $\mathcal{O}(nd)$ mixing timebound for the Dikin walk. The cost of each step of the Vaidya walk is of thesame order as the Dikin walk, and at most twice as large in terms of constantpre-factors. For the John walk, we prove an$\mathcal{O}(d^{2.5}\cdot\log^4(n/d))$ bound on its mixing time and conjecturethat an improved variant of it could achieve a mixing time of$\mathcal{O}(d^2\cdot\text{polylog}(n/d))$. Additionally, we propose variantsof the Vaidya and John walks that mix in polynomial time from a deterministicstarting point. The speed-up of the Vaidya walk over the Dikin walk areillustrated in numerical examples.

Fast MCMC sampling algorithms on polytopes