#  TextHide: Tackling Data Privacy in Language Understanding Tasks

Yangsibo Huang† Zhao Song†‡ Danqi Chen† Kai Li† Sanjeev Arora†‡
†Princeton University ‡Institute for Advanced Study
{yangsibo<EMAIL_ADDRESS>
{danqic, li<EMAIL_ADDRESS>
###### Abstract

An unsolved challenge in distributed or federated learning is to effectively
mitigate privacy risks without slowing down training or reducing accuracy. In
this paper, we propose TextHide aiming at addressing this challenge for
natural language understanding tasks. It requires all participants to add a
simple encryption step to prevent an eavesdropping attacker from recovering
private text data. Such an encryption step is efficient and only affects the
task performance slightly. In addition, TextHide fits well with the popular
framework of fine-tuning pre-trained language models (e.g., BERT) for any
sentence or sentence-pair task. We evaluate TextHide on the GLUE benchmark,
and our experiments show that TextHide can effectively defend attacks on
shared gradients or representations and the averaged accuracy reduction is
only $1.9\%$. We also present an analysis of the security of TextHide using a
conjecture about the computational intractability of a mathematical
problem.111Our code is available at https://github.com/Hazelsuko07/TextHide.

##  1 Introduction

Data privacy for deep learning has become a challenging problem for many
application domains including Natural Language Processing. For example,
healthcare institutions train diagnosis systems on private patients’ data Pham
et al. (2017); Xiao et al. (2018). Google trains a deep learning model for
next-word prediction to improve its virtual keyboard using users’ mobile
device data Hard et al. (2018). Such data are decentralized but moving them to
a centralized location for training a model may violate regulations such as
Health Insurance Portability and Accountability Act (HIPAA) Act (1996) and
California Consumer Privacy Act (CCPA) Legislature (2018).

Federated learning McMahan et al. (year); Kairouz et al. (2019) allows
multiple parties training a global neural network model collaboratively in a
distributed environment without moving data to a centralized storage. It lets
each participant compute a model update (i.e., gradients) on its local data
using the latest copy of the global model, and then send the update to the
coordinating server. The server then aggregates these updates (typically by
averaging) to construct an improved global model.

Privacy has many interpretations depending on the assumed threat models
Kairouz et al. (2019). This paper assumes an eavesdropping attacker with
access to all information communicated by all parties, which includes the
parameters of the model being trained. With such a threat model, a recent work
Zhu et al. (2019) suggests that an attacker can reverse-engineer the private
input.

Multi-party computation Yao (1982) or homomorphic encryption Gentry (2009) can
ensure full privacy but they slow down computations by several orders of
magnitude. Differential privacy (DP) approach Dwork et al. (2006); Dwork
(2009) is another general framework to ensure certain amount of privacy by
adding controlled noise to the training pipeline. However, it trades off data
utility for privacy preservation. A recent work that applies DP to deep
learning was able to reduce accuracy losses Abadi et al. (2016) but they still
remain relatively high.

The key challenge for distributed or federated learning is to ensure privacy
preservation without slowing down training or reducing accuracy. In this
paper, we propose TextHide to address this challenge for natural language
understanding tasks. The goal is to protect training data privacy at a minimal
cost. In other words, we want to ensure that an adversary eavesdropping on the
communicated bits will not be able to reverse-engineer training data from any
participant.

TextHide requires each participant in a distributed or federated learning
setting to add a simple encryption step with one-time secret keys to hide the
hidden representations of its text data. The key idea was inspired by
InstaHide Huang et al. (2020) for computer vision tasks, which encrypts each
training datapoint using a random pixel-wise mask and the MixUp technique
Zhang et al. (2018a) of data augmentation. However, application of InstaHide
to text data is unclear because of the well-known dissimilarities between
image and language: pixel values are real numbers whereas text is sequences of
discrete symbols.

TextHide is designed to plug into the popular framework which transforms
textual input into output vectors through pre-trained language models (e.g.,
BERT Devlin et al. (2019)) and use those output representations to train a new
shallow model (e.g., logistic regression) for any supervised single-sentence
or sentence-pair task. The pre-trained encoder is fine-tuned as well while
training the shallow model. We evaluate TextHide on the GLUE benchmark Wang et
al. (2019). Our results show that TextHide can effectively defend attacks on
shared gradients or representations while the averaged accuracy reduction is
only $1.9\%$.

Lastly, TextHide and InstaHide have completely different security arguments
due to the new designs. To understand the security of the proposed approach,
we also invent a new security argument using a conjecture about the
computational intractability of a mathematical problem.

##  2 InstaHide and Its Challenges for NLP

InstaHide Huang et al. (2020) has achieved good performance in computer vision
for privacy-preserving distributed learning, by providing a
cryptographic222Cryptosystem design since the 1970s seeks to ensure any attack
must solves a computationally expensive task. security while incurring much
smaller utility loss and computation overhead than the best approach based on
differential privacy Abadi et al. (2016).

InstaHide is inspired by the observation that a classic computation problem,
$k$-vector subset sum333$k$-vector subset sum is known to be hard: in the
worst case, finding the secret indices requires $\geq N^{k/2}$ time Abboud and
Lewi (2013) under the conjecture Exponential Time Hypothesis Impagliazzo et
al. (1998). See Appendix A., also appears in the MixUp Zhang et al. (2018a)
method for data augmentation, which is used to improve accuracy on image data.

To encrypt an image $x\in{\mathbb{R}}^{d}$ from a private dataset, InstaHide
first picks $k-1$ other images $s_{2},s_{3},\ldots,s_{k}$ from that private
dataset, or a large public dataset of $N$ images, and random nonnegative
coefficients $\lambda_{i}$ for $i=1,..,k$ that sum to $1$, and creates a
composite image $\lambda_{1}x+\sum_{i=2}^{k}\lambda_{i}s_{i}$ ($k$ is
typically small, e.g., $4$). A composite label is also created using the same
set of coefficients.444Only the labels of the examples from the private
dataset will get combined. See (Huang et al., 2020) or Section 3 for more
details. Then it adds another layer of security: pick a random mask
$\sigma\in\\{-1,1\\}^{d}$ and output the encryption
$\widetilde{x}=\sigma\circ(\lambda_{1}x+\sum_{i=2}^{k}\lambda_{i}s_{i})$,
where $\circ$ is coordinate-wise multiplication of vectors. The neural network
is then trained on encrypted images, which look like random pixel vectors to
the human eye and yet lead to good classification accuracy. Note that the
“one-time secret key” $\sigma,s_{2},\cdots,s_{k}$ used to encrypt $x$ will not
be reused to encrypt other images.

#### Challenges of applying InstaHide to NLP.

There are two challenges to apply InstaHide to text data for language
understanding tasks. The first is the discrete nature of text, while the
encryption in InstaHide operates at continuous inputs. The second is that most
NLP tasks today are solved by fine-tuning pretrained language models such as
BERT on downstream tasks. It remains an open question how to add encryption
into such a framework and what type of security argument it will provide. The
following section presents our approach that overcomes these two challenges.

Figure 1: An illustration of TextHide encryption with $k=2$, where $k$ is the
number of inputs (sentence or sentence-pair) got mixed in each TextHide
representation. TextHide first encodes each text input using a transformer
encoder, then linearly combines their output representations (i.e., [CLS]
tokens), as well as their labels. Finally, an entry-wise mask is chosen from a
randomly pre-generated pool and applied on the mixed representation. The
entry-wise mask, together with the other datapoints to mix constitute the
“one-time secret key” of the TextHide scheme. Note that training directly
takes place on encrypted data and no decryption is needed.

##  3 TextHide: Formal Description

There are two key ideas in TextHide. The first one is using the “one-time
secret key” coming from InstaHide for encryption, and the second is a method
to incorporate such encryption into the popular framework of fine-tuning a
pre-trained language model e.g., BERT Devlin et al. (2019).

In the following, we will describe how to integrate TextHide in the federated
learning setting (Section 3.1), and then present two TextHide schemes (Section
3.2 and 3.3). We analyze the security of TextHide in Section 3.4.

###  3.1 Fine-tuning BERT with TextHide

In a federated learning setting, multiple participants holding private text
data may wish to solve NLP tasks by using a BERT-style fine-tuning pipeline,
where TextHide, a simple InstaHide-inspired encryption step can be applied at
its intermediate level to ensure privacy (see Figure 1).

The BERT fine-tuning framework assumes (input, label) pairs $(x,y)$’s, where
$x$ takes the form of [CLS]$s_{1}$ [SEP]for single-sentence tasks, or
[CLS]$s_{1}$ [SEP]$s_{2}$ [SEP]for sentence-pair tasks. $y$ is a one-hot
vector for classification tasks, or a real-valued number for regression
tasks.555We will mainly use classification tasks as examples throughout the
paper for brevity. For a standard fine-tuning process, federated learning
participants use a BERT-style model $f_{\theta_{1}}$ to compute hidden
representations $f_{\theta_{1}}(x)$’s for their inputs $x$’s and then train a
shallow classifier $h_{\theta_{2}}$ on $f_{\theta_{1}}(x)$, while also fine-
tuning $\theta_{1}$. The parameter vectors $\theta_{1},\theta_{2}$ will be
updated at the central server via pooled gradients. All participants hold
current copies of the two models.

To ensure privacy of their individual inputs $x$’s, federated learning
participants can apply TextHide encryption at the output
$f_{\theta_{1}}(x)$’s. The model $h_{\theta_{2}}$ will be trained on these
encrypted representations. Each participant will compute gradients by
backpropagating through their private encryption, and this is going to be the
source of the secrecy: the attacker can see the communicated gradients but not
the secret encryptions, which limits leakage of information about the input.

We then formally describe two TextHide schemes for fine-tuning BERT in the
federated learning setting: TextHideintra which encrypts an input using other
examples from the same dataset, and TextHideinter which utilizes a large
public dataset to perform encryption. Due to a large public dataset,
TextHideinter is more secure than TextHideintra, but the latter is quite
secure in practice when the training set is large.

###  3.2 Basic TextHide: Intra-Dataset TextHide

In TextHide, we have a pre-trained text encoder $f_{\theta_{1}}$, which takes
$x$, a sentence or a sentence pair, and maps it to a representation
$e=f_{\theta_{1}}(x)\in\operatorname{{\mathbb{R}}}^{d}$ (e.g., $d=768$ for
BERTbase). We use $[b]$ to denote the set $\\{1,2,\cdots,b\\}$. Given a
dataset ${\cal D}$, we denote the set $\\{x_{i},y_{i}\\}_{i\in[b]}$ an “input
batch” by $\mathcal{B}$, where $x_{1},\cdots,x_{b}$ are $b$ inputs randomly
drawn from ${\cal D}$, and $y_{1},\cdots,y_{b}$ are their labels. For each
$x_{i}$ in the batch $\mathcal{B}$, $i\in[b]$, we can encode $x_{i}$ using
$f_{\theta_{1}}$, and obtain a new set of
$\\{e_{i}=f_{\theta_{1}}(x_{i}),y_{i}\\}_{i\in[b]}$. We refer to this set as
an “encoding batch”, and denote it by $\mathcal{E}$. Later in this section, we
use $\widetilde{e}_{i}$ to denote the TextHide encryption of $e_{i}$ for
$i\in[b]$, and name the set
${\widetilde{\mathcal{E}}}=\\{\widetilde{e}_{i},y_{i}\\}_{i\in[b]}$ as a
“hidden batch” of $\mathcal{E}$.

Algorithm 1 $(m,k)$-TextHide

1:procedure TextHide($\mathcal{E},{\cal M},k$)

2: $\triangleright$ $\mathcal{E}$: the training batch, $b$: $|\mathcal{E}|=b$

3: $\triangleright$ ${\cal M}$: the mask pool, $m$: $|{\cal M}|=m$

4: $\triangleright$ $k$: number of training examples to be mixed

5: $\triangleright$ Let $[b]$ denote the set $\\{1,2,\cdots,b\\}$

6: $\widetilde{\mathcal{E}}\leftarrow\emptyset$

7: Generate $\pi_{1}$ such that $\pi_{1}(i)=i$, $\forall i\in[b]$

8: Generate $k-1$ random permutations $\pi_{2}$, $\cdots$,
$\pi_{k}:[b]\rightarrow[b]$

9: Sample $\lambda_{1},\cdots,\lambda_{b}\sim|{\cal
N}(0,I_{k})|\in\operatorname{{\mathbb{R}}}^{k}$ uniformly at random, normalize
s.t. $\sum_{j=1}^{k}(\lambda_{i})_{j}=1$, $\forall i\in[b]$.

10: for $(e_{i},y_{i})\in\mathcal{E}$ do

11: $\sigma_{i}\sim{\cal M}$

12:
$\widetilde{e}_{i}\leftarrow\sigma_{i}\circ\sum_{j=1}^{k}(\lambda_{i})_{j}\cdot
e_{\pi_{j}(i)}$

13: $\widetilde{y}_{i}\leftarrow\sum_{j=1}^{k}(\lambda_{i})_{j}\cdot
y_{\pi_{j}(i)}$

14:
$\widetilde{\mathcal{E}}\leftarrow\widetilde{\mathcal{E}}\cup\\{(\widetilde{x}_{i},\widetilde{y}_{i})\\}$

15: end for

16: return $\widetilde{\mathcal{E}}$

17:end procedure

Algorithm 2 Federated fine-tuning BERT using $(m,k)$-TextHide with $C$ clients
(indexed by $c$)

1:$m$: size of each client’s mask pool

2:$k$: number of training samples to be mixed

3:$d$: hidden size (e.g., 768 in BERT)

4:procedure ServerExecution($f_{\theta_{1}},h_{\theta_{2}}$)

5: $\triangleright$ $f_{\theta_{1}}$: the pre-trained BERT; $h_{\theta_{2}}$:
a shallow classifer

6: $\triangleright$ $T$: number of model updates, $\eta$: learning rate

7: $f_{\theta_{1}^{1}}\leftarrow f_{\theta_{1}}$,
$h_{\theta_{2}^{1}}\leftarrow h_{\theta_{2}}$

8: for $t=1\to T$ do

9: for each client $c$ in parallel do

10: $\nabla_{\theta_{1}^{t},c},\nabla_{\theta_{2}^{t},c}\leftarrow{\text{\sc
CliUpdate}}(c,f_{\theta^{t}_{1}},h_{\theta^{t}_{2}})$

11: end for

12:
$\theta_{1}^{t+1}\leftarrow\theta_{1}^{t}-\frac{\eta}{C}\sum_{c=1}^{C}\nabla_{\theta_{1}^{t},c}$

13:
$\theta_{2}^{t+1}\leftarrow\theta_{2}^{t}-\frac{\eta}{C}\sum_{c=1}^{C}\nabla_{\theta_{2}^{t},c}$

14: end for

15: return $f_{\theta_{1}}^{T+1},h_{\theta_{2}}^{T+1}$

16:end procedure

17:procedure CliUpdate($c,f_{\theta_{1}},h_{\theta_{2}}$) $\triangleright$ Run
on Client $c$

18: $\triangleright$ $b$: batch size; ${\cal D}^{c}$: private train set of
client $c$

19: $\triangleright$ ${\cal M}_{c}$: the mask pool of size $m$ owned by client
$c$, masks are sampled i.i.d. from $\\{-1,+1\\}^{d}$

20: Sample a random batch $\\{x_{i},y_{i}\\}_{i\in[b]}$ from $\mathcal{D}_{c}$

21: $\mathcal{E}=\\{f_{\theta_{1}}(x_{i}),y_{i}\\}_{i\in[b]}$

22: $\widetilde{\mathcal{E}}\leftarrow\textsc{{{\em
TextHide}}}(\mathcal{E},\mathcal{M}_{c},k)$

23: return
$\nabla_{\theta_{1}}\mathcal{L}(f_{\theta_{1}},h_{\theta_{2}};\widetilde{\mathcal{E}})$,
$\nabla_{\theta_{2}}\mathcal{L}(f_{\theta_{1}},h_{\theta_{2}};\widetilde{\mathcal{E}})$

24:end procedure

We use $\sigma\in\\{-1,+1\\}^{d}$ to denote an entry-wise sign-flipping mask.
For a TextHide scheme, ${\cal M}=\\{\sigma_{1},\cdots,\sigma_{m}\\}$ denotes
its randomly pre-generated mask pool of size $m$, and $k$ denotes the number
of sentences combined in a TextHide representation. We name such a
parametrized scheme as $(m,k)$-TextHide.

####  $(m,k)$-TextHide.

Algorithm 1 describes how $(m,k)$-TextHide encrypts an encoding batch
$\mathcal{E}=\\{e_{i},y_{i}\\}_{i\in[b]}$ into a hidden batch
$\widetilde{\mathcal{E}}$, where $b$ is the batch size. For each $e_{i}$ in
$\mathcal{E}$, TextHide linearly combines it with $k-1$ other representations,
as well as their labels. Then, TextHide randomly selects a mask $\sigma_{i}$
from ${\cal M}$, the mask pool, and applies it on the combination using
coordinate-wise multiplication. This gives $\widetilde{e}_{i}$, the encryption
of $e_{i}$ (lines 12, 13 in Algorithm 1). Note that different $e_{i}$’s in the
batch get assigned to a fresh random $\sigma_{i}$’s from the pool.

#### Plug into federated BERT fine-tuning.

Algorithm 2 shows how to incorporate $(m,k)$-TextHide in federated learning,
to allow a centralized server and $C$ distributed clients collaboratively
fine-tune a language model (e.g., BERT) for any downstream tasks, without
sharing raw data. Each client (indexed by $c$) holds its own private data
${\cal D}_{c}$ and a private mask pool ${\cal M}_{c}$, and
$\sum_{c=1}^{C}|{\cal M}_{c}|=m$.

The procedure takes a pre-trained BERT $f_{\theta_{1}}$ and an initialized
task-specific classifier $h_{\theta_{2}}$, and runs $T$ steps of global
updates of both $\theta_{1}$ and $\theta_{2}$. In each global update, the
server aggregates local updates of $C$ clients. For a local update at client
$c$, the client receives the latest copy of $f_{\theta_{1}}$ and
$h_{\theta_{2}}$ from the server, samples a random input batch
$\\{x_{i},y_{i}\\}_{i\in[b]}$ from its private dataset ${\cal D}_{c}$, and
encodes it into an encoding batch
$\mathcal{E}=\\{e_{i}=f_{\theta_{1}}(x_{i}),y_{i}\\}_{i\in[b]}$ (line 21 in
Algorithm 2).

To protect privacy, each client will run $(m,k)$-TextHide with its own mask
pool ${\cal M}_{c}$ to encrypt the encoding batch $\mathcal{E}$ into a hidden
batch $\widetilde{\mathcal{E}}$ (line 22 in Algorithm 2). The client then uses
the hidden batch $\widetilde{\mathcal{E}}$ to calculate the model updates
(i.e., gradients) of both the BERT encoder $f_{\theta_{1}}$ and the shallow
classifier $h_{\theta_{2}}$, and returns them to the server (line 23 in
Algorithm 2). The server averages all updates from $C$ clients, and runs a
global update for $f_{\theta_{1}}$ and $h_{\theta_{2}}$ (lines 12, 13 in
Algorithm 2).

###  3.3 Inter-dataset TextHide

Inter-dataset TextHide encrypts private inputs with text data from a second
dataset, which can be a large public corpus (e.g., Wikipedia). The large
public corpus plays a role reminiscent of the random oracle in cryptographic
schemes Canetti et al. (2004).

Assume we have a private dataset $D_{\text{private}}$ and a large public
dataset $D_{\text{public}}$, TextHideinter randomly chooses $\lceil k/2\rceil$
sentences from $D_{\text{private}}$ and the other $\lfloor k/2\rfloor$ from
$D_{\text{public}}$, mixes their representations, and applies on it a random
mask from the pool. A main difference between TextHideinter and TextHideintra
is, TextHideintra mixes all labels of inputs used in the combination, while in
TextHideinter, only the labels from $D_{\text{private}}$ will be mixed (there
is usually no label from the public dataset). Specifically, for an original
datapoint $\\{x_{i},y_{i}\\}\in{\cal E}$, let $S\subset[b]$ denote the set of
data points’ indices that its TextHide encryption combines, and $|S|=k$. Then
its TextHideinter label is given by

$\displaystyle\frac{\sum_{j=1}^{k}(\lambda_{i})_{j}\cdot
y_{\pi_{j}(i)}\cdot{\bf 1}[\pi_{j}(i)\in{D_{\text{private}}\cap
S}]}{\sum_{j=1}^{k}(\lambda_{i})_{j}\cdot{\bf
1}[\pi_{j}(i)\in{D_{\text{private}}\cap S}]},$

where ${\bf 1}[f]$ is a variable that ${\bf 1}[f]=1$ if $f$ holds, and $=0$
otherwise. For each $j\in[k]$, $\pi_{j}:[b]\rightarrow[b]$ is a permutation.

###  3.4 On Security of TextHide

The encrypted representations produced by TextHide themselves are secure —
i.e., do not allow any efficient way to recover the text $x$ — from the
security framework of InstaHide (see Appendix A for $k$-vector subset sum).
However, an additional source of information leakage is the shared gradients
during federated learning, as shown by Zhu et al. (2019). We mitigate this by
ensuring that the secret mask $\sigma$ used to encrypt the representation of
input $x$ is changed each epoch. The pool of masks is usually much larger than
the number of epochs, which means that each mask gets used only once for an
input (with negligible failure probability). The gradient-matching attack of
Zhu et al. (2019) cannot work in this scenario. In the following section, we
will show that it does not even work with a fixed mask.

##  4 Experiments

We evaluate the utility and privacy of TextHide in our experiments. We aim to
answer the following questions in our experiments:

  * •

What is the accuracy when using TextHide for sentence-level natural language
understanding tasks (Section 4.2)?

  * •

How effective is TextHide in terms of hiding the gradients (Section 4.3) and
the representations of the original input (Section 4.4)?

Dataset | $|\cal D|$ | Task | Metric | Baseline | TextHideintra | TextHideinter
---|---|---|---|---|---|---
RTE | 2.5k | NLI | Acc. | $72.0_{(0.86)}$ | $65.2_{(1.71)}$ | $54.4_{(1.82)}$
MRPC | 3.7k | Paraphrase | F1 / Acc. |  $90.2_{(0.80)}$ / $86.2_{(1.40)}$ |  $89.7_{(0.56)}$ / $85.6_{(0.96)}$ |  $88.1_{(0.52)}$ / $82.6_{(0.75)}$
STS-B | 7k | Similarity | P / S corr. |  $90.1_{(0.12)}$ / $89.7_{(0.17)}$ |  $87.0_{(0.25)}$ / $87.0_{(0.27)}$ |  $86.0_{(0.27)}$ / $86.2_{(0.19)}$
CoLA | 8.5k | Acceptability | MCC | $58.9_{(1.00)}$ | $56.3_{(0.86)}$ | $52.3_{(0.80)}$
SST-2 | 67k | Sentiment | Acc. | $92.4_{(0.76)}$ | $91.7_{(0.51)}$ | $91.3_{(0.41)}$
QNLI | 108k | NLI | Acc. | $91.7_{(0.70)}$ | $91.0_{(0.31)}$ | $89.8_{(0.56)}$
QQP | 364k | Paraphrase | F1 / Acc. |  $87.9_{(0.39)}$ / $91.0_{(0.30)}$ |  $87.3_{(0.41)}$ / $90.5_{(0.33)}$ |  $86.5_{(0.28)}$ / $89.8_{(0.14)}$
MNLI | 393k | NLI | m/mm |  $86.1_{(0.36)}$ / $85.6_{(0.23)}$ |  $84.0_{(0.15)}$ / $84.1_{(0.23)}$ | -
Table 1: Performance on the GLUE tasks for both baseline (standard finetuning)
and TextHide with BERTbase, measured on the development sets. We report the
mean results across 5 runs, with $(m,k)=(16,4)$ for RTE and $(m,k)=(256,4)$
for all the other datasets (see text for more details). Standard deviations
are reported in parentheses. $|\cal D|$ denotes the number of training
examples. TextHide only suffers minor utility loss: $<3\%$ in most cases for
both TextHideintraand TextHideinter. ‘P / S corr.’ is Pearson/Spearman
correlation and ‘MCC’ is Matthew’s correlation.

###  4.1 Experimental Setup

#### Dataset.

We evaluate TextHide on the General Language Understanding Evaluation (GLUE)
benchmark Wang et al. (2019), a collection of 9 sentence-level language
understanding tasks:

  * •

Two sentence-level classification tasks including Corpus of Linguistic
Acceptability (CoLA) Warstadt et al. (2019), and Stanford Sentiment Treebank
(SST-2) Socher et al. (2013).

  * •

Three sentence-pair similarity tasks including Microsoft Research Paraphrase
Corpus (MRPC) Dolan and Brockett (2005), Semantic Textual Similarity Benchmark
(STS-B) Cer et al. (2017), and Quora Question Pairs
(QQP)666https://www.quora.com/q/quoradata/First-Quora-Dataset-Release-
Question-Pairs.

  * •

Four natural language inference (NLI) tasks including Multi NLI (MNLI)
Williams et al. (2018), Question NLI (QNLI) Rajpurkar et al. (2016),
Recognizing Textual Entailment (RTE) Dagan et al. (2005); Bar Haim et al.
(2006); Giampiccolo et al. (2007), and Winograd NLI (WNLI) Levesque et al.
(2011).

Following previous work Devlin et al. (2019); Joshi et al. (2020), we exclude
WNLI in the evaluation. Table 1 summarizes the data size, tasks and evaluation
metrics of all the datasets. All tasks are single-sentence or sentence-pair
classification tasks except that STS-B is a regression task.

#### Implementation.

We fine-tune the pre-trained cased BERTbase model released by Devlin et al.
(2019) on each dataset. We notice that generalizing to different masks
requires a more expressive classifier, thus instead of adding a linear
classifier on top of the [CLS] token, we use a multilayer perceptron of
hidden-layer size (768, 768, 768) to get better performance under TextHide. We
use AdamW Kingma and Ba (2015) as the optimizer, and a linear scheduler with a
warmup ratio of 0.1. More details of hyperparameter selection are given in
Appendix B.3. To show TextHide’s compatibility with the state-of-the-art
model, we also test with the RoBERTabase model released by Liu et al. (2019)
and report the results in Appendix B.2.

(a) RTE ($|\cal D|$: 2.5k) (b) MRPC ($|\cal D|$: 3.7k) (c) STS-B ($|\cal D|$:
7k) (d) CoLA ($|\cal D|$: 8.5k)

(e) SST-2 ($|\cal D|$: 67k) (f) QNLI ($|\cal D|$: 108k) (g) QQP ($|\cal D|$:
364k) (h) MNLI ($|\cal D|$: 393k)

Figure 2: Performance of TextHideintra on the GLUE tasks of different $(m,k)$
pairs, measured on the development sets. $(m,k)=(0,1)$ is equivalent to the
baseline. Metrics are marked on the y-axis. $|\cal D|$ denotes the number of
training examples. TextHide with $m=256$ achieves good utility on all datasets
(except RTE). Larger dataset can work with larger $m$.

###  4.2 Accuracy Results of TextHide

To answer the first question, we compare the accuracy of TextHide to the BERT
baseline without any encryption.

We the vary TextHide scheme as follows:

  * •

Evaluate different $(m,k)$ combinations, where $m$ (the size of mask pool) is
chosen from $\\{0,1,16,64,256,512,1024,4096,\infty\\}$, and $k$ (the number of
inputs to combine) is chosen from $\\{1,2,3,4,8\\}$. $(m,k)=(0,1)$ is
equivalent to the baseline.

  * •

Test both TextHideintra and TextHideinter. We use MNLI train set (around 393k
examples and all the labels are removed) as the “public dataset” in the inter-
dataset setting and run BERT fine-tuning with TextHideinter on the other 7
datasets. Here we use MNLI simply for convenience as it is the largest dataset
in GLUE and one can use any public corpora (e.g., Wikipedia) in principle.

#### Results with different $(m,k)$ pairs.

Figure 2 shows the performance of TextHideintra parameterized with different
$(m,k)$’s. When $m$ is fixed, the network performs consistently with different
$k$’s, suggesting that MixUp Zhang et al. (2018a) also works for language
understanding tasks.

Increasing $m$ makes learning harder since the network needs to generalize to
different masking patterns. However, for most datasets (except for RTE),
TextHide with $m=256$ only reduces accuracy slightly comparable to the
baseline. Our explanation for the poor performance on RTE is that we find
training on this small dataset (even without encryption) to be quite unstable.
This has been observed in Dodge et al. (2020) before. In general, TextHide can
work with larger $m$ (better security) when the training corpus is larger
(e.g., $m=512$ for data size $>100$k).

####  TextHideintra vs. TextHideinter.

TextHideintra mixes the representations from the same private dataset, whereas
TextHideinter combines representations of private inputs with representations
of random inputs from a large public corpus (MNLI in our case).

Table 1 shows the results of the baseline and TextHide (both TextHideintra and
TextHideinter) on the GLUE benchmark, with $(m,k)=(256,4)$ except for RTE with
$(m,k)=(16,4)$. The averaged accuracy reduction of TextHideintra is $1.9\%$,
when compared to the baseline model. With the same $(m,k)$, TextHideinter
incurs an additional $2.5\%$ accuracy loss on average, but as previously
suggested, the large public corpus gives a stronger notion of security.

###  4.3 Security of Gradients in TextHide

We test TextHide against the gradients matching attack in federated learning
Zhu et al. (2019), which has been shown effective in recovering private inputs
from public gradients.

#### Gradients matching attack.

Given a public model and the gradients generated by private data from a
client, the attacker aims to recover the private data: he starts with some
randomly initialized dummy data and dummy labels (i.e., a dummy batch). In
each iteration of attack, he calculates the $\ell_{2}$-distance between
gradients generated by the dummy batch and the real gradients, and
backpropagates that loss to update the dummy batch (see Algorithm 3 in
Appendix C for details).

The original attack is infeasible in the TextHide setting, because the
attacker can’t backpropagate the loss of the dummy batch through the secret
mask of each client. Thus, we enhance the attack by allowing the attacker to
learn the mask: at the beginning of the attack, he also generates some dummy
masks and back-propagates the loss of gradient to update them.

#### Setup and metric.

We use the code777https://github.com/mit-han-lab/dlg of the original paper Zhu
et al. (2019) for evaluation. Due to the unavailability of their code for
attacks in text data, we adapted their setting for computer vision (see
Appendix C for more details). We use the success rate as the metric: an attack
is said to be successful if the mean squared error between the original input
and the samples recovered from gradients is $\leq 0.001$. We vary two key
variables in the evaluation: $k$ and $d$, where $d$ is the dimensionality of
the representation (768 for BERTbase).

#### Test the leakage upper bound.

We run the attack in a much easier setting for the attacker to test the upper
bound of privacy leakage:

  * •

The TextHide scheme uses a single mask throughout training (i.e., $m=1$).

  * •

The batch size is 1.888The original paper Zhu et al. (2019) pointed out that
attacking a larger batch is more difficult.

  * •

The attacker knows the true label for each private input.999As suggested by
Zhao et al. (2020), guessing the correct label is crucial for success in the
attack.

####  TextHide makes gradients matching harder.

As shown in Table 2, increasing $d$, greatly increases the difficulty of
attack — for no mixing ($k=1$), a representation with $d=1024$ reduces the
success rate of $82\%$ (baseline) to only $8\%$. The defense becomes much
stronger when combined with mixing: a small mask of 4 entries combined with
$k=2$ makes the attack infeasible in the tested setting. Figure 3 suggests
that the success of this attack largely depends on whether the mask is
successfully matched, which is aligned with the security argument of TextHide
in Section 3.4.

Baseline |  $k$ $d$ | $4$ | $16$ | $64$ | $256$ | $1024$ |
---|---|---|---|---|---|---|---
| $1$ | 0.76 | 0.56 | 0.30 | 0.22 | 0.08 |
0.82 | $2$ | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
| $4$ | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
Table 2: Success rate of 50 independent gradients matching attacks. Baseline
is the vanilla architecture without TextHide. $d$: the dimensionality of the
representation. Increasing $k$ and $d$ makes attack harder.

(a) Success (b) Failure

Figure 3: Loss over iterations of a succeeded (a) and a failed (b) attacks.
When the mean square error (MSE) between real and dummy masks gets smaller,
both the gradients’ distance and the MSE between leaked image and the original
image gets smaller.

###  4.4 Effectiveness of Hiding Representations

We also design an attack-based evaluation to test whether TextHide
representations effectively “hide” its original representations, i.e., how
‘different’ the TextHide representation is from its original representation.
In Appendix C, we present another attack, which suggests that a deep
architecture can not be trained to reconstruct the original representations
from the TextHide representation.

#### Representation-based Similarity Search (RSS).

Given a corpus of size $n$, and

| Baseline | Mix-only | TextHide | Rand
---|---|---|---|---
Identity | 0.993 | 0.111 | 0.000 | 0.000
JCdist | 0.999 | 0.184 | 0.023 | 0.024
TF-IDFsim | 1.000 | 0.194 | 0.015 | 0.015
Label | 0.998 | 0.759 | 0.494 | 0.542
SBERTsim | 0.991 | 0.280 | 0.102 | 0.101
(a) CoLA

| Baseline | Mix-only | TextHide | Rand
---|---|---|---|---
Identity | 0.992 | 0.064 | 0.000 | 0.000
JCdist | 0.999 | 0.168 | 0.100 | 0.096
TF-IDFsim | 1.000 | 0.080 | 0.007 | 0.008
Label | 1.000 | 0.714 | 0.503 | 0.501
SBERTsim | 1.000 | 0.275 | 0.202 | 0.209
(b) SST-2

Table 3: Averaged similarity score of five metrics over 1,000 independent RSS
attacks on CoLA (a) and SST-2 (b). For each score, the scheme with the worst
similarity (best hiding) is marked in bold. Rand: random baseline. As shown,
attacker against TextHide gives similar performance to random guessing.
Query1 (CoLA):  Some people consider the noisy dogs dangerous. (✓)
---
Baseline:  Some people consider the noisy dogs dangerous. (✓)
Mix-only:  Some people consider the noisy dogs dangerous. (✓)
TextHide: I know a man who hates myself. ($\times$)
Query2 (SST-2):  otherwise excellent ()
Baseline:  otherwise excellent ()
Mix-only:  worthy ()
TextHide: passive-aggressive ()

Table 4: Example queries and answers of RSS with different representation
schemes. We mark words with similar meanings in the same color. We annotate
the acceptability for CoLA (‘✓’: yes, ‘$\times$’: no) and sentiment for SST-2
(‘’: positive, ‘’: negative). Querying with a Mix-only representation still
retrieve the original sentence (Query1), or sentence with similar meanings
(Query2).

  1. 1)

a search index: $\\{x_{i},e_{i}\\}_{i=1}^{n}$, where $x_{i}$ is the $i$-th
example in the training corpus, $e_{i}$ is $x_{i}$’s encoded representation
$f_{\theta_{1}}(x_{i})$;

  2. 2)

a query $\widetilde{e}$: TextHide representation of any input $x$ in the
corpus,

RSS returns $x_{v}$ from the index such that
$v=\arg\min_{i\in[n]}{\cos}(e_{i},\widetilde{e})$. If $x_{v}$ is dramatically
different from $x$, then $\widetilde{e}$ hides $e$ (the original
representation of $x$ ) effectively. To build the search index, we dump all
$(x_{i},e_{i})$ pairs of a corpus by extracting each sentence’s [CLS] token
from the baseline BERT model. We use Facebook’s FAISS library Johnson et al.
(2017) for efficient similarity search to implement RSS.

#### Metrics.

The evaluation requires measuring the similarity of a sentence pair,
($x,x^{*}$), where $x$ is a sample in corpus, and $x^{*}$ is RSS’s answer
given $x$’s encoding $\widetilde{e}$ as query. Our evaluation uses three
explicit leakage metrics:

  * •

Identity: 1 if $x^{*}$ is identical to $x$, else 0.

  * •

JCdist: Jaccard distance $|{\rm words~{}in~{}}x\cap{\rm
words~{}in~{}}x^{*}|/|{\rm words~{}in~{}}x\cup{\rm words~{}in~{}}x^{*}|$

  * •

TF-IDFsim: cosine similarity between $x$’s and $x^{*}$’s TF-IDF representation
in the corpus

and two implicit (semantic) leakage metrics:

  * •

Label: 1 if $x^{*}$, $x$ have the same label, else 0.

  * •

SBERTsim: cosine similarity between $x$’s and $x^{*}$’s SBERT representations
pretrained on NLI-STS101010We use SBERT as an off-the-shelf similarity scorer
since it has been demonstrated great performance in semantic textual
similarity tasks. Reimers and Gurevych (2019).

For all five metrics above, a larger value indicates a higher similarity
between $x$ and $x^{*}$, i.e., worse ‘hiding’.

#### Test Setup.

For an easier demonstration, we run RSS on two single-sentence datasets CoLA
and SST-2 with TextHideintra. The results presumably can generalize to larger
datasets and TextHideinter, since attacking a small corpus with a weaker
security is often easier than attacking a larger one with a stronger security.
For each task, we test three $(m,k)$ variants: baseline ($m=0,k=1$), mix-only
($m=0,k=4$), and TextHide ($m=256,k=4$). We report a random baseline for
reference — for each query, the attacker returns an input randomly selected
from the index.

#### Baseline.

The result with original representation as query can be viewed as an upper
bound of privacy leakage where no defense has been taken. As shown in Table 3
and Table 4, RSS almost returns the correct answer all the time (i.e.,
Identity close to 1), which is a severe explicit leakage.

#### Mix-only.

Mix-only representation greatly reduces both explicit leakage (i.e., gives
much lower similarity on all first 3 metrics) compared to the undefended
baseline. However, RSS still can query back the original sentence with Mix-
only representations (see Query1 in Table 4). Also, semantic leakage, measured
by Label and SBERTsim, is higher than the random baseline.

#### TextHide

TextHide works well in protecting both explicit and semantic information:
sample attacks on TextHide (see Table 4) return sentences seemingly irrelevant
to the original sentence hidden in the query representation. Note that the
sophisticated attacker (RSS) against TextHide gives similar performance to a
naive random guessing attacker.

##  5 Related Work

#### Differential privacy.

Differential privacy Dwork et al. (2006); Dwork and Roth (2014) adds noise
drawn from certain distributions to provide guarantees of privacy. Applying
differential privacy techniques in distributed deep learning is interesting
but non-trivial. Shokri and Shmatikov (2015) proposed a distributed learning
scheme by directly adding noise to the shared gradients. Abadi et al. (2016)
proposed to dynamically keep track of privacy spending based on the
composition theorem Dwork (2009), and McMahan et al. (2018) adapted this
approach to train large recurrent language models. However, the amount of
privacy guaranteed drops with the number of training epochs and the size of
shared parameters Papernot et al. (2020), and it remains unclear how much
privacy can still be guaranteed in practical settings.

#### Cryptographic methods.

Homomorphic encryption Gentry (2009); Graepel et al. (2012); Li et al. (2017)
or secure multi-party computation (MPC) Yao (1982); Beimel (2011); Mohassel
and Zhang (2017); Dolev et al. (2019) allow multiple data cites (clients) to
jointly train a model over their private inputs in distributed learning
setting. Recent work proposed to use cryptographic methods to secure federated
learning by designing a secure gradients aggregation protocol Bonawitz et al.
(2017) or encrypting gradients Aono et al. (2017). However, these approaches
shared the same key drawback: slowing down the computation by several orders
of magnitude, thus currently impractical for deep learning.

####  InstaHide.

See Section 2.

#### Privacy in NLP.

Training with user-generated language data raises privacy concerns: sensitive
information can take the form of key phrases explicitly contained in the text
Harman et al. (2012); Hard et al. (2018); it can also be implicit Coavoux et
al. (2018); Pan et al. (2020), e.g., text data contains latent information
about the author and situation Hovy and Spruit (2016); Elazar and Goldberg
(2018). Recently, Song and Raghunathan (2020) suggests that text embeddings
from language models such as BERT can be inverted to partially recover some of
the input data.

To deal with explicit privacy leakage in NLP, Zhang et al. (2018b) added DP
noise to TF-IDF Salton and McGill (1986) textual vectors, and Hu et al. (2020)
obfuscated the text by substituting each word with a new word of similar
syntactic role. However, both approaches suffer large utility loss when trying
to ensure practical privacy.

Adversarial learning Li et al. (2018); Hu et al. (2020) has been used to
address implicit leakage to learn representations that are invariant to
private-sensitive attributes. Similarly, Mosallanezhad et al. (2019) used
reinforcement learning to automatically learn a strategy to reduce private-
attribute leakage by playing against an attribute-inference attacker. However,
these approaches does not defend explicit leakage.

##  6 Conclusion

We have presented TextHide, a practical approach for privacy-preserving NLP
training with a pretrain and fine-tuning framework in a federated learning
setting. It requires all participants to add a simple encryption step with an
one-time secret key. It imposes a slight burden in terms of computation cost
and accuracy. Attackers who wish to break such encryption and recover user
inputs have to pay a large computational cost.

We see this as a first step in using cryptographic ideas to address privacy
issues in language tasks. We hope our work motivates further research,
including applications to other NLP tasks. An important step could be to
successfully train language models directly on encrypted texts, as is done for
image classifiers.

## Acknowledgements

This project is supported in part by the Graduate Fellowship at Princeton
University, Ma Huateng Foundation, Schmidt Foundation, Simons Foundation, NSF,
DARPA/SRC, Google and Amazon AWS. Arora and Song were at the Institute for
Advanced Study during this research.

## References

  * Abadi et al. (2016) Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. 2016.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS)_ , pages 308–318.
  * Abboud and Lewi (2013) Amir Abboud and Kevin Lewi. 2013.  Exact weight subgraphs and the $k$-sum conjecture.  In _International Colloquium on Automata, Languages, and Programming (ICALP)_ , pages 1–12.
  * Abboud et al. (2014) Amir Abboud, Kevin Lewi, and Ryan Williams. 2014.  Losing weight by gaining edges.  In _European Symposium on Algorithms (ESA)_ , pages 1–12.
  * Act (1996) Accountability Act. 1996.  Health insurance portability and accountability act of 1996.  _Public law_ , 104:191.
  * Aono et al. (2017) Yoshinori Aono, Takuya Hayashi, Lihua Wang, and Shiho Moriai. 2017.  Privacy-preserving deep learning via additively homomorphic encryption.  _IEEE Transactions on Information Forensics and Security_ , 13(5):1333–1345.
  * Bar Haim et al. (2006) Roy Bar Haim, Ido Dagan, Bill Dolan, Lisa Ferro, Danilo Giampiccolo, Bernardo Magnini, and Idan Szpektor. 2006.  The second PASCAL recognising textual entailment challenge.  In _Manuscript_.
  * Beimel (2011) Amos Beimel. 2011.  Secret-sharing schemes: a survey.  In _International conference on coding and cryptology (IWCC)_ , pages 11–46.
  * Bhattacharyya et al. (2011) Arnab Bhattacharyya, Piotr Indyk, David P Woodruff, and Ning Xie. 2011.  The complexity of linear dependence problems in vector spaces.  In _Innovations in Computer Science (ICS)_ , pages 496–508.
  * Bonawitz et al. (2017) Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. 2017.  Practical secure aggregation for privacy-preserving machine learning.  In _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS)_ , pages 1175–1191.
  * Canetti et al. (2004) Ran Canetti, Oded Goldreich, and Shai Halevi. 2004.  The random oracle methodology, revisited.  _Journal of the ACM (JACM)_ , 51(4):557–594.
  * Cer et al. (2017) Daniel Cer, Mona Diab, Eneko Agirre, Inigo Lopez-Gazpio, and Lucia Specia. 2017\.  Semeval-2017 task 1: Semantic textual similarity-multilingual and cross-lingual focused evaluation.  In _Proceedings of the 11th International Workshop on Semantic Evaluation (SemEval@ACL)_ , pages 1–14.
  * Coavoux et al. (2018) Maximin Coavoux, Shashi Narayan, and Shay B Cohen. 2018.  Privacy-preserving neural representations of text.  In _Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1–10.
  * Dagan et al. (2005) Ido Dagan, Oren Glickman, and Bernardo Magnini. 2005.  The PASCAL recognising textual entailment challenge.  In _Machine learning challenges. evaluating predictive uncertainty, visual object classification, and recognising tectual entailment (MLCW)_ , pages 177–190.
  * 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 _North American Chapter of the Association for Computational Linguistics (NAACL)_.
  * Dodge et al. (2020) Jesse Dodge, Gabriel Ilharco, Roy Schwartz, Ali Farhadi, Hannaneh Hajishirzi, and Noah Smith. 2020.  Fine-tuning pretrained language models: Weight initializations, data orders, and early stopping.  _arXiv preprint arXiv:2002.06305_.
  * Dolan and Brockett (2005) William B Dolan and Chris Brockett. 2005.  Automatically constructing a corpus of sentential paraphrases.  In _Proceedings of the International Workshop on Paraphrasing_.
  * Dolev et al. (2019) Shlomi Dolev, Peeyush Gupta, Yin Li, Sharad Mehrotra, and Shantanu Sharma. 2019\.  Privacy-preserving secret shared computations using mapreduce.  _IEEE Transactions on Dependable and Secure Computing_.
  * Dwork (2009) Cynthia Dwork. 2009.  The differential privacy frontier.  In _Theory of Cryptography Conference (TCC)_ , pages 496–502.
  * Dwork et al. (2006) Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. 2006.  Our data, ourselves: Privacy via distributed noise generation.  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , pages 486–503.
  * Dwork and Roth (2014) Cynthia Dwork and Aaron Roth. 2014.  The algorithmic foundations of differential privacy.  _Foundations and Trends in Theoretical Computer Science_ , 9(3–4):211–407.
  * Elazar and Goldberg (2018) Yanai Elazar and Yoav Goldberg. 2018.  Adversarial removal of demographic attributes from text data.  In _Empirical Methods in Natural Language Processing (EMNLP)_ , pages 11–21.
  * Gentry (2009) Craig Gentry. 2009.  Fully homomorphic encryption using ideal lattices.  In _Proceedings of the forty-first annual ACM symposium on Theory of computing (STOC)_ , pages 169–178.
  * Giampiccolo et al. (2007) Danilo Giampiccolo, Bernardo Magnini, Ido Dagan, and Bill Dolan. 2007.  The third PASCAL recognizing textual entailment challenge.  In _Proceedings of the ACL-PASCAL workshop on textual entailment and paraphrasing (IWP)_ , pages 1–9.
  * Graepel et al. (2012) Thore Graepel, Kristin Lauter, and Michael Naehrig. 2012.  Ml confidential: Machine learning on encrypted data.  In _International Conference on Information Security and Cryptology (ICISC)_ , pages 1–21.
  * Hard et al. (2018) Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. 2018.  Federated learning for mobile keyboard prediction.  _arXiv preprint arXiv:1811.03604_.
  * Harman et al. (2012) Laurinda B Harman, Cathy A Flite, and Kesa Bond. 2012.  Electronic health records: privacy, confidentiality, and security.  _AMA Journal of Ethics_ , 14(9):712–719.
  * Hovy and Spruit (2016) Dirk Hovy and Shannon L Spruit. 2016.  The social impact of natural language processing.  In _Association for Computational Linguistics (ACL)_ , pages 591–598.
  * Hu et al. (2020) Zhifeng Hu, Serhii Havrylov, Ivan Titov, and Shay B Cohen. 2020.  Obfuscation for privacy-preserving syntactic parsing.  In _The 16th International Conference on Parsing Technologies (IWPT)_ , pages 62–72.
  * Huang et al. (2020) Yangsibo Huang, Zhao Song, Kai Li, and Sanjeev Arora. 2020.  Instahide: Instance-hiding schemes for private distributed learning.  In _Internation Conference on Machine Learning (ICML)_.
  * Impagliazzo et al. (1998) Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 1998.  Which problems have strongly exponential complexity?  In _Proceedings. 39th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 653–662.
  * Johnson et al. (2017) Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2017.  Billion-scale similarity search with gpus.  _arXiv preprint arXiv:1702.08734_.
  * Joshi et al. (2020) Mandar Joshi, Danqi Chen, Yinhan Liu, Daniel S Weld, Luke Zettlemoyer, and Omer Levy. 2020.  SpanBERT: Improving pre-training by representing and predicting spans.  In _Transactions of the Association of Computational Linguistics (TACL)_ , pages 64–77.
  * Kairouz et al. (2019) Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. 2019.  Advances and open problems in federated learning.  _arXiv preprint arXiv:1912.04977_.
  * Kingma and Ba (2015) Diederik P Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  In _International Conference on Learning Representations (ICLR)_.
  * Krizhevsky (2009) Alex Krizhevsky. 2009.  Learning multiple layers of features from tiny images.  Technical report, Citeseer.
  * LeCun et al. (1998) Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. 1998.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324.
  * Legislature (2018) California State Legislature. 2018.  California consumer privacy act (ccpa).  https://oag.ca.gov/privacy/ccpa.
  * Levesque et al. (2011) Hector J Levesque, Ernest Davis, and Leora Morgenstern. 2011.  The Winograd schema challenge.  In _AAAI Spring Symposium: Logical Formalizations of Commonsense Reasoning_ , volume 46, page 47.
  * Li et al. (2017) Ping Li, Jin Li, Zhengan Huang, Tong Li, Chong-Zhi Gao, Siu-Ming Yiu, and Kai Chen. 2017.  Multi-key privacy-preserving deep learning in cloud computing.  _Future Generation Computer Systems_ , 74:76–85.
  * Li et al. (2018) Yitong Li, Timothy Baldwin, and Trevor Cohn. 2018.  Towards robust and privacy-preserving text representations.  In _Association for Computational Linguistics (ACL)_ , pages 25–30.
  * Liu and Nocedal (1989) Dong C Liu and Jorge Nocedal. 1989.  On the limited memory bfgs method for large scale optimization.  _Mathematical programming_ , 45(1-3):503–528.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  RoBERTa: A robustly optimized BERT pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * McMahan et al. (year) H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. year.  Communication-efficient learning of deep networks from decentralized data.  In _Artificial Intelligence and Statistics (AISTATS)_ , pages 1273–1282.
  * McMahan et al. (2018) H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. 2018.  Learning differentially private recurrent language models.  In _International Conference on Learning Representations (ICLR)_.
  * Mohassel and Zhang (2017) Payman Mohassel and Yupeng Zhang. 2017.  Secureml: A system for scalable privacy-preserving machine learning.  In _2017 IEEE Symposium on Security and Privacy (S &P)_, pages 19–38.
  * Mosallanezhad et al. (2019) Ahmadreza Mosallanezhad, Ghazaleh Beigi, and Huan Liu. 2019.  Deep reinforcement learning-based text anonymization against private-attribute inference.  In _Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2360–2369.
  * Pan et al. (2020) Xudong Pan, Mi Zhang, Shouling Ji, and Min Yang. 2020.  Privacy risks of general-purpose language models.  In _2020 IEEE Symposium on Security and Privacy (S &P)_, pages 1314–1331.
  * Papernot et al. (2020) Nicolas Papernot, Steve Chien, Shuang Song, Abhradeep Thakurta, and Ulfar Erlingsson. 2020.  Making the shoe fit: Architectures, initializations, and tuning for learning with privacy.  In _Manuscript_.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  Pytorch: An imperative style, high-performance deep learning library.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 8024–8035.
  * Pham et al. (2017) Trang Pham, Truyen Tran, Dinh Phung, and Svetha Venkatesh. 2017.  Predicting healthcare trajectories from medical records: A deep learning approach.  _Journal of Biomedical Informatics_ , 69:218 – 229.
  * Rajpurkar et al. (2016) Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016.  SQuAD: 100,000+ questions for machine comprehension of text.  In _Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2383–2392.
  * Reimers and Gurevych (2019) Nils Reimers and Iryna Gurevych. 2019.  Sentence-BERT: Sentence embeddings using siamese bert-networks.  In _Empirical Methods in Natural Language Processing (EMNLP)_.
  * Salton and McGill (1986) Gerard Salton and Michael J McGill. 1986.  Introduction to modern information retrieval.  _McGraw-Hil, New York_.
  * Shokri and Shmatikov (2015) Reza Shokri and Vitaly Shmatikov. 2015.  Privacy-preserving deep learning.  In _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security (CCS)_ , pages 1310–1321.
  * Socher et al. (2013) Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Ng, and Christopher Potts. 2013.  Recursive deep models for semantic compositionality over a sentiment treebank.  In _Empirical Methods in Natural Language Processing (EMNLP)_ , pages 1631–1642.
  * Song and Raghunathan (2020) Congzheng Song and Ananth Raghunathan. 2020.  Information leakage in embedding models.  In _ACM Conference on Computer and Communications Security (CCS)_.
  * Wang et al. (2019) Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. 2019.  GLUE: A multi-task benchmark and analysis platform for natural language understanding.  In _International Conference on Learning Representations (ICLR)_.
  * Warstadt et al. (2019) Alex Warstadt, Amanpreet Singh, and Samuel R. Bowman. 2019.  Neural network acceptability judgments.  In _Transactions of the Association of Computational Linguistics (TACL)_ , pages 625–641.
  * Williams et al. (2018) Adina Williams, Nikita Nangia, and Samuel R. Bowman. 2018.  A broad-coverage challenge corpus for sentence understanding through inference.  In _North American Chapter of the Association for Computational Linguistics (NAACL)_ , pages 1112–1122.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. 2019.  HuggingFace’s transformers: State-of-the-art natural language processing.  In _arXiv preprint_.
  * Xiao et al. (2018) Cao Xiao, Edward Choi, and Jimeng Sun. 2018.  Opportunities and challenges in developing deep learning models using electronic health records data: a systematic review.  _Journal of the American Medical Informatics Association_ , 25(10):1419–1428.
  * Yao (1982) A. C. Yao. 1982.  Protocols for secure computations.  In _23rd Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 160–164.
  * Zhang et al. (2018a) Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. 2018a.  mixup: Beyond empirical risk minimization.  In _International Conference on Learning Representations (ICLR)_.
  * Zhang et al. (2018b) Jinxue Zhang, Jingchao Sun, Rui Zhang, Yanchao Zhang, and Xia Hu. 2018b.  Privacy-preserving social media data outsourcing.  In _IEEE International Conference on Computer Communications (INFOCOM)_ , pages 1106–1114.
  * Zhao et al. (2020) Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. 2020.  iDLG: Improved deep leakage from gradients.  _arXiv preprint arXiv:2001.02610_.
  * Zhu et al. (2019) Ligeng Zhu, Zhijian Liu, and Song Han. 2019.  Deep leakage from gradients.  In _Advances in Neural Information Processing Systems (NeurIPS)_.

##  Appendix A $k$-vector subset sum

Cryptosystem design since the 1970s seeks to ensure that attackers can violate
privacy only by solving a computationally expensive task. A simple example is
the vector subset sum problem Bhattacharyya et al. (2011); Abboud et al.
(2014). Here a set of $N$ vectors
$v_{1},v_{2},\ldots,v_{k}\in{\mathbb{R}}^{d}$ are publicly released. The
defender picks secret indices
$i_{1},i_{2},\ldots,i_{k}\in[N]\overset{\mathrm{def}}{=}\\{1,\cdots,N\\}$ and
publicly releases the vector $\sum_{j}v_{i_{j}}$. Given this released vector
the attacker has to find secret indices $i_{1},i_{2},\ldots,i_{k}$. In worst
cases even when the answer happens to be unique, finding the secret indices
requires $\geq N^{k/2}$ time Abboud and Lewi (2013) under the famous
conjecture, Exponential Time Hypothesis ($\mathsf{ETH}$) Impagliazzo et al.
(1998). Note that $\mathsf{ETH}$ is a stronger notion than
$\mathsf{NP}\neq\mathsf{P}$, and $\mathsf{ETH}$ is widely accepted
computational complexity community.

##  Appendix B Experiment details

###  B.1 Implementation

The implementation uses the PyTorch framework Paszke et al. (2019) based on
HuggingFace’s codebase Wolf et al. (2019). We ran all experiments on 24 NVIDIA
RTX 2080 Ti GPUs.

###  B.2 More Evaluations

Datasets | $|\cal D|$ | Task | Metric | Baseline | TextHideintra | TextHideinter
---|---|---|---|---|---|---
RTE | 2.5k | NLI | Acc. | $78.8_{(0.69)}$ | $77.9_{(0.99)}$ | $70.8_{(0.78)}$
MRPC | 3.7k | Paraphrase | F1 / Acc. |  $92.3_{(0.56)}$ / $89.3_{(0.66)}$ |  $91.1_{(0.68)}$ / $87.6_{(0.34)}$ |  $90.5_{(0.68)}$ / $87.1_{(0.89)}$
STS-B | 7k | Similarity | P / S corr. |  $91.3_{(0.13)}$ / $91.0_{(0.19)}$ |  $90.4_{(0.19)}$ / $90.3_{(0.16)}$ |  $82.6_{(0.65)}$ / $84.2_{(0.52)}$
CoLA | 8.5k | Acceptability | MCC | $63.0_{(1.24)}$ | $59.1_{(1.01)}$ | $57.2_{(0.90)}$
SST-2 | 67k | Sentiment | Acc. | $94.1_{(0.52)}$ | $93.5_{(0.21)}$ | $92.8_{(0.47)}$
QNLI | 108k | NLI | Acc. | $92.7_{(0.21)}$ | $92.3_{(0.29)}$ | $91.7_{(0.48)}$
QQP | 364k | Paraphrase | F1 / Acc. |  $88.8_{(0.21)}$ / $91.6_{(0.15)}$ |  $88.1_{(0.24)}$ / $91.0_{(0.31)}$ |  $87.7_{(0.36)}$ / $90.7_{(0.22)}$
MNLI | 393k | NLI | m/mm |  $87.2_{(0.39)}$ / $86.8_{(0.21)}$ |  $86.4_{(0.21)}$ / $86.0_{(0.15)}$ | -
Table 5: Performance on the GLUE tasks for both baseline (standard finetuning)
and TextHide with RoBERTabase model Liu et al. (2019), measured on the
development sets. We report the mean results across 5 runs, with
$(m,k)=(16,4)$ for RTE and $(m,k)=(256,4)$ for all the other datasets.
Standard deviations are reported in parentheses. $|\cal D|$ denotes the number
of training samples. TextHide only suffers minor utility loss ($\sim 3\%$). ‘P
/ S corr.’ is Pearson/Spearman correlation. ‘MCC’ is Matthew’s correlation.
Private dataset: SST-2 ($|\cal D|$: 67k)
---
Public Corpora | $|\cal D|$ | Task | Acc.
QNLI | 108k | NLI | $91.2_{(0.68)}$
QQP | 364k | Paraphrase | $91.0_{(0.45)}$
MNLI | 393k | NLI | $91.3_{(0.41)}$
Table 6: Dev set performance of SST-2 for TextHideinter with different public
corpora, $(m,k)=(256,4)$. $|\cal D|$ denotes the number of samples. Standard
deviations are annotated as subscripts. The choice of the public corpus does
not have a major impact on the final accuracy of SST-2.

#### Compatibility with the state-of-the-art model.

To test if TextHide is also compatible with state-of-the-art models, we repeat
our accuracy evaluation in Section 4.2 but replace the BERTbase model with the
RoBERTabase model Liu et al. (2019).

As shown in Table 5, TextHide behaves consistently for BERTbase and
RoBERTabase: when incorporated with RoBERTabase, the averaged accuracy
reduction of TextHideintra is $1.1\%$ when compared with the baseline model
(was $1.9\%$ for BERTbase). TextHideinter incurs an additional $2.6\%$
accuracy loss on average (was $2.5\%$ for BERTbase).

####  TextHideinter with different public corpora: A case study of SST-2.

We investigate whether using different public corpora affects the performance
of TextHideinter. We fix SST-2 as the private dataset, set $(m,k)=(256,4)$,
and choose the public corpora from unlabeled {QNLI, QQP, MNLI}. We
intentionally make the public corpora larger than the private dataset (SST-2
in this test), since TextHideinter was designed to use a large public corpus
as the source of randomness to provide useful security.

Table 6 suggests that for our case study of SST-2, the choice of the public
corpus does not have a major impact on the final accuracy of TextHideinter.
However, this may not be true for every dataset.

###  B.3 Fine-tuning Hyperparameters

For results in Table 1 and 5 (including our baseline), we chose the best
parameters with learning rate = $\\{5e-6,1e-5,2e-5,3e-5,5e-5\\}$, epochs =
$\\{5,10,15,20,25,30\\}$, batch size = $\\{16,32\\}$, dropout rate =
$\\{0.1,0.2,0.3,0.4,0.5\\}$ based on the validation performance ($10\%$ from
the training set). We used more epochs for fine-tuning since training with
random masking takes longer to converge.

##  Appendix C Details of attacks

Algorithm 3 Gradients matching attack Zhu et al. (2019) in TextHide

1:Require :

2:The function $F(x;W)$ can be thought of as a neural network

3:For each $l\in[L]$, we define
$W_{l}\in\operatorname{{\mathbb{R}}}^{m_{l}\times m_{l-1}}$ to be the weight
matrix in $l$-th layer, and $m_{0}=d_{i}$ and $m_{l}=d_{o}$

4:Let $W=\\{W_{1},W_{2},\cdots,W_{L}\\}$ denote the weights over all layers

5:Let $\mathcal{L}:\operatorname{{\mathbb{R}}}^{d_{o}\times
d_{o}}\rightarrow\operatorname{{\mathbb{R}}}$ denote loss function

6:Let $g(x,y)=\nabla{\cal L}(F(x;W),y)$ denote the gradients of loss function

7:Let $\widehat{g}=g(\sigma,x,y)|_{\sigma=\sigma_{0},x=x_{0},y=y_{0}}$ denote
the gradients computed on $x_{0}$ with label $y_{0}$, and secret mask
$\sigma_{0}$

8:procedure InputRecoveryfromGradients

9: $x^{(1)}\leftarrow\mathcal{N}(0,1)$, $y^{(1)}\leftarrow\mathcal{N}(0,1)$,
$\sigma^{(1)}\leftarrow\mathcal{N}(0,1)$ $\triangleright$ Random
initialization of the input, label and mask

10: for $t=1\rightarrow T$ do

11: Let $D_{g}(\sigma,x,y)=\|g(\sigma,x,y)-\widehat{g}\|_{2}^{2}$

12: $x^{(t+1)}\leftarrow
x^{(t)}-\eta\cdot\nabla_{x}D_{g}(\sigma,x,y)|_{x=x^{(t)}}$

13: $y^{(t+1)}\leftarrow
y^{(t)}-\eta\cdot\nabla_{y}D_{g}(\sigma,x,y)|_{y=y^{(t)}}$

14:
$\sigma^{(t+1)}\leftarrow\sigma^{(t)}-\eta\cdot\nabla_{y}D_{g}(\sigma,x,y)|_{\sigma=\sigma^{(t)}}$

15: end for

16: return $x^{(T+1)}$, $y^{(T+1)}$, $\sigma^{(T+1)}$

17:end procedure

Q1(CoLA): The magazines were sent to herself by Mary. ($\times$)
---
Baseline: The magazines were sent to herself by Mary. ($\times$)
Mix-only: The company  sent China its senior mining engineers  to help plan
the new mines. ($\times$)
TextHide: Hierarchy of Projections: (✓)
Q2(SST-2):  an exquisitely crafted and acted tale. ()
Baseline:  an exquisitely crafted and acted tale. ()
Mix-only: to make their way through this tragedy ()
TextHide: fails to live up to – or offer any new insight into – its chosen
topic ()
Table 7: Example queries and answer of RepRecon with different representation
schemes. Words with similar meanings are marked in the same color. For CoLA
examples, we annotate the acceptability (‘✓’ for yes, ‘$\times$’ for no); for
SST-2 examples, we annotate sentiment (‘’ for positive, ‘’ for negative).

| Baseline | Mix-only | TextHide | Rand
---|---|---|---|---
ID | 0.982 | 0.002 | 0.000 | 0.000
JCdist | 0.992 | 0.033 | 0.029 | 0.028
TF-IDFsim | 0.993 | 0.018 | 0.014 | 0.018
Label | 0.998 | 0.818 | 0.638 | 0.620
SBERTsim | 0.994 | 0.111 | 0.051 | 0.104
|  |  |  |
(a) RepRecon, CoLA

| Baseline | Mix-only | TextHide | Rand
---|---|---|---|---
ID | 0.948 | 0.000 | 0.000 | 0.000
JCdist | 0.953 | 0.065 | 0.064 | 0.080
TF-IDFsim | 0.949 | 0.019 | 0.013 | 0.014
Label | 0.968 | 0.464 | 0.472 | 0.452
SBERTsim | 0.959 | 0.268 | 0.266 | 0.211
|  |  |  |
(b) RepRecon, SST-2

Table 8: Similarity score of five metrics for RepRecon on CoLA (a) and SST-2
(b) datasets. We report the average score over 500 independent queries. Test
queries come from only the dev set. For each score, the scheme with the worst
similarity (best hiding) is marked in bold. As shown, attacker against
TextHide gives similar performance to random guessing.

###  C.1 Gradients matching attack

Algorithm 3 describes the gradients matching attack Zhu et al. (2019) in
TextHide setting. This attack aims to recover the original image from model
gradients computed on it. As discussed in Section 2, masks are kept private in
TextHide setting, thus the attacker also need to start from a dummy mask (line
9) and iteratively update it to compromise the real mask (line 14). In our
experiment, we made this attack much easier for the attacker, by revealing to
him the real ground truth label ($y_{0}$ in line 7), which means he simply
sets $y^{(t)}=y_{0}$ throughout the attack.

#### Dataset and architecture.

We used CIFAR-10 Krizhevsky (2009) as the dataset and LeNet-5 LeCun et al.
(1998) as the architecture to mimic TextHide.

Given the original LeNet-5, we firstly removed the last linear layer with
output size $d_{o}$, which gives us a new network. We use $d_{c}$ to denote
the size of output in the new network. Then, we appended an MLP with hidden-
layer size $d_{m}$ and output size $d_{o}$ to the new architecture. As in an
$(m,k)$-TextHide scheme, for each private input, we first gets its TextHide
representations by extracting the output from the hidden-layer, and mixes it
with representations of other datapoints. We then apply a mask on this
combination. Note: in this mimic setting, the mask’s dimension is $d_{m}$.

#### Hyper-parameters and running-time.

Following Zhu et al. (2019), we use L-BFGS Liu and Nocedal (1989) optimizer
(learning-rate 1, history-size 100 and max-iterations 20) and optimize for
1,200 iterations. Each run takes 97 seconds (single V100 GPU, averaged across
20 runs).

###  C.2 Representation-based Similarity Search (RSS)

#### Running-time.

For CoLA, building the search index takes $267$ seconds; each search takes
$<0.1$ seconds. For SST-2, building the index takes $1,576$ seconds; each
search takes $<0.1$ seconds.

###  C.3 Representation Reconstruction (RepRecon)

RepRecon tests whether a deep architecture can learn to disrupt our ‘hiding’
scheme. For an representation $e\in\operatorname{{\mathbb{R}}}^{d}$, and its
TextHide version $\widetilde{e}\in\operatorname{{\mathbb{R}}}^{d}$, RepRecon
tries to reconstruct $e$ from $\widetilde{e}$ by training a network
$f:\operatorname{{\mathbb{R}}}^{d}\rightarrow\operatorname{{\mathbb{R}}}^{d}$
such that $\|e-f(\widetilde{e})\|_{2}$ is minimized.

We use a multi-layer perception of hidden-layer size (1024, 1024) as the
reconstruction architecture. We train the network on the train set of a
benchmark for 20 epochs, and run evaluation using the dev set. We then run RSS
to map the recovered representation to its closet sentence in the index, and
measure the privacy leakage.

Quantitative and qualitative results of RepRecon are shown in Table 8 and
Table 7.


# On Finite-Time Mutual Information

Jieao Zhu, Zijian Zhang, Zhongzhichao Wan, and Linglong Dai  Beijing National
Research Center for Information Science and Technology (BNRist)
Department of Electronic Engineering, Tsinghua University, Beijing 100084,
China
E-mails: zja21, zhangzj20<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Shannon-Hartley theorem can accurately calculate the channel capacity when the
signal observation time is infinite. However, the calculation of finite-time
mutual information, which remains unknown, is essential for guiding the design
of practical communication systems. In this paper, we investigate the mutual
information between two correlated Gaussian processes within a finite-time
observation window. We first derive the finite-time mutual information by
providing a limit expression. Then we numerically compute the mutual
information within a single finite-time window. We reveal that the number of
bits transmitted per second within the finite-time window can exceed the
mutual information averaged over the entire time axis, which is called the
exceed-average phenomenon. Furthermore, we derive a finite-time mutual
information formula under a typical signal autocorrelation case by utilizing
the Mercer expansion of trace class operators, and reveal the connection
between the finite-time mutual information problem and the operator theory.
Finally, we analytically prove the existence of the exceed-average phenomenon
in this typical case, and demonstrate its compatibility with the Shannon
capacity.

###### Index Terms:

Finite-time mutual information, exceed-average, Mercer expansion, trace class,
operator theory.

##  I Introduction

The Shannon-Hartley theorem [1] has accurately revealed the fundamental
theoretical limit of information transmission rate $C$, which is also called
as the Shannon capacity, over a Gaussian waveform channel of a limited
bandwidth $W$. The expression for Shannon capacity is
$C=W\log\left(1+S/N\right)$, where $S$ and $N$ denote the signal power and the
noise power, respectively. The derivation of Shannon-Hartley Theorem heavily
depends on the Nyquist sampling principle [2]. The Nyquist sampling principle,
which is also named as the $2WT$ theorem [3], claims that one can only obtain
$2WT+o(2WT)$ independent samples within an observation time window $T$ in a
channel band-limited to $W$ [4].

Based on the Nyquist sampling principle, the Shannon capacity is derived by
multiplying the capacity $1/2\log(1+P/N)$ of a Gaussian symbol channel [5,
p.249] with $2WT+o(2WT)$ at first, and then dividing the result by $T$,
finally letting $T\rightarrow\infty$. Note that this approximation only holds
when $T\to\infty$. Therefore, the Shannon capacity only asymptotically holds
as $T$ becomes sufficiently large. When $T$ is of finite value, the
approximation fails to work. Thus, when the observation time $T$ is finite,
the Shannon-Hartley Theorem cannot be directly applied to calculate the
capacity in a finite-time window. To the best of our knowledge, the evaluation
of the finite-time mutual information has not yet been investigated in the
literature. It is worth noting that real-world communication systems transmit
signals in a finite-time window, thus evaluating the finite-time mutual
information is of practical significance.

In this paper, to fill in this gap, we analyze the finite-time mutual
information instead of the traditional infinite-time counterpart, and prove
the existence of exceed-average phenomenon within a finite-time observation
window111Simulation codes will be provided to reproduce the results presented
in this paper:
http://oa.ee.tsinghua.edu.cn/dailinglong/publications/publications.html..
Specifically, our contributions are summarized as follows:

  * •

We derive the mutual information expressions within a finite-time observation
window by using dense sampling and limiting methods. In this way, we can
overcome the continuous difficulties that appear when analyzing the
information contained in a continuous time interval. These finite-time mutual
information expressions make the analysis of finite-time problems possible.

  * •

We conduct numerical experiments based on the discretized formulas. In the
numerical results under a special setting, we reveal the exceed-average
phenomenon, i.e., the mutual information within a finite-time observation
window exceeds the mutual information averaged over the whole time axis.

  * •

In order to analytically prove the exceed-average phenomenon, we first derive
an analytical finite-time mutual information formula based on Mercer expansion
[6], where we can find the connection between the mutual information problem
and the operator theory [7]. To make the problem tractable, we construct a
typical case in which the transmitted signal has certain statistical
properties. Utilizing this construction, we obtain a closed-form mutual
information solution in this typical case, which leads to a rigorous proof of
the exceed-average phenomenon.

Organization: In the rest of this paper, the finite-time mutual information is
formulated and evaluated numerically in Section II, where the exceed-average
phenomenon is first discovered. Then, in Section III, we derive a closed-form
finite-time mutual information formula under a typical case. Based on this
formula, in Section IV, the exceed-average phenomenon is rigorously proved.
Finally, conclusions are drawn in Section V.

Notations: $X(t)$ denotes a Gaussian Process; $R_{X}(t_{1},t_{2})$ denotes the
autocorrelation function; $S_{X}(f),S_{X}(\omega)$ are the Power Spectral
Density (PSD) of the corresponding process $X(t)$; Boldface italic symbols
$\bm{X}(t_{1}^{n})$ denotes the column vector generated by taking samples of
$X(t)$ on instants $t_{i},1\leq i\leq n$; Upper-case boldface letters such as
${\bf{\Phi}}$ denote matrices; $\mathbb{E\left[\cdot\right]}$ denotes the
expectation; $\mathbbm{1}_{A}(\cdot)$ denotes the indicator function of the
set $A$; $\mathcal{L}^{2}([0,T])$ denotes the collection of all the square-
integrable functions on window $[0,T]$; ${\rm i}$ denotes the imaginary unit.

##  II Numerical Analysis of the Finite-Time Mutual Information

In this section, we numerically evaluate the finite-time mutual information.
In Subsection II-A, we model the transmission problem by Gaussian processes,
and derive the mutual information expressions within a finite-time observation
window; In Subsection II-B, we approximate the finite-time mutual information
by discretized matrix-based formulas; In Subsection II-C, we reveal the
exceed-average phenomenon by numerically evaluating the finite-time mutual
information.

###  II-A The Expressions for finite-time mutual information

Inspired by [8], we model the transmitted signal by a zero-mean stationary
Gaussian stochastic process, denoted as $X(t)$, and the received signal by
$Y(t):=X(t)+N(t)$. The noise process $N(t)$ is also a stationary Gaussian
process independent of $X(t)$. The receiver can only observe the signal within
a finite-time window $[0,T]$, where $T>0$ is the observation window span. We
aim to find the maximum mutual information that can be acquired within this
time window.

To analytically express the amount of acquired information, we first introduce
$n$ sampling points inside the time window, denoted by
$(t_{1},t_{2},\cdots,t_{n}):=t_{1}^{n}$, and then let $n\rightarrow\infty$ to
approximate the finite-time mutual information. By defining
${\bm{X}}(t_{1}^{n})\equiv(X(t_{1}),X(t_{2}),\cdots,X(t_{n}))$ and
${\bm{Y}}(t_{1}^{n})\equiv(Y(t_{1}),Y(t_{2}),\cdots,Y(t_{n}))$, the mutual
information on these $n$ samples can be expressed as

$I(t_{1}^{n})=I({\bm{X}}(t_{1}^{n});{\bm{Y}}(t_{1}^{n})),$ (1)

and the finite-time mutual information is defined as

$I(T)=\lim_{n\rightarrow\infty}\sup_{\\{t_{1}^{n}\\}\subset[0,T]}{I(t_{1}^{n})}.$
(2)

Then, the transmission rate $C(T)$ can be defined as $C(T)=I(T)/T$. After
these definitions, we can then define the limit mutual information as
$C(\infty)=\lim_{T\rightarrow\infty}{C(T)}$ by letting $T\rightarrow\infty$.

###  II-B Discretization

Without loss of generality, we fix the sampling instants uniformly onto
fractions of $T$: $t_{i}=(i-1)T/n,1\leq i\leq n$. Since the random vectors
${\bm{X}}(t_{1}^{n})$ and ${\bm{Y}}(t_{1}^{n})$ are samples of a Gaussian
process, they are both Gaussian random vectors with mean zero and covariance
matrices ${\bm{K}}_{X}$ and ${\bm{K}}_{Y}$, where
${\bm{K}}_{X},{\bm{K}}_{Y}\in\mathbb{R}^{n\times n}$ are symmetric positive-
definite matrices defined as

$\displaystyle({\bm{K}}_{X})_{i,j}$
$\displaystyle=R_{X}(t_{i},t_{j}):=\mathbb{E}\left[X(t_{i})X(t_{j})\right],$
(3) $\displaystyle({\bm{K}}_{Y})_{i,j}$
$\displaystyle=R_{Y}(t_{i},t_{j}):=\mathbb{E}\left[Y(t_{i})Y(t_{j})\right].$

Note that $Y(t)$ is the independent sum of $X(t)$ and $N(t)$, thus the
autocorrelation functions satisfy
$R_{Y}(t_{1},t_{2})=R_{X}(t_{1},t_{2})+R_{N}(t_{1},t_{2})$, and similarly the
covariance matrices satisfy ${\bm{K}}_{Y}={\bm{K}}_{X}+{\bm{K}}_{N}$.

The mutual information $I(t_{1}^{n})$ is defined as
$I(t_{1}^{n})=h({\bm{Y}}(t_{1}^{n}))-h({\bm{Y}}(t_{1}^{n})|{\bm{X}}(t_{1}^{n}))=h({\bm{Y}}(t_{1}^{n}))-h({\bm{N}}(t_{1}^{n}))$,
where $h(\cdot)$ denotes the differential entropy. Utilizing the entropy
formula for $n$-dimentional Gaussian vectors [5], we obtain

$I(t_{1}^{n})=\frac{1}{2}\log\left(\frac{\det({\bm{K}}_{X}+{\bm{K}}_{N})}{\det{({\bm{K}}_{N})}}\right).$
(4)

###  II-C Numerical Analysis

In order to study the properties of mutual information $I(t_{1}^{n})$ as a
function of $n$, we set the autocorrelation function of the signal process
$X(t)$ and noise process $N(t)$ to the following special case

$\displaystyle R_{X}(t_{1},t_{2})$
$\displaystyle=\mathrm{sinc}(10(t_{1}-t_{2})),$ (5) $\displaystyle
R_{N}(t_{1},t_{2})$ $\displaystyle=\exp(-\lvert t_{1}-t_{2}\rvert),$

where $\mathrm{sinc}(x):=\sin(\pi x)/(\pi x)$, and the corresponding PSDs are
$S_{X}(f)=0.1\times\mathbbm{1}_{\\{-5\leq f\leq 5\\}}$ and
$S_{N}(f)=\frac{2}{1+(2\pi f)^{2}}$. In order to compare the finite-time
mutual information with the averaged mutual information, the Shannon limit
with colored noise spectrum $S_{N}(f)$ is utilized, which is a generalized
version of the well-known formula $C=W\log\left(1+S/N\right)$. The averaged
mutual information of colored noise PSD [5] is expressed as

$C_{\rm
av}:=\frac{1}{2}\int_{-\infty}^{+\infty}{\log\left(1+\frac{S_{X}(f)}{S_{N}(f)}\right)\mathrm{d}f}.$
(6)

Then, plugging (5) into (6) yields the numerical result for $C_{\rm av}$.

We calculate the finite-time transmission rate $C(T)$ and the average mutual
information $C_{\rm av}$ against the number of samples $n$ within the
observation window $[0,T]$. The numerical results are collected in Fig. 1. It
is shown that $I(t_{1}^{n})$ is an increasing function of $n$, and for fixed
values of $T$, the approximated finite-time mutual information $I(t_{1}^{n})$
tends to a finite limit under the correlation assumptions given by (5). The
most amazing observation is that, it is possible to obtain more information
within finite-time window $[0,T]$ than the prediction $TC_{\rm av}$ given by
averaging the mutual information along the entire time axis (6). We call this
phenomenon the exceed-average phenomenon.

Figure 1: A first glance to the exceed-average phenomenon. The red dashed
horizontal line is the Shannon limit, and the $T=1,2,8$ curves illustrate the
dependence of $C(t_{1}^{n})$ on $n$.

##  III A Closed-Form Finite-Time Mutual Information Formula

In this section, we first introduce the Mercer expansion in Subsection III-A
as a basic tool for our analysis. Then we derive the series representation of
the finite-time mutual information, and the corresponding power constraint in
Subsection III-B, under the assumption of AWGN noise.

###  III-A The Mercer Expansion

By analyzing the structure of the autocorrelation functions, it is possible to
obtain $I(t_{1}^{n})$ and $I(T)$ directly. In fact, if we know the Mercer
expansion [6] of the autocorrelation function $R_{X}(t_{1},t_{2})$ on interval
$[0,T]$, then we can calculate $h({\bm{X}}(t_{1}^{n}))$ more easily [9]. In
the following discussion, we assume the Mercer expansion of the source
autocorrelation function $R_{X}(t_{1},t_{2})$ to be in the following form

$\lambda_{k}\phi_{k}(t_{1})=\int_{0}^{T}{R_{X}(t_{1},t_{2})\phi_{k}(t_{2})\mathrm{d}t_{2}};k>0,k\in\mathbb{N},$
(7)

where the eigenvalues are positive: $\lambda_{k}>0$, and the eigenfunctions
form an orthonormal set:

$\int_{0}^{T}{\phi_{i}(t)\phi_{j}(t)\mathrm{d}t}=\delta_{ij}.$ (8)

The Mercer’s theorem [6] ensures the existence and uniqueness of the
eigenpairs $(\lambda_{k},\phi_{k}(t))_{k=1}^{\infty}$, and furthermore, the
kernel itself can be expanded under the eigenfunctions:

$R_{X}(t_{1},t_{2})=\sum_{k=1}^{+\infty}{\lambda_{k}\phi_{k}(t_{1})\phi_{k}(t_{2})}.$
(9)

###  III-B Finite-Time Mutual Information Formula

Based on Mercer expansion, we obtain a closed-form formula in the following
Theorem 1.

######  Theorem 1 (Source expansion, AWGN noise)

Suppose the information source, modeled by the transmitted process $X(t)$, has
autocorrelation function $R_{X}(t_{1},t_{2})$. An AWGN noise of PSD $n_{0}/2$
is imposed onto $X(t)$, resulting in the received process $Y(t)$. The Mercer
expansion of $R_{X}(t_{1},t_{2})$ on $[0,T]$ is given by (7), satisfying (8).
Then the finite-time mutual information $I(T)$ within the observation window
$[0,T]$ between the processes $X(t)$ and $Y(t)$ can be expressed as

$I(T)=\frac{1}{2}\sum_{k=1}^{+\infty}{\log\left(1+\frac{\lambda_{k}}{n_{0}/2}\right)}.$
(10)

###### Proof:

The Mercer expansion decomposes the AWGN channel into an infinite number of
independent parallel subchannels, each with signal power $\lambda_{k}$ and
noise variance $n_{0}/2$. Thus, accumulating all the mutual information values
of these subchannels yields the finite-time mutual information $I(T)$. ∎

From Theorem 1 we can conclude that the finite-time mutual information of AWGN
channel is uniquely determined by the Mercer spectra $\lambda_{k}$ of
$R_{X}(t_{1},t_{2})$ within $[0,T]$. However, it remains unknown whether the
series representation (10) converges. In fact, the convergence is closely
related to the signal power, which is calculated in the following Lemma 1.

######  Lemma 1 (Operator Trace Coincide with Power Constraint)

Given stationary Gaussian process $X(t)$ with mean zero and autocorrelation
$R_{X}(t_{1},t_{2})$. The Mercer expansion of $R_{X}(t_{1},t_{2})$ on $[0,T]$
is given by (7), satisfying (8). The Mercer operator
$M(\cdot):\mathcal{L}^{2}([0,T])\rightarrow\mathcal{L}^{2}([0,T])$ is defined
by the integral
$(M\phi)(s)=\int_{0}^{T}{R_{X}(s,\tau)\phi(\tau)\mathrm{d}\tau}$. Then the sum
of all the eigenvalues $\lambda_{k}$ of operator $M$ is equal to the signal
energy $PT$ within $[0,T]$:

$\mathrm{tr}(M):=\sum_{k=1}^{+\infty}{\lambda_{k}}=PT,$ (11)

where $P=R_{X}(0,0)$.

###### Proof:

Integrating both sides of (9) on the interval $[0,T]$ gives the conclusion
immediately. ∎

###### Remark 1

From the above Lemma 1, we can conclude that the sum of $\lambda_{k}$ is
finite when $T$ is finite. It can be immediately derived that $I(T)<\infty$,
since $\log(1+x)\leq x$.

###### Remark 2

The finite-time mutual information formula (10) is closely related to the
operator theory [7] in functional analysis. The sum of all the eigenvalues
$\lambda_{k}$ is called the operator trace in linear operator theory. As is
mentioned in Lemma 1, the autocorrelation function $R_{X}(t_{1},t_{2})$ can be
treated as a linear operator $M$ on $\mathcal{L}^{2}([0,T])$.

##  IV Proof of the Existence of Exceed-Average Phenomenon

In this section, we first give a proof of the existence of the exceed-average
phenomenon in a typical case, then we discuss the compatibility with the
Shannon-Hartley theorem.

###  IV-A Closed-Form Mutual Information in a Typical Case

To prove the exceed-average phenomenon, we only need to show that the finite-
time mutual information is greater than the averaged mutual information in a
typical case. Let us consider a finite-time communication scheme with a
finitely-powered stationary transmitted signal autocorrelation222The signal
autocorrelation $R_{X}(\tau)$ is often observed in many scenarios, such as
passing a signal with white spectrum through an RC lowpass filter., which is
specified as

$R_{X}(t_{1},t_{2})=R_{X}(\tau)=P\exp(-\alpha\lvert\tau\rvert),$ (12)

where $\tau=t_{1}-t_{2}$, under AWGN channel with noise PSD being $n_{0}/2$.
The power of signal $X(t)$ is $P=R_{X}(0)$. According to Lemma 1, the trace of
the corresponding Mercer operator $M(\cdot)$ is finite. Then the finite-time
mutual information given by Theorem 1 is also finite, as is shown in Remark 1.
Finding the Mercer expansion is equivalent to finding the eigenpairs
$(\lambda_{k},\phi_{k}(t))_{k=1}^{\infty}$. The eigenpairs are determined by
the following characteristic integral equation [10]:

$\lambda_{k}\phi_{k}(s)=\int_{0}^{s}{Pe^{-\alpha(s-t)}\phi_{k}(t)\mathrm{d}t}+\int_{s}^{T}{Pe^{-\alpha(t-s)}\phi_{k}(t)\mathrm{d}t}.$
(13)

Differentiating both sides of (13) twice with respect to $s$ yields the
boundary conditions and the differential equation that $\lambda_{k},\phi_{k}$
must satisfy:

$\displaystyle\lambda_{k}\phi_{k}^{\prime\prime}(s)$
$\displaystyle=(\alpha^{2}\lambda_{k}-2\alpha P)\phi_{k}(s),0<s<T,$ (14)
$\displaystyle\phi_{k}^{\prime}(0)$ $\displaystyle=\alpha\phi_{k}(0),$
$\displaystyle\phi_{k}^{\prime}(T)$ $\displaystyle=-\alpha\phi_{k}(T).$

Let $\omega_{k}>0$ denote the resonant frequency of the above harmonic
oscillator equation, and let
$\phi_{k}(t)=A_{k}\cos(\omega_{k}t)+B_{k}\sin(\omega_{k}t)$ be the sinusoidal
form of the eigenfunction. Using the boundary conditions we obtain

$\displaystyle B_{k}\omega_{k}=\alpha A_{k},$ (15) $\displaystyle
B_{k}\omega_{k}\cos(\omega_{k}T)-A_{k}\omega_{k}\sin(\omega_{k}T)$
$\displaystyle=-\alpha\left(A_{k}\cos(\omega_{k}T)+B_{k}\sin(\omega_{k}T)\right).$

Figure 2: Images of $2\arctan(\omega/\alpha)$ and $k\pi-\omega T$ with
$T=2,\alpha=1$ and $k=1,2,3,4$. The desired resonant frequencies $\omega_{k}$
can be read from the horizontal coordinates of the intersection points of the
curve $2\arctan(\omega/\alpha)$ and the parallel lines.

To ensure the existence of solution to the homogeneous linear equations (15)
with unknowns $A_{k},B_{k}$, the determinant must be zero. Exploiting this
condition, we find that $\omega_{k}$ naturally satisfy the transcendental
equation
$\tan(\omega_{k}T)=(2\omega_{k}\alpha)/({\omega_{k}^{2}-\alpha^{2}})$. By
introducing an auxillary variable
$\theta_{k}=\arctan(\omega_{k}/\alpha)\in[0,\pi/2]$, this transcendental
equation can be simplified as $\tan(\omega_{k}T)=-\tan(2\theta_{k})$, i.e.,
there exists positive integer $m$ such that
$2\arctan(\omega_{k}/\alpha)=m\pi-\omega_{k}T$. The integer $m$ can be chosen
to be equal to $k$. From the function images of $2\arctan(\omega/\alpha)$ and
$k\pi-\omega T$ (Fig. 2), we can determine $\omega_{k}$, and then
$\lambda_{k}$. To sum up, the solution to the characteristic equation (13) are
collected into (16) as follows.

$\displaystyle 2\arctan(\omega_{k}/\alpha)$ $\displaystyle=k\pi-\omega_{k}T,$
(16) $\displaystyle\lambda_{k}$ $\displaystyle=\frac{2\alpha
P}{\alpha^{2}+\omega_{k}^{2}},$ $\displaystyle\phi_{k}(t)$
$\displaystyle=\frac{1}{Z_{k}}\left(\omega_{k}\cos(\omega_{k}t)+\alpha\sin(\omega_{k}t)\right),$

where $Z_{k}$ denotes the normalization constants of $\phi_{k}(t)$ on $[0,T]$
to ensure orthonormality.

Equation (16) gives all the eigenpairs
$(\lambda_{k},\phi_{k})_{k=1}^{\infty}$, from which we can calculate $I(T)$ by
applying Theorem 1. As for the Shannon limit $C_{\rm sh}$, by applying (6) and
evaluating the integral with [11] we can obtain

$C_{\rm av}=C_{\rm
sh}=\frac{1}{2}\left(\sqrt{\alpha^{2}+\frac{4P\alpha}{n_{0}}}-\alpha\right).$
(17)

After all the preparation works above, we can rigorously prove that
$C(T)>C_{\rm av}$ under the typical case of (12), as long as the transmission
power $P$ is smaller than a constant $\delta$. The following Theorem 2 proves
this result.

######  Theorem 2 (Existence of exceed-average phenomenon in a typical case)

Suppose $X(t)$ and $Y(t)$ are specified according to (12). The eigenpairs are
determined by (16). Then, for any fixed positive values of $T,n_{0}$ and
$\alpha$, there exists $\delta>0$ such that the exceed-average inequality

$C(T):=\frac{1}{2T}\sum_{k=1}^{+\infty}\log\left(1+\frac{\lambda_{k}}{n_{0}/2}\right)>C_{\rm
av}$ (18)

holds strictly for arbitrary $0<P<\delta$.

###### Proof:

See Appendix A. ∎

Figure 3: Theoretical verification of the exceed-average effect. The blue
lines represent the finite-time mutual information $I(T)$. The red lines are
the average mutual information $TC_{\rm av}$, calculated from (6). All the
curves are evaluated under hypothesis (12), where $P=1,2,4$, $n_{0}=1$ and
$\alpha=1$.

To support the above theoretical analysis, numerical experiments on $I(T)$ are
conducted based on evaluations of (16) and (17). As shown in Fig. 3, it seems
that we can always harness more mutual information in a finite-time
observation window than the averaged mutual information. This fact is somehow
unsurprising because the observations ${\bm{Y}}(t_{1}^{N})$ inside the window
$[0,T]$ can always eliminate some extra uncertainty outside the window due to
the autocorrelation of $X(t)$.

###  IV-B Compatibility with the Shannon-Hartley theorem

Though the exceed-average effect do imply mathematically that the mutual
information within a finite-time window is higher than the average mutual
information $C_{\rm av}$ (which coincides with the Shannon limit (6) in this
case), in fact, it is still impossible to construct a long-time stable data
transmission scheme above the Shannon capacity by leveraging this effect. So
the exceed-average phenomenon does not contradict the Shannon-Hartley Theorem.
Placing additional observation windows cannot increase the average information
rate, because the posterior process $Y(t)|{\bm{Y}}(t_{1}^{N})$ does not carry
as much information as the original one, causing a rate reduction in the later
windows. It is expected that, the finite-time mutual information would
ultimately decrease to the average mutual information as the total observation
time tends to infinity (i.e., $C(\infty)=C_{\rm av}$), and the analytical
proof, as well as the achievability of this finite-time mutual information, is
still worth investigation in future works.

##  V Conclusions

In this paper, we provided rigorous proofs of the existence of the exceed-
average phenomenon under typical autocorrelation settings of the transmitted
signal process and the noise process. Our discovery of the exceed-average
phenomenon provided a generalization of Shannon’s renowned formula
$C=W\log(1+S/N)$ to the practical finite-time communications. Since the
finite-time mutual information is a more precise estimation of the capacity
limit, the optimization target may shift from the average mutual information
to the finite-time mutual information in the design of practical communication
systems. Thus, it may have guiding significance for the performance
improvement of modern communication systems. In future works, general proofs
of $C(T)>C_{\rm av}$, independent of the concrete autocorrelation settings,
still require further investigation. Moreover, we need to answer the question
of how to exploit this exceed-average phenomenon to improve the communication
rate, and whether this finite-time mutual information is achievable by a
certain coding scheme. In addition, although we have discovered numerically
that the finite-time mutual information agrees with the Shannon capacity when
$T\rightarrow\infty$, an analytical proof of this result is required in the
future.

## Appendix A
Proof Of Theorem 2

Plugging (17) into the right-hand side of (18), and differentiate both sides
w.r.t $P$. Notice that if $P=0$, then both sides of (18) are equal to 0. Thus,
we only need to prove that the derivative of left-hand side is strictly larger
than that of right-hand side within a small interval $P\in(0,\delta)$:

$\frac{1}{2}\sum_{k=1}^{+\infty}{\left(\frac{1}{1+\frac{2\lambda_{k}}{n_{0}}}\frac{2\lambda_{k}}{n_{0}P}\right)}>\frac{T}{n_{0}}\frac{1}{\sqrt{1+4P/(n_{0}\alpha)}}.$
(19)

Multiply both sides of (19) by $n_{0}$ and define $\mu_{k}:=\lambda_{k}/(PT)$,
and then from Lemma 1 we obtain $\sum_{k}{\mu_{k}}=1$. In this way, (19) is
equivalent to

$\sum_{k=1}^{+\infty}{\frac{\mu_{k}}{1+\frac{2\lambda_{k}}{n_{0}}}}>\frac{1}{\sqrt{1+4P/(n_{0}\alpha)}}.$
(20)

Since $\varphi(x):=1/(1+2x/n_{0})$ is convex on $(0,+\infty)$, by applying
Jensen’s inequality to the left-hand side of (20), we only need to prove that

$\frac{1}{1+\frac{2}{n_{0}}\sum_{k}{\lambda_{k}\mu_{k}}}>\frac{1}{\sqrt{1+4P/(n_{0}\alpha)}}.$
(21)

From the definition of $\mu_{k}$ we can derive that
$\lambda_{k}\mu_{k}=\lambda_{k}^{2}/(PT)$. So we go on to calculate
$\sum_{k}{\lambda_{k}^{2}}$. That is equivalent to calculate
$\mathrm{tr}(M^{2})$, where $M^{2}$ corresponds to the integral kernel:

$K_{M^{2}}(t_{1},t_{2}):=\int_{0}^{T}{P^{2}\exp(-\alpha\lvert
t_{1}-s\rvert)\exp(-\alpha\lvert t_{2}-s\rvert)\mathrm{d}s}.$ (22)

Evaluating the kernel $K_{M^{2}}$ on the diagonal $t=t_{1}=t_{2}$, and
integrating this kernel on the diagonal of $[0,T]^{2}$ gives
$\sum_{k}{\lambda_{k}^{2}}$, i.e., $\mathrm{tr}(M^{2})$:

$\displaystyle\sum_{k}{\lambda_{k}^{2}}$
$\displaystyle=\frac{P^{2}}{2\alpha}\int_{0}^{T}{\left(2-e^{-2\alpha
t}-e^{-2\alpha(T-t)}\right)\mathrm{d}t},$ (23)
$\displaystyle=\frac{P^{2}}{\alpha}\left(T-\frac{1}{2\alpha}(1-e^{-2\alpha
T})\right).$

By substituting (23) into (21), we just need to prove that

$\sqrt{1+4P/(n_{0}\alpha)}>1+\frac{2P}{n_{0}\alpha}\left(1-\frac{1-e^{-2\alpha
T}}{2\alpha T}\right).$ (24)

Define the dimensionless number $x=2P/(n_{0}\alpha)$. Since the function
$\psi(x):=(1-\exp(-x))/x$ is strictly positive and less than 1 at $x>0$, we
can conclude that, there exists a small positive $\delta>0$ such that (24)
holds for $0<P<\delta$. The number $\delta$ can be chosen as

$\delta=\frac{n_{0}\alpha\psi(2\alpha T)}{(1-\psi(2\alpha T))^{2}}>0,$ (25)

which implies that (19) holds for any $0<P<\delta$. Thus, integrating (19) on
both sides from $p=0$ to $p=P,P<\delta$ gives rise to the conclusion (18),
which completes the proof of Theorem 2.

## Acknowledgment

This work was supported in part by the National Key Research and Development
Program of China (Grant No.2020YFB1807201), in part by the National Natural
Science Foundation of China (Grant No. 62031019), and in part by the European
Commission through the H2020-MSCA-ITN META WIRELESS Research Project under
Grant 956256.

## References

  * [1] C. E. Shannon, “A mathematical theory of communication,” _The Bell Syst. Techni. J._ , vol. 27, no. 3, pp. 379–423, Jul. 1948.
  * [2] H. Landau, “Sampling, data transmission, and the nyquist rate,” _Proc. IEEE_ , vol. 55, no. 10, pp. 1701–1706, Oct. 1967.
  * [3] H. Nyquist, “Certain topics in telegraph transmission theory,” _Trans. American Institute of Electrical Engineers_ , vol. 47, no. 2, pp. 617–644, Apr. 1928.
  * [4] D. Slepian, “On bandwidth,” _Proc. IEEE_ , vol. 64, no. 3, pp. 292–300, Mar. 1976.
  * [5] T. M. Cover, _Elements of information theory_. John Wiley & Sons, 1999.
  * [6] J. Mercer, “Functions of positive and negative type and their connection with the theory of integral equations,” _Philos. Trans. Royal Soc._ , vol. 209, pp. 4–415, 1909.
  * [7] K. Zhu, _Operator theory in function spaces_. American Mathematical Soc., 2007, no. 138.
  * [8] A. Balakrishnan, “A note on the sampling principle for continuous signals,” _IRE Trans. Inf. Theory_ , vol. 3, no. 2, pp. 143–146, Jun. 1957.
  * [9] J. Barrett and D. Lampard, “An expansion for some second-order probability distributions and its application to noise problems,” _IRE Trans. Inf. Theory_ , vol. 1, no. 1, pp. 10–15, Mar. 1955.
  * [10] D. Cai and P. S. Vassilevski, “Eigenvalue problems for exponential-type kernels,” _Comput. Methods in Applied Math._ , vol. 20, no. 1, pp. 61–78, Jan. 2020.
  * [11] I. S. Gradshteyn and I. M. Ryzhik, _Table of integrals, series, and products_. Academic press, 2014.