# Bayes optimal learning in high-dimensional linear regression with network side information

arXiv: https://arxiv.org/abs/2306.05679 · HTML: https://mlsanity.com/paper/2306.05679/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 79 references that are in the map.
- First posted on arXiv 9 Jun 2023.

## Builds on (most cited first, 25 of 25)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Learning curves of generic features maps for realistic datasets with a teacher-student model](https://mlsanity.com/paper/2102.08127/) (2021)
- [Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/1708.03395/) (2017)
- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Controlling the false discovery rate via knockoffs](https://mlsanity.com/paper/1404.5609/) (2014)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Trend Filtering on Graphs](https://mlsanity.com/paper/1410.7690/) (2014)
- [Estimation of Low-Rank Matrices via Approximate Message Passing](https://mlsanity.com/paper/1711.01682/) (2017)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [Graph-based Approximate Message Passing Iterations](https://mlsanity.com/paper/2109.11905/) (2021)
- [The estimation error of general first order methods](https://mlsanity.com/paper/2002.12903/) (2020)
- [Computational Lower Bounds for Community Detection on Random Graphs](https://mlsanity.com/paper/1406.6625/) (2014)
- [Finite Sample Analysis of Approximate Message Passing Algorithms](https://mlsanity.com/paper/1606.01800/) (2016)
- [A Non-Asymptotic Framework for Approximate Message Passing in Spiked Models](https://mlsanity.com/paper/2208.03313/) (2022)
- [Universality of Approximate Message Passing Algorithms](https://mlsanity.com/paper/2003.10431/) (2020)
- [On double-descent in uncertainty quantification in overparametrized models](https://mlsanity.com/paper/2210.12760/) (2022)
- [Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passing](https://mlsanity.com/paper/1907.07502/) (2019)
- [Multi-Layer Generalized Linear Estimation](https://mlsanity.com/paper/1701.06981/) (2017)
- [Empirical Bayes PCA in high dimensions](https://mlsanity.com/paper/2012.11676/) (2020)
- [Finding One Community in a Sparse Graph](https://mlsanity.com/paper/1502.05680/) (2015)
- [EigenPrism: Inference for High-Dimensional Signal-to-Noise Ratios](https://mlsanity.com/paper/1505.02097/) (2015)
- [Learning with latent group sparsity via heat flow dynamics on networks](https://mlsanity.com/paper/2201.08326/) (2022)
- [The Generalized Elastic Net for least squares regression with network-aligned signal and correlated design](https://mlsanity.com/paper/2211.00292/) (2022)

## Built on by (most cited first, 2 of 2)

- [Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions](https://mlsanity.com/paper/2407.03522/) (2024)
- [Asymptotic generalization error of a single-layer graph convolutional network](https://mlsanity.com/paper/2402.03818/) (2024)

## Abstract (arXiv)

Supervised learning problems with side information in the form of a network arise frequently in applications in genomics, proteomics and neuroscience. For example, in genetic applications, the network side information can accurately capture background biological information on the intricate relations among the relevant genes. In this paper, we initiate a study of Bayes optimal learning in high-dimensional linear regression with network side information. To this end, we first introduce a simple generative model (called the Reg-Graph model) which posits a joint distribution for the supervised data and the observed network through a common set of latent parameters. Next, we introduce an iterative algorithm based on Approximate Message Passing (AMP) which is provably Bayes optimal under very general conditions. In addition, we characterize the limiting mutual information between the latent signal and the data observed, and thus precisely quantify the statistical impact of the network side information. Finally, supporting numerical experiments suggest that the introduced algorithm has excellent performance in finite samples.