Derive Hoeffding's inequality from Hoeffding's lemma
ProofIntermediate⏱ 30 minHigh-Dim Probabilityhoeffdingchernoffderivation
Problem
Assuming Hoeffding's lemma — a centred variable supported on satisfies — derive the full Hoeffding inequality
carrying out the optimisation over explicitly. Then invert it to state the bound in "with probability " form for i.i.d. variables in .
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| Solved | Problem | Field | Type | Difficulty | Time |
|---|---|---|---|---|---|
| Markov and Chebyshev are attained | High-Dim Probability | Proof | 15 min | ||
| Generalisation for a finite class | Learning Theory | Proof | 30 min | ||
| Azuma for a random walk with drift | High-Dim Probability | Proof | 30 min | ||
| Derive the dual of a quadratic program | Advanced Optimization | Proof | 30 min | ||
| Locating the Bernstein crossover | High-Dim Probability | Numerical | 30 min |