Lipschitz: Nonlinear Function
Created:
Modified:

Lipschitz

This page is from my personal notes, and has not been specifically reviewed for public consumption. It might be incomplete, wrong, outdated, or stupid. Caveat lector.

A function ff is LL-Lipschitz continuous if changing the input by a little bit can't change the output by more than a proportional amount,

f(x)f(y)Lxy\|f(x) - f(y)\| \le L \|x - y\|

for all x,yx, y in its domain. In particular, choosing y=x+ϵy = x + \epsilon implies that the gradient f(x)\| \nabla f(x) \| is bounded by LL, but the definition doesn't require that ff be differentiable.

Sometimes people talk about "Lipschitz smoothness" or an "LL-smooth" function to mean a function whose gradient is Lipschitz continuous with constant LL. Interestingly, a function is Lipschitz smooth if its convex dual is strongly convex (see, e.g., https://xingyuzhou.org/blog/notes/Lipschitz-gradient).