Does the gradient decrease at each iteration when running gradient descent on a strongly convex function? Given a strongly convex function $f$ gradient descent is the celebrated algo that performs the iterates
$$x_{t + 1} = x_t - \eta \nabla f(x_t),$$
starting from an arbitrary point $x_0$ in the domain of the function ($\eta$ must also be chosen small). The convergence of this procedure is well known.
Will we also have that $\| \nabla f(x_{t+1})\| \le \| \nabla f(x_t) \| $ for all $t$? If not, are there any conditions we can impose on $f$ so that $\| \nabla f(x_{t+1})\| \le \| \nabla f(x_t) \| $ holds for all $t$?
 A: I think you are also assuming that the gradient $\nabla f$ is $L$-Lipschitz continuous, otherwise, you would not set an upper bound on the step size. In the case of the Lipschitz continuous gradient, you have $$\|\nabla f(x_{t+1})\|_2 \leq L\|x_{t+1} - x^\star\|,$$
where $x^\star = \text{argmin}~ f(x)$. From the strong convexity with parameter $m$, you have
$$\|x_{t} - x^\star\| \leq \frac{1}{m}\|\nabla f(x_{t})\|.$$
Finally, for some convergence rate $\rho\in(0,1)$, you have
$$\|x_{t+1}-x^\star\|\leq \rho\|x_{t}-x^\star\|.$$
Combining these three inequalities give
$$\|\nabla f(x_{t+1})\| \leq \frac{\rho L}{m}\|\nabla f(x_{t})\|.$$
A: Given $f$ is convex and differentiable, we have convergence and by the first order optimality conditions we have $$\nabla f(x_*) = 0,$$ where $x_*$ us the minimizer of $f$. This implies that for some $x$ close to $x_*$  we have $$\nabla f(x) \to 0 \Rightarrow \|\nabla f(x)\| \to 0 \Rightarrow \|\nabla f(x_{k})\| \geq \|\nabla f(x_{k+1})\|\geq \dots \geq \|\nabla f(x_{*})\| =0,$$ which proves your remark.
