Tensor Methods for Additive Index Models under Discordance and Heterogeneity

Krishnakumar Balasubramanian, Jianqing Fan, Zhuoran YangarXiv 2018 · DOI · arXiv

TL;DR

This paper introduces Discordant Additive Index Models (DAIM), a framework for handling high-dimensional datasets where the relationship between inputs and outputs is obscured by aggregation or heterogeneity. By leveraging third-order tensor decomposition and the Method of Moments, the authors provide a way to recover model parameters even in "overcomplete" settings (where there are more latent components than dimensions) without needing to know the underlying non-linear link functions.

What Problem Does This Paper Address?

In the "Big Data" era, datasets are often aggregated from diverse sources, leading to two major headaches for statisticians: heterogeneity and discordance.

  • Heterogeneity occurs when data is a mixture of several different underlying models (e.g., different consumer behaviors in one dataset).
  • Discordance happens when we can't see the individual responses of these models, but only an aggregate, like an average or a sum (common in privacy-preserving data or record linkage issues).

Standard regression techniques usually fail here because they assume a direct, clean link between a covariate $X$ and a response $Y$. Furthermore, many existing methods require knowing the exact "link function" (the non-linear shape of the relationship) or struggle when the number of latent components ($k$) exceeds the number of features ($d$). This paper seeks a method that is agnostic to the link function and works in high-dimensional, overcomplete settings.

Methods

The authors propose a Method of Moments approach based on higher-order Score Tensors.

  1. Score Tensors and Stein’s Identity: Instead of looking at simple correlations (second-order matrices), they use third-order tensors derived from the derivatives of the Gaussian density. Using a higher-order version of Stein’s Identity, they show that the expected value of these tensors reveals the "directions" (parametric indices) of the latent models.
  2. Tensor Power Methods: To extract these directions from noisy, sampled data, they employ:
  3. Algorithm 1 (Low-Dimensional): A standard tensor power method for cases where the number of samples $n$ is much larger than the dimension $d$.
  4. Algorithm 2 (High-Dimensional/Sparse): A Truncated Tensor Power Method that enforces sparsity, allowing the model to work even when $n < d$, provided the underlying parameters are sparse.
  5. Agnostic Estimation: Crucially, the method recovers the parameter vectors $\{\beta_j^*\}$ without ever needing to estimate the non-parametric link functions $f_j$.

Datasets

The paper evaluates the proposed methods using synthetic simulations.

  • Covariates: Generated from a standard Gaussian distribution $N(0, I_d)$.
  • Link Functions: To test the "agnostic" claim, they used three distinct non-linear functions:
  • $h_1(u) = u^3 + 10 \cdot \exp(-u^2)$
    1. $h_2(u) = u^3 + 5 \cdot \sin(2 \cdot u^2)$
    2. $h_3(u) = u^3 + 10 \cdot \tanh(u^2)$
  • Settings: They varied the dimensionality ($d=20$ to $100$), the number of components ($k=3$ to $7$), and the sparsity levels ($s=3$ to $5$).

Key Insights and Ideas

  • The Power of 3D: Why use 3rd-order tensors instead of standard 2nd-order matrices (like PCA)? Matrix decomposition only identifies a subspace; tensor decomposition is unique up to permutation and scaling. This allows for the identification of individual components even in overcomplete settings ($k > d$).
  • Agnosticism is a Feature: By focusing on the score function of the covariates rather than the response's distribution, the researchers can "bypass" the need to specify or learn the non-linear part of the model.
  • Theoretical Heavy Lifting: The core theoretical contribution is the derivation of new tensor operator norm concentration inequalities. These proofs explain how quickly the empirical moment tensor converges to the true population tensor, providing a mathematical guarantee for the estimator's accuracy.

Key Results

  • Convergence Rates: The authors established that in the low-dimensional regime, the estimation error scales with $\max(\sqrt{d/n}, d^{5/2}/n)$. In the high-dimensional sparse regime, the error depends only poly-logarithmically on the dimension $d$, scaling with $\sqrt{s \log d / n}$.
  • Simulation Validation: Numerical experiments confirmed the theory. The estimation error decreased linearly as the "inverse signal strength" (a function of $n, d,$ and $s$) decreased.
  • Robustness: The method performed consistently well across all three different non-linear link functions, proving it is truly agnostic to the non-parametric component.

Limitations and Future Work

  • Gaussian Assumption: The current theory relies heavily on the covariates $X$ being Gaussian to utilize Stein’s Lemma. The authors note that while this can be relaxed to "well-conditioned" distributions, moving to general non-Gaussian distributions is a "much harder task."
  • Initialization: Tensor decomposition is a non-convex problem. While the authors used random initialization in their experiments with success, providing a theoretical guarantee for "good" initialization in the overcomplete setting remains an open challenge.
  • Heavy Tails: The current model assumes sub-exponential noise. Future work could explore methods to handle even heavier-tailed data distributions.

Summary updated

Abstract

Motivated by the sampling problems and heterogeneity issues common in high- dimensional big datasets, we consider a class of discordant additive index models. We propose method of moments based procedures for estimating the indices of such discordant additive index models in both low and high-dimensional settings. Our estimators are based on factorizing certain moment tensors and are also applicable in the overcomplete setting, where the number of indices is more than the dimensionality of the datasets. Furthermore, we provide rates of convergence of our estimator in both high and low-dimensional setting. Establishing such results requires deriving tensor operator norm concentration inequalities that might be of independent interest. Finally, we provide simulation results supporting our theory. Our contributions extend the applicability of tensor methods for novel models in addition to making progress on understanding theoretical properties of such tensor methods.
BibTeX
@misc{balasubramanian2018tensor,
  author = {Krishnakumar Balasubramanian and Jianqing Fan and Zhuoran Yang},
  title = {{Tensor Methods for Additive Index Models under Discordance and Heterogeneity}},
  year = {2018},
  eprint = {1807.06693},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1807.06693},
}
Figure