Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Models
Authors: Yihan Zhang
Nir Weinberger
Venue: NeurIPS 2022 Accept (2022)
Keywords: High-dimensional statistics
parameter estimation
hidden Markov model
minimax rate
spectral estimator

Abstract: We consider a high-dimensional mean estimation problem over a binary hidden Markov model, which illuminates the interplay between memory in data, sample size, dimension, and signal strength in statistical inference. In this model, an estimator observes $n$ samples of a $d$-dimensional parameter vector $\theta_{*}\in\mathbb{R}^{d}$, multiplied by a random sign $ S_i $ ($1\le i\le n$), and corrupted by isotropic standard Gaussian noise. The sequence of signs $\{S_{i}\}_{i\in[n]}\in\{-1,1\}^{n}$ is drawn from a stationary homogeneous Markov chain with flip probability $\delta\in[0,1/2]$. As $\delta$ varies, this model smoothly interpolates two well-studied models: the Gaussian Location Model for which $\delta=0$ and the Gaussian Mixture Model for which $\delta=1/2$. Assuming that the estimator knows $\delta$, we establish a nearly minimax optimal (up to logarithmic factors) estimation error rate, as a function of $\|\theta_{*}\|,\delta,d,n$. We then provide an upper bound to the case of estimating $\delta$, assuming a (possibly inaccurate) knowledge of $\theta_{*}$. The bound is proved to be tight when $\theta_{*}$ is an accurately known constant. These results are then combined to an algorithm which estimates $\theta_{*}$ with $\delta$ unknown a priori, and theoretical guarantees on its error are stated.

Mean Estimation in High-Dimensional Binary Markov Gaussian Mixture Models
Yihan Zhang Institute of Science and Technology, Austria
Nir Weinberger
Technion - Israel Institute of Technology nirwein@technion ac.
zephyr 277980gma11 com
Abstract
We consider a nigh-dimensional mean estimation problem over a binary hidden Markov model, which illuminates the interplay between memory data, sample size, dimension, and signal strength in statistical inference. In this model, an estimator observes n samples of a d-dimensional parameter vector O, E R multiplied by a random sign S, (1 < i S nt), and corrupted by isotropic standard Gaussian noise. The sequence of signs {St E {-1,1} drawn from a stationary homogeneous Markov chain with flip probability 8 E 1/2]. As ő varies, this model smoothly interpolates two well-studied models: the Gaussian Location Model for which 1/2. Assuming that the estimator knows 6, we establish nearly minimax optimal (up to logarithmic factors) estimation error rate, as a function of |0-]], 6, d, n. We then provide upper bound to the case of estimating 5, assuming (possibly inaccurate) knowledge of 9.. The bound is proved to be tight when 6, is an accurately known constant. These results are then combined to algorithm which estimates 0. with unknown a priori, and theoretical guarantees on its error are stated.
and the Gaussian Mixture Model for which
Introduction
Memory between data samples is ubiquitous in practical applications, as data collected from networks or sampled time series inevitably inherit spatial or temporal statistical dependencies. Numerous
examples arise in imaging, meteorology, health care, finance, social science, and so on GGlaeser et al.
1996 Bertrand al. 2000 Sacerdote 2001] Duflo and Saez 2003 Christakis and Fowler 2013]. In principle, prior knowledge ledge of the existence of such memory can be used to improve the performance of statistical estimators compared the performance obtained in memoryless models. Development and analysis of statistical inference algorithms for models with memory has been extensively explored from the algorithmic perspective, and computationally efficient algorithms such as Baum-Welch and
message-passing were developed [Ephraim and Merhav 2002 van Handel 2008 MacKay 2003
Wainwright and Jordan 2008). was also extensively studied from the theoretical perspective in the classical, dimenssonli and asymptotic regime, e.g., Györfi al. [2002 Chapter 27 and references therein]. However, much less is understood about the high dimensional, non-asymptotic regime, which is of paramount importance in modern applications, and the focus of current extensive research [Vershynin] 2018 Wainwright 2019). As we exemplify in this paper, the error in such estimation problems depends in intricate way the interplay between the number of samples, the dimension of the vector parameters to be estimated, the noise level (signal-to-nan ratio), and the level of memory between the samples.
An ever popular and fundamental model is the Gaussian mixture model, in which memory exists between samples whenever the latent variables determining the component of each sample are dependent. Numerous recent papers, e.g., Balakrishnan et al. [2017). Xu et al. [016)] Klusowski
and Brinda [0166]. Jin et al. 2016 Dwivedi et al. [020bb] Dwivedi et al.) 2018 Dwivedi et al.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

2020a Zhao et al. (2018), Yan et al. 2017]. Weinberger and Bresler [002] have focused on high- dimensional memoryless models, and analyzed computationally efficient estimation algorithms, most notably the expectation maximization (EM) algorithm. Specifically, the seminal [Balakrishnan et al. 2017] has provided theoretical guarantees for EM in memoryless models, though without proving minimax optimality, which was subsequently established in Wu and Zhou [2019]. As a notable exception, Yang et al. [2015] has generalized the analysis of Balakrishhaan et al. [2017] to a hidden Markov model (HMM) that has memory, yet again, without determining how the minimax error rate depends on the number of samples, dimension, noise level, and the amount of memory. paper, we address the question of precise characterization of the minimax error rate in terms of these parameters, in the context of a high-ding sigh-dimensional Gaussian HMM. We next turn to formally define this model and the estimation problem, describe known results, and then present our contributions. Our obtained results illuminate the opportunities and challenges associated with optimal inference in high dimensional models with memory.
this
1.1 Problem formulation
Let SB == (So, .I,...,S)) be the following homogeneous binary symmetric Markov chain, S; E {-1, 11111.PPP5. P(So 1] 1]=11 =1/2 and
w.p. 1 5 S1- S,
S.
(I)
w.p. 5
for E [n] :- (1...., n,. and where 8 E f0. 1] is the flip probability of the binary Markov chain. We also denote p = 1 E [-1, which is the correlation between adjacent samples p = E[S,S++1]. At each time point E [nn] a sample of a d-dimensional Gaussian mixture model is observed
X; S.O, + Zi,
(2)
where Z; ~ N(0 Ia) is an i.i.d. sequence, independent of St and where 0. E Rdd, 2 1. At its two extremes, this model degenerates one of two fundamental models, which well studied. When 5 = 0, the memory length is infinite, and the sign So = S ..... sign ambiguity, the model (2) is the standard Gaussian location model (GLM), which is essentially memoryless model (and exactly so if So is known). When = 1. the signs Sp are i.i.d. and have no memory at all. The model (2) is then a Gaussian mixture model (GMM) with two symmetric components, which is also memoryless model. In all other cases, 0 < 5 < (or 1
S₂ is fixed. Thus, up to this
2 < 8 < 1), the
model is a simple version of HMM.
The inference problem we consider in this paper is the estimation of 0, E Rdd, under the loss function
loss(ff, 0-) == min [||@ 1. 1 +.11,
(3)
that is, the Euclidean distance error under possible sign ambiguity An intermediate goal (or an additional problem) is estimate 8, under the regular absolute error loss function 88 8). The fundamental limits this estimation problem will be gauged by the local minimax rate, which is the maximal decrease rate of the loss possible for any estimator, given n samples, at dimension d 2 for signal strength ||e_ ||= f, and under flip probability 5. Specifically, for d 2 2 is defined as
M(n, d, 8,t) == inf sup E [oss((0,, 0.,, 0(x)))
((X)) ||@.||=t
For general d 2 1, the global minimax rate is defined with the condition ||0, |0.||= t replaced by ||0_1 S (this condition trivializes the estimator for d = 1).
1.2 Known minimax estimation errors rates for GLM and GMM
Before delving into models with memory (0 < 8 < 1/2), we review known results on the minimax rates in memoryless high dimensional Gaussian models - the GLM (5 = 0) and the GMM (8 = 1 1/2). We refer the reader to note that the minimax error rate in these models may undergo two possible phase transitions one as É increases, and the other one as d increases. We also remark that the regime of interest is that of low-separation (t S 1), in which accurately detecting the components is impossible, yet parameter estimation with vanishing loss is possible.
Similar bounds can be derived for the squared loss by trivial extensions.

---

At the first extreme, the local minimax rate for the GLM (6 0) is the usual parametric eтrоr rate
MMLM(n, d, d,0,), x
(5)
This is achieved by the trivial estimator 0 = 0 if - V and the simple empirical average estimator
/ (see [Wu 2017. Sec. I11-))). The rate @ (t is then the global minimax rate, i.e., the largest error over = |= 0. This model does not have a phase transition with dimension. At the other extreme, the GMM model (ō 2)) undergoes a phase transition at the dimension d = n. At low dimension, d S. n, the minimax rate was neatly shown in [Wu and Zhou 2019 Appendix B] to be
i 0= - -
(#) 1/4
t,
MaMM (n, d,,, M (n, d, 5.1)
x
n
(4)
1/4
sts1,
(6)
1>1
whereas at high dimension d 2 n. it is as for the Gaussian location model in 5 i.e. MaMM(n, d, t) = MGLM (n, d, t). Hence, this high dimensional regime, the loss does not vanishes by increasing the signal strength t, or by increasing the number of samples n. The loss in (6) is achieved by the trivial estimator å = 0 if < (a) 1/4 and by an estimator given by a properly scaled and shifted principal
1/4 For the GMM low dimension, S n. the global minimax rate is (2)2/4 which is worse than the minimax rate the Gaussian location model V //--
component of the empirical covariance matrix of XT == (X1, X.,..., X,), I 2 (a)
Therefore, the GMM has worse estimation performance compared to the GLM from three aspects: First, at low dimension, d I n, it has larger global minimax rate 1 compared to the parametric error rate of the GLM, L. Second, at low dimension, d S n, parametric error rate is achieved only for constant separation 2 1; Third, the transition to the high dimension regime occurs
n. As is intuitively appealing from a "data- processing" reasoning, a Markov model with flip probability 8' should allow for lower estimation error of compared to Markov model with 8 8', Indeed, and as a specific simple example, any Markov model with < can be easily transformed to a GMM model by randomizing the signs of each of the samples by an independent Rademacher variable. Thus we may deduce, e.g., that since at high dimension (d 2 n) the GLM and the GMM have the same minimax rates, the minimax rates for exclusively focus on the regime d S n. As we show, it is generally true that the improvement in estimation error when is reduced is less profound as the dimension increases.
are in fact as in (5) for any 8 E [0, 1]. We thus henceforth
1.3 Contributions
We first consider the case in which ò is known to the estimator of 0.. For this case, we analyze the loss of an estimator that is based on a computation of the principal component a properly chosen empirical covariance matrix. We show (Theorem) I that, at low dimension, d S ôn, it achieves a local minimax rate of
S 6d 1/4
M(n, d, 6,
(
1/4
sts
n
and at high dimension, d 2 8n, it is as for the Gaussian location model in 5). The rate of this estimator is then further shown to asymptotically optimal (up to a logarithmic factor) via a minimax lower bound (Theorem 2b. Evidently, the loss in ? smoothly interpolates the rates of the GLM in (5) and the GMM in (6). Moreover, is evident that the loss is improved with the decrease of from all three aspects previously mentioned. First, at low dimension, d < 8n, the global minimax rate is

---

(d 1/4
(obtained by equating the first and second cases Hence, reducing the flip probability from (1) to 8 smoothly reduces the global minimax rate from the parametric error rate e of the GLM to the (((=)'/ 1/4) of the GMM. Second, at low dimension, d S ôn, the minimal signal strength required obtain parametric error rate is (v0)) (obtained from the third case (7). This, again, improves by decreasing 6, and matches the extremes f. @ x
of GL.M and t (1) of GMM. Third, the transition to the high dimension regime occurs at d = ôn, which is again better with lower 6, and matches the transition point of the GMM given by d = n. This lower transition point allows
achieve the rate of the GLM for any signal strength, even in regime in which the loss V / vanishes with
(unlike for GMM, ó }): specifically, this
occurs whenever d 2 En yet d = o(n). Beyond the formal proof, Appendix A provides heuristic justification for why the minimax error naturally expected to scale in 77p
Second, as step towards the removal of the assumption that ò is known to the estimator, we consider the complementary problem of estimating 8 whenever an estimate 0g of f, is available (which be either exact 0g 0., or inaccurate 0g a 0.). We propose simple estimator for ô, and analyze its error in case of a mismatch (Theorem 4p. We then specify this result the matched case 02 O. and
show that the non-trivial regime (1 1) its error rate ((Te)) V
We then proceed to show
an impossibility lower bound of 22( !,) (Proposition 6) for this error rate. The precise dependence
of the estimation error rate of 5 on |0_|| || is therefore not precisely determined, and we discuss the challenges in settling this matter.
Third, consider the case in which the estimator of 0., has no prior knowledge of 5. We propose three-step algorithm for this case (Algorithm []. First, a (possibly) gross estimate (( 0, is computed based on third of the samples, assuming the worst case of å 1 Then, an estimate ((B) of 8 computed using another third of the samples, assuming the estimate ((A), Finally, a refined estimate ((C) of f. is obtained by (essentially) assuming that 5 (B)) each of the steps above, the algorithm may stop and decide to return its current estimate when it determines that no further improvement is possible by moving on to the next steps. We analyze the loss of this algorithm (Theorem 7b. and show that this algorithm is capable of partially achieving the gains associated with the case of known
Our technique of partitioning the samples to blocks according to the dependence structure of the Markov chain renders the possibility of understanding the minimax rate of more general models, such as mixtures with multiple components [Doss et al. 20200 and memory, Ising models [Daskalakis] jet al. 2019), Boltzmann machines [Bresler al. [2019), Markov random fields, etc. Our findings in the mean estimation setting also stand in contrast to the data wastage phenomenon observed in the
linear regression setting in the prior work [Bresler et al. 2020
1.4
Additional related work
McLachlan et al.) 2019] are classic models which were well-explored from numerous perspectives. In the last few years, there is surge of interest in the non-asymptotic performance analysis of computationally efficient estimation algorithms for this estimation task. For example, Moitra and Valiant [2010), Kalai et al.) Anandkumar et al. (2014). Hardt and Price [2015) Wu and Yang [2020] have analyzed method- of-moments- based algorithms, and various other papers considered the EM algorithm [Balakrishnan Weinberger and Bresler 2022 Dwivedi et al. 2020b a 2018 Zhao et al. 2018 Yan et al. 2017 Specifically, the local
Both the GLM [Johnstone]] 2002 Tsybakov 2008 and GMM [Lindsay] 1995
ct al. 2017 Xu al. 2016 Jin et al. 2016 Klusowski and Brinda, 2016
minimax rate for GMM in 66) was determined in Wu and Zhou
2019
as a benchmark for the
operation of the EM algorithm.
The model (2) is a simple instance of a HMM [Ephraim and Merhay 2002
van Handel, 2008] in high dimensions. Parameter estimation in such models is practically performed via the Baum- Welch algorithm [Baum et al. 1970]. which is a computationally efficient version of EM for HMMs. To the best of our knowledge, there were hardly any attempts to characterize the minimax rates such models, with the exception of [Aiylam 2018 and Yang et al. 2015), previously mentioned. In

---

Aiylam 2018], local version of the Baum- Welch algorithm was proposed, and vanishing error of the convergence of the estimate to the true parameter was established for both a population version as well as finite-sample version. In (Yang et al.) 2015], general bounds on the performance of Baum-Welch algorithm were specified to the Gaussian model with Markov signs (2) considered here. It was shown that the Baum- Welch algorithm achieves a parametric error rate, and converges in finite number of iterations (Yang et al. estimation error bound of Yang et al. 2015 is that & |0+ log T-(1-26)7 that is, a non-trivial separation when o is constant, which further blows up as 5 4 0. By contrast, in this paper, our goal is to characterize the estimation error in the regime of ō and = ||O=]| in which the minimax rate is affected by these parameters, and this requires analyzing vanishing 8 and t.
2015 Corollary 2J. However, the qualifying condition for the
More broadly, there is a growing interest in advancing the quantitative understanding of the performance of statistical learning and inference with dependent data. |Brsserr et al. (2020) studied linear regression with Markovian covariates and characterized the minimax error rate in terms of the mixing time of the Markov chain. A stochastic gradient descent-style algorithm adapted to the Markov setting was shown to be minimax optimal. Statistical estimation problems including linear and logistic regression with more general network dependencies among response variables were studied by Daskalakis et al. [2019) and Kandiros et al.] [202T). Learnability and generalization bounds were derived by Dagan et [2019] for dependent data satisfying the so-called Dobrushin's 's condition.
1.5 Notation conventions
For a vector E Rdd ||al|| is the Euclidean norm. For a positivedefinite matrix A, Amax (A) and Vmax(A) are the maximal eigenvalue and the associated eigenvector (of unit norm) of A. Unless otherwise stated, the constants involved in Bachmann-Landar notation are numerical, and do not depend on the parameters (n, dl, 5, (). It holds that a 2 b (resp. S b) if there exists constant e > 0 (resp. C > 0) such that a 2 cb (resp. a S Cb). a S b and a Z b. then a x b. Integer constraints (ceiling and floor) on large quantities that do not affect the results are omitted for brevity. For a real numbers a, the shorthand notation a v b := max a, 6}. a A := min(a (a, 63 and (a)+ := a V 0 is used. A sequence of objects X1..... Xx, is denoted by XT' Expectation, variance and probability are denoted by E, V and P. respectively. Equality in distribution of random variables X and Y is denoted by X Y. All logarithms log are the base e.
2 Mean estimation for known flip probability
In this section, we consider the problem of estimating 9, whenever is exactly known to the estimator. In that case, it may be assumed w.l.o.g. that 8 E [0, 2) as otherwise one may negate each of the even samples to obtain an equivalent model with ō replaced with 1 - d. Hence also E [0, 1]. We next deseribe estimator for this task, state bound its performance, and then show that it matches (up to logarithmic factor) an impossibility lower bound.
The estimator operationally interpolates and therefore simultaneously generalizes the empirical average estimator (30) and the (properly scaled) principal component estimator (32) analyzed in [Wu and Zhou 2019, Appendix BJ. It degenerates to the latter estimators if 5 & 0 or 8 t 1.2 Specifically, the estimator partitions the sample into blocks of equal length & each (which will later be set to
A n according to the mixing time of the Markov chain S Let l denote the number of blocks respectively, so that ke = n. Let I+ = [(i - 1)k- + 1, (i - 1)k- + 2, 2.... ikk denote the indices of the ith block. Further, let (Ri) be an i.i.d. Rademacher sequence (R, Uniform (1,, and let
1 K
X, = Ra
x,= 8,0, +2
(8)
JEZ.
denote the average of the samples in the ith block (randomized with sign R2), where
3 = R K Σ S
(9)
JEI,
is the gain (average of the signs) of the ith block, and
Z, = R,
1
Σ
Z3
N
(0.
(0. 1
(10)
T
jEZ,
5

---

is the average noise of the ith block. Due to the sign randomization, it holds that (St is an i..d.
sequence. Since |elg is also an i..dd sequence, then is (Xx) For notational simplicity we will omit the block index of a generic block. For block length k; we denote by
Ek = ETS
S
(11)
the second moment of the gain S. Note that & E [ 1] for any 5 E [0, 2), and, in particular, it always positive. For sequence of samples X1 .XI....,xA)) we define by Σn, (XFP the empirical covariance matrix of the averaged samples over blocks (Xstielg. that
En = Σ X
(12)
i=1
whose population average is En, (0.), where
1
(n,) = EX X EnO.O + Kla.
(13)
We note that is the principal component of ,,, (0), that is, Amax ( Ex 10 and the corresponding cigenvector is Umax (En,+(0)) = 6. We thus consider the following estimator for 0.. from sequence Xf". and with block length of lt
1 Ex
(Amma(Enns(X))) 11 Umax (En.a(X3))
oco (XT
V
(14)
The estimator thus constructed from two types of averages: First, coherent average of the samples at each block, obtain É block-samples X, with gain S, and noise variance reduced by factor of k. Second, an incoherent average of the "square" of the block-samples X;X; which resolves the remaining sign ambiguity between blocks. This balance two extreme cases: If 8 = 0, then this reduces the problem to the GLM (with a sign ambiguity) and = n is an optimal choice. If 8 = 5 then this reduces the problem to the GMM, in which coherent averaging is rate optimal. Generally, the optimal choice of the block length k is proportional to the mixing time of the Markov chain ( This choice assures that the random gain is 1 with (constant) high probability. In fact, an elementary, yet crucial, part of the analysis establishes that the random gain has constant variance for this choice of block length (see Lemma D in Appendix B.T). On the other hand, if A (2()). then the random gain 3 will not be #1 (or not even bounded away from zero) with high probability, and such choice is never efficient. Specifically, we consider the estimator in (14) with i g6- The above estimation procedure is depicted in Figure 2 in Appendix B.1
non-beneficial and k = 1
Let us denote
8(n, d,5) =V=V
d
5d
1/4
(15)
which will actually be the global minimax rate.
Theorem 1. Assume that 8 1 and d S n, and set Ô O (XT:; with k 86 Then, there exist numerical constants CD, C1, 02 > such that for every E IRd
p(n, d, d)
|0.115 8(n, d,
E [oss((0,00 (osss 0.)] s co
(16)
n
P..
+ P..
R
3(m, d, s |0011|
and
loss(0, 0.) s c1 llogn)) E losss(0, ( 0w)
(17)
with probability larger than 1 82

---

Theorem D is proved in Appendix B.1 Evidently, Theorem D implies that the upper bound on the minimax rate stated in (7) above holds in low dimension, d ôn, whereas M(n, d, 6, X
MGLM(n, d. 1) holds in high dimension d 2 on F We remark that the condition á > is mild as
otherwise the model (2 essentially equivalent to GLM. See Remark [ Appendix B.T Numerical
validation of the performance of the estimator d (Xf;; k) is shown Appendix F
We next consider an impossibility result. As we have seen, at high dimension, d 2 ön, the minimax error rates achieved are the same for the Gaussian location model, and thus clearly cannot be improved. We thus next focus on the low dimensional regime d S ön.
128 Then the local minimax rate is bounded as Theorem 2. Assume that 2 S d S ön and N d
1/4
1
15
M(n, d, 0) v /log(n)
1
5d
hd
1/4
Sts VO.
(18)
Hence, the minimax rates achieved by the estimator in Theorem D are nearly asymptotically optimal, up to a Vlog(n) factor. The full proof of Theorem 2
together with a summary of the main ideas used
in the proof is presented in Appendix B.2
Remark 3 (Relaxation of the noise distribution assumption). For the sake of clarity of exposition, we have assumed in Theorems] I [and2[taa the noise samples {Z, Ju are i..dd isotropic Gaussians. There are two straightforward relaxations of this assumption. First, our minimax upper bound (Theorem I can be proved to any subGaussian noise distribution, simply because all the concentration bounds for Gaussian random variables used in the proof admit subGaussian analogues. The impossiiillity result (converse, Theorem (2) trivially holds for subGaussian noise since Gaussians are special case of subGaussians. Second, the isotropic assumption can be relaxed to anisotropic noise with known covariance E by simple standardization: If 74- ~ N (Oa, Σ) are i.i.d. for some known Σ > 0, then the estimator will multiply the samples by E- and reduce the problem back to the isotropic setting. After applying the estimator we propose for the isotropic case, the estimator will obtain its final estimate by multiplying its isotropic estimate by 1/2 The loss of the estimator will then be gauged by the Mahalanobis distance, parameterized by Σ. We refer the reader Appendix G for discussion on more challenging directions in which the isotropic Gaussian assumption can be relaxed.
3 Flip probability estimation for a given estimator of 0x
In this section, we consider the problem of estimating whenever 0, is approximately known to be 8,. We propose simple estimator, and then discuss the importance of the accuracy of 6.. We then derive an impossibility result for the matched case, 0; = 0,.
First note that an estimator for 5 can be easily obtained from an estimator for with essentially the same error rate, via å = [1 - p). Thus we focus estimating p. Assume for simplicity that is even. Observing that E. x 11)+1] pl|0.112 propose the following natural estimator for p. which replaces the population average with empirical average:
a/2 2
Poom 0z)
Σ n 1=1
X X2-11
(19)
|00,112
That is, the estimator is based on evaluating the correlation of each of two adjacent samples X2; and X2-11. We first state general bound on the estimation error of this estimator. We then consider the case in which 0, is known, and show how the estimation error is improved in this case.
WWhe ||0.|/ ((n, d, d). the estimator 0e.. k)): in Theorem only achieves a rate 3(n, d, 8) which is larger than the promised rate ||0_]| in (7). However, since the estimator is assumed to know (but not the direction of 0_; common formulation in high-dimensional statistics), then it can output the zero vector. It then incurs loss |@]] for any 0. e IRd matching the promised rate when [|0-]| (mm, d, 8). To summarize, for any value of t, the minimax rate is achieved by the minimum rate of d.n (XT: k) and (X))) = 0.
7

---

Theorem 4. Assume that d S n. Let 02 E R and let 0g be an estimate of 0.. Set P = Peon (XT; 0z)
and 8 (1 P). Then, holds with probability 1
that 1
1 l0 pl |10_11 11:11 (6)
8
d
8
(20)
2
|0,1
n2
|10.11
n2
The proof of Theorem appears in Appendix bound, suitable to its usage later in Section A bound the expectation of the error can be obtained by the standard method of integrating tails.
Note that Theorem staates high-probability
The effect of knowledge of O. If O. known up sign, i.e., 02 =0., then for the purpose of p (or equivalently 5) estimation, the model (2) can be reduced to one-dimensional model by rotational invariance of isotropic Gaussian (See additional details in Appendix C.2). It then immediately follows from Theorem 4 that:
Corollary Assume that S n, 110.15 and 0g +0.. Let UP defined in as Uş == ||0_1|-5; + W; where W; N (0, 1) i.idd., e = Pcor (UT; 04) and 1 (1 -p). Then it holds with probubility 1 & that
00 8 8 = 2
pl S
18 18l) 00,1
V
1
(21)
n
Numerical validation of the performance of the estimator &com (XT: ) Pcom (X::
(2)) in the
mismatched (Theorem 4 and matched (Corollary 5) cases is provided in Appendix F
We next consider an impossibility lower bound.
Proposition 6. Suppose that 8g = 8, and ||0, 1|S
Then V2'
inf sup B(UT) 6c
B[lō 8(U 32'n''
(22)
where the infimum is over any estimator ((UT) based the model U. 110.111, + W, where each W; is i..dd 1).
The proof of Proposition olis presented in Appendix C.2 According Corollary 5 and Proposition 6. in estimating 8 with a known 0,, though the dependence O of the minimax error rate on the sample size is shown to be nearly optimal, it is unclear what the optimal dependence the signal strength should be. This is left as an interesting open question and we discuss the challenges associated with this problem in Appendix
4 Mean estimation under an unknown flip probability
As we have seen, if an estimator for 0, knows the value of 8, and if both 5 < 2 and S on hold, then the estimator can achieve improved error rates over the GMM case (ō = 1)) In this section, we assume that both 6, and are unknown, and so the estimator is required estimate in order to use this knowledge for an estimator of f.. We propose an estimation procedure of three steps based on sample splitting of 3n samples. We mention at the outset that the regime in which improvement is possible will be for low signal strength ||0,|| 1 (low separation between the components), and up to a dimension which depends on Of course the estimation procedure does not know (0., 5) in advance, and so it is required to identify if (0., 8) are in this regime during its operation.
We now begin with an overview of the steps of the estimation algorithm. At Step A, the algorithm estimates 0, based on X assuming a Gaussian mixture model (5 }) to obtain an estimate ((A), Then, based on [| |]. the algorithm decides whether improvement is potentially possible had 8 was known. There are two cases. The first case is that [|0())]] is too low, and then its estimate is not sufficiently accurate to be used in the next steps. Essentially, this happens when the norm is below the global minimax rate 2/4 and the estimation error the norm on the same scale as the norm of ||0_]] ||. A trivial estimator of i = 0 is then optimal in terms of error rates. It can be already noted
8

---

at this step that while the global minimax rate for the known case is (44 here the algorithm already stops and estimates The second case is that ||A_| is larger than a constant. In this case, the estimation based on GMM
even if just ||@~11:. (,)1/4 leading larger global minimax rate.
already achieves the optimal parametric O(y 4) error rate of the Gaussian location model, and so no further estimation steps are necessary. Otherwise, an improvement in the estimation is possible. The algorithm proceeds to Step B, and uses X to obtain an estimate j(B) based on the mismatched 0: = ((A), Then, based on the estimate 8(B) the algorithm decides whether the accuracy of 8(B) is sufficient be used in an refined estimation of 0.. If the accuracy of ((B) not good enough, then the algorithm outputs the estimate from Step A, that 0(4), Otherwise, proceeds to Step C, in which 0. is re-estimated using X x based on a mismatched choice of k; that is k > gem5 instead
of k 86 Intuitively, the estimated value j(B) should be larger than ò so the resulting block size k 3(B) will be such that the gain in the block is still close to 1 with high probability. On the other hand, it is desired that ((B) will be the same scale å so that the estimation rate (304) (see also 7 which now essentially holds with ((B) instead of 5 would be as small as possible. Thus, if the algorithm has assured in Step B that (P) x 8, then at Step C it will achieve the error rate indicated in (304).
Algorithm 1 Mean estimation for unknown 5
input: Parameters Ng, As > 0 (from (304) 305 307
3n data samples X3 from the model
2: step A: Estimate 0, assuming a Gaussian mixture model:
@(4) doov (XP; k
(23)
3: if [|Ō(-) | 2A. log(n) (g)2/4 then
4: return 0 = 0
No further improvement can be guaranteed
5: else if ||0(A)||2 then
6: return 0 = ((A)
b No further improvement is possible
7: end if
8: step B: Estimate 8 assuming mismatched mean value ((A);
((B) = 8evor (2271 ((A))
(24)
9: if 8(B) S 64Agdg log(n) T 2
V
then
10: return 0 = ((4)
No further improvement can be guaranteed
11: end if
12: step C: Estimate 0, assuming a mismatched flip probability }(B);
( = :cn
X2nt1ik=
X 3n
1
(25)
168(B)
13: return Ô= ((C).
The formal description of the estimation algorithm is provided in Algorithm We remark that refining the estimation of 8 can be easily incorporated as fourth step of this algorithm. but do not present this in order to keep the statement of the result simple. The error of the estimator output by Algorithm Tis as follows:
Theorem There exist constants C1, 02 2 0 and No, As 2 1 such that if S 423 (m) then the output & of Algorithm satisfies for any 0, Ed, with probability 1 1- O(4):

---

If d 642323log (n) 8'n then
1|-111-
110.15 lS Ao log(n)
(#)
( 1/4
Ao log(()) ( 1/4 S 110.115 V8Asd0 log(n) (z4h) 1/4
loss(0, 0.) $ c1 log n
| V
70
(26)
6d
V8Aa2o log(n) ( 6
1/4
S 110.11 v8
110_11
n
110.12 v8
If 64x22, Ing 8'n then
11.115 do log(n) (+) (4) 1/4
110111
loss(0,0.) 0.) S 02 log
Ao log(() ( 1/1 S 10.115 V8hado log(n) (g (27)
(14
6._1
|1..12 VA log(n) (aat)) 1/4
Theorem implies that up to logarithmic factors, the error rates of the known á case are recovered for low enough dimension d S 8'nn and |10. 112 (5=Ta 1/4 The analysis of Algorithm appears in Appendix D Numerical validation of the performance of Algorithm can be found in Appendix
The impact of unknown 5 on the estimation error of 8, Comparing Theorems 2 (known 6) and (unknown d) reveals the deterioration in the estimation of O, due to the lack of knowledge of from the three aspects mentioned in Section 1.3 (ignoring logarithmic factors): First, the global minimax rate is O 1/4) for the GMM, instead of the rate O //4 for the Markov model case with known
A instead of the lower Second, at the regime (4)1/4 < 115 ( (1/4 the error rate O |e_ (
Third, the algorithm is only effective when the dimension is as low as d S 8*n, For higher dimensions, the rates of the GMM are achieved, which be achieved even without the knowledge of ó.
0 18_1
6d
Conclusion and future work
In this paper, we have considered an elementary, yet fundamental, nigh-dimensional model with memory. We have obtained sharp bound on the minimax rate of estimation in case the underlying statistical dependency (flip probability) is known, and proposed a three-step estimation algorithm when it is unknown. This has revealed the gains possible in estimation rates due to the memory between the samples, and smoothly interpolated between the extreme cases of GL.M and GMM. An interesting open problem is to either characterize the optimality of the algorithm or improving the unknown 8 case, which requires understanding optimal estimation of the flip probability.
Naturally, as the model considered in this paper is basic, there is an ample of possibilities to generalize this model. These include, larger number of components in the mixture, statistical dependency with a more complicated graphical structure between the data samples, existence of nuisance parameters such as the noise variance, sharp sattlessmmmmemeeeeiiiiiie iteratiio analysis of specific practical algorithms such as Baum- Baum-Welch, location-scale model with anisotropic noise, heavy-taile noise, and so on.
Acknowledgments and Disclosure of Funding
Part of this work was done when YZ was a postdoc at Technion where he received funding from the European Union's Horizon 2020 research and innovation programme under grant agreement No Tradeofff. The work of of NW was supported in part by the Israel Science Foundation (ISF) under Grant 1782/22. NW is grateful to Guy Bresler for introducing him this problem, for the initial ideas that led to this research, and for many helpful discussions on the topic.
10

---

References
Dhroova Aiylam. Parameter estimation in HMMs with guaranteed convergence. Master's 's thesis, Massachusetts Institute of Technology, 2018.
Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. The Journal of Machine Learning Research, 15(1):2773-2832,22) 2014.
Sivaraman Balakrishnan, Martin J. Wainwright, and Bin Yu. Statistical guarantees for the EM algorithm: From population to sample-based analysis. The Annals of Statistics, 45(1):77-120,, 2017.
Leonard H. Baum, Ted Petrie, George Soules, and Norman Weiss. A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains. The Annals of Mathematical Statistics, 1141)1164-171, 1970.
Marianne Bertrand, Erzo FP Luttmer, and Sendhil Mullainathan. Network effects and welfare cultures. The quarterly journal of economics, 1 11(3))1019-1055, 2000.
N. M. Blachman and L. Few. Multiple packing spherical caps. Mathematika, 10:84 1884-88,10 1963. ISSN 0025-5793. doi: 10.1 10.112//0025599300003222
URI. https://doi.onrr org/10ggg/oo 10/00000000 1112/
50025579300003405
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
Guy Bresler, Frederic Koehler, and Ankur Moitra. Learning restricted boltzmann machines via influence maximization. In Proceedings of the S1st Annual ACM SIGACT Symposium Theory of Computing, pages 228-839,27 2019.
Guy Bresler, Prateek Jain, Dheeraj Nagaraj, Praneeth Netrapalli, and Xian Wu. Least squares regression with markovian data: Fundamental limits and algorithms. Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781713829546.
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria, Prasad Raghavendra, and Nilesh Tripuraneni. Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 601-609. ACM, 2020. doi: 10.1145/3357113.3888333
BRLLhttps://doo org/ 10. 33347333333333333333 3384329
Nicholas A Christakis and James H Fowler. Social contagion theory: examining dynamic social networks and human behavior. Statistics in medicine, 52(4))556-577,200 2013.
T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley-Interscience, 2006. ISBN 0471241954.
Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Siddhartha Jayanti. Learning from weakly dependent data under dobrushin's 's condition. CoRR, Abs/1906.092447, 2019. URLhttp
7/arxiv. hwtp://.g///bbaaaeeeoo/o
09247
Constantinos Daskalakis, Nishanth Dikkala, and Ioannis Panageas. Regression from dependent observations. In - of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 88 1-1-889, ACM, New York, 2019.
Natalie Doss, Yihong Wu. Pengkun Yang, and Harrison H Zhou. Optimal estimation of high- dimensional location gaussian mixtures. arXiv preprint arXiv:2002.0588/ 2020.
Esther Duflo and Emmanuel Saez. The role of information and social interactions in retirement plan decisions: Evidence from a randomized experiment. The Quarterly journal of economics, 118(3): 815-842, 2003.
11

---

Raaz Dwivedi, nhat Ho, Koulik Khamaru, Martin J Wainwright, and Michael I Jordan. Theoretical guarantees for em under misspecified gaussian mixture models. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: https://pree http:///eceeeee........ wew.snn.urip...o. wtt.c//pppp///////.... 2cc2177864226222228111fffffff
Paper.
Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Martin J. Wainwright, Michael I. Jordan, and Bin Yu. Challenges with EM in application to weakly identifiable mixture models. CoRR, abs/1992.00014 2019. URL http://arxiv .rgg 0tbb//990..000
Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Martin Wainwright, Michael Jordan, and Bin Yu. Sharp analysis of expectation- pnteectatioo-mmaiiizztttii maximization for weakly identifiable models. In International Conference Artificial Intelligence and Statistics, pages 1866-1876 PMLR, 2020a.
Raaz Dwivedi, Nhat Ho, Koulik Khamaru, Martin J Wainwright, Michael I Jordan, and Bin Yu. Singularity, misspecification and the convergence rate of EM. The Annals of Statisties, 48(6): 3161-3182, 2020b.
Yariv Ephraim and Neri Merhav. Hidden Markov processes. IEEE Transactions on information theory, 48(6):1518-1166) 2002.
Thomas S. Ferguson. An inconsistent maximum likelihood estimate. J. Amer. Statist. Assoc. 77G80):831 834, 1982. ISSN 0162-1459, URL http::/links. http://iinsssssstorrr...o wwt.:jssttoorooiiiii... wrggssicissictii 0162-14580 (198212)
AIMLE-.. C0 Yčorigin=MSi
Edward Glaeser, Bruce Sacerdote, and Jose Scheinkman. Crime and social interactions. The Quarterly journal of economics, 11((2)5577-548 1996.
László Györfi, Michael Kohler, Adam Krzyžak, and Harro Walk. A distributionffre theory of nonparametric regression. Springer Series Statistics, Springer- Verlag, New York, 2002. ISBN 0-387-95441-4 doi: 10. 10.1007/b97848. URL https: http:///oooorr/1/////// 10. 1007 1007/b97848
Moritz Hardt and Eric Price. Tight bounds for learning mixture of two Gaussians. In Proceedings of the seveet annual ACM symposium on Theory of computing, pages 753-760. ACM, 2015.
Samuel B. Hopkins. Mean estimation with aab-Gaussian rates in polynomial time. The Annals of Statistics, 18(2):1193 1213, 2020. doi: 10. 10.1214/1--ASS1843 URL httpp:://oi..oooeeeeee org/10 1144199-AS1888
Samuel B. Hopkins, Jerry Li, and Fred Zhang. Robust and heavy-tailed mean estimation made simple. via regret minimization. In NeurlPS, 2020. URL ittp:/ttps// cc/pper
http:/hahh//aa2//1
html
Daniel J. Hsu and Sham M. Kakade. Learning mixtures of spherical gaussians: moment methods and spectral decompositions. In Robert D. Kleinberg, editor, Innovations in Theoretical Computer Science, ITCS '13 Berkeley, CA, USA, Jamuary 9-12, 2013, pages 11 11-20. ACM, 2013. doi: 10.1145/2422436.2424441 URL pttpss/////o
1145/2422436. 2422433
Chi Jin, Yuchen Zhang, Sivaraman Balakrishnan, Martin J. Wainwright, and Michael I. Jordan. Local maxima in the likelihood of Gaussian mixture models: Structural results and algorithmic consequences. In Advances in neural information processing systems, pages 4116-4124, 2016.
lain M. Johnstone. Function estimation and Gaussian sequence models. Unpublished manuscript, 2 (5.3):2, 2002.
Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant. Efficiently learning mixtures of two gaussians. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 553-562, 2010.
Vardis Kandiros, Yuval Dagan, Nishanth Dikkala, Surbhi Goel, and Constantinos Daskalakis. Statistical estimation from dependent data. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5279-5278. PMLR, 18-24 Jul 2021. htI.sttss: hnttps::/pprceeddiiit
mlr, www.ppess/v3//eeeeese http////////annnnn21l.aa html
12

---

Jason M. Klusowski and W.D. Brinda. Statistical guarantees for estimating the centers of a two-
component Gaussian mixture by EM. arXiv preprint arXiv:1608.02280/ 2016.
Bruce G. Lindsay. Mixture models: Theory, geometry, and applications. Ims, 1995.
David J. C. MacKay. Information theory, inference and learning algorithms. Cambridge University Press, New York, 2003. ISBN 0-521-6422 -64298-1.
Geoffrey J McLachlan, Sharon X Lee, and Suren Rathnayake. Finite mixture models. Annual review of statistics and its application, 6:355-378, 2019.
Ankur Moitra and Gregory Valiant. Settling the polynomial learnability of mixtures of gaussians. In 2010 IEEE 51 Annual Symposium on Foundations of Computer Science, pages 93-102, IEEE, 2010.
Tongzheng Ren, Fuheng Cui, Sujay Sanghavi, and Nhat Ho. Beyond EM algorithm on over- specified two-component location-scale gaussian mixtures. CoRR, abs/2205. 1078. 2022. doi: 10.485500/rXXi:2225..11
WtLLhttps:/// http://ooo..ogg///// org/10 111./1...85////iii/// 2205. 11078
Phillippe Rigollet and Van-Christian Hütter. High dimensional statistics. Lecture notes for course 18$997, 2019.
Bruce Sacerdote. Peer effects with random assignment: Results for dartmouth roommates. The Quarterly journal of economics, 116(2))681-704 2001.
Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Publishing Company, Incorporated, 2008. ISBN 0387790519.
Ramon van Handel. Hidden Markov models. Unpublished lecture notes, 2008
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge University Press, 2018.
Martin J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48.
Cambridge University Press, 2019.
Martin J. Wainwright and Michael I. Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends Machine Learning, 1(1 1(1-2):1-305, 2008. ISSN 1935-8237. doi: 10.1561/22000000001
hRLpttp: //dxt:://xx.r doi org/ 10. 1561/2200000000
Nir Weinberger and Guy Bresler. The em algorithm adaptively-optimal for unbalanced symmetric gaussian mixtures. Journal of Machine Learning Research, 23(103):1-79, 2022. URL URLp
hwwnnl..org/ppperseeeee wttpeers//vv/21100 html
Yihong Wu. Lecture notes on information- theoretic methods for high-dimensional statistics. Lecture Notes for ECE598YW (UIUC), 16, 2017.
Yihong Wu and Pengkun Yang. Optimal estimation of Gaussian mixtures via denoised method of moments. The Annals of Statistics, 48(4):1981-2007, 2020.
Yihong Wu and Harrison H. Zhou. Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in o(vn) iterations. arXiv preprint arXiv: /908. 10935, 2019.
Xu, Daniel J. Hsu, and Arian Maleki. Global analysis of expectation maximization for mixtures of two Gaussians. In Advances in Neural Information Processing Systems, pages 2676-2684, 2016.
Bowei Yan, Mingzhang Yin, and Purnamrita Sarkar. Convergence of gradient EM on multi-component mixture of Gaussians. In Advances in Neural Information Processing Systems, pages 2017.
Fanny Yang, Sivaraman Balakrishnan, and Martin J. Wainwright. Statistical and computational guarantees for the Haum-Welch algorithm. In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 658-665. IEEE, 2015.
13

---

Yuhong Yang and Andrew Barron. Information-theorett determination of minimax rates of convergence. Annals of Statistics, pages 1564-1599, 1999.
Ruofei Zhao, Yuanzhi Li, and Yuekai Sun. Statistical convergence of the EM algorithm on Gaussian mixture models. arXiv preprint arXiv:1810.04090, 2018.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or URL)? [N/A] (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "ok2GPY4Los9", "reviewer": "Reviewer_KdtU", "summary": "The authors study an interpolation between Gaussian location models and Gaussian mixture models, in which samples are Gaussian noise-corrupted versions of a sequence in $\\\\{-1, 1\\\\}^n$ with each sequence element being the flipping of the previous one with probability $\\delta \\in [0, \\frac12]$. They characterise the minimax risk under Euclidean distance error to the near of $\\theta_*$ and $-\\theta_*$. They thus generalize known results for the GLM and GMM, extending these results to estimators and risk parameterized by $\\delta$, with the GLM and GMM at the extremes. Their ultimate result is to provide a three-step estimator to estimate $\\theta_*$ when $\\delta$ is not known, and to provide asymptotic results for its loss. This involves estimators for $\\theta_*$ under known $\\delta$, and for $\\delta$ under approximately known $\\theta_*$, for which they provide both achievability and lower bounds on worst-case risk within a logarithmic factor of each other.", "questions": "1. What motivated or inspired the problem? I'm fairly open to different sorts of motivations; there need not necessarily be concrete practical applications. But it would be good to have an understanding of where this fits into statistical learning, and/or any broader open questions that this contributes towards, and/or any actual or imagined applications. The fact that it is an interpolation between two known extremes doesn't by itself make it interesting: what sorts of questions fall in between the two extremes?\n\n2. I was a bit confused about the argument for why $\\overline{X}_i$ is i.i.d. Equation (8) says that $\\overline{X}_i$ is equal to $\\overline{S}_i \\theta^* + \\overline{Z}_i$ only in distribution. I think this is correct, because $R_i$ is independently drawn, so would break sure equality but maintain equality in distribution. But then the argument for $\\overline{X}_i$ being i.i.d. reasons via $\\overline{S}_i$ and $\\overline{Z}_i$. I don't this carries over an equality in distribution, unless $\\overset{d}{=}$ was intended to indicate equality of the joint distribution of the entire sequence, as opposed to of each element. But also, I don't think it needs to, because I think $\\overline{X}_i = R_i \\cdot \\left[ \\overline{S}_i \\theta^* + \\overline{Z}_i \\right]$, and since $R_i$ is also i.i.d., that makes $\\overline{X}_i$ i.i.d., right? Please feel free to correct me; any clarification would be appreciated.\n\nTypos/grammar:\n- 95: \"allows to achieve\" should be \"allows us to achieve\" (\"to allow\" takes either object + infinitive, or a noun phrase, but not just an infinitive)\n- 162: I think Bachmann is spelled with two n's\n- 204: \"blcok\"\n- 205: \"elemnatary\"\n- 206: \"crucuial\"", "limitations": "I think the authors were reasonably upfront about questions that were left open. The work was entirely theoretical so I don't expect any societal impact, though I'd still encourage the authors to explain what motivates the problem.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I thought the technical elements of the paper were sound. The problem and its relationship to prior results were clear, there was no ambiguity in notation, and all concepts were explained with suitable precision. I haven't had a chance to walk through the proofs in the appendices step by step, but I read through the proof of Theorem 1 and the approach, based on concentration bounds on a decomposition of the loss, seems sound to me.\n\nWhere I think the paper could do with improvement is in the contextualization it provides for the problem and results. Essentially none is given—the authors set up the problem straight away, and the only context given is in Section 1.2, where they state prior results for the GLM and GMM. Why is this problem interesting or significant? Does it have potential applications, or is it inspired indirectly by any potential applications or open questions, or does it get us a step closer to understanding some larger problem? I basically think the lack of contextualization or motivation substantially holds back this paper, and it would be a reasonably strong paper if material was added to address its significance.\n\n-----------------------------\n\n_Edit, 7 August 2022, after author revision:_\n- _Increased presentation score to 3 (was 2)_\n- _Increased contribution score to 3 (was 2)_\n- _Increased overall rating to 6 (was 4)_", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YAfcjBTVfv8", "reviewer": "Reviewer_fjjw", "summary": "The paper considers high-dimensional mean estimation problem over hidden Markov models (HMMs). It considers whether and to what extent the memory between samples can benefit the estimation problem. Specifically, given a Markov chain S^n with fixed flip probability \\delta and correlation \\rho between adjacent samples, the goal is to infer the parameter \\theta* of the model. \n\nIt studies three different memory cases: (i) \\delta = 0, (ii) \\delta = 1/2, and (iii) \\delta\\in(0,1/2), where (i) corresponds to infinite memory, (ii) to no memory, and (iii) to simple versions of HMMs. When \\delta is known, the authors show that a principal component computation based estimator achieves asymptotically optimal rate. When \\delta is unknown, the authors propose an algorithm that first obtains a gross estimate of \\theta by assuming the worst memory case, i.e. (iii); then estimates \\delta using the estimate of \\theta; at last, it refines the estimate of \\theta using the new \\delta. It shows that the information of knowing \\delta plays a role in the performance of the estimator.\n", "questions": "In Algorithm 1, step B relies on the estimate obtained from Step A. I wonder how good the estimate of \\theta should be to facilitate the following steps? Do more samples in Step A essentially help? How strong is the assumption of a Gaussian distribution, and can it be replaced with weaker assumptions?\n", "limitations": "The authors may address the limitation of the Gaussian assumption.\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors were able to demonstrate how memory between the samples affect the rate of estimation. The paper shows sharp bounds on error rates in both low and high-dimensional scenarios. The paper is generally well written. However, some parts of the paper are less clear to the reader.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RKG6GFv5PU2", "reviewer": "Reviewer_nbjp", "summary": "This paper is about the problem of estimating the mean in high-dimensional binary Markov Gaussian mixture models. If $\\delta$ denotes the associated flip probability of the stationary homogeneous Markov chain (and is known), the authors explore the regime of $\\delta$ between the previously studied values of 0 and ½. Moreover, in the other direction, they show that given the sampled (to be estimated) vector $\\theta$, one can compute some rough estimate on the parameter $\\delta$. These two results nicely combine into a method for estimating \\theta even if \\delta is not known.\n", "questions": "Would it make sense to choose the $S_i$ values from some other distribution?\n\nPage 2: Lines 55–56 are not justified, and there is no citation.\n\n\nPage 5: Could you please elaborate on the second equality of Equation (13)?\n\nPage 6:\n\nLine 204: “blcok” should be “block.”\n\nLine 205: “elemantary” should be “elementary.”\n\nLine 206: “crucuial” should be “crucial.”\n\nFootnote 2: I do not understand the last sentence.\n\nPage 7: Please explain why Equation (19) yields a natural estimator.\n\nPage 8: Please further explain lines 280–283.\n\nPage 9: Can you please elaborate on the claims of “The impact of lack of knowledge of $\\delta$?", "limitations": "I did not see an explicit section addressing this. However, this may not be relevant to this paper.  ", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: The originality of this paper mostly stems from its ambitious goal, namely, to understand the problem of mean estimation in high-dimensional binary Markov Gaussian mixture models for the case where the flip probability $\\delta$ can be any value in the interval [0,½]. Prior to this work, only the cases $\\delta = 0,½$ had been studied.\n\nQuality: The quality of the paper is good. It is well written and the results seem strong.\n\nClarity: The presentation of the paper and writing are generally clear. Section 1.3 (Contributions) could be made a bit more reader-friendly.\n\nSignificance: The work is significant: see Originality above. Another non-trivial reason that this paper is significant is about the techniques employed therein; in particular the use of a principal component of a suitable covariance matrix that is used in the aforementioned smooth interpolation between $\\delta$ = 0 and $\\delta$ = ½. I found that quite interesting!\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "24hh7f15xMQ", "reviewer": "Reviewer_9nBR", "summary": "This work focuses on obtaining minimax rates in high-dimensional Binary Markov Gaussian Models.  A random sign is multiplied to the sample and this sign is generated by Markovian coin flips w.p $\\delta$. The true distribution is a high dimensional Gaussian distribution with identity covariance. Thus this model interpolates between a standard mean estimation problem for Gaussians when $\\delta=0$ and when $\\delta=1/2$, this is a GMM with two components. The authors provide an estimator that needs to account for the Markovian samples to obtain near optimal minimax error rates (upto log factors) when $\\delta$ is known which degenerates to the known minimax rates when $\\delta = 0$ or $\\delta=1/2$.  Additionally, when $\\delta$ is unknown they provide an upper bound of the minimax rates.", "questions": "See weaknesses above.", "limitations": "Yes, the limitations are somewhat adequately addressed. Please see weaknesses for some clarifications.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis is one of the few recent works that study estimation under dependent samples, with Markovian dependency specifically. The model is interesting as it interpolates between a standard Gaussian location model and Gaussian Mixture model simultaneously. They obtain near optimal minimax rates from the estimators. The estimate relies on carefully splitting the data into batches of appropriate size, so that the local estimate in each batch forms an i.i.d sequence of estimates.\n\nWeaknesses:\n\n1) The main argument relies on the mixing time of the Markov chain that generates the signs and each batch length is decided based on that. It would be good to see why this $\\Theta(1/\\delta)$ for the sake of completion.  [Nagaraj et al. 2020], apply a variant of SGD for the least squares regression problem with Markovian data and that relies on the mixing time of the Markov chain. Their argument relies on wasting certain amount of data and beyond which there is an approximate. i.i.d behavior in the samples and the errors due to correlation are taken care of.  I am unable to see this argument here and it feels less convincing as to why the data is fully i.i.d after splitting it into batches according to the Markov chain mixing time and the errors due to some residual correlation doesnt seem to appear. Also it is surprising that there is no data wastage. Even if you assume ergodicity, you might have to discard some amount of samples initially. I hope this is clarified better.\n\n2) The results seem to apply only for isotropic Gaussians.\n\nUpdate:\nAfter the rebuttal, I think the authors have clarified my questions convincingly and I am inclined to increase my score.\nReferences :\n\nNagaraj, Dheeraj, et al. \"Least squares regression with markovian data: Fundamental limits and algorithms.\" Advances in neural information processing systems 33 (2020): 16666-16676.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept