From Convex Optimization by Boyd & Vandenberghe:
Let $f$ be a twice continuously differentiable convex function that is strongly convex with constant $m$, i.e., $\nabla^2 f(x) \succeq m I$ for $x \in S = \{x : f(x) \le f(x^{(0)})\}$ for some starting point $x^{(0)}$ where $S$ is a closed set. Assume $$\|\nabla^2 f(x) - \nabla^2 f(y) \|_2 \le L \|x-y\|_2$$ for all $x, y \in S$.
The goal is to prove that there are numbers $\eta$ and $\gamma$ with $0 \lt \eta \le m^2/L$ and $\gamma \gt 0$ such that
If $\|\nabla f(x^{(k)})\|_2 \lt \eta$, then the backtracking line search selects $t^{(k)} = 1$ and $$(L/2m^2)\|\nabla f(x^{(k+1)})\|_2 \le ((L/2m^2)\|\nabla f(x^{(k)})\|_2)^2$$
Suppose it is satisfied for iteration $k$, i.e., $||\nabla f(x^{(k)})||_2 \lt \eta.$ Since $\eta \le m^2 / L$, we have $||\nabla f(x^{(k+1)})||_2 \lt \eta$.
Can someone explain how this last line is true? I've tried to prove it but I can't see any reason why $\eta \le m^2/L \Rightarrow ||\nabla f(x^{(k+1)})||_2 \lt \eta$.
In the last displayed inequality, notice that the RHS is squared. Rewrite the inequality: $$ \|\nabla f(x^{(k+1)})\|_2\le\frac L{2m^2}\|\nabla f(x^{(k)})\|_2^2.\tag1 $$ If $\|\nabla f(x^{(k)})\|_2$ is less than $\eta$, then its square is less than $\eta^2$. But $\eta<m^2/L$ so the RHS of (1) is less than $$ \frac L{2m^2}\eta\eta<\frac L{2m^2}\eta\frac{m^2}L=\frac12\eta<\eta.$$