let there be a strongly convex function $f(x)$.
I want to prove that if: $\forall x\in Dom(f):mI\succcurlyeq\nabla^{2}f(x)$ then:
$f(x)-f(x^{*})\geq\frac{1}{2m}\left|\left|\nabla f(x)\right|\right|_{2}^{2}$
where $ \succcurlyeq\ $is the positive semi-definite notation.
NOTE: $x^{*}$ is the optimum point of $f(x)$ , in this case it's the minimum point
My Solution:
for some $\ z\in Dom(f):mI\succcurlyeq\nabla^{2}f(z)$, then:
$mI\succcurlyeq\nabla^{2}f(z)$ is equivalent to $\rightarrow\nabla^{2}f(z)-mI\preccurlyeq0$ which means that $\forall x,y,z:$
$(x-y)^{T}(\nabla^{2}f(z)-mI)(x-y)\leq0$$\rightarrow(x-y)^{T}(\nabla^{2}f(z))(x-y)-(x-y)^{T}(mI)(x-y)\leq0$
which leads to: $(x-y)^{T}(\nabla^{2}f(z))(x-y)\leq m(x-y)^{T}(I)(x-y)=m\Vert x-y\parallel^{2}$
$(x-y)^{T}(\nabla^{2}f(z))(x-y)\leq m\Vert x-y\parallel^{2}$
from taylor's expansion:
$f(y)=f(x)+\nabla f(x)^{T}(y-x)+\frac{1}{2}(y-x)^{T}\nabla^{2}f(z)(y-x)$
taking: $y=x^{*}$:
$f(x^{*})=f(x)+\nabla f(x)^{T}(x^{*}-x)+\frac{1}{2}(y-x)^{T}\nabla^{2}f(z)(x^{*}-x)$
$\Rightarrow f(x^{*})-f(x)\leq$ $\nabla f(x)^{T}(x^{*}-x)+\frac{1}{2}m\Vert x-x^{*}\parallel^{2}$
$\Rightarrow f(x)-f(x^{*})\geq$ $\nabla f(x)^{T}(x-x^{*})-\frac{1}{2}m\Vert x-x^{*}\parallel^{2}$
we define: $x-x^{*}=t$
$\Rightarrow f(x)-f(x^{*})\geq$ $\underset{g(t)}{\underbrace{\overset{g_{1}(t)}{\overbrace{\nabla f(x)^{T}(t)}}-\frac{1}{2}m\Vert t\parallel^{2}}}$
$\Rightarrow dg_{1}=\nabla f(x)^{T}dt$ $\rightarrow\nabla g_{1}(t)=\nabla f(x)$
$\Rightarrow$$\nabla g(t)=0\rightarrow$$\nabla f(x)-\frac{1}{2}m\cdot2t=0\rightarrow t^{*}=\frac{\nabla f(x)}{m}$
$min\{g(t)\}=g(t^{*})=$$\nabla f(x)^{T}\left(\frac{\nabla f(x)}{m}\right)-\frac{1}{2}m\left|\left|\frac{\nabla f(x)}{m}\right|\right|^{2}$=$\frac{1}{2m}\left|\left|\nabla f(x)\right|\right|_{2}^{2}$
since $f(x)-f(x^{*})\geq$ $\underset{g(t)}{\underbrace{\overset{g_{1}(t)}{\overbrace{\nabla f(x)^{T}(t)}}-\frac{1}{2}m\Vert t\parallel^{2}}}$ holds for every $t$ then, (which is equivalent to every $x$)
$\underset{x}{min}\{f(x)-f(x^{*})\}$ $\geq$$\underset{\text{min\{g(t)\}}}{\underbrace{\frac{1}{2m}\left|\left|\nabla f(x)\right|\right|_{2}^{2}}}$ for every x.
$\Rightarrow$$f(x)-f(x^{*})$ $\geq$$\frac{1}{2m}\left|\left|\nabla f(x)\right|\right|_{2}^{2}$
My problem is with the step: $\Rightarrow$$\nabla g(t)=0\rightarrow$$\nabla f(x)-\frac{1}{2}m\cdot2t=0\rightarrow t^{*}=\frac{\nabla f(x)}{m}$
since $x-x^{*}=t$, and by taking the gradient with respect to $t$ , I can't assume that $\nabla f(x)$ is constant, because $x$ and $t$ are dependant.
how can I make this solution right?
There is no need to use Taylor's expansion, moreover as you have just expanded till the quadratic term. Your proof only holds for a quadratic function. The result to be proved is incorrect. Consider the following one-dimensional function, $f$: $$\ f: [-3, +\infty] \to {R} \ \text{ where } \ f(x)=-x^3-3x^2 $$ You can check that $x^*=-2$ is local minimum. $f''(x) \leq 12$ for all $x$ in domain of $f$. Your result tells the following: $$\ f(x)-f(-2)\geq\frac{1}{24}(f'(x))^2\geq0 $$ Obviously, this is not true for $x>1$.
The result you want holds if $f$ is convex. We can show that $\|\nabla^2 f(x)\|\leq m$ and hence, $f$ is $m$-smooth. Following is the proof:
Let $z=x-\frac{1}{m}\left(\nabla f(x)\right)$, \begin{align} f(x^*)-f(x) &= f(x^*)-f(z)+f(z)-f(x)\\ &\leq f(z) -f(x) \qquad \qquad \qquad \quad \qquad \text{[From Convexity]}\\ &\leq\nabla f(x)^T\left(z-x\right)+\frac{m}{2}\|z-x\|^2 \quad \text{[From Smoothness]}\\ &\leq -\frac{1}{m}\|\nabla f(x)\|^2+\frac{1}{2m}\|\nabla f(x)\|^2\\ &\leq -\frac{1}{2m}\|\nabla f(x)\|^2 \end{align} Hence, we prove the required result.
Note: $\|.\|$ is spectral norm and $l_2$ norm for matrices and vectors respectively.