#  Classes of operators related to $m$-isometric operators

Salah Mecheri and Sid Ahmed Ould Ahmed Mahmoud  S. MecheriDepartment of
MathematicsTebessa University 12002-Tebessa Algeria<EMAIL_ADDRESS>Sid Ahmed Ould Ahmed Mahmoud Mathematics Department, College of Science, Jouf
University,Sakaka P.O.Box 2014. Saudi Arabia<EMAIL_ADDRESS>
###### Abstract.

Isometries played a pivotal role in the development of operator theory, in
particular with the theory of contractions and polar decompositions and has
been widely studied due to its fundamental importance in the theory of
stochastic processes, the intrinsic problem of modeling the general
contractive operator via its isometric dilation and many other areas in
applied mathematics. In this paper we present some properties of
$n$-quasi-$(m,C)$-isometric operators. We show that a power of a
$n$-quasi-$(m,C)$-isometric operator is again a $n$-quasi-$(m,C)$-isometric
operator and some products and tensor products of $n$-quasi-$(m,C)$-isometries
are again n-quasi-$(m,C)$-isometries.

###### Key words and phrases:

$m$-isometries, $n$-quasi-$m$-isometries, $(m,C)$-isometries,
$n$-quasi-$(m,C)$-isometries

###### 2010 Mathematics Subject Classification:

Primary 47B99; Secondary 47A05.

##  1\. Introduction

Let $\mathcal{H}$ be a separable infinite dimensional complex Hilbert space
with inner product $\langle.\;|\;.\rangle$, $\mathcal{B}(\mathcal{H})$ be the
set of all bounded linear operators on $\mathcal{H}$, and $I=I_{\mathcal{H}}$
be the identity operator. For every $T\in\mathcal{B}(\mathcal{H})$ its range
is denoted by $\mathcal{R}(T)$, its null space by $\mathcal{N}(T)$. The
adjoint of $T$ is denoted by $T^{*}$. A subspace
$\mathcal{M}\subset\mathcal{H}$ is invariant for $T$ (or $T$-invariant) if
$T\mathcal{M}\subset\mathcal{M}$. As usual, the orthogonal complement and the
closure of $\mathcal{M}$ are denoted $\mathcal{M}^{\perp}$ and
$\overline{\mathcal{M}}$ respectively. We denote by $P_{\mathcal{M}}$ the
orthogonal projection on $\mathcal{M}$.

A conjugation is a conjugate-linear operator
$C:\mathcal{H}\longrightarrow\mathcal{H}$, which is both involutive (i.e.,
$C^{2}=I)$ and isometric (i.e., $\langle Cx\;|\;Cy\rangle=\langle
y\;|\;x\rangle\quad(\forall\;x,y\in\mathcal{H})$).

Recall that if $C$ is a conjugation on $\mathcal{H}$, then $\|C\|=1$,
$\big{(}CTC\big{)}^{k}=CT^{k}C$ and $\big{(}CTC\big{)}^{*}=CT^{*}C$ for every
positive integer $k$ (see [14] and [15] for more details).

Throughout this paper, let $m$ and $n$ be natural numbers. An operator
$T\in\mathcal{B}(\mathcal{H})$ is said to be :

$m$-isometry if

$\displaystyle\sum_{0\leq k\leq m}(-1)^{m-k}\binom{m}{k}T^{*m-k}T^{m-k}=0,$
(1.1)

or equivalently if

$\sum_{0\leq k\leq
m}(-1)^{m-k}\binom{m}{k}\|T^{k}x\|^{2}=0\;\;\quad\forall\;\;x\in{\mathcal{H}}.$
(1.2)

where $\displaystyle\binom{m}{k}$ is the binomial coefficient. These class of
operators have been introduced and studied by J. Agler and M. stankus in [2],
[3] and [4]. In recent years, the $m$-isometric operators have received
substantial attention. It has been proved in [7] and [10] that the powers of
an $m$-isometry are $m$-isometries and some products of $m$-isometries are
again $m$-isometries. On the other hand, the perturbation of $m$-isometries by
nilpotent operators has been considered in [9], [8], [5] and the dynamics of
$m$-isometries has been explored in [6] and other papers. Furthermore, Duggal
studied the tensor product of $m$-isometries in [13]. In addition,
$m$-isometry weighted shift operators have been discussed in [1] and the
reference therein. S. Mecheri and T.Parasad in [18] extended the notion of
$m$-isometric operator to the case of $n$-quasi-$m$-isometric operators of
bounded linear operators on a Hilbert space. An operator
$T\in{\mathcal{B}}({\mathcal{H}})$ is said to be $n$-quasi-$m$-isometric
operator if

$\displaystyle T^{*n}\bigg{(}\sum_{0\leq k\leq
m}(-1)^{k}\binom{m}{k}T^{*m-k}T^{m-k}\bigg{)}T^{n}=0,$ (1.3)

The $1$-quasi-isometries are shortly called quasi-isometries, such operators
being firstly studied in [20] and [22].

In [11], M. Chō, E. Ko and J. Lee introduced $(m,C)$-isometric operators with
conjugation $C$ and studied properties of such operators. For an operator
$T\in{\mathcal{B}}({\mathcal{H}}$) and an integer $m\geq 1$ , $T$ is said to
be an $(m,C)$-isometric operator if there exists some conjugation $C$ such
that

$\sum_{0\leq k\leq m}(-1)^{k}\binom{m}{k}T^{*m-k}CT^{m-k}C=0.$ (1.4)

According to definitions of $m$-isometry, $n$-quasi-$m$-isometry and
$(m,C)$-isometry, The authors in [23] define an $n$-quasi-$(m,C)$-isometry $T$
as follows. An operator $T$ is said to be an $n$-quasi-$(m,C)$-isometric
operator if there exists some conjugation $C$ such that

$T^{*n}\bigg{(}\sum_{0\leq k\leq
m}(-1)^{k}\binom{m}{k}T^{*m-k}CT^{m-k}C\bigg{)}T^{n}=0.$ (1.5)

It is easy to see that the class of $n$-quasi-$(m,C)$-isometry contains every
$(m,C)$-isometric operators with conjugation $C$.In general, this inclusion
relation is proper (see [23]). Many results about the class of
$n$-quasi-$(m,C)$-isometric operators have been found in [23].

In this paper it is shown that the operators in this class have many
interesting properties in common with $m$-isometries, $n$-quasi-$m$-isometries
and $(m,C)$-isometric operators. In particular, we show that the powers of an
$n$-quasi-$(m,C)$-isometry are $n$-quasi-$(m,C)$-isometries and some products
and tensor products of $n$-quasi-$(m,C)$-isometries are again
$n$-quasi-$(m,C)$-isometries. It has also been proved that the sum of an
$n$-quasi-$(m,C)$-isometry and a commuting nilpotent operator of degree $p$ is
a $(n+p)$-quasi-$(m+2p-2)$-isometry.

##  2\. Main Results

We begin by the following theorem, which is a structure theorem for
$n$-quasi-$(m,C)$-isometric operators.

In [23], the authors studied the matrix representation of
$n$-quasi-$(m,C)$-isometric operator with respect to the direct sum of
$\overline{{\mathcal{R}}(T^{n})}$ and its orthogonal complement. In the
following we give an equivalent condition for $T$ to be
$n$-quasi-$(m,C)$-isometric operator.

######  Theorem 2.1.

Let $C=C_{1}\oplus C_{2}$ be a conjugation on ${\mathcal{H}}$ where $C_{1}$
and $C_{2}$ are conjugation on $\overline{{\mathcal{R}}(T^{n})}$ and
${\mathcal{N}}({T^{\ast}}^{n})$, respectively. Assume that
${\mathcal{R}}(T^{n})$ is not dense, then the following statements are
equivalent:

$(1)$ $T$ is $n$-quasi-$(m,C)$-isometric operator,

$(2)$ $T=\left(\begin{array}[]{ccc}T_{1}&T_{2}\\\ 0&T_{3}\end{array}\right)$
on
${\mathcal{H}}=\overline{{\mathcal{R}}(T^{n})}\oplus{\mathcal{N}}({T^{\ast}}^{n})$,
where $T_{1}$ is an $(m,C_{1})$-isometric operator on
$\overline{{\mathcal{R}}(T^{n})}$, $T_{3}^{n}=0$, and
$\sigma(T)=\sigma(T_{1})\cup\\{0\\}$ where $\sigma(T)$ is the spectrum of $T$.

###### Proof.

$(1)\Rightarrow(2)$. Consider the matrix representation of $T$ with respect to
the decomposition
${\mathcal{H}}=\overline{{\mathcal{R}}(T^{n})}\oplus{\mathcal{N}}({T^{\ast}}^{n})$:

$T=\left(\begin{array}[]{ccc}T_{1}&T_{2}\\\ 0&T_{3}\end{array}\right)\
\mbox{on}\
{\mathcal{H}}=\overline{{\mathcal{R}}(T^{n})}\oplus{\mathcal{N}}({T^{\ast}}^{n}).$

Let $P$ be the projection of ${\mathcal{H}}$ onto
$\overline{{\mathcal{R}}(T^{n})}.$ Since $T$ is an $n$-quasi-$(m,C)$-isometric
operator, it follows that

$P\bigg{(}\sum_{0\leq k\leq
m}(-1)^{k}\binom{m}{k}T^{*m-k}CT^{m-k}C\bigg{)}P=0.$

This means that

$\sum_{0\leq k\leq m}(-1)^{k}\binom{m}{k}T_{1}^{*m-k}C_{1}T_{1}^{m-k}C_{1}=0.$

Hence $T_{1}$ is an $(m,C_{1})$-isometric operator on
$\overline{{\mathcal{R}}(T^{n})}$. Let $x=x_{1}\oplus
x_{2}\in\overline{{\mathcal{R}}(T^{n})}\oplus{\mathcal{N}}({T^{\ast}}^{n})={\mathcal{H}}$.
If $x\in{\mathcal{N}}({T^{\ast}}^{n})$, then

$\displaystyle\langle{T_{3}}^{n}x_{2},x_{2}\rangle$ $\displaystyle=$
$\displaystyle\langle T^{n}(I-P)x,(I-P)x\rangle$ $\displaystyle=$
$\displaystyle\langle(I-P)x,{T^{\ast}}^{n}(I-P)x\rangle=0.$

Hence ${T_{3}}^{n}=0$. So, we get that $\sigma(T)=\sigma(T_{1})\cup\\{0\\}$.

$(2)\Rightarrow(1)$ Suppose that

$T=\begin{pmatrix}T_{1}&T_{2}\\\ 0&T_{3}\end{pmatrix}\quad\text{ on
}\quad\mathcal{H}=\overline{\mathcal{R}(T^{n})}\oplus\mathcal{N}(T^{*n})$

where $\overline{{\mathcal{R}}(T^{n})}$ is the closure of
$\mathcal{R}(T^{n})$, where $T_{1}$ is an $(m,C_{1})$-isometry and
$T_{3}^{k}=0$: Since

$T^{k}=\begin{pmatrix}T^{n}_{1}&\displaystyle\sum_{0\leq j\leq
k-1}T^{j}_{1}T_{2}T^{k-1-j}_{3}\\\ 0&0\end{pmatrix}$

we have

$T^{*n}(\sum_{0\leq l\leq m}(-1)^{k}\begin{pmatrix}m\\\
k\end{pmatrix}T^{*m-k}CT^{m-k}C)T^{n}=$ $\begin{pmatrix}T_{1}&T_{2}\\\
0&T_{3}\end{pmatrix}^{*n}\bigg{(}\sum_{0\leq k\leq
m}(-1)^{k}\begin{pmatrix}m\\\ k\end{pmatrix}\begin{pmatrix}T_{1}&T_{2}\\\
0&T_{3}\end{pmatrix}^{*m-k}\begin{pmatrix}C_{1}&0\\\ 0&C_{2}\\\
\end{pmatrix}\begin{pmatrix}T_{1}&T_{2}\\\
0&T_{3}\end{pmatrix}^{m-k}\begin{pmatrix}C_{1}&0\\\ 0&C_{2}\\\
\end{pmatrix}\bigg{)}\begin{pmatrix}T_{1}&T_{2}\\\ 0&T_{3}\end{pmatrix}^{*n}$
$=\begin{pmatrix}T^{*n}_{1}DT^{k}_{1}&T^{*n}_{1}D\displaystyle\sum_{0\leq
j\leq k-1}T^{j}_{1}T_{2}T^{k-1-j}_{3}\\\ \bigg{(}\displaystyle\sum_{0\leq
j\leq
k-1}T^{j}_{1}T_{2}T^{k-1-j}_{3}\bigg{)}^{*}DT^{k}_{1}&\bigg{(}\displaystyle\sum_{0\leq
j\leq k-1}T^{j}_{1}T_{2}T^{k-1-j}_{3}\bigg{)}^{*}D\sum_{0\leq j\leq
k-1}T^{j}_{1}T_{2}T^{k-1-j}_{3}\end{pmatrix},$

where

$D=\sum_{0\leq k\leq m}(-1)^{k}\begin{pmatrix}m\\\
k\end{pmatrix}T_{1}^{*m-k}C_{1}T^{m-k}C_{1}.$

This implies that $T^{*n}\bigg{(}\displaystyle\sum_{0\leq k\leq
m}(-1)^{k}\begin{pmatrix}m\\\ k\end{pmatrix}T^{*m-k}CT^{m-k}C\bigg{)}T^{n}=0$
on $\mathcal{H}=\overline{\mathcal{R}(T^{n})}\oplus\mathcal{N}(T^{*n})$. Thus
$T$ is $n$-quasi-$(m,C)$-isometric operator.

∎

######  Corollary 2.2.

If $T$ is a $n$-quasi-$(m,C)$-isometric operator and ${\mathcal{R}}(T^{n})$ is
dense, then $T$ is a $(m,C)$-isometric operator.

In [11], the authors showed that a power of an $(m,C)$-isometric operator is
again a $(m,C)$-isometric operator. In the following theorem we show that this
remains true for $n$-quasi-$(m,C)$-isometric operators.

######  Theorem 2.3.

Let $C=C_{1}\oplus C_{2}$ be a conjugation on ${\mathcal{H}}$ where $C_{1}$
and $C_{2}$ are conjugation on $\overline{{\mathcal{R}}(T^{n})}$ and
${\mathcal{N}}({T^{\ast}}^{n})$, respectively. If $T$ is a
$n$-quasi-$(m,C)$-isometric operator, then so is $T^{k}$ for every natural
number $k$.

###### Proof.

If ${\mathcal{R}}(T^{n})$ is dense, then $T$ is an $(m,C)$-isometric operator
and so is $T^{k}$ for every positive integer $k$.

If ${\mathcal{R}}(T^{n})$ is not dense. By Theorem 2.1 we write the matrix
representation of $T$ on
${\mathcal{H}}=\overline{{\mathcal{R}}(T^{n})}\oplus{\mathcal{N}}(T^{*n})$ as
follows

$T=\begin{pmatrix}T_{1}&T_{2}\\\ 0&T_{3}\end{pmatrix}\quad\text{ on
}\quad\mathcal{H}=\overline{\mathcal{R}(T^{n})}\oplus\mathcal{N}(T^{*n})$

where $T_{1}$ is an $(m,C_{1})$-isometric operator. By [11, Theorem 2.1],
$T^{k}_{1}$ is an $(m,C_{1})$-isometric operator. Since

$T^{k}=\begin{pmatrix}T^{k}_{1}&\displaystyle\sum_{0\leq j\leq
k-1}T^{j}_{1}T_{2}T^{k-1-j}_{3}\\\
0&T^{k}_{3}\end{pmatrix}\,\;\;\mbox{on}\;\mathcal{H}=\overline{\mathcal{R}(T^{n})}\oplus\mathcal{N}(T^{*n}).$

Thus $T^{k}$ for every natural number $k$ is a $n$-quasi-$(m,C)$-isometric
operator by Theorem 2.1. ∎

######  Remark 2.4.

The converse of Theorem 2.3 in not true in general as shown in the following
example.

######  Example 2.5.

Let $C$ be a conjugation on $\mathbb{C}^{2}$ defined by
$C(x_{1},x_{2})=(\overline{x_{2}},-\overline{x_{1}})$ and consider the
operator matrix $T=\left(\begin{array}[]{cc}-1&-1\\\ 3&2\\\
\end{array}\right)$ on $\mathbb{C}^{2}$. A simple calculation shows that
$T^{\ast 3}\bigg{(}T^{*3}CT^{3}C-I\bigg{)}T^{3}=0$ and
$T^{*}\bigg{(}T^{*}CTC-I\bigg{)}T\not=0$. So, we obtain that $T^{3}$ is a
quasi-$(1,C)$-isometric operator, but $T$ it is not a quasi- $(1,C)$-isometric
operator.

It was observed that every $(m,C)$-isometric operator is an $(k,C))$-isometric
operator for every integer $k\geq m.$ In the following proposition we show
that this remains true for $n$-quasi-$(m,C)$-isometric operator.

######  Proposition 2.6.

Let $T\in{\mathcal{B}}({\mathcal{H}})$ and let $C=C_{1}\oplus C_{2}$ be a
conjugation on ${\mathcal{H}}$ where $C_{1}$ and $C_{2}$ are conjugation on
$\overline{{\mathcal{R}}(T^{n})}$ and ${\mathcal{N}}({T^{\ast}}^{n})$,
respectively. If $T$ is an $n$-quasi-$(m,C)$-isometric operator, then $T$ is
an $l$-quasi-$(k,C)$-isometric operator for every positive integers $k\geq m$
and $l\geq n$.

###### Proof.

If ${\mathcal{R}}(T^{n})$ is dense, then $T$ is an $(m,C)$-isometric operator
and hence $T$ is an $(k,C)$-isometric operator for every positive integer
$k\geq m$.

If ${\mathcal{R}}(T^{n})$ is not dense, by Theorem 2.1 we write the matrix
representation of T on
${\mathcal{H}}=\overline{{\mathcal{R}}(T^{n})}\oplus{\mathcal{N}}(T^{*n})$ as
follows $T=\left(\begin{array}[]{ccc}T_{1}&T_{2}\\\ 0&T_{3}\end{array}\right)$
where $T_{1}=T_{/\overline{{\mathcal{R}}(T^{n})}}$ is an $(m,C_{1})$-isometric
operator and $T_{3}^{n}=0$. Obviously that $T_{1}$ is an $(k,C_{1})$-isometric
operator for every integer $k\geq m$. The conclusion follows from the
statement $(2)$ of Theorem 2.1.

∎

For an operator $T\in{\mathcal{B}}({\mathcal{H}})$ and a conjugation $C$, the
operator $\Lambda_{m}(T)$ is define by

$\Lambda_{m}(T):=\sum_{0\leq k\leq m}(-1)^{k}\binom{m}{k}T^{*m-k}CT^{m-k}C.$

Then $T$ is an $(m,C)$-isometric operator if and only if $\Lambda_{m}(T)=0.$

The following lemma gives another condition for which an
$n$-quasi-$(m,C)$-isometric operator became an $n$-quasi-$(k,C)$-isometric
operator for $k\geq m$.

######  Lemma 2.7.

Let $T\in{\mathcal{B}}({\mathcal{H}})$ be an $n$-quasi-$(m,C)$-isometric
operator where $C$ is a conjugation on ${\mathcal{H}}$. It $T(CTC)=(CTC)T$,
then $T$ is an $n$-quasi-$(k,C)$-isometric operator for every positive integer
$k\geq m$.

###### Proof.

It is well known that
$\Lambda_{m+1}(T)=T^{*}\Lambda_{m}(T)(CTC)-\Lambda_{m}(T)$ ([11]). Under the
assumptions that $T$ is an $n$-quasi-$(m,C)$-isometric operator and satisfies
$T(CTC)=(CTC)T$, it follows

$T^{*n}\Lambda_{m+1}(T)T^{n}=T^{*n+1}\Lambda_{m}(T)T^{n}(CTC)-T^{*n}\Lambda_{m}(T)T^{n}=0.$

Therefore $T$ is an $n$-quasi-$(m+1,C)$-isometric operator. ∎

Let $T\in{\mathcal{B}}({\mathcal{H}})$. Denote by $r(T)$ the spectral radius
of $T$, that is,
$r(T)=\max\\{\;|\lambda|:\lambda\in\sigma(T)\;\\}.$ We say that T is normaloid
if $r(T)=\|T\|$.

######  Theorem 2.8.

Let $C=C_{1}\oplus C_{2}$ be a conjugation on ${\mathcal{H}}$ where $C_{1}$
and $C_{2}$ are conjugation on $\overline{{\mathcal{R}}(T^{n})}$ and
${\mathcal{N}}(T^{*n})$ respectively. Let $T\in{\mathcal{B}}({\mathcal{H}})$
be an $n$-quasi-$(m,C)$\- isometric operator. Assume that $T$ is power bounded
and $T_{1}=T_{/{\overline{{\mathcal{R}}(T^{n})}}}$ satisfies
$T_{1}C_{1}T_{1}C_{1}-I$ is normaloid, then $T$ is an
$n$-quasi-$(1,C)$-isometric operator.

###### Proof.

We know that $T$ admits the following matrix representation
$T=\left(\begin{array}[]{cc}T_{1}&T_{2}\\\ 0&T_{3}\\\ \end{array}\right)$ on
${\mathcal{H}}=\overline{{\mathcal{R}}(T^{n})}\oplus{\mathcal{N}}(T^{*n}).$
Since $T$ is an $n$-quasi-$(m,C)$-isometric operator, it follows in view of
Theorem 2.1 that $T_{1}$ is an $(m,C_{1})$-isometric operator and
$T_{3}^{n}=0$. Furthermore $T$ is power bounded then it is easy that $T_{1}$
is power bounded and satisfies $T_{1}C_{1}T_{1}C_{1}-I$ is normaloid. By
applying [11, Theorem 3.1] we obtain that $T_{1}$ is an $(1,C_{1})$-isometric
operator. According to Theorem 2.1 we can deduce that $T$ is an
$n$-quasi-$(1,C)$-isometric operator. Thus we complete the proof. ∎

######  Lemma 2.9.

([17, Lemma 3.15]) If $(a_{j})_{j}$ is a sequence of complex numbers and
$r,s,m,l$ are positive integers satisfying

$\sum_{0\leq k\leq m}(-1)^{k}\binom{m}{k}a_{rk+j}=0$ (2.1)

and

$\sum_{0\leq k\leq l}(-1)^{k}\binom{l}{k}a_{sk+j}=0$ (2.2)

for all $j\geq 0$,then

$\sum_{0\leq k\leq q}(-1)^{k}\binom{q}{k}a_{pk}=0,$ (2.3)

where $q$ is the greatest common divisor of $r$ and $s$, and $p$ is the
minimum of $m$ and $l$.

In [7] it was proved that if $T^{r}$ is an $m$-isometry and $T^{s}$ is an
$l$-isometry, then $T^{q}$ is a $p$-isometry, where $q$ is the greatest common
divisor of $r$ and $s$, and $p$ is the minimum of $m$ and $l$. In the
following theorem we extend this result as follows

######  Theorem 2.10.

Let $T\in{\mathcal{B}}({\mathcal{H}})$ such that $T^{r}$ is an
$(m,C)$-isometry and $T^{s}$ is an $(l,C)$-isometry, then $T^{q}$ is a
$(p,C)$-isometry, where $q$ is the greatest common divisor of $r$ and $s$, and
$p$ is the minimum of $m$ and $l$.

###### Proof.

$\displaystyle T\;\text{is an}\;(m,C)-\text{isometry}$
$\displaystyle\Leftrightarrow$ $\displaystyle\sum_{0\leq k\leq
m}(-1)^{m-k}\binom{m}{k}T^{*k}CT^{k}C=0$ $\displaystyle\Leftrightarrow$
$\displaystyle\sum_{0\leq k\leq m}(-1)^{m-k}\binom{m}{k}T^{*k}CT^{k}=0$
$\displaystyle\Leftrightarrow$ $\displaystyle\sum_{0\leq k\leq
m}(-1)^{m-k}\binom{m}{k}\langle
CT^{k}\;|\;T^{k}x\rangle=0\;\;\;\forall\;x\in{\mathcal{H}}$

Fix $x\in{\mathcal{H}}$ and denote $a_{j}=\langle CT^{j}x\;|\;T^{j}x\rangle$
for $j=1,2,\cdots.$ As $T^{r}$ is an $(m,C)$-isometric operator the sequence
$(a_{j})_{j\geq 0}$ verifies the recursive equation

$\displaystyle\sum_{0\leq k\leq m}(-1)^{m-k}\binom{m}{k}a_{kr+j}=0,\;\text{for
all}\;j\geq 0.$

Analogously, as $T^{s}$ is an $(l,C)$-isometric operator the sequence
$(a_{j})_{j\geq 0}$ verifies the recursive equation

$\displaystyle\sum_{0\leq k\leq l}(-1)^{l-k}\binom{l}{k}a_{kr+j}=0,\;\;\text{
for all}\;\;j\geq 0.$

Applying similar we obtain that

$\displaystyle\sum_{0\leq k\leq q}(-1)^{q-k}\binom{q}{k}a_{kp}=0,$

where $q$ is the greatest common divisor of $r$ and $s$, and $p$ is the
minimum of $m$ and $l$. Finally $T^{q}$ is an $(p,C)$-isometric operator. ∎

The following corollary is direct consequence of preceding theorem.

######  Corollary 2.11.

Let $T\in{\mathcal{B}}({\mathcal{H}})$ and let $r,s,m,l$ be positive integers.
The following properties hold.

$(1)$ If $T$ is an $(m,C)$-isometric operator such that $T^{s}$ is an
$(1,C)$-isometric

operator, then $T$ is an $(1,C)$-isometric operator.

$(2)$ If $T^{r}$ and $T^{r+1}$ are $(m,C)$-isometries, then so is $T$.

$(3)$ If $T^{r}$ is an $(m,C)$-isometric operator and $T^{r+1}$ is an
$(l,C)$-isometric operator

with $m<l$, then $T$ is an $(m,C)$-isometric operator.

######  Theorem 2.12.

Let $S$ and $T$ be in ${\mathcal{B}}({\mathcal{H}})$ and let $C=C_{1}\oplus
C_{2}$ be a conjugation on ${\mathcal{H}}$where $C_{1}$ and $C_{2}$ are
conjugation on $\overline{{\mathcal{R}}(S^{n})}$ and
${\mathcal{N}}({S^{\ast}}^{n})$, respectively. Assume that $T$ and $S$ are
doubly commuting and $T(CTC)=(CTC)T$, $T(CSC)=S(CTC)$ and
$S^{\ast}CTC=CTCS^{\ast}$. If $T$ is an $n_{1}$-quasi-$(k,C)$-isometric
operator and $S$ is an $n_{2}$-quasi-$(m,C)$-isometric operator, then $TS$ is
a $n^{\prime}=\max\\{\;n_{1},n_{2}\;\\}$-quasi-$(k+m-1,C)$-isometric
operator.-

###### Proof.

Since $TS=ST$, $T(CSC)=S(CTC)$ and $S^{\ast}CTC=CTCS^{\ast}$, it follows that

$[T^{*},S^{*}]=[CTC,CSC]=[CTC,S^{*}]=0.$

By taking into account [16, Lemma 12] we obtain that

$\displaystyle\Lambda_{k+m-1}(TS)=\sum_{0\leq j\leq
k+m-1}\binom{k+m-1}{j}\,{T^{\ast}}^{j}T^{*{n^{\prime}}}\Lambda_{k+m-1-j}(T)T^{n^{\prime}}\,CT^{j}CS^{*{n^{\prime}}}\Lambda_{j}(S)S^{n^{\prime}}.$

Furthermore as $[T,S^{*}]=[T,CSC]=[CTC,S^{*}]=0$ we get

$\displaystyle(TS)^{*n^{\prime}}\,\Lambda_{k+m-1}(TS)\,(TS)^{n^{\prime}}$
$\displaystyle=$ $\displaystyle\sum_{0\leq j\leq
k+m-1}\binom{k+m-1}{j}\,{T^{\ast}}^{j}T^{*{n^{\prime}}}\Lambda_{k+m-1-j}(T)T^{n^{\prime}}\,CT^{j}CS^{*{n^{\prime}}}\Lambda_{j}(S)S^{n^{\prime}}.$

Under the assumption that $S$ is an $n_{2}$-quasi-$(k,C)$-isometric operator,
we get in view of Proposition 2.6
$S^{*{n^{\prime}}}\Lambda_{j}(S)S^{n^{\prime}}=0$ for $j\geq m$ and
$n^{\prime}\geq n_{2}$. On the other hand, if $j\leq m-1$, then $k+m-1-j\geq
k+m-1-m+1=k$ and so $T^{*^{n^{\prime}}}\Lambda_{k+m-1-j}(T)T^{n^{\prime}}=0$
by Lemma 2.7. Hence, $TS$ is a $n^{\prime}$-quasi-$(k+m-1,C)$-isometric
operator. ∎

######  Corollary 2.13.

Let $S$ and $T$ be in ${\mathcal{B}}({\mathcal{H}})$ are doubly commuting. Let
$C=C_{1}\oplus C_{2}$ be a conjugation on ${\mathcal{H}}$ where $C_{1}$ and
$C_{2}$ are conjugation on $\overline{{\mathcal{R}}(S^{n})}$ and
${\mathcal{N}}({S^{\ast}}^{n})$, respectively. Assume that $T(CSC)=(CSC)T$,
$T(CTC)=(CTC)T$ and $S^{\ast}CTC=CTCS^{\ast}$. If $T$ is an
$n_{1}$-quasi-$(k,C)$-isometric operator and $S$ is an
$n_{2}$-quasi-$(m,C)$-isometric operator, then $TS^{q}$ is a
$n^{\prime}=\max\\{n_{1},n_{2}\\}$-quasi-$(k+m-1,C)$-isometric operator for
some positive integer $q$.

###### Proof.

In view of Theorem 2.3 we have that $S^{q}$ is an
$n_{2}$-quasi-$(m,C)$-isometric operator. Moreover $T$ and $S^{q}$ satisfy the
conditions of Theorem 2.10. Hence $TS^{q}$ is a
$n^{\prime}$-quasi-$(k+m-1,C)$-isometric operator. ∎

######  Proposition 2.14.

Let $S$ and $T$ be in ${\mathcal{B}}({\mathcal{H}})$ are doubly commuting.
Assume that $T(CSC)=(CSC)T$, $T(CTC)=(CTC)T$, $S^{\ast}CTC=CTCS^{\ast}$ and
$S(CSC)=(CSC)S.$ If $T$ is an $n_{1}$-quasi-$(k,C)$-isometric operator and $S$
is an $n_{2}$-quasi-$(m,C)$-isometric operator, then $TS$ is a
$n^{\prime}=\max\\{n_{1},n_{2}\\}$-quasi-$(k+m-1,C)$-isometric operator.

###### Proof.

Under the assumptions that $T(CTC)=(CTC)T$ and $S(CSC)=(CSC)S$, it follows
form Lemma 2.7 that $T$ is an $n_{1}$-quasi-$(k+1,C)$-isometric operator and
$S$ is an $n_{2}$-quasi-$(m+1,C)$-isometric operator. By repeating the
reasoning given in the proof of Theorem 2.12 we check that

$\big{(}TS\big{)}^{*n^{\prime}}\Lambda_{m+k-1}(TS)\big{(}TS\big{)}^{n^{\prime}}=0.$

Therefore $TS$ is a $n^{\prime}$-quasi-$(m+k-1)$-isometric operator. ∎

Let ${\mathcal{H}}\overline{\otimes}{\mathcal{H}}$ denote the completion,
endowed with a reasonable uniform cross-norm, of the algebraic tensor product
${\mathcal{H}}\otimes{\mathcal{H}}$ of ${\mathcal{H}}$ and ${\mathcal{H}}$. It
is well known that if $x\in{\mathcal{H}}\overline{\otimes}{\mathcal{H}}$,
there exists linearly independent sets $(u_{1})_{i\in I}$ and $(v_{i})_{i\in
I}$ such that $x=\displaystyle\sum_{i\in I}u_{i}\otimes v_{i}.$ An inner
product on ${\mathcal{H}}\overline{\otimes}{\mathcal{H}}$ is defines as

$\langle x\otimes y\;|\;u\otimes v\rangle:=\langle x\;|\;u\rangle\langle
y\;|\;v\rangle\;\;\text{where}\;\;x,y,u,v\in{\mathcal{H}}.$

We construct an operator $\widetilde{T}$ on the tensor product of Hilbert
spaces. Let $T$ be an operator on ${\mathcal{H}}$ and $S$ be an operator on
${\mathcal{H}}$. We define

$\widetilde{T}:=T\otimes
S:{\mathcal{H}}\overline{\otimes}{\mathcal{H}}\longrightarrow{\mathcal{H}}\overline{\otimes}{\mathcal{H}}\;\;\text{by}$
$\widetilde{T}(x)=\big{(}T\otimes S\big{)}\bigg{(}\sum_{i\in I}u_{i}\otimes
v_{i}\bigg{)}=\sum_{i\in I}T(u_{i})\otimes S(v_{i}).$

In [12, Lemma 4.5], it was proved that if $C$ and $D$ be conjugations on
${\mathcal{H}}$. Then $C\otimes D$ is a conjugation on
${\mathcal{H}}\overline{\otimes}{\mathcal{H}}$.

######  Lemma 2.15.

If $T\in{\mathcal{B}}({\mathcal{H}})$ and let $C$ and $D$ are conjugations on
$\mathcal{H}$ respectively. Then $T$ is an $n$-quasi-$(m,C)$-isometric
operator if and only if then the tensor product $T\otimes I$
$(\text{resp.}I\otimes T)$ is an $n$-quasi-$(m,C\otimes D)$-isometric
operator.

###### Proof.

A straightforward computation gives

$\displaystyle\big{(}T\otimes I\big{)}^{*n}\bigg{(}\sum_{0\leq k\leq
m}(-1)^{m-k}\binom{m}{k}\big{(}T\otimes I\big{)}^{*k}\big{(}C\otimes
D\big{)}\big{(}T\otimes I\big{)}^{k}\big{(}C\otimes
D\big{)}\bigg{)}\big{(}T\otimes I\big{)}^{n}$ $\displaystyle=$ $\displaystyle
T^{*n}\bigg{(}\sum_{0\leq k\leq
m}(-1)^{m-k}\binom{m}{k}T^{*k}CT^{k}C\bigg{)}\otimes I.$

From this we can get that $T$ is an $n$-quasi-$(m,C)$-isometric operator if
and only if $T\otimes I$ is an $n$-quasi-$(m,C\otimes D)$-isometric operator..
∎

As application of Lemma 2.15 and Proposition 2.14, we get the following
theorem.

######  Theorem 2.16.

Let $T$ and $S\in\mathcal{B}(\mathcal{H})$ such that $T$ is an
$n_{1}$-quasi-$(m,C)$-isometric operator and $S$ is an
$n_{2}$-$(k,D)$-isometric operator where $C$ and $D$ are conjugations on
$\mathcal{H}$, respectively. If $T(CTC)=(CTC)T$ and and $S(DSD)=(DSD)$, then
$T\otimes S$ is an $n^{\prime}=\max\\{n_{1},n_{2}\\}$-quasi-$(m+k-1,C\otimes
D)$-isometric operator.

###### Proof.

It is well known that $T\otimes S=\big{(}T\otimes I\big{)}\big{(}I\otimes
S\big{)}=\big{(}I\otimes S\big{)}\big{(}T\otimes I\big{)}$. In view of Lemma
2.15 we have that $T\otimes I$ is an $n_{1}$-quasi-$(m,C\otimes D)$-isometric
operator and $I\otimes S$ is an $n_{2}$-quasi-$(k,C\otimes D)$-isometric
operator. On the other hand, note that $T\otimes I$ and $I\otimes S$ satisfy
all conditions in Proposition 2.14. We conclude that $(T\otimes I)(I\otimes
S)$ is a $n^{\prime}$-quasi-$(m+k-1,C\otimes D)$-isometric operator. Thus we
arrive at the desired conclusion. It needs to m ∎

######  Lemma 2.17.

Let $T,Q\in{\mathcal{B}}({\mathcal{H}})$ such that $TQ=QT$, then for $m\geq 2$

$\Lambda_{m}(T+Q)=\sum_{i+j+k=m}\binom{m}{i,j,k}\big{(}T+Q\big{)}^{*i}Q^{*j}\Lambda_{k}(T)CT^{j}CCQ^{i}C$

where $\displaystyle\binom{m}{i,j,k}=\frac{m!}{i!\;j!\;k!}.$

###### Proof.

The proof follows by similar arguments as in the proof of [24, Lemma 2]. ∎

It was proved in [8, Thoerem 3.1] that if $T\in{\mathcal{B}}({\mathcal{H}})$
is an $m$-isometry and $Q\in{\mathcal{B}}({\mathcal{H}})$ is an nilpotent
operator of order $p$ such that $TQ=QT$, then $T+Q$-is an $(m+2p-2)$-isometry.
In the following theorem we show that this remains true for $(m,C)$-isometric
operators.

######  Theorem 2.18.

Let $T,Q\in{\mathcal{B}}({\mathcal{H}})$. Assume $T$ commutes with $Q$. If $T$
is an $(m,C)$-isometric operator and $Q$ is a nilpotent operator of order $p$.
Then $T+Q$ is an $(m+2p-2,C)$-isometric operator where $C$ is a conjugation on
${\mathcal{H}}$.

###### Proof.

We need to show

$\Lambda_{m+2p-2}\big{(}T+Q\big{)}=0.$

In view of Lemma 2.17 we have

$\Lambda_{m+2p-2}\big{(}T+Q\big{)}=\sum_{i+j+k=m+2p-2}\binom{m+2p-2}{i,j,k}\big{(}T^{*}+Q^{*}\big{)}^{i}Q^{*j}\Lambda_{k}(T)CT^{j}CCQ^{i}C.$

(i) If $\max\\{i,j\\}\geq p$, then $CQ^{i}C=0$ or $Q^{*j}=0.$

(ii) If $\max\\{i,j\\}\leq p-1,$ then $k\geq m$ and hence $\Lambda_{k}(T)=0.$

From (i) and (ii) we get $\Lambda_{m+2p-2}\big{(}T+Q\big{)}=0.$ ∎

In the following theorem we investigate the nilpotent perturbations of an
$n$-quasi-$(m,C)$-isometric operator.

######  Theorem 2.19.

Let $T$ and $Q\in{\mathcal{B}}({\mathcal{H}})$. Assume that $TQ=QT$ commutes,
$TCQC=CQCT$ and $TCTC=CTCT$ where $C$ is a conjugation on ${\mathcal{H}}$. If
$T$ is an $n$-quasi-$(m,C)$-isometric operator and $Q$ is a nilpotent operator
of order $p$. Then $T+Q$ is a $(n+p)$-quasi-$(m+2p-2,C)$-isometric operator.

###### Proof.

We need to show

$\big{(}T+Q\big{)}^{\gamma}\Lambda_{m+2p-2}\big{(}T+Q\big{)}\big{(}T+Q\big{)}^{\gamma}=0\;\text{where}\;\gamma=n+p.$

In view of Lemma 2.17 we have

$\Lambda_{m+2p-2}\big{(}T+Q\big{)}=\sum_{i+j+k=m+2p-2}\binom{m+2p-2}{i,j,k}\big{(}T^{*}+Q^{*}\big{)}^{i}Q^{*j}\Lambda_{k}(T)CT^{j}CCQ^{i}C$

and

$\displaystyle\big{(}T+Q\big{)}^{*\gamma}\Lambda_{m+2p-2}\big{(}T+Q\big{)}\big{(}T+Q\big{)}^{\gamma}$
$\displaystyle=$ $\displaystyle\bigg{(}\sum_{0\leq r\leq
2\gamma}\binom{\gamma}{r}T^{*(\gamma-r)}Q^{*r}\bigg{)}\bigg{(}\sum_{i+j+k=m+2p-2}\binom{m+2p-2}{i,j,k}\big{(}T^{*}+Q^{*}\big{)}^{i}Q^{*j}\Lambda_{k}(T)CT^{j}CCQ^{i}C\bigg{)}$
$\displaystyle\times\bigg{(}\sum_{0\leq s\leq
2\gamma}\binom{\gamma}{s}T^{\gamma-s}Q^{s}\bigg{)}.$

Now observe that if $\max\\{i,j\\}\geq p$, then $CQ^{j}C=0$ or $Q^{i}=0.$ and
hence

$\big{(}T^{*}+Q^{*}\big{)}^{i}Q^{*j}\Lambda_{k}(T)CT^{j}CCQ^{i}C=0.$

However , if $\max\\{i,j\\}\leq p-1$, then $k\geq m$. Using the fact that $T$
is an $n$-quasi-$m$-isometry and $TCTC=CTCT$, we get

$T^{*(n+p-r)}\Lambda_{k}(T)T^{n+p-s}=0\;\;\;\text{for}\;\;r\in\\{\;0,\cdots,p\;\\}\;\;\text{and}\;s\in\\{\;0,\cdots,p\\}$

and

$T^{*(n+p-r)}Q^{*r}\Lambda_{k}(T)T^{n+p-s}Q^{s}=0\;\;\;\text{for}\;\;r\in\\{\;p+1,\cdots,n+p\\}\;\;\text{and}\;s\in\\{\;p+1,\cdots,n+p\\}.$

Combining the above arguments we deduce that

$\big{(}T+Q\big{)}^{n+p}\Lambda_{m+2p-2}\big{(}T+Q\big{)}\big{(}T+Q\big{)}^{n+p}=0.$

Thus $T+Q$ is a $(n+p)$-quasi-$(m+2p-2)$-isometric operator. Therefore the
theorem is proved. ∎

######  Example 2.20.

Let $C$ be a conjugation on $\mathbb{C}^{3}$ defined by
$C(x_{1},x_{2},x_{3})=(\overline{x_{3}},\overline{x_{2}},\overline{x_{1}})$
and consider the operator matrix $T=\left(\begin{array}[]{ccc}1&0&\alpha\\\
0&1&0\\\ 0&0&1\\\ \end{array}\right)$ on $\mathbb{C}^{3}$. Then $T=I+Q$. Since
$Q^{2}=0$, it follows from Theorem 2.19 that $T$ is a
$(n+2)$-quasi-$(m+2,C)$-isometric operator.

## References

  * [1] B. Abdullah T.Le, The structure of $m$-isometric weigted shift operator, Operators and Matrices, vol 10, Number 2 (2016), 319-334.
  * [2] J. Agler and M. Stankus, $m$-Isometric transformations of Hilbert space I, Integral Equations and Operator Theory, 21(1995), 383-429.
  * [3] J.Agler M.Stankus, $m$-Isometric transformations of Hilbert space. $II$. Integral Equ.Oper. Theory 23(1), 1-48 (1995)
  * [4] J.Agler M.Stankus, $m$-Isometric transformations of Hilbert space. $III$. Integral Equ. Oper. Theory 24(4), 379-421 (1996).
  * [5] M.F.Ahmadi, S. Yarmahmoodi and K. Hedayatian, Perturbation of $(m,p)$\- isometries by nilpotent operators and their supercyclicity, Oper. Matrices 11(2017), 381 -387.
  * [6] F. Bayart,$m$-Isometries on Banach spaces, Math. Nachr. 284(2011), 2141 -2147
  * [7] T. Bermúdez, C. D. Mendoza and A. Martinón, Powers of $m$-isometries, Studia Mathematica 208 (3) (2012).
  * [8] T. Bermúdez, A. Martinón, V.Mvller J.A. Noda, Perturbation of $m$-Isometries by Nilpotent Operators,Abstract and Applied Analysis Volume 2014, Article ID 745479, 6 pages.
  * [9] T. Bermúdez, A. Martinón, J.A. Noda, An isometry plus a nilpotent operator is an $m$-isometry. Applications, J. Math. Anal. Appl. 407(2),(2013). 505-512.
  * [10] T. Bermúdez, A. Martinón, J.A. Noda, Products of $m$-isometries, Linear Algebra and its Applications 438 (2013) 80–86.
  * [11] M. Chō, E. Ko and J. E. Lee, On $(m,C)$-Isometric Operators, Complex Anal. Oper. Theory 10 (2016), 1679-1694.
  * [12] M. Chō , J.E. Lee and H. Motoyoshia, On $[m,C]$-Isometric Operators, Filomat 31:7 (2017), 2073 2080.
  * [13] B.P. Duggal, Tensor product of $n$-isometries, Linear Algebra and its Applications 437 (2012),307 -318.
  * [14] S. R. Garcia and M. Putinar, Complex symmetric operators and applications, Trans. Amer. Math. Soc. 358(2006), 1285-1315.
  * [15] S.R. Garcia, E. Prodan and M. Putinar, Mathematical and physical aspects of complex symmetric operators, J. Phys. A: Math. Theory 47(2014) 353001 (54pp).
  * [16] C.Gu, Structures of left $n$-invertible operators and their applications, Studia Mathemaica 226 (3) (2015).
  * [17] K. Hedayatian and A. M. Moghaddam, Some proprties of the spherical $m$-isometries,J. Operator 79:1(2018), 55 -77.
  * [18] S. Mecheri and T. Prasad, On $n$-quasi-$m$-isometric operators, Asian-European Journal of Mathematics 9 (2016), (8 pages).
  * [19] S. Mecheri and S. M. Patel, On quasi-$2$-isometric operators, Linear and Multlinear Algebra.( 2017), https://doi.org/10.1080/03081087.2017.1335283.
  * [20] S. M. Patel, $2$-isometric operators, Glas. Mat. 37 (57) (2002), 141–145.
  * [21] S. M. Patel, A note on quasi-isometries, Glas. Mat. 35 (55) (2000) 307–312.
  * [22] S. M. Patel, A note on quasi-isometries II, Glas. Mat. 38 (58) (2003) 111-120.
  * [23] O. A. M. Sid Ahmed , M. Chō and J. E. Lee, On $n$-quasi-$(m,C)$-isomtric operators, Linear and Multilinear Algebra, https://doi.org/10.1080/03081087.2018.1524437.
  * [24] O. A. M. Sid Ahmed , M. Chō and J. E. Lee,On $(m,C)$-Isometric Commuting Tuples of Operators on a Hilbert Space, Results Math (2018) 73:51


Stochastic Optimization with Constraints:
A Non-asymptotic Instance-Dependent Analysis

Koulik Khamaru⋄
---
Department of Statistics⋄
---
Rutgers University

###### Abstract

We consider the problem of stochastic convex optimization under convex
constraints. We analyze the behavior of a natural variance reduced proximal
gradient (VRPG) algorithm for this problem. Our main result is a non-
asymptotic guarantee for VRPG algorithm. Contrary to minimax worst case
guarantees, our result is instance-dependent in nature. This means that our
guarantee captures the complexity of the loss function, the variability of the
noise, and the geometry of the constraint set. We show that the non-asymptotic
performance of the VRPG algorithm is governed by the scaled distance (scaled
by $\sqrt{N}$) between the solutions of the given problem and that of a
certain small perturbation of the given problem — both solved under the given
convex constraints; here, $N$ denotes the number of samples. Leveraging a
well-established connection between local minimax lower bounds and solutions
to perturbed problems, we show that as $N\rightarrow\infty$, the VRPG
algorithm achieves the renowned local minimax lower bound by Hàjek and Le Cam
up to universal constants and a logarithmic factor of the sample size.

##  1 Introduction

In this paper, we study the problem of stochastic convex optimization problem
under constraints. Concretely, we are interested in problems of the form

$\displaystyle\min_{x\in\mathcal{X}}\;f(x)$
$\displaystyle\equiv{\mathbb{E}}_{z\sim\mathbb{P}_{0}}f(x,z)$
$\displaystyle\qquad\text{where}\;\;\mathcal{X}$
$\displaystyle=\left\\{x\in{}^{d}\;:\;g_{i}(x)\leq
0\;\;\text{for}\;\;i=1,\ldots,m\right\\}.$ (1)

Here, $g_{i}$ are convex and twice continuously differentiable functions, and
the function $f$ is twice continuously differentiable, $\mu$-strongly convex
and $\mathrm{L}$-smooth for some $0<\mu\leq\mathrm{L}$. Given $N$ iid samples
$z_{1},z_{2},\ldots,z_{N}\sim\mathbb{P}_{0}$, we are interested in designing
computationally efficient algorithm that outputs an approximate solution of
the problem (1).

Constraint stochastic optimization problems of the form (1) are ubiquitous in
statistics and optimization, and the study of these problems dates backs to
more than 70 years. There are two standard strategies for solving the problem
(1): (a) M-estimators under constraints (b) Stochastic approximation methods.

###  1.1 M-estimators under constraints:

The first approach, popular in the statistics community, provides an
approximate solution of problem (1) by solving a constrained M-estimation
problem. Given $N$ iid samples $z_{1},z_{2},\ldots,z_{N}\sim\mathbb{P}_{0}$,
one outputs the solution of the following M-estimation problem

$\displaystyle\min_{x\in\mathcal{X}}\frac{1}{N}\sum_{i=1}^{N}f(x,z_{i}).$ (2)

The asymptotic behavior of the above problem is well understood by now. The
study of this problem has its roots in the works of Dupacoka and Wets [6],
Shapiro [19], and King and Rockafellar [14]. In a recent work Duchi and Ruan
[5] and Davis et al. [2] show that the solution of the solution obtained from
(2) is asymptotically locally minimax optimal in the sense of Hájek and Le Cam
[15, 7, 16, 20, 23]. In simple words, in a local shrinking neighborhood
(shrinking as the number of the sample size increases) of the problem, there
is no other algorithm that performs better than the solution of the problem
(2). Contrary to global minimax bounds which capture the difficulty of the
hardest problem in the problem class, the local minimax lower bounds from [5]
captures a more finer notion of difficulty of the specific problem at hand.

###  1.2 Stochastic approximation methods:

While the asymptotic performance of constrained M-estimator problems are
optimal asymptotically, one drawback of such methods is that they may be
expensive to compute. This motivated people to design computationally
attractive stochastic approximation schemes that converge to the solution of
problem (1).

##### Suboptimality of dual-averaging:

The problem of stochastic optimization under constraints has been has been
studied in the optimization community for some time; see the work of and King
[13]. The behavior stochastic algorithms are more nuanced due to presence of
constraint set $\mathcal{X}$. For instance, Duchi and Ruan [5] show that
stochastic approximation with dual averaging [17] — a natural algorithm in
this case — is not always optimal. Concretely, in Section 5.2 of their paper
Duchi and Ruan argue that the dual averaging algorithm is optimal when the the
constraint set $\mathcal{X}$ consists of linear constraints, but the same
algorithm is sub-optimal when $\mathcal{X}$ contains non-linear constraints.

##### Asymptotic optimality via Polyak-Ruppert averaging:

In a surprising new result, Davis, Drusvyatskiy, and Jiang [2] show that
vanilla stochastic approximation algorithm when combined with a Polyak-Ruppert
(PR) averaging step is asymptotically local-minimax optimal. Staring with an
$x_{1}\in\mathcal{X}$, the updates of the PR-averaged stochastic approximation
as obtained as follows:

$\displaystyle\texttt{(SA-step)}\qquad x_{k+1}$
$\displaystyle=\text{Proj}_{\mathcal{X}}\left(x_{k}-\alpha_{k}\cdot\nabla
f(x_{k},z_{k})\right).$ $\displaystyle\texttt{(PR-
averaging)}\qquad\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{k+1}$
$\displaystyle=\frac{1}{k+1}\sum_{\ell=1}^{k+1}x_{\ell}$

Davis et al. [2] argue that under some mild assumptions of the loss function
$f$ and the constraint set $\mathcal{X}$, the scaled difference
$\sqrt{N}(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{N}-x_{\mathbb{P}_{0}}^{\star})$
converges to a normal distribution with the optimal covariance matrix. Here,
$x_{\mathbb{P}_{0}}^{\star}$ is the (unique) solution to the problem (1), and
$N$ is the number of samples used (or the number of steps in the algorithm).
The authors also argue that $\sqrt{N}{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{N}-x_{\mathbb{P}_{0}}^{\star}\|_{2}$
matches a local minimax lower bound suggested by the Hájek Le Cam theory [7,
15, 5].

###  1.3 Non-asymptotic bounds

While the asymptotic performances of both M-estimator and stochastic
approximation algorithms are quite well understood, not much is known about
the non-asymptotic instance-dependent performance of either methods for the
problem (1) when constraint set $\mathcal{X}\neq{}^{d}$. In a recent work [4],
the authors provide a non-asymptotic lower bounds for the problem (1) under
some growth condition on an appropriate modulus of continuity. In particular,
motivated by the work of [1], the authors in the work [4] construct a non-
asymptotic local minimax lower bound for problem (1) by comparing problem (1)
with its hardest alternative in a local shrinking neighborhood (shrinking with
sample size $N$) of the problem. The authors also argue that in one dimension,
a grid search based algorithm attains this non-asymptotic local lower bound.
Unfortunately, in higher dimensions, grid search algorithms become
computationally prohibitive. Thus it is not clear whether such results can be
extended to higher dimension.

###  1.4 Contribution and organization

Motivated from the recent success of instance dependent understanding of
stochastic approximation algorithms, our goal in this paper is to have a non-
asymptotic understanding of stochastic approximation algorithms in a instance-
dependent sense. Put simply, we would like to derive non-asymptotic upper-
bounds that reflect the structure of the loss function $f$, the variability of
the noise, and the structure of the constraint set $\mathcal{X}$. In Section
2, we motivate non-asymptotic instance dependence benchmark for the problem 1.
This benchmark is motivated from the well-studied connection between the local
minimax lower bounds and solutions of perturbed problem [5, 2]. Section 3 is
devoted to a devoted to a detailed description of the problem that we
consider. In Section 4 we state the variance reduced proximal gradient (VRPG)
algorithm that we study (see Algorithm 1), and in Theorem 1, we provide non-
asymptotic instance-dependent upper bound for the VRPG algorithm. Finally, we
argue that VRPG is asymptotically locally minimax optimal up to a factor which
is logarithmic in the number of sample size $N$ and universal constants.

##  2 An instance-dependent local minimax lower bound

We start with a discussion on the statistical limit of the constrained
stochastic optimization problem (1). Our lower bounds are motivated from the
local minimax theory of Le Cam and Hájek [15, 7]. Contrary to ,standard
minimax guarantees — which capture the difficulty of the worst case problem in
a problem class, local minimax guarantees captures a problem specific
difficulty of the problems. In other words, these lower bounds are adaptive to
the structure of the function $f$ as well as the constrained set $\mathcal{X}$
in problem (1).

The idea is to consider a small neighborhood of the given problem
$\mathcal{P}_{0}$ — shrinking with the sample size — and consider worst case
difficulty in this local neighborhood. Intuitively, in a small local
neighborhood of a given problem $\mathcal{P}_{0}$, problem difficulty does not
change drastically. Consequently, the worst case difficulty in the local
neighborhood of the problem $\mathcal{P}_{0}$ is a finer notion of difficulty
of problem $\mathcal{P}_{0}$ compared to the worst case problem difficulty.

Focusing on our problem (1), let $\mathbb{P}$ is any other distribution over
the randomness $z$ such that $\mathrm{KL}(\mathbb{P},\mathbb{P}_{0})$ is small
to ensure

$\displaystyle f_{\mathbb{P}}={\mathbb{E}}_{z\in\mathbb{P}}f(x,z)\quad\text{is
strongly convex}.$ (3)

Let $x_{\mathbb{P}}^{\star}$ the unique solution to the perturbed problem:

$\displaystyle
x_{\mathbb{P}}^{\star}=\arg\min_{x\in\mathcal{X}}\;\left\\{f_{\mathbb{P}}(x)\equiv{\mathbb{E}}_{z\sim\mathbb{P}}f(x,z)\right\\}.\qquad$
(4)

Given access to $N$ iid samples $z_{1},\ldots,z_{N}$ from the distribution
$\mathbb{P}$, the following result from the paper [5, Corollary 1]
characterizes the local minimax lower bound for the problem (1).

######  Proposition 1 (Informal).

Let $\widehat{x}_{N}$ be the output of _any_ algorithm with access to $N$ iid
samples $z_{1},\ldots,z_{N}$. Then under suitable smoothness condition on the
function $f$ and the constraint functions $g_{i}^{\prime}s$ in problem (1), we
have the following asymptotic lower bound:
$\displaystyle\liminf_{c\rightarrow\infty}\liminf_{N\rightarrow\infty}\sup_{\mathbb{P}:\mathrm{KL}(\mathbb{P}||\mathbb{P}_{0})\leq
c/N}{\mathbb{E}}_{\mathbb{P}^{N}}\left[\|\sqrt{N}(\widehat{x}_{N}-x_{\mathbb{P}}^{\star})\|_{2}^{2}\right]\geq{\mathbb{E}}\|Z\|_{2}^{2}$
(5) where
$Z\sim\mathcal{N}(0,\mathrm{P}_{\mathcal{T}}H^{\star}\mathrm{P}_{\mathcal{T}}\Sigma^{\star}\mathrm{P}_{\mathcal{T}}H^{\star}\mathrm{P}_{\mathcal{T}})$.

A few comments regarding the last lower bound are in order. The lower bound
depends on the property of three matrices $\mathrm{P}_{\mathcal{T}},H^{\star}$
and $\Sigma^{\star}$. Let us understand these three matrices one at a time. We
use $\mathcal{L}(\cdot,\cdot)$ as the Lagrangian of the problem (1), i.e.,

$\displaystyle\mathcal{L}(x,\beta)=f(x)+\sum_{i=1}^{m}\beta_{i}g_{i}(x).$ (6)

  1. (a)

The matrix $H^{\star}$ in the bound (5) is the hessian of the Hessian of the
Lagrangian (6) at optima $x_{\mathbb{P}_{0}}^{\star}$

$\displaystyle
H^{\star}=\nabla^{2}\mathcal{L}(x_{\mathbb{P}_{0}}^{\star},\beta^{\star})=\nabla^{2}f(x_{\mathbb{P}_{0}}^{\star})+\sum_{i=1}^{m}\beta_{i}^{\star}\nabla^{2}g_{i}(x_{\mathbb{P}_{0}}^{\star})$
(7)

where $\beta_{i}^{\star}\geq 0$ with $\beta_{i}^{\star}=0$ when $\nabla
g_{i}(x_{\mathbb{P}_{0}}^{\star})<0$ are unique scalars satisfying

$\displaystyle\nabla
f(x_{\mathbb{P}_{0}}^{\star})+\sum_{i=1}^{m}\beta_{i}^{\star}g_{(}x_{\mathbb{P}_{0}}^{\star})=0$

See the paper [5, Section 2], and the book [8, Chapter VII.2] for more a more
detailed discussion on existence of such $\beta^{\star}$. Put simply, the
Hessian matrix $H^{\star}$ captures the structures of the loss function $f$
and the constraint-set $\mathcal{X}$ near optima $x_{\mathbb{P}_{0}}^{\star}$.

  2. (b)

The matrix $\Sigma^{\star}=\mathrm{Cov}_{z\in\mathbb{P}_{0}}(\nabla
f(x_{\mathbb{P}_{0}}^{\star},z))$ is the covariance matrix of the function
gradient evaluated at the optima $x_{\mathbb{P}_{0}}^{\star}$. This term
captures the noise present in the problem (1).

  3. (c)

Let $\mathcal{T}_{\mathcal{X}}(x_{\mathbb{P}_{0}}^{\star})$ denote the
critical tangent cone at $x_{\mathbb{P}_{0}}^{\star}$:

$\displaystyle\mathcal{T}_{\mathcal{X}}(x_{\mathbb{P}_{0}}^{\star})$
$\displaystyle:=\left\\{w\in{}^{d}\;:\;\nabla
g_{i}(x_{\mathbb{P}_{0}}^{\star})^{\top}w=0\;\;\text{for
all}\;\;i\;\;\text{with}\;\;g_{i}(x_{\mathbb{P}_{0}}^{\star})=0\right\\}$
$\displaystyle=\cap_{i=1}^{m_{0}}\left\\{w\in{}^{d}\;:\;w\in{}^{d}\;:\;\nabla
g_{i}(x_{\mathbb{P}_{0}}^{\star})^{\top}w=0\right\\}$

Here, we assumed, without loss of generality, that the first $m_{0}$
constraints $\left\\{g_{i}(x)\leq 0\right\\}$ are active at the optima
$x_{\mathbb{P}_{0}}^{\star}$. The matrix $\mathrm{P}_{\mathcal{T}}$ denote the
projection matrix to this tangent cone
$\mathcal{T}_{\mathcal{X}}(x_{\mathbb{P}_{0}}^{\star})$. This term captures
the structure of the constraint set $\mathcal{X}$ near the optima
$x_{\mathbb{P}_{0}}^{\star}$.

The lower bound from Proposition 1 provides an asymptotic lower bound for any
procedure, and it is not immediately clear what could be a non-asymptotic
benchmark. To motivate our non-asymptotic benchmark we discuss an alternative
description of the lower bound in Proposition 1. We do so by connecting the
lower bound (5) with solutions of a class of perturbed problems obtained from
the original problem (5).

###  2.1 Perturbed problems and connections to local minimax lower bounds

Before we discuss the connection between perturbations of the problem (1) and
the local minimax lower bound (5), it is helpful to first understand which
distributions $\mathbb{P}$ with $\mathrm{KL}(\mathbb{P}||\mathbb{P}_{0})$
achieve the lower bound in Proposition 1. It turns out that the lower bound is
achieved by considering the _tilted_ distribution:

$\displaystyle d\mathbb{P}_{u}(z)$ $\displaystyle=\frac{1+\left\langle
u,\nabla f(x_{\mathbb{P}_{0}}^{\star},z)-\nabla
f(x_{\mathbb{P}_{0}}^{\star})\right\rangle}{C_{0}}\cdot
d\mathbb{P}_{0}(z)\quad\text{where}$ $\displaystyle\quad C_{0}$
$\displaystyle=1+\int\left\langle u,\nabla
f(x_{\mathbb{P}_{0}}^{\star},z)-\nabla
f(x_{\mathbb{P}_{0}}^{\star})\right\rangle\cdot d\mathbb{P}_{0}(z).$ (8)

and taking supremum over the set $\|u\|_{2}\leq c/\sqrt{N}$; (see Theorem 1 in
the paper [5] for additional details). Put simply,

_The hardest alternative to distribution $\mathbb{P}_{0}$ is obtained when we
_tilt_ the distribution $\mathbb{P}_{0}$ in the direction $[\nabla
f(x_{\mathbb{P}_{0}}^{\star},z)-\nabla f(x_{\mathbb{P}_{0}}^{\star})]$ — the
noise present in the sample function gradient_.

Any distribution $\mathbb{P}_{u}$ of the form (2.1) produces a function
$f_{u}:={\mathbb{E}}_{z\in\mathbb{P}_{u}}f(x,z)$ which is a linear
perturbation to the original function $f$. The study of the change in the
optimal solution of the optimization problem (1) and its _tilted_ counterpart
$f_{u}$ is related to the study of tilt-stability [18] in variational
analysis. The idea of tilt-stability has also been very influential in
developing asymptotic results for the problem (1); see for instance the works
by Shapiro [19]. These ideas are also building blocks for deriving local
asymptotic lower bounds [5, 2].

####  2.1.1 A particular perturbation of interest

A particular perturbation of interest is the following. Given $N$ iid samples
$z_{1},\ldots,z_{N}$, we define a tilted function $f_{N}$ as

$\displaystyle f_{N}(x)=f(x)+\left\langle x,\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(x_{\mathbb{P}_{0}}^{\star})-\nabla
f(x_{\mathbb{P}_{0}}^{\star})\right\rangle\quad\text{where}\quad\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(x_{\mathbb{P}_{0}}^{\star})=\frac{1}{N}\sum_{i=1}^{N}\nabla
f(x_{\mathbb{P}_{0}}^{\star},z_{i})$ $\displaystyle
x_{N}^{\star}=\arg\max_{x\in\mathcal{X}}f_{N}(x).$ (9)

This particular perturbation (9) is motivated from the behavior of the
classical M-estimator. Indeed, let

$\displaystyle\text{(M-estimator:)}\qquad\qquad\widehat{x}^{M}:=\arg\min_{x\in\mathcal{X}}\left\\{\widehat{f}_{N}(x):=\frac{1}{N}\sum_{i=1}^{N}f(x;z_{i})\right\\},\qquad\qquad\qquad\qquad\qquad$

Then under some smoothness assumption on the function $f$, we have

$\displaystyle\nabla\widehat{f}_{N}(x)=\nabla
f_{N}(x)+o_{p}(1)\cdot\left(x-x_{\mathbb{P}_{0}}^{\star}\right)$

The above relation ensures that the the asymptotic behavior of the M-estimator
$\widehat{x}^{M}$ is same as that of $x_{N}^{\star}$ from (9). See Section 2.3
from the paper [5] and also the paper [19] for details. The perturbed problem
$f_{N}$ from (9) lies at the heart of variance reduced stochastic optimization
algorithms [9, 22, 10, 11]. We are now ready to connect the perturbed problem
(9) with the local minimax lower bound (5), and this connection forms the
basis of the non-asymptotic benchmark that we consider.

Intuitively, as $N$ increases, the function $f_{N}$ becomes increasingly close
to $f$, and consequently, $x_{N}^{\star}$ becomes close to
$x_{\mathbb{P}_{0}}^{\star}$. Proposition 1 from the paper [5] formalizes this
intuition:

$\displaystyle
x_{N}^{\star}=x_{\mathbb{P}_{0}}^{\star}+\mathrm{P}_{\mathcal{T}}H^{\star}\mathrm{P}_{\mathcal{T}}v+o(\|v\|)\quad\text{where}\quad
v=\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(x_{\mathbb{P}_{0}}^{\star})-\nabla
f(x_{\mathbb{P}_{0}}^{\star}).$

Also, see the book by [3] for a detailed discussion. Now, scaling the
difference between $x_{N}^{\star}$ and $x_{\mathbb{P}_{0}}^{\star}$ by
$\sqrt{N}$ we obtain the following result

Under the assumptions of Proposition 1
$\displaystyle\lim_{N\rightarrow\infty}\sqrt{N}(x_{N}^{\star}-x_{\mathbb{P}_{0}}^{\star})\stackrel{{\scriptstyle
d}}{{\rightarrow}}\mathcal{N}(0,\mathrm{P}_{\mathcal{T}}H^{\star}\mathrm{P}_{\mathcal{T}}\Sigma^{\star}\mathrm{P}_{\mathcal{T}}H^{\star}\mathrm{P}_{\mathcal{T}})$
(10) Combining the statement (10) and Proposition (1) we observe that the
local minimax lower bound for the problem (1) is characterized by
$\sqrt{N}(x_{N}^{\star}-x_{\mathbb{P}_{0}}^{\star})$ — the (scaled) difference
between the optimal solutions of the function $f$ and its perturbed
counterpart $f_{N}$.

###  2.2 A non-asymptotic instance-dependent benchmark:

Motivated from the discussion in the last two sections, we use $\delta_{N}$ as
the scaled difference between $x_{N}^{\star}$ and
$x_{\mathbb{P}_{0}}^{\star}$:

$\displaystyle\delta^{2}(N):=N\cdot{\mathbb{E}}\|x_{N}^{\star}-x_{\mathbb{P}_{0}}^{\star}\|_{2}^{2}$
(11)

Here, $x_{N}^{\star}$ and $x_{\mathbb{P}_{0}}^{\star}$ are defined in
equations (9) and (4) respectively. A few comments regarding the benchmark
$\delta^{2}(N)$ are in order.

  1. (a)

The benchmark $\delta^{2}(N)$ is non-asymptotic in nature as it depends on
number of samples available.

  2. (b)

The perturbed function $f_{N}$ depends on the randomness noise present in the
problem. Consequently, the benchmark $\delta^{2}(N)$ captures the noise in the
problem.

  3. (c)

The benchmark $\delta^{2}(N)$ depends on the constraint-set $\mathcal{X}$
through $x_{N}^{\star}$ and $x_{\mathbb{P}_{0}}^{\star}$.

In the rest of the paper, our goal is the following:

Can we design an algorithm $\mathcal{A}$ such that given $N$ samples, the
algorithm outputs $\widehat{x}_{\mathcal{A}}$ with
$\displaystyle{\mathbb{E}}\|\widehat{x}_{\mathcal{A}}-x_{\mathbb{P}_{0}}^{\star}\|^{2}\lesssim\frac{\delta^{2}(N)}{N}\qquad\text{for
all}\;\;N.$ (12) The symbol $\lesssim$ above bound indicate that the above
inequality holds up to some universal constants and logarithmic factors.

##  3 Problem setup

While our discussions so far is motivated from the constraint optimization
problem (1), the ideas used to develop our algorithm also applies to a more
general class of problems. In particular, we consider problems of the
following form:

$\displaystyle\min_{x}\left\\{{\mathbb{E}}_{z\in\mathbb{P}_{0}}f(x,z)+\mathrm{R}(x)\right\\}$
(13)

Here, $\mathrm{R}(x)$ is a known penalty function, which is assumed to be
convex, proper and lower semi-continuous. The constraint optimization problem
(1) is a special case of problem (13) when we take
$\mathrm{R}(x)=1_{x\in\mathcal{X}}$ — the indicator function of the convex set
$\mathcal{X}$. Throughout, we assume the following structural assumptions on
the functions $f(\cdot,\cdot)$ and $\mathrm{R}$.

### Assumptions

  1. A1.

The loss-function $f(x)={\mathbb{E}}_{z\sim\mathbb{P}_{0}}f(x,z)$ is
$\mu$-strongly convex and $\mathrm{L}$-smooth, for some
$0<\mu\leq\mathrm{L}<\infty$.

  2. A2.

The penalty function $\mathrm{R}$ is a proper, convex and lower semi-
continuous function. We assume that the function $\mathrm{R}$ is known.

  3. A3.

The function $f(\cdot,\cdot)$ is continuously differentiable in its first
argument, and the gradient with respect to $x$, denoted as $\nabla f(x,z)$, is
$\mathrm{L}$ Lipschitz continuous in its first argument, i.e.,

$\displaystyle\|\nabla f(x,z)-\nabla
f(y,z)\|_{2}\leq\mathrm{L}\|x-y\|_{2}\quad\text{for all}\;\;z.$

#### Instance-dependent benchmark:

Following the discussion of Section 2, let $x_{\mathbb{P}_{0}}^{\star}$ be the
_unique_ solution to the problem (13), i.e.,

$\displaystyle
x_{\mathbb{P}_{0}}^{\star}=\arg\min_{x}\left\\{{\mathbb{E}}_{z\in\mathbb{P}_{0}}f(x,z)+\mathrm{R}(x)\right\\}$
(14)

Given access to $N$ iid samples $z_{1},\ldots,z_{N}$ from $\mathbb{P}_{0}$, we
deine the perturbed function $f_{N}$ and solution $x_{N}^{\star}$ as follows.

$\displaystyle f_{N}(x)=f(x)+\left\langle x,\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(x_{\mathbb{P}_{0}}^{\star})-\nabla
f(x_{\mathbb{P}_{0}}^{\star})\right\rangle\quad\text{where}\quad\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(x_{\mathbb{P}_{0}}^{\star})=\frac{1}{N}\sum_{i=1}^{N}\nabla
f(x_{\mathbb{P}_{0}}^{\star},z_{i})$ $\displaystyle
x_{N}^{\star}=\arg\min_{x}\left\\{f_{N}(x)+\mathrm{R}(x)\right\\}.$ (15)

Note that the function $f_{N}$ is strongly convex by construction, and as a
result the solution $x_{N}^{\star}$ is unique. The benchmark $\delta^{2}(N)$
is again defined as the scaled difference square-difference between
$x_{N}^{\star}$ and $x_{\mathbb{P}_{0}}^{\star}$.

$\displaystyle\delta^{2}(N):=N\cdot{\mathbb{E}}\|x_{N}^{\star}-x_{\mathbb{P}_{0}}^{\star}\|_{2}^{2}$
(16)

##  4 Main results

This section is devoted to the description of our algorithm and its
performance guarantees. In Section 4.1, we first describe our variance reduced
algorithm 1, and discuss the intuition behind the algorithm. In Section 4.2,
we provide non-asymptotic guarantees for the output of Algorithm 1.

###  4.1 Variance-reduced projected stochastic gradient

Our proposed algorithm is a variance reduced stochastic projected gradient
descent algorithm and is stated in Algorithm 1. Just like standard variance
reduction schemes [9] our algorithm proceeds in epochs.

  1. (a)

At the beginning of epoch, we create an approximation of the true constraint
optimization problem (13).

  2. (b)

Within each epoch, we run a proximal stochastic gradient algorithm on the
approximate problem constructed step (a).

Concretely, at epoch $m$ we start with an estimate $\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m}$ of the true minimizer
$x_{\mathbb{P}_{0}}^{\star}$ of the problem (13), and $T$ iid sample
$\\{z_{1},\ldots,z_{T}\\}$ samples from the distribution $\mathbb{P}_{0}$, we
construct a modified estimate of gradient as follows

$\displaystyle\widetilde{\nabla}f(x,z):=\nabla
f(x,z)+\left\\{\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m})-\nabla
f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m},z)\right\\}\quad\text{where}\quad\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m})=\frac{1}{T}\sum_{i=1}^{T}\nabla
f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m},z_{i})$ (17)

where $z$ is independent of $\\{z_{1},\ldots,z_{T}\\}$. By construction,

$\displaystyle{\mathbb{E}}[\widetilde{\nabla}f(x,z)]=\nabla f(x)\quad\text{for
all}\quad x.$ (18)

Additionally, when $x$ is $\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m}$ is _close_ , the
variance of $\widetilde{\nabla}f(x,z)$ is much smaller than $\nabla f(x,z)$.
Indeed, invoking the Lipschitz gradient assumption A3., and using Cauchy-
Schwartz inequality we have

$\displaystyle{\mathbb{E}}\|\widetilde{\nabla}f(x,z)-\nabla f(x)\|^{2}$
$\displaystyle\leq
3{\mathbb{E}}\|\widetilde{\nabla}f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m},z)-\nabla
f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m})\|^{2}+3{\mathbb{E}}\|\widetilde{\nabla}f(x,z)-\widetilde{\nabla}f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m},z)\|^{2}$
$\displaystyle\qquad\qquad\qquad\qquad+3{\mathbb{E}}\|\nabla f(x)-\nabla
f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m})\|^{2}$
$\displaystyle\leq 3{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m})-f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m})\|^{2}+6\mathrm{L}^{2}\|x-\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m}\|^{2}$
$\displaystyle=\frac{3{\mathbb{E}}\|\nabla f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m},z_{1})-\nabla
f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m})\|^{2}}{T}+6\mathrm{L}^{2}\|x-\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m}\|^{2}$

The second last line above follows from the definition of
$\widetilde{\nabla}f$ and the Lipschitz assumption (A3.),and the last line
uses the property uses that $\\{\nabla f(x,z_{i})\\}_{i=1}^{T}$ are mutually
independent and has the same variance. Finally, we show that as the number of
epochs $m$ increase, $\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m}$ converges to
$x_{\mathbb{P}_{0}}^{\star}$ at a geometric rate, and as a result, for all $x$
close to $\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m}$

$\displaystyle{\mathbb{E}}\|\widetilde{\nabla}f(x,z)-\nabla
f(x)\|^{2}\lesssim\frac{{\mathbb{E}}\|\nabla
f(x_{\mathbb{P}_{0}}^{\star},z_{1})-\nabla
f(x_{\mathbb{P}_{0}}^{\star})\|^{2}}{T}\qquad\text{after small number of
epochs}\;\;m.$

In other words, after small number of epochs $m$, all points $x$ that are
close to $\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m}$ are also close to
$x_{\mathbb{P}_{0}}^{\star}$, the variance of gradient estimates
$\widetilde{\nabla}f(x,z)$ are very similar to the noise variance at the
optima $\frac{{\mathbb{E}}\|\nabla f(x_{\mathbb{P}_{0}}^{\star},z_{1})-\nabla
f(x_{\mathbb{P}_{0}}^{\star})\|^{2}}{T}$ — the best one could hope for.

##### Proximal step:

With this intuition at hand, we are now ready to state our variance reduced
proximal-procedure in Algorithm 1. Our algorithm uses a proximal-step at each
step. We use the notation

$\displaystyle\mathrm{prox}_{\mathrm{R}}(x-\lambda\widetilde{\nabla}f(x))=\min_{y}\left\\{\frac{1}{2}\|y-\left\\{x-\lambda\widetilde{\nabla}f(x)\right\\}\|^{2}+\mathrm{R}(y)\right\\}$
(19)

Algorithm 1 Variance-reduced proximal-gradient (VRPG)

1: Given (a) $N$ iid samples $\\{z_{1},\ldots,z_{N}\\}$ form $\mathbb{P}_{0}$
(b) Number of epochs $M$, (c) Epoch length ${K}$ (d) Re-centering sample size
$T$ (e) Step size $\lambda>0$:

2: Initialize at $\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{1}$

3: for epoch $m=1,2,\ldots,M$ do

4: Set index $j_{m}=(m-1)\cdot(T+K)$.

5: Use samples $\\{z_{i}\\}_{i=j_{m}+1}^{j_{m}+T+{K}}$ to construct
$\\{\widetilde{\nabla}f_{k,m}\\}_{k=1}^{K}$ as follows
$\displaystyle\widetilde{\nabla}f_{k,m}(x)$ $\displaystyle:=\nabla
f(x,z_{j_{m}+T+k})+\left\\{\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m})-\nabla
f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m},z_{j_{m}+T+k})\right\\}$
$\displaystyle\text{where}\quad\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(x)$
$\displaystyle=\frac{1}{T}\sum_{i=1}^{T}\nabla f(x,z_{j_{m}+i})$

6: for k = 1, …K do

7: Set $x_{0}=\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m}$

8: Compute proximal update  $\displaystyle
x_{k}=\mathrm{prox}_{\mathrm{R}}(x_{k-1}-\lambda\widetilde{\nabla}f_{k,m}(x_{k-1}))$

9: end for

10: Set $\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m+1}=x_{K}$

11: end for

12: Return $x_{N}:=\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{M+1}$ as the final
estimate

###  4.2 Instance-dependent guarantees

In this section, we state the performance guarantees of the variance reduced
proximal method Algorithm 1. Given access to $N$ iid samples
$\\{z_{1},\ldots,z_{N}\\}$ from $\mathbb{P}_{0}$, we set

$\displaystyle M$ $\displaystyle=\left\lceil{\log N}\right\rceil,\quad
T=\left\lceil{\frac{N}{\log N}}\right\rceil,\quad
K=\frac{\log(120)}{\log(1/(1-\mu^{2}/(6\cdot
8^{2}\cdot\mathrm{L}^{2})))}\quad\text{and}$ $\displaystyle\lambda$
$\displaystyle=\frac{\mu}{6\cdot 8^{2}\cdot\mathrm{L}^{2}}$ (20)

######  Theorem 1.

Suppose conditions (A1.)- (A3.) are in force and we have access to $N$ iid
samples $\\{z_{1},\ldots,z_{N}\\}$ from $\mathbb{P}_{0}$ with $\frac{N}{\log
N}\geq 60\cdot 32\cdot\frac{\mathrm{L}^{2}}{\mu^{2}}$. Then, the output
$\widehat{x}_{N}$ of Algorithm 1, obtained with tuning parameters from (4.2)
and initialization $\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{1}$, satisfies

$\displaystyle{\mathbb{E}}\|\widehat{x}_{N}-x^{\star}\|^{2}\leq\frac{\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{1}-x_{\mathbb{P}_{0}}^{\star}\|^{2}}{N^{2}}+\frac{7\log
N}{N}\cdot\delta^{2}\left(\frac{N}{\log N}\right)$ (21)

See Section 5 for the proof of this theorem.

A few comments regrading Theorem 1 are in order.

##### Non asymptotic nature of upper bound:

We point out that our upper bound is non-asymptotic in nature, and the bound
holds whenever the number of samples $N\gtrsim\frac{\mathrm{L}^{2}}{\mu^{2}}$,
up to some logarithmic factors. The lower bound
$\frac{\mathrm{L}^{2}}{\mu^{2}}$ is needed to distinguish a $\mu$-strongly
function from a constant function. The leading term in our upper bound (21) is
$\frac{\log N}{N}\cdot\delta^{2}\left(\frac{N}{\log N}\right)$ — which differs
from our aimed upper bound (12) of $\frac{\delta^{2}(N)}{N}$ by logarithmic
factors. Our bound (21) also involves a term which depends on the initial-gap
$\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{1}-x_{\mathbb{P}_{0}}^{\star}\|^{2}$;
this decencies on the initialization-dependent term decay to zero at a rate
$\frac{1}{N^{2}}$.

##### Choice of step-sizes:

Theorem 1 analyzes a variance reduced algorithm with a constant stepsize
$\lambda$. A similar analysis can be performed with appropriate polynomially
decaying stepsizes, i.e, $\lambda=\frac{c_{\omega}}{k^{\omega}}$ for
$\omega\in(0,1)$, and $c_{\omega}$ is an appropriate universal constant. See
for instance the analysis in [21].

##### Comparison to standard variance reduction methods:

As we mentioned before, our algorithm is motivated from standard variance
reduction schemes [9, 24] and proceeds in epochs. In usual variance reduction
schemes [9, 24], the number of samples used in epochs increases exponentially
with the number of epoch $m$. In our algorithm, however, the number of samples
used in each epoch remains same. This change in our algorithm is due to some
technical reasons and it contributes to additional factors of $\log(N)$ in our
upper bounds. This produces a leading term of $\frac{\log
N}{N}\cdot\delta^{2}\left(\frac{N}{\log N}\right)$ instead of
$\delta^{2}\left(N\right)/N$. It would be interesting to know if these
additional logarithmic factors can be removed.

##### Removing logarithmic terms in asymptotic limit:

It is natural to ask what is the asymptotic behavior of the output of
Algorithm 1. Assuming the output $x_{N}$ remain bounded, taking number of
samples $N\rightarrow\infty$ in the bound (21) we see that the upper bound
matches the lower bound (5) up to a factor of $\log(N)$, and a universal
constant. It is interesting to ask whether, these logarithmic factor can be
removed, at least asymptotically. Indeed, assuming the iterates
$x_{N}^{\prime}s$ are bounded, from the distributional limit (10) we have that

$\displaystyle c_{1}\leq\frac{\delta^{2}(N)}{N}\leq c_{2}\qquad\text{for
all}\;\;N\geq N_{0}.$

where $c_{1},c_{2}$ are universal constant. We can now modify our variance
reduced algorithm in the following way. Take $T=N_{0}$ in epoch $m=1$, and
double the number of samples used in each epoch — following a standard
variance reduction scheme [24, 9]; the choice of $K$ and the stepsize
$\lambda$ remain the same. A simple modification of our current analysis
ensures that the output of this modified algorithm achieves the lower bound
(5) up to universal constants.

##  5 Proof of Theorem 1

To simplify the proof, without loss of generality, we assume that that
$\log(N)$, $N/\log(N)$ and the tuning parameters $T$ and $K$ are all positive
integers. If this is not the case, the proof can easily be modified by taking
appropriate floors, and ceilings. The proof of the theorem involves in three
steps.

  * (a)

Within epoch progress

  * (b)

Lipschitz property of perturbed problem.

  * (c)

Between epoch progress

###  5.1 Within epoch analysis:

In Lemma 1, we characterize the progress of Algorithm 1 within each epoch.
Within each epoch, we run a constraint stochastic approximation problem. In
particular, at epoch $m$ we consider the following perturbed problem

$\displaystyle\widehat{x}_{m}=\arg\min_{x}\left\\{f(x)+\left\langle
x,\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m})-\nabla
f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m})\right\rangle+\mathrm{R}(x)\right\\}\equiv\arg\min_{x}\left\\{\tilde{f}_{m}(x)+\mathrm{R}(x)\right\\}$
(22)

where

$\displaystyle\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m})=\frac{1}{T}\sum_{i=1}^{T}\nabla
f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m},z_{j_{m}+i})\qquad\text{with}\quad
j_{m}=(m-1)*(T+K)$

In terms of the above notation, $\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m+1}$ is the output of a
projected stochastic approximation algorithm after $K$ steps. With this set
up, we prove

######  Lemma 1.

Under assumptions of Theorem 1 for each epoch $m=1,\ldots,M$, we have:

$\displaystyle{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m+1}-\widehat{x}_{m}\|^{2}_{2}\leq\frac{{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m}-\widehat{x}_{m}\|^{2}_{2}}{20}$
(23)

#### Proof of Lemma 1

Let $x_{k}$ be the $k^{th}$ iterate of the stochastic approximation within
epoch $m$, and we define

$\displaystyle g_{k}=\frac{1}{\lambda_{k}}\left(x_{k-1}-x_{k}\right)$

For notational convenience we hide the dependence on the epoch $m$, and we use
$\widehat{x}$ for $\widehat{x}_{m}$, $\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}$ for
$\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m}$, and $\tilde{f}$ for
$\tilde{f}_{m}$. We have

$\displaystyle\|x_{k}-\widehat{x}\|^{2}$
$\displaystyle=\|x_{k-1}-\widehat{x}\|^{2}-2\lambda_{k}g_{k}^{\top}(x_{k-1}-\widehat{x})+\lambda_{k}^{2}\|g_{k}\|^{2}$
(24)

We next bound the last two terms in the right hand side of the above equation
using the following bound

$\displaystyle-
g_{k}^{\top}(x_{k-1}-\widehat{x})+\frac{\lambda_{k}}{2}\|g_{k}\|^{2}$
$\displaystyle\leq\left\\{\tilde{f}(\widehat{x})+\mathrm{R}(\widehat{x})-\tilde{f}(x_{k})-\mathrm{R}(x_{k})\right\\}-\frac{\mu}{2}\|x_{k-1}-\widehat{x}\|^{2}-\Delta_{k}^{\top}(x_{k}-\widehat{x})$
(25)

Here, we used the shorthand $\Delta_{k}$ to denote the noise in the noisy
gradient at stage $k$:

$\displaystyle\Delta_{k}=\widetilde{\nabla}f_{k,m}(x_{k-1})-\nabla\tilde{f}(x_{k-1})$

We prove the inequality (25) shortly. Next note that

$\displaystyle\tilde{f}(x_{k})+\mathrm{R}(x_{k})$
$\displaystyle\geq\tilde{f}(\widehat{x})+\mathrm{R}(\widehat{x})+\left\langle\nabla\widetilde{f}(\widehat{x})+\partial\mathrm{R}(\widehat{x}),x_{k}-\widehat{x}\right\rangle+\frac{\mu}{2}\|x_{k}-\widehat{x}\|^{2}$
$\displaystyle=\tilde{f}(\widehat{x})+\mathrm{R}(\widehat{x})+\frac{\mu}{2}\|x_{k}-\widehat{x}\|^{2}$
(26)

The last equality uses
$0\in\nabla\widetilde{f}(\widehat{x})+\partial\mathrm{R}(\widehat{x})$. To
bound the term $-\Delta_{k}^{\top}(x_{k}-\widehat{x})$, using
$\tilde{x}_{k}=\mathrm{prox}_{\mathrm{R}}(x_{k-1}-\lambda_{k}\nabla\tilde{f}(x_{k-1}))$,
we have

$\displaystyle-\Delta_{k}^{\top}(x_{k}-\widehat{x})$
$\displaystyle=-\Delta_{k}^{\top}(x_{k}-\tilde{x}_{k})-\Delta_{k}^{\top}(\tilde{x}_{k}-\widehat{x})$
$\displaystyle\leq\|\Delta_{k}\|\cdot\|x_{k}-\tilde{x}_{k}\|-\Delta_{k}^{\top}(\tilde{x}_{k}-\widehat{x})$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\lambda_{k}\|\Delta_{k}\|^{2}-\Delta_{k}^{\top}(\tilde{x}_{k}-\widehat{x})$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\leq}}8\lambda_{k}\mathrm{L}^{2}\|x_{k-1}-\widehat{x}\|^{2}+2\lambda_{k}\|\Delta^{\star}_{k}\|^{2}-\Delta_{k}^{\top}(\tilde{x}_{k}-\widehat{x})$
(27)

The inequality $(i)$ above uses the contractive property of the proximal
operator :

$\displaystyle\|x_{k}-\widetilde{x}_{k}\|_{2}$
$\displaystyle=\|\mathrm{prox}_{\mathrm{R}}(x_{k-1}-\lambda_{k}\widetilde{\nabla}f_{k,m}(x_{k-1}))-\mathrm{prox}_{\mathrm{R}}(x_{k-1}-\lambda_{k}\nabla\tilde{f}(x_{k-1}))\|$
$\displaystyle\leq\lambda_{k}\|\widetilde{\nabla}f_{k,m}(x_{k-1})-\nabla\tilde{f}(x_{k-1})\|=\lambda_{k}\|\Delta_{k}\|_{2}$

In inequality $(ii)$ we used Cauchy-Schwartz inequality, the
$\mathrm{L}$-Lipschitz property of the maps $\nabla\tilde{f}$ and
$\widetilde{\nabla}f_{k,m}$ and the following upper bound

$\displaystyle\|\Delta_{k}\|_{2}$
$\displaystyle=\|\widetilde{\nabla}f_{k,m}(x_{k-1})-\nabla\tilde{f}(x_{k-1})\|_{2}$
$\displaystyle\leq\underbrace{\|\widetilde{\nabla}f_{k,m}(\widehat{x})-\nabla\tilde{f}(\widehat{x})\|_{2}}_{:=\|\Delta^{\star}_{k}\|_{2}}+\|\widetilde{\nabla}f_{k,m}(\widehat{x})-\widetilde{\nabla}f_{k,m}(x_{k-1})\|_{2}+\|\nabla\tilde{f}(\widehat{x})-\nabla\tilde{f}(x_{k-1})\|_{2}$
$\displaystyle\leq\|\Delta^{\star}_{k}\|_{2}+2\mathrm{L}\|x_{k-1}-\widehat{x}\|_{2}$

Substituting bounds (25),(26), and (27) in the expression (24), and noting
${\mathbb{E}}\left\\{\Delta_{k}^{\top}(\tilde{x}_{k}-\widehat{x})\right\\}=0$
we have

$\displaystyle{\mathbb{E}}\|x_{k}-\widehat{x}\|^{2}$
$\displaystyle={\mathbb{E}}\|x_{k-1}-\widehat{x}\|^{2}+2\lambda_{k}{\mathbb{E}}\left\\{-g_{k}^{\top}(x_{k-1}-\widehat{x})+\frac{\lambda_{k}}{2}\|g_{k}\|^{2}\right\\}$
$\displaystyle\leq{\mathbb{E}}\|x_{k-1}-\widehat{x}\|^{2}+2\lambda_{k}\left\\{-\frac{\mu}{2}{\mathbb{E}}\|x_{k-1}-\widehat{x}\|^{2}-\frac{\mu}{2}{\mathbb{E}}\|x_{k}-\widehat{x}\|^{2}+2\lambda_{k}{\mathbb{E}}\|\Delta_{k}^{\star}\|^{2}+8\lambda_{k}\mathrm{L}^{2}{\mathbb{E}}\|x_{k-1}-\widehat{x}\|_{2}^{2}\right\\}$
(28)

Taking $\lambda_{k}\leq\frac{\mu}{6\cdot 8^{2}\mathrm{L}^{2}}$ we have

$\displaystyle 16\lambda_{k}^{2}\mathrm{L}^{2}-\mu\lambda_{k}\leq
0,\qquad\text{and}\qquad\frac{1}{1+\mu\lambda_{k}}\leq\left(1-\mu\lambda_{k}\right)=\left(1-\frac{\mu^{2}}{6\cdot
8^{2}\mathrm{L}^{2}}\right)$

We have

$\displaystyle{\mathbb{E}}\|x_{k}-\widehat{x}\|^{2}$
$\displaystyle\leq\frac{1}{1+\mu\lambda_{k}}{\mathbb{E}}\|x_{k-1}-\widehat{x}\|^{2}+4\lambda_{k}^{2}{\mathbb{E}}\|\Delta_{k}^{\star}\|^{2}$

Finally, using the Lipschitz property of $\nabla f(x,z)$ and $\nabla f(x)$
from Assumptions (A3.) and (A1.), respectively, we have

$\displaystyle\|\Delta_{k}^{\star}\|_{2}=\|\nabla
f(\widehat{x},z_{j_{m}+T+k})-\nabla f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x},z_{j_{m}+T+k})+\nabla
f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x})-\nabla
f(\widehat{x})\|_{2}\leq 2\mathrm{L}\|\widehat{x}-\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}\|_{2}$

Putting together the pieces we obtain at the following recursion

$\displaystyle{\mathbb{E}}\|x_{k}-\widehat{x}\|^{2}$
$\displaystyle\leq\left(1-\frac{\mu^{2}}{6\cdot
8^{2}\cdot\mathrm{L}^{2}}\right){\mathbb{E}}\|x_{k-1}-\widehat{x}\|^{2}+\cdot\frac{16\cdot\mu^{2}}{6^{2}\cdot
8^{4}\cdot\mathrm{L}^{2}}\|\widehat{x}-\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}\|_{2}^{2}$ (29)

Recursing the last equation $k$-times with
$k\geq\frac{\log(120)}{\log(1/(1-\mu^{2}/6\cdot 8^{2}\cdot\mathrm{L}^{2}))}$
we have

$\displaystyle{\mathbb{E}}\|x_{k}-\widehat{x}\|^{2}$
$\displaystyle\leq\left(1-\frac{\mu^{2}}{6\cdot
8^{2}\cdot\mathrm{L}^{2}}\right)^{k}{\mathbb{E}}\|x_{0}-\widehat{x}\|^{2}+\frac{16}{6\cdot
8^{2}}\cdot\frac{\mu^{2}/(6\cdot 8^{2}\cdot\mathrm{L}^{2})}{\mu^{2}/(6\cdot
8^{2}\cdot\mathrm{L}^{2})}{\mathbb{E}}\|\widehat{x}-\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}\|_{2}^{2}$
$\displaystyle=\left(1-\frac{\mu^{2}}{6\cdot
8^{2}\mathrm{L}^{2}}\right)^{k}{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}-\widehat{x}\|^{2}+\frac{1}{24}{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}-\widehat{x}\|^{2}$
$\displaystyle\leq\frac{1}{120}{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}-\widehat{x}\|^{2}+\frac{1}{24}{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}-\widehat{x}\|^{2}\leq\frac{{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}-\widehat{x}\|^{2}}{20}$

Here, we used $\left(1-\frac{\mu^{2}}{6\cdot
8^{2}\mathrm{L}^{2}}\right)^{k}\leq 1/120$ for
$k\geq\frac{\log(120)}{\log(1/(1-\mu^{2}/6\cdot 8^{2}\cdot\mathrm{L}^{2}))}$.
It remains to prove the bound (25).

#### Proof of bound (25):

The bound follows from the following _key_ lemma on the progress of proximal
operators.

######  Lemma 2.

Given a function For any stepsize $0<\lambda\leq\frac{1}{\mathrm{L}}$ we have

$\displaystyle f(y)+\mathrm{R}(y)\geq
f(x^{+})+\mathrm{R}(x^{+})+g^{\top}(y-x)+\frac{\lambda}{2}\|g\|^{2}+\frac{\mu}{2}\|y-x\|^{2}+\Delta^{\top}(x^{+}-y)$
(30)

where $x^{+}=\mathrm{prox}_{\mathrm{R}}(x-\lambda v)$ and $\Delta=v-\nabla
f(x)$.

Given this lemma at hand, we first note that the perturbed function
$\tilde{f}$ is $\mu$-strongly convex and $\mathrm{L}$-smooth, and the stepsize
$\lambda=\frac{\mu}{16\mathrm{L}}\cdot\frac{1}{\mathrm{L}}\leq 1/\mathrm{L}$.
Now applying Lemma 2 on the function $\tilde{f}$, $y=\widehat{x}$,
$x=x_{k-1}$, $\lambda=\lambda_{k}$ and $v=\widetilde{\nabla}f_{k,m}(x_{k-1})$
yields the bound (25). We provide a proof of Lemma 2 in Appendix A.1.

###  5.2 Lipschitz property of perturbed problem solutions:

The second ingredient in the proof is a Lipschitz property of the perturbed
problem. Consider two following perturbed problems

$\displaystyle x_{\tilde{f}}=\arg\min_{x}\left\\{f(x)+\left\langle
x,\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x})-\nabla
f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x})\right\rangle+\mathrm{R}(x)\right\\}\equiv\arg\min_{x}\tilde{f}(x)\qquad\text{and}$

$\displaystyle x_{\tilde{g}}=\arg\min_{x}\left\\{f(x)+\left\langle
x,\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(x^{\star})-\nabla
f(x^{\star})\right\rangle+\mathrm{R}(x)\right\\}\equiv\arg\min_{x}\tilde{g}(x)$

Here, $\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}$ is any point independent
of the randomness in $\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f$, and $x^{\star}$ is
the (unique) solution of the problem (1). The $\mu$-strong convexity of the
function $f$ ensures that the function $\tilde{f}$ satisfies the following two
growth condition

$\displaystyle\tilde{f}(x)$
$\displaystyle\geq\tilde{f}(x_{\tilde{f}})+\frac{\mu}{2}\|x-x_{\tilde{f}}\|^{2}\qquad\text{for
all}\;\;x.$

We have

$\displaystyle\frac{\mu}{2}\|x_{\tilde{g}}-x_{\tilde{f}}\|^{2}\leq\tilde{f}(x_{\tilde{g}})-\tilde{f}(x_{\tilde{f}})$
$\displaystyle=\left\\{\tilde{f}(x_{\tilde{g}})-\tilde{g}(x_{\tilde{g}})\right\\}+\underbrace{\left\\{\tilde{g}(x_{\tilde{g}})-\tilde{g}(x_{\tilde{f}})\right\\}}_{\leq
0}-\left\\{\tilde{f}(x_{\tilde{f}})-\tilde{g}(x_{\tilde{f}})\right\\}$
$\displaystyle\leq\left\\{\tilde{f}(x_{\tilde{g}})-\tilde{g}(x_{\tilde{g}})\right\\}-\left\\{\tilde{f}(x_{\tilde{f}})-\tilde{g}(x_{\tilde{f}})\right\\}$
$\displaystyle=\left\langle
x_{\tilde{g}}-x_{\tilde{f}},[\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x})-\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(x^{\star})]-[\nabla
f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x})-\nabla
f(x^{\star})]\right\rangle$
$\displaystyle\leq\|x_{\tilde{g}}-x_{\tilde{f}}\|\cdot\|[\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x})-\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(x^{\star})]-[\nabla
f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x})-\nabla f(x^{\star})]\|$

Rearranging, last bound and taking expectation we have

$\displaystyle{\mathbb{E}}\|x_{\tilde{g}}-x_{\tilde{f}}\|^{2}\leq\frac{4{\mathbb{E}}\|[\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x})-\makebox[0.0pt][l]{\hskip
2.05pt\rule[8.12498pt]{5.96916pt}{0.43057pt}}{\nabla}f(x^{\star})]-[\nabla
f(\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x})-\nabla
f(x^{\star})]\|^{2}}{\mu^{2}}\leq\frac{16\mathrm{L}^{2}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}-x^{\star}\|^{2}}{T\mu^{2}}$
(31)

The last inequality above follows from the $\mathrm{L}$-Lipschitz property of
the gradient $\nabla f$.

###  5.3 Between epoch progress:

We complete the proof by quantifying the progress over epochs. Recalling the
definition of $\widehat{x}_{m}$ and $x_{N/\log N}^{\star}$ from (22) and (15),
respectively, we deduce the following bound

$\displaystyle{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m+1}-x_{\mathbb{P}_{0}}^{\star}\|^{2}$
$\displaystyle\leq 2{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m+1}-\widehat{x}_{m}\|^{2}+2{\mathbb{E}}\|\widehat{x}_{m}-x_{\mathbb{P}_{0}}^{\star}\|^{2}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\frac{2{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m}-\widehat{x}_{m}\|^{2}}{20}+2{\mathbb{E}}\|\widehat{x}_{m}-x_{\mathbb{P}_{0}}^{\star}\|^{2}$
$\displaystyle\leq\frac{{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m}-x_{\mathbb{P}_{0}}^{\star}\|^{2}}{5}+\frac{{\mathbb{E}}\|\widehat{x}_{m}-x_{\mathbb{P}_{0}}^{\star}\|^{2}}{5}+2{\mathbb{E}}\|\widehat{x}_{m}-x_{\mathbb{P}_{0}}^{\star}\|^{2}$
$\displaystyle=\frac{{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m}-x_{\mathbb{P}_{0}}^{\star}\|^{2}}{5}+\frac{11}{5}\cdot{\mathbb{E}}\|\widehat{x}_{m}-x_{\mathbb{P}_{0}}^{\star}\|^{2}$
(32)

Inequality $(i)$ follows from Lemma 1. Next, we have

$\displaystyle{\mathbb{E}}\|\widehat{x}_{m}-x_{\mathbb{P}_{0}}^{\star}\|^{2}$
$\displaystyle\leq 2{\mathbb{E}}\|\widehat{x}_{m}-x_{N/\log
N}^{\star}\|^{2}+2{\mathbb{E}}\|x_{N/\log
N}^{\star}-x_{\mathbb{P}_{0}}^{\star}\|^{2}$ $\displaystyle\leq\frac{2\cdot
16\mathrm{L}^{2}}{T\mu^{2}}\cdot{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m}-x_{\mathbb{P}_{0}}^{\star}\|^{2}+2{\mathbb{E}}\|x_{N/\log
N}^{\star}-x_{\mathbb{P}_{0}}^{\star}\|^{2}$
$\displaystyle\leq\frac{5\cdot{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{m}-x_{\mathbb{P}_{0}}^{\star}\|^{2}}{11\cdot
20}+2{\mathbb{E}}\|x_{N/\log N}^{\star}-x_{\mathbb{P}_{0}}^{\star}\|^{2}$ (33)

The second last line above used the bound (31) and noting that
$T=\frac{N}{\log N}$. The last line uses the fact $T=\frac{N}{\log
N}\geq\frac{60\cdot 32\cdot\mathrm{L}^{2}}{\mu^{2}}$. Combining bounds (32)
and (33)and recursing the bound for $M$ we obtain

$\displaystyle{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{M+1}-x_{\mathbb{P}_{0}}^{\star}\|^{2}$
$\displaystyle\leq\frac{{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{M}-x_{\mathbb{P}_{0}}^{\star}\|^{2}}{4}+5\cdot{\mathbb{E}}\|x_{N/\log
N}^{\star}-x_{\mathbb{P}_{0}}^{\star}\|^{2}$
$\displaystyle\leq\frac{{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{1}-x_{\mathbb{P}_{0}}^{\star}\|^{2}}{4^{M}}+7\cdot{\mathbb{E}}\|x_{N/\log
N}^{\star}-x_{\mathbb{P}_{0}}^{\star}\|^{2}$
$\displaystyle=\frac{{\mathbb{E}}\|\makebox[0.0pt][l]{\hskip
1.29167pt\rule[5.59721pt]{4.2024pt}{0.43057pt}}{x}_{1}-x_{\mathbb{P}_{0}}^{\star}\|^{2}}{N^{2}}+\frac{7\log(N)}{N}\cdot\delta^{2}\left(\frac{N}{\log
N}\right).$

This completes the proof of Theorem 1.

##  6 Discussion

In this paper we study the non-asymptotic performance of a natural a variance-
reduced algorithm (VRPG) for a stochastic approximation problem under
constraints. An attractive feature of our results are that they are instance-
dependent in nature. Meaning our guarantees reflect the complexity of the loss
function, the variability of the noise, the geometry constraint set.
Additionally, we show that when the number of samples $N\rightarrow\infty$,
our upper bound matches the celebrated Há jek-Le Cam local minimax lower bound
up to a factor of $\log(N)$ and some universal constants.

Our work leaves open a number of open questions. For instance, there is a
significant body of work which construct a non-asymptotic local minimax lower
bound by comparing the given problem with its hardest alternative in a local
shrinking neighborhood of the given problem [1]. Indeed, in absence of the
constraint set (i.e. $\mathcal{X}={}^{d}$), variance reduced schemes — the
ones similar to the one studied in our paper — achieve such non-asymptotic
local minimax lower bound [11, 12]. It would be interesting to see if such
results can be extended to our setting where $\mathcal{X}\neq{}^{d}$.

### Acknowledgments

This research was partially supported by National Science Foundation Grant
DMS-2311304 to KK. The author thank Feng Ruan and Qiyang Han for helpful
discussions on the paper.

## References

  * [1] T. T. Cai and M. G. Low.  A framework for estimation of convex functions.  Statistica Sinica, pages 423–456, 2015.
  * [2] D. Davis, D. Drusvyatskiy, and L. Jiang.  Asymptotic normality and optimality in nonsmooth stochastic approximation.  arXiv preprint arXiv:2301.06632, 2023.
  * [3] A. L. Dontchev, R. T. Rockafellar, and R. T. Rockafellar.  Implicit functions and solution mappings: A view from variational analysis, volume 616.  Springer, 2009.
  * [4] J. C. Duchi, J. Lafferty, Y. Zhu, et al.  Local minimax complexity of stochastic convex optimization.  Advances in Neural Information Processing Systems, 29, 2016.
  * [5] J. C. Duchi and F. Ruan.  Asymptotic optimality in stochastic optimization.  2021\.
  * [6] J. Dupacová and R. Wets.  Asymptotic behavior of statistical estimators and of optimal solutions of stochastic optimization problems.  The annals of statistics, 16(4):1517–1549, 1988.
  * [7] J. Hájek.  Local asymptotic minimax and admissibility in estimation.  In Proceedings of the sixth Berkeley symposium on mathematical statistics and probability, volume 1, pages 175–194, 1972.
  * [8] J.-B. Hiriart-Urruty and C. Lemaréchal.  Convex analysis and minimization algorithms I: Fundamentals, volume 305.  Springer science & business media, 1996.
  * [9] R. Johnson and T. Zhang.  Accelerating stochastic gradient descent using predictive variance reduction.  Advances in neural information processing systems, 26, 2013.
  * [10] K. Khamaru, A. Pananjady, F. Ruan, M. J. Wainwright, and M. I. Jordan.  Is temporal difference learning optimal? an instance-dependent analysis.  SIAM Journal on Mathematics of Data Science, 3(4):1013–1040, 2021\.
  * [11] K. Khamaru, E. Xia, M. J. Wainwright, and M. I. Jordan.  Instance-optimality in optimal value estimation: Adaptivity via variance-reduced q-learning.  arXiv preprint arXiv:2106.14352, 2021.
  * [12] K. Khamaru, E. Xia, M. J. Wainwright, and M. I. Jordan.  Instance-optimality in optimal value estimation: Adaptivity via variance-reduced q-learning.  arXiv preprint arXiv:2106.14352, 2021.
  * [13] A. J. King.  Asymptotic behaviour of solutions in stochastic optimization: nonsmooth analysis and the derivation of non-normal limit distributions (least squares).  1986\.
  * [14] A. J. King and R. T. Rockafellar.  Asymptotic theory for solutions in statistical estimation and stochastic programming.  Mathematics of Operations Research, 18(1):148–162, 1993.
  * [15] L. Le Cam et al.  Limits of experiments.  In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 245–261. University of California Press, 1972.
  * [16] L. M. Le Cam and G. L. Yang.  Asymptotics in statistics: some basic concepts.  2000\.
  * [17] Y. Nesterov.  Primal-dual subgradient methods for convex problems.  Mathematical programming, 120(1):221–259, 2009.
  * [18] R. Poliquin and R. T. Rockafellar.  Tilt stability of a local minimum.  SIAM Journal on Optimization, 8(2):287–299, 1998.
  * [19] A. Shapiro.  Asymptotic properties of statistical estimators in stochastic programming.  The Annals of Statistics, 17(2):841–858, 1989.
  * [20] A. W. Van der Vaart.  Asymptotic statistics, volume 3.  Cambridge university press, 2000.
  * [21] M. J. Wainwright.  Stochastic approximation with cone-contractive operators: Sharp $\ell_{\infty}$-bounds for $q$-learning.  arXiv preprint arXiv:1905.06265, 2019.
  * [22] M. J. Wainwright.  Variance-reduced $q$-learning is minimax optimal.  arXiv preprint arXiv:1906.04697, 2019.
  * [23] J. Wellner et al.  Weak convergence and empirical processes: with applications to statistics.  Springer Science & Business Media, 2013.
  * [24] L. Xiao and T. Zhang.  A proximal stochastic gradient method with progressive variance reduction.  SIAM Journal on Optimization, 24(4):2057–2075, 2014.

##  Appendix A Technical lemma

In this section we prove a technical lemma that were used in the main section
of the proof.

###  A.1 Proof of Lemma 2:

This Lemma is directly borrowed from [24, Lemma 3]. We provide a proof of this
result for completeness. Recall that

$\displaystyle x^{+}=\arg\min_{y}\left\\{\frac{1}{2}\|y-(x-\lambda
v)\|^{2}+\mathrm{R}(y)\right\\}$

Thus, there exists $u\in\partial\mathrm{R}(x^{+})$ such that

$\displaystyle x^{+}=(x-\lambda v)-\lambda\cdot u$ (34)

Now using $\mu$-strong convexity of $f$ and convexity of the penalty function
$\mathrm{R}$ we have

$\displaystyle f(y)+\mathrm{R}(y)\geq f(x)+\nabla
f(x)^{\top}(y-x)+\frac{\mu}{2}\|y-x\|^{2}+\mathrm{R}(x^{+})+u^{\top}(y-x^{+})$

Additionally, using $\mathrm{L}$ smoothness of the function $f$, and the
expression $x-x^{+}=\lambda g$ we have

$\displaystyle f(y)+\mathrm{R}(y)$ $\displaystyle\geq
f(x^{+})+\mathrm{R}(x^{+})-\frac{L\lambda^{2}}{2}\|x^{+}-x\|^{2}+\frac{\mu}{2}\|y-x\|^{2}$
$\displaystyle\qquad-\nabla f(x^{+})(x^{+}-x)+\nabla
f(x)^{\top}(y-x)+u^{\top}(y-x^{+})$
$\displaystyle=f(x^{+})+\mathrm{R}(x^{+})-\frac{L\lambda^{2}}{2}\|x^{+}-x\|^{2}+\frac{\mu}{2}\|y-x\|^{2}$
$\displaystyle\qquad\qquad+g^{\top}(y-x)+\lambda\|g\|^{2}+\Delta^{\top}(x^{+}-y)$
(35)

The last line above uses the following simplification using the relations
$\Delta=v-\nabla f(x)$, $u=g-v$, and $x-x^{+}=\lambda g$

$\displaystyle-\nabla f(x^{+})(x^{+}-x)+\nabla
f(x)^{\top}(y-x)+u^{\top}(y-x^{+})$ $\displaystyle=g^{\top}(y-x^{+})+(v-\nabla
f(x))^{\top}(x^{+}-y)$
$\displaystyle=g^{\top}(y-x)+\lambda\|g\|^{2}+\Delta^{\top}(x^{+}-y)$

Finally, using the stepsize condition $0<\lambda\leq\frac{1}{\mathrm{L}}$ in
the bound (35) we conclude

$\displaystyle f(y)+\mathrm{R}(y)\geq
f(x^{+})+\mathrm{R}(x^{+})+\frac{\lambda}{2}\|g\|^{2}+\frac{\mu}{2}\|y-x^{+}\|^{2}+\Delta^{\top}(x^{+}-y).$

This completes the proof of Lemma 2.