2019/09/05 by Rui Ray Zhang, Xingwu Liu, Zhang, Rui Ray +5 · 3 citations
Computer Science · Mathematics · #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Graph theory and applications #Limits and Structures in Graph Theory #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Point processes and geometric inequalities #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.1909.02330
openalex publication_date 2019/09/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A crucial assumption in most statistical learning theory is that samples are\nindependently and identically distributed (i.i.d.). However, for many real\napplications, the i.i.d. assumption does not hold. We consider learning\nproblems in which examples are dependent and their dependency relation is\ncharacterized by a graph. To establish algorithm-dependent generalization\ntheory for learning with non-i.i.d. data, we first prove novel McDiarmid-type\nconcentration inequalities for Lipschitz functions of graph-dependent random\nvariables. We show that concentration relies on the forest complexity of the\ngraph, which characterizes the strength of the dependency. We demonstrate that\nfor many types of dependent data, the forest complexity is small and thus\nimplies good concentration. Based on our new inequalities we are able to build\nstability bounds for learning from graph-dependent data.\n