提出图距离衰减依赖下的在线到PAC泛化界，统一时间与图依赖分析框架。
Online-to-PAC generalization bounds under graph-mixing dependencies
- 基于图距离定义依赖衰减，结合图结构与混合率建模数据相关性。
- 在高概率下给出泛化误差上界，依赖于混合速率与图的染色数。
- 适用于具有复杂依赖结构的数据，如社交网络或时空序列建模。
传统统计学习泛化理论依赖独立同分布的训练数据。近期放松独立性假设的研究主要聚焦于纯时序（混合）依赖或图依赖，前者需有序时间结构，后者无法量化依赖强度。本文通过引入依赖随图距离衰减的机制，融合两类方法，提出一个统一框架。利用在线到PAC转换，推导出集中不等式，并构建嵌入图结构的在线学习模型。所得高概率泛化保证同时依赖于混合速率和图的染色数，为非独立数据提供更灵活的理论分析工具。
原文摘要 · Abstract (English)
Traditional generalization results in statistical learning require a training data set made of independently drawn examples. Most of the recent efforts to relax this independence assumption have considered either purely temporal (mixing) dependencies, or graph-dependencies, where non-adjacent vertices correspond to independent random variables. Both approaches have their own limitations, the former requiring a temporal ordered structure, and the latter lacking a way to quantify the strength of inter-dependencies. In this work, we bridge these two lines of work by proposing a framework where dependencies decay with graph distance. We derive generalization bounds leveraging the online-to-PAC framework, by deriving a concentration result and introducing an online learning framework incorporating the graph structure. The resulting high-probability generalization guarantees depend on both the mixing rate and the graph's chromatic number.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。