Bayes Optimal Learning in High-Dimensional Linear Regression With Network Side Information

Sagnik Nandy, Subhabrata SenIEEE Trans. Information Theory 2025 · DOI

TL;DR

This paper introduces a novel framework for high-dimensional linear regression that leverages network side information, such as gene co-expression networks. They propose an Approximate Message Passing (AMP) algorithm that is shown to be Bayes optimal under general conditions, offering significant improvements over existing methods for both estimation and variable discovery.

What Problem Does This Paper Address?

In many real-world applications, such as genomics or neuroscience, we have high-dimensional data where we want to predict an outcome (e.g., a phenotype) based on a large number of features (e.g., gene expressions). This is the domain of high-dimensional linear regression. A key challenge is that we often have additional "side information" that can help improve our predictions. In the genomics example, this side information could be a network representing known biological relationships between genes (e.g., which genes are likely to be co-expressed).

Traditional methods often struggle to effectively incorporate this network information. They might use it indirectly through penalization schemes, which can be ad-hoc and difficult to analyze theoretically. The authors aim to bridge this gap by developing a principled Bayesian framework that jointly models the regression data and the network structure, allowing for a more direct and theoretically grounded integration of this side information. This is particularly important for uncovering biologically interpretable insights and achieving better predictive performance.

Methods

The core of the paper is the introduction of a generative model called the Reg-Graph model. This model explicitly links the regression coefficients and the network structure through common latent parameters. This joint modeling allows for a unified approach to inference.

To perform estimation and variable discovery within this model, the authors propose an Approximate Message Passing (AMP) algorithm. AMP is a powerful iterative algorithm well-suited for high-dimensional problems. Their AMP algorithm is designed to naturally incorporate both the supervised regression data and the graph structure. A key theoretical contribution is the state evolution analysis of this AMP algorithm, which allows for the characterization of its asymptotic performance. They also leverage adaptive interpolation methods to derive the limiting mutual information between the data and the latent parameters, which is crucial for establishing Bayes optimality.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical simulations using synthetic data generated according to their proposed Reg-Graph model.

Key Insights and Ideas

  • Joint Modeling is Key: Effectively leveraging network side information requires a model that jointly considers the regression data and the network structure, rather than treating them separately.
  • AMP for Networked Regression: Approximate Message Passing (AMP) is a highly effective algorithmic framework for handling the complexity of high-dimensional regression problems with network side information.
  • Bayes Optimality Achieved: The proposed AMP algorithm, under general conditions, achieves Bayes optimal performance, meaning it performs as well as theoretically possible given the model and priors.
  • Information-Theoretic Gain: The paper quantifies the information-theoretic advantage gained by incorporating network side information, showing it can significantly improve mutual information, especially in noisy settings.
  • Variable Discovery Power: The AMP approach offers superior performance in variable discovery (identifying which features are truly predictive) compared to methods like Knockoffs, precisely because it can utilize the graph structure.

Key Results

  • Bayes Optimal AMP Algorithm: The paper introduces an AMP algorithm for high-dimensional linear regression with network side information that is proven to be Bayes optimal under general conditions.
  • Characterization of Estimation Error: The authors derive the precise limiting L2-estimation error for the regression coefficients (β) and the support recovery error for the latent indicators (σ).
  • Quantification of Mutual Information: They provide a formula for the limiting mutual information between the latent signals and the observed data, demonstrating the information-theoretic gain from the network.
  • Superior Performance in Simulations: Numerical experiments show that the proposed AMP algorithm significantly outperforms existing methods (e.g., Laplacian penalized estimators, Knockoff filter) in terms of reconstruction error and variable discovery (True Discovery Ratio). For instance, in variable selection, the AMP-based method consistently achieves higher True Discovery Ratios than Model-X Knockoff, which ignores graph information.

Limitations and Future Work

  • Single Planted Community: The current framework assumes a single "planted community" in the network structure. Generalizing to multiple planted communities is a natural next step.
  • Independent Gaussian Features: The theoretical analysis assumes independent Gaussian features. Extending the framework to handle correlated features would be more realistic for many applications.
  • Known Model Parameters: The AMP algorithm, as presented, assumes that model parameters (like noise variance, graph connectivity probabilities, and prior distributions) are known. Future work should address estimating these parameters from data (empirical Bayes approaches).
  • Statistical/Computational Gaps: While the AMP algorithm is shown to be Bayes optimal when certain fixed points coincide, the paper acknowledges that statistical/computational gaps might exist in other parameter regimes. Investigating these gaps and developing algorithms that bridge them is an open direction.
  • Applications to Genomics: The authors highlight the motivation from genomics and neuroscience and suggest that AMP-based algorithms can be powerful tools for big-data applications in these fields, stimulating further investigation.

Summary updated

BibTeX
@article{nandy2025bayes,
  author = {Sagnik Nandy and Subhabrata Sen},
  title = {{Bayes Optimal Learning in High-Dimensional Linear Regression With Network Side Information}},
  journal = {IEEE Trans. Information Theory},
  year = {2025},
  doi = {10.1109/tit.2024.3486685},
}
Figure