Unifying Optimization and Dynamics to Parallelize Sequential Computation: A Guide to Parallel Newton Methods for Breaking Sequential Bottlenecks
2026-03-17 • Artificial Intelligence
Artificial IntelligenceDistributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors explain how certain math problems used in machine learning, especially those involving sequences, can be solved faster by working on many parts at once, rather than one step at a time. They improved existing methods that were unstable or slow by creating new, more reliable versions based on advanced optimization techniques. They also figured out when these fast, parallel methods will work well by linking the success to a property of the system called the Largest Lyapunov Exponent. Overall, their work helps make some sequential computations quicker and more stable and guides future researchers in this area.
parallel computingNewton's methodquasi-Newton methodstrust-region methodsdynamical systemsfixed-point iterationLargest Lyapunov Exponentmachine learningassociative scanconvergence analysis
Authors
Xavier Gonzalez
Abstract
Massively parallel hardware (GPUs) and long sequence data have made parallel algorithms essential for machine learning at scale. Yet dynamical systems, like recurrent neural networks and Markov chain Monte Carlo, were thought to suffer from sequential bottlenecks. Recent work showed that dynamical systems can in fact be parallelized across the sequence length by reframing their evaluation as a system of nonlinear equations, which can be solved with Newton's method using a parallel associative scan. However, these parallel Newton methods struggled with limitations, primarily inefficiency, instability, and lack of convergence guarantees. This thesis addresses these limitations with methodological and theoretical contributions, drawing particularly from optimization. Methodologically, we develop scalable and stable parallel Newton methods, based on quasi-Newton and trust-region approaches. The quasi-Newton methods are faster and more memory efficient, while the trust-region approaches are significantly more stable. Theoretically, we unify many fixed-point methods into our parallel Newton framework, including Picard and Jacobi iterations. We establish a linear convergence rate for these techniques that depends on the method's approximation accuracy and stability. Moreover, we give a precise condition, rooted in dynamical stability, that characterizes when parallelization provably accelerates a dynamical system and when it cannot. Specifically, the sign of the Largest Lyapunov Exponent of a dynamical system determines whether or not parallel Newton methods converge quickly. In sum, this thesis unlocks scalable and stable methods for parallelizing sequential computation, and provides a firm theoretical basis for when such techniques will and will not work. This thesis also serves as a guide to parallel Newton methods for researchers who want to write the next chapter in this ongoing story.