Computing Stationary Distribution via Dirichlet-Energy Minimization by Coordinate Descent

Konstantin Avrachenkov, Lorenzo Gregoris, Nelly Litvak · 2026

Read Computing Stationary Distribution via Dirichlet-Energy Minimization by Coordinate Descent by Konstantin Avrachenkov, Lorenzo Gregoris, Nelly Litvak (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-06391.txt.

Introduction

Avrachenkov, Gregoris, and Litvak frame the Red Light Green Light algorithm as an optimization problem that computes steady distributions of large Markov chains. This view shows how the algorithm behaves step by step and proves exponential convergence for one class of chains. It gives useful scheduling plans that speed it up in practice for large chains.

Catalog record

CREATORKonstantin Avrachenkov, Lorenzo Gregoris, Nelly Litvak
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68738
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.06391

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Computing Stationary Distribution via Dirichlet-Energy Minimization by Coordinate Descent Konstantin Avrachenkov, Lorenzo Gregoris, Nelly Litvak Abstract We present an optimization-based formulation of the Red Light Green Light (RLGL) [ 2 ] algorithm for computing stationary distributions of large Markov chains. This perspective clarifies the algorithm’s behavior, establishes exponential convergence for a class of chains, and suggests practical scheduling strategies to accelerate convergence. 1 Introduction Computing the stationary distribution of a Markov chain is a fundamental task with applications ranging from queueing systems, performance evaluation, and chemical networks, to large-scale problems such as PageRank [ 5 ] , semi-supervised learning [ 3 ] , and graph neural networks [ 7 , 4 ] . Formally, the task is to solve the eigenvector problem \pi P=\pi for a transition probability matrix P . In many of these real world settings, a Markov chain may have billions of possible states, making direct numerical methods infeasible and leaving iterative algorithms as the only practical option. Iterative algorithms start with a guess solution \hat{\pi}_{0} , and generate recursively a sequence \{\hat{\pi}_{t}\}_{t\geq 0} , at each step updating the coordinates of \hat{\pi}_{t} , with the goal of eventually converging to the solution \pi . A large class of such iterative algorithms update their estimate using the residual r_{t}=\hat{\pi}_{t}(P-I). (1) Usually, the stopping condition involves some norm of the residual, i.e. we stop when \|r_{t}\|\leq\varepsilon for some \varepsilon>0 . Examples include OPIC [ 1 ] , Gauss–Southwell-type PageRank algorithms [ 13 ] , and more generally a variety of residual-elimination methods [ 10 ] . The RLGL (“Red Light Green Light”) algorithm [ 2 ] is a recent unifying framework for many iterative approaches. In RLGL, only a subset of coordinates is updated at each iteration according to a chosen schedule (following the terminology in [ 2 ] , the updated coordinates receive a “green light”, thus the name of the algorithm). Different schedules and initializations correspond to many of the classical algorithms cited above. RLGL is remarkably simple and performs extremely well in practice, but proving convergence guarantees for the best performing schedules has been challenging. Nonetheless, in the experiments, RLGL consistently outperforms many known algorithms, including state of the art Krylov subspace methods such as GMRES [ 15 ] . Another classical approach for stationary distribution computation is reformulating the eigenvector problem as a minimization problem of the least-squares objective f(x)=\frac{1}{2}\|x(P-I)\|^{2}, (2) for some norm \|\cdot\| . Then f is a convex function minimized at the solutions of the linear system, and we can apply the well-established theory for this class of optimization problems. The simplest class of iterative optimization algorithms are first-order methods [ 19 ] , which use gradient information to update the current estimate. There are drawbacks when applying first-order methods to minimize the least-squares objective function ( 2 ). For instance, the gradient reads \nabla f(x)=x(P-I)(P-I)^{\top}, (3) which depends not only on P , but also depends on PP^{\top} and P^{\top} . This could be a problem because even if P is sparse, PP^{\top} may not be (an effect known as fill-in [ 16 , Section 3.3.2] . A way to address this is to avoid forming PP^{\top} explicitly and instead compute (xP)P^{\top} through two sparse matrix–vector multiplications. While this only doubles the cost per iteration, the condition number of PP^{\top} is the square of that of P , which can slow down convergence. Finally, in applications like PageRank where accessing out-neighbors is cheaper than in-neighbors, approaches whose gradients (or updates) depend only on P and not on P^{\top} , are operationally attractive. Another formulation as an optimization problem applies to the special case when the matrix A of a linear system Ax=b is symmetric positive semi-definite. Under this assumption, one can construct a convex objective function, of which the gradient depends linearly on A : \Phi(x)=\frac{1}{2}x^{\top}Ax-b^{\top}x. (4) This is usually referred to as the energy function of the linear system. This formulation is the starting point of the conjugate-gradient method and other techniques for solving positive semi-definite linear systems [ 8 ] . The power of this approach is in the fact that the gradient of the energy function is \nabla\Phi(x_{t})=Ax_{t}-b=-r_{t}. (5) Relation ( 5 ) bridges the optimization algorithms based on the gradient, and the iterative algorithms based on the residual. The limitation of this approach for stationary distribution computations is that, in general, transition matrices are not symmetric (in this trivial case the stationary distribution is uniform). Therefore, the conjugate-gradient framework is not directly applicable. The RLGL algorithm however, uses linear updates in the transition matrix P , suggesting there may exist an objective function of the form ( 4 ), for which a coordinate descent method produces similar updates and converges exponentially fast. Contributions. In this paper, we provide partial theoretical explanation for the strong empirical performance of RLGL. Our main results are: 1. Variational formulation. We show that when P is similar to a symmetric matrix—for example, for reversible Markov chains—the stationary distribution problem admits an energy formulation based on the Dirichlet energy . In this setting, RLGL corresponds to a block coordinate descent method that minimizes this energy. 2. Exponential convergence for nearly reversible chains. Using this energy viewpoint, we prove that RLGL converges exponentially fast for a class of chains we call nearly reversible , with minimal assumption on the update schedule. This extends the previously known special cases in [ 2 ] . 3. Energy inspired heuristics. The variational formulation yields new coordinate selection rules that provably maximizes the decrease in energy at each step, which we call Gauss-Southwell-Dirichlet heuristics. We show that these rules outperform the previously known heuristics. Outline of the paper. In Section 2 we start by introducing the notation, and give brief preliminaries on Markov chains, the RLGL algorithm, the Dirichlet energy of a Markov Chain, and coordinate descent methods to minimize convex functions. In Section 3 we prove the equivalence of RLGL to coordinate descent in the case when the transition matrix is similar to a symmetric matrix. In Section 4 we extend these ideas by viewing a general irreversible Markov chain as a perturbed reversible chain. By doing so, we obtain spectral conditions that, when satisfied, guarantee exponential convergence. Finally, in Section 5 , we propose new energy-inspired heuristics, and we compare them with baseline heuristics for computation of the stationary distribution and the PageRank computation on both real and synthetic networks. 2 Preliminaries This section recollects the main tools used in the paper, linking the probabilistic and optimization viewpoints. We first fix notation and recall basic facts on Markov chains, stationary distribution and reversibility. We then introduce the RLGL algorithm, a block-coordinate analogue of power iteration. Finally, we discuss the graph Laplacian and the Dirichlet energy, which provide the variational framework to interpret RLGL as a coordinate descent method. 2.1 Notation and conventions We adopt the row vector convention for Markov chains: probability distributions are represented as row vectors \pi\in\mathbb{R}^{n} satisfying \pi\mathbf{1}^{\top}=1 , where \mathbf{1}\in\mathbb{R}^{n} denotes the all-ones row vector. A matrix P\in\mathbb{R}^{n\times n} is called row stochastic if P\mathbf{1}^{\top}=\mathbf{1}^{\top} and P_{ij}\geq 0 for all i,j . For a positive integer n , we write [n]:=\{1,2,\dots,n\} . We denote by \{e_{i}\}_{i=1}^{n} the standard basis of \mathbb{R}^{n}

Read the complete text