EasyDeepLearn

What is Hoeffding's inequality?

hard

Answer

  • For bounded i.i.d.
  • XiX_{i} ∈ [a, b] with mean μ: P(∣Xn  −  μ∣  ≥  t)P( \mid Xn\; - \;{\mu} \mid \; \ge \;t) ≤ 2  ⋅  exp⁡(−2n  ⋅  t2  /  (b−a)2)2\; \cdot \;\operatorname{exp}( - 2n\; \cdot \;t^{2}\; / \;(b - a)^{2}).
  • Exponential (Gaussian-like) tail bound for sample means of bounded variables.
  • Much tighter than Chebyshev.
  • Used to prove PAC learning bounds, bandit / online learning regret bounds, and to derive sample-complexity requirements: n ~ log⁡(1/δ)  /  t2\operatorname{log}(1 / {\delta})\; / \;t^{2} for confidence δ and precision t.
  • Interview classic.
Check yourself — multiple choice
  • P is uniform
  • P(∣Xn  −  μ∣  ≥  t)P( \mid Xn\; - \;{\mu} \mid \; \ge \;t) ≤ 2 exp⁡(−2n  t2/(b−a)2)\operatorname{exp}( - 2n\;t^{2} / (b - a)^{2}) for bounded i.i.d. — sub-Gaussian bound; PAC learning basis
  • Only for normals
  • P doesn't decay

Hoeffding: exp bound on sample mean for bounded i.i.d. — PAC / bandit foundation.

#probability#theory

Practise Statistics Fundamentals

215 interview questions in this topic.

Read the lessonFlashcardsTake the quiz

Related questions