On the number of iterations of the {DBA} algorithm

The DTW Barycenter Averaging (DBA) algorithm isa widely used algorithm for estimating the mean ofa given set of point sequences. In this context, themean is defined as a point sequence that minimisesthe sum of dynamic time warping distances (DTW).The algorithm is similar to the k-means algorithmin the sense that it alternately repeats two steps:(1) computing an optimal assignment to the pointsof the current mean, and (2) computing an optimalmean under the current assignment. The popularityof DBA can be attributed to the fact that it workswell in practice, despite any theoretical guarantees tobe known. In our paper, we aim to initiate a theoreticalstudy of the number of iterations that DBA performsuntil convergence. We assume the algorithm is givenn sequences of m points in Rd and a parameter kthat specifies the length of the mean sequence to becomputed. We show that, in contrast to its fastrunning time in practice, the number of iterations canbe exponential in k in the worst case — even if thenumber of input sequences is n = 2. We complementthese findings with experiments on real-world data thatsuggest this worst-case behaviour is likely degenerate.To better understand the performance of the algorithmon non-degenerate input, we study DBA in the modelof smoothed analysis, upper-bounding the expectednumber of iterations in the worst case under randomperturbations of the input. Our smoothed upper boundis polynomial in k, n and d, and for constant n, it is alsopolynomial in m. For our analysis, we adapt the set oftechniques that were developed for analysing k-meansand observe that this set of techniques is not sufficientto obtain tight bounds for general n.