Remember the claim 2 from the lectures.
probability of at least 1 point being in the cube is p.
If there are N points,
(1-p)=(1-r^D)^N
we want left hand to be constant,
By using Taylor expansion in the RHS
1-p = 1-Nr^D
with same probability if r goes r/2,
N must go 2^D N
In solutions, it used different argument.
You can also divide the space into cubes of r.
her will be 1/r^D cubes if the whole space is [0,1]^D
And if you put the points in the center of cubes, then you have N=1/r^D .
if r goes r/2, N must go N* 2^D.
I was also wondering the same question and it's clear now.
Though I didn't really get the Taylor expansion that you have mentioned, could you be more precise about it ?
Thanks a lot !
Just a last question, what if we would like to have the same performance on the dimension \(2D\) instead of \(D\) ? What would be the strategy ?
What I have found is that we have to solve the equation : \((1-r^{2D})^{N'} = (1-r^{D})^{N}\)
Since we want in this case \(r\) to be constant. With that I have : \(N' = N\frac{ log(1-r^{D}) }{ log(1-r^{2D}) }\)
And I am stuck here ... Is that correct ?
I also can not comment for that by such arguments.
L < 2L_Bayes + 4csqrt(D) N^(-1/(D+1))
I am convincing myself with this bound.
If we do not care about the sort of D, (since the exp is dominant)
For the same bound -> N ~ a^D
Question 4
How exactly do we get to the results $$\(2^D N\) $$? Where does that come from?
Remember the claim 2 from the lectures.
probability of at least 1 point being in the cube is p.
If there are N points,
(1-p)=(1-r^D)^N
we want left hand to be constant,
By using Taylor expansion in the RHS
1-p = 1-Nr^D
with same probability if r goes r/2,
N must go 2^D N
In solutions, it used different argument.
You can also divide the space into cubes of r.
her will be 1/r^D cubes if the whole space is [0,1]^D
And if you put the points in the center of cubes, then you have N=1/r^D .
if r goes r/2, N must go N* 2^D.
I hope that you get the intuition.
1
I was also wondering the same question and it's clear now.
Though I didn't really get the Taylor expansion that you have mentioned, could you be more precise about it ?
Thanks a lot !
1
(1+x)^N=1+Nx+ N(N-1)/2! x^2 +....
if x is small, which is the case if x=r^D (D is too large and r<1)
we can eliminate x^2 and more order terms.
1
Thanks a lot !
Just a last question, what if we would like to have the same performance on the dimension \(2D\) instead of \(D\) ? What would be the strategy ?
What I have found is that we have to solve the equation :
\((1-r^{2D})^{N'} = (1-r^{D})^{N}\)
Since we want in this case \(r\) to be constant. With that I have :
\(N' = N\frac{ log(1-r^{D}) }{ log(1-r^{2D}) }\)
And I am stuck here ... Is that correct ?
Thanks
I also can not comment for that by such arguments.
L < 2L_Bayes + 4csqrt(D) N^(-1/(D+1))
I am convincing myself with this bound.
If we do not care about the sort of D, (since the exp is dominant)
For the same bound -> N ~ a^D
Add comment