Assume we have a convex function $f:\mathbb{R}^n\to \mathbb{R}$ and that it holds, $$c_1 ||x||^2 \leq f(x) \leq c_2 ||x||^2.$$ It looks like $f$ should behave quadratically around $0$, but can we proof that it has Lipschitz derivatives in a neighbourhood $U$ of $0$? Or some other bound on the derivatives near $0$?

I know Lipschitz gradients would be a consequence of L-smoothness in the sense that $\forall x,y\in U$, $$f(y)\leq f(x) + \nabla f(x)^\top (y-x)+\dfrac{L}{2}||x-y||^2 $$ but this seems to be a stronger assumption as $f$ has to be upper bounded by a tangential quadratic function at every point in $U$ and not just in $0$.


1 Answer 1


The best you can do is a Lipschitz estimate at zero itself, that is, there is an $A > 0$ such that \begin{equation*} \sup \left\{ \|p\| \, \mid \, p \in \partial f(x), \, \, x \in B(0,r) \right\} \leq A r. \end{equation*} (Notice $f$ is differentiable at $0$ and $Df(0) = 0$.) In fact, there is also a lower bound: \begin{equation*} \|p\| \geq c_{1}\|x\| \quad \text{if} \, \, p \in \partial f(x). \end{equation*}

The lower bound is much simpler to obtain. If $x \in \mathbb{R}^{n} \setminus \{0\}$ and $p \in \partial f(x)$, then \begin{equation*} 0 = f(0) \geq f(x) - \langle p, x \rangle \geq c_{1} \|x\|^{2} - \langle p, x \rangle. \end{equation*} Hence $\langle p, \frac{x}{\|x\|} \rangle \geq c_{1}\|x\|$, implying $\|p\| \geq c_{1} \|x\|$.

To obtain the upper bound, fix $r > 0$ and assume that $\|x\| \leq r$. If $p \in \partial f(x)$ and $\xi \in S^{n-1}$, then \begin{equation*} c_{2} \|x + r \xi\|^{2} \geq f(x + r \xi) \geq f(x) + r \langle p, \xi \rangle \geq c_{1} \|x\|^{2} + r \langle p, \xi \rangle. \end{equation*} Thus, \begin{equation*} \langle p, \xi \rangle \leq \frac{1}{r} \left( c_{2} \|x\|^{2} + c_{2} r^{2} + 2 c_{2} r \langle x, \xi \rangle - c_{1} \|x\|^{2} \right) \leq (4c_{2} - c_{1}) r. \end{equation*} This gives us the desired upper bound with $A = 4c_{2} - c_{1}$.

The reason this is the best we could hope for (i.e. we can't get $Df$ Lipschitz in a neighborhood of $0$) is $c_{1} < c_{2}$. Therefore, as soon as you get away from $0$, $f$ has a positive amount of space to wiggle around --- if $f$ can wiggle around a bunch, then certainly $Df$ can't be constrained, there's no reason for it to be continuous.

To make this more precise, let's go to $n = 1$. Let $h : [0,\infty] \to [c_{1},c_{2}]$ be a non-decreasing function with a sequence of discontinuities converging at zero. Define $g : \mathbb{R} \to \mathbb{R}$ with $g(x) = -g(-x)$ by \begin{equation*} g(x) = 2 h(x) x. \end{equation*} $g$ is non-decreasing. Therefore, the function $f : \mathbb{R} \to \mathbb{R}$ given by $f(x) = \int_{0}^{x} g(s) \, ds$ is convex. Furthermore, if $x > 0$, then \begin{equation*} c_{1}|x|^{2} \leq f(x) \leq c_{2} |x|^{2}. \end{equation*} Since $f(x) = f(-x)$, $f$ satisfies the desired inequalities, but $f'$ is not continuous in any neighborhood of zero.

We can generalize the previous example to $n > 1$ simpy by setting $F(x) = f(\|x\|)$.

  • $\begingroup$ Thanks a lot! I really appreciate your very complete answer. Such an upper bound on the subgradients is actually exactly what I was looking for. I think in the proof you lost the $c_2$ in front of $r^2+2r\langle x,\xi\rangle$ and we therefore get $A=(4c_2-c_1)r$ right? $\endgroup$
    – andrschl
    Jan 14, 2021 at 23:15
  • 1
    $\begingroup$ @andrschl, yes, you're right! I'll fix the typo. $\endgroup$
    – user711689
    Jan 15, 2021 at 0:28

You must log in to answer this question.

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