Theorem 13, p. 23 — the projected gradient step contracts dist(·, X*) if and only if f has quadratic functional growth (22)

Let problem (P), $\min_{x \in X} f(x)$, satisfy the standing assumptions: $X \subseteq \mathbb{R}^n$ is closed and convex, $f$ is convex and differentiable on $X$ with gradient Lipschitz on $X$ with constant $L_f > 0$, and the optimal set $X^*$ is nonempty. For $x \in X$ let $x^+ = [x - \tfrac{1}{L_f}\nabla f(x)]_X$ be one step of the gradient method (GM) with constant step size $1/L_f$, and let $\bar x = [x]_{X^*}$, $\bar x^+ = [x^+]_{X^*}$. Then:

1. (Growth ⇒ linear convergence.) If $f$ satisfies the quadratic functional growth (22) with some constant $\kappa_f > 0$, then, with $\mu_f = \kappa_f / L_f$,

2. (Linear convergence ⇒ growth.) If for some $\beta$ with $0 < \beta < 1$

then $f$ satisfies (22) with constant $L_f(1-\beta)^2$, i.e. $f$ belongs to $\mathcal F_{L_f, L_f(1-\beta)^2}$.

In particular, the gradient method with constant step size contracts the distance to the optimal set by a uniform factor $< 1$ at every feasible point if and only if $f$ has quadratic functional growth: quadratic functional growth is exactly the condition, among those studied in the paper, under which (GM) converges linearly.

Formalization Note The page does not define "converging linearly"; its proof identifies it with the one-step contraction of Theorem 5 (part 2, obtained from Theorem 5) and obtains that contraction from (52) at $\alpha_k = 1/L_f$ (part 1, in the squared form of (52)). Part 1 gives the contraction of part 2 with $\beta = (1+\mu_f)^{-1/2} \in (0,1)$, so the two parts together give the equivalence of Theorem 13. A multi-step notion ("$\operatorname{dist}(x^k, X^*) \le C q^k$ along every run") is not used: the converse for it is not what the page proves. Nearest points are predicates; they exist and are unique on the nonempty closed convex sets $X$ and $X^*$.