Two different curses of dimensionality

NumericalBeginner⏱ 15 minClassical MLcurse of dimensionalitysample complexitycomparison

Theory: Nearest Neighbours and the Curse of Dimensionality →

Problem

Tabulate the sample size needed for accuracy $\eps = 0.1$ at $d = 10, 50, 200$ for (a) covariance estimation ( $n\asymp d/\eps^2$ ), (b) linear regression ( $n\asymp d/\eps^2$ ), (c) Lipschitz nonparametric regression ( $n\asymp\eps^{-(d+2)}$ ). Comment on the practical consequence.

Compute the requested quantities and say what they mean. A number without an interpretation is not an answer.

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
Distance contrast and the failure of nearest neighbours	Classical ML	Proof	Intermediate	30 min
Locating the Bernstein crossover	High-Dim Probability	Numerical	Intermediate	30 min
Sample complexity of covariance estimation	High-Dim Statistics	Numerical	Intermediate	30 min
Simulate and compare the concentration inequalities run	High-Dim Probability	Coding	Intermediate	1 hour