Theorem 3.1, p. 344 — primal gradient scheme: f(xᵏ) nonincreasing and f(xᵏ) − f(x) ≤ μD_h(x,x⁰)/((1+μ/(L−μ))ᵏ − 1) ≤ (L−μ)D_h(x,x⁰)/k

Let $Q$ be a convex subset of a finite-dimensional real inner-product space $E$, and let $f,h:E\to\mathbb R$ be differentiable at every point of $Q$ and convex on $Q$; $h$ is the reference function and $D_h(y,x)=h(y)-h(x)-\langle\nabla h(x),y-x\rangle$ its Bregman distance. Let $L>0$ and $0\le\mu<L$, and suppose $f$ is $L$-smooth and $\mu$-strongly convex relative to $h$ on $Q$. Let $x^0,x^1,\dots$ be a run of the primal gradient scheme (Algorithm 1) with parameter $L$. Then:

1. the sequence $f(x^k)$ is nonincreasing;
2. for all $k\ge1$ and $x\in Q$,

3. if moreover $\mu>0$, then for all $k\ge1$ and $x\in Q$,

The theorem gives an $O(1/k)$ rate for the primal gradient scheme whenever $f$ is smooth relative to $h$, and a linear rate when $f$ is also strongly convex relative to $h$, without any Lipschitz gradient or strong convexity in the usual sense and without strong convexity of $h$.

Formalization Note The paper states (26) as a single chain for all $\mu\ge0$, with the middle term "defined in the limit as $\mu\to0^+$"; that limit equals the right-hand term, so the statement here gives the right-hand bound for every $0\le\mu<L$ and the full chain for $\mu>0$, and no limit is formalized. The hypothesis $\mu<L$ is added: (26) divides by $L-\mu$, and at $\mu=L$ the page's expression is undefined while Lean's $a/0=0$ would change its meaning. "Monotonically decreasing" is read as nonincreasing, which is what the proof gives. Relative smoothness and strong convexity are assumed on the (relative) interior of $Q$ (Definitions 1.1–1.2), while the conclusion holds for every $x\in Q$ and the iterates may lie anywhere in $Q$. Closedness of $Q$ is not assumed (no step of the argument uses it), which makes the statement stronger. Differentiability of $f,h$ is differentiability as functions on $E$ at each point of $Q$.