Colloquium: Tuesday Feb 13, 2024. Speaker: Nadav Dym (Technion). Title: “Approximation and Separation Results for Group Equivariant Machine Learning”.
In many machine learning tasks, the goal is to learn an unknown function which has some known group symmetries. Equivariant machine learning algorithms exploits this by devising architectures (=function spaces) which have these symmetries by construction. Examples include convolutional neural networks which respect translation symmetries, and neural networks for graphs or multisets which respect their permutation symmetries. The development and analysis of these algorithms involves (basic) mathematical tools from representation theory, classical invariant theory, and in our case, real algebraic geometry and model theory.
A common theoretical requirement of symmetry based architecture is that they will be able to separate any two objects which are not related by a group symmetry . We will review results showing that under very general assumptions such a symmetry preserving separating mapping f exists, and the embedding dimension can be taken to be just over twice the dimension of the data. We will then propose a general methodology for efficient computation of such f using random invariants, based on a ‘finite witness theorem’. This methodology we develop is a generalization of the algebraic geometry argument used for the well known proof of phase retrieval injectivity. Furthermore, borrowing tools from the study of o-minimal systems, we show that this methodology can work with analytic as well as algebraic functions and constraints. In particular, we will show that standard permutation invariant architectures for multisets are separating, if and only if they use analytic rather than piecewise linear activation functions.
