TITLE: Non-trivial lower bound approximation of a convex function using the second derivative at the minimum
QUESTION [3 upvotes]: Say that I am given an infinitely differentiable convex function $f: \mathbb{R}^n \rightarrow \mathbb{R}$. 
I am wondering if I can construct a meaningful lower bound approximation of $f$ using it's minimum value  $f(x^*)$ as well as the value of it's second derivative $\nabla^2 f(x^*)$ at the minimum.
Specifically, I am looking for a function $g: \mathbb{R}^n \rightarrow \mathbb{R}$ such that:
$$g(x) \leq f(x) \text{ for all } x \in \mathbb{R}^n$$
By meaningful, I mean any function $g(x)$ other than the constant function $g(x) = f(x^*)$.
EDIT: I have asked the question in a general form, but it if helps, the function that I am interested in is the $L_2$-regularized logistic loss function $$f(x) = \log(1+\exp(s^Tx)) + C\|x\|^2_2$$ 
where $s \in \mathbb{R}^n$ and $C > 0$. 
The function is not only infinitely differentiable in $x$, but is also strictly convex in $x$ and with a unique minimum. 
EDIT #2: To add to @Michael's answer, you can also find a non-trivial lower / upper bound for strictly convex functions in Section 9.1.2 of Stephen Boyd's Convex Optimization Book.

REPLY [4 votes]: No. For the general case, you cannot get a lower bound that is better than the constant function $f(x)\geq f(x^*)$ for all $x$. 
Claim: For any $a>0$, any $z>0$, and any $\epsilon>0$, we can construct a function $f:\mathbb{R}\rightarrow\mathbb{R}$ that is infinitely differentiable, convex, has minimum at $x=0$ given by $f(0)=0$, has $f''(0)=a$, and satisfies $0 \leq f(x)\leq \epsilon$ for all $x \in [0,z]$. 
Proof: Fix $a>0$.  Let $b>0$ be a given constant and define $f:\mathbb{R}\rightarrow\mathbb{R}$ by:
$$f(x) = \frac{a(bx+e^{-bx}-1)}{b^2}$$
Thus: 
\begin{align}
f'(x) &= \frac{a(1-e^{-bx})}{b}\\
f''(x) &= a e^{-bx} 
\end{align} 
Clearly $f''(x) \geq 0$ for all $x$, so the function is convex.  The function is also infinitely differentiable and has minimum at $x=0$, given by $f(0)=0$.  Further, regardless of the value of $b>0$, we get $f''(0)=a$.  However, the value of $f(z)$ is:  
$$ f(z) = \frac{a(bz + e^{-bz} - 1)}{b^2} $$
which can be made smaller than $\epsilon$ by choosing a suitably large $b>0$. Since $f(x)$ is non-decreasing for $x \geq 0$, it follows that $0 \leq f(x) \leq \epsilon$ for all $x \in [0,z]$.
$\Box$
Note:  I got this example by starting with $f''(x) = ae^{-bx}$ and integrating.

You might be able to get a non-trivial lower bound for your specific function.  

If you have a uniform bound on $f''(x)$ for all $x \in \mathbb{R}$ then you can get what you want:  Suppose there is a constant $c>0$ such that $f''(x) \geq c$ for all $x \in \mathbb{R}$.  Then by the Taylor expansion there is a $z$ in between $x^*$ and $x$ such that: 
\begin{align} 
f(x) &= f(x^*) + (x-x^*)f'(x^*) + \frac{(x-x^*)^2}{2}f''(z)  \\
&= f(x^*) + \frac{(x-x^*)^2}{2}f''(z)\\
&\geq f(x^*) + \frac{c(x-x^*)^2}{2}
\end{align} 
where the second equality holds because $f'(x^*)=0$.
In the $n$-dimensional case you would want a matrix $C$ such that $\nabla^2 f(x) - C$ is positive semi-definite for all $x \in \mathbb{R}^n$. Then the lower bound would be $f(x) \geq f(x^*) + \frac{1}{2}(x-x^*)^TC(x-x^*)$ for all $x \in \mathbb{R}^n$.
{"set_name": "stack_exchange", "score": 3, "question_id": 1223034}