Abstract
This paper introduces a novel framework for multiple-output regression that simultaneously learns the relationship between outputs (the "output structure") and the specific inputs that drive them. By reformulating the regression problem as a Conditional Gaussian Graphical Model (CGGM), the authors utilize inverse-covariance regularization to achieve structured sparsity. This approach overcomes the limitations of traditional methods that require output relationships to be predefined, offering a computationally efficient and fully convex solution for high-dimensional data analysis.
Introduction
In many scientific and financial domains, the goal is to predict multiple related variables from a high-dimensional set of features. For instance, in eQTL mapping, researchers aim to predict the expression levels of hundreds of genes based on thousands of genetic markers (SNPs). Standard techniques like the Lasso treat each output independently, failing to leverage the statistical strength inherent in the relationships between outputs. While structured sparsity methods like GFlasso exist, they typically require the output relationship graph to be known a priori—a significant hurdle in practice. This paper addresses the "chicken-and-egg" problem of joint estimation: learning both the sparse regression coefficients and the underlying network of outputs simultaneously.
Methodology: The CGGM Framework
The core innovation of this work is the transition from the standard regression model ($y = Bx + \epsilon$) to a Conditional Gaussian Graphical Model (CGGM).
Alternative Parameterization
Instead of estimating the regression matrix $B$ directly, the model estimates two distinct matrices:
- $\Theta_{yy}$: Represents the internal network of the outputs (the precision matrix). A zero entry indicates that two outputs are conditionally independent given all other variables.
- $\Theta_{xy}$: Represents the direct influence of inputs on outputs.
The traditional regression coefficients are then recovered through the relationship $B = -\Theta_{yy}^{-1}\Theta_{xy}^T$. This formulation ensures that even if the direct influence matrix $\Theta_{xy}$ is highly sparse, the resulting regression matrix $B$ exhibits "structured sparsity" as effects propagate through the learned $\Theta_{yy}$ network.
Regularization and Optimization
The authors apply $L_1$ penalties to both $\Theta_{yy}$ and $\Theta_{xy}$ to encourage sparsity. Crucially, unlike previous joint-estimation methods (e.g., MRCE) which were bi-convex and prone to local minima, this CGGM formulation is fully convex. To handle the optimization efficiently, the authors adapted the Orthant-Wise Limited-memory Quasi-Newton (OWL-QN) algorithm, providing significant scalability improvements over standard interior-point methods.
Key Insights
- Direct vs. Indirect Influence: The model distinguishes between an input that directly affects a specific output ($\Theta_{xy}$) and an input whose effect "spreads" to other outputs through the learned network ($\Theta_{yy}$). This provides a more nuanced and interpretable view of biological or financial systems.
- Automatic Grouping: The connected components in the learned $\Theta_{yy}$ graph naturally define groups of related outputs. This method discovers these groups automatically from the data, eliminating the need for manual group definition required by methods like Group Lasso.
- Convexity and Stability: By ensuring a single global optimum, the method avoids the convergence issues and instability associated with non-convex or bi-convex alternatives.
Experimental Results
The authors validated their approach across several datasets:
- Simulated Data: In cases involving chain, tree, and overlapping group structures, the Sparse CGGM significantly outperformed Lasso, MRCE, and GFlasso in recovering true non-zero coefficients, as evidenced by superior ROC curves.
- Human Liver Cohort: In an eQTL mapping task (937 SNPs, 100 genes), the method achieved a prediction error of 2.359, nearly half that of Lasso (4.212).
- S&P 500 Stock Prices: The model consistently outperformed competitors in predicting future stock prices by accounting for sector-based correlations.
- Computational Efficiency: The Sparse CGGM is orders of magnitude faster than MRCE, completing in minutes on datasets where MRCE required an entire day.
Conclusion
The proposed CGGM framework offers a robust and efficient solution for joint estimation in multiple-output regression. By leveraging inverse-covariance regularization, it successfully learns both structured sparsity and output relationships. While the current implementation requires matrix inversion—a potential bottleneck for extremely large-scale problems—the move toward fully convex optimization marks a significant step forward in high-dimensional statistical modeling.
Summary updated