Massively Parallel Exact Inference for Hawkes Processes

• URL: http://arxiv.org/abs/2604.01342v1
• Date: Wed, 01 Apr 2026 19:52:25 GMT
• Title: Massively Parallel Exact Inference for Hawkes Processes
• Abstract summary: We show that the Hawkes process intensity can be expressed as a product of sparse transition matrices admitting a linear-time associative multiply.<n>This yields a simple yet massively parallelizable algorithm for maximum likelihood estimation of linear exponential Hawkes processes.<n>We demonstrate orders-of-speedups on simulated and real datasets, scaling to thousands of nodes and tens of millions of events.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multivariate Hawkes processes are a widely used class of self-exciting point processes, but maximum likelihood estimation naively scales as $O(N^2)$ in the number of events. The canonical linear exponential Hawkes process admits a faster $O(N)$ recurrence, but prior work evaluates this recurrence sequentially, without exploiting parallelization on modern GPUs. We show that the Hawkes process intensity can be expressed as a product of sparse transition matrices admitting a linear-time associative multiply, enabling computation via a parallel prefix scan. This yields a simple yet massively parallelizable algorithm for maximum likelihood estimation of linear exponential Hawkes processes. Our method reduces the computational complexity to approximately $O(N/P)$ with $P$ parallel processors, and naturally yields a batching scheme to maintain constant memory usage, avoiding GPU memory constraints. Importantly, it computes the exact likelihood without any additional assumptions or approximations, preserving the simplicity and interpretability of the model. We demonstrate orders-of-magnitude speedups on simulated and real datasets, scaling to thousands of nodes and tens of millions of events, substantially beyond scales reported in prior work. We provide an open-source PyTorch library implementing our optimizations.

Related papers

• Accelerating Discrete Diffusion Models with Parallel-In-Time Sampling [55.388363730120325]
  We parallelize the mainstream $$-leaping algorithm for absorbing discrete diffusion in a Continuous-Time Markov Chain (CTMC) framework.<n>By leveraging the continuous-time integral form of the $$-leaping algorithm and the Picard method, we achieve parallel-in-time sampling acceleration.<n>Our research expands the potential of discrete diffusion models for efficient parallel inference, with broader implications for applications such as molecular structure and language generation.
  arXiv  Detail & Related papers  (2026-07-01T10:59:33Z)
• GraphGP: Scalable Gaussian Processes with Vecchia's Approximation [0.0]
  Vecchia's approximation is a sparse precision matrix approximation for stationary, decaying kernels.<n>We present GraphGP, an algorithm for Vecchia's approximation that scales to nearly a billion parameters with linear time and memory requirements.
  arXiv  Detail & Related papers  (2026-06-09T19:50:27Z)
• Optimal quantum simulation of linear non-unitary dynamics [0.31439717339537293]
  We present a quantum algorithm for simulating the time evolution generated by any bounded, time-dependent operator $-A$.<n>Our method generalizes the recent Linear-Combination-of-Hamiltonian-Simulation (LCHS) framework.
  arXiv  Detail & Related papers  (2025-08-26T17:58:27Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples. We show that our SSN method achieves a global convergence rate of $O (1/sqrtk)$, and a local quadratic convergence rate under standard regularity conditions.
  arXiv  Detail & Related papers  (2023-10-21T18:48:45Z)
• Decreasing the Computing Time of Bayesian Optimization using Generalizable Memory Pruning [56.334116591082896]
  We show a wrapper of memory pruning and bounded optimization capable of being used with any surrogate model and acquisition function. Running BO on high-dimensional or massive data sets becomes intractable due to this time complexity. All model implementations are run on the MIT Supercloud state-of-the-art computing hardware.
  arXiv  Detail & Related papers  (2023-09-08T14:05:56Z)
• Sublinear scaling in non-Markovian open quantum systems simulations [0.0]
  We introduce a numerically exact algorithm to calculate process tensors. Our approach requires only $mathcalO(nlog n)$ singular value decompositions for environments with infinite memory.
  arXiv  Detail & Related papers  (2023-04-11T15:40:33Z)
• Softmax-free Linear Transformers [90.83157268265654]
  Vision transformers (ViTs) have pushed the state-of-the-art for visual perception tasks. Existing methods are either theoretically flawed or empirically ineffective for visual recognition. We propose a family of Softmax-Free Transformers (SOFT)
  arXiv  Detail & Related papers  (2022-07-05T03:08:27Z)
• Strong Simulation of Linear Optical Processes [2.3131309703965135]
  Given $n$ photons at the input of an $m$-mode interferometer, our algorithm computes the probabilities of all possible output states. It outperforms the permanent-based method by an exponential factor.
  arXiv  Detail & Related papers  (2022-06-21T17:27:17Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  We consider online statistical inference of constrained nonlinear optimization problems.<n>We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
  arXiv  Detail & Related papers  (2022-05-27T00:34:03Z)
• Mixability made efficient: Fast online multiclass logistic regression [68.8204255655161]
  We show that mixability can be a powerful tool to obtain algorithms with optimal regret. The resulting methods often suffer from high computational complexity which has reduced their practical applicability.
  arXiv  Detail & Related papers  (2021-10-08T08:22:05Z)
• Sub-Linear Memory: How to Make Performers SLiM [38.068090269482425]
  vanilla Transformers require $O(L2)$ in serial time and memory as functions of input length $L$. Recent works proposed various linear self-attention mechanisms, scaling only as $O(L)$ for serial computation. We observe a remarkable computational flexibility: forward and backward propagation can be performed with no approximations using sublinear memory.
  arXiv  Detail & Related papers  (2020-12-21T13:56:04Z)
• 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.