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
| CREATOR | Zheyuan Lai, Michael C.H. Choi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-00769