*Online Seminar* Graduate Student Seminar: Learning Sparse Graphons and the Generalized Kesten-Stigum Threshold, Speaker, Shuangping Li

Graduate Student Seminars
  • Shuangping Li
  • PACM
  • Learning Sparse Graphons and the Generalized Kesten-Stigum Threshold
Feb 9, 2021
12:30 pm
*Online Seminar*

ZOOM:  https://princeton.zoom.us/j/91903668690

Title:  Learning Sparse Graphons and the Generalized Kesten-Stigum Threshold

Abstract: The problem of learning graphons has attracted considerable attention across several scientific communities, with significant progress over the recent years in sparser regimes. Yet, the current techniques still require diverging degrees in order to succeed with efficient algorithms in the challenging cases where the local structure of the graph is homogeneous. In this talk, I will present an efficient algorithm to learn graphons in the constant expected degree regime. The algorithm is shown to succeed in estimating the rank-$k$ projection of a graphon in the $L_2$ metric if the top $k$ eigenvalues of the graphon satisfy a generalized Kesten-Stigum condition.