Online-to-PAC generalization bounds under graph-mixing dependencies
This work addresses generalization in non-i.i.d. data for machine learning practitioners, but it is incremental as it builds on existing online-to-PAC and mixing dependency methods.
The paper tackles the problem of relaxing independence assumptions in statistical learning by proposing a framework where dependencies decay with graph distance, bridging temporal mixing and graph-dependency approaches. It derives generalization bounds using an online-to-PAC framework, with guarantees depending on mixing rate and graph chromatic number.
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.