Understanding Gradual Domain Adaptation: Improved Analysis, Optimal Path
  and Beyond
  The vast majority of existing algorithms for unsupervised domain adaptation
(UDA) focus on adapting from a labeled source domain to an unlabeled target
domain directly in a one-off way. Gradual domain adaptation (GDA), on the other
hand, assumes a path of $(T-1)$ unlabeled intermediate domains bridging the
source and target, and aims to provide better generalization in the target
domain by leveraging the intermediate ones. Under certain assumptions, Kumar et
al. (2020) proposed a simple algorithm, Gradual Self-Training, along with a
generalization bound in the order of $e^{O(T)}
\left(\varepsilon_0+O\left(\sqrt{log(T)/n}\right)\right)$ for the target domain
error, where $\varepsilon_0$ is the source domain error and $n$ is the data
size of each domain. Due to the exponential factor, this upper bound becomes
vacuous when $T$ is only moderately large. In this work, we analyze gradual
self-training under more general and relaxed assumptions, and prove a
significantly improved generalization bound as
$\widetilde{O}\left(\varepsilon_0 + T\Delta + T/\sqrt{n} + 1/\sqrt{nT}\right)$,
where $\Delta$ is the average distributional distance between consecutive
domains. Compared with the existing bound with an exponential dependency on $T$
as a multiplicative factor, our bound only depends on $T$ linearly and
additively. Perhaps more interestingly, our result implies the existence of an
optimal choice of $T$ that minimizes the generalization error, and it also
naturally suggests an optimal way to construct the path of intermediate domains
so as to minimize the accumulative path length $T\Delta$ between the source and
target. To corroborate the implications of our theory, we examine gradual
self-training on multiple semi-synthetic and real datasets, which confirms our
findings. We believe our insights provide a path forward toward the design of
future GDA algorithms.
