🔢 mathematics

Information-theoretic coordinate subset and partition selection of multivariate Markov chains via submodular optimization

This paper addresses the problem of optimally selecting coordinate subsets and partitions for multivariate Markov chains to minimize information loss under cardinality constraints by leveraging (k-)submodular and (k-)supermodular structures to develop efficient greedy algorithms with theoretical guarantees.

Original authors: Zheyuan Lai, Michael C. H. Choi

Published 2026-03-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zheyuan Lai, Michael C. H. Choi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the conductor of a massive, chaotic orchestra. This orchestra represents a multivariate Markov chain—a complex system where hundreds of musicians (coordinates) are playing together, but their notes depend on what the others played just a moment ago. The sheet music for this system is the transition matrix, which dictates how the music evolves over time.

Now, imagine you want to understand this symphony, but the full score is too complicated to read. You have two main goals:

Simplify: You want to pick a small group of musicians (a subset) whose combined playing captures the most "randomness" or "surprise" (entropy) of the whole orchestra.
Organize: You want to split the orchestra into smaller sections (a partition) that play independently of each other, so you can understand the whole by understanding the parts.

The problem is that there are billions of ways to pick these groups or split the sections. Checking every single possibility is impossible. This is where the paper comes in.

The Core Idea: The "Diminishing Returns" Rule

The authors discovered that these musical problems follow a mathematical rule called Submodularity.

Think of Submodularity like adding toppings to a pizza:

The first slice of pepperoni you add to a plain cheese pizza makes a huge difference. It's delicious!
The second slice is still good, but not as exciting as the first.
By the time you add the tenth slice, you're just adding more pepperoni; the extra value is tiny.

This is the "Diminishing Returns" principle. In the context of the orchestra:

Adding the first "random" musician to your small group adds a lot of new information.
Adding a second musician adds some new info, but less than the first.
Adding a tenth musician adds very little new info because you already have the main players.

Because this rule holds true for these complex Markov chains, the authors realized they don't need to check every possible combination. They can use a Greedy Algorithm.

The Solution: The "Greedy" Chef

A Greedy Algorithm is like a chef who is very hungry and wants to make the best salad possible, but can only pick 5 ingredients.

Step 1: The chef tastes every single vegetable in the market and picks the one that tastes the best.
Step 2: Now, holding that first vegetable, the chef tastes every remaining vegetable to see which one tastes best combined with the first. They pick that one.
Step 3: They repeat this until they have 5 ingredients.

The chef never looks back to see if they should have swapped the first ingredient for something else. They just keep picking the "best next thing."

Usually, this greedy approach is risky. But because of the Diminishing Returns (Submodularity) rule the authors proved, this greedy approach is mathematically guaranteed to get you a result that is very close to the absolute best possible salad (or in this case, the best subset of coordinates).

The New Twist: The "Distorted" Greedy Chef

Sometimes, the "best next thing" isn't actually the best choice because of a hidden cost. Imagine the chef has to pay for the vegetables. The greedy chef might pick the tastiest vegetable, but if it costs $100, it's a bad deal.

The authors developed a "Distorted Greedy Algorithm."

This is like a chef who looks at the taste and the price, but they also have a special "magic discount" that changes as they shop.
Early in the shopping trip, the discount is huge, encouraging them to pick the absolute best ingredients.
Later, the discount shrinks, forcing them to be more careful about the remaining choices.

This "distortion" helps the algorithm avoid getting stuck with a bad combination early on, ensuring the final result is even better than the standard greedy approach. They also extended this to k-submodularity, which is like the chef trying to organize the salad into 3 different bowls (groups) simultaneously, rather than just one pile.

Real-World Application: The "Curie-Weiss" Orchestra

To prove their theory, the authors tested their algorithms on two famous mathematical models:

The Curie-Weiss Model: Think of this as a crowd of people in a room. If one person stands up, others are likely to stand up too (like a magnet). The authors used their algorithm to find which specific people (coordinates) were the most influential in keeping the crowd chaotic or calm.
The Bernoulli-Laplace Model: Imagine a bag of red and blue marbles being shuffled. The algorithm figured out which specific marbles were the most "independent" of the others.

The Result:
In one experiment, they found that if they separated one specific "troublemaker" coordinate (a specific person in the crowd or a specific marble) from the rest, the remaining group settled down (reached equilibrium) much faster. By treating the troublemaker separately and the rest as a group, they could simulate the system's behavior much more efficiently.

Why This Matters

In the real world, we deal with massive amounts of data (like stock markets, weather patterns, or social networks) that behave like these Markov chains.

Before: To understand the system, you had to crunch numbers for the entire massive dataset, which is slow and expensive.
Now: Using these "Submodular Optimization" tools, we can quickly identify the most important few variables or the best way to group them. This allows us to build faster, more efficient computer simulations (MCMC samplers) that give us accurate answers without needing to process the entire universe of data.

In short: The paper teaches us how to use a smart, step-by-step "greedy" strategy to cut through the noise of complex systems, finding the most important pieces of the puzzle with a mathematical guarantee that we won't miss the big picture.

1. Problem Statement

The paper addresses the challenge of model reduction and coordinate selection for finite ergodic multivariate Markov chains. Given a $d$ -dimensional Markov chain with transition matrix $P$ and stationary distribution $\pi$ , the authors seek to:

Select a subset of coordinates $S \subseteq \{1, \dots, d\}$ (with $|S| \leq m$ ) such that the projected transition matrix $P(S)$ optimizes specific information-theoretic criteria.
Partition the coordinates into $k$ groups to approximate the original chain with a factorized model that minimizes information loss.

The optimization targets include:

Maximizing Entropy Rate: Identifying the "most random" subset of coordinates.
Minimizing Distance to Stationarity: Finding subsets whose dynamics are closest to equilibrium.
Minimizing Distance to Independence/Factorizability: Identifying subsets or partitions where the chain behaves most like independent components or a product of simpler chains.
Minimizing Distance to Factorizability: Finding partitions that best approximate the complex chain with a factorized structure.

The core difficulty lies in the combinatorial nature of selecting subsets or partitions from a high-dimensional space, which is generally NP-hard.

2. Methodology

The authors leverage Submodular Optimization to develop efficient, greedy-based algorithms with theoretical performance guarantees.

A. Structural Analysis

The paper establishes that various information-theoretic functionals exhibit submodular (diminishing returns) or supermodular (increasing returns) structures:

Entropy Rate $H(P(S))$ : Submodular but generally non-monotonic.
Distance to Factorizability/Independence: Exhibits submodular or supermodular properties depending on whether the set or its complement is considered.
Distance to Stationarity: Monotonically non-decreasing and supermodular under product-form stationary distributions.

B. Algorithmic Framework

Since standard greedy algorithms only guarantee $(1 - e^{-1})$ -approximation for monotone submodular maximization, the authors employ advanced techniques to handle non-monotone and constrained objectives:

Distorted Greedy Algorithm:
- To handle non-monotone submodular functions (e.g., maximizing entropy rate), the authors transform the objective $f(S)$ into a difference of a monotone submodular function $g(S)$ and a modular function $c(S)$ : $f(S) = g(S) - c(S)$ .
- They utilize a distorted greedy algorithm (Algorithm 2) which maximizes a weighted difference, providing a theoretical lower bound of $(1 - e^{-1})g(\text{OPT}) - c(\text{OPT})$ .
Generalized Distorted Greedy for $k$ -Submodularity:
- For partition selection problems, the authors generalize the concept to $k$ -submodularity, where the decision variable is a partition of coordinates into $k$ groups.
- They introduce a Generalized Distorted Greedy Algorithm (Algorithm 3) that handles $k$ -submodular objectives under cardinality constraints.
- They prove that specific orthant submodular functions arising in Markov chain theory can be transformed into monotone $k$ -submodular functions, allowing the application of Algorithm 3 with similar theoretical guarantees.
Batch Greedy Algorithm:
- For maximizing distance to stationarity (a supermodular minimization problem), they utilize a batch greedy approach (Algorithm 4) which offers guarantees based on the supermodularity and submodularity ratios of the objective function.

3. Key Contributions

Identification of New Submodular Structures: The paper proves that natural set functionals in Markov chain theory (entropy rate, distances to independence, stationarity, and factorizability) possess submodular or supermodular structures. This extends previous work (e.g., [2]) by focusing on subset/partition selection rather than just matrix approximation.
Algorithmic Innovations:
- Development of a Generalized Distorted Greedy Algorithm for $k$ -submodular maximization under cardinality constraints.
- Application of the Distorted Greedy technique to transform non-monotone Markov chain objectives into solvable forms with theoretical approximation bounds.
Theoretical Guarantees: The paper provides rigorous lower bounds (typically $(1 - e^{-1})$ ) for the proposed algorithms, ensuring that the selected subsets or partitions are near-optimal.
Application to MCMC: The authors demonstrate how these selection algorithms can be used to design accelerated MCMC samplers. By identifying coordinates that are far from equilibrium, they propose a heuristic to run independent samplers on separated components, improving mixing rates.

4. Numerical Results

The authors validated their theory on two standard models from statistical physics:

Bernoulli–Laplace Level Model: A model involving particle swapping.
Curie–Weiss Model: A mean-field Ising model with Glauber dynamics.

Key Findings from Experiments:

Entropy Rate: The distorted greedy algorithm consistently outperformed the standard heuristic greedy algorithm in selecting subsets with higher entropy rates, particularly for intermediate cardinality constraints.
Distance to Independence: The algorithms successfully identified subsets that minimized the distance to independence, effectively isolating weakly coupled coordinates.
MCMC Improvement: In a specific experiment on the Curie–Weiss model ( $d=8$ ), the algorithm identified coordinate 4 as the one furthest from equilibrium. Separating this coordinate and running a factorized sampler ( $P(-4) \otimes P(4)$ ) resulted in a ~14% improvement in total variation distance convergence compared to the original chain.
Partitioning: The generalized $k$ -submodular algorithm effectively partitioned coordinates into groups that maximized the entropy of the resulting product chain.

5. Significance

Bridging Theory and Practice: The paper connects abstract submodular optimization theory with practical problems in stochastic processes and statistical physics.
Scalability: Unlike spectral methods (which require eigen-decomposition and are computationally expensive for high dimensions), the proposed combinatorial approach relies only on transition probabilities, making it scalable to higher dimensions.
MCMC Acceleration: The work provides a principled, data-driven method for designing better MCMC samplers by identifying optimal coordinate subsets or partitions, potentially reducing the computational cost of sampling complex multivariate distributions.
Generalizability: The generalized distorted greedy algorithm for $k$ -submodularity is presented as a tool of independent interest, applicable beyond Markov chains to other combinatorial optimization problems involving partitions.

In summary, this paper provides a robust theoretical framework and efficient algorithms for reducing the complexity of multivariate Markov chains, offering both mathematical guarantees and practical improvements for sampling and model analysis.