Information-theoretic minimax and submodular optimization algorithms for multivariate Markov chains

Zheyuan Lai, Michael C.H. Choi · 2025

Read Information-theoretic minimax and submodular optimization algorithms for multivariate Markov chains by Zheyuan Lai, Michael C.H. Choi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-00769.txt.

Description

Zheyuan Lai and Michael Choi study how to approximate a family of Markov chains with simpler models that split into independent parts. The cost of an approximation is measured by information loss, and they want the worst case loss over the whole family to be as small as possible.

Duality results and geometric identities turn that minimax problem into a concave maximization over a simplex, which they read as a game whose mixed strategy equilibrium always exists. A projected subgradient method solves it with guarantees. They also link the choice of split to submodular optimization and test the algorithms on Curie-Weiss and Bernoulli-Laplace chains, where the best approximations turn out to have sparse structure.

Catalog record

CREATORZheyuan Lai, Michael C.H. Choi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE79 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-00769

Browse the full library · About the Tower of Babel