Skip to content
nonconvexcard

Derive Hoeffding's inequality from Hoeffding's lemma

ProofIntermediate⏱ 30 minHigh-Dim Probabilityhoeffdingchernoffderivation

Problem

Assuming Hoeffding's lemma — a centred variable supported on [a,b][a,b] satisfies EeλX≤eλ2(b−a)2/8\E e^{\lambda X}\le e^{\lambda^2(b-a)^2/8} — derive the full Hoeffding inequality

P(∑i=1n(Xi−EXi)≥t)≤exp⁡(−2t2∑i(bi−ai)2),\P\Big(\sum_{i=1}^n(X_i-\E X_i) \ge t\Big) \le \exp\left(-\frac{2t^2}{\sum_i(b_i-a_i)^2}\right),

carrying out the optimisation over λ\lambda explicitly. Then invert it to state the bound in "with probability 1−δ1-\delta" form for i.i.d. variables in [0,1][0,1].

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints

Hints — 0 of 2 revealed

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems
SolvedProblemFieldTypeDifficultyTime
Markov and Chebyshev are attainedHigh-Dim ProbabilityProofFoundation15 min
Generalisation for a finite classLearning TheoryProofBeginner30 min
Azuma for a random walk with driftHigh-Dim ProbabilityProofIntermediate30 min
Derive the dual of a quadratic programAdvanced OptimizationProofIntermediate30 min
Locating the Bernstein crossoverHigh-Dim ProbabilityNumericalIntermediate30 min