Unifying Optimization and Dynamics to Parallelize Sequential Computation: A Guide to Parallel Newton Methods for Breaking Sequential Bottlenecks

• URL: http://arxiv.org/abs/2603.16850v1
• Date: Tue, 17 Mar 2026 17:55:01 GMT
• Title: Unifying Optimization and Dynamics to Parallelize Sequential Computation: A Guide to Parallel Newton Methods for Breaking Sequential Bottlenecks
• Abstract summary: We develop scalable and stable parallel Newton methods based on quasi-Newton and trust-region approaches.<n>We establish a linear convergence rate for fixed-point methods that depends on the method's approximation accuracy and stability.<n>We give a precise condition, rooted in dynamical stability, that characterizes when parallelization provably accelerates a dynamical system and when it cannot.
• Score: 1.2691047660244335
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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.

Related papers

• Federated stochastic bilevel optimization with fully first-order gradients [57.1147486991903]
  Federated matrices bilevel optimization has been actively studied in recent years due to its widespread applications in machine learning.<n>Most existing federated bilevel optimization algorithms require the computation of second-order Hessian and Jacobian matrices.<n>We propose a novel federated convergence variance-reduced bilevel descent algorithm that relies solely on first-order oracles.
  arXiv  Detail & Related papers  (2026-09-14T21:12:59Z)
• PRISM: Parallel Residual Iterative Sequence Model [52.26239951489612]
  We propose PRISM (Parallel Residual Iterative Sequence Model) to resolve this tension.<n>PRISM introduces a solver-inspired inductive bias that captures key structural properties of multi-step refinement in a parallelizable form.<n>We prove that this formulation achieves Rank-$L$ accumulation, structurally expanding the update manifold beyond the single-step Rank-$1$ bottleneck.
  arXiv  Detail & Related papers  (2026-02-11T12:39:41Z)
• A Unifying Framework for Parallelizing Sequential Models with Linear Dynamical Systems [41.44667250045256]
  Several approaches have been proposed for evaluating sequential processes in parallel using fixed-point methods.<n>We show that these methods can be understood within a common framework based on linear dynamical systems.<n>This unifying view highlights shared principles behind these techniques and clarifies when particular fixed-point methods are most likely to be effective.
  arXiv  Detail & Related papers  (2025-09-26T00:27:02Z)
• Towards Scalable and Stable Parallelization of Nonlinear RNNs [13.705742451466225]
  We develop an approach called DEER, which evaluates nonlinear RNNs in parallel by posing the states as the solution to a fixed-point problem.<n>We apply quasi-Newton approximations and show they converge comparably to Newton, use less memory, and are faster.<n>These innovations allow for parallel evaluation of nonlinear RNNs at larger scales and with greater stability.
  arXiv  Detail & Related papers  (2024-07-26T22:38:11Z)
• A fast neural hybrid Newton solver adapted to implicit methods for nonlinear dynamics [6.642649934130245]
  We propose a novel deep learning based hybrid Newton's method to accelerate this solution of the nonlinear time step system for stiff time-evolution nonlinear equations.<n>A quantifiable rate of improvement in Newton's method is provided and we analyse the upper bound of the generalisation error of our unsupervised learning strategy.
  arXiv  Detail & Related papers  (2024-07-04T14:02:10Z)
• Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates [50.36933471975506]
  We consider the finite-sum optimization problem, where each component function is strongly convex and has Lipschitz continuous gradient and Hessian. The recently proposed incremental quasi-Newton method is based on BFGS update and achieves a local superlinear convergence rate. This paper proposes a more efficient quasi-Newton method by incorporating the symmetric rank-1 update into the incremental framework.
  arXiv  Detail & Related papers  (2024-02-04T05:54:51Z)
• Guaranteed Conservation of Momentum for Learning Particle-based Fluid Dynamics [96.9177297872723]
  We present a novel method for guaranteeing linear momentum in learned physics simulations. We enforce conservation of momentum with a hard constraint, which we realize via antisymmetrical continuous convolutional layers. In combination, the proposed method allows us to increase the physical accuracy of the learned simulator substantially.
  arXiv  Detail & Related papers  (2022-10-12T09:12:59Z)
• Newton methods based convolution neural networks using parallel processing [3.9220281834178463]
  Training of convolutional neural networks is a high dimensional and a non- parametric optimization problem. Newton methods for convolutional neural networks deals with this by using sub-sampled Hessian Newton methods. We have used parallel processing instead of serial processing in mini-batch computations.
  arXiv  Detail & Related papers  (2021-12-02T16:42:27Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. We show that the Gaussian sketching matrix can be drastically sparsified, significantly reducing the computational cost of sketching. We prove that Newton-LESS enjoys nearly the same problem-independent local convergence rate as Gaussian embeddings.
  arXiv  Detail & Related papers  (2021-07-15T17:33:05Z)
• Parallelization Techniques for Verifying Neural Networks [52.917845265248744]
  We introduce an algorithm based on the verification problem in an iterative manner and explore two partitioning strategies. We also introduce a highly parallelizable pre-processing algorithm that uses the neuron activation phases to simplify the neural network verification problems.
  arXiv  Detail & Related papers  (2020-04-17T20:21:47Z)
• Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving [106.63673243937492]
  Feedforward computation, such as evaluating a neural network or sampling from an autoregressive model, is ubiquitous in machine learning. We frame the task of feedforward computation as solving a system of nonlinear equations. We then propose to find the solution using a Jacobi or Gauss-Seidel fixed-point method, as well as hybrid methods of both. Our method is guaranteed to give exactly the same values as the original feedforward computation with a reduced (or equal) number of parallelizable iterations, and hence reduced time given sufficient parallel computing power.
  arXiv  Detail & Related papers  (2020-02-10T10:11:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.