Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves

The paper proposes k-DTW (k-Dynamic Time Warping) as a dissimilarity measure between polygonal curves. The motivation is that many diverse datasets can be thought of as curves and measuring appropriately the distance between them is a fundamental problem. Usually researchers has studied Frechet distances and DTW for this purpose and typically some transformations of one curve into another is involved. However, both aforementioned measures have their disadvantages: Frechet distance is very sensitive to outlier whereas DTW is not a metric since it does not satisfy the triangle inequality.

To alleviate these issues with existing distances, the paper proposes k-DTW which combines advantages of standard measures like Frechet distance and of the standard DTW (essentially interpolating between the two), without their disadvantages.

At a high-level, the parameter k controls the degree of accuracy for the transformation performed between the two curves. Oftentimes, carrying out the whole trasformation may be expensive and also overfit to noise, whereas k-DTW only cares about the most important parts of the trasformation, as measured by a small subset of size k, and ignores the rest of the transformation. Although this may seem lossy it offers some advantages.

The main contributions of the paper are:

1. The first point the authors make is that k-DTW satisfies a strengthened triangle inequality compared to DTW and it is thus closer to a proper metric, while retaining some robustness of DTW.

2. The second point is that there is an exact algorithm, as well as a (1 + eps)-approximation for k-DTW using a parametric search for the k-th largest matched distance with standard DTW on modified distance matrices as a subroutine.

3. Next, they show the first dimension-free learning bounds for clustering under k-DTW and a separation result showing that k-DTW has strictly smaller Rademacher and Gaussian complexity than DTW for clustering curves.

4. Finally, the authors provide experiments showing the benefits of k-DTW over the other two measures in the setting of clustering and nearest neighbor classification, on synthetic and real world data.

The paper proposes a new distance for between curves, the k-DTW distance, and make several types of compelling arguments for its use. These include better near-metric properties than DTW, and better learning complexity than Frechet distance - k-DTW generalizes both. The paper provides an efficient approximation algorithm (with clear provable guarantees), heuristics for improving runtime in practice while maintaining guarantees, and learning complexity results for learning a median curve from a set. Each step involves non-trivial insights. Moreover, the paper shows empirical improvement on synthetic (for clustering) and real data sets (for classification) that demonstrate clear improvement over the standard DTW and Frechet distances.

Data analysis on curve data is an active area, and this paper provides an inventive and comprehensively presented new method in this area. Moreover, I found it surprising that the new method works so well - it considers the longest k distances in a matched monotonic sequence (DTW uses all, and Frechet uses the 1 longest), and this has very different properties and seems to be more robust than either.

Moreover I found the paper clearly written. It combines a variety of complicated theoretical and practical perspectives.

This paper proposes a new distance measure called $k$-DTW, which is positioned as a interpolation between the classical DTW distance and the Fréchet distance. The technical novelty is to consider only the top $k$ matched distances in the alignment path, rather than summing all distances (as in DTW) or taking the maximum distance (as in Fréchet). The authors prove that $k$-DTW interpolates these two classical measures for $k = 1$ and $k$ sufficiently large. Empirical results show that $k$-DTW can yield stronger triangle-like properties than DTW, while still being more robust to outliers than Fr'echet. A parametric search algorithm is introduced for computing $k$-DTW exactly (as well as a $(1+\varepsilon)$-approximation). The paper demonstrates applications in clustering (via hierarchical agglomerative clustering) and in nearest neighbor classification on synthetic and real-world datasets. The main contribution is that $k$-DTW addresses key shortcomings of Fréchet (outlier-sensitivity) and DTW (lack of metric-like properties) and, from experiments, appears beneficial in tasks like clustering and classification.

The paper introduces a new dissimilarity measure for polygonal curves called k-DTW, which improves on Dynamic Time Warping (DTW) by offering stronger metric properties and greater robustness to outliers. It provides both exact and approximate algorithms, theoretical learning bounds, and shows improved performance in clustering and nearest neighbor tasks. k-DTW also needs fewer samples than DTW.

All reviewers are positive about the paper. No major issues were raised, while minor ones were largely addressed in the rebuttal.

The finals scores are 3xAccept.

In addition to the theoretical contribution, the reviewers, overall, also appriciated the experiments (related to clustering and classification) and how they provided empirical evidence to support the authors' claims.

In the AC's view, this is a clear Accept.