📊 statistics

Folded Transport MCMC: Certifiable Quotient Posterior Computation for Symmetric Bayesian Models

This paper introduces Folded Transport MCMC (FolT-MCMC), a novel method that performs Bayesian inference directly on the quotient posterior of symmetric models by constructing a symmetrized normalizing flow proposal, thereby overcoming label-switching multimodality to achieve significantly improved and certifiable convergence across various dimensions and real-world applications.

Original authors: Jun Hu

Published 2026-06-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jun Hu

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 trying to find the best spot to set up a campsite in a vast, foggy mountain range. You have a map (your statistical model) that tells you where the "good" spots are, but the map has a strange quirk: it is perfectly symmetrical.

If you find a great spot at the top of a hill, there are actually 24 identical spots scattered around the mountain, just rotated or flipped. To a computer trying to explore this map, these 24 spots look like 24 different destinations, even though they are all the same place. This is called Label Switching.

The computer gets confused. It spends all its time hopping back and forth between these identical spots, thinking it's exploring new territory, when it's actually just running in circles. Because of this confusion, the computer cannot tell you how confident it is in its findings. It's like trying to measure how fast a car is going while the speedometer is spinning wildly.

The Problem: The "Redundant" Mountain

In the world of Bayesian statistics (a way of updating beliefs with data), this happens often in things like:

Mixing paints: If you have three buckets of paint (Red, Blue, Yellow), the computer doesn't know which bucket is which. It sees "Bucket 1 is Red" as different from "Bucket 1 is Blue," even if the final mix is the same.
Building vibrations: When analyzing how a skyscraper sways in a typhoon, there might be three similar "modes" of swaying. The computer can't tell which is which, so it treats them as 6 different possibilities (3! = 6).

This creates a "multimodal" problem where the computer gets stuck in a loop, and its confidence checks (certificates) come back empty or useless.

The Solution: Folded Transport MCMC (FolT-MCMC)

The authors introduce a clever trick called FolT-MCMC. Think of it as folding the map.

Instead of letting the computer wander the whole mountain with its 24 identical peaks, they take the map and fold it up so that all 24 identical peaks are stacked on top of each other, creating one single peak.

The Fold: They define a "Fundamental Domain." Imagine drawing a line down the middle of the mountain range. They say, "We will only look at the left side." If the computer tries to jump to the right side, they simply reflect it back to the left.
The Transport: They use a smart, learnable tool (a "Normalizing Flow") that acts like a guided tour guide. This guide learns the shape of that single, folded peak perfectly.
The Result: Now, the computer only has to explore one spot instead of 24. It stops hopping back and forth. It moves smoothly and efficiently.

The "Certificate": Proving You're Not Lost

The most exciting part of this paper isn't just that the computer moves faster; it's that the computer can now prove it's doing a good job.

In the old method (Unfolded), the computer would say, "I'm 99% sure I'm lost," because the symmetrical confusion made its confidence math break down. The "certificate" of its performance was vacuous (meaningless).

With the new folded method, the computer can say, "I am 90% sure I am in the right place."

The Analogy: Imagine a security guard checking if a building is safe.
- Old Way: The guard tries to check 24 identical rooms at once, gets confused, and says, "I can't guarantee anything."
- New Way: The guard folds the building into one room, checks it thoroughly, and says, "I certify this room is safe."

Real-World Tests

The authors tested this on two main things:

Synthetic Math Problems: They created fake data with 2, 6, and even 24 identical modes. In high dimensions (up to 20 variables), the old method's confidence dropped to near zero. The new method kept its confidence high (around 90%), regardless of how complex the problem got.
Real Typhoon Data: They analyzed accelerometer data from a supertall building during Typhoon Mangkhut. The building had three very similar vibration modes that were hard to tell apart.
- Old Method: Failed to give a useful confidence score.
- New Method: Successfully identified the vibration frequencies and provided a valid, non-empty confidence score, proving the method worked even on messy, real-world data.

The Catch (Design Principle)

The paper notes one important rule for this "folding" to work: You must fold in a valley, not on a mountain ridge.
If you try to fold the map right through the middle of a high-density area (where the data is most likely to be), you create a sharp edge that confuses the computer. You need to fold along the "valleys" between the peaks, where there is very little data. When they did this correctly, the method worked beautifully.

Summary

FolT-MCMC is a new way to solve statistical problems where the answer has "symmetry" (multiple identical versions). By mathematically folding the problem space to remove the duplicates, it allows computers to explore the solution much more efficiently and, crucially, allows them to certify that their results are trustworthy. It turns a confusing, spinning speedometer into a clear, reliable gauge.

Technical Summary: Folded Transport MCMC (FolT-MCMC)

1. Problem Statement

Bayesian models exhibiting finite exchangeability—such as mixture models with exchangeable components or structural identification problems with closely-spaced modes—define posterior distributions invariant under a group of label permutations ( $G$ ). This symmetry induces $m!$ (or generally $|G|$ ) equivalent posterior modes, a phenomenon known as label switching.

Standard Markov Chain Monte Carlo (MCMC) approaches operating on the full labeled parameter space face two critical issues:

Redundant Multimodality: The chain must traverse $|G|$ symmetric modes, leading to poor mixing and unreliable convergence diagnostics.
Vacuous Certification: Convergence certificates based on spectral gap bounds (e.g., via the LCNF framework) become vacuous. The log-density ratio oscillation is inflated by the "cross-mode gap" between separated symmetric modes, causing certified lower bounds on the spectral gap to collapse to near zero, even if the chain mixes well within a single mode.

While post-hoc relabeling methods exist to recover identifiable parameters, they do not address the underlying mixing difficulties of the chain or provide certified convergence guarantees for the sampling process itself.

2. Methodology: Folded Transport MCMC

The paper introduces Folded Transport MCMC (FolT-MCMC), a framework that performs inference directly on the quotient posterior (the distribution over equivalence classes) rather than the full labeled space.

Core Mechanism:

Quotient Target: The method defines a fundamental domain $D$ (e.g., a sorted chamber for permutations or a half-space for reflections) and a folded target density $\pi_F(z) = |G| \cdot \pi(z)$ for $z \in D$ . This eliminates symmetric multimodality, leaving a single representative mode per orbit.
Quotient Proposal: An independence sampler is constructed on $D$ . The proposal density $q_F$ is formed by symmetrizing a learned normalizing flow $T_F$ (trained on folded samples) over the group orbits:
$q_F(z) = \sum_{g \in G} q_{T_F}(g \cdot z)$
This ensures the proposal respects the symmetry while being trained on the single-mode structure of the quotient space.
Sampling: The algorithm runs Independence Metropolis–Hastings (IMH) on the fundamental domain $D$ using the quotient proposal.

Theoretical Framework:
FolT-MCMC integrates with the LCNF (Local Concentration and Normalizing Flow) certification framework. The paper proves that the LCNF oscillation-based certification transfers to the quotient metric:

Quotient Metric: A metric $d_G(\theta, \theta') = \min_{g \in G} \|\theta - g \cdot \theta'\|$ is used to handle covering arguments near the fold boundary.
Stabiliser-Corrected Bounds: The framework incorporates a stabiliser-corrected ball-mass bound to account for points on the fold boundary where the group action is not free.
Certification: The method computes a quantile-core certified lower bound ( $QC_\gamma$ ) for the spectral gap. This bound is computable from finite samples and network parameters, providing a rigorous diagnostic for density-ratio stability on the high-probability posterior core.

3. Key Contributions

Quotient Posterior Framework: The authors define the folded target $\pi_F$ and prove an exact Highest Posterior Density (HPD) identity ( $K_\alpha^F = K_\alpha \cap D$ ). They construct the quotient proposal $q_F$ and show that the density floor improves by a factor of $|G|$ , significantly aiding coverage.
Quotient-Space Certification: The paper establishes that the LCNF empirical oscillation theorem transfers to the quotient setting. Key theoretical results include:
- The covering radius $\varepsilon^*_F$ in the quotient space is less than or equal to the unfolded radius $\varepsilon^*_U$ .
- The certified lower bound improves whenever the unfolded flow exhibits "cross-mode proposal deficiency" (i.e., fails to cover all symmetric modes simultaneously).
Empirical Validation: Extensive experiments demonstrate that FolT-MCMC yields non-vacuous certificates where unfolded methods fail.
- Gaussian Mixtures: On dimensions $d=2$ to $20$, the folded certificate remains stable ( $QC_\gamma \in [0.90, 0.94]$ ), while the unfolded certificate collapses (e.g., to $0.016$ at $d=20$ ).
- Label Switching: For mixtures with up to $24$ equivalent modes ( $m=4$ ), the folded certificate improves by a factor of $145\times$ compared to the unfolded baseline.
- Real-World Application: Applied to accelerometer data from a supertall building during Typhoon Mangkhut, FolT-MCMC produced a non-vacuous certificate for a closely-spaced three-mode identification problem where the unfolded certificate was vacuous.

4. Results and Performance

Dimension Independence: The folded certificate is empirically nearly dimension-free. In contrast, the unfolded certificate degrades rapidly with dimension due to the coupling architecture's difficulty in representing multi-modal structures in high dimensions.
Mode Count Sensitivity: The unfolded certificate is more sensitive to the number of symmetric modes ( $s = |G|$ ) than to the ambient dimension. Increasing the number of modes from 6 to 24 caused a $15\times$ degradation in the unfolded certificate, whereas doubling the dimension (with fixed modes) caused only a $2\times$ degradation.
Comparison with Baselines:
- vs. Unfolded IMH: FolT-MCMC achieves high acceptance rates and recovers true parameters, whereas unfolded chains often freeze or fail to explore the posterior.
- vs. Random Permutation Sampler (RPS): While RPS can recover correct point estimates via post-hoc permutation, it does not improve the underlying proposal quality (acceptance rates remain low) and lacks a compatible certification framework. FolT-MCMC provides a tight, non-vacuous certificate that matches empirical effective sample sizes (ESS).
- vs. Post-hoc Sorting: Sorting samples from a frozen chain yields correct point estimates but provides no convergence guarantee. FolT-MCMC ensures the sampler actually explores the posterior.

5. Significance and Claims

The paper claims that FolT-MCMC resolves the fundamental barrier of certifiable convergence in symmetric Bayesian models.

Restoring Non-Vacuousness: The primary contribution is restoring the utility of oscillation-based certificates in the presence of symmetric multimodality. By folding the space, the method removes the cross-mode oscillation that renders unfolded certificates vacuous.
Distinction from Point Estimation: The authors emphasize that while post-hoc relabeling can recover correct point estimates under exact symmetry, it cannot certify that the sampler has converged or that credible intervals are valid. FolT-MCMC is necessary for certified posterior inference.
Design Principle: The paper identifies a critical design rule: the fold boundary must lie in a low-density valley between symmetric modes. If the boundary cuts through high-density regions (as in the "banana" diagnostic), the full oscillation bound may increase, though the quantile-core certificate often still improves.

Limitations Acknowledged:

The certificate applies to the high-probability core of the posterior, not the full support (tail behavior). Full-support spectral gap guarantees for transport MCMC with unbounded state spaces remain an open problem.
The method requires exact knowledge of the symmetry group $G$ and the fundamental domain $D$ .
The orbit sum in the proposal scales with $|G|$ , which may require approximation for very large groups (though manageable for $m \le 5$ ).

In summary, FolT-MCMC offers a geometric solution to label switching that transforms a redundant, hard-to-certify multimodal problem into a unimodal, certifiable inference task, bridging the gap between theoretical convergence guarantees and practical performance in symmetric Bayesian models.