How to Escape Saddle Points Efficiently | Hacker News Reader

How to Escape Saddle Points Efficiently

bair.berkeley.edu

144 pointsmfagio38 comments

> 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.

These results seem important for nonconvex optimization in general, but for ML applications where we usually use stochastic/batch gradient descent, I wonder if the the stochasticity adds enough perturbation for this to not really be that useful.

Well, in general, no, there is no perturbation method large (or good) enough to get out of saddle points, including via stochastic gradient descent. It might work in a particularly specific problem, but not in general.

Fine, but I mostly care about ML applications, where I'm wondering if this is expected to help at all.

ML is far too broad a category. Like I said, it will depend on the problem/function.

How does what you say agree/disagree with the authors paper?

The authors bound derivatives and 2nd derivatives, which excludes particularly nasty functions?

Put a shell programmer in the saddle point, and give him or her half a dozen backslashes; he or she will figure out how to escape in no time.

It'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 :)

How about ImageNet and CIFAR? :)

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.

You could probably let the schedule of the perturbations be a sequence ε→0, such that ∑ε = ∞, and such that ∑ηε < ∞ with probability 1, where η is IID, bernoulli on {-1, 1} (e.g. a square-summable sequence will do). I suspect this will be a fairly good start.

Note that, then it should in general be independent of the chosen parameter, since the added noise converges in probability to a constant whenever the distribution is close to uniform, but can sum to any real value with consistent bias.

It's a scheduled hyperparameter like the learning rate. All my scalar/non-architectural hyperparameters are optimized using DQNs.

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.

I should clarify that this is in the context of deep learning optimization (training) only.

Many nonconvex problems are solved with more sophisticated methods, like L-BFGS. Are perturbations still a good thing?

Such methods are usually not practical for deep learning

That is true, but I got the impression from the article that they had a wider range of problems in mind.

There's quite a bit of literature on putting quasi-newton methods like BFGS in an online setting, but I've never actually seen anyone use them except in the papers that present them. Maybe a few theoreticals are still being settled or maybe no one has written a robust piece of software for the folks who aren't optimization experts?

Jorge Nocedal begs to differ: http://users.iems.northwestern.edu/~nocedal/publications.htm...

> This leads to a discussion about the next generation of optimization methods for large-scale machine learning, including an investigation of two main streams of research on techniques that diminish noise in the stochastic directions and methods that make use of second-order derivative approximations.

Disclosure: I was his student for a while and in his lab for my whole PhD. My takeaway from studying under him was that even very very approximate hessian information (either the Hessian itself or the solves) is enough for pretty amazing convergence rates, in terms of flops / time.

I'm getting stuck trying to understand the equations in assumptions 1 and 2. Can anyone point me to a resource that explains the idea behind them? Wikipedia is a bit terse, and I'm not having any luck googling for "gradient-lipschitz and hessian-lipschitz" and variations.

On the notation side, am I correct in thinking that "<del>f(x_n) is the partial derivative w.r.t. x_n? And that the elements of the vector x are the parameters against which a "cost function" (f) is computed? But that doesn't seem right. Maybe x_n is a point in R^N, and therefore <del>f(x_n) is the derivative at that point?

∇f(x_1) is the gradient of f evaluated at x_1, a point in R^N.

The first equation indicates that for any two points in R^N, the maximum norm of the difference in gradient is less than a constant times the distance between the points.

The keyword to google for is just "Lipschitz".

Ok. I stared at it long enough, and I think I understand. Being Lipschitz-continuous means (in a non-rigorous way?) that a the gradient / slope of a function has an upper bound. And Hessian-Lipschitz means the same, but for the second derivative / hessian.

So, f(x) = x^2 is not Lipschitz-continuous (because the slope gets arbitrarily large), but something like f(x) = sin(x) is Lipschitz-continuous because the slope never exceeds some upper bound.

Funny how trying to write down the question gives the brain the kick it needs sometimes :)

That's correct.

In some situations, it's enough to prove an equation is Lipschitz-continuous on a range. Example, y=x^2 is lipschitz continuous on x=[0,1].

For assumption 1:

For every two points, the norm of the gradient is bounded by some constant times the absolute values/normed values between the two points. So the slope is bounded.

For assumption 2:

Same as assumption one, but true for the the second derivative to. So the change in slope (acceleration) is bounded. So no starts, no stops.

Has anyone experimented with other optimization techniques like particle swarm optimization? Usually this technique is inefficient but one could adaptively kick off extra particles into the swarm as the gradient starts levelling off, and the direction of more optimal particles could be used to inform the gradient, moving forward.

I'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)

> There is nothing to 'push' the donkey to the left or the right.

It's funny -- I can imagine a real human (perhaps a particularly anxious one) stall in indecision wondering which similar-looking pile held more value or which was closer. Fear of wasted time would likely force them to make a decision. And once they committed to a pile they would likely continue until/unless they discovered new information.

What if the agent had a list of waypoints and only re-evaluated the list every N ticks or when the horizon reveals something new?

I know very little about AI so I have no idea if this is out of scope or could possibly apply.

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.

Here's a section from the fast.ai course where Jeremy discusses learning rates and saddle points (about 2-3 minutes in)

https://youtu.be/V2h3IOBDvrA?t=26m5s

How can a non-linear function even be convex in shape? I assume you mean the whole volume below or above the function and not just the function's surface itself?

Also, what about the case where the function isn't continuous or where it's not defined everywhere (the surface has holes)?

one definition of a convex function is that its epigraph

    { (x, y) : f(x) <= y }

is a convex set. Another is that the line segment between two points on the graph lies above the graph, i.e.

    (1 - t) f(x) + t f(y) >= f((1 - t) x + t y) for all 0 <= t <= 1

known as Jensen's inequality.

Convex function must be defined on a convex domain (no holes) and continuous at everywhere except the boundary of the domain.

> How can a non-linear function even be convex in shape?

I'm not sure what you mean. Apart from the linear case (which is weakly convex), most convex functions are non-linear. So yes, it is not only possible, it is the norm (in a colloquial sense). Refer to this for a mathematical definition of convexity: https://en.wikipedia.org/wiki/Convex_function

> Also, what about the case where the function isn't continuous or where it's not defined everywhere (the surface has holes)?

There are two different cases:

1) Discontinuous functions: these are by definition nonconvex e.g. step functions. Gradient-descent methods cannot handle these directly; typically they are modeled as mixed-integer problems.

2) Non-smooth functions: are convex but do not have derivatives defined everywhere. e.g. abs(x). Gradient-descent methods don't work well on these types of functions. These typically require subgradient/bundle methods, or can be modeled as discontinuous functions.

yes, it's not smooth by definition

   d/dx √(x²) = x/√(x²)

because for x=0 the derivative is 0/0, but in this case it might be interpreted as the interval [-1,1]. That's just the way it is often plotted. I come up short with an algebraic explanation, it might as well be ]-∞,∞[ (deriving it from z(x,y)=1/y for example), but I imagine this as a bundle of tangents on the origin, parameterized by the interval. That's an infinitesimal curve, not just an infinitesimal slope if you will. So it's not linear algebra (I guess). The integral of the derivative is obviously defined everywhere, explain that. It's zero at zero, because the sum of the interval is zero. And if we are only interested in the boundaries of the interval at 0, than that's the tuple (-1,1). Just like complex numbers or vectors are tuples (but this isn't a complex number I guess).

Ah, gotcha, so it's not the graph of the function that convexity refers to but the volume above the graph of the function.

Well, no, in this scenario, it is actually the function (in your words, the graph of the function) that is convex. A 2D example would be y = x^2 (a parabola), which is a convex function. A 3D example would be a paraboloid function, which is also a convex function.

The "volume" (or "area" in the 2D case) above the graph is called an epigraph.

One property of convex functions is that their epigraphs are convex sets (note the word "sets" this time). https://en.wikipedia.org/wiki/Epigraph_(mathematics)

Convex sets are more abstract in meaning, but in general in means can draw a straight-line between any two points in the region without going outside of the region.

Perhaps your notion of convexity comes from a mental idea of the shapes of convex and concave lenses? Those are good visualizations but in mathematics, convexity has a subtler, more rigorous meaning. With this rigorous meaning comes many nice mathematical properties that make optimizing them easier than nonconvex functions.

You're in the middle of a saddle shape (see the figure [1]). This is bad because you could be lower (the goal is to be at the lowest point). Moreover, getting out is apparently slow / difficult. The authors explain "how to escape" the saddle point in an efficient way.

[1]: http://bair.berkeley.edu/blog/assets/saddle_eff/strictsaddle...

Reply on news.ycombinator.com