4 ms·

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

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.

unityByFreedom 9y ago
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 https://youtu.be/V2h3IOBDvrA?t=26m5s
whatidonteven 9y ago
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)?
- blt 9y ago
  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.
- wenc 9y ago
  > 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 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.
  - posterboy 9y ago
    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).
  - whatidonteven 9y ago
    Ah, gotcha, so it's not the graph of the function that convexity refers to but the volume above the graph of the function.
    - wenc 9y ago
      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) 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.

unityByFreedom 9y ago

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 https://youtu.be/V2h3IOBDvrA?t=26m5s

whatidonteven 9y ago

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

blt 9y ago
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.
wenc 9y ago
> 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 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.
- posterboy 9y ago
  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).
- whatidonteven 9y ago
  Ah, gotcha, so it's not the graph of the function that convexity refers to but the volume above the graph of the function.
  - wenc 9y ago
    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) 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.