# Few-Shot Action Recognition with Compromised Metric via Optimal Transport

Su Lu Han-Jia Ye De-Chuan Zhan
State Key Laboratory for Novel Software Technology
Nanjing University, Nanjing, China
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Although vital to computer vision systems, few-shot action recognition is
still not mature despite the wide research of few-shot image classification.
Popular few-shot learning algorithms extract a transferable embedding from
seen classes and reuse it on unseen classes by constructing a metric-based
classifier. One main obstacle to applying these algorithms in action
recognition is the complex structure of videos. Some existing solutions sample
frames from a video and aggregate their embeddings to form a video-level
representation, neglecting important temporal relations. Others perform an
explicit sequence matching between two videos and define their distance as
matching cost, imposing too strong restrictions on sequence ordering. In this
paper, we propose Compromised Metric via Optimal Transport (CMOT) to combine
the advantages of these two solutions. CMOT simultaneously considers semantic
and temporal information in videos under Optimal Transport framework, and is
discriminative for both content-sensitive and ordering-sensitive tasks. In
detail, given two videos, we sample segments from them and cast the
calculation of their distance as an optimal transport problem between two
segment sequences. To preserve the inherent temporal ordering information, we
additionally amend the ground cost matrix by penalizing it with the positional
distance between a pair of segments. Empirical results on benchmark datasets
demonstrate the superiority of CMOT.

##  1 Introduction

The ability to learn with limited data is important, especially when data
collection is difficult. In computer vision systems, it may be impossible to
obtain abundant images of rare targets, restricting the application of image
classification [49], object detection [46, 19] and image segmentation [28].
Action recognition means recognizing a human action from a video containing
complete action execution [22], which is another non-negligible technology in
computer vision. It extends over many real-world applications, from human-
computer interaction to video surveillance and information retrieval [16].
Reducing the demand for training instances in action recognition is critical
owing to the high expense of gathering annotated videos.

Few-shot learning aims to endow a learner with the ability to recognize new
classes from a small number of labeled examples. Directly training a model
with limited instances easily falls into the dilemma of over-fitting. Thus, we
often assume that another large related dataset containing seen classes is
available, and the target is to classify unseen classes given a few annotated
instances. Among few-shot learning algorithms, metric-based algorithms have
achieved promising results [44, 37, 31, 49]. These methods try to learn a
generalizable embedding function from seen classes and reuse it to measure
instance distances or similarities on unseen classes. We can build a metric-
based classifier (e.g., nearest neighbour classifier) to make predictions with
assistance of the learned embedding function. Although successful in few-shot
image classification, the aforementioned algorithms are not specially designed
for video data, making it hard to reuse them in few-shot action recognition.

Figure 1: Illustration of aggregation-based methods and matching-based method.
Aggregation-based methods use aggregation function like average pooling to
obtain a video-level representation, neglecting temporal information.
Matching-based methods find a strictly progressive alignment between segment
sequences.

Some existing methods are direct extensions from few-shot image classification
algorithms [3, 1, 4]. They first obtain semantic representations of video
frames (or video segments) by a CNN (or 3DCNN), and then aggregate the
sequence of vectors into a single video embedding. The simplest aggregation
function is average pooling [7], which naively sums up the vectors in the
sequence. Attention is also widely used when aggregating segment
representations [12, 51]. By considering the similarities between segments,
attention can output a weighted sum of segment features. However, these
aggregation-based methods ignore the long-term temporal relations between
segments, resulting in a sub-optimal measurement of video distances. Consider
two different actions, i.e., moving an object from left to right and moving an
object from right to left. Since the aggregation process neglects the ordering
of segments, the distance between these two actions will be small, which is
harmful to the performance of classifier. Figure 1 (upper right part) is an
illustration of aggregation-based methods.

To overcome this issue, researchers have proposed to explicitly match two
videos by aligning their segment sequences without obtaining video-level
representations. In OTAM [6], the authors use Dynamic Time Warping (DTW) to
find the best alignment between two sequences and define the distance between
them as the alignment cost. As shown in Figure 1 (bottom right part), this
kind of matching-based methods ensures that the long-term ordering information
is considered during the computation of video distances. For example, if we
inverse the frame sequence of a video to generate a new video, the matching
cost between them will be large and OTAM tends to predict them as different
classes. This characteristic helps to differ actions that are sensitive to
long-term ordering (e.g., aforementioned left2right and right2left). However,
for actions that are irrelevant to temporal ordering but sensitive to content,
OTAM may work badly owing to DTW’s strong restriction on matching rules.

From the above introduction about two kinds of methods, we can see that they
are complementary. Aggregation-based methods focus on semantic information
while matching-based methods emphasize temporal ordering. Actually, both
semantic and temporal information should be considered in few-shot action
recognition. In this paper, we propose Compromised Metric via Optimal
Transport (CMOT), which simultaneously compares two videos’ content difference
and ordering difference to give a compromised measurement under Optimal
Transport (OT) framework [43, 9]. CMOT balances semantic and temporal
information in videos, achieving competitive performance in both content-
sensitive tasks and ordering-sensitive tasks.

In CMOT, we first sample several segments from a video, and get their
embeddings by 3DCNN [41, 8] to form a sequence of content representations.
Given two videos, we can compute the semantic cost matrix between their
content representations. To preserve the inherent temporal ordering
information, we additionally amend the semantic cost matrix by penalizing it
with the positional distance between a pair of segments. To be specific, the
cost between two segments at relatively far positions (e.g., the first segment
of a video and the last segment of another one) will be enlarged. Performing
OT on such a fused cost matrix induces an optimal transportation plan between
two videos based on both semantic and temporal information. We then take the
transportation cost as two videos’ distance, and build a metric-based
classifier to optimize the 3DCNN.

We demonstrate the superiority of balancing semantic and temporal information
in a synthetic experiment. CMOT also achieves competitive performance on
several benchmark datasets, e.g., UCF-101 [38], HMDB-51 [23], and SMSM-V2
[13]. Our contributions are threefold:

  * •

We jointly consider semantic and temporal information.

  * •

We formulate the distance between two videos as transportation cost, and
encapsulate the OT algorithm into metric-based few-shot learning framework.

  * •

We empirically demonstrate the effectiveness of CMOT on synthetic experiment
and action recognition datasets.

##  2 Related Work

#### Meta-Learning.

Meta-Learning [40] aims at extracting task-level experience from seen data,
while generalizing the learned meta-knowledge to unseen tasks efficiently. It
acts as one main tool for few-shot learning. Meta-learning algorithms can be
classified into three categories based on what kind of meta-knowledge they
catch. Memory-based methods [14, 35, 30] use external memory to facilitate
task learning. Optimization-based methods [10, 27, 32, 45, 34] try out some
optimization strategies and accelerate the training process of unseen tasks.
Our proposed method falls into the remaining category, metric-based algorithms
[44, 37, 25, 21, 49, 31, 26, 36, 17], which offer a shared embedding for
instances from new tasks. Metric-based methods are suitable for video problems
because they are more efficient than others. In our proposed CMOT, two videos’
distance is defined as the optimal transportation cost based on a fused cost
matrix. We further encapsulate the OT algorithm into the metric-based meta-
learning framework to make the whole model differentiable [50].

#### Few-Shot Action Recognition.

Following the idea of memory-based meta-learning, CMN [53] learns several key-
value pairs to represent a video in a large space. Apart from CMN, most of the
existing few-shot action recognition algorithms follow the idea of metric-
based meta-learning. They extract a generalizable video metric on previous
seen tasks, and transfer it to unseen new tasks. This line of methods can be
classified into two categories, i.e., aggregation-based methods and matching-
based methods. Both of these two kinds of methods first sample frames or
segments from a video and get their content representations, but aggregation-
based methods generate a video-level representation for distance calculation
by pooling [7, 24, 47, 54, 1, 5], adaptive fusion [11, 4], dynamic images
[39], or attention [3, 51, 12] while matching-based methods explicitly align
two sequences and define distance between videos as their matching cost by DTW
[6] or other matching strategies. Aggregation-based methods focus on semantic
contents while matching-based methods emphasize temporal ordering, and our
proposed CMOT simultaneously considers two aspects to form a compromised
metric.

##  3 Preliminary

In this section, we will describe two basic components of our proposed method.
Firstly, we will introduce the problem setting of few-shot learning, and
present a simple solution by transferring the embedding function [37].
Secondly, we give a concise review of optimal transport [43, 9].

###  3.1 Few-Shot Learning

Few-shot learning means learning from limited examples. In action recognition
scenario, an $N$-way $K$-shot task is composed of $N$ classes and $K$ training
videos per class. Another testing set sampled from the same $N$ classes is
provided to evaluate the classifier. In few-shot learning literature, the
small training set of each task is referred as support set
$\mathcal{S}=\\{(\mathbf{x}_{i},y_{i})\\}_{i=1}^{NK}$ and the testing set is
called query set $\mathcal{Q}=\\{(\mathbf{x}_{j},y_{j})\\}_{j=1}^{NQ}$. That
is, a task $\mathcal{T}$ is defined as
$\mathcal{T}=(\mathcal{S},\mathcal{Q})$. We assume that each video
$\mathbf{x}$ is composed of $M$ segments
$\mathbf{x}=[\mathbf{x}^{1},\cdots,\mathbf{x}^{m},\cdots,\mathbf{x}^{M}]$, and
each segment $\mathbf{x}^{m}$ contains a certain number of consecutive frames.

Researchers often utilize meta-learning to tackle few-shot action recognition
problems. A key idea in meta-learning is to mimic meta-testing process in
meta-training phase. Since the learned meta-model is intended for $N$-way
$K$-shot classification tasks, we sample episodic $N$-way $K$-shot tasks from
meta-training set $\mathcal{D}^{tr}$ (composed of SEEN classes) to optimize
our model. The main target is to extract knowledge from sampled tasks and
reuse it when a new task comes. In meta-testing phase, $N$-way $K$-shot tasks
are sampled from a meta-testing set $\mathcal{D}^{ts}$ (composed of UNSEEN
classes) to evaluate model performance. Figure 2 gives an illustration of this
protocol.

Figure 2: An illustration of episodic training protocol. During meta-training
phase, $N$-way $K$-shot action recognition tasks are sampled from
$\mathcal{D}^{tr}$ and used to optimize the meta-model. During meta-testing
phase, we sample $N$-way $K$-shot tasks with non-overlapping classes from
$\mathcal{D}^{ts}$. The target is to obtain high accuracy on unseen meta-
testing tasks.

A simple solution is to meta-learn an embedding function $\phi$, which maps an
input video segment $\mathbf{x}^{m}$ to a vectorial representation
$\phi(\mathbf{x}^{m})$. With a bit abuse of notations, we denote by
$\phi(\mathbf{x})$ the sequence of embedded segments
$[\phi(\mathbf{x}^{1}),\cdots,\phi(\mathbf{x}^{m}),\cdots,\phi(\mathbf{x}^{M})]$.
In a meta-training task $\mathcal{T}^{tr}$, the label of a query video
$\mathbf{x}_{j}$ could be determined by its mean distance to videos belonging
to each class in the support set $\mathcal{S}^{tr}$ as shown in the following
two equations. $\mathrm{dis}(\cdot,\cdot)$ is some function measuring the
distance between two transformed segment sequences.

$p(\hat{y}_{j}=n|\mathbf{x}_{j})=\frac{\exp\left\\{-\overline{\mathrm{DIS}}(\phi(\mathbf{x}_{j});n)\right\\}}{\sum_{n^{\prime}=1}^{N}\exp\left\\{-\overline{\mathrm{DIS}}(\phi(\mathbf{x}_{j});n^{\prime})\right\\}}$
(1)

$\overline{\mathrm{DIS}}(\phi(\mathbf{x}_{j});n)=\frac{1}{K}\sum_{(\mathbf{x}_{i},y_{j})\in\mathcal{S}^{tr}\wedge
y_{i}=n}\mathrm{dis}(\phi(\mathbf{x}_{i}),\phi(\mathbf{x}_{j}))$ (2)

Cross-entropy loss is optimized on all sampled tasks.

$\min_{\phi}\sum_{\mathcal{T}^{tr}\sim\mathcal{D}^{tr}}\sum_{(\mathbf{x}_{j},y_{j})\in\mathcal{Q}^{tr}}-\log
p(\hat{y}_{j}=y_{j}|\mathbf{x}_{j})$ (3)

After meta-training phase, we apply the learned embedding function $\phi$ to
$N$-way $K$-shot tasks $\mathcal{T}^{ts}$ sampled from $\mathcal{D}^{ts}$.

Obviously, the distance function $\mathrm{dis}(\cdot,\cdot)$ will influence
the model performance to a great extent. Aggregation-based methods [51] define
$\mathrm{dis}(\cdot,\cdot)$ as the Euclidean distance between aggregated video
representations, i.e.,
$\mathrm{dis}^{\mathrm{AGG}}(\phi(\mathbf{x}_{i}),\phi(\mathbf{x}_{j}))=\|\mathrm{AGG}(\phi(\mathbf{x}_{i}))-\mathrm{AGG}(\phi(\mathbf{x}_{j}))\|_{2}$
where $\mathrm{AGG}$ is an aggregation function like average pooling.
Important temporal relations in $\phi(\mathbf{x}_{i})$ and
$\phi(\mathbf{x}_{j})$ are neglected. Matching-based methods [6] define
$\mathrm{dis}(\cdot,\cdot)$ as the matching cost between two sequences
$\phi(\mathbf{x}_{i})$ and $\phi(\mathbf{x}_{j})$, i.e.,
$\mathrm{dis}^{\mathrm{MAT}}(\phi(\mathbf{x}_{i}),\phi(\mathbf{x}_{j}))=\mathrm{MAT}(\phi(\mathbf{x}_{i}),\phi(\mathbf{x}_{j}))$.
By performing sequence alignment algorithm such as DTW, matching-based methods
find a strictly progressive route from the first segment to the last segment,
imposing too strong restrictions on the ordering of videos. In CMOT, we
specially design a distance function that combines two methods under a
unifying OT framework.

###  3.2 Optimal Transport

The theory of optimal transport defines a geometry to compare measures
supported on metric probability spaces [2]. It finds a best matching between
two distributions to minimize the transportation cost given a cost matrix,
based on which we can define a distance between these two distributions. OT is
used in many applications, e.g., semantic correspondence analysis [29],
unsupervised domain adaptation [48], and label distribution learning [52]. In
this paper, we focus on discrete optimal transport.

######  Definition 1 (Transportation Plan)

For two discrete distributions $\bm{\mu},\bm{\nu}\in\Delta_{d}$ where
$\Delta_{d}=\\{\bm{\alpha}\in\mathbb{R}_{+}^{d}|\bm{\alpha}^{\top}\mathbf{1}_{d}=1\\}$111$\mathbb{R}_{+}$
is the set of non-negative real numbers. is the set of $d$-dimensional
probability simplexes, let $\Pi(\bm{\mu},\bm{\nu})$ be the set of transport
polytopes, which contains all legal transportation plans from $\bm{\mu}$ to
$\bm{\nu}$.

$\Pi(\bm{\mu},\bm{\nu})=\\{\mathbf{T}\in\mathbb{R}_{+}^{d\times
d}|\mathbf{T}\mathbf{1}_{d}=\bm{\mu},\mathbf{T}^{\top}\mathbf{1}_{d}=\bm{\nu}\\}$
(4)

######  Definition 2 (Optimal Transport)

Given a cost matrix $\mathbf{C}\in\mathbb{R}^{d\times d}$, the total cost of
mapping from $\bm{\mu}$ to $\bm{\nu}$ using transportation plan $\mathbf{T}$
can be quantified as $\langle\mathbf{T},\mathbf{C}\rangle$. The distance
between $\bm{\mu}$ and $\bm{\nu}$ is defined as an OT problem.

$\eta_{\mathbf{C}}\triangleq\min_{\mathbf{T}\in\Pi(\bm{\mu},\bm{\nu})}\langle\mathbf{T},\mathbf{C}\rangle$
(5)

The optimization problem defined in Equation (5) is a classic optimal
transport formulation. However, solving such a problem is computationally
expensive. According to [9], adding an entropy regularization term to the
transport object gives rise to a smoothed version of the underlying problem.
This makes the objective function strictly convex, and we have efficient
algorithms to solve it.

######  Definition 3 (Sinkhorn Distance)

Define the entropy of $\mathbf{T}$ as
$\mathcal{H}(\mathbf{T})=-\sum_{i=1}^{d}\sum_{j=1}^{d}\mathbf{T}_{ij}\log(\mathbf{T}_{ij})$.
By solving a smoothed version of optimal transport problem, we have the
Sinkhorn distance between $\bm{\mu}$ and $\bm{\nu}$.

$\eta_{\mathbf{C}}^{\lambda}\triangleq\min_{\mathbf{T}\in\Pi(\bm{\mu},\bm{\nu})}\langle\mathbf{T},\mathbf{C}\rangle-\frac{1}{\lambda}\mathcal{H}(\mathbf{T})$
(6)

######  Theorem 1 (Sinkhorn Algorithm [9])

Define matrix $\mathbf{G}=\exp(-\lambda\mathbf{C})$ as the element-wise
exponential of $\lambda\mathbf{C}$. The optimizer $\mathbf{T}^{\star}$ of
problem Equation (6) can be represented as the following form, where vector
$\mathbf{u}$ and $\mathbf{v}$ can be obtained by an iterative algorithm
$\mathbf{u}\leftarrow\bm{\mu}\oslash(\mathbf{G}\mathbf{v})$,$\mathbf{v}\leftarrow\bm{\nu}\oslash(\mathbf{G}^{\top}\mathbf{u})$.222$\oslash$
mean element-wise division. Refer to the supplement for proof and more
details.

$\mathbf{T}^{\star}=\mathrm{diag}(\mathbf{u})\mathbf{G}\mathrm{diag}(\mathbf{v})$
(7)

##  4 Main Approach

In this section, we will describe our proposed CMOT. Firstly, we will
introduce segment descriptor for extracting content representations, and then
show how to use optimal transport to measure the semantic gap between two
videos. Secondly, we add a soft restriction on video ordering by penalizing
the ground cost matrix with positional distance between a pair of segments. We
show that semantic and temporal information can be jointly considered in a
unifying framework. Finally we formulate the entire CMOT.

Figure 3: Framework of CMOT. In this figure, we show a $2$-way $1$-shot task.
We firstly sample segments from each video, and then get their content
representations by C3D. After that, we compute the fused cost matrix which
jointly considers semantic and temporal information. Optimal transport is used
to find a matching between segment sequences, based on which we can get query
instance’s distances to both support instances.

###  4.1 Semantic Matching

In this part, we will describe how to use optimal transport to match the
contents of two videos. After extracting segment embeddings by 3DCNN [41, 8],
we formulate the semantic distance between two videos as the optimal
transportation cost between their segment sequences.

#### Segment Descriptor.

As we know, a video describing an action may be split into several segments,
each of which corresponds to a sub-action. Studying the short-term sub-actions
benefits to the recognition of human motions. In CMOT, we assume all the
videos at hand have similar lengths, and each video $\mathbf{x}$ can be
represented by a series of ordered segments, i.e.,
$\mathbf{x}=[\mathbf{x}^{1},\cdots,\mathbf{x}^{m},\cdots,\mathbf{x}^{M}]$.333For
simplicity we assume all the videos have $M$ segments, but our method can
handle videos that have different numbers of segments without any
modification. With assistance of a 3DCNN $\phi$, we are able to embed a short
segment $\mathbf{x}^{m}$ to a $D$-dimensional vector $\phi(\mathbf{x}^{m})$.
Thus, the entire video is represented as
$[\phi(\mathbf{x}^{1}),\cdots,\phi(\mathbf{x}^{m}),\cdots,\phi(\mathbf{x}^{M})]$.
With a bit abuse of notations, we denote the transformed segment sequence of
length $M$ by $\phi(\mathbf{x})$.

#### How to transport between videos?

Following the thoughts in Section 3, now we need to design a distance function
$\mathrm{dis}(\cdot,\cdot)$ to measure the semantic gap between two segment
sequences. First of all, we introduce a probabilistic viewpoint of instance
generation, which is widely adopted by machine learning society. For example,
in NLP, a sentence can be defined as a probability distribution over words
[18]. Here we define each video as a distribution over segments, and then use
Sinkhorn distance Equation (6) to measure the dissimilarity between two
videos. The cost matrix can be obtained by computing Euclidean distances
between segment features. To summarize, the semantic distance between two
videos $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ are formalized as Equation (8)
and Equation (9), where $\bm{\mu}_{1}$ and $\bm{\mu}_{2}$ are segment
distributions of $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ respectively. Without
any prior knowledge, we can set $\bm{\mu}_{1}$ and $\bm{\mu}_{2}$ as
$M$-dimensional uniform distribution. If we know that some segment are more
important in a video, we can increase their weights by conveniently tuning the
segment distributions.

$\mathrm{dis}^{\mathrm{SE}}(\mathbf{x}_{1},\mathbf{x}_{2})=\min_{\mathbf{T}\in\Pi(\bm{\mu}_{1},\bm{\mu}_{2})}\langle\mathbf{T},\mathbf{C}^{\mathrm{SE}}\rangle-\frac{1}{\lambda}\mathcal{H}(\mathbf{T})$
(8)
$\mathbf{C}^{\mathrm{SE}}_{pq}=\|\phi(\mathbf{x}_{1}^{p})-\phi(\mathbf{x}_{2}^{q})\|_{2},\forall
p,q\in[M]$ (9)

###  4.2 Temporal Modelling

As indicated in Section 3, a key point in few-shot action recognition is the
design of distance metric. Like aggregation-based methods [4], the OT-based
method described in the previous subsection matches two videos’ contents,
neglecting important temporal relations in videos. In this part, we further
model temporal relations by optimal transport, imposing a soft regulation on
video orderings.

#### Positional Cost Matrix.

The purpose of considering long-term relations is to ensure that a segment in
$\mathbf{x}_{1}$ is mapped to a segment in $\mathbf{x}_{2}$ at near positions.
This helps to differ actions that are sensitive to orderings. For example,
consider two actions: moving an object from left to right (left2right) and
moving an object from right to left (right2left). If we ignore the ordering of
sub-actions and only focus on video contents, these two actions will not be
separated easily. In OTAM [6], the authors proposed to use DTW to align two
videos. DTW is a dynamic programming algorithm and is strictly progressive in
time dimension. That is, for two segments $\mathbf{x}_{1}^{1}$ and
$\mathbf{x}_{1}^{2}$ in video $\mathbf{x}_{1}$, if $\mathbf{x}_{1}^{1}$ is
located before $\mathbf{x}_{1}^{2}$, it must be mapped to a segment in video
$\mathbf{x}_{2}$ before the target segment of $\mathbf{x}_{1}^{2}$. This
characteristic imposes too strong restrictions on the ordering of videos, and
is harmful to the robustness of the learned distance metric. In this paper, we
define a positional cost matrix $\mathbf{C}^{\mathrm{PO}}$ as Equation (18),
whose value increases with the relative positional distance
$\left(\frac{p}{M}-\frac{q}{M}\right)^{2}$. Here $\sigma$ is a hyper-
parameter.

$\mathbf{C}^{\mathrm{PO}}_{pq}=\exp\left\\{-\frac{1}{\sigma^{2}}\frac{1}{\left(\frac{p}{M}-\frac{q}{M}\right)^{2}+1}\right\\},\forall
p,q\in[M]$ (10)

Similar to Equation (8), we can further define two videos’ positional distance
as Equation (11).

$\mathrm{dis}^{\mathrm{PO}}(\mathbf{x}_{1},\mathbf{x}_{2})=\min_{\mathbf{T}\in\Pi(\bm{\mu}_{1},\bm{\mu}_{2})}\langle\mathbf{T},\mathbf{C}^{\mathrm{PO}}\rangle-\frac{1}{\lambda}\mathcal{H}(\mathbf{T})$
(11)

Obviously, $\mathbf{C}^{\mathrm{PO}}$ imposes a soft regularization on the
ordering of videos by assigning a larger transportation cost between distant
segments.

###  4.3 CMOT Framework

In this subsection, we show that semantic matching and temporal matching can
be unified under a single OT problem, and give the formal expression of CMOT.

#### Compromised Distance Metric.

By simultaneously considering semantic contents and temporal orderings, we can
easily come up with a compromised distance function, i.e., the weighted sum of
$\mathrm{dis}^{\mathrm{SE}}(\cdot,\cdot)$ and
$\mathrm{dis}^{\mathrm{PO}}(\cdot,\cdot)$:

$\mathrm{dis}(\mathbf{x}_{1},\mathbf{x}_{2})=\mathrm{dis}^{\mathrm{SE}}(\mathbf{x}_{1},\mathbf{x}_{2})+\alpha\mathrm{dis}^{\mathrm{PO}}(\mathbf{x}_{1},\mathbf{x}_{2})$
(12)

In Equation (12), $\alpha$ is a hyper-parameter balancing the importance of
two parts. By the linearity of matrix inner-production, we can rewrite the
distance in Equation (12) as the following OT problem.

$\displaystyle\mathrm{dis}(\mathbf{x}_{1},\mathbf{x}_{2})$
$\displaystyle=\min_{\mathbf{T}\in\Pi(\bm{\mu}_{1},\bm{\mu}_{2})}\langle\mathbf{T},\mathbf{C}\rangle-\frac{1}{\lambda}\mathcal{H}(\mathbf{T})$
(13) $\displaystyle\mathrm{s.t.}$
$\displaystyle\mathbf{C}=\mathbf{C}^{\mathrm{SE}}+\alpha\mathbf{C}^{\mathrm{PO}}$

#### Objective.

We now summarize the formal expression of CMOT. For an $N$-way $K$-shot task
$\mathcal{T}^{tr}=(\mathcal{S}^{tr},\mathcal{Q}^{tr})$ sampled from meta-
training set $\mathcal{D}^{tr}$, the label of query instance $\mathbf{x}_{j}$
is predicted as Equation (14) and Equation (15).

$p(\hat{y}_{j}=n|\mathbf{x}_{j})=\frac{\exp\left\\{-\overline{\mathrm{DIS}}(\mathbf{x}_{j};n)\right\\}}{\sum_{n^{\prime}=1}^{N}\exp\left\\{-\overline{\mathrm{DIS}}(\mathbf{x}_{j};n^{\prime})\right\\}}$
(14)
$\overline{\mathrm{DIS}}(\mathbf{x}_{j};n)=\frac{1}{K}\sum_{(\mathbf{x}_{i},y_{j})\in\mathcal{S}^{tr}\wedge
y_{i}=n}\mathrm{dis}(\mathbf{x}_{i},\mathbf{x}_{j})$ (15)

Here $\mathrm{dis}(\mathbf{x}_{i},\mathbf{x}_{j})$ is defined as Equation
(12), i.e., Sinkhorn distance based on fused cost matrix. The main objective
of CMOT is shown as Equation (16).

$\displaystyle\min_{\phi}$
$\displaystyle\sum_{\mathcal{T}^{tr}\sim\mathcal{D}^{tr}}\sum_{(\mathbf{x}_{j},y_{j})\in\mathcal{Q}^{tr}}-\log
p(\hat{y}_{j}=y_{j}|\mathbf{x}_{j})$ (16) $\displaystyle\mathrm{s.t.}$
$\displaystyle\mathrm{dis}(\mathbf{x}_{i},\mathbf{x}_{j})=\min_{\mathbf{T}\in\Pi(\bm{\mu}_{i},\bm{\mu}_{j})}\langle\mathbf{T},\mathbf{C}\rangle-\frac{1}{\lambda}\mathcal{H}(\mathbf{T})$
$\displaystyle\textbf{C}=\textbf{C}^{\mathrm{SE}}+\alpha\mathbf{C}^{\mathrm{PO}}$

Figure 3 shows the whole framework of CMOT.

#### Solution to Bi-Level Optimization.

Obviously, the optimization problem expressed by Equation (16) is bi-level,
which means the computation of target function depends on the solution to
another nested optimization problem. By Equation (7), we can directly obtain
the gradient (or sub-gradient) of Sinkhorn distance
$\mathrm{dis}(\mathbf{x}_{i},\mathbf{x}_{j})$ with respect to parameters in
$\phi$, and make the whole CMOT easy to optimize. Refer to the supplement for
more details.

##  5 Experiments

There are three parts of experiments in this section. In the first part, we
test our method on a specially designed synthetic dataset to show the
superiority of jointly considering semantic and temporal information. In the
second part, we evaluate CMOT on three widely used benchmark datasets, i.e.,
UCF-101, HMDB-51, and SMSM-V2. Last are further studies about CMOT. Experiment
codes will be released after this paper being accepted.

| Content-Dominated | Ordering-Dominated
---|---|---
|  $5$-way $1$-shot |  $5$-way $1$-shot
TARN [3] | 45.0 $\pm$ 0.4 | 33.2 $\pm$ 0.3
OTAM [6] | 36.1 $\pm$ 0.4 | 46.3 $\pm$ 0.5
CMOT | 53.2 $\pm$ 0.6 | 49.4 $\pm$ 0.4
Table 1: Average accuracies ($\%$) with $95\%$ confidence intervals on tasks
sampled from two different meta-testing sets.

###  5.1 Semantic-Temporal Trade-off

#### Settings.

The most important advantage of CMOT is the ability to simultaneously consider
semantic and temporal information. Moreover, we can achieve a trade-off
between them by tuning hyper-parameter $\alpha$. To show this, we specially
design a synthetic experiment in this part by reversing the frame sequences of
videos. To be specific, we have a new video $\tilde{\mathbf{x}}$ by reversing
video $\mathbf{x}$, and consider two different label assignments. (1) Content-
Dominated. We assign the same label to $\tilde{\mathbf{x}}$ as $\mathbf{x}$.
Some actions are not sensitive to frame ordering. For example, when reversing
a video showing “talk”, we still get a “talk”. (2) Ordering-Dominated. We
assign a new label to $\tilde{\mathbf{x}}$. Some actions have totally
different meanings after being reversed. Intuitively, in the first setting,
matching-based methods like OTAM won’t work well. OTAM tries to find a
strictly progressive matching between segment sequences, but now there exist
two inverse videos with a same label, making it impossible for OTAM to pull
them close in the metric space. In the second setting, aggregation-based
methods will fail. Since typical aggregation-based methods generate a video-
level representation by pooling and neglect the temporal information, they
can’t differ two videos with same frames but different orderings. However, our
proposed CMOT can jointly consider semantic contents and temporal orderings,
and it can achieve good performances in both settings.

#### Datasets.

We conduct this synthetic experiment on HMDB-51. Firstly, we split HMDB-51
into meta-training, meta-validation, and meta-testing set. They contain $31$,
$10$, and $10$ classes respectively. After that, we reverse videos in meta-
validation set and meta-testing set to obtain new instances and assign labels
to them. In Content-Dominated setting, a reversed video has a same label as
its raw version, and the total number of classes in meta-validation set and
meta-testing set keeps unchanged. In Ordering-Dominated setting, we assign new
labels to reversed videos. Thus, the total number of classes in both meta-
validation set and meta-testing set comes to $20$.

#### Results.

We implement an aggregation-based method TARN [3] and a matching-based method
OTAM [6]. We train these two models and our proposed CMOT on the meta-training
set of HMDB-51, and test them on different meta-testing set. We show the
testing accuracy on two different meta-testing set in Table 1. As expected,
aggregation-based method fails the Ordering-Dominated setting while matching-
based method fails the Content-Dominated setting. Our proposed method works
well in both two settings, verifying the effectiveness of semantic-temporal
trade-off.

Method | Type | UCF-101 | HMDB-51 | SMSM-V2
---|---|---|---|---
$5$-way $1$-shot |  $5$-way $5$-shot |  $5$-way $1$-shot |  $5$-way $5$-shot |  $5$-way $1$-shot |  $5$-way $5$-shot
TARN | Aggregation | 84.2 $\pm$ 0.4 | 89.3 $\pm$ 0.6 | 57.0 $\pm$ 0.2 | 73.3 $\pm$ 0.3 | 33.2 $\pm$ 0.2 | 44.7 $\pm$ 0.4
TAEN | 88.3 $\pm$ 0.4 | 89.5 $\pm$ 0.4 | 63.9 $\pm$ 0.4 | 78.8 $\pm$ 0.3 | 37.1 $\pm$ 0.4 | 47.3 $\pm$ 0.4
ARN | 62.1 | 84.8 | 44.6 | 59.1 | - | -
ITA | 88.7 | 96.7 | 63.4 | 79.6 | - | -
TAV | 68.3 | 88.1 | 36.0 | 53.1 | - | -
AMeFu-Net | 85.1 | 95.5 | 60.2 | 75.5 | - | -
FAN | 71.8 | 86.5 | 50.2 | 67.6 | - | -
OTAM | Matching | 87.2 $\pm$ 0.3 | 93.3 $\pm$ 0.5 | 64.6 $\pm$ 0.5 | 77.0 $\pm$ 0.3 | 42.8 | 52.3
CMOT | Compromised | 90.4 $\pm$ 0.4 | 95.7 $\pm$ 0.3 | 66.9 $\pm$ 0.5 | 81.5 $\pm$ 0.4 | 46.8 $\pm$ 0.5 | 55.9 $\pm$ 0.4
Table 2: Average accuracies ($\%$) with $95\%$ confidence intervals on tasks
sampled from meta-testing set of UCF-101, HMDB-51, and SMSM-V2. Best results
are in bold. Red values are results from re-implementation. Black values are
results cited from papers. For methods that use 3DCNN backbone, we re-
implement them with pre-trained C3D. For methods that use CNN backbone, we re-
implement them with ResNet-50 [15] pre-trained on ImageNet [33].

###  5.2 Benchmark Evaluation

#### Datasets.

UCF-101 [38], HMDB-51 [23], and SMSM-V2 [13] are three widely used datasets
for action recognition. In our experiments, we re-sample and split them into
meta-training set, meta-validation set, and meta-testing set to fit few-shot
learning setting following [51, 6]. Some statistics about these datasets are
shown in Table 3. More information can be found in the supplement.

|  UCF |  HMDB |  SMSM
---|---|---|---
# classes |  101 |  51 |  100
# videos |  13320 |  6849 |  71718
# meta-training classes |  70 |  31 |  64
# meta-validation classes |  10 |  10 |  12
# meta-testing classes |  21 |  10 |  24
Table 3: Statistics about three benchmark datasets.

#### Implementation Details.

As in many previous papers [24, 51, 1, 3], we use C3D [41] pre-trained on
Sports-1M [20] as the embedding network for segment representations. For each
video, we uniformly sample $M=4$ segments, each of which contains $16$
consecutive frames. Since we have no prior knowledge on these videos, the
target distribution $\bm{\mu}$ in Equation (16) is set to an $4$-dimensional
uniform distribution for all videos. In meta-training phase, we randomly
sample $20000$ episodes from meta-training set. In meta-testing phase, we
sample $1000$ episodes from meta-testing set, and report the average test
accuracies with $95\%$ confidence intervals. More implementation details can
be found in the supplementary material.

#### Results.

We compare our proposed CMOT to other few-shot action recognition methods.
These methods can be classified into two categories, i.e., aggregation-based
methods and matching-based methods. We summarize experiment results in Table
2. CMOT achieves state-of-the-art performance in most cases. ITA [5] achieves
best result on $5$-way $5$-shot UCF-101, and this method utilizes an implicit
segment alignment and considers temporal information to some extent, verifying
that it is beneficial to incorporate sequence matching in few-shot action
recognition. Different from UCF-101 and HMDB-51, SMSM-V2 dataset contains
actions that are sensitive to temporal ordering, e.g., putting something on a
surface, moving something from left to right. Thus, matching-based method
(OTAM) achieves the highest performance among all the comparison methods. Our
proposed CMOT simultaneously considers video contents and temporal information
and outperforms OTAM.

#### Visualization of Transportation.

A key component in CMOT is optimal transport based on fused cost matrix
$\mathbf{C}$, and it is necessary to check whether this module can output a
reasonable matching based on both semantic and temporal information. Figure 4
shows the transportation matrix between two videos sampled from UCF-101. We
can see that segments with similar semantics are matched (first and second
segments in two videos), and segments at same position are matched. This means
the transportation plan generated by CMOT jointly considers video contents and
orderings.

Figure 4: Visualization of transportation matrix between two videos sampled
from UCF-101. Each video is represented by $4$ segments. The color of edge
represents the corresponding value in transportation matrix.

###  5.3 Further Analyses

#### Ablation Study.

In this part, we evaluate the effectiveness of each module in CMOT. We sample
tasks from HMDB-51 to evaluate several variants of CMOT. We summarize
experiment results in Table 4. By removing optimal transport module, our
method degenerates to a simple metric-based meta-learning algorithm, which
classifies the query instance to the class label of its nearest class center.
Equipped with positional cost matrix and optimal transport, our model
outperforms the baseline models by a noticeable margin.

Model | OT | PO |  $5$-way $1$-shot |  $5$-way $5$-shot
---|---|---|---|---
0 | $\times$ | $\times$ |  63.4 $\pm$ 0.3 |  79.4 $\pm$ 0.3
1 | $\checkmark$ | $\times$ |  64.9 $\pm$ 0.2 |  79.2 $\pm$ 0.1
C3D $+$ LSTM | $\times$ | $\times$ |  51.8 $\pm$ 0.4 |  70.0 $\pm$ 0.3
C3D $+$ DTW | $\times$ | $\times$ |  62.6 $\pm$ 0.4 |  77.3 $\pm$ 0.2
CMOT | $\checkmark$ | $\checkmark$ | 66.9 $\pm$ 0.5 | 81.5 $\pm$ 0.4
Table 4: Average test accuracies ($\%$) with $95\%$ confidence intervals of
several variants on HMDB-51. OT stands for optimal transport. PO means
positional cost matrix. C3D $+$ LSTM means using an LSTM to capture temporal
relations in segment features generated by C3D. C3D $+$ DTW means using DTW to
align segment sequences, which is similar to OTAM (different embeddings).

#### Hyper-Parameter $\lambda$.

In CMOT, we utilize Sinkhorn distance Equation (6) to measure the
dissimilarity between two videos. Here $\lambda$ is a smoothing factor, and
the larger it is, the closer Sinkhorn distance is to raw OT distance.
Following [9], we heuristically set $\lambda$ as $\\{5,7,9\\}\times
1/\mathrm{med}(\mathbf{C})$. Here $\mathrm{med}(\cdot)$ is the medium value
operator and $\mathbf{C}$ is defined as Equation (17). Results are shown in
Table 5. We can see that the value of $\lambda$ has little influence on model
accuracy.

$\lambda$ | UCF-101 | HMDB-51
---|---|---
$1$-shot |  $5$-shot |  $1$-shot |  $5$-shot
$5\times\mathrm{med}$ |  89.0$\pm$0.3 | 96.3$\pm$0.4 |  65.2$\pm$0.2 |  80.0$\pm$0.2
$7\times\mathrm{med}$ | 90.4$\pm$0.4 | 95.7$\pm$0.3 | 66.9$\pm$0.5 | 81.5$\pm$0.4
$9\times\mathrm{med}$ |  89.4$\pm$0.3 |  95.1$\pm$0.5 |  66.2$\pm$0.3 |  80.8$\pm$0.3
Table 5: Average test accuracies ($\%$) with $95\%$ confidence intervals for
different $\lambda$ values. Best results are in bold. Blue: we choose
$\lambda=7\times\mathrm{med}(\tilde{\mathbf{C}})$ in our experiments where
$\mathrm{med}(\cdot)$ is medium value operator.

#### Hyper-parameter $\alpha$.

$\alpha$ balances the importance of semantic contents and temporal orderings.
Intuitively, for tasks that are more sensitive to temporal orderings, we
should set $\alpha$ to a larger value. As indicated in the previous
subsection, SMSM-V2 dataset contains fine-grained actions that are not easy to
differ without considering long-term orderings. Thus, we check the influence
of $\alpha$ on UCF-101 and SMSM-V2. Results are shown in Figure 5.

Figure 5: Average test accuracies ($\%$) on $5$-way $1$-shot tasks sampled
from UCF-101 and SMSM-V2. We try different $\alpha$ values. Hyper-parameter
$\alpha$ has relatively small influence on UCF-101 since it is a coarse-
grained dataset. However, for SMSM-V2, we should pay more attention to long-
term temporal ordering to obtain a higher accuracy.

##  6 Conclusion

In this paper, we propose Compromised Metric via Optimal Transport (CMOT), a
new framework that jointly considers video contents and temporal relations in
few-shot action recognition. Different from existing methods that either focus
on semantic information by aggregation or emphasize temporal information by
sequence alignment, we simultaneously take two aspects into account within a
single OT problem. CMOT defines two videos’ distance as the transportation
cost between their segment sequences based on a fused cost matrix, and then
predicts the label using a metric-based meta-learning method. On several
benchmark datasets, CMOT achieves state-of-the-art results.

## Appendix A: Review of CMOT

CMOT is designed for few-shot action recognition problems. It jointly
considers semantic and temporal information in videos and unites them in an
Optimal Transport (OT) framework. In this section, we will first give a
concise review of CMOT, and then discuss several details.

### Algorithm Review

CMOT belongs to metric-based meta-learning methods [21, 44, 37, 25, 49]. These
algorithms often meta-learn an embedding function from meta-training set, and
then reuse the learned representation on meta-testing set. Obviously, a key
point in applying these methods to few-shot action recognition is the design
of distance metric function. In few-shot action recognition, it is more
difficult to measure the distance between videos than images owing to the
complex temporal structures.

0: Cost matrix $\mathbf{C}$, target distribution $\bm{\mu}$ and $\bm{\nu}$,
smoothing parameter $\lambda$.

Compute $G=\exp(-\lambda\mathbf{C})$.

Initialize $\mathbf{u}$ and $\mathbf{v}$.

repeat

Compute $\mathbf{u}=\bm{\mu}\oslash(\mathbf{G}\mathbf{v})$.

Compute $\mathbf{v}=\bm{\nu}\oslash(\mathbf{G}^{\top}\mathbf{u})$.

until Convergence

Compute
$\mathbf{T}^{\star}=\text{diag}(\mathbf{u})\mathbf{G}\text{diag}(\mathbf{v})$.

Algorithm 1 Algorithm flow for solving Sinkhorn problem.

Existing few-shot action recognition algorithms can be classified into two
categories, i.e., aggregation-based methods and matching-based methods. Both
of these two kinds of methods first sample frames or segments from a video and
get their content representations, but aggregation-based methods generate a
video-level representation for distance calculation by pooling [7, 24, 47, 54,
1, 5], adaptive fusion [11, 4], dynamic images [39], or attention [3, 51, 12]
while matching-based methods explicitly align two sequences and define
distance between videos as their matching cost by DTW [6] or other matching
strategies. Aggregation-based methods tend to focus on semantic information
while matching-based methods impose a strict regulation on video orderings.

In CMOT, we simultaneously consider semantic and temporal information in
videos. We first sample segments from videos and get their content
representations by 3DCNN [41, 8], and then compute the distance matrix between
two segment sequences to form a semantic cost matrix. After that, we define
the positional cost matrix as the relative distance between two segments’
positions. By adding the positional cost matrix to segment cost matrix, we can
obtain a fused cost matrix, the optimal transportation plan based on which
jointly considers video contents and segment orderings.

### Sinkhorn Algorithm

An important step in computing video distances with CMOT is solving the OT
problem in Equation (17).

$\displaystyle\mathrm{dis}(\mathbf{x}_{1},\mathbf{x}_{2})$
$\displaystyle=\min_{\mathbf{T}\in\Pi(\bm{\mu}_{1},\bm{\mu}_{2})}\langle\mathbf{T},\mathbf{C}\rangle-\frac{1}{\lambda}\mathcal{H}(\mathbf{T})$
(17) $\displaystyle\mathrm{s.t.}$
$\displaystyle\mathbf{C}=\mathbf{C}^{\mathrm{SE}}+\alpha\mathbf{C}^{\mathrm{PO}}$

Here $\mathbf{C}^{\mathrm{SE}}$ is the semantic cost matrix and
$\mathbf{C}^{\mathrm{PO}}$ is the positional cost matrix. $\bm{\mu}_{1}$ and
$\bm{\mu}_{2}$ are target distributions for two videos, and we empirically set
them as uniform $M$-dimensional distributions. OT problem is not easy to
solve, but by adding an entropy term
$\frac{1}{\lambda}\mathcal{H}(\mathbf{T})$, we make the objective function
smoother and have efficient numerical algorithms [9] as shown in Algorithm 1.

After executing Algorithm 1, we obtain a ‘closed form’ of optimal
transportation plan
$\mathbf{T}^{\star}=\text{diag}(\bm{\mu}_{1})\mathbf{G}\text{diag}(\bm{\mu}_{2})$,
and can differentiate the transportation cost w.r.t. cost matrix $\mathbf{C}$.
The learnable parameters contained in 3DCNN can be updated by sub-gradient
descent.

Positional Cost Matrix | UCF-101 | HMDB-51
---|---|---
$5$-way $1$-shot |  $5$-way $5$-shot |  $5$-way $1$-shot |  $5$-way $5$-shot
Induced by Uniform PE | 89.1 $\pm$ 0.3 | 93.9 $\pm$ 0.2 | 65.2 $\pm$ 0.4 | 79.3 $\pm$ 0.3
Induced by Sinusoid PE | 87.1 $\pm$ 0.3 | 91.2 $\pm$ 0.3 | 64.1 $\pm$ 0.3 | 78.1 $\pm$ 0.5
Our Proposal | 90.4 $\pm$ 0.4 | 95.7 $\pm$ 0.3 | 66.9 $\pm$ 0.5 | 81.5 $\pm$ 0.4
Table 6: Average accuracies ($\%$) with $95\%$ confidence intervals on tasks
sampled from meta-testing set of UCF-101 and HMDB-51. Best results are in
bold. Our proposed positional cost matrix achieves best results.

### Positional Cost Matrix

In order to capture long-term temporal relations in videos, CMOT additionally
penalize the semantic cost matrix with relative distances between segments, as
shown in Equation (18). This means the transportation cost between distant
segments will be enlarged, encouraging OT algorithm to assign a lower value to
the corresponding transportation plan.

$\mathbf{C}^{\mathrm{PO}}_{pq}=\exp\left\\{-\frac{1}{\sigma^{2}}\frac{1}{\left(\frac{p}{M}-\frac{q}{M}\right)^{2}+1}\right\\},\forall
p,q\in[M]$ (18)

In Equation (18). $\sigma$ is a hyper-parameter that rescales the values in
positional cost matrix. We check the influence of $\sigma$ on UCF-101 dataset.
The results are shown in Figure 6. We can see that $\sigma$ has a non-
neglectable influence on model performance. A larger $\sigma$ makes the
distribution of values in $\mathbf{C}$ smoother, weakening the impact of
temporal relations between segment sequences. For tasks that are sensitive to
video orderings, we are supposed to set a smaller $\sigma$.

Figure 6: Average test accuracies ($\%$) on $5$-way $1$-shot tasks and $5$-way
$5$-shot tasks sampled from UCF-101. We try different $\sigma$ values.

Positional cost matrix can be defined as other formulations. For example, we
can borrow the idea of positional encoding [42], and defines the
transportation cost between two segments as the difference between their
positional encodings. Assuming that a video is composed of $M$ segments and
the dimension of positional encoding is $D$, there are two commonly used
positional encodings:

  * •

Uniform Positional Encodings. $\mathbf{P}_{md}=\frac{m}{M},\forall
m\in[M],\forall d\in[D]$.

  * •

Sinusoid Positional Encodings.
$\mathbf{P}_{md}=\left\\{\begin{matrix}\sin\left(\frac{m}{10000^{d/D}}\right),&d\text{
is even}\\\ \cos\left(\frac{m}{10000^{(d-1)/D}}\right),&d\text{ is
odd}\end{matrix}\right.,\forall m\in[M],\forall d\in[D]$.

Positional cost matrix can be computed as
$\mathbf{C}^{\mathrm{PO}}_{pq}=\|\mathbf{P}_{p}-\mathbf{P}_{q}\|_{2}$. For
uniform positional encodings, we have
$\mathbf{C}^{\mathrm{PO}}=\frac{\sqrt{D}}{M}|p-q|$, which is monotonically
increasing in the relative temporal distance $|p-q|$. Thus, the positional
cost matrix induced by uniform positional encodings have similar properties as
our proposed one. However, sinusoid positional encodings proposed in [42]
don’t have this property, and is not very suitable for modelling long-term
temporal relations in our case. Table 6 gives the results of an ablation study
on positional cost matrix. As expected, uniform positional encoding
outperforms sinusoid positional encoding.

### Segment Sampling Strategy

All the existing few-shot action recognition methods first sample segments
from the whole video, and sampling strategy is a vital factor to model
performance. However, there lacks a systematic research of sampling strategy.
After summarizing existing papers [7, 24, 47, 54, 1, 5, 11, 4, 39, 6, 3, 51,
12], we divide sampling strategies into two categories:

  * •

Cut the video into $M$ clips and sample one single frame from each clip. In
this case, a segment is composed of a single image.

  * •

Cut the video into $M$ clips and treat each clip as a segment. In this case, a
segment contains many consecutive images.

The second strategy includes redundant information since consecutive images
are similar to each other while the first strategy may ignore some important
frames. In CMOT, after cutting the video into $M$ clips, we randomly sample
$16$ frames from each clip to form a segment, balancing intra-segment and
inter-segment relations. Table 7 is an ablation study about sampling
strategies.

Sampling Strategy | SMSM-V2
---|---
$5$-way $1$-shot |  $5$-way $5$-shot
Single Frame | 40.3 $\pm$ 0.4 | 47.9 $\pm$ 0.4
Whole Clip | 44.2 $\pm$ 0.3 | 51.7 $\pm$ 0.5
Our Proposal | 46.8 $\pm$ 0.5 | 55.9 $\pm$ 0.4
Table 7: Average test accuracies ($\%$) on $5$-way $1$-shot tasks and $5$-way
$5$-shot tasks sampled from SMSM-V2. We try three different sampling
strategies.

## Appendix B: Experiment Details

In this part, we give more information about experiments, such as dataset
split and implementation details.

### Datasets

In this paper, we use three action recognition benchmark datasets, i.e.,
UCF-101 [38], HMDB-51 [23], and SMSM-V2 [13] to evaluate CMOT and comparison
methods. We split each dataset into meta-training set, meta-validation set,
and meta-testing set to fit few-shot learning setting. UCF-101 contains 101
classes while HMDB-51 contains 51 classes. These two datasets contain coarse-
grained actions that are more sensitive to video contents. SMSM-V2 contains
100 classes, and is composed of fine-grained actions like ‘moving something
from left to right’. Table 8, Table 9, and Table 10 show detailed split of
these three datasets.

split | classes
---|---
meta-training |  | IceDancing, CricketShot, FieldHockeyPenalty, RockClimbingIndoor, CricketBowling, BaseballPitch,
---
CuttingInKitchen, PlayingDhol, MilitaryParade, BrushingTeeth, PoleVault,
VolleyballSpiking,
Hammering, Surfing, HeadMassage, Knitting, SkyDiving, HammerThrow,
TaiChi, PlayingTabla, JumpingJack, ApplyLipstick, PlayingCello,
BoxingPunchingBag,
Haircut, Drumming, BodyWeightSquats, ParallelBars, JavelinThrow, FrisbeeCatch,
TennisSwing, BreastStroke, FloorGymnastics, RopeClimbing, TableTennisShot,
Nunchucks,
HorseRiding, GolfSwing, Skijet, HorseRace, Skiing, JugglingBalls,
PommelHorse, Archery, BalanceBeam, SoccerPenalty, TrampolineJumping,
PlayingDaf,
BandMarching, Fencing, PushUps, PlayingSitar, BoxingSpeedBag, JumpRope,
PlayingGuitar, SalsaSpin, Mixing, CleanAndJerk, Typing, Diving,
WalkingWithDog, WritingOnBoard, HighJump, PlayingViolin, Rowing, PlayingFlute,
Rafting, BabyCrawling, SoccerJuggling, BenchPress
meta-validation |  | Biking, Billiards, Basketball, ShavingBeard, PizzaTossing, HandstandWalking,
---
BlowDryHair, SkateBoarding, PullUps, HandstandPushups
meta-testing |  | FrontCrawl, Shotput, LongJump, BlowingCandles, BasketballDunk, ThrowDiscus,
---
UnevenBars, Swing, Bowling, HulaHoop, Lunges, StillRings,
WallPushups, ApplyEyeMakeup, PlayingPiano, CliffDiving, SumoWrestling,
MoppingFloor,
YoYo, Punch, Kayaking
Table 8: Dataset split of UCF-101. split | classes
---|---
meta-training |  | shoot-bow, jump, smoke, smile, fall-floor, dribble,
---
turn, walk, shoot-ball, sit, sword, kiss,
throw, cartwheel, pushup, sword-exercise, run, pour,
eat, draw-sword, catch, kick-ball, climb-stairs, pullup,
hit, stand, handstand, swing-baseball, push, talk,
clap
meta-validation |  | ride-bike, golf, flic-flac, kick, dive, chew,
---
ride-horse, shoot-gun, climb, pick
meta-testing |  | laugh, wave, shake-hands, punch, situp, brush-hair,
---
drink, fencing, somersault, hug
Table 9: Dataset split of HMDB-51. split | classes
---|---
meta-training |  | Dropping sth behind sth, Poking a stack of sth so the stack collapses, Spilling sth next to sth,
---
Failing to put sth into sth because sth does not fit, Pretending to throw sth,
Taking sth out of sth,
Moving away from sth with your camera, Pretending to take sth out of sth,
Showing sth on top of sth,
Lifting up one end of sth, then letting it drop down, Pretending to put sth on
a surface,
Pushing sth with sth, Pulling sth from right to left, Rolling sth on a flat
surface,
Moving sth away from the camera, Pretending to put sth underneath sth, Tearing
sth into two pieces,
Putting sth onto sth else that cannot support it so it falls down, Showing sth
to the camera,
Dropping sth next to sth, Lifting a surface with sth on it until it starts
sliding down,
Spinning sth so it continues spinning, Tilting sth with sth on it until it
falls off, Plugging sth into sth,
Pretending to be tearing sth that is not tearable, Pretending to sprinkle air
onto sth,
Lifting up one end of sth without letting it drop down, Turning the camera
upwards while filming sth,
Tilting sth with sth on it slightly so it doesn’t fall down, Pretending to
turn sth upside down,
Lifting a surface with sth on it but not enough for it to slide down,
Unfolding sth,
Moving sth across a surface until it falls down, Poking a hole into some
substance,
Spinning sth that quickly stops spinning, Covering sth with sth, Putting sth
next to sth,
Putting sth and sth on the table, Throwing sth onto a surface, Pushing sth
from left to right,
Plugging sth into sth but pulling it right out as you remove your hand,
Sth colliding with sth and both are being deflected, Laying sth on the table
on its side, not upright,
Poking a hole into sth soft, Pushing sth so that it slightly moves, Putting
sth onto sth,
Holding sth over sth, Letting sth roll along a flat surface, Folding sth,
Trying to pour sth into sth, but missing so it spills next to it, Showing a
photo of sth to the camera,
Tipping sth with sth in it over, so sth in it falls out, Twisting (wringing)
sth wet until water comes out,
Taking sth from somewhere, Throwing sth against sth, Spilling sth behind sth,
Approaching sth with your camera, Pretending to squeeze sth, Putting sth
behind sth, Holding sth behind sth,
Poking sth so that it falls over, Pretending to put sth behind sth, Pulling
sth onto sth,
Spreading sth onto sth
meta-validation |  | Putting sth, sth and sth on the table, Putting sth onto sth else that cannot support it so it falls down,
---
Pulling two ends of sth so that it separates into two pieces, Pulling sth from
right to left,
Dropping sth into sth, Pouring sth onto sth, Pretending or failing to wipe sth
off of sth, Folding sth,
Spinning sth so it continues spinning, Pushing sth so that it falls off the
table,
Letting sth roll down a slanted surface, Showing sth to the camera
meta-testing |  | Spreading sth onto sth, Pretending to throw sth, Pretending to close sth without actually closing it,
---
Spinning sth that quickly stops spinning, Pushing sth off of sth, Throwing
sth, Pushing sth onto sth,
Taking one of many similar things on the table, Holding sth over sth, Putting
sth upright on the table,
Tilting sth with sth on it until it falls off, Throwing sth in the air and
catching it,
Showing that sth is inside sth, Pretending to open sth without actually
opening it,
Pretending to turn sth upside down, Pouring sth out of sth, Throwing sth in
the air and letting it fall,
Showing that sth is empty, Putting sth and sth on the table, Showing sth to
the camera,
Sprinkling sth onto sth, Opening sth, Tearing sth into two pieces,
Moving sth across a surface until it falls down
Table 10: Dataset split of SMSM-V2.

### Implementation Details

In this section, we give more implementation details of CMOT. As in many
previous works [24, 51, 1, 3], we use C3D [41] pre-trained on Sports-1M [20]
as the embedding network for frame segment. For each video, we uniformly
sample $M=4$ segments, each of which contains $16$ consecutive frames. The
target distribution $\bm{\mu}$ is set to an $M$-dimensional uniform
distribution for all videos. In meta-training phase, we randomly sample
$20000$ episodes from meta-training set. In meta-testing phase, we sample
$1000$ episodes from meta-testing set. For an $N$-way $K$-shot task, we sample
$1$ video for each class to form the query set. We use SGD optimizer to train
the model. The initial learning rate for pre-trained segment descriptor is set
to $0.001$, and the initial learning rate for other parameters is set to
$0.01$. Two learning rates are decreased by $0.2$ after every $2000$ episodes.
As indicated in the paper, smoothing hyper-parameter $\lambda$ is set to
$7\times\mathrm{med}(\mathbf{C})$ where $\mathrm{med}(\cdot)$ is the medium
value operator and $\mathbf{C}$ is the fused cost matrix. Hyper-parameter
$\alpha$ is set as $0.4$, $0.4$, and $0.8$ for UCF-101, HMDB-51, and SMSM-V2
respectively. Hyper-parameter $\sigma$ is set as $1.2$ for three benchmark
datasets.

## References

  * [1] Rami Ben-Ari, Mor Shpigel, Ophir Azulai, Udi Barzelay, and Daniel Rotman.  Taen: Temporal aware embedding network for few-shot action recognition.  CoRR, abs/2004.10141, 2020.
  * [2] Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré.  Iterative bregman projections for regularized transportation problems.  SIAM Journal on Scientific Computing, 37(2):A1111–A1138, 2015.
  * [3] Mina Bishay, Georgios Zoumpourlis, and Ioannis Patras.  Tarn: Temporal attentive relation network for few-shot and zero-shot action recognition.  CoRR, abs/1907.09021, 2019.
  * [4] Yang Bo, Yangdi Lu, and Wenbo He.  Few-shot learning of video action recognition only based on video contents.  In Proceedings of the IEEE Winter Conference on Applications of Computer Vision, pages 595–604, 2020.
  * [5] Congqi Cao, Yajuan Li, Qinyi Lv, Peng Wang, and Yanning Zhang.  Few-shot action recognition with implicit temporal alignment and pair similarity optimization.  CoRR, abs/2010.06215, 2020.
  * [6] Kaidi Cao, Jingwei Ji, Zhangjie Cao, Chien-Yi Chang, and Juan Carlos Niebles.  Few-shot video classification via temporal alignment.  In Proceedings of the 33rd IEEE Conference on Computer Vision and Pattern Recognition, pages 10618–10627, 2020.
  * [7] Chris Careaga, Brian Hutchinson, Nathan Hodas, and Lawrence Phillips.  Metric-based few-shot learning for video action recognition.  CoRR, abs/1909.09602, 2019.
  * [8] Joao Carreira and Andrew Zisserman.  Quo vadis, action recognition? a new model and the kinetics dataset.  In Proceedings of the 30th IEEE Conference on Computer Vision and Pattern Recognition, pages 6299–6308, 2017.
  * [9] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  In Advances in Neural Information Processing Systems 26, pages 2292–2300, 2013.
  * [10] Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  In Proceedings of the 34th International Conference on Machine Learning, pages 1126–1135, 2017.
  * [11] Yuqian Fu, Li Zhang, Junke Wang, Yanwei Fu, and Yu-Gang Jiang.  Depth guided adaptive meta-fusion network for few-shot video recognition.  In Proceedings of the 28th ACM International Conference on Multimedia, pages 1142–1151, 2020.
  * [12] Zan Gao, Leming Guo, Weili Guan, An-An Liu, Tongwei Ren, and Shengyong Chen.  A pairwise attentive adversarial spatiotemporal network for cross-domain few-shot action recognition-r2.  IEEE Transactions on Image Processing, 30:767–782, 2020.
  * [13] Raghav Goyal, Samira Ebrahimi Kahou, Vincent Michalski, Joanna Materzynska, Susanne Westphal, Heuna Kim, Valentin Haenel, Ingo Fruend, Peter Yianilos, Moritz Mueller-Freitag, et al.  The” something something” video database for learning and evaluating visual common sense.  In Proceedings of the 17th International Conference on Computer Vision, page 5, 2017.
  * [14] Alex Graves, Greg Wayne, and Ivo Danihelka.  Neural turing machines.  CoRR, abs/1410.5401, 2014.
  * [15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the 29th IEEE Conference on Computer Vision and Pattern Recognition, pages 770–778, 2016.
  * [16] Samitha Herath, Mehrtash Harandi, and Fatih Porikli.  Going deeper into action recognition: A survey.  Image and Vision Computing, 60:4–21, 2017.
  * [17] Ruibing Hou, Hong Chang, Bingpeng MA, Shiguang Shan, and Xilin Chen.  Cross attention network for few-shot classification.  In Advances in Neural Information Processing Systems 32, pages 4003–4014. 2019.
  * [18] Gao Huang, Chuan Quo, Matt J Kusner, Yu Sun, Kilian Q Weinberger, and Fei Sha.  Supervised word mover’s distance.  In Advances in Neural Information Processing Systems 29, pages 4869–4877, 2016.
  * [19] Bingyi Kang, Zhuang Liu, Xin Wang, Fisher Yu, Jiashi Feng, and Trevor Darrell.  Few-shot object detection via feature reweighting.  In Proceedings of the 17th International Conference on Computer Vision, pages 8420–8429, 2019.
  * [20] Andrej Karpathy, George Toderici, Sanketh Shetty, Thomas Leung, Rahul Sukthankar, and Li Fei-Fei.  Large-scale video classification with convolutional neural networks.  In CVPR, 2014.
  * [21] Gregory Koch, Richard Zemel, and Ruslan Salakhutdinov.  Siamese neural networks for one-shot image recognition.  In 32nd International Conference on Machine Learning Workshop, volume 2, 2015.
  * [22] Yu Kong and Yun Fu.  Human action recognition and prediction: A survey.  CoRR, abs/1806.11230, 2018.
  * [23] Hildegard Kuehne, Hueihan Jhuang, Estíbaliz Garrote, Tomaso Poggio, and Thomas Serre.  Hmdb: A large video database for human motion recognition.  In Proceedings of the 14th International Conference on Computer Vision, pages 2556–2563, 2011.
  * [24] Sai Kumar Dwivedi, Vikram Gupta, Rahul Mitra, Shuaib Ahmed, and Arjun Jain.  Protogan: Towards few shot learning for action recognition.  In 17th International Conference on Computer Vision Workshop, pages 0–0, 2019.
  * [25] Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto.  Meta-learning with differentiable convex optimization.  In Proceedings of the 32nd IEEE Conference on Computer Vision and Pattern Recognition, pages 10657–10665, 2019.
  * [26] Hongyang Li, David Eigen, Samuel Dodge, Matthew Zeiler, and Xiaogang Wang.  Finding task-relevant features for few-shot learning by category traversal.  In Proceedings of the 32nd IEEE Conference on Computer Vision and Pattern Recognition, pages 1–10, 2019.
  * [27] Zhenguo Li, Fengwei Zhou, Fei Chen, and Hang Li.  Meta-sgd: Learning to learn quickly for few-shot learning.  CoRR, abs/1707.09835, 2017.
  * [28] Weide Liu, Chi Zhang, Guosheng Lin, and Fayao Liu.  Crnet: Cross-reference networks for few-shot segmentation.  In Proceedings of the 33rd IEEE Conference on Computer Vision and Pattern Recognition, pages 4165–4173, 2020.
  * [29] Yanbin Liu, Linchao Zhu, Makoto Yamada, and Yi Yang.  Semantic correspondence as an optimal transport problem.  In Proceedings of the 33rd IEEE Conference on Computer Vision and Pattern Recognition, pages 4463–4472, 2020.
  * [30] Tsendsuren Munkhdalai, Alessandro Sordoni, Tong Wang, and Adam Trischler.  Metalearned neural memory.  In Advances in Neural Information Processing Systems 32, pages 13310–13321. 2019.
  * [31] Boris Oreshkin, Pau Rodríguez López, and Alexandre Lacoste.  Tadam: Task dependent adaptive metric for improved few-shot learning.  In Advances in Neural Information Processing Systems 31, pages 721–731. 2018.
  * [32] Sachin Ravi and Hugo Larochelle.  Optimization as a model for few-shot learning.  In Proceedings of the 5th International Conference on Learning Representations, 2017.
  * [33] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al.  Imagenet large scale visual recognition challenge.  International Journal of Computer Vision, 115(3):211–252, 2015\.
  * [34] Andrei A. Rusu, Dushyant Rao, Jakub Sygnowski, Oriol Vinyals, Razvan Pascanu, Simon Osindero, and Raia Hadsell.  Meta-learning with latent embedding optimization.  In Proceedings of the 7th International Conference on Learning Representations, 2019.
  * [35] Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy Lillicrap.  Meta-learning with memory-augmented neural networks.  In Proceedings of the 33rd International Conference on Machine Learning, pages 1842–1850, 2016.
  * [36] Christian Simon, Piotr Koniusz, Richard Nock, and Mehrtash Harandi.  Adaptive subspaces for few-shot learning.  In Proceedings of the 33rd IEEE Conference on Computer Vision and Pattern Recognition, pages 4136–4145, 2020.
  * [37] Jake Snell, Kevin Swersky, and Richard S. Zemel.  Prototypical networks for few-shot learning.  In Advances in Neural Information Processing Systems 30, pages 4077–4087. 2017.
  * [38] Khurram Soomro, Amir Roshan Zamir, and Mubarak Shah.  Ucf101: A dataset of 101 human actions classes from videos in the wild.  CoRR, 2012.
  * [39] Shaoqing Tan and Ruoyu Yang.  Learning similarity: Feature-aligning network for few-shot action recognition.  In Procedings of International Joint Conference on Neural Networks, pages 1–7, 2019.
  * [40] Sebastian Thrun and Lorien Pratt.  Learning to Learn.  2012\.
  * [41] Du Tran, Lubomir Bourdev, Rob Fergus, Lorenzo Torresani, and Manohar Paluri.  Learning spatiotemporal features with 3d convolutional networks.  In Proceedings of the 16th International Conference on Computer Vision, pages 4489–4497, 2015.
  * [42] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In Advances in Neural Information Processing Systems 30, pages 5998–6008. 2017.
  * [43] Cédric Villani.  Optimal Transport: Old and New.  2008\.
  * [44] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Koray Kavukcuoglu, and Daan Wierstra.  Matching networks for one shot learning.  In Advances in Neural Information Processing Systems 29, pages 3630–3638. 2016.
  * [45] Risto Vuorio, Shao-Hua Sun, Hexiang Hu, and Joseph J Lim.  Multimodal model-agnostic meta-learning via task-aware modulation.  In Advances in Neural Information Processing Systems 32, pages 1–12. 2019.
  * [46] Yu-Xiong Wang, Deva Ramanan, and Martial Hebert.  Meta-learning to detect rare objects.  In Proceedings of the 17th International Conference on Computer Vision, pages 9925–9934, 2019.
  * [47] Yongqin Xian, Bruno Korbar, Matthijs Douze, Bernt Schiele, Zeynep Akata, and Lorenzo Torresani.  Generalized many-way few-shot video classification.  CoRR, abs/2007.04755, 2020.
  * [48] Renjun Xu, Pelen Liu, Liyan Wang, Chao Chen, and Jindong Wang.  Reliable weighted optimal transport for unsupervised domain adaptation.  In Proceedings of the 33rd IEEE Conference on Computer Vision and Pattern Recognition, pages 4394–4403, 2020.
  * [49] Han-Jia Ye, Hexiang Hu, De-Chuan Zhan, and Fei Sha.  Few-shot learning via embedding adaptation with set-to-set functions.  In Proceedings of the 33rd IEEE Conference on Computer Vision and Pattern Recognition, pages 8808–8817, 2020.
  * [50] Chi Zhang, Yujun Cai, Guosheng Lin, and Chunhua Shen.  Deepemd: Few-shot image classification with differentiable earth mover’s distance and structured classifiers.  In Proceedings of the 33rd IEEE Conference on Computer Vision and Pattern Recognition, pages 12203–12213, 2020.
  * [51] Hongguang Zhang, Li Zhang, X Qui, Hongdong Li, Philip HS Torr, and Piotr Koniusz.  Few-shot action recognition with permutation-invariant attention.  In Proceedings of the 16th European Conference on Computer Vision, pages 525–542, 2020.
  * [52] Peng Zhao and Zhi-Hua Zhou.  Label distribution learning by optimal transport.  In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pages 4506–4513, 2018.
  * [53] Linchao Zhu and Yi Yang.  Compound memory networks for few-shot video classification.  In Proceedings of the 15th European Conference on Computer Vision, pages 751–766, 2018.
  * [54] Xiatian Zhu, Antoine Toisoul, Juan-Manuel Prez-Ra, Li Zhang, Brais Martinez, and Tao Xiang.  Few-shot action recognition with prototype-centered attentive learning.  CoRR, abs/2101.08085, 2021.


$x_{m}^{n}\coloneqq(x_{m},\cdots,x_{n})$, for $0\leq m\leq n$. For
$i\in\\{0,\cdots,n-1\\}$, we define

$\displaystyle
g_{i}(x_{0}^{i})\coloneqq\int_{\mathbb{X}^{n}}\sum_{l=0}^{n-1}f_{l}(x_{l})\prod_{j=i+1}^{n-1}P(x_{j-1},dx_{j})=\sum_{l=0}^{i}f_{l}(x_{l})+\sum_{l=i+1}^{n-1}\mathbb{E}_{x_{i}}[f_{l}(X_{l})],$
(81)

where $g_{n-1}(x_{0}^{n-1})=\sum_{l=0}^{n-1}f_{l}(x_{l})$ and
$f_{l}:\mathbb{X}\to[a_{i},b_{i}]$ belongs to $M_{l}\cdot\mathbf{F}$ with
bounded span. With this definition, we observe that

$\displaystyle
g_{n-1}(x_{0}^{n-1})=\sum_{i=1}^{n-1}\bigg{[}g_{i}(x_{0}^{i})-g_{i-1}(x_{0}^{i-1})\bigg{]}+g_{0}(x_{0}),$

and for $i\in\\{1,\cdots,n-1\\}$ and $x_{0}^{i-1}\in\mathbb{X}^{i}$,

$\displaystyle
g_{i-1}(x_{0}^{i-1})=\int_{\mathbb{X}^{i}}g_{i}(x_{0}^{i-1},x_{i})P(x_{i-1},dx_{i}).$

Let $\mathcal{F}_{i}=\sigma(X_{0},\cdots,X_{i})$, the above equation shows
that $g_{i-1}(X_{0}^{i-1})=\mathbb{E}[g_{i}(X_{0}^{i})|\mathcal{F}_{i-1}]$
$\mathbb{P}_{\mu}$-a.s. for $i\geq 1$. Thus,
$\\{g_{i}(X_{0}^{i})\\}_{i=0}^{n-1}$ is a $\mathbb{P}_{\mu}$-martingale
adapted to filtration $\\{\mathcal{F}_{i}\\}_{i=0}^{n-1}$ for initial
distribution $\mu\in\mathcal{P}(\mathcal{X})$. It follows the martingale
decomposition of $\tilde{S}_{n}$ centered at
$\sum_{i=0}^{n-1}\mathbb{E}_{\mu}[f_{i}(X_{i})]$,

$\displaystyle\tilde{S}_{n}-\sum_{i=0}^{n-1}\mathbb{E}_{\mu}[f_{i}(X_{i})]=g_{n-1}(X_{0}^{n-1})=\sum_{i=1}^{n-1}D_{i}+g_{0}(X_{0})-\sum_{i=0}^{n-1}\mathbb{E}_{\mu}[f_{i}(X_{i})],$

where
$\\{D_{i}\\}_{i=1}^{n-1}=\\{g_{i}(X_{0}^{i})-g_{i-1}(X_{0}^{i-1})\\}_{i=1}^{n-1}$
is a martingale difference sequence. We arrive at the Equation 80 after
canceling out the common terms.

The following lemma shows the span of the function $g_{i}$ defined in Equation
81.

######  Lemma 58.

Suppose the transition kernel $P$ with invariant probability $\pi$ satisfies
$\Gamma_{\mathbf{F}}<\infty$ (defined in Equation 5). For each
$i\in\\{0,\cdots,n-1\\}$, if we define

$\displaystyle A_{i}\coloneqq
2M_{i+1}^{\max}\Gamma_{\mathbf{F}}+\texttt{span}(f_{i}),$ (82)

where $M_{i}^{\max}=\max\\{M_{i},\cdots,M_{n-1}\\}$ for
$i\in\\{0,\cdots,n-1\\}$ and $M_{i}^{\max}=0$ for $i\geq n$, then it holds
that for $x_{0}^{i}\in\mathbb{X}^{i+1}$ and $x_{0}\in\mathbb{X}$,

$\displaystyle\inf_{x\in\mathbb{X}}g_{i}(x_{0}^{i-1},x)$ $\displaystyle\leq
g_{i}(x_{0}^{i})\leq\inf_{x\in\mathbb{X}}g_{i}(x_{0}^{i-1},x)+A_{i},$ (83)
$\displaystyle\inf_{x\in\mathbb{X}}g_{0}(x)$ $\displaystyle\leq
g_{0}(x_{0})\leq\inf_{x\in\mathbb{X}}g_{0}(x)+A_{0}.$ (84)

Proof:  It suffices to show Equation 83 holds. The first inequality is
obvious. To show the second inequality, we pick arbitrary $x^{*}\in\mathbb{X}$
and we have

$\displaystyle g_{i}(x_{0}^{i})$
$\displaystyle=\sum_{l=0}^{i}f_{l}(x_{l})+\sum_{l=i+1}^{n-1}\mathbb{E}_{x_{i}}f_{l}(x_{l})$
$\displaystyle\leq\sum_{l=0}^{i-1}f_{l}(x_{l})+f_{i}(x^{*})+\sum_{l=i+1}^{n-1}\mathbb{E}_{x_{i}}f_{l}(x_{l})+(b_{i}-a_{i}).$

Using Lemma 55, we can see that

$\displaystyle\sum_{l=i+1}^{n-1}\mathbb{E}_{x_{i}}f_{l}(x_{l})-\sum_{l=i+1}^{n-1}\mathbb{E}_{x^{*}}f_{l}(x_{l})\leq\sum_{l=i+1}^{n-1}M_{l}\textnormal{{IPM}}_{\mathbf{F}}(\delta_{x_{i}}P^{l-i},\delta_{x^{*}}P^{l-i}),$

where the right-hand side is bounded by
$2M_{i+1}^{\max}\Gamma_{\mathbf{F}}<\infty$. Thus, we have

$\displaystyle g_{i}(x_{0}^{i})\leq$
$\displaystyle\sum_{l=0}^{i-1}f_{l}(x_{l})+f_{i}(x^{*})+\sum_{l=i+1}^{n-1}\mathbb{E}_{x^{*}}f_{l}(x_{l})+\sum_{l=i+1}^{n-1}M_{l}\textnormal{{IPM}}_{\mathbf{F}}(\delta_{x_{i}}P^{l-i},\delta_{x^{*}}P^{l-i})+(b_{i}-a_{i})$
$\displaystyle\leq$ $\displaystyle
g_{i}(x_{0}^{i-1},x^{*})+2M_{i+1}^{\max}\Gamma_{\mathbf{F}}+(b_{i}-a_{i})$
$\displaystyle=$ $\displaystyle g_{i}(x_{0}^{i-1},x^{*})+A_{i}.$

Since $x^{*}$ is arbitrary, we obtain
$g_{i}(x_{0}^{i})\leq\inf_{x^{*}\in\mathbb{X}}g_{i}(x_{0}^{i-1},x^{*})+A_{i}$,
which completes the proof of Equation 83 and Equation 84 can be obtained in a
similar fashion.

Alternatively, we can bound the span of $g_{i}$ using IPM Dobrushin
coefficient for certain choices of generator listed in Proposition 18. This is
useful in the proof of Theorem 21.

######  Lemma 59.

Suppose the transition kernel $P$ with invariant probability $\pi$ satisfies
$\tilde{\Gamma}_{\mathbf{F}}<\infty$ (defined in Equation 9). Let $\mathbf{F}$
be one of the choices in Proposition 18. For each $i\in\\{0,\cdots,n-1\\}$, if
we define

$\displaystyle\tilde{A}_{i}\coloneqq
2\sum_{l=i}^{n-1}M_{l}\Delta_{\mathbf{F}}(P^{l-i})+\texttt{span}(f_{i}),$ (85)

for $i\in\\{0,\cdots,n-1\\}$, then it holds that for
$x_{0}^{i}\in\mathbb{X}^{i+1}$ and $x_{0}\in\mathbb{X}$,

$\displaystyle\inf_{x\in\mathbb{X}}g_{i}(x_{0}^{i-1},x)$ $\displaystyle\leq
g_{i}(x_{0}^{i})\leq\inf_{x\in\mathbb{X}}g_{i}(x_{0}^{i-1},x)+\tilde{A}_{i},$
(86) $\displaystyle\inf_{x\in\mathbb{X}}g_{0}(x)$ $\displaystyle\leq
g_{0}(x_{0})\leq\inf_{x\in\mathbb{X}}g_{0}(x)+\tilde{A}_{0}.$ (87)

Proof:  It suffices to show Equation 86 holds. The first inequality is
obvious. To show the second inequality, we pick arbitrary $x^{*}\in\mathbb{X}$
and we have

$\displaystyle g_{i}(x_{0}^{i})$
$\displaystyle=\sum_{l=0}^{i}f_{l}(x_{l})+\sum_{l=i+1}^{n-1}\mathbb{E}_{x_{i}}f_{l}(x_{l})$
$\displaystyle\leq\sum_{l=0}^{i-1}f_{l}(x_{l})+f_{i}(x^{*})+\sum_{l=i+1}^{n-1}\mathbb{E}_{x_{i}}f_{l}(x_{l})+(b_{i}-a_{i}).$

Using Lemma 55 and the nonexpansiveness of $P$ in
$\textnormal{{IPM}}_{\mathbf{F}}$, we can see that

$\displaystyle\sum_{l=i+1}^{n-1}\mathbb{E}_{x_{i}}f_{l}(x_{l})-\sum_{l=i+1}^{n-1}\mathbb{E}_{x^{*}}f_{l}(x_{l})$
$\displaystyle\leq\sum_{l=i+1}^{n-1}M_{l}\textnormal{{IPM}}_{\mathbf{F}}(\delta_{x_{i}}P^{l-i},\delta_{x^{*}}P^{l-i})$
$\displaystyle\leq\textnormal{{IPM}}_{\mathbf{F}}(\delta_{x_{i}},\delta_{x^{*}})\sum_{l=i+1}^{n-1}M_{l}\Delta_{\mathbf{F}}(P^{l-i}).$
(88)

Suppose $\mathbf{F}=\mathbb{B}_{L^{p}(\pi)}$ for $p\in[1,\infty]$, then we
have for $f\in\mathbb{B}_{L^{p}(\pi)}$ and $x,y\in\mathbb{X}$,

$\displaystyle\bigg{|}\int fd\delta_{x}-\int fd\delta_{y}\bigg{|}=|\int
f(\mathbbm{1}_{x}-\mathbbm{1}_{y})d\pi|\leq\|\mathbbm{1}_{x}-\mathbbm{1}_{y}\|_{L^{q}(\pi)}=2,$

where the last inequality comes from Hölder’s inequality and $q\in[1,\infty]$
is the conjugate of $p$. Thus,
$\textnormal{{IPM}}_{\mathbf{F}}(\delta_{x},\delta_{y})\leq 2$ for any
$x,y\in\mathbb{X}$. As for $\mathbf{F}=\mathbb{B}_{\|\cdot\|_{\infty}}$, it is
easy to deduce that $|\int fd\delta_{x}-\int fd\delta_{y}|\leq
2\|f\|_{\infty}\leq 2$ for any $x,y\in\mathbb{X}$. Therefore, the right-hand
side of Equation A is bounded by
$2\sum_{l=i+1}^{n-1}M_{l}\Delta_{\mathbf{F}}(P^{l-i})\leq
2M^{\max}_{i+1}\tilde{\Gamma}_{\mathbf{F}}(P)<\infty$. We can now go back to
bound $g_{i}(x_{0}^{i})$ as

$\displaystyle g_{i}(x_{0}^{i})\leq$
$\displaystyle\sum_{l=0}^{i-1}f_{l}(x_{l})+f_{i}(x^{*})+\sum_{l=i+1}^{n-1}\mathbb{E}_{x^{*}}f_{l}(x_{l})+2\sum_{l=i+1}^{n-1}M_{l}\Delta_{\mathbf{F}}(P^{l-i})+(b_{i}-a_{i})$
$\displaystyle\leq$ $\displaystyle
g_{i}(x_{0}^{i-1},x^{*})+2\sum_{l=i+1}^{n-1}M_{l}\Delta_{\mathbf{F}}(P^{l-i})+\texttt{span}(f_{i})$
$\displaystyle=$ $\displaystyle g_{i}(x_{0}^{i-1},x^{*})+\tilde{A}_{i}.$

Since $x^{*}$ is arbitrary, we obtain
$g_{i}(x_{0}^{i})\leq\inf_{x^{*}\in\mathbb{X}}g_{i}(x_{0}^{i-1},x^{*})+\tilde{A}_{i}$,
which completes the proof of Equation 86 and Equation 87 can be obtained in a
similar fashion.

###  A.1 Proof of Theorem 9

Proof:  By Lemma 57, we have the martingale decomposition of $\mathbf{X}$ as
in Equation 80,

$\displaystyle\tilde{S}_{n}-\mathbb{E}_{\mu}[\tilde{S}_{n}]=\sum_{i=0}^{n-1}D_{i},$

where we abuse the notation and denote
$D_{0}=f_{0}(X_{0})-\mathbb{E}_{\mu}[f_{0}]$. One can use Chernoff’s bounding
method (Chernoff, 1952) to obtain an exponential bound on the desired
quantity. Taking the moment generating function on both sides of Equation 80
and applying the chain rule for conditional expectation recursively yield,

$\displaystyle\mathbb{E}_{\mu}\bigg{[}\exp\bigg{(}\theta\bigg{(}\tilde{S}_{n}-\sum_{i=0}^{n-1}\mathbb{E}_{\mu}[f_{i}(X_{i})]\bigg{)}\bigg{)}\bigg{]}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\mu}\bigg{[}\exp\bigg{(}\theta\sum_{i=0}^{n-1}D_{i}\bigg{)}\bigg{]}=\mathbb{E}_{\mu}[\exp(\theta
D_{0})]\prod_{i=1}^{n-1}\mathbb{E}_{\mu}[\exp(\theta
D_{i})|\mathcal{F}_{i-1}],$ (89)

for $\theta\geq 0$.

From lemma 58, we know that $D_{i}=g_{i}(X_{0}^{i})-g_{i-1}(X_{0}^{i-1})$ lies
in an interval of length $A_{i}$ for all $i\in\\{0,\cdots,n-1\\}$. By
Hoeffding’s Lemma (Douc et al., 2018, Lemma 23.1.4) for bounded martingale
difference sequences, we have for $\theta\geq 0$,

$\displaystyle\mathbb{E}_{\mu}[\exp(\theta
D_{0})]\leq\exp(\theta^{2}A_{0}^{2}/8),$
$\displaystyle\quad\mathbb{E}_{\mu}[\exp(\theta
D_{i})|\mathcal{F}_{i-1}]\leq\exp(\theta^{2}A_{l}^{2}/8),$

and plugging above into Equation A.1 yields

$\displaystyle\mathbb{E}_{\mu}\bigg{[}\exp\bigg{(}\theta\bigg{(}\tilde{S}_{n}-\sum_{i=0}^{n-1}\mathbb{E}_{\mu}[f_{i}(X_{i})]\bigg{)}\bigg{)}\bigg{]}$
$\displaystyle\leq\exp\bigg{(}\frac{\theta^{2}}{8}\sum_{i=0}^{n-1}A_{i}^{2}\bigg{)}.$

Applying Markov’s inequality to the left-hand side, we have

$\displaystyle\mathbb{P}_{\mu}\bigg{[}\bigg{(}\tilde{S}_{n}-\sum_{i=0}^{n-1}\mathbb{E}_{\mu}[f_{i}(X_{i})]\bigg{)}>n\epsilon\bigg{]}$
$\displaystyle\leq\exp(-n\epsilon\theta)\mathbb{E}_{\mu}\bigg{[}\exp\bigg{(}\theta\bigg{(}\tilde{S}_{n}-\sum_{i=0}^{n-1}\mathbb{E}_{\mu}[f_{i}(X_{i})]\bigg{)}\bigg{)}\bigg{]}$
$\displaystyle\leq\exp\bigg{(}-n\epsilon\theta+\frac{\theta^{2}}{8}\sum_{i=0}^{n-1}A_{i}^{2}\bigg{)}.$

Picking $\theta=4n\epsilon/\sum_{i=0}^{n-1}A_{i}^{2}$ minimizes the right-hand
side and yields

$\displaystyle\mathbb{P}_{\mu}\bigg{[}\bigg{(}\tilde{S}_{n}-\sum_{i=0}^{n-1}\mathbb{E}_{\mu}[f_{i}(X_{i})]\bigg{)}>n\epsilon\bigg{]}\leq\exp\bigg{(}-\frac{2n^{2}\epsilon^{2}}{\sum_{i=0}^{n-1}A_{i}^{2}}\bigg{)}.$

The tail probability of the other side can be bounded in an analogous fashion.
Therefore, we have

$\displaystyle\mathbb{P}_{\mu}\bigg{[}\bigg{|}\tilde{S}_{n}-\sum_{i=0}^{n-1}\mathbb{E}_{\mu}[f_{i}(X_{i})]\bigg{|}>n\epsilon\bigg{]}\leq
2\exp\bigg{(}-\frac{2n^{2}\epsilon^{2}}{\sum_{i=0}^{n-1}A_{i}^{2}}\bigg{)}.$
(90)

To consider the following tail probability of $\tilde{S}_{n}$ centered around
$\sum_{i=0}^{n-1}\pi(f_{i})$, we apply Lemma 56 to $(a)$ and Equation 90 to
$(b)$ and obtain

$\displaystyle\mathbb{P}_{\mu}\bigg{[}\bigg{|}\tilde{S}_{n}-\sum_{i=0}^{n-1}\pi(f_{i})\bigg{|}>n\epsilon\bigg{]}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{P}_{\mu}\bigg{[}\bigg{|}\tilde{S}_{n}-\sum_{i=0}^{n-1}\mathbb{E}_{\mu}[f_{i}(X_{i})]\bigg{|}+\sum_{i=0}^{n-1}M_{i}\textnormal{{IPM}}_{\mathbf{F}}(\mu
P^{i},\pi)>n\epsilon\bigg{]}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}2\exp\bigg{(}-\frac{2[n\epsilon-
A_{0}]^{2}}{\sum_{i=0}^{n-1}A_{i}^{2}}\bigg{)},$

for $\epsilon\geq n^{-1}\textnormal{{IPM}}_{\mathbf{F}}(\mu,\pi)A_{0}$, which
yields the desired result in Equation 6 after expanding $A_{i}$ with Equation
82.

###  A.2 Proof of Theorem 21

Proof:  The overall procedure follows the proof in Appendix A.2 with the
exception where Lemma 58 is replaced by Lemma 59. Thus, $D_{i}$ lies in a
interval of length $\tilde{A}_{i}$ for all $i\in\\{1,...,n-1\\}$. The rest is
the same after replacing $A_{i}$ with $\tilde{A}_{i}$.

## References

  * Adler and Lunz (2018) Jonas Adler and Sebastian Lunz.  Banach Wasserstein GAN.  _Advances in neural information processing systems_ , 31, 2018.
  * Agarwal and Duchi (2012) Alekh Agarwal and John C Duchi.  The generalization ability of online algorithms for dependent data.  _IEEE Transactions on Information Theory_ , 59(1):573–587, 2012.
  * Alquier and Wintenberger (2012) Pierre Alquier and Olivier Wintenberger.  Model selection for weakly dependent time series forecasting.  _Bernoulli_ , 18(3):883–913, 2012.
  * Anantharam et al. (1987) Venkatachalam Anantharam, Pravin Varaiya, and Jean Walrand.  Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-part ii: Markovian rewards.  _IEEE Transactions on Automatic Control_ , 32(11):977–982, 1987.
  * Arbel et al. (2018) Michael Arbel, Danica J Sutherland, Mikołaj Bińkowski, and Arthur Gretton.  On gradient regularizers for MMD GANs.  _Advances in neural information processing systems_ , 31, 2018.
  * Arjovsky et al. (2017) Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein generative adversarial networks.  In _International conference on machine learning_ , pages 214–223. PMLR, 2017.
  * Arlot et al. (2019) Sylvain Arlot, Alain Celisse, and Zaid Harchaoui.  A kernel multiple change-point algorithm via model selection.  _Journal of machine learning research_ , 20(162), 2019.
  * Aronszajn (1950) Nachman Aronszajn.  Theory of reproducing kernels.  _Transactions of the American mathematical society_ , 68(3):337–404, 1950.
  * Azuma (1967) Kazuoki Azuma.  Weighted sums of certain dependent random variables.  _Tohoku Mathematical Journal, Second Series_ , 19(3):357–367, 1967.
  * Bach (2014) Francis Bach.  Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression.  _The Journal of Machine Learning Research_ , 15(1):595–627, 2014.
  * Bach and Moulines (2013) Francis Bach and Eric Moulines.  Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n).  _Advances in neural information processing systems_ , 26, 2013.
  * Bellemare et al. (2017) Marc G Bellemare, Ivo Danihelka, Will Dabney, Shakir Mohamed, Balaji Lakshminarayanan, Stephan Hoyer, and Rémi Munos.  The Cramer distance as a solution to biased Wasserstein gradients.  _arXiv preprint arXiv:1705.10743_ , 2017.
  * Billingsley (2013) Patrick Billingsley.  _Convergence of probability measures_.  John Wiley & Sons, 2013.
  * Bińkowski et al. (2018) Mikołaj Bińkowski, Danica J Sutherland, Michael Arbel, and Arthur Gretton.  Demystifying MMD GANs.  In _International Conference on Learning Representations_ , 2018.
  * Blanchet and Murthy (2019) Jose Blanchet and Karthyek Murthy.  Quantifying distributional model risk via optimal transport.  _Mathematics of Operations Research_ , 44(2):565–600, 2019.
  * Boucheron et al. (2013) Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  _Concentration inequalities: A nonasymptotic theory of independence_.  Oxford university press, 2013.
  * Breiman (1960) Leo Breiman.  The strong law of large numbers for a class of Markov chains.  _The Annals of Mathematical Statistics_ , 31(3):801–803, 1960.
  * Brockman et al. (2016) Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  Openai gym.  _arXiv preprint arXiv:1606.01540_ , 2016.
  * Butkovsky (2014) Oleg Butkovsky.  Subgeometric rates of convergence of Markov processes in the Wasserstein metric.  _The Annals of Applied Probability_ , 24(2):526–552, 2014.
  * Chen et al. (2022) Hao Chen, Jiacheng Tang, and Abhishek Gupta.  Change detection of Markov kernels with unknown pre and post change kernel.  In _2022 IEEE 61st Conference on Decision and Control (CDC)_ , pages 4814–4820, 2022.  doi: 10.1109/CDC51059.2022.9992982.
  * Chernoff (1952) Herman Chernoff.  A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.  _The Annals of Mathematical Statistics_ , pages 493–507, 1952.
  * Czapla et al. (2024) Dawid Czapla, Katarzyna Horbacz, and Hanna Wojewódka-Ściążko.  The central limit theorem for Markov processes that are exponentially ergodic in the bounded-lipschitz norm.  _Qualitative Theory of Dynamical Systems_ , 23(1):1–46, 2024.
  * Davisson et al. (1981) L Davisson, Giuseppe Longo, and Andrea Sgarro.  The error exponent for the noiseless encoding of finite ergodic Markov sources.  _IEEE Transactions on Information Theory_ , 27(4):431–438, 1981.
  * Del Moral et al. (2003) Pierre Del Moral, Michel Ledoux, and Laurent Miclo.  On contraction properties of Markov kernels.  _Probability theory and related fields_ , 126(3):395–420, 2003.
  * Devroye et al. (2013) Luc Devroye, László Györfi, and Gábor Lugosi.  _A probabilistic theory of pattern recognition_ , volume 31.  Springer Science & Business Media, 2013.
  * Diaconis and Freedman (1999) Persi Diaconis and David Freedman.  Iterated random functions.  _SIAM review_ , 41(1):45–76, 1999.
  * Dieuleveut et al. (2017) Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach.  Harder, better, faster, stronger convergence rates for least-squares regression.  _The Journal of Machine Learning Research_ , 18(1):3520–3570, 2017.
  * Dobrushin (1956) Roland L Dobrushin.  Central limit theorem for nonstationary Markov chains. ii.  _Theory of Probability & Its Applications_, 1(4):329–383, 1956.
  * Douc et al. (2011) Randal Douc, Eric Moulines, Jimmy Olsson, and Ramon Van Handel.  Consistency of the maximum likelihood estimator for general hidden Markov models.  _the Annals of Statistics_ , 39(1):474–513, 2011\.
  * Douc et al. (2018) Randal Douc, Eric Moulines, Pierre Priouret, and Philippe Soulier.  _Markov chains_.  Springer, 2018.
  * Dudley (2018) Richard M Dudley.  _Real analysis and probability_.  CRC Press, 2018.
  * Dziugaite et al. (2015) Gintare Karolina Dziugaite, Daniel M Roy, and Zoubin Ghahramani.  Training generative neural networks via maximum mean discrepancy optimization.  In _Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence_ , pages 258–267, 2015.
  * Edwards (2011) David A Edwards.  On the Kantorovich–Rubinstein theorem.  _Expositiones Mathematicae_ , 29(4):387–398, 2011\.
  * Fan et al. (2021) Jianqing Fan, Bai Jiang, and Qiang Sun.  Hoeffding’s inequality for general Markov chains and its applications to statistical learning.  _J. Mach. Learn. Res._ , 22:139–1, 2021.
  * Flynn and Yoo (2019) Thomas Flynn and Shinjae Yoo.  Change detection with the kernel cumulative sum algorithm.  In _2019 IEEE 58th Conference on Decision and Control (CDC)_ , pages 6092–6099. IEEE, 2019.
  * Gao and Kleywegt (2023) Rui Gao and Anton Kleywegt.  Distributionally robust stochastic optimization with Wasserstein distance.  _Mathematics of Operations Research_ , 48(2):603–655, 2023.
  * Gao et al. (2022) Rui Gao, Xi Chen, and Anton J Kleywegt.  Wasserstein distributionally robust optimization and variation regularization.  _Operations Research_ , 2022.
  * Gibbs and Su (2002) Alison L Gibbs and Francis Edward Su.  On choosing and bounding probability metrics.  _International statistical review_ , 70(3):419–435, 2002.
  * Glynn and Ormoneit (2002) Peter W Glynn and Dirk Ormoneit.  Hoeffding’s inequality for uniformly ergodic Markov chains.  _Statistics & probability letters_, 56(2):143–146, 2002.
  * Goodfellow et al. (2020) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial networks.  _Communications of the ACM_ , 63(11):139–144, 2020.
  * Granas and Dugundji (2003) Andrzej Granas and James Dugundji.  _Fixed point theory_ , volume 14.  Springer, 2003.
  * Gretton et al. (2006) Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alex Smola.  A kernel method for the two-sample-problem.  _Advances in neural information processing systems_ , 19, 2006.
  * Gretton et al. (2012) Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola.  A kernel two-sample test.  _The Journal of Machine Learning Research_ , 13(1):723–773, 2012.
  * Gulrajani et al. (2017) Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville.  Improved training of Wasserstein GANs.  _Advances in neural information processing systems_ , 30, 2017.
  * Gupta et al. (2018) Abhishek Gupta, Rahul Jain, and Peter Glynn.  Probabilistic contraction analysis of iterated random operators.  _arXiv preprint arXiv:1804.01195_ , 2018.
  * Gupta et al. (2020) Abhishek Gupta, Hao Chen, Jianzong Pi, and Gaurav Tendolkar.  Some limit properties of Markov chains induced by recursive stochastic algorithms.  _SIAM Journal on Mathematics of Data Science_ , 2(4):967–1003, 2020.
  * Hairer et al. (2011) Martin Hairer, Jonathan C Mattingly, and Michael Scheutzow.  Asymptotic coupling and a general form of Harris’ theorem with applications to stochastic delay equations.  _Probability theory and related fields_ , 149:223–259, 2011\.
  * Han et al. (2023) Jiequn Han, Ruimeng Hu, and Jihao Long.  A class of dimension-free metrics for the convergence of empirical measures.  _Stochastic Processes and their Applications_ , 164:242–287, 2023.
  * Hille and Theewis (2022) Sander C Hille and Esmee S Theewis.  Explicit expressions and computational methods for the Fortet-Mourier distance to finite weighted sums of Dirac measures.  _arXiv preprint arXiv:2206.12234_ , 2022.
  * Hoeffding (1994) Wassily Hoeffding.  Probability inequalities for sums of bounded random variables.  In _The collected works of Wassily Hoeffding_ , pages 409–426. Springer, 1994.
  * Hu and Hong (2013) Zhaolin Hu and L Jeff Hong.  Kullback-Leibler divergence constrained distributionally robust optimization.  _Available at Optimization Online_ , 1(2):9, 2013\.
  * Husain (2020) Hisham Husain.  Distributional robustness with IPMs and links to regularization and GANs.  _Advances in Neural Information Processing Systems_ , 33:11816–11827, 2020.
  * Kim et al. (2022) Dongha Kim, Kunwoong Kim, Insung Kong, Ilsang Ohn, and Yongdai Kim.  Learning fair representation with a parametric integral probability metric.  In _International Conference on Machine Learning_ , pages 11074–11101. PMLR, 2022.
  * Li et al. (2017) Chun-Liang Li, Wei-Cheng Chang, Yu Cheng, Yiming Yang, and Barnabás Póczos.  MMD GAN: Towards deeper understanding of moment matching network.  _Advances in neural information processing systems_ , 30, 2017.
  * Li et al. (2015) Shuang Li, Yao Xie, Hanjun Dai, and Le Song.  M-statistic for kernel change-point detection.  _Advances in Neural Information Processing Systems_ , 28, 2015.
  * Lin et al. (2022) Fengming Lin, Xiaolei Fang, and Zheming Gao.  Distributionally robust optimization: A review on theory and applications.  _Numerical Algebra, Control and Optimization_ , 12(1):159–212, 2022.
  * Liu and Wang (2018) Jin-Guo Liu and Lei Wang.  Differentiable learning of quantum circuit Born machines.  _Phys. Rev. A_ , 98:062324, Dec 2018.  doi: 10.1103/PhysRevA.98.062324.  URL https://link.aps.org/doi/10.1103/PhysRevA.98.062324.
  * Liu and Liu (2021) Yuanyuan Liu and Jinpeng Liu.  Hoeffding’s inequality for Markov processes via solution of Poisson’s equation.  _Frontiers of Mathematics in China_ , 16(2):543–558, 2021.
  * Meyn and Tweedie (2012) Sean P Meyn and Richard L Tweedie.  _Markov chains and stochastic stability_.  Springer Science & Business Media, 2012.
  * Miasojedow (2014) Błażej Miasojedow.  Hoeffding’s inequalities for geometrically ergodic Markov chains on general state space.  _Statistics & Probability Letters_, 87:115–120, 2014\.
  * Mohajerin Esfahani and Kuhn (2018) Peyman Mohajerin Esfahani and Daniel Kuhn.  Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations.  _Mathematical Programming_ , 171(1-2):115–166, 2018.
  * Moulos (2020) Vrettos Moulos.  A Hoeffding inequality for finite state Markov chains and its applications to markovian bandits.  In _2020 IEEE International Symposium on Information Theory (ISIT)_ , pages 2777–2782. IEEE, 2020.
  * Moulos and Anantharam (2019) Vrettos Moulos and Venkat Anantharam.  Optimal Chernoff and Hoeffding bounds for finite state Markov chains.  _arXiv preprint arXiv:1907.04467_ , 2019.
  * Moustakides (1999) George V Moustakides.  Extension of Wald’s first lemma to Markov processes.  _Journal of applied probability_ , 36(1):48–59, 1999.
  * Mroueh and Sercu (2017) Youssef Mroueh and Tom Sercu.  Fisher GAN.  _Advances in neural information processing systems_ , 30, 2017.
  * Mroueh et al. (2018) Youssef Mroueh, Chun Liang Li, Tom Sercu, Anant Raj, and Yu Cheng.  Sobolev GAN.  In _International Conference on Learning Representations_. International Conference on Learning Representations, ICLR, 2018.
  * Müller (1997) Alfred Müller.  Integral probability metrics and their generating classes of functions.  _Advances in Applied Probability_ , 29(2):429–443, 1997.
  * Nemirovski et al. (2009) Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro.  Robust stochastic approximation approach to stochastic programming.  _SIAM Journal on optimization_ , 19(4):1574–1609, 2009.
  * Nowozin et al. (2016) Sebastian Nowozin, Botond Cseke, and Ryota Tomioka.  f-GAN: Training generative neural samplers using variational divergence minimization.  _Advances in neural information processing systems_ , 29, 2016.
  * Polyak and Juditsky (1992) Boris T Polyak and Anatoli B Juditsky.  Acceleration of stochastic approximation by averaging.  _SIAM journal on control and optimization_ , 30(4):838–855, 1992.
  * Rahimian and Mehrotra (2019) Hamed Rahimian and Sanjay Mehrotra.  Distributionally robust optimization: A review.  _arXiv preprint arXiv:1908.05659_ , 2019.
  * Rudolf and Schweizer (2018) Daniel Rudolf and Nikolaus Schweizer.  Perturbation theory for Markov chains via Wasserstein distance.  _Bernoulli_ , 24(4A):2610–2639, 2018.
  * Ruppert (1988) David Ruppert.  Efficient estimations from a slowly convergent Robbins-Monro process.  Technical report, Cornell University Operations Research and Industrial Engineering, 1988.
  * Sandrić and Šebek (2023) Nikola Sandrić and Stjepan Šebek.  Hoeffding’s inequality for non-irreducible Markov models.  _Statistics & Probability Letters_, 200:109870, 2023.  ISSN 0167-7152.  doi: https://doi.org/10.1016/j.spl.2023.109870.  URL https://www.sciencedirect.com/science/article/pii/S0167715223000949.
  * Shorack and Shorack (2000) Galen R Shorack and GR Shorack.  _Probability for statisticians_ , volume 951.  Springer, 2000.
  * Sriperumbudur et al. (2010a) Bharath K Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert RG Lanckriet.  Non-parametric estimation of integral probability metrics.  In _2010 IEEE International Symposium on Information Theory_ , pages 1428–1432. IEEE, 2010a.
  * Sriperumbudur et al. (2010b) Bharath K Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Bernhard Schölkopf, and Gert RG Lanckriet.  Hilbert space embeddings and metrics on probability measures.  _The Journal of Machine Learning Research_ , 11:1517–1561, 2010b.
  * Sriperumbudur et al. (2012) Bharath K Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert RG Lanckriet.  On the empirical estimation of integral probability metrics.  _Electronic Journal of Statistics_ , 6:1550–1599, 2012\.
  * Staib and Jegelka (2019) Matthew Staib and Stefanie Jegelka.  Distributionally robust optimization and generalization in kernel methods.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Tekin and Liu (2012) Cem Tekin and Mingyan Liu.  Online learning of rested and restless bandits.  _IEEE Transactions on Information Theory_ , 58(8):5588–5611, 2012.
  * Watanabe and Hayashi (2017) Shun Watanabe and Masahito Hayashi.  Finite-length analysis on tail probability for Markov chain and application to simple hypothesis testing.  _The Annals of Applied Probability_ , 27(2):811 – 845, 2017.  doi: 10.1214/16-AAP1216.  URL https://doi.org/10.1214/16-AAP1216.
  * Xu (2021) Minkai Xu.  Towards generalized implementation of Wasserstein distance in GANs.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(12):10514–10522, 2021.
  * Yu (1994) Bin Yu.  Rates of convergence for empirical processes of stationary mixing sequences.  _The Annals of Probability_ , pages 94–116, 1994.
  * Zhu et al. (2021) Jia-Jie Zhu, Wittawat Jitkrittum, Moritz Diehl, and Bernhard Schölkopf.  Kernel distributionally robust optimization: Generalized duality theorem and stochastic approximation.  In _International Conference on Artificial Intelligence and Statistics_ , pages 280–288. PMLR, 2021.
  * Zolotarev (1984) Vladimir Mikhailovich Zolotarev.  Probability metrics.  _Theory of Probability & Its Applications_, 28(2):278–302, 1984.
  * Zou et al. (2009) Bin Zou, Luoqing Li, and Zongben Xu.  The generalization performance of ERM algorithm with strongly mixing observations.  _Machine learning_ , 75(3):275–295, 2009.