We consider the problem of learning the underlying graph of a sparse Ising model with $p$ nodes from $n$ i.i.d. samples. The most recent and best performing approaches combine an empirical loss (the logistic regression loss or the interaction screening loss) with a regularizer (an L1 penalty or an L1 constraint). This results in a convex problem that can be solved separately for each node of the graph. In this work, we leverage the cardinality constraint L0 norm, which is known to properly induce sparsity, and further combine it with an L2 norm to better model the non-zero coefficients. We show that our proposed estimators achieve an improved sample complexity, both (a) theoretically, by reaching new state-of-the-art upper bounds for recovery guarantees, and (b) empirically, by showing sharper phase transitions between poor and full recovery for graph topologies studied in the literature, when compared to their L1-based state-of-the-art methods.


翻译:我们考虑的是从一美元(i.d.)样本中用美元节点从稀疏的Ising模型中学习原始图案的问题。最新和最有效果的方法是将经验损失(后勤回归损失或互动筛选损失)与正规化器(L1罚款或L1限制)结合起来。这导致了对图表每个节点可以分别解决的二次曲线问题。在这项工作中,我们利用已知能适当诱导散的基点限制L0规范,并进一步将它与L2规范结合起来,以便更好地模拟非零系数。我们表明,我们提议的估算器在理论上通过达到新的回收保证最先进的最高界限,以及(b)在与基于L1的状态方法相比,通过显示文献中研究的图表表层的穷与全面恢复之间的更敏锐的阶段过渡,从而实现了更高的样本复杂性。

0
下载
关闭预览

相关内容

MIT-深度学习Deep Learning State of the Art in 2020,87页ppt
专知会员服务
61+阅读 · 2020年2月17日
吴恩达新书《Machine Learning Yearning》完整中文版
专知会员服务
145+阅读 · 2019年10月27日
深度学习界圣经“花书”《Deep Learning》中文版来了
专知会员服务
233+阅读 · 2019年10月26日
多任务学习(Multi-task Learning)方法总结
极市平台
6+阅读 · 2020年4月26日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Arxiv
0+阅读 · 2021年10月25日
Arxiv
0+阅读 · 2021年10月24日
Arxiv
6+阅读 · 2021年6月24日
Arxiv
8+阅读 · 2021年5月21日
Arxiv
11+阅读 · 2021年2月17日
Logically-Constrained Reinforcement Learning
Arxiv
3+阅读 · 2018年12月6日
Arxiv
19+阅读 · 2018年10月25日
VIP会员
相关资讯
多任务学习(Multi-task Learning)方法总结
极市平台
6+阅读 · 2020年4月26日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
相关论文
Arxiv
0+阅读 · 2021年10月25日
Arxiv
0+阅读 · 2021年10月24日
Arxiv
6+阅读 · 2021年6月24日
Arxiv
8+阅读 · 2021年5月21日
Arxiv
11+阅读 · 2021年2月17日
Logically-Constrained Reinforcement Learning
Arxiv
3+阅读 · 2018年12月6日
Arxiv
19+阅读 · 2018年10月25日
Top
微信扫码咨询专知VIP会员