Does a convex function sandwiched between two quadratic functions have Lipschitz derivatives?

Question

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

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