3 ms·

It isn't mentioned in the abstract, but this seems to be more of an overview of ML-specific notions of gradient descent, where batch processing is possible due

It isn't mentioned in the abstract, but this seems to be more of an overview of ML-specific notions of gradient descent, where batch processing is possible due to needing to leverage gradients of a fixed prediction architecture over a large set of training data, with respect to tunable weights. So each of those training points represents a sort of separable or parallelizable piece of the whole processes, giving you a ton of freedom in how you actually execute the gradient stepping (with one training point, several of them, or all of them). As I understand it, stochasticity in this process interestingly seems to add enough "noise" that local minima seem to be avoided in many cases. In more general applications of non-linear gradient-based optimization (say for optimizing parametric models in physical engineering), this doesn't necessarily come into play.

sdenton4 9y ago
Do you have any sense of whether tricks like momentum which afaik came out of improving SGD for neural network training have found application in other arenas where batching is less reasonable?
- thearn4 9y ago
  I think there is room to exchange ideas between the nonlinear programming and ML communities for sure. Specifically for momentum, if I understand it right it's a particular way of perturbing step size and gradient steps to prevent oscillation. There are some other good examples of this used by many gradient-descent optimizers. For example: https://www.cs.cmu.edu/~ggordon/10725-F12/scribes/10725_Lecture5.pdf https://www.cs.cmu.edu/~ggordon/10725-F12/scribes/10725_Lect... There's part of me that wonders if one interesting way forward for deep learning is a minibatch form of BFGS or SNOPT.
- santaclaus 9y ago
  > Do you have any sense of whether tricks like momentum which afaik came out of improving SGD for neural network training have found application in other arenas where batching is less reasonable? I thought Yurii Nesterov came up with momentum (or at least proved certain classes of momentum strategies optimal)?
- srean 9y ago
  One does not need to invoke SGD or NN for the momentum term. Its there in conjugate gradients method, its just not called momentum. Its there in heavy-ball methods much more overtly. In fact if the cost function is convex and has smooth gradients one can show that optimal momentum equipped methods would converge faster than gradient methods. These methods achieve the best possible (black box) convergence rate bound for minimizing an arbitrary convex function using local information, gradient descent methods do not. The old references to consult are Nemirovskii, Nesterov and Polyak. One has to be careful about the claim though. The optimal convergence rate result mentioned above applies to arbitrary convex functions. For specific convex functions where you can exploit problem specific structure you may be able to do better. The other caveat is that these (batch) momentum methods tend to be quite sensitive to the convexity and smoothness parameters. Gradient descent is a lot more robust and you can get away with a lot. However if you are sure that the you can evaluate the exact gradient, then momentum based methods are arguably the better choice. Dont panic if the cost function goes up and down (that's expected), they do not reduce the cost function monotonically.

sdenton4 9y ago

Do you have any sense of whether tricks like momentum which afaik came out of improving SGD for neural network training have found application in other arenas where batching is less reasonable?

thearn4 9y ago
I think there is room to exchange ideas between the nonlinear programming and ML communities for sure. Specifically for momentum, if I understand it right it's a particular way of perturbing step size and gradient steps to prevent oscillation. There are some other good examples of this used by many gradient-descent optimizers. For example: https://www.cs.cmu.edu/~ggordon/10725-F12/scribes/10725_Lecture5.pdf https://www.cs.cmu.edu/~ggordon/10725-F12/scribes/10725_Lect... There's part of me that wonders if one interesting way forward for deep learning is a minibatch form of BFGS or SNOPT.
santaclaus 9y ago
> Do you have any sense of whether tricks like momentum which afaik came out of improving SGD for neural network training have found application in other arenas where batching is less reasonable? I thought Yurii Nesterov came up with momentum (or at least proved certain classes of momentum strategies optimal)?
srean 9y ago
One does not need to invoke SGD or NN for the momentum term. Its there in conjugate gradients method, its just not called momentum. Its there in heavy-ball methods much more overtly. In fact if the cost function is convex and has smooth gradients one can show that optimal momentum equipped methods would converge faster than gradient methods. These methods achieve the best possible (black box) convergence rate bound for minimizing an arbitrary convex function using local information, gradient descent methods do not. The old references to consult are Nemirovskii, Nesterov and Polyak. One has to be careful about the claim though. The optimal convergence rate result mentioned above applies to arbitrary convex functions. For specific convex functions where you can exploit problem specific structure you may be able to do better. The other caveat is that these (batch) momentum methods tend to be quite sensitive to the convexity and smoothness parameters. Gradient descent is a lot more robust and you can get away with a lot. However if you are sure that the you can evaluate the exact gradient, then momentum based methods are arguably the better choice. Dont panic if the cost function goes up and down (that's expected), they do not reduce the cost function monotonically.