University of Oxford

The signature of a path in Euclidean space resides in the tensor algebra of that space; it is obtained by systematic iterated integration of the components of the given path against one another. This straightforward definition conceals a host of deep theoretical properties and impressive practical consequences. In this talk I will describe the homotopical origins of path signatures, their subsequent application to stochastic analysis, and how they facilitate efficient machine learning in topological data analysis. This last bit is joint work with Ilya Chevyrev and Harald Oberhauser.

Multi-agent reinforcement learning (MARL) has enjoyed substantial successes in many applications including the game of Go, online Ad bidding systems, realtime resource allocation, and autonomous driving. Despite the empirical success of MARL, general theories behind MARL algorithms are less developed due to the intractability of interactions, complex information structure, and the curse of dimensionality. Instead of directly analyzing the multi-agent games, mean-field theory provides a powerful approach to approximate the games under various notions of equilibria. Moreover, the analytical feasible framework of mean-field theory leads to learning algorithms with theoretical guarantees. In this talk, we will demonstrate how mean-field theory can contribute to the simultaneous-learning-and-decision-making problems with unknown rewards and dynamics. 

To approximate Nash equilibrium, we first formulate a generalized mean-field game (MFG) and establish the existence and uniqueness of the MFG solution. Next we show the lack of stability in naive combination of the Q-learning algorithm and the three-step fixed-point approach in classical MFGs. We then propose both value-based and policy-based algorithms with smoothing and stabilizing techniques, and establish their convergence and complexity results. The numerical performance shows superior computational efficiency. This is based on joint work with Xin Guo (UC Berkeley), Anran Hu (UC Berkeley), and Junzi Zhang (Stanford).

If time allows, we will also discuss learning algorithms for multi-agent collaborative games using mean-field control. The key idea is to establish the time consistent property, i.e., the dynamic programming principle (DPP) on the lifted probability measure space. We then propose a kernel-based Q-learning algorithm. The convergence and complexity results are carried out accordingly. This is based on joint work with Haotian Gu, Xin Guo, and Xiaoli Wei (UC Berkeley).

Contagion maps are a family of maps that map nodes of a network to points in a high-dimensional space, based on the activations times in a threshold contagion on the network. A point cloud that is the image of such a map reflects both the structure underlying the network and the spreading behaviour of the contagion on it. Intuitively, such a point cloud exhibits features of the network's underlying structure if the contagion spreads along that structure, an observation which suggests contagion maps as a viable manifold-learning technique. We test contagion maps as a manifold-learning tool on several different data sets, and compare its performance to that of Isomap, one of the most well-known manifold-learning algorithms. We find that, under certain conditions, contagion maps are able to reliably detect underlying manifold structure in noisy data, when Isomap is prone to noise-induced error. This consolidates contagion maps as a technique for manifold learning. 

Eigenvalue-eigenvector pairs of combinatorial graph Laplacians are extensively used in graph theory and network analysis. It is well known that the spectrum of the Laplacian L of a given graph G encodes aspects of the geometry of G  - the multiplicity of the eigenvalue 0 counts the number of connected components while the second smallest eigenvalue (called the Fiedler eigenvalue) quantifies the well-connectedness of G . In network analysis, one uses Laplacian eigenvectors associated with small eigenvalues to perform spectral clustering. In graph signal processing, graph Fourier transforms are defined in terms of an orthonormal eigenbasis of L. Eigenvectors of L also play a central role in graph neural networks.

Motivated by this we study eigenvalue-eigenvector pairs of Laplacians of random graphs and their potential use in TDA. I will present simulation results on what persistent homology barcodes of Bernoulli random graphs G(n, p) look like when we use Laplacian eigenvectors as filter functions. Also, I will discuss the conjectures made from the simulations as well as the challenges that arise when trying to prove them. This is work in progress.
 

Non-uniformly elliptic functionals are variational integrals like
\[
(1) \qquad \qquad W^{1,1}_{loc}(\Omega,\mathbb{R}^{N})\ni w\mapsto \int_{\Omega} \left[F(x,Dw)-f\cdot w\right] \, \textrm{d}x,
\]
characterized by quite a wild behavior of the ellipticity ratio associated to their integrand $F(x,z)$, in the sense that the quantity
$$
\sup_{\substack{x\in B \\ B\Subset \Omega \ \small{\mbox{open ball}}}}\mathcal R(z, B):=\sup_{\substack{x\in B \\ B\Subset \Omega \ \small{\mbox{open ball}}}} \frac{\mbox{highest eigenvalue of}\ \partial_{z}^{2} F(x,z)}{\mbox{lowest eigenvalue of}\  \partial_{z}^{2} F(x,z)} $$
may blow up as $|z|\to \infty$. 
We analyze the interaction between the space-depending coefficient of the integrand and the forcing term $f$ and derive optimal Lipschitz criteria for minimizers of (1). We catch the main model cases appearing in the literature, such as functionals with unbalanced power growth or with fast exponential growth such as
$$
w \mapsto \int_{\Omega} \gamma_1(x)\left[\exp(\exp(\dots \exp(\gamma_2(x)|Dw|^{p(x)})\ldots))-f\cdot w \right]\, \textrm{d}x
$$
or
$$
w\mapsto \int_{\Omega}\left[|Dw|^{p(x)}+a(x)|Dw|^{q(x)}-f\cdot w\right] \, \textrm{d}x.
$$
Finally, we find new borderline regularity results also in the uniformly elliptic case, i.e. when
$$\mathcal{R}(z,B)\sim \mbox{const}\quad \mbox{for all balls} \ \ B\Subset \Omega.$$

The talk is based on:
C. De Filippis, G. Mingione, Lipschitz bounds and non-autonomous functionals. $\textit{Preprint}$ (2020).

Much progress in the study of 3-manifolds has been made by considering the geometric structures they admit. This is nowhere more true than for 3-manifolds which admit a hyperbolic structure. However, in the land of algorithms a more combinatorial approach is necessary, replacing our charts and isometries with finite simplicial complexes that are defined by a finite amount of data. 

In this talk we'll have a look at how in fact one can combine the two approaches, using the geometry of hyperbolic 3-manifolds to assist in this more combinatorial approach. To do so we'll combine tools from Hyperbolic Geometry, Triangulations, and perhaps suprisingly Polynomial Algebra to find explicit bounds on the runtime of an algorithm for comparing Hyperbolic manifolds.

The mapping class group of a surface with boundary acts freely and properly discontinuously on the fatgraph complex, which is a contractible cell complex arising from a cell decomposition of Teichmuller space. We will use this action to get a presentation of the mapping class group in terms of fat graphs, and convert this into one in terms of chord diagrams. This chord slide presentation has potential applications to computing bordered Heegaard Floer invariants for open books with disconnected binding.