Optimality of Variational Inference for Stochastic Block Model

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=dB5azK4nnbY


Duration: 54:40
918 views
16

Olga Klopp (ESSEC Business School)
https://simons.berkeley.edu/node/22618
Graph Limits, Nonparametric Models, and Estimation

Variational methods are extremely popular in the analysis of network data. Statistical guarantees obtained for these methods typically provide asymptotic normality for the problem of estimation of global model parameters under the stochastic block model. In the present work, we consider the case of networks with missing links that is important in application and show that the variational approximation to the maximum likelihood estimator converges at the minimax rate. This provides the first minimax optimal and tractable estimator for the problem of parameter estimation for the stochastic block model. We complement our results with numerical studies of simulated and real networks, which confirm the advantages of this estimator over current methods.

This is joint work with Adrian Roellin.



Other Videos By Simons Institute for the Theory of Computing


2022-10-11A Tutorial on Finite-Sample Guarantees of Contractive Stochastic Approximation With...
2022-10-11A Tutorial on Finite-Sample Guarantees of Contractive Stochastic Approximation With...
2022-10-11Stochastic Bin Packing with Time-Varying Item Sizes
2022-10-10Constant Regret in Exchangeable Action Models: Overbooking, Bin Packing, and Beyond
2022-10-08On The Exploration In Load-Balancing Under Unknown Service Rates
2022-10-08Sample Complexity Of Policy-Based Methods Under Off-Policy Sampling And ...
2022-10-08The Compensated Coupling (or Why the Future is the Best Guide for the Present)
2022-10-08Higher-Dimensional Expansion of Random Geometric Complexes
2022-10-08On the Power of Preconditioning in Sparse Linear Regression
2022-10-07What Functions Do Transformers Prefer to Represent?
2022-10-01Optimality of Variational Inference for Stochastic Block Model
2022-10-01Machine Learning on Large-Scale Graphs
2022-10-01Survey on Sparse Graph Limits + A Toy Example
2022-10-01Long Range Dependence in Evolving Networks
2022-09-30Stochastic Processes on Sparse Graphs: Hydrodynamic Limits and Markov Approximations
2022-09-30Large Deviation Principle for the Norm of the Adjacency Matrix and the Laplacian Matrix of...
2022-09-30Longitudinal Network Models, Log-Linear Multigraph Models, and Implications to Estimation and...
2022-09-30Graphon Games
2022-09-30Vertexons and Embedded Graphon Mean Field Games
2022-09-30Motif Counting via Subgraph Sampling
2022-09-29Graphon Limit and Large Independent Sets in Uniform Random Cographs


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Graph Limits Nonparametric Models and Estimation
Olga Klopp