# Algorithms and Theory for Supervised Gradual Domain Adaptation

Jing Dong<EMAIL_ADDRESS>
The Chinese University of Hong Kong, Shenzhen
Shiji Zhou<EMAIL_ADDRESS>
Tsinghua-Berkeley Shenzhen Institute, Tsinghua University
Baoxiang Wang<EMAIL_ADDRESS>
The Chinese University of Hong Kong, Shenzhen
Han Zhao<EMAIL_ADDRESS>
University of Illinois Urbana-Champaign

###### Abstract

The phenomenon of data distribution evolving over time has been observed in a
range of applications, calling the needs of adaptive learning algorithms. We
thus study the problem of supervised gradual domain adaptation, where labeled
data from shifting distributions are available to the learner along the
trajectory, and we aim to learn a classifier on a target data distribution of
interest. Under this setting, we provide the first generalization upper bound
on the learning error under mild assumptions. Our results are algorithm
agnostic, general for a range of loss functions, and only depend linearly on
the averaged learning error across the trajectory. This shows significant
improvement compared to the previous upper bound for unsupervised gradual
domain adaptation, where the learning error on the target domain depends
exponentially on the initial error on the source domain. Compared with the
offline setting of learning from multiple domains, our results also suggest
the potential benefits of the temporal structure among different domains in
adapting to the target one. Empirically, our theoretical results imply that
learning proper representations across the domains will effectively mitigate
the learning errors. Motivated by these theoretical insights, we propose a
min-max learning objective to learn the representation and classifier
simultaneously. Experimental results on both semi-synthetic and large-scale
real datasets corroborate our findings and demonstrate the effectiveness of
our objectives.

##  1 Introduction

An essential assumption for the deployment of machine learning models in real-
world applications is the alignment of training and testing data
distributions. Under this condition, models are expected to generalize, yet
real-world applications often fail to meet this assumption. Instead, continual
distribution shift is widely observed in a range of applications. For example,
satellite images of buildings and lands change over time due to city
development (Christie et al., 2018); self-driving cars receive data with
quality degrading towards nightfall (Bobu et al., 2018; Wu et al., 2019b).
Although this problem can be mitigated by collecting training data that covers
a wide range of distributions, it is often impossible to obtain such a large
volume of labeled data in many scenarios. On the other hand, the negligence of
shifts between domains also leads to suboptimal performance. Motivated by this
commonly observed phenomenon of gradually shifting distributions, we study
supervised gradual domain adaptation in this work. Supervised gradual domain
adaptation models the training data as a sequence of batched data with
underlying changing distributions, where the ultimate goal of learning is to
obtain an effective classifier on the target domain at the last step. This
relaxation of data alignment assumption thus equips gradual domain adaptation
with the applicability in a wide range of scenarios. Compared with
unsupervised gradual domain adaptation, where only unlabeled data is available
along the sequence, in supervised gradual domain adaptation the learner also
has access to labeled data from the intermediate domains. Note that this
distinction in terms of problem setting is essential, as it allows for more
flexible model adaptation and algorithm designs in supervised gradual domain
adaptation.

The mismatch between training and testing data distributions has long been
observed, and it had been addressed with conventional domain adaptation and
multiple source domain adaptation (Duan et al., 2012; Hoffman et al., 2013,
2018b, 2018a; Zhao et al., 2018; Wen et al., 2020a; Mansour et al., 2021) in
the literature. Compared with the existing paradigms, supervised gradual
domain adaptation poses new challenges for these methods, as it involves more
than one training domains and the training domains come in sequence. For
example, in the existing setting of multiple-source domain adaptation (Zhao et
al., 2018; Hoffman et al., 2018a), the learning algorithms try to adapt to the
target domain in a one-off fashion. Supervised gradual domain adaptation,
however, is more realistic, and allows the learner to take advantage of the
temporal structure among the gradually changing training domains, which can
lead to potentially better generalization due to the smaller distributional
shift between each consecutive pair of domains.

Various empirically successful algorithms have been proposed for gradual
domain adaptation (Hoffman et al., 2014; Gadermayr et al., 2018; Wulfmeier et
al., 2018; Bobu et al., 2018). Nevertheless, we still lack theoretical
understanding of their limits and strengths. Kumar et al. (2020) provides the
first algorithm-specific theoretical guarantee for unsupervised gradual domain
adaptation. However, the given upper bound of the learning error on the target
domain suffers from exponential dependency (in terms of the length of the
trajectory) on the initial learning error on the source domain. This is often
hard to take in reality and it is left open whether this can be alleviated in
supervised gradual domain adaptation.

In this paper, we study the problem of gradual domain adaptation under a
supervised setting where labels of training domains are available. We prove
that the learning error of the target domain is only linearly dependent on the
averaged error over training domains, showing a significant improvement
compared to the unsupervised case. We show that our results are comparable
with the learning bound for multiple source training and can be better under
certain cases while relaxing the requirement of access to all training domains
upfront simultaneously. Further, our analysis is algorithm and loss function
independent. Compared to previous theoretical results on domain adaptation,
which used $l_{1}$ distance (Mansour et al., 2009) or $W_{\infty}$ distance to
capture shifts between data distributions, our results are obtained under
milder assumptions. We use $W_{p}$ Wasserstein distance to describe the
gradual shifts between domains, enabling our results to hold under a wider
range of real applications. Our bound features two important ingredients to
depict the problem structure: sequential Rademacher complexity Rakhlin et al.
(2015) is used to characterize the sequential structure of gradual domain
adaptation while discrepancy measure Kuznetsov and Mohri (2017) is used to
measure the non-stationarity of the sequence.

Our theoretical results provide insights into empirical methods on gradual
domain adaptation. Specifically, our bound highlights the following two
observations:

  * •

Effective representation where the data drift is “small” helps. Our
theoretical results highlight an explicit term showing that representation
learning can directly optimize the learning bound.

  * •

There exists an optimal time horizon (number of training domains) for
supervised gradual domain adaptation. Our results highlight a trade-off
between the time horizon and learning bound.

Based on the first observation, we propose a min-max learning objective to
learn representations concurrently with the classifier. To optimize this
objective, however, requires simultaneous access to all training domains. In
light of this challenge, we relax the requirement of simultaneous access with
temporal models that encode knowledge of past training domains. To verify our
observations and the proposed objectives, we conduct experiments on both semi-
synthetic datasets with MNIST dataset and large-scale real datasets such as
FMOW (Christie et al., 2018). Comprehensive experimental results validate our
theoretical findings and confirm the effectiveness of our proposed objective.

##  2 Related Work

##### (Multiple source) domain adaptation

Learning with shifting distributions appears in many learning problems.
Formally referred as domain adaptation, this has been extensively studied in a
variety of scenarios, including computer vision (Hoffman et al., 2014;
Venkateswara et al., 2017; Zhao et al., 2019b), natural language processing
(Blitzer et al., 2006, 2007; Axelrod et al., 2011), and speech recognition
(Sun et al., 2017; Sim et al., 2018). When the data labels of the target
domain are available during training, known as supervised domain adaptation,
several parameter regularization based methods (Yang et al., 2007; Aytar and
Zisserman, 2011), feature transformations based methods (Saenko et al., 2010;
Kulis et al., 2011) and a combination of the two are proposed (Duan et al.,
2012; Hoffman et al., 2013). The theoretical limits of domain adaptations have
also been extensively studied (David et al., 2010; Zhao et al., 2019a; Wu et
al., 2019a; Zhao et al., 2020). The problem of adapting with multiple training
domains, referred to as multiple source domain adaptation (MDA), is also
studied extensively. Hoffman et al. (2018a) first studied the asymptotic
learning bounds for MDA. Zhao et al. (2018) provides the first generalization
bounds and proposed efficient adversarial neural networks to demonstrate
empirical superiority. The theoretical results are further explored by Wen et
al. (2020a) with a generalized notion of distance measure, and by Mansour et
al. (2021) when only limited target labeled data are available.

##### Gradual domain adaptation

Many real-world applications involve data that come in sequence and are
continuously shifting. Hoffman et al. (2014) addresses with data from
continuously evolving distribution with a novel unsupervised manifold-based
adaptation method. Following works (Gadermayr et al., 2018; Wulfmeier et al.,
2018; Bobu et al., 2018) also proposed unsupervised approaches for this
variant of gradual domain adaptation with unsupervised algorithms. Kumar et
al. (2020) studied the problem of adapting to an unseen target domain with
shifting training domains. Their result features the first theoretical
guarantee for unsupervised gradual domain adaptation with a self-training
algorithm and highlights that learning with a gradually shifting domain can be
potentially much more beneficial than a Direct Adaptation. The work provides a
theoretical understanding of the effectiveness of empirical tricks such as
regularization and label sharpening. However, they are obtained under rather
stringent assumptions. They assumed that the label distribution remains
unchanged while the varying class conditional probability between any two
consecutive domains has bounded $W_{\infty}$ Wasserstein distance, which only
covers a limited number of cases. Moreover, the loss functions are restricted
to be the hinge loss and ramp loss while the classifier is restricted to be
linear. This result is later extended by Chen et al. (2020) with linear
classifiers and Gaussian spurious features. The theoretical advances are
complemented by recent empirical success in gradual domain adaptation. Recent
works Chen and Chao (2021) extends the unsupervised gradual domain adaptation
problem to the case where intermediate domains are not already available.
Abnar et al. (2021); Sagawa et al. (2021) provides the first comprehensive
benchmark and datasets for both supervised and unsupervised gradual domain
adaptation.

##  3 Preliminaries

###  3.1 Problem Formulation

The problem of gradual domain adaptation proceeds sequentially through a
finite time horizon $\\{1,\dots,T\\}$ with evolving data domains. A data
distribution $P_{t}\in{\mathbb{R}}^{d}\times{\mathbb{R}}^{k}$ is realized at
each time step with the features denoted as $X\in{\mathbb{R}}^{d}$ and labels
as $Y\in{\mathbb{R}}^{k}$. With a given loss function $\ell(\cdot,\cdot)$, we
are interested in obtaining an effective classifier
$h\in\mathcal{H}:{\mathbb{R}}^{d}\rightarrow{\mathbb{R}}^{k}$ that minimizes a
given loss function on the target domain $P_{T}$, which is also the last
domain. With access to only $n$ samples from each intermediate domain
$P_{1},\ldots,P_{T-1}$, we seek to design algorithms that output a classifier
at each time step where the final classifier performs well on the target
domain.

Following the prior work (Kumar et al., 2020), we assume the shift is gradual
and the label distribution remains unchanged. To capture such a gradual shift,
we use the Wasserstein distance to measure the change between any two
consecutive domains. The Wasserstein distance offers a way to include a large
range of cases, including the case where the two measures of the data domains
are not on the same probability space (Cai and Lim, 2020).

######  Definition 3.1.

(Wasserstein distance) The $p$-th Wasserstein distance, denoted as $W_{p}$
distance, between two probability distribution $P,Q$ is defined as

$\displaystyle
W_{p}(P,Q)=\left(\inf_{\gamma\in\Gamma(P,Q)}\int\|x-y\|^{p}d\gamma(x,y)\right)^{1/p}\,,$

where $\Gamma(P,Q)$ denotes the set of all joint distribution $\gamma$ over
$(X,Y)$ such that $X\sim P$, $Y\sim Q$.

Intuitively, Wasserstein distance measures the minimum cost needed to move one
distribution to another. The flexibility of Wasserstein distance enables us to
derive tight theoretical results for a wider range of practical applications.
In comparison, previous results leverage $l_{1}$ distance Mansour et al.
(2009) or the Wasserstein-infinity $W_{\infty}$ distance (Kumar et al., 2020)
to capture non-stationarity. However, due to the monotonicity of the $W_{p}$
distance, the $W_{1}$ distance leads to tighter upper bounds and is more
commonly employed due to its low computational cost. Previous literature hence
offers limited insights whereas our results include this more general
scenario.

###  3.2 Assumptions

We formally describe the assumptions below.

######  Assumption 3.1.

For all $1\leq t\leq T$ and some constant $\Delta>0$, the $p$-th Wasserstein
distance between class conditional distance $P_{t,X\mid Y=y},P_{t+1,X\mid
Y=y}$ is bounded as

$\displaystyle W_{p}(P_{t,X\mid Y=y},P_{t+1,X\mid Y=y})\leq\Delta,\quad\forall
y\in\mathcal{Y}\,.$

######  Assumption 3.2.

The label distribution remains unchanged through out the time horizon, i.e.,
$\forall t\in[T]$,$P_{t}(Y=y)=P_{t+1}(Y=y)$.

We study the problem without restrictions on the specific form of the loss
function, and we only assume that the empirical loss function is bounded and
is hence Lipschitz continuous. This covers a rich class of loss functions,
including the logistic loss/binary cross-entropy, and hinge loss. Formally,
let $\ell_{h}$ be the loss function,
$\ell_{h}=\ell(h(x),y):\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$. We have the
following assumption.

######  Assumption 3.3.

The loss function $\ell_{h}$ is $\rho$-Lipschitz continuous and bounded such
that $\|\ell_{h}\|_{\infty}\leq M$.

This assumption is general as it holds when the input data are compact. In the
case where the input data fails to be compact, the assumption remains true
after the normalization of data. Moreover, we note that this assumption is
mainly for the convenience of technical analysis and is common in the
literature (Mansour et al., 2009; Cortes and Mohri, 2011; Kumar et al., 2020).

Before we present the main theoretical result, we first further define a few
notations and definitions needed for the theorem and the proof sketch in the
next section.

##### Notation

To simplify the notation, we let $Z=(X,Y)$ and use shorthand $Z_{1}^{T}$ for
$Z_{1},\ldots,Z_{T}$.

###  3.3 Other Technical Definitions

Our first tool is used to help us characterize the structure of sequential
domain adaptation. Under the statistical learning scenario with i.i.d. data,
Rademacher complexity serves as a well-known complexity notion to capture the
richness of the underlying hypothesis space. However, with the sequential
dependence, classical notions of complexity are insufficient to provide a
description of the problem. To capture the difficulty of sequential domain
adaptation, we use the sequential Rademacher complexity, which was originally
proposed for online learning where data comes one by one in sequence (Rakhlin
et al., 2015). To formally define the sequential Rademacher complexity, we
need to first introduce the $\mathcal{Z}$-valued tree.

######  Definition 3.2 ($\mathcal{Z}$-valued tree (Rakhlin et al., 2015)).

A path of length $T$ is defined by a sequence
$\epsilon=\left(\epsilon_{1},\ldots,\epsilon_{T}\right)\in\\{\pm 1\\}^{T}$.
Then, a $\mathcal{Z}$-valued tree $\mathbf{z}$ refers to a complete rooted
binary tree where nodes are labeled with elements of $\mathcal{Z}$. The tree
$\mathbf{z}$ can be identified by a sequence
$\left(\mathbf{z}_{1},\ldots,\mathbf{z}_{T}\right)$ of labeling functions
$\mathbf{z}_{i}:\\{\pm 1\\}^{i-1}\rightarrow\mathcal{Z}$. Specifically, the
root of the tree is labelled as $\mathbf{z}_{1}\in\mathcal{Z}$ and
$\mathbf{z}_{i}$ for $i>1$ is the label of the node when we follow a path of
length $i-1$ from the root, with $+1$ denotes “right” and $-1$ denotes “left”.

To shorthand the notation, we use $\mathbf{z}_{t}(\epsilon)$ to denote
$\mathbf{z}_{t}$ that depends only on $(\epsilon_{1},\ldots,\epsilon_{t-1})$.
When $(\epsilon_{1},\ldots,\epsilon_{T})$ are Rademacher random variables, we
can define the sequential Rademacher complexity of a function class
$\mathcal{H}$ as follows.

######  Definition 3.3 (Sequential Rademacher Complexity (Rakhlin et al.,
2015)).

For a function class $\mathcal{F}$, the sequential Rademancher complexity is
defined as

$\displaystyle\mathfrak{R}_{T}^{\mathrm{seq}}(\mathcal{F})=\sup_{\mathbf{z}}\mathbb{E}\left[\sup_{f\in\mathcal{F}}\frac{1}{T}\sum_{t=1}^{T}\epsilon_{t}f\left(z_{t}(\epsilon)\right)\right]\,,$
(1)

where the supremum is taken over all $\mathcal{Z}$-valued trees of depth $T$.

We next introduce the discrepancy measure, a key ingredient that helps us to
characterize the non-stationarity resulting from the shifting data domains.
This can be used to bridge the shift in data distribution with the shift in
errors incurred by the classifier.

######  Definition 3.4 (Discrepancy measure (Kuznetsov and Mohri, 2020)).

$\displaystyle\operatorname{disc}_{T}=$
$\displaystyle\sup_{h\in\mathcal{H}}\left(\mathbb{E}\left[\ell_{h}\left(X_{T},Y_{T}\right)\mid
Z_{1}^{T-1}\right]\frac{1}{T-1}\sum_{t=1}^{T-1}\mathbb{E}\left[\ell_{h}\left(X_{t},Y_{t}\right)\mid
Z_{1}^{t-1}\right]\right)\,.$ (2)

We will later show that the discrepancy measure can be directly upper-bounded
when the shift in class conditional distribution is gradual. We also note that
this notion is general and feasible to be estimated from data in practice
Kuznetsov and Mohri (2020). Similar notions have also been used extensively in
non-stationary time series analysis and mixing processes Kuznetsov and Mohri
(2014, 2017).

##  4 Theoretical Results

In this section, we provide our theoretical guarantees for the performance of
the final classifier learned in the setting described above. Our result is
algorithm agnostic and general to loss functions that satisfy Assumption 3.3.
We then discuss the implications of our results and give a proof sketch to
illustrate the main ideas.

The following theorem gives an upper bound of the expected loss of the learned
classifier on the last domain in terms of the shift $\Delta$, sequential
Rademacher complexity, and etc.

######  Theorem 4.1.

Under Assumptions 3.1, 3.3, with $n$ data points access to each data
distribution $P_{t}$, $t\in\\{1,\ldots,T\\}$, and loss function
$\ell_{h}=\ell(h(x),y):\mathcal{X}\times\mathcal{Y}\to\mathbb{R}$, the loss on
the last distribution incurred by a learned classifier $h\in\frac{1}{T-1}$ can
be upper bounded by

$\displaystyle\mathbb{E}\left[\ell_{h_{T}}\left(X_{T},Y_{T}\right)\mid
Z_{1}^{T-1}\right]$
$\displaystyle\leq\mathbb{E}\left[\ell_{h_{0}}\left(X_{T},Y_{T}\right)\mid
Z_{1}^{T-1}\right]+\underbrace{\frac{3}{T}+\frac{3M}{T}\sqrt{8\log\frac{1}{\delta}}}_{E_{1}}+\underbrace{\frac{1}{T}\sqrt{\frac{\text{VCdim}(\mathcal{H})+\log(2/\delta)}{2n}}+O\left(\frac{1}{\sqrt{nT}}\right)}_{E_{2}}$
$\displaystyle+\underbrace{18M\sqrt{4\pi\log
T}\mathfrak{R}_{T-1}^{seq}(\mathcal{F})+3T\rho\Delta}_{E_{3}}\,,$ (3)

where $\ell_{h}\in\mathcal{F}$, $\mathfrak{R}_{T}^{seq}(\mathcal{F})$ is the
sequential Rademacher complexity of $\mathcal{F}$, $\text{VCdim}(\mathcal{H})$
is the VC dimension of $\mathcal{H}$ and
$h_{0}=\operatorname{argmin}_{h\in\mathcal{H}}\frac{1}{T}\sum_{t=1}^{T}\ell\left(h(X_{t}),Y_{t}\right)$.

When $\ell_{h}\in\mathcal{F}$ is bounded and convex, the sequential Rademacher
complexity term is upper bounded by $O(\sqrt{1/nT})$ (Rakhlin et al., 2015).
For some complicated function classes, such as multi-layer neural networks,
they also enjoy a sequential Rademacher complexity of order $O(\sqrt{1/nT})$
(Rakhlin et al., 2015). Before we move to present a proof sketch of Theorem
4.1, we first discuss the implications of our theorem.

######  Remark 4.1.

There exists a non-trivial trade-off between $E_{1}+E_{2}$ and $E_{3}$ through
the length $T$. When $T$ is larger, all terms except for the terms in $E_{3}$
will be smaller while the terms in $E_{3}$ will be larger. Hence, it is not
always beneficial to have a longer trajectory.

######  Remark 4.2.

All terms in (4.1) except for the last term $3T\rho\Delta$ are determined
regardless of the algorithm. The last term depends on $\Delta$ which measures
the class conditional distance between any two consecutive domains. This
distance can potentially be minimized through learning an effective
representation of data.

##### Comparison with unsupervised gradual domain adaptation

Our result is only linear with respect to the average loss
$\mathbb{E}\left[\ell_{h_{0}}\left(X_{T},Y_{T}\right)\mid Z_{1}^{T-1}\right]$,
where
$h_{0}=\operatorname{argmin}_{h\in\mathcal{H}}\frac{1}{T}\sum_{t=1}^{T}\ell\left(h(X_{t}),Y_{t}\right)$.
In contrast, the previous upper bound given by Kumar et al. (2020), which is
for unsupervised gradual domain adaptation, is exponential with respect to the
initial loss on the first data domain. It remains unclear, however, if the
exponential cost is unavoidable when labels are missing during training as the
result by Kumar et al. (2020) is algorithm specific.

##### Comparison with multiple source domain adaptation

The setting of multiple source domain adaptation neglects the temporal
structure between training domains. Our results are comparable while dropping
the requirement of simultaneous access to all training domains. Our result
suffers from the same order of error with respect to the Rademacher complexity
and from the VC inequality with supervised multiple source domain adaptation
(MDA) (Wen et al., 2020a). However, for MDA, the error of a classifier $h$ on
the target domain also relies on the average error of $h$ on training domains.
We note that in comparison our results scales with the averaged error of the
best classifier on the training domains.

While we defer the full proof to the appendix, we now present a sketch of the
proof.

###### Proof Sketch.

With Assumption 3.1, we first show that when the Wasserstein distance between
two consecutive class conditional distributions is bounded, the discrepancy
measure is also bounded.

######  Lemma 4.1.

Under Assumption 3.3, the expected loss on two consecutive domains satisfy.

$\mathbb{E}_{\mu}[\ell_{h}(X,Y)]-\mathbb{E}_{\nu}[\ell_{h}(X^{\prime},Y^{\prime})]\leq\rho\Delta\,,$

where $\mu,\nu$ are the probability measure for $P_{t},P_{t+1}$, $(X,Y)\sim
P_{t}$, and $(X^{\prime},Y^{\prime})\sim P_{t+1}$.

Then we leverage this result to bound the loss incurred in expectation by the
same classifier on two consecutive data distributions. We start by decomposing
the discrepancy measure with an adjustable summation term as

$\displaystyle\operatorname{disc}_{T}\leq$
$\displaystyle\sup_{h\in\mathcal{H}}\left(\frac{1}{s}\sum_{t=T-s+1}^{T}\mathbb{E}\left[\ell_{h}\left(X_{t},Y_{t}\right)\mid
Z_{1}^{t-1}\right]\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\left[\ell_{h}\left(X_{t},Y_{t}\right)\mid
Z_{1}^{t-1}\right]\right)$
$\displaystyle+\sup_{h\in\mathcal{H}}\left(\mathbb{E}\left[\ell_{h}\left(X_{T},Y_{T}\right)\mid
Z_{1}^{T-1}\right]\frac{1}{s}\sum_{t=T-s+1}^{T}\mathbb{E}\left[\ell_{h}\left(X_{t},Y_{t}\right)\mid
Z_{1}^{t-1}\right]\right)\,.$

We show by manipulating this adjustable summation, the discrepancy measure can
indeed be directly obtained through an application of Lemma 4.1. We now start
to bound the learning error in interest by decomposing

$\displaystyle\mathbb{E}\left[\ell_{h_{T}}\left(X_{T},Y_{T}\right)\mid
Z_{1}^{T-1}\right]-\mathbb{E}\left[\ell_{h_{0}}\left(X_{T},Y_{T}\right)\mid
Z_{1}^{T-1}\right]$ $\displaystyle\leq$ $\displaystyle
2\Phi(Z_{1}^{T})+\left(\frac{1}{T}\sum^{T-1}_{t=1}\left[\ell_{h_{T}}\left(X_{t},Y_{t}\right)\right]-\frac{1}{T}\sum^{T-1}_{t=1}\ell_{h_{0}}\left(X_{T},Y_{T}\right)\right)\,,$

where
$\Phi\left(Z_{1}^{T}\right)=\sup_{h\in\mathcal{H}}\left(\mathbb{E}\left[\ell_{h}\left(X_{T},Y_{T}\right)\mid
Z_{1}^{T-1}\right]\right.$
$\left.-\sum_{t=1}^{T}\frac{1}{T}\ell_{h}\left(X_{t},Y_{t}\right)\right)$. The
term $\Phi\left(Z_{1}^{T}\right)$ can be upper bounded by Lemma B.1 Kuznetsov
and Mohri (2020) and thus it is left to bound the remaining term
$\frac{1}{T}\sum^{T-1}_{t=1}\left[\ell_{h_{T}}\left(X_{t},Y_{t}\right)\right]-\frac{1}{T}\sum^{T-1}_{t=1}\ell_{h_{0}}\left(X_{T},Y_{T}\right)$.
To upper bound this difference of average loss, we first compare the loss
incurred by a classifier learned by an optimal online learning algorithm to
$f_{0}$. By classic online learning theory results, the difference is upper
bounded by $O\left(\frac{1}{\sqrt{nT}}\right)$. Then we compare the optimal
online learning classifier to our final classifier $h_{T}$ and upper bound the
difference through the VC inequality Bousquet et al. (2004).

Lastly, we leverage results from the literature of non-stationary time series,
which is restated in the following lemma.

######  Lemma 4.2.

[Corollary 3 of Kuznetsov and Mohri (2020)] Let $q=(q_{1},\ldots,q_{T})$ be
real numbers. For any $\delta>0$, with probability at least $1-\delta$,

$\displaystyle\mathbb{E}\left[\ell_{h_{0}}\left(X_{T},Y_{T}\right)\mid
Z_{1}^{T}\right]\leq$
$\displaystyle\inf_{h\in\mathcal{H}}\mathbb{E}\left[\ell_{h}\left(X_{T},Y_{T}\right)\mid
Z_{1}^{T-1}\right]+\operatorname{disc}(\mathbf{q})$
$\displaystyle+\|\mathbf{q}\|_{2}+6M\sqrt{4\pi\log
T}\mathfrak{R}_{T}^{seq}(\mathcal{F})+M\|\mathbf{q}\|_{2}\sqrt{8\log\frac{1}{\delta}}\,.$
(4)

where $\operatorname{disc}_{T}$ is the discrepancy measure defined in
Definition 3.4 and $\mathfrak{R}_{T}^{seq}(\mathcal{F})$ is the sequential
Rademacher complexity.

We take $q=(q_{1},\ldots,q_{T})$ to be the uniform weights, $1/T$, for the
final bound. ∎

##  5 Insights for Practice

The key insight indicated by Theorem 4.1 and Remark 4.2 is that the bottleneck
of supervised gradual domain adaption is not only predetermined through the
set up of the problem but also rely heavily on $\rho\Delta$, where $\Delta$ is
the upper bound of the Wasserstein class conditional distance between two data
domains and $\rho$ is the Lipschitz constant of the loss function. In
practice, the loss function is often chosen beforehand and remains unchanged
through out the learning process. Therefore, the only term available to be
optimized is $\Delta$, which can be effectively reduced if a good
representation of data can be learned for classification. We give a feasible
primal-dual objective that learns a mapping function from input to feature
space concurrently with the original classification objective

##### A primal-dual objective formulation

Define $g$ to be a mapping that maps $X\in\mathbb{R}^{d}$ to some feature
space. We propose the learning objective as to learn a classifier $h$
simultaneously with the mapping function $g$ with the exposure of historical
data $Z_{1}^{T-1}$. With the feature $g(X)$ from the target domain, our
learning objective is now

$\displaystyle\mathbb{E}\left[\ell_{h}(g(X_{T}),Y_{T}))|Z_{1}^{T-1}\right]-\inf_{h^{\ast},g^{\ast}}\mathbb{E}\left[\ell_{h^{\ast}}(g^{\ast}(X_{T}),Y_{T})|Z_{1}^{T-1}\right]\,.$
(5)

Intuitively, this can be viewed as a combination of two optimization problems
where both $\Delta$ and the learning loss are minimized.

The objective (6) is hard to evaluate without further assumptions. Thus we
restrict our study to the case where both $g$ and $h$ are parametrizable.
Specifically, we assume $g$ is parameterized by $\omega$ and $h$ is
parameterized by $\theta$. Then we leverage the Wasserstein-$1$ distance’s
dual representation to derive a primal-dual formulation that can be
computationally feasible to evaluate.

$\displaystyle\min_{\theta}\max_{\omega}\mathbb{E}\left[\ell_{h_{\theta,T}}\left(g_{\omega}(X_{T}),Y_{T}\right)\mid
Z_{1}^{T-1}\right]+\lambda L_{D}\,,$ (6)

where
$L_{D}=\max_{t,t+1}\mathbb{E}_{P_{t}}\left[g_{\omega}(X_{t})\right]-\mathbb{E}_{P_{t+1}}\left[g_{\omega}(X_{t+1})\right]$
and $\lambda$ is a tunable parameter.

##### One-step and temporal variants

Notice that $L_{D}$ relies on the maximum distance across all domains. It is
thus hard to directly evaluate $L_{D}$ without simultaneous access to all
domains. With access only to the current and the past domains, we could
optimize the following one-step primal-dual loss at time $t$ instead.

$\displaystyle\min_{\theta}\max_{\omega}\mathbb{E}\left[\ell_{h_{\theta,t}}\left(g_{\omega}(X_{t}),Y_{t}\right)\mid
Z_{1}^{t}\right]+\lambda L_{D_{t}}\,,$ (7)

where
$L_{D_{t}}=\mathbb{E}_{P_{t}}\left[g_{\omega}(X_{t})\right]-\mathbb{E}_{P_{t-1}}\left[g_{\omega}(X_{t-1})\right]$.

Compared to the objective (6), the one-step loss (7) only gives us partial
information, and directly optimizing it may often lead to suboptimal
performance. While it is inevitable to optimize with some loss of information
under the problem set up, we use a temporal model (like an LSTM) to help
preserve historical data information in the process of learning mapping
function $g$. In particular, in the temporal variant, we will be using the
hidden states of an LSTM to dynamically summarize the features from all the
past domains. Then, we shall use the feature distribution computed from the
LSTM hidden state to align with the feature distribution at the current time
step.

To practically implement these objectives, we can use neural networks to learn
the representation and the classifier. To approximate the Wasserstein
distance, another neural network will be used as a critic to judge the quality
of the learned representations. To minimize the distance between
representations of different domains, one can use $W_{1}$ distance as an
empirical metric. Distance of the critic on different domains can then be
minimized to encourage the learning of similar representations. We note that
the use of $W_{1}$ distance, which is easy to evaluate empirically, to guide
representation learning has been practiced before Shen et al. (2018). We take
this approach further to the problem of gradual domain adaption.

##  6 Empirical Results

In this section, we perform experiments to demonstrate the effectiveness of
supervised gradual domain adaptation and compare our algorithm with No
Adaptation, Direct Adaptation, and Multiple Source Domain Adaptation (MDA) on
different datasets. We also verify the insights we obtained in the previous
section by answering the following three questions:

  1. 1.

How helpful is representation learning in gradual domain adaptation?
Theoretically, effective representation where the data drift is “small” helps
algorithms to gradually adapt to the evolving domains. This corresponds to
minimizing the $\rho\Delta$ term in our Theorem 4.1. We show that our
algorithm with objective (7) outperforms the objective of empirical risk (No
Adaptation).

  2. 2.

Can the one-step primal-dual loss (7) act as an substitute to optimization
objective (6)? Inspired by our theoretical results (Theorem 4.1), the primal-
dual optimization objective (6) should guide the adaptation process. However,
optimization of this objective requires simultaneous access to all data
domains. We use a temporal encoding (through a temporal model such as LSTM) of
historical data to demonstrate the importance of the information of past data
domains. We compare this to results obtained with a convolutional network
(CNN)-based model to verify that optimizing the one-step loss (7) with
temporal model could largely mitigate the information loss.

  3. 3.

Does the length of gradual domain adaptation affects the model’s ability to
adapt? Our theoretical results suggest that there exists an optimal length $T$
for gradual domain adaptation. Our empirical results corroborate this as when
the time horizon passes a certain threshold the model performance is
saturated.

###  6.1 Experimental Setting

We briefly introduce our experimental setting here, while more details and
additional experimental results can be found in the appendix. We repeat each
experiment over 5 random seeds and report the mean with $1$ std.

####  6.1.1 Dataset

Rotating MNIST This is a semi-synthetic dataset from the MNIST dataset. We
rotate the image continuously from $0-30$, $0-60$, and $0-120$ degrees across
the time horizon, forming 3 datasets. The degree of rotation increases
linearly as $t$ increases.

Portraits This dataset contains portraits of high school seniors across years
Ginosar et al. (2015). The data is splitted into domains by their year index.

FMOW This dataset is composed of over 1 million satellite images and their
building/land use labels from 62 categories Christie et al. (2018); Koh et al.
(2021) from $2002$-$2017$. The input is an RGB image of $224\times 224$ pixels
and each image comes with metadata of the year it is taken. The data is
splitted into domains chronologically and the target domain is year $2017$.
Our work is the first study of gradual domain adaptation with FMOW.

####  6.1.2 Algorithms and model architecture

No Adaptation For this method, we perform empirical risk minimization with
cross-entropy loss on the initial domain and then test on the target domain.
We use model VGG16 (Simonyan and Zisserman, 2014) for MNIST/Portrait, and
ResNet18 (He et al., 2016) for FMOW.

Direct Adaptation We group the training domains $t=1,\ldots,T-1$ and let the
algorithm learn to adapt from the grouped domain to the target domain. We use
cross-entropy loss with objective (7) and VGG16 (Simonyan and Zisserman, 2014)
for MNIST/Portrait and ResNet18 (He et al., 2016) for FMOW. To test the
effectiveness of the encoding historical representation, we use a 2-layer GRU
for MNIST/Portrait and a 1-layer LTSM for FMOW.

Multiple Source Domain Adaptation (MDA) We compare with algorithms designed
for MDA, where the algorithm has simultaneous access to multiple labeled
domain $t=1,\ldots,T-1$ and learns to adapt to the target domain. We use
maxmin and dynamic variants of MDAN (Zhao et al., 2018), Fish Shi et al.
(2022) and DARN Wen et al. (2020b) as our baseline algorithms. We also provide
the comparisons where the MDA algorithm only has access to the last two source
domains ($T-2,T-1$).

Gradual Adaptations Our proposed approach trains the algorithm to sequentially
adapt from the initial domain $t=1$ to the last domain $t=T$. At each time
step, the algorithm only has access to two consecutive domains. We use cross-
entropy loss with objective (7) to perform successive adaptations with
gradually changing domains. The rest of the setup is the same as the ones for
Direct Adaptation.

###  6.2 Experimental Results

Table 1: Results on rotating MNIST dataset with Gradual Adaptation on 5
domains, Direct Adaptation, and No Adaptation.  Rotating MNIST
---
| Gradual Adaptation with 5 domains | Direct Adaptation | No Adaptation
| CNN | LSTM | CNN | LSTM | CNN
0-30 degree | 90.21 $\pm$ 0.48 |  94.83 $\pm$ 0.49 | 77.97 $\pm$ 0.99 | 89.72 $\pm$ 0.73 | 79.76 $\pm$ 3.20
0-60 degree | 87.35 $\pm$ 1.02 |  92.52 $\pm$ 0.25 | 73.27 $\pm$ 1.51 | 88.53 $\pm$ 0.76 | 58.36 $\pm$ 2.59
0-120 degree | 82.38 $\pm$ 0.57 |  89.72 $\pm$ 0.35 | 62.52 $\pm$ 1.06 | 84.30 $\pm$ 2.60 | 38.25 $\pm$ 0.61

##### Learning representations further helps in gradual adaptation

On rotating MNIST, the performance of the model is better in most cases when
adaptation is considered (Table 1), which demonstrates the benefit of learning
proper representations. With a CNN architecture, the only exception is when
the shift in the domain is relatively small ($0$ to $30$ degree), where the No
Adaptation method achieves higher accuracy than the Direct Adaptation method
by $2\%$. However, when the shift in domains is relatively large, Adaptation
methods are shown to be more successful in this case and this subtle advantage
of No Adaptation no longer holds. Furthermore, Gradual Adaptation further
enhances this outperformance significantly. This observation shows the
advantage of sequential adaptation versus direct adaptation.

We further show that the performance of the algorithm monotonically increases
as it progress to adapt to each domain and learn a cross-domain
representation. Figure 1 shows the trend in algorithm performance on rotating
MNIST and FMOW.

Table 2: Results on rotating MNIST dataset with Gradual Adaptation on 5
domains and MDA (MDAN) (Zhao et al., 2018).

Rotating MNIST
---
|  | Gradual Adaptation with 5 domains
---
MDAN
| CNN | LSTM | Maxmin | Dynamic |  | Dynamic
---
with last 2 domain
0-30 degree | 90.21 $\pm$ 0.48 | 94.83 $\pm$ 0.49 | 93.62 $\pm$ 0.87 |  95.79 $\pm$ 0.33 | 83.04 $\pm$ 0.29
0-60 degree | 87.35 $\pm$ 1.02 |  92.52 $\pm$ 0.25 | 91.99 $\pm$ 0.51 | 92.27 $\pm$ 0.26 | 61.49 $\pm$ 0.72
0-120 degree | 82.38 $\pm$ 0.57 |  89.72 $\pm$ 0.35 | 87.25 $\pm$ 0.52 | 88.57 $\pm$ 0.21 | 44.14 $\pm$ 1.77

Table 3: Results on FMOW with Gradual Adaptation with 3 domains, Direct
Adaptation, and No Adaptation.  FMOW
---
| No Adaptation
---
with ERM
| Direct Adaptation
---
with CNN
| Gradual Adaptation
---
with CNN
| Gradual Adaptation
---
with LSTM
33.10 $\pm$ 1.94 | 41.94 $\pm$ 2.73 | 36.86 $\pm$ 1.91 |  43.52 $\pm$ 1.40
Table 4: Results on Portraits with Gradual Adaptation for different lengths of
horizon $T$, Direct Adaptation, and No Adaptation.  Portraits
---
| CNN | LSTM
No Adpatation | 76.01 $\pm$ 1.45 | N/A
Direct Adaptation | 86.86 $\pm$ 0.84 | N/A
Gradual - 5 Domains | 87.77 $\pm$ 0.98 | 87.41 $\pm$ 0.76
Gradual - 7 Domains | 89.14 $\pm$ 1.64 | 89.15 $\pm$ 1.12
Gradual - 9 Domains |  90.46 $\pm$ 0.54 |  89.88 $\pm$ 0.54
Gradual - 11 Domains |  90.56 $\pm$ 1.21 |  90.93 $\pm$ 0.75

##### One-step loss is insufficient as a substitute, but can be improved by
temporal model

The inefficiency of adaptation without historical information appears with all
datasets we have considered, reflected through Table 1, 3, 4. In almost all
cases, we observe that learning with a temporal model (LSTM) achieves better
accuracy than a convolutional model (CNN). The gap is especially large on
FMOW, the large-scale dataset in our experiments. We suspect that optimizing
with only partial information can lead to suboptimal performance on such a
complicated task. This is reflected through the better performance achieved by
Direct Adaptation with CNN when compared to Gradual Adaptation with CNN and 3
domains (Table 3). In contrast, Gradual Adaptation with LSTM overtakes the
performance of Direct Adaptation, suggesting the importance of historical
representation. Another evidence is that Figure 1 shows that Gradual
Adaptation with a temporal model performs better on all indexes of domains on
rotating MNIST and FMOW.

(a) Rotating MNIST

(b) FMOW

Figure 1: Figure 1(a) compares the training curves on rotating MNIST with
maximum rotation of 120 degrees. Figure 1(b) compares the training curves on
FMOW.

##### Existence of optimal time horizon

With the Portraits dataset and different lengths of horizon $T$, we verify
that optimal time horizon can be reached when model performance is saturated
in Table 4. The performance of the model increases drastically when the shifts
in domains are considered, shown by the difference in the performance of No
Adaptation, Direct Adaptation, and Gradual Adaptation with $5$ and $7$
domains. However, this increase in performance becomes relatively negligible
when $T$ is large (the performance of Gradual Adaptation with $9$ and $11$
domains is very small). This rate of growth in accuracy implies that there
exists an optimal number of domains.

Table 5: Results on rotating MNIST dataset with Gradual Adaptation on 5 domains and MDA methods, Fish Shi et al. (2022) and DARN Wen et al. (2020b) | Fish | DARN | Ours
---|---|---|---
0-30 degree | 95.83 $\pm$ 0.13 | 94.20 $\pm$ 0.27 | 94.83 $\pm$ 0.49
0-60 degree | 90.57 $\pm$ 0.37 | 89.50 $\pm$ 0.12 | 92.52 $\pm$ 0.25
0-120 degree | 83.26 $\pm$ 1.58 | 82.28 $\pm$ 2.42 | 89.72 $\pm$ 0.35
Figure 2: PCA projection plot of learned representation Figure 3: Euclidean
distance to target domain of the projections of learned representations.

##### Comparison with MDA

Lastly, we remark on the results (Table 2 and 5) achieved by Gradual
Adaptation in comparison with MDA methods (MDAN Zhao et al. (2018), DARN Wen
et al. (2020b) and Fish Shi et al. (2022)). On Rotating MNIST, we note that
Gradual Adaptation outperforms MDA methods when the shift is large ($60$ and
$120$ degree rotation) while relaxing on the requirement of simultaneous
access to all source domains. It is only when the shift is relatively small
($30$-degree rotation), MDA method DARN achieves better result than ours. When
MDA method is only presented with the last two training domains, Gradual
Adaptation offers noticeable advantages regardless of the shift in domain
(Table 2). This demonstrates the potential of graduate domain adaptation in
real applications that even when the data are not simultaneously presented it
is possible to achieve a competitive or even better performance.

One possible reason for this can be illustrated by Figure 2 and Figure 3, in
which we plot the PCA projections and the Euclidean distance to the target
domain of learned representations. From Figure 2, we can see that gradual
domain adaptation method is able to gradually learn an increasingly closer
representation of the source domain to the target domain. This helps our
method to make our prediction based on more relevant features while MDA
methods may be hindered by not-so-relevant features from multiple domains.

##  7 Conclusion

We studied the problem of supervised gradual domain adaptation, which arises
naturally in applications with temporal nature. In this setting, we provide
the first learning bound of the problem and our results are general to a range
of loss functions and are algorithm agnostic. Based on the theoretical insight
offered by our theorem, we designed a primal-dual learning objective to learn
an effective representation across domains while learning a classifier. We
analyze the implications of our results through experiments on a wide range of
datasets.

## References

  * Abnar et al. (2021) S. Abnar, R. v. d. Berg, G. Ghiasi, M. Dehghani, N. Kalchbrenner, and H. Sedghi.  Gradual domain adaptation in the wild: When intermediate distributions are absent.  _arXiv preprint arXiv:2106.06080_ , 2021.
  * Axelrod et al. (2011) A. Axelrod, X. He, and J. Gao.  Domain adaptation via pseudo in-domain data selection.  In _Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing_ , pages 355–362, 2011.
  * Aytar and Zisserman (2011) Y. Aytar and A. Zisserman.  Tabula rasa: Model transfer for object category detection.  In _The International Conference on Computer Vision_ , pages 2252–2259. IEEE, 2011.
  * Blitzer et al. (2006) J. Blitzer, R. McDonald, and F. Pereira.  Domain adaptation with structural correspondence learning.  In _Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing_ , pages 120–128, 2006.
  * Blitzer et al. (2007) J. Blitzer, M. Dredze, and F. Pereira.  Biographies, bollywood, boom-boxes and blenders: Domain adaptation for sentiment classification.  In _Proceedings of the 45th annual meeting of the association of computational linguistics_ , pages 440–447, 2007.
  * Bobu et al. (2018) A. Bobu, E. Tzeng, J. Hoffman, and T. Darrell.  Adapting to continuously shifting domains.  In _International Conference on Learning Representations Workshop_ , 2018.
  * Bousquet et al. (2004) O. Bousquet, S. Boucheron, and G. Lugosi.  Introduction to statistical learning theory.  _Advanced Lectures on Machine Learning_ , pages 169–207, 2004.
  * Cai and Lim (2020) Y. Cai and L.-H. Lim.  Distances between probability distributions of different dimensions.  _arXiv preprint arXiv:2011.00629_ , 2020.
  * Chen and Chao (2021) H.-Y. Chen and W.-L. Chao.  Gradual domain adaptation without indexed intermediate domains.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Chen et al. (2020) Y. Chen, C. Wei, A. Kumar, and T. Ma.  Self-training avoids using spurious features under domain shift.  _Advances in Neural Information Processing Systems_ , 33:21061–21071, 2020.
  * Christie et al. (2018) G. Christie, N. Fendley, J. Wilson, and R. Mukherjee.  Functional map of the world.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 6172–6180, 2018.
  * Cortes and Mohri (2011) C. Cortes and M. Mohri.  Domain adaptation in regression.  In _International Conference on Algorithmic Learning Theory_ , pages 308–323. Springer, 2011.
  * David et al. (2010) S. B. David, T. Lu, T. Luu, and D. Pál.  Impossibility theorems for domain adaptation.  In _Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics_ , pages 129–136. JMLR Workshop and Conference Proceedings, 2010.
  * Duan et al. (2012) L. Duan, D. Xu, and I. Tsang.  Learning with augmented features for heterogeneous domain adaptation.  In _Proceedings of the 29th International Conference on Machine Learning, ICML 2012_ , 2012.
  * Gadermayr et al. (2018) M. Gadermayr, D. Eschweiler, B. M. Klinkhammer, P. Boor, and D. Merhof.  Gradual domain adaptation for segmenting whole slide images showing pathological variability.  In _International Conference on Image and Signal Processing_ , pages 461–469. Springer, 2018.
  * Ginosar et al. (2015) S. Ginosar, K. Rakelly, S. Sachs, B. Yin, and A. A. Efros.  A century of portraits: A visual historical record of american high school yearbooks.  In _Proceedings of the IEEE International Conference on Computer Vision Workshops_ , pages 1–7, 2015.
  * Gulrajani et al. (2017) I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. Courville.  Improved training of wasserstein gans.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , pages 5769–5779, 2017.
  * He et al. (2016) K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 770–778, 2016.
  * Hoffman et al. (2013) J. Hoffman, E. Rodner, J. Donahue, K. Saenko, and T. Darrell.  Efficient learning of domain-invariant image representations.  In _The International Conference on Learning Representations_ , 2013\.
  * Hoffman et al. (2014) J. Hoffman, T. Darrell, and K. Saenko.  Continuous manifold based adaptation for evolving visual domains.  In _2014 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 867–874, 2014.  doi: 10.1109/CVPR.2014.116.
  * Hoffman et al. (2018a) J. Hoffman, M. Mohri, and N. Zhang.  Algorithms and theory for multiple-source adaptation.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , pages 8256–8266, 2018a.
  * Hoffman et al. (2018b) J. Hoffman, E. Tzeng, T. Park, J.-Y. Zhu, P. Isola, K. Saenko, A. Efros, and T. Darrell.  Cycada: Cycle-consistent adversarial domain adaptation.  In _International Conference on Machine Learning_ , pages 1989–1998. PMLR, 2018b.
  * Koh et al. (2021) P. W. Koh, S. Sagawa, H. Marklund, S. M. Xie, M. Zhang, A. Balsubramani, W. Hu, M. Yasunaga, R. L. Phillips, I. Gao, et al.  Wilds: A benchmark of in-the-wild distribution shifts.  In _International Conference on Machine Learning_ , pages 5637–5664. PMLR, 2021.
  * Kulis et al. (2011) B. Kulis, K. Saenko, and T. Darrell.  What you saw is not what you get: Domain adaptation using asymmetric kernel transforms.  In _Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 1785–1792, 2011.
  * Kumar et al. (2020) A. Kumar, T. Ma, and P. Liang.  Understanding self-training for gradual domain adaptation.  In _International Conference on Machine Learning_ , pages 5468–5479. PMLR, 2020.
  * Kuznetsov and Mohri (2014) V. Kuznetsov and M. Mohri.  Generalization bounds for time series prediction with non-stationary processes.  In _International Conference on Algorithmic Learning Theory_ , pages 260–274. Springer, 2014.
  * Kuznetsov and Mohri (2017) V. Kuznetsov and M. Mohri.  Generalization bounds for non-stationary mixing processes.  _Machine Learning_ , 106(1):93–117, 2017.
  * Kuznetsov and Mohri (2020) V. Kuznetsov and M. Mohri.  Discrepancy-based theory and algorithms for forecasting non-stationary time series.  _Annals of Mathematics and Artificial Intelligence_ , 88(4):367–399, 2020.
  * Mansour et al. (2009) Y. Mansour, M. Mohri, and A. Rostamizadeh.  Domain adaptation: Learning bounds and algorithms.  In _22nd Conference on Learning Theory_ , 2009.
  * Mansour et al. (2021) Y. Mansour, M. Mohri, J. Ro, A. T. Suresh, and K. Wu.  A theory of multiple-source adaptation with limited target labeled data.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2332–2340. PMLR, 2021.
  * Rakhlin et al. (2015) A. Rakhlin, K. Sridharan, and A. Tewari.  Online learning via sequential complexities.  _Journal of Machine Learning Research_ , 16:155–186, 2015\.
  * Saenko et al. (2010) K. Saenko, B. Kulis, M. Fritz, and T. Darrell.  Adapting visual category models to new domains.  In _European Conference on Computer Vision_ , pages 213–226. Springer, 2010.
  * Sagawa et al. (2021) S. Sagawa, P. W. Koh, T. Lee, I. Gao, S. M. Xie, K. Shen, A. Kumar, W. Hu, M. Yasunaga, H. Marklund, et al.  Extending the wilds benchmark for unsupervised adaptation.  In _Advances in Neural Information Processing Systems Workshop on Distribution Shifts: Connecting Methods and Applications_ , 2021.
  * Shen et al. (2018) J. Shen, Y. Qu, W. Zhang, and Y. Yu.  Wasserstein distance guided representation learning for domain adaptation.  In _Thirty-Second AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Shi et al. (2022) Y. Shi et al.  Gradient matching for domain generalization.  In _ICLR_ , 2022.
  * Sim et al. (2018) K. C. Sim, A. Narayanan, A. Misra, A. Tripathi, G. Pundak, T. N. Sainath, P. Haghani, B. Li, and M. Bacchiani.  Domain adaptation using factorized hidden layer for robust automatic speech recognition.  In _Interspeech_ , pages 892–896, 2018.
  * Simonyan and Zisserman (2014) K. Simonyan and A. Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Sun et al. (2017) S. Sun, B. Zhang, L. Xie, and Y. Zhang.  An unsupervised deep domain adaptation approach for robust speech recognition.  _Neurocomputing_ , 257:79–87, 2017.
  * Venkateswara et al. (2017) H. Venkateswara, J. Eusebio, S. Chakraborty, and S. Panchanathan.  Deep hashing network for unsupervised domain adaptation.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 5018–5027, 2017.
  * Wen et al. (2020a) J. Wen, R. Greiner, and D. Schuurmans.  Domain aggregation networks for multi-source domain adaptation.  In _International Conference on Machine Learning_ , pages 10214–10224. PMLR, 2020a.
  * Wen et al. (2020b) J. Wen et al.  Domain aggregation networks for multi-source domain adaptation.  In _ICML_ , 2020b.
  * Wu et al. (2019a) Y. Wu, E. Winston, D. Kaushik, and Z. Lipton.  Domain adaptation with asymmetrically-relaxed distribution alignment.  In _International Conference on Machine Learning_ , pages 6872–6881. PMLR, 2019a.
  * Wu et al. (2019b) Z. Wu, X. Wang, J. E. Gonzalez, T. Goldstein, and L. S. Davis.  Ace: Adapting to changing environments for semantic segmentation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 2121–2130, 2019b.
  * Wulfmeier et al. (2018) M. Wulfmeier, A. Bewley, and I. Posner.  Incremental adversarial domain adaptation for continually changing environments.  In _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 4489–4495. IEEE, 2018.
  * Yang et al. (2007) J. Yang, R. Yan, and A. G. Hauptmann.  Adapting svm classifiers to data with shifted distributions.  In _Seventh IEEE International Conference on Data Mining Workshops (ICDMW 2007)_ , pages 69–76. IEEE, 2007.
  * Zhao et al. (2018) H. Zhao, S. Zhang, G. Wu, J. M. Moura, J. P. Costeira, and G. J. Gordon.  Adversarial multiple source domain adaptation.  _Advances in Neural Information Processing Systems_ , 31:8559–8570, 2018.
  * Zhao et al. (2019a) H. Zhao, R. T. Des Combes, K. Zhang, and G. Gordon.  On learning invariant representations for domain adaptation.  In _International Conference on Machine Learning_ , pages 7523–7532. PMLR, 2019a.
  * Zhao et al. (2020) H. Zhao, C. Dan, B. Aragam, T. S. Jaakkola, G. J. Gordon, and P. Ravikumar.  Fundamental limits and tradeoffs in invariant representation learning.  _arXiv preprint arXiv:2012.10713_ , 2020.
  * Zhao et al. (2019b) S. Zhao, B. Li, X. Yue, Y. Gu, P. Xu, R. Tan, Hu, H. Chai, and K. Keutzer.  Multi-source domain adaptation for semantic segmentation.  In _Advances in Neural Information Processing Systems_ , 2019b.

##  A Proof of lemma 4.1

See 4.1

###### Proof.

Let $\gamma_{Y,Y^{\prime}}$ denotes the coupling between the conditional
measure $\mu_{X\mid Y}$ and $\nu_{X^{\prime}\mid Y^{\prime}}$. Then,

$\displaystyle W_{p}^{p}(P_{t},P_{t+1})$
$\displaystyle=\inf_{\gamma}\mathbb{E}_{\gamma}[\|(X,Y)-(X^{\prime},Y^{\prime})\|^{p}]$
$\displaystyle=\inf_{\gamma}\mathbb{E}_{Y,Y^{\prime}}\mathbb{E}_{X,X^{\prime}\mid
Y,Y^{\prime}}[\|(X,Y)-(X^{\prime},Y^{\prime})\|^{p}]$
$\displaystyle\leq\inf_{\gamma,Y=Y^{\prime}}\mathbb{E}_{Y,Y^{\prime}}\mathbb{E}_{X,X^{\prime}\mid
Y,Y^{\prime}}[\|(X,Y)-(X^{\prime},Y^{\prime})\|^{p}]$
$\displaystyle=\inf_{\gamma,Y=Y^{\prime}}\mathbb{E}_{Y,Y^{\prime}}\mathbb{E}_{X,X^{\prime}\mid
Y,Y^{\prime}}[\|X-X^{\prime}\|^{p}]$
$\displaystyle=\mathbb{E}_{Y,Y^{\prime}}\inf_{\gamma_{Y,Y^{\prime}}}\mathbb{E}_{X,X^{\prime}\mid
Y,Y^{\prime}}[\|X-X^{\prime}\|^{p}]$
$\displaystyle=\mathbb{E}_{Y,Y^{\prime}}W_{p}^{p}(\mu_{X\mid
Y},\nu_{X^{\prime}\mid Y^{\prime}})$
$\displaystyle=\sum_{y\in\mathcal{Y}}\Pr(Y=Y^{\prime}=y)\cdot
W_{p}^{p}(P_{t,X\mid Y},P_{t+1,X^{\prime}\mid Y^{\prime}})$
$\displaystyle\leq\Delta^{p}\,.$

With this, we then bound the difference of errors of any classifier $h$ over
two distributions $\mu$ and $\nu$ using the Wasserstein distance. Let $\gamma$
be any coupling between $\mu$ and $\nu$, we have

$\displaystyle\mathbb{E}_{\mu}[\ell_{h}(X,Y)]-\mathbb{E}_{\nu}[\ell_{h}(X^{\prime},Y^{\prime})]$
$\displaystyle=\int\ell_{h}(X,Y)~{}d\mu-\int\ell_{h}(X^{\prime},Y^{\prime})~{}d\nu$
$\displaystyle=\int\ell_{h}(X,Y)~{}d\gamma-\int\ell_{h}(X^{\prime},Y^{\prime})~{}d\gamma$
$\displaystyle\leq\left|\int\ell_{h}(X,Y)~{}d\gamma-\int\ell_{h}(X^{\prime},Y^{\prime})~{}d\gamma\right|$
$\displaystyle\leq\int\left|\ell_{h}(X,Y)-\ell_{h}(X^{\prime},Y^{\prime})\right|~{}d\gamma$
$\displaystyle\leq\rho\int\|X-X^{\prime}\|+|Y-Y^{\prime}|~{}d\gamma\,.$

Since the above inequality holds for any coupling $\gamma$ over $\mu$ and
$\nu$, hence the following inequality holds:

$\mathbb{E}_{\mu}[\ell_{h}(X,Y)]-\mathbb{E}_{\nu}[\ell_{h}(X^{\prime},Y^{\prime})]\leq\rho\inf_{\gamma}\int\|X-X^{\prime}\|+|Y-Y^{\prime}|~{}d\gamma=\rho
W_{1}(\mu,\nu)\leq\rho W_{p}(\mu,\nu)\leq\rho\Delta\,,$

where the second to last inequality is due to the monotonicity of the
$W_{p}(\cdot,\cdot)$ metric. ∎

##  B Proof of Theorem 4.1

To simplify the notation, we let $f(x,y)=\ell(h(x),y)$ and denote the function
class of $f$, $\mathcal{F}$ such that $f\in\mathcal{F}$. We first state a few
results from non-stationary time series analysis Kuznetsov and Mohri (2020),
which are used in our theorem.

######  Lemma B.1 (Corollary 2 Kuznetsov and Mohri (2020)).

For any $\delta>0$, with probability at least $1-\delta$,

$\displaystyle\mathbb{E}\left[f\left(Z_{T+1}\right)\mid
Z_{1}^{T}\right]\leq\sum_{t=1}^{T}\frac{1}{T}f\left(Z_{t}\right)+\operatorname{disc}_{T}+\frac{1}{T}+6M\sqrt{4\pi\log
T\Re_{T-1}^{seq}(\mathcal{F})+M\frac{1}{T}}\sqrt{8\log\frac{1}{\delta}}\,,$

where $\operatorname{disc}_{T}$ is the discrepancy measure defined in
Definition 3.4 and $\mathfrak{R}_{T}^{seq}(\mathcal{F})$ is the sequential
Rademancher complexity.

See 4.2

See 4.1

###### Proof.

With Lemma 4.1, we first show that the discrepancy measure can also be bounded
by $\rho\Delta$, the maximum Wasserstein distance between any two consecutive
data distribution. We start by decomposing the discrepancy measure utilizing
an adjustable summation
$\frac{1}{s}\sum_{t=T-s+1}^{T}\mathbb{E}\left[f\left(Z_{t}\right)\mid
Z_{1}^{t-1}\right]$,

$\displaystyle\operatorname{disc}_{T}\leq$
$\displaystyle\sup_{f\in\mathcal{F}}\left(\frac{1}{s}\sum_{t=T-s+1}^{T}\mathbb{E}\left[f\left(Z_{t}\right)\mid
Z_{1}^{t-1}\right]-\frac{1}{T}\sum_{t=1}^{T}\mathbb{E}\left[f\left(Z_{t}\right)\mid
Z_{1}^{t-1}\right]\right)$
$\displaystyle+\sup_{f\in\mathcal{F}}\left(\mathbb{E}\left[f\left(Z_{T}\right)\mid
Z_{1}^{T-1}\right]-\frac{1}{s}\sum_{t=T-s+1}^{T}\mathbb{E}\left[f\left(Z_{t}\right)\mid
Z_{1}^{t-1}\right]\right)\,.$

Notice that the second term can be further decomposed as,

$\displaystyle\sup_{f\in\mathcal{F}}\left(\mathbb{E}\left[f\left(Z_{T}\right)\mid
Z_{1}^{T-1}\right]-\frac{1}{s}\sum_{t=T-s+1}^{T}\mathbb{E}\left[f\left(Z_{t}\right)\mid
Z_{1}^{t-1}\right]\right)$ $\displaystyle\leq$
$\displaystyle\frac{1}{s}\sum^{T-s+1}_{t=1}\sup_{f\in\mathcal{F}}\left(\mathbb{E}\left[f(Z_{T})\mid
Z_{1}^{T-1}\right]-\mathbb{E}\left[f\left(Z_{t}\right)\mid
Z_{1}^{t-1}\right]\right)$ $\displaystyle\leq$
$\displaystyle\frac{1}{s}\sum^{T-s+1}_{t=1}\sum_{r=t}^{T}\sup_{f\in\mathcal{F}}\left(\mathbb{E}\left[f\left(Z_{r+1}\right)\mid
Z_{1}^{r}\right]-\mathbb{E}\left[f\left(Z_{r}\right)\mid
Z_{1}^{r-1}\right]\right)\,.$

As the supremum is taken over $f\in\mathcal{F}$, this cumulative difference
term can be understood as comparing the loss caused by the same classifier
along the trajectory across the time horizon. As we have shown in Lemma 4.1,
for any classifier, the loss incurred on two consecutive distribution of
bounded $W_{p}$ distance of $\Delta$ is at most $\rho\Delta$. Thus we have
$\operatorname{disc}_{T}\leq T\rho\Delta$.

Armed with the bounded discrepancy measure, we are now ready to bound the
learning error in interest. Let us first define
$f_{0}=\operatorname{argmin}_{f\in\mathcal{F}}\sum_{t=1}^{T}\frac{1}{T}f\left(Z_{t}\right)$
and
$\Phi\left(Z_{1}^{T}\right)=\sup_{f\in\mathcal{F}}\left(\mathbb{E}\left[f\left(Z_{T}\right)\mid
Z_{1}^{T-1}\right]\right.$
$\left.-\sum_{t=1}^{T}\frac{1}{T}f\left(Z_{t}\right)\right)$. Then the
conditional expected difference between $\ell_{h_{T}}\left(X_{T},Y_{T}\right)$
and $f_{0}$ can be upper bounded by $\Phi\left(Z_{1}^{T}\right)$.

$\displaystyle\mathbb{E}\left[\ell_{h_{T}}\left(X_{T},Y_{T}\right)\mid
Z_{1}^{T-1}\right]-\mathbb{E}\left[f_{0}\left(Z_{T}\right)\mid
Z_{1}^{T-1}\right]$ $\displaystyle=$
$\displaystyle\left(\mathbb{E}\left[\ell_{h_{T}}\left(X_{T},Y_{T}\right)\mid
Z_{1}^{T-1}\right]-\frac{1}{T}\sum^{T-1}_{t=1}\left[\ell_{h_{T}}\left(X_{t},Y_{t}\right)\right]\right)+\left(\frac{1}{T}\sum^{T-1}_{t=1}\left[\ell_{h_{T}}\left(X_{t},Y_{t}\right)\right]-\frac{1}{T}\sum^{T-1}_{t=1}f_{0}\left(Z_{t}\right)\right)$
$\displaystyle+$
$\displaystyle\left(\frac{1}{T}\sum^{T-1}_{t=1}f_{0}\left(Z_{t}\right)-\mathbb{E}\left[f_{0}\left(Z_{T+1}\right)\mid
Z_{1}^{T-1}\right]\right)$ $\displaystyle\leq$ $\displaystyle
2\Phi(Z_{1}^{T})+\left(\frac{1}{T}\sum^{T-1}_{t=1}\left[\ell_{h_{T}}\left(X_{t},Y_{t}\right)\right]-\frac{1}{T}\sum^{T-1}_{t=1}f_{0}\left(Z_{t}\right)\right)\,.$

By Lemma B.1, for any $\delta>0$, with probability at least $1-\delta$, the
following inequality holds for any $f$

$\displaystyle\mathbb{E}\left[f\left(Z_{T}\right)\mid Z_{1}^{T-1}\right]$
$\displaystyle\leq\frac{1}{T}\sum_{t=1}^{T-1}f\left(Z_{t}\right)+\operatorname{disc}_{T}+\frac{1}{T}+6M\sqrt{4\pi\log
T}\mathcal{R}_{T-1}^{seq}(\mathcal{F})+\frac{M}{T}\sqrt{8\log\frac{1}{\delta}}\,.$

Rearranging the terms, substituting the upper bound of
$\operatorname{disc}_{T}$ and hence we have that

$\displaystyle\Phi\left(Z_{1}^{T}\right)\leq
T\rho\Delta+\frac{1}{T}+6M\sqrt{4\pi\log
T}\mathcal{R}_{T-1}^{seq}(\mathcal{F})+\frac{M}{T}\sqrt{8\log\frac{1}{\delta}}\,.$

It remains to bound
$\frac{1}{T}\sum^{T-1}_{t=1}\left[\ell_{h_{T}}\left(X_{t},Y_{t}\right)\right]-\frac{1}{T}\sum^{T-1}_{t=1}f_{0}\left(Z_{t}\right)$,
where we leverage classical results from online learning literature. Let
$\hat{h}_{t}$ be the classifier picked by an optimal online learning algorithm
at time $t$. Then with a total $nT$ number of data point, the optimal
algorithm will suffer an additional loss of at most $\mathcal{O}\sqrt{nT}$
compared to the optimal loss. Thus we have

$\displaystyle\frac{1}{T}\sum^{T-1}_{t=1}\mathbb{E}\left[\ell_{\hat{h}_{t}}\left(X_{t},Y_{t}\right)\right]-\frac{1}{T}\sum^{T-1}_{t=1}f_{0}\left(Z_{t}\right)=O\left(\frac{1}{\sqrt{nT}}\right)\,.$

Further, the difference between our classifier and the classifier picked by
the online learning algorithm
$\sum^{T-1}_{t=1}\left[\ell_{h_{T}}\left(X_{t},Y_{t}\right)\right]-\sum^{T-1}_{t=1}\mathbb{E}\left[\ell_{\hat{h}_{t}}\left(X_{t},Y_{t}\right)\right]$
can be upper bounded by the VC inequality (Section 3.5 Bousquet et al. (2004))
as

$\displaystyle\frac{1}{T}\sum^{T-1}_{t=1}\left(\mathbb{E}\left[\ell_{h_{T}}\left(X_{t},Y_{t}\right)\right]-\mathbb{E}\left[\ell_{\hat{h}_{t}}\left(X_{t},Y_{t}\right)\right]\right)\leq$
$\displaystyle\frac{1}{T}\sum^{T-1}_{t=1}\left(\mathbb{E}\left[\ell_{h_{T}}\left(X_{t},Y_{t}\right)\right]-\min_{\tilde{h}}\mathbb{E}\left[\ell_{\tilde{h}}\left(X_{t},Y_{t}\right)\right]\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{T}\sqrt{\frac{\text{VCdim}(\mathcal{H})+\log(2/\delta)}{2n}}\,.$

Lastly by Lemma 4.2 and combining the terms, we have the final bound in the
theorem

$\displaystyle\mathbb{E}\left[\ell_{h_{T}}\left(X_{T},Y_{T}\right)\mid
Z_{1}^{T-1}\right]$ $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[\ell_{h_{0}}\left(X_{T},Y_{T}\right)\mid
Z_{1}^{T-1}\right]+\frac{3}{T}+\frac{3M}{T}\sqrt{8\log\frac{1}{\delta}}+\frac{1}{T}\sqrt{\frac{\text{VCdim}(\mathcal{H})+\log(2/\delta)}{2n}}$
$\displaystyle+O\left(\frac{1}{\sqrt{nT}}\right)+18M\sqrt{4\pi\log
T}\mathfrak{R}_{T-1}^{seq}(\mathcal{F})+3T\rho\Delta\,.$

∎

##  C More Experimental results

In this section, we present additional experimental results and compare our
algorithm with our baseline algorithms with shifting MNIST.

##### Shifting MNIST

The shifting MNIST is a semi-synthetic dataset from MNIST dataset. For the
shifting MNIST, we shift the pixel to up, right, down, left by $1,3,5$ pixels.
Each domain contains images that have been shifted in at least one direction
and each consecutive domains contain imaged shifted in different directions.

Table 6: Results on shifting MNIST dataset with Gradual Adaptation on 5
domains, Direct Adaptation and No Adaptation.  Shifting MNIST
---
| Gradual Adaptation with 5 domains | Direct Adpatation | No Adaptation
| CNN | LSTM | CNN | LSTM | CNN
1 pixels | 86.19 $\pm$ 1.54 |  93.81 $\pm$ 0.35 | 76.72 $\pm$ 0.70 | 89.13 $\pm$ 1.10 | 87.36 $\pm$ 1.43
3 pixels | 73.61 $\pm$ 2.53 |  79.11 $\pm$ 0.95 | 60.12 $\pm$ 1.07 | 74.42 $\pm$ 1.89 | 70.63 $\pm$ 2.56
5 pixels | 62.80 $\pm$ 1.81 |  71.31 $\pm$ 2.55 | 46.83 $\pm$ 0.56 | 64.25 $\pm$ 2.57 | 44.41 $\pm$ 2.68
Table 7: Results on shifting MNIST dataset with Gradual Adaptation on 5
domains and Multiple Source Domain Adaptation method (MDA) (Zhao et al., 2018)
Shifting MNIST
---
|  | Gradual Adaptation
---
with 5 domains
MDA
| CNN | LSTM | Maxmin | Dynamic |  | Dynamic
---
with last 2 domain
1 pixel | 86.19 $\pm$ 1.54 | 93.81 $\pm$ 0.35 | 96.44 $\pm$ 0.72 |  97.85 $\pm$ 0.25 | 95.43 $\pm$ 0.82
3 pixels | 73.61 $\pm$ 2.53 | 79.11 $\pm$ 0.95 |  93.79 $\pm$ 0.34 | 93.14 $\pm$ 4.45 | 78.21 $\pm$ 0.69
5 pixels | 62.80 $\pm$ 1.81 | 71.31 $\pm$ 2.55 | 90.49 $\pm$ 0.72 |  93.49 $\pm$ 0.55 | 59.92 $\pm$ 0.92

We observe that when the shift in the domain is subtle ($1$ pixel), directly
performing empirical risk minimization (No Adaptation) can even outperform the
Gradual Adaptation with CNN model architecture. This showcases the
insufficiency of the one-step loss. However, we note that with a temporal
summarization, the one-step loss still overtakes the No Adaptation and Direct
Adaptation method. This is reflected through Gradual Adaptation with LSTM
performs the best when compared to No Adaptation and Direct Adaptation method
in all cases.

On the shifting MNIST, results show that simultaneous access to all data
domains is crucial, as MDA methods are more successful in all cases. This is
in contrast with the Rotating MNIST dataset, for which we showed in an earlier
section that gradual domain adaptation can be better than multiple source
domain adaptation while relaxing on the requirement of simultaneous access to
the training domains. However, we note that Gradual Adaptation still performs
better than the MDA method when it is restricted to accessing the last two
domains on $3$ and $5$ pixels shift. This shows potential of gradual domain
adaptation when only sequential access to data domains is available.

##### Experiment details

We conducted the experiments on 2 GeForce RTX 3090, each with 24265 MB memory
and with CUDA Version of 11.4. Each set of experiments is repeated with 5
different random seeds to ensure reproducible results. We report experimental
details (i.e. hyperparameters) here.

We penalize the gradient using the gradient penalty method originally designed
for stable generative model training (Gulrajani et al., 2017). We denote the
coefficient of penalty as GP factor. To stabilize the primal-dual training, we
perform gradient descent on the critic side for multiple steps before
descending on the classifier. We denote the number of times we descent the
critic side per descent on the classifier side as $k$-critic. Algorithms are
trained til their loss converges.

For the MNIST (rotating and shifting) dataset and Portrait dataset, we’ve used
the following configurations

  * •

Learning rates: $1e-3$ (classifier and feature extractor), $5e-4$ (critic).

  * •

Batch size: 64

  * •

GP factor: 5

  * •

$k$-critic: 5

  * •

Temporal model: 2 layer GRU with hidden size of 64.

For the FMOW dataset, the following configurations are used. We further
normalize the data before feed into the LSTM layer for better performance.

  * •

Learning rates: $1e-3$ (classifier and feature extractor), $1e-5$ (critic).

  * •

Gradient clipping: 3

  * •

Batch size: 216

  * •

GP factor: 1

  * •

$k$-critic: 5

  * •

Temporal model: 1 layer LSTM with hidden size of 2048.


# Values of $p$-adic hypergeometric functions, and $p$-adic analogue of
Kummer’s linear identity

Neelam Saikia  School of Basic Sciences, Discipline of Mathematics, Indian
Institute of Technology Bhubaneswar, Argul-Jatni Rd, Kansapada, Odisha 752050,
India<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Let $p$ be an odd prime and $\mathbb{F}_{p}$ be the finite field with $p$
elements. This paper focuses on the study of values of a generic family of
hypergeometric functions in the $p$-adic setting which we denote by
${{}_{3n-1}G_{3n-1}}(p,t),$ where $n\geq 1$ and $t\in\mathbb{F}_{p}$. These
values are expressed in terms of numbers of zeros of certain polynomials over
$\mathbb{F}_{p}$. These results lead to certain $p$-adic analogues of
classical hypergeometric identities. Namely, we obtain $p$-adic analogues of
particular cases of a Gauss’ theorem and a Kummer’s theorem. Moreover, we
examine the zeros of these functions. For instance, if $n$ is odd then we
obtain zeros of ${{}_{3n-1}G_{3n-1}}(p,t)=0$ under certain condition on $t$.
In contrast we show that if $n$ is even then the function
${{}_{3n-1}G_{3n-1}}(p,t)$ has no non-trivial zeros for any prime $p$.

###### Key words and phrases:

Character sum; Gauss sums; Jacobi sums; $p$-adic Gamma functions

###### 2010 Mathematics Subject Classification:

Primary: 33E50, 33C20, 33C99, 11S80, 11T24.

##  1\. Introduction and statement of results

Let $a$ be a complex number and $k$ be a nonnegative integer. Then the rising
factorial $(a)_{k}$ is defined as $(a)_{0}:=1$ for $k=0$ and
$(a)_{k}:=a(a+1)(a+2)\cdots(a+k-1)$ for $k>0.$ Then for
$a_{i},b_{i},\lambda\in\mathbb{C}$ with $b_{i}\neq 0,-1,-2\ldots$, the
${{}_{r+1}F_{r}}$ classical hypergeometric series is defined by

$\displaystyle{{}_{r+1}}F_{r}\left(\begin{array}[]{cccc}a_{1},&a_{2},&\ldots,&a_{r+1}\\\
&b_{1},&\ldots,&b_{r}\end{array}\mid\lambda\right):=\sum_{k=0}^{\infty}\frac{(a_{1})_{k}\cdots(a_{r+1})_{k}}{(b_{1})_{k}\cdots(b_{r})_{k}}\cdot\frac{\lambda^{k}}{k!}.$

Let $\widehat{\mathbb{F}_{p}^{\times}}$ be the group of all multiplicative
characters of $\mathbb{F}_{p}^{\times}$. Let $\overline{\chi}$ denote the
inverse of a multiplicative character $\chi$. We extend the domain of each
$\chi\in\widehat{\mathbb{F}_{p}^{\times}}$ to $\mathbb{F}_{p}$ by simply
setting $\chi(0):=0$ including the trivial character $\varepsilon.$ Let
$\varphi$ be the quadratic character of $\mathbb{F}_{p}$. For multiplicative
characters $\chi$ and $\psi$ of $\mathbb{F}_{p}$ the Jacobi sum is defined by

$\displaystyle J(\chi,\psi):=\sum_{y\in\mathbb{F}_{p}}\chi(y)\psi(1-y),$

and the normalized Jacobi sum known as binomial is defined by

${\chi\choose\psi}:=\frac{\psi(-1)}{p}J(\chi,\overline{\psi}).$

Let $\mathbb{Z}_{p}$ denote the ring of $p$-adic integers and $\mathbb{Q}_{p}$
denote the field of $p$-adic numbers. McCarthy [17] developed a study of
functions defined in terms of $p$-adic gamma functions with parameters in
$\mathbb{Q}\cap\mathbb{Z}_{p}$ extending Greene’s [10] hypergeometric
functions over finite fields. Let $\Gamma_{p}(\cdot)$ denote the Morita’s
$p$-adic gamma function. Let $\omega$ denote the Teichmüller character of
$\mathbb{F}_{p},$ satisfying $\omega(a)\equiv a\pmod{p},$ and
$\overline{\omega}$ denote the character inverse of $\omega$. For
$x\in\mathbb{Q}$ let $\lfloor x\rfloor$ denote the greatest integer less than
or equal to $x$ and $\langle x\rangle$ denote the fractional part of $x$,
satisfying $0\leq\langle x\rangle<1$. We now recall the McCarthy’s
hypergeometric function in the $p$-adic setting.

######  Definition 1.1.

[17, Definition 5.1] Let $p$ be an odd prime and $t\in\mathbb{F}_{p}$. For
positive integer $n$ and $1\leq k\leq n$, let $a_{k}$, $b_{k}$
$\in\mathbb{Q}\cap\mathbb{Z}_{p}$. Then

(1.3)
$\displaystyle{{}_{n}\mathbb{G}_{n}}\left[\begin{array}[]{cccc}a_{1},&a_{2},&\ldots,&a_{n}\\\
b_{1},&b_{2},&\ldots,&b_{n}\end{array}\mid
t\right]_{p}:=\frac{-1}{p-1}\sum_{a=0}^{p-2}(-1)^{an}~{}~{}\overline{\omega}^{a}(t)$
$\displaystyle\times\prod\limits_{k=1}^{n}(-p)^{-\lfloor\langle
a_{k}\rangle-\frac{a}{p-1}\rfloor-\lfloor\langle-
b_{k}\rangle+\frac{a}{p-1}\rfloor}\frac{\Gamma_{p}(\langle
a_{k}-\frac{a}{p-1}\rangle)}{\Gamma_{p}(\langle
a_{k}\rangle)}\frac{\Gamma_{p}(\langle-
b_{k}+\frac{a}{p-1}\rangle)}{\Gamma_{p}(\langle-b_{k}\rangle)}.$

This function is called $p$-adic hypergeometric function. Evaluation of
particular values of special functions is one of the oldest problem in
mathematics. For example, the follwing classical result of Gauss [9] expresses
the ${}_{2}F_{1}$ classical hypergeometric series in terms of quotients of
classical gamma function. If $R(c-a-b)>0$ then

(1.6) $\displaystyle{{}_{2}F_{1}}\left(\begin{array}[]{cc}a,&b\\\
&c\end{array}\mid
1\right)=\frac{\Gamma(c)\Gamma(c-a-b)}{\Gamma(c-a)\Gamma(c-b)}.$

The Gauss’ theorem has been treated by N. Koblitz [14] and J. Diamond [6] for
classical hypergeometric series with $p$-adic variables, and also for ratios
of such hypergeometric series. Ratios of hypergeometric series with $p$-adic
variables were first considered by B. Dwork while studying the zeta function
of a hypersurface. Similar to Gauss’ theorem Kummer [15], Whipple [16, p. 54],
Saalchütz [19, p. 49], Dixon [19, p. 51], and Watson [19, p. 54] also
evaluated special values of classical hypergeometric functions. This paper
focuses to study the values of the McCarthy’s hypergeometric functions in the
$p$-adic setting. For positive integer $n\geq 1$ consider the following
hypergeometric function in the $p$-adic setting

${{}_{3n-1}G_{3n-1}}(p,t):={{}_{3n-1}\mathbb{G}_{3n-1}}\left[\begin{array}[]{ccccc}\frac{1}{3n},&\frac{2}{3n},&\frac{3}{3n},&\ldots,&\frac{3n-1}{3n}\vspace{1mm}\\\
0,&\frac{1}{2},&\frac{1}{3n-2},&\ldots,&\frac{3n-3}{3n-2}\end{array}\mid
t\right]_{p}.$

The next theorem presents the values of the function
${{}_{3n-1}G_{3n-1}}(p,t)$ in terms of the number of zeros of certain
polynomial over $\mathbb{F}_{p}$. Let
$\delta:\widehat{\mathbb{F}_{p}^{\times}}\rightarrow\\{0,1\\}$ be defined by

$\delta(\chi):=\left\\{\begin{array}[]{ll}1,&\hbox{if $\chi=\varepsilon$;}\\\
0,&\hbox{if $\chi\neq\varepsilon$.}\end{array}\right.$

######  Theorem 1.2.

Let $n\geq 1$ be a positive integer and $p\nmid 3n(3n-2)$ be an odd prime. For
$t\in\mathbb{F}_{p}^{\times}$ let
$\alpha=\frac{(-1)^{n}(3n-2)^{3n-2}}{(3n)^{3n}t}$ and
$f_{t}(y):=y^{3n}-2y^{3n-1}+y^{3n-2}-(-1)^{n}4\alpha$ be a polynomial over
$\mathbb{F}_{p}$. Then we have that

(1.11)
$\displaystyle{{}_{3n-1}G_{3n-1}}(p,t)=\left\\{\begin{array}[]{ll}-1+\frac{1-p}{p}\varphi(\alpha)\delta(\varphi^{n}),&\hbox{if
$f_{t}(y)$ has no root }\\\ &\hbox{in $\mathbb{F}_{p}$;}\\\
r-1+\frac{1-p}{p}\varphi(\alpha)\delta(\varphi^{n}),&\hbox{if $f_{t}(y)$ has
$r$ distinct}\\\ &\hbox{ roots in $\mathbb{F}_{p}$.}\end{array}\right.$

This theorem has some consequences. For example, if we put $n=1$ in Theorem
1.2 then we have
${{}_{2}G_{2}}(p,t)={{}_{2}\mathbb{G}_{2}}\left[\begin{array}[]{cc}\frac{1}{3},&\frac{2}{3}\vspace{1mm}\\\
0,&\frac{1}{2}\end{array}\mid t\right]_{p}$ and obtain the following
corollary.

Let $S(t):=\left\\{y\in\mathbb{F}_{p}:27y^{3}-27y^{2}+\frac{4}{t}\equiv
0\pmod{p}\right\\}$. For brevity we use the notation $\\#S(t)$ to denote the
number of elements of $S(t)$.

######  Corollary 1.3.

Let $p>3$ be a prime. Then we have

(1.12) $\displaystyle{{}_{2}G_{2}}(p,1)=1,$

and if $1\neq t\in\mathbb{F}_{p}^{\times}$ then
${{}_{2}G_{2}}(p,t)=\\#S(t)-1.$

######  Remark.

If we put $a=\frac{1}{3},$ $b=\frac{2}{3}$ and $c=1+\frac{1}{2}$ in (1.6) then
we have

(1.15)
$\displaystyle{{}_{2}F}_{1}\left(\begin{array}[]{cc}\frac{1}{3},&\frac{2}{3}\\\
&1+\frac{1}{2}\end{array}\mid
1\right)=\frac{\Gamma(1+\frac{1}{2})\Gamma(\frac{1}{2})}{\Gamma(1+\frac{1}{6})\Gamma(\frac{5}{6})}=\frac{3}{2}.$

(1.12) can be described as $p$-adic analogue of (1.15). This gives a
motivation to represent Corollary 1.3 as some kind of extension of (1.15) in
the $p$-adic setting.

It is of interest to investigate the zeros of hypergeometric functions. The
zero location of special classes of classical hypergeometric functions can be
found in [2, 3]. By Theorem 1.2 we obtain

######  Corollary 1.4.

If $p\nmid 3n(3n-2)$ is an odd prime, then for $t\in\mathbb{F}_{p}^{\times}$
the following are true.

  1. (1)

If $n$ is even then ${{}_{3n-1}G_{3n-1}}(p,t)\neq 0$.

  2. (2)

If $n$ is odd then ${{}_{3n-1}G_{3n-1}}(p,t)=0$ if and only if
$y^{3n}-2y^{3n-1}+y^{3n-2}+\frac{4(3n-2)^{3n-2}}{(3n)^{3n}t}\equiv 0\pmod{p}$
has exactly one incongruent solution modulo $p$.

Let
${{}_{2}\widetilde{G}_{2}}(p,t)={{}_{2}\mathbb{G}_{2}}\left[\begin{array}[]{cc}\frac{1}{6},&\frac{5}{6}\vspace{1mm}\\\
0,&\frac{1}{2}\end{array}\mid t\right]_{p}$. We now examine the values of the
function ${{}_{2}\widetilde{G}_{2}}(p,t)$.

######  Theorem 1.5.

Let $p>3$ be a prime and $t\in\mathbb{F}_{p}^{\times}.$ Then we have

(1.16) $\displaystyle{{}_{2}\widetilde{G}_{2}}(p,1)=\varphi(3).$

Moreover, if $t\neq 1$ then
${{}_{2}\widetilde{G}_{2}}(p,t)=\varphi(3t)\times(\\#S(t)-1).$

This theorem provides the possible range of the function
${{}_{2}\widetilde{G}_{2}}(p,t).$

######  Corollary 1.6.

Let $p>3$ be a prime and $t\in\mathbb{F}_{p}$. Then the possible values of the
function ${{}_{2}\widetilde{G}_{2}}(p,t)$ can take are $0$, $\pm 1$, and $\pm
2$.

Another important topic to be discussed is that of transformation identities.
Classical hypergeometric series satisfy many transformation identities. Kummer
[4, 21] gave a list of 24 solutions to the differential equation for the
hypergeometric series

$x(l-x)y^{\prime\prime}+(c-(a+b+l)x)y^{\prime}-aby=0.$

Any three such solutions are linearly dependent. The resulting linear
combinations yield transformations for classical hypergeometric series. For
example, Kummer [1, p. 4 eq. (1)] obtained the following linear
transformation.

(1.21) $\displaystyle{{}_{2}F_{1}}\left(\begin{array}[]{cc}a,&b\\\
&c\end{array}\mid
z\right)=\frac{\Gamma(c)\Gamma(c-a-b)}{\Gamma(c-a)\Gamma(c-b)}\cdot{{}_{2}F_{1}}\left(\begin{array}[]{cc}a,&b\\\
&1+a+b-c\end{array}\mid 1-z\right)$ (1.24)
$\displaystyle+\frac{\Gamma(c)\Gamma(a+b-c)}{\Gamma(a)\Gamma(b)}(1-z)^{c-a-b}\cdot{{}_{2}F_{1}}\left(\begin{array}[]{cc}c-a,&c-b\\\
&1+c-a-b\end{array}\mid 1-z\right).$

Euler [19, p. 10], Whipple [20], Dixon [7] also studied transformation
properties of classical hypergeometric series. It is often beneficial to study
such results in different settings. For example, Fuselier-McCarthy [8]
established certain transformation identities for hypergeometric series in the
$p$-adic setting. Interestingly, they proved a transformation of $p$-adic
hypergeometric series analogous to a particular case of Whipple’s
transformation result for ${{}_{3}F_{2}}$-classical hypergeometric series and
using such transformations they proved one supercongruence conjecture of
Rodriguez-Villegas between a truncated ${{}_{4}F_{3}}$-classical
hypergeometric series and the Fourier coefficients of a certain weight four
modular form. These consequences attract our interest to further study other
analogues of classical hypergeometric transformations in the $p$-adic setting.
In this paper, we aim to establish a particular case of Kummer’s identity
(1.21). It is important to recall that Kummer’s methods of deriving solutions
of the differential equation involved changes of variables that do not affect
the form of the differential equation. In our case we do not have any
differential equation so we must develop different techniques to settle
analogous transformations for the hypergeometric series in the $p$-adic
setting. We obtain a $p$-adic analogue of Kummer’s identity (1.21) for the
functions ${{}_{2}G_{2}}(p,t)$ and ${{}_{2}\widetilde{G}_{2}}(p,t)$ in the
next theorem as an application of Corollary 1.3 and Theorem 1.5.

######  Theorem 1.7.

Let $p>3$ be a prime and $1\neq t\in\mathbb{F}_{p}^{\times}$. For fixed $t$
let $f_{t}(y)=27y^{3}-27y^{2}+\frac{4}{t}$, and
$g_{t}(y)=27y^{3}-27y^{2}+\frac{4}{1-t}$ be two polynomials over
$\mathbb{F}_{p}$. If $f_{t}(y)\equiv 0\pmod{p}$ has $r_{1}$ incongruent
solutions and $g_{t}(y)\equiv 0\pmod{p}$ has $r_{2}$ incongruent solutions
modulo $p$ then

$\displaystyle{{}_{2}G_{2}}(p,t)$
$\displaystyle={{}_{2}G_{2}}(p,1-t)+{{}_{2}\widetilde{G}_{2}}(p,1-t)+(r_{1}-r_{2})+(1-r_{2})\varphi(3(1-t)).$

The rest part of the paper is organized as follows. Section 2 contains some
basic definitions including Gauss sum, and $p$-adic gamma function. We also
present some preliminary results along with some important theorems including
Hasse-Devanport Theorem and Gross-Koblitz formula in Section 2. In Section 3
we prove two propositions which play important roles in proving the main
results. We give the proofs of the results in Section 3.

##  2\. Notation and Preliminary results

###  2.1. Multiplicative characters and Gauss sums:

The following result is the orthogonality relation of multiplicative
characters.

######  Lemma 2.1.

[12, Chapter 8] Let $p$ be an odd prime. Then we have

(2.3)
$\displaystyle\sum_{\chi\in\widehat{\mathbb{F}_{p}^{\times}}}\chi(x)=\left\\{\begin{array}[]{ll}p-1,&\hbox{if
$x=1$;}\\\ 0,&\hbox{if $x\neq 1$.}\end{array}\right.$

Let $\zeta_{p}$ denote a fixed primitive $p$-th root of unity. Then for
multiplicative character $\chi$ of $\mathbb{F}_{p}$ the Gauss sum is defined
by

$\displaystyle
g(\chi):=\sum\limits_{x\in\mathbb{F}_{p}}\chi(x)~{}\zeta_{p}^{x}.$

It is easy to verify that $g(\varepsilon)=-1$. The following product of Gauss
sums is very useful in the proofs of our results.

######  Lemma 2.2.

[10, eq. 1.12] Let $\chi\in\widehat{\mathbb{F}_{p}^{\times}}.$ Then

(2.4) $\displaystyle g(\chi)g(\overline{\chi})=p\chi(-1)-(p-1)\delta(\chi).$

The Hasse-Davenport formula is also very important product formula of Gauss
sums.

######  Theorem 2.3.

[5, Hasse-Davenport relation, Theorem 11.3.5] Let $\chi$ be a multiplicative
character of order $m$ of $\mathbb{F}_{p}$ for some positive integer $m.$ For
a multiplicative character $\psi$ of $\mathbb{F}_{p}$ we have

(2.5)
$\displaystyle\prod_{i=0}^{m-1}g(\psi\chi^{i})=g(\psi^{m})\psi^{-m}(m)\prod_{i=1}^{m-1}g(\chi^{i}).$

The next lemma gives a relation between Gauss and Jacobi sums.

######  Lemma 2.4.

[10, eq. 1.14] Let $\chi_{1},\chi_{2}\in\widehat{\mathbb{F}_{p}^{\times}}.$
Then

(2.6) $\displaystyle
J(\chi_{1},\chi_{2})=\frac{g(\chi_{1})g(\chi_{2})}{g(\chi_{1}\chi_{2})}+(p-1)\chi_{2}(-1)\delta(\chi_{1}\chi_{2}).$

Let $\chi,\psi$ be multiplicative characters of $\mathbb{F}_{p}.$ Then from
[10, eq. 2.12, eq. 2.7] we have

(2.7)
$\displaystyle{\chi\choose\varepsilon}={\chi\choose\chi}=-\frac{1}{p}+\frac{p-1}{p}\delta(\chi),$
(2.8)
$\displaystyle{\chi\choose\psi}={\psi\overline{\chi}\choose\psi}\psi(-1).$

###  2.2. $p$-adic preliminaries:

Let $\overline{\mathbb{Q}_{p}}$ denote the algebraic closure of
$\mathbb{Q}_{p}$ and $\mathbb{C}_{p}$ denote the completion of
$\overline{\mathbb{Q}_{p}}$. We now recall the $p$-adic gamma function, for
further details see [13]. For a positive integer $n$ the $p$-adic gamma
function $\Gamma_{p}(n)$ is defined as

$\displaystyle\Gamma_{p}(n):=(-1)^{n}\prod\limits_{0<j<n,p\nmid j}j.$

It can be extended to all $x\in\mathbb{Z}_{p}$ by setting $\Gamma_{p}(0):=1$
and for $x\neq 0$

$\displaystyle\Gamma_{p}(x):=\lim_{x_{n}\rightarrow x}\Gamma_{p}(x_{n}).$

An important product formula of $p$-adic gamma functions is given below. If
$m\in\mathbb{Z}^{+},$ $p\nmid m$ and $x=\frac{r}{p-1}$ with $0\leq r\leq p-1$
then

(2.9)
$\displaystyle\prod_{h=0}^{m-1}\Gamma_{p}\left(\frac{x+h}{m}\right)=\omega(m^{(1-x)(1-p)})~{}\Gamma_{p}(x)\prod_{h=1}^{m-1}\Gamma_{p}\left(\frac{h}{m}\right).$

From [17] we also state that if $t\in\mathbb{Z}^{+}$ and $p\nmid t$ then for
$0\leq j\leq p-2$ we have

(2.10)
$\displaystyle\omega(t^{tj})\Gamma_{p}\left(\left\langle\frac{tj}{p-1}\right\rangle\right)\prod_{h=1}^{t-1}\Gamma_{p}\left(\frac{h}{t}\right)=\prod_{h=0}^{t-1}\Gamma_{p}\left(\left\langle\frac{h}{t}+\frac{j}{p-1}\right\rangle\right),$

and

(2.11)
$\displaystyle\omega(t^{-tj})\Gamma_{p}\left(\left\langle\frac{-tj}{p-1}\right\rangle\right)\prod_{h=1}^{t-1}\Gamma_{p}\left(\frac{h}{t}\right)=\prod_{h=1}^{t}\Gamma_{p}\left(\left\langle\frac{h}{t}-\frac{j}{p-1}\right\rangle\right).$

Let $\pi\in\mathbb{C}_{p}$ be the fixed root of the polynomial $x^{p-1}+p$,
which satisfies the congruence condition
$\pi\equiv\zeta_{p}-1\pmod{(\zeta_{p}-1)^{2}}$. Then the following result is
known as the Gross-Koblitz formula.

######  Theorem 2.5.

[11, Gross-Koblitz formula] For $j\in\mathbb{Z}$,

$\displaystyle
g(\overline{\omega}^{j})=-\pi^{(p-1)\langle\frac{j}{p-1}\rangle}\Gamma_{p}\left(\left\langle\frac{j}{p-1}\right\rangle\right).$

We now state a lemma that is obtained by applying Gross-Koblitz formula.

######  Lemma 2.6.

Let $1\leq j\leq p-2.$ Then

(2.12) $\displaystyle\Gamma_{p}\left(\left\langle
1-\frac{j}{p-1}\right\rangle\right)\Gamma_{p}\left(\left\langle\frac{j}{p-1}\right\rangle\right)=-\omega^{j}(-1).$

###### Proof.

We first apply Gross-Koblitz formula (Theorem 2.5) on the left hand side of
(2.12) and then apply (2.4) to obtain the result. ∎

##  3\. Proof of the theorems

We begin this section with two propositions. These proposition are used to
prove Theorem 1.2, and Theorem 1.5.

######  Proposition 3.1.

Let $n\geq 1$ be a positive integer and $p\nmid 3n(3n-2)$ be an odd prime. For
$x\in\mathbb{F}_{p}^{\times}$ let
$\alpha=\frac{(-1)^{n}(3n-2)^{3n-2}}{(3n)^{3n}x}$, and consider
$f_{x}(y)=y^{3n}-2y^{3n-1}+y^{3n-2}-(-1)^{n}4\alpha\in\mathbb{F}_{p}[y].$
If
$C(n,x)=\displaystyle\sum_{\chi\in\widehat{\mathbb{F}_{p}^{\times}}}g(\chi^{3n})g(\varphi\overline{\chi})g(\overline{\chi})g(\overline{\chi}^{3n-2})~{}\chi(\alpha)$
then we have

$\displaystyle
C(n,x)+(p-1)^{2}g(\varphi)(1+\varphi(\alpha)\delta(\varphi^{n}))$
$\displaystyle=\left\\{\begin{array}[]{ll}0,&\hbox{if $f_{x}(y)\equiv
0\pmod{p}$ has no solution modulo $p$;}\\\ rp(p-1)g(\varphi),&\hbox{if
$f_{x}(y)\equiv 0\pmod{p}$ has $r$ incongruent }\\\ {}{}&\hbox{\hskip
62.59596pt solutions modulo $p$.}\end{array}\right.$

###### Proof.

Multiplying both the numerator and denominator by $g(\chi^{2})$ we can write

(3.1) $\displaystyle
C(n,x)=\sum_{\chi\in\widehat{\mathbb{F}_{p}^{\times}}}\frac{g(\chi^{3n})g(\overline{\chi}^{3n-2})}{g(\chi^{2})}~{}g(\chi^{2})g(\varphi\overline{\chi})g(\overline{\chi})~{}\chi(\alpha).$

Applying Hasse-Davenport (2.5) with $m=2$ we have

(3.2) $\displaystyle
g(\varphi\overline{\chi})g(\overline{\chi})=g(\varphi)\overline{\chi}(2^{-2})g(\overline{\chi}^{2}).$

Substituting (3.2) into (3.1) and then applying (2.4), (2.6) we have

(3.3) $\displaystyle\frac{C(n,x)}{g(\varphi)}$
$\displaystyle=p\sum_{\chi\in\widehat{\mathbb{F}_{p}^{\times}}}J(\chi^{3n},\overline{\chi}^{3n-2})\chi(4\alpha)-(p-1)^{2}(1+\varphi(\alpha)\delta(\varphi^{n})).$

(2.8) yields
$J(\chi^{3n},\overline{\chi}^{3n-2})=\chi^{n}(-1)J(\overline{\chi}^{2},\overline{\chi}^{3n-2})$.
Using this, and replacing $\chi$ by $\overline{\chi}$ in (3.3) we obtain

$\displaystyle C(n,x)$
$\displaystyle=pg(\varphi)\sum_{\chi\in\widehat{\mathbb{F}_{p}^{\times}},~{}y\in\mathbb{F}_{p}}\chi\left(\frac{y^{3n-2}(1-2y+y^{2})}{(-1)^{n}4\alpha}\right)$
$\displaystyle-(p-1)^{2}g(\varphi)(1+\varphi(\alpha)\delta(\varphi^{n})).$

Orthogonality relation of multiplicative characters gives that the double sum
is non zero if and only if the congruence $f_{x}(y)\equiv 0\pmod{p}$ admits a
solution. Considering the number of incongruent solutions of $f_{x}(y)\equiv
0\pmod{p}$ we obtain the required identity. ∎

######  Proposition 3.2.

Let $n\geq 1$ be a positive integer and $p\nmid 3n(3n-2)$ be a prime. For
$x\in\mathbb{F}_{p}^{\times}$ let
$\alpha=\frac{(-1)^{n}(3n-2)^{3n-2}}{(3n)^{3n}x}$, and
Let
$C(n,x)=\displaystyle\sum_{\chi\in\widehat{\mathbb{F}_{p}^{\times}}}g(\chi^{3n})g(\varphi\overline{\chi})g(\overline{\chi})g(\overline{\chi}^{3n-2})~{}\chi(\alpha)$.
Then we have

$\displaystyle C(n,x)=(p-1)g(\varphi)(1+p\cdot{{}_{3n-1}G_{3n-1}}(p,x)).$

###### Proof.

Replacing $\chi$ by $\omega^{j}$ and then applying Gross-Koblitz formula we
obtain

(3.4) $\displaystyle C(n,x)$
$\displaystyle=\sum_{j=0}^{p-2}\omega^{j}(\alpha)\pi^{(p-1)\ell_{j}}~{}\Gamma_{p}\left(\left\langle\frac{-3nj}{p-1}\right\rangle\right)\Gamma_{p}\left(\frac{j}{p-1}\right)$
$\displaystyle\times\Gamma_{p}\left(\left\langle\frac{1}{2}+\frac{j}{p-1}\right\rangle\right)\Gamma_{p}\left(\left\langle\frac{(3n-2)j}{p-1}\right\rangle\right),$

where
$\ell_{j}=\frac{1}{2}-\left\lfloor\frac{-3nj}{p-1}\right\rfloor-\left\lfloor\frac{1}{2}+\frac{j}{p-1}\right\rfloor-\left\lfloor\frac{(3n-2)j}{p-1}\right\rfloor$.
Simplifying the sum by applying (2.11) (with $t=3n$), and (2.10) (with
$t=3n-2$) and then using (2.12) we bring down the sum to

$\displaystyle C(n,x)$
$\displaystyle=\pi^{\frac{(p-1)}{2}}\Gamma_{p}\left(\frac{1}{2}\right)-\sum_{j=1}^{p-2}\overline{\omega}^{j}((-1)^{n+1}x)\pi^{(p-1)\ell_{j}}~{}\Gamma_{p}\left(\left\langle\frac{1}{2}+\frac{j}{p-1}\right\rangle\right)$
$\displaystyle\times\prod_{h=1}^{3n-1}\frac{\Gamma_{p}\left(\left\langle\frac{h}{3n}-\frac{j}{p-1}\right\rangle\right)}{\Gamma_{p}(\frac{h}{3n})}\prod_{h=0}^{3(n-1)}\frac{\Gamma_{p}\left(\left\langle\frac{h}{3n-2}+\frac{j}{p-1}\right\rangle\right)}{\Gamma_{p}(\frac{h}{3n-2})}.$

For $1\leq j\leq p-2$ consider
$\left\lfloor\frac{-3nj}{p-1}\right\rfloor=-3n+s$ for some $s\in\mathbb{Z}$
with $0\leq s\leq 3n-1$ we obtain
$\left\lfloor\dfrac{-3nj}{p-1}\right\rfloor=-1+\displaystyle\sum_{h=1}^{3n-1}\left\lfloor\frac{h}{3n}-\frac{j}{p-1}\right\rfloor$.
Also, let $\left\lfloor\frac{(3n-2)j}{p-1}\right\rfloor=k$ for some
$k\in\mathbb{Z}$ with $0\leq k\leq 3n-3$. Then it is easy to verify that
$\left\lfloor\dfrac{(3n-2)j}{p-1}\right\rfloor=\displaystyle\sum_{h=1}^{3n-3}\left\lfloor\frac{h}{3n-2}+\frac{j}{p-1}\right\rfloor$.
Substituting these identities in the expression of $\ell_{j}$ and rearranging
the terms we have

(3.5) $\displaystyle C(n,x)$
$\displaystyle=(1-p)\pi^{\frac{(p-1)}{2}}\Gamma_{p}(1/2)(1+p\cdot{{}_{3n-1}G_{3n-1}}(p,x)).$

By Gross-Koblitz formula we have
$g(\varphi)=-\pi^{\frac{(p-1)}{2}}\Gamma_{p}(1/2)$. Putting this in (3.5) we
obtain the required identity. This completes the proof of the proposition. ∎

###### Proof of Theorem 1.2.

Let
$C(n,t)=\displaystyle\sum_{\chi\in\widehat{\mathbb{F}_{p}^{\times}}}g(\chi^{3n})g(\varphi\overline{\chi})g(\overline{\chi})g(\overline{\chi}^{3n-2})\chi(\alpha)$.
Now, applying Proposition 3.1, Proposition 3.2 and then comparing the terms we
obtain the result. This completes the proof of the theorem. ∎

###### Proof of Corollary 1.3.

If we put $n=1$ in Theorem 1.2 then we have ${{}_{2}G_{2}}(p,t)=r-1$, where
$0\leq r\leq 3$ is the number of incongruent solutions of
$27y^{3}-54y^{2}+27y-\frac{4}{t}\equiv 0\pmod{p}$ modulo $p$. Replacing $y$ by
$(1-y)$ we obtain $r=\\#S(t)$. In particular, if we put $t=1$ then
$\frac{1}{3}$, and $\frac{2}{3}$ are the only incongruent solutions of
$27y^{3}-27y^{2}+4\equiv 0\pmod{p}$ modulo $p$. Hence, ${{}_{2}G_{2}}(p,1)=1$.
∎

###### Proof of Corollary 1.4.

Let $\alpha=\frac{(-1)^{n}(3n-2)^{3n-2}}{(3n)^{3n}t}$. Let $r$ be the number
of incongruent solutions of
$y^{3n}-2y^{3n-1}+y^{3n-2}-(-1)^{n}4\alpha\equiv\pmod{p}$ modulo $p$. If $n$
is even then by Theorem 1.2 we have

$\displaystyle{{}_{3n-1}G_{3n-1}}(p,t)=r-1+\frac{1-p}{p}\varphi(t)\neq 0.$

Again, if $n$ is odd then by Theorem 1.2 we have

(3.6) $\displaystyle{{}_{3n-1}G_{3n-1}}(p,t)=r-1.$

(3.6) will be zero only if $r=1$. ∎

###### Proof of Theorem 1.5.

Let
$B_{t}=\displaystyle\sum_{\chi\in\widehat{\mathbb{F}_{p}^{\times}}}g(\chi^{3})g(\varphi\overline{\chi})g(\overline{\chi})^{2}~{}\overline{\chi}\left(-27t\right)$.
From Proposition 3.2 we can write $B_{t}=C(1,t)$. Then (3.5) yields

$\displaystyle B_{t}$
$\displaystyle=(1-p)\pi^{\frac{(p-1)}{2}}\Gamma_{p}(1/2)\left(1+p\cdot~{}{{}_{2}G_{2}}(p,t)\right)$
(3.7)
$\displaystyle=p\pi^{\frac{(p-1)}{2}}\sum_{j=0}^{p-2}(-p)^{(-\lfloor\frac{1}{3}-\frac{j}{p-1}\rfloor-\lfloor\frac{2}{3}-\frac{j}{p-1}\rfloor-\lfloor\frac{1}{2}+\frac{j}{p-1}\rfloor-\lfloor\frac{j}{p-1}\rfloor)}$
$\displaystyle\times\overline{\omega}^{j}(t)\frac{\Gamma_{p}\left(\left\langle\frac{1}{3}-\frac{j}{p-1}\right\rangle\right)\Gamma_{p}\left(\left\langle\frac{2}{3}-\frac{j}{p-1}\right\rangle\right)}{\Gamma_{p}(\frac{1}{3})\Gamma_{p}(\frac{2}{3})}\Gamma_{p}\left(\frac{j}{p-1}\right)$
$\displaystyle\times\Gamma_{p}\left(\left\langle\frac{1}{2}+\frac{j}{p-1}\right\rangle\right)+(1-p)\pi^{\frac{(p-1)}{2}}\Gamma_{p}\left(\frac{1}{2}\right).$

Now, replacing $j$ by $j-\frac{p-1}{2}$ in (3) we obtain

$\displaystyle B_{t}$
$\displaystyle=\varphi(t)p\pi^{\frac{(p-1)}{2}}\sum_{j=0}^{p-2}\overline{\omega}^{j}(t)(-p)^{(-\lfloor\frac{1}{6}-\frac{j}{p-1}\rfloor-\lfloor\frac{5}{6}-\frac{j}{p-1}\rfloor-\lfloor\frac{1}{2}+\frac{j}{p-1}\rfloor-\lfloor\frac{j}{p-1}\rfloor)}$
$\displaystyle\times\frac{\Gamma_{p}\left(\left\langle\frac{1}{6}-\frac{j}{p-1}\right\rangle\right)\Gamma_{p}\left(\left\langle\frac{5}{6}-\frac{j}{p-1}\right\rangle\right)}{\Gamma_{p}(\frac{1}{3})\Gamma_{p}(\frac{2}{3})}\Gamma_{p}\left(\frac{j}{p-1}\right)\Gamma_{p}\left(\left\langle\frac{1}{2}+\frac{j}{p-1}\right\rangle\right)$
$\displaystyle+(1-p)\pi^{\frac{(p-1)}{2}}\Gamma_{p}(1/2)$
$\displaystyle=(1-p)\pi^{\frac{(p-1)}{2}}\Gamma_{p}(1/2)\left(1+p\varphi(t)\frac{\Gamma_{p}(\frac{1}{6})\Gamma_{p}(\frac{5}{6})}{\Gamma_{p}(\frac{1}{3})\Gamma_{p}(\frac{2}{3})}\cdot{{}_{2}\widetilde{G}_{2}}(p,t)\right).$

(2.10) gives
$\frac{\Gamma_{p}(\frac{1}{6})\Gamma_{p}(\frac{5}{6})}{\Gamma_{p}(\frac{1}{3})\Gamma_{p}(\frac{2}{3})}=\varphi(3)$
and Gross-Koblitz gives $g(\varphi)=-\pi^{\frac{p-1}{2}}\Gamma_{p}(1/2)$.
Substituting these two in the above sum we have

(3.8) $\displaystyle B_{t}$
$\displaystyle=(p-1)g(\varphi)\left(1+p\varphi(3t)~{}{{}_{2}\widetilde{G}_{2}}(p,t)\right).$

Also, by Proposition 3.2 we have

(3.9) $\displaystyle B_{t}$
$\displaystyle=(p-1)g(\varphi)\left(1+p~{}{{}_{2}{G}_{2}}(p,t)\right).$

Combining (3.8), and (3.9) we can write
${{}_{2}{G}_{2}}(p,t)=\varphi(3t)\cdot{{}_{2}\widetilde{G}_{2}}(p,t)$. Now, by
Corollary 1.3 we obtain the required identity. This completes the proof. ∎

###### Proof of Theorem 1.7.

By Corollary 1.3 and Theorem 1.5 we have

(3.10) $\displaystyle{{}_{2}G_{2}}(p,t)=r_{1}-1$ (3.11)
$\displaystyle{{}_{2}G_{2}}(p,1-t)=r_{2}-1,$ (3.12)
$\displaystyle{{}_{2}\widetilde{G}_{2}}(p,1-t)=(r_{2}-1)\varphi(3(1-t)).$

Combining (3.10), (3.11), and (3.12) we readily obtain the transformation.
This completes the proof of the theorem. ∎

## References

  * [1] W. Bailey, Generalized hypergeometric series, Cambridge University Press, Cambridge, 1935.
  * [2] D. Dominici, K. Driver and K. Jordaan, Polynomial solutions of differential-difference equations, J. Approx. Theory, 163 (2011), 41–48.
  * [3] K. Driver and P. Duren, Zeros of the hypergeometric polynomials $F(-n,b;2b;z)$, Indag. Math. 11(1), (2000), 43–51.
  * [4] A. Erdélyi, Higher transcendental junctions, Vol. I, McGraw· Hill, New York, 1935.
  * [5] B. Berndt, R. Evans, and K. Williams, Gauss and Jacobi Sums, Canadian Mathematical Society Series of Monographs and Advanced Texts, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, (1998).
  * [6] J. Diamond, Hypergeometric series with a $p$-adic variable, Pacific J. Math., 94 (1981), 265–276.
  * [7] A. Dixon, Summation of certain series, Proc. Lond. Mat. Soc. 35 (1) (1903), 285–289.
  * [8] J. Fuselier and D. McCarthy, Hypergeometric type identities in the $p$-adic setting and modular forms, Proc. Amer. Math. Soc. 144 (2016), 1493–1508
  * [9] C. Gauss, Disquisitiones generales circa seriem infinitam, in: Commentationes Societiones Regiae Scientiarum Gottingensis Recentiores, vol. II (1812), 235–-278.
  * [10] J. Greene, Hypergeometric functions over finite fields, Trans. Amer. Math. Soc. 301 (1) (1987), 77–101.
  * [11] B. H. Gross and N. Koblitz, Gauss sum and the $p$-adic $\Gamma$-function, Annals of Mathematics 109 (1979), 569–581.
  * [12] K. Ireland and M. Rosen, A Classical Inroduction to Modern Number Theory, Springer International Edition, Springer, (2005).
  * [13] N. Koblitz, $p$-adic analysis: a short course on recent work, London Math. Soc. Lecture Note Series, 46. Cambridge University Press, Cambridge-New York, (1980).
  * [14] N. Koblitz, The hypergeometric function with $p$-adic parameters, Proc. Queens Number Theory Conference, (1979), 319–328.
  * [15] E. Kummer, Ueber die hypergeometrische reihe, J. Math. 15 (1836), 39–83.
  * [16] R. Lidl and H. Niederreiter, Finite fields, Encyclopedia of Mathematics and Its Applications, (G.-C Rota, ed.), Vol. 20, Addison-Wesley, Cambridge, Mass., 1983.
  * [17] D. McCarthy, The trace of Frobenius of elliptic curves and the $p$-adic gamma function, Pacific J. Math. 261 (1) (2013), 219–236.
  * [18] K. Ono, Values of Gaussian hypergeometric series, Trans. Amer. Math. Soc. 350 (3) (1998), 1205–1223.
  * [19] L. Slater, Generalized hypergeometricfunctions, Cambridge Univ. Press, Cambridge, 1966.
  * [20] F. Whipple, On well-poised series, generalised hypergeometric series having parameters in pairs, each pair with the same sum, Proc. Lond. Math. Soc. 24 (2) (1926), 247–263.
  * [21] E. Whittaker and G. Watson, Modern analysis, Cambridge Univ. Press, Cambridge, 1947.