Quadratic bounds on a convex function Let $f: \mathbb{R}\rightarrow\mathbb{R}$ be a twice-differentiable convex function. It can shown be that for any $x_0 \in \mathbb{R}$:
$f(x) \leq f(x_0) + (x-x_0)f'(x_0) + \frac{(x-x_0)^2}{2}$C
where $C = \arg \max_x f''(x)$ is the maximum curvature of $f(x)$ over its domain. This result has been proven here:
Bohning, D. and Lindsay, B.G., ``Monotonicity of quadratic-approximation algorithms'', Annals of the Institute of Statistical Mathematics, vol. 40, no. 4, pp. 641-663, 1988.
Is it possible to derive a quadratic lower bound as well using a similar idea? It seems intuitively possible with a small enough choice of curvature in the bound.
 A: To elaborate on my comment, suppose $f: \mathbb{R}^n \to \mathbb{R}$ is $C^2$. Then Taylor's theorem gives
$$f(x) = f(x_0) + \frac{\partial f (x_0)}{\partial x} (x-x_0) + \int_0^1 (1-t) (x-x_0)^T \frac{\partial^2 f (x_0+t (x-x_0))}{\partial x^2} (x-x_0) \, dt .$$
Now suppose that $m \leq \frac{\partial^2 f (x)}{\partial x^2} \leq M$ on some convex set $K \subset \mathbb{R}^n$. Then is is easy to see that if $x,x_0 \in K$, then
$$f(x_0) + \frac{\partial f (x_0)}{\partial x} (x-x_0) + \frac{m}{2} \|x-x_0\|^2 \leq f(x) \leq f(x_0) + \frac{\partial f (x_0)}{\partial x} (x-x_0) + \frac{M}{2} \|x-x_0\|^2 .$$
This is true for any $f \in C^2$, not just convex $f$. If $f$ happens to be convex, then you know that $m=0$ will serve as a lower bound. By considering the convex function $f(x) = x^4$ near $0$, you can see that even a strictly convex function may have $m=0$ as the 'best' lower bound in some sense.
A: The last answer is correct, and it gives the lower bound.  However, the comment about strictly convex can be confusing.  If there is a lower bound $m$ on the second derivative, we call the function $m$-convex, and this is equivalent to convexity of $u(x) - mx^2/2$.  Then, instead of using Taylor series, you can obtain the same lower bound using the supporting hyperplane condition.  This is useful for technical reasons: $m$ convexity can hold without the function having second derivatives everywhere.  For more information, see "Semiconcave Functions, Hamilton–Jacobi Equations, and Optimal Control"
