EXTRA (Exact First-Order Algorithm for Decentralized Consensus Optimization)

By introducing U = (tilde_W - W)^{1/2} and auxiliary dual variables q^k = sum_{t=0}^k U x^t so that x^{k+1} = tilde_W x^k - alpha nabla f(x^k) - U q^k and q^{k+1} = q^k + U x^{k+1} (Eq. 14), Lemma 3 proves that (x^*, q^*) satisfies U x^* = 0 and U q^* + alpha nabla f(x^*) = 0 if and only if x_1^* = ... = x_n^* minimizes bar_f(x); for any fixed step size 0 < alpha < 2 lambda_min(tilde_W) / L_f, the G-norm Lyapunov sequence ||z^{k+1} - z^*||_G^2 <= ||z^k - z^*||_G^2 - zeta ||z^k - z^{k+1}||_G^2 with zeta = 1 - alpha L_f / (2 lambda_min(tilde_W)) > 0 guarantees O(1/k) ergodic and o(1/k) running-best convergence of both consensus and optimality residuals for general convex smooth objectives (Theorems 5 and 7).

When the average objective bar_f(x) is restricted strongly convex with respect to x^* (Assumption 3 / Proposition 8, requiring strong convexity only of the mean function bar_f rather than every individual f_i), EXTRA with step size 0 < alpha < 2 mu_g lambda_min(tilde_W) / L_f^2 achieves global Q-linear convergence ||z^{k+1} - z^*||_G^2 <= (1 + delta)^{-1} ||z^k - z^*||_G^2 to the exact consensual optimum (Theorem 9).

Requires static symmetric mixing matrices W and tilde_W satisfying (I + W)/2 >= tilde_W >= W and tilde_W > 0 over an undirected graph, and its exact convergence guarantees apply to deterministic local gradients.

Applied to decentralized least-squares estimation, decentralized Huber loss minimization, and l_2-regularized logistic regression over wireless sensor networks.