primer

We are interested in 3 key properties of functions:

1. Lipschitzness

Defn: L-Lipschitz

A function $F : R^{p} \to R$ is said to be $L$ -Lipschitz if $\forall x, y \in R^{p}$ $$|F(x) - F(y)| \leq L \Vert x - y \Vert$$

Example: $F (x) = x$ is 1-Lipschitz while $F (x) = x^{2}$ is not Lipschitz

2. Convexity

Defn: Convexity

A function $F : R^{p} \to R$ is said to be convex if $\forall x, y \in R^{p}$ and $\forall θ \in [0, 1]$ $$F(\theta x + (1-x)y) \leq \theta F(x) + (1-\theta)F(y)$$A function is said to be strictly convex if the above inequality holds in the strict sense.

Defn: Convexity

An at least once differentiable function $F : R^{p} \to R$ is convex if $\forall x, y \in R^{p}$ $$F(x) + \nabla F(x)^{\top}(y-x) \leq F(y)$$

A differentiable convex function can be thought of as having the property that for any point $x$ in the domain, the tangent to the function at that point is below the graph of the function

Defn:

α

-Strong Convexity

For some $α > 0$ , a function $F : R^{p} \to R$ is said to be $α$ -strongly convex if we have that $F (x) - \frac{α}{2} ‖ x ‖^{2}$ is a convex function

This definition captures the intuition of having a convex function be lower-bounded by paraboloid.
This also provides a simply mechanism for generating examples of strongly convex functions since adding $\frac{α}{2} ‖ x ‖^{2}$ to a convex function yields a $α$ -strongly convex function.

Defn:

α

-Strong Convexity

An at least once differentiable function $F : R^{p} \to R$ is said to be $α$ -strongly convex if for some $α > 0, (x, y) \in R^{p}$ we have$$F(y) \geq F(x) + \nabla F(x)^{\top}(y-x) + \frac{\alpha}{2} \cdot \Vert y - x \Vert^2$$

3. Smoothness

Defn: Lipschitz-Smoothness (

β

-Smooth or

β

- Lipschitz Smooth or

β

-Gradient Smooth)

For some $β > 0$ and an at least once differentiable function $F : R^{p} \to R$ its gradients should be $β$ -Lipschitz i.e. $\forall x, y$ $$\Vert \nabla F(x) - \nabla F(y) \Vert \leq \beta \Vert x - y \Vert$$

Example: $F (x) = x^{2}$ is smooth with $β = 2$