1. Online-to-PAC generalization bounds under graph-mixing dependencies
- Author
-
Abélès, Baptiste, Clerico, Eugenio, and Neu, Gergely
- Subjects
Statistics - Machine Learning ,Computer Science - Machine Learning - Abstract
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., Comment: 13 pages (10 main + 3 supplementary material). All authors contributed equally
- Published
- 2024