[SOLVED] DS-GA1008 Homework 2- The Curse of Dimensionality 

Homework 2 is to let you better understand the curse of dimensionality in theory and practice.

For theory questions, you should put all your answers in a PDF file and we will not accept any scanned hand-written answers. It is recommended to use LATEX.

For coding questions (Q2, Q12 and Q14), you need to program in Python. We recommand you to use PyTorch and NumPy for the experiments and Matplotlib to draw the plot. You need to submit your python files and describe the results with plots in the pdf.

If you only submit your python files without relevant description and plots in the pdf, you will get no points for the questions.

In homework 2, the questions have 25 points in total. We set 5 bonus points and it means that you will have full credits if you get 20 points and extra credits for more points.

The due date of homework 2 is 23:55 EST of 10/11. Submit the following files in a zip file your_net_id.zip through NYU Brightspace:

• HW2.pdf
• q2.py, q12.py (optional) and q14.py

The following behaviors will result in penalty of your final score:

1. 5% penalty for submitting your files without using the correct format. (including naming the zip file, PDF file or python file wrong, or adding extra files in the zip folder, like the testing scripts from coding questions).
2. 20% penalty for late submission within the first 24 hours. We will not accept any late submis- sion after the first 24 hours.
3. 20% penalty for code submission that cannot be executed using the steps we mentioned in coding questions. So please test your code before submit it.

   1

Problem 1: The Curse of Dimensionality

In this problem, we will study a high-dimensional statistical phenomena called the Curse of Dimen- sionality. Originally coined by Bellman in the context of dynamic programming, it generally refers to the failure of certain statistical or algorithmic procedures to scale efficiently as the input dimension grows.

We will first study this curse through the geometry of the unit d-dimensional l2 sphere. Recall that the lp norm of a vector x ∈ Rd is defined as ∥x∥p := (􏰃i |xi|p)1/p, for p ∈ [1,∞). To get a first grasp on the phenomena, we will first consider a ‘Gaussian’ approximation of the d-dimensional unit sphere, by considering a Gaussian random vector X ∼ N (0, I/d), where I is the d × d identity matrix.

1. Using the Central Limit Theorem, show that ∥X∥2 = 1+O(1/􏰀d) with high probability. In other words, show that ∥X∥2 is a random variable with expectation 1 and standard deviation

   proportional to 1/ d. [Alternative: use the χ-squared distribution with d degrees of freedom]. (1 point)

2. Numerically verify this property by simulating ∥X∥2 in dimensions d ∈ {10,100,1000,10000} using a sample size of n = 1000. (2 points)

This means that for large input dimension d, a draw X from the N(0,I/d) Gaussian distribution will concentrate to the unit sphere ∥X∥2 ≈ 1. Let us also verify that the Gaussian distribution is rotationally invariant:

3. LetR∈Rd×d beanyunitarymatrix,ieR⊤R=RR⊤=I.ShowthatthepdfofX∼N(0,I/d)and X ̃ = R X are the same, ie they do not depend on the choice of R. (2 points)

For our purposes, we will thus use Gaussian N(0,I/d) samples as de facto draws from the unit d- dimensional sphere.

4. If we draw two datapoints X,X′ i.i.d. from N(0,I/d), show that |〈X,X′〉|=O(1/􏰀d) with high probability using again the CLT. In other words, show that 〈X,X′〉 is a random variable of

􏰀

􏰀
∥X − X ′∥ ∈ (􏰀2 ± C/􏰀d) for large d with high probability. (2 points)

zero mean and standard deviation proportional to 1/

d. Conclude that for a constant C > 0,

This property reflects the intuition that independent draws from a high-dimensional Gaussian distri- bution (or any rotationally-invariant distribution, more generally) are nearly orthogonal as d → ∞, since |〈 X , X ′ 〉| will have variance going to 0 as d → ∞.

We will now combine this intuition with a simple supervised learning setup. Assume a target function f ∗ : Rd → R is β-Lipschitz, ie |f ∗(x) − f ∗(x′)| 􏰁 β∥x − x′∥, and a dataset {(xi, yi)}i…n with xi ∼ N (0, I/d) and yi = f ∗(xi) drawn independently. We will consider the Nearest-Neighbor estimator

fˆNN given by
5. Show that E|fˆNN(x) − f ∗(x)| 􏰁 βEmini ∥x − xi∥, where the expectation is taken over the test

sample x and the training sample {xi}. (2 points) 2

fˆNN(x):= yi(x) , where i(x)=argmin∥x−xi∥ . i

6. Let En denote the expectation of mini=1…nYi, where Yi ∼N(0,1) i.i.d. Show that if now Xi ∼ N(μ,σ2) i.i.d., then Emini Xi =μ+σEn. (1 point)
7. Using the fact that ∥x−xi∥ and ∥x−xj∥ are conditionally independent, given x, and assuming theasymptoticGaussianityof∥X−X′∥→d N(􏰀2,C/d)foraconstantC>0,showthatEmini∥x−
8. UsingthefactthatEn ≈−􏰅2logn,concludethataslongaslogn≪d,thegeneralisationbound in (5) is vacuous (in other words, unless the sample size is exponential in dimension, the bound does not provide any useful learning guarantee). (2 points)

While this argument shows that our Lipschitz-based upper bound is cursed by dimension, let us conclude this exercise by showing that the exponential dependency in dimension is necessary. For simplicity, we will replace the d-dimensional l2 sphere by the l∞ sphere, ie the cube B = [−1,1]d. Let Ω = [−1/2,1/2]d denote a smaller cube. For x ∈ Ω, let Ψ(x) = dist(x,∂Ω). In words, Ψ(x) is the distance from x to the boundary of the cube Ω.

9. Show that Ψ is 1-Lipschitz. [Hint: Use the triangular inequality, and the definition of Ψ as Ψ(x) = miny∈∂Ω ∥x − y∥. Also, drawing Ψ in two-dimensions might help!] (2 points)

We will now use this 1-Lipschitz function supported in the ‘small’ cube Ω to construct a hard-to-learn function f ∗ defined in the large cube B = [−1, 1]d .

10. Verify that we can fit 2d copies of Ω into B, by translating copies of Ω appropriately [Hint: Use the fact that both Ω and B are separable in the standard basis. Also, drawing this in two-dimensions should help]. (2 points)

Let now g ∈ {±1}2d be a binary string of length 2d, that we index using d binary variables z1 = ±1,…zd =±1. We define

f ∗(x) = 􏰄 g(z)Ψ(x − z/2) . (0.1) z=z1=±1,…zd=±1

In words, f ∗ is constructed by tiling 2d shifted versions of the window Ψ, and flipping the sign of each tile with the bit g(z). From part 9, the support of f ∗ is the ‘large’ cube B.

11. Verify that f ∗ is 1-Lipschitz. [Hint: Given two points x, x′ ∈ B, consider the line segment joining them, and let yk be the intersections with boundaries of tiled Ω, treating each resulting segment separately.] (1 point)
12. For d = 2, draw an instance of f ∗ (You can use either manual drawing or a drawing software). (2 points)
13. Finally, show that if n, the number of training samples, satisfies n 􏰁 2d−1, then the generalisa- tion error of any learning algorithm producing fˆ will be such that

    Ex∼Unif([−1,1]d)|f ∗(x)− fˆ(x)| 􏰂 1/2 . Ex∼Unif([−1,1]d)|f ∗(x)|

    3

􏰀 􏰀C
xi∥∼ 2+􏰀dEn.(1point)

In words, the relative generalisation error won’t go to zero unless n 􏰆 2d. [Hint: Argue in terms of the tiling you have constructed in question 9; what happens if no datapoint intersects a given tile?] (2 points)

14. Choosing d ∈ [5, 13], implement this experiment, using any predictor for f ∗ you want (e.g. a Neural Net), and the Mean-Squared Error (MSE) loss. Verify that the required sample size n before your model starts generalising grows with d exponentially. For each d, draw two large datasets {xi}i=1…n, {x ̃i}i=1…n with xi,x ̃i ∼Unif([−1,1]d), then draw K =10 different target functions fk∗, k = 1…K by picking random bits in equation (0.1), and fit your model to the training data {(xi, yi = fk∗(xi)}i=1…n. Then estimate your relative generalisation error using the test set {(x ̃i,y ̃i = fk∗(x ̃i)} (MSE error divided by standard deviation of the target function on test set), and average the performance across the K runs. You can pick n ∈ {2j; j = 5…16}. (3 points)

4