0
$\begingroup$

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.

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

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$.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – learning Jul 10 '19 at 17:21
  • 1
    $\begingroup$ @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$. $\endgroup$ – Theo Bendit Jul 10 '19 at 17:25
  • $\begingroup$ Thank you so much for the clarification. $\endgroup$ – learning Jul 10 '19 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.