Towards Scalable and Stable Parallelization of Nonlinear RNNs

• URL: http://arxiv.org/abs/2407.19115v3
• Date: Wed, 15 Jan 2025 19:18:35 GMT
• Title: Towards Scalable and Stable Parallelization of Nonlinear RNNs
• Abstract summary: 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.
• Score: 13.705742451466225
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Transformers and linear state space models can be evaluated in parallel on modern hardware, but evaluating nonlinear RNNs appears to be an inherently sequential problem. Recently, however, Lim et al. '24 developed an approach called DEER, which evaluates nonlinear RNNs in parallel by posing the states as the solution to a fixed-point problem. They derived a parallel form of Newton's method to solve the fixed-point problem and achieved significant speedups over sequential evaluation. However, the computational complexity of DEER is cubic in the state size, and the algorithm can suffer from numerical instability. We address these limitations with two novel contributions. To reduce the computational complexity, we apply quasi-Newton approximations and show they converge comparably to Newton, use less memory, and are faster. To stabilize DEER, we leverage a connection between the Levenberg-Marquardt algorithm and Kalman smoothing, which we call ELK. This connection allows us to stabilize Newton's method while using efficient parallelized Kalman smoothing algorithms to retain performance. Through several experiments, we show that these innovations allow for parallel evaluation of nonlinear RNNs at larger scales and with greater stability.

Related papers

• Unifying Optimization and Dynamics to Parallelize Sequential Computation: A Guide to Parallel Newton Methods for Breaking Sequential Bottlenecks [1.2691047660244335]
  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.
  arXiv  Detail & Related papers  (2026-03-17T17:55:01Z)
• Provably Efficient Quantum Algorithms for Solving Nonlinear Differential Equations Using Multiple Bosonic Modes Coupled with Qubits [9.366500214140164]
  We present an analog, continuous-variable algorithm based on bosonic modes with qubit-based adaptive measurements that avoids Hilbert-space digitization.<n>Unlike many analog schemes, the algorithm is provably efficient: advancing a first-order, $L$-grid point, $d$-dimensional, order-$K$ spatial-derivative, degree-$r$-nonline.
  arXiv  Detail & Related papers  (2025-11-13T04:09:32Z)
• ParaRNN: Unlocking Parallel Training of Nonlinear RNNs for Large Language Models [9.107447466062409]
  ParaRNN is a framework that breaks the sequence-parallelization barrier for nonlinear RNNs.<n>Our implementation achieves speedups of up to 665x over sequential application.<n>ParaRNN is released as an open-source framework for automatic training-parallelization of nonlinear RNNs.
  arXiv  Detail & Related papers  (2025-10-24T13:28:33Z)
• A Truncated Newton Method for Optimal Transport [13.848861021326755]
  We introduce a specialized truncated Newton algorithm for entropic-regularized optimal transport (OT) solvers. Our algorithm exhibits exceptionally favorable runtime performance, achieving high precision orders of magnitude faster than many existing alternatives. The scalability of the algorithm is showcased on an extremely large OT problem with $n approx 106$, solved approximately under weak entopric regularization.
  arXiv  Detail & Related papers  (2025-04-02T19:00:24Z)
• Symmetric Rank-One Quasi-Newton Methods for Deep Learning Using Cubic Regularization [0.5120567378386615]
  First-order descent and other first-order variants, such as Adam and AdaGrad, are commonly used in the field of deep learning. However, these methods do not exploit curvature information. Quasi-Newton methods re-use previously computed low Hessian approximations.
  arXiv  Detail & Related papers  (2025-02-17T20:20:11Z)
• Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence [20.766358513158206]
  We prove a global convergence rate of $O(min1/k,sqrtd/k1.25)$ in terms of the duality gap. These results are the first global convergence results to demonstrate a provable advantage of a quasi-Newton method over the extragradient method.
  arXiv  Detail & Related papers  (2024-10-03T16:08:16Z)
• A fast neural hybrid Newton solver adapted to implicit methods for nonlinear dynamics [6.642649934130245]
  We propose a novel operator learning based hybrid Newton's method to accelerate this solution of the nonlinear time step system for stiff time-evolution nonlinear equations. 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)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Smoothing ADMM for Sparse-Penalized Quantile Regression with Non-Convex Penalties [8.294148737585543]
  This paper investigates concave and clipped quantile regression in the presence of nonsecondary absolute and non-smooth convergence penalties. We introduce a novel-loop ADM algorithm with an increasing penalty multiplier, named SIAD, specifically for sparse regression.
  arXiv  Detail & Related papers  (2023-09-04T21:48:51Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  We develop an adaptive inexact Newton method for equality-constrained nonlinear, nonIBS optimization problems. We demonstrate the superior performance of our method on benchmark nonlinear problems, constrained logistic regression with data from LVM, and a PDE-constrained problem.
  arXiv  Detail & Related papers  (2023-05-28T06:33:37Z)
• Second-order optimization with lazy Hessians [55.51077907483634]
  We analyze Newton's lazy Hessian updates for solving general possibly non-linear optimization problems. We reuse a previously seen Hessian iteration while computing new gradients at each step of the method.
  arXiv  Detail & Related papers  (2022-12-01T18:58:26Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  We consider a smooth and strongly convex objective function using a Newton method. We show that there exists a universal weighted averaging scheme that transitions to local convergence at an optimal stage.
  arXiv  Detail & Related papers  (2022-04-20T07:14:21Z)
• 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)
• Online Limited Memory Neural-Linear Bandits with Likelihood Matching [53.18698496031658]
  We study neural-linear bandits for solving problems where both exploration and representation learning play an important role. We propose a likelihood matching algorithm that is resilient to catastrophic forgetting and is completely online.
  arXiv  Detail & Related papers  (2021-02-07T14:19:07Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems [26.24895953952318]
  We develop an algorithm to solve a class of non-gence minimax problems. They can also work with both single or two mini-batch derivatives.
  arXiv  Detail & Related papers  (2020-06-27T03:05:18Z)
• 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.