Source-linked AI summary
Spectral partitioning for $k$-block averaging kernels of finite Markov chains
Michael C. H. Choi, Youjia Wang
TL;DR
The paper addresses how to choose state-space partitions for averaging kernels without exhaustive partition search. It uses bottom spectral modes with weighted k-means rounding, and reports improved convergence and statistical estimation across controlled graph, Ising, and Bayesian variable-selection experiments, while noting scope and computational limitations.
Problem
Selecting partitions that make tractable averaging updates improve finite reversible Markov-chain convergence is computationally difficult because exhaustive search over state-space partitions is impractical.
Method
The method rounds bottom nonconstant eigenfunctions of P^2, or algebraically smallest eigenfunctions of P for additive mixtures, using weighted k-means to construct block partitions.
Results
The experiments report substantially improved convergence when averaging updates are available and connect this improvement to statistical estimation in an exact Bayesian variable-selection benchmark.
Takeaways & Limitations
The framework favors partitions with large cross-block flow rather than the low-flow persistent clusters targeted by classical normalized spectral clustering, and supports multiple averaging objectives and horizons.
Takeaways & Limitations
The first two experiments use only 40 and 256 states, unconstrained objectives may produce unbalanced blocks, and total-variation plots compare kernel iterations rather than equal computational budgets.
Abstract
from arXiv · showhide
We develop spectral algorithms for selecting state-space partitions that define averaging kernels for finite, ergodic and reversible Markov chains. For a partition $\mathcal O$, the Gibbs kernel $G_{\mathcal O}$ resamples within the current block from the stationary conditional distribution; when this update is tractable, composing or mixing it with a baseline kernel $P$ can accelerate convergence. We select $\mathcal O$ by rounding the bottom nonconstant eigenfunctions of $P^2$, or the algebraically smallest eigenfunctions of $P$ for additive mixtures, using weighted $k$-means. For $F(\mathcal O)=\|G_{\mathcal O}P-Π\|_{F,π}^2$, we derive exact trace and normalized-cut representations and show that $F$ equals the Pearson $χ^2$-mutual information between the initial block label and the state after one transition, giving this matrix objective a natural probabilistic interpretation. In the two-block case, a threshold sweep exactly solves the associated one-dimensional weighted two-means rounding problem. For general $k \geq 2$, weighted $k$-means rounds the bottom $(k-1)$-dimensional embedding, after which candidates are rescored by $F$; the rounding distortion is a distance between subspaces that yields spectral approximation bounds. We extend the framework to additive mixtures, finite-horizon objectives, and discounted infinite-horizon objectives. In contrast to classical normalized spectral clustering, which uses top nonconstant modes to find low-flow persistent clusters, our method uses bottom modes to favor large normalized cross-block flow and rapid loss of block-label information. Experiments on a controlled-spectrum graph, a mean-field Ising model, and Bayesian variable selection show notable per-iteration improvements in convergence and statistical estimation.
1 Introduction
The paper develops spectral methods for choosing state-space partitions that make tractable Gibbs averaging updates useful for accelerating finite reversible Markov chains. It replaces exhaustive partition search with bottom-eigenfunction embeddings and rounding, extending the approach across kernels, objectives, and experiments.
- Motivation: A partition defines a Gibbs kernel that resamples within the current block from the stationary conditional distribution, enabling composed or additive averaged chains when these updates are tractable.The practical problem is selecting such a partition without searching over all state-space partitions.
- Spectral construction: The one-step Frobenius objective is relaxed using bottom nonconstant eigenfunctions of P^2, then rounded to a block-constant subspace; additive mixtures instead use algebraically smallest eigenfunctions of P.The construction uses eigenfunctions not only to diagnose convergence but also to build a new simulable kernel.
- Relation to classical clustering: Unlike classical normalized spectral clustering, which seeks low-boundary persistent clusters using largest nonconstant modes of P^2, this method uses smallest eigenvalues to seek large cross-block flow.The paper describes the two approaches as having reversed objectives and guarantees.
- Two-block rounding: For two blocks, thresholding a bottom eigenfunction of P^2 exactly solves the associated one-dimensional weighted two-means problem.The resulting threshold partition is optimal for that weighted rounding objective.
- Multiway rounding: For k ≥ 2 blocks, π-weighted k-means rounds the embedding formed by the bottom k −1 eigenfunctions of P^2, with distortion equal to a projection distance that transfers to the original objective through spectral-sandwich bounds.The distortion is equivalently a sum of squared principal-angle sines.
- Extensions and experiments: The framework extends to additive mixtures and finite- and discounted infinite-horizon criteria, whose spectral choices can differ and whose experiments show substantially improved convergence when averaging updates are available.The experiments cover a controlled-spectrum graph, a mean-field Ising model, and Bayesian variable selection, with the latter connecting improvement to statistical estimation and balanced partitions.
2 Preliminaries
The paper formulates Gibbs kernels as projections associated with partitions of a reversible finite Markov chain, then characterizes the Frobenius objective through spectral, cut, and information-theoretic representations.
- 2.2 Gibbs kernels associated with partitions: A partition O induces a Gibbs kernel G_O that replaces each function by its π-mean within the current block.G_O is the orthogonal projection onto functions constant on every block.
- 2.2 Gibbs kernels associated with partitions: The centered block projection Q_O has range equal to the (k−1)-dimensional subspace of centered functions constant on every block.
- 2.3 The weighted Frobenius objective and its information-theoretic interpretation: Minimizing F is equivalent to maximizing the multiway normalized-cut objective of the two-step chain P^2.
- 2.3 The weighted Frobenius objective and its information-theoretic interpretation: F(O) equals the residual Pearson chi-square information that the state after one transition retains about the initial block label.It vanishes exactly when the initial block label and next state are independent.
- 2.4 Spectral relaxation: For fixed k, the relaxed spectral problem ranges over all centered (k−1)-dimensional subspaces, whereas partitions provide only feasible block-constant subspaces.
- 2.5 Contrast with classical spectral clustering: Unlike classical spectral clustering, the method uses the smallest eigenvalues of P^2 to seek large two-step normalized boundaries rather than small boundaries.
3 The two-block case
In the two-block case, the spectral relaxation produces a one-dimensional eigenfunction, and thresholding its ordered values solves the associated weighted two-means rounding problem while candidates are evaluated by the original objective.
- 3 The two-block case: The two-block problem reduces the rounding step to one-dimensional weighted two-means for the values of a normalized bottom eigenfunction ϕ of P^2.
- Threshold rounding: A threshold set assigns states below a threshold to one block and states above it to the complement, with ties assignable either way.
- Threshold rounding: There is always a minimizer of the weighted two-means error δ(S) that is a threshold set of ϕ.
- The spectral sweep algorithm: The algorithm computes ϕ, sorts states, forms sweep sets, evaluates F for each candidate, and returns the best-scoring set.
- The spectral sweep algorithm: Sorting the states by ϕ enumerates all one-dimensional Voronoi splits, so the sweep attains the optimal threshold-rounding error.
- The spectral sweep algorithm: A non-threshold cut may have a smaller F, so the sweep provides a rounding guarantee rather than an unrestricted optimum of the original objective.
- Guarantees: When n=2, the sweep is exact because only one nontrivial two-block partition exists up to complementation.
- Contrast with the classical Cheeger sweep: The method differs from the classical Cheeger sweep: it uses a bottom eigenfunction of P^2 to maximize normalized cut, not a low-frequency mode to minimize boundary.
4 The k-block case
The k-block method rounds the bottom nonconstant spectral subspace into a feasible block-constant subspace using π-weighted k-means, then rescored candidates are evaluated by the original objective F.
- Spectral embedding: Only k−1 nonconstant eigenfunctions are rounded because a k-block Gibbs kernel already contains the constant direction.The embedding uses the eigenfunctions associated with the k−1 smallest eigenvalues of P^2.
- Spectral rounding: The relaxed spectral subspace is replaced by a feasible centered block-constant subspace indexed by partitions.This is the relaxation–discretization step underlying spectral rounding.
- Weighted k-means: Minimizing δ(O) is exactly weighted k-means on the raw embedding Φ(x), with state weights π(x).The distortion is also the expected squared quantization error after replacing each embedded point by its assigned centroid.
- Geometric interpretation: The spectral rounding error δ(O) is the squared chordal distance between the relaxed spectral subspace and the partition’s block-constant subspace.Equivalently, it is one half of the squared Hilbert–Schmidt distance between their projection operators and can be expressed through principal angles.
- Algorithms: The two-block case is solved exactly by thresholding the one-dimensional spectral points, while general k uses approximate weighted k-means followed by candidate rescoring with F.The threshold property follows from the interval structure of one-dimensional weighted k-means.
- Guarantees: Theorem 4.2 transfers rounding error to F through eigengap and spectral-width bounds, but δ(O) is a geometric surrogate rather than an actual F-suboptimality gap.When the spectral gap is zero, the bottom spectral subspace is exactly block-constant for some partition and both objectives attain the relaxed optimum.
- Relation to classical clustering: Unlike classical normalized spectral clustering, this method uses bottom modes of P^2 to favor large cross-block flow rather than persistent low-flow clusters.The bottom eigenfunctions correspond to directions most strongly suppressed by P.
5 Additive mixtures and a P-spectral multiway sweep
For additive mixtures, the partition-dependent relaxation uses the algebraically smallest eigenfunctions of P, and weighted k-means produces candidates that are rescored by the original mixture objective H.
- Spectral relaxation: The additive-mixture relaxation uses bottom eigenfunctions of P rather than bottom eigenfunctions of P^2.This preserves eigenvalue signs and matters when P has negative eigenvalues.
- Objective identity: For fixed k, minimizing the mixture objective H is equivalent to maximizing the one-step chain’s multiway normalized cut.The partition-dependent terms in the trace identity establish this equivalence.
- Rounding: The P-spectral rounding error δP is both π-weighted k-means distortion and squared chordal distance between the relaxed spectral and block-constant subspaces.The embedding uses the selected bottom (k−1)-dimensional spectral subspace of P.
- Algorithm: Algorithm 3 computes the bottom spectral embedding, runs weighted k-means from several initializations, and retains candidates with k nonempty blocks.The final candidate is selected by evaluating H rather than relying only on δP.
- Guarantees: Theorem 5.2 and Corollary 5.3 provide spectral-sandwich and algorithmic guarantees linking δP to the mixture objective H.The bounds use the eigengap and spectral width of P and accommodate a ρ-approximation to weighted k-means.
- Interpretation: Unlike the P^2 objective, H is sensitive to negative modes and seeks large one-step cross-block flow.If P is positive semidefinite, the bottom spectral subspaces of P and P^2 agree up to choices within tied eigenspaces.
6 Multi-horizon distance to stationarity
The multi-horizon objectives aggregate residual block-label information across lags while retaining the same relaxed bottom spectral subspace, with time-dependent penalties and candidate rescoring selecting the partition.
- Motivation: The one-step distance need not identify the best partition over a longer time scale, motivating finite and discounted infinite-horizon objectives.These objectives aggregate distance to stationarity as it decays over time.
- Probabilistic interpretation: The lag-t objective measures the Pearson chi-square information about the initial block label that remains after t transitions.Finite- and discounted-horizon objectives aggregate this residual block information over multiple lags.
- Scope distinction: The multi-horizon objective is not the t-step convergence of repeatedly applying the averaged kernel because G_OP^t is generally different from (G_OP)^t.The present formulation retains a linear trace representation, whereas repeated averaging is nonlinear in the partition projection.
- Spectral structure: Positive multi-horizon weights preserve the same bottom spectral subspace of P^2 while changing the penalties assigned to different modes.With a strict spectral gap, the subspace and raw embeddings are uniquely determined; ties can make the selected subspace nonunique.
- Mode weighting: Discounting strongly penalizes leakage into modes with |ξ| approximately 1, including negative eigenvalues near −1 because they generate persistent period-two oscillations.Small-|ξ| modes are rapidly suppressed and receive nearly unchanged discounted weighting.
- Algorithm: The multi-horizon sweep reuses the P^2 embedding and weighted k-means rounding, then rescales candidates using the selected finite- or infinite-horizon objective.For k=2, the exact scalar threshold sweep can be used for the first two steps, but final rescoring remains essential.
- Guarantees: Theorem 6.2 and Corollary 6.3 transfer multi-horizon rounding error to the exact objective through spectral-sandwich and approximation guarantees.The guarantee applies to the best generated candidate under the weighted k-means approximation condition.
7 Numerical experiments
The experiments compare spectral-sweep procedures across controlled-spectrum, Ising, and Bayesian variable-selection settings, showing objective-specific partition choices and improvements while highlighting diagnostic and scope limits.
- Experimental design: All multiway procedures use spectral embeddings and weighted k-means to generate candidates, then rank them with the corresponding original Markov-chain objective.The rounding surrogate and final selection objective can differ across one-step, multi-horizon, and additive-mixture procedures.
- Controlled-spectrum graph: In the controlled-spectrum chain, signed-spectrum effects make the additive-mixture partition differ from the P^2-based outputs, while Algorithms 2 and 4 select the same four-block partition.F treats positive and negative eigenvalues symmetrically through P^2, whereas H retains their signs through P.
- Controlled-spectrum graph: Across 48 phase-diagram grid points, selected partitions can change substantially, and the largest observed F–H disagreement is 0.725.These results are restart-dependent algorithmic observations rather than global discrete optima or phase boundaries.
- Controlled-spectrum graph: At the most horizon-sensitive tested point, the two selected partitions disagree on stationary mass 0.550, and lag-10 values are 0.3002 and 0.05818 for the compared F objectives.The repeated-kernel diagnostic also improves from 1.10 × 10^-6 to 3.61 × 10^-8, but that agreement is empirical rather than implied by the multi-horizon objective.
- Exact mean-field Ising: In the exact Ising experiment, each objective-specific sweep beats both deterministic baselines and the empirical mean random baseline on its own objective at every tested parameter pair.At (β, h) = (1.5, 0), reductions relative to magnetization are 69.2% for F, 3.63% for H, and 86.6% for F∞.
- Ising and Bayesian variable selection: The learned Ising partitions are highly imbalanced, with one block holding about 0.96 stationary mass, whereas balanced outputs improve all four Bayesian variable-selection targets.At T = 5000, the balanced multi-horizon kernel reduces ePIP, epair, esize, and eBMA by factors 10.4, 8.4, 2.5, and 9.5 relative to P.