Tue, 14 Jun 2022

14:00 - 15:00
L4

Resolution of the Erdős-Sauer problem on regular subgraphs

Benny Sudakov
(ETH Zurich)
Abstract

In this talk we discuss solution of the well-known problem of Erdős and Sauer from 1975 which asks for the maximum number of edges an $n$-vertex graph can have without containing a $k$-regular subgraph, for some fixed integer $k\geq 3$. We prove that any $n$-vertex graph with average degree at least $C_k\log\log n$ contains a $k$-regular subgraph. This matches the lower bound of Pyber, Rödl and Szemerédi and substantially
improves an old result of Pyber, who showed that average degree at least $C_k\log n$ is enough.

Our method can also be used to settle asymptotically a problem raised by Erdős and Simonovits in 1970 on almost regular subgraphs of sparse graphs and to make progress on the well-known question of Thomassen from 1983 on finding subgraphs with large girth and large average degree.

Joint work with Oliver Janzer

Tue, 24 May 2022

14:00 - 15:00
L3

Size-Ramsey numbers of graphs with maximum degree three

Nemanja Draganić
(ETH Zurich)
Abstract

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.

Tue, 31 May 2022

14:00 - 15:00
C6

Physics-inspired machine learning

Konstantin Rusch
(ETH Zurich)
Abstract

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.

Mon, 21 Feb 2022

15:30 - 16:30
L3

The Wasserstein space of stochastic processes & computational aspects.

GUDMUND PAMMER
(ETH Zurich)
Abstract

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.

Mon, 07 Jun 2021
12:45
Virtual

The string dual of free N=4 SYM

Matthias Gaberdiel
(ETH Zurich)
Abstract

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.
 

Thu, 25 Feb 2021

16:00 - 17:00
Virtual

Discrete-time signatures and randomness in reservoir computing (joint work with Christa Cuchiero, Lukas Gonon, Lyudmila Grigoryeva, Juan-Pablo Ortega)

Josef Teichmann
(ETH Zurich)
Further Information
Abstract

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.

Mon, 09 Nov 2020

16:00 - 17:00

Space-time deep neural network approximations for high-dimensional partial differential equations

DIYORA SALIMOVA
(ETH Zurich)
Abstract


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. 

 

Fri, 13 Nov 2020

12:00 - 13:00

Computational Hardness of Hypothesis Testing and Quiet Plantings

Afonso Bandeira
(ETH Zurich)
Abstract

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.

Thu, 22 Oct 2020

14:00 - 15:00
Virtual

Classifier-based Distribution-Dissimilarities: From Maximum Mean Discrepancies to Adversarial Examples

Carl-Johann Simon-Gabriel
(ETH Zurich)
Further Information

datasig.ox.ac.uk/events

Abstract

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.

Mon, 30 Nov 2020

16:00 - 17:00

Model-independence in a fixed-income market and weak optimal transport

BEATRICE ACCIAIO
(ETH Zurich)
Abstract

 

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.

Subscribe to ETH Zurich