Scientific

Bandit learning of Nash equilibria in monotone games

Speaker: 
Maryam Kamgarpour
Date: 
Fri, Jan 29, 2021
Location: 
Zoom
Conference: 
PIHOT kick-off event
Abstract: 

Game theory is a powerful framework to address optimization and learning of multiple interacting agents referred to as players. In a multi-agent setting, the notion of Nash equilibrium captures a desirable solution as it exhibits stability, that is, no player has incentive to deviate from this solution. From the viewpoint of learning the question is whether players can learn their Nash equilibrium strategies with limited information about the game. In this talk, I address our work on designing distributed algorithms for players so that they can learn the Nash equilibrium based only on information regarding their experienced payoffs. I discuss the convergence of the algorithm and its applicability to a large class of monotone games.

Class: 

Scaling Optimal Transport for High dimensional Learning

Speaker: 
Gabirel Peyré
Date: 
Fri, Jan 29, 2021
Location: 
Zoom
Conference: 
PIHOT kick-off event
Abstract: 

Optimal transport (OT) has recently gained lot of interest in machine learning. It is a natural tool to compare in a geometrically faithful way probability distributions. It finds applications in both supervised learning (using geometric loss functions) and unsupervised learning (to perform generative model fitting). OT is however plagued by the curse of dimensionality, since it might require a number of samples which grows exponentially with the dimension. In this talk, I will explain how to leverage entropic regularization methods to define computationally efficient loss functions, approximating OT with a better sample complexity. More information and references can be found on the website of our book “Computational Optimal Transport” https://optimaltransport.github.io/

Class: 
Subject: 

Initial value problems viewed as generalized optimal transport problems with matrix-valued density fields

Speaker: 
Yann Brenier
Date: 
Fri, Jan 29, 2021
Location: 
Zoom
Conference: 
PIHOT kick-off event
Abstract: 

The initial value problem for many important PDEs (Burgers, Euler, Hamilton-Jacobi, Navier-Stokes equations, systems of conservation laws with convex entropy, etc…) can be often reduced to a convex minimization problem that can be seen as a generalized optimal transport problem involving matrix-valued density fields. The time boundary conditions enjoy a backward-forward structure of “ballistic” type, just as in mean-field game theory.

Class: 

Large orbit closures of translation surfaces are strata or loci of double covers II

Speaker: 
Paul Apisa
Alex Wright
Date: 
Thu, Jan 28, 2021
Location: 
Zoom
Conference: 
Pacific Dynamics Seminar
Abstract: 

Any translation surface can be presented as a collection of polygons in the plane with sides identified. By acting linearly on the polygons, we obtain an action of GL(2,R) on moduli spaces of translation surfaces. Recent work of Eskin, Mirzakhani, and Mohammadi showed that GL(2,R) orbit closures are locally described by linear equations on the edges of the polygons. However, which linear manifolds arise this way is mysterious.

In this lecture series, we will describe new joint work that shows that when an orbit closure is sufficiently large it must be a whole moduli space, called a stratum in this context, or a locus defined by rotation by π symmetry.

We define "sufficiently large" in terms of rank, which is the most important numerical invariant of an orbit closure, and is an integer between 1 and the genus g. Our result applies when the rank is at least 1+g/2, and so handles roughly half of the possible values of rank.

The five lectures will introduce novel and broadly applicable techniques, organized as follows:

An introduction to orbit closures, their rank, their boundary in the WYSIWYG partial compactification, and cylinder deformations.
Reconstructing orbit closures from their boundaries (this talk will explicate a preprint of the same name).
Recognizing loci of covers using cylinders (this talk will follow a preprint titled “Generalizations of the Eierlegende-Wollmilchsau”).
An overview of the proof of the main theorem; marked points (following the preprint “Marked Points on Translation Surfaces”); and a dichotomy for cylinder degenerations.
Completion of the proof of the main theorem.

Class: 
Subject: 

Combinatorial structures in perturbative quantum field theory

Speaker: 
Karen Yeats
Date: 
Fri, Jan 22, 2021
Location: 
Zoom
PIMS, University of Saskachewan
Conference: 
quanTA CRG Seminar
Abstract: 

I will give an overview of a few places where combinatorial structures have an interesting role to play in quantum field theory and which I have been involved in to varying degrees, from the Connes-Kreimer Hopf algebra and other renormalization Hopf algebras, to the combinatorics of Dyson-Schwinger equations and the graph theory of Feynman integrals.

For other events in this series see the quanTA events website.

Class: 

UBC/ PIMS Mathematical Sciences Young Faculty Award Colloquium: Liam Watson

Speaker: 
Liam Watson
Date: 
Fri, Jan 22, 2021 to Sat, Jan 23, 2021
Location: 
Online
Abstract: 

What is Khovanov homology, and when is it boring?

Khovanov homology, though relatively young, is difficult to survey in an hour. This talk will nevertheless attempt to do so, by focussing on the problem of characterizing thin links—those links with simplest-possible Khovanov homology. This is a story that is still unfolding; I will describe some progress that is part of a joint project with Artem Kotelskiy and Claudius Zibrowius.

Class: 
Subject: 

Large orbit closures of translation surfaces are strata or loci of double covers

Speaker: 
Paul Apisa
Alex Wright
Date: 
Thu, Jan 21, 2021
Location: 
Zoom
Conference: 
Pacific Dynamics Seminar
Abstract: 

Any translation surface can be presented as a collection of polygons in the plane with sides identified. By acting linearly on the polygons, we obtain an action of GL(2,R) on moduli spaces of translation surfaces. Recent work of Eskin, Mirzakhani, and Mohammadi showed that GL(2,R) orbit closures are locally described by linear equations on the edges of the polygons. However, which linear manifolds arise this way is mysterious.

In this lecture series, we will describe new joint work that shows that when an orbit closure is sufficiently large it must be a whole moduli space, called a stratum in this context, or a locus defined by rotation by π symmetry.

We define "sufficiently large" in terms of rank, which is the most important numerical invariant of an orbit closure, and is an integer between 1 and the genus g. Our result applies when the rank is at least 1+g/2, and so handles roughly half of the possible values of rank.

The five lectures will introduce novel and broadly applicable techniques, organized as follows:

  1. An introduction to orbit closures, their rank, their boundary in the WYSIWYG partial compactification, and cylinder deformations.
  2. Reconstructing orbit closures from their boundaries (this talk will explicate a preprint of the same name).
  3. Recognizing loci of covers using cylinders (this talk will follow a preprint titled “Generalizations of the Eierlegende-Wollmilchsau”).
  4. An overview of the proof of the main theorem; marked points (following the preprint “Marked Points on Translation Surfaces”); and a dichotomy for cylinder degenerations.
  5. Completion of the proof of the main theorem.
Class: 
Subject: 

The Erdos-Hajnal conjecture for the five-cycle

Speaker: 
Sophie Spirkl
Date: 
Thu, Jan 14, 2021
Location: 
Zoom
PIMS, University of Victoria
Conference: 
PIMS-UVic Discrete Math Seminar
Abstract: 

The Erdos-Hajnal conjecture states that for every graph H there exists c > 0 such that every n-vertex graph G either contains H as an induced subgraph, or has a clique or stable set of size at least n^c. I will talk about a proof of this conjecture for the case H = C5 (a five-cycle), and related results. The proof is based on an extension of a lemma about bipartite graphs due to Pach and Tomon. This is joint work with Maria Chudnovsky, Alex Scott, and Paul Seymour.

Class: 
Subject: 

A coupling approach in the computation of geometric ergodicity for stochastic dynamics

Speaker: 
Shirou Wang
Date: 
Wed, Dec 16, 2020
Location: 
Zoom
PIMS,University of Alberta
Conference: 
Emergent Research: The PIMS Postdoctoral Fellow Seminar
Abstract: 

This talk introduces a probabilistic approach to numerically compute geometric convergence rates in discrete or continuous stochastic systems. Choosing appropriate coupling mechanisms and combining them together, works well in many settings, especially in high-dimensions. Using this approach, it is observed that the rate of geometric ergodicity of a randomly perturbed system can, to some extent, reveal the degree of chaoticity of the unperturbed system. Potential applications of the coupling method and the visualization of higher dimensional non-convex functions, e.g., the loss functions of neural networks, will be discussed.

Class: 
Subject: 

Quantum State Transfer on Graphs

Speaker: 
Christopher van Bommel
Date: 
Wed, Jan 13, 2021
Location: 
Zoom
PIMS, University of Manitoba
Conference: 
Emergent Research: The PIMS Postdoctoral Fellow Seminar
Abstract: 

Quantum computing is believed to provide many advantages over traditional computing, particularly considering the speed at which computations can be performed. One of the challenges that needs to be resolved in order to construct a quantum computer is the transmission of information from one part of the computer to another. This transmission can be implemented by spin chains, which can be modeled as a graph, and analyzed using algebraic graph theory. The ideal situation is that of perfect state transfer, where there exists a time interval during which the information is perfectly moved from one location to another. As perfect state transfer is relatively rare, we also consider pretty good state transfer, where for any desired level of accuracy, there exists a time interval during which the information transfer achieves this accuracy. We will discuss determining whether graphs admit perfect or pretty good state transfer.

Class: 
Subject: 

Pages