21–30 of 151 posts
Asymptotically better? Or practically better?
> The proof relies on a curious fact about high-dimensional geometry, which is that randomly distributed points placed on the surface of a sphere are almost all a full diameter away from each other. What theorem is this referring to? Sounds like something I should already be familiar with, but I'm not.
What I have just thought about though, is what points would be exactly diameter/2 distance away from that point? If you have a circle, you might think it would be the points that form a 90 degree triangle, but that is not the case, those points would be sqrt(2)*radius distance away.
So while it is obvious to me that it is not diameter/2, it is not obvious to me why it would be diameter either, or how larger n converges it closer to the diameter or some other fixed number.
> Right now, we are routinely creating neural networks that have a number of parameters more than the number of training samples. This says that the books have to be rewritten. Confused by this statement. Double descent with overparameterization is exhibited in "classical settings" too and mentioned in older books. > In their new proof, the pair show that overparameterization is necessary for a network to be robust.…
> Double descent with overparameterization is exhibited in "classical settings" too and mentioned in older books. I’m curious for references or citations to this. When I was going over double descent I tried to find citations like this (just in a couple places like ML/stats textbooks).
> The proof relies on a curious fact about high-dimensional geometry, which is that randomly distributed points placed on the surface of a sphere are almost all a full diameter away from each other. What theorem is this referring to? Sounds like something I should already be familiar with, but I'm not.
Earlier quoted context omitted.
Not my area of expertise, but the quoted "fact" seems at best incompletely stated: surely for it to hold there must be some constraints on the number of points (likely as a function of the diameter)?
It’s just wrong as stated, there is only one point a full diameter away from each point on a high dimensional sphere. Aka (1,0,0,0,0, …) maps to (-1,0,0,0,0, …) and nothing else. Just as (1,0) maps to (-1,0) on a unit circle and (1,0,0) maps to (-1,0,0) on a unit sphere. On a high dimensional sphere they should generally be close to square root of 2 radius away from each other.
> The proof relies on a curious fact about high-dimensional geometry, which is that randomly distributed points placed on the surface of a sphere are almost all a full diameter away from each other. What theorem is this referring to? Sounds like something I should already be familiar with, but I'm not.
I think it's something related to the curse of dimensionality [1] [2], basically just a property of high dimensional spaces (perhaps only certain kinds of spaces though). [1] https://en.wikipedia.org/wiki/Curse_of_dimensionality [2] http://kops.uni-konstanz.de/bitstream/handle/123456789/5715/...
The M-Tree is one of my favorite indexes. It works with data that's embedded in infinite dimensional spaces (sometimes; it's bumping up against an impossibility result that's sketched in a sibling comment).
> The proof relies on a curious fact about high-dimensional geometry, which is that randomly distributed points placed on the surface of a sphere are almost all a full diameter away from each other. What theorem is this referring to? Sounds like something I should already be familiar with, but I'm not.
My initial intuition is telling me that it would be diameter/2, from the perspective of a single point, the closest points would be near zero distance away, and the furthest points would be on the opposite side, a full diameter away, and I am assuming that there are a lot of points in a uniform distribution. What I have just thought about though, is what points would be exactly diameter/2 distance away from that poin…
> The proof relies on a curious fact about high-dimensional geometry, which is that randomly distributed points placed on the surface of a sphere are almost all a full diameter away from each other. What theorem is this referring to? Sounds like something I should already be familiar with, but I'm not.
Earlier quoted context omitted.
Not my area of expertise, but the quoted "fact" seems at best incompletely stated: surely for it to hold there must be some constraints on the number of points (likely as a function of the diameter)?
It’s just wrong as stated, there is only one point a full diameter away from each point on a high dimensional sphere. Aka (1,0,0,0,0, …) maps to (-1,0,0,0,0, …) and nothing else. Just as (1,0) maps to (-1,0) on a unit circle and (1,0,0) maps to (-1,0,0) on a unit sphere. On a high dimensional sphere they should generally be close to square root of 2 radius away from each other.
d(x,y) = 0 if x == y; 1 otherwise
Then all points are distance one apart. It's been proven that, as dimensionality increases, normal euclidian distance over uniform point clouds rapidly converges to have the same behavior as the equality metric.
The proof relies on the information gained by performing pairwise distance calculations.
In the example distance function I gave, there is zero information gained if you plug in two points that are known to be non-equal.
The information gained from evaluating the Euclidian distance function converges to zero as the dimensionality of the data set increases.
(Note: This does not hold for low dimensional data that's been embedded in a higher dimensional space.)
Edit: Misread your comment. Yes, everything ends up being the same distance apart. More precisely, the ratio of mean distance / stddev distance tends to infinity. The intrinsic dimensionality of the data is monotonic w.r.t. that ratio.
> The proof relies on a curious fact about high-dimensional geometry, which is that randomly distributed points placed on the surface of a sphere are almost all a full diameter away from each other. What theorem is this referring to? Sounds like something I should already be familiar with, but I'm not.
My initial intuition is telling me that it would be diameter/2, from the perspective of a single point, the closest points would be near zero distance away, and the furthest points would be on the opposite side, a full diameter away, and I am assuming that there are a lot of points in a uniform distribution. What I have just thought about though, is what points would be exactly diameter/2 distance away from that poin…
x1^2 + x2^2 + … + xn^2 = 1.
D = (x1-1)^2 + x2^2 + … + xn^2
x1^2 = 1 - x2^2 - x3^2 - … - xn^2
But we can be more mathematical about it. Our (very reasonable) assumption is that the volume of a n-dimensional disk is proportional to the nth power of its radius. The third equation shows that x1 is going to be big (meaning the distance to the chosen point above is not so close to the diameter) if a corresponding[1] point on the n-disk is close to the middle. But the distance from the origin, R, of a random point in the n-disk is distributed with pdf proportional to p(r) = r^n for r in [0,1]. So the cdf is just r^(n+1) and E[x1^2] = 1 - E[R] = 1 - (n+1)/(n+2), which tends to 0 as n grows.
Therefore we get E[D] = E[(1-x1)^2] + 1 - E[x1^2] which tends to 2 as n grows large.
[1] the correspondence is that if I give you a point on a disk, you can turn it into a point on a sphere by flipping a coin to decide if it goes in the upper or lower hemisphere and then projecting up or down perpendicular to the disk from the point onto the sphere. But thinking a little more, I’m not sure this preserves the metric as it favours points on the sphere that correspond to the middle parts of the disk. So I think the actual expected value of x1 should be smaller.