Sharp and Adaptive Cluster Recovery in Slowly Mixing Gaussian Hidden Markov Models
Abstract
We study cluster recovery in a two-state Gaussian hidden Markov model in the slowly mixing regime, where the transition probability δ may vanish with the sample size. Temporal persistence creates long homogeneous segments and fundamentally changes the recovery problem relative to the i.i.d. Gaussian mixture benchmark. Rather than being purely adverse, label dependence provides exploitable structure: the statistical difficulty becomes concentrated near the rare transition points, giving rise to recovery regimes governed explicitly by their frequency δ. We first characterize, up to universal constants, the oracle Bayes risk for offline and online clustering. Both problems exhibit a nonstandard polynomial risk regime, but the sequential constraint induces an additional logarithmic localization cost, yielding a genuine online/offline gap. We also study fixed lag prediction with delayed label feedback and identify the effective memory horizon beyond which past labels no longer improve the optimal rate. When the signal direction is unknown and possibly high dimensional, the problem is governed by the effective signal strength rn2 = |θ|4/σ4/(|θ|2/σ2+d/n). We derive minimax lower bounds and construct fully adaptive polynomial time procedures attaining the sharp recovery rates. In particular, almost full recovery is possible precisely when rn2≫δ. If nδ≳log n, adaptation to both the signal θ and the transition probability δ incurs no first order loss, and the sharp exact recovery threshold (under the Hamming loss) is rn2 = 2log(nδ) (1+o(1)). Thus the effective complexity of the problem is governed by the number of latent transitions, rather than by the sample size itself.
Related
- Statistical properties for irregular observables in slowly mixing hyperbolic systems
- Stochastic Homogenization of Schrödinger Equations with Exponentially Mixing Sub-Gaussian Potentials
- Mixing profile for Glauber dynamics of the discrete Gaussian Free Field starting from super-harmonic functions
- Near linear mixing of random-cluster Glauber dynamics on random regular graphs
- More Expressive Feedforward Layers: Part I. Token-Adaptive Mixing of Activations
BibTeX
@misc{kaddouri2026sharp,
title = {{Sharp and Adaptive Cluster Recovery in Slowly Mixing Gaussian Hidden Markov Models}},
author = {Ibrahim Kaddouri and Mohamed Ndaoud},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09123},
eprint = {2610.09123},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09123},
}
RIS
TY - UNPB
TI - Sharp and Adaptive Cluster Recovery in Slowly Mixing Gaussian Hidden Markov Models
AU - Ibrahim Kaddouri
AU - Mohamed Ndaoud
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.09123
UR - https://arxiv.org/abs/2610.09123
AB - We study cluster recovery in a two-state Gaussian hidden Markov model in the slowly mixing regime, where the transition probability δ may vanish with the sample size. Temporal persistence creates long homogeneous segments and fundamentally changes the recovery problem relative to the i.i.d. Gaussian mixture benchmark. Rather than being purely adverse, label dependence provides exploitable structure: the statistical difficulty becomes concentrated near the rare transition points, giving rise to recovery regimes governed explicitly by their frequency δ. We first characterize, up to universal constants, the oracle Bayes risk for offline and online clustering. Both problems exhibit a nonstandard polynomial risk regime, but the sequential constraint induces an additional logarithmic localization cost, yielding a genuine online/offline gap. We also study fixed lag prediction with delayed label feedback and identify the effective memory horizon beyond which past labels no longer improve the optimal rate. When the signal direction is unknown and possibly high dimensional, the problem is governed by the effective signal strength r_n^2 = |θ|^4/σ^4/(|θ|^2/σ^2+d/n). We derive minimax lower bounds and construct fully adaptive polynomial time procedures attaining the sharp recovery rates. In particular, almost full recovery is possible precisely when r_n^2≫δ. If nδ≳log n, adaptation to both the signal θ and the transition probability δ incurs no first order loss, and the sharp exact recovery threshold (under the Hamming loss) is r_n^2 = 2log(nδ) (1+o(1)). Thus the effective complexity of the problem is governed by the number of latent transitions, rather than by the sample size itself.
ER -