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.
Figures & tables
Figure 1: Alignments obtained using FastCDTW for different values of Nϕ , the number of breakpoints in the warping function ϕ . The two time series only differ by a central stretching over a null value, yielding a zero DTW distance (up to sampling artifacts).
Figure 2: Computation time of DTW, Soft-DTW and FastCDTW as a function of the series length.
Figure 3: Barycenters of accel (top), ecg (middle) and rate (bottom). Grey: the averaged series.
method
accel
ecg
rate
Euclidean mean
11.88± 0.11
14.81± 0.06
13.19± 0.10
DTW (DBA)
3.16± 0.06
4.43± 0.25
1.48± 0.08
Soft-DTW (best γ )
2.31± 0.04
4.02± 0.03
1.19± 0.02
FastCDTW-PL
2.20± 0.02
4.82± 0.43
1.08± 0.01
FastCDTW-MC
2.42± 0.05
4.80± 0.57
1.16± 0.02
Table 2: Loss ∑iDTW(X,Yi) of each barycenter (lower is better), mean ± standard deviation over ten draws of the series. Soft-DTW is taken at the temperature with the lowest mean DTW loss (Table 4 ).
Figure 4: Average rank of each discrepancy by 1-NN test accuracy over the 95 UCR datasets (1 is best). A horizontal bar joins methods whose accuracies are not significantly different (pairwise two-sided Wilcoxon signed-rank tests with Holm’s correction, α=0.05 ).
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: INR barycenter: a time t∈[0,1] is mapped to Fourier features γ(t) , then an MLP returns the value cω(t)∈Rd of the barycenter at time t . In our experiments, L=10 and the MLP has 5 hidden layers of width 64 .
method
accel
ecg
rate
Euclidean mean
11.88± 0.11
14.81± 0.06
13.19± 0.10
DTW (DBA)
3.16± 0.06
4.43± 0.25
1.48± 0.08
Soft-DTW γ=10
15.92± 0.04
22.11± 0.04
9.75± 0.03
Soft-DTW γ=1
2.72± 0.05
10.34± 0.06
1.32± 0.02
Soft-DTW γ=10−1
2.40± 0.07
4.77± 0.05
1.22± 0.01
Soft-DTW γ=10−2
2.31± 0.04
4.02± 0.03
1.22± 0.01
Appendix
Table 4: DTW loss of each barycenter, as in Table 2 , with Soft-DTW at every temperature γ of the sweep. Mean ± standard deviation over the same ten draws of the series.
Figure 6: Effect of the Monte Carlo budget S on the INR barycenter, rate (top) and accel (bottom), all other settings fixed. Left: the barycenter, from light to dark as S grows. Right: the final objective against S , with wall-clock time on the right axis.
Figure 7: Coarsely sampled series ( T=100 kept samples), rate (top), accel (middle) and ecg (bottom). The discrete barycenters live on the sample grid, while the INR centroid is a function. Soft-DTW is again taken at the temperature with the lowest DTW loss, selected on this grid.
Figure 8: Soft-DTW barycenter at the temperatures not shown in Figure 3 , on accel (top), ecg (middle) and rate (bottom), on the same series as that figure.
method
CPU (s)
GPU (s)
Euclidean
0.01
–
DTW
27.3
–
Soft-DTW
199.3
–
FastCDTW-PL
2114.6
20.1
FastCDTW-MC
2484.9
15.2
Appendix
Table 5: Cost of one cross-distance matrix, in seconds, averaged over the datasets on which every method was timed on CPU, excluding hyperparameter selection.
dataset
Euc.
DTW
Soft-DTW
FastCDTW-PL
FastCDTW-MC
ACSF1
0.540
0.640
0.640
0.520
0.530
Adiac
0.611
0.604
0.598
0.693
0.693
ArrowHead
0.800
0.703
0.794
0.823
0.806
BME
0.827
0.893
0.993
0.993
0.993
Beef
0.667
0.633
0.633
0.667
0.667
BeetleFly
0.750
0.700
0.700
0.700
0.700
Appendix
Table 6: 1-NN test accuracy per dataset (1 of 2). Bold: within 99% of the best method on that row.
dataset
Euc.
DTW
Soft-DTW
FastCDTW-PL
FastCDTW-MC
PigArtPressure
0.288
0.481
0.553
0.558
0.572
PigCVP
0.139
0.327
0.418
0.183
0.188
Plane
0.962
1.000
1.000
1.000
1.000
PowerCons
0.978
0.922
0.972
0.967
0.967
ProximalPhalanxOutlineAgeGroup
0.785
0.805
0.780
0.805
0.810
ProximalPhalanxOutlineCorrect
0.808
0.784
0.725
0.842
0.845
Appendix
Table 7: 1-NN test accuracy per dataset (3 of 3), with the mean over all 95 datasets. Bold: within 99% of the best method on that row.
Warping ( ϕ )
TarnBrittany
miniTimeMatch
Grid
94.4±5.8
84.5±7.2
INR integrated MLP
93.1±7.5
79.3±15.2
Integrated MLP
92.0±9.4
76.6±9.8
DTW
94.0±6.4
78.9±8.0
Appendix
Table 8: Impact of the warping parametrization ( ϕ ) on FastCDTW-MC accuracy (mean over 3 seeds and over problem pairs within each dataset; std over problem pairs only).