SCAFFOLD convergence — Explicit finite-round forms supporting Theorem III

Read-back model: gpt-6.

The declaration asserts a conjunction of two independently universally quantified bounds, with the following common data and run requirements. For an arbitrary universe level, each bound quantifies over natural numbers $d,N$, a problem $P$, a type $\Omega$ in that universe equipped with a measurable space that is a standard Borel space, a probability measure $\nu$ on $\Omega$, natural numbers $S,K,T$, and real numbers $\eta_l,\eta_g$. Write $I=\{0,\ldots,N-1\}$ and $E=\mathbb R^d$, with its Euclidean norm and real inner product. The problem $P$ consists of functions $f_i:E\to\mathbb R$ for $i\in I$, real numbers $\beta,\sigma$, and $x_0\in E$, subject to $N>0$, $\beta>0$, $\sigma\ge0$, existence of the gradient $\nabla f_i(x)$ at every $i,x$, and

$$\|\nabla f_i(x)-\nabla f_i(y)\|\le\beta\|x-y\| \qquad(i\in I,\ x,y\in E).$$

Define the real-valued objective, round times, and effective step by

$$F(x)=\frac1N\sum_{i\in I}f_i(x),\qquad t_r=K+r(K+1)\quad(r\in\mathbb N),\qquad h=K\eta_l\eta_g.$$

Natural numbers occurring in real formulas are interpreted as real numbers.

A run at these parameters requires $0<S\le N$, $K>0$, and $T>0$. It supplies a filtration $(\mathscr F_t)_{t\in\mathbb N}$ of sub-$\sigma$-algebras of the specified measurable space on $\Omega$; random vectors

$$U_{k,i},X_r,C_{r,i},Y_{r,k,i},G_{r,k,i}:\Omega\to E \qquad(r,k\in\mathbb N,\ i\in I);$$

and maps $B_r:\Omega\to\{\text{finite subsets of }I\}$ for all $r\in\mathbb N$. All almost-sure statements below are with respect to $\nu$, and $\mathbb E_\nu[\,\cdot\mid\mathscr F_t]$ denotes conditional expectation. The warm-up vectors satisfy, for every $k<K$ and $i\in I$, strong measurability of $U_{k,i}$ with respect to $\mathscr F_{k+1}$, membership $U_{k,i}\in L^2(\nu;E)$, and

$$\mathbb E_\nu[U_{k,i}\mid\mathscr F_k] =\nabla f_i(x_0)\quad\text{almost surely},\qquad \mathbb E_\nu[\|U_{k,i}-\nabla f_i(x_0)\|^2\mid\mathscr F_k] \le\sigma^2\quad\text{almost surely}.$$

For each $k<K$, the whole family $(U_{k,i})_{i\in I}$ is conditionally independent given $\mathscr F_k$. For every $r\le T$, $X_r$ and each $C_{r,i}$ are strongly measurable with respect to $\mathscr F_{t_r}$ and belong to $L^2(\nu;E)$. For every $r<T$, $k\le K$, and $i\in I$, $Y_{r,k,i}$ is strongly measurable with respect to $\mathscr F_{t_r+k}$ and belongs to $L^2(\nu;E)$. For every $r<T$, $k<K$, and $i\in I$, $G_{r,k,i}$ is strongly measurable with respect to $\mathscr F_{t_r+k+1}$, belongs to $L^2(\nu;E)$, and satisfies

$$\begin{aligned} \mathbb E_\nu[G_{r,k,i}\mid\mathscr F_{t_r+k}] &=\nabla f_i(Y_{r,k,i}) &&\text{almost surely},\\ \mathbb E_\nu[\|G_{r,k,i}-\nabla f_i(Y_{r,k,i})\|^2 \mid\mathscr F_{t_r+k}] &\le\sigma^2 &&\text{almost surely}. \end{aligned}$$

Here a function applied to a random vector is evaluated pointwise on $\Omega$. For each $r<T$ and $k<K$, the whole family $(G_{r,k,i})_{i\in I}$ is conditionally independent given $\mathscr F_{t_r+k}$.

For each $r<T$, the sampled set has $|B_r|=S$ almost surely. For every finite subset $J\subseteq I$, the real-valued indicator $\mathbf1_{\{B_r=J\}}$ is strongly measurable with respect to $\mathscr F_{t_{r+1}}$, and

$$\mathbb E_\nu[\mathbf1_{\{B_r=J\}}\mid\mathscr F_{t_r+K}] = \begin{cases} \binom{N}{S}^{-1},& |J|=S,\\ 0,& |J|\ne S \end{cases} \quad\text{almost surely}.$$

The run has $X_0=x_0$ almost surely. Its initial controls are specified separately in the two bounds below. For every $r<T$ and $i\in I$, it has $Y_{r,0,i}=X_r$ almost surely. For every $r<T$, $k<K$, and $i\in I$, its local update is

$$Y_{r,k+1,i} =Y_{r,k,i} -\eta_l\left(G_{r,k,i}-C_{r,i} +\frac1N\sum_{j\in I}C_{r,j}\right) \quad\text{almost surely}.$$

For every $r<T$ and $i\in I$, its control update is

$$C_{r+1,i}(\omega)= \begin{cases} \displaystyle\frac1K\sum_{k=0}^{K-1}G_{r,k,i}(\omega), &i\in B_r(\omega),\\ C_{r,i}(\omega),&i\notin B_r(\omega) \end{cases} \quad\text{for almost every }\omega.$$

For every $r<T$, its server update is

$$X_{r+1}(\omega)=X_r(\omega) +\frac{\eta_g}{S}\sum_{i\in B_r(\omega)} \bigl(Y_{r,K,i}(\omega)-X_r(\omega)\bigr) \quad\text{for almost every }\omega.$$

These requirements impose the local dynamics and gradient assumptions on every client $i\in I$, including clients outside $B_r(\omega)$. Each displayed almost-sure identity or inequality is required separately for the indicated indices. All of the warm-up requirements are part of a run in both bounds, including when its controls are initialized deterministically.

The first universally quantified bound additionally quantifies over a real number $\mu$, an arbitrary deterministic function $c_0:I\to E$, and $x_\star\in E$. It assumes $\mu\ge0$ and, for every $i\in I$ and every $x,y\in E$,

$$f_i(x)+\langle\nabla f_i(x),y-x\rangle +\frac\mu2\|y-x\|^2\le f_i(y).$$

It also assumes

$$\begin{gathered} F(x_\star)\le F(x)\quad\text{for every }x\in E,\qquad \eta_l>0,\qquad \eta_g\ge1,\\ h\le\frac1{81\beta},\qquad \mu h\le\frac{S}{15N}. \end{gathered}$$

For every run satisfying all the common requirements and the deterministic control initialization $C_{0,i}=c_0(i)$ almost surely for every $i\in I$, let

$$w_r=(1-\mu h/2)^{-(r+1)} \quad(0\le r<T),\qquad W=\sum_{r=0}^{T-1}w_r.$$

The asserted bound is

$$\frac1W\sum_{r=0}^{T-1}w_r \int_\Omega\bigl(F(X_r(\omega))-F(x_\star)\bigr)\,d\nu(\omega) \le \frac{\displaystyle \|x_0-x_\star\|^2 +\frac{9Nh^2}{S}\left( \frac1N\sum_{i\in I}\|c_0(i)-\nabla f_i(x_\star)\|^2 \right)} {hW} +\frac{12h\sigma^2}{KS}\left(1+\frac{S}{\eta_g^2}\right).$$

The left side is the weighted sum of the expected objective gaps at $X_0,\ldots,X_{T-1}$, divided by the sum of those weights.

The second universally quantified bound independently quantifies over all the common data and a real number $f_{\mathrm{lower}}$. It assumes

$$\begin{gathered} f_{\mathrm{lower}}\le F(x)\quad\text{for every }x\in E,\qquad \eta_l>0,\qquad \eta_g\ge1,\\ h\le\frac{(S/N)^{2/3}}{24\beta}, \end{gathered}$$

where $(S/N)^{2/3}$ is the real power with exponent $2/3$. For every run satisfying all the common requirements and the warm-up control initialization

$$C_{0,i}=\frac1K\sum_{k=0}^{K-1}U_{k,i} \quad\text{almost surely}\qquad(i\in I),$$

the asserted bound is

$$\frac1T\sum_{r=0}^{T-1} \int_\Omega\|\nabla F(X_r(\omega))\|^2\,d\nu(\omega) \le \frac{14\bigl(F(x_0)-f_{\mathrm{lower}}\bigr)}{hT} +\frac{70\beta h\sigma^2}{KS} \left(1+\frac{S}{\eta_g^2}\right).$$

Here $\nabla F$ is the Euclidean gradient of the explicitly defined average $F$. This conjunct has no convexity or minimizer hypothesis. The conjunction asserts both universal implications; it does not require the data or the run in one conjunct to coincide with those in the other.

The quantifiers allow $d=0$, when $E$ is the zero-dimensional Euclidean space with one point, and allow $\sigma=0$. They include $N=1$, $S=1$, $K=1$, $T=1$, and full participation $S=N$ whenever the other hypotheses hold. For the first bound, $\mu=0$ is allowed and gives $w_r=1$ and $W=T$. Although $N,S,K,T$ are quantified as arbitrary natural numbers, $N=0$ admits no problem $P$, and $S=0$, $S>N$, $K=0$, or $T=0$ admits no run of the required kind. The universal assertion over runs is vacuous whenever no such run exists; neither conjunct asserts existence of a run. The first conjunct assumes the supplied $x_\star$ is a minimizer, and the second assumes the supplied real $f_{\mathrm{lower}}$ is a global lower bound, without asserting existence of either. In an actual run meeting either conjunct's step assumptions, $N,S,K,T,\beta,\eta_g,h$ are all positive. In the first conjunct, $0\le\mu h\le S/(15N)\le1/15$, hence $1-\mu h/2\ge29/30>0$ and $W>0$. Thus the displayed denominators are nonzero in all instances with an admissible run. The run's arrays are defined for all natural time indices, but measurability, moment, independence, and update conditions apply only over the index ranges explicitly stated above; the bounds use $X_0,\ldots,X_{T-1}$, while the run also constrains $X_T$ and $C_{T,i}$. Conditional independence is imposed for each indicated family across clients at a fixed warm-up step or local step; it does not itself assert independence across different steps. All integrals are the measure-theoretic integrals from the declaration, with their total-function convention of value zero for a nonintegrable integrand; no separate integrability hypothesis for the two displayed objective-gap or squared-gradient integrands is included in the theorem statement.