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
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
54+阅读 · 2019年10月17日
ICML2019:Google和Facebook在推进哪些方向?
专知
5+阅读 · 2019年6月13日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 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日
Arxiv
0+阅读 · 2021年8月4日
Arxiv
6+阅读 · 2021年6月24日
Arxiv
6+阅读 · 2018年12月10日
Arxiv
5+阅读 · 2018年4月30日
VIP会员
相关资讯
ICML2019:Google和Facebook在推进哪些方向?
专知
5+阅读 · 2019年6月13日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 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日
Top
微信扫码咨询专知VIP会员