论文标题
稀疏ISING模型的样品有效的L0-L2约束结构学习
Sample-Efficient L0-L2 Constrained Structure Learning of Sparse Ising Models
论文作者
论文摘要
我们考虑了学习稀疏的ISING模型的基础图的问题，该模型具有$ n $ i.i.d.的$ p $节点。样品。最新和最佳性能的方法结合了经验损失（逻辑回归损失或相互作用筛选损失）与常规器（L1惩罚或L1约束）结合在一起。这导致了一个凸问题，可以为图的每个节点分别求解。在这项工作中，我们利用基数约束L0规范，已知可以适当诱导稀疏性，并将其与L2 Norm相结合，以更好地对非零系数进行建模。我们表明，我们提出的估计器通过（a）在理论上实现了改善的样品复杂性，即通过达到新的最新上限以获得恢复保证，并且（b）在经验上，与与L1基于L1基于L1基于L1的统一方法相比，在文献中研究的图形拓扑较差和完整的图形拓扑之间的较尖锐的相变。
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.
