# Convergence of block coordinate descent with diminishing radius
For nonconvex optimization

Hanbaek Lyu  Hanbaek Lyu, Department of Mathematics, University of California,
Los Angeles, CA 90095, USA<EMAIL_ADDRESS>
###### Abstract.

Block coordinate descent (BCD), also known as nonlinear Gauss-Seidel, is a
simple iterative algorithm for nonconvex optimization that sequentially
minimizes the objective function in each block coordinate while the other
coordinates are held fixed. It is known that block-wise convexity of the
objective is not enough to guarantee convergence of BCD to the stationary
points and some additional regularity condition is needed. In this work, we
provide a simple modification of BCD that has guaranteed global convergence to
the stationary points for block-wise convex objective function without
additional conditions. Our idea is to restrict the parameter search within a
diminishing radius to promote stability of iterates, and then to show that
such auxiliary constraint vanishes in the limit. As an application, we provide
a modified alternating least squares algorithm for nonnegative CP tensor
factorization that is guaranteed to converge to the stationary points of
reconstruction error function. We also provide some experimental validation of
our result.

The codes for the main algorithm and simulations are provided in
https://github.com/HanbaekLyu/BCD-DR

##  1\. Introduction

Throughout this paper, we are interested in the minimization of a continuous
function $f:\mathbb{R}^{I_{1}}\times\dots\times
R^{I_{m}}\rightarrow[0,\infty)$ on a cartesian product of convex sets
$\boldsymbol{\Theta}=\Theta^{(1)}\times\dots\times\Theta^{(m)}$:

(1)
$\displaystyle\boldsymbol{\theta}^{*}\in\operatorname*{arg\,min}_{\boldsymbol{\theta}=[\theta_{1},\dots,\theta_{m}]\in\boldsymbol{\Theta}}f(\theta_{1},\dots,\theta_{m}).$

When the objective function $f$ is nonconvex, convergence of any algorithm for
solving (1) to a globally optimal solution can hardly be expected. Instead,
global convergence to stationary points of the objective function is desired.

Block coordinate descent (BCD), also known as nonlinear Gauss-Seidel [5], is a
simple iterative algorithm that sequentially minimizes the objective function
in each block coordinate while the other coordinates are held fixed. Due to
its simplicity, BCD has been widely used in various optimization problems such
as nonnegative matrix or tensor factorization [14, 15, 11]. More precisely,
fix an initial estimate $\boldsymbol{\theta}_{0}\in\boldsymbol{\Theta}$, and
obtain a new estimate $\boldsymbol{\theta}_{n}$ from the previous one
$\boldsymbol{\theta}_{n-1}$ by successively updating the $i^{\textup{th}}$
block coordinate using the following rule for $i=1,\dots,m$:

(2)
$\displaystyle\theta_{n}^{(i)}\in\operatorname*{arg\,min}_{\theta\in\Theta^{(i)}}f\left(\theta_{n}^{(1)},\cdots,\theta_{n}^{(i-1)},\theta,\theta_{n-1}^{(i+1)},\cdots,\theta_{n-1}^{(m)}\right).$

Then (2) generates a sequence of esimates
$\boldsymbol{\theta}_{n}=[\theta_{n}^{(1)},\dots,\theta_{n}^{(m)}]$ for $n\geq
1$. While it is easy to see that the objective function is non-increasing
under BCD iteration, however, it is known that BCD does not always converge to
the stationary points of the objective function that is convex in each block
coordinate [19], and there is a number of work that obtains such convergence
guarantee with additional conditions on suitable strong convexity assumptions
[1, 7, 9, 9, 10, 16, 18, 28, 30].

In this work, we intend to generalize the global convergence guarantee of BCD
to a setting where the objective function $f$ is only convex in each block
coodinatee, by imposting a simple additional constraint in the algorithm. As
pointed out in [5, Prop. 2.7.1], a necessary property that implies convergence
of BCD to stationary points is the “stability of estimates”, that the change
made in each block update (2) vanishes. Essentially, our idea is to bake this
stability property into the algorithm by restricting the range of parameter
search within a diminishing radius from the previous estimation, and then show
that such additional constraint vanishes in the limit. This modified BCD with
diminishing radius is stated in Algorithm 1. We denote by
$\lVert\cdot\rVert_{F}$ the Frobenius norm.

Algorithm 1 Block Coordinate Descent with Diminishing Radius (BCD-DR)

1:Input:
$\boldsymbol{\theta}_{0}=(\theta_{0}^{(1)},\cdots,\theta_{0}^{(m)})\in\Theta^{(1)}\times\cdots\times\Theta^{(m)}$
(initial estimate); $N$ (number of iterations); $(w_{n})_{n\geq 1}$, (weights
in $(0,1]$); $c^{\prime}>0$ (search radius constant);

2: for $n=1,\cdots,N$ do:

3: Update estimate
$\boldsymbol{\theta}_{n}=[\theta_{n}^{(1)},\cdots,\theta_{n}^{(m)}]$ by

4: For $i=1,\cdots,m$ do:  (3)
$\displaystyle\qquad\theta_{n}^{(i)}\in\operatorname*{arg\,min}_{\theta\in\Theta^{(i)},\,\lVert\theta-\theta_{n-1}^{(i)}\rVert_{F}\leq
c^{\prime}w_{n}}f\left(\theta_{n}^{(1)},\cdots,\theta_{n}^{(i-1)},\theta,\theta_{n-1}^{(i+1)},\cdots,\theta_{n-1}^{(m)}\right);$

5: end for

6: end for

7:output: $\boldsymbol{\theta}_{N}$

###  1.1. Main result

Our main result, stated in Theorem 1.1, shows that Algorithm 1 converges to
the stationary points of the objective function $f$ over $\boldsymbol{\Theta}$
with mild assumptions (A1)-(A2). In particular, our convergence result does
not require strong convexity of $f$ in some blocks nor uniqueness of minimizer
in each sub-problem of block minimization.

######  (A1).

The constraint sets $\Theta^{(i)}\subseteq\mathbb{R}^{I_{i}}$, $i=1,\dots,m$
are convex and compact.

######  (A2).

The function
$f:\Theta^{(1)}\times\dots\times\Theta^{(m)}\rightarrow[0,\infty)$ is
continuously differentiable and convex in each block coordinate (but not
necessarily jointly convex).

######  Theorem 1.1.

Assume (A1) and (A2). Suppose weights $(w_{n})_{n\geq 1}$ satisfy
$\sum_{n=1}^{\infty}w_{n}=\infty$ and $\sum_{n=1}w_{n}^{2}<\infty$. Let
$(\boldsymbol{\theta}_{n})_{n\geq 0}$ be an output of Algorithm 1. Then for
every initial estimate $\boldsymbol{\theta}_{0}\in\boldsymbol{\Theta}$,
$\boldsymbol{\theta}_{n}$ converges to the set of stationary points of $f$
over $\boldsymbol{\Theta}$.

It is important to note that under (A1)-(A2), the sub-problem of block
minimization (3) is a convex minimization problem over a convex set
$\Theta^{(i)}\cap\\{\theta\colon\lVert\theta-\theta^{(i)}_{n-1}\rVert_{F}\leq
c^{\prime}w_{n}\\}$, so Algorithm 1 can be readily executed using standard
convex optimization problems (see, e.g., [5]).

##  2\. Proof of main results

We prove Theorem 1.1 in this section. We start by recalling a classical lemma
on first order approximation of functions with Lipshitz gradients.

######  Lemma 2.1 (First-order approximation of functions with Lipschitz
gradient).

Let $f:\mathbb{R}^{p}\rightarrow\mathbb{R}$ be differentiable and $\nabla f$
be $L$-Lipschitz continuous. Then for each
$\theta,\theta^{\prime}\in\mathbb{R}^{p}$,

(4) $\displaystyle\left|f(\theta^{\prime})-f(\theta)-\nabla
f(\theta)^{T}(\theta^{\prime}-\theta)\right|\leq\frac{L}{2}\lVert\theta-\theta^{\prime}\rVert_{F}^{2}.$

###### Proof.

This is a classical Lemma. See [17, Lem 1.2.3]. ∎

######  Proposition 2.2 (Forward monotonicity).

Suppose (A1)-(A2). Let $(\boldsymbol{\theta}_{n})_{n\geq 1}$ be an output of
Algorithm 1. Then $f(\boldsymbol{\theta}_{n-1})\geq
f(\boldsymbol{\theta}_{n})$ for all $n\geq 1$.

###### Proof.

Write $\boldsymbol{\theta}_{t}=[\theta_{t}^{(1)},\dots,\theta_{t}^{(m)}]$ for
each $t\geq 1$. Then note that

$\displaystyle f(\boldsymbol{\theta}_{n-1})-f(\boldsymbol{\theta}_{n})$
$\displaystyle\quad=\sum_{i=1}^{n}f([\theta_{n}^{(1)},\dots,\theta_{n}^{(i-1)},\theta_{n-1}^{(i)},\theta_{n-1}^{(i+1)},\dots,\theta_{n-1}^{(m)}])-f([\theta_{n}^{(1)},\dots,\theta_{n}^{(i-1)},\theta_{n}^{(i)},\theta_{n-1}^{(i+1)},\dots,\theta_{n-1}^{(m)}])$

Recall that $\theta_{n}^{(i)}$ is a minimizer of the convex function
$\theta\mapsto
f([\theta_{n}^{(1)},\dots,\theta_{n}^{(i-1)},\theta,\theta_{n-1}^{(i+1)},\dots,\theta_{n-1}^{(m)}])$
over the convex set
$\Theta^{(i)}_{n}:=\Theta^{(i)}\cap\\{\theta\colon\lVert\theta-\theta_{n-1}^{(i)}\rVert_{F}\leq
c^{\prime}w_{t}\\}$. Also, $\theta_{n-1}^{(i)}\in\Theta_{n}^{(i)}$. Hence each
summand in the last expression above is nonnegative. This shows
$f(\boldsymbol{\theta}_{n-1})-f(\boldsymbol{\theta}_{n})\geq 0$, as desired. ∎

######  Proposition 2.3 (Finite first-order variation).

Assume (A1), (A2), and $\sum_{n=1}^{\infty}w_{n}^{2}<\infty$. Let
$(\boldsymbol{\theta}_{n})_{n\geq 1}$ be an output of Algorithm 1. Then

$\displaystyle\sum_{n=1}^{\infty}\left|\textup{tr}\left(\nabla
f(\boldsymbol{\theta}_{n+1})^{T}(\boldsymbol{\theta}_{n}-\boldsymbol{\theta}_{n+1})\right)\right|<\infty.$

###### Proof.

According to (A1)-(A2), it follows that $\nabla f$ over $\boldsymbol{\Theta}$
is Lipschitz with some uniform Lipshitz constant $L>0$. Hence by Lemma 2.1,
for all $t\geq 1$,

$\displaystyle\left|f(\boldsymbol{\theta}_{n})-f(\boldsymbol{\theta}_{n+1})-\textup{tr}\left(\nabla
f(\boldsymbol{\theta}_{n+1})^{T}(\boldsymbol{\theta}_{n}-\boldsymbol{\theta}_{n+1})\right)\right|\leq\frac{L}{2}\lVert\boldsymbol{\theta}_{n}-\boldsymbol{\theta}_{n+1}\|_{F}^{2}.$

By Proposition 2.2, $f(\boldsymbol{\theta}_{n})\geq
f(\boldsymbol{\theta}_{n+1})$ for each $n\geq 1$. Hence it follows that

(5) $\displaystyle\left|\textup{tr}\left(\nabla
f(\boldsymbol{\theta}_{n+1})^{T}(\boldsymbol{\theta}_{n}-\boldsymbol{\theta}_{n+1})\right)\right|\leq\frac{L}{2}\lVert\boldsymbol{\theta}_{n}-\boldsymbol{\theta}_{n+1}\|_{F}^{2}+f(\boldsymbol{\theta}_{n})-f(\boldsymbol{\theta}_{n+1})$

Note that
$\lVert\boldsymbol{\theta}_{n}-\boldsymbol{\theta}_{n+1}\rVert_{F}^{2}=O(w_{n+1}^{2})$
and $\sum_{n=1}^{\infty}w_{n}^{2}<\infty$. Also note that
$\sum_{t=1}^{n}f(\boldsymbol{\theta}_{t})-f(\boldsymbol{\theta}_{t+1})=f(\boldsymbol{\theta}_{1})-f(\boldsymbol{\theta}_{n+1})\leq
f(\boldsymbol{\theta}_{1})$. Hence we get

$\displaystyle\sum_{n=1}^{\infty}\left|\textup{tr}\left(\nabla
f(\boldsymbol{\theta}_{n+1})^{T}(\boldsymbol{\theta}_{n}-\boldsymbol{\theta}_{n+1})\right)\right|$
$\displaystyle\leq\frac{L}{2}\left(\sum_{n=1}^{\infty}\lVert\boldsymbol{\theta}_{n}-\boldsymbol{\theta}_{n+1}\|_{F}^{2}\right)+f(\boldsymbol{\theta}_{1})<\infty,$

as desired. ∎

Next, we show that the block coordinate descent we use to obtain
$\boldsymbol{\theta}_{n+1}$ should always give the optimal first order descent
up to an additive error of order $O(w_{n+1})$.

######  Proposition 2.4 (Asymptotic first-order optimality).

Assume (A1) and (A2). Then there exists a constant $c>0$ such that for all
$t\geq 1$,

(6) $\displaystyle\textup{tr}\left(\nabla
f(\boldsymbol{\theta}_{n})^{T}\frac{(\boldsymbol{\theta}_{n+1}-\boldsymbol{\theta}_{n})}{\lVert\boldsymbol{\theta}_{n+1}-\boldsymbol{\theta}_{n}\rVert_{F}}\right)\leq\inf_{\boldsymbol{\theta}\in\boldsymbol{\Theta}}\textup{tr}\left(\nabla
f(\boldsymbol{\theta}_{n})^{T}\frac{(\boldsymbol{\theta}-\boldsymbol{\theta}_{n})}{\lVert\boldsymbol{\theta}-\boldsymbol{\theta}_{n}\rVert_{F}}\right)+cw_{n+1}.$

###### Proof.

Write $\boldsymbol{\theta}_{t}=[\theta^{(1)}_{t},\dots,\theta^{(m)}_{t}]$ for
$t\geq 1$ and denote $f_{n+1;i}:\theta\mapsto
f(\theta_{n+1}^{(1)},\dots,\theta_{n+1}^{(i-1)},\theta,\theta_{n}^{(i+1)},\dots,\theta_{n}^{(m)})$
for $\theta\in\mathbb{R}^{I_{i}}$ and $i=1,\dots,m$. Recall that
$\theta_{n+1}^{(i)}$ is a minimizer of $f_{n+1;i}$ over the convex set
$\Theta^{(i)}_{n}:=\Theta^{(i)}\cap\\{\theta\colon\lVert\theta-\theta_{n-1}^{(i)}\rVert_{F}\leq
c^{\prime}w_{n}\\}$. By convexity of $\Theta^{(i)}$, note that for each
$\theta^{(i)}\in\Theta^{(i)}$,
$\theta_{n}^{(i)}+a(\theta^{(i)}-\theta_{n}^{(i)})\in\Theta^{(i)}$ for all
$a\in[0,1]$. Hence denoting
$\lVert\Theta^{(i)}\rVert_{F}:=\sup_{U,U^{\prime}\in\Theta^{(i)}}\lVert
U-U^{\prime}\rVert_{F}<\infty$,

(7) $\displaystyle f_{n+1;i}(\theta_{n+1}^{(i)})\leq
f_{n+1;i}\left(\theta_{n}^{(i)}+\frac{cw_{n+1}}{\lVert\Theta^{(i)}\rVert_{F}}(\theta^{(i)}-\theta_{n}^{(i)})\right)$

for all $t\geq 1$. Recall that $\nabla f=[\nabla f_{n+1;1},\dots,\nabla
f_{n+1;m}]$ is Lipschitz with uniform Lipschitz constant $L>0$. Hence by Lemma
2.1,

(8) $\displaystyle\textup{tr}\left(\nabla
f_{n+1;i}(\theta_{n}^{(i)})^{T}\frac{(\theta_{n+1}^{(i)}-\theta_{n}^{(i)})}{\lVert\theta_{n+1}^{(i)}-\theta_{n}^{(i)}\rVert_{F}}\right)\leq\textup{tr}\left(\nabla
f_{n+1;i}(\theta_{n}^{(i)})^{T}\frac{(\theta^{(i)}-\theta_{n}^{(i)})}{\lVert\theta_{i}-\theta_{n}^{(i)}\rVert_{F}}\right)+Lc^{\prime}w_{n+1}.$

Adding up these inequalities for $i=1,\dots,m$ and writing
$\boldsymbol{\theta}=[\theta_{1},\dots,\theta_{m}]\in\boldsymbol{\Theta}$, we
get

(9) $\displaystyle\textup{tr}\left(\nabla
f(\boldsymbol{\theta}_{n})^{T}\frac{(\boldsymbol{\theta}_{n+1}-\boldsymbol{\theta}_{n})}{\lVert\boldsymbol{\theta}_{n+1}-\boldsymbol{\theta}_{n}\rVert_{F}}\right)$
$\displaystyle\leq\textup{tr}\left(\left[\nabla
f_{n+1;1}(\theta_{n}^{(1)}),\dots,f_{n+1;m}(\theta_{n}^{(m)})\right]^{T}\frac{(\boldsymbol{\theta}-\boldsymbol{\theta}_{n})}{\lVert\boldsymbol{\theta}-\boldsymbol{\theta}_{n}\rVert_{F}}\right)+mLc^{\prime}w_{n+1}$
(10) $\displaystyle\leq\textup{tr}\left(\nabla
f(\boldsymbol{\theta}_{n})^{T}\frac{(\boldsymbol{\theta}-\boldsymbol{\theta}_{n})}{\lVert\boldsymbol{\theta}-\boldsymbol{\theta}_{n}\rVert_{F}}\right)+m(L+1)c^{\prime}w_{n+1},$

where the second inequality follows from Lipschitz continuity of $\nabla f$.
Since $\boldsymbol{\theta}\in\boldsymbol{\Theta}$ was arbitrary, this shows
the assertion. ∎

######  Proposition 2.5 (Sufficient condition for stationarity I).

Assume (A1), (A2), and $\sum_{n=1}^{\infty}w_{n}^{2}<\infty$. Suppose there
exists a subsequence $(\boldsymbol{\theta}_{n_{k}})_{k\geq 1}$ such that
either

(11)
$\displaystyle\sum_{k=1}^{\infty}w_{n_{k}+1}=\infty\qquad\text{or}\qquad\mathop{\rm
lim\,inf}\limits_{k\rightarrow\infty}\,\,\left|\textup{tr}\left(\nabla
f(\boldsymbol{\theta}_{n_{k}+1})^{T}\frac{\boldsymbol{\theta}_{n_{k}}-\boldsymbol{\theta}_{n_{k}+1}}{\lVert\boldsymbol{\theta}_{n_{k}}-\boldsymbol{\theta}_{n_{k}+1}\rVert_{F}}\right)\right|=0.$

There exists a further subsequence $(s_{k})_{k\geq 1}$ of $(t_{k})_{k\geq 1}$
such that
$\boldsymbol{\theta}_{\infty}:=\lim_{k\rightarrow\infty}\boldsymbol{\theta}_{s_{k}}$
exists and is a stationary point of $\Lambda$.

###### Proof.

By Proposition 2.3, we have

(12) $\displaystyle\sum_{k=1}^{\infty}w_{n_{k}+1}\left|\textup{tr}\left(\nabla
f(\boldsymbol{\theta}_{n_{k}+1})^{T}\frac{\boldsymbol{\theta}_{n_{k}}-\boldsymbol{\theta}_{n_{k}+1}}{\lVert\boldsymbol{\theta}_{n_{k}}-\boldsymbol{\theta}_{n_{k}+1}\rVert_{F}}\right)\right|<\infty.$

Hence if $\sum_{k=1}^{\infty}w_{n_{k}+1}=\infty$, then the latter condition in
(11) holds. Thus it suffices to show that this latter condition implies the
assertion. Assume this condition, and let $(s_{k})_{k\geq 1}$ be a subsequence
of $(t_{k})_{k\geq 1}$ for which the liminf in (11) is achieved. By taking a
subsequence, we may assume that
$\boldsymbol{\theta}_{\infty}^{\prime}=\lim_{k\rightarrow\infty}\boldsymbol{\theta}_{s_{k}}$
exists.

Now suppose for contradiction that $\boldsymbol{\theta}_{\infty}$ is not a
stationary point of $f$ over $\boldsymbol{\Theta}$. Then there exists
$\boldsymbol{\theta}^{\star}\in\boldsymbol{\Theta}$ and $\delta>0$ such that

(13) $\displaystyle\textup{tr}\left(\nabla
f(\boldsymbol{\theta}_{\infty})^{T}(\boldsymbol{\theta}^{\star}-\boldsymbol{\theta}_{\infty})\right)<-\delta<0.$

By triangle inequality, write

(14) $\displaystyle\lVert\nabla
f(\boldsymbol{\theta}_{s_{k}})^{T}(\boldsymbol{\theta}^{\star}-\boldsymbol{\theta}_{s_{k}})-\nabla
f(\boldsymbol{\theta}_{\infty})^{T}(\boldsymbol{\theta}^{\star}-\boldsymbol{\theta}_{\infty})\rVert_{F}$
(15) $\displaystyle\qquad\leq\lVert\nabla
f(\boldsymbol{\theta}_{s_{k}})-\nabla
f(\boldsymbol{\theta}_{\infty})\rVert_{F}\cdot\lVert\boldsymbol{\theta}^{\star}-\boldsymbol{\theta}_{s_{k}}\rVert_{F}+\lVert\nabla
f(\boldsymbol{\theta}_{\infty})\rVert_{F}\cdot\lVert\boldsymbol{\theta}_{\infty}-\boldsymbol{\theta}_{s_{k}}\rVert_{F}.$

Noting that
$\lVert\boldsymbol{\theta}_{n}-\boldsymbol{\theta}_{n-1}\rVert_{F}=O(w_{n})=o(1)$,
we see that the right hand side goes to zero as $k\rightarrow\infty$. Hence
for all sufficiently large $k\geq 1$, we have

(16) $\displaystyle\textup{tr}\left(\nabla
f(\boldsymbol{\theta}_{s_{k}})^{T}(\boldsymbol{\theta}^{\star}-\boldsymbol{\theta}_{s_{k}})\right)<-\delta/2.$

Then by Proposition 2.4, denoting
$\lVert\boldsymbol{\Theta}\rVert_{F}:=\sup_{\boldsymbol{\theta},\boldsymbol{\theta}^{\prime}\in\boldsymbol{\Theta}}\lVert\boldsymbol{\theta}-\boldsymbol{\theta}^{\prime}\rVert_{F}<\infty$,

(17) $\displaystyle\mathop{\rm
lim\,inf}\limits_{k\rightarrow\infty}\,\,\textup{tr}\left(\nabla
f(\boldsymbol{\theta}_{s_{k}+1})^{T}\frac{\boldsymbol{\theta}_{s_{k}}-\boldsymbol{\theta}_{s_{k}+1}}{\lVert\boldsymbol{\theta}_{s_{k}}-\boldsymbol{\theta}_{s_{k}+1}\rVert_{F}}\right)\leq-\frac{\delta}{2\lVert\boldsymbol{\Theta}\rVert_{F}}<0,$

which contradicts the choice of the subsequence
$(\boldsymbol{\theta}_{s_{k}})_{k\geq 1}$. This shows the assertion. ∎

We will denote by $(\boldsymbol{\theta}_{n})_{n\geq 1}$ the output of
Algorithm 1 and $\Lambda:=\\{\boldsymbol{\theta}_{n}\,|\,t\geq
1\\}\subseteq\boldsymbol{\Theta}$. Recall that during the update
$\boldsymbol{\theta}_{n-1}\mapsto\boldsymbol{\theta}_{n}$ each block
coordinate of $\boldsymbol{\theta}_{n-1}$ changes by at most $c^{\prime}w_{n}$
in Frobenius norm. For each $n\geq 1$, we say $\boldsymbol{\theta}_{n}$ is a
long point if none of the block coordinates of $\boldsymbol{\theta}_{n-1}$
change by $c^{\prime}w_{n}$ in Frobenius norm and a short point otherwise.
Observe that if $\boldsymbol{\theta}_{n}$ is a long point, then imposing the
search radius restriction in (3) has no effect and $\boldsymbol{\theta}_{n}$
is obtained from $\boldsymbol{\theta}_{n-1}$ by a single cycle of block
coordinate descent on $f$ over $\boldsymbol{\Theta}$.

######  Proposition 2.6 (Sufficient condition for stationarity II).

Assume (A1) and (A2). If $(\boldsymbol{\theta}_{n_{k}})_{k\geq 1}$ is a
convergent subsequence of $(\boldsymbol{\theta}_{n})_{n\geq 1}$ consisting of
long points, then the
$\boldsymbol{\theta}_{\infty}=\lim_{k\rightarrow\infty}\boldsymbol{\theta}_{s_{k}}$
is stationary.

###### Proof.

The argument is similar to that of [4, Prop. 2.7.1]. However, here we do not
need to assume uniqueness of solutions to minimization problems of $f$ in each
block coordinate due to the added search radius restriction. Namely, write
$\boldsymbol{\theta}_{\infty}=[\theta_{\infty}^{(1)},\dots,\theta_{\infty}^{(m)}]$.
Then for each $k\geq 1$,

(18) $\displaystyle
f(\theta_{t_{k}}^{(1)},\theta_{t_{k}-1}^{(2)},\dots,\theta_{t_{k}-1}^{(m)})\leq
f(\theta^{(1)},\theta_{t_{k}-1}^{(2)},\dots,\theta_{t_{k}-1}^{(m)})$

for all
$\theta^{(1)}\in\Theta^{(1)}\cap\\{\theta\colon\lVert\theta-\theta_{t_{k}-1}^{(1)}\rVert_{F}\leq
c^{\prime}w_{n_{k}}\\}$. In fact, since $\boldsymbol{\theta}_{n_{k}}$ is a
long point by the assumption, (18) holds for all $\theta_{1}\in\Theta_{1}$.
Taking $k\rightarrow\infty$ and using the fact that
$\lVert\theta_{t_{k}}^{(1)}-\theta_{t_{k}-1}^{(1)}\rVert_{F}\leq
c^{\prime}w_{t_{k}}$,

(19) $\displaystyle
f(\theta_{\infty}^{(1)},\theta_{\infty}^{(2)},\dots,\theta_{\infty}^{(m)})\leq
f(\theta^{(1)},\theta_{\infty}^{(2)},\dots,\theta_{\infty}^{(m)})\quad\text{for
all $\theta^{(1)}\in\Theta^{(1)}$}.$

Since $\Theta^{(1)}$ is convex, it follows that

(20)
$\displaystyle\nabla_{1}f(\boldsymbol{\theta}_{\infty})^{T}(\theta^{(1)}-\theta_{\infty}^{(1)})\geq
0\quad\quad\text{for all $\theta^{(1)}\in\Theta^{(1)}$}.$

By using a similar argument for other coordinates of
$\boldsymbol{\theta}_{\infty}$, it follows that $\nabla
f(\boldsymbol{\theta}_{\infty})^{T}(\boldsymbol{\theta}-\boldsymbol{\theta}_{\infty})\geq
0$ for all $\boldsymbol{\theta}\in\boldsymbol{\Theta}$. This shows the
assertion. ∎

######  Proposition 2.7 (Local structure of a non-stationary limit point).

Assume (A1), (A2), $\sum_{n=1}^{\infty}w_{n}=\infty$, and
$\sum_{n=1}^{\infty}w_{n}^{2}<\infty$. Suppose there exists a non-stationary
limit point $\boldsymbol{\theta}_{\infty}$ of $\Lambda$. Then there exists
$\varepsilon>0$ such that the $\varepsilon$-neighborhood
$B_{\varepsilon}(\boldsymbol{\theta}_{\infty}):=\\{\boldsymbol{\theta}\in\boldsymbol{\Theta}\,|\,\lVert\boldsymbol{\theta}-\boldsymbol{\theta}_{\infty}\rVert_{F}<\varepsilon\\}$
with the following properties:

(a)

$B_{\varepsilon}(\boldsymbol{\theta}_{\infty})$ does not contain any
stationary points of $\Lambda$.

(b)

There exists infinitely many $\boldsymbol{\theta}_{n}$’s outside of
$B_{\varepsilon}(\boldsymbol{\theta}_{\infty})$.

###### Proof.

We will first show that there exists an $\varepsilon$-neighborhood
$B_{\varepsilon}(\boldsymbol{\theta}_{\infty})$ of
$\boldsymbol{\theta}_{\infty}$ that does not contain any long points of
$\Lambda$. Suppose for contradiction that for each $\varepsilon>0$, there
exists a long point $\Lambda$ in
$B_{\varepsilon}(\boldsymbol{\theta}_{\infty})$. Then one can construct a
sequence of long points converging to $\boldsymbol{\theta}_{\infty}$. But then
by Proposition 2.6, $\boldsymbol{\theta}_{\infty}$ is a stationary point, a
contradiction.

Next, we show that there exists $\varepsilon>0$ such that
$B_{\varepsilon}(\boldsymbol{\theta}_{\infty})$ satisfies (a). Suppose for
contradiction that there exists no such $\varepsilon>0$. Then we have a
sequence $(\boldsymbol{\theta}_{\infty;k})_{k\geq 1}$ of stationary points of
$\Lambda$ that converges to $\boldsymbol{\theta}_{\infty}$. Fix
$\boldsymbol{\theta}\in\boldsymbol{\Theta}$ and note that by Cauchy-Schwarz
inequality,

(21) $\displaystyle\nabla
f(\boldsymbol{\theta}_{\infty})^{T}(\boldsymbol{\theta}-\boldsymbol{\theta}_{\infty})$
$\displaystyle\geq-\lVert\nabla f(\boldsymbol{\theta}_{\infty})-\nabla
f(\boldsymbol{\theta}_{\infty;k})\rVert_{F}\cdot\lVert\boldsymbol{\theta}-\boldsymbol{\theta}_{\infty}\rVert_{F}$
(22) $\displaystyle\qquad-\lVert\nabla
f(\boldsymbol{\theta}_{\infty;k})\rVert_{F}\cdot\lVert\boldsymbol{\theta}_{\infty}-\boldsymbol{\theta}_{\infty;k}\rVert_{F}+\nabla
f(\boldsymbol{\theta}_{\infty;k})^{T}(\boldsymbol{\theta}-\boldsymbol{\theta}_{\infty;k}).$

Note that $\nabla f$ is Lipschitz and $\nabla
f_{\infty;k}(\boldsymbol{\theta}_{\infty;k})^{T}(\boldsymbol{\theta}-\boldsymbol{\theta}_{\infty;k})\geq
0$ since $\boldsymbol{\theta}_{\infty;k}$ is a stationary point of
$f_{\infty;k}$ over $\boldsymbol{\Theta}$. Hence by taking
$k\rightarrow\infty$, this shows $\nabla
f(\boldsymbol{\theta}_{\infty})^{T}(\boldsymbol{\theta}-\boldsymbol{\theta}_{\infty})\geq
0$. Since $\boldsymbol{\theta}\in\boldsymbol{\theta}^{\textup{dict}}$ was
arbitrary, this shows that $\boldsymbol{\theta}_{\infty}$ is a stationary
point of $f$ over $\boldsymbol{\Theta}$, a contradiction.

Lastly, from the earlier results, we can choose $\varepsilon>0$ such that
$B_{\varepsilon}(\boldsymbol{\theta}_{\infty})$ has no long points of
$\Lambda$ and also satisfies (b). We will show that
$B_{\varepsilon/2}(\boldsymbol{\theta}_{\infty})$ satisfies (c). Then
$B_{\varepsilon/2}(\boldsymbol{\theta}_{\infty})$ satisfies (a)-(b), as
desired. Suppose for contradiction there are only finitely many
$\boldsymbol{\theta}_{n}$’s outside of
$B_{\varepsilon/2}(\boldsymbol{\theta}_{\infty})$. Then there exists an
integer $M\geq 1$ such that $\boldsymbol{\theta}_{n}\in
B_{\varepsilon/2}(\boldsymbol{\theta}_{\infty})$ for all $t\geq M$. Then each
$\boldsymbol{\theta}_{n}$ for $t\geq M$ is a short point of $\Lambda$. By
definition, it follows that
$\lVert\boldsymbol{\theta}_{n-1}-\boldsymbol{\theta}\lVert_{F}\geq
c^{\prime}w_{n}$ for all $t\geq M$. Then by Proposition 2.3, we have

(23) $\displaystyle\sum_{n\geq M}w_{n+1}\left|\textup{tr}\left(\nabla
f(\boldsymbol{\theta}_{n+1})^{T}\frac{\boldsymbol{\theta}_{n}-\boldsymbol{\theta}_{n+1}}{\lVert\boldsymbol{\theta}_{n}-\boldsymbol{\theta}_{n+1}\rVert_{F}}\right)\right|<\infty.$

Since $\sum_{n=1}^{\infty}w_{n}=\infty$, there exists a subsequence
$(s_{k})_{k\geq 1}$ such that
$\boldsymbol{\theta}_{\infty}^{\prime}:=\lim_{k\rightarrow\infty}\boldsymbol{\theta}_{n_{k}}$
exists and is stationary. But since $\boldsymbol{\theta}^{\prime}_{\infty}\in
B_{\varepsilon}(\boldsymbol{\theta})$, this contradicts (a) for
$B_{\varepsilon}(\boldsymbol{\theta})$. This shows the assertion. ∎

We are now ready to give a proof of Theorem 1.1.

###### Proof of Theorem 1.1.

Assume (A1), (A2), $\sum_{n=1}^{\infty}w_{n}=\infty$, and
$\sum_{n=1}^{\infty}w_{n}^{2}<\infty$. Suppose there exists a non-stationary
limit point $\boldsymbol{\theta}_{\infty}\in\boldsymbol{\Theta}$ of $\Lambda$.
By Proposition 2.7, we may choose $\varepsilon>0$ such that
$B_{\varepsilon}(\boldsymbol{\theta}_{\infty})$ satisfies the conditions
(a)-(b) of Proposition 2.7. Choose $M\geq 1$ large enough so that
$w_{n}<\varepsilon/4$ whenever $t\geq M$. We call an integer interval
$I:=[\ell,\ell^{\prime}]$ a crossing if $\boldsymbol{\theta}_{\ell}\in
B_{\varepsilon/3}(\boldsymbol{\theta}_{\infty})$,
$\boldsymbol{\theta}_{\ell^{\prime}}\in
B_{2\varepsilon/3}(\boldsymbol{\theta}_{\infty})$, and no proper subset of $I$
satisfies both of these conditions. By definition, two distinct crossings have
empty intersection. Fix a crossing $I=[\ell,\ell^{\prime}]$, it follows that
by triangle inequality,

(24) $\displaystyle
c^{\prime}\sqrt{m}\sum_{n=\ell}^{\ell^{\prime}-1}w_{n+1}\geq\sum_{n=\ell}^{\ell^{\prime}-1}\lVert\boldsymbol{\theta}_{n+1}-\boldsymbol{\theta}_{n}\rVert_{F}\geq\lVert\boldsymbol{\theta}_{\ell^{\prime}}-\boldsymbol{\theta}_{\ell}\rVert_{F}\geq\varepsilon/3.$

Note that since $\boldsymbol{\theta}_{\infty}$ is a limit point of $\Lambda$,
$\boldsymbol{\theta}_{n}$ visits
$B_{\varepsilon/3}(\boldsymbol{\theta}_{\infty})$ infinitely often. Moreover,
by condition (a) of Proposition 2.7, $\boldsymbol{\theta}_{n}$ also exits
$B_{\varepsilon}(\boldsymbol{\theta}_{\infty})$ infinitely often. It follows
that there are infinitely many crossings. Let $t_{k}$ denote the
$k^{\textup{th}}$ smallest integer that appears in some crossing. Then
$t_{k}\rightarrow\infty$ as $k\rightarrow\infty$, and by (24) (recall that $n$
denotes the number of modes in tensors and is fixed),

(25) $\displaystyle\sum_{k=1}^{\infty}w_{n_{k}+1}\geq(\text{$\\#$ of
crossings})\,\frac{c^{\prime}\varepsilon}{3\sqrt{m}}=\infty.$

Then by Proposition 2.5, there exists a further subsequence $(s_{k})_{k\geq
1}$ of $(t_{k})_{k\geq 1}$ such that
$\boldsymbol{\theta}_{\infty}^{\prime}:=\lim_{k\rightarrow\infty}\boldsymbol{\theta}_{s_{k}}$
exists and is a stationary of $f$ over $\boldsymbol{\Theta}$. However, since
$\boldsymbol{\theta}_{n_{k}}\in
B_{2\varepsilon/3}(\boldsymbol{\theta}_{\infty})$, we have
$\boldsymbol{\theta}_{\infty}^{\prime}\in
B_{\varepsilon}(\boldsymbol{\theta}_{\infty})$. This contradicts condition (b)
of Proposition 2.7 for $B_{\varepsilon}(\boldsymbol{\theta}_{\infty})$ that it
cannot contain any stationary point of $f$ over $\boldsymbol{\Theta}$. This
shows the assertion. ∎

##  3\. Applications to Nonnegative Matrix and Tensor Factorization

In this section, we discuss applications of our main result in the setting of
nonnegative matrix and tensor factorization problems [14, 15, 11].

Figure 1. Illustration of NMF (top) and NTF (bottom). $m$-mode tensors are
observed $n$ times. One seeks $m$ loading matrices as well as a code matrix
that give approximate decomposition of all data.

Given a $d\times T$ data matrix $X\in\mathbb{R}^{d\times T}_{\geq 0}$ and an
integer parameter $r\geq 1$, a simple instance nonnegative matrix
factorization (NMF) is the following two-block optimization problem

(26) $\displaystyle\hskip
42.67912pt\operatorname*{arg\,min}_{W\in\mathbb{R}^{d\times r}_{\geq
0},\,H\in\mathbb{R}^{r\times T}_{\geq 0}}\lVert X-WH\lVert_{F}^{2}.$

Here, the two factors $W$ and $H$ are called dictionary and code matrices of
$X$, respectively. The interpretation of this approximate factorization is
that the $r$ columns of $W$ give an approximate basis for spanning the $n$
columns of $X$, where the columns of $H$ give suitable linear coefficients for
each approximation.

More generally, we can formulate a similar factorization problem in a tensor
setting. An $m$-mode tensor $\mathbf{X}$ of shape $d_{1}\times\dots\times
d_{m}$ is a map
$(i_{1},\dots,i_{m})\mapsto\mathbf{X}(i_{1},\dots,i_{m})\in\mathbb{R}$ from
the multi-index set $\\{1,\dots,d_{1}\\}\times\dots\times\\{1,\dots,d_{m}\\}$
into the real line $\mathbb{R}$. Suppose we have $T$ observed $m$-mode tensor-
valued signals wrapped as a single $(m+1)$-mode tensor
$[\mathbf{X}_{1},\dots,\mathbf{X}_{T}]\in\mathbb{R}_{\geq
0}^{d_{1}\times\dots\times d_{m}\times T}$. Consider the following the
nonnegative tensor factorization (NTF) problem:

(27) $\displaystyle\operatorname*{arg\,min}_{U^{(1)}\in\mathbb{R}^{d_{1}\times
r}_{\geq 0},\dots,U^{(m)}\in\mathbb{R}_{\geq 0}^{d_{m}\times
r},\,H\in\mathbb{R}_{\geq 0}^{r\times
T}}\left\lVert[\mathbf{X}_{1},\dots,\mathbf{X}_{T}]-\operatorname{\texttt{Out}}(U^{(1)},\dots,U^{(m)})\times_{m+1}H\right\rVert_{F}^{2},$

where $\times_{m+1}$ denotes the mode $(n+1)$-product [11] and we define the
outer product of loading matrices $U^{(i)}\in\mathbb{R}^{d_{i}\times r}_{\geq
0}$ as

(28)
$\displaystyle\operatorname{\texttt{Out}}(U^{(1)},\dots,U^{(m)}):=\left[\bigotimes_{k=1}^{m}U^{(k)}(:,1),\,\bigotimes_{k=1}^{m}U^{(k)}(:,2),\,\dots\,,\bigotimes_{k=1}^{m}U^{(k)}(:,R)\right]\in\mathbb{R}_{\geq
0}^{d_{1}\times\dots\times d_{m}\times r}.$

Here $U_{k}(:,j)$ denotes the $j^{\textup{th}}$ column of the $d_{k}\times r$
loading matrix matrix $U_{k}$ and $\otimes$ denotes the outer product. The $r$
rank-1 tensors in $\operatorname{\texttt{Out}}(U^{(1)},\dots,U^{(m)})$ are
called dictionary atoms for $\mathbf{X}_{1},\dots,\mathbf{X}_{T}$. When we
have a single observed tensor ($T=1$), by absorbing the coordinates of $H$
into the loading matrices, (27) reduces to the nonnegative CANDECOMP/PARAFAC
(CP) decomposition problem [24, 29]

(29)
$\displaystyle\mathbf{X}\approx\sum\operatorname{\texttt{Out}}(U^{(1)},\dots,U^{(m)}):=\sum_{i=1}^{R}\bigotimes_{k=1}^{m}U_{k}(:,i),$

Also, if $n=1$ so that $\mathbf{X}_{j}$ are vector-valued signals, then it
reduces to the NMF problem in (26).

NMF has found applications in text analysis, image reconstruction, medical
imaging, bioinformatics, and many other scientific fields more generally [23,
2, 3, 8, 27, 6, 21]. As matrix factorization is for unimodal data, NTF
provides a powerful and versatile tool that can extract useful latent
information out of multi-model data tensors. As a result, tensor factorization
methods have witnessed increasing popularity and adoption in modern data
science [24, 29, 31, 25, 20]. The use of nonnegativity constraint in both NMF
and NTF is crucial in obtaining “parts-based" representation of the input
signals [14].

BCD is a popular approach for both NMF and NTF problems [12]. Namely, when we
apply BCD (2) for (27), each block update is a quadratic problem under
nonnegativity (convex) constraint. Hence in this case BCD takes the form of
alternating least squares (ALS) for minimizing Frobenius reconstruction error
as in (26) and (27). For NMF, ALS (or vanila BCD in (2)) is known to converge
to stationary points [10]. On the other hand, for NTF with $m\geq 2$ modes,
global convergence to stationary points of ALS is not guaranteed in general
[11]. As a corollary of our main result (Theorem 1.1), we show that ALS with
diminishing radius always converge to the stationary points of the objective
function in (27). The following result follows immediately from Theorem 1.1 by
noting that the objective function of NTF in (27) is convex in each block.

######  Corollary 3.1.

Let $\boldsymbol{\theta}_{n}:=[U^{(1)}_{n},\dots,U^{(m)}_{n},H_{n}]$, $n\geq
0$ denote the output of Algorithm 1 applied to the NTF problem (27). Further
assume that the factors $U^{(i)}_{n}$ for $i=1,\dots,n$ and $H_{n}$ are
confined in compact and convex subsets. Suppose
$\sum_{n=1}^{\infty}w_{n}=\infty$ and $\sum_{n=1}w_{n}^{2}<\infty$. Then
$\boldsymbol{\theta}_{n}$ converges to the stationary points of the objective
function in (27) for every data tensors $\mathbf{X}_{1},\dots,\mathbf{X}_{T}$
and initial estimate $\boldsymbol{\theta}_{0}$.

Note that the additional assumption of compact constraints on the loading
matrices does not lose generality since a they can always be normalized and
the scalar could be absorbed into the code matrix $H$. If we also assume that
the norms of the loading matrices are bounded away from zero, then
nonnegativity constraint implies that the norm of $H$ is also bounded. Hence
compact constraint on the code matrix is also reasonable.

We also remark that in a recent joint work with Strohmeier and Needell [26],
we have developed an algorithm for an online version of NTF and convergence
analysis under mild assumptions. The analysis we provide in this work also
plays an important role in the reference.

##  4\. Experimental Validation

In this section, we compare the performance of our proposed BCD-DR algorithm
(Algorithm 1) for the task of NTF (27) against two most popular algorithms of
Alternating Least Squares (ALS) and Multiplicative Update (MU) (see [24]). We
recall that our algorithm for NTF reduces to the standard ALS with additional
diminishing radius condition as in (3). In particular, we recover the standard
ALS from our method by setting $c^{\prime}w_{t}=\infty$ for $t\geq 1$. We
consider one synthetic and one real-world tensor data as follows:

  1. (1)

$\mathbf{X}_{\text{synth}}\in\mathbb{R}_{\geq 0}^{100\times 200\times 300}$ is
generated by $\operatorname{\texttt{Out}}(V_{1},V_{2},V_{3})$, where the
loading matrices $V_{1}\in\mathbb{R}_{\geq 0}^{100\times 5}$,
$V_{1}\in\mathbb{R}_{\geq 0}^{200\times 5}$, and $V_{1}\in\mathbb{R}_{\geq
0}^{300\times 5}$ are generated by sampling each of their entries uniformly
and independently from the unit interval $[0,1]$.

  2. (2)

$\mathbf{X}_{\textup{Twitter}}\in\mathbb{R}_{\geq 0}^{90\times 5000\times
1000}$ is the anonymized Twitter text data related to the COVID-19 pandemic
from Feb. 1 to May 1 of 2020, which is recently obtained and analyzed in [13].
The three modes correspond to days, words, and tweets, in order. In each day,
the top 1000 most retweeted English tweets are collected and encoded as a
5000-dimensional tf-idf vector [22]. The entries of
$\mathbf{X}_{\textup{Twitter}}$ have small mean 1absolute value of $0.00067$.

Figure 2.  Comparison of the performance of BCD-DR (Algorithm 1) for the
nonnegative tensor factorization problem against Alternating Least Squares
(ALS) and Multiplicative Update (MU). BCD-DR-$\beta$ for $\beta=0.5,\,1$
denotes our method with diminishing radius $c^{\prime}w_{t}$ where
$c^{\prime}=10^{5}$ and $n^{-\beta}/\log n$. For the synthetic and Twitter
tensor data of shape $(100,200,300)$ and $(90,5000,1000)$, respectively, we
apply each algorithm ten times to find nonnegative loading matrices
$U_{1},U_{2},U_{3}$ of $R=5$ columns. The average reconstruction error with 1
standard deviation are shown by the solid lines and shaded regions of
respective colors.

For both datasets, we used all three algorithms to learn three loading
matrices $U_{1},U_{2},U_{3}$ with $R=5$ columns, that evolves in time as the
algorithm proceeds. We plot the reconstruction error
$\lVert[X]-\operatorname{\texttt{Out}}(U_{1},U_{2},U_{3})\rVert_{F}$ against
elapsed time (CPU time) in both cases in Figure 2. Each algorithm is used 10
times for the same data, and the plot shows the average reconstruction errors
together with their standard deviation in shades. In Figure 2, BCD-DR-$\beta$
denotes Algorithm 1 with weights $w_{n}=n^{-\beta}/\log n$ for
$\beta=0.5,\,1$. The search radius constant $c^{\prime}$ is chosen to be
$10^{5}$ for all cases. In all cases, the weights are non-summable but are
square-summable, so the algorithm is guaranteed to converge to the stationary
points of the ojective function of (27) by Corollary 3.1. For both experiments
in Figure 2, we see that the additional radius restriction in fact improves
the convergence speed over the standard ALS. For the synthetic data,
${\textup{ALS}\\_}\textup{DR}$-$\beta$ shows a better performance than MU; For
the Twitter data, it appears that MU initializes better than the three ALS-
based methods but the latter ones improve at a faster rate.

## Acknowledgements

This work is partially supported by NSF DMS-2010035.

## References

  * Aus [92] A Auslender, _Asymptotic properties of the fenchel dual functional and applications to decomposition problems_ , Journal of optimization theory and applications 73 (1992), no. 3, 427–449.
  * BB [05] Michael W Berry and Murray Browne, _Email surveillance using non-negative matrix factorization_ , Computational & Mathematical Organization Theory 11 (2005), no. 3, 249–264.
  * BBL+ [07] Michael W Berry, Murray Browne, Amy N Langville, V Paul Pauca, and Robert J Plemmons, _Algorithms and applications for approximate nonnegative matrix factorization_ , Computational statistics & data analysis 52 (2007), no. 1, 155–173.
  * Ber [97] Dimitri P Bertsekas, _Nonlinear programming_ , Journal of the Operational Research Society 48 (1997), no. 3, 334–334.
  * Ber [99] by same author, _Nonlinear programming_ , Athena scientific Belmont, 1999.
  * BMB+ [15] Rostyslav Boutchko, Debasis Mitra, Suzanne L Baker, William J Jagust, and Grant T Gullberg, _Clustering-initiated factor analysis application for tissue classification in dynamic brain positron emission tomography_ , Journal of Cerebral Blood Flow & Metabolism 35 (2015), no. 7, 1104–1111.
  * BT [89] Dimitri P Bertsekas and John N Tsitsiklis, _Parallel and distributed computation: numerical methods_ , vol. 23, Prentice hall Englewood Cliffs, NJ, 1989\.
  * CWS+ [11] Yang Chen, Xiao Wang, Cong Shi, Eng Keong Lua, Xiaoming Fu, Beixing Deng, and Xing Li, _Phoenix: A weight-based network coordinate system using matrix factorization_ , IEEE Transactions on Network and Service Management 8 (2011), no. 4, 334–347.
  * GS [99] Luigi Grippof and Marco Sciandrone, _Globally convergent block-coordinate techniques for unconstrained optimization_ , Optimization methods and software 10 (1999), no. 4, 587–637.
  * GS [00] Luigi Grippo and Marco Sciandrone, _On the convergence of the block nonlinear gauss–seidel method under convex constraints_ , Operations research letters 26 (2000), no. 3, 127–136.
  * KB [09] Tamara G Kolda and Brett W Bader, _Tensor decompositions and applications_ , SIAM review 51 (2009), no. 3, 455–500.
  * KHP [14] Jingu Kim, Yunlong He, and Haesun Park, _Algorithms for nonnegative matrix and tensor factorizations: A unified view based on block coordinate descent framework_ , Journal of Global Optimization 58 (2014), no. 2, 285–319.
  * KKL+ [20] Lara Kassab, Alona Kryshchenk, Lyu, Denali Molitor, Deanna Needell, and Elizaveta Rebrova, _On nonnegative ma trix and tensor decompositions for covid-19 twitter dynamics_ , arXiv prepreint arXiv:2010.01600 (2020).
  * LS [99] Daniel D Lee and H Sebastian Seung, _Learning the parts of objects by non-negative matrix factorization_ , Nature 401 (1999), no. 6755, 788\.
  * LS [01] by same author, _Algorithms for non-negative matrix factorization_ , Advances in neural information processing systems, 2001, pp. 556–562.
  * LT [92] Zhi-Quan Luo and Paul Tseng, _On the convergence of the coordinate descent method for convex differentiable minimization_ , Journal of Optimization Theory and Applications 72 (1992), no. 1, 7–35.
  * Nes [98] Yurii Nesterov, _Introductory lectures on convex programming volume i: Basic course_ , Lecture notes 3 (1998), no. 4, 5.
  * Pat [98] Michael Patriksson, _Decomposition methods for differentiable optimization problems over cartesian product sets_ , Computational optimization and applications 9 (1998), no. 1, 5–42.
  * Pow [73] Michael JD Powell, _On search directions for minimization algorithms_ , Mathematical programming 4 (1973), no. 1, 193–201.
  * RLH [20] Sirisha Rambhatla, Xingguo Li, and Jarvis Haupt, _Provable online cp/parafac decomposition of a structured tensor via dictionary learning_ , Advances in Neural Information Processing Systems 33 (2020).
  * RPZ+ [18] Bin Ren, Laurent Pueyo, Guangtun Ben Zhu, John Debes, and Gaspard Duchêne, _Non-negative matrix factorization: robust extraction of extended structures_ , The Astrophysical Journal 852 (2018), no. 2, 104.
  * RU [11] Anand Rajaraman and Jeffrey David Ullman, _Mining of massive datasets_ , Cambridge University Press, 2011.
  * SGH [02] Arkadiusz Sitek, Grant T Gullberg, and Ronald H Huesman, _Correction for ambiguous solutions in factor analysis using a penalized least squares objective_ , IEEE transactions on medical imaging 21 (2002), no. 3, 216–225.
  * SH [05] Amnon Shashua and Tamir Hazan, _Non-negative tensor factorization with applications to statistics and computer vision_ , Proceedings of the 22nd international conference on Machine learning, ACM, 2005, pp. 792–799.
  * SLLC [17] Will Wei Sun, Junwei Lu, Han Liu, and Guang Cheng, _Provable sparse tensor decomposition_ , Journal of the Royal Statistical Society: Series B (Statistical Methodology) 3 (2017), no. 79, 899–916.
  * SLN [20] Christopher Strohmeier, Hanbaek Lyu, and Deanna Needell, _Online nonnegative tensor factorization and cp-dictionary learning for markovian data_ , arXiv preprint arXiv:2009.07612 (2020).
  * TN [12] Leo Taslaman and Björn Nilsson, _A framework for regularized non-negative matrix factorization, with application to the analysis of gene expression data_ , PloS one 7 (2012), no. 11, e46331.
  * Tse [91] Paul Tseng, _Decomposition algorithm for convex differentiable minimization_ , Journal of Optimization Theory and Applications 70 (1991), no. 1, 109–135.
  * Zaf [09] Stefanos Zafeiriou, _Algorithms for nonnegative tensor factorization_ , Tensors in Image Processing and Computer Vision, Springer, 2009, pp. 105–124.
  * Zan [69] Willard I Zangwill, _Nonlinear programming: a unified approach_ , vol. 52, Prentice-hall Englewood Cliffs, NJ, 1969.
  * ZVB+ [16] Shuo Zhou, Nguyen Xuan Vinh, James Bailey, Yunzhe Jia, and Ian Davidson, _Accelerating online cp decompositions for higher order tensors_ , Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pp. 1375–1384.


# A quick sneak-peek at the $s$-fractional Laplacian operator

Debajyoti Choudhuria,
aDepartment of Mathematics, National Institute of Technology Rourkela,
Rourkela - 769008, Odisha, India.
Email<EMAIL_ADDRESS>a

(August 28, 2024)

###### Abstract

The short note here is to give a few heuristic arguments on the weird looking
fractional Laplacian operator. This is certainly going to expand the vision of
a reader who is looking to develope a taste for research in this direction.

Keywords: Fractional Laplacian, Laplacian

Math. Subject Classification.: 35R35, 35Q35, 35J20, 46E35.

##  1 Introduction

Fractional Laplacian is a fast emerging area of research in many areas of
science, mathematics being a major contributor to it owing to the rich
theoretical aspects it gives rise to. We will discuss about an application of
these operators in atom dislocation in crystals. One essential reading for
this operator is due to Valdinoci et al [2]. This short article has been
written with minimal details so that the surprising aspects of the
$s$-Laplacian operator can be appreciated by the reader(s) without delving
into the rigours of the proofs. With my own experience, it is always important
for the readers to have a heuristic argument for a better insight for one’s
understanding.

##  2 Definition

Following is the definition of the fractional Laplacian:

$\displaystyle\begin{split}(-\Delta)^{s}u(x)&:=C_{N,s}\int_{\mathbb{R}^{N}}\frac{u(x)-u(y)}{|x-y|^{N+2s}}dy.\end{split}$
(2.1)

Here, $0<s<1$, $N\geq 1$. The integral, although is singular in nature, is
computed in the principle value sense as follows:

$\displaystyle\begin{split}(-\Delta)^{s}u(x)&:=\underset{\epsilon\searrow
0}{\lim}\int_{\mathbb{R}^{N}\setminus
B_{\epsilon}(x)}\frac{u(x)-u(y)}{|x-y|^{N+2s}}dy.\end{split}$ (2.2)

The constant $C_{N,s}$ in (2.1) is equal to

$C_{N,s}=\frac{4^{s}\Gamma(\frac{N}{2}+s)}{\pi^{N/2}\Gamma(1-s)}.$

###  2.1 A nice application of $(-\Delta)^{s}$

This subsection will introduce the readers to an application of the operator
in (2.1). Consider a lattice of atoms as in the Figure $1$.

Figure 1: The curve below is the ‘well of energy’

We ignore the vertical component of the movement of the atoms. The atoms are
distributed in $\mathbb{Z}\times\mathbb{Z}_{+}$. We denote $V(x,y)$ to be the
displacement of the atom in the horrizontal direction. The total energy of the
system is then given by

$\displaystyle\mathcal{E}(V)$
$\displaystyle=\frac{1}{2}\int_{\mathbb{R}_{+}^{2}}|\nabla
V|^{2}dxdy+\int_{\mathbb{R}}W(v(y))dy.$ (2.3)

Here $\mathbb{R}_{+}^{2}=\mathbb{R}\times(0,\infty)$ and $V(0,y)=v(y)$. Since
$\mathcal{E}$ is a $C^{1}$ functional, therefore, the Fréchet derivative of
$\mathcal{E}$ is as follows:

$\displaystyle\langle\mathcal{E}^{\prime}(V),\phi\rangle$
$\displaystyle=\int_{\mathbb{R}_{+}^{2}}\nabla V\cdot\nabla\Phi
dxdy+\int_{\mathbb{R}}W^{\prime}(v(x))\phi(x)dy\leavevmode\nobreak\ \text{for
every}\leavevmode\nobreak\ \Phi\in H^{1,2}(\mathbb{R}_{+}^{2}).$ (2.4)

Here $\Phi(0,y)=\phi(y)$. On choosing $\Phi(0,y)=0$, we get

$\displaystyle 0$ $\displaystyle=\int_{\mathbb{R}_{+}^{2}}\nabla
V\cdot\nabla\Phi dxdy\leavevmode\nobreak\ \text{for every}\leavevmode\nobreak\
\Phi\in H_{0}^{1,2}(\mathbb{R}_{+}^{2})\subset H^{1,2}(\mathbb{R}_{+}^{2}).$
(2.5)

Hence

$-\Delta V=0.$

Let us now find the critical points of $\mathcal{E}$, i.e.
$\langle\mathcal{E}^{\prime}(V),\phi\rangle=0$. Hence for any $\Phi\in
H^{1,2}(\mathbb{R}_{+}^{2})$ we have that

$\displaystyle 0$ $\displaystyle=\int_{\mathbb{R}_{+}^{2}}div(\Phi\nabla
V)dxdy+\int_{\mathbb{R}}W^{\prime}(v(x))\phi(x)dy\leavevmode\nobreak\
\text{for every}\leavevmode\nobreak\ \Phi\in H_{0}^{1,2}(\mathbb{R}_{+}^{2})$
(2.6) $\displaystyle=$ $\displaystyle\int_{\mathbb{R}}\phi\frac{\partial
V}{\partial y}dx+\int_{\mathbb{R}}W^{\prime}(v(x))\phi(x)dx.$ (2.7)

Therefore, the problem boils down to

$\displaystyle\begin{split}-\Delta V&=0\leavevmode\nobreak\
\text{in}\leavevmode\nobreak\ \mathbb{R}_{+}^{2}\\\ \frac{\partial V}{\partial
y}(x,0)&=-W^{\prime}(v(x)).\end{split}$ (2.8)

By the Fourier transform, the problem in (2.8) is equivalent to

$\displaystyle\begin{split}(-\Delta)^{1/2}V&=W^{\prime}(v)\leavevmode\nobreak\
\text{in}\leavevmode\nobreak\ \mathbb{R}.\end{split}$ (2.9)

##  3 Surprising aspects of solution to (2.9)

We know from the solutions of harmonic functions with Neumann or Dirichlet
condition has an exponential decay near infinity. However, we will see that
the $s$-harmonic functions have a polynomial decay.
Surprise $1$: We state the following theorem.

######  Theorem 3.1.

Suppose $u$ be a solution of

$\displaystyle(-\Delta)^{s}v=W^{\prime}(v)$ (3.1)

in $\mathbb{R}$ such that $\underset{x\to-\infty}{\lim}u(x)=0$ and
$\underset{x\to\infty}{\lim}u(x)=1$ and $u(0)=1/2$. Then

$\left|u(x)-H(x)+\frac{x}{2sW^{\prime\prime}(0)|x|^{1+2s}}\right|\leq\frac{C}{|x|^{\theta+2s}}$

as $|x|\to\infty$. Here $C,\theta>0$ and $H$ is the Heaviside function.

As remarked in the introduction, we will not play with the rigorous proofs of
the theorems and the associated results. However, at every stage we will help
the reader understand the results via an example or a heuristic but a strong
argument to get the flavour of the results.
In the case of the Theorem 3.1, we demonstrate this by taking $u$ to be a
compactly supported smooth, analytic function in $\mathbb{R}$. Then
$(-\Delta)^{s}u$ is of the order $1/|x|^{2s}$. To see this, we use the
following definition of the $s$-fractional operator.

$\displaystyle\begin{split}(-\Delta)^{s}u(x)&:=C_{N,s}\int_{\mathbb{R}}\frac{u(x+y)+u(x-y)-2u(x)}{|y|^{1+2s}}dy.\end{split}$
(3.2)

On expanding the Taylor series of $u$ around $x$ which is near the origin, we
get that $(-\Delta)^{s}u(x)\sim|x|^{2-2s}$, i.e. for $s<1$. However, near
infinity using the fact that the numerator being bounded, we conclude that the
function $1/|y|^{1+2s}$ is integrable if $s>0$. Hence, the operator
$(-\Delta)^{s}u(x)$ behaves like $1/|x|^{1+2s}$ near infinity for $0<s<1$.
Define $u^{\prime}:=w$. Hence near infinity, the given equation in (3.1) we
get

$\displaystyle(-\Delta)^{s}w=W^{\prime\prime}(1)w$ (3.3)

or

$\displaystyle(-\Delta)^{s}w=W^{\prime\prime}(0)w$ (3.4)

In either case we conclude that $w\sim 1/|x|^{1+2s}$. Hence $u\sim
1/|x|^{2s}$. However, this is a contradiction since a compactly supported
smooth and analytic function cannot have a polynomial like decay. Therefore,
the gist of the Theorem 3.1 is that a solution to (3.1) can neither be
compactly supported nor can be a Schwartz class function. It has to decay like
a polynomial. This is again quite different from a harmonic function, which
decays like an exponential function.
Surprise $2$: It is well known that the Heat equation decays in the order of
exponential function at infinity. Expecting the same to happen for a
fractional heat equation will surely take by surprise. Here is a quick look at
it. Consider the equation

$\displaystyle\begin{split}\frac{\partial}{\partial
t}u&=-(-\Delta)^{1/2}u\leavevmode\nobreak\ \text{in}\leavevmode\nobreak\
\mathbb{R}\times(0,\infty)\\\ u(x,0)&=\delta_{0}(x).\end{split}$ (3.5)

As we do it for the heat equation in the local case, we employ the Fourier
transform and find the quantity, say at $t=1$, to be
$u(x,1)=\mathfrak{F}^{-1}(e^{-|\xi|})=\int_{\mathbb{R}}e^{i\xi\cdot
x}e^{|\xi|}d\xi=\frac{2}{1+|x|^{2}}$. Thus, the decay is like a polynomial
again and not like an exponential function.
Surprise $3$: The problem

$\displaystyle\begin{split}(-\Delta)^{s}u&=0\leavevmode\nobreak\
\text{in}\leavevmode\nobreak\ \Omega\\\ u&=g\leavevmode\nobreak\
\text{in}\leavevmode\nobreak\ \partial\Omega\end{split}$ (3.6)

is ill-posed. This is not the case with a typical Dirichlet problem that
involves a Laplacian. The ill-posedness of the problem is evident from the
definition as

$\displaystyle(-\Delta)^{s}u(x)$
$\displaystyle=\int_{\Omega}\frac{u(x)-u(y)}{|x-y|^{N+2s}}dy+\int_{\mathbb{R}^{N}\setminus\Omega}\frac{u(x)-u(y)}{|x-y|^{N+2s}}dy\leavevmode\nobreak\
\text{for}\leavevmode\nobreak\ x\in\Omega.$ (3.7)

It is easy to see that $u$ can be chosen to be eccentrically different
functions in $\mathbb{R}^{N}\setminus\Omega$ by keeping $g$ to be the same on
the boundary $\partial\Omega$. These different possible extensions of $u$ may
lead to different values of $(-\Delta)^{s}u(x)$ for $x\in\Omega$, for an
unchanged $g$. This is a clear sign of ill-posedness as $(-\Delta)^{s}u$
becomes multi-valued and doesn’t even qualify to be called a function!.
Therefore, the correct formulation is

$\displaystyle\begin{split}(-\Delta)^{s}u&=0\leavevmode\nobreak\
\text{in}\leavevmode\nobreak\ \Omega\\\ u&=g\leavevmode\nobreak\
\text{in}\leavevmode\nobreak\ \mathbb{R}^{N}\setminus\Omega\end{split}$ (3.8)

or

$\displaystyle\int_{\Omega}\frac{u(x)-u(y)}{|x-y|^{N+2s}}dy$
$\displaystyle=:(-\Delta)_{\Omega}^{s}u=0\leavevmode\nobreak\
\text{in}\leavevmode\nobreak\ \Omega$ (3.9) $\displaystyle u$
$\displaystyle=g\leavevmode\nobreak\ \text{in}\leavevmode\nobreak\
\partial\Omega.$ (3.10)

Surprise $4$: The Harnack’s inequality fails to hold. Consider the following
problem.

$\displaystyle\begin{split}(-\Delta)^{1/2}u&=0\leavevmode\nobreak\
\text{in}\leavevmode\nobreak\ \mathbb{R}.\end{split}$ (3.11)

Incidentally,

$u(x)=\begin{cases}(1-|x|^{2})^{-1/2},&\text{if}\leavevmode\nobreak\ |x|<1\\\
0,&\text{otherwise}\end{cases}$

is a solution to (3.11). This is because of the following reason. Consider the
complex valued function $w(z)=\text{Re}(1-z^{2})^{-1/2}$. If one observes
carefully the equations (2.8)-(2.9), then it can bee seen that a problem with
a $s$-Laplacian can be studied by extending by a dimension and convertig it to
a problem with a local operator. For more details on this the reader may refer
to Caffarelli-Silvestre [1]. Therefore,

$\displaystyle(-\Delta)^{1/2}u(x)$ $\displaystyle=-\underset{y\to
0}{\lim}\frac{\partial}{\partial y}w(x+iy)=0.$ (3.12)

Note that this solution can never obey the Harnack’s inequality.
Surprise 5: The boundary growth of a $s$-harmonic function is not linear which
is unlike a harmonic function. Consider the problem

$\displaystyle\begin{split}(-\Delta)^{1/2}u&=1\leavevmode\nobreak\
\text{in}\leavevmode\nobreak\ (-1,1)\\\ u&=0\leavevmode\nobreak\
\text{in}\leavevmode\nobreak\ \mathbb{R}\setminus(-1,1).\end{split}$ (3.13)

A solution to (3.13) is

$u(x)=\begin{cases}(1-|x|^{2})^{1/2},&\text{if}\leavevmode\nobreak\ |x|<1\\\
0,&\text{otherwise}.\end{cases}$

As like in Surprise $4$, we choose $w(z)=\text{Re}[(1-z^{2})^{1/2}-iz]$.
Observe that when $z=iy$, then $w(iy)=(1+y^{2})^{1/2}\sim y$ near infinity.
Therefore we have to deduct $y$ so that at infinity the solution decays. This
is the reason why $iz$ has been deducted while defining the function $w$
(which is not the case with the solution of (3.11)). Thus

$\displaystyle(-\Delta)^{1/2}u(x)$ $\displaystyle=-\underset{y\to
0}{\lim}\frac{\partial}{\partial y}w(x+iy)=1.$ (3.14)

Note that the solution $u$ does not decay linearly near the boundary.

##  4 Acknowledgement

The author acknowledge the facilities received from the Department of
Mathematics, NIT Rourkela, India. The author also thanks Prof. Valdinoci for
his excellent lectures.

## References

  * [1] L. Caffarelli, L. Silvestre, An extension problem related to the fractional Laplacian, Communications in Partial Differential Equations, 32, 1245–1260, 2007.
  * [2] E. Di Nezza, G. Palatucci, E. Valdinoci, Hitchhiker’s guide to the fractional Sobolev spaces, Bull. Sci. Math., 136(5), 521–573, 2012.


# Text Revealer: Private Text Reconstruction via Model Inversion Attacks
against Transformers

Ruisi Zhang
University of California San Diego Seira Hidano
KDDI Research, Inc. Farinaz Koushanfar
University of California San Diego

###### Abstract

Text classification has become widely used in various natural language
processing applications like sentiment analysis. Current applications often
use large transformer-based language models to classify input texts. However,
there is a lack of systematic study on how much private information can be
inverted when  publishing models. In this paper, we formulate _Text Revealer_
— the first model inversion attack for text reconstruction against text
classification with transformers. Our attacks faithfully reconstruct private
texts included in training data with access to the target model. We leverage
an external dataset and GPT-2 to generate the target domain-like fluent text,
and then perturb its hidden state optimally with the feedback from the target
model. Our extensive experiments demonstrate that our attacks are effective
for datasets with different text lengths and can reconstruct private texts
with accuracy.

##  1 Introduction

Natural language processing with its application in various fields have
attracted much attention in recent years. With the recent advance in
transformer-based language models (LMs), BERT Devlin et al. (2018) and its
variants Liu et al. (2019); Xie et al. (2021); Qin et al. (2022) are used to
classify text datasets and achieve state-of-the-art performance. However, LMs
tend to memorize data during training, which results in unintentional
information leakage Carlini et al. (2021).

Model inversion attacks Fredrikson et al. (2015), which invert training
samples from the private dataset, has long been applied in the vision domain
Yang et al. (2019); Zhang et al. (2018); Wang et al. (2021); Kahla et al.
(2022). For text-based datasets, the model inversion attacks have been applied
in the medical domain to infer patients’ privacy information. Recent work like
KART Nakamura et al. (2020) and Lehman et al. Lehman et al. (2021) consider
inverting tabular data with sensitive attributes from the medical datasets.
However, they follow a fill-in-blank scheme and fail to reconstruct sentences
with fluency from scratch.

In this paper, we focus on reconstructing private training data from fine-
tuned LMs at inference time. It has a more general scenario where unauthorized
personal data such as chats, comments, reviews, and search history may be used
to train LMs. We perform a systemic study on how much private information is
leaked via model inversion attacks. There are several challenges when
performing model inversion attacks on NLP models. First, the candidate pixel
range is 256 in images, but the candidate token range is more than 30,000.
Therefore, it is harder to find the exact token for the sentence. Secondly,
image inversion is more error-tolerant, i.e., error in some pixels will not
affect the overall results. However, errors in some of the tokens will
significantly affect the fluency of the texts. Thirdly, current text
reconstruction attacks have different settings from model inversion attacks.
Most of them fall into two categories: Gradient attack Deng et al. (2021); Zhu
et al. (2019), which utilize gradient during distributed training to do
attack. Embedding level reconstruct attack Xie and Hong (2021); Pan et al.
(2020), which trains a mapping function to reconstruct texts from pre-trained
embeddings.

We propose _Text Revealer_ to perform model inversion attack on text data. In
the attack, the adversary knows the domain of the private dataset and has
access to the target models. Our attack consists of two stages: in the first
stage, we collect texts from the same domain as the public dataset and extract
high-frequency phrases from the public dataset as templates. Then, we train a
GPT-2 as the text generator on the public dataset. In the second stage, we
borrow the idea from PPLM Dathathri et al. (2019) to continuously perturb the
hidden state in the GPT-2 based on the feedback from the target model. By
minimizing the cross-entropy loss, generated text distribution becomes closer
to the private datasets. Experiments on the Emotion and Yelp datasets with two
target models, BERT and TinyBERT, demonstrate _Text Revealer_ can reconstruct
private information with readable contents. In summary, our approach has the
following contributions:

$\bullet$ We propose _Text Revealer_ , the first model inversion attack for
text reconstruction against text classification with transformers, to
reconstruct private training data from the target models.

$\bullet$ Results on two transformer-based models and two datasets with
different lengths have demonstrated _Text Revealer_ can reconstruct private
texts with accuracy.

##  2 Approach

###  2.1 Threat Model

#### Adversary’s Target and Goal

The adversary’s goal is to invert memorized training data from the fine-tuned
LMs. The inverted texts should meet two requirements: (1) the texts are close
to the distribution of private dataset $D_{\mathrm{pri}}$. (2) the texts are
readable so the adversary can infer meaningful contents from them. In our
paper, we use the BERT and TinyBERT as the target LMs to do text
classification tasks. We choose the target LMs for the following reasons: (1)
BERT and its variants achieve state-of-the-art in most text classification
tasks. (2) From the ethical standpoint, evaluating how sensitive the
transformer-based model is to text classification, one of the essential tasks
in the NLP domain, is important for subsequent research on defense methods.

#### Adversary’s Capability and Knowledge

We consider the adversary knows the domain of the dataset on which the
language model (LM) is fine-tuned. The adversary also has white-box access to
the LM. During the attack, given the input sentences or input embeddings, the
adversary can get the prediction score over $N$ classes with the probabilities
$P=(p_{1},p_{2},...,p_{n})$. Throughout this paper, let $p_{a}(X)$ denote the
prediction with a given input $X$ for a label $a$.

###  2.2 Attack Construction

As shown in Figure 1, the general attack construction consists of two stages:
(1) public dataset collection and analysis, and (2) word embedding
perturbation.

Figure 1: Attack construction pipeline.

#### Public dataset collection and analysis

We first collect dataset from the same domain to form public dataset
$D_{\mathrm{pub}}$ and perform $n$-gram analysis. There is no annotation in
$D_{\mathrm{pub}}$. As the dataset grows larger, the word frequency between
private dataset $D_{\mathrm{pri}}$ and public dataset $D_{\mathrm{pub}}$
becomes closer (see Section 3.7 for the details). Therefore, we can infer some
phrases may appear in the private dataset by doing the $n$-gram analysis and
collecting high-frequency items as template $T$. Then, we fine-tune a GPT-2
$G$ to generate fluent texts following the distribution of $D_{\mathrm{pub}}$.
We train $G$ by minimizing $\min_{G}L(G,D_{\mathrm{pub}})$, where $L$ is the
cross entropy loss.

#### Word embedding perturbation

We borrow the text perturbation idea from Plug and Play Language Model(PPLM)
Dathathri et al. (2019) but change the optimization objective to perform the
model inversion attack. PPLM is a lightweight text generation algorithm that
uses an attribute classifier to help the GPT-2 perturb its hidden state and
guide the generation.

We perturb the hidden state of the text generator to make generated texts
closer to the distribution of the private dataset. Let $H_{t}$ be the current
hidden state of the text generator $G$. Let $L_{\mathrm{adv}}$ be an
adversarial loss to measure the distance between the generated text $G(H_{t})$
and the private dataset $D_{\mathrm{pri},a}$ of the target label $a$. The
adversary generates perturbations $\Delta H_{t}$ for $H_{t}$ by solving the
following optimization problem:

${\color[rgb]{0,0,0}\min_{\Delta H_{t}}L_{\mathrm{adv}}(G(H_{t}+\Delta
H_{t}),D_{\mathrm{pri},a}).}$ (1)

Since the adversary has no prior knowledge of the private dataset, we measure
the loss $L_{\mathrm{adv}}$ with the cross-entropy calculated from the target
model’s prediction $p_{a}(G(H_{t}))$ with the generated text $G(H_{t})$ for
the target label $a$. This is because the cross-entropy takes a small value
when the input to the model is similar to the training data. We also show that
the cross-entropy is more effective for our model inversion attacks than the
loss based on the whole prediction score $P$, such as the modified entropy
Song and Mittal (2021) (see Section 3.6 for the details). To obtain the
optimal $\Delta H_{t}$, we minimize the cross-entropy by decending the hidden
state.

##  3 Experiments

###  3.1 Datasets

Emotion Dataset Saravia et al. (2018) is a sentence-level emotion
classification dataset with six labels: sadness, joy, love, anger, fear, and
surprise. Yelp Dataset Zhang et al. (2015) is a document-level review dataset.
The reviews are labeled from 1 to 5 stars indicating the user’s preference.
Following the split methods in image model-inversion attacks Zhang et al.
(2020), we randomly sample 80% of the samples as public dataset and 20% of the
samples as the private dataset. The average token length is 20 in the private
Emotion dataset and 134 in the private Yelp dataset.

###  3.2 Evaluation Metrics

Recovery Rate (RR.) is the percentage of tokens in private dataset recovered
by different attack methods. We filtered punctuations, special tokens and
NLTK’s stop words Bird et al. (2009) in the private dataset. Attack Accuracy
(Acc.) is the classification accuracy using evaluation classifier on inverted
texts. According to Zhang et al. (2020), the higher the classification
accuracy is, the more private information the texts is considered to be
inverted. We use BERT Large as the evaluation classifier and fine-tune it
until the accuracy on the private dataset is over 95%. Fluency is the Pseudo
Log-Likelihood (PLL) of fixed-length models on inverted
texts111https://huggingface.co/docs/transformers/perplexity.

###  3.3 Baselines

We compare our method with vanilla model inversion attack Fredrikson et al.
(2015) and vanilla text generation Radford et al. (2019).

#### Vanilla model-inversion attack (VMI)

In this setting, the adversary exploits the classification loss by adjusting
text embeddings and returning the texts minimizing the cross-entropy loss. We
set the text length to the average length of the private dataset, adjust the
text embeddings for 50 epochs and run the same times as the number of
templates.

#### Vanilla text generation (VTG)

In this setting, the adversary uses a GPT-2 model to generate the texts. The
GPT-2 is trained on the public dataset and conditioned on our collected
templates. We limit the maximum length to the average length of the private
dataset. For the attack accuracy on VTG, we calculate the frequency of
collected templates under different labels in the public dataset and use the
label with the highest frequency as the target label. During the attack, only
VTG requires extra annotations to benchmark its performance. For target model
TinyBERT and BERT, we run VTG twice and use the results for two target models.

###  3.4 Target Models

We use two representative transformer-based LM as our target model: (1) Tiny-
BERT Bhargava et al. (2021) and (2) BERT Devlin et al. (2018). The TinyBERT
has four layers, 312 hidden units, a feed-forward filter size of 1200, and 6
attention heads. It has 110M parameters. The BERT has 12 layers, 768 hidden
units, a feed-forward filter size of 3072, and 12 attention heads. It has 4M
parameters.

| Emotion Dataset | Yelp Dataset
---|---|---
| Tiny-BERT | BERT | Tiny-BERT | BERT
| VMI | VTG | TR | VMI | VTG | TR | VMI | VTG | TR | VMI | VTG | TR
RR.(%) | 27.54 | 61.23 | 67.36 | 34.33 | 59.42 | 67.76 | 50.89 | 74.47 | 83.22 | 75.56 | 73.22 | 84.29
Acc. (%) | 72.04 | 74.50 | 84.14 | 73.90 | 73.65 | 85.54 | 22.56 | 23.34 | 33.98 | 21.29 | 22.16 | 34.22
PLL | 1493 | 43.31 | 80.79 | 2628 | 42.27 | 94.53 | 2391.09 | 16.82 | 62.75 | 4010.46 | 16.64 | 72.78
Table 1: Results of the model-inversion attack, TR is short for our _Text
Revealer_.

###  3.5 Results

The result of our model inversion attack is summarized in Table 1. We can make
the following observations: (1) VTG and _Text Revealer_ tend to invert more
tokens and achieve lower PLL compared with VMI. This is because VMI trains the
text embeddings from scratch with random initialization, which results in not
meaningful combinations of tokens. Even though many tokens can be recovered
using VMI, private information still cannot be inferred from the private
dataset. (2) Compared with VTG, our algorithm achieves higher recovery rates
and higher attack accuracy. By perturbing the hidden state of trained GPT-2,
our algorithm can infer more private information from the target model. (3)
For smaller Emotion dataset, all three methods achieve high attack accuracy
and can invert private information from the private dataset. However, in the
larger Yelp dataset, VMI and VTG’s attack accuracy becomes near 20%. It is
close to random classification because only 5 classes are in the dataset. (4)
For both VMI and _Text Revealer_ , BERT’s recovery rate and attack accuracy
are higher than TinyBERT. It means more private information is memorized as
the transformer becomes larger.

###  3.6 Ablation Studies

#### Effectiveness of fine-tuning GPT-2

In this setting, we fine-tune the GPT-2 on the public dataset and compare the
results with vanilla GPT-2 on the Yelp dataset. The results are summarized in
Table 2. The table shows that fine-tuned GPT-2 achieves higher recovery rate
and attack accuracy. It means more sensitive information is revealed from
fine-tuning.

| RR. | Acc. | PLL
---|---|---|---
fine-tuned GPT | 84.29 | 34.22 | 72.78
vanilla GPT | 79.17 | 31.29 | 72.21
Table 2: Model inversion with guidance from fine-tuned GPT-2 and vanilla GPT-2
on BERT.

#### Effectiveness of model inversion attack

We analysis the effectiveness of word perturbation and loss function by
comparing with different methods. For word perturbation, we compare _Text
Revealer_ ’s word perturbation with Gumbel softmax Jang et al. (2016). For
Gumbel softmax, we first use fine-tuned GPT-2 to generate original sentences,
and set coefficient for tokens in vocabulary. Then, we update the coefficient
based on the cross-entropy loss using Gumbel softmax and update the input
sentences. From the table, we can find Gumbel softmax and modified
perturbation achieve similar attack accuracy. However, the recovery rate and
fluency is lower than modified perturbation.

For loss function, we compare cross entropy with Modified entropy loss Song
and Mittal (2021). The modified entropy loss makes the loss monotonically
decreasing with the prediction probability of the correct label and increasing
with the prediction probability of any incorrect label. In this setting, we
use the same pipeline as _Text Revealer_ , but change the loss to modified
entropy loss to update GPT-2’s hidden state. We can find cross entropy loss
achieves best performance out of other loss functions.

Attack | RR. | Acc. | PLL
---|---|---|---
_Text Revealer_ | 84.29 | 34.22 | 72.78
Gumbel softmax | 78.13 | 33.49 | 77.70
Modified Entropy Loss | 74.23 | 32.74 | 77.25
Table 3: Model inversion with different method.

###  3.7 Analysis

#### Effectiveness of template length

In this setting, we analyze how the inversion accuracy changes with the length
of the template and summarize the results in Table 7. The template length is
$L$, and we extract the first 0.3 $L$, 0.5 $L$, and 0.7 $L$ tokens from the
template. If the extracted token number is smaller than 1, we choose the first
token from the template. For example, if the original template is "if i could
give this place 0 star", then 0.7 $L$ template would be "if i could give
this," 0.5 $L$ template would be "if i could give," and 0.3 $L$ template would
be "if i." As text length becomes shorter, _Text Revealer_ achieves worse
recovery rates and attack accuracy. It means longer template length can give
GPT-2 more contexts and help it invert more private information.

Template Length | RR. | Acc. | PLL
---|---|---|---
0.3 $L$ | 84.17 | 17.60 | 76.45
0.5 $L$ | 84.03 | 22.49 | 80.85
0.7 $L$ | 83.62 | 27.32 | 79.71
$L$ | 84.29 | 34.22 | 72.78
Table 4: Model inversion with different length of the template. The percentage means the number of tokens we take since the start token. |  Ground Truth |  Inverted
---|---|---
Example 1 |  i don t feel so exhausted all the time |  feel a little exhausted feel a little bit from all the time
Example 2 |  i feel blessed amazed and yes very excited |  i feel blessed and grateful for the amazing new life
Example 3 |  the Parlor has one of the best atmospheres in Phoenix! |  The Parlor has soo, the best Mexican restaurants in Phoenix Palace!
Example 4 |  The decor was very inviting and we love Mexican food (again, from San Diego) The chips and salsa were delicious. |  We are from San Diego I was a Mexican food lover, we had the chips, salsa was very nice.
Table 5: Iverted Examples, the first two are from the Emotion dataset, and the
last two are from the Yelp dataset.

(a) Example 1 (b) Example 2 (c) Example 3 (d) Example 4

Figure 2: Visualization of inverted embeddings, the first two are from the
Emotion dataset, and the last two are from the Yelp dataset.

#### Inverted examples & Visualization

Following TAG Deng et al. (2021), We display how our inverted examples is
approximate the distribution of private dataset at embedding level and
sentence level. We use sentences with longest matching subsequence in the
private dataset as ground truth. We first use Principal Component Analysis
(PCA) Abdi and Williams (2010) to reduce the dimension for ground truth and
inverted examples and display the plot in Figure 2. Then, we display the
inverted examples at sentence level in Table 5

#### Public dataset & Private dataset

We use Kendall tau distance Fagin et al. (2003) to measure the token
distribution similarity between the private and public datasets. The Kendall
tau distance is a metric to measure the top-$k$ elements correlation between
two lists. The larger the distance is, the stronger correlation the two lists
have. When ranking the tokens in each dataset, we filtered the special tokens,
punctuations, and stop words in NLTK Bird et al. (2009).  From the results in
Table 6, we can find the word ranking and frequency is close between the
private and public datasets.

We also compare the accuracy of the Emotion and the Yelp Dataset in Table 6.
Before fine-tuning, the classification accuracy is similar for both private
and public datasets. However, after fine-tuning, the accuracy between the
private dataset and the public dataset has a large gap, which means some texts
are memorized Carlini et al. (2021) in the trained transformers.

| Emotion | Yelp Dataset
---|---|---
Distance(Top10) | 0.99 | 0.99
Distance(Top100) | 0.32 | 0.62
Tiny-BERT-Public(+) | 84.79 | 60.58
Tiny-BERT-Private(+) | 94.15 | 79.44
Tiny-BERT-Public(-) | 12.81 | 20.38
Tiny-BERT-Private(-) | 13.25 | 20.59
BERT-Public(+) | 91.25 | 64.42
BERT-Private(+) | 99.66 | 95.12
BERT-Public(-) | 13.34 | 20.02
BERT-Private(-) | 14.09 | 19.88
Table 6: The first cell is the ranking distance between the private and public
datasets. The second and third cell is the accuracy on public and private
datasets, "+" means the BERT model is fintuned on the private dataset, "-"
means the plain BERT model.

##  4 Conclusion

In this paper, we present _Text Revealer_ to invert texts from the private
dataset. Experiments on different target models and datasets have demonstrated
our algorithm can faithfully reconstruct private texts with accuracy. In the
future, we are interested in exploring potential defense methods.

## References

  * Abdi and Williams (2010) Hervé Abdi and Lynne J Williams. 2010.  Principal component analysis.  _Wiley interdisciplinary reviews: computational statistics_ , 2(4):433–459.
  * Bhargava et al. (2021) Prajjwal Bhargava, Aleksandr Drozd, and Anna Rogers. 2021.  Generalization in nli: Ways (not) to go beyond simple heuristics.
  * Bird et al. (2009) Steven Bird, Ewan Klein, and Edward Loper. 2009.  _Natural language processing with Python: analyzing text with the natural language toolkit_.  " O’Reilly Media, Inc.".
  * Carlini et al. (2021) Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. 2021.  Extracting training data from large language models.  In _30th USENIX Security Symposium (USENIX Security 21)_ , pages 2633–2650.
  * Dathathri et al. (2019) Sumanth Dathathri, Andrea Madotto, Janice Lan, Jane Hung, Eric Frank, Piero Molino, Jason Yosinski, and Rosanne Liu. 2019.  Plug and play language models: A simple approach to controlled text generation.  _arXiv preprint arXiv:1912.02164_.
  * Deng et al. (2021) Jieren Deng, Yijue Wang, Ji Li, Chao Shang, Hang Liu, Sanguthevar Rajasekaran, and Caiwen Ding. 2021.  Tag: Gradient attack on transformer-based language models.  _arXiv preprint arXiv:2103.06819_.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Fagin et al. (2003) Ronald Fagin, Ravi Kumar, and D. Sivakumar. 2003.  Comparing top k lists.  _SIAM Journal on Discrete Mathematics_ , 17(1):134–160.
  * Fredrikson et al. (2015) Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. 2015.  Model inversion attacks that exploit confidence information and basic countermeasures.  In _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security_ , pages 1322–1333.
  * Jang et al. (2016) Eric Jang, Shixiang Gu, and Ben Poole. 2016.  Categorical reparameterization with gumbel-softmax.  _arXiv preprint arXiv:1611.01144_.
  * Jiao et al. (2019) Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu. 2019.  Tinybert: Distilling bert for natural language understanding.  _arXiv preprint arXiv:1909.10351_.
  * Kahla et al. (2022) Mostafa Kahla, Si Chen, Hoang Anh Just, and Ruoxi Jia. 2022.  Label-only model inversion attacks via boundary repulsion.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 15045–15053.
  * Lehman et al. (2021) Eric Lehman, Sarthak Jain, Karl Pichotta, Yoav Goldberg, and Byron C Wallace. 2021\.  Does bert pretrained on clinical notes reveal sensitive data?  _arXiv preprint arXiv:2104.07762_.
  * 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_.
  * Nakamura et al. (2020) Yuta Nakamura, Shouhei Hanaoka, Yukihiro Nomura, Naoto Hayashi, Osamu Abe, Shuntaro Yada, Shoko Wakamiya, and Eiji Aramaki. 2020.  Kart: Privacy leakage framework of language models pre-trained with clinical records.  _arXiv preprint arXiv:2101.00036_.
  * 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 (SP)_ , pages 1314–1331. IEEE.
  * Qin et al. (2022) Haotong Qin, Yifu Ding, Mingyuan Zhang, Qinghua Yan, Aishan Liu, Qingqing Dang, Ziwei Liu, and Xianglong Liu. 2022.  Bibert: Accurate fully binarized bert.  _arXiv preprint arXiv:2203.06390_.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9.
  * Saravia et al. (2018) Elvis Saravia, Hsien-Chi Toby Liu, Yen-Hao Huang, Junlin Wu, and Yi-Shin Chen. 2018\.  CARER: Contextualized affect representations for emotion recognition.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_.
  * Song and Mittal (2021) Liwei Song and Prateek Mittal. 2021.  Systematic evaluation of privacy risks of machine learning models.  In _30th USENIX Security Symposium (USENIX Security 21)_ , pages 2615–2632.
  * Wang et al. (2021) Kuan-Chieh Wang, Yan Fu, Ke Li, Ashish Khisti, Richard Zemel, and Alireza Makhzani. 2021.  Variational model inversion attacks.  _Advances in Neural Information Processing Systems_ , 34.
  * Xie et al. (2021) Keli Xie, Siyuan Lu, Meiqi Wang, and Zhongfeng Wang. 2021.  Elbert: Fast albert with confidence-window based early exit.  In _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 7713–7717. IEEE.
  * Xie and Hong (2021) Shangyu Xie and Yuan Hong. 2021.  Reconstruction attack on instance encoding for language understanding.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 2038–2044.
  * Yang et al. (2019) Ziqi Yang, Ee-Chien Chang, and Zhenkai Liang. 2019.  Adversarial neural network inversion via auxiliary knowledge alignment.  _arXiv preprint arXiv:1902.08552_.
  * Zhang et al. (2018) Weichen Zhang, Wanli Ouyang, Wen Li, and Dong Xu. 2018.  Collaborative and adversarial network for unsupervised domain adaptation.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 3801–3809.
  * Zhang et al. (2015) Xiang Zhang, Junbo Zhao, and Yann LeCun. 2015.  Character-level convolutional networks for text classification.  _Advances in neural information processing systems_ , 28.
  * Zhang et al. (2020) Yuheng Zhang, Ruoxi Jia, Hengzhi Pei, Wenxiao Wang, Bo Li, and Dawn Song. 2020.  The secret revealer: Generative model-inversion attacks against deep neural networks.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Zhu et al. (2019) Ligeng Zhu, Zhijian Liu, and Song Han. 2019.  Deep leakage from gradients.  _Advances in Neural Information Processing Systems_ , 32.

##  Appendix A Appendix

###  A.1 Limitations

Our work has the following limitations. (1) From the attack side, the model
inversion attack achieves lower attack accuracy as the dataset becomes larger.
It would be interesting to explore better template extract methods to improve
the accuracy. (2) From the ethical standpoint, evaluating how sensitive BERT
based model is to classification tasks is essential to future defense methods.
Due to page limits, we did not go into the defense methods. We will continue
to work on it in future work.

###  A.2 Ethics Statement

Our work focuses on the privacy problems in natural language processing. Even
though model inversion attacks proposed in our paper can cause potential data
leakage. Evaluating how sensitive BERT based model is to classification tasks
is important to future defense methods.

###  A.3 Hyperparameters and training details

#### Template

We perform $n$-gram analysis on the public dataset. For Emotion dataset, we
extract phrase length from 1 word to 3 words with frequency higher than 20.
Then, we filter one-word adjectives and permute them with 2-3 word to form
template. The total number is 220. For Yelp dataset, we extract phrase length
from 3 words to 8 words with frequency higher than 20. The total number is
320. Some of the templates are summarized in Table 7

Datasets |  Examples
---|---
Emotion |  feeling a little, feel like, down, alone, love, good, passionate, sweet, irritable, angry, strange, nervous, surprised, amazed
Yelp |  if i could give this place zero stars, i will never go, really wanted to like this place, i cant wait to go back, if you are looking for, cant say enough good things about, one of the best, i m not a fan of, this place is, if you re in the mood for, only reason i didn t give it
Table 7: Template examples.

#### BERT fine-tuning

The BERT and TinyBERT are trained as target models on the private dataset. For
both BERT and TinyBERT, we set the batch size to 8. We use AdamW as the
optimizer with initial learning rate set to 5e-5. We train 5 epochs on BERT
and 10 epochs on TinyBERT. Other parameters follow the original implementation
in Devlin et al. (2018); Jiao et al. (2019).

#### GPT-2 fine-tuning

The GPT-2 is trained on the public dataset to help _Text Revealer_ reconstruct
texts. For GPT-2, we set the batch size to 8, and use AdamW as the optimizer
with initial learning rate set to 5e-5. We train 10 epochs for both datasets.
Other parameters follow the original implementation in Radford et al. (2019).
It has 124M parameters.

#### Text Revealer

When using the _Text Revealer_ , we set the iteration number to the average
length of the private dataset. We set the window mask to 3 and KL loss
coefficient to 0. Other parameters follow the original implementation in
Dathathri et al. (2019).

#### Computing Infrastructure

Our code is implemented with PyTorch. Our attack pipeline are all constructed
using TITAN Xp. We fine-tune the target LMs and GPT-2 on NVIDIA RTX A6000.

###  A.4 More inverted examples

We display more inverted examples in Table 8 and Table 9. We show four
examples for each method in Emotion dataset and two examples for each method
in Yelp dataset.

Method |  Examples
---|---
BERT-VMI |  cancel the dream vascular place seeing halfway hopeful applicant Mandy.
Higgins suspiciously information poollifting Cardinal faint Scots Davidfeld
lanes creepy fears Call lap dick Evening Slim favor
impressive wireless baptism longing Independent IN forensic Wish physically
BERT-VTG |  feeling a little inspired by their own experience.
feel like productive people and more than a little creepy.
i feel reluctant to give me their phone number.
i feel uncomfortable at all in the light of it
BERT-TR |  feel like glad to be here i feel welcomed.
feel like mellow at breathlessly flowing smoothly and i feel was was pretty
i feel afraid that people dont see the movie spoiler place where
feel uncomfortable talking to my partner or to stop feeling guilty
TinyBERT-VMI |  roughly spiritual thereof 41 rebellious fragrance its caused strangled ave
algeria toward puzzled kowalski bobbie sexually liz circle hiding
code balls redundant persuaded carpathian yugoslav drownedpins
burnley rubbish receipts borough fragmentation worthless soga
TinyBERT-VTG |  i feel resentful and lonely, she doesn’t seem to like me
feel like irritated that my boss is complaining about something
feeling a little rude but i wont be afraid
feeling a little pain in my lower back and im trying to harden
TinyBERT-TR |  feeling a little amazing artistic life positive super job productive
feeling mellow wise just like how much she is
I feel thankful that god gave me more blessings in return
feel like overwhelmed or at the wrong spot saying good feeling
Table 8: Emotion dataset inverted examples, TR is short for our _Text Revealer_. Method |  Examples
---|---
BERT-VMI |  promising odor Daemon asked exactly platinum wonderful confession Aaron Tiger Magazine field AMC documentaries edible Name Always Benito Northeast invalid Brooks d Games exist range removal thee drag monkey revolution hostile graphicspent permitted expenses mythical newest Massey
##wood successors rich hood Jameson Lin publishes festivities Slave ordering
trans plot text Programs reluctantly promising Glad España stands combining
accommodate captain elongated stranger Conservatory express receives phones
bias Depending pile motivation Loving chickens owl denied bage
BERT-VTG |  i wouldn t go out of my way to come here, but i had a coupon for a 50 dollar pizza for one hour and a free 30 minute massage in addition to the 20 dollars i spent. when we arrived the staff greeted us and escorted us to our room. that was good service and i enjoyed that.
can t wait to go back and try more! the food was amazing and the service was
beyond fast! I had the grilled pork chop which was one of the best dishes I
have ever had in my life. the other dishes, the veal, were also very good! The
dessert was just as amazing, I would have happily eaten any dessert.
BERT-TR |  i wouldn t go out of my way to come here, but i love the food and atmosphere well, i’m a foodie, so i know what to expect from this place. the chips are the BEST i’ve had in my lifetime. i had the beef barbacoa taco and i know what to expect from this place, it was absolutely delicious!
i can t wait to go for me to get my first! This is the most of my favorite
place, you. I was shopping a place to take my family that and get the best.
the restaurant is always clean and the staff are friendly.
TinyBERT-VMI |  ##wil apt fish pairs certification maker walker indictment thieves unity negligence 69 crook criminal fraud aligned partly negligence racist bewildered architects inspectors pageant fraud victims atheist restore harassment gasoline ny removed screenplay transformed feathers investigation regular layers random
haiti sloping revolving simulator visitor decided marathon faerie sizable sob
ty gerald decker buzz shortage suriname verity dream edpace batavia oliver
meter41 winced surround fewer grumbled celtics reducing qualify secured
completes brandon dimly brandonnb pointless hunts proper attemp
TinyBERT-VTG |  i can t say enough good things about this place i just will be back and i promise you i will never miss a thing this place is the bomb. and the staff is super nice and helpful post again.the good is amazing. they have a wide variety of beers all great.even on tap. and the service is top notch
if i could give this place zero starsi would. i have been going here since it
opened, but in recent years this place has went downhill. the waiters here use
to be very attentive and nice. now i don’t get it. everything they bring you
seems to have a strange ÿippieẗaste, which makes my blood boil.
TinyBERT-TR |  you get what you pay for for! i will always give my money to a place that gives me the best quality I can give. the ambiance is amazing, but the food takes forever. one friend and i went on a tuesday night, and although the place was dead, only a handful of people were eating. order 2 things: the kobe beef shortribs, the shish kabob, and the chicken shawerma.
can t wait to go back! my husband had the shrimp tacos and they were
fantastic! he had the margaritas and they were ok, but, the atmosphere and
staff was just really nice and friendly. we’ll definately go back. for the
awesome margaritas!!for the delicious food! great prices!!!to our server,
jason. for the amazing service!
Table 9: Yelp dataset inverted examples, TR is short for our _Text Revealer_.