Rebuttal
We would like to thank Reviewer Y15A for insightful comments and detailed comments. We now address the problems as follows.
### Paper exceed 9 pages, clarity after page 6.
We are sorry for the problem. Due to limited time there was a technique problem, which results in a very large black area around Figure 2. This issue is now fixed. We will also carefully revise the experiment section to make it more clear.
### Connection between convergence radius and the trade-off vanishing gradient / non-convexity. Discussion of the known-vs-unknown scale.
We have now added a section, discussing the relationship between Hessian of DAG constraints and the convergence radius. The Hessian of the DAG constraints is symmetric but not positive semi-definite. One common way to convexify the problem is to add a term $\eta \mathbb{I}$ to the Hessian (equivalently, add $\eta ||\tilde{\mathbf{B}}||_F^2$) to the objective. If $\eta$ is larger than the Frobenius norm of the Hessian, the problem is convexified. This means that we can use the Frobenius of the Hessian to roughly measure the non-convexity of the DAG constraints.
The Frobenius norm of the Hessian, at some particular point $\tilde{\mathbf{B}}$, only depends on coefficients $c_i$ of the analytic function. From Eq (33) in the updated paper, it clearly shows that larger $c_i$ causes a large Frobenius norm of the Hessian, which roughly shows that constraints with a finite spectral radius suffer more from non-convexity as they have larger $c_i$. However, they also have the benefits of less gradient vanishing as larger $c_i$ cause a larger norm of gradients.
For a problem with a known scale, it is well-known that the MSE loss provides sufficient information for estimating the graph structure, and thus the non-convexity would not cause too much problem as the MSE loss can help to pull the problem out of local minimum. Meanwhile, for a problem with an unknown scale, due to the symmetric property of the Gaussian distribution, the MSE loss, along with the DAG constraints, may suffer a lot from non-convexity as the MSE loss.
### The experiments only pertain synthetic data and do not report any comparison with score-based non-relaxed/discrete methods, see e.g. [1, 2, 3]
Our algorithm is compared with a discrete score-based discrete method GES on a dataset with an unknown scale. Currently, most score-based non-relaxed/discrete approaches are not so scalable, and they only work on graphs with at most 100-200 nodes, meanwhile in most of our experiments the graph size can go up to 2000. In our revised version, we will add an experiment comparing with those methods on small graphs.
### Invex DAG constraints
If we only consider the DAG constraints, it is invex. In the overall framework we further have constraints on the $\ell_1$ norm of the adjacency matrix. In this case, the curve of the DAG constraints becomes similar to Figure 1 due to the norm constraints. We will clarify this in the revised version.
### Eq (16)
In Eq (16), $\mathbf{B}$ is the adjacency matrix so that it appears in the Frobenius norm. The DAG constraints only work for a positive weighted adjacency matrix, and the weight in $\mathbf{B}$ can be either positive or negative. Meanwhile, $\mathbf{B}$ is a DAG if and only if $\mathbf{B}\odot \mathbf{B}$ is a DAG. Based on this we apply DAG constraints on $\mathbf{B}\odot \mathbf{B}$.
### Other minor comments:
We will carefully do a proofreading and fix all typos.