CS Paper Radar

Fast Gradient-Based Approximation of Continuous Dynamic Time Warping

Pierre Houedry, Romain Tavenard, Nicolas Courty, Romaric Gaudel

cs.LG stat.ML ·submitted 2026-10-09 07:22 UTC · v1

Abstract

Dynamic Time Warping (DTW) is a common choice for measuring the discrepancy between time series. It proceeds by finding an optimal warping between timestamps through dynamic programming, which can be slow and is not differentiable. Consequently, several variants have been proposed. Among them, Soft-DTW proposes a smooth formulation of DTW, amenable to gradient computation, while Continuous-DTW (CDTW) introduces a continuous formulation through parametrizable warping functions. Yet, computational costs remain high for both methods and impractical for large datasets in modern machine learning pipelines. This paper revisits CDTW in several ways. After establishing its differentiability under mild conditions, we introduce FastCDTW, which is an efficient approximate solver with two different computational strategies: an exact closed-form scheme for piecewise-linear warping functions, and an unbiased Monte Carlo estimator for smooth ones, such as implicit neural networks. Both strategies provide gradients with respect to the warping function and the input time series, and the resulting algorithm is GPU-friendly. We demonstrate its benefits through its integration into more complex learning problems, including time series averaging, classification and deep domain adaptation.

Closest papers

Nearest neighbours by meaning across the whole index.

Time-warping estimation via stationarity-based learning of the de-warped signal

cs.LG stat.ML ·2026-09-15 ·Corentin Presvôts, Adrien Meynard
publishedunusual similarity 0.65
Abstract

Time-warping estimation is a fundamental problem in signal processing with applications in bioacoustics, radar, and biomedical analysis. This paper introduces a Time-Warping Estimation Trainable (TWET) model for estimating timewarping functions from a single observation. The proposed approach formulates time-warping estimation as a stationarization problem in the wavelet domain and leverages a hierarchical dilated convolutional architecture to estimate the time-warping functions. A differentiable stationarity criterion is introduced for end-to-end optimization. TWET is compared with existing approaches. Experimental results show improved deformation reconstruction accuracy together with significantly reduced computation time, making the framework compatible with low-latency applications.

0.45

WETW: Learning Pair-Specific Weighted Euclidean Distances for Efficient DTW Search

cs.LG cs.AI ·2026-11-12 ·Christos Panourgias, Qitong Wang, George Tzagkarakis, Themis Palpanas
similarity 0.62
Abstract

Dynamic Time Warping (DTW) is the standard distance for similarity search over time series that are misaligned in time, but its cost is quadratic in the series length and lower bounds often prune few candidates, so search over large collections of long series is slow. Learned approximations embed the series to make comparisons cheap, yet compare every pair with the same fixed rule, usually the Euclidean distance, although DTW aligns each pair differently. We observe that, once a pair is aligned, DTW is a Euclidean distance over coordinates selected for that pair. Building on this view, we propose Weighted Euclidean Time Warping (WETW), a learned distance that adapts the comparison of fixed-length embeddings to each pair. A small symmetric network predicts one weight per embedding di- mension and pair without computing an alignment, which halves the error of the best static distance on the same embeddings. The embeddings come from the Weighted Euclidean SEries Encoder (WESEE), whose multi-scale Temporal Feature Extractor keeps the timing information that global pooling removes and raises recall@1 from 0.90 to 0.95, although WETW works with any encoder. We also show that fitting DTW distances is not enough for search, as regression alone misorders the closest neighbours, and that ranking regularization raises recall@1 from 0.79 to 0.95. Our filter-and-verify pipeline, WETW-FV, uses WETW to build a shortlist and exact DTW to check it, so the search is approximate but every returned distance is exact. Over eight datasets, WETW-FV is 11.4x faster than the fastest exact method among the UCR Suite, lower bounds and MESSI-DTW, at a mean recall@10 of 0.93, while the best learned baseline reaches 0.59 at the same speed. On 48K-point series, WETW- FV remains 40x faster than the UCR Suite at a recall@10 of 0.91.

0.21

Online Gradient Computation for Warping Gaussian Process Transformations

cs.LG eess.SP ·2026-09-15 ·Emilio Ruiz-Moreno, Konstantinos Slavakis, Baltasar Beferull-Lozano
similarity 0.62
Abstract

Warped Gaussian processes (GPs) handle non-Gaussian observations by mapping them into a latent standard GP via a parametric transformation called warping. Existing streaming variants, however, either optimize the warping parameters periodically or sacrifice analytical tractability for a higher model capacity. To bridge this gap, we show that the gradient of the instantaneous negative log-likelihood of a warped GP admits an exact recursive computation. Based on this result, we propose a novel online method for warped GPs that jointly updates the latent GP moments and optimizes the warping parameters.

0.31

Continuous-Time Machine Learning: A Unified Mathematical Perspective

cs.LG cs.AI ·2026-09-15 ·Waleed Razzaq, Yun-Sheng Zhao, Yun-Bo Zhao
surveybenchmark similarity 0.60
Abstract

Continuous-time (CT) machine learning has emerged as a principled framework for modeling temporal dynamics as a continuous process, particularly when observations are sampled at arbitrary time points or span long-range horizons. However, major branches of CT machine learning have matured in separate research communities, leaving their mathematical relationships and design trade-offs insufficiently characterized. In this survey, we develop a unified, concept-driven view of major CT machine learning branches through a taxonomy that organizes families according to their underlying base mathematical formulations. We present a canonical mathematical formulation that relates these families through different architectural choices of vector-field parameterization, stochasticity, memory mechanisms, and discretization. We compare training algorithms, optimization strategies, and failure modes, highlighting the trade-offs across families. We further provide a comparative analysis of theoretical computational complexity alongside an illustrative architecture-controlled benchmark analysis on representative architectures from each family. We also review software ecosystems supporting their implementation. Finally, we identify open challenges in approximation theory, training stability, hardware-efficient implementations, benchmarking, foundation models, and scientific machine learning, and discuss an agenda for future research.

0.21

Robust and Efficient Noisy-Label Time-Series Classification via Dynamic Time Warping Based Granular Ball Computing

cs.LG cs.AI ·2026-08-12 ·Ziqiang Li, Yun Liu, Gouhei Tanaka
benchmark similarity 0.60
Abstract

Dynamic Time Warping (DTW)-based Nearest-Neighbor (NN) classifiers are effective for time-series classification but are vulnerable to mislabeled training samples and require numerous DTW computations during inference. We propose DTW-based Granular Ball Computing (DTW-GBC), which organizes temporally similar training samples into granular balls and performs classification at the granule level. We further develop two granular-ball construction strategies for DTW-GBC. Experiments on four benchmark datasets with symmetric label noise show that the two DTW-GBC variants generally mitigate the performance degradation caused by label noise while requiring substantially fewer comparisons than DTW-based 1-NN during inference. These findings suggest that DTW-GBC provides a favorable balance between classification robustness and inference efficiency.

0.04

Accelerated surrogate dynamics for dynamical, stochastic system evolution

cs.AI ·2026-09-29 ·Marco Jochum, Ioannis Kouroudis, Gohar Ali Siddiqui, Taher Amine Hamzaoui, Manuel Gößwein +1 more
similarity 0.58
Abstract

Dynamic simulations are an entrenched way of gaining insight into the evolution of system dynamics. Their computational cost however is often prohibitively high, especially in cases of stochastic frameworks. Machine learning algorithms are especially suited as simulation surrogates. Nevertheless, they face some very distinct limitations. Firstly, the sheer dimensionality of these systems, however, precludes the use of traditional time series models who struggle with high dimensional feature spaces. Additionally, traditional time series focus exclusively on either long or short range effects, causing local or global drift given enough time. In this paper, we propose a framework that addresses those limitations. Our framework combines a Variational Autoencoder, with a convolutional or graph basis that reduces the dimensionality of the system. This latent vector is propagated in time using a Temporal Fusion Transformer model, which includes both long range and short range effect encoding, as well as static covariate support. We test our framework on three distinct cases, to prove its robustness and in all three we have achieved practically identical to the simulation results at a fraction of the time. Further, our framework is flexible enough to be adapted to any new system and provides an inbuilt uncertainty quantification for targeted experiment design.

0.33

Learning Temporal Dynamics with Derivative Representations for Time Series Forecasting

cs.LG ·2026-11-12 ·Shujie Duan, Jia Hong Puah, Haocheng Wu, Yifei Mao, Hongting Zhou +4 more
code/data similarity 0.57
Abstract · 20 pages, 3 figures

Time series forecasting aims to predict the future evolution of complex systems by learning their underlying dynamics from past observations. Despite recent advances in deep learning, Transformers in particular still struggle to capture the temporal evolution of system dynamics. Existing approaches have been largely driven by architectural innovation, with comparatively little attention paid to training strategies that explicitly exploit the temporal structure governing system dynamics. In this work, we introduce DeltaTSF, a dynamics-aware forecasting framework based on discrete derivative representations of time series. Specifically, DeltaTSF jointly learns the series and their discrete temporal derivatives across both input and forecast horizons within a unified, model-agnostic framework. By coupling these representations over time, the model is encouraged to maintain temporal consistency, a property we show to induce a form of discrete Taylor consistency during training. This formulation enables the model to better reflect the underlying system dynamics, resulting in more stable and physically coherent forecasts. Notably, DeltaTSF does not require explicit derivative computation and introduces no additional computational overhead at inference time. Extensive experiments across diverse benchmarks and backbone architectures demonstrate that DeltaTSF consistently improves forecasting performance and yields more dynamically coherent predictions than strong SOTA methods. These results highlight the effectiveness of enforcing dynamic coherence through derivative representations as a model-agnostic paradigm that operates alongside and complements architectural design. Source code will be made publicly available upon acceptance.

0.18

Approximating CDTW Distance of Piecewise Algebraic Curves

cs.CG cs.SCmath.OC ·2026-09-03 ·Alperen A. Ergür, Shamik Khowala
similarity 0.56
Abstract · 24 pages, 5 figures. Preliminary manuscript, comments welcome!

Curves as input data naturally arise in a variety of fields including finance, seismology, medicine, spatio-temporal data mining, malicious activity detection, and more. A common way to analyze these data sets is to do similarity matching or clustering. The most common metrics used for measuring similarity of curves are Dynamic Time Warping (DTW) and Fréchet distance. These metrics are sensitive to sampling rate and outliers respectively, and do not yield robust outcomes. Continuous Dynamic Time Warping (CDTW) is a more robust distance metric that improves upon DTW and Fréchet distances. Existing algorithms for CDTW are either exact algorithms that focus on non-Euclidean norms and piecewise linear curves, or approximation algorithms limited to piecewise linear curves. We present an approximation algorithm for computing the CDTW distance under Euclidean norm between piecewise (higher degree) algebraic curves. That is, we present a fully polynomial-time approximation scheme (FPTAS) of multiplicative error $\varepsilon$, with $O \left( (m+n)^{\frac{19}{6}} (\frac{1}{\varepsilon})^{\frac{10}{3}} \log \left( \frac{ (m+n) }{\varepsilon^2} \right) \right)$ complexity, where $m$ and $n$ are the number of pieces of the two input curves.

0.53