Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This is an interesting paper that seeks to provide new non-cyclic constraint formulations for DAG learning. The key novelty here is the employment of finite geometric series DAG constraint to escape from gradient vanishing . The idea of reducing the polynomial constraint to order-k polynomial also provides some very interesting benefits. The experimental comparison with SoTA methods is comprehensive, although limited to the comparison on accuracy. Overall, the work is well done and provides some new methodology to this field.
strengths_and_weaknesses: Strength: 
A new type of DAG constraint is proposed, and analysis is provided. Empirical results show that this new constraint helps to improve the learning accuracy, in terms of SHD.

Weakness:
Given that the possibility of using general polynomial constraints was already proposed and proved in NOFEARS, and they have also proposed a new formulation to resolve the vanishing gradient issue, the analysis in this paper seems incremental. One of the main contribution is an efficient algorithm to evaluate the constraint. However, only the comparison on SHD was provided. Therefore, there is not presented evidence that the proposed method is more efficient than the SoTA methods.
questions: 1. For the experimental results, besides SHD and SHDC, the number of learnt edges should also be provided.
2. In numerical tests, the methods were tested only on relatively sparse graphs (with <=3 averaged number of edges). However, it is often more challenging to learn the graph structure on denser graphs. Can the authors provide comparison on at least one denser graph case, say, ER6?
3. Besides SHD, can the authors provide a comparison on computational time, to provide evidence on the claimed efficiency?
4. NOFEARS has also claimed to resolve the vanishing gradient issue. Can the authors compare their method with NOFEARS?
5. According to what I read, it seems DAG no curls aim to accelerate the learning, not to improve the accuracy. Moreover, its accuracy depends on the tunable penalty parameter, which is possibly why the authors observed a deteriorated performance here if they didn't optimize that penalty parameter. This fact should be at least pointed out and discussed in the paper.
limitations: The limitations were discussed adequately.
review_title: null

final_score: 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.
review_content: summary: This paper proposes a new regularization term for DAG estimation, whose role is to enforce that the connectivity matrix is nilpotent.

The contribution basically amounts to depart from state of the art that considers infinite sums of power terms as a regularization to replace them by a finite sum of un-weighted power terms. 
This simple change is motivated in a thorough theoretical way and a fast algorithm is proposed. Performance is good.
strengths_and_weaknesses: * The paper focuses on the very focused problem of estimating a DAG connectivity matrix. This highly focused contribution is a strength in my view: it stays focused and everything about the paper looks good in my view, from the state of the art to the theoretical developments.
* As another strength, I must mention that the whole paper is very factual and written in a neutral tone. For once, people are not pretending they are "reinventing" or "rethinking" something...

* As a weakness, I could mention the limited scale of the experiments. I understand that the paper is mostly theoretical, but I guess that DAG estimation would be an important topic for much larger networks. Maybe going to millions is out of scope, but doing experiments with intermediate scales like thousands would be a desirable feature.
questions: * I am not super knowledgeable about DAG, so that I may be missing something trivial, but I don't understand proposition 2 (3). I do understand that \tilde{B}^{k+1}=0, but I don't really understand why we should have tr(\sum_i \tilde{B}^i)=0. Your explanation "Therefore, Proposition 2 suggests that h_{trunc}^k(\tilde{B})=0 is a valid DAG constraint" is not illuminating in this respect. Please elaborate a bit more for non-knowledgeable readers like me.
* In "The full optimization framework", I don't understand why you are picking B\odot B. It's probably obvious but once again, I need a sentence on that.
* I need more details on the nonlinear real case. Could you please detail that better ? Notably the model and how the algorithm is modified.
* L99: "give"-> given
* L138: "attains far more better" far better
* L225: "we are actually find an": looking for
* L306: "while [...] moderate" reads weird because "moderate" is a negative adjective. Replacing "moderate"-> "promising" makes the sentence closer to what you probably mean (basically "although the previous stuff is good, it suffers from some weakness and fix that")
* L314: "nut-shell"->nutshell
limitations: models able to handle bigger data are mentioned at the end, but as I wrote it would be good to show that the proposed method works fine on moderate but bigger graphs.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper consider continuous score-based DAG learning optimization problem, which is optimizing a least square objective with continuous constraint that characterizes acyclicity for directed graphs. The paper recognizes the gradient vanishing is a important issue in this optimization problem, and most of literature have this issue since they put small weights on the higher order terms in the constraint. The paper proposes a new constraint to avoid gradient vanishing with a trucation to accelerate and ensure stability. Some experiments are conducted to show the effectiveness. 
strengths_and_weaknesses: # Strength

- Solving continuous score-based DAG learning optimization problem is a topic with significance;
- Lots of experiments are conducted to show the effectiveness of proposed new constraint compared to existing work;
- Smooth presentation and discussion about this thread of continuous DAG learning literature.

# Weakness

- It is unclear why gradient vanishing is important, and comparison with existing work is not detailed enough, see Questions;
- Most experiments are about graph recovery, since this is an optimization paper, runtime comparison with other methods is more interesting.
questions: - The paper claims that the gradient vanishing is a key challenge for continuous score-based DAG learning, while current literature all put small weights on higher order terms in the constraint, thus share this problem. Based on the paper, Fig 1 only shows TMPI constraint can control the gradient of higher order terms, but it is still not clear why and how gradient vanishing is important. Does it hinder the optimization process? convergence of algorithm? or statistical property of the estimator?

- If the improment of TMPI is on optimization side, it would be interesting to see the runtime comparison among different methods. And it would be better to provide discussion or intuition why TMPI performs much better in terms of graph recovery (SHD) than other methods while they are essentially optimizing the same least square objective under DAG constraint.

-  How is the proposed constraint related to the ones other than NOTEARS in existing work? Does it also resolve the issues recognized by others (not gradient vanishing)? If not, is it obvious how they can be combined?
limitations: One limitation is discussed right after *Remark 1* and also in *Conclusion*, about all polynomial based DAG constraints, which is when the longest path in the graph is long, the higher order term in constraint matters. It is interesting to see discussion on some particular examples, like Markov chain, especially when the coefficients $B_{jk} > 1$.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper is on learning directed acyclic graphical models using a continuous optimization formulation, where acyclicity is enforced through a matrix polynomial constraint. It is shown that previously proposed polynomial constraints (NOTEARS and similar) suffer from vanishing higher-order terms. A polynomial with unit coefficients is proposed to address this problem, as well as a truncated, lower-order version of this polynomial. The approximation error of the truncated polynomial is bounded. Furthermore, a fast algorithm is presented to compute the new polynomial constraint as well as its gradient. Experiments are performed on synthetic data generated from linear and nonlinear structural equation models, as well as one real dataset. The new polynomial constraint can reduce structural Hamming distance by large factors (i.e. 2-4X) over existing polynomial constraints.
strengths_and_weaknesses: **Strengths:**
+ Furthers our knowledge about continuous constraints for enforcing acyclicity, by pointing out a shortcoming of previously proposed polynomial constraints and proposing a different polynomial to remedy the problem.
+ The structural Hamming distance improvements in the experiments are large (factors of 2-5).
+ The degree $k$ of the polynomial is adapted to each candidate adjacency matrix $\tilde{B}$.

**Weaknesses:**
I like the paper especially for the first reason above. However, the current version suffers from several technical issues in my view.
- Propositions 3 and 5: There appear to be several problems.
    1. First, which norms are meant by the notation $\lVert \cdot \rVert_\infty$ and $\lVert \cdot \rVert_2$? Previously, $\lVert \cdot \rVert_p$ was defined as the element-wise $p$-norm but I suspect this is no longer the case here.
    2. Based on the proof in Appendix A.3, I will assume that $\lVert \cdot \rVert_p$ now means the induced operator norm, i.e., $\lVert A \rVert_p = \sup_{\lVert x \rVert_p = 1} \lVert Ax \rVert_p$. I am assuming this because in the unnumbered equation above (14), I believe $\lVert A \rVert_\infty$ does bound the spectral radius $\rho(A) = \max_i \lvert \lambda_i(A) \rvert$ from above. However, on the left-hand side of this inequality and in (14), the induced 2-norm $\lVert A \rVert_2$ does not equal $\rho(A)$ for a general non-symmetric matrix (the Wikipedia article on spectral radius has a simple counterexample). The adjacency matrix $\tilde{B}$ and its powers are almost certainly non-symmetric.
    3. Continuing with the assumption that $\lVert A \rVert_2$ is the induced 2-norm, the same error occurs in the second-last line of Appendix A.3. On the other hand, I don't think we can replace $\lVert \cdot \rVert_2$ by $\rho(\cdot)$ as we need the sub-additivity property of norms to go from the third-last line to the second-last line, and the spectral radius is not a norm.
    4. Proposition 5: Again assuming that $\lVert A \rVert_2$ is the induced 2-norm, the same error occurs in the proof in Appendix A.5.
    5. Remark 1: The big-O notation seems to be ignoring the $1 - \epsilon^{1/k}$ in the denominators. I don't think this can be done as $k$ can be fairly large so $\epsilon^{1/k}$ is close to 1. Moreover, $k$ is not a constant as it depends on $\epsilon$.
- Proposition 2: I think the proof of (3) $\to$ (1) is incomplete. Since it is still to be proven that $\mathcal{G}$ is a DAG, one must still address directed paths of length greater than $k$, and probably argue that they cannot exist. Also, the phrases "shorter than $k$" and "less than $k$" should be "less than or equal to."
- Proposition 1: The proof of the "if" part in Appendix A.1 refers to [37], but I could not find any mention of "nilpotent" in the paper by Yuan and Malone (2013). Perhaps the reference is to [35] (Wei et al., 2020), wherein Lemma 1 states that $\mathcal{G}$ is acyclic if and only if $\tilde{B}$ is nilpotent. Indeed, Proposition 1 is a corollary of [35, Lemma 1] since the $\tilde{B}^d = 0$/nilpotent $\to$ DAG direction is exactly the same. For the other direction, [35, Lemma 1] implies that $\tilde{B}$ must be nilpotent, and if it is, then $\tilde{B}^k = 0$ for a $k \leq d$, hence $\tilde{B}^d = 0$ also. If the authors agree with this, then the implication from [35, Lemma 1] needs to be acknowledged.
- Figure 1 and corresponding discussion: 
    - It is not clear what gradient is referred to here and what "gradient on higher-order terms" means. I am guessing it is the gradient of the constraint function with respect to $\tilde{B}$ and the "higher-order terms in the gradient" refer to the terms in (7) and similar expressions for the gradient of (3), (4). Perhaps it would be better to show the general form of the gradient and then specialize it to the different cases.
     - The statement "nilpotent properties of DAG result in candidate adjacency matrix with very small spectral radius" needs to be justified mathematically. How this contributes to the vanishing gradient terms seen in Figure 1 should also be better explained.

**Minor comments:**
- Line 43, "these works": Which works does this refer to?
- Eq. (4): Is this missing a $- d$ on the LHS?
- "path": I believe this should be "directed path" to be more precise.
- Eq. (9): Is $p$ the intended exponent rather than $2$?
- Algorithm 2, line 5: I wonder whether the $\tilde{B}$ should be $\tilde{B}_p^{old}$.
- Section 4.1, Results: While the improvements seen here are large, it would be nice to mention for context that factor of $> 2$ improvements upon NOTEARS have been achieved before, e.g. with the KKT search algorithm of [35].
- Figure 4 caption, "our fast": Words missing here. In general, the paper could use careful proofreading for typos, missing/extra words, etc.
- Line 310, $k$ is some constant: As mentioned above, I don't think this is true as it depends on $\epsilon$ and $\tilde{B}$.
questions: - Propositions 3 and 5: Which norms are referred to by $\lVert \cdot \rVert_\infty$ and $\lVert \cdot \rVert_2$?
- Proposition 1: Is the reference to [37] in the proof actually to [35]? Is this proposition a corollary of [35, Lemma 1]?
- Figure 1 and related discussion: Clarify what "gradient" and "gradient on higher-order terms" mean.

More for curiosity:
- The SHD of all algorithms, and in particular the strong baselines Exponential and Binomial, are worse by a large factor for the MSE loss in Figure 2 compared to the likelihood loss in Figure 3. The SHDs in Figure 2 are also worse by a similarly large factor compared to previous work with a similar experimental setting. Compare the top row (ER2) in Figure 2 to e.g. the leftmost columns in Figures 1, 5, 6, 7 in [35], which are also for ER2, $n = 1000$, the same values of $d$, and the same noise types. Any idea why?
limitations: Satisfactory
review_title: null

Meta-review: metareview: During the initial review phase, the reviewers were mostly positive in their opinions of the manuscript, noting that it is well-written, novel, and solves an important problem. However, the reviewers noted a few perceived flaws and technical weaknesses in this manuscript as well. Fortunately, these issues appear to have been positively resolved in a productive discussion during the author response period, particularly with reviewer iGwL. 

Following the response period, the reviewers agreed that the proposed resolutions would significantly strengthen the paper and render it suitable for acceptance. 

I strongly encourage the authors to make the requested changes in preparing an updated version of their manuscript.
confidence: Certain
Decision: Accept