analiza aiqbench
This research introduces spectral algorithms to optimize state-space partitions for accelerating convergence in finite Markov chains, specifically targeting the bottom eigenfunctions rather than traditional top modes. By linking matrix objectives to probabilistic interpretations like Pearson $\chi^2$-mutual information, the method offers measurable improvements in statistical estimation and convergence speed across models such as mean-field Ising systems.
Spectral partitioning for $k$-block averaging kernels of finite Markov chains
arXiv:2608.21466v1 Announce Type: cross Abstract: 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-\Pi\|_{F,\pi}^2$, we derive exact trace and normalized-cut representations and show that $F$ equals the Pearson $\chi^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.
Abstract: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-\Pi\|_{F,\pi}^2$, we derive exact trace and normalized-cut representations and show that $F$ equals the Pearson $\chi^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.
Machine Learning (stat.ML); Information Theory (cs.IT); Machine Learning (cs.LG); Optimization and Control (math.OC); Probability (math.PR); Computation (stat.CO)
arXiv:2608.21466 [stat.ML]
(or arXiv:2608.21466v1 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2608.21466 arXiv-issued DOI via DataCite (pending registration)
Text integral sub licența deschisă a publicației · 269 cuvinte
Subiecte conexe
Discrete MeanFlow: One-Step Generation via Conditional Transition Kernels
arXiv · 15 oct. 2026
A Practical Guide to GPU-Initiated Communication for Molecular Dynamics at Scale
NVIDIA · 9 iul. 2026
Enabling DeepSeek-V4-Flash Training on AMD Instinct MI355X GPUs with Primus
AMD · 3 sept. 2026
Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains
arXiv · 2 oct. 2026