ETH Zurich

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.
 

Topological features as computed via persistent homology offer a non-parametric approach to robustly capture multi-scale connectivity information of complex datasets. This has started to gain attention in various machine learning applications. Conventionally, in topological data analysis, this method has been employed as an immutable feature descriptor in order to characterize topological properties of datasets. In this talk, however, I will explore how topological features can be directly integrated into deep learning architectures. This allows us to impose differentiable topological constraints for preserving the global structure of the data space when learning low-dimensional representations.

The classical Erdős-Szekeres theorem dating back almost a hundred years states that any sequence of $(n-1)^2+1$ distinct real numbers contains a monotone subsequence of length $n$. This theorem has been generalised to higher dimensions in a variety of ways but perhaps the most natural one was proposed by Fishburn and Graham more than 25 years ago. They raise the problem of how large should a $d$-dimesional array be in order to guarantee a "monotone" subarray of size $n \times n \times \ldots \times n$. In this talk we discuss this problem and show how to improve their original Ackerman-type bounds to at most a triple exponential. (Joint work with M. Bucic and T. Tran)

An important property of Gromov hyperbolic spaces is the fact that every path for which all sufficiently long subpaths are quasi-geodesics is itself a quasi-geodesic. Gromov showed that this property is actually a characterization of hyperbolic spaces. In this talk, we will consider a weakened version of this local-to-global behaviour, called the Morse local-to-global property. The class of spaces that satisfy the Morse local-to-global property include several examples of interest, such as CAT(0) spaces, Mapping Class Groups, fundamental groups of closed 3-manifolds and more. The leverage offered by knowing that a space satisfies this property allows us to import several results and techniques from the theory of hyperbolic groups. In particular, we obtain results relating to stable subgroups, normal subgroups and algorithmic properties.

 A central task in modeling, which has to be performed each day in banks and financial institutions, is to calibrate models to market and historical data. So far the choice which models should be used was not only driven by their capacity of capturing empirically the observed market features well, but rather by computational tractability considerations. Due to recent work in the context of machine learning, this notion of tractability has changed significantly. In this work, we show how a neural network approach can be applied to the calibration of (multivariate) local stochastic volatility models. We will see how an efficient calibration is possible without the need of interpolation methods for the financial data. Joint work with Christa Cuchiero and Josef Teichmann.