4 ms·
This series is well written. The speed up is expected due because you're incorporating second-order information during the optimisation. For more insight into
by xtacy 8y ago
This series is well written. The speed up is expected due because you're incorporating second-order information during the optimisation. For more insight into second order optimisation methods, take a look at Newton's method: https://en.wikipedia.org/wiki/Newton%27s_method https://en.wikipedia.org/wiki/Newton%27s_method. The intuition, derivation, and proof of correctness and convergence speed are quite illuminating.
- wenc 8y agoThanks for this insight. I worked in deterministic optimization and there are many well-known techniques for speeding up convergence from line searches to 2nd-order derivatives (Hessians). These are fairly standard techniques. However I was unfamiliar with stochastic optimization, so on cursory reading, I didn't recognize these concepts until I realize what people are trying to do were probabilistic analogues of standard optimization techniques, e.g. instead of Euclidean norms, K-L divergences are used. In the discussion, the ADAM algorithm was mentioned, which sounds like a type of quasi-Newton method but with much simplified properties like constraining the elements to the diagonal. This sounds to me like the akin to the sort of simplification that Stochastic Gradient Descent (SGD) takes -- very crude but practical at extremely large scale. It's useful to note that for normal scale problems (thousands to a million variables), using analytical gradients (of which the natural gradient is a type of) and Hessians via automatic differentiation with a Newton-type method provide much faster convergence. SGD/ADAM are essentially a compromise to make things work at extremely large scale.