Massart's finite maximal inequality

ProofAdvanced⏱ 30 minLearning Theorymassartmaximal inequalityrademachermgf

Problem

Let $A\subseteq\R^n$ be finite with $\|a\|_2\le r$ for all $a\in A$ , and let $\eps$ be a Rademacher vector. Prove

\E\max_{a\in A}\langle\eps,a\rangle \le r\sqrt{2\log|A|} .

Deduce a bound on the Rademacher complexity of a class with growth function $\Pi(n)$ .

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

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

Problem	Field	Type	Difficulty	Time
The psi-2 norm of a Rademacher sign	High-Dim Probability	Numerical	Beginner	15 min
The chi-squared moment generating function and its Chernoff bound	High-Dim Probability	Proof	Intermediate	30 min
VC dimension of halfspaces	Learning Theory	Proof	Intermediate	30 min
A one-parameter class with infinite VC dimension	Learning Theory	Proof	Advanced	1 hour
Rademacher complexity of a norm-bounded linear class	Learning Theory	Proof	Advanced	30 min