Communication-Aware Decentralized FMMC Optimization via Edge-Local ADMM and Chebyshev Polynomial Filtering

Abstract

Extended version of a paper on decentralized fastest mixing Markov chain (FMMC) optimization. The method represents the transition matrix through O(|E|) edge variables, splits the graph-feasibility and spectral-box constraints by ADMM, computes the graph projection with an exact distributed consensus ADMM, and computes the spectral update with a matrix-free extreme-spectrum oracle based on Chebyshev polynomial filtering, which requires no Krylov inner products or reorthogonalization. We give convergence conditions for the resulting inexact ADMM, prove threshold and coverage bounds for the approximate spectral update, and identify the two terms that remain unproven for the Chebyshev backend. The experiments include dual-certified accuracy on 46 instances, communication measured in locality-enforced execution, convergence of the matrix-free ADMM on graphs with up to 1,000 nodes, a gap of 1.7e-5 to an independently certified optimum at 50 nodes, memory measurements, and a comparison with the distributed ADMM of Rokade and Kalaimani. Companion report on the graph projection: https://doi.org/10.5281/zenodo.22775365Code: https://github.com/raghuram87/decentralized-fmmc-admm