3

Let $E\subseteq\mathbb R^d$ be a convex set, $\beta\geq 0$ be a given real number and $f:E\to\mathbb R$ be a convex and differentiable function satisfying: $$f(y)\leq f(x)+\nabla f(x)^\top (y-x) +\frac{\beta}{2}\|x-y\|_2^2, \quad \forall x,y\in E.$$ Show that $\nabla f$ is $\beta$-Lipschitz, i.e., $$\|\nabla f(x)-\nabla f(y)\|_2\leq\beta\|x-y\|_2, \quad \forall x,y\in E.$$

Edit: I am interested in the case when $E$ can be any convex subset of $\mathbb R^d$. When $E=\mathbb R^d$, the claim can be proven as proposed by the answer below. However, in many convex optimisation textbooks, the claim is stated for general domains $E$ without proof.

TrivialPursuit
  • 371
  • Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or be closed. To prevent that, please [edit] the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. – Martin R Nov 10 '20 at 11:48
  • 1
    Imho this is good (reference) question. I have seen the claim several times for general convex $E$, but only found proofs for $E=\mathbb R^d$. – daw Nov 11 '20 at 13:18
  • If the smoothness condition holds for some $x,y\in E$, does the reverse $f(x) \leq f(y) + \nabla f(y)^\top(x-y) + \beta/2\lVert x-y\rVert_2^2$ also hold? – V.S.e.H. Nov 12 '20 at 05:30
  • 1
    @bodil this is just the inequality with $x,y$ exchanged – daw Nov 12 '20 at 08:23
  • Just to mention, Theorem 2.1.5 from "Lectures on Convex Optimization" by Nesterov suggests that the statement does not hold for a general $E$. Instead, we have the weaker additional conditions: $(\nabla f(x) - \nabla f(y))^\top(x-y) \leq \beta\lVert x-y\rVert^2_2$, and $0\leq \alpha f(x) + (1-\alpha)f(y) - f(\alpha x + (1-\alpha)y)\leq \alpha(1-\alpha)\frac{\beta}{2}\lVert x-y\rVert^2_2$ with $\alpha\in[0,1]$. – V.S.e.H. Nov 12 '20 at 19:16

2 Answers2

1

Let $E$ be open, convex and assume that $f$ is convex, differentiable and satisfies your inequality. It is easy to check that $\nabla f$ is continuous:

Let $(x_n) \subset E$ be a sequence with $x_n \to x \in E$. Since $\nabla f(x_n)$ is bounded ($f$ is locally Lipschitz), we have $\nabla f(x_{n_k}) \to g$ for a subsequence. A standard argument shows that $g \in \partial f(x) = \{ \nabla f(x)\}$. A subsequence-subsequence argument shows that the entire sequence $(\nabla f(x_k))$ converges towards $\nabla f(x)$.

The answer by daw shows that we get $$ \| \nabla f(y) - \nabla f(x) \| \le \beta \, \| y - x \| $$ whenever $x,y \in E$ satisfy $$ x + \frac1\beta \, \Big(\nabla f(y) - \nabla f(x)\Big),\; y + \frac1\beta \, \Big(\nabla f(x) - \nabla f(y)\Big) \in E.$$

Now, since $E$ is open, we can check that there is $\varepsilon_x > 0$, such that all $y \in B_{\varepsilon_x}(x)$ satisfy this condition.

Finally, let $x,y \in E$ be arbitrary. Since the segment $[x,y]$ is compact, we can find finitely many $z_k \in [x,y]$, such that the corresponding balls cover $[x,y]$. A repeated application of the triangle inequality shows the desired $$ \| \nabla f(y) - \nabla f(x) \| \le \beta \, \| y - x \|. $$

gerw
  • 31,359
  • Can you elaborate a bit more on your proof? – V.S.e.H. Nov 12 '20 at 14:07
  • @bodil: Which part? – gerw Nov 12 '20 at 14:16
  • So, first showing that $x + \frac{1}{\beta}(\nabla f(y) - \nabla f(x))\in E$ and $y +\frac{1}{\beta}(\nabla f(x) - \nabla f(y))\in E$ for all $x,y\in E$, or how this is satisfied locally, i.e. for an $\epsilon_x$ ball, and how is it useful in daw's proof. Then, I'm interested to see the last part with the triangle inequality in more detail. – V.S.e.H. Nov 12 '20 at 14:34
  • Hi @gerw, thanks! Now, coming back to the general case, is it true that the gradient of a convex and differentiable function is continuous, even at boundary points? If so, the inequality $|\nabla f(x)-\nabla f(y)|\leq\beta |x-y|$, which can be proved for all $x,y$ in the interior of $E$, could be extended to any points of $E$ by continuity. – TrivialPursuit Nov 12 '20 at 21:32
  • @TrivialPursuit: If $E$ is not open, how do you define "differentiable"? One easy case is the following: If $E \subset \Omega$, $\Omega$ is open and $f$ is the restriction of some convex, differentiable $g \colon \Omega \to \mathbb{R}$, you get the continuity of $\nabla f$. – gerw Nov 13 '20 at 07:03
  • @bodil: First point: You take $\delta < \varepsilon/2$ such that $|\nabla f(y) - \nabla f(x)| \le \beta , \varepsilon / 2$ for all $y \in B_\delta(x)$. Then, $\varepsilon_x = \delta$ does the job (triangle inequality). Second point: Take intermediate points $\xi_k = x + \lambda_k , (y-x)$ for an increasing sequence $(\lambda_k) \subset [0,1]$ with $\xi_0 = x$, $\xi_m = y$ and such that $\xi_j, \xi_{j-1}$ belong to a ball on which the Lipschitz inequality holds. Then apply the triangle inequality again. – gerw Nov 13 '20 at 07:06
  • @gerw: If $E$ is convex but not open, then at each $x\in E$, say that a function $f:E\to\mathbb R$ is differentiable at $x\in E$ if there exists $g\in\mathbb R^d$ such that for all $u\in E-x$, $f(x+u)-f(x)-g^\top u=|u|\varepsilon(u)$, where $\varepsilon$ is a function that satisfies $\varepsilon(u)\to 0$ as $u\to 0$. The only such vector $g$ that is parallel to $E$ (i.e. that is in the linear space spanned by $E-x$) is the gradient of $f$ at $x$. – TrivialPursuit Nov 13 '20 at 09:59
0

Let $x,y,z\in \mathbb R^d$. Then by the smoothness condition $$ f(x+z) \le f(x) + \nabla f(x)^Tz + \frac\beta2 \|z\|_2^2 $$ and by convexity $$ \nabla f(y)^T (x+z-y) \le f(x+z)-f(y). $$ Adding both inequalities gives $$ (\nabla f(y) - \nabla f(x))^Tz - \frac\beta2 \|z\|_2^2 \le f(x) - f(y) -\nabla f(y)^T(x-y). $$ The left-hand side is maximal for $z= \frac1{\beta}(\nabla f(y) - \nabla f(x))$, which gives $$ \frac1{2\beta} \|\nabla f(y) - \nabla f(x)\|_2^2 \le f(x) - f(y) -\nabla f(y)^T(x-y). $$ The inequality is true if we exchange $x$ and $y$. Adding the resulting both inequalities yields to $$ \frac1{\beta} \|\nabla f(y) - \nabla f(x)\|_2^2 \le (\nabla f(x)-\nabla f(y))^T(x-y). $$

daw
  • 49,113
  • 2
  • 38
  • 76
  • Hi, thank you. However, this proof only works when $E=\mathbb R^d$, whereas I am interested in the case of a general domain. – TrivialPursuit Nov 10 '20 at 18:02