Abstract
In unsupervised learning, the method of moments provides a powerful framework for discovering hidden structures by decomposing high-dimensional tensors. However, the classical theoretical foundation—Kruskal's theorem—guarantees uniqueness only for exact tensors, failing to account for the sampling noise inherent in empirical data. This paper presents a robust version of Kruskal's theorem, demonstrating that small perturbations in a tensor lead to only polynomially bounded changes in its decomposition. By employing a novel combinatorial approach involving sunflower set systems, the authors bypass the exponential error accumulation typical of algebraic proofs. These results establish that the parameters of latent variable models, such as Hidden Markov Models and topic models, can be learned with polynomial sample complexity even in overcomplete regimes where the number of hidden states exceeds the observation dimension.
Introduction
The method of moments is a cornerstone of statistical estimation, allowing researchers to recover the underlying parameters of a model by analyzing empirical statistics like means, variances, and higher-order correlations. These statistics are often represented as tensors—multi-dimensional arrays that generalize the concept of matrices. The utility of this approach hinges on the "identifiability" of the model: the guarantee that a specific set of moments corresponds to a unique set of parameters.
Kruskal’s theorem has long provided this guarantee for tensor decompositions. It states that under certain conditions regarding the "Kruskal rank" of the component vectors, a tensor decomposition is unique up to permutation and scaling. While mathematically elegant, Kruskal’s original theorem is brittle; it applies only to exact tensors. In practice, researchers work with empirical tensors estimated from finite data, which are inevitably noisy. Furthermore, traditional spectral methods for tensor learning often require the dimension of the data features ($n$) to be at least as large as the number of hidden states ($R$). This paper addresses both the lack of robustness to noise and the limitations of the $n \ge R$ regime.
Overcoming the Robustness Gap
Previous attempts to create a "robust" Kruskal's theorem were hindered by the nature of the mathematical proofs used. Standard algebraic induction tends to accumulate error exponentially at each step, meaning that even a tiny amount of noise in the input tensor could lead to massive uncertainties in the recovered parameters.
To solve this, the authors introduce a Robust Permutation Lemma. Rather than relying on standard algebraic induction, they utilize a combinatorial argument centered on sunflower set systems. A sunflower system is a collection of sets that share a common intersection (the "kernel") while remaining disjoint elsewhere (the "petals"). By framing the uniqueness problem through this combinatorial lens, the authors are able to "lock in" the error bounds at each step, preventing the exponential blow-up and ensuring that the final error scales polynomially with the input noise.
Learning in the Overcomplete Regime
A significant bottleneck in tensor-based learning has been the requirement that the feature dimension $n$ must be greater than or equal to the number of latent components $R$. In many real-world applications, such as speech recognition or complex topic modeling, the number of hidden states can vastly exceed the number of observed dimensions ($R \gg n$).
This paper proves that identifiability is still possible in this "overcomplete" or "degenerate" regime. The authors show that by utilizing higher-order moments (e.g., 4th or 5th-order tensors instead of 3rd-order), one can successfully identify model parameters even when $n$ is a small fraction of $R$. They propose an algorithm that first uses Singular Value Decomposition (SVD) to project the problem into a manageable $O(R)$-dimensional subspace, and then employs an $\epsilon$-net search to find the optimal rank-$R$ components. While the search is exponential in $R$, it remains strictly polynomial in the feature dimension $n$, representing a significant theoretical advancement over previous grid-search methods.
Key Results and Applications
The theoretical breakthroughs in this paper lead to several concrete results for machine learning models:
- Robust Uniqueness: The paper provides the first mathematical proof that if an empirical tensor is $\epsilon$-close to a true tensor, its decomposition is $\epsilon'$-close to the true parameters, where $\epsilon'$ is a polynomial function of $\epsilon$.
- Polynomial Identifiability: The authors demonstrate that a polynomial number of samples—$\text{poly}(n, R)$—is sufficient to learn the parameters of several widely used models, including:
- Multi-view Mixture Models
- Exchangeable Topic Models
- Hidden Markov Models (HMMs)
- Mixtures of Spherical Gaussians
- Algorithmic Efficiency: The proposed algorithm runs in $\exp(R^2 \log(n/\epsilon)) \text{poly}(n)$ time. For models where the number of hidden states $R$ is relatively small or constant, this provides a computationally feasible path to parameter recovery in the overcomplete regime.
Limitations and Future Directions
While the paper marks a major step forward, challenges remain. The algorithm's exponential dependence on $R^2$ limits its application to models with a very large number of hidden states. A truly polynomial-time algorithm (in both $n$ and $R$) for the robust overcomplete regime remains an open problem. Additionally, the theorems rely on the "robust Kruskal rank" condition, which is known to be NP-hard to verify for an arbitrary matrix. Future research may focus on extending these robust proofs to more general distributions, such as mixtures of Gaussians with unknown and varying covariance matrices.
Summary updated