This is the kickoff workshop for the Emmy-Noether Research Group “Numerical and Probabilistic Nonlinear Algebra”. The workshop will take place during September 20-21, 2021. The first day (Monday) will be the “Data Day” and the second day (Tuesday) will be the “Random Day”. The invited speakers will cover topics at the intersection of data science, probability and nonlinear algebra.
Learning with neural networks relies on the complexity of the representable functions, but more importantly, the particular assignment of typical parameters to functions of different complexity. Taking the number of activation regions as a complexity measure, recent works have shown that the practical complexity of deep ReLU networks is often far from the theoretical maximum. In this work we show that this phenomenon also occurs in networks with maxout (multi-argument) activation functions and when considering the decision boundaries in classification tasks. We also show that the parameter space has a multitude of full-dimensional regions with widely different complexity, and obtain nontrivial lower bounds on the expected complexity. Finally, we investigate different parameter initialization procedures and show that they can increase the speed of convergence in training. The linear regions of the functions represented by a maxout network correspond to the faces of polytopes obtained by building convex hulls and Minkowski sums of polytopes. Hence these results can be interpreted as statements about the expected number of faces of certain compositions of random polytopes. This is joint work with Hanna Tseran https://arxiv.org/abs/2107.00379
This talk is motivated by probabilistic models of random monomial ideals that mirror and extend those from random graphs and simplicial complexes literatures. Our results provide precise probabilistic statements about various algebraic invariants of (coordinate rings of) monomial ideals: the probability distributions, expectations and thresholds for events involving monomial ideals with given Hilbert function, Krull dimension, first graded Betti numbers. We will tackle the following related questions: What is a systematic way, in a probabilistic-model sense, to generate binomial ideals randomly? What can be (machine) learned from such data sets? How do we 'test out the waters' to see if a problem is 'learnable'? How do we generate, share, and make available large training data sets for machine learning in computational algebra? These topics are based on joint work with various collaborators and students and form a two-step process in learning on algebraic structures.
In science and engineering, we regularly face polynomial optimization problems, that is: minimize a real, multivariate polynomial under polynomial constraints. Solving these problems is essentially equivalent to certifying of nonnegativity of real polynomials -- a key problem in real algebraic geometry since the 19th century. Since this is a notoriously hard to solve problem, one is interested in certificates that imply nonnegativity and are easier to check than nonnegativity itself. In particular, a polynomial is nonnegative if it is a sums of squares (SOS) of other polynomials. Being an SOS can be detected effectively via semidefinite programming (SDP) in practice.In 2014, Iliman and I introduced a new certificate of nonnegativity based on sums of nonnegative circuit polynomials (SONC), which I have developed further since then both in theory and practice joint with different coauthors. In particular, these certificates are independent of sums of squares and can be computed via relative entropy programs.In this talk, I will give an introduction to the world of polynomial optimization, nonnegativity, SOS, and SONC.
A translation surface is a collection of polygons in the plane with parallel sides identified by translation to form a surface with a singular Euclidean structure. Closed geodesics on a translation surface are straight lines which start and end at a vertex of one of the polygons. Through some concrete examples we will give probabilistic results on counting closed geodesics for certain families of translation surfaces. These translation surfaces live in SL(2,R) orbit closures that are in fact algebraic varieties in the moduli space of translation surfaces, and are equipped with a natural SL(2,R) invariant probability measure.
Point clouds appear naturally in data analysis and machine learning when studying samples or related constructions like persistence homology. Based on ideas from stochastic geometry, generic behaviour of such clouds can be modelled via point processes and here we focus on the case of Poisson point processes. In particular, using Vietoris-Rips or $C\v{e}ch$ complexes this yields models for random simplicial complexes. In this talk we discuss recent results from an algebraic and combinatorial perspective.
We first discuss image formation in computer vision (modelling pinhole cameras as projections in projective space) and the associated (complex) algebraic descriptions. The reverse problem is called scene reconstruction which is our second topic. Along the way, we will see real algebraic refinements of the established complex algebraic picture capturing that the constraints that images are taken of an actual three-dimensional scene in real projective space and that the scene is in front of each camera.
Let $X_1,X_2,\ldots, X_n$ be $n$ random points drawn uniformly at random from the $d$-dimensional unit ball. What is the expected number of $k$-dimensional faces of their convex hull $[X_1,\ldots, X_n]$? Let $Y_1,\ldots, Y_{d+1}$ be $d+1$ random points sampled uniformly at random on the unit sphere in $\mathbb R^d$. What is the expected sum of solid angles of the simplex with vertices at $Y_1,\ldotyY_{d+1}$? We shall review recent results on these and some other questions of stochastic geometry.
We show that every multilinear map between Euclidean spaces induces a unique, continuous, Minkowski multilinear map of the corresponding real cones of zonoids. Applied to the wedge product of the exterior algebra Λ(V ) of a Euclidean space V, this defines the structure of a commutative, associative, and ordered ring on the space A(V ) of virtual zonoids of Λ(V ), which we call the zonoid algebra of V. Our construction incorporates the notion of mixed volume from convex geometry via the length of zonoids (first intrinsic volume), which can be thought of as their average diameter. We also analyze a similar construction based on the complex wedge product on Cn, which naturally leads to the new notion mixed J-volume. These constructions allow to express the expected absolute determinant of random matrices in terms of zonoids. This work prepares the ground for a probabilistic intersection theory for compact homogenous spaces. Ongoing work with Paul Breiding, Antonio Lerario and Leo Mathis.
We review some basic concepts in the interplay of Ricci curvature and Brownian motion on Riemannian manifolds. The second part is devoted to some new results for the case of sticky reflecting boundary diffusion. Such processes interpolate between plain Neumann reflection in the interior and surface diffusion on the boundary. We present new spectral gap estimates in terms of Ricci curvature in the interior and mean curvature on the boundary. (Joint work with Victor Marx and Vitalii Konarovskyi.)
Participants
Rida Ait El Manssour
MPI MiS
Arthur Bik
Max Planck Institute for Mathematics in the Sciences
Marie Brandenburg
MPI MiS
Paul Breiding
Max Planck Institute for Mathematics in the Sciences
Peter Bürgisser
TU Berlin
Timo de Wolff
TU Braunschweig
Mareike Dressler
MPI MiS
Marzieh Eidi
MPI
Henrik Eisenmann
MPI MIS Leipzig
Samantha Fairchild
MPI MiS
Marina Garrote-López
Max Planck Institute for Mathematics in the Sciences
Fulvio Gesmundo
Max Planck Institute for Mathematics in the Sciences
Zakhar Kabluchko
University of Münster
Chiara Meroni
MPI MiS
Guido Montufar
UCLA / MPI MIS
Raffaella Mulas
MPI MiS
Sonja Petrovic
Illinois Institute of Technology
Irem Portakal
MPI Leipzig
Kemal Rose
MPI Leipzig
Artem Sapozhnikov
Universität Leipzig
Elima Shehu
The Max Planck Institute for Mathematics in the Sciences
Rainer Sinn
Universität Leipzig
Bernd Sturmfels
Max Planck Institute for Mathematics in the Sciences
Simon Telen
MPI MiS Leipzig
André Uschmajew
Max Planck Institute for Mathematics in the Sciences
Max von Renesse
Universität Leipzig
Scientific Organizers
Paul Breiding
Max Planck Institute for Mathematics in the Sciences
Administrative Contact
Saskia Gutzschebauch
Max Planck Institute for Mathematics in the Sciences
Contact by email