McDiarmid's inequality
http://dbpedia.org/resource/McDiarmid's_inequality
In probability theory and theoretical computer science, McDiarmid's inequality is a concentration inequality which bounds the deviation between the sampled value and the expected value of certain functions when they are evaluated on independent random variables. McDiarmid's inequality applies to functions that satisfy a bounded differences property, meaning that replacing a single argument to the function while leaving all other arguments unchanged cannot cause too large of a change in the value of the function.
rdf:langString
rdf:langString
McDiarmid's inequality
rdf:langString
McDiarmid's Inequality
xsd:integer
9181701
xsd:integer
1099155059
rdf:langString
In probability theory and theoretical computer science, McDiarmid's inequality is a concentration inequality which bounds the deviation between the sampled value and the expected value of certain functions when they are evaluated on independent random variables. McDiarmid's inequality applies to functions that satisfy a bounded differences property, meaning that replacing a single argument to the function while leaving all other arguments unchanged cannot cause too large of a change in the value of the function.
rdf:langString
Let satisfy the bounded differences property with bounds .
Consider independent random variables where for all .
Then, for any ,
:
:
and as an immediate consequence,
:
rdf:langString
Let be a function.
Consider independent random variables where for all .
Let refer to the th centered conditional version of .
Let denote the sub-exponential norm of a random variable.
Then, for any ,
:
rdf:langString
Let be a function and be a subset of its domain and let be constants such that for all pairs and ,
:
Consider independent random variables where for all .
Let and let .
Then, for any ,
:
and as an immediate consequence,
:
rdf:langString
Let satisfy the bounded differences property with bounds .
Consider independent random variables drawn from a distribution where there is a particular value which occurs with probability .
Then, for any ,
:
rdf:langString
Let satisfy the bounded differences property with bounds . Let and be defined as at the beginning of this section.
Then, for any ,
:
rdf:langString
Let be a function.
Consider independent random variables where for all .
Let refer to the th centered conditional version of .
Let denote the sub-Gaussian norm of a random variable.
Then, for any ,
:
rdf:langString
Let satisfy the bounded differences property with bounds .
Consider independent random variables where for all . Let and be defined as at the beginning of this section.
Then, for any ,
:
xsd:nonNegativeInteger
17483