# Confirmation: The Lipschitz constant of gradient of $f(z):= \frac{1}{2}\|y - z\|_2^2$ is 1. Right?

Sorry for the silly question. I just wanted to confirm whether the

Lipschitz constant of gradient of $$f(z):= \frac{1}{2}\|y - z\|_2^2$$ over $$\mathbb{R}^n$$ is 1, isn't it?

The definition of Lipschitz continuous gradient is \begin{align} \| \nabla f(z_1) - \nabla f(z_2)\|_2 \leq L \|z_1 - z_2\|_2 \quad \forall z_1, z_2 \in \mathbb{R}^n. \end{align}

The gradient of $$f(z)$$ is $$\nabla f(z) = -(y-z)$$. So, plugging this in the above definition, \begin{align} & \| \underbrace{\nabla f(z_1)}_{-y+z_1} - \underbrace{\nabla f(z_2)}_{-y+z_2}\|_2 \leq L \|z_1 - z_2\|_2 \\ \Longleftrightarrow & \| z_1 - z_2 \| \leq L \|z_1 - z_2 \| \quad \Rightarrow \quad L \geq 1. \end{align}

ADD: Of course $$L$$ may depend on the considered norm. I have assumed L2 norm though.

• Since $\nabla f(x) = x-y$, then $\| \nabla f(x_1) - \nabla f(x_2) \| \le \|x_1-x_2\|$. – copper.hat Jul 10 '19 at 16:56

Certainly $$\nabla f$$ is non-expansive, by the argument provided. The argument doesn't quite rule out the possibility of some $$L < 1$$ also satisfying the condition (though it comes very close to concluding this), so the Lipschitz constant can only be concluded to be less than or equal to $$1$$.

To show the Lipschitz constant is indeed $$1$$, consider $$z_1 = (1, 0) + y$$ and $$z_2 = y$$. Then, for any eligible $$L$$, $$\|\nabla f(z_1) - \nabla(z_2)\| \le L\|z_1 - z_2\| \implies \|(1, 0) \| \le L\|(1, 0)\| \implies L \ge 1.$$ Thus the Lipschitz constant is $$1$$.

• Sorry, I am new to all this. Apologies for asking stupid question. You are saying "..Lipschitz constant can only be concluded to be less than or equal to 1." So, $L \leq 1$ ? Or we say that Lipschitz constant of the gradient of the considered function is in general $L \geq 1$. – learning Jul 10 '19 at 17:21
• @learning The Lipschitz constant for a Lipschitz continuous function $g$ is the infimum of all $L$ such that, for all $x, y$, $\|g(x) - g(y)\| \le L \|x - y\|$. You showed $\|\nabla f(z_1) - \nabla f(z_2)\| \le 1\|z_1 - z_2\|$, which implies that $1$ is one such value of $L$. The infimum must therefore be less than or equal to $1$ (it's the infimum of a set containing $1$). My argument shows that the Lipschitz constant must be at least $1$ (any value of $L$ in the set is bounded below by $1$). Thus, between us, we've shown the Lipschitz constant is equal to $1$. – Theo Bendit Jul 10 '19 at 17:25
• Thank you so much for the clarification. – learning Jul 10 '19 at 17:27