A High Order Solver for Signature Kernels

• URL: http://arxiv.org/abs/2404.02926v1
• Date: Mon, 1 Apr 2024 23:09:52 GMT
• Title: A High Order Solver for Signature Kernels
• Authors: Maud Lemercier, Terry Lyons,
• Abstract summary: Signature kernels are at the core of several machine learning algorithms for analysing time series. We introduce new algorithms for the numerical approximation of signature kernels.
• Score: 5.899263357689845
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Signature kernels are at the core of several machine learning algorithms for analysing multivariate time series. The kernel of two bounded variation paths (such as piecewise linear interpolations of time series data) is typically computed by solving a Goursat problem for a hyperbolic partial differential equation (PDE) in two independent time variables. However, this approach becomes considerably less practical for highly oscillatory input paths, as they have to be resolved at a fine enough scale to accurately recover their signature kernel, resulting in significant time and memory complexities. To mitigate this issue, we first show that the signature kernel of a broader class of paths, known as \emph{smooth rough paths}, also satisfies a PDE, albeit in the form of a system of coupled equations. We then use this result to introduce new algorithms for the numerical approximation of signature kernels. As bounded variation paths (and more generally geometric $p$-rough paths) can be approximated by piecewise smooth rough paths, one can replace the PDE with rapidly varying coefficients in the original Goursat problem by an explicit system of coupled equations with piecewise constant coefficients derived from the first few iterated integrals of the original input paths. While this approach requires solving more equations, they do not require looking back at the complex and fine structure of the initial paths, which significantly reduces the computational complexity associated with the analysis of highly oscillatory time series.

Related papers

• Numerical Schemes for Signature Kernels [0.5461938536945723]
  Signature kernels have emerged as a powerful tool within kernel methods for sequential data. We introduce two advanced numerical schemes that leverage representations of boundary conditions through either approximation or boundary techniques. Our algorithms can be GPU-parallelized to reduce computational complexity from quadratic to linear in the length of the input sequences.
  arXiv  Detail & Related papers  (2025-02-12T15:04:23Z)
• MultiPDENet: PDE-embedded Learning with Multi-time-stepping for Accelerated Flow Simulation [48.41289705783405]
  We propose a PDE-embedded network with multiscale time stepping (MultiPDENet) In particular, we design a convolutional filter based on the structure of finite difference with a small number of parameters to optimize. A Physics Block with a 4th-order Runge-Kutta integrator at the fine time scale is established that embeds the structure of PDEs to guide the prediction.
  arXiv  Detail & Related papers  (2025-01-27T12:15:51Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose arbitrary exponentials into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions. We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Sparse Cholesky Factorization for Solving Nonlinear PDEs via Gaussian Processes [3.750429354590631]
  We present a sparse Cholesky factorization algorithm for dense kernel matrices. We numerically illustrate our algorithm's near-linear space/time complexity for a broad class of nonlinear PDEs.
  arXiv  Detail & Related papers  (2023-04-03T18:35:28Z)
• Time-marching based quantum solvers for time-dependent linear differential equations [3.1952399274829775]
  The time-marching strategy is a natural strategy for solving time-dependent differential equations on classical computers. We show that a time-marching based quantum solver can suffer from exponentially vanishing success probability with respect to the number of time steps. This provides a path of designing quantum differential equation solvers that is alternative to those based on quantum linear systems algorithms.
  arXiv  Detail & Related papers  (2022-08-14T23:49:19Z)
• DiffPD: Differentiable Projective Dynamics with Contact [65.88720481593118]
  We present DiffPD, an efficient differentiable soft-body simulator with implicit time integration. We evaluate the performance of DiffPD and observe a speedup of 4-19 times compared to the standard Newton's method in various applications.
  arXiv  Detail & Related papers  (2021-01-15T00:13:33Z)
• Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms [65.09383385484007]
  Two timescale approximation (SA) has been widely used in value-based reinforcement learning algorithms. We study the non-asymptotic convergence rate of two timescale linear and nonlinear TDC and Greedy-GQ algorithms.
  arXiv  Detail & Related papers  (2020-11-10T11:36:30Z)
• 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)
• The Signature Kernel is the solution of a Goursat PDE [11.107838656561766]
  We show that for continuously differentiable paths, the signature kernel solves a hyperbolic PDE and recognize the connection with a class of differential equations known in the literature as Goursat problems. This Goursat PDE only depends on the increments of the input sequences, does not require the explicit computation of signatures and can be solved efficiently using state-of-the-arthyperbolic PDE numerical solvers. We empirically demonstrate the effectiveness of our PDE kernel as a machine learning tool in various machine learning applications dealing with sequential data.
  arXiv  Detail & Related papers  (2020-06-26T04:36:50Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)
• Deep-learning of Parametric Partial Differential Equations from Sparse and Noisy Data [2.4431531175170362]
  In this work, a new framework, which combines neural network, genetic algorithm and adaptive methods, is put forward to address all of these challenges simultaneously. A trained neural network is utilized to calculate derivatives and generate a large amount of meta-data, which solves the problem of sparse noisy data. Next, genetic algorithm is utilized to discover the form of PDEs and corresponding coefficients with an incomplete candidate library. A two-step adaptive method is introduced to discover parametric PDEs with spatially- or temporally-varying coefficients.
  arXiv  Detail & Related papers  (2020-05-16T09:09:57Z)

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.