If $\nabla f$ has a Lipschitz constant of $L$, then
$$f(y) \leq f(x) + \nabla f(x)^T(y − x) + \frac{L}{2}\| y − x\|^2. $$
Using this fact I am going to prove $$\frac{1}{2L}\|\nabla f(x)\|^2 \leq f(x)-f(x^*).$$
I started by writing the following statement,
$$ f(x)-f(x^*)=\arg \max_y[f(x)-f(y)]\geq \arg\max_y[-\nabla f(x)^T(y-x)-\frac{L}{2}\|y-x\|^2].$$
However, I don't know how to find "$\arg\max_y[-\nabla f(x)^T(y-x)-\frac{L}{2}\|y-x\|^2]$. I appreciate any help.
This result does not depend on $f$ being convex.
Let $\phi_x(h) = \langle \nabla f(x), h \rangle + {L \over 2} \|h\|^2$ and note that $\phi_x$ is a convex quadratic function and $\nabla \phi_x(h) = \nabla f(x) + L h$, hence $\phi_x(h^*) \le \phi_x(h)$ where $\nabla f(x) + L h^* = 0$.
In particular, $\phi_x(h^*) = -{1 \over 2L} \| \nabla f(x) \|^2$.
We have $f(x+h) \le f(x) + \phi_x(h)$ and so $\inf_{h'} f(x+h') = \inf f \le f(x) + \phi_x(h)$ for all $h$.
Hence $\inf f \le f(x) + \inf_h \phi_x(h) = f(x) - {1 \over 2L} \| \nabla f(x) \|^2$.
Rearranging gives ${1 \over 2L} \| \nabla f(x) \|^2 \le f(x) - \inf f$.