On the Convergence of Continuous Constrained Optimization for Structure Learning

Ignavier Ng, Sebastien Lachapelle, Nan Rosemary Ke, Simon Lacoste-Julien, Kun Zhang
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:8176-8198, 2022.

Abstract

Recently, structure learning of directed acyclic graphs (DAGs) has been formulated as a continuous optimization problem by leveraging an algebraic characterization of acyclicity. The constrained problem is solved using the augmented Lagrangian method (ALM) which is often preferred to the quadratic penalty method (QPM) by virtue of its standard convergence result that does not require the penalty coefficient to go to infinity, hence avoiding ill-conditioning. However, the convergence properties of these methods for structure learning, including whether they are guaranteed to return a DAG solution, remain unclear, which might limit their practical applications. In this work, we examine the convergence of ALM and QPM for structure learning in the linear, nonlinear, and confounded cases. We show that the standard convergence result of ALM does not hold in these settings, and demonstrate empirically that its behavior is akin to that of the QPM which is prone to ill-conditioning. We further establish the convergence guarantee of QPM to a DAG solution, under mild conditions. Lastly, we connect our theoretical results with existing approaches to help resolve the convergence issue, and verify our findings in light of an empirical comparison of them.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-ng22b, title = { On the Convergence of Continuous Constrained Optimization for Structure Learning }, author = {Ng, Ignavier and Lachapelle, Sebastien and Rosemary Ke, Nan and Lacoste-Julien, Simon and Zhang, Kun}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {8176--8198}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/ng22b/ng22b.pdf}, url = {https://proceedings.mlr.press/v151/ng22b.html}, abstract = { Recently, structure learning of directed acyclic graphs (DAGs) has been formulated as a continuous optimization problem by leveraging an algebraic characterization of acyclicity. The constrained problem is solved using the augmented Lagrangian method (ALM) which is often preferred to the quadratic penalty method (QPM) by virtue of its standard convergence result that does not require the penalty coefficient to go to infinity, hence avoiding ill-conditioning. However, the convergence properties of these methods for structure learning, including whether they are guaranteed to return a DAG solution, remain unclear, which might limit their practical applications. In this work, we examine the convergence of ALM and QPM for structure learning in the linear, nonlinear, and confounded cases. We show that the standard convergence result of ALM does not hold in these settings, and demonstrate empirically that its behavior is akin to that of the QPM which is prone to ill-conditioning. We further establish the convergence guarantee of QPM to a DAG solution, under mild conditions. Lastly, we connect our theoretical results with existing approaches to help resolve the convergence issue, and verify our findings in light of an empirical comparison of them. } }
Endnote
%0 Conference Paper %T On the Convergence of Continuous Constrained Optimization for Structure Learning %A Ignavier Ng %A Sebastien Lachapelle %A Nan Rosemary Ke %A Simon Lacoste-Julien %A Kun Zhang %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-ng22b %I PMLR %P 8176--8198 %U https://proceedings.mlr.press/v151/ng22b.html %V 151 %X Recently, structure learning of directed acyclic graphs (DAGs) has been formulated as a continuous optimization problem by leveraging an algebraic characterization of acyclicity. The constrained problem is solved using the augmented Lagrangian method (ALM) which is often preferred to the quadratic penalty method (QPM) by virtue of its standard convergence result that does not require the penalty coefficient to go to infinity, hence avoiding ill-conditioning. However, the convergence properties of these methods for structure learning, including whether they are guaranteed to return a DAG solution, remain unclear, which might limit their practical applications. In this work, we examine the convergence of ALM and QPM for structure learning in the linear, nonlinear, and confounded cases. We show that the standard convergence result of ALM does not hold in these settings, and demonstrate empirically that its behavior is akin to that of the QPM which is prone to ill-conditioning. We further establish the convergence guarantee of QPM to a DAG solution, under mild conditions. Lastly, we connect our theoretical results with existing approaches to help resolve the convergence issue, and verify our findings in light of an empirical comparison of them.
APA
Ng, I., Lachapelle, S., Rosemary Ke, N., Lacoste-Julien, S. & Zhang, K.. (2022). On the Convergence of Continuous Constrained Optimization for Structure Learning . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:8176-8198 Available from https://proceedings.mlr.press/v151/ng22b.html.

Related Material