Computational aspects of the Volterra Signature

• URL: http://arxiv.org/abs/2605.18406v1
• Date: Mon, 18 May 2026 13:46:47 GMT
• Title: Computational aspects of the Volterra Signature
• Abstract summary: We introduce efficient algorithms for the Volterra signature kernel.<n>All algorithms are implemented in the publicly available JAX-based package "tensordev"<n>We show that the number of factors in matrix-valued kernels of the form $K(t,s)=sum_p k_p(t-s)A_p$ do not increase the complexity in $J$ and $N$.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Volterra signature extends the classical path signature by incorporating general matrix-valued kernel into its iterated integral structure, yielding a flexible notion of memory for time series. Its components can be viewed as successive Picard iterates of linear controlled Volterra equations, making their exact computation of additional mathematical interest. However, the kernel introduces substantial algorithmic challenges. We provide a resolution by first decomposing the Chen-type convolution relation established in [arXiv:2603.04525] into analytic and arithmetic parts, and then introducing several efficient algorithms: a general approximative scheme with quadratic complexity $O(J^2)$ in the number of time steps $J$, an FFT-based acceleration with complexity $O(J\log J)$ for convolution kernels on uniform grids, and an exact recursion with complexity $O(JR^2)$ for kernels admitting a state-space representation of dimension $R$; retaining standard signature complexity in the path dimension and truncation level $N$. We further show that the number of factors in matrix-valued kernels of the form $K(t,s)=\sum_p k_p(t-s)A_p$ do not increase the asymptotic complexity in $J$ and $N$. Finally, we derive a finite-difference predictor--corrector scheme for the associated Volterra signature kernel. All algorithms are implemented in the publicly available JAX-based package "tensordev".

Related papers

• Fast Bounded-Independence Functions and Their Duals [21.031497777539332]
  Motivated by cryptographic applications, we generalize and improve on previous results in this area.<n>We demonstrate the usefulness of the above results to cryptography.<n>This includes the first nontrivial protocols for perfectly secure multiparty computation.
  arXiv  Detail & Related papers  (2026-06-05T07:53:04Z)
• Near-Optimal Regret in Adversarial Kernel Bandits [50.68324062892194]
  We study the adversarial kernel bandit problem, in which the loss at each round is induced by an arbitrary bounded element.<n>Our main result bounds the regret by $widetildeObig(sqrtT, d_*(),log|X|big)$, where $d_*()$ is a widely-adopted notion of effective dimension.
  arXiv  Detail & Related papers  (2026-05-26T06:10:24Z)
• Classical and Quantum Algorithms for Topological Invariants of Torus Bundles [0.42970700836450476]
  We exploit the non-commutative torus structure to embed the skein algebra of the closed torus into its symmetric subalgebra at roots of unity.<n>We prove that extracting individual expansion coefficients is #P-complete, yet there is a quantum algorithm that can efficiently approximate these coefficients for a non-negligible fraction of configurations.
  arXiv  Detail & Related papers  (2025-12-22T04:58:14Z)
• Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
  This work proposes a novel framework based on nested evolving set processes to accelerate Personalized PageRank computation.<n>We show that the time complexity of such localized methods is upper bounded by $mintildemathcalO(R2/epsilon2), tildemathcalO(m)$ to obtain an $epsilon$-approximation of the PPR vector.
  arXiv  Detail & Related papers  (2025-10-09T09:47:40Z)
• The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models [71.5283441529015]
  In this work we consider generic Gaussian Multi-index models, in which the labels only depend on the (Gaussian) $d$-dimensional inputs through their projection onto a low-dimensional $r = O_d(1)$ subspace.<n>We introduce the generative leap exponent $kstar$, a natural extension of the generative exponent from [Damian et al.'24] to the multi-index setting.
  arXiv  Detail & Related papers  (2025-06-05T18:34:56Z)
• Numerical Schemes for Signature Kernels [0.5461938536945723]
  Signature kernels have emerged as a powerful tool within kernel methods for sequential data.<n>We introduce two advanced numerical schemes that leverage representations of boundary conditions through either approximation or boundary techniques.<n>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)
• On the Convergence of Single-Timescale Actor-Critic [49.19842488693726]
  We analyze the global convergence of the single-timescale actor-critic (AC) algorithm for the infinite-horizon discounted Decision Processes (MDs) with finite state spaces.<n>We demonstrate that the step sizes for both the actor and critic must decay as ( O(k-Pfrac12) ) with $k$ diverging from the conventional ( O(k-Pfrac12) ) rates commonly used in (non- optimal) Markov framework optimization.
  arXiv  Detail & Related papers  (2024-10-11T14:46:29Z)
• Exploiting Hankel-Toeplitz Structures for Fast Computation of Kernel Precision Matrices [14.25435308779899]
  Hilbert-space Gaussian Process (HGP) approach offers hyper-independent basis function approximation for speeding up GP inference. In this paper, we lower this dominating computational complexity to $mathcalO(NM)$ with no additional approximations. Our contribution provides a pure speed-up of several existing, widely used, GP approximations, without further approximations.
  arXiv  Detail & Related papers  (2024-08-05T09:45:31Z)
• Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
  Despite being a key bottleneck in many machine learning tasks, the cost of solving large linear systems has proven challenging to quantify.<n>We consider a fine-grained notion of complexity for solving linear systems, which is motivated by applications where the data exhibits low-dimensional structure.<n>We give a algorithm based on the Sketch-and-Project paradigm, that solves the linear system $Ax = b$, that is, finds $barx$ such that $|Abarx - b| le epsilon |b|$, in time
  arXiv  Detail & Related papers  (2024-05-09T14:56:49Z)
• Log-PDE Methods for Rough Signature Kernels [9.050432155719061]
  Signature kernels underpin machine learning algorithms for time series analysis.<n>Existing PDE solvers only use increments as input data, leading to first order approximation errors.<n>We show that a novel system of PDEs whose coefficients involve higher order iterated integrals of the input rough paths can approximate rough signature kernels.
  arXiv  Detail & Related papers  (2024-04-01T23:09:52Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Complexity of zigzag sampling algorithm for strongly log-concave distributions [6.336005544376984]
  We study the computational complexity of zigzag sampling algorithm for strongly log-concave distributions. We prove that the zigzag sampling algorithm achieves $varepsilon$ error in chi-square divergence with a computational cost equivalent to $Obigl.
  arXiv  Detail & Related papers  (2020-12-21T03:10:21Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)

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.