Plain language descriptions of algorithms and theorems are the best writing of all. Thank you for this! The naive question I have from it is, what makes gradient descent better than 1/e best choice sampling (e.g. secretary problem)?
The "step size" parameter seems the same as given a sample size with what appears to be a random walk. I lack the background, but the example shows that you already know the function, so instead of picking an arbitrary point and descent rate, you pick a number of random samples, then apply the secretary problem to them (https://en.wikipedia.org/wiki/Secretary_problem#1/e-law_of_b...)
Top down from an outsiders perspective, (think product manager or customer for ML solution level) what advantage do I get from the compute cost of gradient descent over random sampling?
> what advantage do I get from the compute cost of gradient descent over random sampling?
Random sampling becomes prohibitive in higher dimensions due to the curse of dimensionality [0]. Gradient descent doesn't have this problem and will always converge to a local (but, as can be seen here, not necessarily an absolute) minimum.
The step size effectively controls how far from the "real" local minimum you can get: too big a step size and you end up repeatedly "jumping over" the minimum.
Perfect, that's the problem I needed to know about! I had been using combinatoric explosion as an example for how to explain why some tasks were harder/impossible, but it's a subset of this more general information problem, thank you.
> Plain language descriptions of algorithms and theorems are the best writing of all
Be careful with this. Understanding "edge cases" for an algorithm is just as important if not more than the core idea. With "plain language descriptions" you tend to get the latter but not the former which is _very_ dangerous.
I agree with you, but also want to add that there doesn't need to be that much caution either. Plain language helps create or deepen someones understanding of the core idea (or even an "intuition" for it, afte they become comfortable with it), which in turn then allows them to explore these edge cases.
9 comments
[ 4.6 ms ] story [ 35.4 ms ] threadThe "step size" parameter seems the same as given a sample size with what appears to be a random walk. I lack the background, but the example shows that you already know the function, so instead of picking an arbitrary point and descent rate, you pick a number of random samples, then apply the secretary problem to them (https://en.wikipedia.org/wiki/Secretary_problem#1/e-law_of_b...)
Top down from an outsiders perspective, (think product manager or customer for ML solution level) what advantage do I get from the compute cost of gradient descent over random sampling?
Random sampling becomes prohibitive in higher dimensions due to the curse of dimensionality [0]. Gradient descent doesn't have this problem and will always converge to a local (but, as can be seen here, not necessarily an absolute) minimum.
The step size effectively controls how far from the "real" local minimum you can get: too big a step size and you end up repeatedly "jumping over" the minimum.
[0] - https://en.wikipedia.org/wiki/Curse_of_dimensionality
Be careful with this. Understanding "edge cases" for an algorithm is just as important if not more than the core idea. With "plain language descriptions" you tend to get the latter but not the former which is _very_ dangerous.