Nonparametric Trace Regression in High Dimensions via Sign Series Representation

Chanwoo Lee, Lexin Li, Hao Helen Zhang, Miaoyan WangarXiv 2021 · OpenReview

TL;DR

This paper introduces a nonparametric framework for trace regression that moves beyond the restrictive assumptions of known link functions and global low-rank structures. By representing high-dimensional functions as an aggregation of "sign functions," the authors transform complex matrix regression into a series of simpler, parallelizable weighted classification tasks, enabling the modeling of nonlinear and high-rank effects.

What Problem Does This Paper Address?

Matrix-valued data is ubiquitous in modern science, from brain connectivity networks to genomic signals. The standard tool for analyzing this data is trace regression, which typically assumes that a scalar response $Y$ is a linear function of a matrix predictor $X$ through a low-rank coefficient matrix $B$.

However, the authors identify two major pitfalls in classical trace regression:

  1. Rigid Functional Forms: It assumes the relationship between the predictor and the mean response is known (e.g., linear or a specific link function like logistic).
  2. Global Low-Rank Assumption: It assumes the underlying signal matrix is low-rank across its entire range.

In practice, these assumptions are often violated. For example, a simple monotonic transformation of a low-rank matrix can cause its numerical rank to explode, rendering traditional models ineffective (see Figure 1a). Furthermore, many structured matrices are mathematically full-rank but clearly possess a simple underlying pattern (see Figure 1b).

Figure 1: (a) shows how numerical rank increases rapidly under monotonic transformations; (b) shows a structured but full-rank matrix.

Methods

The authors propose ASSIST (Aggregation of Structured SIgn Series for Trace regression). The core innovation is a sign series representation of the regression function. Instead of trying to estimate the function $f(X)$ directly, they decompose it into a series of binary "sign" functions: $sgn(f(X) - \pi)$ for various threshold levels $\pi$.

Key components include:

  • Learning Reduction: The regression problem is reduced to a series of weighted classification tasks. The weight $|Y - \pi|$ is crucial; it ensures that samples far from the threshold $\pi$ are penalized more heavily, effectively incorporating the magnitude of the response into the classification.
  • Sign Rank: They introduce the concept of "sign rank"—the minimum rank of any matrix that shares the same sign pattern as the target matrix. This is a much more flexible measure of complexity than standard rank.
  • ADMM Optimization: They develop an Alternating Direction Method of Multipliers (ADMM) algorithm to solve the resulting optimization problem, which can handle both low-rank and two-way sparsity constraints.
  • Parallelism: Because each threshold level $\pi$ can be solved independently, the algorithm is naturally parallelizable.

Datasets

The authors evaluated their method using:

  • Simulated Data: Four distinct activation patterns (cross, block, star, and circle) were used to test the model's ability to recover various rank and sparsity structures.
  • Brain Connectivity Data: Sourced from the Human Connectome Project (HCP), consisting of $n=212$ healthy subjects. The goal was to predict cognitive performance (visuospatial processing) based on $68 \times 68$ brain connectivity networks.
  • Image Completion: A standard computer vision benchmark—a gray-scaled hot air balloon image ($217 \times 217$ matrix)—was used to test high-rank matrix completion.

Key Insights and Ideas

  • Rank Invariance: Unlike standard matrix rank, sign rank is invariant to order-preserving (monotonic) transformations of the response. This makes the model robust to unknown distortions in data measurement.
  • Lebesgue-style Partitioning: The authors compare their approach to Lebesgue integration. While standard nonparametric methods partition the domain (the high-dimensional matrix space), ASSIST partitions the range (the scalar response). This is far more efficient when the predictor space is massive but the response is simple.
  • Classification is Easier than Regression: The paper theoretically proves that estimating the sign of a function is statistically "easier" (converges faster) than estimating the function's value. By aggregating these easier tasks, they achieve robust regression results.

Key Results

  • Superior Accuracy: In brain connectivity analysis, ASSIST achieved the highest AUC (0.77), outperforming Logistic Regression (0.68) and Convolutional Neural Networks (0.67).
  • High-Rank Recovery: In image completion tasks, ASSIST significantly outperformed standard methods like SoftImpute and HardImpute, especially when data was highly sparse (80% missing).
  • Interpretability: The model successfully identified specific brain regions (like the right inferior temporal and middle temporal regions) whose connectivity was nonlinearly related to cognitive scores.
  • Theoretical Bounds: The authors established excess risk bounds that show the error decays at a rate related to the "sign complexity" of the matrix rather than its mathematical rank.

Limitations and Future Work

  • Beyond Matrices: The current framework is designed for matrix predictors. The authors suggest extending this to tensors (higher-dimensional arrays) and manifold data as a promising future direction.
  • Base Classifiers: While they used trace functions as the base for classification, the framework could potentially be coupled with more sophisticated classifiers like decision trees or deep neural networks.
  • Computational Convergence: While the theory covers the global optimum, characterizing the behavior of the actual non-convex minimizer in the ADMM algorithm remains a challenging open question.

Summary updated

Abstract

Learning of matrix-valued data has recently surged in a range of scientific and business applications. Trace regression is a widely used method to model effects of matrix predictors and has shown great success in matrix learning. However, nearly all existing trace regression solutions rely on two assumptions: (i) a known functional form of the conditional mean, and (ii) a global low-rank structure in the entire range of the regression function, both of which may be violated in practice. In this article, we relax these assumptions by developing a general framework for nonparametric trace regression models via structured sign series representations of high dimensional functions. The new model embraces both linear and nonlinear trace effects, and enjoys rank invariance to order-preserving transformations of the response. In the context of matrix completion, our framework leads to a substantially richer model based on what we coin as the "sign rank" of a matrix. We show that the sign series can be statistically characterized by weighted classification tasks. Based on this connection, we propose a learning reduction approach to learn the regression model via a series of classifiers, and develop a parallelable computation algorithm to implement sign series aggregations. We establish the excess risk bounds, estimation error rates, and sample complexities. Our proposal provides a broad nonparametric paradigm to many important matrix learning problems, including matrix regression, matrix completion, multi-task learning, and compressed sensing. We demonstrate the advantages of our method through simulations and two applications, one on brain connectivity study and the other on high-rank image completion.
BibTeX
@misc{lee2021nonparametric,
  author = {Chanwoo Lee and Lexin Li and Hao Helen Zhang and Miaoyan Wang},
  title = {{Nonparametric Trace Regression in High Dimensions via Sign Series Representation}},
  year = {2021},
  eprint = {2105.01783},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2105.01783},
}
Figure