Smooth convex gradient differences around a minimizer

Fix $i$ and define [given] ${\varphi }_i(z)=h_i(z)-⟨\mathrm{\nabla }{h}_i(x^{\star }),z-x^{\star }⟩$. For $z\in {\mathbb{R}}^d$ and $0<t\le 1$, convexity [F3] gives $\frac{h_i(x^{\star }+t(z-x^{\star }))-h_i(x^{\star })}{t}\le h_i(z)-h_i(x^{\star })\mathrm{.}$ Letting $t\downarrow 0$ and using differentiability at $x^{\star }$ yields $⟨\mathrm{\nabla }{h}_i(x^{\star }),z-x^{\star }⟩\le h_i(z)-h_i(x^{\star })$. Therefore ${\varphi }_i(z)\ge {\varphi }_i(x^{\star })$ for every $z$, so $x^{\star }$ minimizes ${\varphi }_i$.

The gradient $\mathrm{\nabla }{\varphi }_i$ is $\beta$-Lipschitz and vanishes at [given] $x^{\star }$. Apply the descent inequality [F1] at $x$ with $y=x-{\beta }^{-1}\mathrm{\nabla }{\varphi }_i(x)$; the inner-product and squared-norm terms give ${\varphi }_i(y)\le {\varphi }_i(x)-{\beta }^{-1}\mathrm{\parallel }\mathrm{\nabla }{\varphi }_i(x){\mathrm{\parallel }}_2^2+\frac{\beta }{2}{\beta }^{-2}\mathrm{\parallel }\mathrm{\nabla }{\varphi }_i(x){\mathrm{\parallel }}_2^2={\varphi }_i(x)-\frac{1}{2\beta }\mathrm{\parallel }\mathrm{\nabla }{\varphi }_i(x){\mathrm{\parallel }}_2^2\mathrm{.}$ Since ${\varphi }_i(x^{\star })\le {\varphi }_i(y)$ by step 1.1, rearranging gives $\mathrm{\parallel }\mathrm{\nabla }{h}_i(x)-\mathrm{\nabla }{h}_i(x^{\star }){\mathrm{\parallel }}_2^2\le 2\beta (h_i(x)-h_i(x^{\star })-⟨\mathrm{\nabla }{h}_i(x^{\star }),x-x^{\star }⟩)\mathrm{.}$

Average the inequality in step 1.2 over $i$. By [F2], $N^{-1}{\sum }_i\mathrm{\nabla }{h}_i(x^{\star })=\mathrm{\nabla }f(x^{\star })$. For each coordinate direction $e_j$, the one-variable function $s\mapsto f(x^{\star }+s{e}_j)$ has a minimum at $s=0$, so differentiability gives $⟨\mathrm{\nabla }f(x^{\star }),e_j⟩=0$. Thus every coordinate of $\mathrm{\nabla }f(x^{\star })$ is zero. The averaged inner-product term therefore vanishes and the remaining function terms equal $2\beta (f(x)-f(x^{\star }))$. This is the claimed bound.