Let $V$ denote a strictly convex function (in arbitrary dimension) whose Hessian is $L$-Lipschitz. Given only this knowledge, and the values of $\left\{ V \left( x \right), \nabla V \left( x \right), \nabla^2 V \left( x \right)\right\}$ at a single value $x$, I am interested in finding a good lower bound to $V$. WLOG, I will take $L = 1$, $x = 0$, $V(x) = 0$, $\nabla V (x) = 0$, $\nabla^2 V(x) = H = \mathrm{diag} \left( h \right)$ where $h$ has positive entries.
Using basic estimates, one can see that
\begin{align} V\left(y\right)\geqslant\frac{1}{2} y^\top H y - \frac{1}{6} \left|y \right|^{3}, \end{align}
however, this is slightly unsatisfactory as this bound is not globally convex.
Computing that the Hessian of $y \mapsto \frac{1}{6} \left| y \right|_2^{3}$ is given by $\frac{1}{2} \left( \left| y \right|_2 \cdot I + \frac{yy^{\top}}{\left| y \right|_2} \right) \preceq \left| y \right|_2 \cdot I$, one sees that it is at least convex on the ball $\left\{ y: \left| y \right|_2 \leqslant \mathrm{min} \left( h \right) \right\}$. Thus, at least in principle, one can use the basic estimate on this ball, and then take its minimal convex extension outside of this set. However, I don't know whether one can easily compute a closed-form expression for this extension, and so it's not entirely practical for me to work with.
My questions are thus:
- Can one compute a closed-form expression for this extension?
- Are there good ways to compute explicit, convex minorants to $V$?
and more ambitiously,
- Can one characterise the optimal convex minorant to $V$ somewhat explicitly?
In principle, I am also interested in the same question given more general access to high-order derivatives and smoothness estimates of $V$, but this interest is secondary.
