High Dimensional Probability

Weekly Student Reading Group

Meeting - 2

CS@UIUC

Speaker: Rohan Deb

Basic Quantities

• Expectation and Variance:

• Moment Generating Function:

• L^p norm of a random variable:

• Cumulative Distribution Function:

Basic Inequalities

• Jensen:

​

​

• Markov’s Inequality:

​

Basic Inequalities

• Chebyshev:

​

​

Limit Theorems

• Law of Large numbers:

​

​

Limit Theorems

• Central Limit Theorem:

​

​

Concentration Inequalities

• Concentration Inequalities:

​

Concentration Inequalities - Example

• Example:

​

​

Concentration of Gaussian r.v.

Concentration of Gaussian r.v.

Hoeffding’s Inequality

Sub-Gaussian Random Variables

• Sub-gaussian Random Variables: A random variable X with mean µ is called sub - Gaussian with parameter σ (X ∼ SG(σ)) if:

​

• For sub-Gaussian random variables we have:

Application: Bandits

Application: Bandits

• Algorithm: Explore then Commit
• Average reward received from arm i after round t

​

Application: Bandits

• Algorithm: Explore then Commit

Chernoff’s Inequality

References

• Introduction to High Dimensional Probability, Roman Vershynin
• Bandit Algorithms, Tor Lattimore and Csaba Szepesvari