McDiarmid-Type Inequalities for Graph-Dependent Variables and Stability Bounds

A crucial assumption in most statistical learning theory is that samples are independently and identically distributed (i.i.d.). We consider learning problems in which examples are dependent and their dependency relation is characterized by a graph. To establish algorithm-dependent generalization theory for learning with non-i.i.d. We show that concentration relies on the forest complexity of the graph, which characterizes the strength of the dependency. We demonstrate that for many types of dependent data, the forest complexity is small and thus implies good concentration.