Learning Overcomplete HMMs
We study the problem of learning overcomplete HMMs-those that have many hidden states but a small output alphabet. Despite having significant practical importance, such HMMs are poorly understood with no known positive or negative results for efficient learning. In this paper, we present several new results-both positive and negative-which help define the boundaries between the tractable and intractable settings. Specifically, we show positive results for a large subclass of HMMs whose transition matrices are sparse, well-conditioned, and have small probability mass on short cycles. On the other hand, we show that learning is impossible given only a polynomial number of samples for HMMs with a small output alphabet and whose transition matrices are random regular graphs with large degree. We also discuss these results in the context of learning HMMs which can capture long-term dependencies.
The paper studies the learnability of HMMs in the setting when the output label size m is smaller than the number of states n. This setting is particularly tricky since the usual full-rank assumption that comes up in tensor decomposition based methods is not valid. This paper gives both algorithms and information-theoretic lower-bounds on the learnability of overcomplete HMMs, which clearly increases our state of understanding. 
1. They show that HMMs with m=polylog(n) even for transition-matrix being a random dense regular graphs, can not be learning using poly(n) samples even when the window size is poly(n). 
2. They show that overcomplete HMMs can be learned efficiently with window size O(log_m n), under some additional four conditions (well-conditioned-ness of T, no-short-cycles, sparsity of graph given by T and random sparse output distributions)
	
Positives:
1. The lower bound is interesting and surprisingly strong. This is unlike the parity-based lower bounds in Mossel-Roch which are more computational by nature, and more similar to moment-based identifiability lower bounds known for Gaussian mixtures and multiview models (see Rabani-Swamy-Schulman). 
2. This paper tries to understand in depth the effect of the structure of the transition matrix on learnability in the overcomplete setting. 
3. The techniques developed in this paper are new and significantly depart from previous works. For instance, the algorithmic result using tensor decompositions departs significantly from previous techniques in analyzing the Khatri-Rao (KR) product. Analyzing overcomplete tensor decompositions and these KR products are challenging, and the only non-generic analysis I am aware of (by Bhaskara et al. for smoothed analysis) can not be used here since the different tensor modes are dependent. At the heart of this argument is an interesting coupling argument that shows that for any two different starting states, the random walk distributions after O(log_m n) steps will be significantly different if the observation matrices are random. This crucially depends on the well-conditioned-ness of T and no-short-cycle condition which they argue is needed for identifiability. 
4. I like the discussion of assumptions section 2.4; while the paper assumes four conditions, and they give qualitative reasons for why most of them are necessary. 
Negatives: 
1. The proofs are fairly dense (especially Theorem 1 , Lemma 3) and the error analysis is hand-wavy at places . Though I have no reason to suspect the correctness, it would be good to improve the readability of these proofs. 
2. It is not clear why some of the conditions are necessary. For instance, the random sparse support assumption seems stronger than necessary. Similarly, while the lower bound example in Proposition 1 explains why an example with just short cycles is not identifiable, this doesn't explain why there should be no short-cycles in a connected, well-conditioned T.   
	
Summary: Overall, the paper presents a nice collection of results  that significantly improves our understanding on overcomplete HMMs. I think the techniques developed here may be of independent interest as well. I think the paper is easily above the bar. 
Comments:
The identifiability results for HMMs using O(log_m n ) should also be attributed to Allman-Mathias-Rhodes'2010. They already show that the necessary conditions are true in a generic sense, and they introduced the algorithm based on tensor decompositions. 
Typo in Section 2.2: "The techniques of Bhaskara et al. can be applied.." --> ".. can not be applied ..."