## Structure vs Randomness in Complexity Theory

Rahul Santhanam

University of Oxford

April 20, 2020

The dichotomy between structure and randomness plays an important role in areas such as combinatorics and number theory.

Rahul Santhanam

University of Oxford

April 20, 2020

The dichotomy between structure and randomness plays an important role in areas such as combinatorics and number theory.

Felix Otto

Max Planck Institute Leipzig

April 20, 2020

We present a purely variational approach to the regularity theory for the Monge-Ampère equation, or rather optimal transportation, introduced with M. Goldman. Following De Giorgi’s philosophy for the regularity theory of minimal surfaces, it is based on the approximation of the displacement by a harmonic gradient, which leads to a One-Step Improvement Lemma, and feeds into a Campanato iteration on the C1,α-level for the displacement, capitalizing on affine invariance.

Nicholas Wilkins

University of Bristol

April 17, 2020

There is growing interest in looking at operations on quantum cohomology that take into account symmetries in the holomorphic spheres (such as the quantum Steenrod powers, using a Z/p-symmetry). In order to prove relations between them, one needs to generalise this to include equivariant operations with more marked points, varying domains and different symmetry groups. We will look at the general method of construction of these operations, as well as two distinct examples of relations between them.

Raghu Mahajan

Member, School of Natural Sciences, Institute for Advanced Study

April 17, 2020

In this talk we will present details of quantum extremal surface computations in a simple setup, demonstrating the role of entanglement islands in resolving entropy paradoxes in gravity. The setup involves eternal AdS2 black holes in thermal equilibrium with auxiliary bath systems. We will also describe the extension of this setup to higher dimensions using Randall-Sundrum branes.

April 16, 2020

Organizers: Sanjeev Arora, Sanjoy Dasgupta, Roger Grosse, Sham Kakade and Bin Yu.

Cynthia Rudin

April 16, 2020

While the trend in machine learning has tended towards more complex hypothesis spaces, it is not clear that this extra complexity is always necessary or helpful for many domains. In particular, models and their predictions are often made easier to understand by adding interpretability constraints. These constraints shrink the hypothesis space; that is, they make the model simpler. Statistical learning theory suggests that generalization may be improved as a result as well. However, adding extra constraints can make optimization (exponentially) harder.

Zico Kolter

April 16, 2020

In this talk, I will first introduce our recent work on the Deep Equilibrium Model (DEQ). Instead of stacking nonlinear layers, as is common in deep learning, this approach finds the equilibrium point of the repeated iteration of a single non-linear layer, then backpropagates through the layer directly using the implicit function theorem. The resulting method achieves or matches state of the art performance in many domains (while consuming much less memory), and can theoretically express any "traditional" deep network with just a single layer.

Chelsea Finn

April 16, 2020

Despite the success of deep learning, much of its success has existed in settings where the goal is to learn one, single-purpose function from data. However, in many contexts, we hope to optimize neural networks for multiple, distinct tasks (i.e. multi-task learning), and optimize so that what is learned from these tasks is transferable to the acquisition of new tasks (e.g. as in meta-learning).

Anirudh Goyal

April 16, 2020

Physical processes in the world often have a modular structure, with complexity emerging through combinations of simpler subsystems. Machine learning seeks to uncover and use regularities in the physical world. Although these regularities manifest themselves as statistical dependencies, they are ultimately due to dynamic processes governed by physics. These processes are often independent and only interact sparsely..Despite this, most machine learning models employ the opposite inductive bias, i.e., that all processes interact.

Percy Liang

April 16, 2020

Standard machine learning produces models that are highly accurate on average but that degrade dramatically when the test distribution deviates from the training distribution. While one can train robust models, this often comes at the expense of standard accuracy (on the training distribution). We study this tradeoff in two settings, adversarial examples and minority groups, creating simple examples which highlight generalization issues as a major source of this tradeoff.