The k-NN bias–variance balance

ProofAdvanced⏱ 1 hourClassical MLknnratenonparametriccurse

Theory: Nearest Neighbours and the Curse of Dimensionality →

Problem

Derive the $k$ -NN regression rate $n^{-2/(d+2)}$ by balancing a bias term $\Lambda^2(k/n)^{2/d}$ against a variance term $\sigma^2/k$ , and determine the optimal $k$ . Then compute the sample size needed for accuracy $\eps = 0.1$ at $d = 5, 20, 100$ .

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
Simulate distance contrast run	Classical ML	Coding	Beginner	30 min
Two different curses of dimensionality	Classical ML	Numerical	Beginner	15 min
Distance contrast and the failure of nearest neighbours	Classical ML	Proof	Intermediate	30 min
Measure the covariance estimation rate run	High-Dim Statistics	Coding	Intermediate	1 hour
Non-convex gradient descent reaches an approximate stationary point	Optimization	Proof	Intermediate	30 min