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.). However, for many real applications, the i.i.d. assumption does not hold. 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. data, we first prove novel McDiarmid-type concentration inequalities for Lipschitz functions of graph-dependent random variables. 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. Based on our new inequalities we are able to build stability bounds for learning from graph-dependent data.
Code (0)
등록된 구현이 없습니다.
Tasks
Learning TheoryVocal Bursts Type PredictionSimilar Papers 제목 키워드 기반
Concentration inequalities under sub-Gaussian and sub-exponential conditions
We prove analogues of the popular bounded difference inequality (also called McDiarmid's inequality) for functions of independent random variables under sub-gaussian and sub-exponential conditions. Applied to vector-valu…
regressionDistribution-dependent concentration inequalities for tighter generalization bounds
Concentration inequalities are indispensable tools for studying the generalization capacity of learning models. Hoeffding's and McDiarmid's inequalities are commonly used, giving bounds independent of the data distributi…
Generalization BoundsLearning TheoryOn McDiarmid's Inequality under Dependence via Approximate Tensorization of Entropy
We argue that dependent versions of McDiarmid's inequality are a useful but underutilized tool in mathematical statistics, learning theory and theoretical computer science. To make this point, we first highlight that app…
Concentration Inequalities for the Stochastic Optimization of Unbounded Objectives with Application to Denoising Score Matching
We derive novel concentration inequalities that bound the statistical error for a large class of stochastic optimization problems, focusing on the case of unbounded objective functions. Our derivations utilize the follow…
DenoisingStochastic OptimizationGeneralization Error Bounds Via Rényi-, $f$-Divergences and Maximal Leakage
In this work, the probability of an event under some joint distribution is bounded by measuring it with the product of the marginals instead (which is typically easier to analyze) together with a measure of the dependenc…
Learning Theory