Numerical Schemes for Signature Kernels

• URL: http://arxiv.org/abs/2502.08470v1
• Date: Wed, 12 Feb 2025 15:04:23 GMT
• Title: Numerical Schemes for Signature Kernels
• Authors: Thomas Cass, Francesco Piatti, Jeffrey Pei,
• Abstract summary: 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.
• Score: 0.5461938536945723
• License:
• Abstract: Signature kernels have emerged as a powerful tool within kernel methods for sequential data. In the paper "The Signature Kernel is the solution of a Goursat PDE", the authors identify a kernel trick that demonstrates that, for continuously differentiable paths, the signature kernel satisfies a Goursat problem for a hyperbolic partial differential equation (PDE) in two independent time variables. While finite difference methods have been explored for this PDE, they face limitations in accuracy and stability when handling highly oscillatory inputs. In this work, we introduce two advanced numerical schemes that leverage polynomial representations of boundary conditions through either approximation or interpolation techniques, and rigorously establish the theoretical convergence of the polynomial approximation scheme. Experimental evaluations reveal that our approaches yield improvements of several orders of magnitude in mean absolute percentage error (MAPE) compared to traditional finite difference schemes, without increasing computational complexity. Furthermore, like finite difference methods, our algorithms can be GPU-parallelized to reduce computational complexity from quadratic to linear in the length of the input sequences, thereby improving scalability for high-frequency data. We have implemented these algorithms in a dedicated Python library, which is publicly available at: https://github.com/FrancescoPiatti/polysigkernel.

Related papers

• A High Order Solver for Signature Kernels [5.899263357689845]
  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.
  arXiv  Detail & Related papers  (2024-04-01T23:09:52Z)
• 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)
• FaDIn: Fast Discretized Inference for Hawkes Processes with General Parametric Kernels [82.53569355337586]
  This work offers an efficient solution to temporal point processes inference using general parametric kernels with finite support. The method's effectiveness is evaluated by modeling the occurrence of stimuli-induced patterns from brain signals recorded with magnetoencephalography (MEG) Results show that the proposed approach leads to an improved estimation of pattern latency than the state-of-the-art.
  arXiv  Detail & Related papers  (2022-10-10T12:35:02Z)
• Fast Sketching of Polynomial Kernels of Polynomial Degree [61.83993156683605]
  kernel is especially important as other kernels can often be approximated by the kernel via a Taylor series expansion. Recent techniques in sketching reduce the dependence in the running time on the degree oblivious $q$ of the kernel. We give a new sketch which greatly improves upon this running time, by removing the dependence on $q$ in the leading order term.
  arXiv  Detail & Related papers  (2021-08-21T02:14:55Z)
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition [54.07797071198249]
  We introduce a new scalable variational Gaussian process approximation which provides a high fidelity approximation while retaining general applicability. We demonstrate that, on a range of regression and classification problems, our approach can exploit input space symmetries such as translations and reflections. Notably, our approach achieves state-of-the-art results on CIFAR-10 among pure GP models.
  arXiv  Detail & Related papers  (2021-06-10T18:17:57Z)
• SigGPDE: Scaling Sparse Gaussian Processes on Sequential Data [16.463077353773603]
  We develop SigGPDE, a new scalable sparse variational inference framework for Gaussian Processes (GPs) on sequential data. We show that the gradients of the GP signature kernel are solutions of a hyperbolic partial differential equation (PDE) This theoretical insight allows us to build an efficient back-propagation algorithm to optimize the ELBO.
  arXiv  Detail & Related papers  (2021-05-10T09:10:17Z)
• 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)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)

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.