The LMS Computer Science Colloquium is an annual online event, which includes themed talks on a topical issue at the interface of mathematics and computer science. It is organised by the LMS Computer Science Committee. The event is aimed at PhD students and post-docs, although others are welcome to attend.
This year the event will take place on 17th November 2021 via Zoom and the theme will be Mathematical Foundations for Machine Learning. The event will start at 10am, with introductions from the LMS Computer Science Committee, followed by talks by four speakers.
The confirmed speakers for this year's event are:
10am-11am: Benjamin Guedj: On generalisation and learning: a (condensed) primer on PAC-Bayes, followed by News from the PAC-Bayes frontline
11am-11:30am: breakout sessions
11:30-12:30: Peter Tino: From dynamical systems to kernel based feature spaces and back
13:30-14:30: Aretha Teckentrup: Numerical analysis of Gaussian process regression
14:30-15:00: breakout sessions
15:00-16:00: Alexandros Hollender: The Complexity of Gradient Descent: CLS = PPAD ∩ PLS
Titles and abstracts
On generalisation and learning: a (condensed) primer on PAC-Bayes, followed by News from the PAC-Bayes frontline
PAC-Bayes is a generic and flexible framework to address generalisation abilities of machine learning algorithms. It leverages the power of Bayesian inference and allows to derive new learning strategies. I will briefly present the key concepts of PAC-Bayes and highlight a few recent contributions from my group.
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS
We consider the problem of computing a Gradient Descent solution of a continuously differentiable function f on a bounded convex domain, i.e., finding a "point where Gradient Descent terminates". Equivalently, this corresponds to computing a so-called KKT (Karush-Kuhn-Tucker) stationary point of f.
We study this problem in the "white box" model, where the function f is given in the input, e.g., as an arithmetic circuit. By some standard arguments, it follows that the problem lies in the intersection of the complexity classes PPAD and PLS. PPAD is mostly known for capturing the complexity of computing a Nash equilibrium, while PLS has been successful in characterizing the complexity of various local optimization problems, such as Local-Max-Cut.
We prove that the Gradient Descent problem is complete for PPAD ∩ PLS. In particular, this implies that the class CLS ("Continuous Local Search") which was previously thought to be a strict subset of PPAD ∩ PLS, is in fact equal to it.
Numerical analysis of Gaussian process regression
We are interested in the task of estimating an unknown function from observed data, given as a set of input/output pairs. In this context, Gaussian process regression is often used as a Bayesian inference procedure. This results in a probability distribution on the unknown function conditioned on the observed data, the so-called posterior distribution.
In this talk, we will survey some recent results on convergence properties of Gaussian process regression, and show how tools from applied mathematics can provide insight into the behaviour of this methodology. A particular focus will be on analysing an empirical Bayes' approach for estimating unknown hyper-parameters, and on studying the intrinsic depth of deep Gaussian processes.
From dynamical systems to kernel based feature spaces and back
Parametrized state space models in the form of recurrent neural networks are often used in machine learning to learn from data streams exhibiting temporal dependencies. Such models are usually composed of two parts: an input-driven dynamical system and a (static) readout mapping from the state space of the dynamical system to the outputs.
I will talk about a framework for rigorous analysis of such dynamical systems in a class of recurrent neural networks known as Echo State Networks (ESN). In particular, I will show that there is a deep connection between the state space and the notion of feature space in kernel machines (a well known class of machine learning methods). This viewpoint will lead to several rather surprising results linking the structure of the dynamical coupling in ESN with properties of the associated temporal feature space.
Previous Computer Science Colloquia
The most recent colloquium was held on 19th November 2020 and the topic was 'Algorithms, Complexity and Logic'. The programme for the day, including abstracts, can be accessed here. The speakers and their talks were as follows:
- Anupam Das (Birmingham): The size of proofs: from mathematical logic to computational complexity and back
- Nobuko Yoshida: Session Types: A History and Applications
- Kitty Meeks: From decision to approximate counting
- Igor Carboni Oliveira: Kolmogorov complexity, prime numbers, and complexity lower bounds