Time and Date: Tuesdays 3:30 - 4:30
Unless otherwise noted, all talks will take place in Math Sciences Building 110 at the University of Missouri.
Organized by Tim Duff and Dan Edidin. Contact Tim if you want to be on the mailing list.
Title: Generic orbit recovery from invariants of very low degree.
Abstract: Motivated by the multi-reference alignment (MRA) problem and questions in equivariant neural networks we study the problem of recovering the generic orbit in a representation of a finite group from invariant polynomials of degree at most 3. We prove that in many cases of interest these low degree invariants are sufficient to recover the orbit of a generic vector.
Abstract: Density estimation for Gaussian mixture models is a classical problem in statistics that has applications in a variety of disciplines. Two solution techniques are commonly used for this problem: the method of moments and maximum likelihood estimation. This talk will discuss both methods by focusing on the underlying geometry of each problem.
Title: Homotopies for variational inference and approximate synthesis
Abstract: For parameterized systems, one standard problem is to determine the set of parameters which "best" fits given data. Two examples of this will be summarized in this talk, both of which can be solved using homotopies. The first is variational inference in which one searches in a parameterized family of probability distributions for a probability distribution that best fits the given data. The second is synthesizing a linkage whose coupler curve best approximates the given data. This talk is joint work with Emma Cobian, Fang Liu, and Daniele Schiavazzi (variational inference) and Aravind Baskar and Mark Plecnik (approximate synthesis).
Title: A fourth moment theorem for estimating subgraph counts in large graphs
Abstract: Given a large network one is often interested in efficiently estimating various local statistics. In this talk, we'll discuss the distribution of one possible estimator arising from counting monochromatic subgraphs in a random vertex colorings. We focus on the asymptotic normality of these counts, particularly for monochromatic triangles, and provide new, local influence-based necessary and sufficient conditions. The conditions we obtain combine ideas from Boolean analysis as well as classical fourth-moment theorems originating from normal approximation results in the Wiener space.
Abstract: We highlight a perhaps important but hitherto unobserved insight: The attention module in a ReLU-transformer is a cubic spline. Viewed in this manner, this mysterious but critical component of a transformer becomes a natural development of an old notion deeply entrenched in classical approximation theory. Conversely, if we assume the Pierce--Birkhoff conjecture, then every spline is also an encoder.
Abstract: Random geometric graphs are random graph models defined on metric spaces. Such a model is defined by first sampling points from a metric space and then connecting each pair of sampled points with probability that depends on their distance, independently among pairs. In this work we show how to efficiently reconstruct the geometry of the underlying space from the sampled graph under the manifold assumption, i.e., assuming that the underlying space is a low dimensional manifold and that the connection probability is a strictly decreasing function of the Euclidean distance between the points in a given embedding of the manifold in R^N. Our work complements a large body of work on manifold learning, where the goal is to recover a manifold from sampled points sampled in the manifold along with their (approximate) distances.
(Joint work with P. Jiradilok and E. Mossel).
Title: Two uniqueness results for the method-of-moments in cryo-EM
Abstract: This talk considers provable methods for cryo-electron microscopy, which is an increasingly popular imaging technique for reconstructing 3-D biological macromolecules from a collection of noisy and randomly oriented projection images, with applications in e.g., drug design. The talk will present two uniqueness guarantees for recovering these structures from the second moment of the projection images, as well as two associated numerical algorithms. Mathematically, the results boil down to ensuring unique solutions to highly structured non-linear equations.
Title: Quiver representations and the Paulsen Problem in Frame Theory
Parseval frames provide redundant encodings, with equal-norm Parseval frames offering optimal robustness against one erasure. However, constructing such frames can be challenging. The Paulsen Problem asks to determine how far an ε-nearly equal-norm Parseval frame is from the set of all equal-norm Parseval frames. In this talk, I will present an approach to the Paulsen’s problem based on quiver invariant theory.
Title: Is uniform expressivity for GNNs too restrictive?
Abstract: Uniform expressivity guarantees that a Graph Neural Network (GNN) can express a query without the parameters depending on the size of the input graphs. This property is desirable in applications in order to have number of trainable parameters that is independent of the size of the input graphs. Uniform expressivity of the two variable guarded fragment (GC2) of first order logic is a well-celebrated result for Rectified Linear Unit (ReLU) GNNs [Barcelo & al., 2020]. In this talk, we prove that uniform expressivity of GC2 queries is not possible for GNNs with a wide class of Pfaffian activation functions (including the sigmoid and tanh), answering a question formulated by [Grohe, 2021]. We also show that despite these limitations, many of those GNNs can still efficiently express GC2 queries in a way that the number of parameters remains logarithmic on the maximal degree of the input graphs. Furthermore, we demonstrate that a log-log dependency on the degree is achievable for a certain choice of activation function. This shows that uniform expressivity can be successfully relaxed by covering large graphs appearing in practical applications. Our experiments illustrates that our theoretical estimates hold in practice.
Abstract: Degree bounds have a long history in invariant theory. The Noether bound on the degrees of algebra generators for a ring of invariants is over a century old, and there is a vast literature sharpening and generalizing it. In the last two decades, there has also been an active program on degree bounds for invariants which are able to distinguish orbits as well as algebra generators can (known as separating invariants).
In this talk I make the case that generators for the field of rational invariants represent an exciting avenue for research on degree bounds as well. I present new lower and upper bounds. It will transpire that even the case of G=Z/pZ, uninteresting from the point of view of generating and separating invariants, has a story to tell for rational invariants. The methods involve the classical Minkowski “geometry of numbers”. I argue that this domain of inquiry is both interesting in itself and well-motivated by applications.
This talk is based on joint work with Thays Garcia, Rawin Hidalgo, Consuelo Rodriguez, Alexander Kirillov Jr., Sylvan Crane, Karla Guzman, Alexis Menenses, Maxine Song-Hurewitz, Afonso Bandeira, Joe Kileel, Jonathan Niles-Weed, Amelia Perry, and Alexander Wein