Bregman projections and partition design for accelerating finite Markov chains
Abstract
We study Gibbs averaging of finite Markov chains with a prescribed stationary distribution π. Given a transition matrix P and the Gibbs kernel G induced by a state-space partition, we prove that GPG is an information projection for every admissible Bregman generator ϕ, with divergences defined using transition probabilities relative to π. A Pythagorean identity characterizes this projection and recovers the relative entropy and weighted Frobenius cases. A dual characterization identifies GPG as a kernel closest to stationarity among those with the same projection chain as P; for relative entropy, it maximizes the entropy rate. The identities also give monotonicity under partition coarsening. For every reversible ergodic baseline P, Gibbs averaging cannot increase the squared weighted Frobenius distance to stationarity at any positive integer time, and the inequality is strict unless P=GPG. The corresponding mixing time therefore cannot increase. To choose the partition, we identify the divergence of G from stationarity as the exact worst-case divergence of GPG over all π-stationary baselines P. This objective depends only on the block masses. We give an exact algorithm for concave block costs, including those arising from relative entropy and power generators ϕ(u)=up with 1<p<2, and a greedy approximation algorithm with a provable guarantee for p>2. For power generators ϕ(u)=up with p>1, the objective is proportional to Tsallis entropy of order 2−p: its minimization favors imbalanced block masses when 1<p<2 and balanced block masses when p>2, while all k-block partitions have the same objective value when p=2. A numerical experiment compares the resulting projected chains with a local Metropolis sampler on a multi-modal π.
Related
- Adaptive Bregman Alternating Projections for Feasible Gromov-Wasserstein Learning
- Accelerating Finite-Sum Bilevel Optimization with Fully First-Order Oracles
- Finite-dimensional normed spaces without small-norm hyperplane projections
- The Characteristics of Finite Projections of Certain Stochastic Processes and Queues
- Relax and Follow: L0-Path Computation with L0-Bregman Relaxations
BibTeX
@misc{choi2026bregman,
title = {{Bregman projections and partition design for accelerating finite Markov chains}},
author = {Michael C. H. Choi and Youjia Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39239},
eprint = {2610.39239},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39239},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Bregman projections and partition design for accelerating finite Markov chains
AU - Michael C. H. Choi
AU - Youjia Wang
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39239
UR - https://arxiv.org/abs/2610.39239
AB - We study Gibbs averaging of finite Markov chains with a prescribed stationary distribution π. Given a transition matrix P and the Gibbs kernel G induced by a state-space partition, we prove that GPG is an information projection for every admissible Bregman generator ϕ, with divergences defined using transition probabilities relative to π. A Pythagorean identity characterizes this projection and recovers the relative entropy and weighted Frobenius cases. A dual characterization identifies GPG as a kernel closest to stationarity among those with the same projection chain as P; for relative entropy, it maximizes the entropy rate. The identities also give monotonicity under partition coarsening. For every reversible ergodic baseline P, Gibbs averaging cannot increase the squared weighted Frobenius distance to stationarity at any positive integer time, and the inequality is strict unless P=GPG. The corresponding mixing time therefore cannot increase. To choose the partition, we identify the divergence of G from stationarity as the exact worst-case divergence of GPG over all π-stationary baselines P. This objective depends only on the block masses. We give an exact algorithm for concave block costs, including those arising from relative entropy and power generators ϕ(u)=u^p with 1<p<2, and a greedy approximation algorithm with a provable guarantee for p>2. For power generators ϕ(u)=u^p with p>1, the objective is proportional to Tsallis entropy of order 2−p: its minimization favors imbalanced block masses when 1<p<2 and balanced block masses when p>2, while all k-block partitions have the same objective value when p=2. A numerical experiment compares the resulting projected chains with a local Metropolis sampler on a multi-modal π.
ER -