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.
Best Answer
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.