Fast Gradient-Based Approximation of Continuous Dynamic Time Warping

• DTW is discrete and nondifferentiable; Soft-DTW smooths alignments but can blur features, while continuous CDTW avoids discreteness yet remains costly and often nondifferentiable.Source: §1 · pp. 1–2
• Lipschitz warpings attain the same optimal CDTW cost, and CDTW is differentiable with respect to an input curve when warpings are restricted to a parametrized family.Source: §1 · p. 2
• FastCDTW optimizes a finite-dimensional warping by gradient descent, using closed-form costs for piecewise-linear maps or an unbiased Monte Carlo estimator for smooth maps.The approach gives up a global-optimality guarantee for tractability and is designed for batched GPU computation.Source: §1 · p. 2
• FastCDTW replaces DTW or Soft-DTW at lower computational cost across averaging, classification, and domain adaptation; it avoids Soft-DTW barycenter peak erosion and runs up to 50× faster than DTW in domain adaptation.Source: §1 · p. 2

2 Background

• The background uses squared Euclidean sample discrepancy and Euclidean warping-path length, though other discrepancy choices are possible.Source: §2 · p. 2

2.1 Dynamic Time Warping

• DTW minimizes cumulative sample discrepancy over admissible monotone paths and computes the optimum by dynamic programming in O(NxNyd) time, but its optimal path is non-smooth in the inputs.Source: §2.1 · p. 3

2.2 Differentiable relaxations of DTW

• Soft-DTW replaces the hard minimum over paths with a differentiable soft-minimum, but blending competing alignments can blur sharp, localized features.Source: §2.2 · p. 3

2.3 Continuous-time formulations

• CDTW aligns continuous curves through monotone reparametrizations and integrates discrepancy along the path weighted by its length, making the cost independent of traversal speed.Source: §2.3 · p. 3
• Existing exact and approximate CDTW algorithms target restricted curve representations and yield no input gradients, while GDTW retains a discretized dynamic program with tunable regularizers.Source: §2.3 · pp. 3–4
• Soft-DTW preserves discrete alignment while adding differentiability; continuous-time solvers address discreteness but remain dynamic-programming methods ill-suited to end-to-end training.Source: §2.3 · p. 4

Reparametrization

• For continuously differentiable curves x,y:[0,1]→R^d, the CDTW optimization over two reparametrizations can be reduced to one; the paper therefore optimizes over a single warping map.Source: §3 · p. 4

Differentiability

• The paper presents the Lipschitz-warping result and differentiability result as new, alongside the reduction to a single warping.The reduction has a one-dimensional counterpart in Buchin et al. (2025, Lemma 1).Source: §3 · p. 4

Lipschitz maps

• Optimizing over nondecreasing Lipschitz warpings with fixed endpoints does not lower the optimal cost relative to the stated smooth, strictly increasing class.This permits practical warpings with corners and flat pieces.Source: §3 · p. 4

Differentiability

• For a compact parametrized family satisfying the stated continuity and Lipschitz conditions, the minimizing set is nonempty and compact, and the objective has a one-sided directional derivative with respect to the input curve.The derivative is evaluated at an optimal warping held fixed.Source: §3 · pp. 4–5

4 FastCDTW

• FastCDTW optimizes a finite-dimensional warping by gradient descent, trading a global-optimality guarantee for tractability and use within end-to-end models.It returns the cost at the warping reached by the optimizer, not a guaranteed global optimum.Source: §4 · p. 5

4.1 Evaluating the alignment cost

• The piecewise-linear scheme evaluates the alignment cost in closed form without discretization error, while the Monte Carlo scheme estimates it with an unbiased estimator whose error decays as 1/S.The Monte Carlo scheme requires only pointwise evaluation of the warping, its derivative, and the two curves.Source: §4.1 · p. 5

4.2 Parametrization of ϕ

• A uniform-grid piecewise-linear warping parametrization trades sharper, more localized alignments at finer Nϕ against higher evaluation cost; moderate Nϕ yields smoother paths than DTW and distance estimates converge quickly.The parametrized family is not closed under inversion, so FastCDTW can be asymmetric; both directions converge to CDTW as Nϕ increases.Source: §4.2 · p. 6

4.3 Time complexities

• FastCDTW is far cheaper than exact and approximate CDTW solvers and GDTW; versus DTW and Soft-DTW, it is cheaper only under stated sequence-size, dimension, iteration, and sampling conditions.The comparison is for one alignment or distance value; FastCDTW computations can be parallelized on a GPU.Source: Table 1 · p. 7, §4.3 · p. 7

5 Numerical Experiments

• At series length 10,000, FastCDTW runs up to 10× faster than Soft-DTW, with the advantage appearing for large series.The comparison is shown for DTW, Soft-DTW, and FastCDTW as series length varies.Source: §5 · p. 7, Figure 2 · p. 8

5.1 Time series averaging

• FastCDTW-PL attains lower DTW loss than DBA and Soft-DTW on accel and rate, while Soft-DTW is best on ecg.On ecg, FastCDTW preserves the central peak that Soft-DTW slightly erodes.Source: §5.1 · p. 8, Figure 3 · p. 8

5.2 Time series classification

• 76.7% (Soft-DTW), 76.3% (both FastCDTW schemes), 73.9% (DTW), and 70.3% (Euclidean) are the reported mean 1-NN accuracies.Soft-DTW (2.47), FastCDTW-PL (2.54), and FastCDTW-MC (2.55) have statistically indistinguishable average ranks; all three significantly outperform DTW and Euclidean distance.Source: §5.2 · pp. 8–9, Figure 4 · p. 9

5.3 Domain adaptation

• 20× (PL) and 50× (MC) GPU speedups over DTW accompany matching or slightly improved MAD accuracy on most source/target pairs.The speedup includes the lower cost of FastCDTW evaluations and amortizing optimization of one shared warping across model updates.Source: §5.3 · pp. 9–10, Table 3 · p. 10

6 Conclusion

• FastCDTW serves as a lower-cost drop-in replacement for DTW or Soft-DTW in averaging, classification, and domain adaptation.The authors report that the solver is accurate enough to be useful in machine learning pipelines.Source: §6 · p. 10
• The solver evaluates alignment cost exactly in closed form or with an unbiased Monte Carlo estimator, and both schemes provide gradients for warpings and input curves.The algorithm is also amenable to batched GPU computation.Source: §6 · p. 10
• Because the objective is non-convex, the gradient-based solver does not guarantee global optimality.The authors nevertheless report that it is accurate enough for practical machine-learning pipelines.Source: §6 · p. 10
• A proposed future direction is using FastCDTW as a training loss for continuous-time foundation models on forecasting with irregular grids and imputation.The authors point to implicit neural representations of time series as one possible foundation.Source: §6 · p. 10

A.1 Proof of Proposition 3.1

• For every pair of warpings ϕ and ψ in C, the proposition asserts the existence of a reparametrization ˜ϕ of x.The proof defines ˜ϕ as ϕ composed with ψ⁻¹.Source: §A.1 · p. 12
• In the proof, ψ is a strictly increasing C1-diffeomorphism on [0, 1]; on that basis, the text states that its inverse ψ⁻¹ is well-defined.Source: §A.1 · p. 12
• The proof combines the identities established for the reparametrization to complete the proposition.Source: §A.1 · p. 12

A.2 Proof of Proposition 3.2

• The infima over C and CLip are equal, with C contained in CLip and Lipschitz warpings approximable by warpings in C without changing the limiting cost.The proof shows that the cost converges for approximations whose derivatives converge in L1 under a uniform slope bound.Source: §A.2 · pp. 12–13
• The alignment cost is continuous when approximating warpings have uniformly bounded slopes and their derivatives converge in L1.The proof bounds the cost difference using the curve's modulus of continuity.Source: §A.2 · pp. 12–13
• For a Lipschitz warping, the proof approximates its derivative by continuous functions, rescales them to integrate to one, and constructs C1 warpings with positive derivative.The approximation keeps the derivative values within the original bounded range before rescaling.Source: §A.2 · p. 13

A.3 Proof of Proposition 3.3

• The parameterized warpings are assumed nondecreasing, Lipschitz, and endpoint-preserving, with a uniform slope bound following from compactness and continuity in the parameter.The input curve is continuous, and the parameter set is compact.Source: §A.3 · p. 13
• The minimizing parameter set is nonempty and compact because the alignment cost is continuous over the compact parameter set.Consequently, the infimum defining the parameterized CDTW is attained as a minimum.Source: §A.3 · pp. 13–14
• For every direction h, the parameterized CDTW as a function of input curve y has a one-sided directional derivative.The proof uses the directional derivative of the cost for a fixed warping and the compact set of minimizing parameters.Source: §A.3 · pp. 13–14

A.4 Proof of Proposition 4.1

• The breakpoints partition the domain into intervals where the relevant maps are affine, making each integrand difference affine between its endpoint values.The partition combines warping-grid points with preimages of the input-series breakpoints.Source: §A.4 · p. 15
• Integrating each interval’s squared affine difference gives a closed-form term proportional to (||a||_2^2 + ⟨a,b⟩ + ||b||_2^2)/3.The proof obtains the expression by rescaling the interval to [0, 1] and integrating the linear interpolation of its endpoint vectors.Source: §A.4 · p. 15

B Time complexity of the backward pass

• The backward pass costs the same as the forward pass up to a constant factor; breakpoint merging is locally constant almost everywhere, so no root-finding is differentiated through.The piecewise-linear scheme merges sorted breakpoint sets, while reverse-mode differentiation handles the remaining closed-form operations.Source: B Time complexity of the backward pass · pp. 15–16

C.1 Time series averaging

• The INR barycenter is a continuous-time function represented by a network, so after training it can be evaluated independently of the averaged series’ sampling grid.Time is mapped to Fourier features before an MLP outputs the barycenter value.Source: §C.1 · p. 16, Figure 5 · p. 17
• At S = 200, the objectives are within 5% on rate and 7% on accel of their S = 400 values, while runtime rises from about 180 s to 400 s across tested budgets.The objective decreases with increasing Monte Carlo budget, with peak height varying from 0.98 to 1.01.Source: §C.1 · p. 17, Figure 6 · p. 18
• On ecg, the INR reaches 0.92 between samples although all barycenters stay at or below 0.79 on the 100-point grid.The central peak is about one sampling interval wide; the INR is evaluated at 2000 evenly spaced times.Source: §C.1 · pp. 17, 20, Figure 7 · p. 19

C.2 Time series classification

• The classification comparison reports 1-NN test accuracy across 95 datasets, marking methods within 99% of each dataset’s best accuracy.FastCDTW warping is fitted for each test–train pair using the grid parametrization and 300 Adam steps.Source: §C.2 · pp. 20–21

C.3 Domain adaptation

• The grid parametrization matches or slightly exceeds DTW accuracy on both datasets; INR integrated MLP stays close, while Integrated MLP lags further behind.The Integrated MLP lacks the high-frequency Fourier encoding used by the INR integrated MLP.Source: §C.3 · p. 21, Table 8 · p. 23