Convexity Lipschitzness Smoothness

What do these terms imply? How can they be used in the context of Machine Learning?

This article is motivated by the chapter on Convex Learning Problems in the book Understanding Machine Learning: From Theory To Algorithms (Shalev-Shwartz and Ben-David 2014). Convexity, Lipschitzness and Smoothness are some of the most recurring topics in Machine Learning Research today. This article aims to provide an overview of the theory and some of their most interesting applications.

Convexity

Lipschitzness

Lipschitz Continuous

Theorem

A function \(f : I \rightarrow \mathbb{R}\) over some set \(I \subseteq \mathbb{R}\) is called Lipschitz-continuous if there exists some \(L \geq 0\) such that

\[ |f(x)\ -\ f(y)| \leq L (x\ -\ y) \]

where, \(x,\ y\ \epsilon\ I\)

If such a constant \(L\) exists, then we call \(L\) as the Lipschitz Constant of \(f\) over \(I\).

Equivalently, \(f\) is Lipschitz continuous is there exists \(L \geq 0\) such that

\[ \frac{|f(x)\ -\ f(y)|}{x\ -\ y} \leq L \]

where, \(x,\ y\ \epsilon\ I,\ x\ \neq\ y\)

Lemma

A function \(f\ :\ I\ \rightarrow \ \mathbb{R}\) is Lipschitz-continuous with Lipschitz-constant \(L\) if and only if \[ f(x)\ -\ L |x\ -\ y|\ \leq \ f(y) \ \leq \ f(x) \ + \ L |x\ -\ y| \]

Proof

If \(f\) if Lipschitz-constinuous with constant \(L\) then,

\[ |f(x)\ -\ f(y)| \leq L (x\ -\ y) \]

On resolving the modulus we can get two equations.

The first one, \[f(x)\ -\ f(y) \leq L (x\ -\ y)\] which equivalently is \[f(x)\ -\ L |x\ -\ y|\ \leq \ f(y)\]

and the second one, \[f(y)\ -\ f(x) \leq L (x\ -\ y)\] which is \[f(y)\ \leq \ f(x) +\ L |x\ -\ y|\]

Smoothness

Shalev-Shwartz, S., and Shai Ben-David. 2014. “Understanding Machine Learning - from Theory to Algorithms.” In.