Research map / Learning theory and algorithms / Sample complexity
Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces k-DTW, a dissimilarity for polygonal curves that sums the k largest matched distances over traversals, giving exact and (1+eps)-approximate algorithms, dimension-free learning bounds for curve medians, and separation from DTW complexity.
Problem
Existing curve dissimilarities are either sensitive to outliers (discrete Fréchet) or lack the triangle inequality (DTW); clustering and learning with curves need a measure that is both robust and closer to a metric, with sample-efficient learning guarantees.
Approach
Define k-DTW as the minimum over traversals of the sum of the k largest matched vertex distances, interpolating between discrete Fréchet (k=1) and DTW (large k); compute it exactly by a parametric search over distinct distances using DTW on thresholded distance matrices.
Key results
- On OULAD with l-NN, 72-DTW reached AUC 0.79639 versus 0.73737 for Fréchet and 0.78360 for DTW, with k-DTW improving AUC by up to 8.2% over Fréchet and 1.8% over DTW.
- k-DTW satisfies a relaxed triangle inequality with constant k, versus a factor growing with complexity m for DTW.
- Learning bounds for median curves: Rademacher/Gaussian complexity O(sqrt(m k^2 ...)/n) for k-DTW versus O(sqrt(m^3 ...)/n) for DTW, with a DTW lower bound Omega(sqrt(m^2/n)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use 76-DTW instead of Fréchet | OULAD 17-NN classification · OULAD | AUC: 0.73737 -> 0.79772 | Helped |
| use 76-DTW instead of DTW | OULAD 17-NN classification · OULAD | AUC: 0.78360 -> 0.79772 | Helped |
| use 64-DTW instead of Fréchet | OULAD 17-NN classification · OULAD | Accuracy: 0.83742 -> 0.85557 | Helped |
| use 64-DTW instead of DTW | OULAD 17-NN classification · OULAD | Accuracy: 0.85459 -> 0.85557 | Helped |
| use 64-DTW instead of Fréchet | OULAD 17-NN classification · OULAD | F1-score: 0.90953 -> 0.91796 | Helped |
| use 64-DTW instead of DTW | OULAD 17-NN classification · OULAD | F1-score: 0.91735 -> 0.91796 | Helped |
Surprising findings
- k-DTW traversal lengths can be linearly larger or smaller than DTW traversal lengths on the same curves.
- The k-DTW optimum is not obtained by taking the k largest distances of the DTW-optimal traversal, so standard DTW cannot be directly reused.
Limitations
- Exact algorithm still quartic in worst case since z can be m'm''; no truly subquadratic algorithm known.
- Learning results for dimension-free bounds come at the cost of larger dependence on m and k.
- Experiments are limited to synthetic curves and a single real-world dataset (OULAD) for classification, with no center-based clustering evaluation on real data.
Experimental setup
Datasets: OULAD (Open University Learning Analytics Dataset) synthetic curves of types A, B, C
Benchmarks: OULAD binary pass/fail classification
Metrics: AUC accuracy F1-score
Baselines: discrete Fréchet distance DTW weak Fréchet distance edit distance with real penalty partial window DTW partial segment DTW
Builds on: discrete Fréchet distance dynamic time warping Ky-Fan norm top-k optimization framework
Closest papers by meaning
- Graphical Time Warping for Joint Alignment of Multiple Curves (NeurIPS 2016 · similarity 0.86)
- Perturbed Dynamic Time Warping: A Probabilistic Framework and Generalized Variants (ICLR 2026 · similarity 0.86)
- Efficient Learning of Timeseries Shapelets (AAAI 2016 · similarity 0.84)
- Learning Distances from Data with Normalizing Flows and Score Matching (ICML 2025 · similarity 0.84)
- Dynamic Similarity Graph Construction with Kernel Density Estimation (ICML 2025 · similarity 0.83)
- Exploiting Representation Curvature for Boundary Detection in Time Series (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.