2008/03/25 by Hariharan Narayanan, Narayanan, Hariharan
Computer Science · #Complexity and Algorithms in Graphs #Distributed #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.0803.3642
8 pages
openalex publication_date 2008/03/25 · arxiv created 2008/04/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the question of averaging on a graph that has one sparse cut separating two subgraphs that are internally well connected. While there has been a large body of work devoted to algorithms for distributed averaging, nearly all algorithms involve only \it convex updates. In this paper, we suggest that \it non-convex updates can lead to significant improvements. We do so by exhibiting a decentralized algorithm for graphs with one sparse cut that uses non-convex averages and has an averaging time that can be significantly smaller than the averaging time of known distributed algorithms, such as those of \citetsitsiklis, Boyd. We use stochastic dominance to prove this result in a way that may be of independent interest.