Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Hoeffding's Inequality: Binomial Distribution

In course

MGT-448: Statistical inference and machine learning

This course aims to provide graduate students a thorough grounding in the methods, theory, mathematics and algorithms needed to do research and applications in machine learning. The course covers topics from machine learning, classical statistics, and data ...

Description

This lecture covers Hoeffding's inequality, which is applied to independent random variables to estimate the probability of deviation from the expected sum. It also explores the binomial distribution as the sum of Bernoulli random variables, providing insights into concentration bounds and overfitting in Expected Risk Minimization. The lecture delves into predictors' error minimization and generalization gaps, emphasizing the importance of structural risk minimization in predictor selection.

Instructor

Negar Kiyavash

Official source

Ontological neighbourhood

Statistics

Statistical inference: Mathematical statistics

Related concepts (32)

Exchangeable random variables

In statistics, an exchangeable sequence of random variables (also sometimes interchangeable) is a sequence X1, X2, X3, ... (which may be finitely or infinitely long) whose joint probability distribution does not change when the positions in the sequence in which finitely many of them appear are altered. Thus, for example the sequences both have the same joint probability distribution. It is closely related to the use of independent and identically distributed random variables in statistical models.

Independent and identically distributed random variables

In probability theory and statistics, a collection of random variables is independent and identically distributed if each random variable has the same probability distribution as the others and all are mutually independent. This property is usually abbreviated as i.i.d., iid, or IID. IID was first defined in statistics and finds application in different fields such as data mining and signal processing. Statistics commonly deals with random samples. A random sample can be thought of as a set of objects that are chosen randomly.

Hoeffding's inequality

In probability theory, Hoeffding's inequality provides an upper bound on the probability that the sum of bounded independent random variables deviates from its expected value by more than a certain amount. Hoeffding's inequality was proven by Wassily Hoeffding in 1963. Hoeffding's inequality is a special case of the Azuma–Hoeffding inequality and McDiarmid's inequality. It is similar to the Chernoff bound, but tends to be less sharp, in particular when the variance of the random variables is small.

Concentration inequality

In probability theory, concentration inequalities provide bounds on how a random variable deviates from some value (typically, its expected value). The law of large numbers of classical probability theory states that sums of independent random variables are, under very mild conditions, close to their expectation with a large probability. Such sums are the most basic examples of random variables concentrated around their mean. Recent results show that such behavior is shared by other functions of independent random variables.

Chernoff bound

In probability theory, a Chernoff bound is an exponentially decreasing upper bound on the tail of a random variable based on its moment generating function. The minimum of all such exponential bounds forms the Chernoff or Chernoff-Cramér bound, which may decay faster than exponential (e.g. sub-Gaussian). It is especially useful for sums of independent random variables, such as sums of Bernoulli random variables. The bound is commonly named after Herman Chernoff who described the method in a 1952 paper, though Chernoff himself attributed it to Herman Rubin.

Related lectures (40)

Probability and Statistics

Delves into probability, statistics, paradoxes, and random variables, showcasing their real-world applications and properties.

Advanced Probabilities: Random Variables & Expected Values

Explores advanced probabilities, random variables, and expected values, with practical examples and quizzes to reinforce learning.

Random Variables: Expected Value

Covers advanced probability concepts, including random variables and expected value calculation.

Probability Theory: Midterm Solutions

Covers the solutions to the midterm exam of a Probability Theory course, including calculations of probabilities and expectations.

Probability and Statistics: Fundamental Theorems