FedNova Normalized Averaging for Heterogeneous Federated Optimization

A heterogeneous federated optimization framework and normalized averaging algorithm (FedNova) that models client i's cumulative local model change over tau_i^{(t)} local steps as Delta_i^{(t)} = x_i^{(t,tau_i)} - x^{(t,0)} = -eta * G_i^{(t)} * a_i^{(t)}, where G_i^{(t)} in R^{d x tau_i} stacks the local stochastic gradients and a_i^{(t)} in R^{tau_i} is the local solver's gradient weighting vector (a_i = [1,...,1]^T for vanilla SGD, a_i = [(1-alpha)^{tau_i-1},...,1]^T for proximal SGD, and a_i = [1-rho^{tau_i},...,1-rho]^T/(1-rho) for momentum SGD), normalizes each client's update into an effective local gradient d_i^{(t)} = G_i^{(t)} a_i^{(t)} / ||a_i^{(t)}||_1 = -Delta_i^{(t)} / (eta * ||a_i^{(t)}||_1), and aggregates across clients with weights w_i = p_i and effective global step size tau_eff^{(t)} (defaulting to sum_{i=1}^m p_i ||a_i^{(t)}||_1) via x^{(t+1,0)} = x^{(t,0)} - tau_eff^{(t)} * sum_{i=1}^m p_i * eta * d_i^{(t)}, eliminating the surrogate objective inconsistency chi^2_{p||w} = sum_{i=1}^m (p_i - w_i)^2 / w_i caused by heterogeneous local step counts tau_i or heterogeneous local solvers while achieving O(1/sqrt(m * tau_tilde * T)) convergence to stationary points of the true global objective F(x) = sum_{i=1}^m p_i F_i(x).