Algebra, Statistics, and Optimization

This seminar features talks on interdisciplinary research which involves applications of fields related to algebra, geometry, topology, and combinatorics to fields like statistics, optimization, computer science, electrical engineering, biology, physics, and other sciences. One of the main goals of the seminar is to connect people from pure mathematics with people from applied fields.


Contacts:    Daniel Bernstein   dibernst@mit.edu;   Diego Cifuentes  diegcif@mit.edu;   Elisa Perrone   eperrone@mit.edu; Elina Robeva   erobeva@mit.edu;

Mailing list: If you would like to be added to the mailing list, please contact one of the organizers above.

Spring 2019


In the spring of 2019, the seminar will resume meeting every other week. It now has a new new name: "Seminar on Algebra, Statistcs, and Optimization".
Time: 12-1pm
Place: E18-304 (IDSS)

February 21, 2019, 12 - 1pm:   Yuhao Wang   MIT
Title:   Provable Algorithms for Statistical Challenges in Data Driven Decision Making
Abstract:   Data-driven decision making is now becoming increasingly important in various disciplines, including health care, finance and business analytics. To make data-driven decisions in large-scale systems, learning the statistical associations of different elements is not sufficient. Algorithms need to be equipped with the ability to learn the underlying causal mechanism. Meanwhile, intelligent decision making also requires us to effectively incorporate domain knowledge from various application domains to improve the statistical efficiency as well as the robustness of existing statistical methods. Probabilistically, such domain knowledge can be incorporated as structural constraints on the underlying distribution. Exploiting these underlying structures calls for new statistical methods for inference with various distributional constraints. In this talk, I will present my recent progresses for addressing the two fundamental statistical challenges stated above, namely 1) establishing the underlying causal mechanism in complex systems, and 2) incorporating structural constraints to statistical inference.

Fall 2018


In the fall of 2018, we are going to hold an Applied Algebra Day. Here are the logistics.

Applied Algebra Day

Date: Saturday Novermber 17 2018
Time: 9:30AM - 5PM
Location: E17-304 (access from 50 Ames Street)
Titles and abstracts

Speakers and program:

  • 9:30am      Solving elliptic PDEs on curves and surfaces                                                                        Jonathan Hauenstein, University of Notre Dame
  • 10am         Oriented Gaussoids                                                                                                               Thomas Kahle, OvGU Magdeburg
  • 10:30am    -- coffee break --
  • 11am         The degree of the central curve of semidefinite programming                                               Elias Tsigaridas, Inria Paris
  • 11:30am    A minimal approach to minimal problems in 3D reconstruction                                             Anton Leykin, GATech
  • 12pm         Distinguishing and Inferring Phylogenetic Networks                                                              Elizabeth Gross, U Hawaii
  • 12:30pm    -- lunch break --
  • 2pm           Rank-metric codes and q-polymatroids                                                                                 Elisa Gorla, U Neuchatel
  • 2:30pm      Positively Hyperbolic Varieties and Tropical Geometry                                                          Josephine Yu, GATech
  • 3pm           Tell the truth and never lose with tropical geometry                                                               Ngoc Tran, UT Austin
  • 3:30pm      -- coffee break --
  • 4pm           Tropical Geometry of Deep Neural Networks                                                                         Gregory Naitzat, UChicago
  • 4:30pm      Fast Computations of Monomial Ideal Invariants Using Constraint Integer Programming     Lily Silverstein, UC Davis
  • 5pm           Robust Estimation of High-Dimensional Graphical Models under Total Positivity                  Yuhao Wang, MIT



Spring 2018


April 23, 2018, 1:30-2:30pm:   Jesús De Loera   University of California, Davis
Title:   Random Monomial Ideals
Abstract:   Randomness is a key algorithmic tool in algebra. In this talk I will discuss our recent work describing the random behavior of monomial ideals. Our work is a natural generalization of classical work on random graphs and random simplicial complexes. Under this model we outlined some basic properties of random monomial ideals. For example, I will present theorems about the probability distributions, expectations and thresholds for events of monomial ideals with given Krull dimension, Hilbert function, and the average behavior of minimal-free resolutions.

April 23, 2018, 2:45-3:45pm:   Anna Seigal   University of California, Berkeley
Title:   Ranks and Symmetric Ranks of Cubic Surfaces
Abstract:   We study cubic surfaces as symmetric tensors of format 4 x 4 x 4. We consider the non-symmetric rank and the symmetric rank of cubic surfaces, and show that the two notions coincide over the complex numbers. As part of our analysis, we give a test for symmetric rank given by the non-vanishing of certain discriminants. The corresponding algebraic problem concerns border ranks. We show that the non-symmetric border rank coincides with the symmetric border rank for cubic surfaces, and obtain minimal ideal generators for the symmetric analogue to the secant variety from the salmon conjecture. We also discuss how the results extend to tensors of larger sizes.

Fall 2017


September 19, 2017:  Carlos Améndola  TU Berlin
Title:   Discrete Gaussian Distributions Via Theta Functions
Abstract:   Maximum entropy probability distributions are important for information theory and relate directly to exponential families in statistics. Having the property of maximizing entropy can be used to define a discrete analogue of the classical continuous Gaussian distribution. We present a parametrization of such a density using the Riemann Theta function, use it to derive fundamental properties which include computing its characteristic function, and exhibit connections to the study of abelian varieties. This is ongoing joint work with Daniele Agostini (HU Berlin).


October 3, 2017:   Kaie Kubjas   MIT
Title:   Geometry and Maximum Likelihood Estimation of the Binary Latent Class Model
Abstract:   The Expectation-Maximization algorithm is commonly used for the maximum likelihood estimation of the latent class models. However, it does not guarantee finding the global optimum. We study the geometry of the binary latent class model and in the case of three observed binary variables, apply it to obtain closed formulas for the MLE. The second approach is taken through the study of the EM fixed point ideal. In the case of a binary latent class model with a binary or ternary hidden variable, we show how to get the boundary stratification of the model by decomposing the EM fixed point ideal. This talk is based on the joint work with Elizabeth Allman, Hector Banos Cervantes, Robin Evans, Serkan Hosten, Daniel Lemke, John Rhodes and Piotr Zwiernik.

October 17, 2017:   Jose Israel Rodriguez   University of Chicago
Title:   Trace tests in numerical algebraic geometry
Abstract:   Numerical algebraic geometry uses numerical algorithms to study algebraic varieties, which are sets defined by polynomial equations. It is becoming a core tool in applications of algebraic geometry outside of mathematics. Its fundamental concept is a witness set which gives a representation of a variety that may be manipulated on a computer. The trace test is used to verify that a witness set is complete and provide stopping criteria for algorithms. In this talk we discuss witness sets and how the trace test is used in applications. If time permits we show how a dimension reduction leads to a practical trace test for algebraic varieties in product spaces, which is the natural setting for solutions of parameterized polynomial systems. A background in algebraic geometry will not be assumed.

October 31, 2017:   Elisa Perrone   MIT
Title:   The geometry of discrete copulas
Abstract:   Discrete copulas are fascinating geometric objects of great importance for empirical modeling in the applied sciences. In this work we analyze mathematical features of discrete copulas, i.e. restrictions of copula functions to non-square uniform grid domains. In particular, we first introduce discrete copulas and briefly discuss their applications to dependence modeling. Then, we highlight fundamental connections between copulas and discrete geometry. Finally, we present a geometric approach to describe families of discrete copulas through the properties of their associated polytopes. This talk is based on a joint work with L.Solus (KTH, Sweden) and C. Uhler (MIT, USA).

November 14, 2017:   Anirbit Mukherjee   Johns Hopkins University
Title:   Mathematics of Neural Networks
Abstract:   A plethora of exciting mathematics questions have gotten raised in trying to explain the resurgence of neural networks in being able to execute complex artificial intelligence tasks. In this talk I will give a brief overview of some of the questions that me and Amitabh Basu (with other collaborators) have been exploring. We will start from the basic definition of neural networks and will describe various results that we have gotten about the space of functions that these "architectures" represent. We will particularly focus on (1) our recent results (https://arxiv.org/abs/1711.03073) proving a first of its kind lower bounds on the size of high depth neural circuits representing certain Boolean functions and (2) our results trying to formalized the connection between autoencoders and sparse coding (https://arxiv.org/abs/1708.03735).

November 21, 2017:   Daniel Bernstein   North Carolina State University
Title:   Algebraic geometry of low-rank matrix completion
Abstract:   Given a subset of entries of a matrix, the low-rank matrix completion problem asks for the values of the missing entries that minimize rank. This problem and related ones appear in many applications including collaborative filtering (e.g. the ''Netflix problem''), computer vision, and certifying existence of MLEs in Gaussian graphical models. In this talk, I will discuss the algebraic-geometric approach to this problem, including some classification results about relevant algebraic matroids, and complications that arise when one requires that the completion be real-valued.

November 28, 2017:   Heather Harrington   Oxford
Title:   Computational algebraic geometry for topological data analysis
Abstract:   I will present how computational algebra can be used to study problems arising in topological data analysis. I will motivate each of these problems using applications. Specifically I will discuss two ongoing projects, one using numerical algebraic geometry to sample points on real algebraic varieties. The other project proposes new interpretable invariants for multi-parameter persistent homology using computational commutative algebra.

December 5, 2017:   David Spivak   MIT
Title:   Diagrams for tensor networks and systems of nonlinear equations
Abstract:   The same category-theoretic formalism describes both tensor networks and systems of nonlinear relations (including nonlinear equations, inequalities, etc.). More precisely, there is an operad, called Cospan, for which both tensor networks and nonlinear systems are algebras. A morphism between these algebras provides a method for approximating solutions to nonlinear systems using tensor arithmetic. I will explain these ideas, not assuming any background in category theory.

December 12, 2017:   Yang Qi   University of Chicago
Title:   Geometry of tensor approximations and tensor decompositions
Abstract:   Tensors are closely related to secant varieties. It is known the affine cone of the r-th secant variety of the Segre variety is the set of tensors whose border rank is less than or equal to r. Similarly, we have a geometric interpretation of symmetric tensors. By studying the geometry of these secant varieties, we can derive interesting properties of tensors. In this talk, we will show a general complex (symmetric) tensor has a best (symmetric) rank-r approximation, and we will study the relations between the (border) rank and the symmetric (border) rank of a general symmetric tensor. The talk is based on joint works with Lek-Heng and Mateusz Michalek.