I understand the correct answer to the question, but i don't know why the first bullet point is not true? I feel like the l1-ball of radius 2eps is bigger than the l2-ball of radius eps? Could anyone clarify this for me please? Thanks. !
You are right that "I feel like the l1-ball of radius 2eps is bigger than the l2-ball of radius eps" for \(d=2\), but not for a general \(d\). For a general \(d\), the scaling factor for the radius should be rather \(\sqrt{d}\) instead of just \(2\). Then the \(\ell_1\)-ball of radius \(\sqrt{d} \varepsilon\) will fully contain the \(\ell_2\)-ball of radius \(\varepsilon\). For precise details on why it is the case, see, for example, this note, end of page 3.
My way of looking at this problem, and maybe I am completely mistaken here, is the following:
For the first bullet point on the left you are looking at a circle with a radius being \(\epsilon\), on the right you are looking at a square with a diagonal being 2*\(\epsilon\).
If you compute the surface areas of these two cases you will get \(\pi*\epsilon^2\) <= \(2*\epsilon^2\), which is not correct.
I am really sorry but I really don't understand how to answer this question. I am confused with the different norms… can you give a detailed explanation please?
On Slide 14 of the Adversarial Machine Learning lecture you can see the different shapes of 'balls' that these norms make. Based on the shape, you can calculate the surface area and volume of this 'balls', which can help you to answer this question.
You are right that "I feel like the l1-ball of radius 2eps is bigger than the l2-ball of radius eps" for \(d=2\), but not for a general \(d\). For a general \(d\), the scaling factor for the radius should be rather \(\sqrt{d}\) instead of just \(2\). Then the \(\ell_1\)-ball of radius \(\sqrt{d} \varepsilon\) will fully contain the \(\ell_2\)-ball of radius \(\varepsilon\). For precise details on why it is the case, see, for example, this note, end of page 3.
As for the other suggestions mentioned here, I don't think it's correct to check the surface or volume. It could happen that the volume of set 1 is larger than the volume of set 2, but the maximum taken over set 1 can still be smaller. We can make some definite statements about maxima over different sets only when one set is fully contained within the other one. That was basically the only point of this question.
I am also confused by this Q15, and have read the document you sent (MATH-SHU 236 High Dimensional Geometry) but not understood the mathematical details, so I wanted to check my intuition:
So in the document and your response you only gave the reasoning of how the radii scale for the L1 and L2 norm. Is this also true for the Linf norm?
Ie. can we say for all comparisons between Li and Lj-norms, that the corresponding L_i ball is only contained in L_j ball if,
for ||x-^x||_i <= epsilon
then for
||x-^x||_j <= sqrt(d) * epsilon ?
Problem 15 exam 2020
Hi
I understand the correct answer to the question, but i don't know why the first bullet point is not true? I feel like the l1-ball of radius 2eps is bigger than the l2-ball of radius eps? Could anyone clarify this for me please? Thanks. !
2
Hi,
You are right that "I feel like the l1-ball of radius 2eps is bigger than the l2-ball of radius eps" for \(d=2\), but not for a general \(d\). For a general \(d\), the scaling factor for the radius should be rather \(\sqrt{d}\) instead of just \(2\). Then the \(\ell_1\)-ball of radius \(\sqrt{d} \varepsilon\) will fully contain the \(\ell_2\)-ball of radius \(\varepsilon\). For precise details on why it is the case, see, for example, this note, end of page 3.
I hope that helps.
Best,
Maksym
2
My way of looking at this problem, and maybe I am completely mistaken here, is the following:
For the first bullet point on the left you are looking at a circle with a radius being \(\epsilon\), on the right you are looking at a square with a diagonal being 2*\(\epsilon\).
If you compute the surface areas of these two cases you will get \(\pi*\epsilon^2\) <= \(2*\epsilon^2\), which is not correct.
I hope this helps:)
I am really sorry but I really don't understand how to answer this question. I am confused with the different norms… can you give a detailed explanation please?
On Slide 14 of the Adversarial Machine Learning lecture you can see the different shapes of 'balls' that these norms make. Based on the shape, you can calculate the surface area and volume of this 'balls', which can help you to answer this question.
1
Hi,
You are right that "I feel like the l1-ball of radius 2eps is bigger than the l2-ball of radius eps" for \(d=2\), but not for a general \(d\). For a general \(d\), the scaling factor for the radius should be rather \(\sqrt{d}\) instead of just \(2\). Then the \(\ell_1\)-ball of radius \(\sqrt{d} \varepsilon\) will fully contain the \(\ell_2\)-ball of radius \(\varepsilon\). For precise details on why it is the case, see, for example, this note, end of page 3.
I hope that helps.
Best,
Maksym
2
As for the other suggestions mentioned here, I don't think it's correct to check the surface or volume. It could happen that the volume of set 1 is larger than the volume of set 2, but the maximum taken over set 1 can still be smaller. We can make some definite statements about maxima over different sets only when one set is fully contained within the other one. That was basically the only point of this question.
I hope that helps :)
Hello,
I am also confused by this Q15, and have read the document you sent (MATH-SHU 236 High Dimensional Geometry) but not understood the mathematical details, so I wanted to check my intuition:
So in the document and your response you only gave the reasoning of how the radii scale for the L1 and L2 norm. Is this also true for the Linf norm?
Ie. can we say for all comparisons between Li and Lj-norms, that the corresponding L_i ball is only contained in L_j ball if,
for ||x-^x||_i <= epsilon
then for
||x-^x||_j <= sqrt(d) * epsilon ?
Thanks!
Also a quick notational question:
What does that additional - non-subscript infinity sign mean in the sets? Is this a typo?
2
How do we know if one set is fully contained within the other one?
Add comment