Past Data Science Seminar

Tbc

The data revolution has changed the landscape of computational mathematics and has increased the demand for new numerical linear algebra tools to handle the vast amount of data. One crucial task is data compression to capture the inherent structure of data efficiently. Tensor-based approaches have gained significant traction in this setting by exploiting multilinear relationships in multiway data. In this talk, we will describe a matrix-mimetic tensor algebra that offers provably optimal compressed representations of high-dimensional data. We will compare this tensor-algebraic approach to other popular tensor decomposition techniques and show that our approach offers both theoretical and numerical advantages.

Sparse inversion and classification problems are ubiquitous in modern data science and imaging. They are often formulated as non-smooth minimisation problems. In sparse inversion, we minimise, e.g., the sum of a data fidelity term and an L1/LASSO regulariser. In classification, we consider, e.g., the sum of a data fidelity term and a non-smooth Ginzburg--Landau energy. Standard (sub)gradient descent methods have shown to be inefficient when approaching such problems. Splitting techniques are much more useful: here, the target function is partitioned into a sum of two subtarget functions -- each of which can be efficiently optimised. Splitting proceeds by performing optimisation steps alternately with respect to each of the two subtarget functions.

In this work, we study splitting from a stochastic continuous-time perspective. Indeed, we define a differential inclusion that follows one of the two subtarget function's negative subdifferential at each point in time. The choice of the subtarget function is controlled by a binary continuous-time Markov process. The resulting dynamical system is a stochastic approximation of the underlying subgradient flow. We investigate this stochastic approximation for an L1-regularised sparse inversion flow and for a discrete Allen-Cahn equation minimising a Ginzburg--Landau energy. In both cases, we study the longtime behaviour of the stochastic dynamical system and its ability to approximate the underlying subgradient flow at any accuracy. We illustrate our theoretical findings in a simple sparse estimation problem and also in low- and high-dimensional classification problems.

I will describe algorithms for regularizing and training deep neural networks. Soft constraints, which add a penalty term to the loss, are typically used as a form ofexplicit regularization for neural network training. In this talk I describe a method for efficiently incorporating constraints into a stochastic gradient Langevin framework for the training of deep neural networks. In contrast to soft constraints, our constraints offer direct control of the parameter space, which allows us to study their effect on generalization. In the second part of the talk, I illustrate the presence of latent multiple time scales in deep learning applications.

Different features present in the data can be learned by training a neural network on different time scales simultaneously. By choosing appropriate partitionings of the network parameters into fast and slow parts I show that our multirate techniques can be used to train deep neural networks for transfer learning applications in vision and natural language processing in half the time, without reducing the generalization performance of the model.

Characterising intractable high-dimensional random variables is one of the fundamental challenges in stochastic computation. We develop a deep transport map that is suitable for sampling concentrated distributions defined by an unnormalised density function. We approximate the target distribution as the push-forward of a reference distribution under a composition of order-preserving transformations, in which each transformation is formed by a tensor train decomposition. The use of composition of maps moving along a sequence of bridging densities alleviates the difficulty of directly approximating concentrated density functions. We propose two bridging strategies suitable for wide use: tempering the target density with a sequence of increasing powers, and smoothing of an indicator function with a sequence of sigmoids of increasing scales. The latter strategy opens the door to efficient computation of rare event probabilities in Bayesian inference problems.

Numerical experiments on problems constrained by differential equations show little to no increase in the computational complexity with the event probability going to zero, and allow to compute hitherto unattainable estimates of rare event probabilities for complex, high-dimensional posterior densities.
 

Topological signals associated not only to nodes but also to links and to the higher dimensional simplices of simplicial complexes are attracting increasing interest in signal processing, machine learning and network science. However, little is known about the collective dynamical phenomena involving topological signals. Typically, topological signals of a given dimension are investigated and filtered using the corresponding Hodge Laplacians. In this talk, I will introduce the topological Dirac operator that can be used to process simultaneously topological signals of different dimensions.  I will discuss the main spectral properties of the Dirac operator defined on networks, simplicial complexes and multiplex networks, and their relation to Hodge Laplacians.   I will show that topological signals treated with the Hodge Laplacians or with the Dirac operator can undergo collective synchronization phenomena displaying different types of critical phenomena. Finally, I will show how the Dirac operator allows to couple the dynamics of topological signals of different dimension leading to the Dirac signal processing of signals defined on nodes, links and triangles of simplicial complexes. 

In this talk, I will discuss and introduce deep insight from the dynamical system perspective to understand the convergence guarantees of first-order algorithms involving inertial features for convex optimization in a Hilbert space setting.

Such algorithms are widely popular in various areas of data science (data processing, machine learning, inverse problems, etc.).
They can be viewed discrete as time versions of an inertial second-order dynamical system involving different types of dampings (viscous damping,  Hessian-driven geometric damping).

The dynamical system perspective offers not only a powerful way to understand the geometry underlying the dynamic, but also offers a versatile framework to obtain fast, scalable and new algorithms enjoying nice convergence guarantees (including fast rates). In addition, this framework encompasses known algorithms and dynamics such as the Nesterov-type accelerated gradient methods, and the introduction of time scale factors makes it possible to further accelerate these algorithms. The framework is versatile enough to handle non-smooth and non-convex objectives that are ubiquituous in various applications.

While there have been substantial successes of actor-critic methods in continuous control, simpler critic-only methods such as Q-learning often remain intractable in the associated high-dimensional action spaces. However, most actor-critic methods come at the cost of added complexity: heuristics for stabilisation, compute requirements as well as wider hyperparameter search spaces. To address this limitation, we demonstrate in two stages how a simple variant of Deep Q Learning matches state-of-the-art continuous actor-critic methods when learning from simpler features or even directly from raw pixels. First, we take inspiration from control theory and shift from continuous control with policy distributions whose support covers the entire action space to pure bang-bang control via Bernoulli distributions. And second, we combine this approach with naive value decomposition, framing single-agent control as cooperative multi-agent reinforcement learning (MARL). We finally add illustrative examples from control theory as well as classical bandit examples from cooperative MARL to provide intuition for 1) when action extrema are sufficient and 2) how decoupled value functions leverage state information to coordinate joint optimization.

Numerical optimization is an indispensable tool of modern data analysis, and there are many optimization problems where it is difficult or impossible to compute the full gradient of the objective function. The field of derivative free optimization (DFO) addresses these cases by using only function evaluations, and has wide-ranging applications from hyper-parameter tuning in machine learning to PDE-constrained optimization.

We present two projects that attempt to scale DFO techniques to higher dimensions.  The first method converges slowly but works in very high dimensions, while the second method converges quickly but doesn't scale quite as well with dimension.  The first-method is a family of algorithms called "stochastic subspace descent" that uses a few directional derivatives at every step (i.e. projections of the gradient onto a random subspace). In special cases it is related to Spall's SPSA, Gaussian smoothing of Nesterov, and block-coordinate descent. We provide convergence analysis and discuss Johnson-Lindenstrauss style concentration.  The second method uses conventional interpolation-based trust region methods which require large ill-conditioned linear algebra operations.  We use randomized linear algebra techniques to ameliorate the issues and scale to larger dimensions; we also use a matrix-free approach that reduces memory issues.  These projects are in collaboration with David Kozak, Luis Tenorio, Alireza Doostan, Kevin Doherty and Katya Scheinberg.

I will discuss the use of partitioned schemes for neural networks. This work is in the tradition of multrate numerical ODE methods in which different components of system are evolved using different numerical methods or with different timesteps. The setting is the training tasks in deep learning in which parameters of a hierarchical model must be found to describe a given data set. By choosing appropriate partitionings of the parameters some redundant computation can be avoided and we can obtain substantial computational speed-up. I will demonstrate the use of the procedure in transfer learning applications from image analysis and natural language processing, showing a reduction of around 50% in training time, without impairing the generalization performance of the resulting models. This talk describes joint work with Tiffany Vlaar.

A common observation that wider (in the number of hidden units/channels/attention heads) neural networks perform better motivates studying them in the infinite-width limit.

Remarkably, infinitely wide networks can be easily described in closed form as Gaussian processes (GPs), at initialization, during, and after training—be it gradient-based, or fully Bayesian training. This provides closed-form test set predictions and uncertainties from an infinitely wide network without ever instantiating it (!).

These infinitely wide networks have become powerful models in their own right, establishing several SOTA results, and are used in applications including hyper-parameter selection, neural architecture search, meta learning, active learning, and dataset distillation.

The talk will provide a high-level overview of our work at Google Brain on infinite-width networks. In the first part I will derive core results, providing intuition for why infinite-width networks are GPs. In the second part I will discuss challenges and solutions to implementing and scaling up these GPs. In the third part, I will conclude with example applications made possible with infinite width networks.

The talk does not assume familiarity with the topic beyond general ML background.

4th IMA Conference on The Mathematical Challenges of Big Data

The 4th Ima Conference on The Mathematical Challenges of Big Data is issuing a Call For Papers for both contributed talks and posters. Mathematical foundations of data science and its ongoing challenges are rapidly growing fields, encompassing areas such as: network science, machine learning, modelling, information theory, deep and reinforcement learning, applied probability and random matrix theory. Applying deeper mathematics to data is changing the way we understand the environment, health, technology, quantitative humanities, the natural sciences, and beyond ‐ with increasing roles in society and industry. This conference brings together researchers and practitioners to highlight key developments in the state‐of‐the art and find common ground where theory and practice meet, to shape future directions and maximize impact. We particularly welcome talks aimed to inform on recent developments in theory or methodology that may have applied consequences, as well as reports of diverse applications that have led to interesting successes or uncovered new challenges.

Contributed talks and posters are welcomed from the mathematically oriented data science community. Contributions will be selected based on brief abstracts and can be based on previously unpresented results, or recent material originally presented elsewhere. We encourage contributions from both established and early career researchers. Contributions will be assigned to talks or posters based on the authors request as well as the views of the organizing committee on the suitability of the results. The conference will be held in person with the option to attend remotely where needed.

Inducement of sparsity, Heather Battey
Sparsity, the existence of many zeros or near-zeros in some domain, is widely assumed throughout the high-dimensional literature and plays at least two roles depending on context. Parameter orthogonalisation (Cox and Reid, 1987) is presented as inducement of population-level sparsity. The latter is taken as a unifying theme for the talk, in which sparsity-inducing parameterisations or data transformations are sought. Three recent examples are framed in this light: sparse parameterisations of covariance models; systematic construction of factorisable transformations for the elimination of nuisance parameters; and inference in high-dimensional regression. The solution strategy for the problem of exact or approximate sparsity inducement appears to be context specific and may entail, for instance, solving one or more partial differential equation, or specifying a parameterised path through transformation or parameterisation space.

Confirmed Invited Speakers
Dr Heather Battey, Imperial College London
Prof. Lenka Zdebrova, EPFL (Swiss Federal Institute Technology)
Prof. Nando de Freitas, Google Deep Mind
Prof. Tiago de Paula Peixoto, Central European University

Please follow the link below for Programme and Registration:

https://ima.org.uk/17625/4th-ima-conference-on-the-mathematical-challen…

Predicting a protein’s structure from its primary sequence has been a grand challenge in biology for the past 50 years, holding the promise to bridge the gap between the pace of genomics discovery and resulting structural characterization. In this talk, we will describe work at DeepMind to develop AlphaFold, a new deep learning-based system for structure prediction that achieves high accuracy across a wide range of targets. We demonstrated our system in the 14th biennial Critical Assessment of Protein Structure Prediction (CASP14) across a wide range of difficult targets, where the assessors judged our predictions to be at an accuracy “competitive with experiment” for approximately 2/3rds of proteins. The talk will cover both the underlying machine learning ideas and the implications for biological research as well as some promising further work.

Cryo-Electron Microscopy (cryo-EM) is an imaging technology that is revolutionizing structural biology. Cryo-electron microscopes produce many very noisy two-dimensional projection images of individual frozen molecules; unlike related methods, such as computed tomography (CT), the viewing direction of each particle image is unknown. The unknown directions and extreme noise make the determination of the structure of molecules challenging. While other methods for structure determination, such as x-ray crystallography and NMR, measure ensembles of molecules, cryo-electron microscopes produce images of individual particles. Therefore, cryo-EM could potentially be used to study mixtures of conformations of molecules. We will discuss a range of recent methods for analyzing the geometry of molecular conformations using cryo-EM data.

We consider the problem of finding the best memoryless stochastic policy for an infinite-horizon partially observable Markov decision process (POMDP) with finite state and action spaces with respect to either the discounted or mean reward criterion. We show that the (discounted) state-action frequencies and the expected cumulative reward are rational functions of the policy, whereby the degree is determined by the degree of partial observability. We then describe the optimization problem as a linear optimization problem in the space of feasible state-action frequencies subject to polynomial constraints that we characterize explicitly. This allows us to address the combinatorial and geometric complexity of the optimization problem using tools from polynomial optimization. In particular, we estimate the number of critical points and use the polynomial programming description of reward maximization to solve a navigation problem in a grid world. The talk is based on recent work with Johannes Müller.

Non-smooth optimization is a core ingredient of many imaging or machine learning pipelines. Non-smoothness encodes structural constraints on the solutions, such as sparsity, group sparsity, low-rank and sharp edges. It is also the basis for the definition of robust loss functions such as the square-root lasso.  Standard approaches to deal with non-smoothness leverage either proximal splitting or coordinate descent. The effectiveness of their usage typically depend on proper parameter tuning, preconditioning or some sort of support pruning. In this work, we advocate and study a different route. By over-parameterization and marginalising on certain variables (Variable Projection), we show how many popular non-smooth structured problems can be written as smooth optimization problems. The result is that one can then take advantage of quasi-Newton solvers such as L-BFGS and this, in practice, can lead to substantial performance gains. Another interesting aspect of our proposed solver is its efficiency when handling imaging problems that arise from fine discretizations (unlike proximal methods such as ISTA whose convergence is known to have exponential dependency on dimension). On a theoretical level, one can connect gradient descent on our over-parameterized formulation with mirror descent with a varying Hessian metric. This observation can then be used to derive dimension free convergence bounds and explains the efficiency of our method in the fine-grids regime.

Given two probability distributions in R^d, a transport map is a function which maps samples from one distribution into samples from the other. For absolutely continuous measures, Brenier proved a remarkable theorem identifying a unique canonical transport map, which is "monotone" in a suitable sense. We study the question of whether this map can be efficiently estimated from samples. The minimax rates for this problem were recently established by Hutter and Rigollet (2021), but the estimator they propose is computationally infeasible in dimensions greater than three. We propose two new estimators---one minimax optimal, one not---which are significantly more practical to compute and implement. The analysis of these estimators is based on new stability results for the optimal transport problem and its regularized variants. Based on joint work with Manole, Balakrishnan, and Wasserman and with Pooladian.

The alchemists wanted to create gold, Hilbert wanted an algorithm to solve Diophantine equations, researchers want to make deep learning robust in AI, MATLAB wants (but fails) to detect when it provides wrong solutions to linear programs etc. Why does one not succeed in so many of these fundamental cases? The reason is typically methodological barriers. The history of  science is full of methodological barriers — reasons for why we never succeed in reaching certain goals. In many cases, this is due to the foundations of mathematics. We will present a new program on methodological barriers and foundations of mathematics,  where — in this talk — we will focus on two basic problems: (1) The instability problem in deep learning: Why do researchers fail to produce stable neural networks in basic classification and computer vision problems that can easily be handled by humans — when one can prove that there exist stable and accurate neural networks? Moreover, AI algorithms can typically not detect when they are wrong, which becomes a serious issue when striving to create trustworthy AI. The problem is more general, as for example MATLAB's linprog routine is incapable of certifying correct solutions of basic linear programs. Thus, we’ll address the following question: (2) Why are algorithms (in AI and computations in general) incapable of determining when they are wrong? These questions are deeply connected to the extended Smale’s 9th and 18th problems on the list of mathematical problems for the 21st century. 

Blind deconvolution problems are ubiquitous in many areas of imaging and technology and have been the object of study for several decades. Recently, motivated by the theory of compressed sensing, a new viewpoint has been introduced, motivated by applications in wireless application, where a signal is transmitted through an unknown channel. Namely, the idea is to randomly embed the signal into a higher dimensional space before transmission. Due to the resulting redundancy, one can hope to recover both the signal and the channel parameters. In this talk we analyze convex approaches based on lifting as they have first been studied by Ahmed et al. (2014). We show that one encounters a fundamentally different geometric behavior as compared to generic bilinear measurements. Namely, for very small levels of deterministic noise, the error bounds based on common paradigms no longer scale linearly in the noise level, but one encounters dimensional constants or a sublinear scaling. For larger - arguably more realistic - noise levels, in contrast, the scaling is again near-linear.

This is joint work with Yulia Kostina (TUM) and Dominik Stöger (KU Eichstätt-Ingolstadt).

Volumetric X-ray tomography is used in many areas, including applications in medical imaging, many fields of scientific investigation as well as several industrial settings. Yet complex X-ray physics and the significant size of individual x-ray tomography data-sets poses a range of data-science challenges from the development of efficient computational methods, the modelling of complex non-linear relationships, the effective analysis of large volumetric images as well as the inversion of several ill conditioned inverse problems, all of which prevent the application of these techniques in many advanced imaging settings of interest. This talk will highlight several applications were specific data-science issues arise and showcase a range of approaches developed recently at the University of Southampton to overcome many of these obstacles.

We consider the problem of parameter estimation for a McKean stochastic differential equation, and the associated system of weakly interacting particles. The problem is motivated by many applications in areas such as neuroscience, social sciences (opinion dynamics, cooperative behaviours), financial mathematics, statistical physics. We will first survey some model properties related to propagation of chaos and ergodicity and then move on to discuss the problem of parameter estimation both in offline and on-line settings. In the on-line case, we propose an online estimator, which evolves according to a continuous-time stochastic gradient descent algorithm on the asymptotic log-likelihood of the interacting particle system. The talk will present our convergence results and then show some numerical results for two examples, a linear mean field model and a stochastic opinion dynamics model. This is joint work with Louis Sharrock, Panos Parpas and Greg Pavliotis. Preprint: https://arxiv.org/abs/2106.13751

We study sampling from a target distribution $e^{-f}$ using the unadjusted Langevin Monte Carlo (LMC) algorithm. For any potential function $f$ whose tails behave like $\|x\|^\alpha$ for $\alpha \in [1,2]$, and has $\beta$-H\"older continuous gradient, we derive the sufficient number of steps to reach the $\epsilon$-neighborhood of a $d$-dimensional target distribution as a function of $\alpha$ and $\beta$. Our rate estimate, in terms of $\epsilon$ dependency, is not directly influenced by the tail growth rate $\alpha$ of the potential function as long as its growth is at least linear, and it only relies on the order of smoothness $\beta$.

Our rate recovers the best known rate which was established for strongly convex potentials with Lipschitz gradient in terms of $\epsilon$ dependency, but we show that the same rate is achievable for a wider class of potentials that are degenerately convex at infinity.

The success of operator splitting techniques for convex optimization has led to an explosion of methods for solving large-scale and non convex optimization problems via convex relaxation. 

This success is at the cost of overlooking direct approaches to operator splitting that embrace some of the more inconvenient aspects of many model problems, namely nonconvexity, non smoothness and infeasibility.  I will introduce some of the tools we have developed for handling these issues, and present sketches of the basic results we can obtain.

The formalism is in general metric spaces, but most applications have their basis in Euclidean spaces.  Along the way I will try to point out connections to other areas of intense interest, such as optimal mass transport.

One of the great challenges of neural networks is to understand how they work.  For example: does a neuron encode a meaningful signal on its own?  Or is a neuron simply an undistinguished and arbitrary component of a feature vector space?  The tension between the neuron doctrine and the population coding hypothesis is one of the classical debates in neuroscience. It is a difficult debate to settle without an ability to monitor every individual neuron in the brain.

Within artificial neural networks we can examine every neuron. Beginning with the simple proposal that an individual neuron might represent one internal concept, we conduct studies relating deep network neurons to human-understandable concepts in a concrete, quantitative way: Which neurons? Which concepts? Are neurons more meaningful than an arbitrary feature basis? Do neurons play a causal role? We examine both simplified settings and state-of-the-art networks in which neurons learn how to represent meaningful objects within the data without explicit supervision.

Following this inquiry in computer vision leads us to insights about the computational structure of practical deep networks that enable several new applications, including semantic manipulation of objects in an image; understanding of the sparse logic of a classifier; and quick, selective editing of generalizable rules within a fully trained generative network.  It also presents an unanswered mathematical question: why is such disentanglement so pervasive?

In the talk, we challenge the notion that the internal calculations of a neural network must be hopelessly opaque. Instead, we propose to tear back the curtain and chart a path through the detailed structure of a deep network by which we can begin to understand its logic.

Many machine learning applications involve non-Euclidean data, such as graphs, strings or matrices. In such cases, exploiting Riemannian geometry can deliver algorithms that are computationally superior to standard(Euclidean) nonlinear programming approaches. This observation has resulted in an increasing interest in Riemannian methods in the optimization and machine learning community.

In the first part of the talk, we consider the task of learning a robust classifier in hyperbolic space. Such spaces have received a surge of interest for representing large-scale, hierarchical data, due to the fact that theyachieve better representation accuracy with fewer dimensions. We present the first theoretical guarantees for the (robust) large margin learning problem in hyperbolic space and discuss conditions under which hyperbolic methods are guaranteed to surpass the performance of their Euclidean counterparts. In the second part, we introduce Riemannian Frank-Wolfe (RFW) methods for constrained optimization on manifolds. Here, we discuss matrix-valued tasks for which such Riemannian methods are more efficient than classical Euclidean approaches. In particular, we consider applications of RFW to the computation of Riemannian centroids and Wasserstein barycenters, both of which are crucial subroutines in many machine learning methods.