Estimating the matrix of connections probabilities is one of the key questions when studying sparse networks. In this work, we consider networks generated under the sparse graphon model and the in-homogeneous random graph model with missing observations. Using the Stochastic Block Model as a parametric proxy, we bound the risk of the maximum likelihood estimator of network connections probabilities , and show that it is minimax optimal. When risk is measured in Frobenius norm, no estimator running in polynomial time has been shown to attain the minimax optimal rate of convergence for this problem. Thus, maximum likelihood estimation is of particular interest as computationally efficient approximations to it have been proposed in the literature and are often used in practice.


翻译:估计连接概率矩阵是研究稀疏网络时的一个关键问题。 在这项工作中,我们考虑到根据稀疏的图形模型和同源随机图模型生成的网络并缺少观测。 使用Stochatic区块模型作为参数替代,我们将网络连接概率最大可能性估计值的风险捆绑起来,并显示这是最优化的。 在根据Frobenius规范衡量风险时,没有显示在多元时间内运行的估算器能够达到这一问题最小最佳趋同率。 因此,由于文献中已经提出了计算效率高的近似值,而且在实践中经常使用,因此最大可能性估算是特别有意义的。

0
下载
关闭预览

相关内容

剑桥大学《数据科学: 原理与实践》课程,附PPT下载
专知会员服务
49+阅读 · 2021年1月20日
专知会员服务
52+阅读 · 2020年9月7日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
28+阅读 · 2019年10月18日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
已删除
将门创投
7+阅读 · 2019年10月10日
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
VIP会员
相关资讯
已删除
将门创投
7+阅读 · 2019年10月10日
Top
微信扫码咨询专知VIP会员