FedLin (Federated Linearized Learning with Client Heterogeneity and Gradient Sparsification)

On heterogeneous quadratics f_i(x) = (1/2)(x - c_i)^T A_i (x - c_i), Propositions 1 and 2 prove that FedProx and FedNova converge to distorted surrogate minimizers weighted by Q_i = sum_{l=0}^{tau_i-1} [I - eta(A_i + beta I)]^l (Eqs. 5, 7, 9, 10), whereas FedLin (Algorithm 1) with eta_i = bar_eta / tau_i satisfies the exact fixed-point property x_{i,l}^{(t)} = x^* whenever bar_x_t = x^* and achieves global linear convergence f(bar_x_{T+1}) - f(x^*) <= (1 - 1 / (6 kappa))^T (f(bar_x_1) - f(x^*)) under arbitrary objective and systems heterogeneity (Theorem 1), matching a 2-client lower bound proving that local steps H cannot eliminate the kappa condition-number dependence (Theorem 6, Appendix E).

Under contractive TOP-k gradient sparsification with parameter delta = d / k, FedLin reveals a fundamental asymmetry between server-side and client-side compression (Section 4): server-side sparsification converges linearly to the exact optimum x^* even without error feedback at rate 1 - mu / (2 (delta_s + sqrt(delta_s)) delta_s L) (Theorem 7) and improves to 1 - 1 / (96 kappa delta_s) with server error feedback (Theorem 8) because ||nabla f(bar_x_t)|| -> 0 at x^*, whereas client-side sparsification with error feedback converges linearly only to an O(delta_c D^2) neighborhood proportional to heterogeneity D^2 when nabla f_i(x^*) != 0 (Theorem 9, Corollary 1).

Computing the fresh global gradient g_t = (1/m) sum_{i=1}^m nabla f_i(bar_x_t) requires an extra gradient-aggregation round per epoch, and stochastic noise in local mini-batch gradients reintroduces an O(bar_eta sigma^2) variance floor (Theorem 4).

Applied to heterogeneous federated logistic regression and neural network classification on MNIST and CIFAR-10 under non-IID client partitions and random local iteration counts tau_i.