Fastest Mixing Markov Chain on a Graph

By Stephen P. Boyd, Persi Diaconis, Lin Xiao. 2004

814 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistics and Probability, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Statistics and Probability

In Probabilistic & Bayesian Methods

Citations in the corpus

A-NICE-MC: Adversarial Training for MCMC (2017, background): “Defining an objective to improve the performance of MCMC that can be easily optimized in practice over a large parameter space is itself a difficult problem [12, 13].”
On the Convergence of Decentralized Gradient Descent (2013, background): “[4]), one can design a new mixing matrix W = (W̃ + I)/2 that satisfies 1 = λ1(W ) > λ2(W ) ≥ · · · ≥ λn(W ) > 0.”
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, background): “(iii) Metropolis constant edge weight matrix [3,34], for some small positive (cid:15) > 0.”
Random Walks on Simplicial Complexes and the normalized Hodge Laplacian (2018, background): “Markov chains and diffusion are staples of applied mathematics [19,26,70,87].”
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2014, neutral): “(iii) Metropolis constant edge weight matrix [3, 34],”
Adaptive Networks (2014, methodology): “…the probability transition matrix of an irreducible aperiodic Markov chain [44], [133], and using a construction procedure developed in [134] and [135], it was argued in [11] and [58] that one choice for A o is the following policy, which we will refer to as the Hastings rule: The entries of the…”
Mathematical Aspects of Mixing Times in Markov Chains (2006, background): “To make the above problem more interesting and nontrivial, following the work of [10, 11, 77, 66], let us now further impose that we are given an arbitrary graph G = (V,E), with π a probability measure on V as before, and demand that any kernel P has to be zero on the pairs which are not adjacent in”
A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates (2017, neutral): “The mixing matrix W is always chosen with the Metropolis rule (see [57] and [36, Section 2.”
Algebraic Connectivity Ratio of Ramanujan Graphs (2007, background): “This allows design of fast mixing Markov chains for a fixed topology [3].”
Gossip Algorithms (2009, background): “[7] due to its applicability in proving bounds on mixing times for various reversible random walks.”
Design and analysis of distributed averaging with quantized communication (2014, methodology): “date rule of the form xi(k +1) = wiixi(k)+ X j∈N i wijxj(k), ∀i ∈ V, (1) where k is a discrete time index, Ni is the set of neighbors of agent i and the wij are real-valued weights to be designed. In [8] several methods are proposed for choosing the weights wij with the goal of obtaining algorithms ”
Decentralized Federated Averaging (2021, background): “Luckily, the mixingmatrix is non-unique, and we can choose the one whose is the smallest; it has been shown that searching such a mixing matrix can be relaxed as a constrained convex quadratic optimization problem [38].”
Minimizing Effective Resistance of a Graph (2008, neutral): “We describe some extensions in §VII.”
A Proximal Gradient Algorithm for Decentralized Composite Optimization (2015, background): “Typical choices of can be found in [23], [28].”