Eq. (35) — a subgradient of $L_\beta$ bounded by $C\|x^{t+1}-x^t\|$

Let $h:\mathbb R^n\to\mathbb R$ be twice continuously differentiable with bounded Hessian, $P:\mathbb R^m\to(-\infty,+\infty]$ proper and closed, $\mathcal M:\mathbb R^n\to\mathbb R^m$ linear and $\beta>0$, with augmented Lagrangian $L_\beta(x,y,z)=h(x)+P(y)-\langle z,\mathcal Mx-y\rangle+\frac\beta2\|\mathcal Mx-y\|^2$. Suppose Assumption 1 holds with $\mathcal T_1=0$ (hence $\phi=0$), with witnesses $\sigma,\mathcal Q_1,\mathcal Q_2,\delta,\mathcal Q_3,\gamma$, and let $(x^t,y^t,z^t)_{t\ge0}$ be generated by the ADMM

Then there is a constant $C>0$ such that for every $t\ge1$ there is $w\in\partial L_\beta(x^{t+1},y^{t+1},z^{t+1})$, the limiting subdifferential of $L_\beta$ as a function of $(x,y,z)$, with

In particular $\operatorname{dist}(0,\partial L_\beta(x^{t+1},y^{t+1},z^{t+1}))\le C\|x^{t+1}-x^t\|$, which is (35).

This is the "relative error" half of the KL argument: small primal steps force nearly stationary points of $L_\beta$.

Formalization Note The ADMM is the relation IsProxADMMSeq with $\phi = 0$ (the Bregman term vanishes); Assumption 1 is instantiated with $\phi = 0$ and $\mathcal T_1 = 0$, and $\mathcal T_2$ is left as a parameter (Assumption 1 forces $0 \preceq \mathcal T_2 \preceq \mathcal T_1 = 0$). Values of $L_\beta$ and $P$ live in EReal; iterates are indexed from $0$, and $y^0$ is not constrained. The existential form (an explicit subgradient) implies the distance form. The range $t\ge1$ is where the paper's (14) applies; the paper leaves it implicit.