Post

Conversation

[1/5] New paper: Optimising two-block averaging kernels to speed up Markov chains, joint work with Ryan Lim (NUS) doi.org/10.13140/RG.2. We study how to choose optimal two-block partitions to accelerate mixing of finite Markov chains under group-averaging transformations.

1:26 AM · Mar 11, 2026

6,184

Views

Post your reply

Michael Choi

@michaelchchoi

Mar 11

[2/5] The goal: turn the question “which cut should we use?” into a combinatorial optimisation problem in Markov chains.

[3/5] For the KL divergence, we show the problem reduces to the induced projection chain, giving explicit decay rates via its log-Sobolev constant. For the Frobenius distance, the optimisation is tied to a Cheeger-type functional that characterises good cuts.

[4/5] This leads to a structured combinatorial optimisation problem with difference-of-submodular decompositions. We develop practical approximation methods, including majorisation–minimisation and coordinate descent, as alternatives to exhaustive search.

[5/5] Numerical experiments on the Curie–Weiss model with Glauber dynamics show that well-chosen partitions can substantially improve convergence in total variation distance, and that the proposed approximation algorithms work well in practice. #MCMC #Submodularity

225

Trending now

What’s happening

Fashion & beauty · Trending

Chanel

Technology · Trending

#Python

Trending

#CVPR

Trending

#LearnInPublic

To view keyboard shortcuts, press question markView keyboard shortcuts

Post

Conversation

Trending now

What’s happening

To view keyboard shortcuts, press question mark
View keyboard shortcuts