FedSpeed (Prox-Correction and Extra-Gradient Perturbation for Federated Learning)

A non-convex federated optimization algorithm (Sun et al. 2023, Sections 3-4, Equations 2-5, Algorithm 1, Theorem 4.4, Corollary 4.5) that enables large local training intervals K = O(T) and O(1/T) communication-round convergence without assuming exact local subproblem minimization by combining: (1) an extra-gradient ascent perturbation that merges the current stochastic gradient g_{i,k,1}^t = nabla F_i(x_{i,k}^t; xi_{i,k}^t) and the neighborhood ascent gradient g_{i,k,2}^t = nabla F_i(x_{i,k}^t + rho * g_{i,k,1}^t; xi_{i,k}^t) into the quasi-gradient g~_{i,k}^t = (1 - alpha)*g_{i,k,1}^t + alpha*g_{i,k,2}^t (Appendix A Equation 10); (2) a local update step x_{i,k+1}^t = x_{i,k}^t - eta_l * (g~_{i,k}^t + (1/lambda)*(x_{i,k}^t - x_{i,0}^t) - g^hat_i^{t-1}) (Algorithm 1 Line 11); and (3) a prox-correction momentum update g^hat_i^t = g^hat_i^{t-1} - (1/lambda)*(x_{i,K}^t - x_{i,0}^t) = (1 - gamma)*g^hat_i^{t-1} + sum_{k=0}^{K-1} gamma_k * g~_{i,k}^t (Lemma C.2, Equation 3) with post-processed client parameter upload x^hat_i^t = x_{i,K}^t - lambda * g^hat_i^t (Algorithm 1 Line 14).