PC Seminar: Inference in low-rank networks: Information-theoretical limits and algorithms

Abstract: We present recent results related to inference tasks in random networks with low-rank structure. Examples of such networks include the celebrated Stochastic Block Model (SBM) and its extensions (labeled and degree-corrected SBMs) as well as those arising in Reinforcement Learning with low-rank representation. We derive information-theoretical limits pertaining to the recovery of the network structure, and devise algorithms approaching these limits. Our results accommodate for the potential dependence in the way the data is gathered, and in particular handle scenarios where this is done by navigating in the network.

Joint work with Yassir Jedra (MIT), Junghyun Lee (KAIST), Stefan Stojanovic (KTH), and Seyoung Yun (KAIST)

This is a seminar in our seminar series on Probability and Combinatorics (PC).