Non-convex Statistical Optimization for Sparse Tensor Graphical Model

Wei Sun, Zhaoran Wang, Han Liu, Guang ChengNeurIPS 2015 · OpenReview

TL;DR

This paper introduces Tlasso (Tensor lasso), a fast alternating minimization algorithm for estimating dependencies in high-dimensional tensor data. Despite the underlying optimization problem being non-convex, the authors prove that Tlasso achieves minimax-optimal convergence rates and—most surprisingly—can consistently recover the underlying network structure from just a single tensor sample.

What Problem Does This Paper Address?

In many modern fields, data doesn't arrive as simple lists (vectors) or tables (matrices), but as multi-dimensional arrays called tensors. Examples include fMRI brain scans (location × time × condition) or recommendation systems (user × item × time).

To understand how these variables interact, researchers use graphical models to estimate "precision matrices," which reveal conditional dependencies. However, tensors present two massive hurdles:

  1. The Curse of Dimensionality: Vectorizing a tensor leads to a massive number of parameters. Estimating them requires a huge number of samples, which are rarely available in real-world scenarios.
  2. Non-Convexity: To make the problem tractable, researchers often assume the total covariance is a "Kronecker product" of smaller matrices (one for each dimension). While this drastically reduces the number of parameters, it turns the math into a notoriously difficult non-convex optimization problem.

Until now, there was a theoretical gap: researchers knew a "good" solution existed in theory, but lacked a provably efficient algorithm guaranteed to find it.

Methods

The authors propose Algorithm 1: Tlasso, which utilizes an alternating minimization strategy:

  • Iterative Updates: The algorithm fixes all precision matrices except one and solves for the remaining matrix using the standard "glasso" (graphical lasso) algorithm. It then cycles through all dimensions of the tensor.
  • Normalization: To handle "identifiability" (the fact that you can scale one matrix up and another down without changing their product), the algorithm normalizes each matrix to have a Frobenius norm of 1.
  • Theoretical Innovation: The authors provide a new theoretical framework separating "population" (idealized) and "sample" (real-world) optimizers. They prove that even though the landscape is non-convex, the algorithm converges to the optimal statistical rate in just a few iterations.

Datasets

The paper primarily validates its findings through rigorous synthetic simulations designed to mimic complex real-world dependencies:

  • Simulation 1: A "triangle graph" structure.
  • Simulation 2: A "four-nearest-neighbor" graph.
  • Scenarios: They tested various dimensions (e.g., $10 \times 10 \times 10$ and $100 \times 5 \times 5$) and sample sizes ($n=10, 50$, and even $n=1$).

While the paper focuses heavily on theory and simulation, it cites the AGEMAP microarray study (gene-tissue-mouse-age) and fMRI datasets as the primary real-world motivations for this work.

Key Insights and Ideas

  • The $n=1$ Miracle: The most striking finding is that for tensors of order 3 or higher (e.g., a 3D cube of data), the algorithm can achieve estimation consistency with only one sample. This is possible because the structural constraints of the tensor allow the algorithm to "borrow" information across different dimensions, effectively increasing the sample size.
  • One-Step Convergence: In the "population" limit (if we had infinite data), the algorithm actually recovers the true precision matrix in exactly one iteration, regardless of the starting point.
  • Minimax Optimality: The authors prove that Tlasso reaches the "minimax-optimal" rate—meaning no other algorithm can do better—even if all other precision matrices were already known.
  • Bridging the Gap: This work provides the missing link between computational efficiency (how fast we can solve it) and statistical consistency (how accurate the answer is) for tensor graphical models.

Key Results

  • Speed: Tlasso is orders of magnitude faster than existing methods. In a $100 \times 5 \times 5$ scenario, Tlasso took 5 seconds, while the previous state-of-the-art (P-MLE) took 500 seconds, and the direct Glasso approach took over an hour.
Computation time comparison across scenarios.
  • Accuracy: Tlasso consistently outperformed or matched the accuracy of much slower iterative methods (P-MLE) and vastly outperformed the "direct" approach that ignores tensor structure.
Estimation error comparison across scenarios.
  • Graph Recovery: The algorithm demonstrated high True Positive Rates (TPR), meaning it successfully identified the "edges" (relationships) in the data even in high-dimensional settings with very few samples.

Limitations and Future Work

  • Initialization: The theory assumes the algorithm starts "close enough" to the truth. While the authors note that random initialization works well in practice, a formal proof for global convergence from any starting point remains an open challenge.
  • Irrepresentability Condition: Some of the stronger results (like max-norm convergence) rely on an "irrepresentability condition," which is a standard but restrictive assumption in Lasso-style problems.
  • Non-convex Regularization: The authors suggest that future work could replace the Lasso penalty with other non-convex penalties (like SCAD or MCP) to eliminate the need for the irrepresentability condition.

Summary updated

Abstract

We consider the estimation of sparse graphical models that characterize the dependency structure of high-dimensional tensor-valued data. To facilitate the estimation of the precision matrix corresponding to each way of the tensor, we assume the data follow a tensor normal distribution whose covariance has a Kronecker product structure. The penalized maximum likelihood estimation of this model involves minimizing a non-convex objective function. In spite of the non-convexity of this estimation problem, we prove that an alternating minimization algorithm, which iteratively estimates each sparse precision matrix while fixing the others, attains an estimator with the optimal statistical rate of convergence as well as consistent graph recovery. Notably, such an estimator achieves estimation consistency with only one tensor sample, which is unobserved in previous work. Our theoretical results are backed by thorough numerical studies.
BibTeX
@inproceedings{sun2015non,
  author = {Wei Sun and Zhaoran Wang and Han Liu and Guang Cheng},
  title = {{Non-convex Statistical Optimization for Sparse Tensor Graphical Model}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=rkWCe_-_bH},
}
Figure