Global Optimality in Bivariate Gradient-based DAG Learning

2023/06/30 by Deng, Chang, Bello, Kevin, Aragam, Bryon +1 · 2 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2306.17378

Abstract

Recently, a new class of non-convex optimization problems motivated by the statistical problem of learning an acyclic directed graphical model from data has attracted significant interest. While existing work uses standard first-order optimization schemes to solve this problem, proving the global optimality of such approaches has proven elusive. The difficulty lies in the fact that unlike other non-convex problems in the literature, this problem is not "benign", and possesses multiple spurious solutions that standard approaches can easily get trapped in. In this paper, we prove that a simple path-following optimization scheme globally converges to the global minimum of the population loss in the bivariate setting.

Cited by

• Non-negative DAG Learning from Time-Series Data
• Differentiable Structure Learning and Causal Discovery for General Binary Data

Related

• A Principle for Global Optimization with Gradients
• Stability and Generalization of Learning Algorithms that Converge to Global Optima
• Learning to be Global Optimizer
• Recent Theoretical Advances in Non-Convex Optimization
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems