ETH Zurich

The size-Ramsey number $\hat{r}(H)$ of a graph $H$ is the smallest number of edges a (host) graph $G$ can have, such that for any red/blue coloring of $G$, there is a monochromatic copy of $H$ in $G$. Recently, Conlon, Nenadov and Trujić showed that if $H$ is a graph on $n$ vertices and maximum degree three, then $\hat{r}(H) = O(n^{8/5})$, improving upon the bound of $n^{5/3 + o(1)}$ by Kohayakawa, Rödl, Schacht and Szemerédi. In our paper, we show that $\hat{r}(H)\leq n^{3/2+o(1)}$. While the previously used host graphs were vanilla binomial random graphs, we prove our result by using a novel host graph construction.
We also discuss why our bound is a natural barrier for the existing methods.
This is joint work with Kalina Petrova.

Combining physics with machine learning is a rapidly growing field of research. Thereby, most work focuses on leveraging machine learning methods to solve problems in physics. Here, however, we focus on the reverse direction of leveraging structure of physical systems (e.g. dynamical systems modeled by ODEs or PDEs) to construct novel machine learning algorithms, where the existence of highly desirable properties of the underlying method can be rigorously proved. In particular, we propose several physics-inspired deep learning architectures for sequence modelling as well as for graph representation learning. The proposed architectures mitigate central problems in each corresponding domain, such as the vanishing and exploding gradients problem for recurrent neural networks or the oversmoothing problem for graph neural networks. Finally, we show that this leads to state-of-the-art performance on several widely used benchmark problems.

Wasserstein distance induces a natural Riemannian structure for the probabilities on the Euclidean space. This insight of classical transport theory is fundamental for tremendous applications in various fields of pure and applied mathematics. We believe that an appropriate probabilistic variant, the adapted Wasserstein distance $AW$, can play a similar role for the class $FP$ of filtered processes, i.e. stochastic processes together with a filtration. In contrast to other topologies for stochastic processes, probabilistic operations such as the Doob-decomposition, optimal stopping and stochastic control are continuous w.r.t. $AW$. We also show that $(FP, AW)$ is a geodesic space, isometric to a classical Wasserstein space, and that martingales form a closed geodesically convex subspace. Finally we consider computational aspects and provide a novel method based on the Sinkhorn algorithm.

The talk is based on articles with Daniel Bartl, Mathias Beiglböck and Stephan Eckstein.

A proposal for the worldsheet string theory that is dual to free N=4 SYM in 4d will be explained. It is described by a free field sigma model on the twistor space of AdS5 x S5, and is a direct generalisation of the corresponding model for tensionless string theory on AdS3 x S3. I will explain how our proposal fits into the general framework of AdS/CFT, and review the various checks that have been performed.
 

A new explanation of geometric nature of the reservoir computing phenomenon is presented. Reservoir computing is understood in the literature as the possibility of approximating input/output systems with randomly chosen recurrent neural systems and a trained linear readout layer. Light is shed on this phenomenon by constructing what is called strongly universal reservoir systems as random projections of a family of state-space systems that generate Volterra series expansions. This procedure yields a state-affine reservoir system with randomly generated coefficients in a dimension that is logarithmically reduced with respect to the original system. This reservoir system is able to approximate any element in the fading memory filters class just by training a different linear readout for each different filter. Explicit expressions for the probability distributions needed in the generation of the projected reservoir system are stated and bounds for the committed approximation error are provided.

It is one of the most challenging issues in applied mathematics to approximately solve high-dimensional partial differential equations (PDEs) and most of the numerical approximation methods for PDEs in the scientific literature suffer from the so-called curse of dimensionality (CoD) in the sense that the number of computational operations employed in the corresponding approximation scheme to obtain an  approximation precision $\varepsilon >0$ grows exponentially in the PDE dimension and/or the reciprocal of $\varepsilon$. Recently, certain deep learning based approximation methods for PDEs have been proposed  and various numerical simulations for such methods suggest that deep neural network (DNN) approximations might have the capacity to indeed overcome the CoD in the sense that  the number of real parameters used to describe the approximating DNNs  grows at most polynomially in both the PDE dimension $d \in  \N$ and the reciprocal of the prescribed approximation accuracy $\varepsilon >0$. There are now also a few rigorous mathematical results in the scientific literature which  substantiate this conjecture by proving that  DNNs overcome the CoD in approximating solutions of PDEs.  Each of these results establishes that DNNs overcome the CoD in approximating suitable PDE solutions  at a fixed time point $T >0$ and on a compact cube $[a, b]^d$ but none of these results provides an answer to the question whether the entire PDE solution on $[0, T] \times [a, b]^d$ can be approximated by DNNs without the CoD. 
In this talk we show that for every $a \in \R$, $ b \in (a, \infty)$ solutions of  suitable  Kolmogorov PDEs can be approximated by DNNs on the space-time region $[0, T] \times [a, b]^d$ without the CoD. 

When faced with a data analysis, learning, or statistical inference problem, the amount and quality of data available fundamentally determines whether such tasks can be performed with certain levels of accuracy. With the growing size of datasets however, it is crucial not only that the underlying statistical task is possible, but also that is doable by means of efficient algorithms. In this talk we will discuss methods aiming to establish limits of when statistical tasks are possible with computationally efficient methods or when there is a fundamental «Statistical-to-Computational gap›› in which an inference task is statistically possible but inherently computationally hard. We will focus on Hypothesis Testing and the ``Low Degree Method'' and also address hardness of certification via ``quiet plantings''. Guiding examples will include Sparse PCA, bounds on the Sherrington Kirkpatrick Hamiltonian, and lower bounds on Chromatic Numbers of random graphs.

Any binary classifier (or score-function) can be used to define a dissimilarity between two distributions of points with positive and negative labels. Actually, many well-known distribution-dissimilarities are classifier-based dissimilarities: the total variation, the KL- or JS-divergence, the Hellinger distance, etc. And many recent popular generative modelling algorithms compute or approximate these distribution-dissimilarities by explicitly training a classifier: eg GANs and their variants. After a brief introduction to these classifier-based dissimilarities, I will focus on the influence of the classifier's capacity. I will start with some theoretical considerations illustrated on maximum mean discrepancies --a weak form of total variation that has grown popular in machine learning-- and then focus on deep feed-forward networks and their vulnerability to adversarial examples. We will see that this vulnerability is already rooted in the design and capacity of our current networks, and will discuss ideas to tackle this vulnerability in future.

In this talk I will consider model-independent pricing problems in a stochastic interest rates framework. In this case the usual tools from Optimal Transport and Skorokhod embedding cannot be applied. I will show how some pricing problems in a fixed-income market can be reformulated as Weak Optimal Transport (WOT) problems as introduced by Gozlan et al. I will present a super-replication theorem that follows from an extension of WOT results to the case of non-convex cost functions.
This talk is based on joint work with M. Beiglboeck and G. Pammer.

Topological data analysis has proven to be an effective tool in machine learning, supporting the analysis of neural networks, but also driving the development of new algorithms that make use of topological features. Graph classification is of particular interest here, since graphs are inherently amenable to a topological description in terms of their connected components and cycles. This talk will briefly summarise recent advances in topology-based graph classification, focussing equally on ’shallow’ and ‘deep’ approaches. Starting from an intuitive description of persistent homology, we will discuss how to incorporate topological features into the Weisfeiler–Lehman colour refinement scheme, thus obtaining a simple feature-based graph classification algorithm. We will then build a bridge to graph neural networks and demonstrate a topological variant of ‘readout’ functions, which can be learned in an end-to-end fashion. Care has been taken to make the talk accessible to an audience that might not have been exposed to machine learning or topological data analysis.