Exact Diffusion (Adapt-Correct-Combine Distributed Optimization)

When the left-stochastic combination matrix A (A^T 1 = 1, A p = p) satisfies local detailed balance P A^T = A P with P = diag(p) (Definition 1, Eq. 16), P - A P is symmetric positive semidefinite with nullspace span(1_N) (Lemmas 1-2) and admits the spectral factorization (P (I_N - A^T)) / 2 = V B^T B V^T (Eq. 40); applying incremental primal-dual steps to the penalized augmented Lagrangian yields the ACC recursion (Algorithm 1), which preserves p^T w_i = p^T psi_i for all i >= 1 and guarantees exact consensus at the global weighted minimizer w^* = argmin_w sum_{k=1}^N q_k J_k(w) (Section IV, Lemmas 4-5).

Because Exact Diffusion mixes the gradient difference through bar_A^T before combining (Eq. 103) whereas EXTRA leaves the gradient term unmixed (Eq. 104), its primal-dual dynamics involve bar_A^T (I_N - M H) rather than (I_N - M H), providing a strictly wider step-size stability range than EXTRA on symmetric graphs (Section V-A); conversely, if A is a primitive left-stochastic matrix that violates local balance (P A^T != A P), complex eigenvalues of A can force the error transition matrix to have spectral radius > 1 for all small step-sizes mu > 0 under ill-conditioned local Hessians (Section V-C, Example 1, Appendix A).

Requires the left-stochastic combination policy A to satisfy local balance p_k a_{lk} = p_l a_{kl} (such as Metropolis, Hastings, or degree-proportional rules on undirected topologies) and requires each agent k to store its previous intermediate state psi_{k,i-1} and iterate w_{k,i-1}.

Applied to distributed least-squares estimation and regularized logistic regression over multi-agent networks using locally balanced left-stochastic combination rules without doubly stochastic weight design.