Ali Mohammad Nezhad, CMU

Optimization and Real Algebraic Geometry Seinar

The Optimization and Real Algebraic Geometry seminar was organized by me and Professor Saugata Basu on Thursdays at 2:00 PM (EDT) in Spring 2022. We met on Zoom and recorded the seminars. The recordings are available on our Youtube Channel.

Date: Feb. 24, 2022

Time: 3:00 PM (EDT)

Speaker: Annie Raymond, Department of Mathematics and Statistics, University of Massachusetts

Title: Tropicalization of graph profiles

Abstract: The number of homomorphisms from a graph H to a graph G, denoted by hom(H;G), is the number of maps from V(H) to V(G) that yield a graph homomorphism, i.e., that map every edge of H to an edge of G. Given a fixed collection of finite simple graphs {H_1, ..., H_s}, the graph profile is the set of all vectors (hom(H_1; G), ..., hom(H_s; G)) as G varies over all graphs. Graph profiles essentially allow us to understand all polynomial inequalities in homomorphism numbers that are valid on all graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known. To simplify these objects, we introduce their tropicalization which we show is a closed convex cone that still captures interesting combinatorial information. We explicitly compute these tropicalizations for some sets of graphs, and relate the results to some questions in extremal graph theory. This is joint work with Greg Blekherman, Mohit Singh and Rekha Thomas.

Recording: https://youtu.be/fQo_w6fBefU

Date: Mar. 10, 2022

Time: 3:00 PM (EDT)

Speaker: Daniel Perucci, Department of Mathematics, University of Buenos Aires

Title: Some extensions of Putinar's Positivstellensatz to non-compact sets of cylindrical type

Abstract: One of the most important results in the theory of sums of squares and certificates of non-negativity is Putinar's Positivstellensatz. Given a basic closed semialgebraic set $S \subset \mathbb{R}^n$ defined by polynomial inequalities $g_1 \ge 0, \dots, g_s \ge 0$, under a certain hypothesis on $g_1, \dots, g_s$ (which implies that $S$ is compact), this theorem states that every polynomial $f$ positive on $S$ admits a certificate of its non-negativity on $S$ using sum of squares. In this talk, we will discuss some extensions of this result to the case where $S$ isnon-compact of cylindrical type.

Recording: https://youtu.be/fQo_w6fBefU

Date: Mar. 31, 2022

Time: 3:00 PM (EDT)

Speaker: Antonio Lerario, SISSA

Title: The zonoid algebra

Abstract: In this seminar I will discuss the so called "zonoid algebra", a construction introduced in a recent work (joint withBreiding, Bürgisser and Mathis) which allows to put a ring structure on the set of zonoids (i.e. Hausdorff limits\ of Minkowski sums of segments). This framework gives a new perspective on classical objects in convex geometry, and it allows to introduce new functionals on zonoids, in particular generalizing the notion of mixed volume. Moreover this algebra plays the role of a probabilistic intersection ring for compact homogeneous spaces. Joint work with P. Breiding, P. Bürgisser and L. Mathis.

Recording:https://youtu.be/h2YE_pfUw_Q

Date: Apr. 07, 2022

Time: 2:30 PM (EDT)

Speaker: Jose Israel Rodriguez, Department of Mathematics, University of Wisconsin-Madison

Title: Estimating Gaussian mixtures using sparse polynomial moment systems

Abstract: A fundamental problem in statistics is to estimate the parameters of a density from samples. There are several approaches to tackle this problem, but we will focus on the method of moments. Here, one takes empirical moments as estimates for the moments of the unknown distribution. It turns out, the moments of the distribution are often expressed as polynomials in the density’s parameters. Therefore, we recover parameter estimates by solving a nonlinear system of equations. In fact, we are solving a system of polynomial equations, and we are able to leverage the tools of Algebraic Statistics and Applied Algebraic Geometry. In this talk we consider a prominent class of models: mixtures of Gaussian distributions. Using empirical moments we recover the mean and variance of each component the mixture by solving a system of equations. The first part focuses on bounding the degree of these polynomial systems. Pearson studied the 2-mixture case by solvinga degree nine polynomial. We study the k-mixture case, which gives polynomial systems with much larger degree. Our techniques in\ volve polyhedral methods for solving sparse polynomial systems. A nice consequence of our proofs is that they yield a continuation method for finding the estimate to recover the parameters. The second part of the talk does density estimation for mixtures of high dimensional Gaussians (joint work with Julia Lindberg and Carlos Amendola, Arxiv: 2106.15675)

Recording: h ttps://youtu.be/NpH8B1MvFIM

Date: Apr. 21, 2022

Time: 2:00 PM (EDT)

Speaker: Jesus De Loera, Department of Mathematics, University of California, Davis

Title: The Polyhedral Geometry of All Simplex Pivot Rules

Abstract: Linear optimization is a simple yet fundamental building block in modern computing (e.g., without linear programs and branch-and-cut methods one would not have solvers for integer optimization). Dantzig's Simplex Method is one of the most popular algorithms for linear optimization. It was even named as one of the top ten algorithms in the 20th century. But despite all its success and popularity for the last 80 years we still do not fully understand it. There are still a number of open questions about its behavior and this talk is about how to choose a pivot rule?

Purely geometrically, a linear program (LP) is a polyhedron together with an orientation of its graph. A simplex method selects a directed path from an initial vertex to the sink (optimum) and thus determines an arborescence (of shortest monotone paths). The engine of any simplex method is a pivot rule that selects the outgoing arc for a current vertex. Pivot rules comein many forms and types but we are still ignorant whether there is one that can make the simplex method run in polynomial time. \ Somehow we need ways to grasp the set of all possible pivot rules. In this talk we show this set has a very natural polyhedral structure.

Classic results in parametric linear optimization explain the changes of objective function, e.g., the orientation and sink and for a pivot rule its associated arborescence. I present a new parametric analysisfor all pivot rules belonging to a certain class, memoryless pívot rules. It turns out there exist lovely polytopes, the\ 60;pivot rule polytopes, that parametrize all memoryless pívot rules of a given LP. This is an attempt to get a geometric/topological picture of the “ space of all pivot rules of an LP”.

I will present this entertaining story without assuming prior knowledge of linear programming or the simplex method. The story is related to performance of pivot rules, fiber polytopes, parametric linear programs, shadow-vertex-rules, realizations spaces of polytopes, and several classic polytopes make cameo appearances too. This is joint work with Alex Black (UC Davis), Niklas Lu ̈tjeharms (U. Frankfurt), and Raman Sanyal (U. Frankfurt).

Recording: https://youtu.be/fSZKdWytKwM

Date: Apr. 28, 2022

Time: 2:00 PM (EDT)

Speaker: Pravesh Kothari, Department of Computer Science, Carnegie Mellon University

Title: The Sum-of-Squares Approach to Clustering Gaussian Mixtures

Abstract: Sum-of-Squares is asystematic proof system for reasoning about real solutions to systems of multivariate polynomial inequalities over the real\ s. In the last few years, this proof system has been used to develop a principled method for designing efficient algorithms for average-case algorithmic problems - problems where the inputs are chosen according to some natural probability distribution. By relying on the relationship between sum-of-squares proofs and semidefinite programming, this method reduces designing an efficient algorithm for a given problem to giving a low-degree sum-of-squares certificate of the correctness of a purported solution.

In this talk, I'll give an overview of this method by focusing on two recent works on designingalgorithms for the problem of clustering mixtures of k Gaussians in d dimensions:

1) A d^( O(log^2 k) ) time algorithm for clustering mixtures of k Gaussians with spherical covariances that succeeds whenever the mixture is information-theoretically clusterable. This algorithm relies on using sum-of-squares certificates of subgaussian moments.

2) A $d^O(k^(O(k)))$ time algorithm for clustering mixtures of k arbitrary Gaussians that succeeds whenever the mixture is clusterable. This algorithm relies on sum-of-squares certificatesof hypercontractivity of degree 2 polynomials and anti-concentration of linear projections of Gaussians.

The talk should be accessible to a broad audience and should not require any prior knowledge ofthe problems/techniques. The talk is based on joint works with Jacob Steinhardt and Ainesh Bakshi.

Recording: https://youtu.be/tuAU-OHefG8

Date: May 05, 2022

Time: 2:00 PM (EDT)

Speaker: Alperen A. Ergür, Departmentof Mathematics, University of Texas at San Antonio

Title: Approximate Waring Decomposition

Abstract: The symmetric rank of real symmetric tensors, or equivalently real Waring-rank of homogenous polynomials, is a basic notion that has been studied both from theoretical and ``operational'' perspectives. We study real Waring-rank with a twist: we allow an epsilon room of error in the decomposition. This amounts to estimating the smallest rank within epsilon neighborhood of a given form. We present a few theorems and algorithms to estimate approximate Waring-rank and find approximate low-rank decomposition. To exploit real geometric structure of the problem we use tools from convex geometry and high dimensional probability, rather than availing to complex algebraic machinery. Joint work with Petros Valettas and Jesus Rebollo Bueno.

Recording: https://youtu.be/O4P5i8oT_Gw

Date: May 12, 2022

Time: 2:00 PM (EDT)

Speaker: Peter Scheiblechner, School of Engineering and Architecture, Lucerne University of Applied Sciences and Arts

Title: Effective de Rham Cohomology

Abstract: Grothendieck has proved that each class in the de Rham cohomology of a smooth complex affine variety can be represented by a differential form with polynomial coefficients. We prove a single exponential bound on the degrees of these polynomials for varieties of arbitrary dimension. More precisely, we show that the p-th de Rham cohomology of a smooth affine variety of dimension m and degree D can be represented by differential forms of degree (pD)^{O(pm)}. This result is relevant for the algorithmic computation of the cohomology, but is also motivated by questions in the theory of ordinary differential equations related to the infinitesimal Hilbert 16th problem.

Recording: https://youtu.be/3iBoeEU427M