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

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

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

• 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? Jan 14, 2021 at 23:15
• @andrschl, yes, you're right! I'll fix the typo.
– user711689
Jan 15, 2021 at 0:28