Performance of ordinary least squares(OLS) method for the \emph{estimation of
high dimensional stable state transition matrix} $A$(i.e., spectral radius
$\rho(A)<1$) from a single noisy observed trajectory of the linear time
invariant(LTI)\footnote{Linear Gaussian (LG) in Markov chain literature} system
$X_{-}:(x_0,x_1, \ldots,x_{N-1})$ satisfying \begin{equation}
x_{t+1}=Ax_{t}+w_{t}, \hspace{10pt} \text{ where } w_{t} \thicksim
N(0,I_{n}), \end{equation}
heavily rely on negative moments of the sample covariance matrix:
$(X_{-}X_{-}^{*})=\sum_{i=0}^{N-1}x_{i}x_{i}^{*}$ and singular values of
$EX_{-}^{*}$, where $E$ is a rectangular Gaussian ensemble $E=[w_0, \ldots,
w_{N-1}]$. Negative moments requires sharp estimates on all the eigenvalues
$\lambda_{1}\big(X_{-}X_{-}^{*}\big) \geq \ldots \geq
\lambda_{n}\big(X_{-}X_{-}^{*}\big) \geq 0$. Leveraging upon recent results on
spectral theorem for non-Hermitian operators in \cite{naeem2023spectral}, along
with concentration of measure phenomenon and perturbation theory(Gershgorins'
and Cauchys' interlacing theorem) we show that only when $A=A^{*}$, typical
order of $\lambda_{j}\big(X_{-}X_{-}^{*}\big) \in \big[N-n\sqrt{N},
N+n\sqrt{N}\big]$ for all $j \in [n]$. However, in \emph{high dimensions} when
$A$ has only one distinct eigenvalue $\lambda$ with geometric multiplicity of
one, then as soon as eigenvalue leaves \emph{complex half unit disc}, largest
eigenvalue suffers from curse of dimensionality:
$\lambda_{1}\big(X_{-}X_{-}^{*}\big)=\Omega\big( \lfloor\frac{N}{n}\rfloor
e^{\alpha_{\lambda}n} \big)$, while smallest eigenvalue
$\lambda_{n}\big(X_{-}X_{-}^{*}\big) \in (0, N+\sqrt{N}]$. Consequently, OLS
estimator incurs a \emph{phase transition} and becomes \emph{transient:
increasing iteration only worsens estimation error}, all of this happening when
the dynamics are generated from stable systems.

OLS 方法的性能取决于样本协方差矩阵的负矩和特征值，在高维情况下，当稳定状态转移矩阵具有单个特征值且动力学来自稳定系统时，OLS 估计器会产生相位转变并呈现短暂性行为，迭代次数的增加只会加剧估计误差。

高维线性高斯波谱统计的样本协方差矩阵

Spectral Statistics of the Sample Covariance Matrix for High Dimensional  Linear Gaussians

Sequential data collection has emerged as a widely adopted technique for
enhancing the efficiency of data gathering processes. Despite its advantages,
such data collection mechanism often introduces complexities to the statistical
inference procedure. For instance, the ordinary least squares (OLS) estimator
in an adaptive linear regression model can exhibit non-normal asymptotic
behavior, posing challenges for accurate inference and interpretation. In this
paper, we propose a general method for constructing debiased estimator which
remedies this issue. It makes use of the idea of adaptive linear estimating
equations, and we establish theoretical guarantees of asymptotic normality,
supplemented by discussions on achieving near-optimal asymptotic variance. A
salient feature of our estimator is that in the context of multi-armed bandits,
our estimator retains the non-asymptotic performance of the least square
estimator while obtaining asymptotic normality property. Consequently, this
work helps connect two fruitful paradigms of adaptive inference: a)
non-asymptotic inference using concentration inequalities and b) asymptotic
inference via asymptotic normality.

本文提出了一种构建无偏估计器的普遍方法，使用自适应线性估计方程的思想，并建立渐近正常性的理论保证，以及实现接近最优渐近方差的讨论。

自适应线性估计方程

Adaptive Linear Estimating Equations

As bandit algorithms are increasingly utilized in scientific studies and
industrial applications, there is an associated increasing need for reliable
inference methods based on the resulting adaptively-collected data. In this
work, we develop methods for inference on data collected in batches using a
bandit algorithm. We first prove that the ordinary least squares estimator
(OLS), which is asymptotically normal on independently sampled data, is not
asymptotically normal on data collected using standard bandit algorithms when
there is no unique optimal arm. This asymptotic non-normality result implies
that the naive assumption that the OLS estimator is approximately normal can
lead to Type-1 error inflation and confidence intervals with below-nominal
coverage probabilities. Second, we introduce the Batched OLS estimator (BOLS)
that we prove is (1) asymptotically normal on data collected from both
multi-arm and contextual bandits and (2) robust to non-stationarity in the
baseline reward.

本文发展了一种基于批处理数据的自适应数据收集的带状算法推断方法，证明了普通最小二乘估计器在标准的赌臂算法收集数据时不是渐近正常的，提出了批处理 OLS 估计器，并证明其可以适用于多臂和情境赌臂算法并且对随机变量鲁棒。