# Dimension-free Bounds for Sum of Dependent Matrices and Operators with
Heavy-Tailed Distribution

Shogo Nakakita1, Pierre Alquier2, Masaaki Imaizumi1,2 1The University of
Tokyo, 2RIKEN Center for Advanced Intelligence Project

###### Abstract.

We study the deviation inequality for a sum of high-dimensional random
matrices and operators with dependence and arbitrary heavy tails. There is an
increase in the importance of the problem of estimating high-dimensional
matrices, and dependence and heavy-tail properties of data are among the most
critical topics currently. In this paper, we derive a dimension-free upper
bound on the deviation, that is, the bound does not depend explicitly on the
dimension of matrices, but depends on their effective rank. Our result is a
generalization of several existing studies on the deviation of the sum of
matrices. Our proof is based on two techniques: (i) a variational
approximation of the dual of moment generating functions, and (ii)
robustification through truncation of eigenvalues of matrices. We show that
our results are applicable to several problems such as covariance matrix
estimation, hidden Markov models, and overparameterized linear regression
models.

All the authors equally contributed.

##  1\. Introduction

We study a non-asymptotic upper bound of deviations of the average of multiple
random matrices (or operators) from its expectation. Suppose that we observe a
sequence of $n$ random matrices $M_{1},...,M_{n}$ that is potentially high-
dimensional, dependent, and heavy-tailed. We are interested in evaluating a
deviation of its empirical mean from its expectation
$\Sigma:=\mathbb{E}[M_{1}]$ using an operator norm $\|\cdot\|$ for matrices,
that is, we study the upper bound on the following value for each $n$:

$\displaystyle\left\|\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right\|.$

This problem is foundational and important; moreover, it has a variety of
applications, with the most typical example being the estimation of covariance
matrices. Let $Y_{1},...,Y_{n}$ be a sequence of random vectors; then. we can
estimate its covariance matrix $\Sigma=\mathbb{E}[Y_{1}Y_{1}^{\top}]$ using
the empirical mean $n^{-1}\sum_{\ell=1}^{n}M_{\ell}$ by defining
$M_{\ell}=Y_{\ell}Y_{\ell}^{\top}$. This setup can easily be applied for
estimating Fisher information matrices, for example. Other applications
include estimation of adjacency matrices of random graphs (Oliveira, 2009), a
signal recovery of the compressed sensing (Donoho, 2006), and linear
regression of overparameterization (Bartlett et al., 2020). With the growing
importance of data in the modern data science, it is increasingly becoming
important to study the upper bound with various settings, such as high-
dimensional and more complex distributions and dependencies.

This problem has been actively investigated in several settings. Rudelson
(1999) first studied the upper bound on an operator norm of the deviation. A
representative topic is the case in which a matrix $M_{\ell}$ is high-
dimensional. Bunea and Xiao (2015); Mendelson and Paouris (2014); Srivastava
and Vershynin (2013); Koltchinskii and Lounici (2017) derived an upper bound
that does not depend on the dimensionality, referred to as a dimension-free
upper bound, using the notion of the effective rank of matrices. Especially,
Giulini (2018) studied an infinite-dimensional version of the problem. This
allows for the estimation of high-dimensional matrices without assuming
sparsity (Cai et al., 2010) or the shape of the distribution (Adamczak et al.,
2010; Guédon and Rudelson, 2007; Zhivotovskiy, 2021). Han (2022) studied an
asymptotically exact risk of the problem. Lopes et al. (2023) developed a
bootstrap method for high-dimensional operators, and also studied a dimension-
free bound in this setting. For the case where the distribution of a matrix
$M_{\ell}$ has a heavy-tail, Liaw et al. (2017) derived a dimension-free upper
bound to clarify how the tail property affects the bound. Vershynin (2018);
Jeong et al. (2022) further improved the tightness of the upper bound for
heavy-tailed distributions. For a dependent setting of a sequence of matrices,
Han and Li (2020) derived a bound on the expected value of the norm of this
perturbation, by following Handel (2017).

###  1.1. Focus and Result

Our goal is to derive a dimension-free upper bound for deviations of the
empirical mean of random matrices that are dependent and heavy-tailed. This
setting is a generalization of that considered in many previous studies. To
handle the setup, we introduce the notions discussed below. Let $\mathbb{H}$
be a Hilbert space, which we first consider $\mathbb{H}=\mathbb{R}^{p}$ and
then extend to the case with the infinite-dimensional $\mathbb{H}$.

To study the dimension-free property, we consider $M$ as a symmetric linear
operator between $\mathbb{H}$. Then, we define its effective rank:

######  Definition 1 (Effective Rank).

For an operator $M:\mathbb{H}\to\mathbb{H}$ that is positive semi-definite,
the effective rank is defined as

$\displaystyle\mathbf{r}\left(M\right):=\frac{\mathrm{Tr}(M)}{\|M\|},$

where $\mathrm{Tr}(M)$ denotes a trace of $M$ and $\|M\|$ is the operator
norm.

This notion has been used in several studies such as Koltchinskii and Lounici
(2017), and it allows as to measure the statistical dimension of matrices in
terms of the largest eigenvalue and traces, without using the dimension of
$M$.

To address the dependent property of a sequence $M_{1},...,M_{n}$, we consider
a coefficient $\Gamma_{\ell,n}$ for $\ell=1,...,n$ that bounds the following
value:

$\displaystyle|\mathbb{E}[g(M_{\ell+1},\dots,M_{n})|\mathcal{F}_{\ell}]-\mathbb{E}[g(M_{\ell+1},\dots,M_{n})]|\leq\Gamma_{\ell,n},$

where $g(\cdot)$ is an arbitrary Lipschitz-continuous function that will be
rigorously defined, and $\mathcal{F}_{\ell}=\sigma(M_{1},...,M_{\ell})$ is the
sigma-algebra generated by a subset of the sequence. This definition is used
in Rio (2000); Dedecker et al. (2007) and others, and general enough because
it includes many dependent processes, such as causal Bernoulli shifts and
chains with infinite memory.

We also introduce a function $F:\mathbb{R}_{+}\to\mathbb{R}_{+}$ to uniformly
handle the heavy-tail property of a distribution of $M_{\ell},\ell=1,...,n$
such that

$\max_{1\leq\ell\leq n}\mathbb{P}(\|M_{\ell}\|\geq t)\leq F(t),\forall t>0.$

This definition of $F$ is a general representation of the tail probability of
$\|M_{\ell}\|$ that includes both polynomial and exponential decay.

As a main result, we derive the probabilistic upper bound on the deviation of
the empirical mean of the matrices. That is, for any $t,\tau>0$, the following
inequality holds with probability at least $1-e^{-t}-nF(\tau)$:

$\displaystyle\left\|\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right\|\leq
2\sqrt{2}\left\|\Sigma\right\|\left(2\tau+\max_{\ell=1,...,n}\Gamma_{\ell,n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+t}{n}}+V\sqrt{F(\tau)},$

where $V^{2}\geq\mathbb{E}[\|M_{\ell}\|^{2}]$ denote an upper bound of the
moment. The results suggest that (i) we can obtain a dimension-free upper
bound even with the general notion of heavy-tail and dependence; (ii) the
dependent property affects the constant part of the bound through
$\Gamma_{\ell,n}$; and (iii) the heavy-tail property may affect the
convergence rate of the bound with respect to a number of observations $n$ by
adjusting $\tau$.

From a technical perspective, this study makes two contributions. The first is
the evaluation of a moment-generating function using variational inequality,
following (Catoni and Giulini, 2017). That is, we utilize a dual
representation to reform the moment-generating function using an arbitrary
distribution and then use the form to derive an upper bound for the deviation
of the matrices. This approach was employed by Zhivotovskiy (2021) and others,
and we extend the approach to our setting using random matrices with
dependence. The second is the truncation technique used to ensure that the
estimator is robust. We apply the technique for this problem by truncating
eigenvalues of random matrices. By decomposing the deviation of the empirical
mean into deviations from a truncated estimator, we can analyze the effect of
the heavy-tail property.

###  1.2. Organization

Section 2 presents our setting of the problem with an average of random
matrices, and also provides assumptions and its examples. Section 3 presents
the results. We begin with the result for bounded dependent matrices in
Theorem 4. We then extend this result to unbounded matrices in Corollary 5.
Section 4 describes several applications in which the deviation bound is used.
Section 5 contains the proofs of the main results. Section 6 concludes the
paper. Appendix provides the rest of the proofs for applications.

###  1.3. Notations

Let $\mathbb{H}$ be a Hilbert space equipped with the scalar product
$\left<\cdot,\cdot\right>$ and $\|\cdot\|$ be the corresponding norm. Let
$\mathcal{S}$ be the set of symmetric linear continuous operators
$\mathbb{H}\rightarrow\mathbb{H}$, that is, for any $(u,v)\in\mathbb{H}^{2}$,
for any $M\in\mathcal{S}$, $\left<Mu,v\right>=\left<u,Mv\right><\infty$. In
the special case $\mathbb{H}=\mathbb{R}^{p}$, $\mathcal{S}$ is simply the set
of symmetric matrices. For any $M\in\mathcal{S}$ we let $\|M\|$ denote its
operator norm $\|M\|=\sup_{u\in\mathbb{H},\|u\|=1}\|Mu\|$. For a matrix $A$,
$\|A\|_{F}$ is the Frobenius norm of $A$. Throughout this paper,
$\mathbf{M}=(M_{\ell})_{\ell=1,\dots,n}$ is a finite random sequence of
elements of $\mathcal{S}$, whose expectation is constant with
$\Sigma=\mathbb{E}[M_{\ell}]$. The objective of this paper is to study the
estimators of $\Sigma$. For any $\ell\in\\{0,\dots,n\\}$, let
$\mathcal{F}_{\ell}=\sigma(M_{1},\dots,M_{\ell})$. For probability measures
$P,P^{\prime}$, $P\ll P^{\prime}$ denotes that $P$ is absolutely continuous
with respect to $P^{\prime}$, and
$\mathrm{KL}(P\|P^{\prime})=\int\log(dP/dP^{\prime})dP$ denotes the
Kullback–Leibler divergence.

##  2\. Assumption and Example

###  2.1. Assumptions

We present two assumptions on $\mathbf{M}$: an assumption on the dependence
between the $M_{\ell}$’s by a coefficient of weak dependence and an assumption
on the tail of the random variable $\|M_{\ell}\|$.

####  2.1.1. Dependence

We introduce a coefficient to measure the weak dependence of the process of
operators/matrices, which is essentially the one from Rio (2000) and is also
presented in Dedecker et al. (2007). In preparation, we define a set of
Lipschitz functions on $\ell$ operators/matrices for $\ell=1,...,n$.

######  Definition 2 (Lipschitz function on $\ell$ elements).

Let $E$ be a space equipped with the norm $\|\cdot\|_{E}$. For any
$\ell\in\mathbb{N}$ and $L>0$, we let ${\rm Lip}_{\ell}(E,L)$ denote the set
of all functions $h:E^{\ell}\rightarrow\mathbb{R}$ such that for any
$(a_{1},\dots,a_{\ell},b_{1},\dots,b_{\ell})\in E^{2\ell}$,

$|h(a_{1},\dots,a_{\ell})-h(b_{1},\dots,b_{\ell})|\leq
L\sum_{i=1}^{\ell}\|a_{i}-b_{i}\|_{E}.$

Using this coefficient, we make the following assumption on weak dependency:

######  Assumption 1 (dependent processes).

There exist real numbers $(\Gamma_{\ell,n})_{1\leq\ell\leq n}$ such that for
any $\ell\in\\{1,\dots,n\\}$ and for any function $g\in{\rm
Lip}_{n-\ell}(\mathcal{S},1)$,

$|\mathbb{E}[g(M_{\ell+1},\dots,M_{n})|\mathcal{F}_{\ell}]-\mathbb{E}[g(M_{\ell+1},\dots,M_{n})]|\leq\Gamma_{\ell,n}$
(1)

almost surely. We set $\Gamma_{n}=\max_{1\leq\ell\leq n}\Gamma_{\ell,n}$.

This assumption has several noteworthy points: (i) The coefficient used in the
assumption is a generalization of the uniform mixing coefficient for bounded
processes; (ii) it can represent the efficiency of the estimation by the
volume of the coefficient; and (iii) it is not comparable with the
$\alpha/\beta$-mixing property because it can represent certain non-mixing
processes. This assumption can cover linear auto-regressive moving-average
(ARMA) processes and a causal Bernoulli shift (CBS), which is described later.
For more details, refer to Rio (2000); Dedecker and Prieur (2005); Dedecker et
al. (2007); Alquier and Wintenberger (2012).

Note that in previous studies such as Rio (2000), Assumption 1 is used for
bounded processes; that is, $\|M_{\ell}\|$ is bounded. To address unbounded
processes, it is essential to utilize the form of the CBS processes described
in the next section. A fact that we will often use in this paper is that when
$\mathbf{M}=(M_{1},\dots,M_{n})$ satisfies Assumption 1, then so does
$(f(M_{1}),\dots,f(M_{n}))$ where $f:E\rightarrow E$ is an adequate truncation
function. This result generally holds as soon as $f$ is $1$-Lipschitz.

######  Proposition 1.

Assume that $\mathbf{M}=(M_{1},\dots,M_{n})$ satisfies Assumption 1 and that
$f:E\rightarrow E$ is $1$-Lipschitz. Then $(f(M_{1}),\dots,f(M_{n}))$ also
satisfies Assumption 1.

####  2.1.2. Heavy-Tail

We introduce an assumption regarding the heavy-tail property of random
matrices/operators.

######  Assumption 2.

We have $\mathbb{E}[\|M_{\ell}\|^{2}]\leq V^{2}$ for some $V<+\infty$. We know
a non-increasing function $F:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ such
that $F(t)\rightarrow 0$ for $t\rightarrow\infty$ and such that for any
$t\in\mathbb{R}^{+}$,

$\max_{1\leq\ell\leq n}\mathbb{P}(\|M_{\ell}\|>t)\leq F(t).$

If $F(t)$ is an exponentially decaying function, the $k$-th moment of
$\|M_{\ell}\|$ exists for all $k\in\mathbb{N}$. In particular, $F(t)$ has the
form $\exp(-t^{2})$ or $\exp(-t)$, which corresponds to the sub-Gaussian or
sub-exponential property of the distributions (Vershynin (2018)). If $F(t)$ is
a polynomially decaying function $F(t)=-t^{b}$ for some $b>2$, the $k$-th
moment does not exist for some $k>2$, and the form represents the heavier-tail
property of $\|M_{\ell}\|$.

Note that it is possible to let $F(\cdot)$ depend on $n$ such as by setting
$F(\cdot)=F_{n}(\cdot)$ and $F(\cdot)$ varies as $n$ increases. Despite the
flexibility of this setting, we fixed $F(\cdot)$ regardless of $n$ for
simplicity.

###  2.2. Examples

We now provide examples in which Assumptions 1 and 2 are satisfied. A
recurring case of interest occurs when we have a stationary
$\mathbb{H}$-valued stochastic process $(Y_{\ell})_{\ell\in\mathbb{Z}}$ and
$M_{\ell}=Y_{\ell}Y_{\ell}^{\top}$ or $M_{\ell}=Y_{\ell}Y_{\ell+h}^{\top}$.
Then, the estimation of $\Sigma=\mathbb{E}[M_{\ell}]$ respectively corresponds
to the estimation of the covariance matrix of $(Y_{\ell})_{\ell\in\mathbb{Z}}$
and to its cross-covariances.

####  2.2.1. Causal Bernoulli Shift

An important example is a causal Bernoulli shift (CBS), which includes several
general processes and also a base for generating unbounded processes.

######  Example 1 (Causal Bernoulli shifts, CBS).

Let $\Xi=(\xi_{\ell})_{\ell\in\mathbb{Z}}$ be a sequence of bounded i.i.d.
$\mathbb{H}$-valued random variables: $\|\xi_{\ell}\|\leq B_{\xi}$ almost
surely. Let $C:\mathbb{H}^{\infty}\rightarrow\mathbb{H}$ with
$C(0,0,\dots)=0$. Assume that, for any
$(a_{1},b_{1},a_{2},b_{2},\dots)\in\mathbb{H}^{\infty}$ we have

$\|C(a_{1},a_{2},\dots)-C(b_{1},b_{2},\dots)\|\leq\sum_{\ell=1}^{\infty}\alpha_{\ell}\|a_{\ell}-b_{\ell}\|\text{
and }\mathcal{A}:=\sum_{\ell=1}^{\infty}\alpha_{\ell}<\infty.$

Then, we have the following stationary process
$(X_{\ell})_{\ell\in\mathbb{Z}}$ given by

$X_{\ell}=C(\xi_{\ell},\xi_{\ell-1},\xi_{\ell-2},\dots).$

This process $(X_{\ell})_{\ell\in\mathbb{Z}}$ is called a CBS. Note that
$\|X_{\ell}\|\leq B:=\mathcal{A}B_{\xi}$ almost surely.

The form of CBSs is a generalization of known stationary and ergodic
processes, such as the causal ARMA process. Then, we provide the following
result.

######  Proposition 2.

We define that $(Y_{\ell})_{\ell\in\mathbb{Z}}$ is a CBS and
$M_{\ell}=Y_{\ell}Y_{\ell}^{\top}$ for any $\ell\in\mathbb{Z}^{2}$. Then,
$\mathbf{M}=(M_{\ell})_{\ell=1,\dots,n}$ satisfies Assumption 1 with
$\Gamma_{\ell,n}=4BB_{\xi}\sum_{i=\ell+1}^{\infty}\min(i,n)\alpha_{i}$ and
Assumption 2 with $F(t)=\mathbf{1}_{\\{t\leq 4B^{2}\\}}$.

In this result, we do not have to consider the heavy-tail property, because
CBSs are bounded processes. The proof of Proposition 2 is included in that of
Proposition 3, which provides a more general setting for unbounded processes.

####  2.2.2. Application to Unbounded Process

We apply the CBS class and generate a process that satisfies the assumptions
regarding the choice of the coefficient $\Gamma_{\ell,n}$ and the function
$F(\cdot)$. Here, the generated process can be unbounded.

######  Proposition 3.

We assume that $(X_{\ell})_{\ell\in\mathbb{Z}}$ is a CBS. Let
$\mathcal{E}=(\varepsilon_{\ell})_{\ell\in\mathbb{Z}}$ be a sequence of
centered i.i.d. $\mathbb{H}$-valued random variables with
$F_{\varepsilon}(t):=\mathbb{P}(\|\varepsilon_{\ell}\|^{2}\geq t)$, all
independent from $(X_{\ell})_{\ell\in\mathbb{Z}}$. We define a process
$(Y_{\ell})_{\ell\in\mathbb{Z}}$ as

$\displaystyle Y_{\ell}=X_{\ell}+\varepsilon_{\ell},$

and $M_{\ell}=Y_{\ell}Y_{\ell}^{\top}$ for any $\ell\in\mathbb{Z}^{2}$. Then,
$\mathbf{M}=(M_{\ell})_{\ell=1,\dots,n}$ satisfies Assumption 1 with
$\Gamma_{\ell,n}=4BB_{\xi}\sum_{i=\ell+1}^{\infty}\min(i,n)\alpha_{i}$ and
Assumption 2 with $F(t)=\mathbf{1}_{\\{t\leq 4B^{2}\\}}+F_{\varepsilon}(t/4)$.

Furthermore, if $\Gamma:=4BB_{\xi}\sum_{i=2}^{\infty}i\alpha_{i}<\infty$, then
$\max_{1\leq\ell\leq n}\Gamma_{\ell,n}\leq\Gamma$ holds.

It is important to note that although CBSs are bounded, the generated process
$\mathbf{Y}$ here can be unbounded depending upon the choice of
$\varepsilon_{\ell}$. To clarify this point, we show certain possible choices
for $F_{\varepsilon}(t/4)$: (i) bounded noise: if
$\|\varepsilon_{\ell}\|\leq\lambda$ almost surely, then
$F_{\varepsilon}(t/4)\leq\mathbf{1}_{\\{t\leq 4\lambda^{2}\\}}$, (ii) noise
with moments: if $k,\lambda$ such that
$\mathbb{E}(\|\varepsilon_{\ell}\|^{k}/\lambda)\leq 1$ then
$F_{\varepsilon}(t/4)\leq 2^{k}\lambda t^{-\frac{k}{2}}$, and (iii) noise with
exponential moments: if $k,\lambda>0$ such that
$\mathbb{E}[\exp(\|\varepsilon_{\ell}\|^{k}/\lambda)]\leq 1$, then
$F_{\varepsilon}(t/4)\leq\exp(-t^{k/2}/(2^{k}\lambda))$.

####  2.2.3. Application to Chain with Infinite Memory

We introduce a chain with infinite memory, which turns out to be a special
case of the CBS process.

######  Example 2 (Chain with Infinite Memory, CIM).

Let $\Xi=(\xi_{\ell})_{\ell\in\mathbb{Z}}$ be a sequence of bounded i.i.d.
$\mathbb{H}$-valued random variables: $\|\xi_{\ell}\|\leq B_{\xi}$ almost
surely. Let $D:\mathbb{H}^{\infty}\rightarrow\mathbb{H}$ with
$D(0,0,\dots)=0$. Assume that, for any
$(a_{0},b_{0},a_{1},b_{1},a_{2},b_{2},\dots)\in\mathbb{H}^{\infty}$ we have

$\|D(a_{0},a_{1},a_{2},\dots)-D(b_{0},b_{1},b_{2},\dots)\|\leq\sum_{\ell=0}^{\infty}\beta_{\ell}\|a_{\ell}-b_{\ell}\|\text{
and }\mathcal{B}:=\sum_{\ell=1}^{\infty}\beta_{\ell}<1.$

Then, there is a stationary solution $(X_{\ell})_{\ell\in\mathbb{Z}}$ to the
equation (Doukhan and Wintenberger, 2008):

$X_{\ell}=D(\xi_{\ell},X_{\ell-1},X_{\ell-2},X_{\ell-3},\dots).$

The process $(X_{\ell})_{\ell\in\mathbb{Z}}$ is called a chain with infinite
memory (CIM).

We now discuss the connection between CBSs and CIMs. Using Proposition 4.1 of
Alquier and Wintenberger (2012), a CIM can be rewritten as a CBS as

$X_{\ell}=C(\xi_{\ell},\xi_{\ell-1},\xi_{\ell-2},\dots)\text{ with
}\alpha_{\ell}=\beta_{0}\mathcal{B}^{\ell-1}.$

######  Remark 1.

We briefly discuss our framework and its relation to the vector auto-
regression (VAR) process. Since the VAR with bounded noise terms is obviously
CIM, Assumption 1 and 2 are satisfied by a process with heavy-tailed noise
added to the VAR, by using Proposition 3. On the other hand, when the noise in
the VAR has a heavy-tail, like $Y_{\ell}=AY_{\ell-1}+\varepsilon_{\ell}$ with
$A\in\mathbb{R}^{p}\otimes\mathbb{R}^{p}$ and the heavy-tailed noise
$\varepsilon_{\ell}$, we need to apply another technique to handle it. That
is, we have to approximate the VAR by a finite-order moving-average (MA)
process and show it satisfies Assumption 1 and 2. However, since this
approximation error vanishes as $n\to\infty$, we can apply our result without
any problems.

##  3\. Main Results

We present our upper bound as the main result in stages. First, we consider
the case where $M_{\ell}$ is a $p\times p$ matrix with the bounded property,
and then we extend it to the unbounded and heavy-tailed cases. Then, we
consider the case where $M_{\ell}$ is an operator between infinite-dimensional
spaces.

###  3.1. Result on $p$-Dimensional Matrix

####  3.1.1. Bounded Case

We first consider the case $\mathbb{H}=\mathbb{R}^{p}$ with $p\in\mathbb{N}$
and the case in which the matrices $\|M_{\ell}\|$ are bounded for all
$\ell=1,...,n$. Obviously, $M_{\ell}$ is not heavy-tailed in this case; hence,
we handle the dependence property of process $\mathbf{M}$.

The derivation of this result starts with the variational inequality: with a
random parameter $\theta$ following a measure $\mu$ and a random variable $X$,
it holds that with probability at least $1-e^{-t}$:

$\displaystyle\mathbb{E}_{\rho}[h\left(X,\theta\right)]\leq\mathbb{E}_{\rho}\left[\log\mathbb{E}_{X}\left[\exp\left(h\left(X,\theta\right)\right)\right]\right]+\mathrm{KL}\left(\rho\|\mu\right)+t.$

for all probability measures $\rho\ll\mu$ and measurable function $h$. This
result follows Catoni and Giulini (2017) and Zhivotovskiy (2021). In our
setting with the dependent property, the idea is to apply the inequality by
Rio (2000) for dependent matrices and obtain

$\displaystyle\mathbb{E}\left[\exp\left(\lambda
h(\mathbf{M})-\lambda\mathbb{E}[h(\mathbf{M})]\right)\right]\leq\exp\left(\frac{\lambda^{2}L^{2}\sum_{\ell=1}^{n}\left(2\kappa+\Gamma_{\ell,n}\right)^{2}}{8n^{2}}\right).$

Then, we obtain the below result. We state the concentration bound for the
estimation of $\Sigma$ using the empirical mean of $\mathbf{M}$.

######  Theorem 4.

Assume that $\mathbf{M}$ is a sequence of positive semi-definite symmetric
random $p\times p$ matrices with $\mathbb{E}\left[M_{\ell}\right]=\Sigma$ and
$\left\|M_{\ell}\right\|\leq\kappa^{2}$ almost surely for some $\kappa>0$ and
all $\ell=1,\ldots,n$. Let us assume that Assumption 1 is satisfied. Then for
all $t>0$, it holds that

$\displaystyle\left\|\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right\|\leq
2\sqrt{2}\left\|\Sigma\right\|\left(2\kappa^{2}+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+t}{n}}.$

with probability at least $1-e^{-t}$.

This upper bound has the following implications: First, it is a dimension-free
bound in which $p$ does not appear, and this statistical dimension is
described by the effective rank $\mathbf{r}\left(\Sigma\right)$ except for the
effect of $t$. This is identical to the statistical dimension of the
independent case of Koltchinskii and Lounici (2017) and others. Second, the
effect of this dependence appears as $\Gamma_{n}$ in the coefficient part
$(2\kappa^{2}+\Gamma_{n})$ of the upper bound. If $\mathbf{M}$ is independent,
we have $\Gamma_{n}=0$. Then, our upper bound corresponds to the upper bound
by Koltchinskii and Lounici (2017) up to the universal constants.

####  3.1.2. Heavy-Tailed Case

We now extend Theorem 4 to unbounded heavy-tailed matrices $M_{\ell}$ and
provide an updated upper bound.

The general idea is to apply Theorem 4 to a sequence of transformed matrices
$\\{f(M_{1}),...,f(M_{n})\\}$ where $f:\mathcal{S}\rightarrow\mathcal{S}$ is a
bounded transform, such that $\sup_{M\in\mathcal{S}}\|f(M)\|\leq\tau$. This
application yields a bound on
$\|\frac{1}{n}\sum_{\ell=1}^{n}f(M_{\ell})-\mathbb{E}[f(M_{\ell})]\|$. Then,
we handle the effect of $f$, that is,
$\|\frac{1}{n}\sum_{\ell=1}^{n}f(M_{\ell})-\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}\|$
and $\|\mathbb{E}[f(M_{\ell})]-\Sigma\|$, and develop an upper bound on
$\|\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\|$. This results in the
introduction of an additional term depending on $\tau$ in the upper bound.
This technique leads to the following results:

######  Corollary 5.

Assume that $\mathbf{M}$ is a sequence of positive semi-definite symmetric
random $p\times p$ matrices with $\mathbb{E}\left[M_{\ell}\right]=\Sigma$,
which satisfies Assumptions 1 and 2. For any $\tau>0$ and for all $t>0$, it
holds that

$\displaystyle\left\|\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right\|\leq
2\sqrt{2}\left\|\Sigma\right\|\left(2\tau+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+t}{n}}+V\sqrt{F(\tau)}.$

with probability at least $1-e^{-t}-nF(\tau)$.

The effect of the heavy-tailed property appears additively in the second term
of the derived upper bound. The tightness of the bound will, of course, depend
on how we deviate from the boundedness assumption, that is, on the function
$F$. We provide the following examples:

Bounded Case: Suppose that $\|M_{i}\|\leq\kappa$ almost surely for some
$\kappa>0$, then Assumption 2 is satisfied with $F(\tau)=0$ for
$\tau\geq\kappa$. Thus, we can take $\tau=\kappa$ and recover exactly Theorem
4.

Exponential-Tail Case: Suppose that $F(\cdot)$ has an exponential decay, that
is, $F(t)=\exp(-at^{b})$ with some $a,b>0$. Then, Corollary 5 states that with
probability at least $1-e^{-t}-n\exp(-a\tau^{b})$,

$\displaystyle\left\|\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right\|\leq
2\sqrt{2}\left\|\Sigma\right\|\left(2\tau+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+t}{n}}+V\exp\left(-\frac{a}{2}\tau^{b}\right).$

We select $\tau\geq(\frac{\log n+t}{a})^{1/b}$ which implies that
$nF(\tau)\leq\exp(-t)$, and we set $t=\log(\delta^{-1})$. Subsequently, for
every $\delta\in(0,1)$. with probability at least $1-\delta$, we have that

$\displaystyle\left\|\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right\|$
$\displaystyle\leq 2\sqrt{2}\left\|\Sigma\right\|\left(2\left(\frac{\log
n+\log(\delta^{-1})}{a}\right)^{1/b}+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+\log(\delta^{-1})}{n}}$
$\displaystyle\quad+V\sqrt{\frac{\log(\delta^{-1})}{n}}.$

In this upper bound, the effect of the heavy-tail appears in the second term
$V\sqrt{\log(\delta^{-1})/n}$, which is relatively less significant. In
contrast, the main difference is that the constant part of the first term
$(2(\frac{\log n+\log(\delta^{-1})}{a})^{1/b}+\Gamma_{n})$, which increases in
$(\log n)^{1/b}$. Except for the logarithmic increase in $n$, the effects of
the statistical dimension and the dependent property are identical to the
bound in Theorem 4.

Polynomial-Tail Case: Suppose that $F(\cdot)$ has a polynomial decay
$F(\tau)=a\tau^{-b}$ with $a>0$ and $b>2$, then the bound is, with probability
at least $1-e^{-t}-na\tau^{-b}$,

$\displaystyle\left\|\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right\|\leq
2\sqrt{2}\left\|\Sigma\right\|\left(2\tau+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+t}{n}}+V\sqrt{a\tau^{-b}}.$

Here, we chose $\tau$ such that $na\tau^{-b}=\exp(-t)$ to make
$\tau=(an)^{1/b}\exp(t/b)$, and also set $t=\log(\delta^{-1})$. Then, for any
$\delta\in(0,1)$, we obtain that with probability at least $1-\delta$,

$\displaystyle\left\|\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right\|\leq
2\sqrt{2}\left\|\Sigma\right\|\left(2a^{1/b}+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+\log(\delta^{-1})}{n}}+V\sqrt{\frac{\delta}{n}}.$

Given that $b>2$, the second term $V\sqrt{{\delta}/{n}}$ decreases in $n$
toward $0$, but its convergence rate is slower than that in the previous
cases, depending on the selection of $\delta$. The statistical properties of
the first term remain mostly unchanged, except for the change in the constant
part.

###  3.2. Result on Infinite-Dimensional Operator

Here, we consider the case of an infinite-dimensional separable Hilbert space
$\mathbb{H}$, which has also been actively studied (Koltchinskii and Lounici,
2017; Giulini, 2018). As in Giulini (2018), we extend our result for the
$p$-dimensional setting to the case.

The approach here is to find the finite-dimensional approximation of the
spectral norm of operators on an orthonormal basis. Let
$(e_{j})_{j\in\mathbb{N}}$ be the orthonormal basis of $\mathbb{H}$ and
$\mathbb{H}_{k}:=\mathrm{span}\left\\{e_{1},\ldots,e_{k}\right\\}$. For an
$\mathbb{H}\otimes\mathbb{H}$-valued random operator $M_{\ell}$, let
$(M_{\ell}^{\left(j_{1},j_{2}\right)})_{j_{1},j_{2}=1}^{k}$ be a sequence of
real-valued random variables such that
$M_{\ell}^{\left(j_{1},j_{2}\right)}:=\langle
M_{\ell}e_{j_{1}},e_{j_{2}}\rangle$. We see that

$\displaystyle\sup_{\begin{subarray}{c}u_{k}\in\mathbb{H}_{k}\\\
\left\|u_{k}\right\|=1\end{subarray}}\left|\left\langle\left(\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right)u_{k},u_{k}\right\rangle\right|$
$\displaystyle=\sup_{\begin{subarray}{c}u_{k}^{\left(j\right)}\in\mathbb{R},j=1,\ldots,k\\\
\sum_{j=1}^{k}(u_{k}^{\left(j\right)})^{2}=1\end{subarray}}\left|\frac{1}{n}\sum_{i=1}^{n}\sum_{j_{1}=1}^{k}\sum_{j_{2}=1}^{k}u_{k}^{\left(j_{1}\right)}u_{k}^{\left(j_{2}\right)}\left(M_{\ell}^{\left(j_{1},j_{2}\right)}-\mathbb{E}\left[M_{\ell}^{\left(j_{1},j_{2}\right)}\right]\right)\right|.$

Then, the right-hand side is clearly a spectral norm of the difference between
the sampled matrix and the population one, to which Theorem 4 and Corollary 5
are applicable. Based on this approach of considering a limit $k\to\infty$, we
obtain the following result:

######  Theorem 6.

Assume that $\mathbf{M}$ is a sequence of positive semi-definite symmetric
$\mathbb{H}\otimes\mathbb{H}$-valued random operators with
$\mathbb{E}\left[M_{\ell}\right]=\Sigma$, and also satisfies Assumptions 1 and
2. For any $\tau>0$ and for all $t>0$, it holds that

$\displaystyle\left\|\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right\|\leq
2\sqrt{2}\left\|\Sigma\right\|\left(2\tau+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+t}{n}}+V\sqrt{F(\tau)}.$

with probability at least $1-e^{-t}-nF(\tau)$.

This result shows that the obtained upper bound remains the same, even for
infinite dimensions. Note that it is impossible to consider an infinite-
dimensional case from the beginning without considering the matrix case. This
is because our proof by variational equalities depends on a density function
of $p$-dimensional Gaussian vector; therefore, we cannot directly handle this
proof in the infinite-dimensional case.

##  4\. Applications

###  4.1. Covariance Operator Estimation

We consider the problem of covariance operator estimation using dependent
samples with heavy tails. Suppose there exists a CBS
$(X_{\ell})_{\ell\in\mathbb{N}}$ and a sequence of $\mathbb{H}$-valued random
variables $(Y_{\ell})_{\ell\in\mathbb{Z}}$, which is a strongly stationary
process that follows

$\displaystyle Y_{\ell}=X_{\ell}+\varepsilon_{\ell},$

as the process in Proposition 3. In addition, suppose that
$\mathbb{E}[X_{1}]=0$ and its covariance operator is $\Sigma\in\mathcal{S}$;
that is, $\Sigma$ is defined as $\Sigma u=\mathbb{E}[\langle Y_{1},u\rangle
Y_{1}]$ for any $u\in\mathbb{H}$.

Suppose we have $n$ observations $\mathbf{Y}=(Y_{\ell})_{\ell=1,...,n}$ that
follow the process $(Y_{\ell})_{\ell\in\mathbb{Z}}$. Then, we define an
empirical covariance operator:

$\displaystyle M_{\ell}u:=\langle Y_{\ell},u\rangle Y_{\ell},$

for any $u\in\mathbb{H}$. Using this notion, we obtain $n$ operators
$\mathbf{M}$ from $\mathbf{Y}$ and then obtain the empirical covariance
operator as

$\displaystyle\widehat{\Sigma}:=\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}.$ (2)

We connect this setup to our result in Corollary 5 and obtain the following
result without proof.

######  Proposition 7.

Suppose that the sequence $\mathbf{M}$ satisfies Assumptions 1 and 2. Consider
the empirical covariance operator defined in (2). Then, for any $\tau>0$ and
$t>0$, the following inequality holds with probability at least
$1-e^{-t}-nF(\tau)$:

$\displaystyle\|\widehat{\Sigma}-\Sigma\|\leq
2\sqrt{2}\left\|\Sigma\right\|\left(2\tau+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+t}{n}}+V\sqrt{F(\tau)},$

where $F(\tau)=\mathbf{1}_{\\{\tau\leq 4B^{2}\\}}+F_{\varepsilon}(\tau/4)$.

Examples of specific processes, $(Y_{\ell})_{\ell\in\mathbb{Z}}$ include a CBS
and its extension to the unbounded processes given in Section 2.2.

###  4.2. Lagged Covariance Matrix Estimation

We consider an estimation problem for a lagged covariance matrix, which is
also called a cross-covariance matrix. Consider the same process
$(Y_{\ell})_{\ell\in\mathbb{Z}}$ as in Section 4.1. The objective here is to
estimate

$\displaystyle\Sigma_{1}:=\mathbb{E}[Y_{\ell}Y_{\ell+1}^{\top}],$

from $n$ observations $\mathbf{Y}=(Y_{\ell})_{\ell=1,...,n}$. This problem is
obviously extended to $\Sigma_{h}:=\mathbb{E}[Y_{\ell}Y_{\ell+h}^{\top}]$ for
$h\geq 2$. Note that $\Sigma_{1}$ is not symmetric; hence, our main results
cannot be directly applied to a naive estimator,
$\widehat{\Sigma}_{1}:=(n-1)^{-1}\sum_{\ell=1}^{n-1}Y_{\ell}Y_{\ell+1}^{\top}$.
We also consider a covariance matrix
$\Sigma=\mathbb{E}[Y_{\ell}Y_{\ell}^{\top}]$, which can be regarded as
$\Sigma_{0}$, and its empirical estimator
$\widehat{\Sigma}:=(n-1)^{-1}\sum_{\ell=1}^{n-1}Y_{\ell}Y_{\ell}^{\top}$.

To estimate $\Sigma_{1}$, we define an augmented process and estimator for the
covariance matrix of the process. We define a Hilbert space $\mathbb{H}^{2}$
equipped with the scalar product
$\langle(y_{1},y_{2}),(y_{1}^{\prime},y_{2}^{\prime})\rangle=\langle
y_{1},y_{1}^{\prime}\rangle+\langle y_{1},y_{2}^{\prime}\rangle$ for
$(y_{1},y_{2}),(y^{\prime}_{1},y^{\prime}_{2})\in\mathbb{H}^{2}$. Let
$\widetilde{Y}_{\ell}=(Y_{\ell},Y_{\ell+1})^{\top}$ be an
$\mathbb{H}^{2}$-valued augmented process generated by
$(Y_{\ell})_{\ell\in\mathbb{Z}}$, whose covariance function is written as

$\displaystyle\Sigma_{0:1}:=\mathbb{E}\left[\widetilde{Y}_{\ell}\widetilde{Y}_{\ell}^{\top}\right]=\left(\begin{array}[]{c
c}\mathbb{E}[Y_{\ell}Y_{\ell}^{\top}]&\mathbb{E}[Y_{\ell}Y_{\ell+1}^{\top}]\\\
\mathbb{E}[Y_{\ell+1}Y_{\ell}^{\top}]&\mathbb{E}[Y_{\ell+1}Y_{\ell+1}^{\top}]\end{array}\right)=\left(\begin{array}[]{c
c}\Sigma_{0}&\Sigma_{1}\\\ \Sigma_{1}^{\top}&\Sigma_{0}\end{array}\right).$
(7)

In the following, we estimate $\Sigma_{0:1}$ and apply the result to the
estimation for $\Sigma_{1}$.

Using observations $\mathbf{Y}$, we generate
$\widetilde{Y}_{1},...,\widetilde{Y}_{n-1}$ and its sample-wise product
matrices $M_{1},...,M_{n-1}$ as

$M_{\ell}:=\widetilde{Y}_{\ell}\widetilde{Y}_{\ell}^{\top}=\left(\begin{array}[]{c
c}Y_{\ell}Y_{\ell}^{\top}&Y_{\ell}Y_{\ell+1}^{\top}\\\
Y_{\ell+1}Y_{\ell}^{\top}&Y_{\ell+1}Y_{\ell+1}^{\top}\end{array}\right).$

We then construct an empirical estimator

$\displaystyle\widehat{\Sigma}_{0:1}:=\frac{1}{n-1}\sum_{\ell=1}^{n-1}M_{\ell}=\left(\begin{array}[]{c
c}\widehat{\Sigma}&\widehat{\Sigma}_{1}\\\
\widehat{\Sigma}_{1}^{\top}&\widehat{\Sigma}\end{array}\right).$ (10)

We show a concentration inequality for $\widehat{\Sigma}_{0:1}$ and then
additionally show the convergence of $\widehat{\Sigma}$ and
$\widehat{\Sigma}_{1}$.

######  Proposition 8.

Assume that $\mathbf{Y}$ is a CBS, as in Example 1. Consider matrix (7) and
estimator (10). Then, for any $\tau>0$ and $t>0$, the following inequality
holds with probability at least $1-e^{-t}-nF(\tau)$:

$\displaystyle\|\widehat{\Sigma}_{0:1}-\Sigma_{0:1}\|\leq
4\sqrt{2}\left(\|\Sigma_{0:1}\|\right)\left(32B^{2}+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma_{0:1}\right)+t}{n-1}}+V\sqrt{F(\tau)},$

where $F(\tau)=4\mathbf{1}_{\\{\tau\leq 4B^{2}\\}}+4F_{\varepsilon}(t/2)$.
Furthermore, with the same probability, we obtain

$\displaystyle\max\\{\|\widehat{\Sigma}-\Sigma\|,\|\widehat{\Sigma}_{1}-\Sigma_{1}\|\\}$
$\displaystyle\leq
4\sqrt{2}\left(\|\Sigma_{1}\|+\|\Sigma\|\right)\left(32B^{2}+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma_{0:1}\right)+t}{n-1}}+V\sqrt{F(\tau)}.$

The first statement follows Theorem 4 for estimator $\widehat{\Sigma}_{0:1}$
for a symmetric matrix $\Sigma_{0:1}$. The second statement simply follows the
first statement and the facts
$\left\|\Sigma_{0:1}\right\|\leq\|\Sigma_{1}\|+\|\Sigma\|$. By using the
relation
$\mathrm{tr}(\Sigma_{0:1})=2\mathrm{tr}(\Sigma)=2\|\Sigma\|\mathbf{r}\left(\Sigma\right)$,
we can update the upper bound.

###  4.3. Linear Hidden Markov Model

We consider a linear hidden Markov model (HMM) and study its estimator.
Specifically, we consider a HMM model with a lag order $1$ and set
$\mathbb{H}=\mathbb{R}^{p}$. Suppose that we observe a sequence of
$p$-dimensional random vectors $\mathbf{Y}=(Y_{\ell})_{\ell=0}^{n}$ which
follows the following equations for $\ell\in\mathbb{Z}$:

$\displaystyle Y_{\ell}$ $\displaystyle=X_{\ell}+\varepsilon_{\ell},$ (11)
$\displaystyle X_{\ell}$ $\displaystyle=AX_{\ell-1}+\xi_{\ell}$ (12)

where $A\in\mathbb{R}^{p\times p}$ is an unknown parameter matrix such that
$\|A\|\in(0,1)$, and $(X_{\ell})_{\ell\in\mathbb{Z}}$ is a latent process such
that $\|X_{\ell}\|\leq B$ almost surely. Here,
$(\varepsilon_{\ell})_{\ell\in\mathbb{Z}}$ is a sequence of i.i.d.
$p$-dimensional noise variable with zero mean and finite variance, and
$\xi_{\ell}$ is a sequence of i.i.d. $p$-dimensional bounded noise variable
with zero mean such that $\|\xi_{\ell}\|\leq B_{\xi}$ almost surely. Under
condition $\|A\|\in(0,1)$ and the bounded property of $\xi_{\ell}$, the upper
bound $B$ is guaranteed to be finite. For brevity, we assume that
$\mathbb{E}[\varepsilon_{\ell}\varepsilon_{\ell}^{\top}]=\mathbb{E}[\xi_{\ell}\xi_{\ell}^{\top}]=I$.
We also define a covariance matrix
$\Sigma:=\mathbb{E}[Y_{\ell}Y_{\ell}^{\top}]$ and lagged covariance matrix
$\Sigma_{1}:=\mathbb{E}[Y_{\ell+1}Y_{\ell}^{\top}]$. The goal of this problem
is to estimate the unknown parameter matrix $A$.

We consider a convenient form of the HMM model. Let us define noise matrices
$\mathsf{E}=(\varepsilon_{0},...,\varepsilon_{n-1})\in\mathbb{R}^{p\times n}$,
$\mathsf{E}_{+}=(\varepsilon_{1},...,\varepsilon_{n})\in\mathbb{R}^{p\times
n}$, and $\mathsf{Z}=(\xi_{1},...,\xi_{n})\in\mathbb{R}^{p\times n}$ and also
define matrices $\mathsf{Y}=(Y_{0},...,Y_{n-1})\in\mathbb{R}^{p\times n}$ and
$\mathsf{Y}_{+}=(Y_{1},...,Y_{n})\in\mathbb{R}^{p\times n}$. Then, we rewrite
models (11) and (12) as

$\displaystyle(\mathsf{Y}_{+}-\mathsf{E}_{+})=A(\mathsf{Y}-\mathsf{E})+\mathsf{Z}.$

Multiplying $(\mathsf{Y}-\mathsf{U})^{\top}$ on both sides from the right and
taking an expectation yields

$\displaystyle A$
$\displaystyle=(\mathbb{E}[(\mathsf{Y}_{+}-\mathsf{E}_{+})(\mathsf{Y}-\mathsf{E})^{\top}]-\mathbb{E}[\mathsf{Z}(\mathsf{Y}-\mathsf{E})^{\top}])\mathbb{E}[(\mathsf{Y}-\mathsf{E})(\mathsf{Y}-\mathsf{E})^{\top}]^{-1}$
$\displaystyle=\Sigma_{1}(\Sigma+I)^{-1}.$

Here, we utilize the independent properties of the noise, and
$\mathbb{E}[\varepsilon_{\ell}\varepsilon_{\ell}^{\top}]=I$.

We now consider the estimator for $A$. Using empirical estimators
$\widehat{\Sigma}:=\mathsf{Y}\mathsf{Y}^{\top}/n=n^{-1}\sum_{\ell=0}^{n-1}Y_{\ell}Y_{\ell}^{\top}$
and
$\widehat{\Sigma}_{1}:=\mathsf{Y}_{+}\mathsf{Y}^{\top}/n=n^{-1}\sum_{\ell=0}^{n-1}Y_{\ell+1}Y_{\ell}^{\top}$,
we define the following estimator:

$\displaystyle\widehat{A}:=\widehat{\Sigma}_{1}(\widehat{\Sigma}+I)^{-1}.$
(13)

Then, we obtain the following result:

######  Proposition 9.

Consider the HMM model (11)-(12) and estimator (13) for the parameters in the
model. Then, for any $t>2B^{2}$ with probability at least
$1-\exp(-t)-nF_{\varepsilon}(t/2)$, the following inequality holds:

$\displaystyle\|\widehat{A}-A\|$
$\displaystyle\leq{4\sqrt{2}}\left(\|\Sigma_{1}\|+\|\Sigma\|\right)\|\Sigma\|(1+\|\Sigma_{1}\|)\left(32B^{2}+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+t}{n}}$
$\displaystyle\quad+2V(1+\|\Sigma_{1}\|)\sqrt{F_{\varepsilon}(t/2)}.$

This result is obtained by bounding the estimation error $\|\widehat{A}-A\|$
with the estimation errors of the covariance matrix $\Sigma$ and the lagged
covariance matrix $\Sigma_{1}$, as described in Proposition 4.2. Note that it
is possible to extend the number of lags in this HMM model to larger than $1$.

###  4.4. Overparameterized Linear Regression

Herein, we study a linear regression problem with dependent and heavy-tail
covariates following the overparameterization framework developed by Bartlett
et al. (2020).

Let $(X_{\ell})_{\ell\in\mathbb{Z}}$ be a CBS as a $\mathbb{H}$-valued latent
process and $(Y_{\ell})_{\ell\in\mathbb{Z}}$ be a generated process as a
$\mathbb{H}$-valued covariate such that

$\displaystyle Y_{\ell}$ $\displaystyle=X_{\ell}+\varepsilon_{\ell},$ (14)

where $\varepsilon_{\ell}$ is an i.i.d. $\mathbb{H}$-valued noise variable
with a mean value of zero. In addition, we define $\theta^{*}\in\mathbb{H}$ as
a true unknown parameter and a covariance operator
$\Sigma=\mathbb{E}[Y_{\ell}Y_{\ell}^{\top}]$. For $\ell\in\mathbb{Z}$, we
consider an $\mathbb{R}$-valued random variable $Z_{\ell}$ to be a response
that follows the below model:

$\displaystyle Z_{\ell}$
$\displaystyle=\langle\theta^{*},Y_{\ell}\rangle+U_{\ell},$ (15)

where $U_{\ell}$ is an $\mathbb{R}$-valued independent random variable with a
mean of zero and a variance of $\sigma^{2}>0$.

The goal of the regression problem is to estimate $\theta^{*}$ from the
observations $(Z_{1},Y_{1}),...,(Z_{n},Y_{n})$. We introduce a design matrix
and operator as $\mathsf{Z}=(Z_{1},...,Z_{n})^{\top}\in\mathbb{R}^{n}$ and
$\mathsf{Y}:\mathbb{H}\to\mathbb{R}^{n}$ such that
$\mathsf{Y}^{\top}\theta=(Y_{1}^{\top}\theta,...,Y_{n}^{\top}\theta)^{\top}\in\mathbb{R}^{n}$
for $\theta\in\mathbb{H}$. Define
$\Pi_{\mathsf{Y}}:=\mathsf{Y}^{\top}(\mathsf{Y}\mathsf{Y}^{\top})^{-1}\mathsf{Y}$
and $\widehat{\Sigma}=\mathsf{Y}^{\top}\mathsf{Y}/n$.

To estimate $\theta^{*}$, we define a minimum norm estimator as:

$\displaystyle\widehat{\theta}=\operatornamewithlimits{argmin}_{\theta\in\mathbb{H}}\\{\|\theta\|^{2}:\mathsf{Y}^{\top}\mathsf{Y}\theta=\mathsf{Y}^{\top}\mathsf{Z}\\}=\mathsf{Y}^{\top}(\mathsf{Y}\mathsf{Y}^{\top})^{\dagger}\mathsf{Z},$
(16)

where † denotes the pseudo-inverse of operators. The excess risk of estimator
$\widehat{\theta}$ is measured using

$\displaystyle R(\widehat{\theta}):=\mathbb{E}_{(Z_{*},Y_{*})}[(Z_{*}-\langle
Y_{*},\widehat{\theta}\rangle)^{2}-(Z_{*}-\langle
Y_{*},{\theta}^{*}\rangle)^{2}],$ (17)

where $(Z_{*},Y_{*})$ is an i.i.d. copy of $(Z_{1},Y_{1})$ from the regression
model (15) and $\mathbb{E}_{(Z_{*},Y_{*})}[\cdot]$ is the expectation with
respect to $(Z_{*},Y_{*})$.

We present a technical assumption that specializes in the overparameterization
setting. Let $\Pi_{\Sigma}^{\perp}$ be a projection operator onto a linear
space spanned by vectors orthogonal to any eigenvector of $\Sigma$.

######  Assumption 3.

$\mathrm{dim}(\Pi_{\Sigma}^{\perp}(\mathsf{Y}))>n$ holds almost surely.

This assumption is identical to Assumption 1 in Bartlett et al. (2020) and is
intended to deal with cases where there are no degeneracies, such as perfect
dependence among the variables.

With this setting, we bound the risk of the estimator for the
overparameterized linear regression model.

######  Proposition 10.

Consider the linear regression model (15) with the process (14) by a CBS
$(X_{\ell})_{\ell\in\mathbb{Z}}$. Suppose that Assumption 3 holds. Consider
the estimator (16) and its excess risk (17). Then, for any $t\in(B^{2},n/c)$
with some $c>1$, at least $1-\exp(-t)-nF_{\varepsilon}(t/4)$, we have

$\displaystyle R(\widehat{\theta})$ $\displaystyle\leq
2\sqrt{2}c\|\theta^{*}\|^{2}\left\|\Sigma\right\|\left(2\tau+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+t}{n}}+V\sqrt{F_{\varepsilon}(t/4)}$
$\displaystyle\quad+ct\sigma^{2}\mathrm{tr}(C),$

where
$C=(\mathsf{Y}\mathsf{Y}^{\top})^{-1}\mathsf{Y}\Sigma\mathsf{Y}^{\top}(\mathsf{Y}\mathsf{Y}^{\top})^{-1}$.

This result indicates that we can bound the bias term of the risk of the
overparameterized linear regression estimator, even in the dependent and
heavy-tailed setting. Note that the last term $ct\sigma^{2}\mathrm{tr}(C)$
represents the variance of the risk, which converges to zero by removing
correlations and controlling for them using different techniques. This is
outside our interest, but see Lemma 11 in Bartlett et al. (2020) for further
details.

##  5\. Proofs for Main Results in Section 3

###  5.1. Outline

We first state two lemmas at the core of our proofs in Section 5.2. Lemma 11
appears in many forms in the proofs of the PAC-Bayes bounds (Catoni, 2007;
Alquier, 2021). For convenience, we use here the version stated in (Catoni and
Giulini, 2017; Zhivotovskiy, 2021). Lemma 12 is Rio’s version of Hoeffding’s
inequality (Rio, 2000) for weakly dependent random variables:

Then, we prove Theorem 4 in Section 5.3. To do so, we essentially follow the
techniques developed in (Catoni and Giulini, 2017; Zhivotovskiy, 2021).
However, both these studies rely on exponential inequalities for independent
random variables. Instead, we use Rio’s inequality, which requires the
boundedness assumption.

Then, in Section 5.4, we introduce a truncation function that transforms
unbounded matrices into bounded ones. We thus apply Theorem 4 to the truncated
matrices. Then, we control the effect of the truncation function to prove
Corollary 5.

###  5.2. Preliminary results

######  Lemma 11 (Catoni and Giulini (2017)).

Assume that $X$ is a random variable defined in a measurable space
$\left(\mathcal{X},\mathcal{A}\right)$, and $\left(\Theta,\mathcal{F}\right)$
is a measurable parameter space. Let $\mu$ be a random measure on
$\left(\Theta,\mathcal{F}\right)$ and $h:\mathcal{X}\times\Theta\to\mathbb{R}$
be a real-valued
$\mathcal{A}\otimes\mathcal{F}/\mathcal{B}\left(\mathbb{R}\right)$-measurable
function such that
$\mathbb{E}_{X}[\exp\left(h\left(X,\theta\right)\right)]<\infty$ for
$\mu$-almost all $\theta$. It holds that with probability at least $1-e^{-t}$,
for all the probability measures $\rho\ll\mu$ simultaneously,

$\displaystyle\mathbb{E}_{\rho}[h\left(X,\theta\right)]\leq\mathbb{E}_{\rho}\left[\log\mathbb{E}_{X}\left[\exp\left(h\left(X,\theta\right)\right)\right]\right]+\mathrm{KL}\left(\rho\|\mu\right)+t.$

###### Proof.

The proof is merely a descendant of the duality relationship.

$\displaystyle\mathbb{E}_{X}\left[\exp\left\\{\sup_{\rho\ll\mu}\left(\mathbb{E}_{\rho}\left[h\left(X,\theta\right)-\log\mathbb{E}_{X}[\exp(h\left(X,\theta\right))]\right]-\mathrm{KL}\left(\rho\|\mu\right)\right)\right\\}\right]$
$\displaystyle=\mathbb{E}_{X}\mathbb{E}_{\mu}\left[\exp\left(h\left(X,\theta\right)-\log\mathbb{E}_{X}[\exp(h\left(X,\theta\right))]\right)\right]$
$\displaystyle=\mathbb{E}_{X}\mathbb{E}_{\mu}\left[\frac{\exp(h\left(X,\theta\right))}{\mathbb{E}_{X}[\exp(h\left(X,\theta\right))]}\right]$
$\displaystyle=\mathbb{E}_{\mu}\mathbb{E}_{X}\left[\frac{\exp(h\left(X,\theta\right))}{\mathbb{E}_{X}[\exp(h\left(X,\theta\right))]}\right]$
$\displaystyle=1.$

We use Tonelli’s theorem to exchange the order of expectations. Then Markov’s
inequality leads to the inequality that holds with probability at least
$1-e^{-t}$;

$\displaystyle\sup_{\rho\ll\mu}\left(\mathbb{E}_{\rho}\left[h\left(X,\theta\right)-\log\mathbb{E}_{X}[\exp(h\left(X,\theta\right))]\right]-\mathrm{KL}\left(\rho\|\mu\right)\right)<t.$

This completes the proof. ∎

######  Lemma 12 (Hoeffding’ inequality applied to matrices (Rio, 2000)).

Let $\left\\{M_{1},\ldots,M_{n}\right\\}$ be a sequence of positive semi-
definite symmetric random matrices with
$\max_{\ell=1,..,n}\left\|M_{\ell}\right\|\leq\kappa^{2}$ almost surely for
some $\kappa>0$. Let us assume that Assumption 1 is satisfied. Then, for any
function $h\in{\rm Lip}_{n}(E,L)$ and for any $\lambda>0$ we have

$\displaystyle\mathbb{E}\left[\exp\left(\lambda
h(M_{1},\dots,M_{n})-\lambda\mathbb{E}[h(M_{1},\dots,M_{n})]\right)\right]$
$\displaystyle\leq\exp\left(\frac{\lambda^{2}L^{2}\sum_{\ell=1}^{n}\left(2\kappa+\Gamma_{\ell,n}\right)^{2}}{8n^{2}}\right).$

###  5.3. Bounded Case (Theorem 4)

###### Proof of Theorem 4.

The proof consists of truncation of $\rho=\rho_{u,v}$ given by Zhivotovskiy
(2021) and the lemma above obtained using duality.

(Step 1) Let us assume that $\Sigma$ is invertible. Otherwise, we only need to
consider a lower-dimensional subspace, and the proof is indifferent to the
case with invertible $\Sigma$. Let $\mu$ denote a $2p$-dimensional product
measure of two $p$-dimensional Gaussian measures with a zero mean and
convariance $\left(2\mathbf{r}\left(\Sigma\right)\right)^{-1}\Sigma$. We
define $\mathbb{S}^{p-1}$ as a unit ball in $\mathbb{R}^{p}$. Let us set
$u,v\in\Sigma^{1/2}\mathbb{S}^{p-1}$ and define $f_{u},f_{v}$ as probability
density functions with respect to the Lebesgue measure such that

$\displaystyle f_{u}\left(x\right)$
$\displaystyle=\frac{\exp\left(-\mathbf{r}\left(\Sigma\right)\left(x-u\right)^{\top}\Sigma^{-1}\left(x-u\right)\right)\mathbf{1}\\{\left\|x-u\right\|\leq\sqrt{\left\|\Sigma\right\|}\\}}{\int\exp\left(-\mathbf{r}\left(\Sigma\right)\left(x^{\prime}-u\right)^{\top}\Sigma^{-1}\left(x^{\prime}-u\right)\right)\mathbf{1}\\{\left\|x^{\prime}-u\right\|\leq\sqrt{\left\|\Sigma\right\|}\\}\mathrm{d}x^{\prime}},$
$\displaystyle f_{v}\left(x\right)$
$\displaystyle=\frac{\exp\left(-\mathbf{r}\left(\Sigma\right)\left(x-u\right)^{\top}\Sigma^{-1}\left(x-v\right)\right)\mathbf{1}\\{\left\|x-v\right\|\leq\sqrt{\left\|\Sigma\right\|}\\}}{\int\exp\left(-\mathbf{r}\left(\Sigma\right)\left(x^{\prime}-v\right)^{\top}\Sigma^{-1}\left(x^{\prime}-v\right)\right)\mathbf{1}\\{\left\|x^{\prime}-v\right\|\leq\sqrt{\left\|\Sigma\right\|}\\}\mathrm{d}x^{\prime}}.$

Here, $\mathbf{1}\\{\mathcal{E}\\}$ is an indicator function which is $1$ if
an event $\mathcal{E}$ is true and $0$ otherwise. Assume that the independent
random vectors $\theta,\eta$ have densities $f_{u}$ and $f_{v}$, then
$\mathbb{E}[\left(\theta,\eta\right)]=\left(u,v\right)$ by the symmetricity of
$f_{u},f_{v}$, and
$\max\left\\{\left\|\theta\right\|,\left\|\eta\right\|\right\\}\leq
2\sqrt{\left\|\Sigma\right\|}$ almost surely. Let $\rho_{u,v}$ be a
probability measure of $\theta,\eta$ given by
$\rho_{u,v}\left(\mathrm{d}x,\mathrm{d}y\right)=f_{u}\left(x\right)f_{v}\left(y\right)\mathrm{d}x\mathrm{d}y,x,y\in\mathbb{R}^{d}$.
In the proof of Theorem 1 of Zhivotovskiy (2021), it is shown that

$\displaystyle\mathrm{KL}\left(\rho_{u,v}\|\mu\right)\leq 2\log
2+2\mathbf{r}\left(\Sigma\right).$

(Step 2) Let $f\left(A,\theta,\eta\right):=\theta^{\top}A\eta$ for any
$A\in\mathbb{R}^{p}\otimes\mathbb{R}^{p}$ and $\theta,\eta\in\mathbb{R}^{p}$.
Lemma 12 with $h(M_{1},\dots,M_{n})=\sum_{\ell=1}^{n}f(M_{\ell},\theta,\eta)$
gives that for any $\lambda>0$,

$\displaystyle\mathbb{E}_{\mathbf{M}}\left[\exp\left(\lambda\sum_{\ell=1}^{n}f\left(M_{\ell},\theta,\eta\right)\right)\right]$
$\displaystyle=\mathbb{E}_{\mathbf{M}}\left[\exp\left(\lambda\sum_{\ell=1}^{n}\theta^{\top}M_{\ell}\eta\right)\right]$
$\displaystyle\leq\exp\left(n\lambda\theta^{\top}\Sigma\eta+\frac{n^{2}\lambda^{2}\left\|\theta\right\|^{2}\left\|\eta\right\|^{2}\left(2\kappa^{2}+\Gamma_{n}\right)^{2}}{8n}\right),$

because for any
$A_{1},\ldots,A_{n},B_{1},\ldots,B_{n}\in\mathbb{R}^{p}\otimes\mathbb{R}^{p}$,

$\displaystyle\left|h\left(A_{1},\dots,A_{n}\right)-h\left(B_{1},\dots,B_{n}\right)\right|$
$\displaystyle=\left|\theta^{\top}\left(\sum_{\ell=1}^{n}\left(A_{\ell}-B_{\ell}\right)\right)\eta\right|$
$\displaystyle\leq\left\|\theta\right\|\left\|\eta\right\|\sum_{\ell=1}^{n}\left\|A_{\ell}-B_{\ell}\right\|.$

It holds that

$\displaystyle\frac{1}{n}\mathbb{E}_{\rho_{u,v}}\left[\log\mathbb{E}_{\mathbf{M}}\left[\exp\left(\lambda\sum_{\ell=1}^{n}f\left(M_{\ell},\theta,\eta\right)\right)\right]\right]$
$\displaystyle\leq\frac{1}{n}\mathbb{E}_{\rho_{u,v}}\left[n\lambda\theta^{\top}\Sigma\eta+\frac{n^{2}\lambda^{2}\left\|\theta\right\|^{2}\left\|\eta\right\|^{2}\left(2\kappa^{2}+\Gamma_{n}\right)^{2}}{8n}\right]$
$\displaystyle=\mathbb{E}_{\rho_{u,v}}\left[\lambda\theta^{\top}\Sigma\eta+\frac{\lambda^{2}\left\|\theta\right\|^{2}\left\|\eta\right\|^{2}\left(2\kappa^{2}+\Gamma_{n}\right)^{2}}{8}\right]$
$\displaystyle\leq\lambda u^{\top}\Sigma
v+\frac{\lambda^{2}\left(2\sqrt{\left\|\Sigma\right\|}\right)^{4}\left(2\kappa^{2}+\Gamma_{n}\right)^{2}}{8}$
$\displaystyle=\lambda u^{\top}\Sigma
v+2\lambda^{2}\left\|\Sigma\right\|^{2}\left(2\kappa^{2}+\Gamma_{n}\right)^{2}.$

The last inequality follows the fact
$\max\left\\{\left\|\theta\right\|,\left\|\eta\right\|\right\\}\leq
2\sqrt{\left\|\Sigma\right\|}$. Therefore, from Lemma 11 with
$h\left(M_{1},\ldots,M_{n},\theta,\eta\right)=\lambda\sum_{\ell=1}^{n}f\left(M_{\ell},\theta,\eta\right)$
and the fact that $\log 2\leq\mathbf{r}\left(\Sigma\right)$ for any $\Sigma$,
we obtain

$\displaystyle\frac{1}{n}\sum_{\ell=1}^{n}\lambda u^{\top}M_{\ell}v\leq\lambda
u^{\top}\Sigma
v+2\lambda^{2}\left\|\Sigma\right\|^{2}\left(2\kappa^{2}+\Gamma_{n}\right)^{2}+\frac{4\mathbf{r}\left(\Sigma\right)+t}{n},$

simultaneously for all $u,v$ with probability at least $1-e^{-t}$. By choosing

$\displaystyle\lambda=\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+t}{2n\left\|\Sigma\right\|^{2}\left(2\kappa^{2}+\Gamma_{n}\right)^{2}}},$

we obtain a bound such that

$\displaystyle\left\|\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right\|\leq
2\sqrt{2}\left\|\Sigma\right\|\left(2\kappa^{2}+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+t}{n}}.$

This is our claim. ∎

###  5.4. Heavy-Tailed Case (Corollary 5)

We firstly present a truncation function, which is necessary to our
robustification strategy for heavy-tailed random matrices.

######  Definition 3.

For any $\tau>0$, we definethe truncation function
$\psi_{\tau}:\mathbb{R}\rightarrow\mathbb{R}$ as follows:

$\psi_{\tau}(x)=\left\\{\begin{array}[]{l}-\tau\text{ if }x<\tau,\\\ x\text{
if }|x|\leq\tau,\\\ \tau\text{ if }x>\tau.\end{array}\right.$

There is a standard method to extend a real function
$\mathbb{R}\rightarrow\mathbb{R}$ to a function of symmetric matrices
$\mathcal{S}\rightarrow\mathcal{S}$, by applying the function to the
eigenvalues of the matrix. More precisely, given $A\in\mathcal{S}$, $A$ can be
written as

$A=Q\left(\begin{array}[]{c c c}\lambda_{1}&\dots&0\\\ \vdots&\ddots&\vdots\\\
0&\dots&\lambda_{p}\end{array}\right)Q^{T},$

for some matrix $Q$ such that $QQ^{T}=I$, where
$(\lambda_{1},\dots,\lambda_{p})$ are the eigenvalues of $A$. We then define
$\psi_{\tau}(A)$ by

$\psi_{\tau}(A)=Q\left(\begin{array}[]{c c
c}\psi_{\tau}(\lambda_{1})&\dots&0\\\ \vdots&\ddots&\vdots\\\
0&\dots&\psi_{\tau}(\lambda_{p})\end{array}\right)Q^{T}.$

We can now state the first corollary of Theorem 4.

######  Corollary 13.

Assume that $\left\\{M_{1},\ldots,M_{n}\right\\}$ satisfies Assumption 1. Fix
$\tau>0$. Then for all $t>0$, it holds that

$\displaystyle\left\|\frac{1}{n}\sum_{\ell=1}^{n}(\psi_{\tau}(M_{\ell})-\mathbb{E}[\psi_{\tau}(M_{\ell})])\right\|\leq
2\sqrt{2}\left\|\Sigma\right\|\left(2\tau+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+t}{n}}.$

with probability at least $1-e^{-t}$.

###### Proof of Corollary 13.

Because $x\mapsto\psi_{\tau}(x)$ is $1$-Lipschitz, the sequence of matrices
$\\{\psi_{\tau}(M_{1})-\mathbb{E}[\psi_{\tau}(M_{1})],\dots,\psi_{\tau}(M_{n})-\mathbb{E}[\psi_{\tau}(M_{1})]\\}$
satisfies Assumption 1. As they are bounded by $\tau$ and all have the same
expectation (zero), so we can apply Theorem 4 to yield the result. ∎

As stated in the outline of the proof, we now have to understand what is the
difference between the expectation of the truncated matrices, and the
expectations of the (non-truncated) matrices themselves.

######  Proposition 14.

Fix $\tau>0$. Under Assumption 2 we have

$\max_{1\leq\ell\leq
n}\left\|\mathbb{E}[\psi_{\tau}(M_{\ell})]-\mathbb{E}[M_{\ell}]\right\|\leq
V\sqrt{F(t)}.$

###### Proof of Proposition 14.

For any $\ell=1,...,n$, we have

$\displaystyle\left\|\mathbb{E}[\psi_{\tau}(M_{\ell})]-\mathbb{E}[M_{\ell}]\right\|$
$\displaystyle\leq\mathbb{E}[\left\|\psi_{\tau}(M_{\ell})-M_{\ell}\right\|]$
$\displaystyle=\mathbb{E}[(\|M_{\ell}\|-\tau)\mathbf{1}_{\\{\|M_{\ell}\|>\tau\\}}]$
$\displaystyle\leq\mathbb{E}[\|M_{\ell}\|\mathbf{1}_{\\{\|M_{\ell}\|>\tau\\}}]$
$\displaystyle\leq\sqrt{\mathbb{E}[\|M_{\ell}\|^{2}]\mathbb{P}(\|M_{\ell}\|>\tau)}$
$\displaystyle\leq V\sqrt{F(\tau)}.$

∎

######  Corollary 15.

Assume that $\\{M_{1},\dots,M_{n}\\}$ satisfies Assumptions 1 and 2, and
$\mathbb{E}[M_{\ell}]=\Sigma$. Fix $\tau>0$. For all $t>0$, it holds that

$\displaystyle\left\|\frac{1}{n}\sum_{\ell=1}^{n}\psi_{\tau}(M_{\ell})-\Sigma\right\|\leq
2\sqrt{2}\left\|\Sigma\right\|\left(2\tau+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+t}{n}}+V\sqrt{F(\tau)}.$

with probability at least $1-e^{-t}$.

###### Proof of Corollary 15.

First, we decompose the norm as

$\displaystyle\left\|\frac{1}{n}\sum_{\ell=1}^{n}\psi_{\tau}(M_{\ell})-\Sigma\right\|$
$\displaystyle\leq\left\|\frac{1}{n}\sum_{\ell=1}^{n}(\psi_{\tau}(M_{\ell})-\mathbb{E}[\psi_{\tau}(M_{\ell})])\right\|+\left\|\frac{1}{n}\sum_{\ell=1}^{n}(\mathbb{E}[\psi_{\tau}(M_{\ell})]-\mathbb{E}[M_{\ell}])\right\|$
$\displaystyle\leq\left\|\frac{1}{n}\sum_{\ell=1}^{n}[\psi_{\tau}(M_{\ell})-\mathbb{E}[\psi_{\tau}(M_{\ell})]]\right\|+\frac{1}{n}\sum_{\ell=1}^{n}\left\|\mathbb{E}[\psi_{\tau}(M_{\ell})]-\Sigma\right\|,$

where we use the triangle inequality in the first line, and Jensen’s
inequality and $\mathbb{E}[M_{\ell}]=\Sigma$ in the second line. As Assumption
1 is satisfied, we can upper bound the first term with probability $1-e^{-t}$
by Corollary 13. Because Assumption 2 is also satisfied, we can bound the
second term, Proposition 14. ∎

Note that Corollary 15 already provides an estimation result for $\Sigma$ when
matrices $M_{\ell}$ are unbounded. However, in contrast to Corollary 5, not
only does the bound depend on $\tau$ but the estimator
$\frac{1}{n}\sum_{\ell=1}^{n}\psi_{\tau}(M_{\ell})$ does as well. A mistake in
the choice of $\tau$ can lead to poor estimation in practice.

To control the distance between this estimator
$\frac{1}{n}\sum_{\ell=1}^{n}\psi_{\tau}(M_{\ell})$, and the standard
estimator $\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}$, we prove the following
proposition.

######  Proposition 16.

Under Assumption 2 we have

$\mathbb{P}\left(\left\|\frac{1}{n}\sum_{\ell=1}^{n}\psi_{\tau}(M_{\ell})-\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}\right\|\neq
0\right)\leq nF(\tau).$

###### Proof of Proposition 16.

We have

$\displaystyle\mathbb{P}\left(\left\|\frac{1}{n}\sum_{\ell=1}^{n}\psi_{\tau}(M_{\ell})-\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}\right\|\neq
0\right)$
$\displaystyle\leq\mathbb{P}\left(\frac{1}{n}\sum_{\ell=1}^{n}\left\|\psi_{\tau}(M_{\ell})-M_{\ell}\right\|\geq
0\right)$
$\displaystyle=\mathbb{P}\left(\exists\ell:\left\|\psi_{\tau}(M_{\ell})-M_{\ell}\right\|\geq
0\right)$ $\displaystyle\leq
n\mathbb{P}\left(\left\|\psi_{\tau}(M_{\ell})-M_{\ell}\right\|\geq 0\right)$
$\displaystyle\leq nF(\tau).$

∎

We are now in a position to prove Corollary 5.

###### Proof of Corollary 5.

Using the triangle inequality,

$\left\|\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right\|\leq\left\|\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\frac{1}{n}\sum_{\ell=1}^{n}\psi_{\tau}(M_{\ell})\right\|+\left\|\frac{1}{n}\sum_{\ell=1}^{n}\psi_{\tau}(M_{\ell})-\Sigma\right\|.$

We remind that the assumptions of Corollary 5 include:
$\\{M_{1},\dots,M_{n}\\}$ satisfy Assumptions 1 and 2, and
$\mathbb{E}[M_{\ell}]=\Sigma$, which us allows to use Corollary 15 to upper
bound the second term with probability $1-e^{-t}$. This also allows for the
use of Proposition 16 to prove that the first term will be null with
probability at least $1-nF(\tau)$. ∎

###  5.5. Infinite-Dimensional Case (Theorem 6)

###### Proof of Theorem 6.

For a sequence of $\mathbb{H}\otimes\mathbb{H}$-valued positive semi-definite
symmetric random operators $\left\\{M_{1},\ldots,M_{n}\right\\}$ with
$\mathbb{E}\left[M_{\ell}\right]=\Sigma$ and $\max_{1\leq\ell\leq
n}\left\|M_{\ell}\right\|\leq\kappa^{2}$ almost surely for some $\kappa>0$
satisfying Assumption 1,

$\displaystyle P\left(\sup_{\begin{subarray}{c}u_{k}\in\mathbb{H}_{k}\\\
\left\|u_{k}\right\|=1\end{subarray}}\left|\left\langle\left(\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right)u_{k},u_{k}\right\rangle\right|\geq
2\sqrt{2}\left\|\Sigma\right\|\left(2\kappa^{2}+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+t}{n}}\right)\leq
e^{-t},$

because for $\Sigma_{k}$ such that
$\Sigma_{k}^{\left(j_{1},j_{2}\right)}:=\mathbb{E}[M_{\ell}^{\left(j_{1},j_{2}\right)}]$
and $\Sigma:=\mathbb{E}[M_{\ell}]$,
$\left\|\Sigma_{k}\right\|\leq\left\|\Sigma\right\|$ and
$\mathrm{tr}\left(\Sigma_{k}\right)\leq\mathrm{tr}\left(\Sigma\right)$, and
$\Gamma_{n}$ is also uniform for each, as we can see from the proof. Note that
for any $c\geq 0$ and $k\in\mathbb{N}$,

$\displaystyle\left\\{\sup_{\begin{subarray}{c}u_{k}\in\mathbb{H}_{k}\\\
\left\|u_{k}\right\|=1\end{subarray}}\left|\left\langle\left(\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right)u_{k},u_{k}\right\rangle\right|\geq
c\right\\}$
$\displaystyle\subset\left\\{\sup_{\begin{subarray}{c}u_{k+1}\in\mathbb{H}_{k+1}\\\
\left\|u_{k+1}\right\|=1\end{subarray}}\left|\left\langle\left(\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right)u_{k+1},u_{k+1}\right\rangle\right|\geq
c\right\\},$

and

$\displaystyle\lim_{k\to\infty}\left\\{\sup_{\begin{subarray}{c}u_{k}\in\mathbb{H}_{k}\\\
\left\|u_{k}\right\|=1\end{subarray}}\left|\left\langle\left(\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right)u_{k},u_{k}\right\rangle\right|\geq
c\right\\}=\left\\{\left\|\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right\|\geq
c\right\\}.$

The continuity of $P$ leads to

$\displaystyle
P\left(\left\|\frac{1}{n}\sum_{\ell=1}^{n}M_{\ell}-\Sigma\right\|\geq
2\sqrt{2}\left\|\Sigma\right\|\left(2\kappa^{2}+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma\right)+t}{n}}\right)\leq
e^{-t}.$

Then, using the same approach to extend Theorem 4 to Corollary 5, we obtain
the statement. ∎

##  6\. Conclusion

We study the perturbation of an empirical mean of random matrices from its
expected value such that they are dependent and the distribution has a heavy-
tail. The upper bound derived here is independent of dimension of the
matrices, then is instead mainly described by a trace of the expectation and a
tail of the distribution. In addition, a constant part of the upper bound
increases with the strength of the dependence. The proof here is based on a
variational inequality and robustification by truncation. Our result is
applied to the estimation problem of covariance operators/matrices, the
parameter estimation in linear hidden Markov models, and linear regression
under overparameterization.

The limitation of our result is the tightness of the obtained upper bound. It
is difficult to achieve lower bounds when random matrices are dependent and
heavy-tailed, while some lower bounds are known when they are independent and
each element is Gaussian. The lower bound in this case is an interesting
subject for future research.

##  Appendix A Proof for Examples

###### Proof of Proposition 1.

Let $f:E\rightarrow E$ be a $1$-Lipschitz function and define
$\mathcal{G}_{\ell}=\sigma(f(M_{1}),\dots,f(M_{\ell}))$. Our objective is to
prove that, for any $g\in{\rm Lip}_{n-\ell}(\mathcal{S},1)$, we have

$|\mathbb{E}[g(f(M_{\ell+1}),\dots,f(M_{n}))|\mathcal{G}_{\ell}]-\mathbb{E}[g(f(M_{\ell+1},\dots,f(M_{n}))]|\leq\Gamma_{\ell,n}.$
(18)

Let $h$ be defined by $h(a_{1},\dots,a_{\ell})=g(f(a_{1}),\dots,f(a_{\ell}))$.
Then $h\in{\rm Lip}_{n-\ell}(\mathcal{S},1)$. Indeed,

$\displaystyle\left|h(a_{1},\dots,a_{\ell})-h(b_{1},\dots,b_{\ell})\right|$
$\displaystyle=|g(f(a_{1}),\dots,f(a_{\ell}))-g(f(b_{1}),\dots,f(b_{\ell}))$
$\displaystyle\leq L\sum_{i=1}^{\ell}\|f(a_{i})-f(b_{i})\|_{E}$
$\displaystyle\leq L\sum_{i=1}^{\ell}\|a_{i}-b_{i}\|_{E},$

where we used respectively the definition of $h$, the fact that $g\in{\rm
Lip}_{n-\ell}(\mathcal{S},1)$ and the fact that $f$ is $1$-Lipschitz. Thus, as
we know that $(M_{1},\dots,M_{n})$ satisfies Assumption 1 and $h\in{\rm
Lip}_{n-\ell}(\mathcal{S},1)$, then

$|\mathbb{E}[h(M_{\ell+1},\dots,M_{n})|\mathcal{F}_{\ell}]-\mathbb{E}[h(M_{\ell+1},\dots,M_{n})]|\leq\Gamma_{\ell,n}$

that we can rewrite as

$|\mathbb{E}[g(f(M_{\ell+1}),\dots,f(M_{n}))|\mathcal{F}_{\ell}]-\mathbb{E}[g(f(M_{\ell+1},\dots,f(M_{n}))]|\leq\Gamma_{\ell,n}.$
(19)

This is almost (18), however, the conditional expectation is not with respect
to the correct $\sigma$-algebra. This is easily fixed, because
$\mathcal{G}_{\ell}\subseteq\mathcal{F}_{\ell}$. Thus,

$\displaystyle\bigl{|}\mathbb{E}[g(f(M_{\ell+1}),\dots,f(M_{n}))|\mathcal{G}_{\ell}]-\mathbb{E}[g(f(M_{\ell+1},\dots,f(M_{n}))]\bigr{|}$
$\displaystyle=\bigl{|}\mathbb{E}[\mathbb{E}[g(f(M_{\ell+1}),\dots,f(M_{n}))|\mathcal{F}_{\ell}]|\mathcal{G}_{\ell}]-\mathbb{E}[g(f(M_{\ell+1},\dots,f(M_{n}))]\bigr{|}$
$\displaystyle\leq\mathbb{E}\left[\bigl{|}\mathbb{E}[g(f(M_{\ell+1}),\dots,f(M_{n}))|\mathcal{F}_{\ell}]-\mathbb{E}[g(f(M_{\ell+1},\dots,f(M_{n}))]\bigr{|}|\mathcal{G}_{\ell}\right]$
$\displaystyle\leq\Gamma_{\ell,n},$

by using (19). ∎

###### Proof of Proposition 3.

We define $(\bar{\xi}_{\ell})_{\ell\in\mathbb{Z}}$ as an independent copy
$\Xi$. We fix $\ell\in\\{1,\dots,n\\}$, we are going to check (1). In order to
do so, we define, for $m>\ell$,

$\bar{X}_{m}=C(\xi_{m},\xi_{m-1},\dots,\xi_{\ell+1},\bar{\xi}_{\ell},\bar{\xi}_{\ell-1},\bar{\xi}_{\ell-2},\dots),$

and $\bar{Y}_{m}=\bar{X}_{m}+\varepsilon_{m}$. We put
$\mathcal{G}_{\ell}=\sigma(\xi_{\ell},\xi_{\ell-1},\xi_{\ell-2},\dots;\varepsilon_{\ell},\varepsilon_{\ell-1},\dots)$.
Then, for $g\in{\rm Lip}_{n-\ell}(\mathcal{S},1)$, we have

$\displaystyle\mathbb{E}[g(M_{\ell+1},\dots,M_{n})|\mathcal{F}_{\ell}]-\mathbb{E}[g(M_{\ell+1},\dots,M_{n})]$
$\displaystyle=\mathbb{E}[\mathbb{E}[g(M_{\ell+1},\dots,M_{n})|\mathcal{G}_{\ell}]-\mathbb{E}[g(M_{\ell+1},\dots,M_{n})]|\mathcal{F}_{\ell}],$

and we will prove an upper bound on
$\mathbb{E}[g(M_{\ell+1},\dots,M_{n})|\mathcal{G}_{\ell}]-\mathbb{E}[g(M_{\ell+1},\dots,M_{n})]$.
Hence, we have

$\displaystyle\mathbb{E}[g(M_{\ell+1},\dots,M_{n})|\mathcal{G}_{\ell}]-\mathbb{E}[g(M_{\ell+1},\dots,M_{n})]$
$\displaystyle=\mathbb{E}[g(\bar{Y}_{\ell+1}\bar{Y}_{\ell+1}^{\top},\dots,\bar{Y}_{n}\bar{Y}_{n}^{\top})-g(Y_{\ell+1}Y_{\ell+1}^{\top},\dots,Y_{n}Y_{n}^{\top})|\mathcal{G}_{\ell}]$
$\displaystyle\leq\sum_{m=\ell+1}^{n}\left\|\mathbb{E}\left[\bar{Y}_{m}\bar{Y}_{m}^{\top}-Y_{m}Y_{m}^{\top}|\mathcal{G}_{\ell}\right]\right\|$
$\displaystyle=\sum_{m=\ell+1}^{n}\left\|\mathbb{E}\left[(\bar{X}_{m}+\varepsilon_{m})(\bar{X}_{m}+\varepsilon_{m})^{\top}-(X_{m}+\varepsilon_{m})(X_{m}+\varepsilon_{m})^{\top}|\mathcal{G}_{\ell}\right]\right\|$
$\displaystyle=\sum_{m=\ell+1}^{n}\left\|\mathbb{E}\left[\bar{X}_{m}\bar{X}_{m}^{\top}-X_{m}X_{m}^{\top}|\mathcal{G}_{\ell}\right]\right\|$
$\displaystyle=\sum_{m=\ell+1}^{n}\left\|\mathbb{E}\left[\bar{X}_{m}\bar{X}_{m}^{\top}-\bar{X}_{m}X_{m}^{\top}+\bar{X}_{m}X_{m}^{\top}-X_{m}X_{m}^{\top}|\mathcal{G}_{\ell}\right]\right\|$
$\displaystyle\leq\sum_{m=\ell+1}^{n}\biggl{(}\left\|\mathbb{E}\left[\bar{X}_{m}\bar{X}_{m}^{\top}-\bar{X}_{m}X_{m}^{\top}|\mathcal{G}_{\ell}\right]\right\|+\left\|\mathbb{E}\left[\bar{X}_{m}X_{m}^{\top}-X_{m}X_{m}^{\top}|\mathcal{G}_{\ell}\right]\right\|\biggr{)}$
$\displaystyle\leq\sum_{m=\ell+1}^{n}B\biggl{(}\left\|\mathbb{E}\left[\bar{X}_{m}^{\top}-X_{m}^{\top}|\mathcal{G}_{\ell}\right]\right\|+\left\|\mathbb{E}\left[\bar{X}_{m}-X_{m}|\mathcal{G}_{\ell}\right]\right\|\biggr{)}.$

Then, we obtain

$\displaystyle\left\|\mathbb{E}\left[\bar{X}_{m}-X_{m}|\mathcal{G}_{\ell}\right]\right\|$
$\displaystyle=\left\|\mathbb{E}\left[C(\xi_{m},\xi_{m-1},\dots,\xi_{\ell+1},\bar{\xi_{\ell}},\bar{\xi}_{\ell-1},\dots)-C(\xi_{m},\xi_{m-1},\dots,\xi_{\ell+1},\xi_{\ell},\xi_{\ell-1},\dots)|\mathcal{G}_{\ell}\right]\right\|$
$\displaystyle\leq\sum_{i=m-\ell}^{\infty}\alpha_{i}\mathbb{E}\left[\|\bar{\xi}_{m-i}-\xi_{m-i}\||\mathcal{G}_{\ell}\right]\leq
2\sum_{i=m-\ell}^{\infty}\alpha_{i}B_{\xi}$

and thus,

$\displaystyle\mathbb{E}[g(M_{\ell+1},\dots,M_{n})|\mathcal{G}_{\ell}]-\mathbb{E}[g(M_{\ell+1},\dots,M_{n})]$
$\displaystyle\leq\sum_{m=\ell+1}^{n}\left[4B\sum_{i=m-\ell}^{\infty}\alpha_{i}B_{\xi}\right]$
$\displaystyle\leq 4B\sum_{i=\ell+1}^{\infty}\min(i,n)\alpha_{i}B_{\xi}.$

Thus, (1) is satisfied with
$\Gamma_{\ell,n}=4BB_{\xi}\sum_{i=\ell+1}^{\infty}\min(i,n)\alpha_{i}$. Let us
now check Assumption 2. We have obviously:

$\displaystyle\mathbb{P}(\|M_{\ell}\|\geq t)$
$\displaystyle=\mathbb{P}(\|(X_{\ell}+\varepsilon_{\ell})(X_{\ell}+\varepsilon_{\ell})^{\top}\|\geq
t)$ $\displaystyle=\mathbb{P}(\|X_{\ell}+\varepsilon_{\ell}\|^{2}\geq t)$
$\displaystyle=\mathbb{P}(\|X_{\ell}+\varepsilon_{\ell}\|\geq\sqrt{t})$
$\displaystyle\leq\mathbb{P}(\|X_{\ell}\|\geq\sqrt{t}/2)+\mathbb{P}(\|\varepsilon_{\ell}\|\geq\sqrt{t}/2)$
$\displaystyle\leq\mathbf{1}_{\\{t\leq
4B^{2}\\}}+\mathbb{P}(\|\varepsilon_{\ell}\|\geq\sqrt{t}/2),$

which ends the proof. ∎

###### Proof of Proposition 8.

Since $(X_{\ell})_{\ell\in\mathbb{N}}$ is a CBS, we have
$X_{\ell}=C(\xi_{\ell},\xi_{\ell-1},\xi_{\ell-2},\dots)$ with

$\|C(a_{1},a_{2},\dots)-C(b_{1},b_{2},\dots)\|\leq\sum_{\ell=1}^{\infty}\alpha_{\ell}\|a_{\ell}-b_{\ell}\|\text{
and }\mathcal{A}:=\sum_{\ell=1}^{\infty}\alpha_{\ell}<\infty.$

Using the form, we show that
$(\widetilde{X}_{\ell})_{\ell\in\mathbb{N}}:=((X_{\ell},X_{\ell+1})^{\top})_{\ell\in\mathbb{N}}$
is also a CBS, since we have

$\widetilde{X}_{\ell}=(C(\xi_{t},\xi_{t-1},\xi_{t-2},\dots),C(\xi_{t-1},\xi_{t-2},\xi_{t-3},\dots))=D(\xi_{t},\xi_{t-1},\xi_{t-2},\dots)$

with some function $D$ which satisfies

$\|D(a_{1},a_{2},\dots)-D(b_{1},b_{2},\dots)\|\leq\sum_{\ell=1}^{\infty}(\alpha_{\ell}+\alpha_{\ell+1})\|a_{\ell}-b_{\ell}\|.$

Since $(\widetilde{X}_{\ell})_{\ell\in\mathbb{N}}$ is a CBS, Proposition 3
proves that $(M_{1},...,M_{\ell-1})$ satisfies Assumption 1 with
$\Gamma_{\ell,n}=8BB_{\xi}\sum_{i=\ell+1}^{n}\min(i,n)\alpha_{i}$ and
$\Gamma_{n}:=8BB_{\xi}\sum_{i=2}^{n}\min(i,n)\alpha_{i}$.

For Assumption 2, we utilize the fact that the largest eigenvalue of a matrix
is no more than a sum of largest eigenvalues of its submatrices and obtain

$\displaystyle\mathbb{P}(\|M_{\ell}\|\geq t)$
$\displaystyle\leq\mathbb{P}(\|(X_{\ell}+\varepsilon_{\ell})(X_{\ell}+\varepsilon_{\ell})^{\top}\|\geq
t/4)$
$\displaystyle\quad+\mathbb{P}(\|(X_{\ell}+\varepsilon_{\ell})(X_{\ell+1}+\varepsilon_{\ell+1})^{\top}\|\geq
t/2)$
$\displaystyle\quad+\mathbb{P}(\|(X_{\ell+1}+\varepsilon_{\ell+1})(X_{\ell+1}+\varepsilon_{\ell+1})^{\top}\|\geq
t/4)$ $\displaystyle=2\mathbb{P}(\|X_{\ell}+\varepsilon_{\ell}\|^{2}\geq
t/4)+\mathbb{P}(\|(X_{\ell}+\varepsilon_{\ell})(X_{\ell+1}+\varepsilon_{\ell+1})^{\top}\|\geq
t/2)$ $\displaystyle\leq
2\mathbb{P}(\|X_{\ell}+\varepsilon_{\ell}\|\geq\sqrt{t}/2)+\mathbb{P}(\|X_{\ell}+\varepsilon_{\ell}\|\|X_{\ell+1}+\varepsilon_{\ell+1}\|\geq
t/2)$ $\displaystyle\leq
2\mathbb{P}(\|X_{\ell}+\varepsilon_{\ell}\|\geq\sqrt{t}/2)+2\mathbb{P}(\|X_{\ell}+\varepsilon_{\ell}\|\geq\sqrt{t/2})$
$\displaystyle\leq
4\mathbb{P}(\|X_{\ell}\|\geq\sqrt{t/2})+4\mathbb{P}(\|\varepsilon_{\ell}\|\geq\sqrt{t/2})$
$\displaystyle\leq 4\mathbf{1}_{\\{t\leq
4B^{2}\\}}+4\mathbb{P}(\|\varepsilon_{\ell}\|\geq\sqrt{t/2}).$

Hence, Assumption 2 holds $F(\tau)=4\mathbf{1}_{\\{t\leq
2B^{2}\\}}+4\mathbb{P}(\|\varepsilon_{\ell}\|\geq\sqrt{t/2})$. Thus, Corollary
5 shows the first statement.

Finally, the fact $\left\|\Sigma_{0:1}\right\|\leq\|\Sigma_{1}\|+\|\Sigma\|$
yields the second statement. ∎

###### Proof of Proposition 9.

First, we confirm that $(X_{\ell})_{\ell\in\mathbb{Z}}$ is a CBS in Example 1
by its definition. Hence, by Proposition 2, a sequence of matrices generated
by $Y_{\ell}Y_{\ell}^{\top}$ satisfies Assumption 1 and 2.

We show that the estimation error $\|\widehat{A}-A\|$ is bounded by estimation
error of $\widehat{\Sigma}$ and $\widehat{\Sigma}_{1}$. We bound the error as

$\displaystyle\|\widehat{A}-A\|$
$\displaystyle=\|(\widehat{\Sigma}_{1}-\Sigma_{1})(\widehat{\Sigma}+I)^{-1}+\Sigma_{Y,1}((\widehat{\Sigma}+I)^{-1}-({\Sigma}+I)^{-1})\|$
$\displaystyle\leq\|\widehat{\Sigma}_{1}-\Sigma_{1}\|\|(\widehat{\Sigma}+I)^{-1}\|+\|\Sigma_{1}({\Sigma}+I)^{-1}(\Sigma-\widehat{\Sigma})(\widehat{\Sigma}+I)^{-1}\|$
$\displaystyle\leq\|\widehat{\Sigma}_{1}-\Sigma_{1}\|+\|\Sigma-\widehat{\Sigma}\|\|\Sigma_{1}\|.$
(20)

Here, we use the facts $\|(\widehat{\Sigma}+I)^{-1}\|\leq 1$ and
$\|({\Sigma}+I)^{-1}\|\leq 1$.

We combine the above results. By the same discussion for Proposition 8 in
Section 4.2, then we have the bound. Then, for any $t\geq 4B^{2}$, Corollary 5
yields

$\displaystyle\max\\{\|\widehat{\Sigma}-\Sigma\|,\|\widehat{\Sigma}_{1}-\Sigma_{1}\|\\}$
$\displaystyle\leq
4\sqrt{2}\left(\|\Sigma_{1}\|+\|\Sigma\|\right)\left(32B^{2}+\Gamma_{n}\right)\sqrt{\frac{4\mathbf{r}\left(\Sigma_{0:1}\right)+t}{n}}+\mathbb{P}(\|\varepsilon_{\ell}\|\geq\sqrt{t}/2),$

where the definition of $\Sigma_{0:1}$ follows Section 4.2. We combine this
inequality to the result (20), and we obtain the statement. ∎

###### Proof of Proposition 10.

By Lemma 2 and 19 in Bartlett et al. (2020), the risk $R(\widehat{\theta})$ is
evaluated as

$\displaystyle R(\widehat{\theta})$ $\displaystyle\leq
2(\theta^{*})^{\top}(I-\Pi_{\mathsf{Y}})\Sigma(I-\Pi_{\mathsf{Y}})\theta^{*}+\sigma^{2}\mathrm{tr}((\mathsf{Y}\mathsf{Y}^{\top})^{-1}\mathsf{Y}\Sigma\mathsf{Y}^{\top}(\mathsf{Y}\mathsf{Y}^{\top})^{-1})$
$\displaystyle=2(\theta^{*})^{\top}B\theta^{*}+ct\sigma^{2}\mathrm{tr}(C),$

where $B=(I-\Pi_{\mathsf{Y}})\Sigma(I-\Pi_{\mathsf{Y}})$. We bound the first
term as

$\displaystyle(\theta^{*})^{\top}B\theta^{*}$
$\displaystyle=(\theta^{*})^{\top}(I-\Pi_{\mathsf{Y}})\Sigma(I-\Pi_{\mathsf{Y}})\theta^{*}$
$\displaystyle=(\theta^{*})^{\top}(I-\Pi_{\mathsf{Y}})(\Sigma-n^{-1}\mathsf{Y}^{\top}\mathsf{Y})(I-\Pi_{\mathsf{Y}})\theta^{*}$
$\displaystyle\leq\|\theta^{*}\|^{2}\|I-\Pi_{\mathsf{Y}}\|\|\Sigma-n^{-1}\mathsf{Y}^{\top}\mathsf{Y}\|$
$\displaystyle\leq\|\theta^{*}\|^{2}\|\Sigma-n^{-1}\mathsf{Y}^{\top}\mathsf{Y}\|,$

where the second equality follows
$(I-\Pi_{\mathsf{Y}})\mathsf{Y}^{\top}=(I-\mathsf{Y}^{\top}(\mathsf{Y}\mathsf{Y}^{\top})^{-1}\mathsf{Y})\mathsf{Y}^{\top}=\mathsf{Y}^{\top}-\mathsf{Y}^{\top}(\mathsf{Y}\mathsf{Y}^{\top})^{-1}(\mathsf{Y}\mathsf{Y}^{\top})=0$,
and the second inequality follows $\|I-\Pi_{\mathsf{Y}}\|\leq 1$ from the non-
expansive property of projection operators. Recalling that
$n^{-1}\mathsf{Y}^{\top}\mathsf{Y}=\widehat{\Sigma}$ as in (2), Proposition 7
yields the statement. ∎

## Acknowledgement

The first author’s work is partially supported by Japan Science and Technology
Agency CREST (grant number JPMJCR21D2). The second author’s work is partially
funded by CY Initiative of Excellence (grant “Investissements d’Avenir”
ANR-16-IDEX-0008), Project “EcoDep” PSI-AAP2020-0000000013. The third author’s
work is partially supported by Japan Society for the Promotion of Science
KAKENHI (grant number 21K11780) and Japan Science and Technology Agency FOREST
(grant number JPMJFR216I).

## References

  * Adamczak et al. (2010) Adamczak, R., Litvak, A., Pajor, A. and Tomczak-Jaegermann, N. (2010) Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles, Journal of the American Mathematical Society, 23, 535–561.
  * Alquier (2021) Alquier, P. (2021) User-friendly introduction to PAC-Bayes bounds, arXiv preprint arXiv:2110.11216.
  * Alquier and Wintenberger (2012) Alquier, P. and Wintenberger, O. (2012) Model selection for weakly dependent time series forecasting, Bernoulli, 18, 883–913.
  * Bartlett et al. (2020) Bartlett, P. L., Long, P. M., Lugosi, G. and Tsigler, A. (2020) Benign overfitting in linear regression, Proceedings of the National Academy of Sciences, 117, 30063–30070.
  * Bunea and Xiao (2015) Bunea, F. and Xiao, L. (2015) On the sample covariance matrix estimator of reduced effective rank population matrices, with applications to fpca, Bernoulli, 21, 1200–1230.
  * Cai et al. (2010) Cai, T. T., Zhang, C.-H. and Zhou, H. H. (2010) Optimal rates of convergence for covariance matrix estimation, The Annals of Statistics, 38, 2118–2144.
  * Catoni (2007) Catoni, O. (2007) PAC-Bayesian supervised classification: the thermodynamics of statistical learning, Institute of Mathematical Statistics Lecture Notes – Monograph Series, 56, Institute of Mathematical Statistics, Beachwood, OH, Ohio.
  * Catoni and Giulini (2017) Catoni, O. and Giulini, I. (2017) Dimension-free pac-bayesian bounds for matrices, vectors, and linear least squares regression, arXiv preprint arXiv:1712.02747.
  * Dedecker et al. (2007) Dedecker, J., Doukhan, P., Lang, G., José Rafael, L. R., Louhichi, S. and Prieur, C. (2007) Weak dependence, in Weak dependence: With examples and applications, Springer, pp. 9–20.
  * Dedecker and Prieur (2005) Dedecker, J. and Prieur, C. (2005) New dependence coefficients. examples and applications to statistics, Probability Theory and Related Fields, 132, 203–236.
  * Donoho (2006) Donoho, D. L. (2006) Compressed sensing, IEEE Transactions on information theory, 52, 1289–1306.
  * Doukhan and Wintenberger (2008) Doukhan, P. and Wintenberger, O. (2008) Weakly dependent chains with infinite memory, Stochastic Processes and their Applications, 118, 1997–2013.
  * Giulini (2018) Giulini, I. (2018) Robust dimension-free gram operator estimates, Bernoulli, 24, 3864–3923.
  * Guédon and Rudelson (2007) Guédon, O. and Rudelson, M. (2007) Lp-moments of random vectors via majorizing measures, Advances in Mathematics, 208, 798–823.
  * Han and Li (2020) Han, F. and Li, Y. (2020) Moment bounds for large autocovariance matrices under dependence, Journal of Theoretical Probability, 33, 1445–1492.
  * Han (2022) Han, Q. (2022) Exact spectral norm error of sample covariance, arXiv preprint arXiv:2207.13594.
  * Handel (2017) Handel, R. v. (2017) Structured random matrices, Convexity and concentration, pp. 107–156.
  * Jeong et al. (2022) Jeong, H., Li, X., Plan, Y. and Yilmaz, O. (2022) Sub-gaussian matrices on sets: Optimal tail dependence and applications, Communications on Pure and Applied Mathematics, 75, 1713–1754.
  * Koltchinskii and Lounici (2017) Koltchinskii, V. and Lounici, K. (2017) Concentration inequalities and moment bounds for sample covariance operators, Bernoulli, 23, 110–133.
  * Liaw et al. (2017) Liaw, C., Mehrabian, A., Plan, Y. and Vershynin, R. (2017) A simple tool for bounding the deviation of random matrices on geometric sets, in Geometric aspects of functional analysis, Springer, New York, pp. 277–299.
  * Lopes et al. (2023) Lopes, M. E., Erichson, N. B. and Mahoney, M. W. (2023) Bootstrapping the operator norm in high dimensions: Error estimation for covariance matrices and sketching, Bernoulli, 29, 428–450.
  * Mendelson and Paouris (2014) Mendelson, S. and Paouris, G. (2014) On the singular values of random matrices, Journal of the European Mathematical Society, 16, 823–834.
  * Oliveira (2009) Oliveira, R. I. (2009) Concentration of the adjacency matrix and of the laplacian in random graphs with independent edges, arXiv preprint arXiv:0911.0600.
  * Rio (2000) Rio, E. (2000) Inégalités de Hoeffding pour les fonctions lipschitziennes de suites dépendantes, Comptes Rendus de l’Académie des Sciences-Series I-Mathematics, 330, 905–908.
  * Rudelson (1999) Rudelson, M. (1999) Random vectors in the isotropic position, Journal of Functional Analysis, 164, 60–72.
  * Srivastava and Vershynin (2013) Srivastava, N. and Vershynin, R. (2013) Covariance estimation for distributions with 2+$\epsilon$ moments, The Annals of Probability, 41, 3081–3111.
  * Vershynin (2018) Vershynin, R. (2018) High-Dimensional Probability: An Introduction with Applications in Data Science, Cambridge University Press, Cambridge.
  * Zhivotovskiy (2021) Zhivotovskiy, N. (2021) Dimension-free bounds for sums of independent matrices and simple tensors via the variational principle, arXiv preprint arXiv:2108.08198.