FedExP (Federated Extrapolation for Speeding Up Federated Averaging)

In overparameterized convex settings where clients share a common global minimizer w* with F_i(w*) = 0, Lemma 1 (Section 3, p. 4) proves that tau steps of local gradient descent with eta_l <= 1/L satisfy the quasi-projection inequality <Delta_i^(t), w^(t) - w*> >= 0.5 ||Delta_i^(t)||^2; minimizing the resulting upper bound on ||w^(t) - eta_g^(t) bar_Delta^(t) - w*||^2 yields the extrapolated step size eta_g^(t) = (sum_{i=1}^M ||Delta_i^(t)||^2) / (2 M ||bar_Delta^(t)||^2), which is larger whenever client pseudo-gradients point in diverse directions and automatically decays toward 1 near the optimum.

Theorems 1 and 2 (Section 4, pp. 5-6) establish general convex and non-convex convergence bounds for FedExP where the optimality residual is inversely weighted by the harmonic or arithmetic average of the adaptive server step sizes eta_g^(t) >= 1, guaranteeing progress at least as fast as FedAvg (eta_g = 1).

Under high stochastic mini-batch variance or small client participation M, the denominator ||bar_Delta^(t)||^2 can become dominated by sampling noise near stationarity, requiring a positive stabilization constant epsilon > 0 and decaying local step size eta_l to prevent over-extrapolation (Section 3.2, Section 4).

Applied to federated image classification and language modeling on CIFAR-10, CIFAR-100, CINIC-10, and Shakespeare, accelerating convergence over FedAvg and tuned server-momentum/adaptive baselines without server step-size tuning.