Xavier Gonzalez
Stanford University
3:30 PM
154 Hurley Hall
Parallelizing Markov Processes with Newton's Method
Modern accelerators like GPUs thrive on parallel work. Yet many core algorithms with the Markov property---such as recurrent neural networks (RNNs) and Markov chain Monte Carlo (MCMC)---are usually run step-by-step. Recent work (Danieli et al.; Lim et al., 2023) parallelized Markov processes by recasting them as nonlinear equations and solving them with Newton’s method. I will show how to make this idea practical. First, I introduce two methods inspired by quasi-Newton and trust-region strategies that cut computation and improve robustness. Second, I prove how the stability of a dynamical system, as measured by its Largest Lyapunov Exponent (LLE), determines whether or not Newton's method converges quickly in this problem and should be used. The talk connects root-finding, optimization, and dynamical systems, and illustrates the results on RNNs and MCMC.
View Poster
Originally published at acms.nd.edu.