2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Is the above supposed to be $C||x||^2$? $\endgroup$ – Michael Apr 6 '15 at 23:39
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thank you so much for a clear explanation + proof! I do actually have the uniform bound on $f''(x)$! One follow-up question: how did you use the Taylor expansion to justify that there was a $z$ between $x$ and $x^*$ such that your first equation holds? $\endgroup$ – Elements Apr 7 '15 at 2:03
  • $\begingroup$ See "Mean value forms of the remainder" here: en.wikipedia.org/wiki/Taylor%27s_theorem $\endgroup$ – Michael Apr 7 '15 at 3:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.