5 ms·

What are the alternatives to gradient descent?

thumbuddy 3y ago
There are probably ly a hundred. Many people have asked for research into this for I don't know 20 years. But the hype doesn't die down and modern trends have mostly involved doing more GD with bigger models... A colleague and myself experimented with some alternatives and passed notes once in a while... For certain modelling problems you can save literal gpu days by going against the grain and get better results. Oh well...
- deleted 3y ago
  [deleted]
- stabbles 3y ago
  > Many people have asked for research into this for I don't know 20 years Sometimes I wonder if people in machine learning ever look at literature. Basic iteration schemes like the secant method (ok, 1-dimensional) have been known well over 3000 years. Newton's method is over 300 years old. Quasi-Newton methods (the secant method being an example) became popular in the early 1960s.
  - thumbuddy 3y ago
    Most ML papers I used to read fell into a couple of categories... 1. Baseless empirical result that probably was p hacked. 2. Mostly untested result. 3. A rediscovery of something know for decades without attribution to the source they probably read it from. 4. Incomplete description of problem, resolution, or probably fraud/incompetency. 5. Useless in general. Unverifiable, etc. 6. Review article. 7. A derivation with way more omissions/flaws than say an engineering paper. I'm somewhat seasoned on optimization methods personally, but yea it seems once people go ML they tend to um stop studying the fundamental literature that ML came from. "Online masters program learn AI in 12 weeks from nothing!". Oh okay so calculus won't be included in that... Or statistics... Or... Yep it's going to be scikit learn notebooks ...
    - commonlisp94 3y ago
      It does feel like academic outsiders hacking/taking on the brand of serious academic research to give themselves authority. > Baseless empirical result that probably was p hacked This to me seems like the biggest regression in science. It's all heresy which is very hard to re-produce or learn general lessons from. It feels like disparate social science methodologies are being used to study math. Nobody is going to look back and benefit from these papers. I often bring up to ML folks limitations proven in the book Perceptrons and wonder how their models differ. I have never gotten a response.
      - thumbuddy 3y ago
        I once tried talking about how there is probably a fundamental limit to how deep of a graph traversal chat bots can do to a colleague. And he started blankly at me and said "it'll work". As if chat bots can now solve NP complete problems with ease because "AI"... I'm so glad I left the field the level of snake oil relative to sustenance is pretty hard to stomach.
        commonlisp94 3y ago
        I have seen similar claims that computer science is wrong about complexity theory. What field did you move to?
        thumbuddy 3y ago
        Maybe we are wrong about complexity theory. I know people who have dedicated good chunks of their lives to studying it. One things for sure, if we are wrong about it, and have no basis for studying any of its exceptions, it's hard for me to accept hot takes like this as worth considering. The general "we can do ...insert currently impossible thing... Because AI!" Gets very old. Once had a boss request that light travel faster then it does- literally... "no" wasn't an acceptable answer. Anyway... I float between a few technical fields. Some in natural science, computer science, data science hybrid roles, data bases/engineering, etc. Not a jack of all trades, nor a master of none. What I do have mastered isn't something people hire for, so basically I am an averagely smart person who will take any job and figure it out to pay the bills. At home though I play with all of the areas of creation I can get my hands on. I guess I am just in the field of discovering new things and making things.
  - commonlisp94 3y ago
    > if people in machine learning ever look at literature. They don't. A few other things they seem completely unaware of: - other ways to represent functions besides neural networks (harmonic analysis, polynomials, etc) - other models exist besides neural networks. ie. if you can model the problem with a simple equation you can just optimize that. - polynomial regression. Someone who has read "numerical recipies" is probably more capable in solving ML problems than an "ML software engineer".
stabbles 3y ago
If you solve f(x) = 0 where f: ℝ^k -> ℝ^k maps vectors to vectors, most schemes are based on Taylor expansion around x_n f(x) = f(x_n) + Df(x_n)(x - x_n) + O(||x - x_n||^2) Drop the quadratic term, equate to 0, and you get an approximate solution for x for the next iteration x_{n+1}: x_{n+1} = x_n - Df(x_n)^{-1} * f(x_n) Like this it's the Newton method. The problem is that the Jacobian Df(x_n) is a matrix of size k x k, and inverting it may require O(k^3) work. So, pretty much all schemes are based on approximations of the Jacobian. Gradient descent for example replaces Df(x_n)^{-1} with a scalar a, so it's O(1) work to "compute" it: x_{n+1} = x_n - a * f(x_n) A method like L-BFGS tries to build a relatively cheap approximation to the inverse of the Jacobian during iteration, resulting in O(k) work to compute: x_{n+1} = x_n - P * f(x_n) Other methods may exploit sparsity of the Jacobian, or solve the linear system Df(x_n)z = f(x_n) only approximately for z using e.g. iterative methods. Note: in optimization problems, the function f is typically a gradient of a cost function, and the jacobian is then the hessian of that cost function.
- nerdponx 3y ago
  There's also Coordinate Descent which was traditionally used for fitting LASSO regression.
- quickthrower2 3y ago
  Gradient descent also allows batching, which reduces the memory requirements, can the other methods support that?
  - nerdponx 3y ago
    As far as I know, this is the #1 gradient descent superpower that makes it the preferred choice above all others. I don't think e.g. L-BFGS supports batching, I've certainly never seen it.
PartiallyTyped 3y ago
None really. Gradient descent is great because it is first order, thus cheap to compute since you don’t need a Hessian, points to a descent direction, works with anything that is differentiable or piece-wise differentiable without caveats, and given the millions of parameters in today’s there is always a descent direction. If you do population methods, you suffer in terms of memory because you need to keep all those candidates, evaluate them individually, and then update them. This bounds the memory you can use. More memory means more parameters, means you enter the interpolation scheme means your model behaves well in real world. If you try to go with second order optimisation methods then you need to go for Hessian free methods as computing the Hessian is computationally intractable for large NNs. You can attempt to build a local model of the loss landscape but that is expensive and has many caveats. Nocedal et al is a recommended read for numerical optimisation theory.
- imtringued 3y ago
  >More memory means more parameters, means you enter the interpolation scheme means your model behaves well in real world. The surprising thing about large neural networks is that the difference in quality between the local minima goes down and makes it less and less relevant which one you end up in. The global minimum may also lead to overfitting so you probably don't even want to go there.
  - PartiallyTyped 3y ago
    It is also the case that many of such local minima are locally identical in structure and you can jump between one another via permutations of the parameters.
    - magicalhippo 3y ago
      As a simple example, if you have a NN with one input and output neuron and a single two-neuron hidden layer (with same activation function), you can swap the weights (and bias) of the two neurons in the hidden layer and the result will be the same. Right? Is there something to gain by trying to eliminate or exploit such symmetries?
matteoraso 3y ago
If accuracy isn't as important as speed for you, you can sample 1000 points and pick the smallest one. This point will probably be smaller than 99% of the function, but I wouldn't recommend deploying this in production.

There are probably ly a hundred. Many people have asked for research into this for I don't know 20 years. But the hype doesn't die down and modern trends have mostly involved doing more GD with bigger models... A colleague and myself experimented with some alternatives and passed notes once in a while... For certain modelling problems you can save literal gpu days by going against the grain and get better results. Oh well...

deleted 3y ago
[deleted]
stabbles 3y ago
> Many people have asked for research into this for I don't know 20 years Sometimes I wonder if people in machine learning ever look at literature. Basic iteration schemes like the secant method (ok, 1-dimensional) have been known well over 3000 years. Newton's method is over 300 years old. Quasi-Newton methods (the secant method being an example) became popular in the early 1960s.
- thumbuddy 3y ago
  Most ML papers I used to read fell into a couple of categories... 1. Baseless empirical result that probably was p hacked. 2. Mostly untested result. 3. A rediscovery of something know for decades without attribution to the source they probably read it from. 4. Incomplete description of problem, resolution, or probably fraud/incompetency. 5. Useless in general. Unverifiable, etc. 6. Review article. 7. A derivation with way more omissions/flaws than say an engineering paper. I'm somewhat seasoned on optimization methods personally, but yea it seems once people go ML they tend to um stop studying the fundamental literature that ML came from. "Online masters program learn AI in 12 weeks from nothing!". Oh okay so calculus won't be included in that... Or statistics... Or... Yep it's going to be scikit learn notebooks ...
  - commonlisp94 3y ago
    It does feel like academic outsiders hacking/taking on the brand of serious academic research to give themselves authority. > Baseless empirical result that probably was p hacked This to me seems like the biggest regression in science. It's all heresy which is very hard to re-produce or learn general lessons from. It feels like disparate social science methodologies are being used to study math. Nobody is going to look back and benefit from these papers. I often bring up to ML folks limitations proven in the book Perceptrons and wonder how their models differ. I have never gotten a response.
    - thumbuddy 3y ago
      I once tried talking about how there is probably a fundamental limit to how deep of a graph traversal chat bots can do to a colleague. And he started blankly at me and said "it'll work". As if chat bots can now solve NP complete problems with ease because "AI"... I'm so glad I left the field the level of snake oil relative to sustenance is pretty hard to stomach.
      - commonlisp94 3y ago
        I have seen similar claims that computer science is wrong about complexity theory. What field did you move to?
        thumbuddy 3y ago
        Maybe we are wrong about complexity theory. I know people who have dedicated good chunks of their lives to studying it. One things for sure, if we are wrong about it, and have no basis for studying any of its exceptions, it's hard for me to accept hot takes like this as worth considering. The general "we can do ...insert currently impossible thing... Because AI!" Gets very old. Once had a boss request that light travel faster then it does- literally... "no" wasn't an acceptable answer. Anyway... I float between a few technical fields. Some in natural science, computer science, data science hybrid roles, data bases/engineering, etc. Not a jack of all trades, nor a master of none. What I do have mastered isn't something people hire for, so basically I am an averagely smart person who will take any job and figure it out to pay the bills. At home though I play with all of the areas of creation I can get my hands on. I guess I am just in the field of discovering new things and making things.
- commonlisp94 3y ago
  > if people in machine learning ever look at literature. They don't. A few other things they seem completely unaware of: - other ways to represent functions besides neural networks (harmonic analysis, polynomials, etc) - other models exist besides neural networks. ie. if you can model the problem with a simple equation you can just optimize that. - polynomial regression. Someone who has read "numerical recipies" is probably more capable in solving ML problems than an "ML software engineer".

stabbles 3y ago

If you solve f(x) = 0 where f: ℝ^k -> ℝ^k maps vectors to vectors, most schemes are based on Taylor expansion around x_n f(x) = f(x_n) + Df(x_n)(x - x_n) + O(||x - x_n||^2) Drop the quadratic term, equate to 0, and you get an approximate solution for x for the next iteration x_{n+1}: x_{n+1} = x_n - Df(x_n)^{-1} * f(x_n) Like this it's the Newton method. The problem is that the Jacobian Df(x_n) is a matrix of size k x k, and inverting it may require O(k^3) work. So, pretty much all schemes are based on approximations of the Jacobian. Gradient descent for example replaces Df(x_n)^{-1} with a scalar a, so it's O(1) work to "compute" it: x_{n+1} = x_n - a * f(x_n) A method like L-BFGS tries to build a relatively cheap approximation to the inverse of the Jacobian during iteration, resulting in O(k) work to compute: x_{n+1} = x_n - P * f(x_n) Other methods may exploit sparsity of the Jacobian, or solve the linear system Df(x_n)z = f(x_n) only approximately for z using e.g. iterative methods. Note: in optimization problems, the function f is typically a gradient of a cost function, and the jacobian is then the hessian of that cost function.

nerdponx 3y ago
There's also Coordinate Descent which was traditionally used for fitting LASSO regression.
quickthrower2 3y ago
Gradient descent also allows batching, which reduces the memory requirements, can the other methods support that?
- nerdponx 3y ago
  As far as I know, this is the #1 gradient descent superpower that makes it the preferred choice above all others. I don't think e.g. L-BFGS supports batching, I've certainly never seen it.

PartiallyTyped 3y ago

None really. Gradient descent is great because it is first order, thus cheap to compute since you don’t need a Hessian, points to a descent direction, works with anything that is differentiable or piece-wise differentiable without caveats, and given the millions of parameters in today’s there is always a descent direction. If you do population methods, you suffer in terms of memory because you need to keep all those candidates, evaluate them individually, and then update them. This bounds the memory you can use. More memory means more parameters, means you enter the interpolation scheme means your model behaves well in real world. If you try to go with second order optimisation methods then you need to go for Hessian free methods as computing the Hessian is computationally intractable for large NNs. You can attempt to build a local model of the loss landscape but that is expensive and has many caveats. Nocedal et al is a recommended read for numerical optimisation theory.

imtringued 3y ago
>More memory means more parameters, means you enter the interpolation scheme means your model behaves well in real world. The surprising thing about large neural networks is that the difference in quality between the local minima goes down and makes it less and less relevant which one you end up in. The global minimum may also lead to overfitting so you probably don't even want to go there.
- PartiallyTyped 3y ago
  It is also the case that many of such local minima are locally identical in structure and you can jump between one another via permutations of the parameters.
  - magicalhippo 3y ago
    As a simple example, if you have a NN with one input and output neuron and a single two-neuron hidden layer (with same activation function), you can swap the weights (and bias) of the two neurons in the hidden layer and the result will be the same. Right? Is there something to gain by trying to eliminate or exploit such symmetries?

matteoraso 3y ago

If accuracy isn't as important as speed for you, you can sample 1000 points and pick the smallest one. This point will probably be smaller than 99% of the function, but I wouldn't recommend deploying this in production.