Machine Learning on Non-Euclidean Domains: Powersets, Lattices, Posets

In this presentation, Chris will discuss the key findings from his Ph.D. research on Fourier-sparse learning on powersets, lattices, and partially ordered sets (posets). His research builds upon and expands the recent signal processing theory for set functions, which is an instantiation of algebraic signal processing theory (ASP) to the powerset domain.

ASP offers a theoretical framework for the axiomatic derivation of signal processing operations such as convolutional filters and Fourier transforms from appropriate shift operations that capture the characteristics of a specific domain. When applied to the powerset domain, ASP gives rise to four novel non-orthogonal Fourier transforms. Chris has developed sparse Fourier transform algorithms for these novel bases, substantially expanding the family of learnable set functions. The resulting Fourier-sparse representations are particularly well-suited for combinatorial auctions, where bidders place bids on subsets of goods, and their preferences are modelled using set functions. Inspired by this observation, we designed an auction mechanism that utilizes Fourier-sparse bidder representations.

Chris Wendler earned his B.Sc. in Mathematics and M.Sc. in Computer Science from Leopold-Franzens-University in Innsbruck, Austria, in 2017 and 2016, respectively. In 2023, he obtained his Ph.D. in Computer Science from ETH Zurich. His doctoral research focused on signal processing and machine learning in non-Euclidean domains with a focus on powersets, lattices, and posets.