Acc-DNGD (Accelerated Distributed Nesterov Gradient Descent)

Because the tracker s_i(t) preserves the exact global gradient average (1/n) sum_{i=1}^n s_i(t) = (1/n) sum_{i=1}^n nabla f_i(y_i(t)) by induction (Lemma 1), the network-averaged iterates bar_x(t), bar_v(t), bar_y(t) evolve as centralized Nesterov accelerated gradient descent perturbed by consensus errors ||y(t) - 1 bar_y(t)|| (Section III-A, Equations 5a-5c), achieving O(1 / t^{1.4 - xi}) objective decay via vanishing step sizes eta_t = eta / (t + t_0)^{0.6 + xi} in Acc-DNGD-NSC (Theorem 1) and O((1 - c sqrt(mu / L))^t) linear convergence with alpha = sqrt(mu eta) in Acc-DNGD-SC when condition number L / mu dominates the spectral gap (Theorem 2, Remark 4).

Bounding the coupled consensus errors ||v(t) - 1 bar_v(t)||, ||y(t) - 1 bar_y(t)||, and tracker error ||s(t) - 1 bar_s(t)|| despite the 1 / alpha_t amplification in v_i(t+1) establishes that choosing step size eta <= O((1 - sigma)^2 / L) keeps the spectral radius of the 4x4 consensus-optimality system strictly below the Nesterov contraction factor 1 - sqrt(mu eta / 2) (Section III-C, Lemmas 7-10).

Requires communicating three d-dimensional vectors (y_j(t), v_j(t), and s_j(t)) per neighbor at each iteration, and for non-strongly convex smooth objectives Acc-DNGD-NSC achieves O(1 / t^{1.4 - xi}) rather than the centralized O(1 / t^2) bound due to consensus-error accumulation.

Applied to ill-conditioned decentralized l_2-regularized logistic regression and smoothed Huber loss minimization over multi-agent sensor networks.