mlsanityData to 14 Oct 2026

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

arXiv 2306.05679 ↗First posted 9 Jun 2023math.ST stat.ML stat.THcited by 2

Not on the map. Why?

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.

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

25 of 79 references.

References · 25

  1. 2017Community Detection and Stochastic Block Modelscited by 319
  2. 2021Learning curves of generic features maps for realistic datasets with a teacher-student modelcited by 126
  3. 2017Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Modelscited by 116
  4. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 115
  5. 2014Controlling the false discovery rate via knockoffscited by 97
  6. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 85
  7. 2021A unifying tutorial on Approximate Message Passingcited by 50
  8. 2014Trend Filtering on Graphscited by 45
  9. 2017Estimation of Low-Rank Matrices via Approximate Message Passingcited by 41
  10. 2020Computational Barriers to Estimation from Low-Degree Polynomialscited by 39
  11. 2018Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structurecited by 35
  12. 2021Graph-based Approximate Message Passing Iterationscited by 35
13 more
  1. 2020The estimation error of general first order methodscited by 33
  2. 2014Computational Lower Bounds for Community Detection on Random Graphscited by 22
  3. 2016Finite Sample Analysis of Approximate Message Passing Algorithmscited by 20
  4. 2022A Non-Asymptotic Framework for Approximate Message Passing in Spiked Modelscited by 20
  5. 2020Universality of Approximate Message Passing Algorithmscited by 16
  6. 2022On double-descent in uncertainty quantification in overparametrized modelscited by 16
  7. 2019Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passingcited by 14
  8. 2017Multi-Layer Generalized Linear Estimationcited by 12
  9. 2020Empirical Bayes PCA in high dimensionscited by 11
  10. 2015Finding One Community in a Sparse Graphcited by 8
  11. 2015EigenPrism: Inference for High-Dimensional Signal-to-Noise Ratioscited by 4
  12. 2022Learning with latent group sparsity via heat flow dynamics on networkscited by 2
  13. 2022The Generalized Elastic Net for least squares regression with network-aligned signal and correlated designcited by 2

Built on by

Cited by year

Citing papers per year: 2024: 2.

2 papers.

  1. 2024Optimal thresholds and algorithms for a model of multi-modal learning in high dimensionscited by 4
  2. 2024Asymptotic generalization error of a single-layer graph convolutional networkcited by 3