Reference request: importance of Lipschitz continuity I see that Lipschitz continuity is a common assumption used in optimisation, statistics, machine learning, etc.
Could you point me in the direction of some literature that discusses why Lipschitz continuity is commonly assumed? Does it naturally occur in applications? Contains an important class of functions?
EDIT: I’ve found that it’s central for ODEs because of Picard-Lindelöf theorem but I’d like to have something closer to statistics or optimization.
 A: In Mathematical/High Dimensional Statistics:
One fairly amazing result is for $X=(X_1,\dots,X_n)$ where the coordinates are i.i.d. standard Gaussians, and $f:R^n \to R$ a $L$-Lipschitz function (w.r.t. Euclidean norm), then the random variable $f(X) - E[f(X)]$ is sub-Gaussian with sub-Gaussian norm $L$, i.e. it satisfies for any $\epsilon \ge 0$:
$$
P(|f(X)- E[f(X)]| \ge \epsilon) \le 2 e^{-\epsilon^2/2 L^2}.
$$
It is somewhat surprising (to me at least) how often this result comes in handy - particularly when working with rademacher/gaussian complexities in mathematical statistics/learning theory and also in random matrix analysis.
To give one concrete example, if $X$ is a $n \times p$ random matrix with i.i.d. standard gaussian entries, and $Y$ is another matrix, then by Weyl's inequality:
$$
\max_{k=1,\dots, p} |\sigma_k(X) - \sigma_k(Y)| \le \|X-Y \|_F,
$$
where $\sigma_k$ is the $k$-th largest singular value. This tells us that the $k$-th singular value is a 1-Lipschitz function of the matrix, and so we immediately get
$$
P(|\sigma_k(X) - E[\sigma_k(X)]| \ge \epsilon) \le 2e^{-\epsilon^2/2}.
$$
I would suggest the following two books for more on this kind of usage of Lipschitz continuity:

*

*High Dimensional Statistics - A non-asymptotic viewpoint by Martin J Wainwright

*High Dimensional Probability by Roman Vershynin

In machine learning:
The concept of Lipschitz continuity is also important in the current machine/deep learning literature where model robustness (which they refer to as adversarial robustness) is an important issue. To understand the robustness of a complicated model (such as a neural network), a lot of work has gone into training networks that define an input-output map with small Lipschitz constant. The intuition here is that if my model is robust, it should not be too affected by perturbations in the input, $f(x+\delta x) \approx f(x)$, and this would be ensured by having $f$ be L-Lipschitz where $L$ is small. See this paper Training robust neural networks using Lipschitz bounds and their references for more on this.
A: Here is my two cents: In (unconstrained continuous) optimization you want to find minima of functions and in the differentiable case these have vanishing gradient. (In the convex case, vanishing gradient is sufficient for minimizers, in the nonconvex case, one often just aims for critical points anyway.) But in computational optimization, you'll will only every have approximations and you would like to know how good of an approximation you have. So for the minimization of a function $f$ you would like to have a bound on $f(x) -\inf f$ for some trial point $x$. But usually you don't know $\inf f$. Then you could aim for $\| \nabla f\|$ being small. But how can you know how good you are if you only know the magnitude of the gradient? You can't, unless you know a little something quantitatively about your function, and this little something is Lipschitz continuity of the gradient of $f$. I find the book "Introductory Lectures on Convex Optimization" by Nesterov very enlightening in this regard.
A: The local Lipschitz continuity condition is standard in nonsmooth, nonconvex optimization -- see e.g. this paper and Sections "Nonsmooth, Nonconvex Optimization" and "The Clarke Subdifferential" in these lecture notes.
The Lipschitz continuity condition is also used in stochastic convex optimization problems -- see e.g. this paper.
The Lipschitz continuity condition plays important roles in stochastic differential equations, isoperimetric inequalities, and optimal mass transportation theory.
A: I would also suggest Dembo and Zeitouni for basic large deviations theory. Lipschitz continuity is a good condition to obtain results such as Varadhan's lemma, although there are weaker hypotheses, too.
A: My two cents. Despite being a bit far away from the main theme of the question (statistics and optimization), from the point of view of PDEs I think that a particularly illuminating reference on the importance of Lipschitz/Hölder functions is the recent book of Fiorenza [1]. In this context, the Lipschitz/Hölder continuity requirement is the classical means to control e.g. the behavior of the inner normal vector to a Lyapunov manifold (i.e. a manifold whose representing function is locally Hölder continuous), obtain several classical results on the solvability of boundary value problems for elliptic equations and analyzing the behavior of potentials across a (hyper)surface discontinuity (the classical Plemelj formula is proved assuming Lipschtz continuity of the boundary value of the given harmonic function).
Reference
[1] Renato Fiorenza, Hölder and locally Hölder continuous functions, and open sets of class $C^k$, $C^{k,\lambda}$ (English), Frontiers in Mathematics, Basel: Birkhäuser/Springer (ISBN 978-3-319-47939-2/pbk; 978-3-319-47940-8/ebook), pp. xi+152 (2016), MR3588287, Zbl 1366.26003.
