VC dimension of halfspaces

ProofIntermediate⏱ 30 minLearning Theoryvc dimensionhalfspaceradon

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

Problem

Prove that homogeneous halfspaces $\{x\mapsto\sign\langle w,x\rangle\}$ in $\R^d$ have VC dimension exactly $d$ , and that with a bias term the dimension is $d+1$ .

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
A one-parameter class with infinite VC dimension	Learning Theory	Proof	Advanced	1 hour
Massart's finite maximal inequality	Learning Theory	Proof	Advanced	30 min
Rademacher complexity of a norm-bounded linear class	Learning Theory	Proof	Advanced	30 min
Derive the margin generalisation bound abyss	Learning Theory	Proof	Graduate	1 hour
Prove the Sauer–Shelah lemma abyss	Learning Theory	Proof	Graduate	3 hours