无需依赖混合时间,可精准恢复高维高斯图模型边结构。
Mixing-Free and Signal-Optimal Learning of Gaussian Graphical Models from Glauber Dynamics
- 基于更新序列构造局部统计量,避免依赖马尔可夫链混合时间。
- 在最小归一化边强度κ下,样本复杂度达κ⁻²的理论最优界。
- 适合处理非平稳、强依赖数据,适用于高维图模型学习场景。
高斯图模型选择通常在独立采样假设下研究,但许多应用中数据是依赖随机过程的单一轨迹。本文研究从随机扫描高斯格劳伯动力学的单条轨迹中精确恢复图结构的问题。现有方法或继承链的混合时间(可能随维度p超多项式增长),或在最小归一化边强度κ上表现次优。本文提出两种无混合时间依赖的算法,均达到信息论下界中κ⁻²的依赖关系。二者均基于共享的对抗邻域搜索元算法,使用直接从更新序列构建的局部统计量。对于固定精度矩阵和确定性初始化,第一种算法在每个节点的更新点进行最小二乘回归,点态恢复时域为~O(pd²/κ²),依赖于局部条件数和初始势能的对数。第二种算法基于特定更新模式的计数,需~O(pd⁴/κ²)次更新,且不依赖任何条件数。核心技术挑战在于统计量来自依赖、非平稳观测。分析通过证明如何从更新序列中提取新的高斯创新,实现对相关量的无混合控制。两类算法及其分析均不依赖平稳性、谱间隙或混合条件。
原文摘要 · Abstract (English)
Gaussian graphical model selection is usually studied under independent sampling, but in many applications the data arise as a single trajectory of a dependent stochastic process. We study exact recovery of the graph from one trajectory of random-scan Gaussian Glauber dynamics. Existing techniques for this problem either inherit the mixing time of the chain, which can be super-polynomial in the dimension $p$ without strong assumptions, or are suboptimal in the minimum normalized edge strength $κ$. We propose two algorithms that are mixing-free and attain the $κ^{-2}$ dependence of the information-theoretic lower bounds. Both instantiate a shared dueling-neighborhood search meta-algorithm with a local statistic built directly from the update sequence. For every fixed precision matrix and deterministic initialization, the first algorithm fits a least-squares regression at the updates of each node and has pointwise recovery horizon $\widetilde O(pd^{2}/κ^{2})$, where $d$ is the maximum degree. Its horizon depends logarithmically on a local conditioning quantity and on the initialization potential. The second algorithm is based on counting occurences of a specific update pattern and requires $\widetilde O(pd^{4}/κ^{2})$ updates, with no dependence on any condition number. The central technical challenge is that both statistics are built from dependent, non-stationary observations. Our analysis tackles this by demonstrating how to extract fresh Gaussian innovations from the update sequence, which yields mixing-free control of appropriate quantities. Neither the algorithms nor their analyses invoke stationarity, a spectral gap, or mixing conditions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。