Surveys in Combinatorics, 1989: On the method of bounded differences

By Colin J. H. McDiarmid. 1989

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Rademacher and Gaussian Complexities: Risk Bounds and Structural Results (2003, neutral): “The proof uses McDiarmid’s inequality (McDiarmid, 1989).”
Are adversarial examples inevitable? (2018, background): “The case p = 0 was studied by Milman & Schechtman (1986) (Section 6.2) and McDiarmid (1989), and later by Talagrand (1995; 1996).”
Multi-Task Learning and Algorithmic Stability (2015, methodology): “Recall that the main tool to study the single-task generalization bound based on the single-task uniform stability in (Bousquet and Elisseeff 2002) is the McDiarmid’s inequality (McDiarmid 1989).”
Extensions to McDiarmid's inequality when dierences are bounded with high probability (2002, methodology): “McDiarmid gives a proof [18] of Theorem 1.”
Random graphs with a given degree sequence (2010, background): “The proof is a simple consequence of the bounded difference inequality [36].”
Generalizing from Several Related Classification Tasks to a New Unlabeled Sample (2011, unknown): “…decomposition: sup f∈Bk(R) ∣∣∣∣∣∣ 1N N∑ i=1 1 ni ni∑ j=1 `(f(X̃ij), Yij)− E(f,∞) ∣∣∣∣∣∣ ≤ sup f∈Bk(R) ∣∣∣∣∣∣ 1N N∑ i=1 1 ni ni∑ j=1 ( `(f(P̂ (i)X , Xij), Yij)− `(f(P (i) X , Xij), Yij) )∣∣∣∣∣∣ + sup f∈Bk(R) ∣∣∣∣∣∣ 1N N∑ i=1 1 ni ni∑ j=1 `(f(P (i)X , Xij), Yij)− E(f,∞) ∣∣∣∣∣∣ =: (I) + (II).”
Introduction to Statistical Learning Theory (2004, methodology): “The bounded differences inequality was formulated explicitly first by McDiarmid [17] who proved it by martingale methods (see the surveys [17], [50]), but closely related concentration results have been obtained in various ways including information-theoretic methods (see Alhswede, Gács, and Körner ”
Rademacher Complexity Bounds for Non-I.I.D. Processes (2008, methodology): “Our proof makes use of McDiarmid’s inequality [8] to show that the empirical average closely estimates its expectation.”