Let us consider a convex funtion as shown in the figure below:
Consider two points and with corresponding values of and as shown in the
above figure. The blue curve between and in the above figure represent the left hand
side of equation . The red curve connecting with represents the right hand side of equation . Then, in this simple
scenario, equation can be interpreted as, “a function is convex
if, for every pair , the blue curve between and is below the red line.”
From ,
Taking limit on both sides, we get,
where, is directional derivative.
The Taylor series expansion of is given by,
Taking limit on both sides, we get,
From equation and ,
Thus, if is differentiable, and its gradients exists for all ,
then,
Let us continue with our running example of and try to decipher the meaning of equation through the figure below:
If we make the gradient point towards the same direction as , then we obtain the green arrow in
the above figure. According to equation , “for a function to
be convex, such green arrow at must be below the red line.”
Alpha-Strongly Convex Function
A function is said to be -strongly convex if,
Beta-Smooth Function
A function is said to be -smooth if,
The above condition is equivalent to the Lipschitz condition over gradients,
The equations and are also equivalent with,
Proof of :
From , we have,
Multiplying both sides by , we get,
From Cauchy-Schwarz inequality, we have,
From equation and , we get,
Equation can be written as,
The Taylor expansion of a function about a point is given by,
From equation , we have,
From equation and , we get,
Subtracting equation from , we get,
Let
and
Then, becomes,
and, becomes,
Solving equation and , we get,
From equation ,
Interchanging and , we get,
And this concludes our proof of .
Proof of :
To prove , we can rewrite as,
Then, again using Cauchy-Schwarz inequality as before,
