# Learning from Censored and Dependent Data:
The case of Linear Dynamics

Orestis Plevrakis
Princeton University
<EMAIL_ADDRESS>
###### Abstract

Observations from dynamical systems often exhibit irregularities, such as
_censoring_ , where values are recorded only if they fall within a certain
range. Censoring is ubiquitous in practice, due to saturating sensors, limit-
of-detection effects, image frame effects, and combined with temporal
dependencies within the data, makes the task of system identification
particularly challenging.

In light of recent developments on learning linear dynamical systems (LDSs),
and on censored statistics with _independent_ data, we revisit the decades-old
problem of learning an LDS, from censored observations (Lee and Maddala
(1985); Zeger and Brookmeyer (1986)). Here, the learner observes the state
$x_{t}\in{\mathbb{R}}^{d}$ if and only if $x_{t}$ belongs to some set
$\mathcal{S}_{t}\subseteq{\mathbb{R}}^{d}$. We develop the first
computationally and statistically efficient algorithm for learning the system,
assuming only oracle access to the sets $\mathcal{S}_{t}$. Our algorithm,
_Stochastic Online Newton with Switching Gradients_ , is a novel second-order
method that builds on the Online Newton Step (ONS) of Hazan et al. (2007). Our
Switching-Gradient scheme does not always use (stochastic) gradients of the
function we want to optimize, which we call _censor-aware_ function. Instead,
in each iteration, it performs a simple test to decide whether to use the
censor-aware, or another _censor-oblivious_ function, for getting a stochastic
gradient.

In our analysis, we consider a ?generic? Online Newton method, which uses
arbitrary vectors instead of gradients, and we prove an error-bound for it.
This can be used to appropriately design these vectors, leading to our
Switching-Gradient scheme. This framework significantly deviates from the
recent long line of works on censored statistics (e.g, Daskalakis et al.
(2018); Kontonis et al. (2019); Daskalakis et al. (2019)), which apply
Stochastic Gradient Descent (SGD), and their analysis reduces to establishing
conditions for off-the-shelf SGD-bounds. Our approach enables to relax these
conditions, and gives rise to phenomena that might appear counterintuitive,
given the previous works. Specifically, our method makes progress even when
the current ?survival probability? is exponentially small. We believe that our
analysis framework will have applications in more settings where the data are
subject to censoring.

##  1 Introduction

System identification is the problem of learning the evolution equations of a
dynamical system from data. Mathematically, we have a sequence of system
states $(x_{t})_{t}$, and observations $(y_{t})_{t}$ evolving as

$\displaystyle x_{t+1}=f(x_{t},u_{t},w_{t}),\ \ y_{t}=g(x_{t},v_{t}),$

where $u_{t}$’s are inputs to the system, $w_{t}$ is process noise, and
$v_{t}$ is sensor noise. At each step $t$, the learner observes the input
$u_{t}$, and the resulting output $y_{t+1}$. The goal is to learn the
functions $f$ and $g$, from an observed trajectory.111Some works consider
access to multiple trajectories. In this paper, we consider system
identification with _censored_ observations, where the learner observes
$y_{t}$ if and only if $y_{t}$ belongs to some set $\mathcal{S}_{t}$, which we
call the _observable_ set.

(a) $\mathcal{S}_{t}={\mathbb{R}}^{2}$

(b) $\mathcal{S}_{t}=\\{(x_{1},x_{2}):x_{1}\geq x_{t,2}+0.4,x_{2}\geq
x_{t,1}+0.2\\}$

Figure 1: Linear system in $2$-$d$, $A_{*}=\rho\cdot I$, $\rho=1-\epsilon$,
$\epsilon\approx 0$. Figure 1(a) is an uncensored trajectory (color is a
function of time). Figure 1(b) is the same trajectory, but the grey areas are
censored.

Dynamical data with missing observations are ubiquitous in practice (Honaker
and King, 2010). This is often due to censoring, which frequently manifests in
the fields of signal processing and control theory (Yang and Li, 2009), time
series analysis (Lee and Maddala, 1985), business (Hausman and Wise, 1977),
economics (Johannsen and Mertens, 2018), in medicine, and in physical
sciences. For example, consider learning the dynamics of some target dynamical
system, using observations from cameras. Here, censoring naturally arises due
to occlusions blocking visibility, or from the system exiting the camera
frame. Despite the numerous applications, the problem is not statistically and
computationally understood even for linear, fully-observable dynamics:

$\displaystyle x_{t+1}=A_{*}x_{t}+B_{*}u_{t}+w_{t},\ \ y_{t}=x_{t},$

where $x_{t}\in\mathbb{R}^{d}$, $u_{t}\in\mathbb{R}^{m}$, and
$w_{t}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny i.i.d}}}{\sim}}N(0,I)$.
Actually, even for one-dimensional linear systems $(d=1)$, with no inputs
$(u_{t}=0)$, and observable sets $\mathcal{S}_{t}$ being half-lines, no known
efficient algorithm learns (the scalar) $A_{*}$, not even asymptotically.
Specifically, the existing methods fall in two categories: 1) iterative
methods trying to maximize the non-concave log-likelihood, as in Lee and
Maddala (1985) and Zeger and Brookmeyer (1986), and 2) EM-based imputation
methods (e.g., Park et al. (2007)). Both of them are not guaranteed to recover
the underlying system. On top of that, for large dimension $d$, the
likelihood-based approach is inefficient to implement because it requires
computing high-dimensional integrals over $\mathcal{S}_{t}$’s.

In this work, we study the multidimensional linear case with no inputs:
$x_{t+1}=A_{*}x_{t}+w_{t}$ (e.g., Figure 1(a)). We allow _arbitrary_
observable sets $\mathcal{S}_{t}$ (e.g., Figure 1(b)), with only requirement
being that we have oracle access to each $\mathcal{S}_{t}$, namely, given a
point $x$, the oracle efficiently computes
$\mathds{1}\\{x\in\mathcal{S}_{t}\\}$. For this model, we obtain the first
computationally and statistically efficient algorithm for learning $A_{*}$,
under the following assumptions (stated informally here, and in detail in
Section 3):

Assumption 1:

The system is _stable_ , i.e., the spectral radius $\rho(A_{*})$ is less than
one. Stability is a classical assumption in linear dynamical systems (LDSs).
If $\rho(A_{*})>1$, then the state explodes exponentially, with high
probability.

Assumption 2:

The number of times we observe the state is at least a constant fraction (say
$1\%$) of the trajectory-length.

Assumption 3:

For most of the timesteps $t$, given that we observed $x_{t}$, the probability
of observing $x_{t+1}$ is at least a constant (say $1\%$).

To motivate the last two assumptions, we note that for the simpler problems of
censored Gaussian estimation and censored linear regression (with independent
data), the only known computationally and statistically efficient algorithms
assume that the probability of observing a sample is at least a constant (see
Daskalakis et al. (2018), Daskalakis et al. (2019)). Assumptions 2 and 3 are
the adaption of this, to fit our dynamical setting. Under these assumptions,
our estimation error bound matches (up to logarithmic factors) the best known
bound for learning uncensored LDSs (Simchowitz et al. (2018)), with respect to
the dimension $d$, the trajectory-length $T$, and the spectrum of $A_{*}$. It
is also the first, to the best of our knowledge, estimator that can
accommodate arbitrary observable sets, since previous works considered
intervals, half-lines, and products of these (e.g., Zeger and Brookmeyer
(1986), Yang and Li (2009)). Key for tackling this decades-old problem are
recent advances in 1) (uncensored) linear system identification theory, and 2)
censored/truncated statistics (CTS) for independent data.

##### Learning Linear Dynamics.

The difficulty in learning an LDS, compared to standard linear regression, is
that the observations are dependent. A classical approach that avoids this
issue is based on the system’s mixing time, which is roughly
$\tau_{\text{mix}}=\frac{1}{1-\rho(A_{*})}$ steps. Thus, the learner can use
one $x_{t}$ every $\tau_{\text{mix}}$ steps, and reduce the analysis to
standard linear regression (e.g., Yu (1994)). However, the resulting bounds
get worse with larger $\tau_{\text{mix}}$, and as pointed in Simchowitz et al.
(2018), this behavior is qualitatively incorrect. Intuitively, larger $A_{*}$
gives larger states, which implies larger signal-to-noise ratio, i.e., easier
estimation. The authors provided bounds that express this intuition, and that
was the first sharp analysis for stable systems.222The authors also considered
$\rho(A_{*})=1$, known as the _marginally stable_ regime. This progress
initiated a large line of work on learning LDSs (see Section 1.1).

##### Censored/Truncated Statistics (CTS).

Consider the problem of learning a Gaussian distribution, having access only
to samples from some set $\mathcal{S}$. These are called _truncated_ samples.
Censoring is when we also know the number of unobserved samples, as in our
case, where this number can be inferred from the lengths of time-intervals
during which we do not observe anything. Truncation and censoring go back to
at least Galton (1898) and Pearson (1902), and there has been a large volume
of research devoted to them (see Cohen (1991)). Nevertheless, the first
provably computationally and statistically efficient algorithm, for learning a
truncated Gaussian, was only recently discovered by Daskalakis et al. (2018).
The authors developed a general algorithmic framework, based on Stochastic
Gradient Descent (SGD), which bypasses the computation of high-dimensional
integrals over $\mathcal{S}$. The result and the generality of the approach
created a lot of excitement, and a large number of subsequent works applied
the SGD framework to other problems in CTS (for independent data), e.g.,
linear regression by Daskalakis et al. (2019).

### Our Contributions

We build on the above advances, by introducing new algorithmic and technical
ideas, which we now overview.

##### Our algorithm.

Our first observation is that non-convexity of the negative log-likelihood can
be bypassed by focusing on ?paired observations?, i.e., $(x_{t},x_{t+1})$ such
that $x_{t}\in\mathcal{S}_{t}$ and $x_{t}\in\mathcal{S}_{t+1}$. By ignoring
the other terms in the objective, we get a convex function. The second
observation is that for LDSs, if an SGD-based algorithm relies on the
Markovian property $\mathbb{E}[x_{t+1}|x_{t},x_{t-1},\dots,x_{1}]=A_{*}x_{t}$
to produce _unbiased_ gradient estimates, then the algorithm should process
the data in _temporal order_. The reason is that if we ?see? $x_{t}$ and
$x_{t+s}$ (for some $s\geq 2$), then the expectation of $x_{t+1}$ is not
$A_{*}x_{t}$, i.e., $\mathbb{E}[x_{t+1}|x_{t},x_{t+s}]\neq A_{*}x_{t}$. In
other words, we need an online algorithm. Unfortunately, for censored linear
regression, the SGD framework of Daskalakis et al. (2019) processes the data
in _random_ order, and also does multiple passes over them. This is not a
technicality; making that algorithm online will lead to slow statistical
rates, as we explain later. For this reason, we design a new stochastic
_second-order_ method, building on the Online Newton Step method (ONS) of
Hazan et al. (2007). The crucial difference with ONS, and all recent works on
CTS, is that we do not always use (stochastic) gradients of the function we
want to optimize, which we call _censor-aware_ function. Instead, in each
iteration, we perform a simple test, based on which we decide whether to use
the censor-aware function, or another _censor-oblivious_ function, for getting
a stochastic gradient. We call our method _Stochastic Online Newton with
Switching Gradients_ (SON-SG, given in Algorithm 1), and we show that it can
be combined with a least-squares-based warmup procedure, to learn censored
LDSs (Algorithm 4). We also show that SON-SG can be applied to an even broader
setting, i.e., general linear-response time-series (Section 4).

##### Algorithm-design framework.

We came up with this switching-gradient scheme, by considering a ?generic? ONS
method, where instead of gradients we have an arbitrary vector sequence
$g_{1},g_{2},\dots$. We proved a general estimation error bound for this
method, which serves as a guideline for designing the $g_{i}$’s. A similar
framework for designing $g_{i}$’s has been proposed in the context of non-
convex optimization (for first-order methods), by Arora et al. (2015). This
approach gives a lot of freedom for algorithm design, compared to previous
works on CTS which apply off-the-shelf SGD-bounds, and we believe it will have
more applications in censored and truncated statistics.

##### Technical contributions and insights.

In all recent CTS papers (see Section 1.1 for an extensive list), a crucial
step for proving parameter recovery by SGD is establishing _anti-
concentration_ of truncated Gaussians $\mathcal{N}(\mu,\Sigma,\mathcal{S})$,
where $\mathcal{N}(\mu,\Sigma,\mathcal{S})$ is the Gaussian
$\mathcal{N}(\mu,\Sigma)$, given that the sample is in $\mathcal{S}$.
Daskalakis et al. (2018) reduced this task to showing that the ?survival
probability? is large, i.e.,
$\operatorname{\mathbb{P}}_{x\sim\mathcal{N}(\mu,\Sigma)}[x\in\mathcal{S}]\geq\Omega(1)$.
Hence, this and all follow-up works have focused on lower bounding survival
probabilities. In our case, this methodology does not apply, due to temporal
dependencies. However, our approach (generic ONS bound) enables to
significantly relax the high survival probability condition, and gives rise to
phenomena that might appear counterintuitive, given the intuition built in the
recent literature. Specifically, in high dimensions ($d\to\infty$) our
analysis deals with cases where the survival probability is exponentially
small $(e^{-\Omega(d)})$, while at the same time anti-concentration tends to
infinity. Our other technical contribution is a lower-bound on the covariance
matrix of the _observed_ states. Simchowitz et al. (2018) proved such a bound
when all states are observed. Here, due to censoring, we observe only a subset
of the whole trajectory. For independent data, Daskalakis et al. (2018)
address this issue using union-bound over all possible subsets.333This is
implicit in their analysis. They use a result of Diakonikolas et al. (2019),
which applies union bound over subsets. Unfortunately, for LDSs union-bound
gives vacuous guarantees, because for a fixed subset, the concentration
degrades with larger mixing times. We resolve this difficulty, by generalizing
the ?small-ball? technique of Simchowitz et al. (2018), and we lower-bound the
covariance matrices of _all subsets_ of size $\Omega(T)$ _simultaneously_ ,
where $T$ is the trajectory-length.

###  1.1 Further Related Work

##### Censored and Truncated Statistics.

As we mentioned, there has been a long line of recent works on several
settings within CTS: Gaussian parameter estimation (Daskalakis et al., 2018;
Kontonis et al., 2019), linear, logistic and probit regression (Daskalakis et
al., 2019; Ilyas et al., 2020), compressed sensing (Daskalakis et al., 2020),
sparse graphical models (Bhattacharyya et al., 2020), estimation of boolean
product distributions (Fotakis et al., 2020), mixtures of Gaussians (Nagarajan
and Panageas, 2020). All these works consider independent data and apply the
SGD framework444Exception is Nagarajan and Panageas (2020) who consider the
EM-algorithm. introduced in Daskalakis et al. (2018).

##### Linear System Identification.

Even though linear system identification is a decades-old field (Ljung, 1999),
a sharp non-asymptotic theory was only recently developed (Simchowitz et al.,
2018; Sarkar and Rakhlin, 2019; Tsiamis and Pappas, 2019; Oymak and Ozay,
2019; Simchowitz et al., 2019).

##### Online Convex Optimization.

To design our algorithm, we build on ideas from online convex optimization
(OCO). In the recent years, OCO has been extensively used for learning and
controlling LDSs (e.g., Agarwal et al. (2019); Hazan et al. (2020); Simchowitz
et al. (2020); Ghai et al. (2020); Simchowitz (2020)). For a general overview
of OCO see Hazan (2019).

##  2  Notation

For every vector $x$, we use $\|x\|$ to denote the $\ell_{2}$ norm
$\|x\|_{2}$. Also, we use $\langle A,B\rangle=\mathrm{tr}(A^{\top}B)$ to
denote the matrix inner product. For a matrix $A$ and a $\Sigma\succ 0$, we
define the norm $\|A\|_{\Sigma}=\sqrt{\langle A^{\top}A,\Sigma\rangle}$
555Usually, $\|A\|_{\Sigma}$ is used to denote $\sqrt{\langle
AA^{T},\Sigma\rangle}$. However, this definition is more appropriate for our
setting.. The covariance matrix between two random vectors $x,y$ is
$\text{Cov}[x,y]$. For a sequence $(x_{t})_{t=1}^{T}$, we denote by
$x_{\leq\tau}$, $x_{<\tau}$ and $x_{-\tau}$ the subsequences
$(x_{t})_{t\leq\tau},(x_{t})_{t<\tau},(x_{t})_{t\neq\tau}$ respectively. For a
Gaussian distribution $\mathcal{N}(\mu,\Sigma)$ in ${\mathbb{R}}^{d}$, and a
measurable $\mathcal{S}\subseteq{\mathbb{R}}^{d}$, we define the survival
probability
$\mathcal{N}(\mu,\Sigma;\mathcal{S})=\operatorname{\mathbb{P}}_{x\sim\mathcal{N}(\mu,\Sigma)}[x\in\mathcal{S}]$.
We also define the truncated Gaussian $\mathcal{N}(\mu,\Sigma,\mathcal{S})$ to
be $\mathcal{N}(\mu,\Sigma)$ conditioned on taking values in $\mathcal{S}$.
Finally, whenever we say that a set $\mathcal{S}$ is ?revealed? to the
learner, we mean that she has access to a membership oracle $M_{\mathcal{S}}$,
i.e., an efficient procedure that computes the
$\mathds{1}\\{x\in\mathcal{S}\\}$, for any point $x$.

##  3 Censored Linear Dynamics: Model, and Main Theorem

We study the system $x_{t+1}=A_{*}x_{t}+w_{t}$, where
$x_{t}\in{\mathbb{R}}^{d}$, $A_{*}\in{\mathbb{R}}^{d\times d}$ and
$w_{t}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
i.i.d}}}{\sim}}\mathcal{N}(0,I)$. Starting from $x_{0}=0$,666We assume
$x_{0}=0$ to simplify the exposition. Our proofs generalize for any $x_{0}$,
by paying a $\log{\|x_{0}\|}$ factor in the bound. consider the trajectory
$x_{1},x_{2},\dots,x_{T+1}$. The learner has access to censored observations,
i.e., there is a process of observable sets $(\mathcal{S}_{t})_{t}$, and she
observes $x_{t}$ if and only if $x_{t}\in\mathcal{S}_{t}$. Also, at time $t$,
the set $\mathcal{S}_{t}$ is revealed to her. Now, $\mathcal{S}_{t}$’s may
depend on the state-trajectory, but we assume that given $x_{t}$, the state
$x_{t+1}$ and the set $\mathcal{S}_{t+1}$ are statistically independent. To
see why this is a natural assumption, consider the camera-based example
(Section 1), and think of $x_{t}\in{\mathbb{R}}^{3}$ as the position of some
object, and $\mathcal{S}_{t}$ as the visible part of the space at time $t$.
Having observed $x_{t}$, the camera could adapt its frame (affecting
$\mathcal{S}_{t+1}$), to improve the chances for observing $x_{t+1}$, but
without knowing the next “excitation” $w_{t}$. We now formally state our
assumptions, sketched in Section 1.

######  Assumption 1.

$A_{*}$ is diagonalizable and stable, i.e., $A_{*}=UDU^{-1}$, where $D$ is
diagonal and $\rho(A_{*})=\max_{i}|D_{ii}|<1$.777Note that $S$ and $D$ can
have complex entries.

Let $\mathcal{O}$ be the set of observation times:
$\mathcal{O}=\\{t\in[T]:x_{t}\in\mathcal{S}_{t}\\}$. We assume that we observe
?enough? data:

######  Assumption 2.

For a known constant $\beta\in(0,1)$, with probability $1-o(1)$, we have
$|\mathcal{O}|\geq\beta T$, where $o(1)$ denotes a $\delta_{T}\to 0$, as
$T\to\infty$.

Let $\mathcal{B}(a)$ be the set of timesteps $t$, at which 1) we observe
$x_{t}$, and 2) given $x_{t}$ and $\mathcal{S}_{t+1}$, the probability of
observing $x_{t+1}$ is less than $a$, i.e.,
$\mathcal{B}(a)=\left\\{t\in\mathcal{O}:\
\mathcal{N}\left(A_{*}x_{t},I;\mathcal{S}_{t+1}\right)<a\right\\}$.

######  Assumption 3.

For a known constant $\alpha\in(0,1)$, and some bound $L>0$, with probability
$1-o(1)$, we have $|\mathcal{B}(\alpha)|\leq L$. Also,
$\mathbb{E}\big{[}|\mathcal{B}(\alpha)|\big{]}\leq L$.

Our bounds will depend on $L$, and will match the uncensored case if
$L\leq\smash{\widetilde{O}}(d)$.888$\smash{\widetilde{O}}(\cdot)$ hides
logarithmic factors. As we mentioned in the introduction, Assumptions 2 and 3
are the adaptation of the $\Omega(1)$-survival-probability assumption in
Daskalakis et al. (2018). We further motivate Assumption 3 with a natural one-
dimensional example.

######  Example 3.1.

Let $x_{t+1}=a_{*}x_{t}+w_{t}$, where $a_{*}\in[0,1)$. The observable set is a
static half-line: $\mathcal{S}_{t}=\mathcal{S}=\\{x\in{\mathbb{R}}\ :\
x\geq\lambda\\}$, $\lambda>0$. We claim that here, Assumption 2 implies
Assumption 3 with $\alpha=\Omega(1)$ and $L=0$. This is clear for
$a_{*}\approx 1$, since if $x_{t}\geq\lambda$, then $a_{*}x_{t}+w_{t}\geq
x_{t}\geq\lambda$ with probability almost $1/2$.999Note that for $a_{*}\approx
1$, we did not need Assumption 2, to show Assumption 3. However, we need it
for general $a_{*}$. For general $a_{*}\in[0,1)$, the implication is less
obvious (see Appendix B).

As in Simchowitz et al. (2018), our bounds depend on the controllability
Gramian $\Gamma_{T}$, defined as
$\Gamma_{T}\coloneqq\sum_{s=0}^{T-1}A_{*}^{s}(A_{*}^{s})^{\top}$. This matrix
quantifies how much the noise process excites the system. In the theorem that
follows, we use $\widetilde{\Theta}(1)$ to denote polylogarithmic factors in
$T$ and in $\text{cond}(U)$, where cond(U) is the condition number of the
eigenvector-matrix $U$.

######  Theorem 1.

Under Assumptions 1, 2, 3, there exist
$C_{\alpha,\beta},C_{\alpha,\beta}^{\prime}=\widetilde{\Theta}(1)\cdot\mathrm{poly}\left(\frac{1}{\alpha\beta}\right)$,
such that if

$\displaystyle T\geq
C_{\alpha,\beta}^{\prime}\cdot\left(d^{2}+\frac{d}{1-\rho(A_{*})}+dL\right),$

then with probability at least $99\%$, Algorithm 4 runs in polynomial time,
and outputs an $\widehat{A}$ such that

$\displaystyle\left\|\widehat{A}-A_{*}\right\|_{\Gamma_{T}}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ C_{\alpha,\beta}\sqrt{\frac{d^{2}+dL}{T}}.$ (1)

######  Remark 3.1.

For uncensored LDSs, and stable-diagonalizable $A_{*}$, the best known
(spectral-norm) bound is
$\left\|(\widehat{A}-A_{*})\Gamma_{T}^{1/2}\right\|_{2}\leq\smash{\widetilde{O}}\left(\sqrt{d/T}\right)$.
So, the Frobenius version is
$\|\widehat{A}-A_{*}\|_{\Gamma_{T}}\leq\smash{\widetilde{O}}\left(\sqrt{d^{2}/T}\right)$,
which matches (1), if $\alpha,\beta=\Omega(1)$, and
$L=\smash{\widetilde{O}}(d)$. We leave the spectral-norm bound for censored
LDSs for future work.

######  Remark 3.2.

It is possible to drop the assumption that $A_{*}$ is diagonalizable by paying
an exponential dependence in the size of the largest Jordan block. This
dependence (for a bound on $\|\cdot\|_{\Gamma_{T}}$) appears even in the
uncensored case (see Ghai et al. (2020) for a discussion on this).

As we mentioned, our algorithm is SON-SG, preceded by a least-squares warmup
procedure. Let $\mathcal{P}$ be the set of of pairs $(x_{t},x_{t+1})$, such
that both $t,t+1\in\mathcal{O}$. We will ignore all ?isolated? observations,
i.e., the ones not participating in any pair of $\mathcal{P}$. As we will see,
by ignoring them This decision is justified by the following proposition:

######  Proposition 3.1.

Let $M\coloneqq|\mathcal{P}|$. With probability $1-o(1)$, we have
$M\geq\alpha\beta T/2$.

We prove Proposition 3.1 in Appendix C, using Assumptions 2,3, and that
$T>>L$. Let $\mathcal{P}_{0}$ be the first (in time-order) $\lfloor
M/2\rfloor$ pairs of $\mathcal{P}$, and
$\mathcal{P}_{1}=\mathcal{P}\setminus\mathcal{P}_{0}$. Our algorithm first
uses $\mathcal{P}_{0}$ to create a (rough) confidence ellipsoid $\mathcal{K}$
that includes $A_{*}$, with high probability. Then, it uses $\mathcal{K}$ as
constraint-set for SON-SG, which will operate on $\mathcal{P}_{1}$. In the
next section, we present and analyze SON-SG in a more general setting, which
reveals the key structure that our method exploits. Then, in Section 6, we
give the full-algorithm and conclude the proof of Theorem 1.

##  4 Truncated Time Series with Linear Responses

For timesteps $1$ to $T$, consider a covariate-response process
$(x_{t},y_{t})_{t}$, where $x_{t}\in{\mathbb{R}}^{d}$,
$y_{t}\in{\mathbb{R}}^{n}$. The learner only observes a subset of the data,
based on a Bernoulli process $(o_{t})_{t}$, i.e., if $o_{t}=1$, then she
observes $(x_{t},y_{t})$, otherwise the pair is hidden. In untruncated linear-
response time series, we have $y_{t}=A_{*}x_{t}+w_{t}$, where $w_{t}\sim
N(0,I)$, and $A_{*}\in{\mathbb{R}}^{n\times d}$. Here, when the learner gets
to see a datapoint, the noise will be biased due to truncation. Formally,
consider a process of observable sets $(S_{t})_{t}$, where
$S_{t}\subseteq{\mathbb{R}}^{n}$. Let $\mathcal{F}_{t}$ be the
$\sigma$-algebra generated by $x_{\leq t}$, $y_{<t}$, $o_{\leq t}$ and
$S_{\leq t}$ (note that $y_{t}$ is not in $\mathcal{F}_{t}$). We assume that
given $\mathcal{F}_{t}$ and $o_{t}=1$, the set $S_{t}$ is revealed to the
learner, and $y_{t}\sim\mathcal{N}(A_{*}x_{t},I,S_{t})$. This model has three
notable special cases:

  1. 1.

Untruncated, linear-response time series. This model was studied by Simchowitz
et al. (2018), and corresponds to $o_{t}=1$ and $S_{t}={\mathbb{R}}^{n}$, for
all $t$.

  2. 2.

Truncated linear regression. First considered by Tobin (1958), this model was
revisited by Daskalakis et al. (2019), and corresponds to $o_{t}=1$ for all
$t$, and it requires independent data, i.e., given $x_{t}$, the response
$y_{t}$ is independent of $x_{-t}$.101010To be precise, Daskalakis et al.
(2019) consider one-dimensional responses and fixed truncation set. However,
the extension to multidimensional $y_{t}$’s and time-varying truncation sets
is relatively straightfoward.

  3. 3.

LDS with censored observations. Here, $y_{t}=x_{t+1}$,
$o_{t}=\mathds{1}\left\\{x_{t}\in\mathcal{S}_{t}\ \land\
x_{t+1}\in\mathcal{S}_{t+1}\right\\}$, and $S_{t}=\mathcal{S}_{t+1}$. Note
that we pretend we do not observe the ?isolated? observations, which is
aligned with what our algorithm does.

##### Initial confidence ellipsoid.

SON-SG receives as input a rough initial estimate
$A_{0}\in{\mathbb{R}}^{n\times d}$, and a $\Sigma_{0}\succ 0$ that represents
a confidence ellipsoid $\mathcal{K}=\\{A\in{\mathbb{R}}^{n\times d}:\
\|A-A_{0}\|_{\Sigma_{0}}\leq 1\\}$. For LDSs, we will later show how to use
$\mathcal{P}_{0}$ to construct a $\mathcal{K}$ with the following property:

######  Definition 4.1.

A confidence ellipsoid $\mathcal{K}=\\{A\in{\mathbb{R}}^{n\times d}:\
\|A-A_{0}\|_{\Sigma_{0}}\leq 1\\}$ is $(R,\omega)$-accurate, for some
$R,\omega>0$, if (a) $A_{*}\in\mathcal{K}$, (b)
$\Sigma_{0}\succcurlyeq\omega\cdot I$, and (c) for all $t$,
$\big{\|}\Sigma_{0}^{-1/2}x_{t}\big{\|}$ is $R^{2}$-subgaussian.111111A random
variable $X$ is called $\sigma^{2}$-subgaussian if
$\operatorname{\mathbb{P}}[|X|\geq\delta\cdot\sigma]\leq\exp\left(-\delta^{2}/C\right)$,
where $C=O(1)$.

######  Theorem 2.

Fix $R,R_{w},R_{x},L,\alpha>0$, and let $B(\alpha)\coloneqq\\{t\in[T]:\
o_{t}=1,\ \mathcal{N}(A_{*}x_{t},I;S_{t})<\alpha\\}$. Suppose that (a) we are
given an $(R,\omega)$-accurate confidence ellipsoid $\mathcal{K}$, (b)
$\mathbb{E}[|B(\alpha)|]\leq L$, (c) for all $t$, the noise
$w_{t}=y_{t}-A_{*}x_{t}$ has norm $\|w_{t}\|$ that is $R_{w}^{2}$-subgaussian,
and (d) $\mathbb{E}[\|x_{t}\|^{2}]\leq R_{x}^{2}$. Let
$t_{1}<t_{2}<\dots<t_{N}$ be the observation times ($o_{t_{i}}=1$). If the
total number of steps $T\geq\mathrm{poly}(1/\alpha)$, then SON-SG (Algorithm
1) outputs an $\widehat{A}$ such that

$\displaystyle\mathbb{E}\left[\left\|\widehat{A}-A_{*}\right\|_{\Sigma}^{2}\right]\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \frac{D+LD^{\prime}}{N},$ (2)

where $\Sigma=\frac{1}{N}\sum_{i=1}^{N}x_{t_{i}}x_{t_{i}}^{T}$, and
$D=\smash{\widetilde{O}}(1)\cdot dD^{\prime}$,
$D^{\prime}=\smash{\widetilde{O}}(1)\cdot\mathrm{poly}(1/\alpha)\cdot(d+R^{2}+R_{w}^{2})$.
Here, $\smash{\widetilde{O}}(1)$ denotes a polylogarithmic factor in the
parameters defined in this section.

######  Remark 4.1.

Note that in the LDS case, $R_{w}=O(\sqrt{d})$ by standard concentration of
Gaussian norm. However, for slowly mixing systems ($\rho(A_{*})\to 1$),
$R_{x}$ can grow polynomially with $T$. Our bounds only degrade in the
logarithm of $R_{x}$, which is absorbed in $\smash{\widetilde{O}}(\cdot)$, and
the same happens with $1/\omega$.

Before presenting SON-SG and its analysis, we give some background on existing
techniques for CTS.

###  4.1 Existing Techniques and their Limitations

Even though Daskalakis et al. (2019) consider truncated linear regression with
no temporal dependencies, we will use the same likelihood-based objective.
Specifically, let

$\displaystyle\ell_{S}(\mu;y)\coloneqq-\frac{1}{2}\|y-\mu\|^{2}-\log\left(\int_{S}\exp\left(-\frac{1}{2}\left\|z-\mu\right\|^{2}\right)dz\right),$

and observe that given $\mathcal{F}_{t}$ and that $o_{t}=1$, we have that for
a candidate matrix $A$, the log-likelihood for $y_{t}$ is
$\ell_{S_{t}}(Ax_{t};y_{t})$. Also, let $f_{t}(A)$ be the (negative)
population log-likelihood:

$\displaystyle f_{t}(A)\coloneqq-\mathbb{E}_{y}\Big{[}\ell_{S_{t}}(Ax_{t};y)\
\Big{|}\ \mathcal{F}_{t},o_{t}=1\Big{]},$

and observe that
$f_{t}(A)=-\mathbb{E}_{y\sim\mathcal{N}\left(A_{*}x_{t},I,S_{t}\right)}\Big{[}\ell_{S_{t}}(Ax_{t};y)\Big{]}$.
Given the observed data, our goal will be to minimize
$f(A)\coloneqq\frac{1}{N}\sum_{i=1}^{N}f_{t_{i}}(A)$. To see why $f(A)$ is a
“good” objective, we take the first and second derivatives of
$f_{t}(A)$:121212$\otimes$ denotes Kronecker product.

$\displaystyle\nabla\mkern-2.5muf_{t}(A)=\mathbb{E}_{z\sim\mathcal{N}\left(Ax_{t},I,S_{t}\right)}\left[z\right]x_{t}^{\top}-\mathbb{E}_{y\sim\mathcal{N}\left(A_{*}x_{t},I,S_{t}\right)}\left[y\right]x_{t}^{\top}$
$\displaystyle\nabla\mkern-2.5mu^{2}f_{t}(A)=\text{Cov}_{z\sim\mathcal{N}\left(Ax_{t},I,S_{t}\right)}\left[z,z\right]\otimes\left(x_{t}x_{t}^{\top}\right),$
(3)

where $\nabla\mkern-2.5mu^{2}f_{t}(A)$ is used to denote
$\nabla\mkern-2.5mu^{2}f_{t}\left(\text{vec}\left(A^{\top}\right)\right)$, and
$\text{vec}(\cdot)$ is the standard vectorization. Now, note that
$\nabla\mkern-2.5muf_{t}(A_{*})=0$, and so $\nabla\mkern-2.5muf(A_{*})=0$.
Also, since the Kronecker product of positive semidefinite matrices (PSD) is
PSD, $f_{t}(A)$ is convex, and so $f(A)$ is also convex.131313As we mentioned
in the introduction, for censored LDSs, the negative log-likelihood is non-
convex. However, here we have convexity, because $f(A)$ corresponds to a part
of the overall log-likelihood. Now, if $f$ was _strongly-convex_
($\nabla\mkern-2.5mu^{2}f(A)\succ 0$), then $A_{*}$ would be the unique
optimal solution, justifying the use of the objective. Even though strong-
convexity does not hold, Daskalakis et al. (2019) show how to address this for
independent data, by restricting $A$ in some set that contains $A_{*}$, and
$\nabla\mkern-2.5mu^{2}f(A)\succeq\Omega(1)\cdot I$, inside the set. Let’s
assume (for now) that here, $\nabla\mkern-2.5mu^{2}f(A)\succeq\Omega(1)\cdot
I$ holds. Now, note that a priori, it is not clear how to optimize $f(A)$,
since we do not have a closed-form expression. An important conceptual
contribution of Daskalakis et al. (2019) is the observation that by sampling
$z_{t}\sim\mathcal{N}\left(Ax_{t},I,S_{t}\right)$,141414This is done via
rejection sampling, using the membership oracle for $S_{t}$. and computing
$v_{t}=(y_{t}-z_{t})x_{t}^{\top}$, we have $\mathbb{E}\big{[}v_{t}\ \big{|}\
\mathcal{F}_{t},o_{t}=1\big{]}=\nabla\mkern-2.5muf_{t}(A)$, i.e, we get an
unbiased gradient estimate. Based on this observation, they employ a variant
of SGD to minimize $f(A)$, but their algorithm is tailored to independent
data. The reason is that it processes the data in random order, and also does
multiple passes over them. Thus, by the time it computes $v_{t}$, it is very
likely that before that, it had processed $(x_{t}^{\prime},y_{t}^{\prime})$,
for $t^{\prime}>t$. Because of this, if the data are temporally dependent,
$v_{t}$ can be a _biased_ estimate of $\nabla\mkern-2.5muf_{t}(A)$.

###  4.2 Our Approach

To avoid the above issue, we need to process the data in temporal order. This
is exactly the case for Online Convex Optimization (OCO). In OCO though, the
goal is not to recover some parameter, but to minimize _regret_. However,
regret bounds can often be transformed to statistical recovery rates via
?online-to-batch? conversions (e.g., Cesa-Bianchi et al. (2004)). In our
setting, this conversion can be done, but is trickier than usual, and we will
deal with it later. Now, since we are aiming for a fast
$\smash{\widetilde{O}}(1/N)$-rate, the first natural attempt is online SGD,
which has only logarithmic (in $N$) regret, provided all $f_{t_{i}}$’s are
strongly-convex (Hazan (2019))151515In online-to-batch conversions, a regret-
bound $R_{N}>0$ often translates to $R_{N}/N$ statistical recovery rate..
Unfortunately, this in not true for any $f_{t_{i}}$, due to the rank-one
component $x_{t_{i}}x_{t_{i}}^{T}$ in the Hessian
$\nabla\mkern-2.5mu^{2}f_{t_{i}}(A)$ (3). However, there is still structure we
can exploit. Notice that every row of $\nabla\mkern-2.5muf_{t_{i}}(A)$ has the
same direction as $x_{t_{i}}$, which corresponds exactly to that ?problematic?
rank-one component in the Hessian. This structure is reminiscent of the _exp-
concavity_ property (Hazan et al. (2007)), which essentially is strong-
convexity, _in the direction of the gradient_ :

######  Definition 4.2.

A function $f$ is called $\lambda$-exp-concave, if for all $x$,
$\nabla\mkern-2.5mu^{2}f(x)\succcurlyeq\lambda\cdot\nabla\mkern-2.5muf(x)\nabla\mkern-2.5muf(x)^{\top}$.161616These
functions are called exp-concave, because this property is equivalent to
$e^{-\lambda f(x)}$ being concave.

For exp-concave functions, the Online Newton Step (ONS) algorithm, introduced
in Hazan et al. (2007), has regret that depends logarithmically in $N$.
Unfortunately, this result does not apply here:

##### Obstacles for ONS.

First, $f_{t_{i}}$’s are not necessarily exp-concave (unless $\lambda$ is
exponentially small, which is not useful). This is because of the covariance
term in 3. To the best of our knowledge, the idea used in Daskalakis et al.
(2019) to restrict $A$ is some appropriate set, does not resolve this issue,
due to temporal dependencies. The second obstacle, is that the regret bound of
ONS (Hazan et al. (2007)) will have linear dependence in $R_{x}$, which as we
said can grow as $\mathrm{poly}(T)$.

###  4.3 Stochastic Online Newton with Switching Gradients

We now describe SON-SG. First, we use as projection-set the ellipsoid
$\mathcal{K}$. Second, we use preconditioning as in ONS, but while in ONS the
preconditioner has outer-products of the gradients, here we use outer-products
of the covariates. This is done to simplify the analysis.

##### Switching Gradients.

The crucial difference with ONS is the choice of the $g_{i}$’s, by the
?SwitchGrad? function. To ease notation, suppose we are at time $t$, and
$t=t_{i}$ for some $i$. We define $A(t)=A_{i}$, and $g(t)=g_{i}$. In ONS,
$g(t)$ would simply be $\nabla\mkern-2.5muf_{t}(A(t))$. Of course, we do not
have access to this gradient, but as we said we can get a stochastic gradient
by sampling $z_{t}\sim\mathcal{N}(A(t)x_{t},I,S_{t})$, and setting
$g(t)=(z_{t}-y_{t})x_{t}^{\top}$. Sampling from
$\mathcal{N}(A(t)x_{t},I,S_{t})$ can be done via rejection sampling, using the
membership oracle. However, to be efficient, the mass
$\gamma_{t}\coloneqq\mathcal{N}(A(t)x_{t},I;S_{t})$ should be sufficiently
large. Unfortunately, here $\gamma_{t}$ can be exponentially small. This case
though is easily recognizable, by estimating $\gamma_{t}$ via sampling from
the normal $\mathcal{N}(A(t)x_{t},I)$, and counting how many times we hit
$S_{t}$, using the membership oracle. This is done by the ?Test? function. If
the Test returns ?True?, then with high probability (w.h.p),
$\gamma_{t}\geq\alpha^{O(1)}$, and so we can efficiently sample a stochastic
gradient, and assign it to $g(t)$. If it returns ?False?, then w.h.p,
$\gamma_{t}\leq\alpha^{\Omega(1)}$. They key idea here is that, as we will
show, $\gamma_{t}$ being small is actually an ?easy? case, and simply choosing
$g(t)=(A(t)x_{t}-y_{t})x_{t}^{\top}$ suffices to make progress towards
$A_{*}$. Observe that here $g(t)$ is a stochastic gradient of
$\widetilde{f}_{t}(A)=-\mathbb{E}_{y\sim\mathcal{N}\left(A_{*}x_{t},I,S_{t}\right)}\Big{[}\ell_{{\mathbb{R}}^{n}}(Ax_{t};y)\Big{]}$.
In other words, the Test is a ?switch? between $\nabla\mkern-2.5muf_{t}$ and
$\nabla\mkern-2.5mu\widetilde{f}_{t}$.

Input: $A_{0}\in{\mathbb{R}}^{n\times d}$, PSD matrix
$\Sigma_{0}\in{\mathbb{R}}^{d\times d}$, data
$(x_{t_{i}},y_{t_{i}})_{i=1}^{N}$.

$\eta=(2/\alpha)^{c_{\eta}}$ $\rhd c_{\eta}\geq 0$ is a large constant.

$\mathcal{K}=\\{A\in{\mathbb{R}}^{n\times d}:\ \|A-A_{0}\|_{\Sigma_{0}}\leq
1\\}$

$A_{1}=A_{0}$

for  _$i=1$ to $N$_ do

$g_{i}=\text{SwitchGrad}(A_{i}x_{t_{i}},x_{t_{i}},y_{t_{i}},S_{t_{i}})$

$\Sigma_{i}=\Sigma_{i-1}+x_{t_{i}}x_{t_{i}}^{\top}$

$\widetilde{A}_{i+1}=A_{i}-\eta\cdot g_{i}\Sigma_{i}^{-1}$

$A_{i+1}=\operatorname*{arg\,min}_{A\in\mathcal{K}}\|A-\widetilde{A}_{i+1}\|_{\Sigma_{i}}$

return $\widehat{A}=A_{N+1}$

Algorithm 1 Stochastic Online Newton with Switching Gradients

Input: $\mu,x,y,S$

$z=\mu$

if  _Test $(\mu,S)$_ then

Sample $z^{\prime}\sim\mathcal{N}(\mu,I,S)$ via rejection sampling using the
membership oracle $M_{S}$.

$z=z^{\prime}$

end if

return $g=(z-y)x^{T}$

Algorithm 2 SwitchGrad

Input: $\mu,S$.

$\gamma=(\alpha/2)^{c_{\gamma}}$, $\ k=\frac{4}{\gamma}\log{T}.$ $\rhd
c_{\gamma}\geq 0$ is a large constant.

Sample $\xi_{1},\dots,\xi_{k}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
i.i.d}}}{\sim}}N(\mu,I)$

$p=\frac{1}{k}\sum_{j=1}^{k}\mathds{1}\\{\xi_{j}\in S\\}$

return $(p\leavevmode\nobreak\ \geq\leavevmode\nobreak\ 2\gamma)$

Algorithm 3 Test

##  5 Proof of Theorem 2

In this section, we give an overview of the proof of Theorem 2, with an
emphasis on the novel technical components. Our goal is to convey the key
ideas, and so at some steps we are slightly informal. We provide the formal
and detailed proof in Appendix D.

##### The Generic Bound.

We first prove a bound on $\left\|\widehat{A}-A_{*}\right\|_{\Sigma}^{2}$
(remember that $\Sigma=\Sigma_{N}$ in Algorithm 1), which holds for any
sequence $g_{1},g_{2},\dots,g_{N}$. This bound will serve as a guideline for
choosing the $g_{i}$’s.

######  Lemma 5.1.

Independently of how $g_{i}$’s are chosen,

$\displaystyle\left\|\widehat{A}-A_{*}\right\|_{\Sigma}^{2}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ 1-\sum_{i=1}^{N}\left(2\eta\langle
g_{i},A_{i}-A_{*}\rangle-\left\|(A_{i}-A_{*})x_{t_{i}}\right\|^{2}\right)+\eta^{2}\sum_{i=1}^{N}\mathrm{tr}\left(g_{i}\Sigma_{i}^{-1}g_{i}^{\top}\right).$
(4)

The proof of the lemma is along the lines of the analysis of ONS in Hazan et
al. (2007), and we provide it in Appendix D.1. Let $E_{1}$ be the first sum in
4, and $E_{2}$ the second. We will show that for our choice of $g_{i}$’s,
$E_{1}$ is (almost) non-negative, and $E_{2}$ is not too large (both in
expectation). In the main text, we assume that $L=0$, since the extension for
general $L$ is straightforward.

### Bound on $E_{1}$.

Fix a time $t$, condition on $\mathcal{F}_{t}$, and suppose that $t=t_{i}$,
for some $i$. To ease notation, we define $A(t)=A_{i},\ g(t)=g_{i},\
\mu_{t}^{*}=A_{*}x_{t},\ \mu_{t}=A(t)x_{t}$, and $V_{t}=2\eta\langle
g(t),A(t)-A_{*}\rangle-\left\|(A(t)-A_{*})x_{t}\right\|^{2}$. To bound
$\mathbb{E}[E_{1}]$, we show (roughly) that $\mathbb{E}\big{[}V_{t}\ \big{|}\
\mathcal{F}_{t},t=t_{i}\big{]}\geq 0$. Observe that this immediately implies
$\mathbb{E}[E_{1}]\geq 0$. We consider two cases, based on what the Test
function returns.

##### Large Survival Probability.

Suppose at time $t$, Test returns ?True?. We call this event
$\mathcal{T}_{t}$, and here we assume that Test returning ?True? implies
$\mathcal{N}(\mu_{t},I;S_{t})\geq\gamma$ (this is correct w.h.p.).171717The
parameter $\gamma$ is defined in Algorithm 3. Also, in Appendix D, where we
give the details for handling the low-probability events, we show that
$\mathbb{E}[E_{1}]\geq\Delta$, for some $\Delta>0$, but small. Furthermore,
$z_{t}\sim\mathcal{N}(\mu_{t},I,S_{t})$, and $g(t)=(z_{t}-y_{t})x_{t}^{T}$.
Also, since $y_{t}\sim\mathcal{N}(\mu_{t}^{*},I,S_{t})$, we have

$\displaystyle\mathbb{E}\big{[}V_{t}\ \big{|}\
\mathcal{F}_{t},t=t_{i},\mathcal{T}_{t}\big{]}=2\eta\langle\nu_{t}-\nu_{t}^{*},\mu_{t}-\mu^{*}_{t}\rangle-\|\mu_{t}-\mu_{t}^{*}\|^{2},$
(5)

where $\nu_{t}=\mathbb{E}_{z\sim\mathcal{N}(\mu_{t},I,S_{t})}[z]$ and
$\nu_{t}^{*}=\mathbb{E}_{y\sim\mathcal{N}(\mu_{t}^{*},I,S_{t})}[y]$. Now, note
that since $t=t_{i}$ and $L=0$, we have
$\mathcal{N}(\mu_{t}^{*},I;S_{t})\geq\alpha\geq\gamma$. The key component of
our proof is the following lemma, which we prove here in detail.

######  Lemma 5.2.

Let
$\mathcal{L}_{S}(\mu;\mu^{*})=-\mathbb{E}_{y\sim\mathcal{N}(\mu^{*},I,S)}\big{[}\ell_{S}(\mu;y)\big{]}$,
where $\mu,\mu^{*}\in\mathbb{R}^{n}$ and $S\subseteq{\mathbb{R}}^{n}$. Suppose
that $\mathcal{N}(\mu,I;S),\ \mathcal{N}(\mu^{*},I;S)\geq\gamma$. Then, there
exists an absolute constant $c>0$ such that

$\displaystyle\big{\langle}\nabla\mkern-2.5mu_{\mu}\mathcal{L}_{S}(\mu;\mu^{*}),\mu-\mu^{*}\big{\rangle}\leavevmode\nobreak\
\geq\leavevmode\nobreak\ \left(\gamma/2\right)^{c}\cdot\|\mu-\mu^{*}\|^{2}.$
(6)

Lemma 5.2 implies that, given large enough $c_{\eta}$,181818Remember that
$\eta=(2/\alpha)^{c_{\eta}}$. the expectation in (5) is non-negative. Indeed,
note that $\nabla\mkern-2.5mu_{\mu}L_{S}(\mu;\mu^{*})=\nu-\nu^{*},$ where
$\nu=\mathbb{E}_{z\sim\mathcal{N}(\mu,I,S)}[z]$ and
$\nu^{*}=\mathbb{E}_{y\sim\mathcal{N}(\mu^{*},I,S)}[z]$, so

$\displaystyle\mathbb{E}\big{[}V_{t}\ \big{|}\
\mathcal{F}_{t},t=t_{i},\mathcal{T}_{t}\big{]}\geq(2\eta(\gamma/2)^{c}-1)\cdot\|\mu_{t}-\mu_{t}^{*}\|^{2}$
$\displaystyle=\left(2\left(2/\alpha\right)^{c_{\eta}}(\alpha/4)^{c\cdot
c_{\gamma}}-1\right)\cdot\|\mu_{t}-\mu_{t}^{*}\|^{2}$
$\displaystyle=\left(\frac{2^{c_{\eta}+1-2c\cdot
c_{\gamma}}}{a^{c_{\eta}-c\cdot
c_{\gamma}}}-1\right)\cdot\|\mu_{t}-\mu_{t}^{*}\|^{2}\geq 0,$

for any constant $c_{\eta}\geq 2c\cdot c_{\gamma}$. We now prove Lemma 5.2.

###### Proof.

Let $s(\gamma)\coloneqq\sqrt{2\log(1/\gamma)}+1$. We will need two technical
claims, which hold for any $\mu,\mu^{*}\in{\mathbb{R}}^{n}$ and
$S\subseteq{\mathbb{R}}^{n}$.

######  Claim 5.3.

Let $\nu=\mathbb{E}_{z\sim\mathcal{N}(\mu,I,S)}[z]$. If
$\mathcal{N}(\mu,I;S)\geq\gamma$, then $\|\nu-\mu\|\leq s(\gamma)$.

######  Claim 5.4.

Suppose $\mathcal{N}(\mu^{*},I;S)\geq\gamma$, and for some $\widetilde{\mu}$
we have $\|\widetilde{\mu}-\mu^{*}\|\leq c\cdot s(\gamma)$. Then,

$\displaystyle\text{Cov}_{z\sim\mathcal{N}(\widetilde{\mu},I,S)}[z,z]\succcurlyeq(\gamma/2)^{\mathrm{poly}(c)}\cdot
I.$

Both Claims are mainly from Daskalakis et al. (2018). Claim 5.3 is Lemma 6 in
that paper. Claim 5.4 is not explicitly stated, but can be derived by slightly
adapting their proof (see Appendix H.1). We consider two cases:

Case 1: $\|\mu-\mu^{*}\|\geq 4s(\gamma)$. Then,

$\displaystyle\langle\nu-\nu^{*},\mu-\mu^{*}\rangle$
$\displaystyle=\|\mu-\mu^{*}\|^{2}+\langle\nu-\mu,\mu-\mu^{*}\rangle+\langle\mu^{*}-\nu^{*},\mu-\mu^{*}\rangle$
$\displaystyle\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\|\mu-\mu^{*}\|^{2}-\|\nu-\mu\|\cdot\|\mu-\mu^{*}\|-\|\nu^{*}-\mu^{*}\|\cdot\|\mu-\mu^{*}\|$

Since $\mathcal{N}(\mu,I;S),\ \mathcal{N}(\mu^{*},I;S)\geq\gamma$, Claim 5.3
implies $\|\nu-\mu\|,\|\nu^{*}-\mu^{*}\|\leq s(\gamma)$. Being in Case 1,

$\displaystyle\langle\nu-\nu^{*},\mu-\mu^{*}\rangle\leavevmode\nobreak\
\geq\leavevmode\nobreak\
\|\mu-\mu^{*}\|\cdot\big{(}\|\mu-\mu^{*}\|-2s(\gamma)\big{)}\leavevmode\nobreak\
\geq\leavevmode\nobreak\ \|\mu-\mu^{*}\|^{2}/2.$

Case 2: $\|\mu-\mu^{*}\|<4s(\gamma)$. To ease notation, fix $\mu^{*},S$, and
let $\mathcal{L}(\mu)=\mathcal{L}_{S}(\mu;\mu^{*})$. From fundamental theorem
of calculus,

$\displaystyle\nabla\mkern-2.5mu\mathcal{L}(\mu)-\nabla\mkern-2.5mu\mathcal{L}(\mu^{*})=\int_{0}^{1}\nabla\mkern-2.5mu^{2}\mathcal{L}\left(\mu(\theta)\right)d\theta\cdot(\mu-\mu^{*}),$

where $\mu(\theta)\coloneqq\mu^{*}+\theta(\mu-\mu^{*})$. Since
$\nabla\mkern-2.5muL(\mu^{*})=0$,

$\displaystyle\big{\langle}\nabla\mkern-2.5mu\mathcal{L}(\mu),\mu-\mu^{*}\big{\rangle}=\int_{0}^{1}\Big{\langle}\nabla\mkern-2.5mu^{2}\mathcal{L}\left(\mu(\theta)\right)(\mu-\mu^{*}),\mu-\mu^{*}\Big{\rangle}d\theta.$
(7)

For $\theta\in(0,1)$, $\|\mu(\theta)-\mu^{*}\|=\theta\|\mu-\mu^{*}\|\leq
O\left(s(\gamma)\right)$. Using $\mathcal{N}(\mu^{*},I,S)\geq\gamma$ and Claim
5.4,

$\displaystyle\nabla\mkern-2.5mu^{2}\mathcal{L}\left(\mu(\theta)\right)=\text{Cov}_{z\sim\mathcal{N}\left(\mu(\theta),I,S\right)}[z,z]\succcurlyeq(\gamma/2)^{O(1)}\cdot
I.$

Using 7, we finish the proof. ∎

##### Remark.

We want to highlight an important qualitative difference between Lemma 5.2 and
all recent works in CTS. Suppose $\gamma=\Omega(1)$ and let
$v=\frac{\mu-\mu^{*}}{\|\mu-\mu^{*}\|}$. From the argument in Case 2, 6 can be
rephrased as

$\displaystyle\mathbb{E}_{\widetilde{\mu}\sim[\mu^{*},\mu]}\Big{[}\big{\langle}\text{Cov}_{z\sim\mathcal{N}\left(\widetilde{\mu},I,S\right)}[z,z]\cdot
v,v\big{\rangle}\Big{]}\geq\Omega(1),$ (8)

where $\widetilde{\mu}$ is distributed uniformly on the segment
$[\mu,\mu^{*}]$. In other words, the average variance in the $v$-direction is
$\Omega(1)$. This is an anti-concentration bound. As we mentioned, proving
anti-concentration bounds for truncated normals
$\mathcal{N}(\smash{\widetilde{\mu}},I,S)$ is a core component in all recent
works in CTS, where this task is reduced to lower bounding
$\mathcal{N}(\smash{\widetilde{\mu}},I;S)$. However, inequality (8) cannot be
proven with this methodology. We illustrate this with an insightful example
(Figure 3). In the example, we consider $\mu,\mu^{*}\in{\mathbb{R}}^{d}$ and
$\|\mu-\mu^{*}\|=\sqrt{d}$, because the guaranteed bound in the LDS-case for
$\|\mu_{t}-\mu_{t}^{*}\|$ will be $\Theta(\sqrt{d})$. Let $\mu^{*}=0$,
$\mu=\sqrt{d}\cdot e_{1}$ ($e_{1}$ is the standard-basis vector),
$S=\\{x\in{\mathbb{R}}^{d}:x_{1}\in(-\infty,0]\cup[\sqrt{d},+\infty)\\}$.
Observe that the conditions of Lemma 5.2 are satisfied with $\gamma=1/2$.
However, for most $\smash{\widetilde{\mu}}\in[\mu^{*},\mu]$, the mass
$\mathcal{N}(\smash{\widetilde{\mu}},I;S)$ is exponentially small (in $d$).
Consider now $\smash{\widetilde{\mu}}$ exactly in the middle of $\mu^{*},\mu$.
Even though $\mathcal{N}(\smash{\widetilde{\mu}},I;S)=\exp(-\Omega(d))$, the
variance in the $e_{1}$ direction is $\Omega(d)$, due to symmetry. It can
actually be shown that precisely this $\smash{\widetilde{\mu}}$ and small
perturbations of it make the average variance $\Omega(1)$ in (8). Note that it
is necessary for both corners ($\mu$ and $\mu^{*}$) to have high survival
probability, e.g., in Figure 3 (for the same distance-scales) it can be shown
that the variance is $O(1/d)$.

Figure 2: $\Omega(d)$ variance

Figure 3: $O(1/d)$ variance

##### Small Survival Probability.

Suppose that at time $t$, Test returns ?False? ($\neg\mathcal{T}_{t}$).
Suppose also that this implies $\mathcal{N}(\mu_{t},I;S_{t})\leq 4\gamma$
(again this is w.h.p). We will show that $\mathbb{E}\big{[}V_{t}\ \big{|}\
\mathcal{F}_{t},t=t_{i},\neg\mathcal{T}_{t}\big{]}\geq 0$. Observe that given
$\neg\mathcal{T}_{t}$, we have $g(t)=(\mu_{t}-y_{t})x_{t}^{\top}$, and so

$\displaystyle\mathbb{E}\big{[}V_{t}\ \big{|}\
\mathcal{F}_{t},t=t_{i},\neg\mathcal{T}_{t}\big{]}=2\eta\langle\mu_{t}-\nu_{t}^{*},\mu_{t}-\mu^{*}_{t}\rangle-\|\mu_{t}-\mu_{t}^{*}\|^{2}.$
(9)

Again, since $t=t_{i}$ and $L=0$, we have
$\mathcal{N}(\mu_{t}^{*},I;S_{t})\geq\alpha$, so by Claim 5.3,
$\|\nu_{t}^{*}-\mu_{t}^{*}\|\leavevmode\nobreak\ \leq\leavevmode\nobreak\
s(\alpha)$. We need one more technical claim.

######  Claim 5.5.

If $\mathcal{N}(\mu^{*},I;S)\geq\alpha$, and $\|\mu-\mu^{*}\|\leq c\cdot
s(\alpha)$, then $\mathcal{N}(\mu,I;S)\geq(\alpha/2)^{\mathrm{poly}(c)}$.

Again, Claim 5.5 is proven in Appendix H.2, by slightly adapting the analysis
of Daskalakis et al. (2018). Now, we claim that
$\|\mu_{t}-\mu_{t}^{*}\|>2s(\alpha)$, provided that $c_{\gamma}=O(1)$ is
sufficiently large. Indeed, suppose $\|\mu_{t}-\mu_{t}^{*}\|\leq 2s(\alpha)$.
Combining with $\mathcal{N}(\mu_{t}^{*},I;S_{t})\geq\alpha$ and Claim 5.5, we
get
$4(\alpha/2)^{c_{\gamma}}=4\gamma\geq\mathcal{N}(\mu_{t},I;S_{t})\geq(\alpha/2)^{O(1)}$,
which is a contradiction for large enough $c_{\gamma}=O(1)$. Using that
$\|\nu_{t}^{*}-\mu_{t}^{*}\|\leq s(\alpha)$, we get

$\displaystyle\langle\mu_{t}-\nu_{t}^{*},\mu_{t}-\mu^{*}_{t}\rangle$
$\displaystyle=\|\mu_{t}-\mu^{*}_{t}\|^{2}+\langle\mu_{t}^{*}-\nu_{t}^{*},\mu_{t}-\mu^{*}_{t}\rangle\geq\|\mu_{t}-\mu^{*}_{t}\|^{2}-\|\mu_{t}^{*}-\nu_{t}^{*}\|\cdot\|\mu_{t}-\mu^{*}_{t}\|$
$\displaystyle\geq\|\mu_{t}-\mu^{*}_{t}\|\cdot\big{(}\|\mu_{t}-\mu^{*}_{t}\|-s(\alpha)\big{)}\geq\|\mu_{t}-\mu_{t}^{*}\|^{2}/2.$

Since $\eta\geq 1$, Equation 27 implies $\mathbb{E}\big{[}V_{t}\ \big{|}\
\mathcal{F}_{t},t=t_{i},\neg\mathcal{T}_{t}\big{]}\geq 0$. Thus,
$\mathbb{E}[V_{t}\ |\ \mathcal{F}_{t},t=t_{i}]\geq 0$, and
$\mathbb{E}[E_{1}]\geq 0$.

### Bound on $E_{2}$

Using the assumption that $\mathcal{K}$ is $(R,\omega)$-accurate, we prove
that

$\displaystyle\mathbb{E}\big{[}E_{2}\big{]}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \smash{\widetilde{O}}(1)\cdot
d\left(d+R^{2}+R_{w}^{2}\right).$ (10)

Given this bound, we have

$\displaystyle\mathbb{E}\left[\left\|\widehat{A}-A_{*}\right\|_{\Sigma}^{2}\right]$
$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\
1-\mathbb{E}[E_{1}]+\eta^{2}\mathbb{E}[E_{2}]\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\smash{\widetilde{O}}(1)\cdot\mathrm{poly}(1/\alpha)\cdot
d\left(d+R^{2}+R_{w}^{2}\right),$

which finishes the proof of Theorem 2 (for $L=0$). Now, we illustrate the main
steps for proving (10) (the complete proof is in Appendix F). Let $z_{t_{i}}$
be the value of the variable $z$ of the SwitchGrad function, at the end of its
execution, during iteration $i$. So,
$g_{i}=(z_{t_{i}}-y_{t_{i}})x_{t_{i}}^{\top}$, and thus
$\mathrm{tr}(g_{i}\Sigma_{i}^{-1}g_{i}^{\top})=\|z_{t_{i}}-y_{t_{i}}\|^{2}\cdot
x_{t_{i}}^{\top}\Sigma_{i}^{-1}x_{t_{i}}$. Summing over $i$,

$\displaystyle E_{2}=\sum_{i=1}^{N}\|z_{t_{i}}-y_{t_{i}}\|^{2}\cdot
x_{t_{i}}^{\top}\Sigma_{i}^{-1}x_{t_{i}}\leq\max_{i}\left\\{\|z_{t_{i}}-y_{t_{i}}\|^{2}\right\\}\cdot\sum_{i=1}^{N}x_{t_{i}}^{\top}\Sigma_{i}^{-1}x_{t_{i}}.$
(11)

Using the recurrence $\Sigma_{i}=\Sigma_{i-1}+x_{t_{i}}x_{t_{i}}^{\top}$, we
can show that $\sum_{i=1}^{N}x_{t_{i}}^{\top}\Sigma_{i}^{-1}x_{t_{i}}\leq
d\left(\log{|\Sigma_{N}|^{1/d}}+\log{(1/\omega)}\right)$, where $|\Sigma_{N}|$
denotes the determinant. The proof of this is given in Appendix F (Claim F.2),
and is based on a linear-algebraic technique of Hazan et al. (2007). Combining
with $E_{2}$, and applying Cauchy-Schwarz,

$\displaystyle\mathbb{E}[E_{2}]=O(d)\cdot\sqrt{\mathbb{E}\left[\max_{i}\|z_{t_{i}}-y_{t_{i}}\|^{4}\right]}\cdot\sqrt{\mathbb{E}\left[\log^{2}{|\Sigma_{N}|^{1/d}}\right]+\smash{\widetilde{O}}(1)}.$

We use that $\mathbb{E}[\|x_{t}\|^{2}]\leq R_{x}^{2}$, to control
$\mathbb{E}\left[\log^{2}{|\Sigma_{N}|^{1/d}}\right]$. Specifically, in
Appendix F (Claim F.3), we show that
$\mathbb{E}\left[\log^{2}{|\Sigma_{N}|^{1/d}}\right]\leq\log^{2}\left(e+T\cdot
R_{x}^{2}\right)=\smash{\widetilde{O}}(1)$. The last step is to prove that

$\displaystyle\mathbb{E}\left[\max_{i}\|z_{t_{i}}-y_{t_{i}}\|^{4}\right]\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\smash{\widetilde{O}}(1)\cdot(d^{2}+R^{4}+R_{w}^{4}).$ (12)

This is shown in Appendix F (Claim F.4), and here we give a proof-sketch. Fix
an $i$, and let $t=t_{i}$. We decompose $\|z_{t}-y_{t}\|$:

$\displaystyle\|z_{t}-y_{t}\|=\|z_{t}-\mu_{t}+\mu_{t}-\mu_{t}^{*}+\mu_{t}^{*}-y_{t}\|$
$\displaystyle\leq\|z_{t}-\mu_{t}\|+\|\mu_{t}-\mu_{t}^{*}\|+\|\mu_{t}^{*}-y_{t}\|$
$\displaystyle=\|z_{t}-\mu_{t}\|\cdot\mathds{1}\\{\mathcal{T}_{t}\\}+\|\mu_{t}-\mu_{t}^{*}\|+\|\mu_{t}^{*}-y_{t}\|$
$\displaystyle=\|z_{t}-\mu_{t}\|\cdot\mathds{1}\\{\mathcal{T}_{t}\\}+\|\mu_{t}-\mu_{t}^{*}\|+\|w_{t}\|$
(13)

where for the second-to-last step we use that on $\neg\mathcal{T}_{t}$, we
have $z_{t}=\mu_{t}$. Now, $\|w_{t}\|$ is controlled using the assumption that
it is $R_{w}^{2}$-subgaussian. Now,

$\displaystyle\|\mu_{t}-\mu_{t}^{*}\|=\left\|(A(t)-A_{*})x_{t}\right\|$
$\displaystyle=\left\|(A(t)-A_{*})\Sigma_{0}^{1/2}\Sigma_{0}^{-1/2}x_{t}\right\|$
$\displaystyle\leq\left\|(A(t)-A_{*})\Sigma_{0}^{1/2}\right\|_{2}\cdot\left\|\Sigma_{0}^{-1/2}x_{t}\right\|$
$\displaystyle\leq\left\|A(t)-A_{*}\right\|_{\Sigma_{0}}\cdot\left\|\Sigma_{0}^{-1/2}x_{t}\right\|$
$\displaystyle\leq 2\left\|\Sigma_{0}^{-1/2}x_{t}\right\|,$

where for the last step we used that both $A(t)$ and $A_{*}$ belong to
$\mathcal{K}$, which is guaranteed by the projection step in Algorithm 1, and
the assumption that $\mathcal{K}$ is $(R,\omega)$-accurate. Now,
$\left\|\Sigma_{0}^{-1/2}x_{t}\right\|$ is controlled using the assumption
that it is $R^{2}$-subgaussian (again because of the $(R,\omega)$-accuracy of
$\mathcal{K}$). The final step is to control
$\|z_{t}-\mu_{t}\|\cdot\mathds{1}\\{\mathcal{T}_{t}\\}$. As we did previously,
we assume that Test returning ?True? implies
$\mathcal{N}(\mu_{t},I;S_{t})\geq\gamma$. Now, it can be shown (Appendix H,
Claims H.1, H.2) that $\mathcal{N}(\mu_{t},I;S_{t})\geq\gamma$ implies that
$\|z_{t}-\mu_{t}\|$ is
$O\left(\log\left(\frac{1}{2\gamma}\right)d\log{d}\right)$-subgaussian. Now,
the bound (12) follows from standard properties of subgaussian random
variables.

##  6 The Initial Ellipsoid and Proof of Theorem 1

Here, we provide the overall algorithm (Algorithm 4), and an outline of the
proof of Theorem 1. Let
$\mathcal{I}_{0}=\\{t\in[T]:(x_{t},x_{t+1})\in\mathcal{P}_{0}\\}$, and
$\mathcal{I}_{1}=\\{t\in[T]:(x_{t},x_{t+1})\in\mathcal{P}_{1}\\}$.

$A_{0}=\operatorname*{arg\,min}_{A\in{\mathbb{R}}^{d\times
d}}\sum_{t\in\mathcal{I}_{0}}\|x_{t+1}-Ax_{t}\|^{2}$

$\Sigma_{0}=\frac{1}{s\cdot|\mathcal{I}_{0}|}\cdot\sum_{t\in\mathcal{I}_{0}}x_{t}x_{t}^{\top}$,
where $s=c_{s}\left(\sqrt{\log{(1/\alpha)}}+1\right)$. $\rhd c_{s}\geq 0$ is a
large constant.

Get $\widehat{A}$ by running SON-SG (Algorithm 1) with $A_{0},\Sigma_{0}$, and
dataset $\mathcal{P}_{1}$.

return $\widehat{A}$

Algorithm 4 SON-SG for censored linear dynamics

The least-squares method when all $x_{t}$’s are observed was analyzed in
Simchowitz et al. (2018). Here, we observe only a subset the $x_{t}$’s. In
Appendix G, we generalize the ?small-ball? technique of Simchowitz et al.
(2018), to prove the following theorem.

######  Theorem 3.

There exist
$c_{1},c_{2},c_{3}=\mathrm{poly}\left(\frac{1}{\alpha\beta}\right)$, such that
if
$T\geq\widetilde{\Theta}(c_{1})\cdot\left(d^{2}+\frac{d}{1-\rho(A_{*})}+dL\right)$,
then with probability $1-o(1)$, the ellipsoid
$\mathcal{K}=\\{A\in{\mathbb{R}}^{d\times d}:\|A-A_{0}\|_{\Sigma_{0}}\leq
1\\}$ is $(R,\omega)$-accurate with $R=c_{2}\sqrt{d}$, $\omega=1/c_{2}$, and
also
$\frac{1}{|\mathcal{I}_{1}|}\sum_{t\in\mathcal{I}_{1}}x_{t}x_{t}^{T}\succcurlyeq\frac{1}{c_{3}}\Gamma_{T}$.

We now prove Theorem 1 using Theorems 2 and 3.

###### Proof.

We use the time-series model with $y_{t}=x_{t+1}$, $S_{t}=\mathcal{S}_{t+1}$,
$o_{t}=\mathbbm{1}(t\in\mathcal{I}_{1})$. Thus,
$B(\alpha)\subseteq\mathcal{B}(\alpha)$, so $\mathbb{E}[|B(\alpha)|]\leq L$.
Let $\mathcal{E}_{0}$ be the event that all guarantees in Theorem 3 hold, so
$\operatorname{\mathbb{P}}[\neg\mathcal{E}_{0}]\leq o(1)$. As we mentioned,
$\|w_{t}\|$ is $O(d)$-subgaussian. Also, in Appendix H.3, we show that
$\mathbb{E}[\|x_{t}\|^{2}]$ is polynomial in all parameters. Let
$\Sigma=\frac{1}{|\mathcal{I}_{1}|}\sum_{t\in\mathcal{I}_{1}}x_{t}x_{t}^{T}$.
By conditioning on $\mathcal{E}_{0}$ and applying Theorem 2, using Markov’s
inequality in (2), we have that with probability at least $1-\delta$,
191919Observe that our bounds depend on $1/\delta$. It is possible to achieve
$\log{(1/\delta)}$ dependence, but with more technical proofs. To keep the
presentation simpler, we chose not to optimize this dependence.

$\displaystyle\left\|\widehat{A}-A_{*}\right\|_{\Sigma}^{2}$
$\displaystyle\leq\frac{\smash{\widetilde{O}}(C)}{\delta
N}\cdot\left(d(d+R^{2}+R_{w}^{2})+L(d+R^{2}+R_{w}^{2})\right)\leq\smash{\widetilde{O}}(C)\cdot\frac{d^{2}+dL}{\delta
N}.$ (14)

where $C=\mathrm{poly}\left(\frac{1}{\alpha\beta}\right)$. Now, on
$\mathcal{E}_{0}$,
$\Sigma\succcurlyeq\Gamma_{T}/\mathrm{poly}\left(\frac{1}{\alpha\beta}\right)$.
From Proposition 3.1, $\operatorname{\mathbb{P}}\left[N<\frac{\alpha\beta
T}{4}\right]\leq o(1)$. Thus, by choosing small enough $\delta=\Omega(1)$, we
are done. ∎

##  7 Conclusion and Future Work

In this paper, we developed the first computationally and statistically
efficient algorithm for learning censored LDSs. We believe that there are
several interesting directions for future work:

  * •

The LDSs studied here ($x_{t+1}=A_{*}x_{t}+w_{t}$) often appear in the
literature under the name ?vector autoregressive models of order 1? (VAR(1)).
By including more lagged states in the equation, we get the VAR$(p)$ model:
$x_{t+1}=A_{1}x_{t}+A_{2}x_{t-1}+\dots+A_{p}x_{t-p+1}+w_{t}$, where $p\geq 1$.
Can we efficiently learn censored VAR$(p)$ models? This case (in 1-d) was
considered by Zeger and Brookmeyer (1986) and Park et al. (2007). The
challenge here is that the extension of our approach would use only tuples of
$p$ consecutive observations, which will be very rare for large $p$. Even for
$p=1$, can we leverage the isolated observations?

  * •

In many systems, we do not observe $x_{t}$ directly, but only $Cx_{t}$ for a
short matrix $C\in{\mathbb{R}}^{d_{0}\times d}$, where $d_{0}\leq d$. These
are called partially-observed LDSs, and their censored version was studied by
Allik et al. (2015). Understanding the sample complexity here would require
overcoming the challenge sketched above, i.e., going beyond long tuples of
consecutive observations.

  * •

Finally, censoring often occurs in coordinate level, i.e., only a subset of
the coordinates of $x_{t}$ is observed. This can be thought of as a ReLU
nonlinearity, and shows up in applications with sensor saturations (Yang and
Li (2009)). Can we efficiently learn the system under coordinate-level
censoring?

## References

  * Agarwal et al. (2019) Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh.  Online control with adversarial disturbances.  In _International Conference on Machine Learning_ , pages 111–119. PMLR, 2019.
  * Allik et al. (2015) Bethany Allik, Cory Miller, Michael J Piovoso, and Ryan Zurakowski.  The tobit kalman filter: an estimator for censored measurements.  _IEEE Transactions on Control Systems Technology_ , 24(1):365–371, 2015.
  * Arora et al. (2015) Sanjeev Arora, Rong Ge, Tengyu Ma, and Ankur Moitra.  Simple, efficient, and neural algorithms for sparse coding.  In _Conference on learning theory_ , pages 113–149. PMLR, 2015.
  * Arora et al. (2019) Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  In _International Conference on Machine Learning_ , pages 322–332. PMLR, 2019.
  * Bhattacharyya et al. (2020) Arnab Bhattacharyya, Rathin Desai, Sai Ganesh Nagarajan, and Ioannis Panageas.  Efficient statistics for sparse graphical models from truncated samples.  _arXiv preprint arXiv:2006.09735_ , 2020.
  * Cesa-Bianchi et al. (2004) Nicolo Cesa-Bianchi, Alex Conconi, and Claudio Gentile.  On the generalization ability of on-line learning algorithms.  _IEEE Transactions on Information Theory_ , 50(9):2050–2057, 2004.
  * Cohen (1991) A Clifford Cohen.  _Truncated and censored samples: theory and applications_.  CRC press, 1991.
  * Daskalakis et al. (2018) Constantinos Daskalakis, Themis Gouleakis, Chistos Tzamos, and Manolis Zampetakis.  Efficient statistics, in high dimensions, from truncated samples.  In _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 639–649. IEEE, 2018.
  * Daskalakis et al. (2019) Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis.  Computationally and statistically efficient truncated regression.  In _Conference on Learning Theory_ , pages 955–960, 2019.
  * Daskalakis et al. (2020) Constantinos Daskalakis, Dhruv Rohatgi, and Manolis Zampetakis.  Truncated linear regression in high dimensions.  _arXiv preprint arXiv:2007.14539_ , 2020.
  * Diakonikolas et al. (2019) Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart.  Robust estimators in high-dimensions without the computational intractability.  _SIAM Journal on Computing_ , 48(2):742–864, 2019\.
  * Fotakis et al. (2020) Dimitris Fotakis, Alkis Kalavasis, and Christos Tzamos.  Efficient parameter estimation of truncated boolean product distributions.  In _Conference on Learning Theory_ , pages 1586–1600. PMLR, 2020\.
  * Galton (1898) Francis Galton.  An examination into the registered speeds of american trotting horses, with remarks on their value as hereditary data.  _Proceedings of the Royal Society of London_ , 62(379-387):310–315, 1898.
  * Ghai et al. (2020) Udaya Ghai, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang.  No-regret prediction in marginally stable systems.  _arXiv preprint arXiv:2002.02064_ , 2020.
  * Hausman and Wise (1977) Jerry A Hausman and David A Wise.  Social experimentation, truncated distributions, and efficient estimation.  _Econometrica: Journal of the Econometric Society_ , pages 919–938, 1977.
  * Hazan (2019) Elad Hazan.  Introduction to online convex optimization.  _arXiv preprint arXiv:1909.05207_ , 2019.
  * Hazan et al. (2007) Elad Hazan, Amit Agarwal, and Satyen Kale.  Logarithmic regret algorithms for online convex optimization.  _Machine Learning_ , 69(2-3):169–192, 2007.
  * Hazan et al. (2020) Elad Hazan, Sham Kakade, and Karan Singh.  The nonstochastic control problem.  In _Algorithmic Learning Theory_ , pages 408–421. PMLR, 2020.
  * Honaker and King (2010) James Honaker and Gary King.  What to do about missing values in time-series cross-section data.  _American journal of political science_ , 54(2):561–581, 2010.
  * Ilyas et al. (2020) Andrew Ilyas, Emmanouil Zampetakis, and Constantinos Daskalakis.  A theoretical and practical framework for regression and classification from truncated samples.  In _International Conference on Artificial Intelligence and Statistics_ , pages 4463–4473. PMLR, 2020.
  * Johannsen and Mertens (2018) Benjamin Kramer Johannsen and Elmar Mertens.  A time series model of interest rates with the effective lower bound.  2018\.
  * Kontonis et al. (2019) Vasilis Kontonis, Christos Tzamos, and Manolis Zampetakis.  Efficient truncated statistics with unknown truncation.  In _2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 1578–1595. IEEE, 2019.
  * Lattimore and Szepesvári (2020) Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Lee and Maddala (1985) Lung-Fei Lee and GS Maddala.  The common structure of tests for selectivity bias, serial correlation, heteroscedasticity and non-normality in the tobit model.  _International Economic Review_ , pages 1–20, 1985.
  * Ljung (1999) Lennart Ljung.  System identification.  _Wiley encyclopedia of electrical and electronics engineering_ , pages 1–19, 1999.
  * Nagarajan and Panageas (2020) Sai Ganesh Nagarajan and Ioannis Panageas.  On the analysis of em for truncated mixtures of two gaussians.  In _Algorithmic Learning Theory_ , pages 634–659. PMLR, 2020.
  * Oymak and Ozay (2019) Samet Oymak and Necmiye Ozay.  Non-asymptotic identification of lti systems from a single trajectory.  In _2019 American control conference (ACC)_ , pages 5655–5661. IEEE, 2019.
  * Park et al. (2007) Jung Wook Park, Marc G Genton, and Sujit K Ghosh.  Censored time series analysis with autoregressive moving average models.  _Canadian Journal of Statistics_ , 35(1):151–168, 2007.
  * Pearson (1902) Karl Pearson.  On the systematic fitting of frequency curves.  _Biometrika_ , 2:2–7, 1902.
  * Sarkar and Rakhlin (2019) Tuhin Sarkar and Alexander Rakhlin.  Near optimal finite time identification of arbitrary linear dynamical systems.  In _International Conference on Machine Learning_ , pages 5610–5618. PMLR, 2019.
  * Simchowitz (2020) Max Simchowitz.  Making non-stochastic control (almost) as easy as stochastic.  _arXiv preprint arXiv:2006.05910_ , 2020.
  * Simchowitz et al. (2018) Max Simchowitz, Horia Mania, Stephen Tu, Michael I Jordan, and Benjamin Recht.  Learning without mixing: Towards a sharp analysis of linear system identification.  _arXiv preprint arXiv:1802.08334_ , 2018.
  * Simchowitz et al. (2019) Max Simchowitz, Ross Boczar, and Benjamin Recht.  Learning linear dynamical systems with semi-parametric least squares.  In _Conference on Learning Theory_ , pages 2714–2802. PMLR, 2019\.
  * Simchowitz et al. (2020) Max Simchowitz, Karan Singh, and Elad Hazan.  Improper learning for non-stochastic control.  In _Conference on Learning Theory_ , pages 3320–3436. PMLR, 2020\.
  * Tobin (1958) James Tobin.  Estimation of relationships for limited dependent variables.  _Econometrica: journal of the Econometric Society_ , pages 24–36, 1958.
  * Tsiamis and Pappas (2019) Anastasios Tsiamis and George J Pappas.  Finite sample analysis of stochastic system identification.  In _2019 IEEE 58th Conference on Decision and Control (CDC)_ , pages 3648–3654. IEEE, 2019.
  * van Handel (2014) Ramon van Handel.  Probability in high dimension.  Technical report, PRINCETON UNIV NJ, 2014.
  * Vershynin (2018) Roman Vershynin.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.
  * Yang and Li (2009) Fuwen Yang and Yongmin Li.  Set-membership filtering for systems with sensor saturation.  _Automatica_ , 45(8):1896–1902, 2009.
  * Yu (1994) Bin Yu.  Rates of convergence for empirical processes of stationary mixing sequences.  _The Annals of Probability_ , pages 94–116, 1994.
  * Zeger and Brookmeyer (1986) Scott L Zeger and Ron Brookmeyer.  Regression analysis with censored autocorrelated data.  _Journal of the American Statistical Association_ , 81(395):722–729, 1986.

##  Appendix A Additional Notation

For a random variable $X$, we denote by $\|X\|_{\psi_{2}}$ the subgaussian
norm of $X$, i.e.,

$\displaystyle\|X\|_{\psi_{2}}=\inf\\{\sigma>0:\
\mathbb{E}[\exp(X^{2}/\sigma^{2})]\leq 2\\}.$

For a random vector $X$, the sugaussian norm is
$\|X\|_{\psi_{2}}=\sup_{v\in\mathcal{S}^{d-1}}\|v^{\top}X\|_{\psi_{2}}$. For
two reals $a,b$ we denote $a\lor b$ and $a\land b$ the maximum and minimum
respectively.

##  Appendix B One-dimensional Example

Note that $x_{t+1}=\sum_{s=0}^{t-1}a_{*}^{s}w_{t-s}$, so
$x_{t+1}\sim\mathcal{N}(0,\sum_{s=0}^{t-1}a_{*}^{2s})$. We will need the
following claim.

######  Claim B.1.

Under Assumption 2 with $\beta=\Omega(1)$, we must have $\lambda\leq
O\left(\frac{1}{\sqrt{1-a_{*}}}\right)$.

###### Proof.

Fix a time $t$. Since $x_{t+1}\sim\mathcal{N}(0,\sum_{s=0}^{t-1}a_{*}^{2s})$,
we have $\text{Var}[x_{t+1}]=O\left(\frac{1}{1-a_{*}}\right)$, and so from
Gaussian concentration:
$\operatorname{\mathbb{P}}\left[x_{t+1}\geq\kappa/\sqrt{1-a_{*}}\
\right]\leq\exp(-\Omega(\kappa^{2}))$. By choosing large enough
$\kappa=\Theta(\sqrt{\log{(1/\beta)}})$, we get that
$\operatorname{\mathbb{P}}\left[x_{t+1}\geq\kappa/\sqrt{1-a_{*}}\
\right]\leq\beta/4$. Thus,

$\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\mathds{1}\\{x_{t+1}\geq\kappa/(1-a_{*})\\}\right]\leq\beta
T/4.$ (15)

Now, suppose that $\lambda<\kappa/\sqrt{1-a_{*}}$. Then,
$\mathbb{E}[|\mathcal{O}|]=\mathbb{E}\left[\sum_{t=1}^{T}\mathds{1}\\{x_{t+1}\geq\lambda\\}\right]\leq\beta
T/4$, and so from Markov’s inequality,
$\operatorname{\mathbb{P}}\left[|\mathcal{O}|\geq\beta T/2\right]\leq 1/2$,
which contradicts Assumption 2. Thus, $\lambda<\kappa/\sqrt{1-a_{*}}$, and
since $\kappa=\Theta(\sqrt{\log{(1/\beta)}})$, and $\beta=\Omega(1)$, we are
done. ∎

The claim implies that $\lambda\leq O\left(\frac{1}{1-a_{*}}\right)$. Let $C$
denote the constant on this bound, i.e., $\lambda\leq\frac{C}{1-a_{*}}$. We
consider two cases. First, if $x_{t}\leq\frac{C}{1-a_{*}}$, then
$a_{*}x_{t}+C\geq x_{t}$, i.e, if $x_{t}\in\mathcal{S}$, then
$x_{t+1}\in\mathcal{S}$ with probability $\exp(-O(C^{2}))=\Omega(1)$. If
$x_{t}>\frac{C}{1-a_{*}}$, then
$a_{*}x_{t}+C\geq\frac{C}{1-a_{*}}\geq\lambda$. Again, since $C=O(1)$, we are
done.

##  Appendix C Proof of Proposition 3.1

We will need some definitions. We define the probabilities
$\alpha_{t}^{*}\coloneqq\mathcal{N}(A_{*}x_{t},I;\mathcal{S}_{t+1})$, and the
events $\mathcal{E}_{t}^{\alpha}\coloneqq\\{\alpha_{t}^{*}\geq\alpha\\}$, and
$\mathcal{O}_{t}\coloneqq\\{x_{t}\in\mathcal{S}_{t}\\}$. Also, consider the
process

$\displaystyle
B_{t}\coloneqq\Big{(}\mathds{1}\\{\mathcal{O}_{t+1}\\}-\alpha\Big{)}\cdot\mathds{1}\\{\mathcal{O}_{t}\land\mathcal{E}_{t}^{\alpha}\\},$

and the filtration
$G_{t}\coloneqq\sigma(w_{0},w_{1},\dots,w_{t},\mathcal{S}_{1},\mathcal{S}_{2},\dots,\mathcal{S}_{t+2})$.
Then,

$\displaystyle\mathbb{E}[B_{t}\ |\ G_{t-1}]$
$\displaystyle=\mathbb{E}\bigg{[}\Big{(}\mathds{1}\\{\mathcal{O}_{t+1}\\}-\alpha\Big{)}\cdot\mathds{1}\\{\mathcal{O}_{t}\land\mathcal{E}_{t}^{\alpha}\\}\
\bigg{|}\ G_{t-1}\bigg{]}$
$\displaystyle=\operatorname{\mathbb{P}}\Big{[}\mathcal{O}_{t+1}\ \Big{|}\
G_{t-1},\mathcal{O}_{t}\land\mathcal{E}_{t}^{\alpha}\Big{]}-\alpha\geq 0,$
(16)

where in the last step we use that given $G_{t-1}$ and
$\mathcal{O}_{t}\land\mathcal{E}_{t}^{\alpha}$, we have
$x_{t+1}\sim\mathcal{N}(A_{*}x_{t},I)$, and $\alpha_{t}^{*}\geq\alpha$. Now,
let $M_{t}\coloneqq B_{t}-\mathbb{E}[B_{t}|G_{t-1}]$, and observe that $M_{t}$
is $G_{t}$-measurable, and that $\mathbb{E}[M_{t}\ |\ G_{t-1}]=0$. Since
$-1\leq B_{t}\leq 1$, we have $-2\leq M_{t}\leq 2$. Thus, from Azuma-Hoeffding
inequality,

$\displaystyle\operatorname{\mathbb{P}}\left[\sum_{t=1}^{T}M_{t}\leq-\frac{\alpha\beta
T}{4}\right]\leq\exp{\left(-\frac{\alpha^{2}\beta^{2}}{128}T\right)}=o(1).$
(17)

Moreover,

$\displaystyle\sum_{t=1}^{T}M_{t}$
$\displaystyle=\sum_{t=1}^{T}\Big{(}B_{t}-\mathbb{E}[B_{t}|G_{t-1}]\Big{)}\leq^{(\ref{eq:prop-b1})}\
\sum_{t=1}^{T}B_{t}$
$\displaystyle=\sum_{t=1}^{T}\mathds{1}\\{\mathcal{O}_{t+1}\land\mathcal{O}_{t}\land\mathcal{E}_{t}^{\alpha}\\}-\alpha\sum_{t=1}^{T}\mathds{1}\\{\mathcal{O}_{t}\land\mathcal{E}_{t}^{\alpha}\\}$
$\displaystyle\leq|\mathcal{P}|-\alpha\sum_{t=1}^{T}\mathds{1}\\{\mathcal{O}_{t}\land\mathcal{E}_{t}^{\alpha}\\}.$
(18)

From Assumptions 2 and 3, we have

$\displaystyle\operatorname{\mathbb{P}}\left[\sum_{t=1}^{T}\mathds{1}\\{\mathcal{O}_{t}\land\mathcal{E}_{t}^{\alpha}\\}<\beta
T-L\right]\leavevmode\nobreak\ \leq\leavevmode\nobreak\ o(1).$ (19)

Finally, using the assumed lower bound on $T$, we get $\beta
T-L\geq\frac{3\beta}{4}T$. The proposition follows after combining this with
17,C and 19. $\blacksquare$

##  Appendix D Detailed Proof of Theorem 2

###  D.1 The Generic bound

We will show the following lemma

######  Lemma D.1.

Independently of how $g_{i}$’s are chosen,

$\displaystyle\left\|\widehat{A}-A_{*}\right\|_{\Sigma}^{2}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ 1-\underbrace{\sum_{i=1}^{N}\left(2\eta\langle
g_{i},A_{i}\widetilde{A}_{i+1}-A_{*}\rangle-\left\|(A_{i}-A_{*})x_{t_{i}}\right\|^{2}\right)}_{E_{1}}+\eta^{2}\underbrace{\sum_{i=1}^{N}\mathrm{tr}\left(g_{i}\Sigma_{i}^{-1}g_{i}^{\top}\right)}_{E_{2}}.$
(20)

###### Proof.

For all $i$,

$\displaystyle\widetilde{A}_{i+1}-A_{*}=A_{i}-A_{*}-\eta
g_{i}\Sigma_{i}^{-1}.$ (21)

Multiplying with $\Sigma_{i}$,

$\displaystyle(\widetilde{A}_{i+1}-A_{*})\Sigma_{i}=(A_{i}-A_{*})\Sigma_{i}-\eta
g_{i}.$ (22)

Multiplying 22 with the transpose of 21,

$\displaystyle(\widetilde{A}_{i+1}-A_{*})\Sigma_{i}(\widetilde{A}_{i+1}-A_{*})^{\top}$
$\displaystyle=\left((A_{i}-A_{*})\Sigma_{i}-\eta
g_{i}\right)\left(A_{i}-A_{*}-\eta g_{i}\Sigma_{i}^{-1}\right)^{\top}$

Expanding and taking trace,

$\displaystyle\|\widetilde{A}_{i+1}-A_{*}\|_{\Sigma_{i}}^{2}=\|A_{i}-A_{*}\|_{\Sigma_{i}}^{2}-2\eta\langle
g_{i},A_{i}-A_{*}\rangle+\eta^{2}\
\mathrm{tr}\left(g_{i}\Sigma_{i}^{-1}g_{i}^{\top}\right)$

Since $\mathcal{K}$ is $(R,\omega)$-accurate, $A_{*}\in\mathcal{K}$, and by
convexity of $\mathcal{K}$,
$\|A_{i+1}-A_{*}\|_{\Sigma_{i}}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\|\widetilde{A}_{i+1}-A_{*}\|_{\Sigma_{i}}$ (see Hazan (2019) Theorem 2.1).
Thus,

$\displaystyle\|A_{i+1}-A_{*}\|_{\Sigma_{i}}^{2}\leq\|A_{i}-A_{*}\|_{\Sigma_{i}}^{2}-2\eta\langle
g_{i},A_{i}-A_{*}\rangle+\eta^{2}\
\mathrm{tr}\left(g_{i}\Sigma_{i}^{-1}g_{i}^{T}\right)$

Summing over all $i$,

$\displaystyle
0\leq\sum_{i=1}^{N}\left(\|A_{i}-A_{*}\|_{\Sigma_{i}}^{2}-\|A_{i+1}-A_{*}\|_{\Sigma_{i}}^{2}\right)-2\eta\sum_{i=1}^{N}\langle
g_{i},A_{i}-A_{*}\rangle+\eta^{2}\sum_{i=1}^{N}\mathrm{tr}\left(g_{i}\Sigma_{i}^{-1}g_{i}^{\top}\right)$
(23)

We now focus on the first sum.

$\displaystyle\sum_{i=1}^{N}\left(\|A_{i}-A_{*}\|_{\Sigma_{i}}^{2}-\|A_{i+1}-A_{*}\|_{\Sigma_{i}}^{2}\right)=\|A_{1}-A_{*}\|_{\Sigma_{1}}^{2}+\sum_{i=2}^{N}\Big{(}\|A_{i}-A_{*}\|_{\Sigma_{i}}^{2}$
$\displaystyle-\|A_{i}-A_{*}\|_{\Sigma_{i-1}}^{2}\Big{)}$
$\displaystyle-\|A_{N+1}-A_{*}\|_{\Sigma_{N}}^{2}.$ (24)

Also, since $\Sigma_{i}=\Sigma_{i-1}+x_{t_{i}}x_{t_{i}}^{T}$,

$\displaystyle\|A_{i}-A_{*}\|_{\Sigma_{i}}^{2}-\|A_{i}-A_{*}\|_{\Sigma_{i-1}}^{2}$
$\displaystyle=\mathrm{tr}\left((A_{i}-A_{*})^{\top}(A_{i}-A_{*})\Sigma_{i}\right)-\mathrm{tr}\left((A_{i}-A_{*})^{\top}(A_{i}-A_{*})\Sigma_{i-1}\right)$
$\displaystyle=\mathrm{tr}\left((A_{i}-A_{*})^{\top}(A_{i}-A_{*})x_{t_{i}}x_{t_{i}}^{\top})\right)=\|(A_{i}-A_{*})x_{t_{i}}\|^{2}.$
(25)

Thus,

$\displaystyle\sum_{i=1}^{N}\big{(}\|A_{i}-A_{*}\|_{\Sigma_{i}}^{2}-\|A_{i+1}-A_{*}$
$\displaystyle\|_{\Sigma_{i}}^{2}\big{)}=\|A_{1}-A_{*}\|_{\Sigma_{1}}^{2}-\|A_{N+1}-A_{*}\|_{\Sigma_{N}}^{2}+\sum_{i=2}^{N}\|(A_{i}-A_{*})x_{t_{i}}\|^{2}$
$\displaystyle=^{(\ref{eq:regret-b5})}\|A_{1}-A_{*}\|_{\Sigma_{0}}^{2}-\|A_{N+1}-A_{*}\|_{\Sigma_{N}}^{2}+\sum_{i=1}^{N}\|(A_{i}-A_{*})x_{t_{i}}\|^{2}.$
(26)

Combining 23 with D.1,

$\displaystyle\|A_{N+1}-A_{*}\|_{\Sigma_{N}}^{2}\leq\|A_{1}-A_{*}\|_{\Sigma_{0}}^{2}-\sum_{i=1}^{N}\left(2\eta\langle
g_{i},A_{i}-A_{*}\rangle-\|(A_{i}-A_{*})x_{t_{i}}\|^{2}\right)+\eta^{2}\sum_{i=1}^{N}\mathrm{tr}\left(g_{i}\Sigma_{i}^{-1}g_{i}^{\top}\right).$

Observe that
$\|A_{1}-A_{*}\|_{\Sigma_{0}}^{2}=\|A_{0}-A_{*}\|_{\Sigma_{0}}^{2}\leq 1$,
since $A_{1}=A_{0}$ and $A_{*}\in\mathcal{K}$. The facts that
$\widehat{A}=A_{N+1}$ and $\Sigma=\Sigma_{N}$ finish the proof. ∎

###  D.2 Decomposition of $E_{1}$

We start with some definitions. Fix a $t$, and let

$\displaystyle\mathcal{T}_{t}\coloneqq\Big{\\{}o_{t}=1\ \text{and at step $t$,
Test returns True}\Big{\\}}.$

Also, let $O_{t}=\\{o_{t}=1\\}$. We now define some ?good? events. Let
$G_{t}\coloneqq\\{t\notin B\\}$,

$\displaystyle C_{t}\coloneqq\left\\{O_{t}\rightarrow\left\\{\text{ at
iteration $i(t)$, either Test returns True and $a_{t}\geq\gamma$, or Test
returns False and $a_{t}\leq 4\gamma$}\right\\}\right\\},$ $\displaystyle
K_{t}\coloneqq\left\\{\|\Sigma_{0}^{-1/2}x_{t}\|\leq R\sqrt{\log T}\right\\}$

$G_{t}\coloneqq\big{\\{}\mathcal{N}(A_{*}x_{t},I;S_{t})\geq\alpha\big{\\}}$,
and observe that $|B(\alpha)|=\sum_{t=1}^{T}\mathds{1}\\{\neg G_{t}\land
o_{t}=1\\}$. The next event is about the ?correctness? of the Test. Let

$\displaystyle C_{t}\coloneqq\Big{\\{}o_{t}=1\ \text{and at that step, either
Test returns True and $\gamma_{t}\geq\gamma$, or Test returns False and
$\gamma_{t}\leq 4\gamma$}\Big{\\}},$

where $a_{t}$ is defined in Section 4.3. We aggregate via
$\mathcal{E}_{t}\coloneqq G_{t}\land C_{t}\land K_{t}\land O_{t}$. Now, given
$o_{t}=1$, let $V_{t}\coloneqq 2\eta\langle
g(t),A(t)-A_{*}\rangle-\left\|(A(t)-A_{*})x_{t}\right\|^{2}$, where $A(t)$ and
$g(t)$ are defined in the main text. We decompose $E_{1}$ as

$\displaystyle
E_{1}=\sum_{t=1}^{T}V_{t}\mathds{1}\\{\mathcal{T}_{t}\land\mathcal{E}_{t}\\}+\sum_{t=1}^{T}V_{t}\mathds{1}\\{\neg\mathcal{T}_{t}\land\mathcal{E}_{t}\\}+\sum_{t=1}^{T}V_{t}\mathds{1}\\{\neg\mathcal{E}_{t}\land
O_{t}\\}.$

Let $Q_{1},Q_{2},Q_{3}$ be the above three sums, respectively.

###  D.3 Large Survival Probability

In this step, we prove that $\mathbb{E}[V_{t}\ |\
\mathcal{T}_{t}\land\mathcal{E}_{t}]\geq 0$, which implies
$\mathbb{E}[Q_{1}]\geq 0$. First of all, we condition on $\mathcal{F}_{t}$ and
$\mathcal{T}_{t}\land\mathcal{E}_{t}$. Then, letting $\mu_{t}\coloneqq
A(t)x_{t}$ and $\mu_{t}^{*}\coloneqq A_{*}x_{t}$, we get
$g(t)=(z_{t}-y_{t})x_{t}^{\top}$, where
$y_{t}\sim\mathcal{N}(\mu_{t}^{*},I,S_{t})$ and
$z_{t}\sim\mathcal{N}(\mu_{t},I,S_{t})$. So,

$\displaystyle\mathbb{E}\Big{[}V_{t}\ \Big{|}\ \mathcal{F}_{t},\
\mathcal{T}_{t}\land\mathcal{E}_{t}\Big{]}=2\eta\langle\nu_{t}-\nu_{t}^{*},\mu_{t}-\mu^{*}_{t}\rangle-\|\mu_{t}-\mu_{t}^{*}\|^{2},$

where $\nu_{t}=\mathbb{E}_{z\sim\mathcal{N}(\mu_{t},I,S_{t})}[z]$ and
$\nu_{t}^{*}=\mathbb{E}_{y\sim\mathcal{N}(\mu_{t}^{*},I,S_{t})}[y]$. Also,
note that on $\mathcal{T}_{t}\land\mathcal{E}_{t}$,

$\displaystyle\mathcal{N}(\mu_{t},I;S_{t}),\
\mathcal{N}(\mu_{t}^{*},I;S_{t})\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\gamma$

Now, using Lemma 5.2 of the main text (proven in detail there), we see that
for large enough constant $c_{\eta}$202020Remember that
$\eta=(2/\alpha)^{c_{\eta}}$., we get $\mathbb{E}[V_{t}\ |\ \mathcal{F}_{t},\
\mathcal{T}_{t}\land\mathcal{E}_{t}]\leavevmode\nobreak\
\geq\leavevmode\nobreak\ 0$. Indeed, note that
$\nabla\mkern-2.5mu_{\mu}L_{S}(\mu;\mu^{*})=\nu-\nu^{*},$ where
$\nu=\mathbb{E}_{z\sim\mathcal{N}(\mu,I,S)}[z]$ and
$\nu^{*}=\mathbb{E}_{y\sim\mathcal{N}(\mu^{*},I,S)}[z]$. Thus,

$\displaystyle\mathbb{E}\Big{[}V_{t}\ \Big{|}\ \mathcal{F}_{t},\
\mathcal{T}_{t}\land\mathcal{E}_{t}\Big{]}\geq(2\eta(\gamma/2)^{c}-1)\cdot\|\mu_{t}-\mu_{t}^{*}\|^{2}$
$\displaystyle=\left(2\left(2/\alpha\right)^{c_{\eta}}(\alpha/4)^{c\cdot
c_{\gamma}}-1\right)\cdot\|\mu_{t}-\mu_{t}^{*}\|^{2}$
$\displaystyle=\left(\frac{2^{c_{\eta}+1-2c\cdot
c_{\gamma}}}{a^{c_{\eta}-c\cdot
c_{\gamma}}}-1\right)\cdot\|\mu_{t}-\mu_{t}^{*}\|^{2}\geq 0,$

for any constant $c_{\eta}\geq 2c\cdot c_{\gamma}$.

###  D.4 Small Survival Probability

Here, we prove that $\mathbb{E}[V_{t}\ |\
\neg\mathcal{T}_{t}\land\mathcal{E}_{t}]\geq 0$, which implies
$\mathbb{E}[Q_{2}]\geq 0$. Given $\mathcal{F}_{t}$ and
$\neg\mathcal{T}_{t}\land\mathcal{E}_{t}$, we have
$g(t)=(\mu_{t}-y_{t})x_{t}^{T}$, where
$y_{t}\sim\mathcal{N}(\mu_{t}^{*},I,S_{t})$. Thus,

$\displaystyle\mathbb{E}\Big{[}V_{t}\ \Big{|}\ \mathcal{F}_{t},\
\neg\mathcal{T}_{t}\land\mathcal{E}_{t}\Big{]}=2\eta\langle\mu_{t}-\nu_{t}^{*},\mu_{t}-\mu^{*}_{t}\rangle-\|\mu_{t}-\mu_{t}^{*}\|^{2}.$
(27)

Now, since $\mathcal{E}_{t}$ implies $C_{t}$, we have that given
$\neg\mathcal{T}_{t}\land\mathcal{E}_{t}$, the probability
$\mathcal{N}(\mu_{t},I;S_{t})\leq 4\gamma$. Moreover, $\mathcal{E}_{t}$
implies $G_{t}$, i.e., $\mathcal{N}(\mu_{t}^{*},I;S_{t})\geq\alpha$, which
from Claim 5.3 implies $\|\nu_{t}^{*}-\mu_{t}^{*}\|\leavevmode\nobreak\
\leq\leavevmode\nobreak\ s(\alpha)$. We claim that
$\|\mu_{t}-\mu_{t}^{*}\|>2s(\alpha)$, provided that $c_{\gamma}=O(1)$ is
sufficiently large. Indeed, suppose $\|\mu_{t}-\mu_{t}^{*}\|\leq 2s(\alpha)$.
Combining with $\mathcal{N}(\mu_{t}^{*},I;S_{t})\geq\alpha$ and Claim 5.5, we
get

$\displaystyle
4(\alpha/2)^{c_{\gamma}}=4\gamma\geq\mathcal{N}(\mu_{t},I,S_{t})\leavevmode\nobreak\
\geq\leavevmode\nobreak\ (\alpha/2)^{O(1)},$

which is a contradiction for large enough $c_{\gamma}=O(1)$. Using that
$\|\nu_{t}^{*}-\mu_{t}^{*}\|\leq s(\alpha)$,

$\displaystyle\langle\mu_{t}-\nu_{t}^{*},\mu_{t}-\mu^{*}_{t}\rangle$
$\displaystyle=\|\mu_{t}-\mu^{*}_{t}\|^{2}+\langle\mu_{t}^{*}-\nu_{t}^{*},\mu_{t}-\mu^{*}_{t}\rangle\geq\|\mu_{t}-\mu^{*}_{t}\|^{2}-\|\mu_{t}^{*}-\nu_{t}^{*}\|\cdot\|\mu_{t}-\mu^{*}_{t}\|$
$\displaystyle\geq\|\mu_{t}-\mu^{*}_{t}\|\cdot\big{(}\|\mu_{t}-\mu^{*}_{t}\|-s(\alpha)\big{)}\geq\frac{\|\mu_{t}-\mu_{t}^{*}\|^{2}}{2}.$

Since $\eta\geq 1$, equation 27 implies $\mathbb{E}[V_{t}\ |\
\mathcal{F}_{t},\neg\mathcal{T}\land\mathcal{E}_{t}]\geq 0$.

### Handling Bad Events and Gradient Variance

For $Q_{3}$, we show that

$\displaystyle\mathbb{E}\big{[}|Q_{3}|\big{]}\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\smash{\widetilde{O}}(1)\cdot\mathrm{poly}(1/\alpha)\cdot\left(d+R^{2}+R_{w}^{2}\right)\cdot(L+1).$

This is proven using that bad events have small probabilities, relative to
$V_{t}$’s. This is a purely technical proof, and we provide it in Appendix E.

The last step is to bound
$E_{2}=\sum_{i=1}^{N}\mathrm{tr}\left(g_{i}\Sigma_{i}^{-1}g_{i}^{T}\right).$
This is often called ?the gradient variance? in optimization. We show that

$\displaystyle\mathbb{E}\big{[}E_{2}\big{]}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \smash{\widetilde{O}}(1)\cdot d(d+R^{2}+R_{w}^{2}).$

The proof uses the volume-based potential-function argument used in Hazan et
al. (2007), which also appears in linear bandit theory (Lattimore and
Szepesvári (2020)). We provide the proof in Appendix F. Overall,

$\displaystyle\mathbb{E}\left[\left\|\widehat{A}-A_{*}\right\|_{\Sigma}^{2}\right]$
$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\
1-\mathbb{E}[Q_{1}]-\mathbb{E}[Q_{2}]-\mathbb{E}[Q_{3}]+\eta^{2}\mathbb{E}[E_{2}]$
$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\smash{\widetilde{O}}(1)\cdot\mathrm{poly}(1/\alpha)\cdot\left(d+R^{2}+R_{w}^{2}\right)\cdot(L+1)+\smash{\widetilde{O}}(1)\cdot\mathrm{poly}(1/\alpha)\cdot
d(d+R^{2}+R_{w}^{2})$ $\displaystyle\leavevmode\nobreak\
\leq\leavevmode\nobreak\ D+LD^{\prime},$

where $D=dD^{\prime}$, and
$D^{\prime}=\smash{\widetilde{O}}(1)\cdot\mathrm{poly}(1/\alpha)\cdot(d+R^{2}+R_{w}^{2})$.

##  Appendix E Bound on $\mathbb{E}[|Q_{3}|]$

######  Lemma E.1.

$\mathbb{E}[|Q_{3}|]\leq\smash{\widetilde{O}}(1)\cdot\mathrm{poly}(1/\alpha)\cdot(d+R^{2}+R_{w}^{2})\cdot(L+1)$.

We now prove the above lemma. We start with some definitions (and reminders).
If at time $t$ we have $o_{t}=1$, then we define the following:

  * •

Let $i(t)$ be the iteration $i$, which corresponds to time $t$.

  * •

Let $A(t)\coloneqq A_{i(t)}$, and $\mu_{t}\coloneqq A(t)x_{t}$. Also, let
$\mu_{t}^{*}\coloneqq A_{*}x_{t}$.

  * •

Let $\gamma_{t}\coloneqq\mathcal{N}(\mu_{t},I;S_{t})$.

  * •

Let $z_{t}$ be the $z$ at the end of SwitchGrad function, when called at
iteration $i(t)$.

  * •

If additionally, Test at iteration $i(t)$ returns True ($\mathcal{T}_{t}$),
then let $z_{t}^{\prime}$ be the $z^{\prime}$ of the SwitchGrad function, at
iteration $i(t)$. Observe that on $\mathcal{T}_{t}$, $z_{t}=z_{t}^{\prime}$.

Now, observe that given $o_{t}=1$,

$\displaystyle V_{t}=2\eta\langle
z_{t}-y_{t},\mu_{t}-\mu_{t}^{*}\rangle-\|\mu_{t}-\mu_{t}^{*}\|^{2}.$

All the above quantities are defined on $O_{t}=\\{o_{t}=1\\}$ (except for
$z_{t}^{\prime}$ which is defined on $\mathcal{T}_{t}\subseteq O_{t}$). We
extend all these, by defining them to be zero outside of $O_{t}$
($\mathcal{T}_{t}$ for $z_{t}^{\prime}$). Furthermore, remember that
$\mathcal{E}_{t}=G_{t}\land C_{t}\land K_{t}\land O_{t}$, where the events
(along with $\mathcal{T}_{t}$) are defined in D.2. Moreover, in Appendix H
(Claim H.4), we show that $\operatorname{\mathbb{P}}[\neg C_{t}]\leq 1/T^{2}$.
About $K_{t}$, since $\mathcal{K}$ is $(R,\omega)$-accurate,
$\operatorname{\mathbb{P}}[\neg K_{t}]\leq O(1/T)$. We first decompose
$|Q_{3}|$.

######  Claim E.2.

$|Q_{3}|\leq\eta Q_{4}+\eta Q_{5}$, where

$\displaystyle
Q_{4}=\sum_{t=1}^{T}(8\|\mu_{t}-\mu_{t}^{*}\|^{2}+2\|w_{t}\|^{2})\mathds{1}\\{\neg\mathcal{E}_{t}\land
O_{t}\\},\ \ \ \ \text{and}\ \ \ \
Q_{5}=\sum_{t=1}^{T}\|z_{t}^{\prime}-\mu_{t}\|^{2}\mathds{1}\\{\neg\mathcal{E}_{t}\land\mathcal{T}_{t}\\}.$
(28)

###### Proof.

Let $w_{t}\coloneqq y_{t}-\mu_{t}^{*}$ (the noise). We have
$|Q_{3}|\leq\sum_{t=1}^{T}|V_{t}|\mathds{1}\\{\neg\mathcal{E}_{t}\land
O_{t}\\}$, and

$\displaystyle|V_{t}|$ $\displaystyle\leq 2\eta\left|\langle
z_{t}^{\prime}-y_{t},\mu_{t}-\mu_{t}^{*}\rangle\right|\cdot\mathds{1}\\{\mathcal{T}_{t}\\}+2\eta\left|\langle\mu_{t}-y_{t},\mu_{t}-\mu_{t}^{*}\rangle\right|+\|\mu_{t}-\mu_{t}^{*}\|^{2}$
$\displaystyle\leq
2\eta\|z_{t}^{\prime}-y_{t}\|\cdot\|\mu_{t}-\mu_{t}^{*}\|\cdot\mathds{1}\\{\mathcal{T}_{t}\\}+2\eta\|\mu_{t}-y_{t}\|\cdot\|\mu_{t}-\mu_{t}^{*}\|+\eta\|\mu_{t}-\mu_{t}^{*}\|^{2}$
$\displaystyle\leq
2\eta\|z_{t}^{\prime}-\mu_{t}\|\cdot\|\mu_{t}-\mu_{t}^{*}\|\cdot\mathds{1}\\{\mathcal{T}_{t}\\}+4\eta\|\mu_{t}-y_{t}\|\cdot\|\mu_{t}-\mu_{t}^{*}\|+\eta\|\mu_{t}-\mu_{t}^{*}\|^{2}$
$\displaystyle\leq
2\eta\|z_{t}^{\prime}-\mu_{t}\|\cdot\|\mu_{t}-\mu_{t}^{*}\|\cdot\mathds{1}\\{\mathcal{T}_{t}\\}+4\eta\|\mu_{t}-\mu_{t}^{*}\|^{2}+4\eta\|w_{t}\|\cdot\|\mu_{t}-\mu_{t}^{*}\|+\eta\|\mu_{t}-\mu_{t}^{*}\|^{2}$
$\displaystyle\leq\eta\|z_{t}^{\prime}-\mu_{t}\|^{2}\cdot\mathds{1}\\{\mathcal{T}_{t}\\}+6\eta\|\mu_{t}-\mu_{t}^{*}\|^{2}+2\eta\|\mu_{t}-\mu_{t}^{*}\|^{2}+2\eta\|w_{t}\|^{2}$
$\displaystyle=\eta\|z_{t}^{\prime}-\mu_{t}\|^{2}\cdot\mathds{1}\\{\mathcal{T}_{t}\\}+8\eta\|\mu_{t}-\mu_{t}^{*}\|^{2}+2\eta\|w_{t}\|^{2}$

where we have used that $\eta\geq 1$, and that for all $a,b\in{\mathbb{R}}$,
$2ab\leq a^{2}+b^{2}$. Since $\mathcal{T}_{t}$ implies $O_{t}$,

$\displaystyle|Q_{3}|\leq\eta\sum_{t=1}^{T}\|z_{t}^{\prime}-\mu_{t}\|^{2}\cdot\mathds{1}\\{\neg\mathcal{E}_{t}\land\mathcal{T}_{t}\\}+\eta\sum_{t=1}^{T}(8\|\mu_{t}-\mu_{t}^{*}\|^{2}+2\|w_{t}\|^{2})\cdot\mathds{1}\\{\neg\mathcal{E}_{t}\land
O_{t}\\}.$

∎

We will prove the following claims.

######  Claim E.3.

$\mathbb{E}[Q_{4}]\leq\smash{\widetilde{O}}(R^{2}+R_{w}^{2})\cdot(L+1)$.

######  Claim E.4.

$\mathbb{E}[Q_{5}]\leq\smash{\widetilde{O}}(d)\cdot(L+1)$.

Observe that these two claims complete the bound on $\mathbb{E}[|Q_{3}|]$. We
now prove the claims.

###  E.1 Proof of Claim E.3

We will bound
$\mathbb{E}[Q_{4}]=\mathbb{E}\left[\sum_{t=1}^{T}(8\|\mu_{t}-\mu_{t}^{*}\|^{2}+2\|w_{t}\|^{2})\mathds{1}\\{\neg\mathcal{E}_{t}\land
O_{t}\\}\right]$ by proving the following two claims.

######  Claim E.5.

$\sum_{t=1}^{T}\mathbb{E}\left[\|\mu_{t}-\mu_{t}^{*}\|^{2}\mathds{1}\\{\neg\mathcal{E}_{t}\land
O_{t}\\}\right]\leq\smash{\widetilde{O}}(1)\cdot R^{2}(L+1)$

######  Claim E.6.

$\sum_{t=1}^{T}\mathbb{E}\left[\|w_{t}\|^{2}\mathds{1}\\{\neg\mathcal{E}_{t}\land
O_{t}\\}\right]\leq\smash{\widetilde{O}}(1)\cdot R_{w}^{2}(L+1)$

####  E.1.1 Proofs of Claims E.5, E.6

On $O_{t}$, $A(t)=A_{i(t)}$ and so $A(t),A_{*}\in\mathcal{K}$, in other words
$\|A_{0}-A_{*}\|_{\Sigma_{0}}\leq 1$ and $\|A_{0}-A(t)\|_{\Sigma_{0}}\leq 1$.
From triangle inequality, $\|A(t)-A_{*}\|_{\Sigma_{0}}\leq 2$, and so

$\displaystyle\|\mu_{t}-\mu_{t}^{*}\|$
$\displaystyle=\|(A(t)-A_{*})x_{t}\|=\|(A(t)-A_{*})\Sigma_{0}^{1/2}\Sigma_{0}^{-1/2}x_{t}\|$
$\displaystyle\leq\|(A(t)-A_{*})\Sigma_{0}^{1/2}\|_{2}\cdot\|\Sigma_{0}^{-1/2}x_{t}\|$
$\displaystyle\leq\|(A(t)-A_{*})\Sigma_{0}^{1/2}\|_{\text{F}}\cdot\|\Sigma_{0}^{-1/2}x_{t}\|\leq
2\|x_{t}\|_{\Sigma^{-1}}.$ (29)

Thus, since $\mathcal{K}$ is $(R,\omega)$-accurate, $\|\mu_{t}-\mu_{t}^{*}\|$
is $O(R^{2})$-subgaussian, which implies

$\displaystyle\operatorname{\mathbb{P}}\left[\|\mu_{t}-\mu_{t}^{*}\|>R\sqrt{\log{(TR)}}\right]\leq\frac{1}{T^{2}R^{4}}\
\ \ \text{and}\ \ \ \mathbb{E}\left[\|\mu_{t}-\mu_{t}^{*}\|^{4}\right]\leq
O(R^{4}).$ (30)

Let $K_{t}^{\prime}$ be the event in above probability.

$\displaystyle\mathbb{E}\left[\|\mu_{t}-\mu_{t}^{*}\|^{2}\mathds{1}\\{\neg\mathcal{E}_{t}\land
O_{t}\\}\right]$
$\displaystyle=\mathbb{E}\left[\|\mu_{t}-\mu_{t}^{*}\|^{2}\mathds{1}\\{\neg\mathcal{E}_{t}\land
O_{t}\land(\neg
K_{t}^{\prime})\\}\right]+\mathbb{E}\left[\|\mu_{t}-\mu_{t}^{*}\|^{2}\mathds{1}\\{\neg\mathcal{E}_{t}\land
O_{t}\land K_{t}^{\prime}\\}\right]$
$\displaystyle\leq^{(\ref{eq:prop:R:1})}\smash{\widetilde{O}}(R^{2})\cdot\operatorname{\mathbb{P}}[\mathcal{E}_{t}\land
O_{t}]+\mathbb{E}[\|\mu_{t}-\mu_{t}^{*}\|^{2}\mathds{1}\\{K_{t}^{\prime}\\}]$
$\displaystyle\leq\smash{\widetilde{O}}(R^{2})\cdot(\operatorname{\mathbb{P}}[\neg
G_{t}]+\operatorname{\mathbb{P}}[\neg K_{t}]+\operatorname{\mathbb{P}}[\neg
C_{t}])+\sqrt{\mathbb{E}[\|\mu_{t}-\mu_{t}^{*}\|^{4}]}\cdot\sqrt{\operatorname{\mathbb{P}}[K_{t}^{\prime}]}$
$\displaystyle\leq^{(\ref{eq:prop:R:1})}\smash{\widetilde{O}}(R^{2})\cdot(\operatorname{\mathbb{P}}[\neg
G_{t}]+1/T)+O(R^{2})\cdot\frac{1}{TR^{2}}$
$\displaystyle\leq\smash{\widetilde{O}}(R^{2})\cdot(\operatorname{\mathbb{P}}[\neg
G_{t}]+1/T).$

Summing over $t$ and using that $\sum_{t=1}^{T}\operatorname{\mathbb{P}}[\neg
G_{t}]\leq L$, we finish the proof. For Claim E.6, observe that since
$\|w_{t}\|$ is $R_{w}^{2}$ subgaussian, we can just use identical steps as
above. $\blacksquare$

###  E.2 Proof of Claim E.4

Let $\mathcal{E}_{t,5}\coloneqq\neg\mathcal{E}_{t}\land\mathcal{T}_{t}$, and
so
$Q_{5}=\sum_{t=1}^{T}\|z_{t}^{\prime}-\mu_{t}\|^{2}\mathds{1}\\{\mathcal{E}_{t,5}\\}$

######  Claim E.7.

Given $\mathcal{F}_{t}$ and $\mathcal{E}_{t,5}$, we have that
$\|z_{t}^{\prime}-\mu_{t}\|_{2}$ is
$\smash{\widetilde{O}}(d)\cdot(1\lor\log{(1/\gamma_{t})})$-subgaussian.

###### Proof.

Given $\mathcal{F}_{t}$ and $\mathcal{E}_{t,5}$, we have
$z_{t}^{\prime}\sim\mathcal{N}(\mu_{t},I,S_{t})$. In Appendix H (Claim H.1) we
show that this implies $\|z_{t}^{\prime}-\mu_{t}\|_{\psi_{2}}^{2}\leq
O(1\lor\gamma_{t})$. Claim H.2 in Appendix H finishes the proof. ∎

The claim above implies (see Vershynin (2018))

$\displaystyle\mathbb{E}[\|z_{t}^{\prime}-\mu_{t}\|_{2}^{2}\ |\
\mathcal{F}_{t},\mathcal{E}_{t,5}]\leq\smash{\widetilde{O}}(d)\cdot(1\lor\log{(1/\gamma_{t})}).$
(31)

Thus,

$\displaystyle\mathbb{E}\left[\|z_{t}^{\prime}-\mu_{t}\|^{2}\mathds{1}\\{\mathcal{E}_{t,5}\\}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\|z_{t}^{\prime}-\mu_{t}\|^{2}\mathds{1}\\{\mathcal{E}_{t,5}\\}\
|\ \mathcal{F}_{t}\right]\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\|z_{t}^{\prime}-\mu_{t}\|^{2}\mathds{1}\\{\mathcal{E}_{t,5}\\}\
|\ \mathcal{F}_{t}\right]\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\|z_{t}^{\prime}-\mu_{t}\|^{2}\
|\
\mathcal{F}_{t},\mathcal{E}_{t,5}\right]\cdot\operatorname{\mathbb{P}}[\mathcal{E}_{t,5}\
|\ \mathcal{F}_{t}]\right]$
$\displaystyle\leq\smash{\widetilde{O}}(d)\cdot\mathbb{E}\left[(1\lor\log{(1/\gamma_{t})})\cdot\operatorname{\mathbb{P}}[\mathcal{E}_{t,5}\
|\ \mathcal{F}_{t}]\right]$
$\displaystyle=\smash{\widetilde{O}}(d)\cdot\mathbb{E}\left[\mathbb{E}\left[(1\lor\log{(1/\gamma_{t})})\cdot\mathds{1}\\{\mathcal{E}_{t,5}\\}\
|\ \mathcal{F}_{t}\right]\right]$
$\displaystyle=\smash{\widetilde{O}}(d)\cdot\mathbb{E}\left[(1\lor\log{(1/\gamma_{t})})\cdot\mathds{1}\\{\mathcal{E}_{t,5}\\}\right],$
(32)

where the inequality above is justified by (31). So,

$\displaystyle\mathbb{E}\left[\|z_{t}^{\prime}-\mu_{t}\|^{2}\mathds{1}\\{\mathcal{E}_{t,5}\\}\right]$
$\displaystyle\leq\smash{\widetilde{O}}(d)\cdot\Big{(}\operatorname{\mathbb{P}}\left[\mathcal{E}_{t,5}\right]+\mathbb{E}\left[\log{(1/\gamma_{t})}\cdot\mathds{1}\\{\mathcal{E}_{t,5}\\}\right]\Big{)}$
(33)

We will first bound

$\displaystyle\mathbb{E}[\log{(1/\gamma_{t})}\cdot$
$\displaystyle\mathds{1}\\{\mathcal{E}_{t,5}\\}]=\mathbb{E}\left[\log{(1/\gamma_{t})}\cdot\mathds{1}\\{C_{t}\land\mathcal{E}_{t,5}\\}\right]+\mathbb{E}\left[\log{(1/\gamma_{t})}\cdot\mathds{1}\\{\neg
C_{t}\land\mathcal{E}_{t,5}\\}\right]$
$\displaystyle=\mathbb{E}\left[\log{(1/\gamma_{t})}\cdot\mathds{1}\\{C_{t}\land\mathcal{T}_{t}\\}\cdot\mathds{1}\\{\neg(G_{t}\land
K_{t})\\}\right]+\mathbb{E}\left[\log{(1/\gamma_{t})}\cdot\mathds{1}\\{\neg
C_{t}\land\mathcal{T}_{t}\\}\right],$ (34)

where we used the definition of $\mathcal{E}_{t,5}$. Now, observe that on
$C_{t}\land\mathcal{T}_{t}$, we have $\gamma_{t}\geq\gamma$. Thus,

$\displaystyle\mathbb{E}\left[\log{(1/\gamma_{t})}\cdot\mathds{1}\\{C_{t}\land\mathcal{T}_{t}\\}\cdot\mathds{1}\\{\neg(G_{t}\land
K_{t})\\}\right]$
$\displaystyle\leq\log{(1/\gamma)}\cdot\operatorname{\mathbb{P}}[\neg(G_{t}\land
K_{t})]$
$\displaystyle\leq\log{(1/\gamma)}\cdot(\operatorname{\mathbb{P}}[\neg
G_{t}]+\operatorname{\mathbb{P}}[\neg K_{t}]).$ (35)

We now bound $\mathbb{E}\left[\log{(1/\gamma_{t})}\cdot\mathds{1}\\{\neg
C_{t}\land\mathcal{T}_{t}\\}\right]$ via the following claim.

######  Claim E.8.

Fix $r=O(1)$. Then,
$\mathbb{E}\left[\left(\log{\frac{1}{\gamma_{t}}}\right)^{r}\cdot\mathds{1}\\{\neg
C_{t}\land\mathcal{T}_{t}\\}\right]\leq\smash{\widetilde{O}}\left(1\right)\cdot\frac{\gamma^{-1}}{T^{2}}$.

We state the claim for general $r$, because later we will need it for $r=2$.
Observe that for $r=1$, we get
$\mathbb{E}\left[\log{(1/\gamma_{t})}\cdot\mathds{1}\\{\neg
C_{t}\land\mathcal{T}_{t}\\}\right]\leq\smash{\widetilde{O}}\left(1\right)\cdot\frac{\gamma^{-1}}{T^{2}}$.
We prove the claim at the end of the subsection. Combining with (E.2) and
(E.2), we get

$\displaystyle\mathbb{E}[\log{(1/\gamma_{t})}\cdot\mathds{1}\\{\mathcal{E}_{t,5}\\}]\leq\log{(1/\gamma)}\cdot(\operatorname{\mathbb{P}}[\neg
G_{t}]+\operatorname{\mathbb{P}}[\neg
K_{t}])+\smash{\widetilde{O}}\left(1\right)\cdot\frac{\gamma^{-1}}{T^{2}},$

so from (33),

$\displaystyle\mathbb{E}\left[\|z_{t}^{\prime}-\mu_{t}\|^{2}\mathds{1}\\{\mathcal{E}_{t,5}\\}\right]$
$\displaystyle\leq\smash{\widetilde{O}}(d)\cdot\left(\operatorname{\mathbb{P}}[\mathcal{E}_{t,5}]+\operatorname{\mathbb{P}}[\neg
G_{t}]+\operatorname{\mathbb{P}}[\neg K_{t}]+\frac{\gamma^{-1}}{T^{2}}\right)$
$\displaystyle\leq\smash{\widetilde{O}}(d)\cdot\left(\operatorname{\mathbb{P}}[\mathcal{E}_{t,5}]+\operatorname{\mathbb{P}}[\neg
G_{t}]+\operatorname{\mathbb{P}}[\neg K_{t}]+\frac{\gamma^{-1}}{T^{2}}\right)$

Observe that
$\operatorname{\mathbb{P}}[\mathcal{E}_{t,5}]\leq\operatorname{\mathbb{P}}[\neg
C_{t}]+\operatorname{\mathbb{P}}[\neg K_{t}]+\operatorname{\mathbb{P}}[\neg
G_{t}]$. Also, $\sum_{t=1}^{T}Pr[\neg G_{t}]=\mathbb{E}[|B(\alpha)|]\leq L$,
and $\operatorname{\mathbb{P}}[\neg K_{t}]\leq O(1/T)$ (since $\mathcal{K}$ is
$(R,\omega)$-accurate), and $\operatorname{\mathbb{P}}[\neg C_{t}]\leq
1/T^{2}$ (Appendix H, Claim H.4). Thus, from (E.2),

$\displaystyle\mathbb{E}[Q_{5}]\leq\smash{\widetilde{O}}(d)\cdot\sum_{t=1}^{T}\left(\operatorname{\mathbb{P}}[\neg
G_{t}]+1/T+\frac{\gamma^{-1}}{T^{2}}\right)\leq\smash{\widetilde{O}}(d)\cdot(L+1),$

using that $T\geq\mathrm{poly}(1/\alpha)$ and
$1/\gamma=\mathrm{poly}(1/\alpha)$.

We now give the proof of Claim E.8.

###### Proof.

Let $P_{t}=\\{\gamma_{t}\geq 1/T^{2}\\}$. Then,

$\displaystyle\mathbb{E}\Big{[}\left(\log{\frac{1}{\gamma_{t}}}\right)^{r}\cdot\mathds{1}\\{\neg
C_{t}\land\mathcal{T}_{t}\\}\Big{]}=\mathbb{E}\Big{[}\left(\log{\frac{1}{\gamma_{t}}}\right)^{r}\cdot$
$\displaystyle\mathds{1}\\{\neg C_{t}\land\mathcal{T}_{t}\land
P_{t}\\}\Big{]}$
$\displaystyle+\mathbb{E}\left[\left(\log{\frac{1}{\gamma_{t}}}\right)^{r}\cdot\mathds{1}\left\\{\neg
C_{t}\land\mathcal{T}_{t}\land(\neg P_{t})\right\\}\right].$ (36)

Since $\mathcal{T}_{t}\land(\neg P_{t})$ implies $\neg C_{t}$, we have

$\displaystyle\mathbb{E}\left[\left(\log{\frac{1}{\gamma_{t}}}\right)^{r}\cdot\mathds{1}\\{\neg
C_{t}\land\mathcal{T}_{t}\land(\neg P_{t})\\}\right]$
$\displaystyle=\mathbb{E}\left[\left(\log{\frac{1}{\gamma_{t}}}\right)^{r}\cdot\mathds{1}\\{\mathcal{T}_{t}\land(\neg
P_{t})\\}\right]$
$\displaystyle\leq\mathbb{E}\left[\left(\log{\frac{1}{\gamma_{t}}}\right)^{r}\cdot\mathds{1}\\{\mathcal{T}_{t}\\}\
\bigg{|}\ \neg P_{t}\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\left(\log{\frac{1}{\gamma_{t}}}\right)^{r}\cdot\mathds{1}\\{\mathcal{T}_{t}\\}\
\bigg{|}\ \gamma_{t},\neg P_{t}\right]\ \bigg{|}\ \neg P_{t}\right]$
$\displaystyle=\mathbb{E}\left[\left(\log{\frac{1}{\gamma_{t}}}\right)^{r}\cdot\operatorname{\mathbb{P}}\left[\mathcal{T}_{t}\
\big{|}\ \gamma_{t},\neg P_{t}\right]\ \bigg{|}\ \neg P_{t}\right].$

Combining with (E.2), we get

$\displaystyle\mathbb{E}\Big{[}\left(\log{\frac{1}{\gamma_{t}}}\right)^{r}\cdot\mathds{1}\left\\{\neg
C_{t}\land\mathcal{T}_{t}\right\\}\Big{]}\leq$
$\displaystyle\left(\log{T^{2}}\right)^{r}\cdot\mathbb{E}\Big{[}\mathds{1}\\{\neg
C_{t}\land\mathcal{T}_{t}\\}\Big{]}$
$\displaystyle+\mathbb{E}\left[\left(\log{\frac{1}{\gamma_{t}}}\right)^{r}\cdot\operatorname{\mathbb{P}}\left[\mathcal{T}_{t}\
\big{|}\ \gamma_{t},\neg P_{t}\right]\ \bigg{|}\ \neg P_{t}\right].$

From Appendix H (Claim H.4), we get $\mathbb{E}\left[\mathds{1}\\{\neg
C_{t}\land\mathcal{T}_{t}\\}\right]\leq\mathbb{E}\left[\mathds{1}\\{\neg
C_{t}\land O_{t}\\}\right]\leq 1/T^{2}$. Also, given $\gamma_{t}$, the
probability of $\mathcal{T}_{t}$ is at most $1-(1-\gamma_{t})^{k}$ (if no
$\xi_{j}$ hits $S_{t}$, then the Test definitely returns False), where $k$ is
defined in Algorithm 3. From Bernoulli’s inequality,
$1-(1-\gamma_{t})^{k}\leq\gamma_{t}k$, and so

$\displaystyle\mathbb{E}\left[\left(\log{\frac{1}{\gamma_{t}}}\right)^{r}\cdot\operatorname{\mathbb{P}}\left[\mathcal{T}_{t}\
\big{|}\ \gamma_{t},\neg P_{t}\right]\ \bigg{|}\ \neg P_{t}\right]$
$\displaystyle\leq
k\cdot\mathbb{E}\left[\left(\log{\frac{1}{\gamma_{t}}}\right)^{r}\cdot\gamma_{t}\
\Big{|}\ \gamma_{t}<1/T^{2}\right]$ $\displaystyle\leq
k\cdot\frac{\left(\log{\left(T^{2}\right)}\right)^{r}}{T^{2}}\leq\smash{\widetilde{O}}(1)\cdot\frac{\gamma^{-1}}{T^{2}},$

where we used that $r=O(1)$ and that $T$ is lower-bounded by a large constant.
∎

##  Appendix F Bound on Gradient Variance

######  Lemma F.1.

$\mathbb{E}[E_{2}]\leq\smash{\widetilde{O}}(1)\cdot
d\cdot(d+R^{2}+R_{w}^{2})$.

In this section, we prove Lemma F.1.

$\displaystyle E_{2}$
$\displaystyle=\sum_{i=1}^{N}\mathrm{tr}(g_{i}\Sigma_{i}^{-1}g_{i}^{T})\leq\sum_{i=1}^{N}\|z_{t_{i}}-y_{t_{i}}\|^{2}\cdot(x_{t_{i}}^{T}\Sigma_{i}^{-1}x_{t_{i}})\leq\max_{i}\left\\{\|z_{t_{i}}-y_{t_{i}}\|^{2}\right\\}\cdot\sum_{i=1}^{N}x_{t_{i}}^{T}\Sigma_{i}^{-1}x_{t_{i}}$

######  Claim F.2.

$\sum_{i=1}^{N}x_{t_{i}}^{T}\Sigma_{i}^{-1}x_{t_{i}}\leq
d\left(\log{|\Sigma_{N}|^{1/d}}+\log{(1/\omega)}\right)$, where $|\Sigma_{N}|$
denotes the determinant.

This Claim is (implicitly) proven in Hazan et al. (2007). We provide a proof
for completeness.

###### Proof.

We will use the following inequality: if $A,B$ are PSD matrices, then $\langle
A^{-1},A-B\rangle\leq\log{\frac{|A|}{|B|}}$. For a proof of this see Hazan
(2019) Lemma 4.6.

$\displaystyle\sum_{i=1}^{N}x_{t_{i}}^{\top}\Sigma_{i}^{-1}x_{t_{i}}$
$\displaystyle=\sum_{i=1}^{N}\langle\Sigma_{i}^{-1},x_{t_{i}}x_{t_{i}}^{\top}\rangle=\sum_{i=1}^{N}\langle\Sigma_{i}^{-1},\Sigma_{i}-\Sigma_{i-1}\rangle\leq\sum_{i=1}^{N}\log{\frac{|\Sigma_{i}|}{|\Sigma_{i-1}|}}=\log{\frac{|\Sigma_{N}|}{|\Sigma_{0}|}}.$

The Assumption that $\mathcal{K}$ is $(R,\omega)$-accurate, and so
$\Sigma_{0}\succcurlyeq\omega\cdot I$ completes the proof. ∎

By Cauchy-Schwarz,

$\displaystyle\mathbb{E}[E_{2}]\leq
O(d)\cdot\sqrt{\mathbb{E}\left[\max_{i}\|z_{t_{i}}-y_{t_{i}}\|^{4}\right]}\cdot\sqrt{\mathbb{E}\left[\log^{2}{|\Sigma_{N}|^{1/d}}\right]+\smash{\widetilde{O}}(1)}.$

The following claims complete the proof.

######  Claim F.3.

$\mathbb{E}\left[\log^{2}{|\Sigma_{N}|^{1/d}}\right]\leq\log^{2}\left(e+T\cdot
R_{x}^{2}\right)$.

######  Claim F.4.

$\mathbb{E}\left[\max_{i}\|z_{t_{i}}-y_{t_{i}}\|^{4}\right]\leq\smash{\widetilde{O}}(1)\cdot(d^{2}+R^{4}+R_{w}^{4})$

We now prove these two claims.

###  F.1 Proof of Claim F.4

Let $M\coloneqq\max_{i}\|z_{t_{i}}-y_{t_{i}}\|$, and also let

  1. 1.

$M_{1}\coloneqq\max_{t}\left\\{\|z_{t}^{\prime}-\mu_{t}\|\cdot\mathds{1}\\{C_{t}\land\mathcal{T}_{t}\\}\right\\}$

  2. 2.

$M_{2}\coloneqq\max_{t}\left\\{\|z_{t}^{\prime}-\mu_{t}\|\cdot\mathds{1}\\{\neg
C_{t}\land\mathcal{T}_{t}\\}\right\\}$

  3. 3.

$M_{3}\coloneqq\max_{t}\|{\Sigma_{0}}^{-1/2}x_{t}\|$

  4. 4.

$M_{4}\coloneqq\max_{t}\|w_{t}\|$

######  Proposition F.1.

$M\leq M_{1}+M_{2}+4M_{3}+2M_{4}$

###### Proof.

$M_{1}=\max_{t}\left\\{\|z_{t}-y_{t}\|\cdot\mathds{1}\\{O_{t}\\}\right\\}$.
Now,

$\displaystyle\|z_{t}-y_{t}\|\cdot\mathds{1}\\{O_{t}\\}$
$\displaystyle=\|z_{t}-y_{t}\|\cdot\mathds{1}\\{\mathcal{T}_{t}\\}+\|z_{t}-y_{t}\|\cdot\mathds{1}\\{\neg\mathcal{T}_{t}\land
O_{t}\\}$
$\displaystyle=\|z_{t}^{\prime}-y_{t}\|\cdot\mathds{1}\\{\mathcal{T}_{t}\\}+\|\mu_{t}-y_{t}\|\cdot\mathds{1}\\{\neg\mathcal{T}_{t}\land
O_{t}\\}$
$\displaystyle\leq\|z_{t}^{\prime}-y_{t}\|\cdot\mathds{1}\\{\mathcal{T}_{t}\\}+\|\mu_{t}-y_{t}\|\cdot\mathds{1}\\{O_{t}\\}$
$\displaystyle\leq\left(\|z_{t}^{\prime}-\mu_{t}\|+\|\mu_{t}-y_{t}\|\right)\cdot\mathds{1}\\{\mathcal{T}_{t}\\}+\|\mu_{t}-y_{t}\|\cdot\mathds{1}\\{O_{t}\\}$
$\displaystyle\leq\|z_{t}^{\prime}-\mu_{t}\|\cdot\mathds{1}\\{\mathcal{T}_{t}\\}+2\|\mu_{t}-y_{t}\|\cdot\mathds{1}\\{O_{t}\\}$
$\displaystyle\leq\|z_{t}^{\prime}-\mu_{t}\|\cdot\mathds{1}\\{\mathcal{T}_{t}\\}+2\|\mu_{t}-\mu_{t}^{*}\|\cdot\mathds{1}\\{O_{t}\\}+2\|w_{t}\|$
$\displaystyle\leq\|z_{t}^{\prime}-\mu_{t}\|\cdot\mathds{1}\\{\mathcal{T}_{t}\\}+4\|\Sigma_{0}^{-1/2}x_{t}\|+2\|w_{t}\|$
$\displaystyle=\|z_{t}^{\prime}-\mu_{t}\|\cdot\mathds{1}\\{C_{t}\land\mathcal{T}_{t}\\}+\|z_{t}^{\prime}-\mu_{t}\|\cdot\mathds{1}\\{\neg
C_{t}\land\mathcal{T}_{t}\\}+4\|\Sigma_{0}^{-1/2}x_{t}\|+2\|w_{t}\|,$

where in the second-to-last step we used (E.1.1). ∎

We will prove the following claims, which finish the proof of Claim F.4.

######  Claim F.5.

$\mathbb{E}[M_{1}^{4}]\leq\smash{\widetilde{O}}(d^{2})$.

######  Claim F.6.

$\mathbb{E}[M_{2}^{4}]\leq\smash{\widetilde{O}}(1)\cdot\frac{d^{2}}{\gamma
T^{2}}$.

######  Claim F.7.

$\mathbb{E}[M_{3}^{4}]\leq\smash{\widetilde{O}}(R^{4})$, and
$\mathbb{E}[M_{4}^{4}]\leq\smash{\widetilde{O}}(R_{w}^{4})$.

First, Claim F.7 follows immediately from (a) $\|w_{t}\|$ being
$R_{w}^{2}$-subgaussian, (b) $\|\Sigma_{0}^{-1/2}x_{t}\|$ being
$R^{2}$-subgaussian, and (c) Claim H.3 (Appendix H). We now prove the other
two claims.

####  F.1.1 Proof of Claim F.5

Let $\sigma^{2}\coloneqq(1\lor\log{(1/\gamma)})\cdot d\cdot\log{(2d)}$. We
will show that for all $t$,
$\|z_{t}^{\prime}-\mu_{t}\|\cdot\mathds{1}\\{C_{t}\land\mathcal{T}_{t}\\}$ is
$O(\sigma^{2})$-subgaussian. Given this, Claim H.3 (Appendix H) finishes the
proof. Fix an $r>0$.

$\displaystyle\operatorname{\mathbb{P}}\left[\|z_{t}^{\prime}-\mu_{t}\|\cdot\mathds{1}\\{C_{t}\land\mathcal{T}_{t}\\}\geq\sigma\cdot
r\right]\leq\operatorname{\mathbb{P}}\left[\|z_{t}^{\prime}-\mu_{t}\|\geq\sigma\cdot
r\ \big{|}\ C_{t}\land\mathcal{T}_{t}\right]$

Observe given $C_{t}\land\mathcal{T}_{t}$, we have $\gamma_{t}\geq\gamma$. Let
$\sigma_{t}^{2}\coloneqq(1\lor\log{(1/\gamma_{t})})\cdot d\cdot\log{(2d)}$.

$\displaystyle\operatorname{\mathbb{P}}\left[\|z_{t}^{\prime}-\mu_{t}\|\cdot\mathds{1}\\{C_{t}\land\mathcal{T}_{t}\\}\geq\sigma\cdot
r\right]$
$\displaystyle\leq\operatorname{\mathbb{P}}\left[\|z_{t}^{\prime}-\mu_{t}\|\geq\sigma_{t}\cdot
r\ \big{|}\ C_{t}\land\mathcal{T}_{t}\right]$
$\displaystyle=\mathbb{E}\left[\operatorname{\mathbb{P}}[\|z_{t}^{\prime}-\mu_{t}\|\geq\sigma_{t}\cdot
r\ |\ \mathcal{F}_{t},\mathcal{T}_{t}]\ |\ C_{t}\land\mathcal{T}_{t}\right].$

But, given $\mathcal{F}_{t}$ and $\mathcal{T}_{t}$, we have
$z_{t}^{\prime}\sim\mathcal{N}(\mu_{t},I,S_{t})$, and so from Claims H.1 and
H.2 (Appendix H), $\|z_{t}^{\prime}-\mu_{t}\|$ is
$O(\sigma_{t}^{2})$-subgaussian. Thus,
$\operatorname{\mathbb{P}}\left[\|z_{t}^{\prime}-\mu_{t}\|\cdot\mathds{1}\\{C_{t}\land\mathcal{T}_{t}\\}\geq\sigma\cdot
r\right]\leq e^{-\Omega(r^{2})}$. $\ \blacksquare$

####  F.1.2 Proof of Claim F.6

As previously, given $\mathcal{F}_{t}$ and $\neg C_{t}\land\mathcal{T}_{t}$,
we have $z_{t}^{\prime}\sim\mathcal{N}(\mu_{t},I,S_{t})$, and so from Claims
H.1 and H.2 (Appendix H), $\|z_{t}^{\prime}-\mu_{t}\|$ is
$\sigma^{2}_{t}$-subgaussian. Thus,

$\displaystyle\mathbb{E}\Big{[}\|z_{t}^{\prime}-\mu_{t}\|^{4}\cdot\mathds{1}\\{\neg
C_{t}\land\mathcal{T}_{t}\\}\Big{]}$
$\displaystyle=\operatorname{\mathbb{P}}[\neg
C_{t}\land\mathcal{T}_{t}]\cdot\mathbb{E}\bigg{[}\mathbb{E}\Big{[}\|z_{t}^{\prime}-\mu_{t}\|^{4}\
\big{|}\ \mathcal{F}_{t},\neg C_{t}\land\mathcal{T}_{t}\Big{]}\ \Big{|}\ \neg
C_{t}\land\mathcal{T}_{t}\bigg{]}$ $\displaystyle\leq
O(1)\cdot\mathbb{E}\left[\sigma^{4}_{t}\cdot\mathds{1}\\{\neg
C_{t}\land\mathcal{T}_{t}\\}\right]$
$\displaystyle\leq\smash{\widetilde{O}}(d^{2})\cdot\mathbb{E}\left[\left(1\lor\log(1/\gamma_{t})\right)^{2}\cdot\mathds{1}\\{\neg
C_{t}\land\mathcal{T}_{t}\\}\right]$
$\displaystyle\leq\smash{\widetilde{O}}(d^{2})\cdot\left(\operatorname{\mathbb{P}}[\neg
C_{t}]+\mathbb{E}\left[\left(\log(1/\gamma_{t})\right)^{2}\cdot\mathds{1}\\{\neg
C_{t}\land\mathcal{T}_{t}\\}\right]\right)$
$\displaystyle\leq\smash{\widetilde{O}}(d^{2})\cdot(1/T^{2}+\gamma^{-1}/T^{2}),$

where in the last step we used Claim H.4 (Appendix H) and Claim E.8.
$\blacksquare$

###  F.2 Proof of Claim F.3

The function $\log^{2}(x)$ is concave for $x\geq e$. Thus, from Jensen’s
inequality,

$\displaystyle\mathbb{E}\left[\log^{2}|\Sigma_{N}|^{1/d}\right]\leq\mathbb{E}\left[\log^{2}\left(e+|\Sigma_{N}|^{1/d}\right)\right]\leq\log^{2}\left(e+\mathbb{E}\left[|\Sigma_{N}|^{1/d}\right]\right)$

Now, from AM-GM,
$|\Sigma_{N}|^{1/d}\leq\frac{1}{d}\cdot\mathrm{tr}(\Sigma_{N})\leq\sum_{t=1}^{T}\|x_{t}\|^{2}$.
Thus,

$\displaystyle\mathbb{E}\left[\log^{2}|\Sigma_{N}|^{1/d}\right]\leq\log^{2}\left(e+T\cdot
R_{x}^{2}\right).$

##  Appendix G Proof of Theorem 3

For all $\mathcal{I}\subseteq[T]$, we define
$X_{\mathcal{I}}\in{\mathbb{R}}^{d\times|\mathcal{I}|}$ be the matrix whose
columns are the $\\{x_{t}\\}_{t\in\mathcal{I}}$, placed in temporal order.
Also, let $X\coloneqq X_{[T]}$, and
$\Gamma_{t}:=\sum_{s=0}^{t-1}(A_{*}^{s})(A_{*}^{s})^{\top}$. The following
lemma (a) upper and lower bounds the ?size? of the covariates, (b) certifies
that our algorithms will use enough data and that $|\mathcal{B}(\alpha)|$ is
small, and (c) bounds $\|w_{t}\|$.

######  Lemma G.1.

Let
$\mathcal{I}^{\prime}_{0}\coloneqq\mathcal{I}_{0}\setminus\mathcal{B}(\alpha)$,
and $C_{\alpha,\beta}=\mathrm{poly}(1/\alpha,1/\beta)$ (sufficiently large).
Also, let

$\displaystyle\mathcal{E}_{g,1}\coloneqq\left\\{|\mathcal{B}(\alpha)|\leq
L\right\\}\land\left\\{|\mathcal{I}_{0}|,|\mathcal{I}_{1}|\geq\alpha\beta
T/4\right\\},\ \ \text{and}$
$\displaystyle\mathcal{E}_{g,2}\coloneqq\left\\{\frac{1}{T}XX^{\top}\preccurlyeq\frac{d}{\delta}\Gamma_{T}\right\\}\land\left\\{\frac{1}{|\mathcal{I}_{0}|}X_{\mathcal{I}_{0}^{\prime}}X_{\mathcal{I}_{0}^{\prime}}^{\top}\succcurlyeq\frac{1}{C_{\alpha,\beta}}\Gamma_{T}\right\\}\land\left\\{\frac{1}{|\mathcal{I}_{1}|}X_{\mathcal{I}_{1}}X_{\mathcal{I}_{1}}^{\top}\succcurlyeq\frac{1}{C_{\alpha,\beta}}\Gamma_{T}\right\\},$

and $\mathcal{E}_{g,3}=\left\\{\forall t:\
\|w_{t}\|\leq\smash{\widetilde{O}}(d)\right\\}$. Let
$\mathcal{E}_{g}\coloneqq\mathcal{E}_{g,1}\land\mathcal{E}_{g_{2}}\land\mathcal{E}_{g,3}$.
Then, $\operatorname{\mathbb{P}}[\mathcal{E}_{g}]\geq 1-\delta-o(1)$.

We will prove Lemma G.1 in Appendix G.4. We will need some definitions to ease
notation. Let $B\coloneqq\mathcal{B}(\alpha),X_{0}\coloneqq
X_{\mathcal{I}_{0}}$, $N_{0}\coloneqq|\mathcal{I}_{0}|$,
$\nu_{t}^{*}\coloneqq\mathbb{E}_{y\sim\mathcal{N}(A_{*}x_{t},I,\mathcal{S}_{t+1})}[y]$,
and $\zeta_{t}\coloneqq\nu_{t}^{*}-A_{*}x_{t}$. Finally, for all
$\mathcal{I}\subseteq[T]$, let $W_{\mathcal{I}},Z_{\mathcal{I}}$ denote the
$d\times|\mathcal{I}|$ matrices whose columns are $(w_{t})_{t\in\mathcal{I}}$
and $(\zeta_{t})_{t\in\mathcal{I}}$ respectively (in temporal order).

On $\mathcal{E}_{g}$, $X_{0}X_{0}^{\top}\succ 0$, so the least-squares
solution is unique, i.e.,
$A_{0}=\sum_{t\in\mathcal{I}_{0}}x_{t+1}x_{t}^{\top}\left(X_{0}X_{0}^{\top}\right)^{-1}$.
Using $x_{t+1}=A_{*}x_{t}+w_{t}$, we get

$\displaystyle(A_{0}-A_{*})\cdot\left(\frac{X_{0}X_{0}^{\top}}{N_{0}}\right)^{1/2}$
$\displaystyle=\frac{1}{\sqrt{N_{0}}}\sum_{t\in\mathcal{I}_{0}}w_{t}x_{t}^{\top}\left(X_{0}X_{0}^{\top}\right)^{-1/2}$
$\displaystyle=\underbrace{\frac{1}{\sqrt{N_{0}}}\sum_{t\in\mathcal{I}_{0}^{\prime}}(w_{t}-\zeta_{t})x_{t}^{\top}\left(X_{0}X_{0}^{\top}\right)^{-1/2}}_{\Delta_{1}}+\underbrace{\frac{1}{\sqrt{N_{0}}}\sum_{t\in\mathcal{I}_{0}^{\prime}}\zeta_{t}x_{t}^{\top}\left(X_{0}X_{0}^{\top}\right)^{-1/2}}_{\Delta_{2}}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
+\underbrace{\frac{1}{\sqrt{N_{0}}}\sum_{t\in\mathcal{I}_{0}\cap
B}w_{t}x_{t}^{\top}\left(X_{0}X_{0}^{\top}\right)^{-1/2}}_{\Delta_{3}},$

where remember that $\mathcal{I}_{0}^{\prime}=\mathcal{I}_{0}\setminus B$. We
will control each $\|\Delta_{i}\|_{\text{F}}$ separately.

######  Claim G.2.

On $\mathcal{E}_{g}$,
$\|\Delta_{3}\|_{\text{F}}^{2}\leq\smash{\widetilde{O}}(dL/N_{0})$.

######  Claim G.3.

On $\mathcal{E}_{g}$, $\|\Delta_{2}\|_{\text{F}}^{2}\leq O(\log(1/\alpha)+1)$.

######  Claim G.4.

On $\mathcal{E}_{g}$, with probability at least $1-\delta$, we have
$\|\Delta_{1}\|_{\text{F}}^{2}\leq\smash{\widetilde{O}}(d^{2}/N_{0})$.

Given these claims, we have that on $\mathcal{E}_{g}$, with probability at
least $1-\delta$,

$\displaystyle\left\|(A_{0}-A_{*})\cdot\left(\frac{X_{0}X_{0}^{T}}{N_{0}}\right)^{1/2}\right\|_{\text{F}}^{2}\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\smash{\widetilde{O}}(1)\cdot\frac{d^{2}+dL}{N_{0}}+O(\log(1/\alpha)+1)$

But, on $\mathcal{E}_{g}$, $N_{0}\geq\alpha\beta T/4$ and
$\frac{X_{0}X_{0}^{\top}}{N_{0}}\succcurlyeq\frac{1}{\mathrm{poly}\left(\frac{1}{\alpha\beta}\right)}\Gamma_{T}$.
Setting $\delta=1/T$, and using the assumed lower bound for $T$, we have that
with probability $1-o(1)$, $\|A_{0}-A_{*}\|_{\Gamma_{T}}\leq
O(\sqrt{\log(1/\alpha)}+1)$. Moreover, in Appendix H.4, we show that
$\|\Gamma_{T}^{-1/2}x_{t}\|$ is $O(d)$-subgaussian. Combining with Lemma G.1,
we complete the proof of Theorem 3. We now prove the three claims.

###  G.1 Proof of Claim G.2

Let $B^{\prime}=\mathcal{I}_{0}\cap B$. We will show that on
$\mathcal{E}_{g}$, $\|\Delta_{3}\|_{\text{F}}^{2}\leq\frac{1}{N_{0}}\sum_{t\in
B^{\prime}}\|w_{t}\|^{2}$. Observe that from Lemma G.1, this immediately gives
the claim.

$\displaystyle\|\Delta_{3}\|_{\text{F}}^{2}$
$\displaystyle=\frac{1}{N_{0}}\mathrm{tr}\left(W_{B^{\prime}}X_{B^{\prime}}^{\top}(X_{0}X_{0}^{\top})^{-1}X_{B^{\prime}}W_{B^{\prime}}^{\top}\right)$
$\displaystyle=\frac{1}{N_{0}}\Big{\langle}W_{B^{\prime}}^{\top}W_{B^{\prime}},X_{B^{\prime}}^{\top}(X_{0}X_{0}^{\top})^{-1}X_{B^{\prime}}\Big{\rangle}$
$\displaystyle=\frac{1}{N_{0}}\Big{\langle}W_{B^{\prime}}^{\top}W_{B^{\prime}},X_{B^{\prime}}^{\top}P_{X_{B^{\prime}}}(X_{0}X_{0}^{\top})^{-1}P_{X_{B^{\prime}}}X_{B^{\prime}}\Big{\rangle}$

where $P_{X_{B^{\prime}}}$ is the projection matrix for the columnspace of
$X_{B^{\prime}}$. Now, note that $X_{0}X_{0}^{T}\succcurlyeq
X_{B^{\prime}}X_{B^{\prime}}^{T}$. This implies that

$\displaystyle
P_{X_{B^{\prime}}}\left(X_{0}X_{0}^{\top}\right)^{-1}P_{X_{B^{\prime}}}\preccurlyeq(X_{B^{\prime}}X_{B^{\prime}}^{\top})^{+},$

where $(X_{B^{\prime}}X_{B^{\prime}}^{T})^{+}$ denotes the pseudoinverse of
$X_{B^{\prime}}X_{B^{\prime}}^{T}$. For a proof of this implication, see Arora
et al. (2019) Lemma E.1. Thus,

$\displaystyle\|\Delta_{3}\|_{\text{F}}^{2}$
$\displaystyle\leq\frac{1}{N_{0}}\Big{\langle}W_{B^{\prime}}^{\top}W_{B^{\prime}},X_{B^{\prime}}^{\top}(X_{B^{\prime}}X_{B^{\prime}}^{\top})^{+}X_{B^{\prime}}\Big{\rangle}.$

But,
$X_{B^{\prime}}^{T}(X_{B^{\prime}}X_{B^{\prime}}^{\top})^{+}X_{B^{\prime}}$ is
just the projection matrix for the rowspace of $X_{B^{\prime}}$, and so
$\|\Delta_{3}\|_{\text{F}}^{2}\leq\frac{1}{N_{0}}\|W_{B^{\prime}}\|_{\text{F}}^{2}$,
and we are done. $\blacksquare$

###  G.2 Proof of Claim G.3

First we show that on $\mathcal{E}_{g}$, if $t\in\mathcal{I}_{0}^{\prime}$,
then $\|\zeta_{t}\|\leq\sqrt{2\log(1/\alpha)}+1$. Consider the filtration
$\mathcal{G}_{t}=\sigma(w_{0},\dots,w_{t-1},\mathcal{S}_{1},\dots,\mathcal{S}_{t+1})$,
and (similarly to the time-series case) the events
$O_{t}=\\{x_{t}\in\mathcal{S}_{t}\\}$, and

$\displaystyle
G_{t}\coloneqq\left\\{O_{t}\rightarrow\left\\{\mathcal{N}(A_{*}x_{t},I;\mathcal{S}_{t+1})\geq\alpha\right\\}\right\\}$

Notice that $t\in\mathcal{I}_{0}^{\prime}$ implies $O_{t}\land G_{t}$. Now,
given $\mathcal{G}_{t}$ and $O_{t}\land G_{t}$, we have
$x_{t+1}\sim\mathcal{N}(A_{*}x_{t},I,\mathcal{S}_{t+1})$, and
$\mathcal{N}(A_{*}x_{t},I;\mathcal{S}_{t+1})\geq\alpha$. Using Claim 5.3, we
get $\|\zeta_{t}\|=\|\nu_{t}^{*}-A_{*}x_{t}\|\leq\sqrt{2\log(1/\alpha)}+1$.
Now,

$\displaystyle\|\Delta_{2}\|_{\text{F}}^{2}=\frac{1}{N_{0}}\Big{\langle}Z_{\mathcal{I}_{0}^{\prime}}^{\top}Z_{\mathcal{I}_{0}^{\prime}},X_{\mathcal{I}_{0}^{\prime}}^{\top}(X_{0}X_{0}^{\top})^{-1}X_{\mathcal{I}_{0}^{\prime}}\Big{\rangle},$

and since
$X_{\mathcal{I}_{0}^{\prime}}X_{\mathcal{I}_{0}^{\prime}}^{\top}\preccurlyeq(X_{0}X_{0}^{\top})$,
the exact same arguments as in proof of Claim G.2 show that
$\|\Delta_{3}\|_{\text{F}}^{2}\leq\frac{1}{N_{0}}\|Z_{\mathcal{I}_{0}^{\prime}}\|_{\text{F}}^{2}\leq
O(\log(1/\alpha)+1)$. $\blacksquare$

###  G.3 Proof of Claim G.4

First, remember that on $\mathcal{E}_{g},$ $X_{0}X_{0}^{\top}\succcurlyeq
X_{\mathcal{I}_{0}^{\prime}}X_{\mathcal{I}_{0}^{\prime}}^{\top}\succ 0$. So,

$\displaystyle\|\Delta_{1}\|_{\text{F}}$
$\displaystyle\leq\sqrt{d/N_{0}}\cdot\left\|\left(W_{\mathcal{I}_{0}^{\prime}}-Z_{\mathcal{I}_{0}^{\prime}}\right)X_{\mathcal{I}_{0}^{\prime}}^{\top}\left(X_{0}X_{0}^{\top}\right)^{-1/2}\right\|_{2}$
(37)
$\displaystyle\leq\sqrt{d/N_{0}}\cdot\left\|\left(W_{\mathcal{I}_{0}^{\prime}}-Z_{\mathcal{I}_{0}^{\prime}}\right)X_{\mathcal{I}_{0}^{\prime}}^{\top}\left(X_{\mathcal{I}_{0}^{\prime}}X_{\mathcal{I}_{0}^{\prime}}^{\top}\right)^{-1/2}\right\|_{2}$
(38)

Now,

$\displaystyle\left\|\left(W_{\mathcal{I}_{0}^{\prime}}-Z_{\mathcal{I}_{0}^{\prime}}\right)X_{\mathcal{I}_{0}^{\prime}}^{\top}\left(X_{\mathcal{I}_{0}^{\prime}}X_{\mathcal{I}_{0}^{\prime}}^{\top}\right)^{-1/2}\right\|_{2}$
$\displaystyle=\sup_{v_{1},v_{2}\in\mathcal{S}^{d-1}}v_{1}^{T}\left(W_{\mathcal{I}_{0}^{\prime}}-Z_{\mathcal{I}_{0}^{\prime}}\right)X_{\mathcal{I}_{0}^{\prime}}^{\top}\left(X_{\mathcal{I}_{0}^{\prime}}X_{\mathcal{I}_{0}^{\prime}}^{\top}\right)^{-1/2}v_{2}$
$\displaystyle=\sup_{v_{1},v_{2}\in\mathcal{S}^{d-1}}\frac{v_{1}^{T}\left(W_{\mathcal{I}_{0}^{\prime}}-Z_{\mathcal{I}_{0}^{\prime}}\right)X_{\mathcal{I}_{0}^{\prime}}^{\top}v_{2}}{\left\|\left(X_{\mathcal{I}_{0}^{\prime}}X_{\mathcal{I}_{0}^{\prime}}^{\top}\right)^{1/2}v_{2}\right\|_{2}}$
$\displaystyle=\sup_{v_{1},v_{2}\in\mathcal{S}^{d-1}}\frac{v_{1}^{T}\left(W_{\mathcal{I}_{0}^{\prime}}-Z_{\mathcal{I}_{0}^{\prime}}\right)X_{\mathcal{I}_{0}^{\prime}}^{\top}v_{2}}{\left\|X_{\mathcal{I}_{0}^{\prime}}^{\top}v_{2}\right\|_{2}}$
$\displaystyle=\sup_{v_{1}\in\mathcal{S}^{d-1},v_{2}\in{\mathbb{R}}_{*}^{d}}\frac{v_{1}^{T}\left(W_{\mathcal{I}_{0}^{\prime}}-Z_{\mathcal{I}_{0}^{\prime}}\right)X_{\mathcal{I}_{0}^{\prime}}^{\top}v_{2}}{\left\|X_{\mathcal{I}_{0}^{\prime}}^{\top}v_{2}\right\|_{2}}.$

Fix some $v_{1}\in\mathcal{S}^{d-1},v_{2}\in{\mathbb{R}}_{*}^{d}$. Let
$H_{t}\coloneqq v_{1}^{T}(w_{t}-\zeta_{t})\cdot\mathds{1}\\{t\in
I_{0}^{\prime}\\}$, and $U_{t}\coloneqq v_{2}^{T}x_{t}\cdot\mathds{1}\\{t\in
I_{0}^{\prime}\\}$, and observe that on $\mathcal{E}_{g}$,

$\displaystyle\frac{v_{1}^{T}\left(W_{\mathcal{I}_{0}^{\prime}}-Z_{\mathcal{I}_{0}^{\prime}}\right)X_{\mathcal{I}_{0}^{\prime}}^{\top}v_{2}}{\left\|X_{\mathcal{I}_{0}^{\prime}}^{\top}v_{2}\right\|_{2}}=\frac{\sum_{t=1}^{T}H_{t}\cdot
U_{t}}{\sqrt{\sum_{t=1}^{T}U_{t}^{2}}}$

Let $\Gamma_{\text{min}}\coloneqq\frac{1}{C_{\alpha,\beta}}\Gamma_{T}$,
$\Gamma_{\text{max}}\coloneqq C_{\alpha,\beta}\frac{d}{\delta}\Gamma_{T}$, and
$C_{\alpha,\beta}=\mathrm{poly}(1/\alpha,1/\beta)$ that is large enough, so
that $\Gamma_{\text{min}}\preccurlyeq
X_{\mathcal{I}_{0}^{\prime}}X_{\mathcal{I}_{0}^{\prime}}^{T}\preccurlyeq\Gamma_{\text{max}}$
on $\mathcal{E}_{g}$. Fix a $\delta\in(0,1)$, and consider a large enough
$K=\widetilde{\Theta}(d)$. We will bound the probability

$\displaystyle
p_{1}\coloneqq\operatorname{\mathbb{P}}\left[\left\\{\frac{\sum_{t=1}^{T}H_{t}\cdot
U_{t}}{\sqrt{\sum_{t=1}^{T}U_{t}^{2}}}\geq
K\right\\}\land\left\\{v_{2}^{\top}\Gamma_{\text{min}}v_{2}\leq\sum_{t=1}^{T}U_{t}^{2}\leq
v_{2}^{\top}\Gamma_{\text{max}}v_{2}\right\\}\right].$

Consider the filtration
$\mathcal{F}_{t}\coloneqq\sigma(w_{0},w_{1},\dots,w_{t-1},\mathcal{S}_{1},\dots,\mathcal{S}_{t+1},\mathds{1}\\{x_{t+1}\in\mathcal{S}_{t+1}\\})$
(similarly to the time-series case). Given $\mathcal{F}_{t}$ and that
$t\in\mathcal{I}_{0}^{\prime}$, we have
$A_{*}x_{t}+w_{t}=x_{t+1}\sim\mathcal{N}(A_{*}x_{t},I,\mathcal{S}_{t+1})$, and
$\mathcal{N}(A_{*}x_{t},I;\mathcal{S}_{t+1})\geq\alpha$. Combining with Claim
H.1 (Appendix H), we get $\|v_{1}^{T}w_{t}\|_{\psi_{2}}^{2}\leq
O(1\lor\log{(1/\alpha)})$. Also, from Claim 5.3,
$\|v_{1}^{T}\zeta_{t}\|_{\psi_{2}}^{2}\leq\|\zeta_{t}\|_{2}^{2}\leq
O(1\lor\log{(1/\alpha)})$. Thus, given $\mathcal{F}_{t}$, $H_{t}$ is mean
zero, and $O(1\lor\log{(1/\alpha)})$-subgaussian. Furthermore, observe that
$H_{t}$ is $\mathcal{F}_{t+1}$-measurable, while $U_{t}$ is
$\mathcal{F}_{t}$-measurable. Using Lemma 4.2 from Simchowitz et al. (2018),
we get

$\displaystyle
p_{1}\leq\log\left(\frac{v_{2}^{\top}\Gamma_{\text{min}}v_{2}}{v_{2}^{\top}\Gamma_{\text{max}}v_{2}}\right)\cdot\exp\left(-\frac{K^{2}}{O(1\lor\log{(1/\alpha)})}\right).$

Also, observe that

$\displaystyle\operatorname{\mathbb{P}}\left[\frac{v_{1}^{\top}\left(W_{\mathcal{I}_{0}^{\prime}}-Z_{\mathcal{I}_{0}^{\prime}}\right)X_{\mathcal{I}_{0}^{\prime}}^{\top}v_{2}}{\left\|X_{\mathcal{I}_{0}^{\prime}}^{\top}v_{2}\right\|_{2}}\cdot\mathds{1}\\{\mathcal{E}_{g}\\}>K\right]\leq
p_{1}$

Now, let $\mathcal{N}_{1}$ be a $1/2$-net of $\mathcal{S}^{d-1}$, and let
$\mathcal{N}_{2}$ be a $1/4$-net of $\mathcal{S}_{\Gamma_{\text{min}}}$ in the
norm $\|\Gamma_{\text{max}}^{1/2}(\cdot)\|_{2}$. Taking a union bound,

$\displaystyle\operatorname{\mathbb{P}}\left[\exists\
v_{1}\in\mathcal{N}_{1},v_{2}\in\mathcal{N}_{2}:\
\frac{v_{1}^{\top}\left(W_{\mathcal{I}_{0}^{\prime}}-Z_{\mathcal{I}_{0}^{\prime}}\right)X_{\mathcal{I}_{0}^{\prime}}^{\top}v_{2}}{\left\|X_{\mathcal{I}_{0}^{\prime}}^{\top}v_{2}\right\|_{2}}\cdot\mathds{1}\\{\mathcal{E}_{g}\\}>K\right]\leq
p_{1}\cdot|\mathcal{N}_{1}|\cdot|\mathcal{N}_{2}|$

Using the bounds on $|\mathcal{N}_{1}|,|\mathcal{N}_{2}|$ from Simchowitz et
al. (2018) (Lemma D.1), we get

$\displaystyle p_{1}\cdot|\mathcal{N}_{1}|\cdot|\mathcal{N}_{2}|$
$\displaystyle\leq\log\left(\frac{v_{2}^{\top}\Gamma_{\text{max}}v_{2}}{v_{2}^{\top}\Gamma_{\text{min}}v_{2}}\right)\cdot\exp\left(O(d)+2\log\det(\Gamma_{\text{max}}\Gamma_{\text{min}}^{-1})-\frac{K^{2}}{O(1\lor\log{(1/\alpha)})}\right)\leq\delta,$

where we used the definitions of $\Gamma_{\text{max}},\Gamma_{\text{min}}$,
and $K$. So now we have

$\displaystyle\operatorname{\mathbb{P}}\left[\left\\{\sup_{v_{1}\in\mathcal{N}_{1},v_{2}\in\mathcal{N}_{2}}\frac{v_{1}^{\top}\left(W_{\mathcal{I}_{0}^{\prime}}-Z_{\mathcal{I}_{0}^{\prime}}\right)X_{\mathcal{I}_{0}^{\prime}}^{\top}v_{2}}{\left\|X_{\mathcal{I}_{0}^{\prime}}^{\top}v_{2}\right\|_{2}}>K\right\\}\land\mathcal{E}_{g}\right]\leq\delta.$

With an argument identical to the one of Simchowitz et al. (2018) (Appendix
D.2), we get that

$\displaystyle\operatorname{\mathbb{P}}\left[\left\\{\sup_{v_{1}\in\mathcal{S}^{d-1},v_{2}\in{\mathbb{R}}_{*}^{d}}\frac{v_{1}^{\top}\left(W_{\mathcal{I}_{0}^{\prime}}-Z_{\mathcal{I}_{0}^{\prime}}\right)X_{\mathcal{I}_{0}^{\prime}}^{\top}v_{2}}{\left\|X_{\mathcal{I}_{0}^{\prime}}^{\top}v_{2}\right\|_{2}}>4K\right\\}\land\mathcal{E}_{g}\right]\leq\delta,$

and we are done. $\blacksquare$

###  G.4  Proof of Lemma G.1

We will deduce Lemma G.1 as a corollary of the following lemma.

######  Lemma G.5.

Fix $\delta,\epsilon\in(0,1)$, and an integer $k\geq 1$. Then, there exist
absolute constants $C,C^{\prime}>0$, such that if

$\displaystyle\frac{T}{k}\geq
C\left(\frac{d}{\epsilon^{2}}\log{\left(\frac{d}{\delta\epsilon}\right)}+\frac{1}{\epsilon^{2}}\log\det(\Gamma_{T}\Gamma_{k}^{-1})\right),\
\ \text{then}$ (39)
$\displaystyle\operatorname{\mathbb{P}}\left[\left\\{\frac{1}{T}XX^{\top}\preccurlyeq\frac{d}{\delta}\Gamma_{T}\right\\}\land\left\\{\forall\
\mathcal{I}\subseteq[T]\ \text{s.t.}\ |\mathcal{I}|\geq\epsilon T,\ \text{we
have}\
\frac{1}{|\mathcal{I}|}X_{\mathcal{I}}X_{\mathcal{I}}^{\top}\succcurlyeq\frac{\epsilon^{4}}{C^{\prime}}\Gamma_{k}\right\\}\right]\geq
1-\delta$ (40)

Given the above, we prove Lemma G.1.

###### Proof.

We will use Lemma G.5, with $\epsilon=\alpha\beta/8$, and
$k=\widetilde{\Theta}\left(\frac{1}{1-\rho(A_{*})}\right)$. We need the
following proposition.

######  Proposition G.1.

For large enough $k=\widetilde{\Theta}\left(\frac{1}{1-\rho(A_{*})}\right)$,
we have $2\Gamma_{k}\succcurlyeq\Gamma_{T}$.

###### Proof.

$\|\Gamma_{T}-\Gamma_{k}\|_{2}\leq\sum_{s=k}^{T-1}\left\|(A_{*}^{s})(A_{*}^{s})^{\top}\right\|_{2}$.
Also, observe that
$\left\|(A_{*}^{s})(A_{*}^{s})^{\top}\right\|_{2}\leq\text{cond}(S)^{2}\rho^{2k}(A_{*})$.
Summing up and using the scale of $k$, we get
$\|\Gamma_{T}-\Gamma_{k}\|_{2}<1$. The fact that $\Gamma_{k}\succcurlyeq I$
completes the proof. ∎

Observe that the above proposition, and the assumed lower bound on $T$ imply
that 39 is satisfied. Now, from Proposition (3.1),
$\operatorname{\mathbb{P}}[|\mathcal{I}_{0}|,|\mathcal{I}_{1}|\geq\alpha\beta
T/4]\geq 1-o(1)$. Also, from Assumption 3,
$\operatorname{\mathbb{P}}[|\mathcal{B}(\alpha)|\leq L]\geq 1-o(1)$. Thus,
$\operatorname{\mathbb{P}}[|\mathcal{I}_{0}|,|\mathcal{I}_{1}|,|\mathcal{I}_{0}^{\prime}|\geq\epsilon
T]\geq 1-o(1)$ (remember that $L<<T$). Lemma G.5 and Gaussian-norm
concentration finish the proof. ∎

The main part of this section is devoted to proving the following lemma, from
which we can easily deduce Lemma G.5.

######  Lemma G.6.

Fix $\epsilon\in(0,1)$, $1\leq k\leq\sqrt{\epsilon}T$, and
$v\in\mathcal{S}^{d-1}$. Let $c(\epsilon)=\frac{\sqrt{8/\pi}}{\epsilon}$, and
$k(\epsilon)=\lfloor\frac{\epsilon k}{2}\rfloor$. Then,

$\displaystyle\operatorname{\mathbb{P}}\left[\exists\
\mathcal{I}\subseteq[T]:\ |\mathcal{I}|\geq 5\sqrt{\epsilon}T\ \ \text{and}\ \
\frac{1}{|\mathcal{I}|}\sum_{t\in\mathcal{I}}(v^{\top}x_{t})^{2}<\frac{v^{\top}\Gamma_{k(\epsilon)}v}{2c^{2}(\epsilon)}\right]\leq\exp\left(-\frac{\lfloor
T/k\rfloor}{8}\right).$

Given Lemma G.6, we can show the following corollary, from which Lemma G.5
immediately follows.

######  Corollary G.1.

Fix $\epsilon\in(0,1)$, $1\leq k\leq\sqrt{\epsilon}T$, and let
$c(\epsilon),k(\epsilon)$ as in Lemma G.6. Then,

$\displaystyle\operatorname{\mathbb{P}}\Bigg{[}\left\\{\frac{1}{T}XX^{\top}\preccurlyeq\frac{d}{\delta}\Gamma_{T}\right\\}\land\bigg{\\{}\forall\
\mathcal{I}\subseteq[T]\ \text{s.t.}\ |\mathcal{I}|$ $\displaystyle\geq
5\sqrt{\epsilon}T\ \text{we have}\
\frac{1}{|\mathcal{I}|}X_{\mathcal{I}}X_{\mathcal{I}}^{\top}\succcurlyeq\Gamma_{\text{min}}\bigg{\\}}\Bigg{]}$
$\displaystyle\geq
1-\delta-\exp\left(d\log{9}+\log\det(\Gamma_{\text{max}}\Gamma_{\text{min}}^{-1})-\frac{\lfloor
T/k\rfloor}{8}\right),$

where $\Gamma_{\text{min}}=\frac{1}{4c^{2}(\epsilon)}\Gamma_{k(\epsilon)}$,
$\Gamma_{\text{max}}=\frac{d}{5\delta\sqrt{\epsilon}}\Gamma_{T}$.

###### Proof.

Using that for any $\mathcal{I}\subseteq[T]$ such that $|\mathcal{I}|\geq
5\sqrt{\epsilon}T$, we have
$\frac{1}{|\mathcal{I}|}X_{\mathcal{I}}X_{\mathcal{I}}^{\top}\preccurlyeq\frac{1}{5\sqrt{\epsilon}}\frac{1}{T}XX^{\top}$,
the corollary follows from Lemma G.6 by using exactly the same (net-based)
arguments as Simchowitz et al. (2018) (Lemma D.1., and beginning of Section
4). ∎

For the rest of the section, we work on proving Lemma G.6. We use the
martingale small-ball technique of Simchowitz et al. (2018).

######  Definition G.1 (Martingale Small-Ball; Simchowitz et al. (2018)).

Let $\mathcal{G}_{t}$ be a filtration, and let $(z_{t})_{t\geq 1}$ be a
$\\{\mathcal{G}_{t}\\}_{t\geq 1}$-adapted random process taking values in
${\mathbb{R}}$. We say $(z_{t})_{t\geq 1}$ satisfies the $(k,\nu,p)$-block
martingale small-ball (BMSB) condition if, for any $j\geq 0$, one has
$\frac{1}{k}\sum_{i=1}^{k}\operatorname{\mathbb{P}}(|z_{j+i}\ |\
\geq\nu|\mathcal{G}_{j})\geq p$ almost surely. Given a process $(x_{t})_{t\geq
1}$ taking values in ${\mathbb{R}}^{d}$, we say that it satisfies the
$(k,\Gamma_{\text{sb}},p)$-BMSB condition for $\Gamma_{\text{sb}}\succ 0$ if,
for any fixed $v\in\mathcal{S}^{d-1}$, the process $z_{t}\coloneqq\langle
v,x_{t}\rangle$ satisfies $(k,\sqrt{v^{\top}\Gamma_{\text{sb}}v},p)$-BMSB.

Now, suppose that a (real) process $(z_{t})_{t}$ satisfies the
$(k,\nu,1-\epsilon)$-BMSM condition. We partition the sequence
$z_{1},\dots,z_{T}$ into $\tau\coloneqq\lfloor T/k\rfloor$ blocks of size $k$
(we discard the remaining terms). For $0\leq\ell\leq\tau-1$, we consider the
events

$\displaystyle\mathcal{E}_{\ell}\coloneqq\left\\{\frac{1}{k}\sum_{j=1}^{k}\mathds{1}\left\\{|Z_{\ell
k+j}|\geq\nu\right\\}\geq 1-\sqrt{\epsilon}\right\\}$

######  Claim G.7.

$\operatorname{\mathbb{P}}\left[\sum_{\ell=0}^{\tau-1}\mathds{1}\\{\mathcal{E}_{\ell}\\}\leq(1-\sqrt{\epsilon}/2)\tau\right]\leq\exp(-\tau/8)$.

We provide a proof of Claim G.7 in Appendix H (Claim H.6).

#### Application to LDSs

######  Proposition G.2.

Consider the linear dynamical system $x_{t+1}=A_{*}x_{t}+w_{t}$, where
$x_{0}=0$, $w_{t}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
i.i.d}}}{\sim}}\mathcal{N}(0,I)$, and let
$\Gamma_{t}:=\sum_{s=0}^{t-1}(A_{*}^{s})(A_{*}^{s})^{\top}$. Fix an
$\epsilon\in(0,1)$. Then, for $1\leq k\leq T$, the process $(x_{t})_{t\geq 1}$
satisfies the

$\displaystyle\left(k,\frac{1}{c^{2}(\epsilon)}\Gamma_{k(\epsilon)},1-\epsilon\right)\text{-block
martingale small-ball condition},$

where $c(\epsilon)=\frac{\sqrt{8/\pi}}{\epsilon}$ and
$k(\epsilon)=\lfloor\frac{\epsilon k}{2}\rfloor$.

###### Proof.

Consider the filtration
$\mathcal{G}_{t}\coloneqq\sigma(w_{0},w_{1},\dots,w_{t-1})$. Fix a
$v\in\mathcal{S}^{d-1}$. We have

$\displaystyle
v^{\top}x_{s+j}=v^{\top}A_{*}^{j}x_{s}+v^{\top}\sum_{i=0}^{j-1}A_{*}^{i}w_{s+j-i-1}.$

Given $\mathcal{G}_{s}$,
$v^{\top}\sum_{i=0}^{j-1}A_{*}^{i}w_{s+j-i-1}\sim\mathcal{N}(0,v^{\top}\Gamma_{j}v)$.
From Claim H.5 (Appendix H), for any $c>0$,

$\displaystyle\operatorname{\mathbb{P}}\left[|v^{\top}x_{s+j}|<\frac{v^{\top}\Gamma_{j}v}{c}\
\bigg{|}\ \mathcal{G}_{s}\right]\leq\frac{\sqrt{2/\pi}}{c}.$

We choose $c=\frac{2\sqrt{2/\pi}}{\epsilon}$. Using that for all $j\geq
k(\epsilon)$, $\Gamma_{j}\succcurlyeq\Gamma_{k(\epsilon)}$, we get

$\displaystyle\frac{1}{k}\sum_{j=0}^{k}\operatorname{\mathbb{P}}\left[|v^{\top}x_{s+j}|\geq\frac{\sqrt{v^{\top}\Gamma_{k(\epsilon)}v}}{c}\
\Bigg{|}\ \mathcal{G}_{s}\right]$
$\displaystyle\geq\frac{1}{k}\sum_{j=k(\epsilon)}^{k}\operatorname{\mathbb{P}}\left[|v^{\top}x_{s+j}|\geq\frac{\sqrt{v^{\top}\Gamma_{k(\epsilon)}v}}{c}\
\Bigg{|}\ \mathcal{G}_{s}\right]$
$\displaystyle\geq\frac{1}{k}\sum_{j=k(\epsilon)}^{k}\operatorname{\mathbb{P}}\left[|v^{\top}x_{s+j}|\geq\frac{\sqrt{v^{\top}\Gamma_{j}v}}{c}\
\Bigg{|}\ \mathcal{G}_{s}\right]$
$\displaystyle\geq\frac{k-k(\epsilon)}{k}\left(1-\frac{\sqrt{2/\pi}}{c}\right)\geq(1-\epsilon/2)^{2}\geq
1-\epsilon.$

∎