XOR is not linearly separable

ProofFoundation⏱ 15 minDeep Learningperceptronxorseparability

Theory: Approximation Theory and Backpropagation →

Problem

Prove there is no $(w,b)$ with $\sign(\langle w,x\rangle+b)$ equal to XOR on $\{0,1\}^2$ , then exhibit a two-hidden-unit ReLU network that computes it exactly.

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 proximal operator of the l1 norm	Advanced Optimization	Proof	Beginner	15 min
Derive the backpropagation recursion	Deep Learning	Proof	Intermediate	30 min
Gradient magnitude through a deep chain	Deep Learning	Proof	Intermediate	30 min
Implement backpropagation from scratch run	Deep Learning	Coding	Intermediate	3 hours
Logistic regression diverges on separable data	Classical ML	Proof	Intermediate	30 min