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
  • 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, 2019 at 16:56

1 Answer 1

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$
3
  • $\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, 2019 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$ Jul 10, 2019 at 17:25
  • $\begingroup$ Thank you so much for the clarification. $\endgroup$
    – learning
    Jul 10, 2019 at 17:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .