This paper presents a convex-analytic framework to learn sparse graphs from data. While our problem formulation is inspired by an extension of the graphical lasso using the so-called combinatorial graph Laplacian framework, a key difference is the use of a nonconvex alternative to the $\ell_1$ norm to attain graphs with better interpretability. Specifically, we use the weakly-convex minimax concave penalty (the difference between the $\ell_1$ norm and the Huber function) which is known to yield sparse solutions with lower estimation bias than $\ell_1$ for regression problems. In our framework, the graph Laplacian is replaced in the optimization by a linear transform of the vector corresponding to its upper triangular part. Via a reformulation relying on Moreau's decomposition, we show that overall convexity is guaranteed by introducing a quadratic function to our cost function. The problem can be solved efficiently by the primal-dual splitting method, of which the admissible conditions for provable convergence are presented. Numerical examples show that the proposed method significantly outperforms the existing graph learning methods with reasonable CPU time.


翻译:本文展示了一个从数据中学习稀有图形的解析框架。 虽然我们的问题配方是由使用所谓的组合图形 Laplacian 框架来扩展图形 lasso 的扩展所启发的, 但关键区别在于使用 $\ ell_ 1$ 标准的非convex 替代 $\ ell_ 1$ 标准, 以更好的解释性达到图形。 具体地说, 我们使用微弱的 convex 迷你形群( $\ ell_ 1$ 标准与 Huber 函数之间的差额) 来保证总体的共性。 问题可以通过原始分解法来有效解决, 其估计偏差低于$\ ell_ 1$ 。 在我们的框架中, Laplacian 图形在优化中被与其上三角部分相对应的矢量的线性变换所取代。 我们通过重新配置依靠 Moreau 的分解功能来保证整体的共性。 我们用原始分解法来有效解决问题, 问题可以通过原始分解法来有效解决,, 其中显示可被接受的趋同的条件。 。 Nmericalal exical exual expecal ex exol exm exol ex exmol ex exmol ex exmol exmol lections

0
下载
关闭预览

相关内容

【斯坦福经典书最新版】语音语言处理,653页pdf
专知会员服务
51+阅读 · 2021年1月1日
专知会员服务
50+阅读 · 2020年12月14日
斯坦福2020硬课《分布式算法与优化》
专知会员服务
118+阅读 · 2020年5月6日
元学习与图神经网络逻辑推导,55页ppt
专知会员服务
128+阅读 · 2020年4月25日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
RF(随机森林)、GBDT、XGBoost面试级整理
数据挖掘入门与实战
7+阅读 · 2018年2月6日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Arxiv
0+阅读 · 2021年11月9日
Arxiv
0+阅读 · 2021年11月9日
Arxiv
0+阅读 · 2021年11月8日
Arxiv
7+阅读 · 2021年10月19日
Arxiv
9+阅读 · 2021年4月8日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关VIP内容
【斯坦福经典书最新版】语音语言处理,653页pdf
专知会员服务
51+阅读 · 2021年1月1日
专知会员服务
50+阅读 · 2020年12月14日
斯坦福2020硬课《分布式算法与优化》
专知会员服务
118+阅读 · 2020年5月6日
元学习与图神经网络逻辑推导,55页ppt
专知会员服务
128+阅读 · 2020年4月25日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
RF(随机森林)、GBDT、XGBoost面试级整理
数据挖掘入门与实战
7+阅读 · 2018年2月6日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
相关论文
Arxiv
0+阅读 · 2021年11月9日
Arxiv
0+阅读 · 2021年11月9日
Arxiv
0+阅读 · 2021年11月8日
Arxiv
7+阅读 · 2021年10月19日
Arxiv
9+阅读 · 2021年4月8日
Arxiv
3+阅读 · 2017年12月1日
Top
微信扫码咨询专知VIP会员