Distance contrast in high dimension

ProofAdvanced⏱ 1 hourHigh-Dim Probabilitynearest neighbourcontrastconcentrationcurse

Theory: High-Dimensional Geometry and Concentration of the Norm →

Problem

Let $x, x_1,\dots,x_N$ be i.i.d. with independent coordinates of mean $0$ , variance $1$ and bounded $\psi_2$ norm in $\R^d$ . Prove that with probability at least $1-\delta$ ,

\frac{\max_i\|x_i-x\|_2}{\min_i\|x_i-x\|_2} \le 1 + C\sqrt{\frac{\log(N/\delta)}{d}}

for an absolute constant $C$ , provided $d \gtrsim \log(N/\delta)$ . Interpret the result for $N = 10^6$ and $d = 100$ .

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

Hints

Hints — 0 of 3 revealed

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
Volume concentrates near the boundary	High-Dim Probability	Numerical	Beginner	15 min
Distance contrast and the failure of nearest neighbours	Classical ML	Proof	Intermediate	30 min
From an exponential tail bound to almost sure convergence	Probability	Proof	Intermediate	30 min
Simulate the measure of a spherical cap run	High-Dim Probability	Coding	Intermediate	30 min