4 ms·

You evaluate the function at two neighboring points, and the difference of function values (divided by the distance between the two points) gives you an estimat

You evaluate the function at two neighboring points, and the difference of function values (divided by the distance between the two points) gives you an estimate of the gradient projected along the direction between the two points. It’s literally the definition of the derivative — but you cannot practically take an infinitesimal step, so the points are a finite distance away (substantially bigger than machine precision). Another way to think about it — you choose a random line through your current location, and test neighboring points in two opposite directions, and step in the direction of whichever seems better. That’s why it costs as much as two forward passes. If you squint a little, the random choice of direction (line) makes it look kinda like evolutionary search. This is a textbook method, so I’m sure there must be some description on the web with pretty pictures and clearly worked out math — but I’m AFK right now and can’t find a good one through my phone :-(

nighthawk454 3y ago
Maybe check out this paper, the first page has a decent diagram and caption! https://arxiv.org/abs/2006.06224 https://arxiv.org/abs/2006.06224
oersted 3y ago
Yes that's what I had in mind. Interesting that they can get decent convergence even with 100x, considering that to get a decently accurate gradient in all D dimensions you need to sample D forward passes, and we are talking of D in billions, and each forward pass involves billions of FLOPs. And then it's still an estimate since, as you say, it is not an infinitesimal delta. Interesting that it converges when just sampling one point in one direction per iteration.
- ssivark 3y ago
  Right — that’s certainly surprising & intriguing. So they discuss this in section 4, and offer a theoretical argument why the rate of convergence might be independent of the (large) number of parameters. I haven’t grokked that yet, but maybe one could think of this as a consequence of the shape of the landscape (cost function) in the overparametrized regime.

nighthawk454 3y ago

Maybe check out this paper, the first page has a decent diagram and caption! https://arxiv.org/abs/2006.06224 https://arxiv.org/abs/2006.06224

oersted 3y ago

Yes that's what I had in mind. Interesting that they can get decent convergence even with 100x, considering that to get a decently accurate gradient in all D dimensions you need to sample D forward passes, and we are talking of D in billions, and each forward pass involves billions of FLOPs. And then it's still an estimate since, as you say, it is not an infinitesimal delta. Interesting that it converges when just sampling one point in one direction per iteration.

ssivark 3y ago
Right — that’s certainly surprising & intriguing. So they discuss this in section 4, and offer a theoretical argument why the rate of convergence might be independent of the (large) number of parameters. I haven’t grokked that yet, but maybe one could think of this as a consequence of the shape of the landscape (cost function) in the overparametrized regime.