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

arXiv: https://arxiv.org/abs/2505.23431 · HTML: https://mlsanity.com/paper/2505.23431/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 60 references that are in the map.
- First posted on arXiv 29 May 2025.

## Builds on (most cited first, 25 of 25)

- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [Optimal terminal dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1810.09250/) (2018)
- [p-Generalized Probit Regression and Scalable Maximum Likelihood Estimation via Sketching and Coresets](https://mlsanity.com/paper/2203.13568/) (2022)
- [Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regression](https://mlsanity.com/paper/2304.00051/) (2023)
- [Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails](https://mlsanity.com/paper/1404.1448/) (2014)
- [Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping](https://mlsanity.com/paper/1502.01063/) (2015)
- [Clustering time series under the Fr'echet distance](https://mlsanity.com/paper/1512.04349/) (2015)
- [Optimal Sketching Bounds for Sparse Linear Regression](https://mlsanity.com/paper/2304.02261/) (2023)
- [Random Projections and Sampling Algorithms for Clustering of High-Dimensional Polygonal Curves](https://mlsanity.com/paper/1907.06969/) (2019)
- [(k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping](https://mlsanity.com/paper/2012.00464/) (2020)
- [Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time](https://mlsanity.com/paper/2203.04531/) (2022)
- [Probabilistic smallest enclosing ball in high dimensions via subgradient sampling](https://mlsanity.com/paper/1902.10966/) (2019)
- [On Generalization Bounds for Projective Clustering](https://mlsanity.com/paper/2310.09127/) (2023)
- [A Tight VC-Dimension Analysis of Clustering Coresets with Applications](https://mlsanity.com/paper/2501.06588/) (2025)
- [Solving Proximity Problems for Polygonal Shapes via Polynomials](https://mlsanity.com/paper/2308.05998/) (2023)
- [Turnstile ℓp leverage score sampling with applications](https://mlsanity.com/paper/2406.00339/) (2024)
- [Tight Hardness Results for Consensus Problems on Circular Strings and Time Series](https://mlsanity.com/paper/1804.02854/) (2018)
- [SETH Says: Weak Fr'echet Distance is Faster, but only if it is Continuous and in One Dimension](https://mlsanity.com/paper/1807.08699/) (2018)
- [The VC Dimension of Metric Balls under Fr'echet and Hausdorff Distances](https://mlsanity.com/paper/1903.03211/) (2019)
- [Random projections for curves in high dimensions](https://mlsanity.com/paper/2207.07442/) (2022)
- [Solving Fr'echet Distance Problems by Algebraic Geometric Methods](https://mlsanity.com/paper/2308.14569/) (2023)
- [Fast Approximations and Coresets for (k, l)-Median under Dynamic Time Warping](https://mlsanity.com/paper/2312.09838/) (2023)
- [Probabilistic embeddings of the Fr'echet distance](https://mlsanity.com/paper/1808.01983/) (2018)
- [On the hardness of computing an average curve](https://mlsanity.com/paper/1902.08053/) (2019)

## Built on by (most cited first, 2 of 2)

- [Hardness of High-Dimensional Linear Classification](https://mlsanity.com/paper/2603.19061/) (2026)
- [Dimension Reduction for Curves: Simplified and Generalized](https://mlsanity.com/paper/2607.03112/) (2026)

## Abstract (arXiv)

This paper introduces k-Dynamic Time Warping (k-DTW), a novel dissimilarity measure for polygonal curves. k-DTW has stronger metric properties than Dynamic Time Warping (DTW) and is more robust to outliers than the Fr'echet distance, which are the two gold standards of dissimilarity measures for polygonal curves. We show interesting properties of k-DTW and give an exact algorithm as well as a (1+varepsilon)-approximation algorithm for k-DTW by a parametric search for the k-th largest matched distance. We prove the first dimension-free learning bounds for curves and further learning theoretic results. k-DTW not only admits smaller sample size than DTW for the problem of learning the median of curves, where some factors depending on the curves' complexity m are replaced by k, but we also show a surprising separation on the associated Rademacher and Gaussian complexities: k-DTW admits strictly smaller bounds than DTW, by a factor tildeOmega(√m) when kll m. We complement our theoretical findings with an experimental illustration of the benefits of using k-DTW for clustering and nearest neighbor classification.