Rademacher complexity of a norm-bounded linear class

ProofAdvanced⏱ 30 minLearning Theoryrademacherlinear classdimension freemargin

Theory: VC Dimension, Sauer's Lemma and Rademacher Complexity →

Problem

Let $\Fcal_B = \{x\mapsto\langle w,x\rangle : \|w\|_2\le B\}$ and suppose $\|x_i\|_2\le R$ . Prove $\hat{\mathfrak R}_S(\Fcal_B)\le BR/\sqrt n$ , and observe that the bound does not involve the dimension. Explain the consequence for kernel methods.

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

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

Problem	Field	Type	Difficulty	Time
The geometric margin	Classical ML	Proof	Foundation	15 min
Solve a two-point SVM by hand	Classical ML	Numerical	Beginner	30 min
The psi-2 norm of a Rademacher sign	High-Dim Probability	Numerical	Beginner	15 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