Adaptive Estimation for
Approximate $k$-Nearest-Neighbor Computations

Daniel LeJeune Richard G. Baraniuk Reinhard Heckel

Rice University Rice University Rice University

###### Abstract

Algorithms often carry out equally many computations for “easy” and “hard”
problem instances. In particular, algorithms for finding nearest neighbors
typically have the same running time regardless of the particular problem
instance. In this paper, we consider the approximate $k$-nearest-neighbor
problem, which is the problem of finding a subset of $O(k)$ points in a given
set of points that contains the set of $k$ nearest neighbors of a given query
point. We propose an algorithm based on adaptively estimating the distances,
and show that it is essentially optimal out of algorithms that are only
allowed to adaptively estimate distances. We then demonstrate both
theoretically and experimentally that the algorithm can achieve significant
speedups relative to the naïve method.

##  1 INTRODUCTION

A large number of algorithms in machine learning and signal processing are
based on distance computations. The algorithms for solving the associated
computational problems are typically designed to perform well on a set of
problem instances, in a worst-case or average-case sense, but do not
necessarily have optimal or close-to-optimal computational complexity on any
given problem instance. As a consequence, these algorithms often have running
times and guarantees that are the same for “easy” and “hard” problems.

Ideally, we would like an algorithm that adapts to any given problem instance
and only carries out the computations necessary for that problem instance. In
this paper, we consider an approach for speeding up algorithms and evaluating
their complexity that is based on adapting to a given problem instance with
random adaptive sampling techniques (Bagaria et al., 2018a, b). This approach
is applicable to a variety of algorithms that are based on distance
computations. Adding such adaptivity to algorithms can significantly speed up
the algorithms’ running times, since computationally easy problems have
accordingly smaller running times.

For concreteness, we focus on the problem of _approximate_ _$k$ -nearest-
neighbor_ ($k$-NN) computation. Specifically, given a query point $\mathbf{x}$
and a set of $n$ points, $\mathcal{X}$, our goal is to find a subset
containing the $k$ nearest neighbors of the query point. Our intuition is that
an “easy” $k$-NN problem instance is one where there is a set of at least $k$
points that are close to the query point, and the other points are rather far,
such that the evaluation of only a few coordinate-wise distances of the far
points is sufficient to know that they are farther away than the close points.
Contrarily, a “hard” problem instance is one where the distance from
$\mathbf{x}$ to all other points is very similar, and thus it is difficult to
find a subset of $k$ nearest neighbors.

We note that other formulations of the approximate $k$-NN problem are common
as well. For example, Andoni and Indyk (2006) consider a formulation where
points can be returned whose distance from the query point is within a
multiplicative factor to its nearest points.

We propose an algorithm, which we call the _adaptive $k$-NN algorithm_, that
adaptively estimates the distances and exploits the fact that for finding a
set containing the $k$ nearest neighbors, it is not necessary to compute all
distances exactly. In particular, for easy problem instances, coarse estimates
are sufficient to identify a subset containing the $k$ nearest neighbors.
Contrary to previous approaches, in particular that of Bagaria et al. (2018b),
we focus on identifying a set _containing_ the $k$ nearest neighbors, since
this is computationally considerably cheaper than identifying the _exact_ set
of $k$ nearest neighbors.

We prove that the adaptive $k$-NN algorithm is _near instance-optimal_ for a
restricted class of problems in the class of randomized algorithms that are
based on adaptively estimating the distances. In a nutshell, the proof
strategy is as follows: guaranteeing a solution to a given computational
problem based on estimated distances (say, $k$-NNs) requires sufficiently good
estimates of the distances. With standard change of measure techniques
(Kaufmann et al., 2016) we can derive instance-dependent lower bounds on the
sample complexity required to obtain sufficiently good estimates. This sample
complexity is also a lower bound on the computational complexity of the
respective algorithm, since at the very least the distances have to be
computed sufficiently well to be sure a subset of the $k$ nearest neighbors
can be identified with high probability. Further, we show that this
computational complexity can also be achieved by designing an approximate
$k$-NN algorithm that estimates the distances adaptively in time almost linear
in the sample complexity.

##  2 RELATED WORK ON $k$-NN

There are many highly efficient algorithms that solve versions of the
(approximate) $k$-NN problem. If the dimension of the data points is low, then
the k-d tree algorithm (Bentley, 1975) performs very well. This algorithm
builds a balanced k-d tree and traverses the tree to find the nearest
neighbors. Contrary to our approach, the algorithm is based on pre-processing
the data and thus becomes efficient only when performing many queries, so that
the cost of building the tree becomes negligible. In addition, k-d trees
become inefficient in high dimensions.

In order to overcome complexity in high dimensions, a number of works have
proposed to find solutions that are approximate in that the algorithm is only
asked to return points that are close in distance to the true nearest
neighbors, for example, by using random projections (Ailon and Chazelle,
2006). Perhaps the most popular class of algorithms for performing approximate
nearest-neighbor search is based on locality sensitive hashing (Andoni and
Indyk, 2006). This class of algorithms works very well in theory and practice,
but again uses a pre-processing step that is not negligible if only one query
is executed.

If many $k$-NN queries are carried out on the same dataset, then the k-d
algorithm for small dimensions and locality sensitive hashing algorithms for
higher dimensions are significantly more efficient than algorithms based on
adaptively estimating scores, such as the algorithm proposed here, since then
the amortized pre-processing costs become negligible. In contrast, our
approach is efficient in high dimensions and when we only carry out one or
very few queries.

A setting particularly relevant to our approach is that in which the dataset
is rapidly changing, where the assumption of other $k$-NN algorithms that pre-
processing costs become negligible over time no longer holds. One such example
is in the Impicit Maximum Likelihood Estimation procedure by Li and Malik
(2018), where at each iteration nearest-neighbor queries must be performed
against a set of samples from the new estimate of the distribution.

There are a few recent success stories where adaptive randomized algorithms
significantly speed up computational problems: the Monte-Carlo tree search
method for decision processes (Kocsis and Szepesvári, 2006), hyperparameter
optimization in machine learning (Li et al., 2018), finding the medoid in a
large collection of high-dimensional points (Bagaria et al., 2018a), and
solving discrete optimization problems involving distance computations
adaptively (Bagaria et al., 2018b). All four works apply standard bandit
algorithms in a creative way. Most related to our work is that of Bagaria et
al. (2018b), which proposes an efficient algorithms for solving the $k$-NN
problem using an adaptive sampling strategy, similar to the one proposed here.
The main difference is that we consider the approximate $k$-NN problem, which
is a more general problem that contains the problem of finding the exact
$k$-NN as a special case. In order to solve the approximate $k$-NN problem, we
have to solve a non-standard approximate bandit problem. In addition, we
provide an algorithm that is _near instance-optimal_ in the class of
algorithms that _estimate_ the distances for a restricted class of possible
data points.

##  3 PROBLEM STATEMENT

Suppose we are given a set of high-dimensional points

$\mathcal{X}=\\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\\}\subset\mathbb{R}^{m},$

and our goal is to find, for another given point
$\mathbf{x}\in\mathbb{R}^{m}$, a set of size $O(k)$ that includes the $k$
nearest neighbors of $\mathbf{x}$ to $\mathcal{X}$ in $\ell_{2}$-distance (our
results and discussion generalize to other distances, such as the
$\ell_{1}$-distance). This is a generalization of the exact $k$-nearest-
neighbor problem and has applications in a vast number of classification tasks
(Hastie et al., 2009).

For convenience, we assume that all points are normalized such that
$\|\mathbf{x}\|_{\infty}\leq 1/2$, where
${\left\|\mathbf{x}\right\|}_{\infty}$ denotes the largest absolute value of
the vector $\mathbf{x}$. We can brute-force solve the problem by computing all
distances and then sorting, which yields a worst case complexity of
$O(mn+n\log n)$. Our intuition is that it is unnecessary to compute the
distances exactly, and that by approximating the distances we can save
computations.

##  4 THE ADAPTIVE $k$-NN ALGORITHM

The idea behind our _adaptive $k$-NN algorithm_ is to adaptively estimate the
distances. Then, the problem of finding a superset containing the $k$ nearest
neighbors reduces to a _multi-armed bandit_ problem with the goal of
identifying a set of size $k+h$ containing the $k$ smallest arms. Using
that—up to a logarithmic factor—the sample complexity of the corresponding
algorithm is equal to the computational complexity, we can provide an upper
bound on the computational complexity of the algorithm by proving an upper
bound on the sample complexity. Likewise, we can prove a lower bound for all
algorithms that use adaptive estimates of the distances.

Our algorithm is inspired by the Hamming-LUCB algorithm in (Heckel et al.,
2018) which in turn builds on the Lower-Upper Confidence Bound (LUCB)
strategy, a popular algorithm for identifying the top-k items in a bandit
problem (Kalyanakrishnan et al., 2012) and for ranking from pairwise
comparisons (Heckel et al., 2019). The algorithm is based on actively
identifying sets $\widehat{\mathcal{S}}_{\text{close}}$ and
$\widehat{\mathcal{S}}_{\text{far}}$ consisting of $k$ and $n-k-h$ points,
respectively, such that with high confidence the points in the first set have
a smaller distance to $\mathbf{x}$ than the points in the second set. Once we
have found such sets, the set

$\widehat{\mathcal{S}}=\\{1,\ldots,n\\}\setminus\widehat{\mathcal{S}}_{\text{far}}$

contains the closest $k$ points. Note that the cardinality of
$\widehat{\mathcal{S}}$ is $k+h$, so to obtain a set of cardinality $O(k)$
conaining the $k$ nearest neighbors, we choose $h$ on the order of $k$. We
adaptively estimate the normalized squared distances

$d_{i}=\frac{1}{m}{\left\|\mathbf{x}-\mathbf{x}_{i}\right\|}_{2}^{2}$

by sampling indices $j_{1},\ldots,j_{T_{i}}$ uniformly at
random111Alternatively, one could select $j_{1},\ldots,j_{m}$ uniformly at
random without replacement, in which case $\widehat{d}_{i}(m)=d_{i}$ exactly.
This could be implemented efficiently using ciphers, such as those described
by Black and Rogaway (2002). from all indices $\\{1,\ldots,m\\}$ and then
estimating the squared distance as

$\widehat{d}_{i}(T_{i})=\frac{1}{T_{i}}\sum_{j\in\\{j_{1},\ldots,j_{T_{i}}\\}}|[\mathbf{x}_{i}]_{j}-[\mathbf{x}]_{j}|^{2},$

where $[\mathbf{x}]_{j}$ denotes the $j$-th coordinate of $\mathbf{x}$. The
key idea is to estimate the distances only sufficiently well as to be able to
obtain the two sets $\widehat{\mathcal{S}}_{\text{close}}$ and
$\widehat{\mathcal{S}}_{\text{far}}$ from them.

Let $T_{i}$ be the counter of the number of samples used for estimating the
respective distance. We define a confidence bound based on a non-asymptotic
version of the law of the iterated logarithm (Kaufmann et al., 2016; Jamieson
et al., 2014); it is of the form222The constants involved can explicitly be
chosen as $\alpha(u)=\sqrt{\frac{2\beta(u,\delta/n)}{u}}\quad\text{with
}\beta(u,\delta^{\prime})=\log(1/\delta^{\prime})+3\log\log(1/\delta^{\prime})+1.5\log(1+\log(u)).$

$\alpha(u)\propto\sqrt{\frac{\log(\log(u)n/\delta)}{u}},$

where $u$ is an integer corresponding to the number of samples, and $\delta$
is a parameter such that the algorithm succeeds with probability at least
$1-\delta$. Within each round, we also let $(\cdot)$ denote a permutation of
$[n]$ such that
$\widehat{d}_{(1)}\leq\widehat{d}_{(2)}\leq\dots\leq\widehat{d}_{(n)}$. We
then define the indices

$\displaystyle q_{1}$
$\displaystyle=\operatorname*{arg\,max}_{i\in\\{(1),\ldots,(k)\\}}\widehat{d}_{i}+\alpha_{i},$
(1) $\displaystyle q_{2}$
$\displaystyle=\operatorname*{arg\,min}_{i\in\\{(k+1+h),\ldots,(n)\\}}\widehat{d}_{i}-\alpha_{i},$
(2)

where $\alpha_{i}=\alpha(T_{i})$. These indices are the analogues of the
standard indices of the Lower-Upper Confidence Bound (LUCB) strategy from the
bandit literature (Kalyanakrishnan et al., 2012) for the bottom $k$ and top
$n-h-k$ arms. The LUCB strategy for exact bottom-$k$ recovery would update the
scores $q_{1}$ and $q_{2}$ (for $h=0$) at each round. Our strategy will go
after what it “thinks” are the bottom $k$ items,
$\widehat{\mathcal{S}}_{\text{close}}=\\{(1),\ldots,(k)\\}$, and what it
“thinks” are the top $n-k-h$ items,
$\widehat{\mathcal{S}}_{\text{far}}=\\{(k+1+h),\ldots,(n)\\}$. Moreover, the
algorithm keeps all the other items,
$\widehat{\mathcal{S}}_{\text{middle}}=\\{(k+1),\ldots,(k+h)\\}$, in
consideration for inclusion in these sets by keeping their confidence
intervals below the confidence intervals of the items in
$\widehat{\mathcal{S}}_{\text{far}}$ (see (3) in the algorithm below). This is
crucial to ensure that the algorithm does not get stuck trying to distinguish
the middle items, which in general requires many samples.

1 Input: Confidence parameter $\delta$, approximation parameter $h$

2 Initialization: For every $i\in[n]$, sample an index $j$ uniformly at random
from $[m]$ and set
$\widehat{d}_{i}(1)=|[\mathbf{x}_{i}]_{j}-[\mathbf{x}]_{j}|^{2}$, $T_{i}=1$.

3 Do until termination:

4 Let $(\cdot)$ denote a permutation of $[n]$ such that
$\widehat{d}_{(1)}\leq\widehat{d}_{(2)}\leq\dots\widehat{d}_{(n)}$.

5 For $q_{1}$ and $q_{2}$ defined by equation (2), define the index
$\displaystyle
b_{2}=\operatorname*{arg\,max}_{i\in\\{q_{2},(k+1),\dots,(k+h)\\}}~{}\alpha_{i}.$
(3)

6 For $\ell\in\\{q_{1},b_{2}\\}$, increment $T_{\ell}\leftarrow T_{\ell}+1$,
sample an index $j$ uniformly at random from $[m]$, and update
$\widehat{d}_{\ell}\leftarrow\frac{T_{\ell}-1}{T_{\ell}}\widehat{d}_{\ell}+\frac{1}{T_{\ell}}|[\mathbf{x}_{\ell}]_{j}-[\mathbf{x}]_{j}|^{2}$.
If $T_{\ell}=m$, then compute the distance $d_{\ell}$ exactly and set
$\widehat{d}_{\ell}=d_{\ell}$ and $\alpha_{\ell}=0$.

7 End Loop once the termination condition holds:
$\displaystyle\widehat{d}_{q_{1}}+\alpha_{q_{1}}\leq\widehat{d}_{q_{2}}-\alpha_{q_{2}}.$
(4)

Return $\widehat{\mathcal{S}}=\\{(1),\ldots,(k+h)\\}$ as an estimate of the
set containing the $k$ nearest neighbors.

Algorithm 1 Adaptive $k$-NN

###  4.1 Logarithmic Computational Complexity for Each Iteration

We next describe several implementation details that are critical for ensuring
that each iteration of the adaptive $k$-NN algorithm has computational
complexity $O(\log(n))$ and not $O(n\log(n))$, which a naïve implementation of
computing the permutations via sorting and max and min computations would
have. The key to achieving a logarithmic computational complexity is realizing
that since only two distance estimates are updated in each iteration, the
orderings of the distance estimates and confidence bounds will not change much
between iterations, and at each iteration we only update the distance estimate
for some indices that minimize or maximize some quantities relating to the
confidence bound. This makes the algorithm amenable to the use of a _heap data
structure_ (Cormen et al., 2009) to reduce computational complexity.

Figure 1 illustrates how a total of seven heaps can be used to implement the
adaptive $k$-NN algorithm efficiently. For each of
$\widehat{\mathcal{S}}_{\text{close}}$,
$\widehat{\mathcal{S}}_{\text{middle}}$, and
$\widehat{\mathcal{S}}_{\text{far}}$, a set of two or three coupled heaps is
maintained, providing ordering information on both the distance estimates (so
that we can maintain our permutation at each iteration) and the confidence
bounds (so that we can select which distance estimates to update). For
example, to determine $q_{2}$, we can simply extract the minimum from the min-
heap on $\widehat{\mathcal{S}}_{\text{far}}$ defined on the lower confidence
bounds $\widehat{d}_{i}-\alpha_{i}$, which has a computational cost of $O(1)$.
Later in the iteration, if we update the distance estimate at $q_{2}$, we
update both the distance estimate min-heap and lower confidence bound min-heap
on $\widehat{\mathcal{S}}_{\text{far}}$ accordingly, which has a computational
cost of $O(\log(n))$. At the end of the iteration, after making such updates
across all three sets of heaps, the distance estimate ordering may not be
maintained; e.g., the largest distance estimate in
$\widehat{\mathcal{S}}_{\text{middle}}$ may be larger than the smallest
distance estimate in $\widehat{\mathcal{S}}_{\text{far}}$. Items from each set
must be swapped with items from other sets accordingly to restore the distance
estimate ordering. Only two distance estimates are updated at each iteration,
so at most a constant number of swaps that does not depend on $n$ are
required, and each swap involves updating the appropriate heaps, yielding that
the computational cost of restoring the distance estimate ordering is also
$O(\log(n))$. Thus, the overall complexity per iteration is $O(\log(n))$. We
ask the reader to refer to our implementation333See
https://github.com/dlej/adaptive-knn. for further details.

$\overbrace{\hskip 65.0pt}^{\textstyle\widehat{d}_{i}}$
pt$\widehat{\mathcal{S}}_{\text{far}}$

$\overbrace{\hskip
30.0pt}^{\rotatebox{90.0}{$\textstyle\widehat{d}_{i}-\alpha_{i}$}}$

pt$\widehat{\mathcal{S}}_{\text{middle}}$

$\overbrace{\hskip 30.0pt}^{\rotatebox{90.0}{$\textstyle\alpha_{i}$}}$

pt$\widehat{\mathcal{S}}_{\text{close}}$

$\overbrace{\hskip
30.0pt}^{\rotatebox{90.0}{$\textstyle\widehat{d}_{i}+\alpha_{i}$}}$

Figure 1: Illustration of how seven heaps can be used in the adaptive $k$-NN
algorithm. Upward-branching trees indicate min-heaps and downward-branching
trees indicate max-heaps.

###  4.2 Guarantees and Optimality of the Adaptive $k$-NN Algorithm

We next establish guarantees on the adaptive $k$-NN algorithm’s success as
well as on its computational complexity. The computational complexity depends
on the gaps between the distances, defined as $\Delta_{i,j}=d_{i}-d_{j}$
through the function

$\displaystyle
N(\mathbf{x},\mathcal{X},h)=\widetilde{O}\bigg{(}\sum_{i=1}^{k}\min(\Delta_{i,k+1+h}^{-2},m)$
(5)
$\displaystyle+\sum_{i=k+1+h}^{n}\min(\Delta_{k,i}^{-2},m)+h\min(\Delta_{k,k+1+h}^{-2},m)\bigg{)}.$

The notation $\widetilde{O}$ absorbs factors logarithmic in $n$ and doubly
logarithmic in the gaps.

######  Theorem 1.

For any points $\mathbf{x}$, $\mathcal{X}$, the adaptive $k$-NN algorithm run
with parameters $\delta$ and $h$ yields a set of size $k+h$ that contains the
$k$ nearest neighbors and has computational complexity at most

$N(\mathbf{x},\mathcal{X},h)$

with probability at least $1-\delta$.

Note that the computational complexity of the adaptive $k$-NN algorithm is
upper-bounded by the complexity of the naïve brute force method, $O(mn+n\log
n)$, but is potentially significantly smaller. In particular, the
computational complexity is small if there is a large gap between the $k$-th
closest point and the $(k+h)$-th closest point. Taking $h=k$, for example, the
algorithms returns a set of size $O(k)$ containing the $k$ nearest neighbors.
We next present two examples, one where the sample complexity of the adaptive
$k$-NN algorithm is small, and one where it does not realize savings over the
brute force method.

Both of these examples assume the data lies in a low-dimensional linear
subspace, a regime where one might consider using projection-based $k$-NN
methods. However, such methods require knowledge of the dimension of the
subspace and often have projection cost at least $O(mn)$. Even if the
dimension is known and the projection is as efficient as possible (such as
subsampling), our method will still have the advantage in that it adapts to
the distances.

First, consider a $p$-dimensional subspace spanned by a matrix
$\mathbf{U}\in\mathbb{R}^{m\times p}$ that has orthogonal columns. In
addition, suppose that the columns of $\mathbf{U}$ are incoherent with respect
to the standard basis vectors $\mathbf{e}_{i}$. Specifically, suppose that the
maximum inner product between a column of $\mathbf{U}$ and a standard basis
vector obeys

$\max_{i,j}\left|\left<\frac{\mathbf{u}_{i}}{{\left\|\mathbf{u}_{i}\right\|}_{2}},\mathbf{e}_{j}\right>\right|\leq\frac{B}{\sqrt{m}}$

for some constant $B\geq 1$. We say $\mathbf{U}$ is _incoherent_ if this bound
holds for small values of $B$. Suppose then that the columns of $\mathbf{U}$
are normalized to $\ell_{2}$-norm $\sqrt{m/p}/B$ and that the dataset
$\mathcal{X}$ and query point $\mathbf{x}$ lie in that subspace, i.e.,

$\displaystyle\mathbf{x}=\mathbf{U}\mathbf{y},\quad\mathcal{X}=\left\\{\mathbf{U}\mathbf{y}_{i}:\mathbf{y}_{i}\in\mathcal{Y}\right\\},$

where $\mathbf{y}\in\mathbb{R}^{p}$ and $\mathcal{Y}\subset\mathbb{R}^{p}$ are
the associated coefficient vectors. Assume that the associated coefficient
vectors are normalized to have $\ell_{2}$-norm equal to $1/2$. Denote the gaps
in the coefficient space by $\Delta_{i,j}^{\mathbf{y}}$. From these
assumptions, we are guaranteed that $\mathbf{x}$ and the points in
$\mathcal{X}$ are bounded in $\ell_{\infty}$ norm by $1/2$. In addition, we
have that

$\displaystyle\frac{1}{m}{\left\|\mathbf{x}-\mathbf{x}_{i}\right\|}_{2}^{2}=\frac{1}{pB^{2}}{\left\|\mathbf{y}-\mathbf{y}_{i}\right\|}_{2}^{2}.$

Then $(\Delta_{i,j})^{-2}=(\Delta_{i,j}^{\mathbf{y}})^{-2}B^{4}$, so the
computational complexity of the adaptive $k$-NN algorithm behaves like
$\widetilde{O}\left(n(\Delta_{k,k+1+h}^{\mathbf{y}})^{-2}B^{4}\right)$ for
large $m$; i.e., the computational complexity does not scale linearly with
$m$. Hence, we can expect the adaptive $k$-NN algorithm to achieve significant
computational savings when the data lies in a low-dimensional subspace of
$\mathbb{R}^{m}$. Furthermore, the algorithm is able to realize these savings
_without having this subspace or its dimension specified_. We illustrate this
ability in our experiments below.

Next, suppose that the subspace is coherent with respect to the identitiy
matrix. For example, consider the extreme case where all points lie in the
one-dimensional subspace spanned by a single standard basis vector
$\mathbf{e}_{i}$. Then, estimation of the distances to an accuracy of $O(1)$
requires at least $O(m)$ samples, and thus the adaptive $k$-NN algorithm will
always have the same sample complexity as the naïve brute force algorithm.

We next show that the algorithm is optimal among active algorithms that
estimate the distances by sampling indices when the data points satisfy
$[\mathbf{x}]_{j}\in\\{-1/2,1/2\\}$. We note that it is only the coordinates
of the data that are so constrained; the normalized distances themselves can
be essentially any values between 0 and 1 for large enough $m$.

######  Theorem 2.

For any $\delta\in(0,0.14]$, let $\mathcal{A}$ denote an algorithm that can
only interact with the data by sampling coordinates uniformly at random and
yields, for any $\mathbf{x}$ and $\mathcal{X}$, the $k$ nearest neighbors with
probability at least $1-\delta$. Then, when $\mathcal{A}$ is run on any set of
data points $\mathbf{x}$, $\mathcal{X}$ such that each coordinate of each
point is either $-\frac{1}{2}$ or $\frac{1}{2}$, it has expected sample
complexity at least

$\displaystyle
N_{\text{low}}(\mathbf{x},\mathcal{X},h)=c^{\prime}\left(\sum_{i=1}^{k-h}\Delta_{i,k+1+h}^{-2}+\sum_{i=k+1+h}^{n}\Delta_{k-h,i}^{-2}\right),$

where
$c^{\prime}=\log\left(\frac{1}{2\delta}\right)\min_{\ell\in\\{k-h,k+1+h\\}}\\{{d_{\ell}(1-d_{\ell})}\\}$.

Note that the above lower bound does not depend on the gaps involving the
items $k-h+1,\ldots,k+h$. However, in the case when $d_{k-h}=d_{k}$, we can
relate the lower bound and the upper bound by

$N(\mathbf{x},\mathcal{X},2h)\leq\widetilde{O}(N_{\text{low}}(\mathbf{x},\mathcal{X},h)),$

so that we see that, up to rescaling of the approximation parameter $h$ and
logarithmic factors, the upper and lower bounds match. We emphasize that the
lower bound only applies to algorithms that interact with the data by
_uniformly sampling_ the distances and only when we constrain the data points.
Thus, Theorem 2 only tells us that the adaptive $k$-NN algorithm is optimal
among algorithms based on adaptively estimating the distances, but it does not
state that algorithms based on other strategies cannot perform better.

##  5 EXPERIMENTS

We run the adaptive $k$-NN algorithm both on artificial data restricted to
low-dimensional subspaces and on real data to demonstrate the effectiveness in
reducing computation over the naïve algorithm. The artificial data is
generated via $\mathbf{x}=c\mathbf{Q}\mathbf{y}$, where
$\mathbf{Q}\in\mathbb{R}^{m\times p}$ is an i.i.d. Gaussian matrix, normalized
to have unit-norm columns, $\mathbf{y}$ are drawn uniformly at random from the
unit sphere, and $c$ is the largest scalar such that
${\left\|\mathbf{x}\right\|}_{\infty}\leq 1/2$ for all $\mathbf{x}$ in the
generated dataset. The real data comes from the Tiny ImageNet dataset (2015),
taking pixel values in $[0,1]$. For each trial, we select $\mathcal{X}$ by
sampling $n$ points at random (without replacement for Tiny ImageNet) and then
select the query point $\mathbf{x}$ by drawing another sample. For these
experiments we used $n=1000$ and $m=12288$, where the choice for $m$ comes
from the dimensionality of the Tiny ImageNet images, which are $64\times
64\times 3$. Futher, we use
$\alpha(u)=\sqrt{\frac{C_{\alpha}\log\left(1+(1+\log(u))n/\delta\right)}{u}}$
and vary $C_{\alpha}$.

Figure 2: Effect of varying $C_{\alpha}$ for the adaptive $k$-NN algorithm on
the random data lying in 10-dimensional (upper left), 100-dimensional (upper
right), and 1000-dimensional (lower left) subspaces and on images from Tiny
ImageNet (lower right). In each plot both the recall (blue, solid) and
fraction of iterations used (red, dashed) are shown.

Figure 2 depicts the fraction of $\mathcal{S}_{\text{close}}$ contained in
$\widehat{\mathcal{S}}$ (recall) along with ratio of the number of iterations
taken by the adaptive $k$-NN algorithm versus the naïve algorithm as we vary
$C_{\alpha}$. Here $k=10$, $h=10$, and $\delta=0.001$. We perform 20 random
trials at each $C_{\alpha}$ and plot the median value (lines) and
interquartile range (shaded area) over the trials. As we expect from our
previous discussion, for low-dimensional subspaces (e.g., $p=10$) we see
significant computational savings (multiple orders of magnitude) by using the
adaptive $k$-NN algorithm over the naïve method while still being able to
return a set containing all of the $k$ nearest neighbors. For larger $p$, such
as $p=1000$, this advantage is nearly non-existent. On Tiny ImageNet, we see
similar performance gains to the small $p$ setting, which can be explained by
the fact that, like most real datasets, the data can be well-approximated as
lying in a low-dimensional subspace.

##  6 PROOF OF THEOREM 1

The proof of Theorem 1 relies on relating the sample complexity to the
computational complexity. We use that the computational complexity of the
adaptive $k$-NN algorithm is no more than $\log(n)$ times the sample
complexity of the adaptive $k$-NN algorithm. To see this, note that, as
discussed in Section 4.1, each iteration has computational cost at most
$O(\log(n))$. The initialization of the heaps at the start of the algorithm
can be done in $O(n)$ computations using Floyd’s algorithm, which is smaller
or equal to the sample complexity. As a consequence, the computational
complexity of the adaptive $k$-NN algorithm is no larger than $O(\log(n))$
times the sample complexity.

For notational convenience, we assume throughout that the distances are
ordered so that

$d_{1}\leq d_{2}\leq\ldots\leq d_{n}.$

We begin by showing that the estimate $\widehat{d}_{i}(T_{i})$ is guaranteed
to be $\alpha_{i}$-close to $d_{i}$, for all $i$, with high probability.

######  Lemma 3 (Kaufmann et al., 2016, Lemma 7).

For any $\delta\in(0,0.05)$, with probability at least $1-\delta$, the event

$\displaystyle\mathcal{E}_{\alpha}\coloneqq\bigg{\\{}$
$\displaystyle\left|\widehat{d}_{i}(t)-d_{i}\right|\leq\alpha_{i},\;\forall
i\in[n],\;\forall t\geq 1\bigg{\\}}$ (6)

occurs. The statement continues to hold for any $\delta\in(0,1)$ with
$\alpha_{i}=\alpha(T_{i})=\sqrt{\frac{2\beta(T_{i},\delta^{\prime})}{T_{i}}}$,
$\beta(t,\delta^{\prime})=2\log(125\log(1.12t)/\delta^{\prime})$.

Lemma 3 is a non-asymptotic version of the law of the iterated logarithm from
(Kaufmann et al., 2016) and (Jamieson et al., 2014). Note that the lemma uses
that $\widehat{d}_{i}(t)$ is a sum of $t$ independent random variables, each
bounded between $0$ and $1$, and
${\mathbb{E}}\left[\widehat{d}_{i}(t)\right]=d_{i}$.

We first show that, on the event $\mathcal{E}_{\alpha}$ defined in equation
(6), the set $\widehat{\mathcal{S}}$ contains the $k$ nearest neighbors. On
the event $\mathcal{E}_{\alpha}$, we have by the termination condition (4)
(which is satisfied since the algorithm has terminated) that the items in the
set $\widehat{\mathcal{S}}_{\text{close}}=\\{(1),\ldots(k)\\}$ have smaller
distances than the items in the set
$\widehat{\mathcal{S}}_{\text{far}}=\\{(k+1+h),\ldots,(n)\\}$. Because there
are $k$ distances that are smaller than the distances in
$\widehat{\mathcal{S}}_{\text{far}}$, the set
$\widehat{\mathcal{S}}_{\text{far}}$ cannot contain any of the $k$-nearest
neighbors, i.e.,
$\widehat{\mathcal{S}}_{\text{far}}\subset\\{1,\ldots,n\\}\setminus\mathcal{S}_{\text{close}}$.
Thus $\mathcal{S}_{\text{close}}\subset\widehat{\mathcal{S}}$.

We next show that on the event $\mathcal{E}_{\alpha}$, the adaptive $k$-NN
algorithm terminates after the desired number of samples. Let
$\gamma\coloneqq\frac{d_{k}+d_{k+1+h}}{2}$, and define the event that item $i$
is bad as

$\mathcal{E}_{\mathrm{bad}}(i)=\begin{cases}\widehat{d}_{i}>\gamma-3\alpha_{i},&i\in\\{1,\ldots,k\\}\\\
\widehat{d}_{i}<\gamma+3\alpha_{i},&i\in\\{k+1+h,\ldots,n\\}\\\
\alpha_{i}>\frac{d_{k+1+h}-d_{k}}{4},&\text{otherwise}.\\\ \end{cases}$

######  Lemma 4.

If $\mathcal{E}_{\alpha}$ occurs and the termination condition (4) is false,
then either $\mathcal{E}_{\mathrm{bad}}(q_{1})$ or
$\mathcal{E}_{\mathrm{bad}}(b_{2})$ occurs.

Lemma 4 is proved in Section A.1 in the supplementary material. Given Lemma 4,
we can complete the proof in the following way. For an item $i$, define

$\Delta_{i}=\begin{cases}d_{k+1+h}-d_{i},&i\in\\{1,\ldots,k\\}\\\
d_{i}-d_{k},&i\in\\{k+1+h,\ldots,n\\}\\\
d_{k+1+h}-d_{k},&\text{otherwise},\end{cases}$

and let $\widetilde{T}_{i}$ be the smallest integer $u$ satisfying the bound
$\alpha(u)\leq\Delta_{i}/8$. A simple calculation (see Section A.2 in the
supplementary material) yields the following fact.

######  Fact 5.

On the event $\mathcal{E}_{\alpha}$, if $T_{i}\geq\widetilde{T}_{i}$ holds,
then $\mathcal{E}_{\mathrm{bad}}(i)$ does not occur.

Let $t\geq 1$ be the $t$-th iteration of the steps in the algorithm, and let
$q_{1}$ and $b_{2}$ be the two items selected in the algorithm. Note that in
each iteration only those distances are estimated. By Lemma 4, we can
therefore bound the total number distance estimate updates by

$\displaystyle
2\sum_{t=1}^{\infty}{\mathbf{1}(\mathcal{E}_{\mathrm{bad}}(q_{1})\cup\mathcal{E}_{\mathrm{bad}}(b_{2}))}$
$\displaystyle\leq 2\sum_{t=1}^{\infty}\sum_{i=1}^{n}{\mathbf{1}((i=q_{1}\cup
i=b_{2})\cap\mathcal{E}_{\mathrm{bad}}(i))}$
$\displaystyle\stackrel{{\scriptstyle\text{(i)}}}{{\leq}}2\sum_{t=1}^{\infty}\sum_{i=1}^{n}{\mathbf{1}((i=q_{1}\cup
i=b_{2})\cap T_{i}(t)\leq\widetilde{T}_{i})}$
$\displaystyle\stackrel{{\scriptstyle\text{(ii)}}}{{\leq}}2\sum_{i=1}^{n}\widetilde{T}_{i}.$
(7)

For inequality (i), we used Fact 5, and inequality (ii) follows because
$T_{i}(t)\leq\widetilde{T}_{i}$ can only be true for $\widetilde{T}_{i}$
iterations $t$.

We conclude the proof by noting that the definition of $\alpha(\cdot)$ yields
the following upper bound (see Section A.3 in the supplementary material).

######  Fact 6.

For $c$ sufficiently large,

$\displaystyle\widetilde{T}_{i}$ $\displaystyle\leq
c\log\left(\frac{n}{\delta}\right)\frac{\log(2\log(2/\Delta_{i}))}{\Delta_{i}^{2}}.$
(8)

Applying this inequality to the right-hand side of equation (7) above
concludes the proof.

##  7 PROOF OF THEOREM 2

Consider an algorithm $\mathcal{A}$ that can only interact with the data by
sampling a index $j$ uniformly at random and then obtaining
$|[\mathbf{x}_{i}]_{j}-[\mathbf{x}]_{j}|$ in response. Because the points
satisfy $[\mathbf{x}]_{j}\in\\{-1/2,1/2\\}$, this is equivalent to drawing
from a distribution $\nu_{i}$ corresponding to a binary $\\{0,1\\}$ random
variable that has mean $d_{i}$. The problem of finding a subset containing the
$k$ nearest neighbors then corresponds to the problem of identifying a subset
of all $n$ distribution consisting of $k+h$ distributions containing the $k$
smallest means. Here we will consider only the case where $h<k$. This is an
_approximate_ version of the bottom-$k$ identification problem in the bandit
literature (Kalyanakrishnan et al., 2012). Thus, to prove Theorem 2, we
provide a lower bound on the sample complexity required to find a subset of
$k+h$ distributions containing the $k$ smallest means, and this lower bound is
also a lower bound on the computational complexity.

Towards this goal, we first introduce some notation required to state a useful
lemma (Kaufmann et al., 2016, Lemma 1) from the bandit literature. Let
$\nu=\\{\nu_{i}\\}_{i=1}^{n}$ be a collection of $n$ probability
distributions, each supported on $\\{0,1\\}$. Consider an algorithm
$\mathcal{A}$, that, at times $t=1,2,\ldots$, selects the index $i_{t}\in[n]$
and receives an independent draw $X_{t}$ from the distribution $\nu_{i_{t}}$
in response. Algorithm $\mathcal{A}$ may select $i_{t}$ only based on past
observations; that is, $i_{t}$ is $\mathcal{F}_{t-1}$-measurable, where
$\mathcal{F}_{t}$ is the $\sigma$-algebra generated by
$i_{1},X_{1},\ldots,i_{t},X_{t}$. Algorithm $\mathcal{A}$ has a stopping rule
$\xi$ that determines the termination of $\mathcal{A}$. We assume that $\xi$
is a stopping time measurable with respect to $\mathcal{F}_{t}$ and obeying
${\mathrm{P}}\left[\xi<\infty\right]=1$.

Let $N_{i}(\xi)$ denote the total number of times index $i$ has been selected
by the algorithm $\mathcal{A}$ (until termination). For any pair of
distributions $\nu$ and $\nu^{\prime}$, we let $\mathrm{KL}(\nu,\nu^{\prime})$
denote their Kullback-Leibler divergence, and for any $p,q\in[0,1]$, let
$\mathrm{kl}(p,q)\coloneqq p\log\frac{p}{q}+(1-p)\log\frac{1-p}{1-q}$ denote
the Kullback-Leiber divergence between two binary random variables with
success probabilities $p,q$.

With this notation, the following lemma relates the cumulative number of
comparisons to the uncertainty between the actual distribution $\nu$ and an
alternative distribution $\nu^{\prime}$.

######  Lemma 7 (Kaufmann et al., 2016, Lemma 1).

Let $\nu,\nu^{\prime}$ be two collections of $n$ probability distributions on
$\mathbb{R}$. Then for any event $\mathcal{E}\in\mathcal{F}_{\xi}$ with
${\mathrm{P}}_{\nu}\left[\mathcal{E}\right]\in(0,1)$, we have

$\displaystyle\sum_{i=1}^{n}{\mathbb{E}}_{\nu}\left[N_{i}(\xi)\right]\mathrm{KL}(\nu_{i},\nu_{i}^{\prime})\geq\mathrm{kl}({\mathrm{P}}_{\nu}\left[\mathcal{E}\right],{\mathrm{P}}_{\nu^{\prime}}\left[\mathcal{E}\right]).$
(9)

In our setting, since $\nu_{i}$ and $\nu_{i}^{\prime}$ are binary
distributions,
$\mathrm{KL}(\nu_{i},\nu_{i}^{\prime})=\mathrm{kl}(d_{i},d_{i}^{\prime})$. Let
us now use Lemma 7 to prove Theorem 2.

Let $\mathcal{S}_{1}(\nu)$ be the set of $k$ distributions out of the $n$
distributions $\nu=(\nu_{1},\ldots,\nu_{n})$ with the smallest means. Define
the event

$\mathcal{E}\coloneqq\left\\{\mathcal{S}_{1}(\nu)\subset\widehat{\mathcal{S}}\right\\},$

corresponding to success of the algorithm $\mathcal{A}$. Recalling that $\xi$
is the stopping rule of algorithm $\mathcal{A}$, we are guaranteed that
$\mathcal{E}\in\mathcal{F}_{\xi}$. Let
$\mathcal{M}\coloneqq\\{\ell_{1},\ldots,\ell_{h+1}\\}$ be a set of distinct
items from the set of $n-k$ distributions with the largest means denoted by
$\mathcal{S}_{2}(\nu)$. We next construct an alternative distribution
$\nu^{\prime}$ such that under that distribution,
$\ell_{1},\ldots,\ell_{h+1}\notin\mathcal{S}_{2}(\nu^{\prime})$, or
equivalently, that $\mathcal{M}\subseteq\mathcal{S}_{1}(\nu^{\prime})$. Since
we assume algorithm $\mathcal{A}$ succeeds for any distribution with
probability at least $1-\delta$, we have both
${\mathrm{P}}_{\nu}\left[\mathcal{E}\right]\geq 1-\delta$ and
${\mathrm{P}}_{\nu^{\prime}}\left[\mathcal{E}\right]\leq\delta$. To see this,
note that if $\mathcal{A}$ succeeds under $\nu^{\prime}$, then
$\mathcal{M}\subset\widehat{\mathcal{S}}$. As such, there can be at most $k-1$
elements of $\mathcal{S}_{1}(\nu)$ in $\widehat{\mathcal{S}}$, which means
that $\mathcal{E}$ does not occur.

It follows that

$\displaystyle\mathrm{kl}({\mathrm{P}}_{\nu}\left[\mathcal{E}\right],{\mathrm{P}}_{\nu^{\prime}}\left[\mathcal{E}\right])\geq\mathrm{kl}(\delta,1-\delta)$
$\displaystyle=(1-2\delta)\log\frac{1-\delta}{\delta}\geq\log\frac{1}{2\delta},$
(10)

where the last inequality holds for $\delta\leq 0.15$. It remains to specify
the alternative distribution $\nu^{\prime}$. The alternative distribution is
defined as

$\displaystyle\nu_{i}^{\prime}$
$\displaystyle=\begin{cases}\nu_{k-h},&i\in\mathcal{M}\\\
\nu_{i},&\text{otherwise}.\end{cases}$

To be most precise on avoiding ties, for $\ell\in\mathcal{M}$, one should take
$\nu_{\ell}^{\prime}=\nu_{k-h}-\varepsilon$ for some $\varepsilon>0$ and let
$\varepsilon\to 0$, but we omit carrying out the associated technical details
in this proof. It follows that, under the distribution $\nu^{\prime}$, the
items in the set $\mathcal{M}$ are not among the items with the $n-k$ largest
means which ensures that
$\mathcal{M}\cap\mathcal{S}_{2}(\nu^{\prime})=\emptyset$.

Let $N_{\ell}$ be the total number of draws from the distribution
$\nu_{\ell}$. We have that

$\displaystyle\sum_{\ell\in\mathcal{M}}\mathrm{kl}(\nu_{\ell},\nu_{\ell}^{\prime}){\mathbb{E}}_{\nu}\left[N_{\ell}\right]$
$\displaystyle\stackrel{{\scriptstyle\text{(i)}}}{{=}}\sum_{i=1}^{n}{\mathbb{E}}_{\nu}\left[N_{i}\right]\mathrm{kl}(\nu_{i},\nu_{i}^{\prime})$
$\displaystyle\stackrel{{\scriptstyle\text{(ii)}}}{{\geq}}\mathrm{kl}({\mathrm{P}}_{\nu}\left[\mathcal{E}\right],{\mathrm{P}}_{\nu^{\prime}}\left[\mathcal{E}\right])$
$\displaystyle\geq\log\frac{1}{2\delta}.$ (11)

Here step (i) follows from the fact that
$\mathrm{kl}(\nu_{i},\nu_{i}^{\prime})=0$ for all
$i\notin[n]\setminus\mathcal{M}$ by definition of the $\nu^{\prime}_{i}$, and
step (ii) follows from Lemma 7. Finally, inequality (11) follows from
inequality (10).

We next upper bound the KL divergence on the left hand side of inequality
(11). Using the inequality $\log x\leq x-1$, valid for $x>0$, we have that for
$\ell\in\mathcal{M}$,

$\displaystyle\mathrm{kl}(\nu_{\ell},\nu_{\ell}^{\prime})$
$\displaystyle\leq\mathrm{kl}_{\ell},\quad\mathrm{kl}_{\ell}\coloneqq\frac{(d_{\ell}-d_{k-h})^{2}}{d_{k-h}(1-d_{k-h})}.$
(12)

Applying inequality (12) to the left hand side of inequality (11) yields

$\displaystyle\sum_{\ell\in\mathcal{M}}\mathrm{kl}_{\ell}{\mathbb{E}}_{\nu}\left[N_{\ell}\right]\geq\log\frac{1}{2\delta},$
(13)

which is valid for each subset $\mathcal{M}\subseteq\mathcal{S}_{2}(\nu)$ of
cardinality $h+1$.

We can therefore obtain a lower bound on
$\sum_{i\in\mathcal{S}_{2}(\nu)}{\mathbb{E}}_{\nu}\left[N_{i}\right]$ by
solving the minimization problem:

$\displaystyle\underset{e_{\ell}\geq
0}{\text{minimize}}\sum_{\ell\in\mathcal{S}_{2}(\nu)}e_{\ell}\quad\text{subject
to}\;\sum_{\ell\in\mathcal{M}}\mathrm{kl}_{\ell}e_{\ell}\geq\log\frac{1}{2\delta}$
$\displaystyle\text{ for all $\mathcal{M}\subseteq\mathcal{S}_{2}(\nu)$ of
cardinality $h+1$}.$ (14)

Since the $\mathrm{kl}_{\ell}$ are increasing in $\ell$ (recall that we assume
the distances to be ordered such that $d_{1}\leq d_{2}\leq\ldots\leq d_{n}$)
the solution to this optimization problem is $e_{k+1},\ldots,e_{k+h}=0$ and
$e_{\ell}=\log(1/2\delta)/\mathrm{kl}_{\ell}$ for $\ell\geq k+1+h$.

Using an analogous line of arguments for items in the set
$\mathcal{S}_{1}(\nu)$ (see Section B in the supplemental material), we arrive
at the lower bound

$\displaystyle\log\frac{1}{2\delta}\sum_{i=1}^{k-h}\frac{d_{k+1+h}(1-d_{k+1+h})}{(d_{i}-d_{k+1+h})^{2}}$
$\displaystyle+\log\frac{1}{2\delta}\sum_{i=k+1+h}^{n}\frac{d_{k-h}(1-d_{k-h})}{(d_{k-h}-d_{i})^{2}}$

on the number of comparisons. This concludes the proof.

#### Acknowledgements

We thank the anonymous reviewers for their constructive feedback. DL and RB
are partially supported by NSF grants IIS-17-30574 and IIS-18-38177, AFOSR
grant FA9550-18-1-0478, ARO grant W911NF-15-1-0316, ONR grants
N00014-17-1-2551 and N00014-18-12571, DARPA grant G001534-7500, and DOD
Vannevar Bush Faculty Fellowship (NSSEFF) grant N00014-18-1-2047. RH is
partially supported by NSF award IIS-1816986.

## References

  * tin (2015) Tiny imagenet visual recognition challenge.  https://tiny-imagenet.herokuapp.com/, 2015.  Accessed: 2019-02-21.
  * Ailon and Chazelle (2006) N. Ailon and B. Chazelle.  Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform.  In _Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing_ , pages 557–563, 2006.
  * Andoni and Indyk (2006) A. Andoni and P. Indyk.  Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.  In _Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science_ , pages 459–468. IEEE, 2006.
  * Bagaria et al. (2018a) V. Bagaria, G. Kamath, V. Ntranos, M. Zhang, and D. Tse.  Medoids in almost-linear time via multi-armed bandits.  In _Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics_ , pages 500–509, 2018a.
  * Bagaria et al. (2018b) V. Bagaria, G. M. Kamath, and D. N. Tse.  Adaptive monte-carlo optimization.  _arXiv:1805.08321_ , 2018b.
  * Bentley (1975) J. L. Bentley.  Multidimensional binary search trees used for associative searching.  _Communications of the ACM_ , 18(9):509–517, Sept. 1975.
  * Black and Rogaway (2002) J. Black and P. Rogaway.  Ciphers with arbitrary finite domains.  In _Proceedings of the Cryptographers’ Track at the RSA Conference on Topics in Cryptology_ , pages 114–130. Springer, 2002.
  * Cormen et al. (2009) T. Cormen, C. Leiserson, R. Rivest, and C. Stein.  _Introduction to Algorithms_.  MIT Press, 3 edition, 2009.
  * Hastie et al. (2009) T. J. Hastie, R. J. Tibshirani, and J. J. H. Friedman.  _The elements of statistical learning_.  Springer, 2 edition, 2009.
  * Heckel et al. (2018) R. Heckel, M. Simchowitz, K. Ramchandran, and M. Wainwright.  Approximate ranking from pairwise comparisons.  In _Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics_ , pages 1057–1066, 2018.
  * Heckel et al. (2019) R. Heckel, N. B. Shah, K. Ramchandran, and M. J. Wainwright.  Active ranking from pairwise comparisons and when parametric assumptions don’t help.  _Annals of Statistics_ , 2019.  arXiv:1606.08842.
  * Jamieson et al. (2014) K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck.  lil’ UCB : An optimal exploration algorithm for multi-armed bandits.  In _Proceedings of The 27th Conference on Learning Theory_ , pages 423–439, 2014.
  * Kalyanakrishnan et al. (2012) S. Kalyanakrishnan, A. Tewari, P. Auer, and P. Stone.  PAC subset selection in stochastic multi-armed bandits.  In _Proceedings of the 29th International Conference on Machine Learning_ , pages 655–662, 2012.
  * Kaufmann et al. (2016) E. Kaufmann, O. Cappé, and A. Garivier.  On the complexity of best-arm identification in multi-armed bandit models.  _Journal of Machine Learning Research_ , 17(1):1–42, 2016.
  * Kocsis and Szepesvári (2006) L. Kocsis and C. Szepesvári.  Bandit based monte-carlo planning.  In _Proceedings of the 17th European Conference on Machine Learning_ , pages 282–293. Springer-Verlag, 2006.
  * Li and Malik (2018) K. Li and J. Malik.  Implicit maximum likelihood estimation.  _arXiv preprint arXiv:1809.09087_ , 2018.
  * Li et al. (2018) L. Li, K. Jamieson, G. DeSalvo, A. Rostamizadeh, and A. Talwalkar.  Hyperband: A novel bandit-based approach to hyperparameter optimization.  _Journal of Machine Learning Research_ , 18(185):1–52, 2018.

##  Appendix A PROOFS OF LEMMAS AND FACTS

###  A.1 Proof of Lemma 4

The proof is very similar to the proof of Lemma 2 of Heckel et al. (2018).
There are several cases of $q_{1}$ and $b_{2}$ to consider. We will show each
by contradiction, starting with the assumption that the termination condition
is false and both $\mathcal{E}_{\mathrm{bad}}(q_{1})$ and
$\mathcal{E}_{\mathrm{bad}}(b_{2})$ do not occur, all under the event
$\mathcal{E}_{\alpha}$. Let $\mathcal{E}_{\mathrm{good}}(i)$ denote the
complement of $\mathcal{E}_{\mathrm{bad}}(i)$. It also will be useful to
define the quantity

$\displaystyle
m_{2}=\operatorname*{arg\,max}_{i\in\\{(k+1),\ldots,(k+h)\\}}\alpha_{i}$ (15)

such that $b_{2}=\operatorname*{arg\,max}_{i\in\\{m_{2},q_{2}\\}}\alpha_{i}$.

  1. i.

When $q_{1}\leq k$ and $b_{2}>k+h$, we have by
$\mathcal{E}_{\mathrm{good}}(q_{1})$ that

$\displaystyle\widehat{d}_{q_{1}}+\alpha_{q_{1}}<\widehat{d}_{q_{1}}+3\alpha_{q_{1}}\leq\gamma$
(16)

and similarly that ${\widehat{d}_{b_{2}}-\alpha_{b_{2}}>\gamma}$ by
$\mathcal{E}_{\mathrm{good}}(b_{2})$. Since
$\widehat{d}_{q_{2}}-\alpha_{q_{2}}\geq\widehat{d}_{m_{2}}-\alpha_{m_{2}}$, we
have that $\widehat{d}_{q_{2}}-\alpha_{q_{2}}>\gamma$ in both the case that
$b_{2}=m_{2}$ and $b_{2}=q_{2}$. Together, this implies that the termination
condition (4) is true, which violates our assumption.

  2. ii.

When $q_{1}\leq k$ and $k<b_{2}\leq k+h$, we have first by
$\mathcal{E}_{\mathrm{good}}(q_{1})$ that
${\widehat{d}_{q_{1}}+3\alpha_{q_{1}}\leq\gamma}$. Starting from here, and
using the definition of $q_{1}$, we have for all
$i\in\widehat{\mathcal{S}}_{\text{close}}$,

$\displaystyle\gamma$
$\displaystyle\geq\widehat{d}_{q_{1}}+\alpha_{q_{1}}+2\alpha_{q_{1}}$
$\displaystyle\geq\widehat{d}_{i}+\alpha_{i}+2\alpha_{q_{1}}$
$\displaystyle\geq d_{i}+2\alpha_{q_{1}}$ $\displaystyle>d_{i}.$ (17)

Now we let $\Delta$ denote $d_{k+1+h}-d_{k}$. By definition of $b_{2}$, using
$\mathcal{E}_{\mathrm{good}}(b_{2})$, we have that ${\alpha_{j}\leq\Delta/4}$
for all ${j\in\widehat{\mathcal{S}}_{\text{middle}}\cup\\{q_{2}\\}}$. Then we
can start from ${\gamma>\widehat{d}_{q_{1}}+\alpha_{q_{1}}}$ to conclude that
for all ${j\in\widehat{\mathcal{S}}_{\text{middle}}\cup\\{q_{2}\\}}$,

$\displaystyle\gamma$ $\displaystyle>\widehat{d}_{q_{1}}+\alpha_{q_{1}}$
$\displaystyle\overset{(i)}{>}\widehat{d}_{q_{2}}-\alpha_{q_{2}}$
$\displaystyle\geq\widehat{d}_{q_{2}}-\frac{\Delta}{4}$
$\displaystyle\geq\widehat{d}_{j}-\frac{\Delta}{4}$ $\displaystyle\geq
d_{j}-\alpha_{j}-\frac{\Delta}{4}$ $\displaystyle\geq d_{j}-\frac{\Delta}{2},$
(18)

where $(i)$ comes from our assumption that the terminating condition (4) is
false. Combining (17) and (18) along with ${\gamma+\Delta/2=d_{k+1+h}}$, we
obtain that ${d_{k+1+h}>d_{i}}$ for all
$i\in\widehat{\mathcal{S}}\cup\\{q_{2}\\}$, which is a contradiction, since
there can be at most $k+h$ values of $d_{i}$ that are smaller than
$d_{k+1+h}$.

  3. iii.

When $k<q_{1}\leq k+h$ and $b_{2}>k+h$, the case is similar to the previous
case, except that we need to bound $\alpha_{i}$ for
$i\in\widehat{\mathcal{S}}_{\text{middle}}$ in a different way. By
$\mathcal{E}_{\mathrm{good}}(b_{2})$,
$\widehat{d}_{q_{2}}\geq\widehat{d}_{b_{2}}$, and
$\alpha_{b_{2}}\geq\alpha_{q_{2}}$, we have analogously to (17), for all
$i\in\widehat{\mathcal{S}}_{\text{far}}$,

$\displaystyle\gamma$ $\displaystyle\leq\widehat{d}_{b_{2}}-3\alpha_{b_{2}}$
$\displaystyle\leq\widehat{d}_{q_{2}}-\alpha_{q_{2}}-2\alpha_{b_{2}}$
$\displaystyle\leq d_{i}-2\alpha_{b_{2}}.$ (19)

Equivalently, $d_{i}\geq\gamma+2\alpha_{b_{2}}$. Since there are ${n-k-h}$
values of $i$ for which this inequality holds, it must hold for $d_{k+1+h}$,
so we obtain

$\displaystyle\alpha_{b_{2}}\leq\frac{d_{k+1+h}-\gamma}{2}=\frac{\Delta}{4}.$
(20)

By definition of $b_{2}$, $\alpha_{i}\leq\Delta/4$ for all
$i\in\widehat{\mathcal{S}}_{\text{middle}}\cup\\{q_{2}\\}$, and a
contradiction can be reached similarly as in case ii.

  4. iv.

For the case when both $q_{1},b_{2}\in\\{k+1,\ldots,k+h\\}$, we first show
that at least one of ${\gamma<\widehat{d}_{q_{1}}+\alpha_{q_{1}}}$ or
$\gamma>\widehat{d}_{q_{2}}-\alpha_{q_{2}}$ is true. To see this, first
suppose the former is false. Then using that the terminating condition (4) is
false, we have

$\displaystyle\gamma\geq\widehat{d}_{q_{1}}+\alpha_{q_{1}}>\widehat{d}_{q_{2}}-\alpha_{q_{2}}.$
(21)

Now that we know that at least one of these inequalities holds, and we proceed
similarly for each. First suppose that the former inequality,
${\gamma<\widehat{d}_{q_{1}}+\alpha_{q_{1}}}$, holds. Using that by
$\mathcal{E}_{\mathrm{good}}(q_{1})$ and $\mathcal{E}_{\mathrm{good}}(b_{2})$
we have $\alpha_{i}\leq\Delta/4$ for all
$i\in\\{q_{1},q_{2}\\}\cup\widehat{\mathcal{S}}_{\text{middle}}$, we have
that, for all
$i\in\\{q_{1},q_{2}\\}\cup\widehat{\mathcal{S}}_{\text{middle}}$,

$\displaystyle\gamma$ $\displaystyle<\widehat{d}_{q_{1}}+\alpha_{q_{1}}$
$\displaystyle\leq\widehat{d}_{i}+\alpha_{q_{1}}$ $\displaystyle\leq
d_{i}+\alpha_{i}+\alpha_{q_{1}}$ $\displaystyle\leq d_{i}+\frac{\Delta}{2}.$
(22)

We also have for all $j\in\widehat{\mathcal{S}}_{\text{far}}$ that

$\displaystyle\gamma$ $\displaystyle<\widehat{d}_{q_{1}}+\alpha_{q_{1}}$
$\displaystyle\leq\widehat{d}_{q_{2}}-\alpha_{q_{2}}+\alpha_{q_{2}}+\alpha_{q_{1}}$
$\displaystyle\leq\widehat{d}_{j}-\alpha_{j}+\alpha_{q_{2}}+\alpha_{q_{1}}$
$\displaystyle\leq d_{j}+\alpha_{q_{2}}+\alpha_{q_{1}}$ $\displaystyle\leq
d_{j}+\frac{\Delta}{2}.$ (23)

Combining (iv) and (iv), we have that $d_{i}>d_{k}$ for all
$i\in\\{q_{1}\\}\cup\widehat{\mathcal{S}}_{\text{middle}}\cup\widehat{\mathcal{S}}_{\text{far}}$,
which is a contradiction, since at most $n-k$ values of $i$ can satisfy this
inequality.

The case that $\gamma>\widehat{d}_{q_{2}}-\alpha_{q_{2}}$ is entirely
analogous.

  5. v.

When $q_{1}>k+h$ or $b_{2}\leq k$, we can make similar arguments to the
previous cases to reach a contradiction.

###  A.2 Proof of Fact 5

First, when $i\leq k$, we have

$\displaystyle\widehat{d}_{i}+3\alpha_{i}$ $\displaystyle\leq
d_{i}+4\alpha_{i}$ $\displaystyle\leq d_{i}+\frac{\Delta_{i}}{2}$
$\displaystyle\leq\frac{d_{k+1+h}+d_{i}}{2}\leq\gamma,$ (24)

where the last inequality uses $d_{i}\leq d_{k}$, so
$\mathcal{E}_{\mathrm{bad}}(i)$ does not occur. This is similarly shown for
$i>k+h$. For ${k<i\leq k+h}$, that $\mathcal{E}_{\mathrm{bad}}(i)$ does not
occur follows immediately from $\alpha_{i}\leq\Delta_{i}/8\leq\Delta_{i}/4$.

###  A.3 Proof of Fact 6

Recalling that $\alpha_{i}(u)=\sqrt{\frac{2\beta(u,\delta/n)}{u}}$, at
${\alpha_{i}(u)=\Delta_{i}/8}$ we have that
$u=2(\Delta_{i}/8)^{-2}\beta(u,\delta^{\prime})$, so we need to bound the
greatest fixed point $u^{*}$ of

$\displaystyle f(u)=2(\Delta_{i}/8)^{-2}\beta(u,\delta^{\prime}).$

Let $u_{0}=2(\Delta_{i}/8)^{-2}$, and note that for all $u\geq u_{0}$,

$\displaystyle f^{\prime}(u)$
$\displaystyle=\frac{2(\Delta_{i}/8)^{-2}(2)}{u\log(1.12u)}$
$\displaystyle\leq\frac{2(\Delta_{i}/8)^{-2}(2)}{2(\Delta_{i}/8)^{-2}\log((1.12)2(\Delta_{i}/8)^{-2})}$
$\displaystyle\leq\frac{2}{\log((1.12)32)}$ $\displaystyle<1.$ (25)

The second inequality holds because $\Delta_{i}\leq 2$. Suppose that
$u^{*}>u_{0}$. Using Taylor’s theorem, we have that for some $z\geq u_{0}$,

$\displaystyle f(u_{0})$ $\displaystyle=f(u^{*})+f^{\prime}(z)(u_{0}-u^{*})$
$\displaystyle=u^{*}(1-f^{\prime}(z))+u_{0}f^{\prime}(z).$ (26)

Then

$\displaystyle u^{*}$
$\displaystyle=\frac{f(u_{0})-u_{0}f^{\prime}(z)}{1-f^{\prime}(z)}$
$\displaystyle\leq\frac{f(u_{0})}{1-f^{\prime}(u_{0})}.$ (27)

So, we can bound the greatest fixed point of $f$ as

$\displaystyle u^{*}$
$\displaystyle\leq\max\left\\{u_{0},\frac{f(u_{0})}{1-f^{\prime}(u_{0})}\right\\}$
$\displaystyle=2(\Delta_{i}/8)^{-2}\max\left\\{1,\frac{\beta(2(\Delta_{i}/8)^{-2},\delta^{\prime})}{1-2/\log((1.12)32)}\right\\}$
$\displaystyle=c_{1}\Delta_{i}^{-2}\beta(2(\Delta_{i}/8)^{-2},\delta^{\prime}),$
(28)

where $c_{1}=128/(1-2/\log((1.12)32))$. Since $\widetilde{T}_{i}\leq u^{*}+1$,
letting $c_{2}=c_{1}+1$,

$\displaystyle\widetilde{T}_{i}\leq\frac{c_{2}}{\Delta_{i}^{2}}\log\left(125\frac{n}{\delta}\log\left(\frac{(1.12)128}{\Delta_{i}^{2}}\right)\right).$
(29)

Then for $c$ sufficiently large,

$\displaystyle\widetilde{T}_{i}$ $\displaystyle\leq
c\log\left(\frac{n}{\delta}\right)\frac{\log(2\log(2/\Delta_{i}))}{\Delta_{i}^{2}}.$
(30)

##  Appendix B ADDITIONAL THEOREM 2 PROOF DETAILS

In this section we provide details on bounding
$\sum_{i\in\mathcal{S}_{1}(\nu)}{\mathbb{E}}_{\nu}\left[N_{i}\right]$ that we
omitted in the proof of Theorem 2. We consider the set
$\mathcal{M}=\\{\ell_{1},\ldots,\ell_{h+1}\\}\subseteq\mathcal{S}_{1}(\nu)$
and construct an alternative distribution $\nu^{\prime}$ such that under that
distribution $\mathcal{M}\subseteq\mathcal{S}_{2}(\nu^{\prime})$. Then under
$\nu^{\prime}$, if $\mathcal{A}$ succeeds, then at most $h$ elements of
$\mathcal{S}_{2}(\nu^{\prime})$ can be in $\widehat{\mathcal{S}}$, meaning
that at least one element of $\mathcal{M}$ is not in $\widehat{\mathcal{S}}$
and that $\mathcal{E}$ does not occur. So, if $\mathcal{A}$ succeeds with
probability at least $1-\delta$, then both
${\mathrm{P}}_{\nu}\left[\mathcal{E}\right]\geq 1-\delta$ and
${\mathrm{P}}_{\nu^{\prime}}\left[\mathcal{E}\right]\leq\delta$.

Our alternative distribution $\nu^{\prime}$ is defined as

$\displaystyle\nu_{i}^{\prime}=\begin{cases}\nu_{k+1+h},&i\in\mathcal{M}\\\
\nu_{i},&\text{otherwise}.\end{cases}$

Again, to avoid ties, for $\ell\in\mathcal{M}$, one should take
$\nu_{\ell}^{\prime}=\nu_{k+1+h}+\varepsilon$ and let $\varepsilon\to 0$, but
we omit this detail. The remainder of the arguments are entirely analogous to
the case shown previously, giving us the bound

$\displaystyle\sum_{i\in\mathcal{S}_{1}(\nu)}{\mathbb{E}}_{\nu}\left[N_{i}\right]\geq\log\frac{1}{2\delta}\sum_{i=1}^{k-h}\frac{d_{k+1+h}(1-d_{k+1+h})}{(d_{i}-d_{k+1+h})^{2}}.$


# BasicVSR: The Search for Essential Components in
Video Super-Resolution and Beyond

Kelvin C.K. Chan1 Xintao Wang2 Ke Yu3 Chao Dong4,5 Chen Change Loy1
1S-Lab Corresponding author Nanyang Technological University 2Applied Research
Center  Tencent PCG
3CUHK – SenseTime Joint Lab  The Chinese University of Hong Kong
4Shenzhen Key Lab of Computer Vision and Pattern Recognition  SIAT-SenseTime
Joint Lab
Shenzhen Institutes of Advanced Technology  Chinese Academy of Sciences
5SIAT Branch  Shenzhen Institute of Artificial Intelligence and Robotics for
Society
{chan0899<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Video super-resolution (VSR) approaches tend to have more components than the
image counterparts as they need to exploit the additional temporal dimension.
Complex designs are not uncommon. In this study, we wish to untangle the knots
and reconsider some most essential components for VSR guided by four basic
functionalities, i.e., Propagation, Alignment, Aggregation, and Upsampling. By
reusing some existing components added with minimal redesigns, we show a
succinct pipeline, BasicVSR, that achieves appealing improvements in terms of
speed and restoration quality in comparison to many state-of-the-art
algorithms. We conduct systematic analysis to explain how such gain can be
obtained and discuss the pitfalls. We further show the extensibility of
BasicVSR by presenting an information-refill mechanism and a coupled
propagation scheme to facilitate information aggregation. The BasicVSR and its
extension, IconVSR, can serve as strong baselines for future VSR approaches.

Table 1: Components in existing VSR methods. We categorize components based on
their functionalities: i) Propagation refers to the way in which features are
propagated temporally, ii) Alignment concerns on the spatial transformation
applied to misaligned images/features, iii) Aggregation defines the steps to
combine aligned features, and iv) Upsampling describes the method to transform
the aggregated features to the final output image. Bolded texts correspond to
designs that were reported to achieve better performance in the literature.

| Sliding-Window | Recurrent
---|---|---
EDVR [31] | MuCAN [20] | TDAN [30] | BRCN [10, 11] | FRVSR [25] | RSDN [12] | BasicVSR | IconVSR
Propagation | Local | Local | Local | Bidirectional | Unidirectional | Unidirectional | Bidirectional |  Bidirectional (coupled)
Alignment |  Yes (DCN) |  Yes (correlation) |  Yes (DCN) | No |  Yes (flow) | No |  Yes (flow) |  Yes (flow)
Aggregation | Concatenate + TSA | Concatenate | Concatenate | Concatenate | Concatenate | Concatenate | Concatenate | Concatenate + Refill
Upsampling | Pixel-Shuffle | Pixel-Shuffle | Pixel-Shuffle | Pixel-Shuffle | Pixel-Shuffle | Pixel-Shuffle | Pixel-Shuffle | Pixel-Shuffle

##  1 Introduction

Compared to single-image super-resolution, which focuses on the intrinsic
properties of a single image for the upscaling task, video super-resolution
(VSR) poses an extra challenge as it involves aggregating information from
multiple highly-related but misaligned frames in video sequences.

Various approaches have been proposed to address the challenge. Some designs
can be highly complex. For instance, in the representative method EDVR [32], a
multi-scale deformable alignment module and multiple attention layers are
adopted for aligning and integrating the features from different frames. In
RBPN [9], multiple projection modules are used to sequentially aggregate
features from multiple frames. Such designs are effective but inevitably
increase the runtime and model complexity (see Fig. 1). In addition, unlike
SISR, the potentially complex and dissimilar designs of VSR methods pose
difficulties in implementing and extending existing approaches, hampering
reproducibility and fair comparisons.

Figure 1: Speed and performance comparison. Without bells and whistles,
BasicVSR outperforms state-of-the-art methods with high efficiency. Built upon
BasicVSR, IconVSR further improves the performance. Comparisons are performed
on UDM10 dataset [34].

There is a need to step back and reconsider the diverse designs of VSR models,
with the aim to search for a more generic, efficient, and easy-to-implement
baseline for VSR. We start our search by decomposing popular VSR approaches
into submodules based on functionalities. As summarized in Table 1, most
existing methods entail four inter-related components, namely, propagation,
alignment, aggregation, and upsampling. Such a decomposition allows us to
systematically study various options under each component and understand their
pros and cons.

Through extensive experiments, we find that with minimal redesigns of existing
options, one could already reach a strong yet efficient baseline for VSR
without bells and whistles. In this paper, we highlight one of such
possibilities, named BasicVSR. We observe that, among the four aforementioned
components, the choices of propagation and alignment components could lead to
a big swing in terms of performance and efficiency. Our experiments suggest
the use of bidirectional propagation scheme to maximize information gathering,
and an optical flow-based method to estimate the correspondence between two
neighboring frames for feature alignment. By simply streamlining these
propagation and alignment components with the commonly-adopted designs for
aggregation (feature concatenation) and upsampling (pixel-shuffle [27]),
BasicVSR outperforms existing state of the arts [9, 12, 32] in both
performance (up to 0.61 dB) and efficiency (up to $24{\times}$ speedup).

Thanks to its simplicity and versatility, BasicVSR provides a viable starting
point for extending to more elaborated networks. By using BasicVSR as a
foundation, we present IconVSR that comprises two novel extensions to improve
the aggregation and the propagation components. The first extension is named
information-refill. This mechanism leverages an additional module to extract
features from sparsely selected frames (keyframes), and the features are then
inserted into the main network for feature refinement. The second extension is
a coupled propagation scheme, which facilitates information exchange between
the forward and backward propagation branches. The two modules not only reduce
error accumulation during propagation due to occlusions and image boundaries,
but also allow the propagation to access complete information in a sequence
for generating high-quality features. With these two new designs, IconVSR
surpasses BasicVSR with a PSNR improvement of up to 0.31 dB.

We believe that our work is timely, given the increasing number of approaches
centered around the research of VSR. A strong, simple yet extensible baseline
is needed. Guided by the main functionalities in VSR approaches, we reconsider
some essential components in existing pipelines and present an efficient
baseline for VSR. We show that simple components, when integrated properly,
would synergize and lead to state-of-the-art performance. We further present
an example of extending BasicVSR with two novel modules to refine the
propagation and aggregation components.

Figure 2: An overview of BasicVSR. BasicVSR is a generic and efficient
baseline for VSR. With minimal redesigns of existing components including
optical flow and residual blocks, it outperforms existing state of the arts
with high efficiency. (a) BasicVSR adopts a typical bidirectional recurrent
network. The upsampling module $U$ contains multiple pixel-shuffle and
convolutions. The red and blue colors represent the backward and forward
propagations, respectively. (b) The propagation branches contain only generic
components. $S$, $W$, and $R$ refer to the flow estimation module, spatial
warping module, and residual blocks, respectively.

##  2 Related Work

Existing VSR approaches [10, 21, 28, 34, 20, 12, 13] can be mainly divided
into two frameworks – sliding-window and recurrent. Earlier methods [1, 29,
33] in the sliding-window framework predict the optical flow between low-
resolution (LR) frames and perform spatial warping for alignment. Later
approaches resort to a more sophisticated approach of implicit alignment. For
example, TDAN [30] adopts deformable convolutions (DCNs) [5, 37] to align
different frames at the feature level. EDVR [32] further uses DCNs in a multi-
scale fashion for more accurate alignment. DUF [16] leverages dynamic
upsampling filters to handle motions implicitly. Some approaches take a
recurrent framework. RSDN [12] proposes a recurrent detail-structural block
and a hidden state adaptation module to enhance the robustness to appearance
change and error accumulation. RRN [14] adopts a residual mapping between
layers with identity skip connections to ensure a fluent information flow and
preserve the texture information over long periods. The aforementioned studies
have led to many new and sophisticated components to address the propagation
and alignment problems in VSR. Here, we reinvestigate some of the components
and find that bidirectional propagation coupled with a simple optical flow-
based feature alignment suffice to outperform many state-of-the-art methods.

The information-refill mechanism in IconVSR is reminiscent of the concept of
interval-based processing [4, 15, 26, 35, 36, 38, 39]. These methods divide
video frames into independent intervals characterized by keyframes and non-
keyframes. The keyframes and non-keyframes are then processed by different
pipelines. For instance, FAST [35] applies SRCNN [6, 7] to super-resolve the
keyframes. Non-keyframes are then restored using the upscaled keyframes and
the motion vectors stored in the compressed video codec. IconVSR inherits the
concept of keyframes, but unlike existing methods that process the intervals
independently, we make one advancement by connecting the intervals through the
propagation branches. With this design, long-term information can be
propagated across the inter-connected intervals, further improving the
effectiveness.

##  3 Methodology

Video super-resolution, by nature, involves a long and complex processing
pipeline since it needs to aggregate information from not only the spatial
dimension but also the temporal dimension. Existing studies typically focus on
one aspect of the functionalities to make advancement and may not collectively
consider the synergy of various components. There is an urge to revisit
various components macroscopically and uncover a generic baseline that
inherits the strengths of existing approaches. In this work, we conduct
extensive analysis and present a simple, strong and versatile baseline,
BasicVSR, which can serve as a backbone with abundant flexibilities in design.

###  3.1 BasicVSR

Aiming at discovering generic frameworks for facilitating analysis and
development of VSR methods, we confine our search to commonly-adopted elements
such as optical flow and residual blocks. An overview of BasicVSR is depicted
in Fig. 2.

Propagation. Propagation is one of the most influential components in VSR. It
specifies how the information in a video sequence is leveraged. Existing
propagation schemes can be divided into three main groups: local,
unidirectional and bidirectional propagations. In what follows, we discuss the
weaknesses of the former two to motivate our choice of bidirectional
propagation in BasicVSR.

  * •

Local Propagation. The sliding-window methods [9, 13, 32] take the LR images
within a local window as inputs and employ the local information for
restoration. In this design, the accessible information is restricted in a
local neighborhood. The omittance of distant frames inevitably limits the
potential of the sliding-window methods. To verify our claim, we start with a
global receptive field (in the temporal dimension) and gradually reduce the
receptive field. We separate the test sequences into $K$ segments and use our
BasicVSR to restore each segment independently. The PSNR difference to the
case $K{=}1$ (global propagation) is depicted in Fig. 3.

First, the difference in PSNR is reduced ( better performance) when the number
of segments decreases ( temporal receptive field increases). This suggests
that the information in distant frames is beneficial to the restoration and
should not be neglected. Second, the difference in PSNR is the largest at the
two ends of each segment, indicating the necessity of adopting long sequences
to accumulate long-term information.

Figure 3: Local vs Global propagation. When the number of segments $K$ is
reduced, the increased temporal receptive field leads to higher PSNR. This
demonstrates the importance of aggregating long-term information. Values
smaller than zero (dotted line) indicate a lower PSNR than the case $K{=}1$.

  * •

Unidirectional Propagation. The aforementioned problem can be resolved by
adopting a unidirectional propagation [8, 12, 14, 25], where the information
is sequentially propagated from the first frame to the last frame. However, in
this setting, the information received by different frames is imbalanced.
Specifically, the first frame receives no information from the video sequence
except itself, whereas the last frame receives information from the whole
sequence. Hence, suboptimal results are expected for the earlier frames.

To demonstrate the effects, we compare BasicVSR (using bidirectional
propagation) with its unidirectional variant (with comparable network
complexity). From Fig. 4, we see that the unidirectional model obtains a
significantly lower PSNR than bidirectional propagation at early timesteps,
and the difference gradually reduces as more information is aggregated with
the increase in the number of frames. Moreover, a consistent performance drop
of 0.5 dB is observed with only partial information employed. These
observations reveal the suboptimality of unidirectional propagation. One can
improve the output quality by propagating information back from the last frame
of the sequence.

  * •

Bidirectional Propagation. The above two problems can be simultaneously
addressed by bidirectional propagation, in which the features are propagated
forward and backward in time independently. Motivated by this, BasicVSR adopts
a typical bidirectional propagation scheme. Given an LR image $x_{i}$, its
neighboring frames $x_{i-1}$ and $x_{i+1}$, and the corresponding features
propagated from its neighbors, denoted as $h^{f}_{i-1}$ and $h^{b}_{i+1}$, we
have

$\begin{split}&h_{i}^{b}=F_{b}(x_{i},x_{i+1},h_{i+1}^{b}),\\\
&h_{i}^{f}=F_{f}(x_{i},x_{i-1},h_{i-1}^{f}),\end{split}$ (1)

where $F_{b}$ and $F_{f}$ denote the backward and forward propagation
branches, respectively.

Figure 4: Unidirectional vs Bidirectional. In unidirectional propagation,
earlier timesteps receive less information, leading to inferior performance.
Values smaller than zero (dotted line) indicates a lower PSNR than the
bidirectional counterpart. Note that the unidirectional model outperforms the
bidirectional model only for the last frame, owing to the zero feature
initialization in the bidirectional model.

Alignment. Spatial alignment plays an important role in VSR as it is
responsible to align highly related but misaligned images/features for
subsequent aggregation. Mainstream works can be divided into three categories:
without alignment, image alignment, and feature alignment. In this section, we
conduct experiments to analyze each of the categories and to validate our
choice of feature alignment.

  * •

Without Alignment. Existing recurrent methods [8, 10, 11, 12, 14] generally do
not perform alignment during propagation. The non-aligned features/images
impede aggregation and eventually lead to substandard performance. This
suboptimality can be reflected by our experiment, where we remove the spatial
alignment module in BasicVSR. In this case, we directly concatenate the non-
aligned features for restoration. Without proper alignment, the propagated
features are not spatially aligned with the input image. As a result, the
local operations such as convolutions, which have relatively small receptive
fields, are inefficient in aggregating the information from corresponding
locations. A drop of 1.19 dB of PSNR is observed. This result suggests that it
is pivotal to adopt operations that have a large enough receptive field to
aggregate information from distant spatial locations.

  * •

Image Alignment. Earlier works [17, 33] perform alignment by computing the
optical flow and warping the images before restoration. Recently, Chan et al.
[2] show that moving the spatial alignment from the image level to the feature
level yields a marked improvement. In this work, we further conduct
experiments to verify their claim. We compare image warping and feature
warping111We compute optical flow from the images and use the optical flow for
feature warping. on a variant of BasicVSR. Resulting from the inaccuracy of
optical flow estimation, the warped images inevitably suffer from blurriness
and incorrectness. The loss of details eventually leads to degraded outputs.
In our experiments, a drop of 0.17 dB is observed when adopting image
alignment. This observation confirms the necessity of shifting the spatial
alignment to the feature level.

  * •

Feature Alignment. The inferior performance of removing/image alignment
motivates us to resort to feature alignment. Similar to flow-based methods
[17, 25, 33], BasicVSR adopts optical flow for spatial alignment. But instead
of warping the images as in previous works, we perform warping on the features
for better performance. The aligned features are then passed to multiple
residual blocks for refinement. Formally, we have

$\begin{split}&s_{i}^{\\{b,f\\}}=S(x_{i},x_{i\pm 1}),\\\
&\bar{h}_{i}^{\\{b,f\\}}=W(h_{i\pm 1}^{\\{b,f\\}},s_{i}^{\\{b,f\\}}),\\\
&h_{i}^{\\{b,f\\}}=R_{\\{b,f\\}}(x_{i},\bar{h}_{i}^{\\{b,f\\}}),\end{split}$
(2)

and $F_{\\{b,f\\}}=R_{\\{b,f\\}}\circ W\circ S$ with a slight abuse of
notations. Here $S$ and $W$ denote the flow estimation and spatial warping
modules, respectively, and $R_{\\{b,f\\}}$ denotes a stack of residual blocks.

Aggregation and Upsampling. BasicVSR adopts basic components for aggregation
and upsampling. Specifically, given the intermediate features
$h_{i}^{\\{b,f\\}}$, an upsampling module composed of multiple convolutions
and pixel-shuffle [27] is used to generate the output HR images:

$\begin{split}&y_{i}=U(h_{i}^{f},h_{i}^{b}),\end{split}$ (3)

where $U$ denotes the upsampling module.

Summary of BasicVSR. The analysis above motivates the design choice of
BasicVSR. For propagation, BasicVSR has chosen bidirectional propagation with
emphasis on long-term and global propagation. For alignment, BasicVSR adopts a
simple flow-based alignment but taking place at feature level. For aggregation
and upsampling, popular choices on feature concatenation and pixel-shuffle
suffice. Despite being a simple and succinct method, BasicVSR achieves great
performance in both restoration quality and efficiency. BasicVSR is also
highly versatile as it can readily accommodate additional components to handle
more challenging scenarios, as we show next.

Figure 5: (a) An additional feature extractor is used for feature refinement,
alleviating the error accumulation during propagation. $I_{key}$ denotes the
set of indices of the selected keyframes. $E$ and $C$ denote the feature
extractor and convolution, respectively. (b) The inter-connected propagation
branches facilitate the information exchange by passing the outputs of the
backward branches to the forward branches. The proposed components are colored
in purple.

###  3.2 From BasicVSR to IconVSR

Using BasicVSR as a backbone, we introduce two novel components – Information-
refill mechanism and coupled propagation (IconVSR), to mitigate error
accumulation during propagation and to facilitate information aggregation.

Information-Refill. Inaccurate alignment in occluded regions and on image
boundaries is a prominent challenge that can lead to error accumulation,
especially if we adopt long-term propagation in our framework. To alleviate
undesirable effects brought by such erroneous features, we propose an
information-refill mechanism for feature refinement.

As shown in Fig. 5(a), an additional feature extractor is used to extract deep
features from a subset of input frames (keyframes) and their respective
neighbors. The extracted features are then fused with the aligned features
$\bar{h}_{i}$ (Eq. 2) by a convolution:

$\begin{split}&e_{i}=E(x_{i-1},x_{i},x_{i+1}),\\\
&\hat{h}_{i}^{\\{b,f\\}}=\begin{cases}C\left(e_{i},\bar{h}_{i}^{\\{b,f\\}}\right)&\text{if
}i\in I_{key},\\\ \\\ \bar{h_{i}}^{\\{b,f\\}}&\text{otherwise},\end{cases}\\\
\end{split}$ (4)

where $E$ and $C$ correspond to the feature extractor and convolution,
respectively. $I_{key}$ denotes the set of indices of the selected keyframes.
The refined features are then passed to the residual blocks for further
refinement:

$h_{i}^{\\{b,f\\}}=R_{\\{b,f\\}}(x_{i},\hat{h}_{i}^{\\{b,f\\}}).$ (5)

It is noteworthy that the feature extractor and feature fusion are applied to
the sparsely-selected keyframes only. Hence, the computational burden brought
by the information-refill mechanism is insignificant.

While information-refill inherits the idea of keyframes, we remark here that
unlike existing interval-based methods [15, 35] that isolate the intervals for
independent processing, the intervals (separated by the keyframes) in IconVSR
are connected to maintain a global information propagation.

Table 2: Quantitative comparison (PSNR/SSIM). All results are calculated on
Y-channel except REDS4 [23] (RGB-channel). Red and blue colors indicate the
best and the second-best performance, respectively. Blanked entries correspond
to results unable to be reported. The runtime is computed on an LR size of
$180{\times}320$.

|  |  | BI degradation | BD degradation
---|---|---|---|---
Params (M) | Runtime (ms) | REDS4 [23] | Vimeo-90K-T [33] | Vid4 [21] | UDM10 [34] | Vimeo-90K-T [33] | Vid4 [21]
Bicubic | - | - | 26.14/0.7292 | 31.32/0.8684 | 23.78/0.6347 | 28.47/0.8253 | 31.30/0.8687 | 21.80/0.5246
VESPCN [1] | - | - | - | - | 25.35/0.7557 | - | - | -
SPMC [29] | - | - | - | - | 25.88/0.7752 | - | - | -
TOFlow [33] | - | - | 27.98/0.7990 | 33.08/0.9054 | 25.89/0.7651 | 36.26/0.9438 | 34.62/0.9212 | -
FRVSR [25] | 5.1 | 137 | - | - | - | 37.09/0.9522 | 35.64/0.9319 | 26.69/0.8103
DUF [16] | 5.8 | 974 | 28.63/0.8251 | - | - | 38.48/0.9605 | 36.87/0.9447 | 27.38/0.8329
RBPN [9] | 12.2 | 1507 | 30.09/0.8590 | 37.07/0.9435 | 27.12/0.8180 | 38.66/0.9596 | 37.20/0.9458 | -
EDVR-M [32] | 3.3 | 118 | 30.53/0.8699 | 37.09/0.9446 | 27.10/0.8186 | 39.40/0.9663 | 37.33/0.9484 | 27.45/0.8406
EDVR [32] | 20.6 | 378 | 31.09/0.8800 |  37.61/0.9489 |  27.35/0.8264 | 39.89/0.9686 |  37.81/0.9523 | 27.85/0.8503
PFNL [34] | 3.0 | 295 | 29.63/0.8502 | 36.14/0.9363 | 26.73/0.8029 | 38.74/0.9627 | - | 27.16/0.8355
MuCAN [20] | - | - | 30.88/0.8750 | 37.32/0.9465 | - | - | - | -
TGA [13] | 5.8 | - | - | - | - | - | 37.59/0.9516 | 27.63/0.8423
RLSP [8] | 4.2 | 49 | - | - | - | 38.48/0.9606 | 36.49/0.9403 | 27.48/0.8388
RSDN [12] | 6.2 | 94 | - | - | - | 39.35/0.9653 | 37.23/0.9471 | 27.92/0.8505
RRN [14] | 3.4 | 45 | - | - | - | 38.96/0.9644 | - | 27.69/0.8488
BasicVSR (ours) | 6.3 | 63 |  31.42/0.8909 | 37.18/0.9450 | 27.24/0.8251 |  39.96/0.9694 | 37.53/0.9498 |  27.96/0.8553
IconVSR (ours) | 8.7 | 70 |  31.67/0.8948 |  37.47/0.9476 |  27.39/0.8279 |  40.03/0.9694 |  37.84/0.9524 |  28.04/0.8570

Coupled Propagation. In bidirectional settings, features are typically
propagated in two opposite directions independently. In this design, the
features in each propagation branch are computed based on partial information,
from either previous frames or future frames. To exploit the information in
the sequences, we propose a coupled propagation scheme, where the propagation
modules are inter-connected. As depicted in Fig. 5(b), in coupled propagation,
the features propagated backward $h_{i}^{b}$ are taken as inputs in the
forward propagation module ( Eq. 1, 3):

$\begin{split}&h_{i}^{b}=F_{b}(x_{i},x_{i+1},h_{i+1}^{b}),\\\
&h_{i}^{f}=F_{f}(x_{i},x_{i-1},{h_{i}^{b}},h_{i-1}^{f}),\\\
&y_{i}=U(h_{i}^{f}).\end{split}$ (6)

With coupled propagation, the forward propagation branch receives information
from both past and future frames, leading to features of higher quality and
hence better outputs. More importantly, since coupled propagation requires
only changes of the branch connections, the performance gain can be obtained
without introducing computational overhead.

Figure 6: Qualitative comparison on REDS4 [23]. BasicVSR and IconVSR restores
clearer square patterns. IconVSR restores sharper edges. (Zoom-in for best
view) Figure 7: Qualitative comparison on Vimeo-90K-T [33]. Only BasicVSR and
IconVSR are able to recover the vertical strip patterns. IconVSR restores
sharper edges. (Zoom-in for best view)

##  4 Experiments

Datasets and Settings We consider two widely-used datasets for training: REDS
[23] and Vimeo-90K [33]. For REDS, following [32], we use the REDS4
dataset222Clips 000, 011, 015, 020 of REDS training set. as our test set. We
additionally define REDSval4333Clips 000, 001, 006, 017 of REDS validation
set. as our validation set. The remaining clips are used for training. We use
Vid4 [21], UDM10 [34], and Vimeo-90K-T [33] as test sets along with Vimeo-90K.
We test our models with $4{\times}$ downsampling using two degradations –
Bicubic (BI) and Blur Downsampling (BD).

We use pre-trained SPyNet [24] and EDVR-M444A lightweight version of EDVR.
[32] as our flow estimation module and feature extractor, respectively. We
adopt Adam optimizer [18] and Cosine Annealing scheme [22]. The initial
learning rates of the feature extractor and flow estimator are set to
$1{\times}10^{-4}$ and $2.5{\times}10^{-5}$, respectively. The learning rate
for all other modules is set to $2{\times}10^{-4}$. The total number of
iterations is 300K, and the weights of the feature extractor and flow
estimator are fixed during the first 5,000 iterations. The batch size is 8 and
the patch size of input LR frames is $64{\times}64$. We use Charbonnier loss
[3] since it better handles outliers and improves the performance over the
conventional $\ell_{2}$ loss [19]. Detailed experimental settings are provided
in the appendix.

###  4.1 Comparisons with State-of-the-Art Methods

We conduct comprehensive experiments by comparing BasicVSR and IconVSR with 14
models: VESPCN [1], SPMC [29], TOFlow [33], FRVSR [25], DUF [16], RBPN [9],
EDVR-M [32], EDVR [32], MuCAN [20], PFNL [34], RLSP [8], TGA [13], RSDN [12],
and RRN [14]. The quantitative results are summarized in Table 2 and the speed
and performance comparison is provided in Fig. 1. Note that the parameters of
BasicVSR and IconVSR are inclusive of that in the optical flow network,
SPyNet. So the comparison is fair.

BasicVSR. BasicVSR outperforms existing state of the arts on various datasets,
including REDS4, UDM10, and Vid4. BasicVSR also demonstrates high efficiency
in addition to improvements in restoration quality. As shown in Fig. 1,
BasicVSR surpasses RSDN [12] by 0.61 dB on UDM10 while having a similar number
of parameters. When compared with EDVR [32], which has a significantly larger
complexity, BasicVSR obtains a marked improvement of 0.33 dB on REDS4 and
competitive performances on Vimeo-90K-T and Vid4. We note that the performance
of BasicVSR on Vimeo-90K-T is slightly lower than that achieved by sliding-
window methods such as EDVR [32] and TGA [13]. This is expected since
Vimeo-90K-T contains sequences with only seven frames, while the success of
BasicVSR partially comes from the aggregation of long-term information (which
is a realistic assumption).

IconVSR. IconVSR further improves the performance by up to 0.31 dB over
BasicVSR with slightly longer runtime. The performance gain is especially
obvious in Vimeo-90K-T and REDS4, showing that our proposed coupled
propagation and information-refill mechanisms are beneficial in videos (1)
lacking long-term information (Vimeo-90K-T) and (2) containing large and
complicated motions (REDS4). Overall, both BasicVSR and IconVSR are able to
achieve remarkable performance while being faster than most state of the arts.

Qualitative comparisons are shown in Figures 11 and 12. BasicVSR and IconVSR
are able to recover finer details and sharper edges. For instance, only
BasicVSR and IconVSR successfully recover clear square patterns in Fig. 11 and
the vertical strip patterns in Fig. 12. With the proposed components, IconVSR
is able to reconstruct images with sharper edges. More examples are provided
in the appendix.

##  5 Ablation Studies

Figure 8: (a) Information lost during spatial warping can be compensated by
the additional features. (b) With more effective use of the backward-
propagated features, coupled propagation leads to clearer details and finer
edges, especially in regions that are occluded in previous frames and regions
that exist in the whole sequence. (Zoom-in for best view) Figure 9: Effect of
Information-Refill. The contribution of information-refill is more obvious in
regions with fine details, where alignment is error-prone. The information
from the additional feature extractor leads to marked improvements.

###  5.1 From BasicVSR to IconVSR

Information-Refill. We qualitatively visualize the features before and after
information-refill to gain insights into the mechanism. As shown in Fig. 8(a),
before information-refill, the boundary pixels in the warped feature
essentially become zero due to non-existing correspondences. The lost
information inevitably worsens the feature quality, leading to degraded
outputs. With our information-refill mechanism, the additional features can be
used to “refill” the lost information in regions where the features are poorly
aligned. The retrieved information can then be employed for the subsequent
feature refinement and propagation.

The above effect is especially obvious in regions with fine details. In those
regions, information from neighboring frames cannot be effectively aggregated
due to alignment error, often resulting in inferior quality. With information-
refill, the additional features assist in the restoration of the details,
leading to in improved quality. For example, as shown in Fig. 9, the license
plate number can be reconstructed more clearly with the refill mechanism.

Coupled Propagation. To ablate the coupled propagation scheme, we disable the
information-refill mechanism and compare IconVSR with BasicVSR. In Fig. 8(b),
the yellow box represents a region occluded in previous frames, and the
forward propagation branch in BasicVSR could not receive information of that
region. The red box denotes a region that exists in all frames of the
sequence, and hence abundant “snapshots” of the region can be found in latter
frames. With coupled propagation, the backward-propagated features are
employed more effectively, and hence more details and finer edges can be
reconstructed. The PSNR improvement over BasicVSR is summarized in Table 3.

Table 3: Evaluations of IconVSR components. The two components bring an
improvement of up to 0.28 dB over BasicVSR. The PSNR is computed on
REDS4/REDSval4.

| BasicVSR |  IconVSR (w/o refill) | IconVSR
---|---|---|---
Info-Refill | ✗ | ✗ | ✓
Coupled-Prop | ✗ | ✓ | ✓
PSNR | 31.42/30.17 | 31.60/30.38 | 31.67/30.45

Figure 10: Tradeoff in IconVSR. One can reduce the number of keyframes for
faster inference. The PSNR is positively correlated with the number of
keyframes $N$, indicating the effectiveness of the information-refill
mechanism. The PSNR is calculated on REDSval4. The total number of frames in
each clip is 100, and the keyframes are evenly spaced.

###  5.2 Tradeoff in IconVSR

Although IconVSR is trained with a fixed keyframe interval, one can reduce the
number of keyframes for faster inference. The PSNR using different numbers of
keyframes is depicted in Fig. 10, where we see that the PSNR is positively
correlated with the number of keyframes, verifying the contributions of the
information-refill mechanism. In an extreme case when there is no keyframe,
IconVSR degenerates to a recurrent network. Nevertheless, it still achieves a
PSNR of 30.38 dB on REDSval4, which is 0.21 dB higher than BasicVSR. This
demonstrates the effectiveness of our coupled propagation scheme, which can be
used without introducing additional computational overhead.

##  6 Conclusion

This work devotes attention to the search of generic and efficient VSR
baselines to ease the analysis and extension of VSR approaches. Through
decomposing and analyzing existing elements, we propose BasicVSR, a simple yet
effective network that outperforms existing state of the arts with high
efficiency. We build upon BasicVSR and propose IconVSR with two novel
components to further improve the performance. BasicVSR and IconVSR can serve
as strong baselines for future works, and the discovery on the architecture
designs could potentially be extended to other low-level vision tasks, such as
video deblurring, denoising and colorization.

Acknowledgement. This research was conducted in collaboration with SenseTime
and supported by the Singapore Government through the Industry Alignment Fund
- Industry Collaboration Projects Grant. It is also partially supported by
Singapore MOE AcRF Tier 1 (2018-T1-002-056) and NTU SUG.

## References

  * [1] Jose Caballero, Christian Ledig, Aitken Andrew, Acosta Alejandro, Johannes Totz, Zehan Wang, and Wenzhe Shi.  Real-time video super-resolution with spatio-temporal networks and motion compensation.  In CVPR, 2017.
  * [2] Kelvin CK Chan, Xintao Wang, Ke Yu, Chao Dong, and Chen Change Loy.  Understanding deformable alignment in video super-resolution.  arXiv preprint arXiv:2009.07265.
  * [3] Pierre Charbonnier, Laure Blanc-Feraud, Gilles Aubert, and Michel Barlaud.  Two deterministic half-quadratic regularization algorithms for computed imaging.  In ICIP, 1994.
  * [4] Kai Chen, Jiaqi Wang, Shuo Yang, Xingcheng Zhang, Yuanjun Xiong, Chen Change Loy, and Dahua Lin.  Optimizing video object detection via a scale-time lattice.  In CVPR, 2018.
  * [5] Jifeng Dai, Haozhi Qi, Yuwen Xiong, Yi Li, Guodong Zhang, Han Hu, and Yichen Wei.  Deformable convolutional networks.  In ICCV, 2017.
  * [6] Chao Dong, Chen Change Loy, Kaiming He, and Xiaoou Tang.  Learning a deep convolutional network for image super-resolution.  In ECCV, 2014.
  * [7] Chao Dong, Chen Change Loy, Kaiming He, and Xiaoou Tang.  Image super-resolution using deep convolutional networks.  TPAMI, 38(2):295–307, 2016.
  * [8] Dario Fuoli, Shuhang Gu, and Radu Timofte.  Efficient video super-resolution through recurrent latent space propagation.  In ICCVW, 2019.
  * [9] Muhammad Haris, Greg Shakhnarovich, and Norimichi Ukita.  Recurrent back-projection network for video super-resolution.  In CVPR, 2019.
  * [10] Yan Huang, Wei Wang, and Liang Wang.  Bidirectional recurrent convolutional networks for multi-frame super-resolution.  In NeurIPS, 2015.
  * [11] Yan Huang, Wei Wang, and Liang Wang.  Video super-resolution via bidirectional recurrent convolutional networks.  TPAMI, 2018.
  * [12] Takashi Isobe, Xu Jia, Shuhang Gu, Songjiang Li, Shengjin Wang, and Qi Tian.  Video super-resolution with recurrent structure-detail network.  In ECCV, 2020.
  * [13] Takashi Isobe, Songjiang Li, Xu Jia, Shanxin Yuan, Gregory Slabaugh, Chunjing Xu, Ya-Li Li, Shengjin Wang, and Qi Tian.  Video super-resolution with temporal group attention.  In CVPR, 2020.
  * [14] Takashi Isobe, Fang Zhu, and Shengjin Wang.  Revisiting temporal modeling for video super-resolution.  In BMVC, 2020.
  * [15] Samvit Jain, Xin Wang, and Joseph E Gonzalez.  Accel: A corrective fusion network for efficient semantic segmentation on video.  In CVPR, 2019.
  * [16] Younghyun Jo, Seoung Wug Oh, Jaeyeon Kang, and Seon Joo Kim.  Deep video super-resolution network using dynamic upsampling filters without explicit motion compensation.  In CVPR, 2018.
  * [17] Tae Hyun Kim, Mehdi S M Sajjadi, Michael Hirsch, and Bernhard Schölkopf.  Spatio-temporal transformer network for video restoration.  In ECCV, 2018.
  * [18] Diederik Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In ICLR, 2015.
  * [19] Wei-Sheng Lai, Jia-Bin Huang, Narendra Ahuja, and Ming-Hsuan Yang.  Deep laplacian pyramid networks for fast and accurate super-resolution.  In CVPR, pages 5835–5843, 2017.
  * [20] Wenbo Li, Xin Tao, Taian Guo, Lu Qi, Jiangbo Lu, and Jiaya Jia.  MuCAN: Multi-correspondence aggregation network for video super-resolution.  In ECCV, 2020.
  * [21] Ce Liu and Deqing Sun.  On bayesian adaptive video super resolution.  TPAMI, 2014.
  * [22] Ilya Loshchilov and Frank Hutter.  SGDR: Stochastic gradient descent with warm restarts.  arXiv preprint arXiv:1608.03983, 2016.
  * [23] Seungjun Nah, Sungyong Baik, Seokil Hong, Gyeongsik Moon, Sanghyun Son, Radu Timofte, and Kyoung Mu Lee.  NTIRE 2019 challenge on video deblurring and super-resolution: Dataset and study.  In CVPRW, 2019.
  * [24] Anurag Ranjan and Michael J Black.  Optical flow estimation using a spatial pyramid network.  In CVPR, 2017.
  * [25] Mehdi S M Sajjadi, Raviteja Vemulapalli, and Matthew Brown.  Frame-recurrent video super-resolution.  In CVPR, 2018.
  * [26] Evan Shelhamer, Kate Rakelly, Judy Hoffman, and Trevor Darrell.  Clockwork convnets for video semantic segmentation.  In ECCV, 2016.
  * [27] Wenzhe Shi, Jose Caballero, Ferenc Huszár, Johannes Totz, Andrew P Aitken, Rob Bishop, Daniel Rueckert, and Zehan Wang.  Real-time single image and video super-resolution using an efficient sub-pixel convolutional neural network.  In CVPR, pages 1874–1883, 2016.
  * [28] Hiroyuki Takeda, Peyman Milanfar, Matan Protter, and Michael Elad.  Super-resolution without explicit subpixel motion estimation.  TIP, 18(9):1958–1975, 2009.
  * [29] Xin Tao, Hongyun Gao, Renjie Liao, Jue Wang, and Jiaya Jia.  Detail-revealing deep video super-resolution.  In CVPR, 2017.
  * [30] Yapeng Tian, Yulun Zhang, Yun Fu, and Chenliang Xu.  TDAN: Temporally deformable alignment network for video super-resolution.  In CVPR, 2020.
  * [31] Hua Wang, Dewei Su, Chuangchuang Liu, Longcun Jin, Xianfang Sun, and Xinyi Peng.  Deformable non-local network for video super-resolution.  IEEE Access, 2019.
  * [32] Xintao Wang, Kelvin C.K. Chan, Ke Yu, Chao Dong, and Chen Change Loy.  EDVR: Video restoration with enhanced deformable convolutional networks.  In CVPRW, 2019.
  * [33] Tianfan Xue, Baian Chen, Jiajun Wu, Donglai Wei, and William T Freeman.  Video enhancement with task-oriented flow.  IJCV, 2019.
  * [34] Peng Yi, Zhongyuan Wang, Kui Jiang, Junjun Jiang, and Jiayi Ma.  Progressive fusion video super-resolution network via exploiting non-local spatio-temporal correlations.  In ICCV, 2019.
  * [35] Zhengdong Zhang and Vivienne Sze.  FAST: A framework to accelerate super-resolution processing on compressed videos.  In CVPRW, 2017.
  * [36] Xizhou Zhu, Jifeng Dai, Xingchi Zhu, Yichen Wei, and Lu Yuan.  Towards high performance video object detection for mobiles.  arXiv preprint arXiv:1804.05830, 2018.
  * [37] Xizhou Zhu, Han Hu, Stephen Lin, and Jifeng Dai.  Deformable convnets v2: More deformable, better results.  In CVPR, 2019.
  * [38] Xizhou Zhu, Yujie Wang, Jifeng Dai, Lu Yuan, and Yichen Wei.  Flow-guided feature aggregation for video object detection.  In ICCV, 2017.
  * [39] Xizhou Zhu, Yuwen Xiong, Jifeng Dai, Lu Yuan, and Yichen Wei.  Deep feature flow for video recognition.  In CVPR, 2017.

## Appendix

##  Appendix A Architecture and Experimental Settings

Architecture. In all our models, we adopt SPyNet [24] as our flow estimator
because of its simplicity and efficiency. We use 30 residual blocks in each
propagation branch. The feature channel is set to 64. In IconVSR, we adopt
EDVR-M555A lightweight version of EDVR. [32] as the additional feature
extractor since it maintains a good balance between efficiency and quality.
The complexity of the components are summarized in Table 4. BasicVSR and
IconVSR share the same flow estimator and main network. The main network is a
lightweight network, consisting of only 4.9M parameters.

Table 4: Model complexity of BasicVSR and IconVSR.

| BasicVSR | IconVSR
---|---|---
Flow Estimator | 1.4M | 1.4M
Main Network | 4.9M | 4.9M
Feature Extractor | - | 2.4M
Total | 6.3M | 8.7M

The flow estimator and feature extractor are fine-tuned together with the main
network. In all our experiments, every five frames are selected as keyframes.
Note that the feature extractor is applied to keyframes only. Therefore, the
computational burden brought by it is insignificant.

Datasets. We consider two widely-used datasets for training: REDS [23] and
Vimeo-90K [33]. For REDS, following [32], we use the REDS4 dataset666Clips
000, 011, 015, 020 of REDS training set. as our test set. We additionally
define REDSval4777Clips 000, 001, 006, 017 of REDS validation set. as our
validation set. The remaining clips are used for training. We use Vid4 [21],
UDM10 [34], and Vimeo-90K-T [33] as test sets along with Vimeo-90K.

Experimental Settings. When training on REDS, we use a sequence of 15 frames
as inputs, and loss is computed for the 15 output images. When training on
Vimeo-90K, we temporally augment the sequence by flipping the original input
sequence to allow longer propagation. In other words, we train with a sequence
of 14 frames. During inference, we take the whole video sequence as input.

We adopt Adam optimizer [18] and Cosine Annealing scheme [22]. The initial
learning rates of the feature extractor and flow estimator are set to
$1{\times}10^{-4}$ and $2.5{\times}10^{-5}$, respectively. The learning rate
for all other modules is set to $2{\times}10^{-4}$. The total number of
iterations is 300K, and the weights of the feature extractor and flow
estimator are fixed during the first 5,000 iterations. The batch size is 8 and
the patch size of input LR frames is $64{\times}64$.

Loss Function. We use Charbonnier loss [3] since it better handles outliers
and improves the performance over the conventional $\ell_{2}$ loss [19]:

$\mathcal{L}=\dfrac{1}{N}\sum_{i=0}^{N}\rho(y_{i}-z_{i}),$ (7)

where $\rho(x)=\sqrt{x^{2}+\epsilon^{2}}$, $\epsilon{=}1{\times}10^{-8}$,
$z_{i}$ denotes the ground-truth HR frame, and $N$ denotes to the number of
pixels.

Degradations. We train and test our models with $4{\times}$ downsampling using
two degradations – Bicubic (BI) and Blur Downsampling (BD) [12, 25]. For BI,
we use the MATLAB function imresize for downsampling. For BD, we blur the
ground-truths by a Gaussian filter with $\sigma{=}1.6$, followed by a
subsampling every four pixels.

Implementation. We implement our models with PyTorch and train the models
using two NVIDIA Tesla V100 GPUs. Codes will be made publicly available.

##  Appendix B Qualitative Results

###  B.1 Comparison with State of the Arts

In this section, we provide additional qualitative comparisons on REDS4 [23],
Vimeo-90K [33], Vid4 [21], and UDM10 [34]. In Fig. 11 to Fig. 14, it is
observed that BasicVSR and IconVSR successfully produce outputs with finer
details and sharper edges. Furthermore, with the proposed information-refill
and coupled propagation, IconVSR further improves the quality of the outputs.

Figure 11: Qualitative comparison on REDS [23]. Figure 12: Qualitative
comparison on Vimeo-90K [33]. Figure 13: Qualitative comparison on Vid4 [21].
Figure 14: Qualitative comparison on UDM10 [34].

###  B.2 BasicVSR vs IconVSR

In Fig. 15, we provide additional visual comparison of BasicVSR and IconVSR to
demonstrate the effectiveness of our proposed components. We see that (1)
information-refill improves the output quality on the fine regions, where
alignment is error-prone, and (2) coupled propagation leads to sharper edges
by better employing the long-term information in the sequence.

Figure 15: Ablation of IconVSR. With information-refill and coupled
propagation, IconVSR produces outputs with details and sharper edges.