Learning Directed Acyclic Graphs (DAGs) With Continuous Optimization

Add to your list(s) Download to your calendar using vCal

• Dr Pingfan Song, University of Cambridge
• Wednesday 08 November 2023, 11:00-12:30
• Cambridge University Engineering Department, CBL Seminar room BE4-38..

If you have a question about this talk, please contact Isaac Reid.

Zoom link available upon request (it is sent out on our mailing list, eng-mlg-rcc [at] lists.cam.ac.uk). Sign up to our mailing list for easier reminders via lists.cam.ac.uk.

Estimating the structure of directed acyclic graphs (DAGs) is a challenging problem since the search space of DAGs is combinatorial and scales super-exponentially with the number of nodes. Traditional approaches rely on various local heuristics for enforcing the acyclicity constraint.

Recent advancements have introduced a fundamentally different strategy that formulates DAG learning as a purely continuous optimisation problem over real matrices. This is achieved by capitalising on innovative, differentiable acyclicity characterization functions of DAGs. By eliminating the need for combinatorial constraints, it offers efficient solutions through standard numerical algorithms. Notably, this strategy exhibits several advantages, including the detection of large cycles, improved gradient behaviour, and faster runtime performance.

This talk will introduce a few representative acyclicity characterisation, e.g. trace of matrix exponential function proposed in the No-Tears paper (which is based on the idea that powers of an adjacency matrix contain information about walks and cycles), and log-determinant (log-det) function introduced in the DAGMA paper (which leverages the nilpotency property of DAGs and the property of M-matrices.) These works open possibilities for more effective and efficient DAG learning.

Reading suggestions: Zheng, Xun, Bryon Aragam, Pradeep K. Ravikumar, and Eric P. Xing. “Dags with no tears: Continuous optimization for structure learning.” Advances in neural information processing systems 31 (2018). Bello, Kevin, Bryon Aragam, and Pradeep Ravikumar. “Dagma: Learning dags via m-matrices and a log-determinant acyclicity characterization.” Advances in Neural Information Processing Systems 35 (2022): 8226-8239.

This talk is part of the Machine Learning Reading Group @ CUED series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge University Engineering Department Talks
• Cambridge University Engineering Department, CBL Seminar room BE4-38.
• Cambridge talks
• Centre for Smart Infrastructure & Construction
• Chris Davis' list
• Computational Continuum Mechanics Group Seminars
• Featured lists
• Guy Emerson's list
• Hanchen DaDaDash
• Inference Group Journal Clubs
• Inference Group Summary
• Information Engineering Division seminar list
• Interested Talks
• ML
• Machine Learning Reading Group
• Machine Learning Reading Group @ CUED
• Machine Learning Summary
• Quantum Matter Journal Club
• Required lists for MLG
• School of Technology
• Simon Baker's List
• TQS Journal Clubs
• Trust & Technology Initiative - interesting events
• bld31
• custom
• ndk22's list
• ob366-ai4er
• rp587
• yk373's list

Note that ex-directory lists are not shown.