---- Let $(X, d_{X})$ and $(Y, d_{Y})$ be [[metric space|metric spaces]]. > [!definition] Definition. ([[Lipschitz continuous]]) > A function $f: X \to Y$ is called **Lipschitz continuous** if there exists a constant $L \geq 0$ s.t. $d_{Y}\big(f (x_{1}), f(x_{2}) \big) \leq L \ d_{X}(x_{1},x_{2}).$ > $L$ is called the **Lipschitz constant** of $f$. If $L \leq 1$ we say that $f$ is **nonexpansive**; if $L=1$ we say $f$ is an **isometry**. > [!intuition] > Intuitively, Lipschitz continuity implies a high level of 'regularity' in a function: e.g., for $X=Y=\mathbb{R}$ with standard [[metric]] and $x_{1} \neq x_{2}$ we are saying that the rise/run magnitude (secant line slope) $\frac{|f(x_{2})-f(x_{1})|}{|x_{2}-x_{1}|}$ never exceeds $L$. It is a stronger statement than [[uniformly continuous|uniform continuity]], and a *much* stronger statement than [[continuity]]. > [!basicexample] > - The [[rectified linear unit|ReLU]] function $f(x)=\max(x,0)$ is **Lipschitz continuous** with constant $1$. Note that it's not [[derivative|differentiable]]. ![[CleanShot 2023-11-21 at 15.40.08.jpg]] The [[gradient|gradient]] of the [[least squares]] [[objective function|cost function]] is [[Lipschitz continuous]], for $\begin{align} \|\nabla f(x)- \nabla f(z) \|_{2} = & \|A'(Ax-y) - A'(Az-y)\|_2 \\ = & \|A'A(x-z)\|_{2} \leq \|A'A\|_{2} \|x-z\|_{2} \end{align}$ where $\|A'A\|_{2}=\|A\|_{2}^{2}$ , the squared [[spectral matrix norm]] $\sigma_{1}^{2}(A)=\rho(A'A)$ of $A$, is the Lipschitz constant. (In fact, it is the best such.) > [!basicnonexample] > - The [[least squares]] [[objective function|cost function]] $f(\b x)=\frac{1}{2}\|A\b x-\b y\|_{2}^{2}$ is not generally [[Lipschitz continuous]]. As a counterexample, let $A=1$ and $y=0$, then you've just got $f(x)=\frac{1}{2}x^{2}$. (Its [[gradient|gradient]] is [[Lipschitz continuous]], however.) ---- #### ![[Lipschitz continuity visualization.gif]] ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```