Computer Science

Given many identical copies of a quantum particle, what's the chance measuring their overall angular momentum yields zero? We show how to frame this problem as an optimization problem over a matrix group. We'll then discuss the relationship between this optimization problem and invariant theory, quantum tomography, and the Jacobian conjecture. This talk is based on the joint work https://arxiv.org/abs/2004.14872 with Michael Walter.

I plan to survey some parts of Strassen's seminal body of work on the theory of asymptotic spectra, in which optimization and symmetry play crucial roles. In particular, I will motivate and explain the notion of asymptotic spectra, Strassen's duality theorem (far reaching generalization of linear programming duality, with connections to Positivstellensatz), and Strassen's connectivity theorem of the spectra of matrix multiplication.

Groups and symmetries are at the heart of many problems in statistics and data analysis. I will focus on parameter estimation in statistical models via maximum likelihood estimation. We will see connections between maximum likelihood estimation, linear algebra, and invariant theory. The group or symmetric structure of a statistical model can be used to capture the existence and uniqueness of a maximum likelihood estimate, as well as to suggest suitable algorithms to find it. This talk is based on joint work with Carlos Améndola, Kathlén Kohn, Visu Makam, and Philipp Reichenbach.

Symmetries play a unifying role in physics and many other sciences. In deep learning, symmetries have been incorporated into neural networks through the concept of equivariance. One of the major benefits is that it will reduce the number parameters through parameter sharing and as such can learn with less data. In this talk I will ask the question, can equivariance also help in RL? Besides the obvious idea of using equivariant value functions, we explore the idea of deep equivariant policies. We make a connection between equivariance and MDP homomorphisms, and generalize to distributed multi-agent settings.   Joint work with Elise van der Pol (main contributor), Herke van Hoof and Frans Oliehoek. 

The matrix normal model, the family of Gaussian matrix-variate distributions whose covariance matrix is the Kronecker product of two lower dimensional factors, is frequently used to model matrix-variate data. The tensor normal model generalizes this family to Kronecker products of three or more factors. We study the estimation of the Kronecker factors of the covariance matrix in the matrix and tensor models. We show nonasymptotic bounds for the error achieved by the maximum likelihood estimator (MLE) in several natural metrics. In contrast to existing bounds, our results do not rely on the factors being well-conditioned or sparse. For the matrix normal model, all our bounds are minimax optimal up to logarithmic factors, and for the tensor normal model our bound for the largest factor and overall covariance matrix are minimax optimal up to constant factors provided there are enough samples for any estimator to obtain constant Frobenius error. In the same regimes as our sample complexity bounds, we show that an iterative procedure to compute the MLE known as the flip-flop algorithm converges linearly with high probability. Our main tool is geodesic strong convexity in the geometry on positive-definite matrices induced by the Fisher information metric. This strong convexity is determined by the expansion of certain random quantum channels. We also provide numerical evidence that combining the flip-flop algorithm with a simple shrinkage estimator can improve performance in the undersampled regime.

There has been enormous progress in the last few years in designing neural networks that respect the fundamental symmetries and coordinate freedoms of physical law. Some of these frameworks make use of irreducible representations, some make use of high-order tensor objects, and some apply symmetry-enforcing constraints. Different physical laws obey different combinations of fundamental symmetries, but a large fraction (possibly all) of classical physics is equivariant to translation, rotation, reflection (parity), boost (relativity), and permutations. Here we show that it is simple to parameterize universally approximating polynomial functions that are equivariant under these symmetries, or under the Euclidean, Lorentz, and Poincaré groups, at any dimensionality d. The key observation is that nonlinear O(d)-equivariant (and related-group-equivariant) functions can be universally expressed in terms of a lightweight collection of scalars -- scalar products and scalar contractions of the scalar, vector, and tensor inputs. We complement our theory with numerical examples that show that the scalar-based method is simple, efficient, and scalable.

We report on the geometric structure of symmetry adapted PSD cones and symmetry adapted Gram spectrahedra of symmetric polynomials. We determine the dimension of symmetry adapted PSD cones, describe its extreme rays, and discuss the structure of its matrix representations. We also focus on symmetry adapted Gram spectrahedra of symmetric binary forms, quadrics, ternary quartics and sextics. In particular, we characterize extreme points of these spectrahedra for symmetric binary forms that are of rank two, and we report what we know about the facial structure of the same spectrahedra. The talk will be based on two collaborations, one with Alex Heaton and Isabelle Shankar, and another one with Matthew Heid.

Geometrically, a linear program is a polyhedron together with an orientation of its graph. A simplex method determines a path from any given starting vertex to the sink. The centerpiece of any simplex algorithm is the pivot rule that successively selects outgoing edges along the path. We introduce normalized-weight pivot rules, a class of pivot rules that are memory-less, that subsume many of the most-used pivot rules, and that can be parametrized in a natural continuous manner. We introduce two polytopes that capture the behavior of normalized-pivot rules on polytopes and linear programs. On the one hand, this gives a new perspective on the performance of pivot rules. On the other hand, our constructions generalize classical constructions (e.g. monotone path polytopes) and objects (e.g. permutahedra, associahedra, multiplihedra) from geometric combinatorics, This is joint work with Alex Black, Jesus De Loera, and Niklas Lütjeharms.

We study the average complexity of solving structured polynomial systems that are characterised by a low evaluation cost, as opposed to the dense random model previously used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as black-box evaluation program. Secondly, we introduce a universal model of random polynomial systems with prescribed evaluation complexity L. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with n equations of degree at most d in n variables with only poly(n,d) L operations with high probability. This exceeds the expectations implicit in Smale's 17th problem. This is joint work with Felipe Cucker and Pierre Lairez, see arXiv:2010.10997.

This talk will be very informal: I will discuss ongoing research with open questions and partial results. We study the asymptotic consistency of modern interpolating methods, including deep networks, in both classification and regression settings. That is, we consider learning methods which scale the data size while simultaneously scaling the model size, in a way which always interpolates the train set. We present empirical evidence that, perhaps contrary to intuitions in theory, many natural interpolating learning methods are *inconsistent* for a wide variety of distributions. That is, they do not approach Bayes-optimality even in the limit of infinite data. The message is, in settings with nonzero Bayes risk, overfitting is not benign: interpolating the noise significantly harms the classifier, to the point of preventing consistency. This work is motivated by: (1) understanding differences between the overparameterized and underparameterized regime, (2) guiding theory towards more "realistic" assumptions to capture deep learning practice, and (3) understanding common structure shared by "natural" interpolating methods. Based on joint work with: Neil Mallinar, Amirhesam Abedsoltan, Gil Kur, and Misha Belkin. And is a follow-up work to the paper "Distributional Generalization", joint with Yamini Bansal.

It is well known that, at a random initialization, as their width approaches infinity, neural networks can be well approximated by Gaussian processes. We quantify this phenomenon by providing non-asymptotic convergence rates in the space of continuous functions. In the process, we study the Central Limit Theorem in high and infinite dimensions, as well as anti-concentration properties of polynomials with random variables

We obtain limiting spectral distribution of empirical conjugate kernel and neural tangent kernel matrices for two-layer neural networks with deterministic data and random weights. When the width of the network grows faster than the size of the dataset, a deformed semicircle law appears. In this regime, we also calculate the asymptotic test and training errors for random feature regression. Joint work with Zhichao Wang (UCSD).