Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to Escape Saddle Points Efficiently

bair.berkeley.edu

Post reply on HN
Print view View original

21–30 of 39 posts

Re: How to Escape Saddle Points Efficiently

#21

Post by T_D_K »

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 "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 f(x_n) is the derivative at that point?

Re: How to Escape Saddle Points Efficiently

#22

Post by whatidonteven »

sumitgt wrote: post #9
Demiurge wrote: post #4

I'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 d…

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)?

Re: How to Escape Saddle Points Efficiently

#23

Post by andars »

T_D_K wrote: post #21

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 " f(x_n) is the partial derivative w.r.t. x_n? And that the elements of the vector x are the pa…

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

Re: How to Escape Saddle Points Efficiently

#24

Post by T_D_K »

andars wrote: post #23
T_D_K wrote: post #21

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 " f(x_n) is the partial derivative w.r.t. x_n? And that the elements of the vector x are the pa…

∇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 :)

Re: How to Escape Saddle Points Efficiently

#25

Post by tomrod »

T_D_K wrote: post #21

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 " f(x_n) is the partial derivative w.r.t. x_n? And that the elements of the vector x are the pa…

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.

Re: How to Escape Saddle Points Efficiently

#26

Post by robrenaud »

Cacti wrote: post #17
Eridrus wrote: post #15

Earlier quoted context omitted.

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?

Re: How to Escape Saddle Points Efficiently

#27

Post by blt »

whatidonteven wrote: post #22
sumitgt wrote: post #9

Earlier quoted context omitted.

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 d…

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

Re: How to Escape Saddle Points Efficiently

#28

Post by chestervonwinch »

andbberger wrote: post #12
petters wrote: post #5

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

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?

Re: How to Escape Saddle Points Efficiently

#29

Post by wenc »

whatidonteven wrote: post #22
sumitgt wrote: post #9

Earlier quoted context omitted.

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 d…

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)?

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

Re: How to Escape Saddle Points Efficiently

#30

Post by deepnotderp »

AndrewOMartin wrote: post #7
deepnotderp wrote: post #2

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.

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.

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