Tensor Graphical Model: Non-Convex Optimization and Statistical Inference

Xiang Lyu, Will Wei Sun, Zhaoran Wang, Han Liu, Jian Yang, Guang Cheng

TL;DR

This paper introduces a new framework for analyzing complex, multi-dimensional data (tensors) by modeling their dependency structures as "tensor graphical models." They propose an efficient algorithm, Tlasso, that can learn these structures even from a single data sample, a significant leap for high-dimensional data analysis. This opens doors for deeper insights in fields like neuroimaging and recommendation systems.

What Problem Does This Paper Address?

Many real-world datasets are not simple vectors or matrices but have multiple dimensions, like user-item-time interactions in recommendation systems or brain activity over time and conditions in fMRI. These are called tensors. Understanding the relationships (dependencies) between different aspects of these tensors is crucial for extracting meaningful insights. Traditional methods often struggle with the high dimensionality and complex structure of tensor data, either by ignoring the tensor structure (leading to inefficient estimation) or by relying on assumptions that don't hold in practice. A key challenge is that learning these dependencies often involves solving a non-convex optimization problem, which is notoriously difficult.

Methods

The authors propose a novel Tensor Graphical Model framework. The core idea is to model the precision matrix for each dimension of the tensor using a sparse graphical model. A critical challenge is that estimating these sparse precision matrices involves minimizing a non-convex objective function. To overcome this, they introduce the Tlasso algorithm, which uses an alternating minimization approach. This means it iteratively optimizes one precision matrix while keeping the others fixed. Crucially, they prove that this algorithm achieves an optimal statistical rate of convergence even after just one iteration. They also develop a de-biased statistical inference procedure for hypothesis testing on these precision matrices, including a False Discovery Rate (FDR) control mechanism for robust multiple testing.

Datasets

The paper evaluates its methods on two real-world datasets:

  • Autism Brain Imaging Data Exchange (ABIDE): This dataset contains resting-state functional magnetic resonance imaging (fMRI) data from subjects with and without Autism Spectrum Disorder (ASD). The data is structured as 3D tensors representing brain activity.
  • Advertisement Click Data: This dataset captures user click-through rates for advertisements across different publishers, days of the week, and devices (PC/mobile). This data is structured as multi-dimensional tensors.

Key Insights and Ideas

  • Learning from a Single Sample: A remarkable finding is that Tlasso can achieve estimation consistency even with just one tensor observation when the number of dimensions (K) is 3 or more. This is a significant advantage for datasets where collecting many samples is difficult or impossible.
  • Leveraging Tensor Structure: The Tlasso algorithm effectively utilizes the multi-dimensional structure of the data. This allows it to achieve better performance and faster computation compared to methods that flatten the tensor into a vector.
  • Optimal Estimation Rates: The Tlasso algorithm achieves minimax-optimal convergence rates for estimating the sparse precision matrices, meaning it achieves the best possible rate given the data.
  • Efficient Inference: The proposed statistical inference procedure, including FDR control, is shown to be asymptotically valid and performs well in simulations, enabling reliable hypothesis testing on the learned graphical structures.

Key Results

  • Estimation Accuracy: Tlasso demonstrates superior estimation accuracy in both Frobenius and max norms compared to existing methods like graphical lasso (Glasso) and a penalized maximum likelihood (P-MLE) approach. In simulations, Tlasso is significantly faster than P-MLE and Glasso, with Glasso being omitted in some plots due to its extreme slowness.
  • Computational Efficiency: Tlasso is dramatically faster than competing methods, taking seconds for complex scenarios where others take minutes or hours.
  • Statistical Inference: The inference procedure shows good performance in controlling FDR and achieving high power in simulations, even under challenging conditions like small sample sizes or high dimensionality.
  • Real-World Applications: Analysis of the ABIDE dataset revealed potentially differential connectivity patterns in brain regions associated with ASD. The advertisement click data analysis identified interesting dependencies between advertisements, publishers, and days of the week, varying by device (PC vs. mobile).

Limitations and Future Work

  • Non-Convex Penalties: While Tlasso uses the Lasso penalty, the authors note that other non-convex penalties (SCAD, MCP, Truncated l₁) could potentially correct for estimation bias. They suggest that future work could extend the theoretical analysis to these penalties.
  • Irrepresentability Condition: For achieving optimal rates in the max norm, an "irrepresentability condition" is required. The authors mention that recent advances in non-convex regularization might allow for the elimination of this condition, which is a direction for future research.
  • Computational Complexity: While Tlasso is efficient, the theoretical analysis for some aspects (like the max norm error) requires a small number of iterations (T=2). Further exploration into minimizing the number of iterations while maintaining performance is a potential area for improvement.

Summary updated

Abstract

We consider the estimation and inference of 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. A critical challenge in the estimation and inference of this model is the fact that its penalized maximum likelihood estimation involves minimizing a non-convex objective function. To address it, this paper makes two contributions: (i) 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 an optimal statistical rate of convergence. (ii) We propose a de-biased statistical inference procedure for testing hypotheses on the true support of the sparse precision matrices, and employ it for testing a growing number of hypothesis with false discovery rate (FDR) control. The asymptotic normality of our test statistic and the consistency of FDR control procedure are established. Our theoretical results are backed up by thorough numerical studies and our real applications on neuroimaging studies of Autism spectrum disorder and users' advertising click analysis bring new scientific findings and business insights. The proposed methods are encoded into a publicly available R package Tlasso.
BibTeX
@article{lyu2020tensor,
  author = {Xiang Lyu and Will Wei Sun and Zhaoran Wang and Han Liu and Jian Yang and Guang Cheng},
  title = {{Tensor Graphical Model: Non-Convex Optimization and Statistical Inference}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2020},
  doi = {10.1109/tpami.2019.2907679},
}
Figure