# Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace
Embeddings111This paper appeared in the Proceedings of RANDOM/APPROX 2016,
LIPIcs Vol. 60, 39:1–39:11. The current version corrects the proof of
Corollary 7. Yi Li was supported by ONR grant N00014-14-1-0632 when he was at
Harvard University, where the major part of this work was done. David P.
Woodruff was at IBM Research Almaden when this work was done.

Yi Li
School of Physical and Mathematical Sciences
Nanyang Technological University
<EMAIL_ADDRESS>
David P. Woodruff
Department of Computer Science
Carnegie Mellon University
<EMAIL_ADDRESS>
###### Abstract

We consider the following oblivious sketching problem: given
$\epsilon\in(0,1/3)$ and $n\geq d/\epsilon^{2}$, design a distribution
$\mathcal{D}$ over $\mathbb{R}^{k\times nd}$ and a function
$f:\mathbb{R}^{k}\times\mathbb{R}^{nd}\rightarrow\mathbb{R}$, so that for any
$n\times d$ matrix $A$,

$\Pr_{S\sim\mathcal{D}}[(1-\epsilon)\|A\|_{op}\leq
f(S(A),S)\leq(1+\epsilon)\|A\|_{op}]\geq 2/3,$

where $\|A\|_{op}=\sup_{x:\|x\|_{2}=1}\|Ax\|_{2}$ is the operator norm of $A$
and $S(A)$ denotes $S\cdot A$, interpreting $A$ as a vector in
$\mathbb{R}^{nd}$. We show a tight lower bound of
$k=\Omega(d^{2}/\epsilon^{2})$ for this problem. Previously, Nelson and Nguyen
(ICALP, 2014) considered the problem of finding a distribution $\mathcal{D}$
over $\mathbb{R}^{k\times n}$ such that for any $n\times d$ matrix $A$,

$\Pr_{S\sim\mathcal{D}}[\forall x,\
(1-\epsilon)\|Ax\|_{2}\leq\|SAx\|_{2}\leq(1+\epsilon)\|Ax\|_{2}]\geq 2/3,$

which is called an oblivious subspace embedding (OSE). Our result considerably
strengthens theirs, as it (1) applies only to estimating the operator norm,
which can be estimated given any OSE, and (2) applies to distributions over
general linear operators $S$ which treat $A$ as a vector and compute $S(A)$,
rather than the restricted class of linear operators corresponding to matrix
multiplication. Our technique also implies the first tight bounds for
approximating the Schatten $p$-norm for even integers $p$ via general linear
sketches, improving the previous lower bound from $k=\Omega(n^{2-6/p})$
[Regev, 2014] to $k=\Omega(n^{2-4/p})$. Importantly, for sketching the
operator norm up to a factor of $\alpha$, where $\alpha-1=\Omega(1)$, we
obtain a tight $k=\Omega(n^{2}/\alpha^{4})$ bound, matching the upper bound of
Andoni and Nguyen (SODA, 2013), and improving the previous
$k=\Omega(n^{2}/\alpha^{6})$ lower bound. Finally, we also obtain the first
lower bounds for approximating Ky Fan norms.

##  1 Introduction

Understanding the sketching complexity of estimating matrix norms [4, 14, 25,
30] has been a goal of recent work, generalizing a line of work on estimating
frequency moments in the sketching model [3, 18, 24], and in the somewhat
related streaming model of computation [1].

In the sketching model, one fixes a distribution $\mathcal{D}$ over
$k\times(nd)$ matrices $S$, and is then given an $n\times d$ matrix $A$ which,
without loss of generality, satisfies $n\geq d$. One then samples $S$ from
$\mathcal{D}$, and computes $S(A)$, which denotes the operation of treating
$A$ as a column vector in $\mathbb{R}^{nd}$ and left-multiplying that vector
by the matrix $S$. Any linear transformation applied to $A$ can be expressed
in this form, and therefore we sometimes refer to such a distribution
$\mathcal{D}$ as a general linear sketch. There is also the related notion of
a bilinear sketch, in which one fixes a distribution $\mathcal{D}$ over
$k\times n$ matrices $S$, and is then given an $n\times d$ matrix $A$. One
samples $S$ from $\mathcal{D}$ and computes $S\cdot A$. Bilinear sketches are
special cases of general linear sketches since they form a subclass of all
possible linear transformations of $A$, and general linear sketches can be
much more powerful than bilinear sketches. For example, to compute the trace
exactly of an $n\times n$ matrix $A$, setting $k=1$ suffices for a general
linear sketch, while we do not know how to compute the trace with a small
value $k$ for bilinear sketches, and several lower bounds on $k$ are known
even to approximate the trace [29].

The goal in the sketching model is to minimize the sketching dimension $k$ so
that $S(A)$ can be used to approximate a property of $A$ with constant
probability. Associated with distribution $\mathcal{D}$ is an estimation
procedure, which we model as a function $f$, for which $f(S(A),S)$ outputs a
correct answer to the problem at hand with constant probability. For numerical
properties, such as estimating a norm of $A$, this probability can be
amplified to $1-\delta$, by creating a distribution $\mathcal{D}^{\prime}$
corresponding to taking $O(\log(1/\delta))$ independent copies
$S^{1},\ldots,S^{\log(1/\delta)}$ from $\mathcal{D}$, and outputting the
median of

$f(S^{1}(A),S^{1}),f(S^{2}(A),S^{2}),\ldots,f(S^{\log(1/\delta)}(A),S^{\log(1/\delta)}).$

Notice that the mapping $S$ is linear and oblivious, both of which are
important for a number of applications such as merging sketches in distributed
computation, or for approximately recovering a signal in compressed sensing.
Minimizing $k$ is crucial for these applications, as it corresponds to the
communication or number of observations of the underlying algorithm.

A quantity of interest is the operator norm. Given a matrix $A$, the operator
norm $\|A\|_{op}$ is defined to be
$\|A\|_{op}=\sup_{x:\|x\|_{2}=1}\|Ax\|_{2}$. The operator norm arises in
several applications; for example one sometimes approximates a matrix $A$ by
another matrix $\hat{A}$ for which $\|A-\hat{A}\|_{2}$ is small. Often
$\hat{A}$ has low rank, in which case this is the low rank approximation
problem with spectral error, see, e.g., recent work on this [21]. If one had
an estimator for the operator norm of $A-\hat{A}$, one could use it to verify
if $\hat{A}$ is a good approximation to $A$. Given the linearity in the
sketching model, if $S$ is sampled from a distribution $D$, one can compute
$S(A)-S(\hat{A})=S(A-\hat{A})$, from which one then has an estimation
procedure to estimate $\|A-\hat{A}\|_{2}$ as $f(S(A-\hat{A}),S)$. In the
sketching model, it was first shown that approximating the operator norm up to
a constant factor requires $k=\Omega(d^{3/2})$ [14], which was later improved
by Regev to the tight $k=\Omega(d^{2})$ [30, Section 6.2]. Note that these
lower bounds rule out any possible function $f$ as the estimation procedure.
It is also implicit in [30, Section 6.2] that approximating the operator norm
up to a factor $\alpha$, where $\alpha-1=\Omega(1)$, requires
$k=\Omega(d^{2}/\alpha^{6})$. Andoni and Nguyen showed an upper bound of
$k=O(d^{2}/\alpha^{4})$ [2], that is, they constructed a distribution
$\mathcal{D}$ and corresponding estimation procedure $f$ for which it suffices
to set $k=O(d^{2}/\alpha^{4})$. This follows by Theorem 1.2 of [2].

A wide class of matrix norms is the Schatten $p$-norms, which are the
analogues of $\ell_{p}$-norms of vectors and contain the operator norm as a
special case. The Schatten $p$-norm of matrix $A$ is denoted by $\|A\|_{p}$
and defined to be $\|A\|_{p}=(\sum_{i=1}^{n}(\sigma_{i}(A))^{p})^{1/p}$, where
$\sigma_{1},\dots,\sigma_{n}$ are the singular values of $A$. When $p<1$,
$\|A\|_{p}$ is not a norm but still a well-defined quantity. For $p=0$,
viewing $\|A\|_{0}$ as the limit $\lim_{p\to 0^{+}}\|A\|_{p}$ recovers exactly
the rank of $A$, which has been studied in the data stream [4, 6] and property
testing models [11, 17]. When $p=1$, it is the nuclear or trace norm222The
trace norm is not to be confused with the trace. These two quantities only
coincide if $A$ is positive semidefinite., which has applications in
differential privacy [9, 13] and non-convex optimization [5, 8]. When $p=2$,
it is the Frobenius norm, and when $p\to\infty$, it holds that $\|A\|_{p}$
tends to $\|A\|_{op}$. Such norms are useful in geometry and linear algebra,
see, e.g., [30]. A $k=\Omega(\sqrt{d})$ lower bound for every $p\geq 0$ was
shown in [15]. For $p>2$ a lower bound on the sketching dimension of
$k=\Omega(d^{2/3-3/p})$, and an upper bound of $k=O(d^{2-4/p})$ were shown in
[15]. The upper bound is only known to hold when $p$ is an even integer. The
lower bound was improved by Regev to $k=\Omega(d^{2-6/p})$ for $p>6$ [30,
Section 6.2]333The section discusses only the case of $p=\infty$, i.e., the
operator norm, but the same method can be used for general $p$ and gives the
bound claimed here..

Other related work includes that on oblivious subspace embeddings (OSEs),
which fall into the category of bilinear sketches. Here one seeks a
distribution $\mathcal{D}$ over $\mathbb{R}^{k\times n}$ such that for any
$n\times d$ matrix $A$,

$\Pr_{S\sim\mathcal{D}}[\forall x,\
(1-\epsilon)\|Ax\|_{2}\leq\|SAx\|_{2}\leq(1+\epsilon)\|Ax\|_{2}]\geq 2/3.$

This notion has proved important in numerical linear algebra, and has led to
the fastest known algorithms for low rank approximation and regression [7, 20,
22]. Since an OSE has the property that $\|SAx\|_{2}=(1\pm\epsilon)\|Ax\|_{2}$
for all $x$, it holds in particular that
$\|SA\|_{op}=(1\pm\epsilon)\|A\|_{op}$, where the notation $a=(1\pm\epsilon)b$
means $(1-\epsilon)b\leq a\leq(1+\epsilon)b$. When $n\geq d/\epsilon^{2}$,
Nelson and Nguyen show the tight bound that any OSE requires
$k=\Omega(d/\epsilon^{2})$ [23].

Finally, we mention recent related work in the data stream model on
approximation of matrix norms [4, 19]. Here one sees elements of $A$ one at a
time and the goal is to output an approximation to $\|A\|_{p}$. It is
important to note that the data stream model and sketching models are
incomparable. The main reason for this is that unlike in the data stream
model, the bit complexity is not accounted for in the sketching model, and
both $S$ and $A$ are assumed to have entries which are real numbers. The
latter is the common model adopted in compressed sensing. In the data stream
model, if one wants to output a vector $v\in\\{0,1,\ldots,M-1,M\\}^{n}$, one
needs $n\log M$ bits of space. On the other hand, if $u$ is the vector
$(1,(M+1),(M+1)^{2},(M+1)^{3},\ldots,(M+1)^{n})$, then from $\langle
u,v\rangle$, one can output $v$, so the sketching dimension $k$ is only equal
to $1$. The sketching complexity thus gives a meaningful measure of complexity
in the real RAM model. Conversely, lower bounds in the sketching model do not
translate into lower bounds in the data stream model. This statement holds
even given the work of [14] which characterizes turnstile streaming algorithms
as linear sketches. The problem is that lower bounds in the sketching model
involve continuous distributions and after discretizing the distributions it
is no longer clear if the lower bounds hold.

###  1.1 Our Contributions

In this paper we strengthen known sketching lower bounds for the operator
norm, Schatten $p$-norms, and subspace embeddings. Our lower bounds are
optimal for any approximation to the operator norm, for subspace embeddings,
and for Schatten $p$-norms for even integers $p$. We first describe our
results for the operator norm, as the results for Schatten $p$-norms and
subspace embeddings follow from them.

We consider the following problem: given $\epsilon\in(0,1/3)$ and $n\geq
d/\epsilon^{2}$, design a distribution $\mathcal{D}$ over $\mathbb{R}^{k\times
nd}$ and a function $f:\mathbb{R}^{k}\times\mathbb{R}^{k\times
nd}\rightarrow\mathbb{R}$, so that for any $n\times d$ matrix $A$,

$\Pr_{S\sim\mathcal{D}}[(1-\epsilon)\|A\|_{op}\leq
f(S(A),S)\leq(1+\epsilon)\|A\|_{op}]\geq 2/3,$

For this problem, we show a tight $k=\Omega(d^{2}/\epsilon^{2})$ lower bound.
Our result considerably strengthens the result of Nelson and Nguyen [23] as it
(1) applies only to estimating the operator norm, which can be estimated given
any OSE, and (2) applies to general linear sketches rather than only to
bilinear sketches. Regarding (1), this shows that designing a general linear
sketch for approximating the operator norm of a matrix is as hard as designing
an oblivious subspace embedding. Regarding (2), we lower bound a much larger
class of data structures than OSEs that one could use to approximate
$\|Ax\|_{2}$ for all vectors $x$.

We then generalize the argument above to handle approximation factors
$\alpha$, with $\alpha-1=\Omega(1)$, for approximating the operator norm. In
this case we consider $n=d$, which is without loss of generality since by
first applying an OSE $S$ to $A$ with $k=O(d)$, replacing $A$ with $S\cdot A$,
all singular values of $A$ are preserved up to a constant factor (we can also
pad $SA$ with zero columns to make $SA$ be a square matrix) - see Appendix C
of [15]. We can then apply our general linear sketch to $SA$ (the composition
of linear sketches is a general linear sketch). We show a lower bound of
$k=\Omega(n^{2}/\alpha^{4})$, improving the previous
$k=\Omega(n^{2}/\alpha^{6})$ bound, and maching the $k=O(n^{2}/\alpha^{4})$
upper bound. This answers Open Question 2 in [15].

The proof shows the problem is already hard to distinguish between the two
cases: (1) $A$ has one singular value of value $\Theta(\alpha)$ and remaining
singular values of value $\Theta(1)$, versus (2) all singular values of $A$
are of value $\Theta(1)$. By setting $\alpha=n^{1/p}$, we are able to obtain a
constant factor gap in the Schatten-$p$ norm in the two cases, and therefore
additionally obtain an $\Omega(n^{2-4/p})$ lower bound for Schatten $p$-norms
for constant factor approximation. This improves the previous
$\Omega(n^{2-6/p})$ lower bound, and matches the known upper bound for even
integers $p$. Our proof also establishes a lower bound of
$k=\Omega(n^{2}/s^{2})$ for estimating the Ky-Fan $s$-norm of an $n\times n$
matrix $A$ up to a constant factor, whenever $s\leq.0789\sqrt{n}$.

Our main technical novelty is avoiding a deep theorem of Latała [12]
concerning tail bounds for Gaussian chaoses used in the prior lower bounds for
sketching the operator norm and Schatten $p$-norms. Instead we prove a simple
lemma (Lemma 3) allowing us to bound $\mathbb{E}_{x,y}[e^{x^{T}Ay}]$ for
Gaussian vectors $x$ and $y$ and a matrix $A$, in terms of the Frobenius norm
of $A$. Surprisingly, this lemma suffices for directly upper-bounding the
$\chi^{2}$-distance between the distributions considered in previous works,
and without losing any additional factors. Our technical arguments are thus
arguably more elementary and simpler than those given in previous work.

##  2 Preliminaries

### Notation.

Let $\mathbb{R}^{n\times d}$ be the set of $n\times d$ real matrices and
$N(\mu,\Sigma)$ denote the (multi-variate) normal distribution of mean $\mu$
and covariance matrix $\Sigma$. We write $X\sim\mathcal{D}$ for a random
variable $X$ subject to a probability distribution $\mathcal{D}$. Denote by
$\mathcal{G}(n,n)$ the ensemble of random matrices with entries i.i.d.
$N(0,1)$.

### Singular values and matrix norms.

Consider a matrix $A\in\mathbb{R}^{n\times n}$. Then $A^{T}A$ is a positive
semi-definite matrix. The eigenvalues of $\sqrt{A^{T}A}$ are called the
singular values of $A$, denoted by
$\sigma_{1}(A)\geq\sigma_{2}(A)\geq\cdots\geq\sigma_{n}(A)$ in decreasing
order. Let $r=\operatorname{rank}(A)$. It is clear that
$\sigma_{r+1}(A)=\cdots=\sigma_{n}(A)=0$. Define
$\|A\|_{p}=(\sum_{i=1}^{r}(\sigma_{i}(A))^{p})^{1/p}$ ($p>0$). For $p\geq 1$,
it is a norm over $\mathbb{R}^{n\times d}$, called the $p$-th Schatten norm,
over $\mathbb{R}^{n\times n}$ for $p\geq 1$. When $p=1$, it is also called the
trace norm or nuclear norm. When $p=2$, it is exactly the Frobenius norm
$\|A\|_{F}$. Let $\|A\|_{op}$ denote the operator norm of $A$ when treating
$A$ as a linear operator from $\ell_{2}^{n}$ to $\ell_{2}^{n}$. It holds that
$\lim_{p\to\infty}\|A\|_{p}=\sigma_{1}(A)=\|A\|_{op}$.

The Ky-Fan $s$-norm of $A$, denoted by $\|A\|_{F_{s}}$, is defined as the sum
of the largest $s$ singular values:
$\|A\|_{F_{s}}=\sum_{i=1}^{s}\sigma_{i}(A)$. Note that
$\|A\|_{F_{1}}=\|A\|_{op}$ and $\|A\|_{F_{s}}=\|A\|_{1}$ for $s\geq r$.

### Distance between probability measures.

Suppose $\mu$ and $\nu$ are two probability measures over some Borel algebra
$\mathcal{B}$ on $\mathbb{R}^{n}$ such that $\mu$ is absolutely continuous
with respect to $\nu$. For a convex function $\phi:\mathbb{R}\to\mathbb{R}$
such that $\phi(1)=0$, we define the $\phi$-divergence

$D_{\phi}(\mu||\nu)=\int\phi\left(\frac{d\mu}{d\nu}\right)d\nu.$

In general $D_{\phi}(\mu||\nu)$ is not a distance because it is not symmetric.

The total variation distance between $\mu$ and $\nu$, denoted by
$d_{TV}(\mu,\nu)$, is defined as $D_{\phi}(\mu||\nu)$ for $\phi(x)=|x-1|$. It
can be verified that this is indeed a distance.

The $\chi^{2}$-divergence between $\mu$ and $\nu$, denoted by
$\chi^{2}(\mu||\nu)$, is defined as $D_{\phi}(\mu||\nu)$ for
$\phi(x)=(x-1)^{2}$ or $\phi(x)=x^{2}-1$. It can be verified that these two
choices of $\phi$ give exactly the same value of $D_{\phi}(\mu||\nu)$.

######  Proposition 1 ([27, p90]).

$d_{TV}(\mu,\nu)\leq\sqrt{\chi^{2}(\mu||\nu)}$.

######  Proposition 2 ([10, p97]).

$\chi^{2}(N(0,I_{n})\ast\mu||N(0,I_{n}))\leq\operatorname*{\mathbb{E}}e^{\langle
x,x^{\prime}\rangle}-1$, where $x,x^{\prime}\sim\mu$ are independent.

##  3 Sketching Lower Bound for $p>2$

We follow the notations in [15] throughout this section, though the
presentation here is self-contained. To start, we present the following lemma.

######  Lemma 3 (444A similar result holds for subgaussian vectors $x$ and $y$
with the right-hand side replaced with $\exp(c\|A\|_{F}^{2})$ for some
absolute constant $c>0$, whose proof requires heavier machinery. We only need
the elementary variant here by our choice of hard instance.).

Suppose that $x\sim N(0,I_{m})$ and $y\sim N(0,I_{n})$ are independent and
$A\in\mathbb{R}^{m\times n}$ satisfies $\|A\|_{F}<1$. It holds that

$\operatorname*{\mathbb{E}}_{x,y}e^{x^{T}Ay}\leq\frac{1}{\sqrt{1-\|A\|_{F}^{2}}}.$

###### Proof.

First, it is easy to verify that

$\displaystyle\operatorname*{\mathbb{E}}_{x,y\sim N(0,1)}e^{axy}$
$\displaystyle=\frac{1}{2\pi}\iint_{\mathbb{R}\times\mathbb{R}}e^{axy-\frac{x^{2}+y^{2}}{2}}dxdy$
$\displaystyle=\frac{1}{2\pi}\int_{\mathbb{R}}\int_{\mathbb{R}}e^{-\frac{1}{2}(x-ay)^{2}}e^{-\frac{1}{2}(1-a^{2})y^{2}}dxdy$
$\displaystyle=\frac{1}{\sqrt{2\pi}}\int_{\mathbb{R}}e^{-\frac{1}{2}(1-a^{2})y^{2}}dy$
$\displaystyle=\frac{1}{\sqrt{1-a^{2}}},\quad a\in[0,1).$

Without loss of generality, assume that $m\geq n$. Consider the singular value
decomposition $A=U\Sigma V^{T}$ where $U$ and $V$ are orthogonal matrices of
dimension $m$ and $n$ respectively and
$\Sigma=\operatorname{diag}\\{\sigma_{1},\dots,\sigma_{n}\\}$ with
$\sigma_{1},\dots,\sigma_{n}$ being the non-zero singular values of $A$. We
know that $\sigma_{i}\in[0,1)$ for all $i$ by the assumption that
$\|A\|_{F}<1$. By rotational invariance of the Gaussian distribution, we may
assume that $m=n$ and thus

$\displaystyle\operatorname*{\mathbb{E}}_{x,y\sim N(0,I_{n})}e^{x^{T}Ay}$
$\displaystyle=\operatorname*{\mathbb{E}}_{x,y\sim N(0,I_{n})}e^{x^{T}\Sigma
y}$
$\displaystyle=\frac{1}{(2\pi)^{n}}\iint_{\mathbb{R}^{n}\times\mathbb{R}^{n}}\exp\left\\{\sum_{i=1}^{n}\left(\sigma_{i}x_{i}y_{i}-\frac{x_{i}^{2}+y_{i}^{2}}{2}\right)\right\\}dxdy$
$\displaystyle=\prod_{i=1}^{n}\frac{1}{\sqrt{1-\sigma_{i}^{2}}}$
$\displaystyle\leq\frac{1}{\sqrt{1-\sum_{i=1}^{n}\sigma_{i}^{2}}}$
$\displaystyle=\frac{1}{\sqrt{1-\|A\|_{F}^{2}}}.\qed$

Next we consider the problem of distinguishing two distributions
$\mathcal{D}_{1}=\mathcal{G}(m,n)$ and $\mathcal{D}_{2}$ as defined below. Let
$u_{1},\dots,u_{r}$ be i.i.d. $N(0,I_{m})$ vectors and $v_{1},\dots,v_{r}$
i.i.d. $N(0,I_{n})$ vectors and further suppose that $\\{u_{i}\\}$ and
$\\{v_{i}\\}$ are independent. Let $s\in\mathbb{R}^{r}$ and define the
distribution $\mathcal{D}_{2}$ as
$\mathcal{G}(m,n)+\sum_{i=1}^{r}s_{i}u^{i}(v^{i})^{T}$. We take $k$ linear
measurements and denote the corresponding rows (measurements) of the sketching
matrix by $L^{1},\dots,L^{k}$. Without loss of generality we may assume that
$\operatorname{tr}((L^{i})^{T}L^{i}))=1$ and
$\operatorname{tr}((L^{i})^{T}L^{j}))=0$ for $i\neq j$, since this corresponds
to the rows of the sketching matrix being orthonormal, which we can assume
since we can always change the basis of the row space of the sketching matrix
in a post-processing step. Let $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ be the
corresponding distribution of the linear sketch of dimension $k$ on
$\mathcal{D}_{1}$ and $\mathcal{D}_{2}$, respectively. The main result is the
following theorem.

######  Theorem 4.

There exists an absolute constant $c>0$ such that
$d_{TV}(\mathcal{L}_{1},\mathcal{L}_{2})\leq 1/10$ whenever $k\leq
c/\|s\|_{2}^{4}$.

###### Proof.

It is not difficult to verify that $\mathcal{L}_{1}=N(0,I_{k})$ and
$\mathcal{L}_{2}=N(0,I_{k})+\mu$, where $\mu$ is the distribution of

$\begin{pmatrix}\sum_{i=1}^{r}s_{i}(u^{i})^{T}L^{1}v^{i}\\\
\sum_{i=1}^{r}s_{i}(u^{i})^{T}L^{2}v^{i}\\\ \vdots\\\
\sum_{i=1}^{r}s_{i}(u^{i})^{T}L^{k}v^{i}\\\ \end{pmatrix}.$

Consider a random variable (we shall see in a moment where it comes from)

$\xi=\sum_{i=1}^{k}\sum_{j,l=1}^{r}\sum_{a,c=1}^{m}\sum_{b,d=1}^{n}s_{j}s_{l}(L^{i})_{ab}(L^{i})_{cd}(u^{j})_{a}(v^{j})_{b}(u^{l})_{c}(v^{l})_{d}.$

Take expectation on both sides and notice that the non-vanishing terms on the
right-hand side must have $j=l$, $a=c$ and $b=d$,

$\operatorname*{\mathbb{E}}\xi=\sum_{i=1}^{k}\sum_{j=1}^{r}\sum_{a=1}^{m}\sum_{b=1}^{n}s_{j}^{2}(L^{i})_{ab}^{2}\operatorname*{\mathbb{E}}(u^{j})_{a}^{2}\operatorname*{\mathbb{E}}(v^{j})_{a}^{2}=k\|s\|_{2}^{2}.$

Define an event $\mathcal{E}=\\{\|s\|^{2}\xi<1/2\\}$ and it follows from our
assumption and Markov’s inequality that $\Pr(\mathcal{E})\geq 1-2c$. Restrict
$\mu$ to this event and denote the induced distribution by $\tilde{\mu}$. Let
$\tilde{}\mathcal{L}_{2}=N(0,I_{n})+\tilde{\mu}$.

Then the total variation distance between $\mathcal{L}_{1}$ and
$\mathcal{L}_{2}$ can be upper bounded as

$\displaystyle d_{TV}(\mathcal{L}_{1},\mathcal{L}_{2})$ $\displaystyle\leq
d_{TV}(\mathcal{L}_{1},\tilde{}\mathcal{L}_{2})+d_{TV}(\mathcal{L}_{2},\tilde{}\mathcal{L}_{2})$
$\displaystyle\leq\sqrt{\operatorname*{\mathbb{E}}_{z_{1},z_{2}\sim\tilde{\mu}}e^{\langle
z_{1},z_{2}\rangle}-1}+d_{TV}(\mu,\tilde{\mu})$
$\displaystyle\leq\sqrt{\frac{1}{\Pr(\mathcal{E})}(\operatorname*{\mathbb{E}}_{z_{1}\sim\tilde{\mu},z_{2}\sim\mu}e^{\langle
z_{1},z_{2}\rangle}-1)}+\frac{1}{\Pr(\mathcal{E})}-1$

and we shall bound $\operatorname*{\mathbb{E}}e^{\langle z_{1},z_{2}\rangle}$
in the rest of the proof.

$\displaystyle\operatorname*{\mathbb{E}}_{z_{1}\sim\tilde{\mu},z_{2}\sim\mu}e^{\langle
z_{1},z_{2}\rangle}$
$\displaystyle=\operatorname*{\mathbb{E}}\exp\left\\{\sum_{i=1}^{k}\sum_{j,a,b}\sum_{j^{\prime},a^{\prime},b^{\prime}}s_{j}(L^{i})_{ab}(u^{j})_{a}(v^{j})_{b}\cdot
s_{j^{\prime}}(L^{i})_{a^{\prime}b^{\prime}}(x^{j^{\prime}})_{a^{\prime}}(y^{j^{\prime}})_{b^{\prime}}\right\\}$
$\displaystyle=\operatorname*{\mathbb{E}}_{u^{1},\dots,u^{r},v^{1}\dots,v^{r}|\tilde{\mu}}\prod_{j^{\prime}=1}^{r}\operatorname*{\mathbb{E}}_{\begin{subarray}{c}x_{j^{\prime}}\sim
N(0,I_{m})\\\ y_{j^{\prime}}\sim
N(0,I_{n})\end{subarray}}\exp\left\\{\sum_{a^{\prime},b^{\prime}}Q^{j^{\prime}}_{a^{\prime},b^{\prime}}(x^{j^{\prime}})_{a^{\prime}}(y^{j^{\prime}})_{b^{\prime}}\right\\},$

where

$Q^{j^{\prime}}_{a^{\prime},b^{\prime}}=s_{j^{\prime}}\sum_{i=1}^{k}\sum_{j,a,b}(L^{i})_{ab}(L^{i})_{a^{\prime}b^{\prime}}\cdot
s_{j}(u^{j})_{a}(v^{j})_{b}.$

In order to apply the preceding lemma, we need to verify that
$\|Q^{j^{\prime}}\|_{F}^{2}<1$. Indeed,

$\displaystyle\|Q^{j^{\prime}}\|_{F}^{2}$
$\displaystyle=\sum_{a^{\prime},b^{\prime}}(Q^{j^{\prime}})_{a^{\prime},b^{\prime}}^{2}$
$\displaystyle=s_{j^{\prime}}^{2}\sum_{a^{\prime},b^{\prime}}\sum_{i,i^{\prime}}\sum_{j,a,b}\sum_{\ell,c,d}s_{j}(L^{i})_{ab}(L^{i})_{a^{\prime}b^{\prime}}(u^{j})_{a}(v^{j})_{b}\cdot
s_{\ell}(L^{i^{\prime}})_{cd}(L^{i^{\prime}})_{a^{\prime}b^{\prime}}(u^{\ell})_{c}(v^{\ell})_{d}$
$\displaystyle=s_{j^{\prime}}^{2}\sum_{a^{\prime},b^{\prime}}\sum_{i}(L^{i})^{2}_{a^{\prime}b^{\prime}}\sum_{j,a,b}\sum_{\ell,c,d}s_{j}(L^{i})_{ab}(u^{j})_{a}(v^{j})_{b}\cdot
s_{\ell}(L^{i})_{cd}(u^{\ell})_{c}(v^{\ell})_{d}\quad(i\text{ must equal to
}i^{\prime})$
$\displaystyle=s_{j^{\prime}}^{2}\sum_{i}\sum_{j,a,b}\sum_{\ell,c,d}s_{j}(L^{i})_{ab}(u^{j})_{a}(v^{j})_{b}\cdot
s_{\ell}(L^{i})_{cd}(u^{\ell})_{c}(v^{\ell})_{d}$
$\displaystyle=s_{j^{\prime}}^{2}\xi<1$

since we have conditioned on $\mathcal{E}$. Now it follows from the preceding
lemma that

$\displaystyle\operatorname*{\mathbb{E}}_{u^{1},\dots,u^{r},v^{1}\dots,v^{r}}\prod_{i=1}^{r}\operatorname*{\mathbb{E}}_{x_{j^{\prime}},y_{j^{\prime}}}\exp\left\\{\sum_{a^{\prime},b^{\prime}}Q^{j^{\prime}}_{a^{\prime},b^{\prime}}(x^{j^{\prime}})_{a^{\prime}}(y^{j^{\prime}})_{b^{\prime}}\right\\}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{u^{1},\dots,u^{r},v^{1}\dots,v^{r}}\prod_{j^{\prime}=1}^{r}\frac{1}{\sqrt{1-s_{j^{\prime}}^{2}\xi}}$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{u^{1},\dots,u^{r},v^{1}\dots,v^{r}}\frac{1}{\sqrt{1-\|s\|^{2}\xi}}$
$\displaystyle\leq 1+\|s\|^{2}\operatorname*{\mathbb{E}}\xi$
$\displaystyle\leq 1+k\|s\|^{4},$

where, in the third inequality, we used the fact that $1/\sqrt{1-x}\leq 1+x$
for $x\in[0,1/2]$. Therefore,

$d_{TV}(\mathcal{L}_{1},\mathcal{L}_{2})\leq\sqrt{\frac{k\|s\|^{4}}{1-2c}}+\frac{2c}{1-2c}\leq\sqrt{\frac{c}{1-2c}}+\frac{2c}{1-2c}\leq\frac{1}{10}$

when $c>0$ is small enough. ∎

We will apply the preceding theorem to obtain our lower bounds for the
applications. To do so, notice that by Yao’s minimax principle, we can fix the
rows of our sketching matrix, and show that the resulting distributions
$\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ above have small total variation
distance. By standard properties of the variation distance, this implies that
no estimation procedure $f$ can be used to distinguish the two distributions
with sufficiently large probability, thereby establishing our lower bound.

######  Corollary 5 ($\alpha$-approximation to operator norm).

Let $c>0$ be an arbitrarily small constant. For $\alpha\geq 1+c$, any
sketching algorithm that estimates $\|X\|_{op}$ for $X\in\mathbb{R}^{n\times
n}$ within a factor of $\alpha$ with error probability $\leq 1/6$ requires
sketching dimension $\Omega(n^{2}/\alpha^{4})$.

###### Proof.

Let $m=n$ and take $r=1$ and $s_{1}=C\alpha/\sqrt{n}$ for some constant $C$
large enough in $\mathcal{D}_{2}$ and apply the preceding theorem. ∎

######  Corollary 6 (Schatten norms).

There exists an absolute constant $c>0$ such that any sketching algorithm that
estimates $\|X\|_{p}^{p}$ ($p>2$) for $X\in\mathbb{R}^{n\times n}$ within a
factor of $1+c$ with error probability $\leq 1/6$ requires sketching dimension
$\Omega(n^{2(1-2/p)})$.

###### Proof.

Let $m=n$ and take $r=1$ and $s_{1}=5/n^{1/2-1/p}$ in $\mathcal{D}_{2}$. Note
that $\|X\|_{p}^{p}$ differs by a constant factor with high probability when
$X\sim\mathcal{D}_{1}$ and $X\sim\mathcal{D}_{2}$ (the same hard distribution
as in [15]), apply the preceding theorem. ∎

######  Corollary 7.

Let $\epsilon\in(0,1/3)$. For any matrix
$X\in\mathbb{R}^{(d/\epsilon^{2})\times d}$, any sketching algorithm that
estimates $\|X\|_{op}$ within a factor of $1+\epsilon$ with error probability
$\leq 1/6$ requires sketching dimension $\Omega(d^{2}/\epsilon^{2})$.

###### Proof.

Let $m=d/\epsilon^{2}$ and $n=d$. Take $r=1$ and
$s_{1}=\alpha\sqrt{\epsilon/d}$ for some constant $\alpha>0$ large enough and
apply Theorem 4. Next we shall justify this choice of parameters, that is,

$G\qquad\text{ and }\qquad G+\alpha\sqrt{\frac{\epsilon}{d}}uv^{T}$

differ in operator norm by a factor of $1+\epsilon$ for some constant
$\alpha$. This is de facto proved in the proof of Theorem 7.3 of [16];
nevertheless, we include a full proof below for completeness. First, it
follows from the standard result [28] that

$\|G\|_{op}\leq\frac{\sqrt{d}}{\epsilon}+1.1\sqrt{d}=(1+1.1\epsilon)\frac{\sqrt{d}}{\epsilon}$

with probability at least $1-e^{-\Omega(d)}$. Next we shall show that

$\left\|G+\alpha\sqrt{\frac{\epsilon}{d}}uv^{T}\right\|_{op}\geq(1+2\epsilon)\frac{\sqrt{d}}{\epsilon}$

with high probability. Observe that (denoting the unit sphere in
$\mathbb{R}^{d}$ by $\mathbb{S}^{d-1}$)

$\displaystyle\left\|G+\alpha\sqrt{\frac{\epsilon}{d}}uv^{T}\right\|_{op}=\sup_{x\in\mathbb{S}^{d-1}}\left\|\left(G+\alpha\sqrt{\frac{\epsilon}{d}}uv^{T}\right)x\right\|_{2}$
$\displaystyle\geq\left\|\left(G+\alpha\sqrt{\frac{\epsilon}{d}}uv^{T}\right)\frac{v}{\|v\|_{2}}\right\|_{2}$
$\displaystyle=\left\|G\frac{v}{\|v\|_{2}}+\alpha\sqrt{\frac{\epsilon}{d}}u\|v\|_{2}\right\|_{2}.$

Since $v\sim N(0,I_{d})$, the direction
$v/\|v\|_{2}\sim\operatorname{Unif}(\mathbb{S}^{d-1})$ and the magnitude
$\|v\|_{2}$ are independent, and by rotational invariance of the Gaussian
distribution, $Gx\sim N(0,I_{d})$ for any $x\in\mathbb{S}^{d-1}$. Hence

$\left\|G\frac{v}{\|v\|_{2}}+\alpha\sqrt{\frac{\epsilon}{d}}u\|v\|_{2}\right\|_{2}\overset{\mathrm{dist}}{=\joinrel=}\left\|u_{1}+\alpha\sqrt{\frac{\epsilon}{d}}tu_{2}\right\|_{2}\overset{\mathrm{dist}}{=\joinrel=}\sqrt{1+\frac{\alpha^{2}\varepsilon^{2}t^{2}}{d}}\|u\|_{2},$

where $t$ follows the distribution of $\|v\|_{2}$, $u_{1},u_{2},u\sim
N(0,I_{m})$, $t,u_{1},u_{2}$ are independent, $t$ and $u$ are independent. By
the standard results of standard gaussian vectors, with probability at least
$1-e^{-\Omega(d)}$, it holds that $t\geq\sqrt{d/2}$ and
$\|u\|_{2}\geq(1-\varepsilon)\sqrt{d}/\varepsilon$. Therefore, with
probability at least $1-e^{-\Omega(d)}$, we have

$\left\|G+\alpha\sqrt{\frac{\epsilon}{d}}uv^{T}\right\|_{op}\geq\sqrt{1+\frac{\alpha^{2}\varepsilon}{2}}(1-\varepsilon)\frac{\sqrt{d}}{\varepsilon}\geq(1+2\varepsilon)\frac{\sqrt{d}}{\varepsilon}$

for all $\varepsilon\in(0,1/3)$, provided that $\alpha\geq 3\sqrt{7/2}$. ∎

######  Corollary 8 (Ky-fan norm).

There exists an absolute constant $c>0$ such that any sketching algorithm that
estimates $\|X\|_{F_{s}}$ for $X\in\mathbb{R}^{n\times n}$ and $s\leq
0.0789\sqrt{n}$ within a factor of $1+c$ with error probability $\leq 1/6$
requires sketching dimension $\Omega(n^{2}/s^{2})$.

###### Proof.

Take $r=s$ and $s_{1}=s_{2}=\cdots=s_{r}=5/\sqrt{n}$ in $\mathcal{D}_{2}$ and
apply Theorem 4, for which we shall show the KyFan $s$-norms are different
with high probability in the two cases.

When $X\sim\mathcal{D}_{1}$, we know that $\sigma_{1}(X)\leq 2.1\sqrt{n}$ with
high probability and thus $\|X\|_{F_{s}}\leq 2.1s\sqrt{n}$ with high
probability.

When $X\sim\mathcal{D}_{2}$, we can write $X=G+\frac{5}{\sqrt{n}}P$, where
$P=u_{1}v_{1}^{T}+\cdots+u_{s}v_{s}^{T}$. We claim that with high probability
$\|P\|_{1}\geq 0.9sn$ and thus
$\|X\|_{F_{s}}\geq\frac{5}{\sqrt{n}}\|P\|_{F_{s}}-\|G\|_{F_{s}}\geq
4.5s\sqrt{n}-2.1s\sqrt{n}\geq 2.4s\sqrt{n}$, evincing a multiplicative gap of
$\|X\|_{F_{s}}$ between the two cases.

Now we prove the claim. With high probability, it holds that
$0.99\sqrt{n}\leq\|u_{i}\|\leq 1.01\sqrt{n}$ for all $i$ and $|\sum_{i\neq
j}\langle u_{i},u_{j}\rangle|\leq 1.01s\sqrt{n}$. We shall condition on these
events below.

By the min-max theorem for singular values,

$\sigma_{\ell}^{2}(P)=\max_{H:\dim H=\ell}\min_{\begin{subarray}{c}x\in H\\\
\|x\|_{2}=1\end{subarray}}x^{T}P^{T}Px,$

where

$\displaystyle x^{T}P^{T}Px$
$\displaystyle=\sum_{i,j}x^{T}v_{i}u_{i}^{T}u_{j}v_{j}^{T}x$
$\displaystyle=\sum_{i}x^{T}v_{i}u_{i}^{T}u_{i}v_{i}^{T}x+\sum_{i\neq
j}x^{T}v_{i}(u_{i}^{T}u_{j})v_{j}^{T}x$ $\displaystyle\geq
0.99^{2}n\sum_{i}x^{T}v_{i}^{T}v_{i}x-1.01\sqrt{n}\cdot 1.01k\sqrt{n}\cdot
1.01\sqrt{n}$
$\displaystyle=0.99^{2}n\sum_{i}x^{T}v_{i}^{T}v_{i}x-1.01^{3}kn^{\frac{3}{2}}$

and thus,

$\displaystyle\sigma_{\ell}^{2}(P)$ $\displaystyle\geq 0.99^{2}n\max_{H:\dim
H=\ell}\min_{\begin{subarray}{c}x\in H\\\
\|x\|_{2}=1\end{subarray}}\sum_{i}x^{T}v_{i}^{T}v_{i}x-1.01^{3}kn^{\frac{3}{2}}$
$\displaystyle=0.99^{2}n\sigma_{\ell}^{2}(V)-1.01^{3}kn^{\frac{3}{2}},$

where $V$ is a $k\times n$ matrix with rows $v_{1}^{T},\dots,v_{k}^{T}$.
Therefore

$\|P\|_{1}\geq
0.99\sqrt{n}\|V\|_{1}-1.01^{\frac{3}{2}}s^{\frac{3}{2}}n^{\frac{3}{4}}.$

Since $V$ is a Gaussian random matrix, the classical results imply that
$\|V\|_{1}\geq 0.99s\sqrt{n}$ with high probability [26]. The claim follows
from our assumption on $s$. ∎

##  4 Conclusion

We have presented a simple, surprisingly powerful new analysis which gives
optimal bounds on the sketching dimension for a number of previously studied
sketching problems, including approximating the operator norm, Schatten norms,
and subspace embeddings. We have also presented the first lower bounds for
estimating Ky Fan norms. It would be interesting to see if there are other
applications of this method to the theory of linear sketches.

## References

  * [1] Noga Alon, Yossi Matias, and Mario Szegedy.  The space complexity of approximating the frequency moments.  J. Comput. Syst. Sci., 58(1):137–147, 1999.
  * [2] Alexandr Andoni and Huy L. Nguyen.  Eigenvalues of a matrix in the streaming model.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1729–1737, 2013.
  * [3] Alexandr Andoni, Huy L. Nguyên, Yury Polyanskiy, and Yihong Wu.  Tight lower bound for linear sketches of moments.  In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, pages 25–32, 2013.
  * [4] Marc Bury and Chris Schwiegelshohn.  Sublinear estimation of weighted matchings in dynamic data streams.  In the Proceedings of ESA, 2015.
  * [5] Emmanuel J. Candès and Benjamin Recht.  Exact matrix completion via convex optimization.  Commun. ACM, 55(6):111–119, 2012.
  * [6] Kenneth L. Clarkson and David P. Woodruff.  Numerical linear algebra in the streaming model.  In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 205–214, 2009.
  * [7] Kenneth L. Clarkson and David P. Woodruff.  Low rank approximation and regression in input sparsity time.  In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 81–90, 2013.
  * [8] Amit Deshpande, Madhur Tulsiani, and Nisheeth K. Vishnoi.  Algorithms and hardness for subspace approximation.  In SODA, pages 482–496, 2011.
  * [9] Moritz Hardt, Katrina Ligett, and Frank McSherry.  A simple and practical algorithm for differentially private data release.  In Advances in Neural Information Processing Systems 25, pages 2348–2356. 2012.
  * [10] Yuri Ingster and I. A. Suslina.  Nonparametric Goodness-of-Fit Testing Under Gaussian Models.  Springer, 1st edition, 2002.
  * [11] Robert Krauthgamer and Ori Sasson.  Property testing of data dimensionality.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA., pages 18–27, 2003.
  * [12] Rafał Latała.  Estimates of moments and tails of Gaussian chaoses.  Ann. Probab., 34(6):2315–2331, 2006.
  * [13] Chao Li and Gerome Miklau.  Measuring the achievable error of query sets under differential privacy.  CoRR, abs/1202.3399, 2012.
  * [14] Yi Li, Huy L. Nguyen, and David P. Woodruff.  On sketching matrix norms and the top singular vector.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1562–1581, 2014.
  * [15] Yi Li, Huy L. Nguyen, and David P. Woodruff.  Turnstile streaming algorithms might as well be linear sketches.  In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 174–183, 2014.
  * [16] Yi Li, Ruosong Wang, and David P. Woodruff.  Tight bounds for the subspace sketch problem with applications.  SIAM J. Comput., 50(4):1287–1335, 2021.
  * [17] Yi Li, Zhengyu Wang, and David P. Woodruff.  Improved testing of low rank matrices.  In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’14, New York, NY, USA - August 24 - 27, 2014, pages 691–700, 2014.
  * [18] Yi Li and David P. Woodruff.  A tight lower bound for high frequency moment estimation with small error.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013\. Proceedings, pages 623–638, 2013.
  * [19] Yi Li and David P. Woodruff.  On approximating functions of the singular values in a stream.  In STOC, 2016.
  * [20] Xiangrui Meng and Michael W. Mahoney.  Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression.  In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 91–100, 2013.
  * [21] Cameron Musco and Christopher Musco.  Stronger approximate singular value decomposition via the block lanczos and power methods.  CoRR, abs/1504.05477, 2015.
  * [22] Jelani Nelson and Huy L. Nguyen.  OSNAP: faster numerical linear algebra algorithms via sparser subspace embeddings.  In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 117–126, 2013.
  * [23] Jelani Nelson and Huy L. Nguyên.  Lower bounds for oblivious subspace embeddings.  In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 883–894, 2014.
  * [24] Eric Price and David P. Woodruff.  Applications of the shannon-hartley theorem to data streams and sparse recovery.  In Proceedings of the 2012 IEEE International Symposium on Information Theory, ISIT 2012, Cambridge, MA, USA, July 1-6, 2012, pages 2446–2450, 2012.
  * [25] Oded Regev.  Personal communication, 2014.
  * [26] Terence Tao.  Topics in Random Matrix Theory.  Graduate studies in mathematics. American Mathematical Society, 2012.
  * [27] Alexandre B. Tsybakov.  Introduction to Nonparametric Estimation.  Springer, 1st edition, 2008.
  * [28] Roman Vershynin.  Introduction to the non-asymptotic analysis of random matrices.  In Yonina C. Eldar and Gitta Kutyniok, editors, Compressed Sensing, pages 210–268. Cambridge University Press, 2012.  Cambridge Books Online.
  * [29] Karl Wimmer, Yi Wu, and Peng Zhang.  Optimal query complexity for estimating the trace of a matrix.  CoRR, abs/1405.7112, 2014.
  * [30] David P. Woodruff.  Sketching as a tool for numerical linear algebra.  Foundations and Trends in Theoretical Computer Science, 10(1-2):1–157, 2014.


# Evaluating Open Question Answering Evaluation

Cunxiang Wang$1$, Sirui Cheng$2$11footnotemark: 1, Zhikun Xu$3$, Bowen
Ding$1$, Yidong Wang$1$ and Yue Zhang$1$
$1$School of Engineering, Westlake University, China
$2$Northeastern University, China
$3$Fudan University, China
{wangcunxiang<EMAIL_ADDRESS>Equal contributionThe corresponding
author

###### Abstract

This study focuses on the evaluation of Open Question Answering (Open-QA)
tasks, which have become vital in the realm of artificial intelligence.
Current automatic evaluation methods have shown limitations, indicating that
human evaluation still remains the most reliable approach. We introduce a new
task, QA Evaluation (QA-Eval), designed to assess the accuracy of AI-generated
answers in relation to standard answers within Open-QA. Our evaluation of
these methods utilizes human-annotated results, and we employ accuracy and F1
score to measure their performance. Specifically, the work investigates
methods that show high correlation with human evaluations, deeming them more
reliable. We also discuss the pitfalls of current methods, such as their
inability to accurately judge responses that contain excessive information.
The dataset generated from this work is expected to facilitate the development
of more effective automatic evaluation tools. We believe this new QA-Eval task
and corresponding dataset will prove valuable for future research in this
area. 111The data and code are available at
https://github.com/wangcunxiang/QA-Eval

##  1 Introduction

Open-Domain Question Answering (Open-QA) (Chen et al., 2017), a task that
demands the generation of precise responses to broad, open-ended queries,
serves as an essential measure of a model’s competency in dealing with factual
information. With the advent of Large Language Models (LLMs) such as ChatGPT
(OpenAI, 2022b), significant strides have been made in tackling this task.
However, there still exists a significant challenge for these models -
ensuring the accurate adherence to factual information. Therefore, it becomes
crucial to evaluate the proficiency of LLMs in Open-QA tasks, identify areas
where they might be falling short, and address them to further refine these
models.

Evaluation methods play a vital role in objectively comparing model
performance in Open-QA tasks. Traditional evaluation techniques, such as the
Exact Match (EM) score (Izacard and Grave, 2020; Lewis et al., 2020; Yu et
al., 2022), have certain limitations as they do not adequately account for the
variation in expression of the answers. For instance, ’Lionel Messi’ can also
be expressed as ’Lionel Andrés Messi’, ’Messi’, or ’Leo Messi’, none of which
would produce an exact match. Moreover, the EM score is inapplicable for
detailed responses from LLMs such as ChatGPT (OpenAI, 2022b) and GPT-3.5
(OpenAI, 2022a), where formulating a gold standard answer could excessively
restrict model performance. Furthermore, LLM-based evaluation methods, while
promising, lack empirical evidence of their reliability.

To mitigate these challenges, we first annotate the machine-generated
responses to Open-QA datasets with the help of human evaluators. This is done
with a focus on aligning these responses with gold standard answers and
assessing their factual correctness. Our investigation includes a diverse set
of models like the classic DPR (Karpukhin et al., 2020) \+ FiD (Izacard and
Grave, 2020), as well as newer LLMs like GPT-3.5 and GPT-4. Our study
primarily leverages two Open-QA datasets: Natural Questions (NQ) (Kwiatkowski
et al., 2019) and TriviaQA (TQ) (Joshi et al., 2017).

Building upon this annotated dataset, we propose a novel task – QA-Evaluation
(QA-Eval). QA-Eval aims to assess the reliability of different evaluation
methods in gauging the correctness of machine-generated answers in the context
of Open-QA. The QA-Eval task not only ensures that the generated answers align
with the golden answers but also seeks to match the results with human
evaluations. We consider an evaluation method to be reliable if its results
correlate strongly with human evaluation.

Building upon our annotated Open-QA results, we introduce a novel task, QA-
Evaluation (QA-Eval), designed to test the efficiency of various evaluation
methods in assessing the correlation between machine-generated answers and
gold standard answers in the Open-QA setting. QA-Eval involves an evaluation
method determining the extent to which a machine-generated answer aligns with
the golden answer, with the performance subsequently evaluated against human-
annotated results. Evaluation methods are quantified using accuracy and F1
scores, and the more an evaluation method’s results correlate with the human
annotation, the more reliable it is considered.

In more detail, each instance in the dataset comprises a single question, one
or more gold standard answers, answers generated by multiple models, and human
evaluations of the validity of these generated answers concerning the gold
standard answers. By providing a standard against which various evaluation
methods can be tested and compared, QA-Eval aims to foster the development of
more reliable, effective evaluation techniques in the research community.

We apply several evaluation methods to this benchmark, including Lexical
Match, Neural-Score (Zhang* et al., 2020), and LLMs (Qin et al., 2023), to
determine their ability to assess the correctness of the generated responses.
Our results indicate that although these models are somewhat effective, they
still fall short compared to human evaluators.

We are the pioneers in manually assessing the correctness of answers generated
by both classic and large language models in the context of open question
answering. Additionally, we introduce a benchmark for Open-QA evaluation and
scrutinize the performance of LLMs in this task. Our research presents a
significant leap towards the development of reliable, automated methods for
evaluating Open-QA models, which is a critical component in improving these
models further.

##  2 Related Work

##### Open-Domain Question Answering (Open-QA)

involves soliciting a response to a question that could span a vast range of
topics. There are predominantly two methods currently being employed in this
field.

The first approach involves using pretrained language models to generate
answers, leveraging their internal knowledge learned from a vast amount of
text data (Wang et al., 2021). These models generate answers directly, based
on the information that they have been trained on, without the need for
external databases or retrieval systems.

The second approach comprises of a two-tiered system: a retriever and a
reader. The retriever module fetches pertinent information from a predefined
database that aligns with the given query, while the reader uses this fetched
data to generate an appropriate answer (Izacard and Grave, 2020). Notable
representatives of the retriever module include Dense Passage Retrieval (DPR)
(Karpukhin et al., 2020) and BM25, and for the reader module include Fusion-
in-Decoder (FiD) (Izacard and Grave, 2020) and Retrieval-Augmented Generation
(RAG) (Lewis et al., 2020).

In this study, we delve into both of these approaches, striving to better
understand their strengths and weaknesses when dealing with open-domain
questions. We aim to provide an enhanced perspective on how these different
methodologies perform under varying conditions and question types.

##### Datasets:

Natural Questions (NQ) (Kwiatkowski et al., 2019) and TriviaQA (TQ) (Joshi et
al., 2017) are widely used datasets in the Open-Domain Question Answering
(Open-QA) community, offering unique advantages for training and testing
models’ capabilities.

The Natural Questions (NQ) dataset, developed by Google, is designed to
reflect real-world information-seeking questions and their answers. TriviaQA,
on the other hand, is a dataset developed by the University of Washington that
consists of questions from trivia and quiz-league websites.

We choose to use both NQ and TQ in our work for several reasons. Firstly,
these datasets provide a diverse range of questions and answers, encompassing
both factual and inference-based questions. This diversity helps us to better
understand the strengths and weaknesses of different models and evaluation
methods across various question types. Furthermore, as both NQ and TQ are
well-known and commonly used in the research community, results obtained on
these datasets can be easily compared with existing work, facilitating a more
objective and comprehensive evaluation of our proposed methods.

##### Large Language Models (LLMs)

Large Language Models (LLMs) such as the GPT-series (Radford et al., 2018,
2019; Brown et al., 2020), which includes GPT-3.5 (OpenAI, 2022a), ChatGPT-3.5
(Qin et al., 2023), and Bing Chat (Microsoft, 2023), have been at the
forefront of recent research due to their capability to generate coherent and
contextually accurate textual output. These models have demonstrated
impressive performance across an array of Natural Language Processing (NLP)
tasks, extending from summarization and translation to question answering.

GPT-3.5, an evolution of OpenAI’s GPT-3 (Brown et al., 2020), houses an
immense 175 billion parameters, enhancing its capabilities in understanding
and navigating complex linguistic structures. ChatGPT, a conversational
variant of GPT-3.5, is specifically tailored for dialog-based applications.
Functioning as an interactive AI chatbot, it provides contextually aware and
fluent responses to human inputs. Bing Chat, a development by Microsoft,
integrates the language comprehension of ChatGPT and an extensive retrieval
system to serve as a conversational search engine. It delivers more accurate
and context-sensitive responses to user queries while ensuring proper source
attribution.

In this study, we utilize GPT-3.5, ChatGPT, and Bing Chat in our exploration
of Open-QA and QA-Eval, gaining insights into their relative strengths and
weaknesses in these contexts.

##### Neural Evaluation Models

play a pivotal role in gauging the efficacy of LLMs. One such model deployed
in our investigation is BERT-score (Zhang* et al., 2020), an evaluation tool
that capitalizes on contextual embeddings to measure the similarity between
candidate and reference sentences at the token level. BERT-score’s
contextualized comparison of tokens allows for a more nuanced and accurate
evaluation of language model outputs. It has been applied for evaluating
several machine generation tasks, including machine translation (Zhang* et
al., 2020), dialogue(Sellam et al., 2020) and summarization (Zhao et al.,
2020). In the context of QA-Eval, we use BERT-score as our neural scoring
mechanism, providing us with valuable insights into the accuracy of the
generated responses in relation to their gold standard counterparts.

##  3 Tasks

#####  Open Question Answering (Open-QA):

The Open-QA task mandates that for any given open-domain question $q$, the
model $\mathcal{M}$ must generate a corresponding answer $\hat{a}$. For models
utilizing a retriever-reader mechanism, a database $\mathit{D}$ consisting
documents is also accessible for information retrieval.

The correctness of the produced answer is verified either by human evaluators,
who categorize the answer as ’correct’ or ’incorrect’ by comparing it with a
set of gold standard answers $A$.

##### Open-QA Evaluation (QA-Eval):

In the QA-Eval task, an evaluating model $\mathcal{M}$ is presented with an
open-domain question $q$, an AI-generated answer $\hat{a}$, and a collection
of gold standard answers $A$. The task of the model is to evaluate the
correctness of the AI-produced answer in relation to the gold standard
responses. The prediction $\hat{y}$ should be either ’Yes’ (indicating
correctness) or ’No’ (indicating incorrectness).

The QA-Eval task is considered as a binary classification challenge. The
efficiency of the models is quantified using accuracy and F1 score as the
performance metrics.

##  4 Methods

In this section, we discuss the methods used for the two tasks separately.

###  4.1 For Open-QA

We employ Large Language Models (LLMs), such as GPT-3.5, for an internal-
knowledge approach, and the Dense Passage Retriever + Fusion-in-Decoder model
for a retriever+reader approach for the Open-QA task.

####  4.1.1 Large Language Models

We directly use the question as a prompt to minimize the influence of prompt
engineering, feeding it into the model to generate an answer $\hat{a}$:

$\hat{a}=\mathcal{M}_{llm}(q)$ (1)

Here, $\mathcal{M}_{llm}$ could be GPT-3.5 (text-davinci-003), ChatGPT-3.5
(gpt-3.5-turbo), ChatGPT-4, or Bing Chat.

####  4.1.2 Retriever-Reader Method

For this task, we adopt the Dense Passage Retriever (DPR) model (Karpukhin et
al., 2020) as the retriever model and the Fusion-in-Decoder (FiD) (Izacard and
Grave, 2020) model as the reader model.

The DPR model retrieves relevant documents from all given documents to answer
a specific question. Given a question $q$ and a database $\mathit{D}$ with
each document denoted as $d$, the DPR model comprises two main components: the
question encoder $Q_{enc}$ and the document encoder $D_{enc}$. Both typically
rely on neural networks, such as BERT (Devlin et al., 2019).

The question encoder $Q_{enc}$ maps a question $q$ to a dense vector
representation $q_{emb}=Q_{enc}(q)$, and the document encoder $D_{enc}$ maps
each document $d$ in the database $\mathit{D}$ to a dense vector
representation $d_{emb}=D_{enc}(d)$.

We compute the similarity between the question embedding $q_{emb}$ and each
document embedding $d_{emb}$ using the dot product:

$s(\mathit{d},q)=q_{emb}\cdot d_{emb}$ (2)

Documents in the database $\mathit{D}$ are ranked based on their similarity
scores, and the top $k$ most relevant documents $\mathit{D}_{k}$ are
retrieved. These documents are then used as input for the reader model
$\mathcal{M}_{reader}$ to generate an answer $\hat{a}$ to the question $q$:

$\hat{a}=\mathcal{M}_{reader}(q,\mathit{D}_{k})$ (3)

###  4.2 For QA-Eval

For the QA-Eval task, we employ three representative methods: the lexical
match approach, the Neural-score approach, and the large language model
approach.

####  4.2.1 Lexical Match

We utilize the traditional lexical match method as it is popular in the open-
QA evaluation (Chen et al., 2017; Izacard and Grave, 2020; Lewis et al.,
2020). For answers generated by the DPR+FiD model, we use the Exact Match
method as per Izacard and Grave (2020); Lewis et al. (2020). If the generated
answer $\hat{a}$ exactly matches one golden answer $a\in A$, we classify it as
Yes’, otherwise as No’. Since LLM-generated answers are typically long, the
Exact Match is not applicable, so if at least one golden answer $a\in A$
appears in the AI-generated answer $\hat{a}$, we classify it as ‘Yes’,
otherwise as ‘No’.

####  4.2.2 Large Language Models

Large Language Models (LLMs) have exhibited impressive linguistic
capabilities, indicating significant potential in the assessment of QA
results. Consequently, we have chosen to incorporate them into this task. We
design a prompt filled with a question $q$, an AI-generated answer $\hat{a}$,
and a list of golden answers $A$, and then feed it into the LLM to obtain the
prediction $\hat{y}$:

$\hat{y}=\mathcal{M}_{llm}(prompt)$ (4)

where $prompt$ = "Here is a question, a set of golden answers (split with /),
an AI-generated answer. Can you judge whether the AI-generated answer is
correct according to the question and golden answers, simply answer Yes or
No." + ’Question: ’+$q$+’; ’ + ’Golden Answers: ’ + $A$+’; ’+ ’AI-generated
answer: ’+$\hat{a}$+’; ’+"A:". In this work, we utilize GPT-3.5 (text-
davinci-003) as $\mathcal{M}_{llm}$.

####  4.2.3 Neural-Score

Since BERT-score (Zhang* et al., 2020) is also applicable for evaluating
machine generation tasks, such as machine translation (Zhang* et al., 2020),
dialogue(Sellam et al., 2020) and summarization (Zhao et al., 2020), we also
adopt it as the neural-score approach in the QA-Eval task.

BERT-score is a metric used to evaluate the similarity between two text
sequences, typically between a reference and a hypothesis. We take the
reference as the concatenation of a question ($q$) and the golden answer
($A$), and the hypothesis is the concatenation of the same question ($q$) and
the AI-generated answer ($\hat{a}$). The BERT-score is computed using
contextualized word embeddings from a pre-trained BERT model.

Given a reference $r=A$ and a hypothesis $h=\hat{a}$, we first obtain their
contextualized word embeddings using a pre-trained BERT model:

$\displaystyle E_{r}=\text{BERT}(r),$ (5) $\displaystyle E_{h}=\text{BERT}(h)$

Next, we compute the cosine similarity between each token in the reference and
each token in the hypothesis:

$S_{i,j}=\frac{E_{r_{i}}\cdot E_{h_{j}}}{|E_{r_{i}}||E_{h_{j}}|}$ (6)

We then find the optimal token matchings using the maximum cosine similarity:

$\displaystyle P_{r}=\frac{1}{|r|}\sum_{i=1}^{|r|}\max_{j=1}^{|h|}S_{i,j},$
(7) $\displaystyle P_{h}=\frac{1}{|h|}\sum_{j=1}^{|h|}\max_{i=1}^{|r|}S_{i,j}$

Finally, the BERT-score is calculated as the F1 score between the reference
and hypothesis:

$\text{BERT-score}=\frac{2\cdot P_{r}\cdot P_{h}}{P_{r}+P_{h}}$ (8)

To decide whether the AI-generated answer is positive or not, we set a
threshold $\tau$ and classify the prediction $\hat{y}$ as positive if the
BERT-score is above the threshold and as negative otherwise:

$\hat{y}=\begin{cases}\text{Positive},&\text{BERT-score}>=\tau\\\
\text{Negative},&\text{BERT-score}<\tau\end{cases}$ (9)

We have also considered BART-Score (Yuan et al., 2021) and GPT-Score (Fu et
al., 2023), but they are inapplicable since they provide a continuous score
that measures the similarity between the generated text and the reference
text. It doesn’t explicitly differentiate between correct and incorrect
answers in a binary fashion.

####  4.2.4 Human Evaluation

We manually evaluate answers of different models on the Open-QA task. The
results not only use for calculating the Open-QA performance of each model,
but also serve as the golden $Y$ of the QA-Eval task.

##  5 Data

|  Natural Questions |  TriviaQA
---|---|---
DPR + FiD | 3081/3610 | 485/500
GPT-3.5 | 3081/3610 | 485/500
ChatGPT-3.5 | 3081/3610 | 485/500
GPT-4 | 388/500 | 485/500
Bing Chat | 3081/3610 | 485/500
Table 1: Statistics of data for Open-QA and QA-Eval. In each cell, the right
is the original sample number, while the left the samples after filter.

###  5.1 Data for Open-QA

Following Izacard and Grave (2020); Lewis et al. (2020), we utilize the
Natural Questions (NQ) (Kwiatkowski et al., 2019) and TriviaQA (TQ) (Joshi et
al., 2017) as the Open-QA datasets. Specifically, we use the development set
of NQ and a portion of the test set of TQ. There are 3610 and 500 cases in the
NQ split and TQ split, respectively.

Given that certain questions have answers that change over time, such as ‘Who
is the current US president?’, and some question pairs have answers that are
evidently incorrect, we filter out these instances from the dataset. The
quantity of the remaining dataset is shown in Table 1.

It is noteworthy that some gold standard answers may contain inaccuracies. For
instance, some may include factual errors, as demonstrated in the initial two
examples in Appendix A.1. In such cases, we retain these answers and base our
evaluations upon them. Conversely, when the errors are grammatical or format-
related, like the last two examples, we exclude these from our evaluation
process.

Additionally, there are instances where the LLMs refuse to answer certain
questions. We record these refusals as answers as well.

###  5.2 Data for QA-Eval

After annotation in the Open-QA task, we have the following datasets: NQ-FiD,
NQ-GPT35, NQ-ChatGPT35, NQ-ChatGPT4, NQ-BingChat, TQ-FiD, TQ-GPT35, TQ-
ChatGPT35, TQ-ChatGPT4, and TQ-BingChat. The prefix denotes the original
dataset, while the suffix denotes the generator model. Details of these
datasets can be seen in Table 1.

For the answers produced by Bing Chat, we clear their special symbols and
referential sources to avoid any potential influence on the performance of
evaluating models. Some Bing Chat answers contain an extra question at the
end, such as ‘Do you want to know more about xx?’. These additional questions
might induce the evaluating models to answer the question instead of providing
judgments. Hence, we also remove these end questions.

Dataset | Cohen’s Kappa score
---|---
NQ-Fid | 97.0
NQ-GPT35 | 95.1
NQ-ChatGPT35 | 89.9
NQ-ChatGPT4 | 93.5
NQ-BingChat | 84.9
Table 2: Inter-annotator agreement for different NQ-based datasets used in QA-
Eval.

###  5.3 Human Annotation

The human annotation process for our study was conducted by the authors
themselves, eliminating the need for external paid services. The process
included the careful removal of inappropriate questions and thorough
evaluation of the models’ generated responses’ correctness. To ensure
consistency and precision in the annotation process, we established detailed
guidelines, a portion of which can be found in Appendix B.

Additionally, we employed an additional human annotator to evaluate the inter-
annotator agreement on 500 samples from each NQ-based dataset. The Cohen’s
Kappa scores representing inter-annotator agreement for these evaluations are
presented in Table 2. With all scores above 80, this indicates strong
alignment and agreement among our annotations.

|  Natural Questions |  TriviaQA
---|---|---
DPR + FiD | 68.39 | 74.23
GPT-3.5 | 65.14 | 72.58
ChatGPT-3.5 | 64.34 | 76.49
GPT-4 | 80.93 | 86.80
Bing Chat | 79.07 | 85.15
Table 3: Human evaluated accuracy of several models on Natural Questions (NQ) and TriviaQA (TQ).  |  NQ-FiD |  NQ-GPT35 |  NQ-ChatGPT35 |  NQ-ChatGPT4 |  NQ-BingChat
---|---|---|---|---|---
Lexical Match | 86.8/89.4 | 84.8/86.8 | 80.0/82.3 | 84.0/89.1 | 82.3/87.7
BERT-Score | 74.7/83.2 | 69.5/77.5 | 69.9/77.3 | 77.6/85.6 | 67.2/77.1
GPT-3.5 | 93.6/95.3 | 83.7/86.8 | 86.9/89.6 | 84.5/89.7 | 69.7/77.2
Another Human | 98.7/99.1 | 97.9/98.5 | 95.3/96.3 | 97.9/98.7 | 95.0/96.7
on NQ
|  NQ-FiD |  NQ-GPT35 |  NQ-ChatGPT35 |  NQ-ChatGPT4 |  NQ-BingChat
Lexical Match | 90.0/93.5 | 90.7/93.2 | 92.2/94.6 | 88.7/93.1 | 88.5/92.8
BERT-Score | 64.7/72.4 | 75.5/83.0 | 75.5/83.7 | 81.0/88.8 | 76.1/84.6
GPT-3.5 | 96.1/97.3 | 91.1/93.6 | 93.6/95.7 | 92.3/95.7 | 85.2/90.6
on TQ
Table 4: Performance of Eval-Models on the NQ/TQ set. In each cell, the left
is the accuracy while the right is the F1.

##  6 Experiment

###  6.1 Settings

For the DPR+FiD model, we first use a publicly available DPR
checkpoint222$dl.fbaipublicfiles.com/FiD/data/nq\\_passages.tar.gz$ to
retrieve 100 passages for each question. Subsequently, we train a FiD model
from a T5-large model with the retrieved 100 passages for each question using
the FiD source code333$github.com/facebookresearch/FiD$ and the suggested
hyper-parameters.

For the Large Language Models, we obtain the answers using either the API or
the webpage. For instance, for GPT-3.5 and ChatGPT-3.5, we utilize the OpenAI
text-davinci-003 and gpt-3.5-turbo APIs, respectively, and we set the
temperature to 0 to ensure consistent outputs. For ChatGPT-4 and Bing Chat, we
use their respective webpages. The full Open-QA experiments for GPT-3.5 and
ChatGPT-3.5 were conducted from April 15 to April 17, 2023. For ChatGPT-4 and
Bing Chat, the Open-QA experiments were primarily conducted in April 2023 due
to their daily access limit.

For the BERT-Score approach, we set the threshold $\tau$ at 0.5, considering
it as the most natural choice.

###  6.2 Open-QA performance

The Open-QA result is presented at Table 3.

##### Performance across Different Datasets

:

All models perform better on TriviaQA compared to Natural Questions. This
might suggest that the TriviaQA dataset, which is known for its trivia-style
questions, is more aligned with the kind of diverse and general knowledge
these models have been trained on. In contrast, the Natural Questions dataset,
which is derived from real Google search queries, might contain more complex
or niche questions that are challenging for the models.

##### Model Comparison

:

GPT-3.5 vs ChatGPT-3.5: These two models have very similar performance, both
achieving approximately 65% accuracy on NQ and 72-76% on TQ. This similarity
is expected, as they are versions of the same base model, with the main
difference being that ChatGPT is fine-tuned specifically for conversational
contexts.

GPT-4 vs GPT-3.5 and ChatGPT-3.5: The newer model GPT-4 significantly
outperforms both GPT-3.5 and ChatGPT-3.5 on both datasets. This suggests that
the improvements incorporated into GPT-4, likely including a larger model size
and potentially refined training techniques, have resulted in substantial
gains in question answering performance.

ChatGPT-4 vs Bing Chat: These two models exhibit the highest performance on
both datasets. Their performance is remarkably similar, with GPT-4
outperforming Bing Chat by only a small margin on both datasets. This suggests
that the two models, despite potentially having quite different architectures
and training procedures, have reached similar levels of proficiency in
question answering.

##### Performance Gap

: The best-performing models, ChatGPT-4 and Bing Chat, still fall short of
100% accuracy, scoring around 80% on NQ and 86% on TQ. This indicates that
despite the impressive performance of these models, there are still questions
that remain challenging. Further analysis of these incorrect answers could
reveal specific types of questions or topics that these models struggle with,
providing valuable direction for future model improvements.

##### LLMs vs. Retrieval-based Methods

: The DPR+FiD model, a representative of traditional retrieval-based methods,
performs comparably to the earlier language models (GPT-3.5 and ChatGPT-3.5),
but falls behind the newer ones (ChatGPT-4 and Bing Chat). This indicates that
while retrieval-based methods remain competitive, the newer generation of
language models have surpassed them in terms of question answering capability.
This could be due to the ability of these large models to better understand
and generate natural language, enabling them to generate more accurate and
contextually appropriate answers.

###  6.3 QA-Eval performance

The QA-Eval performance is shown at Table 4.

Table 4 shows the evaluation performance of different models, namely Lexical
Match, BERT-Score, GPT-3.5, and Another Human (used as a reference), on
different subsets of the Natural Questions (NQ) and TriviaQA (TQ) datasets.
These subsets are identified by the generator model used to create them,
including NQ-FiD, NQ-GPT35, NQ-ChatGPT35, NQ-ChatGPT4, NQ-BingChat, and their
TQ equivalents. Besides, we also present the precision and recall performance
in the Appendix Table 6.

A few key observations can be made from the data presented in the table 4:

##### Lexical Match Performance

: The Lexical Match model performs relatively well, coming second to the human
evaluator in most cases. This indicates that straightforward lexical matching
can be a surprisingly effective technique for evaluating the quality of
answers within these specific datasets.

##### BERT-Score Performance

: The BERT-Score model typically yields lower performance than the other
models, particularly on the TQ datasets. This suggests that the BERT-Score
approach, which leverages pre-trained language models to compare embeddings,
may not effectively capture the nuances and complexities of answer quality.

##### GPT-3.5 Performance

: The performance of the GPT-3.5 model is reasonably good across all datasets.
However, there is notable variation in its performance depending on the
dataset, which underscores the impact of the specific dataset on the
evaluation capability of this model.

##### Dataset Differences

: Generally, the performance of the evaluation models is higher on the TQ
datasets compared to the NQ datasets. This could be attributed to the nature
of the answers in the TQ dataset, which might be more straightforward and less
ambiguous, thereby facilitating easier evaluation. Additionally, there are
significant performance differences across various subsets of the datasets,
emphasizing that the choice of generator model can greatly impact the quality
of the generated answers.

##### Human Evaluation

: Ad we say in Section 5.3, we conduct an inter-annotator agreement analysis.
This secondary evaluation yielded an accuracy and F1 score exceeding 95%,
demonstrating superior consistency over all employed AI methods. This result
is in line with expectations, as human evaluators, with their innate
understanding and assessment capabilities, tend to outperform AI models in
accurately gauging the quality of answers. Thus, human evaluators provide an
essential benchmark against which the performance of these AI models can be
measured.

In summary, these findings highlight the challenges and complexities involved
in evaluating answer quality in open-domain question answering systems. They
also underscore the need for further research to enhance the performance of
evaluation models, bringing them closer to human-level evaluation
capabilities.

##  7 Analysis

###  7.1 Error Analysis in Open-QA

|  InAcc |  InCom |  IrrA |  OutInf |  MisQs |  Others
---|---|---|---|---|---|---
DPR + FiD | 25.0 | 3.0 | 0.9 | 1.2 | 1.7 | 0.0
GPT-3.5 | 25.3 | 5.4 | 0.3 | 2.1 | 1.8 | 0.1
ChatGPT-3.5 | 23.2 | 7.9 | 0.5 | 1.4 | 2.4 | 0.2
GPT-4 | 13.3 | 2.8 | 0.3 | 1.2 | 1.3 | 0.0
Bing Chat | 9.5 | 7.6 | 1.3 | 1.3 | 0.8 | 0.5
Table 5: Distribution of error types across different generative models on the
NQ-test dataset. Each cell represents the proportion of the respective error
type to all responses generated by the model.

We classify the errors in the Open-QA scenario into several distinct
categories:

  * •

Inaccurate Information (InAcc): These errors occur when the model’s response,
while relevant to the question, contains inaccuracies.

  * •

Incomplete Answer (InCom): This type of error is characterized by the model
providing pertinent information but failing to fully address the question.

  * •

Irrelevant Answer (IrrA): Here, the model’s response bears no relevance to the
posed question.

  * •

Outdated Information (OutInf): These errors occur when the model provides
information that was correct at some point in the past but is no longer valid
or applicable.

  * •

Misinterpretation of the Question (MisQs): This category includes errors where
the model misinterprets the question’s intent or context.

  * •

Other Errors: This catch-all category includes any errors that don’t fit into
the above classifications.

To perform this error classification, we initially used ChatGPT-4 to conduct a
preliminary categorization of the Open-QA error data. Subsequently, human
annotators were engaged to review and correct the classification results. The
finalized results are represented in Table 5.

Analyzing the data reveals several interesting patterns. Notably, Bing Chat
appears to have the highest rate of ’Incomplete Answer’ errors, suggesting
that while it generally understands the question, it often fails to provide a
comprehensive answer. However, it also has the lowest rate of ’Inaccurate
Information’ errors, implying that the quality of the information it provides
is usually high.

Conversely, DPR + FiD, GPT-3.5, and ChatGPT-3.5 all have similar rates of
’Inaccurate Information’ errors, indicating a potential challenge in
maintaining accuracy for these models. GPT-4 seems to outperform the other
models in both ’Inaccurate Information’ and ’Incomplete Answer’ errors,
suggesting an overall improvement in the quality and completeness of its
responses.

It’s also worth noting the relatively low incidence of ’Outdated Information’
and ’Misinterpretation of the Question’ errors across all models, suggesting
that these areas are less problematic in current models.

This error analysis is helpful in identifying the strengths and weaknesses of
different models and provides valuable insights into the areas that need
further improvements.

###  7.2 Error Analysis in QA-Eval

Figure 1: Correlation between the evaluation accuracy of GPT-3.5 and the
answer length in tokens across all models.

Figure 1 depicts the relationship between GPT-3.5’s evaluation accuracy and
the number of tokens present in the answers produced by all models. The token
count is segmented into six distinct categories: 0-35, 36-70, 71-105, 106-140,
141-175, and 175 and above. The corresponding accuracy for these ranges are
90, 71, 60, 58, 54, and 40 respectively.

Additionally, the average token counts for the answers generated by each model
are as follows: FiD (4.8 tokens), GPT-3.5 (31.4 tokens), ChatGPT (41.9
tokens), GPT-4 (39.9 tokens), and Bing Chat (49.7 tokens).

We can draw several conclusions:

GPT-3.5’s evaluation accuracy exhibits an inverse correlation with the length
of the answer. As the number of tokens in the answer escalates, the evaluation
accuracy diminishes. This could indicate that GPT-3.5 may struggle to
accurately evaluate more extended responses, potentially due to challenges in
retaining context or comprehending intricate or unfamiliar constructs in
longer text spans.

Considering the average token counts, FiD, the model that generates the
shortest responses on average (4.8 tokens), would predominantly fall into the
0-35 token range where GPT-3.5 has its peak accuracy (90). This observation
could imply that GPT-3.5 would exhibit optimal evaluation performance with
responses generated by the FiD model.

Conversely, models like Bing Chat, which on average yield longer responses
(49.7 tokens), would generally fall into the token ranges where GPT-3.5’s
evaluation accuracy is lower. This can partially explain why GPT-3.5 performs
worse than Lexical Match in NQ-BingChat and TQ-BingChat.

##  8 Conclusion

Our study unveils the current limitations in evaluating Open Question
Answering (Open-QA) tasks, exposing the inability of existing methods to
provide reliable evaluations. Particularly, these methods falter when answers
contain an excess of information, leading to misjudgments. However, our
research also highlights that manual human evaluations remain the most
trustworthy approach to assess the correctness of AI-generated answers. To
address these gaps, we introduce the concept of evaluating evaluation models,
encapsulated in our QA-Evaluation (QA-Eval) task. Through this task, we
underscore the importance of assessing the evaluation models themselves to
improve their effectiveness and reliability. We believe our annotated dataset
serves as a valuable resource for this cause, offering potential to aid in the
development of more accurate and dependable automated evaluation tools for
Open-QA tasks in the future.

## References

  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language models are few-shot learners.
  * Chen et al. (2017) Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. 2017.  Reading Wikipedia to answer open-domain questions.  In _Association for Computational Linguistics (ACL)_.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Fu et al. (2023) Jinlan Fu, See-Kiong Ng, Zhengbao Jiang, and Pengfei Liu. 2023.  Gptscore: Evaluate as you desire.  _arXiv preprint arXiv:2302.04166_.
  * Izacard and Grave (2020) Gautier Izacard and Edouard Grave. 2020.  Leveraging passage retrieval with generative models for open domain question answering.
  * Joshi et al. (2017) Mandar Joshi, Eunsol Choi, Daniel S. Weld, and Luke Zettlemoyer. 2017.  Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics_ , Vancouver, Canada. Association for Computational Linguistics.
  * Karpukhin et al. (2020) Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020.  Dense passage retrieval for open-domain question answering.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6769–6781, Online. Association for Computational Linguistics.
  * Kwiatkowski et al. (2019) Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Matthew Kelcey, Jacob Devlin, Kenton Lee, Kristina N. Toutanova, Llion Jones, Ming-Wei Chang, Andrew Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. 2019.  Natural questions: a benchmark for question answering research.  _Transactions of the Association of Computational Linguistics_.
  * Lewis et al. (2020) Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. 2020.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  In _Proceedings of the 34th International Conference on Neural Information Processing Systems_ , NIPS’20, Red Hook, NY, USA. Curran Associates Inc.
  * Microsoft (2023) Microsoft. 2023.  Bing chat.  _https://www.bing.com/new_.
  * OpenAI (2022a) OpenAI. 2022a.  Gpt-3.5 - openai.  _https://platform.openai.com/docs/models/gpt-3-5_.
  * OpenAI (2022b) OpenAI. 2022b.  Introducing chatgpt.  _https://openai.com/blog/chatgpt_.
  * Qin et al. (2023) Chengwei Qin, Aston Zhang, Zhuosheng Zhang, Jiaao Chen, Michihiro Yasunaga, and Diyi Yang. 2023.  Is chatgpt a general-purpose natural language processing task solver?  _arXiv preprint arXiv:2302.06476_.
  * Radford et al. (2018) Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. 2018.  Improving language understanding by generative pre-training.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9.
  * Sellam et al. (2020) Thibault Sellam, Dipanjan Das, and Ankur Parikh. 2020.  BLEURT: Learning robust metrics for text generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7881–7892, Online. Association for Computational Linguistics.
  * Wang et al. (2021) Cunxiang Wang, Pai Liu, and Yue Zhang. 2021.  Can generative pre-trained language models serve as knowledge bases for closed-book QA? In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3241–3251, Online. Association for Computational Linguistics.
  * Yu et al. (2022) Donghan Yu, Chenguang Zhu, Yuwei Fang, Wenhao Yu, Shuohang Wang, Yichong Xu, Xiang Ren, Yiming Yang, and Michael Zeng. 2022.  KG-FiD: Infusing knowledge graph in fusion-in-decoder for open-domain question answering.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 4961–4974, Dublin, Ireland. Association for Computational Linguistics.
  * Yuan et al. (2021) Weizhe Yuan, Graham Neubig, and Pengfei Liu. 2021.  Bartscore: Evaluating generated text as text generation.  In _Advances in Neural Information Processing Systems_ , volume 34, pages 27263–27277. Curran Associates, Inc.
  * Zhang* et al. (2020) Tianyi Zhang*, Varsha Kishore*, Felix Wu*, Kilian Q. Weinberger, and Yoav Artzi. 2020.  Bertscore: Evaluating text generation with bert.  In _International Conference on Learning Representations_.
  * Zhao et al. (2020) Jinming Zhao, Ming Liu, Longxiang Gao, Yuan Jin, Lan Du, He Zhao, He Zhang, and Gholamreza Haffari. 2020.  Summpip: Unsupervised multi-document summarization with sentence graph compression.  In _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pages 1949–1952.

##  Appendix A Data

###  A.1 Golden Error Examples

Here some examples whose golden answer has obvious mistake.

Question: was star wars a book or a movie first? Golden: film

Question: what is the democracy of the united states? Golden: federal republic

Question: the south west wind blows across nigeria between? Golden: till
September

Question: what season does bart bass die in gossip girl? Golden: $($

##  Appendix B Human Annotation Guidelines

  * •

If the question specifies a number (e.g., names of four people), and the
response does not meet this requirement (e.g., provides only one name), the
answer is deemed incorrect.

  * •

Spelling errors in the responses are considered mistakes. For example, if
"golden answer" is misspelled as "gloden answer," the response is marked as
incorrect.

  * •

For questions related to specific times, such as "When was the term social
justice first used?" a response of "1840s" would be considered correct.
However, if the answer needs to be precise to a specific day, month, and year,
each time component needs to be factually accurate for the response to be
marked as correct.

  * •

For location-based queries, like "Where was Oak Island filmed?", a response of
"Canada" would be deemed correct. But, if the answer requires specific details
like state, city, or county, each geographical component must be accurate for
the answer to be considered correct.

These guidelines were strictly followed to maintain the reliability and
validity of the evaluation process.

##  Appendix C Experiments

|  NQ-FiD |  NQ-GPT35 |  NQ-ChatGPT35 |  NQ-ChatGPT4 |  NQ-BingChat
---|---|---|---|---|---
Lexical Match | 99.6/81.1 | 99.6/77.0 | 95.2/72.5 | 99.6/80.6 | 97.6/79.6
BERT-Score | 74.7/76.2 | 74.5/80.8 | 75.1/80.0 | 89.3/82.2 | 85.9/70.0
GPT-3.5 | 96.3/94.3 | 91.7/82.4 | 92.0/87.3 | 97.4/83.1 | 95.5/64.7
Another Human | 99.6/98.5 | 98.9/98.2 | 97.4/95.3 | 99.4/98.1 | 98.0/95.4
on NQ
|  NQ-FiD |  NQ-GPT35 |  NQ-ChatGPT35 |  NQ-ChatGPT4 |  NQ-BingChat
Lexical Match | 100/87.7 | 99.0/88.0 | 100/89.7 | 97.9/88.8 | 98.4/87.9
BERT-Score | 86.2/62.4 | 83.1/82.9 | 85.0/82.4 | 90.8/86.9 | 93.5/77.2
GPT-3.5 | 98.9/95.8 | 98.1/89.5 | 98.3/93.2 | 98.2/93.3 | 97.8/84.5
on TQ
Table 6: Performance of Eval-Models on the NQ/TQ set. In each cell, the left
is the precision while the right is the recall.

##  Appendix D Analysis

###  D.1 Does retrieval Help in LLM?

Figure 2:

In our quest to determine the impact of retrieval on Large Language Models
(LLMs) in an Open-QA setting, we investigate two distinct scenarios. Firstly,
we assess the performance of Bing Chat when retrieval is disabled. Secondly,
we augment GPT-3.5 with a retrieval mechanism and gauge its effectiveness.

####  D.1.1 Performance of Bing Chat Without Retrieval

In this experiment, we modify the standard prompt fed to Bing Chat by
preceding the question $q$ with the instruction "Please do not search, answer
the following question directly:". We choose a sample of 500 questions from
the NQ test dataset, filtering out those unsuitable for this setting. The
results of this experiment are depicted in the left section of Figure 2.

The data suggests a significant decline in Bing Chat’s performance when
retrieval is disabled, dropping approximately 15 percentage points from 80.5
to 65.6. This is comparable to the performance of GPT-3.5 (65.0), which lacks
a retrieval mechanism. This substantial decline implies that the retrieval
component significantly boosts the performance of the LLM underpinning Bing
Chat in an Open-QA context.

####  D.1.2 Augmenting GPT-3.5 with a Retrieval Mechanism

For the second scenario, we employ the same Dense Retriever used in the
DPR+FiD model (referenced in Section4.1.2) to fetch relevant passages from the
database for a given question. We then integrate these passages into the
prompt supplied to GPT-3.5. The prompt reads: "We have a question here:
QUESTION. Now, we have the following relevant passages: PASSAGE 1; PASSAGE 2;
PASSAGE 3; PASSAGE 4; PASSAGE 5. Please answer the question referring to the
above passages."

The results of this experiment, shown in the right section of Figure 2, reveal
a slight decrease in performance with the addition of retrieval, falling from
69.6 to 69.1. This suggests that simply injecting retrieved passages into the
prompts, without any form of thoughtful adaptation, does not contribute
positively to the LLM’s performance in an Open-QA setting.