SPS-DSI (DEGAS) Webinar: SymmetricDiffusers: Learning Discrete Diffusion on Finite Symmetric Groups
Date: 4 December 2024
Time: 11:00 AM ET (New York time)
Presenter(s): Renjie Liao
DEGAS Webinar Series is an event initiated by the Data Science Initiative (DSI) of the IEEE Signal Processing (SP) Society. The goal is to provide the SP community with updates and advances in learning and inference on graphs. Signal processing and machine learning often deal with data living in regular domains such as space and time. This webinar series will cover the extension of these methods to network data, including topics such as graph filtering, graph sampling, spectral analysis of network data, graph topology identification, geometric deep learning, and so on. Applications can for instance be found in image processing, social networks, epidemics, wireless communications, brain science, recommender systems, and sensor networks. These bi-weekly webinars will be hosted on Zoom, with recordings made available in the IEEE Signal Processing Society’s YouTube channel following the live events. Further details about live and streaming access will follow. Each webinar speaker will give a lecture, which is followed by Q&A and discussions.
Abstract
Finite symmetric groups Sn are essential in fields such as combinatorics, physics, and chemistry. However, learning a probability distribution over Sn poses significant challenges due to its intractable size and discrete nature. In this paper, we introduce SymmetricDiffusers, a novel discrete diffusion model that simplifies the task of learning a complicated distribution over Sn by decomposing it into learning simpler transitions of the reverse diffusion using deep neural networks. We identify the riffle shuffle as an effective forward transition and provide empirical guidelines for selecting the diffusion length based on the theory of random walks on finite groups. Additionally, we propose a generalized Plackett-Luce (PL) distribution for the reverse transition, which is provably more expressive than the PL distribution. We further introduce a theoretically grounded “denoising schedule” to improve sampling and learning efficiency. Extensive experiments show that our model achieves state-of-the-art or comparable performances on solving tasks including sorting 4-digit MNIST images, jigsaw puzzles, and traveling salesman problems. Our code is released at this https url.
Biography
Renjie Liao received the B.Eng. in Automation in 2011 from Beihang University, the M.Phil. degree in computer science in 2015 from the Chinese University of Hong Kong and the Ph.D. in computer science in 2021 from the University of Toronto under the supervision of Richard Zemel and Raquel Urtasun. During his Ph.D., he worked as a Senior Research Scientist at Uber Advanced Technologies Group.
He is an assistant professor in the Department of Electrical and Computer Engineering and an associated member of the Department of Computer Science at the University of British Columbia (UBC). He is a faculty member at the Vector Institute and a Canada CIFAR AI Chair. Before joining UBC, he was a Visiting Faculty Researcher at Google Brain, working with Geoffrey Hinton and David Fleet.
Dr. Liao is broadly interested in machine learning and its intersection with computer vision, self-driving, healthcare, and other areas, with a focus on probabilistic and geometric deep learning.
