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

31–39 of 39 posts

Re: How to Escape Saddle Points Efficiently

#31

Post by Choco31415 »

T_D_K wrote: post #24
andars wrote: post #23

Earlier quoted context omitted.

∇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 n…

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

Re: How to Escape Saddle Points Efficiently

#32

Post by deepnotderp »

ovi256 wrote: post #3
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.

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

Re: How to Escape Saddle Points Efficiently

#33

Post by deepnotderp »

cool_username wrote: post #10
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.

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

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

Re: How to Escape Saddle Points Efficiently

#34

Post by wyldfire »

cool_username wrote: post #8
Demiurge wrote: post #4

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

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

Re: How to Escape Saddle Points Efficiently

#35

Post by dnautics »

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.

Re: How to Escape Saddle Points Efficiently

#36

Post by posterboy »

wenc wrote: post #29
whatidonteven wrote: post #22

Earlier quoted context omitted.

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…

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

Re: How to Escape Saddle Points Efficiently

#37

Post by traviscj »

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

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.

Re: How to Escape Saddle Points Efficiently

#38

Post by whatidonteven »

wenc wrote: post #29
whatidonteven wrote: post #22

Earlier quoted context omitted.

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…

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

Re: How to Escape Saddle Points Efficiently

#39

Post by wenc »

whatidonteven wrote: post #38
wenc wrote: post #29

Earlier quoted context omitted.

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

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.

Post reply on HN