Let $f,h\colon\mathbb R^n\to\mathbb R$ be two strongly convex functions such that $f\ge h$ and $f\left( x^*\right)=h\left( x^*\right)$, where $x^*$ is a joint unique minimizer for both. Assume that $f$ is non-differntiable and $h$ is continuously differentiable.
Take any $x,y\in\mathbb R^n$ such that $f\left( x\right)\ge f\left( y\right)$. Can we say that $f\left( x\right)- f\left( y\right)\ge h\left( x\right)- h\left( y\right)$?
I encountered this problem while analyzing an optimization algorithm. I tried to use the the multi-variable mean value theorem (although $f$ is non-differentiable in infinitely many points). Any ideas on even if this statement is true?
The statement is not true. Think about this counterexample for $n=1$: Let's denote by $z_0\approx 4.89$ the bigger one of the two roots of $g(x)=3x^{4/3}-1-x^2 $. Then the counterexample is given by $$h(x)=x^2$$ and $$f(x)=\begin{cases}2x^2,\qquad x<1\\ 3x^{4/3}-1,\ x\in[1,z_0]\\ x^2,\quad x>z_0 \end{cases} $$ at the points $x=z_0$ and $y=1$. Both functions have the same value at point $x$, but as $h(y)=1$ and $f(y)=2$, so the function $f$ is growing less in this interval.