Recently, an intriguing class of non-convex optimization problems has emerged
in the context of learning directed acyclic graphs (DAGs). These problems
involve minimizing a given loss or score function, subject to a non-convex
continuous constraint that penalizes the presence of cycles in a graph. In this
work, we delve into the optimization challenges associated with this class of
non-convex programs. To address these challenges, we propose a bi-level
algorithm that leverages the non-convex constraint in a novel way. The outer
level of the algorithm optimizes over topological orders by iteratively
swapping pairs of nodes within the topological order of a DAG. A key innovation
of our approach is the development of an effective method for generating a set
of candidate swapping pairs for each iteration. At the inner level, given a
topological order, we utilize off-the-shelf solvers that can handle linear
constraints. The key advantage of our proposed algorithm is that it is
guaranteed to find a local minimum or a KKT point under weaker conditions
compared to previous work and finds solutions with lower scores. Extensive
experiments demonstrate that our method outperforms state-of-the-art approaches
in terms of achieving a better score. Additionally, our method can also be used
as a post-processing algorithm to significantly improve the score of other
algorithms. Code implementing the proposed method is available at
this https URL

本研究提出了一种新的双层算法，用于优化具有非凸性约束的有向无环图，并解决了此类问题的优化挑战，具有更弱的条件保证和更低的得分，并且在实验中表现优于现有方法。

通过拓扑交换优化 NOTEARS 目标

Optimizing NOTEARS Objectives via Topological Swaps

We propose a mixed integer programming (MIP) model and iterative algorithms
based on topological orders to solve optimization problems with acyclic
constraints on a directed graph. The proposed MIP model has a significantly
lower number of constraints compared to popular MIP models based on cycle
elimination constraints and triangular inequalities. The proposed iterative
algorithms use gradient descent and iterative reordering approaches,
respectively, for searching topological orders. A computational experiment is
presented for the Gaussian Bayesian network learning problem, an optimization
problem minimizing the sum of squared errors of regression models with L1
penalty over a feature network with application of gene network inference in
bioinformatics.

本文提出了一种基于拓扑序的混合整数规划模型与迭代算法，来解决带有有向图中非循环约束的优化问题。模型具有较少的约束条件且使用了梯度下降和迭代重新排序等方法。该方法在高斯贝叶斯网络学习问题中进行了计算实验，用于在生物信息学中推断基因网络