Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

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.

Quality: The quality of the paper is good. It is well written and the results seem strong.

Clarity: The presentation of the paper and writing are generally clear. Section 1.3 (Contributions) could be made a bit more reader-friendly.

Significance: 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!

questions: Would it make sense to choose the $S_i$ values from some other distribution?

Page 2: Lines 55–56 are not justified, and there is no citation.


Page 5: Could you please elaborate on the second equality of Equation (13)?

Page 6:

Line 204: “blcok” should be “block.”

Line 205: “elemantary” should be “elementary.”

Line 206: “crucuial” should be “crucial.”

Footnote 2: I do not understand the last sentence.

Page 7: Please explain why Equation (19) yields a natural estimator.

Page 8: Please further explain lines 280–283.

Page 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.

Where 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.

-----------------------------

_Edit, 7 August 2022, after author revision:_
- _Increased presentation score to 3 (was 2)_
- _Increased contribution score to 3 (was 2)_
- _Increased overall rating to 6 (was 4)_
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?

2. 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.

Typos/grammar:
- 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)
- 162: I think Bachmann is spelled with two n's
- 204: "blcok"
- 205: "elemnatary"
- 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:

This 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.

Weaknesses:

1) 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.

2) The results seem to apply only for isotropic Gaussians.

Update:
After the rebuttal, I think the authors have clarified my questions convincingly and I am inclined to increase my score.
References :

Nagaraj, Dheeraj, et al. "Least squares regression with markovian data: Fundamental limits and algorithms." Advances in neural information processing systems 33 (2020): 16666-16676.
questions: See weaknesses above.
limitations: Yes, the limitations are somewhat adequately addressed. Please see weaknesses for some clarifications.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 

It 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.

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.

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?

limitations: The authors may address the limitation of the Gaussian assumption.
review_title: null

Meta-review: metareview: The paper addresses the problem of high-dimensional statistical inference from dependent samples. This is a recently emerging area, and the authors establish nearly tight minimax error rate bounds for a basic statistical model (gaussian hidden markov model). 

The reviewers appreciated the technical strength of the paper, but there were some questions about the framing and context of the problem. The authors clarified these issues suitably in their rebuttal, clearing the way for acceptance.
confidence: Certain
Decision: Accept