1-Convex Sets and Functions (Modern Optimization Techniques)
To begin with understanding what is convexity truely mean is crucial. Convexity is a measure of the curvature and due to is curvature we can define two different concepts in convexity which are convex sets and convex functions.
A set is a convex set
If we can draw a line segment between any two points in the set and all points on that line segment are within that set.
How we can make non convex set into convex set ?
Let me introduce you something called convex hull. To just basically clarify what Convex Hull is the smallest convex set that contains it.
Okayyy Heliya where do we use Convex Hull in real-life senario ??
Assume that I would like to make a hand recognition system and as I can see that between my fingers I have some gaps… If a line pass between my fingers it is empty right so it is not convex.
So I should think my hand as a convex hull!
A function is a convex function
Its domain is a convex set and it is always below its secant segments.
There are 3 ways to find a function is said to be a convex :
(i) Jenson’s Inequality
𝒇(𝜽𝒙 + (𝟏 − 𝜽)𝒚) ≤ 𝜽𝒇(𝒙) + (𝟏 − 𝜽)𝒇(𝒚)
Jenson’s Inequality represents the condition that a convex function is always below its secant segments, where secant segments or chords are lines connecting two points in the function domain.
(ii) First-order Condition:
𝒇(𝒚) ≥ 𝒇(𝒙) + (𝛁𝒙𝒇(𝒙)) 𝑻 (𝒚 − 𝒙)
First-order Condition described above means that a convex function is above all of its tangents.
(iii) Second-order Condition:
f 𝛁𝒙 𝟐 ≥ 𝟎 For function belonging to a single dimension, this means that the second derivative is positive i.e. 𝑓 ´´(𝑥) ≥ 0
However, for multi-dimensional domains, this means that the Hessian f𝛁𝒙 𝟐 is positive semidefinite.
Why convexity is important in machine learning ?
In machine learning, we always want to minimize our objective function, which is a loss function. Convex functions are important in optimization because local minima of a convex function is also a global minima. Therefore, once we find a local minima, our minimization problem is solved and we have found minimum loss.
And let’s briefly talk about types of convexity and how we can find them.
Answer is super super easy look at the Hessian of that function and calculate it’s determinant!!!
- Convex
A function is convex if the function is differentiable it is domain we take the first order derivative (gradient) and equal to zero and we find the points where tangent is 0.
Also afunction is convex if the determinant of Hessian (second order derivative) of that function is ≥ 0(semi-positive definite)
Note: Before checking determinant in hessian all number should be ≥ 0 if we want to find convexity
Example: 𝒇𝟏:𝑹 → 𝑹 + 𝒇𝟏 (𝒙) = 𝒆.𝒂𝒙 and 𝒂 𝝐 R
𝑓1 ´ (𝑥) = 𝑎. 𝑒 𝑎𝑥
𝑓1 ´´(𝑥) = 𝑎. 𝑎. 𝑒 𝑎𝑥 = 𝑎 2𝑒 𝑎𝑥 > 0
Since, both the square and exponential will always be positive for any real number a, second-order condition holds and the function is convex.
2. Strictly Convex
A function is strictly convex if the determinant Hessian (second order derivative) of that function is > 0 (positive definite)
Before checking determinant in hessian all number should be >0 if we want to find strict convexity.
3. Strongly Convex
A function is stongly convex if the determinant Hessian (second order derivative) of that function is ≥ mA (m is some tzpe of coefficient it will be clear in the below example dont worry :) )
Example: f(x) = x² and x 𝝐 R
If we compute it’s Hessian it is 2.
Lets assume our function is 3x²
If we compute it’s Hessian it is 6.
As you can see the coeffienct change the Hessian magnitude is also changing by it is coefficient (m). So we can say that function of x² is strongly convex.
References:
1-http://www.gtmath.com/2016/03/
3-https://math.stackexchange.com/questions/1518550/geometric-interpretation-of-first-order-condition
