How to Escape Saddle Points Efficiently
bair.berkeley.edu
How to Escape Saddle Points Efficiently
1–10 of 39 posts
Re: How to Escape Saddle Points Efficiently
#2It's interesting, I once tried injecting perturbations for a short period selectively when the norm of the gradient was near zero, and it gave me consistent improvement.
Re: How to Escape Saddle Points Efficiently
#3It's interesting, I once tried injecting perturbations for a short period selectively when the norm of the gradient was near zero, and it gave me consistent improvement.
It seems like it would add similar behaviour to simulated annealing. I wonder how this applies to SGD or batch gradient descent, which is commonly used in machine learning applications. Something to try on a toy dataset like MNIST :)
Re: How to Escape Saddle Points Efficiently
#4I'm not an AI expert, but I'm decent with computers. Could anyone explain what is this about?
Re: How to Escape Saddle Points Efficiently
#5Many nonconvex problems are solved with more sophisticated methods, like L-BFGS. Are perturbations still a good thing?
Re: How to Escape Saddle Points Efficiently
#6> Our sharp rate depends on a key observation — although we don’t know the shape of the stuck region, we know it is very thin.
Oh... really? :)
(After 12 years I finally get an excuse to show a fun side project I coauthored during my PhD...)
http://graemebell.net/pubs/taros05-bl-embedded-preprint.pdf
Check out Figure 5 / Section 3.4
The rest of the paper is an introduction to why saddle points can be surprisingly problematic for people using potential fields (neural nets, game/robot navigation). Hope someone finds it interesting.
Re: How to Escape Saddle Points Efficiently
#7It's interesting, I once tried injecting perturbations for a short period selectively when the norm of the gradient was near zero, and it gave me consistent improvement.
How do you select the average size/standard deviation of your perturbations? Too small and you get no benefit, or very little speed up, too large and you lose the ability to sensibly optimise, and if you attempt to make an adaptive function then you'll find yourself with another postdoc.
Re: How to Escape Saddle Points Efficiently
#8I'm not an AI expert, but I'm decent with computers. Could anyone explain what is this about?
Assuming you want to understand a bit more about saddle points:
http://graemebell.net/pubs/taros05-bl-embedded-preprint.pdf
Section 3 has some low dimensional examples with simulated robots and donkeys.
Take a look at Figure 3 with the donkey.
Burridan's Ass is a classic philosophical example where a saddle point prevents success.
Basically, place a donkey between two piles of food in front of it that are equally attractive. The donkey moves in whatever direction will take it towards food.
So at first, it can move forward (reducing its distance to both piles of food) up to a point, but then it gets stuck because both piles are equally attractive. It can't move forward or back either because that moves it away from both piles of food.
There is nothing to 'push' the donkey to the left or the right.
('push'/hunger being analogous to 'following the gradient' for neural net training or robot navigation here)
If you add a bit of a random wobble, it's enough to free the donkey from its indecision and make one of the piles slightly closer.
But things are more complex than that especially as you move into higher-dimensions of space beyond 2D and 3D [as you see when training neural nets, for example].
And a random wobble is not enough to guarantee success. It may have consequences for physical devices (your robot shakes around and falls over), it may have consequences for realism and immersion in games/simulations (the AI monster stops and does a mad shake for a minute to creep its way around a rock to get you, rather than moving smoothly/normally around the rock)
Re: How to Escape Saddle Points Efficiently
#9I'm not an AI expert, but I'm decent with computers. Could anyone explain what is this about?
I'm not an AI expert either, but let me give this a try.
I assume you are vaguely familiar with gradient descent. In gradient descent, we are basically trying to find the sweet spot where the value of a function is minimized. We do this by calculating the derivative of the function at a certain point and then use it to take small steps in the direction where we believe the function will have a lower value.
Gradient descent usually suffers from a problem where the algorithm gets stuck in local minimas if the function is not convex in shape.
However, when people use gradient descent to optimize functions with a very large number of parameters (as is the case in Deep Learning), another problem surfaces called saddle points. Imagine a 3 dimensional plot of the function at different values of its parameters (in reality the plot will be multi-dimensional). Now on this plot, there will be many regions where the derivative of the components defining the surface become zero. This messes with our plan to use derivatives to find the direction in which to move. So we need to come up with strategies to escape saddle points during the gradient descent process.
Re: How to Escape Saddle Points Efficiently
#10It's interesting, I once tried injecting perturbations for a short period selectively when the norm of the gradient was near zero, and it gave me consistent improvement.
That's generally helpful and usually enough, but it's not universally helpful, depending on the shape of the problem and your step size - see Figure 5 below.
(http://graemebell.net/pubs/taros05-bl-embedded-preprint.pdf)
It also depends what the impact of 'perturbations' is in the real world.
Random juddering motions can be bad for physical platforms like robots, spacecraft.
[I once saw a conference presentation where people were encountering saddle point problems when automatically aligning groups tiny space craft in space]
In computer games, random perturbations can make movement look strange, unrealistic or creepy.