Non-trivial lower bound approximation of a convex function using the second derivative at the minimum

Question

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.

Answer 1

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