Because if you are trying to draw samples from a hypersphere via rejection sampling from samples of the hypercube, your sampling efficiency will go down exponentially with dimensionality. A smaller and smaller percentage of your samples will go unrejected as dimensionality grows
Hmmm I don't think that's how it works. If you're trying to estimate the ratio of the volume between A and B and B is contained in A, and you randomly sample from A, the probability that the sample also belongs to B is smaller the smaller the B/A ratio, yes that's the point of the methodology. It's not less "efficient", every single data point contributes to the estimate the same way.
If the ratio B/A is 1/1 and you sample 1M times, 100k of the samples will also be contained in B. Are you saying that the other 900k somehow go unused?!
If the ratio B/A is 1/100, and you sample the same number of times, only 10k of the samples will be contained in B. Are you saying that's less "efficient"? You need both the numerator and the denominator!
What is the ratio B/A is 1/100 and you'd say that the methodology is very inefficient here, and I tell you that actually we're estimating the ratio A/B. Does it become very efficient? Surely it can't change as the two ratios arent independent.
No, I think your comment misses the point (or I missed the point of your comment).
Sorry, yes, you did miss the point. Specifically for the case of estimating volume, you just need enough points interior to the hypersphere to get good sampling statistics (which would become a problem in and of itself, by the way, at sufficient dimensionality). But estimating volume (or pi) is normally just used as a pedagogical example of rejection sampling, it’s not (usually) what people actually use the technique for. Typically its used to draw samples from one distribution, X, that is notionally hard to draw from, by instead drawing from Y. The sphere case is just an example (its actually easy to draw from a hypersphere without rejection sampling) - but if you did try to use rejection sampling specifically, it would take you a long time and lots of compute resources to generate those samples (in high dimensions)
(note: I am going to be imprecise here by describing the volume of the unit hypersphere, when such a concept does not exist, as the hypersphere only describes the surface of such a construct. It is more correct to call it the volume of the n-ball, or the volume enclosed by the unit hypersphere, but I'm not going to use that terminology throughout, in the interest of expediency.)
> What is the ratio B/A is 1/100 and you'd say that the methodology is very inefficient here, and I tell you that actually we're estimating the ratio A/B. Does it become very efficient? Surely it can't change as the two ratios arent independent.
That's exactly it, though. Rejection sampling is not primarily used to estimate ratios, but rather to draw points from a distribution by sampling a broader distribution and then rejecting points that don't satisfy some criteria. If you're attempting to sample the unit hypersphere by picking N points between 0 and 1, and rejecting any sets where sum(x_i^2) > 1, then you're going to be throwing away most of your data points in the process.
Going back to the topic of volume ratio estimation, though: both of you are underestimating quite how quickly the volume drops off. The unit hypersphere's volume decreases super-exponentially (there's a factorial in the denominator!), so if you're dealing with a mere 50 dimensions, you're looking at a ratio of 10^-13 [0]. In that regime, adding an extra dimension shrinks that volume by a factor of about 3; by the time you get to 100, that factor increases to 4.
If you're still only sampling a million points, chances are very good that you're going to decide that the ratio is 0. In order to accurately estimate the ratio, you need progressively more and more samples just to compensate for a slight increase in dimension.
I'd expect it to be much more efficient to use the change-of-coordinates approach the article also mentions, although I have personally never thought about a coordinate system well-suited to the 50-dimensional hypersphere. Probably 49 angles and a radius that's basically almost always 1, and a weird Jacobian that I don't want to compute by hand?
Also, as I mentioned, using rejection sampling to estimate the value of pi is a cute exercise but quite useless in practice compared to any of the more direct methods. If you sample a million points in the unit square, you'll end up with 3.142 +/- 0.0016. Meanwhile, if you use the fourth continued fraction for pi (355/113), you already have 3.141592(9)... for far less computation.
My point is that we're not just talking about A/B of 100, but rather A/B of 10000000000000 or more. If you're inverting the ratio we're estimating, then instead of estimating the value at 0, we're estimating it at infinity (or, okay, if you want to use Laplace smoothing, then a million, which is far too low).
There are situations where you would use rejection sampling because generating 100x more random numbers is much cheaper than doing the complex calculations required to accurately model the space in question. Maybe 50 dimensions (and the 13 orders of magnitude difference) isn't big enough to raise those concerns. If we instead talk about 100 dimensions, then we're dealing with a difference of 40 orders of magnitude, and if you tell me that still doesn't matter, then I don't know what to say.
You haven't addressed my question at all. If you think estimating 1e-1000 is a problem, then estimating 1e+1000 shouldn't be. But one is just the inverse of the other. What's the problem with this argument, you haven't answered it at all.
> If you think estimating 1e-1000 is a problem, then estimating 1e+1000 shouldn't be.
They're both problems. If you want to estimate 1e1000 via sampling individual points, then you need at least that order of magnitude of samples. If all of your data points fall in one class, then it doesn't matter what you're trying to calculate from that.
As I said: "If you're inverting the ratio we're estimating, then instead of estimating the value at 0, we're estimating it at infinity (or, okay, if you want to use Laplace smoothing, then a million, which is far too low)."
First off, you didn't answer my question which to restate is: if the ratio is 1/2, how many samples do you need.
Second, your claim that it depends on dimension is wrong, given the ratio of sets, dimension doesn't matter. If the ratio is 1/2 then you'll reject one half of the times regardless of dimension, and so by your own argument it's "very efficient"
> First off, you didn't answer my question which to restate is: if the ratio is 1/2, how many samples do you need.
Are we just trying to estimate the ratio? To what desired accuracy? If you have 100 samples and find that 50 points landed in your smaller set, okay, you can be 95% sure that the ratio is between 40% and 60%. That's not a very good estimate. If you want to drive those error bars down by 2x, you need 4x as many samples.
> Second, your claim that it depends on dimension is wrong, given the ratio of sets, dimension doesn't matter. If the ratio is 1/2 then you'll reject one half of the times regardless of dimension, and so by your own argument it's "very efficient"
When your sets in question are the volume enclosed by the n-dimensional unit hypersphere and the volume enclosed by the corresponding hypercube, which is what I assume we've been discussing this whole time, you do not get to pick what your ratio is between your sets for a given choice of n. If you're dealing with a 3-dimensional unit sphere and picking three random values uniformly between 0 and 1 (i.e. constrained to the positive octant), you will land within the hypersphere with probability pi/6 (close to your one-half ratio). You can't decide "okay now my ratio is 99%" unless you change how you draw your samples.
You can draw however many samples you want from the 100-dimensional unit hypercube to estimate the volume of the 100-dimensional unit hypersphere, and all you'll ever get is "the ratio is somewhere between 0 and some very small number, with X% probability".
Either way, as I have said multiple times, you are completely missing the point of rejection sampling by overindexing on the toy example that I explicitly stated is not a good use of rejection sampling.
> Are we just trying to estimate the ratio? To what desired accuracy?
Exactly. Number of samples depends on volume ratio and accuracy. It depends on dimension only through these two numbers. You got there in the end, proud of you.
You continue to miss the point. In this specific context, volume ratio scales super-exponentially with dimension, and unless you're willing to have accuracy also drop super-exponentially (as in, go very very quickly to zero), then you are wasting your time by trying to perform rejection sampling in a context where you are statistically never going to hit the target set.
Do you know how to program? It’s super easy to write a very simple rejection-based program to estimate the volume of a hypersphere (you can do it in <10 lines with numpy). Try it yourself for dimensionality 50 and see how long it takes before the estimate rises above precisely 0
Read my conversation with the other person. If you sample N times you'll be able to put a bound on the ratio, and that is the same regardless of dimension. To your example: if the ratio between sets in D=50 is 1e-50 and you ask how long it takes that your estimate bound doesn't contain zero, that will take a long time. Now if I ask you to estimate the ratio between the 2D circle and the 2D square with 50 decimal place, it will take the same time. Therefore, dimension doesn't enter here. This is a general property of Monte Carlo.
You know who also told everyone what he was going to do? And about whom everyone said "nah he's not really that crazy, he's just pretending for his supporters". Hitler. Also just stating facts.
I've used Jax quite a bit and it's so much better than tf/pytorch.
Now for the life of me, I still haven't been able to understan what a TPU is. Is it Google's marketing term for a GPU? Or is it something different entirely?
There's basically a difference in philosophy. GPU chips have a bunch of cores, each of which is semi-capable, whereas TPU chips have (effectively) one enormous core.
So GPUs have ~120 small systolic arrays, one per SM (aka, a tensorcore), plus passable off-chip bandwidth (aka 16 lines of PCI).
Where has TPUs have one honking big systolic array, plus large amounts of off-chip bandwidth.
This roughly translates to GPUs being better if you're doing a bunch of different small-ish things in parallel, but TPUs are better if you're doing lots of large matrix multiplies.
Way back when, most of a GPU was for graphics. Google decided to design a completely new chip, which focused on the operations for neural networks (mainly vectorized matmul). This is the TPU.
It's not a GPU, as there is no graphics hardware there anymore. Just memory and very efficient cores, capable of doing massively parallel matmuls on the memory. The instruction set is tiny, basically only capable of doing transformer operations fast.
Today, I'm not sure how much graphics an A100 GPU still can do. But I guess the answer is "too much"?
TPUs (short for Tensor Processing Units) are Google’s custom AI accelerator hardware which are completely separate from GPUs. I remember that introduced them in 2015ish but I imagine that they’re really starting to pay off with Gemini.
Believe it or not, I'm also familiar with Wikipedia. It reads that they're optimized for low precisio high thruput. To me this sounds like a GPU with a specific optimization.
It's a chip (and associated hardware) that can do linear algebra operations really fast. XLA and TPUs were co-designed, so as long as what you are doing is expressible in XLA's HLO language (https://openxla.org/xla/operation_semantics), the TPU can run it, and in many cases run it very efficiently. TPUs have different scaling properties than GPUs (think sparser but much larger communication), no graphics hardware inside them (no shader hardware, no raytracing hardware, etc), and a different control flow regime ("single-threaded" with very-wide SIMD primitives, as opposed to massively-multithreaded GPUs).
Thank you for the answer! You see, up until now I had never appreciated that a GPU does more than matmuls... And that first reference, what a find :-)
Edit: And btw, another question that I had had before was what's the difference between a tensor core and a GPU, and based on your answer, my speculative answer to that would be that the tensor core is the part inside the GPU that actually does the matmuls.
There is some kind of weird issue here, not sure what it is called, that where if the media were to blow this up everyone would say they are overreacting.
So it becomes a "seat at the table is better than no seat" thing where they won't ask Trump these questions.
It’s not the only possible outcome. Many countries have successfully protested against less controversial government practices and/or under worse conditions than there are now in the US.
reply