Bounding Second Derivatives

The first result, which has been widely applied, applies to functions with a continuous and uniformly bounded second derivative [Böhning and Lindsay, 1988].

Theorem: If $f$ is twice differentiable and there is an $a>0$ such that $f''(x)\leq a$ for all $x$, then for each $y$ the convex quadratic function $$\begin{eqnarray*} g(x)=f(y)+f'(y)(x-y)+\frac{1}{2}a(x-y)^2. \end{eqnarray*}$$ majorizes $f$ at $y$.

Proof: Use Taylor's theorem in the form $$f(x)=f(y)+f'(y)(x-y)+ \frac{1}{2}f''(\xi)(x-y)^2,$$ with $\xi$ on the line connecting $x$ and $y$. Because $f''(\xi)\leq a$, this implies $f(x)\leq g(x)$, where $g$ is defined above. QED

This result is very useful, but it has some limitations. In the first place we would like a similar result for functions that are not everywhere twice differentiable, or even those that are not everywhere differentiable. Second, the bound does take into account that we only need to bound the second derivative on the interval between $x$ and $y$, and not on the whole line. This may result in a bound which is not sharp. In particular we shall see below that substantial improvements can result from a non-uniform bound $a(y)$ that depends on the support point $y$.

If $\mathcal{D}^2f(x)\lesssim D$ for all $x\in\mathcal{X},$ then $\phi(\omega)\leq\phi(\xi)+(\omega-\xi)'\nabla\phi(\xi)+ \frac{1}{2}(\omega-\xi)'D(\omega-\xi).$ Let $\eta(\xi)=\xi-D^{-1}\nabla\phi(\xi),$ then $\phi(\omega)\leq\phi(\xi)-\frac{1}{2}\nabla\phi(\xi)'D^{-1}\nabla\phi(\xi)+ \frac{1}{2}(\omega-\eta(\xi))'D(\omega-\eta(\xi)).$ Thus here we have quadratic majorizers.