Strongly convex local-SGD round complexity

Given: The finite-sum objective, its local-SGD trajectory and the step schedule in the Statement.

Local SGD with periodic synchronization: worker updates use independent uniform component indices, average $b$ gradients, and synchronize at the declared times.

One-step progress of the virtual local-SGD iterate: if ${\eta }_t\le 1\mathrm{/}(4L)$, the virtual mean iterate obeys the one-step distance/function-gap inequality there.

Variance reduction across independent local-SGD workers: under the component variance bound, the centered mean stochastic gradient has second moment at most ${\sigma }^2\mathrm{/}(bK)$.

Deviation of local-SGD workers from their virtual mean: under the local-gradient second-moment bound and ${\eta }_s\le 2{\eta }_t$ for the preceding synchronization time, the mean squared worker deviation is at most $4{\eta }_t^2{G}^2{H}^2$.

Quadratic-weighted telescope for a strongly convex recursion: the quadratic-weighted telescope bounds a recurrence with coefficients $A,B,C$ by its stated three terms.

Finite Jensen inequality for convex functions on ${\mathbb{R}}^n$: a convex function at a finite weighted average is bounded above by the same weighted average of its values.

Gradient of a finite sum is the finite sum of gradients and Independent random elements: the mean of a uniform component gradient is $\mathrm{\nabla }f$, and distinct draws are independent.

Expectation of a nonnegative or integrable random variable, Linearity, monotonicity, and the modulus bound for expectation, Expectation agrees with the published finite weighted sum, and The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$: the finite sampling law permits linearity, conditional averaging, and the usual squared-norm expansions.

The hypotheses in the Statement hold at every local iterate, the local steps are positive and nonincreasing, and the run starts with $x_0^k=x_0$.