Summary
This paper studies the problem of learning the correct Directed Acyclic Graph (DAG) that describes the data using continuous optimization. The connection of this problem with continuous methods comes from a prior work of Zheng et al., where they introduce a differentiable function $h$ whose level set at 0 exactly characterizes DAGs. The problem then becomes to optimize a score function of the data subject to the constraint that h is 0. This is a non-convex problem, since h is non-convex. The standard way of solving it is by converting it to an unconstrained problem and penalizing the solutions with high values of h. This paper provides a way of solving a sequence of these problems with varying penalty parameters, so that the final output provably converges to the true solution, when we have two nodes in the DAG. The model is analyzed in the population case, i.e. when we have access to infinite data. The authors first show that for sufficiently small values of the penalty parameter, the loss landscape is not benign, as there exists a saddle point and a spurious local minimum in addition to the global minimum. Using this observation, they show a way to pick a sequence of penalty parameters, which provides a solution path that avoids the local minima and converges provably to the true model asymptotically. Their main result is phrased in terms of gradient flow, but they also provide a finite step analysis for gradient descent.
Strengths
Consider the optimization problem
\begin{equation}\label{eq1}
\min_\Theta g_\mu(\Theta) := \mu f(\Theta) + h(W(\Theta))
\end{equation}
where $f$ is the least squares loss, $\mu$ is the penalty parameter, $\Theta$ represents the model parameters and $W(\Theta)$ represents the adjacency matrix of the DAG. $f$ is a function that was introduced in prior work, which is $0$ if and only if $W(\Theta)$ corresponds to a DAG.
This paper is the first that provides theoretical guarantees about the optimization landscape of this unconstrained problem for various values of $\mu$, in the case of $2$ nodes. It is worth noting that this is actually the method that is used in practice to learn DAGs, since enumeration methods quickly become intractable when the number of nodes in the DAG increases.
The authors establish interesting properties of the solutions space, namely that if $\mu$ is sufficiently small, the loss is not benign.
Also, the idea of successively solving different optimization problems and using the solution of the last as a starting point for the next is an intriguing one and could have applications beyond this work. The proof strategy is also very intuitive and elegant, by choosing $\mu$ so that the optimizer of $g_\mu$ lies in the basin of attraction of the global minimum of the next problem.
All arguments are very clearly explained, which makes this paper enjoyable to read.
Weaknesses
-The result is only proven for $d=2$ nodes in the DAG. This makes most calculations tractable, since there is a closed form for the loss $g_\mu$ (a quadratic polynomial in two variables). Hence, while the proof strategy is elegant and novel, the technical arguments required to establish the claims do not have significant innovation.
Questions
-It would be interesting to see whether similar results hold for higher values of $d$. Have the authors tried to run simulations for $d=3$ or $4$ and observe similar solution landscapes? What about other choices of loss function or penalty?
-Is it always true that there is a unique DAG that describes the data? For example, for two nodes, suppose we have $X_2 = X_1 + \epsilon$, where $\epsilon\sim \mathcal{N}(0,1)$. Then, clearly it is also true that $X_1 = X_2 + \epsilon'$, where $\epsilon' \sim \mathcal{N}(0,1)$. In that case, it seems that we have two solutions $x=1,y=0$ and $x=0,y=1$. I'm curious where would this come up in the analysis.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.